C语言实现staque结构

登录 · 发表于 2022-10-22 15:12:28

C语言实现staque结构

1. 使用说明

staque结构以单链表方式实现，结合了stack与queue结构：pop_front+push_front使用方式为stack；pop_front+push_back使用方式是queue。
首尾插入和顶部弹出是运行效率最高的，此外还实现了任意位置的插入、移除和访问功能。
带有返回值的函数：返回值如果是void*类型，则NULL代表执行失败；如果是int类型，则0为成功，-1为失败。

2. 代码实现

staque.h

1 #ifndef __STAQUE_H
2 #define __STAQUE_H
3
4 typedef
5 struct unidirectional_node
6 {
7 void* p_data;
8 struct unidirectional_node* p_next;
9 }STRUCT_UD_NODE,
10 * P_STRUCT_UD_NODE;
11
12 typedef
13 struct staque
14 {
15 unsigned int count;
16 P_STRUCT_UD_NODE p_first;
17 P_STRUCT_UD_NODE p_last;
18 }STRUCT_STAQUE,
19 * P_STRUCT_STAQUE;
20
21 P_STRUCT_STAQUE
22 f_staque_construct(void);
23
24 void
25 f_staque_push_back(P_STRUCT_STAQUE const p_stq, void* const p_data);
26
27 void
28 f_staque_push_front(P_STRUCT_STAQUE const p_stq, void* const p_data);
29
30 void*
31 f_staque_pop_front(P_STRUCT_STAQUE const p_stq);
32
33 int
34 f_staque_data_insert(P_STRUCT_STAQUE const p_stq, void* const p_data, const unsigned int index);
35
36 void*
37 f_staque_data_remove(P_STRUCT_STAQUE const p_stq, const unsigned int index);
38
39 void*
40 f_staque_data_access(P_STRUCT_STAQUE const p_stq, const unsigned int index);
41
42 int
43 f_staque_data_index(P_STRUCT_STAQUE const p_stq, void* const p_data, unsigned int* const p_index);
44
45 void
46 f_staque_destroy(P_STRUCT_STAQUE const p_stq);
47
48 #endif // !__STAQUE_H

复制代码

head
staque.c

1 #include "staque.h"
2 #include <stdlib.h>
3
4 #pragma warning(disable:6011)
5
6 P_STRUCT_STAQUE f_staque_construct(void)
7 {
8 P_STRUCT_STAQUE p_ret_vec = (P_STRUCT_STAQUE)malloc(sizeof(STRUCT_STAQUE));
9 p_ret_vec->count = 0;
10 p_ret_vec->p_first = NULL;
11 p_ret_vec->p_last = NULL;
12 return p_ret_vec;
13 }
14
15 void innf_add_first_node(P_STRUCT_STAQUE const p_stq, void* const p_data)
16 {
17 p_stq->p_first = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE));
18 p_stq->p_first->p_data = p_data;
19 p_stq->p_first->p_next = NULL;
20 p_stq->p_last = p_stq->p_first;
21 p_stq->count = 1;
22 }
23
24 void* innf_remove_last_node(P_STRUCT_STAQUE const p_stq)
25 {
26 void* p_ret_data = p_stq->p_first->p_data;
27 free(p_stq->p_first);
28 p_stq->p_first = NULL;
29 p_stq->p_last = NULL;
30 p_stq->count = 0;
31 return p_ret_data;
32 }
33
34 void f_staque_push_back(P_STRUCT_STAQUE const p_stq, void* const p_data)
35 {
36 switch (p_stq->count)
37 {
38 case 0:
39 innf_add_first_node(p_stq, p_data);
40 return;
41 }
42 P_STRUCT_UD_NODE p_node = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE));
43 p_node->p_data = p_data;
44 p_node->p_next = NULL;
45 p_stq->p_last->p_next = p_node;
46 p_stq->p_last = p_node;
47 p_stq->count++;
48 }
49
50 void f_staque_push_front(P_STRUCT_STAQUE const p_stq, void* const p_data)
51 {
52 switch (p_stq->count) {
53 case 0:
54 innf_add_first_node(p_stq, p_data);
55 return;
56 }
57 P_STRUCT_UD_NODE p_node = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE));
58 p_node->p_data = p_data;
59 p_node->p_next = p_stq->p_first;
60 p_stq->p_first = p_node;
61 p_stq->count++;
62 }
63
64 void* f_staque_pop_front(P_STRUCT_STAQUE const p_stq)
65 {
66 switch (p_stq->count) {
67 case 0:
68 return NULL;
69 case 1:
70 return innf_remove_last_node(p_stq);
71 }
72 void* p_ret_data = p_stq->p_first->p_data;
73 P_STRUCT_UD_NODE p_node = p_stq->p_first->p_next;
74 free(p_stq->p_first);
75 p_stq->p_first = p_node;
76 p_stq->count--;
77 return p_ret_data;
78 }
79
80 int f_staque_data_insert(P_STRUCT_STAQUE const p_stq, void* const p_data, const unsigned int index)
81 {
82 switch (index) {
83 case 0:
84 f_staque_push_front(p_stq, p_data);
85 return 0;
86 }
87 if (index == p_stq->count) {
88 f_staque_push_back(p_stq, p_data);
89 return 0;
90 }
91 else if (index > p_stq->count) {
92 return -1;
93 }
94 P_STRUCT_UD_NODE p_node = p_stq->p_first;
95 for (unsigned int i = 0 ; i < index - 1; i++) {
96 p_node = p_node->p_next;
97 }
98 P_STRUCT_UD_NODE p_node_next = p_node->p_next;
99 p_node->p_next = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE));
100 p_node->p_next->p_data = p_data;
101 p_node->p_next->p_next = p_node_next;
102 p_stq->count++;
103 return 0;
104 }
105
106 void* f_staque_data_remove(P_STRUCT_STAQUE const p_stq, const unsigned int index)
107 {
108 switch (p_stq->count) {
109 case 0:
110 return NULL;
111 }
112 switch (index) {
113 case 0:
114 return f_staque_pop_front(p_stq);
115 }
116 if (index >= p_stq->count) {
117 return NULL;
118 }
119 P_STRUCT_UD_NODE p_node = p_stq->p_first;
120 for (unsigned int i = 0; i < index - 1; i++) {
121 p_node = p_node->p_next;
122 }
123 P_STRUCT_UD_NODE p_node_next = p_node->p_next->p_next;
124 void* p_ret_data = p_node->p_next->p_data;
125 free(p_node->p_next);
126 p_node->p_next = p_node_next;
127 p_stq->count--;
128 return p_ret_data;
129 }
130
131 void* f_staque_data_access(P_STRUCT_STAQUE const p_stq, const unsigned int index)
132 {
133 switch (p_stq->count) {
134 case 0:
135 return NULL;
136 }
137 if (index >= p_stq->count) {
138 return NULL;
139 }
140 P_STRUCT_UD_NODE p_node = p_stq->p_first;
141 for (unsigned int i = 0; i < index; i++) {
142 p_node = p_node->p_next;
143 }
144 return p_node->p_data;
145 }
146
147 int f_staque_data_index(P_STRUCT_STAQUE const p_stq, void* const p_data, unsigned int* const p_index)
148 {
149 P_STRUCT_UD_NODE p_node = p_stq->p_first;
150 for (unsigned int i = 0; i < p_stq->count; i++) {
151 if (p_node->p_data == p_data) {
152 *p_index = i;
153 return 0;
154 }
155 p_node = p_node->p_next;
156 }
157 return -1;
158 }
159
160 void f_staque_destroy(P_STRUCT_STAQUE const p_stq)
161 {
162 if (p_stq == NULL) {
163 return;
164 }
165 while (p_stq->count != 0) {
166 f_staque_pop_front(p_stq);
167 }
168 free(p_stq);
169 }

