第三章 線性表
線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。
線性表的順序存儲(chǔ)結(jié)構(gòu)：指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：
為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼元素ai+1之間的邏輯關(guān)系室谚，對(duì)于數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身上的信息之外刁标，還需存儲(chǔ)一個(gè)指示其直接后繼的信息。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域址晕，把存儲(chǔ)直接后繼元素位置的域稱為指針域膀懈。指針域中存儲(chǔ)的信息稱為指針或鏈。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)鏡像 稱為結(jié)點(diǎn)（Node）谨垃。
n個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表启搂，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
線性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置稱為頭指針刘陶。最后一個(gè)結(jié)點(diǎn)的指針為空胳赌。
單鏈表的第一個(gè)結(jié)點(diǎn)前一般還有有個(gè)頭結(jié)點(diǎn)，用于存放頭指針匙隔。
頭指針和頭結(jié)點(diǎn)的異同
對(duì)于插入或刪除數(shù)據(jù)越頻繁的操作疑苫，單鏈表的效率優(yōu)勢(shì)就越加明顯。
單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：
結(jié)論:
1.若線性表需要頻繁查找纷责，很少進(jìn)行插入和刪除操作時(shí)捍掺，宜采用順序存儲(chǔ)結(jié)構(gòu)，若需要頻繁插入和刪除時(shí)再膳，宜采用單鏈表結(jié)構(gòu)挺勿。
2.當(dāng)線性表中的元素個(gè)數(shù)變化較大或者根本不知道多大時(shí)，最好用單鏈表結(jié)構(gòu)喂柒，這樣可以不用考慮存儲(chǔ)空間大小問題不瓶。如果事先知道長(zhǎng)度禾嫉，用順序存儲(chǔ)結(jié)構(gòu)效率會(huì)高很多。
用數(shù)組描述的鏈表叫做靜態(tài)鏈表湃番。
將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)吭露，這種頭尾相接的單鏈表稱為單循環(huán)鏈表吠撮，簡(jiǎn)稱循環(huán)鏈表。
雙向鏈表：是在單鏈表的每個(gè)結(jié)點(diǎn)中讲竿，在設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域泥兰。
本章小結(jié)：
