1. 1 知識學習

本節將介紹數據結構課程的研究內容、數據結構的基本概念，以及算法的概念、特性及評價方法。

1.1.1 數據結構課程的研究內容

數據結構（Data Structure）起源于程序設計。計算機解決問題時，一般要經過以下幾個步驟：首先要將實際問題抽象出數學模型，然后針對數學模型設計出求解算法，最后編寫程序上機調試，直到求出最終結果。數值計算問題的數學模型一般可由數學方程或數學公式來描述。

隨著計算機科學技術的發展，計算機應用領域不再局限于數值計算，而是更多地應用于信息處理、智能控制、辦公自動化等非數值計算領域。

對于非數值計算問題，如導學問題中涉及的學生信息管理、文件樹形列表顯示、道路最短路徑求解等問題，它們的數學模型無法用數學方程或數學公式來描述，而是要用抽象出的數據模型來描述，并且要對這些模型設計相應的算法來求解。數據結構就是研究非數值計算問題中的數據以及它們之間的關系和操作算法的學科。數據結構主要包含3個方面的內容：數據的邏輯結構、數據的存儲結構（物理結構）和數據的操作算法，如圖1-3所示。

1968年，數據結構作為一門獨立的課程在美國開設，在這之前，它的某些內容已在其他課程中涉及。1968年，斯坦福大學的康納德·克努特教授開創了數據結構的最初體系，他所著的 《計算機程序設計藝術》第一卷 《基本算法》是一本較系統地闡述數據的邏輯結構、存儲結構及其操作算法的著作。后來各種版本的數據結構著作相繼出現，如Pascal版、C版、C++版、Java版。我國于20世紀80年代初開設“數據結構”課程，該課程不僅是計算機專業教學計劃中的核心課程之一，還是其他信息類專業的必修課。

20世紀60～80年代，計算機開始廣泛應用于非數值計算領域，數據組織成為程序設計的重要問題。人們認識到程序設計規范的重要性，提出了結構化程序設計的思想。數據結構概念的引入對程序設計的規范化起到了重要作用。圖靈獎獲得者、瑞士計算機科學家尼古拉斯·沃斯教授曾提出“程序=數據結構+算法”，由此可以看出，數據結構和算法是構成程序的兩個重要組成部分。

1.1.2 數據的結構

1. 相關術語

（1）數據

數據（Data）是信息的載體，是指所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。數據可以分為兩大類：一類是整數、實數等數值數據，另一類是圖形、圖像、聲音、文字等非數值數據。

（2）數據元素

數據元素（Data Element）是組成數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數據元素具有廣泛的含義，一般來說，能獨立、完整地描述問題的一切實體都是數據元素。數據元素又稱為元素、結點、頂點或記錄。構成數據元素的不可分割的最小單位稱為數據項（Data Item）。數據元素是討論數據時涉及的最小數據單位，其中的數據項一般不予考慮。

例如，問題1-4涉及的學生成績表1-1中，一條學生記錄就是一個數據元素或稱為一個結點，其中的學號、姓名等就是數據項；問題1-5涉及的樹形文件目錄結構中，一個文件或文件夾稱為一個數據元素或一個結點；問題1-6中涉及的城市地標建筑道路圖中，一個地標建筑就是一個數據元素（或稱為一個結點）。

（3）數據對象

數據對象（Data Object）是具有相同性質數據元素的集合，是數據的子集。在實際應用中處理的數據元素通常具有相同的性質。例如，學生成績表中每個數據元素具有相同數目和類型的數據項，所有數據元素的集合就構成了一個數據對象。

2. 數據結構的三要素

數據結構的三要素包括數據的邏輯結構、存儲結構和操作算法，如圖1-4所示。

（1）數據的邏輯結構

數據的邏輯結構（Logical Structure）是指數據元素之間的邏輯關系。邏輯關系是指數據元素之間的關聯方式或鄰接關系。數據的邏輯結構常用邏輯結構圖來描述，其描述方法是將每一個數據元素看作一個結點，用圓圈表示，元素之間的邏輯關系用結點之間的連線表示。如果強調關系的方向性，則用帶箭頭的連線表示關系。

如圖1-5所示，數據的邏輯結構分為4類。樹結構和圖結構也稱為非線性結構。

為了更確切地描述一種數據結構，通常采用如下的二元組形式化定義數據結構：

Data_Structure=（D，R）

其中，D是數據元素的有限集合，R是D上關系的有限集合。

例如，有一種數據結構T=（D，R），其中：

