链接队列输出错误的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;

调用addtolist

    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

你的时间毫无意义…当'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!
}

上面的代码是修复代码的方法。我有两个建议，这取决于你的队列意味着什么。

第一:这个队列需要排序吗?元素插入的顺序对你有影响吗?

如果是，那么一个队列就是你所需要的，而不是每次插入都要遍历整个列表，你可以有一个这样的结构体:

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