刷题时间：2021/03/23-2021/03/26
数据结构实验之栈与队列
一：进制转换
Description
输入一个十进制非负整数，将其转换成对应的 R (2 <= R <= 9) 进制数，并输出。
Input
第一行输入需要转换的十进制非负整数；
第二行输入 R。
Output
输出转换所得的 R 进制数。
Sample
**Input **
1279
8
Output
2377
参考代码
/*
思路很简单就是多少进制就对R取余进栈就完事了，最后出栈输出
*/
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,r;
int a[100000];
int top=0;
scanf("%d",&n);
scanf("%d",&r);
if(n==0)printf("%d\n",n);
else
{
while(n!=0)
{
a[top++]=n%r;//进栈
n=n/r;
}
while(top!=0)
{
printf("%d",a[--top]);//出栈
}
}
return 0;
}
二：一般算术表达式转换成后缀式
Description
对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。
Input
输入一个算术表达式，以‘#’字符作为结束标志。
Output
输出该表达式转换所得到的后缀式。
Sample
Input
a*b+(c-d/e)*f#
**Output **
ab*cde/-f*+
参考代码
#include <stdio.h>
#include <string.h>
int f(char ch, char sh)
{//判断新的字符
if(sh=='(') return 1;
if( (ch=='*' || ch=='/' || ch=='%')&&( sh=='+' || sh=='-') )//判断新的运算符是不是比栈顶的运算符优先级高
return 1;
else
return -1;
}
int main()
{
int i = 0 , n , top = -1 ;//top运算符栈顶
char exp[1000] , str[1000] , ch ;//exp后缀式，str运算符栈
while(scanf("%c", &ch) && ch != '#')
{
if(ch >= 'a' && ch <='z')//正常输入
exp[i++] = ch ;
else if(ch=='(')//左括号进栈
str[++top] = ch ;
else if(ch==')')//右括号出栈
{
while(top!=-1)//while(1)也行，因为里面有‘(’的break
{
exp[i++] = str[top];
top--;
if(str[top]=='(')//遇到左括号break
{
top--;
break;
}
}
}
else//运算符
{
if(top == -1 || f(ch,str[top]) > 0 )//栈内无元素 或者 新运算符优先级高->进栈
str[++top] = ch ;
else//新运算符优先级低于栈顶元素
{
while(top >=0 && f(ch,str[top]) < 0 )//所有优先级高的运算符出栈
{
exp[i++] = str[top--];
}
str[++top] = ch ;//出栈完成后将新的运算符进栈
}
}
}
while(top != -1)//所有元素出栈
{
exp[i++] = str[top--];
}
exp[i] = '\0';//结束符
printf("%s\n", exp);
return 0;
}
三：后缀式求值
Description
对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。
Input
输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。
Output
求该后缀式所对应的算术表达式的值，并输出之。
Sample
**Input **
59*684/-3*+#
**Output **
57
Hint
基本操作数都是一位正整数!
参考代码
#include <stdio.h>
#include <stdlib.h>
int top=0,i,stack[1001];
int main()
{
char a[1001];
scanf("%s",a);
for(i=0;a[i]!='#';i++)//遍历
{
if(a[i]>='1'&&a[i]<='9')//正常数进栈
{
stack[++top]=a[i]-'0';
}
//然后判断 + - * /
else if(a[i]=='+')
{
stack[top-1]=stack[top-1]+stack[top];
top--;
}
else if(a[i]=='-')
{
stack[top-1]=stack[top-1]-stack[top];
top--;
}
else if(a[i]=='*')
{
stack[top-1]=stack[top-1]*stack[top];
top--;
}
else if(a[i]=='/')
{
stack[top-1]=stack[top-1]/stack[top];
top--;
}
}
printf("%d\n",stack[top]);
return 0;
}
四：括号匹配
Description
给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。
Input
输入数据有多组，处理到文件结束。
Output
如果匹配就输出“yes”，不匹配输出“no”
Sample
**Input **
sin(20+10)
{[}]
**Output ***
yes
no
参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int date[52];
int main()
{
char a[55];
int i,top,len;
while(gets(a))
{
top=0;
len=strlen(a);
for(i=0;i<len;i++)//遍历
{
if(a[i]=='('||a[i]=='['||a[i]=='{'){//左括号进栈
date[top++]=a[i];
}
else if((a[i]==')'||a[i]==']'||a[i]=='}'))//右括号判断
{
if(top==0){//栈为空，只有右括号,匹配失败
break;
}
else//栈不为空
{
if((date[top-1]=='(' && a[i]==')') || (date[top-1]=='[' && a[i]==']') || (date[top-1]=='{' && a[i]=='}'))
date[--top];//匹配成功，出栈
else{
break;
}
}
}
}
if(top==0&&i==len)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
五：下一较大值（一）
Description
对于包含n（1<=n<=1000）个整数的序列，对于序列中的每一元素，在序列中查找其位置之后第一个大于它的值，如果找到，输出所找到的值，否则，输出-1。
Input
输入有多组，第一行输入t（1<=t<=10），表示输入的组数；
以后是 t 组输入：每组先输入n，表示本组序列的元素个数，之后依次输入本组的n个元素。
Output
输出有多组，每组之间输出一个空行（最后一组之后没有）；
每组输出按照本序列元素的顺序，依次逐行输出当前元素及其查找结果，两者之间以-->间隔。
Sample
**Input **
2
4 12 20 15 18
5 20 15 25 30 6
**Output **
12-->20
20-->-1
15-->18
18-->-1
20-->25
15-->25
25-->30
30-->-1
6-->-1
Hint
本题的数据量小、限时要求低，可以不用栈来完成。
参考代码（无栈）
#include<stdio.h>
#include<stdlib.h>
int a[1001];
int main()
{
int t,n,i,j,flag;//flag标记是否输出过
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
}
for(i=1; i<=n; i++)
{
for(j=i; j<=n; j++)//双重循环暴力跑
{
if(a[j]>a[i])
{
flag=1;
printf("%d-->%d\n",a[i],a[j]);
break;
}
else flag=0;
}
if(flag==0)//之前没有被输出标记，所以没有比它大的，输出-1
{
printf("%d-->%d\n",a[i],-1);
}
}
if(t==0){
break;
}else{
printf("\n");
}
}
}
return 0;
}
六：下一较大值（二）
Description
对于包含n（1<=n<=100000）个整数的序列，对于序列中的每一元素，在序列中查找其位置之后第一个大于它的值，如果找到，输出所找到的值，否则，输出-1。
Input
输入有多组，第一行输入t（1<=t<=10），表示输入的组数；
以后是 t 组输入：每组先输入n，表示本组序列的元素个数，之后依次输入本组的n个元素。
Output
输出有多组，每组之间输出一个空行（最后一组之后没有）；
每组输出按照本序列元素的顺序，依次逐行输出当前元素及其查找结果，两者之间以-->间隔。
Sample
**Input **
2
4 12 20 15 18
5 20 15 25 30 6
Output
12-->20
20-->-1
15-->18
18-->-1
20-->25
15-->25
25-->30
30-->-1
6-->-1
Hint
本题数据量大、限时要求高，须借助栈来完成。
参考代码（栈实现）
#include <stdio.h>
#include <stdlib.h>
int s[100005]; //分配栈的大小
int main()
{
int i,t,n,a[100005],b[100005],top; //b存a对应的下一个较大值
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
top=0;
b[n]=-1; //最后一个数无下一较大值
s[++top]=a[n]; //a[n]入栈
for(i=n-1;i>=1;i--)
{
if(a[i]<s[top])
{
b[i]=s[top]; //找到a[i]的下一较大值存入b[i]
s[++top]=a[i]; //a[i]入栈
}
else
{
while(a[i]>=s[top]&&top!=0)
top--; //不符合条件出栈
if(top==0)
{
b[i]=-1; //无下一较大值
s[++top]=a[i]; //a[i]入栈
}
else
{
b[i]=s[top];
s[++top]=a[i]; //a[i]入栈
}
}
}
for(i=1;i<=n;i++)
printf("%d-->%d\n",a[i],b[i]);
if(t!=0)
printf("\n");
}
return 0;
}
七：出栈序列判定
Description
给一个初始的入栈序列，其次序即为元素的入栈次序，栈顶元素可以随时出栈，每个元素只能入栈依次。输入一个入栈序列，后面依次输入多个序列，请判断这些序列是否为所给入栈序列合法的出栈序列。
例如序列1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个出栈序列，但4，3，5，1，2就不可能是该序列的出栈序列。假设压入栈的所有数字均不相等。
Input
第一行输入整数n(1<=n<=10000)，表示序列的长度。
第二行输入n个整数，表示栈的压入顺序。
第三行输入整数t（1<=t<=10）。
后面依次输入t行，每行n个整数，表示要判断的每一个出栈序列。
Output
对应每个测试案例输出一行，如果由初始入栈序列可以得到该出栈序列，则输出yes，否则输出no。
Sample
**Input **
5
1 2 3 4 5
2
4 5 3 2 1
4 3 5 1 2
**Output **
yes
no
Hint
参考代码
#include<stdio.h>
int main()
{
int i,j,n,t,top,a[10010],b[10010],c[10010];//数组a表示入栈元素，数组b表示出栈元素，数组c模拟栈
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&t);
while(t--)
{
top=0;
for(i=0;i<n;i++)
{
scanf("%d",&b[i]);
}
i=0;
j=0;
while(j<n)//遍历出栈元素
{
if(a[i]==b[j])//入栈元素等于出栈元素，表示刚入栈就出栈
{
i++;
j++;
}
else if(top!=0&&c[top]==b[j])//栈不为空时，栈顶元素等于出战元素（在刚入栈就出栈的元素后，次栈顶元素成为栈顶元素之后也要出栈）
{
--top;
j++;
}
else
{
c[++top]=a[i];
i++;
}
}
if(top==0)//栈为空时，表示出栈顺序可以满足
printf("yes\n");
else
printf("no\n");
}
return 0;
}
八：栈的基本操作
Description
堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。
Input
首先输入整数t（1 <= t <= 10），代表测试的组数，以后是 t 组输入。
对于每组测试数据，第一行输入两个正整数 m（1 <= m <= 100)、n（1 <= n <= 1000)，其中m代表当前栈的最大长度，n代表本组测试下面要输入的操作数。 而后的 n 行，每行的第一个字符可能是'P’或者'O’或者'A’；如果是'P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O’，表示栈顶元素出栈；如果是'A'，表示询问当前栈顶的值'。
Output
对于每组测试数据，根据其中的命令字符来处理堆栈；
（1）对所有的'P'操作，如果栈满输出'F'，否则完成压栈操作；
（2）对所有的'A'操作，如果栈空，则输出'E'，否则输出当时栈顶的值；
（3）对所有的'O'操作，如果栈空，则输出'E'，否则输出栈顶元素的值，并让其出栈；
每个输出占据一行，每组测试数据（最后一组除外）完成后，输出一个空行。
Sample
**Input **
2
5 10
A
P 9
A
P 6
P 3
P 10
P 8
A
P 2
O
2 5
P 1
P 3
O
P 5
A
**Output **
E
9
8
F
8
3
5
Hint
建议： 用串的方式（%s）读入操作字符。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int t, m, n, i, j, x;
char a[20];
int b[10010];
scanf("%d", &t);
for(j = 1; j <= t; j++)
{
scanf("%d%d", &m, &n);
int num = 0;
for(i = 1; i <= n; i++)
{
scanf("%s", a);
if(strcmp(a, "P") == 0)
{
scanf("%d", &x);
if(m > num)
{
b[num] = x;
num++;
}
else
{
printf("F\n");
}
}
else if(strcmp(a, "A") == 0)
{
if(num == 0)
{
printf("E\n");
}
else
{
printf("%d\n", b[num-1]);
}
}
else if(strcmp(a, "O") == 0)
{
if(num == 0)
{
printf("E\n");
}
else
{
printf("%d\n", b[num - 1]);
num--;
}
}
}
if(j != t)
{
printf("\n");
}
}
return 0;
}
九：行编辑器
Description
一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。
由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符"#"，以表示前一个字符无效；
如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符"@"，以表示当前行中的字符均无效。
如果已经在行首继续输入'#'符号无效。
Input
输入多行字符序列，行字符总数（包含退格符和退行符）不大于250。
Output
按照上述说明得到的输出。
Sample
**Input **
whli##ilr#e(s#*s)
outcha@putchar(*s=#++);
**Output **
while(*s)
putchar(*s++);
参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char q[260];
int main()
{
int i,len,top;
char a[260];
while(gets(a))
{
top=0;
len=strlen(a);
for(i=0;i<len;i++)
{
if(a[i]=='#')
{
if(top!=0)
top--; //出栈
}
else if(a[i]=='@')
{
if(top!=0)
top=0; //清空栈
}
else
q[top++]=a[i]; //入栈
}
for(i=0;i<top;i++){
printf("%c",q[i]);
}
printf("\n");
}
return 0;
}
十：走迷宫
Description
一个由n * m 个格子组成的迷宫，起点是(1, 1)， 终点是(n, m)，每次可以向上下左右四个方向任意走一步，并且有些格子是不能走动，求从起点到终点经过每个格子至多一次的走法数。
Input
第一行一个整数T 表示有T 组测试数据。(T <= 110)
对于每组测试数据:
第一行两个整数n, m，表示迷宫有n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行，每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走，否则是1 表示这个格子不能走，输入保证起点和终点都是都是可以走的。
任意两组测试数据间用一个空行分开。
Output
对于每组测试数据，输出一个整数R，表示有R 种走法。
Sample
**Input **
3
2 2
0 1
0 0
2 2
0 1
1 0
2 3
0 0 0
0 0 0
**Output **
1
0
4
参考代码
//我的思路：dfs遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int mmap[110][110],vis[110][110],n,m,r;
void dfs(int x,int y){
if(x<1||y<1||x>n||y>m||mmap[x][y]==1){//1不能访问
return ;
}
if(x==n&&y==m){
r++;
return ;
}
if(vis[x][y]==0&&mmap[x][y]==0){
vis[x][y]=1;//本次访问过
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
vis[x][y]=0;//访问过就归0
}
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
memset(mmap,0,sizeof(mmap));//初始化数组
memset(vis,0,sizeof(vis));
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&mmap[i][j]);
}
}
r=0;
dfs(1,1);
printf("%d\n",r);
}
return 0;
}
十一：refresh的停车场
Description
refresh最近发了一笔横财，开了一家停车场。由于土地有限，停车场内停车数量有限，但是要求进停车场的车辆过多。当停车场满时，要进入的车辆会进入便道等待，最先进入便道的车辆会优先
进入停车场，而且停车场的结构要求只出去的车辆必须是停车场中最后进去的车辆。现告诉你停车场容量N以及命令数M，以及一些命令（Add num 表示车牌号为num的车辆要进入停车场或便道，
Del 表示停车场中出去了一辆车，Out 表示便道最前面的车辆不再等待，放弃进入停车场）。假设便道内的车辆不超过1000000.
Input
输入为多组数据，每组数据首先输入N和M（0＜ ｎ，ｍ ＜200000），接下来输入M条命令。
Output
输入结束后，如果出现停车场内无车辆而出现Del或者便道内无车辆而出现Out,则输出Error,否则输出停车场内的车辆，最后进入的最先输出，无车辆不输出。
Sample
**Input **
2 6
Add 18353364208
Add 18353365550
Add 18353365558
Add 18353365559
Del
Out
**Output **
18353365558
18353364208
参考代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char a[10005][15], b[10005][15], s[15];
int main()
{
int n, m, i, j, flag, sum1, sum2;
while(scanf("%d%d",&m,&n)!=EOF)
{
//m表示停车场容量，n表示n条操作
//m,n和题目弄反了，不过没关系，我知道就好了
flag=0;
sum1=0;//初始化栈顶
sum2=0;
for(i=1; i<=n; i++)
{
scanf("%s",s);//读入操作
if(strcmp("Add",s)==0)//Add
{
char x[20];
scanf("%s",x);
if(sum1<m)//停车场未满
{
strcpy(a[sum1],x);//进栈1（停车场）
sum1++;//栈顶+1
}
else//停车场满了
{
strcpy(b[sum2],x);//进栈2（便道）
sum2++;//栈顶+1
}
}
if(strcmp("Del",s)==0)//Del
{
if(sum1==0)flag=1;//flag=1表示ERROR，停车场为空，无法Del
else if(sum2==0)//停车场不为空，便道为空，则停车场出栈--
{
sum1=sum1-1;
}
else//都不为空
{
if(sum2==1)//便道只有一辆车
{
strcpy(a[sum1-1],b[0]);//把b[0]给a[sum1-1]，也就是把便道唯一的一辆车停在停车场的最后一位
sum2=0;//便道归0
}
else//便道有多辆车
{
strcpy(a[sum1-1],b[0]);//把便道最前面的一辆车停在停车场的最后一位
for(j=0; j<=sum2-2; j++)//递归依次赋值前一个
strcpy(b[j],b[j+1]);
sum2--;//便道出栈
}
}
}
if(strcmp("Out",s)==0)//Out
{
if(sum2==0)flag=1;//便道无车ERROR
else
{
if(sum2==1)//便道只有一辆车
sum2=0;
else
{
for(j=0; j<=sum2-2; j++)//递归依次赋值前一个
strcpy(b[j],b[j+1]);
sum2--;
}
}
}
}
if(flag==1)printf("Error\n");
else
{
for(i=sum1-1; i>=0; i--)
printf("%s\n",a[i]);
}
}
return 0;
}
评论区