队列及相关算法

队列及相关算法

2010/03/291作业分析

表达式转换中缀式转前缀式

Exp=ab

+

(cd/e)f后缀式:ab

cde/f

+前缀式:+

ab

c/def后缀式的运算后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现，且紧靠它的两个操作数构成一个最小表达式（算子）。例：31*(5–22)+7031522-*70+

带括号的表达式的计算*6)/3#operatorstackoperandstackexpression???push(data);Push(oper);getResult();checkIn(oper);栈抽象数据类型定义几个常用函数优先级矩阵及优先级判断当前运算符优先级低…By00811093赖俊By00811093赖俊By00811093赖俊一个中缀式到其他式子的转换方法（）这里给出一个中缀表达式~

a+b*c-(d+e)

第一步：按照运算符的优先级对所有的运算单位加括号，式子变成：((a+(b*c))-(d+e))

第二步：转换前缀与后缀表达式

前缀：把运算符号移动到对应的括号前面

则变成拉：-(+(a*(bc))+(de))

把括号去掉：-+a*bc+de

前缀式子出现

后缀：把运算符号移动到对应的括号后面

则变成拉：((a(bc)*)-(de)+)-

把括号去掉：abc*-de+-

后缀式子出现

队列

：队列的引入与抽象数据类型定义队列的存储结构与实现队列的应用队列特点队列是一种特殊的线性表，只允许在表的一端有插入操作，而在另一端有删除操作。队头：允许删除的这一端叫队列的头。队尾：允许插入的这一端叫队列的尾。空队列：当队列中没有任何元素时，称为空队列。进队/出队：队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。

队列基本概念队列也称作先进先出表（FirstInFirstOut，FIFO表）。支持队尾插入，队头删除操作。

a0a1a2an-1入队列队头队尾出队列队列的示意图队列ADTADTQueueisoperations QueuecreateEmptyQueue(void);//创建一个空队列。 intisEmptyQueue(Queuequ);//判队列qu是否为空队列。 voidenQueue(Queuequ,DataTypex); //往队列qu尾部插入一个值为x的元素。 voiddeQueue(Queuequ);//从队列qu头部删除一个元素。 DataTypefrontQueue(Queuequ);//求队列qu头部元素的值。endADTQueue顺序结构队列frontrearenQueue:{qBuffer[rear]=inData;rear++;}deQueue:{outData=qBuffer[rear];front++;}isEmpty(){…}环形存储结构队列frontrearmodMAXSIZEenQueue:{qBuffer[rear]=inData;rear=(rear+1)%MAXSIZE;}deQueue:{outData=qBuffer[rear];rear=(rear+1)%MAXSIZE;}isOverflow(){…}把数组paqu->q[MAXNUM]从逻辑上看成一个环，这种队列称为环形队列。当表中已有MAXNUM－1个结点时，如果还要插入，paqu->r和paqu->f就会重合，而这与空队列的情形相混。为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM－1个结点时就称满，再要插入就发生溢出。环形存储结构队列顺序结构队列的类型定义顺序结构队列操作的实现顺序结构队列操作的实现链接结构队列尾部插入头部删除。r->link=newNode;r=newNode;newNode.link=NULL;ptr=f;f=f->next;