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

敢死隊問題+數(shù)據(jù)結(jié)構(gòu)

課程設(shè)計

-CAL-FENGHAl-(2020YEAR-YICAI)_JINGBIAN

目錄

一?問題描述

二.線性表數(shù)據(jù)結(jié)構(gòu)

（一）?需求分析

（二）?概要設(shè)計

（三）?詳細設(shè)計

（四）?程序調(diào)試及運行

（五）?設(shè)計總結(jié)

（六）?附件

三.單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)

（一）,需求分析

（二）?概要設(shè)計

（三）?詳細設(shè)計

（四）?程序調(diào)試及運行

（五）?設(shè)計總結(jié)

（六）?附件

一.問題描述

敢死隊問題

有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)

的辦法來決定哪個戰(zhàn)士去執(zhí)行任務(wù)。如果前一個戰(zhàn)士沒完成任務(wù)，則要再派一

個戰(zhàn)士上去。現(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è)計一程序，求出從第幾號戰(zhàn)士

開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。

要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。

二.線性表數(shù)據(jù)結(jié)構(gòu)

（一卜需求分析

1.本程序輸入隊伍人數(shù)n為任意的，最終輸出記數(shù)的初始位置，首先輸入一個

報數(shù)上限m,當達到報數(shù)上限時，那名士兵出列執(zhí)行任務(wù)，從下個人開始記

數(shù)，再次循環(huán)，直到只剩一人，得到其在隊伍中的位置，通過數(shù)學思想求得

題目要求即隊長為首的情況下需要記數(shù)初始位置。

2.程序執(zhí)行的命令包括：

（1）構(gòu)造數(shù)據(jù)結(jié)構(gòu)；（2）數(shù)據(jù)輸入；（3）執(zhí)行隊員出列；（4）輸出要求

數(shù)值

（5）結(jié)束。

3.數(shù)據(jù)測試：

當n=10輸出結(jié)果為：要求的位置是：9

（二）、概要設(shè)計

算法思想：本程序其實質(zhì)是約瑟夫環(huán)問題，本次實驗用了線性表和循環(huán)隊列兩

種數(shù)據(jù)結(jié)構(gòu)，并運用模塊化的程序設(shè)計思想，算法的實現(xiàn)是這樣的：

1,定義結(jié)構(gòu)體類型

2.定義變量并初始化

3.線性表初始化

4.隊員報數(shù)，是5的倍數(shù)出列

5.當隊員數(shù)等于1時，輸出

程序框圖：

（三）、詳細設(shè)計

宏定義：

^defineLIST_INIT_SIZE100

#defineLISTINCCREMENT10

數(shù)據(jù)類型定義:typedefintElemType;

定義數(shù)據(jù)結(jié)構(gòu)：

typedefstructKList/*定義數(shù)據(jù)結(jié)構(gòu)體類型*/

|

ElemType*elem;/*存儲空間基址*/

intlength;/*當前長度*/

intlistsize;/*當前分配的存儲容量(以sizeof(ElemType)為單位)*/

JSqList;

模塊一:創(chuàng)建線性表函數(shù)

SqListlnitList_Sq()/*創(chuàng)建線性表函數(shù)*/

{

SqListL;

=(ElemType*)malloc(LISTJNIT_SIZE*sizeof(ElemType));/**/

if(!printf("Failinnewcreatlist"),exit(O);/*存儲分配失敗*/

else

(

=0;/*空表長度為0*/

=UST」NIT_SIZE;/*初始存儲容量*/

)

)

模塊二:線性表再分配函數(shù)

SqListListlnsert_Sq(SqListL)/*線性表再分配函數(shù)*/

|

/*SqListL;*/

int*newbase;

newbase=(ElemType*)realloc,

+LISTINCCREMENT)*sizeof(ElemType));

/*為順序表增加一個大小為存儲LISTINCCREMENT個數(shù)據(jù)元素的空間*/

