数据结构第九章.ppt

第九章 查 找 9.1查找的概念 查找表（Search table）:是由同一类数据元素（或记录）构成的集合。对查找表进行的操作有： 1） 查找某个“给定的”数据元素是否在表中； 2） 检索某个“给定的”数据元素的各种属性； 3） 在查找表中插入一个数据元素； 4） 从查找表中删除某个数据元素。 9.1 基本概念 静态查找采用顺序表可以最大限度地节省记录集合占用的存储空间. 动态查找采用树表可以减小插入或删除记录所用的时间。 哈希表的构造采用的是把关键字映射为数据元素存储地址的方法，因此，哈希表上的查找是把待查找关键字用同样的映射公式映射为数据元素地址的过程。 马上要举行世界杯赛了。大家都很关心谁会是冠军。假如我错过了看世界杯，赛后我问一个知道比赛结果的观 众“哪支球队是冠军”？ 他不愿意直接告诉我， 而要让我猜，并且我每猜一次，他要收一元钱才肯告诉我是否猜对了，那么我需要付给他多少钱才能知道谁是冠军呢?  9.2 静态查找技术 静态查找表是在创建过程中建立的，在对数据元素的查找与访问过程中不能对它进行修改所以它不提供数据元素的插入与删除过程。通常采用顺序表结构。 Create_st(ST， int n) 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy_st(ST) 初始条件：静态查找表存在； 操作结果：销毁表态查找表ST。 Search(SSTable ST，KeyType keyval) 初始条件：静态查找表ST存在，keyval是和查找表中元素的类型相同的给定值； 操作结果：若ST中存在其关键字等于keyval的数据元素，则函数值为该元素的值或在查找表中的位置，否则为“空”。 Traverse(ST) 初始条件：静态查找表ST存在； 操作结果：按某种次序输出ST中的每个数据元素。 9.2.1顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较. int SequelSearch(SSTable ST， KeyType SearchKey) {//在ST中顺序查我关键字为SearchKey的记录 //查找成功时返回该记录在表中的位置，失败时返回0 ST.elem[0].Key=SearchKey; //设置“哨兵” for (int i=ST.len; ST.elem[I].key!= SearchKey ;--i); //从后往前查找 return i; //找不到时i为0 } 顺序查找小结 简单，查找效率却较低。 当已知各记录的查找频率不等时，可以改变记录的存储次序: 把查找频率高的记录尽可能放到序列的前面， 把查找频率低的记录放到序列的后面。 排序后的顺序表中进行下述的二分查找，这样也可以大大缩短平均查找长度。 我可以把球队编上号，从 1 到 32， 然后提问： “冠军的球队在 1-16 号中吗?” 假如他告诉我猜对了， 我会接着问： “冠军在 1-8 号中吗?” 假如他告诉我猜错了， 我自然知道冠军队在 9-16 中。 这样只需要五次， 我就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信息量只值五块钱。  查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,d为给定值 初始时，令low=0,high=n-1,mid=?(low+high)/2? 让d与mid指向的记录比较 若d==r[mid].key，查找成功 若dr[mid].key，则high=mid-1 若dr[mid].key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败 int low=0; int high=n-1; while (low=high) { int mid=(low+high)/2; if (Searchkey ==ST[mid].key) return mid; else if (Searchkey ST[mid].key) low=mid+1; else high=mid-1; } return –1; //查找失败 } 二分查找法的查找效率 二分查找法的查找效率 二分查找小结 平均查找长度小，查找速度快，尤其当n值较大时，它的查找效率较高,O(n)=O(log2n)。 付出的代价是需要在查找之前将顺序表按记录关键字的大小排序。这种排序过程也需要花费不少的时间; 二分查找适合于长度较大且又经常进行查找的顺序表。 实际上可能不需要猜五次就能猜出谁是冠军，因为象巴西、德国、意 大利这样