[栈和队列](3)题集_1

栈和队列的结构特性:

栈:可用线性存储结构的顺序存储和链式存储,特点是先进后出,后进先出

队列:可用线性存储结构的顺序存储和链式存储,特点是先进先出,后进后出

基础知识题

1、用栈的存储结构模拟火车进站,如果进站的车厢序列为123,则可能得到的出站车厢序列为多少?如果进站的车厢序列为123456,则能否得到435612和135426的出站序列,并请说明为什么不能得到或者如何得到(即写出以‘S’表示进站,X表示出栈操作序列)

  1. 由于栈的存储结构为先进后出,则可能得到的车厢序列为123、321、321、213、132
  2. 可能出现135426,但不可能出现435612,因为4356出栈,说明还有12在栈中,1不可能先于2出栈。
  3. 这题需要S跟X不间断的操作,画个图然后一个一个配就行,了解栈的先进后出原理就没太大问题

2、简述栈和线性表的差别

栈和线性表的差别主要是在插入和删除操作上,线性表的插入和删除是无限制,根据程序要求进行插入和删除操作,而栈则的插入操作和删除都是位于前端

3、写出下列程序段的输出结果(栈的元素类型为:SElemType为char)

void main()
{

    Stack S;
    char x, y;
    InitStack(S);
    x = 'c';
    y = 'k';
    Push(S, x);
    Push(S, 'a');
    Push(S, y);
    Pop(S, x);
    Push(S, 't');
    Push(S, x);
    Pop(S, x);
    Push(S, 's');
    whilie(!StackEmpty(S))
    {
        Pop(S, y);
        printf(y);
    }
    printf(x);
}

程序运行过程如下所示:

  • 定义一个S栈
  • 定义两个字符类型变量x,y
  • 为S栈初始化
  • 将x赋值字符c,将y赋值字符k
  • 将x进栈,此时S('c');
  • 将字符a进栈,此时S('a','c');
  • 将y进栈,此时S('k','a','c');
  • S进行出栈,传入x内,此时S('a','c'),x=‘k’;
  • 将字符t进栈,此时S('t','a','c');
  • 将x进栈,此时S('k','t','a','c');
  • S进行出栈,传入x内,此时S('t',‘a’,'c');,x='k';
  • 将字符s进行进栈,此时S('s','t','a','c');
  • 执行循环,不断从栈顶出栈,栈顶元素传入y内,打印y,循环结束够打印x
  • 最后输出结果为:stack

4、简述以下算法的功能(栈的元素类型SElemType为int)

一、

Status algol(Stack S)
{
    int i, n, A[255];
    n = 0;
    while (!StackEmpty(S))
    {
        n++;
        Pop(S, A[i]);
    };

    for (i = 1; i <= n; i++)
    {
        Push(S, A[i]);
    }
}

反转栈内元素,由于栈的特点是先进后出,程序第一个while循环的作用是将栈站内元素不断出栈传入A数组内,我们假设栈内元素为Hello

则A={H,e,l,l,o};

然后第二个循环是将数组元素按从左到右的顺序不断压入栈顶,则进栈顺序为Hello。

栈内元素从上到下来看,此时为:olleH

图解如下:

img

二、

Status algo2(Stack S, int e)
{
    Stack T;
    int d;
    InitStack(T);
    while (!StackEmpty(S))
    {
        Pop(S, d);
        if (d != e)
        {
            Push(T, D);
        }
    }
    while (!StackEmpty(T))
    {
        Pop(T, d);
        Push(S, d);
    }
}

从S栈从删除所有值为e的数。

程序首先给定了一个临时栈T,不断从S栈中取出元素去做判断,如果元素不为e,则压入T栈中,如果为e,则不压入

直到所有元素全部判断完,再将T内元素传入S中,操作结束后,此时S栈内已经没有值为e的元素,注意此算法需要改变S栈内的状态,所以用引用或指针类型。

5、假设以S和X分别表示入栈和出栈操作,则初态和终态均为栈空的入栈和出栈操作序列可以仅由S和X组成的序列,称可以操作的序列为合法序列(例如,SXSX为合法序列,SXXS为非法序列),试给出区分给定序列为合法序列或非法序列的一般准则,并证明:两个不同的合法(栈操作)序列(对同一输出序列)不可能得到相同的输出元素(注意:在此指的是元素实体,而不是值)。

这题别看题目那么长,其实挺简单, 首先题目给定的条件:初始操作为空栈,S表示压入元素到栈顶,X表示从栈顶删除元素。

  • S操作前提是栈不满
  • X操作前提是栈不空

所以合法表达式的前提就是S<=X,每进行一次X操作都必须建立在S操作后面。由于栈是后进先出的特点,则不同的合法序列对应的输出值不同,可用下列代码证明:

int main()
{
    int n = 0, x = 0;
    char ch;
    InitStack(&S);
    ch = getchar();
    while (ch != '#')
    {
        if (ch == 'S')
        {
            Push(&S,++n);
        }
        if (ch == 'X')
        {
            Pop(&S, &x);
        }
        ch = getchar();
    }

    int* p = S.base;
    while (p < S.top)
    {
        printf("%d", *p);
        p++;
    }
    system("pause");
    return 0;
}

