北京理工大学数据结构实验报告4.doc

《北京理工大学数据结构实验报告4.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构与算法统计》实验报告——实验四学院：班级：学号：姓名：一、实验目的1、熟悉VC环境，学会使用C语言利用顺序表解决实际问题。2、通过上机、编程调试，加强对线性表的理解和运用的能力。3、锻炼动手编程，独立思考的能力。二、实验内容从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。三、程序设计1、概要设计为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。(1)抽象数据类型：ADTSqList{数据对象：D=数据关系：R1=基本操作：InPut(SqList&L)操作

2、结果：构造一个线性表L。OutPut(SqListL)初始条件：线性表L已存在。操作结果：按顺序在屏幕上输出L的数据元素。InsertSort(SqList&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行插入排序。QuickSort(SqList&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行快速排序。SelectSort(SqList&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行选择排序。}ADTSqList⑵主程序流程由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(

3、L)函数进行插入排序，调用OutPut(L)函数显示排序结果。再由主程序首先调用InPut(L)函数创建顺序表，调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。⑶模块调用关系由主函数模块调用创建顺序表模块，排序模块与显示输出模块。⑷流程图开始结束创建线性表创建线性表创建线性表进行插入排序进行交换排序进行选择排序输出排序结果输出排序结果输出排序结果2、详细设计(

4、1)数据类型设计#defineMAXSIZE15//用作示例的小顺序表的最大长度typedefstruct{intkey;//关键字项intotherinfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型(2)操作算法设计voidInPut(SqList&L)//输入数字，创建顺序表{inti;printf("请输入10个数字:");L.length=10;for(i=

5、1;i<=L.length;i++){scanf("%d",&L.r[i].key);}}voidInsertSort(SqList&L)//对顺序表L作直接插入排序{inti,j;for(i=2;i<=L.length;i++){if(L.r[i].key

6、L.r[j].key;//记录后移}L.r[j+1].key=L.r[0].key;//插入到正确位置}}}intPartition(SqList&L,intlow,inthigh)//交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在位置，/此时在它之前（后）的记录均不大（小）于它。{intpivotkey;L.r[0].key=L.r[low].key;//用子表的第一个记录作枢轴记录pivotkey=L.r[low].key;//枢轴记录关键字while(low

7、{while(low=pivotkey){--high;//将比枢轴记录小的记录移到低端}L.r[low].key=L.r[high].key;while(low

8、//对顺序表L中的子序列L.r[low…high]作快速排序{intpivotloc;if(low