數(shù)據(jù)結(jié)構(gòu)約瑟夫環(huán)模擬課程設(shè)計(jì)

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>　　院（系）：計(jì)算機(jī)學(xué)院</p><p>　　專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)</p><p><b>　　1 課程設(shè)計(jì)介紹</b>&

2、lt;/p><p>　　1.1 課程設(shè)計(jì)內(nèi)容</p><p>　　由一個(gè)雙向循環(huán)鏈表模擬m個(gè)人站成一個(gè)圈，輸入一個(gè)數(shù)n，n>0正向前進(jìn)，n<0逆向前進(jìn)，當(dāng)前人由1開始計(jì)數(shù)，每行進(jìn)一個(gè)人，計(jì)數(shù)加1，數(shù)到|n|的人出圈，然后依原行進(jìn)方向繼續(xù)由1開始計(jì)數(shù)，重復(fù)上述過程，直到所有人都出圈，輸出其出圈序列。</p><p>　　1.2 課程設(shè)計(jì)要求</p>

3、<p>　　程序正常運(yùn)行,并將出圈順序以動(dòng)態(tài)方法表示出來。</p><p><b>　　2 課程設(shè)計(jì)原理</b></p><p>　　2.1 課設(shè)題目粗略分析</p><p>　　根據(jù)課設(shè)題目要求，將整體程序分為查找和刪除兩大模塊：</p><p>　　在查找模塊中，當(dāng)輸入的n的數(shù)值大于0時(shí)，鏈表正向循環(huán)

4、且輸出第n人所在位置并調(diào)用刪除模塊釋放當(dāng)前節(jié)點(diǎn)，直到所有人都出圈；當(dāng)輸入的n值小于0時(shí)鏈表逆向循環(huán)且輸出第n人所在位置并調(diào)用刪除模塊釋放當(dāng)前節(jié)點(diǎn)，直到所有人出圈。</p><p>　　刪除模塊負(fù)責(zé)將查找模塊找到的當(dāng)前人的節(jié)點(diǎn)進(jìn)行刪除并返回下一個(gè)人的位置。</p><p><b>　　2.2 原理圖介紹</b></p><p>　　2.2.1 功

5、能模塊圖</p><p>　　如圖2.1所示為約瑟夫環(huán)模擬程序的功能模塊圖，函數(shù)包括查找模塊和刪除模塊，主函數(shù)中調(diào)用了查找模塊， 查找模塊中調(diào)用了刪除模塊。</p><p>　　圖2.1 功能模塊圖</p><p>　　2.2.2 流程圖分析</p><p>　　主程序是整個(gè)程序的核心部分，通過對(duì)子函數(shù)JosephLink的調(diào)用，完成整個(gè)程序

6、，主函數(shù)流程圖表示如圖2.2所示： </p><p>　　圖2.2主函數(shù)流程圖</p><p>　　子函數(shù)JosephLink，主要功能為從當(dāng)前人開始查找第到|n|個(gè)人的位置并輸出第|n|個(gè)人所在位置，然后將第|n|個(gè)節(jié)點(diǎn)傳入函數(shù)del_link，流程圖如圖2.3所示：</p><p>　　圖2.3子函數(shù)JosephLink流程圖</p><p&

7、gt;　　子函數(shù)del_link1，主要功能為將由函數(shù)JosephLink查找到的節(jié)點(diǎn)進(jìn)行刪除操作并將該節(jié)點(diǎn)的下一節(jié)點(diǎn)返回到函數(shù)JosephLink中，流程圖如圖2.4所示：</p><p>　　圖2.4 del_link1函數(shù)流程圖</p><p>　　子函數(shù)del_link2，主要功能為將由函數(shù)JosephLink查找到的節(jié)點(diǎn)進(jìn)行刪除操作并將該節(jié)點(diǎn)的上一節(jié)點(diǎn)返回到函數(shù)JosephLin

8、k中，流程圖如圖2.5所示：</p><p>　　圖2.5 del_link2函數(shù)流程圖</p><p><b>　　3 數(shù)據(jù)結(jié)構(gòu)分析</b></p><p><b>　　3.1 存儲(chǔ)結(jié)構(gòu)</b></p><p>　　程序中主要用到的存儲(chǔ)結(jié)構(gòu)為雙向循環(huán)鏈表，其存儲(chǔ)結(jié)構(gòu)體為：</p>

9、<p>　　typedef struct DulNode{</p><p><b>　　int data;</b></p><p>　　struct DulNode*prev;</p><p>　　struct DulNode*next;</p><p><b>　　}DulNode;</b&g

10、t;</p><p>　　該結(jié)構(gòu)體包括數(shù)據(jù)域和前指針prev域與后指針next域。</p><p><b>　　3.2 算法描述</b></p><p>　　創(chuàng)建雙向循環(huán)鏈表，簡單算法說明如下：</p><p>　　person=(DulNode*)malloc(sizeof(DulNode)); //為第一個(gè)節(jié)點(diǎn)

11、申請(qǐng)空間</p><p>　　person->data=1; // data記錄當(dāng)前人的位置</p><p>　　person->next=person->prev=person;</p><p><b>　　s=person;</b></p><p&

