线性表小结 元素之间的线性关系 顺序表 顺序表：元素相邻存储 单链表：后继指针链接 一维数组 给定下标随机存取 插入/删除/查找所需元素移动或比较次数=表长度的一半 2018/12/3

线性表小结 (单)链表 头指针 vs. 头结点 插入/删除操作中，不能使链表“断开” 头结点：使得链表的插入/删除算法代码简洁、一致 若无头结点，则在首结点前插入新元素或删除首结点时，头指针需要修改 头指针：对链表(不包括循环链表)的任何操作必须从头指针开始 头指针起着标记链表的作用，通常将头指针称为链表的名字 插入/删除操作中，不能使链表“断开” 必须知道前驱结点的指针 2018/12/3

第三章 栈和队列 第一部分 栈(Stack) 2018/12/3

3.1 栈（stack） 先进后出(FILO) 操作受限的线性表： 只能在表尾进行插入或删除 结构：表尾栈顶，表头栈底 操作：栈顶插入入栈，删除栈顶出栈 只能在表尾进行插入或删除 先进后出(FILO) 入栈 出栈 an a1 a2 ……... ... 栈底 栈顶 栈 s = ( a1 , a2 , …… , an ) 2018/12/3

栈实现1：顺序栈(一维数组) typedef struct { SElemType *base ; //元素数组(指针) SElemType *top ; //栈顶元素位置指针 int stacksize ; //栈空间尺寸 } SqStack ; top 1 2 3 4 … base 栈顶指针 2018/12/3

顺序栈基本操作 1 入栈 关键代码： * s.top = e ; s.top ++ ; 栈满后继续入栈： 上溢(overflow) 栈满 F 2 3 4 5 base E D C B top A 入栈 栈满后继续入栈： 上溢(overflow) 2018/12/3

入栈(push)算法 Status Push ( SqStack &s , SElemType e ){ if ( S.top - S.base >= S.stacksize ) { //栈满 ……//追加空间 s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; } * s.top = e; //新元素放入当前栈顶 s.top ++ ; //栈顶(指针)+1 return OK; 2018/12/3

顺序栈基本操作 2 出栈 关键代码： F s.top -- ; e = * s.top ; E D C B A 栈空后继续出栈： 1 2 3 4 5 base F E D 栈空 C B A 栈空后继续出栈： 下溢(underflow) 2018/12/3

出栈(pop) Status pop ( SqStack &s , SElemType &e) { if ( s.top == s.base ) return ERROR ; //栈空 s.top -- ; //栈顶(指针)－1 e = *s.top; return OK; } 2018/12/3

栈实现(2)：链栈(单链表) typedef struct SNode { SElemType data ; struct SNode *next ; } StackNode , * LinkStack ; ^ …... H data next 栈底 栈顶 2018/12/3

栈的应用(1) 数制转换：十进制八进制 练习：(3467)10 = (6613)8 N N div 8 (整除) N mod 8 (余数入栈) 3467 433 3 433 54 1 54 6 6 6 0 6 低位：后进先出(LIFO) 高位：先进后出(FILO) 2018/12/3

栈的应用(2) 括号匹配：对任意的括号串进行配对检测 ①若配对，返回：“成功” ②否则，返回：“失败” 例1：( [ ] ( ) ) 例2：[ ( ] ) 例3：[ ( [ ] [ ] ) ] 例4：( ( ) ] ) 成功 失败 成功 失败 2018/12/3

栈的应用(2) 括号匹配：对任意的括号串进行配对检测 思路：基于栈来判断括号配对是否正确 方法：左括号保存、右括号配对 消解 假设：输入中除左/右括号外无其他字符，回车键结束 2018/12/3

栈的应用(2) 括号匹配：对任意的括号串进行配对检测 方法：基于栈，左括号保存、右括号配对 消解 ①读到 (：入栈 ①读到 (：入栈 ②读到 )：与和栈顶的 ( 配对 消解弹出栈顶 ③若输入读完且栈为空：配对成功，算法停止； 若栈先空：输入中剩余的 ) 已无可匹配的 (，出错 若输入先读完：栈中剩余的 ( 已无可匹配的 )，出错 2018/12/3

栈的应用(2)：括号匹配算法 Status Check( ){ //检查输入的括号串是否配对成功 InitStack (S); //构造空栈 Push (S,'#'); //栈底符号 #：栈空标志 int bool = 1; //匹配标志：1－成功；0－失败 char ch = getchar (); //键盘读入第一个输入字符 while ( ch != '\n' && bool ) { if ( ch == '(' ) Push ( S , ch ); //左括号入栈 if ( ch == ')' ) { if ( GetTop ( S , e) == '#' ) bool=0; //栈顶元素＝ #，栈先空，失败 2018/12/3

栈的应用(2)：括号匹配算法(续) … else Pop ( S , e); //栈顶元素≠ #，是左括号，配对消解 ch = getchar (); //读入下一个字符 } //end if ) } //end while if ( Gettop ( S , e ) != '#' ) bool = 0; //输入先读完，失败 if ( bool ) printf ("成功") else printf ( "失败" ); } 2018/12/3

栈的应用(3) 表达式求值： 中缀、后缀、前缀 中缀表达式 后缀表达式 a * b + c a b * c + a + ( b * c + d ) / e a b c * d + e / + a + ( b * c + d ) / e a b c * d + e / + ---Reverse Polish Notation 2018/12/3

栈的应用(3) 表达式求值：后缀 例：4+3*5 后缀表达式：4 3 5 * + ① 读入表达式一个符号 ② 若是操作数，压入栈，转 ④ ③ 若是运算符，栈中弹出操作数，运算结果入栈 ④ 若表达式输入完毕，栈顶即表达式值；若未输入完，转 ① 例：4+3*5 后缀表达式：4 3 5 * + top 7 3 5 top 4 top 4 3 top 4 15 top 19 top 2018/12/3

栈的应用(4) 递归：嵌套调用子程序 r s r r s t r 主程序 s t r s r 子过程2 子过程1 子过程3 2018/12/3

栈的应用(4) 递归调用的实现：操作系统内部建立的工作栈 结果：? 1， void print(int w) { 2，2， int i; 3，3，3， void print(int w) { int i; if ( w!=0) { print( w-1 ); for( i = 1; i <=w ; ++i ) printf(“%3d,”, w); printf(“\n”); } 2018/12/3

递归程序执行情况分析： 1 print(0); （3）w=1 （2）w=2 （1）w=3 top (4)输出：1 w （4）w=0 （4）w=0 （3）w=1 （2）w=2 （1）w=3 top w 2 print(1); （2）w=2 （1）w=3 top (3) 输出：2, 2 w 3 print(2); （1）w=3 top (2) 输出：3, 3, 3 w (4)输出：1 (3) 1 (2) 2 (1) 3 top 返回 (3) 1 (2) 2 (1) 3 top (4) 0 主程序 print(3); 结束 (1) (3) 输出：2, 2 (2) 2 (1) 3 top (2) 输出：3, 3, 3 (1 ) 3 top (1) 2018/12/3

典型考题： 1、有6个元素A、B、C、D、E、F依次入栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，说明理由。 1) CDBEFA 2) ABEDFC 3) DCEABF 4) BAEFCD 2018/12/3

典型考题： 1、有6个元素A、B、C、D、E、F依次入栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，说明理由。 1) CDBEFA 2) ABEDFC 3) DCEABF 4) BAEFCD 能：1) 2) 否：3) 4) 为什么？ 2018/12/3

