自己写的顺序栈
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<bits/stdc++.h> #define max 1000 using namespace std; typedef struct { int data[max]; int top; }sqstack; //要实现的操作有1 插入（insertstack） 2 删除一个元素（deletestack） 3 清空栈（destorystack） 4 初始化栈(initstack) //5 判断栈是否为空（isemptystack） 6将栈中元素全部打印（printstack）。。。目前就先写这几个操作吧 void initstack(sqstack *&s){ s=(sqstack*)malloc(sizeof(sqstack)); //先为栈分配一个空间把 s->top=0; } void insertstack(sqstack*&s,int x){ s->data[s->top]=x; s->top++; } void deletestack(sqstack*&s){ s->top--; } void destorystack(sqstack*&s){ free(s); } bool isemptystack(sqstack*s){ return s->top == 0; } void printstack(sqstack*s){ while(s->top--){ cout<<s->data[s->top]<<" "; } } int main(){ sqstack *s; initstack(s); insertstack(s,4); insertstack(s,6); insertstack(s,9); insertstack(s,2); insertstack(s,1); printstack(s); } |
教材上的顺序栈
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
//顺序栈基本运算算法 #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int top; //栈指针 } SqStack; //顺序栈类型 void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } void DestroyStack(SqStack *&s) { free(s); } bool StackEmpty(SqStack *s) { return(s->top==-1); } bool Push(SqStack *&s,ElemType e) { if (s->top==MaxSize-1) //栈满的情况，即栈上溢出 return false; s->top++; s->data[s->top]=e; return true; } bool Pop(SqStack *&s,ElemType &e) { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; s->top--; return true; } bool GetTop(SqStack *s,ElemType &e) { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; return true; } |
回文串的应用
例，设计一个算法利用顺序栈判断一个字符串是否为对称串。
比如这样一串字符abcba，是回文串，首先保存到一个数组中然后将其全部进栈，接着一个一个出栈来和数组中的字符判断是否一样。要用的函数有，进栈函数，取栈顶元素值函数，出栈函数，最后别忘了，还有一个判断栈为空的函数，这里我直接用教材的标准栈代码来写==
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
//顺序栈基本运算算法 #include<bits/stdc++.h> using namespace std; #define MaxSize 100 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int top; //栈指针 } SqStack; //顺序栈类型 void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } void DestroyStack(SqStack *&s) { free(s); } bool StackEmpty(SqStack *s) { return(s->top==-1); } bool Push(SqStack *&s,ElemType e) { if (s->top==MaxSize-1) //栈满的情况，即栈上溢出 return false; s->top++; s->data[s->top]=e; return true; } bool Pop(SqStack *&s,ElemType &e) { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; s->top--; return true; } bool GetTop(SqStack *s,ElemType &e) { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; return true; } int main(){ int n; cin>>n; while(n){ n--; SqStack *st; InitStack(st); string s; cin>>s; ElemType e; bool bl=1; for(int i=0;i<s.length();i++) Push(st,s[i]); for(int i=0;i<s.length();i++){ Pop(st,e); if(s[i]!=e){ DestroyStack(st); cout<<"false"<<endl; bl=0; break; } } if(bl){ cout<<"true"<<endl; DestroyStack(st); } } } |
标准答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//【例3.4】的算法：判断一个字符串是否是对称串 #include "sqstack.cpp" bool symmetry(ElemType str[]) { int i; ElemType e; SqStack *st; InitStack(st); //初始化栈 for (i=0;str[i]!='\0';i++) //将串所有元素进栈 Push(st,str[i]); //元素进栈 for (i=0;str[i]!='\0';i++) { Pop(st,e); //退栈元素e if (str[i]!=e) //若e与当前串元素不同则不是对称串 { DestroyStack(st); //销毁栈 return false; } } DestroyStack(st); //销毁栈 return true; } int main() { ElemType str[]="1234321"; if (symmetry(str)) printf("%s是对称串\n",str); else printf("%s不是对称串\n",str); return 1; } |
