数据结构(七)——线性表的基本操作

🧑个人简介：大家好，我是尘觉，希望我的文章可以帮助到大家，您的满意是我的动力😉

在csdn获奖荣誉: 🏆csdn城市之星2名
⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　💓csdn2023年后端赛道第第七
⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　💓csdn2023年长沙赛道第一
⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　💓csdn2023年大二赛道第二
⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　💓Java全栈群星计划top前5
⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　🤗 端午大礼包获得者
⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　🥰阿里云专家博主
⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　⁣⁣⁣⁣　😉亚马逊DyamoDB结营
获得国家荣誉3项省级荣誉7项以及多项校院级

💕欢迎大家：这里是CSDN，我总结知识的地方，欢迎来到我的博客，感谢大家的观看🥰
如果文章有什么需要改进的地方还请大佬不吝赐教 先在次感谢啦😊

数据结构(八)——线性表的基本操作

操作中常用的预定义常量与类型

初始化(分配空间；赋初值)

销毁线性表

线性表置空/清空线性表

求表长

判断线性表是否为空

线性表的按值查找算法(这里我们先说最简单的顺序查找,后面就详细讲解)

查找算法的算法分析

查找算法的基本操作:将记录的关键字同给定值进行比较(L.elem==e)

比较的次数与输入的定值e有关(假设7个数字出现的概率均为1/7)

当e=a，1次；当e=b，2次；当e=c，3次；…e=g,7次

平均比较次数(1+2+3+…+7)/7=4

在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch Length, ASL)。

从顺序表查找的过程可见,C取决于所查元素在表中的位置。例如,查找表中第一个记录时,仅需比较一次;而査找表中最后一个记录时,则需比较n次。一般情况下C等于i。假设每个元素的查找概率相等,即

可简化为

由此可见,顺序表按值查找算法的平均时间复杂度为O(n)。

插入算法

插入位置在最后在线性表的最后添加一个元素不需要移动直接添加
插入位置在最前在原线性表的第1个元素之前插入一个新的元素，线性表的所有元素都要移动移动次数最多
插入位置中间如上例

插入算法的算法分析

删除操作

①判断删除位置i是否合法（合法值为1≤i≤n)
②将欲删除的元素保留在e当中
③将第i+l个至第n个的元素依次向前移动一个位置(i= n时无需移动）
④表长减1

删除算法分析

线性表的小结；

查找、插入、删除的平均算法复杂度为O(n)

空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)

线性表的优缺点

优点

存储密度大(结点本身所占用的空间/结点结构所占存储量=1)无需为表示表中元素之间的逻辑关系，而增加额外的存储空间

可以随机存取表中任意位置的元素

缺点

插入、删除某一元素需移动大量元素

当线性表长度变化较大时，难以确定存储空间的容量，数据元素的个数不能自由扩充(存储空间不灵活)