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

1、数据结构与算法设计实验报告实验四学院：自动化学院班级：_学号：_姓名：_ _一、实验目的 1、熟悉VC环境，学习使用C语言实现链表的存储结构。2、通过编程、上机调试，进一步理解线性表、链表、环表的基本概念。3、锻炼动手编程，独立思考的能力。二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。三、程序设计 1、概要设计为实现上述程序功能，应用线性表寄存数字序列。为此，需要线性表的抽象数据结构。(1)、线性表的抽象数据类型定义为：ADT SqList 数据对象：D=数据关系：R1= 基本操作：CreateList(&L)操作结果：构造一个线性

2、表L。ShowList(&L)初始条件：线性表L已存在。操作结果：按顺序在屏幕上输出L的数据元素。InsertSort(&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行插入排序。QuickSort(&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行快速排序。SelectSort(&L)初始条件：线性表L已存在。操作结果：对L的数据元素进行选择排序。ADT SqList (2)、宏定义#define MAXSIZE 10#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0 (3

3、)、主程序流程主程序首先调用CreateList(l1)函数创建顺序表l1。随后调用InsertSort(l1)、QuickSort(l2)、SelectSort(l3)函数计算三种排序结果，并调用相应的ShowList()函数显示排序结果。(4)、模块调用关系：由主函数模块调用创建模块，显示模块与计算模块。(5)、流程图开始创建线性表排序输出结果结束 2、详细设计 (1)、数据类型设计typedef int Status;typedef int ElemType; /定义数据元素类型typedef structElemType rMAXSIZE+1;int length;SqList; /定

4、义顺序表类型(2)、操作算法设计Status CreateList(SqList &L)/创建顺序表L.length=0;for(int i=1;i=MAXSIZE;i+)scanf(%d,&L.ri);L.length+;return OK;Status ShowList(SqList &L)/显示顺序表的内容for(int i=1;i=MAXSIZE;i+)printf(%d ,L.ri);return OK;void InsertSort(SqList &L)/插入排序for(int i=2;i=L.length;+i)if(L.riL.ri-1) /需将L.ri插入有序子表L.r0=L

5、.ri; /复制为哨兵L.ri=L.ri-1;for(int j=i-2;L.r0L.rj;-j)L.rj+1=L.rj; /记录后移L.rj+1=L.r0; /插入到正确位置int Partition(SqList &L, int low, int high)/一趟快速排序L.r0=L.rlow; /用子表第一个记录做枢轴元素int pivotkey=L.rlow; /枢轴记录关键字while(lowhigh) /从两端交替向中间扫描while(low=pivotkey) -high;L.rlow=L.rhigh; /将记录小的移到低端while(lowhigh & L.rlow=pivot

6、key) +low;L.rhigh=L.rlow; /将记录大的移到高端 L.rlow=L.r0; /枢轴记录到位return low; /返回枢轴位置void QSort(SqList &L,int low,int high)/对low,high做快速排序if(lowhigh) /长度大于1int pivotloc=Partition(L,low,high); /一分为二QSort(L,low,pivotloc-1); /对低子表递归排序QSort(L,pivotloc+1,high); /对高子表递归排序void QuickSort(SqList &L)/对L快速排序QSort(L,1,L

7、.length);void SelectSort(SqList &L)/对L选择排序for(int i=1;iL.length;+i) /选择第i小记录并交换到位int k=i;for(int j=i+1;j=L.length;j+) if(L.rjL.rk)k=j; if(k!=i) L.r0=L.ri;L.ri=L.rk;L.rk=L.r0; /与第i个元素交换 (3)、主函数设计int main()/主程序SqList l1,l2,l3;printf(Please input 10 numbers:n);CreateList(l1); /创建线性表l1 l2=l1; l3=l1;Inse

8、rtSort(l1); /对l1插入排序printf(The result of InsertSort is:n);ShowList(l1);printf(n);QuickSort(l2); /对l2快速排序printf(The result of QuickSort is:n);ShowList(l2);printf(n);SelectSort(l3); /对l3选择排序printf(The result of SelectSort is:n);ShowList(l3);printf(n);return 0;四、程序调试分析 1、由于对于快速排序理解不深，开始时出现了许多细节问题，导致排序结

9、果不正常，经过修改后得以解决。2、在选择排序中，由于不细心，误将”打为”=”导致结果不正常。3、在快速排序中，一些后引入的变量，例如pivotkey没有声明，导致编译失败。五、用户使用说明 1、本程序的运行环境为DOS操作系统，执行文件为：Sort.exe。2、进入程序后，在Please input 10 numbers:后输入所需排序的十个整数，回车运行程序。 3、程序运行后即在屏幕上输出计算结果。六、程序运行结果1、2、七、程序清单#define MAXSIZE 10#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#d

10、efine FALSE 0#includestdio.h#includestdlib.htypedef int Status;typedef int ElemType; /定义数据元素类型typedef structElemType rMAXSIZE+1;int length;SqList; /定义顺序表类型Status CreateList(SqList &L)/创建顺序表L.length=0;for(int i=1;i=MAXSIZE;i+)scanf(%d,&L.ri);L.length+;return OK;Status ShowList(SqList &L)/显示顺序表的内容for(

11、int i=1;i=MAXSIZE;i+)printf(%d ,L.ri);return OK;void InsertSort(SqList &L)/插入排序for(int i=2;i=L.length;+i)if(L.riL.ri-1) /需将L.ri插入有序子表L.r0=L.ri; /复制为哨兵L.ri=L.ri-1;for(int j=i-2;L.r0L.rj;-j)L.rj+1=L.rj; /记录后移L.rj+1=L.r0; /插入到正确位置int Partition(SqList &L, int low, int high)/一趟快速排序L.r0=L.rlow; /用子表第一个记录做

12、枢轴元素int pivotkey=L.rlow; /枢轴记录关键字while(lowhigh) /从两端交替向中间扫描while(low=pivotkey) -high;L.rlow=L.rhigh; /将记录小的移到低端while(lowhigh & L.rlow=pivotkey) +low;L.rhigh=L.rlow; /将记录大的移到高端 L.rlow=L.r0; /枢轴记录到位return low; /返回枢轴位置void QSort(SqList &L,int low,int high)/对low,high做快速排序if(lowhigh) /长度大于1int pivotloc=P

13、artition(L,low,high); /一分为二QSort(L,low,pivotloc-1); /对低子表递归排序QSort(L,pivotloc+1,high); /对高子表递归排序void QuickSort(SqList &L)/对L快速排序QSort(L,1,L.length);void SelectSort(SqList &L)/对L选择排序for(int i=1;iL.length;+i) /选择第i小记录并交换到位int k=i;for(int j=i+1;j=L.length;j+) if(L.rjL.rk)k=j; if(k!=i) L.r0=L.ri;L.ri=L.rk;L.rk=L.r0; /与第i个元素交换int main()/主程序SqList l1,l2,l3;printf(Please input 10 numbers:n);CreateList(l1); /创建线性表l1 l2=l1; l3=l1;InsertSort(l1); /对l1插入排序printf(The result of Ins