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

...wd......wd......wd...《數(shù)據(jù)構(gòu)造與算法設(shè)計(jì)》約瑟夫環(huán)實(shí)驗(yàn)報(bào)告——實(shí)驗(yàn)一專業(yè)：物聯(lián)網(wǎng)工程班級(jí)：物聯(lián)網(wǎng)1班學(xué)號(hào)：15180118姓名：劉沛航實(shí)驗(yàn)?zāi)康?、熟悉VC環(huán)境，學(xué)習(xí)使用C語(yǔ)言利用鏈表的存儲(chǔ)構(gòu)造解決實(shí)際的問(wèn)題。2、在編程、上機(jī)調(diào)試的過(guò)程中，加深對(duì)線性鏈表這種數(shù)據(jù)構(gòu)造的根本概念理解。3、鍛煉較強(qiáng)的思維和動(dòng)手能力和更加了解編程思想和編程技巧。二、實(shí)驗(yàn)內(nèi)容1、采用單向環(huán)表實(shí)現(xiàn)約瑟夫環(huán)。請(qǐng)按以下要求編程實(shí)現(xiàn)：從鍵盤輸入整數(shù)m，通過(guò)create函數(shù)生成一個(gè)具有m個(gè)結(jié)點(diǎn)的單向環(huán)表。環(huán)表中的結(jié)點(diǎn)編號(hào)依次為1，2，……，m。從鍵盤輸入整數(shù)s〔1<=s<=m〕和n，從環(huán)表的第s個(gè)結(jié)點(diǎn)開場(chǎng)計(jì)數(shù)為1，當(dāng)計(jì)數(shù)到第n個(gè)結(jié)點(diǎn)時(shí)，輸出該第n結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)，將該結(jié)點(diǎn)從環(huán)表中消除，從輸出結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開場(chǎng)重新計(jì)數(shù)到n，這樣，不斷進(jìn)展計(jì)數(shù)，不斷進(jìn)展輸出，直到輸出了這個(gè)環(huán)表的全部結(jié)點(diǎn)為止。例如，m=10，s=3，n=4。則輸出序列為：6，10，4，9，5，2，1，3，8，7。三、程序設(shè)計(jì)1、概要設(shè)計(jì)為了解決約瑟夫環(huán)的問(wèn)題，我們可以建設(shè)單向環(huán)表來(lái)存儲(chǔ)每個(gè)人的信息〔該人的編號(hào)以及其下一個(gè)人的編號(hào)〕，及結(jié)點(diǎn)，人后通過(guò)查找每個(gè)結(jié)點(diǎn)，完成相應(yīng)的操作來(lái)解決約瑟夫問(wèn)題。抽象數(shù)據(jù)類型定義ADTJoh{ 數(shù)據(jù)對(duì)象：D= 數(shù)據(jù)關(guān)系：R1= 根本操作：create(&J,n) 操作結(jié)果：構(gòu)造一個(gè)有n個(gè)結(jié)點(diǎn)的單向環(huán)表J。show(J) 初始條件：?jiǎn)蜗颦h(huán)表J已存在。 操作結(jié)果：按順序在屏幕上輸出J的數(shù)據(jù)元素。calculate(J,s,n)初始條件：?jiǎn)蜗颦h(huán)表J已存在，s>0，n>0，s<環(huán)表結(jié)點(diǎn)數(shù)。操作結(jié)果：返回約瑟夫環(huán)的計(jì)算結(jié)果。}ADTJoh〔2〕宏定義#defineNULL0#defineOK1#defineERROR-1〔3〕主程序流程開場(chǎng)開場(chǎng)輸入數(shù)據(jù)輸入數(shù)據(jù)〔m，s，n〕創(chuàng)立環(huán)表創(chuàng)立環(huán)表輸出建設(shè)好的環(huán)表輸出建設(shè)好的環(huán)表計(jì)算處理計(jì)算處理輸出結(jié)果輸出結(jié)果完畢完畢模塊調(diào)用關(guān)系程序分為下述模塊：1〕主函數(shù)模塊——執(zhí)行輸入調(diào)用其他的功能函數(shù)2〕創(chuàng)立環(huán)表模塊——?jiǎng)?chuàng)立單向環(huán)表3〕計(jì)算處理模塊——計(jì)算出要出列的標(biāo)號(hào)并輸出4〕顯示模塊——輸出建設(shè)好的環(huán)表調(diào)用關(guān)系如下：主函數(shù)模塊創(chuàng)立環(huán)表模塊顯示模塊計(jì)算處理模塊2、詳細(xì)設(shè)計(jì)(1)數(shù)據(jù)類型設(shè)計(jì)typedefintElemType;//元素類型typedefstruct{ ElemTypedata; structJoh*next;}Joh,*LinkList,*p;//結(jié)點(diǎn)類型，指針類型(2)操作算法Statuscreate(LinkList&J,intn){ //創(chuàng)立一個(gè)有n個(gè)結(jié)點(diǎn)的單向環(huán)表 if(n<=0) returnERROR; //n<0錯(cuò)誤 J=(LinkList)malloc(sizeof(J)); J->data=1; J->next=J;//建設(shè)第一個(gè)結(jié)點(diǎn) for(inti=n;i>1;--i){ p=(LinkList)malloc(sizeof(J)); p->data=i; p->next=J->next;J->next=p;//插入到表頭 } returnOK;}//createvoidshow(LinkListJ){//主要的操作函數(shù) //順序輸出環(huán)表J的結(jié)點(diǎn) p=J; printf("%d",p->data); p=p->next; while(p!=J){//循環(huán)終止條件 printf("%d",p->data); p=p->next; }}//showvoidcalculate(LinkListJ,ints,intn){ p=J; Joh*head=p; //聲明結(jié)點(diǎn) while(p->data!=s){ p=p->next; head=p; }//尋找起始結(jié)點(diǎn) while(p->next!=p){//終止條件 for(inti=0;i<n-1;i++){ head=p;//保存前置節(jié)點(diǎn) p=p->next; } printf("%d",p->data); head->next=p->next;//刪除已輸出結(jié)點(diǎn) p=head->next; } if(n!=1) printf("%d\n",p->data); else printf("\n");}//calculate(3)主函數(shù)代碼intmain(){//主函數(shù) Joh*J;intm,s,n; printf("Thenumofnodeis:"); scanf("%d",&m); create(J,m);//創(chuàng)立單向環(huán)表J show(J);//輸出J的數(shù)據(jù) printf("\n"); printf("Thefirstnodewhichyouwantis:"); scanf("%d",&s); printf("Theinternalwhichyouwantis:"); scanf("%d",&n); calculate(J,s,n);//計(jì)算并輸出結(jié)果 return0;}//main四、程序調(diào)試分析1、細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過(guò)分，往往檢查了半天發(fā)現(xiàn)錯(cuò)誤發(fā)生在某個(gè)括號(hào)，分號(hào)，引號(hào)，或者數(shù)據(jù)類型上。在寫主要操作函數(shù)caculate〔〕時(shí)，在終止條件的書寫處不是很清楚，導(dǎo)致我浪費(fèi)了很多時(shí)間。2、還有一點(diǎn)很大的感觸就是，在自己絞盡腦汁都解決不了遇到的問(wèn)題時(shí)，一個(gè)很好的手段就是詢問(wèn)同學(xué)，尋求其幫助，就比方我在想函數(shù)終止條件時(shí)，同學(xué)一句簡(jiǎn)單的話語(yǔ)就讓我如夢(mèng)初醒。這不是什么丟臉的事情，相反的，在快速解決問(wèn)題的同時(shí)，還會(huì)收獲友誼，不是一舉兩得嗎。我想，這也是合作學(xué)習(xí)的真諦吧。五、用戶使用說(shuō)明1、本程序的運(yùn)行環(huán)境為Windows操作系統(tǒng)下的MicrosoftVisualC++6.0。2、在VC環(huán)境下翻開程序后，按要求鍵入要求的數(shù)字，以等號(hào)或空格斷開，敲擊“回車符〞，即可以顯示要求的結(jié)果。3、按下任意鍵以繼續(xù)。六、程序運(yùn)行結(jié)果程序測(cè)試1：程序測(cè)試2：七、程序清單#include<stdio.h>#include<stdlib.h>//引用函數(shù)庫(kù)structLNode{intnum;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==0)return(0);p->next=q;p=q;p->num=i;}p->next=head;//使鏈表尾指向鏈表頭,形成循環(huán)鏈表 returnhead;}voidjoseph(NODE*p,intn,intm){ //約瑟夫函數(shù)，用于輸出約瑟夫環(huán)inti,j;NODE*q;for(i=1;i<=n;i++) { for(j=1;j<m;j++) p=p->next;//計(jì)算出列者序號(hào) q=p->next; p->next=q->next; printf("%d",q->num); free(q); }p->next=NULL;}voidmain(){ NODE*head;intn,s,m; inti; //確定計(jì)算系數(shù) printf("**********************物理網(wǎng)1班-15180118-劉沛航****************************\n");printf("圍繞圓桌的人數(shù)為?\n");scanf("%d",&n);printf("從第幾人開場(chǎng)?\n");scanf("%d",&s);printf("數(shù)到幾的人出列?\n");scanf("%d",&m); //確定頭指針head=createlinkli