D ={a，b，c，d，e，f，g，h，i，j}

R ={（a，b），（a，c），（a，d），（b，e），（c，f），（c，g），（d，h），（d，i），（d，j）}

顯然，數據結構T是一棵樹形結構。

（2）數據的存儲結構

數據的存儲結構（Storage Structure）又稱為物理結構，是數據元素及其邏輯結構在計算機中的表示。換言之，存儲結構除了存儲數據元素之外，必須隱式或顯示地存儲數據元素之間的邏輯關系。通常有兩種存儲結構：順序存儲結構和鏈式存儲結構，如圖1-6所示。

順序存儲結構是指用一組連續的存儲單元存儲數據元素。數據元素之間的邏輯關系是由元素的存儲位置來表示的。例如，線性表（a，b，c）的順序存儲示意圖如圖1-7所示。

鏈式存儲結構是指用一組任意的存儲單元存儲數據元素。數據元素之間的邏輯關系是用指針來表示的。例如，線性表（a，b，c）的鏈接存儲示意圖如圖1-8所示。

數據的邏輯結構和存儲結構是密切相關的。一般來說，一種數據的邏輯結構可以用多種存儲結構來存儲，而采用不同的存儲結構，其數據處理的效率往往是不同的。

（3）數據的操作算法

對數據的操作有以下兩個方面的含義：操作的定義和操作的實現，如圖1-9所示。操作的定義取決于數據的邏輯結構，知道了問題中的數據及數據間的聯系，就可以設計相應的數據操作方法。

對數據的操作通常可以分為數值型計算和非數值型計算。對于數據的數值型操作在C/C++ 語言中都學習過，如整型、實型、字符型、指針、數組、結構體、類等數據類型（Da-ta Type）就規定了該類型數據的取值范圍和對這些數據所能采取的操作。這里的數據類型是一組值的集合以及定義于這個值集上的一組操作的總稱。例如，C/C++中的整型變量可以取的值是機器所能表示的最小負整數和最大正整數之間的任何一個整數，允許的操作有+、-、*、/、%、＜、＜=、＞、＞=、==、！=等。

常見的非數值型操作如下。

● 初始化：對存儲結構設定初值或申請存儲空間。

● 輸出：輸出所有數據元素的各數據項內容。

● 取值：獲取指定數據元素的值。

● 置值：修改（更新）指定數據元素的值。

● 插入：增加數據元素。

● 刪除：刪除數據元素。

以上這些基本非數值型操作以及其他（如排序、求最短路徑等）非數值型操作的實現與數據元素的存儲形式密切相關，即數據操作算法的實現基于數據的存儲結構。后續章節中將詳細介紹各類問題操作算法的實現。

將一個數據結構以及定義在該結構上的一組操作的總稱定義為抽象數據類型（Abstract Data Type，ADT）。數據類型和ADT的區別在于：數據類型是指高級程序設計語言支持的基本數據類型，而ADT是指自定義的數據類型。例如，本課程將要學習的表、棧、隊列、樹、圖等結構就是一些不同的ADT。

1.1.3 算法與算法分析

1. 算法

（1）算法的概念

算法（Algorithm）是計算機求解特定問題的方法和步驟，是指令的有限序列。通常一個問題可以有多種算法，一個給定算法解決一個特定的問題。

算法具有以下5個重要特性：

1）輸入。一個算法有零個或多個輸入（即算法可以無輸入），這些輸入通常取自于某個特定的對象集合。

2）輸出。一個算法有一個或多個輸出（即算法必須要有輸出），通常輸出與輸入之間有著某種特定的關系。

3）有窮性。一個算法必須（對任何合法的輸入）在執行有窮步之后結束，且每一步都在有窮時間內完成。

4）確定性。算法中的每一條指令必須有確切的含義，不存在二義性，并且在任何條件下，對于相同的輸入只能得到相同的輸出。

5）可行性。算法描述的操作可以通過已經實現的基本操作執行有限次來實現。

算法與程序不同。程序（Program）是對一個算法使用某種程序設計語言的具體實現。原則上，任一算法可以用任何一種程序設計語言實現。算法的有窮性意味著不是所有的計算機程序都是算法。例如，操作系統是一個在無限循環中執行的程序，而不是一個算法，可以把操作系統的各個任務看成是一個單獨的問題，每一個問題由操作系統中的一個子程序通過特定的算法來實現，得到輸出結果后便終止。

（2）算法的評價

