国道324线路面改造工程.pptx

1第3章栈和队列栈和队列是两种特殊的线性表,是操作受限的线性表,(stack)栈的定义和特点定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶top,表头—栈底bottom,不含元素的空表称空栈特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)进栈-插入元素出栈-删除元素抽象数据类型定义2栈的表示和实现顺序栈一维数组s[M]或先分配一个基本容量,逐段扩大,动态数组top=0123450栈空栈顶指针top,指向实际栈顶后的空位置,初值为0base保持不变top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空,此时出栈,则下溢(underflow)top=M,栈满,此时入栈,则上溢(overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空3typedefstruct{SElemType*base;//保持不变,NULL不存在栈SElemType*top;//栈顶,指向不用(空)元素,与定义不同intstacksize;}SqStack;//(进)入栈top++,出(退)栈top--算法描述InitStack,DestroyStack,ClearStack,StackEmpty,StackLength,GetTop,Push,Pop,StackTraverse4构造一个空栈SStatusInitStack(SqStack&S){=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!) exit(OVERFLOW);//=;=STACK_INIT_SIZE;returnOK;}取栈顶元素StatusGetTop(SqStackS,SElemType&e){if(==)returnERROR;e=*(-1);returnOK;}5入栈算法StutasPush(SqStack&S,SElemTypee){if(–>={=(SElemType*)realloc(, (+STACKINCREMENT)*sizeof(SElemType));if(!)exit(OVERFLOW);=+; +=STACKINCREMENT; }*++=e;//先赋值,再加指针returnOK;}6出栈算法StatusPop(SqStack&S,SElemType&e){if(==)returnERROR; e=*--;//先减指针,再取值returnOK;}0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈7链栈栈顶^…...topdatalink栈底结点定义入栈算法出栈算法typedefstructnode{intdata;structnode*link;}JD;^…...栈底toptopxptop^…...=(Ndivd)xd+Nmodd -入栈打印过程-出栈例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top7329voidconversion(intNum){////对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数InitStack(S);//构造空栈while(Num){Push(S,Num%8);Num=Num/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}printf("\n");}//conversion10括号匹配的检验园、方、花括号嵌套匹配回文游戏:顺读与逆读字符串一样(不含空格)(原串),非回文若直到栈空都相等,回文字符串:“madamimadam”