数据结构试验哈希表.doc

数据结构试验哈希表优质资料
(可以直接使用，可编辑 优质资料，欢迎下载）
第10章实验
实验名称：考试日程安排与成绩统计
实验类型：综合性性实验
班级：20210611
学号：2021061118
姓名：郭鑫

1. 问题描述
①问题描述
l 现要安排考试的考表（即考试日程表），假设共有10个班的学生，要安排10门必修课程的考试，必修课程是以班级来确定的，每个班各有3门必修课，因此各班的考试科目是不相同的；安排考表的原则是：相同课程采用统一的试卷，因此同一门课程的考试必须在相同时间进行，同一个班所修的科目必须安排在不同的时间进行考试，以避免考试时间的冲突。并要求全部考试的日程尽可能短。
l 要求对考试结果做统计和排序。假设分别以编号0,1,2,3,4,5,6,7,8,9代表10门要考试的课程，以B1，B2，B3，B4，B5，B6，B7，B8，B9，B10代表10个班，每个人的信息包括学号、姓名、班级、各门考试课程成绩、三门课程总成绩，每个班的学生人数自行设定。要求设计一个简单的考试成绩的查询统计系统实现以下功能：
² 显示学生考试情况-按考试总分从高到底输出全体学生的信息。-按照从B1到B10的班级顺序，分班级按照考试总分从高到底的顺序输出各班学生的信息。-输出指定班的学生考试成绩信息。
² 统计学生考试成绩-按总成绩统计出90分以上、80~89分、70~79分、60~69分、60分以下各分数段的人数，并按总分从高到低分段输出。-根据指定的某们课程的成绩，统计出上述各分数段的人数，并按分数从高到低分段输出。-统计并输出指定班级中总成绩或某一门课成绩的各分数段人数和每个人具体的信息。
² 查找学生成绩-查找总分或某一门课程成绩的指定分数段的人数及学生的详细信息。-查找指定班级中总分或某一门课程成绩属于某分数段的学生详细信息。-查找指定学生（例如给定学号）的具体信息，包括：姓名、班级、各科分数、总分数等。
②求解方法说明
l 考试日程安排问题。
² 该问题实际上是对若干元素进行子集划分的问题，要求所划分的每个子集中的元素没有“考试冲突”关系。
² 假设各个班的考试课程分别为：(1,4,8),(1,3,7),(8,2,4),(1,0,5),(2,6,9),(3,0,8),(4,5,9),(2,9,7),(6,0,3),(5,6,9)。根据题中考试安排原则，各个班要进行的考试课程可以抽象为“考试冲突关系”，归纳各个班的考试课程可以整理得到考试冲突关系：R={(1,4),(1,8),(4,8),(1,3),(1,7),(3,7),(8,2),(2,4),(1,0),(1,5),(0,5),(2,6),(2,9),(6,9),(3,0),(0,8),(3,8),(4,5),(5,9),(4,5),(2,7),(9,7),(6,0),(6,3),(5,6)}。显然，“考试冲突”关系R的每个有序对中的两门课程不能安排在同一时间考试，据此可以将10门课划分为若干个考试时间没有冲突的子集，并且使考场的场次尽量少，使得整个考试时间尽可能短。
² 上述子集划分问题可以用对集合中的元素逐个“筛选”的办法来解决。首先将集合的第1个元素置为第1个子集，再逐个检查集合中的其余元素是否和第1个元素有考试冲突，若不存在考试冲突，则将其加入到第1个子集中，继续检查集合中的其余元素，凡是不与第1个子集中的元素冲突的元素都逐个将其加入到其中；接着按同样的方法“筛选”出若干没有考试冲突的元素构成第2个子集，…，该过程一直到集合中的全部元素都分到某个子集中结束。得到的每一个子集中的课程就是可以安排在同一时间考试的课程。不同子集的课程则要安排在不冲突的时间考试。
l 考试分数的统计与排序
² 考试成绩输出
ü 每个学生的信息记录数据项应包括：学号、姓名、班级、课程1、课程2、…、课程10、总成绩。
ü 按总分高低输出所有学生信息时，应该以总成绩为关键字从高分到低分对所有的学生记录进行排序，排序方法自行选定，然后依次输出各个记录。
ü 按照班级顺序和总分高低输出各班学生信息时，要对学生记录进行多关键字排序，首先以总成绩为关键字从高分到低分对所有的学生记录进行排序，然后再以班号为关键字对全部学生记录排序，再输出结果。
² 统计成绩统计各分数段的人数，要求由用户输入，具体要求可以有：
ü 按照总成绩统计各分数段的人数，并输出各分数段的学生记录，即在统计一个分数段的人数过程中，要输出满足查找条件的学生记录，再输出统计的结果。
ü 指定某一门课程，统计各分数段的人数并输出各分数段的学生记录。
ü 对指定班级中总成绩或指定课程成绩做各分数段人数的统计，也要输出各分数段的学生记录。
² 查找成绩查找要求由用户输入，可以输入以下条件：
ü 查找指定分数项（总分或某一门课程）的某分数段的学生信息，输出查找结果。
ü 查找指定班级、指定分数项的某分数段的学生信息，输出查找结果。
ü 查找指定学生（给定学号）的具体信息，输出查找结果。
③算法提示
l 考试场次的划分——“无考试冲突”子集划分的算法思路。 为了把10门课程划分为时间上不冲突的若干场考试，可以利用一个循环队列来实现求解方法中说明的“筛选”过程。 首先定义一个循环队列，再把10门课程的编号从小到大依次加入到循环队列中，然后重复下列步骤：
ü 队头元素出队并作为当前子集的第1个元素。
ü 队头元素继续依次出队，每出队一个队头元素都要检查与当前子集中的元素是否有“考试冲突”；如果没有冲突，则将其加入到当前子集中，否则将其重新加入队列中，等待以后加入新子集的机会。
ü 比较刚出队元素与前一出队元素编号。因为队列中原有的元素是以编号从小到大的顺序排列的，重新入队的元素编号一定小于它的前一元素，所以一旦发现目前出队的元素编号小于前一个出队的元素，就可以断定当前的“考试冲突”子集已经构建完，队列中剩余元素应该构建新的子集。为此，在当前的队头元素出队前，要先记下刚刚出队的元素，以便判断当前出队的元素是否要开始构建一个新子集。
重复上述步骤一直到队列空，则“无考试冲突”子集划分完成。
由上述算法思路可以知道，“无考试冲突”子集的划分过程是一个循环的执行过程，循环中的主要操作是元素出队和判断的操作。判断操作包括出队元素是否可以加入当前子集和是否要开始构建一个新子集两个方面，对后一个判断如前所述，通过比较出队元素与前一个出队元素编号大小可以确定。为了判断出队元素与当前子集中的元素是否有“考试冲突”，可以定义一个二维数组conf[n][n]来表示课程的考试冲突关系矩阵，矩阵中各元素的值根据以下规则确定，若编号为i的课程和编号为j的课程有考试冲突，则置conf[i][j]=1，否则置conf[i][j]=0，考试冲突关系矩阵如图1所示。
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
1
0
1
1
0
0
0
0
0
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
1
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
1
0
0
0
1
0
1
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0
1
1
1
1
0
0
图1 考试冲突关系矩阵
利用“考试冲突”关系矩阵可以检查出队元素i是否与当前子集中的元素有考试冲突，其方法是：当课程号为j1，j2，…，jk的元素已经在当前子集S中，要判断目前出队的元素i是否可以加入子集S，只要检查“考试冲突”关系矩阵中第i行的元素conf[i][ j1]，conf[i][ j2]，…conf[i][ jk]的值是否为0即可。如果这些元素的值都为0，表示课程i与子集中的课程没有考试冲突，可以加入其中，否则说明表示课程i与子集中的某些课程有考试冲突，它不能加入该子集中。为了减少在二维数组conf中查找元素的操作，可以定义一个一维数组clash[n]来方便出队元素i是否要加入当前子集的判断，数组clash[n]用于记录出队元素i与当前子集中的元素是否存在考试冲突的信息。每当开始构建一个新子集时，先将数组clash[n]的各元素初始化为0，当有编号为i的课程加入子集时，将“考试冲突”关系矩阵中第i行的各列的值与数组clash的各对应元素的值相加，因而使得数组clash中和编号为i的元素有考试冲突的相应元素的值不再是0，当下一个队头元素j出队时，只要检查数组clash中第j个元素的值是否为0，就可以判断其是否与当前子集中的元素有考试冲突；若数组clash中第j个元素的值不为0，则说明元素j与当前子集中元素存在考试冲突，应将其重新加入队列；若数组clash中第j各元素的值为0，则说明它与当前子集中元素不存在考试冲突，应该将它加入当前子集中，同时要将“考试冲突”关系矩阵中第j行的各列的值与数组clash的各对应元素的值相加，这个过程一直到队列空，则划分无考试冲突子集完成。划分结果可以用一个二维数组来记录各子集中的元素的方式来表示，也可以用一个一维数组来记录每个元素其所属的子集号的方式来表示。上述算法的思路可以描述如下：
建立表示课程考试冲突关系矩阵的二维数组conf[n][n]；
定义用于检查当前子集的课程考试冲突信息的数组clash[n]；
定义用于记录子集划分结果的数组result[n]；
pre=n;//pre用于记录前一个出队元素的编号，初始值置为n以
新建第1个子集
k=0； //k用于记录子集序号
0~9(课程编号)依次入队；
while（队列不空）
{
队头元素i出队；
if(i<pre)//刚出队元素小于前一个出队元素，生成一个新子集
{
k++;
数组clash初始化；
}
if(i可以加入当前子集)//如果刚出队元素与当前子集中的元素
无考试冲突，将其加入当前子集
{
将i加入当前子集，记录i所属子集的序号；
将conf数组第i行各列的值与clash数组对应列的值相加并记入clash中；
}
else //如果刚出队元素与当前子集中的元素有考试冲突，将其重新入队
将i重新加入队列；
pre=i;
}
l 考试成绩统计和排序的实现
ü 按总成绩或按某一门课的成绩统计并输出人数时，应该使各分数段的人数和每个学生的信息清晰的分开。
ü 对全体学生或对某一个班的学生的成绩进行排序时，排序方法可以任意选择。就本实验问题而言，因表长不大采用简单的排序方法就可以达到目的，但为了比较各种常用排序方法性能和适用场合，还可以采用不同的排序方法实现排序。
ü 对多关键字的排序要求，要注意排序方法的稳定性问题。例如，在按总成绩从高分到低分对全体学生进行排序后，再按班级从高分到低分进行排序，此时要求分班级排序时采用的排序方法其动态性能必须是稳定的。同样地，如果在按总成绩从高分到低分排序的基础上，再要求按某一门课的成绩从高分到低分排序，也要求第2层排序一定注意选择动态性能稳定的排序方法。
ü 在实现查找或排序功能时，其查找或排序的依据（指定项）和目标（输出结果）通过提示用户输入来确定。
2. 数据结构设计

typedef int KeyType;
typedef char InfoType[10];
typedef struct /*记录类型*/
{
KeyType key; /*关键字项*/
InfoType data; /*其他数据项,类型为InfoType*/
} RecType
3. 算法设计
#include<iostream>
using namespace std;
#define MAXE 20/*线性表中最多元素个数*/
typedef int KeyType;
typedef char InfoType[10];
typedef struct /*记录类型*/
{
KeyType key; /*关键字项*/
InfoType data; /*其他数据项,类型为InfoType*/
} RecType;
void SelectSort(RecType R[],int n)/*直接选择排序算法*/
{
int i,j,k,l;
RecType temp;
for (i=0;i<n-1;i++) /*做第i趟排序*/
{
k=i;
for (j=i+1;j<n;j++) /*在当前无序区R[i..n-1]中选key最小的R[k] */
if (R[j].key<R[k].key)
k=j; /*k记下目前找到的最小关键字所在的位置*/
if (k!=i) /*交换R[i]和R[k] */
{
temp=R[i];R[i]=R[k];R[k]=temp;
}
printf(" i=%d ",i);/*输出每一趟的排序结果*/
for (l=0;l<n;l++)
printf("%2d",R[l].key);
printf("\n");
}
}
int main()
{
int i,k,n=10,m=5;
KeyType a[]={6,8,7,9,0,1,3,2,4,5};
RecType R[MAXE];
for (i=0;i<n;i++)
R[i].key=a[i];
printf("\n");
printf(" 初始关键字 ");/*输出初始关键字序列*/
for (k=0;k<n;k++)
printf("%2d",R[k].key);
printf("\n");
SelectSort(R,n);
printf(" 最后结果 ");/*输出初始关键字序列*/
for (k=0;k<n;k++)
printf("%2d",R[k].key);
printf("\n\n");
system("pause");
}
4.界面设计
程序包含有多个功能，所以，采用菜单，以方便用户进行功能选择。菜单如下：
1：直接插入排序算法验证
2：快速排序算法验证。
3: 直接选择排序算法验证。
4: 退出

5. 运行、测试与分析
1）直接插入排序算法验证

2） 快速排序算法验证。

3）直接选择排序算法验证。

6. 实验收获及思考
这次实验我对选择拍循序，插入排序，快速排序有了更好的理解，以及时间复杂度的问题分析，通过这次实验，我对排序的内容有了更深入的了解。编程技术有了很大的提高

1．实验要求
i. 实验目的:
通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。
理解算法的主要思想及流程。
ii. 实验内容：
使用链表实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、冒泡排序（改进型冒泡排序）
3、快速排序
4、简单选择排序
5、堆排序（小根堆）
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性

iii. 代码要求：
1、必须要有异常处理，比如删除空链表时需要抛出异常；
2、保持良好的编程的风格：
代码段与段之间要有空行和缩近
标识符名称应该与其代表的意义一致
函数名之前应该添加注释说明该函数的功能
关键代码应说明其功能
3、递归程序注意调用的过程，防止栈溢出
2. 程序分析
通过排序算法将单链表中的数据进行由小至大（正向排序）
2.1 存储结构
……
单链表存储数据：

structnode
{
int data;
node*next;
};
单链表定义如下：
classLinkList
{
private:
node * front;
public:
LinkList(int a[], int n);//构造
~LinkList();
void insert(node*p, node*s);//插入
void turn(node*p, node*s);//交换数据
void print();//输出
void InsertSort();//插入排序
void BubbleSort();//pos冒泡
void QSort();//快速排序
void SelectSort();//简单选择排序
node* Get(int i); //查找位置为i的结点
void sift(int k, int m); //一趟堆排序
voidLinkList::QSZ(node * b, node *e); //快速排序的递归主体
void heapsort(int n); //堆排序算法
};
2.2 关键算法分析：
1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。
分析上述排序过程，需设一个工作指针p->next在无序区中指向待插入的结点，在找到插入位置后，将结点p->next插在结点s和p之间。

voidLinkList::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数
node * p = front->next;//要插入的节点的前驱
while (p->next)
{
node * s = front;//充分利用带头结点的单链表
while (1)
{
comparef++;
if (p->next->data <s->next->data)// [P后继]比[S后继]小则插入
{
insert(p, s); break;
}
s = s->next;
if (s == p)//若一趟比较结束，且不需要插入
{
p = p->next; break;
}
}
}
QueryPerformanceCounter(&t2); //测后跳动次数
double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒
cout << "操作时间为：" << d << endl;
}
2.快速排序：
主要通过轴值将数据从两端向中间进行比较，交换以实现排序。
通过递归的调用来实现整个链表数据的排序。
代码中选用了第一个元素作为轴值。
一趟排序的代码：
voidLinkList::QSZ(node * b, node *e)
{
if (b->next == e || b == e)//排序完成
return;
node * qianqu = b;//轴点前驱
node * p = qianqu->next;
while (p != e && p != e->next)
{
comparef++;
if (qianqu->next->data > p->next->data)//元素值小于轴点值，则将该元素插在轴点之前
{
if (p->next == e)//若该元素为e，则将其前驱设为e
e = p;
insert(p, qianqu);
qianqu = qianqu->next;
}
else p = p->next;
}
QSZ(b, qianqu);//继续处理轴点左侧链表
QSZ(qianqu->next, e);//继续处理轴点右侧链表
}
整个快速排序的实现:
voidLinkList::QSort()
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数
node * e = front;
while (e->next)
{
e = e->next;
}
QSZ(front, e);
QueryPerformanceCounter(&t2); //测后跳动次数
double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒
cout << "操作时间为：" << d << endl;
}
3.改进版的冒泡排序：
通过设置pos来记录无序边界的位置以减少比较次数。
将数据从前向后两两比较，遇到顺序不对是直接交换两数据的值。
每交换一次movef+3；
voidLinkList::BubbleSort()
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数
node * p = front->next;

