栈的链式实现

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 <stdlib.h>
  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             else
106             {
107                 FirstCell = S->Next;
108                 S->Next = S->Next->Next;
109                 free( FirstCell );
110             }
111         }
112 /* END */