当前位置:文档之家› 北京理工大学《数据结构与算法设计》实验报告实验四

北京理工大学《数据结构与算法设计》实验报告实验四

《数据结构与算法设计》
实验报告
——实验四
学院:
班级:
学号:
姓名:
一、实验目的
1.
通过实验实践、巩固线性表的相关操作; 2.
熟悉VC 环境,加强编程、调试的练习; 3.
用C 语言实现线性表的抽象数据类型,实现线性表构造、插入、取数据等基本操作; 4. 理论知识与实际问题相结合,利用上述基本操作实现三种排序并输出。

二、实验内容
从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。

三、程序设计
1、概要设计
为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。

(1)抽象数据类型:
ADT SqList{
数据对象:D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥
数据关系:R1=11{,|,,1,2,,}i i
i i a a a a D i 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
⑵主程序流程
由主程序首先调用InPut(L)函数创建顺序表,调用InsertSort(L)函数进行插入排序,
调用OutPut(L)函数显示排序结果。

调用QuickSort(L)函数进行交换排序,调用OutPut(L)
函数显示排序结果。

调用SelectSort(L)函数进行选择排序,调用OutPut(L)函数显示排序
结果。

⑶模块调用关系
由主函数模块调用创建顺序表模块,排序模块与显示输出模块。

⑷流程图
2、详细设计
(1)、宏定义
#define MAXSIZE 15//用作示例的小顺序表的最大长度(2)、抽象数据类型定义
typedef struct
{
int key;//关键字域
int otherinfo;//其它域
}RedType;//记录类型
typedef struct
{
RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元int length;//顺序表长度
}SqList;//顺序表类型
(3)、操作算法程序实现:
void InPut(SqList &L)
{//输入数字,创建顺序表
int i;
printf("请输入10个数字:\n");
L.length=10;
for(i=1;i<=L.length;i++)
{
scanf("%d",&L.r[i].key);
}
}
void InsertSort(SqList &L)
{ //对顺序表L作直接插入排序(非递减)
int i,j;
for (i=2; i<=L. length; ++i)
if (L.r[i].key < L.r[i-1].key)
{ //将L.r[i]插入有序子表
L.r[0]=L.r[i]; //将L.r[i]复制为哨兵
for(j=i-1; L.r[0].key<L.r[j].key; --j ) L.r[j+1]=L.r[j]; //记录后移
L.r[j+1]=L.r[0]; //插入正确位置
}
}
int Partition(SqList &L,int low,int high)
{//交换顺序表L中子表r[low…high]的记录,枢轴记录到位,并返回其所在位置,
此时在它之前(后)的记录均不大(小)于它。

int pivotkey;
L.r[0].key=L.r[low].key;//用子表的第一个记录作枢轴记录
pivotkey=L.r[low].key;//枢轴记录关键字
while(low<high)//从表的两端交替地向中间扫描
{
while(low<high&&L.r[high].key>=pivotkey)
{
--high;//将比枢轴记录小的记录移到低端
}
L.r[low].key=L.r[high].key;
while(low<high&&L.r[low].key<=pivotkey)
{
++low;//将比枢轴记录大的记录移到高端
}
L.r[high].key=L.r[low].key;
}
L.r[low].key=L.r[0].key;//枢轴记录到位
return low;//返回枢轴位置
}
void QSort(SqList &L,int low,int high)
{//对顺序表L中的子序列L.r[low…high]作快速排序。

相关主题