while (p->next) // 排序查找无序边界
{
comparef++;
if (p->data > p->next->data)
turn(p, p->next);
p = p->next;
}
node * pos = p; p = front->next;
while (pos != front->next)
{
node * bound = pos;
pos = front->next;
while (p->next != bound)
{
comparef++;
if (p->data > p->next->data)
{
turn(p, p->next); pos = p->next;
}
p = p->next;
}
p = front->next;
}

QueryPerformanceCounter(&t2); //测后跳动次数
double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒
cout << "操作时间为：" << d << endl;
}
4.选择排序：
每趟排序再待排序的序列中选择关键码最小的元素，顺序添加至已排好的有序序列最后，知道全部记录排序完毕。
voidLinkList::SelectSort()
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数

node * s = front;
while (s->next->next)
{
node * p = s;
node * index = p;
while (p->next)
{
comparef++;
if (p->next->data < index->next->data)
index = p;
p = p->next;
}
insert(index, s);
s = s->next;
}
QueryPerformanceCounter(&t2); //测后跳动次数
double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒
cout << "操作时间为：" << d << endl;
}
5.堆排序：
利用前一趟比较的结果来减少比较次数，提高整体的效率。
其中通过链表储存了一棵树。
选择使用小根堆进行排序。
voidLinkList::sift(intk, intm)
{
int i = k, j = 2 * i;
while (j <= m)
{
comparef++;
if (j<m && (Get(j)->data>Get(j + 1)->data)) j++;
if (Get(i)->data < Get(j)->data) break;
else
{
turn(Get(i), Get(j));
i = j;
j = 2 * i;
}
}
}
voidLinkList::heapsort(intn)
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数

