第1章第2节 线性表的链式表示（1）
最后更新于：2022-04-01 19:50:31
由于顺序表的插入，删除操作需要移动大量的元素，影响了运算效率，由此线性表的链式存储便应运而生。链式存储线性表时，逻辑上连续的元素物理结构上不需要连续，它们彼此可以通过“链”建立起数据元素之间的逻辑关系，因此对于线性表的插入，删除操作并不需要移动元素，只需修改指针即可。
## 一.单链表的定义
线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。
单链表结点的结构如下图所示，其中，data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。
对于每一个结点的描述如下：
~~~
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
~~~
利用单链表在解决顺序表需要大量的连续存储空间的缺点的同时，也引入了一些不可避免的缺点。比如因为需要额外的指针域，因此需要额外的存储空间；由于单链表是离散的分布在存储空间中，所以单链表不能完成随机存取的操作。
为了方便标识一个单链表，我们一般需要引入头指针来操作整个单链表。此外，为了统一增加和删除元素的操作，我们一般会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的指针域指向单链表的第一个元素结点。
注：这里应该注意区分头指针和头结点。而不管单链表有没有头结点，头指针总是指向单链表的第一个结点。简单说就是如果单链表有头结点，那么头指针将指向头结点；如果单链表没有头结点，头指针将指向单链表的第一个结点。此处我们应该注意到一般情况下头结点内不存储任何信息。这里说明下，如果后面的例题中没有具体说明，一般都是建立有头结点的单链表。
引入头节点后，可以带来两个优点：
- 由于开始节点的位置被存放在头节点的指针域中，所以在链表的第一个位置上操作与表其他位置上的操作一致，无需进行特殊处理。
- 无论链表是否为空，其头指针都是指向头节点的非空指针（在空表中，头节点的指针域为空），因此也使得空表和非空表的处理方式变得统一。
## 二.单链表基本操作的实现
### 2.1建立单链表
### 2.1.1头插法建立单链表
该方法中，首先建立一个具有头结点的空单链表，然后每生成一个读取到数据的新节点，就将其放置到头结点之后。如下图所示：
算法描述如下：
~~~
typedef int ElemType;
LinkList CreateLink(LNode *head)
{
LNode *s;
ElemType x;
scanf("%d",&x);
while(x!=999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=head->next;
head->next=s;
scanf("%d",&x);
}
return head;
}
~~~
注：采用头插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序刚好是相反的。
每个结点插入的时间复杂度为O(1)，设单链表长为n，则总的时间复杂度为O(n)。
### 2.1.2尾插法建立单链表
该方法中同样首先建立一个具有头结点的空单链表，然后每生成一个读取到数据的新节点，就将它插入到表尾；为了达到这样的目的，必须增加一个尾指针r，使其始终指向当前链表的尾结点。如下图所示
算法描述如下
~~~
LinkList CreatLink(LNode *head)
{
LNode *s;
LNode *r=head;
ElemType x;
scanf("%d",&x);
while(x!=999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
s->next=NULL;
return head;
}
~~~
注：因为附加设置了一个指向表尾的尾指针r，因此每个结点插入的时间复杂度同样为O(1)，设单链表长为n，则总的时间复杂度为O(n)。
### 2.2按序号查找结点值
从单链表的第一个结点出发，顺着指针next域逐个从上往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
算法描述如下：
~~~
LNode* GetElem(LNode *head, ElemType i)
{
LNode *p=head->next;
int j=1;
if(i==0){
printf("The Link is empty!\n");
return head;
}
if(i<=0){
printf("The postion is illegal!\n");
return NULL;
}
while(p){
if(j==i){
printf("Find success!\n");
break;
}
p=p->next;
j++;
}
return p;
}
~~~
注：按序号查找的时间复杂度为O(n)。
### 2.3按值查找结点值
从单链表的第一个结点开始，由前往后依次比较各结点数据域的值，若某结点数据域的值等于给定值x，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。
算法描述如下：
~~~
LNode* GetElem(LNode *head, ElemType x)
{
LNode *p=head->next;
if(head==NULL){
printf("The LinkList is empty!\n");
return head;
}
while(p){
if(p->data==x){
printf("Find the number!\n");
return p;
}
p=p->next;
}
printf("Not Find the number!\n");
return NULL;
}
~~~
注：按值查找的时间复杂度为O(n)。
### 2.4插入结点
### 2.4.1插入后继结点
插入操作是将值为x的新结点插入倒单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新的结点。
算法首先需要调用`GetElem(L,i-1)`查找第i−1个结点。假设返回的第i−1个结点为*p，然后令新结点*s的指针域指向*p的后继结点，再令结点*p的指针域插入新的结点*s。其操作过程如下图所示：
算法描述如下：
~~~
LNode* GetElem(LNode *head, int i)
{
if(i==0){
printf("The LinkList is empty!\n");
return head;
}
if(i<=0){
printf("The LinkList is illegal!\n");
return NULL;
}
LNode *p=head->next;
int j=1;
while(p){
if(j==i){
printf("Find it!The postion is %dth\n", j);
break;
}
j++;
p=p->next;
}
return p;
}
void InertElem(LNode *p, ElemType x){
LNode *s;
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=p->next;
p->next=s;
}
~~~
算法中，时间的主要开销是查找第i−1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
### 2.4.1插入前驱结点
在方法一中，我们可以在指针p指向的结点后面插入新的结点s，但是有时如果我们需要在指针p指向的结点前面插入新的结点s时，上述算法明显是办不到的。
但是如果我们换个思路，将指针p指向的结点和s结点它们之间的数据域做一次交换，依旧将s结点插入到指针p指向的结点后面，如此我们便将前插操作变为了向指针p指向的结点的后插操作，并且在逻辑上仍旧满足条件。
算法描述如下：
~~~
void InertElem(LNode *p, ElemType x){
LNode *s;
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
ElemType temp;
temp=p->data;
p->data=s->data;
s->data=temp;
s->next=p->next;
p->next=s;
}
~~~
注：同方法一相同，时间的主要开销是查找第i−1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
### 2.5删除结点
#### 2.5.1删除后继结点
删除结点操作即将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点（即将要被删除结点的前驱结点），然后在删除第i个结点。其操作过程如下图所示：
假设我们要删除指针q指向的结点，那么我们首先通过遍历所有结点找到指针q指向的结点的前驱结点p，为了实现算法，我们只需修改指针p的指针域，将指针p的指针域next直接指向指针q指向的结点的指针域next所指的下一个结点便可。
算法描述如下：
~~~
void DelLNode(LNode *head, int i)
{
LNode *p=head;
LNode *q=head->next;
while(i){
p=q;
q=q->next;
i--;
}
p->next=q->next;
free(q);
}
~~~
注：删除操作中，时间的主要开销是查找第i−1个元素，因此时间复杂度为O(n)。若是删除给定结点的后继结点，则时间复杂度为O(1)。
#### 2.5.2删除自身结点
有时我们需要删除指针所指向的自身结点（比如指针p指向的结点），此时如果继续使用上述方法明显是不可能的。我们采用与`2.4.1插入前驱结点`相似的方法，将指针p所指向的结点的数据域与指针q所指向的结点的数据域进行一次交换（因为是一次删除操作，我们只需要将指针q指向的结点的数据域直接赋值为指针p指向的结点的数据域便可），这样，我们就又变成了删除指针q指向的结点的操作。
算法描述如下：
~~~
void DelList(LNode *head, int i)
{
LNode *p=head;
LNode *q=p->next;
while(i){
p=q;
q=q->next;
i--;
}
p->data=q->data;
p->next=q->next;
free(q);
}
~~~
注：与上述算法一样，删除操作中，时间的主要开销是查找第i个元素，因此时间复杂度为O(n)。若是删除给定的结点，则时间复杂度为O(1)。
### 2.5求链表长度
求表长实际上就是计算单链表中数据结点（不含头节点）的个数。为了达到这个目的，我们只需对链表进行一次遍历，同时设置计数器对每次访问到的结点计数便可。
算法描述如下：
~~~
int LenLink(LNode *head)
{
int cnt=0;
LNode *p=head->next;
while(p){
p=p->next;
cnt++;
}
return cnt;
}
~~~
注：遍历操作中需要访问所有结点，因此时间复杂度为O(n)。
';