View Code 1 #include < cstdio > 2 #include < cstdlib > 3 // 链栈 Freeze 2010 10 4 4 typedef struct Point{ 5 int low; 6 int high; 7 }Point; 8 typedef Point StackElemType; 9 10 typedef struct Node 11 { 12 StackElemType data; 13 struct Node * next; 14 }Node; 15 typedef struct { 16 Node * base ; // 存储空间基指针； 17 Node * top; // 栈顶指点针 18 int size; // 长度，默认为0 19 }LiStack; 20 21 22 LiStack * initStack(LiStack * S); // 构造一个空栈S 23 void freeStack(LiStack * S); // 若栈已存在，销毁栈S 24 bool isEmpty( const LiStack * S); // 若栈S为空，则返回ture，否则返回false 25 StackElemType get ( const LiStack * S); // 返回栈顶元素 26 Node * push(LiStack * S,StackElemType e); // 入栈 27 StackElemType pop(LiStack * S); // 出栈 28 29 30 // 构造一个空栈S 31 LiStack * initStack(LiStack * S) 32 { 33 S = (LiStack * )malloc( sizeof (LiStack)); 34 if ( ! S) 35 { 36 printf( " 内存不足\n " ); 37 exit( 1 ); 38 } 39 S -> top = NULL; 40 S -> base = NULL; 41 S -> size = 0 ; 42 return S; 43 } 44 45 // 销毁栈S 46 void freeStack(LiStack * S) 47 { 48 while (S -> size > 0 ) 49 pop(S); 50 free(S); 51 } 52 53 // 若栈S为空，则返回ture，否则返回false 54 bool isEmpty( const LiStack * S) 55 { 56 return (S -> size == 0 ); 57 } 58 59 // 返回栈顶元素 若栈为空，则报错 60 StackElemType get ( const LiStack * S) 61 { 62 if ( ! isEmpty(S)) 63 return S -> top -> data; 64 else { 65 printf( " 空栈,无法入栈!\n " ); 66 exit( 1 ); 67 } 68 } 69 70 // 插入元素e成为新的栈顶元素 71 Node * push(LiStack * S,StackElemType e) 72 { 73 Node * temp = (Node * )malloc( sizeof (Node)); 74 if ( ! temp) 75 { 76 printf( " 内存不足\n " ); 77 exit( 1 ); 78 } 79 temp -> data = e; 80 if (S -> size == 0 ) // 插入的是第一个元素 81 { 82 S -> top = temp; 83 S -> base = temp; 84 temp -> next = NULL; 85 } 86 else 87 { 88 temp -> next = S -> top; 89 S -> top = temp; 90 } 91 S -> size ++ ; 92 return temp; 93 } 94 95 // 出栈 96 StackElemType pop(LiStack * S) 97 { 98 if (isEmpty(S)){ 99 printf( " 空栈，无法出栈!\n " ); 100 exit( 1 ); 101 } else { 102 S -> size -- ; 103 Node * temp = S -> top; 104 StackElemType data = S -> top -> data; 105 S -> top = temp -> next; 106 free(temp); 107 return data; 108 } 109 }