武漢工業學院
數學與計算機學院
資料結構課程設計
設計題目：約瑟夫環
專業大類計算機
班級計算機6班
學號 100702129
姓名王元
指導教師李禹生
2023年 9月 3 日
題目：約瑟夫環
問題描述：
編號為1,2，…..，n的n個人按順時針方向圍坐圈，每個人持有乙個密碼（正整數）。一開始任選乙個正整數作為報數上限值m，從第乙個人開始按順時針方向自1開始順序報數，報到m時停止報數。
報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下乙個人開始重新重新從1報數，如此下去，直至所有人全部出列為止。
基本要求：
⑴ 建立模型，確定儲存結構；
⑵ 對任意 n個人，密碼為 m ，實現約瑟夫環問題；
⑶ 出圈的順序可以依次輸出，也可以用乙個陣列儲存。
設計指導思想：
首先，設計實現約瑟夫環問題的儲存結構。由於約瑟夫環問題本身具有迴圈性質，考慮採用迴圈鍊錶，為了統一對錶中任意結點的操作，迴圈鍊錶不帶頭結點。 其次，建立乙個不帶頭結點的迴圈鍊錶並由頭指標 first 指示。
最後，設計約瑟夫環問題的演算法。下面給出偽**描述，操作示意圖如圖 2-1 所示。
本方案通過建立單迴圈鍊錶模擬了約瑟夫問題；首先，建立乙個結構體node，然後給他開闢乙個儲存空間；利用頭指標head標記鍊錶，利用尾指標向後移將建立的結點連線成我們需要的單迴圈鍊錶，
過程如下：
約瑟夫問題中的人數個數即為鍊錶的長度，鍊錶中node->num 編號n，node->data為每個人的密碼。建立單迴圈鍊錶後，通過初始報數上限找到出列的結點，輸出該結點的node->num值，將該結點中的data中數作為新密碼開始下乙個步的開始，將該結點從鍊錶中刪除，並釋放該結點的空間。重複此過程，直到剩下最後乙個結點，就直接將該結點中的num值輸出，刪除該結點，並釋放該結點的空間。
輸出的num值即為約瑟夫中人的編號。
typedef struct node
listnode;
定義乙個結構體用來儲存學生的編號和所攜帶的密碼
for(i=1;i<=n;i++)
定義指標p1，然後建立乙個新結點並將p1->next指向它的位址，然後將這個位址賦給p1，最後將head->next賦給p1->next,構成乙個單迴圈鍊錶，並不斷在尾部插入新的結點，直至所有人都進入迴圈鍊錶中，而且在迴圈的過程中給結點的num和data成員賦值
do //報數過程中將指標p1指向下一位
p2=p1->next;
p1->next=p2->next;//將報m的人的結點從鍊錶中刪去
printf("編號為%d的人出列，他的密碼%d作為新的m值\n",p2->num,p2->data);//報數為m的人出列
m=p2->data;//報數為m的人的密碼作為新的m值
free(p2);//釋放報m的人的結點
}while(p1->next!=p1);//當p1->next指向的位址是它自己的位址，所有報數結束
定義指標p1用以迴圈鍊錶，定義變數k計數，指標p1每移動一次，k加1，直到k==m時，輸出指標p1所指向的節點序號，也就是令這個「人」出列，p2指向該節點上一節點，令上一節點next域指向該節點下一節點，然後刪除該節點，令頭節點p1指向該節點下一節點作為再次報數初始「人」，再令k歸1，繼續迴圈。知道p1->next= =p1時，表示所有「人」出列完畢，刪除最後的節點後跳出迴圈
測試資料：
n=4, 4個人的密碼依次為4, 3，8, 6, 首先m=6
輸出結果：
測試資料：
n=7，7個人的密碼依次為3，1，7，2，48，4，首先m=20
輸出結果：
為期一周的課程設計快結束了，通過這次資料結構課程設計，我感受最深的就是對於迴圈鍊錶的使用，可以說對迴圈鍊錶有了比以前更進一步的認識，以前只是一知半解的，如果只給個題目自己根本不能把程式完整地編寫出來，所以這次課程設計最大的收穫就在於對迴圈鍊錶有了一定的理解，包括其中的一系列操作，如建立乙個迴圈鍊錶，刪除鍊錶中的乙個結點，增加乙個結點等。
在這次課程設計過程中需要我們一邊設計一邊探索，這這個過程當中我發現自己在資料結構方面知識掌握不夠深入，對一些基本概念不能很好的理解，對一些資料結構不能夠熟練的進行上機實現，這是自己比較薄弱的。學好基礎知識是理論付諸實踐的前提，這樣理論和實踐才能充分地結合起來。在以後的學習中，我還要努力改正，充分利用上機實驗的機會提高自己。
在程式的輸入的時候，因為自己對鍵盤的不熟練，**又很多很繁瑣，常常會產生放棄的念頭，從中我也感受到只有堅持到底，勝利才會出現。
在除錯程式的時候我也有所體會，雖然約瑟夫環問題不是很難，但除錯的時候還是會出現很多錯誤，因此我們不能認為容易就不認真對待。在以後的學習中，要能不斷發現問題，提出問題，解決問題，從不足之處出發，在不斷學習中提高自己。
#include<>
#include<>
typedef struct node
listnode;
typedef listnode *linklist;
void main()
do//報數過程中將指標p1指向下一位
p2=p1->next;
p1->next=p2->next;//將報m的人的結點從鍊錶中刪去
printf("編號為%d的人出列，他的密碼%d作為新的m值\n",p2->num,p2->data);//報數為m的人出列
m=p2->data;//報數為m的人的密碼作為新的m值
free(p2);//釋放報m的人的結點
}while(p1->next!=p1);//當p1->next指向的位址是它自己的位址，所有報數結束
printf("編號為%d的人出列，至此所有人出列完畢\n",p1->num);//至此所有人出列完畢
free(p1);//釋放最後乙個人的結點
free(head);//釋放頭結點
printf("程式結束\n");}
資料結構約瑟夫環上機報告
題目 約瑟夫環 班級 030914班 姓名 吳多堅 學號 03091443 完成日期 2010 5 12 一 需求分析 1 建立鍊錶的型別 根據題意，操作物件是圍成一圈的同學，數數時以一圈為迴圈，因此建立的鍊錶為迴圈鍊錶最為合適。2 每個結點所應包含的元素 因為每位同學的座位都有對應固定的易個座位號...
資料結構課程設計報告
交通諮詢系統設計 不用輸入程式語句，也不用那個截圖 不用太著急，報告周五之前給我就行了 列印和壓縮包都要哈！對了，這段文字記得刪掉啊嘿嘿 題目名稱交通諮詢系統設計 院 系 管理學院 課程名稱資料結構課程設計 班級資訊 10 2 學生姓名呂德麗 指導教師李長雲 目錄一 需求分析及選題要求 3 1 問題...
資料結構課程設計報告
課程設計報告 課程名稱資料結構 課題名稱生死者遊戲 專業資訊管理與資訊系統 班級學號 姓名指導教師 2011 年 1 月 20 日 湖南工程學院 課程設計任務書 課程名稱資料結構 課題生死者遊戲 專業班級 學生姓名 學號指導老師 審批任務書下達日期 2011 年 1 月 3 日 任務完成日期 201...