链式栈(Chain stack)

  1  /*linkstack.h*/       
  2 #ifndef LINKSTACK_H
  3 #define LINKSTACK_H
  4 
  5 #include <stdlib.h>//malloc
  6 #include <stdbool.h>//bool
  7 
  8 //链表节点的数据类型默认是　int
  9 #ifndef LINKSTACK_DATATYPE
 10 #define LINKSTACK_DATATYPE int
 11 #endif
 12 
 13 typedef LINKSTACK_DATATYPE datatype;//取别名
 14 
 15 /*
 16  * 链式栈节点类型
 17  * 即链表节点类型
 18 */
 19 
 20 struct node
 21 {
 22   //数据域
 23   datatype data;
 24   //单链表指针域
 25   struct node *next;
 26 };
 27 
 28 /*
 29  * 链式栈的管理结构体
 30  */
 31 typedef struct
 32 {
 33     //栈顶元素指针
 34     struct node *top;
 35     //链表节点个数
 36     int size;
 37 }linkstack;
 38 
 39 /*
 40  * 初始化链式栈的管理结构体
 41  * 参数：无
 42  * 返回值：
 43  *      成功：返回链式栈的管理结构体指针
 44  *      失败：返回NULL
 45  */
 46 static linkstack *init_linkstack(void)
 47 {
 48     linkstack *ls = malloc(sizeof(linkstack));
 49     if(ls != NULL)
 50     {
 51         //初始时　链式栈的节点个数为0
 52         ls->size = 0;
 53         //初始时　链式栈的栈顶指针指向空
 54         ls->top = NULL;
 55     }
 56     return ls;
 57 }
 58 
 59 /*
 60  * 链式栈的管理结构体
 61  * 参数：
 62  *      man_struct：链式栈的管理结构体指针
 63  * 返回值：
 64  *      链式栈为空：返回true
 65  *      链式栈非空：返回false
 66  */
 67 static bool linkstack_empty(linkstack *man_struct)
 68 {
 69     //栈中节点元素个数为0
 70     return man_struct->size == 0;
 71 }
 72 
 73 
 74 /*
 75  *将新节点入栈
 76  *参数：
 77  *     man_struct：链式栈的管理结构体指针
 78  *     new_node：新节点的指针
 79  * 返回值：无
 80  */
 81 static void linkstack_push(linkstack *man_struct,struct node * new_node)
 82 {
 83     //新节点的指针　指向　原栈顶的节点
 84     new_node->next = man_struct->top;
 85     //更新原栈顶的节点(栈顶指针指向新节点)
 86     man_struct->top = new_node;
 87     //链式栈的元素加1
 88     man_struct->size++;
 89 }
 90 
 91 /*
 92  * 读取栈顶节点的数据域
 93  * 参数：
 94  *     man_struct：链式栈的管理结构体指针
 95  *     save_node：指向栈顶指针的　指针
 96  * 返回值：
 97  *     成功：返回true
　　　*　　　失败：返回false
 98  */
 99 static bool linkstack_top(linkstack *man_struct,struct node **save_node)
100 {
101     //栈空则失败
102     if(linkstack_empty(man_struct))
103         return false;
104 
105     //为用户提供栈顶节点地址
106     *save_node = man_struct->top;
107     return true;
108 }
109 
110 /*
111  *节点出栈
112  * 参数：
113  *      man_struct：链式栈的管理结构体指针
114  *返回值：
115  *      成功：返回true
116  *      失败：返回false(栈空)
117  */
118 static bool linkstack_pop(linkstack *man_struct)
119 {
120     //栈空就失败
121     if(linkstack_empty(man_struct))
122         return false;
123 
124     //栈顶节点准备出栈
125     struct node *p = man_struct->top;
126 
127     //管理结构体的栈顶指针指向下面的节点
128     man_struct->top = man_struct->top->next;
129     //栈节点的元素减1
130     man_struct->size--;
131 
132     p->next = NULL;//取消指向
133     free(p);//释放节点
134     return true;
135 }
136 /*
137  *遍历链式栈　回调　用户实现的访问数据域的函数
138  * 参数：
139  *     man_struct：链式栈的管理结构体
140  *     hander：用户实现的函数　的指针
141  */
142 static bool linkstack_travel(linkstack *man_struct,void (*hander)(datatype))
143 {
144    //链式栈为空则失败
145    if(linkstack_empty(man_struct))
146        return false;
147 
148    //记录链式栈节点的指针(过渡使用)
149    struct node *t = man_struct->top;
150    while(1)
151    {
152        //调用用户实现的访问数据域的函数
153         hander(t->data);
154         //下一个节点
155         t = t->next;
156 
157         //如果遍历结束则退出while
158         if(t == NULL)
159             break;
160    }
161    return true;
162 }
163 
164 /*
165  * 链式栈回归初始化
166  * 参数：
167  *      **man_struct：链式栈的管理结构体指针　的指针
168  * 返回值：无
169  */
170 static void uninit_linkstack(linkstack **man_struct)
171 {
172     //从栈顶开始释放节点
173     struct node *d = (*man_struct)->top;
174     while(d)//非空
175     {
176         //记录下一个节点
177         struct node *tmp = d->next;
178         //释放该当前节点
179         free(d);
180         //下一个节点
181         d = tmp;
182     }
183     //回归初始化
184     (*man_struct)->top = NULL;
185     (*man_struct)->size = 0;
186 }
187 
188 #endif // LINKSTACK_H
189         

 1 /*main.c*/
 2 #include <stdio.h>
 3 
 4 #define LINKSTACK_DATATYPE int
 5 #include "linkstack.h"
 6 
 7 /*
 8  * 申请内存存放新节点
 9  * 参数：
10  *      data：节点的数据域(根据实际情况)
11  * 返回值：
12  *      新节点的地址(堆内存地址)
13  */
14 static struct node *new_node(int data)
15 {
16     struct node *n = malloc(sizeof(struct node));
17     if(n != NULL)
18     {
19         n->data = data;//数据域
20         n->next = NULL;//指针域
21     }
22     return n;
23 }
24 
25 /*
26  * 用户实现的访问数据域的函数　回调
27  * 参数：
28  *      data：数据
29  * 返回值：无
30  */
31 void show(int data)
32 {
33     printf("%d",data);
34 }
35 
36 /*
37  *主函数
38  */
39 int main()
40 {
41     //初始化链式栈的管理结构体
42     linkstack *man_struct = init_linkstack();
43     if(man_struct == NULL)
44     {
45         perror(" ");
46         return 0;
47     }
48 
49     int num,tmp;
50 
51     while(1)
52     {
53         printf("输入：");
54 
55         if(scanf("%d",&num) !=1)
56         {
57             //清空非法输入
58             while(getchar()!=‘\n‘);
59             continue;
60         }
61 
62         if(num == -1)//来个结束
63             return 0;
64 
65         while(1)
66         {
67             tmp = num/8;//短除法
68             //余数入栈
69             linkstack_push(man_struct,new_node(num%8));
70 
71             if(tmp == 0)//计算完毕则退出while循环
72                 break;
73 
74             num = tmp;//否者继续
75         }
76 
77         printf("p is :0");
78         //遍历链式栈(只读)
79         linkstack_travel(man_struct,show);
80 
81         printf("\n");
82 
83         //链式栈的管理结构体回归初始化
84         uninit_linkstack(&man_struct);
85     }
86 
87     return 0;
88 }

 1 输入：0
 2 p is :00
 3 输入：8
 4 p is :010
 5 输入：7
 6 p is :07
 7 输入：256256
 8 p is :0764400
 9 输入：-1
10 Press <RETURN> to close this window...