如何用CC++实现链表队列来处理长尾词的？

本文共计1011个文字，预计阅读时间需要5分钟。

链表数组是一种基于链表实现的数组，相较于顺序数组，链表数组不需要预先申请固定大小的内存空间，可以根据需要动态申请和释放内存。在链表数组中，每个节点包含数据和指向下一个节点的指针。

链表队列是一种基于链表实现的队列，相比于顺序队列而言，链表队列不需要预先申请固定大小的内存空间，可以根据需要动态申请和释放内存。在链表队列中，每个节点包含一个数据元素和一个指向下一个节点的指针，头节点表示队头，尾节点表示队尾，入队操作在队尾插入元素，出队操作在队头删除元素，队列的长度由节点数量决定。由于链表队列没有容量限制，因此可以处理任意数量的元素，但是相比于顺序队列，链表队列的访问速度较慢，因为需要通过指针来访问下一个节点。

读者需自行创建头文件linkqueue.h并拷贝如下链表队列代码实现；

#include <stdio.h> #include <string.h> #include <stdlib.h> struct BiNode { int data; struct BiNode *lchild; struct BiNode *rchild; }; // 链表结点的数据类型 struct QueueNode { struct QueueNode *next; }; struct LQueue { struct QueueNode header; // 头结点 struct QueueNode *rear; // 尾指针 int size; }; typedef void* LinkQueue; // 初始化 LinkQueue InitLinkQueue() { struct LQueue *queue = malloc(sizeof(struct LQueue)); if (NULL == queue) { return NULL; } queue->header.next = NULL; queue->size = 0; queue->rear = &(queue->header); return queue; } // 入队 void PushLinkQueue(LinkQueue queue, void *data) { if (NULL == queue || NULL == data) { return; } struct LQueue *q = (struct LQueue *)queue; struct QueueNode *n = (struct QueueNode *)data; q->rear->next = n; n->next = NULL; // 更新尾指针 q->rear = n; q->size++; } // 出队 void PopLinkQueue(LinkQueue queue) { if (NULL == queue) { return; } struct LQueue *q = (struct LQueue *)queue; if (q->size == 0) { return; } if (q->size == 1) { q->header.next = NULL; q->rear = &(q->header); q->size--; return; } struct QueueNode *pFirstNode = q->header.next; q->header.next = pFirstNode->next; q->size--; } // 获得队头元素 void* FrontLinkQueue(LinkQueue queue) { if (NULL == queue) { return NULL; } struct LQueue *q = (struct LQueue *)queue; return q->header.next; } // 获得队尾元素 void* BackLinkQueue(LinkQueue queue) { if (NULL == queue) { return NULL; } struct LQueue *q = (struct LQueue *)queue; return q->rear; } // 获得队列长度 int SizeLinkQueue(LinkQueue queue) { if (NULL == queue) { return -1; } struct LQueue *q = (struct LQueue *)queue; return q->size; } // 销毁队列 void DestroyLinkQueue(LinkQueue queue) { if (NULL == queue) { return; } struct LQueue *q = (struct LQueue *)queue; q->header.next = NULL; q->rear = NULL; q->size = 0; free(queue); queue = NULL; }

在主函数中使用也很容易，首先定义Studnet结构体，通过调用InitLinkQueue初始化队列，并使用PushLinkQueue向队列中插入元素，函数BackLinkQueue可用于获取到队列队尾元素，函数PopLinkQueue用于弹出元素，函数DestroyLinkQueue则用于销毁队列。

#include"linkqueue.h" struct Student { struct QueueNode node; char name[64]; int age; }; int main(int argc, char *argv[]) { // 初始化队列 LinkQueue queue = InitLinkQueue(); // 创建数据 struct Student p1 = { NULL, "aaa", 10 }; struct Student p2 = { NULL, "bbb", 20 }; struct Student p3 = { NULL, "ccc", 30 }; struct Student p4 = { NULL, "ddd", 40 }; struct Student p5 = { NULL, "eee", 50 }; struct Student p6 = { NULL, "fff", 60 }; // 插入队列 PushLinkQueue(queue, &p1); PushLinkQueue(queue, &p2); PushLinkQueue(queue, &p3); PushLinkQueue(queue, &p4); PushLinkQueue(queue, &p5); PushLinkQueue(queue, &p6); struct Student *pBack = (struct Student *)BackLinkQueue(queue); printf("队尾元素: %s %d\n", pBack->name, pBack->age); while (SizeLinkQueue(queue) > 0) { // 获得队头元素 struct Student *person = (struct Student *)FrontLinkQueue(queue); // 打印队头元素 printf("姓名: %s 年龄: %d \n", person->name, person->age); // 弹出队头元素 PopLinkQueue(queue); } // 销毁队列 DestroyLinkQueue(queue); system("pause"); return 0; }

本文作者： 王瑞 本文链接： www.lyshark.com/post/64399f2.html 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！