C语言数据结构之链式队列(链表实现方式)
1、【1】打开Visual Studio 2013软件并创建Win32控制台应用程序。
【2】添加后文件
#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "stdbool.h"
【3】验证刚创建工程的完整性和正确性
#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "stdbool.h"
void main(void)
{
printf("Hello World......\r\n");
while (1);
}
2、【1】定义链式队列的数据类型
//节点
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 *
【2】编写创建链式队列函数
创建链式队列指针和队列头结点
//创建链式队列
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;
}
【2】验证创建的链式队列
void main(void)
{
pLinkQueue Queue;
Queue = CreatLinkQueue();//创建链式队列
printf("\r\n");
while (1);
}
【3】编写判断链式队列是否为空函数
//判断链式队列是否为空
bool IsEmptyLinkQueue(pLinkQueue queue)
{
//队首与队尾指向同一节(首节点)点则队列为空
if (queue->qFront == queue->qRear)
return true;
else
return false;
}
3、【1】编写链式队列数据入队函数
为新入队的结点分配内存、将新入队结点挂到队尾指针上，队尾指针指向新入队结点。
//链式队列数据入队
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);
}
【2】验证链式队列数据入队
void main(void)
{
pLinkQueue Queue;
Queue = CreatLinkQueue();//创建链式队列
printf("\r\n");
EnterLinkQueue(Queue, 10);//链式队列数据入队
EnterLinkQueue(Queue, 20);
EnterLinkQueue(Queue, 30);
while (1);
}
【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");
}
【4】验证遍历链式队列数据
void main(void)
{
pLinkQueue Queue;
Queue = CreatLinkQueue();//创建链式队列
printf("\r\n");
EnterLinkQueue(Queue, 10);//链式队列数据入队
EnterLinkQueue(Queue, 20);
EnterLinkQueue(Queue, 30);
TraverseLinkQueue(Queue);//遍历链式队列数据
printf("\r\n");
while (1);
}
4、【1】编写链式队列数据出队函数
//链式队列数据出队
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);
}
【2】验证链式队列数据出队函数
void main(void)
{
pLinkQueue Queue;
int delVal = 0;
Queue = CreatLinkQueue();//创建链式队列
printf("\r\n");
EnterLinkQueue(Queue, 10);//链式队列数据入队
EnterLinkQueue(Queue, 20);
EnterLinkQueue(Queue, 30);
TraverseLinkQueue(Queue);//遍历链式队列数据
printf("\r\n");
OutLinkQueue(Queue, &delVal);//链式队列数据出队
OutLinkQueue(Queue, &delVal);
TraverseLinkQueue(Queue);//遍历链式队列数据
printf("\r\n");
while (1);
}
【3】编写获取链式队列长度函数
//获取链式队列长度
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;
}
【4】验证获取链式队列长度函数
void main(void)
{
pLinkQueue Queue;
int delVal = 0;
Queue = CreatLinkQueue();//创建链式队列
printf("\r\n");
EnterLinkQueue(Queue, 10);//链式队列数据入队
EnterLinkQueue(Queue, 20);
EnterLinkQueue(Queue, 30);
CountLinkQueue(Queue);//获取链式队列长度
TraverseLinkQueue(Queue);//遍历链式队列数据
printf("\r\n");
OutLinkQueue(Queue, &delVal);//链式队列数据出队
OutLinkQueue(Queue, &delVal);
CountLinkQueue(Queue);//获取链式队列长度
TraverseLinkQueue(Queue);//遍历链式队列数据
printf("\r\n");
while (1);
}
5、【1】链式队列所有API其他情况的验证
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);
EnterLinkQueue(Queue, 70);
CountLinkQueue(Queue);//获取链式队列长度
TraverseLinkQueue(Queue);//遍历链式队列数据
printf("\r\n");
OutLinkQueue(Queue, &delVal);//链式队列数据出队
OutLinkQueue(Queue, &delVal);
CountLinkQueue(Queue);//获取链式队列长度
TraverseLinkQueue(Queue);//遍历链式队列数据
printf("\r\n");
while (1);
}
【2】链式队列所有API函数
//创建链式队列
LinkQueue * CreatLinkQueue(void)
//判断链式队列是否为空
bool IsEmptyLinkQueue(pLinkQueue queue)
//链式队列数据入队
void EnterLinkQueue(pLinkQueue queue, int value)
//链式队列数据出队
void OutLinkQueue(pLinkQueue queue, int * value)
//遍历链式队列数据
void TraverseLinkQueue(pLinkQueue queue)
//获取链式队列长度
int CountLinkQueue(pLinkQueue queue)
