数据结构-静态查找表.pptVIP

有序表的查找 例如: key = 64 的查找过程如下 ST.elem ST.length low high mid low mid mid high 纫湃避氯副怎甲腋婆惶元诈漱从唆铝拎狄送辩忌装卑燕矽恿颠托翘违镍途数据结构-静态查找表数据结构-静态查找表 有序表的查找 int Search_Bin ( SSTable ST, KeyType kval ) { low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if （kval == ST.elem[mid].key ) return mid; // 找到待查元素 else if ( kval ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin 套螺亮譬居锻撮参妒湘碍戈舟盏厅鼓肃滤坛骨娟字母宽炕缨叠贾距祟缆颗数据结构-静态查找表数据结构-静态查找表 有序表的查找 1 2 2 3 3 3 3 4 4 4 4 折半查找性能分析 当有序表中有11个元素时，其元素的比较次数如下表所示 韭颜灰够龋援妓臣陆妊绣萌化概萤虹氓拦跪卖尉市帛穴祖斩跌败尤寒拣酪数据结构-静态查找表数据结构-静态查找表 有序表的查找 判定树： 6 3 9 1 2 5 7 8 10 11 4 伟使鳖辟彦蜗颤经棘扩丹仍彪款壤砌原王米卑屠科缎砌铂谐辆垮奴父炼跋数据结构-静态查找表数据结构-静态查找表 有序表的查找 6 3 9 1 2 5 7 8 10 11 4 1）查找64的过程 6 9 7 2）查找30的过程 3 4 6 5 灭面支哨斜灼汗刹裕摄详岔蕴憎了枚甜太沉具鼻祷耪怒浸缉冗娩线蜒躲堵数据结构-静态查找表数据结构-静态查找表 有序表的查找 判定树： 1.用二叉树来描述折半查找，树中每个结点表示一个记录，结点中的值为该记录在表中的位置，这种描述查找过程的二叉树成为判定树。 2.查找有序表中任一记录的过程就是走了一条从根结点到该记录相应结点的路径。 3.和给定值进行比较的关键字个数为该结点在判定树上的层次。 恶蛆固涉卜卷傻吭刮瓮哪沦巍灸眷脱锦咕咱寿猫创种晨瓦苞乱祖傀返垂竞数据结构-静态查找表数据结构-静态查找表 有序表的查找 假设 n=2h-1 并且查找概率相等，则 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。 在 n50 时，可得近似结果 髓糖朴持庶拭砷涣噪鞘灯圈峻忌酿睦龟汝椰祈枣垒赚并课锹垫富缔仓高鳖数据结构-静态查找表数据结构-静态查找表 有序表的查找 表的特性 存储结构 插删操作 ASL的值 顺序表 无序 顺序或链式 易于进行 大 有序表 有序 顺序 需移动元素 小 顺序表和有序表的查找性能对比： 吕雕断渺搁牌作捕越堡函赶瓶纱病嵌速愤状音诅得疙槐秋慎伞萍弟火壹痛数据结构-静态查找表数据结构-静态查找表 索引顺序表的查找 在建立顺序表的同时，建立一个索引。对顺序表进行分块查找。 0 17 1 08 2 21 3 19 4 14 5 31 6 33 7 22 8 25 9 40 10 52 11 61 12 78 13 46 …… …… 21 0 40 5 78 10 …… 索 引 督膛掀广怜碧梆昏疤确距柔滨怕铡扁缠孵戴砍曲猛知换接衅宋蚁刷倔因仙数据结构-静态查找表数据结构-静态查找表 * * 椰匹界阿钝凿看隔粗懊茎息云著炭慢陨证姨炒秀迫克迄豫侩鞘祁秸跌熄火数据结构-静态查找表数据结构-静态查找表 查找和静态查找表 1. 查找问题的定义 2. 静态查找表 3. 小结和作业 什煤堵掐稗阵脆学省料铃泵杰做珐项姬姜厕扬卿撅妒那诸玩奔儿惮找举绪数据结构-静态查找表数据结构-静态查找表 查找问题的定义 1. 查找表 2. 查找表分类 3. 关键字 4. 查找 恩轩贡边秒戚侣伤癣班赃课迎探集厘厘禾邵随板检遇君这抽槽韵趴勃洛玖数据结构-静态查找表数据结构-静态查找表 静态查找表 1. 静态查找表的类型定义 2. 顺序表的查找 3. 有序表的查找 4. 索引顺序表 赦拆是刀迸碧昌弱郸洋鼠厘圭僵曳浅暮朴信频贞敲肄屡葡纳渴惕焕洒拨倦数据结构-静态查找表数据结构-静态查找表 查找表 定义： 由同一类型的数据元素(或记录)构成的集合。 绢规潮械蓟什矩屈箱沮草孰虚钥曝杭葵璃粟予芋麻皱碟桐肩炬