(完整word版)数据结构(C语言版)实验报告(内部排序算法比较).doc

(完整word版)数据结构(C语言版)实验报告(内部排序算法比较)
(完整word版)数据结构(C语言版)实验报告(内部排序算法比较)
(完整word版)数据结构(C语言版)实验报告(内部排序算法比较)
《数据结构与算法》实验报告

需求分析
问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：
（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：
二．概要设计
程序所需的抽象数据类型的定义：
typedefintBOOL;//说明BOOL是int的别名
typedefstructStudentData{intnum;//存放关键字
}
Data;typedefstructLinkList{intLength;//数组长度
DataRecord[MAXSIZE];//用数组存放所有的随机数
}LinkListintRandArray[MAXSIZE];//定义长度为MAXSIZE的随机数组
voidRandomNum()//随机生成函数
voidInitLinkList(LinkList*L)//初始化链表
BOOLLT(inti,intj,int*CmpNum)//比较i和j的大小
voidDisplay(LinkList*L)//显示输出函数
voidShellSort(LinkList*L,intdlta[],intt,int*CmpNum,int*ChgNum)//希尔排序
voidQuickSort(LinkList*L,int*CmpNum,int*ChgNum)//快速排序
voidHeapSort(LinkList*L,int*CmpNum,int*ChgNum)//堆排序
voidBubbleSort(LinkList*L,int*CmpNum,int*ChgNum)//冒泡排序
voidSelSort(LinkList*L,int*CmpNum,int*ChgNum)//选择排序
voidCompare(LinkList*L,int*CmpNum,int*ChgNum)//比较所有排序
2.各程序模块之间的层次（调用）关系：

详细设计
typedefintBOOL;//定义标识符关键字BOOL别名为
inttypedefstructStudentData//记录数据类型
{
intnum;//定义关键字类型
}Data;//排序的记录数据类型定义
typedefstructLinkList//记录线性表
{
intLength;//定义表长
DataRecord[MAXSIZE];//表长记录最大值
}LinkList;//排序的记录线性表类型定义
intRandArray[MAXSIZE];//定义随机数组类型及最大值
/******************随机生成函数********************/
voidRandomNum()
{
inti;srand((int)time(NULL));//用伪随机数程序产生伪随机数
for(i=0;i小于MAXSIZE;i++)RandArray[i]<=(int)rand();返回;
}
/*****************初始化链表**********************/
voidInitLinkList(LinkList*L)//初始化链表
{
inti;
memset(L,0,sizeof(LinkList));
RandomNum();
for(i=0;i小于<MAXSIZE;i++)
L->Record[i].num<=RandArray[i];L->Length<=i;
}
BOOLLT(inti,intj,int*CmpNum)
{
(*CmpNum)++;若i<j)则返回TRUE;否则返回FALSE;
}
voidDisplay(LinkList*L)
{
FILE*f;//定义一个文件指针finti;
若打开文件的指令不为空则//通过文件指针f打开文件为条件判断
{//是否应该打开文件输出“can'topenfile”;exit(0);}
for(i=0;i小于L->Length;i++)
fprintf(f,"%d\n",L->Record[i].num);
通过文件指针