编译没有错误,运行失败
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define STACK_INIT_SIZE 100//存储空间初始分配量 没分号“;”
#define STACKINCREMENT 10 //存储空间分配增量
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
//在HT[1..i-1]选择parent为0且weight最小的两个结点,
//其序号为最小s1和次小s2(若parent≠0,则说明被选取过不能再选)
//s1s2并不是指的weight权值,而是最(次)小的这个字符前面的编号(后面需要填进lchild、rchild)
void Select(HuffmanTree p,int n,int *s1,int *s2)
{
int i;
int min = 99999;
for(i=1;i<=n;i++){
if(p[i].parent == 0){
if(p[i].weight <= min){
min = p[i].weight;
*s1 = i;
}
}
}
min = 99999;
for(i=1;i<=n;i++){
if(p[i].parent==0){
if(p[i].weight<=min && i!=*s1){
min = p[i].weight;
*s2 = i;
}
}
}
}
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n){
//n字符 m节点 HT空间
int m,i;
HuffmanTree p;
//int w[8] = {5,29,7,8,14,23,3,11};
m = 2*n-1;
if(n<=1){return;}
//加上一个未用的0号单元
HT = (HuffmanTree *)malloc((m+1)*sizeof(HTNode));
//一:初始化,得a图:
//(1)把已有字符(1-8) 权重赋值w,左右孩子及parent赋值为0,p指向第二个单元(非0第一个)
for(p=*HT+1,i=1 ; i<=n ; ++i,++p,++w){//[问题p=HT+1?]看和鸿昌的聊天记录
//*p={*w,0,0,0};
//错误原因: 赋值数组不能分着写
//http://zhidao.baidu.com/link?url=jZOgI5PGVycg1v6c1pJ2AlDI3J6fiDLUQQ-1FkGjGzrXTE-hYQusYkoVQlM-EBhr3IjdF9d1wy-o_6elz6m2hald8u0LVM1EUzDaTZ6Rs7e
(*p).weight = *w;
(*p).parent = 0;
(*p).lchild = 0;
(*p).rchild = 0;
}
//(2)把未知字符(9-15) 权重、左右孩子及parent赋值为0, p指向上面跳出来的 未知字符的第一个 9
for(;i<=m;++i,++p){
(*p).weight = 0;
(*p).parent = 0;
(*p).lchild = 0;
(*p).rchild = 0;
}
//二:建立赫夫曼树,得到b图
//在HT[1..i-1]选择parent为0且weight最小的两个结点,其序号为最小s1和次小s2(若parent≠0,则说明被选取过不能再选)
for(i=n+1;i<=m;++i){ //n+1 即后面未知字符 (比如9开始到15)
int s1,s2;
//void Select(HuffmanTree HT,int q,int *s1,int *s2){
Select(*HT,i-1,&s1,&s2);
//select(*HT,i-1,&s1,&s2);
//给s1 s2的parent赋值为当前i 编号
(*HT)[s1].parent = i;
(*HT)[s2].parent = i;
//给当前i 的lchild和rchild赋值为s1、s2编号 ,给当前i 的 weight赋值为二者权重之和
//设最小的作左子树,次小的作右子树
(*HT)[i].lchild = s1;
(*HT)[i].rchild = s2;
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
//三:从叶子到根逆向求每个结点字符的赫夫曼编码
//存放赫夫曼编码的cd
char cd[n];
int c,f;
//分配n个字符编码的头指针向量HC
//HuffmanTree HC;报错类型:declaration of'HTNode* HC'shadows a parameter 原因:函数参数里已有HC的定义导致重复
HC = (HuffmanCode *)malloc((n+1)*sizeof(char *));
//编码结束符 如声明cd[8],0-7中最后一个结束符则为cd[7]
cd[n-1] = '\0';//书上写错了,应该是'\0'
//1-8逐个求
for(i=1;i<=n;++i){
//编码结束符位置
int start = n-1;
//c=i,f指向当前字 符i的双亲 双亲不为0则循环 经过循环一次后,当前字符变成它的双亲,以此逆向递推
//小细节:--start 如图
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent){
if((*HT)[f].lchild ==c){
cd[--start]='0';//书上写错了,应该是单引号'0'
}else{
cd[--start]='1';
}
//for循环结束后,得到cd,为第i个字符分配存储空间HC
(*HC)[i] = (char *)malloc((n-start)*sizeof(char));
//start目前指到最前面了,所以将cd复制(strcpy)给HC
/*原型声明:char *strcpy(char* dest, const char *src);
头文件:#include <string.h> 和 #include <stdio.h>
功能:把从src地址开始且含有NULL结束符的字符串复制到以dest开始的地址空间*/
strcpy((*HC)[i],&cd[start]);
}
}
free(cd);
}
int main(void){
HuffmanTree HT;
HuffmanCode HC;
int n;
printf("请输入字符个数(空格间隔):");
scanf("%d",&n);
int i;
int *w=NULL;
w=(int*)malloc(n*sizeof(int));
printf("请依次输入权值(空格间隔):");
for(i=0;i<n;i++){
scanf("%d",w+i);
}
HuffmanCoding(&HT,&HC,w,n);
for(i=1;i<=n;i++){
puts(HC[i]);//???
}
}
已解决。。。