dn城市之星2名

欢迎大家这里是CSDN我总结知识的地方欢迎来到我的博客感谢大家的观看

先在次感谢啦

数据结构(八)——线性表的基本操作操作中常用的预定义常量与类型初始化(分配空间赋初值)销毁线性表线性表置空/清空线性表求表长判断线性表是否为空

查找算法的算法分析插入算法插入算法的算法分析删除操作删除算法分析

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

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

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

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

平均比较次数(123…7)/74

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

Length,

从顺序表查找的过程可见,C取决于所查元素在表中的位置。

例如,查找表中第一个记录时,仅需比较一次;而査找表中最后一个记录时,则需比较n次。

一般情况下C等于i。

假设每个元素的查找概率相等,即

插入算法

插入位置在最前在原线性表的第1个元素之前插入一个新的元素线性表的所有元素都要移动移动次数最多

插入位置中间如上例

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

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

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

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