数据结构语言课件习题语言版栈和队列

1、1第三章 栈和队列-操作受限的线性表3.1 栈 3.2 表达式求值 3.3 栈与递归的实现 3.4 队列 3.5 离散事件模拟23.1 栈3.1.1抽象数据类型栈的定义栈是限定仅在表尾进行插入或删除操作的线性表。栈顶栈的表尾。栈底栈的表头。空栈不含元素的空表。a1a2an栈底栈顶进栈出栈栈s=(a1,a2,an)后进先出（LIFO）3栈的抽象数据类型定义：数据对象:D=ai|ai ElemSet,i=1,2,.,n,n=0数据关系:R1=|ai-1,aiD,i=2,.,n基本操作:IniStack(S) 构造一个空栈S.Empty(S) 栈S为空栈，则返回TRUE,否则FALSE.Push(S

2、,x) 栈S存在则插入元素x为新的栈顶元素.Pop(S) 栈S存在且非空,则删除S的栈顶元素并返回其值.GetTop(S) 栈S存在且非空,则返回S的栈顶元素.Clear(S) 栈S存在则清为空栈.Current_size(S) 栈S存在则返回S的元素个数,即栈的长度.43.1.2栈的表示和实现栈的存储结构： （1）顺序栈 （2）链栈1.顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置例子：Top=0Top=1ATop=5EDCBACBATop=353.1.2 栈的顺序表示与实现- (顺序栈)typedef struct SElem

3、Type *base; /* 在栈构造之前和销毁之后，base的值为NULL*/ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位*/SqStack;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERROR 06顺序栈示意图*base*topstacksize.a1.aian*base*topstacksize初始空栈*top = *base; stacksize = STACK_IN

4、IT_SIZE顺序栈7顺序栈的操作实现举例 InitStack /* 构造一个空的栈S*/Status InitStack(SqStack *s) s-base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s - base) return(OVERFLOW); s - top = s - base; s - stacksize = STACK_INIT_SIZE; return OK; /* InitStack */8顺序栈的操作实现 (GetTop) 栈S非空, 则用e返回栈S中栈顶元素的值，并返回OK, 则返

5、回ERROR。Status GetTop(SqStack s, SElemType *e) if (s.top = s.base)return ERROR; *e = *(s.top-1); return OK; /* GetTop */*base*topstacksize.a1.aianse*e = *(s.top-1);9顺序栈的操作实现 （Push）插入元素e为新的栈顶元素。 Status Push(SqStack *s, SElemType e) if (s-top s-base = s-stacksize) /* 栈满，追加存储空间 */ l_temp=(SElemType*)rea

