北京科技大學(xué)數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告(附錄含代碼)匯編

1、學(xué)習(xí)-好資料1）功能描述輸入數(shù)據(jù)（設(shè)為整型）建立單鏈表，并求相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)。2）詳細(xì)設(shè)計(jì)遵循鏈表建立的基本思想，建立一個(gè)新的鏈表，H為表頭，r為新節(jié)點(diǎn)，p為表尾節(jié)點(diǎn)指針，沒(méi)存入一個(gè)新的數(shù)據(jù)則申請(qǐng)一個(gè)新的節(jié)點(diǎn)，知道沒(méi)有數(shù)據(jù)輸入， 利用循環(huán)和打擂臺(tái)法，比較和的大小，并輸出。3）測(cè)試分析程序調(diào)試完成后，選取兩組數(shù)據(jù)進(jìn)行測(cè)試，都得出了正確結(jié)果（數(shù)據(jù)以0為結(jié)束符，若有相同和，則取第一組）結(jié)果截圖4）心得體會(huì)通過(guò)做第一題，學(xué)習(xí)到鏈表的建立以及鏈表里指針的使用，并且復(fù)習(xí)了比較法里面的打 擂臺(tái)法。1）功能描述實(shí)現(xiàn)算術(shù)表達(dá)式求值程序（棧的運(yùn)用），輸入中綴表達(dá)式，可將其轉(zhuǎn)換成后綴表達(dá)式2

2、）詳細(xì)設(shè)計(jì)本題目的程序是根據(jù)課本上的程序改進(jìn)之后得出的，課本上有完整的程序，但是有bug,按照課本上的程序，結(jié)果會(huì)出現(xiàn)“燙燙燙燙燙”，原因是對(duì)于優(yōu)先級(jí)的比較沒(méi)有處理好， 因此加了兩行代碼，將優(yōu)先級(jí)的比較處理好，即現(xiàn)在的程序。3）測(cè)試分析程序調(diào)試完成后，選取題目所給的式子進(jìn)行測(cè)試，得出了正確后綴表達(dá)式結(jié)果結(jié)果截圖4）心得體會(huì)通過(guò)做第二題，對(duì)于課本上的知識(shí)表示得出“實(shí)踐出真知”的真理，即使書(shū)上的東西也 不一定就是正確的，尤其是代碼，最好是個(gè)人自己真正實(shí)踐一下。1）功能描述實(shí)現(xiàn)鏈?zhǔn)疥?duì)列運(yùn)算程序（隊(duì)列的運(yùn)用）2）詳細(xì)設(shè)計(jì)本題目是隊(duì)列相關(guān)應(yīng)用，隊(duì)列和棧是相反的，隊(duì)列是先進(jìn)的先出，因此輸入12345，先出

3、的是1，本著隊(duì)列的這一特性，根據(jù)課本所學(xué)的隊(duì)列的算法，設(shè)計(jì)了如下程序。3）測(cè)試分析程序調(diào)試完成后，選取 12345進(jìn)行測(cè)試，后綴加 0,則一個(gè)字符出隊(duì)，只輸入0,則繼續(xù)出隊(duì)，輸入 ，則打印剩余全部元素。結(jié)果截圖4）心得體會(huì)通過(guò)做第三題，對(duì)于隊(duì)列的特點(diǎn)有了更加深刻的認(rèn)識(shí)，尤其區(qū)分隊(duì)列與棧的不同點(diǎn)，需要特別注意。四、1）功能描述 構(gòu)造關(guān)于F的Huffman樹(shù)； 求出并打印 D總各字符的Huffman編碼。2）詳細(xì)設(shè)計(jì)本題目是Huffman樹(shù)的應(yīng)用以及 Huffman編碼的應(yīng)用，參照課本上關(guān)于Huffman樹(shù)的建立以及Huffman編碼的應(yīng)用的實(shí)現(xiàn)，將所給數(shù)據(jù)依權(quán)值最小原則建立Huffman樹(shù)，并實(shí)

