三：栈和队列.ppt

1、第三章栈和队列、栈和队列是两种特殊的线性表，是操作受到限制的线性表，被称为限定性DS 3.1栈(stack )栈的定义和特征定义：包括只对显示终端进行插入和删除操作的线性表、显示终端栈、显示表头栈、元素ADT Stack数据对象： D ai | ai ElemSet，I=1，2，n，n0数据关系： R1 | ai-1，aiD，i=2，n约定，基本操作：ADT Stack，堆栈的类型定义，init stack (int sqstack； 动态分配定义方式# define stack _ init _ size 100 # definestackincrement 10类型defstructele

2、mtype * base； elemtype *顶部； 堆叠大小； sqstack； Top是整数值，s.Top=0是nulls.Top=stack_maxsize是full，top是指针，s.top=s.base是null，基本操作的实现，堆栈状态的初始化ElemType /GetTop，堆栈status Pop(sqstack /GetTop，Status push(sqstack，堆叠(/插入元素e是新的堆叠元素) ) struct node *next； JD； 例1、数字转换、堆栈应用、例如(1348)10=()8、其运算过程如下：校正运算顺序、输出顺序、算法原理：基于N=(N di

3、v d)d N mod d的scanf (%d，n )； 推出(s，N % 8)； N=N/8； 威廉(！ 堆栈空间(s ) pop (s，e ) :打印(% d，e )； /conversion，常用算法：运算符优先法，例2，公式评价，公式：操作数，由运算符和边界线组成，运算符优先度(规定)，算法思想：将操作数OPTR存储运算符以2个堆栈： OPND存储，operandtypeevaluate 推(optr，# )； /运算符初始化堆栈，将表示/式起始符按入OPTR堆栈的底部InitStack(OPND )。 /初始化操作数栈OPND c=getchar ()； /读取公式的第一个字母whi

4、le (c！=# | GetTop(OPTR )！=#) if (！ 如果不是In(c，OP)/运算符，则op是运算符集合push(OPND，c )； /进制操作数堆栈c=getchar ()； /对于读取下一个字符的else /运算符，如果switch (precede (GetTop(OPTR )，c) ) case : /堆栈的第一个元素优先，则堆栈的第一个元素从堆栈中退出。 /运算符堆栈的堆栈顶元素pop(OPND，b )； pop (开放，a )；/两个操作数推式(opnd、操作(a、thete、b ) )； /运算结果堆栈break；/交换机/whilereturngettop (

5、opnd )； 我们已经完成了修订运算，并且我们将进入结果，例如修订运算3*(7-2)、3 * (7 2 ) #、#、 可以直接调用自己，也可以通过一系列调用语句间接调用自己的函数。 叫做递归函数。、3.4队列定义和特征定义：允许插入仅在表的一端而无法在表的另一端删除的线性表队列末端(rear )允许删除一端队列报头(front )允许删除的一端队列特征：先进先出(front ) n0数据关系： R1 | ai-1，ai D，i=2，n是，a1侧是队列首部，an侧是队列尾部，基本操作：队列的类型定义，ADT Queue，约定队列的基本操作的LinkQueue；队列头、队列头指针front和re

6、ar、前端是头节点、rear是队列头、typedefstructqnodeqelemtypedata； 结构节点*下一步； Qnode、*QueuePtr；空队列q、链路队列、损坏队列q、链路队列、插入元素e是q的新队列元素、状态排队()、队列的顺序存储结构的前端是在队列头元素之前的位置的初始值front=rear=-1，输入队列： sq rear=x； 输出队列： x=sq前端； 空队列条件： front=rear，如果将存在问题的数组维数设为m，则在front=-1，rear=M-1时，进一步元素的排队溢出，真正的溢出变为front-1，实现：利用“类型”运算排队： reen sqrear=x； 出队：前端=(前端