數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告—敢死隊的問題

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：16 大?。?87.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告—敢死隊的問題_第1頁

已閱讀1頁，還剩15頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　年月日　　敢死隊問題　　問題描述　　有M個敢死隊員要炸掉敵人的一碉堡，

2、誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決定哪個戰(zhàn)士去執(zhí)行任務(wù)。如果前一個戰(zhàn)士沒完成任務(wù)，則要再派一個戰(zhàn)士上去?，F(xiàn)給每個戰(zhàn)士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當數(shù)到5時，對應的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再從下一個戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。　　排長是不愿意去的，假設(shè)排長為1號，請你設(shè)計一程

3、序，求出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。　　要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。　　一、單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)　　(一) 需求分析　　1.本程序任務(wù)是通過輸入任意隊伍人數(shù)n和報數(shù)上限m，輸出使排長最后一

4、個執(zhí)行任務(wù)而開始記數(shù)的初始位置。首先輸入隊伍人數(shù)n，然后輸入報數(shù)上限m(m<=n),從1號開始報數(shù)，當達到報數(shù)上限時，那名士兵出列執(zhí)行任務(wù)，從下個人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊伍中的位置，記下該位置視為排長位置，則1號即可視為最先報數(shù)的人，通過數(shù)學計算即可獲得所求。　　2.功能模塊和流程： 　　1）功能模塊<

5、/b>　　該程序功能比較單一，主要是為解決敢死隊問題而設(shè)計。通過輸入隊伍人數(shù)和報數(shù)上限即可獲得開始報數(shù)的位置。　　2）程序流程　?。?）構(gòu)造鏈表（2）數(shù)據(jù)輸入（3）執(zhí)行刪除（4）輸出要求數(shù)值（5）結(jié)束　　3.數(shù)

6、據(jù)測試：　　當 n=10，m=5, 輸出結(jié)果為：要求的位置是：9。　　(二) 詳細設(shè)計　　1.算法設(shè)計：　　本程序其實質(zhì)是約瑟夫環(huán)問題。從排長位置即1號開始報數(shù)，共有n個人，達

7、到報數(shù)上限m=5的戰(zhàn)士出列，繼續(xù)進行報數(shù)，直到剩余最后一人，記下該位置為k。若將該位置視為排長位置，則原先的1號位置即位所有的開始報數(shù)的位置z。則z=n-k+2。　　2.以單循環(huán)鏈表為存儲結(jié)構(gòu)，包含三個模塊： 　?。?）主程序模塊 　?。?）構(gòu)造鏈表并初始化

8、;　?。?）刪除結(jié)點 　　3.結(jié)點類型和指針類型　　typedef struct node　　{　　int data;

9、;　　struct node *next;　　}LNode;/* 定義結(jié)點類型 */　　LNode *p;　　4.每個模塊的分析　?。?）主程序模塊：<