我们测试用例SXSXS和SSXSX两个合法的操作序列,得到的结果为:

img

img

6、试证明:若借助栈由输入序列12....n得到的输出序列为p1,p2....pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形,存在着i<j<k使pj<jk<pi

假设我们输入栈中的序列为123,则出栈序列为321,按题目要求,输入栈中的是有序序列,则必然先出来的数值比后出来的数值大,只能存在i<j<k,则pk<pj<pi;

7、按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,仿表达式运算的格式,画出下列算术表达式求值时操作数和栈的运算符栈的变化过程。

碰到操作数,则进操作数栈,碰到运算符,则进算符栈。

img

8、试推导n阶Hanoi塔执行移动的次数

img

9、试将下列递推过程改写为递归过程。

void ditui(int n)
{
    int i;
    i = n;
    while (i > 1)
    {
        printf(i--);
    }
}

改写后:

void digui(int n)
{
    if (n > 1)
    {
        printf("%d ", n);
        digui(n - 1);
    }
}

10、试将下列递归程序改写为非递归过程

void digui(int *sum)
{
    int x;
    scanf_s("%d", &x);
    if (x == 0)
    {
        *sum = 0;
    }
    else
    {
        digui(sum);
        *sum += x;
    }
    printf("%d\n", *sum);
}

非递归:

void ditui(int *sum,SqStack *S)
{
    int x;
    scanf_s("%d", &x);
    while (x != 0)
    {
        Push(S, x);
        scanf_s("%d", &x);
    }

    int* p = S->top - 1;
    while (p >= S->base)
    {
        *sum += *p;
        printf("%d\n", *sum);
        p--;
    }
}

利用栈的后进先出将x的值压入栈顶,直到x为0结束,然后从栈顶不断访问并与sum相加,达到与递归一样的效果。

递归就是当x不为0的时候,不断保存这个场景,然后继续递,直到x为0的时候,再不断归回来,在归的过程中,sum的值从最后一个场景开始累加。

11、简述队列和栈这两种数据类型的相同点和差异处

队列和栈都是操作受限的线性表,差异处就是队列插入操作都在前端,删除操作在尾端,特点是先进先出,而栈是插入和删除都在前端,特点是后进先出

12、写出以下程序段的输出结果(队列中的元素类型QElemType为char)

void main()
{
    Queue Q;
    InitQueue(Q);
    char x = 'e', y = 'c';
    EnQueue(Q, 'h');
    EnQueue(Q, 'r');
    EnQueue(Q, y);
    DeQueue(Q, x);
    EnQueue(Q, x);
    DeQueue(Q, x);
    EnQueue(Q, 'a');

    while (!QueueEmpty(Q))
    {
        DeQueue(Q, y);
        printf(y);
    }
    printf(x);
}
  • 将字符h插入队列,此时Q=h
  • 将字符r插入队列,此时Q=h,r
  • 将y插入队列,此时Q=h,r,c
  • 删除操作,将值传入x,此时队列Q=r,c x=h
  • 将x插入队列,此时Q=r,c,h
  • 删除操作,将值传入x,此时队列Q=c,h x=r
  • 将字符a插入队列,此时队列Q=c,h,a
  • 循环删除操作,值传入y,打印出来。
  • 最后打印x
  • 结果为:char

13、简述下列算法的功能(栈和队列的元素类型均为int)

void algo(Queue& Q)
{
    Stack S;
    int d;
    InitStack(S);
    while (!QueueEmpty(Q))
    {
        DeQueue(Q, d);
        Push(S, d);
    }

    while (!StackEmpty(Q))
    {
        Pop(S, d);
        EnQueue(Q, d);
    }
}

利用S栈做跳板,反转队列中的元素,例如Q=Hello,则第一个循环后,栈从上到下为:olleH,然后插入队列中为olleH

14、若以1234作为双端队列的输出序列,试分别求出满足以下条件的输出序列:

  • 能由输入受限的双端队列得到,但不能由输出首先的双端队列得到的输出序列
  • 能由输出受限的双端队列打得到,但不能由输入受限的双端队列得到的输出序列
  • 即不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列

img

我们先看看 上图,可以知道

  • 输入受限就是插入受限,只能在一端进行插入,但删除缺两端都行
  • 输出受限就是删除受限,只能在一端进行删除,但是输入两端都行

这道题最主要的就是求出在栈形式下不可能输出的序列,然后一个一个去尝试,下列视频详细的解答了这道题,在这我就不放答案了。

详细解答视频

算法设计题

15、假设以顺序存储结构实现一个双向栈,即在一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点,试编写实现这个双向栈tws的三个操作:初始化initstack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法,其中i为0或1,用以分别指示设在数组两端的两个栈,并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么优缺点、

img

上图所示是一个双向栈,即在同一顺序存储空间内实现的两个栈。把两个栈的栈底分别设在顺序存储空间(如数组v[n])的两端,每个栈都有各自独立的栈底和栈顶指针。栈底位置不变。入栈时,各自的栈顶向中间伸展,仅当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺,使得每个栈的可利用空间均有可能超过n/2。这不仅减少了栈溢出的可能性,也增加了空间的利用率。因此,这种方案经常被采用。

