數(shù)據(jù)結(jié)構(gòu)課程總結(jié)

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