1、 .PAGE9 / NUMPAGES9數據結構與算法教案歐訓勇電子信息工程學院第一章 緒論課程簡要說明數據結構是計算機學科的一門核心專業基礎課程，是計算機程序設計的重要理論和實踐基礎。本課程討論了軟件設計中經常遇到的線性表、堆棧、隊列、串、 數組、二叉樹、圖等典型數據結構的設計方法以與各種典型排序和查找算法的性能和設計方法，并介紹了各種典型數據結構的應用。通過本課程的學習，學生對軟件 設計的基本要素和軟件的基本結構有了深入理解，并通過算法設計方法學習和上機編程實踐，編程能力有了進一步提高。課程要求掌握主要容包括：線性表、堆 棧、隊列、串、數組、樹、二叉樹、圖等典型數據結構問題的邏輯結構、存儲結

2、構和操作的實現方法，各種典型的排序和查找算法，以與遞歸算法的設計方法。通過本課程的學習，應使學生掌握各種數據結構的特點：存貯表示、運算方法以與在計算機科學中最基本的應用，培養、訓練學生選用合適的數據結構和運用 C語言編寫質量高、風格好的應用程序與初步評價算法程序的能力；為編譯技術、操作系統和數據庫等后續課程的學習以與為應用軟件特別是非數值應用軟件的開發 打下良好的理論基礎和實踐基礎。要求結合實際問題，學會分析計算機加工的數據對象的特性，能夠選擇適當的數據結構和存儲結構以與相應的算法，并初步掌握算法的簡單時間復雜度分析方法，訓練掌握各種數據結構的表示方法和實現的算法。(1)知識要求：學生通過學習

3、該課程后主要應掌握以下容：掌握程序設計的基本原理和方法了解對各種抽象數據類型的性質掌握處理各種抽象數據類型的基本算法初步掌握算法的簡單時間復雜度分析方法(2)素質要求：學生通過學習該課程后能夠運用數據結構的思想，針對不同數據對象的特性，能夠選擇適當的數據結構和存儲結構以與相應的算法，解決實際的問題。(3)能力要求：學生通過學習該課程后能夠應用一門程序設計語言進行各種應用系統的設計、開發與維護。第一次（2學時）教學主題或章、節課程導論第一章 緒論(1.1節、1.2節)授課類型理論課 實驗課 實習或課程設計 練習課 其他教學過程前面導論 15 分鐘，新課 83分鐘，布置作業 2 分鐘教學方式講授

4、討論 閱讀 示操作 練習 提問 其他教學資源多媒體課件 演示動畫 相關軟件 音像 其他教學目的與要求（分掌握、理解、了解三個層次）：本次課程要求學生了解什么是數據結構、數據結構課程的特點、數據結構研究的容是什么，理解在解決問題過程中所涉與問題中數據之間的邏輯關系，掌握本課程所涉與到的基本名詞、術語和概念，特別是數據的邏輯結構和存儲結構之間的關系與性質。教學容提要：第一部分 前面章節簡要回顧（約15分鐘）介紹數據結構課程的性質、特點、課程的整體框架介紹、本課程學習過程的說明、以與最終的考核方法。理論課和實驗課的要求、所需要的參考教材和習題輔導教材、學好本課程的意義、以與如何學好數據結構這門課程。

5、第二部分 新課（約83分鐘）第一章 緒論本章容概述（約3分鐘）簡述本章基本要求、學習容、重點、以與本章教學容安排1.1 什么是數據結構（約35分鐘）提問：什么是數據結構？分析用計算機可以解決那些問題，其發展的背景以與解決問題的整體過程，引出在用計算機解決問題的過程中，需要考慮到數據與數據之間的關系。舉例說明：（1）圖書檢索系統中所涉與到的數據之間的關系線性關系（2）人家對弈問題過程中所涉與到的棋盤與棋盤數據之間的關系樹型結構（3）十字路口交通燈顏色設計的問題中數據之間的關系圖型結構引出數據結構的定義、研究的容、與其基本概念、發展史和在整個學科中的地位和作用。2 基本概念和術語（約50分鐘）（1

