0

我目前正在尝试来自麻省理工学院开放课件的“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 时只使用“父”和“下一个”指针，如果当前的“频率”值小于下一个检查节点的“频率”值，我在下一个之前将它添加到队列中？？我在这里可能错了，但这是我感到困惑的领域之一？

下面是完整的文件。

#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”指针。如果有人冷冷地指点我一些伪代码的方向，那也会很有帮助。

4

1 回答 1

1

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

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

您要执行的操作称为“按排序顺序插入”，此处描述了一般过程：将元素插入排序列表

通常，“curr”将在您遍历链表时获取链表每个节点的值，而“prev”将获取前一个节点的值（在推进 curr 之前设置此值。）将 curr 设置为 null pq_insert 的开始很好，因为当您要插入新元素时，您需要从列表的第一个元素开始。如果您发现当前节点属于您尝试插入的节点之后，您将想知道前一个节点是什么。

于 2015-07-29T22:09:42.417 回答