| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1629 人关注过本帖
标题:[求助]赫夫曼树问题
只看楼主 加入收藏
happyyu
Rank: 1
等 级:新手上路
帖 子:35
专家分:0
注 册:2005-4-10
收藏
 问题点数:0 回复次数:4 
[求助]赫夫曼树问题
赫夫曼树的非递归遍历  求赫夫曼编码
搜索更多相关主题的帖子: 赫夫曼 
2005-04-20 15:19
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

//Tree.h #include<iostream> #include<stdlib.h> using namespace std;

const int MaxValue=10000; const int MaxBit=10; const int MaxN=10;

struct HaffNode{ int weight; int flag; int parent; int leftChild; int rightChild; }; struct Code{ int bit[MaxN]; int start; int weight; }; void Haffman(int weight[],int n,HaffNode haffTree[]){ int j,m1,m2,x1,x2; for(int i=0;i<2*n-1;i++){ if(i<n) haffTree[i].weight=weight[i]; else haffTree[i].weight=0; haffTree[i].flag=0; haffTree[i].parent=0; haffTree[i].leftChild=-1; haffTree[i].rightChild=-1; } for(i=0;i<n-1;i++){ m1=m2=MaxValue; x1=x2=0; for(j=0;j<n+i;j++){ if(haffTree[j].weight<m1&&haffTree[j].flag==0) { m2=m1; x2=x1; m1=haffTree[j].weight; x1=j; } else if(haffTree[j].weight<m2&&haffTree[j].flag==0){ m2=haffTree[j].weight; x2=j; } } haffTree[x1].parent=n+i; haffTree[x2].parent=n+i; haffTree[x1].flag=1; haffTree[x2].flag=1; haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild=x1; haffTree[n+i].rightChild=x2; } }

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) { Code *cd=new Code; int child,parent; for(int i=0;i<n;i++) { cd->start=n-1; cd->weight=haffTree[i].weight; child=i; parent=haffTree[child].parent; while(parent!=0) { if(haffTree[parent].leftChild==child) cd->bit[cd->start]=0; else cd->bit[cd->start]=1; cd->start--; child=parent; parent=haffTree[child].parent; } for(int j=cd->start+1;j<n;j++) haffCode[i].bit[j]=cd->bit[j]; haffCode[i].start=cd->start; haffCode[i].weight=cd->weight; } } #include "Tree.h"

void main(void) { int i,j,n=4; int weight[]={1,3,5,7}; HaffNode *myHaffTree=new HaffNode[2*n+1]; Code *myHaffCode=new Code[n]; if(n>MaxN) { cerr<<"定义的n越界!"<<endl; exit(1); } Haffman(weight,n,myHaffTree); HaffmanCode(myHaffTree,n,myHaffCode); for(i=0;i<n;i++) { cout<<"Weight="<<myHaffTree[i].weight<<'\t'<<"Code="; for(j=myHaffCode[i].start+1;j<n;j++) cout<<myHaffCode[i].bit[j]; cout<<endl; } }

enjoy youself!!!

c++/C + 汇编 = 天下无敌
2005-04-21 10:09
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
热情发的帖子,顶~~~~~~~~~~~~~~~(他是我师傅呢)

生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-04-21 10:19
牛虻
Rank: 1
等 级:新手上路
威 望:1
帖 子:472
专家分:0
注 册:2004-10-1
收藏
得分:0 

2樓事用c++做的,我用c做勒一個: #include<stdio.h> #define MAXVALUE 10000 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2-1 #define MAXBIT 10

typedef struct {char letter; int weight; int parent; int lchild; int rchild; }HNodeType;

typedef struct {char letter; int bit[MAXBIT]; int start; }HCodeType;

typedef struct {char s; int num; }Bowen;

void HuffmanTree(HNodeType HuffNode[],int n,Bowen a[]) {int i,j,m1,m2,x1,x2;

for(i=0;i<2*n-1;i++) {HuffNode[i].letter=NULL; HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1;} for(i=0;i<n;i++){HuffNode[i].weight=a[i].num;HuffNode[i].letter=a[i].s;} for(i=0;i<n-1;i++) {m1=m2=MAXVALUE; x1=x2=0; for(j=0;j<n+i;j++) { if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) {m2=m1;x2=x1; m1=HuffNode[j].weight; x1=j;} else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2) {m2=HuffNode[j].weight; x2=j;} } HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i; HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2;}}

void HuffmanCode(int n,Bowen a[]) {HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i,j,c,p; HuffmanTree(HuffNode,n,a); for(i=0;i<n;i++) {cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=-1) {if(HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HuffNode[c].parent;} for(j=cd.start+1;j<n;j++) HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start;} for(i=0;i<n;i++) {printf("%c ",HuffNode[i].letter); for(j=HuffCode[i].start+1;j<n;j++) printf("%d",HuffCode[i].bit[j]); printf("\n");} }

main() {Bowen data[30]; char s[100],*p; int i,count=0;clrscr(); printf("Input some letters:"); scanf("%s",&s); for(i=0;i<30;i++) {data[i].s=NULL; data[i].num=0;} p=s;

while(*p) {for(i=0;i<=count+1;i++) {if(data[i].s==NULL) {data[i].s=*p;data[i].num++;count++;break;} else if(data[i].s==*p) {data[i].num++;break;}} p++;} printf("\n"); printf("different letters:%d\n",count); for(i=0;i<count;i++) {printf("%c ",data[i].s); printf("weight:%d",data[i].num); printf("\n\n");} HuffmanCode(count,data); getch();}

[此贴子已经被作者于2005-4-23 18:45:50编辑过]


土冒
2005-04-23 18:40
牛虻
Rank: 1
等 级:新手上路
威 望:1
帖 子:472
专家分:0
注 册:2004-10-1
收藏
得分:0 
但是在下译码功能只知道算法就是编不出来.太怪胎了,求激情帮忙

土冒
2005-04-23 19:10
快速回复:[求助]赫夫曼树问题
数据加载中...
 
   



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

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