第2章線性表2.1線性表的定義和基本操作2.2線性表的順序存儲結(jié)構(gòu)2.3線性表的鏈式存儲結(jié)構(gòu)本章主要內(nèi)容2.1

線性表的定義和基本操作線性表的定義線性表是由n（n≥0）個的數(shù)據(jù)元素組成的有限序列。L=(a1,a2,...,ai-1,ai,ai+1,...,an)；其中：L為表名，習慣用大寫書寫；ai為該線性表的數(shù)據(jù)元素，習慣用小寫書寫；線性表中數(shù)據(jù)元素的個數(shù)被稱為線性表的長度，當n=0時，稱為空線性表。

線性表特點特點除第一個和最后一個元素外，其他元素都存在唯一的前驅(qū)、后繼關系舉例

La=（34，89，765，12，90，-34，22）數(shù)據(jù)元素類型為I。

Ls=(Hello,World,China,Welcome)數(shù)據(jù)元素類型為C。

2.2線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)指用一組連續(xù)的存儲單元依次存儲線性表中的每個數(shù)據(jù)元素。如右圖所示：說明：L為每個數(shù)據(jù)元素所占據(jù)的存儲單元數(shù)目。順序存儲結(jié)構(gòu)的特點邏輯與物理一致：邏輯上相鄰，物理上也相鄰——利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關系隨機存取：可以利用上述給出的數(shù)學公式，快速地計算出任何一個數(shù)據(jù)元素的存儲地址2.3線性表的鏈式存儲結(jié)構(gòu)線性表順序存儲結(jié)構(gòu)的優(yōu)點：邏輯上相鄰、物理上相鄰，結(jié)構(gòu)簡單可以根據(jù)元素的下標存取，速度便捷

線性表順序存儲結(jié)構(gòu)的缺點：在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用線性表的容量難以擴充為此我們引入線性表的鏈式存儲線性表的鏈式存儲邏輯上相鄰的元素之間的物理位置是通過指針的指向來實現(xiàn)的，這種指向一般是通過的動態(tài)的地址指針來實現(xiàn)的（也可以通過靜態(tài)的偽地址指針來實現(xiàn)）每個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息下頁給出鏈式存儲的內(nèi)存示意圖：headd^

cba線性表鏈式存儲結(jié)構(gòu)示意圖鏈式存儲表示每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點,其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域data；表示直接后繼元素存儲地址的部分被稱為指針或指針域next單鏈表中最后一個結(jié)點沒有直接后繼結(jié)點，它的指針域放入一個特殊的值NULL為了簡化對鏈表的操作，人們經(jīng)常在鏈表的第一個結(jié)點之前附加一個結(jié)點，并稱為頭結(jié)點headd^

cba帶頭結(jié)點的單鏈表結(jié)構(gòu)示意圖鏈式存儲結(jié)構(gòu)的特點線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致通過頭指針進入鏈表，通過結(jié)點的指針域訪問后繼結(jié)點，尋找第一個結(jié)點和尋找最后一個結(jié)點所花費的時間不等，存取方式被為順序存取方式對比順序存儲為隨即存取方式鏈式存儲鏈式存儲的幾種形式單鏈表循環(huán)鏈表雙向鏈表靜態(tài)鏈表首先介紹單鏈表鏈表的每個元素構(gòu)成一個結(jié)點單鏈表的定義單鏈表的邏輯結(jié)構(gòu)示意圖單鏈表的幾種形態(tài)

循環(huán)鏈表循環(huán)鏈表為空的情形特點：