約瑟夫環(huán)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

.需求分析約瑟夫環(huán)問題是典型的線性表的應(yīng)用實(shí)例，其開辟主要包括后臺(tái)數(shù)據(jù)庫的建立和維護(hù)以及前端應(yīng)用程序的開辟兩個(gè)方面。對(duì)于前者要求建立起數(shù)據(jù)一致性和完整性強(qiáng)、數(shù)據(jù)安全性好的庫。而對(duì)于后者則要求應(yīng)用程序功能完備，易使用等特點(diǎn)。關(guān)鍵詞：單循環(huán)鏈表；c語言；約瑟夫環(huán)；.概要設(shè)計(jì)本次課程設(shè)計(jì)的內(nèi)容是用單循環(huán)鏈表摹擬約瑟夫環(huán)問題，循環(huán)鏈表是一種首尾相接鏈表，其特點(diǎn)是無須增加存儲(chǔ)容量，僅對(duì)表的鏈接方式稍作改變，使表處理更加靈活，約瑟夫環(huán)問題就是用單循環(huán)鏈表處理的一個(gè)實(shí)際應(yīng)用。.問題描述約瑟夫環(huán)問題描述的是：設(shè)編號(hào)為1,2,…，n的n(n>0)個(gè)人按順時(shí)針方向圍坐一圈，每一個(gè)人持有一正整數(shù)密碼。開始時(shí)選擇一個(gè)正整數(shù)作為報(bào)數(shù)上限m,從第一個(gè)人開始順時(shí)針方向自1起順序報(bào)數(shù)，報(bào)到m時(shí)住手報(bào)數(shù)，報(bào)m的人出圈，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人起重新從1報(bào)數(shù)。如此下去，直到所有人都出圈為止。令n最大值為100。要求設(shè)計(jì)一個(gè)程序摹擬此過程，求出出圈的編號(hào)序列。.采用類c語言定義相關(guān)的數(shù)據(jù)類型結(jié)點(diǎn)的定義typedefstructNode{intdata;intpassword;structNode*next;(Node,*LinkList;單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：ADTList參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》.清華大學(xué)出版社.2嚴(yán)蔚敏，吳偉民.《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》.清華大學(xué)出版社.3譚浩強(qiáng).《c語言程序設(shè)計(jì)》.清華大學(xué)出版社.4寧正元，易金聰?shù)?《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機(jī)試驗(yàn)指導(dǎo)》.中國水利水出電版社,上海交通大學(xué)出版社，東南大學(xué)出版社課程設(shè)計(jì)完成之際，除了感到一種輕松以外，即將想到的就是對(duì)老師以及在課程設(shè)計(jì)過程中匡助我的同學(xué)們，因?yàn)樗麄兊闹笇?dǎo)和鞭策，才使我下定決心，集中精力投入到課程設(shè)計(jì)的建設(shè)。首先感謝我的指導(dǎo)老師王旭陽王老師，他在我的課程設(shè)計(jì)過程中提出了指導(dǎo)性的方案和架構(gòu)，比如讓我把密碼設(shè)計(jì)成自動(dòng)和手動(dòng)兩種方式，使我在不熟悉的領(lǐng)域中仍能迅速掌握新的技術(shù)。感謝我的數(shù)據(jù)結(jié)構(gòu)老師張永張老師和C語言老師王連相王老師在以往的基礎(chǔ)課學(xué)習(xí)中為我打下良好的基礎(chǔ)，這是我這次課程設(shè)計(jì)能夠順利完成的前提。我的同學(xué)在這次課設(shè)中也賦予了我一些好的建議！在此，也謝謝他們！附件I基本算法實(shí)現(xiàn)、/*Hash鏈表的刪除*/structnode/*定義線性單鏈表結(jié)點(diǎn)類型*/{intd;/*定義線性單鏈表結(jié)點(diǎn)數(shù)據(jù)類型*/structnode*nex結(jié)哽*指針*/)；whasht(h,k,f)/*Hash表的填入*/int(*f)()；/*Hash碼函數(shù)*/inik;structnode 外鏈Hash表的Hash表順序存儲(chǔ)空間*/{inti;structnode*p;i=(*f)(k);p=(structnode*)malloc(sizeof(slructn取od?fe)結(jié));h>d=k;/*填入關(guān)鍵字*/p~>next=h[i-l];h[i?l]咻;新/結(jié)*點(diǎn)連接到以H(i)為頭指針的鏈表鏈頭*/return;)whashs(h,k,f)/*Ha表sh的刪除*/ini(*0();/*碼as函h數(shù)*/intk;/*關(guān)鍵字*/structnode*h[];/*外鏈Hash表的順序存儲(chǔ)空間*/{inti,flag;structnode*p,*q,*s;i=(*f)(k);/*計(jì)算Hash碼*/p=h[i-l];q=NULL;flag=O;whilc(p!=NULL)/*在以H(i)為頭指針的鏈表中查找所有關(guān)鍵字k*Z{if(p_>d=k)/*找到*/{iRp=h[i-1])h[i-l]=p~>ne修xt改；*表結(jié)點(diǎn)的指針*/elseq->next=p->next;flag=l;s=p;p=p->next;free(s);1else{q=p;p=p->next;})if(flag=O)return;)main(){structnode*p,*h[I2];staticintk[l2]={9,31,26,19,1,13,2,11,27,16,5,21);intm,n=12,i();*h=(slruclnode*)malloc(n*sizeoflstructn分od配e)Ha;sH*表順序存儲(chǔ)空間*/執(zhí)行結(jié)果⑴找到輸入值的情況亙D:\Temp\MYDOCU~l\XIAOCH~l.exek=ll11369167111112223input2936916711112223(2)找不到輸入值的情況1369167111112223putk=23i?/ougaiguanjianzi?1369167111112223數(shù)據(jù)對(duì)象：D=ai|a日正整數(shù)，1=1,2,, n,n>0(數(shù)據(jù)關(guān)系:Rl=<ai-Lai>,|ai-l,ai^DJ=L2, ,n｝基本操作：CreatLinkList(LinkList*)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。ListInsert(&L,i,e)初始條件：線性表L己存在，1<i<ListLehnfeLt)+l.操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)無素e,L長度加1。ListDelete(&L,i,&e)初始條件：線性表L存在非空，l<i<ListLength(L).操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L長度減1。.各模塊的偽碼算法(1)主函數(shù)：intmain(void)(LinkListL;intpersonNumber,reportValue;intanay[MAXPERSONNUMBERJ;personNumber=GetPersonNumber();reportValue=GetFirstCountValue();CreatLinkList(&L);InitLinkList(&L,personNumber)；GetOutputOrder(&L,personNumber,reportValue,array);printResult(array,personNumber);return0;I(2)鏈表:voidCreatLinkList(LinkList*L)((*L)=(LinkList)malloc(sizeof(Node));if((*L)==NULL){exit(l);))voidInitLinkList(LinkList*L,intpersonNumber)(Node*p,*q;inti,a;P=(*L)；p->data=1;swilch(a){casel:p->password=GetPassword1();break;case2:p->password=GetPassword2();break;)for(i=2;i<=personNumber;i++)q=(LinkList)malloc(sizeof(Node));if(q==NULL)(exit(l);)switch(a){casel:p->password=GetPassword1();break;case2:p->password=GctPassword2();brcak;)q->data=i;p->next=q;P二q；)p->next=(*L);)(3)輸入密碼：intGetPassword1(){intpassword1;staticintcount1=1;if(password1>MAXPASSWORD||passwordI<0)(numberisnotusefuLpleaseprintftheintfrom0counll++;returnpassword1;)intGetPassword2(){intpassword2;staticintcount2=1;password2=count2+2;count2++;returnpassword2;)(4)輸出結(jié)果:voidprintRcsult(intarray」,intpersonNumbcr)(inti;for(i=0;i<personNumbcr;i++)()14.C語言程序設(shè)計(jì)#include<stdio.h>Intmain(){intn=100,s=1,m=10,i,j,s,w,q[100],p[100];for(i=0;i<n;i++)q[i]=0;sl=s;For(i=l;i<+n;i++)p[i-l]=i;For(i=n;i>=2;i-){sl=(sl+m-l)%i;If(sl==())sl=i；W=p[sl-1];For(j=sl;j<i;j)+tU-l]=p[j];P[i-l]=w;)For(i=0,j=n-l;i<n,j>=0;i++,j-)q[j]=p[i];For(i=0;i<n;i++)plij=q[i];For(i=0;i<n;i++).函數(shù)的調(diào)用關(guān)系圖.調(diào)試分析和測試結(jié)果.軟件使用說明書這是一個(gè)使用循環(huán)鏈表的經(jīng)典問題。因?yàn)橐粩嗟爻隽校捎面湵淼拇鎯?chǔ)形式能更好地摹擬出列的情況。問題描述采用不帶頭結(jié)點(diǎn)的循環(huán)單鏈表。其中，Maxpersonnumber為最大人數(shù)值，Maxflrstcountvalu為e最大上限數(shù)，Maxpassword為最大個(gè)人密碼值，Next為指向下一個(gè)結(jié)點(diǎn)的指針。設(shè)計(jì)總結(jié)我的這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目是：《約瑟夫環(huán)》，通過對(duì)該題目的設(shè)計(jì)，我加深了對(duì)數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的理解，進(jìn)一步地理解和掌握了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，特別是對(duì)單循環(huán)鏈表上基本運(yùn)算的實(shí)現(xiàn)，學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問題,鍛煉了自己動(dòng)手的能力。在此過程我深深地體味到了在自己獨(dú)立自主地解決問題的同時(shí)，也要借助團(tuán)隊(duì)的力量！俗話說的