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

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