計算機科學與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設計報告

1、鄭州師范學院計算機科學與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu) 課程設計報告設計題目： 約瑟夫環(huán) 班 級： b15軟件工程（）組 長： 組 員： 指導教師： 完成日期： 2016-1-7 成績： 目 錄1需求分析31.1功能分析31.2設計平臺32概要設計32.1類linklist32.2類joseph42.3類異常處理43詳細設計和實現(xiàn)43.1創(chuàng)建結(jié)點node43.2創(chuàng)建雙向循環(huán)鏈表53.3從鏈表中刪除結(jié)點64調(diào)試與操作說明104.1調(diào)試情況104.2操作說明105設計總結(jié)11參 考 文 獻12附錄121需求分析1.1功能分析本次選做的課程設計是改進約瑟夫(joseph)環(huán)問題。約瑟夫環(huán)問題是一個古老的數(shù)學問題

2、，本次課題要求用程序語言的方式解決數(shù)學問題。此問題僅使用單循環(huán)鏈表就可以解決此問題。而改進的約瑟夫問題通過運用雙向循環(huán)鏈表，同樣也能方便地解決。在建立雙向循環(huán)鏈表時，因為約瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個結(jié)點的數(shù)據(jù)域的值定為生成結(jié)點時的順序號和每個人持有的密碼。進行操作時，用一個指針current指向當前的結(jié)點，指針front始終指向頭結(jié)點。然后建立雙向循環(huán)鏈表，因為每個人的密碼是通過rand()函數(shù)隨機生成的，所以指定第一個人的順序號，找到結(jié)點，不斷地從鏈表中刪除鏈結(jié)點，直到鏈表剩下最后一個結(jié)點，通過一系列的循環(huán)就可以解決改進約瑟夫環(huán)問題。1、本演示程序中，利用單向循環(huán)鏈表存儲

3、結(jié)構(gòu)模擬約瑟夫問題的進行。程序運行后，首先要求用戶指定初始報數(shù)上限值，然后讀取個人的密碼。可設n30。此題所用的循環(huán)鏈表中不需要“頭結(jié)點”，因此在程序設計中應注意空表和非空表的界限。2、演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令：相應的輸入數(shù)據(jù)和運算結(jié)果顯示在其后。3、程序執(zhí)行的命令包括：1）構(gòu)造約瑟夫環(huán)；2）執(zhí)行約瑟夫環(huán)，并輸出出列人的序號以及相應的密碼；3）結(jié)束。4、測試數(shù)據(jù) 1）m的初始值為20； 2）n=7，7個人的密碼依次為：3、1、7、2、4、8、4。 3）首先m值為6，正確的出列順序應為6、1、4、7、2

4、、3、5。1.2設計平臺windows2000以上操作系統(tǒng)；microsoft visual c+ 6.02概要設計已知n個人（以編號1，2，3.n分別表示）圍成一圈。從編號為1的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復下去，直到一圈的人全部出列。這個就是約瑟夫環(huán)問題的實際場景，有一種是要通過輸入n,m,k三個正整數(shù)，來求出列的序列。這個問題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個鏈表的尾元素指針指向隊首元素。 p-link=head。解決問題的核心步驟：首先建立一個具有n個鏈結(jié)點，無頭結(jié)點的循環(huán)鏈表。然后確定第1個報數(shù)人的位置。最后不

5、斷地從鏈表中刪除鏈結(jié)點，直到鏈表為空。改進的約瑟夫環(huán)問題與原問題思路一致，只是不再采用單循環(huán)鏈表存儲結(jié)構(gòu)，而采用雙向循環(huán)鏈表，而且用一個判斷語句來決定報數(shù)的方向的順時針還是逆時針。本課程設計主要采用了類的數(shù)據(jù)結(jié)構(gòu)，程序中包含了兩個類：linklist , joseph。為實現(xiàn)上述程序功能，應以單向循環(huán)鏈表表示約瑟夫環(huán)。為此，需要兩個抽象數(shù)據(jù)類型：單向循環(huán)鏈表和約瑟夫環(huán)。1）、單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：adt list數(shù)據(jù)對象：d=aiaielemset,i=1,2,n,n0數(shù)據(jù)關(guān)系：r1=a(i-1),aia(i-1),aid,i=2,n基本操作： initlist(&l) 操作結(jié)果：

