數(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)單鏈表儲存結(jié)構(gòu)線性表儲存結(jié)構(gòu)循環(huán)隊列儲存結(jié)構(gòu)退出功

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é)點。開始聲明類型定義變量并初始化初始化單鏈表循環(huán)模塊輸入敢死隊員總數(shù)剩下的隊員數(shù)1?隊員報數(shù)報數(shù)值=死亡數(shù)?隊員出列輸出結(jié)果（2）.線性表儲存結(jié)構(gòu)功能設(shè)計本程序其實質(zhì)是約瑟夫環(huán)問題,本次實驗用了線性表數(shù)據(jù)結(jié)構(gòu),并運用模塊化的程序設(shè)計思想,算法的實現(xiàn)是這樣的:定義類類型1. 定義變量并初始化2. 線性表初始化3. 當(dāng)隊員數(shù)小于等于

3、1時,輸出結(jié)果算法流程圖開始聲明數(shù)據(jù)類型定義變量并初始化初始化線性表輸入敢死隊員總數(shù)敢死隊員人數(shù)線性表長度隊員報數(shù)報數(shù)值=5？隊員出列剩下的隊員數(shù)1?輸出增加存儲分配循環(huán)隊列儲存結(jié)構(gòu)解決功能設(shè)計本程序其實質(zhì)是約瑟夫環(huán)問題,本次實驗用了循環(huán)隊列數(shù)據(jù)結(jié)構(gòu),并運用模塊化的程序設(shè)計思想,算法的實現(xiàn)是這樣的:這個方法是用隊列循環(huán)來做的，實現(xiàn)的方法是這樣的：首先從第一號開始報數(shù)，循環(huán)到指定的偏移位置刪除結(jié)點，直至剩下一個結(jié)點。然后再比較一下它的號碼是不是等于1，如果等于則輸出開始計數(shù)位置，如果不等，繼續(xù)循環(huán)查找，直到找出符合條件的計數(shù)起始位置，輸出結(jié)果。算法流程圖開始聲明數(shù)據(jù)類型定義變量并初始化初始化循環(huán)

4、隊列輸入敢死隊員總數(shù)隊列滿？隊員報數(shù)報數(shù)值=5?隊員出列即清零剩下的隊員數(shù)1?輸出增加存儲分配編號=1？給隊員編號入隊列4. 系統(tǒng)的主要界面設(shè)計及運行說明：進入用戶主界面，選者實現(xiàn)結(jié)果的方法以10個隊員，死亡數(shù)字為5來運行，結(jié)果如下 選擇第2項功能，運用線性表儲存結(jié)構(gòu) 選擇第3項功能，運用循環(huán)隊列來實現(xiàn)結(jié)果5.程序的主要代碼：#include #include#include#include/-循環(huán)單鏈表-typedef struct node int data; struct node *next;lnode;/* 定義結(jié)點類型 */lnode* creat(int n) /* 創(chuàng)建循環(huán)鏈表

