数据结构--线性表的链式表示[王道]

���图来自王道课程，侵权立删。

本篇博客主要为个人学习记录。

目录

单链表的定义

代码定义-单链表

单链表的插入与删除

按位序插入(带头结点)

按位序插入(不带头结点)

指定结点的后插操作

指定节点的前插操作

按位序删除(带头结点)

扩展：指定结点*p的删除

单链表的查找

按位查找

按值查找

求链表长度

尾插法与头插法 (带头结点)

尾插法建立单链表

头插法建立单链表

双链表

双链表的初始化(带头结点)

双链表的插入

双链表的删除

双链表的遍历

---

单链表的定义

利用单链表可以解决顺序表需要 大量连续存储单元 的缺点，但附加的指针域，也存在浪费存储空间的缺点。单链表的元素离散的分布在存储空间中，因此是非随机存取的存储结构，即不能直接找到表中某个特定结点，查找特定结点时，需要从表头开始遍历，依次查找。

头结点 和 头指针的关系：不管带不带头结点，头指针始终指向链表的第一个结点， 头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

引入头结点后，有两个优点：

1.链表第一个位置上的操作和表中其他位置上的操作一致，无需进行特殊处理。

2.无论链表是否为空，其头指针都是指向头结点的非空指针(空表中 头结点的指针域为空)，因此空表和非空表的处理得到了统一。

代码定义-单链表

声明一个单链表时，只需声明一个头指针L，指向单链表的第一个结点(带头结点)

#include//单链表的定义 typedef struct LNode{  //定义单链表结点类型 ElemType data;     //结点存放的数据域 struct LNode *next;//结点存放的指针域，指向下一个结点 }LNode, *LinkList;

需要注意

LinkList 强调这是一个单链表

LNode* 强调这是一个结点

不带头结点的单链表

#includetypedef struct LNode{ElemType data;      //数据域struct LNode *next; //指针域}LNode,*LinkList;//初始化空单链表(不带头结点)bool InitList(LinkList &L){L = NULL; //空表，暂时没有任何结点。防止脏数据return true; } //判断单链表是否为空(不带头结点)bool Empty(LinkList L){return (L == NULL);} int main(){LinkList L; //声明一个指向单链表的指针InitList(L);//初始化一个空表 return 0;}

带头结点的单链表 

#include#includetypedef struct LNode{Elemtype data;        //结点存放的数据域 struct LNode *next;   //结点存放的指针域 }LNode,*LinkList;//初始化空单链表(带头结点)bool InitList(LinkList &L){L = (LNode*)malloc(sizeof(LNode)); //分配空间给头节点if (L == NULL) return false; //分配失败L -> next = NULL; //头结点之后暂时无结点，指向NULLreturn true; } //判断单链表是否为空(带头结点)bool Empty(LinkList L){if (L->next == NULL) return true;else return false;} int main(){LinkList L; //声明一个指向单链表头结点的指针InitList(L);//初始化一个空表 return 0;}

---

单链表的插入与删除

按位序插入(带头结点)

ListInsert(&L,i,e):插入操作，在表L中的第i个位置上插入指定元素e。 找到第i-1个结点，将新结点插入其后。

头结点当作第0个结点。

#include#include//定义单链表 typedef struct LNode{int data;           //结点存放的数据域 struct LNode *next; //结点存放的指针域 }LNode, *LinkList;//在第i个位置插入元素e(带头结点)bool ListInsert(LinkList &L, int i, int e){if(i data = e;s -> next = p->next;p -> next = s;return true; } //防止程序无法运行 int main(){return 0;}

最好时间复杂度O(1) --结点直接插在头结点之后

最坏时间复杂度O(n) --结点插在链表末尾，需要循环多次

平均时间复杂度O(n)

按位序插入(不带头结点)

ListInsert(&L,i,e):插入操作，在表L中的第i个位置上插入指定元素e。 找到第i-1个结点，将新结点插入其后。   

由于不存在第0个结点(即头结点)，因此i=1时需要做特殊处理。并且不带头结点的链表，进行插入、删除第一个元素时，需要更改头指针L的指向。(如图)

