程序设计:编写一个哈夫曼编码译码程序。

CSDN问答 2021-12-30 11:49:39 阅读数:157

程序设计 设计 程序 编写 一个

按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。
为确保构建的哈夫曼树唯一,本题做如下限定:
(1)选择根结点权值最小的两棵二叉树时,选取权值较小者作为左子树。
(2)若多棵二叉树根结点权值相等,按先后次序分左右,先出现的作为左子树,后出现的作为右子树。
生成哈夫曼编码时,哈夫曼树左分支标记为0,右分支标记为1。
【输入格式】
第一行输入字符个数n;
第二行到第n行输入相应的字符及其词频(可以是整数,与可以是小数);
最后一行输入需进行译码的串。
【输出格式】
首先按树的先序顺序输出所有字符的编码,每个编码占一行;
最后一行输出需译码的原文,加上original:字样。
输出中均无空格
【样例输入】
3
m1
n1
c2
10110
【样例输出】
c:0
m:10
n:11
original:mnc




采纳答案:
#include<stdio.h>#include<stdlib.h>#define max 100const int m=100;int n,i,top=0,first=0,last=0,first1=0,last1=0;int s[m],z[m];typedef struct snodelinked{undefinedint data;char bianma;int parent;struct snodelinked *Rson,*Lson,*next;}snodelinked,*ptr;ptr hfcreat(ptr head);//void bianma(ptr root);void preorder(ptr root);void push(int s[],int &top,int x);void pop(int s[],int &top);void addq(int s[],int first,int &last,char x);int delq(int s[],int &first,int last);ptr hfinition();void translate(ptr root);int main(){undefinedptr head,root;head=hfinition();root=hfcreat(head);preorder(root);// putchar(’\n’);getchar();translate(root);return 0;}ptr hfinition(){undefinedptr head,p;scanf("%d",&n);head=p=(ptr)malloc(sizeof(snodelinked));head->data=max;head->bianma=’ ‘;getchar();for(i=0;i<n;i++){undefinedp->next=(ptr)malloc(sizeof(snodelinked));p=p->next;scanf("%c%1d",&p->bianma,&p->data);p->Lson=p->Rson=NULL;p->parent=0;}p->next=head;return head;}ptr hfcreat(ptr head){undefinedptr t1,t2,p,q,r;for(i=0;i<n-1;i++){undefinedr=(ptr)malloc(sizeof(snodelinked));t1=head->next;t2=t1->next;r->data=t1->data+t2->data;r->Lson=t1;r->Rson=t2;r->bianma=’ ‘;t1->parent=0;t2->parent=1;head->next=t2->next;p=head;q=p->next;while(1){undefinedif(r->data>=q->data){undefinedp=p->next;q=p->next;}else{undefinedr->next=q;p->next=r;break;}}}p=head->next;free(head);return p;}void preorder(ptr root){undefinedif(root->bianma!=’ ‘){undefinedputchar(root->bianma);printf( “:”);for(i=1;i<=top;i++){undefinedprintf("%d",s[i]);}putchar(’\n’);}if(root->Lson!=NULL) {undefinedpush(s,top,root->Lson->parent);preorder(root->Lson);top–;}if(root->Rson!=NULL) {undefinedpush(s,top,root->Rson->parent);preorder(root->Rson);top–;}}void push(int s[],int &top,int x){undefineds[++top]=x;}void pop(int s[],int &top){undefinedprintf("%d",s[top–]);}void translate(ptr root){undefinedptr h;h=root;int y;char x;x=getchar();printf(“original:”);while(x!=’\n’){undefinedaddq(z,first1,last1,x);x=getchar();}while(first1!=last1){undefinedy=delq(z,first1,last1);if(y== 0) {undefinedh = h->Lson;}else if(y== 1) h=h->Rson;if(h->bianma!=’ '){undefinedputchar(h->bianma);h=root;}}}void addq(int z[],int first,int &last,char x){undefinedif(x==‘0’) z[last]=0;else if(x==‘1’) z[last]=1;last=(last+1)%m;}int delq(int z[],int &first,int last){undefinedreturn z[first++];}

img



其他答案2:

这属实有点难

版权声明:本文为[CSDN问答]所创,转载请带上原文链接,感谢。 https://ask.csdn.net/questions/7619927