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

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

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

2、(SqListL)初始条件：线性表L已存在。操作结果：按顺序在屏幕上输出L的数据元素。BiInsertionsort(SqlistL)初始条件：线性表L已存在。操作结果：对L的数据元素进行折半插入排序。QuickSort(SqlistL)初始条件：线性表L已存在。操作结果：对L的数据元素进行交换排序。SelectSort(SqList&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行选择排序。}ADTSqList⑵宏定义#defineKeyTypeint#defineMAXSIZE10#defineok1#defineerror0⑶主程序流程由主程序首先调用In

3、put(L)函数创建顺序表，先调用BiInsertionsort(L)函数进行折半插入排序，调用output(L)函数显示排序结果。10再调用QuickSort(L)函数进行交换排序，调用output(L)函数显示排序结果。最后调用SelectSort(L)函数进行选择排序，调用output(L)函数显示排序结果。⑷模块调用关系由主函数模块调用创建顺序表模块，排序模块与显示输出模块。(5)流程图开始结束创建线性表进行插入排序进行交换排序进行选择排序输出排序结果输出排序结果输出排序结果输入待排数字2、详细设计(1)数据类型设计/*顺序存储结构*/typedefstruct{

4、KeyTypeKey;//关键字项}RedType;10typedefstruct{RedTyper[MAXSIZE+1];intlength;//=MAXSIZE;}Sqlist;//定义顺序表类型(2)操作算法设计/*输入数据*/intInput(Sqlist&L){for(inti=1;i<=MAXSIZE;i++)scanf("%d",&L.r[i].Key);L.length=MAXSIZE;returnok;}/*输出排好的数字*/intoutput(SqlistL){for(inti=1;i<=MAXSIZE;i++)printf("%-4d",L.r[i]

5、.Key);printf("");returnok;}/*折半插入排序法*/voidBiInsertionsort(SqlistL){inti,j,low,high,m;for(i=2;i<=L.length;i++){L.r[0].Key=L.r[i].Key;//把要插入的当成哨兵low=1;high=i-1;while(low<=high)//折半法找到要插入的位置{m=(low+high)/2;if(L.r[0].Key=high+1;j--)//插入位置后的袁术后移一

6、位.r[j+1]=L.r[j];L.r[high+1]=L.r[0];//插入元素}//lowprintf("折半插入排序:");output(L);10}//BiInsertionsort/*快速交换排序法*/intPartition(Sqlist&L,intlow,inthigh){intpivotkey;L.r[0].Key=L.r[low].Key;//用子表的第一个记录作枢轴记录pivotkey=L.r[low].Key;//枢轴记录关键字while(low

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