數據結構實驗報告-約瑟夫問題求解

教育資料教育資料《計算機軟件技術基礎》

實驗報告I—數據結構實驗一、約瑟夫斯問題求解一、問題描述.實驗題目：編號1,2,....,n的1個人順時針圍坐一圈，每人持有一個密碼（正整數）。開始選擇一個正整數作為報數上限m，從第一個人開始順時針自1報數，報到m的人出列，將他的密碼作為新的m值，從他在順時針方向下一個人開始重新從1報數，直至所有人全部出列。.基本要求：利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序印出個人的編號。.測試數據：口=7,7個人的密碼依次為：3,1,7,2,4,8,4.m初值為6（正確的出列順序應為6,1,4,77,2,3）。二、需求分析.本程序所能達到的基本可能：該程序基于循環(huán)鏈表來解決約瑟夫問題。用循環(huán)鏈表來模擬口個人圍坐一圈，用鏈表中的每一個結點代表一個人和他所代表的密碼。在輸入初始密碼后m，對該鏈表進行遍歷，直到第m個結點，令該結點的密碼值作為新的密碼值，后刪除該結點。重復上述過程，直至所有的結點被釋放空間出列。.輸入輸出形式及輸入值范圍：程序運行后提示用戶輸入總人數。輸入人數口后，程序顯示提示信息，提示用戶輸入第i個人的密碼，在輸入達到預定次數后自動跳出該循環(huán)。程序顯示提示信息，提示用戶輸入初始密碼，密碼須為正整數且不大于總人數。3．輸出形式提示用戶輸入初始密碼，程序執(zhí)行結束后會輸出相應的出列結點的順序，亦即其編號。用戶輸入完畢后，程序自動運行輸出運行結果。.測試數據要求：測試數據n=7,7個人的密碼依次為：3,1,7,2,4,8,4。山初值為6（正確的出列順序應為6，1，4，7，2，3，5)。三、概要設計為了實現上述功能，應用循環(huán)鏈表來模擬該過程，用結構體來存放其相應的編號和密碼信息，因此需要循環(huán)鏈表結構體這個抽象數據類型。1．循環(huán)鏈表結構體抽象數據類型定義：ADTNode{數據對象：D={ai,bi,ci|ai￡int,bi￡int,ci￡(Node*),i=1,2...,n,n三0}:數據關系：R=0基本操作：CreatList(intn) //構建循環(huán)單鏈表；Order(intm,node*l) //輸出函數，輸出出列順序并刪除鏈表中的結點；}ADTnode；ADT的C語言形式說明：typedefstructNode{intnum; //結點的數據域，存放編號；intword;//結點的數據域，存放密碼；structNode*next; //結點的指針域，存放指向下一結點的指針；}Node；Node*CreatList() //建立循環(huán)單項鏈表；voidOrder(Node*h) //輸出出列順序并刪除結點；主程序流程及其模塊調用關系:).主程序流程：先提示用戶輸入相關數據：總人數，運行循環(huán)鏈表結構體模塊，輸入每個人持有的密碼值，創(chuàng)建出新鏈表，運行輸出函數模塊，再輸入初始密碼m值，輸出出列序列。(創(chuàng)建循環(huán)單鏈表模塊：實現鏈表的抽象數據類型刪除鏈表結點輸出序列模塊：實現輸出出列順序)).模塊調用關系：四、詳細設計1.元素類型、結點類型和結點指針類型：typedefstructNode //定義一個結構體，包含了每個人的序號和密碼{intword;intnum;structNode*next;}Node;2、創(chuàng)建單向循環(huán)鏈表類型：Node*CreatList() //尾插法創(chuàng)建一個單向循環(huán)鏈表{Node*p,*s;Node*h; //定義頭指針h=(Node*)malloc(sizeof(Node)); //申請動態(tài)存儲空間p=h;h->next=NULL; //初始化鏈表printf("第1個人的密碼是：")；scanf("%d",&h->word);h->num=1; //給頭指針賦值for(i=0;i<n-1;i++){s=(Node*)malloc(sizeof(Node));if(h->next==NULL)h->next=s;else p->next=s;p=s;printf("第％4個人的密碼是："，i+2);scanf("%d",&s->word);s->num=i+2;}p->next=h;returnh;}.刪除鏈表結點輸出函數模塊：voidOrder(Node*h) //輸出結果{Node*p;p=h;Node*d;while(p->next!=p){if(m<2){p=p->next;}else{for(i=1;i<m-1;i++) //查找第m個結點{p=p->next;}}d=p->next;m=d->word;printf("%d--",d->num);p->next=d->next; //刪除結點p=p->next;free(d);}printf("%d\n",p->num);}.主函數：voidmain(){printf("試驗名稱：約瑟夫斯問題求解\n");printf("學號：\n");printf("姓名：xx'n");printf("=========================================================\n");time_trawtime1;structtm*timeinfo1;time(&rawtime1);timeinfo1=localtime(&rawtime1); //時間函數；printf("程序運行開始,當前日期和時間:%s",asctime(timeinfo1));printf("請輸入總人數：")；scanf("%d",&n);h=CreatList();printf("請輸入初始密碼：")；scanf("%d",&m);if(m>n){printf("初始密碼不得大于總人數，請重新輸入。")；scanf("%d",&m);Order(h);}else{Order(h);}time_trawtime2;structtm*timeinfo2;time(&rawtime2);timeinfo2=localtime(&rawtime2);printf("程序運行結束,當前日期和時間:%s",asctime(timeinfo2));while(1);}.函數調用關系：主函數調用Node*CreatList()創(chuàng)建循環(huán)單向鏈表以及調用voidOrder(Node*h)進行刪除結點及輸出序列功能。輸出出列序列輸出以后，函數調用結束。五、調試分析

岸號：0313算?10的￡史上由于鏈…用的…是單向……表，而鏈表中按結點二除后運行開修當前日期和時間：TueNOu0316：30：5岸號：0313算?10的輸入數據后界面：

5l\Adrnini^trator\DesLtcp\JF^Si4^KDrbug\TcirigxiniJQ3e,phus.eKei叵1317245l\Adrnini^trator\DesLtcp\JF^Si4^KDrbug\TcirigxiniJQ3e,phus.eKei叵131724S467日皆即皆晉晉甘(生--rrp34.3.3.ripr:rF節(jié)7.--SM0055Tfl上竽密密密蜜密空艇^AAAAAA^卷1234567^-ll1qngxin.Josephu工exe 上工作出現了t｛可史.m當程序修止正常二歸.諳關閉讀程序，3關閉程序4調試程序八、遇到的問題和解決方法：回S31.起初程序編寫好后顯示0error，回S3■'F:、學習七大二'K?管柏實踐\Debug\.Tongxir.Josephu&.exe"試驗名稱：約瑟夫斯問題求解學號：031350103姓名：佟欣程請第第第第第第第請IG-程pP■:rJrTzrp.rzrpr=rrT=rFTJrr=rp程請第第第第第第第請IG-程pP■:rJrTzrp.rzrpr=rrT=rFTJrr=rp2AyAnL^A5?55-.fl55e取醇愷密密密密密密崎7-舒趾△運-4-行0331724*840331.改正上述錯誤后雖然可以運行但輸出產生了一串隨機數。經調試程序發(fā)現，出現隨機數是因為頭指針的數據域沒有賦值。增加了對頭指針數據域賦值語句后隨機數消失。.在調試的開始發(fā)現輸出順序有錯誤，經調試發(fā)現是因為查找第m個結點時所用的for循環(huán)是從i=1到i<m-1的，但第二個人密碼為1，沒有考慮m<2的情況，于是輸出出錯。改正方式是增加一個m<2的特殊情況。經運行，輸出成功。九、實驗收獲和感想：約瑟夫問題是我們學習了軟件工程原理與應用這門課后第一次上機編寫程序，在以前接觸c語言的時候，我們是沒有學過鏈表的，因此，以前也沒有編寫過循環(huán)鏈表的程序。本學期的軟件工程原理與應用開課后，我才真正深入學習和理解了鏈表結構，通過此次編程對所學知識有了具體的運用，使我對鏈表結構有了更清晰的了解，從茫然到能正確運用，感覺收獲非常大。約瑟夫問題雖說是鏈表問題中相對來說最簡單的一個問題，但我剛開始時卻是充滿了茫然，編出來的程序處處報錯。起初，并沒有真正理解建立鏈表的算法，我單純仿著課本上的代碼照搬上去，不會正確的運用，結果自然是大量的錯誤。于是我放下急于求成的心態(tài)，認真看書，認真查資料，終于成功地寫出了這個約瑟夫問題的程序。當它最終0error通過且運行正常時，我的心中充滿了激動和滿足感，看著自己的作品，很有成就感。編寫完整的程序最考驗人的耐心和細心，每一個微不足道的小錯誤都會導致很長時間的排錯。這次的計算機實踐使我在運用中理解了循環(huán)鏈表這部分的知識，為后面的學習和接下來的計算機實踐打好了基礎，奠定了基石。十、附錄源程序文件清單：#include<stdio.h>#include<malloc.h>#include<time.h>#defineNULL0typedefstructNode //定義一個結構體，包含了每個人的序號和密碼{intword;intnum;structNode*next;}Node;inti,n,m;Node*h;Node*CreatList() //尾插法創(chuàng)建一個單向循環(huán)鏈表{Node*p,*s;Node*h; //定義頭指針h=(Node*)malloc(sizeof(Node)); //申請動態(tài)存儲空間p=h;h->next=NULL; //初始化鏈表printf("第1個人的密碼是：");scanf("%d",&h->word);h->num=1; //給頭指針賦值for(i=0;i<n-1;i++){s=(Node*)malloc(sizeof(Node));if(h->next==NULL)h->next=s;else p->next=s;p=s;printf("第％4個人的密碼是："，i+2);scanf("%d",&s->word);s->num=i+2;}p->next=h;returnh;}voidOrder(Node*h) //輸出結果{Node*p;p=h;Node*d;while(p->next!=p){if(m<2){p=p->next;}else{for(i=1;i<m-1;i++) //查找第m個結點{p=p->next;))d=p->next;m=d->word;printf("%d--”,d->num);p->next=d->next;〃刪除結點p=p->next;free(d);)printf("%d\n",p->num);)voidmain()(printf("試驗名稱：約瑟夫斯問題求解\n");printf("學號：\n");printf("姓名：xx'n");printf("=========================================================\n");time_trawtime1;structtm*timeinfo1;time(&rawtime1);timeinfo1=localtime(&rawtime1); //時間函數；printf("程序運行開始，當前日期和時間：%s",asctime(timeinfo1));printf("請輸入總人數：")；scanf("%d",&n);h=CreatList();printf(