數(shù)據(jù)結(jié)構(gòu)與算法（Java語言版）課件 第1、2章 數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介、算法復(fù)雜度

第1章數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介2024/11/91主要內(nèi)容邏輯結(jié)構(gòu)物理結(jié)構(gòu)算法與結(jié)構(gòu)1.1邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指有限多個(gè)節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）之間的邏輯關(guān)系，不涉及節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）在計(jì)算機(jī)中的存儲(chǔ)位置。2024/11/92主要的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖結(jié)構(gòu)和集合這四種結(jié)構(gòu)。⒈線性結(jié)構(gòu)2024/11/93在實(shí)際生活中，經(jīng)常遇到具有線性結(jié)構(gòu)的一組數(shù)據(jù)，比如，中國農(nóng)歷的二十四節(jié)氣：立春、雨水、驚蟄、春分、清明、谷雨、立夏、小滿、芒種、夏至、小暑、大暑、立秋、處暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒2024/11/94⒈線性結(jié)構(gòu)2024/11/95⒈線性結(jié)構(gòu)2024/11/96⒈線性結(jié)構(gòu)2024/11/972024/11/982.

樹結(jié)構(gòu)

2024/11/992.

樹結(jié)構(gòu)用倒置的樹形示意一個(gè)樹2024/11/9102.

樹結(jié)構(gòu)一個(gè)樹T=(A,R)

由多個(gè)互不相交的樹構(gòu)成2024/11/9112.

樹結(jié)構(gòu)樹的每個(gè)結(jié)點(diǎn)至多有2個(gè)子結(jié)點(diǎn)，稱這樣的樹是二叉樹二叉查詢樹，特點(diǎn)是，每個(gè)結(jié)點(diǎn)上的值都大于等于它的左子樹上的結(jié)點(diǎn)里的值、小于它的右子樹上結(jié)點(diǎn)里的值。首先猜m是上面的二叉樹的根結(jié)點(diǎn)中的數(shù)，如果猜測(cè)錯(cuò)誤，反饋信息給你，你猜測(cè)的比根結(jié)點(diǎn)中的數(shù)大，那你就繼續(xù)猜測(cè)這個(gè)數(shù)是當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)，如果告知你，你猜測(cè)的數(shù)不大于根結(jié)點(diǎn)中的數(shù)，那你就繼續(xù)猜測(cè)這個(gè)數(shù)是當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)，依次類推，您可以較快的猜測(cè)到這個(gè)數(shù)。2024/11/9122.

樹結(jié)構(gòu)樹的層從上至下，從0層開始根結(jié)點(diǎn)沒有父結(jié)點(diǎn)，非根、非葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但有一個(gè)或多個(gè)子結(jié)點(diǎn)，葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但沒有子結(jié)點(diǎn)。根據(jù)樹結(jié)構(gòu)的這個(gè)特點(diǎn)，可以把樹的結(jié)點(diǎn)按層次分類：樹的結(jié)點(diǎn)按層次分類，從根開始定義，根為第0層，根的子結(jié)點(diǎn)為第1層，以此類推。每一層上的結(jié)點(diǎn)只能和上一層中的至多一個(gè)結(jié)點(diǎn)有關(guān)系，但可能和下一層的0個(gè)或多個(gè)結(jié)點(diǎn)有關(guān)系。2024/11/9133.

圖結(jié)構(gòu)鋼筋焊接起來的平面架中的焊點(diǎn)：a,b,c,d,e2024/11/9143.

圖結(jié)構(gòu)鋼筋焊接起來的平面架中的焊點(diǎn)：a,b,c,d,e

這個(gè)圖結(jié)構(gòu)中，人們規(guī)定(a,b)和(b,a)是一樣的（都代表同一根鋼筋），即(a,b)和(b,a)都是沒有方向的“標(biāo)量”邊，這樣的圖結(jié)構(gòu)稱作無向圖2024/11/9153.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

2024/11/9163.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