6、lloc (s-base,(s-stacksize+STACKINCREMENT) *sizeof(SElemType); if (!l_temp) return(OVERFLOW); s-base = l_temp; s-top = s-base + s-stacksize; s-stacksize += STACKINCREMENT; *(s-top+) = e; return OK; /* Push */10插入新的栈顶元素时，堆栈变化示意e*base*topstacksize.a1.aians*base*topstacksize.a1.aians栈满时，追加存储空间*(s-top+)

7、= e;11顺序栈的操作实现 (Pop) 栈S非空, 则删除S的栈顶元素, 用e返回栈S中栈顶元素的值，并返回OK, 否则返回ERROR。Status Pop(SqStack *s, SElemType *e) if (s-top = s-base)return ERROR; *e = *(-s-top); return OK; /* Pop */*base*topstacksize.a1.aianse*e = *(-s-top);12应用顺序栈时，一个程序需多个栈的解决方法：共享空间栈1底栈1顶栈2顶栈2底栈1栈2132.链栈链栈的PASCAL表示： TYPE pointer=nodetyp

8、e; nodetype=record data:elemtp; next:pointer end; Linked_stack=pointer;例子：var la:linked_stack; /LA是链栈形式，指示栈顶元素 .ladata next栈顶栈底14链栈的操作实现：（1）IniStack(S) （2）Empty(S) （3）Push(S,x) （4）Pop(S) （5）GetTop(S) （6）Clear(S) （7）Current_size(S)（1）初始化操作Init_linkstack(S)PROC init_linkstack(VAR s:linked_stack); S:=n

9、ilEndp; init_linkstack15(3)进栈操作push_linkstack(s,x)proc push_linkstack(VAR s:linked_stack; x:elemtp); new(p); p.data:=x; p.next:=s; s:=pEndp; push_linkstack(4)出栈函数pop_linkstack(s)Func pop_linkstack(var s:linked_stack):elemtp; if s=nil then return(null) else 【p:=s; x:=s.data; s:=s.next; dispose(p); re

10、turn(x)】endF;pop_linkstack演示演示163.2 栈的应用1、行编辑 一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据。允许用户输入出错时可以及时更正。可以约定为退格符，以表示前一个字符无效，为退行符，表示当前行所有字符均无效。例：在终端上用户输入为： BGE#EGIM#N RAD（AREAD(A) 应为：BEGIN READ(A)17行编辑算法：p42PROC line_edit; read(ch); while not eof do 【inistack(s); while not eoln do 【case ch of #: b:=pop(s); : cl

11、ear(s); else push(s,ch) endc; read(ch)】; 将栈S的字符作为一行，传送至数据区； if not eof then read(ch) 】Endp; line_edit182、表达式求值 例子： 要对以下算术表达式求值： 4+23 - 10/5算术四则运算的规则： （1）先乘除，后加减； （2）从左算到右； （3）先括号内，后括号外。=4+6-10/5=4+6-2=10-2=8算符优先法根据运算优先关系的规定来实现对表达式的编译或解释执行的。表达式的组成：（ 1） 操作数 （2） 运算符 （3） 界限符算符19根据运算规则，在运算的每一步中，任意两个相继出现的

12、算符1和2之间的优先关系至多是三种关系之一： （1） 1 2表：+ - * / （ ） # 7 种运算符间的优先关系21+ - * / （ ） #+-*/（）# =表达式的结束符表示运算结束20算符优先算法的实现：设两个工作栈，一个称为optr，用以寄存运算符；另一个称为opnd,用以寄存操作数或运算结果。算法的基本思想： ）首先置操作数栈为空栈，表达式起始符为运算 符栈的栈底元素； ）依次读入表达式中每个字符，若是操作数则进 Opnd栈，若是运算符，则和Optr栈的栈顶运算符 比较优先权后作相应操作，直至整个表达式求值 完毕。21例子：4 +(2*3-10/2)#4+(2*3-10/2)#O

13、ptr栈Opnd栈#4+（2*3（1）计算2*3=66-10/2（2）计算10/2=55（3）计算6-5=11（4）计算4+1=55演示22Precede: 判定运算符栈的栈顶运算符1与读入的运算符2之间 的优先关系的函数.Operate: 进行二元运算ab的函数.23算术表达式求值过程(算法3.4)OperandType EvaluateExpression()InitStack(OPTR); Push(OPTR, #); InitStack(OPND); c = getchar(); While(c!=# | GetTop(OPTR)!=#) If(!In(c,OP) Push(OPND,

14、c); c = getchar(); / 不是运算符则进栈 else switch(Precede(GetTop(OPTR),c) case : / 退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; default: printf(“Expression error!”); return(ERROR); / switch / while return GetTop(OPND); / EvaluateExpression24对算术表达式3*(7-2)求值.步骤 OPT

15、R栈 OPND栈 输入字符 主要操作1 # 3 * ( 7 - 2 ) # Push(OPND,3)2 # 3 * ( 7 - 2 ) # Push(OPTR,*)3 # * 3 ( 7 - 2 ) # Push(OPTR,()4 # * ( 3 7 - 2 ) # Push(OPND,7)5 # * ( 3 7 - 2 ) # Push(OPTR,-)6 # * ( - 3 7 2 ) # Push(OPND,2)7 # * ( - 3 7 2 ) # Operate(7,-,2)8 # * ( 3 5 ) # POP(OPTR)9 # * 3 5 # Operate(3,*,5)10 #

16、15 # Return(GetTop(OPND)253.4 队列3.4.1 抽象数据类型队列的定义队列是一种先进先出的线性表。它只允许在表 的一端进行插入，而在另一端删除元素。队尾队列中允许插入的的一端。队头队列中允许删除的一端。例：队列S=（a1,a2,an)a1 a2 an 队头队尾出队列入队列26队列的抽象数据类型定义：数据对象: D=ai| aiElemSet,i=1,2,.,n,n=0 数据关系: R1= | ai-1,aiD,i=2,.,n 基本操作： InitQueue(Q) 构造一个空队列QEmpty(Q) 若Q为空队列，则返回TRUE,否则返回FALSEEnQueue(Q,x

17、) 队列Q存在,插入元素x为Q的队尾元素DLQueue(Q) Q为非空队列,删除Q的队头元素,并返回其值GetHead(Q) Q为非空队列,返回Q的队头元素ClearQueue(&Q) 队列Q存在则将Q清为空队列CURRENT_SIZE(Q) 队列Q存在,返回Q的元素个数.27队列的表示及实现：队列的存储结构： （1）链队列 （2）循环队列3.4.2链队列链队列用链表表示的队列。一个链队列需要两个分别指示队头和队尾的指针。例子：队头队尾a1a2an28链队列的PASCAL表示：TYPE queueptr=queuenode; Queuenode=record data:elemtp; next

