c - Queue中的node_add，只插入前3个作为前中后

Question

我的插入函数对于空队列、前后相等的队列以及多一个队列都可以正常工作。在那之后似乎有一个逻辑错误。我只有 2 小时的时间来提交这个。

测试上升和下降的输出

测试升序队列 插入:42 17 -12 9982 476 2912 -22 3291213 7782

删除:17 3291213 7782

测试降序队列 插入:42 17 -12 9982 476 2912 -22 3291213 7782

删除:42 -22 7782

测试 FIFO 队列 插入:42 17 -12 9982 476 2912 -22 3291213 7782

删除:42 17 -12 9982 476 2912 -22 3291213 7782

void que_insert( QueueADT queue, void *data ) {
    struct node *temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->data= data;
    node *currNode;
                //currNode = (struct node*)malloc(sizeof(struct node));
    currNode = queue->front;
    //cmp = &(queue->cmprFunc);
    if ( queue->front != NULL ) {
            if ( queue->cmprFunc == NULL ) {        //if the cmp_func is FIFO

                queue->rear->next = temp;
                queue->rear= temp;
                queue->rear->next=NULL;
                if ( queue->front == queue->rear ) {
                    currNode->next = temp;
                    queue->rear = temp;
                    temp->next= NULL;
                    }
            } else {

                while ( currNode->next != NULL ){
                    if (( (*(queue->cmprFunc))(currNode->next->data, temp->data) < 0 ) ||
                            ((*(queue->cmprFunc))(currNode->next->data, temp->data) == 0 ) ) {
                        temp->next = currNode->next;
                        currNode->next = temp;
                        break;

                    } else  {
                        currNode = currNode->next;
                        if (currNode->next != NULL )  {
                            currNode->next = temp;
                            queue->rear = temp;
                            temp->next = NULL;
                        }
                                            //exit_failure  
                    }
                }
                if ( queue->front == queue->rear ) {

                    if (( (*(queue->cmprFunc))(currNode->data, temp->data) < 0 ) ||
                            ((*(queue->cmprFunc))(currNode->data, temp->data) == 0 ) ) {
                            queue->rear = temp;
                            queue->front->next = queue->rear;
                            temp->next= NULL;
                        } else {
                            queue->front = temp;
                            temp->next = temp;

                        }
                    }
                //printf("Front is equal to next %i\n", (queue->front == queue->rear));
            }
    } else {                                                //( queue->front == NULL )
        queue->front = temp;
        queue->rear= queue->front;
        queue->front->next= queue->rear->next = NULL;

        }
    }

比较函数根据以下条件返回一个 int:

*** < 0 a < b
 = 0    a == b
 > 0    a > b***

其中“>”和“<”取决于被比较的数据

typedef struct node {
    void* data;
    struct node *next;
}node;


struct queueStruct {
    struct node *front;                     /* pointer to front of queue */
    struct node *rear;                      /* pointer to rear of queue  */
    int (*cmprFunc)(const void*a,const void*b);
    //size_t num;                               /* The compare function used for insert */
};

typedef struct queueStruct *QueueADT;       //typedef inserted for pointers, name is QueueADT

#define _QUEUE_IMPL_
#include "queueADT.h"

/// create a queue that is either sorted by cmp or FIFO
//function with two void
QueueADT que_create( int (*cmp)(const void*a,const void*b) ) {

    QueueADT new;
    new = (QueueADT)malloc(sizeof(struct queueStruct));

    if (cmp == NULL) {
        //do I create a new pointer to the cmp_int64?
        new->front = NULL;
        new->rear = NULL;
        new->cmprFunc = NULL;

    } else {
        new->cmprFunc = cmp;
        new->front = NULL;
        new->rear = NULL;
    }

    return ( new );
}

Answer 1

您的que_insert:

void que_insert( QueueADT queue, void *data ) {
    struct node *temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->data= data;
    node *currNode, *prevNode = NULL;

    currNode = queue->front;

    if(currNode == NULL){
        //first node to add
        temp->next = NULL;
        queue->front = temp;
        queue->rear = temp;

        return;
    }

    while(currNode != NULL){
        if( /* comparison is negative */ ){
            temp->next = currNode;
            if(prevNode != NULL){
                prevNode->next = temp;
            }
            else{
                queue->front = temp;
            }

            return;
        }

        prevNode = currNode;
        currNode = currNode->next;
    }

    //add to the end
    prevNode->next = temp;
    temp->next = NULL;
    queue->rear = temp;
}