對(duì)于G=(V,E)，如果(a,b)是邊，那么默認(rèn)(b,a)也就是邊，并規(guī)定(a,b)邊等于(b,a)邊，這樣規(guī)定的G=(V,E)是無向圖，簡(jiǎn)稱V是無向圖，即無向圖的邊是沒有方向的。無向圖2024/11/9173.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

如果(a,b)，(b,a)都是邊，就規(guī)定(a,b)邊不等于(b,a)邊，這樣規(guī)定的G=(V,E)是有向圖，簡(jiǎn)稱V是有向圖，即有向圖的邊是有方向的。2024/11/9184.

集合集合A中的元素除了同屬一個(gè)集合外，無其它任何關(guān)系，即關(guān)系集合是空集合，可表示為(A,?)（?是A×A的空子集）2024/11/919對(duì)于(A,R)，計(jì)算機(jī)程序在存儲(chǔ)空間中存放集合A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的形式，稱為A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的物理結(jié)構(gòu)，也稱為A的存儲(chǔ)結(jié)構(gòu)。1.2物理結(jié)構(gòu)比如，對(duì)于一個(gè)線性表，可根據(jù)需要采用順序存儲(chǔ)（節(jié)點(diǎn)的物理地址是依次相鄰的）或鏈?zhǔn)酱鎯?chǔ)（節(jié)點(diǎn)的物理地址不必是相鄰的）。常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)和哈希存儲(chǔ)等，有關(guān)細(xì)節(jié)見后續(xù)的章節(jié)，例如，第4章至第11章2024/11/920實(shí)施于集合上的算法，在其執(zhí)行完畢后，必須保持集合的邏輯結(jié)構(gòu)不變，比如，對(duì)于線性表，實(shí)施了增加或刪除節(jié)點(diǎn)的操作后，要保證新的節(jié)點(diǎn)構(gòu)成的集合仍然是線性結(jié)構(gòu)，否則算法必須對(duì)當(dāng)前的線性表的節(jié)點(diǎn)進(jìn)行調(diào)整，使得當(dāng)前線性表在邏輯上仍然是一個(gè)線性結(jié)構(gòu)。1.3算法與結(jié)構(gòu)有關(guān)細(xì)節(jié)見后續(xù)的章節(jié)，例如，第4章至第11章。算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)第2章算法復(fù)雜度2024/11/921主要內(nèi)容●算法●算法的復(fù)雜度

