數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-約瑟夫問(wèn)題求解

教育資料教育資料《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》

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

岸號(hào)：0313算?10的￡史上由于鏈…用的…是單向……表，而鏈表中按結(jié)點(diǎn)二除后運(yùn)行開(kāi)修當(dāng)前日期和時(shí)間：TueNOu0316：30：5岸號(hào)：0313算?10的輸入數(shù)據(jù)后界面：

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