1、數(shù)據(jù)結構課程設計題目（程序實現(xiàn)采用C語言）題目1:猴子選王（學時：3）一堆猴子都有編號，編號是1, 2, 3 .m，這群猴子（m個）按照1-m的順 序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個，該猴子就要離開此圈，這樣依次下 來，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：m及n要求從鍵盤輸入，存儲方式采用向量及鏈表兩種方式實現(xiàn)該問 題求解。題目2 :字符逆轉（學時：3）從鍵盤讀入一個字符串，把它存入一個鏈表（每個結點存儲1個字符），并按相反的次序將字符串輸出到顯示屏。題目3 :工資核算（學時：3）設有一個單位的人員工資有如下信息：name department、base pay、allowa

2、nee、total。現(xiàn)從鍵盤輸入一組人員工資數(shù)據(jù)并將它們存儲到名為paydata的文件中；再從paydata取出工資數(shù)據(jù)并給每個人的 base pay增加100 兀，增加后將工資數(shù)據(jù)顯示于屏幕（每行1人）。題目4：滿足條件的有序表生成（學時：3）已知三個有序表A、B、C,它們皆由同一類元素構成，現(xiàn)要求對于表 A作以 下運算而獲得有序表D:排出A中所有的既在B中又在C中出現(xiàn)的元素。另外該 任務要求具有建立有序表功能以及輸出有序表到屏幕的功能。題目5： 一元多項式的減法（學時：6）設有兩個一元多項式A（x）,B（x），請完成運算A（x）+B（x）、A（x）-B（x），要求多項 式采用鏈表進行存儲。

3、另外該任務要求具有建立多項式鏈表以及輸出多項式到屏 幕的功能。題目 6：床位 分配（學時：6）某客店有N個等級的房間，第k級客房有A （k）個，每個房間有B （k）個 單人床，以菜單調用方式設計為單身旅客分配床位以及離店時收回床位的程序。 要求分配成功時，印出旅客姓名、年齡、性別、到達日期、客房等級、房間號及 床位號；分配不成功時， 允許更改房間等級， 若不更改等級， 印出“滿客”提示。 題目 7：文本文件單詞的檢索及計數(shù)（學時：6）要求編程建立一個文本文件， 每個單詞不包括空格及跨行， 單詞由字符序列 構成且區(qū)分大小寫，完成以下功能：統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)、 檢索輸出某單詞在文

4、本文件中首次出現(xiàn)的行號及位置。題目 8：二叉 樹的 遍歷（學時：6）二叉樹以 lson-rson 鏈接方式存儲， 以菜單方式設計并完成功能任務： 建立 并存儲樹、輸出前序遍歷結果、輸出中序遍歷結果、輸出后序遍歷結果、交換左 右子樹、統(tǒng)計高度，其中對于中序、后序的遍歷運算要求采用非遞歸方式。 題目 9：創(chuàng)建 二叉排序樹（ 學時： 3）二叉排序樹以 lson-rson 鏈接方式存儲， 編寫能夠通過鍵盤輸入建立二叉排 序樹，并在建立完立即在屏幕顯示中序遍歷結果的程序。題目 10：霍夫曼編碼應用（學時：3）假設一串由大寫字母構成的電文， 采用霍夫曼規(guī)則對其進行編碼， 以菜單方 式設計并完成功能任務：建

5、立霍夫曼樹、霍夫曼編碼生成、編碼文件譯碼。#include<stdio.h>#include<string.h>#include<math.h>#define n 100#define m 2*n-1 typedef struct / 碼結點的存儲結構 char ch;char bits9;int len;CodeNode;typedef CodeNode HuffmanCoden+1;typedef struct / 樹結點的存儲結構int weight;int lchild,rchild,parent;HTNode;typedef HTNode Huff

6、manTreem+1; int num;void select(HuffmanTree HT,int k,int &s1,int &s2)/ 挑選權值最小的兩個結點 int i,j;int minl=32767; for(i=1;i<=k;i+)if(HTi.weight<minl&&HTi.parent=0)j=i; minl=HTi.weight;s1=j;minl=32767; for(i=1;i<=k;i+)if(HTi.weight<minl&&HTi.parent=0&&i!=s1)j=i; m