设有两个栈S1和S2,按上图的方法共享一个数组的空间。试为此双向栈设计初始化inistack、入栈PUSH和出栈POP的算法,其中i为0或1,用以指示栈号。试写一个算法,完成对任何一个栈(S1或S2)的入栈和出栈操作。

完整算法如下所示:

#define MAX 100
#include<stdio.h>
#include<stdlib.h>
typedef int type;
typedef struct 
{
    type* Arr;
    int top1;
    int top2;
    int base1;
    int base2;
}TwsStack;

TwsStack S;

void InitStack(TwsStack* S)
{
    S->Arr = (type*)malloc(sizeof(int) * MAX);

    if (S->Arr == NULL)
    {
        exit(0);
    }

    S->base1 = 0;
    S->top1 = -1;

    S->base2 = MAX - 1;
    S->top2 = MAX;
}

void Push(TwsStack* S, int i, type x)
{

    if (S->top1 >= S->top2)
    {
        printf("栈满\n");
        exit(0);
    }
    else
    {
        switch (i)
        {
        case 0:
            S->top1++;
            S->Arr[S->top1] = x;
            break;
        case 1:
            S->top2--;
            S->Arr[S->top2] = x;
            break;
        default:
            printf("Error: type is 0 or 1");
            break;
        }
    }
}

void Pop(TwsStack* S, int i)
{
    switch (i)
    {
    case 0:
        if (S->top1 < S->base1)
        {
            printf("栈空\n");
            exit(0);
        }
        S->top1--;
        break;

    case 1:
        if (S->top2 > S->base2)
        {
            printf("栈空\n");
            exit(0);
        }
        S->top2++;
        break;
    }
}

17、试写一算法,识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’的模式的字符序列,其中序列1和序列2中都不含字符‘&’,且序列2是序列1的逆序列,例如,‘a+b&b+a’是属该模式的序列,而‘1+3&3-1’则不是。

这道题就是依次读入进去,将序列1压入堆栈,遇到&字符的时候,从栈顶取出元素与其做判断,如果判断为假,则不是,如果为真,则是。算法如下:

int NatureType()
{
    InitStack(&S);
    char ch;
    ch = getchar();
    while (ch != '@'&&ch!='&')
    {
        Push(&S, ch);
        ch = getchar();
    }
    if (ch == '&')
    {
        ch = getchar();
        while (ch != '@')
        {
            char temp;
            Pop(&S, &temp);
            if (Judge(ch, temp))
            {
                ch = getchar();
            }
            else
            {
                return 0;
            }
        }
    }
    else
    {
        return -1;
    }
    return 1;
}

运行结果如下所示:

img正确

img错误

18、试写一个判别表达式中开、闭括号是否配对出现的算法

这道题我们在看教程的时候出现过讲解,假设表达式中允许包括两种括号:圆括号和方括号,其嵌套的顺序随意,即([]())或[([][])]等正确的格式,[(])或([())或(()]均为不正确的格式。

由此,在算法中设置一个栈,每读入一个括号,若是左括号,则作为一个新的元素压入栈顶,若是右括号,则去对栈顶元素做判断,若匹配,则可以抵消,读入下一个字符,或是不合法情况。

注意:开始和结束的时候,栈都应该为空!测试代码如下所示:

int Judge(char a, char b)
{
    if ((a == '(' && b == ')') || (a == '[' && b == ']'))
    {
        return 1;
    }
    return 0;
}

int NatureType()
{
    InitStack(&S);
    char ch;
    ch = getchar();
    if (S.base == S.top)
    {
        while (ch != '@')
        {
            if (ch == '(' || ch == '[')
            {
                Push(&S, ch);
                ch = getchar();
            }
            else if (ch == ')' || ch == ']')
            {
                int temp;
                Pop(&S, &temp);
                if (Judge(temp, ch))
                {
                    ch = getchar();
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return -1;
            }
        }
        if (S.base == S.top)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return -1;
    }
}
int main()
{
    switch (NatureType())
    {
    case -1:
        printf("输入出错\n");
        system("pause");
        break;
    case 1:
        printf("true\n");
        system("pause");
        break;
    case 0:
        printf("false\n");
        system("pause");
        break;
    }
}

19、假设一个算术表达式可以包含三种括号:圆括号“(”和“)”、方括号“[”和“]”和花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用,(如...[...{...}...[...]...]...[...]...(...)...)。编写判别给定表达式这种所含括号是否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中)

这道题和18题的思路一样,我傻逼的把18题中的中开闭理解成两种括号了,这题就是上题的答案加一个花括号的判断

20、假设以二维数组g(1…m, 1…n)表示一个图像区域,g[i,j]表示该区域中点(i,j)所具颜色,其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。

这道题和之前的N皇后问题相似,这道题用DFS反而不好,耗时久,所以用DFS做比较好,可以参考PS等画图软件的染色功能,具体请看补充笔记。

补充笔记

本文链接:

https://nullcode.fun/24.html
1 + 8 =
快来做第一个评论的人吧~