西北工业大学计算机学院数据结构实验代码

#include <stdio.h> #include <stdlib.h> #include<string.h> #define N 30 #define M 2*N -1 //采用静态三叉链表进行存储 typedef struct { int flag;//用于遍历标记以及编码 char data;//存放输入的字符 int weight;//结点的权值 int parent;//双亲的下标 int LChild;//左孩子结点的下标 int RChild;//右孩子结点的下标 }HTNode,HuffmanTree[M + 1];//0不用 typedef char *HuffmanCode[N + 1]; void InitHuffman(HuffmanTree ht, int w[], char str[], int n); void Select(HuffmanTree ht,int pos,int *s1,int *s2); void CreateHuffmanTree(HuffmanTree ht,int w[],int n); void HuffmanEncoder(HuffmanTree ht,HuffmanCode hc, int n); void OutputEncoder(HuffmanTree ht, HuffmanCode hc, char* target, int n,char *encode); void OutputDecoder(char *decode); //初始化哈夫曼树 void InitHuffman(HuffmanTree ht, int w[], char str[], int n)//ht为哈夫曼树，str为输入字符串，n为字符和权值 { int m = 2 * n - 1; ht[0].flag = 0;//初始化 for (int i = 1;i <= n;i++)//1~n号单元存放叶子结点，初始化 { ht[i].flag = ht[i - 1].flag + 1;//如果为2说明为右节点，如果为1说明为左节点 ht[i].data = str[i]; ht[i].weight = w[i]; ht[i].LChild = 0; ht[i].RChild = 0; ht[i].parent = 0; } for (int i = n + 1;i <= m;i++)//n+1~m号单元存放非叶子结点，初始化 { ht[i].flag = ht[i - 1].flag + 1; ht[i].data = 0; ht[i].weight = 0; ht[i].LChild = 0; ht[i].RChild = 0; ht[i].parent = 0; } } //在ht[1]~ht[i-1]的范围内选择两个parent为0，且weight最小的结点，其序号分别赋值给s1,s2 /* 1.两次遍历，每次找到一个最小值 2.一次遍历找到最小和次小值 3.小顶堆，两次取堆顶元素 */ //采用两次遍历每次找到最小值的方法 void Select(HuffmanTree ht,int pos,int *s1,int *s2) { int min1 = 0; int min2 = 0; int tmp = 0;//作为比较的中间变量 for (int i = 1;i <= pos;i++) { if (ht[i].parent == 0)//如果为根节点,即parent为0 { min1 = i; tmp = ht[i].weight; break; } } for (int i = 1; i <= pos ; i++){ if (ht[i].parent == 0 && ht[i].weight < tmp){ min1 = i; tmp = ht[i].weight; } } *s1 = min1; ht[min1].parent = -1;//防止重复遍历该位置 //第二次遍历寻找次小元 for (int i = 1;i <= pos;i++) { if (ht[i].parent == 0)//如果为根节点,即parent为0 { min2 = i; tmp = ht[i].weight; break; } } for (int i = 1; i <= pos ; i++){ if (ht[i].parent == 0 && ht[i].weight < tmp){ min2 = i; tmp = ht[i].weight; } } *s2 = min2; } //创建哈夫曼树 void CreateHuffmanTree(HuffmanTree ht,int w[],int n)//构造哈夫曼树ht[M+1],w[]存放n个权值 { int m = 2*n - 1; int s1,s2; //创建非叶结点，建哈夫曼树 for (int i = n + 1;i <= m;i++) { Select(ht,i - 1,&s1,&s2);//在F中选取两棵权值最小的树s1,s2 ht[i].weight =ht[s1].weight + ht[s2].weight;//将权值最小的树权值之和作为新的根结点的权值 //如果s1为次小值，s2为最小值，根据哈夫曼树左子树比右子树小的规律，生成新的结点 if (ht[s1].weight < ht[s2].weight) { ht[i].LChild = s1; ht[i].RChild = s2; } else//反之同理 { ht[i].LChild = s2; ht[i].RChild = s1; } //完成后遍历下一个位置 ht[s1].parent = i; ht[s2].parent = i; } } //哈夫曼编码 /* 进行编码时需找到编码数据在树中位置， 再循环判断当前节点是其父节点的左支还是右支， 若是左支则记录0， 右支记录1， 直到当前节点为头结点， 就可得到需编码数据编码的逆序， 再将它反过来就是所求编码。 */ void HuffmanEncoder(HuffmanTree ht,HuffmanCode hc,int n)//ht为构造的哈夫曼树，hc为需要输出的编码结果，target为输入的目标报文 { //构建哈夫曼编码 char* ec;//ec为字符串数组首地址指针 ec = (char*)malloc(sizeof(char) * n); if (ec == NULL) return; ec[n - 1] = '\0';//为防止字符串数组溢出 for (int i = 1; i <= n; i++) { int head = n - 1;//将编码逆序输出 int tmp = i; int par = ht[i].parent;//父结点 //当当前结点不为头结点，即当前结点仍有父节点时 while (par) { head--; //判断当前节点是其父节点的左支还是右支,左支则记录0，右支记录1 //直到当前节点为头结点 if (ht[par].LChild == tmp) { ec[head] = '0'; } else { ec[head] = '1'; } tmp = par; par = ht[par].parent; } hc[i] = (char*)malloc(sizeof(char) * (n - head)); if (hc[i] == NULL) return; strcpy(hc[i], &ec[head]); } free(ec); } //输出编码结果 void OutputEncoder(HuffmanTree ht, HuffmanCode hc, char* target, int n,char *encode) { int length = strlen(target); encode[0] = '\0'; for (int i = 0; i < length; i++) { for (int j = 1; j <= n; j++) { if (target[i] == ht[j].data) { strcat(encode, hc[j]); } } } printf("%s\n",encode); } //哈夫曼译码 /* 只需要从头结点开始走，0走左支1走右支， 直到走到叶节点为止， 叶节点中数据就是所求数据 */ void HuffmanDecoder(HuffmanTree ht,HuffmanCode hc, char* encode, char *decode, int n)//length为输入的需要译码的编码的长度，count为译码的长度，ec[]为存储编码值的数组 { int length1 = strlen(encode); int i = 0, k = 0; while (i < length1) { for (int j = 1; j <= n; j++) { if (encode[i] == hc[j][0]) { int length2 = strlen(hc[j]); if (strncmp(hc[j], &encode[i], length2) == 0) { decode[k] = ht[j].data; k++; i = i + length2; } } } } } //输出解码结果 void OutputDecoder(char *decode)//这里可能存在数据传输问题 { printf ("%s",decode); printf ("\n"); } //用huffmanTree数组存储 int main() { int n;//n表示用户输入的字符集大小 HuffmanTree ht; HuffmanCode hc; char target[200];//目标报文 char encode[200] ;//编码数组 char decode[200] ;//解码数组 int *w;//用于存放输入的权值 char *str; //完成初始信息的输入 scanf("%d ",&n); str = (char*)malloc(sizeof(char) * (n + 1)); for (int i = 1; i <= n; i++) { getchar(); scanf("%c", &str[i]); } w = (int*)malloc(sizeof(int) * (n+1)); for (int i = 1; i <= n; i++) { scanf("%d", &w[i]); } //哈夫曼树初始化 InitHuffman(ht,w,str,n); //创建哈夫曼树 CreateHuffmanTree(ht,w,n); //哈夫曼树编码 HuffmanEncoder(ht,hc,n); //输出哈夫曼树编码 OutputEncoder(ht,hc,target,n,encode); //哈夫曼译码,并输出解码值，最后输出一个回车！ HuffmanDecoder(ht,hc,encode,decode,n); //输出哈夫曼译码 OutputDecoder(decode); return 0; }