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

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