单循环赛中选手胜负序列求解问题v数据结构与算法课程设计报告.docx

单循环赛中选手胜负序列求解问题v数据结构与算法课程设计报告.docx

《单循环赛中选手胜负序列求解问题v数据结构与算法课程设计报告.docx》由会员分享，可在线阅读，更多相关《单循环赛中选手胜负序列求解问题v数据结构与算法课程设计报告.docx（34页珍藏版）》请在冰点文库上搜索。

单循环赛中选手胜负序列求解问题v数据结构与算法课程设计报告

合肥学院

计算机科学与技术系

课程设计报告

2009～2010学年第二学期

课程

数据结构与算法

课程设计名称

单循环赛中选手胜负序列求解问题

学生姓名

管明璐

学号

0804012038

专业班级

08计科

（2）班

指导教师

王昆仑、张贯虹

2010年6月

一、问题分析和任务定义

单循环赛，是所有参加比赛的队均能遭遇一次，两队之间非胜即负，最后按各队在全部比赛中的积分、得失分率排列名次。

如果参赛球队不多，而且时间和场地都有保证，通常都采用这种竞赛方法。

本题可以从两个方面进行思考，一是按比赛过程中的积分排名产生胜负序列，二是根据比赛过程中各选手之间的胜负关系产生胜负序列。

针对第一种情况，比赛规定各选手之间只能遭遇一次，获胜的选手得一分，失败的一方不得分，比赛结束时按照各选手之间的积分排名决定他们的胜负序列，在设计过程中要用到排序的算法。

针对第二种情况，按照比赛过程中的胜负关系产生胜负序列，不过这种方法产生的胜负序列可能不是唯一的，但是实际情况是比赛结束时一定会产生一种胜负序列。

为此需要用合适的数据结构进行存储，来确定如何产生胜负序列，选取哪位选手作为第一名，假如该选手已经在序列中，在后面的筛选过程中，如何将该选手排除等一系列问题。

二、概要设计和数据结构选择

（1）针对第一种情况，所采用的数据结构是类。

将选手的编号、积分以及胜负过程中的积分处理等封装在类中。

其中，以编号和积分作为私有成员，而设置编号、获胜处理、失败处理、获取积分、获取编号等作为公有成员。

此时将该问题转化为对选手积分进行排序的问题。

在实际操作时，我想分别输入选手的姓名，根据姓名来判断积分的高低，但是当姓名也作为私有成员时，由于权限问题，不能在主调函数中直接输入，所以使用了另外一个数据结构：

结构体，将姓名放入结构体中，在排序时让姓名与积分一一对应。

（2）针对第二种情况，采用的数据结构是有向图，将每个选手作为有向图的一个顶点，选手间的胜负关系作为有向弧，从箭头出发的一方作为获胜者，所以该问题转化为了有向图的深度遍历问题，即求解一条包含所有顶点的简单路径。

在深度遍历过程中，以有向图的邻接矩阵作为存储结构。

在本实验中，为了使功能更完善，还用到了磁盘文件。

可以将参赛选手的人数、他们之间的胜负关系预先放进一个记事本中，运行程序时被读入，在处理后将胜负序列读出到另一个记事本中，并保存起来。

这里会用到输入、输出文件流的成员函数。

三、详细设计和编码

（1）针对第一种情况，设计一个选手类player,私有成员包括选手编号num和选手积分mark。

公有成员包括构造函数player（），设置编号函数voidsetnum（intnum1），获胜处理函数voidwin（），失败处理函数voidfail（），返回编号函数intgetnum（），返回积分函数intgetmark（）。

同时设计一个结构体play，包含选手姓名name。

选手类的定义如下：

classplayer//选手类

{

private:

//私有成员

intmark;//选手积分

intnum;//选手编号

public:

//公有成员

player（）//构造函数

{}

voidsetnum（intnum1）//设置编号函数

{num=num1;

mark=0;

}

voidwin（）//胜利处理函数

{mark++;

}

voidfail（）//失败处理函数

{mark--;

}

intgetmark（）//获取分数函数

{returnmark;

}

intgetnum（）//获取编号函数

{returnnum;

}

};

