《数据结构》实验报告 

专    业  _____________

年    级  _____________

学    号  _____________

学生姓名  _____________

指导老师  _____________

华中师范大学信息管理系编

I  实验要求

1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。

2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。

3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。

4．上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。

II  实验内容

实验一    线性表

【实验目的】

1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。

2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。

3．熟练掌握线性表的综合应用问题。

【实验内容】

1．一个线性表有n个元素（n<MAXSIZE, MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。

    2. 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。

    要求：

①指定的值x由键盘输入；

②程序能处理空链表的情况。

    3．设有头结点的单链表，编程对表中的作一值只保留一个结点，删除其余值相同的结点。

要求：

①该算法用函数（非主函数）实现；

②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。

4．已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。

要求：

①该算法用函数Reverse(head,p)实现，其中head为表头指针，p指向要交换的结点；

②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。

5．设有一个单链表，编写能够完成下列功能的算法：

①找出最小值的结点，且打印该数值；

②若该数值是奇数，则将其与直接后继结点交换；

③若该数值是偶数，则将其直接后继结点删除。

要求：

编写主函数验证算法的正确性。

6．在一链表中，已知每个结点含有三个域：data、next和prior，其中prior域为空，设计一个算法，使每个结点的prior指向它的前驱结点，形成双向循环链表。

要求：

①建立一个结点中含有三个域的单链表；

②在主函数中调用此算法，构成双向循环链表；

③在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。

7．用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。

    要求：

①通讯录是按姓名项的字母顺序排列的；

    ②能查找通讯录中某人的信息；

提示：

可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为‘工作结点’，需从链表的首结点开始比较，如果‘工作结点’的数据比链中的‘当前结点’的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。

【实验报告】

实习时间：          实习地点：             实习机号：

实验二    堆栈与队列

【实验目的】

1．学习如何使用C语言实现堆栈与队列。

2．熟悉堆栈与队列的基本操作及应用。

【实验内容】

1．  现有一顺序循环队列，其结构描述为：

# define MAX 100

typedef struct

{ ElemType  queue[MaxQueueSize];

  int front;                // 队头指针

int count;               // 计数器

        }QueueType;

要求：

①设计队列的几种几种操作：初始化、进队、出队、取队头元素和判断队列是否非空。

②编写一个主函数进行测试。

2．已知Q是一个非空队列，S是一个空栈。编写算法实现：将队列Q中的所有元素逆置。

要求：

①调用堆栈和队列的操作函数实现该算法。

②编写一个主函数进行测试。

3．设计一个算法，将计算机产生的n个随机数分为奇数、偶数两组，并将它们分别压入两个栈中，然后在屏幕上输出。

4．编写一个程序，反映病人到医院看病排队看医生的情况。在病人排队过程中，主要重复两件事：

①病人到达诊室，将病历交给护士，排到等候队列中候诊。

②护士从等待队列中取出下一个病人的病历，该病人进入诊室就诊。

要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下：

①排队──输入排队病人的病历号，加入到病人排队队列中；

②就诊──病人排队队列中最前面的病人就诊，并将其从候诊队列中删除；

③查看排队──从队首到队尾列出所有的排队病人的病历号；

④不再排队，余下依次就诊──从队首到队尾列出所有的排队病人的病历号，并退出运行；

⑤下班──退出运行。

【实验报告】

实习时间：             实习地点：                       实习机号：

实验三    串

【实验目的】

1．掌握串的基本运算。

2．掌握有关串的比较、复制和转换等操作的实现。

3．熟悉串的有关应用问题。

【实验内容】

1．设计一个算法，统计输入字符串中各个不同字符出现的频度。设字符串中的合法字符为‘A’～‘Z’这26个字母和‘0’～‘9’这10个数字（串的存储结构自行选择）。

2．已知字符串S1中存放一段英文，写出算法format(S1,S2,S3,n),将其按给定的长度n格式化成两端对齐的字符串S2,其多余的字符送S3（即将字符串S1拆分成字符串S2和字符串S3，要求字符串S2长度为n且首尾字符不得为空格字符）。