6、）通過例子引出幾個基本概念（約5分鐘）數據：是信息的載體，是描述客觀事物的數、字符、以與所有能輸入到計算機中并被計算機程序識別和處理的符號的集合, 是計算機程序加工的”原料”。數據對象：數據對象是具有一樣性質的數據元素的集合。舉例說明。數據元素：數據的基本單位。在計算機程序中常作為一個整體進行考慮和處理。有時一個數據元素可以由若干數據項(Data Item)組成。舉例說明。數據項：數據項是數據不可分割的最小標識單位。舉例說明。 說明幾者之間的關系和區別。引出數據元素之間的關系、數據結構的定義。（2）數據之間的按照關系不同的分類（約5分鐘）集合：數據元素之間無特殊關系； 線性結構：數據元素之間存

7、在著一個對一個的關系；樹型結構：數據元素之間存在著一個對多個的關系；圖型結構。數據元素之間存在著多對多的關系。（3）數據結構的形式定義（二元組定義）（約10分鐘）Data_Structure = （D, S）其中，D 是數據元素的有限集（即一個數據對象），S 是該對象中所有數據成員之間的關系的有限集合。舉例說明：以復數為例，說明復數類的數據結構形式定義方式。以一個事務管理的程序為例，說明該程序中數據之間的關系，（4）數據的邏輯結構定義、邏輯結構的分類（約10分鐘）數據的邏輯結構從邏輯關系上描述數據，可以看作是從具體問題抽象出來的數據模型，與數據的存儲無關，也與數據元素本身的形式、容、相對位置無

