數(shù)據(jù)結(jié)構(gòu)(C語言版)ppt課件

1、1,總學(xué)時：32 講課學(xué)時：24 教材：數(shù)據(jù)結(jié)構(gòu)C語言版嚴(yán)蔚敏、吳偉民 -清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏，清華大學(xué)出版社,參考書： 數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述），殷人昆等，清華大學(xué)出版社,輔導(dǎo) 每周五下午：信息科技大廈1901,課程安排,2,編程基礎(chǔ) 考研課程 計算機等級考試課程 程序員考試課程,課程重要性,3,第一章 緒論,1.1 數(shù)據(jù)結(jié)構(gòu)的概念 1.2 基本概念和術(shù)語 1.3 抽象數(shù)據(jù)類型 1.4 算法和算法分析,4,為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？ 什么是程序、軟件？ N.沃思（Niklaus Wirth)教授提出,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,程序=算法+數(shù)據(jù)結(jié)構(gòu) 以上公式說明了如下兩個問

2、題： (1)數(shù)據(jù)上的算法決定如何構(gòu)造和組織數(shù)據(jù)(算法數(shù)據(jù)結(jié)構(gòu)) (2)算法的選擇依賴于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)(數(shù)據(jù)結(jié)構(gòu)算法)。 軟件=程序+文檔（軟件工程的觀點,5,電子計算機的主要用途： 早期： 主要用于數(shù)值計算。 后來： 處理逐漸擴大到非數(shù)值計算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù),1.1 數(shù)據(jù)結(jié)構(gòu)的概念,6,數(shù)值計算解決問題的一般步驟： 數(shù)學(xué)模型選擇計算機語言編出程序測試最終解答。 數(shù)值計算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？ 程序設(shè)計人員比較關(guān)注程序設(shè)計的技巧。 非數(shù)值計算問題： 數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,7,例 書目自動檢索系統(tǒng),書

3、目文件,8,例 井字棋,9,例 電話號碼查詢問題： （1）按順序存儲方式：須遍歷表 （2）按姓氏索引方式：索引 要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲方式。 電話號碼表的結(jié)構(gòu)和存儲方式?jīng)Q定了查找（算法）的效率,非數(shù)值計算問題,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,10,例 多叉路口交通燈管理問題,11,例 田徑賽的時間安排問題（無向圖的著色問題） ： 設(shè)有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）設(shè)計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,非數(shù)值計算問題,12,1)設(shè)用如下六個不同的代號代表不同的項目： 跳高 跳遠(yuǎn) 標(biāo)槍 鉛球 100米

4、200米 A B C D E F (2)用頂點代表比賽項目 不能同時進(jìn)行比賽的項目之間連上一條邊。 (3)某選手比賽的項目必定有邊相連(不能同時比賽,非數(shù)值計算問題： -田徑賽的時間安排問題解法,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,13,A,E,B,F,D,C,只需安排四個單位時間進(jìn)行比賽,14,在應(yīng)用程序中涉及到各種各樣的數(shù)據(jù)，如何在計算機中組織、存儲、傳遞數(shù)據(jù)，需要討論它們的歸類及它們之間的關(guān)系，從而建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，依此實現(xiàn)軟件功能。 綜上，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不是數(shù)學(xué)方程,而是樹、表和圖之類的數(shù)據(jù)結(jié)構(gòu)。 因此從廣義上講，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實世界實體的數(shù)學(xué)模型及其上的操作在計算機中的表示和

5、實現(xiàn),1.1 數(shù)據(jù)結(jié)構(gòu)的概念,15,求解非數(shù)值計算的問題： 主要考慮的是設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。 即：首先要考慮對相關(guān)的各種信息如何表示、組織和存儲？ 因此，可以認(rèn)為：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學(xué)科,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,16,數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展： 形成階段： 60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學(xué)計算機科學(xué)系的教學(xué)計劃。 發(fā)展階段： 數(shù)據(jù)結(jié)構(gòu)的概念不斷擴充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。 70年代后期，我國高

6、校陸續(xù)開設(shè)該課程,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,17,數(shù)據(jù)結(jié)構(gòu)課程 所處的地位,1.1 數(shù)據(jù)結(jié)構(gòu)的概念,18,數(shù)據(jù)(Data): 對信息的一種符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。 數(shù)值型數(shù)據(jù) 非數(shù)值型數(shù)據(jù),1.2 基本概念和術(shù)語,19,數(shù)據(jù)元素(Data Element): 數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小標(biāo)識單位,1.2 基本概念和術(shù)語,20,數(shù)據(jù)對象(Data Object)： 性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。 整數(shù)數(shù)據(jù)對象 N = 0, 1, 2

7、, 字母字符數(shù)據(jù)對象 C= A, B, C, F,1.2 基本概念和術(shù)語,21,定義1- 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 定義2- 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計算機語言并按一定的存儲表示 方式把它們存儲在計算機的存儲器中，并在其上定義了一個運算的集合,什么是數(shù)據(jù)結(jié)構(gòu),22,數(shù)據(jù)結(jié)構(gòu)的三個方面的含義： 邏輯結(jié)構(gòu)- 數(shù)據(jù)元素間抽象化的相互關(guān)系（簡稱為數(shù)據(jù)結(jié)構(gòu)）。 與數(shù)據(jù)的存儲無關(guān)，獨立于計算機，它是從具體問題抽象出來的數(shù)學(xué)模型。 存儲結(jié)構(gòu)（物理結(jié)構(gòu)）- 數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式。 是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它依賴于計

8、算機語言。 運算（算法,1.2 基本概念和術(shù)語,23,1.2 基本概念和術(shù)語,24,數(shù)據(jù)結(jié)構(gòu)3方面含義之邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu)-劃分方法一 （1）線性結(jié)構(gòu)- 有且僅有一個開始和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個后繼。 例如：線性表、棧、隊列、串 （2）非線性結(jié)構(gòu)- 一個結(jié)點可能有多個直接前趨和直接后繼。 例如：樹、圖、多維數(shù)組、廣義表等,1.2 基本概念和術(shù)語,25,邏輯結(jié)構(gòu)-劃分方法二 一、集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。 二、線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系，如線性表、棧、隊列。 三、樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系，如

