-
超详细的数据结构---顺序表的有关教程
顺序表：
用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，
元素之间的关系有存储单元的邻接关系来体现。二者之间关系如下图所示：
对于元素内存空间的分配，我们早在C语言中学过，它有两种方式，一种是静态分配内存空间，也就是通过数组的形式，指定数组的长度，那么就相当于指定了内存空间的大小，往往这种情况都是存在于我们知道元素的个数，但很多时候我们并不知道要存放数据的多少，此时就需要使用动态内存分配了。下面我们通过学习来体会不同分配方式的差异：
首先我们来看静态分配的方式：
顺序表的实现-----静态分配：
但是静态分配存在一定的局限性！静态分配的缺点：
原因：
int data[Maxsize];- 1
上述这种用静态数组存放数据元素，这里的Maxsize一旦设置好是不能改变的，因此，如果当数组元素放满了之后，只能拜拜了，因为存储空间是静态的，无法被改变。
既然我们“怕存满”，那为什么不直接在设置长度的时候设置一个超大的呢？
这样根本就不怕，enmmm,确实是空间足够大了，但是你不觉得这样很浪费？假设你在设置长度的时候给定的长度为10000，结果你实际只用了10，这样就浪费了一大块的存储空间啊，所以还是好好继承中华传统美德“节约光荣，浪费可耻”。由此我们可得出一个结论：静态分配具有很大的局限性，因为容量是固定不变的。
对此，C语言给出了另一种分配方式，动态分配方式：顺序表的实现-----动态分配：
C语言规定了动态空间的申请函数malloc和释放该空间的函数free，他们所包含的头文件#include
malloc函数：
功能：分配所需的连续内存空间
free函数：
free 函数没有返回值，它的功能是释放指针变量 data所指向的内存单。此时data所指向的那块内存单元将会被释放并还给操作系统，不再归它使用。
操作系统可以重新将它分配给其他变量使用，但释放并不是指清空内存空间，而是指将该内存空间标记为 “可用”状态，使操作系统在分配内存时可以将它重新分配给其他变量使用。
注：
只有动态创建的内存才能用 free 把它释放掉，静态内存是不能用free释放的。静态内存只能由系统释放。如果此时出现了上述静态分配中出现的问题，数组存满了，该怎么办呢？
此时我们可以使用Increasesize(SeqList &L, int len)函数。Increasesize函数：
该函数的功能是把已有元素的数组赋值给新建的int *p。自己再从新开辟一片能够存下原来的值和新增加的长度的空间。
此时L.data是为没有元素的，下面进行循环遍历把旧的元素给赋值过来。还剩下给新的元素留下的空间地址。这样就实现了动态分配了。
用代码实现：
#include#include #define Initsize 10 ---snip--- void Inicreasesize(SeqList& L, int len) { int* p = L.data;//将扩充前的数据赋值给新的指针P L.data = (int*)malloc(sizeof(int) * (L.Maxsize + len));//扩宽顺序表的长度 for (int i = 0; i < L.length; i++)//实现原数据的复制 { L.data[i] = p[i]; } L.Maxsize = L.Maxsize + len;//将最大长度修改为扩宽后的长度 free(p);//释放内存空间 } int main() { SeqList L; InitList(L); Inicreasesize(L, 5); } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
分析过程如下：
关于静态/动态分配的有关知识点,大家可以移步C语言专栏！这里我们要讲的重点为顺序表的实现：
对顺序表的实现，选用动态分配的方式大体上和静态的分配方式一致，只是初始化会不一样，并且动态增加了一个可以增加空间的方法：
顺序表的定义：
//动态方式 typedef struct { int* data;//使用指针 int length; int MAXSize; }Seqlist;- 1
- 2
- 3
- 4
- 5
- 6
//静态方式 typedef struct { int MAXSize; int data[Inistsize];//使用数组 int length; }Seqlist;- 1
- 2
- 3
- 4
- 5
- 6
顺序表的初始化：
//动态方式 void InistList(Seqlist &L) { L.data = (int*)malloc(Inistsize * sizeof(int));//向内存申请定义的长度的整形变量的内存空间 L.MAXSize = Inistsize; L.length = 0; }- 1
- 2
- 3
- 4
- 5
- 6
//静态方式 void InistList(Seqlist &L) { for (int i = 0; i < Inistsize; i++) {//为数组设置初始化数据 L.data[i] = 0; } L.MAXSize = Inistsize; L.length = 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
看到这里，有些小伙伴可能会觉得为数组设置初始化数据这一步骤多次一举，那么它到底有什么用呢？
下面我们就来学习设置初始值的重要性：
设置数据元素默认值的重要性：
设置的：
#include#define Maxsize 10 typedef struct { int data[Maxsize]; int length; }SqList; void InitList(SqList &L) { for (int i = 0; i < Maxsize; i++) { L.data[i] = 0;//初始化顺序表：设置数据元素的默认值 } L.length = 0;//顺序表中最开始没有任何数据，因此长度为0 } int main() { SqList L;//声明顺序表 InitList(L);//初始化顺序表 for (int i = 0; i < Maxsize; i++) { printf("data[%d]=%d\n", i, L.data[i]); } 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
输出如下：
将设置默认值的代码删去：输出如下：
出现这些数据的原因即为我们进行初始化顺序表之后，系统为其开辟了一段空间，但由于我们对其中的值并没有设置默认值，这块空间之前存有的数据还保留在这个空间中。但其实我们所编写的main函数也是有问题的：
//尝试“违规打印整个data数组” for (int i = 0; i < Maxsize; i++) { printf("data[%d]=%d\n", i, L.data[i]); }- 1
- 2
- 3
- 4
- 5
违规的原因在于Maxsize是顺序表的最大长度，并不是当前长度，那有的小伙伴会说，既然用不了Maxsize,那么L.length总可以吧？其实也不可以，不信你替换成L.length你会发现程序是没有任何输出的,因为我们不应该访问大于顺序表实际长度的元素。
最好的做法就是使用我们上篇文章所讲的基本操作中的GetElem（L,I）进行访问，选用这种正确的方法，把各个数据元素的值设为默认值这一步骤就可以省略了。
但是L.length=0（将顺序表的长度初始化为0），这一步骤可不能省略哦，和上面的原因相同，内存为顺序表开辟的这一块空间，你并不知道之前存放了什么样的数据。
直接放图会比较好理解：
相信不少学过C语言的同学会有这样的疑问，那在C语言中为什么我没有设定初始值，系统就会默认给初始值为0呢？实际上做这个初始化工作的是编译器，你在VS编译器下系统会帮你进行初始化，但并不是所有的编译器都像VS那么暖心，因此我们还是自己操作吧。搞懂了这个之后，我们下面进入顺序表基本操作的学习：元素的写入：
动态静态分配的操作方法相似！//将元素写入 void writelist(Seqlist& L) { printf("请输入你要创建的线性表长度：");//注意这里不要超过最大长度（Inistsize） scanf_s("%d", &L.length); for (int i = 0; i < L.length; i++) { printf("请输入位序为%d个元素：", i + 1); scanf_s("%d", &L.data[i]); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
插入操作：
基本思路：
先判断顺序表是否存满？
满了？拒绝插入。
没满？进行插入---->将插入位序后面的元素依次向后移动一个位置。void Insertlis(Seqlist& L) { int i, x; printf("请输入要插入的位序和元素："); scanf("%d,%d", &i, &x); if (L.length > L.MAXSize) { printf("该顺表已存放满"); } else if (i<1 || i>L.length)//位序从1开始 printf("错误"); else { for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; } } L.data[i - 1] = x; L.length++; printf("元素插入成功!\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
假设，数组中的元素为5个，现在我们想实现在位序为3的位置插入一个数字。
那么内存中的空间分配。如下图所示：
通过for循环所实现的插入思想：for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; } } L.data[i - 1] = x; L.length++;- 1
- 2
- 3
- 4
- 5
- 6
- 7
j的初始值为L.length，L.length是长度，而j是下标，还是上述实例，此时顺序表长度为5，j=5,假设我们插入的位序为3。
那么循环过程如下：
第一次：
将第5个元素移至第6个空间：
第二次：将第4个元素移至第5个空间：
第三次：将第3个元素移至第4个空间：
需要提醒的是：1：这里for循环的判断部分必须是：
j>=i而不能是j>i,因为你要插入的位序为i,只有通过L.data[j] = L.data[j - 1];这个操作才能将位序为3的位置空间腾出来。2:一定是让变量j的初始值为最后一个元素+1的下标，而不是要插入的位序的下标，原因是，如果j初始为要插入的位序，那么后面会导致数据覆盖，也就是，位序为3的位置是空出来了，但是位序为4的数据被位序为3的数据覆盖了，后面亦是如此。所以
移动的方向一定是后面的数据先移动。3：下标和位序的差值为1，那么最终元素存放的位置是下标为i-1的位置
4：顺表表长度不要忘记++
插入操作的时间复杂度：
要求时间复杂度，就要关注深层循环语句的执行次数与问题规模n的关系（这里不懂得同学移步至时间复杂度那篇文章）
而对于我们上述这个代码来说，时间复杂度和表长有关，原因是在插入的过程中，表中的元素需要不停的进行移动，而表长恰恰决定了循环的次数。
分析如下：
最好时间复杂度：新元素插入到表尾，不需要移动元素，i=n+1,循环0次时间复杂度:T=O（1）
最坏时间复杂度：新元素插入到表头，所有的元素都要进行移动，i=1,时间复杂度:T=O(n)
平均时间复杂度：新元素插到任何一个位置的概率相同，即i=1,2,3,4,length的概率都是p=1/n+1,i=1（插入表头）,循环n次，i=2，（插入到位序为2）循环n-1次…i=n+1,循环0次（插入表尾）
平均循环次数：=np+(n-1)p+(n-2)p+…+1*p=[n(n+1)/2]*1/n+1=(n/2)=O(n)顺序表删除操作：
基本思路：
先判断顺序表是否为空？
空？拒绝删除。
非空？进行删除---->将删除位序后面的元素依次向前移动一个位置。void deletelist(Seqlist& L) { if (L.length == 0) { printf("当前表为空！"); } else { int i; printf("请输入要删除的位序:"); scanf("%d", &i); if (i<1 || i>L.length) { printf("您的输入有误！"); } else { for (int j = i - 1; j < L.length - 1; j++) { L.data[j] = L.data[j + 1]; } L.length--; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
j的初始值为L.length，L.length是长度，而j是下标，还是上述实例，此时顺序表长度为5，j=5,假设我们删除的位序为3。
j=i-1(j=3-1),这里还是因为下标/位序的差值为1for (int j = i - 1; j < L.length - 1; j++)//找到要删除元素 {//相当于依次覆盖数据，类比插入操作所提到的数据覆盖 L.data[j] = L.data[j + 1];//将它后面的元素向前挪动一位 }- 1
- 2
- 3
- 4
顺表表长度不要忘记--删除操作的时间复杂度：
和插入操作一样，同样需要关注深层循环语句的执行次数与问题规模n的关系
最好时间复杂度：删除表尾元素，不需要移动其他的元素，i=n,循环0次，此时时间复杂度为：T=O(1)
最坏时间复杂度：删除表头元素，所有的元素都需要发生移动，i=1,循环n-1次，此时时间复杂度为T=O(n)
平均时间复杂度：假设删除任何一个元素的概率相同，即i=1,2,3,…,length的概率都是p=1/n,i=1,（删除表头元素）循环n-1次，i=2（删除位序为2的元素）,循环n-2次…i=n（删除表尾元素）,循环0次
平均循环次数=（n-1）p+(n-2)p+…+1*p=[n(n-1)/2]*1/n=(n-1)/2=O(n)删除某元素后，其后面的元素移动先后顺序是：位序在前的先进行移动。
插入某元素后，其后面的元素移动先后顺序是：位序在后的先进性移动。其他的操作，查找，销毁，求表长等比较简单的思想操作这就就不单列来讲啦，需要注意的点，我已放在文章最后的完整代码中，使用注释标注出来啦。
顺序表的按位查找时间复杂度：
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素----“随机存取”特性，因此它的时间复杂度为O（1）
顺序表的按值查找时间复杂度：
分析如下：
最好时间复杂度：目标元素在表头，循环一次：时间复杂度为O（1）
最坏时间复杂度：目标元素在表尾，循环n次，时间复杂度为O（n）
平均时间复杂度：假设目标元素出现在任何一个位置的概率相同，都是1/n,那么当目标元素在表头，循环一次，在第二位，循环两次，以此类推，
平均循环次数=11/n+21/n+…+n*1/n=[[n(n+1)]/2]*1/n=(n+1)/2
平均复杂度=O（n）动态存储完整代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #define Inistsize 10 typedef struct { int *data; int length; int MAXSize; }Seqlist; //顺序表的初始化 void InistList(Seqlist &L) { L.data = (int*)malloc(Inistsize * sizeof(int)); L.MAXSize = Inistsize; L.length = 0; } //将元素写入 void writelist(Seqlist& L) { printf("请输入你要创建的线性表长度："); scanf_s("%d", &L.length); for (int i = 0; i < L.length; i++) { printf("请输入位序为%d个元素：", i + 1); scanf_s("%d", &L.data[i]); } } //插入操作 void Insertlis(Seqlist& L) { int i, x; printf("请输入要插入的位序和元素："); scanf("%d,%d", &i, &x); if (L.length > L.MAXSize) { printf("该顺表已存放满"); } else if (i<1 || i>L.length) printf("错误"); else { for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; } } L.data[i-1] = x; L.length++; printf("元素插入成功!\n"); } //删除顺序表 void deletelist(Seqlist& L) { if (L.length == 0) { printf("当前表为空！"); } else { int i; printf("请输入要删除的位序:"); scanf("%d", &i); if (i<1 || i>L.length) { printf("您的输入有误！"); } else { for (int j = i - 1; j < L.length - 1; j++) { L.data[j] = L.data[j + 1]; } L.length--; } } } //查找 void Findlist(Seqlist& L) { if (L.length == 0) { printf("当前顺序表为空！"); } else { int i; printf("请输入你要查找的元素位序："); scanf("%d", &i); if (i > L.length || i < 1) { printf("您的输入有误！"); } else { printf("您查找的位序元素为："); printf("%d\n", L.data[i - 1]); } } } //按值查找某元素 void searchlist(Seqlist& L) { if (L.length == 0) { printf("当前顺序表为空！"); } else { int x,k=1//使用变量p来标记是否查找到元素 printf("请输入你要查找的元素："); scanf("%d", &x); for (int i = 0; i < L.length; i++) { if (L.data[i] == x) { printf("找到啦，该元素的位序为%d\n", i + 1); k = 0;//找到啦，将变量k置为0，下面的printf语句不再执行 } } if(k) printf("该顺序表不存在该元素\n"); } } //输出顺序表 void Printlist(Seqlist& L) { printf("当前顺序表中的元素为:"); for (int i = 0; i <L.length; i++) { printf("%d", L.data[i]); } printf("\n"); } //求表长 void lenlist(Seqlist& L) { if(L.length==0) { printf("该表为空表！"); } else { printf("该顺序表的表长为：%d",L.length); } } //销毁顺序表 void Destorylist(Seqlist& L) { printf("你是否要销毁顺序表？Y/N"); char x; getchar(); scanf("%c", &x); if (x == 'Y') { L.length = 0; L.MAXSize = 0; free(L.data); } printf("顺序表已经销毁！"); } int main() { Seqlist L; InistList(L); writelist(L); Insertlis(L); Printlist(L); deletelist(L); Printlist(L); Findlist(L); Printlist(L); searchlist(L); lenlist(L); Destorylist(L); } - 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
输出：
静态存储完整代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #define Inistsize 5 typedef struct { int MAXSize; int data[Inistsize]; int length; }Seqlist; //顺序表的初始化 void InistList(Seqlist &L) { for (int i = 0; i < Inistsize; i++) { L.data[i] = 0; } L.MAXSize = Inistsize; L.length = 0; } //将元素写入 void writelist(Seqlist& L) { printf("请输入你要创建的线性表长度："); scanf_s("%d", &L.length); for (int i = 0; i < L.length; i++) { printf("请输入位序为%d个元素：", i + 1); scanf_s("%d", &L.data[i]); } } //插入操作 void Insertlis(Seqlist& L) { int i, x; printf("请输入要插入的位序和元素："); scanf("%d,%d", &i, &x); if (L.length > L.MAXSize) { printf("该顺表已存放满"); } else if (i<1 || i>L.length) printf("错误"); else { for (int j = L.length; j >= i; j--) { L.data[j] = L.data[j - 1]; } } L.data[i-1] = x; L.length++; printf("元素插入成功!\n"); } //删除顺序表 void deletelist(Seqlist& L) { if (L.length == 0) { printf("当前表为空！"); } else { int i; printf("请输入要删除的位序:"); scanf("%d", &i); if (i<1 || i>L.length) { printf("您的输入有误！"); } else { for (int j = i - 1; j < L.length - 1; j++) { L.data[j] = L.data[j + 1]; } L.length--; } } } //查找 void Findlist(Seqlist& L) { if (L.length == 0) { printf("当前顺序表为空！"); } else { int i; printf("请输入你要查找的元素位序："); scanf("%d", &i); if (i > L.length || i < 1) { printf("您的输入有误！"); } else { printf("您查找的位序元素为："); printf("%d\n", L.data[i - 1]); } } } //按值查找某元素 void searchlist(Seqlist& L) { if (L.length == 0) { printf("当前顺序表为空！"); } else { int x,k=1; printf("请输入你要查找的元素："); scanf("%d", &x); for (int i = 0; i < L.length; i++) { if (L.data[i] == x) { printf("找到啦，该元素的位序为%d\n", i + 1); k = 0; } } if(k) printf("该顺序表不存在该元素\n"); } } //输出顺序表 void Printlist(Seqlist& L) { printf("当前顺序表中的元素为:"); for (int i = 0; i <L.length; i++) { printf("%d", L.data[i]); } printf("\n"); } //求表长 void lenlist(Seqlist& L) { if(L.length==0) { printf("该表为空表！"); } else { printf("该顺序表的表长为：%d",L.length); } } //销毁顺序表 void Destorylist(Seqlist& L) { printf("你是否要销毁顺序表？Y/N"); char x; getchar(); scanf("%c", &x); if (x == 'Y') { L.length = 0; L.MAXSize = 0; free(L.data); } printf("顺序表已经销毁！"); } int main() { Seqlist L; InistList(L); writelist(L); Insertlis(L); Printlist(L); deletelist(L); Printlist(L); Findlist(L); Printlist(L); searchlist(L); lenlist(L); /*Destorylist(L);*/ } - 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
输出：
顺序表的特点：
1：随机访问：可实现在O(1)【常数级】时间内找到第i个元素，这也得益于它的按顺序存储的特点。
代码实现方法：data[i-1]2:存储密度高，每个节点只存储数据元素。
相比于链式存储模式，既存放数据元素还存放对应的指针来说，顺序存储模式只存储数据元素。
3：拓展容量不方便（静态分配直接就是不能拓展容量，虽然动态分配可以拓展，但是拓展长度的时间复杂度也比较高）
4：插入，删除操作不方便，需要移动大量元素，这个特点也是和顺序存储模式有关
-
相关阅读:
基于Python实现语法分析
将 Ordinals 与比特币智能合约集成：第 4 部分
vue项目开发环境工具-node
基于web的医院预约挂号系统/医院管理系统
基于springboot+vue的大学生科创项目在线管理系统
2023秋招大厂经典面试题及答案整理归纳（341-360）校招必看【Linux篇】
CICD 持续集成与持续交付——git
创新案例分享 | 建立校园大数据治理评价平台，高效提高教学效率与质量
强大CSS3可视化代码生成器
从0开始的C语言入门教程day2（完结，让你0基础两天学会C语言）
- 原文地址：https://blog.csdn.net/m0_64365419/article/details/127418126