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

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

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

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

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

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

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

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

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

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

intNum;//編號

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

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

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

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

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

2.1.1輸出結(jié)點p的編號和密碼

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

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

2.2.1工作指針pre和p后移

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