資料結構課程設計報告

目錄一、課程設計目的 2

二、功能描述 2

2.1演算法設計說明 2

2.2儲存結構設計說明 2

三、詳細設計 3

四、程式實現 6

4.1原始碼分析 6

4.2除錯結果 7

4.3問題思考 8

4.4改進設想 9

結束語 10

參考文獻 11

資料結構是實踐性很強的課程。課程設計是加強學生實踐能力的乙個強有力手段。課程設計要求學生在完成程式設計的同時能夠寫出比較規範的設計報告。

嚴格實施課程設計這一環節，對於學生基本程式設計素養的培養和軟體工作者工作作風的訓練，將起到顯著的促進作用。

本文是利用迴圈鍊錶解決joseph環問題。編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有乙個密碼（正整數）。一開始任選乙個正整數作為報數上限值m,從第乙個人開始順時針方向自1開始順序報數，報到m時停止報數。

報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下乙個人開始重新從1報數，如此下去，直到所有人全部出列為止。本文就是設計乙個程式來求出出列順序。

本演算法的流程是在main函式中使用乙個switch函式。switch函式有三個選項，執行第乙個選項後會產生乙個長為m的隨機鍊錶，並輸出；執行第二個選項後，輸入乙個任意正整數m，隨機鍊錶將會按照joseph環的規則以新的次序輸出；執行第三個選項，退出程式。其中，第

一、二個選項可以無限次迴圈使用。

本文是關於迴圈鍊錶的使用，資料採用迴圈鍊錶的鏈式儲存結構儲存。

迴圈鍊錶是另一種形式的鏈式儲存結構。它的特點是表中最後乙個結點的指標指向頭結點，整個鍊錶形成乙個環。從表中任意乙個點出發都可以找到其它結點。[1]

#include<>

#define m 8

#define elemtype int

#define status int

#define error 0

#define ok 1

typedef struct lnode

lnode,*linklist;

linklist l,p,q;

main()

}while(cord<=3);

}status creat()

return ok;

}//生成長度為m的隨機鍊錶

status display()

printf("\n");

return ok;

}//輸出已生成的隨機鍊錶

status outlin()

printf("%7d",p->data);

m=p->data;

p=pnext(p);

if(p==l) p=l->next;//跳過頭結點，頭結點不能作為一次迴圈的開始

}printf("\n");

return ok;

}//將鍊錶按照joseph規則輸出

int pnext(linklist p)

//刪除指定的結點，並讓前結點指向後結點

輸出操作提示選單。使用乙個switch函式實現建立、輸出之間的實現，並且能夠多次迴圈地進行建立、輸出的操作，也可以結束程式。

建立頭結點l，建立其他的結點，用倒序的方法插入，並使用隨機生成函式rand生成隨機數，為非頭結點的其他結點的data成員賦值,這裡data值為0沒有意義，所以用乙個for語句保證data值不為0。鍊錶的長度由巨集定義中的m值決定。為了保證生成數的隨機性，另外插入隨機種子生成函式srand，並引用標頭檔案，以時間為函式的引數。

該函式用於迴圈鍊錶的輸出，從頭結點後第乙個結點開始依次輸出各結點的值。使用for語句輸出時的迴圈條件是p->next==l，與順序鍊錶有所區別。

函式的一開始給m賦一任意正整數值，判斷鍊錶不為空，否則返回error。使用乙個for語句，迴圈次數為m，迴圈一次輸出乙個值，並進行刪除相應結點等操作。在迴圈體中，首先，再使用乙個for語句，使得指標p指向要出列的結點，迴圈的次數由m決定，但在經過頭結點時迴圈次數不加1，因為頭結點中data域為空。

然後，把該要出列結點的data值賦值給m，作為下一次迴圈的次數。最後，呼叫pnext函式，刪除該結點，並將返回值賦值給指標p，p就指向了所刪除結點的下乙個結點，也作為下次迴圈的開始結點，但是，在這裡p不能指向頭結點l，若指向l則讓p=p->next。再次進行大迴圈。

該函式在outlin函式中使用到，用於刪除實參指定的結點，通過乙個for語句找到要刪除的結點和它的前乙個結點，並把該結點的前乙個結點的指標域指向該結點的下乙個結點，保證各結點的連通。同時，返回所刪除結點的下一結點的位址。

首先，執行源程式如下圖所示

輸入cord值1，如下圖所示

然後，輸入cord值2，隨後輸入任意正整數給m，如下圖所示

最後，輸入cord值3，結束程式，如下圖所示

在編寫過程中主要遇到以下幾個問題：

一、在最初出列後刪除結點時，沒注意應該把前乙個結點的指標域指向下乙個結點。導致了在刪除操作以後不在是迴圈鍊錶。該問題在pnext函式中得到解決。

二、隨機數的產生範圍不對。隨機函式生成的數值在0-65535之間，我們取的隨機數限定為一位或兩位數，原來使用 e=rand()/1000語句，產生的隨機數在0-65之間，後改為 e=rand()/100%100，能產生0-99之間的隨機數。

三、給p->data賦值的時候，e的值不能為0。若產生的隨機數為0，應該另外再生成乙個非0數再賦值給e，所以用到了for(;e==0;) e=rand()/100%100;語句，可以保證每個數值都有意義。

四、沒處理頭結點。當末尾結點出列以後，向量p指向下乙個結點，但不能是頭結點，頭結點在沒有賦值，不能計數。所以每次刪除結點，p指向下乙個結點時，插入乙個判斷語句，若p指向了l，則p=p->next。

在執行迴圈語句經過頭結點l時也應作處理，讓計數變數i-1。

現有程式已經可以完全實現joseph環的功能，只是在鍊錶的生成上可以改進。可以外加乙個函式生成迴圈鍊錶，每個結點不使用隨機數，而是手動輸入每個結點的data域值，這樣就可以把指定的數列按照joseph原則進行排序。多增加這個功能，可以讓該程式的實用性大大增加。

如果結合已有程式，也可以再次把生成的鍊錶出列的序列匯入新的迴圈鍊錶中進行第二次轉換，可以在輸出的時候同時把各個數依次放入乙個順序棧中，二次生成迴圈鍊錶時再依次取出各數。該種方法類似於對原始碼的二次加密，進而可以實現原始碼的n次加密。

joseph環問題在生活中易於操作，可作為乙個小遊戲執行。在這裡，使用迴圈鍊錶模擬了joseph環的生成、出列等操作過程，可以直觀地表現出joseph環的功能和作用，也可以幫助我們更好地認識和了解它。

資料結構課程設計報告

資料結構課程設計報告

資料結構課程設計報告

《資料結構》課程設計報告

相關推薦