热门标签
热门文章
- 1AIGC的API使用详解_aigc api
- 2uni-app+uview组件上传图片时添加水印并保存到相册，具体样式需自己调整_uview upload 选择多张图片并添加水印
- 3k8s 命令行工具_terminationmessagepath:
- 4数据结构 顺序表实现手机通讯录_设计手机通讯录系统用线性表的顺序存储
- 5数学建模—编程手算法学习路线（自用）_研究生数学建模编程手怎么准备代码
- 6pythonpecan教程_python后台Flask 快速入门
- 7电话机器人：智能助手，提升销售效率
- 8云原生周刊：Kubernetes v1.30 发布 ｜ 2024.4.22
- 9编程思路整理---逻辑篇_编程思路怎么写
- 10什么是 TLS/SSL 握手
当前位置: article > 正文
数据结构—动态顺序表
作者：繁依Fanyi0 | 2024-04-23 15:30:43
赞
踩
动态顺序表
动态顺序表的实现
一、顺序表的概念
*（1）*顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上实现各种功能
*（2）*这里我们注意顺序表之所以有顺序二字就是因为它和数组最大的区别就是要依次存储数据元素（也就是说）要按顺序存储。
而顺序表又可以分成静态顺序表和动态顺序表。
二、静态顺序表（可跳过）
我们首先来创建一个数组，利用几个接口函数来完成对顺序表的完善。而与以往不同的是，接口函数的命名风格是跟着STL走的，代码如下
#define MAX 100
typedef int SLDataType;
typedef struct Seqlist
{
SLDataType a[MAX];
Int size
}SL;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
这就是静态数组开始的创建，通过typedef（重定义）将原本复杂的名词Seqlist写成SL。 同时，SLDataType更好的实现以后替换其他类型变量的麻烦。而今天，我们讲的重点是动态顺序表的实现。
三、动态顺序表的动态思路
动态顺序表与静态顺序表在开始建立的时候，由于需要满足满了再扩容的需要，我们会创建一个指针a指向这个数组，在创建一个capacity用来表示数组实际能存储的空间容量是多大。
代码如下
typedef struct Seqlist
{
SLDataType* a;
int size;// 表示数组中存储了多少”个“数据
int capacity; // 数组实际能存储数据的空间容量是多大
}SL;
- 1
- 2
- 3
- 4
- 5
- 6
四、初始化顺序表
在使用顺序表时我们一般先将其初始化，避免后面不必要的麻烦。代码如下
void SeqlistInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;// 初始化
}
- 1
- 2
- 3
- 4
- 5
五、检查扩容
（1）这是一个动态的顺序表，因此在其数据满的时候我们要将其扩容，这个程序在后面其他的接口函数中也会使用到，因此我们将它单独写出来。此时注意，由于我们第一次已经将capacity初始化为0了，再次进行扩容时，newcapacity不能直接*0 。代码如下
void SeqlistCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;// 扩容 SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));// realloc算的是字节数 if (tmp == NULL) { printf("realloc fail\n"); exit(-1);// 这里return是不行的exit直接终止程序了 } ps->a = tmp; ps->capacity = newcapacity; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
（2）在这个代码中我们先判断了capacity是否为0，为0则赋给它一个值，我们这里给它赋了4。扩容我们选择乘2倍（这个无所谓乘多少1.5倍也行，只是2倍是个怎么说嘞，非常合适的这样的一个值，扩小了扩容就会频繁，扩大了，就会造成空间浪费）。
有人会说ps->a为NULL有问题啊。实际上没关系，不用担心，realloc函数的第一个参数如果是空，realloc作用和malloc一样。
（3）在这里面如果开辟失败我们用exit(-1)来结尾，很多时候我们写代码习惯用return-1来终止。而在这里，假如开辟失败，剩下的内容我们就无法进行下去，所以在这里我们用的是exit而不是return。
六、各种功能的实现
6.1 尾插（删）顺序表
1.尾插函数：我们第一步要做的事情就是检查空间是否已满，如果满了就要扩容，这里我们先引用前面增容函数。
将我们要插入的X插入到数组中。由于size是袁旭的个数，同时也是尾部最后一个元素后一个元素的位置。因此可以直接++,代码如下：
void SeqlistPushBack(SL* ps, SLDataType x) // 尾插
{
SeqlistCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
- 1
- 2
- 3
- 4
- 5
- 6
2.尾删函数：，尾插函数成功实现后我们就可以实现尾删函数。尾删函数我们可以将最后一个数改为0，然后再size减减，减减在前或者在后都不影响实际结果。而这里面就有两种方法，代码如下：
void SeqlistPopBack(SL* ps)
{
/* if (ps->size > 0)
{
//ps->a[ps->size - 1] = 0; 这个不要也没有问题
ps->size--;
}
*/ // 方法一
assert(ps->size > 0); //为真继续，为假即<=0就会终止程序，并说明断言失败
ps->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
6.2 头插（删）函数
1.头插函数：如图所示，我们要将数组中的元素依次往后诺一个位置，如图（见谅。画图有点抽象）
这里end指向的是size-1的位置，size是数组元素的个数，减一就是指向最后的位置，代码实现如下
void SeqlistPushFront(SL* ps, SLDataType x)
{
SeqlistCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end; // 前置后置都可以
}
ps->a[0] = x;
ps->size++;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.头删函数：将后一个数据向前挪动，代码如下：
void SeqlistPopFront(SL* ps)
{
assert(ps->size > 0);
int begin = 1; //begin = 0
while (begin < ps->size) // size - 1
{
ps->a[begin - 1] = ps->a[begin]; // begin begin + 1
++begin;
}
ps->size--;
// 挪动数据
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
6.3 插入数据
插入数据首先我们应该考虑的是数组空间是否已满以及越界的问题，这里与上文一样有两种方法，我们还是采用断言的方法， 如图所示
代码如下：
void SeqlistInsert(SL* ps, int pos, SLDataType x) { /* if (pos > ps->size || pos < 0) 越界 { printf("pos invalid\n"); return; } */ //两种方法 assert(pos >= 0 && pos <= ps -> size); SeqlistCheckCapacity(ps); // 插入考虑扩容 int end = ps->size - 1; // 挪动数据 while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
事实上，我们在完成插入实现后可以将其应用在气脉你的数组的头插为尾插上面，这样我们就可以将代码改成这样：
void SeqlistPushFront(SL* ps, SLDataType x)
{
/* SeqlistCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end; // 前置后置都可以
}
ps->a[0] = x;
ps->size++;
*/
SeqlistInsert(ps, 0, x);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
像这样，对，没错的。
6.4 删除
删除思路与前面类似，如图
代码的实现如下
void SeqlistErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
6.5 查找
这个相对容易，我i们直接上代码：
int SeqlistFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
6.6 打印
void SeqlistPrint(SL* ps)
{
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
七、完整代码
这样，所有的代码我们基本已经实现了，下面是完整代码：
test.c
#include "Seqlist.h" void TestSeqlist1() { SL s1; SeqlistInit(&s1); SeqlistPushBack(&s1, 1); SeqlistPushBack(&s1, 2); SeqlistPushBack(&s1, 3); SeqlistPushBack(&s1, 4); SeqlistPushBack(&s1, 5); SeqlistPrint(&s1); SeqlistPopBack(&s1); SeqlistPopBack(&s1); SeqlistPrint(&s1); SeqlistDestory(&s1); } void TestSeqlist2() { SL s1; SeqlistInit(&s1); SeqlistPushBack(&s1, 1); SeqlistPushBack(&s1, 2); SeqlistPushBack(&s1, 3); SeqlistPushBack(&s1, 4); SeqlistPushBack(&s1, 5); SeqlistPrint(&s1); SeqlistPushFront(&s1, 10); SeqlistPushFront(&s1, 20); SeqlistPushFront(&s1, 30); SeqlistPrint(&s1); SeqlistPopFront(&s1); SeqlistPopFront(&s1); SeqlistPrint(&s1); SeqlistDestory(&s1); } void TestSeqlist3() { SL s1; SeqlistInit(&s1); SeqlistPushBack(&s1, 1); SeqlistPushBack(&s1, 2); SeqlistPushBack(&s1, 3); SeqlistPushBack(&s1, 4); SeqlistPushBack(&s1, 5); SeqlistPrint(&s1); SeqlistInsert(&s1, 2, 30); SeqlistPrint(&s1); int pos = SeqlistFind(&s1, 4); if (pos != -1) { SeqlistInsert(&s1, pos, 40); } SeqlistPrint(&s1); SeqlistDestory(&s1); } void TestSeqlist4() { SL s1; SeqlistInit(&s1); SeqlistPushBack(&s1, 1); SeqlistPushBack(&s1, 2); SeqlistPushBack(&s1, 3); SeqlistPushBack(&s1, 4); SeqlistPushBack(&s1, 5); SeqlistPrint(&s1); int pos = SeqlistFind(&s1, 3); if (pos != -1) { SeqlistErase(&s1, pos); } SeqlistPrint(&s1); SeqlistDestory(&s1); } enum { PushFront = 1, PopFront, PushBack, PopBack, Insert, Erase, Find, Print }; // 菜单 void Menu() { printf("*********************************\n"); printf("***** 请选择你的操作:> *****\n"); printf("***** 1、头插 2、头删 *****\n"); printf("***** 3、尾插 4、尾删 *****\n"); printf("***** 5、插入 6、删除 *****\n"); printf("***** 7、查找 8、打印 *****\n"); printf("***** -1、退出 *****\n"); printf("*********************************\n"); } int main() { //TestSeqlist1(); //TestSeqlist2(); //TestSeqlist3(); SL s1; SeqlistInit(&s1); // 初始化 int input = 0; int x; int pos = 0; while (input != -1) { Menu(); scanf("%d", &input); switch (input) { case PushFront: printf("请选择你要插入的数据，-1结束\n"); do { scanf("%d", &x); if (x != -1) { SeqlistPushFront(&s1, x); } } while (x != -1); break; case PopFront: SeqlistPopFront(&s1); break; case PushBack: printf("请选择你要插入的数据，-1结束\n"); do { scanf("%d", &x); if (x != -1) { SeqlistPushBack(&s1, x); } } while (x != -1); break; case PopBack: SeqlistPopBack(&s1); break; case Insert: printf("请选择你要插入的数据以及插入的位置，-1结束\n"); do { scanf("%d %d", &pos, &x); if (x != -1) { SeqlistInsert(&s1, pos, x); } } while (x != -1); break; case Erase: printf("请选择你要删除的数据，-1结束\n"); do { scanf("%d", &x); if (x != -1) { SeqlistErase(&s1, x); } } while (x != -1); break; case Find: printf("请选择你要查找的数据，-1结束\n"); do { scanf("%d", &x); if (x != -1) { printf("找到了，下标为%d\n", SeqlistFind(&s1, x)); } else { printf("没找到\n"); } } while (x != -1); break; case Print: SeqlistPrint(&s1); break; default: printf("无此选项，请重新选择\n"); break; } } SeqlistDestory(&s1); TestSeqlist4(); return 0; }
- 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
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
SeqList.c
#include "Seqlist.h" void SeqlistPrint(SL* ps) { for (int i = 0; i < ps->size; ++i) { printf("%d ", ps->a[i]); } printf("\n"); } void SeqlistInit(SL* ps) { ps->a = NULL; ps->size = ps->capacity = 0;// 初始化 } void SeqlistDestory(SL* ps) { free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; } void SeqlistCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;// 扩容 SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));// realloc算的是字节数 if (tmp == NULL) { printf("realloc fail\n"); exit(-1);// 这里return是不行的exit直接终止程序了 } ps->a = tmp; ps->capacity = newcapacity; } } void SeqlistPushBack(SL* ps, SLDataType x) // 尾插 { /* SeqlistCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; */ SeqlistInsert(ps, ps->size, x); } void SeqlistPopBack(SL* ps) { /* if (ps->size > 0) { //ps->a[ps->size - 1] = 0; 这个不要也没有问题 ps->size--; } */ // 方法一 assert(ps->size > 0); //为真继续，为假即<=0就会终止程序，并说明断言失败 ps->size--; } void SeqlistPushFront(SL* ps, SLDataType x) { /* SeqlistCheckCapacity(ps); // 挪动数据 int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; --end; // 前置后置都可以 } ps->a[0] = x; ps->size++; */ SeqlistInsert(ps, 0, x); } void SeqlistPopFront(SL* ps) { assert(ps->size > 0); int begin = 1; //begin = 0 while (begin < ps->size) // size - 1 { ps->a[begin - 1] = ps->a[begin]; // begin begin + 1 ++begin; } ps->size--; // 挪动数据 } int SeqlistFind(SL* ps, SLDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; } void SeqlistInsert(SL* ps, int pos, SLDataType x) { /* if (pos > ps->size || pos < 0) 越界 { printf("pos invalid\n"); return; } */ //两种方法 assert(pos >= 0 && pos <= ps -> size); SeqlistCheckCapacity(ps); // 插入考虑扩容 int end = ps->size - 1; // 挪动数据 while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; } void SeqlistErase(SL* ps, int pos) { assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; }
- 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
SeqList.h
#pragma once #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> // #define N 1000 typedef int SLDataType; // 动态顺序表 typedef struct Seqlist { SLDataType* a; int size;// 表示数组中存储了多少”个“数据 int capacity; // 数组实际能存储数据的空间容量是多大 }SL; // 静态特点：如果满了就不让插入 缺点：无法确定多少合适 // N给小了不够用， N给打了浪费 // //接口函数 -- 命名风格是跟着STL走的 void SeqlistPrint(SL* ps);// 打印顺序表 void SeqlistInit(SL* ps);// 初始化顺序表 void SeqlistDestory(SL* ps);// 将顺序表销毁 void SeqlistCheckCapacity(SL* ps);// 检查数据增容 void SeqlistPushBack(SL* ps, SLDataType x); //尾插 void SeqlistPopBack(SL* ps); //尾删 void SeqlistPushFront(SL* ps, SLDataType x); // 头插 void SeqlistPopFront(SL* ps); // 头删 int SeqlistFind(SL* ps, SLDataType x);// 查找这个值的位置，找到了返回X下标位置，没有返回-1 void SeqlistInsert(SL* ps, int pos, SLDataType x);//在指定pos下标位置插入 void SeqlistErase(SL* ps, int pos);//删除pos位置的数据
- 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
八、总结
关于顺序表的介绍就到这里了。可以说顺序表虽然按照顺序存储有它自己的优势，但这种特性又给它带来了麻烦，例如说O（N） 啥的，在增删过程中效率的不高等等。
在今后的文章中我也给大家准备了很多我个人原创的文章以及见解（有很多我不理解的地方欢迎大家在评论区告诉我） 。期待的话请多多为我投票吧（bushi) ，搞错了，期待的话请给我一键三连吧。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/474634
推荐阅读
相关标签