3．输入一篇短文，统计其中所出现的单词的频率（单词间以空格隔开）。

4．采用动态顺序结构存储串，编写算法：求用户输入串S中出现的第一个最长重复子串的下标和长度。一个字符串中重复最长的部分，比如说有如下字符串：

abcdbcdbcb

对于这个字符串最长的重复子串为bcdbc。

【实验报告】

实习时间：          实习地点：            实习机号：

实验四    数组

【实验目的】

1．进一步熟悉关于数组的压缩存储的有关概念。

2．掌握数组在压缩存储下的有关运算。

【实验内容】

1．如果矩阵A中存在这样一个元素A[i][j]满足下列条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写算法计算m×n的矩阵A的所有马鞍点。

2．设矩阵A、B和C均为采用压缩存储方式存储的n阶上三角矩阵，矩阵元素为整数类型，要求：

①设计算法实现矩阵相加运算：C=A+B；

②设计算法实现矩阵相乘运算：C=A×B；

③在主函数中设定矩阵A和B，并调用该算法验证其正确性。

3．编写一个算法，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。

【实验报告】

实习时间：          实习地点：            实习机号：

实验五    二叉树

【实验目的】

1．理解和掌握二叉树的定义、性质、存储结构、遍历原理与实现方法。

1．  建立二叉树并对其进行简单操作。

2．  进一步熟悉二叉树的应用。

【实验内容】

1．  设计算法实现以下操作：

①建立一棵二叉树（二叉树中的结点的数据为字符型）；

②统计二叉树中的结点数；

③统计二叉树中叶子数；

④输出所有的叶子结点；

⑤输出所有从叶子结点到根结点的路径。

2．单词排序

试将一段英文中出现的单词按词典的顺序打印出来，同时应注明每个单词在该段文章中出现的次数。

提示：将一段英文中出现的单词按词典的顺序打印的过程，就是由一个无序序列构造为有序序列的过程，这个过程可以通过构造二叉排序树，并按中序遍历来实现。

3．编写一个算法，判断以二叉链表存储的二叉树中否为完全二叉树，并用主函数进行测试。

4．已知在以二叉链表存储的二叉树BT中，p和q指向二叉树中两个不同的结点，试编写一算法，求包含p和q所指结点的最小子树。

5．若二叉树以三叉链表作为其存储结构，编写一个不设堆栈进行中序遍历的非递归算法。

【实验报告】

实习时间：          实习地点：             实习机号：

实验六    查找与排序

【实验目的】

1．  进一步熟悉各种查找与排序的算法，并对各种算法的效率进行比较和测试。

【实验内容】

1． 排序算法比较。要求：

①调用函数int rand(void)产生100000个待排序的数据；

②测试下列各排序函数的机器实际执行时间：

a.直接插入排序；    b.希尔排序      c.选择排序

d.冒泡排序          e.堆排序        f.快速排序

g.归并排序          h.基数排序

2．编写一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后输出结果。要求用一个二叉树保存处理结果，字符串中的每个不同字符用树中结点描述，每个结点包含四个域：

字符

该字符出现的次数

指向ASCII码小于该字符的左子树的指针

指向ASCII码大于该字符的右子树的指针

3．编写判定给定的二叉树是否是二叉排序树的算法。并用主函数进行验证。

4．编写一个非递归的快速排序算法。并用主函数进行验证。

【实验报告】

实习时间：          实习地点：            实习机号：

实验七    综合练习

【实验目的】

1．在掌握基本概念的基础上，综合运用线性结构和树结构以及排序和查找算法进行复杂结构程序设计。

【实验内容】

1．试将一棵普通树转换成二叉树，同时转换而成的二叉树按前序、中序、后序进行遍历，并输出遍历后结点的序列。例如，下面左图是一棵普通树，用括号表示法表示为：A(BC(FG)DE)，右图是转换后的二叉树。

    提示：从分析输入的树串形式可知，左括号后面的字符为左括号前面字符的左子树，括号内的字符关系是兄弟，则转化为二叉树后，后面字符为其前一字符的右子树。所以，依据左右括号及字符间的关系，可以生成结点的左右子树。

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;

}