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

1、華北科技學(xué)院課程設(shè)計說明書（數(shù)據(jù)結(jié)構(gòu)課程設(shè)計）班級：姓名：學(xué)號：設(shè)計題目：設(shè)計時間：指導(dǎo)教師：評 語:評閱成績：評閱教師：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告開課實驗室： 基礎(chǔ)實驗室 一2010 年9月16日實驗題目敢死隊問題1. 實驗題目敢死隊問題2. 實驗設(shè)備及環(huán)境PC兼容機、Windows操作系統(tǒng)、VB軟件等。3. 功能模塊簡介和系統(tǒng)結(jié)構(gòu)圖 系統(tǒng)結(jié)構(gòu)圖本程序有四個功能模塊，包括三個解決敢死隊問題方案的模塊和一個退出系統(tǒng)模塊。 三個解決方案分別采用了循環(huán)聊表儲存結(jié)構(gòu)、線性表儲存結(jié)構(gòu)、循環(huán)隊列儲存結(jié)構(gòu)。功 能模塊如下圖所示。循環(huán)單鏈表儲線性表儲存循環(huán)隊列儲存退出敢死隊問題結(jié)構(gòu)結(jié)構(gòu)存結(jié)構(gòu) L功能模塊具體簡

2、介如下: （1）.循環(huán)單鏈表以單循環(huán)鏈表為存儲結(jié)構(gòu)，包含三個模塊:1.主程序模塊 包含敢死隊人數(shù)的輸入，死亡數(shù)字的輸入，函數(shù)的調(diào)用，結(jié)果的輸出。2.構(gòu)造鏈表并初始化構(gòu)造鏈表，給每個結(jié)點賦值，給隊員編號。3 刪除當(dāng)報數(shù)到死亡數(shù)字時隊員出列去執(zhí)行任務(wù)，刪除該節(jié)點。(2).線性表儲存結(jié)構(gòu)功能設(shè)計本程序其實質(zhì)是約瑟夫環(huán)問題，本次實驗用了線性表數(shù)據(jù)結(jié)構(gòu),并運用模塊化的程序設(shè)計思想，算法的實現(xiàn)是這樣的：定義類類型1. 定義變量并初始化2. 線性表初始化3. 當(dāng)隊員數(shù)小于等于1時，輸出結(jié)果算法流程圖循環(huán)隊列儲存結(jié)構(gòu)解決功能設(shè)計,算法本程序其實質(zhì)是約瑟夫環(huán)問題，本次實驗用了循環(huán)隊列數(shù)據(jù)結(jié)構(gòu)，并運用模塊化的程序

3、設(shè)計思想 的實現(xiàn)是這樣的這個方法是用隊列循環(huán)來做的，實現(xiàn)的方法是這樣的：首先從第一號開始報數(shù)，循環(huán)到指定的偏移位置刪除結(jié)點，直至剩下一個結(jié)點。然后再比較一下它的號碼是不是等于1，如果等于則輸出開始計數(shù)位置，如果不等，繼續(xù)循環(huán)查找，直到找出符合條件的計數(shù)起始位置，輸出結(jié)果。算法流程圖E F : Debuck敢死6k- exe表列 鍍表臥 隹壞出 BI M 12 3 4請選擇實現(xiàn)結(jié)果的方祛：g10個隊員，死亡數(shù)字為5來運行，結(jié)果如下?cl F: Debug：敢死6k. exe您使用是循那鏈舂儲存結(jié)構(gòu) 請輸入敢死隊的人數(shù)：10請輸入死亡數(shù)數(shù)字人執(zhí)號戰(zhàn)士開始計數(shù)才能讓排長最后一個滔下來而不去執(zhí)行任務(wù)表

4、列 鏈表臥 程壞岀Bf 12 3 4請選擇實駆吉果的方法！ (1-4)選擇第2項功能，運用線性表儲存結(jié)構(gòu)n x表列 程壞出 H 12 3 4嘰: DebueVtt5EEk- ese弓使用的是線性表儲存結(jié)構(gòu)胡輸入敢死隊的人數(shù)；10JA第y號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下耒而不去執(zhí)行任務(wù)。晴選擇實現(xiàn)結(jié)杲的方法 C1-4)選擇第3項功能，運用循環(huán)隊列來實現(xiàn)結(jié)果c；F : DebueSlexe圾使用的是循壞臥列儲存結(jié)構(gòu)請輸入敢死隊的人數(shù)；k報號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下耒而不去執(zhí)行任務(wù)。表列 鋌表隊 程壞出 n 1 2 3 JI淸選擇實現(xiàn)結(jié)果的方法：C1-4)5.程序的主要代碼:#i nc

5、lude #i nclude#i nclude#i nclude/循環(huán)單鏈表typedef struct nodeint data;struct node *n ext;LNode;/* 定義結(jié)點類型*/LNode* CREAT(int n) /*創(chuàng)建循環(huán)鏈表 */LNode *s,*q,*T;int i;if(n !=0)T=q=(LNode *)malloc(sizeof(LNode);q-data=1;/*生成第一個結(jié)點并使其 data值為1 */for(i=2;in ext=s;q- next-data=i;/*賦值 */q=q-n ext;q-n ext=T;return T;DEL

6、ETE (LNode* T,int m)/* 鏈表的刪除 */LNode *a;i nt i;while (T-n ext!=T)for (i=1;in ext;a=T- n ext;T-n ext=a-n ext;free(a);T=T-n ext;prin tf(n);return (T-data);/ 線性表#defi ne LIST_INIT_SIZE 100#defi ne LISTINCCREMENT 10#defi ne OK 1#defi ne ERROR 0 typedef int ElemType;typedef struct KList/*定義數(shù)據(jù)結(jié)構(gòu)體類型*/ElemT

7、ype *elem; /*存儲空間基址*/int length;/* 當(dāng)前長度 */int listsize; /*當(dāng)前分配的存儲容量(以sizeof(ElemType)為單位)*/SqList;int InitList_Sq( SqList &L)/* 創(chuàng)建線性表函數(shù) */L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType);if(!L.elem)printf(存儲分配失敗);return ERROR; elseL.length=O;/* 空表長度為 0*/L.listsize=LIST_INIT_SIZE;return OK

