数据结构_链队(C语言)

(一)链队图文解析

链队是指采用链式存储结构实现的队列，用单链表来表示，一个链队需要俩个分别指示队头和队尾的头指针和尾指针，同时还需要一个头结点，使头指针指向头结点。
<mark>注意队头不是头结点！！</mark>。

(二) 链队代码解析

(1)链队的基本操作

1.1 链队的存储结构

typedef struct QNode
{
	int data;//数据域，存放数据元素
	struct QNode *next;//指针域
}QNode,*QueuePoint;
typedef struct
{
	QueuePoint front;//头指针
	QueuePoint rear;//尾指针
}LinkQueue;

1.2 链队的初始化

void InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QNode*)malloc(sizeof(QNode));//头指针和尾指针新创建的指向头结点
	Q.front->next=NULL;//头结点的指针域为空
}

1.3 链队的入队

void EnQueue(LinkQueue &Q,int e)
{
	QNode *p;	//定义一个结点
	p=(QNode*)malloc(sizeof(QNode));//为结点分配空间
	p->data=e;//新结点数据域存放数据e
	p->next=NULL;//因为在队尾入队，新结点p不需要指向哪里，指针域为空
	Q.rear->next=p;//将尾指针指向新结点p
	Q.rear=p;//使新结点p为队尾结点
}

1.4 链队的出队

void DeQueue(LinkQueue &Q,int &e)
{
	QNode *p;//定义一个新结点
	if(Q.front==Q.rear)
		printf("队空!\n");
	else
	{
		p=Q.front->next;//将头结点指向的队头结点交给p
		e=p->data;//将队头结点的数据域交给e
		Q.front->next=p->next;//头结点指向队头结点的下一个结点
		if(Q.rear==p)
			Q.rear=Q.front;//最后一个元素被删除时，队尾指针指向头结点
		free(p);//释放结点空间 
	}
}

1.5 链队的长度

int QueueLength(LinkQueue Q)
{
	int i=0;
	while(Q.front->next!=NULL)
	{
		Q.front=Q.front->next;//遍历链队
		i++;//计数队长
	}
	return i;
}

1.6 链队的队头元素

int GetHead(LinkQueue Q)
{
	if(Q.front!=Q.rear)
		return Q.front->next->data;
	else
		return false;
}

1.7 链队的队尾元素

int GetTail(LinkQueue Q)
{
	if(Q.front!=Q.rear)
		return Q.rear->data;
	else
		return false;
}

(2) 链队源代码及测试

2.1 源代码:

#include<stdio.h>
#include<malloc.h>
typedef struct QNode
{
	int data;
	struct QNode *next;
}QNode,*QueuePoint;
typedef struct
{
	QueuePoint front;
	QueuePoint rear;
}LinkQueue;

void InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QNode*)malloc(sizeof(QNode));
	Q.front->next=NULL;
}

void EnQueue(LinkQueue &Q,int e)
{
	QNode *p;
	p=(QNode*)malloc(sizeof(QNode));
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
void DeQueue(LinkQueue &Q,int &e)
{
	QNode *p;
	if(Q.front==Q.rear)
		printf("队空!\n");
	else
	{
		p=Q.front->next;
		e=p->data;
		Q.front->next=p->next;
		if(Q.rear==p)
			Q.rear=Q.front;
		free(p);
	}
}
int QueueLength(LinkQueue Q)
{
	int i=0;
	while(Q.front->next!=NULL)
	{
		Q.front=Q.front->next;
		i++;
	}
	return i;
}
int GetHead(LinkQueue Q)
{
	if(Q.front!=Q.rear)
		return Q.front->next->data;
	else
		return false;
}
int GetTail(LinkQueue Q)
{
	if(Q.front!=Q.rear)
		return Q.rear->data;
	else
		return false;
}
int main()
{
	int e;
	LinkQueue Q;
	InitQueue(Q);
	printf("依次入队10,20,30\n");
	EnQueue(Q,10);
	EnQueue(Q,20);
	EnQueue(Q,30);
	printf("队列长度:%d\n",QueueLength(Q));
	printf("队头元素:%d\n",GetHead(Q));
	printf("队尾元素:%d\n",GetTail(Q));
	printf("\n");
	
	printf("出队一次\n");
	DeQueue(Q,e);
	printf("队列长度:%d\n",QueueLength(Q));
	printf("队头元素:%d\n",GetHead(Q));
	printf("队尾元素:%d\n",GetTail(Q));
	return 0;
}