操作序列 出栈序列 1) CDBEFA top 2018/12/3

操作序列 出栈序列 push(A) 1) CDBEFA top A 2018/12/3

操作序列 出栈序列 push(A) 1) CDBEFA push(B) top B A 2018/12/3

操作序列 出栈序列 push(A) 1) CDBEFA push(B) push(C) top C B A 2018/12/3

操作序列 出栈序列 push(A) C 1) CDBEFA push(B) push(C) pop(C) top B A 2018/12/3

操作序列 出栈序列 push(A) C 1) CDBEFA push(B) push(C) pop(C) push(D) D B A top 2018/12/3

操作序列 出栈序列 push(A) C D 1) CDBEFA push(B) push(C) pop(C) push(D) pop(D) top B A 2018/12/3

操作序列 出栈序列 push(A) C D B 1) CDBEFA push(B) push(C) pop(C) push(D) pop(D) pop(B) top A 2018/12/3

操作序列 出栈序列 push(A) C D B 1) CDBEFA push(B) push(C) pop(C) push(D) pop(D) pop(B) top push(E) E A 2018/12/3

操作序列 出栈序列 push(A) C D B E 1) CDBEFA push(B) push(C) pop(C) push(D) pop(D) pop(B) top push(E) pop(E) A 2018/12/3

