數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 教案 -單元8查找

教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程代碼總學(xué)時(shí)64課程負(fù)責(zé)人任課教師

單元教案授課日期年月日—月日授課地點(diǎn)授課班級(jí)班級(jí)人數(shù)教學(xué)單元單元8查找教學(xué)時(shí)數(shù)8教學(xué)目標(biāo)AOB1:掌握計(jì)算機(jī)程序設(shè)計(jì)中的線性表、棧、隊(duì)列、樹(shù)和圖的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計(jì)算機(jī)程序設(shè)計(jì)中的線性表、棧、隊(duì)列、樹(shù)、圖的數(shù)據(jù)增、刪、改、查操作運(yùn)算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對(duì)算法的科學(xué)分析方法。BOB1:能根據(jù)實(shí)際問(wèn)題中的數(shù)據(jù)特性選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設(shè)計(jì)出適當(dāng)?shù)乃惴ê统绦颉OB1:掌握使用搜索引擎、論壇、幫助文檔、課外書(shū)籍等方法解決學(xué)習(xí)中出現(xiàn)的問(wèn)題；EOB2:能主動(dòng)閱讀書(shū)后拓展知識(shí)并進(jìn)行實(shí)驗(yàn)驗(yàn)證；EOB3:能獨(dú)立分析解決問(wèn)題，能把自己的想法用代碼實(shí)現(xiàn)。教學(xué)方式混合式教學(xué)評(píng)價(jià)方式課堂考勤（20%），課堂活動(dòng)參與程度（20%）線上單元測(cè)試（40%）線下課堂教學(xué)參與程度（20%）教學(xué)資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言描述），陳媛，清華大學(xué)大學(xué)出版社2.電腦50臺(tái)（含eclips）;3.網(wǎng)絡(luò)學(xué)習(xí)資源：/forums/ST_Arithmetic：課程平臺(tái)網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學(xué)設(shè)計(jì)第一次課（2學(xué)時(shí)）教學(xué)內(nèi)容1查找的概念關(guān)鍵字：數(shù)據(jù)元素中的一個(gè)數(shù)據(jù)項(xiàng)，可以標(biāo)識(shí)數(shù)據(jù)元素，主關(guān)鍵字，次關(guān)鍵字查找表：具有同一屬性的數(shù)據(jù)元素的集合，分為靜態(tài)查找表和動(dòng)態(tài)查找表兩類(lèi)查找：給定關(guān)鍵字值K，在表中找出關(guān)鍵字等于給定值K的結(jié)點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置。否則查找失敗，返回相關(guān)的指示信息查找方法的評(píng)價(jià)查找效率：占用存儲(chǔ)空間多少，算法本身復(fù)雜程度平均查找長(zhǎng)度ASL：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值靜態(tài)查找靜態(tài)查找問(wèn)題：查找過(guò)程中數(shù)據(jù)不變靜態(tài)查找表結(jié)構(gòu)：順序表，線性鏈表靜態(tài)查找分類(lèi)：順序查找、折半查找、分塊查找等2順序查找查找過(guò)程:從表的一端開(kāi)始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較順序查找的評(píng)價(jià)：查找成功時(shí)，平均查找長(zhǎng)度約為元素個(gè)數(shù)的一半順序查找的優(yōu)點(diǎn)：算法簡(jiǎn)單，順序表或用鏈表均適用，結(jié)點(diǎn)是否按關(guān)鍵字有序，都同樣適用順序查找的缺點(diǎn)：查找效率低提高順序查找的效率：合理安排節(jié)點(diǎn)位置，使訪問(wèn)越頻繁的數(shù)據(jù)，比較的次數(shù)越少3.折半查找二分查找條件：順序表，表中數(shù)據(jù)元素按關(guān)鍵字有序基本思想：每次將待查記錄所在區(qū)間縮小一半舉例實(shí)現(xiàn)過(guò)程的基本思想：確定查找區(qū)間的中點(diǎn)mid，將待查的K值與seqlist[mid].key比較，若相等，查找成功并返回此位置；若不相等，確定新的查找區(qū)間,返回1，重新開(kāi)始二分法查找，當(dāng)上下界相等時(shí),結(jié)束查找過(guò)程。二分查找過(guò)程二叉樹(shù)實(shí)現(xiàn)已知表中有n個(gè)結(jié)點(diǎn)，以當(dāng)前查找區(qū)間的中點(diǎn)為作為根，左半?yún)^(qū)和右半?yún)^(qū)中的結(jié)點(diǎn)分別作為根的左子樹(shù)和右子樹(shù)。由此得到的二叉樹(shù)，稱為二分查找的判定樹(shù)(DecisionTree)或比較樹(shù)(ComparisonTree)折半查找的特點(diǎn)雖然二分查找的效率高，但是要將表按關(guān)鍵字排序。只適用于順序存儲(chǔ)結(jié)構(gòu)。為保持表的有序性，在順序結(jié)構(gòu)里插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)。適用于表結(jié)點(diǎn)比較穩(wěn)定的，很少做插入或刪除操作的順序表。不適用于鏈表。教學(xué)重點(diǎn)順序查找，折半查找教學(xué)難點(diǎn)折半查找的實(shí)現(xiàn)教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)講評(píng)和考勤（5分鐘）1平臺(tái)發(fā)布任務(wù)2考勤1考勤講授（80分鐘）1.查找的概念（15分鐘）2.順序查找（25分鐘）3.折半查找（40分鐘）1.積極回答教師提問(wèn)2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過(guò)程中出現(xiàn)的，問(wèn)題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)第二次課（2學(xué)時(shí)）教學(xué)內(nèi)容技能訓(xùn)練：折半查找訓(xùn)練目標(biāo)：掌握利用二分查找判定樹(shù)實(shí)現(xiàn)折半查找的方法訓(xùn)練步驟：1根據(jù)數(shù)組元素的個(gè)數(shù)創(chuàng)建完全二叉樹(shù)2數(shù)組中的元素是有序的，對(duì)建立好的二叉樹(shù)進(jìn)行中序遍歷，同時(shí)按順序放入數(shù)據(jù)。完成二分查找判定樹(shù)的創(chuàng)建3創(chuàng)建查詢?cè)氐姆椒?主函數(shù)測(cè)試方法教學(xué)重點(diǎn)二分查找判定樹(shù)的創(chuàng)建，查詢?cè)氐姆椒ń虒W(xué)難點(diǎn)二分查找判定樹(shù)的創(chuàng)建教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)考勤（5分鐘）1.考勤1.考勤技能訓(xùn)練（80分鐘）1.布置技能訓(xùn)練任務(wù)（5分鐘）2.在技能訓(xùn)練過(guò)程中巡視并啟發(fā)學(xué)生解決遇到的問(wèn)題。1.獨(dú)立完成老師下發(fā)的課堂練習(xí)2.在遇到問(wèn)題時(shí)與同學(xué)討論。總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務(wù)1.思考教師總結(jié)，2.記錄教師的任務(wù)要求并在課后完成。第三次課（2學(xué)時(shí)）教學(xué)內(nèi)容分塊查找分塊查找表由“分塊有序”的線性表和索引表組成。塊間有序，塊內(nèi)無(wú)序。索引表有序，又稱“索引順序查找”。查找過(guò)程：將表分成幾塊，塊內(nèi)無(wú)序，塊間有序。先確定待查記錄所在塊，再在塊內(nèi)查找。適用條件：后一個(gè)子表中,所有記錄的關(guān)鍵字均大于前一個(gè)子表中的最大關(guān)鍵字。算法實(shí)現(xiàn)：順序存儲(chǔ)待查記錄,每個(gè)數(shù)據(jù)元素包含關(guān)鍵字域。建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針。分塊查找算法分析假設(shè)：表中有10000個(gè)結(jié)點(diǎn)順序查找：平均比較5000次二分查找：平均比較14次分塊查找：將其分成100個(gè)數(shù)據(jù)塊，每塊含100個(gè)數(shù)據(jù)元素。順序查找確定塊，塊內(nèi)順序查找，平均比較100次分塊查找的效率于順序和二分查找之間動(dòng)態(tài)查找靜態(tài)查找過(guò)程中僅僅是執(zhí)行“查找”的操作動(dòng)態(tài)查找在查找過(guò)程中會(huì)對(duì)表進(jìn)行構(gòu)建、擴(kuò)充、修改、刪除的操作動(dòng)態(tài)查找：二叉排序樹(shù)、平衡二叉樹(shù)、B-/B+樹(shù)、紅黑樹(shù)等二叉排序樹(shù)查找二叉排序樹(shù)定義：二叉排序樹(shù)或者是一棵空樹(shù)；或者滿足如下性質(zhì):若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。左右子樹(shù)本身也都是二叉排序樹(shù)。按中序遍歷該樹(shù)得到的序列是遞增有序的二叉排序樹(shù)生成：從空樹(shù)出發(fā)，經(jīng)過(guò)一系列的插入操作之后，可生成一棵二叉排序樹(shù)。插入原則：若二叉排序樹(shù)為空，則插入結(jié)點(diǎn)應(yīng)為新的根結(jié)點(diǎn)；否則，在其左、右子樹(shù)上查找，直至某個(gè)結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)為空為止，則插入結(jié)點(diǎn)應(yīng)為該結(jié)點(diǎn)的左孩子或右孩子二叉排序樹(shù)的生成舉例：二叉排序樹(shù)查找算法分析平均查找長(zhǎng)度和二叉樹(shù)的形態(tài)有關(guān)二叉排序樹(shù)是把表的n個(gè)結(jié)點(diǎn)依次插入生成的最壞情況，二叉排序樹(shù)是深度為n的單支樹(shù)，其平均查找長(zhǎng)度和順序查找相同，是(n+1)/2最好情況，生成的二叉排序樹(shù)，其形態(tài)比較勻稱，得到與二分查找的判定樹(shù)形態(tài)相似的二叉排序樹(shù)，此時(shí)平均查找長(zhǎng)度大約是log2n。插入、刪除和查找算法的時(shí)間復(fù)雜度均為O(log2n)。教學(xué)重點(diǎn)分塊查找，二叉排序樹(shù)查找教學(xué)難點(diǎn)二叉排序樹(shù)查找教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)講評(píng)和考勤（5分鐘）1平臺(tái)發(fā)布任務(wù)2考勤1考勤講授（70分鐘）1.分塊查找（25分鐘）2.靜態(tài)查找算法比較（10分鐘）3動(dòng)態(tài)查找（5分鐘）4.二叉排序樹(shù)查找（30分鐘）1.積極回答教師提問(wèn)2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)課堂練習(xí)（10分鐘）1.二叉排序樹(shù)的構(gòu)造（10分鐘）認(rèn)真思考，獨(dú)立完成練習(xí)總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過(guò)程中出現(xiàn)的，問(wèn)題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)第五次課（2學(xué)時(shí)）教學(xué)內(nèi)容散列表查找概念的引入：二分法,順序查找，二叉排序樹(shù)都以關(guān)鍵字的比較作為查找的基礎(chǔ)。如果建立關(guān)鍵字與存儲(chǔ)地址的映射關(guān)系，則已知關(guān)鍵字時(shí)，可以直接定位到相應(yīng)的存儲(chǔ)位置上，從而達(dá)到查找的目的理想情況下，無(wú)須任何比較就可以找到待查關(guān)鍵字，查找的期望時(shí)間為O(1)以結(jié)點(diǎn)的關(guān)鍵字K為自變量，通過(guò)一個(gè)確定的函數(shù)關(guān)系h，計(jì)算出函數(shù)值h(K)這個(gè)值可理解為結(jié)點(diǎn)的存儲(chǔ)地址，將結(jié)點(diǎn)存入h(K)所指的存儲(chǔ)位置上查找時(shí)，根據(jù)關(guān)鍵字，用函數(shù)h(K)計(jì)算出地址，再到相應(yīng)的單元里去取出結(jié)點(diǎn)。函數(shù)h稱為散列函數(shù)，h(K)稱為散列地址，散列方法存儲(chǔ)的線性表稱為散列表(HashTable)，哈希表舉例：常用哈希函數(shù)-平方取中法求關(guān)鍵字的平方值,擴(kuò)大相近數(shù)的差別然后根據(jù)表長(zhǎng)度取中間的幾位數(shù)作為散列函數(shù)值如{0100,0010,1010,1001,0111}，散列表長(zhǎng)度為1000平方后得到：{0010000,0012100,1020100,1002001,0012321}根據(jù)表長(zhǎng)度,可取中間三位數(shù)作為散列地址：{100，121，201，020，123}常用哈希函數(shù)-除留余數(shù)法h(key)=key％p例：{159，259，359，459，559}取p=100,得到地址:{59,59,59,59,59}取p=1000,得到地址:{159,259,359,459,559}選取的p值應(yīng)使得散列函數(shù)值盡可能與關(guān)鍵字的各位相關(guān)，p最好為素?cái)?shù)，通常p的取值為表的長(zhǎng)度m常用的哈希函數(shù)-數(shù)字分析法例：有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)常用的哈希函數(shù)-折疊例：關(guān)鍵字為：0442205864，哈希地址位數(shù)為4將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址，此法適合于關(guān)鍵字的數(shù)字位數(shù)特別多的情形散列表沖突散列表的沖突現(xiàn)象：兩個(gè)不同的關(guān)鍵字，可能得到相同的散列函數(shù)值，從而被映射到表的同一位置上稱為沖突或碰撞。發(fā)生沖突的若干個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞避免沖突：選擇合適的散列函數(shù)，關(guān)鍵字的個(gè)數(shù)小于或等于散列表的長(zhǎng)度沖突不可能完全避免：若關(guān)鍵字的個(gè)數(shù)大于散列表的長(zhǎng)度,則無(wú)論怎樣設(shè)計(jì)h，也不可能完全避免沖突。設(shè)計(jì)散列函數(shù)時(shí)盡可能使沖突最少。要確定解決沖突的方法，使發(fā)生沖突的同義詞能夠存儲(chǔ)到散列表中。處理沖突的方法-線性探測(cè)法堆積現(xiàn)象：散列地址不同的關(guān)鍵字，爭(zhēng)奪同一個(gè)后繼位置。使得非同義詞也加入了探測(cè)序列，增加了探查的長(zhǎng)度，即增加了查找時(shí)間。若散列函數(shù)不好或裝填因子過(guò)大，會(huì)使堆積加劇。裝填因子α=填入表中的元素個(gè)數(shù)/哈希表的長(zhǎng)度處理沖突的方法-拉鏈法分配指針數(shù)組，建立m個(gè)空鏈表，由哈希函數(shù)對(duì)關(guān)鍵字轉(zhuǎn)換后，映射到同一哈希地址的同義詞均加入到相應(yīng)指向的鏈表中拉鏈法優(yōu)點(diǎn)：處理沖突簡(jiǎn)單，無(wú)堆積現(xiàn)象，非同義詞絕不會(huì)發(fā)生沖突，因此平均查找長(zhǎng)度較短；鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，更適合于造表前無(wú)法確定表長(zhǎng)的情況；開(kāi)放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。拉鏈法缺點(diǎn)：指針需要額外的空間。當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，效率低于線性探測(cè)法。若將節(jié)省的指針空間用來(lái)擴(kuò)大散列表的規(guī)模，可使裝填因子變小，減少了開(kāi)放定址法中的沖突，從而提高平均查找速度處理沖突的方法-建立公共溢出區(qū)建立公共溢出區(qū)存儲(chǔ)所有哈希沖突的數(shù)據(jù)。為哈希地址集分配兩個(gè)表：一個(gè)基本表，每個(gè)單元只能存放一個(gè)元素，一個(gè)溢出表，放“溢出”的元素散列表的查找分析散列表的查找過(guò)程基本上和造表過(guò)程相同。一些關(guān)鍵字可通過(guò)哈希函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵字在哈希函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵字進(jìn)行比較的過(guò)程。哈希表查找效率的量度，用平均查找長(zhǎng)度來(lái)衡量。查找過(guò)程中，關(guān)鍵字的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素，有以下三個(gè)方面，哈希函數(shù)是否均勻，處理沖突的方法，哈希表的裝填因子教學(xué)重點(diǎn)常用哈希函數(shù)，處理沖突的方法教學(xué)難點(diǎn)常用哈希函數(shù)，處理沖突的方法教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)講評(píng)和考勤（5分鐘）1.平臺(tái)發(fā)布任務(wù)2.考勤1.考勤講授（80分鐘）1.散列的引入（10分鐘）2.常用哈希函數(shù)（30分鐘）3.散列表沖突概念（10分鐘）4.處理沖突的方法（20分鐘）5.散列表的查找分析（10分鐘）1.積極回答教師提問(wèn)2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過(guò)程中出現(xiàn)的，問(wèn)題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)教學(xué)效果與