查找排序的应用实验

1、淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 查找、排序的应用实验 班 级： 软件112 学 号： 2011122635 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日排序、查找的应用实验报告要求1目的与要求:1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；3）利用C或C+语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单形式列出实验排序和显示命令，并可进行交互操作）和实用性；4）本次

2、实验为实验成绩评定主要验收内容之一，希望同学们认真对待，并按时完成实验任务；5）本次实验为综合性实验，请于2012年12月23日按时提交实验报告（纸质报告每班10份）；6）下周开始数据结构课程设计，务必按时提交实验报告，任何同学不得拖延。2 实验内容或题目题目：对记录序列（查找表）：287，109，063，930，589，184，505，269,008，083分别实现如下操作：1) 分别使用直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序（可选）、链式基数排序算法对纪录序列进行排序，并显示排序结果；2) 对上述纪录列表排好序，然后对其进行折半查找或顺序查找；3 实验步骤与源程序 #inc

3、lude stdio.h#include stdlib.h#define LIST_SIZE 20#define TRUE 1#define FALSE 0typedef int KeyType;typedef structKeyType key;RecordType;typedef structRecordType rLIST_SIZE+1;int length;RecordList;void seqSearch(RecordList *l)KeyType k;int i;printf(请输出要查询的元素k:); fflush(stdin);scanf(%d,&k);i=l-length;w

4、hile (i=0&l-ri.key!=k) i-;printf(该元素的位置是);printf(%d,i+1);/cout该元素在图中第i个位置length;while(lowrmid.key)printf(该元素的位置为:);printf(%d,mid+1);/注意不能随便使用&printf(n);break;else if(qrmid.key) high=mid-1;elselow=mid+1;void inputkey(RecordList *l) int i;printf(请输入线性表长度:);/遇到错误：1.print用法scanf(%d,&(l-length);/&将变量的地址赋

5、值，而不是变量的值for(i=1;ilength ;i+)printf(请输入第%d个元素的值:,i); fflush(stdin);scanf(%d,&(l-ri.key);void InsSort(RecordList *l)for(int i=2;ilength;i+)l-r0.key=l-ri.key;int j=i-1;while(l-r0.keyrj.key) l-rj+1.key=l-rj.key;j=j-1;l-rj+1.key=l-r0.key;/直接插入排序void BubbleSort(RecordList *l) int x,i,n,change,j; n=l-leng

6、th;change=TRUE; for(i=1;i=n-1&change;+i) change=FALSE; for(j=1;jrj.keyl-rj+1.key) x=l-rj.key; l-rj.key=l-rj+1.key ; l-rj+1.key=x; change=TRUE; /冒泡排序法int QKPass(RecordList *l,int left,int right) int x; x=l-rleft.key ;int low=left;int high=right; while(lowhigh) while(lowrhigh.key=x) high-; if(lowrlow.

7、key=l-rhigh.key; low+; while(lowrlow.key=x) low+;if(lowrhigh.key=l-rlow.key;high-; l-rlow.key=x; return(low); void QKSort(RecordList *l,int low,int high) int pos; if(lowlength; for(i=1;i=n-1;+i) k=i; for(j=i+1;jrj.keyrk.key) k=j; if(k!=i) x=l-ri.key;l-ri.key=l-rk.key;l-rk.key=x; void output(RecordLi

8、st *l)for(int i=1;ilength;i+)printf(%d,l-ri.key);printf(n);void main()RecordList *l,*t,*m,*n; l=(RecordList *)malloc(sizeof(RecordList);int low;int high;int flag=1;int xuanze;while(flag!=0)printf(#n);printf(# 请选择你要进行的操作! #n);printf(# 1.直接插入排序; #n);printf(# 2.冒泡排序; #n);printf(# 3.快速排序; #n);printf(# 4

9、.简单选择排序; #n);printf(# 5.顺序查找; #n);printf(# 6.折半查找; #n);printf(# 7.退出! #n);printf(#n);scanf(%d,&xuanze);switch(xuanze)case 1:inputkey(l);InsSort(l);printf(直接插入排序结果是:n);output(l);break;case 2:inputkey(l);BubbleSort(l);printf(冒泡排序结果是:n);output(l);break;case 3:inputkey(l); low=1; high=l-length; QKSort(l,low,high);printf(快速排序结果是:n);output(l);break;case 4:inputkey(l); SelectSort(l); printf(简单选择排序结果是:n); output(l);break;case 5:inputkey(l); InsSort(l); printf(排序结果是:n); output(l);seqSearch(l);break;case 6:inputkey(l); InsSort(l); pr