10、;/b>　　main()　　{　　LNode *p;　　int m,n,z,y;　　do&l

11、t;/b>　　{　　printf(" Please input the people number:\n");　　scanf ("%d",&n);　　}</

12、b>　　while (n<=0);　　do　　{　　printf(" Please input the excursion:\n");<

13、;p>　　scanf("%d",&m);　　}　　while (m<=0);　　if (n=1)　　printf("the position is

14、: 1");　　else　　{　　p=CREAT(n);　　y=DELETE(p,m);　　z=n-y+2;

15、;　　if(z%n==0) /* 排除特殊情況 */　　printf ("the position is:\n%d\n",z);　　else　　printf("the position is:\n%d\

16、n",(n-y+2)%n);　　}/* 通過數(shù)學思想求得實驗要求情況下的數(shù)值 */　　}　?。?）構(gòu)造單循環(huán)鏈表并初始化模塊：　　LNode* CREAT(int n) /* 創(chuàng)建循環(huán)鏈表 */<

17、;p>　　{　　LNode *s,*q,*t;　　int i;　　if(n!=0)　　{&

18、lt;p>　　t=q=(LNode *)malloc(sizeof(LNode));　　q->data=1;/* 生成第一個結(jié)點并使其data值為1 */　　for(i=2;i<=n;i++)　　{　　s=(LNod

19、e *)malloc(sizeof(LNode));/*自動生成結(jié)點*/　　q->next=s;　　q->next->data=i;/*給第i個結(jié)點賦值i*/　　q=q->next;　　}

20、　　q->next=t;　　}/* 生成后續(xù)結(jié)點，并使其data值即為它所在鏈表（隊伍）中的位置 */　　return t;　　}　?。?）刪除結(jié)點模塊：</p&g

21、t;　　DELETE (LNode* t,int m)/* 鏈表的刪除 */　　{　　LNode *a;int i;　　while (t->next!=t)　　{<

22、;/p>　　for (i=1;i<m-1;i++)/*查找要刪除結(jié)點的前一結(jié)點*/　　t=t->next;　　a=t->next;　　t->next=a->next;　　free(a);/*釋放結(jié)點*/</p

23、>　　t=t->next;　　}/* while循環(huán)依次刪除被點到的士兵 */　　printf("\n");　　return (t->data);　　}

24、　　(三) 調(diào)試分析：　　1.本程序運行后的結(jié)果應是如下提示：　　Exit please input '0' Or Go on 　　Please input the tatal of the team:<p&

25、gt;　　輸入隊伍總?cè)藬?shù)　　Please input the excursion:　　輸入間隔人數(shù)　　結(jié)果顯示：The wanted position is 　　選擇的位置&l

26、t;/b>　　2.在程序調(diào)試運行的過程中產(chǎn)生了各種各樣的問題，有的是多了空格，有的是拼寫錯誤，還有的是少了括號，類似的問題有很多。解決的辦法是一遍遍嘗試，不斷逐行逐句進行修改。　　例如程序調(diào)試過程中遇到警告：發(fā)現(xiàn)錯誤為 if(m=1)　　后改正為 if(m==1)程序運行正確了，運行如下：</

27、p>　　顯示輸出如圖：　　3.由程序分析可得：本程序時間復雜度為O（nm）!　　4.①在設(shè)計生成循環(huán)單鏈表時，考慮到程序結(jié)果需要士兵的位序，故將每個結(jié)點的data值設(shè)置為他們在隊列中的位置，方便返回。 　　②在刪除單鏈表時，如果在報數(shù)時直接數(shù)到出列

28、士兵則不方便鏈表的刪除，可設(shè)置i<m-1找到出列士兵的前一位執(zhí)行如下：　　for (i=1;i<m-1;i++)/*查找要刪除結(jié)點的前一結(jié)點*/　　t=t->next;　　a=t->next;　　t->next=a->next;<

29、/p>　　free(a);/*釋放結(jié)點*/　　t=t->next;　?、郏诔绦蛟O(shè)計前，如果按原題所設(shè)，則需設(shè)隊長為第一位，再分別測試從第幾個開始才能符合條件。現(xiàn)在改變思想，通過數(shù)學思想：單循環(huán)鏈表本身是一個循環(huán)體，可先求出當從第一個出發(fā)的話，求出每隔m個出去一個最后是誰未出列，然后再設(shè)置它為鏈頭，求出當他為隊首時從第幾

30、個開始方能使其不出列。(n-y+2)%n 即可實現(xiàn)這功能！　　5.經(jīng)驗與體會　　通過這次課程設(shè)計我又學到了很多東西,如程序的模塊化設(shè)計思想，同時也加深了對數(shù)據(jù)結(jié)構(gòu)這門課程的理解和學會了如何在實際中應用數(shù)據(jù)結(jié)構(gòu).　　這個方法是用單循環(huán)鏈表來做的，實現(xiàn)的方法是這樣的：首先從第一號

31、開始報數(shù)，循環(huán)到指定的偏移位置刪除結(jié)點，直至剩下一個結(jié)點。然后設(shè)計輸出，令這個位置為隊長位置，隊首為開始報數(shù)的位置，并按此輸出即為所求。這種方法大大的降低了時間復雜度，復雜度為O(mn)。　?。ㄎ澹y試結(jié)果　?。└郊?lt;/b>　　typedef

32、 struct node　　{　　int data;　　struct node *next;　　}LNode;/* 定義結(jié)點類型 */　　LNode* C

33、REAT(int n) /* 創(chuàng)建循環(huán)鏈表 */　　{　　LNode *s,*q,*t;　　int i;　　if(n!=0)<p

34、>　　{　　t=q=(LNode *)malloc(sizeof(LNode));　　q->data=1;/* 生成第一個結(jié)點并使其data值為1 */　　for(i=2;i<=n;i++)　　{&

35、lt;/b>　　s=(LNode *)malloc(sizeof(LNode));/*自動生成結(jié)點*/　　q->next=s;　　q->next->data=i;/*給第i個結(jié)點賦值i*/　　q=q->next;<

36、;p>　　}　　q->next=t;　　}/* 生成后續(xù)結(jié)點，并使其data值即為它所在鏈表（隊伍）中的位置 */　　return t;　　}&l

37、t;/p>　　DELETE (LNode* t,int m)/* 鏈表的刪除 */　　{　　LNode *a;int i;　　while (t->next!=t)　　{</b&

38、gt;　　for (i=1;i<m-1;i++)/*查找要刪除結(jié)點的前一結(jié)點*/　　t=t->next;　　a=t->next;　　t->next=a->next;　　free(a);/*釋放結(jié)點*/

39、　　t=t->next;　　}/* while循環(huán)依次刪除被點到的士兵 */　　printf("\n");　　return (t->data);　　}</

40、p>　　main()　　{　　LNode *p;　　int m,n,z,y;　　printf("Exit please

41、input '0' Or Go on...\nPlease input the tatal of the team:");　　scanf ("%d",&n); /*輸入隊員總數(shù)*/　　while(n!=0) /*當隊員總數(shù)等于0時退出*/<b&

42、gt;　　{　　do　　{　　printf("Please input the excursion:"); /*輸入偏移數(shù)*/　　scanf(&quo

43、t;%d",&m);　　}　　while (m<=0);　　if(m==1)　　printf("The wanted position is 1th.\n&quo

44、t;);　　else　　{　　p=CREAT(n);　　y=DELETE(p,m);　　z=n-y+2;</p

45、>　　if(z%n==0) /* 排除特殊情況 */　　printf ("The wanted position is %dth:\n",z);　　else　　printf("The wanted position

46、is %dth:\n",(n-y+2)%n);　　}/* 通過數(shù)學思想求得實驗要求情況下的數(shù)值 */　　printf("Exit please input '0' Or Go on...\nPlease input the tatal of the team:");

47、　scanf("%d",&n); /*輸入敢死隊員總數(shù)*/　　}　　}　　二．線性表數(shù)據(jù)結(jié)構(gòu)　　(

48、一)需求分析　　1.本程序任務(wù)是通過輸入任意隊伍人數(shù)n和報數(shù)上限m，輸出使排長最后一個執(zhí)行任務(wù)而開始記數(shù)的初始位置。首先輸入隊伍人數(shù)n，然后輸入報數(shù)上限m(m<=n),從1號開始報數(shù)，當達到報數(shù)上限時，那名士兵出列執(zhí)行任務(wù)，從下個人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊伍中的位置，記下該位置視為排長位置，則1號即可視為最先報數(shù)的人，通過數(shù)學計算即可獲得所求。<

49、;/p>　　2.功能模塊和流程： 　　1）功能模塊　　該程序功能比較單一，主要是為解決敢死隊問題而設(shè)計。通過輸入隊伍人數(shù)和報數(shù)上限即可獲得開始報數(shù)的位置。　　2）程序流程

50、;　　如下圖。　　3.數(shù)據(jù)測試：　　當 n=10 輸出結(jié)果為：要求的位置是：9　?。ǘ┰敿氃O(shè)計　　1.算法思想: 本程序其實質(zhì)是約瑟夫環(huán)問題,本次實驗用了線

51、性表和循環(huán)隊列兩種數(shù)據(jù)結(jié)構(gòu),并運用模塊化的程序設(shè)計思想,算法的實現(xiàn)是這樣的:　　定義結(jié)構(gòu)體類型　　定義變量并初始化　　線性表初始化　　隊員報數(shù),是5的倍數(shù)出列

52、　　當隊員數(shù)等于1時,輸出　　流程圖　　從排長位置即1號開始報數(shù)，共有n個人，達到報數(shù)上限m=5的戰(zhàn)士出列，繼續(xù)進行報數(shù)，直到剩余最后一人，記下該位置為k。若將該位置視為排長位置，則原先的1號位置即位所有的開始報數(shù)的位置z。則z=n-k+2。<p

53、>　　2.模塊設(shè)計：　　宏定義:　　#define LIST_INIT_SIZE 100　　#define LISTINCCREMENT 10　　數(shù)據(jù)類型定義:typedef int Ele

54、mType;　　定義數(shù)據(jù)結(jié)構(gòu):　　typedef struct KList /*定義數(shù)據(jù)結(jié)構(gòu)體類型*/　　{　　ElemType *elem; /*存儲空間基址*/</p

55、>　　int length; /*當前長度*/　　int listsize; /*當前分配的存儲容量(以sizeof(ElemType)為單位)*/　　}SqList;　　模塊一:創(chuàng)建線性表函數(shù)<p&g

56、t;　　SqList InitList_Sq() /*創(chuàng)建線性表函數(shù)*/　　{　　SqList L;　　L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));<

57、/p>　　if(!L.elem) printf("Fail in new creat list"),exit(0); /*存儲分配失敗*/　　else　　{　　L.length=0;

58、 /*空表長度為0*/　　L.listsize=LIST_INIT_SIZE; /*初始存儲容量*/　　}　　}　　模塊二: 線性表再分配函數(shù)<

59、;p>　　SqList ListInsert_Sq(SqList L) /*線性表再分配函數(shù)*/　　{　　/*SqList L;*/　　int *newbase;　　newbase=(ElemType *)realloc

60、(L.elem,　　(L.listsize+LISTINCCREMENT)*sizeof(ElemType));　　/*為順序表增加一個大小為存儲LISTINCCREMENT個數(shù)據(jù)元素的空間*/　　if(!newbase) printf("Fail in new add list"),exit

61、(0);/*存儲分配失敗*/　　else　　{　　L.elem=newbase; /*新基址*/　　L.listsize+=LISTINCCRE

62、MENT; /*增加存儲容量*/　　}　　}　　主模塊:實現(xiàn)總體功能　　main()<b&

63、gt;　　{　　SqList L;　　int s,i,m,count=0; /*聲明變量*/　　L=InitList_Sq();　　printf("Please input the tatal of

64、 the team:");　　scanf("%d",&m); /*輸入敢死隊員總數(shù)*/　　while(m!=0)/*當輸入為0時退出程序*/　　{　　while(m>L.len

65、gth) /*當順序表當前分配的存儲空間大小不足時進行再分配*/　　L=ListInsert_Sq(L);　　for(i=0;i<m;i++) L.elem[i]=i+1; /*為隊員賦值*/　　s=m;

66、　　i=0;　　while(s>1) /*當所剩敢死隊員總數(shù)為1時,總循環(huán)結(jié)束*/　　{　　for(i=0;i<m;i++)　　if(L.elem[i]!=0)

67、　　{　　count++;　　if(count==5) /*報數(shù)循環(huán)*/　　{　　L.elem[i]

68、=0; /*表示隊員出列*/　　count=0; /*計數(shù)器清零*/　　s--; /*敢死隊員數(shù)-1*/　　}　　}<b&g

69、t;　　}　　for(i=0;i<m;i++) /*輸出*/　　if(L.elem[i]!=0)　　if((m-L.elem[i]+2)%m==0) /**/　　printf("\nThe wanted order is %dth\

70、n",m);　　else　　printf("\nThe wanted order is %dth\n",(m-L.elem[i]+2)%m);　　printf("Exit please input '0' Or Go o

71、n...\nPlease input the tatal of the team:");　　scanf("%d",&m); /*輸入敢死隊員總數(shù)*/　　}　　}&

72、lt;p>　　（三）調(diào)試分析　　1.程序正常運行后應該為：　　exit please input ‘0’or go on…　　please input the total of the team　　輸入總共人數(shù)

73、　　The wanted position is th　　輸出所求的開始報數(shù)位置　　2. 在程序調(diào)試運行的過程中產(chǎn)生了各種各樣的問題，有的是多了空格，有的是拼寫錯誤，還有的是少了括號，類似的問題有很多。解決的辦法是一遍遍嘗試，不斷逐行逐句進行修改。

74、例如程序調(diào)試過程中出現(xiàn)了下面的警告:　　經(jīng)查詢錯誤為:不可移動的指針（地址常數(shù)）賦值　　最終發(fā)現(xiàn)是下面的定義錯誤造成的　　在變量定義中int *newbase =0; 　　定義成了 int newbase =0;　　經(jīng)改正

75、程序運行正常了.　　3.經(jīng)驗與體會　　通過這次課程設(shè)計我又學到了很多東西,如程序的模塊化設(shè)計思想，同時也加深了對數(shù)據(jù)結(jié)構(gòu)這門課程的理解和學會了如何在實際中應用數(shù)據(jù)結(jié)構(gòu)編程。　　我首先是用線性表來做的，開始的想法是想用試驗的方法來查找到所要求的位置，即首先從第一號開始報數(shù)，然后

76、檢查最后剩下的一個是否是隊首，然后從第二個開始報數(shù)……從第三個開始報數(shù)……直到所剩下的最后一個是隊首。雖然這種方法可以實現(xiàn)查找，可卻是以消耗更多的時間為代價的，于是我又想到了這個方法：總是從第一個開始報數(shù)，報到5出列，直到剩下最后一個為止，然后就令這個位置為隊長位置，隊首為開始報數(shù)的位置，并按此設(shè)計輸出即可。這種方法大大的降低了時間復雜度，復雜度為O(mn)。　?。ㄋ模y試結(jié)果

77、　?。ㄎ澹└郊?lt;/b>　　程序源代碼:　　#define LIST_INIT_SIZE 100　　#define LISTINCCREMENT 10<p&

78、gt;　　typedef int ElemType;　　typedef struct KList /*定義數(shù)據(jù)結(jié)構(gòu)體類型*/　　{　　ElemType *elem; /*存儲空間基址*/　　int length;

79、 /*當前長度*/　　int listsize; /*當前分配的存儲容量(以sizeof(ElemType)為單位)*/　　}SqList;　　SqList InitList_Sq() /*創(chuàng)建線性表函數(shù)*/<

80、b>　　{　　SqList L;　　L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); 　　if(!L.elem) printf("Fail in new creat

81、list"),exit(0); /*存儲分配失敗*/　　else　　{　　L.length=0; /*空表長度為0*/　　L.listsize=LIST_

82、INIT_SIZE; /*初始存儲容量*/　　}　　}　　SqList ListInsert_Sq(SqList L) /*線性表再分配函數(shù)*/　　{

83、　　/*SqList L;*/　　int *newbase;　　newbase=(ElemType *)realloc(L.elem,　　(L.listsize+LISTINCCREMENT)*sizeof(ElemType));

84、　　/*為順序表增加一個大小為存儲LISTINCCREMENT個數(shù)據(jù)元素的空間*/　　if(!newbase) printf("Fail in new add list"),exit(0);/*存儲分配失敗*/　　else　　{</

85、b>　　L.elem=newbase; /*新基址*/　　L.listsize+=LISTINCCREMENT; /*增加存儲容量*/　　}

86、;　　}　　main()　　{　　SqList L;　　int s,i,m,count=0; /*聲明變量*/

87、　　L=InitList_Sq();　　printf("Please input the tatal of the team:");　　scanf("%d",&m); /*輸入敢死隊員總數(shù)*/　　while(m!=0)/*當輸入為0

88、時退出程序*/　　{　　while(m>L.length) /*當順序表當前分配的存儲空間大小不足時進行再分配*/　　L=ListInsert_Sq(L);　　for(i=0;i<m;i++) L.elem[i]=i+

89、1; /*為隊員賦值*/　　s=m;　　i=0;　　while(s>1) /*當所剩敢死隊員總數(shù)為1時,總循環(huán)結(jié)束*/　　{&l

90、t;/b>　　for(i=0;i<m;i++)　　if(L.elem[i]!=0)　　{　　count++;　　if(count==5)

91、 /*報數(shù)循環(huán)*/　　{　　L.elem[i]=0; /*表示隊員出列*/　　count=0; /*計數(shù)器清零*/　　s--; /*敢死隊員數(shù)-1*/<

92、b>　　}　　}　　}　　for(i=0;i<m;i++) /*輸出*/　　if(L.elem[i]!=0)　　if(

93、(m-L.elem[i]+2)%m==0) /**/　　printf("\nThe wanted order is %dth\n",m);　　else　　printf("\nThe wanted order is %dth\n",(m-

94、L.elem[i]+2)%m);　　printf("Exit please input '0' Or Go on...\nPlease input the tatal of the team:\n");　　scanf("%d",&m); /*輸入敢死隊員總數(shù)*/</p&g

95、t;　　}　　}　　參考文獻　　譚浩強《c程序設(shè)計》　　2.李業(yè)麗，鄭良斌《數(shù)據(jù)機構(gòu)（c）實驗教程》

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告—敢死隊的問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告—敢死隊的問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載