數(shù)據(jù)結(jié)構(gòu)與算法（Java語言版） 教案15-28（48+8）耿祥義 第7-14章 棧與Stack類-經(jīng)典算法思想

參考教案（共計56學時，含4個上機實踐教案）耿祥義編寫《數(shù)據(jù)結(jié)構(gòu)與算法（java語言版）清華大學出版社出版耿祥義，張躍平主編參考教案15（2學時，實踐）1.實踐前的復習完成下列選擇題。（1）Arrays類的sort()方法是()。A.雙軸快速排序。B.穩(wěn)定排序。C.時間復雜度比氣泡法高的排序。D.時間復雜度比選擇法高的排序。（2）下列敘述正確的是()。A.鏈表的單向迭代器在遍歷鏈表時也可以刪除節(jié)點。B.鏈表的單向或雙向迭代器在遍歷鏈表時，不允許鏈表調(diào)用set(intindex，Eobj)方法更新節(jié)點中的數(shù)據(jù)。C.如果增加或刪除鏈表節(jié)點，鏈表之前的視圖仍然能被使用。D.可以對不可變鏈表經(jīng)行排序操作。（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輸出的結(jié)果是A。B.代碼B輸出的結(jié)果是B。C.代碼C輸出的結(jié)果是B。D.代碼D輸出的結(jié)果是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輸出的結(jié)果是3。B.代碼B輸出的結(jié)果是true。C.代碼C輸出的結(jié)果是1。D.代碼D輸出的結(jié)果是F。2.實踐內(nèi)容完成后，要向老師展示程序的運行效果，老師根據(jù)完成情況，記載相關(guān)成績。（1）輸出int型數(shù)組的一個最長的遞增子數(shù)組，例如，對于int[]a={15,16,6,8,9,10,11,11,11,8,2,10};程序輸出[6,8,9,10,11]。（2）鏈表刪除頭節(jié)點和尾節(jié)點的時間復雜度都是O(1)。對于某些問題，可以利用鏈表的這一特點快速的處理數(shù)據(jù)。編寫一個程序，判斷字符串是否是回文串。算法提示：將字符串中的全部字符按順序依次添加到鏈表，然后開始分別從頭、尾刪除鏈表的節(jié)點，如果字符串是回文串，那么從頭刪除的節(jié)點中的字符一定和從尾刪除的節(jié)點中的字符相同，當鏈表中剩余的節(jié)點數(shù)目不足2個時，停止刪除操作。（3）將一個節(jié)點是Integer的順序表listOne升序排序，然后將另一個節(jié)點是Integer的順序表listTwo中的節(jié)點插入到listOne，并繼續(xù)保持listOne是升序。

