-
顺序表的实现
顺序表的概念及结构
顺序表是用一段 物理地址连续 的存储单元存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1.静态顺序表：使用定长数组存储。
2.动态顺序表：使用动态开辟的数组存储。静态 & 动态顺序表的特点
静态顺序表：使用定长数组存储数据，也就意味着存储的数据量是固定的，当需要存储的数据量很少时，会造成空间浪费；当存储的数据量很大时，可能空间会不够；
#define MAX 100 typedef int SLDataType; typedef struct SeqList { SLDataType a[MAX];//定长数组存储数据 size_t size;//数据个数 size_t capacity;//空间容量 }SeqList;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
动态顺序表：使用动态开辟的数组来存储数据，当空间不够时，便扩容。
typedef int SLDataType; typedef struct SeqList { SLDataType* a;//动态开辟数组存储数据 size_t size;//数据个数 size_t capacity;//顺序表容量 }SeqList;- 1
- 2
- 3
- 4
- 5
- 6
- 7
由于动态顺序表能够扩容的优点，之后的顺序表实现，都统一使用动态结构。
动态顺序表增删查改的接口函数
1.初始化顺序表
注意：
函数的参数必须使用指针形式，因为只有传址传递才能间接修改实参//顺序表的初始化 void SeqListInit(SeqList* psl) { assert(psl);//使用断言防止psl为空指针 //因为空指针解引用程序将会崩溃 psl->a = NULL; psl->capacity = psl->size = 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
SeqList sl; SeqListInit(&sl);- 1
- 2
2.销毁顺序表
1.销毁顺序表时，必须将动态申请的空间进行释放，否则将会出现内存泄漏。
2.并且把指向那段空间的指针置为空指针，否则它将会是一个野指针。//销毁顺序表 void SeqListDestory(SeqList* psl) { assert(psl);//使用断言防止psl为空指针 free(psl->a);//1 psl->a = NULL;//2 psl->capacity = psl->size = 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
3.打印顺序表
//打印顺序表 void SeqListPrint(SeqList* psl) { assert(psl && psl->a); for (int 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
4. 顺序表尾部插入数据
在进行插入数据前，需要先判断空间是否有剩余，如果空间满了，则需要扩容。
由于在初始化中并没有给定数组一块起始空间，所以在一开始插入数据时就需要进行扩容，并且需要给定一个起始空间大小。在扩容时，我们选择对原有空间翻二倍。//顺序表尾部插入数据 void SeqListPushBack(SeqList* psl, SLDataType val) { assert(psl); //判断是否需要扩容 check_capacity(psl); //尾部插入数据 psl->a[psl->size] = val; psl->size++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
一些问题的思考
为什么选择扩容二倍？
因为二倍是刚好合适的倍数，如果扩小了，那么当插入数据很多时，就要频繁的扩容，会导致性能的下降；如果扩大了，那么当插入数据不是很多时，可能造成空间的浪费。
既然有了扩容，那是否需要缩容
在c++库的顺序表中是没有缩容这个操作的，原因有二：
1.缩容这一操作是利用realloc来实现的，当需要缩容时，可能会在内存中重新寻找一块空间再将数据拷贝到那块空间上来实现缩容，这一操作是会损耗性能的
2.当需要重新插入数据时，又可能需要扩容，扩容时也有可能需要开辟一块新的空间，释放旧空间，这一操作也是需要消耗性能的。5. 对空间容量的检查
//对空间容量的检查 void check_capacity(SeqList* psl) { assert(psl); if (psl->capacity == psl->size) { int new_capacity = psl->capacity == 0 ? 4 : 2 * psl->capacity; //如果起始容量为0，那么就给定一个初始值 //如果不为0，则将原有容量翻倍 //扩容 SLDataType* tmp = (SLDataType*)realloc(psl->a, new_capacity * sizeof(SLDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1);//扩容失败，终止程序 } //扩容成功 psl->a = tmp; psl->capacity = new_capacity; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
6.顺序表头部插入数据
如果要在顺序表头部插入数据，则需要从后往前依次挪动数据，将头部位置空出来。
//顺序表头部插入数据 void SeqListPushFront(SeqList* psl, SLDataType val) { assert(psl); check_capacity(psl);//检查容量 //从后往前挪动数据 int end = psl->size - 1; while (end >= 0) { psl->a[end + 1] = psl->a[end]; //将数据依次挪动到后一个下标处 end--; } //头部插入数据 psl->a[0] = val; psl->size++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
7. 顺序表尾部删除数据
顺序表尾部删除数据，只需要让元素个数减一即可。
顺序表中无法做到真正删除一个数据，只能进行覆盖或者不把其归为顺序表中的内容
注意：如果元素个数少于1个，则不能进行删除，否则后续插入将会造成越界访问。//顺序表尾部删除数据 void SeqListPopBack(SeqList* psl) { assert(psl); //确保有数据可删 assert(psl->size > 0); psl->size--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
8.顺序表的头部删除数据
如果要对顺序表的头部删除数据，则需要从第二个元素起，从前往后将后续元素覆盖到前一个元素处。
//顺序表的头部删除数据 void SeqListPopFront(SeqList* psl) { assert(psl); assert(psl->size > 0); //从前往后挪动数据进行覆盖 int start = 0; while (start < psl->size - 1) { psl->a[start] = psl->a[start + 1]; start++; } psl->size--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
9.顺序表中查找元素下标
//顺序表中查找元素下标 int SeqListFind(SeqList* psl, SLDataType val) { assert(psl); assert(psl->size > 0); //遍历寻找 for (int i = 0; i < psl->size; i++) { if (psl->a[i] == val) { return i;//找到了返回当前下标 } } return -1;//表示没找到 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
10.顺序表在pos位置插入数据
注意：函数第二个参数是size_t（无符号整型），在挪动数据时，需要小心是否会出现负数判断条件
错误版本：
当在头部插入数据时，这个版本将会出现死循环，原因是：
end变量是一个无符号整型，当它等于0进入循环后再减减，将会变成-1，但无符号整型的-1是整型的最大值，循环将永远不会停止，并且会造成越界访问。//错误版本的插入数据 void SeqListInsert(SeqList* psl, size_t pos, SLDataType val) { assert(psl); check_capacity(psl); size_t end = psl->size - 1; while (end >= pos) { psl->a[end + 1] = psl->a[end]; end--; } psl->a[pos] = val; psl->size++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
正确版本：
//顺序表在pos位置插入数据 void SeqListInsert(SeqList* psl, size_t pos, SLDataType val) { assert(psl); check_capacity(psl); size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end-1];//将数组往后挪动 end--; } psl->a[pos] = val; psl->size++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
11.顺序表在pos位置删除数据
删除pos位置的数据，我们只需要将pos后面的数据依次往前挪动覆盖即可。
//顺序表在pos位置删除数据 void SeqListErase(SeqList* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t start = pos; while (start < psl->size - 1) { //从前往后挪动覆盖 psl->a[start] = psl->a[start + 1]; start++; } psl->size--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
12.对Insert 和Erase的复用
尾部插入数据
//顺序表尾部插入数据 void SeqListPushBack(SeqList* psl, SLDataType val) { assert(psl); //判断是否需要扩容 check_capacity(psl); //复用Insert SeqListInsert(psl, psl->size, val); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
头部插入数据
//顺序表头部插入数据 void SeqListPushFront(SeqList* psl, SLDataType val) { assert(psl); check_capacity(psl);//检查容量 //复用Insert SeqListInsert(psl, 0, val); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
尾部删除数据
//顺序表尾部删除数据 void SeqListPopBack(SeqList* psl) { assert(psl); assert(psl->size > 0); SeqListErase(psl, psl->size - 1); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
头部删除数据
//顺序表的头部删除数据 void SeqListPopFront(SeqList* psl) { assert(psl); assert(psl->size > 0); SeqListErase(psl,0); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
顺序表的全代码实现
test.c
#include"SeqList.h" //对顺序表尾部插入和t头部插入的测试 void SeqList_Test1() { SeqList s; SeqListInit(&s); //尾部插入 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPrint(&s); //对扩容的检查 SeqListPushBack(&s, 5); SeqListPrint(&s); //头部插入 SeqListPushFront(&s, 1); SeqListPushFront(&s, 2); SeqListPushFront(&s, 3); SeqListPushFront(&s, 4); SeqListPrint(&s); SeqListDestory(&s); } //对顺序表头部删除和尾部删除的检测 void SeqList_Test2() { SeqList s; SeqListInit(&s); //插入数据 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPrint(&s); //尾部删除数据 SeqListPopBack(&s); SeqListPopBack(&s); SeqListPrint(&s); //头部删除数据 SeqListPopFront(&s); SeqListPrint(&s); SeqListDestory(&s); } void SeqList_Test3() { SeqList s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListInsert(&s, 0, 2); SeqListPrint(&s); SeqListErase(&s, 2); SeqListPrint(&s); SeqListDestory(&s); } int main() { //SeqList_Test1(); SeqList_Test2(); //SeqList_Test3(); 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
SeqList.c
#include"SeqList.h" //顺序表的初始化 void SeqListInit(SeqList* psl) { assert(psl);//使用断言防止psl为空指针 //因为空指针解引用程序将会崩溃 psl->a = NULL; psl->capacity = psl->size = 0; } //销毁顺序表 void SeqListDestory(SeqList* psl) { assert(psl);//使用断言防止psl为空指针 free(psl->a); psl->a = NULL; psl->capacity = psl->size = 0; } //打印顺序表 void SeqListPrint(SeqList* psl) { assert(psl && psl->a); for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); } //对空间容量的检查 void check_capacity(SeqList* psl) { assert(psl); if (psl->capacity == psl->size) { int new_capacity = psl->capacity == 0 ? 4 : 2 * psl->capacity; //如果起始容量为0，那么就给定一个初始值 //如果不为0，则将原有容量翻倍 //扩容 SLDataType* tmp = (SLDataType*)realloc(psl->a, new_capacity * sizeof(SLDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1);//扩容失败，终止程序 } //扩容成功 psl->a = tmp; psl->capacity = new_capacity; } } //顺序表尾部插入数据 void SeqListPushBack(SeqList* psl, SLDataType val) { assert(psl); //判断是否需要扩容 check_capacity(psl); //尾部插入数据 //psl->a[psl->size] = val; //psl->size++; //复用Insert SeqListInsert(psl, psl->size, val); } //顺序表头部插入数据 void SeqListPushFront(SeqList* psl, SLDataType val) { assert(psl); check_capacity(psl);//检查容量 从后往前挪动数据 //int end = psl->size - 1; //while (end >= 0) //{ // psl->a[end + 1] = psl->a[end]; // end--; //} 头部插入数据 //psl->a[0] = val; //psl->size++; //复用Insert SeqListInsert(psl, 0, val); } //顺序表尾部删除数据 void SeqListPopBack(SeqList* psl) { assert(psl); assert(psl->size > 0); //psl->size--; //复用Erase SeqListErase(psl, psl->size - 1); } //顺序表的头部删除数据 void SeqListPopFront(SeqList* psl) { assert(psl); assert(psl->size > 0); //从前往后挪动数据进行覆盖 //int start = 0; //while (start < psl->size - 1) //{ // psl->a[start] = psl->a[start + 1]; // start++; //} //psl->size--; //复用Erase SeqListErase(psl,0); } //顺序表中查找元素下标 int SeqListFind(SeqList* psl, SLDataType val) { assert(psl); assert(psl->size > 0); //遍历寻找 for (int i = 0; i < psl->size; i++) { if (psl->a[i] == val) { return i;//找到了返回当前下标 } } return -1;//表示没找到 } //顺序表在pos位置插入数据 void SeqListInsert(SeqList* psl,size_t pos, SLDataType val) { assert(psl); check_capacity(psl); size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end-1]; end--; } psl->a[pos] = val; psl->size++; } //顺序表在pos位置删除数据 void SeqListErase(SeqList* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t start = pos; while (start < psl->size - 1) { psl->a[start] = psl->a[start + 1]; start++; } 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
- 176
SeqList.h
#pragma once #include#include #include typedef int SLDataType; typedef struct SeqList { SLDataType* a;//动态开辟数组存储数据 size_t size;//数据个数 size_t capacity;//顺序表容量 }SeqList; //顺序表增删查改的接口函数 //顺序表的初始化 void SeqListInit(SeqList* psl); //销毁顺序表 void SeqListDestory(SeqList* psl); //打印顺序表 void SeqListPrint(SeqList* psl); //顺序表尾部插入数据 void SeqListPushBack(SeqList* psl, SLDataType val); //顺序表头部插入数据 void SeqListPushFront(SeqList* psl, SLDataType val); //顺序表尾部删除数据 void SeqListPopBack(SeqList* psl); //顺序表的头部删除数据 void SeqListPopFront(SeqList* psl); //顺序表中查找元素下标 int SeqListFind(SeqList* psl, SLDataType val); //顺序表在pos位置插入数据 void SeqListInsert(SeqList* psl, size_t pos, SLDataType val); //顺序表在pos位置删除数据 void SeqListErase(SeqList* 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
-
相关阅读:
AI美颜SDK算法详解
javaIO流01：文件，创建文件三种方式，获取文件相关信息，目录操作
leetcode10--正则表达式
人工智能之机器学习
[答疑]《实现领域驱动设计》的译者其实没错?（一）
Java刷题面试系列习题(五)
安全狗受邀出席CIS 2022网络安全创新大会
好用的vscode插件
浅析ChatGPT中涉及到的几种技术点
【学习笔记】Redis的持久化
- 原文地址：https://blog.csdn.net/m0_64240499/article/details/126036880
