【数据结构】C语言实现顺序表万字详解(附完整运行代码)
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
一.了解项目功能
在本次项目中我们的目标是实现一个顺序表: 该顺序表使用动态内存分配,可以用来存储任意数量的同类型数据. 顺序表需要包含三个要素:存储数据的数组arr,顺序表的当前存储容量capacity,线性表当前的长度size. 顺序表提供的功能有:
- 顺序表的初始化
- 顺序表元素的查满扩容.
- 顺序表元素的尾插.
- 顺序表元素的头插.
- 顺序表元素的任意指定位置插入.
- 顺序表的尾删.
- 顺序表的头删.
- 顺序表元素的任意指定位置删除.
- 顺序表的查找.
- 顺序表的打印.
- 顺序表的销毁.
二.项目功能演示
要编写一个顺序表项目，首先要明确我们想要达到的效果是什么样，下面我将用vs2022编译器来为大家演示一下顺序表运行时的样子：
顺序表的C语言实现xi
三.逐步实现项目功能模块及其逻辑详解
通过第二部分对项目功能的介绍，我们已经对顺序表的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！
！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。
1.实现顺序表程序菜单
菜单部分的逻辑比较简单，就是利用C语言printf函数打印出这个菜单界面即可。基础问题就不过多赘述了，代码如下：
//菜单函数
void SeqMenu(int size)
{
printf("******************************\n");
printf("******请选择要进行的操作******\n");
printf("******1.顺序表的定点插入******\n");
printf("******2.顺序表的定点删除******\n");
printf("******3.顺序表的定位查找******\n");
printf("******4.顺序表的数据打印******\n");
printf("******5.顺序表的销毁 ******\n");
printf("******0.退出程序 ******\n");
printf("** tips:数据元素位置从0开始 **\n");
printf("** 顺序表的当前长度:%d **\n",size);//每次打印菜单都向用户显示顺序表当前长度
printf("******************************\n");
printf("请选择:>");
}2.实现顺序表程序功能可循环使用
由于我们要实现顺序表的功能可以反复使用的逻辑，因此选择do...while的循环语句来实现这一部分的逻辑，该部分每步的详细解释见代码注释：
int main()
{
SL s; // 创建顺序表变量s
SLInit(&s); // 调用初始化函数初始化顺序表
int swi = 0; // 定义变量swi作为do...while循环的终止条件,以及switch语句的运行条件
do // 使用do...while实现顺序表功能可以反复使用
{
SeqMenu(s.size); // 打印菜单,打印菜单提示用户选择
scanf("%d", &swi); // 存储用户的输入选项
switch (swi) // 根据选项执行相应操作
{
case 0://当用户选择'0',退出程序
printf("您已退出程序:>\n");
// 释放链表内存
SLDestroy(&s);
break;
case 1://当用户选择'1',插入元素
printf("请输入要插入的数据:>");
int insert_data = 0;
scanf("%d", &insert_data);
printf("请输入要插入的数据位置:>");
int insert_pos = 0;
scanf("%d", &insert_pos);
SLInsert(&s, insert_pos, insert_data); // 在顺序表中插入数据
printf("已成功插入:>\n");
break;
case 2://当用户选择'2',删除元素
printf("请输入要删除的数据位置:>");
int delete_pos = 0;
scanf("%d", &delete_pos);
SLErase(&s, delete_pos); // 在顺序表中删除数据
printf("删除成功:>\n");
break;
case 3://当用户选择'3',查找元素
printf("请输入要查找的数据的值:>");
int find_data = 0;
scanf("%d", &find_data);
int find_pos = SLFind(&s, find_data); // 在顺序表中查找数据
if (find_pos != -1)
{
printf("找到了,数据元素%d的下标为%d\n", find_data, find_pos);
}
else
{
printf("没找到,顺序表中可能不存在此数据:<\n");
}
break;
case 4://当用户选择'4',打印元素
printf("打印数据:>\n");
SLPrint(&s); // 打印顺序表中的数据
break;
case 5://当用户选择'5',销毁顺序表
printf("确定要销毁顺序表吗?:>\n");
printf("销毁顺序表输入:1\n");
printf("取消销毁顺序表输入:0\n");
int destroy = 0;
printf("请输入:>");
scanf("%d", &destroy);
if (destroy)
{
SLDestroy(&s); // 销毁顺序表
SLInit(&s); // 重新初始化顺序表
printf("已成功销毁:>\n");
}
else
{
printf("已取消销毁:>\n");
}
break;
default://当用户输入了非选项数字时，提醒用户重新输入
printf("输入错误,请重新输入\n");
break;
}
} while (swi); // 当swi为0时退出循环,结束程序
return 0;
}3.创建顺序表
创建顺序表成员的结构体应该包括:存储数据的数组arr,顺序表的当前存储容量capacity,线性表当前的长度size. 因此我们创建SeqList结构体类型时应由一个数组及两个整型组成.
这里的第一行使用的typedef类定义的作用是方便我们后续在使用顺序表时对存储的数据类型做更改,比如后续我们不想存储int类型数据了,就可以很方便的在这里对数组类型做更改.比如改成char类型,或者double类型,甚至改成任意自己构造的结构类型.在之前的实战项目通讯录中,我们就创建过类似的自定义结构体:如下图.
ps:想了解通讯录程序的朋友可以移步这篇博客:
https://blog.csdn.net/weixin_72357342/article/details/132265734?spm=1001.2014.3001.5502
第二行的宏定义可以方便我们后续对顺序表的初始大小做调整.
有还不太了解宏定义#define及其使用方法的朋友可以移步这里: 【C语言】什么是宏定义?(#define详解)
https://blog.csdn.net/weixin_72357342/article/details/133607987?spm=1001.2014.3001.5502
综上,该部分代码如下:
typedef int SLDataType;//将结构体数组重命名,方便后面修改线性表的成员
#define INIT_CAPACITY 4
//动态顺序表——按需申请
typedef struct SeqList //对结构体重命名为SL
{
SLDataType *arr; //一个指针指向一片连续的空间
int size; //有效数据个数
int capacity; //空间容量
}SL;4.初始化顺序表
初始化顺序表的逻辑不难,但代码编写的细节上可能会需要多注意一些.
首先在进入初始化程序后,我们应当对函数传进来的参数做一个检验,即检验ps指针是否为空指针,如果该指针为空的话,那么指针变量就没有指向任何有效的内存地址，即指针变量的值为0或NULL。这时我们再进入下一步强行开辟内存空间就很可能会导致程序出现一些问题:
tips:用空指针接收malloc函数返回值的危害是非常严重的，因为它会导致程序出现未定义的行为，甚至可能会导致程序崩溃。 当我们调用malloc函数时，它会在堆上分配一块指定大小的内存，并返回指向该内存的指针。如果我们用空指针来接收malloc函数返回的指针，那么就相当于没有为分配的内存分配任何指针变量，这意味着我们无法访问该内存块，也无法释放该内存块，因为我们没有指向它的指针。 这种情况下，如果我们试图访问该内存块，就会发生未定义的行为，也可能会导致程序崩溃。此外，如果我们忘记释放该内存块，就会导致内存泄漏，这会导致程序消耗大量的内存资源，最终导致程序崩溃或者系统变慢。 因此，我们应该始终使用有效的指针变量来接收malloc函数返回的指针，以确保我们能够正确地访问和释放动态分配的内存块。
因此,我们可以使用assert来对函数传进来的参数ps进行检验,如果ps为空,那么立刻终止程序,并抛出异常警告程序员.
对assert宏的使用想要更详细了解的朋友可以移步到这:【C语言】库宏assert简介及使用方法详解
https://blog.csdn.net/weixin_72357342/article/details/133822893?spm=1001.2014.3001.5502
需要注意的是,这里我们对传入的ps指针的断言需要与后面我们要实现的链表中的断言作一下区分:顺序表中要求ps不能为空,是因为一旦ps为空,那么传入的指针一定是一个非法的空指针,因为ps为空,不仅代表arr为NULL,还代表size,capacity也都为NULL.这意味着整个顺序表都是不存在的,而不是仅仅只意味着顺序表中没有元素. 但链表中如果传入的头节点指针指向了NULL,并不能说明链表不存在,而只能说明链表中没有元素而已.这点上的不同是它们两者的结构不同导致的.
检验没有问题后,我们就可以开始进行动态内存开辟的相关操作了:
首先我们使用malloc动态开辟一定字节的空间交给ps->arr来使用:
ps->arr =(SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY);这段代码看似好像很复杂,我给大家将每一小块都拆解一下:
如果对malloc()函数掌握的还是不太好的朋友可以先移步这里: 里面有非常详细的简介及使用方法,在后续查满扩容函数乃至以后的链表,树,图的实现中我们还会经常使用到这个函数:
https://blog.csdn.net/weixin_72357342/article/details/133971625?spm=1001.2014.3001.5502
该部分的功能实现代码如下:
//顺序表的初始化
void SLInit(SL*ps)
{
assert(ps); //查空
ps->arr =(SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY); //扩容
if (ps->arr == NULL)
{
perror("malloc fail"); //如果开辟失败,打印错误信息
return;
}
ps->size = 0; //将顺序表初始元素设为0
ps->capacity = INIT_CAPACITY; //将顺序表初始容量设为INIT_CAPACITY
}5.顺序表的查满及扩容
在顺序表的查满扩容函数中,其实我们只需要进行简单的四步操作:
1.操作之前先使用assert检查一下ps是否为空指针. 2.判断size与capacity的关系,当顺序表的元素个数一旦等于顺序表的容量时,就使用realloc()函数进行扩容.(一般来说,我们每次扩容的容量是扩容前的2倍时比较合理.) 3.使用realloc()函数和malloc()函数一样,当遇到未开辟成功的情况时需要抛出错误信息. 4.最后记得扩容后要给capacity的值也乘2,和空间真实容量保持一致.
该部分功能实现代码如下:
//顺序表的查满扩容
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//扩容二倍比较合理
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->arr = tmp;//原地扩容
ps->capacity *= 2;
}
}6.顺序表元素的插入(插前检查容量)
顺序表元素的插入有三种方式:分别是尾插,头插和任意指定位置插入.
这三种方式都可以实现顺序表的元素插入,接下来我们分别来看一下这三种插入:
?顺序表元素尾插
尾插元素：将元素插入到顺序表的最后一个位置，只需要在arr数组的末尾添加元素即可。该算法的时间复杂度为O(1)。
尾插的逻辑非常简单,不需要挪动元素,只需要在插入元素前检查一下顺序表容量是否满了就行.(调用SLCheckCapacity()函数,查满和扩容一起进行)
该部分功能实现代码如下:
//顺序表的插入(尾插)
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps); //检查ps指针不为NULL
SLCheckCapacity(ps); //首先要检查容量,如果不够要增容
ps->arr[ps->size] = x; //最后将数据赋值给arr数组中的最后一个元素即可
ps->size++;
}?顺序表元素头插
头插元素：将元素插入到顺序表的第一个位置，需要将原有的所有元素都向后移动一位。该算法的时间复杂度为O(n)，其中n是顺序表中元素的个数。
头插的逻辑比尾插复杂一些, 我们需要先将顺序表中的所有元素都向后挪动一位,然后才能在顺序表的首位插入元素.当然,在挪动和插入操作前,我们还是照例要先检查一下顺序表当前容量是否满了. (同样调用SLCheckCapacity()函数,查满和扩容一起进行)
该部分实现代码如下:
/顺序表的插入(头插)
//头插n个数据时间复杂度是O(n),少用!
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
//插之前检查是不是满了
SLCheckCapacity(ps);
//先挪
int end = ps->size - 1;
while (end >= 0)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
//后放
ps->arr[0] = x;
ps->size++;
}?顺序表元素插入任意指定位置
任意指定位置插入元素：将元素插入到顺序表中的任意位置，需要将插入位置后的所有元素都向后移动一位。该算法的时间复杂度为O(n)，其中n是顺序表中元素的个数。
任意指定位置插入的逻辑和头插差不多,只不过头插是把所有位置的元素都向后挪动,使头空出来,好插入元素.而指定位置插入是将指定位置后的所有元素向后挪动一位,使指定位置空出来,好在指定位置插入元素. 因此,我们需要先将顺序表中指定位置后的所有元素都向后挪动一位,然后才能在顺序表的指定位置插入元素.当然,在挪动和插入操作前,我们还是要先检查一下顺序表当前容量是否满了以及检查待插入位置pos是否合法(pos<0或pos>ps->size都是越界访问). (同样调用SLCheckCapacity()函数,查满和扩容一起进行).
该部分实现代码如下:
//顺序表的定点插入
//有定点删除之后就可以不要头插尾插了,直接传参0或者size就行
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
//定点插入,插入点必须在0~size之间(判断).
assert(pos >= 0 && pos <= ps->size);
//pos<0或pos>ps->size都是越界访问
//pos==0,相当于头插,pos==ps->size,相当于尾插
SLCheckCapacity(ps);
int end = ps->size - 1;//从顺序表的末尾逐一向后挪动元素
while (end >= pos) //当将原本pos位置的元素挪走后,就可以插入新元素了
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
//插入新元素
ps->arr[pos] = x;
//元素个数增加
ps->size++;
}有了任意指定位置插入函数后我们容易发现,当我们要求在pos=0的位置插入元素时,其实就相当于顺序表的头插了,当我们要求在pos=size的位置插入元素时,其实就相当于顺序表的尾插了.因此,如果写了任意指定位置插入函数,我们就完全不再需要再写头插和尾插函数了.因为任意指定位置插入函数就可以很好的实现头插和尾插的功能.
7.顺序表元素的删除(删前检查是否为空表)
顺序表元素的删除同样有三种方式:分别是尾删,头删和任意指定位置删除.
这三种方式都可以实现顺序表的元素删除,接下来我们分别来看一下这三种删除:
?顺序表元素尾删
尾删元素：将顺序表的最后一个位置的元素删除，只需要将顺序表的元素个数size-1即可。可以不需要将该位置的数据置为0,因为给size-1实际上是拿走了这块位置的访问权限,没有访问权限时该位置的数据是什么都没有意义.该算法的时间复杂度为O(1)。
尾删的逻辑同样很简单,不需要挪动元素,只需要在删除前检查顺序表是否为空表就行,然后将size--一下.(如果为空,则不需要删除,直接返回即可).
该部分功能实现代码如下:
//顺序表的删除(尾删)
void SLPopBack(SL* ps)
{
//先判断,如果size已经为0了,就不要再删了
if (ps->size == 0)
return;
ps->size--;
//这里没必要把数据置为0,因为size减少后原位置的数据就无法访问了
//其次是这里没法把删除的空间free掉,动态内存申请的空间都是"团购"的,要申请一起申请,要释放只能从头一起释放.
}?顺序表元素头删
头删元素：将顺序表的第一个位置的元素删除掉，需要将除了首元素之外的所有元素都向前移动一位。该算法的时间复杂度为O(n)，其中n是顺序表中元素的个数。
头删的逻辑比尾删复杂一些, 我们需要将顺序表中第一个元素后的所有元素都向前挪动一位,这样刚好原来第一位元素的数据就会被覆盖,即第一个元素被"删除"了.当然,在挪动前,我们还是照例要先检查一下顺序表当前是不是空表.
该部分功能实现代码如下:
//顺序表的删除(头删)时间复杂度O(n^)
void SLPopFront(SL* ps)
{
assert(ps);
//判断是否为空,不为空才能删,为空直接报错
assert(ps->size > 0);
int begin = 1; //元素下标为1,即从第二个元素开始挪动
while (begin < ps->size) //直到将最后一个元素挪动到size-2的位置上
{
ps->arr[begin-1] = ps->arr[begin];
begin++;
}
ps->size--;
}?顺序表删除任意指定位置元素
任意指定位置删除元素：将顺序表的任意位置的元素删除，需要将删除位置后的所有元素都向前移动一位。该算法的时间复杂度为O(n)，其中n是顺序表中元素的个数。
任意指定位置删除的逻辑和头删差不多,只不过头删是把所有第一个元素后的元素都向前挪动,使头位置元素被覆盖.而指定位置删除是将指定位置后的所有元素向前挪动一位,使指定位置被覆盖,以达到删除该元素的效果. 因此,我们需要将顺序表中指定位置后的所有元素都向前挪动一位,以此来达到删除某个元素的效果.当然,在挪动删除操作前,我们还是照例要先检查一下顺序表当前是不是空表,以及检查待删除位置pos是否合法(pos<0或pos>=ps->size都是越界访问).
该部分实现代码如下:
//顺序表的定点删除
//头删和尾删也不用存在了
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);//可以间接检查size是否为0.因为pos没法小于0.
//pos<0或pos>=ps->size都是越界访问
int begin = pos + 1;
while (begin < ps->size)
{
ps->arr[begin - 1] = ps->arr[begin];
begin++;
}
ps->size--;
}有了任意指定位置删除函数后我们发现,当我们要求在pos=0的位置删除元素时,其实就相当于顺序表的头删了,当我们要求在pos=size-1的位置删除元素时,其实就相当于顺序表的尾删了.因此,如果写了任意指定位置删除函数,我们就完全不再需要再写头删和尾删函数了.
8.顺序表元素的查找
顺序表元素的查找有些类似于数组的元素查找,都是在合法数组范围内遍历整个顺序表的元素即可. 如果在遍历的过程中找到了要查找的元素,就返回该元素的下标,如果遍历完还没找到该元素,则意味着该元素不在顺序表中,因此返回-1.
该部分功能实现代码如下:
//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps); //使用assert断言,防止ps为NULL
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i; //找到了,返回元素下标
}
}
return -1; //没找到,返回-1
}9.顺序表元素的打印
顺序表的打印逻辑和查找一样简单,使用循环遍历打印元素即可.
该部分功能实现代码如下:
//顺序表的打印
void SLPrint(SL* ps)
{
assert(ps); //断言防止pa为NULL
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
printf("打印成功:>\n");
}10.顺序表的销毁
当我们使用完顺序表想要退出程序时,就应该将之前动态开辟的内存释放掉,还给操作系统.即销毁顺序表操作. 我们使用free()函数释放掉之前动态开辟的数组arr,然后将arr置为空指针,最后将size,capacity的值置为0即可.
该部分功能实现代码如下:
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->arr);//因为arr是malloc出来的,所以free就要释放arr
ps->arr = NULL;//将arr置为空指针
ps->capacity = 0;
ps->size = 0;
}四.项目完整代码
我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:
SeqList.c文件
#include"SeqList.h"
//菜单
void SeqMenu(int size)
{
printf("******************************\n");
printf("******请选择要进行的操作******\n");
printf("******1.顺序表的定点插入******\n");
printf("******2.顺序表的定点删除******\n");
printf("******3.顺序表的定位查找******\n");
printf("******4.顺序表的数据打印******\n");
printf("******5.顺序表的销毁 ******\n");
printf("******0.退出程序 ******\n");
printf("** tips:数据元素位置从0开始 **\n");
printf("** 顺序表的当前长度:%d **\n",size);
printf("******************************\n");
printf("请选择:>");
}
//顺序表的初始化
void SLInit(SL*ps)
{
assert(ps);
ps->arr =(SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY);
if (ps->arr == NULL)
{
perror("malloc fail");
return;
}
ps->size = 0;
ps->capacity = INIT_CAPACITY;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
assert(ps);
free(ps->arr);//因为a是malloc出来的,所以free就要释放a
ps->arr = NULL;//将a置为空指针
ps->capacity = 0;
ps->size = 0;
}
//顺序表的查满扩容
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//扩容二倍比较合理
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->arr = tmp;//原地扩容
ps->capacity *= 2;
}
}
//顺序表的插入(尾插)
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps); //检查ps指针不为NULL
SLCheckCapacity(ps); //首先要检查容量,如果不够要增容
ps->arr[ps->size] = x; //最后将数据赋值给arr数组中的最后一个元素即可
ps->size++;
}
//顺序表的删除(尾删)
void SLPopBack(SL* ps)
{
assert(ps->size > 0);//括号里为真就过了,为假就报错
ps->size--;
//没必要把数据置为0,因为size减少就是无法访问了
//其次是没法把删除的空间free掉,动态内存申请的空间都是"团购"的,要申请一起申请,要释放只能从头一起释放.
}
//顺序表的插入(头插)
//头插n个数据时间复杂度是O(n),少用!
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
//插之前检查是不是满了
SLCheckCapacity(ps);
//先挪后放
int end = ps->size - 1;
while (end >= 0)
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
ps->arr[0] = x;
ps->size++;
}
//顺序表的删除(头删)删看空,插看满.时间复杂度O(n)
void SLPopFront(SL* ps)
{
assert(ps);
//判断是否为空,不为空才能删,为空直接报错
assert(ps->size > 0);
int begin = 1;
while (begin < ps->size)
{
ps->arr[begin-1] = ps->arr[begin];
begin++;
}
ps->size--;
}
//顺序表的定点插入
//有定点删除之后就可以不要头插尾插了,直接传参0或者size就行
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
//定点插入,插入点必须在0~size之间(判断).
assert(pos >= 0 && pos <= ps->size);
//pos==0,相当于头插,pos==ps->size,相当于尾插
SLCheckCapacity(ps);
int end = ps->size - 1;//从顺序表的末尾逐一向后挪动元素
while (end >= pos) //当将原本pos位置的元素挪走后,就可以插入新元素了
{
ps->arr[end + 1] = ps->arr[end];
end--;
}
//插入新元素
ps->arr[pos] = x;
//元素个数增加
ps->size++;
}
//顺序表的定点删除
//头删和尾删也不用写了
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);//可以间接检查size是否为0.因为pos没法小于0.
int begin = pos + 1;
while (begin < ps->size)
{
ps->arr[begin - 1] = ps->arr[begin];
begin++;
}
ps->size--;
}
//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
//顺序表的打印
void SLPrint(SL* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
printf("打印成功:>\n");
}SeqList.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;//将结构体数组重命名,方便后面修改线性表的成员
#define INIT_CAPACITY 4
//动态顺序表——按需申请
typedef struct SeqList //对结构体重命名为SL
{
SLDataType *arr; //一个指针指向一片连续的空间
int size; //有效数据个数
int capacity; //空间容量
}SL;
//顺序表的初始化
void SLInit(SL*s);
//顺序表的销毁
void SLDestroy(SL*s);
//顺序表的查满
void SLCheckCapacity(SL* ps);
//顺序表的插入(尾插)
void SLPushBack(SL* ps, SLDataType x);
//顺序表的删除(尾删)
void SLPopBack(SL* ps);
//顺序表的插入(头插)
void SLPushFront(SL* ps, SLDataType x);
//顺序表的删除(头删)
void SLPopFront(SL* ps);
//顺序表的定点插入
void SLInsert(SL* ps, int pos, SLDataType x);
//顺序表的定点删除
void SLErase(SL* ps, int pos);
//顺序表的查找
int SLFind(SL* ps, SLDataType x);
//顺序表的打印
void SLPrint(SL* ps);
//顺序表的菜单
void SeqMenu(int size);test.c文件
#include"SeqList.h"
int main()
{
SL s;
SLInit(&s);
int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
do //使用do...while实现
{
SeqMenu(s.size);
scanf("%d", &swi);
switch (swi)
{
case 0:
printf("您已退出程序:>\n");
// 释放链表内存
SLDestroy(&s);
break;
case 1:
printf("请输入要插入的数据:>");
int insert_data = 0;
scanf("%d", &insert_data);
printf("请输入要插入的数据位置:>");
int insert_pos = 0;
scanf("%d", &insert_pos);
SLInsert(&s, insert_pos,insert_data);
printf("已成功插入:>\n");
break;
case 2:
printf("请输入要删除的数据位置:>");
int delete_pos = 0;
scanf("%d", &delete_pos);
SLErase(&s, delete_pos);
printf("删除成功:>\n");
break;
case 3:
printf("请输入要查找的数据的值:>");
int find_data = 0;
scanf("%d", &find_data);
int find_pos = SLFind(&s, find_data);
if (find_pos != -1)
{
printf("找到了,数据元素%d的下标为%d\n", find_data, find_pos);
}
else
{
printf("没找到,顺序表中可能不存在此数据:<\n");
}
break;
case 4:
printf("打印数据:>\n");
SLPrint(&s);
break;
case 5:
printf("确定要销毁顺序表吗?:>\n");
printf("销毁顺序表输入:1\n");
printf("取消销毁顺序表输入:0\n");
int destroy = 0;
printf("请输入:>");
scanf("%d", &destroy);
if (destroy)
{
SLDestroy(&s);
SLInit(&s);
printf("已成功销毁:>\n");
}
else
{
printf("已取消销毁:>\n");
}
break;
default:
printf("输入错误,请重新输入\n");
break;
}
} while (swi);
return 0;
}