if(inewbase)printf("Failinnewaddlist"),exit(O);/*存儲分配失敗*/

else

(

=newbase;/*新基址*/

+=LISTINCCREMENT;/*增加存儲容量*/

}

)

主模塊:實現(xiàn)總體功能

main()

(

SqListL;

ints,i,m,count=0;/*聲明變量*/

L=lnitList_Sq();

printf("Pleaseinputthetataloftheteam:");

scanf("%d",&m);/*輸入敢死隊員總數(shù)*/

whRe(m!=O)/*當輸入為。時退出程序*/

while(m>/*當順序表當前分配的存儲空間大小不足時進行再分配*/

L=Listlnsert_Sq(L);

for(i=0;i<m;i++)[i]=i+l;/*為隊員賦值*/

s=m;

i=0;

while(s>l)/*當所剩敢死隊員總數(shù)為1時，總循環(huán)結(jié)束*/

(

for(i=0;i<m;i++)

if[i]!=O)

|

count++;

if(count==5)/*報數(shù)循環(huán)*/

(

[i]=0;/*表示隊員出列*/

count=0;/*計數(shù)器清零*/

s-;/*敢死隊員數(shù)-1*/

)

)

)

for(i=0;i<m;i++)/*輸出*/

if[i]!=0)

if([i]+2)%m==0)/**/

printf("\nThewantedorderis%dth\n",m);

else

printf("\nThewantedorderis%dth\n",[i]+2)%m);

printf("Exitpleaseinput'O'OrGoon...\nPleaseinputthetataloftheteam:")；

scanf("%d",&m);/*輸入敢死隊員總數(shù)*/

}

}

思考：本次設(shè)計問題的核心是如何輸出，因為這影響到了程序的時間復雜度。

總模塊的輸出設(shè)計是這樣實現(xiàn)的：總是從第一個開始報數(shù)，報到5出列，直到

剩下最后一個為止，然后就令這個位置為隊長位置，隊首為開始報數(shù)的位置，

并按此設(shè)計輸出即可。這種方法大大的降低了時間復雜度，其復雜度為

O(mn)o

(四)、程序調(diào)試及運行

程序調(diào)試過程中出現(xiàn)了下面的警告：

ompilinH

Mainfile：HYDESI~3.G

CoRPilin?：EDITOR-MVDESI^.C

T0Fi

7373le

Linescompiled：22

Warnings:00

EI'POFS：

Auarlablememory：295K

Warnings：,Pressanykey

—^=4^盤sage

CompilingC：\DOCUHE~i+1|卜||當yLESI3C：

.C25：Non-portablepointerassignmentinfunctionListinsert_Sq

WarningC：\DOCUME~111|\||L^^IXMVDESK3.C31：Non-poi*tablepointei*a

經(jīng)查詢錯誤為:不可移動的指針（地址常數(shù)）賦值

最終發(fā)現(xiàn)是下面的定義錯誤造成的

在變量定義中int*newbase=0;

定義成了intnewbase=0;

經(jīng)改正程序運行正常了.

二Compiling=

Mainfile：MVDESI^.C

Compiling：EDITOR-MYDESI，.C

TF?1

01e

7373

Linescompiled：00

Warnings:00

Errors-

Availablememory：295H

Success：Pressanykey

數(shù)據(jù)測試如下:

C<D:\tc\TC.EXE

Exitpleaseinput'0'OrGoon...

Pleaseinputtheratalofthetean：2

Thewantedpositionis2th

Exitpleaseinput'0'OrGoon...

Pleaseinputthetatalofthetean：9

Thewantedpositionis4th

Exitpleaseinput'0'OrGoon...

Pleaseinputtheratalofthetean：89

Thev/antedpositionis9th

Exitpleaseinput'0'OrGoon...

Pleaseinputthetatalofthetean：158

Theviantedpositionis80th

Exitpleaseinput'0'OrGoon...

