热门标签
热门文章
- 1javascript基本和常用的东西
- 2尝试在手机上运行google 最新开源的gpt模型 gemma
- 3apache-dolphinscheduler-3.2.0伪集群启动，采用mysql数据库_dolphinscheduler3.2.0伪集群部署
- 4自我摸索：如何运营并玩转CSDN？_如何运营csdn
- 5字节跳动应届生薪资都能2万+，年薪30万，这样工作真的开心吗？_字节离职率很高吗
- 6【基于遗传算法改进的粒子群GA-PSO算法优化shubert函数及MATLAB编程实现，测试函数shubert(十)
- 7怎样找回删除的照片？学会这4招，恢复超简单！_照片删除了怎么恢复回来
- 8基于FPGA的PCIe-Aurora 8/10音频数据协议转换系统设计阅读笔记_pcie aurora 收发工程
- 9红黑瓷砖（BFS和DFS）
- 10[Distributed Training]强化学习并行训练论文合集_ga3c: gpu-based a3c for deep reinforcement learnin
当前位置: article > 正文
数据结构之【顺序表的实现（详解）】_数据结构顺序表实现
作者：繁依Fanyi0 | 2024-04-15 09:46:35
赞
踩
数据结构顺序表实现
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，**常见的线性表：顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构，也就说是连续的一条直线。**但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表
本质就是一个数组，但它是动态增长的，并且要求里面存储的数据必须是从左往右连续的。
顺序表的物理结构和逻辑结构是一致的都是连续的。
顺序表存在着一定的缺陷：
1.0 动态增容存在性能消耗
2.0 需要头部插入数据，需要挪动数据
数据结构本质就是为了存储数据
顺序表的实现
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
- 静态顺序表：使用定长数组存储。
- 动态顺序表：使用动态开辟的数组存储。
静态的顺序表(相当于一个数组，数组长度固定的，存储有效个数据)
#define N 100
struct Seqlist
{
int a[N]; //定向数组
int size; //有效数据的个数
};
- 1
- 2
- 3
- 4
- 5
- 6
动态的顺序表
typedef int SeqDataType;
//方便可以让我们存储其他类型的数据（只需要将int改成其他类型即可）
- 1
- 2
typedef struct SeqList
{
SeqDataType *a; //指向动态开辟的数组
int size; //记录有效数据
int capacity; //容量空间大小
}SeqList,SEQ;
- 1
- 2
- 3
- 4
- 5
- 6
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
接口的实现（内存中管理数据的结构增删查改的接口）
通常有以下几种接口（接口其实就是实现功能的函数，数据结构以接口称之）
void SeqListInit(SeqList *pq); //初始化
void SeqListDestory(SeqList *pq); //销毁
void SeqlistPushBack(SeqList *pq, SeqDataType x); //尾插
void SeqlistPushFront(SeqList *pq, SeqDataType x); //头插
void SeqlistPopBack(SeqList *pq); //尾删
void SeqlistPopFront(SeqList *pq); //头删
void SeqListPrint(SeqList* pq); //打印
int SeqListFind(SeqList* pq, SeqDataType x); //查找
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
但是需要特别注意所传的参数例如以下几种
这几种就是典型的错误写法
//初始化与销毁
void SeqListInit(SeqList seq);
void SeqListDestory(SeqList seq);
//头插头删，尾插尾删
//void SeqlistPushBack(SEQ seq, SeqDataType x); 等价
void SeqlistPushBack( SeqList seq, SeqDataType x);
void SeqlistPushFront(SeqList seq, SeqDataType x);
void SeqlistPopBack( SeqList seq);
void SeqlistPopFront(SeqList seq);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
形参只是实参的拷贝，形参的改变不会影响实参，要改变就得传他们的地址，要用指针（类比交换两个数字传地址）
断言的好处
这里在实现接口中用到了断言assert
如果有人不小心调用这样一个接口
void TestSeqList1()
{
SeqList* p = NULL;
SeqListInit(p);
}
- 1
- 2
- 3
- 4
- 5
直接报错并且告诉我们第几行出错了
如果没有断言，编译器并没有报错，则很难发现我们的错误，你得去分析程序
初始化的实现
void TestSeqList1()
{
SeqList s = {NULL,0,0};
//SeqListInit(&s);
}
- 1
- 2
- 3
- 4
- 5
这种初始化只能在结构体定义的地方，但在顺序表中不建议这样初始化，我们采用接口的方式实现
void SeqListInit(SeqList *pq)
{
//assert(pq!=NULL); 两者等价，如果指针空报错
assert(pq);
pq->a = NULL;
pq->capacity = pq->size = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
销毁的实现
void SeqListDestory(SeqList *pq)
{
assert(pq);
free(pq->a);
pq->a = NULL;
pq->capacity = pq->size = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
动态增容的实现
如果我们想要实现动态增长，就必须写一个接口检测容量是否满了，满了就增容，没满就继续
void SeqCheckCapacity(SeqList*pq) { if (pq->size == pq->capacity) //数据满了 { int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2; SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity); if (newA == NULL) { printf("realloc fail\n"); exit(-1); } pq->a = newA; pq->capacity = newcapacity; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
尾插的实现
思路：先检查空间是否足够，接着，直接在尾部插入即可
void SeqlistPushBack(SeqList* pq, SeqDataType x)
{
assert(pq);
SeqCheckCapacity(pq); //检测容量
pq->a[pq->size] = x;
pq->size++;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
头插的实现
找到最后一个数据的下标，依次将数据向后挪动，最后再在开端插入你想插入的数据
图解：
代码的实现：
void SeqlistPushFront(SeqList* pq, SeqDataType x)
{
assert(pq);
SeqCheckCapacity(pq);
int end = pq->size - 1;
while (end >= 0)
{
pq->a[end + 1] = pq->a[end];
end--;
}
pq->a[0] = x;
pq->size++;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
尾删的实现
首先得有数据才能删除，将有效数据减减即可实现
void SeqlistPopBack(SeqList* pq)
{
assert(pq);
assert(pq->size>0);
pq->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
头删的实现
将后一个数据覆盖前一个数据
图解：
void SeqlistPopFront(SeqList* pq)
{
assert(pq);
assert(pq->size > 0);
int begin = 0;
while (begin < pq->size-1)
{
pq->a[begin] = pq->a[begin + 1];
begin++;
}
pq->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
查找的实现
思路：只需要将a里面的数据遍历一遍即可
int SeqListFind(SeqList* pq, SeqDataType x)
{
assert(pq);
for (int i = 0;i < pq->size;i++)
{
if (x==pq->a[i])
{
return x;
}
}
return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
打印的实现
思路：很简单，遍历一遍数组即可（顺序表本质就是数组）
void SeqListPrint(SeqList* pq)
{
assert(pq);
for (int i = 0;i < pq->size;i++)
{
printf("%d ", pq->a[i]);
}
printf("\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
到此顺序表的基本结构已经实现，下面实现几个其他有趣的接口
void SeqListInsert(SeqList* pq, int pos, SeqDataType x); //在指定处插入数据
void SeqListErase(SeqList* pq, int pos); //在指定处删除数据
void SeqListModify(SeqList* pq, int pos, SeqDataType x); //修改数据
- 1
- 2
- 3
指定处插入数据的实现
pos代表着插入的位置（必须大于0且小于等于最后一个数据的下标）
在任意一处插入数据，就要找到最后一个数据的下标，把pos后面的数据依次向后挪动，最后在pos处赋予你想插入的数据即可。
图解：
代码如下：
void SeqListInsert(SeqList* pq, int pos, SeqDataType x) { assert(pq); assert(pos >= 0 && pos <= pq->size); // 这里<=pq->size相当于尾插 int end = pq->size-1; SeqCheckCapacity(pq); while (end >= pos) { pq->a[end + 1] = pq->a[end]; end--; } pq->a[pos] = x; pq->size++; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
指定处删除数据的实现
与插入数据相反，删除pos处的数据后，需要将pos后的数据依次向前挪动
图解：
代码如下：
void SeqListErase(SeqList* pq, int pos)
{
assert(pq);
assert(pos >= 0 && pos < pq->size ); //注意这里不能用 <=pq->size ，因为这个地方啥也没有
while (pos <= pq->size - 1)
{
pq->a[pos] = pq->a[pos + 1];
pos++;
}
pq->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
修改数据的实现
修改很简单，只要把pos处的数据换成你想要的数据即可
void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
assert(pq);
assert(pos >= 0 && pos <= pq->size - 1);
pq->a[pos] = x;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
但是这里有人可能就会说为什么不用结构体的性质来修改数据而要多写一个接口?
因为如果超出数组的范围直接用结构体性质修改，编译器不会报错，而接口会直接检查出错误
SeqListModify(&s, 0, -1);
s.a[0] = -1; //这种虽然是正确的，但不如接口好
SeqListModify(&s, 15, -1); //直接检查出错误
s.a[15] = -1; //编译器检查不出错误
- 1
- 2
- 3
- 4
- 5
- 6
到此一个完整的顺序表已经实现。
但是我们可以发现头插头删，尾插尾删都可以用SeqListInsert SeqListErase这两个接口来实现，这就是接口的复用。大大减少了我们的代码量，我们用两个接口实现了四个接口的工作。
void SeqlistPushBack(SeqList* pq, SeqDataType x) { SeqListInsert(pq, pq->size, x); //复用 } void SeqlistPushFront(SeqList* pq, SeqDataType x) { SeqListInsert(pq, 0, x); //复用 } void SeqlistPopBack(SeqList* pq) { SeqListErase(pq, pq->size - 1); //复用 } void SeqlistPopFront(SeqList* pq) { SeqListErase(pq,0); //复用 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
以下是完整代码
头文件部分
#include <stdio.h> #include<assert.h> #include<stdlib.h> typedef int SeqDataType; //方便可以让我们存储其他类型的数据（只需要将int改成其他类型即可） typedef struct SeqList { SeqDataType *a; int size; //记录有效数据 int capacity; //容量空间大小 }SeqList,SEQ; void SeqListInit(SeqList *pq); void SeqListDestory(SeqList *pq); void SeqlistPushBack(SeqList *pq, SeqDataType x); void SeqlistPushFront(SeqList *pq, SeqDataType x); void SeqlistPopBack(SeqList *pq); void SeqlistPopFront(SeqList *pq); void SeqListPrint(SeqList* pq); int SeqListFind(SeqList* pq, SeqDataType x); void SeqListInsert(SeqList* pq, int pos, SeqDataType x); void SeqListErase(SeqList* pq, int pos); void SeqListModify(SeqList* pq, int pos, SeqDataType x);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
源文件部分
#include "Seqlist.h" void SeqListInit(SeqList *pq) { //assert(pq!=NULL); 两者等价，如果指针空报错 assert(pq); pq->a = NULL; pq->capacity = pq->size = 0; } void SeqListDestory(SeqList *pq) { assert(pq); free(pq->a); pq->a = NULL; pq->capacity = pq->size = 0; } void SeqCheckCapacity(SeqList*pq) { if (pq->size == pq->capacity) //数据满了 { int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2; SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity); if (newA == NULL) { printf("realloc fail\n"); exit(-1); } pq->a = newA; pq->capacity = newcapacity; } } void SeqlistPushBack(SeqList* pq, SeqDataType x) { assert(pq); //if (pq->size == pq->capacity) //数据满了 //{ // int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2; // SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity); // if (newA == NULL) // { // printf("realloc fail\n"); // exit(-1); // } // pq->a = newA; // pq->capacity = newcapacity; //} /*SeqCheckCapacity(pq); pq->a[pq->size] = x; pq->size++;*/ SeqListInsert(pq, pq->size, x); //复用 } void SeqListPrint(SeqList* pq) { assert(pq); for (int i = 0;i < pq->size;i++) { printf("%d ", pq->a[i]); } printf("\n"); } void SeqlistPushFront(SeqList* pq, SeqDataType x) { /*assert(pq); SeqCheckCapacity(pq); int end = pq->size - 1; while (end >= 0) { pq->a[end + 1] = pq->a[end]; end--; } pq->a[0] = x; pq->size++;*/ SeqListInsert(pq, 0, x); //复用 } void SeqlistPopBack(SeqList* pq) {/* assert(pq); assert(pq->size>0); pq->size--;*/ SeqListErase(pq, pq->size - 1); //复用 } void SeqlistPopFront(SeqList* pq) { /* assert(pq); assert(pq->size > 0); int begin = 0; while (begin < pq->size-1) { pq->a[begin] = pq->a[begin + 1]; begin++; } pq->size--;*/ SeqListErase(pq,0); } int SeqListFind(SeqList* pq, SeqDataType x) { assert(pq); for (int i = 0;i < pq->size;i++) { if (i==pq->a[i]) { return i; } } return -1; } void SeqListInsert(SeqList* pq, int pos, SeqDataType x) { assert(pq); assert(pos >= 0 && pos <= pq->size); // 加一个等于相当于尾插 int end = pq->size-1; SeqCheckCapacity(pq); while (end >= pos) { pq->a[end + 1] = pq->a[end]; end--; } pq->a[pos] = x; pq->size++; } void SeqListErase(SeqList* pq, int pos) { assert(pq); assert(pos >= 0 && pos < pq->size ); while (pos <= pq->size - 1) { pq->a[pos] = pq->a[pos + 1]; pos++; } pq->size--; } void SeqListModify(SeqList* pq, int pos, SeqDataType x) { assert(pq); assert(pos >= 0 && pos <= pq->size - 1); pq->a[pos] = x; }
- 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
测试源文件部分
#include "Seqlist.h" void TestSeqList1() { SeqList s; SeqListInit(&s); SeqlistPushBack(&s, 1); SeqlistPushBack(&s, 2); SeqlistPushBack(&s, 3); SeqlistPushBack(&s, 4); SeqlistPushBack(&s, 5); SeqlistPushFront(&s, 0); SeqlistPushFront(&s, 0); SeqlistPushFront(&s, 0); SeqlistPushFront(&s, 0); SeqlistPushFront(&s, 0); SeqListPrint(&s); SeqlistPopBack(&s); SeqListPrint(&s); SeqlistPopFront(&s); SeqListPrint(&s); SeqListDestory(&s); } void TestSeqList2() { SeqList s; SeqListInit(&s); SeqlistPushBack(&s, 1); SeqlistPushBack(&s, 2); SeqlistPushBack(&s, 3); SeqlistPushBack(&s, 4); SeqlistPushBack(&s, 5); SeqListPrint(&s); SeqListInsert(&s, 0, 3); SeqListPrint(&s); SeqListInsert(&s, 3, 35); SeqListPrint(&s); SeqListErase(&s, 3); SeqListPrint(&s); SeqListErase(&s, 5); SeqListPrint(&s); SeqListModify(&s, 0, -1); //s.a[0] = -1; //这种虽然是正确的，但不如接口好 SeqListPrint(&s); //SeqListModify(&s, 15, -1); 直接检查出错误 //s.a[15] = -1; 编译器检查不出错误 SeqListPrint(&s); SeqListDestory(&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
- 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/427150
推荐阅读
相关标签
