北理工数据结构实验4.doc
文本预览下载声明
《数据结构与算法设计》
实验报告
——实验四
学院：
班级：
学号：
姓名：
一、实验目的
通过实验实践、巩固的相关操作；
VC环境，编程、调试的；
C语言，实现、取数据等基本操作；
与实际相结合，上述基本操作实现。
从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。
三、程序设计
1、概要设计
为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。
(1)抽象数据类型：
ADT SqList{
数据对象：D=
数据关系：R1=
基本操作：
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].keyL.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(lowhigh)//从表的两端交替地向中间扫描
{
while(lowhighL.r[high].key=pivotkey)
{
--high;//将比枢轴记录小的记录移到低端
}
L.r[low].key=L.r[high].key;
while(lowhighL.r[low].key=pivotkey)
{
++low;//将比枢轴记录大的记录移到高端
}
L.r[high].key
显示全部