-
【数据结构】顺序表的概念及实现
1、顺序表概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采取数组存储。在数组上完成数据的增删查改。
顺序表一般可分为：
1.静态顺序表：使用定长数组存储元素。如下：//静态的顺序表，存储的数据是固定的，N个 #define N 10 typedef int SLDataType; typedef struct SeqList { SLDataType a[N]; //定长数组 int size; //存储数据的个数 }SL;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
1.如代码所示，这个顺序表最多只能存储十个元素，也就是说当想要存储的元素超过十个时，这个结构没有办法进行存储。
2.动态顺序表
typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size; //存储数据的个数 int capacity; //顺序表的容量 }SL;- 1
- 2
- 3
- 4
- 5
- 6
- 7
1.结构体中用了一个整形的指针指向一个动态开辟的存储空间（数组），因此这块空间可以扩大，一旦存储空间不够了，可以随时扩容。
2.这个表示顺序表的结构体中还定义了用来表明顺序表当前存储元素的个数size，和顺序表总的容量capacity。2、初始化顺序表
//初始化函数 void SLInit(SL* psl) { assert(psl); psl->a = NULL; psl->capacity = psl->size = 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
1.当顺序表为空的时候，也就意味着还没有动态开辟空间，将指向动态开辟空间的指针置空。
2.顺序表中的元素个数和总的容量此时也为零。3、销毁顺序表
//销毁函数 void SLDestory(SL* psl) { assert(psl); if (psl->a) //销毁顺序表，要保证顺序表不为空 { free(psl->a); psl->a = NULL; psl->capacity = psl->size = 0; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
1.要销毁顺序表说明顺序表中有数据，即销毁顺序表时，要保证顺序表不为空。
2.直接将指向动态开辟的这块存储空间free掉，置为空，当前存储元素个数和总的容量设为0，顺序表也就被销毁了。4、判断顺序表是否为空
//判空函数 bool SLEmpty(SL* psl) { assert(psl); return psl->size == 0; }- 1
- 2
- 3
- 4
- 5
- 6
1.如果顺序表存储的元素个数为0的话，为真，返回的是非零，如果不等于的话，为假，返回的是0。
5、打印顺序表
//打印函数 void SLPrintf(SL* psl) { assert(psl); assert(!SLEmpty(psl)); int i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
1.顺序表是由数组构成的，依次照着数组重头打到尾，顺序表中的元素也就打印出来了。
2.打印顺序表首先要判断顺序表是否为空，因此调用第四节的判空函数。6、检查顺序表的容量（同时充当扩容任务）
当用顺序表存储数据时，即往顺序表中插入数据，要先判断顺序表当前总的容量是否已经被塞满了，如果被塞满了就需要扩容。
//检查容量 void SLCheckCapacity(SL* psl) { assert(psl); if (psl->size == psl->capacity) { int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapacity * sizeof(SLDataType)); if (tmp == NULL) { perror("ralloc fail"); exit(-1); } psl->a = tmp; psl->capacity = newCapacity; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 如何判断顺序表已经满了？
答:当前存储数据的个数与顺序表的总容量相等时，说明顺序表已经满了。 - 顺序表满了有两种情况，第一种情况是顺序表中存储的元素真的满了，第二种情况是顺序表为空的情况。
- 当顺序表为空时，给顺序表动态开辟四个整型空间的容量，当顺序表不为空又真的满了时，给顺序表动态开辟原先容量两倍的空间。
7、顺序表的尾插
//尾插 void SLPushBack(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); psl->a[psl->size] = x; psl->size++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
1.尾插之前检查顺序表的容量，容量不够了直接扩容。
2.因为顺序表是数组构成的，所以顺序表尾插，直接将要插入的数放在数组最后即可，插入完后，表示顺序表存储个数的size加一。8、顺序表的头插
//头插 void SLPushFront(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); //挪动数据，从后往前挪 int end = psl->size - 1; while (end >= 0) { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x; psl->size++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
1.顺序表要插入数据首先检查顺序表的容量。
2.顺序表是数组，所以头插时，并不能在数组前面再开辟一个空间用来放入新的数据。要实现顺序表的头插只能将数组中的数据一个一个往后移动，第一个位置空出来，才能将数据放入首位置。
头插数据，挪动数据时要从后面的数据开始挪起，如果从前面的数据开始挪起，后面的数据就会被覆盖。在主函数中调用头插函数
void TestSeqList1() { SL s; SLInit(&s); SLPushFront(&s, 8); SLPushFront(&s, 6); SLPushFront(&s, 5); SLPushFront(&s, 4); SLPrintf(&s); SLPushFront(&s, 12); SLPrintf(&s); } int main() { TestSeqList1(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
打印结果
9、顺序表的尾删
//尾删 void SLPopBack(SL* psl) { assert(psl); assert(!SLEmpty(psl)); //顺序表为空时，不能再删除了 psl->size--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
1.只要将数组下标减一，顺序表的尾访问不到，那么就相当于将顺序表的尾删掉了。
2.尾删顺序表的时候要判断顺序表是否为空，如果为空，这不能再删了。在主函数中调用顺序表的尾删
void TestSeqList2() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPrintf(&s); SLPushFront(&s, 8); SLPrintf(&s); SLPopBack(&s); SLPopBack(&s); SLPopBack(&s); SLPrintf(&s); SLPopBack(&s); SLPrintf(&s); SLPopBack(&s); } int main() { TestSeqList2(); 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
打印结果
1.之前插入的数据被一一的尾删到只剩8，将8删除后再进行打印，打印程序段出现报错，因为此时此时已无数据打印。10、顺序表的头删
//头删 void SLPopFront(SL* psl) { assert(psl); assert(!SLEmpty(psl)); //顺序表为空时，不能再删除了 //挪动数据，从前往后挪 int cur = 0; while (cur < psl->size-1) { psl->a[cur] = psl->a[cur + 1]; cur++; } psl->size--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
1.数组中后面的数据依次往前挪，将数组中第一个数据覆盖，顺序表就相当于头删了。
顺序表头删时，往前挪需要先挪前面的，如果从最后开始挪的话，前面的数据会被覆盖掉。11、查找顺序表中某个数的位置
查找顺序表中某个数的位置，找了返回这个数据的下标，找不到返回-1。
//查找某个数在顺序表中的位置，并且返回它的下标,没有找到就返回-1 int SLFind(SL* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return - 1; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
1.遍历整个顺序表，将要找的数与顺序表中数一一比对，相等则说明找到了，返回这个数在数组中的下标。
2.遍历完了还没找到相等的数，说明要找的数在顺序表不存在，返回-1。在主函数中调用
TestSeqList3() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPushBack(&s, 12); SLPushBack(&s, 15); SLPushBack(&s, 18); SLPrintf(&s); int a = SLFind(&s, 6); printf("%d\n", a); } int main() { TestSeqList3(); 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
打印结果
在顺序表中查找数字6，在数组的第二位被找到，返回他在数组中的下标1。（并且将下标打印了出来）12、在顺序表pos位置插入数字x
//顺序表在pos位置插入x void SeqListInsert(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos <= psl->size); //等于时即是尾插 SLCheckCapacity(psl); //检查容量 挪动数据 //size_t end = psl->size - 1; //while (end >= pos) //{ // psl->a[end + 1] = psl->a[end]; // --end; //} //挪动数据 size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end - 1]; --end; } psl->a[pos] = x; ++psl->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
1.顺序表是由数组构成的，数组在物理地址上是连续的，插入时，只能在与数组中相连的地方插入（即头插、尾插、数组中间插入），因此要保证插入的pos位置是小于等于数组最后一个下标的。
2.从最后一个数开始，依次往后挪动，直到挪到pos位置，此时在pos位置插入本来要插入的数。插入完后，将顺序表中表示当前存储数据个数的size加一。
3.上述代码被“注释”掉的是一种又缺陷的写法。当pos为0时候，即头插，此时end==0，进入循环，移动完毕后，end–，end变为-1，因为end为size_t类型（无符号类型），无符号数-1>0,所以还会再次进入循环，形成死循环。
4.头插与尾插都可以在接口中直接调用这段代码。在主函数中调用
TestSeqList4() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPushBack(&s, 12); SLPrintf(&s); int x = 0; scanf("%d", &x); int pos = SLFind(&s, x); if (pos != -1) { SeqListInsert(&s, pos, x*100); } SLPrintf(&s); } int main() { 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
打印结果
1.在pos位置插入首先要找到pos位置，比如在数字9的位置插入，首先要找到数字9的位置
2.在9的位置插入，输入9，此时在这里插入了一个9×100的数，900。13、删除顺序表中pos位置的值
//顺序表删除pos位置的值 void SeqListErase(SL* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t begin = pos; while (begin < psl->size - 1) { psl->a[begin] = psl->a[begin + 1]; ++begin; } psl->size--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
1.删除顺序表中pos位置的值，首先要确保pos位置是存在于数组下标中的，即pos < psl->size；
2.从pos位置开始，将pos位置的后面的数依次往前挪，将pos位置的数覆盖掉，这样就像与将pos位置的数删除掉了。
3.挪动数据时，不能从数组中最后一个数开始往前挪，因为这样的话，pos位置与数组尾部中间的数还没开始挪就被覆盖掉了。在主函数中调用
TestSeqList5() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPushBack(&s, 12); SLPrintf(&s); int x = 0; scanf("%d", &x); int pos = SLFind(&s, x); if (pos != -1) { SeqListErase(&s, pos); } SLPrintf(&s); } int main() { TestSeqList5(); 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
打印结果
1.输入要删除的数，例如9，删除这个数首先要找到这个数在数组中的位置。
2.头删与尾删都可以在接口中直接调用这段代码。14、顺序表全部代码
SeqList.h头文件部分：包含了库函数的头文件以及自定义函数的声明
#pragma once #include#include #include #include 静态的顺序表，存储的数据是固定的，N个 //#define N 10 //typedef int SLDataType; //typedef struct SeqList //{ // SLDataType a[N]; //定长数组 // int size; //存储数据的个数 //}SL; //动态的顺序表 #define N 10 typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size; //存储数据的个数 int capacity; //顺序表的容量 }SL; //初始化 void SLInit(SL* sl); //销毁顺序表 void SLDestory(SL* sl); //打印顺序表 void SLPrintf(SL* psl); //顺序表判空函数 bool SLEmpty(SL* pSL); //头插头删 尾插尾删 //尾插 void SLPushBack(SL* psl, SLDataType x); //头插 void SLPushFront(SL* psl, SLDataType x); //尾删 void SLPopBack(SL* psl); //头插 void SLPopFront(SL* psl); //查找某个数在顺序表中的位置，并且返回它的下标,没有找到就返回-1 int SLFind(SL* psl, SLDataType x); //顺序表在pos位置插入x void SeqListInsert(SL* psl, size_t pos, SLDataType x); //顺序表删除pos位置的值 void SeqListErase(SL* psl, size_t 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
- 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
SeqList.c部分：实现各自定义函数的功能
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" //初始化函数 void SLInit(SL* psl) { assert(psl); psl->a = NULL; psl->capacity = psl->size = 0; } //销毁函数 void SLDestory(SL* psl) { assert(psl); if (psl->a) //销毁顺序表，要保证顺序表不为空 { free(psl->a); psl->a = NULL; psl->capacity = psl->size = 0; } } //判空函数 bool SLEmpty(SL* psl) { assert(psl); return psl->size == 0; } //打印函数 void SLPrintf(SL* psl) { assert(psl); assert(!SLEmpty(psl)); int i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); } //检查容量 void SLCheckCapacity(SL* psl) { assert(psl); if (psl->size == psl->capacity) { int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapacity * sizeof(SLDataType)); if (tmp == NULL) { perror("ralloc fail"); exit(-1); } psl->a = tmp; psl->capacity = newCapacity; } } //尾插 void SLPushBack(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); psl->a[psl->size] = x; psl->size++; } //头插 void SLPushFront(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); //挪动数据，从后往前挪 int end = psl->size - 1; while (end >= 0) { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x; psl->size++; } //尾删 void SLPopBack(SL* psl) { assert(psl); assert(!SLEmpty(psl)); //顺序表为空时，不能再删除了 psl->size--; } //头删 void SLPopFront(SL* psl) { assert(psl); assert(!SLEmpty(psl)); //顺序表为空时，不能再删除了 //挪动数据，从前往后挪 int cur = 0; while (cur < psl->size-1) { psl->a[cur] = psl->a[cur + 1]; cur++; } psl->size--; } //查找某个数在顺序表中的位置，并且返回它的下标,没有找到就返回-1 int SLFind(SL* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return - 1; } //顺序表在pos位置插入x void SeqListInsert(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos <= psl->size); //等于时即是尾插 SLCheckCapacity(psl); //检查容量 挪动数据 //size_t end = psl->size - 1; //while (end >= pos) //{ // psl->a[end + 1] = psl->a[end]; // --end; //} //挪动数据 size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end - 1]; --end; } psl->a[pos] = x; ++psl->size; } //顺序表删除pos位置的值 void SeqListErase(SL* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t begin = pos; while (begin < psl->size - 1) { psl->a[begin] = psl->a[begin + 1]; ++begin; } psl->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
- 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
Test.c部分：主函数放在这，在主函数中调用个函数，在实现各函数时，可以用来测试各函数的功能。
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void TestSeqList1() { SL s; SLInit(&s); SLPushFront(&s, 8); SLPushFront(&s, 6); SLPushFront(&s, 5); SLPushFront(&s, 4); SLPrintf(&s); SLPushFront(&s, 12); SLPrintf(&s); } void TestSeqList2() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPrintf(&s); SLPushFront(&s, 8); SLPrintf(&s); SLPopBack(&s); SLPopBack(&s); SLPopBack(&s); SLPrintf(&s); SLPopBack(&s); SLPrintf(&s); SLPopBack(&s); } TestSeqList3() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPushBack(&s, 12); SLPushBack(&s, 15); SLPushBack(&s, 18); SLPrintf(&s); int a = SLFind(&s, 6); printf("%d\n", a); } TestSeqList4() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPushBack(&s, 12); SLPrintf(&s); int x = 0; scanf("%d", &x); int pos = SLFind(&s, x); if (pos != -1) { SeqListInsert(&s, pos, x*100); } SLPrintf(&s); } TestSeqList5() { SL s; SLInit(&s); SLPushBack(&s, 3); SLPushBack(&s, 6); SLPushBack(&s, 9); SLPushBack(&s, 12); SLPrintf(&s); int x = 0; scanf("%d", &x); int pos = SLFind(&s, x); if (pos != -1) { SeqListErase(&s, pos); } SLPrintf(&s); } int main() { TestSeqList5(); 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
-
相关阅读:
SCRAM authentication requires libpq version 10 or above
防止Android点击app图标应用重启
Apache——阿帕奇简介
Emgu CV4图像处理之ROI与mask掩码10(C#)
用A-Spice思路解读“西门庆和潘金莲的不可描述之事”，不信你看不懂
第三章 多维随机变量及其分布
2--OpenCV:图形基础
亚商投资顾问 早餐FM/0928 养老金抵扣个税优惠来了
RK3399平台开发系列讲解（内存篇）15.34、 Linux 进程内存布局
Ubuntu 22.04 搭建 KubeSphere 3.4.1 集群
- 原文地址：https://blog.csdn.net/weixin_44930735/article/details/128138773
