C语言实现数据结构——链队列

C语言实现数据结构——链队列 定义

前面学习了栈这种数据结构，我们知道他的特点是数据先进后出。与栈相反，队列的特点时数据先进先出。即first in firsr out,简称FIFO。
队列只允许在表的一端进行数据的插入，在另一端进行数据的删除。这和生活中的排队是一致的，最早进入队列的最先离开。在链表中，允许插入数据的一端叫队尾（rear），允许删除数据的一端叫队头（front）。假设将数据a,b,c,d,e,f输入到一个队列中，那么输入的顺序是a,b,c,d,e,f。输出的顺序也是a,b,c,d,e,f。

基本 *** 作

1. 初始化一个队列

Status InitQueue(linkQueue *q)

2. 销毁一个队列

Status DestoryQueue(linkQueue *q)

3. 清空一个队列

Status ClearQueue(linkQueue *q)

4. 判断队列是否为空

Status QueueEmpty(linkQueue *q)

5. 返回队列中可用元素的数量，即队列的长度

int QueueLength(linkQueue *q)

6. 返回队头

Status GetHead(linkQueue Q, QElemType* e)

7. 从队尾添加元素

tatus EnQueue(linkQueue* Q, QElemType e)

8. 将队头元素删除

Status DeQueue(linkQueue* Q, QElemType* e)

9. 队列的遍历

Status QueueTraverse(linkQueue Q, void (Visit)(QElemType))

基本 *** 作方法的代码实现

1. 初始化一个队列

Status InitQueue(linkQueue* Q) {
    if(Q == NULL) {
        return ERROR;
    }
    
    (*Q).front = (*Q).rear = (QueuePtr) malloc(sizeof(QNode));
    if(!(*Q).front) {
        exit(OVERFLOW);
    }
    
    (*Q).front->next = NULL;
    
    return OK;
}

2. 销毁一个队列

Status DestroyQueue(linkQueue* Q) {
    if(Q == NULL) {
        return ERROR;
    }
    
    while((*Q).front) {
        (*Q).rear = (*Q).front->next;
        free((*Q).front);
        (*Q).front = (*Q).rear;
    }
    
    return OK;
}

3. 清空一个队列

Status ClearQueue(linkQueue* Q) {
    if(Q == NULL) {
        return ERROR;
    }
    
    (*Q).rear = (*Q).front->next;
    
    while((*Q).rear) {
        (*Q).front->next = (*Q).rear->next;
        free((*Q).rear);
        (*Q).rear = (*Q).front->next;
    }
    
    (*Q).rear = (*Q).front;
    
    return OK;
}

4. 判断队列是否为空

Status QueueEmpty(linkQueue Q) {
    if(Q.front == Q.rear) {
        return TRUE;
    } else {
        return FALSE;
    }
}

5. 返回队列中可用元素的数量，即队列的长度

int QueueLength(linkQueue Q) {
    int count = 0;
    QueuePtr p = Q.front;
    
    while(p != Q.rear) {
        count++;
        p = p->next;
    }
    
    return count;
}

6. 返回队头

Status GetHead(linkQueue Q, QElemType* e) {
    QueuePtr p;
    
    if(Q.front == NULL || Q.front == Q.rear) {
        return ERROR;
    }
    
    p = Q.front->next;
    *e = p->data;
    
    return OK;
}

7. 从队尾添加元素

Status EnQueue(linkQueue* Q, QElemType e) {
    QueuePtr p;
    
    if(Q == NULL || (*Q).front == NULL) {
        return ERROR;
    }
    
    p = (QueuePtr) malloc(sizeof(QNode));
    if(!p) {
        exit(OVERFLOW);
    }
    
    p->data = e;
    p->next = NULL;
    
    (*Q).rear->next = p;
    (*Q).rear = p;
    
    return OK;
}

图片演示

8. 将队头元素删除

