回 帖 发 新 帖 刷新版面

主题:[原创]哈夫曼编码的翻译?加分!

各位请帮忙看一下这个程序:
它是一道哈夫曼编码问题,就是要求用户首先输入字符对及应的权值(从大到小输),本题字符串中最多包含4个字符,不过可以通过修改N来修改,可以包含的最多字符个数。(注意:左子树为权值小的)
它能正常编码,在传送过程中的传递(即转化为0,1代码传递),但是在对方接到字符串时,它的0,1代码都在yi这个数组中,但是如果传一个字符能正常翻译过来,可是如果有2个以上就不正确了,请教一下,这个翻译过程,哪里出错了,你可以贴下去,运行一下,谢了!
#include<string.h>
#include<conio.h>
#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
const int n=4;
typedef struct node
{int data;
int r,l,p;
char ch;
char stf[n+1];
}node;
node * init();
void creattree(node *T);
void getrule(node *T);
void deal(node *p);
int main()
{node *p;
p=init();
creattree(p);
getrule(p);
deal(p);
return 0;
}
node *  init()
{int i;
node *T;
T=(node *)malloc((2*n-1)*sizeof(node));
if(!T){cout<<"开辟失败"<<endl;
getch();exit(0);}
cout<<"本题只给出4个叶子结点,可以令常量n取其他它值,增加或者减少叶子结点个数即传送字符串可以包含的字符个数.注意:请按权值从大到小输入"<<endl;
for(i=0;i<n;i++)
{cout<<"请输入权值:";
cin>>(T+i)->data;
cout<<"代表字符:";
cin>>(T+i)->ch;
}
for(i=0;i<2*n-1;i++)
(T+i)->l=(T+i)->r=(T+i)->p=-1;
cout<<"初始化结束,请按任意键继续"<<endl;
getch();
return T;
}

void getrule(node *T)
{int w=0,i,m,k=0,j,t;
char temp[n]={'\0'};
for(i=0;i<n;i++)
{j=i;
m=(T+i)->p;
while(m!=-1)
{if((T+m)->l==j)temp[w++]='0';
else temp[w++]='1';
j=m;
m=(T+m)->p;
}
for(t=w-1;t>=0;t--)
(T+i)->stf[w-1-t]=temp[t];
(T+i)->stf[w]='\0';
w=0;
for(k=0;k<n;k++)
temp[k]='\0';
}
for(i=0;i<n;i++)
cout<<(T+i)->ch<<"对应的代码:"<<(T+i)->stf<<endl;
}
void deal(node *p)
{char temp[100],yi[250]={'\0'},opyi[100]={'\0'},arr[n+1];
int i=0,v=0,j,k=0,t=0,m=0,flag=0;
cout<<"输入要表达的字符串"<<endl;
cin>>temp;
while(1)
{
    for(t=0;t<n;t++)
if(temp[i]==(p+t)->ch)strcat(yi,(p+t)->stf);
i++;
if(temp[i]=='\0')break;
}
cout<<"发送字符串    :"<<yi<<endl;
cout<<"对方接收字符串:"<<yi<<endl;
i=k=m=v=0;
while(1)
{


    for(i=k;i<n+k;i++)
{arr[m]=yi[i];
m++;
    for(j=0;j<n;j++)
if(!strcmp(arr,(p+j)->stf))
{flag=1;opyi[v]=(p+j)->ch;break;}
if(flag==1){flag=0;break;}    
    }
cout<<i<<endl;    
k=i+1;
     m=0;
while(1)
{arr[m++]='\0';
if(arr[m]=='\0')break;
}
m=0;
if(yi[k]=='\0')break;
}
cout<<"经过事先约定的规则译后得到的字符串如下:"<<opyi<<endl;
}  
void creattree(node *T)
{int t=n,s,m1,m2,s1,s2,w,x;
m1=T->data;
m2=m1;
s1=0;
s2=s1;
while(1)
{for(w=0;w<t;w++)
{if((T+w)->p!=-1)continue;
if((T+w)->data<m1){m1=(T+w)->data;s1=w;}
}
if(s1==t-1)x=t-1;
else x=t;
for(w=0;w<x;w++)
{if(((T+w)->p!=-1)||((T+w)->data==m1&&w==s1))continue;
if((T+w)->data<m2){m2=(T+w)->data;s2=w;}
}
(T+t)->data=m1+m2;
(T+t)->l=s1;
(T+t)->r=s2;
(T+t)->p=-1;
(T+s1)->p=(T+s2)->p=t;

t++;
if(t==2*n-1)break;
m1=0xffff;
m2=m1;
s1=0;
s2=s1;
}
}















回复列表 (共2个回复)

沙发

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define MAX 1000
#define MIN 20000
typedef struct node{
    int w;
    char data;
    int num;
    bool visited;
    int parents;
}Node;

void Create(Node *m[MAX],int n);//要构造的叶顶点
int Min_Node(Node *m[MAX]);//寻找具有最小权值的顶点
int Count_Visit(Node *m[MAX]);//被访问的顶点数
void CreateHuffman(Node *m[MAX],int n);//创建最优二叉树
void HuffmanCode(Node *m[MAX],int n);//编码

void Create(Node *m[MAX],int n)
{
    int i;
    Node *p;
    printf("**输入顺序为字符和权值**\n");
    for(i=0;i<n;i++){
        p=(Node *)malloc(sizeof(Node));
        cin>>p->data;
        cin>>p->w;
        p->visited=0;
        p->parents=-1;
        m[i]=p;
    }
    for(;i<MAX;i++) m[i]=NULL;
}


int Min_Node(Node *m[MAX])
{
    int min,i,spot;
    min=MIN;
    for(i=0;i<MAX;i++){
        if(m[i]&&m[i]->visited==0&&m[i]->w<min){
            min=m[i]->w;
            spot=i;
        }
    }
    m[spot]->visited=1;
    return(spot);
}


int Count_Visit(Node *m[MAX])
{
    int num=0,i;
    for(i=0;i<MAX;i++){
        if(m[i]&&m[i]->visited==0){
            num++;
        }
    }
    return(num);
}


void CreateHuffman(Node *m[MAX],int n)
{
    int spot1,spot2;
    int j;
    Node *p;
    j=n;
    while(Count_Visit(m)>1){
        spot1=Min_Node(m);
        spot2=Min_Node(m);
        p=(Node *)malloc(sizeof(Node));
        m[spot1]->num=0;
        m[spot2]->num=1;
        p->parents=-1;
        p->w=m[spot1]->w+m[spot2]->w;
        p->visited=0;
        m[++j]=p;
        m[spot1]->parents=m[spot2]->parents=j;
    }
}


void HuffmanCode(Node *m[MAX],int n)
{
    int ch[20];
    Node *p;
    int i,j;
    for(i=0;i<n;i++){
        printf("vex %c:",m[i]->data);
        p=m[i];
        j=0;
        while(p->parents!=-1){
            ch[j++]=p->num;
            p=m[p->parents];
        }
        j--;
        for(;j>=0;j--){
            printf("%d",ch[j]);
        }
        printf("\n");
    }
}


void main()
{
    Node *m[MAX];
    int n;
    printf("叶子数:");
    cin>>n;
    Create(m,n);
    CreateHuffman(m,n);
    HuffmanCode(m,n);
}
        

板凳

你的结构太乱了,你该一下习惯,这样容易找错。你的程序我停两天给你改一下,看能否成功!

我来回复

您尚未登录,请登录后再回复。点此登录或注册