淮海工学院计算机科学系
实验报告书
课程名： 《数据结构》
题 目： 查找、排序的应用实验
班 级： 学 号： 姓 名：
评语： 成绩： 指导教师： 批阅时间： 年 月 日
排序、查找的应用实验报告要求
1目的与要求:
1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。
2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；
3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单形式列出实验排序和显示命令，并可进行交互操作）和实用性；
4）本次实验为实验成绩评定主要验收内容之一，希望同学们认真对待，并按时完成实验任务；
5）本次实验为综合性实验，请于2012年12月23日按时提交实验报告（纸质报告每班10份）；
6）下周开始数据结构课程设计，务必按时提交实验报告，任何同学不得拖延。
2 实验内容或题目
题目：对记录序列（查找表）：{287，109，063，930，589，184，505，269,008，083}分别实现如下操作：
1) 分别使用直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序（可选）、链式基数排序
算法对纪录序列进行排序，并显示排序结果；
2) 对上述纪录列表排好序，然后对其进行折半查找或顺序查找；
（特别要求：使用菜单机制，在一个主程序下实现题目要求的排序和查找以及结果显示） 3 实验步骤与源程序
#include
typedef int KeyType; typedef int OtherType; typedef struct {
KeyType key[KEY_SIZE]; /* 子关键字数组 */ OtherType other_data; /* 其它数据项 */ int next; /* 静态链域 */ } RecordType1;
typedef struct {
RecordType1 r[LIST_SIZE+1];/* r[0]为头结点 */ int length; int keynum;
}SLinkList; /* 静态链表 */ typedef int PVector[RADIX]; typedef struct {
int next; KeyType key;
OtherType other_data; }RecordType;
void InsSort(RecordType r[], int length)
/* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/ {
int i,j;
for (i=2; i<=length; i++) {
r[0]=r[i]; /*将待插入记录存放到监视哨r[0]中*/ j=i-1;
while (r[0].key< r[j].key ) /* 寻找插入位置 */ {
r[j+1]= r[j]; j=j-1; }
r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/ }
} /* InsSort */ //顺序查找
void SeqSearch(RecordType r[],int length,KeyType k) {
int i;
r[0].key=k; i=length;
while(r[i].key!=k) i--;
printf(\该元素在数组中的位置是%d\}
//冒泡排序
void BubbleSort(RecordType r[], int length ) /*对记录数组r做冒泡排序，length为数组的长度*/ {
int n,i,j; int change; RecordType x; n=length;
change=TRUE;
for ( i=1 ; i<= n-1 && change ;++i ) {
change=FALSE;
for ( j=1 ; j<= n-i ; ++j)
if (r[j].key > r[j+1].key ) {
x= r[j];
r[j]= r[j+1]; r[j+1]= x; change=TRUE; } }
} /* BubbleSort */ // 快速排序
int QKPass(RecordType r[],int left,int right)
/*对记录数组r 中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/ {
RecordType x; int low,high;
x= r[left]; /* 选择基准记录*/ low=left; high=right;
while ( low while (low< high && r[high].key>=x.key ) /* high从右到左找小于x.key的记录 */ high--; if ( low r[low]= r[high]; low++; } /* 找到小于x.key的记录，则进行交换*/ while (low if ( low r[high]= r[low]; high--; } /* 找到大于x.key的记录，则交换*/ } r[low]=x; /*将基准记录保存到low=high的位置*/ return low; /*返回基准记录的位置*/ } /* QKPass */ void SelectSort(RecordType r[],int length) /*对记录数组r做简单选择排序，length为数组的长度*/ { int i,j,k,n; RecordType x; n=length; for(i=1;i<=n-1;++i) { k=i; for(j=i+1;j<=n;++j) if(r[j].key x=r[i]; r[i]=r[k]; r[k]=x; } } } void QKSort(RecordType r[],int low, int high ) /*对记录数组r[low..high]用快速排序算法进行排序*/ { int pos; if(low pos=QKPass(r, low, high); /*调用一趟快速排序，将枢轴元素为界划分两个子表*/ QKSort(r, low, pos-1); /*对左部子表快速排序*/ QKSort(r, pos+1, high); /*对右部子表快速排序*/ } } // 堆排序 void sift(RecordType r[], int k, int m) /* 假设ｒ[k..m]是以ｒ[k]为根的完全二叉树，且分别以ｒ[2k]和ｒ[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质 */ { RecordType t; int i,j; int x; int finished; t= r[k]; /* 暂存\根\记录r[k] */ x=r[k].key; i=k; j=2*i; finished=FALSE;
查找、排序应用实验
