數(shù)據(jù)結構約瑟夫環(huán)模擬課程設計

1、<p>　　課 程 設 計 報 告</p><p>　　課程設計名稱：數(shù)據(jù)結構課程設計</p><p>　　課程設計題目： 約瑟夫環(huán)模擬</p><p>　　院（系）：計算機學院</p><p>　　專 業(yè)：計算機科學與技術</p><p><b>　　1 課程設計介紹</b>&

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

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

4、且輸出第n人所在位置并調(diào)用刪除模塊釋放當前節(jié)點，直到所有人都出圈；當輸入的n值小于0時鏈表逆向循環(huán)且輸出第n人所在位置并調(diào)用刪除模塊釋放當前節(jié)點，直到所有人出圈。</p><p>　　刪除模塊負責將查找模塊找到的當前人的節(jié)點進行刪除并返回下一個人的位置。</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>　　主程序是整個程序的核心部分，通過對子函數(shù)JosephLink的調(diào)用，完成整個程序

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

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

8、k中，流程圖如圖2.5所示：</p><p>　　圖2.5 del_link2函數(shù)流程圖</p><p><b>　　3 數(shù)據(jù)結構分析</b></p><p><b>　　3.1 存儲結構</b></p><p>　　程序中主要用到的存儲結構為雙向循環(huán)鏈表，其存儲結構體為：</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>　　該結構體包括數(shù)據(jù)域和前指針prev域與后指針next域。</p><p><b>　　3.2 算法描述</b></p><p>　　創(chuàng)建雙向循環(huán)鏈表，簡單算法說明如下：</p><p>　　person=(DulNode*)malloc(sizeof(DulNode)); //為第一個節(jié)點

11、申請空間</p><p>　　person->data=1; // data記錄當前人的位置</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個節(jié)點</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é)點插入循環(huán)鏈表中</p><p>　　r->next->prev=s;</p><p>　　s->next=r->next;</p><p>　　r->next=s;}</p><p>　　刪除節(jié)點tmp的算法

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

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

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

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

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

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

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

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個節(jié)點打印本次操作結果并返回后一個節(jié)點信息*/</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個節(jié)點打印本次操作結果并返回前一個節(jié)點信息*/</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個節(jié)點*/</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("請輸入人數(shù)m:\n");</

43、p><p>　　scanf("%d",&m);</p><p>　　printf("請輸入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("出圈動態(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,