《3-第三章.ppt》由会员分享，可在线阅读，更多相关《3-第三章.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 栈和队列l栈和队列是两种特殊的线性表应用l3.1 栈（stack）栈的定义和特点l定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈l特点：先进后出（FILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)栈的表示和实现l顺序栈实现：一维数组sMtop=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop
2、123450ABCDEFtoptoptoptoptoptop栈空lADT Stack l数据对象：D|ElemSet,i=1,2,.,n,n0 l数据关系：数据元素间呈线性关系。l基本操作：lInitStack（&S）：初始化操作。构造一个空栈 S。lClearStack（&S）：将S清为空栈。l Empty（&S）：判断栈是否为空，若为空栈，则返回值为 l “TRUE”，否则返回值为“FALSE”。l Pop（&S）：出栈函数。若S不为空，则从栈中删除栈顶元素，l 并返回栈顶元素的值，否则返回NULL。l Full（&S）：判断栈是否为满，若为满栈，则返回值为“TRUE”，l 否则返回值为“
3、FALSE”。l Push（&S，t）：入栈操作。若S不为满，则插入t为栈中栈顶元l 素，否则返回NULL。l GetTop（&S）：函数返回栈顶元素的值。l堆栈的实现l#include l#define MAXITEM 200 ltypedef enum FALSE，TRUE bool;ltypedef struct l intitemMAXITEM;l int top;l Stack;l Stack s;lvoid ClearStack(Stack *s)l l s-top =0;l l l bool Empty(Stack *s)l l if (s-top=0)l return TRUE
4、;l else l return FALSE;l lbool Full(Stack*s)l l if (s-top=MAXITEM-1)l return TRUE;l elsel return FALSE;l lbool Push(stack *s,int t)l l if(Full(s)l return FALSE;l else l l s-items-top =t;l s-top+;l return TRUE;l l lint Pop(stack *s)l l if (Empty(s)l return FALSE;l else l l s-top-;l return s-items-top
5、;l l lint GetTop(stack *s)l l if (Empty(s)l l return FALSE;l elsel return s-items-top;l l l链栈栈顶栈顶 .topdata link栈底结点定义入栈算法出栈算法typedef struct node int data;struct node *link;JD;.栈底toptopxptop .栈底topq栈的应用l过程的嵌套调用r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程3例例 递归的执行情况分析递归的执行情况分析 l递归过程及其实现递归：函数直接或间接的调用自身叫实现：建立
6、递归工作栈void print(int w)int i;if(w!=0)print(w-1);for(i=1;i1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题算法：执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示n x y z 返回地址 l回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文
7、l多进制输出：字符串：“madam im adam”例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732v 括号匹配的检验 假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（）（）（）v 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。l表达式求值 中缀表达式 后缀表达式（RPN)a*b+c ab*c+a+b*c abc*+a+(b*c+d)/e abc*d+e
8、/+中缀表达式：操作数栈和运算符栈例 计算 2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12错误!24+36*-l3.2 队列队列的定义及特点l定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端l队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)l双端队列a1 a2 a3.an 端1端2入队出队入队出队队列lADT Queuel 数据对象：D|ElemSet,i=1,2,.,n,n0 l 数据关系：数
9、据元素间呈线性关系。l 基本操作：l InitQueue(&Q)：构造一个空队列 Q。l ClearQueue(&Q)：将已存在的队列Q清为空队列。l QueueEmpty(Q)：若Q为空队列，则返回TRUE，否则l 返回FALSE。l EnQueue(&Q,e)：插入元素e为Q的新的队尾元素。l DeQueue(&Q,&e)：删除Q的队头元素，并用e返回其值。l GetHead(&Q,&e)：用e返回Q的队头元素。l链队列l结点定义typedef struct Qnode QElemType data;struct Qnode *next;Qnode,*QueuePtr;Typedef st
10、ruct QueuePtr front;QueuePtr rear;/LinkQueue;头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队队列的顺序表示和实现l实现：用一维数组实现sqMfront=0rear=0123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队
11、尾元素；front指示队头元素位置初值front=rear=0空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront从1开始少用一元素l存在问题设数组维数为M，则：当front=0,rear=M-1时，再有元素入队发生溢出真溢出当front0,rear=M-1时，再有元素入队发生溢出假溢出l解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-11frontrear.实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front