怎么调用该函数?void Encoding(HuffNode ht[],HuffCode hcd[],int n){//哈夫曼结点、哈夫曼编码、第n个结点 HuffCode d; int i,k,f,c; for(i=1;i<=n;i++){ d.start = n+1; //起始位置 c = i; //从叶子结点开始向上 f = ht[i].parent; while(f!=0){ if(ht[f].leftchild == c) d.cd[--d.start] = '0'; //左树为0 else d.cd[--d.start] = '1'; //右树为1 c = f; f = ht[f].parent; } hcd[i] = d; } printf("输出哈夫曼编码:\n"); for(i=1;i<=n;i++){ printf("%c:",ht[i].data); for(k=hcd[i].start;k<=n;k++){ printf("%c",hcd[i].cd[k]); } printf("\n"); } }
时间: 2023-11-22 22:52:29 浏览: 27
该函数的调用方式与普通函数一样,可以在程序的其他位置直接调用。需要传入三个参数:哈夫曼结点数组ht[]、哈夫曼编码数组hcd[]和第n个结点n。在调用函数前需要先定义好这三个数组,并根据需要初始化它们。
示例代码:
```c
int main(){
HuffNode ht[MAX_N];
HuffCode hcd[MAX_N];
int n = 10;
// 初始化ht数组
Encoding(ht, hcd, n);
return 0;
}
```
在上面的示例代码中,我们定义了一个大小为MAX_N的哈夫曼结点数组ht[]和哈夫曼编码数组hcd[],并且将结点数n设为10。在调用Encoding函数时,将这三个参数传入即可。
相关问题
用c语言构造Huffm树,其中包含如下函数。 ●CreateHT(HTNode ht[],intn); 由含有n个叶子结点的ht构造完整的哈夫曼树。 ●CreateHCode( HTNode ht[], HCode hed[],int n): 由哈夫曼树ht构造哈夫曼编码 hed。 ●DispHCode( HTNode ht[], HCode hed[],int n): 输出哈夫曼树ht和哈夫曼编码 hed中n个叶子结点的哈夫曼编码。 其中,主函数如下:int main() { int n = 15, i; string str[] = { "The","of","a","to","and","in","that","he","is","at","on","for","His","are","be" }; int fnum[] = { 1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123 }; HTNode ht[M]; HCode hcd[N]; for (i = 0; i < n; i++) { ht[i].data = str[i]; ht[i].weight = fnum[i]; } CreateHT(ht, n);//创建哈夫曼树 CreateHCode(ht, hcd, n);//求得哈夫曼编码 DispHCode(ht, hcd, n);//输出哈夫曼编码和平均查找长度 return 0; }
下面是一个用C语言实现哈夫曼树的示例代码,包含了CreateHT、CreateHCode和DispHCode三个函数:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 2*N-1 // 哈夫曼树中结点的个数
#define N 100 // 哈夫曼编码的最大长度
typedef struct {
char* data; // 结点的内容
int weight; // 结点的权值
int parent; // 父结点的下标
int lchild; // 左子结点的下标
int rchild; // 右子结点的下标
} HTNode;
typedef char* HCode; // 定义哈夫曼编码类型为char*类型
// 选择权值最小的两个结点s1和s2
void Select(HTNode ht[], int n, int* s1, int* s2)
{
int i, min1, min2;
min1 = min2 = -1;
for (i = 0; i < n; i++) {
if (ht[i].parent == -1) {
if (min1 == -1 || ht[i].weight < ht[min1].weight) {
min2 = min1;
min1 = i;
}
else if (min2 == -1 || ht[i].weight < ht[min2].weight) {
min2 = i;
}
}
}
*s1 = min1;
*s2 = min2;
}
// 创建哈夫曼树
void CreateHT(HTNode ht[], int n)
{
int i, s1, s2;
for (i = 0; i < 2 * n - 1; i++) {
ht[i].parent = -1;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
for (i = n; i < 2 * n - 1; i++) {
Select(ht, i, &s1, &s2);
ht[s1].parent = i;
ht[s2].parent = i;
ht[i].lchild = s1;
ht[i].rchild = s2;
ht[i].weight = ht[s1].weight + ht[s2].weight;
}
}
// 求哈夫曼编码
void CreateHCode(HTNode ht[], HCode hcd[], int n)
{
int i, j, p;
char* cd = (char*)malloc(N * sizeof(char));
cd[N - 1] = '\0';
for (i = 0; i < n; i++) {
p = i;
j = N - 1;
while (ht[p].parent != -1) {
if (ht[ht[p].parent].lchild == p) {
cd[--j] = '0';
}
else {
cd[--j] = '1';
}
p = ht[p].parent;
}
hcd[i] = (char*)malloc((N - j) * sizeof(char));
strcpy(hcd[i], &cd[j]);
}
free(cd);
}
// 输出哈夫曼编码和平均查找长度
void DispHCode(HTNode ht[], HCode hcd[], int n)
{
int i, j, len, sum = 0;
printf("哈夫曼编码如下:\n");
for (i = 0; i < n; i++) {
printf("%s: %s\n", ht[i].data, hcd[i]);
len = strlen(hcd[i]);
sum += ht[i].weight * len;
}
printf("平均查找长度为:%.2f\n", (float)sum / 10000);
}
int main()
{
int n = 15, i;
char* str[] = { "The","of","a","to","and","in","that","he","is","at","on","for","His","are","be" };
int fnum[] = { 1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123 };
HTNode ht[M];
HCode hcd[N];
for (i = 0; i < n; i++) {
ht[i].data = str[i];
ht[i].weight = fnum[i];
}
CreateHT(ht, n); // 创建哈夫曼树
CreateHCode(ht, hcd, n); // 求得哈夫曼编码
DispHCode(ht, hcd, n); // 输出哈夫曼编码和平均查找长度
return 0;
}
```
在上面的代码中,我们首先定义了一个HTNode结构体,用于表示哈夫曼树中的结点。然后定义了HCode类型为char*类型,用于表示哈夫曼编码。在CreateHT函数中,我们使用了Select函数来选择权值最小的两个结点,然后将它们合并为一个新的结点,并更新哈夫曼树。在CreateHCode函数中,我们使用了一个cd数组来保存当前结点的编码,然后反向遍历哈夫曼树,找到每个叶子结点的编码,并将其保存在hcd数组中。在DispHCode函数中,我们输出每个叶子结点的编码,并计算平均查找长度。
注意,上面的代码中使用了动态内存分配来保存哈夫曼编码,需要在程序结束时释放掉分配的内存。
实验题3:构造哈夫曼树和生成哈夫曼编码 (一)实验目的:领会哈夫曼的构造过程以及哈夫曼编码的生成过程。 (二)实验内容:编写一个程序exp3-3.cpp,构造一棵哈夫曼树,输出对应的哈夫曼编码和平均查找长度。并对如表1所示的数据进行验证。 表1 单词及出现的频度 单词 The of a to and in that he is at on for His are Be 出现频度 1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123 设计相关算法,其中包含如下函数。 CreateHT(HTNode ht[],int n):由含有n个叶子结点的ht构造完整的哈夫曼树。 CreateHCode(HTNode ht[],HCode hcd[],int n):由哈夫曼树ht构造哈夫曼编码hcd。 DispHCode(HTNode ht[],HCode hcd[],int n):输出哈夫曼树ht和哈夫曼编码hcd中n个叶子结点的哈夫曼编码。
以下是基于C++的实现代码,包含CreateHT、CreateHCode、DispHCode三个函数的实现。
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int MAXM = MAXN * 2 - 1;
struct HTNode {
int weight;
int parent, lchild, rchild;
};
struct HCode {
char code[MAXN];
int start;
};
void CreateHT(HTNode ht[], int n) {
int m = 2 * n - 1;
for (int i = 0; i < n; i++) {
cin >> ht[i].weight;
ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
}
for (int i = n; i < m; i++) {
int min1 = -1, min2 = -1;
for (int j = 0; j < i; j++) {
if (ht[j].parent == -1) {
if (min1 == -1) {
min1 = j;
} else if (min2 == -1) {
min2 = j;
} else if (ht[j].weight < ht[min1].weight) {
min2 = min1;
min1 = j;
} else if (ht[j].weight < ht[min2].weight) {
min2 = j;
}
}
}
ht[i].weight = ht[min1].weight + ht[min2].weight;
ht[min1].parent = i;
ht[min2].parent = i;
ht[i].lchild = min1;
ht[i].rchild = min2;
}
}
void CreateHCode(HTNode ht[], HCode hcd[], int n) {
for (int i = 0; i < n; i++) {
int c = i, f = ht[c].parent;
while (f != -1) {
if (ht[f].lchild == c) {
hcd[i].code[hcd[i].start++] = '0';
} else {
hcd[i].code[hcd[i].start++] = '1';
}
c = f;
f = ht[c].parent;
}
reverse(hcd[i].code, hcd[i].code + hcd[i].start);
}
}
void DispHCode(HTNode ht[], HCode hcd[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
cout << i << " " << hcd[i].code << endl;
sum += ht[i].weight * hcd[i].start;
}
cout << "Average Length: " << (double)sum / n << endl;
}
int main() {
int n;
cin >> n;
HTNode ht[MAXM];
HCode hcd[MAXN];
CreateHT(ht, n);
CreateHCode(ht, hcd, n);
DispHCode(ht, hcd, n);
return 0;
}
```
在该实现中,我们首先定义了两个结构体,HTNode表示哈夫曼树的节点,HCode表示哈夫曼编码的结构体。其中,HCode中的code数组表示哈夫曼编码,start表示该编码的起始位置(即最高位的位置)。接着,我们实现了三个函数,分别为:
- CreateHT:由含有n个叶子结点的ht构造完整的哈夫曼树。
- CreateHCode:由哈夫曼树ht构造哈夫曼编码hcd。
- DispHCode:输出哈夫曼树ht和哈夫曼编码hcd中n个叶子结点的哈夫曼编码。
在主函数中,我们读入叶子节点的权值,并调用CreateHT、CreateHCode和DispHCode三个函数,输出哈夫曼编码和平均查找长度。
需要注意的是,在CreateHCode函数中,我们采用了反向存储哈夫曼编码的方式,即先存储最低位的编码,最后再将整个编码翻转过来,这样可以方便地输出哈夫曼编码。