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

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

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

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

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

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

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

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

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

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