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

1、 主講人：牛小飛e_mail: niujiaoxue163. compassword: niujiaoxue123e_mail: tel:論教學(xué)：理論教學(xué)：48學(xué)時(shí)學(xué)時(shí)實(shí)踐教學(xué)：上機(jī)實(shí)踐教學(xué)：上機(jī)8學(xué)時(shí)學(xué)時(shí) 2周集中課程設(shè)計(jì)周集中課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用:java語言描述語言描述sartaj sanhi 著著 汪詩林等譯汪詩林等譯 機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) java語言描述語言描述sichael main著著 機(jī)械工業(yè)出版社機(jī)械工業(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)立編著 清華大學(xué)出版社清華大學(xué)出版社 要求要求不遲到、不曠課，良好的課堂紀(jì)律不遲到、不曠課，良好的課堂紀(jì)律作業(yè)按時(shí)交、字跡工整作業(yè)按時(shí)交、字跡工整實(shí)驗(yàn)認(rèn)真準(zhǔn)備實(shí)驗(yàn)認(rèn)真準(zhǔn)備課前預(yù)習(xí)、課后復(fù)習(xí)課前預(yù)習(xí)、課后復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)相關(guān)概念數(shù)據(jù)結(jié)構(gòu)相關(guān)概念引論引論小結(jié)和作業(yè)小結(jié)和作業(yè)本課程學(xué)習(xí)內(nèi)容本課程學(xué)習(xí)內(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ù)字、字符以及所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)接受的各種符號(hào)集合的統(tǒng)稱。數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型是指一個(gè)值的集合和定義在這個(gè)值集上的操作的集合。高級(jí)程序設(shè)計(jì)語言通常預(yù)定義一些基本數(shù)據(jù)類型和構(gòu)造數(shù)據(jù)類型。java語言的基本數(shù)據(jù)類型有整數(shù)類型、浮點(diǎn)數(shù)類型、字符類型、布爾類型。構(gòu)造類型(引用類型)有數(shù)組、類和接口。數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)元素是數(shù)據(jù)的基本單位基本單位。一個(gè)數(shù)據(jù)元素可以是一個(gè)不可分割的原子項(xiàng)，也可以由多個(gè)數(shù)據(jù)項(xiàng)組成。 數(shù)據(jù)項(xiàng)是數(shù)據(jù)元素中有獨(dú)立含義的、不可分割的最小標(biāo)識(shí)單位最小標(biāo)識(shí)單位。一個(gè)整數(shù)、一個(gè)字符都是原子項(xiàng)；一個(gè)學(xué)生數(shù)據(jù)元素由學(xué)號(hào)、姓名、性別和出生日期等數(shù)據(jù)項(xiàng)組成。結(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， “計(jì)算機(jī)”， “王明輝”，“男”，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 對(duì)每個(gè)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的方法兩種存儲(chǔ)結(jié)構(gòu)順序映像-順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)接诚?鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)器模型1、電子元器件構(gòu)成存儲(chǔ)單元2、地址寄存器4、地址總線6、數(shù)據(jù)寄存器物理模型邏輯模型5、數(shù)據(jù)總線3、地址譯碼器0123n存儲(chǔ)器模型存儲(chǔ)器模型假設(shè)有假設(shè)有5位同學(xué)的成績表：位同學(xué)的成績表：2006001 992006002 802006003 852006004 602006005 70順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)元素元素n n.元素元素i i.元素元素2 2元素元素1 1lolo+mlo+(i-1)*mlo+（n-1)*m

7、存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容2006001 992006002 802006003 852006004 602006005 70鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)內(nèi)容存儲(chǔ)內(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)集合線性樹形圖狀順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)操作數(shù)據(jù)操作是指對(duì)一種數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素進(jìn)行數(shù)據(jù)操作是指對(duì)一種數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素進(jìn)行各種運(yùn)算和處理。每種數(shù)據(jù)結(jié)構(gòu)都有一組數(shù)據(jù)操各種運(yùn)算和處理。每種數(shù)據(jù)結(jié)構(gòu)都有一組數(shù)據(jù)操作?；静僮饔?/p>

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

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

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

11、)=2f(x-1)+x2 if x0 當(dāng)一個(gè)函數(shù)用它自己來定義時(shí)就稱為是遞歸的。當(dāng)一個(gè)函數(shù)用它自己來定義時(shí)就稱為是遞歸的。public int f(int x) if(x=0) return 0; else return 2*f(x-1)+x*x;/基準(zhǔn)情況基準(zhǔn)情況/遞歸調(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一個(gè)規(guī)模為n的問題可以分解為若干個(gè)規(guī)模小于n的相同問題遞歸體現(xiàn)為一個(gè)函數(shù)調(diào)用自身，即函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用可以用棧來實(shí)現(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實(shí)現(xiàn)泛型特性實(shí)現(xiàn)泛型特性(教材教材1.5) java泛型泛型n面向?qū)ο蟮囊粋€(gè)重要特點(diǎn)是對(duì)代碼重用的支持。n支持這個(gè)目標(biāo)的一個(gè)重要機(jī)制就是泛型機(jī)制(generic mechanism)：如果除去對(duì)象的基本類型外，實(shí)現(xiàn)方法是相同的，就可以用泛型實(shí)現(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中引入的一個(gè)新特性，允許在定義類和接口的時(shí)候使用類型參數(shù)（type parameter）。聲明的類型參數(shù)在使用時(shí)用具體的類型來替換。 泛型類與一般的java類基本相同，只是在類和接口定義上多出來了用聲明的類型參數(shù)。javajava泛型泛型（1）簡單的泛型類）簡單的泛型類public class genericmemorycell public anytype read( ) return

17、storedvalue; public void write(anytype x) storedvalue=x; private anytype storedvalue; 當(dāng)指定一個(gè)泛型類時(shí)，類的聲明則包含一個(gè)或多個(gè)類型參數(shù)，這些參數(shù)被放到類名后面的一對(duì)尖括號(hào)內(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這樣適當(dāng)?shù)某悂韺?shí)現(xiàn)泛型類。舉例4（2）使用）使用object表示泛型表示泛型n測(cè)試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類型的包裝為第一個(gè)字符大寫，其余不變。ncha