第一篇：數據結構實驗三哈夫曼樹實驗報告
實驗報告3：哈夫曼編/譯碼器
題目：哈夫曼編/譯碼器
一、題目要求：
寫一個哈夫曼碼的編/譯碼系統，要求能對要傳輸的報文進行編碼和解碼。構造哈夫曼樹時，權值小的放左子樹，權值大的放右子樹，編碼時右子樹編碼為1，左子樹編碼為0.二、概要設計：
數據結構：
typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 編碼結構體 */
typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 結點結構體 */ 函數：
void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n)作用：構造一個哈夫曼樹，并循環構建 int main()作用：運用已經構建好的哈弗曼樹，進行節點的處理，達到成功解碼編譯
三、詳細設計： 哈夫曼樹的建立：
void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n){
int i = 0, j, m1, m2, x1, x2;
char x;
/* 初始化存放哈夫曼樹數組 HuffNode[] 中的結點 */
while(i { HuffNode[i].weight = 0;//權值 實驗報告3：哈夫曼編/譯碼器 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; scanf(“%c”,&x); scanf(“%c”,&HuffNode[i].value);//實際值，可根據情況替換為字母 i++; } /* 輸入 n 個葉子結點的權值 */ scanf(“%c”,&x);for(i=0;i { scanf(“%d”, &HuffNode[i].weight); } for(i=n;i<2*n-1;i++) { HuffNode[i].weight = 0;//權值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; HuffNode[i].value=i; } /* 循環構造 Huffman 樹 */ for(i=0;i { m1=m2=MAXQZ; // m1、m2中存放兩個無父結點且結點權值最小的兩個結點 x1=x2=0;//找出所有結點中權值最小、無父結點的兩個結點，并合并之為一顆二叉樹 for(j=0;j { if(HuffNode[j].weight < m1 && HuffNode[j].parent==-1) { m2=m1;//m1中是最小 x2=x1; m1=HuffNode[j].weight; x1=j; } else if(HuffNode[j].weight < m2 && HuffNode[j].parent==-1) { m2=HuffNode[j].weight; x2=j; } 實驗報告3：哈夫曼編/譯碼器 } /* end for */ /* 設置找到的兩個子結點 x1、x2 的父結點信息 */ HuffNode[x1].parent = n+i; HuffNode[x2].parent = n+i; HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight; HuffNode[n+i].lchild = x1; HuffNode[n+i].rchild = x2; } } 葉子節點的哈夫曼編碼的保存： for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; 主函數展示： int main(){ HNode HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i, j, c, p, n,k=0; char wen[100]; char z; scanf(“%d”, &n); HuffmanTree(HuffNode, n); for(i=0;i < n;i++) { cd.start = n-1; c = i; p = HuffNode[c].parent; while(p!=-1) /* 父結點存在 */ { if(HuffNode[p].lchild == c) cd.bit[cd.start] = 0; else cd.bit[cd.start] = 1; cd.start--; /* 求編碼的低一位 */ c=p; p=HuffNode[c].parent; /* 設置下一循環條件 */ } /* end while */ 實驗報告3：哈夫曼編/譯碼器 for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; } /* end for */ z=getchar(); z=getchar(); for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);for(i=0;i { printf(“%c”,wen[i]); } printf(“n”); return 0;} 四、調試分析與心得體會： 雖然哈夫曼樹的建立有書上的參考，但是實際寫整個代碼的時候還是問題重重。首先就是哈弗曼樹忘記了初始的賦值，導致最后出現了問題。這樣的錯誤還是很容易解決，但是之后就出現了WA的情況。在同學的幫助下，最后發現是因為在選取節點的時候，循環出現了問題，雖然看起來編譯沒有錯，但是邊緣情況就會出現數據錯誤，這個還是很令人警醒，而這種思考的不全面的問題，在debug的過程中會耗去大量的時間，這是要注意的。 五、用戶操作說明： 輸入表示字符集大小為n（n <= 100）的正整數，以及n個字符和n個權值（正整數，值 越大表示該字符出現的概率越大）； 輸入串長小于或等于100的目標報文。實驗報告3：哈夫曼編/譯碼器 六、運行結果： 附帶自己的算法完成的結果圖，可以通過Prt Sc和圖片編輯器獲得； 實驗報告3：哈夫曼編/譯碼器 七、附錄： #include #define MAXBIT 100 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2-1 #define MAXQZ 10000 //權值 typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 編碼結構體 */ 實驗報告3：哈夫曼編/譯碼器 typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 結點結構體 */ /* 構造一顆哈夫曼樹 */ void HuffmanTree(HNode HuffNode[MAXNODE], int n){ int i = 0, j, m1, m2, x1, x2;char x;/* 初始化存放哈夫曼樹數組 HuffNode[] 中的結點 */ while(i scanf(“%c”,&x);scanf(“%c”,&HuffNode[i].value);//實際值，可根據情況替換為字母 i++;} /* 輸入 n 個葉子結點的權值 */ scanf(“%c”,&x);i = 0;while(i for(i=n;i<2*n-1;i++){ HuffNode[i].weight = 0;//權值 HuffNode[i].parent =-1;HuffNode[i].lchild =-1;HuffNode[i].rchild =-1;HuffNode[i].value=i;} 實驗報告3：哈夫曼編/譯碼器 /* 循環構造 Huffman 樹 */ for(i=0;i x1=x2=0;//找出所有結點中權值最小、無父結點的兩個結點，并合并之為一顆二叉樹 for(j=0;j } } int main(){ HNode HuffNode[MAXNODE];/* 定義一個結點結構體數組 */ HCodeType HuffCode[MAXLEAF],cd;/* 定義一個編碼結構體數組，同時定義一個臨時變量來存放求解編碼時的信息 */ int i, j, c, p, n,k=0;char wen[100];char z;scanf(“%d”, &n);HuffmanTree(HuffNode, n);8 3：哈夫曼編/譯碼器 for(i=0;i < n;i++){ cd.start = n-1;c = i;p = HuffNode[c].parent;while(p!=-1)/* 父結點存在 */ { if(HuffNode[p].lchild == c)cd.bit[cd.start] = 0;else cd.bit[cd.start] = 1;cd.start--;/* 求編碼的低一位 */ c=p;p=HuffNode[c].parent;/* 設置下一循環條件 */ } /* end while */ /* 保存求出的每個葉結點的哈夫曼編碼和編碼的起始位 */ for(j=cd.start+1;j z=getchar();z=getchar();for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);i = 0;while(i { printf(“%c”,wen[i]);實驗報告 實驗報告3：哈夫曼編/譯碼器 } printf(“n”);return 0;} ? i++; 實驗報告3：哈夫曼編/譯碼器 上機實習要求： 1、認真準備，按時參加上機實習，不得無故缺席，抽查不到者扣分； 2、獨立完成老師布置的題目，上機完成程序并調試正確，課后完成實驗報告的編寫，將上機程序和實驗報告打包后交給輔導老師評定分數，實驗報告要求和評分標準見后面； 3、提倡創新，可對課本上提供的算法進行改進； 4、上機程序必須在程序中提供足夠的注釋，詳細為好。 5、實驗報告不用寫出算法，只要寫出對課程設計的見解，如對某一算法的改進思想，算法設計思想，調試算法過程中出現的問題及改進方法，調試程序的體會等。只要是自己編程和調試就會寫出相應的報告。 考核標準 1、機試程序和結果、設計報告缺一不可，機試程序和結果壓縮打包后上交給輔導老師，設計報告主要是自己的設計過程和調試心得，報告中不必附帶全部的源程序）。機試成績占總成績60%，設計報告占40%。 2、上機程序和設計報告必須獨立完成，嚴禁抄襲，若發現雷同，原創者視上機結果最多60分，抄襲者按0分計，若找不到原創，都按0分計。 所以原創同學注意，我們的檢查專門針對抄襲情況，一旦發現將嚴肅處理！！ 題目：哈夫曼編/譯碼器 一、題目要求： 寫一個哈夫曼碼的編/譯碼系統，要求能對要傳輸的報文進行編碼和解碼。構造哈夫曼樹時，權值小的放左子樹，權值大的放右子樹，編碼時右子樹編碼為1，左子樹編碼為0.二、概要設計： 數據結構： typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 編碼結構體 */ typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 結點結構體 */ 函數： void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n)作用：構造一個哈夫曼樹，并循環構建 int main()作用：運用已經構建好的哈弗曼樹，進行節點的處理，達到成功解碼編譯 三、詳細設計： 哈夫曼樹的建立： void DEMONHuffmanTree(HNode HuffNode[MAXNODE], int n){ int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼樹數組 HuffNode[] 中的結點 */ while(i { HuffNode[i].weight = 0;//權值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; scanf(“%c”,&x); scanf(“%c”,&HuffNode[i].value);//實際值，可根據情況替換為字母 i++; } /* 輸入 n 個葉子結點的權值 */ scanf(“%c”,&x);for(i=0;i { scanf(“%d”, &HuffNode[i].weight); } for(i=n;i<2*n-1;i++) { HuffNode[i].weight = 0;//權值 HuffNode[i].parent =-1; HuffNode[i].lchild =-1; HuffNode[i].rchild =-1; HuffNode[i].value=i; } /* 循環構造 Huffman 樹 */ for(i=0;i { m1=m2=MAXQZ; // m1、m2中存放兩個無父結點且結點權值最小的兩個結點 x1=x2=0;//找出所有結點中權值最小、無父結點的兩個結點，并合并之為一顆二叉樹 for(j=0;j { if(HuffNode[j].weight < m1 && HuffNode[j].parent==-1) { m2=m1;//m1中是最小 x2=x1; m1=HuffNode[j].weight; x1=j; } else if(HuffNode[j].weight < m2 && HuffNode[j].parent==-1) { m2=HuffNode[j].weight; x2=j; } } /* end for */ /* 設置找到的兩個子結點 x1、x2 的父結點信息 */ HuffNode[x1].parent = n+i; HuffNode[x2].parent = n+i; HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight; HuffNode[n+i].lchild = x1; HuffNode[n+i].rchild = x2; } } 葉子節點的哈夫曼編碼的保存： for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; 主函數展示： int main(){ HNode HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i, j, c, p, n,k=0; char wen[100]; char z; scanf(“%d”, &n); HuffmanTree(HuffNode, n); for(i=0;i < n;i++) { cd.start = n-1; c = i; p = HuffNode[c].parent; while(p!=-1) /* 父結點存在 */ { if(HuffNode[p].lchild == c) cd.bit[cd.start] = 0; else cd.bit[cd.start] = 1; cd.start--; /* 求編碼的低一位 */ c=p; p=HuffNode[c].parent; /* 設置下一循環條件 */ } /* end while */ for(j=cd.start+1;j HuffCode[i].bit[j] = cd.bit[j]; HuffCode[i].start = cd.start; } /* end for */ z=getchar(); z=getchar(); for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);for(i=0;i { printf(“%c”,wen[i]); } printf(“n”); return 0;} 四、調試分析與心得體會： 雖然哈夫曼樹的建立有書上的參考，但是實際寫整個代碼的時候還是問題重重。首先就是哈弗曼樹忘記了初始的賦值，導致最后出現了問題。這樣的錯誤還是很容易解決，但是之后就出現了WA的情況。在同學的幫助下，最后發現是因為在選取節點的時候，循環出現了問題，雖然看起來編譯沒有錯，但是邊緣情況就會出現數據錯誤，這個還是很令人警醒，而這種思考的不全面的問題，在debug的過程中會耗去大量的時間，這是要注意的。 五、用戶操作說明： 輸入表示字符集大小為n（n <= 100）的正整數，以及n個字符和n個權值（正整數，值 越大表示該字符出現的概率越大）； 輸入串長小于或等于100的目標報文。 六、運行結果： 附帶自己的算法完成的結果圖，可以通過Prt Sc和圖片編輯器獲得； 七、附錄： #include #define MAXBIT 100 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2-1 #define MAXQZ 10000 //權值 typedef struct { int bit[MAXBIT];int start;} HCodeType;/* 編碼結構體 */ typedef struct { int weight;int parent;int lchild;int rchild;char value;} HNode;/* 結點結構體 */ /* 構造一顆哈夫曼樹 */ void HuffmanTree(HNode HuffNode[MAXNODE], int n){ int i = 0, j, m1, m2, x1, x2;char x;/* 初始化存放哈夫曼樹數組 HuffNode[] 中的結點 */ while(i scanf(“%c”,&x);scanf(“%c”,&HuffNode[i].value);//實際值，可根據情況替換為字母 i++;} /* 輸入 n 個葉子結點的權值 */ scanf(“%c”,&x);i = 0;while(i for(i=n;i<2*n-1;i++){ HuffNode[i].weight = 0;//權值 HuffNode[i].parent =-1;HuffNode[i].lchild =-1;HuffNode[i].rchild =-1;HuffNode[i].value=i;} /* 循環構造 Huffman 樹 */ for(i=0;i x1=x2=0;//找出所有結點中權值最小、無父結點的兩個結點，并合并之為一顆二叉樹 for(j=0;j } } int main(){ HNode HuffNode[MAXNODE];/* 定義一個結點結構體數組 */ HCodeType HuffCode[MAXLEAF],cd;/* 定義一個編碼結構體數組，同時定義一個臨時變量來存放求解編碼時的信息 */ int i, j, c, p, n,k=0;char wen[100];char z;scanf(“%d”, &n);HuffmanTree(HuffNode, n);8 for(i=0;i < n;i++){ cd.start = n-1;c = i;p = HuffNode[c].parent;while(p!=-1)/* 父結點存在 */ { if(HuffNode[p].lchild == c)cd.bit[cd.start] = 0;else cd.bit[cd.start] = 1;cd.start--;/* 求編碼的低一位 */ c=p;p=HuffNode[c].parent;/* 設置下一循環條件 */ } /* end while */ /* 保存求出的每個葉結點的哈夫曼編碼和編碼的起始位 */ for(j=cd.start+1;j z=getchar();z=getchar();for(;z!='n';z=getchar()){ wen[k++]=z; for(i=0;i { if(z==HuffNode[i].value) { for(j=HuffCode[i].start+1;j < n;j++) printf(“%d”, HuffCode[i].bit[j]); break; } else; } } printf(“n”);i = 0;while(i { printf(“%c”,wen[i]); } printf(“n”);return 0;} ? i++; 上機實習要求： 1、認真準備，按時參加上機實習，不得無故缺席，抽查不到者扣分； 2、獨立完成老師布置的題目，上機完成程序并調試正確，課后完成實驗報告的編寫，將上機程序和實驗報告打包后交給輔導老師評定分數，實驗報告要求和評分標準見后面； 3、提倡創新，可對課本上提供的算法進行改進； 4、上機程序必須在程序中提供足夠的注釋，詳細為好。 5、實驗報告不用寫出算法，只要寫出對課程設計的見解，如對某一算法的改進思想，算法設計思想，調試算法過程中出現的問題及改進方法，調試程序的體會等。只要是自己編程和調試就會寫出相應的報告。 考核標準 1、機試程序和結果、設計報告缺一不可，機試程序和結果壓縮打包后上交給輔導老師，設計報告主要是自己的設計過程和調試心得，報告中不必附帶全部的源程序）。機試成績占總成績60%，設計報告占40%。 2、上機程序和設計報告必須獨立完成，嚴禁抄襲，若發現雷同，原創者視上機結果最多60分，抄襲者按0分計，若找不到原創，都按0分計。 所以原創同學注意，我們的檢查專門針對抄襲情況，一旦發現將嚴肅處理！！ 樹和哈夫曼樹實驗報告 一．實驗目的 練習樹和哈夫曼樹的有關操作，和各個算法程序，理解哈夫曼樹的編碼和譯碼 二．實驗環境 Microsoft visual c++ 三．實驗問題描述 1.問題描述：建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序、中序和后序），打印輸出遍歷結果。 基本要求：從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），并將此二叉樹按照“樹狀形式”打印輸出，然后對其進行遍歷（先序、中序和后序），最后將遍歷結果打印輸出。在遍歷算法中要求至少有一種遍歷采用非遞歸方法。測試數據： ABC??DE?G??F???（其中?表示空格字符）輸出結果為： 先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2.問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接受端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/譯碼系統。基本要求：(至少完成功能1-2）一個完整的系統應具有以下功能： I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。基本要求： E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。 D：譯碼（Decoding)。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。 P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。T：印哈夫曼樹（TreePrinting）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。測試數據： 設權值w=（5，29，7，8，14，23，3，11），n=8。 按照字符‘0’或‘1’確定找左孩子或右孩子，則權值對應的編碼為： 5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001 用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。四．實驗主要程序流 實驗題目一主要程序： 1．void CreatBiTree(BitTree *bt)//用擴展先序遍歷序列創建二叉樹，如果是#當前樹根置為空，否則申請一個新節點// { char ch;ch=getchar();if(ch=='.')*bt=NULL;else { *bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));} } 2．void Visit(char ch)//訪問根節點 { printf(“%c ”,ch);} 3． void PreOrder(BitTree root){ if(root!=NULL){ Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);} } 4． void InOrder(BitTree root){ if(root!=NULL){ InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);} } 5．int PostTreeDepth(BitTree bt)//后序遍歷求二叉樹的高度遞歸算法// { int hl,hr,max;if(bt!=NULL){ hl=PostTreeDepth(bt->LChild);//求左子樹的深度 hr=PostTreeDepth(bt->RChild);//求右子樹的深度 max=hl>hr?hl:hr;//得到左、右子樹深度較大者 return(max+1);//返回樹的深度 } else return(0);//如果是空樹，則返回0 } 6．void PrintTree(BitTree Boot,int nLayer)//按豎向樹狀打印的二叉樹 // { int i;if(Boot==NULL)return;PrintTree(Boot->RChild,nLayer+1);for(i=0;i // 函數功能：建立哈夫曼樹（調用鍵盤建立哈夫曼樹或調用從文件建立哈夫曼樹的函數）void HuffmanTree::CreateHuffmanTree(){char Choose;cout<<“你要從文件中讀入哈夫曼樹(按1)，還是從鍵盤輸入哈夫曼樹(按2)？”;cin>>Choose;if(Choose=='2'){ //鍵盤輸入建立哈夫曼樹 CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹 CreateHuffmanTreeFromFile();} } 3.// 從鍵盤建立哈夫曼樹函數 // 函數功能：從鍵盤建立哈夫曼樹 //函數參數：無 //參數返回值：無 void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num;cout<<“n請輸入源碼字符集個數：”;cin>>Num;if(Num<=1){ cout<<“無法建立少于2個葉子結點的哈夫曼樹。nn”;return;} LeafNum=Num;Node=new HuffmanNode[2*Num-1];for(int i=0;i cout<<“請輸入第”<第二篇：數據結構實驗三哈夫曼樹實驗報告
第三篇：樹和哈夫曼樹實驗報告