4、現(xiàn)Huffman編碼。3）測(cè)試分析程序調(diào)試完成后，給出數(shù)據(jù)abcdefgh，相應(yīng)頻率為12345678，運(yùn)行代碼得出結(jié)果如圖。 同時(shí)選取另一組數(shù)據(jù)測(cè)試也得出了正確結(jié)論結(jié)果截圖11110 Hill 111B10111B 03 (dl1111U 111Q ±iil± 100 囲 110 ei碼為祠為Con tin lie? 清輸厶電w'符集：ttbcdcTg)!電文宇符集含尊個(gè)字符，連續(xù)輸入不同頻率之闔隔卄請(qǐng)輸入宇符岀現(xiàn)* wJ PHlnf frii 怙的HuFf4BuFf4 » 的 Huffiti m的HuM胡 十的luFf4Comtinue? ¥

5、/NaJ ffiluFf 為: b*的HuF£m離碼為: c '的HuFfm遍碼為: (T的HU土伽編碼為: eJ的HuFfm繼碼為: f *的Huff m遍碼為= 3* ffilurfwaS碼為: W的HuFfm編碼為:V/N y4）心得體會(huì)通過(guò)做第四題，對(duì)于Huffman樹(shù)有了更加深刻的體會(huì)，同時(shí)練習(xí)也使得對(duì)課本知識(shí)進(jìn)行實(shí)踐，有助于更好的理解Huffman樹(shù)的算法。五、1）功能描述設(shè)英文句子： “ every one round you can hear you whe n you speak. ”（1）依次讀入句中各單詞，構(gòu)造一棵二叉排序樹(shù)；（2）按LDR遍歷此二叉排序

6、樹(shù)。LDR： can every one hear round speak whe n you （有序）2）詳細(xì)設(shè)計(jì)本題目是有關(guān)二叉樹(shù)的建立和中序遍歷的，二叉樹(shù)作為數(shù)據(jù)存儲(chǔ)一個(gè)很重要的結(jié)構(gòu)，它的建立也是很重要的。本題目代碼設(shè)計(jì)上采用課本上的對(duì)于二叉樹(shù)建立的方法，將所給單詞以二叉樹(shù)形式建立并存儲(chǔ)，然后中序遍歷的到字典順序。3)測(cè)試分析程序調(diào)試完成后，給出單詞串every one round you can hear you whe n you speak，運(yùn)行代碼得出中序遍歷結(jié)果如圖。結(jié)果截圖4)心得體會(huì)通過(guò)做第五題，練習(xí)運(yùn)用二叉樹(shù)模型解決了一些實(shí)際問(wèn)題如現(xiàn)實(shí)中字典的編排問(wèn)題，在熟悉算法的基礎(chǔ)上

7、，同時(shí)得出結(jié)論，好的算法可以應(yīng)用與實(shí)際生活生產(chǎn)，使之更為便捷。附錄程序代碼實(shí)驗(yàn)一：#i nclude"stdio.h"#i nclude"malloc.h"typedef struct nodeint data;struct node *n ext;list,*List;List Creatlist() /建立鏈表函數(shù)List H,p,r; H為表頭，r為新節(jié)點(diǎn)，p為表尾節(jié)點(diǎn)指針H=(List)malloc(sizeof(list);/ 建立頭節(jié)點(diǎn)r=H;p=(List)malloc(sizeof(list);/ 申請(qǐng)新節(jié)點(diǎn)while(scanf(&qu

8、ot;%d",p)&&p->data!=0)/ 輸入數(shù)據(jù)，直到為零(結(jié)束標(biāo)志)r->next=p; /新節(jié)點(diǎn)鏈入表尾r=p;p=(List)malloc(sizeof(list);更多精品文檔學(xué)習(xí) 好資料r->next=NULL; / 將尾節(jié)點(diǎn)的指針域置空return H; / 返回已創(chuàng)建的頭節(jié)點(diǎn)List Adjmax(List H) / 比較相鄰兩數(shù)之和 / 返回相鄰兩數(shù)之和最大的第一個(gè)數(shù)指針List p,r,q;int sum=0;p=H->next;if(H->next =NULL) / 判斷是否為空printf("Emp

9、ty List!");q=(List)malloc(sizeof(list);q->data =0;while(p!=NULL) / 比較相鄰兩數(shù)之和r=p->next ;if(p&&r)if(r->data+p->data>sum)q=p;sum=r->data +p->data ;/ 不斷賦給 sum 新的最大值 else;p=p->next ;return q;int main()char ch;printf("/ 請(qǐng)輸入整形數(shù)據(jù)，以空格隔開(kāi)， 0 結(jié)束。 / n"); printf("

