赞
踩
使用c++完成数据结构顺序栈的基本操作,包括(初始化、入栈、出栈、取栈顶元素、遍历输出栈等),可直接编译运行。
#define MAXSIZE 100
typedef int Status;
typedef int SElemType;
//顺序栈的存储结构
typedef struct {
SElemType * base; //栈底指针
SElemType * top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack;
【算法步骤】
① 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间,使base指向栈底。
② 栈顶指针top初始为base,表示栈为空。
③ stacksize置为栈的最大容量MAXSIZE。
【算法描述】
//顺序栈的初始化
Status InitStack(SqStack& S)
{
S.base = new SElemType[MAXSIZE]; //构造一个空栈S
if (!S.base)
return ERROR;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
【算法步骤】
① 判断栈是否满,若满则返回ERROR。
② 将新元素放入栈顶,栈顶指针加1。
【算法描述】
//顺序栈的入栈
Status Push(SqStack& S, SElemType e)
{ //插入元素e为新的栈顶元素
if (S.top - S.base == S.stacksize)
return ERROR;
*S.top++ = e;
return OK;
}
【算法步骤】
① 判断栈是否空,若空则返回ERROR。
② 栈顶指针减1,栈顶元素出栈。
【算法描述】
//顺序栈的出栈
Status Pop(SqStack& S, SElemType& e)
{ //删除S的栈顶元素,用e返回其值
if (S.base == S.top)
return ERROR;
e = *--S.top;
return OK;
}
【算法步骤】
① 判断栈是否空,若空则返回ERROR。
② 返回e获取栈顶元素的值。
【算法描述】
//取顺序栈的栈顶元素
Status GetTop(SqStack S, SElemType& e)
{ //返回S的栈顶元素,不修改栈顶指针
if (S.top == S.base)
return ERROR;
e = *(S.top - 1);
return OK;
}
【算法步骤】
① 判断栈是否空,若空则返回ERROR。
② 循环输出栈顶元素。
【算法描述】
//遍历输出顺序栈 Status StackTraverse(SqStack S) { SElemType* p; p = S.top; if (S.base == p) { cout << "顺序栈为空!" << endl; return ERROR; } cout << "栈顶->"; for (p--; p >= S.base; p--) cout << *p << " "; cout << endl; return OK; }
//顺序栈的基本操作.cpp #include <iostream> using namespace std; #define ERROR 0 #define OK 1 #define MAXSIZE 100 typedef int Status; typedef int SElemType; //顺序栈的存储结构 typedef struct { SElemType * base; //栈顶指针 SElemType* top; //栈底指针 int stacksize; //栈可用的最大容量 }SqStack; Status InitStack(SqStack&); //空栈 Status Push(SqStack&, SElemType); //入栈 Status Pop(SqStack&, SElemType&); //出栈 Status GetTop(SqStack, SElemType&); //读栈顶元素 Status StackTraverse(SqStack); //遍历 Status StackLength(SqStack); //栈的长度 int main() { SqStack S; int a; SElemType e; if (!InitStack(S)) cout << "顺序栈初始化失败!" << endl; else cout << "顺序栈初始化成功!" << endl; while (1) { cout << "\n【1】入栈 【2】出栈 【3】读栈顶元素 【4】输出栈 【0】退出" << endl; cout << "请选择要进行的操作:"; cin >> a; switch (a) { case 1: cout << "请输入入栈元素:"; cin >> e; if (!Push(S, e)) cout << "入栈失败!" << endl; else cout << "元素" << e << "入栈成功!" << endl; break; case 2: if (!Pop(S, e)) cout << "出栈失败!" << endl; else cout << "元素" << e << "出栈成功!" << endl; break; case 3: if (!GetTop(S, e)) cout << "读栈顶元素失败!" << endl; else cout << "栈顶元素为:" << e << endl; break; case 4: StackTraverse(S); break; case 0: return OK; default: return OK; } } } //顺序栈的初始化 Status InitStack(SqStack& S) { S.base = new SElemType[MAXSIZE]; //构造一个空栈S if (!S.base) return ERROR; S.top = S.base; S.stacksize = MAXSIZE; return OK; } //顺序栈的入栈 Status Push(SqStack& S, SElemType e) { //插入元素e为新的栈顶元素 if (S.top - S.base == S.stacksize) return ERROR; *S.top++ = e; return OK; } //顺序栈的出栈 Status Pop(SqStack& S, SElemType& e) { //删除S的栈顶元素,用e返回其值 if (S.base == S.top) return ERROR; e = *--S.top; return OK; } //取顺序栈的栈顶元素 Status GetTop(SqStack S, SElemType& e) { //返回S的栈顶元素,不修改栈顶指针 if (S.top == S.base) return ERROR; e = *(S.top - 1); return OK; } //遍历输出顺序栈 Status StackTraverse(SqStack S) { SElemType* p; p = S.top; if (S.base == p) { cout << "顺序栈为空!" << endl; return ERROR; } cout << "栈顶->"; for (p--; p >= S.base; p--) cout << *p << " "; cout << endl; return OK; }
美美地解决!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。