主讲：计算机工程学院 李兰 答疑地点：主教学楼B区213

Presentation on theme: "主讲：计算机工程学院 李兰 答疑地点：主教学楼B区213"— Presentation transcript:

1 主讲：计算机工程学院 李兰 邮箱：jsj2014cpp@163.com 答疑地点：主教学楼B区213
第9章 查 找 主讲：计算机工程学院 李兰 答疑地点：主教学楼B区213

2 学习目标： ⒈了解.NET平台。 ⒉掌握Visual Studio 2008及MSDN的安装。 ⒊创建ASP.NET Web应用程序。
⒋掌握Visual Studio 2008 IDE的使用技巧。

3 数据结构课程的内容

4 基本概念 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字
是一种数据结构 基本概念 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ——可以唯一标识一个记录的关键字 例如“学号” ——识别若干记录的关键字 例如“女”

5 9.1 静态查找表 9.2 动态查找树表 9.3 哈希表

6 9.1 静 态 查 找 表 假设静态查找表的顺序存储结构为 数据元素类型的定义为: typedef struct {
9.1 静 态 查 找 表 假设静态查找表的顺序存储结构为 typedef struct { ElemType *elem; // 表基址，建表时按实际长度分配0号单元留空 int length; // 表的长度 } SSTable; 数据元素类型的定义为: typedef struct { keyType key; // 关键字域 … … // 其它属性域 } ElemType ;

7 对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。
9.1 顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较 例 找64 64 i i i i i 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 比较次数=5 监视哨 查找第i个元素： n+1-i 查找失败： n+1 对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。

8 int Search_Seq(SSTable ST, KeyType key) {
ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq

9 2 有序查找表 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。
2 有序查找表 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。

10 价格竞猜的小游戏 1000 3000 3500 4000 5000 主持人：平板的价格在1000元到5000元之间 主持人：少了
主持人：多了 主持人：恭喜你答对了！

11 折半查找的过程 例如: 在下面的表中查找key=64 的过程如下： ST.length ST.elem low low high high
64<elem[mid] high=mid-1 到前半区间查找 64=elem[mid] 查找成功 64>elem[mid] low=mid+1 到后半区间查找 ST.elem low low high high mid mid mid 步骤： while(low<=high) //搜素区间>=1 { 1.mid=(low+high)/2 2.如果key==elem[mid] return mid 否则 如果key<elem[mid] high=mid-1 否则 如果key>elem[mid] low=mid+1 } low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2

12 折半查找的过程 例如: 在下面的表中查找key=63 的过程如下： ST.length ST.elem low low high high
63>elem[mid].key low=mid+1 到后半区间查找 low>high 搜素区间为负，搜素失败 63<elem[mid].key high=mid-1 到前半区间查找 63<elem[mid].key high=mid-1 到前半区间查找 ST.elem low low high high mid mid mid 步骤： while(low<=high) //搜素区间>=1 { 1.mid=(low+high)/2 2.如果key==elem[mid] return mid 否则 如果key<elem[mid] high=mid-1 否则 如果key>elem[mid] low=mid+1 } low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2

13 折半查找的算法 low <= high (low + high) / 2
int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while ( ) { mid = ; //查找成功 else if ( key < ST.elem[mid].key) // 继续在前半区间进行查找 else // 继续在后半区间进行查找 } //查找失败 } // Search_Bin low <= high (low + high) / 2 if （key == ST.elem[mid].key ) return mid; high = mid - 1; low= mid + 1; return 0;

14 也可以采用如下递归算法： int BinSearch(SSTable ST,int low,int high,KeyType key) { int mid; if (low<=high) 　 { mid=(low+high)/2; if (ST[mid].key==key) return mid; if (ST[mid].key>key)//在R[low..mid-1]中递归查找 else //在R[mid+1..high]中递归查找 } else return 0; BinSearch(ST,low,mid-1,key); BinSearch(ST,mid+1,high,key);

15 查找性能分析 先看一个具体的情况，假设：表中有11个数据 3 4 2 3 4 1 3 4 2 3 4 判定树 6 3 9 1 4 2 5 7 8 10 11 < = > =（1*1+2*2+3*4+4*4）/11=3 查找性能优于顺序查找

16 6 3 9 4 7 1 10 5 8 2 11 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。
假设 n=2h-1 并且查找概率相等 则 在n>50时，可得近似结果 6 3 9 4 7 1 10 5 8 2 11

17 3 索引存储结构和分块查找 索引存储结构 索引存储结构＝数据表+索引表 索引表中的每一项称为索引项，索引项的一般形式是： （关键字,地址）
3 索引存储结构和分块查找 索引存储结构 索引存储结构＝数据表+索引表 索引表中的每一项称为索引项，索引项的一般形式是： （关键字,地址） 关键字唯一标识一个节点，地址作为指向该关键字对应节点的指针，也可以是相对地址。

18 例如，逻辑结构City，将区号看成是关键字，其索引存储结构如下图所示。索引表由（区号,地址）组成，其中区号按递增次序排序。
数据表 地址 关键字 区号 城市名 说明 300 010 100 Beijing 首都 310 021 130 Shanghai 直辖市 320 025 210 160 027 Wuhan 湖北省省会 330 190 029 Xian 陕西省省会 340 Nanjing 江苏省省会

19 分块查找 　性能： 　　　介于顺序查找和二分查找之间的查找方法。 思路： 　　（1）将数据表R[0..n-1]均分为b块,前b-1块中记录个数为s=n/b，最后一块即第b块的记录数小于等于s； 　　（2）每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是“分块有序”的； 　　（3）抽取各块中的最大关键字及其起始位置构成一个索引表IDX[0..b-1]，即IDX[i]（0≤i≤b-1）中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。

20 例如,设有一个线性表，其中包含25个记录，其关键字序列为：
　　8,14,6,9,10,22,34,18,19,31,40,38,54,66, 　　　　46,71,78,68,80,85, 100, 4,88,96,87 　　假设将25个记录分为5块，每块中有5个记录，该线性表的索引存储结构如下图所示。