（3）数据结构——栈（数组）实现

1 /*********************************************************************
2 *:
3 *:
4 *: Author: dspeeding
5 *: Copyright (c) 2012, dspeeding
6 *:
7 *: Created at: 2012.06.15
8 *: Last modified: 2012.06.15
9 *:
10 *: Introduction: 数组栈&＃xff08;数据结构&＃xff09;的c实现
11 *:
12 *:
13 *:*********************************************************************/
14 #ifndef _ARRAYSTACK_H_
15 #define _ARRAYSTACK_H_
16
17 #include "ElemType.h"
18
19
20 typedef struct TDefArrayStack
21 {
22 int nTop;
23 int nMaxSize;
24 PElemType pArray;
25 }ArrayStack;
26
27 typedef ArrayStack* PArrayStack;
28 typedef const ArrayStack CArrayStack;
29 typedef const ArrayStack* PCArrayStack;
30
31
32 /****************************************
33 Purpose : 初始化数组栈
34 Input : pStack -- 栈指针
35 nMaxSize -- 栈容量
36 Return : 0 --OK
37 -1 --FAIL
38 *****************************************/
39 int InitArrayStack(PArrayStack pStack, int nMaxSize);
40
41
42 /****************************************
43 Purpose : 判断栈是否为空
44 Input : pStack -- 栈指针
45 Return : 0 --空
46 -1 --非空
47 *****************************************/
48 int IsEmptyArrayStack(PArrayStack pStack);
49
50
51
52 /****************************************
53 Purpose : 判断栈是否已满
54 Input : pStack -- 栈指针
55 Return : 0 --满
56 -1 --没满
57 *****************************************/
58 int IsFullArrayStack(PArrayStack pStack);
59
60
61 /****************************************
62 Purpose : 入栈
63 Input : pStack --栈指针
64 pVal --数据指针
65 Return : 0 --OK
66 -1 --Fail
67 *****************************************/
68 int PushArrayStack(PArrayStack pStack, PCElemType pVal);
69
70
71
72 /****************************************
73 Purpose : 出栈
74 Input : pStack --栈指针
75 pVal --数据指针
76 Return : 0 --OK
77 -1 --Fail
78 *****************************************/
79 int PopArrayStack(PArrayStack pStack, PElemType pVal);
80
81
82
83 /****************************************
84 Purpose : 取栈顶数据
85 Input : pStack --栈指针
86 pVal --数据指针
87 Return : 0 --OK
88 -1 --Fail
89 *****************************************/
90 int GetTopArrayStack(PArrayStack pStack, PElemType pVal);
91
92
93
94 /****************************************
95 Purpose : 销毁栈
96 Input : pStack --栈指针
97 Return : 0 --OK
98 -1 --Fail
99 *****************************************/
100 int DestroyArrayStack(PArrayStack pStack);
101
102 #endif

