《关于太极计算机股份有限公司》由会员分享，可在线阅读，更多相关《关于太极计算机股份有限公司（96页珍藏版）》请在金锄头文库上搜索。
1、第九章 查找,有关查找的基本概念 查找表，关键字，查找成功，查找失败 静态查找表，动态查找表 平均查找长度 静态查找表 动态查找表 哈希表（散列表）,9.1 静态查找表,顺序表的查找 顺序查找,i,顺序查找,int Sq_search(int A,int n,int e) / 在无序表中查找元素e，查找成功时，返回元素在表中的位置 / 否则返回0 i=n; while (i0 ,12,23,6,99,45,30,51,28,i,顺序查找,无序表上的顺序查找，设监视哨,12,23,6,99,45,30,51,28,i,无序表上的顺序查找,int Sq_search(int A,int n,int
2、 e) / 在无序表中查找元素e，查找成功时，返回元素在表中的位置 / 否则返回0 i=n; A0=e; /监视哨：下标为0的位置存放待查找的元素 while (Ai!=e) i-; return i; ,平均查找长度,查找性能：平均查找长度（ASL） 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。,其中，n是查找表中的长度，Pi为查找第i个元素的概率 ci是找到表中其关键字与给定值相等的记录时(第i个记录)，和给定值已进行过比较的关键字的个数。,无序表上的顺序查找,int Sq_search(int A,int n,int e) /
3、 在无序表中查找元素e，查找成功时，返回元素在表中的位置 / 否则返回0 i=n; A0=e; while ( Ai!=e) i-; return i; ,有序表上的顺序查找,6,12,23,28,31,45,51,99,0,监视哨,例如：e=23,成功时，与顺序查找的平均查找长度（ASL）相同，失败时无须与所有元素进行比较,有序表上的顺序查找,6,12,23,28,31,45,51,99,23,0,监视哨,e=23?,有序表上的顺序查找,6,12,23,28,31,45,51,99,23,0,监视哨,e =23?,有序表上的顺序查找,6,12,23,28,31,45,51,99,23,0,监
4、视哨,e =23?,有序表上的顺序查找,6,12,23,28,31,45,51,99,23,0,监视哨,e =23?,有序表上的顺序查找,6,12,23,28,31,45,51,99,23,0,监视哨,e =23?,有序表上的顺序查找,6,12,23,28,31,45,51,99,23,0,监视哨,e =23?,aie不成立， 停止查找,有序表上的顺序查找,int Sq_search(int A,int n,int e) / 在无序表中查找元素e，查找成功时，返回元素在表中的位置 / 否则返回0 i=n; A0=e; while ( Aie) i-; if Ai=e return i; els
5、e return 0; ,有序表上的顺序查找：失败,6,12,23,28,31,45,51,99,40,0,监视哨,静态查找表,顺序查找 无序表的顺序查找 有序表的顺序查找 折半查找,有序顺序表上的折半查找,6,12,23,28,31,45,51,99,low,high,mid=(low+high)/2,下标,有序顺序表上的折半查找,6,12,23,28,31,45,51,99,low,high,mid,e Amid,23,有序顺序表上的折半查找,6,12,23,28,31,45,51,99,1,2,3,4,5,6,7,8,low,high,mid,e Amid,e=23 mid=(low+h
6、igh)/2,23,有序顺序表上的折半查找：成功,6,12,23,28,31,45,51,99,1,2,3,4,5,6,7,8,low,high,mid,e 等于 Amid,23,有序顺序表上的折半查找,6,12,23,28,31,45,51,99,low,high,mid,e Amid,55,有序顺序表上的折半查找,6,12,23,28,31,45,51,99,1,2,3,4,5,6,7,8,low,high,mid,e Amid,55,有序顺序表上的折半查找,6,12,23,28,31,45,51,99,1,2,3,4,5,6,7,8,low,high,mid,e Amid,55,有序顺序
7、表上的折半查找,6,12,23,28,31,45,51,99,1,2,3,4,5,6,7,8,low,high,mid,e Amid,55,有序顺序表上的折半查找：失败,6,12,23,28,31,45,51,99,1,2,3,4,5,6,7,8,low,high,?,有序顺序表上的折半查找,mid=(low+high)/2; if (Amid = = e) return mid; /查找成功 else if (eAmid) high=mid-1; /下一次到前半区间查找 else low=mid+1; /下一次到后半区间查找,折半查找方法： 先确定待查记录所在的范围(区间)，若待查记录等于表
8、中间位置上的记录，则查找成功；否则，缩小查找范围，即若待查记录小于中间位置上的元素，则下一次到前半区间进行查找，若待查记录大于中间位置上的元素，则下一次到后半区间进行查找。,折半查找算法,int B_search(int A,int n,int e) / 在有序表中查找元素e，若查找成功，则返回元素在表中的位置 / 否则返回0 low=1; high=n; while ( low=high) mid=(low+high)/2; if (Amid=e) return mid; /查找成功 else if (eAmid) high=mid-1;/下一次到前半区查找 else low=mid+1;
9、/下一次到后半区查找 /end of while return 0; /查找失败 /end of B_search,折半查找法,问题： 若采用链表（单链表或双向链表）作为查找表的存储结构，能否进行折半查找？,折半查找判定树,折半查找判定树：描述折半查找过程的二叉树 有序顺序表：a1，a2，a3，a4，a5，a6，a7，a8,a4,a2,a6,a1,a3,a5,a7,a8,折半查找判定树,a4,a2,a6,a1,a3,a5,a7,a8,ASL成功 = (1+2+2+3+3+3+3+4)/8 = 21/8 -等概率查找,查找失败,若查找失败，即表中不存在要查找的元素，平均查找长度又如何呢？,查找失
10、败,ASL失败 = ？,a1 a2 a3 a4 a5 a6 a7 a8,折半查找判定树,a4,a2,a6,a1,a3,a5,a7,a8,比a1小的所有元素,比a8大的所有元素,大于a2而小于a3的所有元素,大于a5而小于a6的所有元素,折半查找算法,int B_search(int A,int n,int e) / 在有序表中查找元素e，若查找成功，则返回元素在表中的位置 / 否则返回0 low=1; high=n; while ( lowhigh /end of B_search,折半查找判定树,a4,a2,a6,a1,a3,a5,a7,a8,ASL失败 = (3*7+4*2)/9 = 29
11、/9,折半查找判定树n=11,a6,a3,a1,a4,a9,a10,a7,a11,a2,a5,a8,折半查找判定树n=11,a6,a3,a1,a4,a9,a10,a7,a11,a2,a5,a8,折半查找的效率分析,如果查找表中有n个元素，那么对应的折半查找判定树又如何？,查找成功和失败的平均查找长度与有n个结点的完全二叉树的高度相同。即：,完全二叉树,折半查找的效率分析,设有序顺序表中有n个元素，进行折半查找,设n=2h-1，则描述折半查找的判定树是高度为h的满二叉树 设表中每个记录的查找概率相等，即Pi=1/n,折半查找的效率分析,则查找成功时折半查找的平均查找长度为：,索引顺序表的查找,元
12、素分块有序 建立索引表,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,22,12,索引表,索引顺序表的查找：分块查找,在索引顺序表中查找指定元素时，分两步： 先在索引表中确定元素所在的块； 再在块中顺序查找；,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,22,12,索引表,索引顺序表的查找：分块查找,在索引顺序表中查找指定元素时，分两步： 先在索引表中确定元素所在的块； 再在块中顺序查找；,索引顺序表的查找：分块查找,设查找表中的元素可均匀地分为b块，每块含有s个记录 若在索引表和块内都进行顺序查找，
13、则：,实际上，在索引表中可进行折半查找。,完全二叉树n=11,return,9.2 动态查找表,动态查找表的特点 表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。 动态查找表的主要运算 创建、销毁 查找、插入和删除 遍历,二叉排序树和平衡二叉树,1.二叉排序树(二叉检索树、二叉查找树) 定义 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 若其左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若其右子树不空，则右子树上所有结点的值均大于它的根结点的值 其左、右子树也分别为二叉排序树,二叉排
14、序树图示,CAO,ZHAO,DING,CHEN,WANG,LI,XIA,DU,MA,(a),(b),二叉排序树的查找运算,查找：查找键值等于key的记录 若二叉排序树为空树，则查找失败，返回； 若根结点的键值等于key，则查找成功，返回； 若根结点的键值大于key，则到根的左子树上继续查找；否则，到根的右子树上继续查找；,二叉排序树的查找算法,BiTree SearchBST(BiTree T,keyType key) /在T指向根的二叉排序树中递归地查找关键字等于key的数据元素， /若找到，返回指向该结点的指针，否则返回null if (T=NULL) return NULL; else
15、if (T-data.key=key) return T; else if (T-data.keykey) return SearchBST(T-lchild,key); else return SearchBST(T-rchild,key); /SearchBST,T,二叉排序树的插入运算,插入：在二叉排序树中插入键值等于key的记录 若二叉排序树为空树，则插入元素作为树根结点； 若根结点的键值等于key，则插入失败； 若key小于根结点的键值，则插入到根的左子树上；否则，插入到根的右子树上； 新插入的结点一定是个叶子结点,二叉排序树的插入算法,Status InsertBST(BiTree &T,ElemType e) /当二叉排序树中不存在关键字等于e.key的数据元素时， /插入元素e并返回true，否则返回false,if (
