贵阳手机网站建设公司,昆明专业网站制作公司,seo价格,如何网页设计与制作Content#xff1a; 一、问题描述二、算法思想三、代码实现四、小结 一、问题描述 对一篇英文文章#xff0c;统计各字符#xff08;仅限于26个小写字母#xff09;出现的次数#xff0c;并据此进行 Huffman 编码。
二、算法思想 首先#xff0c;打开文本文件#xff0… Content 一、问题描述二、算法思想三、代码实现四、小结 一、问题描述 对一篇英文文章统计各字符仅限于26个小写字母出现的次数并据此进行 Huffman 编码。
二、算法思想 首先打开文本文件统计各个小写英文字母出现的次数 然后统计出现过的字母个数 num 如果 num1进行相关信息的显示不进行 Huffman 编码 否则进行 Huffman 编码 准备工作存储出现过的字母编号及出现次数 1、根据出现次数创建 Huffman 树 (1)根据求得的 num 个出现次数 { w 1 , w 2 , ⋯ , w n u m } \lbrace w_1,w_2,\cdots,w_{num} \rbrace {w1,w2,⋯,wnum} 构成 num 棵二叉树的集合 F { T 1 , T 2 , ⋯ , T n u m } F\lbrace T_1,T_2,\cdots,T_{num} \rbrace F{T1,T2,⋯,Tnum}其中每棵二叉树 T i T_i Ti 中只有一个带权为 w i w_i wi 的根节点其左右子树均为空 (2)在 F 中选取两棵根节点权值最小的树作为左右子树构造一棵新二叉树其根节点的权值为两棵子树根节点权值之和 (3)从 F 中删除这两棵树并将新生成的树添加到 F 中 (4)重复(2)和(3)直到 F 中只含一棵树。所得到的树就是 Huffman 树 2、根据 Huffman 树进行 Huffman 编码 约定 ‘0’ 表示左分支‘1’ 表示右分支。从某个叶子节点开始如果没有父节点表示编码结束如果其有父节点如果为父节点的左孩子编码尾部添加 ‘0’如果为右孩子尾部添加 ‘1’然后向根节点移动当前节点变为其父节点父节点变为父节点的父节点进行相同操作。 编码结束之后对编码进行逆置得到正序编码 3、最后显示出现的字母及其出现的次数和 Huffman 编码
三、代码实现
#includestdio.h
#includestring.h
#includestdlib.h
#includemath.h
#pragma warning(disable:4996)typedef struct myhuffman//赫夫曼树的节点
{int weight;int parent,lchild,rchild;
}HTnode;typedef struct mylist//存放序号和权重
{int index;int weight;
}LI;int *statis();//统计小写英文字母出现的频次返回存放频次的数组char **huffmanCoding(int *w, int n);//创建huffman编码w用于存放叶子节点的权重n表示叶子节点个数void select(HTnode *HT,int k,int *s1,int *s2);//在HT[1,,,k]中选取parent0且weight最小的两个节点返回其序号(*s1),(*s2)int main(void)
{int i,j;int *w,num;int **A;//用于存放频次不为0的字母编号和频次char **HC;//获取小写字母出现次数wstatis(); //统计出现过的字母个数num0;for (i 1; i 26; i){if (w[i] ! 0)num;}printf(\n字母出现的次数和Huffman编码如下:\n);if (num 0)printf(\n没有出现小写英文字母无需进行Huffman编码\n);else // num1{A(int **)malloc(2*sizeof(int *));A[0](int *)malloc((num1)*sizeof(int));A[1](int *)malloc((num1)*sizeof(int));//向A中存放数据j1;for (i 1; i 26 j num; i){if (w[i] ! 0){A[0][j]i;A[1][j]w[i];j;}}if (num 1)printf(只出现了一个字母:%c频次%d其Huffman编码为1\n, A[0][1] a - 1, A[1][1]);else // num2{//创建huffman编码HC huffmanCoding(A[1], num);//显示huffman编码 for (i 1; i num; i)printf(%c频次%2d编码%s\n, A[0][i] a - 1, A[1][i], HC[i]);free(HC);}free(A);}free(w); return 0;
}int *statis()//统计小写英文字母出现的频次返回存放频次的数组
{int i;int *w;FILE *fp;char ch,filename[50];//初始化w(int *)malloc(27*sizeof(int));for (i 1; i 26; i)w[i]0;//打开文件printf(请输入文件名:);scanf(%s,filename);fpfopen(filename,r);if (!fp){printf(文件不存在!\n);exit(-1);}//统计小写字母出现次数printf(\n文本信息为:\n);while (!feof(fp)){chfgetc(fp);printf(%c,ch);if (a ch ch z)w[ch - a 1];}printf(\n);//关闭文件fclose(fp);return w;
}char **huffmanCoding(int *w, int n)//创建huffman编码w用于存放叶子节点的权重n表示叶子节点个数
{int i,j,k,l;HTnode *HT,p;int m;int s1,s2;char **HC;char *cd;//一、创建huffman树m2*n-1;//总的节点个数HT(HTnode *)malloc((m1)*sizeof(HTnode));//HT为结构体数组用于存放huffman树的节点//初始化for (i 1; i n; i)//叶子节点{p.weightw[i];p.parent0;p.lchildp.rchild0;HT[i]p;}for (; i m; i)//非叶子节点{p.weight0;p.parent0;p.lchildp.rchild0;HT[i]p;}//合并子树for (i n 1; i m; i){select(HT,i-1,s1,s2);//在HT[1,,,i-1]中选取parent0且weight最小的两个节点并返回其序号HT[s1].parenti;HT[s2].parenti;HT[i].weightHT[s1].weightHT[s2].weight;HT[i].lchilds1;HT[i].rchilds2;}//二、生成huffman编码HC(char **)malloc((n1)*sizeof(char *));cd(char *)malloc(n*sizeof(char));cd[n-1]\0;//字符串结束标志for (i 1; i n; i)//对各个叶子节点进行编码{jn-1;ki;lHT[i].parent;while (l ! 0){j--;if(HT[l].lchild k)cd[j]0;elsecd[j]1;//更新循环变量kl;lHT[l].parent;}//为第i个编码分配空间并赋值HC[i](char *)malloc((n-j)*sizeof(char));strcpy(HC[i],cd[j]);}free(HT);free(cd);return HC;
}void select(HTnode *HT, int k, int *s1, int *s2)//在HT[1,,,k]中选取parent0且weight最小的两个节点返回其序号(*s1),(*s2)
{int i,j;int n,lastindex;LI *T,temp;if(k 1)return;T(LI *)malloc((k1)*sizeof(LI));j0;for (i 1; i k; i)//挑选parent0的点{if (HT[i].parent 0){j;T[j].indexi;T[j].weightHT[i].weight;}}//对T冒泡排序寻找weight最小的两个节点nj;//parent0的节点个数lastindexn;while (lastindex n - 2)//至多进行两趟冒泡排序{ilastindex;lastindex0;for (j 1; j i; j){if (T[j].weight T[j 1].weight)//交换两个数据小的放在后面{tempT[j];T[j]T[j1];T[j1]temp;lastindexj;}}}//返回节点序号(*s1)T[n].index;(*s2)T[n-1].index;free(T);
}四、小结
1、 由于 Huffman 树中没有出度为1的点所以可以根据叶子节点的个数 n 0 n_0 n0 事先确定总的节点个数为 2 n 0 − 1 2n_0-1 2n0−1。 2、 结构体变量之间可以直接赋值 3、 在寻找 parent0 且 weight 最小的两个节点时只需进行至多两次的冒泡排序大大提高了查找效率和算法性能 4、 进行 Huffman 编码时由于是从叶子节点开始向前回溯到根节点所以编码时从后向前进行这样就避免了逆置编码 5、 对于特殊情况出现的英文字母个数小于等于1则不进行 Huffman 编码
