C++实现链表

C++实现链表

众所周知，C/C++语言实现的链表是由一个一个的结点构成，每个结点分为数据域和指针域，指针域中存储了其后继结点的地址，通过地址来访问下一个结点。

链表是一系列节点串联形成的数据结构，链表存储有序的元素集合，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的部分和一个指向下一个元素的链接部分组成。因此链表增删非首尾元素时不需要移动元素，只需要更改链接部分的值即可。

本文仅以单链表为例介绍。

单链表每个节点的结构如下：

单链表只有一个指向其他节点的变量，也就是在这种类型的数据结构中，任何两个数据元素之间只有一个链接，参见下图：

链表的操作包括了创建、删除、插入、输出等。

创建就是空间的分配，将头、尾指针及链表结点个数等初始化。删除和插入根据被操作元素的位置可以细分为头删除（插入），尾删除（插入），中间删除（插入）。

插入操作

头插入实际上是增加一个新节点，然后把新增加的结点指针指向原来头指针指向的元素，再把头指针指向新增的节点。

尾插入也是增加一个新节点，该节点指针置为null，然后把原尾结点指针指向新增加的节点，最后把尾指针指向新增加的节点即可。

中间插入稍复杂，首先增加一个节点，然后新增节点的指针指向插入位置的后一个节点，把插入位置的前一个节点指针指向新插入节点即可。

删除操作

删除头元素时，先将头指针指向下一个节点，然后把原头结点的指针置空即可。

删除尾元素时，首先找到链表倒数第2个元素，然后把尾指针指向这个元素，接着把原倒数第2个元素的指针置空。

删除中间元素相对复杂一些，首先将要删除的节点的前一个节点指针指向要删除的节点的下一个节点，然后把要删除节点的指针置空。

上面提到是单链表最基本的操作，除此之外还有其它操作不多说了。下面给出代码示例。本文介绍两种实现方法：一、使用指针自定义实现；二、使用C++ STL（标准模板库）中的list容器实现。

一、使用指针自定义实现

先看一个简单点的示例源码：