结构体定义如下：

#definemax100

structplay{

charname[10];//选手姓名

}p[max];

定义了一个名为“比赛积分.txt”的文本文件：

ofstreamf3（"比赛积分.txt",ios:

:

trunc）;

if（!

f3）

{cerr<<"openerror!

"<

exit

（1）;}

这些代码定义在头文件mark.h中。

在程序的初始化时根据输入的选手人数n，动态申请一个选手类的数组Player[n]。

首先依次输入选手的姓名，然后依次输入第一个选手和后面的n-1个选手的胜负关系，第二个选手和后面n-2个选手的胜负关系……第n-1个选手和第n个选手的胜负关系。

W或w表示胜利，F或f表示失败。

在各个选手的胜负关系输入完毕后，通过返回获取积分函数getmark（）对各选手的积分进行排序，从而产生胜负序列。

并且将参赛选手的人数、他们的胜负关系和产生的胜负序列读出到“比赛积分.txt”文本文件中。

（2）针对第二种情况，由于仅涉及到n个选手，并且这些选手之间的关系仅是胜负关系，因此可用有向图来表示，由于是赛程安排问题，所以又可用到深度优先遍历的思想。

为搜索出符合条件的简单路径，需按深度优先搜索方式进行遍历。

因此求解算法应是深度遍历算法的变形形式，也应是递归形式的算法。

用顶点表示选手，用弧表示选手之间的胜负关系：

当且仅当Pi胜Pj时，有从顶点i到j的一条有向弧。

在这种表示下，本题问题变成了如下的问题：

在有向图中求解出一条包含所有顶点的简单路径的问题。

下图所示为一个有6个选手的问题的一个示例。

其中的一个解为1,6,3,4,5,2。

图1

由图中的各顶点按次序构成一条简单路径，这与所学过的深度优先遍历算法稍有差异：

并不是任意选择一个起点或任意的试探路径都能得到要求的简单路径。

但是对算法设计到这里时，还不能确定怎么才能构成简单路径。

为此需要做下一步的准备工作，在求解过程中试探：

试探起点及访问次序。

试探时要记录一些中间状态：

某顶点是否在试探路径中、已经试探顶点的次序、正在试探的顶点、某顶点不满足条件时怎么取舍等。

设置变量及参数如下：

设置MAX_VERTEX100为最大选手数量，设图为G，当前试探路径中试探的最后顶点为i，i在试探路径中的序号为k。

定义一个访问标志数组visited[n]来记录各顶点是否在当前试探路径中，初值为0，如果在试探路径中，则visited[i]=1，如果不在试探路径中，则visited[i]=0。

定义路径结构体PATH，包含试探路径中的序号k和选手序列path[MAX_VERTEX],用路径pa中的path[MAX_VERTEX]存储当前路径中的各顶点。

设置结构体MGraph为图的存储结构，包含选手的人数n、弧数e和存储矩阵edges[MAX_VERTEX][MAX_VERTEX]，为邻接存储矩阵，即本程序采用邻接矩阵作为图的存储结构。

在试探时，需要对当前顶点i的每个邻接点（用j表示）进行试探，试探由i经j往下是否可以得到解。

每个i都可能有成功与失败两种情况，对此应分别作不同的处理：

1）若试探成功，则应j放入路径中，并置相应的状态值，visited[i]=1。

然后再由j往下求解。

2）若试探不成功，则应恢复j的有关信息，visited[i]=0，以使j在试探其它路径时成为可选顶点。

为了能求出解以及所有可能的解，需要作如下两方面的工作：

1）选择起点：

应以每个顶点为起点进行搜索。

2）搜索路径：

在从i往下搜索时，应依次选择i的所有不在当前试探路径中的邻接点往下搜索。

为此，需要有这方面的保证：

