计算机软件基础第4章查找和排序.ppt

1、第4章 查 找 和 排 序,4.1 线性表查找 4.1.1 顺序查找 4.1.2 折半查找 4.2 二叉排序树的查找 4.3 排序 4.3.1 直接插入排序 4.3.2 简单选择排序 4.3.3 冒泡排序,4.1 线性表查找,查找(Searching)，也称检索，亦即查表，就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作，如查寻电话号码、查字典、查图书目录卡片等。为确切定义查找，先引入几个概念。 查找表：由同一类型的数据元素(或记录)构成的集合。,关键字(key)：数据元素中可以惟一标识一个数据元素的数据项。例如在学校中，将每一个学生的数据信息作为一个记录，其中包

2、括学号、姓名、性别、民族等。若要唯一地标识一个学生的记录，则必须用“学号”作为关键字；若用“姓名”，可能有重名而失去唯一性。查找就是根据给定的关键字的值，在一组数据中确定一个其关键字等于给定值的数据元素的过程。若存在这样的数据元素，则称查找是成功的，否则称查找不成功。 决定查找操作的是关键字，因此这里讨论时，只关注记录中的关键字域，而一概忽略记录中其它诸域的信息。,表2-1 学生学籍登记表,4.1.1 顺序查找 顺序查找是最简单、常用的查找技术。其基本思想是：从表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到

3、所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值(常用1表示)。,顺序查找方法既适用于以顺序存储结构组织的查找表的查找，也适用于以链式存储结构组织的查找表的查找。在本章的有关查找和排序算法中，假设线性表均采用顺序存储结构，其类型说明为：,#define MAXLEN n /* n为查找表中元素个数的最大可能值*/ struct element int key; /*设关键字的类型为整型*/ int otherterm; /*为说明起见，除关键字外只有一个整型数据项*/ ; typedef struct element DATATYPE; DATATYPE tableM

4、AXLEN;,算法4-1 顺序查找算法。 int seqsearch1(DATATYPE A, int k) /*返回关键字等于k的元素在表中的位置*/ int i; i=0; while(Ai.key!=k) if(Ai.key=k),return i; /*查找成功，返回被查元素在表中的相对位置*/ else return 1; /*查找失败，返回1*/ 若对此算法进行一些改进，在表尾增加一个关键字为指定值K的记录，可避免每“比较”一次，就要判别查找是否结束。当n很大时，大约可节省一半的时间。,算法4-2 改进的顺序查找算法。 #define MAXLEN n+1 int seqsearc

5、h2(DATATYPE A, int k) int i; i=0; AMAXLEN1.key=k;,while (Ai.key!=k) i+; if(iMAXLEN1) return i; /*查找成功，返回被查元素在表中的相对位置*/ else return 1; /*查找失败，返回1*/ ,将AMAXLEN1称作监视哨，这个增加的记录起到了边界标识的作用。 下面对改进后的算法进行一下性能分析，计算它的平均查找长度。 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。,对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=Pi

6、Ci (i=1,2,3,n)可以简单以数学上的期望来这么理解。 其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。,从顺序查找的过程看，Ci取决于所查元素在表中的位置，对于第一个记录只要比较一次，对第n个记录，需要比较n次，查找记录Ai-1时，比较i次。设每个记录的查找概率相等，则Pi=1/n 。故此算法在等概率情况下查找成功的平均查找长度为,ASL =,4.1.2 折半查找(二分查找) 如果查找表中的记录按关键字有序，则可以采用一种高效率的查找方法折半查找，也称二分查找。 折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行

7、比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到找到或者查找范围为空而查不到为止。设有序表中的关键字按升序排列,整型变量low和high分别表示待查找范围的下界和上界,中间位置mid=(low+high)DIV 2。,将给定值k和mid所指的记录关键字值Amid.key比 较，有三种可能的结果： (1)若kAmid.key,由于各记录的关键字值是从小到大排 列的，因此要找的记录如果存在的话，必定在左半部 分。于是，查找范围缩小了一半。修改范围的上界 high= mid-1，在左半部分继续使用折半查找； (2)若k=Amid.k

