《软件开发技术基础 第2版 教学课件 ppt 作者 赵英良 第2章 数据结构及其应用3_查找和排序》由会员分享，可在线阅读，更多相关《软件开发技术基础 第2版 教学课件 ppt 作者 赵英良 第2章 数据结构及其应用3_查找和排序（41页珍藏版）》请在金锄头文库上搜索。
1、第2章 数据结构及其应用 2.4查找和排序,西安交通大学 计算机教学实验中心 http:/,软件开发技术基础,2.4.1 查找基的本概念,查找表 关键字 静态查找表，静态查找技术 动态查找表,动态查找技术 动态查找的例子: 词汇统计问题。统计一篇文章中使用了多少词汇以及每个词汇的使用次数。,2,3,查找效果度量平均查找长度（ASL）： 查找过程中，给定值与表中的数据元素的关键字进行比较的次数的期望值。 平均查找长度ASL的计算方法为：,Ci为找到该记录时，曾和给定值比较过的数据元素的个数。 Pi 为查找第i个元素的概率。n 为表长； 在等概率条件下（ Pi=1/n）这时平均查找长度为：,其中：
2、,2.4.2 静态查找技术,顺序查找 折半查找,4,查找表的数据结构,假设静态顺序查找表的存储结构为： struct SSTable ElemType *data; /存储空间地址 int length; /表的长度 ; 顺序查找表的元素存放在data0至datalength-1中。,5,1顺序查找 顺序查找的方法是从表的一端开始，逐一比较给定的数据key和表中数据元素的关键字x的值，若两个数据一致则查找成功，同时给出该数据元素在表中的位置，否则查找失败。,6,顺序查找算法C+语言描述如下： int SqSearch(SSTable 该算法若查找成功，则函数返回值为目标元素在表中的位置，否则返
3、回0。这里元素位置从1开始算起。,7,顺序查找的主程序实现1,typedef struct NODE int x; int y; ElemType; typedef int KeyType;,8,顺序查找的主程序实现2,#include void main() SSTable mtable; ElemType table100; mtable.length =100; mtable.data =table;,9,顺序查找的主程序实现3,int j=1; for(int i=0;i100;i+) tablei.x =10+i; tablei.y =18+i; couttablei.x“t“; i
4、f(j=10) coutendl;j=0; j+; coutSqSearch(mtable, 19)endl; ,10,在上述算法中为了避免“出界”，需在循环中作kL.length 的判断，这使算法的执行时间几乎增加一倍。为提高效率，对查找表的结构改动如下： 适当设置数组长度，将元素存于data1至datalength-1中，在0号单元预存待查找数据key作为监视哨。改写查找过程为从后往前查找。 因为循环查找过程至少会在0号单元停止，这样就不必在每一次循环中都判别是否数组出界。,11,改进的顺序查找算法C+语言描述如下： int SqSearch(SSTable /找不到时，k为0 该算法若查
5、找成功，则函数返回值为目标元素在表中的位置，否则返回0。,12,13,下面分析一下改进的顺序查找算法的时间性能。对于改进的顺序查找而言，找到第i个元素的比较次数Ci = n-i+1，所以在等概率查找的情况下，顺序表查找的平均查找长度为：,2折半查找(也称二分查找 ),顺序查找表的查找算法简单，但平均查找长度较大。如果顺序查找表的元素按照关键字的值有序存放，那么可利用高效的折半查找来完成查询。 假定元素按关键字的值升序排列，折半查找的思路是: 将给定的数据X与有序表中间位置的元素A做比较， 若两者相等则查找成功； 若X小于A则在中间位置左边的元素中继续查找； 若X大于A则在中间位置右边的元素中继
6、续查找。 不断重复这一过程直到查找成功，或者直到查找区间缩小为一个元素时却仍未找到目标，则查找失败。,14,对给定有序数列 5，6，11，17，21，23，28，30，32，40进行半查找算法，查找关键字值为30的数据元素。则查找过程如下： 第1次： 5，6，11，17，21，23，28，30，32，40 low=0 mid=(0+9)/2 =4 high=9 mid=(low+high)/2=4; 3021; low=mid+1=4 第2次： 5，6，11，17，21，23，28，30，32，40 low=5 mid=7 high=9 mid=(low+high)/2=5; 30=data7
7、;查找成功；,15,最大查找长度为,即 O(log2n),折半查找算法的C+语言描述如下： int BinSearch( SSTable /不存在待查元素 ,16,2.4.3 动态查找技术,动态查找技术所依赖的查找表以树状结构居多，例如二叉排序树、B+树、B-树等。 它们的共同特点是结构灵活，易于实现插入、删除等操作。这里主要介绍简单易用的二叉排序树。,17,二叉排序树 二叉排序树可能为一棵空的二叉树，若非空则必须满足以下特征： （1）根结点左子树中所有结 点的关键字小于根结点的关 键字； （2）根结点右子树中所有结 点的关键字大于或等于根结 点的关键字； （3）根结点的左右子树也都 是二叉排
8、序树。,18,一棵二叉排序树,建立了二叉排序树之后，若查找过程中不插入或删除元素(静态查找)，则在二叉排序树中查找方法为： 1)将给定数据key与根结点关键字x进行比较，若key=x则查找成功； 2)若keyx，则与右子树的根结点的关键字值进行比较。 重复上述步骤，直到查找成功；或者一直比较到叶子结点也找不到目标元素，则查找失败。,19,可定义二叉排序树结点如下： typedef struct BinNode ElemType x; /关键字 struct BinNode *left, *right; *BinNodePtr; 二叉排序树查找算法（静态查找）C+语言描述： BinNode *s
9、earch_btree(BinNodePtr ,20,动态查找举例（创建二叉排序树）,二叉排序树的构建 动态查找过程也是生成二叉排序树的过程。 假定由整数序列10，6，19，22，8，2生成一棵二叉排序树，可以采用逐个元素插入的方法实现。,21,二叉排序树动态查找算法C+语言描述如下： BinNode* Search_ Insert (BinNodePtr / 查找失败，插入新结点 ( 见下一页 ),22,23,（接上一页内容） if(p=NULL) / 建立新结点 p=new BinNode; p-left =NULL; p-right=NULL; p-x=key; /新结点不是根，则作为叶
10、子插入 if(pre!=NULL) if(pre-x p-x) pre-left=p; /插入为左孩子 else pre-right=p; /插入为右孩子 return p; /返回找到的结点或插入的新结点的指针 ,例2-7字符统计程序,例2-7 利用二叉排序树统计字符出现次数 该程序可统计由用户输入的一个字符串中各种字符的使用次数。 程序算法是：首先建立空的二叉排序树，每次读入字符后就在树表中查询，若找到则将该字符使用次数加一；否则，将读入的字符插入二叉排序树。 为记录字符使用次数，在二叉树结点定义中增加了使用次数属性。 读完整个字符串后用中序遍历法读出每个字符使用次数。,24,2.4.4排
11、序的基本概念,排序是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。 例如将学生记录按学号排序，将课程记录按课程编码排序。 排序的形式化定义为：假设含n个记录的序列为 R1, R2,，Rn ，其相应的关键字序列为 K1, K2,，Kn 。这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1Kp2Kpn，按此固有关系将最初的记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。,25,排序分为内部排序和外部排序。 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类
12、排序问题为外部排序。 本节只讨论内部排序的若干方法,26,内部排序方法有很多类型。 按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等； 按方法效率可分为简单的排序法、先进的排序法等等。简单的排序法包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为O(n2)。而先进的排序法包括快速排序、归并排序等，它们的时间复杂度大约为O(nlog2n)。,27,显示在序列35，22，16，19，22上应用插入排序的过程，为了对序列中相同记录加以区别，使用了下划线。,28,初始状态： 35 22 16 19 22 第1趟 ： 22 35 16 19 22 第2趟 ： 16 22 35 19 2
13、2 第3趟 ： 16 19 22 35 22 第4趟 ： 16 19 22 22 35 直接插入排序执行过程,1、直接插入排序,直接插入排序算法C+语言描述： void InsertSort( int v , int n ) int i, j, temp; for( i=1; i0 /插入元素 ,29,在序列35，22，16，19，22上应用简单选择排序的过程。 初始状态： 35 22 16 19 22 第1趟 ： 16 22 35 19 22 第2趟 ： 16 19 35 22 22 第3趟 ： 16 19 22 35 22 第4趟 ： 16 19 22 22 35,30,2、简单选择排序,
14、简单选择排序算法C+语言描述： void SelectSort( int v , int n ) int i,j,k,temp; for( i=0; in-1; i+ ) int k = i; /k存放最小记录位置 for( j=i+1; jn; j+) /找最小记录位置 if( vjvk ) k = j; if( k!=i ) /交换第i和第k个位置记录 temp=vi; vi=vk; vk=temp; ,31,下图显示了在序列35，22，16，19，22上应用冒泡排序的过程。 初始状态：35 22 16 19 22 第1趟 ： 22 16 19 22 35 第2趟 ： 16 19 22 2
15、2 35 第3趟 ： 16 19 22 22 35 第4趟 ： 16 19 22 22 35,32,3、冒泡排序,冒泡排序算法C+语言描述： void BubleSort(int v , int n) int temp; for (int i=1; ivj+1 ) /交换两个相邻元素 temp=v j ; vj=vj+1; vj+1=temp; /第i大的元素筛选结束 ,33,34,在22, 35, 27, 16, 45, 19, 22上应用划分算法 （即一趟快速排序）,4、快速排序,下列算法对vlow与vhigh之间的元素进行划分，利用了序列第一个记录作为基准，最终将low与high区间中的序列划分为左右两个子序列，将基准对象放到适当位置并返回其位置的下标。,35,int Partition( int low, int high ) int pivot = vlow; /基准对象pivot位置为low while(lowpivot
