三章栈和队列.ppt

《三章栈和队列.ppt》由会员分享，可在线阅读，更多相关《三章栈和队列.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、三章栈和队列 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 栈栈：在表的某一端进行插入和删除操作的 线性表。特点：后进先出 抽象数据数据类型的定义：ADT Stack 数据对象:D=ai|aiElemSet,i=1,2,n,n=0 数据关系:R1=|ai-1,aiD,i=2,n 约定an端为栈顶，a1端为栈底栈的示意图：a1a2:an栈顶栈底进栈 栈顶栈底出栈a2:a1an栈顶栈顶栈顶栈顶栈顶栈顶栈顶栈顶基本操作：InitStack(&s)操作结果：构造一个空栈

2、S DestroyStack(&s)初始条件：栈S已存在操作结果：栈S被销毁 ClearStack(&s)初始条件：栈S已存在操作结果：将S清为空栈 StackEmpty(s)初始条件：栈S已存在操作结果：若栈为空栈，则返回TRUE，否则FALSE StackLength(s)初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度 GetTop(S,&e)初始条件：栈S已存在且非空操作结果：用e返回s的栈顶元素 Push(&s,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&s,&e)初始条件：栈S已存在且非空操作结果：删除s的栈顶元素，并用e返回其值StackTrav

3、erse(S,visit()初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对s的每个数据元素调用函 数visit()。一旦visit()失败，则操作失败ADT Stack二：栈的表示与实现栈的存储结构（两种）顺序存储结构 链式存储结构1.顺序存储结构：利用一组地址连续的存储单元 依次存放自栈底到栈顶的数据 元素结构描述：typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;图示：AEDCBABAtopbasebasetoptopbasetopbase栈顶指针和栈中元素之间的关系规定：top指针指向下一个元素

4、进栈的位置空栈条件：S.top=S.base栈满条件：S.top-S.base=S.stacksize入栈：top指针增加1出栈：top指针减1栈的顺序存储表示：#define STACK_INIT_SIZE 100;/存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量 Typedef struct SElemType *base;/在栈构造之前和销毁之后，base的值为NULL SElemType *top;/栈顶指针 int stacksize;/当前已分配的存储空间，以元素为单位SqStack;基本操作的函数原型：Status InitStack(S

5、qStack&s);/构造一个空栈SStatus DestroyStack(SqStack&s);/销毁栈S，S不再存在Status ClearStack(SqStack&s);/把S置为空栈Status StacjEmpty(SqStack s);/若栈S为空栈，则返回TRUE,否则返回FALSEInt StackLength(SqStack s);返回S的元素个数，即栈的长度StatusGetTop(SqStack s,SElemType&e);/若栈 不为空，则用e返回S的栈顶元素，并返回OK;否则返回ERRORStatus PUSH(SqStack&s,SElemType&e);/插入

6、元素e为新的栈顶元素Status POP(SqStack&s,SElemType&e);/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERRORStatus StackTraverse(SqStack&s,Status(*visit)();/从栈底到栈顶依次对栈中的每个元素调用函数visit()。一旦visit()失败，则操作失败/-基本操作的算法描述（部分)-Status InitStack(SqStack&s)/构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT-SIZE*sizeof(Elemtype);If(!S.base)exi

7、t(OVERFLOW);/存储分配失败S.top=S.base;S.stacksize=STACK _INIT-SIZE;Return OK;/InitStackStatusGetTop(SqStack s,SElemType&e)/若栈 不为空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;/GetTopStatus PUSH(SqStack&s,SElemType&e)/插入元素e为新的栈顶元素 if(S.top-s.base=s.stacksize)/栈满，追加存储空间 S.

