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

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

課程設(shè)計(jì)

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

目錄

一?問題描述

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

（一）?需求分析

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

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

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

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

（六）?附件

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

（一）,需求分析

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

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

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

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

（六）?附件

一.問題描述

敢死隊(duì)問題

有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰都不想去，排長(zhǎng)決定用輪回?cái)?shù)數(shù)

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

個(gè)戰(zhàn)士上去。現(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號(hào)，大家圍坐成一圈，隨便從某一個(gè)戰(zhàn)士開

始計(jì)數(shù)，當(dāng)數(shù)到5時(shí)，對(duì)應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計(jì)

數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再?gòu)南乱粋€(gè)戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)

士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。

排長(zhǎng)是不愿意去的，假設(shè)排長(zhǎng)為1號(hào)，請(qǐng)你設(shè)計(jì)一程序，求出從第幾號(hào)戰(zhàn)士

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

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

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

（一卜需求分析

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

報(bào)數(shù)上限m,當(dāng)達(dá)到報(bào)數(shù)上限時(shí)，那名士兵出列執(zhí)行任務(wù)，從下個(gè)人開始記

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

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

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

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

數(shù)值

（5）結(jié)束。

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

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

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

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

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

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

2.定義變量并初始化

3.線性表初始化

4.隊(duì)員報(bào)數(shù)，是5的倍數(shù)出列

5.當(dāng)隊(duì)員數(shù)等于1時(shí)，輸出

程序框圖：

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

宏定義：

^defineLIST_INIT_SIZE100

#defineLISTINCCREMENT10

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

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

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

|

ElemType*elem;/*存儲(chǔ)空間基址*/

intlength;/*當(dāng)前長(zhǎng)度*/

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

JSqList;

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

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

{

SqListL;

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

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

else

(

=0;/*空表長(zhǎng)度為0*/

=UST」NIT_SIZE;/*初始存儲(chǔ)容量*/

)

)

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

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

|

/*SqListL;*/

int*newbase;

newbase=(ElemType*)realloc,

+LISTINCCREMENT)*sizeof(ElemType));

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

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

else

(

=newbase;/*新基址*/

+=LISTINCCREMENT;/*增加存儲(chǔ)容量*/

}

)

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

main()

(

SqListL;

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

L=lnitList_Sq();

printf("Pleaseinputthetataloftheteam:");

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

whRe(m!=O)/*當(dāng)輸入為。時(shí)退出程序*/

while(m>/*當(dāng)順序表當(dāng)前分配的存儲(chǔ)空間大小不足時(shí)進(jìn)行再分配*/

L=Listlnsert_Sq(L);

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

s=m;

i=0;

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

(

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

if[i]!=O)

|

count++;

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

(

[i]=0;/*表示隊(duì)員出列*/

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

s-;/*敢死隊(duì)員數(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);/*輸入敢死隊(duì)員總數(shù)*/

}

}

思考：本次設(shè)計(jì)問題的核心是如何輸出，因?yàn)檫@影響到了程序的時(shí)間復(fù)雜度。

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

剩下最后一個(gè)為止，然后就令這個(gè)位置為隊(duì)長(zhǎng)位置，隊(duì)首為開始報(bào)數(shù)的位置，

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

O(mn)o

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

