数据结构(B)上机实验五__查找和排序 下载本文

内容发布更新时间 : 2024/6/16 20:10:11星期一 下面是文章的全部内容请认真阅读。

数据结构上机实验五

实验内容:查找表和内部排序的基本算法 实验要求:

1) 基本操作要作为函数被调用,做到模块化. 2) 基本上实现每个实验题目的要求. 分组要求:可单独完成,也可两人一组。 实验目的:

1)熟悉C/C++基本编程,培养动手能力. 2)通过实验,加深对查找算法的理解. 评分标准:

1) 只完成第一和第二题,根据情况得4,5-分; 2)完成前3题,根据情况得5,6分;

3)在2)基础上,选做四)中题目,根据情况得6,7分。 题目:

一)顺序表与有序表的查找

(1)建立一个顺序表,利用教材9.1.1的顺序查找算法进行查找; (2)建立一个有序表,利用折半法进行查找; (3)试将把(2)中的折半法改用递归算法实现;

二)二叉排序树的一些基本操作

(1)利用二叉链表的存储形式,从键盘输入建立一棵二叉排序树; (2)对(1)中建立的二叉排序树进行中序遍历并打印; (3)编写算法,判断一棵二叉树是否为二叉排序树。

(4)在(1)建立的二叉排序树中,查找一个树中不存在的关键字后并插入,之后打印该树; 三)排序

(1)插入排序——已知序列{17,18,60,40,7,32,73,65,85} 建立一个顺序表,采用插入排序算法的实现升序排序,打印排序结果;

(2)交换排序——已知序列{503,87,512,61,908,170,897,275,652,462} (1)建立一个顺序表,采用冒泡排序法实现升序排序,并打印每趟排序结果;

(2)建立一个顺序表,采用快速排序法实现升序排序,并打印每趟排序结果,与(1)做比较;

(3)选择排序——已知序列{42,13,24,91,23,16,05,88} 利用简单选择排序,实现上述序列的降序排序; 四)选作题

(1)试构造一个算法,从键盘输入一组关键字,按哈希函数H(key) = key MOD 13和链地址法处理冲突构来造哈希表,能对关键字进行查找并显示。 如(19,14,23,1,68,20,84,27,55,11,10,79,33).

(2)已知序列{503,87,512,61,908,170,897,275,652,462},采用基数排序法对其作升序排序,打印每一趟的结果。

(3)归并排序——已知序列{10,18,4,3,6,12,1,9,15,8},采用归并排序法对其作升序排序,打印每一趟的结果。

(4)堆排序——已知序列{42,13,24,91,23,16,05,88}

按照从小到大,建立“大”顶堆,并打印完全二叉树及其存储结果的变化情况;

一)顺序表与有序表的查找

(1)建立一个顺序表,利用教材9.1.1的顺序查找算法进行查找; (2)建立一个有序表,利用折半法进行查找; (3)试将把(2)中的折半法改用递归算法实现; #include #include #include

#define OK 1 #define ERROR 0

int r[10];

#define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b))

typedef int KeyType; typedef int Status; typedef struct {

KeyType key; }ElemType; typedef struct {

ElemType *elem; int length; }SSTable;

/* 构造一个含n个数据元素的静态顺序查找表ST(数据来自全局数组r) */ Status Creat_Seq(SSTable &ST,int n) {

int i;

ST.elem=(ElemType *)calloc(n+1,sizeof(ElemType)); if(!ST.elem)

return ERROR; for(i=1;i<=n;i++)

ST.elem[i].key=r[i-1];

ST.length=n; return OK; }

/* 重建静态查找表为按关键字非降序排序 */ void Ascend(SSTable &ST) {

int i,j,k;

for(i=1;i

k=i;

ST.elem[0]=ST.elem[i];

for(j=i+1;j<=ST.length;j++)

if LT(ST.elem[j].key,ST.elem[0].key) {

k=j;

ST.elem[0]=ST.elem[j]; } if(k!=i) {

ST.elem[k]=ST.elem[i]; ST.elem[i]=ST.elem[0]; } } }

/* 构造一个含n个数据元素的静态按关键字非降序查找表ST */ Status Creat_Ord(SSTable &ST,int n) {

Status f;

f=Creat_Seq(ST,n); if(f)

Ascend(ST); return f; }

/* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到,则函数值为该元素在表中的位置,否则为0 */

int Search_Seq(SSTable ST,KeyType key) {

int i;

ST.elem[0].key=key;

for(i=ST.length;!EQ(ST.elem[i].key,key);--i); return i; }

/* 在有序表ST中折半查找其关键字等于key的数据元素。若找到,则函数值为该元素在表中的位置,否则为0。算法9.2 */

int Search_Bin(SSTable ST,KeyType key) {

int low,high,mid;