首页 文章

如何在c中的链表中实现队列?

提问于
浏览
0

我得到了这些结构声明,以实现使用循环链表的队列集合 .

typedef struct intnode {
int value;
struct intnode *next;
} intnode_t;

typedef struct {
intnode_t *rear;   // Points to the node at the tail of the 
                   // queue's linked list
int size;          // The # of nodes in the queue's linked list
} intqueue_t;

intnode_t *intnode_construct(int value, intnode_t *next)
{
    intnode_t *p = malloc(sizeof(intnode_t));
    assert (p != NULL);
    p->value = value;
    p->next = next;
    return p;
}


/* Return a pointer to a new, empty queue.
 * Terminate (via assert) if memory for the queue cannot be allocated.
 */

intqueue_t *intqueue_construct(void)
{
intqueue_t *queue = malloc(sizeof(intqueue_t));
assert(queue != NULL);

    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

我正在尝试创建一个将在指定值中排队的函数(将其附加到队列的后面),我需要考虑队列为空且队列有一个或多个元素的两种情况 . 这是我到目前为止的代码:

void intqueue_enqueue(intqueue_t *queue, int value)
{

    intnode_t *p = intnode_construct(value, NULL);

    if(queue->rear->next == NULL) {
    //the queue is empty
    queue->rear->next =p;
}     else {
    //the queue is not empty
    queue->rear=p;
}
queue->rear=p;
queue->size++;
}

这段代码给了我一个运行时错误,所以我不确定什么是错的 . 在代码中,我假设queue-> rear-> next是前面的,但我认为这是问题所在 . 非常感谢所有帮助 . 谢谢!

UPDATE--

我试图重做代码并得到了这个:

void intqueue_enqueue(intqueue_t *queue, int value)
{
assert(queue!=NULL);


  intnode_t *p = intnode_construct(value,NULL);

 if (queue->size==0){

    queue->rear=p;
    queue->size++;
    queue->rear->next=p;
    free(p);
    }
else {
    p->next = queue->rear;
    queue->rear=p;
    queue->size++;
    free(p);

    }
}

这仅在空时有效,但在非空时无效 .

1 回答

  • 2

    链表中的循环队列

    你的代码太大而无法读出,所以我在这里用来实现循环队列:

    #include using namespace std;

    // Structure of a Node
    struct Node
    {
        int data;
        struct Node* link;
    };
    
    struct Queue
    {
        struct Node *front, *rear;
    };
    
    // Function to create Circular queue
    void enQueue(Queue *q, int value)
    {
        struct Node *temp = new Node;
        temp->data = value;
        if (q->front == NULL)
            q->front = temp;
        else
            q->rear->link = temp;
    
        q->rear = temp;
        q->rear->link = q->front;
    }
    
    // Function to delete element from Circular Queue
    int deQueue(Queue *q)
    {
        if (q->front == NULL)
        {
            printf ("Queue is empty");
            return INT_MIN;
        }
    
        // If this is the last node to be deleted
        int value; // Value to be dequeued
        if (q->front == q->rear)
        {
            value = q->front->data;
            free(q->front);
            q->front = NULL;
            q->rear = NULL;
        }
        else  // There are more than one nodes
        {
            struct Node *temp = q->front;
            value = temp->data;
            q->front = q->front->link;
            q->rear->link= q->front;
            free(temp);
        }
    
        return value ;
    }
    
    // Function displaying the elements of Circular Queue
    void displayQueue(struct Queue *q)
    {
        struct Node *temp = q->front;
        printf("\nElements in Circular Queue are: ");
        while (temp->link != q->front)
        {
            printf("%d ", temp->data);
            temp = temp->link;
        }
        printf("%d", temp->data);
    }
    
    /* Driver of the program */
    int main()
    {
        // Create a queue and initialize front and rear
        Queue *q = new Queue;
        q->front = q->rear = NULL;
    
        // Inserting elements in Circular Queue
        enQueue(q, 14);
        enQueue(q, 22);
        enQueue(q, 6);
    
        // Display elements present in Circular Queue
        displayQueue(q);
    
        // Deleting elements from Circular Queue
        printf("\nDeleted value = %d", deQueue(q));
        printf("\nDeleted value = %d", deQueue(q));
    
        // Remaining elements in Circular Queue
        displayQueue(q);
    
        enQueue(q, 9);
        enQueue(q, 20);
        displayQueue(q);
    
        return 0;
    }
    

相关问题