北理工数据结构实验报告4.docx
《北理工数据结构实验报告4.docx》由会员分享，可在线阅读，更多相关《北理工数据结构实验报告4.docx（16页珍藏版）》请在冰点文库上搜索。
北理工数据结构实验报告4
《数据结构与算法统计》
实验报告
——实验四
学院：
班级：
学号：
姓名：
一、实验目的
1、熟悉VC环境，学会使用C语言利用顺序表解决实际问题。
2、通过上机、编程调试，加强对线性表的理解和运用的能力。
3、锻炼动手编程，独立思考的能力。
二、实验内容
从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。
三、程序设计
1、概要设计
为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。
（1）抽象数据类型：
ADTSqList{
数据对象：
D=
数据关系：
R1=
基本操作：
Input（Sqlist&L）
操作结果：
构造一个线性表L。
output（SqListL）
初始条件：
线性表L已存在。
操作结果：
按顺序在屏幕上输出L的数据元素。
BiInsertionsort（SqlistL）
初始条件：
线性表L已存在。
操作结果：
对L的数据元素进行折半插入排序。
QuickSort（SqlistL）
初始条件：
线性表L已存在。
操作结果：
对L的数据元素进行交换排序。
SelectSort（SqList&L）
初始条件：
线性表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;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;//=MAXSIZE;
}Sqlist;//定义顺序表类型
（2）操作算法设计
/*输入数据*/
intInput（Sqlist&L）
{
for（inti=1;i<=MAXSIZE;i++）
scanf（"%d",&L.r[i].Key）;
L.length=MAXSIZE;
returnok;
}
/*输出排好的数字*/
intoutput（SqlistL）
{
for（inti=1;i<=MAXSIZE;i++）
printf（"%-4d",L.r[i].Key）;
printf（"\n"）;
returnok;
}
/*折半插入排序法*/
voidBiInsertionsort（SqlistL）
{
inti,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].Keyelselow=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
/*快速交换排序法*/
intPartition（Sqlist&L,intlow,inthigh）
{
intpivotkey;
L.r[0].Key=L.r[low].Key;//用子表的第一个记录作枢轴记录
pivotkey=L.r[low].Key;//枢轴记录关键字
while（low{
while（low=pivotkey）
{
--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;//枢轴记录到位
returnlow;//返回枢轴位置
}//Partition
voidQSort（Sqlist&L,intlow,inthigh）
{
intpivotloc;
if（low{
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）;
printf（"交换排序:
\n"）;
output（L）;
}//QuickSort
/*选择排序法*/
voidSelectSort（SqlistL）
{
inti,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
⑶主函数设计
intmain（）
{
SqlistL;
Input（L）;//输入要排的数字，创建线性表L
BiInsertionsort（L）;//对L进行插入排序,输出线性表L
BubbleSort（L）;//对L进行交换排序,输出线性表L
SelectSort（L）;//对L进行选择排序,输出线性表L
returnok;
}
四、程序调试分析
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
#defineMAXSIZE10
#defineok1
#defineerror0
/*顺序存储结构*/
typedefstruct
{
KeyTypeKey;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;//=MAXSIZE;
}Sqlist;
/*输入数据*/
intInput（Sqlist&L）
{
for（inti=1;i<=MAXSIZE;i++）
scanf（"%d",&L.r[i].Key）;
L.length=MAXSIZE;
returnok;
}
/*输出排好的数字*/
intoutput（SqlistL）
{
for（inti=1;i<=MAXSIZE;i++）
printf（"%-4d",L.r[i].Key）;
printf（"\n"）;
returnok;
}
/*折半插入排序法*/
voidBiInsertionsort（SqlistL）
{
inti,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].Keyelselow=m+1;
}
for（j=i-1;j>=high+1;j--）//插入位置后的袁术后移一位
L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];//插入元素
}//low
printf（"折半插入排序:
\n"）;
output（L）;
}//BiInsertionsort
/*快速交换排序法*/
intPartition（Sqlist&L,intlow,inthigh）
{
intpivotkey;
L.r[0].Key=L.r[low].Key;//用子表的第一个记录作枢轴记录
pivotkey=L.r[low].Key;//枢轴记录关键字
while（low{
while（low=pivotkey）
{
--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;//枢轴记录到位
returnlow;//返回枢轴位置
}//Partition
voidQSort（Sqlist&L,intlow,inthigh）
{
intpivotloc;
if（low{
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）;
printf（"交换排序:
\n"）;
output（L）;
}//QuickSort
/*选择排序法*/
voidSelectSort（SqlistL）
{
inti,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.r[i].Key=L.r[k].Key;
L.r[k].Key=temp;
}//for
printf（"选择排序:
\n"）;
output（L）;
}//SelectSort
intmain（）
{
SqlistL;
Input（L）;//输入要排的数字
BiInsertionsort（L）;
QuickSort（L）;
SelectSort（L）;
returnok;
}
升级会员 