当前位置:文档之家› 数据结构实验报告

数据结构实验报告

scanf("%d",&L.r[i].key);
QSort(L,1,L.length);
for (i=1;i<=L.length;i++)
printf("%d\n",L.r[i].key);
//cout<<"\b\t";//删除最后一个逗号
}
4、实验结果及分析
5、实验体会、问题讨论
通过本次试验,让我更深刻理解了快速排序法与其应用,因为快速排序是对冒泡排
if(!L.r) return 0;
=0;
return 1;
}
int Partition(SqList &L, int low, int high) { //算法10.6(b)
//交换顺序表L中子序列L.r[low..high]的记录,使枢轴记录到位,
//并返回其所在位置,此时,在它之前(后)的记录均不大(小)于它
L.r[low] = L.r[high]; //将比枢轴记录小的记录移到低端
while (low<high && L.r[low].key<=pivotkey) ++low;
L.r[high] = L.r[low]; //将比枢轴记录大的记录移到高端
}
L.r[low] = L.r[0]; //枢轴记录到位
淮北师范大学实验报告
姓名
张立寅
学号
20141201066
实验日期
2015.12.11
预习
(满分20分)
报告
(满分30分)
成绩
院别
计算机
年级
2014级
实验场地
A209
实验课程名称
数据结构试验
实验项目名称
实验五:快速排序
对于每一个实验项目,实验报告(含预习)一般应包含以下内容:第一部分——预习后的书面汇报。其主要内容应包含:*1、实验目的;*2、实验内容。第二部分——实验结果的书面汇报。其主要内容应包含:*3、实验源代码;*4、实验结果及分析(含实验测试输入数据,试验运行结果截图,用简洁的语言总结实验,汇报是否达到实验目的);*5、实验体会、问题讨论(谈体会或感想、提出建议或意见、讨论与实验有关的且自己感兴趣的问题);6、回答课后思考题(按指导教师的要求)。
typedef struct{
KeyType key;
}RedType;
typedef struct SqList{
RedType *r;
int length;
}SqList;
typedef int status;
status InitSqList(SqList &L)
{
L.r=(RedType*)malloc((MAX_SIZE+1)*sizeof(RedType)); //0空间空出来
[具体要求]
(1)需要用一维数组a来存储等待排序的序列;
(2)设置两个工作指针i和j;
(3)每次快速排序都以排序区域的首元素为基准(轴);
(4)程序用递归函数来实现。
3、实验源代码
#include <stdio.h>
#include <malloc.h>
#define MAX_SIZE 20
typedef int KeyType;
1、实验目的
1.理解排序稳定性含义,掌握各种排序算法的稳定性;
2.掌握各种内部排序的基本算法和特点;
3.掌握快速排序的排序过程,程序实现快速排序。
2、实验内容
掌握快速排序的算法程序实现排序过程。
具体算法可描述如下:
设初始序列为a1,a2,……,an,以序列中的某个元素ai为基准(轴),经调整后,使得ai左边的元素均小于ai,右边的均大于等于ai,而后对这两个子区再分别使用快速排序。
序的一种改进,所以在冒泡排序的原有基础上再学习快速排序就显得不是很困难。但
在上机的操作过场中,发现了自己平时疏忽的细节,以后的学习过程中要多加注意
教师签字:批改日期:
KeyType pivotkey;
L.r[0] = L.r[low]; //用子表的第一个记录作枢轴记录
pivotkey = L.r[low].key; //枢轴记录关键字
while (low<high) { //从表的两端交替地向中间扫描
while (low<high && L.r[high].key>=pivotkey) --high;
void main()
{
SqList L;
int l;//定义序列的长度
printf("请输入待排序的序列的长度:(不大于20)");
scanf("%d",&l);
InitSqList(L);
L.length=l;
printf("请输入待排序的序列的关键字:");
for(int i=1;i<=L.length;i++)
pivotloc = Partition(L, low, high); //将L.r[low..high]一分为二
QSort(L, low, pivotloc-1); //对低子表递归排序,pivotloc是枢轴位置
QSort(L, pivotloc+1, high); //对高子表递归排序
}
} // QSort
return low; //返回枢轴位置
} // Partition
void QSort(SqList &L, int low, int high) { //算法10.7
//对顺序表L中的子序列L.r[low..high]进行快速排序
int pivotloc;
if (low < high) { //长度大于1
相关主题