蘭州大學(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、department、 base pay、allowanc

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

3、有建立多項(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è)文本文件，每個(gè)單詞不包括空格及跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫(xiě)，完成以下功能：統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)、檢索輸出某單詞在文本文件中首次出現(xiàn)的行號(hào)及位置。題目8：二叉樹(shù)的

4、遍歷（學(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ù)，并在建立完立即在屏幕顯示中序遍歷結(jié)果的程序。題目10：霍夫曼編碼應(yīng)用（學(xué)時(shí)：3） 假設(shè)一串由大寫(xiě)字母構(gòu)成的電文，采用霍夫曼規(guī)則對(duì)其進(jìn)行編碼，以菜單方式設(shè)計(jì)并完成功能任務(wù)：建立霍夫曼樹(shù)、霍夫曼編碼生成、編碼文件譯碼。#include<stdio.h&g

5、t;#include<string.h>#include<math.h>#define n 100#define m 2*n-1typedef 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 lchild,rchild,parent;HTNode;typedef HTNode HuffmanTreem+1;int num;void select(HuffmanTree HT,

6、int k,int &s1,int &s2)/挑選權(quán)值最小的兩個(gè)結(jié)點(diǎn)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;minl=HTi.weight;s2=j;int jsq(char *s,int cnt,char str)

7、/統(tǒng)計(jì)輸入字符和串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;/建立霍夫曼樹(shù)void chuffmanTree(HuffmanTree&HT,HuffmanCode&HC,int cnt,char str) int i,s1,s2; for(i=1;i<=2*num-1;

8、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<=num;i+) HCi.ch=stri;/給霍夫曼樹(shù)的每個(gè)葉子節(jié)點(diǎn)分配二進(jìn)制代碼

9、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é)點(diǎn)，每個(gè)節(jié)點(diǎn)都有二進(jìn)制編碼串 start = num ; c=i; while(p=HTc.parent)>0) start-; cdstart=(HTp.lchild=c)?'0':'1'c=p; strcpy(HCi.bits,&cdstart); HCi.len=num-start

10、; 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(HCj.bits,cd)=0) str

11、k=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() char str257; /str用于在統(tǒng)計(jì)輸入序列中的字母時(shí)用，存

12、放是什么字符，1到256 char st10000,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&

13、#39;)printf("請(qǐng)選擇:"); scanf("%d",&d);switch(d)case 1: printf("輸入要編碼的字符串："); scanf("%s",&st); 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ù)霍

14、夫曼樹(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,st,get); printf("n上述字符串的霍夫曼碼為%sn",get); / printf("編碼效率為%f%n",code_ratio(st,cn,HC);break;case 3: prin

15、tf("輸入二進(jìn)制碼開(kāi)始譯碼："); 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：關(guān)鍵路徑尋找（學(xué)時(shí)：6）對(duì)于給定的一個(gè)工程施工圖，該圖以邊為單位從鍵盤(pán)輸入，編寫(xiě)能夠找出該圖的關(guān)鍵路徑的程序。#i

16、nclude"stdio.h"#include"stdlib.h"#define LEN sizeof(struct Enode)typedef struct Vexnode /頂點(diǎn)表int adjvex; /鄰接域int dut; /記錄權(quán)值struct Vexnode * next;vexnode;typedef struct Enodeint indegree; /記錄入度int vertex; /頂點(diǎn)int ee,el; /記錄最遲開(kāi)始時(shí)間和最早結(jié)束時(shí)間struct Vexnode * link;enode;void print(enode di

17、g,int first,int len)int i,j;static int top=0,list50;vexnode * q;i=first;q=digi.link;listtop=digi.vertex;top+; /進(jìn)棧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 (digj.ee=digj.el)listtop=dig

18、j.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則進(jìn)棧stacktptop=i;top+;len=top;while (top>bottom) /拓?fù)渑判騣=stacktpbottom;q=digi.link;bottom+;while (q!=NULL)j=q->adjv

