循環(huán)單鏈表法實(shí)現(xiàn)Josephus問題.doc

向量法求解Josephus問題智能一班 林瀟 2220101468一 實(shí)驗(yàn)題目描述問題可描述如下：設(shè)有個人圍成一個環(huán)，現(xiàn)從第個人開始報數(shù)，數(shù)到第的人出列，然后從出列的下一個人從新開始報數(shù)，數(shù)到第的人又出列，如此重復(fù)，直至所有人均出列為止。求這些人出列的順序。二 實(shí)驗(yàn)?zāi)康氖炀氄莆站€性表的鏈表實(shí)現(xiàn)基本操作。三實(shí)現(xiàn)功能以循環(huán)單鏈表為存儲結(jié)構(gòu)，求解問題。四算法步驟編寫一個獨(dú)立的函數(shù)模塊求解問題，該函數(shù)僅通過參數(shù)與外界進(jìn)行數(shù)據(jù)交換，不使用其它非局部變量，實(shí)現(xiàn)方案應(yīng)具有良好的健壯性。另編寫一個主函數(shù)作為驅(qū)動，在主函數(shù)中處理數(shù)據(jù)的輸入與輸出。五程序結(jié)構(gòu)描述程序主要包括一個驅(qū)動功能的主函數(shù)，包括要排列數(shù)組元素的輸入，開始報數(shù)的位置，所報數(shù)字的輸入。還有一個獨(dú)立函數(shù)模塊來實(shí)現(xiàn)Josephus問題，主函數(shù)通過調(diào)用該函數(shù)來實(shí)現(xiàn)元素的出列，并將出列元素按順序重新存入數(shù)組，并將出列元素按順序輸出。六程序代碼#define N 10#include#includetypedef struct LNode/建立節(jié)點(diǎn)類型int message;struct LNode *next;LNode,*LinkList;void Josephus(LinkList L,int s,int m,int n,int e,int a);void main()int i,s,m,e;int a10;printf(請輸入Josephus環(huán)的元素);/輸入組成Josephus環(huán)的元素for(i=0;imessage=a0;L-next=NULL;Josephus(L,s,m,N,e,a);void Josephus(LinkList L,int s,int m,int n,int e,int a)LinkList p,q;int i,j; /將組成Josephus環(huán)的元素儲存到單鏈中for(i=n-1;i0;i-)p=(LinkList)malloc(sizeof(LNode);p-message=ai;p-next=L-next;L-next=p;LinkList H;H=L;for(i=0;inext; H-next=L;/尾部節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)p=L;for(i=1;inext;/找到開始報數(shù)位置i=1; /利用循環(huán)將元素輸出while(p-next!=p-next-next)for(j=1;jnext;q=p-next;p-next=q-next;e=q-message;free(q);/釋放被輸出元素的節(jié)點(diǎn)printf(n第%d 個出列的元素為%dn,i,e);p=p-next;i+; printf(n第%d 個出列的元素為%dn,10,p-message);七測試數(shù)組及結(jié)果測試數(shù)組為一個長度為10的整形數(shù)組，存儲元素為1-10是個整數(shù)。開始報數(shù)位置為數(shù)組的第二個元素，所報數(shù)字為3。測試結(jié)果截屏如下：八實(shí)驗(yàn)