内容发布更新时间 : 2024/11/14 15:36:58星期一 下面是文章的全部内容请认真阅读。
数据结构上机实验五
实验内容:查找表和内部排序的基本算法 实验要求:
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
#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;