數(shù)據(jù)結(jié)構(gòu)約瑟夫環(huán)實驗報告

伍）*#夕*大導(dǎo)世E岸花CMwnrCM*. fM?■tBlMMnwoati《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》

約瑟夫環(huán)實驗報告一實驗一專業(yè)：物聯(lián)網(wǎng)工程班級：物聯(lián)網(wǎng)1班學(xué)號：姓名：structLNodeintnum;structLNode*next;}； 〃定義鏈表typedefstructLNodeNODE;NODE*createlinklist(intn)(〃初始化循環(huán)鏈表,并返回頭指針NODE*head,*p,*q;inti=1;head=p=(structLNode*)malloc(sizeof(structLNode));p->num=i;for(i=2;i<=n;i++)(q=(structLNode*)malloc(sizeof(structLNode));if(q==O)return(O);p->next=q;p=q;p->num=i;}p->next=head; //使鏈表尾指向鏈表頭，形成循環(huán)鏈表returnhead;)voidjoseph(NODE*p,intn5intm){〃約瑟夫函數(shù)，用于輸出約瑟夫環(huán)intij;NODE*q;for(i=1;iv=n;i++)(for(j=1;j<m;j++)p=p->next; //計算出列者序號q=p->next;p->next=q->next;free(q);)p->next=NULL;voidmain()(NODE*head;intn,s,m;inti;〃確定計算系數(shù)物理網(wǎng)1班?15180118?劉沛航環(huán)繞圓桌的人數(shù)為從第兒人開始數(shù)到幾的人出列〃確定頭指針head=createlinklist(n);if(s==1)for(i=1;i<n;i++)head=head->next;elsefor(i=1;i<s-1;i++)head=head->next;〃輸出約瑟夫環(huán)出列順序出列的順序如下joseph(head,n,m);一、實驗?zāi)康?、熟悉VC環(huán)境，學(xué)習(xí)使用C語言利用鏈表的存儲結(jié)構(gòu)解決實際的問題。2、在編程、上機調(diào)試的過程中，加深對線性鏈表這種數(shù)據(jù)結(jié)構(gòu)的基本概念理解。3、鍛煉較強的思維和動手能力和更加了解編程思想和編程技巧。二、實驗內(nèi)容1、采用單向環(huán)表實現(xiàn)約瑟夫環(huán)。請按以下要求編程實現(xiàn)：①從鍵盤輸入整數(shù)m,通過create函數(shù)生成一個具有m個結(jié)點的單向環(huán)表。環(huán)表中的結(jié)點編號挨次為1,2,, ni。②從鍵盤輸入整數(shù)s(K=s<=m)和n,從環(huán)表的第s個結(jié)點開始計數(shù)為1,當(dāng)計數(shù)到第n個結(jié)點時，輸出該第n結(jié)點對應(yīng)的編號，將該結(jié)點從環(huán)表中消除，從輸出結(jié)點的下一個結(jié)點開始重新計數(shù)到n,這樣，不斷進(jìn)行計數(shù)，不斷進(jìn)行輸出，直到輸出了這個環(huán)表的全部結(jié)點為止。例如，m=10,s=3,n=4o則輸出序列為：6,10,4,9,5,2,1,3,8,7o三、程序設(shè)計1、概要設(shè)計為了解決約瑟夫環(huán)的問題，我們可以建立單向環(huán)表來存儲每個人的信息(該人的編號以及其下一個人的編號)，及結(jié)點，人后通過查找每一個結(jié)點，完成相應(yīng)的操作來解決約瑟夫問題。(1)抽象數(shù)據(jù)類型定義ADTJoh{數(shù)據(jù)對象：D={a|aeElemSet,i=1,2,...,n,nN0}數(shù)據(jù)關(guān)系：R1={<a,a>|a,aeD,i=1,2,...,n)

i-1ii-1i基本操作：create(&J,n)操作結(jié)果：構(gòu)造一個有n個結(jié)點的單向環(huán)表J。show(J)初始條件：單向環(huán)表J已存在。操作結(jié)果：按順序在屏幕上輸出J的數(shù)據(jù)元素。calculate(J,s,n)初始條件：單向環(huán)表J已存在，s>0,n>0,sv環(huán)表結(jié)點數(shù)。操作結(jié)果：返回約瑟夫環(huán)的計算結(jié)果。}ADTJoh(2)宏定義ttdefineNULL0^defineOK1ttdefineERROR-1(3)主程序流程開始開始輸入數(shù)據(jù)（m,s,n創(chuàng)建環(huán)表輸出建立好的環(huán)計算處理輸出結(jié)果結(jié)束（4）模塊調(diào)用關(guān)系 程序分為下述模塊：1）主函數(shù)模塊一一執(zhí)行輸入調(diào)用其他的功能函數(shù)2）創(chuàng)建環(huán)表模塊一一創(chuàng)建單向環(huán)表3）計算處理模塊一一計算出要出列的標(biāo)號并輸出4）顯示模塊一一輸出建立好的環(huán)表調(diào)用關(guān)系如下：主函數(shù)模塊

