1.1.1 算法與數(shù)據(jù)結(jié)構(gòu)概述

本節(jié)的主要考點集中在算法與數(shù)據(jù)結(jié)構(gòu)的基本概念上，包括算法的基本特征、復(fù)雜度，以及數(shù)據(jù)結(jié)構(gòu)的表示等。

1.算法的概念

算法（Algorithm）是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)得到所要求的輸出的步驟。如果一個算法有缺陷，或不適合某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法完成同樣的任務(wù)可能有不同的時間、空間或效率。

（1）算法的基本特征

1）有窮性（Finiteness）：算法必須能在執(zhí)行有限個步驟之后終止。

2）確定性（Definiteness）：算法的每一步驟必須有確切的定義。

3）輸入項（Input）：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件。

4）輸出項（Output）：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。

5）可行性（Effectiveness）：也稱有效性，算法中執(zhí)行的任何計算步都可以被分解為基本的、可執(zhí)行的操作步，即每個計算步都可以在有限時間內(nèi)完成。

（2）算法的基本要素

算法中對數(shù)據(jù)的運算和操作：每個算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。

計算機可以執(zhí)行的基本操作是以指令的形式描述的。一個計算機系統(tǒng)能執(zhí)行的所有指令的集合，稱為該計算機系統(tǒng)的指令系統(tǒng)。計算機程序就是按解題要求從計算機指令系統(tǒng)中選擇合適的指令所組成的指令序列。在一般的計算機系統(tǒng)中，基本的運算和操作有以下4類。

1）算術(shù)運算：主要包括加、減、乘、除等運算。

2）邏輯運算：主要包括與、或、非等運算。

3）關(guān)系運算：主要包括大于、小于、等于、不等于等運算。

4）數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。

算法的控制結(jié)構(gòu)：一個算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。

（3）算法設(shè)計的基本方法

計算機算法不同于人工處理的方法，下面是工程上常用的幾種算法設(shè)計。在實際應(yīng)用時，各種方法之間往往存在著一定的聯(lián)系。

1）遞推法：遞推法是利用問題本身所具有的一種遞推關(guān)系求解問題的一種方法。它把問題分成若干步，找出相鄰幾步的關(guān)系，從而達到目的。

2）遞歸法：遞歸法指的是一個過程。函數(shù)不斷引用自身，直到引用的對象已知。

3）窮舉搜索法：窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從中找出那些符合要求的候選解作為問題的解。

4）貪婪法：貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎(chǔ)做最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

5）分治法：分治法是把一個復(fù)雜的問題分成兩個或更多相同或相似的子問題，再把子問題分成更小的子問題，直到最后子問題可以簡單地直接求解，原問題的解即子問題的解的合并。

6）動態(tài)規(guī)劃法：動態(tài)規(guī)劃法是一種在數(shù)學(xué)和計算機科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計算機科學(xué)和工程領(lǐng)域。

7）迭代法：迭代法是數(shù)值分析中通過從一個初始估計解出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。

（4）良好的算法設(shè)計的要求

一個良好的算法應(yīng)達到如下目標。

1）正確性（Correctness）：算法的計算結(jié)果必須是正確的。

2）可讀性（Readability）：可讀性好有助于用戶對算法的理解；不易理解的程序容易隱藏較多錯誤，難以調(diào)試和修改。

3）健壯性（Robustness）：當輸入數(shù)據(jù)非法時，算法也能適當?shù)刈龀龇磻?yīng)或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。

4）效率與低存儲量需求：效率指的是程序執(zhí)行時，對于同一個問題如果有多個算法可以解決，執(zhí)行時間短的算法效率高；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。

2.算法的復(fù)雜度

算法復(fù)雜度分為空間復(fù)雜度和時間復(fù)雜度。

（1）算法的時間復(fù)雜度

算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。

（2）算法的空間復(fù)雜度

算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括算法程序所占的存儲空間、輸入的初始數(shù)據(jù)所占的存儲空間，以及算法執(zhí)行中所需要的額外空間。

3.數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)（Data Structure）是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

數(shù)據(jù)（Data）是對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。

數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

在一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在某種關(guān)系（即連續(xù)），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（或直接前驅(qū)與直接后繼關(guān)系）來描述。

一般來說，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述。

（1）數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。所謂結(jié)構(gòu)實際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。

一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面信息：表示數(shù)據(jù)元素的信息和表示各數(shù)據(jù)元素之間的前后件關(guān)系的信息。

數(shù)據(jù)的邏輯結(jié)果是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述。它可以用一個數(shù)據(jù)元素的集合和在此集合中定義的若干關(guān)系來表示。用D表示數(shù)據(jù)元素的集合，用R表示數(shù)據(jù)元素之間的前后件關(guān)系，即一個數(shù)據(jù)結(jié)構(gòu)可以表示為B=（D, R），這是一個二元關(guān)系的表示方式。

（2）數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱為數(shù)據(jù)的物理結(jié)構(gòu)）。

由于數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。

一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等，而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進行數(shù)據(jù)處理時，選擇合適的存儲結(jié)構(gòu)是很重要的。

4.數(shù)據(jù)結(jié)構(gòu)的表示

數(shù)據(jù)結(jié)構(gòu)的表示除了用二元關(guān)系表示外，還可以直觀地用圖形表示。

在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示，一般稱之為數(shù)據(jù)節(jié)點，簡稱為節(jié)點。為了進一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件節(jié)點指向后件節(jié)點。

在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的節(jié)點稱為根節(jié)點；沒有后件的節(jié)點稱為終端節(jié)點（也稱為葉子節(jié)點）。

一個數(shù)據(jù)結(jié)構(gòu)中的節(jié)點可能是在動態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新節(jié)點（稱為插入運算），也可以刪除數(shù)據(jù)結(jié)構(gòu)中的某個節(jié)點（稱為刪除運算）。插入與刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運算。除此之外，對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復(fù)制和修改等。

5.線性結(jié)構(gòu)與非線性結(jié)構(gòu)

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。

線性結(jié)構(gòu)滿足以下條件：

1）有且只有一個根節(jié)點。

2）每一個節(jié)點最多有一個前件，也最多只有一個后件。

如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。如果在一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)結(jié)構(gòu)為空。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。對于空的數(shù)據(jù)結(jié)構(gòu)，如果對該數(shù)據(jù)結(jié)構(gòu)的運算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)。