《数据结构栈和队列讲述》由会员分享，可在线阅读，更多相关《数据结构栈和队列讲述（115页珍藏版）》请在金锄头文库上搜索。
1、东北大学信息学院计算机应用技术研究所东北大学信息学院计算机应用技术研究所 杨雷杨雷 yangleiyanglei 第第三三章章 栈和队列栈和队列 通常称，栈和队列是限定插入和删除 只能在表的“端点”进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in 栈和队列是两种常用的数据类型 3.1 栈的类型定义 3.2 栈类型的实现 3.3 栈的应用举例 3.4 队列的类型定义 3.5 队列类型的实现 3.6 队列的应用举例
2、 3.1 栈的类型定义 ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT Stack top bottom 进栈 出栈 an . . . . a1 InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 类似于线性表的顺序映象实现，指向 表尾的指针可以作为栈顶指针。 S
3、tatus InitStack (SqStack if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; Status Push (SqStack if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; Status Pop (SqStack e = *-S.top; re
4、turn OK; 链栈 栈的链式存储结构称为链栈链栈。 栈顶 l链栈的特点- （1）插入和删除（进栈/退栈） 仅在表头位置上（栈顶）进 行。 （2）不需附加头结点，栈顶指 针就是链表（即链栈）的头 指针。 data link 栈底 栈的链接存储结构 链栈的结点定义: typedef char SElemType ; typedef struct LinkNode SElemType data; struct LinkNode *next; LinkNode, *LinkStack; LinkStack top; 链栈的进栈算法: Status Push( LinkStack p=(LinkNo
5、de *)malloc(sizeof(LinkNode); if ( !p ) exit(ERROR); p-data = e; p-next=top; top = p; 链栈的出栈算法: Status Pop(LinkStack else e = top-data; p= top; top = top-next; free(p); return OK; 3.3 栈的应用举例 例一、 数制转换 例二、 括号匹配的检验 例三、 行编辑程序问题 例四、 迷宫求解 例五、 表达式求值 例六、 实现递归 例一、 数制转换 算法基于原理： N = (N div d)d + N mod d 例如：（134
6、8)10 = (2504)8 ，其 运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 计算顺序 输出顺序 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 回文游戏 顺读与逆读字符串一样（不含空格） d a d top 1.读入字符串 2.去掉空格（原串） 3.压入栈 4.原串字符与出栈字符
7、依次比 较 若不等，非回文 若直到栈空都相等，回文 字符串：“madam im adam” 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 （）) 均为不正确的格式。 则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。 例二、 括号匹配的检验 分析可能出现的不匹配的情况: 到来的右括弧并非是所“期待”的； 例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客”； 直到结束，也没有到来所“期 待”的括弧。 算法的设计思想： 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶
8、元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。 Status matching(string while (i ( # 0)的阶乘等于n乘上(n-1)的阶乘 递归的应用 递归定义：如阶乘、Fibonacci数列等 数据结构：如表、树、二叉树等 问题求解：如Hanoi塔、八皇后 栈与递归的实现阶乘函数 定义是递归的 求解阶乘函数的递归算法 long fact ( long n ) if ( n = 0 ) return 1;/递归结束条件 else return n * fact (n-1); /递
9、归的规则 栈与递归的实现阶乘函数 主程序主程序 main( ): fact(4) 参 数 传 递 递递 归归 调调 用用 结 果 返 回 回回 归归 求求 值值 fact(4): fact(3): fact(2): fact(1): fact(0): 1 直接定值为1 计算 4*fact(3) 计算 3*fact(2) 计算 2*fact(1) 计算 1*fact(0) 1 2 6 24 栈与递归的实现数据结构是递 归的 数据结构是递归的-表 空表 非空表: (表头元素+除表头元素以外的剩余元素 ) 查找表L中是否有元素值e LinkList search(LinkList L, ElemTy
10、pe e) / L为不带头结点的单向非循环链表 if ( L=NULL ) return NULL; else if ( L-data=e ) return L; else return search(L-next, e); 栈与递归的实现问题求解是递归的 Hanoi塔问题 void hanoi(int n, char a, char b, char c) n-圆盘数a-源塔座 b-中介塔座 c-目标塔座 搬动方法 n=1, a-c n1: hanoi(n-1, a, c, b) a-c hanoi(n-1, b, a, c) 注意 用递归调用的结果， 不关注该结果如何 获得的细节 栈与递归的实现递归实现 调用函数与被调用函数-系统工作栈 执行被调用函数前 现场保护：实在参数、返回地址 为被调用函数的局部变量分配存储区 将控制转移到被调函数的入口 从被调用函数返回调用函数前 保存被调函数的计算结果 释放被调函数的数据区 现场恢复：返回
