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

學(xué)習(xí)提要 掌握本課程所涉及到的基本名詞、術(shù)語和概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系及性質(zhì)。 了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。 理解算法設(shè)計的五個要素和基本要求；掌握算法效率的度量方法，著重學(xué)習(xí)算法的時間復(fù)雜度分析。第1頁/共51頁教學(xué)重點數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項；邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別；數(shù)據(jù)結(jié)構(gòu)及其三個組成部分；抽象數(shù)據(jù)類型和數(shù)據(jù)抽象；評價算法優(yōu)劣的標準及方法。第2頁/共51頁1.1什么是數(shù)據(jù)結(jié)構(gòu)一、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？1、電子計算機的主要用途：早期： 主要用于數(shù)值計算。后來： 處理逐漸擴大到非數(shù)值計算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）。第3頁/共51頁用計算機解決問題的過程建立模型構(gòu)造求解算法選擇存儲結(jié)構(gòu)編寫程序測試描述問題的共性描述問題的求解方法將問題涉及的數(shù)據(jù)存儲到計算機中分析問題的過程數(shù)據(jù)結(jié)構(gòu)的作用進行更為復(fù)雜的算法設(shè)計選擇合理的存儲結(jié)構(gòu)提高編程技術(shù)第4頁/共51頁引引 例例書目自動檢索系統(tǒng)的數(shù)學(xué)模型書目自動檢索系統(tǒng)的數(shù)學(xué)模型登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠祥L01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L002,S001,003,索引表線性表第5頁/共51頁人機對奕問題的數(shù)學(xué)模型人機對奕問題的數(shù)學(xué)模型樹樹.第6頁/共51頁CEDABABACADBABCBDDADBDCEAEBECED圖十字路口的交通燈管理問題的數(shù)學(xué)模型第7頁/共51頁求解非數(shù)值計算的問題： 主要考慮的是設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。 即：首先要考慮對相關(guān)的各種信息如何表示、組織和存儲？ 因此，簡單說來，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學(xué)科。第8頁/共51頁問題：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？答：計算機內(nèi)的數(shù)值運算依靠數(shù)學(xué)方程，而非數(shù)值運算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。 同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異。 程序設(shè)計的實質(zhì)是對實際問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法。而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。 算法+數(shù)據(jù)結(jié)構(gòu)=程序 提高復(fù)雜程序設(shè)計的能力 培養(yǎng)算法設(shè)計能力 為后繼課程（如操作系統(tǒng)、編譯原理等）打基礎(chǔ)。第9頁/共51頁數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展 形成階段 60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。 1968年，美唐歐克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，計算機程序設(shè)計技巧第一卷基本算法 ，“數(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年代后期，80年代初，我國高校陸續(xù)開設(shè)該課程。第10頁/共51頁數(shù)據(jù)結(jié)構(gòu)課程所處的地位：介于數(shù)學(xué)、計算介于數(shù)學(xué)、計算機硬件和計算機機硬件和計算機軟件三者之間的軟件三者之間的一門核心課程。一門核心課程。第11頁/共51頁基本概念和術(shù)語1.2.1基本概念1.數(shù)據(jù)（data）： 數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合, 是計算機程序加工的”原料”。 分類： 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù)第12頁/共51頁2、數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項(Data Item)(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)不可分割的最小標識單位。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。學(xué)號學(xué)號 姓名姓名成成績績001LiLy89002Yang98003Zhao78第13頁/共51頁3、數(shù)據(jù)對象（data object）l數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。u整數(shù)數(shù)據(jù)對象 N = 0, 1, 2, u字母字符數(shù)據(jù)對象 C=A，B，Zu學(xué)生成績數(shù)據(jù)對象Cj=（101，jane，80）， （ 102，jack，90 ）， （ 103，jerry，75 ）學(xué)號學(xué)號姓名姓名成績成績001LiLy89002Yang98003Zhao78第14頁/共51頁4、數(shù)據(jù)結(jié)構(gòu)(data structure) 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 在任何問題中，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)(Structure)。 數(shù)據(jù)結(jié)構(gòu)是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間的關(guān)系的總和。第15頁/共51頁 按數(shù)據(jù)元素之間關(guān)系的不同特性，通常有4類基本結(jié)構(gòu)（1）集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個集合”外，別無其它關(guān)系。（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)系。bindevetclibuseretcuserdevlibbindevetcuser14131211234567891031587101199874566231311152436第16頁/共51頁數(shù)據(jù)結(jié)構(gòu)的形式定義用一個二元組表示，記為： Data_Structure = （D, S） 其中，D 是數(shù)據(jù)元素的有限集（即一個數(shù)據(jù) 對象），S 是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。在計算機科學(xué)中，對復(fù)數(shù)的定義：復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)Complex=(C,R)其中：C是包含兩個實數(shù)的集合 C1, C2 ,R=P,P是定義在C上的一種關(guān)系 。第17頁/共51頁例、用數(shù)據(jù)結(jié)構(gòu)如何描述2行3列矩陣： 它是一個含6個數(shù)據(jù)元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行關(guān)系”和“列關(guān)系”兩個次序關(guān)系，其中 行關(guān)系為 ， 列關(guān)系為 ，。 意為 x 和 y 之間存在 x領(lǐng)先于y 的次序關(guān)系。654321aaaaaa思考： 如何描述一個一行六列的矩陣？第18頁/共51頁例1-5 假設(shè)我們需要編制一個事務(wù)管理的程序，管理學(xué)校科學(xué)研究課題小組的各項事務(wù)，則首先要為程序的操作對象課題小組設(shè)計一個數(shù)據(jù)結(jié)構(gòu)。假設(shè)每個小組由一位教師、一至三名研究生及一至六名本科生組成，小組成員之間的關(guān)系是：教師指導(dǎo)研究生，而由每位研究生指導(dǎo)一至兩名本科生。 則可以如下定義數(shù)據(jù)結(jié)構(gòu)： Group = (P，R) 其中: P = T，G1，Gn，S11Snm 1=n=3，1=m=2， R = R1, R2 R1 = | 1=i=n, 1=n=3 R2 = | 1=i=n, 1=j=m, 1=n=3, 1=m=2 第19頁/共51頁5、數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，可以看作是從具體問題抽象出來的數(shù)據(jù)模型，與數(shù)據(jù)的存儲無關(guān)，也與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置無關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)分類： 線性結(jié)構(gòu) 線性表、棧、隊列 、串 非線性結(jié)構(gòu) 樹 、圖（或網(wǎng)絡(luò)）第20頁/共51頁6、數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(或稱映象）稱為數(shù)據(jù)的存儲結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。（1）數(shù)據(jù)元素的表示：位、字長、元素、結(jié)點、數(shù)據(jù)域（2）關(guān)系的表示兩種基本的存儲方法：順序映像（順序存儲結(jié)構(gòu)）非順序映像（鏈式存儲結(jié)構(gòu)） 第21頁/共51頁u順序存儲結(jié)構(gòu): 借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計算機內(nèi)仍然相鄰。u鏈式存儲結(jié)構(gòu)： 在每一個數(shù)據(jù)元素中增加一個存放地址的指針，借助該指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 所有元素存放在可以不連續(xù)的存貯單元中，但元素之間的關(guān)系可以通過地址（指針）確定，邏輯上相鄰的元素存放到計算機內(nèi)存后不一定是相鄰的。第22頁/共51頁存儲結(jié)構(gòu)的描述 存儲結(jié)構(gòu)的描述方法隨編程環(huán)境的不同而不同，通?？捎酶呒壘幊陶Z言中提供的數(shù)據(jù)類型描述之。 例如，用一維數(shù)組類型描述順序存儲結(jié)構(gòu)，用指針描述鏈式存儲結(jié)構(gòu)。 例如，定義日期為：typedef struct int y; / 年號 Yearint m; / 月號 Monthint d; / 日號 Day DateType; / 日期類型同樣，此時對數(shù)據(jù)元素也要借用高級編程語言中的數(shù)據(jù)類型描述之。第23頁/共51頁7、數(shù)據(jù)類型（data type） 數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。 數(shù)據(jù)類型可分兩類：原子類型和結(jié)構(gòu)類型。 例如：在C語言中 原子類型：整型、實型、字符型等 結(jié)構(gòu)類型：數(shù)組、結(jié)構(gòu)體、聯(lián)合等第24頁/共51頁9、抽象抽象數(shù)據(jù)類型 (Abstract Data Type簡稱ADT) l由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型l指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。 l例如：計算機擁有的整數(shù)類型。l它與數(shù)據(jù)類型實質(zhì)上是一個概念，但其特征是使用與實現(xiàn)分離，實行封裝和信息隱蔽（獨立于計算機）。第25頁/共51頁抽象數(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)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼（不真正執(zhí)行的符號）描述?；静僮鞯亩x格式為： 基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述第26頁/共51頁 基本操作有兩種參數(shù)： 賦值參數(shù)只為操作提供輸入值； 引用參數(shù)以&打頭， 除了可以提供輸入值外，還將返回操作結(jié)果。 “初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。若初始條件為空，則省略之。 “操作結(jié)果” 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。第27頁/共51頁舉例抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADT Complex 數(shù)據(jù)對象：De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：R1變量1變量n; 輸出語句 printf( 格式串，表達式1， ，表達式n);或 cout表達式1表達式n;(9)注釋 行注釋 /文字序列(10)基本函數(shù)有 求最大值 max (表達式l，表達式n) 求最小值 min (表達式1，表達式n) 求絕對值 abs (表達式) 求不足整數(shù)值 floor(表達式)向下取整 求進位整數(shù)值 ceil(表達式)向上取整 判定文件結(jié)束 eof(文件變量)或eof 判定行結(jié)束 eoln(文件變量)或eoln 第35頁/共51頁抽象數(shù)據(jù)類型實現(xiàn)示例例如利用C語言實現(xiàn)的“復(fù)數(shù)”類型如下描述：/ 存儲結(jié)構(gòu)的定義typedef struct float realpart;float imagpart; complex;/ 基本操作的函數(shù)原型說明void Assign( complex &Z, float realval, float imagval );/ 構(gòu)造復(fù)數(shù) Z，其實部和虛部分別被賦以參數(shù) realval 和 imagval 的值void DestroyComplex( complex &Z) / 銷毀復(fù)數(shù) Zfloat GetReal( cpmplex Z ); / 返回復(fù)數(shù) Z 的實部值float Getimag( cpmplex Z ); / 返回復(fù)數(shù) Z 的虛部值void add( complex z1, complex z2, complex &sum );/ 以 sum 返回兩個復(fù)數(shù) z1，z2 的和基本操作的實現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個復(fù)數(shù) z1，z2 的和sum.realpart = z1.realpart + z2.realpart;sum.imagpart = z1.imagpart + z2.imagpart; 第36頁/共51頁1.4算法和算法分析 算法的定義：是對特定問題求解步驟的一種描述,是一個有窮的指令集，這些指令表示一個或多個操作。 算法的特性(要素)： 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束,且每一步都在有窮時間內(nèi)完成 確定性 每步定義都是確切、無歧義的 可行性 算法中描述的操作應(yīng)能通過執(zhí)行有限次已經(jīng)實現(xiàn)的基本運算而實現(xiàn) 輸入 有0個或多個輸入 輸出 有一個或多個輸出(處理結(jié)果)。第37頁/共51頁算法設(shè)計的要求 正確性：不含有語法錯誤；對于各種合法的輸入數(shù)據(jù)能夠得到滿足規(guī)格說明要求的結(jié)果。 可讀性：要求程序有較好的人機交互性,有助于人們對算法的理解。 健壯性：對輸入的非法數(shù)據(jù)能作出適當?shù)捻憫?yīng)或處理。 效率與低存儲需求：主要指算法的執(zhí)行時間和所需的最大存儲空間，這兩方面主要和問題的規(guī)模有關(guān)。第38頁/共51頁算法效率的度量 算法的后期測試 在算法中的某些部位插裝時間函數(shù) time ( )測定算法完成 某一功能所花費時間。 算法的事前估計： 空間復(fù)雜度 時間復(fù)雜度第39頁/共51頁程序運行所需要的時間取決于下列因素： 依據(jù)的算法選用何種策略。 問題的規(guī)模。 書寫程序的語言。 編譯程序所生成目標代碼的質(zhì)量。 硬件的速度。 可以認為一個特定算法“運行工作量”大小，只依賴于問題的規(guī)模（通常用整數(shù)n表示），或者說，它是問題規(guī)模的函數(shù)。第40頁/共51頁 一個算法所耗費的時間，應(yīng)該是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間又是該語句的執(zhí)行次數(shù)（頻度）與該語句執(zhí)行一次所需時間的乘積。 語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。 我們假定，每條語句一次執(zhí)行的時間都是相同的，為單位時間。這樣我們對時間的分析就可以獨立于軟硬件系統(tǒng)。 時間復(fù)雜度是問題規(guī)模的函數(shù)T( n )。第41頁/共51頁語句頻度舉例 （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第42頁/共51頁時間復(fù)雜度 設(shè)解決一個問題的規(guī)模為n ，基本操作被重復(fù)執(zhí)行的次數(shù)是n的一個函數(shù) f（n），假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，則可記作： T (n) = O(f(n) 其中T（n）叫算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度， O是Order（數(shù)量級）的首字母，意思是T（n）與f（n）只差一個常數(shù)倍。 比較同一問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度?；静僮鞯脑僮?數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同。第43頁/共51頁漸進時間復(fù)雜度的計算 加法規(guī)則 針對并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) 乘法規(guī)則針對嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m) 注：c log2n n nlog2n n2 n3 2n 3n n!第44頁/共51頁x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)第45頁/共51頁例對 n 個整數(shù)的序列進行選擇排序。其中序列的“長度” n 為問題的規(guī)模。void selectSort ( int a , int n ) /對n個整數(shù)a0,a1,an-1按遞增順序排序 for ( int i = 0; i n-1; i+ ) int k = i; /從ai查到an-1, 找最小整數(shù), 在ak for ( int j = i+1; j n; j+ ) if ( aj = 0 & Ai != k ) i-; return i;算法的語句 i- 的頻度不僅與 n 有關(guān)，還與 A i 中各元素的取值，以及 k 的取值有關(guān)。第47頁/共51頁算法的空間復(fù)雜度 空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的度量，記作： S(n) = O(g(n) 表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。 算法的存儲量包括： 輸入數(shù)據(jù)所占空間; 程序本身所占空間； 輔助變量所占空間。 第48頁/共51頁說明 算法的所有性能之間都存在著或多或少的相互影響，因此，當設(shè)計一個算法，特別是大型算法時，要綜合考慮算法的各項性能、算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語言的特性及算法運行的機器系統(tǒng)環(huán)境等各方面因素，才能設(shè)計出比較好的算法。 第49頁/共51頁本章小結(jié) 與數(shù)據(jù)結(jié)構(gòu)相關(guān)的幾個名詞概念 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)） 在數(shù)據(jù)結(jié)構(gòu)上的操作 抽象數(shù)據(jù)類型 算法分析：時間復(fù)雜度、空間復(fù)雜度第50頁/共51頁感謝您的觀看。第51頁/共51頁