本节我们使用链表来实现一个队列。队列的特点是先进先出(FIFO)。普通队列的实现非常简单,下面是队列的实现代码:
#include "typedef.h" //节点 typedef struct s_node { void *data; struct s_node *next; } s_node; //队列数据结构 typedef struct { //元素大小 int ele_size; //头节点 s_node *header; //脚节点 s_node *footer; //用于释放节点数据的回调函数 void (*free_data)(); //用于访问节点数据内容的回调函数 void (*visit_data)(void *data); } s_queue; //构建一个队列 bool init_queue(s_queue *queue, int ele_size, void (*free_data)(), void (*visit_data)()) { if (queue == null) { return false; } queue->ele_size = ele_size; queue->free_data = free_data; queue->visit_data = visit_data; queue->header = null; queue->footer = null; return true; } //销毁队列 bool destroy_queue(s_queue *queue) { if (queue == null) { return false; } if (queue->header == null) { return true; } clear_queue(queue); return true; } //清空队列中所有元素 bool clear_queue(s_queue *queue) { if (queue == null) { return false; } //从头节点开始释放 s_node *p = queue->header; while (p != null) { //释放内存 queue->free_data(p->data); s_node *t = p; p = p->next; free(t); } queue->header = null; queue->footer = null; return true; } //在队列尾追加一个元素 bool queue_insert(s_queue *queue, void *e) { if (queue == null || e == null) { return false; } //申请新节点内存 s_node *p_new = (s_node *) malloc(sizeof(s_node)); p_new->data = e; p_new->next = null; if (queue->footer == null) { queue->header = p_new; queue->footer = p_new; return true; } queue->footer->next = p_new; queue->footer = p_new; return true; } //在队列头删除一个元素 bool queue_delete(s_queue *queue) { if (queue == null || queue->header == null) { return false; } s_node *p_del = queue->header; queue->header = queue->header->next; if (queue->footer == p_del) { queue->footer = queue->header->next; } queue->free_data(p_del); return true; } //对每个元素执行visit操作 bool queue_visit(s_queue *queue) { if (queue == null || queue->header == null) { return false; } //顺序访问每一个元素 s_node *p = queue->header; while (p != null) { queue->visit_data(p->data); p = p->next; } return true; }
再来写一个main函数来测试队列:
#include "queue.h" void free_int(void *data) { free(data); } void print_int(void *data) { printf("%d\n", *((int *) data)); } typedef struct { int no; int age; char *name; } student; void print_stu(void *data) { student *stu = (student *) data; printf("no:%d age:%d name:%s\n", stu->no, stu->age, stu->name); } void free_stu(void *data) { student *stu = (student *) data; free(stu->name); free(stu); } int main(int argc, char **args) { //用于存放int型数据的队列 s_queue queue_int; //释放内存函数与访问函数均是int型 init_queue(&queue_int, sizeof(int), free_int, print_int); //插入数据 for (int i = 0; i < 5; ++i) { int *e = (int *) malloc(sizeof(int)); *e = i; queue_insert(&queue_int, e); } //显示queue中所有数据内容 queue_visit(&queue_int); //销毁queue destroy_queue(&queue_int); printf("\n"); //用于存放student型数据的queue s_queue queue_stu; //释放内存函数与访问函数均是student型 init_queue(&queue_stu, sizeof(student), free_stu, print_stu); //在队列尾插入数据 student *stu1 = (student *) malloc(sizeof(student)); stu1->no = 15100101; stu1->age = 23; stu1->name = (char *) malloc(20); memcpy(stu1->name, "lidq", 20); queue_insert(&queue_stu, stu1); //在队列尾插入数据 student *stu2 = (student *) malloc(sizeof(student)); stu2->no = 15100102; stu2->age = 21; stu2->name = (char *) malloc(20); memcpy(stu2->name, "zhaoy", 20); queue_insert(&queue_stu, stu2); //在队列尾插入数据 student *stu3 = (student *) malloc(sizeof(student)); stu3->no = 15100103; stu3->age = 22; stu3->name = (char *) malloc(20); memcpy(stu3->name, "liuzh", 20); queue_insert(&queue_stu, stu3); //显示队列中所有内容 queue_visit(&queue_stu); printf("\n"); //在队列头删除元素 queue_delete(&queue_stu); //显示队列中所有内容 queue_visit(&queue_stu); //销毁队列 destroy_queue(&queue_stu); return 0; }
运行结果:
0 1 2 3 4 no:15100101 age:23 name:lidq no:15100102 age:21 name:zhaoy no:15100103 age:22 name:liuzh no:15100102 age:21 name:zhaoy no:15100103 age:22 name:liuzh 本例代码: code path chapter.02/e.g.2.4/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号