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