应在试探某顶点j后并在换下一个试探顶点前恢复j的有关状态，以使其仍为可选择的顶点。

由上面的准备工作可得到如下结论：

1）若k=n-1，则说明已经求得一解，因此可输出结果，并结束本次调用。

2）若k

①试探：

将j放到path[MAX_VERTEX]中，并置visited[j]=1，然后以j为起点往下搜索。

②恢复：

将j恢复为不在当前路径中，以使其在试探其它路径时可用。

算法描述：

程序开始要求输入选手的人数。

并初始化path[MAX_VERTEX]全为-1，visited[j]为0，邻接矩阵edges[MAX_VERTEX][MAX_VERTEX]全为0。

提示依次输入第一个选手和后面的n-1个选手的胜负关系，第二个选手和后面n-2个选手的胜负关系……第n-1个选手和第n个选手的胜负关系。

W或w表示胜利，F或f表示失败。

初始化完成后尝试以不同的选手为起点进行搜索（从第1个到第n个）。

每次选择新的起点时对以上各个数组个数据从新初始化。

MGraph*Creat_MGraph（intn），为图的建立函数，这个函数被从键盘输入参赛人数时所调用。

根据选手的人数进行初始化，G->n=n;（图的顶点个数=选手个数），G->e=n*（n-1）/2;（图的边数=n*（n-1）/2）。

并且根据输入的选手胜负关系置相应的状态，i胜j时，G->edges[i][j]=1;否则，G->edges[j][i]=1。

MGraph*Creat_MGraph2（intn），为图的建立函数，这个函数被从文件读入参赛人数时所调用。

voidPush（intnum），为访问路径入栈，并且置相应的状态，即将编号为num的点入栈，也就是存储在pa.path[MAX_VERTEX]中，并使pa.k++；visited[num]=1。

voidPop（intnum）出栈，并且置相应的访问状态，即将编号为num的点出栈，也就是存储在pa.path[MAX_VERTEX]中，并使pa.k--；visited[num]=0。

voidPrint_MGraph（MGraph*G,intn）为输出图的存储矩阵，以矩阵的形式输入。

intTest（MGraph*G,inti,intn），试探当前结点是否可行,若可行，则入栈并返回1，否则出栈并返回0，把测试的结果返回给深度搜索函数voidSearch（MGraph*G,inti,intn），Search根据返回值进行向的处理。

voidSearch（MGraph*G,inti,intn），深度搜索函数，也就是本算法的核心函数，若n=pa.k-1则退出。

根据参数i从第i行开始搜索edges[i][j]，遇到1的点edges[i][j]的时候对该点进行测试，调用Test（G,j,n），若返回1则递归调用Search（G，j，n）继续搜索；若返回0则跳过该点从下一个合适的点进行测试，并根据测试的结果进行和上面相同的处理方式。

voidInit（），初始化函数，对w.path[MAX_VERTEX]全部置-1，对visited[MAX_VERTEX]全部置0。

具体设计如下：

#defineMAX_VERTEX100//最大选手数量

intvisited[MAX_VERTEX]={0};//访问标志数组，0表示未访问，1表示已经被访问

typedefstruct

{

intk;//k是在试探路径中的序号

intpath[MAX_VERTEX];//path[]存储试探路径的各顶点

}PATH;//路径结构

PATHpa;

typedefstruct

{

intn;//图的顶点个数=选手个数

inte;//图的边数=n*（n-1）/2

intedges[MAX_VERTEX][MAX_VERTEX];//邻接存储矩阵

}MGraph;//图

voidmenu2（）

{cout<<"\t★==========*=======☆副菜单☆========*===========★"<

cout<<"\t|\t1---------键盘输入|"<

cout<<"\t|\t2---------文件读入|"<

cout<<"\t★==========*===========☆============*===========★"<

}

MGraph*Creat_MGraph（intn）//图的建立，被键盘输入时调用

