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

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

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

第三章詳細(xì)設(shè)計(jì)3.1程序代碼#include<stdio.h>#include<malloc.h>typedefstructnode{ intdata; structnode*next;}node;//函數(shù)功能：構(gòu)造不帶頭結(jié)點(diǎn)的循環(huán)鏈表并賦值1~n，頭指針head指向第s個(gè)人node*create(intn,ints){ node*head; node*p,*q,*r;inti,j; if(n<=0)returnNULL;//若分配內(nèi)存失敗返回 //把長(zhǎng)度為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é)點(diǎn) for(j=1;j<s;j++)//從第s個(gè)人開(kāi)始數(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個(gè)人 while(head->next!=head)//循環(huán)結(jié)束后鏈表只剩一個(gè)元素 { //數(shù)到第m個(gè)刪除，head指向m的前一個(gè) 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"