數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告二叉樹哈弗曼鏈表

1、北京xx大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(報告)院 （系）：計算機(jī)與信息工程學(xué)院班 級:軟件082學(xué) 號:xxxxxxx姓 名:xxxxxxx同組學(xué)生：_指導(dǎo)教師_成 績_實踐地點：_實踐時間：2010年5月1日至2010年5月20日二叉樹的操作：實驗?zāi)康模航⒍鏄洌⒑蟮南刃?。中序。后序。的遍歷，及輸出。思路：用遞歸的方法建立二叉樹，用先序建立，然后調(diào)整建立時左右孩子，和根結(jié)點的順序，就完成了，三種順序的遍歷。遇到的困難：在先序建立時忘記了用#符號表示該節(jié)點沒有孩子。如何解決的：用if(ch=#) t=null;語句解決。收獲：明白了，二叉樹的三種建立，和他們之間的區(qū)別以及遞歸的一些簡單的應(yīng)用。運行

2、結(jié)果：輸入數(shù)字元素用#表示結(jié)點沒有左孩子或右孩子。然后屏幕上顯示出三種順序的遍歷。#include#include#define null 0#define overflow -2#define ok 1typedef int status;typedef struct treenode char data; treenode *lchild,*rchild;*diaotree;status creat_tree(diaotree &t);status preorder_traversal(diaotree &t);status inorder_traversal(diaotree &t);s

3、tatus postorder_traverse(diaotree &t);void main() diaotree t; cout先序建立:;coutendl;cout輸入元素: ;creat_tree(t); cout先序遍歷: ;preorder_traversal(t); coutendl;cout中序遍歷: ;inorder_traversal(t); coutendl; cout后續(xù)遍歷: ;postorder_traverse(t); coutch; if(ch=#) t=null; else t=(diaotree)malloc(sizeof(treenode);if(!t)

4、exit(overflow); t-data=ch;creat_tree(t-lchild);creat_tree(t-rchild); return ok;status preorder_traversal(diaotree &t) if(t) coutdatalchild); preorder_traversal(t-rchild);return ok;status inorder_traversal(diaotree &t) if(t) inorder_traversal(t-lchild); coutdatarchild); return ok;status postorder_tra

5、verse(diaotree &t)if(t) postorder_traverse(t-lchild); postorder_traverse(t-rchild); coutdata ; return ok;哈夫曼編碼：實驗?zāi)康模航o出各節(jié)點權(quán)值的大小，然后建立哈弗曼樹，然后根據(jù)哈弗曼樹給對應(yīng)的權(quán)值生成對應(yīng)的不等長的二進(jìn)制編碼。思路：先輸入權(quán)值的個數(shù)，然后輸入權(quán)值的大小，再輸入對應(yīng)權(quán)值的英文字母，然后對每個結(jié)點的父親，左右孩子進(jìn)行初始化賦0，然后用select函數(shù)建立哈弗曼樹，然后存儲根據(jù)求出的哈弗曼表建立哈弗曼碼，選用左孩子為零右孩子為一，最后得出各個英文字母所對應(yīng)的不等長的二進(jìn)制編碼。遇到

6、的難點：如何編寫select選擇函數(shù)。如何解決的：先判斷所有結(jié)點的父親是否為零，然后把父親為零的權(quán)值放入一個新建立的int行數(shù)組中，然后在數(shù)組中進(jìn)行大小排序，先兩個樹是兩個權(quán)值最小的。然后再把原數(shù)組中兩個最小的權(quán)值的數(shù)組下標(biāo)給新的結(jié)點當(dāng)左右孩子，新節(jié)點就是這兩個節(jié)點的父親。收獲：了解了哈弗曼樹的建立，以及怎樣自己編寫select函數(shù)。運行結(jié)果：先輸入權(quán)值的個數(shù)，再輸入對應(yīng)權(quán)值的英文字母，再輸入對應(yīng)英文字母的權(quán)值的大小，會顯示各節(jié)點權(quán)值的大小，也就是哈弗曼樹的建立，在輸出各英文字母對應(yīng)的不等長的二進(jìn)制編碼 #include#include#include#include#define ok 1#

7、define overflow -1 #define null 0typedef struct diaochar data;int weight;int parent;int lchild;int rchild;diao,* dt;typedef char * *hc;int select(dt &tree,int i,int &m1,int &m2);void main()int n,m,i;cout請輸入權(quán)值的個數(shù)n;m=2*n-1;dt tree;tree=(dt)malloc(m+1)*sizeof(diao);cout請輸入英文字母endl;for(i=1;itreei.data;c

