《数据结构第3章栈和队列》由会员分享，可在线阅读，更多相关《数据结构第3章栈和队列（42页珍藏版）》请在金锄头文库上搜索。
1、栈 和 队 列,1、栈和队列的定义及特点； 2、栈的顺序存储表示； 3、队列的顺序存储表示；队列的链接存储表示； 4、栈和队列的应用举例。,教学内容,限定仅在表尾进行插入或删除操作。,3.1 栈,3.1.1 抽象数据类型栈的定义,栈的定义,栈顶 (top),栈底 (bottom),出栈,进栈,栈底元素,栈顶元素,栈(stack)：线性表,后进先出 (LIFO结构)。,栈的抽象数据类型的定义,ADT Stack 数据对象：D ai | ai ElemSet, i = 1, 2, ., n, n0 数据关系：R1 | ai-1, aiD, i = 2, ., n 约定an 端为栈顶，a1 端为栈底
2、。 基本操作： InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALSE。,StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。 Push(&S,
3、e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。 ADT Stack,#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量 typedef struct ElemType *elem; / 数组指针，指示线性表的基地址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位
4、) SqList;,3.1.2 栈的表示和实现,顺序栈,顺序栈：利用一组地址连续的 存储单元依次存放自栈底到栈顶的 数据元素，同时附设指针 top 指示 栈顶元素在顺序栈中的位置。,SelemType *base; / 栈底指针，它始终指向栈底的位置。,SelemType *top; / 栈顶指针。,int stacksize; / 当前分配的栈可使用的最大存储容量。,Sqstack;,A,B,C,D,E,注：base 的值为 NULL，表明栈结构不存在。,空栈 若再进行元 素“出栈”操 作，将产生 “下溢”。,栈满 若再进行元 素“入栈”操 作，将产生 “上溢”。,#define STACK
5、_INIT_SIZE 100 / 栈存储空间的初始分配量,#define STACKINCREMENT 10 / 栈存储空间的分配增量,栈的基本操作在顺序栈中的实现,#define maxs 9; main() int stackmaxs; int top=0;while(top0)e=stacktop-1; top-=1; ,InitStack,Push,Pop,1,2,2,GetTop,2,1,Status InitStack (SqStack / InitStack,Status Push (SqStack / Push,Status GetTop (SqStack S, SElemTy
6、pe / GetTop,Status Pop (SqStack / Pop,3.2 栈的应用举例,3.2.1 数制转换,十进制数 N 和其他 d 进制数 M 的转换是计算机实现计算 的基本问题，其解决方法很多，其中一个简单算法是逐次除以 基数 d 取余法，它基于下列原理：N = (N div d )*d + N mod d,具体作法为：首先用 N 除以 d，得到的余数是 d 进制数 M 的最低位 M0，接着以前一步得到的商作为被除数，再除以 d， 得到的余数是 d 进制数 M 的次最低位 M1，依次类推，直到商 为 0 时得到的余数是 M 的最高位 Ms（假定 M 共有 s +1 位）。,例：
7、 (1348)10=(2504)8，其运算过程如下：,N N div 8 N mod 81348 168 4168 21 021 2 52 0 2,例：要求：输入一个非负十进制整数，输出等值的八进制数。,4,0,5,2,1348,168,main() int stack4; int top=0, N;scanf(“%d”, ,21,2,0,2504,3.2.2 括号匹配的检验,假设表达式中允许括号嵌套，则检验括号是否匹配的 方法可用“期待的急迫程度”这个概念来描述。,例： ( ) ,1 2 3 4 5 6 7 8,(,可能出现的不匹配的情况：,盼来的右括号不是所“期待”的；,盼来的是“不速之客
8、”；,到结束也未盼来所“期待”的括号。,算法的设计思想：,1）凡出现左括号，则进栈；,2）凡出现右括号，首先检查栈是否空。 若栈空，则表明该“右括号”多余； 否则和栈顶元素比较， 若相匹配，则“左括号出栈”， 否则表明不匹配。,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括号”有多余的。,3.2.3 行编辑程序,功能：接受用户从终端输入的程序或数据并存入用户的数据区。,每接受一个字符即存入用户的数据区。（差！难纠错。）,设一个输入缓冲区，接受完一行字符后再存入用户的数据 区。（好！可及时纠错。）,做法,纠错办法,# 退格符，表示前一个字符无效。, 退行符，表示整行字符
9、均无效。,例：接受的字符为：whli#ile outchputch,实际有效的为：while putch,w,h,l,i,i,l,e,3.2.4 迷宫求解,出口,入 口,0 1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8 9,11,12,22,32,33,34,24,25,26,16,15,14,31,41,51,52,53,63,64,65,75,85,86,87,88,穷举求解,求迷宫路径算法的基本思想： 若当前位置“可通”，则纳入路径，继续前进； 若当前位置“不可通”，则后退，换方向（按东南西北 的顺序）继续探索； 若四周“均无通路”，则将当前位置从路径中删除出去
10、。,3.2.5 表达式求值,运算规则,先乘除，后加减；,从左算到右；,先括号内，后括号外；,例：求表达式 4+23-10/5 的值。,计算顺序为：4+23-10/5=4+6-10/5=10-10/5=10-2=8,操作数或结果,运算符,#,4,+,2,3,6,10,-,10,/,5,8,2,作业： 3.1、3.2、3.3、3.4、3.18,选择题部分 1、若入栈序列是 a, b, c, d, e，则不可能的出栈序列是（）。 （A） edcba（B）decba（C）dceab （D）abcde 2、判定一个栈 ST(最多元素为m0) 为空的条件是（）。 （A） ST.top != 0 （B）ST
11、.top = 0 （C）ST.top != m0 （D）ST.top = m0 3、判定一个栈 ST(最多元素为m0) 为满的条件是（）。 （A）ST.top != 0 （B）ST.top = 0 （C）ST.top != m0 （D）ST.top = m0,3.3 栈与递归的实现,递归：一个直接调用自己或通过一系列的调用语句间接地调用自 己的函数，称做递归函数。,例：阶乘函数,相应的 C 语言函数是： float fact(int n) float s; if (n = = 0) s = 1; else s = n*fact(n -1); return (s); ,若求 5!，则有 main
12、() printf(“5!=%fn”,fact(5); ,当在一个函数的运行期间调用另一个函数时，在运行该被 调用函数之前，需先完成三件事： 将实参等信息传递给被调用函数，保存返回地址（入栈）； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。,从被调用函数返回调用函数之前，应该完成： 保存被调函数的计算结果； 释放被调函数的数据区； 按被调函数保存的返回地址（出栈）将控制转移到调用函数。,多个函数嵌套调用的规则是：后调用先返回。,此时的内存管理实行“栈式管理”。,float fact(int n) float s;if (n = = 0)s =1;elses = n*fac
13、t(n -1);return (s); ,递归调用执行过程：,主函数 main() Printf(fact(5),第一层调用 n = 5 s = 5*fact(4),第二层调用 n = 4 s = 4*fact(3),第三层调用 n = 3 s = 3*fact(2),第四层调用 n = 2 s = 2*fact(1),第五层调用 n = 1 s = 1*fact(0),fact(5)=120,输出 s = 120.00,第六层调用 n = 0 s = 1,fact(4)=24,fact(3)=6,fact(2)=2,fact(1)=1,fact(0)=1,主 a,5 a,4 a,3 a,2
14、a,1 a,printf(“5!=%fn”,fact(5);,float fact(int n) float s;if (n = = 0)s =1;elses = n*fact(n -1);return (s); ,float fact(int n) float s;if (n = = 0)s =1;elses = n*fact(n -1);return (s); ,float fact(int n) float s;if (n = = 0)s =1;elses = n*fact(n -1);return (s); ,float fact(int n) float s;if (n = = 0)s =1;elses = n*fact(n -1);return (s); ,float fact(int n) float s;if (n = = 0)s =1;elses = n*fact(n -1);return (s); ,n = 5,n = 4,
