線性表的應(yīng)用 約瑟夫環(huán)

線性表的應(yīng)用約瑟夫環(huán)（Josephu環(huán)）

約瑟夫問題：編號(hào)為1，2，..n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序來求出出列順序，并輸出結(jié)果。【問題描述】線性表的應(yīng)用--約瑟夫環(huán)（Josephu環(huán)）

對(duì)于一個(gè)綜合性問題，其求解步驟如下：1.分析問題，對(duì)問題建立數(shù)據(jù)模型2.根據(jù)問題的特點(diǎn)和運(yùn)算為數(shù)據(jù)模型設(shè)計(jì)適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)3.基于存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)相應(yīng)的算法4.調(diào)試算法，上機(jī)實(shí)現(xiàn)【分析問題】線性表的應(yīng)用--約瑟夫環(huán)（Josephu環(huán)）分析問題最好的方法是應(yīng)用實(shí)例

設(shè)：M的初值為3;n=6,6個(gè)人的密碼依次為：3，1，7，2，4，8【分析問題】線性表的應(yīng)用--約瑟夫環(huán)（Josephu環(huán)）21345631724821345672134564213456221345632134563出列順序?yàn)椋?，5，4，1，2，6

由上述分析可得：數(shù)據(jù)模型----線性表把每個(gè)人的編號(hào)看成是一個(gè)數(shù)據(jù)元素，n個(gè)編號(hào)構(gòu)成一個(gè)線性表線性表的應(yīng)用--約瑟夫環(huán)（Josephu環(huán)）

設(shè)：M的初值為3;n=6,6個(gè)人的密碼依次為：3，1，7，2，4，8【分析問題】數(shù)據(jù)模型

存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)線性表的應(yīng)用--約瑟夫環(huán)（Josephu環(huán)）

設(shè)：M的初值為3;n=6,6個(gè)人的密碼依次為：3，1，7，2，4，8【分析問題】約瑟夫環(huán)問題本身具有循環(huán)性質(zhì)，采用循環(huán)單鏈表需要設(shè)置頭結(jié)點(diǎn)嗎？為了統(tǒng)一對(duì)表中任意結(jié)點(diǎn)的操作，循環(huán)鏈表不帶頭結(jié)點(diǎn)1236head456

存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)線性表的應(yīng)用--約瑟夫環(huán)（Josephu環(huán)）

設(shè)：M的初值為3;n=6,6個(gè)人的密碼依次為：3，1，7，2，4，8【分析問題】類型描述：typedefstruct{//個(gè)人數(shù)據(jù)的基本結(jié)構(gòu)

intNum;//編號(hào)

intPwd;//密碼}datatype;Typedefstructnode{鏈表結(jié)點(diǎn)結(jié)構(gòu)

datatypedata;//或intNum,pwd;structnode*next;}*jsphList,Lnode;

為了便于刪除操作，從2開始計(jì)數(shù)線性表的應(yīng)用--約瑟夫環(huán)（Josephu環(huán)）

設(shè)：M的初值為3;n=6,6個(gè)人的密碼依次為：3，1，7，2，4，8【分析問題】算法設(shè)計(jì)1236head456prepCount=21.工作指針pre和p初始化，計(jì)數(shù)器count初始化

Pre=head;p=head->next;count=22.循環(huán)直到p=pre2.1如果count=m,則

2.1.1輸出結(jié)點(diǎn)p的編號(hào)和密碼

2.1.2新的m=當(dāng)前人的密碼

2.1.2刪除結(jié)點(diǎn)p2.1.3計(jì)數(shù)器count=1，重新開始計(jì)數(shù)。2.2否則，

2.2.1工作指針pre和p后移

2.2.2計(jì)數(shù)器增12.3鏈表中只剩下一個(gè)結(jié)點(diǎn)P,輸出結(jié)點(diǎn)p后將結(jié)點(diǎn)p刪除線性表的應(yīng)