6、構(gòu)造一個空的鏈表l。 destroylist(&l) 初始條件：線性表l已存在。 操作結(jié)果：銷毀線性表l。 listlength(l) 初始條件：線性表l已存在。 操作結(jié)果：返回l中數(shù)據(jù)元素個數(shù)。 getelem(l,i,&e) 初始條件：線性表l已存在，1ilistlength(l)。 操作結(jié)果：用e返回l中第i個數(shù)據(jù)元素的值。 listinsert(&l,i,e) 初始條件：線性表l已存在，1ilistlength(l)+1。 操作結(jié)果：在l中第i個位置之前插入新的數(shù)據(jù)元素e，l的長度加1。 listdelete(&l,i,&e) 初始條件：線性表l已存在且非空，1ilistlength(

7、l)。 操作結(jié)果：刪除l的第i個數(shù)據(jù)元素，并用e返回其值，l的長度減1。 listtraverse(l,visit() 初始條件：線性表l已存在。 操作結(jié)果：依次對l的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。 adt list2)約瑟夫環(huán)的抽象數(shù)據(jù)類型定義為：adt set 數(shù)據(jù)對象：d=aiai為用戶輸入的數(shù)字密碼，i=1,2,n,1n7 數(shù)據(jù)關(guān)系： 基本操作： creatset(&l，s) 初始條件：l為單向循環(huán)鏈表。 操作結(jié)果：對鏈表中的數(shù)據(jù)域進行賦值。 deleteset(&l,i,&e) 初始條件：線性表l已存在且非空，1ilistlength(l)。

8、 操作結(jié)果：刪除l的第i個數(shù)據(jù)元素，并用e返回其值，l的長度減1。 printset(l) 初始條件：鏈表l已存在。 操作結(jié)果：按輸出次序顯示每個人的密碼。 adt set3)本程序包含四個模塊： 1、主程序模塊： void main() 初始化； do接受命令；處理命令； while (“命令”=”退出”)； 2、約瑟夫環(huán)單元模塊實現(xiàn)約瑟夫環(huán)的抽象數(shù)據(jù)類型； 3、單向循環(huán)鏈表單元模塊實現(xiàn)單向循環(huán)鏈表的抽象數(shù)據(jù)類型； 4、結(jié)點結(jié)構(gòu)單元模塊定義單向循環(huán)鏈表的結(jié)點結(jié)構(gòu)。 各模塊之間的調(diào)用關(guān)系如下： 結(jié)點結(jié)構(gòu)單元模塊 單向循環(huán)鏈表單元模塊 約瑟夫環(huán)單元模塊 主程序模塊2.1類linklist主要功能

9、是創(chuàng)建結(jié)點，每個結(jié)點數(shù)值域包括data,password,還有指示前驅(qū)結(jié)點的指針llink,和指示后繼結(jié)點的指針rlink。2.2類joseph主要功能是實現(xiàn)創(chuàng)建雙向循環(huán)鏈表及一些相應的操作。2.3類異常處理在c+程序中，可以使用try-throw-catch結(jié)構(gòu)處理程序異常。采用這一程序結(jié)構(gòu)能夠?qū)⑹褂煤蛯崿F(xiàn)分離：類和函數(shù)的實現(xiàn)者使用throw語句易地錯誤類別通知使用者。使用者根據(jù)獲悉的錯誤類別采取相應的措施，這就是異常處理。3詳細設計和實現(xiàn)改進約瑟夫環(huán)問題的基本思路和原問題基本一致，只是一個采用單循環(huán)鏈表，另一個采用雙向循環(huán)鏈表來解決問題。第一步是定義結(jié)構(gòu)變量結(jié)點linklist，并在該結(jié)點

10、下定義結(jié)點的元素域:data,password，指針域:llink和rlink。然后建立一個由n個鏈結(jié)點，無表頭結(jié)點的雙向循環(huán)鏈表。并由構(gòu)造函數(shù)對結(jié)點賦值，由隨機函數(shù)rand()產(chǎn)生每個結(jié)點的password。由于每個結(jié)點的password是由隨機函數(shù)產(chǎn)生的，也就是每個結(jié)點的password是后知的，所以在一開始人為地指定一個結(jié)點的順序，由此結(jié)點開始報數(shù)。報password個數(shù)后，報到的那個結(jié)點被刪除，它的password被記錄下，由它的下一個結(jié)點開始逆方向報數(shù)如此循環(huán)，直到循環(huán)鏈表里只剩下一個結(jié)點，那就是問題所求的結(jié)果。具體到問題上，還需要創(chuàng)建一個joseph類，由構(gòu)造函數(shù)來初始化，輸入所有

