电子科技大学软件技术基础实验报告4

电子科技大学通信与信息工程学院标准实验报告

（实验）课程名称软件技术基础实验

电子科技大学教务处制表

电子科技大学

实验报告

一、实验室名称：校公共机房

二、实验项目名称：二叉树和哈夫曼树

三、实验学时：4学时

四、实验原理：

使用VS2010等C语言集成开发环境（IDE），在微型计算机上对程序进行编辑、编译、连接与运行。通过上机练习掌握二叉树的建立、插入删除，遍历等方法和过程，掌握递归函数在二叉树建立，遍历中的应用，掌握哈夫曼树的最小路径和建立过程。

五、实验目的：

1.熟练二叉树和哈夫曼树的概念和基本操作方法。

2.掌握课程平台使用方法。

六、实验内容：

上机完成所有函数，编程实验，调试运行程序并完成报告。

七、实验器材（设备、元器件）：

硬件要求：普通pc机，1G内存，100G硬盘空间即可。

软件要求：Windows 7，包括C编译器的IDE。

八、实验步骤、实验编程与运行结果：

下面建立该二叉树并展示输出结果：

#include

#include

typedef struct bnode

{

int data;

struct bnode *lc,*rc;

};

struct bnode* create()

{

struct bnode *tree=NULL;

char ch;

ch=getchar();

if(ch=='_')

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->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(root->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("后序遍历输出：");

postorder(root);

printf("\n");

}

下面建立该二叉树并展示输出结果：

#include

#include

struct hftree

{

int data;

struct hftree *left;

struct hftree *right;

};

struct hftree *CreateHuffman(int a[], int n)

{

int i, j;

struct hftree *b[100], *q;//假设哈弗曼书最大为100个节点

for (i = 0; i < n; i++) //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点{

b[i]=(struct hftree*)malloc(sizeof(struct hftree));

b[i]->data=a[i];

b[i]->left=NULL;

b[i]->right=NULL;

}

for (i = 1; i < n; i++)//进行n-1 次循环建立哈夫曼树

{

//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标

int k1 = -1, k2;

for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树，k2指向第二棵

{

if (b[j] != NULL && k1 == -1)

{

k1 = j;

continue;

}

if (b[j] != NULL)

{

k2 = j;

break;

}

}

for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小

{

if (b[j] != NULL)

{

if (b[j]->data < b[k1]->data)

{

k2 = k1;

k1 = j;

}

else if (b[j]->data < b[k2]->data)

k2 = j;

}

}

//由最小权值树和次最小权值树建立一棵新树，q指向树根结点

q = (struct hftree*)malloc(sizeof(struct hftree));

q->data = b[k1]->data + b[k2]->data;

q->left = b[k1];

q->right = b[k2];

b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置

b[k2] = NULL;//k2位置为空

}

free(b); //删除动态建立的数组b

return q; //返回整个哈夫曼树的树根指针

}

//求哈夫曼树的带权路径长度

int WeightPathLength(struct hftree* T, int len)//len初始为0

{

if (T == NULL) //空树返回0

return 0;

else

{

if (T->left == NULL && T->right == 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 a[10];//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一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", a[i]);

printf("\n");

}

else

{

a[len] = 0;

HuffManCoding(T->left, len + 1);

a[len] = 1;

HuffManCoding(T->right, len + 1);

}

}

}

int main()

{

int n, i;

int a[100];

struct hftree* t;

printf("从键盘输入待构造的哈夫曼树中带权叶子结点数n：");

scanf("%d", &n);

printf("从键盘输入%d个整数作为权值：", n);

for (i = 0; i < n; i++)

scanf(" %d", &a[i]);

t = CreateHuffman(a, n);

printf("哈夫曼树的带权路径长度：");

printf("%d\n", WeightPathLength(t, 0));

printf("各个数据的哈夫曼编码：\n");

HuffManCoding(t, 0);

}

本文来源：https://www.bwwdw.com/article/lv0e.html