數(shù)據(jù)結(jié)構(gòu)授課教案-第1章

1、山東輕工業(yè)學(xué)院教師授課教案課程名稱：數(shù)據(jù)結(jié)構(gòu)（計科）課程代碼：學(xué) 分：4.5課程類別：必修開課單位:信息科學(xué)與技術(shù)學(xué)院授課班級：授課教師：楊春花 山東輕工業(yè)學(xué)院教務(wù)處制授課時間年 月 日 星期 第 節(jié)年 月 日 星期 第 節(jié)年 月 日 星期 第 節(jié)授課內(nèi)容概要第一章 緒論第一節(jié) 什么是數(shù)據(jù)結(jié)構(gòu)第二節(jié) 基本概念和術(shù)語第三節(jié) 抽象數(shù)據(jù)類型的表示與實現(xiàn)第四節(jié) 算法和算法分析目的要求目的：了解數(shù)據(jù)結(jié)構(gòu)課程及相關(guān)的基本術(shù)語，了解算法的描述和分析?；疽螅赫莆諗?shù)據(jù)結(jié)構(gòu)的基本概念和相關(guān)術(shù)語、數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的分類、時間復(fù)雜度的概念和分析方法；了解數(shù)據(jù)類型和抽象數(shù)據(jù)類型的概念；理解數(shù)據(jù)的邏輯結(jié)構(gòu)、存

2、儲結(jié)構(gòu)和運算之間的關(guān)系，理解算法的描述方法、概念、特性和設(shè)計目標(biāo)；。重 點數(shù)據(jù)結(jié)構(gòu)的基本概念；數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算之間的關(guān)系；數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的分類；算法的時間復(fù)雜度的概念和分析方法。難點算法的時間復(fù)雜度計算。作業(yè)布置習(xí)題1參考書1. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版), 嚴(yán)蔚敏，清華大學(xué)出版社，2002。3. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+語言描述，(美)Sartaj Sahni著，汪詩林等譯，機(jī)械工業(yè)出版社，2002。課 型理論課學(xué)時分配復(fù) 習(xí) 分鐘主要教具投影、黑板講 授 分鐘教學(xué)方法講解、提問、示例指 導(dǎo) 分鐘教學(xué)手段板書、課件總 結(jié) 分鐘備注共4學(xué)時注：課型一欄填寫理論課、實驗課、

3、習(xí)題課等授 課 內(nèi) 容備 注課程介紹：教材: 數(shù)據(jù)結(jié)構(gòu)（ C語言版），嚴(yán)蔚敏 吳偉民，清華大學(xué)出版社，2002參考教材: 1 數(shù)據(jù)結(jié)構(gòu)題集 （ C語言版），嚴(yán)蔚敏 吳偉民，清華大學(xué)出版社2 數(shù)據(jù)結(jié)構(gòu)（ C語言篇）習(xí)題與解析，李春葆，清華大學(xué)出版社學(xué)時數(shù)：72（講課：64，實驗：8）；課程設(shè)計（1周）課程性質(zhì)及特點 數(shù)據(jù)結(jié)構(gòu)是一門專業(yè)基礎(chǔ)課，是十分重要的核心課程。 難度大 綜合性強(qiáng) 必須下苦功學(xué)習(xí) 學(xué)習(xí)方法: 1戒驕戒躁，踏實學(xué)習(xí)，打好基礎(chǔ)；2聽、記、練結(jié)合，積極思考。第一章 緒論第一節(jié) 什么是數(shù)據(jù)結(jié)構(gòu)1 數(shù)據(jù)結(jié)構(gòu)課程研究的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機(jī)操作對

4、象以及它們之間的關(guān)系和操作的學(xué)科。2數(shù)據(jù)結(jié)構(gòu)課程體系的形成1968年美國唐歐克努特（Donald E. Knuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系：它所著的計算機(jī)程序設(shè)計技巧（The Art of Computer Programming）第一卷基本算法是第一本系統(tǒng)闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。第二節(jié) 基本概念和術(shù)語1數(shù)據(jù)數(shù)據(jù)(Data):是對客觀事物的符號表示。在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。2數(shù)據(jù)元素數(shù)據(jù)元素(Data Element)：是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項

5、是數(shù)據(jù)的不可分割的最小單位。3數(shù)據(jù)對象的概念數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。在某個具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對象。4數(shù)據(jù)結(jié)構(gòu)的概念和分類數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的分類：1)集合：結(jié)構(gòu)中的數(shù)據(jù)元素“同屬于一個集合”。2)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。3)樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。例：某班學(xué)生基本情況登記表家族的族譜

