插入到优先级队列.MIT c编程开放课程

Question

我目前正在尝试麻省理工学院开放课程"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;
};

我假设指针"左"one_answers"右"不用于我的PQ结构?在创建PQ时，我只是使用"父"one_answers"下一个"指针，如果当前的"频率"值小于下一个检查节点的"频率"值，我将其添加到下一步之前的队列中?我可能在这里错了，但这是我困惑的领域之一??

是完整的文件。

#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,%fn",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,%fn",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,%sn",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 %sn",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;
}

我认为我是过度思考这真的和左和右指针只是在优先级队列创建后用于树结构。另一件让我感到困惑的事情是，每当pq_insert()被调用时，"curr"被设置为null ?我想也许curr被设置为qhead。假设其"频率"值小于"qhead"频率值?我也不是把它当做家庭作业。无论如何，任何输入都是感激的。

也不确定如何在pq_insert方法中使用"curr"one_answers"prev"指针。如果有人能给我指出一些伪代码的方向，那也会很有帮助。

Answer 1

实现优先级队列的常见方法之一是作为堆，堆通常表示为树结构。然而，open encourseware Lab 2 Part B似乎特别提到了这个优先队列的链表实现。

因此，你假设"左"one_answers"右"指针不会被使用是正确的。此外，"父"指针可能不会被使用，因为注释将其引用为基于树的实现。对于一个简单的链表来说，"下一个"指针就足够了，因为每个节点都指向从"头"节点或列表开始的下一个节点。

你想要做的事情被称为"按排序顺序插入"，一般的过程描述在这里:将元素插入到排序列表

一般来说，"curr"将在迭代链表时获取链表中每个节点的值，而"prev"将获取前一个节点的值(在推进curr之前设置此值)。在pq_insert开始时将curr设置为null是可以的，因为当您要插入新元素时，您将希望从列表的第一个元素开始。如果您发现当前节点位于您试图插入的节点之后，那么您需要知道前一个节点是什么。