12、gt;　　for(i=2;i<=m;i++){ //創(chuàng)建m-1個(gè)節(jié)點(diǎn)</p><p><b>　　r=s;</b></p><p>　　s=(DulNode*)malloc(sizeof(DulNode));</p><p>　　s->data=i;</p><p&

13、gt;　　s->prev=r; //依次將新生成的節(jié)點(diǎn)插入循環(huán)鏈表中</p><p>　　r->next->prev=s;</p><p>　　s->next=r->next;</p><p>　　r->next=s;}</p><p>　　刪除節(jié)點(diǎn)tmp的算法

14、，如下所示：</p><p>　　tmp->prev->next=tmp->next; //將tmp前一個(gè)節(jié)點(diǎn)的next指 </p><p>　　//針指向tmp的下一個(gè)節(jié)點(diǎn)</p><p>　　tmp->next->prev=tmp->prev;//將tmp下一個(gè)節(jié)

15、點(diǎn)的prev指針//指向tmp的上一個(gè)節(jié)點(diǎn)</p><p><b>　　4 調(diào)試與分析</b></p><p><b>　　4.1 調(diào)試過程</b></p><p>　　在調(diào)試程序時(shí)主要遇到以下幾個(gè)問題：</p><p>　　調(diào)試時(shí)發(fā)現(xiàn)在鏈表上刪除節(jié)點(diǎn)之后無法繼續(xù)將下一個(gè)節(jié)點(diǎn)作為開始來循環(huán)而且當(dāng)輸

16、入的n的值為n的整數(shù)倍時(shí)無法正常輸出出圈序列。</p><p>　　問題分析及解決辦法：專門創(chuàng)建一個(gè)刪除函數(shù)，負(fù)責(zé)刪除傳入的節(jié)點(diǎn)并返回刪除節(jié)點(diǎn)的下一節(jié)點(diǎn)，另外申請(qǐng)一個(gè)節(jié)點(diǎn)傳入鏈表的表頭。</p><p>　　當(dāng)鏈表中節(jié)點(diǎn)只剩下一個(gè)的時(shí)候發(fā)現(xiàn)無法輸出最后節(jié)點(diǎn)所在的位置。</p><p>　　問題分析及解決辦法：在循環(huán)中添加一個(gè)判斷條件，當(dāng)鏈表中只剩唯一一個(gè)節(jié)點(diǎn)的時(shí)候單

17、獨(dú)輸出節(jié)點(diǎn)所在的位置。</p><p>　　調(diào)試過程中發(fā)現(xiàn)在刪除第一個(gè)節(jié)點(diǎn)之后鏈表不能繼續(xù)前進(jìn)n個(gè)位置并輸出第n個(gè)位置的序列。 問題分析及解決辦法：當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)被刪除后，將第一個(gè)節(jié)點(diǎn)后的節(jié)點(diǎn)作為頭結(jié)點(diǎn)。</p><p>　　調(diào)試過程中發(fā)現(xiàn)程序運(yùn)行時(shí)不能按照正常的順序輸出出圈序列，后經(jīng)過多次細(xì)心調(diào)試及同學(xué)幫助才發(fā)現(xiàn)是全局變量和局域變量發(fā)生沖突而導(dǎo)致。</p

18、><p>　　解決辦法：將全局變量和局域變量分別用不同的字母表示加以區(qū)分，經(jīng)過調(diào)試后輸出正常。</p><p><b>　　5 運(yùn)行結(jié)果</b></p><p><b>　　如圖：</b></p><p><b>　　參考文獻(xiàn)</b></p><p>　　