。創(chuàng)建環(huán)表模塊顯示%塊計算處%模塊2、詳細(xì)設(shè)計(1)數(shù)據(jù)類型設(shè)計typedefintElemType; 〃元素類型typedefstruct{ElemTypedata;structJoh*next;}Joh,*LinkList,*p; 〃結(jié)點類型，指針類型⑵操作算法Statuscreate(LinkList&J,intn){〃創(chuàng)建一個有n個結(jié)點的單向環(huán)表if(n<=0)returnERROR;//n<0錯誤J=(LinkList)malloc(sizeof(J));J->data=1;J->next=J;//建立第一個結(jié)點for(inti=n;i>1;-i){p=(LinkList)malloc(sizeof(J));p->data=i;p->next=J->next;J->next=p;〃插入至ij表頭)returnOK;}//createvoidshow(LinkListJ){〃主要的操作函數(shù)〃順序輸出環(huán)表J的結(jié)點P=J；p=p->next;while(p!=J){〃循環(huán)終止條件p=p->next;)}//showvoidcalculate(LinkListJJnts3intn){P=J;Joh*head=p; 〃聲明結(jié)點while(p->data!=s){p=p->next;head=p;}//尋覓起始結(jié)點while(p->next!=p){ 〃終止條件for(inti=0;i<n-1;i++){head=p; //保存前置節(jié)點p=p->next;)head->next=p->next;//刪除已輸出結(jié)點p=head->next;)if(n!=1)else}//calculate(3)主函數(shù)代碼intmain。{〃主函數(shù)Joh*J;intm3s5n;create(J5create(J5m);show(J);//創(chuàng)建單向環(huán)表j//輸出J的數(shù)據(jù)calculate(J5s5n); 〃計算并輸出結(jié)果return0;}//main四、程序調(diào)試分析1、細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都無非分，往往檢查了半天發(fā)現(xiàn)錯誤發(fā)生在某個括號，分號，引號，或者數(shù)據(jù)類型上。在寫主要操作函數(shù)caculate()時，在終止條件的書寫處不是很清晰，導(dǎo)致我浪費了不少時間。2、還有一點很大的感觸就是，在自己絞盡腦汁都解決不了遇到的問題時，一個很好的手段就是問詢同學(xué)，尋求其匡助，就比如我在想函數(shù)終止條件時，同學(xué)一句簡單的話語就讓我如夢初醒。這不是什么丟臉的事情，相反的，在快速解決問題的同時，還會收獲友誼，不是一舉兩得嗎。我想，這也是合作學(xué)習(xí)的真諦吧。五、用戶使用說明1、本程序的運行環(huán)境為Windows操作系統(tǒng)下的MicrosoftVisualC++6.0o2、在VC環(huán)境下打開程序后，按要求鍵入要求的數(shù)字，以等號或者空格斷開，敲擊“回車符”，即可以顯示要求的結(jié)果。3、按下任意鍵以繼續(xù)。六、程序運行結(jié)果程序測試1：程序測試2：j?,C KAH'QCSXj|F?S7C1^tug卜*“*4**??*****?“