8、關；舉例說明；（5）數據的物理結構定義、物理結構的分類（約15分鐘）數據結構在計算機中的表示(或稱映象）稱為數據的存儲結構，又稱為物理結構。它包括數據元素的表示和關系的表示。物理結構的分類：著重講解順序存儲結構和鏈式存儲結構，并說明二者之間的不同，舉例說明。綜合比較數據邏輯結構和物理結構之間的關系，并舉例說明。（6）數據類型的定義和分類（約5分鐘）數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。數據類型可分兩類：原子類型和結構類型。小結（約2分鐘）容回顧、重點、難點。第三部分 布置作業（約2分鐘） 習題練習。重點和難點： 重點：數據結構所涉與的基本概念、數據結構的分類，數據的邏輯結構

9、和物理結構、他們之間的關系。參考資料：數據結構題集嚴蔚敏等編著，清華大學數據結構學習指導與習題詳解鳳琴等編，清華大學數據結構（C語言篇）習題與解析春葆編，清華大學注意事項與心得： 注意把握時間。注：表中選項打“”第二次（2學時）教學主題或章、節前面章節簡要回顧1.3抽象數據類型、1.4 算法與其分析授課類型理論課 實驗課 實習或課程設計 練習課 其他教學過程前面章節復習 5 分鐘，新課 93 分鐘，布置作業 2 分鐘教學方式講授 討論 閱讀 示操作 練習 提問 其他教學資源多媒體課件 演示動畫 相關軟件 音像 其他教學目的與要求（分掌握、理解、了解三個層次）：了解抽象數據類型的定義、表示和實現

10、方法。理解算法設計的五個要素和基本要求；掌握算法效率的度量方法，著重學習算法的時間復雜度分析。教學容提要：第一部分 前面章節簡要回顧（約5分鐘）前面第一節、第二節容的簡要回顧。第二部分 新課（約93分鐘）本次容概述（約3分鐘）簡述本次課的基本要求、學習容、重點、以與容安排1.3 抽象數據類型（約35分鐘）由數據類型定義引入抽象數據類型的定義。抽象數據類型：由用戶定義，用以表示應用問題的數據模型，指一個數學模型以與定義在此數學模型上的一組操作。 抽象數據類型的定義方式： ADT 抽象數據類型名 數據對象：數據對象的定義 數據關系：數據關系的定義 基本操作：基本操作的定義 ADT 抽象數據類型名抽

11、象數據類型的表示與實現，舉例說明：三元組的表示與實現。類C語言的一些共同的約定。1.4算法和算法分析（約55分鐘） 一、算法的基本概念（約10分鐘）（1）算法的定義：是對特定問題求解步驟的一種描述,是一個有窮的指令集，這些指令表示一個或多個操作。（2）算法的特性(要素) 有窮性：算法應在執行有窮步后結束,且每一步都在有窮時間完成 確定性：每步定義都是確切、無歧義的 可行性：算法中描述的操作應能通過執行有限次已經實現的基本運算實現 輸入：有0個或多個輸入 輸出：有一個或多個輸出(處理結果)。（3）算法設計的要求 正確性：不含有語法錯誤；對于各種合法的輸入數據能夠得到滿足規格說明要求的結果。 可讀

12、性：要求程序有較好的人機交互性,有助于人們對算法的理解。 健壯性：對輸入的非法數據能作出適當的響應或處理。 效率與低存儲需求：主要指算法的執行時間和所需的最大存儲空間，這兩方面主要和問題的規模有關。二、算法效率的度量（約45分鐘）（1）衡量算法的方法（約5分鐘） 算法的后期測試：在算法中的某些部位插裝時間函數 time ( )測定算法完成 某一功能所花費時間。 算法的事前估計：空間復雜度、時間復雜度（2）算法的時間效率度量方法（時間復雜度）（約30分鐘）依據的算法選用何種策略、問題的規模、書寫程序的語言、編譯程序所生成目標代碼的質量、硬件的速度。一個特定算法“運行工作量”大小，只依賴于問題的規

13、模（通常用整數n表示），或者說，它是問題規模的函數。一個算法所耗費的時間，應該是該算法中每條語句的執行時間之和，而每條語句的執行時間又是該語句的執行次數（頻度）與該語句執行一次所需時間的乘積。語句的頻度指的是該語句重復執行的次數。舉例說明。（a） +x; s=0； +x 的頻度為1 （b） for (i=1; i=n; +i) +x; s+=x; +x的頻度為n（c） for (j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x; +x的頻度為n2我們假定，每條語句一次執行的時間都是一樣的，為單位時間。這樣我們對時間的分析就可以獨立于軟硬件系統。時間復雜度是問題規模的函

14、數T( n )。設解決一個問題的規模為n ，基本操作被重復執行的次數是n的一個函數 f（n），假如，隨著問題規模n的增長，算法執行時間的增長率和f(n)的增長率一樣，則可記作： T (n) = O(f(n) 其中T（n）叫算法的漸進時間復雜度，簡稱時間復雜度， O是Order（數量級）的首字母，意思是T（n）與f（n）只差一個常數倍。 舉例說明時間復雜度的計算方法：例對 n 個整數的序列進行選擇排序。其中序列的“長度” n 為問題的規模。void selectSort ( int a , int n ) /對n個整數a0,a1,an-1按遞增順序排序 for ( int i = 0; i n-

15、1; i+ ) int k = i; /從ai查到an-1, 找最小整數, 在ak for ( int j = i+1; j n; j+ ) if ( aj ak ) k = j; int temp = ai; ai = ak; ak = temp; （3）算法的空間效率度量方法（空間復雜度）（約5分鐘）空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的度量，記作：S(n) = O(g(n)表示隨著問題規模n的增大，算法運行所需存儲量的增長率與g(n)的增長率一樣。算法的存儲量包括： 輸入數據所占空間； 程序本身所占空間； 輔助變量所占空間 小結（約3分鐘）容回顧、重點、難點。第三部分 布置作業（約2分