緒論數(shù)據(jù)結(jié)構(gòu)第2版李冬梅.ppt

1、北京林業(yè)大學(xué)信息學(xué)院,李冬梅,第1章 緒論,Office: 西配樓304（軟件教研室） Email:,編程基礎(chǔ) 計算機及相關(guān)專業(yè)考研考博課程 計算機等級考試課程 程序員考試課程,為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu),北京林業(yè)大學(xué)信息學(xué)院,北京林業(yè)大學(xué)信息學(xué)院,課程學(xué)習(xí)指導(dǎo),1.提前預(yù)習(xí)、認(rèn)真聽課、按時完成書面及上機作業(yè) 2.注意先修課程的知識準(zhǔn)備 離散數(shù)學(xué)、C語言 3.注意循序漸進(jìn)： 基本概念、基本思想、基本步驟、算法設(shè)計 4.注意培養(yǎng)算法設(shè)計的能力 理解所講算法、對此多做思考：若問題要求不同，應(yīng)如何選擇數(shù)據(jù)結(jié)構(gòu)，設(shè)計有效的算法,課程特點：內(nèi)容抽象、概念性強、內(nèi)容靈活、不易掌握,平時成績 : 30% 作業(yè)、小

2、測驗、實驗 課堂紀(jì)律 無故遲到： 無故曠課： 上機：玩游戲、上網(wǎng)聊天 期末成績 : 70%(閉卷筆試),考核方式,北京林業(yè)大學(xué)信息學(xué)院,教材和參考書 教材： 數(shù)據(jù)結(jié)構(gòu)(第2版)，嚴(yán)蔚敏，李冬梅等，人民郵電出版社 參考書： 數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏，清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅcC+描述，殷人昆等，清華大學(xué)出版社 算法藝術(shù)與信息學(xué)競賽，劉汝佳，黃亮清華大學(xué)出版社,北京林業(yè)大學(xué)信息學(xué)院,第1章緒論,1. 了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 2.掌握數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念 3. 掌握算法的時間、空間復(fù)雜度及其分析的簡易方法,教學(xué)目標(biāo),北京林業(yè)大學(xué)信息學(xué)院,1.1 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容 1.2 基本概念和術(shù)

3、語 1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn) 1.4 算法與算法分析,教學(xué)內(nèi)容,北京林業(yè)大學(xué)信息學(xué)院,N.沃思（Niklaus Wirth)教授提出： 程序=算法+數(shù)據(jù)結(jié)構(gòu) 電子計算機的主要用途： 早期： 主要用于數(shù)值計算 后來： 處理逐漸擴大到非數(shù)值計算領(lǐng)域，能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù),1.1 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容,北京林業(yè)大學(xué)信息學(xué)院,書目自動檢索系統(tǒng),書目文件,北京林業(yè)大學(xué)信息學(xué)院,人機對奕問題,/ (root),bin,lib,user,etc,math,ds,sw,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖,北京林業(yè)大學(xué)信

4、息學(xué)院,04:03,多叉路口交通燈管理問題,頂點：一條通路 連線：不能同時通行 染色：有連線的兩個頂點不能具有相同顏色,北京林業(yè)大學(xué)信息學(xué)院,求解非數(shù)值計算的問題： 設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法 即：首先要考慮對相關(guān)的各種信息如何表示、組織和存儲？ 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容為： 研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作。,北京林業(yè)大學(xué)信息學(xué)院,數(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)的概念不斷擴充，包

5、括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。 70年代后期，我國高校陸續(xù)開設(shè)該課程。,北京林業(yè)大學(xué)信息學(xué)院,數(shù)據(jù)結(jié)構(gòu)所處的地位：,介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程,北京林業(yè)大學(xué)信息學(xué)院,北京林業(yè)大學(xué)信息學(xué)院,04:03,數(shù)據(jù)結(jié)構(gòu)在計算機學(xué)科中的地位,課程目的,能夠分析研究計算機加工的對象的特性，獲得其邏輯結(jié)構(gòu)，根據(jù)需求，選擇合適存貯結(jié)構(gòu)及其相應(yīng)的算法； 學(xué)習(xí)一些常用的算法； 復(fù)雜程序設(shè)計的訓(xùn)練過程，要求編寫的程序結(jié)構(gòu)清楚和正確易讀； 初步掌握算法的時間分析和空間分析技術(shù),北京林業(yè)大學(xué)信息學(xué)院,1、數(shù)據(jù)（data)所有能輸入到計算機中去的描述客觀事物的符號 數(shù)值性數(shù)

6、據(jù) 非數(shù)值性數(shù)據(jù)（多媒體信息處理） 2、數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位，也稱結(jié)點（node）或記錄（record） 3、數(shù)據(jù)項（data item）有獨立含義的數(shù)據(jù)最小單位，也稱域(field),三者之間的關(guān)系：數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項,例：學(xué)生表 個人記錄 學(xué)號、姓名,1.2 基本概念和術(shù)語,北京林業(yè)大學(xué)信息學(xué)院,整數(shù)數(shù)據(jù)對象 N = 0, 1, 2, 學(xué)生數(shù)據(jù)對象 學(xué)生記錄的集合,4、數(shù)據(jù)對象(Data Object)：相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集,北京林業(yè)大學(xué)信息學(xué)院,5、數(shù)據(jù)結(jié)構(gòu)（Data Structure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集