11、的人數(shù)，也就是表長，然后指定由第幾個人開始報數(shù)。在joseph類中定義一個getwinner()函數(shù)，由它來實現(xiàn)獲得最后的勝利者。并在該類中設置一個判斷語句來確定先由順時針報數(shù)并淘汰了一個人之后，再按逆時針順序報數(shù)，如此交替進行。主要功能實現(xiàn)的程序流程圖及核心代碼算法流程圖：開始輸入開始的報數(shù)上限turn循環(huán)次數(shù)i為1否結(jié)束指針p指向鏈表頭結(jié)點i是否小于等于人數(shù)-1j是否小于等于turn-1報數(shù)j從1開始是指針后移否報數(shù)+1報數(shù)上限變成p的下一個結(jié)點的密碼，并刪除p的下一個結(jié)點循環(huán)次數(shù)i加1輸出p的下一個結(jié)點的值輸出p的下一個結(jié)點的值是3.1創(chuàng)建結(jié)點node鏈表都是由一個個結(jié)點組成，由于結(jié)點的

12、不同，組成的鏈表也不同。因此需要創(chuàng)建雙向鏈表結(jié)點。由于每一個結(jié)點有一個密碼和一個序號，所以可以將結(jié)點結(jié)構(gòu)體定義為：datallinkpasswordrlinkstruct node int data;int password;dnode* llink;dnode* rlink; 圖3.1 結(jié)點dnode3.2創(chuàng)建雙向循環(huán)鏈表創(chuàng)建一個空雙向循環(huán)鏈表，雙向循環(huán)鏈表和每個結(jié)點包括三個域:element，llink,rlink.其中element為元素域，rlink域為指向后繼結(jié)點的指針，新增的llink域用以指向前驅(qū)結(jié)點。雙向鏈表也可以帶表頭結(jié)點，并且也可以構(gòu)成雙向循環(huán)鏈表。此時，表頭結(jié)點的rlin

13、k，llink分別指向雙向循環(huán)鏈表的頭結(jié)點(或表頭結(jié)點)和尾結(jié)點。一個結(jié)點的llink域的指針指向它左邊結(jié)點的后部，這并不意味著該結(jié)點的llink域保存的仍是該左邊結(jié)點存儲塊的起始地址。在此處，指針指向某個結(jié)點任何部分都是等價的，都是指該存儲塊的起始位置。first 圖3.2 單表頭的雙向循環(huán)鏈表每當結(jié)點計數(shù)到某一結(jié)點時，將他的前驅(qū)結(jié)點接到他的后繼結(jié)點，然后將他的密碼值password賦給計數(shù)變量，再將此結(jié)點刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。由于當某個人退出圓圈后，報數(shù)的工作要從下一個人開始繼續(xù)，剩下的人仍然是圍成一個圓圈的，可以使用循環(huán)表，由于退出圓圈的工作對應著表中結(jié)點的

14、刪除操作，對于這種刪除操作頻繁的情況，選用效率較高的鏈表結(jié)構(gòu)，為了程序指針每一次都指向一個具體的代表一個人的結(jié)點而不需要判斷，鏈表不帶頭結(jié)點。所以，對于所有人圍成的圓圈所對應的數(shù)據(jù)結(jié)構(gòu)采用一個不帶頭結(jié)點的循環(huán)鏈表來描述。設頭指針為front，front始終指向頭結(jié)點，并定義指針current記錄當前的結(jié)點。并根據(jù)具體情況移動（順逆時針）。為了記錄退出的人的先后順序，采用一個順序表進行存儲。程序結(jié)束后再輸出依次退出的人的編號順序。由于只記錄各個結(jié)點的data值就可以。最后通過函數(shù)調(diào)用來輸出順序。要解決約瑟夫環(huán)問題，首先一點就是必須有一個環(huán)，所以第一步我們必須建立一個雙向循環(huán)鏈表。而建立一個雙向循

15、環(huán)鏈表必須有一個空的雙向循環(huán)鏈表，然后運用尾插法建立一個雙向循環(huán)鏈表，這樣約瑟夫環(huán)就創(chuàng)建出來了，接下來就是處理約瑟夫環(huán)問題。3.3從鏈表中刪除結(jié)點在雙向循環(huán)鏈表中，一個結(jié)點的前驅(qū)結(jié)點地址保存在該結(jié)點的llink域中，這樣可以方便地實現(xiàn)在一個指定結(jié)點之前插入一個新結(jié)點的操作，也可以方便地刪除某個指定結(jié)點。函數(shù)通過代碼：q-llink-rlink=q-rlink;q-rlink-llink=q-llink;delete q;來刪除當前的那個結(jié)點q，通過循環(huán)來一次次刪除當前的結(jié)點，直到鏈表中剩下最后一個結(jié)點。具體程序如下：#include#include#includetypedef struct

