數據對象是具有相同性質的數據元素的集合。通常，一個數據對象中的數據元素不是孤立的，而是彼此之間存在著一定的聯系，這種聯系就是數據結構。數據對象中數據元素之間的聯系需要在對數據進行存儲和加工中反映出來，因此，數據結構概念一般包括三方面的內容:數據之間的邏輯關系、數據在計算機中的存儲方式、以及在這些數據上定義的運算的集合。

　　(1)數據的邏輯結構

　　數據的邏輯結構只抽象地反映數據元素之間的邏輯關系，它與數據的存儲無關，是獨立于計算機的。

　　數據的邏輯結構分為線性結構和非線性結構兩大類，線性結構的邏輯特征是:有且僅有一個開始結點和一個終端結點，并且所有的結點都最多有一個直接前驅和一個直接后繼。線性表就是一個典型的線性結構。非線性結構的邏輯特征是:一個結點可能有多個直接前驅和直接后繼。樹、圖等都是非線性結構。

　　2.算法

　　(1)算法及其特征

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

　　①有窮性 一個算法必須在執行有窮步后結束。

　　②確定性 算法的每一步必須是確切地定義的，無二義性。

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

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

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

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

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

　　(2)算法的分析

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

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

　　二、線性表

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

　　線性表是n≥0個元素的一個有限序列:(a 1 ，a 2 ，a 3 ，…，a n- 1 ，a n ，)表中元素的個數n稱為表的長度，長度n=0的表稱為空表。表元素又稱為結點，線性表的一個重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。若n≥1，則a 1 ，為第一個元素，a n 為最后一個元素。元素a i-1 先于a i ，我們稱a i-1 為a i 的前驅;a i 在a i-1 之后，a 1 為a i-1 的后繼。除第一個元素外，每個元素都有一個且僅有一個直接前驅;除最后一個元素外，每個元素都有一個且僅有一個直接后繼，下面所列的是其中一些常用的運算。

　　①查找運算

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

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

　?、诓迦脒\算

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

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

　　③刪除運算

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

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

　　④其他運算

　　統計線性表元的個數;

　　輸出線性表各表元的值;

　　復制線性表;

　　線性表分析;

　　線性表合并;

　　線性表排序;

　　按某種規則整理線性表。

　　(2)線性表的存儲

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

　　①線性表的順序存儲

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

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

　?、诰€性表的鏈接存儲

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

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

　　(3)線性表上的查找

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