Microsoft PowerPoint - ch3.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - ch3.pptx"

托轸常
5 years ago
Views:

1 第 3 章栈和队列第 3 章栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列哈尔滨工业大学 ( 威海 ) 计算机科学与技术学院 (2014/2015 学年秋季版 ) 1 本章重点难点第 3 章栈和队列重点 : (1) 栈队列的定义特点性质和应用 ;(2)AT 栈 AT 队列的设计和实现以及基本操作及相关算法难点 : (1) 循环队列中对边界条件的处理 ;(2) 分析栈和队列在表达式求值括号匹配数制转换迷宫求解中的应用实例, 提高利用栈和队列解决实际问题的应用水平 3.1 栈 3.2 栈的应用举例 3.3 队列 2 3

2 3.1 栈抽象数据类型栈的定义抽象数据类型栈的定义栈的定义栈 (Stack) 是一种特殊的线性表, 其插入和删除操作均在表的一端进行, 是一种运算受限的线性表栈的术语栈顶 (top) 是栈中允许插入和删除的一端栈底 (bottom) 是栈顶的另一端抽象数据类型栈的定义抽象数据类型栈的定义栈的示意图出栈入栈抽象数据类型栈 AT Stack { 栈的特点 a n 后进先出 (Last In First Out, 简称 LIFO) 又称栈为后进先出表 ( 简称 LIFO 结构 ) a 2 a 1 栈顶栈底数据对象 : ={ a i a i ElemSet, i=1,2,...,n, n 0 数据关系 : R1={ <a i-1, a i > a i-1, a i, i=2,...,n 约定 a n 端为栈顶,a 1 端为栈底基本操作 : AT Stack 见下页 6 7

3 3.1.1 抽象数据类型栈的定义栈的基本操作 InitStack(&S) // 初始化栈 estroystack(&s) // 销毁栈 learstack(&s) // 清空栈 StackEmpty(S) // 判栈空 StackLength(S) // 求栈长度 GetTop(S, &e) // 取栈顶元素 Push(&S, e) // 入栈 Pop(&S, &e) // 出栈 StackTravers(S, visit()) // 遍历栈 3.1 栈抽象数据类型栈的定义 8 9 顺序栈的语言实现 //----- 栈的顺序存储表示 #define STAK_INIT_SIZE 100; // 栈容量 #define STAKINREMENT 10; // 栈增量 typedef struct { SElemType *base; // 基地址 SElemType *top; // 栈顶指针 int stacksize; // 栈容量 SqStack; SqStack S; 栈初始化过程演示 (1) 给栈 S 申请栈空间 (2) 设置基地址 S.base 和栈顶地址 S.top (3) 设置栈容量 S.stacksize=STAK_INIT_SIZE S.base S.top 10 11

4 栈初始化算法 Status InitStack (SqStack &S){ // 构造一个空栈 S S.base=(ElemType*)malloc(STAK_INIT_SIZE* sizeof(elemtype)); if (!S.base) exit (OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STAK_INIT_SIZE; return OK; 入栈操作演示 (1) 如果栈满, 给栈增加容量 (2) 将数据存入栈顶位置, 栈顶后移一位 S.base a b c d e f e S.top S.top 入栈操作演示 Status Push (SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) { S.base = (ElemType *) realloc ( S.base, (S.stacksize + STAKINREMENT) * sizeof (ElemType)); if (!S.base) exit (OVERFLOW); // 存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STAKINREMENT; *S.top++ = e; return OK; 其它栈操作讨论 estroystack(&s) // 销毁栈 learstack(&s) // 清空栈 StackEmpty(S) // 判栈空 StackLength(S) // 求栈长度 GetTop(S, &e) // 取栈顶元素 Pop(&S, &e) // 出栈 StackTravers(S, visit()) // 遍历栈 14 15

5 链栈的实现与链表的实现基本相同, 头结点作为栈顶位置链栈的语言类型定义 Typedef struct SNode { ElemType data; struct Snode *next; SNode, *LinkStack; // 数据域 // 链域讨论链栈基本操作的实现 InitStack(&S) // 初始化栈 estroystack(&s) // 销毁栈 learstack(&s) // 清空栈 StackEmpty(S) // 判栈空 StackLength(S) // 求栈长度 GetTop(S, &e) // 取栈顶元素 Push(&S, e) // 入栈 Pop(&S, &e) // 出栈 StackTravers(S, visit()) // 遍历栈第 3 章栈和队列 3.2 栈的应用举例 3.1 栈 3.2 栈的应用举例 3.3 队列数制转换括号匹配的检验行编辑程序问题表达式求值 18 19

6 计算顺出顺序进制转换原理 : 任何 X 进制数 N 转换成 Y 进制数其结果都是要化成如下形式 N X a Y n 数制转换 n a2 Y a1 Y a0 Y 转换的过程就是通过取余运算求出 a 0,a 1,, a n, 而先求出的是个位, 十位, 与我们写数的习惯先从高位写正好相反, 通过栈先进后出的特点, 很容易实现倒过来的过程数制转换将 10 进制 1348 转换成 8 进制. 过程如下 : N N div 8 N mod 8 输序例数制转换 10 进制数 N 转换成 8 进制的算法 void conversion () { InitStack(S); scanf ("%d", &N); while (N) { Push(S, N%8); N = N/8; while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); // conversion 3.2 栈的应用举例数制转换括号匹配的检验行编辑程序问题表达式求值 22 23

7 问题描述一个表达式中, 包含三种括号 ( 和 ), [ 和 ] 和 { 和, 这三种括号可以按任意的合法次序嵌套使用 ( 如 : [ { [ ] ] [ ] ( ) ) 设计算法检验表达式中所使用括号的合法性问题讨论括号匹配的检验讨论 : 如果第一次遇到的右括号是 ], 那么前面出现的左括号有什么特点结论 : 如果第一次遇到的右括号是 ], 那么急迫期待前面出现的最后一个左括号是 [ 算法过程括号匹配的检验 (1) 当遇到左括号时, 进栈, 遇到右括号时出栈 ; (2) 当遇到某一个右括号时, 栈已空, 说明到目前为止, 右括号多于左括号 ; (3) 从栈中弹出的左括号与当前检验的右括号类型不同, 说明出现了括号交叉情况 ; (4) 算术表达式输入完毕, 但栈中还有没有匹配的左括号, 说明左括号多于右括号期待的急迫程度括号匹配的检验括号匹配检验算法 Status check( ) { char ch; InitStack(S); while ((ch=getchar())!= #') { switch (ch) { case (ch=='(' ch=='[' ch=='{'):push(s,ch);break; case (ch== ')'): if (StackEmpty(S)) retrun FALSE; else { Pop(S,e); if(e!= '(') return FALSE; break; 括号匹配的检验括号匹配检验算法 case (ch== ]'): if (StackEmpty(S)) retrun FALSE; else {Pop(S,e);if(e!= [') return FALSE; break; default:break; if (StackEmpty(S)) return TRUE; else return FALSE; 27

8 3.2 栈的应用举例数制转换括号匹配的检验行编辑程序问题表达式求值问题描述行编辑程序问题在用户输入一行的过程中, 允许用户输入出差错, 并在发现有误时可以及时更正解决办法设立一个输入缓冲区, 用以接受用户输入的一行字符, 然后逐行存入用户数据区, 并假设 # 为退行符行编辑程序问题例假设从终端接受了这样两行字符 : whli##ilr#e(s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行 : while (*s) putchar(*s++); 解决方案 : 栈作为输入缓冲区 ; 对接受字符判断, 非 # 则压栈 ; 若为 # 则弹栈 ; 则清空栈行编辑问题算法 void LineEdit(){ // 利用字符栈 S, 从终端接收一行并传送至调用过程的数据区 InitStack(S); ch=getchar(); while (ch!= EOF) { //EOF 为全文结束符 while (ch!= EOF && ch!= \n ) { 行编辑程序问题 estroystack(s); 30 31

9 switch (ch) { case '#' : Pop(S, c); break; case '@': learstack(s); break;// 重置 S 为空栈 default : Push(S, ch); break; ch = getchar(); // 从终端接收下一个字符 3.2 栈的应用举例数制转换括号匹配的检验行编辑程序问题栈中字符传送至调用过程的数据区 ; learstack(s); // 重置 S 为空栈 if (ch!= EOF) ch = getchar(); 表达式求值问题描述如图表示一个迷宫, 有一个入口, 一个出口, 从一个位置可以向 8 个方向走,0 表示能走通,1 表示走不通, 求从入口到出口的路径入口出口用栈实现迷宫路径求解的过程 (1) 入口位置入栈, 作标记以免重复进入 (2) 从栈顶位置任选一个可以进的位置, 并将此位置作标记避免重复, 新进位置入栈 (3) 重复 (2), 若栈顶位置无路可走, 则退栈, 从新的栈顶重复 (2) (4) 直到找到出口, 从栈底到栈顶即是路径, 或者栈空, 表示从入口到出口没通路 34 35

10 四周墙壁解决办法如图从某一点 [x][y] 出发搜索其四周的邻点 maze[6][8] maze[8][10] 36 [x-1][y-1] [x-1][y] [x-1][y+1] [x][y-1] [x][y] [x][y+1] [x+1][y-1] [x+1][y] [x+1][y+1] struct moved { int x,y; move[0].x=0 move[0].y=1... move[8]; move[1].x=1 move[7].x=-1 move[1].y=1 move[7].y=1 37 如何防止重复到达某位置到达某点后, 将此点的值改为 -1 迷宫路径求解算法设定当前位置的初值为入口位置 ; do{ 若当前位置可通, 则 { 将当前位置插入栈顶 ; 若该位置是出口位置, 则算法结束 ; 否则切换当前位置的东邻方块为新的当前位置 ; 否则 {. while ( 栈不空 ); maze[8][10] 38 39

11 迷宫路径求解算法若栈不空且栈顶位置尚有其他方向未被探索, 则设定新的当前位置为 : 沿顺时针方向旋转找到的栈顶位置的下一相邻块 ; 若栈不空但栈顶位置的四周均不可通, 则 { 删去栈顶位置 ; 若栈不空, 则重新测试新的栈顶位置, 直至找到一个可通的相邻块或出栈至栈空 ; 3.2 栈的应用举例数制转换括号匹配的检验行编辑程序问题表达式求值若栈空, 则表明迷宫没有通路表达式求值表达式求值问题描述一个表达式由操作数 (operand) 运算符 (operator) 界限符 (delimiter) 组成运算符和界限符统称为算符, 写出算符优先法求值的算法例求 3*(2+3*5)+6 的值算法求解过程设置两个栈, 一个存操作数, 栈名为 OPN, 一个存操作符, 栈名为 OPTR 栈 (1) 首先置操作数栈为空, 表达式起始符 # 为运算符栈的栈底元素 ; (2) 依次读入表达式中每个字符, 若是操作数则进 OPN 栈, 若是运算符则和 OPTR 栈的栈顶运算符比较优先权后作相应操作, 直到整个表达式操作完毕 42 43

3.2.5 表达式求值算法求解过程 (1) 若栈顶运算符小于输入运算符, 输入运算符进栈 OPTR; (2) 若栈顶运算符等于输入运算符 ( 只有栈顶是 (, 输入是 ), 或者栈顶是 #, 输入是 #) 两种情况, 分别去除一对括号, 或结束 (3) 若栈顶运算符大于输入运算符, 弹出栈顶运算符, 从 OPN 中弹出两个操作数与弹出运算符计算后再存入 OPN 栈, 继续 3.2.5 表达式求值表达式求值算法 OperandType EvaluateExpression(){ initstack(optr);push(optr, # ); initstack(opn);c=getchar(); while(c!

12 3.2.5 表达式求值算法求解过程 (1) 若栈顶运算符小于输入运算符, 输入运算符进栈 OPTR; (2) 若栈顶运算符等于输入运算符 ( 只有栈顶是 (, 输入是 ), 或者栈顶是 #, 输入是 #) 两种情况, 分别去除一对括号, 或结束 (3) 若栈顶运算符大于输入运算符, 弹出栈顶运算符, 从 OPN 中弹出两个操作数与弹出运算符计算后再存入 OPN 栈, 继续表达式求值表达式求值算法 OperandType EvaluateExpression(){ initstack(optr);push(optr, # ); initstack(opn);c=getchar(); while(c!= # ) GetTop(OPTR)!= # ){ if(!in(c,op)) { Push((OPN,c);c=getchar(); else switch(precede(gettop(optr),c)){ case < : Push(OPTR,c);c=getchar();break; case = : Pop(OPTR,x);c=getchar;break; case > : Pop(OPTR,theta); Pop(OPN,a); Pop(OPN,b); Push(OPN,Operate(a,theta,b)); break; //switch 语句结束 //while 语句结束 return(gettop(opn)); // 算法结束第 3 章栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列 46 47

13 队列的定义抽象数据类型队列的定义队列示意图抽象数据类型队列的定义队列 (Queue) 是一种运算受限的特殊的线性表, 它只允许在表的一端进行插入, 而在表的另一端进行删除出队 a 1 a 2 a 3 a n 队头队尾入队队列的术语队尾 (rear) 是队列中允许插入的一端队头 (front) 是队列中允许删除的一端队列的特点先进先出 (First In First Out, 简称 FIFO) 又称队列为先进先出表抽象数据类型队列 AT Queue { 数据对象 : ={a i a i ElemSet, i=1,2,...,n, n 0 数据关系 : R1={ <a i-1,a i > a i-1, a i, i=2,...,n 约定其中 a 1 端为队列头, a n 端为队列尾基本操作 : 抽象数据类型队列的定义 AT Queue 见下页抽象数据类型队列的定义队列的基本操作 InitQueue(&Q) // 初始化队列 estroyqueue(&q) // 销毁队列 QueueEmpty(Q) // 判队列是否空 QueueLength(Q) // 求队列长度 GetHead(Q, &e) // 取队头元素 learqueue(&q) // 清空队列 EnQueue(&Q, e) // 入队列 equeue(&q, &e) // 出队列 QueueTravers(Q, visit()) // 遍历队列 50 51

14 3.3.2 链队列链队列结点实现 typedef struct QNode { // 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr; 带头结点的链队列示意图 Q.front Q.rear 链队列 ^ 头结点空队列链队列数据类型实现 typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 LinkQueue; Q.front Q.rear a 1 a 2 a n ^ 链队列带头结点的链队列初始化 Status InitQueue (LinkQueue &Q) { // 构造一个空队列 Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); // 存储分配失败 Q.front->next = NULL; return OK; 链队列带头结点的链队列入队算法 Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素 e 为 Q 的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); // 存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; 54 55

15 3.3.2 链队列带头结点的链队列出队算法 Status equeue (LinkQueue &Q, QElemType &e) { // 若队列不空, 则删除 Q 的队头元素, // 用 e 返回其值, 并返回 OK; 否则返回 ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; 链队列带头结点的链队列其它操作讨论 estroyqueue(&q) // 销毁队列 QueueEmpty(Q) // 判队列是否空 QueueLength(Q) // 求队列长度 GetHead(Q, &e) // 取队头元素 learqueue(&q) // 清空队列 QueueTravers(Q, visit()) // 遍历队列顺序队列讨论顺序队列讨论循环队列属于顺序队列的一种, 讨论在采用一般顺序队列时出现的问题 4 3 E E E E B A B 1 0 A B A B A Sq.rear=5 sq.front=0 Sq.rear=5 Sq.front=1 Sq.rear=5 Sq.front=2 Sq.rear=5 Sq.front=5 Sq.rear=0 Sq.front=0 Sq.rear=1 Sq.front=0 Sq.rear=2 Sq.front=0 Sq.rear=5 Sq.front=0 讨论 : 在采用一般顺序队列时出现假上溢现象

16 循环队列的定义循环队列是顺序队列的一种特例, 它是把顺序队列构造成一个首尾相连的循环表指针和队列元素之间关系不变 Sq.rear=4 Sq.front=2 E Sq.rear=0 Sq.front=2 E F Sq.rear=1 Sq.front=2 循环队列空状态和满状态的讨论空状态 Sq.rear=0 Sq.front=0 满状态 E B A Sq.rear=0 Sq.front=0 讨论结论 : 循环队列空状态和满状态都满足 Q.front=Q.rear 循环队列空状态和满状态的判别方案 1: 另设一个标志区别队列是空还是满 ; 例如 : 设一个变量 count 用来记录队列中元素个数, 当 count==0 时队列为空, 当 count== MAXQSIZE 时队列为满循环队列空状态和满状态的判别方案 2: 以队头指针在队列尾指针的下一位置 ( 指环状的下一位置 ) 上作为队列呈满状态的标志, 牺牲一个元素存储空间 ; 队满条件为 : (sq.rear+1) mod maxsize==sq.front 队空条件为 : sq.rear==sq.front 62 63

17 循环队列数据类型实现 #define MAXQSIZE 100 // 最大队列长度 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针, 若队列不空, // 指向队列头元素 int rear; // 尾指针, 若队列不空, 指向队列尾元素的下一个位置 SqQueue; SqQueue Sq; 循环队列初始化算法 Status InitQueue (SqQueue &Q) { // 构造一个空队列 Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if (!Q.base) exit (OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; 循环队列入队算法 Status EnQueue (SqQueue &Q, ElemType e) { // 插入元素 e 为 Q 的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; // 队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; 循环队列出队算法 Status equeue (SqQueue &Q, ElemType &e) { // 若队列不空, 则删除 Q 的队头元素, // 用 e 返回其值, 并返回 OK; 否则返回 ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; 66 67

18 分析以下两种状态如何求队列长度求循环队列长度算法 int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MaxSize)%MaxSize; sq->rear=4 sq->front=2 sq->rear=1 sq->front= 本章小结熟练掌握 : (1) 栈队列的定义特点和性质 ; (2) AT 栈 AT 队列的设计和实现以及基本操作及相关算法重点学习 : AT 栈和队列在表达式求值括号匹配数制转换迷宫求解中的应用, 提高利用栈和队列解决实际问题的应用水平 70

第三章栈和队列

第三章栈和队列第 3 章栈 3.1 ADT 栈 3.2 ADT 栈的实现 3.3 ADT 栈的应用 2008-3-31 福州大学数学与计算机科学学院吴英杰 1 1 栈的定义和特点 3.1 ADT 栈 (stack) 定义 : 限定仅在表首进行插入或删除操作的线性表, 表首栈顶, 表尾栈底, 不含元素的空表称空栈特点 : 先进后出 (FILO) 或后进先出 (LIFO) 进栈栈顶... an... 出栈栈