#include#include//定义单链表 typedef struct LNode{int data;           //结点存放的数据域 struct LNode *next; //结点存放的指针域 }LNode, *LinkList;//在第i个位置插入元素e(带头结点)bool ListInsert(LinkList &L, int i, int e){if(idata = e;s->next = L; L = s; //头指针指向新结点return true; } //其余结点，操作一致  逻辑与带头结点的链表一样 LNode *p; //指针p指向当前扫描到的结点int j = 1;//记录当前p指向的是第几个结点p = L ;   //L指向第一个结点 //循环，遍历链表，找到第i-1个结点 while(p != NULL && jnext; //指针向后一个结点移位j++;          } if(p == NULL)//i值不合法return false; LNode *s = (LNode *)malloc(sizeof(LNode)); //申请结点空间,s指向待插入的结点 s -> data = e;s -> next = p->next;p -> next = s;return true; //插入成功 } //防止程序无法运行 int main(){return 0;}

指定结点的后插操作

//后插操作：在p结点之后插入元素ebool InsertNextNode(LNode *p , int e){if(p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); //为结点s申请分配空间if(s == NULL) return false; //申请分配失败，比如内存不足s->data = e; //用结点s保存数据元素es->next = p->next;p->next = s; //将结点s连接到p之后return true; } 

时间复杂度O(1)

指定节点的前插操作

如何找到p结点的前驱节点？ --1. 传入头指针    -- 2. 仍然使用后插法，交换数据域

第一种方法，时间复杂度为O(n),需要从头遍历链表，找到p结点的前驱结点，非常麻烦。

第二种方法，时间复杂度为O(1)，代码如下：

//前插操作：在p结点之前插入元素ebool InsertPriorNode(LNode *p , int e){if(p == NULL) return false;LNode *s = (LNode *)malloc(sizeof(LNode)); //为新结点申请分配内存if(s == NULL) return false; //内存分配失败s -> next = p->next;p->next = s;       //新结点接到p结点之后 s->data = p->data; //将p中元素复制到s中 p->data = e;       //将e值覆盖到p结点上return true; }

王道书上的版本：

//前插操作 ：王道书版本bool InsertPriorNode_ (LNode *p , LNode *s){if (p == NULL || s == NULL) return false;s ->next = p->next; //将p结点后的元素接到s后 p->next = s;        //将s连接到p后//交换数据域部分 int temp = p ->data;p->data = s->data;s->data = temp; return true;} 

按位序删除(带头结点)

ListDelete(&L,i,&e):删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值。找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点。(如下图)

王道书上的描述也很好理解：假设结点*p为被删结点的前驱，仅需修改*p的指针域next,将*p的指针域next指向被删结点*q的下一结点，然后释放*q的存储空间。

//按位序删除结点(带头结点)bool ListDelete(LinkList &L, int i,int &e){if(inext == NULL) return false; //第i-1个结点之后无其他结点，错误LNode *q = p->next; //令q指向被删除结点e = q->data;        //e保存被删除的元素值，并返回p->next = q->next;  //将*q结点从链中断开free(q);            //释放结点q的存储空间return true;//删除成功 } 

最好时间复杂度--O(1)  删除头结点之后的第一个结点

最坏、平均时间复杂度--O(n)  删除最后的结点

扩展：指定结点*p的删除

删除结点*p，需要修改其前驱结点的next指针。 --方法1.传入头指针，循环遍历链表，寻找p的前驱结点   --方法2.类似于结点前插中的交换数据域，时间复杂度为O(1)

方法2的实质就是，将被删除结点*p的后继的data值，赋给*p,然后再删除后继，使得时间复杂度为O(1)：

(由于单链表的局限性，方法2会受到限制，比如需要删除的结点是最后一个结点。它的next指针将会指向NULL，方法失效。     被指定删除的结点是最后一个结点时，需要做特殊处理。)

---

单链表的查找

按位查找

//按位查找，返回第i个元素(带头结点)LNode * GetElem(LinkList L, int i){if(inext;if(i==0) return L; //所要查找即为头结点，即第0个结点if(inext; //从第一个结点(头结点之后的结点)开始查找while(p != NULL && p->data != e)p = p->next;return p; //找到后返回该结点指针，否则返回NULL } 

