1.資料結構 --- 緒論

資料 : 是對客觀事物的符号表示，在計算機科學中是指所有能輸入到計算機中并被計算機程式處理的符号總稱。它是計算機程式加工的'原料'。
資料元素 : 是資料的基本機關，在計算機程式中通常作為一個整體進行考慮和處理。有時候，一個資料元素可由若幹個資料項組成。
資料對象 : 是性質相同的資料元素的集合，是資料的一個子集。
資料結構 : 是互相之間存在一種或多種特定關系的資料元素的集合。	
	1.集合
	2.線性 (1對1)
	3.樹 (1對多)
	4.圖 (多對多)

資料類型 : 是以資料類型是一個值的集合和定義在這個值集上的一組操作的總稱
抽象資料類型(abstract data type,簡稱ADT) : 是指一個數學模型以及定義在該模型上的一組操作。抽象資料類型的定義取決于它的一組邏輯特性，而與其在計算機内部如何表示實作無關，即不論其内部結構如何變化，隻要它的數學特性不變，都不影響其外部的使用。

算法的5個特性：
	1.有窮性
	2.确定性
	3.可行性
	4.輸入
	5.輸出

算法的要求：
	1.正确性
	2.可讀性
	3.健壯性
	4.效率與低存儲量需求


1.什麼是資料結構
	一般來說，用計算機解決一個具體問題時，大緻需要經過以下幾個步驟：首先要從具體問題抽象出一個适當的數學模型，然後設計一個解此數學模型的算法，最後
  編出程式，進行測試，調整直到得到最終答案。尋求數學模型的實質是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關系，然後用數學的語言
  加以描述。
  具體問題 => 數學模型 => 設計算法 => 編寫程式

    資料結構是一門研究非數值計算的程式設計問題中計算機的操作對象以及它們之間的關系和操作等的學科。
    程式設計的實質是對确定的問題選擇一種好的結構，加上一種好的算法。

