《数据结构与算法统计》
实验报告
——实验四
学院：
班级：
学号：
姓名：
一、实验目的
1、熟悉VC环境，学会使用C语言利用顺序表解决实际问题。
2、通过上机、编程调试，加强对线性表的理解和运用的能力。
3、锻炼动手编程，独立思考的能力。
二、实验内容
从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。
三、程序设计
1、概要设计
为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。
(1)抽象数据类型：
ADT SqList{
数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥K
数据关系：R1=11{,|,,1,2,,}i i
i i a a a a D i n --<>∈=K 基本操作：
Input(Sqlist & L)
操作结果：构造一个线性表L 。
output(SqList L)
初始条件：线性表L 已存在。
操作结果：按顺序在屏幕上输出L 的数据元素。
BiInsertionsort (Sqlist L)
初始条件：线性表L 已存在。
操作结果：对L 的数据元素进行折半插入排序。
QuickSort (Sqlist L)
初始条件：线性表L 已存在。
操作结果：对L 的数据元素进行交换排序。
SelectSort(SqList &L)
初始条件：线性表L 已存在。
操作结果：对L 的数据元素进行选择排序。
}ADT SqList
⑵ 宏定义
#define KeyType int
#define MAXSIZE 10
#define ok 1
#define error 0
⑶主程序流程
由主程序首先调用Input(L)函数创建顺序表，
先调用BiInsertionsort (L)函数进行折半插入排序，调用output(L)函数显示排序结果。
再调用QuickSort (L)函数进行交换排序，调用output (L)函数显示排序结果。
最后调用SelectSort(L)函数进行选择排序，调用output(L)函数显示排序结果。
⑷模块调用关系
由主函数模块调用创建顺序表模块，排序模块与显示输出模块。
(5)流程图
2、详细设计
(1)数据类型设计
/* 顺序存储结构 */
typedef struct
{
KeyType Key; //关键字项
} RedType;
开始
结束
创建线性表进行插入排序进行交换排序进行选择排序输出排序结果
输出排序结果输出排序结果
输入待排数字
typedef struct
{
RedType r[MAXSIZE+1];
int length; // =MAXSIZE;
} Sqlist; //定义顺序表类型
(2)操作算法设计
/* 输入数据 */
int Input(Sqlist & L)
{
for(int i=1;i<=MAXSIZE;i++)
scanf("%d",&L.r[i].Key);
L.length=MAXSIZE;
return ok;
}
/* 输出排好的数字 */
int output(Sqlist L)
{
for(int i=1;i<=MAXSIZE;i++)
printf("%-4d",L.r[i].Key);
printf("\n");
return ok;
}
/* 折半插入排序法 */
void BiInsertionsort (Sqlist L)
{
int i,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 else low=m+1; } for(j=i-1;j>=high+1;j--) //插入位置后的袁术后移一位.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; //插入元素 }//low printf("折半插入排序:\n"); output(L); }//BiInsertionsort /* 快速交换排序法 */ int Partition(Sqlist &L,int low,int high) { int pivotkey; L.r[0].Key=L.r[low].Key; //用子表的第一个记录作枢轴记录 pivotkey=L.r[low].Key; //枢轴记录关键字 while(low { while(low { --high;//将比枢轴记录小的记录移到低端 }//while L.r[low].Key=L.r[high].Key; while(low { ++low;//将比枢轴记录大的记录移到高端 }//while L.r[high].Key=L.r[low].Key; }//while L.r[low].Key=L.r[0].Key;//枢轴记录到位 return low;//返回枢轴位置 }//Partition void QSort(Sqlist &L,int low,int high) { int pivotloc; if(low { pivotloc=Partition(L,low,high);//将L.r[low…high]一分为二 QSort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢轴位置 QSort(L,pivotloc+1,high);//对高子表递归排序 }//if }//QSort void QuickSort(Sqlist &L) //对顺序表L做快速排序 { QSort(L,1,L.length); printf("交换排序:\n"); output(L); }//QuickSort /* 选择排序法 */ void SelectSort(Sqlist L) { int i,j,k,temp; for(i=1;i<=L.length;i++) { k=i; //要确定排序元素的位置 for(j=i+1;j<=L.length;j++) { if(L.r[k].Key>L.r[j].Key) k=j; //若后面有更小的记录下其位置} temp=L.r[i].Key; 输出线性表L L.r[i].Key=L.r[k].Key; L.r[k].Key=temp; }//for printf("选择排序:\n"); output(L); }//SelectSort ⑶主函数设计 int main() { Sqlist L; Input(L); //输入要排的数字，创建线性表L BiInsertionsort(L); //对L进行插入排序, 输出线性表L BubbleSort(L); //对L进行交换排序,输出线性表L SelectSort(L); //对L进行选择排序, 输出线性表L return ok; } 四、程序调试分析 1、由于本次实验中存储数据的线性表是在Input函数中进行的，所以开始时忘了将l.length初始化，出现报错，开始我直接在定义线性表的结构中赋值为MAXSIZE，还是有问题，原来是定义结构时不能直接在内部赋初值！通过这次错误让我对数组的用法有了一个更深的了解，实践后记得更深。 2、对于快速排序一直都不太理解，编译时出现了各种报错提示，后来我又回头仔仔细细的看了书上的内容，重新理解快排的算法思想，先设置枢轴，进行一趟简单的分大小，再进行递归调用，直到排序结束，重新写了一遍程序，调试了几次就成功了，对于快排有了一个较深的把握与理解。 3、一直对于快排的交换环节存有疑虑，当出现第一个比枢轴小的关键字时就进行这句L.r[low].Key=L.r[high].Key;原以为这样后low空间里的关键字被换成了high的了，那low里的关键字就缺失了，但是调试却没有问题，经过单步运行后，发现原来low里的为枢轴量，放在了首单元地址里，后来又换回来了，所以没有缺失。 4、在选择排序中，刚开始我的程序是比较后就直接交换的，后来看书上是记住数组的下标全部比较后进行一次交换就可以了，少了不少的交换次数，效率提高了不少，让我看到了优化程序的重要性，在实现的基础上不断地去优化程序，让程序变得更好。 五、用户使用说明 1、本程序的运行环境为DOS操作系统，执行文件为：排序.exe。 2、进入程序后，输入所需排序的十个整数，回车运行程序。
相关主题
文本预览