5、 */ lnode *s,*q,*t; int i; if(n!=0) t=q=(lnode *)malloc(sizeof(lnode); q-data=1;/* 生成第一個結(jié)點并使其data值為1 */ for(i=2;inext=s; q-next-data=i;/*賦值*/ q=q-next; q-next=t; return t;delete (lnode* t,int m)/* 鏈表的刪除 */ lnode *a;int i; while (t-next!=t) for (i=1;inext; a=t-next; t-next=a-next; free(a); t=t-next;

6、printf(n); return (t-data);/-/-線性表-#define list_init_size 100#define listinccrement 10#define ok 1#define error 0typedef int elemtype;typedef struct klist /*定義數(shù)據(jù)結(jié)構(gòu)體類型*/elemtype *elem; /*存儲空間基址*/int length; /*當(dāng)前長度*/int listsize; /*當(dāng)前分配的存儲容量(以sizeof(elemtype)為單位)*/sqlist;int initlist_sq(sqlist &l) /*創(chuàng)

7、建線性表函數(shù)*/l.elem=(elemtype *)malloc(list_init_size * sizeof(elemtype); if(!l.elem)printf(存儲分配失敗);return error; elsel.length=0; /*空表長度為0*/l.listsize=list_init_size;return ok;/*初始存儲容量*/int listinsert_sq(sqlist &l) /*線性表再分配函數(shù)*/*sqlist l;*/int *newbase;newbase=(elemtype *)realloc(l.elem, (l.listsize+listi

8、nccrement)*sizeof(elemtype); /*為順序表增加一個大小為存儲listinccrement個數(shù)據(jù)元素的空間*/if(!newbase) printf(存儲分配失敗);return error;else l.elem=newbase; /*新基址*/ l.listsize+=listinccrement; /*增加存儲容量*/ return ok; /-/-循環(huán)隊列-#define queuesize 1000 /假定預(yù)分配的隊列空間最多為1000個元素typedef struct int dataqueuesize; int front;int rear; int c

9、ount; /計數(shù)器，記錄隊中元素總數(shù)cirqueue;void initial(cirqueue *q) /將順序隊列置空q-front=q-rear=0; q-count=0; /計數(shù)器置 / 判隊列空int empty(cirqueue *q) return q-front=q-rear; /判隊列滿int full(cirqueue *q) return q-rear=queuesize-1+q-front; /進隊列void enqueue(cirqueue *q,int x) if (isfull(q) printf(隊列上溢); /上溢,退出運行exit(1); q-count

10、+; /隊列元素個數(shù)加q-dataq-rear=x; /新元素插入隊尾q-rear=(q-rear+1)%queuesize; /循環(huán)意義下將尾指針加 /出隊列int dequeue(cirqueue *q) int temp; if(isempty(q) printf(隊列為空); /下溢,退出運行exit(1); temp=q-dataq-front; q-count-; /隊列元素個數(shù)減q-front=(q-front+1)%queuesize; /循環(huán)意義下的頭指針加1return temp; /-void main () sqlist l; int s,i,m,count=0; /*

11、聲明變量*/ lnode *p; int z,y; int num;int opt; abc: printf(_n);printf(| 1.循環(huán)鏈表 |n);printf(| 2.線性表 |n);printf(| 3.循環(huán)隊列 |n);printf(| 4.退出 |n); printf(_n);printf(請選擇實現(xiàn)結(jié)果的方法：（14）nn);scanf(%d,&opt);if(opt4 | opt1) printf(輸入有誤請重新輸入n);goto abc;switch(opt)case 1:system(cls);printf(您使用是循環(huán)鏈表儲存結(jié)構(gòu)nn);efg:printf(請輸入

12、敢死隊的人數(shù)：n);scanf(%d,&num);if(numnum | m1) printf(輸入有誤請重新輸入); goto m; else p=creat(num); y=delete(p,m); z=num-y+2; if(z%num=0) printf (從第 %dth:開始計數(shù)n,z); else printf(從第%d號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。n,(num-y+2)%num);break;case 2:system(cls);printf(您使用的是線性表儲存結(jié)構(gòu)nn);e:printf(請輸入敢死隊的人數(shù)：n);scanf(%d,&num);if(n

13、uml.listsize ) /*當(dāng)順序表當(dāng)前分配的存儲空間大小不足時進行再分配*/ listinsert_sq(l); for(i=0;i1) /*當(dāng)所剩敢死隊員總數(shù)為1時,總循環(huán)結(jié)束*/ for(i=0;inum;i+) if(l.elemi!=0) count+; if(count=5) /*報數(shù)循環(huán)*/ l.elemi=0; /*表示隊員出列*/ count=0; /*計數(shù)器清零*/ s-; /*敢死隊員數(shù)-1*/ for(i=0;inum;i+) /*輸出*/if(l.elemi!=0)if(num-l.elemi+2)%num=0) printf(從第%d號戰(zhàn)士開始計數(shù)才能讓排長最

14、后一個留下來而不去執(zhí)行任務(wù)。n,num);elseprintf(從第%d號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。n,(num-l.elemi+2)%num); break;case 3:system(cls);printf(您使用的是循環(huán)隊列儲存結(jié)構(gòu)nn);int start,count,j; cirqueue s; g:printf(請輸入敢死隊的人數(shù)：n);scanf(%d,&num);if(num1)printf(輸入有誤請重新輸入n);goto g;for(start=1;start=num;start+)/start為測試起點 initial(&s); for(i=1;

15、i=num;i+) enqueue(&s,i); for(i=1;istart;i+) j=dequeue(&s); enqueue(&s,j); count=1; while(countnum) for(i=1;i5;i+) j=dequeue(&s); enqueue(&s,j); j=dequeue(&s); count+; if(s.datas.front=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é)果時，明白了