数据结构3

 

栈和队列

 

1,栈的类型定义

 

ADT Stack{

 

         数据对象：

 

         D={a1|ai=elementSet,i=1,2,,,,,,n,n>=0}

 

         数据关系

 

         R1={<ai-1,ai>|ai-1,ai=D,i=2,,,,,n}

 

         约定an端为栈顶，a1端为栈底

 

}

 

 

 

基本操作：

 

InitStack(&s)

 

操作结果：构造一个空的栈S

 

DestroyStack(&s)

 

初始条件：栈S已存在

 

操作结果：栈S被销毁

 

StackEmpty(s)

 

初始条件：栈S已经存在

 

操作结果：如果栈S存在，返回TRUE，否则返回FALSE

 

StackLength(s)

 

初始条件：栈S已存在

 

操作结果：返回S的元素个数，即栈的长度

 

GetTop(S,&e)

 

初始条件：栈S已存在且非空

 

操作结果：用e返回S的栈顶元素

 

ClearStack(&s)

 

初始条件：栈S已存在

 

操作结果：将S清为空栈

 

Push(&s,e)

 

初始条件：栈S已经存在

 

操作结果：插入元素e为新的栈顶元素

 

Pop(&s,&e)

 

初始条件：栈S已经存在且非空

 

操作结果：删除S的栈顶元素，并用e返回其值

 

 

 

 

 

栈的应用举例

 

1、数值转换

 

2、括号匹配的检验

 

3、行编辑程序问题

 

4、迷宫求解

 

5、表达式求值

 

6、递归实现

 

 

 

 

 

数制转换

 

算法基本原理

 

N=(N div d) * d+ N mod d

 

例如：(1345) =(2504)的八进制，其运输过程如下：

 

N      N div 8     N mod 8

 

1348      168                4

 

168    21             0

 

21       8              5

 

2        0               2

 

 

 

计算输出的结果和显示结果相反，所以用栈

 

void converson(){

 

         InitStack(S);

 

         scanf("%d",N);

 

         while(N){

 

                   Push(S,N%8);

 

                   N=N/8;

 

         }

 

         while(!StackEmpty(S)){

 

                   Pop(S,e);

 

                   printlf("%d",e);

 

         }

 

}

 

 

 

 

 

括号匹配的检验

 

( [ ] ( ) )或[ ( [ ] [ ] ) ]等为正确的格式。

 

[ ( ] )或 ( [ () ]均为不正确的格式，

 

检验括号是否匹配的方法用“期待的急迫程度”这个概念来描述，例如考虑下面的括号序列在

 

[ ( [ ] [ ] ) ]

 

1 2 3 4 5 6 7 8

 

 

 

分析可能出现的不匹配的情况：

 

到来的右括号非是所“期待”的

 

到来的是“不速之客”

 

直到结束，也没有到来所“期待”的。

 

 

 

算法的设计思想

 

1，凡出现左括号，则进栈

 

2、凡是出现右括号，首先检查栈是否为空，若栈空，则表明“右括号”多了，否则和栈顶元素比较，若想匹配，则“左括号”出栈，否则不匹配。

 

3、表达式检验结束时，若，空栈，则匹配正确。否则表明“左括号”多了。

 

Status matching(string &exp){

 

int state=1;

 

         while(i<=length(exp)&&state){

 

                   case 左括号:{

 

                            Push(S,exp[i];

 

                            i++;

 

                            break;

 

                   }

 

                   case ")":{

 

                            if(NOT StackEmeptY(s)&&GetTop(S)=="("){

 

                                     Pop(S,e);

 

                                     i++;

 

                            }else{

 

                                     state=0;

 

                            }

 

                   }

 

         }

 

}

 

 

 

 

 

迷宫求解

 

通常用的是“穷举求解”的方法

 

基本思想是：

 

1、若当前位置“可通”，则纳入路径，继续前进

 

2、若当前位置“不可通”，则后退，换向探索

 

3、若四周均“不可通”，则从路径中删除

 

 

 

从迷宫中一条从入口到出口的路径的算法：

 

设定当前位置的初始为入口位置；

 

do{

 

         若当前位置可同，

 

         则{

 

                   将当前位置插入栈顶

 

                   若改位置是出口位置，则结束

 

                   否则切换当前位置的东邻方块为新的当前位置。

 

         }否则{

 

                   若栈不为空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为：延顺时针方向旋转找到的栈顶位置的下一相邻块；

 

                   若栈不为空但栈顶位置的四周均不可通。

 

                   则{

 

                            删去栈顶位置；//从路径中山区该通道块

 

                            若栈不空，则重新测试新的栈顶位置

 

                            直到找到一个可通的相邻块或出栈至栈空。

 

                   }

 

         }

 

}

 

 

 

 

 

 

 

表达式求值

 

限于二元运算符的表达式定义：

 

表达式：：=（操作数）+（运算符）+（操作数）

 

操作数：=简单变量|表达式

 

简单变量：=标示符|无符号整数

 

 

 

在计算机中，表达式可以有三种

 

不同的标示方法

 

设Exp =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*+

 

 

 

结论:

 

1,操作数之间的相对次序不变

 

2，运算符的相对次序不同

 

3，中缀式丢失了括弧信息。致使运算的次序不确定。

 

4，前缀式的运算规则为：连续出现的俩个操作数和在它们之前且紧靠它们的运算符构成了一个最小表达式。

 

5、后缀式的运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的俩个操作数构成一个最小表达式。

 

 

 

如何从后缀式求值？

 

先找运算符，再找操作数

 

 

 

如何从原表达式求得后缀式？

 

分析“原表达式”和“后缀式”中的运算符

 

原表达式：a+b*c-d/e*f

 

后缀式：abc*+de/f*-

 

每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。

 

 

 

从原表达式求得后缀式的规律为：

 

1，设立操作数栈

 

2，设表达式的结束符为#，予设运算符栈的栈底为#

 

3，若当前字符是操作数，则直接发送给后缀式，

 

4，若当前运算符的优先数高于栈顶运算符，则进栈

 

5，否则，退出栈顶运算符发送给后缀式

 

6，“（”对它之前后的运算符起隔离作用，“）”可视为自相应左括号开始的表达式。

 

 

 

 

 

递归实现

 

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需要完成三件事

 

1，将所有的实在参数，返回地址等信息传递给被调用函数保存。

 

2，为被调用函数的局部变量分配存储区

 

3，将控制转移到被掉函数的入口。

 

 

 

 

 

从被调用函数返回调用函数之前，应该完成：

 

1，保存被调用函数的计算结果；

 

2，释放被调函数的数据区

 

3，依照被调函数保存的返回地址将控制转移到调用函数

 

多个函数嵌套调用的规则是：

 

后调用先返回，此时的内存管理实行“栈式管理”