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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(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)：姓名：劉沛航一、 實(shí)驗(yàn)?zāi)康?1、熟悉VC環(huán)境，學(xué)習(xí)使用C語言利用鏈表的存儲(chǔ)結(jié)構(gòu)解決實(shí)際的問題。2、在編程、上機(jī)調(diào)試的過程中，加深對(duì)線性鏈表這種數(shù)據(jù)結(jié)構(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，通過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)開始計(jì)數(shù)為1，當(dāng)計(jì)數(shù)到第n

2、個(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)開始重新計(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)的問題，我們可以建立單向環(huán)表來存儲(chǔ)每個(gè)人的信息（該人的編號(hào)以及其下一個(gè)人的編號(hào)），及結(jié)點(diǎn)，人后通過查找每個(gè)結(jié)點(diǎn)，完成相應(yīng)的操作來解決約瑟夫問題。（1） 抽象數(shù)據(jù)類型定義 ADT Joh數(shù)據(jù)對(duì)象：D=數(shù)據(jù)關(guān)系：R1=基本操作：create(&J, n)操作結(jié)果：構(gòu)造一個(gè)有n個(gè)結(jié)點(diǎn)的單向環(huán)表J。sh

3、ow(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é)果。ADT Joh（2）宏定義#define NULL 0 #define OK 1#define ERROR -1 （3）主程序流程開始輸入數(shù)據(jù)（m，s，n）創(chuàng)建環(huán)表輸出建立好的環(huán)表計(jì)算處理輸出結(jié)果結(jié)束（4） 模塊調(diào)用關(guān)系程序分為下述模塊：1）主函數(shù)模塊執(zhí)行輸入調(diào)用其他的功能函數(shù) 2）創(chuàng)建環(huán)表模塊創(chuàng)建單向環(huán)表 3）計(jì)算處理模塊計(jì)算出要出列的標(biāo)號(hào)并輸出 4）顯示模塊輸出建立好

4、的環(huán)表 調(diào)用關(guān)系如下： 主函數(shù)模塊 創(chuàng)建環(huán)表模塊 顯示模塊 計(jì)算處理模塊 2、詳細(xì)設(shè)計(jì)(1)數(shù)據(jù)類型設(shè)計(jì)typedef int ElemType; /元素類型typedef struct ElemType data;struct Joh *next;Joh, *LinkList,*p; /結(jié)點(diǎn)類型，指針類型(2)操作算法Status create(LinkList &J,int n)/創(chuàng)建一個(gè)有n個(gè)結(jié)點(diǎn)的單向環(huán)表if(n<=0)return ERROR;/n<0錯(cuò)誤J=(LinkList)malloc(sizeof(J);J->data=1;J->next=J;

5、/建立第一個(gè)結(jié)點(diǎn)for(int i=n;i>1;-i)p=(LinkList)malloc(sizeof(J);p->data=i;p->next=J->next;J->next=p;/插入到表頭return OK;/create void show(LinkList J)/主要的操作函數(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;/showvoid

6、calculate(LinkList J,int s,int n)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(int i=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("%dn",p-&g

7、t;data);elseprintf("n");/calculate(3)主函數(shù)代碼int main()/主函數(shù)Joh *J;int m,s,n;printf("The num of node is:");scanf("%d",&m);create(J,m); /創(chuàng)建單向環(huán)表Jshow(J); /輸出J的數(shù)據(jù)printf("n");printf("The first node which you want is:");scanf("%d",&s);printf

8、("The internal which you want is:");scanf("%d",&n);calculate(J,s,n); /計(jì)算并輸出結(jié)果return 0;/main四、程序調(diào)試分析 1、細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過分，往往檢查了半天發(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)很大的感觸就是，在自己絞盡腦汁都解決不了遇到的問題時(shí)，一個(gè)很好的手段就是詢問同學(xué)，尋求其幫助，就比如我在想函數(shù)終止條件時(shí)，

9、同學(xué)一句簡(jiǎn)單的話語就讓我如夢(mèng)初醒。這不是什么丟臉的事情，相反的，在快速解決問題的同時(shí)，還會(huì)收獲友誼，不是一舉兩得嗎。我想，這也是合作學(xué)習(xí)的真諦吧。五、用戶使用說明 1、本程序的運(yùn)行環(huán)境為Windows操作系統(tǒng)下的Microsoft Visual C+ 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ù)struct LNode int num; str

10、uct LNode *next; /定義鏈表typedef struct LNode NODE;NODE *createlinklist(int n)/初始化循環(huán)鏈表,并返回頭指針 NODE *head,*p,*q; int i=1; head=p=(struct LNode*)malloc(sizeof(struct LNode); p->num=i; for(i=2;i<=n;i+) q=(struct LNode*)malloc(sizeof(struct LNode); if(q=0) return(0); p->next=q; p=q; p->num=i; p

11、->next=head; /使鏈表尾指向鏈表頭,形成循環(huán)鏈表return head;void joseph(NODE *p,int n,int m)/約瑟夫函數(shù)，用于輸出約瑟夫環(huán)int i,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;void main() NODE *head; int n,s,m; int i;/確定計(jì)算系數(shù)printf("*物理網(wǎng)1班-劉沛航*n"); printf("圍繞圓桌的人數(shù)為?n"); scanf("%d",&n); printf("從第幾人開始?n"); scanf("%d",&s); printf("數(shù)到幾的人出列?n"); scanf("%d",&m); /確定頭指針 head=createlinklist(