C语言数据结构———链式队列(链表实现方式)_链表队列c语言

链式队列(链表实现方式)

有关队列相关知识请查看上一章

C语言数据结构———循环队列(静态数组实现方式)

一、链式队列

链式队列 ： 用链表形式实现的队列。链表结点为队列数据存储区，链表结点包括两部分数据存储区和指针存储区。
数据存储区 ：存放真实有效数据的区域。
指针存储区 ：存放下一个链表结点的地址。

注意：
1. 链式队列不存在队列已满的情况。在内存足够大的情况下，每次动态申请链表结点内存都会成功，即不会出现队列已满的情况，除非数据量超大内存不够。

2. 链式队列只存在队列为空的情况，在刚创建队列成功时队列为空，或者队列数据已全部出队，则此时队列为空。

3.在链式队列中头结点的数据域不存放有效数据，指针域存放第一个有效数据域的结点地址，头结点的作用是方便对链式队列的操作。

二、链式队列数据类型定义

//队列节点 
typedef struct Node
{
	int dat;//结点值
	struct Node *pNext;//下一个结点
}Node, *pNode;
//Node   等效于 struct Node
//*pNode 等效于 struct Node *


//链式队列
typedef struct LinkQueue
{
	struct Node * qFront;//队首指针
	struct Node * qRear;//队尾指针
}LinkQueue, *pLinkQueue;
//LinkQueue  等效于 struct LinkQueue
//pLinkQueue 等效于 struct LinkQueue *
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、创建链式队列

1. 为链式队列申请内存，即为队首指针和队尾指针申请内存。
2. 为链式队列头结点申请内存，头结点不存放有效数据，方便队列的操作。
3. 将队首指针和队尾指针指向头结点，即队首指针和队尾指针相等。
4. 链式队列头结点指针域为空，即为NULL；头结点数据域可不管，亦可为零，作为链式队列有效的节点数，亦可作为创建队列成功标识等等，由开发者根据实际情况而定。

如下图所示：