2.基本概念和術語
	資料 : 是對客觀事物的符号表示，在計算機科學中是指所有能輸入到計算機中并被計算機程式處理的符号總稱。它是計算機程式加工的'原料'。
	資料元素 : 是資料的基本機關，在計算機程式中通常作為一個整體進行考慮和處理。有時候，一個資料元素可由若幹個資料項組成。
	資料對象 : 是性質相同的資料元素的集合，是資料的一個子集。
	資料結構 : 是互相之間存在一種或多種特定關系的資料元素的集合。

	在任何問題中，資料元素都不是孤立存在的，而是它們之間存在某種關系，這種資料元素之間的關系稱之為結構。根據資料元素之間的不同特性，通常有下列4類
  基本結構：
  	1.集合
  		結構中的資料元素之間除了'同屬于一個集合'的關系外，别無其他關系
  	2.線性結構
  		結構中的資料元素之間存在一個對一個的關系
  	3.樹形結構
  		結構中的資料元素之間存在一個對多個的關系
  	4.圖狀結構或網狀結構
  		結構中的資料元素之間存在多個對多個的關系

  	資料結構的形式定義為：資料結構是一個二進制組 : Data_Structure = (D,S)。其中：D是資料元素的有限集，S是D上關系的有限集。

  	結構定義中的'關系'描述的是資料元素之間的邏輯關系，是以又稱為資料的邏輯結構。然後，讨論資料結構的目的是為了在計算機中實作對它的操作，是以還需要研究
  如何在計算機中表示它。
  	資料結構在計算機中的表示稱為資料的實體結構，又稱為存儲結構。它包含資料元素的表示和關系的表示。在計算機中表示資訊的最小機關是二進制數的一位，叫做位(bit)。
  在計算機中，我們可以用一個由若幹位組合起來形成的一個位串表示一個資料元素(如用一個字長的位串表示一個整數，用8位二進制數表示一個字元等)，通常稱這個位串為元素
  或者結點。當資料元素由若幹資料項組成時，位串對應于各個資料項的子位串稱為資料域。是以，元素或結點可以看成是資料元素在計算機中的映像。
  	資料元素之間的關系在計算機中有兩種不同的表示方法：順序映像和非順序映像，并由此得到兩種不同的存儲結構：順序存儲結構和非順序存儲結構。順序映像的特點是借助元素
  在存儲器中的相對位置來表示資料元素之間的邏輯關系。假如，假設用兩個字長的位串表示一個實數，則可以用位址相鄰的4個字長的位串來表示一個複數；非順序映像的特點是借助
  訓示元素存儲位址的指針表示資料元素之間的邏輯關系，如為表示複數z1的鍊式存儲結構，其中的虛部和實部之間的關系用值為'0415'的指針來表示(0415是虛部的存儲位址)。資料
  的邏輯結構和實體結構是密切相關的兩個方面，任何一個算法的設計取決于標明的資料結構，而算法的實作依賴于采用的存儲結構。

  	資料類型和資料結構密切相關的一個概念，它最早出現在進階程式設計語言中，用以刻畫(程式)操作對象的特性。在用進階語言編寫的程式中，每個變量，常量和表達式都有一個
  它所屬的确定的資料類型。類型明顯或隐式的規定了在程式執行期間變量或表達式所有可能取值的範圍，以及在這些值上允許進行的操作。是以資料類型是一個值的集合和定義在
  這個值集上的一組操作的總稱。例如，C語言中的整型變量，其值集為某個區間上的整數(區間大小依賴于不同的機器)，定義在其上的操作為加，減，乘，除和取模等算數運算。
  	按'值'的不同特性，進階程式語言中的資料類型可分為兩類：一類是非結構的原子類型。原子類型的值是不可分解的，例如C語言中的基本類型(整型，實型，字元型和枚舉類型)，
  指針類型和空類型。另一類是結構類型，結構類型的值是由若幹成分按某種結構組成的，是以是可以分解的，并且它的成分可以是非結構的，也可以是結構的。如數組。
    實際上，在計算機中，資料類型的概念并非局限于進階語言中，每個處理器(包括計算機硬體系統，作業系統，進階語言，資料庫等)都提供了一組原子類型或結構類型。例如，
  一個計算機硬體系統通常包含'位','位元組','字'等原子類型，它們的操作通過計算機設計的一套指令系統直接由電路系統完成，而進階程式語言提供的資料類型，其操作需要通過
  編譯器或解釋器轉換成底層，即彙編語言或機器語言的資料類型來實作。引入'資料類型'的目的，從硬體角度看，是作為解釋計算機記憶體中資訊含義的一種手段，而對使用資料類型
  的使用者來說，實作了資訊的屏蔽，即将一切使用者不必要了解的細節都封裝在類型中。例如，使用者在使用'整數'類型時，既不需要了解'整數'在計算機内部是如何表示的，也不需要知道
  其操作是如何實作的。如'兩整數求和'，程式設計者注重的僅僅是其'數學上求和'的抽象特性，而不是其硬體的'位'操作如何進行。

  	抽象資料類型(abstract data type,簡稱ADT)是指一個數學模型以及定義在該模型上的一組操作。抽象資料類型的定義取決于它的一組邏輯特性，而與其在計算機内部如何表示
  實作無關，即不論其内部結構如何變化，隻要它的數學特性不變，都不影響其外部的使用。
    抽象資料類型和資料類型實質上是一個概念。例如，各個計算機都擁有的'整數'類型是一個抽象資料類型，盡管它們在不同處理器上實作的方法可以不同，但由于其定義的資料特性
  相同，在使用者看來都是相同的。是以，'抽象'的意義在于資料類型的數學抽象特性。

    另一方面，抽象資料類型的範圍更廣，它不再局限于前述各處理器已經定義并實作的資料類型(也可稱為這類資料類型為固有資料類型)，還包括使用者在設計軟體系統時自己定義的
  資料類型。為了提高軟體的複用率，在近代程式設計方法學中指出，一個軟體系統的架構應該建立在資料之上，而不是建立在操作之上(後者是傳統的軟體設計方法所為)。即在構成
  軟體系統的每個相對獨立的子產品上，定義一組資料和施于這些資料上的一組操作，并在子產品内部給出這些資料的表示及其操作細節，而在子產品外部使用的隻是抽象的資料和抽象的操作。
  顯然，所定義的資料類型的抽象層次越高，含有該抽象資料類型的軟體子產品的複用程度也越高。

  	一個含有抽象資料類型的軟體子產品通常包含定義，表示和實作3個部分。
  	如前所述，抽象資料類型的定義由一個值域和定義在該值域上的一組操作組成。若按其值的不同，可細分為3種：
  	1.原子類型 : 屬原子類型的變量的值是不可分解的。這類抽象資料類型較少，因為一般情況下，已有的固有的資料類型足以滿足需求。但有時也有必要定義新的原子資料類型，
    例如，位數為100的整數。
  	2.固定聚合類型 : 屬該類型的變量，其值由确定數目的成分按某種結構組成。例如，複述是由兩個實數依确定的次序關系構成。
  	3.可變聚合類型 : 和固定聚合類型相比，構成可變聚合類型'值'的成分的數目不确定。例如，可定義一個'有序整數序列'的抽象資料類型，其中序列的長度是可變的。

  	顯然，後兩種類型可統稱為結構類型。
  	和資料結構的形式定義相對應，抽象資料類型可用以下三元組表示：
  	(D,S,P)
  	其中，D是資料對象，S是D上的關系集，P是對D的基本操作集。
  	ADT 後續資料類型名 {
  		資料對象 : <資料對象的定義>
  		資料關系 : <資料關系的定義>
  		基本操作 : <基本操作的定義>
  	}ADT 抽象資料類型名
  	其中，資料對象和資料關系的定義用僞代碼描述，基本操作的定義格式為：
  	基本操作名(參數表)
  		初始條件:<初始條件描述>
  		操作結果:<操作結果描述>
  	基本操作有兩種參數：指派參數隻為操作提供輸入值；引用參數以&打頭，除可提供輸入值外，還将傳回操作結果。'初始條件'描述了操作執行之前資料結構和參數應滿足的條件，
  若不滿足，則操作失敗，并傳回相應出錯資訊。'操作結果'說明了操作正常完成之後，資料結構的變化情況和應傳回的結果。若初始條件為空，則省略之。

  	多型資料類型是指其值的成分不确定的資料類型。從抽象資料類型的角度看，具有相同的數學抽象特性，故稱之為多行資料類型。