Status DeQueue(linkQueue* Q, QElemType* e) {
    QueuePtr p;
    
    if(Q == NULL || (*Q).front == NULL || (*Q).front == (*Q).rear) {
        return ERROR;
    }
    
    p = (*Q).front->next;
    *e = p->data;
    
    (*Q).front->next = p->next;
    if((*Q).rear == p) {
        (*Q).rear = (*Q).front;
    }
    
    free(p);
    
    return OK;
}

图片演示

9. 队列的遍历

Status QueueTraverse(linkQueue Q, void (Visit)(QElemType)) {
    QueuePtr p;
    
    if(Q.front == NULL) {
        return ERROR;
    }
    
    p = Q.front->next;
    
    while(p != NULL) {
        Visit(p->data);
        p = p->next;
    }
    
    printf("n");
    
    return OK;
}

该源码实现的是链队列，所以设置了一个并不包含数据的头节点，实际上不设置此节点也能进行队列的 *** 作，只不过添加头节点使得删除遍历灯过程更加的方便易懂

所有代码文件

1. 状态码宏定义头文件

Status.h

#ifndef STATUS_H
#define STATUS_H

#include 

 
#define TRUE        1   // 真/是
#define FALSE       0   // 假/否
#define OK          1   // 通过/成功
#define ERROR       0   // 错误/失败

//系统中已有此状态码定义，要防止冲突
#ifndef OVERFLOW
#define OVERFLOW    -2  //堆栈上溢
#endif

//系统中已有此状态码定义，要防止冲突
#ifndef NULL
#define NULL ((void*)0)
#endif


typedef int Status;


typedef int Boolean;

#endif

2. 函数定义头文件

linkQueue.h

#include 
#include      
#include "Status.h"    


typedef int QElemType;

// 队列元素结构
typedef struct QNode {
    QElemType data;
    struct QNode* next;
} QNode, * QueuePtr;

// 队列结构
typedef struct {
    QueuePtr front;     // 队头指针
    QueuePtr rear;      // 队尾指针
} linkQueue;            // 队列的链式存储表示



Status InitQueue(linkQueue* Q);


Status DestroyQueue(linkQueue* Q);


Status ClearQueue(linkQueue* Q);


Status QueueEmpty(linkQueue Q);


int QueueLength(linkQueue Q);


Status GetHead(linkQueue Q, QElemType* e);


Status EnQueue(linkQueue* Q, QElemType e);


Status DeQueue(linkQueue* Q, QElemType* e);


Status QueueTraverse(linkQueue Q, void(Visit)(QElemType));

#endif

3. 函数实现头文件

linkQueue.c

#include"linkQuquq.h"
#include"Status.h"

Status InitQueue(linkQueue* q)
{ 
	if (q == NULL)
	{
		return ERROR;
	}
	(*q).front = (*q).rear = (QueuePtr)malloc(sizeof(QNode));
	if (!(*q).front)
	{
		exit(OVERFLOW);
	}
	(*q).front->next = NULL;
	return OK;
}

//队列的销毁的函数并不是经常的用到
Status DestoryQueue(linkQueue* q)
{
	if (q == NULL)
	{
		return ERROR;
	}
	while ((*q).front)
	{
		(*q).rear = (*q).front->next;
		free((*q).front);
		(*q).front = (*q).rear;
	}
	return OK;
}


//内容置空，但是要将中间非头结点的空间释放
Status ClearQueue(linkQueue* q)
{
	if (q = NULL)
	{
		return ERROR;
	}
	(*q).rear = (*q).front->next;
	while ((*q).rear) {
		(*q).front->next = (*q).rear->next;
		free((*q).rear);
		(*q).rear = (*q).front->next;
	}

	(*q).rear = (*q).front;

	return OK;
}

