C语言数据结构

2023-07-17 07:17| 来源: 网络整理| 查看: 265

链式队列(链表实现方式) 有关队列相关知识请查看上一章 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 * 三、创建链式队列为链式队列申请内存，即为队首指针和队尾指针申请内存。为链式队列头结点申请内存，头结点不存放有效数据，方便队列的操作。将队首指针和队尾指针指向头结点，即队首指针和队尾指针相等。链式队列头结点指针域为空，即为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.更新队尾指针，将队尾指针指向新插入的结点。

如下图所示：链式队列数据入队

//链式队列数据入队 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); } 五、判断链式队列是否为空

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

如下图所示：链式队列为空

//判断链式队列是否为空 bool IsEmptyLinkQueue(pLinkQueue queue) { //队首与队尾指向同一节(首节点)点则队列为空 if (queue->qFront == queue->qRear) return true; else return false; } 六、遍历链式队列数据

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.释放出队结点数据内存。

如下图所示：链式队列数据出队

//链式队列数据出队 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); } 八、获取链式队列长度

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

//获取链式队列长度 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; } 九、代码验证演示 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); } 十、运行结果链式队列创建成功...... 头结点: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

【本文地址】

公司简介

联系我们