電子科技大學軟件技術基礎實驗報告4

1、電子科技大學 通信與信息工程 學院標 準 實 驗 報 告（實驗）課程名稱 軟件技術基礎實驗 電子科技大學教務處制表電 子 科 技 大 學實 驗 報 告一、實驗室名稱：校公共機房 二、實驗項目名稱：二叉樹和哈夫曼樹三、實驗學時：4學時四、實驗原理：使用VS2010等C語言集成開發(fā)環(huán)境（IDE），在微型計算機上對程序進行編輯、編譯、連接與運行。通過上機練習掌握二叉樹的建立、插入刪除，遍歷等方法和過程，掌握遞歸函數在二叉樹建立，遍歷中的應用，掌握哈夫曼樹的最小路徑和建立過程。五、實驗目的：1. 熟練二叉樹和哈夫曼樹的概念和基本操作方法。2. 掌握課程平臺使用方法。六、實驗內容：上機完成所有函數，編程

2、實驗，調試運行程序并完成報告。七、實驗器材（設備、元器件）：硬件要求：普通pc機，1G內存，100G硬盤空間即可。 軟件要求：Windows 7，包括C編譯器的IDE。八、實驗步驟、實驗編程與運行結果：下面建立該二叉樹并展示輸出結果：#include<stdio.h>#include<stdlib.h>typedef struct bnode int data; struct bnode *lc,*rc;struct bnode* create() struct bnode *tree=NULL; char ch; ch=getchar(); if(ch='_&

3、#39;) tree=NULL; else tree=(struct bnode *)malloc(sizeof(struct bnode); tree->data=ch; tree->lc=create(); tree->rc=create(); return tree;/先序遍歷（根左右）-遞歸int preorder(struct bnode *root) putchar(root->data); if(root->lc!=NULL) preorder(root->lc); if(root->rc!=NULL) preorder(root->

4、;rc);/中序遍歷-遞歸int inorder(struct bnode *root) if(root->lc!=NULL) inorder(root->lc); putchar(root->data); if(root->rc!=NULL) inorder(root->rc);/后序遍歷-遞歸int postorder(struct bnode *root) if(root->lc!=NULL) postorder(root->lc); if(root->rc!=NULL) postorder(root->rc); putchar(ro

5、ot->data);int main() struct bnode *root=NULL; printf("先序建立二叉樹，輸入變量: (下劃線為NULL):"); root=create(); /輸入(ABC DE G F ) printf("先序遍歷輸出："); preorder(root); printf("n"); printf("中序遍歷輸出："); inorder(root); printf("n"); printf("后序遍歷輸出："); postorde

6、r(root); printf("n");下面建立該二叉樹并展示輸出結果：#include<stdio.h>#include<stdlib.h>struct hftree int data; struct hftree *left; struct hftree *right;struct hftree *CreateHuffman(int a, int n) int i, j; struct hftree *b100, *q;/假設哈弗曼書最大為100個節(jié)點 for (i = 0; i < n; i+) /初始化b指針數組，使每個指針元素指向a

7、數組中對應的元素結點 bi=(struct hftree*)malloc(sizeof(struct hftree); bi->data=ai; bi->left=NULL; bi->right=NULL; for (i = 1; i < n; i+)/進行 n-1 次循環(huán)建立哈夫曼樹 /k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標 int k1 = -1, k2; for (j = 0; j < n; j+)/讓k1初始指向森林中第一棵樹，k2指向第二棵 if (bj != NULL && k1 = -1) k1 = j; co

8、ntinue; if (bj != NULL) k2 = j; break; for (j = k2; j < n; j+)/從當前森林中求出最小權值樹和次最小 if (bj != NULL) if (bj->data < bk1->data) k2 = k1; k1 = j; else if (bj->data < bk2->data) k2 = j; /由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點 q = (struct hftree*)malloc(sizeof(struct hftree); q->data = bk1->

9、data + bk2->data; q->left = bk1; q->right = bk2; bk1 = q;/將指向新樹的指針賦給b指針數組中k1位置 bk2 = NULL;/k2位置為空 free(b); /刪除動態(tài)建立的數組b return q; /返回整個哈夫曼樹的樹根指針/求哈夫曼樹的帶權路徑長度int WeightPathLength(struct hftree* T, int len)/len初始為0 if (T = NULL) /空樹返回0 return 0; else if (T->left = NULL && T->righ

10、t = NULL)/訪問到葉子結點 return T->data * len; else /訪問到非葉子結點，進行遞歸調用，返回左右子樹的帶權路徑長度之和，len遞增 return WeightPathLength(T->left,len+1)+WeightPathLength(T->right,len+1); /哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的算法基礎上進行修改）void HuffManCoding(struct hftree* T, int len)/len初始值為0 static int a10;/定義靜態(tài)數組a，保存每個葉子的編碼，數組長度至少是樹深度減一

11、if (T != NULL)/訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼 if (T->left = NULL && T->right = NULL) int i; printf("結點權值為%d的編碼：", T->data); for (i = 0; i < len; i+) printf("%d", ai); printf("n"); else alen = 0; HuffManCoding(T->left, len + 1); alen = 1; HuffManCoding(T->right, len + 1); int main() int n, i; int a100; struct hftree* t; printf("從鍵盤輸入待構造的哈夫曼樹中帶權葉子結點數n："); scanf("%d", &n); printf("從鍵盤輸入%d個整數作為權值：", n); for (i = 0; i < n; i+) scanf(&qu