數(shù)據(jù)構(gòu)造課程設(shè)計(jì)實(shí)驗(yàn)學(xué)校：江西農(nóng)業(yè)大學(xué)班級：軟件1115班姓名：朱利斌學(xué)號：1976課程：數(shù)據(jù)構(gòu)造課程設(shè)計(jì)指導(dǎo)教師：彭玉瑩實(shí)驗(yàn)一：約瑟夫問題問題簡述：約瑟夫環(huán)是一種數(shù)學(xué)的應(yīng)用問題：已知n個(gè)人（以編號1，2，3...n分別表達(dá)）圍坐在一張圓桌周邊。從編號為k的人開始報(bào)數(shù)，數(shù)到m的那個(gè)人出列；他的下一種人又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)律重復(fù)下去，直到圓桌周邊的人全部出列。約瑟夫問題是由古羅馬出名的史學(xué)家Josephus提出的問題演變而來，因此普通稱為Josephus問題。改善約瑟夫問題的描述是：編號為1，2，…，n的n個(gè)人按順時(shí)針方向圍坐一圈,每人有一種密碼Ki（整數(shù)），留作其出圈后應(yīng)報(bào)到Ki后出圈。報(bào)數(shù)辦法采用順時(shí)針報(bào)數(shù)和逆時(shí)針報(bào)數(shù)交替進(jìn)行，初始密碼可任意擬定。求最后剩余的人的編號。這個(gè)就是約瑟夫環(huán)問題的實(shí)際場景，后來老師規(guī)定我們對規(guī)定中的每人所持有的密碼以及第一次的報(bào)數(shù)上限值要用隨機(jī)數(shù)產(chǎn)生。因此約瑟夫環(huán)問題如果采用雙向循環(huán)鏈表則能較好的解決。循環(huán)鏈表的數(shù)據(jù)構(gòu)造，就是將一種鏈表的尾元素指針指向隊(duì)首元素。p->link=head解決問題的核心環(huán)節(jié)：先建立一種含有n個(gè)鏈結(jié)點(diǎn)，無頭結(jié)點(diǎn)的循環(huán)鏈表，然后擬定第一種報(bào)數(shù)人的位置，并不停地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表為空。一、題目內(nèi)容及規(guī)定【問題描述】編號是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一種密碼（正整數(shù)）。一開始任選一種正整數(shù)作為報(bào)數(shù)上限值m,從第一種仍開始順時(shí)針方向自1開始次序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一種人開始重新從1報(bào)數(shù)，如此下去，直到全部人全部出列為止。設(shè)計(jì)一種程序來求出出列次序?！疽?guī)定】運(yùn)用單向循環(huán)鏈表存儲構(gòu)造模擬此過程，按照出列的次序輸出各個(gè)人的編號。2）

掌握線性表的基本操作，如插入、刪除、檢索等在鏈?zhǔn)酱鎯?gòu)造上的運(yùn)算。二、

