数据结构——队列的链式实现（C语言）

骑猪看日落 2022-08-25 05:25 210阅读 0赞

**队列是一种先进先出的线性表，但队列顺序存储的时候，操作不方便，为了操作简单，队列采用链式存储结构。队列入队时只能在队尾操作，出队时在队首操作，头结点的指针域有头指针(front)和尾指针(rear)，头结点只存放指针域，不存放数据项，但头指针和尾指针指向头指针时，队列为空。**

**以下是C语言源程序：**

**函数声明：**

#ifndef Queue_H
    #define Queue_H
    
    typedef int Item;
    typedef struct node *PNode;
    
    typedef struct node
    {
    	Item data;
    	PNode next;
    }Node;
    
    typedef struct queue *PQueue;
    
    typedef struct queue
    {
    	PNode front;
    	PNode rear;
    	Item size;
    }Queue;
    
    /***创建空队列***/
    PQueue Creat_Queue();
    
    /***判断队列是否为空***/
    int Is_Empty(PQueue);
    
    PQueue CreateQueue(PQueue); //创建队列  
    
    
    /***数据项入队，在队尾入队***/
    PQueue Add_Queue(PQueue,Item);
    
    /***计算队列大小***/
    int Size_Queue(PQueue);
    
    /***数据项出队，在队首出队***/
    Item Delete_Queue(PQueue);
    
    /***清空队列***/
    void Clear_Queue(PQueue);
    
    /***遍历队列***/
    void Traverse_Queue(PQueue);
    #endif

**函数定义：**

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include"Queue.h"
    
    /***创建空队列***/
    PQueue Creat_Queue()
    {
    	PQueue P=(PQueue)malloc(sizeof(Queue));
    	P->rear=P->front=(PNode)malloc(sizeof(Node));
    	if(NULL==P || NULL==P->front)
    	{
    		printf("The queue is failed.\n");
    		exit(1);
    	}
    	//P->front=P->rear;
    	P->front->next=NULL;
    	P->size=0;
    	return P;
    }
    
    /***判断队列是否为空***/
    int Is_Empty(PQueue P)
    {
    	if(P->front==P->rear)
    		return 1;
    	else
    		return 0;
    }
    
    PQueue CreateQueue(PQueue P) //创建队列  
    {  
        P=Creat_Queue();  
    	printf("Enter the data:");  
        int k;  
        while((scanf("%d",&k)) == 1)  
    	{
    		Add_Queue(P,k);
    		printf("Enter the next data:");  
    	}
    	return P;
    }
    
    /***数据项入队,在队尾入队***/
    PQueue Add_Queue(PQueue P,Item data)
    {
    	PNode temp=(PNode)malloc(sizeof(Node));
    	if(NULL==temp)
    	{
    		printf("The temp is failed.\n");
    		exit(1);
    	}
    	temp->data=data;
    	temp->next=NULL;
    	if(Is_Empty(P))
    		P->front->next=temp;
    	else
    		P->rear->next=temp;
    	P->rear=temp;
    	P->size++;
    	printf("Add the data of %d to queue is success: %d\n ",data,data);
    	return P;
    }
    
    /***计算队列大小***/
    int Size_Queue(PQueue P)
    {
    	return P->size;
    }
    
    /***数据项出队，在队首出队***/
    Item Delete_Queue(PQueue P)
    {
    	Item data;
    	if(Is_Empty(P))
    		return NULL;
    	PNode temp=P->front->next;
    	data=temp->data;
    	P->front->next=temp->next;
    	if(0==P->size)
    		P->rear=P->front;
    	P->size--;
    	free(temp);
    	return data;
    }
    
    /***清空队列***/
    void Clear_Queue(PQueue P)
    {  
        PNode temp = P->front->next;  
        while(temp)  
        {  
            PNode tp = temp;  
            temp = temp->next;  
            free(tp);  
        }  
        temp = P->front;  
        P->front = P->rear = NULL;  
        free(temp);  
    }  
    
    /***遍历队列***/
    void Traverse_Queue(PQueue P)
    {  
        if(Is_Empty(P))  
            printf("there is no data in the queue!\n");  
        else  
        {     
            PNode pCurrent = P->front->next;   
            printf("Now datas int the queue are:\n");  
            while(pCurrent)  
            {  
                printf("%d ",pCurrent->data);  
                pCurrent = pCurrent->next;  
            }  
            printf("\n");  
        }  
        return;  
    }

**测试程序：**

#include<stdio.h>
    #include<stdlib.h>
    #include "Queue.h"
    #define num 5
    
    int main()
    {
    	
    	/***创建空队列***/
    	PQueue PQ;
    	int size=0;
    	int data;
    	PQ=Creat_Queue();
    	printf("The queue is created.\n");
    
    	/***判断队列是否为空***/
    	if(Is_Empty(PQ))
    		printf("The queue is empty.\n");
    
    	PQ=CreateQueue(PQ); //创建队列
    	/***遍历队列***/
    	Traverse_Queue(PQ);
    
    	/***数据项入队，在队尾入队***/
    	PQ=Add_Queue(PQ,num);
    	/***遍历队列***/
    	Traverse_Queue(PQ);
    
    	/***计算队列大小***/
    	size=Size_Queue(PQ);
    	printf("The size of queue are: %d\n",size);
    
    	/***数据项出队，在队首出队***/
    	data=Delete_Queue(PQ);
    	printf("The deleted data is: %d\n",data);
    	/***遍历队列***/
    	Traverse_Queue(PQ);
    
    	/***清空队列***/
    	Clear_Queue(PQ);
    	if(Is_Empty(PQ))
    		printf("The queue is empty.\n");
    	/***遍历队列***/
    	Traverse_Queue(PQ);
    
    	return 0;
    }