8、;/*初始存儲容量*/int List In sert_Sq(SqList &L)/* 線性表再分配函數(shù) */*SqList L;*/int *n ewbase;n ewbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCCREMENT)*sizeof(ElemType);/*為順序表增加一個大小為存儲LISTINCCREMENT個數(shù)據(jù)元素的空間*/if(! newbase)printf(存儲分配失敗);return ERROR;elseL.elem=newbase;/* 新基址 */L.listsize+=LISTINCCREMENT;/*增

9、加存儲容量*/return OK;/ 循環(huán)隊列#define QueueSize 1000 /假定預(yù)分配的隊列空間最多為 1000個元素typedef structint dataQueueSize;int front;in t rear;in t cou nt; /計數(shù)器，記錄隊中元素總數(shù)CirQueue;void Initial(CirQueue *Q)/將順序隊列置空Q-fron t=Q-rear=0;Q-cou nt=0; /計數(shù)器置/判隊列空int Empty(CirQueue *Q)retur n Q-fron t=Q-rear;/判隊列滿int Full(CirQueue *Q)

10、retur n Q-rear=QueueSize-1+Q-fr ont;/進隊列void En Queue(CirQueue *Q,i nt x)if (IsFull(Q)printf(隊列上溢);/上溢，退出運行exit(1);Q-cou nt +; /隊列元素個數(shù)加Q-dataQ-rear=x; /新元素插入隊尾Q-rear=(Q-rear+1)%QueueSize; /循環(huán)意義下將尾指針加/出隊列int DeQueue(CirQueue *Q)int temp;if(lsEmpty(Q)printf(隊列為空);/下溢，退出運行 exit(1);temp=Q-dataQ-fr on t;

11、循環(huán)意義下的頭指針加1Q-cou nt-; /隊列元素個數(shù)減Q-fro nt=(Q-fro nt+1)%QueueSize; / return temp;/void mai n ()SqList L;int s,i,m,count=O;/* 聲明變量 */LNode *p;int 乙y;int num;int opt;abc:printf(n);prin tf(|1.循環(huán)鏈表|n);prin tf(|2.線性表|n);prin tf(|3.循環(huán)隊列|n);prin tf(|4.退出|n);printf(n);printf(”請選擇實現(xiàn)結(jié)果的方法：(14 ) nn);scan f(%d,&opt

12、);if(opt4 | opt1)printf(輸入有誤請重新輸入n);goto abc; switch(opt)case 1:system(cls);efg:printf(您使用是循環(huán)鏈表儲存結(jié)構(gòu)nn);printf（請輸入敢死隊的人數(shù)：n）;sea nf(%d,&nu m);if(nu mnum | m1) printf(輸入有誤請重新輸入);goto m;elsep=CREAT (n um);y=DELETE(p,m);z=num-y+2;if(z% num=0)printf (從第 %dth:開始計數(shù) n,z);elseprintf(從第%d號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去

13、執(zhí)行去執(zhí)行任務(wù)。n,(num-y+2)%num);break;case 2:system(cls);printf(您使用的是線性表儲存結(jié)構(gòu)nn);e:printf(請輸入敢死隊的人數(shù)：n);sca nf(%d,&nu m);if(nu mL.listsize)/*當(dāng)順序表當(dāng)前分配的存儲空間大小不足時進行再分配*/ListI nsert_Sq(L);for(i=0;i1)/*當(dāng)所剩敢死隊員總數(shù)為1時，總循環(huán)結(jié)束*/for(i=0;i nu m;i+)if(L.elemi!=0)coun t+;if(cou nt=5)/* 報數(shù)循環(huán) */L.elemi=0; /* 表示隊員出列*/count=0;

14、/*計數(shù)器清零*/s-;/*敢死隊員數(shù)-1*/for(i=0;i nu m;i+)/* 輸出 */if(L.elemi!=0)if( num-L.elemi+2)% nu m=0)printf(從第%d號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。n,num);else 任務(wù)。n,(num-L.elemi+2)%num);break;case 3:system(cls);printf(您使用的是循環(huán)隊列儲存結(jié)構(gòu)nn);int start,co un t,j;CirQueue s;g:printf(請輸入敢死隊的人數(shù)：n);sca nf(%d,&nu m);if(nu m1)printf

15、(輸入有誤請重新輸入n);goto g;for(start=1;start=nu m;start+)/start為測試起點In itial(& s);for(i=1;i=nu m;i+)En Queue(&s,i);for(i=1;istart;i+)j=DeQueue(&s);En Queue(&s,j);coun t=1;while(co untvnum)for(i=1;i5;i+)j=DeQueue(&s);En Queue(&s,j);j=DeQueue(&s);coun t+;if(s.datas.fr on t=1)break;printf(從第%d號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。n,start);break;case 4:exit(0);goto abc;6.實驗總結(jié)：通過這次課程設(shè)計我又學(xué)到了很多東西，如程序的模塊化設(shè)計思想，同時也加深了對 數(shù)據(jù)結(jié)構(gòu)這門課程的理解和學(xué)會了如何在實際中應(yīng)用數(shù)據(jù)結(jié)構(gòu)。在做程序之前，覺得敢死隊這個問題，很難解決。在通過自己一次次的畫圖，推算 結(jié)果時，明白了該程