8、base=(ElemType*)realloc(s.base,(s.stacksize+CREMENT)*sizeof(elemtype);If(!S.base)exit(OVERFLOW);/存储分配失败s.top=s.base+S.stacksize;s.stacksize+=STACKINCREMENT;*S.top+=e;Return OK;/PushStatus POP(SqStack&s,SElemType&e);/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(S.top=S.base)return ERROR;e=*-s.top;return

9、OK;/Pop栈的链式存储结构：结构与链表结构相同入栈：在表首插入一个结点出栈：删除表首结点链栈示意图：如右图data next栈顶栈底S 栈的应用举例数制转换十进制数N和其它d进制的转换原理：N=(N div d)d+N mod d(其中：div为整除运算，mod 为求余运算例:(1348)10=(2504)8,其运算过程如下：N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2算法：void conversion（）/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制 InitStack(s);/构造空栈 scanf(“%d”,N);

10、While(N)push(s,n%8);N=N/8;While(!StackEmpty)pop(s,e);printf(“%d”,e);/conversion括号匹配的检验：设表达式中只有，()思想：利用栈解决，依次输入表达式每一个字符，若是左括号，将其入栈，若是右括号，则出栈左括号与其匹配，循环执行，直到表达式输入结束。行编辑程序思想：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出错，并在发现有误时及时更正算法：Void LinEdit()/利用字符栈S，从终端接收一行并传送至调用过程的数据区InitStack(S);/Ch=getchar();/从终

11、端接收第一个字符While(ch!=EOF)/EOF 为全文结束符 while(ch!=EOF&ch!=n)switch(ch)case#:Pop(s,c);break;/仅当栈非空时退栈 case:ClearStack(s);break;/重置S为空栈 default:push(S,ch);break;/有效字符进栈，未考虑栈满情况 ch=getchar();/从终端接收下一个字符 将从栈底到栈顶的栈内字符传送至调用过程的数据区；ClearStack(S);/重置S为空栈 if(ch!=EOF)ch=getchar();DestroyStack(S);/LineEdit表达式求值表达式组成：

12、操作符（常量，变量）；运算符（+,-,，）；界限符（(),#,结束符）；运算规则：先乘除，后加减；从左算到右 先括号内，后括号外，算符优先 为实现算符优先算法，使用两个工作栈。一个称为OPTR，用以寄存运算符；另一个为OPND，用以寄存操作数或运算结果。算法思想：首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕。得到表达式结束在OPND栈中相应操作有三种情况：栈顶运算符输入运算符，从OPND栈中出两个操作运算符出栈，对栈顶运算符进行运算，将结果入OP

13、ND栈算符1 和2之间的优先关系：1 2 1 的优先权高于2算符间的优先关系表 +-*/(#=2 1+-*/()#.算法：OperandType EvaluateExpression()/算术表达式求值的算符优先算法/OP为运算符集合InitStack(OPND);push(OPTR,#);InitStack(OPND);c=getchar();While(c!=#|GetTop(OPND)!=#)if(!In(c,Op)Push(OPND,c);c=getchar();/不是运算符则进栈/while return GetTop(OPND);/EvaluateExpressionelse sw

14、itch(Precede(GetTop(OPND),c)case /退栈并将运算结果入栈 Pop(OPTR,theta);pop(OPND,b);pop(OPND,a);push(OPND,operate(a,theta,b);break;/switch 队列（Queue)定义：在表的一端进行插入，在另一端进行删除操作线性表特点：先进先出队列示意图：a1a2a3an队尾出队列入队列队头队列的抽象数据类型定义：ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=|ai-1,aiD,i=2,n约定其中ai端为队列头,an端为队列尾。基本操作：Initq

15、ueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列 Q已存在。操作结果：若Q为空队列，则返回TRUE,否则 FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueu

16、e(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。QueueTraverse(Q,visit()初始条件：Q已存在且非空。操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ADT Queue 和栈类似，在本书以后各章中引用的队列都应是如上定义的队列类型。队列的数据元素类型在应用程序内定义。双端队列(Deque)定义：是限定插入和删除操作在表的两端进行的线性表，这两端分别叫端点1和端点2如图：a1a2a3an端1端2插入删除插入删除链表的两种存储表示：链队列队列的链式表示和实现循环队列队列的顺序表示和实现链

17、队列队列的链式表示和实现定义：用链表表示的队列简称链队列结构与链表相同：链表中只有表首指针 队列增加一个尾指针为操作方便，给链队列添加一个头结点，并令头指针指向头结点如图：data nextQ.frontQ.rear队头队尾当头指针和尾指针均指向头结点时，链队列为空如图：Q.frontQ.rear链队列的操作其实就为单链表的插入和删除操作的特殊情况，只要修改尾指针或头指针，下图即展示了这两种操作指针变化情况xQ.frontQ.rear元素x入队列xyyx元素y入队列元素x出队列Q.frontQ.rearQ.frontQ.rear队列的链式存储结构：Typedef struct QNode QE

18、lemType data;struct Qnode *next;Qnode,*QueuePtr;Typedef struct QueuePtr front;QueuePtr rear;LinkQueue;/-基本操作的函数原型说明-Status InitQueue(LinkQueue&Q)/构造一个空队列QStatus DestroyQueue(LinkQueue&Q)/销毁队列Q,Q不再存在Status ClearQueue(LinkQueue&Q)/将Q清为空队列Status QueueEmpty(LinkQueue Q)/若队列Q为空队列，则返回TRUE,否则返回FALSEInt Que

19、ueLength(LinkQueue Q)/返回Q的元素个数，即为队列的长度Status GetHead(LinkQueue Q,QElemType&e)/若队列不空，则用e返回Q的队头元素，并返回OK;否则返回ERRORStatus EnQueue(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，用e 返回其值，并返回OK;/否则返回ERRORStatus QueueTraverse(LinkQueue Q,visit()/从队头到队尾依次对队列Q中每

20、个元素调用函数visit()。一旦visit失败，则操作失败。/-基本操作的算法描述（部分）-Status InitQueue(LinkQueue&Q)/构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode);if(!Q.front)exit(OVERFLOW);Q.front next=NULL;return OK;Status DestroyQueue(LinkQueue&Q)/销毁队列Q while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;S

21、tatus EnQueue(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(Qnode);if(!p)exit(OVERFLOW);/存储分配失败 p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，用e返回其值，/并返回OK;否则返回ERROR if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-

22、data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;循环队列队列的顺序表示和实现定义：除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，需设两各指针front和rear分别指示队列头元素和队尾元素的位置说明：Q.front 表示指向队首元素 Q.rear表示指向队尾元素下一个位置如何判断队空还是队满：有两种处理方法判断：其一是另设一个标志位以区别队 列是“空”还是“满“其二是少用一个元素空间，约定以 “队列头指针在队列尾指针的下一 个位置（指环状的下一个位置）上作位队列”满“的标志 入队：Q.

23、baseQ.rear=x;Q.rear=(Q.rear+1)%maxsize出队：e=Q.baseQ.front Q.front=(Q.front+1)%maxsize循环队列示意图：队列10Maxsize-1Q.frontQ.rearJ3J2J1J3J6J5012345Q.frontQ.rearQ.frontQ.rearQ.frontQ.rearQ.frontQ.rear空队列J1,J2,J3相继队列J1,J2相继被删除J4,J5,J6相继插入队列之后J4被删除012345J3J4J5Q.frontQ.rear012345J5J6J7J8J3J4Q.frontQ.rear012345Q.fr

24、ontQ.rear空队列队列满时一般情况/-循环队列队列的顺序存储结构-#define MAXQSIZE 100 /最大队列长度Typedef struct QElemType *base;/初始化的动态分配存储空间 int front;/头指针，若队列不空，指向队列头元素 int rear;/尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/-循环队列的基本操作的算法描述-Status InitQueue(SqQueue&Q)/构造一个空队列Q Q.base=(ElemType*)malloc(MAXQSIZE*sizeof (ElemType);if(!Q.base)exit

25、(OVERFLOW);/存储分配失败 Q.front=Q.rear=0;return OK;Int QueueLength(SqQueue Q)/返回Q的元素个数，即队列的长度 return(Q.rear Q.front+MAXSIZE)%MAXSIZE;Status EnQueue(SqQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满 Q.baseQ.rear=e;Q.front=(Q.front+1)%MAXQSIZE;return OK;Statue DeQueue(SqQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，用e返回其值，/并返回OK;否则返回ERROR if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;