徐州住房与建设局网站,多平台网站设计实例,中企动力的销售适合什么人,深圳建伟业公司商城实验五 栈
一、实验目的与要求
1#xff09;熟悉栈的类型定义和基本操作#xff1b;
2#xff09;灵活应用栈解决具体应用问题。
二、实验内容
1、判断回文数#xff0c;回文是指正读反读均相同的字符序列#xff0c;如“1221”和“12321”均是回文#xff0c;但“…实验五 栈
一、实验目的与要求
1熟悉栈的类型定义和基本操作
2灵活应用栈解决具体应用问题。
二、实验内容
1、判断回文数回文是指正读反读均相同的字符序列如“1221”和“12321”均是回文但“1234”不是回文。请写一个算法判定给定的字符向量是否为回文。(提示将一半字符入栈)
2、给定一个只包括 (){}[] 的字符串s 判断字符串是否有效。有效字符串需满足
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示列()和()[]{}都是合法的括号序列但( ]和( [ )]不合法。
3、在某程序中有两个栈共享一个一维数组空间SPACE[N]SPACE[0]、SPACE[N-1] 分别是两个栈的栈底。(扩展选作) 1对栈1、栈2试分别写出元素x入栈的主要语句和出栈的主要语句。 2对栈1、栈2试分别写出栈满、栈空的条件。
三、实验结果
1请将调试通过的源代码粘贴在下面。代码注意书写规范、主要模块要有功能注释
实验1代码
#include iostream
#include cstring
using namespace std;
typedef struct{char data[1000];int top;
}Stack;//初始化栈
void Init_stack(Stack *s){s-top-1;
}//元素入栈
void Push_stack(Stack *s,char x){s-tops-top1;s-data[s-top]x;
}//元素出栈
void Pop_stack(Stack *s,char *x){*xs-data[s-top];s-tops-top-1;
}int main(){char data[1000],x;int i;Stack s;//初始化测试栈 Init_stack(s);cindata;//输入的字符串长度 int lenstrlen(data);//输入的字符串入栈 for(i0;ilen;i){Push_stack(s,data[i]);}//首尾对比判断回文数 for(i0;ilen;i){Pop_stack(s,x);if(data[i]!x){cout不是回文数endl;return 0;}}cout是回文数endl;return 0;
}实验1结果展示 实验2代码
#include iostream
#include cstring
using namespace std;typedef struct{char data[1000];//元素 int top;//顶指针
}Stack;//初始化栈
void Init_stack(Stack *s){s-top-1;
}//元素入栈
void Push_stack(Stack *s,char *x){s-tops-top1;s-data[s-top]*x;
}//元素出栈
void Pop_stack(Stack *s,char *x){*xs-data[s-top];s-tops-top-1;
}int main(){char str[1000];Stack s;Init_stack(s);coutPlease input your string;cinstr;int lenstrlen(str),i0;//len为str的长度 //coutlen;//如果长度为奇数一定缺少括号 if(len%2!0){coutWrong string!endl;return 0;}//长度为偶数分类讨论 for(i0;ilen;i){//[]情况 if(str[i][){Push_stack(s,str[i]);if(str[i1]]){Pop_stack(s,str[i]);continue;}else{coutWrong string!endl;return 0;}}//()情况 if(str[i](){Push_stack(s,str[i]);if(str[i1])){Pop_stack(s,str[i]);continue;}else{coutWrong string!endl;return 0;}}//{}情况 if(str[i]{){Push_stack(s,str[i]);if(str[i1]}){Pop_stack(s,str[i]);continue;}else{coutWrong string!endl;return 0;}}}coutRight string!endl; return 0;
}实验2结果展示 实验3代码
#include cstdio
#define MaxSize 10 //栈的容量
#define ElemType int
#include iostream
using namespace std; typedef struct {ElemType data[MaxSize]; int top1;//1号栈栈顶指针int top2;//2号栈栈顶指针
}ShStack;//初始化共享栈
void InitShStack(ShStack S) {S.top1 -1;//初始化1号栈栈顶指针S.top2 MaxSize;//初始化2号栈栈顶指针
}//1号栈判空
bool Stack1Empty(ShStack S) {return (S.top1 -1);
}//2号栈判空
bool Stack2Empty(ShStack S) {return (S.top2 MaxSize);
}//1号栈入栈操作新元素入栈(先存再加)
bool Push1(ShStack S, ElemType x) {if (S.top11 S.top2){return false;//栈满报错}S.data[S.top1] x;return true;
}//2号栈入栈操作新元素入栈(先存再加)
bool Push2(ShStack S, ElemType x) {if (S.top11 S.top2){return false;//栈满报错}S.data[--S.top2] x;return true;
}//1号栈出栈操作栈顶元素出栈
bool Pop1(ShStack S, ElemType x) {if (S.top1 -1){return false;//1号栈栈空报错}x S.data[S.top1--]; return true;
}//2号栈出栈操作栈顶元素出栈
bool Pop2(ShStack S, ElemType x) {if (S.top2 MaxSize){return false;//2号栈栈空报错}x S.data[S.top2];return true;
}//1号栈读取栈顶元素操作
bool GetTop1(ShStack S, ElemType x) {if (S.top1 -1){return false;//1号栈栈空报错}x S.data[S.top1];return true;
}//2号栈读取栈顶元素操作
bool GetTop2(ShStack S, ElemType x) {if (S.top2 MaxSize){return false;//2号栈栈空报错}x S.data[S.top2];return true;
}int main() {//声明一个共享栈ShStack S; //初始化共享栈InitShStack(S);//1号栈-判空if(Stack1Empty(S)){printf(当前1号栈空\n);}else{printf(当前1号栈非空\n);}//1号栈-入栈操作ElemType e1;printf(请输入1号栈入栈元素的值);scanf(%d, e1);if(Push1(S, e1)){printf(1号栈新元素入栈成功\n);}else{printf(共享栈已满,1号栈新元素入栈失败\n);}//1号栈-读取栈顶元素ElemType e2 -1;if(GetTop1(S, e2)){printf(1号栈读取栈顶元素成功当前栈顶元素值为%d\n, e2);}else{printf(1号栈已空读取栈顶元素失败\n);}//1号栈-出栈操作ElemType e3 -1;if(Pop1(S, e3)){printf(1号栈栈顶元素出栈成功出栈元素值为%d\n, e3);}else{printf(1号栈已空栈顶元素出栈失败\n);}//1号栈-读取栈顶元素ElemType e4 -1;if (GetTop1(S, e4))printf(1号栈读取栈顶元素成功当前栈顶元素值为%d\n, e4);elseprintf(1号栈已空读取栈顶元素失败\n);coutendl;//2号栈-判空if (Stack2Empty(S)){printf(当前2号栈空\n);}else{printf(当前2号栈非空\n);}//2号栈-入栈操作ElemType e21;printf(请输入2号栈入栈元素的值);scanf(%d, e21);if (Push2(S, e21)){printf(2号栈新元素入栈成功\n);}else{printf(共享栈已满,2号栈新元素入栈失败\n);}//2号栈-读取栈顶元素ElemType e22 -1;if (GetTop2(S, e22)){printf(2号栈读取栈顶元素成功当前栈顶元素值为%d\n, e22);}else{printf(2号栈已空读取栈顶元素失败\n);}//2号栈-出栈操作ElemType e23 -1;if (Pop2(S, e23)){printf(2号栈栈顶元素出栈成功出栈元素值为%d\n, e23);}else{printf(2号栈已空栈顶元素出栈失败\n);}//2号栈-读取栈顶元素ElemType e24 -1;if (GetTop2(S, e24)){printf(2号栈读取栈顶元素成功当前栈顶元素值为%d\n, e24);}else{printf(2号栈已空读取栈顶元素失败\n);}return 0;
}实验3结果展示 2请分析你程序中每个功能模块的算法时间复杂度。
实验1 单元素出栈只需要锁定顶层的元素即可。所以时间复杂度为O(1)。 单元素入栈只需要对顶层进行元素覆盖即可。所以时间复杂度为O(1)。 假设字符串长度为len那么多元素入栈需要执行len次。所以时间复杂度为O(n)。 本段代码通过对入栈后的字符串反向出栈进行判断即出栈的第一个元素是原来字符串的最后一个元素。我们可以令出栈的第一个元素与原字符串的第一个元素进行对比来判断该字符串对应的数字是否为回文数。所以时间复杂度为O(n)。
实验2
出栈、入栈等操作沿用实验1的结果这里不再赘述。 当输入的符号字符串长度为奇数的时候一定有一个括号落单即一定不可能为合法的输入。符号字符串的长度为偶数是必要不充分条件因此直接否定奇数长度可减少算力。所以时间复杂度为O(1)。 本段算法通过循环先对当前的字符进行判断再对下一个邻近的字符进行判断即判断相邻两个括号是否为合法输入。整个过程需要对字符串每一个位置的字符进行判断。所以时间复杂度为O(n)。
实验3 判断栈是否为空栈只需要判断顶指针是否处于-1位置。所以时间复杂度为O(1)。 新元素入栈的时候先要判断共享栈是否已满。如果共享栈非满那么在下一个位置插入一个元素顶指针同时移动到该位置。所以时间复杂度为O(1)。 新元素出栈的时候先要判断共享栈是否已空。如果共享栈非空那么在当前位置弹出一个元素顶指针同时移动到前一个位置。所以时间复杂度为O(1)。 查看共享栈的两个栈顶元素时只需要在保证两个栈非空的情况下对顶指针所指向的元素进行查看。所以时间复杂度为O(1)。 其他
#includeiostream
#includecstring
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
using namespace std;typedef struct SqStack {char *elem;int top;int stacksize;
}SqStack;//初始化栈容量是事先定义好的定义初始的top标号为-1.
void InitStack(SqStack S)
{S.elem new char[STACK_INIT_SIZE];if (!S.elem)cout Overflow! endl;S.top -1;S.stacksize STACK_INIT_SIZE;
}//该函数用来释放栈的空间
void DestroyStack(SqStack S)
{delete[]S.elem;S.top -1;S.stacksize 0;
}//若栈已满该函数用来增加栈的空间
void increment(SqStack S)
{char *newstack new char[S.stacksize STACK_INCREMENT];if (!newstack)cout Overflow! endl;for (int i 0; i S.top; i){newstack[i] S.elem[i];}delete[]S.elem;S.elem newstack;S.stacksize STACK_INCREMENT;
}//该函数用来往栈里面增添元素因为是入栈所以栈顶元素的位置数加一该元素成为新的栈顶元素
void Push(SqStack S, char e)
{if (S.top S.stacksize - 1)increment(S);S.elem[S.top] e;
}//该元素用来返回栈顶元素的值
char GetTopStack(SqStack S)
{if (S.top -1)cout Empty! endl;return S.elem[S.top];
}//该函数用来将元素出栈
void Pop(SqStack S)
{if (S.top -1)cout Empty! endl;S.top--;
}//主函数将字符串的长度len对2取模记为mid将前mid个字符入栈。若该字符串回文先给标志赋值为0如果len为偶数则第mid1个元素应和栈顶元素相同如果不同就直接退出循环将标志的值改为1相同就将元素出栈判断下一个字符和栈顶元素是否相等以此类推。如果len为奇数则最中间的元素和其它元素都不同跳过这个元素继续向下判断。最后通过标志的值判断该字符串是否回文如果标志的值被修改说明对称的两元素不相同则字符串不回文。
int main()
{SqStack s;InitStack(s);char str[1000];cin str;int len strlen(str);int mid len / 2;int i, flag 0;for (i 0; i mid; i){Push(s, str[i]);}if (len % 2 1)i;while (ilen){if (GetTopStack(s) ! str[i]){flag 1;break;}i;Pop(s);}if (flag){cout 该字符向量不是回文 endl;}else{cout 该字符向量是回文 endl;}return 0;
}#includeiostream
#includecstring
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
using namespace std;typedef struct SqStack {char* elem;int top;int stacksize;
}SqStack;//初始化栈容量是事先定义好的定义初始的top标号为-1.
void InitStack(SqStack S)
{S.elem new char[STACK_INIT_SIZE];if (!S.elem)cout Overflow! endl;S.top -1;S.stacksize STACK_INIT_SIZE;
}//该函数用来释放栈的空间
void DestroyStack(SqStack S)
{delete[]S.elem;S.top -1;S.stacksize 0;
}//若栈已满该函数用来增加栈的空间
void increment(SqStack S)
{char* newstack new char[S.stacksize STACK_INCREMENT];if (!newstack)cout Overflow! endl;for (int i 0; i S.top; i){newstack[i] S.elem[i];}delete[]S.elem;S.elem newstack;S.stacksize STACK_INCREMENT;
}//该函数用来往栈里面增添元素因为是入栈所以栈顶元素的位置数加一该元素成为新的栈顶元素
void Push(SqStack S, char e)
{if (S.top S.stacksize - 1)increment(S);S.elem[S.top] e;
}//该元素用来返回栈顶元素的值
char GetTopStack(SqStack S)
{if (S.top -1)cout Empty! endl;return S.elem[S.top];
}//该函数用来将元素出栈
void Pop(SqStack S)
{if (S.top -1)cout Empty! endl;S.top--;
}//主函数输入字符串向后遍历如果元素是左括号则将左括号入栈如果元素是右括号则将左括号弹出栈顶这样可以继续判断下一个左括号是否和右括号匹配。一旦右括号和左括号匹配不成功那么修改标志表示括号匹配失败。其中需要一开始就将‘#’压入栈如果最后字符串遍历完了也就是左括号都被消解完了栈顶元素是‘#’说明左括号和右括号匹配上不多不少刚刚好。
int main()
{SqStack s;int flag 1;InitStack(s);Push(s, #);char str[1000];cin str;int len strlen(str);for (int i 0; i len; i){if (str[i] ( || str[i] [ || str[i] {)Push(s, str[i]);else{if (str[i] )){if (GetTopStack(s) ! (){flag 0;break;}elsePop(s);}else if (str[i] ]){if (GetTopStack(s) ! [){flag 0;break;}elsePop(s);}else if (str[i] }){if (GetTopStack(s) ! {){flag 0;break;}elsePop(s);}}}if (GetTopStack(s) ! #)flag 0;if (flag)cout 括号匹配成功 endl;elsecout 括号匹配失败 endl;return 0;
} 设top1和top2分别为栈1和2的栈顶元素的位置。 (1) 入栈主要语句 栈1的入栈语句 if(top2-top11) { cout“栈满”endl; exit(0); } SPACE[top1]x; //设x为入栈元素。 栈2的入栈语句 if(top2-top11) { cout“栈满”endl; exit(0); } SPACE[--top2]x; 出栈主要语句 栈1的出栈语句: if(top1-1) { cout“栈空”endl; exit(0); } top1--; return(SPACE[top11]); //返回出栈元素。 栈2的出栈语句: if(top2N) { cout“栈空”endl; exit(0); } top2; return(SPACE[top2-1]); 栈满条件:top2-top11 栈空条件:top1-1并且top2N //top1-1为左栈空,top2N为右栈空