3.抽象資料類型的表示與實作
	抽象資料類型可以通過固有資料類型來表示和實作，即利用處理器中已存在的資料類型來說明新的結構，用已經實作的操作來組合新的操作。

4.算法和算法分析
	算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；此外，一個算法還具有下列5個重要特性：
	1.有窮性
		一個算法必須總是在執行有窮步之後結束，且每一步都可在有窮時間内完成。
	2.确定性
		算法中每一條指令必須有确切的含義，讀者了解時不會産生二義性。并且，在任何條件下，算法隻有唯一的一條執行路徑，即對于相同的輸入隻能得出相同的輸出。
	3.可行性
		一個算法是可行的，即算法中描述的操作都是可以通過已經實作的基本運算執行有限次來實作的。
	4.輸入
		一個算法有零個或多個的輸入，這些輸入取自于某個特定的對象的集合。
	5.輸出
		一個算法有一個或者多個的輸出，這些輸出是同輸入有着某些特定關系的量。

	算法設計的要求，一個好的算法應該考慮以下目标：
		1.正确性
		2.可讀性
		3.健壯性
		4.效率與低存儲的需求

	算法效率的度量:
		算法執行時間需要通過依據該算法編制的程式在計算機上運作時所消耗的時間來度量。而度量一個程式的執行時間通常有2個方法：
		1.事後統計法
		2.事前分析估算的方法

	一個算法是由控制結構(順序，分支，循環)和原操作(指固有的資料類型的操作)構成的，則算法時間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法
  是，從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作重複執行的次數作為算法的時間度量。
    一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數f(n)，算法的時間度量記作:
    	T(n) = O(f(n))
    它表示随問題規模n的增大，算法執行的時間的增長率和f(n)的增長率相同，稱作算法的漸近時間複雜度，簡稱為時間複雜度。
    顯然，被稱作問題的基本操作的原操作應是其重複執行次數和算法的執行時間成正比的原操作，多數情況下它是最深層循環内的語句中的原操作，它的執行次數和包含它的語句的
  頻度相同。語句的頻度指的是該語句重複執行的次數。
    由于算法的時間複雜度考慮的隻是對于問題規模n的增長率，則在難以精确計算基本操作執行次數的情況下，隻需求出它關于n的增長率即可。

    算法的空間複雜度:
    	S(n) = O(f(n))
    其中，n為問題的規模。一個上機執行的程式除了需要存儲空間來寄存本身所用指令，常數，變量和輸入資料等，也需要一些對資料進行操作的工作單元和存儲一些為實作計算
  所需資訊的輔助空間。