c语言实现链队列的基本功能

秒速五厘米 2022-05-17 02:26 211阅读 0赞

**链队列，实际上是一个带有头指针和尾指针的单链表，头指针指向头节点（不存放数据），尾指针指向队尾节点，虽然用头指针可以确定一个单链表，但是插入操作是在队尾进行，如果没有尾指针，会变得复杂**

**初始化：**

void init(pQueue pq){
    	pq->front=pq->rear=(pNode)malloc(sizeof(Node));
    }

注意：（1）.为头指针和尾指针申请内存

**入队:**

void enqueue(pQueue pq,int x){
    	pNode pNew=(pNode)malloc(sizeof(Node));
    	pNew->data=x;
    	pNew->next=NULL;
    	pq->rear->next=pNew;
    	pq->rear=pNew;
    }

注意：（1）.入队是在队尾进行，所以需要尾指针

**出队:**

void dequeue(pQueue pq,int *e){
    	pNode pTemp=(pNode)malloc(sizeof(Node));
    	pTemp=pq->front->next;
    	*e=pTemp->data;
    	pq->front->next=pTemp->next;
    	free(pTemp);
    }

注意：（1）.出队是在队头进行

（2）.记得free（pTemp），因为一开始申请了一块内存

（3）.用e来存储数据，方便在main函数中处理，int \*p是定义一个指针p，p是一个地址，所以p=&a（或者一开始就用int \*p=&a），然后printf（“%d”，\*p）,是输出变量a的值，printf（"%d",&p），是输出一个地址，因为指针p也是一个变量，也有自己的地址

**求队列长度:**

int QueueLength(pQueue pq){
    	int count=0;
    	pNode p=pq->front->next;
    	while(p!=NULL){
    	count++;
    	p=p->next;
    	}
    	printf("\n");
    	return count;
    }

注意：（1）.while循环要跳出，p要等于null，这就需要入队把pNew->next=NULL

**遍历队列:**

void show_queue(pQueue pq){
    	pNode p=pq->front->next;
    	printf(" 当前元素从头到尾:");
    	while(p!=NULL){
    		printf("%d ",p->data);
    		p=p->next;
    	}
    }

**main函数:**

void main(){
    	int count;
    	int x;
    	int e;
    	Queue q;
    	init(&q);
    	printf("_____入队10个元素_____");
    	for(int i=0;i<10;i++){
    		enqueue(&q,i);
    		count=QueueLength(&q);
    		printf("%d入队,当前队列元素个数:%d ",i,count);
    		show_queue(&q);
    	}
    	printf("\n_____出队5个元素_____");
    	for(int i=0;i<5;i++){
    		dequeue(&q,&x);
    		count=QueueLength(&q);
    		printf("%d出队,当前队列元素个数:%d ",x,count);
    		show_queue(&q);
    	}
    	GetHead(&q,&e);
    	printf("\n当前队头为:%d\n",e);
    	system("pause");
    }

注意：（1）.如果定义的是结构体指针，比如pQueue pq（pq是地址），就应该申请一块内存，也可以用Queue q，然后&q取地址传入函数，这样就不用申请内存了

（2）.入队出队可以用for循环提高效率，同时通过传入&x，把x的值传出到main函数，方便调用

（3）.xx删除，当前还有xx个元素，从头到尾是xx，这样一目了然

**完整代码如下:**

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    typedef struct node{
    int data;
    node *next;
    }Node,*pNode;
    
    typedef struct{
    	pNode front;
    	pNode rear;
    }Queue,*pQueue;
    
    void init(pQueue pq){
    	pq->front=pq->rear=(pNode)malloc(sizeof(Node));
    	//pq->rear->next=NULL;
    }
    int QueueLength(pQueue pq){
    	int count=0;
    	pNode p=pq->front->next;
    	while(p!=NULL){
    	count++;
    	p=p->next;
    	}
    	printf("\n");
    	return count;
    }
    void enqueue(pQueue pq,int x){
    	pNode pNew=(pNode)malloc(sizeof(Node));
    	pNew->data=x;
    	pNew->next=NULL;
    	pq->rear->next=pNew;
    	pq->rear=pNew;
    }
    void dequeue(pQueue pq,int *e){
    	pNode pTemp=(pNode)malloc(sizeof(Node));
    	pTemp=pq->front->next;
    	*e=pTemp->data;
    	pq->front->next=pTemp->next;
    	free(pTemp);
    }
    
    void show_queue(pQueue pq){
    	pNode p=pq->front->next;
    	printf(" 当前元素从头到尾:");
    	while(p!=NULL){
    		printf("%d ",p->data);
    		p=p->next;
    	}
    }
    void GetHead(pQueue pq,int *e){
    	*e=pq->front->next->data;
    }
    void main(){
    	int count;
    	int x;
    	int e;
    	Queue q;
    	init(&q);
    	printf("_____入队10个元素_____");
    	for(int i=0;i<10;i++){
    		enqueue(&q,i);
    		count=QueueLength(&q);
    		printf("%d入队,当前队列元素个数:%d ",i,count);
    		show_queue(&q);
    	}
    	printf("\n_____出队5个元素_____");
    	for(int i=0;i<5;i++){
    		dequeue(&q,&x);
    		count=QueueLength(&q);
    		printf("%d出队,当前队列元素个数:%d ",x,count);
    		show_queue(&q);
    	}
    	GetHead(&q,&e);
    	printf("\n当前队头为:%d\n",e);
    	system("pause");
    }