參考教案16（2學時）主要內(nèi)容教材第7章棧與Stack類7.1-7.8棧的特點教材7.1棧的創(chuàng)建與獨特的方法教材7.2棧與回文串教材7.3棧與遞歸教材7.4棧與undo操作教材7.5棧與括號匹配教材7.6棧與深度搜素教材7.7棧與后綴表達式教材7.8基礎(chǔ)知識棧的特點。重點知識棧的創(chuàng)建與獨特方法。基礎(chǔ)算法1.利用棧判斷一個字符串是否為回文串（例子7.2）2.使用棧實現(xiàn)撤銷操作（例子7.5）3.檢查括號是否匹配（例子7.6）重點算法用棧模擬老鼠走迷宮（例子7.7）難點算法1.使用棧計算后綴表達式（例子7.8）2.把中綴表達式轉(zhuǎn)換為后綴表達式（例子7.9）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：結(jié)合圖7.1講解棧的特點，使用例子7.1講解如何創(chuàng)建棧以及棧的獨特方法。講解基礎(chǔ)算法：利用棧判斷一個字符串是否為回文串（例子7.2）。例子7.3和7.4可以作為自學內(nèi)容（根據(jù)課堂時間情況）。講解基礎(chǔ)算法：使用棧實現(xiàn)撤銷操作（例子7.5），檢查括號是否匹配（例子7.6）。第2個學時：講解7.7節(jié)，講清什么叫深度優(yōu)先搜索，以及棧為何能體現(xiàn)深度優(yōu)先搜索。結(jié)合例子5.5講解添加節(jié)點。講解重點算法：用棧模擬老鼠走迷宮（例子7.7）。講解難點算法：使用棧計算后綴表達式（例子7.8），要特別結(jié)合圖7.10介紹后綴表達式的算法。對于中綴表達式轉(zhuǎn)換為后綴表達式（例子7.9），老師課堂可以只講算法的思想，其詳細代碼可以留作學生自學。多媒體輔助PPT電子講義。作業(yè)在習題7中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案17（2學時）主要內(nèi)容教材第8章隊列與Stack類8.1-8.8隊列的特點教材8.1隊列的創(chuàng)建與獨特的方法教材8.2隊列與回文串教材8.3隊列與加密解密教材8.4隊列與約瑟夫問題教材8.5隊列與廣度搜素教材8.6隊列與網(wǎng)絡爬蟲教材8.7隊列與排隊教材8.8基礎(chǔ)知識隊列重點知識隊列的創(chuàng)建與獨特方法?；A(chǔ)算法1.利用隊列判斷一個字符串是否為回文串（例子8.2）2.使用隊列加密、解密字符序列（例子8.3）3.隊列與約瑟夫問題（例子8.4）重點算法使用廣度優(yōu)先搜索法進行排雷（例子8.5）難點算法1.使用網(wǎng)絡爬蟲爬去網(wǎng)頁（例子8.6）2.用隊列模擬排隊（例子8.7）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：結(jié)合圖8.1講解隊列的特點，使用例子8.1講解如何創(chuàng)建隊列以及隊列的獨特方法。講解基礎(chǔ)算法：利用隊列判斷一個字符串是否為回文串（例子8.2）。講解基礎(chǔ)算法：使用隊列加密、解密字符序列（例子8.3），隊列與約瑟夫問題（例子8.4）。第2個學時：講解7.7節(jié)，講清什么叫廣度優(yōu)先搜索，以及隊列為何能體現(xiàn)廣度優(yōu)先搜索。講解重點算法：使用廣度優(yōu)先搜索法進行排雷（例子8.5）。講解難點算法：使用網(wǎng)絡爬蟲爬去網(wǎng)頁（例子8.6）。對于難點算法：用隊列模擬排隊（例子8.7），可以根據(jù)時間情況，只講解思想，代碼細節(jié)留給學生自學。多媒體輔助PPT電子講義。作業(yè)在習題8中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案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輸出的結(jié)果是30。B.代碼B輸出的結(jié)果是6。C.代碼C輸出的結(jié)果是180。D.代碼D輸出的結(jié)果是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輸出的結(jié)果是50。B.代碼B輸出的結(jié)果是20。C.代碼C輸出的結(jié)果是30。D.代碼D輸出的結(jié)果是2。（5）下列敘述正確的是()。A.Stack<E>的isEmpty()方法是線程安全的。B.Stack<E>的empty()方法是線程安全的。C.Stack<E>的elementAt(intindex)。方法不是線程安全的。D.Stack<E>的intsearch(Objectobj)方法不是線程安全的。2.實踐內(nèi)容完成后，要向老師展示程序的運行效果，老師根據(jù)完成情況，記載相關(guān)成績。（1）借助棧，在一個類中編寫一個方法publicstaticStringreverse(Strings)，方法返回的String對象中的字符序列是參數(shù)s的字符序列的反轉(zhuǎn)（倒置）字符序列。（2）農(nóng)夫攜帶狼、羊、菜從河東岸到西岸，橋上限制農(nóng)夫每次至多只能攜帶狼、羊、菜中的一種。另外，如果沒有農(nóng)夫看著，羊會吃菜，狼會吃羊，但狼不吃菜。農(nóng)夫帶羊過河辦法之一：①農(nóng)夫帶羊過河，返回。②農(nóng)夫帶狼過河，帶羊返回。③帶菜過河、返回。④帶羊過河。編程程序，通過兩個隊列：一個東岸隊列和西岸隊列，來模擬農(nóng)夫過河。用數(shù)字1代表菜，數(shù)字2代表羊，數(shù)字3代表狼。將數(shù)字1，2，3存入東岸的隊列中。東岸出列到西岸入列時，如果導致東岸的隊列的長度是2，必須保證東岸的隊列中的數(shù)字之和是4，否則重新入列東岸。如果西岸的隊列的長度是2，必須保證西岸的隊列中的數(shù)字之和是4，否則西岸出列，然后再入列東岸。

