数据结构与算法排序资料.docx
《数据结构与算法排序资料.docx》由会员分享，可在线阅读，更多相关《数据结构与算法排序资料.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构与算法排序资料
《数据结构与算法》实验报告
班级学号
姓名
实验周次
实验日期
xxxxx
xxxxxx
xxxxxx
2015年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"
#defineMAX50
//顺序表结构体
typedefstruct
{
ints[MAX];//存放一批随机整数，数组大小MAX不能扩充
intlength;//当前表中元素的个数
}SeqList;
//功能菜单
voidmenu（）
{
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;
//返回整个顺序表的（起始）地址
returnp;
}
/*随机产生一批整数到线性表中*/
voidrandGen（SeqList*p）
{
intnum,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"）;
}
/*手动输入一批整数到线性表中*/
voidmanInput（SeqList*p）
{
intnum,i;
printf（"请输入元素个数（<=%d）：
\n",MAX-1）;
scanf（"%d",&num）;
printf（"请输入%d个整数：
\n",num）;
if（num<=MAX-1）
{
//输入num个整数存入顺序表中（从1号单元开始存放，0号单元留作“哨兵”）
for（i=1;i<=num;i++）
scanf（"%d",&（p->s[i]））;
p->length=num;
printf（"顺序表中已成功输入%d个整数!
\n",num）;
}
else
printf（"顺序表空间不够，请重新输入元素个数!
\n"）;
}
/*将顺序表中现有元素打乱为随机排列*/
voidrandomizeList（SeqList*p）
{
inti,selectLoc,tmp;
//借助选择法排序的思想，每次从尚未挑选的序列中随机挑选一个元素，
//将随机选中的元素交换到尚未选中元素序列的最前面或最后面。
for（i=1;ilength;i++）
{
//产生一个属于区间[i,p->length]的随机数selectLoc
selectLoc=i+（int）（（p->length-i）*rand（）/（RAND_MAX+1.0））;
if（selectLoc!
=i）
{
tmp=p->s[i];
p->s[i]=p->s[selectLoc];
p->s[selectLoc]=tmp;
}
}
//反过来再来一遍
for（i=p->length;i>1;i--）
{
//产生一个属于区间[0，i]的随机数selectLoc
selectLoc=1+（int）（i*rand（）/（RAND_MAX+1.0））;
if（selectLoc!
=i）
{
tmp=p->s[i];
p->s[i]=p->s[selectLoc];
p->s[selectLoc]=tmp;
}
}
printf（"顺序表中的元素已经重新随机排列!
\n"）;
}
//快速排序——划分函数
intPartition（intR[],intlow,inthigh）
{
//对记录子序列R[low...high]进行一趟快速排序，并返回枢轴记录所在位置
intpivotkey;
R[0]=R[low];
pivotkey=R[low];
while（low{
while（low=pivotkey）
--high;
if（lowR[low++]=R[high];//将比枢轴记录小的记录移到低端
while（low++low;
if（lowR[high--]=R[low];//将比枢轴记录大的记录移到高端
}
R[low]=R[0];
returnlow;//最后返回枢轴的位置（下标）
}
//快速排序——递归函数
voidQSort（intR[],ints,intt）
{
//对记录R[s...t]进行快速排序
intpivotloc;
if（s{
pivotloc=Partition（R,s,t）;//对R[s...t]进行一次划分，并返回枢轴的位置
QSort（R,s,pivotloc-1）;
QSort（R,pivotloc+1,t）;
}
}
/*快速排序的主调函数*/
voidquickSort（SeqList*p）
{
//对顺序表P进行快速排序
QSort（p->s,1,p->length）;
printf（"已采用快速排序算法成功排序!
\n"）;
}
//一趟希尔插入排序（实质为直接插入排序的变形）
voidshellInsert（SeqList*p,intdk）
{
inti,j;
for（i=dk+1;i<=p->length;++i）
if（p->s[i]s[i-dk]）
{
p->s[0]=p->s[i];//设置插入排序的“哨兵”
for（j=i-dk;j>0&&p->s[0]s[j];j-=dk）
p->s[j+dk]=p->s[j];
p->s[j+dk]=p->s[0];
}
}
/*希尔排序（缩小增量排序），假设增量设置为5，3，1*/
voidshellSort（SeqList*p,intdlta[],intt）
{
intk;
//按增量序列dlta[0..t-1]对顺序表中的元素作希尔排序
for（k=0;kshellInsert（p,dlta[k]）;
printf（"已采用希尔排序算法成功排序!
\n"）;
}
//堆排序——将p->s[m..n]区间元素重新调整为堆的函数
voidheapAdjust（SeqList*p,intm,intn）
{
//使得p->s[m...n]成为大堆
intj,rc;
rc=p->s[m];
for（j=2*m;j<=n;j*=2）
{
if（js[j]s[j+1]）
++j;
if（rc>=p->s[j]）break;
p->s[m]=p->s[j];
m=j;
}
p->s[m]=rc;
}
/*堆排序*/
voidheapSort（SeqList*p）
{
//对顺序表p进行堆排序
intrc,i;
for（i=p->length/2;i>0;--i）
heapAdjust（p,i,p->length）;
for（i=p->length;i>1;--i）
{
rc=p->s[1];
p->s[1]=p->s[i];
p->s[i]=rc;
heapAdjust（p,1,i-1）;
}
printf（"已采用堆排序算法成功排序!
\n"）;
}
//归并排序——合并有序表
//将有序的SR[1..m]和SR[m+1..n]归并为有序的TR[i..n]
voidMerge（intSR[],intTR[],inti,intm,intn）
{
//将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n]
intk,j;
for（j=m+1,k=i;i<=m&&j<=n;++k）//将SR中记录由小到大的并入TR
{
if（SR[i]<=SR[j]）
TR[k]=SR[i++];
elseTR[k]=SR[j++];
}
while（i<=m）TR[k++]=SR[i++];//将剩余的SR[i...m]复制到TR
while（j<=n）TR[k++]=SR[j++];//将剩余的SR[j...n]复制到TR
}
//归并排序——递归函数部分
//将SR[]中的数据借助辅助空间TR2排序后存入TR1[]中。
voidMsort（intSR[],intTR2[],intTR1[],ints,intt）
{
//对SR[s...t]进行归并排序，排序后的记录存入TR1[s...t]
voidMsort2（intSR[],intTR1[],ints,intt）;
Msort2（SR,TR1,s,t）;
}
voidMsort2（intSR[],intTR1[],ints,intt）
{
intm;
int*TR3=（int*）malloc（（t+1）*sizeof（int））;
if（s==t）TR1[s]=SR[s];
else
{
m=（s+t）/2;//将SR[s...t]平分为SR[s...m]和SR[m+1...t]
Msort2（SR,TR3,s,m）;
Msort2（SR,TR3,m+1,t）;
Merge（TR3,TR1,s,m,t）;
}
}
/*归并排序——主调函数*/
voidmergeSort（SeqList*p）
{
//开辟辅助空间
int*auxSpa=（int*）malloc（（p->length+1）*sizeof（int））;
//调用递归函数作归并排序
Msort（p->s,auxSpa,p->s,1,p->length）;
//释放辅助空间
free（auxSpa）;
printf（"已采用归并排序算法成功排序!
\n"）;
}
/*显示表中所有数据*/
voidshowAll（SeqList*p）
{
inti;
if（p->length>0）
{
printf（"当前表中的元素个数为%d，依次如下：
\n",p->length）;
for（i=1;i<=p->length;i++）
printf（"%d",p->s[i]）;
printf（"\n"）;
}
else
printf（"当前顺序表为空!
\n"）;
}
voidmain（）
{
intchoice=-1;
SeqList*plist;
intincArr[]={5,3,1};//将希尔排序的增量设置为5，3，1
plist=init（）;
while
（1）
{
menu（）;
fflush（stdin）;
printf（"\t请选择一个菜单项：
"）;
scanf（"%d",&choice）;
switch（choice）
{
case1:
//随机产生一组整数放入表中
randGen（plist）;
showAll（plist）;
break;
case2:
//手动输入一批整数放入表中
manInput（plist）;
showAll（plist）;
break;
case3:
//将现有表中数据随机化排列
randomizeList（plist）;
showAll（plist）;
break;
case4:
//快速排序
quickSort（plist）;
showAll（plist）;
break;
case5:
//希尔排序（增量为3个，依次为5，3，1）
shellSort（plist,incArr,3）;
showAll（plist）;
break;
case6:
//堆排序
heapSort（plist）;
showAll（plist）;
break;
case7:
//归并排序
mergeSort（plist）;
showAll（plist）;
break;
case8:
//按顺序显示表中所有数据
showAll（plist）;
break;
case0:
exit（0）;
break;
default:
printf（"\t您输入的菜单项不存在，请重新选择!
\n"）;
}
choice=-1;//表示未选择菜单项或者菜单项选择错误
}
}
升级会员 