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){ pNod髫潋啜缅e 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)
