数据结构c语言赫夫曼树和赫夫曼编码的实现

好的，关于数据结构赫夫曼树的C语言实现，可以分为以下几个步骤： 1. 定义赫夫曼树的结构体 ``` typedef struct HuffmanTreeNode { int weight; // 权值 int parent; // 父节点下标 int leftChild; // 左孩子下标 int rightChild; // 右孩子下标 } HuffmanTreeNode; ``` 2. 构建赫夫曼树 ``` void createHuffmanTree(HuffmanTreeNode *huffmanTree, int n) { int i, j, min1, min2; for (i = 0; i < 2 * n - 1; i++) { huffmanTree[i].parent = -1; huffmanTree[i].leftChild = -1; huffmanTree[i].rightChild = -1; } for (i = 0; i < n; i++) { scanf("%d", &huffmanTree[i].weight); } for (i = 0; i < n - 1; i++) { min1 = min2 = INT_MAX; int node1, node2; for (j = 0; j < n + i; j++) { if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) { min2 = min1; node2 = node1; min1 = huffmanTree[j].weight; node1 = j; } else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) { min2 = huffmanTree[j].weight; node2 = j; } } huffmanTree[node1].parent = n + i; huffmanTree[node2].parent = n + i; huffmanTree[n + i].weight = min1 + min2; huffmanTree[n + i].leftChild = node1; huffmanTree[n + i].rightChild = node2; } } ``` 3. 编码 ``` void huffmanEncoding(HuffmanTreeNode *huffmanTree, int n) { char **huffmanCode = (char **) malloc(n * sizeof(char *)); char *code = (char *) malloc(n * sizeof(char)); code[n - 1] = '\0'; int i, j, c, p; for (i = 0; i < n; i++) { huffmanCode[i] = (char *) malloc(n * sizeof(char)); for (j = 0; j < n; j++) { huffmanCode[i][j] = '\0'; } c = i; p = huffmanTree[c].parent; while (p != -1) { if (huffmanTree[p].leftChild == c) { code[--n] = '0'; } else { code[--n] = '1'; } c = p; p = huffmanTree[c].parent; } strcpy(huffmanCode[i], &code[n]); } for (i = 0; i < n; i++) { printf("%d的哈夫曼编码为：%s\n", huffmanTree[i].weight, huffmanCode[i]); } } ```