文章目录[隐藏]
自己写的链式栈
|
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 |
#include<bits/stdc++.h> using namespace std; //自己写的链式栈 //要实现的操作有： 初始化栈initstack ， 销毁栈destroystack ， 判断栈空emptystack // 取栈顶元素 gettop 进栈pushstack ， 出栈popstack , 打印栈元素printstack typedef struct linknode{ int data; struct linknode *next; }sqstack; void initstack(sqstack*&st){ st=(sqstack*)malloc(sizeof(sqstack)); st->next=NULL; } void destroystack(sqstack*&st){ sqstack *pre=st,*p=st->next; while(p){ free(pre); pre=p; p=pre->next; } free(pre); } bool emptystack(sqstack*st){ return(st->next==NULL); } int gettop(sqstack*st){//栈空的时候请不要用这个函数 return st->next->data; } void pushstack(sqstack*&st,int e){ sqstack*p; p=(sqstack*)malloc(sizeof(sqstack)); p->data=e; p->next=st->next; st->next=p; } bool popstack(sqstack*&st){ if(st->next==NULL) return false; // st->next=st->next->next; // free(st->next); // return true; sqstack *p; p=st->next; //p指向首结点 st->next=p->next;//删除首结点 free(p); return true; } void printstack(sqstack*st){ st=st->next;//栈的头结点是没有数据的 while(st){ cout<<st->data<<" "; st=st->next; } } int main(){ sqstack *st; initstack(st); for(int i=1;i<=10;i++) pushstack(st,i); popstack(st); printstack(st); int bl=emptystack(st); cout<<bl; } |
标准栈结构（链式）
|
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 |
//链栈基本运算算法 #include <stdio.h> #include <malloc.h> typedef char ElemType; typedef struct linknode { ElemType data; //数据域 struct linknode *next; //指针域 } LinkStNode; //链栈类型 void InitStack(LinkStNode *&s) { s=(LinkStNode *)malloc(sizeof(LinkStNode)); s->next=NULL; } void DestroyStack(LinkStNode *&s) { LinkStNode *p=s->next; while (p!=NULL) { free(s); s=p; p=p->next; } free(s); //s指向尾结点,释放其空间 } bool StackEmpty(LinkStNode *s) { return(s->next==NULL); } void Push(LinkStNode *&s,ElemType e) { LinkStNode *p; p=(LinkStNode *)malloc(sizeof(LinkStNode)); p->data=e; //新建元素e对应的结点p p->next=s->next; //插入p结点作为开始结点 s->next=p; } bool Pop(LinkStNode *&s,ElemType &e) { LinkStNode *p; if (s->next==NULL) //栈空的情况 return false; p=s->next; //p指向开始结点 e=p->data; s->next=p->next; //删除p结点 free(p); //释放p结点 return true; } bool GetTop(LinkStNode *s,ElemType &e) { if (s->next==NULL) //栈空的情况 return false; e=s->next->data; return true; } |
括号配对
例子3-5：设计一个算法判断输入的表达式中括号是否配对（假设只有左右，圆括号）
思路很明确，题目只设计圆括号，我觉得还可以加上方括号和❀括号，遇到左括号就进栈，遇到右括号就判断栈顶元素是否和它匹配，匹配就出栈，
这里我用自己写的栈代码来写，顺便看看自己写的栈有没有错误
|
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
//自己写的链式栈 //要实现的操作有： 初始化栈initstack ， 销毁栈destroystack ， 判断栈空emptystack // 取栈顶元素 gettop 进栈pushstack ， 出栈popstack , 打印栈元素printstack #include<bits/stdc++.h> using namespace std; typedef struct linknode{ char data; struct linknode *next; }sqstack; void initstack(sqstack*&st){ st=(sqstack*)malloc(sizeof(sqstack)); st->next=NULL; } void destroystack(sqstack*&st){ sqstack *pre=st,*p=st->next; while(p){ free(pre); pre=p; p=pre->next; } free(pre); } bool emptystack(sqstack*st){ return(st->next==NULL); } char gettop(sqstack*st){//栈空的时候请不要用这个函数 return st->next->data; } void pushstack(sqstack*&st,char e){ sqstack*p; p=(sqstack*)malloc(sizeof(sqstack)); p->data=e; p->next=st->next; st->next=p; } bool popstack(sqstack*&st){ if(st->next==NULL) return false; // st->next=st->next->next; // free(st->next); // return true; sqstack *p; p=st->next; //p指向首结点 st->next=p->next;//删除首结点 free(p); return true; } void printstack(sqstack*st){ st=st->next;//栈的头结点是没有数据的 while(st){ cout<<st->data<<" "; st=st->next; } } int main(){ string s; cin>>s; sqstack *st; char ss; int bl=1; initstack(st); for(int i=0;i<s.length();i++){ if(s[i]=='('||s[i]=='['||s[i]=='{') pushstack(st,s[i]); if(s[i]==')'){ if(emptystack(st)){ bl=0; break; } ss=gettop(st); if(ss=='(') popstack(st); else{ bl=0; break; } } if(s[i]==']'){ if(emptystack(st)){ bl=0; break; } ss=gettop(st); if(ss=='[') popstack(st); else{ bl=0; break; } } if(s[i]=='}'){ if(emptystack(st)){ bl=0; break; } ss=gettop(st); if(ss=='{') popstack(st); else{ bl=0; break; } } } if(!emptystack(st)) bl=0; if(bl) cout<<"true"<<endl; else cout<<"false"<<endl; } |
标准答案（只判断了圆括号
|
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 |
//【例3.5】的算法：判断表达式中的括号是否配对 #include "listack.cpp" #include <string.h> bool Match(char exp[],int n) { int i=0; char e; bool match=true; LinkStNode *st; InitStack(st); //初始化栈 while (i<n && match) //扫描exp中所有字符 { if (exp[i]=='(') //当前字符为左括号,将其进栈 Push(st,exp[i]); else if (exp[i]==')') //当前字符为右括号 { if (GetTop(st,e)==true) { if (e!='(') //栈顶元素不为'('时表示不匹配 match=false; else Pop(st,e); //将栈顶元素出栈 } else match=false; //无法取栈顶元素时表示不匹配 } i++; //继续处理其他字符 } if (!StackEmpty(st)) //栈不空时表示不匹配 match=false; DestroyStack(st); //销毁栈 return match; } int main() { char exp[]="(1+2*(5+3)/2)"; if (Match(exp,strlen(exp))==1) printf("表达式%s括号配对\n",exp); else printf("表达式%s括号不配对\n",exp); return 1; } |