平均时间复杂度O(n)

求链表长度

//求链表长度(带头结点)int length(LinkList L){int len = 0; //统计表长，初始表长为0LNode *p = L; //结点p指向表头，即第0个结点while(p->next != NULL){p = p->next;len++;} return len;} 

时间复杂度O(n)

---

尾插法与头插法 (带头结点)

给了很多数据元素，如何把它们存到一个单链表里？

step1:初始化一个单链表

step2:每次取一个数据元素，插入到表头/表尾

尾插法建立单链表

尾插法生成的链表结点次序和输入数据顺序一致

步骤： 1.初始化单链表  2.设置尾指针r，始终指向链表尾部结点

            3.while循环{每次取一个数据元素插到尾部}

//尾插法，正向建立单链表LinkList List_TailInsert(LinkList &L){int x;      //设元素类型为整型L = (LNode*)malloc(sizeof(LNode)); //创建头结点，申请存储空间LNode *s,*r = L;  //r为表尾指针scanf("%d",&x); //输入结点值//建立循环，开始插入元素，直接插到表尾 while(x != 999){ //999只是一个标志着结束的值，可以任意替换 s = (LNode *)malloc(sizeof(LNode)); //为结点申请空间s -> data = x; //赋值r -> next = s; //结点s插入到尾指针r所指结点的后方r = s; //尾指针r向后移动一位,指向新的表尾结点 scanf("%d",&x); } r -> next = NULL; //尾结点指针置空return L; } 

时间复杂度为O(n)

头插法建立单链表

头插法 数据读入的顺序与生成的链表中元素的顺序是相反的，可以用来实现链表的逆置。总时间复杂度为O(n)，单链表表长为n。

步骤: 1.初始化单链表 2.while循环{每次取一个数据元素e；;}

每次将读取到的数据元素插入到当前链表的头结点之后。

//头插法 逆向建立单链表 LinkList List_HeadInsert(LinkList &L){int x; //数据元素为整型L = (LNode *)malloc(sizeof(LNode)); //创建头结点 L->next = NULL; //初始为空链表LNode *s; //设置指针scanf("%d",&x); //输入结点值while(x != 999){s = (LNode *)malloc(sizeof(LNode)); //创建新结点s -> data = x; //赋值s -> next = L->next ;L -> next = s; //将新结点插入表中，L为头指针scanf("%d",&x);  }  return L;} 

时间复杂度为O(n)

---

双链表

双链表有两个指针prior和next,分别指向直接前驱和直接后继。

表头结点的prior域和尾结点的next域都是NULL.

双链表中结点类型的描述如下:

//双链表类型定义typedef struct DNode{int data;  //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode,*DLinkList; 

双链表的按值查找和按位查找操作与单链表相同，但删除和查找操作比较容易断链，此外，双链表可以很容易的找到当前结点的前驱，插入、删除操作的时间复杂度仅为O(1)。

由于双链表的每个结点多了一个指针域，所以存储密度会低一些。

双链表的初始化(带头结点)

//初始化双链表bool InitDLinkList(DLinkList &L){L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点if(L == NULL) return false; //内存不足，分配失败L ->prior = NULL ; //头结点的prior指向NULL L ->next = NULL ;  //头结点之后暂时没有结点return true; } 

双链表的插入

//双链表的插入//在p结点之后插入s结点bool InsertNextDNode(DNode *p,DNode *s){if(p == NULL || s==NULL) return false; //非法参数s ->next = p->next;if(p->next != NULL) //如果p结点有后继结点 p->next->prior = s; s -> prior = p;p -> next = s;return true;} 

双链表的删除

//删除p结点的后继结点qbool DeleteNextDNode(DNode *p){if(p == NULL) return false; //非法DNode *q = p->next ; //找到p的后继结点qif (q == NULL) return false; //p没有后继结点p->next = q->next;if(q->next != NULL) //q不是最后一个结点q->next->prior = p;free(q); //释放结点空间return true; } 

双链表的遍历