《查找和排序算法的实现(实验七).docx》由会员分享，可在线阅读，更多相关《查找和排序算法的实现(实验七).docx（10页珍藏版）》请在三一文库上搜索。
1、实验七查找和排序算法的实现实验目的及要求(1) 学生在实验中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算法的 可能性和寻找、构造高效算法的方法。(2) 掌握运用查找和排序解决一些实际应用问题。二.实验内容：(1) 编程实现一种查找算法(如折半查找、二叉排序树的查找、哈希查找等)算相应的ASL。，并计(2)编程实现一种内部排序算法(如插入排序、快速排序等)。三.实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写，请另加附页)(1)编程实现一种查找算法(如折半查找、二叉排序树的查找、哈希查找等)算相应的ASL。，并计程序代码：折半查找：头文件：#defi ne EQ(a
2、,b) (a)=(b)#define LT(a,b) (a)v(b)#defi ne maxle ngth 20 typedef int ElemType;typedef structElemType key;ElemType other;card; 每条记录包含的数据项typedef structcard rmaxle ngth;int len gth;SSTable;/ 一张表中包含的记录容量void Create(SSTable & L); int Search(SSTable Lj nt elem);功能函数：#i nclude,f1.hn #i ncludestdio.hvoid C
3、reate(SSTable &L)20) n);printf(新的线性表已经创建，请确定元素个数(不超过 scanf(n%d,&L.length);prints请按递增序列输入具体的相应个数的整数元素(空格隔开)n) for(int i=O;iL.length;i+) (scanf(n%d,&L.ri.key);)int Search(SSTable L,int elem)iif(L.rL.length-1.keyelem)(printf(表中没有该元素(不在范围内)n);return 0;int low=0,high=L.length-1;int mid;while(low=high)(mi
4、d=(low+high)/2; if(EQ(L.rmid.key,elem)printf( elseif(LT(elem,L.rmid.key)该元素在第 %d 位 n,mid+1); return 0;(high=mid-1;) else( low=mid+1;) ) printf(表中没有该元素(不在范围内) return 0;)W)；主函数：#includestdio.h#includeM1.hn int main() typedef int Status;SSTable L;Create(L);prin tf(Hn);printf(此时的线性表元素：n)；for(i nt a=O;aL
5、 Jen gth;a+)(prin tf(H%d .ra.key);)prin tf(Hn);prin tf(Hn);int elem;do(printf(请输入要查找的元素(输入000表示结束程序八n“);sea nf(d“，&elem);if(elem!=000)(Seareh(L,elem);)while(elem!=000);return 0;)运行结果:(2)编程实现一种内部排序算法(如插入排序、快速排序等)。程序代码部分：直接插入排序头文件：#defi ne maxle ngth 20/最大数据容量#defi ne OK 1typedef int Other;typedef int
6、 KeyType;typedef structKeyType key;Other data;Red;typedef structRed rmaxle ngth+1; 加了个哨兵的位置intlen gth;当前数据个数 SqList;Status lnit(SqList &L);Status lnsertsort(SqList &L);功能函数：#includenstdio.hH#includeH1.hnStatus lnit(SqList &L) (printf(新的线性表以创建，请确定元素个数(不超过20)n);scanf(d”,&Length);printf(“请输入具体的相应个数的整数元
7、素(空格隔开)n“)；for(inti=1/* 将哨兵的位置0空出来 */;iL.length+1 ;i+)(scanf (d & L. ri. key);return OK;)Status lnsertsort(SqList &L) (for(int i=2;i0&L.r0.keyL.rj-1 .key/* 这里是依据记录中的数据项 key 来 排序的，所以比较的是key,而不是一条记录的所有数据项*/;卜)L.rU=L.rO-1；L.rD=L.rO:return OK;)主函数:#includeHstdio.hH #includeH1 .hnint main()(SqList L;Init
8、(L);printf(HnH);printf(排序前的线性表元素：n”)；for(int a=1 ;aL.length+1 ;a+)printf(%d H,L.ra.key);)printf(nnH);printf(,nn);Insertsort(L);printf(排序后的线性表元素:n”);for(int b=1 ;bL.length+1 ;b+)printf(%d H,L.rb.key);)printf(nnH);return 0;快速排序头文件：#define maxlength 20最大数据容量 #define OK 1 typedef int Other;typedef int K
9、eyType;typedef structKeyType key;Other data;Red;typedef structRed rmaxle ngth+1; /加了个哨兵的位置int len gth;当前数据个数 SqList;void lnit(SqList &L);Status Partition(SqList &L,int low,int high);void QSort(SqList &L,int lowjnt high);功能函数：#includeHstdio.hH#includeH1.hnvoid lnit(SqList &L)printf(新的线性表以创建，请确定元素个数(不
10、超过 20)n“);scanf(d”,&L.length);printf(”请输入具体的相应个数的整数元素(空格隔开)n“)；for(int i=1/*将存放枢轴中关键字所在记录完整信息的位置0空出来*/;iL.length+1 ;i+)scanf(%dn,&L.ri.key);Status Partition(SqList &L,int lowjnt high) (int pivotkey;pivotkey=L.rlow.key; 用第一条记录的关键字作枢轴LMOkL.Eowp/存放作为枢轴的关键字所在记录的完整信息while(lowhigh)while(low=pivotkey)high-
11、;/从右端往左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 lowjnt high) (int pivotloc;if(lowhigh)pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1 ,high); )主函数：#includenstdio.hn#includen1 .h int main
12、() (SqList L;Init(L);printf(MnH);printf(排序前的线性表元素：n);for(int a=1 ;aL.length+1 ;a+)printf(n%d n,L.ra.key);)printf(,nH);printf(,n,);printf(“请输入无序子列的开始和结束位置(有序子列不用管)int n“)；low,high;scanf(%d %dn,&low,&high);QSort(L,low,high);printf(排序后的线性表元素:n)；for(int b=1 ;bL.length+1 ;b+)printf(n%d n,L.rb.key);)print
13、f(nnn);return 0;运行结果:新的线性表以创建.请确定元素个数不超过胆）10请输入具休的相应个数的整数元素（空格隔开）1 -1 2 5 R 88 34 6 34 23排序前的线性表元素1 -1 2 5 0 88 -34 G 34 23请输入无序子列的开始和结束位置有序子列不用管）1 1S排序后的线性表元素34 -1 0 1 2 5 b 23 34 98Pvess any hey to cont inue_四.实验结果的分析与评价（该部分如不够填写，请另加附页）1 快速排序利用了递归的思想；2折半查找使用前提为：数列有序 注：实验成绩等级分为（90 -100分）优，（80 89分）良，（7079分）中，（60 69分）及格，（59分）不 及格。