数据结构查找精品文稿.ppt

数据结构课件查找第1页，本讲稿共40页 查找中用到如下的基本概念。例如查找中用到如下的基本概念。例如查找中用到如下的基本概念。例如查找中用到如下的基本概念。例如8.1查找基本的概念查找基本的概念2列表列表列表列表关键字关键字关键字关键字查找查找查找查找平均查找长度平均查找长度平均查找长度平均查找长度基本查找方法基本查找方法基本查找方法基本查找方法第2页，本讲稿共40页姓名姓名姓名姓名学号学号学号学号性别性别性别性别年龄年龄年龄年龄班级班级班级班级健康健康健康健康黄佳黄佳黄佳黄佳98319831男男男男1818计计计计9898良好良好良好良好钱昌钱昌钱昌钱昌98329832女女女女1717计计计计9898一般一般一般一般王羽王羽王羽王羽98339833男男男男1919计计计计9898近视近视近视近视高甜高甜高甜高甜98349834女女女女1818计计计计9898一般一般一般一般列表：列表：由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。关键字：关键字：数据元素的某个数据项的值，用它可标识列表中的一个数据元素的某个数据项的值，用它可标识列表中的一个或一组数据元素或一组数据元素查找查找：根据给定的关键字值，在列表中确定一个其关键字与给定值相：根据给定的关键字值，在列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。同的数据元素，并返回该数据元素在列表中的位置。第3页，本讲稿共40页平均查找长度平均查找长度定义：为确定数据元素在列表中的位置，需和给定关键值进行比定义：为确定数据元素在列表中的位置，需和给定关键值进行比较的关键值个数的期望值，称为查找算法在查找成功时的较的关键值个数的期望值，称为查找算法在查找成功时的平均查平均查找长度找长度P Pi i是查找第是查找第i i个元素概率，个元素概率，C Ci i是为找到第是为找到第i i个元素进行的比较次数个元素进行的比较次数第4页，本讲稿共40页顺序查找法顺序查找法5折半查找折半查找分块查找法分块查找法8.2基于线性表的查找法基于线性表的查找法第5页，本讲稿共40页8.2.1 顺序查找法顺序查找法1 1、数据类型的定义、数据类型的定义#define LiST_SIZE 20Typedef struct KeyType key;OtherType other_data;RecordType;Typedef struct RecordType rLIST_SIZE+1;/r0为工作单元为工作单元 int length;RecordList第6页，本讲稿共40页2 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(RecordList l,KeyType k)/不用监视哨，在顺序表中查找关键字等于不用监视哨，在顺序表中查找关键字等于k的元的元素素 i=l.length;while(i=1&l.ri.key!=k)i-;if(i1)return(i);else return(0);第7页，本讲稿共40页3、性能分析、性能分析 假设列表长度为假设列表长度为n，那么查找第，那么查找第i个数据元素需要进行个数据元素需要进行n-i+1次比较，次比较，即即Ci=n-i+1。又假设查找每个数据元素的概率相等，即。又假设查找每个数据元素的概率相等，即Pi=1/n,则顺序查则顺序查找算法的平均查找长度为：找算法的平均查找长度为：第8页，本讲稿共40页8.2.2 折半查找法折半查找法1 1、折半查找定义、折半查找定义折半查找法又称二分查找法，这种方法对待查找的列表有折半查找法又称二分查找法，这种方法对待查找的列表有两个要求两个要求:列表必须是列表必须是顺序存储结构顺序存储结构 列表必须按列表必须按关键字大小有序排列关键字大小有序排列 学号学号姓名姓名平均成绩平均成绩其它其它00010001 王一王一90.290.2.00020002张三张三707000320032李四李四75.575.500340034 刘四刘四80.080.0.00600060钱五钱五6868.第9页，本讲稿共40页2 2、基本过程、基本过程 将表中间位置记录的关键字与需要查找的关键字比较将表中间位置记录的关键字与需要查找的关键字比较 如果如果两者相等，则查找成功两者相等，则查找成功;否则否则利用中间记录将表分成前、后两个子表利用中间记录将表分成前、后两个子表;如果如果列表中间位置记录的关键字大于要查找关键字，列表中间位置记录的关键字大于要查找关键字，则进一步查找前一子表则进一步查找前一子表 否则否则进一步查找后一子表。进一步查找后一子表。第10页，本讲稿共40页3 3、算法、算法Int BinSrch(RecordList l,KeyType k)/在有序表中折半查找其关键字等于在有序表中折半查找其关键字等于k k的元素，若找到，则函数返回值为该的元素，若找到，则函数返回值为该元素在表中的位置元素在表中的位置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);第11页，本讲稿共40页4 4、性能分析、性能分析 折半查找过程可用一折半查找过程可用一二叉判定树二叉判定树描述。描述。二叉判定树结构：二叉判定树结构：树中每一结点对应表中一记录，结点值设为记录树中每一结点对应表中一记录，结点值设为记录在列表中的位置序号。在列表中的位置序号。61215182225283546586012345678101163124597810119第12页，本讲稿共40页4 4、性能分析、性能分析 从根到被查结点路径关键字比较次数为被查从根到被查结点路径关键字比较次数为被查结点结点层次数层次数 假设表的长度假设表的长度n=2n=2h h-1,-1,则相应判定树必为深则相应判定树必为深度是度是h h的满二叉树，的满二叉树，h=logh=log2 2(n+1)(n+1)又假设每个记录的查找概率相等，则折半又假设每个记录的查找概率相等，则折半查找成功时的查找成功时的平均查找长度为平均查找长度为 树中层次为树中层次为1 1的结点有的结点有1 1个，层次为个，层次为2 2的的结点有结点有2 2个，层次为个，层次为h h的结点有的结点有2 2h-1h-1个个第13页，本讲稿共40页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第14页，本讲稿共40页算法优点算法优点比较次数少比较次数少查找速度快查找速度快平均性能好平均性能好算法缺点算法缺点待查表为有序表待查表为有序表插入、删除困难插入、删除困难第15页，本讲稿共40页8.2.3 分块查找法分块查找法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索引表索引表第16页，本讲稿共40页2 2、基本思想、基本思想构造一索引表构造一索引表将待查关键字将待查关键字K K与索引表中的关键字进行比较，以确定待查记录所在与索引表中的关键字进行比较，以确定待查记录所在的块。的块。用顺序查找法，在相应块内查找关键字为用顺序查找法，在相应块内查找关键字为K K的元素的元素第17页，本讲稿共40页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.假定表中每个元素的查找概率相等，则每个索引项的查找概率为假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b,1/b,块内每个元素的查找概率为块内每个元素的查找概率为1/s,1/s,则有则有顺序法平均查找长度顺序法平均查找长度折半法平均查找长度折半法平均查找长度第18页，本讲稿共40页查找方法比较查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找ASLASL最大最大最小最小两者之间两者之间表结构表结构有序表，无序表有序表，无序表有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构，顺序存储结构，线性链表线性链表顺序存储结顺序存储结构，构，顺序存储结构，顺序存储结构，线性链表线性链表第19页，本讲稿共40页课堂练习课堂练习例例1 1：折半查找有序表（：折半查找有序表（4 4，6 6，1010，1212，2020，3030，5050，7070，8888，100100），），若查找元素若查找元素5858，则它将依次与表中那些元素比较，查找结果失败。，则它将依次与表中那些元素比较，查找结果失败。例例2 2：对于具有：对于具有144144个记录的文件，若采用分块查找，且每块长度为个记录的文件，若采用分块查找，且每块长度为8,8,则平均查找长度为多少？则平均查找长度为多少？第20页，本讲稿共40页二叉排序树二叉排序树21平衡二叉排序树平衡二叉排序树B B树树8.3基于树的查找法基于树的查找法第21页，本讲稿共40页8.3.1 二叉排序树二叉排序树1 1、定义、定义二叉排序树二叉排序树或者是一棵空树，或或者是一棵空树，或者是具有如下性质的二叉树：者是具有如下性质的二叉树：若它的左子树非空，则若它的左子树非空，则左子树上所有结点的值均左子树上所有结点的值均小于小于根结点的值根结点的值若它的右子树非空，则右若它的右子树非空，则右子树上所有结点的值均子树上所有结点的值均大于大于根结点的值根结点的值它的左右子树也分别为二它的左右子树也分别为二叉排序树叉排序树503020104025238090858835是二叉排序树是二叉排序树66不不21第22页，本讲稿共40页2 2、二叉排序树的存储结构、二叉排序树的存储结构取二叉链表作为二叉排序树的存储结构取二叉链表作为二叉排序树的存储结构Typedef struct BiTNode KeyType Key;struct BiTnode *lchild,*rchildBiTNode,*BSTree第23页，本讲稿共40页3、二叉排序树的插入、二叉排序树的插入【算法思想算法思想】5030802090854035883250505030403550508090若二叉树是空，则新结点若二叉树是空，则新结点是二叉树的根是二叉树的根若二叉树非空，则将若二叉树非空，则将S.keyS.key与二叉排序树根结与二叉排序树根结点的关键字进行比较：点的关键字进行比较：a.a.若若S.keyS.key的值等于根结点的的值等于根结点的值，则停止插入；值，则停止插入；b.b.若若S.keyS.key的值小于根结点的的值小于根结点的值，则将插入左子树；值，则将插入左子树；c.c.若若S.keyS.key的值大于根结点的的值大于根结点的值，则将插入右子树；值，则将插入右子树；20328588第24页，本讲稿共40页Void InsertBST(BSTree *bst,KeyType key)/若在二叉排序树中不存在关键字等于若在二叉排序树中不存在关键字等于keykey的元素，插入该元素的元素，插入该元素 Bitree s;If(*bst=NULL)/递归结束条件递归结束条件 Else if(keykey)/将将s s插入左子树插入左子树Else if(key(*bst)-key)/将将s s插入右子树插入右子树s=(BSTree)malloc(sizeof(BSTNode)s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;InsertBST(&(*bst)-lchild),key);InsertBST(&(*bst)-rchild),key);第25页，本讲稿共40页 BSTNode*InsertBST(BSTree root,KeyType key)/若在二叉排序树中不存在关键字等于若在二叉排序树中不存在关键字等于keykey的元素，插入该元素的元素，插入该元素if(root=NULL）s=(BSTree)malloc(sizeof(BSTNode)s-key=key;s-lchild=NULL;s-rchild=NULL;root=s;else p=root;/建立新结点建立新结点 r=(BSTree)malloc(sizeof(BSTNode);r-key=key;r-lchild=NULL;rrchild=NULL;二叉排序树插入的非递归算法二叉排序树插入的非递归算法第26页，本讲稿共40页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)/寻找新结点的插入位置寻找新结点的插入位置 q=p;if(p-keykey)p=p-lchild;else p=p-rchild;第27页，本讲稿共40页一个无序序列可以通过构造一棵二叉排一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列序树而变成一个有序序列每次插入的新结点都是二叉排序树上每次插入的新结点都是二叉排序树上新的叶子结点新的叶子结点插入时不必移动其它结点，仅需修改某插入时不必移动其它结点，仅需修改某个结点的指针个结点的指针结论结论第28页，本讲稿共40页50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字=50,505035,503040355090,50809095,第29页，本讲稿共40页4 4、二叉排序树的查找算法、二叉排序树的查找算法若二叉排序树为空为空，则查找不成查找不成功功；否则若给定值等于等于根结点的关键字，则查找成查找成功功；若给定值小于小于根结点的关键字，则继续继续在在左子树左子树上进行查找上进行查找；若给定值大于大于根结点的关键字，则继续继续在在右子树右子树上进行查找上进行查找。第30页，本讲稿共40页BSTree SearchBST(BSTree bst,KeyType key)/在根结点在根结点bst所指的二叉排序树中，递归查找关键字等于所指的二叉排序树中，递归查找关键字等于key的元素，若查找成功，返回指向该元素结点的指针，的元素，若查找成功，返回指向该元素结点的指针，否则返回空指针否则返回空指针if(!bst)Else if(bst-key=key)Else if(bst-keykey)elseReturn NULL Return bst /查找成功查找成功Return SearchBST(bst-lchild,key);/在左子树中继续查找在左子树中继续查找Return SearchBST(bst-rchild,key);/在右子树中继续查找在右子树中继续查找 第31页，本讲稿共40页BSTree SearchBST(BSTree bst,KeyType key)/在根结点在根结点bst所指的二叉排序树中，查找关键字等于所指的二叉排序树中，查找关键字等于key的元的元素，若查找成功，返回指向该元素结点的指针，否则返回空指素，若查找成功，返回指向该元素结点的指针，否则返回空指针针 BSTree q;q=bst;While (q)if (q-key=key)return q;if(q-keykey)q=q-lchild;else q=q-rchild;return NULL;第32页，本讲稿共40页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 /若找不到，返回原二叉树若找不到，返回原二叉树第33页，本讲稿共40页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);第34页，本讲稿共40页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);/DelBST第35页，本讲稿共40页368.4计算式查找法哈希法计算式查找法哈希法哈希表的相关定义哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的查找分析第36页，本讲稿共40页基本思想基本思想 首先在元素的关键字首先在元素的关键字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),从而达到按关键字直从而达到按关键字直接存取元素的目的。接存取元素的目的。第37页，本讲稿共40页哈希表哈希表 根据设定的哈希函数根据设定的哈希函数 H(key)和所选中的处理冲和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连突的方法，将一组关键字映象到一个有限的、地址连续的地址集续的地址集(区间区间)上，并以关键字在地址集中的上，并以关键字在地址集中的“象象”作为相应记录在表中的存储位置，如此构造所得的查作为相应记录在表中的存储位置，如此构造所得的查找表称之为找表称之为“哈希表哈希表”。第38页，本讲稿共40页例例 30个地区的各民族人口统计表个地区的各民族人口统计表编号编号 地区地区 总人口总人口 汉族汉族 回族回族1 北京北京2 上海上海.以编号作关键字，以编号作关键字，构造哈希函数：构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区名作关键字，取地区以地区名作关键字，取地区名称第一个拼音字母的序号名称第一个拼音字母的序号作哈希函数：作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19第39页，本讲稿共40页从例子可见：从例子可见：哈希函数只是一种映象，所以哈希函哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围的哈希函数值都落在表长允许的范围之内即可。之内即可。冲突：冲突：key1key1 key2key2，但，但H(key1)=H(key2)H(key1)=H(key2)的现象的现象第40页，本讲稿共40页