for (int i = n / 2; i >= 1; i--)
sift(i, n);
for (int i = 1; i < n; i++)
{
turn(Get(1), Get(n - i + 1));
sift(1, n - i);
}
QueryPerformanceCounter(&t2); //测后跳动次数
double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒
cout << "操作时间为：" << d << endl;
}
其中堆排序中需要知道孩子节点和父亲节点处的值，故设置了函数获取i出的指针。
node*LinkList::Get(inti)
{
node*p = front->next;
int j = 1;
while (j != i&&p)
{
p = p->next;
j++;
}

if (!p) throw"查找位置非法";
elsereturn p;
};
6.输出结果的函数：
void tell(LinkList &a, LinkList &b, LinkList &c, LinkList &d, LinkList &e)
{
a.print();
comparef = 0; movef = 0;
a.InsertSort();
cout << "排序结果："; a.print();
cout << "1.插入排序法： Compare：" << setw(3) << comparef << "; Move：" << setw(3) << movef << endl;

comparef = 0; movef = 0;
b.BubbleSort();
cout << "2.改进型冒泡排序法： Compare：" << setw(3) << comparef << "; Move：" << setw(3) << movef << endl;

comparef = 0; movef = 0;
c.QSort();
cout << "3.快速排序法： Compare：" << setw(3) << comparef << "; Move：" << setw(3) << movef << endl;

comparef = 0; movef = 0;
d.SelectSort();
cout << "4.简单选择排序法 Compare：" << setw(3) << comparef << "; Move：" << setw(3) << movef << endl;

comparef = 0; movef = 0;
e.heapsort(10);
cout << "5.堆排序算法 Compare：" << setw(3) << comparef << "; Move：" << setw(3) << movef << endl;
}

