精华内容
下载资源
问答
  • 设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。 A 5 1 2 3 4 B 4 5 1 3 2 C 4 3 1 2 5 D 3 2 1 5 4 分析: A 1234 比5先入 后出但没有逆序 错误 B 123比45先入 后出没有逆序 变成...

    一句话,先入后出必逆序,违反这个规则的都是错误序列。

    例一:
    设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。

    A 5 1 2 3 4
    B 4 5 1 3 2
    C 4 3 1 2 5
    D 3 2 1 5 4
    分析:
    A 1234 比5先入 后出但没有逆序 错误
    B 123比45先入 后出没有逆序 变成了132 错误
    C 12先入 后出没有逆序 错误
    D 正确
    D
    例二:
    有六个元素6,5,4,3,2,1的顺序进栈,问下列( )不是合法的出栈序列?
    A 543612

    B453126

    C 346521

    D 234156
    分析:
    C 65比34先入 后出没有逆序 错误
    C

    展开全文
  • 2、判断全排列是否可以是对应序列的满足栈规则的输出 #include #include using namespace std; #include bool isstack(vector in, vector out){  bool res=true;  if(in.size()==out.size()){  stack...

    1、列出全排列

    2、判断全排列是否可以是对应序列的满足栈规则的输出

    #include<iostream>
    #include<stack>
    using namespace std;
    #include<vector>


    bool isstack(vector<int> in, vector<int> out){
        bool res=true;
        if(in.size()==out.size()){
            stack<int> help;
            int j=0;
            for(int i=0;i<out.size();i++){
                if(!help.empty()&&help.top()==out[i]){
                    help.pop();
                }
                else{
                    bool find=false;
                    for(;j<in.size();j++){
                        help.push(in[j]);
                        if(out[i]==in[j]){
                            find=true;
                            j++;
                            break;
                        }
                    }
                    if(!find){
                        res=false;
                        break;
                    }
                    else{
                        help.pop();
                    }
                }
            }
        }
        return res;
    }


    void quan(vector<int> in, vector<int> vec, int start){
        if(start==vec.size()&&isstack(in,vec)){
            for(int i=0;i<vec.size()-1;i++){
                cout<<vec[i]<<" ";
            }
            cout<<vec[vec.size()-1];
            cout<<endl;
        }
        else{
            for(int i=start;i<vec.size();i++){
                int temp=vec[i];
                vec[i]=vec[start];
                vec[start]=temp;
                
                quan(in,vec,start+1);
                
                temp=vec[i];
                vec[i]=vec[start];
                vec[start]=temp;
            }
        }
    }


    int main(){
    //int a[3]={1,2,3};
    //int b[3]={3,1,2};
    //vector<int> aa(a,a+3);
    //vector<int> bb(b,b+3);
    //cout<<isstack(aa,bb);


        int n;
        int x;
        while(cin>>n){
            vector<int> in;
            for(int i=0;i<n;i++){
                cin>>x;
                in.push_back(x);
                
            }
            vector<int> temp=in;
            quan(in,temp,0);
        }
    system("pause");
        return 0;
    }

    展开全文
  • 其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。 比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个...
    题目:输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。
    

    比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列:push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

    //判断输入输出是否符合栈的规则
    #include <iostream>
    #include <stack>
    using namespace std;
    bool isstack(int *pushstr,int *popstr,int length)
    {
        
    	if (pushstr==nullptr||popstr==nullptr||length<=0)
    	{
    		return false;
    	}
    	bool ismstack=false;
    	stack<int> stackdata;//辅助栈
    	int *m_nextpush=pushstr;//输入栈中的数据
    	int *m_nextpop=popstr;//输出栈中的数据
    	stackdata.push(*m_nextpush);//给辅助栈一个初值
    	while (m_nextpop-popstr<length)
    	{
    		//判断栈顶元素是否与输出数组中的数相等,不等的话则继续输入
    		while (*m_nextpop!=stackdata.top())
    		{
    			if (m_nextpush-pushstr<length-1)
    			{
    				m_nextpush++;
    				stackdata.push(*m_nextpush);
    			}
    			//输入数组已经全部输入进去
    			else
    			{
    				m_nextpush==nullptr;
    				break;
    			}	
    		}
    		//若与栈顶元素相等,将栈顶元素pop出去,表示已经输出了一个数,输出数组指针+1,指向下一个输出的数,
    		if (*m_nextpop==stackdata.top())
    		{
    			stackdata.pop();
    			m_nextpop++;
    		}
    		else
    		{
    			break;
    		}
    	}
    	//当输出数组中所有的数都已经输出后,辅助栈的为空时则是正确的
    	if (stackdata.empty()&&m_nextpop-popstr==length)
    	{
    		ismstack=true;
    	}
    	return ismstack;
    }
    int main()
    {
    	int m_push[5]={1,2,3,4,5};
    	int m_pop[5]={4,5,3,2,1};
    	bool c=false;
    	c=isstack(m_push,m_pop,5);
    	if (c==true)
    	{
    		cout<<"Yes"<<endl;
    	}
    	else
    	{
    		cout<<"No"<<endl;
    	}
    	return 0;
    }


    展开全文
  • 初始化共享栈的基本操作:入栈共享栈的基本操作:出栈链栈的实现链栈的基本操作接口链栈的基本操作初始化入栈出栈取栈顶元素几点说明栈的应用键盘输入字符序列的逆置输出数制转换问题描述样例:把十进制数159转换成...

    双向顺序栈

    双向栈在一维数组中的实现
    • 栈的共享中最常见的是两栈的共享。
    • 具体做法是:
      对两栈共享情况来说,将两个栈底分别设在两端,两个栈顶指针top1和top2相对中间位置动态移动,两个栈之间的分界线是不定的。

    在这里插入图片描述

    栈的结构体定义
    Typedef struct
    {
        Elemtype stack[MAXNUM];
        int  lefttop;     /*左栈栈顶位置指示器*/
        int  righttop;  /*右栈栈顶位置指示器*/
    } dupsqstack;
    

    左栈入栈时,栈顶指针加1,右栈入栈时,栈顶指针减1。
    在这里插入图片描述

    识别左右栈
    为了识别左右栈,必须另外设定标志:
    char status;
    status=’L’;  /*左栈*/
    status=’R’;  /*右栈*/
    
    判断栈满
    判断栈满的条件为:
    s->lefttop+1= =s->rigthtop;
    

    在这里插入图片描述

    共享栈的基本操作:初始化
    int initDupStack(dupsqstack *s)
    {
        /*创建两个共享邻接空间的空栈由指针S指出*/
        if ((s=(dupsqstack*)malloc(sizeof(dupsqstack)))
              = =NULL) return FALSE;
        s->lefttop= -1;
        s->righttop=MAXNUM;
        return TRUE;
    } //initDupStack
    

    在这里插入图片描述

    共享栈的基本操作:入栈
    int pushDupStack(dupsqstack *s,char status,Elemtype x)
    {
         /*把数据元素x压入左栈(status=’L’)或右栈(status=’R’)*/
         if(s->lefttop+1= =s->righttop) return FALSE; /*栈满*/   
         if(status=’L’)  s->stack[++s->lefttop]=x; /*左栈进栈*/
         else if(status=’R’)  s->stack[--s->righttop]=x; /*右栈进栈*/
         else return FALSE; /*参数错误*/
         return TRUE;
    } //pushDupStack
    

    在这里插入图片描述

    共享栈的基本操作:出栈
    Elemtype  popDupStack(dupsqstack *s,char status)
    {
         /*从左栈(status=’L’)或右栈(status=’R’)退出栈顶元素*/
         if(status= =’L’)
         { 
             if (s->lefttop<0)   return NULL;  /*左栈为空*/
             else return (s->stack[s->lefttop--]);   /*左栈出栈*/ 
         }
         else if(status= =’R’)
         { 
             if (s->righttop>MAXNUM-1) return NULL;  /*右栈为空*/
             else return (s->stack[s->righttop++]);   /*右栈出栈*/
         }
         else  return NULL;  /*参数错误*/
    } //popDupStack 
    

    链栈的实现

    • 链栈的结点结构和单链表中的结点结构相同,无须重复定义。由于栈只在栈顶作插入和删除操作,因此链栈中不需要头结点,但要注意链栈中指针的方向是从栈顶指向栈底的,这正好和单链表相反。
    • 不存在栈满上溢的情况,是一种特殊的单链表;
    • 链栈是动态存储结构,无需预先分配存储空间,因此节省存储空间;
    • 入栈时,先申请一个结点的存储空间,然后修改栈顶指针;
    • 出栈时,同样也是将栈顶的后继结点作为栈顶。

    简而言是:就是入栈就是头插法,出栈就是删除头结点

    链栈的基本操作接口
    • 只需要对顺序栈的基本操作接口作两处改动,便可作为链栈的基本操作接口。
      • 初始化时不需要maxsize的参数,因为它不需要事先分配空间;
      • 在进入栈操作时不需要顾及栈的空间是否已经被填满。
    链栈的基本操作
    初始化
    void InitStack( Stack &S) 
    {
        // 构造一个空栈S
        S.top = NULL;   // 设栈顶指针的初值为“空”
        S.length = 0;      // 空栈中元素个数为0
    } // InitStack
    
    • 注意:
      • 将头指针置为空,不要忘记初始化相关的长度
    入栈

    在这里插入图片描述

    void Push( Stack &S, SElemType &e) 
    {
        // 在栈顶之上插入元素e为新的栈顶元素。
        p = new LNode;     // 建新的结点
        if( !p ) exit(1);         // 存储分配失败
        p->data = e;
        p->next = S.top;    // 链接到原来的栈顶
        S.top = p;              // 移动栈顶指针
        ++S.length;           // 栈的长度增1
    } // push
    
    • 注意:
      • 链栈的入栈就是的头插法
      • 反是申请了新的内存,就要判定申请的内存是否成功
      • 修改栈顶指针的时候,不要忘记修改栈的长度
    出栈

    在这里插入图片描述

    bool Pop( Stack &S, SElemType &e) 
    {
        // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回TRUE;
        // 否则返回FALSE。
        if( !S.top ) return FALSE; 
        else 
        {
           e = S.top->data;  // 返回栈顶元素
           q = S.top; 
           S.top = S.top->next;   // 修改栈顶指针
           --S.length;   // 栈的长度减1
           delete q;   // 释放被删除的结点空间
           return TRUE;
        } // else
    } // Pop
    
    • 注意:
      • 出栈要判定栈是否为空,进而判定传出去的值是否有意义
    取栈顶元素
    bool GetTop( Stack &S, SElemType &e) 
    {
       //若栈不空,则用e返回S的栈顶元素,
       //并返回TRUE;否则返回FALSE。
       if( !S.top ) return FALSE;
       e = S.top->data;   //返回非空栈中栈顶元素
       return TRUE;
    } // GetTop
    
    • 注意
      • 判定是否为空给,进而判定返回的值是否有意义
      • 取栈顶元素不同于出栈,不改变逻辑结构
    几点说明
    • 链栈不设头结点,没有意义,用不到
    • 链栈的空间都是离散的,都是临时申请的,不会存在栈满的情况
    • 链栈的出栈和入栈就是的插入和删除相关的结点,只需要修改指针就可完成
    • 链栈的优点:
      • 多个栈共享共享存储空间
      • 栈中的元素个数变化大,存储多个栈,链栈是栈的首选存储方式

    栈的应用

    • 键盘输入字符序列逆置输出
    • 数制转换(十转N)
    • 括弧匹配检验
    • 表达式求值
    • 迷宫求解问题
    键盘输入字符序列的逆置输出

    在这里插入图片描述

    typedef char StackEntry;
    void ReverseRead( )
    {  
          STACK S;                //定义一个栈结构S
          char ch;
          InitStack(&S);             //初始化栈
          while ((ch=getchar())!=’\n’)   //从键盘输入字符,直到输入换行符为止
              Push(&S ,ch);            //将输入的每个字符入栈
          while (!StackEmpty(S)) 
          {  //依次退栈并输出退出的字符
              Pop(&S,&ch);
              putchar(ch);
          }
          putchar(‘\n’);
    }
    
    • 分析与总结
      • 完全没想到用getchar和putchar去简化输入和输出,C++中的cin有识别不了空白符,cout有需要拼接
    数制转换
    问题描述
    • 数制转换:十进制数N和其他d进制数的转换是计算机实现计算的基本问题。
    • 其中一个简单算法基于下列原理:
      N = (N div d)×d + N mod d
      其中div为整除运算,mod为求余运算
    • N除d取余:先余为低,后余为高。
    样例:把十进制数159转换成八进制数

    由十进制转换为其他进制的数的规则,可知,求得的余数的顺序为由低位到高位,而输出则是由高位到低位。因此,这正好利用栈的特点,先将求得的余数依次入栈,输出时,再将栈中的数据出栈。

    在这里插入图片描述
    在这里插入图片描述

    void conversion()
    {
        // 对于输出的任意一个非负十进制整数,打印输出与其等值的八进制数
        InitStack(S);   // 构造空栈
        cin >> N;   // 输入一个十进制数
        while( N ) 
        {
           push( S, N % 8 );   // “余数”进栈
           N = N / 8;   // 非零“商”继续运算
        } // while
        while( !StackEmpty) {  // 和“求余”所得相逆的顺序输出八进制的各位数
           Pop( S, e );
           count << e;
        } // while
    } // conversion
    
    • 分析与总结
      • 基本的思路是一致的,都是对余数进行入栈,然后出栈,就是最红的结果
    括弧匹配检验
    问题描述
    • 假设表达式允许有两种括号:圆括号和方括号,其嵌套顺序随意。

      • 假设在表达式中出现下列匹配情况,则为正确的格式。
        ([ ]())或[([ ][ ])]
      • 假设在表达式中出现下列匹配情况,则为不正确的格式。
        [( ])或([( ))或 (()])
      • 结论:检验括号是否匹配的方法可用期待的急迫程度这个概念来描述。
    • 例如,考虑下列括号序列的匹配过程:

               [  (   [   ]  [   ]   )  ]  
               1    2  3  4  5  6  7  8
      

      可见,上述括号的匹配过程正好类似于入栈和出栈的过程。

    • 针对[( ] )、( ( ) ) ) 、([ ]( ) 这三种错误匹配,从期待匹配的角度描述即为:

      • 来的右括弧不是所期待的;
      • 来的是不速之客;
      • 直到结束,也没有到来所期待的。
    • 这三种情况对应到栈的操作即为:

      • 和栈顶的左括弧不相匹配;
      • 栈中并没有左括弧等在那里;
      • 栈中还有左括弧没有等到和它相匹配的右括弧。
    算法设计思想
    • 凡是出现左括弧,则将左括号进栈。
    • 凡是出现右括弧,首先检查栈是否空。如果栈空,则表明该右括弧多余,否则和栈顶元素比较,若相匹配,则左括弧出栈,否则表明不匹配。
    • 表达式检验结束时,若栈空,则表明表达式中匹配正确,否则表明左括弧有余。
    Status matching(string &exp) 
    {
         // str[]中为输入的字符串,
      //利用栈来检查该字符串中的括号是否匹配
        InitStack(S); 
        int i = 1;
        while (i<=length(exp)) //对字符串中的字符逐一扫描
        {
              swith( exp[i]) 
              {
                    case(,[: 
                        Push(S,exp[i]); i++; break; 
                    case):  
                        if (NOT StackEmpty(S) && GetTop(S) = =() 
                        { Pop(S,e); i++; }  
                        else return ERROR; 
                        break; 
                    case]:  
                       if (NOT StackEmpty(S) && GetTop(S) = =[) 
                       { Pop(S,e); i++; }  
                       else return ERROR;  
                       break;
                  }  //switch
            } //while
            if (StackEmpty(S) ) return OK; 
            else return ERROR;
            DestroySTack(S);
    } //matching
    
    • 分析与总结
      • 比我的思路分析的要全面细致一点,分析方法更科学
      • 列出所有的组合可能,然后分为对的,错的
      • 然后找出所有的错的特点
    表达式求值
    问题描述
    • 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。
      • 操作数可以是常数也可以是被说明为变量或常量的标识符;
      • 运算符可以分为算术运算符、关系运算符和逻辑运算符等三类;
      • 基本界限符有左右括弧和表达式结束符等。
    二元表达式的标识方法
    • 对二元表达式可以有三种不同的标识方法:

      • 中缀表达式:运算符放在两个运算对象中间。(简称中缀式)。
      • 后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。(简称后缀式或逆波兰式)。
      • 前缀表达式:同后缀式一样,不包括括号,运算符放在两个运算对象的前面。 (简称前缀式或波兰式)。
    • 在计算机中,对二元表达式可以有三种不同的标识方法:

      • 假设 Exp=S1+OP+S2
        • 第一操作数(S1),运算符(OP),第二操作数(S2)
        • 称OP+S1+S2为表达式的前缀表示法
        • 称S1+OP+S2为表达式的中缀表示法
        • 称S1+S2+OP为表达式的后缀表示法
    • 例如:若Exp=a×b + (c-d/e)×f,则它的

      • 前缀式为:+ ×ab ×-c/def
      • 中缀式为:a×b + (c-d/e)×f
      • 后缀式为:ab× cde/-f× +
    算符优先法(中缀式)
    • 根据算术四则运算的规则所确定的运算优先关系的规定来实现对表达式的编译或解释执行的。
    • 一个算术表达式是由操作数(x,y,z,…)和运算符(*,/,+,-,(,),#)组成。
    • 表达式求值必须满足算术四则运算规则:
      • 从左算到右;
      • 先乘除,后加减;
      • 先括号内,后括号外。
    运算符的优先级

    在这里插入图片描述

    运算符间的优先关系规则
    • 遵循算术四则运算规则,一般任意两个相继出现的两个算符θ1和θ2之间的优先关系至多有下面三种之一:
      • θ1<θ2,θ2的优先权高于θ1 ;
      • θ1=θ2,二者优先权相等;
      • θ1>θ2 ,θ2的优先权低于θ1。
    • 一般作为相同运算符,先出现的比后出现的优先级高;先出现的运算符优先级低于(,高于);后出现的运算符优先级高于(,低于);优先权相等的仅有(和)、#。
    • #作为表达式结束符,通常在表达式之前加一#使之成对,当出现“#”=“#”时,表明表达式求值结束,#的优先级最低。
    运算符的优先数
    • 对中缀式中出现的每一个运算符是否即刻进行运算取决于在它后面出现的运算符,如果它的优先数高或等于后面的运算,则它的运算先进行,否则就得等待在它之后出现的所有优先数高于它的运算都完成之后再进行。
    • 进行运算的算符θi是当前扫描过的运算符中优先级最高者,同时,也是到当前最后被保存的运算符,由此可见,可以利用两个栈分别保存扫描过程中遇到的操作数和运算符。
    具体实现
    • 为了实现算符优先算法,可以设定两个工作栈:

      • OPND存放操作数或运算结果,OPTR存放运算符号。
    • 算法思想:

      • 首先置操作数栈OPND为空栈,表达式的起始符#为运算符栈OPTR的栈底元素;
      • 依次读入表达式中的每个字符,
        若运算符是#或栈顶是#,结束计算,返回OPND栈顶值。
        if(是操作数)→则PUSH(OPND,操作数);
        if(是运算符)→则与OPTR栈顶元素进行比较,按优先级(规定详见上表)进行操作;
      • 直到整个表达式求值完毕(当前读入的字符和OPTR栈的栈顶元素均为#)。
    • if栈顶元素<输入运算符,则运算符压入OPTR栈,并接收下一字符;

    • if栈顶元素=运算符但≠‘#’,则脱括号(弹出左括号)并收下一字符;

    • if栈顶元素>运算符,则退栈、按栈顶计算,将结果压入OPND栈。

    • 且该未入栈的运算符要保留,继续与下一个栈顶元素比较!

    样例3*7(7-2)的表达式的求职过程

    在这里插入图片描述

    后缀表达式
    • 由于后缀表达式中没有括号,不需判别优先级,计算严格从左向右进行。故计算一个后缀式要比计算一个中缀式简单的多。

    • 分析中缀式和后缀式两者中运算符出现的次序的不同。

        例一:中缀式为 a×b/c×d-e+f     例二:中缀式为 a+b×c-d/e×f
            后缀式为 ab×c/d×e-f+           后缀式为abc×+de/f×-
      
    • 例一中缀式中运算符出现的先后次序恰为运算的顺序,自然在后缀式中它们出现的次序和原表达式相同。但例二中运算符出现的先后次序不应该是它的运算顺序。按照算术运算规则,先出现的加法应在它之后出现的乘法完成之后进行,并应该在后面出现的减法之前进行;同理,后面一个乘法应后于在它之前出现的除法进行,而先于在它之前的减法进行。

    后缀式的运算规则
    • 运算符在式中出现的顺序恰为表达式的运算顺序。
      • 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。
        • 若将原表达式转换成它的后缀式,那么就可以按后缀式中运算符出现的先后次序来对表达式进行运算了。
      • 可以用两句话来归纳后缀式的求值规则:
        • 先找运算符,后找操作数。
    从中缀表达式得后缀表达式得规则
    • 设立运算符栈;
    • 设表达式的结束符为#,预设运算符栈的栈底为#;
    • 若当前字符是操作数,则直接发送给后缀式;
    • 若当前字符为运算符且优先数大于栈顶运算符,则进栈,否则退出栈顶运算符发送给后缀式;
    • 若当前字符是结束符,则自栈顶至栈底依次将栈中所有运算符发送给后缀式;
    • 若当前字符为界限符(时,总是将它进栈;
    • 若当前字符为界限符)时,将靠近栈顶的第一个左括号(上面的运算符全部依次弹出,发送给后缀式,再丢弃左括号 ( 。
    具体样例A+(B-C/D)XE

    在这里插入图片描述
    在这里插入图片描述

    具体算法
    void transform(char suffix[], char exp[] ) 
    {  // 从合法的表达式字符串 exp 求得其相应的后缀式 suffix  
    	InitStack(S); 
    	Push(S, # );  
    	p = exp; ch = *p;     
    	while (!StackEmpty(S)) {       
            if (!IN(ch, OP)) Pass( suffix, ch); // 直接发送给后缀式    
            else 
           {      
           		switch (ch) 
                {     
                	case(: 
                		Push(S, ch); 
                		break;     
                	case): {      
                		Pop(S, c);      
                		while (c!=()      
                		{ 
                			Pass( suffix, c); 
                			Pop(S, c) } //while  
                			break;}
                	default : { 
                	      while(!Gettop(S, c) && ( precede(c,ch)))      
                	      { 
                             	Pass( suffix, c); 
                             	Pop(S, c); 
                        	} //while        
                        	if ( ch!= ‘#’ ) Push( S, ch);         				break;        
                        	} // case default      
                        } // switch    
                     } // else     
                     if ( ch!= # ) { p++; ch = *p; }
              } // while
         } // transform
                		    														   			     
    
    后缀式得运算过程
    • 对后缀式从左向右扫描,遇见操作数则暂时保存,遇见运算符即可进行运算。
    • 此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数,并且先出现的是第一操作数,后出现的是第二操作数。
    • 由此可见:在运算过程中保存操作数的结构应该是个栈。
      在这里插入图片描述
    运用后缀式进行计算
    • 建立一个栈S。
    • 从左向右读后缀式,读到数字就将它转换为数值压入栈中,读到运算符则从栈中依次弹出两个数分别到Y和X,然后以X运算符Y的形式计算出结果,再压入栈S中。
    • 如果后缀式未读完,就重复上面过程,最后输出栈顶的数值为结束。

    在这里插入图片描述

    迷宫求解问题
    问题描述
    • 迷宫求解问题:求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。
    • 在计算机中可以用下页图所示的方块图表示迷宫。
      • 图中的空白方块为通道;
      • 图中的斜线方块为墙;
      • 所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

    在这里插入图片描述

    算法的基本的思想
    • 探索到出口的路径,具有递归性质:
      • 若当前位置是出口,则问题已解决;
      • 若当前位置不可通,则探索失败;
      • 向可行的方向走一步,从那里出发探索到出口的路径。
    • 本问题的特点:
      • 在每个位置上可能有多个可行选择,有分支,需要逐一试探;
      • 只需要找到一条路经(而不是所有可能路径)。
    • 要解决这个问题,需要:
      • 为问题找一种数据表示;
      • 一种确定可行方向的方式;
      • 防止出现兜圈子的情况(设法纪录已试探过的位置)。

    在这里插入图片描述

    算法的基本的思想(回溯法)
    • 从入口出发,采用试探方法,搜索到目标点(出口)的路径,遇到出口则成功结束。
    • 遇到分支点时选一个方向向前探索,这时需纪录当时的分支点和在这里已试探过的分支(和尚未试探过的分支)。
    • 若遇到死路(所有方向都不能走或已试探过),就退回前一分支点,换一方向再探索。直到找到目标,或者所有可能通路都探索到为止。这类方法称为回溯法。
    • 通过栈来保存分支点的信息
      • 每次回退(回溯)时总是去考虑最近纪录的那个分支点,如果
      • 最近分支点已经没有其它选择,就把它删除;
      • 纪录和删除具有后进先出性质,可以用栈保存分支点信息;
      • 遇到分支点将相关信息压入栈,删除分支点时将它弹出。
    迷宫问题算法框架
    入口点相关信息(位置和方向)入栈;
    While(栈不空){
       取栈顶元素作为当前点和方向(并弹出栈顶)while(当前点还存在未试探的方向){
           求下一点的位置(g,h)if(maze[g][h]是出口){
               输出路径并return}
           if(maze[g][h]==0){ //可前进
              当前点和方向入栈;
              标记maze[g][h]; 
              把(g,h)作为当前点;
           }
       }
    } //while(栈不空); 栈空则说明没有路径存在
    
    

    栈中元素需要纪录走过的位置和已经做过的方向选择。包括三项,分别记录位置的行、列坐标,以及在该位置已选的方向,4个方向编码为0、1、2、3(direction数组的下标值),记录已试探过的方向的最大下标。

    算法使用顺序栈,栈中元素的说明如下:

    struct  NodeMaze
    { 
        int  x,y,d;  //当前位置(x,y)和已试探方向的最大下标d
     } DataType;
    

    所有经过位置都入栈。

    算法伪代码

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 判断一个按从小到大输入栈的序列是否为栈的输出 规则为,在数 n 的后面(n > 2), 后1 ,2,3 ,n-1的排列得是降序 数的排列得是降序 例如进栈的顺序是1234 那么 4 2 3 1 是不可能的 因为 在 4 的后面 1,2,3 这三...
  • //其实就是一个深度优先搜索,题目的规则就是在某一个时间你可以选择执行入栈或出栈,出栈所组成这些序列就是合法的栈输出 #include&lt;iostream&gt; #include&lt;stack&gt; using namespace std;...
  • 我们都知道一维数组可以在栈和队列中进行存入和取出操作,并且由于各自的特殊性,同样的数列(1,2,3,4,5)进入栈或进入队列后,他们的输出序列是不一样的。栈的规则是先进后出(输出5,4,3,2,1,),而队列的...
  • 牛客网这一题题干如下: 输入描述: 输入包括一个合法括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含’(‘和’)’。 输出描述: ...4、每个合法括号序列都可以由以上规则生成。 例如:
  • 单词序列的反转

    2020-07-24 16:49:47
    对字符串考虑倒序输出,正好符合栈的出入规则,因此选用栈进行操作。 step.1首先,需要以空格为标记将单词分开,但是会出现一个问题,最后一个字母后面没有空格,如果不加入条件限定,会直接丢失最后一个单词。 选用...
  • 数据结构之

    2018-09-03 16:31:21
    栈的应用: 逆序输出:进制转换 括号匹配:‘(’消去一对紧邻的左右括号,不影响全局的匹配判断。 左括号入栈,遇到右括号,匹配的话出栈。栈可以考虑多种不同的括号(方括号,圆括号) 栈混洗:按照某种规则,...
  • 规则简述如下:假设参加游戏小朋友是A和B,游戏开始时候,他们得到随机纸牌序列如下: A方:[K, 8, X, K, A, 2, A, 9, 5, A] B方:[2, 7, K, 5, J, 5, Q, 6, K, 4] 其中X表示“10”,我们忽略了纸牌...
  • acwing150 括号画家

    2020-02-08 10:44:41
    本题要求是输入一个字符串,输出其中最长连续括号序列。 O(n)判断一个序列是否括号序列是很简单。但本题不适用。 这里有两种思路: 1, 对于每个字符,如果能与栈顶字符匹配,则出栈 不可话则进栈 这里...
  • 12.2.5 其他的输出流成员函数 365 12.3 流的层次:继承的简要介绍 370 12.4 随机文件存取 375 第13章 递归 384 13.1 递归void函数 384 13.1.1 一个递归调用的跟踪 386 13.1.2 递归的进一步认识 388 13.1.3 ...
  • 数据结构考博题11

    2018-02-28 18:28:38
    从这一个定义中引申出算法具有的五个特征:(1)确定性(2) 能行性 (3) 有穷性(4)有0个或1个以上的输入(5)有1个以上的输出@栈的出入栈代码实现@@#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s...
  • 编译器实现(三)

    2019-05-28 20:52:00
    1. 上下文无关文法及分析 ...分析函数将扫描程序生成记号序列作为输入,并生成语法树作为输出: 编译器中更多是多遍,后面遍将语法树作为他们输入。 语法树结构很大程度依赖语言特定语法结构...
  • 编译原理课程设计报告

    热门讨论 2008-01-08 11:56:54
    编译程序的输出结果包括词法分析后的二元式序列、变量名表、状态分析过程显示及四元式序列程序。整个编译程序分为三部分:词法分析部分、语法分析处理及四元式生成部分、输出显示部分。 编译程序需要在单词级别...
  • 浙江大学ACM题型分类

    2009-09-28 23:18:23
    1004 Anagrams by Stack 给出输入序列和若干输出序列,求栈的处理过程 stack 1005 JUGS 给两杯子,倒出n升水的最少步骤 搜索 1006 Do the Untwist  字符可加密成数字,指定数字可再加密。给出密文求原文 1007 ...
  • 堆是栈的一个组成元素 22、forward 和redirect的区别  forward是服务器请求资源,服务器直接访问目标地址的URL,把那个URL的响应内容读取过来,然后把这些内容再发给浏览器,浏览器根本不知道服务器发送的内容是从...
  • 全排列

    2021-02-14 11:53:16
    题目:给定一个没有重复数字的序列,返回其所有可能全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 分析:利用树形结构 枚举出所有可行解集合,然后利用...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    2、 按要求记录下要求的输出结果。 <br> 实验六 二叉树(二) 实验目的: 通过实验掌握下列知识: 1、继续熟悉二叉树的存储结构和遍历算法; 2、熟悉二叉搜索树的应用,并做一个小型的课程设计;...
  • 13.7.3正则表达式中一些高级规则421 13.7.4正则表达式中其他通用规则424 13.7.5使用技巧425 13.8Pattern类使用426 13.9Matcher类使用428 13.9.1匹配方法使用429 13.9.2替换方法使用430 13.9.3组...
  • 写一段程序,找出数组中第k大小数,输出数所在位置。例如{2,4,3,4,7}中,第一大数是7,位置在4。第二大、第三大数都是4,位置在1、3随便输出哪一个均可。 3.5.3 给40亿个不重复unsigned int整数,...
  • C#与.NET3.5高级程序设计第四版高清PDF中文完整版

    千次下载 热门讨论 2011-07-05 10:25:50
    19.3 入栈和出栈:cil基于栈的本质  19.4 正反向工程  19.5 cil指令和特性  19.6 net基类库、c#和cil数据类型的映射  19.7 在cil中定义成员  19.8 剖析cil操作码  19.9 使用cil构建.net程序集  19.10...
  • 2.3 数据输入与输出 36 2.3.1 I/O流 36 2.3.2 预定义插入符和提取符 36 2.3.3 简单I/O格式控制 37 2.4 算法基本控制结构 38 2.4.1 用if语句实现选择结构 39 2.4.2 多重选择结构 40 2.4.3 循环结构 43...
  • (21) 栈的基本运算有三种:入栈、退栈和______。 答:读栈顶元素#读栈顶的元素#读出栈顶元素 (22) 在面向对象方法中,信息隐蔽是通过对象的______性来实现的。 答:封装 (23) 数据流的类型有______和事务型。 答:...
  • go栈扩容和栈缩容,连续栈的缺点 golang怎么做代码优化 golang隐藏技能:怎么访问私有成员 问题排查 trace pprof 源码阅读 sync.map net/http i/o timeout , 希望你不要踩到这个net/http包的坑 mutex ...
  • (22) 下列关于栈的叙述中正确的是(D) A. 在栈中只能插入数据 B. 在栈中只能删除数据 C. 栈是先进先出的线性表 D. 栈是先进后出的线性表 (23) 下列关于队列的叙述中正确的是(C) A. 在队列中只能插入数据 B. 在队列中...

空空如也

空空如也

1 2 3 4
收藏数 64
精华内容 25
关键字:

栈的输出序列规则