验证实验-折半查找

数据结构协同上机实验

第三组

验证实验－折半查找

一、折半查找－实验目的

对给定的有序数组（假设长度为），查找数组中与给定值相等的元素。

nk

二、折半查找－实验过程

1、算法思想

将数列按有序化排列(升序)，查找过程中采用跳跃式方式查找，即先以有序

数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查

序列缩小为前半部分，否则为后半部分。通过一次比较，将查找区间缩小一

半。

2、变量

I：循环变量.

J：查找次数计数器

Key：需查找的值.

Low：刚开始为第一个值所对应的下标.

High：刚开始为最后一个值所对应的下标.

Mid：第一个与最后一个值所对应下标和的一半

Arr：一维数组,用来存放15个数据.

3、步骤

➢ 读取一组15个已升序排列的数据。

➢ 取出15个数最中间下标的数与关键字进行比较，进行查找

➢ 若关键字等于这个数的话，则查找成功

➢ 若关键字小于这个数的话，则范围缩小为表的前半部分

➢ 若关键字大于这个数的话，则范围缩小为表的后半部分

➢ 重复执行3）4）5）过程，直到low>high为止。

Page 1 of 8

数据结构协同上机实验

第三组

➢ 输出各次查询low,high,mid值，总查询次数，验证折半算法

4、折半查找－流程图

low=mid+1

YES

arr[mid]

NO

high=mid-1

程序结束

arr[mid]==key

NO

查询成功，并输出数

组下标

YES

BREAK 跳出循环

LOW<=HIGH

YES

mid=(low+high)/2

NO

没有找到，查询不成

功

读取一组15个以

升序排列的数据

5、折半查找－程序代码

/* 对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素。*/

#include

#include "stdafx.h"

#define N 15 //定义常量N 为数组长度

void find(int arr[],int key,int i) 土木工程简历 //折半查找函数

