数据结构查找

数据结构课件查找第1页，共40页，2023年，2月20日，星期六

查找中用到如下的基本概念。例如8.1查找基本的概念2列表关键字查找平均查找长度基本查找方法第2页，共40页，2023年，2月20日，星期六姓名学号性别年龄班级健康黄佳9831男18计98良好钱昌9832女17计98一般王羽9833男19计98近视高甜9834女18计98一般………………………………列表：由同一类型的数据元素（或记录）构成的集合。关键字：数据元素的某个数据项的值，用它可标识列表中的一个或一组数据元素查找：根据给定的关键字值，在列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。第3页，共40页，2023年，2月20日，星期六平均查找长度定义：为确定数据元素在列表中的位置，需和给定关键值进行比较的关键值个数的期望值，称为查找算法在查找成功时的平均查找长度Pi是查找第i个元素概率，Ci是为找到第i个元素进行的比较次数第4页，共40页，2023年，2月20日，星期六顺序查找法5折半查找分块查找法8.2基于线性表的查找法第5页，共40页，2023年，2月20日，星期六 8.2.1顺序查找法1、数据类型的定义#defineLiST_SIZE20Typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;Typedefstruct{RecordTyper[LIST_SIZE+1];//r[0]为工作单元

intlength;}RecordList第6页，共40页，2023年，2月20日，星期六2、顺序查找法设置监视哨intSeqSearch(RecordListl,KeyTypek)//在顺序表l中顺序查找关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0.{l.r[0].key=k;i=l.length;while(l.r[i].key!=k)i--;return(i);}不设监视哨

intSeqSearch(RecordListl,KeyTypek)//不用监视哨，在顺序表中查找关键字等于k的元素

i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>1)return(i);elsereturn(0);}第7页，共40页，2023年，2月20日，星期六3、性能分析

假设列表长度为n，那么查找第i个数据元素需要进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n,则顺序查找算法的平均查找长度为：第8页，共40页，2023年，2月20日，星期六 8.2.2折半查找法1、折半查找定义折半查找法又称二分查找法，这种方法对待查找的列表有两个要求:⑴列表必须是顺序存储结构⑵列表必须按关键字大小有序排列学号姓名平均成绩其它0001

王一90.2…….0002张三70…………………………0032李四75.5……0034

刘四80.0…………………….…….0060钱五68…….第9页，共40页，2023年，2月20日，星期六2、基本过程

将表中间位置记录的关键字与需要查找的关键字比较

如果两者相等，则查找成功;

否则利用中间记录将表分成前、后两个子表;

如果列表中间位置记录的关键字大于要查找关键字，则进一步查找前一子表

否则进一步查找后一子表。第10页，共40页，2023年，2月20日，星期六3、算法IntBinSrch(RecordListl,KeyTypek)//在有序表中折半查找其关键字等于k的元素，若找到，则函数返回值为该元素在表中的位置d{low=1;high=l.length;

//置区间初值While(low<=high){mid=(low+high)

if(k==l.r[mid].key)return(mid)

//找到待查元素elseif(k<l.r[mid].key)high=mid-1;elselow=mid+1;

}

return(0);}第11页，共40页，2023年，2月20日，星期六4、性能分析

折半查找过程可用一二叉判定树描述。二叉判定树结构：树中每一结点对应表中一记录，结点值设为记录在列表中的位置序号。61215182225283546586012345678101163124597810119第12页，共40页，2023年，2月20日，星期六4、性能分析

从根到被查结点路径关键字比较次数为被查结点层次数

假设表的长度n=2h-1,则相应判定树必为深度是h的满二叉树，h=log2(n+1)

又假设每个记录的查找概率相等，则折半查找成功时的平均查找长度为

树中层次为1的结点有1个，层次为2的结点有2个，层次为h的结点有2h-1个第13页，共40页，2023年，2月20日，星期六5、二叉判定树举例(Apr,Aug,Dec,Feb,Jan,July,june,Mar,May,Nov,Oct,Sep)JulyDecAugAprFebJanMayJuneMarOctSepNov其在等概率(1/12)的情况下，查找成功的平均查找长度：ASL＝（1+2*2+3*4+4*5)/12=3.1第14页，共40页，2023年，2月20日，星期六算法优点比较次数少查找速度快平均性能好算法缺点待查表为有序表插入、删除困难第15页，共40页，2023年，2月20日，星期六 8.2.3分块查找法1、对所查表的要求⑴将列表分成若干块（子表），一般情况下，块的长度均匀，最后一块可不满⑵每块内元素无序⑶块与块间有序1814122582832453658608871

0

1234567891011122558880510索引表第16页，共40页，2023年，2月20日，星期六2、基本思想⑴构造一索引表⑵将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。⑶用顺序查找法，在相应块内查找关键字为K的元素第17页，共40页，2023年，2月20日，星期六3、平均查找长度

设查找索引表的平均查找长度LB，相应块内顺序查找的平均查找长度LW，则平均查找长度：ASLbs=LB+Lw

假定将长度为n的表分成b块，每块内含s个元素，则b=n/s.

