数据基础结构 5

教案纸（首页）第1页第次课学时授课时间________教学主题栈和队列栈的特点；栈的表示和实现；栈的典型应用与实现教学要求通过本章的学习，学生应达到如下基本要求：1、掌握栈的逻辑结构特性，栈抽象数据类型的描述方法。2、掌握栈的先进后出特点。3、掌握栈基本运算在两类存储结构下的实现算法。4、掌握栈在实际求解问题中的应用方法。教学重点栈的逻辑结构特点；顺序栈和链栈的基本算法设计。教学难点栈与线性表的异同；顺序栈和链栈的基本算法设计教学方法讲授、练习教学手段多媒体、板书、上机实操讲授要点1、栈的逻辑结构特性。2、栈抽象数据类型的描述方法。3、顺序栈的算法设计方法。4、链栈的算法设计方法。5、栈在表达式求值中的应用。作业完成学习通上第三章中有关栈的练习作业。参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第5页教学内容备注与后记3.1栈1、栈的定义栈是一种只能在一端进行插入或删除操作的线性表。特点：后进先出关于栈的几个概念：允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈。栈的删除操作通常称为退栈或出栈。举实例说明，加深学生对栈的理解和认识。2、栈的存储结构顺序存储——顺序栈链式存储——链栈3、栈的基本运算InitStack(&s)：初始化栈。构造一个空栈s。DestroyStack(&s)：销毁栈。释放栈s占用的存储空间。StackEmpty(s)：判断栈是否为空:若栈s为空，则返回真；否则返回假。Push(&S，e)：进栈。将元素e插入到栈s中作为栈顶元素。Pop(&s，&e)：出栈。从栈s中退出栈顶元素，并将其值赋给e。GetTop(s，&e)：取栈顶元素。返回当前的栈顶元素，并将其值赋给e。4、顺序栈的基本操作实现typedefstruct{ElemTypedata[MaxSize]；inttop； //栈顶指针}SqStack；顺序栈的6种基本运算实现。例3-4。5、链栈的基本操作实现typedefstructlinknode{ElemTypedata; //数据域structlinknode*next; //指针域}LinkStNode;顺序栈的6种基本运算实现。例3-5。3.2栈的典型应用与实现1、简单表达式求值这里限定的简单表达式求值问题是：用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法算术表达式，计算该表达式的运算结果。中缀表达式：1+2*3后缀表达式：123*+前缀表达式：+1*23利用栈的特点将表达式转化成后缀表达式，再利用栈求出表达式的值。2、求解迷宫问题（选讲内容）给定一个M×N的迷宫图、入口与出口、行走规则。求一条从指定入口到出口的路径。利用栈后进先出的特点求解上述问题并实现算法。教学总结：本章节给大家介绍了栈的基本定义，栈的特点是后进先出。利用栈的这个特性可以解决实际生活中遇到的一些问题。

第次课学时授课时间______教学主题栈和队列队列的特点，表示和实现；队列的应用与实现教学要求1、掌握队列的逻辑结构特性，队列抽象数据类型的描述方法。2、掌握队列的先进后出特点。3、掌握队列基本运算在两类存储结构下的实现算法。4、掌握队列在实际求解问题中的应用方法教学重点顺序队的基本运算算法设计；链队的基本运算算法设计；利用队列求解复杂的应用问题。双链表的查找、插入和删除操作过程及其实现。教学难点顺序队和链队的基本运算算法设计；利用队列求解复杂的应用问题。教学方法讲授、练习教学手段多媒体、板书、上机实操讲授要点1、队列的逻辑结构特性。2、队列抽象数据类型的描述方法。3、顺序队的算法设计方法。4、链队的算法设计方法。作业完成学习通上第三章作业中有关队列的练习题。参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）教学内容备注与后记3.3队列1、队列的定义队列简称队，它也是一种运算受限的线性表。。特点：先进先出。队列的几个概念：进行插入的一端称做队尾（rear）。进行删除的一端称做队首或队头（front）。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素。从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。2、队列的基本运算InitQueue(&q)：初始化队列。构造一个空队列q。DestroyQueue(&q)：销毁队列。释放队列q占用的存储空间。QueueEmpty(q)：判断队列是否为空。若队列q为空，则返回真；否则返回假。enQueue(&q，e)：进队列。将元素e进队作为队尾元素。deQueue(&q，&e)：出队列。从队列q中出队一个元素，并将其值赋给e。3、队列的存储结构顺序存储——顺序队链式存储——链队4、顺序队的基本运算实现typedefstruct{ElemTypedata[MaxSize]；intfront，rear；//队首和队尾指针}SqQueue;顺序队的四要素：队空条件：front=rear队满条件：rear=MaxSize－1元素e进队：rear++;data[rear]=e;元素e出队：front++;e=data[front];顺序队实现队列中的基本运算。5、循环队列的基本运算实现把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，称为环形队列或循环队列。rear=(rear+1)%MaxSizefront=(front+1)%MaxSize循环队列的四要素：队空条件：front=rear队满条件：(rear+1)%MaxSize=front进队e操作：rear=(rear+1)%MaxSize;将e放在rear处出队操作：front=(front+1)%MaxSize;取出front处元素e;6、链队的基本运算实现typedefstruct{DataNode*front; //指向单链表队头结点DataNode*rear; //指向单链表队尾结点}LinkQuNode;链队的四要素：队空条件：rear=NULL队满条件：不考虑进队e操作：将包含e的结点插入到单链表表尾出队操作：删除单链表首数据结点链队实现队列中的基本运算。3.4队列的应用与实现求解报数问题设有n个人站成一排，从左向右的编号分别为1～n，现在从左往右报数“1，2，1，2，…”，数到“1”的人出列，数到“2”的立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求给出他们的出列顺序。例如，当n=8时，初始序列为12345678则出列顺序为1