資料結構課程設計報告

課程設計報告

課程名稱資料結構

課題名稱生死者遊戲

專業資訊管理與資訊系統

班級學號

姓名指導教師

2011 年 1 月 20 日

湖南工程學院

課程設計任務書

課程名稱資料結構

課題生死者遊戲

專業班級

學生姓名

學號指導老師

審批任務書下達日期 2011 年 1 月 3 日

任務完成日期 2011 年 1 月 20 日

一、設計內容與設計要求

1．設計內容：

[問題描述]　每n（n>k）個旅客同乘一條船，因為嚴重超載，加上風高浪大，危險萬分，因此船長告訴乘客，只有將全船一半的旅客投入海中，其餘人才能倖免遇難。無奈，大家只得同意這種辦法，並擬定n個人圍城一圈，由第乙個人數起，依次報數，數到第k人，便把他投入大海中，然後再從他的下乙個人數起，數到第k人，再將他扔進大海中，如此迴圈地進行，直至剩下n/2個乘客為止。問哪些位置是將被扔進大海的位置。

[基本功能]

（1）實時顯示每仍乙個旅客之前，按序號從小到大的順序顯示當前在船上的旅客的編號。

（2）變換n和k的值，看顯示結果是否仍然正確。

2．設計要求：

1）．設計正確，方案合理。

2）．介面友好，使用方便。

3）．程式精煉，結構清晰。

4）．設計報告以上，含程式設計說明、系統的功能框圖、流程圖、源程式清單等。

5）．實際操作過程中遇到的問題及解決方法：設計總結及心得體會。

6）．上機演示。

二、進度安排

第 19 周星期一 8時：00分——11時：30分

星期二 8時：00分——11時：30分

星期三 14時：00分——17時：30分

星期四 14時：00分——17時：30分

星期五 8時：00分——11時：30分

第 20 周星期一 8時：00分——11時：30分

目錄1 課題系統主要功能分析 1

1.1 設計內容 1

1.2 設計思路 1

1.3 資料結構 1

2 總體設計 2

3 主要演算法及模組流程圖 3

3.1 主要演算法 3

3.2 刪除模組 5

3.3 查詢模組 6

4 詳細設計 7

4.1 結構體定義 7

4.2 主函式 7

4.3 單鏈表的建立 8

4.4 輸出船員資訊 9

4.5 船員的刪除 10

4.6 查詢模組 11

5 系統除錯及執行結果 14

5.1 程式除錯中的問題 14

5.2 程式執行結果 16

6 心得體會 18

7 附件 20

7.1程式源** 20

7.2參考文獻 25

8 評分表 26

本遊戲的數學建模如下：假設m個旅客排成乙個環形，依次順序編號1，2，…，n。從某個指定的第1號開始，沿環計數，每數到第k個人就讓其出列，且從下乙個人開始重新計數，繼續進行下去。

這個過程一直進行到剩下m/2個旅客為止。

本遊戲的要求使用者輸入的內容包括：

1. 旅客的個數，也就是m的值；

2. 離開旅客的間隔數，也就是k的值；

3. 所有旅客的序號作為一組資料要求存放在某種資料結構中。

本遊戲要求輸出的內容是包括

1. 離開旅客的序號；

2. 剩餘旅客的序號；

所以，根據上面的模型分析及輸入輸出引數分析，可以定義一種資料結構後進行演算法實現。

為了解決這一問題，可以用長度為30的陣列作為線性儲存結構，並把該陣列看成是乙個首尾相接的環形結構，那麼每投入大海乙個乘客，就要在該陣列的相應位置做乙個刪除標記，該單元以後就不再作為計數單元。這樣做不僅演算法較為複雜，而且效率低，還要移動大量的元素。用單迴圈鍊錶解決這一問題，實現的方法相對要簡單得多。

首先要定義鍊錶結點，單迴圈鍊錶的結點結構與一般的結點結構完全相同，只是資料域用乙個整數來表示位置；然後將它們組成具有30個結點的單迴圈鍊錶。接下來從位置為1的結點開始數，數到第8個結點，就將下乙個結點從迴圈鍊錶中刪去，然後再從刪去結點的下乙個結點開始數起，數到第8個結點，再將其下乙個結點刪去，如此進行下去，直到剩下15個結點為止。

本程式實行了對生死者遊戲的操作，其系統功能模組如圖所示；

圖2.1系統功能模組

為了不失一般性，將30改為乙個任意輸入的正整數m，而報數上限也為乙個任選的正整數k。這樣該演算法描述如下：

(1) 建立含有m個結點的單迴圈鍊錶；

建立乙個有m個船員的陣列a[m]，且每個成員都初始化為0。

(2) 生著與死者的選擇：

p, q指向鍊錶的第乙個結點head，初始j置為1；

while(m>m/2) //刪除一半的結點

｛ if(k==1)

else

(3) 查詢系統

1---按船員進行查詢資訊

2---按照扔的次序進行查詢資訊

（4）輸出船上的船員

圖3.1 刪除模組

圖3.2 查詢模組

在c語言中，可以定義結構體型別，將多個相關的變數包裝成為乙個整體使用。在結構體中的變數，可以是相同、部分相同，或完全不同的資料型別。這裡定義乙個gnode結構體，裡面包括船員的號碼值number,也包括鍊錶的下乙個結點的指標。

資料結構課程設計報告

資料結構課程設計報告

《資料結構》課程設計報告

資料結構課程設計報告

相關推薦