精华内容
下载资源
问答
  • 学习篇--数据结构伪代码

    千次阅读 2016-12-28 13:21:50
    ADT 抽象数据类型 Data 数据元素之间的逻辑关系的定义 Operation 操作 endADT 结束符

    ADT 抽象数据类型
    Data 数据元素之间的逻辑关系的定义
    Operation 操作
    endADT 结束符

    展开全文
  • 例如下面图片上的,能编译,只是方便学习用的伪代码有必要记吗?![图片](https://img-ask.csdn.net/upload/201609/08/1473296160_353213.jpg)
  • 因此,伪代码必须结构清晰、代码简单、可读性好,并且类似自然语言。 介于自然语言与编程语言之间。  它以编程语言的书写形式指明算法的职能。相比于程序语言(例如Java, C++,C, Dephi 等等)它更类似自然语言。...

    伪代码(Pseudocode)是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。因此,伪代码必须结构清晰、代码简单、可读性好,并且类似自然语言。 介于自然语言与编程语言之间。

      它以编程语言的书写形式指明算法的职能。相比于程序语言(例如Java, C++,C, Dephi 等等)它更类似自然语言。它是半角式化、不标准的语言。我们可以将整个算法运行过程的结构用接近自然语言的形式(这里,你可以使用任何一种你熟悉的文字,中文,英文 等等,关键是你把你程序的意思表达出来)描述出来. 使用伪代码, 可以帮助我们更好的表述算法, 不用拘泥于具体的实现.

      人们在用不同的编程语言实现同一个算法时意识到,他们的实现(注意:这里是实现,不是功能)很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个(用其他编程语言编写的程序的)功能时可能很难,因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。

      当考虑算法功能(而不是其语言实现)时,伪代码常常得到应用。计算机科学在教学中通常使用虚拟码,以使得所有的程序员都能理解。

      综上,简单的说,让人便于理解的代码。不依赖于语言的,用来表示程序执行过程,而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。 

    语法规则

      例如,类Pascal语言的伪代码的语法规则是: 在伪代码中,每一条指令占一行(else if,例外)。指令后不跟任何符号(Pascal和C中语句要以分号结尾)。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性;同一模块的语句有相同的缩进量,次一级模块的语句相对与其父级模块的语句缩进。

        算法的伪代码语言在某些方面可能显得不太正规,但是给我们描述算法提供了很多方便,并且可以使我们忽略算法实现中很多麻烦的细节。通常每个算法开始时都要描述它的输入和输出,而且算法中的每一行都给编上号码,在解释算法的过程中会经常使用算法步骤中的行号来指代算法的步骤。算法的伪代码描述形式上并不是非常严格,其主要特性和通常的规定如下:
            1) 算法中出现的数组、变量可以是以下类型:整数、实数、字符、位串或指针。通常这些类型可以从算法的上下文来看是清楚的,并不需要额外加以说明。
            2) 在算法中的某些指令或子任务可以用文字来叙述,例如,"设x是A中的最大项",这里A是一个数组;或者"将x插入L中",这里L是一个链表。这样做的目的是为了避免因那些与主要问题无关的细节使算法本身杂乱无章。
            3) 算术表达式可以使用通常的算术运算符(+,-,*,/,以及表示幂的^)。逻辑表达式可以使用关系运算符=,≠,<,>,≤和≥,以及逻辑运算符与(and),或(or),非(not)。
            4) 赋值语句是如下形式的语句:a<-b 。
    这里a是变量、数组项,b是算术表达式、逻辑表达式或指针表达式。语句的含义是将b的值赋给a。
            5) 若a和b都是变量、数组项,那么记号a<->b 表示a和b的内容进行交换。
            6) goto语句具有形式
                                            goto label(goto标号)
    它将导致转向具有指定标号的语句。
            7) 条件语句有以下两种形式:
                                                if c then s或者 
                                                   if c then s
                                                      else s′
    这里c是逻辑表达式,s和s′是单一的语句或者是被括在do和end之间的语句串。对于上述两种形式,假若c为真,则s被执行一次。假若c为假,则在第一种形式中,if语句的执行就完成了,而在第二种形式中,执行s′。在所有的情况下,控制就进行到了下一个语句,除非在s或s′中的goto语句使控制转向到其它地方。
             8) 有两种循环指令:while和for。
             while语句的形式是
                                                  while c do  
                                                        s
                                                      end
    这里c是逻辑表达式,而s是由一个或更多个语句组成的语句串。当c为真时,执行s。在每一次执行s之前,c都被检查一下;假若c为假,控制就进行到紧跟在while语句后面的语句。注意,当控制第一次达到while语句时,假若c为假,则s一次也不执行。 
           for语句的形式是
                                          for var init to limit by incr do
                                                            s
                                                          end
    这里var是变量,init、limit和incr都是算术表达式,而s是由一个或多个语句组成的语句串。初始时,var被赋予init的值。假若incr≥0,则只要var≤limit,就执行s并且将incr加到var上。(假若incr<0,则只要var≥limit,就执行s并且将incr加到var上)。incr的符号不能由s来该改变。
          9) exit语句可以在通常的结束条件满足之前,被用来结束while循环或者for循环的执行。exit导致转向到紧接在包含exit的(最内层)while或者for循环后面的一个语句。
         10) return用来指出一个算法执行的终点;如果算法在最后一条指令之后结束,它通常是被省略的;它被用得最多的场合是检测到不合需要的条件时。return的后面可以紧接被括在引号的信息。
          11) 算法中的注释被括在/* */之中。诸如read和output之类的各种输入或者输出也在需要时被用到。
         

    伪代码实例

      伪代码只是像流程图一样用在程序设计的初期,帮助写出程序流程。简单的程序一般都不用写流程、写思路,但是复杂的代码,最好还是把流程写下来,总体上去考虑整个功能如何实现。写完以后不仅可以用来作为以后测试,维护的基础,还可用来与他人交流。但是,如果把全部的东西写下来必定可能会让费很多时间,那么这个时候可以采用伪代码方式。比如:

      IF 九点以前 THEN

         do 私人事务;

      ELSE 9点到18点 THEN

      工作;

      ELSE

      下班;

      END IF

      这样不但可以达到文档的效果,同时可以节约时间. 更重要的是,使结构比较清晰,表达方式更加直观.

      下面介绍一种类Pascal语言的伪代码的语法规则。

      在伪代码中,每一条指令占一行(else if 例外,),指令后不跟任何符号(Pascal和C中语句要以分号结尾);

      书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性;同一模块的语句有相同的缩进量,次一级模块的语句相对与其父级模块的语句缩进; 

      在伪代码中,通常用连续的数字或字母来标示同一即模块中的连续语句,有时也可省略标号。

      符号△后的内容表示注释;

      在伪代码中,变量名和保留字不区分大小写,这一点和Pascal相同,与C或C++不同;

      在伪代码中,变量不需声明,但变量局部于特定过程,不能不加显示的说明就使用全局变量;

      赋值语句用符号←表示,x←exp表示将exp的值赋给x,其中x是一个变量,exp是一个与x同类型的变量或表达式(该表达式的结果与x同类型);多重赋值i←j←e是将表达式e的值赋给变量i和j,这种表示与j←e和i←e等价。

      例如:

      x←y

      x←20*(y+1)

      x←y←30

      以上语句用C分别表示为:

      x = y;

      x = 20*(y+1);

      x = y = 30;

      选择语句用if-then-else来表示,并且这种if-then-else可以嵌套,与Pascal中的if-then-else没有什么区别。

      例如:

      if (Condition1)

      then [ Block 1 ]

      else if (Condition2)

      then [ Block 2 ]

      else [ Block 3 ]

      循环语句有三种:while循环、repeat-until循环和for循环,其语法均与Pascal类似,只是用缩进代替begin - end;

      例如:

      1. x ← 0

      2. y ← 0

      3. z ← 0

      4. while x < N

      1. do x ← x + 1

      2. y ← x + y

      3. for t ← 0 to 10

      1. do z ← ( z + x * y ) / 100

      2. repeat

      1. y ← y + 1

      2. z ← z - y

      3. until z < 0

      4. z ← x * y

      5. y ← y / 2

       上述语句用C或C++来描述是:

      x = y = z = 0;

      while( z < N )

      {

      x ++;

      y += x;

      for( t = 0; t < 10; t++ )

      {

      z = ( z + x * y ) / 100;

      do {

      y ++;

      z -= y;

      } while( z >= 0 );
         }
      z = x * y;

      }

      y /= 2;

      数组元素的存取有数组名后跟“[下标]”表示。例如A[j]指示数组A的第j个元素。符号“ …”用来指示数组中值的范围。

      例如:

      A[1…j]表示含元素A[1], A[2], … , A[j]的子数组;

      复合数据用对象(Object)来表示,对象由属性(attribute)和域(field)构成。域的存取是由域名后接由方括号括住的对象名表示。

      例如:

      数组可被看作是一个对象,其属性有length,表示其中元素的个数,则length[A]就表示数组A中的元素的个数。在表示数组元素和对象属性时都要用方括号,一般来说从上下文可以看出其含义。

      用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f,赋值y←x就使f[y]=f[x],更进一步,若有f[x]←3,则不仅有f[x]=3,同时有f[y]=3,换言之,在赋值y←x后,x和y指向同一个对象。

      有时,一个指针不指向任何对象,这时我们赋给他nil。

      函数和过程语法与Pascal类似。

      函数值利用 “return (函数返回值)” 语句来返回,调用方法与Pascal类似;过程用 “call 过程名”语句来调用;

      例如:

      1. x ← t + 10

      2. y ← sin(x)

      3. call CalValue(x,y)

      参数用按值传递方式传给一个过程:被调用过程接受参数的一份副本,若他对某个参数赋值,则这种变化对发出调用的过程是不可见的。当传递一个对象时,只是拷贝指向该对象的指针,而不拷贝其各个域。  

    展开全文
  • 最近在《大话数据结构》,下载了源代码一边看书一边敲,发现一些代码看不懂,觉得有问题 ``` /* 初始条件: 串S和T存在,1≤pos≤StrLength(S)+1 */ /* 操作结果: 在串S的第pos个字符之前插入串T。完全插入返回...
  • 伪代码及其实例讲解

    万次阅读 多人点赞 2012-10-29 21:07:18
    因此,伪代码必须结构清晰、代码简单、可读性好,并且类似自然语言。 介于自然语言与编程语言之间。  它以编程语言的书写形式指明算法的职能。相比于程序语言(例如Java, C++,C, Dephi 等等)它更类似自然语言。...

    伪代码(Pseudocode)是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal,C,Java,etc)实现。因此,伪代码必须结构清晰、代码简单、可读性好,并且类似自然语言。 介于自然语言与编程语言之间。

      它以编程语言的书写形式指明算法的职能。相比于程序语言(例如Java, C++,C, Dephi 等等)它更类似自然语言。它是半角式化、不标准的语言。我们可以将整个算法运行过程的结构用接近自然语言的形式(这里,你可以使用任何一种你熟悉的文字,中文,英文 等等,关键是你把你程序的意思表达出来)描述出来. 使用伪代码, 可以帮助我们更好的表述算法, 不用拘泥于具体的实现.

      人们在用不同的编程语言实现同一个算法时意识到,他们的实现(注意:这里是实现,不是功能)很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个(用其他编程语言编写的程序的)功能时可能很难,因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。

      当考虑算法功能(而不是其语言实现)时,伪代码常常得到应用。计算机科学在教学中通常使用虚拟码,以使得所有的程序员都能理解。

      综上,简单的说,让人便于理解的代码。不依赖于语言的,用来表示程序执行过程,而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。 

    语法规则

      例如,类Pascal语言的伪代码的语法规则是: 在伪代码中,每一条指令占一行(else if,例外)。指令后不跟任何符号(Pascal和C中语句要以分号结尾)。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性;同一模块的语句有相同的缩进量,次一级模块的语句相对与其父级模块的语句缩进。

        算法的伪代码语言在某些方面可能显得不太正规,但是给我们描述算法提供了很多方便,并且可以使我们忽略算法实现中很多麻烦的细节。通常每个算法开始时都要描述它的输入和输出,而且算法中的每一行都给编上号码,在解释算法的过程中会经常使用算法步骤中的行号来指代算法的步骤。算法的伪代码描述形式上并不是非常严格,其主要特性和通常的规定如下:
            1) 算法中出现的数组、变量可以是以下类型:整数、实数、字符、位串或指针。通常这些类型可以从算法的上下文来看是清楚的,并不需要额外加以说明。
            2) 在算法中的某些指令或子任务可以用文字来叙述,例如,"设x是A中的最大项",这里A是一个数组;或者"将x插入L中",这里L是一个链表。这样做的目的是为了避免因那些与主要问题无关的细节使算法本身杂乱无章。
            3) 算术表达式可以使用通常的算术运算符(+,-,*,/,以及表示幂的^)。逻辑表达式可以使用关系运算符=,≠,<,>,≤和≥,以及逻辑运算符与(and),或(or),非(not)。
            4) 赋值语句是如下形式的语句:a<-b 。
    这里a是变量、数组项,b是算术表达式、逻辑表达式或指针表达式。语句的含义是将b的值赋给a。
            5) 若a和b都是变量、数组项,那么记号a<->b 表示a和b的内容进行交换。
            6) goto语句具有形式
                                            goto label(goto标号)
    它将导致转向具有指定标号的语句。
            7) 条件语句有以下两种形式:
                                                if c then s或者 
                                                   if c then s
                                                      else s′
    这里c是逻辑表达式,s和s′是单一的语句或者是被括在do和end之间的语句串。对于上述两种形式,假若c为真,则s被执行一次。假若c为假,则在第一种形式中,if语句的执行就完成了,而在第二种形式中,执行s′。在所有的情况下,控制就进行到了下一个语句,除非在s或s′中的goto语句使控制转向到其它地方。
             8) 有两种循环指令:while和for。
             while语句的形式是
                                                  while c do  
                                                        s
                                                      end
    这里c是逻辑表达式,而s是由一个或更多个语句组成的语句串。当c为真时,执行s。在每一次执行s之前,c都被检查一下;假若c为假,控制就进行到紧跟在while语句后面的语句。注意,当控制第一次达到while语句时,假若c为假,则s一次也不执行。 
           for语句的形式是
                                          for var init to limit by incr do
                                                            s
                                                          end
    这里var是变量,init、limit和incr都是算术表达式,而s是由一个或多个语句组成的语句串。初始时,var被赋予init的值。假若incr≥0,则只要var≤limit,就执行s并且将incr加到var上。(假若incr<0,则只要var≥limit,就执行s并且将incr加到var上)。incr的符号不能由s来该改变。
          9) exit语句可以在通常的结束条件满足之前,被用来结束while循环或者for循环的执行。exit导致转向到紧接在包含exit的(最内层)while或者for循环后面的一个语句。
         10) return用来指出一个算法执行的终点;如果算法在最后一条指令之后结束,它通常是被省略的;它被用得最多的场合是检测到不合需要的条件时。return的后面可以紧接被括在引号的信息。
          11) 算法中的注释被括在/* */之中。诸如read和output之类的各种输入或者输出也在需要时被用到。
         

    伪代码实例

      伪代码只是像流程图一样用在程序设计的初期,帮助写出程序流程。简单的程序一般都不用写流程、写思路,但是复杂的代码,最好还是把流程写下来,总体上去考虑整个功能如何实现。写完以后不仅可以用来作为以后测试,维护的基础,还可用来与他人交流。但是,如果把全部的东西写下来必定可能会让费很多时间,那么这个时候可以采用伪代码方式。比如:

      IF 九点以前 THEN

         do 私人事务;

      ELSE 9点到18点 THEN

      工作;

      ELSE

      下班;

      END IF

      这样不但可以达到文档的效果,同时可以节约时间. 更重要的是,使结构比较清晰,表达方式更加直观.

      下面介绍一种类Pascal语言的伪代码的语法规则。

      在伪代码中,每一条指令占一行(else if 例外,),指令后不跟任何符号(Pascal和C中语句要以分号结尾);

      书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性;同一模块的语句有相同的缩进量,次一级模块的语句相对与其父级模块的语句缩进; 

      在伪代码中,通常用连续的数字或字母来标示同一即模块中的连续语句,有时也可省略标号。

      符号△后的内容表示注释;

      在伪代码中,变量名和保留字不区分大小写,这一点和Pascal相同,与C或C++不同;

      在伪代码中,变量不需声明,但变量局部于特定过程,不能不加显示的说明就使用全局变量;

      赋值语句用符号←表示,x←exp表示将exp的值赋给x,其中x是一个变量,exp是一个与x同类型的变量或表达式(该表达式的结果与x同类型);多重赋值i←j←e是将表达式e的值赋给变量i和j,这种表示与j←e和i←e等价。

      例如:

      x←y

      x←20*(y+1)

      x←y←30

      以上语句用C分别表示为:

      x = y;

      x = 20*(y+1);

      x = y = 30;

      选择语句用if-then-else来表示,并且这种if-then-else可以嵌套,与Pascal中的if-then-else没有什么区别。

      例如:

      if (Condition1)

      then [ Block 1 ]

      else if (Condition2)

      then [ Block 2 ]

      else [ Block 3 ]

      循环语句有三种:while循环、repeat-until循环和for循环,其语法均与Pascal类似,只是用缩进代替begin - end;

      例如:

      1. x ← 0

      2. y ← 0

      3. z ← 0

      4. while x < N

      1. do x ← x + 1

      2. y ← x + y

      3. for t ← 0 to 10

      1. do z ← ( z + x * y ) / 100

      2. repeat

      1. y ← y + 1

      2. z ← z - y

      3. until z < 0

      4. z ← x * y

      5. y ← y / 2

       上述语句用C或C++来描述是:

      x = y = z = 0;

      while( z < N )

      {

      x ++;

      y += x;

      for( t = 0; t < 10; t++ )

      {

      z = ( z + x * y ) / 100;

      do {

      y ++;

      z -= y;

      } while( z >= 0 );
         }
      z = x * y;

      }

      y /= 2;

      数组元素的存取有数组名后跟“[下标]”表示。例如A[j]指示数组A的第j个元素。符号“ …”用来指示数组中值的范围。

      例如:

      A[1…j]表示含元素A[1], A[2], … , A[j]的子数组;

      复合数据用对象(Object)来表示,对象由属性(attribute)和域(field)构成。域的存取是由域名后接由方括号括住的对象名表示。

      例如:

      数组可被看作是一个对象,其属性有length,表示其中元素的个数,则length[A]就表示数组A中的元素的个数。在表示数组元素和对象属性时都要用方括号,一般来说从上下文可以看出其含义。

      用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f,赋值y←x就使f[y]=f[x],更进一步,若有f[x]←3,则不仅有f[x]=3,同时有f[y]=3,换言之,在赋值y←x后,x和y指向同一个对象。

      有时,一个指针不指向任何对象,这时我们赋给他nil。

      函数和过程语法与Pascal类似。

      函数值利用 “return (函数返回值)” 语句来返回,调用方法与Pascal类似;过程用 “call 过程名”语句来调用;

      例如:

      1. x ← t + 10

      2. y ← sin(x)

      3. call CalValue(x,y)

      参数用按值传递方式传给一个过程:被调用过程接受参数的一份副本,若他对某个参数赋值,则这种变化对发出调用的过程是不可见的。当传递一个对象时,只是拷贝指向该对象的指针,而不拷贝其各个域。

    展开全文
  • [数据结构]——单调栈

    万次阅读 多人点赞 2019-04-09 17:23:28
    笔者在做leetcode的题(下一个出现的最大数字)时,接触到了单调栈这一种数据结构,经过研究之后,发现单调栈在解决某些问题时出奇的好用,下面是对单调栈的性质和一些典型题目。 什么是单调栈? 从名字上就听的出来...

    单调栈

    笔者在做leetcode的题(下一个出现的最大数字)时,接触到了单调栈这一种数据结构,经过研究之后,发现单调栈在解决某些问题时出奇的好用,下面是对单调栈的性质和一些典型题目。
    2020年11月23日更新

    没想到文章会火,这半年来一直有读者反映文章有问题,但本人也是大四学生一直在忙秋招,没时间修改文章。今天过来重新修改了下单调栈的定义。如果有问题请接着指正,十分感谢!

    2020年4月23日更新

    感谢各位同学对笔者之前文章错误的指出,此文章写于笔者学习数据结构早期,所以有些地方由于理解不深刻以及代码不规范出现了一些偏差。由于访问量的越来越多经常收到同学们的抱怨。在这里笔者非常感谢那些认真阅读文章后指出错误的小伙伴,现在笔者已经将错误改正,如果还有问题请接着指正!!!笔者90度鞠躬感谢!!!

    什么是单调栈?

    从名字上就听的出来,单调栈中存放的数据应该是有序的,所以单调栈也分为单调递增栈单调递减栈

    • 单调递增栈:单调递增栈就是从栈底到栈顶数据是从大到小
    • 单调递减栈:单调递减栈就是从栈底到栈顶数据是从小到大

    模拟单调栈的数据push和pop

    模拟实现一个递增单调栈:

    现在有一组数10,3,7,4,12。从左到右依次入栈,则如果栈为空入栈元素值小于栈顶元素值,则入栈;否则,如果入栈则会破坏栈的单调性,则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。

    • 10入栈时,栈为空,直接入栈,栈内元素为10。

    • 3入栈时,栈顶元素10比3大,则入栈,栈内元素为10,3。

    • 7入栈时,栈顶元素3比7小,则栈顶元素出栈,此时栈顶元素为10,比7大,则7入栈,栈内元素为10,7。

    • 4入栈时,栈顶元素7比4大,则入栈,栈内元素为10,7,4。

    • 12入栈时,栈顶元素4比12小,4出栈,此时栈顶元素为7,仍比12小,栈顶元素7继续出栈,此时栈顶元素为10,仍比12小,10出栈,此时栈为空,12入栈,栈内元素为12。

    单调栈的伪代码

    stack<int> st;
    //此处一般需要给数组最后添加结束标志符,具体下面例题会有详细讲解
    for (遍历这个数组)
    {
    	if (栈空 || 栈顶元素大于等于当前比较元素)
    	{
    		入栈;
    	}
    	else
    	{
    		while (栈不为空 && 栈顶元素小于当前元素)
    		{
    			栈顶元素出栈;
    			更新结果;
    		}
    		当前数据入栈;
    	}
    }
    

    单调栈的应用

    单调栈的应用我们直接拿一些具体的题来对照应用:

    1.视野总和

    描叙:有n个人站队,所有的人全部向右看,个子高的可以看到个子低的发型,给出每个人的身高,问所有人能看到其他人发现总和是多少。
    输入:4 3 7 1
    输出:2
    解释:个子为4的可以看到个子为3的发型,个子为7可以看到个子为1的身高,所以1+1=2
    思路:观察题之后,我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字,然后将每个          结果累计就是答案,但是这里时间复杂度为O(N^2),所以我们使用单调栈来解决这个问题。

    1.设置一个单调递增的栈(栈内0~n为单调递减)
    2.当遇到大于栈顶的元素,开始更新之前不高于当前人所能看到的值
    在这里插入图片描述

    int FieldSum(vector<int>& v)
    {
    	v.push_back(INT_MAX);/这里可以理解为需要一个无限高的人挡住栈中的人,不然栈中元素最后无法完全出栈
    	stack<int> st;
    	int sum = 0;
    	for (int i = 0; i < (int)v.size(); i++)
    	{
    		if (st.empty() || v[st.top()] > v[i])//小于栈顶元素入栈
    		{
    			st.push(i);
    		}
    		else
    		{
    			while (!st.empty() && v[st.top()] <= v[i])
    			{
    				int top = st.top();//取出栈顶元素
    				st.pop();
    				sum += (i - top - 1);//这里需要多减一个1
    			}
    			st.push(i);
    		}
    	}
    	return sum;
    }
    

    2.柱状图中的最大矩形

    https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
    在这里插入图片描述
    在这里插入图片描述
    思路:当前的数字可以向两边拓展,遇到比自己大的就接着拓展,小的就停止,然后用自己的高度乘以拓展的宽度,每次都         跟新最大面积,时间复杂度同样为O(N^2),所以我们接着借助单调栈

    上面使用了单调递增栈,这里我们通过这道例题来使用一下单调递减栈

    1.设置一个单调递减的栈(栈内0~n为单调递增)
    2.当遇到小于栈顶元素的值,我们开始更新数据,因为有可能最大面积就会出现在栈中的序列里
    3.牢记栈中数据永远是有序的,这个问题比较复杂,所以读者不妨对照着代码来理解问题

    int largestRectangleArea(vector<int>& heights) {
    	heights.push_back(-1);/同理,我们希望栈中所有数据出栈,所以给数组最后添加一个负数
    	stack<int> st;
    	int ret = 0, top;
    	for (int i = 0; i < heights.size(); i++)
    	{
    		if (st.empty() || heights[st.top()] <= heights[i])
    		{
    			st.push(i);
    		}
    		else
    		{
    			while (!st.empty() && heights[st.top()] > heights[i])
    			{
    				top = st.top();
    				st.pop();
    				//i-top指的是当前矩形的宽度,heights[top]就是当前的高度
    				//再次强调栈中现在为单调递增
    				int tmp = (i - top)*heights[top];
    				if (tmp > ret)
    					ret = tmp;
    			}
    			st.push(top);
    			heights[top] = heights[i];
    		}
    	}
    	return ret;
    }
    

    很多读者不太懂下图这两句代码:
    在这里插入图片描述
    假设遇到了小于栈顶的数据,我们需要判断下图中哪个矩形更大,并且跟新数据,这里应该都可以理解,我们将图中三个数据标记为0,1,2.接着往下看
    在这里插入图片描述
    因为需要保持栈中递增的属性,所以栈中只有i一个数据:
    在这里插入图片描述
    但是对于当前元素来说下标为0,1的元素都比他大,所以那么就意味着它可以向左延申扩大矩形:像下图那样
    在这里插入图片描述
    但是我们为了保持栈中的递增属性,并且可以让i可以向左拓展,我们索性修改了i的下标,将他修改为最左边的top下标,所以当我们下次需要以他为基准获取矩形面积时就像这样
    在这里插入图片描述
    所以假设我们数组中的4个数据(实际是5个,最后一个数字用来出栈所有数据)全部访问完时:如下面的方式计算矩形
    在这里插入图片描述
    ps:如果有的同学还是不清楚,可以用自己的编译器调试一下。

    3.求最大区间

    描述:给出一组数字,求一区间,使得区间元素和乘以区间最小值最大,结果要求给出这个最大值和区间的左右端点
    输入:3 1 6 4 5 2
    输出:60
           3 5
    解释:将3到5(6+4+5)这段区间相加,将和与区间内最小元素相乘获得最大数字60
    思路:使用暴力解法求出所有区间,再求出区间的最小值相乘跟新数据,并不是一种很好的算法,所以经过上面俩题的磨         炼,此时我们应该使用一个单调递减栈

    1.设置一个单调递减的栈(栈内0~n为单调递增)
    2.当遇到小于栈顶元素的值,我们开始更新数据,因为当前遇到的值一定是当前序列最小的

    int GetMaxSequence(vector<int>& v)
    {
    	stack<int> st;
    	vector<int> vs(v.size()+1);
    	vs[0] = 0;
    	for (int i = 1; i < vs.size(); i++)
    	{
    			vs[i] = vs[i - 1] + v[i-1];
    	}
    	v.push_back(-1);
    	int top, start, end, ret = 0;
    	for (int i = 0; i < v.size(); i++)
    	{
    		if (st.empty() || v[st.top()] <= v[i])
    		{
    			st.push(i);
    		}
    		else
    		{
    			while (!st.empty() && v[st.top()] > v[i])
    			{
    				top = st.top();
    				st.pop();
    				int tmp = vs[i] - vs[top];
    				tmp = tmp * v[top];
    				if (tmp > ret)
    				{
    					ret = tmp;
    					start = top+1;
    					end = i;
    				}
    			}
    			st.push(top);
    			v[top] = v[i];//与第二题相同的道理,将当前数据的更改最左的top下标,防止出现比当前数据更小的数据
    			//这句在这道题里真的超级难理解,但是只要你有耐心相信你可以理解的
    		}
    	}
    	return ret
    }
    

    总结

    单调栈是帮助我们完成算法的一个数据结构,很多的题中还是单调栈的身影,更多需要单调栈的题就希望读者自己去发现啦,文章如果有什么问题或者建议希望广大读者们可以提出。

    展开全文
  • 算法这本书真心简洁易懂,dijstra我是课本怎么看不懂,最后这本书才懂的。真心推荐。大话数据结构工程向算法 Java实现 C实现 C++实现 普林斯顿的算法课程教材,Coursera上面有配套的在线视频。这套书不仅有...
  • 栈和队列(思想+伪代码+部分代码)

    千次阅读 2016-04-07 17:30:14
    ADT 栈(stack) Data 同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。 operation InitStack(*s):初始化操作,建立一个空栈S。 DestroyStack(*s):若栈存在,则销毁它。...GetTop(s,*e):若栈空,用
  • 强化学习算法伪代码对比

    千次阅读 2020-03-29 22:14:30
    2、下一状态的动作选取使用的是e-greedy算法,因此产生数据的策略(e-greedy)和迭代模型的策略(贪心:选取最大动作价值)不同,属于off-policy SARSA: 1、在迭代模型时Q-learning算法目标值的计算是选取e-greedy...
  • 数据结构教材推荐

    万次阅读 2018-06-03 12:59:09
    目前主流的教材有《算法导论》,《数据结构》——严蔚敏 和《数据结构教程{第5版}》...严老师的书我个人认为适合基础较好的同学研读学习,因为这本书的代码是伪代码能直接在编译器上面编译通过, 这就要求你...
  • 数据结构,是对大量程序编写经验的总结。 一些程序,处理的数据用数组、链表存储;一些数据比如组织机构、家谱数据、硬盘文件组织等,要用树形结构处理;一些数据,比如地图等,要用图形结构处理。 因此,会了线性...
  • 清华大学严蔚敏老师的《数据结构(C语言版)》以其严谨被奉为经典,我是从其Pascal版一路追着买到C语言版,一直觉得这本书理论功力深厚,是不可多得的数据结构教材。但其编写过程中为避免太过拘泥于具体语言细节,...
  • Java数据结构与算法入门

    万次阅读 多人点赞 2018-04-29 11:53:50
    第一部分:Java数据结构要理解Java数据结构,必须能清楚何为数据结构数据结构:Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。而各数据元素之间的相互关系,又...
  • 数据结构学习与应用

    千次阅读 2020-11-08 20:48:06
    严蔚敏奶奶的数据结构更是一头雾水????(不光我,还有我宿舍的,我专业的绝大部分。。。)从头到尾晦涩难懂的伪代码,让编程更加抽象。哎,编程实战,力倍而功半。 当然不是说二老的不好,毕竟二老是
  • 算法与数据结构书籍由浅入深: 闲暇拓展知识面: 《算法帝国》:文科生也可以看懂 《数学之美》 《算法之美》 入门书:(有感性认识) 《算法图解》200页 《大话数据结构》400页 《数据结构和算法分析》 ...
  • 数据结构中的二级指针和引用

    千次阅读 2017-01-05 15:45:49
    最近在复习《数据结构与算法》方面的知识,但是绝大多数数据结构的书籍都是以伪代码/类C语言的形式来描述算法的,当然也有少数C语言的版本。但是在C语言的算法描述中,由于C语言没有像C++一样的引用变量,因此出现了...
  • 数据结构

    千次阅读 2012-03-03 23:03:10
    数据结构知识点总结整理 0、常考基础必知必会 A. 排序:排序有几种,各种排序的比较,哪些排序是稳定的,快排的算法; B. 查找:哈希查找、二叉树查找、折半查找的对比,哈希映射和哈希表的区别? C. 链表...
  • C语言数据结构 链表的合并

    千次阅读 2017-03-02 01:04:01
    今天复习了一下数据结构 发现了一伪代码是这么写的 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素 递增排列的链表A 和B 合并为C,且C 中元素递减排列,使用原空间 { pa=A->next;pb=B->next;...
  • 数据结构实验报告

    万次阅读 多人点赞 2019-01-12 16:22:02
    转载请注明出处,代码可以直接用,...数据结构   实验报告书   实 验 名__数据结构实验报告  班 级___网络工程***________ 姓 名_____**______________ 学 号_____*******_______ 指导教师 *****...
  • 它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 时间复杂度为o(n^2),是一种稳定的排序算法,比较类排序算法 算法描述: 从第一个元素开始,该元素可以...
  • 数据结构----严蔚敏

    千次阅读 2009-10-14 17:08:00
    但缺点是很多都是伪代码,对编程初学者来说有一些难度,甚至有些考研的同学来这本书有很多还看不懂,并且里面也有些容易迷惑人的地方。出于对自己数据结构知识的巩固和给那些考研的同学学习这本书一个参考,我决定...
  • 数据结构之栈迷宫求解

    千次阅读 2016-09-03 15:55:33
    了解下书上的思路,不过那个伪代码写的例子怎么也看不懂。难道是因为我的是盗版  头文件  #pragma once #include #define STACK_INIT_SIZE 100 #define STACK_INCREMENT 50 const int Xrange = 12; const int...
  • 如何学好算法和数据结构之我见

    千次阅读 多人点赞 2010-10-26 21:41:00
    数据结构与算法课程是大学计算机专业的重要基础课程。考研中,数据结构也几乎是专业课之必考。在实际工作中,数据结构依然很有用。至少很多公司面试笔试也会考的。如果你数据结构知识为零,那基本上是无法从事“更有...
  • 二叉查找树的插入 如果要在二叉查找树中插入一个结点,首先要查找到结点插入的位置,然后进行插入,假设插入的结点为z的话,插入的伪代码如下: TREE-INSERT(T, z) 1 y ← NIL 2 x ← root[T] 3 while x ≠ NIL 4 ...
  • 数据结构与算法

    千次阅读 2017-05-28 08:11:18
    整理和自己总结的部分数据结构和算法。数据结构队列特点是FIFO。是一种常见的数据结构。可用链表和数组实现。 出队时,链表只需要给出链头并将链头重新指向即可,而数组则需要进行一次全数组移动的操作。 入队时,...
  • 数据结构】二叉树

    千次阅读 2015-11-13 19:01:51
    数据结构还是大二的时候学过的,当然由于是非计算机专业的学生,所以学的也怎么样,去年用c++实现了最基本的数据结构,链表/栈/队列/二叉树,三月份的时候还贴到了博客上。然而当时由于代码量不够,其实写的并...
  • 数据结构之一元多项式

    千次阅读 2014-03-20 01:05:43
    当你们按照书上的代码敲上去vc或者其他编译器时候,是不是发现无法通过,在这里提示一下各位,我们书上虽然写着数据结构(c语言版),但是这里面的伪代码涉及到了引用“&”,这是c里面没有的,而是c++的概念,因
  • 如果想写出酷炫的自定义View,理解该机制是必可少的功课。 但是发现往往在开发过程中,一动手写事件逻辑,常常出现一些无法理解的错误,如果还停留在“onTouchEvent 返回true拦截事件,返回false拦截事件”表层...
  • 数据结构复习笔记

    千次阅读 多人点赞 2020-05-30 23:46:16
    可能有些算法介绍的较为简单了,说的也不够细致,毕竟这个是面向考试才写的,只涉及了必要的考点。对于这篇文章找思路的人来说太友善,可能甚至是无用,在这里提前道歉

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,164
精华内容 7,265
关键字:

数据结构伪代码看不懂

数据结构 订阅