文档介绍：第9章查找查找的基本概念静态查找表动态查找表哈希表主要知识点查找的基本概念查找表: 同一类型数据元素构成的集合。(集合则无相同元素) 查找:查询关键字是否在(数据元素集合)表中的过程。也称作检索。主关键字:能够惟一区分各个不同数据元素的关键字次关键字:通常不能惟一区分各个不同数据元素的关键字查找成功:在数据元素集合中找到了要查找的数据元素查找不成功:在数据元素集合中没有找到要查找的数据元素静态查找:只查找,不改变数据元素集合内的数据元素动态查找:既查找,又改变(增减)集合内的数据元素静态查找表:静态查找时构造的查找表动态查找表:动态查找时构造的查找表平均查找长度:查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为: 其中, P i是要查找数据元素出现的概率, C i是查找相应数据元素的比较次数。??? ni iiCP ASL 静态查找表静态查找表主要有三种结构: 顺序表有序顺序表索引顺序表静态查找表的顺序存储结构: typedef struct{ ElemType * elem; // 数据元素存储空间基址, 0号单元留空 int length / *表长度*/ } SSTable; typedef int KeyType; typedef char * InfoType; 定义要查找数据元素的结构体为: typedef struct{ KeyType key; / *关键字域*/ InfoType otherinfo; / *其他域*/ } ElemType; . 1 顺序表顺序查找的基本思想是: 从顺序表的一端开始,用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较,若在顺序表中查找到要查找的数据元素,则查找成功,函数返回该数据元素在顺序表中的位置;否则查找失败,函数返回 0。查找函数设计如下: int Search_Seq(SSTable ST, KeyType key) { // 算法 // 在顺序表 ST 中顺序查找其关键字等于 key 的数据元素。 // 若找到,则函数值为该元素在表中的位置,否则为 0。 int i=0; [0].key=key; // " 哨兵" for (i=; [i].key!=key; --i); // 从后往前找 return i; // 找不到时, i为0 } // Search_Seq 利用监视哨的算法。思考: 监视哨作用? 算法分析(顺序表)查找成功时的平均查找长度 ASL 成功为: ASL= ?P iC i = 1/n * (n-i+1) = (n+1)/2 ( 约表长的一半) 查找失败时的平均查找长度 ASL 失败显然为 n+1 有序表的查找有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。一、有序表的顺序查找有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同二、二分查找( 又称折半查找) 算法的基本思想: 先给数据排序(一般按升序排好),形成有序表, 然后再将 key 与正中元素相比,若 key 小,则缩小至前半部内查找;再取其中值比较,每次缩小 1/2 的范围,直到查找成功或失败为止。反之,如果 key 大,则缩小至后半部内查找。查找 21 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low 5 13 19 21 37 56 64 75 80 88 92 1 2 3 4 5 6 7 8 9 10 11 Mid High Low (a) 查找成功示例算法示例如图 (a) , (b) 所示。查找 71 -5 13 17 2