合肥學院

計算機科學與技術系

課程設計報告

2009～2010學年第二學期

課程

數據結構與算法

課程設計名稱

單循環賽中選手勝負序列求解問題

學生姓名

王夢宇

學號

0804012009

專業班級

08計科(2)

指導教師

張貫虹 王昆侖

2010年6月

題目：單循環賽中選手勝負序列求解問題

題目內容：有n個選手p1,p2,p3,…,pn參加了的單循環賽，每對選手之間非勝即負。現在要求求出一個選手序列p1’,p2’,p3’,…，pn’，使其滿足pi’勝pi+1’(i=1，…，n-1)。

1、問題分析和任務定義

單循環賽的定義：

單循環賽，是所有參加比賽的隊兩兩進行比賽并且每兩隊均能相遇一次，最后按各隊在全部比賽中的積分、得失分率排列名次。如果參賽球隊不多，而且時間和場地都有保證，通常都采用這種競賽方法。

單循環比賽輪次的計算：

本題有兩種不同的理解，第一個是按比賽的積分排名產生勝負序列，第二個是按比賽過程中各個選手間的勝負關系產生勝負序列，具體分析如下：

(1)按比賽中積分排名產生勝負序列：

比賽可規定各個選手之間均遭遇且只遭遇一次，比賽時勝方得1分，負方得-1分，在比賽結束時按積分排序進行排名，由此產生勝負序列關系。

(2)按比賽過程中各個選手間的勝負關系產生勝負序列：

該種方法是以過程中的勝負為標準從而產生勝負序列，當然，這種勝負序列很大的可能性是不唯一的，本程序按課程設計任務書的要求，僅求出其中的一個勝負序列關系，即是在有向圖中求解出一條包含所有頂點的簡單路徑的問題。

2、數據結構的選擇和概要設計

(1)對于第一種情況，本實驗選用的數據結構是結構體。結構體中包含選手的名字，編號和勝負所得的積分。勝負序列的求解轉化為了對所有選手的積分的排序問題。然后根據積分的多少從大到小輸出選手的名次、選手姓名、選手編號信息。其概要設計如下：

定義了一個都文件Score.h.主要包含了以下幾個功能：

1

1

★★★★歡迎進入積分處理比賽結果菜單★★★★

1 輸入比賽選手的信息

2 輸出比賽選手的比賽名次

3 根據選手編號查詢選手的比賽名次及得分

4 根據選手姓名查詢選手的比賽名次及得分

0 結束本菜單操作

*****注：第一次使用本系統時請選擇1號功能*****

判斷

0

3

2

1

4

使用子函數Creat()用于輸入選手信息

使用子函數Order()用來根據積分對選手進行排名

使用子函數Search_num(int num)根據編號查詢選手信息

使用子函數Search_name(string name)根據姓名查詢選手信息

跳出循環

圖1 Score函數的主框架

(2)對于第二種情況，本實驗采用的數據結構是有向圖，每個選手視為一個頂點，每條邊視為選手之間的勝負關系，箭頭指向的一方為失敗方。所以勝負序列的求解就轉化為了圖的深度遍歷問題(實際上跟有向圖的深度遍歷不太一樣，詳情請看源代碼附錄)。另外為了便于深度遍歷有向圖，本實驗采用的存儲結構為圖的鄰接矩陣存儲。

主要框架如下：

Win_Fail.h

Win_Fail.h的功能

子函數Graph *Creat_Graph(int n)用于創建圖

子函數Print_Graph(Graph *g,int n)用于輸出矩陣

void Push(int num)用于頂點進棧

子函數Pop(int num)用于出棧

子函數intTest(Graph *g,int i,int n)用于測試

子函數voidSearch(Graph *g,int i,int n)用于深度搜索

初始化函數Init()

圖2 Win_Fail.h的主框架

(3)主函數的主要框架

主菜單

主菜單

歡迎使用單循環賽中選手勝負序列求解問題程序"

本程序有以下三個功能:

1:以單循環賽中的積分排名為標準

2:以單循環賽過程中的勝負為標準

0:結束操作

Case 1:子函數Score()用于根據積分求解選手序列

Case2:子函數Process()用于根據選手之間的勝負關系求解

Case3:跳出主菜單，即程序運行結束

判斷

圖3 主函數功能框架

3、詳細設計和編碼

(1)、對于第一種情況：根據積分求解的詳細設計及編碼

1、定義如下數據結構的選手類型

typedef struct{ //結構體

string name; //選手的姓名

int num; //選手的編號

int score; //選手所得分數

} player;

2、全局變量的定義

player pl[max];定義全局變量，其中max為

總結

以上是生活随笔為你收集整理的单循环比赛算法设计c语言,单循环赛中选手胜负序列求解问题-数据结构与算法课程设计报告.doc...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。