8、outendl;cout請輸入對應(yīng)權(quán)值的大小endl;for(i=1;ix;treei.weight=x;for(i=1;i=n;i+)treei.parent=0;static int s1,s2;for(i=n+1;i=m;i+) select(tree,i,s1,s2);trees1.parent=i;trees2.parent=i;treei.lchild=s1;treei.rchild=s2;treei.weight=trees1.weight+trees2.weight;treei.parent=0;cout各結(jié)點的權(quán)值endl;int h=0; for(h=1;h=m;h+)co

9、uttreeh.weight ; coutendl;hc diaocode;int start,c,f;diaocode=(hc)malloc(m+1)*sizeof(char *);char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=treei.parent;f!=0;c=f,f=treef.parent)if(treef.lchild=c) cd-start=0;else cd-start=1;diaocodei=(char *)malloc(n-start)*sizeof

10、(char);strcpy(diaocodei,&cdstart);free(cd);cout個英文字母的編碼為endl;for(i=1;i=n;i+)couttreei.data的編碼為diaocodeiendl;int select(dt &tree,int i,int &m1,int &m2)int t,m,temp;int p=0;for(t=0;ti-1;t+)if(treet+1.parent=0)p=p+1;int a100;int j=0;for(t=0;ti-1;t+)if(treet+1.parent=0)aj=treet+1.weight;j=j+1;for(t=0;t=

11、p-1;t+)for(m=t+1;mam)temp=at;at=am;am=temp;for(t=0;ti-1;t+)if(treet+1.weight=a0)&(treet+1.parent=0)break;m1=t+1;treet+1.parent=i; for(t=0;ti-1;t+)if(treet+1.weight=a1)&(treet+1.parent=0)break;m2=t+1;treet+1.parent=i;return ok;鏈表的操作：實驗?zāi)康模合冉捂湵?，然后進(jìn)行鏈表的添加，刪除操作，最后進(jìn)行約瑟夫環(huán)的形成。思路：用正序建立單鏈表，然后進(jìn)行添加，刪除，操作，在把單鏈

12、表改成循環(huán)鏈表，罪行約瑟夫環(huán)，我的約瑟夫環(huán)本質(zhì)上和遞歸類似。遇到的難點：如何建立約瑟夫環(huán)。怎么解決的：先把單鏈表變成循環(huán)鏈表，然后用while循環(huán)判斷元素是否為一個，當(dāng)不為一個時繼續(xù)循環(huán)，在while函數(shù)中有一個for循環(huán)次數(shù)為約瑟夫環(huán)要進(jìn)行到第幾個刪除的次數(shù)，在for循環(huán)后面加一個刪除函數(shù)來刪掉剛才循環(huán)倒的樹，知道最后剩一個。收獲：知道了單鏈表的建立，以及添加，刪除等操作，知道了怎樣把單鏈表變成循環(huán)鏈表，以及約瑟夫環(huán)的建立。運行結(jié)果：先輸入鏈表的長度，再輸入個元素的大小，顯示結(jié)果，愛輸入添加到第幾項，添加項的大小，顯示鏈表，再輸入要刪除第幾項，顯示結(jié)果。再輸入約瑟夫環(huán)中以幾為一個循環(huán)，也就是

13、數(shù)到幾殺人，然后顯示最后一個剩下的元素大小。#include#include#define ok 1 #define null 0#define overflow -1typedef struct diaoint data;struct diao *next;diao, * diaoinit;int diaolist(diaoinit &l,int n);int adddiao(diaoinit &l,int n,int e);int deletediao(diaoinit &l,int n);int delete2(diaoinit &l);void main()diaoinit l;int

14、 n;cout請輸入鏈表的長度n;cout請輸入各元素的大小next; int i;cout鏈表的結(jié)果為endl;for(i=0;in;i+)coutdatanext;coutendl;int x,e;cout請輸入添加第幾項x;cout請輸入添加數(shù)的大小e;adddiao(d,x,e);diaoinit m;m=d;d=d-next;cout鏈表的結(jié)果為endl;for(i=0;in+1;i+)coutdatanext;coutendl;cout請輸入刪除鏈表的第幾項o;deletediao(m,o);cout鏈表的結(jié)果為endl;for(i=0;in;i+)coutnext-datanex

