3.1栈-顺序栈-类型定义 3.1栈-顺序栈-基本操作的实现 。题序想 ·顺序找 。基本操作的实现 。类型定义 注意t即的含义—的定 。战项的初始化：S.top=S.base #define STACK_INIT_SIzE1O0/∥存情空间的初地分配量 空，S.base==5.top ,找满：5.top-S.base>=S.stacksize #define STACKINCREMENT10/∥存情空间的分配增量 。入栈：S.top++=e,出找：e=*-S.top typedef struct( ElemType *base; 川提度指针 ElemType *top:∥线顶指针（拉亚元意的下一个位置） int stacksize; top- ∥当前分配的存伸容量 top >SqStack; base base- 空栈 a进栈 b进栈 7/50 回 钩定：op指向找顶元的下一个位 图 3.1栈-顺序栈-基本操作的实现 3.1栈赞钱的表示与实现 ,顺序栈 ■链栈 ·无栈满问题（除非分配不出内存），空间可扩充 top ,栈顶一链表的表头 。可以不必引入头结，点 hase has o柳一N一□一□一…一囚 e进栈 ∫进栈溢出 e出栈 约定：top指向栈顶元素所在的结点 约定：top指向找顶元素的下一个位量 9/50 图 10/50 图 3.2栈的应用举例 3.2栈的应用举例-数制转换 ,数制转换 ■数制转换：将十进制数N转换成其他d进制数 ■括号匹配的检验 ,算法思想：N=(N div d)Xd+N mod d ■行编辑程庄 1)保存余数N%d 2)N=N/d, ■迷宫求解 3)若N==0结束，否则继续1)。 ■表达式求值 保存的余数从先到后依次表示转换后的d进制数的 低位到高位，而输出是由高位到低位的，因此必须 定义先进后出的线性表栈来保存：当全部的余 数求出后，通过逐个出栈输出d进制数。 11/50 图 12/50 图 22 7/50 3.1 栈–顺序栈-类型定义 „ 顺序栈 „ 类型定义 注意top的含义——约定 #define STACK_INIT_SIZE 100// 存储空间的初始分配量 #define STACKINCREMENT 10// 存储空间的分配增量 typedef struct{ ElemType *base; // 栈底指针 ElemType *top; // 栈顶指针(栈顶元素的下一个位置) int stacksize; // 当前分配的存储容量 }SqStack; 8/50 3.1 栈–顺序栈-基本操作的实现 „ 顺序栈 „ 基本操作的实现 „ 栈顶的初始化：S.top = S.base „ 栈空：S.base == S.top „ 栈满：S.top - S.base >= S.stacksize „ 入栈：*S.top ++ = e，出栈：e = *--S.top base 空栈 a 进栈 b 进栈 a top base top base top a b 约定：top指向栈顶元素的下一个位置 9/50 3.1 栈–顺序栈-基本操作的实现 base e 进栈 f 进栈溢出 e出栈 e d c b a top base top base top 约定：top指向栈顶元素的下一个位置 e d c b a „ 顺序栈 d c b a 10/50 3.1 栈–链栈的表示与实现 约定：top指向栈顶元素所在的结点 „ 链栈 „ 无栈满问题(除非分配不出内存), 空间可扩充 „ 栈顶----链表的表头 „ 可以不必引入头结点 top N ^ 11/50 3.2 栈的应用举例 „ 数制转换 „ 括号匹配的检验 „ 行编辑程序 „ 迷宫求解 „ 表达式求值 12/50 3.2 栈的应用举例-数制转换 „ 数制转换: 将十进制数N转换成其他d进制数 „ 算法思想：N = ( N div d )×d + N mod d 1) 保存余数N%d 2) N=N/d， 3) 若N==0结束，否则继续1)。 保存的余数从先到后依次表示转换后的d 进制数的 低位到高位，而输出是由高位到低位的，因此必须 定义先进后出的线性表——栈来保存；当全部的余 数求出后，通过逐个出栈输出d进制数