数据结构与算法（Java语言版） 教案15-28（48+8）耿祥义 第7-14章 栈与Stack类-经典算法思想

参考教案（共计56学时，含4个上机实践教案）耿祥义编写《数据结构与算法（java语言版）清华大学出版社出版耿祥义，张跃平主编参考教案15（2学时，实践）1.实践前的复习完成下列选择题。（1）Arrays类的sort()方法是()。A.双轴快速排序。B.稳定排序。C.时间复杂度比气泡法高的排序。D.时间复杂度比选择法高的排序。（2）下列叙述正确的是()。A.链表的单向迭代器在遍历链表时也可以删除节点。B.链表的单向或双向迭代器在遍历链表时，不允许链表调用set(intindex，Eobj)方法更新节点中的数据。C.如果增加或删除链表节点，链表之前的视图仍然能被使用。D.可以对不可变链表经行排序操作。（3）顺序表的时间复杂度不是O(1)的方法是()A.publicEget(intindex)。B.publicintindexOf(Objectobj)。C.publicbooleanadd(Ee)。D.publicEset(intindex,Eelement)。（4）对于下列代码，下列叙述错误的是()。importjava.util.LinkedList;importjava.util.ListIterator;publicclassC{publicstaticvoidmain(Stringargs[]){LinkedList<String>list=newLinkedList<>();for(charc='A';c<='F';c++){list.add(""+c);}ListIterator<String>iterTwoWay=list.listIterator();System.out.println(iterTwoWay.next());//代码ASystem.out.println(iterTwoWay.previous());//代码BiterTwoWay.next();System.out.println(iterTwoWay.next());//代码CiterTwoWay.next();iterTwoWay.next();System.out.println(iterTwoWay.next());//代码D}}A.代码A输出的结果是A。B.代码B输出的结果是B。C.代码C输出的结果是B。D.代码D输出的结果是E。（5）对于下列代码，下列叙述错误的是()。importjava.util.ArrayList;publicclassC{publicstaticvoidmain(Stringargs[]){ArrayList<String>list=newArrayList<>();list.add("A");list.add("B");list.add("F");list.add("F");list.add("B");list.add("G");System.out.println(list.lastIndexOf("F"));//代码ASystem.out.println(list.remove("B"));//代码BSystem.out.println(list.indexOf("B"));//代码CSystem.out.println(list.remove(2));//代码D}}A.代码A输出的结果是3。B.代码B输出的结果是true。C.代码C输出的结果是1。D.代码D输出的结果是F。2.实践内容完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。（1）输出int型数组的一个最长的递增子数组，例如，对于int[]a={15,16,6,8,9,10,11,11,11,8,2,10};程序输出[6,8,9,10,11]。（2）链表删除头节点和尾节点的时间复杂度都是O(1)。对于某些问题，可以利用链表的这一特点快速的处理数据。编写一个程序，判断字符串是否是回文串。算法提示：将字符串中的全部字符按顺序依次添加到链表，然后开始分别从头、尾删除链表的节点，如果字符串是回文串，那么从头删除的节点中的字符一定和从尾删除的节点中的字符相同，当链表中剩余的节点数目不足2个时，停止删除操作。（3）将一个节点是Integer的顺序表listOne升序排序，然后将另一个节点是Integer的顺序表listTwo中的节点插入到listOne，并继续保持listOne是升序。

参考教案16（2学时）主要内容教材第7章栈与Stack类7.1-7.8栈的特点教材7.1栈的创建与独特的方法教材7.2栈与回文串教材7.3栈与递归教材7.4栈与undo操作教材7.5栈与括号匹配教材7.6栈与深度搜素教材7.7栈与后缀表达式教材7.8基础知识栈的特点。重点知识栈的创建与独特方法。基础算法1.利用栈判断一个字符串是否为回文串（例子7.2）2.使用栈实现撤销操作（例子7.5）3.检查括号是否匹配（例子7.6）重点算法用栈模拟老鼠走迷宫（例子7.7）难点算法1.使用栈计算后缀表达式（例子7.8）2.把中缀表达式转换为后缀表达式（例子7.9）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图7.1讲解栈的特点，使用例子7.1讲解如何创建栈以及栈的独特方法。讲解基础算法：利用栈判断一个字符串是否为回文串（例子7.2）。例子7.3和7.4可以作为自学内容（根据课堂时间情况）。讲解基础算法：使用栈实现撤销操作（例子7.5），检查括号是否匹配（例子7.6）。第2个学时：讲解7.7节，讲清什么叫深度优先搜索，以及栈为何能体现深度优先搜索。结合例子5.5讲解添加节点。讲解重点算法：用栈模拟老鼠走迷宫（例子7.7）。讲解难点算法：使用栈计算后缀表达式（例子7.8），要特别结合图7.10介绍后缀表达式的算法。对于中缀表达式转换为后缀表达式（例子7.9），老师课堂可以只讲算法的思想，其详细代码可以留作学生自学。多媒体辅助PPT电子讲义。作业在习题7中挑选有关内容布置相关作业。

参考教案17（2学时）主要内容教材第8章队列与Stack类8.1-8.8队列的特点教材8.1队列的创建与独特的方法教材8.2队列与回文串教材8.3队列与加密解密教材8.4队列与约瑟夫问题教材8.5队列与广度搜素教材8.6队列与网络爬虫教材8.7队列与排队教材8.8基础知识队列重点知识队列的创建与独特方法。基础算法1.利用队列判断一个字符串是否为回文串（例子8.2）2.使用队列加密、解密字符序列（例子8.3）3.队列与约瑟夫问题（例子8.4）重点算法使用广度优先搜索法进行排雷（例子8.5）难点算法1.使用网络爬虫爬去网页（例子8.6）2.用队列模拟排队（例子8.7）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图8.1讲解队列的特点，使用例子8.1讲解如何创建队列以及队列的独特方法。讲解基础算法：利用队列判断一个字符串是否为回文串（例子8.2）。讲解基础算法：使用队列加密、解密字符序列（例子8.3），队列与约瑟夫问题（例子8.4）。第2个学时：讲解7.7节，讲清什么叫广度优先搜索，以及队列为何能体现广度优先搜索。讲解重点算法：使用广度优先搜索法进行排雷（例子8.5）。讲解难点算法：使用网络爬虫爬去网页（例子8.6）。对于难点算法：用队列模拟排队（例子8.7），可以根据时间情况，只讲解思想，代码细节留给学生自学。多媒体辅助PPT电子讲义。作业在习题8中挑选有关内容布置相关作业。

参考教案18（2学时，实践）1.实践前的复习完成下列选择题。（1）Stack<E>的时间复杂度不是O(1)的方法是()A.publicbooleanempty()。B.publicsynchronizedintindexOf(Objectobj)。C.publicsynchronizedEpeek()。D.publicsynchronizedbooleanadd(Ee)。（2）下列叙述错误的是()。A.队列擅长在线性表的头、尾两端实施删除和添加操作。B.栈擅长在线性表尾端实施删除和添加操作。C.顺序表擅长在线性表的中间实施删除和添加操作。D.双链表擅长在线性表的头、尾两端实施删除和添加操作。（3）对于下列代码，下列叙述错误的是()。importjava.util.Stack;publicclassC{publicstaticvoidmain(Stringargs[]){intm=0;intm1=0,m2=0;Stack<Integer>stack=newStack<>();stack.push(13);stack.push(17);m2=stack.pop();m1=stack.pop();m=m1+m2;System.out.println(m);//代码Astack.push(m);stack.push(6);m2=stack.pop();System.out.println(m2);//代码Bm1=stack.pop();m=m1*m2;System.out.println(m);//代码Cm=m1/m2;System.out.println(m);//代码D}}A.代码A输出的结果是30。B.代码B输出的结果是6。C.代码C输出的结果是180。D.代码D输出的结果是0。（4）对于下列代码，下列叙述错误的是()。importjava.util.ArrayDeque;publicclassB{publicstaticvoidmain(Stringargs[]){ArrayDeque<Integer>deque=newArrayDeque<>();deque.offer(10);deque.offerFirst(20);deque.offer(30);deque.offerFirst(50);deque.forEach((v)->{System.out.println(""+v);});System.out.println(deque.peek());//代码ASystem.out.println(deque.poll());//代码BSystem.out.println(deque.pollLast());//代码CSystem.out.println(deque.size());//代码D}}A.代码A输出的结果是50。B.代码B输出的结果是20。C.代码C输出的结果是30。D.代码D输出的结果是2。（5）下列叙述正确的是()。A.Stack<E>的isEmpty()方法是线程安全的。B.Stack<E>的empty()方法是线程安全的。C.Stack<E>的elementAt(intindex)。方法不是线程安全的。D.Stack<E>的intsearch(Objectobj)方法不是线程安全的。2.实践内容完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。（1）借助栈，在一个类中编写一个方法publicstaticStringreverse(Strings)，方法返回的String对象中的字符序列是参数s的字符序列的反转（倒置）字符序列。（2）农夫携带狼、羊、菜从河东岸到西岸，桥上限制农夫每次至多只能携带狼、羊、菜中的一种。另外，如果没有农夫看着，羊会吃菜，狼会吃羊，但狼不吃菜。农夫带羊过河办法之一：①农夫带羊过河，返回。②农夫带狼过河，带羊返回。③带菜过河、返回。④带羊过河。编程程序，通过两个队列：一个东岸队列和西岸队列，来模拟农夫过河。用数字1代表菜，数字2代表羊，数字3代表狼。将数字1，2，3存入东岸的队列中。东岸出列到西岸入列时，如果导致东岸的队列的长度是2，必须保证东岸的队列中的数字之和是4，否则重新入列东岸。如果西岸的队列的长度是2，必须保证西岸的队列中的数字之和是4，否则西岸出列，然后再入列东岸。

参考教案19（2学时）主要内容教材第9章二叉树与TreeSet类9.1-9.5二叉树的基本概念教材9.1遍历二叉树教材9.2二叉树的存储教材9.3平衡二叉树教材9.4二叉查询树和平衡二叉查询树教材9.5基础知识二叉树的基本概念重点知识二叉查询树和平衡二叉查询树。基础算法遍历与查询二叉树（例子9.1）重点算法中序遍历二叉查询树（例子9.2）难点算法创建平衡二叉查询树并查询（例子9.3）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图9.1讲解二叉树的基本概念。结合图9.2讲解遍历二叉树：前序遍历，中序遍历，后序遍历。讲解基础算法：遍历与查询二叉树（例子9.1）。第2个学时：讲解9.4节：平衡二叉树。结合图9.4讲解重点算法：中序遍历二叉查询树（例子9.2）。讲解难点算法：创建平衡二叉查询树并查询（例子9.3）。多媒体辅助PPT电子讲义。作业在习题9中挑选有关内容布置相关作业。

参考教案20（2学时）主要内容教材第9章二叉树与TreeSet类9.6-9.11TreeSet树集教材9.6树集的基本操作教材9.7树集的视图教材9.8树集与数据统计教材9.9树集与过滤数据教材9.10树集与节目单教材9.11基础知识TreeSet树集重点知识树集的基本操作。基础算法1.借助树集模拟双色球（例子9.5）2.使用树集存放节目单（例子9.11）重点算法1.统计随机数（例子9.8）2.使用树集过滤数据（例子9.9）3.处理重复的数据（例子9.10）难点算法借助树集求最大、最小连接数（例子9.6）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合例子9.4，讲TreeSet树集和它的基本操作。讲解基础算法：借助树集模拟双色球（例子9.5）。讲解难点算法：借助树集求最大、最小连接数（例子9.6）第2个学时：讲解9.8节：树集的视图（含例子9.7）。讲解重点算法：统计随机数（例子9.8），使用树集过滤数据（例子9.9），处理重复的数据（例子9.10）。讲解基础算法：使用树集存放节目单（例子9.11）。多媒体辅助PPT电子讲义。作业在习题9中挑选有关内容布置相关作业。

参考教案21（2学时）主要内容教材第10章散列表与HashMap类10.1-10.5散列结构的特点教材10.1简单的散列函数教材10.2HashMap类教材10.3散列表的基本操作教材10.4遍历散列表教材10.5统计字符、单词出现的次数和频率教材10.6基础知识散列结构的特点重点知识简单的散列函数。基础算法遍历散列表（例子10.4）难点算法统计字符、单词出现的次数和频率（例子10.5）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图10.1讲清楚散列结构。借助图10.2至10.4和例子10.1讲重点知识点：简单的散列函数。第2个学时：借助例子10.2和例子10.3讲解HashMap类和散列表的基本操作。讲解基础算法：遍历散列表（例子10.4）。讲解难点算法：统计字符、单词出现的次数和频率（例子10.5）多媒体辅助PPT电子讲义。作业在习题10中挑选有关内容布置相关作业。

参考教案22（2学时）主要内容教材第10章散列表与HashMap类10.1-10.5散列表与单件模式教材10.7散列表与数据缓存教材10.8TreeMap类教材10.9Hashtable类教材10.10基础知识TreeMap类，Hashtable类。重点知识单件模式。基础算法使用树映射排序数据（例子10.10）重点算法使用散列表缓存数据（例子10.7）难点算法用单件模式模拟只有一个太阳（例子10.6）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合图10.11讲解单件模式，然后讲解难点算法：用单件模式模拟只有一个太阳（例子10.6）。讲解重点算法：使用散列表缓存数据（例子10.7）。第2个学时：讲解10.9节：TreeMap类，特别注意讲解和HashMap类的不同，讲解基础算法：使用树映射排序数据（例子10.10），对于例子10.8，如果时间不允许，可以让学生自学。介绍Hashtable类，重点介绍其线程安全的特点，有关代码可留给学生自学。多媒体辅助PPT电子讲义。作业在习题10中挑选有关内容布置相关作业。

参考教案23（2学时）主要内容教材第11章集合与HashSet类11.1-11.6集合的特点教材11.1HashSet类教材11.2集合的基本操作教材11.3集合与数据过滤教材11.4正整数集合的生成集教材11.5获得随机数的速度教材11.6基础知识集合的特点，HashSet类。重点知识集合的基本操作。基础算法使用集合和树集过滤数据（例子11.2）重点算法比较借助数组、链表、树集、集合获得随机数的速度（例子11.4）难点算法返回集合的生成集（例子11.3）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：结合例子1讲解集合的特点，HashSet类，集合的基本操作。特别强调：集合的添加、查找和删除元素等操作的时间复杂度通常为O(1)。讲解基础算法：使用集合和树集过滤数据（例子11.2）。第2个学时：讲解难点算法：返回集合的生成集（例子11.3）。讲解重点算法：比较借助数组、链表、树、集合获得随机数的速度（例子11.4）多媒体辅助PPT电子讲义。作业在习题11中挑选有关内容布置相关作业。

参考教案24（2学时，实践）1.实践前的复习完成下列选择题。（1）对于平衡二叉查询树，叙述正确的是()。A.查询时间复杂度OnB.查询时间复杂度是O(logn)。C.查询时间复杂度是O(nlogn)。D.查询时间复杂度是O(1)。（2）下列叙述错误的是()。A.红黑树是平衡的二叉查询树。B.AVL树是平衡的二叉查询树。C.红黑树的查询时间复杂度是O(logD.AVL树的查询时间复杂度是O(（3）对于图示意的二叉树，()是中序遍历的结果。注意这个二叉树不是查询二叉树。12121117613915图二叉树A.691113151712。B.121196131517。C.691113121517。D.961115131712。（4）叙述正确的是()。A.TreeMap<K,V>映射树也是散列结构。B.TreeMap<K,V>映射树是红黑树结构。C.TreeMap<K,V>映射树查询、添加和删除等操作的时间复杂度都是O(n)D.TreeMap<K,V>映射树中的Value中不能有两个相同的对象。（5）叙述正确的是()。A.HashSet集合中的元素仅仅同属一个集合，无任何关系。B.HashSet集合中的元素的存储是链式存储。C.HashSet集合中的元素形成的关系是线性关系。D.HashSet集合中的元象的逻辑关系是树形关系。2.实践内容完成后，要向老师展示程序的运行效果，老师根据完成情况，记载相关成绩。（1）某种学生小档案的中的数据是一个"键-值"(key,value)，其中key是学号，value是学生名称或介绍。编程用HashMap散列表存储学生小档案。使用key关键字输出全部学生的姓名或介绍，输出样式是(key,vlaue)。不使用关键字，直接输出全部学生的小档案中全部学生的名字。（2）在一个类里编写一个方法booleanrepeatElement(inta[])，该方法借助集合判断数组a是否有重复的元素，即数组a是否有两个或多个元素的值是相同的。

参考教案25（2学时）主要内容教材第12章常用算法与Collections类11.1-11.6排序教材12.1二分查找教材12.1反转与旋转教材12.3洗牌教材12.4求最大值与最小值教材12.5统计次数和频率教材12.6基础算法排序（例子12.1）重点算法1.使用二分法判断句子中的单词（例子12.2）2.判断回文单词和解决约瑟夫问题（例子12.3）3.使用Fisher-Yates洗牌法演示洗牌过程（例子12.4）4.求最大值与最小值（例子12.5）难点算法统计单词、汉字出现而次数和频率（例子12.6）两个学时可以根据实际讲解情况，在时间的分配上有所调整。教学过程设计第1个学时：讲解基础算法：排序（例子12.1）。讲解重点算法：使用二分法判断句子中的单词（例子12.2），判断回文单词和解决约瑟夫问题（例子12.3），使用Fisher-Yates洗牌法演示洗牌过程（例子12.4）。4.求最大值与最小值（例子12.5）。第2个学时：讲解难点算法：统计单词、汉字出现而次数和频率（例子12.6）。多媒体辅助PPT电子讲义。作业在习题12中挑选有关内容布置相关作业。

参考教案26（2学时）主要内容教材第13章图论13.1-13.5无向图教材13.1有向图教材13.2无向网络和有向网络教材13.3图的存储教材13.4图的遍历教材13.5