数据结构讲义

《数据结构讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构雅礼朱全民数据结构常见形式多叉路口交通灯几种常见的模型比较普通线性表操作双向循环链表一般顺序表线行表的结构特性比较方案逻辑结构物理结构特点无序数组无序线性表数组差无序链表链表插入快有序数组有序线性表数组查找快有序链表链表比较平衡使用两个一维数组，一个数组中存放数据本身，另一数组中存放数据的下一个数据元素的位置。如下图所示：数组下标12345数据元素84653499109数组下标012345数据元素123450用数组实现有序表的链式结构思考题:一元多项式的加法一元多项式按升幂可表示为：Pn(x)=p0+p1x+p2x2+p3x3+…+pnxn其中p0、p1、p2……p

2、n称为该一元多项式的系数，而x的n次方称作次幂（n=0,1,2…n）。一元多项式相加的运算规则：（1）指数相同的项，对应系数相加，若和不为0，则构成“和多项式”的一项。（2）所有指数不相同的项均复抄到“和多项式”中。例如：A=2-x+x2-9x4+2x7-7x9,B=3-x2+6x5,则A+B=5-x-9x4+6x5+2x7-7x9（按升幂排列）。逻辑结构：线性表物理结构：数据运算：排序，合并同类项——指数相同，系数相加栈(Stack)只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)退栈进栈a0an

3、-1an-2topbottom双栈共享一个栈空间b[0]t[0]t[1]b[1]0maxSize-1V两个栈共享一个数组空间V[maxSize]，两个栈的栈底分别位于数组的开头和结尾；分别向中间生长。主要目的是节约空间：两个独立栈，预期的最大空间max(sizeofstack1)+max(sizeofstack2)。而双栈空间是max(sizeofstack1+sizeofstack2)。栈的应用：表达式求值栈的LIFO特性决定了它比较适合用来处理具有嵌套结构/递归结构的问题:括号匹配，表达式求值由于LIFO特性，如果一个应用中总是把前面求出的某个值和后续求出的某个值进行

4、运算得到一个新结果，并且从此之后前面求出的值就不再需要，就可以考虑使用栈来完成计算。在计算这些值的过程中，可能还需要计算一些中间结果，那么这些中间结果的计算也需要遵循这样的模式。此时可以把运算分量入栈，然后在计算结果时在栈顶获得运算分量。结果可能还需要入栈。中缀表达式a+b*(c-d)-e/f后缀表达式abcd-*+ef/-前缀表达式-+a*b–cd/ef中缀表达式中相邻两个操作符的计算次序为：优先级高的先计算优先级相同的自左向右计算当使用括号时从最内层括号开始计算但是括号左边的值的计算可以先期进行表达式示例后缀表达式的计算每个子表达式的计算结果，和下一个并列子表达式的计算

5、结果，根据后续的运算符进行运算，得到较大的子表达式的结果。从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。计算rst1rst2rst3rst4rst5abcd-*+ef/-计算方式从左到右扫描后缀表达式：如果是数字（最小的子表达式），压栈如果是运算符（和前面的子表达式一起，组成一个较大的子表达式），从栈中弹出相应的分量，并计算结果。将结果压栈。例如：35+2*首先3，5入栈然后处理+，3、5出栈，得到结果8（35+)，再入栈2入栈处理*，8，2出栈，得到结果(35+2*)16，再入栈，完成。思考题如果要把后缀表达式转成中缀表达式，怎么做？如果利用上面的算法

6、的框架？构造算符优先关系队列表+-*/()@+-*/()@>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=示例以3*(5-2)+7@为例,操作过程如下,构造操作符和操作数栈算法框架Functionexp_reduced:oprandtype;inistack(optr);push(optr,’@’);inistack(opnd)read(w);whilenot((w=‘@’)and(gettop(optr)=‘@’))doIfnotwinopthen[push(opnd,w);read(w)]elsecasepredede(get

7、top(optr),w)of‘<‘:[push(optr,w);read(w)];‘=‘:[x:=pop(optr);read(w)];‘>‘:[theta:=pop(optr);b:=pop(opnd);a:=pop(opnd);push(opnd,operate(a,theta,b))];endcreturn(gettop(opnd))endF思考题：等价表达式明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数