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

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

2、EQ(a,b)(a)=(b)#defineLT(a,b)(a)<(b)#definemaxlength20typedefintElemType;typedefstructElemTypekey;ElemTypeother;card;/每条记录包含的数据项typedefstructcardrmaxlength;intlength;SSTable;/一张表中包含的记录容量voidCreate(SSTable&L);intSearch(SSTableL,intelem);功能函数：#include"1.h"#include"stdio.h"voi

3、dCreate(SSTable&L)(printf("新的线性表已经创建，请确定元素个数(不超过20)n");scanf("%d”,&L.length);printf("请按递增序列输入具体的相应个数的整数元素(空格隔开)n");for(inti=0;i<L.length;i+)(scanf("%d”,&L.ri.key);intSearch(SSTableL,intelem)(if(L.rL.length-1.key<elem|L.r0.key>elem)(printf("表中没有

4、该元素(不在范围内)n");return0;intlow=0,high=L.length-1;intmid;while(low<=high)(mid=(low+high)/2;if(EQ(L.rmid.key,elem)printf("该元素在第%d位n",mid+1);return0;elseif(LT(elem,L.rmid.key)high=mid-1;elselow=mid+1;printf("表中没有该元素(不在范围内)n");return0;主函数：#include"stdio.h"#include&quo

5、t;1.h"intmain()SSTableL;Create(L);printf("n");printf("此时的线性表元素：n");for(inta=0;a<L.length;a+)(printf("%d",L.ra.key);printf("n");printf("n");intelem;do(printf("请输入要查找的元素(输入000表示结束程序)n");scanf("%d”,&elem);if(elem!=000)(Search(

6、L,elem);while(elem!=000);return0;运行结果：(2)编程实现一种内部排序算法(如插入排序、快速排序等)。程序代码部分：直接插入排序头文件：#definemaxlength20/服大数据容量#defineOK1typedefintStatus;typedefintOther;typedefintKeyType;typedefstructKeyTypekey;Otherdata;Red;typedefstructRedrmaxlength+1;力口了个哨兵的位置intlength;/当前数据个数SqList;StatusInit(SqList&L);Statu

7、sInsertsort(SqList&L);功能函数：#include"stdio.h"#include"1.h"StatusInit(SqList&L)printf("新的线性表以创建，请确定元素个数(不超过20)n");scanf("%d",&L.length);printf("请输入具体的相应个数的整数元素(空格隔开)n");for(inti=1/*将哨兵的位置【0】空出来*/;i<L.length+1;i+)scanf("%d",&

8、;L.ri.key);returnOK;StatusInsertsort(SqList&L)for(inti=2;i<L.length+1;i+)L.r0=L.ri;/交换的应该是该位置记录的完整数据项，而不仅仅是数据项中的一个keyfor(intj=i;j>0&&L.r0.key<L.rj-1.key/*这里是依据记录中的数据项key来排序的，所以比较的是key,而不是一条记录的所有数据项*/;j-)L.rj=L.rj-1;L.rj=L.r0;returnOK;)主函数：#include"stdio.h"#include"

9、;1.h"intmain()(SqListL;Init(L);printf("n");printf("排序前的线性表元素：n");for(inta=1;a<L.length+1;a+)(printf("%d",L.ra.key);)printf("n");printf("n");Insertsort(L);printf("排序后的线性表元素：n");for(intb=1;b<L.length+1;b+)(printf("%d",L.r

10、b.key);)printf("n");return0;)快速排序头文件：#definemaxlength20/服大数据容量#defineOK1typedefintStatus;typedefintOther;typedefintKeyType;typedefstructKeyTypekey;Otherdata;Red;typedefstructRedrmaxlength+1;力口了个哨兵的位置intlength;/当前数据个数SqList;voidInit(SqList&L);StatusPartition(SqList&L,intlow,inthigh)

11、;voidQSort(SqList&L,intlow,inthigh);功能函数：#include"stdio.h"#include"1.h"voidInit(SqList&L)printf("新的线性表以创建，请确定元素个数(不超过20)n");scanf("%d",&L.length);printf("请输入具体的相应个数的整数元素(空格隔开)n");for(inti=1/*将存放枢轴中关键字所在记录完整信息的位置【0】空出来*/;i<L.length+1;i+

12、)scanf("%d",&L.ri.key);StatusPartition(SqList&L,intlow,inthigh)intpivotkey;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<=pi

13、votkey)low+;/从左端往右L.rhigh=L.rlow;)L.rlow=L.r0;returnlow;)voidQSort(SqList&L,intlow,inthigh)(intpivotloc;if(low<high)(pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);)主函数：#include"stdio.h"#include"1.h"intmain()(SqListL;Init(L);printf("n&

14、quot;);printf("排序前的线性表元素：n");for(inta=1;a<L.length+1;a+)(printf("%d",L.ra.key);)printf("n");printf("n");printf("请输入无序子列的开始和结束位置(有序子列不用管)n");intlow,high;scanf("%d%d",&low,&high);QSort(L,low,high);printf("排序后的线性表元素：n");for(intb=1;b<L.length+1;b+)(printf("%d",L.rb.key);)printf("n");return0;运行结果:断的线性表以创建，请确定元素个数（不超过2青输入具体的相应个数的整数元素（空格隔开）30-12t33126-24排序前的线性表元素.30-12633126-24排序后的线性表元素；-2-10234661233Pressanj/keytocontinue新的线性表以创建，请确定元素个数（不超过2m1Q请输入具体的相应个数的整数元素（空格隔开）1