10、;Ready? nY/N (enter 'y' or 'Y' to continue) n"); while(scanf("%c",&ch)&&(ch='Y'|ch='y')List H,pmax;H=Creatlist();pmax=Adjmax(H);",pmax->data );printf(" 相鄰兩數(shù)之和最大的第一個(gè)數(shù)為： %dnContinue? Y/N free(H);scanf("%c",&ch);retur

11、n 0;實(shí)驗(yàn)二：#include<stdio.h>#include<malloc.h>#include<conio.h>typedef struct node / 棧節(jié)點(diǎn)類型char data; / 存儲(chǔ)一個(gè)棧元素struct node *next; / 后繼指針snode,*slink;int Emptystack(slink S) / 檢測(cè)棧空if(S=NULL) return(1);else return(0);char Pop(slink*top) / 出棧char e;slink p;if(Emptystack(*top) return(-1);

12、/ ?？辗祷豦lsee=(*top)->data; / 取棧頂元素p=*top; *top=(*top)->next; / 重置棧頂指針 free(p);return(e);void Push(slink*top,char e) / 進(jìn)棧slink p;p=(slink)malloc(sizeof(snode); / 生成進(jìn)棧 p 節(jié)點(diǎn) p->data=e; / 存入元素 ep->next=*top; /p 節(jié)點(diǎn)作為新的棧頂鏈入*top=p;void Clearstack(slink*top) / 置空棧slink p;while(*top!=NULL)p=(*top)

13、->next;Pop(top); / 依次彈出節(jié)點(diǎn)直到?？?top=p;*top=NULL;char Getstop(slink S) / 取棧頂 if(S!=NULL)return(S->data); return(0);/ 符號(hào)優(yōu)先級(jí)比較int Precede(char x,char y) / 比較 x 是否 " 大于 "yswitch(x)case '(':x=0;break;case '+':case '-':x=1;break;case '/':x=2;break; default: x=

14、-1; switch(y)case '+':case '-':y=1;break;case '*':case '/':y=2;break;case '(':y=3;break;default: y=100;if (x>=y)return(1);else return(0);/ 中后序轉(zhuǎn)換post 的轉(zhuǎn)換的算法void mid_post(char post,char mid)/ 中綴表達(dá)式 mid 到后綴表達(dá)式 int i=0,j=0;char x;sli nk S=NULL; 置空棧Push(&S,&

15、#39;#');結(jié)束符入棧dox=midi+;/ 掃描當(dāng)前表達(dá)式分量 xswitch(x) case '#': while(!Emptystack(S) postj+=Pop(&S);break;case ')': while(Getstop(S)!='(') postj+=Pop(&S);/ 反復(fù)出棧直至遇到 '( ' Pop(&S); 退掉(break;case '+':case '-': case '/':case1*1.case '(&

16、#39;: while(Precede(Getstop(S),x) 棧頂運(yùn)算符(Q1)與 x 比較 postj+=Pop(&S);/Q1>=x 時(shí)，輸出棧頂符并退棧Push(&S,x);/Q1<x 時(shí) x進(jìn)棧break;default:postj+=x;/ 操作數(shù)直接輸出while(x!='#');postj='0'/ 后綴表達(dá)式求值int postcount(char post)/ 后綴表達(dá)式 post 求值的算法int i=0;char x;float z,a,b;sli nk S=NULL; 置?？誻hile (posti!=&

17、#39;#') x=posti;/ 掃描每一個(gè)字符送 xswitch(x)case '+':b=Pop(&S);a=Pop(&S);z=a+b;Push(&S,z);break;case '-':b=Pop(&S);a=Pop(&S);z=a-b;Push(&S,z);break;case '*':b=Pop(&S);a=Pop(&S);z=a*b;Push(&S,z);break;case '/':b=Pop(&S);a=Pop(&S

18、);z=a/b;Push(&S,z);break;/ 執(zhí)行相應(yīng)運(yùn)算結(jié)果進(jìn)棧 default:x=posti-'0'Push(&S,x);/ 操作數(shù)直接進(jìn)棧i+;if (!Emptystack(S)return(Getstop(S);/ 返回結(jié)果void main()char post255,mid255=""printf(" 請(qǐng)輸入要處理的中綴表達(dá)式： n");scanf("%s",mid);printf(" 相應(yīng)的后綴表達(dá)式為： n");mid_post(post,mid);pri

19、ntf("%sn",post);printf(" 表達(dá)式的值為： %dn",postcount(post); getch();實(shí)驗(yàn)三：#include"stdio.h"#include"malloc.h"#define max 1000typedef struct nodechar chmax;int front,rear;squeue,*sq;void Clearqueue(sq Q)Q->front=Q->rear;int Emptyqueue(sq Q) if(Q->rear=Q->f

20、ront) return 1;elsereturn 0;void Enqueue(sq Q,char ch)if(Q->rear>=max)printf("FULL QUEUE!");elseQ->ch Q->rear=ch;Q->rear +;void Dequeue(sq Q)if(Emptyqueue(Q)printf("Empty QUEUE!n");elseprintf(" 出隊(duì)： %cn",Q->chQ->front);Q->front +;void Printqueue(s

21、q Q)if(Emptyqueue(Q)elseprintf(" 隊(duì)列中全部元素： n");while(Q->front!=Q->rear-1)printf("%c",Q->chQ->front); Q->front+;printf("n");int main()sq Queue;char f;printf(*n");printf（”請(qǐng)輸入字符 XnX工'并且 X豐'字符入隊(duì)；n”）;printf("X='0', 字符出隊(duì)； n"); prin

22、tf("X='', 打印隊(duì)列中各元素。 n");更多精品文檔printf(“*n");Queue=(sq)malloc(sizeof(squeue);Queue->front =Queue->rear=0;while(scanf("%c",&f)&&f!='')if(f!='0')Enqueue(Queue,f);elseDequeue(Queue);if(f='')Printqueue(Queue); else;return 0;實(shí)驗(yàn)四：#in

23、clude"stdio.h" #include"malloc.h" #define N 8 #define MAX 100 #define M 2*N-1 typedef struct char letter; int w;int parent,lchild,rchild;Huffm; typedef struct char bitsN+1; int start; char ch;ctype;void inputHT(Huffm HTM+1) int i; for(i=1;i<=M;i+)HTi.w=0; HTi.parent=0; HTi.lch

24、ild=0; HTi.rchild=0;printf(" 請(qǐng)輸入電文字符集： "); for(i=1;i<=N;i+)scanf("%c",&HTi.letter );printf(" 請(qǐng)輸入字符出現(xiàn)的頻率： "); for(i=1;i<=N;i+)scanf("%d",&HTi.w ); void CreatHT(Huffm HTM+1)int i,j,min1,min2;int tag1,tag2; / 權(quán)值最小兩個(gè)點(diǎn)標(biāo)號(hào)； for(i=N+1;i<=M;i+)tag1=tag

25、2=0;min1=min2=MAX;for(j=1;j<=i-1;j+)if(HTj.parent =0)if(HTj.w <min1) min2=min1; min1=HTj.w; tag2=tag1; tag1=j;elseif(HTj.w <min2) min2=HTj.w; tag2=j;HTtag1.parent =HTtag2.parent =i;HTi.lchild =tag1;HTi.rchild =tag2;HTi.w =HTtag1.w +HTtag2.w;void Huffmcode(Huffm HTM+1) / Huffm 編碼函數(shù) int i,j,p

26、,tag;ctype mcode,codeN+1;for(i=1;i<=N;i+)codei.ch=HTi.letter;for(i=1;i<=N;i+)mcode.ch =codei.ch;mcode.start=N+1;tag=i;p=HTi.parent ;for(j=0;j<=N;j+)mcode.bits j=' 'while(p!=0)mcode.start-;if(HTp.lchild =tag)mcode.bitsmcode.start ='0' elsemcode.bits mcode.start ='1'ta

27、g=p;p=HTp.parent ;codei=mcode;for(i=1;i<=N;i+)printf(" '%c' 的 Huffm 編碼為： ",codei.ch ); for(j=0;j<=N;j+) printf("%c",codei.bits j);printf("n");int main()char ch;printf("*n");n");printf("*n");printf(" 電文字符集含 8 個(gè)字符，連續(xù)輸入，不同頻率之間以空格

28、隔開(kāi)ch='y'while(ch='y')Huffm HTM+1; inputHT(HT);CreatHT(HT);Huffmcode(HT); printf("Continue? Y/N "); fflush(stdin);scanf("%c",&ch); fflush(stdin);實(shí)驗(yàn)五：#include"stdio.h"#include"malloc.h"#include"string.h" typedef struct bsnode char word20;struct bsnode *lchild,*rchild;BStree,*BST;BST BST