《北京理工大学数据结构实验报.docx》由会员分享，可在线阅读，更多相关《北京理工大学数据结构实验报.docx（12页珍藏版）》请在三一办公上搜索。
1、北京理工大学数据结构实验报数据结构与算法统计 实验报告 实验四 学院： 班级： 学号： 姓名： 1 一、实验目的 1、熟悉VC环境，学会使用C语言利用顺序表解决实际问题。 2、通过上机、编程调试，加强对线性表的理解和运用的能力。 3、锻炼动手编程，独立思考的能力。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList 数据对象：D=ai|aiElemSet,i=1,2,K,n,n0 数据关系：R
2、1=|ai-1,aiD,i=1,2,K,n 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L。 OutPut(SqList L) 初始条件：线性表L已存在。 操作结果：按顺序在屏幕上输出L的数据元素。 InsertSort(SqList &L) 初始条件：线性表L已存在。 操作结果：对L的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L已存在。 操作结果：对L的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L已存在。 操作结果：对L的数据元素进行选择排序。 ADT SqList 主程序流程 由主程
3、序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。 模块调用关系 2 由主函数模块调用创建顺序表模块，排序模块与显示输出模块。 流程图 开始 创建线性表 进行插入排序 输出排序结果 创建线性表 进行交换排序 输出排序结果 创建线性表 进行选择
4、排序 输出排序结果 结束 2、详细设计 (1)数据类型设计 #define MAXSIZE 15/用作示例的小顺序表的最大长度 typedef struct int key;/关键字项 int otherinfo;/其它数据项 3 RedType;/记录类型 typedef struct RedType rMAXSIZE+1;/r0闲置或用作哨兵单元 int length;/顺序表长度 SqList;/顺序表类型 (2)操作算法设计 void InPut(SqList &L) /输入数字，创建顺序表 void InsertSort(SqList &L) /对顺序表L作直接插入排序 int Pa
5、rtition(SqList &L,int low,int high) /交换顺序表L中子表rlowhigh的记录，枢轴记录到位，并返回其所在位置， /此时在它之前的记录均不大于它。 int i; printf(请输入10个数字:n); L.length=10; for(i=1;i=L.length;i+) scanf(%d,&L.ri.key); int i,j; for(i=2;i=L.length;i+) if(L.ri.keyL.ri-1.key)/如果“”,需将L.ri插入有序子表 L.r0.key=L.ri.key;/复制为哨兵 L.ri.key=L.ri-1.key; for(j
6、=i-2;L.r0.keyL.rj.key;j-) L.rj+1.key=L.rj.key;/记录后移 L.rj+1.key=L.r0.key;/插入到正确位置 int pivotkey; 4 L.r0.key=L.rlow.key;/用子表的第一个记录作枢轴记录 pivotkey=L.rlow.key;/枢轴记录关键字 while(lowhigh)/从表的两端交替地向中间扫描 while(low=pivotkey) -high;/将比枢轴记录小的记录移到低端 L.rlow.key=L.rhigh.key; while(lowhigh&L.rlow.key=pivotkey) +low;/将比
7、枢轴记录大的记录移到高端 L.rhigh.key=L.rlow.key; L.rlow.key=L.r0.key;/枢轴记录到位 return low;/返回枢轴位置 void QSort(SqList &L,int low,int high) /对顺序表L中的子序列L.rlowhigh作快速排序 int pivotloc; if(lowhigh)/长度大于1 pivotloc=Partition(L,low,high);/将L.rlowhigh一分为二 QSort(L,low,pivotloc-1);/对低子表递归排序，pivotloc是枢轴位置 QSort(L,pivotloc+1,hig
8、h);/对高子表递归排序 void QuickSort(SqList &L) /对顺序表L做快速排序 void SelectSort(SqList &L) /对顺序表L作简单选择排序 QSort(L,1,L.length); int i,j,k; for(i=1;iL.length;i+)/选择第i小的记录，并交换到位 k=i; 5 for(j=i+1;jL.length;j+)/在L.riL.length中选择key最小的记录 if(L.rj.keyL.rk.key) k=j; if(i!=k)/与第i个记录交换 L.r0.key=L.ri.key; L.ri.key=L.rk.key; L
9、.rk.key=L.r0.key; void OutPut(SqList L) /输出顺序表 int i; for(i=1;i=L.length;i+) printf(%d ,L.ri.key); printf(n); 主函数设计 void main/主程序 SqList L; printf(插入排序法:n); InPut(L);/创建线性表L InsertSort(L);/对L进行插入排序 OutPut(L);/输出线性表L printf(交换排序法:n); InPut(L);/创建线性表L QuickSort(L);/对L进行交换排序 OutPut(L);/输出线性表L printf(选择
10、排序法:n); InPut(L);/创建线性表L SelectSort(L);/对L进行选择排序 OutPut(L);/输出线性表L 6 四、程序调试分析 在快速排序中，对一些后引入的变量，如pivotkey没有声明，导致编译失败。 在直接插入排序中，由于对程序理解不深，将if的扩错了位置，导致程序不能按预期输出。 五、程序运行结果 测试一： 插入排序法: 请输入10个数字: 1 3 5 7 9 2 4 6 8 0 0 1 2 3 4 5 6 7 8 9 交换排序法: 请输入10个数字: 1 3 5 7 9 2 4 6 8 0 0 1 2 3 4 5 6 7 8 9 选择排序法: 请输入10个
11、数字: 1 3 5 7 9 2 4 6 8 0 1 2 3 4 5 6 7 8 9 0 测试二： 插入排序法: 请输入10个数字: 49 38 65 97 76 13 27 67 52 34 13 27 34 38 49 52 65 67 76 97 交换排序法: 请输入10个数字: 49 38 65 97 76 13 27 67 52 34 13 27 34 38 49 52 65 67 76 97 选择排序法: 请输入10个数字: 49 38 65 97 76 13 27 67 52 34 13 27 38 49 52 65 67 76 97 34 六、程序清单 #include #inc
12、lude #define MAXSIZE 15/用作示例的小顺序表的最大长度 typedef struct int key;/关键字项 int otherinfo;/其它数据项 7 RedType;/记录类型 typedef struct RedType rMAXSIZE+1;/r0闲置或用作哨兵单元 int length;/顺序表长度 SqList;/顺序表类型 void InPut(SqList &L); void InsertSort(SqList &L); void OutPut(SqList L); void QuickSort(SqList &L); void QSort(SqLi
13、st &L,int low,int high); void SelectSort(SqList &L); void main/主程序 SqList L; printf(插入排序法:n); InPut(L);/创建线性表L InsertSort(L);/对L进行插入排序 OutPut(L);/输出线性表L printf(交换排序法:n); InPut(L);/创建线性表L QuickSort(L);/对L进行交换排序 OutPut(L);/输出线性表L printf(选择排序法:n); InPut(L);/创建线性表L SelectSort(L);/对L进行选择排序 OutPut(L);/输出线
14、性表L void InPut(SqList &L)/输入数字，创建顺序表 void InsertSort(SqList &L)/对顺序表L作直接插入排序 int i; printf(请输入10个数字:n); L.length=10; for(i=1;i=L.length;i+) scanf(%d,&L.ri.key); int i,j; 8 for(i=2;i=L.length;i+) if(L.ri.keyL.ri-1.key)/如果“”,需将L.ri插入有序子表 L.r0.key=L.ri.key;/复制为哨兵 L.ri.key=L.ri-1.key; for(j=i-2;L.r0.key
15、L.rj.key;j-) L.rj+1.key=L.rj.key;/记录后移 L.rj+1.key=L.r0.key;/插入到正确位置 int Partition(SqList &L,int low,int high)/交换顺序表L中子表rlowhigh的记录，枢轴记录到位，并返回其所在位置， 于它。 int pivotkey; L.r0.key=L.rlow.key;/用子表的第一个记录作枢轴记录 pivotkey=L.rlow.key;/枢轴记录关键字 while(lowhigh)/从表的两端交替地向中间扫描 while(low=pivotkey) -high;/将比枢轴记录小的记录移到低
16、端 L.rlow.key=L.rhigh.key; while(lowhigh&L.rlow.key=pivotkey) +low;/将比枢轴记录大的记录移到高端 /此时在它之前的记录均不大 L.rhigh.key=L.rlow.key; L.rlow.key=L.r0.key;/枢轴记录到位 return low;/返回枢轴位置 void QSort(SqList &L,int low,int high)/对顺序表L中的子序列L.rlowhigh作快速排序 int pivotloc; if(lowhigh)/长度大于1 9 pivotloc=Partition(L,low,high);/将L
17、.rlowhigh一分为二 QSort(L,low,pivotloc-1);/对低子表递归排序，pivotloc是枢轴位置 QSort(L,pivotloc+1,high);/对高子表递归排序 void QuickSort(SqList &L)/对顺序表L做快速排序 QSort(L,1,L.length); void SelectSort(SqList &L)/对顺序表L作简单选择排序 int i,j,k; for(i=1;iL.length;i+)/选择第i小的记录，并交换到位 k=i; for(j=i+1;jL.length;j+)/在L.riL.length中选择key最小的记录 if(L.rj.keyL.rk.key) k=j; if(i!=k)/与第i个记录交换 L.r0.key=L.ri.key; L.ri.key=L.rk.key; L.rk.key=L.r0.key; void OutPut(SqList L)/输出顺序表 int i; for(i=1;i=L.length;i+) printf(n); printf(%d ,L.ri.key); 10 11