{ifstreamf1（"Text1.txt"）;

ofstreamf2（"胜负关系.txt",ios:

:

app）;

if（!

f2）

{cerr<<"openerror!

"<

exit

（1）;}

inti,j;chart1;

MGraph*G=（MGraph*）malloc（sizeof（MGraph））;

G->n=n;//图的顶点个数=选手个数

G->e=n*（n-1）/2;//图的边数=n*（n-1）/2

for（i=0;i

{for（j=0;j

G->edges[i][j]=0;//邻接存储矩阵初值为0

}

for（i=0;i

{

cout<<"请输入第"<

f2<<"请输入第"<

for（j=i+1;j

{

cin>>t1;

f2<<""<

if（t1=='w'||t1=='W'）//i胜j，矩阵相应位置置1

G->edges[i][j]=1;

elseif（t1=='f'||t1=='F'）//i负j，矩阵相应位置置1

G->edges[j][i]=1;

else

{cout<<"错误输入,请重新输入其后的胜负关系"<

j--;

continue;

}

}

f2<

}

returnG;

f1.close（）;f2.close（）;

}

MGraph*Creat_MGraph2（intn）//图的建立，被文件读取时调用

{ifstreamf1（"Text2.txt"）;

ofstreamf2（"胜负关系.txt",ios:

:

app）;

if（!

f2）

{cerr<<"openerror!

"<

exit

（1）;}

inti,j;

chart2;

MGraph*G=（MGraph*）malloc（sizeof（MGraph））;

G->n=n;//图的顶点个数=选手个数

G->e=n*（n-1）/2;//图的边数=n*（n-1）/2

for（i=0;i

{for（j=0;j

G->edges[i][j]=0;//邻接存储矩阵初值为0

}

for（i=0;i

{

cout<<"请输入第"<

f2<<"请输入第"<

for（j=i+1;j

{

f1>>t2;

cout<<""<

f2<<""<

if（t2=='w'||t2=='W'）//i胜j，矩阵相应位置置1

G->edges[i][j]=1;

elseif（t2=='f'||t2=='F'）//i负j，矩阵相应位置置1

G->edges[j][i]=1;

else

{cout<<"错误输入,请重新输入其后的胜负关系"<

j--;

continue;

}

}

cout<

}

returnG;

f1.close（）;f2.close（）;

}

voidPush（intnum）//访问路径入栈，并且置相应的状态

{

pa.path[pa.k]=num;

pa.k++;

visited[num]=1;//标记为1，将该顶点加入到数组pa[]中

}

voidPop（intnum）//出栈，并且置相应的访问状态

{

pa.k--;

visited[num]=0;//标记为0，恢复相关信息

}

voidPrint_MGraph（MGraph*G,intn）//输出图的存储矩阵

{

ifstreamf1（"Text1.txt"）;

ofstreamf2（"胜负序列.txt",ios:

:

app）;

if（!

f2）

{cerr<<"openerror!

"<

exit

（1）;}

cout<

cout<<"选手胜负矩阵如下:

"<

f2<<"选手胜负矩阵如下:

"<

inti,j;

for（i=0;i

{for（j=0;j

cout<edges[i][j]<<"";

cout<

for（j=0;j

f2<edges[i][j]<<"";

f2<

}

f1.close（）;f2.close（）;

}

intTest（MGraph*G,inti,intn）//试探当前结点是否可行,若可行，则入栈，否则出栈

{

intflag=0,j;//flag=0表示试探失败，flag=1表示试探成功

for（j=0;j

if（G->edges[i][j]==1）

{flag=1;break;}

returnflag;

}

voidSearch（MGraph*G,inti,intn）//深度搜索函数

{

if（pa.k==n-1）//已经搜索完毕

{pa.path[pa.k]=i;return;}

intj;

for（j=0;j

{

if（G->edges[i][j]==1&&visited[j]==0）//找到合适的路径

{if（visited[i]==0）Push（i）;

if（Test（G,j,n））//试探成功，则递归搜索

Search（G,j,n）;

else//试探不成功

{

if（pa.k==n-1）{pa.path[pa.k]=j;return;}//试探不成功，但已经是最后一个顶点，则将其存储

else{Pop（i）;continue;}//试探失败，则从i的下一个邻接点试探

}

}

//elsecontinue;

if（pa.k==0）return;

}

}

