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

1、一. 实验目的及要求（1）学生在实验中体会各种查找和内部排序算法的基木思想、适用场合，理解开发 高效算法的可能性和寻找、构造髙效算法的方法。（2）掌握运用查找和排序解决一些实际应用问题。二. 实验内容：（1）编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计 算相应的aslo（2）编程实现一种内部排序算法（如插入排序、快速排序等）。三. 实验主要流程、基木操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1） 编程实现一种杳找算法（如折半杳找、二叉排序树的查找、哈希查找等），并计 算相应的aslo> 程序代码：折半查找：头文件：#define eq(a,b)

2、(a)=(b)#define lt(a,b) (a)<(b)#define maxlength 20typedef int elemtype;typedef structelemtype key;elemtype other;card;/条记录包含的数据项typedef structcard rmaxlength;int length;jsstable;/ -张表中包含的记录容量 void create(sstable &l);int search(sstable ljnt elem);功能函数：#includem lhh #includehstdio.hhvoid create

3、(sstable &l)printf("新的线性表已经创建，请确定元素个数(不超过20) w); scanf(u%dm,&l.length);printf(-请按递增序列输入具体的相应个数的整数元索(空格隔开)n“)；for(int i=0;i<l.length;i+)scanf(" %dn ,&l.r i .key);int search(sstable l,int elem)if(l.rl.length-1 .key<elemlll.r0 .key>elem)printf(”表中没有该元索(不在范围内)n”)；return 0;

4、int low=0,high=l.length-1;int mid;while(lowv 二 high)mid=(low+high)/2;if(eq(l.rmidj.key,elem)printf(n该元素在第d 位n”,mid+l); return 0; else if(lt(elem,l.rmid.key)high=mid-l;elselow 二 mid+1;printf(”表中没有该元素(不在范围内)n”);return 0;主函数：#include"stdio.h"include11 l.hnsstable l;create(l);printf(” n”);prin

5、tf(”此时的线性表元素：n“)；for(int a=o;a<lcngth;a+)printf(”d h,l.ra.key);printf(”n”);printf(” n”);int elem;doprintf请输入耍查找的元素(输入000表示结束程序)n“); scanf("%d",&elem);if(elem!=000)search(l,eleni); while(elem!=000);return 0;> 运行结果：新的线性表已经创建，请确定元素个数（不超过20）10请按递増序列输入具体的相应个数的整数元素（空格隔开）-2 1 3 6 10 11

6、14 23 44 99此时的线性表兀素:-2 1 3 6 10 11 14 23 44 99请输入要查找的元素输入000表示结束程序11皈元素在第6位（2）编程实现一种内部排序算法（如插入排序、快速排序 等）。程序代码部分：直接插入排序头文件：#define maxlength 20最人数据容量#define ok 1typedef int other;typedef int keytype;typedef struct keytype key;other data;red;typedef struct red rfmaxlength+1;/加了个哨兵的位置 int length;/当询数据个

7、数jsqlist;status init(sqlist &l);status insertsort(sqlist &l);功能函数：#includenstdio.h"#include"l.h"status init(sqlist &l)prindt新的线性表以创建，请确定元素个数(不超过20) )； scanf("%d",&l.length);printfc1请输入具体的相应个数的整数元素(空格隔开)n”)； for(int i=l/*将哨兵的位置0空出来*/;ivl.length+l;i+)scanf(n%d&

8、quot;,&l.ri.key);return ok;status insertsort(sqlist &l)for(int i=2;i<l.length+l;i+)l.r0=l.ri;/交换的应该是该位置记录的完整数据项，而不仅仅是数据项 屮的一个keyfor(int j=i;j>0&&l.r0 .key<l.rj-1 .key/* 这里是依据记录中的数据项 key 来 排序的，所以比较的是key,而不是一条记录的所有数据项*/*)l.ru=l.ru-l;l.rj=l.r0;return ok;主函数：#includemstdio.h&quo

9、t;#includeul.hnint main()sqlist l;init(l);printf("nn);primf(“排序前的线性表元b： nn);for(int a=l ;a<l.length+l ;a+)printf(h%d n,l.ra.key); printf("nn); printf(,nh); insertsort(l);printf(”排序后的线性表元素:nn);for(int b= 1 ;b<length+1 ;b+)printf(m%d ”,l.rb.key); printfc，nn); return 0;快速排序头文件：#define m

10、axlength 20最大数据容量#define ok 1typedef int other;typedef int keytype;typedef struct keytype key;other data;red;typedef struct red rfmaxlength+1;/加了个哨兵的位置int length;/当询数据个数jsqlist;void init(sqlist &l);status partition(sqlist &l,int lowjnt high);void qsort(sqlist &ljnt lowjnt high);功能函数：#inc

11、lude"stdio.h"#includeul.hhvoid init(sqlist &l)printfc*新的线性表以创建，请确定元素个数(不超过20) )； scanf("%d",&l.length);printfc*请输入具体的相应个数的整数元索(空格隔开)nj;for(int i=l/*将存放枢轴中关键字所在记录完整信息的位置【0】空出来*/;i<l.length+l ;i+)scanf(n%dh,&l.rfi.key);status partition(sqlist &l,int low,int high)

12、int pivotkey;pivotkey=l.rlow .key;/用第一条记录的关键字作枢轴l.r0=l.rlow;/存放作为枢轴的关键字所在记录的完整信息 while(low<high)while(low<high&&l.rhigh .key>=pivotkey) high; 从右端往左 l.rlow=l.rhigh;while(low<high&&l.rlow.key<=pivotkey) low+;/ 从左端往右 l.rfhigh=l.rflow;l.rlow=l.r0; return low;void qsort(sql

13、ist &l,int high)int pivotloc;if(low<high)pivotloc=partition(l,low,high);qsort(ljow,pivotloc-1);qsort(l,pivotloc+1 .high);主函数：#includehstdio.h"#includenl.hmint main()sqlist l;init(l);printf(nnn);printfc*排序前的线性表元素:nn);for(int a= 1 ;a<l.length+1 ;a+)printf("%d ",l.ra.ke

14、y);printf("nn);printf("nh);printfc请输入无序子列的开始和结束位置(有序子列不用管)w); int low,high;scanf(n%d %d”,&k)w,&high);qsort(l,low,high);printfc排序后的线性表元素：)；for(int b= 1 ;b<l.length+1 ;b+)printf(h%d h,l.rb.key);printf("nn);return 0;> 运行结果:新的线性表以创建，请确定元素个数（不超过20）10惰输入具体的相应个数的整数元素（空格隔开）3 0 -1 2 6 33 12 6 -2 4排序前的线性表元素：3 0 -1 2 6 33 12 6 -2 4排序后的线性表元素：-2 -1 0 2 3 4 6 6 12 33press any key to contimie.10请输入具体的相应个数的整数元素（空格隔开）1 -1 2 5 0 88 -34 6 34 23排序前的线性表元素：1