版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
查找和排序1.需求分析1.编写一个程序输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序方法查找关键字5的过程;2.编写一个程序输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用顺序方法查找关键字9的过程;3.编写一个程序实现直接插入排序算法,并输出{9,8,7,6,5,4,3,2,1,0}的排序过程;4.编写一个程序实现快速排序算法,并输出{6,8,7,9,0,1,3,2,4,5}的排序过程2.系统设计1. 静态查找表的抽象数据类型定义:ADTStaticSearchTable{数据对象D:D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同,可惟一标识数据元素的关键字数据关系R:数据元素同属一个集合基本操作P:Create(&ST,n)操作结果:构造一个含n个数据元素的静态查找表STDestroy(&ST)初始条件:静态查找表ST存在操作结果:销毁表STSearch(ST,key)初始条件:静态查找表ST存在,key为和关键字类型相同的给定值操作结果:若ST中存在其关键字等于key的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”Traverse(ST,Visit())初始条件:静态查找表ST存在,Visit是对元素操作的应用函数操作结果:按某种次序对ST的每个元素调用函数Visit()一次且仅一次。一旦Visit()失败,则操作失败}ADTStaticSearchTable3.调试分析(1)要在适当的位置调用Print函数,以正确显示排序过程中顺序表的变化(2)算法的时间复杂度分析:顺序查找:T(n)=O(n)折半查找:T(n)=O(logn)直接插入排序:T(n)=O(n2)快速排序:T(n)=O(nlogn)4.测试结果用需求分析中的测试数据顺序查找:顺序表3,6,2,10,1,8,5,7,4,9,查找5折半查找:顺序表1,2,3,4,5,6,7,8,9,10,查找9直接插入排序:顺序表9,8,7,6,5,4,3,2,1,0,从小到大排序快速排序:顺序表6,8,7,9,0,1,3,2,4,5,从小到大排序5.用户手册(1)输入表长;(2)依次输入建立顺序表;(3)查找:输入要查找的关键字(4)回车输出,查找为下标的移动过程;排序为顺序表的变化过程6.附录源程序:(1)顺序查找#include<stdio.h>#include<stdlib.h>#defineST_INIT_SIZE200#defineEQ(a,b)((a)==(b))#defineOVERFLOW-2typedefintKeyType;typedefstruct{KeyTypekey;}ElemType;typedefstruct{ElemType*elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空intlength;//表长度}SSTable;voidInitST(SSTable&ST){ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));if(!ST.elem)exit(OVERFLOW);ST.length=0;}voidCreateST(SSTable&ST){inti;printf("输入表长:");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++)scanf("%d",&ST.elem[i].key);}voidPrintST(SSTableST){inti;for(i=1;i<=ST.length;i++)printf("%2d",ST.elem[i].key);printf("\n");}intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素//若找到则函数值为该元素在表中的位置,否则为0inti;ST.elem[0].key=key;printf("下标:");for(i=ST.length;!EQ(ST.elem[i].key,key);--i)printf("%d→",i);//从后往前找returni;}voidmain(){SSTableST;KeyTypekey;InitST(ST);CreateST(ST);printf("顺序查找表:");PrintST(ST);printf("输入要查找的关键字:");scanf("%d",&key);intfound=Search_Seq(ST,key);if(found)printf("找到,为第%d个数据\n",found);elseprintf("没有找到!\n");}(2)折半查找#include<stdio.h>#include<stdlib.h>#defineST_INIT_SIZE200#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineOVERFLOW-2typedefintKeyType;typedefstruct{KeyTypekey;}ElemType;typedefstruct{ElemType*elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空intlength;//表长度}SSTable;voidInitST(SSTable&ST){ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));if(!ST.elem)exit(OVERFLOW);ST.length=0;}voidCreateST(SSTable&ST){inti;printf("输入表长:");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++)scanf("%d",&ST.elem[i].key);}voidPrintST(SSTableST){inti;for(i=1;i<=ST.length;i++)printf("%2d",ST.elem[i].key);printf("\n");}intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素//若找到,则函数值为该元素在表中的位置,否则为0intlow,high,mid;low=1;high=ST.length;//置区间初值printf("下标:");while(low<=high){mid=(low+high)/2;printf("%d→",mid);if(EQ(key,ST.elem[mid].key))returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找elselow=mid+1;}return0;//顺序表中不存在待查元素}voidmain(){SSTableST;KeyTypekey;InitST(ST);CreateST(ST);printf("顺序查找表:");PrintST(ST);printf("输入要查找的关键字:");scanf("%d",&key);intfound=Search_Bin(ST,key);if(found)printf("找到,为第%d个数据\n",found);elseprintf("没有找到!\n");}(3)直接插入排序#include<stdio.h>#defineMAXSIZE20#defineLT(a,b)((a)<(b))typedefintKeyType;typedefstruct{KeyTypekey;}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型voidCreateSq(SqList&L){inti;printf("输入表长:");scanf("%d",&L.length);for(i=1;i<=L.length;i++)scanf("%d",&L.r[i].key);}voidPrintSq(SqListL){inti;for(i=1;i<=L.length;i++)printf("%2d",L.r[i].key);printf("\n");}voidInsertSort(SqList&L){//对顺序表L作直接插入排序inti,j;printf("排序过程:\n");for(i=2;i<=L.length;++i){if(LT(L.r[i].key,L.r[i-1].key)){//"<",需将L.r[i]插入有序子表L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}PrintSq(L);}}//InsertSortvoidmain(){SqListL;CreateSq(L);printf("原始顺序表:");PrintSq(L);InsertSort(L);printf("排序后的顺序表:");PrintSq(L);}(4)快速排序#include<stdio.h>#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型voidCreateSq(SqList&L){inti;printf("输入表长:");scanf("%d",&L.length);for(i=1;i<=L.length;i++)scanf("%d",&L.r[i].key);}voidPrintSq(SqListL){inti;for(i=1;i<=L.length;i++)printf("%2d",L.r[i].key);printf("\n");}intPartition(SqList&L,intlow,inthigh){//交换顺序表L中子表r[low…high]的记录,枢轴记录到位,并返回其所在位置,//此时在它之前/后的记录均不大/小于它intpivotkey;L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录pivotkey=L.r[low].key;//枢轴记录关键字while(low<high){//从表的两端交替地向中间扫描while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端}L.r[low]=L.r[0];//枢轴记录到位PrintSq(L);returnlow;//返回枢轴位置}//PartitionvoidQSort(SqList&L,intlow,inthigh){//对顺序表L中的子序列L.r[low…high]作快速排序intpivotloc;if(low<high){//长度大于1pivotloc=Partition(L,low,high);//将L.r[low…high]一分为二QSort(L,low,pivotloc-1
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 大班柳树姑娘听评课记录
- 2018听课评课记录
- 2013年造价课程设计
- 泉州市金门县2024年一级造价工程师《土建计量》预测试卷含解析
- 《助产士的沟通技巧》课件
- 《豪威MT平台操作》课件
- 《数据通信网》课件
- 理学成果答辩报告模板
- 和田专业水池防腐施工方案
- 吉林锅炉烟囱维修施工方案
- 行政事业单位财务报销审批手续的若干规定
- word-电子公章-模板
- 精益生产设备管理培训
- 新版PEP三上英语Look-at-me课件
- 箱梁毕业设计
- 2022年西藏开发投资集团有限公司招聘59人测试题(8)模拟试题3套(含答案解析)
- (完整版)物理化学习题库(含答案)
- 新人教版(部编)八年级语文上册《外古诗词诵读-采桑子(轻舟短棹西湖好)》优质课课件-1
- 分式的乘方公开课一等奖省优质课大赛获奖课件
- 《行政组织学》广东开放大学2022年10月题库答案
- JJF(苏)212-2018 锥孔端面直径测量表校准规范-(现行有效)
评论
0/150
提交评论