蘭州大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)4講解

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目 （程序?qū)崿F(xiàn)采用 C 語(yǔ)言） 題目 1：猴子選王（學(xué)時(shí)：3） 一堆猴子都有編號(hào)，編號(hào)是 1，2，3 .m ，這群猴子（ m個(gè)）按照 1-m的順 序圍坐一圈，從第 1 開(kāi)始數(shù)，每數(shù)到第 n 個(gè)，該猴子就要離開(kāi)此圈，這樣依次下 來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。 要求： m及 n 要求從鍵盤(pán)輸入，存儲(chǔ)方式采用向量及鏈表兩種方式實(shí)現(xiàn)該問(wèn) 題求解。 題目 2 ：字符逆轉(zhuǎn)（學(xué)時(shí)：3） 從鍵盤(pán)讀入一個(gè)字符串，把它存入一個(gè)鏈表（每個(gè)結(jié)點(diǎn)存儲(chǔ) 1 個(gè)字符），并 按相反的次序?qū)⒆址敵龅斤@示屏。 題目 3 ：工資核算（學(xué)時(shí)：3） 設(shè)有一個(gè)單位的人員工資有如下信息：name、

2、department 、 base pay 、 allowance 、 total ?，F(xiàn)從鍵盤(pán)輸入一組人員工資數(shù)據(jù)并將它們存儲(chǔ)到名為 paydata 的文件中； 再?gòu)?paydata 取出工資數(shù)據(jù)并給每個(gè)人的 base pay 增加 100 元，增加后將工資數(shù)據(jù)顯示于屏幕 （ 每行 1 人 ） 。 題目 4：滿足條件的有序表生成（學(xué)時(shí)：3） 已知三個(gè)有序表 A、B、C，它們皆由同一類元素構(gòu)成，現(xiàn)要求對(duì)于表 A 作以 下運(yùn)算而獲得有序表 D：排出 A中所有的既在 B 中又在 C中出現(xiàn)的元素。另外該 任務(wù)要求具有建立有序表功能以及輸出有序表到屏幕的功能。 題目 5：一元多項(xiàng)式的減法（學(xué)時(shí)：6） 設(shè)

3、有兩個(gè)一元多項(xiàng)式 A（x）,B（x） ，請(qǐng)完成運(yùn)算 A（x）+B（x） 、A（x）-B（x） ，要求多項(xiàng) 式采用鏈表進(jìn)行存儲(chǔ)。 另外該任務(wù)要求具有建立多項(xiàng)式鏈表以及輸出多項(xiàng)式到屏 幕的功能。 題目 6：床位 分配（學(xué)時(shí)：6） 某客店有 N個(gè)等級(jí)的房間，第 k 級(jí)客房有 A（k）個(gè)，每個(gè)房間有 B（k）個(gè) 單人床，以菜單調(diào)用方式設(shè)計(jì)為單身旅客分配床位以及離店時(shí)收回床位的程序。 要求分配成功時(shí)，印出旅客姓名、年齡、性別、到達(dá)日期、客房等級(jí)、房間號(hào)及 床位號(hào)； 分配不成功時(shí)， 允許更改房間等級(jí)， 若不更改等級(jí)， 印出“滿客” 提示。 題目 7：文本文件單詞的檢索及計(jì)數(shù)（學(xué) 時(shí)：6） 要求編程建立一個(gè)

