数据结构与算法-排序讲解.doc
文本预览下载声明
实验02-排序 PAGE \* MERGEFORMAT12
《数据结构与算法》实验报告
班级学号姓 名实验周次实验日期xxxxxxxxxxxxxxxxx2015年10月 28 日实验02：排序
一、实验目的
1．掌握各种常用排序方法的特点及其存储的方式。
2．掌握各种排序算法的要求、方法和过程。
3．了解各种排序算法效率的分析和计算方法。
二、实验内容
以Sort01（ReferenceParameter）.cpp或者Sort02（PointerParameter）.cpp为基础，实现如图2-1程序界面所示的常用排序算法。
注意：功能4（快速排序）、功能6（堆排序）和功能7（归并排序）是需要完成的部分；功能5（希尔排序）因为本学期采用的课本上没有提及，所以直接将答案给出了，大家只需看懂理解即可，其它和排序无关的功能项均已给出实现代码，大家无需更改。
三、实验要求
1、Sort01（ReferenceParameter）.cpp和Sort02（PointerParameter）.cpp选做其中一题即可（两题代码的思路完全一致，只有实现时参数传递方式的差别）。
2、演示程序SortDemo.exe中的所有排序均是升序排列，但完成本实验时，学号为单号的同学：排序时要求升序排列；学号为双号的：排序时要求降序排列。
3、实验报告电子稿和打印稿及其它提交方面的要求同实验01。
四、运行结果
图2-1 随机产生一批整数并快速排序
图2-2 随机排列表中元素并希尔排序
图2-3 随机排列表中元素并希尔排序
图2-4 随机排列表中元素并归并排序
五、参考程序
#include stdio.h
#include stdlib.h
#include time.h
#define MAX 50
// 顺序表结构体
typedef struct
{
int s[MAX]; // 存放一批随机整数，数组大小MAX不能扩充
int length; // 当前表中元素的个数
} SeqList;
// 功能菜单
void menu()
{
printf(\n\t*************排序*************\n);
printf(\t* 1 随机产生一批整数 *\n);
printf(\t* 2 手动输入一批整数 *\n);
printf(\t* 3 将表中数据随机化 *\n);
printf(\t* 4 快速排序 *\n);
printf(\t* 5 希尔排序 *\n);
printf(\t* 6 堆排序 *\n);
printf(\t* 7 归并排序 *\n);
printf(\t* 8 依次显示表中所有数据 *\n);
printf(\t* 0 退出程序 *\n);
printf(\t************************************\n);
}
/* 初始化一个空的顺序表 */
SeqList *init()
{
// 开辟顺序表空间
SeqList *p=(SeqList *)malloc(sizeof(SeqList));
// 设置顺序表的初始长度为0
p-length=0;
// 返回整个顺序表的（起始）地址
return p;
}
/* 随机产生一批整数到线性表中 */
void randGen(SeqList *p)
{
int num, i;
printf(请输入元素个数（=%d）：\n, MAX-1);
scanf(%d, num);
srand((int)time(0));
if(num = MAX)
{
// 随机产生num个整数存入顺序表中（从1号单元开始存放，0号单元留作“哨兵”）
for(i=1; i=num; i++)
p-s[i]=1+(int)(100.0*rand()/(RAND_MAX+1.0));
p-length=num;
printf(顺序表中已成功放入%d个整数!\n, num);
}
else
printf(顺序表空间不够，请重新输入元素个数!\n);
}
/* 手动输入一批整数到线性表中 */
void manInput(SeqList *p)
{
int num, i;
printf(请输入元素个数（=
显示全部