北理工数据结构实验报告4(20211112155046).pdfVIP

《数据结构与算法设计》 实验报告 ——实验四 学院：自动化学院 班级： ____ 学号： __ 姓名： ____ ____ 一、实验目的 1、熟悉 VC 环境，学习使用 C 语言实现链表的存储结构。 2、通过编程、上机调试，进一步理解线性表、链表、环表的基本概念。 3、锻炼动手编程，独立思考的能力。 二、实验内容 从键盘输入 10 个数，编程实现分别用插入排序、交换排序、选择排序算法 进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为实现上述程序功能，应用线性表寄存数字序列。为此，需要线性表的抽象 数据结构。 (1) 、线性表的抽象数据类型定义为： ADT SqList{ 数据对象： D= { a |a ElemSet,i 1,2, , n, n 0} i i 数据关系： R1={ ai 1 ,ai | ai 1, ai D, i 1,2, ,n} 基本操作： CreateList(L) 操作结果：构造一个线性表 L 。 ShowList(L) 初始条件：线性表 L 已存在。 操作结果：按顺序在屏幕上输出 L 的数据元素。 InsertSort(L) 初始条件：线性表 L 已存在。 操作结果：对 L 的数据元素进行插入排序。 QuickSort(L) 初始条件：线性表 L 已存在。 操作结果：对 L 的数据元素进行快速排序。 SelectSort(L) 初始条件：线性表 L 已存在。 操作结果：对 L 的数据元素进行选择排序。 }ADT SqList (2)、宏定义 #define MAXSIZE 10 #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 (3)、主程序流程 主程序首先调用 CreateList(l1) 函数创建顺序表 l1 。 随后调用 InsertSort(l1)、QuickSort(l2) 、SelectSort(l3)函数计算三种排序结果， 并调用相应的 ShowList() 函数显示排序结果。 (4)、模块调用关系： 由主函数模块调用创建模块，显示模块与计算模块。 (5)、流程图 开始 创建线性表 排序 输出结果 结束 2、详细设计 (1)、数据类型设计 typedef int Status; typedef int ElemType; // 定义数据元素类型 typedef struct{ ElemType r[MAXSIZE+1]; int length;