19、ex;digj.indegree-; /入度-if (digi.ee+q->dut>digj.ee) /求一下最早開(kāi)始時(shí)間digj.ee=digi.ee+q->dut;if (digq->adjvex.indegree=0) /入度為0 則進(jìn)棧 stacktptop=q->adjvex; top+; q=q->next;if (top=e_n) /表示沒(méi)有環(huán)存在，則求出最遲結(jié)束時(shí)間for (i=1; i<=e_n; i+)digi.el=digstacktptop-1.ee; /先初始化一下bottom=0;while (top>bottom)

20、/棧非空top-; /從最后的一個(gè)事件開(kāi)始倒推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; /頂點(diǎn)表數(shù)組vexnode *q; /鄰接點(diǎn)鏈表char ch; int e_n,v_n,m,i,j,u,v,sta

21、cktp20;printf("-關(guān)鍵路徑-nn");printf("請(qǐng)輸入頂點(diǎn)個(gè)數(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("請(qǐng)輸入%d條邊以及該邊的權(quán)：n",v_n);for (i=0; i<v_n; i+)scanf("%d%d%d",&u,

22、&v,&j); /讀入各邊以及邊的權(quán)值q=malloc(LEN);digv.indegree+;q->adjvex=v;q->dut=j;q->next=digu.link;/將 q結(jié)點(diǎn) 放入u 鄰接鏈表中digu.link=q; /將 q結(jié)點(diǎn) 放入u 鄰接鏈表中m=toposort(dig,e_n,stacktp); /拓?fù)渑判騣f (m) printf("圖中存在環(huán)，不存在關(guān)鍵路徑n");elseprintf("需要各點(diǎn)明細(xì)查詢嗎y/n");scanf("n%c",&ch);if (ch=

23、'y'|ch='Y')for (i=0; i<e_n; i+)printf("%d (%d %d) n",stacktpi,digstacktpi.ee,digstacktpi.el);題目12：堆排序?qū)崿F(xiàn)（學(xué)時(shí)：3）假設(shè)有一個(gè)數(shù)據(jù)類(lèi)型為整型的一維數(shù)組A，A 中的數(shù)據(jù)元素呈無(wú)序狀態(tài)，編寫(xiě)一個(gè)采用堆排序法將A中的數(shù)據(jù)元素按由小到大進(jìn)行排序的程序。#include<stdio.h>#define MAX 255int AMAX;void creatdui(int l,int m) /*建初始堆過(guò)程函數(shù)*/ int i,j,x;

24、i=l; j=2*i; /*Rj是Ri的左孩子*/ x=Ai; while(j<=m) if(j<m&&Aj<Aj+1)j+; /*若左孩子較大，則把j修改為右孩子的下標(biāo)*/ if(x<Aj) Ai=Aj; /*將Aj調(diào)到父親的位置上*/ i=j; /*修改i和j的值，以便繼續(xù)向下篩選*/ j=2*i; else j=m+1; /*起結(jié)束作用*/ Ai=x; /*被篩結(jié)點(diǎn)的值存入最終的位置*/void sortdui(int n) int i; int m; for(i=n/2;i>=1;i-)creatdui(i,n); /*建立初始堆，遍布所有

25、的根結(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); /*篩選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",&n); if(n<=0|n>MAX) printf("n輸入的數(shù)據(jù)有誤!&q

26、uot;); return; printf("n請(qǐng)輸入整型無(wú)序序列: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"); for(i=1;i<=n;i+) printf("%4d",Ai); printf("n");題目13基數(shù)排序

27、的實(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ū)進(jìn)行由小到大的排序。#include<stdio.h>#include <stdlib.h>#define N 1024int 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;i<nMax;+i) pnCounti=0; for (i=0;i<nLen;+i) /初始化計(jì)數(shù)個(gè)數(shù) +pnCountnpIndexi; for (i=1; i<10;+i) /確定不大于該位置的個(gè)數(shù)。 pnCounti +=pnCounti-1; int * pnSort =(int*)malloc(sizeof(int) * nLen); /存放零時(shí)的排序結(jié)果。 /注意：這里i是從nLen-1到0的順序排序的，是為了使排序穩(wěn)定。 for (i=nLen-1;i>=0;-i) -pnCountnpIndexi; pnSortpnCountnpIndexi=npDatai; for (i=0;i<n