數(shù)據(jù)結(jié)構(gòu)與算法培訓(xùn)教（學(xué)）案

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

2、構(gòu)和操作的實(shí)現(xiàn)方法，各種典型的排序和查找算法，以與遞歸算法的設(shè)計(jì)方法。通過本課程的學(xué)習(xí)，應(yīng)使學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)：存貯表示、運(yùn)算方法以與在計(jì)算機(jī)科學(xué)中最基本的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和運(yùn)用 C語言編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序與初步評(píng)價(jià)算法程序的能力；為編譯技術(shù)、操作系統(tǒng)和數(shù)據(jù)庫等后續(xù)課程的學(xué)習(xí)以與為應(yīng)用軟件特別是非數(shù)值應(yīng)用軟件的開發(fā) 打下良好的理論基礎(chǔ)和實(shí)踐基礎(chǔ)。要求結(jié)合實(shí)際問題，學(xué)會(huì)分析計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，能夠選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以與相應(yīng)的算法，并初步掌握算法的簡單時(shí)間復(fù)雜度分析方法，訓(xùn)練掌握各種數(shù)據(jù)結(jié)構(gòu)的表示方法和實(shí)現(xiàn)的算法。(1)知識(shí)要求：學(xué)生通過學(xué)習(xí)

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

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

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

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

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

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

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

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

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

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

13、模（通常用整數(shù)n表示），或者說，它是問題規(guī)模的函數(shù)。一個(gè)算法所耗費(fèi)的時(shí)間，應(yīng)該是該算法中每條語句的執(zhí)行時(shí)間之和，而每條語句的執(zhí)行時(shí)間又是該語句的執(zhí)行次數(shù)（頻度）與該語句執(zhí)行一次所需時(shí)間的乘積。語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。舉例說明。（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我們假定，每條語句一次執(zhí)行的時(shí)間都是一樣的，為單位時(shí)間。這樣我們對(duì)時(shí)間的分析就可以獨(dú)立于軟硬件系統(tǒng)。時(shí)間復(fù)雜度是問題規(guī)模的函

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

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