操作序列 出栈序列 push(A) C D B E 1) CDBEFA push(B) push(C) pop(C) push(D) pop(D) top pop(B) push(E) F pop(E) A push(F) 2018/12/3

操作序列 出栈序列 push(A) C D B E F 1) CDBEFA push(B) push(C) pop(C) push(D) pop(D) pop(B) top push(E) pop(E) A push(F) pop(F) 2018/12/3

操作序列 出栈序列 push(A) C D B E F A 1) CDBEFA push(B) push(C) pop(C) push(D) pop(D) pop(B) push(E) top pop(E) push(F) pop(F) pop(A) 2018/12/3

操作序列 出栈序列 3) DCEABF top 2018/12/3

操作序列 出栈序列 push(A) 3) DCEABF top A 2018/12/3

操作序列 出栈序列 push(A) 3) DCEABF push(B) top B A 2018/12/3

操作序列 出栈序列 push(A) 3) DCEABF push(B) push(C) top C B A 2018/12/3

操作序列 出栈序列 push(A) 3) DCEABF push(B) push(C) push(D) D C B A top 2018/12/3

操作序列 出栈序列 push(A) D 3) DCEABF push(B) push(C) push(D) pop(D) C B A top 2018/12/3

操作序列 出栈序列 push(A) D C 3) DCEABF push(B) push(C) push(D) pop(D) pop(C) top B A 2018/12/3

操作序列 出栈序列 push(A) D C 3) DCEABF push(B) push(C) push(D) pop(D) pop(C) top push(E) E B A 2018/12/3

操作序列 出栈序列 push(A) D C E 3) DCEABF push(B) push(C) push(D) pop(D) pop(C) top push(E) pop(E) B A 2018/12/3

操作序列 出栈序列 push(A) D C E A? 3) DCEABF push(B) push(C) push(D) pop(D) pop(C) top push(E) pop(E) B A 2018/12/3

合法出栈序列判定 入栈序列1、2、…… n，出栈序列为p1、p2、…… pn 定理：若 i<j<k，则不存在出栈序列 pk < pi < pj i < k，而 pk < pi，即 i 先入栈，但需后于 k 出栈，则 k 压在 i 上 j < k，而 pk < pj，即 j 先入栈，但需后于 k 出栈，则 k 压在 j 上 又 k 最先出栈，所以 i , j 均在栈内，按入栈顺序 j 必在 i 上 所以，不可能 i 先于 j 出栈，即 pi<pj 2018/12/3

栈：小结 逻辑结构：线性表 存储结构： 基本操作 操作受限：只在一端插入/删除(LIFO) 顺序栈：栈顶指针－栈顶元素后的空位置 链栈： 入栈(push) 出栈(pop) 2018/12/3

栈：小结 应用：栈能够记忆处理的中间结果 数制转换 过程调用(递归) 括号匹配 表达式计算 后缀表达式计算 中缀表达式计算 (中缀表达式转换为后缀表达式) 2018/12/3