voidInit（）//初始化函数

{

pa.k=0;//开始以第一个结点做搜索节点

for（inti=0;i

{

pa.path[i]=-1;

visited[i]=0;

}

}

这些代码定义为头文件：

order.h（）。

从键盘输入的参赛人数、他们的胜负关系、存储矩阵和相应的胜负序列，读出在名为“胜负关系.txt”的文本文件中。

从文件读入的参赛人数、胜负关系和处理后所得的胜负序列也读出在“胜负关系.txt”的文本文件中。

由参赛选手间的胜负关系得到的胜负序列的流程图如下：

图2

四、上机调试

（1）第一种情况时，主要用到了类，但是以选手姓名作为私有成员时，由于权限问题，私有成员不能直接被调用，而主调函数中要求输入姓名，编译时一直出错。

为了解决这个问题，另外定义了一个结构体，只放了选手姓名name，这样就可以使用了。

在程序中只需要注意让选手姓名与积分对应起来就行了。

同时，所得的胜负序列会读出到名为“比赛积分.txt”的文本文件中。

（2）第二种情况时，用到了递归的深度优先遍历，调试过程中出现了一些问题：

①在试探的路径中出现了编号的重复，也就是说有些点在试探成功后又被试探了，这显然是错误的，分析可知，这是由于在对结点的试探成功后并没有修改相应的标志数组中的相应位置，即让visited[i]=1，导致了重复试探。

在入栈函数Push（）中加入了入栈功能，此问题得以解决。

同理在测试失败时也应该修改相应的标志位置。

②在从文件中读入参赛人数及胜负关系时，在记事本中格式为“4wffwfw”,第一次读入人数，在第二次读胜负关系时，“4”被重新读了一遍。

为解决这个问题，老师指导时提及了fseek函数，但是从网上查到它只能在C语言中使用。

因此，建立了两个记事本”Text1.txt”、”Text2.txt”，分别存放参赛人数和胜负关系，这样就不会出现问题了。

在本实验中，算法不仅具有可行性，还要考虑其健壮性，对分配的内存空间进行检测，并作出相应的处理。

例如在输入第2个选手和后面2个选手的胜负关系时，只能输入两个关系，如果输入“wff”时，则会自动报错并提示是否重新输入。

五、测试结果及其分析

这是第一种情况的测试结果，选择以积分排名为标准后，输入3个选手，姓名分别为“a”、“b”、“c”时，输入他们的胜负关系，经过处理后，先输出名次：

1→2→3，然后输出选手姓名：

c→a→b,再输出各自的分数：

2→0→-2。

这是第二种情况的测试结果，选择以胜负关系为标准时，弹出一个副菜单，提示是从键盘输入还是从文件读入，选择从键盘输入时，输入4个选手，分别输入他们的胜负关系，用邻接矩阵存储的胜负关系如上所示，最后得出胜负序列：

3124。

这也是第二种情况的测试结果，选择以胜负关系为标准时，弹出一个副菜单，提示是从键盘输入还是从文件读入，选择从文件读入时，自动将记事本中的参赛人数5和他们的胜负关系读入，用邻接矩阵存储的胜负关系如上所示，最后得出胜负序列：

31452。

六、用户使用说明

（1）本程序运行过程时带有提示性语句，程序的起始界面如上所示，有一个主菜单，要求用户输入所有求解的方法，有两种，输入1选择第一种情况，输入2选择第二种情况，输入0时退出。

在输入除了这三个数字以外的其他字符的时候，程序报错，提示用户输入错误，并要求用户重新进行相应的选择。

（2）如果输入1的时候进入第一种情况的处理界面，按提示用户依次输入第一个