假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b,块内每个元素的查找概率为1/s,则有顺序法平均查找长度折半法平均查找长度第18页，共40页，2023年，2月20日，星期六查找方法比较顺序查找折半查找分块查找ASL最大最小两者之间表结构有序表，无序表有序表分块有序表存储结构顺序存储结构，线性链表顺序存储结构，顺序存储结构，线性链表第19页，共40页，2023年，2月20日，星期六课堂练习例1：折半查找有序表（4，6，10，12，20，30，50，70，88，100），若查找元素58，则它将依次与表中那些元素比较，查找结果失败。例2：对于具有144个记录的文件，若采用分块查找，且每块长度为8,则平均查找长度为多少？第20页，共40页，2023年，2月20日，星期六二叉排序树21平衡二叉排序树B树8.3基于树的查找法第21页，共40页，2023年，2月20日，星期六 8.3.1二叉排序树1、定义二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：⑴若它的左子树非空，则左子树上所有结点的值均小于根结点的值⑵若它的右子树非空，则右子树上所有结点的值均大于根结点的值⑶它的左右子树也分别为二叉排序树503020104025238090858835是二叉排序树66不21第22页，共40页，2023年，2月20日，星期六2、二叉排序树的存储结构取二叉链表作为二叉排序树的存储结构TypedefstructBiTNode{

KeyTypeKey;structBiTnode*lchild,*rchild}BiTNode,*BSTree第23页，共40页，2023年，2月20日，星期六3、二叉排序树的插入【算法思想】5030802090854035883250505030403550508090⑴若二叉树是空，则新结点Ｓ是二叉树的根⑵若二叉树非空，则将S.key与二叉排序树根结点的关键字进行比较：a.若S.key的值等于根结点的值，则停止插入；b.若S.key的值小于根结点的值，则将Ｓ插入左子树；c.若S.key的值大于根结点的值，则将Ｓ插入右子树；20328588第24页，共40页，2023年，2月20日，星期六VoidInsertBST(BSTree*bst,KeyTypekey)//若在二叉排序树中不存在关键字等于key的元素，插入该元素{Bitrees;If(*bst==NULL)

//递归结束条件

Elseif(key<(*bst)->key)

//将s插入左子树Elseif(key>(*bst)->key)

//将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页，2023年，2月20日，星期六BSTNode*InsertBST(BSTreeroot,KeyTypekey)//若在二叉排序树中不存在关键字等于key的元素，插入该元素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;r>rchild=NULL;二叉排序树插入的非递归算法第26页，共40页，2023年，2月20日，星期六if(q->key==key)return;

if(q->key>key)q->lchild=r;//插入r做q的左孩子else

q->rchild=r;//插入r做q的右孩子}returnroot;}while(p)//寻找新结点的插入位置

{q=p;if(p->key>key)p=p->lchild;elsep=p->rchild;}第27页，共40页，2023年，2月20日，星期六一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列每次插入的新结点都是二叉排序树上新的叶子结点插入时不必移动其它结点，仅需修改某个结点的指针结论第28页，共40页，2023年，2月20日，星期六50308020908540358832例如:二叉排序树查找关键字==50,505035,503040355090,50809095,第29页，共40页，2023年，2月20日，星期六4、二叉排序树的查找算法若二叉排序树为空，则查找不成功；否则⑴若给定值等于根结点的关键字，则查找成功；⑵若给定值小于根结点的关键字，则继续在左子树上进行查找；⑶若给定值大于根结点的关键字，则继续在右子树上进行查找。第30页，共40页，2023年，2月20日，星期六BSTreeSearchBST(BSTreebst,KeyTypekey){//在根结点bst所指的二叉排序树中，递归查找关键字等于key的元素，若查找成功，返回指向该元素结点的指针，否则返回空指针if(!bst)Elseif(bst->key==key)Elseif(bst->key>key)elseReturnNULL

Returnbst//查找成功ReturnSearchBST(bst->lchild,key);//在左子树中继续查找ReturnSearchBST(bst->rchild,key);//在右子树中继续查找}第31页，共40页，2023年，2月20日，星期六BSTreeSearchBST(BSTreebst,KeyTypekey){//在根结点bst所指的二叉排序树中，查找关键字等于key的元素，若查找成功，返回指向该元素结点的指针，否则返回空指针{BSTreeq;q=bst;While(q){if(q->key==key)returnq;if(q->key>key)q=q->lchild;elseq=q->rchild;}returnNULL;}第32页，共40页，2023年，2月20日，星期六BSTNode*DelBST(BSTreet,KeyTypek){//在二叉排序树t中删除关键字为K的结点BSTNode*p,*f,*s,*q;P=t;f=NULL;While(p){if(p->key==k)break;f=p;if(p->key>k)p=p->lchild;elsep=p->rchild;}If(p==NULL)returnt//若找不到，返回原二叉树第33页，共40页，2023年，2月20日，星期六If(p->lchild==NULL){if(f==NULL)t=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild;elsef->rchild=p->rchild;free(p);第34页，共40页，2023年，2月20日，星期六Else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}if(q==p)q->lchild=s->lchild;elseq->rchild=s->lchild;p->key=s->key;free(s);}}//DelBST第35页，共40页，2023年，2月20日，星期六368.4计算式查找法－哈希法哈希表的相关定义哈希函数的构造方法