《三章栈和队列.ppt》由会员分享,可在线阅读,更多相关《三章栈和队列.ppt(46页珍藏版)》请在三一文库上搜索。
1、第三章 栈和队列,栈 栈的应用举例 队列,栈,栈: 在表的某一端进行插入和删除操作的 线性表。 特点: 后进先出 抽象数据数据类型的定义: ADT Stack 数据对象:D=ai|aiElemSet,i=1,2,n, n=0 数据关系:R1=|ai-1,aiD,i=2,n 约定an端为栈顶,a1端为栈底,栈的示意图:,a1,a2,:,an,进栈,栈底,出栈,a2,:,a1,an,基本操作: InitStack (&s) 操作结果:构造一个空栈S DestroyStack(& s) 初始条件:栈S已存在 操作结果:栈S被销毁 ClearStack(& s) 初始条件:栈S已存在 操作结果:将S清
2、为空栈,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返回其值 StackTraverse(S,visit() 初始条件:栈S已存在且非空 操作结果:从栈底到栈顶依次对s的每个数据元素调用函
3、 数visit()。一旦visit()失败,则操作失败 ADT Stack,二:栈的表示与实现 栈的存储结构(两种) 顺序存储结构 链式存储结构 1.顺序存储结构:利用一组地址连续的存储单元 依次存放自栈底到栈顶的数据 元素 结构描述:typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,图示:,top,base,base,top,top,base,top,base,栈顶指针和栈中元素之间的关系,规定:top指针指向下一个元素进栈的位置 空栈条件:S.top=S.base 栈满条件:S.top-S.bas
4、e=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 (SqStack /构造一个空栈S,Sta
5、tus DestroyStack (SqStack 返回S的元素个数,即栈的长度,StatusGetTop(SqStack s,SElemType /从栈底到栈顶依次对栈中的每个元素调用函数visit()。一旦visit()失败,则操作失败,/-基本操作的算法描述(部分)- Status InitStack(SqStack /InitStack,StatusGetTop(SqStack s,SElemType ,If(!S.base) exit (OVERFLOW);/存储分配失败 s.top=s.base+S.stacksize; s.stacksize+=STACKINCREMENT; *
6、S.top+=e; Return OK; /Push Status POP(SqStack /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 (
7、 ) /对于输入的任意一个非负十进制整数,打印输出与其等值的八进制 InitStack( s); /构造空栈 scanf (“% d”,N); While (N) push (s, n% 8); N=N/8; While (! StackEmpty ) pop(s,e); printf( “% d”, e); /conversion,括号匹配的检验: 设表达式中只有 ,( ) 思想:利用栈解决,依次输入表达式每一个字符,若是左括号,将其入栈,若是右括号,则出栈左括号与其匹配,循环执行,直到表达式输入结束。 行编辑程序 思想:设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区
8、。允许用户输入出错,并在发现有误时及时更正 算法: Void LinEdit ( ) /利用字符栈S,从终端接收一行并传送至调用过程的数据区 InitStack( S);/,Ch=getchar( ); /从终端接收第一个字符 While (ch !=EOF) /EOF 为全文结束符 while (ch!=EOF /从终端接收下一个字符 ,将从栈底到栈顶的栈内字符传送至调用过程的数据区; ClearStack (S);/重置S为空栈 if (ch !=EOF) ch=getchar(); DestroyStack(S); /LineEdit 表达式求值 表达式组成:操作符(常量,变量); 运算
9、符 (+,-,,); 界限符 (( ),#,结束符); 运算规则 :先乘除,后加减; 从左算到右 先括号内,后括号外,算符优先,为实现算符优先算法,使用两个工作栈。一个称为OPTR, 用以寄存运算符;另一个为OPND,用以寄存操作数或运 算结果。 算法思想: 首先置操作数栈为空栈,表达式起始符“#”为运算符栈的栈底元素 依次读入表达式中每个字符,若是操作数则进OPND栈, 若是运算符,则和OPTR栈的栈顶运算符比较优先权作相应操作,直至整个表达式求值完毕。得到表达式结束在OPND栈中 相应操作有三种情况: 栈顶运算符输入运算符优先级,输入运算符入栈,读下一个字符,栈顶运算符=输入运算符优先级,
10、是( ) 脱(),( 出栈并抛弃 是#说明表达式结束,读下一个字符 3.栈顶运算符输入运算符,从OPND栈中出两个操作运算符出栈,对栈顶运算符进行运算,将结果入OPND栈 算符1 和2之间的优先关系: 1 2 1 的优先权高于2,算符间的优先关系表, 2, 1,+ - * / ( ) #,.,算法: OperandType EvaluateExpression() /算术表达式求值的算符优先算法 /OP为运算符集合 InitStack (OPND); push (OPTR,#); InitStack (OPND); c=getchar( ); While(c!=#|GetTop(OPND)!=
11、#) if (! In(c,Op) Push (OPND, c); c=getchar( ); /不是运算符则进栈 /while return GetTop(OPND); /EvaluateExpression,else switch (Precede(GetTop(OPND),c) case /退栈并将运算结果入栈 Pop(OPTR,theta); pop(OPND,b); pop(OPND,a); push(OPND, operate(a,theta,b); break; /switch,队列(Queue),定义:在表的一端进行插入,在另一端进行删除操作线性表 特点:先进先出 队列示意图:
12、,a1,a2,a3,an,队尾,出队列,队列的抽象数据类型定义: ADT Queue 数据对象:D=ai| aiElemSet,i=1,2,n,n0 数据关系:R1=|ai-1,aiD,i=2, ,n约定其中ai端为队列头,an端为队列尾。 基本操作: Initqueue(&Q) 操作结果:构造一个空队列Q。 DestroyQueue(&Q) 初始条件:队列Q已存在。 操作结果:队列Q被销毁,不再存在。,ClearQueue(&Q) 初始条件:队列Q已存在。 操作结果:将Q清为空队列。 QueueEmpty(Q) 初始条件:队列 Q已存在。 操作结果:若Q为空队列,则返回TRUE,否则 FAL
13、SE。 QueueLength(Q) 初始条件:队列Q已存在。 操作结果:返回Q的元素个数,即队列的长度。 GetHead(Q,&e) 初始条件:Q为非空队列。 操作结果:用e返回Q的队头元素。,EnQueue(&Q,e) 初始条件:队列Q已存在。 操作结果:插入元素e为Q的新的队尾元素。 DeQueue(&Q,&e) 初始条件:Q为非空队列。 操作结果:删除Q的队头元素,并用e返回其值。 QueueTraverse(Q,visit() 初始条件:Q已存在且非空。 操作结果:从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。 ADT Queue 和
14、栈类似,在本书以后各章中引用的队列都应是如上定义的队列类型。队列的数据元素类型在应用程序内定义。,双端队列(Deque) 定义:是限定插入和删除操作在表的两端进行的线性表, 这两端分别叫端点1和端点2 如图:,a1,a2,a3,an,端1,端2,插入,删除,插入,删除,链表的两种存储表示: 链队列队列的链式表示和实现 循环队列队列的顺序表示和实现 链队列队列的链式表示和实现 定义:用链表表示的队列简称链队列 结构与链表相同:链表中只有表首指针 队列增加一个尾指针 为操作方便,给链队列添加一个头结点, 并令头指针指向头结点 如图:,data,next,Q.front,Q.rear,队头,队尾,当
15、头指针和尾指针均指向头结点时,链队列为空 如图:,Q.front,Q.rear,链队列的操作其实就为单链表的插入和删除操作的特殊情况,只要修改尾指针或头指针,下图即展示了这两种操作指针变化情况,Q.front,Q.rear,元素x入队列,元素y入队列,元素x出队列,Q.front,Q.rear,Q.front,Q.rear,队列的链式存储结构: Typedef struct QNode QElemType data; struct Qnode *next; Qnode , *QueuePtr; Typedef struct QueuePtr front; QueuePtr rear; Link
16、Queue; /-基本操作的函数原型说明- Status InitQueue(LinkQueue &Q) /构造一个空队列Q,Status DestroyQueue(LinkQueue 否则返回ERROR Status EnQueue(LinkQueue &Q,QElemType e) /插入元素e为Q的新的队尾元素,Status DeQueue(LinkQueue ,Status DestroyQueue(LinkQueue ,Q.rear-next = p; Q.rear = p; return OK; Status DeQueue(LinkQueue ,循环队列队列的顺序表示和实现 定义
17、:除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,需设两各指针front和rear分别指示队列头元素和队尾元素的位置 说明:Q.front 表示指向队首元素 Q.rear表示指向队尾元素下一个位置 如何判断队空还是队满: 有两种处理方法判断:其一是另设一个标志位以区别队 列是“空”还是“满“ 其二是少用一个元素空间,约定以 “队列头指针在队列尾指针的下一 个位置(指环状的下一个位置) 上作位队列”满“的标志,入队: Q.baseQ.rear=x; Q.rear=(Q.rear+1) % maxsize 出队: e=Q.baseQ.front Q.front=(Q.front+1
18、) % maxsize 循环队列示意图:,队列,1,0,Maxsize-1,Q.front,Q.rear,0,1,2,3,4,5,Q.front,Q.rear,Q.front,Q.rear,Q.front,Q.rear,Q.front,Q.rear,空队列,J1,J2,J3 相继队列,J1,J2 相继被删除,J4,J5,J6 相继插入 队列之后 J4被删除,0,1,2,3,4,5,J3,J4,J5,Q.front,Q.rear,0,1,2,3,4,5,J5,J6,J7,J8,J3,J4,Q.front,Q.rear,0,1,2,3,4,5,Q.front,Q.rear,空队列,队列满时,一般情
19、况,/-循环队列队列的顺序存储结构- #define MAXQSIZE 100 /最大队列长度 Typedef struct QElemType *base; /初始化的动态分配存储空间 int front; /头指针,若队列不空,指向队列头元素 int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置 SqQueue; /-循环队列的基本操作的算法描述- Status InitQueue(SqQueue ,if (!Q.base) exit (OVERFLOW); /存储分配失败 Q.front = Q.rear = 0; return OK; Int QueueLength (SqQueue Q) /返回Q的元素个数,即队列的长度 return (Q.rear Q.front +MAXSIZE) % MAXSIZE; Status EnQueue (SqQueue ,Q.front = (Q.front + 1) % MAXQSIZE; return OK; Statue DeQueue (SqQueue ,
链接地址:https://www.31doc.com/p-2626425.html