链表实现栈的动态顺序存储实现—C语言

1
/***
2
*DynaSeqStack.h - 动态顺序栈的定义
3
*
4
****/
5

6
#if !defined(DYNASEQSTACK_H)
7
#define DYNASEQSTACK_H
8

9
#include "ElemType.h"
10

11
/*------------------------------------------------------------
12
// 栈结构的定义
13
------------------------------------------------------------*/
14
typedef struct Stack
15
{
16
  ElemType *base;        // 栈基址
17
  ElemType *top;        // 栈顶
18
  int stacksize;        // 栈存储空间的尺寸
19
} SqStack;
20

21
/*------------------------------------------------------------
22
// 栈的基本操作
23
------------------------------------------------------------*/
24

25
bool InitStack(SqStack *S);
26
void DestroyStack(SqStack *S);
27
bool StackEmpty(SqStack S);
28
int  StackLength(SqStack S);
29
bool GetTop(SqStack S, ElemType *e);
30
void StackTraverse(SqStack S, void (*fp)(ElemType));
31
bool Push(SqStack *S, ElemType e);
32
bool Pop(SqStack *S, ElemType *e);
33

34
#endif /* DYNASEQSTACK_H */

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include "DynaSeqStack.h"
4

5
const int STACK_INIT_SIZE = 100;   // 初始分配的长度
6
const int STACKINCREMENT  = 10;    // 分配内存的增量
7

8

9
int main()
10
{
11
  SqStack S;
12

13
    InitStack(&S);
14
  Push(&S,12);
15
  system("pause");
16
  return 0;
17
}

1
/***
2
*ElemType.cpp - ElemType的实现
3
*
4
****/
5

6
#include <stdio.h>
7
#include "ElemType.h"
8

9
int compare(ElemType x, ElemType y)
10
{
11
  return(x-y);
12
}
13

14
void visit(ElemType e)
15
{
16
  printf("%dn", e);
17
}

1
/***
2
*DynaSeqStack.cpp - 动态顺序栈，即栈的动态顺序存储实现
3
*
4
*
5
*题目：实验3-1 栈的动态顺序存储实现
6
*
7
*
8
*
9
*
10
****/
11

12
#include <stdlib.h>
13
#include <malloc.h>
14
#include <memory.h>
15
#include <assert.h>
16
#include "DynaSeqStack.h"
17

18
const int STACK_INIT_SIZE = 100;  // 初始分配的长度
19
const int STACKINCREMENT  = 10;    // 分配内存的增量
20

21
/*------------------------------------------------------------
22
操作目的：  初始化栈
23
初始条件：  无
24
操作结果：  构造一个空的栈
25
函数参数：
26
    SqStack *S  待初始化的栈
27
返回值：
28
    bool    操作是否成功
29
------------------------------------------------------------*/
30
bool InitStack(SqStack *S)
31
{
32
     S->base = S->top = (ElemType *)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
33
   if (!S->base)
34
   {
35
     return false;
36
   }
37
  S->stacksize = STACK_INIT_SIZE;
38
  return true;
39
}
40

41
/*------------------------------------------------------------
42
操作目的：  销毁栈
43
初始条件：  栈S已存在
44
操作结果：  销毁栈S
45
函数参数：
46
    SqStack *S  待销毁的栈
47
返回值：
48
    无
49
------------------------------------------------------------*/
50
void DestroyStack(SqStack *S)
51
{
52
  free(S->base);
53
  S->top = S->base = NULL;
54
}
55

56
/*------------------------------------------------------------
57
操作目的：  判断栈是否为空
58
初始条件：  栈S已存在
59
操作结果：  若S为空栈，则返回true，否则返回false
60
函数参数：
61
    SqStack S  待判断的栈
62
返回值：
63
    bool    是否为空
64
------------------------------------------------------------*/
65
bool StackEmpty(SqStack S)
66
{
67
  if (S.base == S.top)
68
  {
69
        return true;
70
  }
71
  return false;
72
}
73

74
/*------------------------------------------------------------
75
操作目的：  得到栈的长度
76
初始条件：  栈S已存在
77
操作结果：  返回S中数据元素的个数
78
函数参数：
79
    SqStack S  栈S
80
返回值：
81
    int      数据元素的个数
82
------------------------------------------------------------*/
83
int StackLength(SqStack S)
84
{
85

86
  return (S.top - S.base);
87
;
88
}
89

90
/*------------------------------------------------------------
91
操作目的：  得到栈顶元素
92
初始条件：  栈S已存在
93
操作结果：  用e返回栈顶元素
94
函数参数：
95
    SqStack S  栈S
96
    ElemType *e  栈顶元素的值
97
返回值：
98
    bool    操作是否成功
99
------------------------------------------------------------*/
100
bool GetTop(SqStack S, ElemType *e)
101
{
102
  if (!S.base)
103
  {
104
    *e = *(S.top-1);
105
    return true;
106
  }
107
  return false;
108
}
109

110
/*------------------------------------------------------------
111
操作目的：  遍历栈
112
初始条件：  栈S已存在
113
操作结果：  依次对S的每个元素调用函数fp
114
函数参数：
115
    SqStack S    栈S
116
    void (*fp)()  访问每个数据元素的函数指针
117
返回值：
118
    无
119
------------------------------------------------------------*/
120
void StackTraverse(SqStack S, void (*fp)(ElemType))
121
{
122
  for (;S.base<S.top;S.base++)
123
  {
124
    fp(*S.base);
125

126
  }
127
}
128

129
/*------------------------------------------------------------
130
操作目的：  压栈——插入元素e为新的栈顶元素
131
初始条件：  栈S已存在
132
操作结果：  插入数据元素e作为新的栈顶
133
函数参数：
134
    SqStack *S  栈S
135
    ElemType e  待插入的数据元素
136
返回值：
137
    bool    操作是否成功
138
------------------------------------------------------------*/
139
bool Push(SqStack *S, ElemType e)
140
{
141
  if ((S->top - S->base)==S->stacksize)
142
  {
143
    //1.分配大一点的空间
144
    ElemType *newbase = (ElemType*)malloc(sizeof(ElemType)*(S->stacksize+STACKINCREMENT));
145
    if (!newbase)
146
    {
147
      return false;
148
    }
149
    //2.复制元素到新的空间
150
    memcpy(newbase,S->base,sizeof(ElemType)*S->stacksize);
151
    //3.销毁原储存空间
152
    free(S->base);
153

154
    //4.栈顶指针、栈顶指针
155
    S->base = newbase;
156
    S->top = S->base+S->stacksize;
157
    S->stacksize = S->stacksize+STACKINCREMENT;
158

159
  }
160
  *(S->top) = e;
161
  S->top++;
162
  return true;
163
}
164

165
/*------------------------------------------------------------
166
操作目的：  弹栈——删除栈顶元素
167
初始条件：  栈S已存在且非空
168
操作结果：  删除S的栈顶元素，并用e返回其值
169
函数参数：
170
    SqStack *S  栈S
171
    ElemType *e  被删除的数据元素值
172
返回值：
173
    bool    操作是否成功
174
------------------------------------------------------------*/
175
bool Pop(SqStack *S, ElemType *e)
176
{
177
  *e = *(--S->top);
178
  return true;
179
}