单链表 – 数据结构

概念介绍
链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

链接存储方法

链接方式存储的线性表简称为链表（Linked List）。

链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

List 头部文件

//List.h
class LNode
{
public:
  int data;     //数据域
  LNode * next;  //指针域
};
 
class List
{
public:
  List();
  ~List();
  void CreateList();
  void Insert(int data, int index, bool flag = true);
  void Delete(int index);
  void printList();
  void getData(int index);
  void exchange(int index1, int index2);
  int getLength();
private:
  LNode *head;//头结点
};

List 实现部分 及 main函数

//List.cpp
#include<iostream>
#include"List.h"
using namespace std;
 
List::List()
{
  head = new LNode;
  head->next = NULL;
  cout << "创建对象成功！" << endl;
}
 
List::~List()
{
  LNode *p = head, *s;
  while (p->next != NULL){
    s = p->next;
    p = s->next;
    delete s;
  }
  delete p;
  delete head;
}
 
int List::getLength()
{
  int len = 0;
  LNode *p = head;
  while (p->next!=NULL)
  {
    len++;
    p = p->next;
  }
  return len;
}
 
void List::CreateList()
{
  int data_num,data;
  cout << "开始创建链表（尾插）,请输入数据个数: ";
  cin >> data_num;
  for (int i = 0; i < data_num;i++)
  {
    cout << "请输入第" << i + 1 << "个数据: ";
    cin >> data;
    Insert(data, getLength() + 2, false);//这里我就没有用正儿八经的尾插，因为已经有Insert函数了
  }
  cout << "CreateList: 创建完成" << endl;
}
 
//把元素data，插入第index个位置
void List::Insert(int data, int index,bool flag)
{
  LNode *p = head, *s;
  if (index<=0)
  {
    cout << "插入失败，请输入大于0的数！" << endl;
    return;
  }
  if (getLength() + 1 < index)
  {
    while (p->next != NULL)
    {
      p = p->next;
    }
    s = (LNode *)new LNode[1];
    s->data = data;
    s->next = NULL;
    p->next = s;
    if (flag != false)
    {
      cout << "Insert: 链表长度为" << getLength()-1 << ",无法插入到第" << index << "个位置；";
      cout << "现将数据" << data << "插入链表尾部！" << endl;
    }
  }
  else
  {
    for (int i = 0; i < index-1; i++)
    {
      p = p->next;
    }
    s = (LNode *)new LNode[1];
    s->data = data;
    s->next = p->next;
    p->next = s;
    cout << "数据" << data <<"插入" << "第" << index <<"位置成功！" << endl;
  }
}
 
//删除元素
void List::Delete(int index)
{
  LNode *p = head, *s;
  int i = 0;
  if (index <= 0 || index>getLength())
  {
    cout << "待删除元素不在链表中" << endl;
    return;
  }
  while (i<index-1)
  {
    i++;
    p = p->next;
  }
  
  s = p->next;
  p->next = s->next;
  cout << "第" << index <<"个元素删除成功！" << endl;
  delete s;
}
 
//打印链表
void List::printList()
{
  LNode *p = head;
  cout << "printList: ";
  if (p->next==NULL)
  {
    cout << "空链表" << endl;
    return;
  }
  p = p->next;
  while (p!=NULL)
  {
    cout << p->data << " ";
    p = p->next;
  }
  cout << endl;
}
 
//交换元素
void List::exchange(int index1, int index2)
{
  LNode *p = head, *s1, *s2;
  s1 = (LNode *)new LNode[1];
  s2 = (LNode *)new LNode[1];
  int data;
  int min = (index1 > index2) ? index2 : index1;
  int max = (index1 > index2) ? index1 : index2;
  if (min<=0 || max>getLength())
  {
    cout << "待交换元素超过链表范围" << endl;
    return;
  }
  p = p->next;
  for (int i = 1; i <= max;i++)
  {
    if (i==min)
    {
      s1 = p;
    }
    if (i==max)
    {
      s2 = p;
    }
    p = p->next;
  }
  data = s1->data;
  s1->data = s2->data;
  s2->data = data;
  cout << "第" << index1 << "个元素和" << "第" << index2 << "个元素交换成功" << endl;
}
 
//打印第index个元素
void List::getData(int index)
{
  LNode *p = head;
  if (index <= 0 || index>getLength())
  {
    cout << "待查找元素不在链表中" << endl;
    return;
  }
  for (int i = 0; i < index;i++)
  {
    p = p->next;
  }
  cout << "第" << index << "元素为" << p->data << endl;
}
int main()
{
  List list;
  list.CreateList();
  list.printList();
  list.Insert(10, 2);
  list.Insert(20, 10);
  list.printList();
  list.Delete(2);
  list.printList();
  list.getData(1);
  list.getData(2);
  list.getData(3);
  list.getData(4);
  list.getData(10);
  list.exchange(1,2);
  list.printList();
  list.exchange(4, 3);
  list.printList();
  return 0;
}