| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1093 人关注过本帖
标题:数据结构学到霍夫曼编码了,自己结合课本编了一个,有个错误解决不了,求高 ...
只看楼主 加入收藏
bluecoyote
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2010-4-5
结帖率:100%
收藏
 问题点数:0 回复次数:6 
数据结构学到霍夫曼编码了,自己结合课本编了一个,有个错误解决不了,求高手解决!!!
程序代码:
#include<iostream>
#include<cstdlib>
#include<cstring>
using    namespace    std;
typedef    struct{
    unsigned    int    weight;
    unsigned    int    parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef    char **HuffmanCode;
void    Select(HuffmanTree &HT,int s,int& s1,int& s2){
    int    k;
    int    tag;
    for(k=1;k<=s;k++){
        if(HT[k].parent!=0){
            s1=k;
            tag=k+1;
            break;
        }
    }
    for(;k<=s;k++){
        if(HT[k].parent!=0&&HT[k].weight<=HT[s1].weight)
            s1=k;
    }
    for(k=tag;k<=s;k++){
        if(HT[k].parent!=0){
            s2=k;
            break;
        }
    }
    for(;k<=s;k++){
        if(HT[k].parent!=0&&HT[k].weight<=HT[s2].weight&&k!=s1)
            s2=k;
    }
}
int    HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
    int    m;
    int    i;
    char*    cd;
    HuffmanTree    p;
    if(n<=1) return 0;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(p=HT, i=1;i<=n;++i,++p,++w){
        p->weight=*w;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    for(;i<=m;++i,++p){
        p->weight=0;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }
    for(i=n+1;i<=m;++i){
        int s1,s2;
        Select(HT,i-1,s1,s2);
        HT[s1].parent=i;HT[s2].parent=i;
        HT[i].lchild=s1;HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    cout<<"huffman tree"<<endl;
    for(i=1,p=HT;i<=m;++i,++p){
        cout<<p->weight<<"----"<<p->parent<<"----"<<p->lchild<<"----"<<p->rchild<<endl;
    }
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    cd=(char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=1;i<=n;++i){
        int    start=n-1;
        int    f;
        int    c;
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
            if(HT[f].lchild==c)    cd[--start]='0';
            else cd[--start]='1';
        HC[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy(HC[i],&cd[start]);
    }
    free(cd);
    return    0;
}

int    main(){
    HuffmanTree    HT;
    HuffmanCode    HC;
    int* w;
    int    n;
    int    m;
    HuffmanTree ht;
    cout<<"please input the value of n=";
    cin>>n;
    w=(int *)malloc(n*sizeof(int));
    for(m=0;m<n;m++){
        cout<<"please input the weight of the "<<m+1<<"value :";
        cin>>w[m];
    }
    HuffmanCoding(HT,HC,w,n);
    system("pause");
    return    0;
}

上边的代码有一处错误,已经标注出来,求高手解决,先谢过了~~~
搜索更多相关主题的帖子: 霍夫曼 数据结构 课本 编码 
2010-06-10 21:07
bluecoyote
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2010-4-5
收藏
得分:0 
先顶一下~~

策杖只为图雪耻,横戈原不为封侯
2010-06-10 21:07
bluecoyote
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2010-4-5
收藏
得分:0 
已经解决了,错在select函数中的if语句判断条件错误,应该是                 HT[s1].parent==0   几处这样的语句都应该是这样,实在是大意了,翻了这样的错误。。。

策杖只为图雪耻,横戈原不为封侯
2010-06-12 16:15
longxuan1011
Rank: 2
等 级:论坛游民
威 望:1
帖 子:4
专家分:20
注 册:2010-6-19
收藏
得分:0 
居然是c++写的,好无奈啊
2010-06-24 21:57
longxuan1011
Rank: 2
等 级:论坛游民
威 望:1
帖 子:4
专家分:20
注 册:2010-6-19
收藏
得分:0 
# include <stdio.h>      
# include <stdlib.h>
# include <conio.h>
# include <string.h>
# define MAX_LENGTH 100
typedef char **HuffmanCode;
//**********数据结构*************
typedef struct   
{   int weight; //权值
    int parent,lchild,rchild; //双亲,左右孩子
}HTNode,*HuffmanTree;   //结点和指针
//**********select函数**************
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{ //在建立哈夫曼树的所有结点中选择权值最小的两个结点存放在s1,s2中
   int j,k=1;               
   while(HT[k].parent!=0)
       k++;
   s1=k;
   for(j=1;j<=i;++j)
      if(HT[j].parent==0&&HT[j].weight<HT[s1].weight)
   s1=j;
   k=1;
   while(HT[k].parent!=0||k==s1)
      k++;
   s2=k;
   for(j=1;j<=i;++j)
      if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1)
   s2=j;
}
//**********构建哈夫曼树***********************


void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)
{
    int m,i,s1,s2,start,c,f;
    HuffmanTree p;
   if(n<=1)
     return;
   m=2*n-1;//由得到的叶子数而计算结点总数
   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//分配存储空间
   for(p=HT+1,i=1;i<=n;++i,++p,++w)
     { p->weight=*w;//为结点初始化权值
       //cout<<endl<<"HT["<<i<<"].weight="<<p->weight<<" ";  
       printf("\nHT[%d].weight=%d ",i,p->weight);
       p->parent=0;
       p->lchild=0;
       p->rchild=0;
     }
   for(;i<=m;++i,++p)   
     { p->weight=0;
       p->parent=0;
       p->lchild=0;
       p->rchild=0;
     }//初始化双亲和左右孩子,使他们成为孤立的
  // cout<<endl<<endl<<"哈弗曼树创建的顺序如下:";
   printf("\n\n赫夫曼树创建的顺序如下:");
   for(i=n+1;i<=m;++i)
   {
      Select(HT,i-1,s1,s2); //调用select函数
      HT[s1].parent=i;
      HT[s2].parent=i;
      HT[i].lchild=s1;
      HT[i].rchild=s2;
      HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值是s1和s2权值的和
     // cout<<endl<<"HT["<<s1<<"] and HT["<<s2<<"] create";
      printf("\nHT[%d] and HT[%d] create",s1,s2);
    //  cout<<" HT["<<i<<"].weight="<<HT[i].weight;
      printf("\tHT[%d].weight=%d",i,HT[i].weight);
     
   }//每次选择最小的两个结点做左右孩子,权值和为新的结点的权值和,删去连个小的结点
   //*********哈夫曼编码*****************
   HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
   char *cd;
   cd=(char *)malloc(n*sizeof(char));
   cd[n-1]='\0';
   //cout<<endl<<endl<<"HuffmanTree编码是:"<<endl;
    printf("\n\nHuffmanTree编码是:\n");
   for(i=1;i<=n;++i)//从底下往上寻回编码
   { start=n-1;
      for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
        if(HT[f].lchild==c)
           cd[--start]='0';
         else
          cd[--start]='1';
      HC[i]=(char*)malloc((n-start)*sizeof(char));
      strcpy(HC[i],&cd[start]);
      printf("\nHT[%d] node's Huffman code is: %s",i,HC[i]);
   }
   free(cd);
}
//****************主函数部分********************
void main()              
{  HuffmanTree HT;
   HuffmanCode HC;
   int n,i;
   int *w,W[MAX_LENGTH];
  // cout<<"***********本实验实现的是哈夫曼树的建立以及编码*********";//交互信息
   printf("***********本实验实现的是赫夫曼树的建立以及编码**********");
  // cout<<endl<<"请输入哈弗曼树元素的个数: ";
   printf("\n请输入赫夫曼树元素的个数:");
  // cin>>n;
   scanf("%d",&n);
   for(i=0;i<n;++i)
   {
       //cout<<"请输入第 "<<i+1<<"个元素的权值(0~255的整数): ";
       printf("请输入第%d个元素的权值(0~255的整数):",i+1);
      // cin>>W[i];
       scanf("%d",&W[i]);
   }
   w=W;
   HuffmanCoding(HT,HC,w,n);
   getch();
}

2010-06-24 21:58
bluecoyote
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2010-4-5
收藏
得分:0 
回复 4楼 longxuan1011
呵呵,感觉c++语句比较简洁(一家之言)~~

策杖只为图雪耻,横戈原不为封侯
2010-07-06 23:53
lucky563591
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:765
专家分:2103
注 册:2009-11-18
收藏
得分:0 
我还以为是C语言
2010-07-18 08:50
快速回复:数据结构学到霍夫曼编码了,自己结合课本编了一个,有个错误解决不了, ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030316 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved