第3章栈与队列A.ppt

告 示 为保证电信6、7、8班和通信1、2班同学的正常上课权限，请同学们依下图就座，敬请配合！ 数据结构课程的内容 上堂课若干问题讨论 讨论：自测卷第七题第2小题 【严题集2.6②】已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在P结点后插入S结点的核心语句序列。 答：此题答案不唯一。 第三章 栈和队列 3.1 栈（Stack） 1. 定义 问：堆栈是什么？它与一般线性表有什么不同？ 教材P44对栈有更详细定义： 顺序栈示意图 表和栈的操作区别——对线性表 s= (a1 , a2 , …. , an-1 , an ) 入栈操作——例如用堆栈存放（A，B，C，D） （注意要遵循“后进先出” 原则） 出栈操作——例如从栈中取出‘B’ （注意要遵循“后进先出” 原则） 例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。 例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？ 例4：计算机系2001年考研题（程序设计基础） 设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b 补充1： 若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的栈 入栈口诀：堆栈指针top先压后加（v[top++]=x）； 出栈口诀：堆栈指针top先减后弹（y=v[--top]) 。 补充3：链栈 链栈示意图 链栈的入栈函数、出栈函数（以头指针为栈顶，在头指针处插入或删除！） 公共说明部分： typedef struct snode{ SElemType data; struct snode *link; }NODE; NODE *st, *p; int m=sizeof(NODE); 问：为什么要设计堆栈？它有什么独特用途？ 调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。 数制转换（十转N） ——P48 设计思路：用栈暂存低位值 例2：括号匹配的检验————P49 设计思路：用栈暂存左括号 例3 ：表达式求值 —-————P52 设计思路：用栈暂存运算符 例4：汉诺仪（Hanoi）塔-——P55 设计思路：用栈实现递归调用 * 欢迎到 喻信星空BBS站点的2001级专版反映意见和建议。 IP地址：2 端口: 2600 教案下载FTP网址：2/pub/dian/ 注：第2章自测卷最后40分编程题，建议上机验证。 上机时间： 今晚6:30～9:50 上机地点：南一楼东头MCA机房（仅150个机位） 上机内容：线性表的插入与删除—— 用循环链表方式制作福利彩票（36选7）和体育彩票（10选7）的选号器（有关说明详见第2章自测卷附录） 。 讲 台 电信7班 通信1班 (4列) (4列) 旁听席（最后2行） 电信8班1列 电信6班 电信8班 通信2班 (3列) (3列) (3列) 前门 后门 同学向老师提问： 1. 删除结点时，好像不需要知道前驱结点的指针吧？用P=P-next一个操作应该就足够了？ 错！ 老师继续问：先删除会不会丢掉了指针qb？ —请自查P37DelFirst（…）函数定义 同学回答老师疑问： 自测卷第6题中的判断条件确实不完备。 例如选表长为10，从第1结点开始删除连续10个结点时，i=1,j=10，却会造成i+k10而误告警。 应当改为i+k-1a.length 2. P43中case1中的两个动作，为何要先删除，后插入？作者意图是不多占任何其他内存 法二：已知P结点，则不必“顺藤摸瓜”，直接链接即可。 (4)??S-next=P-next; (1) P-next=S; 法一：从头“摸”起： (7) Q=P; (11) P=L; (8) while(P-next!=Q)P=P-next; (10) P=