數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。
數據元素是數據的基本單位，有時一個數據元素可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。如整數這個集合中，10這個數就可稱是一個數據元素.又比如在一個數據庫(關系式數據庫)中，一個記錄可稱為一個數據元素，而這個元素中的某一字段就是一個數據項。
數據結構的定義雖然沒有標準，但是它包括以下三方面內容：邏輯結構、存儲結構、和對數據的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。
比如一個表(數據庫)，我們就稱它為一個數據結構，它由很多記錄(數據元素)組成，每個元素又包括很多字段(數據項)組成。那么這張表的邏輯結構是怎么樣的呢? 我們分析數據結構都是從結點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關系來分析的，對于這個表中的任一個記錄(結點)，它只有一個直接前趨，只有一個直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結點和一個終端結點，那我們知道了這些關系就能明白這個表的邏輯結構了。
而存儲結構則是指用計算機語言如何表示結點之間的這種關系。如上面的表，在計算機語言中描述為連續存放在一片內存單元中，還是隨機的存放在內存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結構。(注意，在本課程里，我們只在高級語言的層次上討論存儲結構。)
第三個概念就是對數據的運算，比如一張表格，我們需要進行查找，增加，修改，刪除記錄等工作，而怎么樣才能進行這樣的操作呢? 這也就是數據的運算，它不僅僅是加減乘除這些算術運算了，在數據結構中，這些運算常常涉及算法問題。
弄清了以上三個問題，就可以弄清數據結構這個概念。
在順序表中實現的基本運算主要討論了插入和刪除兩種運算。相關的算法我們通過練習掌握。對于順序表的插入和刪除運算，其平均時間復雜度均為O(n)。
--------------------------------------------------------------------------------
線性表的鏈式存儲結構。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結點，這組存儲單元可以分布在內存中任何位置上。因此，鏈表中結點的邏輯次序和物理次序不一定相同。所以為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其后繼結點的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結點結構。
一個單鏈表由頭指針的名字來命名。
對于單鏈表，其操作運算主要有建立單鏈表(頭插法、尾插法和在鏈表開始結點前附加一個頭結點的算法)、查找(按序號和按值)、插入運算、刪除運算等。以上各運算的平均時間復雜度均為O(n).其主要時間是耗費在查找操作上。
--------------------------------------------------------------------------------
循環鏈表是一種首尾相接的鏈表。也就是終端結點的指針域不是指向NULL空而是指向開始結點(也可設置一個頭結點)，形成一個環。采用循環鏈表在實用中多采用尾指針表示單循環鏈表。這樣做的好處是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表了。
判別鏈表終止的條件也不同于單鏈表，它是以指針是否等于某一指定指針如頭指針或尾指針來確定。
--------------------------------------------------------------------------------
雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior,這樣形成的鏈表就有兩條不同方向的鏈。使得從已知結點查找其直接前趨結點可以和查找其直接后繼結點的時間一樣縮短為O(1)。
雙鏈表一般也由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構成雙(向)循環鏈表。
--------------------------------------------------------------------------------
關于順序表和鏈表的比較，請看下表：
具體要求 順序表 鏈表
基于空間 適于線性表長度變化不大，易于事先確定其大小時采用。 適于當線性表長度變化大，難以估計其存儲規模時采用。
基于時間 由于順序表是一種隨機存儲結構，當線性表的操作主要是查找時，宜采用。 鏈表中對任何位置進行插入和刪除都只需修改指針，所以這類操作為主的線性表宜采用鏈表做存儲結構。若插入和刪除主要發生在表的首尾兩端，則宜采用尾指針表示的單循環鏈表。
第二章 線性表習題及答案
--------------------------------------------------------------------------------
一、基礎知識題
(答案及點評) 2.1 試描述頭指針、頭結點、開始結點的區別、并說明頭指針和頭結點的作用。
一、基礎知識題
2.1 答：
開始結點是指鏈表中的第一個結點，也就是沒有直接前趨的那個結點。
鏈表的頭指針是一指向鏈表開始結點的指針(沒有頭結點時)，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。
頭結點是我們人為地在鏈表的開始結點之前附加的一個結點。有了頭結點之后，頭指針指向頭結點，不論鏈表否為空，頭指針總是非空。而且頭指針的設置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結點之后)。
--------------------------------------------------------------------------------
(答案及點評) 2.2 何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜?
2.2 答：
在實際應用中，應根據具體問題的要求和性質來選擇順序表或鏈表作為線性表的存儲結構，通常有以下幾方面的考慮：
1.基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規模時，采用動態鏈表作為存儲結構為好。
2.基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結構為宜；反之， 若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結構。并且，若鏈表的插入和刪除主要發生在表的首尾兩端，則采用尾指針表示的單循環鏈表為宜。
--------------------------------------------------------------------------------
(答案及點評) 2.3 在順序表中插入和刪除一個結點需平均移動多少個結點?具體的移動次數取決于哪兩個因素?
2.3.答：
在等概率情況下，順序表中插入一個結點需平均移動n/2個結點。刪除一個結點需平均移動(n-1)/2個結點。具體的移動次數取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動的結點數越少。
--------------------------------------------------------------------------------
(答案及點評) 2.4 為什么在單循環鏈表中設置尾指針比設置頭指針更好?
2.4. 答：
尾指針是指向終端結點的指針，用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環鏈表，其尾指針為rear，則開始結點和終端結點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。
