栈和队列PPT课件

第三章栈和队列栈和队列是两种特殊的线性 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf ，是操作受限的线性表，称限定性DS 3.1栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 栈的存储结构 栈顺序存储表示：#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct {Selemtype*base;//在栈构造之前和销毁之后，base的值为NULL Selemtype*top;//栈顶指针 intstacksize;//当前已分配的存储空间，以元素为单位 }sqstack;栈的基本操作：P46栈顶指针top,指向实际栈顶后的空位置，初值为0进栈A出栈栈满BCDEFtop=0,栈空，此时出栈，则下溢top=stacksize,栈满，此时入栈，则上溢栈的操作演示： 构造一个空栈statusinitstack(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; } 置栈为空栈statusclearstack(sqstack&s) {if(!s.base) exit(error); s.top=s.base; returnOK; } 判空intstackempty(sqstacks) {returns.base==s.top; } 在一个程序中同时使用两个栈 链栈 入栈 出栈 栈的应用 数值转换 回文游戏：顺读与逆读字符串一样（不含空格）1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文 括号匹配的检验： 行编辑程序 迷宫求解字符串：“madamimadam” 表达式求值中缀表达式后缀表达式（RPN)a*b+cab*c+a+b*cabc*+a+(b*c+d)/eabc*d+e/+中缀表达式：操作数栈和运算符栈(1)对每种运算符赋予一个优先数(2)可以使用两个工作栈：数栈(NS)；运算符栈(OS)。(3)编译程序自左向右扫描至语句结束符，处理的 原则 组织架构调整原则组织架构设计原则组织架构设置原则财政预算编制原则问卷调查设计原则 是：凡遇到操作数，一律进数栈；当遇到运算符时，则将该运算符的优先数与运算符栈中的栈顶元素的优先数相比较。若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈，然后继续比较该运算符与栈顶元素的优先数。---ReversePolishNotation例计算2+4-3*6后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1例计算4+3*5后缀表达式：435*+ 3.2队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) 双端队列 链队列 结点定义typedefstructQNode{Qelemtypedata;structQNode*next;}Qnode,*QueuePtr;设队首、队尾指针front和rear,front指向头结点，rear指向队尾typedefstruct{QueuePtrfront;QueeuPtrrear;}LinkQueue; 构造空队列 销毁队列QstatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode)); if(!Q.front) exit(overflow); Q.front->next=NULL; returnOK; }statusDestoryQueue(LinkQueue&Q) {while(Q.front) {Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } returnOK; } 入队算法 出队算法statusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(overflow); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK; }statusDeQueue(LinkQueue&Q,QElemType&e) {if(Q.front==Q.rear)return(error); p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); returnOK; } 队列的顺序存储结构J1J2J3设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[++front]; 存在问题设顺序空间为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出—真溢出 当front-1,rear=M-1时，再有元素入队发生溢出—假溢出 解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0; 实现：利用“模”运算 入队：rear=(rear+1)%M;sq[rear]=x; 出队：front=(front+1)%M;x=sq[front]; 队满、队空判定条件队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front 构造空队列 队列长度statusinitqueue(sqQueue&Q){Q.base=(Qelemtype*)malloc(MAXQUEUESIZE*sizeof(Qelemtype));if(!Q.base)exit(OVERFLOW); Q.front=Q.rear=0;returnOK;}intqueuelength(sqQueueQ) {return(Q.rear-Q.front+MAXQUEUESIZE)%MAXQUEUESIZE; }#defineMAXQUEUESIZE100typedefstruct{Qelemtype*base;intfront，rear;}sqQueue; 入队算法 出队算法statusEnQueue(SqQueue&Q,QelemTypee){if((Q.rear+1)%MAXQUEUESIZE==Q.front) exit(overflow); Q.rear=(Q.rear+1)%MAXQUEUESIZE;Q.base[Q.rear]=e; returnOK;}statusDeQueue(SqQueue&Q,QelemType&e) {if(Q.front==Q.rear)exit(error); Q.front=(Q.front+1)%MAXQUEUESIZE; e=Q.base[Q.front];returnOK; }---ReversePolishNotation