2024年4月30日发(作者：)

《数据结构与算法》实验报告

一、 需求分析

问题描述：

在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概

执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

基本要求：

（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希

尔排序、堆排序。

（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作

比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。

数据测试：

二．概要设计

1. 程序所需的抽象数据类型的定义：

typedef int BOOL; //说明BOOL是int的别名

typedef struct StudentData { int num; //存放关键字

}

Data; typedef struct LinkList { int Length; //数组长度

Data Record[MAXSIZE]; //用数组存放所有的随机数

} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组

void RandomNum() //随机生成函数

void InitLinkList(LinkList* L) //初始化链表

BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小

void Display(LinkList* L) //显示输出函数

void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum)

//希尔排序

void QuickSort (LinkList* L, int* CmpNum, int* ChgNum)

//快速排序

void HeapSort (LinkList* L, int* CmpNum, int* ChgNum)

//堆排序

void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum)

//冒泡排序

void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //

选择排序

void Compare(LinkList* L,int* CmpNum, int* ChgNum) //

比较所有排序

2 .各程序模块之间的层次（调用）关系：

二、 详细设计

typedef int BOOL; //定义标识符关键字BOOL别名为

int typedef struct StudentData //记录数据类型

{

int num; //定义关键字类型

}Data; //排序的记录数据类型定义

typedef struct LinkList //记录线性表

{

int Length; //定义表长

Data Record[MAXSIZE]; //表长记录最大值

}LinkList; //排序的记录线性表类型定义

int RandArray[MAXSIZE]; //定义随机数组类型及最大值