{

int low=0,high=N-1,mid,j=0; //j计数查找次数

while(low<=high)

{

mid=(low+high)/2; //取中间位

++j;

printf("n 第%2d次查找 low=%2d high=%2d mid=%2d

",j,low,high,mid); //显示每次查找低中高位，查找次数

Page 2 of 8

数据结构协同上机实验

第三组

if(arr[mid]==key) //查到数据，跳出循环

break;

if(arr[mid]查找的KEY大于中位值，查后半部

low=mid+1;

el

high=mid-1; //查找的KEY小于中位值，查前半部

}

if(low<=high) //查到数据

printf("nn经过总共%2d次查找，找到该数字，该数字位于数组第%d

位,nn",j,mid+1);//显示查到的数据的值，下标值，总查找次数

el

printf("nn没有找到!"); //显示没有找到

}

void main()

{

int arr[N],key,i;

printf("n折半查找验证程序，设定被查数据有位，设定为：n");

for(i=0;i输入15个排好序的数据

{

arr[i]=i+1;

printf("%d ",arr[i]);

}

printf("n请输入要查询的数字（－，输入小于等于零的数字退出验证程

序）:");

scanf("%d",&key); //输入KEY

while(key>0)

{

find(arr,key,N); //调用折半查找函数

printf("n请输入要查询的数字（－，输入小于等于零的数字退出验证程

序）:");

scanf("%d",&key); //输入KEY

}

}

6、折半查找－运行结果

输入一个数值为1至15的有序一维数据，查询2，7，8的结果的截屏。

Page 3 of 8

数据结构协同上机实验

第三组

7、折半查找－时间性能

折半算法的时间复杂度O（N）≤log2n，即每经过一次比较,查找范围就缩小一

半。经log2n 次计较可以完成查找过程。

四、折半查找－小结

折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率，

而且程序实现也较为简单。但是，折半查找的先决条件是查找表中的数据元素必须

有序，而对所有数据元素按大小排序是非常费时的操作，因而，还需撑握更高效的

排序与查询方法。

Page 4 of 8

数据结构协同上机实验

第三组

协同作业试验四－直方图

2008年11月

一、实验要求－直方图

1. 关键码的数据类型是整型，且用数组存储；

2. 求出每个关键码在数组中出现的次数；

3. 输出直方图。

二、实验流程－直方图

初始化

输入数据

是否为1~5

整数

是否满足个数

统计出现次数

输出结果

三、算法思想－直方图

1. 建立一个与全国城市房价 关键码个数相同的数组，数组元素为一个结构体，包含关键码及

频率累加计数器。利用数组下标与关键码的对应关系（本例中，数组下标对

应关键码减1），把输入的需统计关键码对应到相应的数组元素，并对该元素

中的频率累加器进行计数，统计其出现频率。

Page 5 of 8

数据结构协同上机实验

第三组

2. 使用冒泡排序法，对数组以频率数为序进行降序排列，输出整个数组内容，

使用此算法能非常简洁的表示直方图。

四、算法说明－直方图

说明：使用结构体，是为了确保排序时关键码与频率之间的对应关系，可以以

少量空量换取较简洁的程序设计与时间性能。

五、算法设计概要－直方图

➢ data 自定义结构，用于存放关键码及关键码出现的次数

➢ mber 关键码

➢ mes 关键码出现的次数

➢ number 直方图结构数组

➢ t 临时结构体,用于排序交换的临时变量

➢ i 循环变量

➢ j 循环变量

➢ key 关键码，对应直方图结构数组下标

六、步骤

1) 初始化直方图结构，定义每个关键码，初始化关键码频率累加计数器为0

2) 循环接受关键码，并且根据输入的关键码找到相对应的元素， 对关键码频

率累加计数器累加计数

3) 对直方图中进行排序,排序规则根据关键码出现的频率降序

4) 输出直方图

七、时间性能－直方图

本程序中，使用了冒泡算法对数组进行了排序，这也是本程序中最大的时间复

杂度，所以本程序与冒泡排序算法的时间复杂度一致为O(n^2 )。

Page 6 of 8

数据结构协同上机实验

第三组

八、运行结果－直方图

九、直方图――程序代码

// 直方图

#include "stdafx.h"

#include "stdio.h"

#define N 10 //输入次数10次

#define R 5 //统计数字1-5

struct data

{

int datanumber; //存放预定数据(1-5) 如果仅用数组，无法解决排序后，被统计数与频率

的对应关系

int dat如何煮螃蟹 让爱传递 atimes; //存放出现次数

};

void main()

{

struct data number[R],t;

int key=0,j,i;

for(i情人节送女友什么礼物 =0;i初始化

{

number[i].datanumber=i+1;

number[i].datatimes=0;

}

printf("请输入数据，测试数据范围控制在1-5之间：n");

i = 0;

Page 7 of 8

数据结构协同上机实验

第三组

while(i

scanf("%d",&key);

//如果输入有误，则继续循环，直到输入正确后，累加计数器，进行下个数据的输

入

if(key<1 || key>5)

{

printf("输入数据有误，请重新输入n");

continue;

}

number[key-1].datatimes++;

i++;

}

for(i=0;i冒泡排序法对数组进行排序

{

for(j=R-1;j>i;j--)

{

if(number[j-1].datatimes

{

t=number[j-1];number[j-1]=number[j];number[j]=t;

}

}

}

printf("nn 关键码 频率n");

for(int i=0;i

printf("%8d %8dn",num宝宝笑声 ber[i].datanumber,number[i].datatimes);

}

十、小结－直方图

本实验，我们小组采用了一维结构数组，超声加工 比较好的解决了关键码与频率在排序后，

无法对应的问题。如果采用一维数组，关键码由数组下标承担，数组元素表示频

率，这样，排完序后，关键码与频率完全对不上号，频率高的永远是1，所以无

法采用；如果采用二维数组，空间与时间复杂度都会增加，解决方法也会更复杂

些。一维结构数组较好地解决了该问题，在牺牲极有限空间的情况下，换取了简

洁的程序设计与比较好的时间性能。

附：《数据结构》协同作业第三组组员表（略）

Page 8 of 8