《数据结构域算法设计-#第三部分 线性部分之栈(第5章)》由会员分享，可在线阅读，更多相关《数据结构域算法设计-#第三部分 线性部分之栈(第5章)（30页珍藏版）》请在金锄头文库上搜索。
1、数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华1第五章 栈o 什么是栈？(即栈抽象数据类型) o 栈的存储结构及基本运算的实现 o 栈的应用数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华2什么是栈Stack？u 栈的定义 u 栈的基本运算数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华3栈的定义o Definition栈是一种运算受限的线性表，它限定只能 在表的一端进行插入和删除操作。其中： 允许插入和删除的一端称作栈顶； 不允许插入和删除的一端称作栈底。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华4栈的结构特性a1是栈底
2、元素, an是栈顶元素;以如下顺序入栈：a1, a2, , an只能在栈顶进行插入和删除操作， 第一个出栈的元素是an。也就是说，后进栈的元素先出栈，先入 栈的元素后出栈。栈顶栈底出栈 进栈 an a1 a2 因此，栈的结构特性是：后进先出LIFO ( Last In First Out)。栈又被称为后进先出表。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华5【思考题5.1】有进栈 序列：a，b，c，d。 假设进栈 、出栈操作可以交替进行，请 写出所有可能的出栈序列。栈的结构特性a, b, c, d a, d, c, b b, c, d, a c, b, a, da, b,
3、d, c b, a, c, d b, d, c, a d, c, b, aa, c, b, d b, a, d, c c, d, b, aa, c, d, b b, c, a, d c, b, d, a数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华6【一个结论】当入栈的数据元素的数目为n ，进栈 序列为a1，a2，an-1，an，假设 进栈 、出栈操作可以交替进行，那么可 获得的出栈序列个数由尤卡塔南数决定 ，即栈的结构特性数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华7栈的几个基本运算 InitStack( int top; SqStack;数据结构与应用
4、算法C语言描述配套课件湖北工业大学计算机学院 沈华14栈的顺序存储结构 顺序栈中基本运算的实现l初始化操作 InitStack_sq l访问栈顶操作 GetTop_sq l入栈操作 Push_sq l出栈操作 Pop_sq数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华15l 初始化操作 InitList_sq算法5.1 int InitStack_sq(SqStack *S ) (*S).top = -1; retrun 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华16l 访问栈顶操作 GetTop_sq算法5.5 int GetTop_sq
5、(SqStack S, ElemType *e) if(StackEmpty_sq(S) return -1; *e = S.dataS.top; return 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华17l 入栈操作 Push_sq算法5.6 int Push_sq(SqStack *S, ElemType e) if(StackFull_sq(*S) return -1; (*S).top = (*S).top + 1; (*S).data(*S).top = e; return 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院
6、 沈华18l 出栈操作 Pop_sq算法5.7 int Pop_sq(SqStack *S, ElemType *e) if(StackEmpty_sq(*S) return -1; *e = (*S).data(*S).top; (*S).top = (*S).top 1; return 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华19栈的链式存储结构 采用链式存储的栈称为链栈(Linked Stack) 。 链栈的结点结构和链表的结点结构相同。故链栈的类型描述如下：typedef LNode SNode;typedef LinkList LinkStack
7、;注意： 链栈中指针的方向是从栈顶指向栈底的。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华20栈的链式存储结构链栈的示意图如右：data next s栈顶栈底【思考5.2】链栈中栈顶和栈底的 位置是否可以交换？ 即链栈中指针方向是 从栈底指向栈顶。空链栈的示意图如右：data nexts数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华21 链栈中基本运算的实现栈的链式存储结构l初始化操作 InitStack_link l访问栈顶操作 GetTop_link l入栈操作 Push_link l出栈操作 Pop_link数据结构与应用算法C语言描述配套课件湖北工
8、业大学计算机学院 沈华22l 初始化操作 InitList_link算法5.8 int InitStack_link(LinkStack *stack ) *stack = (SNode *)malloc(sizeof(SNode); if(NULL = *stack) retrun -1; (*stack) - next = NULL; return 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华23l 访问栈顶操作 GetTop_link算法5.11 int GetTop_link(LinkStack stack, ElemType *e) if(Stack
9、Empty_link(stack) return -1; *e = stack - next - data; return 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华24l 入栈操作 Push_link算法5.12 int Push_link(LinkStack stack, ElemType e) SNode *p; p = (SNode *)malloc(sizeof(SNode); if(NULL = p) return -1; p - data = e; p - next = stack - next; stack - next = p; retur
10、n 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华25l 出栈操作 Pop_link算法5.13 int Pop_link(LinkStack stack, ElemType *e) SNode *p = NULL; if(StackEmpty_link(stack) return -1; p = stack - next; *e = p - data; stack - next = p - next; free(p); return 0; O(1)数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华26栈的应用 表达式的求解 任何一个表达式均是由操
11、作数Operand、运 算符Operator和界限符Delimiter组成。为了 叙述简洁 ，在此只讨论 二元运算符构成的 算术表达式。假设，表达式Exp = (第一操作数)S1 OP (第二操 作数)S2，即Exp = S1 OP S2。其中S1和S2可以 是简单变 量也可以是表达式。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华27 算术表达式算符之间的优先级关系2 1+-*/（）#+ - * / ( # val(1) 将扫描到的2压入栈OP；继续扫 描；else if(val(2) val(1) 将1从OP中弹出；从栈S中弹出栈顶 操作数t1和次栈顶 操作数t2；计算T = t2 1 t1；将中间结 果T压入栈S；else if(2是右括号 & 1是左括号)将1从栈OP中弹出；继续扫 描； while(2 = 1 & 2 = # & 1 = #)； 操作数栈S中的栈顶 元素即为整个表达式的解。数据结构与应用算法C语言描述配套课件湖北工业大学计算机学院 沈华30栈的应用 表达式的求解 算术表达式求解示例下述表达式的求解过程，请参见教材P58P60 。