//创建链式队列
LinkQueue * CreatLinkQueue(void)
{
	pLinkQueue pHeadQueue = NULL;//链式队列指针
	pNode pHeadNode = NULL;//头结点指针


	//为链式队列申请内存
	pHeadQueue = (LinkQueue *)malloc(sizeof(LinkQueue));
	if (pHeadQueue == NULL)
	{
		printf("链式队列内存申请失败，程序终止......\r\n");
		while (1);
	}

	//为链式队列头结点申请内存
	pHeadNode = (Node *)malloc(sizeof(Node));
	if (pHeadNode == NULL)
	{
		printf("链式队列头结点内存申请失败，程序终止......\r\n");
		while (1);
	}
	
	pHeadQueue->qFront = pHeadNode;//队首指向头结点
	pHeadQueue->qRear  = pHeadNode;//队尾指向头结点
	pHeadNode->pNext   = NULL;//头结点无下个结点
	pHeadNode->dat     = 0;//头结点数据为零

	printf("链式队列创建成功......\r\n");
	printf("头结点:0x%08X    头结点指针:0x%08X    队首指针:0x%08X    队尾指针:0x%08X\r\n", pHeadNode, pHeadNode->pNext, pHeadQueue->qFront, pHeadQueue->qRear);

	return pHeadQueue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

四、链式队列数据入队

1.为链式队列入队数据结点申请内存。
2.将新结点设置为最后个结点，新结点的指针域为空，数据域为入队数据。
3.更新队尾指针，将队尾指针指向新插入的结点。

如下图所示：

//链式队列数据入队
void EnterLinkQueue(pLinkQueue queue, int value)
{
	pNode newNode = NULL;//链式队列入队结点指针


	//为链式队列入队结点申请内存
	newNode = (Node *)malloc(sizeof(Node));
	if (newNode == NULL)
	{
		printf("链式队列入队结点内存申请失败......\r\n");
		return;
	}

	queue->qRear->pNext = newNode;//入队新结点为最后个结点
	queue->qRear   = newNode;//队尾指向入队新结点
	newNode->pNext = NULL;//入队新结点无下个结点
	newNode->dat   = value;//入队值

	printf("入队成功！入队值:%d  ---->  ", value);
	printf("队首结点指针:0x%08X    队尾指针:0x%08X\r\n", queue->qFront, queue->qRear);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

五、判断链式队列是否为空

当队首指针和队尾指针相等，即都指向头结点时，则表示链式队列为空，此时头结点指针域为空。

如下图所示：

//判断链式队列是否为空
bool IsEmptyLinkQueue(pLinkQueue queue)
{
	//队首与队尾指向同一节(首节点)点则队列为空
	if (queue->qFront == queue->qRear)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8
9

六、遍历链式队列数据

1.只有在链式队列非空时才遍历队列。
2.从队首的下一个有效结点开始遍历，直到队尾结束。
3.遍历一个结点后，指向下一个结点继续遍历。

//遍历链式队列数据
void TraverseLinkQueue(pLinkQueue queue)
{
	pNode queNode = NULL;//结点指针

	if (IsEmptyLinkQueue(queue))
	{
		printf("链式队列为空，遍历失败......\r\n");
		return;
	}

	printf("链式队列数据: ");
	queNode = queue->qFront->pNext;//第一个有效结点
	while (queNode != NULL)//最后一个结点结束
	{
		printf("%d ", queNode->dat);//结点数据
		queNode = queNode->pNext;//下一个结点
	}
	printf("\r\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

七、链式队列数据出队

1.只有在链式队列非空时出队数据才有效。
2.若只有一个有效结点时，需将队尾指针指向头结点，头结点指针域为空。
3.头结点指针指向下下个有效结点。
4.结点数据出队。
5.释放出队结点数据内存。

如下图所示：

//链式队列数据出队
void OutLinkQueue(pLinkQueue queue, int * value)
{
	pNode queNode = 0;//队列结点指针

	if (IsEmptyLinkQueue(queue))
	{
		printf("链式队列为空，出队失败......\r\n");
		*value = 0;
		return;
	}

	if (queue->qFront->pNext == queue->qRear)//只有一个有效结点
		queue->qRear = queue->qFront;//队尾指针等于队首指针

	queNode = queue->qFront->pNext;//结点指针指向队首有效结点
	queue->qFront->pNext = queNode->pNext;//队首结点指针指向下个结点
	*value = queNode->dat;//出队结点值
	free(queNode);//释放内存

	printf("出队成功！出队值:%d  ---->  ", *value);
	printf("队首结点指针:0x%08X    队尾指针:0x%08X\r\n", queue->qFront->pNext, queue->qRear);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

八、获取链式队列长度

获取链式队列长度与遍历链式队列原理一致，从队首结点的第一个有效结点开始遍历，直到队尾结束。

//获取链式队列长度
int CountLinkQueue(pLinkQueue queue)
{
	pNode queNode = NULL;//结点指针
	int len = 0;

	if (IsEmptyLinkQueue(queue))
	{
		printf("链式队列为空......\r\n");
		return len;
	}

	queNode = queue->qFront->pNext;//第一个有效结点
	while (queNode != NULL)//最后一个结点结束
	{
		len++;
		queNode = queNode->pNext;//下一个结点
	}
	
	printf("链式队列长度: %d\r\n", len);
	return len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

九、 代码验证演示

void main(void)
{
	pLinkQueue Queue;
	int delVal = 0;

	Queue =  CreatLinkQueue();//创建链式队列
	printf("\r\n");
	
	EnterLinkQueue(Queue, 10);//链式队列数据入队
	EnterLinkQueue(Queue, 20);
	EnterLinkQueue(Queue, 30);
	EnterLinkQueue(Queue, 40);
	EnterLinkQueue(Queue, 50);
	EnterLinkQueue(Queue, 60);
	CountLinkQueue(Queue);//获取链式队列长度
	TraverseLinkQueue(Queue);//遍历链式队列数据
	printf("\r\n");

	OutLinkQueue(Queue, &delVal);//链式队列数据出队
	OutLinkQueue(Queue, &delVal);
	OutLinkQueue(Queue, &delVal);
	OutLinkQueue(Queue, &delVal);
	OutLinkQueue(Queue, &delVal);
	CountLinkQueue(Queue);//获取链式队列长度
	TraverseLinkQueue(Queue);//遍历链式队列数据
	printf("\r\n");
	
	while (1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

十、 运行结果

链式队列创建成功......
头结点:0x005D5860    头结点指针:0x00000000    队首指针:0x005D5860    队尾指针:0x005D5860

入队成功！入队值:10  ---->  队首结点指针:0x005D5860    队尾指针:0x005DB2A8
入队成功！入队值:20  ---->  队首结点指针:0x005D5860    队尾指针:0x005DB2F0
入队成功！入队值:30  ---->  队首结点指针:0x005D5860    队尾指针:0x005DB338
入队成功！入队值:40  ---->  队首结点指针:0x005D5860    队尾指针:0x005DB380
入队成功！入队值:50  ---->  队首结点指针:0x005D5860    队尾指针:0x005DB3C8
入队成功！入队值:60  ---->  队首结点指针:0x005D5860    队尾指针:0x005DB410
链式队列长度: 6
链式队列数据: 10 20 30 40 50 60

出队成功！出队值:10  ---->  队首结点指针:0x005DB2F0    队尾指针:0x005DB410
出队成功！出队值:20  ---->  队首结点指针:0x005DB338    队尾指针:0x005DB410
出队成功！出队值:30  ---->  队首结点指针:0x005DB380    队尾指针:0x005DB410
出队成功！出队值:40  ---->  队首结点指针:0x005DB3C8    队尾指针:0x005DB410
出队成功！出队值:50  ---->  队首结点指针:0x005DB410    队尾指针:0x005DB410
链式队列长度: 1
链式队列数据: 60
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19