實(shí)驗(yàn)環(huán)境（硬/軟件規(guī)定）：WindowsXP+三、概要設(shè)計(jì)運(yùn)用單向循環(huán)鏈表存儲構(gòu)造模擬此過程，由于循環(huán)鏈表最后一種結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一人環(huán)，剛好和題中的“n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一種密碼（正整數(shù)）”內(nèi)容規(guī)定一致，并且，循環(huán)鏈表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)，運(yùn)用這一優(yōu)點(diǎn)可較容易地找出報(bào)數(shù)的人及下一種報(bào)數(shù)的人，最后按照出列的次序用一種for語句實(shí)現(xiàn)。循環(huán)鏈表的存儲構(gòu)造以下：structJoseph實(shí)踐約瑟夫問題時(shí)的核心是用兩個(gè)指針把一種移動(dòng)的，一種指向要?jiǎng)h除的節(jié)點(diǎn)，另外要注意保存頭指針。第一步是建立一種循環(huán)的單向鏈表。第二步是運(yùn)用指針遍歷鏈表同時(shí)計(jì)數(shù)到第m個(gè)時(shí)將其刪除。此時(shí)指針指向不變。其格式以下：voidoutput(structJoseph*head)//輸出出列狀況{inti,j=1;structJoseph*p1,*p2;p1=p2=head;//p1p2都指向頭指針for(i=1;i<m;i++)p1=p1->next;//從第M個(gè)人開始報(bào)數(shù)，因此p1指針依次后移，指向第m個(gè)人while(n>0){for(i=1;i<s;i++){p2=p1;p1=p1->next;//開始報(bào)數(shù)，報(bào)到s前p1、p2依次后移}printf("第%d個(gè)出列的人是:%d\n",j,p1->num);p2->next=p1->next;p1=p2->next;//此人出列，將p1->next賦給p2->next，將p1所指向的結(jié)點(diǎn)刪掉n--;//人數(shù)減少1j++;//出列人數(shù)加1}}2創(chuàng)立單循環(huán)鏈表創(chuàng)立一種空單循環(huán)鏈表，雙向循環(huán)鏈表和每個(gè)結(jié)點(diǎn)涉及兩個(gè)域:元素域和指針域。形成單循環(huán)鏈表的原理：定義三個(gè)指針變量H,r,s,三指針開始全部指向頭結(jié)點(diǎn)，在插入操作開始后，H不變?nèi)灾赶蝾^結(jié)點(diǎn)，s指針在插入過程中始終指向新插入的節(jié)點(diǎn)，而r指針緊隨其后，用于將新插入的節(jié)點(diǎn)和前一種節(jié)點(diǎn)連接起來，最后通過r指向頭指針H，來完畢環(huán)的操作。核心代碼實(shí)現(xiàn)以下：if(H==NULL){H=s，r=H;}//從鏈表的第一種節(jié)點(diǎn)插入else{r->next=s，r=s;//r后移}//鏈表的其它節(jié)點(diǎn)插入結(jié)束for循環(huán)后結(jié)成環(huán)的操作：r->next=H;/*生成循環(huán)單鏈表*/returnH;3查找并刪除節(jié)點(diǎn)每當(dāng)結(jié)點(diǎn)計(jì)數(shù)到某一結(jié)點(diǎn)時(shí)，將他的前驅(qū)結(jié)點(diǎn)接到他的后繼結(jié)點(diǎn)，然后將他的密碼值cipher賦給計(jì)數(shù)變量，再將此結(jié)點(diǎn)刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。函數(shù)通過代碼：p=H;pre=p;p=p->next;pre->next=p->next;p=pre->next;來刪除現(xiàn)在的那個(gè)結(jié)點(diǎn)q，通過循環(huán)來一次次刪除現(xiàn)在的結(jié)點(diǎn)，直到鏈表中剩余最后一種結(jié)點(diǎn)。五、程序清單/*運(yùn)行環(huán)境VC*/#include<>#include<>#include<>#defineLENsizeof(structJoseph)structJoseph//定義joseph{intnum;structJoseph*next;};intn,s,m;voidprint(structJoseph*head)//打印鏈對中的信息{structJoseph*p;//p指針p=head;//將p指向頭指針printf("%d個(gè)人的代號以下:\n",n);do{printf("%d",p->num);p=p->next;}while(p!=head);//依次輸入每個(gè)人的代號printf("\n");}voidoutput(structJoseph*head)//輸出出列狀況{inti,j=1;structJoseph*p1,*p2;p1=p2=head;//p1p2都指向頭指針for(i=1;i<m;i++)p1=p1->next;//從第M個(gè)人開始報(bào)數(shù)，因此p1指針依次后移，指向第m個(gè)人while(n>0){for(i=1;i<s;i++){p2=p1;p1=p1->next;//開始報(bào)數(shù)，報(bào)到s前p1、p2依次后移}printf("第%d個(gè)出列的人是:%d\n",j,p1->num);p2->next=p1->next;p1=p2->next;//此人出列，將p1->next賦給p2->next，將p1所指向的結(jié)點(diǎn)刪掉n--;//人數(shù)減少1j++;//出列人數(shù)加1}}structJoseph*create()//建立鏈隊(duì)列{inti;structJoseph*head;structJoseph*p1,*p2;printf("請輸入總?cè)藬?shù)(輸入0退出程序):\n");scanf("%d",&n);if(n==0)exit(0);//退出for(i=1;i<=n;i++){p1=(structJoseph*)malloc(LEN);p1->num=i;if(i==1)head=p1;elsep2->next=p1;p2=p1;}p2->next=head;//將整個(gè)鏈隊(duì)構(gòu)成一種環(huán)形print(head);printf("請輸入從第幾個(gè)人開始報(bào)數(shù):\n");scanf("%d",&m);printf("數(shù)到第幾個(gè)人出列:\n");scanf("%d",&s);returnhead;}main(){structJoseph*head;while(1){head=create();output(head);system("pause");system("cls");}}六、運(yùn)行成果七、實(shí)驗(yàn)心得在約瑟夫問題中，著重訓(xùn)練的是鏈表的應(yīng)用，特別是鏈表中結(jié)點(diǎn)的刪除、檢索等。由于單向鏈表等線性表的操作基本思想是一致的，因此通過對單向鏈表的練習(xí)來加深對線性表的理解。在本實(shí)驗(yàn)中，需要解決的問題的重點(diǎn)是如何找到要?jiǎng)h除的結(jié)點(diǎn)。因此，我首先考慮解決這個(gè)問題，即應(yīng)用循環(huán)語句來找到滿足條件的結(jié)點(diǎn)，我選用了if循環(huán)語句。然后應(yīng)用指針實(shí)現(xiàn)查找過程。在搞清出這些之后，在建立一種單向鏈表即形成程序。在通過調(diào)試改正某些細(xì)節(jié)即可。在編輯的過程中，將所學(xué)的知