vc++6.0编写程序实现哈夫曼编码

以下是使用VC++6.0编写程序实现哈夫曼编码的步骤：

1.定义哈夫曼树的结构体和节点结构体

// 哈夫曼树结构体
struct HuffmanTree {
    int weight; // 权值
    int parent; // 父节点下标
    int lchild; // 左孩子下标
    int rchild; // 右孩子下标
};

// 哈夫曼树节点结构体
struct HuffmanNode {
    int weight; // 权值
    char ch; // 字符
    string code; // 编码
};

2.定义比较函数，用于排序

bool cmp(HuffmanTree a, HuffmanTree b) {
    return a.weight < b.weight;
}

3.创建哈夫曼树

void createHuffmanTree(HuffmanTree tree[], int n) {
    int i, j, k;
    for (i = 0; i < 2 * n - 1; i++) {
        tree[i].parent = -1;
        tree[i].lchild = -1;
        tree[i].rchild = -1;
    }
    for (i = 0; i < n; i++) {
        cout << "请输入第" << i + 1 << "个节点的权值：";
        cin >> tree[i].weight;
    }
    for (i = 0; i < n - 1; i++) {
        int min1 = -1, min2 = -1;
        for (j = 0; j < n + i; j++) {
            if (tree[j].parent == -1) {
                if (min1 == -1) {
                    min1 = j;
                } else if (min2 == -1) {
                    min2 = j;
                } else {
                    if (tree[j].weight < tree[min1].weight) {
                        min2 = min1;
                        min1 = j;
                    } else if (tree[j].weight < tree[min2].weight) {
                        min2 = j;
                    }
                }
            }
        }
        tree[min1].parent = n + i;
        tree[min2].parent = n + i;
        tree[n + i].lchild = min1;
        tree[n + i].rchild = min2;
        tree[n + i].weight = tree[min1].weight + tree[min2].weight;
    }
}

4.生成哈夫曼编码

void createHuffmanCode(HuffmanTree tree[], HuffmanNode node[], int n) {
    int i, j, k;
    for (i = 0; i < n; i++) {
        node[i].ch = i + 'a';
        node[i].weight = tree[i].weight;
        int parent = tree[i].parent;
        int current = i;
        while (parent != -1) {
            if (tree[parent].lchild == current) {
                node[i].code = '0' + node[i].code;
            } else {
                node[i].code = '1' + node[i].code;
            }
            current = parent;
            parent = tree[parent].parent;
        }
    }
}

5.输出哈夫曼编码

void printHuffmanCode(HuffmanNode node[], int n) {
    cout << "字符\t权值\t编码" << endl;
    for (int i = 0; i < n; i++) {
        cout << node[i].ch << "\t" << node[i].weight << "\t" << node[i].code << endl;
    }
}