19、[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2007.</p><p>　　[2] 呂英國.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，2006. </p><p>　　[3] 徐寶文 李志.C程序設(shè)計(jì)語言[M].北京：機(jī)械工業(yè)出版社，2004.</p><p>　　[4] 張長海，陳娟.C程序設(shè)計(jì)[M].北京：高等教育出版社，2004

20、.</p><p>　　[5] 譚浩強(qiáng).C程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2005.</p><p>　　[6] 張千帆.數(shù)據(jù)結(jié)構(gòu)與算法（C語言實(shí)現(xiàn)）[M].北京：科學(xué)出版社，2009</p><p>　　[7] 徐寶文 李志 . C程序設(shè)計(jì)語言[M] . 北京：機(jī)械工業(yè)出版社，2004</p><p>　　附 錄（關(guān)鍵部分程序清單

21、）</p><p><b>　　程序代碼</b></p><p>　　#include<stdio.h> </p><p>　　#include<stdlib.h></p><p>　　#include<malloc.h></p><p>　　typede

22、f struct DulNode</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct DulNode*prev;</p><p>　　struct DulNode*next;</p><p><

23、;b>　　}DulNode;</b></p><p>　　DulNode*del_link1(DulNode*person,DulNode*tmp,int m)</p><p>　　{ /* n>0 刪除第n個(gè)節(jié)點(diǎn)打印本次操作結(jié)果并返回后一個(gè)節(jié)點(diǎn)信息*/</p><p>　　DulN

24、ode*s=tmp;</p><p><b>　　int i=0;</b></p><p>　　DulNode*head;</p><p>　　if(tmp!=person)</p><p>　　head=person;</p><p><b>　　else</b></

25、p><p>　　head=person->next;</p><p>　　tmp->prev->next=tmp->next;</p><p>　　tmp->next->prev=tmp->prev;</p><p>　　s=s->next;</p><p>　　free(t

26、mp);</p><p>　　printf("\n");</p><p><b>　　if(m>1)</b></p><p><b>　　{</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{

27、</b></p><p>　　printf("%d ",head->data);</p><p>　　head=head->next;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p&

28、gt;<b>　　}</b></p><p><b>　　return s;</b></p><p><b>　　}</b></p><p>　　DulNode*del_link2(DulNode*person,DulNode*tmp,int m)</p><p>　　{

29、 /* n<0 刪除第n個(gè)節(jié)點(diǎn)打印本次操作結(jié)果并返回前一個(gè)節(jié)點(diǎn)信息*/</p><p>　　DulNode*s=tmp;</p><p><b>　　int i=0;</b></p><p>　　DulNode*head;</p><p>　　if(tmp!

30、=person)</p><p>　　head=person;</p><p><b>　　else </b></p><p>　　head=person->next;</p><p>　　tmp->prev->next=tmp->next;</p><p>　　tmp-&

31、gt;next->prev=tmp->prev;</p><p>　　s=s->prev;</p><p>　　free(tmp);</p><p>　　printf("\n");</p><p><b>　　if(m>1)</b></p><p>&l

32、t;b>　　{</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　printf("%d ",head->data);</p><p>　　head=head->next;</p>

33、<p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　return s;</b></p><p><b>　　}</b></p

34、><p>　　void JosephLink(DulNode*person,int m,int n)</p><p>　　{ /* 查找并打印第n個(gè)節(jié)點(diǎn)*/</p><p><b>　　int i;</b></p><p>　　DulNode*tmp=person;</p&g

35、t;<p><b>　　if(n>0)</b></p><p><b>　　{</b></p><p>　　while(tmp->next!=tmp)</p><p><b>　　{</b></p><p>　　for(i=1;i<n;i++)&

36、lt;/p><p><b>　　{</b></p><p>　　tmp=tmp->next;</p><p><b>　　}</b></p><p>　　printf("出圈數(shù)據(jù)為:\n%d \n圈中剩余數(shù)據(jù)為:",tmp->data);</p><p

37、><b>　　m--;</b></p><p>　　if(tmp==person)</p><p>　　person=person->next;</p><p>　　tmp=del_link1(person,tmp,m);</p><p><b>　　}</b></p>&

38、lt;p>　　printf("%d\n",tmp->data);</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　while(tmp->pre

39、v!=tmp)</p><p><b>　　{</b></p><p>　　for(i=1;i<-n;i++)</p><p><b>　　{</b></p><p>　　tmp=tmp->prev;</p><p><b>　　}</b>&

40、lt;/p><p>　　printf("出圈數(shù)據(jù)為:\n%d \n圈中剩余數(shù)據(jù)為:",tmp->data);</p><p><b>　　m--;</b></p><p>　　if(tmp==person)</p><p>　　person=person->next;</p>&

41、lt;p>　　tmp=del_link2(person,tmp,m);</p><p><b>　　}</b></p><p>　　printf("%d\n",tmp->data);</p><p><b>　　}</b></p><p><b>　　}&l

42、t;/b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　DulNode*person,*s,*r;</p><p>　　int i,m,n;</p><p>　　printf("請(qǐng)輸入人數(shù)m:\n");</

43、p><p>　　scanf("%d",&m);</p><p>　　printf("請(qǐng)輸入n的值:\n");</p><p>　　scanf("%d",&n);</p><p>　　printf("約瑟夫環(huán)為:\n");</p><

44、p>　　if(m%2==1)</p><p><b>　　{</b></p><p>　　for(i=1;i<=m/2+1;i++)</p><p>　　printf("%d ",i);</p><p>　　printf("\n");</p><p&

45、gt;　　for(i=m;i>m/2+1;i--)</p><p>　　printf("%d ",i);</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p>

46、<p>　　for(i=1;i<=m/2;i++)</p><p>　　printf("%d ",i);</p><p>　　printf("\n");</p><p>　　for(i=m;i>m/2;i--)</p><p>　　printf("%d ",i

47、);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　printf("出圈動(dòng)態(tài)為:\n");</p><p>　　person=(DulNode*)malloc(sizeof(DulNode));</p>&

48、lt;p>　　person->data=1;</p><p>　　person->next=person->prev=person;</p><p><b>　　s=person;</b></p><p>　　for(i=2;i<=m;i++)</p><p><b>　　{<

49、;/b></p><p><b>　　r=s;</b></p><p>　　s=(DulNode*)malloc(sizeof(DulNode));</p><p>　　s->data=i;</p><p>　　s->prev=r;</p><p>　　r->next-&g

50、t;prev=s;</p><p>　　s->next=r->next;</p><p>　　r->next=s;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　JosephLink(person,