【正文】 到一組代數(shù)方程或微分方程。然而，更多的問題無法用數(shù)學方程加以描述。下面用一個例子來說明數(shù)據(jù)結構。多叉路口交通燈的管理問題。通常，在十字交叉的路口只要設紅綠兩色的交通燈便可保持正常的交通秩序，而在多叉路口需設幾種顏色的交通燈才能既使車輛相互之間不碰撞而又達到最大的流通呢？假設有如圖A111（a）所示的五叉路，其中C和E為單行道，在路口有13條可行的通路，其中有的可以同時通行，如A→B、和E→C，而有的不可同時通行，如E→B和A→D，那末，在路口應如何設置交通燈進行管理？這個問題可以轉(zhuǎn)換成一個圖的染色問題。假設在圖上以一個圓圈表示一條通路，在不能同時通行的兩個圓圈之間畫一連線，對圖中的圓圈上色，要求同一連線上的兩個圓圈不同色且顏色種類最少。圖A111（b）是與圖A111（a）相應的圖，圖中13個圓圈表示13條通路，圓中的號碼分別表示四種顏色的交通燈。圖11:五叉路口交通管理意圖（a）三叉路口（b）表示通路的圖由以上例子可見，描述這樣一類問題的數(shù)學模型不再是數(shù)值方程，而是諸如表、樹和圖等的非數(shù)值性的數(shù)據(jù)結構。因此，簡單說來，數(shù)據(jù)結構就是一門研究非數(shù)值性程序設計中計算機操作的對象以及它們之間的關系和運算等的學科。3．1．2基本術語下面是數(shù)據(jù)結構中常用到的名詞和術語的含義：1）數(shù)據(jù)（Data）數(shù)據(jù)是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。它是計算機程序加工的“原料”。例如，一個利用數(shù)值分析的方法解代數(shù)方程的程序處理的對象只是整數(shù)和實數(shù)，而一個編譯程序或文字處理程序的對象是字符串。因此，對計算機而言，數(shù)據(jù)的含義極為廣泛，如圖形、聲音等都屬于數(shù)據(jù)的范疇。2）數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位，即數(shù)據(jù)這個集合中的一個個體（客體）。有時一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（data item）組成，數(shù)據(jù)項是數(shù)據(jù)的最小單位。3）數(shù)據(jù)對象（Data Object）是具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)的數(shù)據(jù)對象是集合N＝｛…，2，1，0，1，2，…｝，字母字符的數(shù)據(jù)對象是集合C＝｛A，B，…，Z｝。4）數(shù)據(jù)結構（Data Structure）簡單說來，數(shù)據(jù)結構是帶有結構的數(shù)據(jù)元素的集合。從上述面的例子可以看到，被計算機加工的數(shù)據(jù)元素都不是孤立的，在它們之間存在著某種聯(lián)系，這種相互的關系，通常稱做結構。我們可以從集合論的觀點加以形式化描述。數(shù)據(jù)結構是一個二元組DataStructure＝（D,R）其中：D是數(shù)據(jù)元素的集合，R是D上關系的集合。例如，復數(shù)可被定義為一種數(shù)據(jù)結構:Complex＝（D，R）其中D＝｛x|x是實數(shù)｝R＝｛R1｝R={x，y＞|x，y∈D，x稱為實部，y稱為虛部}由此，由任何一對實數(shù)均可得到一個復數(shù)。在上面對數(shù)據(jù)結構的定義中，R集合中的關系指的是數(shù)據(jù)元素之間的邏輯關系，因此，又稱數(shù)據(jù)的邏輯結構。與此對應，則有數(shù)據(jù)的物理結構，又稱存貯結構，是數(shù)據(jù)結構在計算機中的映象（或表示）。5）數(shù)據(jù)類型（Data Type）是程序設計語言中所允許的變量的種類，換句話說，是變量可能取的值和能作的運算的集合。在每一種程序設計語言中都有一組它所允許的基本數(shù)據(jù)類型。各種語言所能提供變量類型的多少決定了該語言功能的強弱。我們可以把數(shù)據(jù)類型看作是程序設計語言中已經(jīng)實現(xiàn)的數(shù)據(jù)結構，如復數(shù)、數(shù)組等。因此，數(shù)據(jù)類型實際上是數(shù)據(jù)結構（包括邏輯結構和存貯結構）及其運算的總稱?！獦浜蛨D3．2．1樹和二叉樹樹（Tree）是一種重要的非線性結構，在計算機軟件設計中被廣泛使用，如哈夫曼樹可以應用于數(shù)據(jù)壓縮編碼，而B+樹則在文件系統(tǒng)管理中被使用。圖A112表示了樹的示例。圖A112：樹的示例在圖A112中，結點A為樹的根，根的每個分支稱為子樹（Subtree），子樹也是一棵樹；結點子樹的根為結點的孩子（Child），如B、C、D為結點A的孩子，而A為B、C、D的雙親（Parent）；同一個雙親的孩子之間為兄弟（Sibling）關系；沒有孩子的結點為樹的葉子（Leaf），H、F、G、D為樹的葉子。樹的基本操作包括：1）初始化一棵樹；2）得到樹的根；3）得到一個結點的雙親；4）得到一個結點的兄弟；5）得到一個結點的孩子；6）插入子樹；7）刪除子樹；8）遍歷（Travers）樹；9）清空樹。在不同的軟件系統(tǒng)中，由于具體實現(xiàn)的不同樹的操作也不同。二叉樹（Binary Tree）是另一種樹型結構，其特點是每個結點最多有兩棵子樹。樹和二叉樹之間可以相互轉(zhuǎn)換。各種特定的樹型結構被廣泛應用于查找算法的實現(xiàn)中，它們可以加快查找的速度；在地理信息系統(tǒng)中，可以用于空間索引的建立，以提高空間要素的檢索效率。3．2．1圖圖（Graph）是較樹更為復雜的數(shù)據(jù)結構，在圖中，結點之間的關系是任意的，圖中任意兩個數(shù)據(jù)元素都可能相關。圖A113給出了圖的示例。（a）有向圖 （b）無向圖圖A113：圖的示例圖的形式化定義為：Graph = (V,R)其中：V={x|x∈dataobject}R={VR}VR={x,y|P(x,y)∧(x,y∈V)}圖中數(shù)據(jù)元素稱為頂點（Vertex），V是頂點的有窮非空集合；VR是兩個頂點之間的關系的集合，其定義中P(x,y)表示x到y(tǒng)的一條單向通路；若x,y∈VR，則x,y表示從x到y(tǒng)的一條弧，此時圖稱為有向圖（Digraph）；若x,y∈VR必有x,y∈VR，則此時圖稱為無向圖。在圖中，如果x,y∈VR，則x，y互為鄰接點。路徑（Path）是一個頂點序列（V1,V2,…Vn），其中Vi和Vi+1為鄰接點。圖可以有多種存儲結構，其中最普通的是采用鄰接矩陣，如果兩個結點Vi,Vj∈VR，則矩陣對應元素A[i,j]=1，反之，A[i,j]=0。無向圖的鄰接矩陣是對稱的，而有向圖的鄰接矩陣則不一定對稱，圖A113中兩個圖的鄰接矩陣如下（其中沒有考慮相同點鄰接性）：在地理信息系統(tǒng)中，可以應用圖數(shù)據(jù)結構進行網(wǎng)絡分析，判斷兩個空間要素之間的連通性及其最短路徑。3．2．1算法的概念和特性數(shù)據(jù)結構和算法構成了計算機程序，所謂算法（Algorithm），是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每個指令表示一個或者多個操作。一個算法還具有以下五個重要特征：1）有窮性一個算法必須總在執(zhí)行有窮步之后結束，而且每一步都可以在有窮時間內(nèi)完成；2）確定性算法中的每一步必須有明確的含義，不會引起二義性；并且，算法只有唯一的執(zhí)行路徑，即相同的輸入只會得到相同的輸出。3）可行性一個算法必須是可行的，即算法中的操作都是可以通過已有的基本運算完成。4）輸入一個算法可以有零個或者多個的輸入。5）輸出一個算法有一個或者多個的輸出，這些輸出同輸入有特定的關系。3．2．2算法設計的要求 設計一個“好”的算法應該考慮達到以下目標：1）正確性算法應該滿足具體問題的要求，對于輸入數(shù)據(jù)能夠得到符合規(guī)格說明的結果。2）可讀性算法的可讀性有助于人對算法的理解，便于修改和調(diào)試。3）健壯性當輸入數(shù)據(jù)非法時，算法也能夠正確處理，而不會出錯。4）效率與低存儲量需求效率指的是算法執(zhí)行時間，一個算法執(zhí)行時間越少，效率越高；存儲量需求是指算法執(zhí)行過程中所需要的最大存儲空間。一個好算法要有高的執(zhí)行效率和低的存儲量需求，但是在實際實現(xiàn)中，二者并不可以兼得，通?？梢杂么蟮目臻g開銷來提高算法執(zhí)行效率，或者以降低執(zhí)行速度作為減少空間開銷的代價。決定一個算法的效率和存儲需求的因素包括書寫程序的語言、生成的機器代碼的質(zhì)量、機器執(zhí)行指令的速度等等，但最重要的是算法解決問題的規(guī)模。一個算法是由控制結構（順序、分支和循環(huán)三種）和原操作構成，通常是在算法中選取一個基本原操作，并以該操作重復執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記做：T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱為算法的漸近時間復雜度，簡稱時間復雜度(Time Complexity)。常見的算法時間復雜度有O(1)、O(n)、平方階O(n2)、對數(shù)階O(logn)、指數(shù)階O(2n)等等，在算法設計時，可以根據(jù)時間復雜度對算法優(yōu)劣進行評判，通常指數(shù)階的時間復雜度是不可以考慮的。算法執(zhí)行所需要的存儲空間通過空間復雜度來度量，記做：S(n)=O(f(n))其意義類同于時間復雜度