线性表（Linear List）
是由n(n≥0)个具有相同特性（数据类型）的数据元素（结点）a1，a2，...，ai-1，ai，ai+1，...，an组成的有限序列。
其中，a1为线性起点（起始结点），an为线性终点（终端结点）。对于每一个数据元素ai，我们称ai-1为它的直接前驱，ai+1为它的直接后继。i（1≤i≤n）为下标，是元素的序号，表示元素在表中的位置；n为数据元素总个数，即表长。当n=0时，称线性表为空表。
线性表的存储结构
在计算机中，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。
回到顶部
线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储，即把逻辑上相邻的数据元素存储在物理上相邻的存储单元中。其特点是依次存储，地址连续——中间没有空出存储单元，且任一元素可随机存取。
线性表的第一个数据元素a1的存储位置，称为线性表的起始位置或基地址。
顺序表中元素存储位置的计算
LOC(ai） = LOC(a1) + (i-1) x m （m为每个元素占用的存储单元）
每个元素的存取时间复杂度为O(1)，我们称之为随机存取。
顺序表的表示
1
2
3
4
5
例如：多项式 Pn(x) = p1xe1 + p2xe2 + ... + pmxem 的顺序存储结构类型定义如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2.1 顺序表基础操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
顺序表初始化、销毁顺序表、清空顺序表、求顺序表长度、判断顺序表是否为空及顺序表的取值等操作，它们的时间复杂度都为O(1)
2.2 顺序表的查找
1
2
3
4
5
6
7
8
平均查找长度ASL（Average Search Length）：为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。
含有n个记录的表，查找成功时：
ASL = 1/n * (1+2+...+n) = (n+1)/2
所以，顺序表查找算法的平均时间复杂度为：O(n)
2.3 顺序表的插入
【算法思路】
- 判断插入位置i是否合法；
- 判断顺序表的存储空间是否已满，若已满返回ERROR；
- 将第n至第i位的元素依次向后移动一个位置，空出第i个位置；
- 将要插入的新元素e放入第i个位置；
- 表长加1，插入成功返回OK。
【代码】
1
2
3
4
5
6
7
8
9
10
11
【算法分析】
算法时间主要耗费在移动元素的操作上。
若插入在尾结点之后，则需要移动0次；若插入在首结点之前，则需要移动n次；在各个位置插入（共n+1种可能）的平均移动次数为：E = 1/(n+1) * (0+1+...+n) = n/2
所以，顺序表插入算法的平均时间复杂度为：O(n)
2.4 顺序表的删除
【算法思路】
- 判断删除位置i是否合法；
- 将第i+1至第n位的元素依次向前移动一个位置；
- 表长减1，删除成功返回OK。
【代码】
1
2
3
4
5
6
7
8
【算法分析】
算法时间主要耗费在移动元素的操作上。
若删除尾结点，则需要移动0次；若删除首结点，则需要移动n-1次；在各个位置删除（共n种可能）的平均移动次数为：E = 1/n * (0+1+...+n-1) = (n-1)/2
所以，顺序表删除算法的平均时间复杂度为：O(n)
由于没有占用辅助空间，顺序表所有操作的空间复杂度都为：O(1)
2.5 顺序表的优缺点
优点：
- 存储密度大（结点本身所占存储量 / 结点结构所占存储量 = 1）；
- 可以随机存取表中任一元素。
缺点：
- 在插入、删除某一元素时，需要移动大量元素；
- 浪费存储空间；
- 属于静态存储形式，数据元素的个数不能自由扩充。
回到顶部
链式存储结构又称为非顺序映像或链式映像。其特点是：
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
- 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。这种存取元素的方法被称为顺序存取法。
链式存储相关术语：
- 结点：数据元素的存储映像。由数据域和指针域两部分组成。
- 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
- 单链表：结点只有一个指针域的链表，结点包括当前元素的数据和其后继元素的地址。
- 双链表：结点有两个指针域的链表，结点当前元素的数据、其前驱元素的地址以及其后继元素的地址。
- 循环链表：首尾相接的链表。
- 头指针：指向链表中第一个结点的指针。
- 首元结点：链表中存储第一个数据元素a1的结点。
- 头结点：在链表的首元结点之前附设的一个结点。
- 空表：链表中无元素，称为空链表（头指针和头结点仍然在）。
Q1：如何表示空表？
- 无头结点时，头指针为空时表示空表。
- 有头结点时，当头结点的指针域为空时表示空表。
Q2：在链表中附设头结点有什么好处？
- 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理。
- 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
Q3：头结点的数据域内装的是什么？
头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值。
3.1 单链表
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。若头指针名为L，则把链表称为表L。
单链表的存储结构
1
2
3
4
5
定义链表和节点指针可以用 LinkList L; 或LNode* L;
这两种方式等价，但为了表述清晰，一般建议使用LinkList定义链表，Lnode定义结点指针。即：
定义链表：LinkList L;
定义节点指针：Lnode* p;
3.1.1 单链表的初始化（带头结点）
即构造一个如图的空表：
【算法思路】
- 生成新结点作头结点，用头指针L指向头结点；
- 将头结点的指针域置空。
【代码】
1
2
3
4
5
6
3.1.2 判断单链表是否为空
【算法思路】
判断头结点指针域是否为空。
【代码】
1
2
3
4
5
6
3.1.3 单链表的销毁
【算法思路】
从头指针开始，依次释放所有节点。
【代码】
1
2
3
4
5
6
7
8
9
10
3.1.4 清空单链表
【算法思路】
从首元结点开始，依次释放所有结点，并将头结点指针域设置为空。
【代码】
1
2
3
4
5
6
7
8
9
10
11
3.1.5 求单链表的表长
【算法思路】
从首元结点开始，依次计数所有结点。
【代码】
1
2
3
4
5
6
7
8
9
10
11
3.1.6 取值
【算法思路】
从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点位置。我们称之为顺序存取。
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3.1.7 查找
【算法思路】
- 从第一个结点起，依次与待查找数据e相比较；
- 如果找到一个其值与e相等的数据元素，则返回其在链表中的位置或地址；
- 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或NULL。
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
【算法分析】
因线性链表只能顺序存取，即在查找时要从头指针找起，因此查找的时间复杂度为：O(n)
3.1.8 插入新结点
【算法思路】
- 首先找到ai-1的存储位置p；
- 生成一个数据域为e的新结点s；
- 插入新结点：首先新结点的指针域指向结点ai，然后结点ai-1的指针域指向新结点。
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
【算法分析】
在编译 p->next = s 这句代码是会报异常：“不能将Lnode*类型的值分配到Lnode类型的实体”。
因线性链表不需要移动元素，只要修改指针，一般情况下插入操作的时间复杂度为：O(1)。但是，如果要在单链表中进行前插操作，由于要从头查找前驱结点，其时间复杂度为：O(n)。
3.1.9 删除结点
【算法思路】
- 首先找到ai-1的存储位置p，保存要删除的ai的值（如果有必要）；
- p的指针域指向结点ai+1；
- 释放结点ai的空间。
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
【算法分析】
其时间复杂度和插入操作一致。
3.1.10 建立单链表
（1）头插法——元素插入在链表头部，也叫前插法。
【算法思路】
- 从一个空表开始，重复读入数据；
- 生成新结点，将读入数据存放到新结点的数据域中；
- 从最后一个结点开始，依次将各结点插入到链表的前端。
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
（2）尾插法——元素插入在链表尾部，也叫后插法。
【算法思路】
- 从一个空表L开始，将新结点逐个插入到链表尾部，尾指针r指向链表的尾结点；
- 初始时，r和L都指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
【算法分析】
建立单链表时间复杂度为：O(n)
3.2 双向链表
双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链中就形成了两个方向不同的链，故称为双向链表。
双向循环链表：让头结点的前驱指针指向链表的最后一个结点；让最后一个节点的后继指针指向头结点。
双向链表的结构定义
1
2
3
4
5
双向链表结构具有对称性（设指针p指向某一结点）：
p -> prior -> next = p = p ->next -> prior
在双向链表中有些操作（求表长、取值等），因仅涉及一个方向的指针，所以他们的算法与线性链表相同。但在插入、删除时，则需要同时修改两个方向上的指针，两者的时间复杂度都为O(n)。
3.2.1 双向链表的插入
【算法思路】
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
3.2.2 双向链表的删除
【算法思路】
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3.3 循环链表
循环链表是一种头尾相接的链表，表中最后一个结点的指针域指向头结点，整个链表形成一个环。
优点：从表中任一结点出发均可找到表中其他结点。
示例：带尾指针循环链表的合并（将Tb合并在Ta之后）
【算法思路】
【代码】
1
2
3
4
5
6
7
8
9
3.4 单链表、双向链表和循环链表的时间效率比较
回到顶部
存储密度定义：
存储密度 = 结点数据本身占用的空间 / 结点占用的空间总量
比如单链表某个节点p，其数据域占8个字节，指针域占4个字节，其存储密度 = 8/12 = 67%。
回到顶部
5.1 有序表的合并
已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
例如：La=(1,7,8) Lb=(2,4,6,8,10,11) → Lc=(1,2,4,6,7,8,8,10,11)
（1）顺序表实现有序表合并
【算法思路】
- 创建一个空表Lc；
- 依次从La和Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变为空；
- 继续将La或Lb其中一个表的剩余结点插入到Lc表的最后。
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
【算法分析】
时间复杂度：O(ListLength(La) + ListLength(Lb))
空间复杂度：O(ListLength(La) + ListLength(Lb))
（2）链表实现有序表合并
【算法思路】
【代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
【算法分析】
时间复杂度：O(ListLength(La) + ListLength(Lb))
空间复杂度：O(1)
到此这篇单向链表和双向链表的数据结构（单链表和双向链表的区别）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/sjkxydsj/16648.html