9、樹。 四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系，如圖,1.2 基本概念和術(shù)語,26,四個基本結(jié)構(gòu) 集合 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 網(wǎng)狀結(jié)構(gòu),27,user,線性結(jié)構(gòu),樹形結(jié)構(gòu) 樹 二叉樹 二叉排序樹,28,堆結(jié)構(gòu),12,3,5,4,8,7,11,10,2,9,1,6,圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu),29,數(shù)據(jù)結(jié)構(gòu)3方面含義之存儲結(jié)構(gòu) 存儲結(jié)構(gòu)兩方面的內(nèi)容： （1）數(shù)據(jù)元素自身值的表示（數(shù)據(jù)域） （2）該結(jié)點與其它結(jié)點關(guān)系的域（鏈域） 四種基本的存儲方法： （1）順序存儲方法（結(jié)構(gòu)） （2）鏈接存儲方法（鏈?zhǔn)酱鎯Y(jié)構(gòu)） （3）索引存儲方法 （4）散列存儲方法 同一種邏輯結(jié)構(gòu)可采用不同的存儲方法（

10、以上四種之一或組合），這主要考慮的是運算方便及算法的時空要求,1.2 基本概念和術(shù)語,30,31,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?h,32,邏輯結(jié)構(gòu)存儲結(jié)構(gòu)小結(jié)： （1）數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算（算法）構(gòu)成了數(shù)據(jù)結(jié)構(gòu)三個方面的含義。 （2）程序設(shè)計的實質(zhì)是對實際問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法。而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu),1.2 基本概念和術(shù)語,33,1.3 抽象數(shù)據(jù)類型(ADT,數(shù)據(jù)類型：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。 例1、 在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實

11、型、和復(fù)數(shù)型 例2、在C語言中 數(shù)據(jù)類型：基本類型和構(gòu)造類型 基本類型：整型、浮點型、字符型 構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義,34,1.3 抽象數(shù)據(jù)類型(ADT,抽象數(shù)據(jù)類型 是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作 數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作 = 抽象數(shù)據(jù)類型 例如：矩陣 +（求轉(zhuǎn)置、加、乘、求逆、求特征值） 構(gòu)成一個矩陣的抽象數(shù)據(jù)類型,35,抽象數(shù)據(jù)類型的描述 抽象數(shù)據(jù)類型可用（D，S，P）三元組表示 其中，D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本

12、操作的定義 ADT 抽象數(shù)據(jù)類型名,1.3 抽象數(shù)據(jù)類型(ADT,36,其中,數(shù)據(jù)對象、數(shù)據(jù)關(guān)系用偽碼描述；基本操作定義格式為 基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述 基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以 for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x+; 由于內(nèi)循環(huán)的執(zhí)行次數(shù)雖與規(guī)模n無直接關(guān)系，但與外循環(huán)的變量取值有關(guān)。因此從內(nèi)層向外層循環(huán)分析執(zhí)行次數(shù),1.4 算法和算法分析,46,即: T(n)=n(n+1)(2n+1)/6+n(n+1)/2/2 所以： T(n)=O(n3/6+

13、低次項) 取T(n)的數(shù)量級階，得最后結(jié)果為： T(n)=O(n3,1.4 算法和算法分析,47,例1.5 分析以下程序段的時間復(fù)雜度 for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+) x+;,* 1 *,* 2 *,1.4 算法和算法分析,48,分析：語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。一個算法中所有語句的頻度之和構(gòu)成了該算法的運行時間。 語句1的頻度是：n-1 語句2的頻度是,則該程序段的時間復(fù)雜度： T(n),1.4 算法和算法分析,49,例1.6 分析以下程序段的時間復(fù)雜度 i=1; while (i=n) i=i*2 語句1的頻度是：1 設(shè)語句2的頻度是f(n)，則有： 即 ，取最大值 則該程序段的時間復(fù)雜度為,* 1 *,* 2 *,1.4 算法和算法分析,