В настоящее время я пробую упражнение из «практического программирования на C» от MIT opencourseware. упражнение по кодированию Хаффмана. это 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? Я просто использую указатели «parent» и «next» при создании PQ, и если текущее значение «freq» меньше, чем значение «freq» следующего проверенного узла, я добавляю это в очередь перед следующим ?? Я могу ошибаться здесь, но это одна из областей, в которых я запутался??
ниже полный файл.
#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;
}
я думаю, что я слишком много думал об этом, и левый и правый указатели просто используются в построении дерева после создания очереди приоритетов. еще одна вещь, которая меня смутила, заключалась в том, что для «curr» устанавливается значение null всякий раз, когда вызывается pq_insert()? Я думаю, может быть, curr настроен на qhead. предполагая, что его значение «freq» меньше значения частоты «qhead»? Кроме того, я не делаю это как домашнюю работу или что-то в этом роде. в любом случае, любой вклад приветствуется.
также не совсем уверен, как использовать указатели «curr» и «prev» в методе pq_insert. если кто-нибудь укажет мне на какой-нибудь псевдокод, это тоже будет очень полезно.
