前言
本章主要讲解：
顺序表以及顺序表的接口实现
注：保姆级教程，相信你一定会的~
顺序表
顺序表是线性标的一种
- 概念：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储（完成数据的增删查改）
- 分类：
静态顺序表
使用定长数组存储元素
参考代码：
//静态循序表 #define CAPACITY 100 typedef struct SeqList { SLDateType data[CAPACITY];//动态开辟指向其地址 size_t size;//已经使用的数量 }SeqList;
图示：
动态顺序表：
使用动态开辟的数组存储
- 参考代码：
//动态顺序表 typedef struct SeqList { SLDateType* data;//动态开辟指向其地址 size_t size;//已经使用的数量 size_t capacity; //开辟空间的总大小（容量） }SeqList;
接口实现
- 静态顺序表：
只适用于确定知道需要存多少数据的场景
局限：静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用
- 动态顺序表：
现实使用时多采用动态顺序表
优势：需要多少用多少
注：下面我们着重实现动态顺序表（静态顺序表可以依法炮制~）
各项功能
顺序表的增删查改接口
//默认开辟大小 #define DEFAULT_SZ 4 //设定默认数据类型 typedef int SLDateType; //动态顺序表 typedef struct SeqList { SLDateType* data;//动态开辟指向其地址 size_t size;//已经使用的数量 size_t capacity; //开辟空间的总大小（容量） }SeqList; // 对数据的管理:增删查改 //初始化 void SeqListInit(SeqList* ps); //释放 void SeqListDestory(SeqList* ps); //打印（展示） void SeqListPrint(SeqList* ps); //尾插 void SeqListPushBack(SeqList* ps, SLDateType x); //头插 void SeqListPushFront(SeqList* ps, SLDateType x); //前删 void SeqListPopFront(SeqList* ps); //尾删 void SeqListPopBack(SeqList* ps); // 顺序表查找x的位置 int SeqListFind(SeqList* ps, SLDateType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, size_t pos, SLDateType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, size_t pos);
接口详解
顺序表初始化
比较简单
- 参考代码：
//初始化顺序表 void SeqListInit(SeqList* ps)//传入链表地址便于修改 { ps->data = NULL; ps->capacity = 0; ps->size = 0; return; }
顺序表释放
动态顺序表是动态开辟的空间，结束时需要进行释放，避免造成内存泄漏
- 参考代码：
//摧毁释放顺序表 void SeqListDestory(SeqList* ps) { free(ps->data); //记得置空地址 ps = NULL; return; }
顺序表展示
- 注意：
- 当顺序表为空时不打印
//展示顺序表 void SeqListPrint(SeqList* ps) { //暴力断言（ps不为空） assert(ps->data); //使用指针打印结构体内保存的数据 for (int i = 0; i < ps->size; i++) { printf("%d\t", ps->data[i]); } return; }
顺序表容量检查
- 注意：
- 每当要增加数据时，都需要考虑空间是否使用完毕
- 如果使用完毕则需要考虑增容，增容为原来的两倍（避免频繁扩容）
- 增容后更新记录容量大小
注：这里我们考虑到有许多地方要检查是否增容，为了方便将它封装成一个函数
参考代码:
//顺序表容量判断 void SeqListCheak(SeqList* ps) { int newcapacity; //使用完毕时进行判断 if (ps->size == ps->capacity) { //如果为容量为0,则开辟默认大小的空间；否则扩容为原来的两倍空间 newcapacity = ps->capacity == 0 ? DEFAULT_SZ : ps->capacity* 2; //当data为NULL时，realloc的功能和malloc一致（申请开辟空间） ps->data = realloc(ps->data, newcapacity); //判断是否扩容（开辟）空间成功 if (ps == NULL) { //为开辟（扩容）成功，则打印对应的错误原因，并结束进程 perror("realloc:"); exit(1); } } //成功则更新记录容量的大小 ps->capacity = newcapacity; return; }
顺序表数据尾插
- 注意：
- 插入数据考虑扩容
- 尾插后更新记录使用数量
- 参考代码：
//顺序表数据尾插 void SeqListPushBack(SeqList* ps, SLDateType x) { //容量检查 SeqListCheak(ps); ps->data[ps->size]=x; //更新使用数量 ps->size++; printf("顺序表尾插数据成功！\n"); return; }
顺序表数据头插
- 注意：
- 插入数据考虑扩容
- 头插从后开始移动数据（避免数据覆盖）
- 尾插后更新记录使用数量
- 参考代码：
//顺序表头插数据 void SeqListPushFront(SeqList* ps, SLDateType x) { //插入数据考虑扩容 SeqListCheak(ps); for (int i = ps->size - 1; i >= 0; i--) { //头插从后开始移动数据（避免数据覆盖） ps->data[i + 1] = ps->data[i]; } ps->data[0]=x; //尾插后更新记录使用数量 ps->size++; printf("顺序表头插数据成功！\n"); return; }
顺序表数据前删
- 注意：
- 没有数据或者顺序表为空无法删除
- 前删后从前往后移动数据（避免覆盖）
- 更新记录使用的数量
参考代码：
//顺序表数据前删 void SeqListPopFront(SeqList* ps) { //暴力断言（也可以选择if判断语句） assert(ps->data||ps->size); //从前往后移动数据（避免覆盖） for (int i = 0; i+1<ps->size; i++) { ps->data[i] = ps->data[i+1]; } //更新记录使用的数量 ps->size--; printf("顺序表前删数据成功！\n"); return; }
顺序表数据尾删
- 注意：
- 没有数据或者顺序表为空无法删除
- 尾删数据只要记录使用数量的变量自减就行了
参考代码：
//顺序表尾删数据 void SeqListPopBack(SeqList* ps) { assert(ps->data||ps->size); ps->size--; printf("顺序表尾删数据成功！\n"); return; }
顺序表数据查找
- 注意：
- 没有数据或者顺序表为空无法查找
- 遍历查找，找到则返回下标，否则返回-1
- 参考代码：
// 顺序表查找 int SeqListFind(SeqList* ps, SLDateType x) { //没有数据或者顺序表为空无法查找 assert(ps->data||ps->size); //遍历查找，找到则返回下标，否则返回-1 int pos=-1; for (int i = 0; i < ps->size; i++) { if (ps->data[i] == x) { pos=i; printf("数据查到了，下标是：%d\n", pos); return pos; } } printf("链表数据未查到！\n"); return pos; }
顺序表指定位置插入数据
- 注意：
- 检查是否扩容
- 插入前先移动数据
- 插入后更新记录使用数量的大小
- 参考代码：
//顺序表在pos位置插入x void SeqListInsert(SeqList* ps, size_t pos, SLDateType x) { SeqListCheak(ps); for (int i = ps->size; i >= pos; i++) { ps->data[i] = ps->data[i - 1]; } printf("请输入要插入的数："); scanf("%d", &ps->data[pos]); ps->size++; printf("链表插入数据成功！\n"); return; }
以上基本上就已经讲解顺序表完毕了，别忘了留个三连再走~~
