栈和队列PPT课件.ppt

《栈和队列PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的存储结构栈顺序存储表示：#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{Selemtype*ba

2、se;//在栈构造之前和销毁之后，base的值为NULLSelemtype*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}sqstack;栈的基本操作：P46base123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEFtop=0,栈空，此时出栈，则下溢top=stacksize,栈满，此时入栈，则上溢toptoptoptoptop123450ABCDEFtoptoptopbasetopbase栈的操作演示：top构造一个空栈statusi

3、nitstack(sqstack&s){s.base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype));if(!s.base)exit(overflow);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;}销毁栈statusdestorystack(sqstack&s){if(!s.base)exit(error);free(s.base);s.base=s.top=NULL;returnOK;}置栈为空栈statusclear

4、stack(sqstack&s){if(!s.base)exit(error);s.top=s.base;returnOK;}判空intstackempty(sqstacks){returns.base==s.top;}0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈链栈栈顶^…...top栈底^…...栈底toptopxp入栈top^…...栈底topq出栈栈的应用数值转换例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top732回文游戏：顺读与逆读

5、字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文括号匹配的检验：行编辑程序迷宫求解字符串：“madamimadam”表达式求值中缀表达式后缀表达式（RPN)a*b+cab*c+a+b*cabc*+a+(b*c+d)/eabc*d+e/+中缀表达式：操作数栈和运算符栈(1)对每种运算符赋予一个优先数(2)可以使用两个工作栈：数栈(NS)；运算符栈(OS)。(3)编译程序自左向右扫描至语句结束符，处理的原则是：凡遇到操作数，一律进数栈；当遇到运算

6、符时，则将该运算符的优先数与运算符栈中的栈顶元素的优先数相比较。若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈，然后继续比较该运算符与栈顶元素的优先数。例计算2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1top4top

7、43top735top例计算4+3*5后缀表达式：435*+top415top193.2队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)双端队列a1a2a3…………………….an端1端2入队出队入队出队链队列结点定义typedefstructQNode{Qelemtypedata;structQNode*n

8、ext;}Qnode,*QueuePtr;头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾typedefstruct{QueuePtrf