【数据结构】顺序表介绍及代码实现 目录一、介绍二、顺序表的实现1.定义顺序表包含头文件...2.顺序表初始化3.顺序表销毁4.顺序表插入1尾部插入顺序表检查空间2头部插入5.顺序表打印6.顺序表删除1尾部删除2头部删除7.指定位置之前插入/删除数据1在下标为 pos 的位置插入数据 x2删除下标为 pos 的数据8.顺序表查找三、完整代码SeqList.hSeqList.c一、介绍顺序表是一种线性表是n个具有相同特性的数据元素的有限序列。常见的线性表顺序表、链表、栈、队列、字符串。线性表在逻辑上是线性结构你在物理上不一定是线性的通常以数组或链式结构的形式存储。顺序表的底层结构是数组所以顺序表的物理结构和逻辑结构都是线性的。顺序表的底层结构是数组通过对数组的封装实现了简单的增删改查等功能。顺序表分为静态顺序表使用定长数组存储元素和动态顺序表。一般使用的是动态顺序表。为了养成一个好的习惯我们将动态顺序表的实现分为3个文件test.c(测试用SeqList.c(写顺序表的方法)SeqList.h(定义顺序表的结构、声明顺序表的方法、添加程序需要的头文件)。二、顺序表的实现1.定义顺序表包含头文件...这一步在SeqList.h中完成在SeqList.h中需要包含的头文件有stdio.hstdlib.h动态申请内存#pragma once //确保头文件只被编译一次防止重复包含 #includestdio.h #includestdlib.h //动态申请内存的头文件 #define SLDataType int //给int起别名为SLDataType代表顺序表存储的数据类型方便后续修改 typedef struct SeqList { SLDataType* arr; int size; //有效数据个数 int capacity; //空间容量 }SL; //定义顺序表的结构并给顺序表重命名为SL2.顺序表初始化定义完顺序表紧接着就是完成顺序表的初始化。SeqList.hvoid SLInit(SL* ps);SeqList.carr指向空指针并将有效数据个数和空间容量赋值为0。//顺序表初始化 void SLInit(SL* ps) { ps-arr NULL; ps-size ps-capacity 0; }在text.c中测试刚刚定义的方法有没有错误#includeSeqList.h // 引入SeqList.h void SLTest01() { SL sl; //创建一个顺序表sl SLInit(sl); //调用SLInit(Sl * ps)传入sl的地址 } int main() { SLTest01(); // 调用SLTest01() return 0; }如果可以正常运行说明定义的方法没有问题可以继续定义下一个方法。3.顺序表销毁在对顺序表进行增删查改操作之后要将顺序表销毁。SeqList.hvoid SLDestroy(SL* ps);SeqList.c判断顺序表中的数组是否为空并重新将arr指向空指针并将有效数据个数和空间容量赋值为0。void SLDestroy(SL* ps) { if (ps-arr) // 判断顺序表中的数组是否为空如果不是空就释放空间 { free(ps-arr); } ps-arr NULL; // 将arr指向的地址变为空指针 ps-capacity ps-size 0; // 将有效数据个数和空间容量重新置为0 }依旧测试4.顺序表插入顺序表插入分为两个方法分别是头部插入和尾部插入1尾部插入SeqList.hvoid SLPushBack(SL* ps, SLDataType x);SeqList.c首先判断ps是否为空指针然后判断是否有空余空间如果没有空余就申请最后把 x 放入 arr 的尾部并将有效数据个数size1void SLPushBack(SL* ps, SLDataType x) // 尾部插入 { assert(ps); // 等价于 assert(ps!NULL) 判断ps是否为空指针如果是空指针直接结束程序 if (ps-size ps-capacity) // 当 size 和 capacity 的值相等时说明程序没有空余空间需要申请空间 { // 申请空间此处需要增容所以使用 realloc // 增容一般是成倍增加一般是二倍或三倍数学推理:为什么增容要以倍数增加 // 频繁增容会导致程序性能低下运行效率大大降低 // 增容过大会导致空间浪费 int newCapacity (ps-capacity 0) ? 4 : 2 * ps-capacity; // 使用三目操作符判断 capacity 是否为0如果为0赋一个初始值4如果不为0让 newCapacity 等于 capacity 的2倍 SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * sizeof(SLDataType)); // realloc(起始指针空间大小字节)字节数空间容量*单个元素所占字节数 // realloc 申请空间有可能失败所以先复制给临时变量 tmp ,确认没问题再复制给 arr if (tmp NULL) // 如果 tmp 为空指针说明 realloc 申请失败此时需要报出错误信息 { perror(realloc error!); exit(1); // 立即终止程序运1是返回给操作系统的状态码通常表示程序非正常退出比如遇到错误。 // 它会先清理一些资源比如关闭文件、清空缓冲区然后直接结束整个程序。 // 和 return 不同exit()可以在任何地方调用直接终止程序而 return 只是退出当前函数。 } // 空间申请成功把地址赋给 arr并把 newCapacity 赋给 capacity ps-arr tmp; ps-capacity newCapacity; } ps-arr[ps-size] x; }依旧测试顺序表检查空间因为顺序表在进行所有插入操作前都需要检查空间是否够用所以这里我们将检查空间是否够用的过程封装成函数。SeqList.hSLCheckCapacity(ps);SeqList.c// 检查空间是否够用 void SLCheckCapacity(SL* ps) { if (ps-size ps-capacity) // 当 size 和 capacity 的值相等时说明程序没有空余空间需要申请空间 { // 申请空间此处需要增容所以使用 realloc // 增容一般是成倍增加一般是二倍或三倍数学推理:为什么增容要以倍数增加 // 频繁增容会导致程序性能低下运行效率大大降低 // 增容过大会导致空间浪费 int newCapacity (ps-capacity 0) ? 4 : 2 * ps-capacity; // 使用三目操作符判断 capacity 是否为0如果为0赋一个初始值4如果不为0让 newCapacity 等于 capacity 的2倍 SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * sizeof(SLDataType)); // realloc(起始指针空间大小字节)字节数空间容量*单个元素所占字节数 // realloc 申请空间有可能失败所以先复制给临时变量 tmp ,确认没问题再复制给 arr if (tmp NULL) // 如果 tmp 为空指针说明 realloc 申请失败此时需要报出错误信息 { perror(realloc error!); exit(1); // 立即终止程序运1是返回给操作系统的状态码通常表示程序非正常退出比如遇到错误。 // 它会先清理一些资源比如关闭文件、清空缓冲区然后直接结束整个程序。 // 和 return 不同exit()可以在任何地方调用直接终止程序而 return 只是退出当前函数。 } // 空间申请成功把地址赋给 arr并把 newCapacity 赋给 capacity ps-arr tmp; ps-capacity newCapacity; } }2头部插入SeqList.hvoid SLPushBack(SL* ps, SLDataType x);SeqList.c首先判断ps是否为空指针然后判断是否有空余空间如果没有空余就申请使用 for 循环把 arr 中的每一个值向后移动一位最后把 x 放入 arr 的头部并将有效数据个数size1void SLPushFront(SL* ps, SLDataType x)// 头部插入 { assert(ps); SLCheckCapacity(ps); // 先检查空间是否够用 for (int i ps-size; i 0; i--) { ps-arr[i] ps-arr[i - 1]; } ps-arr[0] x; ps-size; }依旧测试5.顺序表打印为了方便调试可以每次修改完顺序表后将顺序表打印出来由于顺序表打印不需要对顺序表内部做任何修改所以函数参数可以传值SeqList.hvoid SLPrint(SL p);SeqList.c和数组打印的方法相同void SLPrint(SL p) { for (int i 0; i p.size; i) { printf(%d , p.arr[i]); } printf(\n); }依旧测试6.顺序表删除1尾部删除SeqList.hvoid SLPopBack(SL* ps);SeqList.c首先判断顺序表是否为空然后有效数据个数-1void SLPopBack(SL* ps)// 尾部删除 { assert(ps); assert(ps-size); // 判断顺序表有效数据个数是否为0 --ps-size; // 有效数据个数-1 }依旧测试2头部删除SeqList.hvoid SLPopFront(SL* ps);SeqList.c首先判断顺序表是否为空然后有效数据个数-1void SLPopFront(SL* ps)// 头部删除 { assert(ps); assert(ps-size); for (int i 0; i ps-size - 1; i) // 将数组中的数据向前移动一位 { ps-arr[i] ps-arr[i 1]; } ps-size--; }依旧测试7.指定位置之前插入/删除数据1在下标为 pos 的位置插入数据 xSeqList.hvoid SLInsert(SL* ps, int pos, SLDataType x);SeqList.c首先判断ps是否为空 因为 pos 是下标所以一定 0 并且 size检查空间是否够用将顺序表中下标为 pos 及 pos 之后的数据向后移动一位把 pos 空出把 x 插入到 pos 的位置有效数据个数1void SLInsert(SL* ps, int pos, SLDataType x) // 在下标为 pos 的位置插入数据 x { assert(ps); assert(pos 0 pos ps-size); // 因为 pos 是下标所以一定 0 并且 size SLCheckCapacity(ps); // 检查空间是否够用 for (int i ps-size; i pos; i--) // 将 pos 及之后的数据向后移动1位 { ps-arr[i] ps-arr[i - 1]; } ps-arr[pos] x; // 将 x 插入到 pos 处 ps-size; // 有效数据个数1 }依旧测试2删除下标为 pos 的数据SeqList.hvoid SLErase(SL* ps, int pos);SeqList.c首先判断ps是否为空 因为 pos 是下标所以一定 0 并且 size将顺序表中下标为 pos 及 pos 之后的数据向前移动一位有效数据个数-1void SLErase(SL* ps, int pos) // 删除 pos 处的数据 { assert(ps); assert(pos 0 pos ps-size); for (int i pos; i ps-size - 1; i) { ps-arr[i] ps-arr[i 1]; } ps-size--; }依旧测试8.顺序表查找SeqList.hint SLFind(SL* ps, SLDataType x);SeqList.c和数组查找的方法相同因为要返回查找数据所在位置的下标所以返回值为 int找到就返回下标值找不到就返回-1不能作为下标的数int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i 0; i ps-size; i) { if (ps-arr[i] x) { return i; } } return -1; }依旧测试三、完整代码SeqList.h#pragma once // 确保头文件只被编译一次防止重复包含 #includestdio.h #includestdlib.h // 动态申请内存的头文件 #includeassert.h // assert #define SLDataType int // 给 int 起别名为 SLDataType代表顺序表存储的数据类型方便后续修改 // 定义顺序表的结构、声明顺序表的方法 // 动态顺序表 typedef struct SeqList { SLDataType* arr; int size; // 有效数据个数 int capacity; // 空间容量 }SL; // 定义顺序表的结构并给顺序表重命名为SL // 顺序表初始化 void SLInit(SL* ps); // 顺序表检查空间 void SLCheckCapacity(SL* ps); // 顺序表销毁 void SLDestroy(SL* ps); // 顺序表打印 void SLPrint(SL p); // 顺序表插入 void SLPushBack(SL* ps, SLDataType x); // 尾部插入 void SLPushFront(SL* ps, SLDataType x);// 头部插入 // 顺序表删除 void SLPopBack(SL* ps); // 尾部删除 void SLPopFront(SL* ps);// 头部删除 // 指定位置之前插入、删除数据 void SLInsert(SL* ps, int pos, SLDataType x); void SLErase(SL* ps, int pos); // 顺序表查找 int SLFind(SL* ps, SLDataType x);SeqList.c#define _CRT_SECURE_NO_WARNINGS 1 #includeSeqList.h //顺序表初始化 void SLInit(SL* ps) { ps-arr NULL; ps-size ps-capacity 0; } //顺序表销毁 void SLDestroy(SL* ps) { if (ps-arr) // 判断顺序表中的数组是否为空如果不是空就释放空间 { free(ps-arr); } ps-arr NULL; // 将arr指向的地址变为空指针 ps-capacity ps-size 0; // 将有效数据个数和空间容量重新置为0 } // 顺序表打印 void SLPrint(SL p) { for (int i 0; i p.size; i) { printf(%d , p.arr[i]); } printf(\n); } // 检查空间是否够用 void SLCheckCapacity(SL* ps) { if (ps-size ps-capacity) // 当 size 和 capacity 的值相等时说明程序没有空余空间需要申请空间 { // 申请空间此处需要增容所以使用 realloc // 增容一般是成倍增加一般是二倍或三倍数学推理:为什么增容要以倍数增加 // 频繁增容会导致程序性能低下运行效率大大降低 // 增容过大会导致空间浪费 int newCapacity (ps-capacity 0) ? 4 : 2 * ps-capacity; // 使用三目操作符判断 capacity 是否为0如果为0赋一个初始值4如果不为0让 newCapacity 等于 capacity 的2倍 SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * sizeof(SLDataType)); // realloc(起始指针空间大小字节)字节数空间容量*单个元素所占字节数 // realloc 申请空间有可能失败所以先复制给临时变量 tmp ,确认没问题再复制给 arr if (tmp NULL) // 如果 tmp 为空指针说明 realloc 申请失败此时需要报出错误信息 { perror(realloc error!); exit(1); // 立即终止程序运1是返回给操作系统的状态码通常表示程序非正常退出比如遇到错误。 // 它会先清理一些资源比如关闭文件、清空缓冲区然后直接结束整个程序。 // 和 return 不同exit()可以在任何地方调用直接终止程序而 return 只是退出当前函数。 } // 空间申请成功把地址赋给 arr并把 newCapacity 赋给 capacity ps-arr tmp; ps-capacity newCapacity; } } // 顺序表插入 void SLPushBack(SL* ps, SLDataType x) // 尾部插入 { assert(ps); // 等价于 assert(ps!NULL) 判断ps是否为空指针如果是空指针直接结束程序 SLCheckCapacity(ps); //调用检查空间是否够用的函数 ps-arr[ps-size] x; } void SLPushFront(SL* ps, SLDataType x)// 头部插入 { assert(ps); SLCheckCapacity(ps); // 先检查空间是否够用 for (int i ps-size; i 0; i--) { ps-arr[i] ps-arr[i - 1]; } ps-arr[0] x; ps-size; } // 顺序表删除 void SLPopBack(SL* ps)// 尾部删除 { assert(ps); assert(ps-size); // 判断顺序表有效数据个数是否为0 --ps-size; // 有效数据个数-1 } void SLPopFront(SL* ps)// 头部删除 { assert(ps); assert(ps-size); for (int i 0; i ps-size - 1; i) // 将数组中的数据向前移动一位 { ps-arr[i] ps-arr[i 1]; } ps-size--; } // 指定位置之前插入、删除数据 void SLInsert(SL* ps, int pos, SLDataType x) // 在下标为 pos 的位置插入数据 x { assert(ps); assert(pos 0 pos ps-size); // 因为 pos 是下标所以一定 0 并且 size SLCheckCapacity(ps); // 检查空间是否够用 for (int i ps-size; i pos; i--) // 将 pos 及之后的数据向后移动1位 { ps-arr[i] ps-arr[i - 1]; } ps-arr[pos] x; // 将 x 插入到 pos 处 ps-size; // 有效数据个数1 } void SLErase(SL* ps, int pos) // 删除 pos 处的数据 { assert(ps); assert(pos 0 pos ps-size); for (int i pos; i ps-size - 1; i) { ps-arr[i] ps-arr[i 1]; } ps-size--; } // 顺序表查找v int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i 0; i ps-size; i) { if (ps-arr[i] x) { return i; } } return -1; }完