// 插入
// 将x插入到以head为头节点的pos位置上 
void insert(node* head, int pos, int x){node *p=head;for(int i=0;i<pos-1;i++){//比如要插到第三个位置，从0开始的话就是下标为2，前一个下标为1 p=p->next;// 1 < 3-1 }node* q=new node;q->data=x;q->next=p->next;p->next=q;
} //删除 
//删除所有值为x的数 
void del(node* head, int x){node* p= head->next;node* pre=head;while(p!=NULL){if(p->data==x){pre->next=p->next;delete(p);p=pre->next;}else{pre=p;p=p->next;}} 
}//查找 
//查找链表中有几个x，返回count值 
int search(node *head, int x){int count=0;node *p=head->next;while(p!=NULL){if(p->data==x){count++;}p=p->next; } return count;
} //排序
//冒泡排序
void sort(node *head){for(node *temp=head->next;temp->next!=NULL;temp=temp->next){for(node *p=head->next;p->next!=NULL;p=p->next){if(p->data > p->next->data){int t=p->data;p->data=p->next->data;p->next->data=t;}}}
} int main(){int array[5]={6,3,9,1,2};node* L=create(array);	//返回头节点L //insert(L, 3, 8);  //插入后结果为6,3,8,9,1，2 //del(L, 9); //删除后结果为6,3,1,2 int y=9; int x=search(L, y);cout<<"查找到"<< x <<"个"<<y<<endl;//sort(L);  //排序 //遍历打印 L=L->next;	//头节点L是没有数据域的，下个结点才有 while(L != NULL){cout<<L->data<<" ";L=L->next;} return 0;
}

运行输出：

再给出一个较完善的示例，源码如下：

// 单链表.cpp: #include<iostream>
using namespace std;typedef int DataType;
#define Node ElemType//构建一个节点类
class Node						  
{
public:int data;     //数据域Node * next;  //指针域
};//构建一个单链表类
class LinkList					  
{
public:LinkList();					  //构建一个单链表;~LinkList();                  //销毁一个单链表;void CreateLinkList(int n);   //创建一个单链表void TravalLinkList();        //遍历线性表int GetLength();              //获取线性表长度bool IsEmpty();               //判断单链表是否为空ElemType * Find(DataType data); //查找节点void InsertElemAtEnd(DataType data);            //在尾部插入指定的元素void InsertElemAtIndex(DataType data,int n);    //在指定位置插入指定元素void InsertElemAtHead(DataType data);           //在头部插入指定元素void DeleteElemAtEnd();       //在尾部删除元素void DeleteAll();             //删除所有数据void DeleteElemAtPoint(DataType data);     //删除指定的数据void DeleteElemAtHead();      //在头部删除节点
private:ElemType * head;              //头结点
};//初始化单链表
LinkList::LinkList()                  
{head = new ElemType;            head->data = 0;               //将头结点的数据域定义为0head->next = NULL;            //头结点的下一个定义为NULL
}     //销毁单链表
LinkList::~LinkList()
{delete head;                 //删除头结点
} //创建一个单链表
void LinkList::CreateLinkList(int n)
{ElemType *pnew, *ptemp;ptemp = head;if (n < 0) {       //当输入的值有误时，处理异常cout << "输入的节点个数有误" << endl;		}for (int i = 0; i < n;i++) {        //将值一个一个插入单链表中pnew = new ElemType;cout << "请输入第" << i + 1 << "个值: " ;cin >> pnew->data;pnew->next = NULL;          //新节点的下一个地址为NULLptemp->next = pnew;         //当前结点的下一个地址设为新节点ptemp = pnew;               //将当前结点设为新节点}
}//遍历单链表
void LinkList::TravalLinkList()
{if (head == NULL || head->next ==NULL) {cout << "链表为空表" << endl;}ElemType *p = head;                 //另指针指向头结点while (p->next != NULL)        //当指针的下一个地址不为空时，循环输出p的数据域{p = p->next;               //p指向p的下一个地址cout << p->data << " ";}
}//获取单链表的长度
int LinkList::GetLength()
{int count = 0;                  //定义count计数ElemType *p = head->next;           //定义p指向头结点while (p != NULL)                //当指针的下一个地址不为空时，count+1{count++;                  p = p->next;                //p指向p的下一个地址}return count;                   //返回count的数据
}//判断单链表是否为空
bool LinkList::IsEmpty()
{if (head->next == NULL) {                 return true;}return false;
}//查找节点
ElemType * LinkList::Find(DataType data)
{ElemType * p = head;if (p == NULL) {                           //当为空表时，报异常cout << "此链表为空链表" << endl;return NULL;}else{while (p->next != NULL)               //循环每一个节点{if (p->data == data) {return p;                     //返回指针域}p = p->next;}if (p->data == data) { return p; }return NULL;                           //未查询到结果}
}//在尾部插入指定的元素
void LinkList::InsertElemAtEnd(DataType data)
{ElemType * newNode = new ElemType;    //定义一个Node结点指针newNodenewNode->next = NULL;         //定义newNode的数据域和指针域newNode->data = data;ElemType * p = head;              //定义指针p指向头结点if (head == NULL) {           //当头结点为空时，设置newNode为头结点head = newNode;}else                          //循环知道最后一个节点，将newNode放置在最后{while (p->next != NULL){p = p->next;}p->next = newNode;}
}//在指定位置插入指定元素
void LinkList::InsertElemAtIndex(DataType data,int n)
{if (n<1 || n>GetLength())                   //输入有误报异常cout << "输入的值错误" << endl;else{ElemType * ptemp = new ElemType;        //创建一个新的节点ptemp->data = data;                     //定义数据域ElemType * p = head;                    //创建一个指针指向头结点int i = 1;while (n > i)                           //遍历到指定的位置{p = p->next;i++;}ptemp->next = p->next;                 //将新节点插入到指定位置p->next = ptemp;}
}//在头部插入指定元素
void LinkList::InsertElemAtHead(DataType data)
{ElemType * newNode = new ElemType;    //定义一个Node结点指针newNodenewNode->data = data;ElemType * p = head;              //定义指针p指向头结点if (head == NULL) {           //当头结点为空时，设置newNode为头结点head = newNode;}newNode->next = p->next;          //将新节点插入到指定位置p->next = newNode;
}//在尾部删除元素
void LinkList::DeleteElemAtEnd()
{ElemType * p = head;          //创建一个指针指向头结点ElemType * ptemp = NULL;      //创建一个占位节点if (p->next == NULL) {        //判断链表是否为空cout << "单链表空" << endl;}else{while (p->next != NULL)   //循环到尾部的前一个{ptemp = p;            //将ptemp指向尾部的前一个节点p = p->next;          //p指向最后一个节点}delete p;                //删除尾部节点p = NULL;ptemp->next = NULL;}
}//删除所有数据
void LinkList::DeleteAll()
{ElemType * p = head->next;ElemType * ptemp = new ElemType;while (p != NULL)                    //在头结点的下一个节点逐个删除节点{ptemp = p;p = p->next;head->next = p;ptemp->next = NULL;delete ptemp;}head->next = NULL;                 //头结点的下一个节点指向NULL
}//删除指定的数据
void LinkList::DeleteElemAtPoint(DataType data)
{ElemType * ptemp = Find(data);    //查找到指定数据的节点位置if (ptemp == head->next) {        //判断是不是头结点的下一个节点，如果是就从头部删了它DeleteElemAtHead();}else{ElemType * p = head;          //p指向头结点while (p->next != ptemp)      //p循环到指定位置的前一个节点{p = p->next;}p->next = ptemp->next;         //删除指定位置的节点delete ptemp;ptemp = NULL;               }}//在头部删除节点
void LinkList::DeleteElemAtHead()
{ElemType * p = head;if (p == NULL || p->next == NULL) {   //判断是否为空表，报异常cout << "该链表为空表" << endl;}else{ElemType * ptemp = NULL;      //创建一个占位节点p = p->next;ptemp = p->next;              //将头结点的下下个节点指向占位节点delete p;                     //删除头结点的下一个节点p = NULL;head->next = ptemp;           //头结点的指针更换}
}//测试函数
int main()
{LinkList l;int i;cout << "1.创建单链表(整数类型数据)   2.遍历单链表   3.获取单链表的长度   4.判断单链表是否为空 \n";cout << "5.获取节点   6.在尾部插入指定元素   7.在指定位置插入指定元素   8.在头部插入指定元素\n";cout << "9.在尾部删除元素   10.删除所有元素   11.删除指定元素   12.在头部删除元素   0.退出" << endl;cout << " --------  "<< endl;do{cout << "请输入要执行的操作: ";cin >> i;switch (i){case 1:int n;cout << "请输入单链表的长度: ";cin >> n;l.CreateLinkList(n);break;case 2:l.TravalLinkList();break;case 3:cout << "该单链表的长度为" << l.GetLength() << endl;break;case 4:if (l.IsEmpty() == 1)cout << "该单链表是空表" << endl;else{cout << "该单链表不是空表" << endl;}break;case 5:DataType data;cout << "请输入要获取节点的值: ";cin >> data;cout << "该节点的值为" << l.Find(data)->data << endl;break;case 6:DataType endData;cout << "请输入要在尾部插入的值: ";cin >> endData;l.InsertElemAtEnd(endData);break;case 7:DataType pointData;int index;cout << "请输入要插入的数据: ";cin >> pointData;cout << "请输入要插入数据的位置: ";cin >> index;l.InsertElemAtIndex(pointData, index);break;case 8:DataType headData;cout << "请输入要在头部插入的值: ";cin >> headData;l.InsertElemAtHead(headData);break;case 9:l.DeleteElemAtEnd();break;case 10:l.DeleteAll();break;case 11:DataType pointDeleteData;cout << "请输入要删除的数据: ";cin >> pointDeleteData;l.DeleteElemAtPoint(pointDeleteData);break;case 12:l.DeleteElemAtHead();break;default:break;}}while (i != 0);system("pause");return 0;
}

 运行结果：

二、使用C++ STL（标准模板库）中的list容器实现

C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。

std::list_C++中文网

要用list容器必须声明请头文件：#include <list>。

Dev C++ 5.11及其之前的版本默认是不支持c++11新标准的，解决方案也很简单，在菜单栏点开Tools -> Compile Options，添加编译指令-std=c++11即可，参见下图：

下面给出示例源码：

#include <iostream>
#include <list>
using namespace std;
int main(){list<int> l;cout<<"list的大小:"<<l.size()<<endl;//list的大小:0for (int i=0; i<10; i++)l.push_back(i); //尾部插入元素 尾插法cout<<"list的大小:"<<l.size()<<endl;//list的大小:10list<int>::iterator it = l.begin();while(it!=l.end()){cout<<*it<<" ";it++;}cout << endl;//0 1 2 3 4 5 6 7 8 9//list不能随机访问容器中的值，即不能it+5这样的操作。只能一个一个的走，即it++it=l.begin();it++;it++;it++;l.insert(it, 100); //100插入在链表第4个位置for (list<int>::iterator it = l.begin(); it != l.end(); it++)cout<<*it<<" ";cout<<endl;//0 1 2 100 3 4 5 6 7 8 9l.clear(); cout<<"list的大小:"<<l.size()<<endl;//list的大小:0for (int i=0; i<10; i++)l.push_front(i); 		//尾部插入元素 尾插法cout<<"list的大小:"<<l.size()<<endl;//list的大小:10for(list<int>::iterator it=l.begin(); it!=l.end(); it++)cout<<*it<<" ";cout<<endl;        //9 8 7 6 5 4 3 2 1 0list<int>::iterator it1 = l.begin();list<int>::iterator it2 = l.begin();it2++;it2++;it2++;//要想删除一个区间段。只能用指针++一步一步的指向那个末尾位置，不能直接l.begin()+3l.erase(it1, it2);		//删掉的是区间[it1,it2) for (list<int>::iterator it=l.begin(); it!=l.end(); it++)cout<<*it<<" ";cout<<endl;//6 5 4 3 2 1 0l.insert(l.begin(), 100);l.insert(l.begin(), 100);l.insert(l.begin(), 100);l.erase(l.begin()); 		//删除该位置的元素for (list<int>::iterator it=l.begin(); it!=l.end(); it++)cout<<*it<<" ";cout<<endl;//100 100 6 5 4 3 2 1 0cout<<"链表中的第一个元素："<<l.front()<<endl; //链表中的第一个元素：100cout<<"链表中的最后一个元素："<<l.back()<<endl; //链表中的最后一个元素：0l.remove(100);				//移除所有100元素的值  removefor (list<int>::iterator it=l.begin(); it!=l.end(); it++)cout<<*it<<" ";cout<<endl;//6 5 4 3 2 1 0
}

运行之：