18、:queueptr end;Linkedquetp=record front,rear:queueptr end;例：var q:linkedquetp;(a)非空队列(b)空队列q.fronta1anq.rearq.frontq.rear29链队列的操作实现：（1）初始化操作init_linkedque(q)Proc init_linkedque(var q:linkedquetp); new(q.front); q.rear:=q.front; q.front.next:=nilendP; init_linkedque（2）判空函数empty_linkedque(q)Func empty_

19、linkedque(q:linkedquetp):boolean; if q.front=q.rear then return(true) else return(false)Endf; empty_linkedque30(3) 插入操作en_linkedque(q,x)q.fronta1anq.rear一级算法：（1）生成数据域为x的新结点； new(p); p.data:=x; p.next:=nil; （2）修改有关指针； q.rear.next:=p;q.rear:=p;PxPROC en_linkedque(var q:linkedquetp; x:elemtp); new(p);

20、p.data:=x; p.next:=nil; q.rear.next:=p; q.rear:=pENDp; en_linkedque演示31(4) 删除操作dl_linkedque(q)一级算法： （1） 如果q为空队列，则返回null，否则执行（2）； （2）删除队头元素； s:=q.front.next; q.front.next:=s.next;q.fronta1anq.reara2sReturn(s.data); dispose(s);检验：当队列只有一个结点时（即删除队头元素后队列变为空）。q.fronta1q.rears演示32删除队头元素算法实现：Func dl_linkedq

21、ue(VAR q:linkedquetp):elemtp; if q.front=q.rear then retrun( null) else 【s:=q.front.next; q.front.next:=s.next; x:=s.data; dispose(s);return(x)】Endf; dl_linkedque If s.next=nil then q.rear:=q.front;333.4.3 循环队列顺序队列利用一组地址连续的存储单元依次存放自队头到队尾的数据元素,同时附设指针front指示队头元素在队列中的前一个位置，设指针rear指示队尾元素在队列中的位置。例子：65432

22、1Front=0Rear=0Front=0rear=4j4j3j2j1Front=1rear=4j4j3j2rear=4Front=434顺序队列的PASCAL表示： CONST maxsize= TYPE sequeuetp=record elem:array1.maxsize of elemtp; front,rear:0.maxsize; end;例：var sq:sequeuetp;(1)入队操作Sq.rear:=sq.rear+1; sq.elemsq.rear:=x;(2)出队操作Sq.front:=sq.front+1;(3)判空操作Sq.front=sq.rear(4)判满操作

23、Sq.rear=maxsize假溢出35若将front,rear的上、下界改为0.maxsize-1,并用数学中的“模（mod)运算”就更容易实现这种循环队列的运算。*解决假溢出的方法：循环队列基本思想：把队列设想为一个循环的表，臆想sq.elem1接在sq.elemmaxsize之后,即如果sq.rear+1=maxsize+1,则令sq.rear=1.Sq.frontSq.rearmaxsize12Sq.frontSq.rearmaxsize-10136(1)入队操作 Sq.rear:=(sq.rear+1) mod maxsize; sq.elemsq.rear:=x;(2)出队操作Sq

24、.front:=(sq.front+1) mod maxsize;Sq.frontSq.rearmaxsize-10137(3)判空操作(4)判满操作0012345Sq.rearSq.frontABCD（a)初始状态0012345Sq.rearSq.frontABCD(b)E、F入队EFSq.rear0012345Sq.rearSq.frontABCD(c) A、B、C、D出队Sq.front38判空、判满的方法： （1）另设一个标志位以区别队列是“空”还是“满”。 （2）少用一个元素空间，以rear+1=front作为队列“满”。 以rear=front作为队列“空”。循环队列的PASCAL表示： CONST maxsize= ； m=maxsize-1; TYPE cyclicquetp=record elem:array0.m of elemtp; front,rear:0.m; end;39循环队列的操作实现：(1)初始化操作init_cycque(cq)Proc init_cycque(var cq:cyclicquetp); cq.front:=cq.rear:=0;