2.3 线性表的链式表示和实现
2.3 线性表的链式表示和实现
从上一节看到，线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此存取表中任一元素十分简单，但插入和删除运算需要移动大量的元素。而线性表的链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此没有顺序表的弱点，但同时也失去了顺序表可随机存取的优点。
在链式存储结构中，每个存储节点不仅包含所存元素本身的信息（称之为数据域），而且包含元素之间逻辑关系的信息，即前驱节点包含后继节点的地址信息，这称为指针域，这样可以通过前驱节点的指针域方便地找到后继节点的位置，提高数据查找速度。一般地，每个节点有一个或多个这样的指针域。若一个节点中的某个指针域不需要任何节点，则它的值为空，用常量NULL表示。由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一的逻辑关系。
当进行链式存储时，一种最简单也最常用的方法是：在每个节点中除包含数据域外，只设置一个指针域，用以指向其后继节点，这样构成的链接表称为线性单向链接表，简称单链表；另一种可以采用的方法是：在每个节点中除包含数值域外，还设置了两个指针域，分别用以指向其前驱节点和后继节点，这样构成的链接表称为线性双向链接表，简称双向链表。
2.3.1 线性链表
以数组方式存放数据时，若要插入（Insert）或删除（Delete）某一节点（Node）就很困难了，如在数组中已有a、b、d、e四个元素，现将c插入数组中，并按字母顺序排列，方法就是d和e往后一格，然后将c插入；而删除一元素，也必须移动元素才不会浪费空间，有没有方法来改善这一问题呢？这就是本章所要探讨的链表（Linked List）。
利用数组的方式存放数据时，一般所配置的内存都会比实际所要的空间多，因此会造成空间的浪费，而链表就不会，因为链表是根据实际的需要配置内存的。
链表在插入与删除时都比数组简单容易，因为只要利用指针（Pointer）加以处理就可以了。但无可否认，在查找上，数组比链表来得快，因为从数组索引（Index）便可得到想要的数据（假设已知道要得到数据的数组索引）；而链表需要花费较多的时间去比较方可找到正确的数据。
假设链表中每个节点的数据结构包括两个域，分别是数据域（data）和指针域（next），若将节点结构定义为struct node类型，则表示如下：
struct node
{
int data;
struct node *next;
}
如链表A={a,b,c,d}，则其数据结构如图2-2所示。
图2-2 链表A的数据结构
其中head为指向链表前端的指针，通常此节点的data域为空。
链表中的插入与删除操作又可分为前端、尾端或是针对某一特定节点3种操作方式。
1．插入操作
（1）插入到链表的前端。
假设有一个链表B，如图2-3所示。
图2-3 链表B的数据结构图
有一节点x将插入到链表的前端，其操作步骤如下：
①x=(struct node *) malloc(sizeof(struct node))
执行完第①步后的链表示意图如图2-4所示。
图2-4 执行第①步后的链表示意图
②x->next=head->next /*（a）*/
执行完第②步后的链表示意图如图2-5所示。
图2-5 执行第②步后的链表示意图
③head->next=x /*（b）*/
执行完第③步后的链表示意图如图2-6所示。
图2-6 执行第③步后的链表示意图
（2）插入到链表的尾端。
假设有一个链表C，如图2-7所示。
图2-7 链表C的数据结构图
将一个节点x插入到链表的尾端，其操作步骤如下：
①x=(struct node *) malloc(sizeof(struct node))
执行完第①步后的链表示意图如图2-8所示。
②x->next=NULL
执行完第②步后的链表示意图如图2-9所示。
图2-8 执行第①步后的链表示意图 图2-9 执行第②步后的链表示意图
此时必须追踪此链表的尾端在什么地方，利用下列的程序段便可找到链表的尾端。
p=head->next;
while(p->next !=NULL)
p=p->next;
③p->next=x;
执行完第③步后的链表示意图如图2-10所示。
图2-10 执行第③步后的链表示意图
（3）插入到链表某一特定节点的后面。
假设有一个单向链表D，按data字段由大到小排列，如图2-11所示。
现在有一个节点ptr的data值为75，要插入到上述链表中。首先必须找到插入的位置，应为80和70之间，因此可用下述程序段执行。
图2-11 链表D的数据结构图
prev=head;
this=head->next;
while(this !=NULL && this->data > ptr->data)
{
prev=this;
this=this->next;
}
利用prev和this两个指针来跟踪，prev会紧跟在this节点之后，如图2-12所示。
图2-12 使用prev和this的链表D的数据结构图
接下来将ptr指向的节点插在prev的后面，执行后的结果如图2-13所示。
ptr->next=this; /* （a）*/
prev->next=ptr; /* （b）*/
图2-13 将ptr指向节点插在prev后面的链表D的数据结构图
2．删除操作
（1）删除链表的前端节点。
假设有一个链表E，如图2-14所示。
图2-14 链表E的数据结构图
只要执行以下几个步骤便可达到目的。
①p=head->next
执行完第①步后的链表示意图如图2-15所示。
图2-15 执行第①步后的链表示意图
②head->next=p->next
执行完第②步后的链表示意图如图2-16所示。
图2-16 执行第②步后的链表示意图
③free(p)
执行完第③步后的链表示意图如图2-17所示。
图2-17 执行第③步后的链表示意图
经由free(p)便可将p节点回收。
（2）删除链表的最后节点。
假设有一个链表F，如图2-18所示。
图2-18 链表F的数据结构图
此时必须先跟踪到尾端及尾端的前一个节点在什么地方，步骤如下。
①执行下列的程序段，得到如图2-19所示的链表F的数据结构图。
图2-19 执行第①步后的链表示意图
p=head->next；
while(p->next !=NULL)
{ /*找出尾端的前一节点prev*/
prev=p;
p=p->next;
}
②prev->next=NULL
执行完第②步后的链表示意图如图2-20所示。
图2-20 执行第②步后的链表示意图
③free(p)
执行完第③步后的链表示意图如图2-21所示。
图2-21 执行第③步后的链表示意图
（3）删除某一特定的节点。
删除某一特定的节点也必须利用两个指针prev和this，分别指到即将被删除节点（this）及前一节点（prev），因此指针prev永远跟着指针this。
假设有一个单向链表G，如图2-22所示。
图2-22 链表G的数据结构图
现在要删除"Mary"，因此将del_data变量指定为"Mary"，接下来利用下列程序段就可以将this指针指向"Mary"节点，而prev指向"John"节点。
prev=head;
this=head->next;
while(this !=NULL && strcmp(this->data,del_data)!=0)
{
prev=this;
this=this->next;
}
if(this !=NULL)
{ /*删除this节点*/
prev->next=this->next;
free(this);
}
else
printf("the data not found");
执行上面程序后的结果如图2-23所示。
图2-23 删除"mary"节点后的链表示意图
3．将两个单向链表相互连接
假设有两个链表A和B，如图2-24所示。
图2-24 链表A和B的数据结构图
将x与y链表合并为z链表，其操作步骤如下：
（1）if(x->next ==NULL) z=y;
表示当x链表为空时，直接将y链表指定给z链表。
（2）if(y->next ==NULL) z=x;
表示当y链表为空时，直接将x链表指定给z链表。
（3）z=x; c=x->next;
执行该条语句后的链表状态如图2-25所示。
图2-25 执行第（3）步后的链表示意图
（4）while(c->next !=NULL)
c=c->next;
执行该段语句后的链表状态如图2-26所示。
图2-26 执行第（4）步后的链表示意图
（5）c->next=y->next;
执行该条语句后的链表状态如图2-27所示。
图2-27 执行第（5）步后的链表示意图
4．将链表反转
链表的反转（Invert）是将原先的链表首变为链表尾，链表尾变为链表首。若有一个链表是由小到大排列的，只要将该链表反转，即可实现由大到小排列。
假设有一个链表C，如图2-28所示。
图2-28 链表C的数据结构图
经由下面几个步骤就可以完成反转的操作。
（1）p=head->next;
（2）this=NULL;
执行完第（1）、（2）步后的链表状态如图2-29所示。
图2-29 执行第（1）、（2）步后的链表示意图
（3）while(p !=NULL)
{
prev=this;
this=p;
p=p->next;
this->next=prev;
}
上述循环前3个语句中的p指针、this指针和prev指针有先后顺序。经过一次循环后，链表的状态如图2-30所示。
图2-30 执行第一次循环后的链表示意图
依此进行到p ==NULL后，循环停止，此时的链表状态如图2-31所示。
图2-31 循环停止时的链表示意图
（4）head->next=this;
利用该语句便可完成链表的反转，如图2-32所示。此操作的重点在于需要3个指针才能完成任务。
图2-32 执行第（4）步后的链表示意图
5．计算链表的长度
链表的长度即链表的节点数目，执行下面的程序段即可算出链表的长度。
p=head->next;
while( p !=NULL)
{
count ++;
p=p->next;
}
其中值得注意的是，循环的中止条件为p!=NULL，而最后的count为链表的长度。由于head节点不存放任何数据，故不予以计算。
2.3.2 循环链表
当将链表最后一个节点的指针指向head节点时，此链表称为循环链表（Circular Linked List），如图2-33所示。
图2-33 循环链表示意图
循环链表可以从任一节点来追踪所有节点。上图假设第一个节点在x1。
1．插入操作
（1）插入一个节点到循环链表前端。
有一循环链表A如图2-34所示。
利用malloc函数配置了一个节点x，如图2-35所示。
图2-34 循环链表A示意图 图2-35 x节点示意图
利用下列步骤即可将x指向的节点插入到循环链表的前端。
①x->next=head->next;
执行该条语句后的循环链表如图2-36所示。
图2-36 执行第①步后的循环链表示意图
②head->next=x;
执行该条语句后的循环链表如图2-37所示。
图2-37 执行第②步后的循环链表示意图
上述步骤①和②也适用于循环链表开始时为空的情况。
（2）插入一个节点到循环链表的尾端。
①先找到尾端：
p=head->next;
while(p->next !=head)
p=p->next;
执行该段语句后的循环链表如图2-38所示。
图2-38 执行第①步后的循环链表示意图
②p->next=x;
x->next=head;
执行该段语句后的循环链表如图2-39所示。
（3）在循环链表的某一特定节点后插入一个节点，与单向链表相似，在此不再赘述，读者可将它作为练习题进行练习。
图2-39 执行第②步后的循环链表示意图
2．删除操作
（1）删除循环链表的前端。
有一个循环链表B，如图2-40所示。
图2-40 循环链表B示意图
其操作步骤如下：
①p=head->nexr; /*（a）*/
head->next=p->next; /*（b）*/
执行该段语句后的循环链表如图2-41所示。
图2-41 执行第①步后的循环链表示意图
② free(p);
执行该条语句后的循环链表如图2-42所示。
图2-42 执行第②步后的循环链表示意图
回收p所指向的节点，此时循环链表剩下两个节点。
（2）删除循环链表的尾端。
有一个循环链表C，如图2-43所示。
图2-43 循环链表C示意图
其操作步骤如下：
①利用下列程序段找到链表的尾端及尾端的前一节点，执行完该语句后的链表如图2-44所示。
p=head->next;
while(p->next !=head)
{
prev=p;
p=p->next;
}
图2-44 执行第①步后的循环链表示意图
②prev->next=p->next; /*（a）*/
执行该条语句后的循环链表如图2-45所示。
图2-45 执行第②步后的循环链表示意图
③free(p);
执行该条语句后的循环链表如图2-46所示。
图2-46 执行第③步后的循环链表示意图
（3）删除循环链表的特定节点与单向链表相同，在此不再赘述。
3．如何回收整个循环链表
回收整个循环链表表示此链表不再需要了，因此将它归还给系统。假设有一个链表A，如图2-47所示。
图2-47 循环链表A示意图
不再需要的循环链表B，如图2-48所示。
图2-48 循环链表B示意图
只要下面3个步骤就可以回收整个循环链表。
p=head->next;
head->next=av;
av=p;
以下是回收整个单向链表的程序段。
p=head;
while(p !=NULL)
{
this=p;
p=p->next;
free(this);
}
此处的free(this)表示将它归还到系统。
4．计算循环链表的长度
计算循环链表的长度，基本上与计算单向链表的长度大同小异。读者是否可以看出其差别在哪里呢？
计算循环链表长度的程序段如下：
p=head->next;
while (p !=head)
{
count++
p=p->next;
}
2.3.3 双向链表
前几节所谈的链表都是单向链表（Single Linked List），只能单向查找链表中的节点，并且在插入或删除某一节点x时，必须先知道x的前一个节点。当将单向链表的最后一个节点的指针指到此链表的第一个节点时，此链表则称为循环链表。
双向链表中每个节点都具有3个部分：一为左链接（llink），二为数据（data），三为右链接（rlink）。其数据结构如图2-49所示。
图2-49 双向链表示意图
其中llink指向前一个节点，而rlink指向后一个节点。通常在双向链表中加上一个链表首，此链表首的数据域不存放数据，如图2-50所示。
图2-50 带链表首的双向链表示意图
双向链接具有下列两点特性：
· 假设ptr是任何节点的指针，则ptr==ptr->llink->rlink==ptr->rlink->llink。
· 若此双向链表是空的链表，则只有一个链表首。
1．插入操作
（1）插入到双向链表的前端。
假设一开始双向链表，如图2-51所示。
图2-51 双向链表初始状态
经由下列步骤就可完成将已配置的x节点插入到前端的操作。
①p=head->rlink; /*（a）*/
x->rlink=p; /*（b）*/
x->llink=head; /*（c）*/
执行该段语句后的双向链表，如图2-52所示。
图2-52 执行完第①步后的双向链表示意图
②head->rlink=x; /*（d）*/
p=llink=x; /*（e）*/
执行该段语句后的双向链表如图2-53所示。
图2-53 执行完第②步后的双向链表示意图
（2）插入到双向链表的尾端。
假设有一个双向链表A，如图2-54所示。
图2-54 双向链表A示意图
经由下列步骤就可以完成将已配置的x节点插入到尾端的操作。
①p=head->llink; /*（a）*/
执行该条语句后的双向链表A如图2-55所示。
图2-55 执行完第①步后的双向链表A示意图
②x->llink=p; /*（b）*/
x->rlink=head; /*（c）*/
该步骤是先将x的左、右link指针指向某一节点，如图2-56所示。
图2-56 执行完第②步后的双向链表示意图
③p->rlink=x; /*（d）*/
head->llink=x; /*（e）*/
该步骤是调整p的rlink字段和head的llink字段，如图2-57所示。
读者可将第②步与第③步结合起来。
图2-57 执行完第③步后的双向链表示意图
（3）插入到某一特定节点的后面。
插入到某一特定节点的后面，理论上和单向链表相似，例如有一双向链表B，如图2-58所示（由大至小排列）。
图2-58 双向链表B示意图
现要将含有75的节点插入其中，先找到适当的节点，如下列程序段所示。
prev=head;
this=head->rlink;
while(this !=head && this->score > ptr->score)
{
prev=this;
this=this->next;
}
此时this指针会指向数值为70的节点，而prev指针会指向数值为80的节点，如图2-59所示。
图2-59 找到插入节点后的双向链表示意图
接着通过执行下列4条语句即可完成插入的操作，完成后的双向链表状态如图2-60所示。
ptr->rlink=this;
ptr->llink=prev;
prev->rlink=ptr;
this->llink=ptr;
图2-60 完成插入后的双向链表示意图
2．删除操作
（1）删除双向链表的前端。
假设有一个双向链表C，如图2-61所示。
图2-61 双向链表C示意图
操作步骤如下：
①p=head->rlink; /*（a）*/
②head->rlink=p->rlink; /*（b）*/
执行第①、②步后的双向链表如图2-62所示。
图2-62 执行完第①、②步后的双向链表示意图
③p->rlink->llink=p->llink; /*（c）*/
执行该条语句后的双向链表如图2-63所示。
图2-63 执行完第③步后的双向链表示意图
④free(p);
执行该条语句后的双向链表如图2-64所示。
图2-64 执行完第④步后的双向链表示意图
（2）删除双向链表的尾端。
假设有一个双向链表D，如图2-65所示。
图2-65 双向链表D示意图
操作步骤如下：
①p=head->llink; /*（a）*/
②p->llink->rlink=p->rlink; /*（b）*/
先跟踪到尾端的节点，如图2-66所示。
图2-66 执行完第①、②步后的双向链表示意图
③head->rlink=p->llink; /*（c）*/
执行该条语句后的双向链表如图2-67所示。
图2-67 执行完第③步后的双向链表示意图
④free(p);
执行该条语句后的双向链表如图2-68所示。
图2-68 执行完第④步后的双向链表示意图
（3）删除双向链表的某一特定节点。
假设有一个双向链表C，如图2-69所示。
图2-69 双向链表示C意图
例如，删除del_dat为cd，其程序片段如下所示：
prev=head;
this=head->rlink;
while(this !=head && strcmp(this->data,del_dat) !=0)
{
prev=this;
this=this->rlink;
}
此时this指向要寻找的数据，而prev指向this的前一节点，如图2-70所示。
图2-70 找到删除节点后的双向链表示意图
if (this != head)
{
prev->rlink=this->rlink; /*（a）*/
this->rlink->llink=prev; /*（b）*/
}
else
printf("the data not found")
执行上述程序段后的双向链表如图2-71所示。
图2-71 执行上述程序段后的双向链表示意图