蘭州大學資料結構課程設計

《資料結構》課程設計題目

(程式實現採用c語言)

題目1：猴子選王（學時：3）

一堆猴子都有編號，編號是1，2，3 ...m，這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數，每數到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最後乙隻猴子，則該猴子為大王。

要求：m及n要求從鍵盤輸入，儲存方式採用向量及鍊錶兩種方式實現該問題求解。

題目2 ：字元逆轉（學時：3）

從鍵盤讀入乙個字串，把它存入乙個鍊錶（每個結點儲存1個字元），並按相反的次序將字串輸出到顯示屏。

題目3 ：工資核算（學時：3）

設有乙個單位的人員工資有如下資訊：name、department、 base pay、allowance、total。現從鍵盤輸入一組人員工資資料並將它們儲存到名為paydata的檔案中；再從paydata取出工資資料並給每個人的base pay增加100元，增加後將工資資料顯示於螢幕(每行1人)。

題目4：滿足條件的有序表生成（學時：3）

已知三個有序表a、b、c，它們皆由同一類元素構成，現要求對於表a作以下運算而獲得有序表d：排出a中所有的既在b中又在c中出現的元素。另外該任務要求具有建立有序表功能以及輸出有序表到螢幕的功能。

題目5：一元多項式的減法（學時：6）

設有兩個一元多項式a(x),b(x)，請完成運算a(x)+b(x)、a(x)-b(x)，要求多項式採用鍊錶進行儲存。另外該任務要求具有建立多項式鍊錶以及輸出多項式到螢幕的功能。

題目6：床位分配（學時：6）

某客店有n個等級的房間，第k級客房有a（k）個，每個房間有b（k）個單人床，以選單呼叫方式設計為單身旅客分配床位以及離店時收回床位的程式。要求分配成功時，印出旅客姓名、年齡、性別、到達日期、客房等級、房間號及床位號；分配不成功時，允許更改房間等級，若不更改等級，印出「滿客」提示。

題目7：文字檔案單詞的檢索及計數（學時：6）

要求程式設計建立乙個文字檔案，每個單詞不包括空格及跨行，單詞由字串行構成且區分大小寫，完成以下功能：統計給定單詞在文字檔案中出現的總次數、檢索輸出某單詞在文字檔案中首次出現的行號及位置。

題目8：二叉樹的遍歷（學時：6）

二叉樹以lson-rson鏈結方式儲存，以選單方式設計並完成功能任務：建立並儲存樹、輸出前序遍歷結果、輸出中序遍歷結果、輸出後序遍歷結果、交換左右子樹、統計高度，其中對於中序、後序的遍歷運算要求採用非遞迴方式。

題目9：建立二叉排序樹（學時：3）

二叉排序樹以lson-rson鏈結方式儲存，編寫能夠通過鍵盤輸入建立二叉排序樹，並在建立完立即在螢幕顯示中序遍歷結果的程式。

題目10：霍夫曼編碼應用（學時：3）

假設一串由大寫字母構成的電文，採用霍夫曼規則對其進行編碼，以選單方式設計並完成功能任務：建立霍夫曼樹、霍夫曼編碼生成、編碼檔案解碼。

#include

#define n 100

#define m 2*n-1

typedef struct //碼結點的儲存結構

codenode;

typedef codenode huffmancode[n+1];

typedef struct //樹結點的儲存結構

htnode;

typedef htnode huffmantree[m+1];

int num;

void select(huffmantree ht,int k,int &s1,int &s2)//挑選權值最小的兩個結點

s1=j;

minl=32767;

for(i=1;i<=k;i++)

if(ht[i].weight

s2=j;

}int jsq(char *s,int cnt,char str)//統計輸入字元和串

num=j;

return j;

}//建立霍夫曼樹

void chuffmantree(huffmantree&ht,huffmancode&hc,int cnt,char str)

for(i=1;i<=num;i++)

ht[i].weight=cnt[i];

for(i=num+1;i<=2*num-1;i++)

for(i=1;i<=num;i++)

hc[i].ch=str[i];

}//給霍夫曼樹的每個葉子節點分配二進位制**

void huffmanencoding(huffmantree ht,huffmancode hc)

strcpy(hc[i].bits,&cd[start]);

hc[i].len=num-start;

}}void decode(huffmancode hc,char receive,char s)//解碼

}str[k]='\0';

strcpy(s,str);

}void coding(huffmancode hc,char str,char get)//輸出字串的二進位制編碼

strcat(get,"\0");

}void main()

{ char str[257str用於在統計輸入序列中的字母時用，存放是什麼字元，1到256

char st[10000],s[10000]; //st 用來接收輸入的字串，s用來接收解壓的字串

int cn[257cn用於接收統計後的每個字元的頻率，1到256

huffmantree ht;

huffmancode hc;

char ch='y';int d,i;

printf霍夫曼樹n\n");

printf1.建立霍夫曼樹.\n");

printf2.生成霍夫曼編碼.\n");

printf3.編碼檔案解碼.\n");

while(ch=='y')

{printf("請選擇:");

scanf("%d",&d);

蘭州大學資料結構課程設計

蘭州大學資料結構課程設計

資料結構課程設計

資料結構課程設計

相關推薦