Pleaseinputtheratalofthetean：589

Thewantedpositionis357th

Exitpleaseinput'?'OrGoon...

Pleaseinputthetatalofthetean：1256

Theuantedpositionis275th

Exitpleaseinput*0JOrGoon...

Pleaseinputthetatalofthetean：0

時間復雜度為O（mn）

（五）、設(shè)計總結(jié)

通過這次課程設(shè)計我又學到了很多東西,如程序的模塊化設(shè)計思想，同時也

加深了對數(shù)據(jù)結(jié)構(gòu)這門課程的理解和學會了如何在實際中應用數(shù)據(jù)結(jié)構(gòu)編程。

我首先是用線性表來做的，開始的想法是想用試驗的方法來查找到所要求

的位置，即首先從第一號開始報數(shù)，然后檢查最后剩下的一個是否是隊首，然

后從第二個開始報數(shù)……從第三個開始報數(shù)……直到所剩下的最后一個是隊

首。雖然這種方法可以實現(xiàn)查找，可卻是以消耗更多的時間為代價的，于是我

又想到了這個方法：總是從第一個開始報數(shù)，報到5出列，直到剩下最后一個

為止，然后就令這個位置為隊長位置，隊首為開始報數(shù)的位置，并按此設(shè)計輸

出即可。這種方法大大的降低了時間復雜度，復雜度為O(mn)。

(六)、附件

程序源代碼：

#defineLIST_INIT_SIZE100

SdefineLISTINCCREMENT10

typedefintElemType;

typedefstructKList/*定義數(shù)據(jù)結(jié)構(gòu)體類型*/

{

ElemType*elem;/*存儲空間基址*/

intlength;/*當前長度*/

intlistsize;/*當前分配的存儲容量(以sizeof(ElemType)為單位)*/

}SqList;

SqListlnitList_Sq()/*創(chuàng)建線性表函數(shù)*/

(

SqListL;

=(ElemType*)malloc(LISTJNIT_SIZE*sizeof(ElemType));/**/

if(!printf("Failinnewcreatlist"),exit(O);/*存儲分配失敗*/

else

(

=0;/*空表長度為0*/

=LIST_INIT_SIZE;/*初始存儲容量*/

)

)

SqListListlnsert_Sq(SqListL)/*線性表再分配函數(shù)*/

{

/*SqListL;*/

int*newbase;

newbase=(ElemType*)realloc,

+LISTINCCREMENT)*sizeof(ElemType));

/*為順序表增加一個大小為存儲LISTINCCREMENT個數(shù)據(jù)元素的空間*/

if(inewbase)printf("Failinnewaddlist"),exit(O);/*存儲分配失敗*/

else

=newbase;/*新基址*/

+=LISTINCCREMENT;/*增加存儲容量*/

)

main()

(

SqListL;

ints,i,m,count=0;/*聲明變量*/

L=lnitList_Sq();

printf("Pleaseinputthetataloftheteam:");

scanf("%d",&m);/*輸入敢死隊員總數(shù)*/

wh加(m!=0)/*當輸入為0時退出程序*/

while(m>/*當順序表當前分配的存儲空間大小不足時進行再分配*/

L=Listlnsert_Sq(L);

for(i=0;i<m;i++)[i]=i+l;/*為隊員賦值*/

s=m;

i=0;

while(s>l)/*當所剩敢死隊員總數(shù)為1時，總循環(huán)結(jié)束*/

(

for(i=0;i<m;i++)

if[i]!=0)

{

count++;

if(count==5)/*報數(shù)循環(huán)*/

{

[i]=0;/*表示隊員出列*/

count=0;/*計數(shù)器清零*/

s--;/*敢死隊員數(shù)-1*/

}

)

)

for(i=0;i<m;i++)/*輸出*/

if[i]!=0)

if([i]+2)%m==0)/**/

printf("\nThewantedorderis%dth\n",m);

