数据结构与算法(C++版)课件第三章 栈和队列.pptx
《数据结构与算法(C++版)课件第三章 栈和队列.pptx》由会员分享,可在线阅读,更多相关《数据结构与算法(C++版)课件第三章 栈和队列.pptx(25页珍藏版)》请在三一文库上搜索。
1、第3章 栈和队列学时分配:学时分配:4 4学时学时3.1 栈3.1.1 栈的定义及运算3.1.2 顺序栈及运算的算法实现3.1.3 链栈及运算的算法实现3.1.4 栈的应用3.1.5 栈与递归3.2 队列3.2.1 队列的定义及运算3.2.2 顺序队列及运算的实现3.2.3 链队列及运算的实现3.3 栈与队列的比较2【学习目标】【学习目标】l 理解栈和队列的概念、运算特点。l 掌握栈和队列的存储以及运算的实现。l 理解栈和队列在解决实际问题中的应用。l 综合运用栈或队列解决实际应用问题。【思维导图思维导图】3.1.1 3.1.1 栈的定义及运算栈的定义及运算1.1.定义:栈(stack)是运算
2、受限的线性表,限制是运算受限的线性表,限制它的插入和删除操作仅在表的一端进行。栈是后它的插入和删除操作仅在表的一端进行。栈是后进先出的线性表(进先出的线性表(last in first outlast in first out),简称),简称 LIFOLIFO表表2.2.术语:栈顶(术语:栈顶(toptop),栈顶元素,栈底栈顶元素,栈底(bottom),bottom),空栈空栈,进栈或入栈,出栈或退栈。进栈或入栈,出栈或退栈。3.3.栈的运算的实例栈的运算的实例3.1 栈3.栈的基本运算有五种:(1)初始化栈 initStack(s):构造了一个空栈s。(2)判栈空empty(s):若栈s为
3、空栈,返回值为“真”(1),否则返回值为“假”(0)。(3)入栈push(s,x):在栈s的顶部插入一个新元素x,x成为新的栈顶元素。(4)出栈pop(s):删除栈s的栈顶元素。(5)读栈顶元素top(s):栈顶元素作为结果返回,不改变栈的状态。4.栈的存储(1)采用顺序方式存储的栈称为顺序栈(sequential stack)(2)采用链接方式存储的栈称为链栈(linked stack)1.顺序栈用C语言描述如下:3.1.2 顺序栈及运算的算法实现#define MAXSIZE 1024 /*栈可能达到的最大容量*/typedef int DataType;typedef struct Da
4、taType dataMAXSIZE;int top;SeqStack;SeqStack *s;/*定义s是一个指向顺序栈的指针*/栈的操作及栈顶指针变化情况2.在顺序栈上实现五种基本运算的C函数(1)初始化栈 首先建立栈空间,然后初始化栈顶指针。eqStack *initSeqStack()SeqStack *s;s=(SeqStack*)malloc(sizeof(SeqStack);s-top=-1;return s;(2)判栈空int empty(SeqStack*s)if(s-top=-1)return 1;else return 0;(3)入栈int push(SeqStack*s
5、,DataType x)if(s-top=MAXSIZE-1)/*栈满不能入栈*/printf(overflow);return 0;s-top+;s-datas-top=x;return 1;(4)出栈void pop(SeqStack*s)/*设栈不空*/s-top-;(5)读栈顶元素DataType top(SeqStack*s)/*设栈不空*/return(s-datas-top);链栈用C语言描述如下:3.1.3 链栈及运算的实现typedef int DataType;typedef struct Node DataType data;struct Node *next;LinkS
6、tack;LinkStack *top;/*top为栈顶指针*/【例3.1】将一个十进制正整数N转换成R进制的数。N N/8(整除)N%8(求余)1835 229 3 低 229 28 5 28 3 4 3 0 3 高3.1.4 栈的应用转换算法中的主要步骤如下:(1)当N0时,将N%r存入栈s中,然后用N/r代替N,直到N=0退出循环。(2)只要栈s不空,就读出栈顶元素输出并把栈顶元素出栈。【例3.2】算术表达式中括号匹配的检查用栈来实现括号匹配检查的原则是,对表达式从左到右扫描。(1)当遇到左括号时,左括号入栈;(2)当遇到右括号时,首先检查栈是否空,若栈空,则表明该“右括弧”多余;否则比
7、较栈顶左括号是否与当前右括号匹配,若匹配,将栈顶左括号出栈,继续操作;否则,表明不匹配,停止操作。(3)当表达式全部扫描完毕,若栈为空,说明括号匹配,否则表明“左括弧”有多余的。u递归:函数、过程或数据结构等对象在其定义的内部直接或间接出现了对自身的引用是一种递归。u递归函数:一个函数在其定义的内部直接调用自身,这个函数就叫做直接递归函数。3.1.5 栈与递归long fact(int n)long f;if(n=0)f=1;else f=n*fact(n-1);return f;main()long m;int n=3;m=fact(n);printf(“%d!=%dn”,n,m);递归调用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法C+版课件第三章 栈和队列 数据结构 算法 C+ 课件 第三 队列
链接地址:https://www.31doc.com/p-21712401.html