16、node /定義單循環(huán)鏈表中節(jié)點的結(jié)構(gòu)int num;/序列號即個人的編號int cipher;/個人所持有的密碼struct node *next;linklist;class ysfhpublic:linklist *creat(int n);linklist *select1(int m);linklist *head;/頭指針指示有n個結(jié)點的單循環(huán)鏈表creatprotected: linklist *select(linklist *head,int m);private:linklist *p;/存放人員信息linklist *r;/臨時存放 linklist *q;int k;/

17、*建立單循環(huán)鏈表函數(shù)*/linklist *ysfh:creat(int n)linklist *head;linklist *p;p=(linklist *)malloc(sizeof(linklist);head=p;p-num=1;printf(隨機產(chǎn)生第1個人的密碼: );p-cipher=rand()%10;if(p-cipher=0)p-cipher=rand()%10; printf(%dn,p-cipher);r=p;p-next=p;for(int k=2;knum=k;/給每人一個編號printf(隨機產(chǎn)生第%d個人的密碼: ,k); p-cipher=rand()%10;

18、if(p-cipher=0)p-cipher=rand()%10;printf(%dn,p-cipher);r-next=p;r=p;p-next=head;return(head);/*決定出列編號*/linklist *ysfh:select1(int m)return select(head,m);linklist *ysfh:select(linklist *head,int m)q=head;k=1;p=q-next;/q為p的前驅(qū)指針,p指向當前報數(shù)的人printf(出列的序號依次為:);/在head中的第一個結(jié)點起循環(huán)記數(shù)找第m個結(jié)點while(q!=p)k=k+1;/報一次數(shù)

19、if(k%m=0)/所報數(shù)等于報數(shù)上限值時printf(%d ,p-num);/輸出該結(jié)點的num值m=p-cipher;/把該結(jié)點的cipher(密碼)值賦給mq-next=p-next;/對應的節(jié)點從鏈表中刪除free(p);k=0;p=q-next;elseq=p;p=p-next;/p指向當前報數(shù)的人head=p;return(head);void main()int n,m;m!=0; ysfh y;printf(輸入總?cè)藬?shù)n: );scanf(%d,&n);y.head=y.creat(n);printf(隨機產(chǎn)生第一次的報數(shù)上限值m: );m=rand()%10;if(m=0)m

20、=rand()%10;printf(%dn,m);y.head=y.select1(m);printf(%dn,y.head-num);4調(diào)試與操作說明4.1調(diào)試情況這次的課程設計的代碼很冗長，所以等有了解題思路后，把代碼都寫上后難免會有很多錯誤。當?shù)谝淮伟颜麄€程序?qū)懞煤筮\行，出現(xiàn)了很多錯誤。不過經(jīng)過一點點的改正，錯誤也慢慢地變少。這也說明做事要認真，尤其做計算機這方面工作的時候，因為計算機不容許不一點點的錯誤，有了一點小錯誤和有一個大錯誤在計算機看來都是一樣的，都不會得不到結(jié)果。有些小錯誤，比如說少了個分號，變量忘了定義，數(shù)據(jù)溢出等都是些小錯誤，但也不能松懈。因為要注意的地方很多，經(jīng)過多次嘗

21、試，問題也就自然而然的解決了，而且以后遇到這方面的問題都會覺得比較得心應手。在隨機設置每個結(jié)點的password時也曾是個問題，因為我做的隨機函數(shù)一直都用不好，要不是每次隨到的都是一樣的，要么就是每次隨到的數(shù)都很大，后來通過老師的耐心講解才得以解決。在調(diào)試的過程中，類的優(yōu)勢很明顯，能很簡單的把問題解決，而不需要使用的其他的一些比較復雜的方法。4.2操作說明生成界面如圖4.1，4.2所示：圖4.1 生成界面圖4.2生成界面當程序運行的時候會出現(xiàn)如上圖所示的提示，要求使用者輸入程序中所需的輸入總?cè)藬?shù)，使用者只需輸入自己所想的總?cè)藬?shù)，系統(tǒng)便會隨機產(chǎn)生每個人對應的密碼，同時隨機產(chǎn)生第一次的報數(shù)上限值。