●常見的復(fù)雜度2.1算法算法(algorithm)就是一個(gè)正確的計(jì)算過程，該過程取某個(gè)值或值的集合作為輸入并產(chǎn)生某個(gè)值或值的集合作為輸出。2024/11/9222024/11/923算法的4個(gè)主要特性：2.1算法算法的4個(gè)主要特性是：●確切性：算法由語句組成，每個(gè)語句的功能是確切的?！褫斎霐?shù)據(jù)：可以向算法輸入多個(gè)或0個(gè)數(shù)據(jù)（方法可以有參數(shù)或無參數(shù)），即算法可以接收或不接收外部數(shù)據(jù)?！褫敵鰯?shù)據(jù)：算法可以給出明確的計(jì)算結(jié)果（方法的返回值）或輸出若干數(shù)據(jù)到客戶端以反映算法產(chǎn)生的效果?！窨尚行裕夯静僮鞫际窃谟邢迺r(shí)間內(nèi)被完成。所謂有限時(shí)間是指這個(gè)時(shí)值僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，即不會(huì)隨著n的增加而增大?！翊_切性●輸入數(shù)據(jù)●輸出數(shù)據(jù)●可行性2024/11/924一個(gè)算法不能在有限的時(shí)間內(nèi)結(jié)束，就不屬于算法復(fù)雜度的研究的范疇，比如一個(gè)算法里出現(xiàn)的無限循環(huán)，就不再屬于算法復(fù)雜度的研究的范疇了2.2復(fù)雜度算法，從執(zhí)行到結(jié)束，涉及兩個(gè)度量：一個(gè)是執(zhí)行方法所消耗的時(shí)間，一個(gè)是執(zhí)行方法所需要的內(nèi)存空間。2024/11/925方法里聲明的局部變量，包括參數(shù)都不歸類到基本操作，即不是基本操作。2.2復(fù)雜度⒈基本操作一個(gè)基本操作是一個(gè)語句或一個(gè)運(yùn)算表達(dá)式。一個(gè)基本操作是一個(gè)語句或一個(gè)運(yùn)算表達(dá)式，而且必須是在有限時(shí)間內(nèi)能被完成的計(jì)算步驟，其耗時(shí)僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，不會(huì)隨著n的增加而增大。2024/11/926在計(jì)算算法執(zhí)行的基本操作的總數(shù)時(shí)，要真對(duì)最壞的情況，即在某種條件下執(zhí)行的基本操作的總數(shù)是最多的情況2.2復(fù)雜度3時(shí)間復(fù)雜度算法執(zhí)行的基本操作的總數(shù)T(n)。算法的復(fù)雜度主要是度量隨著n的增大，T(n)值的趨勢(shì)。2024/11/927學(xué)習(xí)復(fù)雜度，記住一個(gè)通俗的道理：時(shí)間累加，空間不累加.2.2復(fù)雜度4復(fù)雜度比較2024/11/9282.3常見復(fù)雜度⒈O(jiān)(1)復(fù)雜度算法中的基本操作被執(zhí)行的總次數(shù)是一個(gè)常量，即不依賴一個(gè)正整數(shù)n、不會(huì)隨著n的增加而增大，那么將算法的時(shí)間復(fù)雜度，記作O(1)。算法中的所占用的內(nèi)存是一個(gè)常量，即所占內(nèi)存不依賴一個(gè)正整數(shù)n、不會(huì)隨著n的增加而增大，那么將算法的空間復(fù)雜度，記作O(1)。

例子1Max.javaExample2_1.java2024/11/9292.3常見復(fù)雜度1.O(1)復(fù)雜度

例子2Sum.javaExample2_2.java2024/11/9302.3常見復(fù)雜度2.O(n)復(fù)雜度

2024/11/9312.3常見復(fù)雜度2.O(n)復(fù)雜度例子3SumAndMult.java

Example2_3.java

2024/11/9322.3常見復(fù)雜度2.O(n)復(fù)雜度例子4ArrayMax.java

Example2_4.java

2024/11/9332.3常見復(fù)雜度2.O(n)復(fù)雜度例子5FindMissNumber.java

Example2_5.java

理論上知道，同一臺(tái)計(jì)算機(jī)，執(zhí)行“異或”運(yùn)算要比“加減”運(yùn)算快。所以，對(duì)于同一個(gè)算法，在復(fù)雜度相同的情況下，盡量使用速度快的基本操作。如果軟件的需求不十分介意速度，選擇的基本操作能使得的代碼更簡(jiǎn)練、閱讀性更好，那么也可以使用這樣的基本操作。2024/11/9342.3常見復(fù)雜度3.2024/11/9352.3常見復(fù)雜度3.例子6Multi.java

Example2_6.java

2024/11/9362.3常見復(fù)雜度3.例子7BubbleSort.java

Example2_7.java

2024/11/9372.3常見復(fù)雜度4.

2024/11/9382.3常見復(fù)雜度4.例子8OutPutNumber.java

Example2_8.java

2024/11/9392.3常見復(fù)雜度5.

2024/11/9402.3常見復(fù)雜度5.例子9FindNumber.java

Example2_9.java

2024/11/9412.3常見復(fù)雜度5.例子10Euclidean.java

Example2_10.java

2024/11/9422.3常見復(fù)雜度6.

如果一個(gè)方法里又調(diào)用了其它方法，即一個(gè)算法又包含另外一個(gè)算法，那么該方法的復(fù)雜度將和它包含的方法復(fù)雜度有關(guān)，需合并考察復(fù)雜度。

2024/11/9432.3常見復(fù)雜度6