約瑟夫環(huán)試驗(yàn)報(bào)告

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

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

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

4、11四、實(shí)驗(yàn)過(guò)程與分析(1)主要的函數(shù)或操作內(nèi)部的主要算法，分析 這個(gè)算法的時(shí)、空復(fù)雜度，并說(shuō)明設(shè)計(jì)的巧妙之 處。本實(shí)驗(yàn)中主要的函數(shù)包括創(chuàng)建鏈表、 顯示鏈 表內(nèi)容和出列過(guò)程四個(gè)部分。主要函數(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) 建一個(gè)鏈表(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("請(qǐng)輸入第個(gè)人的密碼： ",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é)點(diǎn)，形成 創(chuàng)建這個(gè)鏈表的時(shí)間復(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("編號(hào)：%2d 密 碼： %dn",p->data,p->password);p=p->next;)該算法的時(shí)

7、間復(fù)雜度為 O (n),空間復(fù) 雜度為O(n2)。刪除結(jié)點(diǎn)，完成出列功能：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(" 編 號(hào)： d 密 碼：dn",p->data,p->password);m=p->password;q->next=p-&g

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

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

10、序自動(dòng) 終止，不能正常顯示之后出列的人的信息， 并且 程序自動(dòng)終止運(yùn)行，經(jīng)過(guò)檢查我發(fā)現(xiàn)在經(jīng)過(guò)一次 刪除后，沒(méi)有將指針指向下一個(gè)結(jié)點(diǎn)，因而出現(xiàn)問(wèn)題。經(jīng)過(guò)更改，程序運(yùn)行正常。3)在實(shí)驗(yàn)的開(kāi)始階段，數(shù)據(jù)遍歷總是出現(xiàn) 問(wèn)題，經(jīng)過(guò)查找資料我發(fā)現(xiàn)了約瑟夫環(huán)頭結(jié)點(diǎn)的 特殊性，因此我不再使用頭結(jié)點(diǎn)，程序便恢復(fù)正 常了。(2)測(cè)試結(jié)果事D學(xué)皆建辱善后葩妻含藥毒天環(huán)24174 to cantinue33馬333當(dāng)yrl密密重密密.的h-:到號(hào)號(hào)號(hào)號(hào)號(hào)號(hào)號(hào)馬馬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-小號(hào)號(hào)號(hào)號(hào)號(hào)號(hào)號(hào)五、實(shí)驗(yàn)結(jié)果總結(jié)回答以下問(wèn)題：(1)你的測(cè)試充分嗎？為什么？你是怎樣考慮的？答：我認(rèn)為我的測(cè)試充分，因?yàn)槲译S 機(jī)選用了很多組不同的數(shù)據(jù)進(jìn)行測(cè)試，并且 每次測(cè)試的結(jié)果都是正確的答案，這樣選取 的數(shù)據(jù)具有很強(qiáng)的隨機(jī)性，具有代表性，因 而我認(rèn)為我的測(cè)試比較充分。(2)你的存儲(chǔ)結(jié)構(gòu)的選取是不是很 適合這個(gè)應(yīng)用？為什么？答：我認(rèn)為我選取的線性鏈?zhǔn)酱鎯?chǔ)結(jié) 構(gòu)適合這個(gè)應(yīng)用，因?yàn)槭紫却祟}中描述的情 景中表示人們按照順時(shí)針的方向進(jìn)行排隊(duì)， 此時(shí)頭尾相連，這與循環(huán)鏈表的結(jié)構(gòu)十分相 似

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

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

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