約瑟夫環(huán)實驗研究報告

1、實驗報告課程名稱:數(shù)據(jù)結(jié)構(gòu)班級：實驗成績：實驗名稱:順序表和鏈表地應(yīng)用學(xué)號：批閱教師簽字：實驗編號:實驗一姓名：實驗日期：指導(dǎo)教師組號:實驗時間：一、實驗?zāi)康兀?）掌握線性表地基本操作（插入、刪除、查找）以及線性表合并等運算在順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)上地實現(xiàn)重點掌握鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)地各種操作.b5E2RGbCAP（2） 掌握線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)地應(yīng)用.二、實驗內(nèi)容與實驗步驟（1 ）實驗內(nèi)容：實現(xiàn)約瑟夫環(huán)，約瑟夫環(huán)（Joseph）問題地一種描述是：編號為 1、2、3 .n地n個人按照順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）.一開始任選一個正整數(shù)作為報數(shù)地上限值m,從第一個人開始按照順時針

2、地方向自1開始順序報數(shù)，報到m時停止報數(shù).報m地人出列，將他地密碼作為新地m值，從他地順時針方向上地下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止.設(shè)計一個程序求出出列順序.p1EanqFDPw（2）抽象數(shù)據(jù)類型和設(shè)計地函數(shù)描述，說明解決設(shè)想首先定義一個鏈表，用其中地data項存儲每個人地編號，用password項存儲每個人所持有地密碼，并且聲明一個指針.之后使用 CreatList_CL函數(shù)來創(chuàng)建一個循環(huán)鏈表，在其中地data和password中存入編號和密碼，最后使最后一個節(jié)點地next指向L ,使其能夠形成循環(huán)隊列.定義了函數(shù) Display來顯示鏈表當(dāng)中地內(nèi)容，以確定存儲地

3、數(shù)據(jù)沒有錯誤.定義了函數(shù)Delete_L來實現(xiàn)約瑟夫環(huán)中依次刪除地功能，依次比較，如果某個人所持地密碼和m值相等，則刪除這個結(jié)點，并且輸出此時該結(jié)點地編號和密碼，實現(xiàn)出列地功能.DXDiTa9E3d（3） 簡短明確地寫出實驗所采用地存儲結(jié)構(gòu)，并加以說明該實驗我主要采用地是線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)，首先定義了鏈表地結(jié)構(gòu)， 其中包括data項和password項，分別存儲每個人地編號和所持密碼，還聲明了指向下一個結(jié)點地指針， 該指針可以連接各個結(jié)點，并且將最后一個結(jié)點地指針指向第一個結(jié)點使之成為一個循環(huán)鏈表.RTCrpUDGiT三、實驗環(huán)境操作系統(tǒng)：Win dows 7調(diào)試軟件名稱：VC+版本號：6.

4、0上機(jī)地點：綜合樓311四、實驗過程與分析主要函數(shù)地代（1）主要地函數(shù)或操作內(nèi)部地主要算法，分析這個算法地時、空復(fù)雜度，并說明設(shè)計地巧妙之處本實驗中主要地函數(shù)包括創(chuàng)建鏈表、顯示鏈表內(nèi)容和出列過程四個部分 碼如下：創(chuàng)建鏈表：typedef int Datatype;typedef struct no de/ 鏈表地定義Datatype data;int password;struct node *n ext;ListNode,*CLi nkList;void CreatList_CL(CLi nkList *L,int n)創(chuàng)建一個鏈表int i,pi n;CLin kList p,q;(*L)

5、=(CLi nkList)malloc(sizeof(ListNode); if(*L)=NULL)prin tf(error n);else(*L)- next=NULL;q=*L;for(i=0;i data=i+1; p-password=pi n; q- next=NULL; q_n ext=p;q=p;q-next=(*L)-next;/ 指向 L 結(jié)點，形成2創(chuàng)建這個鏈表地時間復(fù)雜度為O(n),空間復(fù)雜度為 O (n )顯示鏈表中地信息內(nèi)容：void Display(CLinkList *L,int n)int i;CLi nkList p;p=(*L)-n ext;printf(

6、n顯示鏈表內(nèi)容n);for(i=0;idata,p-password);p=p-n ext;2該算法地時間復(fù)雜度為O( n),空間復(fù)雜度為O(n ).刪除結(jié)點，完成出列功能：void Delete_L(CLinkList *L,int n,int m)int i=0,j;CLin kList p,q;q=(*L);p=(*L)-n ext;printf(n 刪除地順序：n);while(i n)for(j=0;jn ext;printf(編號：%d 密碼：%dn,p-data,p-password);m=p-password;q_n ext=p-n ext;free(p);p=q _n ext

7、;n-;該算法地時間復(fù)雜度為O( n2)，空間復(fù)雜度為0( n2).該設(shè)計地巧妙之處在于并不需要額外地空間來存儲數(shù)據(jù)，因而空間復(fù)雜度較低，而且線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)可以用物理位置上地鄰接關(guān)系來表示結(jié)點間地邏輯關(guān)系，這樣使讀者在閱讀代碼地過程中可以更加方便和便于理解.它可以隨機(jī)存取表中地任一結(jié)點，還可以免插入和刪除操作帶來地大量地結(jié)點地移動，能給結(jié)點動態(tài)分配內(nèi)存，這樣就不存在存儲空間不足地情況，而且循環(huán)鏈表還可以方便地從鏈表地最后一個結(jié)點遍歷到鏈表地第一個結(jié)點.使操作更加方便.5PCzVD7HxA(2)你在調(diào)試過程中發(fā)現(xiàn)了怎樣地問題？又做了怎樣地改進(jìn)1)在最開始地調(diào)試階段，我發(fā)現(xiàn)鏈表插入結(jié)束之后，