else

printf("\nThewantedorderis%dth\n",[i]+2)%m);

printf("Exitpleaseinput'O'OrGoon...\nPleaseinputthetataloftheteam:\n");

scanf("%d",&m);/*輸入敢死隊員總數(shù)*/

)

)

三.單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)

(一)、需求分析

1.本程序輸入隊伍人數(shù)n為任意的，最終輸出記數(shù)的初始位置，首先輸入一

個報數(shù)上限m,當達到報數(shù)上限時，那名士兵出列執(zhí)行任務(wù)，從下個人開始記

數(shù)，再次循環(huán)，直到只剩一人，得到其在隊伍中的位置，通過數(shù)學思想求得題

目要求即隊長為首的情況下需要記數(shù)初始位置。

2.程序執(zhí)行的命令包括：

(1)構(gòu)造鏈表；(2)數(shù)據(jù)輸入；(3)執(zhí)行刪除；(4)輸出要求數(shù)值

(5)結(jié)束。

3.數(shù)據(jù)測試：

當n=10,m=5,輸出結(jié)果為：要求的位置是：9

(二卜概要設(shè)計

以單循環(huán)鏈表為存儲結(jié)構(gòu)，包含三個模塊：

1.主程序模塊

2.構(gòu)造鏈表并初始化

3.刪除結(jié)點

(三人詳細設(shè)計

1.結(jié)點類型和指針類型

typedefstructnode

(

intdata;

structnode*next;

}LNode;/*定義結(jié)點類型*/

LNode*p;

2.每個模塊的分析：

主程序模塊：

main()

(

LNode*p;

intm,n,z,y;

do

(

printf("Pleaseinputthepeoplenumberin'')；

scanf("%d",&n);

)

while(n<=0);

do

(

printf("Pleaseinputtheexcursion:\n");

scanf("%d",&m);

)

while(m<=0);

if(n=l)

printf("thepositionis:1");

else

(

p=CREAT(n);

y=DELETE(p,m);

z=n-y+2;

if(z%n==0)/*排除特殊情況*/

printf("thepositionis:\n%d\n",z);

else

printf("thepositionis:\n%d\n",(n-y+2)%n);

}/*通過數(shù)學思想求得實驗要求情況下的數(shù)值*/

}

2.構(gòu)造單循環(huán)鏈表并初始化模塊：

LNode*CREAT(intn)/*創(chuàng)建循環(huán)鏈表*/

(

LNode*sz*q,*t;

inti;

if(n!=0)

(

t=q=(LNode*)malloc(sizeof(LNode));

q->data=l;/*生成第一個結(jié)點并使其data值為1*/

for(i=2;i<=n;i++)

(

s=(LNode*)malloc(sizeof(LNode));/*自動生成結(jié)點*/

q->next=s;

q?>next?>data=i;/*給第/個結(jié)點賦值/*/

q=q->next;

}

q->next=t;

}/*生成后續(xù)結(jié)點，并使其data值即為它所在鏈表(隊伍)中的位置*/

returnt;

)

3.刪除結(jié)點模塊：

DELETE(LNode*t,intm)/*鏈表的刪除*/

LNode*a;inti;

while(t->next!=t)

for(i=l;i<m-l;i++)/*查找要刪除結(jié)點的前一結(jié)點*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*釋放結(jié)點*/

t=t->next;

}/*while循環(huán)依次刪除被點到的士兵*/

printf("\n");

return(t->data);

)

(四).調(diào)試分析：

說明：(1)本程序的運行環(huán)境是TC

(2)進入演示程序后顯示提示信息:

Exitpleaseinput'O'OrGoon

Pleaseinputthetataloftheteam:

輸入隊伍總?cè)藬?shù)

Pleaseinputtheexcursion:

輸入間隔人數(shù)

結(jié)果顯示：Thewantedpositionisth

選擇的位置