4、文本文件， 每個(gè)單詞不包括空格及跨行， 單詞由字符序列 構(gòu)成且區(qū)分大小寫(xiě)，完成以下功能：統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)、 檢索輸出某單詞在文本文件中首次出現(xiàn)的行號(hào)及位置。 題目 8：二叉 樹(shù)的遍歷（學(xué)時(shí)：6） 二叉樹(shù)以 lson-rson 鏈接方式存儲(chǔ)， 以菜單方式設(shè)計(jì)并完成功能任務(wù)： 建立 并存儲(chǔ)樹(shù)、輸出前序遍歷結(jié)果、輸出中序遍歷結(jié)果、輸出后序遍歷結(jié)果、交換左 右子樹(shù)、統(tǒng)計(jì)高度，其中對(duì)于中序、后序的遍歷運(yùn)算要求采用非遞歸方式。 題目 9：創(chuàng)建 二叉排序樹(shù)（學(xué)時(shí)： 3） 二叉排序樹(shù)以 lson-rson 鏈接方式存儲(chǔ)， 編寫(xiě)能夠通過(guò)鍵盤(pán)輸入建立二叉排 序樹(shù)，并在建立完立即在屏幕顯示中序遍

5、歷結(jié)果的程序。 題目 10：霍夫曼編碼應(yīng)用（學(xué)時(shí)：3） 假設(shè)一串由大寫(xiě)字母構(gòu)成的電文， 采用霍夫曼規(guī)則對(duì)其進(jìn)行編碼， 以菜單方 式設(shè)計(jì)并完成功能任務(wù)：建立霍夫曼樹(shù)、霍夫曼編碼生成、編碼文件譯碼。 #include #include #include #define n 100 #define m 2*n-1 typedef struct / 碼結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) char ch; char bits9; int len; CodeNode; typedef CodeNode HuffmanCoden+1; typedef struct / 樹(shù)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) int weight; int lchi

