数据结构 - 栈的实现和应用
程序员文章站
2023-12-23 09:19:10
1、采用书上第 46 页定义的栈的顺序存储表示,编程实现栈的下列基本操作。(1)初始化顺序栈 (2)创建顺序栈 (3)判断栈空 (4)输出顺序栈(5)取栈顶元素 (6)入栈 (7)出栈2、采用栈的顺序存储表示,编程实现表达式中圆括号“( )”和方括号“[ ]”匹配的检验。4.1#include #include #include #include #define TRU...
1、采用书上第 46 页定义的栈的顺序存储表示,编程实现栈的下列基本操作。
(1)初始化顺序栈 (2)创建顺序栈 (3)判断栈空 (4)输出顺序栈
(5)取栈顶元素 (6)入栈 (7)出栈
2、采用栈的顺序存储表示,编程实现表达式中圆括号“( )”和方括号“[ ]”匹配的检验。
4.1
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
Status InitStack(SqStack &S) {
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S) {
if(S.top == S.base)
return TRUE;
else
return FALSE;
}
Status GetTop(SqStack S, SElemType &e) {
if(S.top == S.base)
return ERROR;
e = *(S.top - 1);
return OK;
}
Status Push(SqStack &S, SElemType e) {
if(S.top-S.base >= S.stacksize) {
S.base=(SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack &S, SElemType &e) {
if(S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}
Status Stackoutput(SqStack &S){
SElemType *p;
if(S.top == S.base) return ERROR;
p = S.top;
while(p!=S.base-1){
printf("%d-",*p--);
}
printf("\n");
return OK;
}
Status StackTraverse(SqStack S) {
SElemType *p;
if(S.top == S.base) return ERROR;
p = S.base;
while(p!=S.top){
printf("%d-",*p++);
}
printf("\n");
return OK;
}
int main() {
int i,n,k,h,a,b;
SqStack S;
printf("创建一个空栈!\n");
InitStack(S);
printf("判断栈是否为空!\n");
printf("StackEmpty(S) = %d\n",StackEmpty(S));
printf("创建栈的元素个数: \n");
scanf("%d",&n);
printf("输入%d个入栈元素的值: \n",n);
while(n--) {
scanf("%d",&k);
Push(S,k);
}
printf("逆序输出顺序栈元素值: \n");
StackTraverse(S);
Pop(S,a);
printf("输出第1个出栈元素值: %d\n",a);
Pop(S,a);
printf("输出第2个出栈元素值: %d\n",a);
printf("输出两次出栈后顺序栈元素值: ");
StackTraverse(S);
GetTop(S,b);
printf("输出栈顶元素值: %d\n",b);
}
4.2
#include<bits/stdc++.h>
#define TLE ios::sync_with_stdio(0),cin.tie(0)
#define long long ll
using namespace std;
typedef char st;
struct SqStack{
st *base;
st *top;
int stacksize;
};
void InitStack(SqStack &S) {
S.base = (st*)malloc(105* sizeof(st));
if(!S.base) exit (0);
S.top = S.base;
S.stacksize = 105;
}
bool Correct(st s[]){
int l = strlen(s);
SqStack S; InitStack(S);
for(int i = 0; i < l; i++){
if(s[i] == '(' || s[i] == '[') {
*++S.top = s[i];
}
else if(s[i] == ')' && *S.top == '(' && S.top!=S.base) {
free(S.top);
S.top--;
}
else if(s[i] == ']' && *S.top == '[' && S.top!=S.base) {
free(S.top);
S.top--;
}
}
if(S.top == S.base) {
free(S.base);
return 1;
}
else {
free(S.base);
return 0;
}
}
int main(){
st s[105];
printf("请输入带括号的表达式: \n");
scanf("%s",s);
if(Correct(s)) printf("括号匹配正确!\n");
else printf("括号匹配不正确!\n");
}
本文地址:https://blog.csdn.net/weixin_45919985/article/details/110286325