当前位置：网站首页>第三章课后习题15-23
第三章课后习题15-23
2022-07-21 11:22:00 【我辈当自强】
3.10
void test(int &sum)
{
int x;
scanf(x);
if(x==0) sum=0;
else{
test(sum);sum+=x;
}
printf(sum);
}
答案：
void test(int &sum)
{
Stack s;
InitStack(s);
int x;
do{
scanf(x);
Push(s,x);
}while(x>0);
while(!StackEmpty(s)){
Pop(s,x);
sum+=x;
printf(sum);
}
DestoryStack(s);
}
3.11简述队列和栈这2种数据类型的相同点和差异点
栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
3.15
class DStack{
ElemType *top[2];
ElemType *p;
int stacksize;
int di;
public:
DStack(int m)
{
p=new ElemType[m];
if(!p) exit(OVERFLOW);
top[0]=p+m/2;
top[1]=top[0];
stacksize=m;
}
DStack(){
delete p;
}
void Push(int i,ElemType x)
{
di=i;
if(di==0){
if(top[0]>=p) *top[0]--=x;
else printf("Stack overflow");
}
else{
if(top[1]<p+stacksize-1) *++top[1]=x;
printf("Stack overflow");
}
}
ElemType Pop(int i)
{
di=i;
if(di==0){
if(top[0]<top[1]) return *++top[0];
printf("Stack empty!");
}else{
if(top[1]>top[0]) return *top[1]--;
else printf("Stack empty");
}
return OK;
}
};
typedef struct NodeType{
ElemType data;
NodeType *next;
}NodeType,*LinkType;
typedef struct{
LinkType top;
int size;
}Stack;
void InitStack(Stack &s)
{
s.top=NULL;
s.size=0;
}
void DestroyStack(Stack &s)
{
LinkType p;
while(s.top){
p=s.top;
s.top=p->next;
delete p;
s.size--;
}
}
void ClearStack(Stack &s)
{
LinkType p;
while(s.top){
p=s.top;
s.top=p->next;
delete p;
s.size--;
}
}
int StackLength(Stack s)
{
return s.size;
}
Status StackEmpty(Stack s)
{
if(s.size==0) return TRUE;
else return FALSE;
}
Status GetTop(Stack s,ElemType &e)
{
if(!s.top) return ERROR;
else{
e=s.top->data;
return OK;
}
}
Status Push(Stack &s,ElemType e)
{
LinkType p;
p=new NodeType;
if(!p) exit(OVERFLOW);
p->next=s.top;
s.top=p;
p->data=e;
s.size++;
return OK;
}
Status Pop(Stack &s,ElemType &e)
{
LinkType p;
if(s.top){
e=s.top->data;
p=s.top;
s.top=p->next;
delete p;
s.size--;
}
return OK;
}
//从栈顶到栈底用visit（）函数遍历栈中每一个数据元素
void StackTraverse(Stack s,Status (*Visit)(ElemType e))
{
LinkType p;
p=s.top;
while(p) Visit(p->data);
}
3.16
int main()
{
Stack s;
char Buffer[80];
int i=0,j=0;
InitStack(s);
printf("请输入硬席H和软席S序列:");
scanf(Buffer);
prinf(Buffer);
while(Buffer[i]){
if(Buffer[i]=='S'){
Buffer[j]=Buffer[i];
j++;
}
else Push(s,Buffer[i]);
i++;
}
while(Buffer[j]){
Pop(s,Buffer[j]);
j++;
}
prinf(Buffer);
return 0;
}
3.17
bool Symmetry(char a[])
{
int i=0;
Stack s;
InitStack(s);
ElemType x;
while(a[i]!='&'&&a[i]){
Push(s,a[i]);
i++;
}
while(a[i]){
Pop(s,x);
if(x!=a[i]){
DestroyStack(s);
return FALSE;
}
i++;
}
return TRUE;
}
3.18试写一个判断表达式中开、闭括号是否匹配出现的算法
bool BracketCorrespondency(char a[])
{
int i=0;
Stack s;
InitStack(s);
ElemType x;
while(a[i]){
switch(a[i]){
case '(':
Push(s,a[i]);
break;
case '[':
Push(s,a[i]);
break;
case ')':
GetTop(s,x);
if(x=='(') Pop(s,x);
else return FALSE;
break;
case ']':
GetTop(s,x);
if(x=='[') Pop(s,x);
else return FALSE;
break;
default:
break;
}
i++;
}
if(s.size!=0) return FALSE;
return TRUE;
}
3.19、假设一个算术表达式中包含圆括号、方括号、花括号3种类型的括号，编写一个算法来判断表达式中的括号是否匹配，以字符‘\0’作为算术表达式的结束符
bool BracketCheck(char *str)
{
int i=0;
while(str[i]!='\0'){
switch(str[i]){
//左括号入栈
case '(':Push(S,'(');break;
case '[':Push(S,'[');break;
case '{':Push(S,'{');break;
case ')':Pop(S,e);
if(e!='(') return false;
break;
case ']':Pop(S,e);
if(e!='[') return false;
case '}':Pop(S,e);
if(e!='(') return false;
break;
default:
break;
}
i++;
}
if(!IsEmpty(S)){
printf("括号不匹配\n");
return false;
}
else{
printf("括号匹配\n");
return true;
}
}
3.21
void InversePolandExpression(char Buffer[])
{
//输入的表达式串必须为#...#格式
Stack s;
InitStack(s);
int i=0,j=0;
ElemType e;
Push(s,Buffer[i]);
i++;
while(Buffer[i]!='#'){
if(!IsOperator(Buffer[i])){
//是操作数
Buffer[j]=Buffer[i];
i++;
j++;
}
else{
//是操作符
GetTop(s,e);
if(Prior(e,Buffer[i])){
//当栈顶优先权高于当前序列时，退栈
Pop(s,e);
Buffer[j]=e;
j++;
}
else{
Push(s,Buffer[i]);
i++;
}
}
}
while(!StackEmpty(s)){
Pop(s,e);
Buffer[j]=e;
j++;
}
}
Status IsOpertor(char c)
{
char *p="#+-*/";
while(*p){
if(*p==c)
return TRUE;
p++;
}
return FALSE;
}
Status Prior(char c1,char c2)
{
char ch[]="#+-*/";
int i=0,j=0;
while(ch[i]&&ch[i]!=c1) i++;
if(i==2) i--;//加和减可认为是同级别的运算符
if(i==4) i--;//乘和除可认为是同级别的运算符
while(ch[j]&&ch[j]!=c2) j++;
if(j==2) j--;
if(j==4) j--;
if(i>=j) return TRUE;
else return FALSE;
}
3.22
char CalVal_InverPoland(char Buffer[])
{
Stack Opnd;
InitStack(Opnd);
int i=0;
char c;
ElemType e1,e2;
while(Buffer[i]!='#'){
if(!IsOperator(Buffer[i])){
Push(Opnd,Buffer[i]);
}
else{
Pop(Opnd,e2);
Pop(Opnd,e1);
c=Cal(e1,Buffer[i],e2);
Push(Opnd,c);
}
i++;
}
return c;
}
char Cal(char c1,char op,char c2)
{
int x,x1,x2;
char ch[10];
ch[0]=c1;
ch[1]='\0';
x1=atoi(ch);
ch[0]=c2;
ch[1]='\0';
x2=atoi(ch);
switch(op){
case '+':
x=x1+x2;
break;
case '-':
x=x1-x2;
break;
case '*':
x=x1*x2;
break;
case '/':
x=x1/x2;
break;
default:
break;
}
itoa(x,ch,10);
return ch[0];
}
3.23
逆波兰表达式：后缀表达式
波兰变达式：前缀表达式
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include "d:\VC99\DSConstant.h"
typedef char ARRAY[30];
typedef ARRAY ElemType;
typedef struct NodeType{
ElemType data;
NodeType *next;
}NodeType,*LinkType;
typedef struct{
LinkType top;
int size;
}Stack;
void InitStack(Stack &s);
Status Push(Stack &s,ElemType e);
Status Pop(Stack &s,ElemType e);
Status IsOperator(char c);
Status StackEmpty(Stack s);
Status InvToFroPoland(char a[]);
int main
{
char a[30];
cout<<"请输入逆波兰算术表达式字符序列:";
cin>>a;
if(InvToFroPoland(a)) cout<<a<<endl;
else cout<<"输入逆波兰算术表达式字符序列错误!";
return 0;
}
Status InvToFroPoland(char a[])
{
Stack s;
InitStack(s);
int i=0;
ElemType ch;
ElemType c1;
ElemType c2;
while(a[i]!='#'){
if(!IsOperator(a[i])){
if(a[i]>'0'&&a[i]<='9'){
ch[0]=a[i];ch[1]='\0';
Push(s,ch);
}
else return FALSE;
}
else{
ch[0]=a[i];
ch[1]='\0';
if(!StackEmpty(s)){
Pop(s,c2);
if(!StackEmpty(s)){
Pop(s,c1);
strcat(ch,c1);
strcat(ch,c2);
Push(s,ch);
}
else return FALSE;
}
else return FALSE;
}
i++;
}
if(!StackEmpty(s)){
Pop(s,c1);
strcpy(a,c1);
}
else return FALSE;
if(!StackEmpty(s)) return FALSE;
return OK;
}
void InitStack(Stack &s)
{
s.top=NULL;
s.size=0;
}
Status Push(Stack &s,ElemType e)
{
LinkType p;
p=new NodeType;
if(!p) exit(OVERFLOW);
p->next=s.top;
s.top=p;
strcpy(p->data,e);
s.size++;
return OK;
}
Status Pop(Stack &s,ElemType e)
{
LinkType p;
if(s.top){
strcpy(e,s.top->data);
p=s.top;
s.top=p->next;
delete p;
s.size--;
}
return OK;
}
Status IsOperator(char c)
{
char *p="#+-*/";
while(*p){
if(*p==c)
return TRUE;
p++;
}
return FALSE;
}
边栏推荐
猜你喜欢
Multiplier technology cloud management and control platform adapts to Alibaba cloud polardb, and jointly promotes the prosperity of cloud native database ecosystem
IDEA 2020.1 取消参数名称显示
一招教你拿捏网上视频
servlet写webapp时，用filter拦截实现登陆验证
Talking about NPM construction process and package JSON and package lock. Workflow of JSON
Flink reports an error when executing SQL using API
Application of SCA on devsecops platform
LTspice软件电源设置
Idea 2020.1 cancel parameter name display
3.1栈
随机推荐
代码管理（新手）
Advanced Fruits(公共子序列)
如何搭建一个好的知识库管理系统？
[mid 2022 summary] I walk very slowly, but I never retreat
二月天
DDR SDRAM板卡设计指南
关于Thread.sleep()方法
【2022年中总结】我走得很慢，但我从不后退
A solution for adding new MySQL users that cannot be authorized
高速ASIC封装趋势：集成，SKU和25G+
PAM4科普
Dialogue ace phase IV: challenges and opportunities for the future development of distributed databases
seaborn绘制箱线图和折线图
Excel实操笔记1
Idea建文件夹时，文件夹的空文件夹的展开与重叠
Lsky Pro兰空图床安装与使用:一个用于在线上传,管理图片的图床程序
网站为什么会有漏洞要去修补
Date tool class
servlet写webapp时，用filter拦截实现登陆验证
MySQL(数据类型和完整约束)