8、ey,则查找成功，返回该记录下标mid，结束 查找；,(3)若kAmid.key,类似kAmid.key的情形，要找的记录如果 存在，必定在右半部分。于是，查找的范围缩小了一半。修 改范围的下界low= mid+1，再对右半部分进行折半查找。 经过一次关键字比较，查找范围就缩小一半。重复上述过 程，查找范围不断缩小，当最后只剩下一个记录，而且此记 录不是要找的记录，则说明查找不成功。,例4-1 一有序表的关键字序列为(5，12，18，20，35，50，64，72，80，88，95)，表长为11，假设要查找k=20对序列中11个元素的折半查找过程如下： (1) low=0，high=10，mid

9、=(0+10)/2=5，将k与 Amid.key 进行比较，因为k18,说明待查元素若存在，必在区间mid+1,high范围内，则令low=mid+1 (3) low=mid+1=3，high=4，重新求得mid=(3+4)/2=3，由于 k=20， Amid.key =20，查找成功，所找到的记录下标为3,按照折半查找算法，对序列中11个元素的查找过程如 下： (1) mid =(0+10)/2=5，查到第6个元素50，比较1次； (2) mid =(0+4) /2=2 /*若查找的元素小于50*/ 查到第3个元素18，比较2次；,或 mid =(6+10) /2=8 /*若查找的元素大于5

10、0*/ 查到第9个元素80，比较2次； (3) 依次类推，查到第1、4、7和第10个元素需比较3次；查到第2、5、8和第11个元素需比较4次。,这个查找过程可用图4-1(a)的二叉树表示。若树中每个结点表示一个记录，结点中的值为该记录在表中的位置：即第几个元素，通常这个描述查找过程的二叉树为判定树，如图4-1(b)所示。从判定树上看，查找20的过程恰好是走了一条从根到结点4的路径，比较次数为该路径上的结点数，或结点4在判定树上的层次数。因此，折半查找在查找成功时进行比较的次数最多不超过树的深度。,图4-1 描述折半查找过程的二叉树及判定树 (a) 描述折半查找的二叉树；(b) 描述折半查找的判

11、定树,从判定树上可知 ASLsucc= (1+2+2+3+3+3+3+4+4+4+4) = 3,算法4-3 折半查找算法。 #define MAXLEN n int binsearch(DATATYPE A, int k) int low,mid,high; low=0; high=MAXLEN1; while (low=high) mid=(low+high)/2;,if (k=Amid.key) return mid; /*查找成功，返回被查元素在表中的相对位置*/ else if(kAmid.key) low=mid+1; else high=mid1; return 1;/*查找失败，

12、返回1*/ ,4.2 二叉排序树的查找,前一节我们介绍了两种基本的查找方法：顺序查找、折半查找等。其中折半查找的效率最高，但折半查找要求查找表中的数据元素按关键字有序，且不能用链表作存储结构。当对查找表中的数据元素进行插入和删除操作时，为了保持查找表的有序性，势必要移动很多记录，造成新的时间开销。当插入和删除频繁进行时，这种额外开销就会抵消折半查找的优点。,若我们对查找表只作查找运算，则称该表为静态查找表。 若对查找表既允许进行查找运算，又允许进行插入和删除运算， 则称该表为动态查找表。 静态查找表一旦生成之后，所含记录在查找过程中一般是 固定不变的。而动态查找表则不然，对表中记录经常进行插入