7、inl=HTi.weight;s2=j;int jsq(char *s,int cnt,char str)/ 統(tǒng)計輸入字符和串 char *p;int i,j,k=0;int temp257;for(i=0;i<257;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;/建立霍夫曼樹void chuffmanTree(HuffmanTree&HT,HuffmanCode&HC,int cn

8、t,char str) int i,s1,s2;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=cnti;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<=nu

9、m;i+)HCi.ch=stri;/給霍夫曼樹的每個葉子節(jié)點分配二進制代碼void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC)int c,p,i;char cdn; int start;cdnum='0'進制編碼串for(i=1;i<=num;i+)/1 到 num 為葉子節(jié)點，每個節(jié)點都有 start = num ;c=i;while(p=HTc.parent)>0)start-;cdstart=(HTp.lchild=c)?'0':'1'c=p;strcpy(HCi.bits,&a

10、mp;cdstart);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;i<num&&cjs=0&&receivep!='0'i+)cdi=' 'cdi+1='0'cdi=receivep+;for(j=1;j<=num;j+) if(strcmp

11、(HCj.bits,cd)=0) strk=HCj.ch; k+; cjs = 1; break; strk='0'strcpy(s,str);void coding(HuffmanCode HC,char str,char get)/ 輸出字符串的二進制編碼 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)計輸入序列中的字母時用，

12、存放是什么字char str257;符， 1 到 256char st10000,s10000; /st用來接收輸入的字符串，s用來接收解壓的字符串int cn257;/cn 用于接收統(tǒng)計后的每個字符的頻率， 1 到 256HuffmanTree HT;HuffmanCode HC;char ch='y'int d,i;printf(" 霍夫曼樹 nn");printf("1 .建立霍夫曼樹 .n");printf("2.生成霍夫曼編碼 .n");printf("3.編碼文件譯碼 .n");whil

13、e(ch='y') printf(" 請選擇 :"); scanf("%d",&d); switch(d) case 1:printf(" 輸入要編碼的字符串： "); scanf("%s",&st);num=jsq(st,cn,str);/統(tǒng)計文件中的字符 strnum+1 = '0'chuffmanTree(HT,HC,cn,str);printf(" 霍夫曼樹建立成功 !n");/ 建立霍夫曼樹break;case 2:HuffmanEnco

