最佳答案

#include #include #include #define N 255 #define M 2*N - 1 char file[20] = "1.txt"; typedef struct { int data; /* 字符值 */ int weight; /* 權重 */ int parent; /* 雙親結點 */ int lchild; /* 左孩子結點 */ int rchild; /* 右孩子結點 */ }Tree; typedef struct { char cd[N]; int start; }Code; Tree ht[M]; Code hcd[N]; int cmp(const void*, const void*); int NumberOfChar(); void Reset(); void InputFile(); void Encode(int); void Decode(int); void OutputFile(int); void PrintHuffmanCode(int); void CreateHT(int); void CreateHCode(int); int main() { int x = 0; int n = 0; char ch; Reset(); InputFile(); /* 排序使得有效字符在前面 */ qsort(ht, N, sizeof(Tree), cmp); /* 記下有效字符的個數 */ n = NumberOfChar(); CreateHT(n); CreateHCode(n); OutputFile(n); PrintHuffmanCode(n); Encode(n); Decode(n); getchar(); return 0; } int cmp(const void *a ,const void *b) { return (*(Tree *)a).weight < (*(Tree *)b).weight ? 1 : -1; } int NumberOfChar() { int i, num = 0; for (i = 0; i < N; i++) { if (ht[i].weight > 0) num++; } return num; } void Reset() { int i; for (i = 0; i < M; i++) { ht[i].weight = 0; ht[i].parent = -1; ht[i].lchild = -1; ht[i].rchild = -1; } } void InputFile() { FILE *fp; char ch; system("cls"); fp = fopen(file, "rt"); /* 讀入字符并處理權重 */ while (fscanf(fp, "%c", &ch) != EOF) { ht[ch].data = ch; ht[ch].weight++; } fclose(fp); printf("原文件 %s 讀入成功!
", file); } void Encode(int n) { int i, k; char ch; FILE *fp1, *fp2; fp1 = fopen(file, "rt"); fp2 = fopen("Encode.txt", "wt+"); /* 一個字符一個字符替換 */ while (fscanf(fp1, "%c", &ch) != EOF) { for (i = 0; i < n; i++) { if (ht[i].data == ch) { for (k = hcd[i].start; k <= n; k++) { fprintf(fp2, "%c", hcd[i].cd[k]); } } } } fclose(fp1); fclose(fp2); printf("編碼成功，結果在 Encode.txt 中!
"); } void Decode(int n) { int i, k; char ch; FILE *fp1, *fp2; fp1 = fopen("Encode.txt", "rt"); fp2 = fopen("Decode.txt", "wt+"); i = 2 * n - 2; while (fscanf(fp1, "%c", &ch) != EOF) { if (ch == '0') i = ht[i].lchild; else i = ht[i].rchild; /* 找到葉子節點為止 */ if (ht[i].lchild == -1) { fprintf(fp2, "%c", ht[i].data); /* 繼續從根節點開始查找 */ i = 2 * n - 2; } } fclose(fp1); fclose(fp2); printf("解碼成功，結果在 Decode.txt 中!
"); } void OutputFile(int n) { FILE *fp; int i, k; fp = fopen("Huffman_Code.txt", "wt+"); for (i = 0; i < n; i++) { fprintf(fp, "%d ", ht[i].data); for (k = hcd[i].start; k <= n; k++) { fprintf(fp, "%c", hcd[i].cd[k]); } if (i < n - 1) fprintf(fp, "
"); } fclose(fp); printf("代碼表文件 Huffman_Code.txt 生成成功!
"); } void PrintHuffmanCode(int n) { int i, k; printf("ASCII \t Char \t HuffmanCode
"); for (i = 0; i < n; i++) { printf("%d \t \"%c\" \t ", ht[i].data, ht[i].data); for (k = hcd[i].start; k <= n; k++) { printf("%c", hcd[i].cd[k]); } printf("
"); } } void CreateHT(int n) { int i, k ,lmin, rmin; int min1, min2; /* 一共有2n-1個節點 */ for (i = n; i < 2 * n - 1; i++) { /*lmin和rmin為最小權重的兩個節點置*/ min1 = min2 = 0x7FFFFFFF; lmin = rmin = -1; for (k = 0; k <= i - 1; k++) { /*只在尚未構造二叉樹的節點中查找*/ if (ht[k].parent == -1) { if (ht[k].weight < min1) { min2 = min1; rmin = lmin; min1 = ht[k].weight; lmin = k; } else if (ht[k].weight < min2) { min2 = ht[k].weight; rmin = k; } } } /* 修改2個小權重節點的雙親 */ ht[lmin].parent = i; ht[rmin].parent = i; /* 修改雙親的權重 */ ht[i].weight = ht[lmin].weight + ht[rmin].weight; /* 修改雙親的孩子 */ ht[i].lchild = lmin; ht[i].rchild = rmin; } } void CreateHCode(int n) { int i, f, c; Code hc; for (i = 0; i < n; i++) { hc.start = n; c = i; f = ht[i].parent; /* 循序直到樹根結點 */ while (f != -1) { /* 處理左孩子結點 */ if (ht[f].lchild == c) hc.cd[hc.start--] = '0'; /* 處理右孩子結點 */ else hc.cd[hc.start--] = '1'; c = f; f = ht[f].parent; } /* start指向哈夫曼編碼最開始字符 */ hc.start++; hcd[i] = hc; } }

回答者：mrp672016-11-02 00:00