数结 华中科技大学 计犷机学院(10) 200=9=2Q
2001 -- 12 --29 华中科技大学 数据结构计算机学院(10)
9.0与查找有关的术语: ●査找表——由同一类型的数据元素(记录)组成的集 记作:ST={a1,a2,,.an} 学生成绩表 序号学号姓名性别数学外语 200041刘大海男8075 2[20021伟」男「9083 3[2006晓英女8288 200048王伟女8090 n 数据项1数据项2 数据项5 (主关键字) ●关键字 可以标识一个记录的数据项 ●主关键字—可以唯一地标识一个记录的数据项 ●次关键字—可以识别若干记录的数据项
9.0 与查找有关的术语： ● 查找表----由同一类型的数据元素（记录）组成的集合。 记作：ST={a1,a2,...,an} 学 号 姓 名 性别 数学 外语 200041 刘大海 男 80 75 200042 王 伟 男 90 83 200046 吴晓英 女 82 88 200048 王 伟 女 80 90 ...... ..... ... .... ... 序号 1 2 3 4 n ● 关键字-------可以标识一个记录的数据项 ● 主关键字-----可以唯一地标识一个记录的数据项 ● 次关键字-----可以识别若干记录的数据项 学生成绩表 数据项1 (主关键字) 数据项2 数据项5
●查找表的操作 ●生成查找表 ●查找元素(记录)x在是否在表ST中 ●查找元素(记录)x的属性 ●插入新元素(记录)x ●删除元素(记录)x ●査找——-根据给定的某个关键字值,在査找表中确定一个其 关键字等于给定值的记录或数据元素。 设k为给定的一个关键字值,R[1..n]为n个记录的表,若 存在R[i].key=k,1≤i≤n,称查找成功;否则称查找失败。 ●静态査找——查询某个特定的元素,检査某个特定的数据元 素的属性,不插入新元素或删除元素(记录)。 ●动态查找一在查找过程中,同时插入查找表中不存在的数 据元素(记录)
● 查找表的操作 ● 生成查找表 ● 查找元素(记录)x在是否在表ST中 ● 查找元素(记录)x的属性 ● 插入新元素(记录)x ● 删除元素(记录)x ...... ● 查找----根据给定的某个关键字值，在查找表中确定一个其 关键字等于给定值的记录或数据元素。 设k为给定的一个关键字值，R[1..n]为n个记录的表,若 存在R[i].key=k,1≤i≤n,称查找成功；否则称查找失败。 ● 静态查找----查询某个特定的元素，检查某个特定的数据元 素的属性,不插入新元素或删除元素(记录) 。 ● 动态查找----在查找过程中，同时插入查找表中不存在的数 据元素(记录)
●查找表的类型及其查找方法 (1)静态查找表 ●顺序表,用顺序查找法 ●线性链表,用顺序查找法 ●有序的顺序表,用: 折半査找法;*斐班那契査找法;插值査找法; ●索引顺序表/分块表,用分块查找法 (2)动态查找表 ●二叉排序树,平衡二叉树(AⅥL树) *。B树,B+树,键树 (3)哈希(Hash)表 ●平均查找长度——査找一个记录时比较关键字次数的平均值 ASL=∑PCi 查找r[订]的概率 C1-—查找r[订所需比较关键字的次数
● 查找表的类型及其查找方法 (1) 静态查找表 ● 顺序表，用顺序查找法 ● 线性链表，用顺序查找法 ● 有序的顺序表，用： 折半查找法；**斐班那契查找法；插值查找法； ● 索引顺序表/分块表，用分块查找法。 (2) 动态查找表 ● 二叉排序树,平衡二叉树(AVL树） **● B树, B+树, 键树 (3) 哈希(Hash)表 ● 平均查找长度----查找一个记录时比较关键字次数的平均值。 n ASL=∑ PiCi i=1 Pi --- 查找r[i]的概率 Ci --- 查找r[i]所需比较关键字的次数
9.1静态查找表 9.1.1顺序表与顺序查找法 ey name 顺序表的描述 例元素(记录)类型 监视哨 # define n100//表长100 2041刘大海 struct arecord 22042王伟 keytype key;/关键字类型 2046吴晓英 char name[6];/姓名 //其它 r[n+1] //n+1个记录 其中:r[O0]为监视哨; 记录按输入次序存入r[1..n中。监视哨x[1..6 12|10|3020|2515 2.顺序查找法( sequential search) 456
9.1 静态查找表 9.1.1 顺序表与顺序查找法 1.顺序表的描述 例 元素(记录)类型 #define n 100 //表长100 struct arecord { keytype key ；//关键字类型 char name[6]；//姓名 ...... //其它 } r[n+1]； //n+1个记录 其中：r[0]为监视哨； 记录按输入次序存入r[1..n]中。 2041 刘大海 ... 2042 王 伟 ... 2046 吴晓英 ... ... ... ... ... ... ... ... ... ... 0 1 2 3 n key name ... 监视哨 2.顺序查找法(sequential search) 12 10 30 20 25 15 0 1 2 3 4 5 6 监视哨 r[1..6]
3.算法设计 算法1:假定不使用监视哨r[0] 基本思想:将关键字k依次与记录的关键字 r[n].key,r[n-1].key,,.,r[1].key比较, 如果找到一个记录r[i],有r[i].key=k(1≤i≤n),则查找 成功,停止比较,返回记录的下标i;否则,查找失败,返回0。 int sequsearch(struct arecord r[, int n, keytype k) inti=n;//从第n个记录开始查找 while (i>=1 & k!=r[i]. key) //继续扫描 if(i) printf(" SuccessⅦn〃);//查找成功 else printf("fail\n) //查找失败 return 1 //返回记录的下标i
3.算法设计 算法1：假定不使用监视哨r[0] 基本思想：将关键字k依次与记录的关键字 r[n].key,r[n-1].key，...,r[1].key 比较, 如果找到一个记录r[i],有r[i].key＝k (1≤i≤n)，则查找 成功，停止比较,返回记录的下标i；否则,查找失败,返回0。 int sequsearch(struct arecord r[],int n,keytype k) { int i=n； //从第n个记录开始查找 while (i>=1 && k!=r[i].key) i--； //继续扫描 if (i) printf(”success\n”)； //查找成功 else printf(”fail\n”)； //查找失败 return i； //返回记录的下标i }
算法2:假定使用监视哨r[0] 基本思想:先将关键字k存入r[0].key,再将k依次与 r[n].key,r[n-1].key,,..,r[1].key,r[0].key进行比较, 如果找到一个记录,有k=r[i].key,(0≤i≤n),则停止比较。 如果i>0,则查找成功;否则,查找失败。 int sequsearch (struct arecord r[, int n, keytype k) int l-n: /从第n个记录开始查找 r[o]. key=k; //k填入r[O].key while(k=rLi]. key //继续扫描 if(i!=0) printf(" successⅦn〃);/查找成功 else printf("fai1Ⅶn) //查找失败 return 1 //返回记录的下标i
算法2：假定使用监视哨r[0] 基本思想：先将关键字k存入r[0].key,再将k依次与 r[n].key,r[n-1].key，...,r[1].key, r[0].key进行比较, 如果找到一个记录,有k=r[i].key, (0≤i≤n)，则停止比较。 如果 i>0,则查找成功；否则,查找失败。 int sequsearch(struct arecord r[],int n,keytype k) { int i=n； //从第n个记录开始查找 r[0].key=k； //k填入r[0].key while( k!=r[i].key ) i-- ； //继续扫描 if (i!=0) printf(”success\n”)； //查找成功 else printf(”fail\n”)； //查找失败 return i； //返回记录的下标i }
4查找算法性能分析: 对n个记录的表,所需比较关键字的次数 ●若查找成功:最少为1,最多为n 假定每个记录的查找概率相等,即P1=P2 1/n ASL=∑P;Ci (n+(n-1)+..+1)=(n+1)/2 n i=l ●若查找失败:使用监视哨r[0],为n+1 不使用监视哨r[0],为n 假定查找成功和失败的机会相同,对每个记录的查找概率相 等,P;=1/(2*n),则 ASL=--∑ 2n (+h+1n+1n+1 =3(n+1)/4 24
4 查找算法性能分析： 对n个记录的表,所需比较关键字的次数 ● 若查找成功: 最少为1,最多为n 假定每个记录的查找概率相等，即 P1 = P2 = ... = Pn =1/n n 1 n 1 ASL=∑ PiCi =-- ∑ Ci =--(n+(n-1)+...+1)=(n+1)/2 i=1 n i=1 n ● 若查找失败: 使用监视哨r[0],为 n+1 不使用监视哨r[0],为 n 假定查找成功和失败的机会相同，对每个记录的查找概率相 等，Pi=1/(2*n), 则 1 n n+1 n+1 n+1 ASL=-- ∑ Ci + --- =--- + --- =3(n+1)/4 2n i=1 2 4 2
9.1.2有序的顺序表的查找与折半查找法 1.有序表 r[1].key≤r[2].key≤..≤r[n].key 2.折半查找( binary search,对半查找,二分查找) 假定k=10 1012182025304010w=1,hig=8 12345678 mid=(lowthig)/2=4 hi 51012 1820253040 low=l, hig=3 mid=(low+hig)/ 2=2 12345678 low mid hig
9.1.2 有序的顺序表的查找与折半查找法 1.有序表 r[1].key≤r[2].key≤...≤r[n].key 2.折半查找(binary search,对半查找，二分查找) 假定 k=10 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=8 mid=(low+hig)/2=4 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=3 mid=(low+hig)/2=2
假定k=40 510 1820253040 low=l, hig=8 mid=(low+hig)/2=4 2345678 low id hi 510 12 low=5, hig=8 1820|253040 mid=(lowthig)/2=6 12345678 low mid hig low=7, hig=8 510121820253040 mid=(lowhig)/ 2=7 low mid hig
假定k=40 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=8 mid=(low+hig)/2=4 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=5,hig=8 mid=(low+hig)/2=6 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ low mid hig low=7,hig=8 mid=(low+hig)/2=7 ↑