約瑟夫環(huán)課程設(shè)計(jì)報(bào)告

1、<p>　　課 程 設(shè) 計(jì) 報(bào) 告</p><p>　　課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</p><p>　　課程設(shè)計(jì)題目：約瑟夫環(huán)</p><p><b>　　院（系）：</b></p><p><b>　　專 業(yè)： </b></p><p><b>

2、;　　班 級(jí)：</b></p><p><b>　　學(xué) 號(hào)：</b></p><p><b>　　姓 名：</b></p><p><b>　　指導(dǎo)教師：</b></p><p><b>　　目 錄</b></p&

3、gt;<p>　　1 課程設(shè)計(jì)介紹1</p><p>　　1.1 課程設(shè)計(jì)內(nèi)容1</p><p>　　1.2 課程設(shè)計(jì)要求1</p><p>　　2 課程設(shè)計(jì)原理2</p><p>　　2.1 課設(shè)題目粗略分析2</p><p>　　2.2 原理圖介紹2</p><

4、p>　　2.2.1 功能模塊圖（如圖2.1）2</p><p>　　2.2.2 流程圖分析3</p><p>　　3 數(shù)據(jù)結(jié)構(gòu)分析5</p><p>　　3.1 存儲(chǔ)結(jié)構(gòu)5</p><p>　　3.2 算法描述5</p><p>　　4 調(diào)試與分析6</p><p>　

5、　4.1 調(diào)試過程6</p><p>　　4.2 程序執(zhí)行過程6</p><p><b>　　參考文獻(xiàn)8</b></p><p>　　附 錄（關(guān)鍵部分程序清單）9</p><p><b>　　1 課程設(shè)計(jì)介紹</b></p><p>　　1.1 課程設(shè)計(jì)內(nèi)容

6、</p><p>　　編號(hào)為1,2，……，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他的順時(shí)針方向上的下一個(gè)開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止，設(shè)計(jì)一個(gè)程序求出出列順序。使用單循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)</p><p>　

7、　分析：由題意可以將每個(gè)人看做鏈表上的一個(gè)節(jié)點(diǎn)，每個(gè)人持有的密碼即為每個(gè)節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)；相鄰的人之間存在連結(jié)關(guān)系，即鏈表的兩個(gè)相鄰節(jié)點(diǎn)之間由指針來進(jìn)行關(guān)聯(lián)；最后一個(gè)人和第一個(gè)人也存在連結(jié)關(guān)系，即鏈表的末尾節(jié)點(diǎn)和頭結(jié)點(diǎn)相連構(gòu)成了單循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)。執(zhí)行報(bào)數(shù)過程可以看做一個(gè)單獨(dú)指針依次指向每一個(gè)節(jié)點(diǎn)，有人出列即刪除掉鏈表中相應(yīng)的節(jié)點(diǎn)。</p><p>　　1.2 課程設(shè)計(jì)要求</p><p>

8、;　　1.參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。</p><p>　　2.交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。</p><p><b>　　2 課程設(shè)計(jì)原理</b></p><p>　　2.1 課設(shè)題目粗略分析</p><p>　　根據(jù)課設(shè)題目要求，程序應(yīng)該分為兩大部分：</p><p>　　1、單

9、循環(huán)鏈表儲(chǔ)存結(jié)構(gòu)的建立：建立所需的單循環(huán)鏈表數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，對(duì)每個(gè)節(jié)點(diǎn)輸入所需的密碼、序號(hào)數(shù)據(jù)并通過指針連接成單循環(huán)鏈表。</p><p>　　2、實(shí)現(xiàn)約瑟夫環(huán)數(shù)據(jù)出列順序的算法：依照題目要求按照?qǐng)?bào)數(shù)上限對(duì)節(jié)點(diǎn)進(jìn)行查找和刪除操作，按順序輸出出列的節(jié)點(diǎn)序號(hào)，依照每次出列的節(jié)點(diǎn)存儲(chǔ)的密碼修改報(bào)數(shù)上限循環(huán)操作直到全部節(jié)點(diǎn)出列完畢程序運(yùn)行結(jié)束。</p><p>　　2.2 原理圖介紹</p&

