約瑟夫環(huán)試驗報告

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

2、方向自 1 開始順序報數(shù)，報到 m時停止報數(shù)。報m的人 出列，將他的密碼作為新的 m值，從他的順時 針方向上的下一個人開始重新從 1報數(shù)，如此下 去，直至所有人全部出列為止。設(shè)計一個程序求 出出列順序。(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)出列的功能。(3)簡短明確地寫出實驗所采用的存儲結(jié)構(gòu)， 并加以說明。該實驗我主要采用的是線性表的鏈?zhǔn)酱鎯?結(jié)構(gòu)，首先定義了鏈表的結(jié)構(gòu)，其中包括data項和password項，分別存儲每個人的編號和所 持密碼，還聲明了指向下一個結(jié)點的指針，該指針可以連接各個結(jié)點，并且將最后一個結(jié)點的指 針指向第一個結(jié)點使之成為一個循環(huán)鏈表。三、實驗環(huán)境操作系統(tǒng)：Windows 7調(diào)試軟件名稱：VC+版本號：6.0上機地點：綜合樓3

4、11四、實驗過程與分析(1)主要的函數(shù)或操作內(nèi)部的主要算法，分析 這個算法的時、空復(fù)雜度，并說明設(shè)計的巧妙之 處。本實驗中主要的函數(shù)包括創(chuàng)建鏈表、 顯示鏈 表內(nèi)容和出列過程四個部分。主要函數(shù)的代碼如 下：創(chuàng)建鏈表：typedef int Datatype;typedef struct node/ 鏈表的定義(Datatype data;int password;struct node *next;ListNode,*CLinkList;void CreatList_CL(CLinkList *L,int n)/創(chuàng) 建一個鏈表(int i,pin;CLinkList p,q;(*L)=(CLin

5、kList)malloc(sizeof(ListNode);if(*L)=NULL)printf("errorn");else(*L)->next=NULL;q=*L;for(i=0;i<n;i+) ( 3p=(CLinkList)malloc(sizeof(ListNode);if(p=NULL) printf("errorn");printf("請輸入第個人的密碼： ",i+1);scanf("%d”,&pin);p->data=i+1;p->password=pin;q->next

6、=NULL;q->next=p;q=p; q->next=(*L)->next; 指向 L 結(jié)點，形成 創(chuàng)建這個鏈表的時間復(fù)雜度為O(n),空間復(fù)雜度為O (n2)。顯示鏈表中的信息內(nèi)容：void Display(CLinkList *L,int n)int i;CLinkList p;p=(*L)->next; printf("n 顯示鏈表內(nèi)容n");for(i=0;i<n;i+)(printf("編號：%2d 密 碼： %dn",p->data,p->password);p=p->next;)該算法的時

7、間復(fù)雜度為 O (n),空間復(fù) 雜度為O(n2)。刪除結(jié)點，完成出列功能：void Delete_L(CLinkList *L,int n,int m)(int i=0,j;CLinkList p,q;q=(*L);p=(*L)->next;printf("n 刪除的順序:n");while(i<n)(for(j=0;j<m-1;j+)(q=p；p=p->next;)printf(" 編 號： d 密 碼：dn",p->data,p->password);m=p->password;q->next=p-&g

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

9、的改進1)在最開始的調(diào)試階段，我發(fā)現(xiàn)鏈表插入 結(jié)束之后，不能按照正常情況下輸出鏈表的內(nèi) 容，只能正常顯示第一個人的數(shù)據(jù)，在顯示第二 個人的信息是數(shù)據(jù)為亂碼。之后我發(fā)現(xiàn)，在插入 鏈表的過程中，我是在執(zhí)行循環(huán)插入數(shù)據(jù)的循環(huán) 中將結(jié)點的指針指向了第一個結(jié)點，因而，在進行鏈表顯示的過程中，第二個結(jié)點的內(nèi)容不是正 常的數(shù)據(jù)。之后我將q->next=(*L)->next;這條指 令放到了整個插入循環(huán)的外部，這樣表示在插入 所有數(shù)據(jù)之后，最后一個結(jié)點的指針指向了第一 個結(jié)點，形成了一個循環(huán)隊列，此時鏈表的數(shù)據(jù) 顯示正確。2)再次調(diào)試時，我發(fā)現(xiàn)人員出列時，只有 第一個人出列正常，在第二個人出列時程

10、序自動 終止，不能正常顯示之后出列的人的信息， 并且 程序自動終止運行，經(jīng)過檢查我發(fā)現(xiàn)在經(jīng)過一次 刪除后，沒有將指針指向下一個結(jié)點，因而出現(xiàn)問題。經(jīng)過更改，程序運行正常。3)在實驗的開始階段，數(shù)據(jù)遍歷總是出現(xiàn) 問題，經(jīng)過查找資料我發(fā)現(xiàn)了約瑟夫環(huán)頭結(jié)點的 特殊性，因此我不再使用頭結(jié)點，程序便恢復(fù)正 常了。(2)測試結(jié)果事D學(xué)皆建辱善后葩妻含藥毒天環(huán)24174 to cantinue33馬333當(dāng)yrl密密重密密.的h-:到號號號號號號號馬馬3馬馬馬馬 密密密密密密密 JOM"-TT -fvLT1 7人人人人人人人廠變 L 2 3 4 5t7 -入第第第第第第第 人人入AA-入入入A-

11、主耳坐R土耳主R壬同主閆王同主R壬月3 17 2 4 8 4馬333馬33一密密密密密密密12 3 4 5 6 7-小號號號號號號號五、實驗結(jié)果總結(jié)回答以下問題：(1)你的測試充分嗎？為什么？你是怎樣考慮的？答：我認為我的測試充分，因為我隨 機選用了很多組不同的數(shù)據(jù)進行測試，并且 每次測試的結(jié)果都是正確的答案，這樣選取 的數(shù)據(jù)具有很強的隨機性，具有代表性，因 而我認為我的測試比較充分。(2)你的存儲結(jié)構(gòu)的選取是不是很 適合這個應(yīng)用？為什么？答：我認為我選取的線性鏈?zhǔn)酱鎯Y(jié) 構(gòu)適合這個應(yīng)用，因為首先此題中描述的情 景中表示人們按照順時針的方向進行排隊， 此時頭尾相連，這與循環(huán)鏈表的結(jié)構(gòu)十分相 似

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

13、且將各 種數(shù)據(jù)存儲到鏈表中相應(yīng)的項里，將前一個 結(jié)點的next賦值為空，再將前一個結(jié)點的指 針指向下一個結(jié)點，此時完成一個元素的插 入。依次類推，運用循環(huán)來實現(xiàn)所有人的數(shù) 據(jù)的插入，關(guān)鍵代碼如下：p=(CLinkList)malloc(sizeof(ListNode);if(p=NULL)printf("errorn");printf("請輸入第%d個人的密碼:",i+1);scanf("%d”,&pin);p->data=i+1;p->password=pin;q->next=NULL;q->next=p;q=

14、p;10刪除元素：進行循環(huán)來實現(xiàn)每個元 素出列的功能，首先每個人進行循環(huán)，一次 進行報數(shù)，在報到m-1之前都不進行刪除元 素這個動作，在m時，把此時結(jié)點中的 password中的數(shù)值賦給m然后運用 q->next=p->next;將結(jié)點刪除，同時釋放結(jié) 點p,將人數(shù)減1,以此類推完成所有的刪除 操作，直到所有的元素出列，關(guān)鍵代碼如下：while(i<n)(for(j=0;j<m-1;j+)(q=p;p=p->next;printf("編號：%d 密 碼： dn",p->data,p->password);m=p->password;q->next=p->next;free(p);p=q->next;n-;11(4)在你的應(yīng)用中是否用到了頭結(jié)點？你 覺得使用頭結(jié)點為你帶來方便了嗎？答：在我的應(yīng)用中我沒有用到頭結(jié) 點。在實驗的一開始，我使用了頭結(jié)點，但 是使用頭結(jié)點給數(shù)據(jù)的遍歷帶來了困難，因 此我便放棄使用頭結(jié)點。(5)源程序的大致的執(zhí)行過程是怎樣的？答：首先用編譯器編寫一個.c的文 件，然后編譯生成.obj的文件，通過連接將目 標(biāo)文件連接生成