2017-12-03 269 views
0

为了实现使用循环链表的队列集合,我给了这些结构声明。如何在c中的链表中实现一个队列?

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); 

    } 
} 

这只有当它是空的,但是当它不是不是空的。在链表

+0

它必须是一个循环链表吗?它使事情复杂化,如果允许前后指针,则不需要队列。 –

+0

是的,这是我得到的 – student17

回答

2

循环队列

你的代码太大读出,所以在这里我用它来实现循环队列:使用命名空间std

的#include ;

// 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; 
}