版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- DB3301∕T 65.17-2024 反恐怖防范系统管理规范 第17部分:危险化学品
- 国庆假期安全教育主题班会教案
- 第六单元 单元复习课件-2024-2025学年七年级语文上册同步备课系列(统编版2024)
- 综合探究二 方向决定道路 道路决定命运课件-2024-2025学年高中政治统编版必修一
- 2022-2023学年高二物理竞赛课件:若干常用组合逻辑电路
- 高考地理一轮复习课件 洋流
- 2024年巴中客运从业资格证的考题
- 2024年黄山A1客运从业资格证
- 2024年许昌客车上岗证模拟考试
- 2024年巴彦淖尔客运从业资格模拟考试
- (正式版)SH∕T 3548-2024 石油化工涂料防腐蚀工程施工及验收规范
- 2024年南水北调中线干线工程建设管理局渠首分局应届高校毕业生招聘7人历年(高频重点提升专题训练)共500题附带答案详解
- 2024年云南新华书店图书限公司招聘工作人员历年(高频重点提升专题训练)共500题附带答案详解
- 四川省成都市2025届高中毕业班摸底测试英语试题(含答案)
- 2024版美团商家入驻合作标准协议书
- 餐馆学手艺的合同
- 螺旋锥齿轮传动计算几何尺寸
- 《装在套子里的人》剧本演绎推理+课件++2023-2024学年统编版高中语文必修下册
- 自考04729大学语文密训考前必看资料
- 电厂项目选址报告
- 华为交换机检测报告
评论
0/150
提交评论