7.统计时间的函数：
#include<windows.h>
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数
node * p = front->next;//要插入的节点的前驱
QueryPerformanceCounter(&t2); //测后跳动次数
double d = ((double)t2.QuadPart - (double)t1.QuadPart) / ((double)feq.QuadPart);//时间差秒
cout << "操作时间为：" << d << endl;

};

2.3其他
算法的时间复杂度：
排序方法
随机序列的平均情况
最好情况
最坏情况
辅助空间
直接插入排序
O(n2)
O(n)
O(n2)
O(1)
快速排序
O(nlog2n)
O(nlog2n)
O(n2)
O(log2n) ~O(n)
改进版冒泡排序
O(n2)
O(n)
O(n2)
O(1)
选择排序
O(n2)
O(n2)
O(n2)
O(1)
堆排序
O(nlog2n)
O(nlog2n)
O(nlog2n)
O(1)
3. 程序运行结果
1.流程图开始
：

初始化正序链表，调用各类排序，并输出运行结果

初始化逆序链表，调用各类排序，并输出运行结果

初始化顺序随机的链表，调用各类排序，并输出运行结果

结 束

2.测试条件：
如果需要对不同的正序，逆序随机序列进行排序，则需要在main函数中进行初始化设置。3.测试结论：

4. 总结
通过这次实验我再次复习了链表的建立及相应的操作，对各类排序算法的实现也有了新的理解，在调试过程中出现了许多问题也花费了很多时间和精力去逐步解决，最后程序运行成功的瞬间真的很开心。
问题一：
直接插入排序中若是使用从后向前比较插入的话（即书上的办法）难以找到该节点的前驱节点，不方便进行操作，所以最后采用了从前向后进行比较。
voidLinkList::InsertSort()//将第一个元素定为初始有序区元素，由第二个元素开始依次比较
{
LARGE_INTEGER t1, t2, feq;
QueryPerformanceFrequency(&feq); //每秒跳动次数
QueryPerformanceCounter(&t1); //测前跳动次数
node * p = front->next;//要插入的节点的前驱
while (p->next)
{
node * s = front;//充分利用带头结点的单链表
while (1)
{
comparef++;
if (p->next->data <s->next->data)// [P后继]比[S后继]小则插入
{
insert(p, s); break;
}
s = s->next;
if (s == p)//若一趟比较结束，且不需要插入
{
p = p->next; break;
}
}
}
问题二：
如何将书上以数组方式储存的树转化为链表储存并进行操作？
原本打算建立一颗完全二叉树储存相应数据再进行排序，但是那样的话需要新设置结点存左孩子右孩子，比较麻烦容易出错，所以选择了利用Get(inti)函数将筛选结点的位置获得。
与书上代码相比修改如下：
if (j<m && (Get(j)->data>Get(j + 1)->data)) j++;
if (Get(i)->data < Get(j)->data) break;
else
{
turn(Get(i), Get(j));
i = j;
j = 2 * i;
}
问题三：
时间如何精确至微秒？需要调用函数，这个问题是上网查找解决的。
总结：解决了以上的问题后代码就比较完整了，可是还是希望通过日后的学习能将算法编写得更完善，灵活，简捷。
附录：
完整代码如下：
#include"lianbiaopaixu.h"
#include<windows.h>
usingnamespace std;
void main()
{

int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
LinkList zhengxu1(a, 10), zhengxu2(a, 10), zhengxu3(a, 10), zhengxu4(a, 10), zhengxu5(a, 10);
cout << "正序数列：";
tell(zhengxu1, zhengxu2, zhengxu3, zhengxu4, zhengxu5);

int b[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
LinkList nixu1(b, 10), nixu2(b, 10), nixu3(b, 10), nixu4(b, 10), nixu5(b, 10);
cout << "\n逆序数列：";
tell(nixu1, nixu2, nixu3, nixu4, nixu5);

int c[10] = { 2, 6, 10, 5, 8, 3, 9, 1, 4, 7 };
LinkList suiji1(c, 10)