资源描述：
《数据结构课件非常详细 ch3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的存储结构顺序栈实现：一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（ov
2、erflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空123450ABCDEFbase栈的存储结构顺序栈实现：一维数组s[M],为了C语言处理方便，设一个base指针栈底指针base,始终指向栈底的位置栈顶指针top,指向实际栈顶后的空位置，初值为top=basetop进栈Atop出栈栈满BCDEF设数组维数为Mtop=base,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空top123450栈空base123450
3、base入栈算法出栈算法顺序栈的定义Typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;链栈栈顶^…...topdatalink栈底结点定义入栈算法出栈算法typedefstructnode{intdata;structnode*link;}JD;^…...栈底toptopxptop^…...栈底topq栈的应用1数字转换十进制数N与其他d进制数的转换N=(Ndivd)*d+Nmodddiv—整除运算，mod—求余运算2括号匹配的检查[([][])]123456783行编辑程序接受用户从终端输入的程序或数据，并存
4、入用户的数据区。建立一个数据缓冲区，接受用户输入一行字符，然后逐行存入用户数据区。退格符“#”，退行符“@”比如输入whli##ilr#e(e#*s)outcha@putchar(*s=#++)输出while(*s)putchar(*s++)4迷宫求解5表达式求值算符优先法（1）先乘除，后加减（2）从左到右（3）先括号内，后括号外4+2*3-10/5=4+6-10/5=10-10/5=10-2=8使用2个工作栈，一个称作OPTR，寄存运算符；另一个OPND，寄存操作数或运算结果。基本思路：（1）首先置操作数栈为空栈，用表达式#（表达式的结束符）为运算符栈的栈底元素（2）依次读入表达式中每个
5、字符，若是操作数则进OPND栈，若是运算符和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR的栈顶元素和当前读入的字符均为#）对表达式3*（7-2）求值过程如下栈的应用过程的嵌套调用r主程序srrrs子过程1rst子过程2rst子过程3例递归的执行情况分析递归过程及其实现递归：函数直接或间接的调用自身叫~实现：建立递归工作栈voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“/n”);}}运行结果：1，2，2，3，3，3，递归调用执行情况如下：主
6、程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1);（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)输出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)输出：2,2(2)2(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)TowerofHanoi问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号
7、1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上解决方法：n=1时，直接把圆盘从A移到Cn>1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题算法：
