Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to implement a linked list queue in C language". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how C language implements a linked list queue.

Implementation of linked list queue in C language data structure

1. Write at the front

A queue is a linear table that follows the first-in-first-out principle as opposed to the stack.

This code is the C language implementation code of the pseudo code above the data structure book of Professor Yan Weimin.

The code that is not included in the decomposition code is as follows:

# include # include # define OK 1#define ERROR 0typedef int QElemtype;typedef int status

two。 Code decomposition

2.1 structural definition of queues and nodes

Typedef struct QNode / / structure definition of a pair of nodes {QElemtype data; struct QNode * next;} QNode,*QueuePtr;typedef struct {/ / structure definition of a pair of queues QueuePtr head; QueuePtr rear;} LinkQueue

| description:

1. The node of the queue should first save the element, and then guide the location of the next element, which is the basis and key to the implementation of linear storage.

two。 Two node pointers are defined in the queue, and the first head is used to represent the head of the line, allowing elements to be removed. In contrast, rear is used to represent the end of the line, allowing elements to be inserted.

3. Why is it so defined?

2.2 initialize and recycle queues

Status initQueue (LinkQueue* que) / / initialize the queue {que- > head=que- > rear= (QueuePtr) malloc (sizeof (QNode)); if (! que- > head) / / this code initializes the user-defined data types in the queue return ERROR; return OK;} status destoryQueue (LinkQueue* que) / / Recycle queue {while (que- > head) {que- > rear= que- > head- > next; free (que- > head); que- > head=que- > rear } return OK;}

| description:

1. Initialization is as simple as allocating space for two important nodes in the queue.

two。 The recovery of the queue is very ingenious.

The loop condition is that the queue header node head exists {where rear acts as a temporary variable, constantly pointing to head- > next while releasing head. In this way, queues including head nodes can be cleaned up cleanly. }

2.3 add and remove elements

Status enQueue (LinkQueue* que,QElemtype e) {QueuePtr p = (QueuePtr) malloc (sizeof (QNode)); if (! p) / / if the space is not available, exit return ERROR; p-> data=e; p-> next=NULL; que- > rear- > next= p; que- > rear=p; return OK;} status delQueue (LinkQueue* que,QElemtype * t) {if (que- > rear==que- > head) return ERROR; / / list as empty QueuePtr p = que- > head- > next; * troomp-> data Que- > head- > next=p- > next; if (que- > rear==p) / / this decision is to ensure that the rear pointer is reset when the queue is cleared. Que- > rear=que- > head; free (p); return OK;}

| description:

1. The idea for adding elements: create a new node and assign a data,next to it. Connect the tail of the queue to this node and update the tail node.

two。 The idea of deleting elements: first determine whether the node is empty? Then use the temporary node to get the first node from the queue head, that is, head- > next, (our head node does not save the element), get its address, update the first node referred to by the team head node to get the value and release the address space.

2.4 traversal queues and test methods

Status viewQueue (LinkQueue* que) {if (que- > rear = = que- > head) return ERROR; QueuePtr p = que- > head- > next; while (p) {printf ("val:%d", p-> data); pairp-> next;} return OK;} int main (int argc, char * * argv) {LinkQueue myQueue; initQueue (& myQueue); for

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.