本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第2章，第2.3节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3线性表的链式表示与实现

线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的弱点：在作插入或删除操作时，需移动大量元素。本节我们将讨论线性表的另一种表示方法——链式存储结构，其特点是用一组地址任意的存储单元存储线性表中的数据元素。由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表随机存取的特点。

2.3.1单链表

单链表是一种最简单的链式存储结构，可以看做是以“结点的序列”来表示线性表。其中，每个结点包括两个域：存放数据元素信息的域，称为数据域；存储直接后继位置的域，称为指针域。指针域中存储的信息称为指针。由于这种链表中只包含一个指针域，所以又称为单链表。线性表(a1,a2,…,ai－1,ai,ai+1,…,an)的单链表表示如图22所示。指针L指向链表的第一个结点(也称首元结点)，称作线性表的头指针。

由于单链表可由头指针唯一确定，所以在C语言中可用“结构指针”来描述。

//线性表的单链表存储结构 typedef struct LNode{ ElemTypedata;//数据域 struct LNode*next;//指针域 }LNode,*LinkList;//定义指针类型 LinkList L;//L为单链表的头指针

由于在单链表的第一个位置插入或删除结点时，需修改头指针，因此，为了使在任意位置插入或删除结点时操作统一，常在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可存储链表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。非空单链表与空表如图23所示，此时，单链表的头指针指向头结点。

头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理一致。由于头结点的重要性，本书中如不加说明，链表均指带头结点的链表。下面讨论单链表操作的实现算法。1．单链表的初始化单链表的初始化就是建立一个只有头结点的空链表。实际上就是创建一个结点，不需设置结点的数据域，将其指针域设置为空。算法描述如下：

void InitLinkList(LinkList &L){ L=new LNode; if(!L)exit(OVERFLOW); L->next=NULL; }

2．求表长设一个移动工作指针p和一个计数器j，初始时p=L->next，j=0，若p非空，则计数器加1，并将指针下移一个位置，直到到达链表尾。算法描述如下：