數據結構與算法之間存在著本質聯系。本課程學習的目的就是要在某一種數據結構基礎上學習算法設計方法，不但要設計正確的算法，而且要設計“好”的算法。什么樣的算法是“好”的算法呢？通常一個“好”算法具有以下5個基本特性。

1）正確性。算法能滿足具體問題的需求，即對于任何合法的輸入，算法都會得出正確的結果。

2）健壯性（魯棒性）。算法對非法輸入的抵抗能力，即對于錯誤的輸入，算法應能識別并做出處理，而不是產生錯誤動作或陷入癱瘓。

3）可讀性。一個好的算法應該便于人們理解和相互交流。可讀性好的算法有助于人們對算法的理解，反之，難懂的算法易于隱藏錯誤且難于調試和修改。

4）高效率。算法的效率通常是指算法的執行時間。對于同一個問題，如果有多個算法可以解決，則執行時間短的算法效率高。

5）低存儲空間。算法需要的存儲空間是指算法在執行過程中所需要的最大存儲空間，它與問題規模有關。一個“好”算法應該占用較少的輔助空間。

（3）算法的描述方法

設計了一個算法之后，必須清楚準確地將所設計的求解步驟表達出來，即描述算法。算法的描述方法通常有自然語言、流程圖、偽代碼和程序設計語言等方法。下面以歐幾里得算法（用輾轉相除法求兩個自然數m和n的最大公約數，并假設m≥n）為例進行介紹。

1）自然語言。用自然語言描述算法的最大優點是容易理解，缺點是容易出現二義性，并且算法通常都很冗長。歐幾里得算法用自然語言描述如下：

①輸入m和n。

②求m除以n的余數r。

③若r等于0，則n為最大公約數，算法結束；否則執行步驟④。

④將n的值放在m中，將r的值放在n中。

⑤重新執行步驟②。

2）流程圖。用流程圖描述算法的優點是直觀易懂，缺點是嚴密性不如程序設計語言，靈活性不如自然語言。歐幾里得算法用流程圖描述如圖1-10所示。

在計算機應用早期，使用流程圖描述算法占有統治地位，但實踐證明，除了一些非常簡單的算法以外，這種描述方法使用起來非常不方便。

3）偽代碼。偽代碼是介于自然語言和程序設計語言之間的方法，計算機科學家對偽代碼的書寫形式沒有做出嚴格的規定。它采用某一種程序設計語言的基本語法，操作指令可以結合自然語言來設計。算法中自然語言的成分有多少取決于算法的抽象級別。抽象級別高的偽代碼自然語言多一些，抽象級別低的偽代碼程序設計語言的語句多一些。只要具有一些程序設計語言基礎的人都能閱讀偽代碼。歐幾里得算法用C++偽代碼描述如下：

偽代碼不是一種實際的編程語言，但在表達能力上類似于編程語言，同時極小化了描述算法的不必要的技術細節，是比較合適的描述算法的方法，被稱為“算法語言”。

本書采用基于C/C++語言的偽代碼來描述算法，使得算法的描述簡明清晰，既不拘泥于C/C++語言的實現細節，又容易轉換為C/C++程序。

4）程序設計語言。用程序設計語言描述的算法能由計算機直接執行，缺點是抽象性差，使算法設計者拘泥于描述算法的具體細節，忽略了“好”算法和正確邏輯的重要性。此外，還要求算法設計者掌握程序設計語言及其編程技巧。歐幾里得算法用C++語言書寫的程序如下：

2. 算法分析

一種數據結構的優劣是由實現其各種操作的算法決定的。對數據結構的分析實質上就是對實現各種操作的算法進行分析。除了要驗證算法是否正確解決問題外，還需要對算法的效率進行評價。對于一個實際問題的解決，可以提出若干算法，那么如何從這些可行的算法中找出最有效的算法呢？有了一個解決實際問題的算法，如何來分析它的性能呢？這些問題需要通過算法分析來確定。通常算法分析主要分析算法的時間代價和空間代價這兩個主要指標。

可能有人認為，隨著計算機功能的日益強大，程序的運行效率變得越來越不重要了。然而，計算機功能越強大，人們就越想去嘗試解決更復雜的問題，而更復雜的問題需要更大的計算量。實際上，不僅需要算法，而且需要“好”算法。以破解密碼的算法為例，理論上，通過窮舉法列出所有可能的輸入字符的組合情況可以破解任何密碼，但是，如果密碼較長或組合情況太多，這個破解算法就需要很長時間，可能幾年、十幾年甚至更多，這樣的算法顯然沒有實際意義。所以，在選擇和設計算法時要有效率的觀念，這一點比提高計算機本身的速度更為重要。

