C语言程序设计（第5版）第12章 结构体和数据结构基础.ppt

***或为空树，或由一个根结点和左右两棵互不交叉的子树组成，顺序不能换*若图G中的每条边都是有方向的，则称G为有向图(Digraph)。若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。**12.9.1栈和队列//队列的链式存储typedefstructqueue{intdata;structqueue*front;//指向队头structqueue*rear;//指向队尾}QUEUE;//队列的顺序存储typedefstructqueue{intdata[Max];intfront；//控制队头intrear;//控制队尾}QUEUE;//栈的顺序存储typedefstructstack{intdata[Max];inttop;//控制栈顶}STACK;//栈的链式存储typedefstructstack{intdata;structstack*next;//指向栈顶}STACK;栈的应用实例：计算逆波兰表达式中缀表示：二元运算符置于两个运算对象之间a+b后缀表示：运算符置于其运算对象之后，逆波兰表达式ab+?a+babc+d*+?a+(b+c)*dabcab+cab+cda(b+c)*da+(b+c)*d栈的应用实例：计算逆波兰表达式intmain(void){charword[N];NodeTyped1,d2,d3;STACKstack;stack.top=0;//初始化栈顶while(scanf(%s,word)==1word[0]!=#){if(isdigit(word[0])){d1.ival=atoi(word);Push(stack,d1);}else{d2=Pop(stack);d1=Pop(stack);d3=OpData(d1,d2,word[0]);Push(stack,d3);}}d1=Pop(stack);//弹出栈顶保存的最终计算结果printf(%d\n,d1.ival);return0;}typedefstructdata{inttype;//数据类型union{intival;}dat;//数据的值}NodeType;typedefstructstack{NodeTypedata[N];inttop;//控制栈顶}STACK;//栈的顺序存储如何输入逆波兰表达式356+2*+栈的应用实例：计算逆波兰表达式//函数功能：弹出栈顶数据并返回NodeTypePop(STACK*stack){stack-top=stack-top-1;returnstack-data[stack-top];}1002003004005000*pPushPop//函数功能：将数据data压入堆栈voidPush(STACK*stack,NodeTypedata){memcpy(stack-data[stack-top],data,sizeof(NodeType));stack-top=stack-top+1;}*pPush(stack,d1);//入栈d2=Pop(stack);//出栈栈的应用实例：计算逆波兰表达式//函数功能：对d1和d2执行运算op，并返回计算结果NodeTypeOpData(NodeType*d1,NodeType*d2,intop){NodeTyperes;res=OpInt(d1-ival,d2-ival,op);returnres;}//函数功能：对整型的数据d1和d2执行运算op，并返回计算结果NodeTypeOpInt(intd1,intd2,