主要操作函数如下:
- InitStack(SqStack &s) 参数:顺序栈s 功能:初始化 时间复杂度O(1)
- Push(SqStack &s,SElemType e) 参数:顺序栈s,元素e 功能:将e入栈 时间复杂度:O(1)
- Pop(SqStack &s,SElemType &e) 参数:顺序栈s,元素e 功能:出栈,e接收出栈元素值 时间复杂度O(1)
- GetTop(SqStack s,SElemType &e) 参数:顺序栈s,元素e 功能:得到栈顶元素 时间复杂度O(1)
-
注意:严蔚敏版没有判断栈空函数,在入栈、出栈函数里面判断栈是否空,与王道的不同 尤其是top指针在base之上(有元素时)另外,严蔚敏版 59页取栈顶有误
/*
Project: sequence_stack (数据结构-顺序栈)
Date: 2018/09/14
Author: Frank Yu
InitStack(SqStack &s) 参数:顺序栈s 功能:初始化 时间复杂度O(1)
Push(SqStack &s,SElemType e) 参数:顺序栈s,元素e 功能:将e入栈 时间复杂度:O(1)
Pop(SqStack &s,SElemType &e) 参数:顺序栈s,元素e 功能:出栈,e接收出栈元素值 时间复杂度O(1)
GetTop(SqStack s,SElemType &e) 参数:顺序栈s,元素e 功能:得到栈顶元素 时间复杂度O(1)
注意:严蔚敏版没有判断栈空函数,在入栈、出栈函数里面判断栈是否空,与王道的不同 尤其是top指针在base之上(有元素时)
另外,严蔚敏版 59页取栈顶有误
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define Status int
#define SElemType int
#define MaxSize 100
//栈数据结构
typedef struct Stack
{
SElemType *base;//栈底指针 不变
SElemType *top;//栈顶指针 一直在栈顶元素上一个位置
int stacksize;//栈可用的最大容量
}SqStack;
//**************************************基本操作函数************************************//
//初始化函数
Status InitStack(SqStack &s)
{
s.base=new SElemType[MaxSize];//动态分配最大容量
if(!s.base)
{
printf("分配失败\n");
return 0;
}
s.top=s.base;//栈顶指针与栈底相同 王道上top起初在base下面,感觉很别扭,top应该高于或等于base
s.stacksize=MaxSize;
return 1;
}
//入栈
Status Push(SqStack &s,SElemType e)
{
if(s.top-s.base==s.stacksize) return 0;//栈满
*(s.top++)=e;//先入栈,栈顶指针再上移 注意与王道上的不同,具体问题具体分析
return 1;
}
//出栈 用e返回值
Status Pop(SqStack &s,SElemType &e)
{
if(s.top==s.base) return 0;//栈空
e=*--s.top;//先减减 指向栈顶元素,再给e
return 1;
}
//得到栈顶元素,不修改指针
bool GetTop(SqStack s,SElemType &e) //严蔚敏版59页有问题,应该用e去获得,函数返回bool类型去判断
{
if(s.top==s.base) return false;//栈空
else e=*--s.top;
return true;
}
//********************************功能实现函数**************************************//
//菜单
void menu()
{
printf("********1.入栈 2.出栈*********\n");
printf("********3.取栈顶 4.退出*********\n");
}
//入栈功能函数 调用Push函数
void PushToStack(SqStack &s)
{
int n;SElemType e;int flag;
printf("请输入入栈元素个数(>=1):\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入第%d个元素的值:",i+1);
scanf("%d",&e);
flag=Push(s,e);
if(flag)printf("%d已入栈\n",e);
else {printf("栈已满!!!\n");break;}
}
}
//出栈功能函数 调用Pop函数
void PopFromStack(SqStack &s)
{
int n;SElemType e;int flag;
printf("请输入出栈元素个数(>=1):\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
flag=Pop(s,e);
if(flag)printf("%d已出栈\n",e);
else {printf("栈已空!!!\n");break;}
}
}
//取栈顶功能函数 调用GetTop
void GetTopOfStack(SqStack &s)
{
SElemType e;bool flag;
flag=GetTop(s,e);
if(flag)printf("栈顶元素为:%d\n",e);
else printf("栈已空!!!\n");
}
//主函数
int main()
{
SqStack s;int choice;
InitStack(s);
while(1)
{
menu();
printf("请输入菜单序号:\n");
scanf("%d",&choice);
if(choice==4) break;
switch(choice)
{
case 1:PushToStack(s);break;
case 2:PopFromStack(s);break;
case 3:GetTopOfStack(s);break;
default:printf("输入错误!!!\n");
}
}
return 0;
}
----------------------------------------回复lena512.bmp(20200427)------------------------------------
从图中可以看到地址及地址内存的数据。
------------------------------------------取栈顶的统一回复(20200920)-------------------------------------
传参有多种,可分为参数修改后对原变量进行修改和不修改。对于需要修改的,我们可以使用&或指针,对参数的修改会反应到原来的变量;对于不需要修改的,你可以继续使用&或指针,不做修改那很好,做了修改但是没有回溯(即忘记再反操作回原来的数值)那就不好了,为了防止自己忘记回溯,博主对于get、print等获取数据而不修改的函数使用传值方式,你可以去查看下方专栏的图相关内容,对于图的建立,传参是&G,而遍历则是G。
建议您先复制代码运行一下,没有问题再思考原理,出了问题再评论,好记性不如烂笔头,动手才是王道!
本人b站账号:lady_killer9
更多数据结构实现:数据结构严蔚敏版的实现(含全部代码)
有问题请下方评论,转载请注明出处,并附有原文链接,谢谢!如有侵权,请及时联系。如果您感觉有所收获,自愿打赏,可选择支付宝18833895206(小于),您的支持是我不断更新的动力。