在 isEmpty() 队列数据结构的头节点指针中检测 NULL 的问题

Question

我写了一个队列数据结构和测试代码。所有测试都通过，直到程序到达最后一个测试。检查队列是否为空的 IF 语句应该 return FALSE 因为调用了入队并且数据被插入到队列中。

当我使用 link->head == NULL 进行测试时，测试失败。但是，如果我使用计数变量进行比较，则测试通过。这意味着队列已成功入队，打印时计数为“1”而不是“0”。

我的问题是，为什么当我使用指针测试时测试失败，而当我使用计数测试时测试通过。这些有什么理由吗？正如我期望他们以同样的方式行事。

测试代码

#include <stdio.h>
#include "queue.h"
#include "header.h"
#define RED "3[0;31m"
#define GREEN "3[0;32m"
#define RESET "3[0m"

int main()
{
    int n1 = 10, n2 = 20;
    int *retData = NULL;
    LinkedList *queue = createQueue();

    /* First Test when nothing was enqueued */
    printf("TEST Empty: ");
    if ( isQueueEmpty( queue ) == TRUE )
        printf("%sPASSED%s\n\n", GREEN, RESET);
    else
        printf("%sFAILED%s\n\n", RED, RESET); 

    /* Second Test when enqueue was called */
    enqueue( queue, &n1, 'i' );
    printf("TEST Empty (Enqueue): ");
    if ( isQueueEmpty( queue ) == FALSE )
        printf("%sPASSED%s\n\n", GREEN, RESET);
    else
        printf("%sFAILED%s\n\n", RED, RESET); 

    /* Third test when dequeue was called */
    printf("TEST Dequeue: ");
    retData = (int *)(dequeue( queue ));
    if ( *retData == 10 )
        printf("%sPASSED%s\n\n", GREEN, RESET);
    else
        printf("%sFAILED%s\n\n", RED, RESET); 
        
    printf("TEST Empty (Dequeue): ");
    if ( isQueueEmpty( queue ) == TRUE )
        printf("%sPASSED%s\n\n", GREEN, RESET);
    else
        printf("%sFAILED%s\n\n", RED, RESET); 

    /* Fourth test when enqueue is called after dequeue */
    enqueue( queue, &n2, 'i' );
    printf("TEST Empty (Enqueue): ");
    if ( isQueueEmpty( queue ) == FALSE )
        printf("%sPASSED%s\n\n", GREEN, RESET);
    else
        printf("%sFAILED%s\n\n", RED, RESET); 

    return 0;
}

队列函数

LinkedList* createQueue()
{
    LinkedList *queue = createLinkedList();
    return queue;
}

void enqueue( LinkedList *queue, void *data, char dataType )
{
    if( queue != NULL )
        insertLast( queue, data, dataType );
}

void* dequeue( LinkedList *queue )
{
    void *retData = NULL;
    if( queue != NULL )
        retData = removeStart( queue );

    return retData;
}

int isQueueEmpty( LinkedList *queue )
{
    int empty = FALSE;
    if( queue->head == NULL )
        empty = TRUE;
/*
    
    **                                                      **
    When the checking was done in such manner, the test PASSED 
    **                                                      **  
    if( queue->count == 0 )
        empty = TRUE;
    printf("%d\n", queue->count);
*/
    return empty;
}

链表

LinkedList* createLinkedList()
{
    LinkedList *list = malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    list->count = 0;
    return list;
}

void insertStart( LinkedList* list, void* inData, char valueType )
{
    /* Creating the node first */
    LinkedListNode *newNd = malloc(sizeof(LinkedListNode));
    newNd->data = inData;
    newNd->type = valueType;
    newNd->next = NULL;

    /* If head and tail is NULL, then allocate the newNd as head and tail */
    if ( list->head == NULL && list->tail == NULL )
    {
        list->head = newNd;
        list->tail = newNd;
    }
    else
    {
        /* newNd will be head, so it has new next pointer */
        newNd->next = list->head;
        list->head = newNd;
    }
    list->count++;
}

void insertLast( LinkedList* list, void *inData, char valueType )
{
    /* Creating the node first */
    LinkedListNode *newNd = malloc(sizeof(LinkedListNode));
    newNd->data = inData;
    newNd->type = valueType;
    newNd->next = NULL;

    /* If head and tail is NULL, then allocate the newNd as head and tail */
    if ( list->head == NULL && list->tail == NULL )
    {
        list->head = newNd;
        list->tail = newNd;
    }
    else
    {
        list->tail->next = newNd;   /* Current tail has new connection */
        list->tail = newNd;         /* new tail is updated */
    }
    list->count++;
}

void* removeStart( LinkedList *list )
{
    LinkedListNode *delNd = NULL;
    void *delData = NULL;

    /* Make sure the list is not empty */
    if ( list->head != NULL && list->tail != NULL )
    {
        delNd = list->head;         /* Remove start is removing from head */
        list->head = delNd->next;   /* Move to next pointer */

        delData = delNd->data;
        free(delNd); delNd = NULL;
        list->count--;
    }
    return delData;
}

void* removeLast( LinkedList *list )
{
    LinkedListNode *delNd = NULL, *travelNd = NULL;
    void *delData = NULL;

    /* Make sure the list is not empty */
    if ( list->head != NULL && list->tail != NULL )
    {
        delNd = list->tail; /* Remove last is removing from tail */

        travelNd = list->head; /* Traversal starts from head */

        /* Loop stops at the node before the tail */
        while( travelNd->next != delNd )
            travelNd = travelNd->next;  /* Move to next pointer */

        travelNd->next = NULL;
        list->tail = travelNd;

        delData = delNd->data;
        free(delNd); delNd = NULL;
        list->count--;
    }
    return delData;
}

LinkedList.h

typedef struct LinkedListNode
{
    struct LinkedListNode *next;
    void *data;
    char type;
} LinkedListNode;

typedef struct LinkedList
{
    struct LinkedListNode *head;
    struct LinkedListNode *tail;
    int count;
} LinkedList;

header.h

#ifndef BOOLEAN
#define BOOLEAN
    #define FALSE 0
    #define TRUE !FALSE
#endif

Answer 1

isEmptyQueue 仅检查 queue->head，enqueue 使用 insertLast 检查 both queue->head 和 queue->tail检查空队列。

然后是真正的错误：removeStart 从不更新 queue->tail 并且 removeLast 从不更新 queue->head 删除队列中的最后一个元素时。

简而言之，您没有正确保留不变量。

在 isEmpty() 队列数据结构的头节点指针中检测 NULL 的问题

Issue with detecting NULL in head node pointer of Queue Data Structure in isEmpty()

c

pointers

data-structures

queue

is-empty