第_章 緒論前言（為什么會有數據結構這門課）計算機主要應用在兩個方面：一個是數值計算，另一個是非數值計算。早期的計算機只能處理數值計算（也就是數學上的運算，特點是計算過程復雜，數據類型相對簡單，數據量較少），這時候人們主要通過程序設計的思想來處理處理問題。隨著計算機滲入生活，人們開始要求計算機參與處理非數值計算（特點是計算過程相對簡單，數據結構相對復雜，數據的組織排列結構從某種意義上決定著非數據計算應用的有效性，數據的組織排列結構成為處理和解決數據處理問題的核心），這時候原來的程序設計以程序為中心的設計過程已經無法滿足大量的非數值計算。急需一門以復雜數據為中心，研究數據的合理組織形式，并設計出基于合理數據組織結構下的高效程序的科學來指導計算機的發展。數據結構就是在這種環境下誕生的。每種數據結構類型都分四個描述層次一一概念層、邏輯層、存儲層、運算實現層。而數據結構往往在邏輯層上為程序抽象出算法，并對算法進行優化。最終推出較優的指導性算法，方便后續的具體程序設計。什么是數據結構數據結構是隨著計算機科學的發展而建立起來的圍繞非數值計算問題的一門科學。準確來說，數據結構就是研究大量數據在計算機中存儲的組織形式，并定義且實現對數據相應的高效運算，以提高計算機的數據處理能力的一門科學。這里的運算主要指的是非公式化的運算，如數據存取、插入、刪除、查找、排序和遍歷等運算。也就是說，數據結構是管信息管理和存儲的，研究怎么存比較好，怎么管理相對比較優化。而這里就涉及到一個問題：信息應該怎么表示，根據程序設計中介紹的思路，要在電腦中寫入一個數據，應該包括它的屬性和它的位置。只要有他的位置和屬性都確定了，那這個數據就完整地被存儲到計算機中了。所以，信息是由信息元素的值及信息元素之間的相互關系（邏輯順序）和信息元素在計算機中的存儲方式（物理順序）共同組成。邏輯結構就是代表了信息本身的屬性，他是與計算機本身無關的“邏輯組織結構”它的構成是由數據的值、數據與數據之間的關聯方式兩個部分組成。而存儲方式則是代表他在計算機的位置，是將具有邏輯組織結構的數據在計算機的存儲介質上如何存放的“物理組織結構”。做好了邏輯和儲存兩方面的處理，信息才真正變成了計算機中的一個數據。同時，根據定義，另一個問題無法忽視，什么高效運算？在我看來，高效運算指的就是算法的優化。因為算法不僅要實現問題的要求，而且，應該是高效地完成。低效的算法無法滿足用戶的需求或根本不能運用于實際。低效的處理算法設計的程序即使運用高速運算的計算機也可能不能滿足用戶的處理要求。數據結構的相關概念信息和數據的區別在哪？信息的意義更加廣泛，他包括了現實中客觀事物的數據集合，而數據則是單單指信息以某一特定符號表示的形式，是計算機加工的對象。也就是說，數據是信息的特有形式，這種形式是為計算機服務的。什么是數據元素？數據元素是數據集合中的個體，是數據組成的基本單位。（強調的是抽象上的不可再分的最小性，并不一定指某一項，這與馬克思眼中抽象的基本粒子的概念有點相似）數據結構中結構有兩種：邏輯結構和物理結構邏輯結構（線性與非線性）邏輯結構描述數據元素與數據元素之間的關聯方式，簡稱為關系，表示的是事物本身的內在聯系。（定義非常好了，一個關系就能說明內涵了。這種抽象的邏輯結構，可以理解成計算機紀錄我們的人際網絡等方面的一個結構就好）其中的線性結構就包括線性表，堆棧和隊列等，他們的共同特點是只能有一個直接前驅元素和一個直接后繼元素。所以他們元素之間的正逆關系都是“一對一”的。關于非線性結構，這個就比較復雜了，我們的生活往往都是由非線性結構形成的。如樹形結構，圖狀或網狀結構。你想想你的家族族譜是不是一個樹形結構？你的人際網絡是不是圖狀的？不敢想象一個只存在線性結構的世界是怎么樣的。在這種非線性結構中，數據元素不一定存在確定的前后次序，甚至是無序的，數據元素之間存在從屬、或互為從屬、或離散關系。如樹型結構中，數據元素之間存在著“一對多”的從屬關系。圖或網狀結構中，數據元素之間存在著“多對多”的互為從屬關系。在純集合結構中，數據元素具有“同屬于一個集合”的關系。物理結構定義:也稱為存儲結構，是邏輯結構的數據元素在計算機的物理存儲空間上地映象（存儲），映象不僅包含數據元素本身，而且包含著數據元素之間的關聯方式，即關系的映象。（這個定義用了什么映像，我覺得太麻煩了。我只能直接上我自己的理解。在我看來，存儲結構就是你前面說的邏輯結構中抽象上的關系和信息本身的內容，要存在計算機中，到底應該怎么存。怎么存才能反映出你本身的內容和原來那種關系，這種關系在計算機物理存儲空間上的體現就是存儲結構，也可以叫做映象（存儲））映象可以分為：順序映象和非順序映象。也可以叫作順序存儲和非順序存儲。順序存儲：是指數據元素在一塊連續地物理存儲空間上存儲，物理存儲空間只用于存放數據元素值本身。這里的順序是空間的連續，這種存儲方式直接把兩個元素的關系（邏輯結構）體現在它們的相對位置關系上。非順序存儲：是指數據元素在物理存儲空間上非連續地存儲，物理存儲空間不僅存放數據元素本身，而且為實現數據元素之間的關聯（邏輯結構），在每個數據元素存儲的相鄰空間中存儲該數據元素關聯的另一個或多個數據元素的起始地址。用非順序存儲，數據元素之間就不一定在物理空間上相鄰了，他們的邏輯關系也不再體現在物理的相鄰上了，而是體現在“指針和鏈接”上。這樣，數據元素的邏輯結構不再被順序的物理結構所局限，通過鏈表的結構，非線性結構得以被計算機存儲。一個數據元素應包含的區域1、 數據域數據域是物理存儲空間中存儲數據元素中數據值的空間。所占用的空間大小（字節數）依實際應用的數據元素中包含的信息量的大小而定。（就是放除了關系之外的那些內在的屬性的地方，如一個人的姓名等）2、 鏈接域鏈接域又稱指針域，是非順序存儲映象時表示數據元素之間關系的地址存儲空間，是額外的空間付出。所占用的空間大小（字節數）一般地與特定計算機的地址表示有關。（說白了就是放地址的地方，在順序存儲結構中，物理上的相鄰就已經反映了邏輯結構，也不需要指針指向下一個或者上一個指針了，自然也不存在鏈接域了。）存儲空間分配問題怎么分配存儲空間，對于順序存儲和非順序存儲，我們應該進行不一樣的對待。對于順序存儲，我們采用靜態存儲空間分配和釋放的方法：一次性獲取足夠的物理存儲結構，用完一次性釋放。對于非順序存儲，我們采用動態存儲空間的分配和釋放方法：用多少分配多少，用和存同時進行（C++中用new函數分配空間）。釋放時某個數據元素空間不使用時，立即釋放。（在C++中要用delete釋放空間，C++不會主動釋放空間，如果你不釋放，就是在制造蠕蟲病毒！！！！）數據類型、抽象數據類型和數據結構數據類型數據類型具體含義是，它描述了一組數據和在這組數據上的操作或運算及其操作或運算的接口。抽象數據類型抽象數據類型是指不涉及數據值的具體表示，只涉及數據值的值域，操作或運算與具體實現無關，只描述操作或運算所滿足的抽象性質的數據類型和接口。算法及算法分析、算法描述定義：算法是非空的、有限的指令序列，遵循它就可以完成某一確定的任務。在我看來，由于一個算法解決一個問題，那么他就是函數的一種非語言抽象化的表述。而計算機運行的程序，則是一個或者多個算法具體化語言化的產物。但程序與算法是有區別的，他們二者是一個多對一的關系。多個程序對應同一算法，一個算法可以通過多種語言來實現。另外，算法必須可終止，但程序不一定，程序可以在無外力的作用下一直執行下去，且可以無輸入和輸出。算法必須要在具體運行細節上進行修飾才能轉化成程序。為了進一步區分程序和算法的區別，以下列出算法的五大特點：1、 有窮性(不是死循環)2、 確定性3、 可行性(算法可行，指在計算機的運行速度的范圍內運算，如果要運行個十多二十年，那么這個算法也就沒有可行的意義了)4、 有輸入5、 有輸出程序性能一個程序的性能的好壞，主要取決于運行這個程序的時間長短和空間占用程度。空間復雜性(空間占用程度)數據的空間復雜性包括指令空間，數據空間和環境棧空間。指令空間就是那個編譯后的文件大小，一般來說，這個無需擔心。而數據空間和環境棧空間才是影響一個程序性能的關鍵。對于數據空間來說，數據元素值占用的空間是考量重點，數據元素值太多，會嚴重占用內存，造成程序運行的緩慢，甚至死機。而環境棧空間中返回地址、局部變量的值、參數的值越多，調用或遞歸的層次越深，所需有環境棧空間就越大，就越容易耗盡環境棧空間，造成性能下降。其中尤其以遞歸函數的影響最嚴重。當然，這一部分的空間是可變部分，只要合理安排好遞歸的結構，盡量錯開同時運行的時間，就可以有效降低對棧空間的消耗。注：環境棧用來保存函數調用和返回時需要的信息的。由于程序是由算法發展而來的。程序性能的好壞，本質上就是反應原算法的效率問題。時間復雜性(時間的長短)根據課本所述，程序在計算機上運算所消耗的時間主要取決于下述因素：程序運行時所需要輸入的數據總量消耗的時間。對源程序進行編譯所需要的時間。計算機執行每條機器指令所需要的時間。程序中關鍵指令重復執行的次數。前三條都是和計算機硬件相關的問題，對總的時間影響不大且不是數據結構主要要討論的問題。但第四個程序中關鍵指令重復執行的次數，對程序性能的影響常常是指數級別的。一個優良的算法指導下寫出的程序和一個普通代碼指導下寫出的程序，最后的時間可能天壤之別。具體來說，時間復雜性大致上可以從兩個方面估算:一是關鍵操作，特別是關鍵的循環、遞歸結構；二是關鍵步驟的執行次數，二者最終決定了時間的長短。附：典型的復雜性函數的表示