8、不能按照正常情況下輸出鏈表地 內(nèi)容，只能正常顯示第一個人地數(shù)據(jù)，在顯示第二個人地信息是數(shù)據(jù)為亂碼.之后我發(fā)現(xiàn)，在插入鏈表地過程中，我是在執(zhí)行循環(huán)插入數(shù)據(jù)地循環(huán)中將結(jié)點地指針指向了第一個結(jié)點，因而，在進(jìn)行鏈表顯示地過程中，第二個結(jié)點地內(nèi)容不是正常地數(shù)據(jù).之后我將3 3 1717 2 2 4 4 8 8 4 4密密密密密密密0 02 2 3 3 1717 2 2 484484 VVBVVB VBVB nFnF v v 頁 r r n n61472356147235 a a 的 .s 列口！P號號號號號口eses dddd i ip p帛密密密密密密密y y8 8 3 3 2417424174 o

9、ot tcontincontinueueq-next=（*L）-next;這條指令放到了整個插入循環(huán)地外部，這樣表示在插入所有數(shù)據(jù)之后， 最后一個結(jié)點地指針指向了第一個結(jié)點，形成了一個循環(huán)隊列，此時鏈表地數(shù)據(jù)顯示正 確.jLBHrnAlLg2）再次調(diào)試時，我發(fā)現(xiàn)人員出列時，只有第一個人出列正常，在第二個人出列時程序自動終止，不能正常顯示之后出列地人地信息，并且程序自動終止運行，經(jīng)過檢查我發(fā)現(xiàn)在經(jīng)過一次刪除后，沒有將指針指向下一個結(jié)點，因而出現(xiàn)問題經(jīng)過更改，程序運行正常.XHAQX74J0X3）在實驗地開始階段，數(shù)據(jù)遍歷總是出現(xiàn)問題，經(jīng)過查找資料我發(fā)現(xiàn)了約瑟夫環(huán)頭結(jié)點地特殊性，因此我不再使用頭結(jié)

10、點，程序便恢復(fù)正常了.LDAYtRyKfE（2 ）測試結(jié)果、D:學(xué)咬謐撓議徴斡瑞實邇約瑟夫環(huán)DE五、實驗結(jié)果總結(jié)回答以下問題：（1） 你地測試充分嗎？為什么？你是怎樣考慮地？答：我認(rèn)為我地測試充分，因為我隨機(jī)選用了很多組不同地數(shù)據(jù)進(jìn)行測試，并且 每次測試地結(jié)果都是正確地答案，這樣選取地數(shù)據(jù)具有很強(qiáng)地隨機(jī)性，具有代表性， 因而我認(rèn)為我地測試比較充分 Zzz6ZB2Ltk（2） 你地存儲結(jié)構(gòu)地選取是不是很適合這個應(yīng)用？為什么？答：我認(rèn)為我選取地線性鏈?zhǔn)酱鎯Y(jié)構(gòu)適合這個應(yīng)用，因為首先此題中描述地情 景中表示人們按照順時針地方向進(jìn)行排隊，此時頭尾相連，這與循環(huán)鏈表地結(jié)構(gòu)十分 相似，使用循環(huán)鏈表地結(jié)構(gòu)，

11、這樣可以很方便地從鏈表地最后一個結(jié)點訪問到鏈表地 第一個結(jié)點，并且這樣地存儲方式是用物理位置上地鄰接關(guān)系來表示結(jié)點間地邏輯關(guān) 系，根據(jù)這個特點，該種結(jié)構(gòu)可以隨機(jī)存取表中地任一結(jié)點，而且它也可以避免插入 和刪除操作帶來地大量結(jié)點地移動，并且可以隨時分配空間和釋放空間，這樣可以減 少空間地使用量，并且可以做到靈活地擴(kuò)充空間，這樣地結(jié)構(gòu)很適合這個應(yīng) 用.dvzfvkwMIl（3） 用一段簡短地代碼及說明論述你地應(yīng)用中有關(guān)插入和刪除元素是如何做地？答：插入元素：首先定義了兩個臨時指針p和q來分別表示新插入結(jié)點地指針和第一個結(jié)點地指針，在每次插入之前應(yīng)該動態(tài)地分配內(nèi)存，輸入要輸入地信息，并且將各種數(shù)據(jù)存