15、t;cout約瑟夫環(huán)的循環(huán)數(shù)r;while(!(n=1)for(i=0;inext;delete2(m);n-;cout最后剩下的數(shù)字是endl;coutdata;int diaolist(diaoinit &l,int n)l=(diaoinit)malloc(sizeof(diao);l-next=null;diaoinit tail;tail=l;int i;diaoinit p;for(i=0;ip-data;tail-next=p;tail=p;tail-next=l-next;return ok;int adddiao(diaoinit &l,int n,int e)diaoini

16、t p;diaoinit s;s=(diaoinit)malloc(sizeof(diao);p=(diaoinit)malloc(sizeof(diao);s-next=null;s-data=e;p=l;int i;for(i=0;inext;s-next=p-next; p-next=s;return ok;int deletediao(diaoinit &l,int n)int x;diaoinit q;q=l;for(x=0;xnext;q-next=q-next-next;return ok ;int delete2(diaoinit &l)l-next=l-next-next;r

17、eturn ok;順序表的操作：實驗?zāi)康模喉樞虮淼慕?，以幾添加刪除的操作。思路：建立順序表。遇到的困難：再添加刪除早做事，經(jīng)常顯示沒有添加，lenght在添加，刪除后沒有進(jìn)行對應(yīng)的加或者減。解決的方法：對lenght進(jìn)行加或減。收獲：知道了順序表的建立，添加刪除操作，以幾必須改變lenght的值。運行結(jié)果：先輸入表長的大小，再輸入對應(yīng)各個數(shù)字，顯示結(jié)果，再輸入添加的位置，添加數(shù)的大小，顯示結(jié)果，再輸入刪除的位置，顯示結(jié)果。#include#include#define ok 1#define null 0#define overflow -1#define list_init_size 10

18、0#define increamlist 20typedef struct dingint *elem;int listsize;int length;diao;int initlist(diao &l);int addlist(diao &l,int m,int k);int deletelist(diao &l,int m);void main()cout順序表的操作endl;diao l;initlist(l);int i,n;cout請輸入數(shù)字的數(shù)量n;cout請輸入個數(shù)字的大小endl;for(i=0;il.elemi;cout顯示個數(shù)字的大小endl;for(i=0;in;i+)c

19、outl.elemi ;coutendl;l.length=n;cout請輸入加入數(shù)字的位置o;cout請輸入加入數(shù)字的大小u;addlist(l,o,u);cout各數(shù)字的大小為endl;for(i=0;in+1;i+)coutl.elemi ;l.length+;coutendl;cout請輸入刪除數(shù)字的位置m1;deletelist(l,m1);cout個數(shù)字的大小為endl;for(i=0;in;i+)coutl.elemi ; int initlist(diao &l)l.elem=(int *)malloc(list_init_size*sizeof(int);if(!l.elem

20、) exit(overflow);l.length=0;l.listsize=list_init_size;return ok ;int addlist(diao &l,int m,int k)if(ml.length+1) exit(overflow);if(l.length=l.listsize)int *newbase;newbase=(int *)realloc(l.elem,(l.listsize+increamlist)*sizeof(int);l.elem=newbase;l.listsize=l.listsize+increamlist;int *q,*p;q=&l.elemm

21、-1;for(p=&l.eleml.length-1;p=q;p-)*(p+1)=*p;*q=k;l.length+;return ok;int deletelist(diao &l,int m)if(ml.length+1) exit(overflow);int *p,*q;p=&l.elemm-1;q=&l.eleml.length-1;for(p+;pq;p+)*(p-1)=*p;return ok;無向圖鄰接表實驗?zāi)康模簾o向圖鄰接表的建立。思路：把每個頭結(jié)點的后面都鏈成用表結(jié)點做結(jié)點的鏈表。遇到的難點：如何把頭結(jié)點和表結(jié)點連起來。解決的方法：用頭結(jié)點中指向標(biāo)結(jié)點的指針指向表結(jié)點，然后表結(jié)點再指向頭結(jié)點，周而復(fù)始循環(huán)下去。收獲：明白了圖的建立，以及頭結(jié)點，表結(jié)點還之間的連接。運行結(jié)果：輸入頭結(jié)點的個數(shù)的大小，然后依次輸入節(jié)電元素的大小，輸入邊的個數(shù)，然后輸入各條邊的大小，如1 2, 3 4,算兩條邊。最后輸出的是每個結(jié)點后面鏈表元素的數(shù)組下標(biāo)#include#include#define maxvex 20#define ok 1#define null 0typedef struct arcnodeint dajvex;struct arcnode *nextarc;int weight;arcnode;typed