计算机软件基础课件：查找与排序.pptx

;;本章重点难点;查找和排序是数据处理过程的主要操作;;1.查找的概念;;?;;1.设“监视哨”的顺序查找;2）算法流程与实现;3）平均查找长度;2.折半查找

;2）算法流程与实现;例10-1已知待查序列为：2，5，9，13，18，26，32。待查关键字K分别为13、32和4，试写出折半查找过程。;3)折半查找判定树;例10-2试构造具有9个结点的折半查找判定树，并求查找成功的平均查找长度ASL。;3.二叉查找树查找;2）二叉查找树上的查找

由于二叉查找树的特殊性质，查找可以比较方便地实现。其过程如下：

1）查找从树的根结点开始，如果树为空，返回NULL，表示未找到关键字为key的结点。

2）查找树非空，则根结点关键字和key进行比较，依据比较结果，需要进行不同的处理：

若根结点关键字小于key，则在此根结点的右子树中继续进行查找；

若根结点关键字大于key，则在此根结点的左子树中继续进行查找；

若两者比较结果是相等，查找完成，返回指向此结点的指针。

;3）构造二叉查找树的方法

已知一个关键字序列，构造二叉查找树的方法通常是通过逐个插入序列中的关键字来完成的。以下是一种常见的方法：

创建一个空的二叉查找树。

从序列中取出第一个关键字作为根结点，将其插入到二叉查找树中。

对于序列中的每个后续关键字，按照以下规则进行插入：

从根结点开始，递归地比较要插入关键字和当前结点关键字。

如果要插入关键字小于当前结点的关键字，则向其左子树移动；如果该大于当前结点的关键字，则向其右子树移动。

重复步骤③直到遇到一个空的子结点（即空指针），表示找到了插入位置，将要插入关键字作为新结点插入到这个空的子结点位置。

重复步骤③和④，直到遍历完整个序列，插入所有关键字为止。

;;4）二叉查找树上结点的平均查找长度

;;内部排序：是指待排序数据元素存放在计算机随机存储器中进行的排序过程。

外部排序：指待排序数据元素的数量较大，内存一次不能容纳全部数据元素，在排序过程中尚需对外存进行访问的排序过程;;根据排序方法进行一趟的基本操作不同，内部排序方法分为下面几大类：;基于“选择”思想的排序方法;1.直接插入排序;?;2.冒泡排序

基本思想是对所有相邻元素的关键字进行比较，如果是逆序，则将其交换，最终达到有序。冒泡排序方法简单，应用广泛。;?;3.直接选择排序;?;;例10-8青年歌手大赛，有10位评委进行打分，每位选手的最后得分为：去掉1个最高分和1个最低分后，8位评委的总分。要求编写一个通用程序，输入各选手的编号、各位评委的评分，输出各选手的编号、总分及名次。

采用模块化思想，可设置4个函数如下：

①sum1函数。计算各选手总分。

②sort1函数。应用冒泡排序方法，总分由高到低排序。

③print1函数。输出各选手的编号、总分和名次。

④main主函数。输入各选手的编号、各位评委的评分，分别调用以上3个函数。

定义标识符说明：

M：符号常量，设有10位评委。

N：符号常量，设有5位选手。

a[1..M]：10位评委的打分。

b[1..N]：5位选手最后得分。

c[1..N]：选手的编号。

;intsum1(intx[],intn) /*计算各位选手总分*/

{

inti,max,min,s; /*max和min分别记录最高分和最低分，s记录评分和*/

max=min=s=x[1]; /*设置初值*/

for(i=2;i=n;i++)

{

if(x[i]max)max=x[i]; /*求最高分*/

if(x[i]min)min=x[i]; /*求最低分*/

s=s+x[i]; /*评委总分*/

}

s=s-max-min; /*去掉1个最高分和1个最低分后选手的最后得分*/

returns;

}

;voidsort1(intx[],inty[],intn) /*选手总分由高到低排序*/

{

inti,j,m;

for(i=1;i=n-1;i++)

for(j=1;j=n-i;j++)

if(x[j]x[j+1])

{

m=x[j];x[j]=x[j+1];x[j+1]=m;/*总分交换*/

m=y[j];y[j]=y[j+1];y[j+1]=m;/*编号交换*/

}

}