c - 具有链接队列输出错误的 BST

Question

在将新节点分配给动态节点列表时遇到问题，实际上我只能获得那里的第一个节点。一旦检测到重复项，要么我没有正确打印它们(不太可能)，要么它们没有分配。一切打印正常，除了显示插入队列的第一个数字。

typedef struct lineList
{
    int lineNum;
    LIST *next;
}LIST;

typedef struct nodeTag{
   char data[80];
   LIST *lines;
   struct nodeTag *left;
   struct nodeTag *right;
} NODE;

调用添加列表

    mover = (*root)->lines;
    printf("Node already in the tree!\n");
    while(mover)
        mover = mover->next;
    mover = addToList();  //allocate memory for new node
    mover->lineNum = line; //set data

加入列表

LIST *addToList()
{
    LIST *pnew;
    pnew = (LIST *) malloc(sizeof (LIST)); //memory for LIST
    if (!pnew)
    {
        printf("Fatal memory allocation error in insert!\n");
        exit(3);
    }
    pnew->next = NULL; //set next node to NULL

    return pnew;
}

树输出到文件(我在这里也有一些节点的小问题 打印两次)

void treeToFile(NODE *root, FILE *fp)
{
    if(root->left)
    {
      treeToFile(root->left, fp);
      fprintf(fp, "%-15s",  root->data);
      printList(root->lines, fp);
      fprintf(fp, "\n");
   }
   if(root->right)
   {
      treeToFile(root->right, fp);
      fprintf(fp, "%-15s",  root->data);
      printList(root->lines, fp);
      fprintf(fp, "\n");
   }
   return;
}

打印列表

void printList(LIST *myList, FILE *fp)
{
    LIST *mover;
    mover = myList;
    while(mover) //while mover
    {
        fprintf(fp, "%5d", mover->lineNum); //line nums where string occurs
        mover = mover->next; //move to next node
    }
}

Answer 1

你失去了链接，看看这段代码:

while(mover)
    mover = mover->next;
mover = addToList();  //allocate memory for new node
mover->lineNum = line; //set data

你的 while 毫无意义......当'mover' == NULL 时你离开了 while，你想要做的是拥有最后一个节点(下一个为 null 的节点)

将您的代码更改为以下内容

// the IF below is for the case when the queue is empty, so you won't try to dereference a NULL
// in the while condition
if(mover)               
    while(mover->next)
        mover = mover->next;

if(mover) // make sure you have at least one element in the queue
{
    mover->next = addToList();  //allocate memory for new node
    mover->next->lineNum = line; //set data
}
else // if the queue is empty, then lines will return NULL and you 
       //are inserting the first element
{
    mover = addToList();
    mover->lineNum = line;
    (*root)->lines = mover; // here you are putting the new element in the first position 
                          // of your queue (It is necessary to do this because 
                          // it is currently empty!
}

上面的代码是修复代码的方法。根据您的队列的含义，我有 2 个建议。

第一:这个队列需要点单吗？插入元素的顺序对你很重要吗？

如果是，那么队列就是您所需要的，但不必为每次插入都遍历整个列表，您可以拥有这样的结构:

struct queue
 {
    LIST *first;
    LIST *last;
 }

然后您将在 last->next 中插入新元素(第一个元素不同，因为 last 在那里将为空...您需要使 next 和 first 指向该元素)

或者，如果您的顺序无关紧要，只需在列表的开头添加新元素

mover = addToList();
mover->lineNum = line;
mover->next = *(root)->lines; //supposing you are using the right side correctly in your code,  
                       // you are adding the current list as being the next of your new element

*(root)->lines = mover; //here you are saying that your list starts now at your new element