數(shù)據(jù)結(jié)構(gòu)牛小飛第1章引論

1、 主講人：牛小飛e_mail: niujiaoxue163. compassword: niujiaoxue123e_mail: tel:論教學：理論教學：48學時學時實踐教學：上機實踐教學：上機8學時學時 2周集中課程設(shè)計周集中課程設(shè)計數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用:java語言描述語言描述sartaj sanhi 著著 汪詩林等譯汪詩林等譯 機械工業(yè)出版社機械工業(yè)出版社 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) java語言描述語言描述sichael main著著 機械工業(yè)出版社機械工業(yè)出版社 課程信息課程信息數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)( java版版)(第第2版版) 葉核亞編著葉核亞編

2、著 電子工業(yè)出版社電子工業(yè)出版社 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-java語言描述語言描述 朱戰(zhàn)立編著朱戰(zhàn)立編著 清華大學出版社清華大學出版社 要求要求不遲到、不曠課，良好的課堂紀律不遲到、不曠課，良好的課堂紀律作業(yè)按時交、字跡工整作業(yè)按時交、字跡工整實驗認真準備實驗認真準備課前預(yù)習、課后復(fù)習課前預(yù)習、課后復(fù)習數(shù)據(jù)結(jié)構(gòu)相關(guān)概念數(shù)據(jù)結(jié)構(gòu)相關(guān)概念引論引論小結(jié)和作業(yè)小結(jié)和作業(yè)本課程學習內(nèi)容本課程學習內(nèi)容用用javajava語言描述數(shù)據(jù)結(jié)構(gòu)語言描述數(shù)據(jù)結(jié)構(gòu)遞歸簡論遞歸簡論相關(guān)概念數(shù)據(jù)（data）2、形式3、含義數(shù)字、字符、圖形、圖像、音頻、視頻3089.2數(shù)據(jù)類型：int double char張三1、定義數(shù)據(jù)是描

3、述客觀事物的數(shù)字、字符以及所有能輸入到計算機中并能被計算機接受的各種符號集合的統(tǒng)稱。數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型是指一個值的集合和定義在這個值集上的操作的集合。高級程序設(shè)計語言通常預(yù)定義一些基本數(shù)據(jù)類型和構(gòu)造數(shù)據(jù)類型。java語言的基本數(shù)據(jù)類型有整數(shù)類型、浮點數(shù)類型、字符類型、布爾類型。構(gòu)造類型(引用類型)有數(shù)組、類和接口。數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)元素是數(shù)據(jù)的基本單位基本單位。一個數(shù)據(jù)元素可以是一個不可分割的原子項，也可以由多個數(shù)據(jù)項組成。 數(shù)據(jù)項是數(shù)據(jù)元素中有獨立含義的、不可分割的最小標識單位最小標識單位。一個整數(shù)、一個字符都是原子項；一個學生數(shù)據(jù)元素由學號、姓名、性別和出生日期等數(shù)據(jù)項組成。結(jié)構(gòu)（stru

4、cture）結(jié)構(gòu)：關(guān)系（relation）數(shù)據(jù)結(jié)構(gòu)data_structure=(d, s)d: a1, a2, a3, , ans: , , d：1, 7, 8, 9d：“abc”, “city”d：“張明”，“男”，19， “計算機”， “王明輝”，“男”，20，“法律”，從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:集合結(jié)構(gòu) 線性結(jié)構(gòu)樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)邏輯結(jié)構(gòu)da1, a2, , ans 集合da1, a2, , ans |ai-1 ,ai d, i=2,.,n 線性da1, a2, ,ans |i j 對每個j，存在唯一的i有 樹形da1, a2, ,ans |ai d, aj d 圖狀例

5、1有數(shù)據(jù)結(jié)構(gòu):d=1, 2, 3, 4, 5 s=, , , 什么數(shù)據(jù)結(jié)構(gòu)?邏輯結(jié)構(gòu)例1d=1, 2, 3, 4, 5 s=, , , 12345邏輯結(jié)構(gòu)例2有數(shù)據(jù)結(jié)構(gòu):d=1, 2, 3, 4, 5, 6, 7 s=, , , , , 什么數(shù)據(jù)結(jié)構(gòu)?邏輯結(jié)構(gòu)例2d=1, 2, 3, 4, 5, 6, 7 s=, , , , , 1234675邏輯結(jié)構(gòu)例3有數(shù)據(jù)結(jié)構(gòu):d=1, 2, 3, 4, 5, 6, 7,8 s=row, colrow=, , , , , col=, , , 什么數(shù)據(jù)結(jié)構(gòu)?邏輯結(jié)構(gòu)例31234675d=1, 2, 3, 4, 5, 6, 7,8 row=, , , , ,