复制代码

code

3. 代码测试

source.c

1 #include "staque.h"
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 #pragma warning(disable:6011)
6
7 int main(int argc, char** argv)
8 {
9 P_STRUCT_STAQUE p_stq = f_staque_construct();
10 const unsigned int arr_size = 10;
11 int* arr = (int*)malloc(sizeof(int) * arr_size);
12 printf("arr: ");
13 for (unsigned int i = 0; i < arr_size; i++) {
14 *(arr + i) = i * 2;
15 printf("%d ", *(arr + i));
16 }
17 printf("\nstaque push back all\n");
18 for (unsigned int i = 0; i < arr_size; i++) {
19 f_staque_push_back(p_stq, arr + i);
20 }
21 printf("access staque data\n");
22 for (unsigned int i = 0; i < p_stq->count; i++) {
23 printf("%d ", *(int*)f_staque_data_access(p_stq, i));
24 }
25 printf("\nstaque push front all\n");
26 for (unsigned int i = 0; i < arr_size; i++) {
27 f_staque_push_front(p_stq, arr + i);
28 }
29 for (P_STRUCT_UD_NODE p_node = p_stq->p_first; p_node != NULL; p_node = p_node->p_next) {
30 printf("%d ", *(int*)p_node->p_data);
31 }
32 printf("\ninsert to half\n");
33 f_staque_data_insert(p_stq, &p_stq->count, p_stq->count / 2);
34 for (P_STRUCT_UD_NODE p_node = p_stq->p_first; p_node != NULL; p_node = p_node->p_next) {
35 printf("%d ", *(int*)p_node->p_data);
36 }
37 unsigned int index = 0;
38 f_staque_data_index(p_stq, &p_stq->count, &index);
39 printf("\nget index of that node: %d", index);
40 printf("\nremove half: %d\n", *(int*)f_staque_data_remove(p_stq, p_stq->count / 2));
41 for (P_STRUCT_UD_NODE p_node = p_stq->p_first; p_node != NULL; p_node = p_node->p_next) {
42 printf("%d ", *(int*)p_node->p_data);
43 }
44 printf("\nstaque pop front all\n");
45 while (p_stq->count != 0) {
46 printf("%d ", *(int*)f_staque_pop_front(p_stq));
47 }
48 printf("\n");
49 f_staque_destroy(p_stq);
50 free(arr);
51 return 0;
52 }

复制代码

test
运行结果：
arr: 0 2 4 6 8 10 12 14 16 18
staque push back all
access staque data
0 2 4 6 8 10 12 14 16 18
staque push front all
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18
insert to half
18 16 14 12 10 8 6 4 2 0 21 0 2 4 6 8 10 12 14 16 18
get index of that node: 10
remove half: 20
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18
staque pop front all
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

本帖子中包含更多资源

浏览过的版块