//判断队列是否为空
Status QueueEmpty(linkQueue* q)
{
	if (q->front == q->rear)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

//返回队列中有效元素的个数
int	QueueLength(linkQueue* q)
{
	int count = 0;
	QueuePtr p = q->front;

	while (p != q->rear)
	{
		count++;
		p = p->next;
	}
	return count;
}

//取出队头元素
Status GetHead(linkQueue* q,int* e)
{
	QueuePtr p;

	if (q->front == NULL || q->front == q->rear)
	{
		return ERROR;
	}
	p = q->front->next;
	*e = p->data;
	return OK;
}

Status Enter(linkQueue* q, int e)
{
	QueuePtr p;

	if (q == NULL || (*q).front == NULL)
	{
		return ERROR;
	}
	p = (QueuePtr)malloc(sizeof(QNode));
	if (!p)
	{
		exit(OVERFLOW);
	}
	p->data = e;
	p->next = NULL;

	(*q).rear->next = p;
	(*q).rear = p;

	return OK;

}

//出队列，移除队头的元素
Status Out(linkQueue* q, int e)
{
	QueuePtr p;

	if (q == NULL || q->front==NULL || q->front == q->rear)
	{
		return ERROR;
	}
	p = (*q).front->next;
	e = p->data;

	(*q).front->next = p->next;
	if ((*q).rear == p)
	{
		(*q).front = (*q).rear;
	}
	free(p);
	return OK;
}
void QueueTraverse(linkQueue* q)
{
	QueuePtr p;

	if (q->front == NULL)
	{
		return ERROR;
	}
	p = q->front->next;

	while (p != NULL)
	{
		printf("%d  ", p->data);
		p = p->next;
	}
	printf("n");
}

4. 测试主函数

linkQueue-main.c

#include 
#include "linkQueue.h"        //

// 测试函数，打印整型
void PrintElem(QElemType e);

int main(int argc, char** argv) {
    linkQueue Q;
    int i;
    QElemType e;
    
    printf(" 函数 InitQueue n");
    {
        printf(" 初始化链队 Q ...n");
        InitQueue(&Q);
    }

    
    printf(" 函数 QueueEmpty n");
    {
        QueueEmpty(Q) ? printf(" Q 为空！！n") : printf(" Q 不为空！n");
    }

    
    printf(" 函数 EnQueue n");
    {
        for(i = 1; i <= 6; i++) {
            EnQueue(&Q, 2 * i);
            printf(" 元素 "%2d" 入队...n", 2 * i);
        }
    }

    
    printf(" 函数 QueueTraverse n");
    {
        printf(" Q 中的元素为：Q = ");
        QueueTraverse(Q, PrintElem);
    }

    
    printf(" 函数 QueueLength n");
    {
        i = QueueLength(Q);
        printf(" Q 的长度为 %d n", i);
    }

    printf(" 函数 DeQueue n");
    {
        DeQueue(&Q, &e);
        printf(" 队头元素 "%d" 出队...n", e);
        printf(" Q 中的元素为：Q = ");
        QueueTraverse(Q, PrintElem);
    }

    
    printf(" 函数 GetHead n");
    {
        GetHead(Q, &e);
        printf(" 队头元素的值为 "%d" n", e);
    }

    
    printf(" 函数 ClearQueue n");
    {
        printf(" 清空 Q 前：");
        QueueEmpty(Q) ? printf(" Q 为空！！n") : printf(" Q 不为空！n");
        
        ClearQueue(&Q);
        
        printf(" 清空 Q 后：");
        QueueEmpty(Q) ? printf(" Q 为空！！n") : printf(" Q 不为空！n");
    }
    
    
    printf(" 函数 DestroyQueue n");
    {
        printf(" 销毁 Q 前：");
        Q.front != NULL && Q.rear != NULL ? printf(" Q 存在！n") : printf(" Q 不存在！！n");
        
        DestroyQueue(&Q);
        
        printf(" 销毁 Q 后：");
        Q.front != NULL && Q.rear != NULL ? printf(" Q 存在！n") : printf(" Q 不存在！！n");
    }

    
    return 0;
}

// 测试函数，打印整型
void PrintElem(QElemType e) {
    printf("%d ", e);
}