数据结构第二章(中篇)
2.5 线性表的链式表示和实现
通过上一小节的学习，我们不难发现顺序表的优点是任一元素均可随机存取。但他的缺点也很明显，在进行插入和删除操作时，需移动大量元素，存储空间不灵活
所有这些问题，都可以通过线性表的另一种表示方法——链式存储结构来解决。
- 再开始本章的学习之前，我们先了解一下什么是链表：
- 用一组物理位置任意的存储单元来存放线性表的数据元素。
- 这组存储单元既可以是连续的也可以是不连续的，甚至是零散分布在存储中任意位置上的。
- 链表中的元素的逻辑次序和物理次序不一定相同
其中姓名列为数据域，数据域是用来存储元素数值数据
后面的四位编码为指针域，用来存储直接后继结点的存储位置
我们可以通过头指针来命名单链表
- 与链式存储相关的术语
- 结点：数据元素的存储映像。有数据域和指针域两部分组成
- 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
- 单链表，双链表，循环链表
- 节点只有一个指针域的链表称为单链表或线性链表
- 结点有两个指针域的链表，称为双链表
- 首位相连的链表称为循环链表
- 头指针，头结点，首元结点（头指针>头结点>首元结点）
- 头指针：指向链表中第一个结点的指针
- 首元结点：存储第一个元素的结点
- 头结点：首元结点前附设的一个结点
- 带头结点
- 不带头结点
-
空表如何表示？
无头结点时，头指针为空
有头结点时，头结点指针域为空
-
多设置一个头结点有什么好处？
-
便于首元结点的处理
结点是由结构体构造的，没有头结点的话，第一个数据元素的地址储存在头指针里，就没有储存在结构体里，操作上就和其他数据元素不同，而有了头结点，在链表里第一个位置的操作和其他位置一致，无须进行特殊处理
-
便于空表和非空表的统一处理
结点是由结构体构造的，没有头结点的话，第一个数据元素的地址储存在头指针里，就没有储存在结构体里，操作上就和其他数据元素不同
-
头结点的数据域内装什么
可以空着也可以存放线性表长度等附加信息，但该结点不能计入链表长度值
顺序表是随机存取法：找到要取的元素直接找他的位置就可以了
链表是顺序存取：只能从头指针进入链表，然后顺序扫描其余结点。
-
2.5.1 单链表的定义和表示
-
单链表的存储结构为： 数据域|指针域 =》 【data|next】
-
其中data什么类型取决于数据元素什么类型，如果处理的是学生表这种，比较复杂的数据类型，则通常定义为ElemType类型
-
next的类型取决于他存放的地址的数据元素是什么类型 比如存放的是int a=5,那么就是int *P
1 | typedef struct Lnode{ //声明结点的类型和指向结点的指针类型 |
定义链表L：LinkList L；
定义结点指针P：LNode *P；
- 例如：有一个存储学生学号、姓名、成绩的单链表结点类型定义如下：
1 | typedef Struct student{ |
这样写不常用，不方便不统一，通常用一下格式
1 | typedef Struct{ |
2.5.2 单链表基本操作和实现 （重点）
1.5.2.1 初始化
算法2.6 单链表的初始化
- 生成新结点作为头结点，用头指针L 指向头结点。
- 头结点的指针域置空。 =》 【 |^】
1 | Status lnitList_L(LinkList &L){ |
补充单链表的几个常用简单算法：
-
判断链表是否为空
1
2
3
4
5
6int ListEmpty(LinkList L){
if(L->next)
return 0;
else
return 1;
} -
单链表的销毁
-
从头指针开始，依次释放所有结点
1
2
3
4
5
6
7
8
9Status DestroyList_L(LinkList &L){ //销毁单链表P
Lnode *p; //或LinkLIst p
while(L){ //L指向空停止循环
p=L; //把L的地址给p
L=L->next； //L指向下一个地址
delete p; //删除p所指的结点
}
return OK;
}
-
-
清空链表
-
依次释放所有结点，并将头结点的指针域设置为空
1
2
3
4
5
6
7
8
9
10
11
12
13Status clearList_L(LinkList &L){ //将L重置为空表
Lnode *p,*q;
p=L->next;
while(p){ //没到表尾
g=p->next;
delete p;
p=q;
}
L->next=NULL; //头结点指针域为空
return OK:
}
-
-
求链表表长
-
从首元结点开始，依次计数所有结点
1
2
3
4
5
6
7
8
9
10int ListLength_L(LinkList L){ //LinkLIst定义的变量就是指针型的
LinkList p:
P=L->next;
i=0;
while(p){
i++;
p=p->next
}
return i;
}
-
重要知识点重温：
1.5.2.2 取值
算法2.7 取值 ——取链表中第i个元素的内容
-
从头开始，顺着链域往下搜索，指针后移且计数器x++直到x=i.
1
2
3
4
5
6
7
8
9Status GetElem_L(LinkList L,int i, ElemType &e){
p=L->next;i=1; //初始化
while(p&&j<i){ //向后扫，知道p指向第i个元素或p为空
p=p->next;++j;
}
if(!p||j>i)return ERROR; //第i个元素不存在
e=p->data;
return OK;
}//GetElem_L
1.5.2.3 查找
算法2.8 按值查找——根据指定数据获取改数据所在位置
-
从第一个结点开，依次和e比较
-
如果找到了与e值相等的数据元素，则返回其地址
-
没找到则返回0或NULL
1
2
3
4
5
6Lnode *LocateELem_L (LinkList L, Elemtype e) {
p=L->next;
while(p&&p->data!=e)
p=p->next;
return p;
}或者
1
2
3
4
5
6
7int LocateELem_L(LinkList L, Elemtype e){
p=L->next;i=1:
while(p&&p->data!=e)
{p=p->next;j++;}
if(p)return j; //没找到的话p指向空
else return 0;
}
1.5.2.4 插入
算法2.9 插入——在第i个结点前插入值为e的新结点
-
找到结点i-1
-
建构新结点s
-
s->next=p->next；p->next=s；
1
2
3
4
5
6
7
8
9Status Listlnsert_L(lLinkList &L,int i,ElemType e){
p=L;j=0;
while(p&&j<i-1){p=p->next;++j;} //找节点
if(!p||j>i-1)return ERROR; //判断位置是否合法（是否小于一或大于表长加一）
s=new LNode; s->data=e; //生成新结点s,数据域为e
s->next=p->next; //插入新结点
p->next=s;
return OK;
}//Listlnsert_L
1.5.2.5 删除
算法2.10 删除——删除第i个结点
-
找到结点i-1
-
p->next=p->next->next
-
释放结点i的空间
1
2
3
4
5
6
7
8
9
10Status ListDelet_L(LinkList &L,int i,ElemType &e){
p=L;j=0;q;i;
while(p->next&&j<i-1){p=p-next;++j;} //找到i-1
if(!(p->next)||j>i-1)return ERROR; //删除位置不合理
q=p->next; //q指向要删除的结点
p->next=q->next; //是p指针next域指向删除域的下一个结点
e=q->data; //保存删除结点的数据域
delete q; //释放空间
retun OK;
}
分析单链表查找，插入，删除算法的时间效率分析：
- 查找：应为只能顺序存取，即要从头指针开始找起，查找时间复杂度为$\large O(n)$
- 插入和删除：因为线性链表不需要移动元素，只用修改至臻，一般情况下的时间复杂度为$\large O(1)$
1.5.2.6 创建单链表
1.5.2.6.1 头插法——插到链表头部
-
L=new LNode;
L=（LinkList）malloc(sizeof(LNode));//C语言 //生成一个结点
p->data=$a_n$ //数据域赋值
-
p->next=L->next; L->next=p; //L指针域的空赋给p的指针域,L指针域指向p
1
2
3
4
5
6
7
8
9
10void CreateList_H(LinkList &L,int n){
L=new LNode;
L->next=NULL; //建立带头结点的单链表
for(i=n;i>0;--i){
p=（LNode*)malloc(sizeof（LNode)); //生成新结点
scanf(&p->data);
p->next=L->next;
L->next=P:
}
}
1.5.2.6.2 尾插法——插到链表尾部
-
从空表L开始，将新结点逐个插入到链表尾部，尾指针r指向链表的尾节点
-
初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。
1
2
3
4
5
6
7
8
9
10
11void CreatList_R(LinkList &L,int n){
L=new LNode;
L->next=NULL;
r=L;
for(i=0;i<n;++i){
p=（LNode*)malloc(sizeof（LNode)); //生成新结点
scanf(&p->data);
r->next=p;
r=p;
}
}
