第二章考試要點(diǎn)
本章內(nèi)容主要是:數(shù)據(jù)結(jié)構(gòu)、算法的基本概念;線性表邏輯結(jié)構(gòu)，鏈表、數(shù)組的存儲和運(yùn)算;隊列與棧的定義，存儲及應(yīng)用;樹和二叉樹的定義，互相轉(zhuǎn)換，二叉樹的存儲，二叉樹的周游;圖的基本概念，圖的存儲的周游;排序的基本概念與排序算法（選擇排序，插入排序，交換排序，歸并排序）;檢索的基本概念與檢索算法（順序檢索，二分檢索，散列技術(shù)檢索，二叉排序樹）。
以下介紹一些常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們在計算機(jī)中的存儲表示，以及在這些數(shù)據(jù)結(jié)構(gòu)上進(jìn)行的各種運(yùn)算和實(shí)際的執(zhí)行算法，并對算法的效率進(jìn)行簡單的分析。
一、基本概念
1.什么是數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)是描述客觀事物的數(shù)字、字符以及所有能直接輸入到計算機(jī)中并被計算機(jī)程序處理的符號的集合。
數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。通常，一個數(shù)據(jù)對象中的數(shù)據(jù)元素不是孤立的，而是彼此之間存在著一定的聯(lián)系，這種聯(lián)系就是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)對象中數(shù)據(jù)元素之間的聯(lián)系需要在對數(shù)據(jù)進(jìn)行存儲和加工中反映出來，因此，數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容:數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計算機(jī)中的存儲方式、以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。
（1）數(shù)據(jù)的邏輯結(jié)構(gòu)
數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計算機(jī)的。
數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類，線性結(jié)構(gòu)的邏輯特征是:有且僅有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，并且所有的結(jié)點(diǎn)都最多有一個直接前驅(qū)和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是:一個結(jié)點(diǎn)可能有多個直接前驅(qū)和直接后繼。樹、圖等都是非線性結(jié)構(gòu)。 來源：www.examda.com
（2）數(shù)據(jù)的存儲結(jié)構(gòu)
數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器里的實(shí)現(xiàn)（亦稱為映象）。它是依賴于計算機(jī)的，并有四種基本的存儲映象方法。它們是:
①順序存儲方法 該方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰的存儲單元內(nèi)，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。順序存儲方法主要用于線性的數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以**某種線性化方法來實(shí)現(xiàn)順序存儲。
②鏈接存儲方法 在鏈接存儲方法中，邏輯上相鄰的結(jié)點(diǎn)在物理位置上未必相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。
③索引存儲方法 該方法通常是在存儲結(jié)點(diǎn)信息的同時，還建立一個附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是:（關(guān)鍵字，地址）。關(guān)鍵字是能標(biāo)識一個結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。
④散列存儲方法 在散列存儲方法中，結(jié)點(diǎn)的存儲地址是根據(jù)結(jié)點(diǎn)的關(guān)鍵字值直接計算出來的。上述四種基本的存儲方法也可以組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲映象。
（3）數(shù)據(jù)的運(yùn)算
數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上，每種邏輯結(jié)構(gòu)都有一個運(yùn)算的集合。常用的運(yùn)算有:查找、插入、刪除、更新、排序等。顯然，對數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)方法只有在確定了存儲結(jié)構(gòu)之后才能加以考慮。
2.算法
（1）算法及其特征
簡單地說，一個算法就是一種解題方法，更嚴(yán)格地說，算法是由若干條指令組成的有窮序列，它必須具有以下特征:
①有窮性 一個算法必須在執(zhí)行有窮步后結(jié)束。
②確定性 算法的每一步必須是確切地定義的，無二義性。
③可行性 算法中的所有待實(shí)現(xiàn)的運(yùn)算必須在原則上能夠由人使用筆和紙在做有窮次運(yùn)算后完成。
④輸入 一個算法具有0個或多個輸入的外界量，它們是算法開始前對算法最初給出的量。
⑤輸出 一個算法至少產(chǎn)生一個輸出，它們是與輸入有某種關(guān)系的量。
算法的含義與程序十分相似，但二者又有區(qū)別。一個程序不一定滿足有窮性，操作系統(tǒng)就是如此，只要整個系統(tǒng)不被破壞，操作系統(tǒng)就永遠(yuǎn)不會停止，所以操作系統(tǒng)程序不是一個算法。另外，程序中的指令必須是機(jī)器可以執(zhí)行的，而算法中的指令則無此限制。但是，一個算法如果用機(jī)器可執(zhí)行的語言書寫，則它就是一個程序。
對一個算法的描述可以采用自然語言、數(shù)學(xué)語言、約定的符號語言、以及圖解等方式。
（2）算法的分析
求解同一個問題可以有多種不同的算法，評價一個算法的優(yōu)劣除了正確性和簡明性外，主要考慮兩點(diǎn):一是執(zhí)行算法所耗費(fèi)的時間，二是執(zhí)行算法所耗費(fèi)的存儲空間，特別是輔助存儲空間的耗費(fèi)。就這兩者而言，前者顯得比后者更為重要，在數(shù)據(jù)結(jié)構(gòu)中往往更注重對算法執(zhí)行時間的分析。
一個算法所耗費(fèi)的時間是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句執(zhí)行次數(shù)（頻度）與該語句一次執(zhí)行所需時間的乘積。如果假定每條語句一次執(zhí)行所需的時間均為單位時間，則一個算法的時間耗費(fèi)就是該算法中所有語句的頻度之和。
二、線性表
（1）線性表及其基本操作
線性表是n≥0個元素的一個有限序列:（a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，）表中元素的個數(shù)n稱為表的長度，長度n=0的表稱為空表。表元素又稱為結(jié)點(diǎn)，線性表的一個重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。若n≥1，則a 1 ，為第一個元素，a n 為最后一個元素。元素a i-1 先于a i ，我們稱a i-1 為a i 的前驅(qū);a i 在a i-1 之后，a 1 為a i-1 的后繼。除第一個元素外，每個元素都有一個且僅有一個直接前驅(qū);除最后一個元素外，每個元素都有一個且僅有一個直接后繼，下面所列的是其中一些常用的運(yùn)算。
①查找運(yùn)算
查找線性表的第i（0≤i≤n-1）個表元;
在線性表中查找具有給定鍵值的表元;
②插入運(yùn)算
把新表元插在線性表的第i（0≤i≤n）個位置上;
把新表元插在具有給定鍵值的表元的前面或后面;
③刪除運(yùn)算
刪除線性表的第i（0≤i≤n-1）個表元;
刪除線性表中具有給定鍵值的表元;
④其他運(yùn)算
統(tǒng)計線性表元的個數(shù);
輸出線性表各表元的值;
復(fù)制線性表;
線性表分析;
線性表合并;
線性表排序;
按某種規(guī)則整理線性表。
（2）線性表的存儲
有多種存儲方式能將線性表存儲在計算機(jī)內(nèi)，其中最常用的是順序存儲和鏈接存儲。
①線性表的順序存儲
線性表的順序存儲是最簡單的存儲方式。程序通常用一個足夠大的數(shù)組，從數(shù)組的第一個元素開始，將線性表的結(jié)點(diǎn)依次存儲在數(shù)組中。即線性表的第i個結(jié)點(diǎn)存儲在數(shù)組的第i（0≤i≤n-1）個元素中，用數(shù)組元素的順序存儲來體現(xiàn)線性表中結(jié)點(diǎn)的先后次序關(guān)系。用數(shù)組存儲線性表的優(yōu)點(diǎn)是能直接訪問線性表中的任一結(jié)點(diǎn)。
用數(shù)組存儲線性表的缺點(diǎn)主要有兩個:一是程序中的數(shù)組通常大小是固定的，可能會與線性表的結(jié)點(diǎn)可以任意增加和減少的要求相矛盾;二是執(zhí)行線性表的結(jié)點(diǎn)插、刪操作時要移動存于數(shù)組中的其他元素，使插和刪操作不夠簡便。
②線性表的鏈接存儲
線性表鏈接存儲是用鏈表存儲線性表，最簡單的用單鏈表。如從鏈表的第一個表元開始，將線性表的結(jié)點(diǎn)依次存儲在鏈表的各表元中。即線性表的第i個結(jié)點(diǎn)存儲在鏈表的第i（0≤i≤n-1）個表元中。鏈表的每個表元除要存儲線性結(jié)點(diǎn)的信息外，還要有一個成分用來存儲其后繼結(jié)點(diǎn)的指針。單鏈表就是**鏈接指針來體現(xiàn)線性表中結(jié)點(diǎn)的先后次序關(guān)系。每個鏈表還要有一個指向鏈表的第一個表元，鏈表的最末一個表元的后繼指針值為空。用鏈表存儲線性表的優(yōu)點(diǎn)是線性表的每個表元的后繼指針就能完成插或刪的操作，不需移動任何表元。
其缺點(diǎn)也主要有兩條:一是每個表元增加了一個后繼指針成分，要花費(fèi)更多的存儲空間;二是不便隨機(jī)地直接訪問線性表的任一結(jié)點(diǎn)。
（3）線性表上的查找
線性表上的查找運(yùn)算是指在線性表中找某個鏈值的結(jié)點(diǎn)。根據(jù)線性表的存儲形式和線性表本身的性質(zhì)差異，有多種查找算法，如:順序查找、二分法查找、分塊查找、散列查找等。