赞
踩
目录
定义:栈(Stack)是一个特殊的线性表,是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。
又称后进先出(Last In First Out)的线性表,简称LIFO结构。
逻辑结构:与线性表相同,仍为一对一关系。
存储结构:用顺序栈和链栈存储均可,但以顺序栈更常见。
运算规则:只能在栈顶运算,且访问节点时仍依照后进先出的原则。
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #define MaxSize 100
- #define Ok 1
- #define Error 0
- #define OverFlow -2
- using namespace std;
-
- typedef int Status;
- typedef int SElemType;
- typedef struct{
- SElemType *top; //栈顶指针
- SElemType *base; //栈底指针
- int stacksize; //栈可用最大容量
- }SqStack;
- SqStack S,T;
- //初始化
- Status InitStack(SqStack &S){
- S.base = (SElemType*)malloc(sizeof(SElemType) * MaxSize);
- if(!S.base)
- exit(OverFlow); //存储分配失败
- S.top = S.base; //栈顶指针等于栈底指针
- S.stacksize = MaxSize;
- return Ok;
- }
- //判断栈是否为空
- Status StackEmpty(SqStack S){
- if(S.top == S.base)
- return Ok;
- else
- return Error;
- }
- //求顺序栈的长度
- int StackLength(SqStack S){
- return S.top - S.base;
- }
- //清空顺序栈
- Status ClearStack(SqStack &S){
- if(S.base)
- S.top = S.base;
- return Ok;
- }
- //销毁顺序栈
- Status DestroyStack(SqStack &S){
- if(S.base){
- delete S.base; //释放内存
- S.stacksize = 0; //清空栈容量
- S.base = S.top = NULL; //指针指向空
- }
- return Ok;
- }
- //顺序栈的入栈
- Status Push(SqStack &S,SElemType e)
- {
- if(S.top - S.base >= S.stacksize) //栈满,扩容
- {
- S.base = (SElemType *)realloc(S.base,(S.stacksize * 2)*sizeof(SElemType));
- if(!S.base)
- exit(OverFlow);
- S.top = S.base + S.stacksize;
- S.stacksize *= 2;
- }
- *S.top++ = e;
- return Ok;
- }
- //顺序栈的出栈
- Status Pop(SqStack &S,SElemType &e){
- if(S.top == S.base)
- return Error;
- e = *--S.top;
- return Ok;
- }
- //取栈顶元素
- Status GetTop(SqStack S,SElemType &e)
- {
- if(S.top==S.base) //栈为空
- return Error;
- e = *(S.top-1);
- return Ok;
- }
- //输出顺序栈中的元素
- Status Print(SqStack S){
- SElemType *p = S.top;
- while(p != S.base)
- cout<< *--p << " ";
- cout<<endl;
- return Ok;
- }
- //进制转换
- Status Num(SqStack &S,int e,int num){
- while(e){
- Push(S,e % num);
- e /= num;
- }
- }
-
- //输出转换后的元素
- Status NumStack(SqStack &S){
- SElemType *p = S.top;
- while(!StackEmpty(T)){
- int ans;
- Pop(T,ans);
- if(ans < 10)
- cout<< ans;
- else{
- char c;
- c = ans - 10 + 'A';
- cout<< c;
- }
- }
- cout<<endl;
- }
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #define MaxSize 100
- #define Ok 1
- #define Error 0
- #define OverFlow -2
- using namespace std;
-
- typedef int Status;
- typedef int SElemType;
- typedef struct{
- SElemType *top; //栈顶指针
- SElemType *base; //栈底指针
- int stacksize; //栈可用最大容量
- }SqStack;
- SqStack S,T;
-
- //初始化
- Status InitStack(SqStack &S){
- S.base = (SElemType*)malloc(sizeof(SElemType) * MaxSize);
- if(!S.base)
- exit(OverFlow); //存储分配失败
- S.top = S.base; //栈顶指针等于栈底指针
- S.stacksize = MaxSize;
- return Ok;
- }
-
- //判断栈是否为空
- Status StackEmpty(SqStack S){
- if(S.top == S.base)
- return Ok;
- else
- return Error;
- }
-
- //求顺序栈的长度
- int StackLength(SqStack S){
- return S.top - S.base;
- }
-
- //清空顺序栈
- Status ClearStack(SqStack &S){
- if(S.base)
- S.top = S.base;
- return Ok;
- }
-
- //销毁顺序栈
- Status DestroyStack(SqStack &S){
- if(S.base){
- delete S.base; //释放内存
- S.stacksize = 0; //清空栈容量
- S.base = S.top = NULL; //指针指向空
- }
- return Ok;
- }
-
- //顺序栈的入栈
- Status Push(SqStack &S,SElemType e)
- {
- if(S.top - S.base >= S.stacksize) //栈满,扩容
- {
- S.base = (SElemType *)realloc(S.base,(S.stacksize * 2)*sizeof(SElemType));
- if(!S.base)
- exit(OverFlow);
- S.top = S.base + S.stacksize;
- S.stacksize *= 2;
- }
- *S.top++ = e;
- return Ok;
- }
-
- //顺序栈的出栈
- Status Pop(SqStack &S,SElemType &e){
- if(S.top == S.base)
- return Error;
- e = *--S.top;
- return Ok;
- }
-
- //取栈顶元素
- Status GetTop(SqStack S,SElemType &e)
- {
- if(S.top==S.base) //栈为空
- return Error;
- e = *(S.top-1);
- return Ok;
- }
-
- //输出顺序栈中的元素
- Status Print(SqStack S){
- SElemType *p = S.top;
- while(p != S.base)
- cout<< *--p << " ";
- cout<<endl;
- return Ok;
- }
-
- //进制转换
- Status Num(SqStack &S,int e,int num){
- while(e){
- Push(S,e % num);
- e /= num;
- }
- }
-
- //输出转换后的数
- Status NumStack(SqStack &S){
- SElemType *p = S.top;
- while(!StackEmpty(T)){
- int ans;
- Pop(T,ans);
- if(ans < 10)
- cout<< ans;
- else{
- char c;
- c = ans - 10 + 'A';
- cout<< c;
- }
- }
- cout<<endl;
- }
-
-
- int main()
- {
- int order,init = 0,des = 0,len,e;
- cout<< "*--------------栈----------------*"<<endl;
- cout<< "*---------1.初始化栈-------------*"<<endl;
- cout<< "*---------2.销毁栈---------------*"<<endl;
- cout<< "*---------3.清空栈---------------*"<<endl;
- cout<< "*---------4.栈判空---------------*"<<endl;
- cout<< "*---------5.求栈长度-------------*"<<endl;
- cout<< "*---------6.获取栈顶元素---------*"<<endl;
- cout<< "*---------7.插入一个元素---------*"<<endl;
- cout<< "*---------8.删除一个元素---------*"<<endl;
- cout<< "*---------9.输出所有元素---------*"<<endl;
- cout<< "*---------10.进制转换------------*"<<endl;
- do{
- cout<< "请输入指令:";
- cin>> order;
- if(order == 0 || order > 10)
- cout<< "没有该指令" <<endl;
- else if(!init && order > 1 && order != 10)
- cout<< "请先初始化栈" <<endl;
- else if(des && order > 1 && order != 10)
- cout<< "栈已销毁,请先初始化" <<endl;
- else
- switch(order)
- {
- case 1:
- InitStack(S);
- init=1;
- des=0;
- cout<< "初始化完成!" <<endl;
- break;
- case 2:
- DestroyStack(S);
- des = 1;
- cout<< "栈已销毁" <<endl;
- break;
- case 3:
- ClearStack(S);
- cout<< "栈已清空" <<endl;
- break;
- case 4:
- if(!StackEmpty(S))
- cout<< "栈非空" <<endl;
- else
- cout<< "栈为空" <<endl;
- break;
- case 5:
- len=StackLength(S);
- cout<< "栈长度为:" << len <<endl;
- break;
- case 6:
- if(GetTop(S,e))
- cout<< "栈顶元素为:" << e <<endl;
- else
- cout<< "空栈,无栈顶元素" <<endl;
- break;
- case 7:
- cout<< "请输入插入元素:";
- cin>> e;
- Push(S,e);
- cout<< "入栈成功" <<endl;
- break;
- case 8:
- if(Pop(S,e))
- cout<< "栈顶元素" << e << "出栈成功" <<endl;
- else
- cout<< "栈为空" <<endl;
- break;
- case 9:
- cout<< "栈为:";
- Print(S);
- break;
- case 10:
- int num;
- cout<< "输入一个十进制数:";
- cin>> e;
- cout<< "输入要转换的进制:";
- cin>> num;
- InitStack(T);
- cout<< "10进制数" << e << "转换为" << num <<"进制数后为:";
- if(e < 0)
- {
- cout<< '-';
- e = -e;
- }
- if(!e)
- cout<< 0;
- Num(T,e,num);
- NumStack(T);
- break;
- default:
- cout<< "程序已退出" <<endl;
- break;
- }
- }while(order>=0);
- return Ok;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。