各位看官們,大家好,從今天開始,我們講大型章回體科技小說 :C栗子,也就是C語言實例。閑話休提, 言歸正轉(zhuǎn)。讓我們一起talk C栗子吧!
看官們,上一回中咱們說的是棧和特點和基本操作,最后通過順序存儲的方式實現(xiàn)了棧,這一回咱們繼續(xù) 說棧,不過咱們這一回說的是棧的鏈式存儲方式。
在代碼中通過雙向鏈表來實現(xiàn)棧的鏈式存儲。入棧操作沿著表頭到表尾的方向進行,出棧操作與其正好相 反(就把它當作雙向鏈表的一個使用實例吧)。棧的結(jié)點可以看作是鏈表中的結(jié)點,對棧的操作,可以看 作是在鏈表中進行插入或者刪除結(jié)點操作。只不過插入或者刪除時要遵循棧“先進后出"的特點。棧的類型 中增加了一個size成員,可以通過它方便地得出棧的長度。與棧的順序存儲方式相比,多了一個銷毀棧的 功能。因為棧中的空間都是動態(tài)分配得來的,每次入棧操作都會分配一塊內(nèi)存空間,與其相反,每次出棧 操作都會把內(nèi)存空間釋放掉。但是在實際程序中入棧和出棧并不是成對出現(xiàn)的,也就是說,如果使用完棧 后,沒有通過出棧操作來釋放動態(tài)空間,那么就會造成內(nèi)存泄漏。所以我增加了銷毀棧的功能,以方便在 程序的最后檢查棧中動態(tài)分配來的空間是否被釋放。
棧的鏈式存儲與棧的順序存儲相比,最大的優(yōu)點就是不需要事先知道棧的長度,只要內(nèi)存空間足夠大就能 存放足夠多的元素到棧中。不過,它也有缺點,那就是入棧和出棧操作要復(fù)雜,而且效率低。總之,在實 際的程序中如果事先知道棧的長度,可以使用棧的順序存儲,如果與事先不知道棧的長度,那么可以使用 棧的鏈式存儲,這樣比較靈活一些。
看官們,詳細的代碼如下,大家可以參考:
1 /* **************************
2 * Head file of Stack
3 * *************************/
4 #ifndef STACK_H
5 #define STACK_H
6
7 #include<stdio.h>
8 #include<stdlib.h>
9
10 #define SUCCESS 0
11 #define FAILE 1
12
13 typedef struct _StackElmt
14 {
15 int data;
16 struct _StackElmt *pre;
17 struct _StackElmt *next;
18 }StackElmt; //把int當作棧中元素的類型,實際中可以使用其它的類型或者自己定義一個類型
19
20 typedef struct _Stack{
21 StackElmt *base; //棧底指針
22 StackElmt *top; //棧頂指針,它指向的區(qū)域存放StackElmt類型的值
23 int size; //方便統(tǒng)計棧的長度
24 }Stack;
25
26 //聲明函數(shù)原型,這里有入棧和出棧操的函數(shù)
27 int StackInit(Stack *s);
28 int StackPrint(Stack *s);
29 int StackPush(Stack *s, int e);
30 int StackPop(Stack *s, int *e);
31 int StackDestroy(Stack *s);
32
33 #endif /*STACK_H*/
1 /* **************************
2 * Soure file of Stack
3 * *************************/
4
5 #include"Ex015_Stack2.h"
6
7 //實現(xiàn)List的函數(shù),為了方便,放到了主函數(shù)所在的文件中,最好是單獨建立實現(xiàn)函數(shù)的源文件
8 //
9 //初始化中棧
10 int StackInit(Stack *s)
11 {
12 if(NULL == s)
13 return FAILE;
14
15 s->top = s->base = NULL;
16 s->size = 0;
17
18 return SUCCESS;
19 }
20
21 //輸出棧中存放的元素
22 int StackPrint(Stack *s)
23 {
24 int index = 0;
25 StackElmt *t = NULL;
26
27 if(NULL == s)
28 return FAILE;
29
30 if(s->size == 0)
31 {
32 printf("the Stack is empty,there is not any element \n");
33 return FAILE;
34 }
35
36 t = s->base;
37 while(NULL != t)
38 {
39 printf("%d ",t->data);
40 t = t->next;
41 }
42
43 printf("\n ");
44
45 return SUCCESS;
46 }
47
48 //入棧函數(shù),top指向棧頂,每次push操作都會分配一個空間,top永遠指向該空間
49 int StackPush(Stack *s, int e)
50 {
51 StackElmt *node = NULL;
52
53 if(NULL == s)
54 return FAILE;
55
56 node = (StackElmt *)malloc( sizeof(StackElmt) );
57
58 if(NULL != node)
59 {
60 if(NULL == s->base)
61 {
62 s->top = s->base = node;
63 node->pre = NULL;
64 }
65 else
66 {
67 (s->top)->next = node;
68 node->pre = s->top;
69 s->top = node; //相當于順序存儲中的top++
70 }
71
72 node->data = e;
73 node->next = NULL;
74 (s->size)++;
75
76 return SUCCESS;
77 }
78 else
79 return FAILE;
80 }
81
82 //出棧函數(shù),先把top指向的元素出棧,然后釋放top指向的空間
83 int StackPop(Stack *s, int *e)
84 {
85 StackElmt *t = NULL;
86
87 if(NULL == s)
88 return FAILE;
89
90 if(s->size == 0)
91 {
92 printf("the Stack is empty \n");
93 return FAILE;
94 }
95
96 *e = (s->top)->data ;
97 t = (s->top)->pre;
98 free(s->top);
99 s->top = t; //相當于top--
100
101 if(s->size == 1) //最后一個元素出棧時,base和top都為NULL
102 s->base = s->top;
103
104 (s->size)--;
105
106 return SUCCESS;
107 }
108
109 //棧銷毀函數(shù),因為有動態(tài)分配的空間,如果不執(zhí)行出棧操作,要把棧destroy
110 int StackDestroy(Stack *s)
111 {
112 int t = 0;
113 int result = 0;
114
115 if(NULL == s)
116 return FAILE;
117
118 while(NULL != (s->base) )
119 result = StackPop(s,&t);
120
121 return result;
122 }
123
124 int main()
125 {
126 int i = 0;
127 int e = 0;
128 Stack stack ;
129
130 if( SUCCESS == StackInit(&stack) )
131 StackPrint(&stack);
132
133 StackPush(&stack,7);
134 StackPrint(&stack);
135
136 StackPop(&stack,&e);
137 printf("%d is poped \n",e);
138
139 while(i++ < 5)
140 {
141 if( SUCCESS == StackPush(&stack,i) )
142 printf("%d is pushed \n",i);
143 else
144 printf("push failed \n");
145 }
146
147 while(i-- > 0)
148 {
149 if( SUCCESS == StackPop(&stack,&e) )
150 printf("%d is poped \n",e);
151 else
152 printf("pop failed \n");
153 }
154
155 if( SUCCESS == StackDestroy)
156 printf("Stack destroy successfully \n");
157 else
158 printf("Stack need not to destroy \n");
159
160 }
各位看官,關(guān)于棧的例子咱們就說到這里。欲知后面還有什么例子,且聽下回分解。