電子科技大學(xué)軟件技術(shù)基礎(chǔ)實驗報告4

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

2、實驗，調(diào)試運行程序并完成報告。七、實驗器材（設(shè)備、元器件）：硬件要求：普通pc機(jī)，1G內(nèi)存，100G硬盤空間即可。 軟件要求：Windows 7，包括C編譯器的IDE。八、實驗步驟、實驗編程與運行結(jié)果：下面建立該二叉樹并展示輸出結(jié)果：#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");下面建立該二叉樹并展示輸出結(jié)果：#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;/假設(shè)哈弗曼書最大為100個節(jié)點 for (i = 0; i < n; i+) /初始化b指針數(shù)組，使每個指針元素指向a

7、數(shù)組中對應(yīng)的元素結(jié)點 bi=(struct hftree*)malloc(sizeof(struct hftree); bi->data=ai; bi->left=NULL; bi->right=NULL; for (i = 1; i < n; i+)/進(jìn)行 n-1 次循環(huán)建立哈夫曼樹 /k1表示森林中具有最小權(quán)值的樹根結(jié)點的下標(biāo)，k2為次最小的下標(biāo) 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+)/從當(dāng)前森林中求出最小權(quán)值樹和次最小 if (bj != NULL) if (bj->data < bk1->data) k2 = k1; k1 = j; else if (bj->data < bk2->data) k2 = j; /由最小權(quán)值樹和次最小權(quán)值樹建立一棵新樹，q指向樹根結(jié)點 q = (struct hftree*)malloc(sizeof(struct hftree); q->data = bk1->

9、data + bk2->data; q->left = bk1; q->right = bk2; bk1 = q;/將指向新樹的指針賦給b指針數(shù)組中k1位置 bk2 = NULL;/k2位置為空 free(b); /刪除動態(tài)建立的數(shù)組b return q; /返回整個哈夫曼樹的樹根指針/求哈夫曼樹的帶權(quán)路徑長度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)/訪問到葉子結(jié)點 return T->data * len; else /訪問到非葉子結(jié)點，進(jìn)行遞歸調(diào)用，返回左右子樹的帶權(quán)路徑長度之和，len遞增 return WeightPathLength(T->left,len+1)+WeightPathLength(T->right,len+1); /哈夫曼編碼（可以根據(jù)哈夫曼樹帶權(quán)路徑長度的算法基礎(chǔ)上進(jìn)行修改）void HuffManCoding(struct hftree* T, int len)/len初始值為0 static int a10;/定義靜態(tài)數(shù)組a，保存每個葉子的編碼，數(shù)組長度至少是樹深度減一

11、if (T != NULL)/訪問到葉子結(jié)點時輸出其保存在數(shù)組a中的0和1序列編碼 if (T->left = NULL && T->right = NULL) int i; printf("結(jié)點權(quán)值為%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("從鍵盤輸入待構(gòu)造的哈夫曼樹中帶權(quán)葉子結(jié)點數(shù)n："); scanf("%d", &n); printf("從鍵盤輸入%d個整數(shù)作為權(quán)值：", n); for (i = 0; i < n; i+) scanf(&qu