沈师PTA数据结构第3章实验题集-栈与队列操作
R7-1 堆栈操作合法性 (20 分)
假设以S
和X
分别表示入栈和出栈操作。如果根据一个仅由S
和X
构成的序列,对一个空堆栈进行操作,相应操作均可行(如没有出现删除时栈空)且最后状态也是栈空,则称该序列是合法的堆栈操作序列。请编写程序,输入S
和X
序列,判断该序列是否合法。
输入格式:
输入第一行给出两个正整数N和M,其中N是待测序列的个数,M(≤50)是堆栈的最大容量。随后N行,每行中给出一个仅由S
和X
构成的序列。序列保证不为空,且长度不超过100。
输出格式:
对每个序列,在一行中输出YES
如果该序列是合法的堆栈操作序列,或NO
如果不是。
输入样例:
4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX
结尾无空行
输出样例:
YES
NO
NO
NO
结尾无空行
#include
#include
#include
#include
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int Status;
using namespace std;
typedef struct{
char *base;
char *top;
int stacksize;
} SqStack;
Status InitStack(SqStack &S,int L){
S.base=new char[L];
if(!S.base)
exit(OVERFLOW);
S.top=S.base;
S.stacksize=L;
return OK;
}
Status push(SqStack &S,char c){
if(S.top-S.base==S.stacksize)
return ERROR;
*S.top++=c;
return OK;
}
Status pop(SqStack &S,char c){
if(S.top==S.base)
return ERROR;
c=*(--S.top);
return OK;
}
bool IsRight(string s,int L){
int i=0,flag=1;
SqStack St;
InitStack(St,L);
while(s[i]!='\0'){
if(s[i]=='S'){
if(push(St,s[i])==OK)
i++;
else{
flag=0;
break;
}
}
else{
if(pop(St,s[i])==OK)
i++;
else{
flag=0;
break;
}
}
}
if((St.top==St.base) && s[i]=='\0')
flag=1;
else
flag=0;
if(flag==1)
return true;
else
return false;
}
int main()
{
int N,M,k=0;
char c;
string ss;
cin>>N>>M;
for(int i=0; i>ss;
if(IsRight(ss,M)==true)
cout<<"YES"<
R7-2 括号匹配 (20 分)
检查一段C语言代码的小括号( )
、 中括号 [ ]
和大括号{ }
是否匹配。
输入格式:
在一行中输入一段C语言代码,长度不超过1000个字符(行末以换行符结束)。
输出格式:
第一行输出左括号的数量和右括号的数量,中间以一个空格间隔。
若括号是匹配的,在第二行打印YES
,否则打印NO
。
输入样例1:
for(int i=0; iAdj[i][j])); }
结尾无空行
输出样例1:
8 8
YES
结尾无空行
输入样例2:
for(int i=0; i
输出样例2:
2 2
NO
#include
#include
#include
#include
using namespace std;
int main() {
string s;
stack st;
getline(cin,s);
int l=0,r=0;
bool flag=1;
for(int i=0; i
R7-3 字符串对称 (20 分)
编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。
输入格式:
输入一个无空格的字符串。
输出格式:
如果该字符是对称的,输出yes,否则输出no。
输入样例:
在这里给出一组输入。例如:
abba
结尾无空行
输出样例:
在这里给出相应的输出。例如:
yes
结尾无空行
输入样例:
在这里给出一组输入。例如:
abcd
结尾无空行
输出样例:
在这里给出相应的输出。例如:
no
结尾无空行
#include
#include
#include
using namespace std;
#define MaxSize 60
typedef int 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 symmetry(string str){
ElemType e;
SqStack *st;
InitStack(st); //初始化栈
//元素进栈
for(int i=0;i>str;
bool flag;
//判断它是不是对称串
flag=symmetry(str);
if(flag)
cout<<"yes"<
R7-4 数据结构考题 十进制转换为二进制 (20 分)
利用栈(以顺序栈作存储结构)实现进制转换。给定一个十进制整数,编程将该数以二进制形式输出。
顺序栈的类型定义:
#define MAXSIZE 100 // MAXSIZE为最大数据元素数目
typedef int ElemType;
typedef struct
{ ElemType *base;
ElemType *top;
}SqStack;
输入格式:
输入一个十进制整数。
输出格式:
输出转换后的二进制数。
输入样例:
15
结尾无空行
输出样例:
在这里给出相应的输出。例如:
1111
结尾无空行
#include
using namespace std;
#define MaxSize 100 /* 栈最大容量 */
int top; /* 栈顶指针 */
int mystack[MaxSize]; /* 顺序栈 */
/*判栈是否为空,空返回true,非空返回false */
bool isEmpty();
/* 元素x入栈 */
void Push(int x);
/* 取栈顶元素 */
int getTop();
/* 删除栈顶元素 */
void Pop();
/* 十进制正整数转换为二进制 */
void dec2bin(int x) {
top = -1; /* 初始化栈顶指针 */
while (x) {
Push(x % 2);
x >>= 1;
}
while (!isEmpty()) {
int t = getTop();
Pop();
printf("%d", t);
}
//printf("\n");
}
int main(int argc, char const *argv[]){
int n;
while (scanf("%d", &n) != EOF) {
dec2bin(n);
}
return 0;
}
bool isEmpty(){
if (top == -1)
return true;
else
return false;
}
/* 元素x入栈 */
void Push(int x){
if (top == MaxSize - 1)
return;
else
{
top++;
mystack[top] = x;
}
}
/* 取栈顶元素 */
int getTop(){
if (top == -1)
return 0;
else
return mystack[top];
}
/* 删除栈顶元素 */
void Pop(){
if (top == -1)
return;
else
top--;
}
R7-5 数据结构考题 十进制转换为八进制 (20 分)
利用栈(以顺序栈作存储结构)实现进制转换。给定一个十进制整数,编程将该数以八进制形式输出。
顺序栈的类型定义:
#define MAXSIZE 100 // MAXSIZE为最大数据元素数目
typedef int ElemType;
typedef struct
{ ElemType *base;
ElemType *top;
}SqStack;
输入格式:
输入一个十进制整数。
输出格式:
输出转换后的八进制数。
输入样例:
100
结尾无空行
输出样例:
在这里给出相应的输出。例如:
144
结尾无空行
#include
#include
//定义栈结构
typedef struct stack{
int num[50];
int tap;
}Stack;
//声明函数
void setTable(char* table);
void push(int number);
int pop();
int isEmpty();
//声明全局变量
Stack *stack;
int main(){
int number; //number-被转换数
char table[36]; //定于数字字母匹配表
setTable(table);
//printf("输入十进制数字:");
scanf("%d",&number);
stack = (Stack*)malloc(sizeof(Stack));
stack->tap=0;
//短除法
while(1){
push( number % 8);
number = number/8;
if(number == 0)break;
}
//printf("结果为:");
while(isEmpty() == 0){
printf("%c",table[pop()]);
}
//putchar(10);//换行
return 0;
}
//填充数字字母表
void setTable(char table[]){
int i = 0;
for(;i<10;i++){
table[i]='0'+i;
}
for(;i<37;i++){
table[i]='A'+i-10;
}
}
//入栈
void push(int number){
stack->num[stack->tap] = number;
stack->tap = stack->tap + 1;
}
//出栈
int pop(){
stack->tap = stack->tap - 1;
return stack->num[stack->tap];
}
//判断是否为空
int isEmpty(){
if(stack->tap == 0)
return 1;
else
return 0;
}
R7-6 队列操作 (20 分)
请实现一个MyQueue类,实现出队,入队,求队列长度.
实现入队函数 void push(int x); 实现出队函数 int pop(); 实现求队列长度函数 int size();
输入格式:
每个输入包含1个测试用例。每个测试用例第一行给出一个正整数 n (n <= 10^6) ,接下去n行每行一个数字,表示一种操作: 1 x : 表示从队尾插入x,0<=x<=2^31-1。 2 : 表示队首元素出队。 3 : 表示求队列长度。
输出格式:
对于操作2,若队列为空,则输出 “Invalid”,否则请输出队首元素。 对于操作3,请输出队列长度。 每个输出项最后换行。
输入样例:
5
3
2
1 100
3
2
结尾无空行
输出样例:
0
Invalid
1
100
#include
using namespace std;
typedef struct queue{
int x;
struct queue *next;
} LinkList;
class MyQueue{
LinkList *head, *node, *end;
static int j;
public:
MyQueue()
{
head=NULL;
node=NULL;
end=NULL;
head=new LinkList;
end=head;
}
void push(int x)
{
node=new LinkList;
node->x=x;
end->next=node;
node=end;
j++;
}
void pop()
{
if(j==0)
cout<<"Invalid"<next->x<next=head->next->next;
delete head->next;
j--;
}
}
int size(){
return j;
}
};
int MyQueue::j=0;
int main(void){
MyQueue ob;
int n,i,c,d;
scanf("%d",&n);
for(i=0;i