6、 col=, , , 8邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)在內(nèi)存中如何表示？數(shù)據(jù)之間的關(guān)系在內(nèi)存中如何表示？表示x, y的方法兩種存儲結(jié)構(gòu)順序映像-順序存儲結(jié)構(gòu) 鏈式映像-鏈式存儲結(jié)構(gòu)存儲器模型1、電子元器件構(gòu)成存儲單元2、地址寄存器4、地址總線6、數(shù)據(jù)寄存器物理模型邏輯模型5、數(shù)據(jù)總線3、地址譯碼器0123n存儲器模型存儲器模型假設(shè)有假設(shè)有5位同學的成績表：位同學的成績表：2006001 992006002 802006003 852006004 602006005 70順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)元素元素n n.元素元素i i.元素元素2 2元素元素1 1lolo+mlo+(i-1)*mlo+（n-1)*m

7、存儲地址存儲地址存儲內(nèi)容存儲內(nèi)容2006001 992006002 802006003 852006004 602006005 70鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)存儲內(nèi)容存儲內(nèi)容l0元素元素n n.元素元素2 2.元素元素3 3元素元素1 12006001 992006002 802006003 852006004 602006005 70p數(shù)據(jù)結(jié)構(gòu)物理結(jié)構(gòu)邏輯結(jié)構(gòu)集合線性樹形圖狀順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)操作數(shù)據(jù)操作是指對一種數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素進行數(shù)據(jù)操作是指對一種數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素進行各種運算和處理。每種數(shù)據(jù)結(jié)構(gòu)都有一組數(shù)據(jù)操各種運算和處理。每種數(shù)據(jù)結(jié)構(gòu)都有一組數(shù)據(jù)操作。基本操作有

8、：作?；静僮饔校撼跏蓟跏蓟袛嗍欠窨諣顟B(tài)判斷是否空狀態(tài)求長度：統(tǒng)計元素個數(shù)求長度：統(tǒng)計元素個數(shù)包含：判斷是否包含指定元素包含：判斷是否包含指定元素遍歷：按某種次序訪問所有元素，每個元素只被訪問一次。遍歷：按某種次序訪問所有元素，每個元素只被訪問一次。取值：獲取指定元素值。取值：獲取指定元素值。置值：設(shè)置指定元素值。置值：設(shè)置指定元素值。插入、刪除等。插入、刪除等。學習內(nèi)容學習內(nèi)容1、如何使用存儲結(jié)構(gòu)實現(xiàn)邏輯結(jié)構(gòu)、如何使用存儲結(jié)構(gòu)實現(xiàn)邏輯結(jié)構(gòu)2、如何實現(xiàn)邏輯結(jié)構(gòu)的常用操作、如何實現(xiàn)邏輯結(jié)構(gòu)的常用操作3、如何評價？、如何評價？學習內(nèi)容學習內(nèi)容主要學習以下四種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法：主要學習以下四種

9、數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法：1.線性表線性表 2.棧和隊列棧和隊列 3.樹樹 4.圖圖散列及排序問題的算法設(shè)計散列及排序問題的算法設(shè)計 通過學習，可以深刻理解數(shù)據(jù)結(jié)構(gòu)的作用，通過學習，可以深刻理解數(shù)據(jù)結(jié)構(gòu)的作用，基本具備針對具體問題設(shè)計選擇數(shù)據(jù)結(jié)構(gòu)的能基本具備針對具體問題設(shè)計選擇數(shù)據(jù)結(jié)構(gòu)的能力。力。n引論： 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型的概念；遞歸程序；java描述數(shù)據(jù)結(jié)構(gòu)n算法分析：時間復(fù)雜度和空間復(fù)雜度n線性表：線性表的邏輯結(jié)構(gòu)定義、基本操作和在兩種存儲結(jié)構(gòu)中基本操作的實現(xiàn)；線性表的應(yīng)用。n棧和隊列：棧和隊列的結(jié)構(gòu)特性、基本操作及在兩種存儲結(jié)構(gòu)上基本操作的實現(xiàn)；棧和隊列的應(yīng)用。學習內(nèi)容學習內(nèi)

10、容n樹和二叉樹：樹的基本概念；二叉樹的定義、性質(zhì)、存儲表示；二叉樹的遍歷；森林和二叉樹的相互轉(zhuǎn)換；樹的應(yīng)用；哈夫曼樹及哈夫曼編碼。n散列：哈希表；n圖：圖的基本概念、存儲表示（鄰接矩陣、鄰接表、十字鏈表，鄰接多重表）；圖的遍歷、圖的連通性問題；拓撲排序、關(guān)鍵路徑；最短路徑。學習內(nèi)容學習內(nèi)容學習內(nèi)容學習內(nèi)容n排序：介紹插入排序、快速排序（交換排序）、選擇排序、歸并排序；排序的基本思想和算法分析。遞歸簡論遞歸簡論(教材教材1.3)大部分數(shù)學函數(shù)由簡單公式描述：大部分數(shù)學函數(shù)由簡單公式描述： c=5(f-32)/9 將華氏溫度轉(zhuǎn)換成攝氏溫度。將華氏溫度轉(zhuǎn)換成攝氏溫度。f(x)=0 if x=0f(x

11、)=2f(x-1)+x2 if x0 當一個函數(shù)用它自己來定義時就稱為是遞歸的。當一個函數(shù)用它自己來定義時就稱為是遞歸的。public int f(int x) if(x=0) return 0; else return 2*f(x-1)+x*x;/基準情況基準情況/遞歸調(diào)用遞歸調(diào)用遞歸函數(shù)遞歸函數(shù)舉例1f(x)=0 if x=0f(x)=2f(x-1)+x2 if x0 階乘 n！，n=0,1,2,3basis: 0!=1induction: n!=n(n -1)! 4！= 43！3！= 32！2！= 21！1！= 10!0! = 1public int factorial(int n) i

