名称Doubletful的博客数据结构专栏签名路漫漫其修远兮吾将上下而求索文章目录前言一、概念1-线性表的基本概念2-顺序表的定义3-我的理解二、手撕实现0.5-准备1-头文件内容的总览1.1-初始化1.2-判断空间容量1.3-添加尾插数据1.4-增加头插数据1.5-删除尾部数据1.6-删除头部数据1.7-插入指定位置1.8-删除指定位置1.9-查找数据2.0-销毁顺序表2.5-一份测试代码3.0-静态顺序表简介三、总结1-与数组对比2-顺序表的问题及思考四、练习前言本博客将使用C语言实现基础数据结构——顺序表主要内容包括使用头文件声明、源文件定义的形式实现详细讲解顺序表的概念、实现原理和操作接口提供完整的代码示例和实际应用场景分析一、概念先来看看官方解释1-线性表的基本概念线性表(linear list)是相同类型的 n(n 0) 个数据元素的有限序列若用 L 命名为线性表则⼀般表示为 L (a 1 a_1a1,a 2 a_2a2, …,a i a_iai,a i 1 a_i1ai1, …,a n a_nan)。a i a_iai是表中的第 i 个数据元素称 i 为数据元素a i a_iai在线性表中的位序。注概念上数组下标从 0 开始位序从 1 开始容易混淆。2-顺序表的定义用顺序存储的方式实现线性表就是顺序表用链式存储的方式实现线性表就是链表(我们后面再专讲链表)。顺序存储把逻辑上相邻的数据元素存放在⼀段连续物理存储单元中数据元素之间的逻辑关系可以由物理存储关系体现。3-我的理解如果用一句话来概括顺序表就是“经过封装、拥有属性与接口函数的数组”。存储相同点数组可分为静态数组与动态数组顺序表也相应地分为静态顺序表和动态顺序表。并且静态顺序表在程序运行时不可更改动态顺序表能在程序运行时发生变化。以下是数组与顺序表的结构及物理存储位置示例图从图中可以发现顺序表和数组一样都是连续的存储空间且存储元素类型相同但顺序表还包含以下两个重要属性size 与 capacity。需特别注意 size 不仅能表示当前表中的元素个数还能告诉我们下一个执行尾插操作的位置与接口实现有关。这时可能产生一个疑惑应该如何让数组拥有容量与大小两个属性答使用结构体并且增删改查使用函数封装实现。二、手撕实现0.5-准备正式开始编辑前请先阅览以下前置知识assert()函数介绍C语言标准库中的调试宏用于在程序运行时检查条件是否成立。若条件为假0则输出错误信息文件、行号、表达式并调用 abort()终止程序若条件为真非0则无动作。常用于捕捉“不可能发生”的逻辑错误、验证函数前置条件等。perror()函数介绍C 语言标准库函数用于打印错误信息。调用格式perror(“前缀字符串”)输出格式为“前缀字符串错误原因\n”常用于系统调用或库函数失败后快速定位错误原因。exit()函数介绍C 语言标准库函数用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统0or EXIT_SUCCESS表示成功-1or EXIT_FAILURE表示失败。1-头文件内容的总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#防止头文件重复包含#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#方便类型替换typedefintSLDataType;#动态顺序表typedefstructSeqList{SLDataType*arr;intsize;#当前有效的数据个数intcapacity;#空间大小}SL;#初始化顺序表voidSLInit(SL*ps);#增加尾插数据voidSLPushBack(SL*ps,SLDataType x);#增加头插数据voidSLPushFront(SL*ps,SLDataType x);#删除尾部数据voidSLPopBack(SL*ps);#删除头部数据voidSLPopFront(SL*ps);#插入指定位置voidSLInsert(SL*ps,intpos,SLDataType x);#删除指定位置voidSLErase(SL*ps,intpos);#查找数据intSLFind(SL*ps,SLDataType x);#销毁顺序表voidSLDestroy(SL*ps);首先使用 typedef 为顺序表内存储的数据类型起别名便于日后进行修改与调整。其次在定义结构体时直接为顺序表起别名为 SL便于书写语法可理解为 “typedef 结构体类型 新类型名”。结构体内部包含三个成员变量arr 是指向动态存储空间的指针即尚未开辟空间的数组size 承担两个作用一是记录数组当前的有效元素个数二是表示下一个存入元素的下标位置最后是 capacity记录数组当前已开辟空间的容量。之后是使用函数封装的操作接口以下依次介绍。1.1-初始化注从1.1开始皆为源文件内容直接复制请记得引入头文件。voidSLInit(SL*ps){assert(ps);ps-arrNULL;ps-size0;ps-capacity0;}第一种初始化方式示例图传入一个顺序表结构体变量并断言传入的指针不为 NULL。初始化方式有两种第一种在初始化时直接使用 malloc 开辟空间并将容量赋值为开辟空间能容纳的元素个数此教程使用第二种在涉及到添加数据时再开辟空间避免空间浪费及忘记释放动态开辟的内存造成内存泄漏。1.2-判断空间容量voidSLCheckCapacity(SL*ps){if(ps-sizeps-capacity){intnewcapacity(ps-capacity0?4:ps-capacity*2);SLDataType*tmp(SLDataType*)realloc(ps-arr,newcapacity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail);exit(1);}ps-arrtmp;ps-capacitynewcapacity;}}这是未声明在头文件内的函数因为其并非对外调用接口而是实现添加接口所必备的内部函数。传入顺序表如果当前的大小与总容量相等则执行增容操作否则不变newcapacity 第一次增容为 4往后的增容规则是当前总容量乘以 2 倍增长经科学计算此为最合理的增容规则能相对减少增容次数减少 realloc 操作的消耗开辟新空间拷贝旧空间数据释放旧空间。由于 realloc 有增容失败的可能需判断是否成功失败则打印错误信息后结束程序通常不会失败成功后让结构体内的 arr 指向 tmp 指向的新空间并更新总容量。1.3-添加尾插数据voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);#尾插数据 ps-arr[ps-size]x;}传入顺序表与要添加的元素断言传入指针不为NULL判断容量。由于是在数组的尾部插入使用size找到当前尾部位置插入随后size。1.4-增加头插数据voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);#头插数据for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;}传入顺序表与要添加的元素断言传入指针不为NULL判断容量。——数组在头部插入数据需将整体元素向后移动一位i 从尾开始遍历使头部位置空缺此时原头部位置的数据有两份在数组中使用值x覆盖第一位后完成头插。语法细节增加元素后需使size在 for 循环定义 i 时完成操作因为该表达式只在 for 开始运作前执行一次接下来的条件判断令 i 0 防止越界操作从当前的size下标开始依次将前一个元素复制到当前位。1.5-删除尾部数据voidSLPopBack(SL*ps){assert(psps-size);#尾删数据 ps-size--;}传入顺序表断言传入指针不为NULL且表中元素个数不为0。——由于 size 永远都是下一个存入元素的下标位令 size–在下次有关添加操作时能直接覆盖删除元素这被称之为逻辑删除。1.6-删除头部数据voidSLPopFront(SL*ps){assert(psps-size);#头删数据for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}传入顺序表断言传入指针不为NULL且表中元素个数不为0。——头删时令整体元素向前移动一位i 从头开始遍历条件判断中令 i size - 1 或 i size 都可以两种做法都不会越界访问因为在 i 的最后位置 size - 1 到 size 的移动操作可忽略所以使用 i size - 1 的条件判断使其只移动有效元素(size - 1 移至 size - 2)依次将后一个元素复制到当前位。1.7-插入指定位置voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos0posps-size);SLCheckCapacity(ps);#指定位置插入for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;}传入顺序表、指定下标位与要添加的元素断言传入指针不为NULL且pos的位置合法(位置在数组中)判断容量。——当 pos 为0时相当于头插为 size 时相当于尾插因此合法。从末尾开始依次将前一个元素复制到当前位直到 pos 位置空缺(整体过程与头插类似)。1.8-删除指定位置voidSLErase(SL*ps,intpos){assert(psps-size);assert(pos0posps-size);#指定位置删除for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}传入顺序表及指定下标位断言传入指针不为NULL、表中元素个数不为0且pos的位置合法(位置为有效元素)。——当 pos 为0时相当于头删但为 size 时非法因为当前的 size下标位不是有效元素。从 pos 位置开始令其后的元素向前移动一位直至完成有效元素的移动(整体过程与头删类似)。1.9-查找数据intSLFind(SL*ps,SLDataType x){assert(ps);#查找数据for(inti0;ips-size;i){if(ps-arr[i]x){returni;}}return-1;}传入顺序表与要查找的元素断言传入指针不为NULL。——遍历数组查找元素找到返回对应下标否则返回不可能为数组下标的值例如-1此查找仅能满足顺序表内存储的数据类型为内置数据类型自定义数据类型还需自定义查找方式(比较逻辑)。2.0-销毁顺序表voidSLDestroy(SL*ps){assert(ps);free(ps-arr);ps-arrNULL;ps-sizeps-capacity0;}当要释放结构体开辟的空间时传入顺序表断言传入指针不为NULL。——释放arr指向的动态开辟内存(arr本身为NULL时无问题当传递给free的参数为NULL时不执行任何操作只有重复释放堆区空间会发生问题)此时arr为野指针需置空。清空 size 与 capacity 记录的大小与容量。2.5-一份测试代码voidTest_SeqList(){SL s;#初始化测试SLInit(s);#尾插测试SLPushBack(s,1);SLPushBack(s,2);SLPushBack(s,3);#头插测试SLPushFront(s,3);SLPushFront(s,2);SLPushFront(s,1);#尾删测试SLPopBack(s);SLPopBack(s);SLPopBack(s);#头删测试SLPopFront(s);SLPopFront(s);SLPopFront(s);#指定位置插入测试SLInsert(s,0,1);SLInsert(s,1,2);SLInsert(s,2,3);SLInsert(s,0,3);SLInsert(s,0,2);SLInsert(s,0,1);#指定位置删除测试SLErase(s,0);SLErase(s,4);SLErase(s,1);#查找数据测试intindexSLFind(s,2);if(index0){printf(%d\n,index);}indexSLFind(s,1);if(index0){printf(%d\n,index);}#销毁测试SLDestroy(s);}3.0-静态顺序表简介#指定容量的宏常量#defineN100typedefintSLDataType;#静态顺序表structSqList{SLDataType arr[N];#定长数组intsize;#当前有效的数据个数};静态顺序表使用固定长度的数组来存储数据其最大容量在编译时就已经确定无法在程序运行时改变。三、总结1-与数组对比对比列表数组顺序表定义一组连续内存空间的集合通过下标访问逻辑上连续的线性表物理上用数组存储并提供一套操作接口容量静态数组在编译时固定不可更改动态数组需手动管理无法自动扩容动态顺序表可自动扩容大小记录不记录元素个数需单独维护自动记录当前元素个数与总容量操作每次增删改查均需手动编写代码提供对应接口实现增删改查内存管理动态数组需手动释放调用destroy接口释放并置空指针典型应用场景底层存储、固定大小缓冲池、性能极敏感且大小确定的场景。需要动态增删、自动扩容、安全边界检查的场景。优点直接、高效、无额外结构开销。安全、易用、封装了扩容策略和边界管理。缺点无容量管理、无边界保护、代码重复易错。有轻微结构体开销部分接口有性能损耗如函数调用。——顺序表底层依赖数组但通过封装提供了更安全、更便捷、更适合动态数据管理的操作接口。在实际开发中除非极其简单的场景否则优先使用顺序表或标准库动态数组容器。2-顺序表的问题及思考问题中间、头插与删除操作的时间复杂度为O(N)问题每次增容申请的新空间及对旧空间的释放消耗较大问题每次增容必定成倍数增长有可能造成空间浪费思考如何解决以上问题————答链表、(此回答具有承上启下作用)四、练习有关顺序表的练习实际上相当于数组的练习推荐以下LeetCode题目27.移除元素 链接link.88.合并两个有序数组 链接link.⚛️EL PSY CONGROO十分感谢你的阅读本期不确定是否应该继续更新内容顺序表与AI的相关内容有哪些
