一、基本概念
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ù)上定義的運算的集合。
（1）數(shù)據(jù)的邏輯結(jié)構(gòu)
數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機(jī)的。
數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類，線性結(jié)構(gòu)的邏輯特征是:有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有的結(jié)點都最多有一個直接前驅(qū)和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是:一個結(jié)點可能有多個直接前驅(qū)和直接后繼。樹、圖等都是非線性結(jié)構(gòu)。 來源：www.examda.com
（2）數(shù)據(jù)的存儲結(jié)構(gòu)
數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器里的實現(xiàn)（亦稱為映象）。它是依賴于計算機(jī)的，并有四種基本的存儲映象方法。它們是:
①順序存儲方法 該方法是把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元內(nèi)，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。順序存儲方法主要用于線性的數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以**某種線性化方法來實現(xiàn)順序存儲。
②鏈接存儲方法 在鏈接存儲方法中，邏輯上相鄰的結(jié)點在物理位置上未必相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。
③索引存儲方法 該方法通常是在存儲結(jié)點信息的同時，還建立一個附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是:（關(guān)鍵字，地址）。關(guān)鍵字是能標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。
④散列存儲方法 在散列存儲方法中，結(jié)點的存儲地址是根據(jù)結(jié)點的關(guān)鍵字值直接計算出來的。上述四種基本的存儲方法也可以組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲映象。
（3）數(shù)據(jù)的運算
數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上，每種邏輯結(jié)構(gòu)都有一個運算的集合。常用的運算有:查找、插入、刪除、更新、排序等。顯然，對數(shù)據(jù)運算的具體實現(xiàn)方法只有在確定了存儲結(jié)構(gòu)之后才能加以考慮。
2.算法
（1）算法及其特征
簡單地說，一個算法就是一種解題方法，更嚴(yán)格地說，算法是由若干條指令組成的有窮序列，它必須具有以下特征:
①有窮性 一個算法必須在執(zhí)行有窮步后結(jié)束。
②確定性 算法的每一步必須是確切地定義的，無二義性。
③可行性 算法中的所有待實現(xià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)劣除了正確性和簡明性外，主要考慮兩點:一是執(zhí)行算法所耗費的時間，二是執(zhí)行算法所耗費的存儲空間，特別是輔助存儲空間的耗費。就這兩者而言，前者顯得比后者更為重要，在數(shù)據(jù)結(jié)構(gòu)中往往更注重對算法執(zhí)行時間的分析。
一個算法所耗費的時間是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句執(zhí)行次數(shù)（頻度）與該語句一次執(zhí)行所需時間的乘積。如果假定每條語句一次執(zhí)行所需的時間均為單位時間，則一個算法的時間耗費就是該算法中所有語句的頻度之和。