10、gt;<p>　　2.2.1 功能模塊圖（如圖2.1）</p><p>　　圖2.1 功能模塊圖</p><p>　　2.2.2 流程圖分析</p><p>　　1.主程序圖，如圖2.2：首先建立單循環(huán)鏈表作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)并存儲(chǔ)數(shù)據(jù)，然后如果執(zhí)行報(bào)數(shù)。如果鏈表中剩余節(jié)點(diǎn)數(shù)大于1，執(zhí)行報(bào)數(shù)操作，得到節(jié)點(diǎn)的序號(hào)數(shù)據(jù)并輸出；若鏈表中只剩一個(gè)節(jié)點(diǎn)，輸出節(jié)點(diǎn)的

11、序號(hào)數(shù)據(jù)，程序運(yùn)行結(jié)束。</p><p>　　圖2.2 主程序圖</p><p>　　2.構(gòu)建單循環(huán)鏈表流程圖，如圖2.3：首先為鏈表存儲(chǔ)空間，然后判斷節(jié)點(diǎn)數(shù)是否達(dá)到上限，若沒有到達(dá)上限，構(gòu)建新節(jié)點(diǎn)；若已到達(dá)上限，將末尾節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)形成單循環(huán)鏈表并結(jié)束建立鏈表操作。</p><p>　　圖2.3構(gòu)建單循環(huán)鏈表流程圖</p><p>

12、<b>　　3 數(shù)據(jù)結(jié)構(gòu)分析</b></p><p><b>　　3.1 存儲(chǔ)結(jié)構(gòu)</b></p><p>　　typedef struct LNode</p><p><b>　　{</b></p><p>　　int data; //每個(gè)人持有的密碼</p&g

13、t;<p>　　int num; //每個(gè)人的編號(hào)</p><p>　　struct LNode *next; //指向下一個(gè)節(jié)點(diǎn)的指針</p><p>　　}LNode, *LinkList; //定義一個(gè)結(jié)構(gòu)體為一個(gè)持有密碼的人</p><p><b>　　3.2 算法描述</b></p><

14、p>　　1.構(gòu)建單循環(huán)鏈表：首先定義結(jié)構(gòu)體節(jié)點(diǎn)指針節(jié)點(diǎn)p，鏈表L，頭指針head。使head指向L的頭結(jié)點(diǎn)，p指向L。對(duì)結(jié)構(gòu)體p的數(shù)據(jù)部分進(jìn)行輸入賦值作為L(zhǎng)的一個(gè)節(jié)點(diǎn)然后向后移一位。循環(huán)此步操作形成單鏈表。最后將末尾節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)形成單循環(huán)鏈表。</p><p>　　2.約瑟夫環(huán)出列操作：首先定義指針J和K，指針J指向單循環(huán)鏈表的第一個(gè)節(jié)點(diǎn)，隨機(jī)生成一個(gè)報(bào)數(shù)上限m值。將指針p向后撥m-1次，此時(shí)p所指

15、向節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)即為要出列的節(jié)點(diǎn)，使指針K指向該節(jié)點(diǎn)，將這個(gè)節(jié)點(diǎn)從鏈表中刪除，然后讀取其中存儲(chǔ)的序號(hào)數(shù)據(jù)輸出，讀取其中存儲(chǔ)的密碼作為新的m值。然后繼續(xù)反復(fù)執(zhí)行撥指針p，出列節(jié)點(diǎn)，讀取數(shù)據(jù)操作，直到鏈表中只剩下一個(gè)節(jié)點(diǎn)停止循環(huán)操作，此時(shí)輸出最后一個(gè)節(jié)點(diǎn)中的序號(hào)數(shù)據(jù)完成全部出列操作。</p><p><b>　　4 調(diào)試與分析</b></p><p><b>

16、;　　4.1 調(diào)試過程</b></p><p>　　調(diào)試過程中出現(xiàn)error C2065：’rand’: undeclared identifier報(bào)錯(cuò)，在添加預(yù)處理命令#includes “time.h”后正常執(zhí)行；</p><p>　　在執(zhí)行過程中出現(xiàn)極大數(shù)據(jù)，發(fā)現(xiàn)構(gòu)建循環(huán)鏈表時(shí)將末尾指針指向了頭結(jié)點(diǎn)，改為指向頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)之后正常運(yùn)行；</p><

