數據結構敢死隊問題

1、15華 北 科 技 學 院課程設計說明書（數據結構課程設計）班級: 信管b08-1 姓名: 陳秋苗 學號： 200807034118 設計題目： 敢死隊問題 設計時間:_2010-9-6_至_2010-9-17_ 指導教師:_蘭 蕓_ 評 語:_ _評閱成績: 評閱教師: 數據結構課程設計實驗報告開課實驗室： 基礎實驗室 一 2010 年9 月16 日實驗題目敢死隊問題1.實驗題目敢死隊問題2.實驗設備及環(huán)境pc兼容機、windows操作系統(tǒng)、vb軟件等。3.功能模塊簡介和系統(tǒng)結構圖系統(tǒng)結構圖本程序有四個功能模塊，包括三個解決敢死隊問題方案的模塊和一個退出系統(tǒng)模塊。三個解決方案分別采用了循環(huán)聊

2、表儲存結構、線性表儲存結構、循環(huán)隊列儲存結構。功能模塊如下圖所示。敢死隊問題循環(huán)單鏈表儲存結構線性表儲存結構循環(huán)隊列儲存結構退出功能模塊具體簡介如下：(1).循環(huán)單鏈表以單循環(huán)鏈表為存儲結構，包含三個模塊： 1.主程序模塊 包含敢死隊人數的輸入，死亡數字的輸入，函數的調用，結果的輸出。2.構造鏈表并初始化 構造鏈表，給每個結點賦值，給隊員編號。3刪除 當報數到死亡數字時隊員出列去執(zhí)行任務，刪除該節(jié)點。開始聲明類型定義變量并初始化初始化單鏈表循環(huán)模塊輸入敢死隊員總數剩下的隊員數>1?隊員報數報數值=死亡數?隊員出列輸出結果（2）.線性表儲存結構功能設計本程序其實質是約瑟夫環(huán)問題,本次實驗用

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

4、等于1，如果等于則輸出開始計數位置，如果不等，繼續(xù)循環(huán)查找，直到找出符合條件的計數起始位置，輸出結果。算法流程圖開始聲明數據類型定義變量并初始化初始化循環(huán)隊列輸入敢死隊員總數隊列滿？隊員報數報數值=5?隊員出列即清零剩下的隊員數>1?輸出增加存儲分配編號=1？給隊員編號入隊列4. 系統(tǒng)的主要界面設計及運行說明：進入用戶主界面，選者實現(xiàn)結果的方法以10個隊員，死亡數字為5來運行，結果如下 選擇第2項功能，運用線性表儲存結構 選擇第3項功能，運用循環(huán)隊列來實現(xiàn)結果5.程序的主要代碼：#include <stdio.h>#include<string.h>#includ

5、e<stdlib.h>#include<malloc.h>/-循環(huán)單鏈表-typedef struct node int data; struct node *next;lnode;/* 定義結點類型 */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;/* 生成第一個結點并使其data值為1 */ for(i=2;i<=n;i+) s=(lnode *)malloc(sizeof(lno

6、de); q->next=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;i<m-1;i+)/*查找要刪除結點的前一結點*/ t=t->next; a=t->next; t->next=a->next; free(a); t=t->next; printf("n"); return

7、(t->data);/-/-線性表-#define list_init_size 100#define listinccrement 10#define ok 1#define error 0typedef int elemtype;typedef struct klist /*定義數據結構體類型*/elemtype *elem; /*存儲空間基址*/int length; /*當前長度*/int listsize; /*當前分配的存儲容量(以sizeof(elemtype)為單位)*/sqlist;int initlist_sq(sqlist &l) /*創(chuàng)建線性表函數*/l.

8、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) /*線性表再分配函數*/*sqlist l;*/int *newbase;newbase=(elemtype *)realloc(l.elem, (l.listsize

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

10、nt;int rear; int count; /計數器，記錄隊中元素總數cirqueue;void initial(cirqueue *q) /將順序隊列置空q->front=q->rear=0; q->count=0; /計數器置 / 判隊列空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 (isf

11、ull(q) printf("隊列上溢"); /上溢,退出運行exit(1); q->count +; /隊列元素個數加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-; /隊列元素個數減

12、q->front=(q->front+1)%queuesize; /循環(huán)意義下的頭指針加1return temp; /-void main () sqlist l; int s,i,m,count=0; /*聲明變量*/ 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&q

13、uot;); printf("_n");printf("請選擇實現(xiàn)結果的方法：（14）nn");scanf("%d",&opt);if(opt>4 | opt<1) printf("輸入有誤請重新輸入n");goto abc;switch(opt)case 1:system("cls");printf("您使用是循環(huán)鏈表儲存結構nn");efg:printf("請輸入敢死隊的人數：n");scanf("%d",&am

14、p;num);if(num<1)printf("輸入有誤請重新輸入n");goto efg; printf("請輸入死亡數數字n");m: scanf("%d",&m); if(m>num | m<1) printf("輸入有誤請重新輸入"); goto m; else p=creat(num); y=delete(p,m); z=num-y+2; if(z%num=0) printf ("從第 %dth:開始計數n",z); else printf("從第%

15、d號戰(zhàn)士開始計數才能讓排長最后一個留下來而不去執(zhí)行任務。n",(num-y+2)%num);break;case 2:system("cls");printf("您使用的是線性表儲存結構nn");e:printf("請輸入敢死隊的人數：n");scanf("%d",&num);if(num<1)printf("輸入有誤請重新輸入n");goto e; m=5; initlist_sq(l); while(num>l.listsize ) /*當順序表當前分配的存儲空

16、間大小不足時進行再分配*/ listinsert_sq(l); for(i=0;i<num;i+) l.elemi=i+1; /*為隊員賦值*/ s=num; i=0; while(s>1) /*當所剩敢死隊員總數為1時,總循環(huán)結束*/ for(i=0;i<num;i+) if(l.elemi!=0) count+; if(count=5) /*報數循環(huán)*/ l.elemi=0; /*表示隊員出列*/ count=0; /*計數器清零*/ s-; /*敢死隊員數-1*/ for(i=0;i<num;i+) /*輸出*/if(l.elemi!=0)if(num-l.ele

17、mi+2)%num=0) printf("從第%d號戰(zhàn)士開始計數才能讓排長最后一個留下來而不去執(zhí)行任務。n",num);elseprintf("從第%d號戰(zhàn)士開始計數才能讓排長最后一個留下來而不去執(zhí)行任務。n",(num-l.elemi+2)%num); break;case 3:system("cls");printf("您使用的是循環(huán)隊列儲存結構nn");int start,count,j; cirqueue s; g:printf("請輸入敢死隊的人數：n");scanf("%d

18、",&num);if(num<1)printf("輸入有誤請重新輸入n");goto g;for(start=1;start<=num;start+)/start為測試起點 initial(&s); for(i=1;i<=num;i+) enqueue(&s,i); for(i=1;i<start;i+) j=dequeue(&s); enqueue(&s,j); count=1; while(count<num) for(i=1;i<5;i+) j=dequeue(&s); enqueue(&s,j); j=dequeue(&s); count+; if(s.datas.front=1) break; printf("從第%d號戰(zhàn)士開始計數才能讓排長最后一個留下來而不去執(zhí)行任務。n",start); break; case 4:exit(0);goto abc;6.實驗總結：通過這次課程設計我又學到了很多東西,如程序的模塊化設計思想，同時也加深了對數據結構這門課程的理解和學會了如何在