数据结构（三）链式表
线性表分为顺序存储结构和链式存储结构，顺序存储结构已经在上一篇文章中讲过，本文就来介绍链式存储结构。
1 链式存储结构（链式表）
在前面介绍过，顺序表的特点是元素之间逻辑关系上相邻，物理位置也相邻，因此可以随机存取任一元素。但是这种存储结构也存在一定的缺点，例如在插入或者删除元素时，需要移动大量的元素。为了弥补这种不足，就引入了链式存储结构的概念。
线性表的链式存储结构可以用任意存储单元（这里存储单元的物理位置可以是连续的，也可以是不连续的）来存储线性表的数据元素。
为了表示数据元素ai和其后继元素ai+1之间的逻辑关系，对ai来说需存储其本身信息和后继元素的信息（存储位置）。这两部分组成ai的存储映像，称为结点（Node），它包含两个域：数据域和指针域。n个结点链结在一起，就组成线性表的链式存储结构。
1.1 单向链表
C描述：
typedef struct Node
{
Datatype Data; /* Data field */
struct Node *Next; /* Pointer field */
}Node;
图1 单链表示意图
整个链表的存取从头指针开始，头指针表示链表中的第一个结点的存储位置；最后一个元素没有后继元素，用空指针（NULL）表示。有时会在单链表的第一个结点之前附一个结点，称之为头结点，头结点的数据域可以不存储任何信息，也可以存储诸如线性表长度等附加信息，头结点的指针域指向第一个结点的指针（即第一个元素结点的存储位置）。如果线性表为空表，则头结点的指针域指向“空”（NULL）。
单向循环链表：
图2 单向循环链表示意
单向循环链表描述方式与单向链表描述一致。
1.2 双向链表
C描述：
typedef struct DNode
{
Datatype Data; /* Data field */
struct Node *prior; /* Pointer field */
struct Node *next; /* Pointer field */
}DNode;
图3 双向链表示意
双向循环链表：
图4 双向循环链表示意
双向循环链表描述方式与双向链表描述一致。
1.3 静态链表
C描述：
#define MAXSIZE 100
typedef struct
{
Datatype Data;
int cur;
}component,SLinklist[MAXSIZE];用一堆数组来描述线性链表，这种结构称为静态链表。在上述描述的结构中，Data来表示结点数据，游标（cur）来代替指针指示结点在数组中的相对位置。
图5 静态链表示意
这种存储结构需要预先分配一个较大的空间，但在做线性表插入和删除操作时不需要移动元素，只需修改指针，所以仍具有链式存储结构的特点。
2
链表的基本算法
链表的基本算法有如下3种：
（1）定位
（2）插入
（3）删除
2.1 单向链表
2.1.1 单向链表的定位
在链表中查找（定位）第i个结点，若存在，返回地址。
算法思想：
从头结点开始，逐个查找（后移）并计数，直到第i个为止。
代码示意：
#define NULL ((void *)0)
typedef unsigned char uint8;
typedef struct Node
{
uint8 Data; /* Data field */
struct Node *Next; /* Pointer field */
}Node;
Node *LocNode(Node *head,uint8 i)
{
Node *p;
uint8 j = 0;
p = head;
while((p != NULL) && (j < i))
{
p = p -> Next;
j ++;
}
return p;
}定位算法的执行，平均查找表长的一半，算法的平均时间复杂度为T(n) = O(n)。
2.1.2 单向链表的插入
在线性表第i处插入数值为x的新结点。
算法思想：
（1）找到第i-1个结点
（2）在p结点后插入新结点q
代码示意：
void Insert(Node *head,uint8 i,uint8 x)
{
Node *p;
Node *q;
p = LocNode(head,i-1);
if(p != NULL)
{
q = (Node *)malloc(sizeof(Node));
q -> Data = x;
q -> Next = p -> Next;
p -> Next = q;
}
}2.1.3 单向链表的删除
删除第i个结点。
算法思想：
（1）找到第i-1个结点
（2）删除p的下一个结点
代码示意：
void Delete(Node *head,uint8 i)
{
Node *q; /* pointer to element to delete */
Node *p = head;
uint8 j = 0;
while((p -> Next != NULL) && (j < i - 1))
{
p = p -> Next;
j ++;
}
if((p -> Next != NULL) && (j == i - 1))
{
q = p -> Next;
p -> Next = q -> Next;
free(q);
}
else
{
/* Do nothing. */
}
}2.2 双向链表
后面算法不提供具体代码只提供伪代码指明思路，读者可以自行编写一下程序。
2.2.1 双向链表的插入
在结点p（第i个结点）之前插入新节点。
伪代码：
S = (DNode *)malloc(sizeof(DNode));
S -> Data = x; /* New element value */
S -> next = p;
S -> prior = p -> proir;
S -> prior -> next = S;
p -> prior = S;2.2.2 双向链表的删除
删除第i个结点（p结点）。
伪代码：
p -> prior -> next = p -> next;
p -> next ->prior = p -> prior;
free(p);3
链表的应用——多项式相加
图6 链表的应用
typedef struct pNode
{
uint8 coef; /* Coefficient */
uint8 expn; /* exponent */
}pointer;思想：
两个多项式逐项相加：
（1）当两个多项式均未结束时，比较指数，较小指数的结点链入新多项式链表中；
（2）若某一多项式结束，将未结束的多项式链入新链表。
腾讯云开发者
