緒論數(shù)據(jù)結構第2版李冬梅.ppt

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

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

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

4、息學院,04:03,多叉路口交通燈管理問題,頂點：一條通路 連線：不能同時通行 染色：有連線的兩個頂點不能具有相同顏色,北京林業(yè)大學信息學院,求解非數(shù)值計算的問題： 設計出合適的數(shù)據(jù)結構及相應的算法 即：首先要考慮對相關的各種信息如何表示、組織和存儲？ 數(shù)據(jù)結構的研究內容為： 研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作。,北京林業(yè)大學信息學院,數(shù)據(jù)結構課程的形成和發(fā)展： 形成階段： 60年代初期，“數(shù)據(jù)結構”有關的內容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結構”被列入美國一些大學計算機科學系的教學計劃。 發(fā)展階段： 數(shù)據(jù)結構的概念不斷擴充，包

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

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

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

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

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

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

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

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

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

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

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

16、行時間的貢獻最大,北京林業(yè)大學信息學院,n * n階矩陣加法： for( i = 0; i n; i+) for( j = 0; j n; j+) cij = aij + bij; 語句的頻度（Frequency Count ): 重復執(zhí)行的次數(shù)：n*n; T( n ) = O ( n 2) 即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級,北京林業(yè)大學信息學院,找出語句頻度最大的那條語句作為基本語句 計算基本語句的頻度得到問題規(guī)模n的某個函數(shù)f(n) 取其數(shù)量級用符號“O”表示,分析算法時間復雜度的基本方法,f(n)=n2,T(n) = O(n2),北京林業(yè)大學信息學院,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(n)=m*n,T(n) = O(m*n),北京林業(yè)大學信息學院,例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è)大學信息學院,例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è)大學信息學院,例3：分析以下程序段的時間復雜度,i=1; while(i=n) i=i*2; ,即f(n)log2n，取最大值f(n)=log2n,所以該程序段的時間復雜度T(n) =O( log2n),北京林業(yè)大學信息學院,例4：順序查找，在數(shù)組ai中查