Chap4_算法与数据结构—C语言描述(第2版)张乃孝编课件1.ppt

4.1.2 抽象数据类型 栈的存储结构 顺序栈(实现：一维数组s[M]) ? 3. 进栈运算 程序实现 void push_seq( PSeqStack pastack, DataType x ) 往pastack所指的栈中插入（或称推入）一个值为ｘ的元素。当栈不满时，先修改栈顶变量，将其值加1，然后把元素x放入栈顶变量所指的位置中。 假设plstack是PLinkStack类型的变量，则plstack-top就是栈顶指针，plstack-top-info是栈顶元素， 运算的实现 1.创建空链接栈 程序实现PLinkStack createEmptyStack_link(void) 创建一空链接栈，需要申请链接栈结构(struct LinkStack)空间，将其中top置为NULL,返回该结构的地址。 ? 3. 进栈运算程序实现 void push_link( PLinkStack plstack, DataType x ) 往plstack所指的栈中插入（或称压入）一个值为x的元素。首先申请结点空间，然后通过指针修改，将结点插在栈顶。 3. 迷宫问题 空白方块 : 通道 带阴影的方块: 墙 迷宫问题：求从入口到出口的一个以空白方块构成的(无环)路径。  求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。这类方法统称回溯法 数据结构 迷宫可用二维数组maze[m][n]来表示， 0：表示通道 1：表示墙 2：走过的点 迷宫的入口处为maze[1][1]，出口处为maze[m-2][n-2]， 它们的元素值必为0。 任意时刻在迷宫中的位置可用元素的行下标和列下标(i,j)来表示。 栈用顺序存储结构实现，栈中的元素类型DataType说明如下： typedef struct{  int x,y,d; //行坐标,列坐标,该位置上所选方向 } DataType; 4. 表达式计算 为了这里讨论的方便，对表达式做如下简化：(1) 假定所有运算分量都是整数；(2) 所有运算符都是整数的二元操作，且都用一个字符表示。 举例：31*(5-22)+70 转换为：31 5 22 - * 70 + 31*(5-22)+70 *(5-22)+70 31 (5-22)+70 * 31 5-22)+70 (* 31 -22)+70 (* 31 5 22)+70 -(* 31 5 )+70 -(* 31 5 22 +70 * 31 5 22 - 70 + 31 5 22 - * + 31 5 22 - * 70 31 5 22 - * 70 + 后缀表达式的求值 后缀表达式的主要优点是可以写出非常简单的求值过程。使用一个存放运算分量的栈，求值过程顺序扫描后缀表达式，每次遇到运算分量便将它推入栈中；遇到运算符时，就从栈中弹出两个整数(运算分量)进行计算，而后再把结果推入栈中。这样，到扫描结束时，留在栈顶的整数就是所求表达式的值。 输入串 栈顶 ……栈底 31 5 22 - * 70 + 5 22 - * 70 + 31 22 - * 70 + 5 31 - * 70 + 22 5 31 * 70 +