[暑期补课]数据结构试验第三题赫夫曼树
// 哈夫曼编码.cpp : 定义控制台应用程序的入口点。//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree;
typedef char * * HuffmanCode;
int min(HuffmanTree t,int i)
{
int j,flag;
unsigned int k = 100000;
for(j=1;j<=i;j++)
if(t.weight<k&&t.parent==0)
k = t.weight,flag = j;
t.parent = 1;
return flag;
}
void select(HuffmanTree t,int i, int *s1, int *s2)//在HT选择parent为0且weight最小的两个结点，其序号分别为s1和s2.
{
int temp;
*s1 = min(t,i);
*s2 = min(t,i);
if(*s1>*s2)
{
temp = *s1;
*s1 = *s2;
*s2 = temp;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int i,s1,s2,start;
HuffmanTree p;
if( n<=1 )
return;
int m = 2*n - 1;//n个叶子结点的赫夫曼树共有2n-1个结点（保证是正则二叉树）
HT = (HuffmanTree) malloc( (m+1)*sizeof(HTNode) );//0号单元未用
for( p = HT+1,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)
{
select(HT,i-1,&s1,&s2);
HT.parent=i;
HT.parent=i;
HT.lchild=s1;
HT.rchild=s2;
HT.weight=HT.weight+HT.weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
char *cd;
cd=(char*)malloc(n*sizeof(char));
cd='\0';
int c,f;
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=HT.parent;f!=0;c=f,f=HT.parent)
if(HT.lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC=(char*)malloc((n-start)*start*sizeof(char));
strcpy(HC,&cd);
}
free(cd);
}
int main()
{
int w;
HuffmanTree ht;
HuffmanCode hc;
int n;
cout<<"请输入需编码个数"<<endl;
cin>>n;
cout<<"请输入权值";
for (int i=0;i<n;i++)
{
cin>>w;
}
HuffmanCoding(ht,hc,w,n);
for (int i=1;i<=n;i++)
{
printf("%d的赫夫曼编码：%s\n",ht.weight,hc);
}
system("pause");
}
68 69 70 行是HT<i> ? seleveny 发表于 2012-8-20 06:32 static/image/common/back.gif
68 69 70 行是HT ?
我程序里是[]不知道为啥拷贝过来就成了<>
应该是代码显示的问题 好。。、 xywhere 发表于 2013-8-13 19:37
好。。、
这是在挖数据结构的节奏啊~~~~我也跟来瞅瞅 xywhere 发表于 2013-8-13 19:37
好。。、
这是在挖数据结构的节奏啊~~~~我也跟来瞅瞅 vo_ 发表于 2013-8-13 20:06
这是在挖数据结构的节奏啊~~~~我也跟来瞅瞅
必须的啊 这都被你发现了。。很隐秘的 vo_ 发表于 2013-8-13 20:06
这是在挖数据结构的节奏啊~~~~我也跟来瞅瞅
。。。。。 xywhere 发表于 2013-8-13 20:25
必须的啊 这都被你发现了。。很隐秘的
你挖掘~~我跟踪哈哈 vo_ 发表于 2013-8-13 21:36
你挖掘~~我跟踪哈哈
最新的 帖子 。。快去跟踪 感谢学长，nice
页:
[1]