数据结构与算法 －线性表链式存储及其相关算法
数据结构与算法 －线性表链式存储及其相关算法
用链接方式存储的线性表简称为链表。
链表的具体存储用一组任意的存储单元来存放，链表中结点的逻辑次序和物理次序不一定相同，还必须存储指示其后继结点的地址信息。
线性表链式存储（单链表）
单链表的结点分为 data 域和 next 域，data域用于存放结点值的数据，next域用于存放结点的直接后继地址的指针域。所有结点通过指针链接而组成单链表。 Head称为头指针变量，存放链表中第一个结点地址。NULL称为空指针，一般为最后一个节点的next指针域。
我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，单链表就可以表示为下图形式。
单链表中第一个结点内一般不存数据，称为 头结点，利用头指针存放该结点地址从而方便运算的实现。
以下是单链表节点类型的定义。
// 单链表的类型定义
typedef struct node{
// 数据域
DataType data;
// 指针域,用于存放结点的直接后继结点的地址
struct node * next;
}Node，*LinkList;通过对单链表节点的认识，我们总结一下单链表的特点：
1. 起始节点又称为首结点，无前驱，故设头指针head 指向开始结点 ；
2. 链表由头指针唯一确定，单链表可以用头指针的名字来命名，头指针名是head的链表可称为表head ；
3. 终端结点又称尾结点，无后继，故终端结点的指针域为空，即NULL ；
4. 除头结点之外的结点为表结点 ；
5. 为运算操作方便，头结点中不存数据。
线性表链式存储（单链表）的运算
1. 初始化
建立一个空的单链表L，InitiateLinkList（L） ，一个空的单链表是一个头指针和一个头结点构成的 。定义指针变量head，令其指向头结点 ，并使头结点的next为NULL。注意：产生头结点时由malloc函数产生一个新节点。算法描述如下：
// 建立一个空的单链表
LinkList InitiateLinkList(){
// 头指针
LinkList head;
// 动态构建一结点，它是头结点
head = malloc (sizeof (Node));
head->next = NULL;
return head;
}在算法中，变量head是链表的头指针，它指向新创建的结点，即头结点。一个空单链表仅有一个头结点，它的指针域为NULL。
2. 求表长
在单链表存储结构中，线性表的长度等于单链表所含结点的个数（不含头结点）。
实现步骤：
(1). 令计数器j为0 ；
(2). 令p指向头结点 ；
(3). 当下一个结点不空时，j加1，p指向下一个结点；
(4). j的值即为链表中结点个数，即表长度。
以下是算法实现：
int lengthLinklist(LinkList head){
Node *p;
p = head; j=0;
while(p->next != null){
j++
p = p->next;
};
return (j)
}3. 读表元素
实现步骤：
(1). 令计数器j为0；
(2) .令p指向头结点 ；
(3). 当下一个结点不空时，并且j<i时，j加1，p指向下一个结点；
(4) .如果j等于i，则p所指结点为要找的第i结点 否则，链表中无第i结点；
Node * GetlinkList(LinkList head,init i){
Node * p;
p = head->next;init c=1;
while((c<i) && (p!=NULL)){
p = p->next;
c++
};
if(i==c){
return (p);
}else{
return NULL;
};
}4. 定位
线性表的定位运算，就是对给定表元素的值，找出这个元素的位置。在单链表的实现中，则是给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称作按值查找。 在定位运算中，也需要从头至尾访问链表，直至找到需要的结点，返回其序号，若未找到，返回0。
实现步骤：
(1). 令p指向头结点；
(2) .令i=0 ；
(3). 当下一个结点不空时，p指向下一个结点，同时i的值加1；
(4) .直到p指向的结点的值为x，返回i+1的值；
(5). 如果找不到结点值为x的话，返回值为0。
init LocateLinklist(LinkList head,DataType x){
Node *p = head;
p = p->next;
init i =0;
while(p!= NULL && p->data !=x){
i++;
p=p->next;
};
if(p!=NULL){
// 下标从0开始，找个数要加1
return i+1
}else{
return 0;
}
}5. 插入
插入运算是将值为x的新结点插入到表的第i个结点 的位置上，即插入到ai-1与ai之间。
实现步骤：
(1). 找到ai-1存储位置p；
(2) .生成一个数据域为x的新结点*s；
(3). 令结点*p的指针域指向新结点；
(4) .新结点的指针域指向结点ai。
// 在表head的第i个数据元素结点之前插入一个以x为值的新结点
void InsertLinklist(LinkList head, DataType,init i){
Node *p, *q;
if(i==1){
q = head;
}else{
// 将结点插入i-1到i之间，所以要i-1;
q = GetLinklist(head,i-1);
};
if(q = NULL){
exit("找不到插入的位置");
}else{
// 生成新的结点
p = malloc(sizeof(Node));
p ->data = x;
// 切换指针
p ->next =q->next;
q ->next = p;
}
}6. 删除
删除运算是将表的第i个结点删去。
实现步骤：
(1). 找到ai-1的存储位置p；
(2) .令p-＞next指向ai的直接后继结点；
(3). 释放结点ai的空间，将其归还给"存储池" 。
// 删除表head的第i个结点
void DeleteLinklist(LinkList head,init i){
Node *q;
if(i==1){
q = head;
}else{
// 找到待删除结点的直接前驱
q = GetLinklist(head,i-1);
};
// 若直接前驱存在且待删结点存在
if(q != NULL && q->next != NULL){
// p指向待删除结点
p=q->next;
// 移除待删除结点
q->next = p->next;
// 释放已移出结点p的空间
free(p);
}else {
// 结点不存在
exit("找不到要删除的结点")
}
}7. 删除值为x的重复结点
实现步骤：
(1). 遍历指针域，当指针域不为空，且数据域不等于X时，指针指向下一个；
(2) .遍历完成后，如果指针域为空，返回0；
(3). 遍历完成后，如果指针域不为空，释放指针域所指结点的空间。
int deleteX(LinkList *head, DataType x){
LinkList *p,*q;
p = head;
// 下一个指针域不为空，并且存放的数据不为X时
while(p->next->next!= NULL && p->next->next->data!= x){
p = p->next;
};
// 如果指针为空
if(p->next==NULL) {
return 0;
}else {
q=p->next;
p->next=q->next;
// 释放指针
free(q);
return 1
}
}8. 删除所有重复的结点
实现步骤：
(1). 遍历指针域，当指针域不为空，保存当前指针q；
(2) .再来一层遍历，从保存的指针q开始向后遍历，查找是否有结点的数据域等于q的数据域；
(3). 如果在第二层遍历中有结点的数据域等于q的数据域，则将其删除。
(4). 第二层遍历结束后更新q为下一个指针域，重复之前的操作。
// 删除表head中多余的重复结点
void PurgeLinklist(LinkList head){
Node *p,*q,*r;
// q指示当前检查结点的位置，置其初值指向首结点
q = head->next;
// 当前检查结点*q不是尾结点时，寻找并删除它的重复结点
while(q != NULL){
// 工作指针p指向*q
p = q;
// 当*p的后继结点存在时,将其数据域与*q数据域比较
while(p->next != NULL) {
// 若*(p->next)是*q的重复结点
if (p->next->data==q->data){
// r指向待删结点
r = p->next;
// 移出结点* (p->next)，p->next指向原来* (p->next)的后继结点
p->next = r->next;
free (r);
// 让p指向下一个结点
}else {
p = p->next;
}
};
// 更新检查结点
q = q->next;
}
}9. 建表
建表的过程能常分为三步：首先建立带头结点的空表；其次建立一个新结点，然后将新结点链接到头结点之后，这个结点为尾结点（也是头结点）；重复操作建立新结点和将新结点链接到表尾这两个步骤，直到线性表中所有的元素链接到单链表中。
方法一：通过已实现的插入算法InsertLinklist(LinkList head,int x,int i)来实现，依次增大插入位置 i，使新的结点链入到链表中。
LinkList CreateLinklist1(){
Linklist head;
int x,i;
// 调用上面已实现的初始化算法
head = InitiateLinklist();
i = 1;
scanf("%d",&x);
while(x!=0){
// 调用上面已实现的插入算法
InsertLinklist(head,x,i);
i++;
scanf("%d",&x);
};
return head;
}1+2+...+(n-1) = n(n-1)/2 ，其时间复杂度为 O(n^2)
方法二：上面的算法由于每次插入都从表头开始查找，比较浪费时间。因为每次都是把新的结点链接到表尾，我们可以用一个指针指向尾结点，这样就为下一个新结点指明了插入位置。
Link CreateLinklist2(){
Linklist head;
// q是一个LinkList类型的变量，用来指示链入位置
Node *q,*t;
int x;
// 生成头结点
head = malloc(sizeof(Node));
// 尾指针置初值
q = head;
// 读入第一个元素
scanf("%d",&x);
// 输入的不是结束标志时继续链入
while(x!= 0){
// 生成新结点
t = malloc(sizeof(Node));
t ->data = x;
// 新结点t链入
q ->next = t;
// 修改尾指针q，指向新的尾结点
q = t;
// 读入下一个元素
scanf("%d",&x);
};
// q指向尾结点，置尾结点标志
q->next = NULL;
return head;
}以上算法的时间复杂度为 O(n)
方法三：上面的方法中要借助临时变量t，我们也可以不用这个变量。
LinkList CreateLinklist3(){
Linklist head;
Node *p;
int x;
// 生成头结点
head = malloc(sizeof(Node));
head->next = NULL;
scanf("%d",&x);
// 输入的不是结束标志时继续链入
while(x){
p = malloc(sizeof(Node));
p->data = x;
// 前插：插入链表的第一个结点处
p->next = head->next;
head->next = p;
scanf("%d",&x);
};
return head;
}最终形成的链表的数据顺序与输入顺序正好相反，时间复杂度也是O(n)
线性表链式存储（单向循环链表）
普通链表的终端结点的next值为NULL，循环链表的终端结点的next指向头结点， 在循环链表中，从任一结点出发能够扫描整个链表。
在需要经常操作头尾结点的链表操作中，为了方便的找到循环链表的尾结点，可以在循环链表中附设一个rear指针指向尾结点
线性表链式存储（双向循环链表）
在链表中设置两个指针域， 一个指向后继结点 ，一个指向前驱结点 ，这样的链表叫做双向链表。
双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。找前驱和后继的复杂度均为：O(1)。双向链表的结构体定义如下：
struct dbNode{
DataType data;
struct dbNode *prior, *next;
};
typedef struct dbNode *dbPointer;
typedef dbPointer Dlinklist;假设双向链表中p指向某节点，则有 p->prior->next 与p->next->prior相等。
线性表链式存储（双向循环链表）的运算
1. 删除
设p指向待删结点，删除*p可通过下述语句完成：
(1). p->prior->next=p->next;
p前驱结点的后链指向p的后继结点
(2). p->next->prior=p->prior;
p后继结点的前链指向p的前驱结点
(3). free(p);
释放*p的空间
2. 插入
在p所指结点的后面插入一个新结点*t，需要修改四个指针：
(1). t->prior=p;
t的前驱指向节点p
(2). t->next=p->next;
t的后继指向p的后继
(3). p->next->prior=t;
p的后继的前驱指向t
(4). p->next=t;
p的后继指向t
以上4步操作过程中，第一步和第二步必须先执行，然后才能执行第三步和第四步。