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

《数据结构与算法设计》实验报告——实验四学院：自动化学院班级：____学号：__姓名：________一、实验目的1、熟悉VC环境，学习使用C语言实现链表的存储结构。2、通过编程、上机调试，进一步理解线性表、链表、环表的基本概念。3、锻炼动手编程，独立思考的能力。二、实验内容从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。三、程序设计1、概要设计为实现上述程序功能，应用线性表寄存数字序列。为此，需要线性表的抽象数据结构。(1)、线性表的抽象数据类型定义为：ADTSqList{数据对象：D={|,1,2,,,0}iiaaElemSetinn数据关系：R1=11{,|,,1,2,,}iiiiaaaaDin基本操作：CreateList(&L)操作结果：构造一个线性表L。ShowList(&L)初始条件：线性表L已存在。操作结果：按顺序在屏幕上输出L的数据元素。InsertSort(&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行插入排序。QuickSort(&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行快速排序。SelectSort(&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行选择排序。}ADTSqList(2)、宏定义#defineMAXSIZE10#defineOVERFLOW-2#defineOK1#defineERROR0#defineTRUE1#defineFALSE0(3)、主程序流程主程序首先调用CreateList(l1)函数创建顺序表l1。随后调用InsertSort(l1)、QuickSort(l2)、SelectSort(l3)函数计算三种排序结果，并调用相应的ShowList()函数显示排序结果。(4)、模块调用关系：由主函数模块调用创建模块，显示模块与计算模块。(5)、流程图2、详细设计(1)、数据类型设计typedefintStatus;typedefintElemType;//定义数据元素类型typedefstruct{ElemTyper[MAXSIZE+1];intlength;}SqList;//定义顺序表类型(2)、操作算法设计StatusCreateList(SqList&L){//创建顺序表L.length=0;for(inti=1;i=MAXSIZE;i++){scanf(%d,&L.r[i]);L.length++;}returnOK;}StatusShowList(SqList&L){//显示顺序表的内容for(inti=1;i=MAXSIZE;i++)printf(%d,L.r[i]);returnOK;}voidInsertSort(SqList&L){//插入排序for(inti=2;i=L.length;++i)if(L.r[i]L.r[i-1]){//需将L.r[i]插入有序子表L.r[0]=L.r[i];//复制为哨兵开始创建线性表排序输出结果结束L.r[i]=L.r[i-1];for(intj=i-2;L.r[0]L.r[j];--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}intPartition(SqList&L,intlow,inthigh){//一趟快速排序L.r[0]=L.r[low];//用子表第一个记录做枢轴元素intpivotkey=L.r[low];//枢轴记录关键字while(lowhigh){//从两端交替向中间扫描while(lowhigh&&L.r[high]=pivotkey)--high;L.r[low]=L.r[high];//将记录小的移到低端while(lowhigh&&L.r[low]=pivotkey)++low;L.r[high]=L.r[low];//将记录大的移到高端}L.r[low]=L.r[0];//枢轴记录到位returnlow;//返回枢轴位置}voidQSort(SqList&L,intlow,inthigh){//对[low,high]做快速排序if(lowhigh){//长度大于1intpivotloc=Partition(L,low,high);//一分为二QSort(L,low,pivotloc-1);//对低子表递归排序QSort(L,pivotloc+1,high);//对高子表递归排序}}voidQuickSort(SqList&L){//对L快速排序QSort(L,1,L.length);}voidSelectSort(SqList&L){//对L选择排序for(inti=1;iL.length;++i){//选择第i小记录并交换到位intk=i;for(intj=i+1;j=L.length;j++)if(L.r[j]L.r[k])k=j;if(k!=i){L.r[0]=L.r[i];L.r[i]=L.r[k];L.r[k]=L.r[0];//与第i个元素交换}}}(3)、主函数设计intmain(){//主程序SqListl1,l2,l3;printf(Pleaseinput10numbers:\n);CreateList(l1);//创建线性表l1l2=l1;l3=l1;InsertSort(l1);//对l1插入排序printf(TheresultofInsertSortis:\n);ShowList(l1);printf(\n);QuickSort(l2);//对l2快速排序printf(TheresultofQuickSortis:\n);ShowList(l2);printf(\n);SelectSort(l3);//对l3选择排序printf(TheresultofSelectSortis:\n);ShowList(l3);printf(\n);return0;}四、程序调试分析1、由于对于快速排序理解不深，开始时出现了许多细节问题，导致排序结果不正常，经过修改后得以解决。2、在选择排序中，由于不细心，误将””打为”=”导致结果不正常。3、在快速排序中，一些后引入的变量，例如pivotkey没有声明，导致编译失败。五、用户使用说明1、本程序的运行环境为DOS操作系统，执行文件为：Sort.exe。2、进入程序后，在Pleaseinput10numbers:后输入所需排序的十个整数，回车运行程序。3、程序运行后即在屏幕上输出计算结果。六、程序运行结果1、2、七、程序清单#defineMAXSIZE10#defineOVERFLOW-2#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#includestdio.h#includestdlib.htypedefintStatus;typedefintElemType;//定义数据元素类型typedefstruct{ElemTyper[MAXSIZE+1];intlength;}SqList;//定义顺序表类型StatusCreateList(SqList&L){//创建顺序表L.length=0;for(inti=1;i=MAXSIZE;i++){scanf(%d,&L.r[i]);L.length++;}returnOK;}StatusShowList(SqList&L){//显示顺序表的内容for(inti=1;i=MAXSIZE;i++)printf(%d,L.r[i]);returnOK;}voidInsertSort(SqList&L){//插入排序for(inti=2;i=L.length;++i)if(L.r[i]L.r[i-1]){//需将L.r[i]插入有序子表L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(intj=i-2;L.r[0]L.r[j];--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}intPartition(SqList&L,intlow,inthigh){//一趟快速排序L.r[0]=L.r[low];//用子表第一个记录做枢轴元素intpivotkey=L.r[low];//枢轴记录关键字while(lowhigh){//从两端交替向中间扫描while(lowhigh&&L.r[high]=pivotkey)--high;L.r[low]=L.r[high];//将记录小的移到低端while(lowhigh&&L.r[low]=pivotkey)++low;L.r[high]=L.r[low];//将记录大的移到高端}L.r[low]=L.r[0];//枢轴记录到位returnlow;//返回枢轴位置}voidQSort(SqList&L,intlow,inthigh){//对[low,high]做快速排序if(lowhigh){//长度大于1intpivotloc=Partition(L,low,high);//一分为二QSort(L,low,pivotloc-1);//对低子表递归排序QSort(L,pivotloc+1,high);//对高子表递归排序}}voidQuickSort(SqList&L){//对L快速排序QSort(L,1,L.length);}voidSelectSort(SqList&L){//对L选择排序for(inti=1;iL.length;++i){//选择第i小记录并交换到位intk=i;for(intj=i+1;j=L.length;j++)if(L.r[j]L.r[k])k=j;if(k!=i){L.r[0]=L.r[i];L.r[i]=L.r[k];L.r[k]=L.r[0];//与第i个元素交换}}}intmain(){//主程序SqListl1,l2,l3;printf(Pleaseinput10numbers:\n);CreateList(l1);//创建线性表l1l2=l1;l3=l1;InsertSort(l1);//对l1插入排序printf(TheresultofInsertSortis:\n);ShowList(l1);printf(\n);QuickSort(l2);//对l2快速排序printf(TheresultofQuickSortis:\n);ShowList(l2);printf(\n);SelectSort(l3);//对l3选择排序printf(TheresultofSelectSortis:\n);ShowList(l3);printf(\n);return0;}