SDUT《数据结构与算法》专题训练 3栈与队列 4串题解记录

数据结构实验之栈与队列一：进制转换

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

输入一个十进制非负整数，将其转换成对应的 R (2 <= R <= 9) 进制数，并输出。

Input

第一行输入需要转换的十进制非负整数；
第二行输入 R。

Output

输出转换所得的 R 进制数。

Sample Input

1279
8

Sample Output

Reference Code

#include<stdio.h>
int main() {
    int n,r;
    int a[1000], top = 0,base = 0;
    scanf("%d%d", &n,&r);
    if(n==0)
        printf("%d\n", n);
    else {
        while (n) {
            a[top] = n % r;
            n /= r;
            top++;
        }
        while (top!=base) {
            top--;
            printf("%d", a[top]);
        }
    }
    return 0;
}

数据结构实验之栈与队列二：一般算术表达式转换成后缀式

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

Input

输入一个算术表达式，以‘#’字符作为结束标志。

Output

输出该表达式转换所得到的后缀式。

Sample Input

a*b+(c-d/e)*f#

Sample Output

ab*cde/-f*+

Reference Code

#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, top = -1;
    char exp[1000], str[1000], ch;
    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)
            {
                exp[i++] = str[top];
                top--;
                if (str[top] == '(')
                {
                    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;
}

数据结构实验之栈与队列三：后缀式求值

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。

Input

输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。

Output

求该后缀式所对应的算术表达式的值，并输出之。

Sample Input

59*684/-3*+#

Sample Output

Hint

基本操作数都是一位正整数!

Reference Code

#include <stdio.h>
#include <string.h>
int main()
{
    char s;
    int top = 0, stack[1000];
    while (scanf("%c", &s), s != '#')
    {
        if (s >= '0' && s <= '9')
        {
            stack[++top] = s - '0';
        }
        else if (s == '+' || s == '-' || s == '*' || s == '/')
        {
            if (s == '+')
            {
                stack[top - 1] = stack[top - 1] + stack[top];
                top--;
            }
            if (s == '-')
            {
                stack[top - 1] = stack[top - 1] - stack[top];
                top--;
            }
            if (s == '*')
            {
                stack[top - 1] = stack[top - 1] * stack[top];
                top--;
            }
            if (s == '/')
            {
                stack[top - 1] = stack[top - 1] / stack[top];
                top--;
            }
        }
    }
    printf("%d\n", stack[top]);
    return 0;
}

数据结构实验之栈与队列四：括号匹配

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。

Input

输入数据有多组，处理到文件结束。

Output

如果匹配就输出“yes”，不匹配输出“no”

Sample Input

sin(20+10)
{[}]

Sample Output

yes
no

Reference Code

#include <stdio.h>
#include <string.h>
int main()
{
    char a[110];
    char s[110];
    while (gets(a))
    {
        int top = 0, base = 0;
        int i, len = strlen(a);
        for (i = 0; i < len; i++)
        {
            if (a[i] == '(' || a[i] == '[' || a[i] == '{')
            {
                s[top++] = a[i];
            }
            else if (a[i] == ')' || a[i] == ']' || a[i] == '}')
            {
                if (s[top - 1] + 1 == a[i] || s[top - 1] + 2 == a[i])
                {
                    top--;
                }
                else
                {
                    break;
                }
            }
        }
        if (top == base && i == len)
        {
            printf("yes\n");
        }
        else
        {
            printf("no\n");
        }
    }
    return 0;
}

数据结构实验之栈与队列五：下一较大值（一）

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem 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

Sample Output

12-->20
20-->-1
15-->18
18-->-1

20-->25
15-->25
25-->30
30-->-1
6-->-1

Hint

本题的数据量小、限时要求低，可以不用栈来完成。

Reference Code

#include <stdio.h>
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int i, j, n, a[1000], b[1000];
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        int k = 0;
        for (i = 0; i < n - 1; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if (a[j] > a[i])
                {
                    b[k] = a[j];
                    k++;
                    break;
                }
                else if (j == n - 1 && a[j] <= a[i])
                {
                    b[k] = -1;
                    k++;
                }
            }
        }
        b[n - 1] = -1;
        for (i = 0; i < n; i++)
            printf("%d-->%d\n", a[i], b[i]);
        printf("\n");
    }
    return 0;
}

数据结构实验之栈与队列六：下一较大值（二）

Time Limit: 150 ms Memory Limit: 8000 KiB

Problem 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

Sample Output

12-->20
20-->-1
15-->18
18-->-1

20-->25
15-->25
25-->30
30-->-1
6-->-1

Hint