17、;p>　　4.2 程序執(zhí)行過程</p><p>　　1.如圖4.1所示，當(dāng)輸入人數(shù)為5，每個(gè)人所持有的密碼依次為2、4、6、8、10時(shí)，輸出結(jié)果：出列順序?yàn)椋?->3->2->5->4，程序運(yùn)行正確。</p><p>　　圖4.1 當(dāng)人數(shù)為5時(shí)的程序運(yùn)行結(jié)果</p><p>　　2.如圖4.2所示，當(dāng)輸入人數(shù)為10，每個(gè)人所持有的密碼

18、依次為9、1、5、7、3、6、8、2、4、10時(shí)，輸出結(jié)果：出列順序?yàn)椋?->10->2->3->9->6->1->7->5->4，程序運(yùn)行正確。</p><p>　　圖4.2當(dāng)人數(shù)為10時(shí)的程序運(yùn)行結(jié)果</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏，吳偉

19、民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社，2007.</p><p>　　[2] 張長(zhǎng)海，陳娟. C程序設(shè)計(jì)[M]. 北京：高等教育出版社，2004. </p><p>　　[3] 譚浩強(qiáng). C程序設(shè)計(jì)[M]. 北京：清華大學(xué)出版社，2005.</p><p>　　[4] 蘇士華，黃學(xué)俊. 數(shù)據(jù)結(jié)構(gòu) 解析.習(xí)題.課程設(shè)計(jì)[M]. 合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2

20、009.</p><p>　　[5] 張瑞軍. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社，2009.</p><p>　　[6] 劉懷亮. 數(shù)據(jù)結(jié)構(gòu) 習(xí)題解析與實(shí)驗(yàn)指導(dǎo)[M]. 北京：冶金出版社，2009.</p><p>　　[7] 王敬華，林萍，張清國(guó). C語言程序設(shè)計(jì)教程（第二版）[M]. 背景：清華大學(xué)出版社，2005.</p><p>

21、;　　附 錄（關(guān)鍵部分程序清單）</p><p>　　#include <stdafx.h></p><p>　　#include <stdio.h></p><p>　　#include "stdlib.h"</p><p>　　#include <string.h></p&

22、gt;<p>　　#include <malloc.h></p><p>　　#include <math.h></p><p>　　#include "time.h"</p><p>　　typedef struct LNode</p><p><b>　　{</b&

23、gt;</p><p><b>　　int data;</b></p><p><b>　　int num;</b></p><p>　　struct LNode *next;</p><p>　　}LNode, *LinkList;</p><p>　　void creat

24、elist(LinkList &L,int n)</p><p><b>　　{</b></p><p>　　LinkList p,head;</p><p><b>　　int i,a;</b></p><p>　　L=(LinkList )malloc(sizeof(LNode));&l

25、t;/p><p><b>　　head=L;</b></p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　p=(LinkList )malloc(sizeof(LNode));</p><p>　　printf(

26、"請(qǐng)輸入第%d個(gè)人的密碼\n",i+1);</p><p>　　scanf("%d",&a);</p><p>　　p->data=a;</p><p>　　p->num=i+1;</p><p>　　L->next=p;</p><p>　　p->

27、;next=NULL;</p><p><b>　　L=p;</b></p><p><b>　　}</b></p><p>　　p->next=head->next;</p><p><b>　　}</b></p><p>　　void m

28、ain()</p><p><b>　　{</b></p><p>　　int n,m,x,k,l;</p><p>　　LinkList J,L,K;</p><p>　　printf("請(qǐng)輸入人數(shù)：\n");</p><p>　　scanf("%d",&

29、amp;n);</p><p>　　createlist(L,n);</p><p><b>　　J=L;</b></p><p>　　srand((unsigned) time(NULL));</p><p>　　m=rand()%n;</p><p>　　printf("出列順序?yàn)椋?/p>

30、");</p><p>　　for (l=0;l<n-1;l++)</p><p><b>　　{</b></p><p>　　for (k=0;k<m-1;k++)</p><p><b>　　{</b></p><p>　　J=J->next;

31、</p><p><b>　　}</b></p><p>　　K=J->next;</p><p>　　J->next=K->next;</p><p><b>　　x=K->num;</b></p><p>　　printf("%d->

32、;",x);</p><p>　　m=K->data;</p><p><b>　　free(K);</b></p><p><b>　　}</b></p><p><b>　　x=J->num;</b></p><p>　　pri