数据结构考研讲义.docx

PAGE \* MERGEFORMAT PAGE \* MERGEFORMAT 1 目录 TOC \o 1-3 \h \u ,N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( , e ); }} 2..表达式求值 表达式求值是程序设计语言编译中一个最基本的问题，它的实现也是需要栈的加入。下面的算法是由运算符优先法对表达式求值。在此仅限于讨论只含二目运算符的算术表达式。 （ 1）中缀表达式求值： 中缀表达式：每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括： + 、- 、 *、 /、 %、 ^（乘方）和括号（）。 设运算规则为： ．运算符的优先级为：（） —— ^ ——＊、 /、 %—— +、 - ； ．有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行； ．乘方连续出现时先算最右面的。 表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^（ 4+2*2-１*3） -5”,它的的求值过程为：自左向右扫描表达式，当扫描到 3*2 时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：需要两个栈：对象栈 s1 和运算符栈 s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从运算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符。 中缀表达式表达式 “3*2^（ 4+2*2-１*3） -5”求值过程中两个栈的状态情况见图所示。 图 中缀表达式 3*2^（ 4+2*2-1*3） -5 的求值过程 为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不在引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。 中缀表达式“3*2^（ 4+2*2-1*3） -5 ”的后缀表达式为： “32422*+13*-^*5-”。 （ 2）后缀表达式求值 计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。 （ 3） 中缀表达式转换成后缀表达式： 将中缀表达式转化为后缀表达示和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组 A 中，转换后的后缀表达式存储在字符数组 B 中。具体做法：遇到运算对象顺序向存储后缀表达式的 B 数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入 B 中存放。具体算法在此不再赘述。 3．栈与递归 在高级语言编制的程序中，调用函数与被调用函数之间的链接和信息交换必须通过栈进行。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事: （ 1）将所有的实在参数、返回地址等信息传递给被调用函数保存; （ 2）为被调用函数的局部变量分配存储区; （ 3）将控制转移到被调用函数的入口。 从被调用函数返回调用函数之前，应该完成: （ 1）保存被调函数的计算结果; （ 2）释放被调函数的数据区; （ 3）依照被调函数保存的返回地址将控制转移到调用函数。 多个函数嵌套调用的规则是：后调用先返回，此时的内存管理实行“栈式管理”。 递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已。在每次调用时系统将属于各个递归层次的信息组成一个活动记录（ ActivaTion Record），这个记录中包含着本层调用的实参、返回地址、局部变量等信息，并将这个活动记录保存在系统的“递归工作栈”中，每当递归调用一次，就要在栈顶为过程建立一个新的活动记录，一旦本次调用结束，则将栈顶活动记录出栈，根据获得的返回地址信息返回到本次的调用处。 将递归程序转化为非递归程序时常使用栈来实现。  2.2 队列 2.2.1 队列的定义及基本运算 栈是一种后进先出的数据结构，在实际问题中还经常使用一种“先进先出”的数据结构：即插入在表一端进行，而删除在表的另一端进行，将这种数据结构称为队或队列， 把允许插入的一端叫队尾(rear) ；把允许删除的一端叫队头(front)。 2.2.2 队列的存储实现及运算实现