数据结构(严蔚敏)第3章

.第三章堆栈和队列，【课前思考】，简而言之，线性结构是数据元素的系列。必须遵循以下顺序，即n、2、1。 他们遵循“后出”的法则。 这就是本章讨论的“栈”的结构特征。 是“行列”。 在计算机程序中，伪队列的数据结构是“队列”。【学习目标】、1 .掌握堆栈和队列这两种抽象数据类型的特征，可以在适当的应用问题中正确选择。 2 .熟悉堆栈类型的两种实现方法。 3、熟悉循环队列和链队列的基本操作实现算法。 4 .理解递归算法执行中堆栈的状态变化过程。堆栈和队列是程序设计中广泛应用的两种线性数据结构，本章的学习要点是把握这两种结构的特点，使其在应用问题中得到正确应用。 【知识点】、序列堆栈、链堆栈、循环队列、链队列、【重点和难点】、【学习指南】本章主要学习如何在解决应用问题的基础上适当应用堆栈和队列，并且在堆栈和队列存储结构中实现起来很困难，但是对它们的了解很多特别要注意实现基本操作时的特殊情况，如堆满、堆满和队列满的条件及其描述方法。 本章要完成的算法设计主题包括：3.15、3.17、3.19、3.22、3.27、3.28、3.30、3.31和3.32。 其中前四个主要是练习栈的应用，后四个主要是有关队列实现方法的练习。堆栈和队列通常被称为只能在表的“端点”插入和删除的线性表。 线性代表堆栈队列Insert(L，I，x)Insert(S，n 1，x)Insert(Q，n 1，x)1in 1Delete(L，i)Delete(S，n)Delete(Q， 1)1in )，堆栈和队列是常用的两种数据类型，3.1堆栈、3.2堆栈应用、3.4队列、目录、3.3堆栈和递归实现、3.1堆栈、一、堆栈定义、堆栈(stack )作为限定性线性表表中允许插入/删除的一侧通常称为“堆栈顶点”(Top )，因此堆栈顶点的当前位置会动态变化，并由称为堆栈顶点指针的位置指示器指示。 另外，桌子的另一端是固定的，被称为堆栈底(Bottom )。 如果堆栈没有元素，则称为空堆栈。 栈的插入操作称为栈或栈，删除操作称为出栈或出栈。 插入：首先将堆栈元素放置在堆栈的底部，最后放置的元素放置在堆栈的顶部删除：最后放置的元素首先被删除，最后放置的元素被删除。 堆栈是后推(LastInFirstOut )的线性表，简称为LIFO表。 假设、图3.1堆栈、例如一个堆栈的输入序列为a、b、c、d，则经由一个堆栈获得的输出序列是不可能的。 (A)A，b，c，D(B)D，c，b，A(C)A，c，d，B(D)D，a，b，c回答：可以简单地估计，并且不可能容易地获得d，a，b，c。 因为d先出现，所以说明a，b，c，d都在堆栈中，堆栈中的顺序为d，c，b，a，堆栈中的顺序为d，c，b，a。 这个问题的答案是d。、二、堆栈主要操作，1 .初始化堆栈： InitStack(/堆栈结构之前和之后的base值为NULLSElemType*top； /堆栈顶部指针intstacksize； SqStack； /当前分配的存储空间或简单定义如下： #defineM100intsM； inttop；图3.2序列堆栈中的输入堆栈和输出堆栈，Top指示堆栈元素的初始状态： top=-1； 空堆栈，堆栈没有元素，进入堆栈： top=top 1； stop=x； 退席： stop； top=top-1； 堆满： top=M-1； 堆栈溢出(溢出)、无法进一步堆栈(错误状态) top=-1时无法堆栈下溢(正常状态、常时控制条件)、 (1)构造空序列堆栈算法：初始化堆栈statussinitstack (sqstack )/init stack， 2 .顺序堆栈基本操作的实现如下：步骤说明：/thisprsprogistionmitinitializeastack # include # define stack _ init _ size 100 # defineestackincrement typedef struct/defineestructuresqstack () elemtype * base； SElemType*top； 堆叠大小； SqStack； intInitStack(SqStack )，(2)将顺序堆栈的堆栈要素StatusGetTop(SqStackS，smeletype)/gettop，(3)要素作为顺序堆栈算法(进入堆栈) status push (sqstack (4)弹出元素的顺序堆栈算法(返回堆栈) StatusPop(SqStack/Pop，(5)确定堆栈是否为空的IntEmpty(SqStackS)/如果堆栈为空，则返回1如果堆栈s不为空，则返回0 if(S.top=S.base)return1； /如果堆栈s为空，则为1elsereturn0； /如果堆栈s为空，则可能返回0/Emptyend，3 .堆栈的共享，如果在一个程序设计中需要使用多个相同类型的堆栈，则一个堆栈空间过小，容量溢出，另一个堆栈空间过大，大量的存储单元多个堆栈共享存储单元可以用于利用各个堆栈的存储空间。 即，通过对多个堆栈分配足够大的存储空间，多个堆栈能够补充存储空间的优势。堆叠空间： top1=0、top2=M-1； 堆栈完整： top1 1=top2，可以使用以下c语句编写两个堆栈共享存储单元： # define maxsize 100 # definitedstacksizemaxsiztypepedefstructdusqstack selemtypeded inttop1； /top1 isthepointerofdusqstacks1int top 2； /top2 isthepointerofdusqstacks2intflag； DuSqStack； /或： # define maxsize 100 structdusestack elemtype data maxsize ； inttop2； /两个堆栈的堆栈指针intflag； ，(1)2个堆栈共享存储单元的堆栈算法statusqstackpush (如果du sqstack/flag不是1，2，则errorrelse/flag是1或2，则堆栈switch (s.flag ) case 133 /元素x进入堆栈S1S.top1修正堆栈S1的堆栈指针break的case2:/标志位flag是2S.dataS.top2=x； /要素x输入堆栈S2S.top2-； /修改堆栈S2的堆栈停止指针break /switch结束返回ok； /else结束/else结束/DuSqStackPush，(2)2个堆栈共享存储单元的堆栈算法StatusDuSqStackPop(DuSqStack/要素x堆栈) /if结束，elsereturnERROR /堆栈S1为空时为ERRORbreak； case2:/标志位flag为1if(S.top2next=NULL； (b )堆栈运算status push _ l (link stack )/push _ l，(c )堆栈运算StatusPop_L(LinkStack/Pop_L， (d )堆栈元素status gettop _ l (link stack top ) s elemtype /else结束/GetTop_L，(5)判断堆栈空间intempty (link stack * top ) if (top-next=null ) return (top-next=null ) elsereturn(0) 、上课前进行复习，令n个要素的堆栈序列为P1、P2、P3、Pn，如果其输出序列为1、2、3、n、P1=3，则为P2的值() a，可能的是2B，可能的是2C，不可能的是1D，可能的是1，1，数字转换假设十进制数n要转换成d进制数，简单的转换算法是重复下一步骤，直到n等于零：卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡，void转换(intn ) 22222222222222222222222222222222226 intx； /*S创建一个算法来确定序列堆栈或链堆栈*/可卡可卡可卡可卡可卡可卡653表达式中的括号是否正确配对。设置括号堆栈并扫描表达式。 如果找到左括号(，和 )，则进入堆栈；如果找到右括号，则进入堆栈；如果找到匹配的左括号，则返回0。 如果公式扫描完成，则堆栈为空，返回1，表示括号正确匹配，否则返回0。 intcorrect(charexp，intn)charstMaxSize； inttop=-1，i=0，tag=1； while(i-1)tag=0； /*若堆栈不空闲，则*/return(tag) 、三、行编辑程序功能：接受用户从终端输入的数据和程序，存储在用户的数据区域。 算法思想：如果输入缓冲区为堆栈结构，并且每次从终端接收字符时，该字符既不是反斜线符号(# )也不是反斜线符号( )，则从堆栈顶部删除字符，如果backspace符号(# ) 算法描述如下。 voidLineEdit()InitStack(s )； ch=getchar ()； while！=EOF)/EOF是全文终结符while(ch！=EOF，5，式评价，式评价是高级语言编译的基本问题，是堆栈的典型应用例。 每个表达式都由“操作数”、“运算符”和“分隔符”组成。 操作数可以是常量，也可以是被解释为变量或常量的标识符的运算符可以分为三类：算术运算符、关系运算符和逻辑运算符。基本边界符号包括左右括号和表达式的结束符号。1.无括号算术表达式评估157348； 公式计算157348； 编程语言存在计算公式问题，这是语言编译的典型问题。 57348； (1)公式形式：由运算对象、运算符及必要的公式括号构成57348； (2)式的运算：运算需要正确的运算形式顺序。 由于某些运算符的优先级可能高于其他运算符，因此表达式不会严格从左到右。 请参见图3.5。图3.5式运算和运算符优先级，图3.6无括号运算式的处理过程，2 .运算式处理规则157348； (一)规定优先级表； 57348； (2)设定ovs (运算数堆栈)和OPTR (运算符堆栈)这两个堆栈。 57348； (3)从左到右扫描，操作数进入OVS，操作数与OPTR栈优先级进行比较：当前操作员OPTR栈，当前操作员进入OPTR栈的当前运算符OPTR栈，OVS栈，子栈，optr栈57348； 例如：实现A/BC D*E#的运算过程时的堆栈变化如图3.7所示。图3.7A/BC D*E示意性地表示运算过程中堆栈的变化状况的图，*，3 .带括号的算术式157348； 操作数为整数常数，运算符只包含加、减、乘、除4种运算符，边界符号有左右括号和公式的开始、结束符号“#”: # (7- 15 ) * (23-28/4 ) #”等。 引入表达式的开头和结尾符号非常有用。 要评估简单的算术表达式，您必须首先了解算术四则运算的规则。 也就是说，卡卡卡卡卡卡卡卡卡卡卡卡(2)首先乘除，然后加减(3)前括号内、后括号外。 可以将运算符和分隔符统称为运算符，将它们的集合命名为OPTR。 根据上述3个运算规则，在运算过程中，出现于任意2个前后的运算符1与2的优先关系必须是12、1的优先顺序高于2这3个关系之一。表3-1为了实现运算符之间的优先关系，运算符优先算法，需要使用存储运算符的optr这一工作堆，另一个称为opnd，存储操作数和运算的中间结果。算法的基本过程包括： 57348； 首先初始化操作数堆栈opnd和运算符堆栈optr，在运算符堆栈中插入表达式的开始符号 # ，按顺序读取表达式的各个字符，如果是操作数，则比较操作数堆栈opnd，如果是运算符，则比较运算符堆栈optr的堆栈顶运算符和优先级，进行如下处理57348；(1)如果栈顶运算符的优先级低于刚读入的运算符，则将刚读入的运算符放入optr栈57348； (2)堆栈顶端运算符的优先级比刚读入的运算符高时，堆栈顶端运算符发送，同时堆栈操作数堆栈opnd 2次，得到2个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推到opnd堆栈如果堆栈顶端运算符的优先级与刚读入的运算符的优先级相同，则它可以显示出已经找到左括号和右括号，并且将堆栈顶端运算符(左括号)解除堆栈。算法具体描述如下： intexpevaluation ()卡卡卡卡卡卡卡卡卡卡卡卡卡6 operator和operand分别是运算符堆栈和运算符堆栈，OPS是运算符集*/1卡卡卡卡卡卡卡卡卡卡=#)/*GetTop ()是函数值的堆栈元素*/卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡，步进操作数堆栈运算符堆栈的说明，开始，两堆栈1是操作数堆栈，2是操作数堆栈，*是运算符堆栈，3是操作