厦门网站设计制作,专门找建筑案例的网站,坂田网站建设,公司注册地址和经营地址不一样#x1f9d1;个人简介#xff1a;大家好#xff0c;我是尘觉#xff0c;希望我的文章可以帮助到大家#xff0c;您的满意是我的动力#x1f609; 在csdn获奖荣誉: #x1f3c6;csdn城市之星2名 … 个人简介大家好我是尘觉希望我的文章可以帮助到大家您的满意是我的动力 在csdn获奖荣誉: csdn城市之星2名 csdn2023年后端赛道第第七 csdn2023年长沙赛道第一 csdn2023年大二赛道第二 Java全栈群星计划top前5 端午大礼包获得者 阿里云专家博主 亚马逊DyamoDB结营 获得国家荣誉3项省级荣誉7项以及多项校院级
欢迎大家这里是CSDN我总结知识的地方欢迎来到我的博客感谢大家的观看 如果文章有什么需要改进的地方还请大佬不吝赐教 先在次感谢啦 文章目录 数据结构(八)——线性表的基本操作操作中常用的预定义常量与类型初始化(分配空间赋初值)销毁线性表线性表置空/清空线性表求表长判断线性表是否为空 查找算法的算法分析插入算法插入算法的算法分析删除操作删除算法分析 线性表的小结线性表的优缺点优点缺点 数据结构(八)——线性表的基本操作
操作中常用的预定义常量与类型 初始化(分配空间赋初值) 销毁线性表 线性表置空/清空线性表 求表长 判断线性表是否为空 线性表的按值查找算法(这里我们先说最简单的顺序查找,后面就详细讲解) 查找算法的算法分析
查找算法的基本操作:将记录的关键字同给定值进行比较(L.eleme) 比较的次数与输入的定值e有关(假设7个数字出现的概率均为1/7)
当ea1次当eb2次当ec3次…eg,7次
平均比较次数(123…7)/74
在查找时为确定元素在顺序表中的位置需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch Length, ASL)。 从顺序表查找的过程可见,C取决于所查元素在表中的位置。例如,查找表中第一个记录时,仅需比较一次;而査找表中最后一个记录时,则需比较n次。一般情况下C等于i。假设每个元素的查找概率相等,即 可简化为 由此可见,顺序表按值查找算法的平均时间复杂度为O(n)。
插入算法 插入位置在最后在线性表的最后添加一个元素不需要移动直接添加 插入位置在最前在原线性表的第1个元素之前插入一个新的元素线性表的所有元素都要移动移动次数最多 插入位置中间如上例 插入算法的算法分析 删除操作 ①判断删除位置i是否合法合法值为1≤i≤n) ②将欲删除的元素保留在e当中 ③将第il个至第n个的元素依次向前移动一个位置(i n时无需移动 ④表长减1 删除算法分析 线性表的小结
查找、插入、删除的平均算法复杂度为O(n)
空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)
线性表的优缺点
优点
存储密度大(结点本身所占用的空间/结点结构所占存储量1)无需为表示表中元素之间的逻辑关系而增加额外的存储空间
可以随机存取表中任意位置的元素
缺点
插入、删除某一元素需移动大量元素
当线性表长度变化较大时难以确定存储空间的容量数据元素的个数不能自由扩充(存储空间不灵活)
