情報源(情報記号の集合)
情報記号 今回はAからZまで26シンボルとします。
出現頻度は面倒なので、正の整数値(すなわち出現回数を数え上げたもの)
としてAからZそれぞれに与えてください。
この出現頻度はmainに直接書いても良いし、
ファイルや標準入力から読み込んでも、何でも結構です。
出現頻度をもとにハフマン木を作成する関数を実装してください。
デバッグのために情報記号(たとえばBとか)を入力すると
対応する符号語(011...1とか)を表示する関数を
作成するとよいかもしれません。
------------------------------------------------------------------------------------------
この課題に対して以下のようなプログラムを書きました。(未完成)
ハフマン木を連結リストを用いて作成するところまでは出来たのですが、
最後にそのハフマン木を辿って、入力されたそれぞれの情報記号に対応する符号語を表示させる部分
(最後のprintf("\n-normal end-\n");の手前)が書けなくて困っております。
どのように書けば良いか教えていただけないでしょうか。よろしくお願いします。
#include <stdio.h>
#include <stdlib.h>
#define NCHS 2048
#define AST '*'
typedef struct node {
char asc;
int frq;
struct node *nxt;
struct node *low;
struct node *hgh;
} NOD;
void frq256(int frq[256],char chs[]){
char *c=chs;
while(*c!='\0'){
frq[*c]++;
c++;
}
return;
}
NOD *create(char asc,int frq){
NOD *nod;
nod = (NOD*)malloc(sizeof(NOD));
if(nod==NULL){
printf("malloc failed for %c(%d), exit job.\n",asc,frq);
exit(1);
}
nod->asc = asc;
nod->frq = frq;
nod->nxt = NULL;
nod->low = NULL;
nod->hgh = NULL;
return nod;
}
NOD *insert(NOD *top,NOD *nod){
NOD *pre;
NOD *nxt;
int frq=nod->frq;
if(top==NULL){
top = nod;
}else if(frq<=top->frq){
nod->nxt = top;
top = nod;
}else{
pre = top;
nxt = top->nxt;
while(nxt!=NULL){
if(frq<=nxt->frq) break;
pre = nxt;
nxt = nxt->nxt;
}
if(nxt!=NULL) nod->nxt = nxt;
pre->nxt = nod;
}
return top;
}
int main(void){
int frq[256]={0};
char chs[NCHS];
char ABC;
NOD *top=NULL;
NOD *nod;
printf("文字列 > "); fgets(chs,NCHS,stdin);
frq256(frq,chs);
for(ABC='A';ABC<='Z';ABC++){
if(frq[ABC]>0){
nod = create(ABC,frq[ABC]);
top = insert(top,nod);
}
}
printf("LINK-LIST:");
nod = top;
while(nod!=NULL){
printf(" %c(%d)",nod->asc,nod->frq);
nod = nod->nxt;
} printf("\n");
while(top->nxt!=NULL){
nod = create(AST,top->frq+(top->nxt)->frq);
nod->low = top;
nod->hgh = top->nxt;
printf("new node of tree(%c:%d)\n",nod->asc,nod->frq);
printf(" ->low=(%c:%d)\n",nod->low->asc,nod->low->frq);
printf(" ->hgh=(%c:%d)\n",nod->hgh->asc,nod->hgh->frq);
top = top->nxt->nxt;
nod->low->nxt = NULL;
nod->hgh->nxt = NULL;
top = insert(top,nod);
}
printf("\n-normal end-\n");
return 0;
}