㈠ 數據結構
何謂數據結構
?
數據結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數據的內部構成，即一個數據由那些成分數據構成，以什麼方式構成，呈什麼結構。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系，而物理上的數據結構反映成分數據在計算機內部的存儲安排。數據結構是數據存在的形式。 數據結構是信息的一種組織方式，其目的是為了提高演算法的效率，它通常與一組演算法的集合相對應，通過這組演算法集合可以對數據結構中的數據進行某種操作。
?
數據結構主要研究什麼？
?
數據結構作為一門學科主要研究數據的各種邏輯結構和存儲結構，以及對數據的各種操作。因此，主要有三個方面的內容：數據的邏輯結構；數據的物理存儲結構；對數據的操作（或演算法）。通常，演算法的
?
設計取決於數據的邏輯結構，演算法的實現取決於數據的物理存儲結構。
?
什麼是數據結構？什麼是邏輯結構和物理結構？
?
數據是指由有限的符號（比如，"0"和"1"，具有其自己的結構、操作、和相應的語義）組成的元素的集合。結構是元素之間的關系的集合。通常來說，一個數據結構DS 可以表示為一個二元組：
?
DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part) 這里D是數據元素的集合（或者是「結點」，可能還含有「數據項」或「數據域」），S是定義在D（或其他集合）上的關系的集合，S = { R | R : D×D×...}，稱之為元素的邏輯結構。 邏輯結構有四種基本類型：集合結構、線性結構、樹狀結構和網路結構。表和樹是最常用的兩種高效數據結構，許多高效的演算法可以用這兩種數據結構來設計實現。表是線性結構的（全序關系），樹(偏序或層次關系)和圖（局部有序(weak/local orders)）是非線性結構。
?
數據結構的物理結構是指邏輯結構的存儲鏡像(image)。數據結構 DS 的物理結構 P對應於從 DS 的數據元素到存儲區M（維護著邏輯結構S）的一個映射：
?
(PD,S) -- > M 存儲器模型：一個存儲器 M 是一系列固定大小的存儲單元，每個單元 U 有一個唯一的地址 A(U)，該地址被連續地編碼。每個單元 U 有一個唯一的後繼單元 U'=succ(U)。 P 的四種基本映射模型：順序（sequential）、鏈接（linked）、索引（indexed）和散列（hashing）映射。
?
因此，我們至少可以得到4×4種可能的物理數據結構：
?
sequential (sets)
linked lists
indexed trees
hash graphs
?
（並不是所有的可能組合都合理）
?
??? 數據結構DS上的操作：所有的定義在DS上的操作在改變數據元素（節點）或節點的域時必須保持DS的邏輯和物理結構。
?
DS上的基本操作：任何其他對DS的高級操作都可以用這些基本操作來實現。最好將DS和他的所有基本操作看作一個整體——稱之為模塊。我們可以進一步將該模塊抽象為數據類型（其中DS的存儲結構被表示為私有成員，基本操作被表示為公共方法），稱之為ADT。作為ADT，堆棧和隊列都是一種特殊的表，他們擁有表的操作的子集。 對於DATs的高級操作可以被設計為（不封裝的）演算法，利用基本操作對DS進行處理。
?
好的和壞的DS：如果一個DS可以通過某種「線性規則」被轉化為線性的DS（例如線性表），則稱它為好的DS。好的DS通常對應於好的（高效的）演算法。這是由計算機的計算能力決定的，因為計算機本質上只能存取邏輯連續的內存單元，因此如何沒有線性化的結構邏輯上是不可計算的。比如對一個圖進行操作，要訪問圖的所有結點，則必須按照某種順序來依次訪問所有節點（要形成一個偏序），必須通過某種方式將圖固有的非線性結構轉化為線性結構才能對圖進行操作。
?
樹是好的DS——它有非常簡單而高效的線性化規則，因此可以利用樹設計出許多非常高效的演算法。樹的實現和使用都很簡單，但可以解決大量特殊的復雜問題，因此樹是實際編程中最重要和最有用的一種數據結構。樹的結構本質上有遞歸的性質——每一個葉節點可以被一棵子樹所替代，反之亦然。實際上，每一種遞歸的結構都可以被轉化為（或等價於）樹形結構。
?
從機器語言到高級語言的抽象
?
我們知道，演算法被定義為一個運算序列。這個運算序列中的所有運算定義在一類特定的數據模型上，並以解決一類特定問題為目標。這個運算序列應該具備下列四個特徵。 有限性，即序列的項數有限，且每一運算項都可在有限的時間內完成;確定性，即序列的每一項運算都有明確的定義，無二義性;可以沒有輸入運算項，但一定要有輸出運算項;可行性，即對於任意給定的合法的輸入都能得到相應的正確的輸出。這些特徵可以用來判別一個確定的運算序列是否稱得上是一個演算法。 但是，我們現在的問題不是要判別一個確定的運算序列是否稱得上是一個演算法，而是要對一個己經稱得上是演算法的運算序列，回顧我們曾經如何用程序設計語言去表達它。
?
演算法的程序表達，歸根到底是演算法要素的程序表達，因為一旦演算法的每一項要素都用程序清楚地表達，整個演算法的程序表達也就不成問題。
?
作為運算序列的演算法，有三個要素。 作為運算序列中各種運算的運算對象和運算結果的數據;運算序列中的各種運算;運算序列中的控制轉移。這三種要素依序分別簡稱為數據、運算和控制。 由於演算法層出不窮，變化萬千，其中的運算所作用的對象數據和所得到的結果數據名目繁多，不勝枚舉。最簡單最基本的有布爾值數據、字元數據、整數和實數數據等;稍復雜的有向量、矩陣、記錄等數據;更復雜的有集合、樹和圖，還有聲音、圖形、圖像等數據。 同樣由於演算法層出不窮，變化萬千，其中運算的種類五花八門、多姿多彩。最基本最初等的有賦值運算、算術運算、邏輯運算和關系運算等;稍復雜的有算術表達式和邏輯表達式等;更復雜的有函數值計算、向量運算、矩陣運算、集合運算，以及表、棧、隊列、樹和圖上的運算等:此外，還可能有以上列舉的運算的復合和嵌套。 關於控制轉移，相對單純。在串列計算中，它只有順序、分支、循環、遞歸和無條件轉移等幾種。
?
我們來回顧一下，自從計算機問世以來，演算法的上述三要素的程序表達，經歷過一個怎樣的過程。
?
最早的程序設計語言是機器語言，即具體的計算機上的一個指令集。當時，要在計算機上運行的所有演算法都必須直接用機器語言來表達，計算機才能接受。演算法的運算序列包括運算對象和運算結果都必須轉換為指令序列。其中的每一條指令都以編碼(指令碼和地址碼)的形式出現。與演算法語言表達的演算法，相差十萬八千里。對於沒受過程序設計專門訓練的人來說，一份程序恰似一份"天書"，讓人看了不知所雲，可讀性
?
極差。
?
用機器語言表達演算法的運算、數據和控制十分繁雜瑣碎，因為機器語言所提供的指令太初等、原始。機器語言只接受算術運算、按位邏輯運算和數的大小比較運算等。對於稍復雜的運算，都必須一一分解，直到到達最初等的運算才能用相應的指令替代之。機器語言能直接表達的數據只有最原始的位、位元組、和字三種。演算法中即使是最簡單的數據如布爾值、字元、整數、和實數，也必須一一地映射到位、位元組和字
中，還得一一分配它們的存儲單元。對於演算法中有結構的數據的表達則要麻煩得多。機器語言所提供的控制轉移指令也只有無條件轉移、條件轉移、進入子程序和從子程序返回等最基本的幾種。用它們來構造循環、形成分支、調用函數和過程得事先做許多的准備，還得靠許多的技巧。 直接用機器語言表達演算法有許多缺點。
?
大量繁雜瑣碎的細節牽制著程序員，使他們不可能有更多的時間和精力去從事創造性的勞動，執行對他們來說更為重要的任務。如確保程序的正確性、高效性。程序員既要駕馭程序設計的全局又要深入每一個局部直到實現的細節，即使智力超群的程序員也常常會顧此失彼，屢出差錯，因而所編出的程序可靠性差，且開發周期長。 由於用機器語言進行程序設計的思維和表達方式與人們的習慣大相徑庭，只有經過
較長時間職業訓練的程序員才能勝任，使得程序設計曲高和寡。因為它的書面形式全是"密"碼，所以可讀性差，不便於交流與合作。因為它嚴重地依賴於具體的計算機，所以可移植性差，重用性差。這些弊端造成當時的計算機應用未能迅速得到推廣。
?
克服上述缺點的出路在於程序設計語言的抽象，讓它盡可能地接近於演算法語言。 為此，人們首先注意到的是可讀性和可移植性，因為它們相對地容易通過抽象而得到改善。於是，很快就出現匯編語言。這種語言對機器語言的抽象，首先表現在將機器語言的每一條指令符號化:指令碼代之以記憶符號，地址碼代之以符號地址，使得其含義顯現在符號上而不再隱藏在編碼中，可讓人望"文"生義。其次表現在這種語言擺脫了具體計算機的限制，可在不同指令集的計算機上運行，只要該計算機配上匯編語言的一個匯編程序。這無疑是機器語言朝演算法語言靠攏邁出的一步。但是，它離演算法語言還太遠，以致程序員還不能從分解演算法的數據、運算和控制到匯編才能直接表達的指令等繁雜瑣碎的事務中解脫出來。 到了50年代中期，出現程序設計的高級語言如Fortran，Algol60，以及後來的PL/l， Pascal等，演算法的程序表達才產生一次大的飛躍。
?
誠然，演算法最終要表達為具體計算機上的機器語言才能在該計算機上運行，得到所需要的結果。但匯編語言的實踐啟發人們，表達成機器語言不必一步到位，可以分兩步走或者可以築橋過河。即先表達成一種中介語言，然後轉成機器語言。匯編語言作為一種中介語言，並沒有獲得很大成功，原因是它離演算法語
?
言還太遠。這便指引人們去設計一種盡量接近演算法語言的規范語言，即所謂的高級語言，讓程序員可以用它方便地表達演算法，然後藉助於規范的高級語言到規范的機器語言的"翻譯"，最終將演算法表達為機器語言。而且，由於高級語言和機器語言都具有規范性，這里的"翻譯"完全可以機械化地由計算機來完成，就像匯編語言被翻譯成機器語言一樣，只要計算機配上一個編譯程序。 上述兩步，前一步由程序員去完成，後一步可以由編譯程序去完成。在規定清楚它們各自該做什麼之後，這兩步是完全獨立的。它們各自該如何做互不相干。前一步要做的只是用高級語言正確地表達給定的演算法，產生一個高級語言程序;後一步要做的只是將第一步得到的高級語言程序翻譯成機器語言程序。至於程序員如何用高級語言表達演算法和編譯程序如何將高級語言表達的演算法翻譯成機器語言表達的演算法，顯然毫不相干。
?
處理從演算法語言最終表達成機器語言這一復雜過程的上述思想方法就是一種抽象。匯編語言和高級語言的出現都是這種抽象的範例。 與匯編語言相比，高級語言的巨大成功在於它在數據、運算和控制三方
?
面的表達中引入許多接近演算法語言的概念和工具，大大地提高抽象地表達演算法的能力。 在運算方面，高級語言如Pascal，除允許原封不動地運用演算法語言的四則運算、邏輯運算、關系運算、算術表達式、邏輯表達式外，還引入強有力的函數與過程的工具，並讓用戶自定義。這一工具的重要性不僅在於它精簡了重復的程序文本段，而且在於它反映出程序的兩級抽象。
?
在函數與過程調用級，人們只關心它能做什麼，不必關心它如何做。只是到函數與過程的定義時，人們才給出如何做的細節。用過高級語言的讀者都知道，一旦函數與過程的名稱、參數和功能被規定清楚，那麼，在程序中調用它們便與在程序的頭部說明它們完全分開。你可以修改甚至更換函數體與過程體，而不影響它們的被調用。如果把函數與過程名看成是運算名，把參數看成是運算的對象或運算的結果，那麼
?
，函數與過程的調用和初等運算的引用沒有兩樣。利用函數和過程以及它們的復合或嵌套可以很自然地表達演算法語言中任何復雜的運算。
?
在數據方面，高級語言如Pascal引人了數據類型的概念，即把所有的數據加以分類。每一個數據(包括表達式)或每一個數據變數都屬於其中確定的一類。稱這一類數據為一個數據類型。 因此，數據類型是數據或數據變數類屬的說明，它指示該數據或數據變數可能取的值的全體。對於無結構的數據，高級語言如Pascal，除提供標準的基本數據類型--布爾型、字元型、整型和實型外，還提供用戶可自定義的枚舉類、子界類型和指針類型。這些類型(除指針外)，其使用方式都順應人們在演算法語言中使用的習慣。對於有結構的數據，高級語言如Pascal，提供了數組、記錄、有限制的集合和文件等四種標準的結構數據類型。其中，數組是科學計算中的向量、矩陣的抽象;記錄是商業和管理中的記錄的抽象;有限制的集合是數學中足夠小的集合的勢集的抽象;文件是諸如磁碟等外存儲數據的抽象。
?
人們可以利用所提供的基本數據類型(包括標準的和自定義的)，按數組、記錄、有限制的集合和文件的構造規則構造有結構的數據。 此外，還允許用戶利用標準的結構數據類型，通過復合或嵌套構造更復雜更高層的結構數據。這使得高級語言中的數據類型呈明顯的分層。 高級語言中數據類型的分層是沒有窮盡的，因而用它們可以表達演算法語言中任何復雜層次的數據。 在控制方面，高級語言如Pascal，提供了表達演算法控制轉移的六種方式。
?
(1)預設的順序控制";"。
?
(2)條件(分支)控制:"if表達式(為真)then S1 else S2;" 。
?
(3)選擇(情況)控制:
?
"Case 表達式 of
?
值1: S1
值2: S2
...
值n: Sn
end"
?
(4)循環控制:
?
"while 表達式(為真) do S;" 或
"repeat S until 表達式(為真);" 或
"for變數名:=初值 to/downto 終值do S;"
?
(5)函數和過程的調用，包括遞歸函數和遞歸過程的調用。
?
(6)無條件轉移goto。
這六種表達方式不僅覆蓋了演算法語言中所有控製表達的要求，而且不再像機器語言或匯編語言那樣原始、那樣繁瑣、那樣隱晦，而是如上面所看到的，與自然語言的表達相差無幾。 程序設計語言從機器語言到高級語言的抽象，帶來的主要好處是： 高級語言接近演算法語言，易學、易掌握，一般工程技術人員只要幾周時間的培訓就可以勝任程序員的工作；高級語言為程序員提供了結構化程序設計的環境和工具，使得設計出來的程序可讀性好，可維護性強，可靠性高；高級語言遠離機器語言，與具體的計算機硬體關系不大，因而所寫出來的程序可移植性好，重用率高； 由於把繁雜瑣碎的事務交給了編譯程序去做，所以自動化程度高，開發周期短，且程、序員得到解脫，可以集中時間和精力去從事對於他們來說更為重要的創造性勞動，以提高、程序的質量。
?
數據結構、數據類型和抽象數據類型
?
數據結構、數據類型和抽象數據類型，這三個術語在字面上既不同又相近，反映出它們在含義上既有區別又有聯系。
?
數據結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數據的內部構成，即一個數據由哪些成分數據構成，以什麼方式構成，呈什麼結構。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系，物理上的數據結構反映成分數據在計算機內的存儲安排。數據結構是數據存在的形式。
?
數據是按照數據結構分類的，具有相同數據結構的數據屬同一類。同一類數據的全體稱為一個數據類型。在程序設計高級語言中，數據類型用來說明一個數據在數據分類中的歸屬。它是數據的一種屬性。這個屬性限定了該數據的變化范圍。為了解題的需要，根據數據結構的種類，高級語言定義了一系列的數據類型。不同的高級語言所定義的數據類型不盡相同。Pascal語言所定義的數據類型的種類。
?
其中，簡單數據類型對應於簡單的數據結構;構造數據類型對應於復雜的數據結構;在復雜的數據結構里，允許成分數據本身具有復雜的數據結構，因而，構造數據類型允許復合嵌套;指針類型對應於數據結構中成分數據之間的關系，表面上屬簡單數據類型，實際上都指向復雜的成分數據即構造數據類型中的數據，因此這里沒有把它劃入簡單數據類型，也沒有劃入構造數據類型，而單獨劃出一類。
?
數據結構反映數據內部的構成方式，它常常用一個結構圖來描述:數據中的每一項成分數據被看作一個結點，並用方框或圓圈表示，成分數據之間的關系用相應的結點之間帶箭號的連線表示。如果成分數據本身又有它自身的結構，則結構出現嵌套。這里嵌套還允許是遞歸的嵌套。
?
由於指針數據的引入，使構造各種復雜的數據結構成為可能。按數據結構中的成分數據之間的關系，數據結構有線性與非線性之分。在非線性數據結構中又有層次與網狀之分。 由於數據類型是按照數據結構劃分的，因此，一類數據結構對應著一種數據類型。數據類型按照該類型中的數據所呈現的結構也有線性與非線性之分，層次與網狀之分。一個數據變數，在高級語言中的類型說明必須是讀變數所具有的數據結構所對應的數據類型。最常用的數據結構是數組結構和記錄結構。數組結構的特點是：
?
成分數據的個數固定，它們之間的邏輯關系由成分數據的序號(或叫數組的下標)來體現。這些成分數據按照序號的先後順序一個挨一個地排列起來。每一個成分數據具有相同的結構(可以是簡單結構，也可以是復雜結構)，因而屬於同一個數據類型(相應地是簡單數據類型或構造數據類型)。這種同一的數據類型稱為基類型。所有的成分數據被依序安排在一片連續的存儲單元中。 概括起來，數組結構是一個線性的、均勻的、其成分數據可隨機訪問的結構。
?
由於這、種結構有這些良好的特性，所以最常被人們所採用。在高級語言中，與數組結構相對應的、數據類型是數組類型，即數組結構的數據變數必須說明為array [i] of T0 ，其中i是數組、結構的下標類型，而T0是數組結構的基類型。 記錄結構是另一種常用的數據結構。它的特點是:與數組結構一樣，成分數據的個數固定。但成分數據之間沒有自然序，它們處於平等地位。每一個成分數據被稱為一個域並賦予域名。不同的域有不同的域名。不同的域允許有不同的結構，因而允許屬於不同的數據類型。與數組結構一樣，它們可以隨機訪問，但訪問的途徑靠的是域名。在高級語言中記錄結構對應的數據類型是記錄類型。記錄結構的數據的變數必須說明為記錄類型。
?
抽象數據類型的含義在上一段已作了專門敘述。它可理解為數據類型的進一步抽象。即把數據類型和數據類型上的運算捆在一起，進行封裝。引入抽象數據類型的目的是把數據類型的表示和數據類型上運算的實現與這些數據類型和運算在程序中的引用隔開，使它們相互獨立。對於抽象數據類型的描述，除了必須描述它的數據結構外，還必須描述定義在它上面的運算(過程或函數)。抽象數據類型上定義的過程和函
數以該抽象數據類型的數據所應具有的數據結構為基礎。
?
泛型設計和數據結構與演算法
?
下面我想再說說關於泛型程序設計模型對於數據結構和演算法方面的最新推動，泛型思想已經把數據結
?
構和演算法方面的基本思想抽象到了一個前所未有的高度，現在有多種程序設計語言支持泛型設計，比如
ADA，C++，而且據說在JAVA的下一版本和C#中也將對泛型設計進行全面的支持。
?
先說說泛型設計的基本思想：泛型編程（generic programming，以下直接以GP稱呼）是一種全新的程序設計思想，和OO，OB，PO這些為人所熟知的程序設計想法不同的是GP抽象度更高，基於GP設計的組件之間偶合度底，沒有繼承關系，所以其組件間的互交性和擴展性都非常高。我們都知道，任何演算法都是作用在一種特定的數據結構上的，最簡單的例子就是快速排序演算法最根本的實現條件就是所排序的對象是存
貯在數組裡面，因為快速排序就是因為要用到數組的隨機存儲特性，即可以在單位時間內交換遠距離的對象，而不只是相臨的兩個對象，而如果用聯表去存儲對象，由於在聯表中取得對象的時間是線性的既O[n]，這樣將使快速排序失去其快速的特點。也就是說，我們在設計一種演算法的時候，我們總是先要考慮其應用的數據結構，比如數組查找，聯表查找，樹查找，圖查找其核心都是查找，但因為作用的數據結構不同
?
將有多種不同的表現形式。數據結構和演算法之間這樣密切的關系一直是我們以前的認識。泛型設計的根本思想就是想把演算法和其作用的數據結構分離，也就是說，我們設計演算法的時候並不去考慮我們設計的演算法將作用於何種數據結構之上。泛型設計的理想狀態是一個查找演算法將可以作用於數組，聯表，樹，圖等各種數據結構之上，變成一個通用的，泛型的演算法。這樣的理想是不是很誘惑人？
?
泛型編程帶來的是前所未有的彈性以及不會損失效率的抽象性，GP和OO不同，它不要求你通過額外的間接層來調用函數：它讓你撰寫完全一般化並可重復使用的演算法，其效率與針對特定數據結構而設計的演算法旗鼓相當。我們大家都知道數據結構在C++中可以用用戶定義類型來表示，而C++中的模板技術就是以類型作為參數，那麼我可以想像利用模板技術可以實現我們開始的GP思想，即一個模板函數可以對於各種傳遞進來的類型起作用，而這些類型就可以是我們定義的各種數據結構。
?
泛型演算法抽離於特定類型和特定數據結構之外，使得其適應與盡可能的一般化類型，演算法本身只是為了實現演算法其需要表達的邏輯本質而不去被為各種數據結構的實現細節所干擾。這意味著一個泛型演算法實際具有兩部分。1，用來描敘演算法本質邏輯的實際指令；2，正確指定其參數類型必須滿足的性質的一組需求條件。到此，相信有不少人已經開始糊塗了，呵呵，不要緊。畢竟GP是一種抽象度非常高的程序設計思想，裡面的核心就是抽象條件成為成為程序設計過程中的核心，從而取代了類型這在OO裡面的核心地位，正是因為類型不在是我們考慮的重點，類型成為了抽象條件的外衣，所以我們稱這樣的程序思想為泛型思想------把類型泛化。