6、對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題：1）數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作； 2）數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)；數(shù)據(jù)結(jié)構(gòu)的另一種定義：把按某種邏輯關(guān)系組織起來的一組節(jié)點（數(shù)據(jù)元素），按一定的存儲方式存儲于計算機(jī)中，并在其上定義一個運算的集合，稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的三個組成部分： 1)數(shù)據(jù)的邏輯結(jié)構(gòu) 2)數(shù)據(jù)的存儲結(jié)構(gòu) 3)數(shù)據(jù)的運算一、數(shù)據(jù)（邏輯）結(jié)構(gòu)的表示1)圖示表示2)二元組表示Data_Structrue=（D，S）其中: D 是數(shù)據(jù)元素集合，S 是 D 上關(guān)系的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲無關(guān)二、數(shù)據(jù)的存儲結(jié)構(gòu)1)定義數(shù)據(jù)

7、結(jié)構(gòu)在計算機(jī)中的表示或?qū)崿F(xiàn)稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。2)表示包括數(shù)據(jù)元素的表示及元素間關(guān)系的表示。數(shù)據(jù)元素的表示:在計算機(jī)中，可用二進(jìn)制位串表示一個數(shù)據(jù)元素，稱這個位串為元素（Element）或 結(jié)點（Node）。元素間關(guān)系的表示3 分類根據(jù)數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中的不同表示方法，數(shù)據(jù)的存儲結(jié)構(gòu)分類如下4類：1) 順序存儲結(jié)構(gòu)2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)3) 索引存儲4) 散列存儲4 描述本書采用在高級語言中的數(shù)據(jù)類型（Data type）來描述存儲結(jié)構(gòu)。如：對數(shù)據(jù)元素，可用基本類型（整型、字符型等）或結(jié)構(gòu)類型來描述對關(guān)系：可用一維數(shù)組描述順序存儲結(jié)構(gòu) 用“指針”描述鏈?zhǔn)酱鎯Y(jié)構(gòu)三、數(shù)據(jù)的

8、運算數(shù)據(jù)的運算是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。如檢索、插入、刪除等。數(shù)據(jù)的運算是在邏輯結(jié)構(gòu)上定義，在具體的存儲結(jié)構(gòu)上實現(xiàn)。5數(shù)據(jù)類型和抽象數(shù)據(jù)類型的概念。數(shù)據(jù)類型（Data Type）:是一個值的集合和定義在該值集上的一組操作的總稱。抽象數(shù)據(jù)類型（Abstruct Data Type，簡稱ADT）:是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。（D，S，P）其中，D表示數(shù)據(jù)對象，S表示關(guān)系集，P表示基本操作集。本書實際用ADT來描述數(shù)據(jù)的邏輯結(jié)構(gòu)及運算。第三節(jié) 抽象數(shù)據(jù)類型的表示與實現(xiàn)數(shù)據(jù)元素的表示 數(shù)據(jù)類型 typedef 定義新類型算法的描述 類C語言 函數(shù)幾點說明： 1 typede

9、f 2 數(shù)據(jù)元素的定義 3 算法的書寫采用類C語言、函數(shù)描述算法的輸入、輸出參數(shù)傳遞方式例：已知學(xué)生信息表，存儲在數(shù)組中。書寫算法實現(xiàn)根據(jù)學(xué)號查找學(xué)生所在專業(yè)。第四節(jié) 算法和算法分析1.4.1算法算法的概念:算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列。算法的五個特性：（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出1.4.2 算法設(shè)計的要求要設(shè)計一個好的算法通常要考慮以下的要求。正確性(Correctness ):算法應(yīng)滿足具體問題的需求?？勺x性性(Readability) :算法應(yīng)該好讀。以有利于閱讀者對程序的理解。健壯性(Robustness) :

10、算法應(yīng)具有容錯處理。效率與低存儲量要求: 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。1.4.3 算法效率的度量算法執(zhí)行時間分析方法的分類： 事后統(tǒng)計 事前分析度量方法 采用時間復(fù)雜度來估計算法的算法的執(zhí)行時間T(n)=O(f(n)即：如果存在兩個正常數(shù)c和n0，對于所有的nn0，有T(n) cf(n) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作漸近時間復(fù)雜度（Asymptotic Time Complexity），簡稱時間復(fù)雜度。時間復(fù)雜度的求法： 基本操作（原操作） 語句的頻度：語句執(zhí)行的次數(shù) 定理：若A(n)=amnm+am-1nm-1+a1n+a0是一個m次多項式，則A(n)=O(nm) 方法：確定基本操作，求各語句的頻度之和，根據(jù)定理求出最后結(jié)果。示例:常用的時間復(fù)雜度關(guān)系：O(1)O(logn)O(n)O(nlogn)O(n2)O(