/***
*ElemType.h - ElemType的定义
*
****/
#ifndef ELEMTYPE_H
#define ELEMTYPE_H
typedef int ElemType;
int compare(ElemType x, ElemType y);
void visit(ElemType e);
#endif /* ELEMTYPE_H */
/***
*DynaSeqStack.h - 动态顺序栈的定义
*
****/
#if !defined(DYNASEQSTACK_H)
#define DYNASEQSTACK_H
#include "ElemType.h"
/*------------------------------------------------------------
// 栈结构的定义
------------------------------------------------------------*/
typedef struct Stack
{
ElemType *base; // 栈基址
ElemType *top; // 栈顶
int stacksize; // 栈存储空间的尺寸
} SqStack;
/*------------------------------------------------------------
// 栈的基本操作
------------------------------------------------------------*/
bool InitStack(SqStack *S);
void DestroyStack(SqStack *S);
bool StackEmpty(SqStack S);
int StackLength(SqStack S);
bool GetTop(SqStack S, ElemType *e);
void StackTraverse(SqStack S, void (*fp)(ElemType));
bool Push(SqStack *S, ElemType e);
bool Pop(SqStack *S, ElemType *e);
#endif /* DYNASEQSTACK_H */
#include <stdio.h>
#include <stdlib.h>
#include "DynaSeqStack.h"
const int STACK_INIT_SIZE = 100; // 初始分配的长度
const int STACKINCREMENT = 10; // 分配内存的增量
int main()
{
SqStack S;
InitStack(&S);
Push(&S,12);
system("pause");
return 0;
}
/***
*ElemType.cpp - ElemType的实现
*
****/
#include <stdio.h>
#include "ElemType.h"
int compare(ElemType x, ElemType y)
{
return(x-y);
}
void visit(ElemType e)
{
printf("%dn", e);
}
/***
*DynaSeqStack.cpp - 动态顺序栈,即栈的动态顺序存储实现
*
*
*题目:实验3-1 栈的动态顺序存储实现
*
*
*
*
****/
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaSeqStack.h"
const int STACK_INIT_SIZE = 100; // 初始分配的长度
const int STACKINCREMENT = 10; // 分配内存的增量
/*------------------------------------------------------------
操作目的: 初始化栈
初始条件: 无
操作结果: 构造一个空的栈
函数参数:
SqStack *S 待初始化的栈
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool InitStack(SqStack *S)
{
S->base = S->top = (ElemType *)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
if (!S->base)
{
return false;
}
S->stacksize = STACK_INIT_SIZE;
return true;
}
/*------------------------------------------------------------
操作目的: 销毁栈
初始条件: 栈S已存在
操作结果: 销毁栈S
函数参数:
SqStack *S 待销毁的栈
返回值:
无
------------------------------------------------------------*/
void DestroyStack(SqStack *S)
{
free(S->base);
S->top = S->base = NULL;
}
/*------------------------------------------------------------
操作目的: 判断栈是否为空
初始条件: 栈S已存在
操作结果: 若S为空栈,则返回true,否则返回false
函数参数:
SqStack S 待判断的栈
返回值:
bool 是否为空
------------------------------------------------------------*/
bool StackEmpty(SqStack S)
{
if (S.base == S.top)
{
return true;
}
return false;
}
/*------------------------------------------------------------
操作目的: 得到栈的长度
初始条件: 栈S已存在
操作结果: 返回S中数据元素的个数
函数参数:
SqStack S 栈S
返回值:
int 数据元素的个数
------------------------------------------------------------*/
int StackLength(SqStack S)
{
return (S.top - S.base);
;
}
/*------------------------------------------------------------
操作目的: 得到栈顶元素
初始条件: 栈S已存在
操作结果: 用e返回栈顶元素
函数参数:
SqStack S 栈S
ElemType *e 栈顶元素的值
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool GetTop(SqStack S, ElemType *e)
{
if (!S.base)
{
*e = *(S.top-1);
return true;
}
return false;
}
/*------------------------------------------------------------
操作目的: 遍历栈
初始条件: 栈S已存在
操作结果: 依次对S的每个元素调用函数fp
函数参数:
SqStack S 栈S
void (*fp)() 访问每个数据元素的函数指针
返回值:
无
------------------------------------------------------------*/
void StackTraverse(SqStack S, void (*fp)(ElemType))
{
for (;S.base<S.top;S.base++)
{
fp(*S.base);
}
}
/*------------------------------------------------------------
操作目的: 压栈——插入元素e为新的栈顶元素
初始条件: 栈S已存在
操作结果: 插入数据元素e作为新的栈顶
函数参数:
SqStack *S 栈S
ElemType e 待插入的数据元素
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool Push(SqStack *S, ElemType e)
{
if ((S->top - S->base)==S->stacksize)
{
//1.分配大一点的空间
ElemType *newbase = (ElemType*)malloc(sizeof(ElemType)*(S->stacksize+STACKINCREMENT));
if (!newbase)
{
return false;
}
//2.复制元素到新的空间
memcpy(newbase,S->base,sizeof(ElemType)*S->stacksize);
//3.销毁原储存空间
free(S->base);
//4.栈顶指针、栈顶指针
S->base = newbase;
S->top = S->base+S->stacksize;
S->stacksize = S->stacksize+STACKINCREMENT;
}
*(S->top) = e;
S->top++;
return true;
}
/*------------------------------------------------------------
操作目的: 弹栈——删除栈顶元素
初始条件: 栈S已存在且非空
操作结果: 删除S的栈顶元素,并用e返回其值
函数参数:
SqStack *S 栈S
ElemType *e 被删除的数据元素值
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool Pop(SqStack *S, ElemType *e)
{
*e = *(--S->top);
return true;
}