int LinkListLen(LinkList L){//求带头结点单链表L的长度 LNode *p; int j=0; p=L->next;//p指向第1个结点 while(p){j++;p=p->next;} //p指向第j个结点 return j; }

求单链表长度的主要操作是移动指针，将指针从头移到尾。所以，其时间复杂度为O(n)，其中n为单链表的长度。3按序号查找按序号查找是查找单链表的第i个数据元素。从单链表的第一个元素结点起，判断当前结点是否是第i个结点，若是，则返回该结点的指针；否则继续判断下一个结点，直到表结束为止。若没有找到该结点，则返回空指针。算法描述如下：

LNode *GetElem_L(LinkList L,int i){//在带头结点的单链表L中查找第i个结点,若找到则返回该结点, //否则返回空。这里假定链表非空 LNode *p; int j=1;//假定单链表非空,p指向第一个结点，j为计数器 p=L->next; while(p&&j<i){p=p->next;++j;}//顺指针向后查找,直到p指向第i个元素或p为空 if(j==i)return p;//第i个元素存在 elsereturn NULL;//第i个元素不存在 }

按序号查找的基本操作是比较j和i并移动指针，所以算法的时间复杂度为O(n)。4按值查找从单链表的第一个元素结点起，判断当前结点的值是否等于x，若是，返回该结点的指针；否则继续判断下一个结点，直到表结束为止。若没有找到则返回空指针。算法描述如下：

LNode *locateelem(LinkList L,ElemType x){ LNode *p; p=L->next; while(p&&p->data!=x)p=p->next; if(p&&p->data==x)return p; else return NULL; }``` 5插入操作 假设单链表为(a1,a2,…,ai－1,ai,ai+1,…,an)，则在第i个位置之前插入元素x后变为 (a1,a2,…,ai－1,x,ai,ai+1,…,an) 要想实现上述操作，首先要找到第i-1个结点，然后修改结点x和ai－1的指针域即可，如图24所示。但要注意修改的顺序，否则会造成链表断链。算法描述如下：  int LinkListInsert_L(LinkList &L,int i,ElemType x){//在单链表L中第i个位置之前插入元素x LNode *p,*s; p=GetElem_L(L,i-1); if(!p)return ERROR; s=new LNode //生成新结点 if(!p)return ERROR;s->data=x; s->next=p->next; //插入L中 p->next=s; return OK; } 由于上述算法的主要操作是查找第i-1个结点，所以算法的时间复杂度仍为O(n)。 6删除操作 假设单链表为(a1,a2,…,ai－1,ai,ai+1,…,an)，则删除第i个结点后变为 (a1,a2,…,ai－1,ai+1,…,an) 要想实现上述操作，首先要找到第i-1个结点，然后修改结点ai－1的指针域并释放结点ai即可，如图25所示。算法描述如下：  int LinkListDelete_L(LinkList &L,int i){ LNode *p,*q; p=GetElem_L(L,i-1); if(!p)return ERROR;//删除位置不合理 q=p->next; p->next=q->next;//删除并释放结点 deleteq; return OK; } 由于上述算法的主要操作是查找第i-1个结点，所以算法的时间复杂度仍为O(n)。 7将单链表L置空 将单链表L置空就是将单链表的所有结点所占空间释放掉。算法描述如下： void ClearLinkList(LinkList &L){ LNode *p; while(L->next){ p=L->next; L->next=p->next; delete p; } } 8单链表的建立 (1)头插法 单链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。头插法的操作步骤是：1)建立一个“空表”；2)建立新增结点；3)将新增结点插入在头结点和第一个结点之间；4)重复步骤2和步骤3直至结束。由于后插入的结点在单链表的头部，所以读入的数据与线性表的逻辑顺序是相反的。算法描述如下： void CreateLinkList(LinkList &L,int n) {//逆序输入n个数据元素,建立带头结点的单链表 LNode *p; InitLinkList(L);//建立空表 for(int i=n;i>0;--i){ p=new LNode;//新增结点 scanf(("%d",&p->data);//输入元素值 p->next=L->next; L->next=p;//插入到表头 } } (2)尾插法 尾插法与头插法不同的是：新增结点插入在单链表的尾部，因此要设置一个工作指针r，让r始终指向单链表的最后一个结点。采用尾插法建立单链表时，读入的数据与线性表的逻辑顺序是相同的。算法描述如下： void CreateLinkList (LinkList &L,int n){ LNode *p,*r; InitLinkList(L);//建立空表 r=L;// r始终指向表尾结点 for(int i=1;i<=n;i++){ p=new LNode; scanf("%d",&p->data);//输入元素值 r->next=p;//插入到表尾 r=p; } r->next=NULL; } 9输出单链表L的元素 将单链表L中的元素依次输出。算法描述如下： void DispLinkList(LinkList L) { LNode *p; for(p=L->next;p;p=p->next)printf("%d",p->data); printf("\\\\n"); } ####2.3.2双向链表 单链表的结点中只有一个指向直接后继的指针域，从某个结点出发只能顺指针往后寻找其他结点。若要寻找结点的直接前驱，则需从表头指针出发。换句话说，在单链表中，NextElem的时间复杂度为O(1)，而PriorElem的时间复杂度为O(n)。为了克服单链表的这种单向性的缺点，可以利用双向链表。在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，如图26所示。  在C语言中可描述如下：

//线性表的双向链表存储结构typedef struct DuLNode {ElemTypedata;//数据域struct DuLNode*prior;//指向前驱的指针域struct DuLNode*next;//指向后继的指针域}DuLNode,*DuLinkList;

双向链表的操作特点是：“初始化”、“插入”、“删除”、“建立”时需要同时修改两个方向上的指针，其他操作和单链表基本相同。双向链表各种操作的实现可以依照单链表相应操作来完成，只是注意需要修改两个指针即可。下面给出双向链表主要操作的实现算法。 1．双向链表的初始化 双向链表的初始化就是建立一个只有头结点的空链表。与单链表初始化不同的是，双向链表同时将其两个指针域设置为空。算法描述如下： void InitDuLinkList(DuLinkList &L){ L=new DuLNode; if(!L)exit(OVERFLOW); L->next=L->prior=NULL; } 2按序号查找 按序号查找是查找双向链表的第i个数据元素。其操作与单链表的相应操作完全相同，即从双向链表的第一个元素结点起，判断当前结点是否是第i个结点，若是，则返回该结点的指针；否则继续判断下一个结点，直到表结束为止。若没有找到该结点则返回空指针。算法描述如下： DuLNode *GetElem_L(DuLinkList L,int i){//在带头结点的双向链表L中查找第i个结点， //找到则返回该结点，否则返回空 DuLNode *p; p=L->next; int j=1;//p指向第一个结点，j为计数器 while(p!=NULL&&j<i){//顺指针向后查找，直到p指向第i个元素或p为空 p=p->next; ++j; } if(j==i)return p;//第i个元素存在 else return NULL;//第i个元素不存在 } 3插入操作 假设双向链表为(a1,a2,…,ai－1,ai,ai+1,…,an)，则在第i个位置之前插入元素x后变为 (a1,a2,…,ai－1,x,ai,ai+1,…,an) 要想实现上述操作，首先要找到第i-1个结点，然后修改结点x和ai－1的指针域即可，如图27所示。但要注意修改的顺序，否则会造成链表断链。这里需要注意的是：当元素插到双向链表尾部与插到其他位置时的操作有所不同。算法描述如下： int DuLinkListInsert(DuLinkList &L,int i,ElemType x){//在双向链表L中第i个位置之前插入元素x DuLNode *p,*s; p=GetElem_L(L,i-1); if(!p)return ERROR; s=new DuLNode;//生成新结点 s->data=x; if(p->next){//插在L尾部位置之外的任何位置 p->next->prior=s; s->next=p->next; s->prior=p; p->next=s; } else{//插在L尾部的处理 s->next=p->next; p->next=s; s->prior=p; } return OK; }  4删除操作 假设双向链表为(a1,a2,…,ai－1,ai,ai+1,…,an)，则删除第i个结点后变为 (a1,a2,…,ai－1,ai+1,…,an) 要想实现上述操作，首先要找到第i-1个结点，然后修改结点ai－1的指针域并释放结点ai即可，如图28所示。需要注意的是：删除尾部结点与删除其他位置的结点的操作有所不同。算法描述如下： int DuLinkListDelete(DuLinkList &L,int i){ DuLNode *p,*q; p=GetElem_L(L,i-1); if(!p)return ERROR;//删除位置不合理 if(p->next->next){ q=p->next; q->next->prior=p; p->next=q->next;//删除并释放结点 } else{//删除尾部结点 q=p->next; p->next=NULL; } delete q; return OK; }  5双向链表的建立 双向链表的建立与单链表的建立算法相同，描述如下： void CreateDuLinkList(DuLinkList &L,int n) {//逆序输入n个数据元素，建立带头结点的双向链表 DuLNode *p; InitDuLinkList(L);//建立空表 for(int i=n;i>0;--i){ p=new DuLNode;//新增结点 scanf("%d",&p->data);//输入元素值 if(L->next)L->next->prior=p; p->next=L->next; p->prior=L; L->next=p; } } ####2.3.3循环链表 1．单循环链表 单循环链表是指最后一个结点指针域的指针又指回到头结点的链表。其结点结构与单链表相同。为了与单链表区分，将其类型描述为CirLinkList。带头结点的单循环链表如图29所示。它和单链表的差别仅在于，前者判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。单循环链表往往只设尾指针。  单循环链表与单链表的唯一区别在于：单循环链表最后一个结点的指针指向头结点，而单链表最后一个结点的指针为空。所以，单循环链表相关操作的实现几乎与单链表的相应操作完全相同，只是注意最后一个结点的指针要指向头结点。例如，单循环链表的初始化算法为 int InitCirLinkList(CirLinkList &L){ L=new LNode; if(!L)exit(OVERFLOW); L->next=L; return OK; } 单循环链表的建立算法为 void CreateList_L(CirLinkList &L,int n) {// 逆序输入 n 个元素，建立带头结点的单循环链表 L=new CLNode;L->next=L;// 先建立一个带头结点的空单循环链表 for(i=n;i>0;--i){ p=new CLNode; scanf(&p->data);// 输入元素值 p->next=L->next;L->next=p;//插入 } } 例1编写一个将单循环链表逆置的算法。 解设置一个工作指针p，初始指向单循环链表L的第一个结点，将L的next域指向L，即建立一个空单循环链表，然后采用头插法依次将所有结点插入到单循环链表L中。算法如下： int ContrayCirLinkList(CirLinkList &L){//头插法建立 LNode *p,*q; p=L->next; L->next=L;//建立空单循环链表 while(p!=L){ q=p; p=p->next; q->next=L->next; L->next=q; } return OK; } 例2已知有两个带头结点的循环单链表，设计一个算法，用最快速度将这两个表合成一个带头结点的循环单链表。要求时间复杂度为O(1)，且占用辅助空间最小。 解根据题目条件的要求，显然只有设尾指针的单循环链表才能实现。算法如下： void UnionCirLinkList(CirLinkList &La,CirLinkList &Lb){//La和Lb是两个带头结点的单循环链表的尾 //指针，本方法将Lb接在La后成为一个单循环链表 LNode *q; q=Lb->next;// q指向Lb的头结点 Lb->next=La->next;//Lb的后继结点为La的头结点 La->next=q->next;//La的后继结点为原Lb的第一个元素结点 delete q;//释放原Lb的头结点 } 2．双向循环链表 双向循环链表结点结构与双向链表相同，为了与双向链表区分，将其类型描述为CirDuLinkList。双向循环链表与双向链表的操作基本相同，只是在实现相应操作时，要注意修改头结点的prior域和尾结点的next域的值。下面给出双向循环链表的初始化、建立、插入和删除操作的算法。 (1)双向循环链表的初始化 void InitCirDuLinkList(CirDuLinkList &L){ L=new DuLNode; if(!L)exit(OVERFLOW); L->next=L->prior=L; } (2)双向循环链表的建立 void CreateCirDuLinkList (CirDuLinkList &L,int n) {//逆序输入n个数据元素，建立带头结点的双向循环链表 DuLNode *p; int i; InitCirDuLinkList(L);//建立空表 for(i=n;i>0;--i){ p=new DuLNode;//新增结点 scanf("%d",&p->data);//输入元素值 L->next->prior=p； P->next=L→next; p->prior=L; L→next=p; } } (3)在双向循环链表的第i个位置之前插入元素e int CirDuLinkListInsert(CirDuLinkList &L,int i,ElemType x){//在双向循环链表L中第i个位 //置之前插入元素x DuLNode *p,*s; p=GetElem_L(L,i-1); if(!p)return ERROR; s=new DuLNode;//生成新结点 s->data=x; p->next->prior=s; s->next=p->next; s->prior=p; p->next=s; return OK; } (4)删除双向循环链表的第i个元素 int CirDuLinkDelete(CirDuLinkList &L,int i){ DuLNode *p,*q; p=GetElem_L(L,i-1); if(!p)return ERROR;//删除位置不合理 q=p->next; q->next->prior=p; p->next=q->next;//删除并释放结点 delete q; return OK; } ####2.3.4静态链表 有些高级语言没有指针类型，如Fortran和Java，这时可用数组来表示和实现链表。其类型说明如下：

//线性表的静态单链表存储结构

define Maxsize 1000//链表的最大长度

typedef struct{ ElemType data;int cur; //游标，相当于指针}component，SLinkList［Maxsize］;

在如上所述的链表中，数组的每个分量表示一个结点，同时用游标代替指针指示结点在数组中的相对位置。数组的下标为零的分量可看成备用链表L的头结点，其指针域指示备用链表中第一个可用结点。数组的下标为1的分量可看成链表S的头结点，其指针域指示链表中第一个结点。含四个元素a、b、c、d的静态链表S如图210a所示。在S的第4个元素之前插入f，结果如图210b所示。再删去第2个元素，结果如图210c所示。  下面给出静态链表的各种操作的算法。 (1)备用链表的初始化 void InitSL(SLinkList L){//将L中的各分量连成一个备用链表，L［0］.cur指向备用链表的头指针，0表 //示空指针 int i; for(i=0;i<maxsize-1;++i)L［i］.cur=i+1; L［maxsize-1］.cur=0; } (2)实现函数new的功能 int SLnew(SLinkList &L){//备用链表非空，则返回分配的结点下标，否则返回0 int i; i=L［0］.cur; if(L［0］.cur)L［0］.cur=L［i］.cur; return i; } (3)实现函数delete的功能 void SLdelete(SLinkList &L,int k){//将下标为k的空闲结点回收到备用链表 L［k］.cur=L［0］.cur; L［0］.cur=k; } (4)在静态链表中查找元素e int locateelem(SLinkList L,ElemType e){//在静态链表中查找第一个结点为e的元素，若找到则返回它 //在链表中的位序，否则返回0 int j; j=L［1］.cur;//指向链表的第一个结点 while(j!=0&&L［j］.data!=e)j=L［j］.cur; return j; } (5)建立静态链表 void CreateSL(SLinkList &L,int n){ int p;//指向静态链表尾结点 p=SLnew(L);//生成静态链表头结点 for(int i=1;i<=n;i++){ p=SLnew(L); scanf("%d",&L［p］.data);//输入元素值 } L［p］.cur=0; } (6)输出静态链表 void DispSL(SLinkList L) { int p; for(p=L［1］.cur;p;p=L［p］.cur)printf("%d ",L［p］.data); printf("\\\\n"); } 例3依次输入A和B的元素，在L中建立表示集合(A-B)∪(B-A)的静态链表，S为其头指针。假设备用空间足够大，L［0］.cur为其头结点。 解代码如下： void difference(SLinkList &L,int &s){ int r,m,n,i,j,p,k,b; InitSL(L);//初始化备用空间 s=SLnew(L);//生成静态链表S的头结点 r=s;//r指向S的当前最后一个结点 scanf("%d%d",&m,&n);//输入A和B的元素个数 for(j=1;j<=m;++j){//建立集合A的链表 i=SLnew(L);//分配结点 scanf("%d",&L［i］.data);//输入A的元素值 L［r］.cur=i;//插入到表尾 r=i;//r始终指向表的最后一个结点 } L［r］.cur=0;//表尾结点的指针为空 for(j=1;j<=n;++j){//依次输入B的元素，若该元素不在当前表中，则将其插入，否则将其删除 scanf("%d",&b); p=s; k=L［s］.cur;//k指向S中的第一个结点 while(k!=L［r］.cur&&L［k］.data!=b){//在当前表中查找 p=k; k=L［k］.cur; } if(k==L［r］.cur){//当前表中不存在该元素，将其插入在r所指结点之后，且r的位置不变 i=SLnew(L); L［i］.data=b; L［i］.cur=L［r］.cur; L［r］.cur=i; } else{ L［p］.cur=L［k］.cur; SLdelete(L,k); if(r==k)r=p; }//该元素已在表中，删除之。若删除的是表尾元素，则需修改指针r } } 235链表的应用举例 例4将两个有序表La和Lb归并成一个有序表，要求不另设新空间。 解由于题目要求不另设新空间，所以生成的新链表要使用原来链表的空间。算法如下： void mergelist(LinkList &La,LinkList &Lb,LinkList &Lc){//将两个有序表并为一个有序表，要求不 //另设新表空间 LinkList pa,pb,pc; pa=La->next;pb=Lb->next; Lc=pc=La; while(pa&&pb){ if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb;pc=pb;pb=pb->next;} } if(!pa)pc->next=pb; if(!pb)pc->next=pa; delete Lb; } 例5一元稀疏多项式相加。 解链表的存储结构如下： typedef struct{ float coef;//系数 int expn;//指数 }term，ElemType; typedef struct Lnode{ Elemtype data; struct Lnode *next; }Lnode,*LinkList; 对于两个一元多项式中所有指数相同的项，将对应系数相加。若其和不为0，则构成“和多项式”中的一项；对两个一元多项式中指数不同的项，则分别复抄到“和多项式”中。 void addlist(LinkList &La,LinkList &Lb){ //pa=pa+pb，La和Lb分别是多项式pa和pb的链表 pa=La->next; pb=Lb->next; pc=La;//指向链表当前的尾结点 while(pa&&pb){ if(pa->data.expn<pb->data.expn){ pc->next=pa; pc=pa; pa=pa->next; } else if(pa->data.expn>pb->data.expn){ pc->next=pb; pc=pb; pb=pb->next; } else{ sum=pa->data.coef+pb->data.coef; if(sum==00){ p=pa;pa=pa->next;delete p; p=pb;pb=pb->next;delete p; } else{ pa->data.coef=sum;pc->next=pa;pc=pa; pa=pa->next;p=pb;pb=pb->next;delete p; } } } if(pa)pc->next=pa； if(pb)pc->next=pb; delete Lb;//释放Lb的头指针 } 例6设L是带头结点的单链表的头指针，试编写算法，按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。要求不允许使用数组作为辅助空间。 解按照题目要求，应对链表进行遍历，在每次遍历中查找出整个链表的最小元素，输出并释放所占空间；再次查找最小元素，输出并释放空间；如此进行下去，直至链表为空，最后释放头结点的存储空间。当然，删除结点时一定要记住该结点的前驱结点的指针。算法如下： void deleteMin(LinkList &L){//L为单链表的头指针，递增输出链表的各元素并释放所有结点所占空间 LNode *pre,*p,*q; while(L->next){ pre=L;//pre为元素值最小结点的前驱结点的指针 p=L->next;//p为工作指针 while(p->next) if(p->next->data<pre->next->data){//记住当前元素值最小结点的前驱 pre=p;p=p->next; } else p=p->next; printf("%d",pre->next->data);//输出元素值最小结点的数据 q=pre->next; pre->next=q->next; delete(q);//删除元素值最小的结点 } delete(L);//释放头结点 } 例7有一个双向链表从第二个结点至表尾递增有序。试编写算法，将第一个结点删除并插入到适当位置，使整个链表递增有序。 解由已知条件，需要将双向链表的第一个结点从链表中摘下来，再将其插入到链表中的相应位置。由于是双向链表，所以不必像单链表中那样必须知道插入结点的前驱。算法如下： void insetnode(DuLinkList &L){//L为双向链表的头指针，第二个结点至表尾递增有序，将第一个结点删除 //并插入到适当位置，使整个链表仍然递增有序 DuLNode *p,*q,*r; p=L->next;L->next=p->next;p->next->prior=L;//将链表的第一个结点摘下 q=L->next;//q为工作指针 r=L;//r指向q的前驱 while(q&&q->data<p->data){//查找p应插入的位置 r=q; q=q->next; } if(q){ q->prior->next=p; p->prior=q->prior; p->next=q; q->prior=p; } else{//插在尾部 p->next=r->next; r->next=q; p->prior=r; } 相关资源：数据结构（C语言版）第二版