admin管理员组文章数量:1794759
【数据结构】顺序表
数据结构是计算机存储、组织数据的方式，简单来说，数据结构就是把数据“管理”起来，以什么方式“管理”起来呢？本篇就介绍了“管理”方式之一，顺序表。
1. 顺序表的概念及结构
1.1 线性表
说顺序表就不得不说线性表。
线性表是n个具有相同特性的数据元素的有限序列，是一种广泛使用的数据结构，它在逻辑结构上是线性的，也就是连续的一条线，而在物理结构上不一定是连续的，可以像下图这样理解
常见的线性表：顺序表、链表、栈、队...
顺序表是线性表的一种，所以顺序表在逻辑结构上也是连续的，而且在物理结构上也是连续的
1.2顺序表和数组
顺序表底层就是数组，顺序表在数组的基础上对数据进行增加、删除、查找、改变的操作，成为一个“多功能的数组”
1.3 顺序表的结构
顺序表有两种：静态顺序表、动态顺序表
静态顺序表：底层是定长数组
代码语言：javascript代码运行次数：0运行复制struct SeqList
{
int arr[100];//申请的空间 是固定值
int size; //记录顺序表当前有效的数据个数
};两个结构体成员，首先申请空间，第一个成员假设申请了100个整型空间，这100个空间就固定了，但是不一定这100个空间都存放数据，所以还要有第二个成员size来记录顺序表的有效数据个数
动态顺序表：按需申请
代码语言：javascript代码运行次数：0运行复制struct SeqList
{
int* arr;//动态申请空间 大小可调整
int size;//记录顺序表当前有效的数据个数
int capacity;//记录空间大小
};三个结构体成员，第一个成员，动态内存管理相关的函数来按需求灵活的开辟空间，开辟成功接受空间的地址，第二个成员size来记录顺序表的有效数据个数，因为空间不是定长，所以要第三个成员记录开辟了多大空间
(结构体相关知识请看【C语言】结构体详解-CSDN博客)
我们更推荐使用动态顺序表
2.动态顺序表实现
首先我们要新建一个头文件(.h)，一个源文件(.c)
为什么要这样呢？比如说我们在读一本书的时候会发现书的前面有目录，在这个顺序表的实现中，头文件就起到了这样一个作用
我们写好之后还要测试我们写的代码是否正确，所以还要一个负责测试的源文件(.c)
好的，我们先从头文件开始
点开头文件，在这个文件里面我们要定义顺序表结构，这里我们选择用动态顺序表
代码语言：javascript代码运行次数：0运行复制//定义顺序表结构
struct SeqList //动态顺序表结构
{
int* arr;
int size; //有效个数
int capacity; //空间大小
};但是呢，这个顺序表不一定就是存放整型的数组，并且我觉得创建结构体数组变量的时候太麻烦了，所以这里我们做一个修改，给类型取个别的名字，给结构体也取个名字，如下
代码语言：javascript代码运行次数：0运行复制typedef int Type;
typedef struct SeqList //动态顺序表结构
{
Type* arr;
int size; //有效个数
int capacity; //空间大小
}SL;假如以后要改数据的类型，只需要将typedef int Type;中的int改为别的就好了，就不要整个代码一处一处改
2.1 顺序表初始化
在头文件中，进行函数的声明，首先我们要进行初始化
代码语言：javascript代码运行次数：0运行复制//顺序表初始化
void SLInit(SL* ps);在SeqList.c中进行函数的实现
代码语言：javascript代码运行次数：0运行复制#include "SeqList.h" //包含头文件
//顺序表的初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}代码写好之后，我们要在test.c中进行测试，一定要边写边测试，不然到最后错误一大堆，不知道从哪改起
代码语言：javascript代码运行次数：0运行复制#include "SeqList.h" //也要包含头文件
void SLtest1()
{
SL s1;
SLInit(&s1); //传地址
}
int main()
{
SLtest1();
return 0;
}我们打开调试窗口来看，初始化成功
2.2 顺序表的销毁
因为我们在顺序表中会用到动态内存函数malloc、calloc、realloc，所以要释放空间，但是因为简单所以我们先说这一步，先提前写好代码
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制//顺序表的销毁
void SLDest(SL* ps);在SeqList.c中进行函数的实现
代码语言：javascript代码运行次数：0运行复制void SLDest(SL* ps) //顺序表的销毁
{
if (ps->arr)//如果申请的有空间
{
free(ps->arr);//销毁
}
ps->arr = NULL;//置空
ps->size = ps->capacity = 0;//三个参数都还原
}不要忘了在test.c中测试
代码语言：javascript代码运行次数：0运行复制void SLtest1()
{
SL s1;
SLInit(&s1);//初始化
//增、删、查、改
//.....
SLDest(&s1);//使用完销毁
}2.3 顺序表的插入
要在顺序表里插入数据有三种情况，从最前面插入，叫头插，从最后面插入，叫尾插，还有指定位置插入
2.3.1 申请空间
在插入数据之前我们要先看空间够不够
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制//申请空间
void SLFind(SL* ps);在SeqList.c中进行函数的实现
代码语言：javascript代码运行次数：0运行复制void SLFind(SL* ps)
{
if (ps->size == ps->capacity) //两者相等时说明空间不够了
{
//申请空间
}
}那么问题来了，申请多大的空间呢？一次增容增多大呢？ 增容通常来说是成倍数增加，一般是原空间的2倍或者3倍
代码语言：javascript代码运行次数：0运行复制void SLFind(SL* ps)
{
if (ps->size == ps->capacity) //两者相等时说明空间不够了
{
//申请空间
ps->arr = (Type*)realloc(ps->arr, ps->capacity * 2 * sizeof(Type));
}
}现在问题又来了，这个capacity我们初始化为0了，怎么办呢？那我们再创建一个变量判断一下capacity是否为0，为0就默认给4个空间大小，不为0就直接变成原来的2倍，然后把ps->capacity*2换成newcapacity
代码语言：javascript代码运行次数：0运行复制void SLFind(SL* ps)
{
if (ps->size == ps->capacity) //两者相等时说明空间不够了
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断
ps->arr = (Type*)realloc(ps->arr, newcapacity * sizeof(Type));//申请空间
}
}当然，直接在初始化的时候就给一定的空间也是可以的，只要不出错就行。
因为realloc如果空间申请失败返回NILL，严谨起见我们再把代码优化一下
代码语言：javascript代码运行次数：0运行复制void SLFind(SL* ps)
{
if (ps->size == ps->capacity) //两者相等时说明空间不够了
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
Type* temp = (Type*)realloc(ps->arr, newcapacity * sizeof(Type));//申请空间
if (temp == NULL)//空间申请失败
{
perror("realloc");
return;
}
else //空间申请成功
{
ps->arr = temp;
ps->capacity = newcapacity;
}
}
}测试的话和后面的尾插一起测试
2.3.2 尾插
也就是从数组的最后面插入数据
还是一样，在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制//尾部插入
void SLPushBack(SL* ps, Type x);第一个参数就是顺序表，第二个参数是要插入的数据，而这个数据的类型Type就是前面我们改名了的类型，在这里其实就是int。
在SeqList.c中进行函数的实现
先分析一下，假如下面的情景
我们要尾插一个5，就插在下标为size的位置，此时size要+1
代码为
代码语言：javascript代码运行次数：0运行复制void SLPushBack(SL* ps, Type x) //顺序表的尾插
{
assert(ps);//ps不能为NULL
SLFind(ps); //调用刚刚写的申请空间的函数
ps->arr[ps->size] = x; //尾插
ps->size++;
}不要忘了在test.c中测试
我们尾插5个数据，结果成功
代码语言：javascript代码运行次数：0运行复制#include "SeqList.h"
void SLtest1()
{
SL s1;
SLInit(&s1);//初始化
SLPushBack(&s1, 1);
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPushBack(&s1, 5);
SLDest(&s1);//使用完销毁
}
int main()
{
SLtest1();
return 0;
}空间申请也成功
小总结：
到目前为止，SeqList.h内代码如下
SeqList.c内代码如下
test.c内代码如下
2.3.3 头插
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制void SLPushhead(SL* ps, Type x);//头部插入和尾插参数一样，第一个参数就是顺序表，第二个参数是要插入的数据，而这个数据的类型Type就是前面我们改名了的类型，在这里其实就是int。
在SeqList.c中进行函数的实现
头插就是在下标为0的位置插入数据
所以我们要把顺序表中已有的数据整体往后挪动一位
然后再一个一个往后挪
移动完之后size+1
分析完之后我们来看代码如何实现
代码语言：javascript代码运行次数：0运行复制void SLPushhead(SL* ps, Type x)//头部插入
{
assert(ps);//ps不能为NULL
SLFind(ps); //调用申请空间的函数
for (int i = ps->size; i > 0; i--)//移动
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}不要忘了在test.c中测试
代码语言：javascript代码运行次数：0运行复制#include "SeqList.h"
void SLtest1()
{
SL s1;
SLInit(&s1);//初始化
SLPushBack(&s1, 1);//尾插
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPushhead(&s1, 5);//头插
SLPushhead(&s1, 6);
SLDest(&s1);//使用完销毁
}
int main()
{
SLtest1();
return 0;
}插入成功
2.3.4 打印
我们直接把数据打印出来看，就不在调试窗口看了
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制void SLPrint(SL* ps);//打印数据在SeqList.c中进行函数的实现
代码语言：javascript代码运行次数：0运行复制void SLPrint(SL* ps)//打印数据
{
for (int i = 0; i < ps->size; i++)
printf("%d ", ps->arr[i]);
printf("\n");
}在test.c中测试
代码语言：javascript代码运行次数：0运行复制#include "SeqList.h"
void SLtest1()
{
SL s1;
SLInit(&s1);//初始化
SLPushBack(&s1, 1);//尾插
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPrint(&s1);//打印
SLPushhead(&s1, 5);//头插
SLPushhead(&s1, 6);
SLPrint(&s1);//打印
SLDest(&s1);//使用完销毁
}
int main()
{
SLtest1();
return 0;
}运行看结果
2.3.5 指定位置之前插入
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制void SLInsert(SL* ps, int pos, Type x);//指定位置之前插入第一个参数是顺序表，第二个参数是插入的下标的位置，pos不能是任意的，要大于等于0，小于等于size，第三个就是插入的数据
在SeqList.c中进行函数的实现
要把pos的位置空出来，pos后面的数据都要往后移
然后把x放入下标为2的位置，size+1
代码表示如下
代码语言：javascript代码运行次数：0运行复制void SLInsert(SL* ps, int pos, Type x)//指定位置之前插入
{
assert(ps);//ps不能为NULL
assert(pos >= 0 && pos <= ps->size);//pos有限制
SLFind(ps);//检查是否需要增容
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}在test.c中测试
2.4顺序表的删除
数据的删除有三种情况：尾删、头删、指定位置删除
2.4.1 尾删
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制void SLPopBack(SL* ps);//尾删删除数据就行，所以只要一个参数
在SeqList.c中进行函数的实现
删除最后面的那个数据其实只需要size-1就可以了
我们对顺序表的控制只在size之前，让要删除的数据不在控制范围内，且这样操作不影响顺序表的增、删、查、改即可
当顺序表中的数据删完了，size=0时，就不能在执行删除操作了
所以size也不能为0，代码如下
代码语言：javascript代码运行次数：0运行复制void SLPopBack(SL* ps)//尾删
{
assert(ps);//ps不能为NULL
assert(ps->size);//size不能为0
ps->size--;
}在test.c中测试一下
代码语言：javascript代码运行次数：0运行复制void SLtest1()
{
SL s1;
SLInit(&s1);//初始化
SLPushBack(&s1, 1);//尾插
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPrint(&s1);//打印
SLPushhead(&s1, 5);//头插
SLPushhead(&s1, 6);
SLPrint(&s1);//打印
SLPopBack(&s1);//尾删
SLPrint(&s1);//打印
SLDest(&s1);//使用完销毁
}运行，尾删成功
2.4.2 头删
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制void SLPopHead(SL* ps);//头删在SeqList.c中进行函数的实现
我们先把下标为1的数据放到下标为0的地方去
依次向前移动，注意，只能访问到size-1处
代码为
代码语言：javascript代码运行次数：0运行复制void SLPopHead(SL* ps)//头删
{
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
}移动完之后，size-1
最终代码为
代码语言：javascript代码运行次数：0运行复制void SLPopHead(SL* ps)//头删
{
assert(ps);//ps不能为NULL
assert(ps->size);//size不能为0
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}在test.c中测试
代码语言：javascript代码运行次数：0运行复制void SLtest1()
{
SL s1;
SLInit(&s1);//初始化
SLPushBack(&s1, 1);//尾插
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPrint(&s1);//打印
SLPushhead(&s1, 5);//头插
SLPushhead(&s1, 6);
SLPrint(&s1);//打印
SLPopBack(&s1);//尾删
SLPopHead(&s1);//头删
SLPrint(&s1);//打印
SLDest(&s1);//使用完销毁
}运行，头删成功
2.4.3 指定位置删除
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制void SLErase(SL* ps, int pos);//指定位置删除第一个参数是顺序表，第二个参数是插入的下标的位置，pos不能是任意的，要大于等于0，小于size，这里不能等于size
在SeqList.c中进行函数的实现
将pos后面的数据移到pos处，以此类推
最后再size-1
代码实现如下
代码语言：javascript代码运行次数：0运行复制void SLErase(SL* ps, int pos)//指定位置删除
{
assert(ps);//ps不能为NULL
assert(ps->size);//size不能为0
assert(pos >= 0 && pos <= ps->size);//pos有限制
for (int i = pos; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}在test.c中测试
代码语言：javascript代码运行次数：0运行复制void SLtest1()
{
SL s1;
SLInit(&s1);//初始化
SLPushBack(&s1, 1);//尾插
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPrint(&s1);//打印
SLErase(&s1, 0);//指定位置删除
SLPrint(&s1);//打印
SLDest(&s1);//使用完销毁
}测试结果
2.5 顺序表的查找
在头文件SeqList.h中，进行函数声明
代码语言：javascript代码运行次数：0运行复制int SLSeek(SL* ps, Type x);//查找找到了就返回数据的下标，没找到就返回-1，参数一个是顺序表，一个是要查找到数据
在SeqList.c中进行函数的实现
代码语言：javascript代码运行次数：0运行复制int SLSeek(SL* ps, Type x)//查找
{
assert(ps);//ps不能为NULL
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)//找到了
{
return i;
}
}
return -1; //没找到
}在test.c中测试
代码语言：javascript代码运行次数：0运行复制void SLtest2()
{
SL s1;
SLInit(&s1);//初始化
SLPushBack(&s1, 1);//尾插
SLPushBack(&s1, 2);
SLPushBack(&s1, 3);
SLPushBack(&s1, 4);
SLPrint(&s1);//打印
int seek = SLSeek(&s1, 4);
if (seek == -1)
printf("没找到\n");
else
printf("找到了，下标为%d\n", seek);
SLDest(&s1);//使用完销毁
}
int main()
{
//SLtest1();
SLtest2();
return 0;
}顺序表基本就是这样了，本次分享就到这里，下次见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-04-08，如有侵权请联系 cloudcommunity@tencent 删除函数数据数据结构ps测试本文标签： 数据结构顺序表
版权声明：本文标题：【数据结构】顺序表 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754692719a1705288.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论