数据结构--线性表的链式表示[王道]
���图来自王道课程，侵权立删。
本篇博客主要为个人学习记录。
目录
单链表的定义
代码定义-单链表
单链表的插入与删除
按位序插入(带头结点)
按位序插入(不带头结点)
指定结点的后插操作
指定节点的前插操作
按位序删除(带头结点)
扩展：指定结点*p的删除
单链表的查找
按位查找
按值查找
求链表长度
尾插法与头插法 (带头结点)
尾插法建立单链表
头插法建立单链表
双链表
双链表的初始化(带头结点)
双链表的插入
双链表的删除
双链表的遍历
单链表的定义
利用单链表可以解决顺序表需要 大量连续存储单元 的缺点，但附加的指针域，也存在浪费存储空间的缺点。单链表的元素离散的分布在存储空间中，因此是非随机存取的存储结构，即不能直接找到表中某个特定结点，查找特定结点时，需要从表头开始遍历，依次查找。
头结点 和 头指针的关系：不管带不带头结点，头指针始终指向链表的第一个结点， 头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。
引入头结点后，有两个优点：
1.链表第一个位置上的操作和表中其他位置上的操作一致，无需进行特殊处理。
2.无论链表是否为空，其头指针都是指向头结点的非空指针(空表中 头结点的指针域为空)，因此空表和非空表的处理得到了统一。
代码定义-单链表
声明一个单链表时，只需声明一个头指针L，指向单链表的第一个结点(带头结点)
#include
//单链表的定义
typedef struct LNode{ //定义单链表结点类型
ElemType data; //结点存放的数据域
struct LNode *next;//结点存放的指针域，指向下一个结点
}LNode, *LinkList;
需要注意
LinkList 强调这是一个单链表
LNode* 强调这是一个结点
不带头结点的单链表
#include
typedef 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
#include
typedef 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; //头结点之后暂时无结点，指向NULL
return 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结点之后插入元素e
bool 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保存数据元素e
s->next = p->next;
p->next = s; //将结点s连接到p之后
return true;
}
时间复杂度O(1)
指定节点的前插操作
如何找到p结点的前驱节点？ --1. 传入头指针 -- 2. 仍然使用后插法，交换数据域
第一种方法，时间复杂度为O(n),需要从头遍历链表，找到p结点的前驱结点，非常麻烦。
第二种方法，时间复杂度为O(1)，代码如下：
//前插操作：在p结点之前插入元素e
bool 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; //统计表长，初始表长为0
LNode *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结点的后继结点q
bool DeleteNextDNode(DNode *p){
if(p == NULL) return false; //非法
DNode *q = p->next ; //找到p的后继结点q
if (q == NULL) return false; //p没有后继结点
p->next = q->next;
if(q->next != NULL) //q不是最后一个结点
q->next->prior = p;
free(q); //释放结点空间
return true;
}