热门标签
热门文章
- 1Go实战Gin+Vue+微服务打造秒杀商城第四课 VUE的使用与渲染_gin+vite+vue3实现服务端渲染
- 2STM32F103学习笔记（三）-STM32F103的存储器、供电_stm32f103系列单片机电源
- 3kafka的原理及集群部署详解
- 4踏进字节的那一瞬间，我泪目了，这457天的外包经历值了...._字节外包岗
- 5Git Pull Push 避免用户名和密码方法_git pull的时候不想使用默认密码怎么办
- 6《TrollStore巨魔商店》TrollStore2安装使用教程_巨魔商店2
- 7uniapp通过custom-tab-bar 自定义tabbar导航栏(主要用于微信小程序)_uniapp custom-tab-bar
- 8PyTorch中如何读取数据_pytorch里的读取数据的代码
- 9机器人领域顶刊TRO，TASE及RAL的区别与关系_ral期刊
- 10端点安全时刻影响着网络安全，我们应该如何保护
当前位置: article > 正文
顺序表的实现超详细
作者：weixin_40725706 | 2024-04-15 09:37:57
赞
踩
顺序表的实现
顺序表的基本操作
一、顺序表的概念
● 顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
顺序表一般可以分为：
- 静态顺序表：使用定长数组存储元素。
//把 int 重命名为SLDataType,方便后期数据类型的修改
typedef int SLDataType;
//capacity初始大小为3个(int)
#define N 50
typedef struct SeqList
{
SLDataType data[N]; //用来存放数据的数组指针
int size; //当前顺序表中有效数据的个数
}SeqList;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 动态顺序表：使用动态开辟的数组存储。
//把 int 重命名为SLDataType,方便后期数据类型的修改
typedef int SLDataType;
//capacity初始大小为3个(int)
#define INIT_CAPACITY 3
typedef struct SeqList
{
SLDataType* data; //用来存放数据的数组指针
int size; //当前顺序表中有效数据的个数
int capacity; //顺序表的总大小
}SeqList;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
二、顺序表的基本实现
1.顺序表的定义
使用结构体来创建一个顺序表
//把 int 重命名为SLDataType,方便后期数据类型的修改
typedef int SLDataType;
//capacity初始大小为3个(int)
#define INIT_CAPACITY 3
typedef struct SeqList
{
SLDataType* data; //用来存放数据的数组指针
int size; //当前顺序表中有效数据的个数
int capacity; //顺序表的总大小
}SeqList;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
2.顺序表的初始化
初始化顺序表为3个空间大小
void SeqListInit(SeqList* ps)
{
//使用malloc为data初始化为3个空间
ps->data = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
//如果开辟失败则打印字符串和错信息
if (ps->data == NULL)
{
perror("SeqListInit");
return;
}
ps->size = 0; //size是顺序表的有效数据，初始为0
//上面为顺序表开辟了3个空间，所以这里capacity初始为3个空间大小
ps->capacity = INIT_CAPACITY;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
3.顺序表的销毁
动态开辟的空间都需要销毁
void SeqListDestroy(SeqList* ps)
{
free(ps->data);
ps->data = NULL;
ps->capacity = ps->size = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
4.顺序表的打印
void SeqListPint(SeqList* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->data[i]);
}
printf("\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
5.增加容量（空间不够则增容）
如果已经插入了3个数据，则空间已经满了，继续增加会非法访问内存，这时我们需要增加容量，我们是按照总容量大小的2倍来增加容量的，因为使用realloc开辟的空间，如果要增加的这个空间太大，realloc可能会异地扩容，realloc异地扩容的消耗大，所以我们每次增加总容量的2倍。
void check_capacity(SeqList* ps) { //当size==capacity时，则代表顺序表的空间满了，需要扩容 if (ps->size == ps->capacity) { //每次开辟的空间都是总空间的2倍 SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2); //如果开辟失败则打印字符串和错信息 if (tmp == NULL) { perror("check_capacity"); return; } ps->data = tmp; //把tmp开辟的空间给data ps->capacity *= 2; //扩完容，把capacity的容量也修改成总空间大小的2倍 printf("增容成功\n"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
6.查找指定位置
给定一个要查找的值，返回这个值下标就行了
int SeqListFind(SeqList* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->data[i] == x)
{
return i;
}
}
return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
7.任意位置插入
给定一个下标，在下标位置插入一个新的值，下标的值和下标后的值都要往后移动一个位置
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
//当pos=0时，相当于头插，当下标为size时，相当于尾插
assert(pos>=0 && pos<=ps->size);
check_capacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->data[end + 1] = ps->data[end];
end--;
}
ps->data[pos] = x;
ps->size++;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
8.任意位置删除
给定一个下标，从pos下标开始，把后面的元素向前覆盖一个位置
void SeqListErase(SeqList* ps, int pos)
{
assert(pos>=0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->data[begin-1] = ps->data[begin];
begin++;
}
ps->size--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
9.尾部插入
1.尾部插入比较简单，我们只需要找到有效元素最后一个位置+1就可以插入了
2.也可以调用SeqListInsert任意位置插入函数
void SeqListPushBack(SeqList* ps, SLDataType x)
{
//方法1：
//assert(ps);
//check_capacity(ps);
//ps->data[ps->size] = x;
//ps->size++;
//方法2：调用SeqListInsert任意位置插入函数
SeqListInsert(ps, ps->size , x);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
10.尾部删除
1.尾部删除也比较简单，只需要找到size位置然后减1
2.也可以调用SeqListInsert任意位置删除函数
void SeqListPopBack(SeqList* ps)
{
//方法1：
//断言size不能为空，为空则会报错，不为空则什么也不做
//assert(ps->size > 0);
//ps->size--;
//方法2：调用SeqListErase任意位置删除函数
SeqListErase(ps, ps->size-1);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
11.头部插入
1.把顺序表中所有数据向后移动，然后把data[0]首元素位置插入新值
2.也可以调用SeqListErase任意位置删除函数
void SeqListPushFront(SeqList* ps, SLDataType x) { //方法一： //check_capacity(ps); //int end = ps->size - 1; //while (end >= 0) //{ // ps->data[end + 1] = ps->data[end]; // end--; //} //ps->data[0] = x; //ps->size++; //方法2：调用SeqListInsert任意位置插入函数 SeqListInsert(ps, 0, x); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
12.头部删除
1.头部删除就是把顺序表中所有元素向前移动一个位置
2.也可以调用SeqListErase任意位置插入函数
void SeqListPopFront(SeqList* ps)
{
//方法1：
//assert(ps->size > 0);
//int begin = 1;
//while (begin < ps->size-1)
//{
// ps->data[begin - 1] = ps->data[begin];
// begin++;
//}
//ps->size--;
//方法2：调用SeqListErase任意位置删除函数
SeqListErase(ps,0);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
13.整体代码
SeqList.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<string.h> //把 int 重命名为SLDataType,方便后期数据类型的修改 typedef int SLDataType; //capacity初始大小为3个(int) #define INIT_CAPACITY 3 typedef struct SeqList { SLDataType* data; //用来存放数据的数组指针 int size; //当前顺序表中有效数据的个数 int capacity; //顺序表的总大小 }SeqList; void SeqListInit(SeqList* ps); void SeqListDestroy(SeqList* ps); void SeqListPint(SeqList* ps); void SeqListPushBack(SeqList* ps, SLDataType x); void SeqListPopBack(SeqList* ps); void SeqListPushFront(SeqList* ps, SLDataType x); void SeqListPopFront(SeqList* ps); // 顺序表查找 int SeqListFind(SeqList* ps, SLDataType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, int pos, SLDataType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, int 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
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" void SeqListInit(SeqList* ps) { //使用malloc为data初始化为3个空间 ps->data = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); //如果开辟失败则打印字符串和错信息 if (ps->data == NULL) { perror("SeqListInit"); return; } ps->size = 0; //size是顺序表的有效数据，初始为0 //上面为顺序表开辟了3个空间，所以这里capacity初始为3个空间大小 ps->capacity = INIT_CAPACITY; } void SeqListDestroy(SeqList* ps) { free(ps->data); ps->data = NULL; ps->capacity = ps->size = 0; } void SeqListPint(SeqList* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->data[i]); } printf("\n"); } void check_capacity(SeqList* ps) { //当size==capacity时，则代表顺序表的空间满了，需要扩容 if (ps->size == ps->capacity) { //每次开辟的空间都是总空间的2倍 SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2); //如果开辟失败则打印字符串和错信息 if (tmp == NULL) { perror("check_capacity"); return; } ps->data = tmp; //把tmp开辟的空间给data ps->capacity *= 2; //扩完容，把capacity的容量也修改成总空间大小的2倍 printf("增容成功\n"); } } void SeqListPushBack(SeqList* ps, SLDataType x) { //方法1： //assert(ps); //check_capacity(ps); //ps->data[ps->size] = x; //ps->size++; //方法2：调用SeqListInsert任意插入函数 SeqListInsert(ps, ps->size , x); } void SeqListPopBack(SeqList* ps) { //方法1： //断言size不能为空，为空则会报错，不为空则什么也不做 //assert(ps->size > 0); //ps->size--; //方法2：调用SeqListInsert任意位置删除函数 SeqListErase(ps, ps->size-1); } void SeqListPushFront(SeqList* ps, SLDataType x) { //方法一： //check_capacity(ps); //int end = ps->size - 1; //while (end >= 0) //{ // ps->data[end + 1] = ps->data[end]; // end--; //} //ps->data[0] = x; //ps->size++; //方法2：调用SeqListErase任意位置插入函数 SeqListInsert(ps, 0, x); } void SeqListPopFront(SeqList* ps) { //方法1： //assert(ps->size > 0); //int begin = 1; //while (begin < ps->size-1) //{ // ps->data[begin - 1] = ps->data[begin]; // begin++; //} //ps->size--; //方法2：调用SeqListErase任意位置删除函数 SeqListErase(ps,0); } // 顺序表查找 int SeqListFind(SeqList* ps, SLDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->data[i] == x) { return i; } } return -1; } // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, int pos, SLDataType x) { //当pos=0时，相当于头插，当下标为size时，相当于尾插 assert(pos>=0 && pos<=ps->size); check_capacity(ps); int end = ps->size - 1; while (end >= pos) { ps->data[end + 1] = ps->data[end]; end--; } ps->data[pos] = x; ps->size++; } // 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, int pos) { assert(pos>=0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->data[begin-1] = ps->data[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
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
test.c
enum Optin { EXIT, SLBACKPUSH, SLBACKPOP, SLFRONTPUSH, SLFRONTPOP, SLINSERT, SLERASE, SLEFIND, SLPRINT }; void menu() { printf("**************************************************************\n"); printf("********* 1.尾插 2.尾删 ***********\n"); printf("********* 3.头插 4.头删 ***********\n"); printf("********* 5.任意位置插入 6.任意位置删除 ***********\n"); printf("********* 7.查找元素的下标 8.打印 ***********\n"); printf("********* 0/-1.退出 ***********\n"); printf("*************************************************************\n"); } int main() { int option = 0; SeqList p; SeqListInit(&p); while (option != -1) { menu(); printf("请输入要选择的选项："); scanf("%d", &option); if (option == EXIT) { printf("请依次输入要尾插的数据，以-1结束："); int x = 0; while (x != -1) { scanf("%d", &x); SeqListPushBack(&p, x); } SeqListPint(&p); } else if (option == SLBACKPUSH) { int x = 0; printf("请输入要尾删的个数："); scanf("%d", &x); while (x--) { SeqListPopBack(&p); } SeqListPint(&p); } else if (option == SLBACKPOP) { int x = 0; printf("请依次输入要头插的数据，以-1结束："); while (x != -1) { scanf("%d", &x); SeqListPushFront(&p, x); } SeqListPint(&p); } else if (option == SLFRONTPOP) { int x = 0; printf("请输入要头删的个数："); scanf("%d", &x); while (x--) { SeqListPopFront(&p); } SeqListPint(&p); } else if (option == SLINSERT) { int x = 0; int y = 0; printf("请输入要任意插入位置的下标："); scanf("%d", &x); printf("请依次输入你要插入的数据："); scanf("%d", &y); SeqListInsert(&p, x, y); SeqListPint(&p); } else if (option == SLERASE) { int x = 0; printf("请输入你要任意删除位置的下标："); scanf("%d", &x); SeqListErase(&p, x); SeqListPint(&p); } else if (option == SLEFIND) { int x = 0, y = 0; printf("请输入你要查找下标的个数："); scanf("%d", &x); printf("请依次输入你要查找下标的数字："); while (x--) { scanf("%d", &y); int ret = SeqListFind(&p, y); printf("%d ", ret); } printf("\n"); } else if (option == SLPRINT) { SeqListPint(&p); } else if (option == -1) { printf("退出顺序表\n"); } else { printf("无此选项，请重新输入\n"); } } }
- 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
打印结果：
14.顺序表的优缺点
优点：
1.支持随机访问（用下标访问），需要随机访问结构支持算法可以很好的适用；
2.cpu高速缓存命中率更高；
缺点：
1.头部中部插入删除时间效率低O(N);
2.连续的物理空间，空间不够了以后需要增容；
a.增容有一定程度的消耗；
b.为了避免频繁增容，我们一般按照2倍去增加，用不完会存在一定空间的浪费；
这篇文章到这就结束啦，不管你喜不喜欢，都看到这了，点完赞再走吧
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/427097
推荐阅读
相关标签
Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。
