數(shù)據(jù)結(jié)構(gòu)與算法教案

數(shù)據(jù)結(jié)構(gòu)與算法教案歐訓(xùn)勇電子信息工程學(xué)院第一章緒論課程簡(jiǎn)要說(shuō)明軟件設(shè)計(jì)的基本要素和軟件的基本結(jié)構(gòu)有了深入理解，并通過(guò)算法設(shè)計(jì)方法學(xué)性表、堆棧、隊(duì)列、串、數(shù)組、樹(shù)、二叉樹(shù)、圖等典型數(shù)據(jù)結(jié)構(gòu)問(wèn)題的邏輯結(jié)設(shè)計(jì)方法。用C語(yǔ)言編寫(xiě)質(zhì)量高、風(fēng)格好的應(yīng)用程序及初步評(píng)價(jià)算法程序的能力；為編譯件的開(kāi)發(fā)打下良好的理論基礎(chǔ)和實(shí)踐基礎(chǔ)。方法，訓(xùn)練掌握各種數(shù)據(jù)結(jié)構(gòu)的表示方法和實(shí)現(xiàn)的算法。(1)知識(shí)要求：學(xué)生通過(guò)學(xué)習(xí)該課程后主要應(yīng)掌握以下內(nèi)容：①掌握程序設(shè)計(jì)的基本原理和方法②了解對(duì)各種抽象數(shù)據(jù)類(lèi)型的性質(zhì)③掌握處理各種抽象數(shù)據(jù)類(lèi)型的基本算法④初步掌握算法的簡(jiǎn)單時(shí)間復(fù)雜度分析方法(2)素質(zhì)要求：學(xué)生通過(guò)學(xué)習(xí)該課程后能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)的思想，針對(duì)不同際的問(wèn)題。(3)能力要求：學(xué)生通過(guò)學(xué)習(xí)該課程后能夠應(yīng)用一門(mén)程序設(shè)計(jì)語(yǔ)言進(jìn)行各種應(yīng)用系統(tǒng)的設(shè)計(jì)、開(kāi)發(fā)及維護(hù)?！镜谝淮危?學(xué)時(shí)）】章、節(jié)第一章緒論(1.1節(jié)、1.2節(jié))授課類(lèi)型理論課√實(shí)驗(yàn)課實(shí)習(xí)或課程設(shè)計(jì)練習(xí)課其他□教學(xué)過(guò)程前面導(dǎo)論15分鐘，新課83分鐘，布置作業(yè)2分鐘教學(xué)方式講授√討論√閱讀√示范操作練習(xí)提問(wèn)√其他□教學(xué)資源多媒體課件√演示動(dòng)畫(huà)√相關(guān)軟件教學(xué)目的及要求（分掌握、理解、了解三個(gè)層次）：的關(guān)系及性質(zhì)。教學(xué)內(nèi)容提要：第一部分前面章節(jié)簡(jiǎn)要回顧（約15材、學(xué)好本課程的意義、以及如何學(xué)好數(shù)據(jù)結(jié)構(gòu)這門(mén)課程。第二部分新課（約83本章內(nèi)容概述（約3在用計(jì)算機(jī)解決問(wèn)題的過(guò)程中，需要考慮到數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。舉例說(shuō)明：（1）圖書(shū)檢索系統(tǒng)中所涉及到的數(shù)據(jù)之間的關(guān)系——線性關(guān)系（2）人家對(duì)弈問(wèn)題過(guò)程中所涉及到的棋盤(pán)與棋盤(pán)數(shù)據(jù)之間的關(guān)系——樹(shù)型結(jié)構(gòu)（3）十字路口交通燈顏色設(shè)計(jì)的問(wèn)題中數(shù)據(jù)之間的關(guān)系——圖型結(jié)構(gòu)位和作用。（1）通過(guò)例子引出幾個(gè)基本概念（約5數(shù)據(jù)：是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合,是計(jì)算機(jī)程序加工的”原料”。數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。舉例說(shuō)明。數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(DataItem)組成。舉例說(shuō)明。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位。舉例說(shuō)明。說(shuō)明幾者之間的關(guān)系和區(qū)別。引出數(shù)據(jù)元素之間的關(guān)系、數(shù)據(jù)結(jié)構(gòu)的定義。（2）數(shù)據(jù)之間的按照關(guān)系不同的分類(lèi)（約5線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一個(gè)對(duì)一個(gè)的關(guān)系；樹(shù)型結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一個(gè)對(duì)多個(gè)的關(guān)系；（3）數(shù)據(jù)結(jié)構(gòu)的形式定義（二元組定義）（約10Data_Structure=（D,是數(shù)據(jù)元素的有限集（即一個(gè)數(shù)據(jù)對(duì)象），S是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。的程序?yàn)槔?，說(shuō)明該程序中數(shù)據(jù)之間的關(guān)系，（4）數(shù)據(jù)的邏輯結(jié)構(gòu)定義、邏輯結(jié)構(gòu)的分類(lèi)（約10模型，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，也與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置無(wú)關(guān)；舉例說(shuō)明；（5）數(shù)據(jù)的物理結(jié)構(gòu)定義、物理結(jié)構(gòu)的分類(lèi)（約15數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(或稱(chēng)映象）稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，又稱(chēng)為物理結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。同，舉例說(shuō)明。綜合比較數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間的關(guān)系，并舉例說(shuō)明。（6）數(shù)據(jù)類(lèi)型的定義和分類(lèi)（約5兩類(lèi)：原子類(lèi)型和結(jié)構(gòu)類(lèi)型。第三部分布置作業(yè)（約2習(xí)題練習(xí)。重點(diǎn)和難點(diǎn)：重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)所涉及的基本概念、數(shù)據(jù)結(jié)構(gòu)的分類(lèi)，數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、他們之間的關(guān)系。注意把握時(shí)間。注：表中選項(xiàng)打“√”【第二次（2學(xué)時(shí)）】教學(xué)主題或前面章節(jié)簡(jiǎn)要回顧授課類(lèi)型理論課√實(shí)驗(yàn)課實(shí)習(xí)或課程設(shè)計(jì)練習(xí)課其他□教學(xué)過(guò)程前面章節(jié)復(fù)習(xí)5分鐘，新課93分鐘，布置作業(yè)2分鐘教學(xué)方式講授√討論√閱讀√示范操作練習(xí)提問(wèn)√其他□教學(xué)資源多媒體課件√演示動(dòng)畫(huà)√相關(guān)軟件音像其他√教學(xué)目的及要求（分掌握、理解、了解三個(gè)層次）：求；掌握算法效率的度量方法，著重學(xué)習(xí)算法的時(shí)間復(fù)雜度分析。教學(xué)內(nèi)容提要：本次內(nèi)容概述（約3簡(jiǎn)述本次課的基本要求、學(xué)習(xí)內(nèi)容、重點(diǎn)、以及內(nèi)容安排§1.3抽象數(shù)據(jù)類(lèi)型（約35由數(shù)據(jù)類(lèi)型定義引入抽象數(shù)據(jù)類(lèi)型的定義。及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類(lèi)型的定義方式：§1.4算法和算法分析（約55些指令表示一個(gè)或多個(gè)操作。（2）算法的特性(要素)–有窮性：算法應(yīng)在執(zhí)行有窮步后結(jié)束,且每一步都在有窮時(shí)間內(nèi)完成–確定性：每步定義都是確切、無(wú)歧義的–可行性：算法中描述的操作應(yīng)能通過(guò)執(zhí)行有限次已經(jīng)實(shí)現(xiàn)的基本運(yùn)算實(shí)現(xiàn)–輸入：有0個(gè)或多個(gè)輸入–輸出：有一個(gè)或多個(gè)輸出(處理結(jié)果)。–正確性：不含有語(yǔ)法錯(cuò)誤；對(duì)于各種合法的輸入數(shù)據(jù)能夠得到滿足規(guī)格說(shuō)明要求的結(jié)果。–可讀性：要求程序有較好的人機(jī)交互性,有助于人們對(duì)算法的理解。–健壯性：對(duì)輸入的非法數(shù)據(jù)能作出適當(dāng)?shù)捻憫?yīng)或處理。–效率與低存儲(chǔ)需求：主要指算法的執(zhí)行時(shí)間和所需的最大存儲(chǔ)空間，這兩方面主要和問(wèn)題的規(guī)模有關(guān)。二、算法效率的度量（約45–算法的后期測(cè)試：在算法中的某些部位插裝時(shí)間函數(shù)time(某一功能所花費(fèi)時(shí)間。–算法的事前估計(jì)：空間復(fù)雜度、時(shí)間復(fù)雜度（2）算法的時(shí)間效率度量方法（時(shí)間復(fù)雜度）（約30依據(jù)的算法選用何種策略、問(wèn)題的規(guī)模、書(shū)寫(xiě)程序的語(yǔ)言、編譯程序所生成目標(biāo)代碼的質(zhì)量、硬件的速度。一個(gè)特定算法“運(yùn)行工作量”大小，只依賴(lài)于問(wèn)題的規(guī)模（通常用整數(shù)n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。的執(zhí)行時(shí)間又是該語(yǔ)句的執(zhí)行次數(shù)（頻度）與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。語(yǔ)句的頻度指的是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)。舉例說(shuō)明。（a）{++x;s=0；}++x的頻度為1{++x;s+=x;}++x的頻度為n2的分析就可以獨(dú)立于軟硬件系統(tǒng)。時(shí)間復(fù)雜度是問(wèn)題規(guī)模的函數(shù)——T(n)。設(shè)解決一個(gè)問(wèn)題的規(guī)模為nn的一個(gè)函數(shù)n假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則其中T（n）叫算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度，O是Order（數(shù)量例對(duì)n個(gè)整數(shù)的序列進(jìn)行選擇排序。其中序列的“長(zhǎng)度”n為問(wèn)題的規(guī)模。//對(duì)n個(gè)整數(shù)a[0],a[1],…,a[n-1]按遞增順序排序inttemp=a[i];a[i]=a[k];a[k]=temp;空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的度量，記作：表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。算法的存儲(chǔ)量包