#include
#include
#include <string.h>
#include "ArrayStack.h"/*************************************************************************Function: InitArrayStack()Purpose : 初始化数组栈Input : pStack -- 栈指针nMaxSize -- 栈容量Return : 0 --OK-1 --FAILModify :Remark :*************************************************************************/
int InitArrayStack(PArrayStack pStack, int nMaxSize)
{pStack->pArray &＃61; (PElemType)malloc((nMaxSize&＃43;1) * sizeof(ElemType));if(pStack->pArray &＃61;&＃61; NULL){/*申请内存空间失败*/return -1;}pStack->nMaxSize &＃61; nMaxSize;pStack->nTop &＃61; 0;
}/*************************************************************************Function: IsEmptyArrayStack()Purpose : 判断栈是否为空Input : pStack -- 栈指针Return : 0 --空-1 --非空Modify :Remark :
**************************************************************************/
int IsEmptyArrayStack(PArrayStack pStack)
{if(pStack->nTop &＃61;&＃61; 0){return 0;}return -1;
}/*************************************************************************Function: IsFullArrayStack()Purpose : 判断栈是否已满Input : pStack -- 栈指针Return : 0 --满-1 --没满Modify :Remark :
**************************************************************************/
int IsFullArrayStack(PArrayStack pStack)
{if(pStack->nTop &＃61;&＃61; pStack->nMaxSize){return 0;}return -1;
}/*************************************************************************Function: AgainMallocArrayStack()Purpose : 空间扩展为原来的2倍&＃xff0c;原内容被自动拷贝到pStack所指向的存储空间中Input : pStack --栈指针Return : NoneModify :Remark :*************************************************************************/
int AgainMallocArrayStack(PArrayStack pStack)
{int i;PElemType pTempData;pTempData &＃61; realloc(pStack->pArray, 2*pStack->nMaxSize*sizeof(ElemType));if(!pTempData){/*动态存储空间分配失败*/return -1;}/*指向新的队列空间*/pStack->pArray &＃61; pTempData;pStack->nMaxSize &＃61; 2 * pStack->nMaxSize;return 0;
}/*************************************************************************Function: PushArrayStack()Purpose : 入栈Input : pStack --栈指针pVal --数据指针Return : 0 --OK-1 --FailModify :Remark :
**************************************************************************/
int PushArrayStack(PArrayStack pStack, PCElemType pVal)
{if(IsFullArrayStack(pStack) &＃61;&＃61; 0){/*栈满*/if(AgainMallocArrayStack(pStack)){return -1;}}pStack->nTop &＃43;&＃61; 1;memcpy(&pStack->pArray[pStack->nTop], pVal, sizeof(ElemType));return 0;
}/*************************************************************************Function: PopArrayStack()Purpose : 出栈Input : pStack --栈指针pVal --数据指针Return : 0 --OK-1 --FailModify :Remark :
**************************************************************************/
int PopArrayStack(PArrayStack pStack, PElemType pVal)
{if(IsEmptyArrayStack(pStack) &＃61;&＃61; 0){/*栈空*/return -1;}memcpy(pVal, &pStack->pArray[pStack->nTop], sizeof(ElemType));memset(&pStack->pArray[pStack->nTop], 0, sizeof(ElemType));pStack->nTop -&＃61; 1;return 0;
}/*************************************************************************Function: GetTopArrayStack()Purpose : 取栈顶数据Input : pStack --栈指针pVal --数据指针Return : 0 --OK-1 --FailModify :Remark :
**************************************************************************/
int GetTopArrayStack(PArrayStack pStack, PElemType pVal)
{if(IsEmptyArrayStack(pStack) &＃61;&＃61; 0){/*栈空*/return -1;}memcpy(pVal, &pStack->pArray[pStack->nTop], sizeof(ElemType));return 0;
}/*************************************************************************Function: DestroyArrayStack()Purpose : 销毁栈Input : pStack --栈指针Return : 0 --OK-1 --FailModify :Remark :
**************************************************************************/
int DestroyArrayStack(PArrayStack pStack)
{if(pStack->pArray !&＃61; NULL){free(pStack->pArray);pStack->nTop &＃61; 0;}return 0;
}

#ifndef _ELEMTYPE_H_
#define _ELEMTYPE_H_/*定义需要的数据类型&＃xff0c;这里可以是基本数据类型&＃xff0c;也可以是结构体数据类型&＃xff0c;结构体中最好不要使用指针&＃xff0c;使用结构体时请包含相关头文件*/
typedef int ElemType;
typedef ElemType* PElemType;
typedef const ElemType* PCElemType;/****************************************Purpose : 打印数据Input : pVal --要被打印的数据Return : None
*****************************************/void visit(PCElemType pVal);#endif

#include
#include "ElemType.h"
/*************************************************************************Purpose : 打印输出数据Input : pVal --要被打印的数据Return : NoneModify :Remark :*************************************************************************/void visit(PCElemType pVal){printf("%d\n",*pVal);}

1 #include
2 #include "ArrayStack.h"
3
4 int main()
5 {
6 ElemType arr[7]&＃61;{2,5,3,1,4,8,10};
7 ArrayStack mStack;
8 int i;
9 ElemType outData;
10
11 InitArrayStack(&mStack, 4);
12 for(i&＃61;0;i<7;i&＃43;&＃43;)
13 {
14 if(PushArrayStack(&mStack, &arr[i]))
15 {
16 printf("push stack fail\n");
17 }
18 }
19
20 if(PopArrayStack(&mStack, &outData))
21 {
22 printf("pop stack fail\n");
23 }
24 visit(&outData);
25
26
27 int a1 &＃61; 80;
28 if(PushArrayStack(&mStack, &a1))
29 {
30 printf("push stack fail\n");
31 }
32
33
34 if(GetTopArrayStack(&mStack, &outData))
35 {
36 printf("getTop stack fail\n");
37 }
38 visit(&outData);
39
40
41 while(IsEmptyArrayStack(&mStack))
42 {
43 if(PopArrayStack(&mStack, &outData))
44 {
45 printf("pop stack fail\n");
46 }
47 visit(&outData);
48 }
49
50 DestroyArrayStack(&mStack);
51
52 return 0;
53 }