程序調(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|卜||當(dāng)yLESI3C：

.C25：Non-portablepointerassignmentinfunctionListinsert_Sq

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

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

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

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

定義成了intnewbase=0;

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

二Compiling=

Mainfile：MVDESI^.C

Compiling：EDITOR-MYDESI，.C

TF?1

01e

7373

Linescompiled：00

Warnings:00

Errors-

Availablememory：295H

Success：Pressanykey

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

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

時(shí)間復(fù)雜度為O（mn）

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

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

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

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

的位置，即首先從第一號(hào)開始報(bào)數(shù)，然后檢查最后剩下的一個(gè)是否是隊(duì)首，然

后從第二個(gè)開始報(bào)數(shù)……從第三個(gè)開始報(bào)數(shù)……直到所剩下的最后一個(gè)是隊(duì)

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

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

為止，然后就令這個(gè)位置為隊(duì)長(zhǎng)位置，隊(duì)首為開始報(bào)數(shù)的位置，并按此設(shè)計(jì)輸

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

(六)、附件

程序源代碼：

#defineLIST_INIT_SIZE100

SdefineLISTINCCREMENT10

typedefintElemType;

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

{

ElemType*elem;/*存儲(chǔ)空間基址*/

intlength;/*當(dāng)前長(zhǎng)度*/

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

}SqList;

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

(

SqListL;

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

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

else

(

=0;/*空表長(zhǎng)度為0*/

=LIST_INIT_SIZE;/*初始存儲(chǔ)容量*/

)

)

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

{

/*SqListL;*/

int*newbase;

newbase=(ElemType*)realloc,

+LISTINCCREMENT)*sizeof(ElemType));

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

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

else

=newbase;/*新基址*/

+=LISTINCCREMENT;/*增加存儲(chǔ)容量*/

)

main()

(

SqListL;

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

L=lnitList_Sq();

printf("Pleaseinputthetataloftheteam:");

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

wh加(m!=0)/*當(dāng)輸入為0時(shí)退出程序*/

while(m>/*當(dāng)順序表當(dāng)前分配的存儲(chǔ)空間大小不足時(shí)進(jìn)行再分配*/

L=Listlnsert_Sq(L);

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

s=m;

i=0;

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

(

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

if[i]!=0)

{

count++;

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

{

[i]=0;/*表示隊(duì)員出列*/

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

s--;/*敢死隊(duì)員數(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);/*輸入敢死隊(duì)員總數(shù)*/

)

)

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

(一)、需求分析

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

個(gè)報(bào)數(shù)上限m,當(dāng)達(dá)到報(bào)數(shù)上限時(shí)，那名士兵出列執(zhí)行任務(wù)，從下個(gè)人開始記

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

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

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

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

(5)結(jié)束。

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

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

(二卜概要設(shè)計(jì)

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

1.主程序模塊

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

3.刪除結(jié)點(diǎn)

(三人詳細(xì)設(shè)計(jì)

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

typedefstructnode

(

intdata;

structnode*next;

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

LNode*p;

2.每個(gè)模塊的分析：

主程序模塊：

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ù)學(xué)思想求得實(shí)驗(yàn)要求情況下的數(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;/*生成第一個(gè)結(jié)點(diǎn)并使其data值為1*/

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

(

s=(LNode*)malloc(sizeof(LNode));/*自動(dòng)生成結(jié)點(diǎn)*/

q->next=s;

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

q=q->next;

}

q->next=t;

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

returnt;

)

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

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

LNode*a;inti;

while(t->next!=t)

for(i=l;i<m-l;i++)/*查找要?jiǎng)h除結(jié)點(diǎn)的前一結(jié)點(diǎn)*/

t=t->next;

a=t->next;

t->next=a->next;

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

t=t->next;

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

printf("\n");

return(t->data);

)

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

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

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

Exitpleaseinput'O'OrGoon

Pleaseinputthetataloftheteam:

輸入隊(duì)伍總?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)錯(cuò)誤為if(m=l)

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

顯示輸出如圖：

"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)由程序分析可得：本程序時(shí)間復(fù)雜度為。(nm)!(4)

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

每個(gè)結(jié)點(diǎn)的data值設(shè)置為他們?cè)陉?duì)列中的位置，方便返回。

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

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

for(i=l;i<m-l;i++)/*查找要?jiǎng)h除結(jié)點(diǎn)的前一結(jié)點(diǎn)*/

t=t->next;

a=t->next;

t->next=a->next;

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

t=t->next;

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

從第幾個(gè)開始才能符合條件?，F(xiàn)在改變思想，通過數(shù)學(xué)思想：?jiǎn)窝h(huán)鏈表本身

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

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

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

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

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

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

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

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

出，令這個(gè)位置為隊(duì)長(zhǎng)位置，隊(duì)首為開始報(bào)數(shù)的位置，并按此輸出即為所求。

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

(