22、最后系統(tǒng)會給出出列的次序，最后產(chǎn)生的編號便是此次游戲的獲勝者。使用者還可按下任意鍵，進行下一次的游戲。5設計總結(jié)通過這次數(shù)據(jù)結(jié)構(gòu)課程設計，我感受最深的就是對于循環(huán)鏈表的使用，可以說對循環(huán)鏈表有了比以前更進一步的認識，以前只是一知半解的，如果只給個題目自己根本不能把程序完整地編寫出來，所以這次課程設計最大的收獲就在于對循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個循環(huán)鏈表，刪除鏈表中的一結(jié)點，增加一個結(jié)點等。 在這次課程設計過程中需要我們一邊設計一邊探索，這這個過程當中我發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)方面知識掌握不夠深入，對一些基本概念不能很好的理解，對一些數(shù)據(jù)結(jié)構(gòu)不能夠熟練的進行上機實現(xiàn)，這是自

23、己比較薄弱。學好基礎知識是理論付諸實踐的前提，這樣理論和實踐才能充分地結(jié)合起來。在以后的學習中，我還要努力改正，充分利用上機實驗的機會提高自己。在程序的輸入的時候，因為自己對鍵盤的不熟練，代碼又很多很繁瑣，常常會產(chǎn)生放棄的念頭，從中我也感受到只有堅持到底，勝利才會出現(xiàn)。在調(diào)試程序的時候我也有所體會，雖然約瑟夫環(huán)問題不是很難，但調(diào)試的時候還是會出現(xiàn)很多錯誤，因此我們不能認為容易就不認真對待。在以后的學習中，要能不斷發(fā)現(xiàn)問題，提出問題，解決問題，從不足之處出發(fā)，在不斷學習中提高自己。參 考 文 獻1張乃孝,裘宗燕.數(shù)據(jù)結(jié)構(gòu)c+與面向?qū)ο蟮耐緩?北京：高等教育出版社，19982 周云靜數(shù)據(jù)結(jié)構(gòu)習題解

24、析與上機指導北京：冶金工業(yè)出版社，20043 陳慧南數(shù)據(jù)結(jié)構(gòu)c+語言描述北京：人民郵電出版社，20054 嚴蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)北京：清華大學出版社，19975 adam drozdek數(shù)據(jù)結(jié)構(gòu)與算法北京：清華大學出版社，20066 徐孝凱數(shù)據(jù)結(jié)構(gòu)實驗北京：中央廣播電視大學出版社，2001附錄源程序附下：#include #include #include#include #include#define null 0typedef struct node int m;/密碼int n;/序號struct node *next;node,*linklist;linklist create(int

25、 z) /生成循環(huán)單鏈表并返回,z為總?cè)藬?shù) int i,mm;linklist h,r,s;h=null;printf(請按順序依次為每個人添加密碼：);for(i=1;in=i;s-m=mm;printf(%d號的密碼%d,i,s-m);if(h=null)/從鏈表的第一個節(jié)點插入 h=s;r=h;else/鏈表的其余節(jié)點插入 r-next=s;r=s;/r后移/for結(jié)束r-next=h;/*生成循環(huán)單鏈表*/return h;void search(linklist h,int m0,int z)/用循環(huán)鏈表實現(xiàn)報數(shù)問題 int count=1;/count為累計報數(shù)人數(shù)計數(shù)器int n

26、um=0;/num為標記出列人數(shù)計數(shù)器linklistpre,p; p=h;printf(出列的順序為:);while(numnext;while(countnext=p-next;printf(%d ,p-n);m0=p-m;free(p);p=pre-next;count=1;num+;/while結(jié)束void clean()int system(const char *string);int inquiry;printf(請問需要清除上一次操作記錄嗎（1.清屏/2.不清屏）.?n);scanf(%d,&inquiry);if(inquiry =1)system(cls);void text()int m0,z,i, choose,k=1; /k用來阻止第一次進入程序清屏操作linklist h; boolchooseflag=false;while(1)if(k!=1)clean();k+;while(!chooseflag)printf( 歡迎進入約瑟夫環(huán)問題系統(tǒng)n);printf( * 1.輸入約瑟夫環(huán)數(shù)據(jù) * n);printf( * 2.什么是約瑟夫環(huán) * n);printf( * 3.退出系統(tǒng) * n