第三章 栈和队列1814291.pptVIP

Double calcul_exp(char *A){//本函数返回由后缀表达式A表示的表达式运算结果 SeqStack s; ch=*A++; s=Init_SeqStack;//初始化对象栈 while(ch!=‘#’){ if(ch!=运算符) Push_SeqStack(s,ch);//操作数入栈 else{ Pop_SeqStack(s,b); Pop_SeqStack(s,a);//取出两个运算量 switch(ch){ case ch==‘+’:c=a+b;break; case ch==‘-’:c=a-b;break; case ch==‘*’:c=a*b;break; case ch==‘/’:c=a/b;break; } Push_SeqStack(s,c);//计算结果入栈 } ch=*A++; } Pop_SeqStack(s,result);//最终计算结果出栈 return result; } 3-3 队列 3-3-1 队列的定义和基本运算 队列是限定在表的一端进行插入，在表的另一端进行删除的线性表。 允许进行插入一端称为队尾(rear)，允许进行删除操作的一端称为队首(front)。 当表中没有元素的时候称为空队。 队列或队又称为先进先出的线性表(First In First Out,FIFO)，简称FIFO表。 队列的类型定义 ADT Queue{ 数据对象： D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系： R={ai-1,ai|ai-1,ai ∈D,i=1,2,…,n} 其中，设定一端为队首，另一端为队尾。 基本操作： Init_Queue(Q); Destroy_Queue(Q); Empty_Queue (Q); Length_Queue (Q); Front_Queue (Q,e); Clear_Queue(Q); In_Queue (Q,e); Out_Queue (Q,e); } ADT Queue Init_Queue(Q) 队列初始化 操作结果：构造一个空队Q。 Destroy_Queue(Q) 销毁队列 初始条件：队Q已存在。 操作结果：队Q被销毁。 Empty_Queue (Q) 判断队空 初始条件：队Q已存在。 操作结果：若队Q为空队，则返回1，否则返回0。 Length_Queue (Q) 求队的长度 初始条件：队Q已存在。 操作结果：返回Q中元素的个数，即队的长度。 Front_Queue (Q,e) 读队首元素 初始条件：队Q已存在且非空。 操作结果：用e返回Q的队首元素，队列不变。 Clear_Queue(Q) 清空队 初始条件：队Q已存在。 操作结果：队Q清为空栈。 In_Queue (Q,e) 入队 初始条件：队Q已存在。 操作结果：在队Q的队尾插入元素x为新的队尾元素。 Out_Queue (Q,e) 出队 初始条件：队Q已存在且非空。 操作结果：删除Q的队首元素并且用e返回其值。 3-3-2 队列的存储实现和运算实现 1、顺序队——顺序存储映像 #define MAXSIZE … //根据实际需要设置队列的最大容量 typedef struct{ DataType data[MAXSIZE]; //队列数据元素的存储空间 int rear,front; //队首、队尾指针 }SeQueue; SeQueue *sq; sq=new SeQueue; 队列的数据区为：sq-data[0]~sq-data[MAXSIZE] 队首指针：sq-front 通常设队首指针指向队首元素的前一位 队尾指针：sq-rear 队尾指着指向队尾元素 　 0 1 2 3 0 1 2 3 　 front rear c b a front rear