数据结构-3期（KC002） 电子教材 查找的分析与应用.docx

PAGE 157 第8章 查找的分析与应用 【学习目标】 了解查找的基本概念。 熟练掌握线性表的顺序查找和二分法查找方法及算法实现。 熟练掌握二叉排序树的生成和查找方法。 熟练掌握散列表的构造方法、查找过程及解决冲突的方法。 教学指导：第8 教学指导：第8章 查找的分析与应用 PPT：第8章 查找的分析与应用 第8章 查找的分析与应用 第8章 查找的分析与应用 实例描述——通讯录查询系统设计 假设电子通讯录包含姓名、部门、年龄、电话等信息，采用记事本存储具体信息，内容如图8-1所示，在大量的信息中我们如何能够根据要求快速查找得到想要的结果呢？分别可以显示全部通讯录信息、通过姓名查找通讯录信息、通过部门查找通讯录信息，也可以查找青年教师（≤35岁）的通讯录信息。 图8-1通讯录存储示例 知识储备 8.1基本概念微视频：查找的概念 微视频：查找的概念 我们的日常生活离不开各种的查询操作，如通过考号查询高考考分、通过歌名在互联网上检索歌曲等。因此，可以说信息检索是计算机最重要的一种应用。这里，我们所说的查询、检索和查找是同一个概念。 在本章的讨论中，我们假定被查找的对象是由一组结点组成的表或文件，而每个结点则由若干个数据项组成，并假设每个结点都有一个能惟一标识该结点的关键字。在这种假定下，查找的定义是：给定一个值K，在含有N个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。 若在查找的同时对表进行插入或者删除操作，则相应的表称之为动态查找表，否则称之为静态查找表。查找也有内查找和外查找之分。若整个查找过程都在内存进行，则称之内查找；反之，若查找过程中需要访问外存，则称之外查找。 由于查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL（Average Search Length）定义为： ASL= pici 其中：n是结点的个数；pi是查找第i个结点的概率，若不特别声明，均认为每个结点 的查找概率相等，即p1=p2=…=pn=1/n；ci是找到第i个结点所需进行的比较次数。 8.2 线性表查找 在表的组织方式中，线性表是最简单的一种。本节将介绍三种在线性表上进行查找的方法，它们分别是顺序查找、二分查找和分块查找。 8.2.1 顺序查找微视频：顺序查找 微视频：顺序查找 顺序查找是一种最简单的查找方法。实例演示如图8-2所示，要在5名学生当中查找身高为170厘米的学生，从第1号学生开始比较，依次和第2号、第3号比较，直到找到满足条件的学生为止，如果没有满足条件的，查找失败。 动画：身高的顺序查找 动画：身高的顺序查找 身高=170厘米 图8-2 顺序法查找学生描述图 它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到结点的关键字和给定值K相比较，若当前扫描到结点的关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。下面 只介绍以顺序表作为存储结构时实现的顺序查找算法，具体算法如下。 #include stdio.h源 源程序：顺序查找算法 #define n 10 typedef struct { int key; //InfoType otherinfo; }NodeType; int SeqSearch(NodeType R[],int K) { int i; for(i=0;in;i++) if(R[i].key==K) return i; return -1; } main() { int result,i; NodeType SeqList[n]; for(i=0;in;i++) scanf(%d,SeqList[i].key); result=SeqSearch(SeqList,50);//查找K=50 if(result==-1) printf(查找失败!); else printf(查找成功!该数位置是:%d,result); } 动画：顺序查找假设在下面顺序表中查找50，执行SeqSearch函数后，返回值为4。 动画：顺序查找 从下标为0的结点比较关键字和K的大小，只要不相等就继续向后比较直到下标为n-1 ,如果相等就返回下标的值，如果没有相等的关键字就返回-1。 在等概率情况下，pi =1/n，故成功的平均查找长度为(1+2+…+n)/n=(n+1)/2，即查找成功时的平均比较次数约为表长的一半。若K值不在表中，则需要进行n