2017-12-03 265 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; 
}