私は現在、MIT オープンコースウェアの「C での実用的なプログラミング」の演習を試みています。演習はハフマン符号化です。私が問題を抱えているのは lab2 パート 2 です。主に pq_insert() メソッド。ノードの挿入をどのように実行する必要があるかについて、かなり混乱していますか? 以下に .c ファイル全体を掲載します。挿入操作にはsudoコードが必要だと思います。
私のノードは基本的に構造体です（以下に示します）
struct tnode
{
struct tnode* left; /*used when in tree*/
struct tnode*right; /*used when in tree*/
struct tnode*parent;/*used when in tree*/
struct tnode* next; /*used when in list*/
float freq;
int isleaf;
char symbol;
};
「左」と「右」のポインターが私の PQ 構築で使用されていないと思いますか? PQ を作成するときに「親」ポインターと「次の」ポインターを使用するだけで、現在の「頻度」値が次にチェックされるノードの「頻度」値よりも小さい場合、これを次の前にキューに追加しますか?? 私はここで間違っているかもしれませんが、これは私が混乱している分野の 1 つです??
以下は完全なファイルです。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SYMBOLS 255
#define MAX_LEN 7
struct tnode
{
struct tnode* left; /*used when in tree*/
struct tnode*right; /*used when in tree*/
struct tnode*parent;/*used when in tree*/
struct tnode* next; /*used when in list*/
float freq;
int isleaf;
char symbol;
};
/*global variables*/
char code[MAX_SYMBOLS][MAX_LEN];
struct tnode* root=NULL; /*tree of symbols*/
struct tnode* qhead=NULL; /*list of current symbols*/
struct cnode* chead=NULL;/*list of code*/
/*
@function talloc
@desc allocates new node
*/
struct tnode* talloc(int symbol,float freq)
{
struct tnode* p=(struct tnode*)malloc(sizeof(struct tnode));
if(p!=NULL)
{
p->left=p->right=p->parent=p->next=NULL;
p->symbol=symbol;
p->freq=freq;
p->isleaf=1;
}
return p;
}
/*
@function display_tnode_list
@desc displays the list of tnodes during code construction
*/
void pq_display(struct tnode* head)
{
struct tnode* p=NULL;
printf("list:");
for(p=head;p!=NULL;p=p->next)
{
printf("(%c,%f) ",p->symbol,p->freq);
}
printf("\n");
}
/*
@function pq_insert
@desc inserts an element into the priority queue
NOTE: makes use of global variable qhead
*/
void pq_insert(struct tnode* p)
{
struct tnode* curr=NULL;
struct tnode* prev=NULL;
printf("inserting:%c,%f\n",p->symbol,p->freq);
if(qhead==NULL) /*qhead is null*/
{
/*TODO: write code to insert when queue is empty*/
//qhead = null means we nead to set something as the heeed!
//possibly p???????
qhead = p;
return;
//not too sure bout this.
}
/*TODO: write code to find correct position to insert*/
//potentially check if 'symbol' less
//than ??
if(curr==qhead)//curr is always set to null when method called????
{
/*TODO: write code to insert before the current start*/
curr->parent = p;
curr = p;
}
else /*insert between prev and next*/
{
/*TODO: write code to insert in between*/
}
}
/*
@function pq_pop
@desc removes the first element
NOTE: makes use of global variable qhead
*/
struct tnode* pq_pop()
{
struct tnode* p=NULL;
p = qhead;
if(qhead->next != NULL)
{
qhead = qhead->next;
}
/*TODO: write code to remove front of the queue*/
printf("popped:%c,%f\n",p->symbol,p->freq);
return p;
}
/*
@function build_code
@desc generates the string codes given the tree
NOTE: makes use of the global variable root
*/
void generate_code(struct tnode* root,int depth)
{
int symbol;
int len; /*length of code*/
if(root->isleaf)
{
symbol=root->symbol;
len =depth;
/*start backwards*/
code[symbol][len]=0;
/*
TODO: follow parent pointer to the top
to generate the code string
*/
printf("built code:%c,%s\n",symbol,code[symbol]);
}
else
{
generate_code(root->left,depth+1);
generate_code(root->right,depth+1);
}
}
/*
@func dump_code
@desc output code file
*/
void dump_code(FILE* fp)
{
int i=0;
for(i=0;i<MAX_SYMBOLS;i++)
{
if(code[i][0]) /*non empty*/
fprintf(fp,"%c %s\n",i,code[i]);
}
}
/*
@func encode
@desc outputs compressed stream
*/
void encode(char* str,FILE* fout)
{
while(*str)
{
fprintf(fout,"%s",code[*str]);
str++;
}
}
/*
@function main
*/
int main()
{
/*test pq*/
struct tnode* p=NULL;
struct tnode* lc,*rc;
float freq[]={0.01,0.04,0.05,0.11,0.19,0.20,0.4};
int NCHAR=7; /*number of characters*/
int i=0;
const char *CODE_FILE="code.txt";
const char *OUT_FILE="encoded.txt";
FILE* fout=NULL;
/*zero out code*/
memset(code,0,sizeof(code));
/*testing queue*/
pq_insert(talloc('a',0.1));
pq_insert(talloc('b',0.2));
pq_insert(talloc('c',0.15));
/*making sure it pops in the right order*/
puts("making sure it pops in the right order");
while((p=pq_pop()))
{
free(p);
}
qhead=NULL;
/*initialize with freq*/
for(i=0;i<NCHAR;i++)
{
pq_insert(talloc('a'+i,freq[i]));
}
/*build tree*/
for(i=0;i<NCHAR-1;i++)
{
lc=pq_pop();
rc=pq_pop();
/*create parent*/
p=talloc(0,lc->freq+rc->freq);
/*set parent link*/
lc->parent=rc->parent=p;
/*set child link*/
p->right=rc; p->left=lc;
/*make it non-leaf*/
p->isleaf=0;
/*add the new node to the queue*/
pq_insert(p);
}
/*get root*/
root=pq_pop();
/*build code*/
generate_code(root,0);
/*output code*/
puts("code:");
fout=fopen(CODE_FILE,"w");
dump_code(stdout);
dump_code(fout);
fclose(fout);
/*encode a sample string*/
puts("orginal:abba cafe bad");
fout=fopen(OUT_FILE,"w");
encode("abba cafe bad",stdout);
encode("abba cafe bad",fout);
fclose(fout);
getchar();
/*TODO: clear resources*/
return 0;
}
私はこれを本当に考えすぎていると思います。左右のポインターは、優先キューが作成された後、ツリーの構築に使用されるだけです。私を混乱させたもう1つのことは、pq_insert()が呼び出されるたびに「curr」がnullに設定されることでしたか? おそらくcurrがqheadに設定されていると思います。その「freq」値が「qhead」freq 値よりも小さいと仮定しますか? また、宿題などとしてこれを行っているわけではありません。とにかく、どんな入力でも大歓迎です。
また、pq_insert メソッドで「curr」および「prev」ポインターを使用する方法もよくわかりません。誰かが私にいくつかの疑似コードの方向性を教えてくれたら、それもかなり役に立ちます。