数据结构与算法-排序资料.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(请输入元素个数