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

樹結構

2024/11/992.

樹結構用倒置的樹形示意一個樹2024/11/9102.

樹結構一個樹T=(A,R)

由多個互不相交的樹構成2024/11/9112.

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

樹結構樹的層從上至下，從0層開始根結點沒有父結點，非根、非葉結點有且只有一個父結點，但有一個或多個子結點，葉結點有且只有一個父結點，但沒有子結點。根據樹結構的這個特點，可以把樹的結點按層次分類：樹的結點按層次分類，從根開始定義，根為第0層，根的子結點為第1層，以此類推。每一層上的結點只能和上一層中的至多一個結點有關系，但可能和下一層的0個或多個結點有關系。2024/11/9133.

圖結構鋼筋焊接起來的平面架中的焊點：a,b,c,d,e2024/11/9143.

圖結構鋼筋焊接起來的平面架中的焊點：a,b,c,d,e

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

圖結構當V×V的子集E滿足下列①和②時，稱E是V上的圖關系，記作G=(V,E)

2024/11/9163.

圖結構當V×V的子集E滿足下列①和②時，稱E是V上的圖關系，記作G=(V,E)

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

圖結構當V×V的子集E滿足下列①和②時，稱E是V上的圖關系，記作G=(V,E)

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

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

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

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

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

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

Example2_3.java

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

Example2_4.java

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

Example2_5.java

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

Example2_6.java

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

Example2_7.java

2024/11/9372.3常見復雜度4.

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

Example2_8.java

2024/11/9392.3常見復雜度5.

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

Example2_9.java

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

Example2_10.java

2024/11/9422.3常見復雜度6.

如果一個方法里又調用了其它方法，即一個算法又包含另外一個算法，那么該方法的復雜度將和它包含的方法復雜度有關，需合并考察復雜度。

2024/11/9432.3常見復雜度6