本题数据量大、限时要求高，须借助栈来完成。

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[400001];
int c[400001], b[400001];
int main()
{
    int top = 0, i, t, n;
    scanf("%d", &t);
    while (t--)
    {
        top = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        b[n-1] = -1;
        c[++top] = a[n-1];
        for (i = n - 2; i >= 0; i--)
        {
            if (a[i] < c[top])
            {
                b[i] = c[top];
                c[++top] = a[i];
            }
            else
            {
                while (a[i] >= c[top] && top > 0)
                {
                    top--;
                }
                if (top == 0)
                {
                    b[i] = -1;
                    c[++top] = a[i];
                }
                else
                {
                    b[i] = c[top];
                    c[++top] = a[i];
                }
            }
        }
        for (i = 0; i < n; i++)
        {
            printf("%d-->%d\n", a[i], b[i]);
        }
        if (t != 0)
        {
            printf("\n");
        }
    }
    return 0;
}

数据结构实验之栈与队列七：出栈序列判定

Time Limit: 30 ms Memory Limit: 1000 KiB

Problem 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

Sample Output

yes
no

Reference Code

#include <stdio.h>
#define MaxNum 10005
int main()
{
    int n, t;
    int a[MaxNum], b[MaxNum], s[MaxNum];
    scanf("%d",&n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
    }
    scanf("%d", &t);
    while (t--)
    {
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &b[i]);
        }
        int i = 0, j = 0, top = -1;
        while (j < n)
        {
            if (a[i] == b[j])
            {
                i++;
                j++;
            }
            else if (top != -1 && s[top] == b[j])
            {
                top--;
                j++;
            }
            else if (j < n)
            {
                s[++top] = a[i];
                i++;
            }
        }
        if (top == -1)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

数据结构实验之栈与队列八：栈的基本操作

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem 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

Sample Output

Hint

建议：用串的方式（%s）读入操作字符。

Reference Code

