《数据结构与算法设计》
实验报告
——实验四
学院:
班级: 学号: 姓名:
一、实验目的
1. 2. 3. 4.
通过实验实践、巩固线性表的相关操作; 熟悉VC环境,加强编程、调试的练习; 用C语言实现线性表的抽象数据类型,实现线性表构造、插入、取数据等基本操作; 理论知识与实际问题相结合,利用上述基本操作实现三种排序并输出。
二、实验内容
从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。
三、程序设计 1、概要设计
为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。 (1)抽象数据类型: ADT SqList{ 数据对象:D={ai|ai?ElemSet,i?1,2,?,n,n?0}
?|ai?1,ai?D,i?1,2,?,n}
数据关系:R1={?ai?1,ai 基本操作:
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;
北京理工大学《数据结构与算法设计》实验报告实验四
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)