7、合。,數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。,北京林業(yè)大學(xué)信息學(xué)院,數(shù)據(jù)結(jié)構(gòu)的兩個層次： 邏輯結(jié)構(gòu)- 數(shù)據(jù)元素間抽象化的相互關(guān)系，與數(shù)據(jù)的存儲無關(guān)，獨立于計算機，它是從具體問題抽象出來的數(shù)學(xué)模型。 存儲結(jié)構(gòu)（物理結(jié)構(gòu)）- 數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式。,北京林業(yè)大學(xué)信息學(xué)院,劃分方法一 （1）線性結(jié)構(gòu)- 有且僅有一個開始和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個后繼。 例如：線性表、棧、隊列、串 （2）非線性結(jié)構(gòu)- 一個結(jié)點可能有多個直接前趨和直接后繼。 例如：樹、圖,邏輯結(jié)構(gòu),北京林業(yè)大學(xué)信息學(xué)院,線性結(jié)構(gòu)一個對一個，如線性表

8、、棧、隊列,樹形結(jié)構(gòu)一個對多個，如樹,集合數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系,圖形結(jié)構(gòu)多個對多個，如圖,邏輯結(jié)構(gòu),劃分方法二,北京林業(yè)大學(xué)信息學(xué)院,存儲結(jié)構(gòu)分為： 順序存儲結(jié)構(gòu)借助元素在存儲器中的相對位置來表示 數(shù)據(jù)元素間的邏輯關(guān)系 鏈?zhǔn)酱鎯Y(jié)構(gòu)借助指示元素存儲地址的指針表示數(shù)據(jù) 元素間的邏輯關(guān)系,存儲結(jié)構(gòu),北京林業(yè)大學(xué)信息學(xué)院,北京林業(yè)大學(xué)信息學(xué)院,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?h,北京林業(yè)大學(xué)信息學(xué)院,邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都相同, 但運算不同, 則數(shù)據(jù)結(jié)構(gòu)不同. 例如, 棧與隊列 對于一種數(shù)據(jù)結(jié)構(gòu), 常見的運算 插入 刪除 修

9、改 查找 排序,數(shù)據(jù)的運算,北京林業(yè)大學(xué)信息學(xué)院,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的運算：插入、刪除、修改、查找、排序,線性結(jié)構(gòu),非線性結(jié)構(gòu),順序存儲,鏈?zhǔn)酱鎯?線性表,棧、隊列,串、數(shù)組,樹形結(jié)構(gòu),圖形結(jié)構(gòu),邏輯結(jié)構(gòu) 唯一 存儲結(jié)構(gòu) 不唯一 運算的實現(xiàn) 依賴于 存儲結(jié)構(gòu),北京林業(yè)大學(xué)信息學(xué)院,定義：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類,數(shù)據(jù)類型,FORTRAN語言：整型、實型、和復(fù)數(shù)型 C語言： 基本數(shù)據(jù)類型： char int float double void 構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)體、共用體、文件,數(shù)據(jù)類型是一組性質(zhì)相同的值的集合, 以及定義于這個集合上的一組運算的總稱,北

10、京林業(yè)大學(xué)信息學(xué)院,抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types),更高層次的數(shù)據(jù)抽象 由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型 由基本的數(shù)據(jù)類型組成, 并包括一組相關(guān)的操作,抽象數(shù)據(jù)類型,北京林業(yè)大學(xué)信息學(xué)院,抽象數(shù)據(jù)類型可以用以下的三元組來表示： ADT = （D，S，P） 數(shù)據(jù)對象 D上的關(guān)系集 D上的操作集,ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基本操作 ： ADT抽象數(shù)據(jù)類型名,ADT常用定義格式,北京林業(yè)大學(xué)信息學(xué)院,抽象數(shù)據(jù)類型,查找插入 刪除 修改,線性表,接口或用戶界面,數(shù)據(jù)類型的物理實現(xiàn)封裝,信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離,北京林業(yè)大學(xué)信息

11、學(xué)院,1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn),抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。,它有些類似C語言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的操作 教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具,但上機時要用具體語言實現(xiàn)，如C或C+等,北京林業(yè)大學(xué)信息學(xué)院,(1) 預(yù)定義常量及類型 /函數(shù)結(jié)果狀態(tài)代碼 #define OK 1 #define ERROR 0 #define OVERFLOW -2 / Status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。 typedef int Status;,北京林業(yè)大學(xué)信息學(xué)院,(2)數(shù)據(jù)元素被約定為ElemT

