數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目： 班級： 組長：姓名（學(xué)號） 組員：姓名（學(xué)號）… 指導(dǎo)教師： 完成日期： 成績：目錄TOC\o"1-2"\h\z\u1需求分析 31.1功能分析 31.2設(shè)計(jì)平臺 32概要設(shè)計(jì) 32.1類LinkList 32.2類Joseph 42.3類異常處理 43詳細(xì)設(shè)計(jì)和實(shí)現(xiàn) 43.1創(chuàng)建結(jié)點(diǎn)Node 43.2創(chuàng)建雙向循環(huán)鏈表 53.3從鏈表中刪除結(jié)點(diǎn) 64調(diào)試與操作說明 104.1調(diào)試情況 104.2操作說明 105設(shè)計(jì)總結(jié) 11參考文獻(xiàn) 12附錄 12 1需求分析1.1功能分析本次選做的課程設(shè)計(jì)是改進(jìn)約瑟夫(Joseph)環(huán)問題。約瑟夫環(huán)問題是一個古老的數(shù)學(xué)問題，本次課題要求用程序語言的方式解決數(shù)學(xué)問題。此問題僅使用單循環(huán)鏈表就可以解決此問題。而改進(jìn)的約瑟夫問題通過運(yùn)用雙向循環(huán)鏈表，同樣也能方便地解決。在建立雙向循環(huán)鏈表時，因?yàn)榧s瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個結(jié)點(diǎn)的數(shù)據(jù)域的值定為生成結(jié)點(diǎn)時的順序號和每個人持有的密碼。進(jìn)行操作時，用一個指針current指向當(dāng)前的結(jié)點(diǎn)，指針front始終指向頭結(jié)點(diǎn)。然后建立雙向循環(huán)鏈表，因?yàn)槊總€人的密碼是通過rand()函數(shù)隨機(jī)生成的，所以指定第一個人的順序號，找到結(jié)點(diǎn)，不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表剩下最后一個結(jié)點(diǎn)，通過一系列的循環(huán)就可以解決改進(jìn)約瑟夫環(huán)問題。1、 本演示程序中，利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬約瑟夫問題的進(jìn)行。程序運(yùn)行后，首先要求用戶指定初始報(bào)數(shù)上限值，然后讀取個人的密碼?？稍O(shè)n≤30。此題所用的循環(huán)鏈表中不需要“頭結(jié)點(diǎn)”，因此在程序設(shè)計(jì)中應(yīng)注意空表和非空表的界限。2、 演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令：相應(yīng)的輸入數(shù)據(jù)和運(yùn)算結(jié)果顯示在其后。3、 程序執(zhí)行的命令包括：1） 構(gòu)造約瑟夫環(huán)；2）執(zhí)行約瑟夫環(huán)，并輸出出列人的序號以及相應(yīng)的密碼；3）結(jié)束。4、測試數(shù)據(jù) 1）m的初始值為20；2）n=7，7個人的密碼依次為：3、1、7、2、4、8、4。3）首先m值為6，正確的出列順序應(yīng)為6、1、4、7、2、3、5。1.2設(shè)計(jì)平臺Windows2000以上操作系統(tǒng)；MicrosoftVisualC++6.02概要設(shè)計(jì)已知n個人（以編號1，2，3...n分別表示）圍成一圈。從編號為1的人開始報(bào)數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報(bào)數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復(fù)下去，直到一圈的人全部出列。這個就是約瑟夫環(huán)問題的實(shí)際場景，有一種是要通過輸入n,m,k三個正整數(shù)，來求出列的序列。這個問題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個鏈表的尾元素指針指向隊(duì)首元素。p->link=head。解決問題的核心步驟：首先建立一個具有n個鏈結(jié)點(diǎn)，無頭結(jié)點(diǎn)的循環(huán)鏈表。然后確定第1個報(bào)數(shù)人的位置。最后不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表為空。改進(jìn)的約瑟夫環(huán)問題與原問題思路一致，只是不再采用單循環(huán)鏈表存儲結(jié)構(gòu)，而采用雙向循環(huán)鏈表，而且用一個判斷語句來決定報(bào)數(shù)的方向的順時針還是逆時針。本課程設(shè)計(jì)主要采用了類的數(shù)據(jù)結(jié)構(gòu)，程序中包含了兩個類：Linklist,Joseph。為實(shí)現(xiàn)上述程序功能，應(yīng)以單向循環(huán)鏈表表示約瑟夫環(huán)。為此，需要兩個抽象數(shù)據(jù)類型：單向循環(huán)鏈表和約瑟夫環(huán)。1）、單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：ADTList{數(shù)據(jù)對象：D={ai｜ai∈Elemset,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={＜a(i-1),ai＞｜a(i-1),ai∈D,i=2,…n}基本操作：InitList(&L)操作結(jié)果：構(gòu)造一個空的鏈表L。DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。ListLength(L)初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。GetElem(L,i,&e)初始條件：線性表L已存在，1≤i≤ListLength(L)。操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。ListInsert(&L,I,e)初始條件：線性表L已存在，1≤i≤ListLength(L)+1。操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1。ListDelete(&L,i,&e)初始條件：線性表L已存在且非空，1≤i≤ListLength(L)。操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。ListTraverse(L,visit())初始條件：線性表L已存在。操作結(jié)果：依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。}ADTList2)約瑟夫環(huán)的抽象數(shù)據(jù)類型定義為：ADTSet{數(shù)據(jù)對象：D={ai｜ai為用戶輸入的數(shù)字密碼，i=1,2,…,n,1≤n≤7}數(shù)據(jù)關(guān)系：{}基本操作：CreatSet(&L，s)初始條件：L為單向循環(huán)鏈表。操作結(jié)果：對鏈表中的數(shù)據(jù)域進(jìn)行賦值。DeleteSet(&L,i,&e)初始條件：線性表L已存在且非空，1≤i≤ListLength(L)。操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。PrintSet(L)初始條件：鏈表L已存在。操作結(jié)果：按輸出次序顯示每個人的密碼。}ADTSet3)本程序包含四個模塊：1、主程序模塊：Voidmain(){初始化；Do{接受命令；處理命令；}while(“命令”=”退出”)；}2、約瑟夫環(huán)單元模塊——實(shí)現(xiàn)約瑟夫環(huán)的抽象數(shù)據(jù)類型；3、單向循環(huán)鏈表單元模塊——實(shí)現(xiàn)單向循環(huán)鏈表的抽象數(shù)據(jù)類型；4、結(jié)點(diǎn)結(jié)構(gòu)單元模塊——定義單向循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)。各模塊之間的調(diào)用關(guān)系如下：結(jié)點(diǎn)結(jié)構(gòu)單元模塊↓單向循環(huán)鏈表單元模塊↓約瑟夫環(huán)單元模塊↓主程序模塊2.1類LinkList主要功能是創(chuàng)建結(jié)點(diǎn)，每個結(jié)點(diǎn)數(shù)值域包括data,password,還有指示前驅(qū)結(jié)點(diǎn)的指針llink,和指示后繼結(jié)點(diǎn)的指針rlink。2.2類Joseph主要功能是實(shí)現(xiàn)創(chuàng)建雙向循環(huán)鏈表及一些相應(yīng)的操作。2.3類異常處理在C++程序中，可以使用try-throw-catch結(jié)構(gòu)處理程序異常。采用這一程序結(jié)構(gòu)能夠?qū)⑹褂煤蛯?shí)現(xiàn)分離：類和函數(shù)的實(shí)現(xiàn)者使用throw語句易地錯誤類別通知使用者。使用者根據(jù)獲悉的錯誤類別采取相應(yīng)的措施，這就是異常處理。3詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)改進(jìn)約瑟夫環(huán)問題的基本思路和原問題基本一致，只是一個采用單循環(huán)鏈表，另一個采用雙向循環(huán)鏈表來解決問題。第一步是定義結(jié)構(gòu)變量結(jié)點(diǎn)linklist，并在該結(jié)點(diǎn)下定義結(jié)點(diǎn)的元素域:data,password，指針域:lLink和rLink。然后建立一個由n個鏈結(jié)點(diǎn)，無表頭結(jié)點(diǎn)的雙向循環(huán)鏈表。并由構(gòu)造函數(shù)對結(jié)點(diǎn)賦值，由隨機(jī)函數(shù)rand()產(chǎn)生每個結(jié)點(diǎn)的password。由于每個結(jié)點(diǎn)的password是由隨機(jī)函數(shù)產(chǎn)生的，也就是每個結(jié)點(diǎn)的password是后知的，所以在一開始人為地指定一個結(jié)點(diǎn)的順序，由此結(jié)點(diǎn)開始報(bào)數(shù)。報(bào)password個數(shù)后，報(bào)到的那個結(jié)點(diǎn)被刪除，它的password被記錄下，由它的下一個結(jié)點(diǎn)開始逆方向報(bào)數(shù)………如此循環(huán)，直到循環(huán)鏈表里只剩下一個結(jié)點(diǎn)，那就是問題所求的結(jié)果。具體到問題上，還需要創(chuàng)建一個Joseph類，由構(gòu)造函數(shù)來初始化，輸入所有的人數(shù)，也就是表長，然后指定由第幾個人開始報(bào)數(shù)。在Joseph類中定義一個GetWinner()函數(shù)，由它來實(shí)現(xiàn)獲得最后的勝利者。并在該類中設(shè)置一個判斷語句來確定先由順時針報(bào)數(shù)并淘汰了一個人之后，再按逆時針順序報(bào)數(shù)，如此交替進(jìn)行。主要功能實(shí)現(xiàn)的程序流程圖及核心代碼。算法流程圖：開始開始輸入開始的報(bào)數(shù)上限turn循環(huán)次數(shù)i為1否結(jié)束指針p指向鏈表頭結(jié)點(diǎn)i是否小于等于人數(shù)-1j是否小于等于turn-1報(bào)數(shù)j從1開始是指針后移否報(bào)數(shù)+1報(bào)數(shù)上限變成p的下一個結(jié)點(diǎn)的密碼，并刪除p的下一個結(jié)點(diǎn)循環(huán)次數(shù)i加1輸出p的下一個結(jié)點(diǎn)的值輸出p的下一個結(jié)點(diǎn)的值是3.1創(chuàng)建結(jié)點(diǎn)Node鏈表都是由一個個結(jié)點(diǎn)組成，由于結(jié)點(diǎn)的不同，組成的鏈表也不同。因此需要創(chuàng)建雙向鏈表結(jié)點(diǎn)。由于每一個結(jié)點(diǎn)有一個密碼和一個序號，所以可以將結(jié)點(diǎn)結(jié)構(gòu)體定義為：datallinkpasswordrLinkstructNode{datallinkpasswordrLinkintdata;intpassword;DNode*llink;DNode*rlink;}圖3.1結(jié)點(diǎn)Dnode3.2創(chuàng)建雙向循環(huán)鏈表創(chuàng)建一個空雙向循環(huán)鏈表，雙向循環(huán)鏈表和每個結(jié)點(diǎn)包括三個域:Element，lLink,rLink.其中element為元素域，rLink域?yàn)橹赶蚝罄^結(jié)點(diǎn)的指針，新增的lLink域用以指向前驅(qū)結(jié)點(diǎn)。雙向鏈表也可以帶表頭結(jié)點(diǎn)，并且也可以構(gòu)成雙向循環(huán)鏈表。此時，表頭結(jié)點(diǎn)的rLink，lLink分別指向雙向循環(huán)鏈表的頭結(jié)點(diǎn)(或表頭結(jié)點(diǎn))和尾結(jié)點(diǎn)。一個結(jié)點(diǎn)的lLink域的指針指向它左邊結(jié)點(diǎn)的后部，這并不意味著該結(jié)點(diǎn)的lLink域保存的仍是該左邊結(jié)點(diǎn)存儲塊的起始地址。在此處，指針指向某個結(jié)點(diǎn)任何部分都是等價的，都是指該存儲塊的起始位置。firstfirst………圖3.2單表頭的雙向循環(huán)鏈表每當(dāng)結(jié)點(diǎn)計(jì)數(shù)到某一結(jié)點(diǎn)時，將他的前驅(qū)結(jié)點(diǎn)接到他的后繼結(jié)點(diǎn)，然后將他的密碼值password賦給計(jì)數(shù)變量，再將此結(jié)點(diǎn)刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。由于當(dāng)某個人退出圓圈后，報(bào)數(shù)的工作要從下一個人開始繼續(xù)，剩下的人仍然是圍成一個圓圈的，可以使用循環(huán)表，由于退出圓圈的工作對應(yīng)著表中結(jié)點(diǎn)的刪除操作，對于這種刪除操作頻繁的情況，選用效率較高的鏈表結(jié)構(gòu)，為了程序指針每一次都指向一個具體的代表一個人的結(jié)點(diǎn)而不需要判斷，鏈表不帶頭結(jié)點(diǎn)。所以，對于所有人圍成的圓圈所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)采用一個不帶頭結(jié)點(diǎn)的循環(huán)鏈表來描述。設(shè)頭指針為front，front始終指向頭結(jié)點(diǎn)，并定義指針current記錄當(dāng)前的結(jié)點(diǎn)。并根據(jù)具體情況移動（順逆時針）。為了記錄退出的人的先后順序，采用一個順序表進(jìn)行存儲。程序結(jié)束后再輸出依次退出的人的編號順序。由于只記錄各個結(jié)點(diǎn)的data值就可以。最后通過函數(shù)調(diào)用來輸出順序。要解決約瑟夫環(huán)問題，首先一點(diǎn)就是必須有一個環(huán)，所以第一步我們必須建立一個雙向循環(huán)鏈表。而建立一個雙向循環(huán)鏈表必須有一個空的雙向循環(huán)鏈表，然后運(yùn)用尾插法建立一個雙向循環(huán)鏈表，這樣約瑟夫環(huán)就創(chuàng)建出來了，接下來就是處理約瑟夫環(huán)問題。3.3從鏈表中刪除結(jié)點(diǎn)在雙向循環(huán)鏈表中，一個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)地址保存在該結(jié)點(diǎn)的lLink域中，這樣可以方便地實(shí)現(xiàn)在一個指定結(jié)點(diǎn)之前插入一個新結(jié)點(diǎn)的操作，也可以方便地刪除某個指定結(jié)點(diǎn)。函數(shù)通過代碼：q->llink->rlink=q->rlink;q->rlink->llink=q->llink;deleteq;來刪除當(dāng)前的那個結(jié)點(diǎn)q，通過循環(huán)來一次次刪除當(dāng)前的結(jié)點(diǎn)，直到鏈表中剩下最后一個結(jié)點(diǎn)。具體程序如下：#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedefstructnode//定義單循環(huán)鏈表中節(jié)點(diǎn)的結(jié)構(gòu){ intnum;//序列號即個人的編號 intcipher;//個人所持有的密碼 structnode*next;}linklist;classYSFH{public: linklist*Creat(intn); linklist*Select1(intm); linklist*head;//頭指針指示有n個結(jié)點(diǎn)的單循環(huán)鏈表creatprotected:linklist*Select(linklist*head,intm);private: linklist*p;//存放人員信息 linklist*r;//臨時存放linklist*q; intk;};/*建立單循環(huán)鏈表函數(shù)*/linklist*YSFH::Creat(intn){ linklist*head; linklist*p; p=(linklist*)malloc(sizeof(linklist)); head=p; p->num=1; printf("隨機(jī)產(chǎn)生第1個人的密碼:"); p->cipher=rand()%10; { if(p->cipher==0) p->cipher=rand()%10; }printf("%d\n",p->cipher); r=p; p->next=p; for(intk=2;k<=n;k++) { p=(linklist*)malloc(sizeof(linklist)); p->num=k;//給每人一個編號 printf("隨機(jī)產(chǎn)生第%d個人的密碼:",k);p->cipher=rand()%10; { if(p->cipher==0) p->cipher=rand()%10; } printf("%d\n",p->cipher); r->next=p; r=p; } p->next=head; return(head);}/*決定出列編號*/linklist*YSFH::Select1(intm){ returnSelect(head,m);}linklist*YSFH::Select(linklist*head,intm){ q=head; k=1; p=q->next;//q為p的前驅(qū)指針,p指向當(dāng)前報(bào)數(shù)的人 printf("出列的序號依次為:"); //在head中的第一個結(jié)點(diǎn)起循環(huán)記數(shù)找第m個結(jié)點(diǎn) while(q!=p) { k=k+1;//報(bào)一次數(shù) if(k%m==0)//所報(bào)數(shù)等于報(bào)數(shù)上限值時 { printf("%d",p->num);//輸出該結(jié)點(diǎn)的num值 m=p->cipher;//把該結(jié)點(diǎn)的cipher(密碼)值賦給m q->next=p->next;//對應(yīng)的節(jié)點(diǎn)從鏈表中刪除 free(p); k=0; p=q->next; } else{ q=p; p=p->next;//p指向當(dāng)前報(bào)數(shù)的人 } } head=p; return(head);}voidmain(){ intn,m; m!=0;YSFHY; printf("輸入總?cè)藬?shù)n:"); scanf("%d",&n); Y.head=Y.Creat(n); printf("隨機(jī)產(chǎn)生第一次的報(bào)數(shù)上限值m:"); m=rand()%10; { if(m==0) m=rand()%10; } printf("%d\n",m); Y.head=Y.Select1(m); print