12、f( n = = 0) return 1; return n * factorial(n-1);遞歸函數(shù)遞歸函數(shù)舉例2遞歸函數(shù)遞歸函數(shù)xn，n=0,1,2,3basis: x0 = 1induction: xn = xn-1x x4= x3xx3=x2xx2= x1xx1=x0 xx0=1int power(float x, int n) if( n = = 0 ) return 1; return (power(x, n-1)*x);舉例3fibonacci數(shù)列 0 若n=0fib(n) = 1 若n=1 fib(n - 1) + fib(n - 2)0, 1, 1, 2, 3, 5遞歸函數(shù)

13、遞歸函數(shù)舉例4ackerman函數(shù) n + 1 若m=0ack(m, n)= ack(m - 1,1) 若n=0 ack(m - 1, ack(m, n - 1) 其它遞歸函數(shù)遞歸函數(shù)舉例5一個規(guī)模為n的問題可以分解為若干個規(guī)模小于n的相同問題遞歸體現(xiàn)為一個函數(shù)調(diào)用自身，即函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用可以用棧來實現(xiàn)遞歸簡論遞歸簡論用用javajava語言描述數(shù)據(jù)結(jié)構(gòu)語言描述數(shù)據(jù)結(jié)構(gòu)public class 線性表線性表/樹樹/圖圖 boolean isempty( );int length( );boolean contain(object obj);boolean add(elementty

14、pe element);boolean remove(object obj);public int thesize, count;用用javajava語言描述數(shù)據(jù)結(jié)構(gòu)語言描述數(shù)據(jù)結(jié)構(gòu)泛型特性構(gòu)件泛型特性構(gòu)件(教材教材1.4) 利用利用java實現(xiàn)泛型特性實現(xiàn)泛型特性(教材教材1.5) java泛型泛型n面向?qū)ο蟮囊粋€重要特點是對代碼重用的支持。n支持這個目標的一個重要機制就是泛型機制(generic mechanism)：如果除去對象的基本類型外，實現(xiàn)方法是相同的，就可以用泛型實現(xiàn)(generic implementation)來描述這種基本功能。javajava泛型泛型void swap(i

15、nt a, int i, int j) int temp=ai; ai=aj; aj=temp;void swap(anytype a, int i, int j) anytype temp=ai; ai=aj; aj=temp;javajava泛型泛型舉例1javajava泛型泛型public anytype extends comparable void bubblesort(anytype a) for(int i=a.length-1;i0;i-)for(int j=0;j0) swapreferences(a,j,j+1);public void bubblesort(int a)

16、for(int i=a.length-1;i0;i-)for(int j=0;jaj+1)0)swapreferences(a,j,j+1);帶有限制的通配符舉例2java泛型（generics）是jdk 5中引入的一個新特性，允許在定義類和接口的時候使用類型參數(shù)（type parameter）。聲明的類型參數(shù)在使用時用具體的類型來替換。 泛型類與一般的java類基本相同，只是在類和接口定義上多出來了用聲明的類型參數(shù)。javajava泛型泛型（1）簡單的泛型類）簡單的泛型類public class genericmemorycell public anytype read( ) return

17、storedvalue; public void write(anytype x) storedvalue=x; private anytype storedvalue; 當指定一個泛型類時，類的聲明則包含一個或多個類型參數(shù)，這些參數(shù)被放到類名后面的一對尖括號內(nèi)。舉例3public class myclassanytype extends comparable帶有限制的通配符帶有限制的通配符（2）使用）使用object表示泛型表示泛型n泛型memorycell類public class memorycell public object read( ) return storedvalue; p

18、ublic void write(object x) storedvalue=x; private object storedvalue;java中的基本思想就是可以通過使用像object這樣適當?shù)某悂韺崿F(xiàn)泛型類。舉例4（2）使用）使用object表示泛型表示泛型n測試memorycell類public class testmemorycell public static void main(string args) memorycell m=new memorycell();m.write(“37”);string val=(string)m.read();system.out.print

19、ln(val); 不能使用基本類型不能使用基本類型（2）使用）使用object表示泛型表示泛型n泛型泛型memorycell類類public class memorycell public object read( ) return storedvalue; public void write(object x) storedvalue=x; private object storedvalue;只有引用類型能與object相容。引用類型:數(shù)組、接口、類（3）基本類型的包裝）基本類型的包裝nint類型的包裝是integernbyte,short,long,float,double,boolean類型的包裝為第一個字符大寫，其余不變。ncha