（1）度量算法效率的方法

如何度量一個算法的效率呢？一種方法是事后統計的方法，先將算法實現，然后輸入適當的數據運行，測算其時間和空間開銷。事后統計的方法有以下缺點：

● 編寫程序實現算法將花費較多的時間和精力。

● 所得實驗結果依賴于計算機的軟、硬件等環境因素，有時容易掩蓋算法本身的優劣。

通常采用事前分析估算的方法——漸進復雜度（Asymptotic Complexity），它是對算法所消耗資源的一種估算方法。

（2）算法的時間復雜度

撇開與計算機軟、硬件有關的因素，影響算法時間代價的最主要因素是問題規模。問題規模是指輸入量的多少。一般來說，它可以從問題描述中得到。例如，對一個具有n個整數的數組進行排序，問題規模是n；對一個m行n列的矩陣進行轉置，則問題規模是m×n。一個顯而易見的事實是：幾乎所有的算法，對于規模更大的輸入都需要運行更長的時間。例如，需要更多時間來對更大的數組排序，更大的矩陣轉置需要更長的時間。所以，運行算法所需要的時間是問題規模n的函數。

要精確地表示算法的運行時間函數常常是很困難的，即使能夠給出，也可能是一個相當復雜的函數，函數的求解本身也是相當復雜的。算法時間分析度量的標準不是針對實際執行時間精確算出算法執行的具體時間，而是針對算法中基本語句的執行次數做出估計。設算法中基本語句執行的總次數是問題規模n的某個函數f（n），因此算法時間量度記作：T（n）=O（f（n）），它表示隨著問題規模n的增大，算法執行時間增長率和f（n）增長率相同，稱為算法的漸近時間復雜度，簡稱時間復雜度（Time Complexity），通常用大O記號表示。這里的“O”是英文“Order”的縮寫，但并不代表“順序”的意思，而是一個數量級的概念，表示在計算任何算法的時間復雜度時忽略所有低次冪項和最高次冪項的系數。即

O（a_mn^m+a_m-1n^m-1+…+a₁n+a₀）=O（n^m）

例：求下列各程序段的時間復雜度。

1）for（i=1；i＜100；i++） s++；

該程序段的語句執行次數是常量，時間復雜度記為O（1），稱為常量階。

2）for（i=0；i＜n；i++） s+=i；

該程序段基本語句s+=i，執行次數f（n）=n，因此它的時間復雜度T（n）=O（f（n））=O（n），稱為線性階。

3）for（i=0；i＜n；i++）

for（j=0；j＜n；j++）

s++；

該程序段基本語句s++；執行次數f（n）=n+n+…+n=n²，時間復雜度T（n）=O（f（n））=O（n²），稱為平方階。

4）for（i=0；i＜n；i++）

for（j=i；j＜n；j++）

s++；

這是一個二重循環，基本語句s++；執行次數為n+（n-1）+（n-2）+…+2+1=n（n+1）/2。

該程序段的語句執行次數是n²數量級，因此時間復雜度T（n）=O（n²）。

5）for（i=1；i＜=n；i=2*i）

s++；

設該程序段基本語句s++的執行次數為f（n），則有2^f（n）≤n，即f（n）≤log₂n，因此該段程序的時間復雜度為O（log₂n），稱為對數階。

數據結構中常用的時間復雜度有以下7個：O（1）常量階、O（n）線性階、O（n²）平方階、O（n³）立方階、O（2ⁿ）指數階、O（log₂n）對數階、O（nlog₂n）二維階。

（3）算法的空間復雜度

算法的存儲空間需求類似于算法的時間復雜度，采用空間復雜度作為算法所需存儲空間的量度，記作：

S（n）=O（f（n））

其中，n為問題的規模。一般情況下，一個程序在機器上執行時，除了需要寄存本身所用的指令、常數、變量和輸入數據以外，還需要一些對數據進行操作的輔助存儲空間。其中對于輸入數據所占的具體存儲量只取決于問題本身，與算法無關，因此只需要分析該算法在實現時所需要的輔助空間單元個數就可以。若算法執行時所需要的輔助空間相對于輸入數據量而言是個常數，則稱這個算法為原地工作，輔助空間為O（1）。

算法執行時間的耗費和所占存儲空間的耗費兩者是矛盾的，難以兼得。即算法執行時間上的節省一定是以增加空間存儲為代價的，反之亦然。不過，就一般情況而言，常常以算法執行時間作為算法優劣的主要衡量指標。