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

PAGEPAGE2實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級(jí)：實(shí)驗(yàn)成績(jī)：實(shí)驗(yàn)名稱：順序表和鏈表的應(yīng)用學(xué)號(hào)：批閱教師簽字：實(shí)驗(yàn)編號(hào)：實(shí)驗(yàn)一姓名：實(shí)驗(yàn)日期：指導(dǎo)教師：組號(hào)：實(shí)驗(yàn)時(shí)間：一、實(shí)驗(yàn)?zāi)康恼莆站€性表的基本操作（插入、刪除、查找）以及線性表合并等運(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)的各種操作。掌握線性表的鏈?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、3……n的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ咳顺钟幸粋€(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m，從第一個(gè)人開(kāi)始按照順時(shí)針的方向自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ù)類型和設(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)容，以確定存儲(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)出列的功能。簡(jiǎn)短明確地寫出實(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)：Windows7調(diào)試軟件名稱：VC++版本號(hào)：6.0上機(jī)地點(diǎn)：綜合樓311四、實(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)建鏈表：typedefintDatatype;typedefstructnode//鏈表的定義{Datatypedata;intpassword;structnode*next;}ListNode,*CLinkList;voidCreatList_CL(CLinkList*L,intn)//創(chuàng)建一個(gè)鏈表{inti,pin;CLinkListp,q;(*L)=(CLinkList)malloc(sizeof(ListNode)); if((*L)==NULL)printf("error\n");else (*L)->next=NULL; q=*L; for(i=0;i<n;i++) {p=(CLinkList)malloc(sizeof(ListNode)); if(p==NULL) printf("error\n"); printf("請(qǐng)輸入第%d個(gè)人的密碼：",i+1); scanf("%d",&pin); p->data=i+1; p->password=pin;q->next=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)容：voidDisplay(CLinkList*L,intn){inti;CLinkListp;p=(*L)->next;有人的數(shù)據(jù)的插入，關(guān)鍵代碼如下：p=(CLinkList)malloc(sizeof(ListNode)); if(p==NULL) printf("error\n"); printf("請(qǐng)輸入第%d個(gè)人的密碼：",i+1); scanf("%d",&pin); p->data=i+1; p->password=pin;q->next=NULL; q->next=p; q=p;刪除元素：進(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，以此類推完成所有的刪除操作，直到所有的元素出列，關(guān)鍵代碼如下：while(i<n){for(j=0;j<m-1;j++) { q=p; p=p->next; } printf("編號(hào)：%d密碼：%d\n",p->data,p->password); m=p->password; q->next=p->next; free(p); p=q->next; n--;}（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ò)程是怎樣的？答：首先用編譯器編寫一個(gè).c的文件，然后編譯生成.obj的文件，通過(guò)連接將目標(biāo)文件連接生成一個(gè).exe文件，之后運(yùn)行文件就可以執(zhí)行了。六、附錄（1）實(shí)驗(yàn)設(shè)想和建議這次實(shí)驗(yàn)提高了我對(duì)數(shù)據(jù)結(jié)構(gòu)中關(guān)于循環(huán)鏈表和順序表的理解，提高了我的編程能力，學(xué)校以后最好可以增加實(shí)驗(yàn)課的課時(shí)，這樣