12、儲到鏈表中相應(yīng)地項里，將前一個結(jié)點地 next賦值為空，再將前一個結(jié)點地指針指向下一個結(jié)點， 此時完成一個元素地插入依次類推，運用循環(huán)來實現(xiàn)所有 人地數(shù)據(jù)地插入，關(guān)鍵代碼如下：rqyn14ZNXIp=(CL in kList)malloc(sizeof(ListNode);if(p=NULL)prin tf(errorn);printf(請輸入第d個人地密碼：”,i+1);scan f(%d,&pi n);p-data=i+1;p-password=pi n;q- next=NULL;q_n ext=p;q=p;刪除元素：進(jìn)行循環(huán)來實現(xiàn)每個元素出列地功能，首先每個人進(jìn)行循環(huán)，一次進(jìn)行報數(shù)，在報

13、到 m-1之前都不進(jìn)行刪除元素這個動作，在m時，把此時結(jié)點中地password中地數(shù)值賦給m然后運用q-next=p-next;將結(jié)點刪除，同時釋放結(jié)點 p, 將人數(shù)減1,以此類推完成所有地刪除操作，直到所有地元素出列，關(guān)鍵代碼如下：EmxvxOtOcowhile(i n)for(j=0;jn ext;printf(編號：%d 密碼：dn,p-data,p-password);m=p-password;q_n ext=p-n ext;free(p);p=q _n ext;n-;(4)在你地應(yīng)用中是否用到了頭結(jié)點？你覺得使用頭結(jié)點為你帶來方便了嗎？答：在我地應(yīng)用中我沒有用到頭結(jié)點在實驗地一開始，

14、我使用了頭結(jié)點，但是使用頭結(jié)點給數(shù)據(jù)地遍歷帶來了困難，因此我便放棄使用頭結(jié)點.SixE2yXPq5(5 )源程序地大致地執(zhí)行過程是怎樣地？答：首先用編譯器編寫一個.c地文件，然后編譯生成.obj地文件，通過連接將目 標(biāo) 文件連接生成一個.exe文件，之后運行文件就可以執(zhí)行了.6ewMyirQFL六、附錄(1 )實驗設(shè)想和建議這次實驗提高了我對數(shù)據(jù)結(jié)構(gòu)中關(guān)于循環(huán)鏈表和順序表地理解，提高了我地編程能力，學(xué)校以后最好可以增加實驗課地課時，這樣我們可以更大程度地提高自己地編程能力.另外我認(rèn)為該實驗不僅可以使用使用鏈表指針來實現(xiàn)，還可以使用數(shù)組來模擬 鏈表來實現(xiàn)約瑟夫環(huán)，用數(shù)組地下標(biāo)來指向前一個和后一個

15、元素，之后進(jìn)行刪除來實 現(xiàn)約瑟夫環(huán).kavU42VRUs（2）參考資料：數(shù)據(jù)結(jié)構(gòu)（第二版）閆玉寶編著 清華大學(xué)出版社版權(quán)申明本文部分內(nèi)容，包括文字、圖片、以及設(shè)計等在網(wǎng)上搜集整理.版權(quán)為個人所有This article in eludes someparts, in clud ing text, pictures, and desig n. Copyright is pers onal own ership.y6v3ALoS89用戶可將本文地內(nèi)容或服務(wù)用于個人學(xué)習(xí)、研究或欣賞，以及其他非商業(yè)性或非盈利性用途，但同時應(yīng)遵守著作權(quán)法及其他相關(guān)法律 地規(guī)定，不得侵犯本網(wǎng)站及相關(guān)權(quán)利人地合法權(quán)利.除此

16、以外，將本文任何內(nèi)容或服務(wù)用于其他用途時，須征得本人及相關(guān)權(quán)利人地書面 許可，并支付報酬.M2ub6vSTnPUsers may use the contents or services of this articlefor personal study, research or appreciation, and other non-commercial or non-profit purposes, but at the same time, they shall abide by the provisi ons of copyright law and other releva nt l

17、aws, and shall n ot infringe upon the legitimate rights of this website and its releva nt obligees. In additi on, when any content or service of this article is used for other purposes, writte n permissi on and remun erati on shall be obta ined from the pers on concerned and the releva nt obligee. oYujefmuew轉(zhuǎn)載或引用本文內(nèi)容必須是以新聞性或資料性公共免費信息為使用目地地合理、善意引用，不得對本文內(nèi)容原意進(jìn)行曲解、修改， 并自負(fù)版權(quán)等法律責(zé)任 eUts8ZQVRdReproducti on or quotatio n of the content