【2.2】线性表的物理结构
前言
在前面介绍了线性表是什么，现在来讲述线性表的两种物理结构的第一种——顺序存储结构。
学习本文需要掌握一定的 C语言基础。
本部分内容参考程杰老师《大话数据结构》，青岛大学王卓老师的授课，王道考研公开课等 综合个人所学的总结笔记。
线性表的顺序存储结构
顺序表——用顺序存储的方式实现的线性表
顺序存储定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表的顺序存储示意图如下：
可以通过
sizeof(ElemType)函数来获取数据元素的大小
顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
顺序表上的基本操作的实现
静态分配
静态分配，顾名思义，它的分配空间在一开始定义的时候就是固定的，代码示例：
1 |
|
ElemType需要看你具体使用的数据结构的类型此处
Sq为sequence的缩写
实现了顺序表静态分配表的初始化和插入操作，代码示例：
1 | // 线性表的顺序表示 |
运行结果：
可以很明显的看出来，这种静态分配的方式的弊端在于其分配的内存空间在一开始是缺点的，使用起来很不灵活，所以引出下面的动态分配，通过动态的分配内存空间来合理运用内存。
动态分配
动态分配内存则需要使用两个函数malloc()和free()函数，这两个函数分别负责申请和释放内存，关于这两个函数的详细说明查看这篇文章：处理动态链表的函数。
使用如上函数需要引入
<malloc.h>头文件
代码示例：
1 |
|
运行结果：
插入操作
插入元素的时候，需要将插入的元素位置后的元素全部向后移动一位，代码示例：
1 | //插入元素 |
注：如果你使用
VS code编译器报错存在未定义的bool，则引入#include <stdbool.h>
删除操作
删除元素的时候，需要将删除元素位置后的元素全部前移一位，代码示例：
1 | //删除元素 |
运行结果：
查找操作
按位查找
1 | //查找操作——按位查找 |
按值查找
1 | //按值查找 |
查找测试
1 | int main(){ |
运行结果：
顺序表的特点
- 随机访问，即在 $O(1)$ 的时间内找到第 i 个元素
- 存储密度高，每个节点只存储数据元素
- 拓展容量不方便（即使是动态分配，也需要大量的时间拓展）
- 插入，删除操作不方便，需要移动大量的元素
线性表的链式存储结构
顺序表可以随时存取表中任意一个元素，它的存储和读取更为直观，但是对于插入和删除操作则需要移动大量元素。使用链式存储，不需要大量连续的存储地址，它通过指针来指示下一部分的存储位置，对于删除和插入操作来说，它不需要大量移动元素就可以完成。
链式存储结构根据其设计类型不同还可以分为：
- 单链表
- 双链表
- 循环链表
- 静态链表
前排提醒：下面代码中的
ElemType，是我一开始定义的#define ElemType int
单链表
单链表的定义
单链表的基本操作实现
单链表的定义
单链表的每个结点包含两个部分：数据域和指针域，分别用来存储数据和指向下一个结点的地址。
而头结点只表示链表的地址，也就是链表本身的表示方式，其数据域负责存储链表的结点数量信息。
1 | //单链表结点结构 |
初始化链表
对创建的单链表进行初始化工作。
1 | //初始化单链表 |
插入结点
将新数据插入链表中，需要考虑插入的位序是否在链表中不存在，在插入过程中，需要给插入的数据创建专门的结点，然后将结点的指针域指向至其要插入的位序的下一个结点，再将其要插入位序的上一个结点指向新结点完成插入。代码示例：
注意：需要先将新结点指向后面再将插入点前的结点的指针域指向新指针吗，反之，则会出现断链
1 | //按位序插入结点 |
删除结点
思路：便利获取删除结点的前一个结点或者便利获取删除结点的前一个结点和删除结点，然后将删除结点的前一个结点的指针域指向删除的结点的指针域，即删除结点的下一个结点。代码示例：
1 | //删除结点——按位序删除 |
输出链表
思路：遍历链表打印输出即可。
1 | //输出链表 |
链表查找——按位序查找
1 | //单链表的查找——按位查找 |
链表查找——按值查找
1 | //单链表的查找——按值查找 |
建立单链表——尾插法
1 | //单链表的建立——尾插法 |
建立单链表——头插法
1 | //单链表的建立——头插法 |
双链表
在单链表插入操作的时候，往往我们是没有办法直接获取一个结点的前驱结点，双链表就解决了这个问题，在定义结点的时候，不仅存储下一个结点的位置，还存储上一个结点的位置。
双链表(带头结点)
1 | //结点结构体 |
双链表建立——尾插法
1 | //建立双链表——尾插法 |
*L的用法详见C指针运算符
输出双链表内容
1 | //输出链表 |
双链表(不带头结点)
1 | //结点结构体 |
双链表建立——头插法
1 | //头插法建立双链表 |
输出双链表的内容
1 | //输出链表 |
循环链表
循环链表是单链表的最后一个结点的指针域指向头结点。
循环链表的定义
此处借用单链表定义的内容，代码示例：
1 | //循环链表结点结构 |
循环链表初始化
1 | //循环链表初始化 |
循环链表的建立——头插法
1 | //循环链表建立——头插法 |
输出双链表
1 | //输出循环链表 |
静态链表
在一些没有指针的语言中，前辈们想到的用静态链表的方式来实现链表的功能的办法。
静态链表的定义
1 |
|
静态链表的操作
不想写啊啊啊，空着了
End
如上，线性表部分结束，最后呈现单链表，双链表的整合代码，代码不全，仅做示例。
单链表
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//单链表结点结构
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
//单链表头结点
typedef struct SingleList
{
int n; //表示链表长度
Node *first; //链表的起始地址
}SingleList;
bool InitList(SingleList *L); //初始化表
bool InsertNode(SingleList *L, int locattion, ElemType data); //按位序插入结点
bool PrintList(SingleList *L); //输出链表
bool DeleteNode(SingleList *L, int location); //删除结点——按位序
bool GetElem(SingleList* L,int location); //链表查找——按位序
bool GetElemLocation(SingleList *L, ElemType data); //链表查找——按值
bool List_TailInsert(SingleList *L); //建立单链表——尾插法
bool List_HandInsert(SingleList *L); //建立单链表——头插法
//程序入口点
int main(){
SingleList singleList;
InitList(&singleList);
List_HandInsert(&singleList);
PrintList(&singleList);
InsertNode(&singleList, 2, 6);
PrintList(&singleList);
}
//初始化单链表
bool InitList(SingleList* L){
L->first = NULL;
L->n = 0;
return true;
}
//按位序插入结点
bool InsertNode(SingleList* L,int locattion,ElemType data){
if (locattion > L->n+1 || locattion < 1)
{
printf("插入失败\n");
return false;
}else{
// Node* tempout = malloc(sizeof(Node)); //申请插入结点的内存空间
Node* tempout = malloc(sizeof(Node));
Node* tempin = (Node *)L; //临时结点
for (int i = 0; i < locattion-1; i++)
{
tempin = tempin->next; //获取插入结点的前一个结点
}
tempout->data = data; //插入结点包含的数据
tempout->next = tempin->next; //将插入结点的下一个指针指向原来指针指向的位置
tempin->next = tempout; //将插入位置前一个结点的指针指向插入结点
L->n++;
printf("插入成功\n");
return true;
}
}
//输出链表
bool PrintList(SingleList* L){
if (L->first ==NULL)
{
printf("输出失败");
return false;
}else{
Node *temp = (Node*)L;
printf("链表的数据为：");
while (temp->next!=NULL)
{
temp = temp->next;
printf("%d", temp->data);
}
printf("\n");
return true;
}
}
//删除结点——按位序删除
bool DeleteNode(SingleList* L,int location){
if (location < 1 || location > L->n)
{
return false;
}
Node *temp = (Node*)L; //删除结点的前一个结点
Node *tempNext = (Node*)L; //删除结点
for (int i = 0; i < location; i++)
{
tempNext = tempNext->next; //获取删除结点
if(i<location-1)
temp = temp->next; //获取删除结点的前一个结点
}
temp->next = tempNext->next; //将删除结点的前一个结点的指针域指向删除结点的后一个结点
printf("删除位序(%d)成功，其数据为 %d\n", location, tempNext->data);
free(tempNext); //释放删除结点
L->n--; //表长度减一
return true;
}
//单链表的查找——按位查找
bool GetElem(SingleList* L,int location){
if (location < 1 || location >L->n) //判断查找位序是否超出范围
{
return false;
}
Node * temp = (Node*)L;
for (int i = 0; i < location; i++)
{
temp = temp->next; //便利到指定位序获取结点
}
printf("该位序数据域为: %d \n", temp->data); //输出查找的位序结点的数据域
return true;
}
//单链表的查找——按值查找
bool GetElemLocation(SingleList* L,ElemType data){
Node * temp = (Node*)L; //起始位置为头结点
for (int i = 0; i < L->n; i++)
{
temp = temp->next; //移动下一个结点
if (temp->data ==data) //判断是否符合数据
{
printf("指定数据的位序为: %d\n", i+1);
return true;
}
}
return false; //遍历完成不存在该数据，返回false
}
//单链表的建立——尾插法
bool List_TailInsert(SingleList* L){
Node *temp = (Node*)L;
int datas;
scanf("%d", &datas); //获取第一个输入的数值
while (datas!=9999) //取一个特殊值表示终止单链表数据的输入
{
Node *tempNext = malloc(sizeof(Node)); //申请一个新结点的内存空间
tempNext->data = datas; //新结点的数据域设定为输入的数据
temp->next = tempNext; //将结点指向新创建的结点
temp = temp->next; //结点向下走一个
L->n++; //表长+1
scanf("%d", &datas);
}
temp->next = NULL; //单链表最后的结点的指针域为NULL
return true;
}
//单链表的建立——头插法
bool List_HandInsert(SingleList* L){
int datas;
scanf("%d", &datas); //获取第一个输入的数值
while (datas!=9999) //取一个特殊值表示终止单链表数据的输入
{
Node *tempNext = malloc(sizeof(Node)); //为新数据结点开辟内存空间
tempNext->data = datas; //将输入的数据传递给新结点的数据域
tempNext->next = L->first; //新结点的指针域指向单链表的第一个结点
L->first = tempNext; //单链表头结点指向新结点
L->n++; //链表长度+1
scanf("%d", &datas); //获取第一个输入的数值
}
return true;
}双链表
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//结点结构体
typedef struct Node
{
ElemType data; //数据域
struct Node* before; //前结点指针
struct Node* next; //后结点指针
}Node,Dlist;
bool List_TailInsert(Dlist* L); //建立双链表——尾插法
bool PrintList(Dlist* L); //输出链表
bool InitSingleList(Dlist* L); //初始化链表
//程序入口
int main() {
Dlist L;
InitSingleList(&L);
List_TailInsert(&L);
PrintList(&L);
}
//链表初始化
bool InitSingleList(Dlist* L) {
L->before = NULL;
L->next = NULL;
return true;
}
//建立双链表——尾插法
bool List_TailInsert(Dlist* L){
Node* temp = L;
int data;
printf("请输入数值：");
scanf("%d", &data);
while (data != 9999)
{
Node* tempNext = (Node*)malloc(sizeof(Node)); //插入的新结点开辟内存空间
tempNext->data = data; //将数值放入结点的数据域
tempNext->next = temp->next; //新结点的后指针指向前一个结点的后指针
tempNext->before = temp; //新结点的前指针指向前一个结点
temp->next = tempNext; //前一个结点的后指针指向新结点
temp = temp->next; //结点光标移动到下一位
printf("请输入数值：");
scanf("%d", &data);
}
return true;
}
//输出链表
bool PrintList(Dlist* L) {
if(L->next == NULL){
printf("链表为空");
return false;
}
Node* temp = L->next;
printf("链表内容为：");
printf("%d", temp->data);
while (temp->next != NULL)
{
temp = temp->next;
printf("%d", temp->data);
}
printf("\n");
return true;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Seraphineの小窝！
评论