14、ding(HT,HC);/根據(jù)霍夫曼樹建立霍夫曼編碼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,st,get);printf("n 上述字符串的霍夫曼碼為 %sn",get);/ printf(" 編碼效率為 %f%n",code_ratio(st,

15、cn,HC);break;case 3:printf(" 輸入二進制碼開始譯碼： ");char receive10000;scanf("%s",&receive);decode(HC,receive,s);/ 譯碼printf(" 譯碼為： %sn",s);break;printf("n 是否繼續(xù)？ (y/n):");scanf("%c",&ch);scanf("%c",&ch);題目 11：關鍵路徑尋找(學時：6) 對于給定的一個工程施工圖，該圖以

16、邊為單位從鍵盤輸入，編寫能夠找出該圖的關鍵路徑的程序。#include"stdio.h"#include"stdlib.h"#define LEN sizeof(struct Enode)typedef struct Vexnode /頂點表int adjvex;/ 鄰接域int dut;/ 記錄權值struct Vexnode * next;vexnode;typedef struct Enodeint indegree;int vertex;int ee,el;struct Vexnode * link;/記錄入度/頂點/記錄最遲開始時間和最早結束時

17、間enode;void print(enode 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<top;i+) printf("->%d",listi); printf("n");while (q!=NULL) j=q->adjvex; if (di

18、gj.ee=digj.el) listtop=digj.vertex; print(dig,j,len);/ q=q->next;top-;/int toposort(enode dig,int e_n,int stacktp)/進棧int top=0,bottom=0,i,j,len=0; vexnode *q;for (i=1; i<=e_n; i+)if (digi.indegree=0)/入度為 0 則進棧stacktptop=i;/拓撲排序/入度 -/求一下最早開始/入度為 0 則進棧/ 表示沒有環(huán)/先初始化一下/棧非空/ 從最后的top+;len=top;while (

19、top>bottom)i=stacktpbottom;q=digi.link;bottom+;while (q!=NULL)j=q->adjvex; digj.indegree-; if (digi.ee+q->dut>digj.ee) 時間digj.ee=digi.ee+q->dut;if (digq->adjvex.indegree=0) stacktptop=q->adjvex; top+; q=q->next;if (top=e_n) 存在，則求出最遲結束時間for (i=1; i<=e_n; i+) digi.el=digstac

20、ktptop-1.ee; bottom=0;while (top>bottom)top-;一個事件開始倒推i=stacktptop;q=digi.link; while (q!=NULL) j=q->adjvex;if (digj.el-q->dut<digi.el) digi.el=digj.el-q->dut;q=q->next;for (i=0; i<len; i+) print(dig,stacktpi,i); return 0;else return 1;void main()enode dig20; / 頂點表數(shù)組 vexnode *q;/

21、鄰接點鏈表char ch;int e_n,v_n,m,i,j,u,v,stacktp20;printf(" 關鍵路徑 nn");printf(" 請輸入頂點個數(shù)和邊的條數(shù)： "); scanf("%d%d",&e_n,&v_n);for (i=1; i<=e_n; i+)/ 初始化digi.indegree=0; digi.link=NULL;digi.vertex=i; digi.ee=digi.el=0;printf(" 請輸入 %d 條邊以及該邊的權： n",v_n);for (i=0;

22、 i<v_n; i+)scanf("%d%d%d",&u,&v,&j); / 讀入各邊以及邊的權值q=malloc(LEN); digv.indegree+;q->adjvex=v;q->dut=j;q->next=digu.link;/ 將 q 結點 放入 u 鄰接鏈表中 digu.link=q;/將 q 結點 放入 u 鄰接鏈表中 m=toposort(dig,e_n,stacktp); /拓撲排序 if (m) printf(" 圖中存在環(huán)，不存在關鍵路徑 n");elseprintf("

23、需要各點明細查詢嗎 y/n"); scanf("n%c",&ch);if (ch='y'|ch='Y')for (i=0; i<e_n; i+)printf("%d (%d %d) n",stacktpi,digstacktpi.ee,digstacktpi.el);題目 12：堆排序實現(xiàn)(學時：3)假設有一個數(shù)據(jù)類型為整型的一維數(shù)組 A，A 中的數(shù)據(jù)元素呈無序狀態(tài)，編 寫一個采用堆排序法將 A 中的數(shù)據(jù)元素按由小到大進行排序的程序。 #include<stdio.h>#define M

24、AX 255int AMAX;void creatdui(int l,int m) /* 建初始堆過程函數(shù) */int i,j,x;i=l;j=2*i; /*Rj 是 Ri 的左孩子 */x=Ai;while(j<=m)if(j<m&&Aj<Aj+1)j+; /* 若左孩子較大，則把 j 修改為右孩子的下標 */ if(x<Aj)Ai=Aj; /* 將 Aj 調到父親的位置上 */i=j; /* 修改 i 和 j 的值，以便繼續(xù)向下篩選 */j=2*i;else j=m+1; /* 起結束作用 */Ai=x; /* 被篩結點的值存入最終的位置 */voi

25、d sortdui(int n)int i;int m;for(i=n/2;i>=1;i-) creatdui(i,n); /* 建立初始堆，遍布所有的根結點 */for(i=n;i>=2;i-)/* 進行 n-1 次循環(huán)完成堆排序 */m=Ai;Ai=A1; /* 將第一個元素同當前區(qū)域的最后一個元素對換 */A1=m; creatdui(1,i-1); /* 篩選 A1 結點，得到 i-1 個結點的堆，僅有 A1 可能違反堆性質 */void main()int i,n;printf(" 堆排序 nn");printf(" 輸入整型一維數(shù)組 A 中

26、數(shù)字總數(shù) :"); scanf("%d",&n);if(n<=0|n>MAX)printf("n 輸入的數(shù)據(jù)有誤 !");return;printf("n 請輸入整型無序序列 :n");for(i=1;i<=n;i+)scanf("%d",&Ai);printf("n 該序列為 :n");for(i=1;i<=n;i+)printf("%4d",Ai);sortdui(n);printf("n 堆排序后的序列為 :n

27、");for(i=1;i<=n;i+)printf("%4d",Ai);printf("n");題目 13基數(shù)排序的實現(xiàn)(學時：3)A為每個關鍵字不超過3位的十進制整數(shù)關鍵字集合，試編寫一個采用靜態(tài) 鏈表組織模式實現(xiàn)的基數(shù)排序程序將 A進行由小到大的排序。#include<stdio.h>#include <stdlib.h>#define N 1024int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)int* pnCount=(int

28、*)malloc(sizeof(int)* nMax);/保存計數(shù)的個數(shù)int i=0;for (i=0;i<nMax;+i) pnCounti=0;for (i=0;i<nLen;+i) / 初始化計數(shù)個數(shù)+pnCountnpIndexi;for (i=1; i<10;+i) /確定不大于該位置的個數(shù)。 pnCounti +=pnCounti-1;int * pnSort =(int*)malloc(sizeof(int) * nLen);/ 存放零時的排序結果。/注意：這里 i 是從 nLen-1 到 0 的順序排序的，是為了使排序穩(wěn)定。 for (i=nLen-1;i>=0;-i)-pnCountnpIndexi; pnSortpnCount