计算机软件技术基础 课件.ppt

《计算机软件技术基础 课件.ppt》由会员分享，可在线阅读，更多相关《计算机软件技术基础 课件.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机软件技术基础,教 师：曾晓东电 话：13679007201E_mail: ,3.4 栈,一、栈的定义二、栈的运算三、栈的存储结构及算法四、栈的应用,计算机软件技术基础,数据结构栈和队列,一、栈的定义,栈是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。设栈s=(a1,a2,.,an)，a1称为栈底元素，an称为栈顶元素。栈中元素按a1,a2,.,an次序进栈，又按an,.,a2,a1次序退栈。因此栈的操作特点是：后进先出（LIFO）；n=0时称为空栈。,计算机软件技术基础,数据结构栈和队列,二、栈的运算,1.初始化栈I

2、NISTACK(S)将栈S置成空栈2.判空栈ISEMPTY(S)若栈S是空栈，返回“真”，否则返回“假”3.进栈PUSH(S,x) 在栈S顶部插入（压入）元素x4.出栈POP(S) 若栈S不空，删除顶部元素5.取栈顶GETTOP(S)取栈顶元素，并不改变栈中内容,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,1.顺序栈1)类型定义顺序栈用向量作为栈的存储结构，可用一维数组s1:m表示。其中m表示栈的最大容量。用一个简单变量top来指示栈顶位置，称为栈顶指示器。top=0表示栈空，top=m表示栈满。类型定义struct SeqStackelemtype stackMAXSIZE

3、;int top;,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,2）顺序栈初始化 操作:建一空栈，将栈顶位设置为-1 接口：入口和出口参数均为堆栈指针s 算法描述：令栈顶位 s.top为-1 函数实现：void iniStack(SeqStack ,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,3)进栈算法 操作:先将栈顶位置加一将数据放入栈顶位置 接口： 入口参数：堆栈指针s，新数据元素x出口参数: 堆栈指针s函数值：成功则返回 1 ( 用true表示), 失败则返回 0 ( 用false表示),计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,

4、(3)算法描述,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,(4) 函数实现int push(SeqStack ,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,4)出栈算法(1) 操作取栈顶位置内数据.再将栈顶位置减一(2) 接口 入口参数：堆栈指针s出口参数: 堆栈指针s函数值： 成功则返回数据元素x, 失败则返回NULL,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,(3) 算法描述,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,(4) 函数实现elemtype pop(SeqStack ,计算机软件技术基础,数据结构栈和队

5、列,三、栈的存储结构及算法,5)双栈操作顺序栈的缺点：栈满后不能进行进栈操作，否则将产生“上溢”错误同时使用同类的两个栈，充分利用剩余空间两栈共用一个存储空间，分别从两端向中间增长,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,2.链栈链栈是用链表作为栈的存储结构，top为栈顶指针，指示栈顶元素位置，若top=NULL,则表示栈空。链栈一般不会出现上溢，除非内存中已不存在可用空间。使用单链表，不设头结点插入和删除仅在表头一端 栈顶top ：指始结点，浮动空栈用 top=NULL 实现 链栈结点动态分配，空间无限链栈定义与单链表相同 struct link *top；,.,计算机

6、软件技术基础,数据结构栈和队列,四、栈的应用,表达式求值1）高级语言中的表达式是用人们熟悉的公式形式书写的，编译系统要根据表达式的运算顺序将它翻译成机器指令序列。2）为解决运算顺序问题，把运算符分成若干等级，称为优先数。3）为进行表达式的翻译，需设立两个栈，分别存放操作数(NS)和运算符(OS)。,计算机软件技术基础,数据结构栈和队列,四、栈的应用,4）首先在OS中放入表达式结束符“#”，然后自左至右扫描表达式，根据扫描的每一个符号作如下不同处理： 若为操作数，将其压入NS栈 若为运算符，需看当前OS的栈顶元素：若OS栈顶运算符小于或等于当前运算符的优先数，则将当前运算符压入OS栈。若OS栈顶

7、运算符大于当前运算符的优先数，则从NS栈中弹出两个操作数，设为x、y，再从OS栈中弹出一个运算符，设为，由此构成一条机器指令：y x T，并将结果T送入NS栈。 若当前运算符为“#”，且OS栈顶也为“；”，则表示表达式处理结束，此时NS栈顶的元素即为此表达式的值。,计算机软件技术基础,数据结构栈和队列,四、栈的应用,5)算符优先,计算机软件技术基础,数据结构栈和队列,四、栈的应用,6)函数实现double Exp()inistack(OS); inistack(NS);/初始化栈OS和NS push (OS,#); /在OS栈中压入结束符t=0; /t=0表示扫描下一个符号 while (t!

8、=2) /当处理没有结束时循环if (t=0) w=getchar(); /读取一个符号if (w为操作数) push(NS,w); /操作数压NS栈else q=top(OS); /查看OS栈顶元素 if (qfront=(q-rear+1)%MAXSIZE)队尾指针加一 q-rear = (q-rear+1)%MAXSIZE将数据放入队尾 q-queueq-rear=x返回true 接口： 入口参数：队列指针q，新数据元素x出口参数: 函数值：成功true;失败false,计算机软件技术基础,数据结构栈和队列,二、顺序队列,(3)算法描述,计算机软件技术基础,数据结构栈和队列,二、顺序队列

9、,(4)函数实现int enQueue(SeqQueue ,计算机软件技术基础,数据结构栈和队列,二、顺序队列,3、循环队列的出队操作 操作:若队列空，返回NULL(q-front= q-rear )队头指针加一q-front=(q-front+1)%MAXSIZE返回队头数据q-queueq-front 接口： 入口参数：队列指针q，出口参数: 函数返回值：成功：数据元素;失败返回NULL,计算机软件技术基础,数据结构栈和队列,二、顺序队列,(3)算法描述,计算机软件技术基础,数据结构栈和队列,二、顺序队列,(4)函数实现elemtype dlQueue(SeqQueue ,计算机软件技术基

10、础,数据结构栈和队列,3.5 队列,三、链队列链队列是用链表作队列的存储结构，当队列的容量无法预先估计时采用。在链队列中设一个头结点，头指针front始终指向头结点，尾指针rear指向队尾元素，当rear=front表时队空。结点动态分配，不会溢出链队列结点定义与单链表一样,q,计算机软件技术基础,数据结构栈和队列,三、链队列,1、结点结构定义:struct LNode elemtype data;/ 数据域LNode *next; / 指针域;链队列结构定义:struct LinkQueue LNode *front, *rear;/ 队头、队尾指针;,计算机软件技术基础,数据结构栈和队列,三、链队列,2、插入int enQueue(LinkQueue /失败,计算机软件技术基础,数据结构栈和队列,三、链队列,3、删除void dlQueue(LinkQueue ,计算机软件技术基础,数据结构栈和队列,3.5 队列,四、队列的应用任务调度打印任务多用户资源竞争问题主机与外设速度不匹配问题消息队列排队模拟,计算机软件技术基础,数据结构栈和队列,3.5 队列,五、小结1、理解队列的概念和特点2、理解队的假溢出现象3、掌握循环队列判断空和满的条件4、掌握进/出队列的算法,计算机软件技术基础,数据结构栈和队列,