stackli.h

1        /* 栈的链表实现的类型声明*/ 2  3         typedef int ElementType; 4 /* START: fig3_39.txt */ 5         #ifndef _Stack_h 6         #define _Stack_h 7  8         struct Node; 9         typedef struct Node *PtrToNode;10         typedef PtrToNode Stack;11 12         int IsEmpty( Stack S );13         Stack CreateStack( void );14         void DisposeStack( Stack S );15         void MakeEmpty( Stack S );16         void Push( ElementType X, Stack S );17         ElementType Top( Stack S );18         void Pop( Stack S );19 20         #endif  /* _Stack_h */21 22 /* END */

 

stackli.c

1         #include "stackli.h"  2         #include "fatal.h"  3         #include 
     
        4   5         struct Node  6         {  7             ElementType Element;  8             PtrToNode   Next;  9         }; 10  11 /* START: fig3_40.txt */ 12  13         /* 判断栈是否为空 */ 14         int 15         IsEmpty( Stack S ) 16         { 17             return S->Next == NULL; 18         } 19 /* END */ 20  21 /* START: fig3_41.txt */ 22  23         /* 创建一个空栈 */ 24         Stack 25         CreateStack( void ) 26         { 27             Stack S; 28  29             S = malloc( sizeof( struct Node ) ); 30             if( S == NULL ) 31                 FatalError( "Out of space!!!" ); 32             S->Next = NULL; 33             MakeEmpty( S ); 34             return S; 35         } 36  37         /* 使栈为空 */ 38         void 39         MakeEmpty( Stack S ) 40         { 41             if( S == NULL ) 42                 Error( "Must use CreateStack first" ); 43             else 44                 while( !IsEmpty( S ) ) 45                     Pop( S ); 46         } 47 /* END */ 48  49          /* 释放栈 */ 50         void 51         DisposeStack( Stack S ) 52         { 53             MakeEmpty( S ); 54             free( S ); 55         } 56  57 /* START: fig3_42.txt */ 58  59         /* 入栈 */ 60         void 61         Push( ElementType X, Stack S ) 62         { 63             PtrToNode TmpCell; 64  65             TmpCell = malloc( sizeof( struct Node ) ); 66             if( TmpCell == NULL ) 67                 FatalError( "Out of space!!!" ); 68             else 69             { 70                 TmpCell->Element = X; 71                 TmpCell->Next = S->Next; 72                 S->Next = TmpCell; 73             } 74         } 75         /* 76         有头节点，栈顶是第一个节点，入栈是插到第一个节点前面，变成第一个节点 77         这样出栈方便 78         */ 79         80 /* END */ 81  82 /* START: fig3_43.txt */ 83  84         /* 返回栈顶元素 */ 85         ElementType 86         Top( Stack S ) 87         { 88             if( !IsEmpty( S ) ) 89                 return S->Next->Element; 90             Error( "Empty stack" ); 91             return 0;  /* Return value used to avoid warning */ 92         } 93 /* END */ 94  95 /* START: fig3_44.txt */ 96          97         /* 出栈 */ 98         void 99         Pop( Stack S )100         {101             PtrToNode FirstCell;102 103             if( IsEmpty( S ) )104                 Error( "Empty stack" );105             else106             {107                 FirstCell = S->Next;108                 S->Next = S->Next->Next;109                 free( FirstCell );110             }111         }112 /* END */