数据结构实验报告
武汉大学国际软件学院
实验报告
课程名称 数据结构--使用C++语言描述
专业年级 2013级软件工程二班
姓 名
学 号
协作者 无
实验学期 20##-2015 学年 1 学期
课堂时数 72
填写时间 20## 年 1 月 2 日
附件：
实验报告说明
1．实验项目名称：要用最简练的语言反映实验的内容。要求与实验指导书中相一致。
2．实验目的：目的要明确，要抓住重点，符合实验任务书中的要求。
3．实验环境：实验用的软硬件环境（配置）。
4．实验方案设计（思路、步骤和方法等）：这是实验报告极其重要的内容。包括概要设计、详细设计和核心算法说明及分析，系统开发工具等。应同时提交程序或设计电子版。
对于设计型和综合型实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。
对于创新型实验，还应注明其创新点、特色。
5．结论（结果）：即根据实验过程中所见到的现象和测得的数据，做出结论（可以将部分测试结果进行截屏）。
6．小结：对本次实验的心得体会，所遇到的问题及解决方法，其他思考和建议。
7．指导教师评语及成绩：指导教师依据学生的实际报告内容，用简练语言给出本次实验报告的评价和价值。
第二篇：数据结构实验报告——排序
20##级数据结构实验报告
实验名称： 实验四 排序
学生姓名：
班 级：
班内序号：
学 号：
日 期： 20##年12月6日
1．实验要求
a. 实验目的
通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。
b. 实验内容
使用简单数组实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序（选作）
7、归并排序（选作）
8、基数排序（选作）
9、其他
2. 程序分析
2.1 存储结构
存储结构:
顺序存储结构
示意图如下:
2.2 关键算法分析
核心算法思想：
1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。
2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读性增、结构更加优化。
关键算法思想描述和实现：
关键算法1：
实现七种算法的基本排序功能。
1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。
2、希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
3、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。
4、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。
5、选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。
6、堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。
7、归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。
C++实现：
参看源代码的七个排序函数。
关键算法2：
获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数QueryPerformanceCounter()用于得到高精度计时器的值。
C++实现：
long double Sort::GetNowTime(void)
{
LARGE_INTEGER litmp;
LONG64 QPart;
QueryPerformanceCounter(&litmp);
QPart=litmp.QuadPart;
return (long double)QPart;
}
关键算法3：
试图寻求最简短的代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。
采用以下三种方法实现：
① 使用函数指针数组，分别指向各排序函数的入口地址，然后在Statistics()函数中加以调用，使得排序函数运行在统计时间函数之间，这样使用一个for语句即可实现七种算法的一次性调用、时间统计、移动次数和比较次数统计。
C++实现：
void Statistics(Sort &obj,int i,int j)
{
obj.startTime=obj.GetNowTime();
(obj.*pFunction[i])(obj.pRandom1);
obj.endTime=obj.GetNowTime();
obj.runtime[i][j]=obj.endTime-obj.startTime;
}
② 使用两个数组实现乱序、顺序以及逆序数据的排序，大大节省了空间的消耗。基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。
C++实现：
请参看源代码。
③ 建立两个数组分别统计运行次数，再统一使用一个数组记录七种算法在三种不同数据情况下的移动次数和交换次数。在分别运行乱序、顺序和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零继续统计。
C++实现：
请参看源代码。
时间复杂度与空间复杂度：
理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示：
3. 程序运行结果
程序运行框图：
实际测试和分析：
实际运行结果如下：（其中随机产生的数据量为1000）
图一 加入了次数统计的运行结果
图二 没有加入次数统计的运行结果
作如下分析：
1、 多次运行之后统计，从乱序的时间消耗来看，基本符合理论分析。参看图一。
2、 由于加入了统计次数的代码，势必增加时间开销，这样统计出来的时间将有一定的误差。
假若比较次数和移动次数相差较多，则将产生较大的实验误差。故重新写了代码，没有加入比较次数和移动次数的比较的代码，运行结果如图二所示，均采用随机产生的1000个乱序数据进行排序。可以看出时间有所减少。因而图二更加接近实际。
3、本程序中的代码有的采用了递归的形式，如果考虑用栈来模拟的话，效率会有提升，所以运行时间还和代码的实现有关，代码本身只是描述了算法思想，并没有再进行编写方面的优化，因而还不能完全反映出每个算法的根本性能。
4. 总结
1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生器，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。因而采用了函数指针数组和统一的接口函数，采用二维数组存储移动次数和比较次数，调用精确的系统函数实现时间的统计。此外还添加了一些列优化，特别是函数封装的方法，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。
2、程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。
3、改进：本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。在实现类的封装的时候为了共享数据采用了友元函数的方式，考虑能否使用其他方式使得类的封装更加完善。
附录源码：
（包括三个cpp文件）
//Main.cpp
#include<iostream>
using namespace std;
#include"Sort.h"
#include<time.h>
#include<string.h>
static int (Sort::*pFunction[7])(long int [])={&Sort::InsertSort,&Sort::ShellSort,&Sort::BubbleSort,&Sort::QuickSort,&Sort::SelectSort,&Sort::HeapSort,&Sort::MergeSort};
char *funcName[7]={"1、插入排序:","2、希尔排序:","3、冒泡排序:","4、快速排序:","5、选择排序:","6、堆 排 序:","7、归并排序:"};
/*****************************统计时间函数*****************************/
void Statistics(Sort &obj,int i,int j)
{
obj.startTime=obj.GetNowTime();
(obj.*pFunction[i])(obj.pRandom1);
obj.endTime=obj.GetNowTime();
obj.runtime[i][j]=obj.endTime-obj.startTime;
}
/****************************主调函数*********************************/
int main(void)
{
cout<<"程序说明：\n1、默认产生10个随机数，如需加大数据量，请修改常量Max;\n2、默认打印排序的结果以显示算法正确与否，如果想不打印，请注释相关语句。\n\n";
Sort obj;
obj.CreateData();
memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));
int i(0),j(0);
/*************************乱序序列*********************************/
obj.SetTimesZero();
for(i=0;i<7;i++)
{
Statistics(obj,i,0);
cout<<funcName[i]<<"\n"; //如果不输出各排序结果，请注释掉此两行
obj.PrintArray(obj.pRandom1);
if(i!=6)
memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));
}
obj.RecordTimes(0);
/*************************顺序序列*********************************/
obj.SetTimesZero();
for( i=0;i<7;i++)
Statistics(obj,i,1);
obj.RecordTimes(2);
/*************************逆序序列*********************************/
obj.SetTimesZero();
for(i=1;i<=Max;i++)
obj.pRandom2[i]=obj.pRandom1[Max+1-i];
memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));
for(i=0;i<7;i++)
{
Statistics(obj,i,2);
memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));
}
obj.RecordTimes(4);
/************************统计排序数据******************************/
obj.PrintStatistics(funcName);
return 0;
}
//Sort.cpp
const int Max =10;
class Sort
{
public:
Sort();
~Sort();
void CreateData(void);
int InsertSort(long int []);
int ShellSort(long int []);
int BubbleSort(long int []);
int QuickSort(long int []);
int QuickSortRecursion(long int [], int ,int);
int QuickSortPatition(long int [], int , int );
int SelectSort(long int []);
int HeapSort(long int []);
void HeapSortSift(long int [], int , int );
int MergeSort(long int []);
void Merge(long int [],long int [], int , int , int );
void MergePass(long int [],long int [] , int );
long double GetNowTime(void);
void PrintArray(long int*);
void SetTimesZero(void);
void RecordTimes(int);
friend void Statistics(Sort &,int ,int);
void PrintStatistics(char *[]);
friend int main(void);
private:
long int *pRandom1;
long int *pRandom2;
long double runtime[7][3];
int comparetimes[7];
int movetimes[7];
int timestable[7][6];
long double startTime,endTime;
};
//Function.cpp
#include"Sort.h"
#include<iostream>
#include <stdlib.h>
#include <time.h>
#include<string.h>
#include<cstdio>
#include<windows.h>
#include<string>
#include<iomanip>
using namespace std;
/***********************************************************构造函数**********************************************************************/
Sort::Sort()
{
memset(timestable,0,sizeof(int)*7*6);
}
/***********************************************************构造数组**********************************************************************/
void Sort::CreateData(void)
{
pRandom1=new long int[Max+1];
pRandom2=new long int[Max+1];
srand((unsigned)time(NULL));
for(int i = 1; i <= Max;i++ )
pRandom2[i]=rand();
cout<<"随机乱序数组如下：\n"; //如果不输出原始数组，请注释掉此两行
PrintArray(pRandom2);
}
/********************************************************简单插入排序*******************************************************************/
int Sort::InsertSort(long int parray[])
{
int j=0;
for(int i =2; i <= Max;i++)
{
parray[0]=parray[i];
comparetimes[0]++;
for(j=i-1;parray[0]<parray[j];j--)
{
parray[j+1]=parray[j];
movetimes[0]++;
}
parray[j+1]=parray[0];
movetimes[0]+=2;
}
return 0;
}
/**********************************************************希尔排序***********************************************************************/
int Sort::ShellSort(long int parray[])
{
int j=0;
for(int d=Max/2;d>=1;d/=2)
{
for(int i=d+1;i<=Max;i++)
{
parray[0]=parray[i];
comparetimes[1]++;
for(j=i-d;j>0 && parray[0]<parray[j];j-=d)
{
parray[j+d]=parray[j];
movetimes[1]++;
}
parray[j+d]=parray[0];
movetimes[1]+=2;
}
}
return 0;
}
/**********************************************************冒泡排序***********************************************************************/
int Sort::BubbleSort(long int parray[])
{
int exchange=Max;
int bound,j;
while(exchange)
{
bound=exchange;
exchange=0;
for(j=1;j<bound;j++)
{
comparetimes[2]++;
if(parray[j]>parray[j+1])
{
parray[0]=parray[j];
parray[j]=parray[j+1];
parray[j+1]=parray[0];
exchange=j;
movetimes[2]+=3;
}
}
}
return 0;
}
/***********************************************************快速排序**********************************************************************/
int Sort::QuickSort(long int parray[])
{
QuickSortRecursion(parray,1, Max);
return 0;
}
int Sort::QuickSortRecursion(long int parray[], int first=1, int end=Max)
{
if (first<end)
{
int pivot=QuickSortPatition(parray, first, end);
QuickSortRecursion(parray, first, pivot-1);//左侧子序列排序
QuickSortRecursion(parray, pivot+1, end); //右侧子序列排序
}
return 0;
}
int Sort::QuickSortPatition(long int r[], int first, int end )
{
int i=first;
int j=end;
int temp;
while (i<j)
{
while (i<j && r[i]<= r[j])
{
j--;
comparetimes[3]++;
} //右侧扫描
if (i<j)
{
temp=r[i]; //将较小记录交换到前面
r[i]=r[j];
r[j]=temp;
i++;
movetimes[3]+=3;
}
while (i<j && r[i]<= r[j])
{
i++;
comparetimes[3]++;
} //左侧扫描
if (i<j)
{
temp=r[j];
r[j]=r[i];
r[i]=temp; //将较大记录交换到后面
j--;
movetimes[3]+=3;
}
}
return i; //i为轴值记录的最终位置
}
/***********************************************************选择排序**********************************************************************/
int Sort::SelectSort(long int parray[])
{
int i,j,index,temp;
for (i=1; i<Max; i++) //对n个记录进行n-1趟简单选择排序
{
index=i;
for (j=i+1; j<=Max; j++)
{
comparetimes[4]++; //在无序区中选取最小记录
if (parray[j]<parray[index])
index=j;
}
if (index!=i)
{
temp=parray[i];
parray[i]=parray[index];
parray[index]=temp;
movetimes[4]+=3;
}
}
return 0;
}
/*************************************************************堆排序***********************************************************************/
int Sort::HeapSort(long int parray[])
{
int i;
for (i=Max/2; i>=1; i--)
HeapSortSift(parray, i, Max) ;
for (i=1; i<Max; i++)
{
parray[0]=parray[Max-i+1];
parray[Max-i+1]=parray[1];
parray[1]=parray[0];
movetimes[5]+=3;
HeapSortSift(parray, 1, Max-i);
}
return 0;
}
void Sort::HeapSortSift(long int parray[], int k, int m)
{
int i,j;
i=k;
j=2*i; //置i为要筛的结点，j为i的左孩子
while (j<=m) //筛选还没有进行到叶子
{
if (j<m && parray[j]<parray[j+1])
{
j++;
comparetimes[5]++;
} //比较i的左右孩子，j为较大者
if (parray[i]>parray[j])
{
comparetimes[5]++;
break;
} //根结点已经大于左右孩子中的较大者
else
{
parray[0]=parray[i];
parray[i]=parray[j];
parray[j]=parray[0];
movetimes[5]+=3;
i=j;
j=2*i; //被筛结点位于原来结点j的位置
}
}
}
/************************************************************归并排序*********************************************************************/
int Sort::MergeSort(long int parray[])
{
long int r1[Max+1];
int h(1);
while (h<Max)
{
MergePass(parray, r1, h); //归并
h=2*h;
MergePass(r1, parray, h);
h=2*h;
}
return 0;
}
void Sort::Merge(long int parray[], long int r1[], int s, int m, int t) //一次归并
{
int i=s;
int j=m+1;
int k=s;
while (i<=m && j<=t)
{
comparetimes[6]++;
movetimes[6]++;
if (parray[i]<=parray[j])
{
r1[k++]=parray[i++];
}
else
r1[k++]=parray[j++];
}
if (i<=m)
while (i<=m)
{
r1[k++]=parray[i++];
movetimes[6]++;
}
else
while (j<=t)
{
r1[k++]=parray[j++];
movetimes[6]++;
}
}
void Sort::MergePass(long int parray[], long int r1[], int h) //一趟归并
{
int i(1),k;
while (i<=Max-2*h+1)
{
Merge(parray, r1, i, i+h-1, i+2*h-1);
i+=2*h;
}
if (i<Max-h+1)
Merge(parray, r1, i, i+h-1, Max);
else for (k=i; k<=Max; k++)
{
r1[k]=parray[k];
movetimes[6]++;
}
}
/************************************************************获取当前时间**********************************************************************/
long double Sort::GetNowTime(void)
{
LARGE_INTEGER litmp;
LONG64 QPart;
QueryPerformanceCounter(&litmp);
QPart=litmp.QuadPart;
return (long double)QPart;
}
/**************************************************************打印数组************************************************************************/
void Sort::PrintArray(long int *pRandom)
{
for(int j=1;j<=Max;j++)
cout<<pRandom[j]<<'\t';
cout<<endl;
}
/************************************************************数组置零函数***********************************************************************/
void Sort::SetTimesZero()
{
memset(comparetimes,0,sizeof(int)*7);
memset(movetimes,0,sizeof(int)*7);
}
void Sort::RecordTimes(int j)
{
for(int i=0;i<7;i++)
{
timestable[i][j]=movetimes[i];
timestable[i][j+1]=comparetimes[i];
}
}
/************************************************************输出排序数据***********************************************************************/
void Sort::PrintStatistics(char* funcname[])
{
int i(0),j(0);
cout<<" 排序方法\t"<<"乱序耗时(μs) "<<"顺序耗时(μs) "<<"逆序耗时(μs)"<<endl;
for(i=0;i<7;i++)
cout<<funcname[i]<<'\t'<<setw(8)<<setiosflags(ios::fixed)<<setprecision(0)
<<setiosflags(ios::left)<<runtime[i][0]<<'\t'<<setw(8)<<runtime[i][1]
<<'\t'<<setw(8)<<runtime[i][2]<<endl;
cout<<'\n'<<"\t\t\t★★★移动次数统计表★★★\n\n";
cout<<" 排序方法\t"<<" 乱序序列\t"<<" 顺序序列\t"<<" 逆序序列\t"<<endl;
for(i=0;i<7;i++)
{
cout<<funcname[i];
for(j=0;j<6;j+=2)
cout<<'\t'<<'\t'<<timestable[i][j];
cout<<endl;
}
cout<<'\n'<<"\t\t\t★★★比较次数统计表★★★\n\n";
cout<<" 排序方法\t"<<" 乱序序列\t"<<" 顺序序列\t"<<" 逆序序列\t"<<endl;
for(i=0;i<7;i++)
{
cout<<funcname[i];
for(j=1;j<6;j+=2)
cout<<'\t'<<'\t'<<timestable[i][j];
cout<<endl;
}
}
/*************************************************************类的析构函数**********************************************************************/
Sort::~Sort()
{
delete pRandom1;
delete pRandom2;
}
-
数据结构实验报告
实验报告实验课程：数据结构实验项目：实验专业：计算机科学与技术姓名：**学号：***指导教师：**实验时间：20**-12-7重庆…
-
数据结构实验报告(C语言)(强力推荐)
数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查…
-
数据结构实验———图实验报告
数据结构实验报告目的要求掌握图的存储思想及其存储实现掌握图的深度广度优先遍历算法思想及其程序实现掌握图的常见应用算法的思想及其程序…
-
数据结构实验报告格式
数据结构实验报告格式实验11顺序表的基本操作一实验目的1掌握使用VC上机调试线性表的基本方法2掌握线性表的基本操作插入删除查找等运…
-
数据结构实验报告全集
数据结构实验报告全集实验一线性表基本操作和简单程序1实验目的1掌握使用VisualC60上机调试程序的基本方法2掌握线性表的基本操…
-
20xx数据结构实验报告(范文)
报告格式说明数据结构实验,实验成绩占该科成绩20%。实验报告抄袭者，一经发现实验成绩为0；实验报告不交者，该科成绩为0。参考资料：…
-
数据结构实验报告格式
实验报告格式一实验目的二实验内容实验内容包括1程序要求2根据程序要求写出程序源程序两部分内容三程序调试过程记录四实验结果实验结果包…
-
数据结构实验报告
数据结构实验报告实验名称数据结构与算法专业班级数学与应用数学1201班学号1304120xx6姓名谢伟指导老师陈明0目录1前言22…
-
数据结构实验报告
本科生实验报告二姓名学院专业班级实验课程名称数据结构实验日期20xx年5月25日指导教师及职称实验成绩开课时间20xx20xx学年…
-
数据结构实验报告实验1
数据结构实验报告湖南师范大学工程与设计学院数据结构实验报告姓名王新建年级20xx级专业应用电子技术教育学号20xx180320任课…
-
华中科技大学·计算机13级·数据结构实验报告
课程设计报告课程名称专业班级CS1308学号姓名陈劲龙指导教师报告日期计算机科学与技术目录实验一基于顺序结构的线性表实现11问题描…