数据结构（链式队列）（C语言）

女爷i 2022-05-17 11:46 256阅读 0赞

### 利用C语言实现链式队列的基本功能： ###

*  头文件：

#ifndef _LINKQUEUE_H_
    #define _LINKQUEUE_H_
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define SUCCESS   100
    #define FAILURE   101
    #define TRUE      102
    #define FALSE     103
    
    typedef int DataType;
    
    typedef struct node
    {
    	DataType data;
    	struct node *next;
    }Node;
    
    typedef struct queue
    {
    	Node *front;
    	Node *rear;
    }Queue;
    
    int QueueInit(Queue **queue);
    int QueueInsert(Queue *queue, DataType e);
    int QueueDelete(Queue *queue);
    int GetTop(Queue *queue);
    int QueueEmpty(Queue *queue);
    int QueueClear(Queue *queue);
    int QueueDestory(Queue **queue);
    
    #endif

*  功能函数：

#include "LinkQueue.h"
    
    int QueueInit(Queue **queue)
    {
    	if(NULL == queue)
    	{
    		return FAILURE;
    	}
    	
    	*queue = (Queue *)malloc(sizeof(Queue));
    	if(NULL == *queue)
    	{
    		return FAILURE;
    	}
    	
    	Node *p = (Node *)malloc(sizeof(Node));
    	if(NULL == p)
    	{
    		return FAILURE;
    	}
    	p->next = NULL;
    	
    	(*queue)->front = p;
    	(*queue)->rear = p;
    	
    	return SUCCESS;
    }
    
    int QueueInsert(Queue *queue, DataType e)
    {
    	if(NULL == queue)
    	{
    		return FAILURE;
    	}
    	
    	Node *p = (Node *)malloc(sizeof(Node));
    	if(NULL == p)
    	{
    		return FAILURE;
    	}
    	
    	p->data = e;
    	p->next = NULL;
    	
    	queue->rear->next = p;
    	queue->rear = p;
    	
    	return SUCCESS;
    }
    
    int QueueDelete(Queue *queue)
    {
    	if(NULL == queue || queue->front->next == NULL)
    	{
    		return FAILURE;
    	}
    	
    	DataType e = queue->front->next->data;
    	Node *p = queue->front->next;
    	queue->front->next = p->next;
    	free(p);
    	
    	if(queue->front->next == NULL)
    	{
    		queue->rear = queue->front;
    	}
    	
    	return e;
    }
    
    int GetTop(Queue *queue)
    {
    	if(NULL == queue || queue->front->next == NULL)
    	{
    		return FAILURE;
    	}
    	
    	return queue->front->next->data;
    }
    
    int QueueEmpty(Queue *queue)
    {
    	if(NULL == queue)
    	{
    		return FAILURE;
    	}
    	
    	return (queue->rear == queue->front) ? TRUE : FALSE;
    }
    
    int QueueClear(Queue *queue)
    {
    	if(NULL == queue)
    	{
    		return FAILURE;
    	}
    	
    	Node *p = queue->front->next;
    	while(p)
    	{
    		queue->front->next = p->next;
    		free(p);
    		p = queue->front->next;
    	}
    	
    	queue->rear = queue->front;
    	
    	return SUCCESS;
    }
    
    int QueueDestory(Queue **queue)
    {
    	if(NULL == queue || *queue == NULL)
    	{
    		return FAILURE;
    	}
    	
    	Node *p = (*queue)->front->next;
    	while(p)
    	{
    		(*queue)->front->next = p->next;
    		free(p);
    		p = (*queue)->front->next;
    	}
    	
    	(*queue)->rear = (*queue)->front;
    	free((*queue)->rear);
    	free(*queue);
    	
    	return SUCCESS;
    }

*  测试主函数：

#include "LinkQueue.h"
    
    int main()
    {
    	Queue *queue = NULL;
    	int ret, i;
    	
    	ret = QueueInit(&queue);
    	if(SUCCESS == ret)
    	{
    		printf("Init Success.\n");
    	}
    	else
    	{
    		printf("Init Failure.\n");
    	}
    	
    	for(i = 0; i < 9; i++)
    	{
    		ret = QueueInsert(queue, i);
    		if(SUCCESS == ret)
    		{
    			printf("QueueInsert %d Success.\n", i);
    		}
    		else
    		{
    			printf("QueueInsert %d Failure.\n", i);
    		}
    	}
    	
    	for(i = 0; i < 4; i++)
    	{
    		ret = QueueDelete(queue);
    		if(FAILURE == ret)
    		{
    			printf("QueueDelete Failure.\n");
    		}
    		else
    		{
    			printf("QueueDelete %d Success.\n", ret);
    		}
    	}
    	
    	ret = GetTop(queue);
    	if(FAILURE == ret)
    	{
    		printf("Get Top Failure.\n");
    	}
    	else
    	{
    		printf("Queue Top is %d.\n", ret);
    	}
    	
    	ret = QueueEmpty(queue);
    	if(TRUE == ret)
    	{
    		printf("Queue is Empty.\n");
    	}
    	else if(FALSE == ret)
    	{
    		printf("Queue is not Empty.\n");
    	}
    	else if(FAILURE == ret)
    	{
    		printf("ERROR.\n");
    	}
    	
    	ret = QueueClear(queue);
    	if(SUCCESS == ret)
    	{
    		printf("QueueClear Success.\n");
    	}
    	else
    	{
    		printf("QueueClear Failure.\n");
    	}
    	
    	ret = QueueDestory(&queue);
    	if(SUCCESS == ret)
    	{
    		printf("QueueDestory Success.\n");
    	}
    	else
    	{
    		printf("QueueDestory Failure.\n");
    	}
    	
    	
    	return 0;
    }