12、ype 類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。,(3)算法描述為以下的函數(shù)形式： 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） 語句序列； ,北京林業(yè)大學(xué)信息學(xué)院,（4）內(nèi)存的動態(tài)分配與釋放 使用new和delete動態(tài)分配和釋放內(nèi)存空間 分配空間指針變量=new數(shù)據(jù)類型; 釋放空間delete指針變量;,（5）賦值語句 （6）選擇語句 （7）循環(huán)語句,北京林業(yè)大學(xué)信息學(xué)院,（8）使用的結(jié)束語句形式有： 函數(shù)結(jié)束語句 return 循環(huán)結(jié)束語句 break; 異常結(jié)束語句 exit（異常代碼）；,北京林業(yè)大學(xué)信息學(xué)院,（9）輸入輸出語句形式有： 輸入語句 cin (scanf( ) 輸出語句 co

13、ut (printf( ) （10）擴展函數(shù)有： 求最大值 max 求最小值 min,北京林業(yè)大學(xué)信息學(xué)院,算法定義：一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列 算法的描述： 自然語言 流程圖 程序設(shè)計語言 偽碼,1.4 算法和算法分析,北京林業(yè)大學(xué)信息學(xué)院,算法的特性： 輸入 有0個或多個輸入 輸出 有一個或多個輸出(處理結(jié)果) 確定性 每步定義都是確切、無歧義的 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束 有效性 每一條運算應(yīng)足夠基本,北京林業(yè)大學(xué)信息學(xué)院,算法的評價,正確性 可讀性 健壯性 高效性（時間代價和空間代價）,北京林業(yè)大學(xué)信息學(xué)院,算法效率：用依據(jù)該算法編制的程序在計

14、算機上執(zhí)行所消耗的時間來度量,算法的效率的度量,事后統(tǒng)計 事前分析估計,北京林業(yè)大學(xué)信息學(xué)院,1.事后統(tǒng)計：利用計算機內(nèi)的計時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分,缺點： 必須先運行依據(jù)算法編制的程序 所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣,北京林業(yè)大學(xué)信息學(xué)院,2.事前分析估計： 一個高級語言程序在計算機上運行所消耗的時間取決于： 依據(jù)的算法選用何種策略 問題的規(guī)模 程序語言 編譯程序產(chǎn)生機器代碼質(zhì)量 機器執(zhí)行指令速度,同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，使用絕對時間單位衡量算法效率不合適,北京林業(yè)大學(xué)信息學(xué)院,算

15、法中基本語句重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間量度記作： T(n)=O(f(n),時間復(fù)雜度的漸進(jìn)表示法,數(shù)學(xué)符號“O”的定義為： 若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n)表示存在正的常數(shù)C和n0，使得當(dāng)nn0時都滿足0T(n)Cf(n)。,表示隨著n的增大，算法執(zhí)行的時間的增長率和f(n)的增長率相同，稱漸近時間復(fù)雜度。,n越大算法的執(zhí)行時間越長 排序：n為記錄數(shù) 矩陣：n為矩陣的階數(shù) 多項式：n為多項式的項數(shù) 集合：n為元素個數(shù) 樹：n為樹的結(jié)點個數(shù) 圖：n為圖的頂點數(shù)或邊數(shù),算法中重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的語句 對算法運

16、行時間的貢獻(xiàn)最大,北京林業(yè)大學(xué)信息學(xué)院,n * n階矩陣加法： for( i = 0; i n; i+) for( j = 0; j n; j+) cij = aij + bij; 語句的頻度（Frequency Count ): 重復(fù)執(zhí)行的次數(shù)：n*n; T( n ) = O ( n 2) 即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級,北京林業(yè)大學(xué)信息學(xué)院,找出語句頻度最大的那條語句作為基本語句 計算基本語句的頻度得到問題規(guī)模n的某個函數(shù)f(n) 取其數(shù)量級用符號“O”表示,分析算法時間復(fù)雜度的基本方法,f(n)=n2,T(n) = O(n2),北京林業(yè)大學(xué)信息學(xué)院,void exa

17、m ( float x , int m, int n ) float sum ; for ( int i = 0; i m; i+ ) sumi = 0.0; for ( int j = 0; j n; j+ ) sumi += xij; for ( i = 0; i m; i+ ) cout i “ : ” sum i endl; ,時間復(fù)雜度是由嵌套最深層語句的頻度決定的,f(n)=m*n,T(n) = O(m*n),北京林業(yè)大學(xué)信息學(xué)院,例1：NN矩陣相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik

18、*bkj; ,算法中的基本操作語句為cij=cij+aik*bkj;,北京林業(yè)大學(xué)信息學(xué)院,例2： for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+) x=x+1;,語句頻度 =,定理1.1 若f(n)=amnm+am-1nm-1+a1n+a0是m次多項式，則T(n)=O(nm)。,忽略所有低次冪項和最高次冪系數(shù)，體現(xiàn)出增長率的含義,北京林業(yè)大學(xué)信息學(xué)院,例3：分析以下程序段的時間復(fù)雜度,i=1; while(i=n) i=i*2; ,即f(n)log2n，取最大值f(n)=log2n,所以該程序段的時間復(fù)雜度T(n) =O( log2n),北京林業(yè)大學(xué)信息學(xué)院,例4：順序查找，在數(shù)組ai中查