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

郭艷慧實驗一線性表08-10-20《數(shù)據(jù)結(jié)構(gòu)》實驗報告班級：姓名：學(xué)號：日期：08-10-20題目：約瑟夫環(huán)上機(jī)實驗的問題和要求：問題描述：編號為1到n的n個人圍成一圈，每人帶一個密碼c，以m為報數(shù)上限。然后從第一個人開始順時針自1開始報數(shù)，報到m的人出列，將其密碼作為新的m值，從他的下一個人開始，同樣順時針自1開始報數(shù)，依次循環(huán)下去，直到所有的人都出列！要求得到依次出列的那些人的編號序列！基本要求：用C代碼實現(xiàn)此活動，要求使用一定的算法進(jìn)行操作，并最終通過程序運算出最后的結(jié)果！二、程序設(shè)計的基本思想，原理和算法描述：（包括程序的模塊結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，輸入/輸出設(shè)計，符號名說明等）基本思想：利用不帶頭結(jié)點單向循環(huán)鏈表模擬該活動，在實現(xiàn)了一切動作之后，運用一定的算法得到最終的結(jié)果。程序的模塊結(jié)構(gòu)：定義了相關(guān)的結(jié)構(gòu)體之后，主要有以下幾大模塊：建立由頭指針指示的有n個結(jié)點的不帶頭結(jié)點的單向循環(huán)鏈表crt_CLinkList(H,n);尋找、輸出、刪除H單循環(huán)鏈表的第m個結(jié)點locfor(H,m);最后通過main函數(shù)體處理參數(shù)的輸入與顯示，并調(diào)用以上兩函數(shù)，最終解決問題。主要數(shù)據(jù)結(jié)構(gòu)：單鏈的循環(huán)鏈表，即線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。算法的偽碼描述：結(jié)構(gòu)體定義如下：typedefstructLnode/*定義單鏈表*/{intnumber;/*編號*/intcipher;/*密碼*/structLnode*next;/*指針*/}Lnode,*CLinklist;/*重定向命名*/CLinklistH;/*Ｈ為全局單鏈表*/算法的實現(xiàn)詳見源程序。輸入/輸出設(shè)計本程序并未采用任何二進(jìn)制文件出入的方式，這點說明將在最后總結(jié)提到。至于函數(shù)的出入口問題，在源程序及注釋中將得到詳細(xì)說明，這里不再贅述。三、源程序及注釋：(說明函數(shù)功能、入口及出口參數(shù),其他)#include<stdio.h>/*頭文件*/#include<stdlib.h>#include<alloc.h>typedefstructLnode/*定義單鏈表*/{intnumber;/*編號*/intcipher;/*密碼*/structLnode*next;/*指針*/}Lnode,*CLinklist;/*重定向命名*/CLinklistH;/*Ｈ為全局單鏈表*/structLnode*crt_CLinkList(CLinklistH,intm)/*創(chuàng)建一個不帶頭結(jié)點的單向循環(huán)鏈表*/{/*其中，Ｈ為全局單鏈表，m為鏈表結(jié)點總數(shù)*/inti;/*循環(huán)記數(shù)用*/ structLnode*ptr1;/*用于索引*/if((ptr1=(structLnode*)malloc(sizeof(structLnode)))==NULL)/*一旦動態(tài)內(nèi)存分配失敗，報錯退出！*/{perror("malloc");returnptr1;}H=ptr1;/*形成單個結(jié)點的單循環(huán)鏈表*/ptr1->next=H;for(i=1;i<m;i++)/*形成m個結(jié)點的不帶頭結(jié)點的單循環(huán)鏈表*/{if((ptr1->next=(structLnode*)malloc(sizeof(structLnode)))==NULL){perror("malloc");ptr1->next=H;returnH;}ptr1=ptr1->next;/*其中Ｈ指頭，ptr指尾*/ptr1->next=H;}returnH;/*返回成功新建的單鏈表Ｈ*/}voidlocfor(CLinklistH,intm)/*尋找輸出刪除鏈表Ｈ中的第m個結(jié)點*/{/*H為全局鏈表，m為要查找刪除的結(jié)點位置*/inti;/*循環(huán)計數(shù)*/structLnode*ptr;for(i=1;i<=5;i++)/*考慮圖形界面的美觀問題*/printf("number\tcipher\t");i=1;/*初始化*/while(H->next!=H)/*只剩單個結(jié)點時停止循環(huán)，進(jìn)行最后輸出！*/{ if(m==1)/*考慮進(jìn)行自身刪除的情況，即m=1*/ { for(ptr=H->next;ptr->next!=H;ptr=ptr->next);/*正因為是自身刪除才要費大勁尋找其父結(jié)點*/ printf("%-6d\t",H->number);/*找到后，先輸出*/ printf("%-6d\t",H->cipher);m=H->cipher;/*確定下一次尋找的m值*/ptr->next=H->next;*刪除結(jié)點，即自身結(jié)點*/ ptr=ptr->next;free(H);/*因為對于鏈表中的結(jié)點，每個之前都分配了內(nèi)存，所以free是必要的*/ H=ptr;/*不同于以下普通結(jié)點的刪除，自身刪除還要還原H*/i=1;/*i重置，以方便下一次的循環(huán)操作*/ } elseif(i==m-1)/*因為從自身開始即為1號，因為m-1,而不是m*/{ptr=H->next;/*結(jié)點的刪除操作同于上面的情況!*/ printf("%-6d\t",ptr->number); printf("%-6d\t",ptr->cipher);m=ptr->cipher;H->next=ptr->next; H=H->next;free(ptr);i=1;}else{H=H->next;/*若未找到，則繼續(xù)遍歷！*/i++;}} printf("%-6d\t",H->number);/*對于單個結(jié)點的單循環(huán)鏈表，進(jìn)行最終的輸出操作！*/ printf("%-6d",H->cipher); free(H);/*完成所有任務(wù)并釋放所有內(nèi)存占用！*/}voidmain()/*主函數(shù)接口*/{/*調(diào)用所有函數(shù)，進(jìn)行實驗?zāi)M，并得出實驗結(jié)果！*/ inti,j,n=30,m,k; structLnode*ptr; randomize();/*因為下面調(diào)用了random函數(shù)，故此處的初始化很有必要！*/ printf("Nowtheexperimentwillbegin.Youhavetwochoices!\n");/*數(shù)據(jù)輸入可以電腦隨機(jī)，也可以自行輸入*/ printf("Ifyouwanttoenterthedatasallbyyourself,pleaseenter1.\n");/*自行輸入（方便檢測程序問題）*/ printf("Ifyouwanttogetthedatasbythecomputer,pleaseenter0.\n");/*電腦隨機(jī)產(chǎn)生數(shù)據(jù)*/ printf("Nowyourchoice:");/*用戶選擇*/ scanf("%d",&j); while(j!=0&&j!=1)/*考慮程序的完善性，對于誤輸入的提示并報警！*/ { printf("\nYouenterisunillage!Pleasetryagain!\n"); printf("Nowyourchoice:");/*重新輸入*/ scanf("%d",&j); } H=crt_CLinkList(H,n);/*初始化鏈表*/if(j==0)/*電腦隨機(jī)充入數(shù)據(jù)*/ for(i=1;i<=30;i++) { H->number=i; H->cipher=rand();/*隨機(jī)函數(shù)*/ H=H->next; } else/*此時選擇實驗者輸入數(shù)據(jù)！*/ { for(i=1;i<=30;i++) { H->number=i; printf("Nownumber%d,pleaseenterthecipher:",i); scanf("%d",&k); H->cipher=k; H=H->next; } } m=rand();/*默認(rèn)情況下，m隨機(jī)產(chǎn)生*/ printf("Doyouwanttoenterthenumberm?Enter1tosetorotherscancel!\n");/*當(dāng)然，如果想自已輸，可以進(jìn)行覆蓋*/ scanf("%d",&k); if(k==1)/*自行輸入m值*/ { printf("Pleaseenterthenumberm:"); scanf("%d",&m); } system("cls");/*考慮屏幕大小，進(jìn)行分屏顯示*/ printf("Allfollowedareyourdatas!\n");/*界面友善*/for(i=1;i<=5;i++)printf("number\tcipher\t");for(i=0;i<30;i++)/*顯示所有處理前數(shù)據(jù)*/{ printf("%-6d\t",H->number); printf("%-6d\t",H->cipher);H=H->next; } printf("Andthenumbermis:%d\n",m); printf("\nAftertheprogram,theresultis:\n"); locfor(H,m);/*對所有數(shù)據(jù)進(jìn)行實驗處理，直至所有結(jié)點處理完！*/ getchar(); printf("\nPressanykeyreturn!");/*TC環(huán)境下，方便查看結(jié)果！*/ getchar();}四、用戶使用說明與測試運行結(jié)果：1．運行程序后，首先彈出界面，截圖如右：理性化的選擇：如果打1，則所有的cipher均由用戶輸入，這樣方便對特殊數(shù)據(jù)進(jìn)行程序測試！如果打0，那么所有的數(shù)據(jù)均由電腦產(chǎn)生！那如果打其他的呢？考慮到誤輸入，加了一個循環(huán)，以提高程序的健壯性！2．首先自行輸入數(shù)據(jù)進(jìn)行測試。輸完后的對話框：同樣的，對于m的輸入，這里也有兩種情況，只是在程序中表現(xiàn)為，無論你是否輸入，m先都已經(jīng)隨機(jī)產(chǎn)生，當(dāng)你自己輸時，它就被覆蓋掉了，感覺還是很優(yōu)化的。畢竟，當(dāng)我們用電腦產(chǎn)生隨機(jī)數(shù)時，它的位數(shù)將達(dá)到五位，這對于程序的代碼測試，幾乎不可能！這里，我們手動輸入（當(dāng)然，只有1才行）！這個是結(jié)果，界面還算整齊！經(jīng)檢驗，正確！3．接下來，讓電腦產(chǎn)生數(shù)據(jù)試試。最終結(jié)果如下：一樣的界面，只是隨機(jī)產(chǎn)生的數(shù)所比較大而矣！另外，不知道大家是否注意到了，結(jié)果中的屏幕已經(jīng)被刷新過了，這就是system(“cls”);的功勞，通常一屏顯示不下時就可以調(diào)用這個函數(shù)進(jìn)行刷屏！還有，最后那句pressanykeyreturn！這個是getchar();導(dǎo)致的，因為這樣才能保留結(jié)果，不必再調(diào)用userscreen命令查看結(jié)果！。4．對于所有的運行狀況這里都進(jìn)行了討論，程序個人感覺還算完善！至于其他的問題，將在下面得到討論。另外，我用vc跑過這個程序，這樣得到了一個可執(zhí)行文件，運行起來跟真的一樣，不妨雙擊試試！五、調(diào)試和運行程序過程中產(chǎn)生的問題及采取的措施：問題1：環(huán)境的使用，這個，因為TC環(huán)境對于很多快捷鍵乃至修改、撤消的限制，所以用起來相當(dāng)困難，也不喜歡它。解決：這個就得益于平時對其他工具的使用了，比如，用記事本打開，就可以方便的復(fù)制粘貼，查找替換；用VC編輯代碼就更容易保持其格式化，而且，理所當(dāng)然的，更容易發(fā)現(xiàn)問題所在！還有，對于注釋的編寫，因為在TC中，是無法實現(xiàn)漢字輸入的，所以，沒有記事本和其他工具的幫助，真的可以說是困難重重！問題2：typedef使用時CLinklistH;這句始終都得不到通過。解決：查了好多資料，也試了好多方法，結(jié)果，居然發(fā)現(xiàn)是Lnode拼成了Londe，唉，不該……問題3：對于函數(shù)*crt_CLinkList的報警，更是讓我好一陣子百思不得其解。解決：嘗試很多改法，居然發(fā)現(xiàn)問題是CLinklist中的l打成了I，又是一陣汗……問題4：數(shù)據(jù)分布問題，這個主要是表現(xiàn)在界面沒有滾動條，以致大部分?jǐn)?shù)據(jù)不得見！解決：一方面調(diào)用system(“cls”);函數(shù)，進(jìn)行刷屏，這樣，就可以把沒必要的內(nèi)容提前清掉；另一方面，我對界面布局進(jìn)行改造，正如上面的結(jié)果所示，由原來的一行一個改成了一行5個，這樣，至少可以做到一屏之內(nèi)裝下所有的數(shù)據(jù)。問題5：有返回與無返回的區(qū)別。這個確實給我的調(diào)試帶來了相當(dāng)大的阻力。因為對于鏈表的定義，一開始就定義為全局的，所以在函數(shù)中修改后，自然的，我們會認(rèn)為它已經(jīng)實現(xiàn)了更改，再傳回去根本多此一舉。所以，對于，最終的傳參，我用crt_CLinkList(H,n);結(jié)果，報警不斷！解決：對于指針函數(shù)，有返回就一定有接收，跟無返回的有本質(zhì)的區(qū)別，你即然是有返回的函數(shù)，對傳遞過去的參數(shù)不接收就一定有問題。最后，我改成了H=crt_CLinkList(H,n);問題6：對于老師關(guān)于“主程序處理參數(shù)輸入與顯示”的說法，我覺得可能有手動輸入的意思！我當(dāng)時的程序，所有的數(shù)據(jù)都是電腦random出來的。解決：加入一個j變量，讓用戶進(jìn)行選擇，是否手動輸入，若為1即手動，此時再建一個手動輸入的語句段；若為0，由電腦自動生成，結(jié)果，運行良好！問題7：因為VC跟TC的區(qū)別，每次運行完后，TC自動關(guān)閉窗口，看不到結(jié)果！解決：這個最終用getchar();實現(xiàn)了！當(dāng)然，后來還發(fā)現(xiàn)問題依舊在，這是因為，最后輸入數(shù)據(jù)的同時，按了enter鍵，這個對于getchar()來說，一樣截獲，換言之，getchar就無效了。最后用了兩個ge