笔灵AI论文写作三步搞定，GO>>
计算机工程知识线性结构思维导图
免费下载
免费使用文件
FC 浏览量：22022-11-05 00:49:54
已被使用0次
简要介绍计算机工程知识线性结构的有关内容
树图思维导图提供 计算机工程知识线性结构思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机工程知识线性结构思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：d7884f6007de0e5832c56ddb797c83bf
思维导图大纲
线性结构思维导图模板大纲
顺序查找
查找效率
有序表
ASL（成功）=（n+1）/2
ASL（失败）=n/2+n/(n+1)
因为n+1种失败情况，查找长度为1+2+...+n+n
无序表
ASL（成功）=（n+1）/2
ASL（失败）=n+1
特点
可以是顺序表或者链表
折半查找
折半查找判定树
一定是平衡二叉树
根据mid向上或向下取整，X个元素对应的判定树是唯一的
倒数第二层是满的，最下层的叶子结点从左向右先填左子树或从右向左先填右子树
查找效率
判定树高度：h=log2(n+1)向上取整
查找成功：次数<h
查找失败：次数=h或h-1（查找失败共n+1种情况）
特点
只适合有序的顺序表
查找条件：while(low<=high),high=mid-1或者low=mid+1
分块查找
特点
块内无序，块间有序
把长度为n的查找表分为b个s个记录的块
先折半后顺序
ASL=log2(n+1)+(s+1)/2
两次顺序查找
ASL=(b+1+s+1)/2
s=根号n，ASL取最小值
块内只能顺序查找，索引表查找可以顺序或折半
折半查找索引表，若未在索引表查到，最终low>high，并在low所zhi指向的分块中查找
沪公网安备 31011502019485号
上海工商