查找和排序算法的实现 (实验七).doc

实验 七 查找和排序算法的实现 一 实验目的及要求（1） 学生在实验中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算法的可能性和寻找、构造高效算法的方法。（2） 掌握运用查找和排序解决一些实际应用问题。二.实验内容：（1） 编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。（2） 编程实现一种内部排序算法（如插入排序、快速排序等）。三.实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1） 编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计算相应的ASL。 程序代码：折半查找：头文件：#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define maxlength 20typedef int ElemType;typedef structElemType key;ElemType other;card;/每条记录包含的数据项typedef structcard rmaxlength; int length;SSTable;/一张表中包含的记录容量void Create(SSTable &L);int Search(SSTable L,int elem);功能函数：#include1.h#includestdio.hvoid Create(SSTable &L) printf(新的线性表已经创建，请确定元素个数（不超过20）n); scanf(%d,&L.length); printf(请按递增序列输入具体的相应个数的整数元素（空格隔开）n); for(int i=0;iL.length;i+) scanf(%d,&L.ri.key); int Search(SSTable L,int elem)if(L.rL.length-1.keyelem) printf(表中没有该元素（不在范围内）n); return 0;int low=0,high=L.length-1;int mid;while(low=high)mid=(low+high)/2;if(EQ(L.rmid.key,elem)printf(该元素在第%d位n,mid+1); return 0;else if(LT(elem,L.rmid.key) high=mid-1;else low=mid+1;printf(表中没有该元素（不在范围内）n);return 0;主函数：#includestdio.h#include1.hint main() SSTable L; Create(L); printf(n); printf(此时的线性表元素：n); for(int a=0;aL.length;a+) printf(%d ,L.ra.key); printf(n); printf(n); int elem; do printf(请输入要查找的元素(输入000表示结束程序)n); scanf(%d,&elem);if(elem!=000) Search(L,elem); while(elem!=000); return 0; 运行结果：（2）编程实现一种内部排序算法（如插入排序、快速排序等）。程序代码部分：直接插入排序头文件：#define maxlength 20/最大数据容量#define OK 1typedef int Status;typedef int Other;typedef int KeyType;typedef structKeyType key; Other data;Red;typedef structRed rmaxlength+1;/加了个哨兵的位置 int length;/当前数据个数SqList;Status Init(SqList &L);Status Insertsort(SqList &L);功能函数：#includestdio.h#include1.hStatus Init(SqList &L) printf(新的线性表以创建，请确定元素个数（不超过20）n); scanf(%d,&L.length); printf(请输入具体的相应个数的整数元素（空格隔开）n); for(int i=1/*将哨兵的位置【0】空出来*/;iL.length+1;i+) scanf(%d,&L.ri.key); return OK;Status Insertsort(SqList &L) for(int i=2;i0&L.r0.keyL.rj-1.key/*这里是依据记录中的数据项key来排序的，所以比较的是key，而不是一条记录的所有数据项*/;j-) L.rj=L.rj-1; L.rj=L.r0; return OK;主函数：#includestdio.h#include1.hint main() SqList L; Init(L); printf(n); printf(排序前的线性表元素：n); for(int a=1;aL.length+1;a+) printf(%d ,L.ra.key); printf(n); printf(n); Insertsort(L); printf(排序后的线性表元素：n); for(int b=1;bL.length+1;b+) printf(%d ,L.rb.key); printf(n); return 0;快速排序头文件：#define maxlength 20/最大数据容量#define OK 1typedef int Status;typedef int Other;typedef int KeyType;typedef structKeyType key; Other data;Red;typedef structRed rmaxlength+1;/加了个哨兵的位置 int length;/当前数据个数SqList;void Init(SqList &L);Status Partition(SqList &L,int low,int high);void QSort(SqList &L,int low,int high);功能函数：#includestdio.h#include1.hvoid Init(SqList &L) printf(新的线性表以创建，请确定元素个数（不超过20）n); scanf(%d,&L.length); printf(请输入具体的相应个数的整数元素（空格隔开）n); for(int i=1/*将存放枢轴中关键字所在记录完整信息的位置【0】空出来*/;iL.length+1;i+) scanf(%d,&L.ri.key); Status Partition(SqList &L,int low,int high) int pivotkey; pivotkey=L.rlow.key;/用第一条记录的关键字作枢轴 L.r0=L.rlow;/存放作为枢轴的关键字所在记录的完整信息 while(lowhigh) while(low=pivotkey)high-;/从右端往左 L.rlow=L.rhigh; while(lowhigh&L.rlow.key=pivotkey)low+;/从左端往右 L.rhigh=L.rlow; L.rlow=L.r0; return low;void QSort(SqList &L,int low,int high) int pivotloc; if(lowhigh) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); 主函数：#includestdio.h#include1.hint main() SqList L; Init(L); printf(n); printf(排序前的线性表元素：n); for(int a=1;aL.length+1;a+) printf(%d ,L.ra.key); printf(n); printf(n); printf(请输入无序子列的开始和结束位置（有序子列不用管）n); int low,high; scanf(%d %d,&low,&high); QSort(L,low,high); printf(排序后的线性表元素：n); for(int