《數(shù)據(jù)結(jié)構(gòu)約瑟夫環(huán)實驗報告(共7頁).doc》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結(jié)構(gòu)約瑟夫環(huán)實驗報告(共7頁).doc（7頁珍藏版）》請在匯文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實 驗 報 告實 驗 課 程：  線性表的應用 專  業(yè)： *  年級（班級）： * 姓  名： * 學  號： * 實 驗 報 告實驗名稱約瑟夫環(huán)問題實驗時間實驗地點指導教師一、實驗目的：1. 熟練掌握線性表的基本操作在順序存儲和鏈式存儲上的實現(xiàn)；2. 以線性表的各種操作（建立、插入、刪除、遍歷等）的實現(xiàn)為重點；3. 掌握線性表的動態(tài)分配順序存儲結(jié)構(gòu)的定義和基本操作的實現(xiàn)；4. 通過本章實驗加深對C語言的使用（特別是函數(shù)的參數(shù)調(diào)用、指針類型的應用和鏈表的建立等各種基本操作）。二、實驗內(nèi)容：【問題描述】設有N個

2、人圍坐一圈，現(xiàn)從某個人開始報數(shù)，數(shù)到M的人出列，接著從出列的下一個人開始重新報數(shù)，數(shù)到M的人又出列，如此下去，直到所有的人都出列為止。試設計確定他們的出列次序序列的程序【基本要求】選擇單向循環(huán)鏈表或循環(huán)數(shù)組作為存儲結(jié)構(gòu)模擬整個過程，并依次輸出出列的各人的編號。【實現(xiàn)提示】 由于問題是由古羅馬著名史學家Josephus提出的問題演變而來，所以通常稱之為Josephus問題。程序運行之后，首先要求用戶指定初始報數(shù)的上限值，可以N=30，此題中循環(huán)鏈表可以不設頭結(jié)點，而且必須注意空表和“非空表”的界限。如 N=8，M=4時，若從第一人開始，設每個人的編號依次是1，2，3，.開始報數(shù)，則得到的出列次序

3、為4，8，5，2，1，3，7，6。 專心-專注-專業(yè)三、實驗程序：#include<stdio.h> #include<malloc.h>#include<stdlib.h>/*宏定義和單鏈表類型定義*/#define ListSize 100typedef int DataType;typedef struct NodeDataType data;struct Node *next;ListNode,*LinkList;/*函數(shù)聲明*/LinkList CreateCycList(int n);/*創(chuàng)建一個長度為n的循環(huán)單鏈表的函數(shù)聲明*/void Jos

4、ephus(LinkList head,int n,int m,int k); /*在長度為n的循環(huán)單鏈表中，報數(shù)為編號為m的出列*/void DisplayCycList(LinkList head);/*輸出循環(huán)單鏈表*/void main() LinkList h; int n,k,m; printf("輸入環(huán)中人的個數(shù)n="); scanf("%d",&n); printf("輸入開始報數(shù)的序號k="); scanf("%d",&k); printf("報數(shù)為m的人出列m=&quo

5、t;); scanf("%d",&m); h=CreateCycList(n); Josephus(h,n,m,k); void Josephus(LinkList head,int n,int m,int k)/*在長度為n的循環(huán)單鏈表中，從第k個人開始報數(shù)，數(shù)到m的人出列*/ ListNode *p,*q; int i; p=head; for(i=1;i<k;i+) /*從第k個人開始報數(shù)*/ q=p; p=p->next; while(p->next!=p) for(i=1;i<m;i+) /*數(shù)到m的人出列*/ q=p; p=p-&

6、gt;next; q->next=p->next; /*將p指向的結(jié)點刪除，即報數(shù)為m的人出列*/ printf("%4d",p->data); free(p); p=q->next; /*p指向下一個結(jié)點，重新開始報數(shù)*/ printf("%4dn",p->data);LinkList CreateCycList(int n)/*宏定義和單鏈表類型定義*/ LinkList head=NULL; ListNode *s,*r; int i; for(i=1;i<=n;i+) s=(ListNode*)malloc(s

7、izeof(ListNode); s->data=i; s->next=NULL; if(head=NULL) head=s; else r->next=s; r=s; r->next=head; return head;void DisplayCycList(LinkList head)/*輸出循環(huán)鏈表的每一個元素*/ ListNode *p; p=head; if(p=NULL) printf("該鏈表是空表"); return; while(p->next!=head)/*如果不是最后一個結(jié)點，輸出該結(jié)點*/ printf("%

8、4d",p->data); p=p->next; printf("%4dn",p->data);/*輸出最后一個結(jié)點*/四、實驗結(jié)果及分析：五、感想與體會： 做這次數(shù)據(jù)結(jié)構(gòu)實驗，不僅讓我對這段時間內(nèi)所學的知識有了更好的理解，而且對自己的編程能力也有所提高。發(fā)現(xiàn)在解決問題的過程中還有很多不會的地方，在編程和寫報告的過程中曾多次遇到各種各樣的問題，發(fā)現(xiàn)自己的編程能力亟待提高。通過與同學們的交流以及自己思考，最終得到解決并順利完成了此次作業(yè)。六、得分：指導教師評語： 實驗目的明確； 操作步驟正確； 設計文稿符合要求； 實驗結(jié)果正確； 實驗分析總結(jié)全面； 實驗報告規(guī)范； 評閱教師簽名：