数据结构单元查找.pptx

教学目标【知识目标】了解查找的基本概念掌握顺序查找的基本思想、算法实现和查找效率分析掌握二分查找的基本思想、算法实现和查找效率分析掌握分块查找的基本思想、算法实现和查找效率分析掌握二叉查找树的插入、删除、建树和查找算法及时间性能掌握哈希查找方法、哈希函数的构造和解决冲突的方法【能力目标】具有选择恰当的查询算法解决实际问题的能力 第1页/共48页引例描述高校最低录取分数线查询 该系统用于学生、学生家长和其他人员查询各高校的最低录取分数线，为他们的了解高校录取情况、做出正确的选择和决策提供有必要的信息。该系统有以下六项功能：（1）按考生分数查询高校信息；（2）按给定分数查询一定范围内的高校信息，包括：查询录取分数线比给定分数高（包括相等）的高校信息和录取分数线比给定分数低（包括相等）的高校信息；（3）按给定的分数范围查询高校信息；（4）能够添加高校信息；（5）为用户提供系统帮助，以便更好的使用系统；（6）安全退出本系统。演示执行 第2页/共48页一、基本概念1查找定义 给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。2动态查找表和静态查找表 若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表。否则称之为静态查找表。3内查找和外查找 若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。7.1 查找的基本概念 知识储备第3页/共48页4平均查找长度（Average Search Length）ASL 查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL定义：即ASL等于每个结点的查找概率pi与比较次数ci的乘积的和。其中：（1）n是结点的个数；（2）pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即pl=p2=pn=1/n；（3）ci是找到第i个结点所需进行的比较次数。第4页/共48页一、顺序查找（sequential search）顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链表。1基本思想 从表的一端开始，顺序扫描线性表，依次按给定值kx与关键字（Key）进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表查找完毕，仍未找到与kx相同的关键字，则查找失败，给出失败信息。2基于顺序结构的顺序查找算法的类型描述 7.2 静态查找#define N 20typedef int KeyType;/关键字字段类型定义typedef char OtherdataType;/非关键字字段类型定义typedef structKeyType key;OtherdataType data;NodeType;typedef NodeType SeqListN+1;/0号单元用作监视哨第5页/共48页3具体算法4算法分析（1）算法中监视哨R0的作用 为了在for循环中省去判定防止下标越界的条件i1，从而节省比较的时间。（2）成功时的顺序查找的平均查找长度 在等概率情况下，pi=1/n(1in)，故成功的平均查找长度为(n+2+1)/n=(n+1)/2，即查找成功时的平均比较次数约为表长的一半，若K值不在表中，则须进行n+1次比较之后才能确定查找失败。（3）顺序查找的优缺点 优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。int SeqSearch(Seqlist R,KeyType K)/在顺序表R1.n中查找关键字为K的结点int i;R0.key=K;/设置哨兵for(i=n;Ri.key!=K;i-);/从表后往前找return i;/若i为0，表示查找失败，否则Ri是要找的结点 第6页/共48页2二、二分查找（binary search）1二分查找：二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。2二分查找的基本思想 设Rlow.high是当前的查找区间。（1）首先确定该区间的中点位置：mid=(low+high)/2;（2）然后将待查的K值与Rmid.key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：第7页/共48页若Rmid.keyK，则由表的有序性可知Rmidn.key均大于K，因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R1mid-1中，故新的查找区间是左子表R1.mid-1；若Rmid.keyK，类似地，则新的查找区间是右子表Rmid+1n。下次在新的查找区间进行查找。因此，从初始的查找区间R1.n开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空（即查找失败）时为止。第8页/共48页3二分查找算法int BinSearch(SeqList R,KeyType K)int low=1,high=n,mid;/置当前查找区间的初值while(lowK)high=mid-1;elselow=mid+1;return 0;/当lowhigh时查找区间为空，查找失败 第9页/共48页4算法分析（1）二分查找的平均查找长度：在等概率假设下，二分查找成功时平均查找长度为：ASLbn=(n+1)/n)lg(n+1)-1；最坏情况下查找成功的比较次数为：。（2）二分查找的优缺点：二分查找效率高，但要将表按关键字排序；二分查找只适用顺序存储结构。对经常进行插入和删除操作的表，不宜采用此方法。第10页/共48页三、分块查找（block search）分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。1二分查找表存储结构 二分查找表由“分块有序”的线性表和索引表组成。（1）“分块有序”的线性表：表R1.n均分为b块，前b-1块中结点个数为是s=n/b，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序”的。（2）索引表：抽取各块中的最大关键字及其起始位置构成一个索引表IDl.b，即：IDi(1ib)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。【示例】图7-1给出的就是满足上述要求的存储结构，其中R只有15个结点，被分成3块，每块中有5个结点，第一块中最大关键字22小于第二块中最小关键字24，第二块中最大关键字44小于第三块中最小关键字47。图7-1 分块查找2247416111234567891011121314152212139833424438244860587447最大关键字值块地址IDR第11页/共48页2分块查找的基本思想 先在索引表中采用二分查找或顺序查找，以确定待查的结点在哪一块；然后在已确定的块中进行顺序查找。3算法分析（1）平均查找长度ASL：将含有n个元素的线性表平均分成b块，每块有s个元素。整个查找过程的平均查找长度是两次查找的平均查找长度之和。以二分查找来确定块，分块查找成功时的平均查找长度ASLblk=ASLbn+ASLsq=lg(b+1)-1+(s+1)/2。以顺序查找确定块，分块查找成功时的平均查找长度ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)。（2）分块查找的优缺点：在表中插入或删除记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算；因块内记录的存放是任意的，所以插入或删除无须移动大量记录；分块查找的主要代价是增加辅助存储空间和将初始表分块排序的运算。第12页/共48页一、二叉排序树（Binary Sort Tree）1二叉排序树的定义 二叉排序树又称二叉查找（搜索）树（Binary Search Tree）。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；（3）左、右子树本身又各是一棵二叉排序树。上述性质简称二叉排序树性质（BST性质），故二叉排序树实际上是满足BST性质的二叉树。7.3 动态查找 第13页/共48页2二叉排序树的特点（1）二叉排序树中任一结点x，其左(右)子树中任一结点y（若存在）的关键字必小（大）于x的关键字。（2）二叉排序树中，各结点关键字是惟一的。（3）按中序遍历该树所得到的中序序列是一个递增有序序列。注意：实际应用中，被查找的数据集中各元素的关键字可能相同，所以可将BST性质（1）里的“小于”改为“小于等于”，或将性质（2）里改为“大于等于”。【示例】如图7-2所示的两棵树均是二叉排序树，满足BST性质，它们的中序序列均为有序序列2，3，4，5，7，8。图7-2 二叉排序树238574(a)(b)723845第14页/共48页3二叉排序树的结构描述 typedef int KeyType;/关键字类型定义typedef char OtherdataType;/非关键字字段类型定义typedef struct node /结点类型KeyType key;/关键字项OtherdataType data;/其它数据域struct node*lchild,*rchild;/左右孩子指针 BSTNode;typedef BSTNode*BSTree;/BSTree是二叉排序树的类型第15页/共48页二、二叉排序树上的运算1二叉排序树的插入 二叉排序树插入新结点的过程：在二叉排序树中插入新结点，要保证插入后仍满足BST性质。插入过程是：（1）若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；（2）若二叉排序树T不空，则将key和根的关键字比较：若二者相等，则树中已有此关键字key，无须插入；若keykey，则将key插入根的左子树中；若keyT-key，则将它插入根的右子树中。子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。二叉排序树插入新结点的递归算法 二叉排序树插入新结点的非递归算法 void InsertBSTR(BSTree*Tptr,KeyType key)if(!(*Tptr)(*Tptr)=(BSTNode*)malloc(sizeof(BSTNode);if(*Tptr=NULL)puts(内存申请不成功!);return;(*Tptr)-key=key;(*Tptr)-lchild=NULL;(*Tptr)-rchild=NULL;elseif(*Tptr)-key=key)return;if(keykey)InsertBSTR(&(*Tptr)-lchild,key);elseInsertBSTR(&(*Tptr)-rchild,key);void InsertBST(BSTree*Tptr,KeyType key)/若二叉排序树*Tptr中没有关键字为key,则插入,否则直接返回BSTNode*f,*p=*Tptr;/p的初值指向根结点while(p)/查找插入位置if(p-key=key)return;/树中已有key,无须插入f=p;/f保存当前查找的结点p=(keykey)?p-lchild:p-rchild;/*若keykey，则在左子树中查找，否则在右子树中查找*/p=(BSTNode*)malloc(sizeof(BSTNode);if(p=NULL)puts(内存申请不成功!);return;p-key=key;p-lchild=p-rchild=NULL;/生成新结点if(*Tptr=NULL)/原树为空*Tptr=p;/新插入的结点为新的根else/原树非空时将新结点*p作为*f的左孩子或右孩子插入if(keykey)f-lchild=p;else f-rchild=p;第16页/共48页2二叉排序树的生成算法 二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。BSTree CreateBST(void)/输入一个结点序列，建立二叉排序树，返回根指针BSTree T=NULL;/初始时T为空树KeyType key;scanf(%d,&key);/读入一个关键字while(key)/假设key=0是输入结束标志InsertBSTR(&T,key);/将key插入二叉排序树Tscanf(%d,&key);/读入下一关键字return T;/返回建立的二叉排序树的根指针 第17页/共48页3二叉排序树的删除 从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足BST性质。（1）删除操作的一般步骤进行查找：查找时，令p指向当前访问到的结点，parent指向其双亲(其初值为NULL)。若树中找不到被删结点则返回，否则被删结点是*p。删去*p：删*p时，应将*p的子树(若有)仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。第18页/共48页（2）删除*p结点的三种情况*p是叶子：无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。*p只有一个孩子*child：只需将*child和*p的双亲直接连接后，即可删去*p。注意：*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态。*p有两个孩子：先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*r，并在查找过程中仍用parent记住*r的双亲位置。*q的中序后继*r一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*r的操作，即在释放结点*r之前将其数据复制到*q中，就相当于删去了*q。void DelBSTNode(BSTree*Tptr，KeyType key)/在二叉排序树*Tptr中删去关键字为key的结点BSTNode*parent=NULL,*p=*Tptr,*q,*child;while(p)/从根开始查找关键字为key的待删结点if(p-key=key)break;/已找到，跳出查找循环parent=p;/parent指向*p的双亲p=(keykey)?p-lchild:p-rchild;/在*p的左或右子树中继续找if(!p)return；/找不到被删结点则返回q=p;/q记住被删结点*pif(q-lchild&q-rchild)for(parent=q,p=q-rchild;p-lchild;parent=p,p=p=-lchild);child=(p-lchild)?p-lchild:p-rchild;if(!parent)*Tptr=child;else/*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下if(p=parent-lchild)/*p是双亲的左孩子parent-lchild=child;/*child作为*parent的左孩子else parent-rchild=child;/*child作为*parent的右孩子if(p!=q)/是情况(3)，需将*p的数据复制到*qq-key=p-key;/若还有其它数据域亦需复制free(p)；/释放*p占用的空间 第19页/共48页4二叉排序树的查找查找递归算法：在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。BSTNode*SearchBST(BSTree T,KeyType key)/在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULLif(T=NULL|key=T-key)/递归的终结条件return T;if(keykey)return SearchBST(T-lchild,key);elsereturn SearchBST(T-rchild,key);第20页/共48页说明：在二叉排序树上进行查找时，若查找成功，则是从根结点出发走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。二叉排序树查找成功的平均查找长度：在等概率假设下，二叉排序树查找成功的平均查找长度为O(lgn)。与二分查找类似，和关键字比较的次数不超过树的深度。在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关。第21页/共48页【课堂实践6-1】已知关键字序列为(51，22，83，46，75，18，68，30)，写出对其进行直接插入排序各趟的状态。做做一一做做第22页/共48页二、希尔排序（Shell Sort）1基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。2希尔排序的算法（1）算法思路先取一个正整数d1(d1n)作为一个增量，把全部记录分成d1个组，所有距离为d1的倍数的记录看成一组，然后在各组内进行插入排序；取下一个增量d2（d2=1)，即所有记录成为一个组为止。（2）增量的选取：希尔排序对增量序列的选择的原则是：最后一个增量必须是1；应尽量避免增量序列中的值（尤其是相邻的值）互为倍数的情况。若违反后一原则，效果肯定很差。第23页/共48页（3）一趟希尔排序的排序算法3算法分析（1）希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题。到目前为止尚未求得一种最好的增量序列，有人在大量实验的的基础推出：当n在某个特定范围内希尔排序所需的比较和移动次数约为n1.25，所以其平均时间复杂度约为O(n1.25)。其辅助空间为O(1)；（2）希尔排序是不稳定的排序方法。void ShellPass(SeqList R,int d)/希尔排序中的一趟排序，d为当前增量int i,j;for(i=d+1;i=n;i+)if(Ri.key0&R0.keySNum,T-SName,T-PM);PreOrder(T-lchild,fp);PreOrder(T-rchild,fp);第38页/共48页int SaveFiles(BSTree T)/退出系统前保存文件FILE*fp;if(fp=fopen(高校信息表.txt,w)=NULL)printf(nt文 件 保 存 不 成 功!n);system(pause);return 0;else PreOrder(T,fp);fclose(fp);return 1;第39页/共48页void InOrder(BSTree T,int PM1,int PM2,int k)/中序遍历二叉排序树，实现输出if(T!=NULL)InOrder(T-lchild,PM1,PM2,k);if(k=1&T-PMPM=PM1)|(k=0&PM1 PM&T-PMSName)15)printf(%stt%st%dn,T-SNum,T-SName,T-PM);elseprintf(%stt%stt%dn,T-SNum,T-SName,T-PM);InOrder(T-rchild,PM1,PM2,k);第40页/共48页BSTNode*SearchBST(BSTree T,int PM)/查找分数线为PM的结点if(T=NULL)|(T-PM=PM)return T;else if(T-PMPM)return SearchBST(T-lchild,PM);else return SearchBST(T-rchild,PM);第41页/共48页BSTNode*InsertBST(BSTree*Tptr,FILE*fp)/二叉排序树插入新结点的非递归算法BSTNode*p=*Tptr,*f,*q;q=(BSTNode*)malloc(sizeof(BSTNode);if(q=NULL)puts(内存申请不成功!);return q;if(fp=NULL)puts(请输入高校代码、学校名称和最低录取分数线（用空格分隔数据）：);scanf(%s%s%d,q-SNum,q-SName,&q-PM);flushall();else fscanf(fp,%st%st%dn,q-SNum,q-SName,&q-PM);q-lchild=q-rchild=NULL;if(*Tptr=NULL)*Tptr=q;return*Tptr;while(p!=NULL)/查找插入位置f=p;p=(p-PMq-PM)?p-lchild:p-rchild;f-PMq-PM?f-lchild=q:f-rchild=q;return q;第42页/共48页int ReadFile(BSTree*T)/读高校信息文件，建立二叉排序树FILE*fp;if(fp=fopen(高校信息表.txt,r)=NULL)printf(nt读文件失败，请先添加高校信息!n);system(pause);return 0;while(!feof(fp)InsertBST(T,fp);fclose(fp);return 1;第43页/共48页int help()/打开系统帮助文件，显示文件信息char*str=(char*)malloc(3000);FILE*fp;if(fp=fopen(系统帮助.txt,r)=NULL)printf(nt读文件失败，帮助文件可能未建立!n);system(pause);return 0;while(!feof(fp)fgets(str,80,fp);printf(%s,str);printf(nn);system(pause);free(str);return 1;第44页/共48页int Menu()int i;system(cls);printf(nt 高校最低录取分数线查询系统n);printf(tn);printf(“t 1.按考生分数查询 2.按分数查询范围 n);printf(tn);printf(“t 3.按分数范围查询 4.添加高校信息 n);printf(tn);printf(“t 5.系统帮助 6.退出系统 n);printf(tn);printf(t 选择操作项(16):);while(1)scanf(%d,&i);flushall();if(i6)printf(t 数据不合法!请重新选择操作项(16):);else return i;第45页/共48页int main()int i,j;BSTree temp,T=NULL;ReadFile(&T);while(1)i=Menu();system(cls);switch(i)case 1:printf(输入考生分数:);scanf(%d,&i);flushall();temp=SearchBST(T,i);if(temp=NULL)printf(没有相关信息,建议选择2或3方式查找!n);system(pause);elseprintf(有以下高校的最低录取线是%d 分:nn,i);printf(高校代码t高校名称tt最低录取线nn);InOrder(T,i,i,0);printf(n);system(pause);break;case 2:printf(输入分数:);scanf(%d,&i);flushall();printf(选择范围:1.录取线在%d分及以下的高校:n,i);printf(t 2.录取线在%d分及以上的高校:,i);scanf(%d,&j);flushall();while(j2|jj)i=i+j;j=i-j;i=i-j;printf(有以下高校满足查询条件:nn);printf(高校代码t高校名称tt最低录取线nn);InOrder(T,i,j,0);printf(n);system(pause);break;case 4:InsertBST(&T,NULL);break;case 5:help();break;case 6:SaveFiles(T);printf(欢迎再次使用，谢谢!n);exit(0);return 1;第46页/共48页再再 见见第47页/共48页感谢您的观看！第48页/共48页