数据结构实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告答案”。
实验报告4 排序
一、实验目的1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
二、实验要求及内容
要求编写的程序所能实现的功能包括：
1、从键盘输入要排序的一组元素的总个数
2、从键盘依次输入要排序的元素值
3、对输入的元素进行快速排序
4、对输入的元素进行折半插入排序
三、实验代码及相关注释
#include using namespace std;#include “malloc.h”
typedef struct { int key;}RedType;
typedef struct { RedType r[100];int length;}SqList;
//1 快速排序的结构体
typedef struct {
int data[100];
int last;}Sequenlist;//2 折半插入排序的结构体
int Partition(SqList &L, int low, int high)
//1 寻找基准
{
L.r[0]=L.r[low];//子表的第一个记录作基准对象
int pivotkey = L.r[low].key;//基准对象关键字 while(low
while(low= pivotkey)--high;
L.r[low] = L.r[high];//小于基准对象的移到区间的左侧
while(low
L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 }
L.r[low] = L.r[0];return low;}
void QuickSort(SqList &L, int low, int high)
//1 快速排序 { //在序列low-high中递归地进行快速排序
if(low
{
int pivotloc= Partition(L, low, high);
//寻找基准
QuickSort(L, low, pivotloc-1);//对左序列同样递归处理
QuickSort(L, pivotloc+1, high);//对右序列同样递归处理
} }
Sequenlist *Sqlset()
//2 输入要折半插入排序的一组元素
{
Sequenlist *L;
int i;
L=(Sequenlist *)malloc(sizeof(Sequenlist));
L->last=0;
cout
cin>>i;
cout
cout
if(i>0)
{
for(L->last=1;L->lastlast++)
cin>>L->data[L->last];
L->last--;
}
return(L);}
middlesort(Sequenlist *L)
//2 折半插入排序 { int i,j,low,high,mid;for(i=1;ilast;i++){
L->data[0]=L->data[i];
low=1;
high=i-1;
while(low
{
mid=(low+high)/2;
if(L->data[0]data[mid])
high=mid-1;//插入点在前半区
else
low=mid+1;//插入点在后半区
}
for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移
L->data[high+1]=L->data[0];//插入 } return 0;}
int main(){ gg: cout>m;cout
if(m==1){ SqList L;int n;cout>n;cout
cin>>L.r[i].key;
} cout
QuickSort(L,1,L.length);
for(int j=1;j
{
cout
}
cout
cout
}
if(m==2){
Sequenlist *L;
int i;
L=Sqlset();
cout
middlesort(L);
cout
for(i=1;ilast;i++)
{
coutdata[i]
}
cout
cout
goto gg;}
if(m==3){
exit(0);
cout
四、重要函数功能说明
1、Sequenlist *Sqlset()
输入要折半插入排序的一组元素
2、int Partition(SqList &L, int low, int high)
寻找快速排序的基准
3、void QuickSort(SqList &L, int low, int high)
快速排序
4、middlesort(Sequenlist *L)
折半插入排序
五、程序运行结果
下图仅为分别排序一次，可多次排序，后面有相关截图：
六、实验中遇到的问题、解决及体会
1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。
运行程序错误截图：
2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。
修改程序前两个运行结果截图
（两个程序，调试运行两次，每次只能进行一次排序）
1、快速排序程序运行结果截图：
2、折半插入排序程序结果截图：
程序重要模块修改截图：
修改程序后运行截图：
（一个程序，调试运行一次，可多次进行不同序列的不同排序）
刀豆文库小编为你整合推荐8篇数据结构实验报告，也许这些就是您需要的文章，但愿刀豆文库能带给您一些学习、工作上的帮助。......
注意：实验结束后提交一份实验报告电子文档电子文档命名为“学号+姓名”，如：E01214058宋思怡《数据结构》实验报告（一）学号：姓名：专业年级：实验名称：线性表实验日期：2014年4月14日实验......
数据结构实验报告想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是本站小编给大家整理收集的数据结构实验报告，供大家阅读参考。数据结构实验报告1一、......
数据结构实验报告（精选16篇）由网友“coco2008”投稿提供，下面是小编为大家推荐的数据结构实验报告，欢迎大家分享。篇1：数据结构实验报告 一、实验目的及要求1)掌握栈和队列这两种......
天 津 科 技 大 学14学年—15学年第 2 学期 数据结构实验任务书专业名称： 计算机科学与技术 实验学时： 4 课程名称：数据结构 任课教师： 史绍强 实验题目：图的最短路径算法的实现......
