c - 使用队列插入关卡顺序的程序有时会崩溃

Question

在C语言中，我使用队列(链表)编写了这个用于级别顺序插入的程序，但它有时会崩溃，否则会按预期工作。我使用队列来管理级别排序。我已经在 Dev C++ 和 Borland 5.5 上运行了这个程序，两者都有相同的结果。

#include<stdlib.h>
#include<stdio.h>

typedef struct ListNode
{
    struct TreeStructure *node;
    struct Listnode *next;
}*List;

typedef struct ListQueue
{
    struct ListNode *rear;
    struct ListNode *front;
}*Queue;

typedef struct TreeStructure
{
    int data;
    struct TreeStructure *left;
    struct TreeStructure *right;
}*Tree;


Queue Creation()
{
    List tmp;
    Queue Q=(Queue)malloc(sizeof(struct ListQueue));
    if(!Q)
        return NULL;
    tmp=(List)malloc(sizeof(struct ListNode));
    Q->rear=Q->front=NULL;
    return Q;
}

int isEmpty(Queue Q)
{
    return Q->front==NULL;
}

void Enqueue(Queue Q ,Tree Root )
{
    List tmp;
    tmp=(List)malloc(sizeof(struct ListNode));
    if(!tmp) {
        printf("\nMemory error");
        return;
    }
    tmp->node=Root;                 
    tmp->next=NULL;
    if(!Q->rear)
        Q->rear=tmp;
    else
    {
        Q->rear->next=(List)tmp;   // only warning here
        Q->rear=tmp;
    }

    if(!Q->front)
        Q->front=Q->rear;
}

Tree Dequeue(Queue Q)
{
    Tree node;
    List tmp;
    if(isEmpty(Q))
        printf("\nUnderflow");
    else
    {
        tmp=Q->front;
        Q->front=(List)Q->front->next;
        node=tmp->node;
        free(tmp);
        return node;
    }
}  

void DeleteQueue(Queue Q)
{
    Queue tmp;
    while((Q->front!=NULL)&&(Q->front!=Q->rear))
    {
        tmp=(Queue)Q->front;
        Q->front=(List)Q->front->next;
        free(tmp);
    }
    if(Q->rear)
        free(Q->rear);
    if(Q->front)
        free(Q->front);
    Q->rear=Q->front=NULL;
}

// Tree Insertion 

Tree Insertion(Tree Root,int data)
{
     Tree tmp,newnode,ptr;
     Queue Q;
     ptr=Root;
     newnode=(Tree)malloc(sizeof(struct TreeStructure));    
     if(!newnode) {
         printf("\nMemory Error");
         exit(1);
     }
     newnode->data=data;
     newnode->left=newnode->right=NULL;
     if(!Root)
         return newnode;
     Q=Creation();
     Enqueue(Q,Root);
     printf("\nInside Happy");
     while(!isEmpty(Q))
     {     
         Root=Dequeue(Q);        
         if(Root->left)
             Enqueue(Q,Root->left);
         else
         {
             Root->left=newnode;
             DeleteQueue(Q);
             return ptr;
         } 
         if(Root->right)
             Enqueue(Q,Root->right);
         else
         {
             Root->right=newnode;
             DeleteQueue(Q);
             return ptr;
         }

    }
    DeleteQueue(Q);
}

void Preorder(Tree Root)
{
    if(Root)
    {
        printf("\n Element is %d",Root->data);
        Preorder(Root->left);
        Preorder(Root->right);
    }
}

int main()
{
    int i;
    Tree p,Root=NULL;
    for(i=0;i<10000;i++)
    {
        Root=Insertion(Root,i+98);
    }
    printf("\nInsertion finished");
    Preorder(Root);
    getch();
}

Answer 1

您的系统内存分配可能有问题，您可以尝试其他编译器或仔细检查代码。