北理工数据结构实验报告4Word格式.docx
《北理工数据结构实验报告4Word格式.docx》由会员分享，可在线阅读，更多相关《北理工数据结构实验报告4Word格式.docx（12页珍藏版）》请在冰点文库上搜索。
L）
操作结果：
构造一个线性表L。
output（SqListL）
初始条件：
线性表L已存在。
按顺序在屏幕上输出L的数据元素。
BiInsertionsort（SqlistL）
对L的数据元素进行折半插入排序。
QuickSort（SqlistL）
对L的数据元素进行交换排序。
SelectSort（SqList&
L）
对L的数据元素进行选择排序。
}ADTSqList
⑵宏定义
#defineKeyTypeint
#defineMAXSIZE10
#defineok1
#defineerror0
⑶主程序流程
由主程序首先调用Input（L）函数创建顺序表，
先调用BiInsertionsort（L）函数进行折半插入排序，调用output（L）函数显示排序结果。
再调用QuickSort（L）函数进行交换排序，调用output（L）函数显示排序结果。
最后调用SelectSort（L）函数进行选择排序，调用output（L）函数显示排序结果。
⑷模块调用关系
由主函数模块调用创建顺序表模块，排序模块与显示输出模块。
（5）流程图
2、详细设计
（1）数据类型设计
/*顺序存储结构*/
typedefstruct
{
KeyTypeKey;
//关键字项
}RedType;
RedTyper[MAXSIZE+1];
intlength;
//=MAXSIZE;
}Sqlist;
//定义顺序表类型
（2）操作算法设计
/*输入数据*/
intInput（Sqlist&
for（inti=1;
i<
=MAXSIZE;
i++）
scanf（"
%d"
&
L.r[i].Key）;
L.length=MAXSIZE;
returnok;
}
/*输出排好的数字*/
intoutput（SqlistL）
{
for（inti=1;
i++）
printf（"
%-4d"
L.r[i].Key）;
printf（"
\n"
）;
returnok;
/*折半插入排序法*/
voidBiInsertionsort（SqlistL）
inti,j,low,high,m;
for（i=2;
=L.length;
{
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<
L.r[m].Key）high=m-1;
elselow=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（"
折半插入排序:
output（L）;
}//BiInsertionsort
/*快速交换排序法*/
intPartition（Sqlist&
L,intlow,inthigh）
intpivotkey;
L.r[0].Key=L.r[low].Key;
//用子表的第一个记录作枢轴记录
pivotkey=L.r[low].Key;
//枢轴记录关键字
while（low<
high）//从表的两端交替地向中间扫描
{
high&
&
L.r[high].Key>
=pivotkey）
--high;
//将比枢轴记录小的记录移到低端
}//while
L.r[low].Key=L.r[high].Key;
L.r[low].Key<
++low;
//将比枢轴记录大的记录移到高端
L.r[high].Key=L.r[low].Key;
}//while
L.r[low].Key=L.r[0].Key;
//枢轴记录到位
returnlow;
//返回枢轴位置
}//Partition
voidQSort（Sqlist&
intpivotloc;
if（low<
high）//长度大于1
pivotloc=Partition（L,low,high）;
//将L.r[low…high]一分为二
QSort（L,low,pivotloc-1）;
//对低子表递归排序，pivotloc是枢轴位置
QSort（L,pivotloc+1,high）;
//对高子表递归排序
}//if
}//QSort
voidQuickSort（Sqlist&
L）//对顺序表L做快速排序
QSort（L,1,L.length）;
交换排序:
output（L）;
}//QuickSort
/*选择排序法*/
voidSelectSort（SqlistL）
inti,j,k,temp;
for（i=1;
{k=i;
//要确定排序元素的位置
for（j=i+1;
j<
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
选择排序:
output（L）;
}//SelectSort
⑶主函数设计
intmain（）
SqlistL;
Input（L）;
//输入要排的数字，创建线性表L
BiInsertionsort（L）;
//对L进行插入排序,输出线性表L
BubbleSort（L）;
//对L进行交换排序,输出线性表L
SelectSort（L）;
//对L进行选择排序,输出线性表L
四、程序调试分析
1、由于本次实验中存储数据的线性表是在Input函数中进行的，所以开始时忘了将l.length初始化，出现报错，开始我直接在定义线性表的结构中赋值为MAXSIZE，还是有问题，原来是定义结构时不能直接在内部赋初值！
通过这次错误让我对数组的用法有了一个更深的了解，实践后记得更深。
2、对于快速排序一直都不太理解，编译时出现了各种报错提示，后来我又回头仔仔细细的看了书上的内容，重新理解快排的算法思想，先设置枢轴，进行一趟简单的分大小，再进行递归调用，直到排序结束，重新写了一遍程序，调试了几次就成功了，对于快排有了一个较深的把握与理解。
3、一直对于快排的交换环节存有疑虑，当出现第一个比枢轴小的关键字时就进行这句L.r[low].Key=L.r[high].Key;
原以为这样后low空间里的关键字被换成了high的了，那low里的关键字就缺失了，但是调试却没有问题，经过单步运行后，发现原来low里的为枢轴量，放在了首单元地址里，后来又换回来了，所以没有缺失。
4、在选择排序中，刚开始我的程序是比较后就直接交换的，后来看书上是记住数组的下标全部比较后进行一次交换就可以了，少了不少的交换次数，效率提高了不少，让我看到了优化程序的重要性，在实现的基础上不断地去优化程序，让程序变得更好。
五、用户使用说明
1、本程序的运行环境为DOS操作系统，执行文件为：
排序.exe。
2、进入程序后，输入所需排序的十个整数，回车运行程序。
3、程序运行后即在屏幕上输出计算结果。
六、程序运行结果
七、程序清单
#include"
stdio.h"
/*宏定义*/
#defineKeyTypeint
printf（"
inti,j,low,high,m;
for（i=2;
{
L.r[0].Key=L.r[i].Key;
low=1;
m=（low+high）/2;
if（L.r[0].Key<
elselow=m+1;
}
for（j=i-1;
L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}//low
output（L）;
intpivotkey;
L.r[0].Key=L.r[low].Key;
//用子表的第一个记录作枢轴记录
pivotkey=L.r[low].Key;
//枢轴记录关键字
while（low<
high）//从表的两端交替地向中间扫描
{
--high;
L.r[low].Key=L.r[high].Key;
++low;
L.r[high].Key=L.r[low].Key;
}//while
L.r[low].Key=L.r[0].Key;
returnlow;
intpivotloc;
if（low<
pivotloc=Partition（L,low,high）;
QSort（L,low,pivotloc-1）;
QSort（L,pivotloc+1,high）;
}//if
QSort（L,1,L.length）;
inti,j,k,temp;
for（i=1;
{k=i;
for（j=i+1;
if（L.r[k].Key>
}
temp=L.r[i].Key;
L.r[i].Key=L.r[k].Key;
L.r[k].Key=temp;
}//for
//输入要排的数字
BiInsertionsort（L）;
QuickSort（L）;
SelectSort（L）;
升级会员 