C语言数据结构之顺序表（上）
前言：
⭐️此篇博文主要分享博主在学习C语言的数据结构之顺序表的知识点时写的笔记，若有错误，还请佬指出，一定感谢！制作不易，若觉得内容不错可以点赞👍+收藏❤️，这是对博主最大的认可！
顺序表的概念
顺序表是用一段
物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表的分类
1.静态顺序表：使用定长数组存储元素
2.动态顺序表：使用动态开辟的数组存储
静态顺序表的实现
1.前期准备
a.建立工程，建立相应的文件。
博主这边建立了三个文件，首先第一个SeqList.h这个头文件是用于接口（函数）的声明，SeqList.c这个.c文件是用于接口（函数）的实现，test.c文件主要用于测试相对应的接口与预期是否有差别。
b.两个.c文件均包含SeqList.h
c.浅浅的定义好结构体
typedef struct SeqList
{
int arr[100];
size_t size;//有效数据个数
}SeqList;
由于定义数组类型时只定义了int类型，这样的话只能存储int类型的数据了。为了方便接收其他数据时，改动较少关于int的地方，故可对int类型重定义。而且100把这个数组的大小写死了，故可用#define定义的常变量来替代100，方便后续对数组大小进行修改。（有时不止仅仅是修改int arr[100]里面的100，而是整个工程中用到数组大小为100的地方都需要修改，这样修改较麻烦。）还有一点是要使用size_t类型（vs2022下是无符号整型）需包含头文件stdio.h。
改动如下：
typedef int Datatype;
#define N 100
typedef struct SeqList
{
Datatype arr[N];
size_t size;//有效数据个数
}SeqList;
注：用到int的地方都可以用Datatype替代，要接收其他数据类型时，只需把typedef int Datatype中的int改为其他类型即可，数组大小100也是如此。
2.接口的实现
.h文件：
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
typedef int Datatype;
#define N 100
typedef struct SeqList
{
Datatype arr[N];
size_t size;//有效数据个数
}SeqList;
//顺序表的初始化
void InitSeqList();
//顺序表的展示
void ShowSeqList();
//顺序表的销毁
void DestorySeqList();
//顺序表的增加数据功能
void AddData();
//顺序表的删除数据功能
void DeleteData();
//顺序表的查找功能
void FindData();
//顺序表的修改功能
void ModifyData();🤔思考：参数传值还是传址？
😶凡是需要对对象操作的都应当传地址，因为有对象的地址才能找到对象那片空间，对空间进行操作。所以这里为了统一形参形式，我都选择了用指针接收。由于对象是个结构体所以用结构体指针当形参。
//顺序表的初始化
void InitSeqList(SeqList*);
//顺序表的展示
void ShowSeqList(SeqList*);
//顺序表的销毁
void DestorySeqList(SeqList*);
//顺序表的增加数据功能
void AddData(SeqList*, Datatype);
//顺序表的删除数据功能
void DeleteData(SeqList*, Datatype);
//顺序表的查找功能
void FindData(SeqList*);
//顺序表的修改功能
void ModifyData(SeqList*, Datatype, Datatype);SeqList.c文件：
先来实现第一个接口//顺序表的初始化---void InitSeqList(SeqList*)
//顺序表的初始化
void InitSeqList(SeqList* p)
{
//对数组进行初始化
for (size_t i = 0; i < N; i++)
{
p->arr[i] = -1;//初始化为-1，这一步可不做
}
p->size = 0;//有效数据个数置为0
}一个一个功能来测试：
调试发现确实和预期的效果一样。
再来实现第二个接口//顺序表的销毁---void destorySeqList(SeqList*)
//顺序表的销毁
void DestorySeqList(SeqList* p)
{
p->size = 0;
}这个和初始化差不多，可做可不做。
再来实现第三个接口//顺序表的增加数据---void AddData(SeqList*, Datatype)
//顺序表的增加数据功能
void AddData(SeqList* p, Datatype x)
{
p->arr[p->size] = x;
p->size++;
//p->arr[p->size++] = x;
}
功能测试（调试）：
☑️这里对op这个结构体增加数据，确实能发现数组元素增加了5个，size也跟着更新了。
再来实现第四个接口//顺序表的展示void ShowSeqList(SeqList*)
//顺序表的展示
void ShowSeqList(SeqList* p)
{
for (size_t i = 0; i < p->size; i++)
{
printf("%d ", p->arr[i]);
}
printf("\n");//换个行，没别的意思
}
☑️ok，没啥问题。
再来实现第五个接口//顺序表的删除数据功能void DeleteData(SeqList*, Datatype)
//顺序表的删除数据功能
void DeleteData(SeqList* p, Datatype x)
{
for (size_t i = 0; i < N; i++)//遍历寻找
{
if (p->arr[i] == x)//找到了,i是对对应的下标
{
//挪动覆盖即可
for (size_t j = i + 1; j < p->size; j++)
{
p->arr[j - 1] = p->arr[j];
}
p->size--;
}
}
}
☑️下标为4那个5不在size的有效数据范围内，打印时不会显示出它。
最后来实现第六个接口//顺序表的查找功能void FindData(SeqList*)和第七个接口//顺序表的修改功能
查找过程在删除那里结合在一起写了，就不再重复写了，应该是博主不小心把删除和查找的参数写反了，本来删除应该是实现顺序表的尾删。不过问题不大，静态顺序表不是重点，实际应用中也不多。
//顺序表的修改功能
void ModifyData(SeqList* p, Datatype x, Datatype y)
{
for (size_t i = 0; i < N; i++)//遍历寻找
{
if (p->arr[i] == x)//找到了,i是对对应的下标
{
p->arr[i] = y;//把对应的值改掉即可
}
}
}
☑️这里先增加了5这个数据，然后顺序表中有2个5，我改成了0，如果只想改第一个5，可以在Modify函数的if语句后加break;语句，找到一个就修改然后结束循环。
3.完整代码展示
.h文件：
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
typedef int Datatype;
#define N 100
typedef struct SeqList
{
Datatype arr[N];
size_t size;//有效数据个数
}SeqList;
//顺序表的初始化
void InitSeqList(SeqList*);
//顺序表的展示
void ShowSeqList(SeqList*);
//顺序表的销毁
void DestorySeqList(SeqList*);
//顺序表的增加数据功能
void AddData(SeqList*, Datatype);
//顺序表的删除数据功能
void DeleteData(SeqList*, Datatype);
//顺序表的查找功能
void FindData(SeqList*);
//顺序表的修改功能
void ModifyData(SeqList*, Datatype, Datatype);SeqList.c接口功能的实现：
#include "SeqList.h"
//顺序表的初始化
void InitSeqList(SeqList* p)
{
//对数组进行初始化
for (size_t i = 0; i < N; i++)
{
p->arr[i] = -1;//初始化为-1，这一步可不做
}
p->size = 0;//有效数据个数置为0
}
//顺序表的销毁
void DestorySeqList(SeqList* p)
{
p->size = 0;
}
//顺序表的增加数据功能
void AddData(SeqList* p, Datatype x)
{
//p->arr[p->size] = x;
//p->size++;
p->arr[p->size++] = x;
}
//顺序表的展示
void ShowSeqList(SeqList* p)
{
for (size_t i = 0; i < p->size; i++)
{
printf("%d ", p->arr[i]);
}
printf("\n");//换个行，没别的意思
}
//顺序表的删除数据功能
void DeleteData(SeqList* p, Datatype x)
{
for (size_t i = 0; i < N; i++)//遍历寻找
{
if (p->arr[i] == x)//找到了,i是对对应的下标
{
//挪动覆盖即可
for (size_t j = i + 1; j < p->size; j++)
{
p->arr[j - 1] = p->arr[j];
}
p->size--;
}
}
}
//顺序表的修改功能
void ModifyData(SeqList* p, Datatype x, Datatype y)
{
for (size_t i = 0; i < N; i++)//遍历寻找
{
if (p->arr[i] == x)//找到了,i是对对应的下标
{
p->arr[i] = y;//把对应的值改掉即可
}
}
}测试代码.c文件
#include "SeqList.h"
void test1(SeqList* p)
{
InitSeqList(p);
AddData(p, 1);
AddData(p, 2);
AddData(p, 3);
AddData(p, 4);
AddData(p, 5);
ShowSeqList(p);
DeleteData(p, 3);
ShowSeqList(p);
AddData(p, 5);
ShowSeqList(p);
ModifyData(p, 5, 0);
ShowSeqList(p);
}
int main()
{
SeqList op;
test1(&op);
return 0;
}4.小结
以上就是博主在学习数据结构中以自己的构思写的静态顺序表，写法不唯一，但静态顺序表在实际开发中并不怎么被使用，原因在于太固定了，不够灵活，要么数组大小太大，浪费空间；要么数组太小，存不下太多东西。
动态顺序表的实现
1.前期准备
a.创建工程时，和静态顺序表一样，这里不过多赘述。
b.浅浅定义好结构体
typedef int Datatype;
typedef struct SeqList
{
Datatype* arr;//指针管理开辟的空间
size_t size;//有效数据的个数
size_t Capacity;//容量大小
}SeqList;2.接口的实现
.h文件：
//顺序表的初始化
void InitSeqList();
//顺序表的扩容
void CheckCapacity();
//顺序表的展示
void PrintSeqList();
//顺序表的尾插
void PushBack();
//顺序表的尾删
void PopBack();
//顺序表的头插
void PushFront();
//顺序表的头删
void PopFront();
//顺序表的查找
void FindSeqList();//统计出个数
size_t FindSeqList1();//返回首先找到的元素的下标
//顺序表任意位置的插入
void InsertSeqList();//插入到当前下标位置的后面一个位置
void InsertSeqList1();//插入到当前下标位置
//顺序表任意位置的删除
void EraseSeqList();
//顺序表任意元素的删除
void EraseSeqList1();
//顺序表任意位置的修改
void ModifySeqList();
//顺序表任意元素的修改
void ModifySeqList1();
//顺序表的销毁
void DestorySeqList();🤔思考：参数传值还是传址？
SeqList.c文件：
//顺序表的初始化void InitSeqList()
//顺序表的初始化
void InitSeqList(SeqList* p)
{
assert(p);//这个可写可不写，因为操作系统生成p这个变量还是有空间的
p->arr = NULL;
p->size = 0;
p->Capacity = 0;
}
☑️发现确实初始化成功。
//顺序表的扩容void CheckCapacity();
//顺序表的扩容
void CheckCapacity(SeqList* p)
{
assert(p);
if (p->size == p->Capacity)//扩容判断条件，这里选扩容两倍
{
SeqList* tem = (SeqList*)realloc(p->arr, 2 * p->Capacity * (sizeof(Datatype)));
if (tem == NULL)//扩容失败
{
perror("reallc fail\n");//打印扩容失败的原因
exit(-1);//退出程序
}
else//扩容成功
{
p->arr = tem;
p->Capacity *= 2;//更新容量大小
tem = NULL;//tem指针为局部变量可置空可不置
}
}
}🤔思考：有啥问题没有？
😶明显初始化的时候，给的容量和有效数据个数都为0，这里不做处理的话就会出bug。
注：局部变量tem不置空，出了函数体tem一样会被销毁。调用assert函数记得引用头文件assert.h；调用realloc函数和记得引用头文件stdlib.h。
☑️扩容函数确实有问题
改为：
//顺序表的扩容
void CheckCapacity(SeqList* p)
{
assert(p);
if (p->size == p->Capacity)//扩容判断条件，这里选扩容两倍
{
if (p->Capacity == 0)//先考虑容量为0的特殊情况
{
p->Capacity = 2;
}
SeqList* tem = (SeqList*)realloc(p->arr, 2 * p->Capacity * (sizeof(Datatype)));
if (tem == NULL)//扩容失败
{
perror("reallc fail\n");//打印扩容失败的原因
exit(-1);//退出程序
}
else//扩容成功
{
p->arr = tem;
p->Capacity *= 2;//更新容量大小
tem = NULL;//tem指针为局部变量可置空可不置
}
}
}
☑️good，处理容量为0的情况（这个根据初始化容量大小给的多少，我这里是初始化的时候容量给0了，所以在扩容的时候要优先考虑容量为0的情况，如果你不是扩容几倍的话也不用考虑容量是否为0的情况），不然会产生bug。
//顺序表的尾插void PushBack()
//顺序表的尾插
void PushBack(SeqList* p, Datatype x)
{
assert(p);
CheckCapacity(p);//检查容量，确保容量大于有效数据个数，保证能插入数据
//p->arr[p->size] = x;
//p->size++;
p->arr[p->size++] = x;
}
☑️good，不仅尾插成功了，而且我插入5个数据，容量也确实扩大了两倍！完美符合预期。
//顺序表的尾删void PopBack()
//顺序表的尾删
void PopBack(SeqList* p)
{
assert(p);
p->size--;//有效个数-1即可
}🤔思考：有啥问题没有？
😶万一有效数据个数size已经为0了呢？再--，又因为size是个size_t类型（无符号整型），都不知道减哪里去了哈哈哈。
☑️千万别小瞧了这个哦，因为在打印顺序表的时候，是不是要根据有效数据个数size来确定打印几个数据？这个时候size这么大？但是容量也就是开辟的空间有那么大吗？越界那么大，直接程序就崩了。下面给你验证一下VS2022会给出啥错误提示吧。
改为：
//顺序表的尾删
void PopBack(SeqList* p)
{
assert(p);
if (p->size == 0)//处理一下有效个数为0的情况
{
printf("顺序表已为空，无需删除\n");//提示一下
return;
}
p->size--;//有效个数-1即可
}
☑️Ok，符合预期。
//顺序表的展示void PrintSeqList()
//顺序表的展示
void PrintSeqList(SeqList* p)
{
assert(p);
for (size_t i = 0; i < p->size; i++)//打印这size个有效数据个数
{
printf("%d ", p->arr[i]);
}
printf("\n");//无别的意思，换个行，方便观察
}🤔思考：size = 0时，会有影响吗？
😶size = 0时，不进循环，不打印数据，没影响，但是我想提示一下size = 0的情况。
改为：
//顺序表的展示
void PrintSeqList(SeqList* p)
{
assert(p);
if (p->size == 0)
{
printf("NULL");//提示一下
}
for (size_t i = 0; i < p->size; i++)//打印这size个有效数据个数
{
printf("%d ", p->arr[i]);
}
printf("\n");//无别的意思，换个行，方便观察
}
🤔思考：程序为啥崩了呢？
😶哈哈哈，调试给你看看：
定位这条语句，啥意思呢？翻译过来就是读写发生冲突。那为啥会这样呢？我们来看realloc的参数，p->arr，思考arr我们初始化了吗？那它的值是个随机值，被当做地址处理了，但是那块地址我们又没申请，怎么可以通过p对arr解引用访问呢？
吓得博主赶紧去初始化。
☑️okk，再去试试把数据删空，看是否能打印我对于数据个数为0的处理。
☑️ferfect，跟预期一毛一样。
补充：对于尾删不处理有效个数为0的情况，试试尾删多了，打印的时候会出什么bug
果然崩了，对于size_t类型的size，当size = 0时，size--，这个数会反向增大，结果就是size远大于容量，这肯定就崩了。从这里结合上述未初始化顺序表还能看出当发生读写冲突时大概就是数组越界了。（对于越界一点点VS会报错误，比如int arr[10],你去访问arr[10]，这时候访问越界，VS会报错误，但是对于arr[1000]，能运行起来，但是程序会崩了，体现在：...已退出，（退出）代码为一堆乱七八糟的数字，不是正常的return 0，这个退出是程序崩了的退出，调试上表现为发生异常，读写访问冲突。这里博主就不证明了哈，不是本篇的重点。）
//顺序表的头插void PushFront()
数据结构这里比较重要的一点是画好逻辑图。
挪动覆盖，把i-i位置上的数据copy到i对应的位置上，也可以下面这样Ovo
这里我用第一种吧。
//顺序表的头插
void PushFront(SeqList* p, Datatype x)
{
assert(p);
CheckCapacity(p);//检查容量，确保容量大于有效数据个数，保证能插入数据
//挪动覆盖
for (size_t i = p->size; i > 0; i--)
{
p->arr[i] = p->arr[i - 1];
}
//插入数据
p->arr[0] = x;
//更新有效数据个数
p->size++;
}
☑️顺序表没数据时也完全可以插入，不会出bug，因为不进for循环挪动且容量大于当前有效数据个数，保证能插入数据，只不过size只需要更新一下即可。使用第二种那可就坑太多了！建议踩踩。
//顺序表的头删void PopFront()
先不着急写代码，先把逻辑理清。
这次我要选择第二种了！因为i从下标为1开始的话，万一顺序表无数据呢？那不就越界了吗？
//顺序表的头删
void PopFront(SeqList* p)
{
assert(p);
//挪动覆盖
for (size_t i = 0; i < p->size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
//更新有效数据个数
p->size--;
}
这是头删五次的运行结果，那如果五次以上呢？也就是说数据空了，我接着删！
这就是程序崩了导致的退出，来看看因为啥崩了。
好好好，又是因为越界了，哈哈哈，为啥呢？一步一步（F11）调试的时候会发现居然size = 0的时候，循环竟然还进去了！为啥会进去？难道i = 0的时候小于p->size - 1了？嗯，没错！因为p->size是个size_t类型的变量，size-1时，你猜它等于几？没错，又是那个巨大的数！
于是我试着强转
结果还是能进循环（意味着判断条件0<-1居然进循环了？）这里引入一下大佬的文章size_t与int进行比较时的陷阱_vector的size无法和int进行比较_arccosY的博客-CSDN博客
确实这里比较的时候有陷阱。okk回归重点！即使这样p->size = 0，再跳过循环size--，不还是会在打印的时候出bug吗？
☑️该崩还得崩，主要原因是要去判断没数据时就不用--了。
改为：
//顺序表的头删
void PopFront(SeqList* p)
{
assert(p);
//if (p->size == 0)
//{
// printf("顺序表已空，无须删除\n");//提示一下
// return;
//}
if (p->size > 0)//有数据才能--
{
//挪动覆盖
for (size_t i = 0; i < p->size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
//更新有效数据个数
p->size--;
}
}☑️这两种改法都ok。
//顺序表的查找void FindSeqList()//统计出个数
//顺序表的查找
void FindSeqList(SeqList* p, Datatype x)//统计出个数
{
assert(p);
//遍历寻找是否有要查找的元素
size_t i;
size_t count = 0;//记录有几个这样的数
for (i = 0; i < p->size; i++)
{
if (p->arr[i] == x)
{
count++;
}
}
if (count == 0)//遍历完没找到要查找的数据而退出循环
{
printf("你要查找的元素是%d,共有%d个，下标分别是：", x, count);
}
else//表示在size个数据前找到跳出的循环而不是遍历完了没找到退出循环
{
printf("共有%d个，下标分别是：", count);
for (size_t i = 0; i < p->size; i++)
{
if (p->arr[i] == x)
{
printf("%d ", i);
}
}
printf("\n");//换个行，方便观察
}
}
//size_t FindSeqList1();//返回首先找到的元素的下标
size_t FindSeqList1(SeqList* p, Datatype x)//返回首先找到的元素的下标
{
assert(p);
//遍历寻找
size_t i;
for (i = 0; i < p->size; i++)
{
if (p->arr[i] == x)
{
return i;//返回首个查找到的元素的下标
}
}
if (i == p->size)//遍历完数组没找到元素而退出的循环
{
return -1;//没找到
}
}🤔思考：这样有问题没？
😶肯定有问题啊！返回-1怎么能被函数的返回类型size_t接收呢？
所以把size_t改为int即可。
//顺序表任意位置的插入void InsertSeqList()//插入到当前下标位置的后面一个位置
//顺序表任意位置的插入
void InsertSeqList(SeqList* p, size_t pos, Datatype x)//插入到当前下标位置的后面一个位置
{
assert(p);
CheckCapacity(p);
//将pos位置后面的数据挪动覆盖
for (size_t i = p->size - 1; i > pos; i++)
{
p->arr[i + 1] = p->arr[i];
}
//插入数据到pos位置后面
p->arr[pos + 1] = x;
//更新size
p->size++;
}
好像成功了哦，但毕竟是好像！
crazy！i = 184467......居然在判断条件的时候小于pos（0）跳出了循环，但这还不是更要命的！最重要的是它插到size后面去了！怎么打印出来呢？这才是最要命的！表明上没bug其实调试一看，有很大的bug。
改正：
//顺序表任意位置的插入
void InsertSeqList(SeqList* p, size_t pos, Datatype x)//插入到当前下标位置的后面一个位置
{
assert(p);
CheckCapacity(p);
if (p->size > 0 && p->size > pos)//在数据的后面插入的前提是有数据&&在某个数据后面插入，那他的下标肯定小于有效数据的个数
{
//将pos位置后面的数据挪动覆盖
for (size_t i = p->size - 1; i > pos; i++)
{
p->arr[i + 1] = p->arr[i];
}
//插入数据到pos位置后面
p->arr[pos + 1] = x;
//更新size
p->size++;
}
else if (p->size <= pos)//这种p->size等不等于0都一样
{
if (p->size == 0 && p->size == pos)//这种特殊情况就尾插
{
PushBack(p, x);
}
else
printf("无效插入!\n");
}
}
这个是最开始写的，有点bug后来改为了上面那种。
一一测试一下，防止有bug
就是设置值去把自己的逻辑都走一遍，看是否跟自己的代码逻辑一致。
也是完全ok，和自己想要的功能一样。
void InsertSeqList1()//插入到当前下标位置
单纯只是想退出循环的时候是i = pos，所以不用i和i+1。
void InsertSeqList1(SeqList* p, size_t pos, Datatype x)//插入到当前下标位置
{
assert(p);
CheckCapacity(p);
if (p->size >= pos)//保证插入的数据下标小于等于size
{
if (p->size == 0 && p->size == pos)//特殊情况，无数据时的插入
{
p->arr[pos] = x;
p->size++;
}
else if (p->size > pos)//我这里设置只能插size - 1之前的，因为有size个数据
{
for (size_t i = p->size; i > pos; i--)//挪动覆盖
{
p->arr[i] = p->arr[i - 1];
}
p->arr[pos] = x;
p->size++;
}
}
else
printf("无效插入\n");
}
也可以在else if后再加一条else if (p->size == pos) printf("无效插入\n”);//提示一下。
//顺序表任意位置的删除void EraseSeqList()
//顺序表任意位置的删除
void EraseSeqList(SeqList* p, size_t pos)
{
assert(p);
//挪动覆盖即可
if (p->size > 0 && p->size >= pos)//有数据才能这样挪
{
for (size_t i = pos; i < p->size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
//更新size
p->size--;
}
}这里就不写pos>size的情况打印提示：无效数据的删除了。
//顺序表任意元素的删除void EraseSeqList1()
//顺序表任意元素的删除
void EraseSeqList1(SeqList* p, Datatype x)
{
//这里联系前面的查找返回下标写一个，效率会低一点
assert(p);
int ret = FindSeqList1(p, x);//遍历一遍的情况，接收暗号
if (ret == -1)//遍历一遍还没找到就没有该元素
{
printf("顺序表无该元素\n");
return;
}
while (ret != -1)//这是遍历一遍至少有一个该元素
{
EraseSeqList(p, ret);
ret = FindSeqList1(p, x);//找下一个下标
}
}
//顺序表任意位置的修改void ModifySeqList()
//顺序表任意位置的修改
void ModifySeqList(SeqList* p, size_t pos, Datatype x)
{
if (p->size == 0 || p->size <= pos)//pos肯定要在最大下标之前
{
printf("该位置无数据，无需修改\n");
return;
}
p->arr[pos] = x;//修改
}
//顺序表任意元素的修改void ModifySeqList1()
//顺序表任意元素的修改
void ModifySeqList1(SeqList*p, Datatype x, Datatype y)
{
assert(p);
int ret = FindSeqList1(p, x);//遍历一遍看能找得到不
if (ret == -1)
{
printf("该位置无数据，无需修改\n");
return;
}
while (ret != -1)
{
ModifySeqList(p, ret, y);//找到下标修改
ret = FindSeqList1(p, x);//找下一个下标
}
}
注：以上的任意元素的修改和删除并不是最优效率！只是为了联系我写的那些函数。
//顺序表的销毁void DestorySeqList()
所以别单纯的把arr置空，而是应该先把arr指向的那块空间显free掉。
//顺序表的销毁
void DestorySeqList(SeqList* p)
{
free(p->arr);
p->arr = NULL;
p->Capacity = p->size = 0;//置空即可
}
3.完整代码展示
.h文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int Datatype;
typedef struct SeqList
{
Datatype* arr;//指针管理开辟的空间
size_t size;//有效数据的个数
size_t Capacity;//容量大小
}SeqList;
//顺序表的初始化
void InitSeqList(SeqList*);
//顺序表的扩容
void CheckCapacity(SeqList*);
//顺序表的展示
void PrintSeqList(SeqList*);
//顺序表的尾插
void PushBack(SeqList*, Datatype);
//顺序表的尾删
void PopBack(SeqList*);
//顺序表的头插
void PushFront(SeqList*, Datatype);
//顺序表的头删
void PopFront(SeqList*);
//顺序表的查找
void FindSeqList(SeqList*, Datatype);//统计出个数
int FindSeqList1(SeqList*, Datatype);//返回首先找到的元素的下标
//顺序表任意位置的插入
void InsertSeqList(SeqList*, size_t, Datatype);//插入到当前下标位置的后面一个位置
void InsertSeqList1(SeqList*, size_t, Datatype);//插入到当前下标位置
//顺序表任意位置的删除
void EraseSeqList(SeqList*, size_t);
//顺序表任意元素的删除
void EraseSeqList1(SeqList*, Datatype);
//顺序表任意位置的修改
void ModifySeqList(SeqList*, size_t, Datatype);
//顺序表任意元素的修改
void ModifySeqList1(SeqList*, Datatype, Datatype);
//顺序表的销毁
void DestorySeqList(SeqList*);SeqList.c接口功能的实现：
#include "SeqList.h"
//顺序表的初始化
void InitSeqList(SeqList* p)
{
assert(p);
p->arr = NULL;
p->size = 0;
p->Capacity = 0;
}
//顺序表的扩容
void CheckCapacity(SeqList* p)
{
assert(p);
if (p->size == p->Capacity)//扩容判断条件，这里选扩容两倍
{
if (p->Capacity == 0)//先考虑容量为0的特殊情况
{
p->Capacity = 2;
}
SeqList* tem = (SeqList*)realloc(p->arr, 2 * p->Capacity * (sizeof(Datatype)));
if (tem == NULL)//扩容失败
{
perror("reallc fail\n");//打印扩容失败的原因
exit(-1);//退出程序
}
else//扩容成功
{
p->arr = tem;
p->Capacity *= 2;//更新容量大小
tem = NULL;//tem指针为局部变量可置空可不置
}
}
}
//顺序表的尾插
void PushBack(SeqList* p, Datatype x)
{
assert(p);
CheckCapacity(p);//检查容量，确保容量大于有效数据个数，保证能插入数据
//p->arr[p->size] = x;
//p->size++;
p->arr[p->size++] = x;
}
//顺序表的尾删
void PopBack(SeqList* p)
{
assert(p);
//if (p->size == 0)//处理一下有效个数为0的情况
//{
// printf("顺序表已为空，无需删除\n");//提示一下
// return;
//}
p->size--;//有效个数-1即可
}
//顺序表的展示
void PrintSeqList(SeqList* p)
{
assert(p);
if (p->size == 0)
{
printf("NULL");//提示一下
}
for (size_t i = 0; i < p->size; i++)//打印这size个有效数据个数
{
printf("%d ", p->arr[i]);
}
printf("\n");//无别的意思，换个行，方便观察
}
//顺序表的头插
void PushFront(SeqList* p, Datatype x)
{
assert(p);
CheckCapacity(p);//检查容量，确保容量大于有效数据个数，保证能插入数据
//挪动覆盖
for (size_t i = p->size; i > 0; i--)
{
p->arr[i] = p->arr[i - 1];
}
//插入数据
p->arr[0] = x;
//更新有效数据个数
p->size++;
}
//顺序表的头删
void PopFront(SeqList* p)
{
assert(p);
if (p->size == 0)
{
printf("顺序表已空，无须删除\n");//提示一下
return;
}
//if (p->size > 0)//有数据才能--
//{
//挪动覆盖
for (size_t i = 0; i < p->size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
//更新有效数据个数
p->size--;
//}
}
//顺序表的查找
void FindSeqList(SeqList* p, Datatype x)//统计出个数
{
assert(p);
//遍历寻找是否有要查找的元素
size_t i;
size_t count = 0;//记录有几个这样的数
for (i = 0; i < p->size; i++)
{
if (p->arr[i] == x)
{
count++;
}
}
if (count == 0)//遍历完没找到要查找的数据而退出循环
{
printf("顺序表无该元素\n");//提示一下
}
else//表示在size个数据前找到跳出的循环而不是遍历完了没找到退出循环
{
printf("你要查找的元素是%d,共有%d个，下标分别是：", x, count);
for (size_t i = 0; i < p->size; i++)
{
if (p->arr[i] == x)
{
printf("%d ", i);
}
}
printf("\n");//换个行，方便观察
}
}
int FindSeqList1(SeqList* p, Datatype x)//返回首先找到的元素的下标
{
assert(p);
//遍历寻找
size_t i;
for (i = 0; i < p->size; i++)
{
if (p->arr[i] == x)
{
return i;//返回首个查找到的元素的下标
}
}
if (i == p->size)//遍历完数组没找到元素而退出的循环
{
return -1;//没找到
}
}
//顺序表任意位置的插入
void InsertSeqList(SeqList* p, size_t pos, Datatype x)//插入到当前下标位置的后面一个位置
{
assert(p);
CheckCapacity(p);
if (p->size > 0 && p->size > pos)//在数据的后面插入的前提是有数据&&在某个数据后面插入，那他的下标肯定小于有效数据的个数
{
//将pos位置后面的数据挪动覆盖
for (size_t i = p->size - 1; i > pos; i++)
{
p->arr[i + 1] = p->arr[i];
}
//插入数据到pos位置后面
p->arr[pos + 1] = x;
//更新size
p->size++;
}
else if (p->size <= pos)//这种p->size等不等于0都一样
{
if (p->size == 0 && p->size == pos)//这种特殊情况就尾插
{
PushBack(p, x);
}
else
printf("无效插入!\n");
}
}
void InsertSeqList1(SeqList* p, size_t pos, Datatype x)//插入到当前下标位置
{
assert(p);
CheckCapacity(p);
if (p->size >= pos)//保证插入的数据下标小于等于size
{
if (p->size == 0 && p->size == pos)//特殊情况，无数据时的插入
{
p->arr[pos] = x;
p->size++;
}
else if (p->size > pos)//我这里设置只能插size - 1之前的，因为有size个数据
{
for (size_t i = p->size; i > pos; i--)//挪动覆盖
{
p->arr[i] = p->arr[i - 1];
}
p->arr[pos] = x;
p->size++;
}
}
else
printf("无效插入\n");
}
//顺序表任意位置的删除
void EraseSeqList(SeqList* p, size_t pos)
{
assert(p);
//挪动覆盖即可
if (p->size > 0 && p->size >= pos)//有数据才能这样挪
{
for (size_t i = pos; i < p->size - 1; i++)
{
p->arr[i] = p->arr[i + 1];
}
//更新size
p->size--;
}
}
//顺序表任意元素的删除
void EraseSeqList1(SeqList* p, Datatype x)
{
//这里联系前面的查找返回下标写一个，效率会低一点
assert(p);
int ret = FindSeqList1(p, x);//遍历一遍的情况，接收暗号
if (ret == -1)//遍历一遍还没找到就没有该元素
{
printf("顺序表无该元素\n");
return;
}
while (ret != -1)//这是遍历一遍至少有一个该元素
{
EraseSeqList(p, ret);
ret = FindSeqList1(p, x);//找下一个下标
}
}
//顺序表任意位置的修改
void ModifySeqList(SeqList* p, size_t pos, Datatype x)
{
if (p->size == 0 || p->size <= pos)//pos肯定要在最大下标之前
{
printf("该位置无数据，无需修改\n");
return;
}
p->arr[pos] = x;//修改
}
//顺序表任意元素的修改
void ModifySeqList1(SeqList*p, Datatype x, Datatype y)
{
assert(p);
int ret = FindSeqList1(p, x);//遍历一遍看能找得到不
if (ret == -1)
{
printf("该位置无数据，无需修改\n");
return;
}
while (ret != -1)
{
ModifySeqList(p, ret, y);//找到下标修改
ret = FindSeqList1(p, x);//找下一个下标
}
}
//顺序表的销毁
void DestorySeqList(SeqList* p)
{
free(p->arr);
p->arr = NULL;
p->Capacity = p->size = 0;//置空即可
}测试代码.c文件
#include "SeqList.h"
void test1(SeqList* p)
{
InitSeqList(p);
//CheckCapacity(p);
PushBack(p, 1);
PushBack(p, 2);
PushBack(p, 3);
PushBack(p, 4);
PushBack(p, 5);
PopBack(p);
PopBack(p);
PopBack(p);
PopBack(p);
PopBack(p);
PopBack(p);
PrintSeqList(p);
}
void test2(SeqList* p)
{
InitSeqList(p);
PushBack(p, 1);
PushBack(p, 2);
PushBack(p, 3);
PushBack(p, 4);
PushBack(p, 5);
PrintSeqList(p);
PopBack(p);
PrintSeqList(p);
PopBack(p);
PrintSeqList(p);
PopBack(p);
PrintSeqList(p);
PopBack(p);
PrintSeqList(p);
PopBack(p);
PrintSeqList(p);
}
void test3(SeqList* p)
{
InitSeqList(p);
PushFront(p, 5);
PrintSeqList(p);
PushFront(p, 4);
PrintSeqList(p);
PushFront(p, 3);
PrintSeqList(p);
PushFront(p, 2);
PrintSeqList(p);
PushFront(p, 1);
PrintSeqList(p);
PopFront(p);
PrintSeqList(p);
PopFront(p);
PrintSeqList(p);
PopFront(p);
PrintSeqList(p);
PopFront(p);
PrintSeqList(p);
PopFront(p);
PrintSeqList(p);
PopFront(p);//第六次头删，对着空顺序表删
PrintSeqList(p);
}
void test4(SeqList* p)
{
InitSeqList(p);
PushBack(p, 1);
PrintSeqList(p);
PushBack(p, 2);
PrintSeqList(p);
PushBack(p, 3);
PrintSeqList(p);
PushBack(p, 3);
PrintSeqList(p);
PushBack(p, 4);
PrintSeqList(p);
FindSeqList(p, 0);
FindSeqList(p, 1);
FindSeqList(p, 3);
FindSeqList(p, 4);
int a = FindSeqList1(p, 0);
int b = FindSeqList1(p, 1);
int c = FindSeqList1(p, 3);
int d = FindSeqList1(p, 4);
}
void test5(SeqList* p)
{
InitSeqList(p);
InsertSeqList(p, 0, 0);
PrintSeqList(p);
InsertSeqList(p, 1, 0);
PrintSeqList(p);
InsertSeqList(p, 3, 0);
PrintSeqList(p);
InsertSeqList(p, 0, 1);
PrintSeqList(p);
InsertSeqList(p, 1, 2);
PrintSeqList(p);
}
void test6(SeqList* p)
{
InitSeqList(p);
InsertSeqList1(p, 0, 0);//无数据时的插入
PrintSeqList(p);
InsertSeqList1(p, 0, -1);//头插
PrintSeqList(p);
InsertSeqList1(p, 1, 1);//中间插
PrintSeqList(p);
InsertSeqList1(p, 3, 2);//假尾插
PrintSeqList(p);
InsertSeqList1(p, 4, 2);//无效插入
PrintSeqList(p);
}
void test7(SeqList* p)
{
InitSeqList(p);
EraseSeqList(p, 0);//为空的时候删删试试会不会出bug
PrintSeqList(p);
PushBack(p, 1);//造几组数据
PushBack(p, 2);
PushBack(p, 3);
PushBack(p, 4);
PushBack(p, 5);
PrintSeqList(p);
EraseSeqList(p, 0);//头删
PrintSeqList(p);
EraseSeqList(p, 3);//尾删
PrintSeqList(p);
EraseSeqList(p, 1);//中间删
PrintSeqList(p);
}
void test8(SeqList* p)
{
InitSeqList(p);
PushBack(p, 1);//造元素
PushBack(p, 2);
PushBack(p, 3);
PushBack(p, 3);
PushBack(p, 4);
PushBack(p, 4);
PushBack(p, 4);
PushBack(p, 5);
PrintSeqList(p);
EraseSeqList1(p, 0);//验证没找到的暗号
EraseSeqList1(p, 1);//头删
PrintSeqList(p);
EraseSeqList1(p, 3);//群删
PrintSeqList(p);
}
void test9(SeqList* p)
{
InitSeqList(p);
ModifySeqList(p, 0, 0);//无数据时
PushBack(p, 1);//造数据
PushBack(p, 2);
PushBack(p, 3);
PushBack(p, 4);
PushBack(p, 5);
PrintSeqList(p);
ModifySeqList(p, 5, 0);//pos == size
ModifySeqList(p, 0, 0);//头修
PrintSeqList(p);
ModifySeqList(p, 4, 0);//尾修
PrintSeqList(p);
ModifySeqList(p, 2, 0);//中间修
PrintSeqList(p);
}
void test10(SeqList* p)
{
InitSeqList(p);
ModifySeqList1(p, 0, 1);//无元素时的试探
//造数据
PushBack(p, 1);
PushBack(p, 2);
PushBack(p, 3);
PushBack(p, 3);
PushBack(p, 5);
PrintSeqList(p);
ModifySeqList1(p, 1, -1);//修改头
PrintSeqList(p);
ModifySeqList1(p, 3, -3);//修改群
PrintSeqList(p);
DestorySeqList(p);
}
int main()
{
SeqList op;
//test1(&op);
//test2(&op);
//test3(&op);
//test4(&op);
//test5(&op);
//test6(&op);
//test7(&op);
//test8(&op);
//test9(&op);
test10(&op);
return 0;
}4.小结
以上就是博主分享的顺序表以及在敲代码中间遇到的一些常见问题和易错的地方，由于篇幅问题，后面还有一些遇到的问题就不展示了。其实用int类型来代替size_t类型可能会简单挺多，但我们始终要明白，锻炼自己的调试能力也是提高自己代码能力的一个重要途径。感谢各位观看，祝大家在学习C语言数据结构的道路上越走越远！