【正文】 第一章 緒 論數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容①數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)關(guān)系之間的邏輯關(guān)系 ②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示 數(shù)據(jù)邏輯結(jié)構(gòu)的種類：集合、線性表、樹和圖的性質(zhì)和特點(diǎn)。v 集合結(jié)構(gòu)中的元素是各自獨(dú)立的，元素之間沒有聯(lián)系v 線性結(jié)構(gòu)中的元素是一個(gè)接一個(gè)串聯(lián)起來的，它有一個(gè)頭元素和一個(gè)尾元素，其余為中間元素；每個(gè)中間元素既有前驅(qū)元素，又有后繼元素v 在樹結(jié)構(gòu)中，樹根結(jié)點(diǎn)只有后繼結(jié)點(diǎn)，而沒有前驅(qū)結(jié)點(diǎn)；除樹根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有唯一一個(gè)前驅(qū)結(jié)點(diǎn)，又稱為是父結(jié)點(diǎn)或雙親結(jié)點(diǎn)v 在圖結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)或稱頂點(diǎn)都可以有任意多個(gè)前驅(qū)結(jié)點(diǎn)和任意多個(gè)后繼結(jié)點(diǎn)。 v 樹結(jié)構(gòu)是圖結(jié)構(gòu)的特例，線性結(jié)構(gòu)是樹結(jié)構(gòu)的特例。為了區(qū)別于線性結(jié)構(gòu)，時(shí)常把樹結(jié)構(gòu)和圖結(jié)構(gòu)稱為非線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的二元組定義，能根據(jù)給出的二元組來判斷數(shù)據(jù)的邏輯結(jié)構(gòu)類型。v 集合結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={ }v 線性結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，B,C，C,D，D,E，E,F，F(xiàn),G}v 樹結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,D，C,E，C,F，D,G}v 圖結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,G，D,G，D,F，C,E，C,F，G,F}了解數(shù)據(jù)的幾種存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）及它們各自的性質(zhì)和特點(diǎn)。（1）順序的方法: 將邏輯上相鄰的元素存儲(chǔ)到物理上相鄰的存儲(chǔ)位置. 常用于線性的數(shù)據(jù)結(jié)構(gòu).（2）鏈?zhǔn)浇Y(jié)構(gòu)：給結(jié)點(diǎn)附加一個(gè)指針字段, 指出其后繼節(jié)點(diǎn)的位置, 即存放結(jié)點(diǎn)的存儲(chǔ)單元分為兩部分:數(shù)據(jù)項(xiàng)指針項(xiàng)（3）散列（hashing) 結(jié)構(gòu)：散列的方法是用結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算出結(jié)點(diǎn)的存儲(chǔ)地址。這個(gè)取值函數(shù)也稱為散列函數(shù)。 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和總的數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系v 邏輯結(jié)構(gòu)相同，但存儲(chǔ)結(jié)構(gòu)不同，則認(rèn)為是不同的數(shù)據(jù)結(jié)構(gòu)。 如順序表和鏈表具有相同的邏輯結(jié)構(gòu)，但存儲(chǔ)結(jié)構(gòu)分別為順序結(jié)構(gòu)和鏈表結(jié)構(gòu)算法的設(shè)計(jì)要求有那些，會(huì)結(jié)合實(shí)際的語言設(shè)計(jì)來說明這些要求1）正確性：對于合法的輸入產(chǎn)生符合要求的輸出；2）可讀性：算法應(yīng)該易讀、便于交流， 這也是保證算法正確性的前提；添加注釋也是一種增加可讀性的辦法；3）健壯性：當(dāng)輸入非法時(shí)， 算法還能做出適當(dāng)?shù)姆磻?yīng)而不會(huì)崩潰， 如輸出錯(cuò)誤信息；算法中應(yīng)該考慮適當(dāng)?shù)腻e(cuò)誤處理；4）效率高且內(nèi)存消耗小：效率高指運(yùn)行時(shí)間短。存儲(chǔ)指算法執(zhí)行過程中所需的最大存儲(chǔ)空間。了解時(shí)間復(fù)雜度的概念、時(shí)間復(fù)雜度的度量、時(shí)間復(fù)雜度的類型，能對實(shí)際的程序分析它的時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度是一個(gè)算法運(yùn)行時(shí)間的相對量度。把算法中包含簡單操作次數(shù)的多少叫做該算法的時(shí)間復(fù)雜度，或者叫做時(shí)間復(fù)雜性，用它來衡量一個(gè)算法的運(yùn)行時(shí)間性能或稱計(jì)算性能v 平均復(fù)雜度(The Average Case)：．v 最壞情況復(fù)雜度 (The Worst Case)：估算最壞情況下時(shí)間復(fù)雜度的一個(gè)上界．這也是通常所指的復(fù)雜度．v 最好復(fù)雜度 (The Best Case):在最理想輸入情況下的時(shí)間復(fù)雜度。第二章 線性表了解并掌握線性表的定義及性質(zhì)線性表是線性結(jié)構(gòu)的一種表現(xiàn)形式，即是具有相同屬性數(shù)據(jù)元素的一個(gè)有限序列，序列中的元素是一個(gè)接一個(gè)在邏輯上是有序的，序列中元素的個(gè)數(shù)就是該線性表的長度.v 存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素v 存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素v 除起點(diǎn)元素之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)v 除終點(diǎn)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼v 起點(diǎn)元素只有后繼沒有前驅(qū)，終點(diǎn)元素只有前驅(qū)沒有后繼 v 對于線性表中的數(shù)據(jù)元素ai1和ai來說，ai1是ai的直接前驅(qū)，ai是ai1的直接后繼。v 所有數(shù)據(jù)元素ai在同一個(gè)線性表中必須是相同的數(shù)據(jù)類型。熟悉順序線性表（順序存儲(chǔ)的線性表）的存儲(chǔ)方式及其表單元（簡單數(shù)據(jù)類型和記錄數(shù)據(jù)類型）的定位和計(jì)算。 線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的，即前驅(qū)元素一定存儲(chǔ)在后繼元素的前面。熟悉順序線性表的插入、刪除和查找的算法思想和程序了解線性表鏈接存儲(chǔ)的結(jié)構(gòu)和特點(diǎn)v 假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。v 在鏈?zhǔn)酱鎯?chǔ)方式中，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域（或稱為信息域）；另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)，從而可以表示數(shù)據(jù)元素之間的邏輯關(guān)系。v 長度可以任意擴(kuò)充，存儲(chǔ)效率較高；v 物理存儲(chǔ)可以是不連續(xù)的；v 數(shù)據(jù)元素的邏輯次序可以與其存儲(chǔ)的物理次序不一致。v 插入、刪除運(yùn)算靈活方便，不需移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可了解單鏈表、雙向鏈表和循環(huán)鏈表的結(jié)構(gòu)和特點(diǎn)通過每個(gè)結(jié)點(diǎn)的指針域?qū)個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的結(jié)點(diǎn)序列我們就稱為鏈表。如果這一鏈表中每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，則稱該鏈表為線性鏈表或單鏈表，否則則稱為雙向鏈表。雙向鏈表是指線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，用以指向其直接前驅(qū)；另一個(gè)稱為右指針，用以指