考研数据结构代码实现之链式队列（基于王道书）

代码实现基于王道书上给的代码代码如有缺陷之处欢迎指正~说明· .h文件用于声明· .cpp文件用于定义· main.cpp 用于测试注代码在VS2022调试测试链式队列带头结点Linkqueue.h#pragma once #includestdio.h #includestdlib.h #define ElemType int /* 带头结点的链式队列 */ typedef struct LinkNode { ElemType data; struct LinkNode* next; }LinkNode; // 队列结点 typedef struct { LinkNode* front, * rear; }LinkQueue; // 链队 void InitQueue(LinkQueue q); // 初始化 bool QueueEmpty(LinkQueue q); // 队列判空 void EnQueue(LinkQueue q,ElemType e); // 入队 bool DeQueue(LinkQueue q, ElemType e); // 出队并带回Linkqueue.cpp#include Linkqueue.h void InitQueue(LinkQueue Q) { Q.front Q.rear (LinkNode*)malloc(sizeof(LinkNode)); Q.front-next NULL; } bool QueueEmpty(LinkQueue Q) { if (Q.front Q.rear) return true; else return false; } void EnQueue(LinkQueue Q, ElemType e) { LinkNode* s (LinkNode*)malloc(sizeof(LinkNode)); s-data e; s-next NULL; Q.rear-next s; Q.rear s; } bool DeQueue(LinkQueue Q,ElemType e) { if (QueueEmpty(Q)) return false; LinkNode* p Q.front-next; // 待删除结点 e p-data; Q.front-next p-next; if (Q.rear p) Q.rear Q.front; free(p); return true; }main.cpp#include Linkqueue.h #include stdio.h // 用于输出测试结果 // 打印队列元素用于观察 void PrintQueue(LinkQueue Q) { if (QueueEmpty(Q)) { printf(队列为空\n); return; } LinkNode* p Q.front-next; printf(队列元素: ); while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 测试函数 void TestLinkQueue() { printf( 链式队列测试开始 \n\n); // 1. 测试初始化 printf(【测试1】初始化队列\n); LinkQueue Q; InitQueue(Q); printf(初始化完成\n); PrintQueue(Q); printf(队列是否为空: %s\n\n, QueueEmpty(Q) ? 是 : 否); // 2. 测试入队 printf(【测试2】入队操作\n); printf(依次入队: 10, 20, 30, 40, 50\n); EnQueue(Q, 10); EnQueue(Q, 20); EnQueue(Q, 30); EnQueue(Q, 40); EnQueue(Q, 50); PrintQueue(Q); printf(队列是否为空: %s\n, QueueEmpty(Q) ? 是 : 否); printf(队首元素: %d\n, Q.front-next-data); printf(队尾元素: %d\n\n, Q.rear-data); // 3. 测试出队 printf(【测试3】出队操作\n); ElemType e; printf(执行出队: ); if (DeQueue(Q, e)) { printf(出队元素 %d\n, e); } PrintQueue(Q); printf(执行出队: ); if (DeQueue(Q, e)) { printf(出队元素 %d\n, e); } PrintQueue(Q); printf(执行出队: ); if (DeQueue(Q, e)) { printf(出队元素 %d\n, e); } PrintQueue(Q); printf(\n); // 4. 测试继续入队验证rear指针正确性 printf(【测试4】出队后再入队\n); printf(入队: 60, 70\n); EnQueue(Q, 60); EnQueue(Q, 70); PrintQueue(Q); printf(队首元素: %d\n, Q.front-next-data); printf(队尾元素: %d\n\n, Q.rear-data); // 5. 测试全部出队验证空队列状态和rear指针 printf(【测试5】全部出队测试边界条件\n); printf(依次出队所有元素:\n); int count 0; while (!QueueEmpty(Q)) { DeQueue(Q, e); printf(第%d次出队: %d, , count, e); printf(队列是否为空: %s\n, QueueEmpty(Q) ? 是 : 否); } PrintQueue(Q); printf(\n); // 6. 测试空队列出队应该失败 printf(【测试6】空队列出队预期失败\n); if (DeQueue(Q, e)) { printf(出队成功: %d\n, e); } else { printf(出队失败队列为空\n); } printf(\n); // 7. 测试大量数据 printf(【测试7】大量数据入队出队\n); printf(入队 1-10:\n); for (int i 1; i 10; i) { EnQueue(Q, i); } PrintQueue(Q); printf(出队前5个元素:\n); for (int i 0; i 5; i) { if (DeQueue(Q, e)) { printf(出队: %d , e); } } printf(\n); PrintQueue(Q); printf(继续入队 11-15:\n); for (int i 11; i 15; i) { EnQueue(Q, i); } PrintQueue(Q); printf(\n); // 8. 测试rear指针是否正确关键测试 printf(【测试8】验证rear指针正确性\n); printf(当前队列: ); PrintQueue(Q); printf(front-next-data %d\n, Q.front-next-data); printf(rear-data %d\n, Q.rear-data); printf(如果front-next-data和rear-data都正确说明rear指针维护正确\n\n); // 9. 清空队列 printf(【测试9】清空队列\n); while (!QueueEmpty(Q)) { DeQueue(Q, e); } printf(清空完成\n); PrintQueue(Q); printf(队列是否为空: %s\n, QueueEmpty(Q) ? 是 : 否); printf(front地址: %p, rear地址: %p\n, Q.front, Q.rear); printf(front rear: %s\n\n, (Q.front Q.rear) ? 是 : 否); printf( 测试结束 \n); } // 主函数 int main() { TestLinkQueue(); return 0; }