參考教案19（2學時）主要內(nèi)容教材第9章二叉樹與TreeSet類9.1-9.5二叉樹的基本概念教材9.1遍歷二叉樹教材9.2二叉樹的存儲教材9.3平衡二叉樹教材9.4二叉查詢樹和平衡二叉查詢樹教材9.5基礎(chǔ)知識二叉樹的基本概念重點知識二叉查詢樹和平衡二叉查詢樹?；A(chǔ)算法遍歷與查詢二叉樹（例子9.1）重點算法中序遍歷二叉查詢樹（例子9.2）難點算法創(chuàng)建平衡二叉查詢樹并查詢（例子9.3）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：結(jié)合圖9.1講解二叉樹的基本概念。結(jié)合圖9.2講解遍歷二叉樹：前序遍歷，中序遍歷，后序遍歷。講解基礎(chǔ)算法：遍歷與查詢二叉樹（例子9.1）。第2個學時：講解9.4節(jié)：平衡二叉樹。結(jié)合圖9.4講解重點算法：中序遍歷二叉查詢樹（例子9.2）。講解難點算法：創(chuàng)建平衡二叉查詢樹并查詢（例子9.3）。多媒體輔助PPT電子講義。作業(yè)在習題9中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案20（2學時）主要內(nèi)容教材第9章二叉樹與TreeSet類9.6-9.11TreeSet樹集教材9.6樹集的基本操作教材9.7樹集的視圖教材9.8樹集與數(shù)據(jù)統(tǒng)計教材9.9樹集與過濾數(shù)據(jù)教材9.10樹集與節(jié)目單教材9.11基礎(chǔ)知識TreeSet樹集重點知識樹集的基本操作?；A(chǔ)算法1.借助樹集模擬雙色球（例子9.5）2.使用樹集存放節(jié)目單（例子9.11）重點算法1.統(tǒng)計隨機數(shù)（例子9.8）2.使用樹集過濾數(shù)據(jù)（例子9.9）3.處理重復的數(shù)據(jù)（例子9.10）難點算法借助樹集求最大、最小連接數(shù)（例子9.6）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：結(jié)合例子9.4，講TreeSet樹集和它的基本操作。講解基礎(chǔ)算法：借助樹集模擬雙色球（例子9.5）。講解難點算法：借助樹集求最大、最小連接數(shù)（例子9.6）第2個學時：講解9.8節(jié)：樹集的視圖（含例子9.7）。講解重點算法：統(tǒng)計隨機數(shù)（例子9.8），使用樹集過濾數(shù)據(jù)（例子9.9），處理重復的數(shù)據(jù)（例子9.10）。講解基礎(chǔ)算法：使用樹集存放節(jié)目單（例子9.11）。多媒體輔助PPT電子講義。作業(yè)在習題9中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案21（2學時）主要內(nèi)容教材第10章散列表與HashMap類10.1-10.5散列結(jié)構(gòu)的特點教材10.1簡單的散列函數(shù)教材10.2HashMap類教材10.3散列表的基本操作教材10.4遍歷散列表教材10.5統(tǒng)計字符、單詞出現(xiàn)的次數(shù)和頻率教材10.6基礎(chǔ)知識散列結(jié)構(gòu)的特點重點知識簡單的散列函數(shù)?；A(chǔ)算法遍歷散列表（例子10.4）難點算法統(tǒng)計字符、單詞出現(xiàn)的次數(shù)和頻率（例子10.5）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：結(jié)合圖10.1講清楚散列結(jié)構(gòu)。借助圖10.2至10.4和例子10.1講重點知識點：簡單的散列函數(shù)。第2個學時：借助例子10.2和例子10.3講解HashMap類和散列表的基本操作。講解基礎(chǔ)算法：遍歷散列表（例子10.4）。講解難點算法：統(tǒng)計字符、單詞出現(xiàn)的次數(shù)和頻率（例子10.5）多媒體輔助PPT電子講義。作業(yè)在習題10中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案22（2學時）主要內(nèi)容教材第10章散列表與HashMap類10.1-10.5散列表與單件模式教材10.7散列表與數(shù)據(jù)緩存教材10.8TreeMap類教材10.9Hashtable類教材10.10基礎(chǔ)知識TreeMap類，Hashtable類。重點知識單件模式。基礎(chǔ)算法使用樹映射排序數(shù)據(jù)（例子10.10）重點算法使用散列表緩存數(shù)據(jù)（例子10.7）難點算法用單件模式模擬只有一個太陽（例子10.6）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：結(jié)合圖10.11講解單件模式，然后講解難點算法：用單件模式模擬只有一個太陽（例子10.6）。講解重點算法：使用散列表緩存數(shù)據(jù)（例子10.7）。第2個學時：講解10.9節(jié)：TreeMap類，特別注意講解和HashMap類的不同，講解基礎(chǔ)算法：使用樹映射排序數(shù)據(jù)（例子10.10），對于例子10.8，如果時間不允許，可以讓學生自學。介紹Hashtable類，重點介紹其線程安全的特點，有關(guān)代碼可留給學生自學。多媒體輔助PPT電子講義。作業(yè)在習題10中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案23（2學時）主要內(nèi)容教材第11章集合與HashSet類11.1-11.6集合的特點教材11.1HashSet類教材11.2集合的基本操作教材11.3集合與數(shù)據(jù)過濾教材11.4正整數(shù)集合的生成集教材11.5獲得隨機數(shù)的速度教材11.6基礎(chǔ)知識集合的特點，HashSet類。重點知識集合的基本操作?；A(chǔ)算法使用集合和樹集過濾數(shù)據(jù)（例子11.2）重點算法比較借助數(shù)組、鏈表、樹集、集合獲得隨機數(shù)的速度（例子11.4）難點算法返回集合的生成集（例子11.3）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：結(jié)合例子1講解集合的特點，HashSet類，集合的基本操作。特別強調(diào)：集合的添加、查找和刪除元素等操作的時間復雜度通常為O(1)。講解基礎(chǔ)算法：使用集合和樹集過濾數(shù)據(jù)（例子11.2）。第2個學時：講解難點算法：返回集合的生成集（例子11.3）。講解重點算法：比較借助數(shù)組、鏈表、樹、集合獲得隨機數(shù)的速度（例子11.4）多媒體輔助PPT電子講義。作業(yè)在習題11中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案24（2學時，實踐）1.實踐前的復習完成下列選擇題。（1）對于平衡二叉查詢樹，敘述正確的是()。A.查詢時間復雜度OnB.查詢時間復雜度是O(logn)。C.查詢時間復雜度是O(nlogn)。D.查詢時間復雜度是O(1)。（2）下列敘述錯誤的是()。A.紅黑樹是平衡的二叉查詢樹。B.AVL樹是平衡的二叉查詢樹。C.紅黑樹的查詢時間復雜度是O(logD.AVL樹的查詢時間復雜度是O(（3）對于圖示意的二叉樹，()是中序遍歷的結(jié)果。注意這個二叉樹不是查詢二叉樹。12121117613915圖二叉樹A.691113151712。B.121196131517。C.691113121517。D.961115131712。（4）敘述正確的是()。A.TreeMap<K,V>映射樹也是散列結(jié)構(gòu)。B.TreeMap<K,V>映射樹是紅黑樹結(jié)構(gòu)。C.TreeMap<K,V>映射樹查詢、添加和刪除等操作的時間復雜度都是O(n)D.TreeMap<K,V>映射樹中的Value中不能有兩個相同的對象。（5）敘述正確的是()。A.HashSet集合中的元素僅僅同屬一個集合，無任何關(guān)系。B.HashSet集合中的元素的存儲是鏈式存儲。C.HashSet集合中的元素形成的關(guān)系是線性關(guān)系。D.HashSet集合中的元象的邏輯關(guān)系是樹形關(guān)系。2.實踐內(nèi)容完成后，要向老師展示程序的運行效果，老師根據(jù)完成情況，記載相關(guān)成績。（1）某種學生小檔案的中的數(shù)據(jù)是一個"鍵-值"(key,value)，其中key是學號，value是學生名稱或介紹。編程用HashMap散列表存儲學生小檔案。使用key關(guān)鍵字輸出全部學生的姓名或介紹，輸出樣式是(key,vlaue)。不使用關(guān)鍵字，直接輸出全部學生的小檔案中全部學生的名字。（2）在一個類里編寫一個方法booleanrepeatElement(inta[])，該方法借助集合判斷數(shù)組a是否有重復的元素，即數(shù)組a是否有兩個或多個元素的值是相同的。

參考教案25（2學時）主要內(nèi)容教材第12章常用算法與Collections類11.1-11.6排序教材12.1二分查找教材12.1反轉(zhuǎn)與旋轉(zhuǎn)教材12.3洗牌教材12.4求最大值與最小值教材12.5統(tǒng)計次數(shù)和頻率教材12.6基礎(chǔ)算法排序（例子12.1）重點算法1.使用二分法判斷句子中的單詞（例子12.2）2.判斷回文單詞和解決約瑟夫問題（例子12.3）3.使用Fisher-Yates洗牌法演示洗牌過程（例子12.4）4.求最大值與最小值（例子12.5）難點算法統(tǒng)計單詞、漢字出現(xiàn)而次數(shù)和頻率（例子12.6）兩個學時可以根據(jù)實際講解情況，在時間的分配上有所調(diào)整。教學過程設(shè)計第1個學時：講解基礎(chǔ)算法：排序（例子12.1）。講解重點算法：使用二分法判斷句子中的單詞（例子12.2），判斷回文單詞和解決約瑟夫問題（例子12.3），使用Fisher-Yates洗牌法演示洗牌過程（例子12.4）。4.求最大值與最小值（例子12.5）。第2個學時：講解難點算法：統(tǒng)計單詞、漢字出現(xiàn)而次數(shù)和頻率（例子12.6）。多媒體輔助PPT電子講義。作業(yè)在習題12中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案26（2學時）主要內(nèi)容教材第13章圖論13.1-13.5無向圖教材13.1有向圖教材13.2無向網(wǎng)絡和有向網(wǎng)絡教材13.3圖的存儲教材13.4圖的遍歷教材13.5