《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－3》由会员分享，可在线阅读，更多相关《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－3（51页珍藏版）》请在金锄头文库上搜索。
1、1,计算机软件技术基础,课件,第一章 数据结构,第二章 操作系统,第三章 软件工程,第四章 数据库,制作者：张选芳 Email: 电话:5182508,2,第一章 数据结构,第一单元,第二单元,第三单元,第四单元,第五单元,第六单元,第七单元,第八单元,3,栈和队列,第三单元,第一章 数据结构,4,1.2.2 栈和队列,一栈的定义及基本运算 1、栈(Stack)的定义 只允许在一端插入和删除的顺序表 插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO) 当表中没有元素时称为空栈。,设给定栈S = ( a0 ,a1 , an-1) ,则称a0为栈
2、底， an-1为栈顶。,5,【例1-3】元素是以a0, a1, , an1的顺序进栈,退栈的次序却是an1, an-2, , a1 , a0。 2、栈的基本运算 (1)InitStack（S） 构造一个空栈S。 (2) StackEmpty（S） 判栈空。若S为空栈，则返回TRUE，否则返回FALSE。 (3) StackFull（S） 判栈满。若S为满栈，则返回TRUE，否则返回FALSE。该运算只适用于栈的顺序存储结构。,6,(4) Push（S，x） 进栈。若栈S不满，则将元素x插入S的栈顶。 (5) Pop（S） 退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。 (6) Stac
3、kTop（S） 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。 二顺序栈 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。,7,1 顺序栈的类型定义 #define StackSize 100 /假定预分配的栈空间最多为100个元素 struct SeqStack char dataStackSize; /假定栈元素的数据类型为字符 int top; ; 注意：顺序栈中元素用向量存放，栈底位置是固定不变的，栈顶位置是随着进栈和退栈操作而变化的。,8,2. 顺序栈的基本操作 设S是SeqStack类型的指针变量。若栈底位置在向量的低端,即S-data0是栈底元素。 (1) 进栈操
4、作 进栈时,需要将S-top加1。 注意： S-top=StackSize-1表示栈满,“上溢”现象。 (2) 退栈操作 退栈时,需将S-top减1。 注意:S-top0表示空栈,“下溢“现象。,9,3顺序栈的基本运算 (1) 置栈空 void InitStack（SeqStack *S） /将顺序栈置空 S-top=-1; (2) 判栈空 int StackEmpty（SeqStack *S） return S-top=-1; ,10,(3) 判栈满 int StackFull（SeqStack *S） return S-top=StackSize-1; (4) 进栈 void Push（S
5、，x） if (StackFull(S) Error(“Stack overflow“); /上溢，退出运行 S-data+S-top=x; /栈顶指针加1后将x入栈 ,11,进栈示例,进栈,12,(5) 退栈 char Pop（struct SeqStack *S） if(StackEmpty(S) Error(“Stack underflow“); /下溢，退出运行 return S-dataS-top-; /栈顶元素返回后将栈顶指针减1 ,13,退栈示例,退栈,14,（6） 取栈顶元素 char StackTop（struct SeqStack *S） if(StackEmpty(S)
6、Error(“Stack is empty“); /空栈，退出运行 return S-dataS-top; 4. 双栈共享一个栈空间,15,三链栈 栈的链式存储结构称为链栈。采用链接方式来表示一个栈，便于结点的插入与删除。,链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作,16,1链栈的类型定义 链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针如图所示。,top,链栈的类型说明 struct StackNode char data； struct StackNode *next； ; struct LinkStack StackNode
7、 *top; ; /栈顶指针,17,2链栈的基本运算 (1) 置栈空 Void InitStack(LinkStack *S) S-top=NULL; (2) 判栈空 int StackEmpty(LinkStack *S) return S-top=NULL; ,18,(3) 进栈 void Push(LinkStack *S, char x) /将元素x插入链栈头部 struct StackNode *p= ( struct StackNode *) malloc(sizeof(struct StackNode); p-data=x; p-next=S-top; /将新结点*p插入链栈头部
8、 S-top=p; ,19,(4) 退栈 char Pop(struct LinkStack *S) char x; StackNode *p=S-top; /保存栈顶指针 if(StackEmpty(S) Error(“Stack underflow.“); /下溢 x=p-data; /保存栈顶结点数据 S-top=p-next; /将栈顶结点从链上摘下 free(p); return x; ,20,(5) 取栈顶元素 char StackTop(struct LinkStack *S) if(StackEmpty(S) Error(“Stack is empty.“) return S-
9、top-data; 注意： 链栈中的结点是动态分配的,所以可以不考虑上溢,无须定义StackFull运算。,21,四栈的应用 1利用栈实现递归函数 栈的一个重要应用是在程序设计中实现递归过程。所谓递归，是指，若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。以下三种情况常常用到递归方法：,22,（1）定义是递归的。例如，求n！可以递归定义如下：,（2） 数据结构是递归的。例如，单链表结点结构的定义： struct ListNode char data; /数据域 struct ListNode* next; /指
10、针域 ;,23,（3） 问题的解法是递归的。例如，汉诺塔问题的解法。 有大量的计算问题可以归结成一个递归函数。 例如, 累加求和问题、求最大公约数、求解斐波那契数列、求幂运算等。 数学中许多著名的函数和多项式都是以递归形式给出的。 例如, Ackerman函数，厄米特多项式、勒让德多项式等。,24,根据n!的定义,可以写出相应的递归函数long factorial(long n) long f; if (n=0) f=1; else f=n*factorial(n-1); R2: return f; void main() long f,n=4; f=factorial(n); R1: pri
11、ntf(“%ld!=%ld n“,n,f); ,25,递归工作栈的现场信息,在上面的程序代码中，R1为主调函数main调用factorial函数时的返回地址，R2为factorial函数中递归调用factorial(n-1)时的返回地址。每层调用的现场信息如表1-3所示。,26,每层调用的现场信息如表1-3所示 表1-3 递归工作栈,27,程序的递归调用执行过程如图1-22所示（设n=4）。,28,2利用栈求表达式的值 表达式 所谓表达式，是由操作数、运算符、括号所组成的有意义的计算公式。 运算符 单目运算符、双目运算符和三目运算符。 运算符的类型 算术运算符、逻辑运算符和关系运算符等 中缀表
12、达式： 12*(20-5)+30 后缀表达式： 12 20 5 - * 30 +,29,（1）后缀表达式的求值 利用栈求解后缀表达式的值，可以使用一个存放操作数的栈，求值过程中，按顺序依次扫描后缀表达式，当遇到操作数时就将它压入栈中，当遇到运算符时，就从栈中弹出两个操作数进行运算，然后再把运算结果压入栈中。当后缀表达式扫描结束时，留在栈顶的数就是所求表达式的值。因此，利用栈可以很方便地求出后缀表达式的值，算法实现较为简单。,30,（2）中缀表达式的求值 对于中缀表达式5*(27+3*7)+22，转换为后缀表达式为5 27 3 7 * + * 22 +，实现这个转换的基本思想是：按顺序依次扫描中
13、缀表达式，当读入一个操作数时就立即输出；而在读入一个运算符（如“+”或“-”）时，首先把它放进一个运算符栈，一直等到这个运算符的两个操作数都读到后，才能将它输出。例如，在对表达式4*6+5,31, 后缀（infix）表达式求值, 利用后缀表达式求值，从左向右顺序地扫描表达式，并使用一个栈暂存扫描到的操作数或计算结果。 在后缀表达式的计算顺序中已经隐含了加括号的优先次序，因而括号在后缀表达式中不出现。 只涉及双目操作数，不考虑单目操作数,A B C D E F /,R1,R2,R3,R4,R5,后缀表达式的计算顺序,32, 后缀表达式计算表达式的过程,步序 扫描项 项类型 动作 栈中内容 1 置
14、空栈 空 2 A 操作数 进栈 A 3 B 操作数 进栈 AB 4 C 操作数 进栈 ABC 5 D 操作数 进栈 ABCD 6 - 操作符 D、C退栈 ABR1 计算C-D 结果R1进栈,33,步序 扫描项 项类型 动作 栈中内容,7 * 操作符 R1、B退栈 AR2 计算B* R1 结果R2进栈 8 + 操作符 R2、A退栈 R3 计算A+ R2 结果R3进栈 9 E 操作数 进栈 R3 E 10 F 操作数 进栈 R3 EF,34,步序 扫描项 项类型 动作 栈中内容 11 / 操作符 F、E退栈 R3 R4 计算E/F 结果R4进栈 12 - 操作符 R4 、 R3退栈 R5 计算R3- R4 结果R5进栈,35,中缀表达式转换为后缀表达式, 把中缀表达式转换为后缀表达式的过程也是一个栈应用的典型例子。 把中缀表达式转换为后缀表达式，可简化求值过程。 在扫描中缀表达式，将它转换为后缀表达式的过程中，只要遇到操作数就直接输出。 遇到操作符时，先把它放在（操作符)栈中，待到以后适当的时刻再将栈中的操作符输出。,36,步序 扫描 项类 动作 栈的变化 输出 项 型,0 #进栈 # 1 A 操作数 # A 2 + 操作符 isp(#) # + A icp(+