6、ld,rchild,parent; HTNode; typedef HTNode HuffmanTreem+1; int num; void select(HuffmanTree HT,int k,int int minl=32767; for(i=1;i=k;i+) if(HTi.weightminl minl=HTi.weight; s1=j; minl=32767; for(i=1;i=k;i+) if(HTi.weightminl minl=HTi.weight; s2=j; int jsq(char *s,int cnt,char str)/ 統(tǒng)計(jì)輸入字符和串 char *p; in

7、t i,j,k=0; int temp257; for(i=0;i257;i+) tempi=0; for(p=s;*p!=0;p+) temp*p+; for(i=0,j=0;i=256;i+) if(tempi!=0) j+; strj=i; cntj=tempi; num=j; return j; /建立霍夫曼樹(shù) void chuffmanTree(HuffmanTree for(i=1;i=2*num-1;i+) HTi.lchild=0; HTi.rchild=0; HTi.parent=0; HTi.weight=0; for(i=1;i=num;i+) HTi.weight=cn

8、ti; for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; for(i=1;i=num;i+) HCi.ch=stri; /給霍夫曼樹(shù)的每個(gè)葉子節(jié)點(diǎn)分配二進(jìn)制代碼 void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) int c,p,i; char cdn; int start; cdnum=0; 進(jìn)制編碼串 f

9、or(i=1;i0) start-; cdstart=(HTp.lchild=c)?0:1; c=p; strcpy(HCi.bits, HCi.len=num-start; void decode(HuffmanCode HC,char receive,char s)/ 譯碼 char str268; char cd9; int i,j,k=0,p=0,cjs; while(receivep!=0) cjs=0; for( i=0;inumi+) cdi= ; cdi+1=0; cdi=receivep+; for(j=1;j=num;j+) if(strcmp(HCj.bits,cd)=0

10、) strk=HCj.ch; k+; cjs = 1; break; strk=0; strcpy(s,str); void coding(HuffmanCode HC,char str,char get)/ 輸出字符串的二進(jìn)制編碼 int i,j=0; while(strj!=0) for(i=1;i=num;i+) if(HCi.ch = strj) strcat(get,HCi.bits); break; j+; strcat(get,0); void main() /str 用于在統(tǒng)計(jì)輸入序列中的字母時(shí)用，存放是什么字 char str257; 符， 1 到 256 char st10

11、000,s10000; /st 用來(lái)接收輸入的字符串， s用來(lái)接收解壓的字符串 int cn257; /cn 用于接收統(tǒng)計(jì)后的每個(gè)字符的頻率， 1 到 256 HuffmanTree HT; HuffmanCode HC; char ch=y;int d,i; printf( 霍夫曼樹(shù) nn); printf(1.建立霍夫曼樹(shù) .n); printf(2.生成霍夫曼編碼 .n); printf(3.編碼文件譯碼 .n); while(ch=y) printf( 請(qǐng)選擇 :); scanf(%d, switch(d) case 1: printf( 輸入要編碼的字符串： ); scanf(%s,

12、 num=jsq(st,cn,str); /統(tǒng)計(jì)文件中的字符 strnum+1 = 0; chuffmanTree(HT,HC,cn,str); printf( 霍夫曼樹(shù)建立成功 !n);/ 建立霍夫曼樹(shù) break; case 2: HuffmanEncoding(HT,HC);/根據(jù)霍夫曼樹(shù)建立霍夫曼編碼 printf( 建立霍夫曼編碼如下 n 共有 %d 種字符 n,num); for(i=1;i=num;i+) printf( 字符 %c 次數(shù)為 %d, 編碼為 %sn,HCi.ch,cni,HCi.bits); char get10000; get0 = 0; coding(HC,s

13、t,get); printf(n 上述字符串的霍夫曼碼為 %sn,get); / printf( 編碼效率為 %f%n,code_ratio(st,cn,HC); break; case 3: printf( 輸入二進(jìn)制碼開(kāi)始譯碼： ); char receive10000; scanf(%s, decode(HC,receive,s);/ 譯碼 printf( 譯碼為： %sn,s); break; printf(n 是否繼續(xù)？ (y/n):); scanf(%c, scanf(%c, 題目 11：關(guān)鍵路徑尋找(學(xué)時(shí)：6) 對(duì)于給定的一個(gè)工程施工圖，該圖以邊為單位從鍵盤(pán)輸入，編寫(xiě)能夠找出該

14、圖的關(guān)鍵路徑的程序。 #includestdio.h #includestdlib.h #define LEN sizeof(struct Enode) typedef struct Vexnode /頂點(diǎn)表 int adjvex;/ 鄰接域 int dut;/ 記錄權(quán)值 struct Vexnode * next; vexnode; typedef struct Enode int indegree; int vertex; int ee,el; struct Vexnode * link; /記錄入度 /頂點(diǎn) /記錄最遲開(kāi)始時(shí)間和最早結(jié)束時(shí)間 enode; void print(enode

15、 dig,int first,int len) int i,j; static int top=0,list50; vexnode * q; i=first; q=digi.link; listtop=digi.vertex; top+; if (q=NULL) printf(%d,listlen); for (i=1+len;i%d,listi); printf(n); while (q!=NULL) j=q-adjvex; if (digj.ee=digj.el) listtop=digj.vertex; print(dig,j,len); / q=q-next; top-;/ int t

16、oposort(enode dig,int e_n,int stacktp) /進(jìn)棧 int top=0,bottom=0,i,j,len=0; vexnode *q; for (i=1; ibottom) i=stacktpbottom; q=digi.link; bottom+; while (q!=NULL) j=q-adjvex; digj.indegree-; if (digi.ee+q-dutdigj.ee) 時(shí)間 digj.ee=digi.ee+q-dut; if (digq-adjvex.indegree=0) stacktptop=q-adjvex; top+; q=q-ne

17、xt; if (top=e_n) 存在，則求出最遲結(jié)束時(shí)間 for (i=1; ibottom) top-; 一個(gè)事件開(kāi)始倒推 i=stacktptop; q=digi.link; while (q!=NULL) j=q-adjvex; if (digj.el-q-dutdut; q=q-next; for (i=0; ilen; i+) print(dig,stacktpi,i); return 0; else return 1; void main() enode dig20; / 頂點(diǎn)表數(shù)組 vexnode *q;/鄰接點(diǎn)鏈表 char ch; int e_n,v_n,m,i,j,u,v

18、,stacktp20; printf( 關(guān)鍵路徑 nn); printf( 請(qǐng)輸入頂點(diǎn)個(gè)數(shù)和邊的條數(shù)： ); scanf(%d%d, for (i=1; i=e_n; i+)/ 初始化 digi.indegree=0; digi.link=NULL; digi.vertex=i; digi.ee=digi.el=0; printf( 請(qǐng)輸入 %d 條邊以及該邊的權(quán)： n,v_n); for (i=0; iadjvex=v; q-dut=j; q-next=digu.link;/ 將 q 結(jié)點(diǎn) 放入 u 鄰接鏈表中 digu.link=q;/將 q 結(jié)點(diǎn) 放入 u 鄰接鏈表中 m=toposor

19、t(dig,e_n,stacktp); /拓?fù)渑判?if (m) printf( 圖中存在環(huán)，不存在關(guān)鍵路徑 n); else printf( 需要各點(diǎn)明細(xì)查詢嗎 y/n); scanf(n%c,; if (ch=y|ch=Y) for (i=0; ie_n; i+) printf(%d (%d %d) n,stacktpi,digstacktpi.ee,digstacktpi.el); 題目 12：堆排序?qū)崿F(xiàn)(學(xué)時(shí)：3) 假設(shè)有一個(gè)數(shù)據(jù)類型為整型的一維數(shù)組 A，A 中的數(shù)據(jù)元素呈無(wú)序狀態(tài)，編 寫(xiě)一個(gè)采用堆排序法將 A 中的數(shù)據(jù)元素按由小到大進(jìn)行排序的程序。 #include #define

20、MAX 255 int AMAX; void creatdui(int l,int m) /* 建初始堆過(guò)程函數(shù) */ int i,j,x; i=l; j=2*i; /*Rj 是 Ri 的左孩子 */ x=Ai; while(j=m) if(jm /* 若左孩子較大，則把 j 修改為右孩子的下標(biāo) */ if(x=1;i-) creatdui(i,n); /* 建立初始堆，遍布所有的根結(jié)點(diǎn) */ for(i=n;i=2;i-) /* 進(jìn)行 n-1 次循環(huán)完成堆排序 */ m=Ai; Ai=A1; /* 將第一個(gè)元素同當(dāng)前區(qū)域的最后一個(gè)元素對(duì)換 */ A1=m; creatdui(1,i-1);

21、/* 篩選 A1 結(jié)點(diǎn)，得到 i-1 個(gè)結(jié)點(diǎn)的堆，僅有 A1 可能違反堆性質(zhì) */ void main() int i,n; printf( 堆排序 nn); printf( 輸入整型一維數(shù)組 A 中數(shù)字總數(shù) :); scanf(%d, if(nMAX) printf(n 輸入的數(shù)據(jù)有誤 !); return; printf(n 請(qǐng)輸入整型無(wú)序序列 :n); for(i=1;i=n;i+) scanf(%d, printf(n 該序列為 :n); for(i=1;i=n;i+) printf(%4d,Ai); sortdui(n); printf(n 堆排序后的序列為 :n); for(i=1

22、;i=n;i+) printf(%4d,Ai); printf(n); 題目 13基數(shù)排序的實(shí)現(xiàn)(學(xué)時(shí)：3) A為每個(gè)關(guān)鍵字不超過(guò) 3 位的十進(jìn)制整數(shù)關(guān)鍵字集合， 試編寫(xiě)一個(gè)采用靜態(tài) 鏈表組織模式實(shí)現(xiàn)的基數(shù)排序程序?qū)?A 進(jìn)行由小到大的排序。 #include #include #define N 1024 int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen) int* pnCount=(int*)malloc(sizeof(int)* nMax);/保存計(jì)數(shù)的個(gè)數(shù) int i=0; for (i=0;inMax;+i) pnCounti=0; for (i=0;inLen;+i) / 初始化計(jì)數(shù)個(gè)數(shù) +pnCountnpIndexi; for (i=1; i=0;-i) -pnCountnpIndexi; pnSortpnCountnpInde