天大數(shù)據(jù)結(jié)構(gòu)實驗報告一-約瑟夫環(huán)

數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告題目：用單循環(huán)鏈表解決約瑟夫問題學(xué)生姓名學(xué)生學(xué)號學(xué)院名稱計算機(jī)學(xué)院專業(yè)計算機(jī)科學(xué)與技術(shù)時間2013.10.7PAGE1PAGE1目錄第一章、需求分析…………11.1原題表述……………11.2所選的要求及整體規(guī)劃……………1第二章、概要設(shè)計…………22.1抽象數(shù)據(jù)類型…………22.2算法……………………2第三章、詳細(xì)設(shè)計…………33.1程序代碼………………3第四章、調(diào)試分析…………74.1調(diào)試工作………………74.2時間復(fù)雜度…………7第五章、測試結(jié)果…………85.1輸入數(shù)據(jù)和輸出數(shù)據(jù)樣例…………8計算機(jī)學(xué)院2012級數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告PAGE8第一章需求分析1.1原題表述設(shè)n個人圍坐在一圓桌周圍，現(xiàn)在從第s個人開始報數(shù)，數(shù)到第m個人，讓他出局；然后從出局者的下一人重新開始報數(shù)，數(shù)到第m個人，再讓他出局······如此反復(fù)，直到所有的人全部出局為止。1.2所選的要求及整體規(guī)劃 對于任意給定的n、s和m，求出這個n個人的出局序列，數(shù)據(jù)結(jié)構(gòu)采用單循環(huán)鏈表。構(gòu)造不帶頭結(jié)點的單循環(huán)鏈表。

第二章概要設(shè)計2.1抽象數(shù)據(jù)類型不帶頭結(jié)點的單循環(huán)鏈表2.2算法建立一個不帶頭結(jié)點的空循環(huán)鏈表，依次在鏈表中添加數(shù)據(jù)域為1~n的n個數(shù)據(jù)元素，此時指針head指向第一個元素，再用一個for循環(huán)讓頭指針head指向第s個元素，之后用while循環(huán)讓head指向第m-1個元素，刪除第m個元素，head指向第m+1個元素，直至鏈表中只剩一個元素。依次輸出被刪除的元素及最后剩余的元素。

第三章詳細(xì)設(shè)計3.1程序代碼#include<stdio.h>#include<malloc.h>typedefstructnode{ intdata; structnode*next;}node;//函數(shù)功能：構(gòu)造不帶頭結(jié)點的循環(huán)鏈表并賦值1~n，頭指針head指向第s個人node*create(intn,ints){ node*head; node*p,*q,*r;inti,j; if(n<=0)returnNULL;//若分配內(nèi)存失敗返回 //把長度為n的鏈表賦值1~n head=(node*)malloc(sizeof(node)); head->data=1; head->next=NULL; p=head; for(i=1;i<n-1;i++) { q=(node*)malloc(sizeof(node)); q->data=i+1; p->next=q; p=q; } //構(gòu)造循環(huán)鏈表 q=(node*)malloc(sizeof(node)); q->data=n; p->next=q; q->next=head;//不帶頭結(jié)點 for(j=1;j<s;j++)//從第s個人開始數(shù) { r=head->next; head=r; } returnhead;}intdel(node*head)//刪除{ node*p,*q; if(head==NULL)return-1; p=head; q=p->next; p->next=q->next; p=q->next; free(q); head=p;return1;}intmain(){ intn,m,s,person; node*head,*r,*p; //輸入n、m、s printf("Entern:\n"); scanf("%d",&n); printf("Enterm:\n"); scanf("%d",&m); printf("Enters:\n"); scanf("%d",&s); head=create(n,s);//head指向第s個人 while(head->next!=head)//循環(huán)結(jié)束后鏈表只剩一個元素 { //數(shù)到第m個刪除，head指向m的前一個 for(inti=1;i<m-1;i++) { r=head->next; head=r; } person=head->next->data; printf("Number%disout\n",person); p=head->next->next; del(head); head=p; } person=head->data; printf("Number%disout\n",person); system("pause"