#include <stdio.h>
#include <string.h>
int main()
{
    int t;
    scanf("%d", &t);
    int stack[100];
    while (t--)
    {
        int m, n, top = 0;
        char op[3];
        scanf("%d %d", &m, &n);
        while (n--)
        {
            scanf("%s", op);
            if (strcmp(op, "A") == 0)
            {
                if (top == 0)
                {
                    printf("E\n");
                }
                else
                {
                    printf("%d\n", stack[top - 1]);
                }
            }
            else if (strcmp(op, "P") == 0)
            {
                int k;
                scanf("%d", &k);
                if (top == m)
                {
                    printf("F\n");
                }
                else
                {
                    stack[top] = k;
                    top++;
                }
            }
            else if (strcmp(op, "O") == 0)
            {
                if (top == 0)
                {
                    printf("E\n");
                }
                else
                {
                    printf("%d\n", stack[top - 1]);
                    top--;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

数据结构实验之栈与队列九：行编辑器

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。

由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符"#"，以表示前一个字符无效；

如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符"@"，以表示当前行中的字符均无效。

如果已经在行首继续输入'#'符号无效。

Input

输入多行字符序列，行字符总数（包含退格符和退行符）不大于250。

Output

按照上述说明得到的输出。

Sample Input

whli##ilr#e(s#*s)
[email protected](*s=#++);

Sample Output

while(*s)
putchar(*s++);

Reference Code

#include <stdio.h>
int main()
{
    char str[251];
    char stack[251];
    while (scanf("%s", str) != EOF)
    {
        int top = 0, i = 0;
        while (str[i] != '\0')
        {
            if (str[i] == '#')
            {
                if (top>0)
                {
                    top--;
                }
            }
            else if (str[i] == '@')
            {
                top = 0;
            }
            else
            {
                stack[top] = str[i];
                top++;
            }
            i++;
        }
        for (i = 0; i < top; i++)
        {
            printf("%c", stack[i]);
        }
        printf("\n");
    }
    return 0;
}

数据结构实验之栈与队列十：走迷宫

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem 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

Sample Output

1
0
4

Reference Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dis[110][110];
int vis[110][110];
int m, n, cnt;
int fx[] = {0, 1, 0, -1};
int fy[] = {1, 0, -1, 0};
void dfs(int s, int e)
{
    int i;
    int u, v;
    vis[s][e] = 1;
    for (i = 0; i < 4; i++)
    {
        u = s + fx[i];
        v = e + fy[i];
        if (u >= 1 && u <= 100 && v >= 1 && v <= 100)
        {
            if (!vis[u][v] && !dis[u][v])
            {
                if (u == m && v == n)
                    cnt++;
                else
                    dfs(u, v);
            }
        }
    }
    vis[s][e] = 0;
}
int main()
{
    int t, i, j;
    scanf("%d", &t);
    while (t--)
    {
        cnt = 0;
        memset(dis, 1, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        scanf("%d %d", &m, &n);
        for (i = 1; i <= m; i++)
            for (j = 1; j <= n; j++)
                scanf("%d", &dis[i][j]);
        dfs(1, 1);
        printf("%d\n", cnt);
    }
    return 0;
}

数据结构实验之栈与队列十一：refresh的停车场

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem 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

Sample Output

18353365558
18353364208

Reference Code

#include<stdio.h>
#include<string.h>

int main()
{
    int n,m,i,j,flag;
    int top,top1;
    char park[200000][20],op[20],road[200000][20],d[20];
    while(scanf("%d%d",&m,&n) != EOF)
    {
        flag = 0;top=0,top1=0;
        for(i = 0;i < n;i++)
        {
            scanf("%s",op);
            if(strcmp("Add",op) == 0)
            {
                scanf("%s",d);
                if(top < m)
                {
                    top++;
                    strcpy(park[top],d);
                }
                else
                {
                    top1++;
                    strcpy(road[top1],d);
                }

            }
            if(strcmp("Del",op) == 0)
            {
                if(top<1)
                {
                    flag = 1;
                }
                else
                {
                    if(top1>0)
                    {
                        strcpy(park[top],road[1]);
                        for(j = 1;j < top1;j++)
                        {
                            strcpy(road[j],road[j+1]);
                        }
                        top1--;
                    }
                    else
                    top--;
                }
            }
            if(strcmp("Out",op) == 0)
            {
                if(top1 < 1)
                    flag = 1;
                else
                {
                for(j = 1;j < top1;j++)
                {
                    strcpy(road[j],road[j+1]);
                }
                top1--;
                }
            }
        }
        if(flag)
        {
            printf("Error\n");
        }
        else
        {
            for(i = top;i >= 1;i--)
            {
                printf("%s\n",park[i]);
            }
        }
    }
    return 0;
}

数据结构实验之串一：KMP简单应用

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定两个字符串string1和string2，判断string2是否为string1的子串。

Input

输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。

Output

对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。

Sample Input

abc
a
123456
45
abc
ddd

Sample Output

1
4
-1

Reference Code

#include<stdio.h>
#include<string.h>
void get_next(char *t,int *next)
{
    int len = strlen(t);
    int i = 0, j = -1;
    next[i] = j;
    while (i<len-1)
    {
        if(j==-1||t[i]==t[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

int kmp(char *s,char *t,int *next)
{
    int len1 = strlen(s), len2 = strlen(t);
    int i = 0, j = 0;
    while (i<len1&&j<len2)
    {
        if (j==-1||s[i]==t[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j>=len2)
        return i - len2 + 1;
    return -1;
}

int main()
{
    char s[1000000], t[1000000];
    int next[1000000];
    while (scanf("%s",s)!=EOF)
    {
        scanf("%s", t);
        get_next(t, next);
        printf("%d\n", kmp(s, t, next));
    }
    return 0;
}

数据结构实验之串三：KMP应用

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

有n个小朋友，每个小朋友手里有一些糖块，现在这些小朋友排成一排，编号是由1到n。现在给出m个数，能不能唯一的确定一对值l和r(l <= r)，使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数？

Input

首先输入一个整数n，代表有n个小朋友。下一行输入n个数，分别代表每个小朋友手里糖的数量。

之后再输入一个整数m，代表下面有m个数。下一行输入这m个数。

Output

如果能唯一的确定一对l,r的值，那么输出这两个值，否则输出-1

Sample Input

Sample Output

2 4

Reference Code

#include <stdio.h>
#include <stdlib.h>
int a[1100000], b[1100000];
int next[1100000];
void getnext(int b[], int m)
{
    int i = 0, j = -1;
    next[0] = -1;
    while (i < m)
    {
        if (j == -1 || b[i] == b[j])
        {
            i++;
            j++;
            if (b[i] != b[j])
                next[i] = j;
            else
                next[i] = next[j];
        }
        else
            j = next[j];
    }
}

int kmp(int a[], int b[], int n, int m, int p)
{
    int i = p, j = 0;
    while (i < n && j < m)
    {
        if (j == -1 || a[i] == b[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if (j == m)
        return i - j + 1;
    else
        return -1;
}

int main()
{
    int i, n, m, x, y;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d", &b[i]);
    }
    getnext(b, m);
    x = kmp(a, b, n, m, 0);
    if (x == -1)
        printf("-1\n");
    else
    {
        y = kmp(a, b, n, m, x);
        if (y == -1)
            printf("%d %d\n", x, x + m - 1);
        else
            printf("-1\n");
    }
    return 0;
}