石家莊經濟學院
華信學院
基於單向迴圈鍊錶的約瑟夫環設計
學院: 石家莊經濟學院華信學院
專業: 電腦科學與技術
班級2班
學號: 412417080203
姓名: 閆靜
約瑟夫環問題的設計與實現
1.問題描述
約瑟夫 (joseph) 問題的一種描述是：編號為 1，2，… ，n 的n個人按順時針方向圍坐一圈，每人持有乙個密碼(正整數)。一開始任選乙個正整數作為報數上限值m，從第乙個人開始按順時針方向自1開始順序報數，報到m時停止報數。
報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下乙個人開始重新從1報數，如此下去，直至所有人全部出列為止。試設計乙個程式求出出列順序。
2.需求分析
（1）利用單向迴圈鍊錶儲存結構模擬此過程，按照出列的順序印出各人的編號。
（2）測試資料：m 的初值為 20；n=7，7 個人的密碼依次為：3，1，7，2，4，8，4， 首先 m 值為 6( 正確的出列順序應為 6，1，4，7，2，3，5) 。
（3）輸入資料：建立輸入函式，處理輸入的資料，輸入m的初值，輸入每個人的密碼，建立單向迴圈鍊錶。
（4）輸出形式：建立乙個輸出函式，將正確的出列順序輸出。
3.概要設計
本程式主要是以建立單向迴圈鍊錶的形式，建立起乙個約瑟夫環，然後根據之前創立的結點，輸入結點裡的一些資料。遊戲中人的編號為正整數，所以用整數來儲存編號。
3.1 圖結構的adt的定義
adt graph
資料關係： r1=
基本操作：
iinitlist(&l)
操作結果：構造乙個空的線性表 l 。
destroylist( &l )
初始條件：線性表 l 已存在。
操作結果：銷毀線性表 l 。
clearlist( &l )
初始條件：線性表 l 已存在。
操作結果：將 l 重置為空表。
listempty( l )
初始條件：線性表l已存在。
操作結果：若 l 為空表，則返回 true，否則返回 false
listlength( l )
初始條件：線性表 l 已存在。
操作結果：返回 l 中元素個數。
getelem( l, i, &e )
初始條件：線性表 l 已存在，1≤i≤lengthlist(l)。
操作結果：用 e 返回 l 中第 i 個元素的值。
locateelem( l, e, compare( ) )
初始條件：線性表 l 已存在，compare( ) 是元素判定函式。
操作結果：返回 l 中第1個與 e 滿足關係 compare( ) 的元素的位序。
若這樣的元素不存在，則返回值為0。
priorelem( l, cur_e, &pre_e )
初始條件：線性表 l 已存在。
操作結果：若 cur_e 是 l 中的資料元素，則用 pre_e 返回它的前驅，
否則操作失敗，pre_e 無定義。
nextelem( l, cur_e, &next_e )
初始條件：線性表 l 已存在。
操作結果：若 cur_e 是 l 中的資料元素，則用 next_e 返回它的後繼，
否則操作失敗，next_e 無定義。
listinsert( &l, i, e )
初始條件：線性表 l 已存在，1≤i≤lengthlist(l)+1。
操作結果：在 l 的第 i 個元素之前插入新的元素 e，l 的長度增1。
listdelete( &l, i, &e )
初始條件：線性表 l 已存在且非空，1≤i≤lengthlist(l)。
操作結果：刪除 l 的第 i 個元素，並用 e 返回其值，l 的長度減1。
listtr**erse(l, visit( ))
初始條件：線性表 l 已存在，visit( ) 為元素的訪問函式。
操作結果：依次對 l 的每個元素呼叫函式 visit( )。
一旦 visit( ) 失敗，則操作失敗。
}adt graph
3.2 系統功能模組設計
約瑟夫環系統由6個功能模組組成：構造結點模組、建立鍊錶模組、出隊處理模組、約瑟夫環說明模組、選單模組、主函式模組。
1、 構造結點模組
lnode*creatnode(int m_num,int m_pwd)
2、 建立鍊錶模組
void createlist(lnode *pphead,int n)
3、 出隊處理模組
void jose(lnode *pphead,int m pwd)
4、 約瑟夫環說明輸出模組
void instruction()
5、 選單模組
void menu()
6、 主函式模組
int main()
。。。。。。（可以對每個功能分別介紹，並介紹每個模組使用時的輸入和輸出）
下面給出功能模組圖，如圖3-1所示。
（這個示例圖沒有畫完……）
圖3-1 校園導遊系統功能模組圖
3.3主要函式呼叫關係圖
（給出adt內基本操作的那些函式之間的函式呼叫關係圖）
如圖1所示
圖1約瑟夫環函式呼叫關係圖
3.4主介面設計
為了實現校園導遊系統，需要設計乙個含有多選單項的主控選單子程式，以鏈結系統中各個子專案的呼叫，為了方便使用者使用本系統，本系統主控選單的執行介面如圖3-3所示。
4.詳細設計
4.1 資料型別定義
迴圈鍊錶抽象資料型別定義
typedef struct lnode//定義單迴圈鍊錶中結點的結構
｛ int num;//編號
int pwd;//password
struct lnode *next;//指向下一結點的指標
｝lnode;
（分別給出各個型別的定義描述）
4.2 系統子程式詳細設計
（分別給出各個函式的演算法描述）
5.編碼實現及系統測試
（對各功能模組進行測試，給出截圖）
6.結果分析
（對所採用的資料結構和演算法，給出時間複雜度和空間複雜度的分析）
7.學習體會
8.源程式清單
[1][2]
資料結構課程設計報告
交通諮詢系統設計 不用輸入程式語句，也不用那個截圖 不用太著急，報告周五之前給我就行了 列印和壓縮包都要哈！對了，這段文字記得刪掉啊嘿嘿 題目名稱交通諮詢系統設計 院 系 管理學院 課程名稱資料結構課程設計 班級資訊 10 2 學生姓名呂德麗 指導教師李長雲 目錄一 需求分析及選題要求 3 1 問題...
資料結構課程設計報告
課程設計報告 課程名稱資料結構 課題名稱生死者遊戲 專業資訊管理與資訊系統 班級學號 姓名指導教師 2011 年 1 月 20 日 湖南工程學院 課程設計任務書 課程名稱資料結構 課題生死者遊戲 專業班級 學生姓名 學號指導老師 審批任務書下達日期 2011 年 1 月 3 日 任務完成日期 201...
《資料結構》課程設計報告
1.1 要求 1.2 題目分析 1.3相關 1.4執行結果 1.5總結 2.1 要求 2.2 題目分析 2.3相關 2.4執行結果 2.5總結 3.1 要求 3.2 題目分析 3.3相關 3.4執行結果 3.5總結 4.1 要求 4.2 題目分析 4.3相關 4.4執行結果 4.5總結 1 可以錄入...