[其它]数据结构第三章栈和队列.ppt
第三章 栈和队列,第三章 栈和队列,本章介绍在程序设计中常用的两种数据结构 栈和队列,第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.4 队列,3.1 栈3.1.1 栈的概念3.1.2 栈的顺序存储和实现3.1.3 栈的链式存储和实现,3.1 栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1,a2,.,ai-1,ai,ai+1,an）,3.1.1 栈的概念一 什么是栈,3.1 栈,栈的示意图,出栈,进栈,栈的特点后进先出,第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素,3.1 栈,二 栈的基本操作1）构造一个空栈S；2）进栈操作Push3）出栈操作Pop4)取栈顶元素top,3.1 栈,top,base,base,A,A,栈操作图示,空栈,A进栈,B C D E 进栈,E D C 出栈,3.1 栈,3.1.2 栈的顺序存储和实现 一、栈的顺序存储结构,1 栈的顺序存储结构,#define MAX 50struct sqstackelemtype stackMAX;int top;,3.1 栈,约定栈顶指针指向栈顶元素的下一个位置,3.1 栈,1)进栈操作 void Push(int x,struct sqstack*s)if(s-top=MAX)printf(“overflow”);else s-stacks-top=x;s-top+;,2）出栈操作int pop(struct sqstack*s)if(s-top=0)printf(“underflow”);return(NULL);s-top-;return s-stacks-top;,共享栈,#define MAX 100Int stackMAX,top1=0,top2=MAX-1;,3.1 栈,2 栈的链式存储和实现栈的链式存储结构，也称链栈，如图所示：,在前面学习了线性链表的插入删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法,3.1 栈,(1)进栈算法NODE*top;Void push(int x)NODE*p=(NODE*)malloc(sizeof(NODE);p-data=x;p-next=top;top=p;,3.1 栈,(2)出栈算法NODE*pop();NODE*p;if(top=NULL)return(NULL);p=top;top=p-next;return(p);,小 结 1 栈是限定仅能在表尾一端进行插入、删除操作的线性表；2 栈的元素具有后进先出的特点；3 栈顶元素的位置由一个称为栈顶指针的 变量指示，进栈、出栈操作要修改栈顶指针；,3.1 栈,3.2 栈的应用举例,例1 数制转换 对于输入的任意一个非负十进制数，显示输出与其等值的八进制数,数制转换方法 N=(Ndiv8)10 8+N mod 8 N：十进制数，div：整除运算，mod：求余运算；(1348)10=283+582+08+4=(2504)8 N 1348 168 21 2 N div 8 168 21 2 0 N mod 8 4 0 5 2,计算时从低位到高位顺序产生八进制数的各个数位,结果：2 5 0 4,显示时按从高位到低位的顺序输出,3.2 栈的应用举例,void conversion()InitStack(s);/建空栈 scanf(“%d”,算法3.7,3.2 栈的应用举例,例2 表达式求值1）问题的提出 设计一个小计算器:对键入的表达式进行求值。,高级语言中的赋值语句：变量=表达式；,2）表达式的构成 操作数+运算符+界符（如括号）3）表达式的求值：例 5+6(1+2)-4 按照四则运算法则，上述表达式的计算过程为：5+6(1+2)-4=5+6 3-4=5+18-4=23-4=19,3.2 栈的应用举例,1,2,3,4,4）算符优先关系表 表达式中任何相邻运算符c1、c2的优先关系有：c1c2：c1的优先级高于c2,算符间的优先关系表,注：c1 c2是相邻算符，c1在左，c2在右,3.2 栈的应用举例,5 算符优先算法,从左向右扫描表达式：遇操作数保存；遇运算符号cj与前面的刚扫描过的运算符ci比较 若cicj 则说明ci是已扫描的运算符中优先级最高者，可进行运算；若ci=cj 则ci为（，cj 为），说明括号内的式子已计算完，需要消去括号；,5+4(1+2)-6,后面也许有优先级更高的算符,+,+,(,后保存的算符有优先级高,用两个栈分别保存扫描过程中遇到的操作数和运算符,算法,算符比较算法,Char Precede(char c1,char c2)int c_temp1,c_temp2;switch(c1)case*:case/:c_temp1=4;break;case+:case-:c_temp1=2;break;.switch(c2)case*:case/:c_temp2=3;break;case+:case-:c_temp2=1;break;.,续,if(c_temp1c_temp2)return();,3.2 栈的应用举例,在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符,一个是OPND栈，用以保存操作数或运算结果。int express()/运算数栈，OP为运算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);w=qetchar();While(w!=#|GetTop(OPTR)!=#)if(!In(w,OP)Push(OPND,w);w=getchar();/不是运算符则进栈 else/In(w,OP)判断c是否 是运算符的函数,3.2 栈的应用举例,续 switch(Precede(GetTop(OPTR),w)case:/新输入的算符c优先级低，即栈顶算符优先权高，/出栈并将运算结果入栈OPND op=Pop(OPTR);b=Pop(OPND);a=Pop(OPND);Push(OPND,Operate(a,op,b);break;return GetTop(OPND);,表达式求值示意图：5+6(1+2)-4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18=23,23-4=19,3.4 队列3.4.1 队列的概念3.4.2 循环队列 队列的顺序存储和实现3.4.3 队列的链式存储和实现,34 队列,3.4.1 队列的概念一 什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,34 队列,a1 a2 a3 an,入队列,队头,队尾,出队列,队 列 的 示 意 图,队列的特点先进先出,第一个入队的元素在队头，最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素,34 队列,二 队列的基本操作1）初始化操作 2）销毁操作 3）置空操作 4）判空操作 5）取队头元素操作 6）入队操作 7）出队操作,(b)J1,J2相继入队列,(c)J1出队,(d)J3,J4和J5相继入队之后,J2出队,（a)空队列,3.4 队列,front,rear均为整数用箭头指示只是为了直观,34 队列,#define MAX 50/*数据结构定义*/struct squeueelemtype queueMAX;int front;int rear;初始化Init（struct squeue*q)q-front=-1;q-rear=-1;,int insert_queue(int x，struct squeue*q)/*入队列*/if(*q).rear=MAX-1)return(0);q-rear+;q-queueq-rear=x;return(1);int del_queue(struct squeue*q)/*出队列*/if(q-rear=q-front)return(0);q-front+;return(q-queueq-front);,3.4 队列,3.循环队列,(b)队空,(c)队满,队空、队满都有front=rear,J6,3.4 队列,有两种方法：1）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件:front=rear+1;,front,（d）,3.4 队列,1）初始化操作 功能：建一个空队列Q；算法：struct squeue elemtype queueMAX;int front;int rear;int InitQueue_Sq(struct squeue*q)/构造一个空队列Q q-front=q-rear=0;return(1),二 循环队列的基本操作算法,建一个空队列Q,3.4 队列,6）入队操作 功能：将元素 x 插入队尾,元素 x 入队前,元素 x 入队后,3.4 队列,求余运算,3.4.2 循环队列队列的顺序存储和实现 int insert_queue(int x,struct squeue*q)/*入队列*/if(q-rear+1)%MAX=q-front)return(0);q-rear=(q-rear+1)%MAX;q-queueq-rear=x;return(1);,3.4 队列,7）出队操作 功能：删除队头元素；,3.4 队列,int del_queue(struct squeue*q)/*出队列*/if(q-rear=q-front)return(0);q-front=(q-front+1)%MAX;return(q-queueq-front);,3.4.3 链队列队列的链式存储结构和实现一 链队列,front,rear,空链队列,front,rear,链队列图示,3.4 队列,3.4 队列,二 链队列的类型定义,struct node/链队列结点的类型定义int data;struct node*next;typedef struct node NODE NODE*front,*rear;,3.4 队列 入列运算,Void addqlink(int x)NODE*p;p=(NODE*)malloc(sizeof(NODE);p-data=x;p-next=NULL;rear-next=p;rear=p;,3.4 队列 出列运算,NODE*deleqlink()NODE*p;if(front=rear)return(NULL);p=front-next;front-next=p-next;if(front-next=NULL)rear=front;return(p);,3.4 队列 元素记数运算,int count()int i;NODE*p;if(front=rear)return(0);for(p=front-next,i=1;p!=rear-next)i+;p=p-next;return(1);,小 结 1 队列是限定仅能在表尾一端进行插入，表头一端删除 操作的线性表；2 队列中的元素具有先进先出的特点；3 队头、队尾元素的位置分别由称为队头指针和队尾指针 的变量指示，4 入队操作要修改队尾指针，出队操作要修改队头指针；,
