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

PAGEPAGE2實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：實驗成績：實驗名稱：順序表和鏈表的應(yīng)用學號：批閱教師簽字：實驗編號：實驗一姓名：實驗日期：指導教師：組號：實驗時間：一、實驗目的掌握線性表的基本操作（插入、刪除、查找）以及線性表合并等運算在順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)上的實現(xiàn)。重點掌握鏈式存儲結(jié)構(gòu)實現(xiàn)的各種操作。掌握線性表的鏈式存儲結(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，從第一個人開始按照順時針的方向自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來顯示鏈表當中的內(nèi)容，以確定存儲的數(shù)據(jù)沒有錯誤。定義了函數(shù)Delete_L來實現(xiàn)約瑟夫環(huán)中依次刪除的功能，依次比較，如果某個人所持的密碼和m值相等，則刪除這個結(jié)點，并且輸出此時該結(jié)點的編號和密碼，實現(xiàn)出列的功能。簡短明確地寫出實驗所采用的存儲結(jié)構(gòu)，并加以說明。該實驗我主要采用的是線性表的鏈式存儲結(jié)構(gòu)，首先定義了鏈表的結(jié)構(gòu)，其中包括data項和password項，分別存儲每個人的編號和所持密碼，還聲明了指向下一個結(jié)點的指針，該指針可以連接各個結(jié)點，并且將最后一個結(jié)點的指針指向第一個結(jié)點使之成為一個循環(huán)鏈表。三、實驗環(huán)境操作系統(tǒng)：Windows7調(diào)試軟件名稱：VC++版本號：6.0上機地點：綜合樓311四、實驗過程與分析（1）主要的函數(shù)或操作內(nèi)部的主要算法，分析這個算法的時、空復雜度，并說明設(shè)計的巧妙之處。本實驗中主要的函數(shù)包括創(chuàng)建鏈表、顯示鏈表內(nèi)容和出列過程四個部分。主要函數(shù)的代碼如下：創(chuàng)建鏈表：typedefintDatatype;typedefstructnode//鏈表的定義{Datatypedata;intpassword;structnode*next;}ListNode,*CLinkList;voidCreatList_CL(CLinkList*L,intn)//創(chuàng)建一個鏈表{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("請輸入第%d個人的密碼：",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é)點，形成}創(chuàng)建這個鏈表的時間復雜度為O(n)，空間復雜度為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("請輸入第%d個人的密碼：",i+1); scanf("%d",&pin); p->data=i+1; p->password=pin;q->next=NULL; q->next=p; q=p;刪除元素：進行循環(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密碼：%d\n",p->data,p->password); m=p->password; q->next=p->next; free(p); p=q->next; n--;}（4）在你的應(yīng)用中是否用到了頭結(jié)點？你覺得使用頭結(jié)點為你帶來方便了嗎？答：在我的應(yīng)用中我沒有用到頭結(jié)點。在實驗的一開始，我使用了頭結(jié)點，但是使用頭結(jié)點給數(shù)據(jù)的遍歷帶來了困難，因此我便放棄使用頭結(jié)點。（5）源程序的大致的執(zhí)行過程是怎樣的？答：首先用編譯器編寫一個.c的文件，然后編譯生成.obj的文件，通過連接將目標文件連接生成一個.exe文件，之后運行文件就可以執(zhí)行了。六、附錄（1）實驗設(shè)想和建議這次實驗提高了我對數(shù)據(jù)結(jié)構(gòu)中關(guān)于循環(huán)鏈表和順序表的理解，提高了我的編程能力，學校以后最好可以增加實驗課的課時，這樣