(3)調(diào)試

程序調(diào)試過程中遇到如下警告：

Edit

Line54Col9InsertIndentTabFillUnindent*I：SHEJI2.C

while<n!=0>

<

do

<

printf<MPleaseinputtheexcursion:0)；/*^S與怪口出？“

scanf<,,zdu,8tn>；

>

while<n<=0>；

if<n=l>

printf<uThewantedpositionis1th")；

else

<

p=CREAT<n>；

y=DELETE<pJ,n>；

z=n-sr+2；

if<zxn==0>/*H|2IH^T||env

printf<MTliewantedpositionisZdth：\nM,z>；

Message

Compilina1：\^2J|^p~lxSHEJ^-C：

ningIU0~1\SHEJI2.C54：Possiblyincorrectassignmentinfunctionmain

Fl-HeluFS-ZoomF6-SwitchF7-Ti、aceF8-SteuF9-MakeF10-Menu

發(fā)現(xiàn)錯誤為if(m=l)

后改正為if(m==l)程序運行正確了，運行如下:

顯示輸出如圖：

"D:\tckTC.EXE

Exitpleaseinput'0'OrGoon...

Ploaooinputthotatalofthotoam：2

Thev/antedpositionis2th

Exitpleaseinput'0'OrGoon...

Pleaseinputthetataloftheteam：?

Thewantedpositionis4th

Exitpleaseinput’0，OrGoon...

Pleaseinputthetatalofthetean：89

1hev/antedpositionis9th

Exitpleaseinput'0'OrGoon...

Pleaseinputthetatalofthetean：158

Thewantedpositionis80th

Exitpleaseinput*0*OrGoon...

Pleaseinputthetatalofthetean：589

Thev/antedpositionis357th

Exitpleaseinput'0'OrGoon...

Pleaeeinputthetatalo￡thet?

Thewantedpositionis275th

Exitpleaseinput'0'OrGoon...

Pleaseinputthetataloftheteam：0

(3)由程序分析可得：本程序時間復雜度為。(nm)!(4)

①在設(shè)計生成循環(huán)單鏈表時，考慮到程序結(jié)果需要士兵的位序，故將

每個結(jié)點的data值設(shè)置為他們在隊列中的位置，方便返回。

②在刪除單鏈表時，如果在報數(shù)時直接數(shù)到出列士兵則不方便鏈表的刪

除，可設(shè)置i<m-l找到出列士兵的前一位執(zhí)行如下：

for(i=l;i<m-l;i++)/*查找要刪除結(jié)點的前一結(jié)點*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*釋放結(jié)點*/

t=t->next;

③.在程序設(shè)計前，如果按原題所設(shè)，則需設(shè)隊長為第一位，再分別測試

從第幾個開始才能符合條件。現(xiàn)在改變思想，通過數(shù)學思想：單循環(huán)鏈表本身

是一個循環(huán)體，可先求出當從第一個出發(fā)的話，求出每隔m個出去一個最后是

誰未出列，然后再設(shè)置它為鏈頭，求出當他為隊首時從第幾個開始方能使其不

出列。(n-y+2)%n即可實現(xiàn)這功能！

(五人設(shè)計總結(jié)

通過這次課程設(shè)計我又學到了很多東西,如程序的模塊化設(shè)計思想，同時也

加深了對數(shù)據(jù)結(jié)構(gòu)這門課程的理解和學會了如何在實際中應用數(shù)據(jù)結(jié)構(gòu).

這個方法是用單循環(huán)鏈表來做的，實現(xiàn)的方法是這樣的：首先從第一號開

始報數(shù)，循環(huán)到指定的偏移位置刪除結(jié)點，直至剩下一個結(jié)點。然后設(shè)計輸

出，令這個位置為隊長位置，隊首為開始報數(shù)的位置，并按此輸出即為所求。

這種方法大大的降低了時間復雜度，復雜度為O(mn)。

(