教案-數(shù)據(jù)結(jié)構(gòu)-查找

教案班級(jí)：學(xué)號(hào)：姓名：日期：教案首頁(yè)第__1__次課授課時(shí)間__2015年10月15日教案完成時(shí)間_2015年10月10日___課程名稱數(shù)據(jù)結(jié)構(gòu)年級(jí)三年級(jí)專業(yè)、層次計(jì)算機(jī)科學(xué)與技術(shù)教員授課方式(大、小班)小班學(xué)時(shí)一學(xué)時(shí)授課對(duì)象計(jì)科1201班授課題目〔章、節(jié)〕第9章9.1.1順序表的查找根本教材或主要參考書(shū)選用教材：《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏編著清華大學(xué)出版社教學(xué)目的與要求：1． 了解抽象數(shù)據(jù)類型靜態(tài)查找表的定義2． 了解順序查找表的存儲(chǔ)結(jié)構(gòu)3． 掌握順序查找表的算法4． 掌握平均查找長(zhǎng)度的定義并且計(jì)算教材分析：本教材采用了理論和實(shí)踐相結(jié)合的方式，注重學(xué)生的編程能力。本書(shū)中涵蓋了多種算法，需要同學(xué)們好好理解，并能夠把所學(xué)的應(yīng)用到實(shí)踐中去。學(xué)情分析：教學(xué)重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的首要工作是訓(xùn)練學(xué)生的編程能力和分析問(wèn)題、解決問(wèn)題的能力。本節(jié)課要求學(xué)生能夠掌握順序查找的根本思想，并應(yīng)用到實(shí)際生活中。要求學(xué)生掌握順序查找表的算法，并且能夠?qū)懗鲰樞虿檎冶淼某绦?。大體內(nèi)容與時(shí)間安排，教學(xué)方法〔教學(xué)設(shè)計(jì)〕：列舉生活中的實(shí)例，并進(jìn)行這一節(jié)內(nèi)容的導(dǎo)入〔1分鐘〕靜態(tài)查找表的定義〔2分鐘〕順序查找的思想及算法〔5分鐘〕順序查找的優(yōu)缺點(diǎn)〔1分鐘〕5、課程總結(jié)及布置作業(yè)〔1分鐘〕教學(xué)方法：實(shí)例法：利用例如的方式，把教學(xué)內(nèi)容與這些內(nèi)容有機(jī)的結(jié)合起來(lái)啟發(fā)法：先從直觀意義或直觀解釋入手，引出實(shí)例，進(jìn)而分析討論畫(huà)圖法：將順序查找過(guò)程畫(huà)成圖，以加強(qiáng)理解?！步贪咐m(xù)頁(yè)〕教學(xué)過(guò)程一列舉生活中的實(shí)例，并進(jìn)行這一節(jié)內(nèi)容的導(dǎo)入我們已經(jīng)結(jié)束了上一章內(nèi)容的學(xué)習(xí)，下面我們來(lái)進(jìn)行新的一章的學(xué)習(xí)。在學(xué)習(xí)新的內(nèi)容之前，我們先來(lái)觀察幾個(gè)生活中的例子。在生活中，大家有沒(méi)有想過(guò)字典的排列方式和各種名單的排列方式，還有這樣做的方便之處在哪里，為什么要編號(hào)處理。首先我們來(lái)想查字典的情況：假設(shè)要查到一個(gè)字，我們通?？梢杂煤芏喾N不同的方法找到這個(gè)字。由于字典里的字都是按順序排的，我們可以從第一頁(yè)依次找，直到找到這個(gè)字，我們也可以從中間找，看這個(gè)字在在這一頁(yè)的前面還是后面，然后一次接一次直到找到這個(gè)字。假設(shè)字典里的字都是無(wú)序的，錯(cuò)綜復(fù)雜的，我們要想找到某個(gè)字，真的很麻煩。所以我們從中得到一個(gè)結(jié)論：有序表查找比擬方便，無(wú)序表查找費(fèi)時(shí)。每個(gè)人的學(xué)號(hào)都代表了不同的含義，比方學(xué)號(hào)“”,022代表學(xué)院，10代表計(jì)算機(jī)專業(yè)，1201代表班級(jí)，40代表是第40個(gè)同學(xué)，所以“”代表的索引信息我們可以得知這個(gè)同學(xué)是在信息技術(shù)工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)1201班40號(hào)學(xué)生，簡(jiǎn)單的一個(gè)學(xué)號(hào)便代表了這么多信息，我們可以根據(jù)學(xué)號(hào)查找到這位同學(xué)。通過(guò)以上這些例子我們可以知道不同的排序決定了不同的查找方法，查字典的不同方法代表了不同的查找方法，各種查找方法有各自的特點(diǎn)。那么我們就來(lái)學(xué)習(xí)新旳一章，第九章查找表。下面我們來(lái)學(xué)習(xí)9.1.1的內(nèi)容我們先來(lái)看靜態(tài)查找表的定義二、靜態(tài)查找表的定義抽象數(shù)據(jù)類型靜態(tài)查找表的定義為：ADTStaticSearchTable{數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：R數(shù)據(jù)元素的靜態(tài)查找表ST根本操作P：Create(&ST,n);初始條件：靜態(tài)查找表ST存在。操作結(jié)果：銷毀表ST。Search(ST,key);初始條件：靜態(tài)查找表ST存在，key為和關(guān)鍵字類型相同的給定值。操作結(jié)果：假設(shè)ST中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，那么函數(shù)值為該元素值或在表中的位置，否那么為“空”。Traverse(ST,Visit());初始條件：靜態(tài)查找表ST存在，Visit是對(duì)元素操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次又一次。一旦visit()失敗，那么操作失敗。教具:教科書(shū)時(shí)間分配：舉例并導(dǎo)入〔2分鐘〕教具:教科書(shū)時(shí)間分配：靜態(tài)查找表的定義〔1分鐘〕教學(xué)過(guò)程三、順序查找的思想和算法。順序查找的查找思想：從表的一端開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比擬，假設(shè)某個(gè)記錄的關(guān)鍵字和給定值進(jìn)行比擬相等，那么查找成功，找到所查記錄，其關(guān)鍵字和給定值比擬不相等，那么說(shuō)明表中沒(méi)有所查記錄，查找不成功。此查找過(guò)程可用算法描述。技巧：把待查關(guān)鍵字key存入表頭或表尾〔俗稱“哨兵”〕，這樣可以加快執(zhí)行速度。例子：順序查找的算法：IntSeqSearch(SqlListr,intk,intn){i=1;while(r[i].key!=k&&i<=n)i++;if(i>n)i=0;return(i);}四、順序查找的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：算法簡(jiǎn)單，對(duì)表的結(jié)構(gòu)無(wú)特別要求，只要當(dāng)前掃描到的節(jié)點(diǎn)關(guān)鍵字與K值相等就行。缺點(diǎn)：查找效率低，當(dāng)n較大時(shí)不宜采用。五、總結(jié)并布置作業(yè)教具:教科書(shū)時(shí)間分配：順序查找的思想和算法〔5分鐘〕教具:電腦、投影儀、教科書(shū)時(shí)間分配：順序查找的優(yōu)缺點(diǎn)〔1分鐘〕總結(jié)并布置作業(yè)〔1分鐘〕小結(jié)本節(jié)課結(jié)合教學(xué)大綱對(duì)教材充分的分析，通過(guò)復(fù)習(xí)檢查，導(dǎo)入新課，運(yùn)用各種教學(xué)方案，講授新課，并對(duì)重難點(diǎn)逐個(gè)突破，討論重難點(diǎn)逐個(gè)突破，布置作業(yè)，并延伸到下節(jié)課內(nèi)容的教學(xué)過(guò)程，讓學(xué)生到達(dá)預(yù)定的知識(shí)、能力、技能、素質(zhì)。復(fù)習(xí)思考題、作業(yè)題1． 請(qǐng)同學(xué)們根據(jù)一個(gè)表{24,3,2,5,12,78,49,98,54,34}，寫(xiě)出順序查找到數(shù)字12的算法。2．