- /*
- * 香农编码
- * 输入的信源为26个英文字母
- */
- #include <stdio.h>
- #include <math.h>
- #include <stdlib.h>
- #include <string.h>
- typedef struct shannon {
- char ch; //信源
- int num; //该信源出现的次数
- float p; //该信源出现的概率
- float padd; //该信源出现的概率和
- int lenth; //该信源的码长
- char w[20]; //编码出来的码字
- } SHAN;
- SHAN *input[26];
- void sortInput(int n) {
- SHAN *temp;
- int maxNum; //用选择排序排列input
- int maxLoc;
- int i;
- int j;
- //按照从大到小排序
- for (i = 0; i < n; i++) {
- maxNum = input[i]->num;
- maxLoc = i;
- for (j = i + 1; j < n; j++) {
- if (input[j]->num > maxNum) {
- maxNum = input[j]->num;
- maxLoc = j;
- }
- }
- if (maxLoc != i) {
- temp = input[i];
- input[i] = input[maxLoc];
- input[maxLoc] = temp;
- }
- }
- }
- void lenCode(int n) {
- int i;
- int sumNum; //所有信源出现的总次数
- double lognum;
- //计算所有信源出现的次数
- sumNum = 0;
- for (i = 0; i < n; i++) {
- sumNum += input[i]->num;
- }
- //计算概率、概率和、编码码长
- for (i = 0; i < n; i++) {
- //概率
- input[i]->p = (float)(input[i]->num) / (float)sumNum;
- //概率和
- if (i == 0) {
- input[i]->padd = 0;
- } else {
- input[i]->padd = input[i-1]->padd + input[i-1]->p;
- }
- //码长
- lognum = -log((double)(input[i]->p));
- lognum /= log((double)2);
- input[i]->lenth = (int)ceil((double)(lognum));
- }
- }
- void encode(int n) {
- int i;
- int j;
- float padd;
- char temp[20];
- for (i = 0; i < n; i++) {
- strcpy(temp, "");
- padd = input[i]->padd;
- for (j = 0; j < input[i]->lenth; j++) {
- padd *= 2;
- if (padd >= 1) {
- padd -= 1;
- temp[j] = '1';
- } else {
- temp[j] = '0';
- }
- }
- temp[j] = '\\0';
- strcpy(input[i]->w, temp);
- }
- }
- int main(void) {
- int i;
- int n; //信源的个数
- printf("请输入需要编码的信源的个数:\\n");
- scanf("%d", &n);
- for (i = 0; i < n; i++) {
- input[i] = (SHAN *)malloc(sizeof(SHAN));
- }
- //输入所有信源和每个信源的出现次数
- printf("请输入需要每个信源和该信源出现的次数,以空格隔开,每输入一组请以回车结束:\\n");
- for (i = 0; i < n; i++) {
- getchar(); //用来接收上一个输入时多出来的'\\n'
- scanf("%c %d", &(input[i]->ch), &(input[i]->num));
- }
- //按照每个信源出现的次数排序
- sortInput(n);
- //计算每个信源出现的概率、概率和、码长
- lenCode(n);
- //编码
- encode(n);
- printf("\\n编码结果:\\n");
- printf("编号 信源 次数 出现概率 码长 编码结果\\n");
- for (i = 0; i < n; i++) {
- printf("%3d %4c %4d %15f %6d %-s\\n",
- i,
- input[i]->ch,
- input[i]->num,
- input[i]->p,
- input[i]->lenth,
- input[i]->w);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/150320132423.html
来源: http://www.codesnippet.cn/detail/150320132423.html