資源簡介

(共43張PPT)
第1章 數據結構與算法概述
數據結構的概念
邏輯結構與物理結構
算法的概念
數據結構的概念
邏輯結構與物理結構
算法的概念
1.2
1.3
1.1
點擊查看本小節知識架構
點擊查看本小節知識架構
點擊查看本小節知識架構
學習目標
了解
了解
了解
了解數據結構的概念與專業術語
1
2
了解數據的邏輯結構與物理結構
3
掌握算法的概念與特性
數據結構是計算機專業的一門基礎課，其主要研究程序設計中的操作對象及它們之間的關系。算法指的是解決問題的策略，只要有符合一定規范的輸入，在有限時間內就能獲得所要求的輸出。雖然數據結構與算法屬于不同的研究課題，但優秀的程序設計離不開二者的相輔相成。因此，本章將主要介紹數據結構與算法的基本概念，包括數據結構的基本術語、數據的結構分類以及算法的各種特性。
1.1 數據結構與算法
1.1.1
數據
返回目錄
1.1.2
數據元素與數據項
1.1.3
數據對象
1.1.4
數據結構
1.1.1 數據
數據（Data）在計算機科學中是指計算機操作的對象，是輸入到計算機中被計算機程序處理的符號集合。例如，一個讀取終端輸入的程序，其操作的對象可能是字符串，那么字符串就是計算機程序處理的數據。數據不僅可以是整型、字符型等數值類型，也可以是音頻、圖片、視頻等非數值類型。
綜上所述，數據的本質就是符號，且這些符號都滿足以下特定的需求。
（1）可以輸入到計算機中。
（2）可以被計算機程序處理。
其中數值類型的數據可以被執行數值計算，而非數值類型的數據可以被執行非數值的處理，例如，音頻、圖片、視頻等資源在計算中都是被編碼轉換為字符數據來處理的。
1.1.2 數據元素與數據項
數據元素（Data Element）是組成數據的基本單位。數據的基本單位是一種抽象的概念，并沒有具體的數值化標準。例如，可以將公司看作一個數據元素，也可以將員工視為一個數據元素。
數據元素由數據項組成，并且數據項是數據不可分割的最小單位。例如，將公司看作一個數據元素，則行政部、人事部、財務部都可以視為該元素的數據項，也可以將董事長、經理、總監作為該元素的數據項。
1.1.3 數據對象
數據對象（Data Object）指的是具有相同性質的數據元素的集合，是數據的子集。相同性質指的是數據項的數量與類型的相同。例如，每一個人都有姓名、年齡、性別、出生地址這些數據項。
在實際開發應用中，處理相同性質的數據元素時，默認將數據對象簡稱為數據。也就是說，“數據”在數據結構這一課題中代指數據對象，即具有相同性質的多個數據元素。
1.1.4 數據結構
結構（Structure）通常指的是數據元素之間的特定關系。因此，數據結構（Data Structure）通常指的是相互之間存在一種或多種特定關系的數據元素的集合。
數據結構主要研究的是數據的邏輯結構與數據的物理（存儲）結構以及它們之間的相互關系。其目的是對這種結構設計相應的算法，確保經過運算后得到的新結構仍保持原來的結構類型。
1.2 邏輯結構與物理結構
1.2.1
邏輯結構
返回目錄
1.2.2
物理結構
1.2 邏輯結構與物理結構
數據結構可分為邏輯結構與物理結構。數據的邏輯結構是對數據元素之間邏輯關系的描述，而數據的物理結構是指數據元素及其關系在計算機內存中的表示。
邏輯結構與物理結構是與數據結構密切相關的兩個概念，同一種邏輯結構可以對應不同的物理結構。算法的設計取決于數據的邏輯結構，算法的實現依賴于指定的物理結構。
1.2.1 邏輯結構
按照數據元素之間存在的邏輯關系的不同數學特性，通常可以將邏輯結構分為4種類型。
1.線性結構
線性結構中的數據元素之間是一對一的關系，即數據元素存在依次排列的先后次序關系，且只有一個起始數據元素和一個終止數據元素，如圖所示。
生活中的城市公交路線類似于上述結構，其站點就是數據元素，每一條公交線路都有一個起點和終點，中間各站都按先后次序排列。
1.2.1 邏輯結構
2.樹形結構
樹形結構中的數據元素之間存在一對多的關系，即層次關系或分支關系。這種結構只有一個起始數據元素（稱為樹根），其他數據元素稱為樹葉，如圖所示。
一個公司的組織架構類似于上述結構，樹根為公司，公司的下一層對應各部門，各部門下有各種分組。因此，公司架構可被抽象成樹形結構來進行數據管理，如圖所示。
1.2.1 邏輯結構
3.圖形結構
圖形結構中的數據元素之間存在多對多的網絡關系，即數據元素之間相互連接成網狀，如圖所示。
生活中常用的交通路線圖類似于上述結構，每一個地點都是一個數據元素，公路是地點之間的關系。一個地點可能與多個地點有公路，地點之間通過公路連接成網狀，如圖所示。
1.2.1 邏輯結構
4.集合結構
集合結構中的數據元素除了同屬一個集合外，沒有其他關系，各個元素是“平等”的，該結構類似于數學中的集合，如圖所示。
1.2.2 物理結構
物理結構即存儲結構，主要指的是數據的邏輯結構在實際的計算機內存中存儲的形式。通常數據的物理結構有以下4種類型。
1.順序存儲
順序存儲指的是將相鄰的數據元素存放在計算機地址連續的存儲單元中，如圖所示。
1.2.2 物理結構
在C語言程序中，數組采用的就是典型的順序存儲。當程序中定義一個含有5個整型元素的數組時，操作系統就會在內存中申請一塊連續且大小為20字節的區域存放這個數組。數組中的元素依次存放在這塊連續的區域中，每個元素占4個字節。
2.鏈式存儲
鏈式存儲不同于順序存儲，在順序存儲中，邏輯上相鄰的數據元素在內存中也是相鄰的，而鏈式存儲中，邏輯上相鄰的數據元素在內存中不一定相鄰。簡單地說，鏈式存儲中的數據元素可以存儲在內存的任意位置。如圖所示，C語言程序通過指針指向地址的方式來連接不同存儲位置上的數據元素。
1.2.2 物理結構
生活中的飛機航班路線就可以理解為鏈式結構。假設飛機從北京飛往廣州，且需要經停長沙，那么北京、長沙、廣州可認為是在邏輯上相鄰的元素，航班路線就是三者的邏輯關系，但是這三座城市在地理位置上是不相鄰的。
3.索引存儲
索引存儲指的是在存儲數據元素的同時建立索引列表，存儲元素之間的關系。這是一種為了加速檢索而創建的存儲結構。例如，一所大學在安排學生宿舍時，一定不能按照學生的學號依次分配宿舍，學號并不考慮性別，也就是說不可能采用順序存儲；其次，也不能是鏈式存儲，因為學號只是學生的一個標識，沒有其他意義。因此，為學生分配宿舍可采用索引存儲，即建立一個索引列表記錄學號與宿舍關系，根據索引列表即可找到與學號對應的宿舍。
4.散列存儲
散列存儲指的是根據數據元素的關鍵字直接計算出該數據元素的存儲位置。其基本的設計思想是以數據元素的關鍵字K為自變量，通過一個確定的函數關系f（稱為散列函數），計算出對應的函數值f(K)，將這個值解釋為數據元素的存儲地址，最后將數據元素存入f(K)所指的存儲位置上。查找時只需根據要查找的關鍵字用同樣的函數計算地址，然后到相應的地址提取要查找的數據元素。
1.3 算法的概念
1.3.1
算法的描述
返回目錄
1.3.2
算法的特性
1.3.3
算法的設計要求
1.3.4
算法效率的度量方法
1.3 算法的概念
1.3.5
算法的時間復雜度
返回目錄
1.3.6
算法的空間復雜度
1.3 算法的概念
算法是解決問題的方法，該術語最早出現在公元825年由波斯數學家阿勒 花刺子密所寫的《印度數字算術》中。
1.3.1 算法的描述
算法可以用自然語言、數學語言、約定的符號語言或計算機程序語言來描述。例如，“從3個整數中選出最大的1個整數輸出”這一問題，可采用以下3種方法來描述。
1.自然語言描述
（1）輸入3個整數a、b、c。
（2）先從前兩個整數a、b中選出較大的一個整數，設為x。
（3）從x、c中選出較大的整數，設為y。
（4）輸出y的值。
使用自然語言描述算法通俗易懂，但算法整體的數據流向不夠清晰。
1.3.1 算法的描述
2.符號語言描述
描述算法的符號語言有很多種類型，其中比較有特點的是程序流程圖，如圖所示。
程序流程圖描述算法比較清晰，而且容易轉換為計算機語言。
1.3.1 算法的描述
3.計算機程序語言描述
計算機程序語言有很多，本次使用C語言，如例所示。
用計算機程序語言描述算法對描述者的要求較高，需要描述者在理解算法工作原理的前提下，具備計算機語言的編程能力。但這種描述可以直接輸入計算機，便于驗證其正確性。
1.3.2 算法的特性
算法有5個基本的特性：輸入、輸出、有窮性、確定性、可行性。
1.輸入
一個算法可以有多個或沒有輸入，具體的輸入量取決于算法中的數據對象。有些算法的輸入需要在執行過程中進行，有些算法則將輸入嵌入到算法之中，如例所示。
從例中可以看出，變量i在函數內部自加并完成運算，無須用戶輸入。沒有輸入量的算法，其輸出結果一般是固定的。
1.3.2 算法的特性
2.輸出
一個算法必須有一個或多個輸出，這些輸出是算法對輸入進行運算后的結果。如果一個算法沒有輸出，則算法沒有任何意義。
3.有窮性
有窮性指的是算法在執行有限次數的操作后自動停止，不會出現無限循環的情況，且每次操作都可以在有限時間內完成。簡單地說，算法運行一定有結束的時刻。
1.3.2 算法的特性
在例中，代碼第8行的循環語句添加了分號，成為一個獨立的語句。當輸入的n值大于0時，此語句將無限循環，因為i的值一直為0。
例就是典型的錯誤算法，程序不能在有限時間內結束，而是進入死循環狀態。將第8行的分號去掉，則第8行與第9行代碼變成一個完整的語句，實現在有限次循環中疊加，算法具備了有窮性。
4.確定性
確定性指的是算法的每次操作都具有確定的含義，不會出現二義性。算法在一定條件下，應只有一條執行路徑，相同的輸入在任何時刻執行都應該導向相同的結果。
5.可行性
可行性指的是算法中描述的操作都可以通過將已經實現的基本運算執行有限次來實現。簡單地說，算法可以轉換為程序上機運行，并可以輸出正確的結果。
1.3.3 算法的設計要求
同一個問題可以有很多種算法。判斷一個算法是否為最優算法，可以從以下4個方面分析。
1.正確性
算法的正確性指的是算法能正確反映問題的需求，經得起一切可輸入數據的測試。算法的正確性包括以下4個層次。
（1）算法程序無語法錯誤。
（2）算法程序對于合法的輸入數據能夠產生滿足要求的輸出結果。
（3）算法程序對于非法的輸入數據能夠產生滿足規格的說明。
（4）算法程序對于極端的輸入數據能夠產生滿足要求的輸出結果。
1.3.3 算法的設計要求
例的算法程序看似沒有錯誤，但是當用戶輸入的數據為0或負數時，該算法都無法產生滿足需求的結果。
1.3.3 算法的設計要求
2.可讀性
可讀性指的是算法的設計應該盡可能簡單，便于閱讀、理解。
3.健壯性
健壯性指的是算法可以對不合法的輸入數據做出處理，而不是產生異常或極端的結果。
4.高效率
高效率指的是算法的執行時間要盡量短，對存儲空間的使用要盡可能少。在滿足前3個要求的前提下，高效率是體現算法優異的重要指標。
1.3.4 算法效率的度量方法
由1.3.3節可知，高效率算法應該具備運行時間短和存儲量低的特點。接下來介紹如何對算法效率進行測試。
1.事后統計法
事后統計法指的是通過設計好的測試程序和數據，對不同算法程序的運行時間進行比較，從而確定算法效率的高低。
通常情況下，不采用事后統計法進行算法效率測試，其原因如下。
（1）解決問題的算法有很多，為了測試某算法效率的高低，需要盡可能多地編寫算法程序與之進行比較測試，而設計編寫算法程序需要大量的時間和精力。
（2）程序運行時間受計算機硬件等環境因素影響，有時會掩蓋算法本身的優劣。例如，八核處理器明顯比單核處理器處理程序的速度要快。
（3）算法測試數據設計困難，效率高的算法在測試數據規模小時表現不明顯。
1.3.4 算法效率的度量方法
2.事前分析法
事前分析法指的是設計算法程序之前，根據統計方法對算法進行估算。一個好的算法所消耗的時間，應該是算法中每條語句執行的時間之和；每條語句的執行時間是該語句的執行次數與該語句執行一次所需時間的乘積。
接下來對比兩個求和的示例，討論算法的優劣。
1.3.4 算法效率的度量方法
例通過循環累加計算從1到100的和，在不討論語句執行一次所需時間的情況下（只討論語句執行次數），可見示例核心部分的語句總共執行了 2×n+5 次。
例1-6實現與例1-5相同的需求，其核心部分的語句總共執行了3次。
1.3.4 算法效率的度量方法
由上述示例可以看出，在相同硬件環境下，例1-6所示的算法程序明顯優于例1-5。變量n的值越大，例1-5所示的算法程序劣勢越明顯。
在上述兩個示例的基礎上再進行進一步討論，如例所示。
在例中，外部循環的循環次數為n，內部循環的循環次數也為n，因此循環內部的x++語句將執行 n 2 次。顯然，隨著n值的增加，例1-7的執行次數明顯高于例1-5和例1-6。
1.3.5 算法的時間復雜度
在1.3.4節中的例1-5、例1-6、例1-7中，變量n稱為問題規模，算法中語句的執行次數稱為時間頻度，記為T(n)。例1-5和例1-7中，當n不斷變化時，時間頻度T(n)也會不斷變化。
如果有某個輔助函數f(n)，并且存在一個正常數c使得 f(n)×c≥T(n)恒成立，則記作 T(n)=O(f(n))。通常將 O(f(n))稱為算法的漸進時間復雜度，簡稱時間復雜度。使用O( )計算時間復雜度的記法稱為大O記法。一般情況下，隨著n的增大，T(n)增長最慢的算法為最優算法。
利用上述時間復雜度的公式，分別計算例1-5、例1-6、例1-7中算法的時間復雜度，具體分析如下。（輔助函數 f(n)獲取執行次數，正常數c視為單次執行時間，可以忽略。）
（1）例1-5的算法時間為 2×n+5，則 f(n)=2n+5。當問題規模n變為無窮大時，該算法的執行時間可估算為n，使用大O記法表示時間復雜度為 O(n)。
（2）例1-6的算法時間為3，則 f(n)=3。此值相較于無窮大的n值可忽略不計，因此使用大O記法表示時間復雜度為 O(1)。（ O(1)表示執行次數或時間是一個常數，不隨著n的變化而變化）
（3）例1-7的算法時間為 3×n 2 +3×n+3，則 f(n)=3(n 2 +n+1)。當問題規模n變為無窮大時，該算法的執行時間可估算為 n 2 ，使用大O記法表示時間復雜度為 O(n 2 )。
1.3.4 算法的度量方法
通常情況下，將 O(1)、O(n)、O(n 2 )分別稱為常數階、線性階、平方階。除此之外，還有對數階、指數階等其他階。
1.常數階
例中的算法時間為3，根據上述時間復雜度計算方法可知，該算法的時間復雜度沒有最高階項，就是一個常數。使用平面直角坐標系表示常數階，如圖所示。
2.線性階
例中的算法時間為 2n+5，根據上述時間復雜度計算方法可知，隨著問題規模n變大，時間復雜度成線性增長。使用平面直角坐標系表示線性階，如圖所示。
1.3.4 算法的度量方法
3.平方階
例中的算法執行時間為 3(n 2 +n+1)，根據上述時間復雜度計算方法可知，隨著問題規模n變大，時間復雜度線性增長變快。使用平面直角坐標系表示平方階，如圖所示。
1.3.4 算法的度量方法
常見的時間復雜度如表所示。
常見的時間復雜度所對應的時間從短到長依次為：
1.3.6 算法的空間復雜度
了解算法的空間復雜度之前，需要先理解算法存儲量的概念。算法的存儲量指的是算法執行過程中所需的最大存儲空間，其主要包括3個部分：輸入/輸出數據所占空間、程序代碼所占空間、程序運行臨時占用空間。
1.輸入/輸出數據所占空間
算法的輸入/輸出數據所占用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不會隨著算法的不同而改變，因此在算法比較時不予考慮。
2.程序代碼所占空間
算法的程序代碼所占用的存儲空間與程序的長度成正比，要壓縮這部分存儲空間，就必須編寫出較短的程序。程序代碼本身所占空間對不同算法來說不會有數量級的差別。
1.3.6 算法的空間復雜度
3.程序運行臨時占用空間
根據程序在運行過程中臨時占用存儲空間的不同，可以將算法分為兩類。
（1）原地算法：只占用較小的臨時空間，且占有量不會隨著問題規模n的改變而改變。
（2）非原地算法：占用臨時空間的大小與問題規模n有關，n越大占用的臨時空間越大。
通過計算算法存儲量可以得到算法的空間復雜度，算法空間復雜度的計算公式記作 S(n)=O(f(n))，其中，n為問題的規模，f(n)為關于n所占存儲空間的函數。隨著問題規模n的增大，算法存儲量的增長率與 f(n)的增長率相同。
1.3.6 算法的空間復雜度
根據上述概念，使用示例進行具體分析，如例所示。
例現的功能為從1到n的數值累加。其中，變量s、i所占用的空間不會隨著n的變化而發生改變，因此空間復雜度與n無關，該算法的空間復雜度記作 S(n)=O(1)。
本章小結
本章以概念為主，重點介紹了數據的概念、數據的邏輯結構與物理結構以及算法的概念。其中，數據的邏輯結構與物理結構以及二者之間的關系，是數據結構研究的核心內容。讀者需要對數據結構與算法建立初步的認識，重點要理解邏輯結構與物理結構的設計思想，為后續的程序設計奠定良好的基礎。

展開更多......

收起↑