數(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ù)進行存儲和加工中反映出來，因此，數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容:數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計算機中的存儲方式、以及在這些數(shù)據(jù)上定義的運算的集合。

　　(1)數(shù)據(jù)的邏輯結(jié)構(gòu)

　　數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。

　　數(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)。

　　2.算法

　　(1)算法及其特征

　　簡單地說，一個算法就是一種解題方法，更嚴格地說，算法是由若干條指令組成的有窮序列，它必須具有以下特征:

　　①有窮性 一個算法必須在執(zhí)行有窮步后結(jié)束。

　?、诖_定性 算法的每一步必須是確切地定義的，無二義性。

　?、劭尚行?算法中的所有待實現(xiàn)的運算必須在原則上能夠由人使用筆和紙在做有窮次運算后完成。

　　④輸入 一個算法具有0個或多個輸入的外界量，它們是算法開始前對算法最初給出的量。

　?、葺敵?一個算法至少產(chǎn)生一個輸出，它們是與輸入有某種關(guān)系的量。

　　算法的含義與程序十分相似，但二者又有區(qū)別。一個程序不一定滿足有窮性，操作系統(tǒng)就是如此，只要整個系統(tǒng)不被破壞，操作系統(tǒng)就永遠不會停止，所以操作系統(tǒng)程序不是一個算法。另外，程序中的指令必須是機器可以執(zhí)行的，而算法中的指令則無此限制。但是，一個算法如果用機器可執(zhí)行的語言書寫，則它就是一個程序。

　　對一個算法的描述可以采用自然語言、數(shù)學(xué)語言、約定的符號語言、以及圖解等方式。

　　(2)算法的分析

　　求解同一個問題可以有多種不同的算法，評價一個算法的優(yōu)劣除了正確性和簡明性外，主要考慮兩點:一是執(zhí)行算法所耗費的時間，二是執(zhí)行算法所耗費的存儲空間，特別是輔助存儲空間的耗費。就這兩者而言，前者顯得比后者更為重要，在數(shù)據(jù)結(jié)構(gòu)中往往更注重對算法執(zhí)行時間的分析。

　　一個算法所耗費的時間是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句執(zhí)行次數(shù)(頻度)與該語句一次執(zhí)行所需時間的乘積。如果假定每條語句一次執(zhí)行所需的時間均為單位時間，則一個算法的時間耗費就是該算法中所有語句的頻度之和。

　　二、線性表

　　(1)線性表及其基本操作

　　線性表是n≥0個元素的一個有限序列:(a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，)表中元素的個數(shù)n稱為表的長度，長度n=0的表稱為空表。表元素又稱為結(jié)點，線性表的一個重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。若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ū);除最后一個元素外，每個元素都有一個且僅有一個直接后繼，下面所列的是其中一些常用的運算。

　?、俨檎疫\算

　　查找線性表的第i(0≤i≤n-1)個表元;

　　在線性表中查找具有給定鍵值的表元;

　?、诓迦脒\算

　　把新表元插在線性表的第i(0≤i≤n)個位置上;

　　把新表元插在具有給定鍵值的表元的前面或后面;

　?、蹌h除運算

　　刪除線性表的第i(0≤i≤n-1)個表元;

　　刪除線性表中具有給定鍵值的表元;

　　④其他運算

　　統(tǒng)計線性表元的個數(shù);

　　輸出線性表各表元的值;

　　復(fù)制線性表;

　　線性表分析;

　　線性表合并;

　　線性表排序;

　　按某種規(guī)則整理線性表。

　　(2)線性表的存儲

　　有多種存儲方式能將線性表存儲在計算機內(nèi)，其中最常用的是順序存儲和鏈接存儲。

　?、倬€性表的順序存儲

　　線性表的順序存儲是最簡單的存儲方式。程序通常用一個足夠大的數(shù)組，從數(shù)組的第一個元素開始，將線性表的結(jié)點依次存儲在數(shù)組中。即線性表的第i個結(jié)點存儲在數(shù)組的第i(0≤i≤n-1)個元素中，用數(shù)組元素的順序存儲來體現(xiàn)線性表中結(jié)點的先后次序關(guān)系。用數(shù)組存儲線性表的最大優(yōu)點是能直接訪問線性表中的任一結(jié)點。

　　用數(shù)組存儲線性表的缺點主要有兩個:一是程序中的數(shù)組通常大小是固定的，可能會與線性表的結(jié)點可以任意增加和減少的要求相矛盾;二是執(zhí)行線性表的結(jié)點插、刪操作時要移動存于數(shù)組中的其他元素，使插和刪操作不夠簡便。

　?、诰€性表的鏈接存儲

　　線性表鏈接存儲是用鏈表存儲線性表，最簡單的用單鏈表。如從鏈表的第一個表元開始，將線性表的結(jié)點依次存儲在鏈表的各表元中。即線性表的第i個結(jié)點存儲在鏈表的第i(0≤i≤n-1)個表元中。鏈表的每個表元除要存儲線性結(jié)點的信息外，還要有一個成分用來存儲其后繼結(jié)點的指針。單鏈表就是通過鏈接指針來體現(xiàn)線性表中結(jié)點的先后次序關(guān)系。每個鏈表還要有一個指向鏈表的第一個表元，鏈表的最末一個表元的后繼指針值為空。用鏈表存儲線性表的優(yōu)點是線性表的每個表元的后繼指針就能完成插或刪的操作，不需移動任何表元。

　　其缺點也主要有兩條:一是每個表元增加了一個后繼指針成分，要花費更多的存儲空間;二是不便隨機地直接訪問線性表的任一結(jié)點。

　　(3)線性表上的查找

　　線性表上的查找運算是指在線性表中找某個鏈值的結(jié)點。根據(jù)線性表的存儲形式和線性表本身的性質(zhì)差異，有多種查找算法，如:順序查找、二分法查找、分塊查找、散列查找等。