13、和 删除操作，所以动态表是一直在变化的。动态查找表的这种特性 要求采用灵活的存储方法来组织查找表中的记录，以便高效率地 实现动态查找表的查找、插入、删除等操作。二叉排序树又称为 二叉查找树，就是一种能方便地实现动态查找表的查找、插入等 操作的理想数据结构。,1二叉排序树的查找 二叉排序树(binary sort tree)或者是一棵空树；或者是具有下列性质的二叉树。 (1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； (2) 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； (3) 它的左、右子树也分别为二叉排序树。 图4-3所示为两棵二叉排序树。,由其

14、定义可得出二叉排序树的一个重要性质：按中序遍 历该树所得到的中序序列是一个递增有序序列。例如， 图4-3所示的两棵树均是二叉排序树，若中序遍历图4-3(a) 所示的二叉排序树，可得有序序列：9，30，36，47， 50，65，72，78，90。 因此，用二叉排序树组织数据既 可以维持数据的有序性，便于查询，又可以方便地进行 查找删除。,图4-3 二叉排序树示例,二叉排序树查找的思想是： (1) 当二叉排序树不空时，首先将给定值K与根结点的关键字进行比较，若相等则查找成功； (2) 若给定值K小于根结点的值，则继续在根的左子树中查找；若给定值K大于根结点的值，则继续在根的右子树中查找。 也就是说

15、，每次只需查找左子树或右子树中的一枝即可，效果明显提高。其查找算法见算法4-5。,算法4-5 二叉排序树的查找。 struct treenode int key; int otherterm; struct treenode *lchild,*rchild; ; typedef struct treenode TREENODE; TREENODE *bstsearch(TREENODE *root,int k) TREENODE *p; p=root;,while(p!=NULL) if(p-key=k) return p;/*查找成功，返回非空指针*/ else if(p-keyk) p=p

16、-lchild; /*在左子树中查找*/ else p=p-rchild; /*在右子树中查找*/ return p;/*查找失败，返回空指针*/ ,2二叉排序树的生成（插入） 对一组数据序列K1，K2，Kn，先设一棵空二叉树，然后依次将序列中的元素生成结点后逐个插入到已生成的二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。,设有一组关键字序列为(48，24，53，20，35，90)，这一组数据按二叉排序树组织时，其二叉排序树的构造过程如图4-4所示。 从图4-4中可看出，二叉排序树的生成过程就是在二叉排序树上插入结点的过程。 设有n个数据元素序列存放在一维数组An中，二叉排序树采用二

17、叉链表存储结构，根结点指针为head，生成二叉排序树的算法如算法4-6所示。,图4-4 二叉排序树的构造过程,算法4-6 二叉排序树的生成算法。 #define N n/*n为二叉排序树中结点个数的最大可能值*/ struct tnode int data; struct tnode *lchild, *rchild; ; typedef struct tnode TNODE; int An; TNODE *create_binary_sort_tree() / 将新结点*s插入到head所指的二叉排序树中，函数返回插入*s后二叉排序树的根指针head, int i; TNODE *head,

18、*s,*p,*q; head=NULL; for(i=0;idata=Ai; s-lchild=NULL; s-rchild=NULL; if(head=NULL),head=s; else p=head; while(p!=NULL) q=p; if(s-datadata) p=p-lchild; / 在左子树中查找插入位置 else p=p-rchild; / 在右子树中查找插入位置 ,if(s-datadata) q-lchild=s; / 将* s插入为 * q 的左孩子 else q-rchild=s; / 将* s插入为 * q的右孩子 return head; ,3二叉排序树的查

19、找分析 例4-3 对图4-4(g)所示的二叉排序树进行查找，如要查找的关键字K=35，则K先与根结点比较，因3548，查找左子树；因3524，故在根的左子树的右子树上查找；因以结点24为根的右子树的根正好为35，故查找成功。,图4-4 二叉排序树的构造过程,由上例可以看出，在二叉排序树中查找成功时走了 一条从根结点到所查结点的路径，这与折半查找类似， 与给定值比较的关键字个数不超过树的深度。 然而，折半查找长度为n的表的判定树是惟一的， 而含有n个结点的二叉排序树却不唯一。二叉排序树查找 成功的平均查找长度取决于二叉排序树的形状，而二叉 排序树的形状既与结点数目有关，更取决于建立二叉排 序树时

20、结点的插入顺序。对于含有同样一组结点的表， 由于结点插入的先后次序不同，所构成的二叉排序树的 形态和深度也不同。,例4-4 已知长度为6的线性表是(45，24，53，13，30，85)，若按表中元素的顺序依次插入，得到二叉排序树如图4-5(a)所示；若依次序13,24,30,45，53，85插入，得到二叉排序树为图4-5(b)所示，试分别求出在等概率情况下二叉排序树查找成功的平均查找长度。 解：因是6个记录等概率查找，所以Pi = 。 则(a)树的平均查找长度为 ASL(a)= 1+2+2+3+3+3= 则(b)树的平均查找长度为 ASL(b)= 1+2+3+4+5+6=,这两棵二叉树的深度分

21、别是3和6，二叉排序树查找的平均比较次数取决于二叉树的深度。在最好情况下，二叉排序树查找的平均比较次数与折半查找相同，其查找效率最高。而在最坏情况下，二叉排序树是通过把有序表的n个结点依次插入而生成的，所得到的二叉排序树蜕化为一棵深度为n的单支树，平均查找长度和单链表上的顺序查找相同。,图4-5 例4-4构造的二叉排序树 (a) 二叉排序树；(b)单支树,4.3 排 序,排序是计算机程序设计中的一种重要运算，也是日常生活中经常遇到的问题，如图书馆中图书的摆放和目录卡的建立就是按照某种次序进行的。排序的功能就是将一个数据元素的无序序列按指定的关键字重新排列成一个有序序列。经排序的数据若按由大到小

22、的顺序排列，称为下降序；反之，若按由小到大的顺序排列，称为上升序。本节介绍常用的排序算法如插入排序、选择排序、冒泡排序等。,基本概念： 排序又称为分类，是数据处理的一种重要操作。它的功 能就是将一个数据元素的无序序列按指定的关键字重新 排列成一个有序序列。关键字是数据元素中的某个数据 项或某些数据项的组合。用于排序的关键字也称为排序 关键字。为了处理方便，本节假设关键字由单个数据项 构成。,例如，下表为某班学生的成绩表，表中每个学生的情况包括学号、姓名、三门课的考试成绩以及这三门课的平均成绩。 如果希望按学号对学生考试成绩表进行排序，则学号就是排序关键字；如果希望按考试的平均成绩对该表进行排序

23、，则平均成绩就是其排序关键字。可见，数据元素序列的排序可以根据实际需要，选取其任一数据项作为排序关键字。,排序的分类：根据排序中所涉及的存储器，可将排序分为内部 排序和外部排序两大类。排序过程中，所有记录都放在内存中处理 的称为内部排序；当待排序的记录很多，排序时不仅要使用内存， 而且还要使用外部存储器的排序方法称为外部排序。本节只讨论内 部排序。 当待排序记录的关键字均不相同时，则排序的结果是唯一的，否 则排序的结果不一定唯一。如果待排序的文件中，存在有多个关键 字相同的记录，经过排序后这些具有相同关键字的记录之间的相对 次序保持不变，则称这种排序方法是稳定的；反之，若具有相同关 键字的记录

24、之间的相对次序发生变化，则称这种排序方法是不稳定 的。,为简单起见，采用顺序存储结构存放所排序的记录序列。其C语言描述如下：,#define N n struct record /*定义记录为结构类型 */ int key; /* 数据元素的关键字*/ int otheritem; /*数据元素中的其他成分，在以后的 讨论中忽略*/ ; typedef struct record RECORD; RECORD RN+1; /* R为记录类型的数组 */ 其中n为待排序的记录数目。,4.3.1 直接插入排序 插入排序的基本思想是把记录逐一按其关键字的大 小插入到已经排好次序的记录序列中的适当位置

25、，直到 全部插入完为止。 设有n个记录(R1，R2，Rn)，存放在数组Rn+1 中，已划分为已排序部分和未排序部分，即插入Ri时， (R1，R2，Ri1)是已排好序的部分，(Ri，Ri+1， Rn)属于未排序部分。用Ri依次与Ri1，Ri2，R1进行 比较，找出Ri在有序子文件中的插入位置，原位置上的记 录至Ri1均顺序后移一位，再将Ri插入 。,例4-6 设待排序记录的关键字序列为(20，15，8，23，55，25)，写出直接插入排序每一趟执行后的序列状态。 解：直接插入排序过程如图4-11所示。,图4-11 直接插入排序示例,初始时，令i=1，因为一个记录自然有序，故R1自成有 序区，无序

26、区则是R2到Rn，然后依次将R2， R3，插入到当前的有序区中，直到i=n时，将Rn 插入到有序区为止。 同时，从上例中可得，对有n个记录的序列进行直接插入 排序，需要重复以下步骤n-1次： （1）根据关键字的大小，查找插入位置； （2）原位置上的记录至Ri-1均顺序后移一位，再将记录Ri插入,算法4-7 直接插入排序算法。 void insertsort ( RECORD R , int n) 按递增进行插入排序 /*注意设待排记录放在R1到Rn中*/ int i,j; for(i=2;i=n; i+) /* 依次插入R2，Rn */ R0=R i; /*R0是监视哨，且是R i的副本 */

27、 j=i1; /*j总是指向有序序列的最后一个记录*/ while(R0.keyR j. key) /*查找R i的插入位置*/, Rj+1=R j; /*将关键字大于Ri.key的记录后移 */ /*后移一位，设结构体变量可以整体赋值*/ j; Rj+1=R0; /*插入R i元素到有序序列中*/ 算法中引进附加记录R0有两个作用：其一是进入查找循环之前，保存Ri 的副本， 以防记录后移而丢失Ri的内容；其二是在while循环中“监视”下标 变量j是否越界，一旦越界(即j1)，由R0控制while循环结束。因此，将R0 称为监视哨。采用这种技巧，可使测试循环条件的时间大约减少一半。 直接插入

28、排序是稳定的，其时间复杂度为O(n2)。,4.4.2 简单选择排序 简单选择排序的方法是在所有的记录中选出关键字最小的记录，把它与第一个记录交换存储位置，然后再在余下的记录中选出次小的关键字对应的记录，把它与第二个记录交换，依此类推，直至排序完成。 例4-7 待排序的记录关键字序列为(20，15，8，40，55，25)，写出简单选择排序每一趟执行后的序列状态。 解：简单选择排序过程如图4-12所示。,图4-12 简单选择排序示例,算法4-8 简单选择排序。 void selectsort(RECORD R,int n) /*注意待排记录放在R1到Rn中*/ int i,j,k; RECORD

29、temp; for (i=1;in; i+) /*做n-1趟选择排序*/ k=i; for(j=i+1;j=n; j+) /* 在当前无序区选择关键字最小的记录Rk */ if( Rj. keyRk. key),k=j; if(i!=k) temp=Rk; /*交换Ri和Rk ，设结构体变量可以整体赋值*/ Rk=Ri; Ri=temp; 简单选择排序是不稳定的，其时间复杂度是O(n2)。,4.3.3 冒泡排序 冒泡排序的基本思想为：若待排序记录为R1、 R2、 Rn，其对应关键字为K1、 K2、 Kn,则冒泡排序过程如下： （1）对于K1和K2 ，若逆序（ K1K2）则交换之，然后比较K2和K3 ， ，直至Kn-1和Kn，如此经过一趟排序，关键字最大的记录被安置在最后一个位置(Rn)上，进行了n1次比较。 （2）