algorithm - 插入优先队列。 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;
};

我假设我的 PQ 构造中没有使用指针“left”和“right”？我在创建 PQ 时只使用“parent”和“next”指针，如果当前“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;
}

我想我真的想多了，左右指针只是在创建优先级队列后用于树构造。另一件让我感到困惑的事情是，每当调用 pq_insert() 时，“curr”都设置为 null？我在想也许 curr 被设置为 qhead。假设它的“频率”值小于“qhead”频率值？我也不会把这当作家庭作业或其他任何事情来做。无论如何，任何意见表示赞赏。

也不确定如何在 pq_insert 方法中使用“curr”和“prev”指针。如果有人冷淡地向我指出一些伪代码的方向，那也会非常有帮助。

Answer 1

实现优先级队列的一种常见方法是堆，堆通常表示为树结构。但是，OpenCourseware Lab 2 Part B 似乎专门提到了此优先级队列的链表实现。

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

您要执行的操作称为“按排序顺序插入”，此处描述了一般过程:inserting element into a sorted list

一般来说，“curr”会在你遍历它时取链表的每个节点的值，而“prev”会取前一个节点的值(在你推进curr之前设置这个。)设置curr为pq_insert 开头的 null 很好，因为当您要插入新元素时，您会希望从列表的第一个元素开始。如果您发现当前节点属于您尝试插入的节点之后，您将想知道前一个节点是什么。