1、18.1查找的基本概念查找的基本概念8.2 基于线性表的查找法基于线性表的查找法8.3 基于树的查找基于树的查找8.4 计算式查找法计算式查找法哈希法哈希法2列表：列表：由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。关键字：关键字：数据元素的某个数据项的值，用它可标识列表中的数据元素的某个数据项的值，用它可标识列表中的一个或一组数据元素一个或一组数据元素查找查找：根据给定的关键字值，在列表中确定一个其关键字与给：根据给定的关键字值，在列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。定值相同的数据元素，并返回该数据元素在列表中的
2、位置。平均查找长度平均查找长度定义：为确定数据元素在列表中的位置，需和给定关键值进定义：为确定数据元素在列表中的位置，需和给定关键值进行比较的关键值个数的期望值，称为查找算法在查找成功时行比较的关键值个数的期望值，称为查找算法在查找成功时的的平均查找长度平均查找长度iniinnCPCPCPCPASL12211.P Pi i是查找第是查找第i i个元素概率，个元素概率，C Ci i是为找到第是为找到第i i个元素进行的比较次数个元素进行的比较次数顺序查找法顺序查找法5折半查找折半查找1 1、数据类型的定义、数据类型的定义#define LiST_SIZE 20Typedef struct Key
3、Type key;OtherType other_data;RecordType;Typedef struct RecordType rLIST_SIZE+1;/r0为工作单元为工作单元 int length;RecordList2 2、顺序查找法、顺序查找法设置监视哨设置监视哨int SeqSearch(RecordList l,KeyType k)/在顺序表l中顺序查找关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0.l.r0.key=k;i=l.length;while(l.ri.key!=k)i-;return(i);不设监视哨不设监视哨 int SeqSearch(
4、RecordList l,KeyType k)/不用监视哨，在顺序表中查找关键字等不用监视哨，在顺序表中查找关键字等于于k的元素的元素 i=l.length;while(i=1&l.ri.key!=k)i-;if(i1)return(i);else return(0);3、性能分析、性能分析 假设列表长度为假设列表长度为n，那么查找第，那么查找第i个数据元素需要进行个数据元素需要进行n-i+1次比次比较，即较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即。又假设查找每个数据元素的概率相等，即Pi=1/n,则顺序查找算法的平均查找长度为：则顺序查找算法的平均查找长度为：)1(21)1
5、(11111ninnCnCpASLniniiinii1 1、折半查找定义、折半查找定义折半查找法又称二分查找法，这种方法对待查找的列表有折半查找法又称二分查找法，这种方法对待查找的列表有两个要求两个要求:列表必须是列表必须是顺序存储结构顺序存储结构 列表必须按列表必须按关键字大小有序排列关键字大小有序排列 学号学号姓名姓名平均成绩平均成绩其它其它00010001 王一王一90.290.2.00020002张三张三707000320032李四李四75.575.500340034 刘四刘四80.080.0.00600060钱五钱五6868.2 2、基本过程、基本过程 将表中间位置记录的关键字与需要
6、查找的关键字比较将表中间位置记录的关键字与需要查找的关键字比较 如果如果两者相等，则查找成功两者相等，则查找成功;否则否则利用中间记录将表分成前、后两个子表利用中间记录将表分成前、后两个子表;如果如果列表中间位置记录的关键字大于要查找关键列表中间位置记录的关键字大于要查找关键字，则进一步查找前一子表字，则进一步查找前一子表 否则否则进一步查找后一子表。进一步查找后一子表。3 3、算法、算法Int BinSrch(RecordList l,KeyType k)/在有序表中折半查找其关键字等于在有序表中折半查找其关键字等于k k的元素，若找到，则函数的元素，若找到，则函数返回值为该元素在表中的位置
7、返回值为该元素在表中的位置d d low=1;high=l.length;/置区间初值置区间初值While(low=high)mid=(low+high)if(k=l.rmid.key)return (mid)/找到待查元素找到待查元素else if(kl.rmid.key)high=mid-1;else low=mid+1;return(0);4 4、性能分析、性能分析 折半查找过程可用一折半查找过程可用一二叉判定树二叉判定树描述。描述。二叉判定树结构：二叉判定树结构：树中每一结点对应表中一记录，结点值树中每一结点对应表中一记录，结点值设为记录在列表中的位置序号。设为记录在列表中的位置序号。
8、612151822252835465860123456781011631245978101194 4、性能分析、性能分析 从根到被查结点路径关键字比较次数为被查从根到被查结点路径关键字比较次数为被查结点结点层次数层次数 假设表的长度假设表的长度n=2n=2h h-1,-1,则相应判定树必为深则相应判定树必为深度是度是h h的满二叉树，的满二叉树，h=logh=log2 2(n+1)(n+1)又假设每个记录的查找概率相等，则折半又假设每个记录的查找概率相等，则折半查找成功时的查找成功时的平均查找长度为平均查找长度为1)1(log12*12111nnnjnCpASLhjjiniibs 树中层次为树
9、中层次为1 1的结点有的结点有1 1个，层次为个，层次为2 2的的结点有结点有2 2个，层次为个，层次为h h的结点有的结点有2 2h-1h-1个个5 5、二叉判定树举例、二叉判定树举例(Apr,Aug,Dec,Feb,Jan,July,june,Mar,May,Nov,Oct,Sep)JulyDecAugAprFebJanMayJuneMarOctSepNov其在等概率其在等概率(1/12)(1/12)的情况下，查的情况下，查找成功的平均查找长度：找成功的平均查找长度：ASL（1+2*2+3*4+4*5)/12=3.1算法优点算法优点比较次数少比较次数少查找速度快查找速度快平均性能好平均性能
10、好算法缺点算法缺点待查表为有序表待查表为有序表插入、删除困难插入、删除困难1 1、对所查表的要求、对所查表的要求将列表分成若干块（子表），一般情况下，块的长度均匀，将列表分成若干块（子表），一般情况下，块的长度均匀，最后一块可不满最后一块可不满每块内元素无序每块内元素无序块与块间有序块与块间有序18 14 12 25 828 32 45 36 58 60 88 71 0 1 2 3 4 5 6 7 8 9 10 11 122558880510索引表索引表2 2、基本思想、基本思想构造一索引表构造一索引表将待查关键字将待查关键字K K与索引表中的关键字进行比较，以确定待查与索引表中的关键字进行比
11、较，以确定待查记录所在的块。记录所在的块。用顺序查找法，在相应块内查找关键字为用顺序查找法，在相应块内查找关键字为K K的元素的元素3 3、平均查找长度、平均查找长度 设查找索引表的平均查找长度设查找索引表的平均查找长度L LB B，相应块内顺序查找的平，相应块内顺序查找的平均查找长度均查找长度L LW W，则平均查找长度：，则平均查找长度：ASLASLbsbs=L=LB B+L+Lw w 假定将长度为假定将长度为n n的表分成的表分成b b块，每块内含块，每块内含s s个元素，则个元素，则b=n/s.b=n/s.假定表中每个元素的查找概率相等，则每个索引项的查找概假定表中每个元素的查找概率相
12、等，则每个索引项的查找概率为率为1/b,1/b,块内每个元素的查找概率为块内每个元素的查找概率为1/s,1/s,则有则有顺序法平均查找长度顺序法平均查找长度1)(21/21121111sbASLsnbsisLbjbLbssiWbjB代入将折半法平均查找长度折半法平均查找长度2)1(log211)1(log1)1(log222ssnsbASLbLbsb查找方法比较查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找ASLASL最大最大最小最小两者之间两者之间表结构表结构有序表，无序表有序表，无序表有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构，顺序存储结构，线性链表线性链表
13、顺序存储结顺序存储结构，构，顺序存储结构，顺序存储结构，线性链表线性链表课堂练习课堂练习例例1 1：折半查找有序表（：折半查找有序表（4 4，6 6，1010，1212，2020，3030，5050，7070，8888，100100），若查找元素），若查找元素5858，则它将依次与表中那些元素比较，查找，则它将依次与表中那些元素比较，查找结果失败。结果失败。例例2 2：对于具有：对于具有144144个记录的文件，若采用分块查找，且每块个记录的文件，若采用分块查找，且每块长度为长度为8,8,则平均查找长度为多少？则平均查找长度为多少？二叉排序树二叉排序树21平衡二叉排序树平衡二叉排序树1 1、定
14、义、定义二叉排序树二叉排序树或者是一棵空树，或者是一棵空树，或者是具有如下性质的二叉树：或者是具有如下性质的二叉树：若它的左子树非空，则若它的左子树非空，则左子树上所有结点的值均左子树上所有结点的值均小于小于根结点的值根结点的值若它的右子树非空，则若它的右子树非空，则右子树上所有结点的值均右子树上所有结点的值均大于大于根结点的值根结点的值它的左右子树也分别为它的左右子树也分别为二叉排序树二叉排序树503020104025238090858835是二叉排序树是二叉排序树66不不212 2、二叉排序树的存储结构、二叉排序树的存储结构取二叉链表作为二叉排序树的存储结构取二叉链表作为二叉排序树的存储结
15、构Typedef struct BiTNode KeyType Key;struct BiTnode *lchild,*rchildBiTNode,*BSTree3、二叉排序树的插入、二叉排序树的插入【算法思想算法思想】5030802090854035883250505030403550508090若二叉树是空，则新结若二叉树是空，则新结点是二叉树的根点是二叉树的根若二叉树非空，则将若二叉树非空，则将S.keyS.key与二叉排序树根结与二叉排序树根结点的关键字进行比较：点的关键字进行比较：a.a.若若S.keyS.key的值等于根结的值等于根结点的值，则停止插入；点的值，则停止插入；b.b.
16、若若S.keyS.key的值小于根结的值小于根结点的值，则将插入左子点的值，则将插入左子树；树；c.c.若若S.keyS.key的值大于根结点的值大于根结点的值，则将插入右子树；的值，则将插入右子树；20328588Void InsertBST(BSTree *bst,KeyType key)/若在二叉排序树中不存在关键字等于若在二叉排序树中不存在关键字等于keykey的元素，插入该元素的元素，插入该元素 Bitree s;If(*bst=NULL)/递归结束条件递归结束条件 Else if(keykey)/将将s s插入左子树插入左子树Else if(key(*bst)-key)/将将s s
17、插入右子树插入右子树s=(BSTree)malloc(sizeof(BSTNode)s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;InsertBST(&(*bst)-lchild),key);InsertBST(&(*bst)-rchild),key);BSTNode*InsertBST(BSTree root,KeyType key)/若在二叉排序树中不存在关键字等于若在二叉排序树中不存在关键字等于keykey的元素，插入该元素的元素，插入该元素if(root=NULL）s=(BSTree)malloc(sizeof(BSTNode)s-key=k
18、ey;s-lchild=NULL;s-rchild=NULL;root=s;else p=root;/建立新结点建立新结点 r=(BSTree)malloc(sizeof(BSTNode);r-key=key;r-lchild=NULL;rrchild=NULL;二叉排序树插入的非递归算法二叉排序树插入的非递归算法if(q-key=key)return;if (q-keykey)q-lchild=r;/插入插入r r做做q q的左孩子的左孩子 else q-rchild=r;/插入插入r做做q的右孩子的右孩子 return root;while(p)/寻找新结点的插入位置寻找新结点的插入位置
19、q=p;if(p-keykey)p=p-lchild;else p=p-rchild;一个无序序列可以通过构造一棵二一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列叉排序树而变成一个有序序列 每次插入的新结点都是二叉排序树每次插入的新结点都是二叉排序树上新的叶子结点上新的叶子结点 插入时不必移动其它结点，仅需修插入时不必移动其它结点，仅需修改某个结点的指针改某个结点的指针结论结论50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字=50,505035,503040355090,50809095,4 4、二叉排序树的查找算法、二叉排序树的查找算法若二
20、叉排序树为空为空，则查找不成查找不成功功；否则若给定值等于等于根结点的关键字，则查查找成功找成功；若给定值小于小于根结点的关键字，则继继续在续在左子树左子树上进行查找上进行查找；若给定值大于大于根结点的关键字，则继继续在续在右子树右子树上进行查找上进行查找。BSTree SearchBST(BSTree bst,KeyType key)/在根结点在根结点bst所指的二叉排序树中，递归查找关键字等所指的二叉排序树中，递归查找关键字等于于key的元素，若查找成功，返回指向该元素结点的指的元素，若查找成功，返回指向该元素结点的指针，否则返回空指针针，否则返回空指针if(!bst)Else if(bs
21、t-key=key)Else if(bst-keykey)elseReturn NULL Return bst /查找成功查找成功Return SearchBST(bst-lchild,key);/在左子树中继续查找在左子树中继续查找Return SearchBST(bst-rchild,key);/在右子树中继续查找在右子树中继续查找 BSTree SearchBST(BSTree bst,KeyType key)/在根结点在根结点bst所指的二叉排序树中，查找关键字等于所指的二叉排序树中，查找关键字等于key的元素，若查找成功，返回指向该元素结点的指针，否则的元素，若查找成功，返回指向该元
22、素结点的指针，否则返回空指针返回空指针 BSTree q;q=bst;While (q)if (q-key=key)return q;if(q-keykey)q=q-lchild;else q=q-rchild;return NULL;BSTNode *DelBST(BSTree t,KeyType k)/在二叉排序树t中删除关键字为K的结点BSTNode *p,*f,*s,*q;P=t;f=NULL;While(p)if (p-key=k)break;f=p;if(p-keyk)p=p-lchild;else p=p-rchild;If(p=NULL)return t /若找不到，返回原二叉
23、树若找不到，返回原二叉树If(p-lchild=NULL)if(f=NULL)t=p-rchild;else if(f-lchild=p)f-lchild=p-rchild;else f-rchild=p-rchild;free(p);Else q=p;s=p-lchild;while (s-rchild)q=s;s=s-rchild;if(q=p)q-lchild=s-lchild;else q-rchild=s-lchild;p-key=s-key;free(s);/DelBST36哈希表的相关定义哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的查找分析基本思想基本思想 首先在元素的关
24、键字首先在元素的关键字k k和元素的存储位置和元素的存储位置p p之间之间建立一个对应关系建立一个对应关系H H，使得，使得p=H(k),p=H(k),H H称为称为哈希函数哈希函数 创建创建哈希表哈希表时，把关键字为时，把关键字为K K的元素直接存入的元素直接存入地址为地址为H(k)H(k)的单元的单元;当查找关键字为当查找关键字为k k的元素时，再利用哈希函数的元素时，再利用哈希函数计算出该元素的存储位置计算出该元素的存储位置p=H(k),p=H(k),从而达到按关从而达到按关键字直接存取元素的目的。键字直接存取元素的目的。哈希表哈希表 根据设定的哈希函数根据设定的哈希函数 H(key)和
25、所选中的处理和所选中的处理冲突的方法，将一组关键字映象到一个有限的、冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集地址连续的地址集(区间区间)上，并以关键字在地址上，并以关键字在地址集中的集中的“象象”作为相应记录在表中的存储位置，作为相应记录在表中的存储位置，如此构造所得的查找表称之为如此构造所得的查找表称之为“哈希表哈希表”。例例 30个地区的各民族人口统计表个地区的各民族人口统计表编号编号 地区地区 总人口总人口 汉族汉族 回族回族1 北京北京2 上海上海.以编号作关键字，以编号作关键字，构造构造哈希函数：哈希函数：H(key)=keyH(1)=1H(2)=2以地区名作关键字，取地区以地区名作关键字，取地区名称第一个拼音字母的序号名称第一个拼音字母的序号作哈希函数：作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19从例子可见：从例子可见：哈希函数只是一种映象，所以哈希哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许键字的哈希函数值都落在表长允许的范围之内即可。的范围之内即可。冲突：冲突：key1key1 key2key2，但但H(key1)=H(key2)H(key1)=H(key2)的现象的现象
