首页 / 更多教程 / 基于单向链表的队列的实现
基于单向链表的队列的实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了基于单向链表的队列的实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6031字，纯文字阅读大概需要9分钟。
内容图文
1.单链表实现
slist.h
1
#ifndef _SLIST_H
2
#define _SLIST_H
3 4 typedef struct _slist_node
5{
6struct _slist_node *p_next; /* 指向下一个结点的指针 */ 7}slist_node_t;
8 9typedef slist_node_t slist_head_t;
10 typedef int (*slist_node_process_t)(void *p_arg, slist_node_t *p_node);
1112int slist_init(slist_head_t *p_head);
13int slist_add(slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node);
14int slist_add_tail(slist_head_t *p_head, slist_node_t *p_node);
15int slist_add_head(slist_head_t *p_head, slist_node_t *p_node);
16int slist_del(slist_head_t *p_head, slist_node_t *p_node);
1718 slist_node_t *slist_prev_get(slist_head_t *p_head, slist_node_t *p_pos);
19 slist_node_t *slist_next_get(slist_head_t *p_head, slist_node_t *p_pos);
20 slist_node_t *slist_tail_get(slist_head_t *p_head);
21 slist_node_t *slist_begin_get(slist_head_t *p_head);
22 slist_node_t *slist_end_get (slist_head_t *p_head);
23int slist_foreach(slist_head_t *p_head,
24 slist_node_process_t pfn_node_process,
25void *p_arg);
2627#endif
slist.c
1 #include "slist.h" 2 #include <stdlib.h>
3 4int slist_init(slist_head_t *p_head)
5{
6if (p_head == NULL)
7 {
8return -1;
9 }
10 p_head->p_next = NULL;
11return0;
12}
1314int slist_add(slist_head_t *p_head, slist_node_t *p_pos, slist_node_t *p_node)
15{
16 p_node->p_next = p_pos->p_next;
17 p_pos->p_next = p_node;
18return0;
19}
2021int slist_add_tail(slist_head_t *p_head, slist_node_t *p_node)
22{
23 slist_node_t *p_tmp = slist_tail_get(p_head); /* 找到尾结点 */24return slist_add(p_head, p_tmp, p_node); /* 添加结点至尾结点之后 */25}
2627int slist_add_head(slist_head_t *p_head, slist_node_t *p_node)
28{
29return slist_add(p_head, p_head, p_node); /* 添加结点至头结点之后 */30}
3132int slist_del(slist_head_t *p_head, slist_node_t *p_node)
33{
34 slist_node_t *p_prev = slist_prev_get(p_head, p_node); /* 找到待删除结点的上一个结点 */35if (p_prev)
36 {
37 p_prev->p_next = p_node->p_next;
38 p_node->p_next = NULL;
39return0;
40 }
41return -1;
42}
4344 slist_node_t *slist_prev_get(slist_head_t *p_head, slist_node_t *p_pos)
45{
46 slist_node_t *p_tmp = p_head;
47while ((p_tmp != NULL) && (p_tmp->p_next != p_pos))
48 {
49 p_tmp = p_tmp->p_next;
50 }
51return p_tmp;
52}
5354 slist_node_t *slist_next_get(slist_head_t *p_head, slist_node_t *p_pos)
55{
56if (p_pos)
57 {
58return p_pos->p_next;
59 }
60return NULL;
61}
6263 slist_node_t *slist_tail_get(slist_head_t *p_head)
64{
65return slist_prev_get(p_head, NULL);
66}
6768 slist_node_t *slist_begin_get(slist_head_t *p_head)
69{
70return slist_next_get(p_head, p_head);
71}
7273 slist_node_t *slist_end_get(slist_head_t *p_head)
74{
75return NULL;
76}
7778int slist_foreach(slist_head_t *p_head,
79 slist_node_process_t pfn_node_process,
80void *p_arg)
81{
82 slist_node_t *p_tmp, *p_end;
83int ret;
8485if ((p_head == NULL) || (pfn_node_process == NULL))
86 {
87return -1;
88 }
89 p_tmp = slist_begin_get(p_head);
90 p_end = slist_end_get(p_head);
91while (p_tmp != p_end)
92 {
93 ret = pfn_node_process(p_arg, p_tmp);
94if (ret < 0)
95return ret; /* 不再继续遍历 */96 p_tmp = slist_next_get(p_head, p_tmp); /* 继续下一个结点 */97 }
98return0;
99 }
2.队列的实现
queue.h
1
#ifndef _QUEUE_H
2
#define _QUEUE_H
3 4 #include <stdbool.h>
5 #include <stddef.h>
6 7 typedef int queueElementT;
8 typedef struct queueCDT * queueADT;
910 queueADT newQueue(void);
11void freeQueue(queueADT queue);
12bool inQueue(queueADT queue, queueElementT value);
13bool outQueue(queueADT queue, queueElementT *p_alue);
14bool queueIsEmpty(queueADT queue);
15bool queueIsFull(queueADT queue);
16size_t getQueueLength(queueADT queue);
1718#endif
queue_slist.c
1 #include "queue.h" 2 #include <stdlib.h>
3 #include "slist.h" 4 5#define MAXQSIZE 100
6struct queueCDT
7{
8 slist_head_t list_head; /* 链表头结点 */ 9 slist_node_t *p_rear; /* 指向队列的尾结点 */10};
1112 typedef struct _queue_node_t
13{
14 slist_node_t node;
15 queueElementT data;
16} queue_node_t;
1718 queueADT newQueue(void)
19{
20 queueADT queue;
21 queue = (queueADT)malloc(sizeof(struct queueCDT));
22 slist_init(&queue->list_head);
23 queue->p_rear = &(queue->list_head);
24return queue;
25}
2627void freeQueue(queueADT queue)
28{
29while (!queueIsEmpty(queue))
30 {
31 slist_node_t *p_node = slist_begin_get(&queue -> list_head);
32 slist_del(&queue -> list_head, p_node);
33free((queue_node_t *)p_node);
34 }
35free(queue);
36}
3738bool inQueue(queueADT queue, queueElementT value)
39{
40if(queueIsFull(queue))
41 {
42returnfalse;
43 }
44 queue_node_t *p_node = (queue_node_t *)malloc(sizeof(queue_node_t));
45 p_node -> data = value;
46 slist_add(&queue->list_head, queue->p_rear,&(p_node->node));
47 queue->p_rear = queue->p_rear->p_next;
48returntrue;
49}
5051bool outQueue(queueADT queue, queueElementT *p_value)
52{
53if(queueIsEmpty(queue))
54 {
55returnfalse;
56 }
57 slist_node_t *p_node = slist_begin_get(&queue -> list_head);
58 *p_value = ((queue_node_t *)p_node) -> data;
59 slist_del(&queue -> list_head, p_node);
60free(p_node);
61returntrue;
62}
6364bool queueIsEmpty(queueADT queue)
65{
66return (slist_begin_get(&queue -> list_head) == slist_end_get(&queue -> list_head));
67}
6869bool queueIsFull(queueADT queue)
70{
71/* 链队列不会满 */72returnfalse;
73}
7475staticint _numElems_node(void *p_arg, slist_node_t *p_node)
76{
77 (*(size_t *)p_arg)++;
78return0;
79}
8081size_t getQueueLength(queueADT queue)
82{
83 size_t count = 0;
84 slist_foreach(&queue->list_head, _numElems_node, &count);
85return count;
86 }
3.Demo
main.c
1 #include <stdio.h>
2 #include "queue.h" 3 4int main(int argc, char *argv[])
5{
6 queueADT queue;
7int temp, i;
8 9 queue = newQueue();
10for(i = 0; i < 16; i++)
11 {
12 inQueue(queue, i);
13 }
14 printf("The length is %d\n", (int)getQueueLength(queue));
15while (!queueIsEmpty(queue))
16 {
17 outQueue(queue, &temp);
18 printf("%d ", temp);
19 }
20 freeQueue(queue);
21return0;
22 }
原文：https://www.cnblogs.com/chenweilin/p/12874147.html
内容总结
以上是互联网集市为您收集整理的基于单向链表的队列的实现全部内容，希望文章能够帮你解决基于单向链表的队列的实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】