約瑟夫環(huán)數(shù)據(jù)結構設計

.需求分析約瑟夫環(huán)問題是典型的線性表的應用實例，其開辟主要包括后臺數(shù)據(jù)庫的建立和維護以及前端應用程序的開辟兩個方面。對于前者要求建立起數(shù)據(jù)一致性和完整性強、數(shù)據(jù)安全性好的庫。而對于后者則要求應用程序功能完備，易使用等特點。關鍵詞：單循環(huán)鏈表；c語言；約瑟夫環(huán)；.概要設計本次課程設計的內容是用單循環(huán)鏈表摹擬約瑟夫環(huán)問題，循環(huán)鏈表是一種首尾相接鏈表，其特點是無須增加存儲容量，僅對表的鏈接方式稍作改變，使表處理更加靈活，約瑟夫環(huán)問題就是用單循環(huán)鏈表處理的一個實際應用。.問題描述約瑟夫環(huán)問題描述的是：設編號為1,2,…，n的n(n>0)個人按順時針方向圍坐一圈，每一個人持有一正整數(shù)密碼。開始時選擇一個正整數(shù)作為報數(shù)上限m,從第一個人開始順時針方向自1起順序報數(shù)，報到m時住手報數(shù)，報m的人出圈，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新從1報數(shù)。如此下去，直到所有人都出圈為止。令n最大值為100。要求設計一個程序摹擬此過程，求出出圈的編號序列。.采用類c語言定義相關的數(shù)據(jù)類型結點的定義typedefstructNode{intdata;intpassword;structNode*next;(Node,*LinkList;單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：ADTList參考文獻1嚴蔚敏，吳偉民.《數(shù)據(jù)結構（C語言版）》.清華大學出版社.2嚴蔚敏，吳偉民.《數(shù)據(jù)結構題集（C語言版）》.清華大學出版社.3譚浩強.《c語言程序設計》.清華大學出版社.4寧正元，易金聰?shù)?《數(shù)據(jù)結構習題解析與上機試驗指導》.中國水利水出電版社,上海交通大學出版社，東南大學出版社課程設計完成之際，除了感到一種輕松以外，即將想到的就是對老師以及在課程設計過程中匡助我的同學們，因為他們的指導和鞭策，才使我下定決心，集中精力投入到課程設計的建設。首先感謝我的指導老師王旭陽王老師，他在我的課程設計過程中提出了指導性的方案和架構，比如讓我把密碼設計成自動和手動兩種方式，使我在不熟悉的領域中仍能迅速掌握新的技術。感謝我的數(shù)據(jù)結構老師張永張老師和C語言老師王連相王老師在以往的基礎課學習中為我打下良好的基礎，這是我這次課程設計能夠順利完成的前提。我的同學在這次課設中也賦予了我一些好的建議！在此，也謝謝他們！附件I基本算法實現(xiàn)、/*Hash鏈表的刪除*/structnode/*定義線性單鏈表結點類型*/{intd;/*定義線性單鏈表結點數(shù)據(jù)類型*/structnode*nex結哽*指針*/)；whasht(h,k,f)/*Hash表的填入*/int(*f)()；/*Hash碼函數(shù)*/inik;structnode 外鏈Hash表的Hash表順序存儲空間*/{inti;structnode*p;i=(*f)(k);p=(structnode*)malloc(sizeof(slructn取od?fe)結);h>d=k;/*填入關鍵字*/p~>next=h[i-l];h[i?l]咻;新/結*點連接到以H(i)為頭指針的鏈表鏈頭*/return;)whashs(h,k,f)/*Ha表sh的刪除*/ini(*0();/*碼as函h數(shù)*/intk;/*關鍵字*/structnode*h[];/*外鏈Hash表的順序存儲空間*/{inti,flag;structnode*p,*q,*s;i=(*f)(k);/*計算Hash碼*/p=h[i-l];q=NULL;flag=O;whilc(p!=NULL)/*在以H(i)為頭指針的鏈表中查找所有關鍵字k*Z{if(p_>d=k)/*找到*/{iRp=h[i-1])h[i-l]=p~>ne修xt改；*表結點的指針*/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*表順序存儲空間*/執(zhí)行結果⑴找到輸入值的情況亙D:\Temp\MYDOCU~l\XIAOCH~l.exek=ll11369167111112223input2936916711112223(2)找不到輸入值的情況1369167111112223putk=23i?/ougaiguanjianzi?1369167111112223數(shù)據(jù)對象：D=ai|a日正整數(shù)，1=1,2,, n,n>0(數(shù)據(jù)關系:Rl=<ai-Lai>,|ai-l,ai^DJ=L2, ,n｝基本操作：CreatLinkList(LinkList*)操作結果：構造一個空的線性表L。ListInsert(&L,i,e)初始條件：線性表L己存在，1<i<ListLehnfeLt)+l.操作結果：在L中第i個位置之前插入新的數(shù)據(jù)無素e,L長度加1。ListDelete(&L,i,&e)初始條件：線性表L存在非空，l<i<ListLength(L).操作結果：刪除L的第i個元素，并用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)輸出結果:voidprintRcsult(intarray」,intpersonNumbcr)(inti;for(i=0;i<personNumbcr;i++)()14.C語言程序設計#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ù)的調用關系圖.調試分析和測試結果.軟件使用說明書這是一個使用循環(huán)鏈表的經典問題。因為要不斷地出列，采用鏈表的存儲形式能更好地摹擬出列的情況。問題描述采用不帶頭結點的循環(huán)單鏈表。其中，Maxpersonnumber為最大人數(shù)值，Maxflrstcountvalu為e最大上限數(shù)，Maxpassword為最大個人密碼值，Next為指向下一個結點的指針。設計總結我的這次數(shù)據(jù)結構課程設計的題目是：《約瑟夫環(huán)》，通過對該題目的設計，我加深了對數(shù)據(jù)結構及存儲結構的理解，進一步地理解和掌握了課本中所學的各種數(shù)據(jù)結構，特別是對單循環(huán)鏈表上基本運算的實現(xiàn)，學會了如何把學到的知識用于解決實際問題,鍛煉了自己動手的能力。在此過程我深深地體味到了在自己獨立自主地解決問題的同時，也要借助團隊的力量！俗話說的