2．2線性表

　　線性表的邏輯結(jié)構(gòu)是由n個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列。線性表中所包含元素的個(gè)數(shù)叫線性表的長(zhǎng)度．它是可變的．可同線性表中增加或刪除元素。線性表包括順序表、鏈表、散列表和串等。

　　線性表的基本運(yùn)算有：置表空、求表長(zhǎng)、讀表元素、插人、刪除及檢索等操作。

考點(diǎn)4　順序表和一維數(shù)組

　　線性表的順序存儲(chǔ)是線性表的一種最簡(jiǎn)單的存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)方法是：在內(nèi)存中為線性表開辟一塊連續(xù)的存儲(chǔ)空間，該存儲(chǔ)空間所包含的存儲(chǔ)單元數(shù)要大于或等于線性表的長(zhǎng)度，讓線性表的第一個(gè)元素存儲(chǔ)在這個(gè)存儲(chǔ)空間的第一個(gè)單元中，第二個(gè)元素存儲(chǔ)在第二個(gè)單元中，其他元素依次類推。一般情況下，若長(zhǎng)度為n的順序表，在任何位置土插入或刪除的概率相等，元素移動(dòng)的平均次數(shù)均為n/2。

考點(diǎn)5鏈　表

　　鏈表分為線性鏈表和非線性鏈表二線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示，非線性鏈表是非線性數(shù)據(jù)結(jié)構(gòu)樹和圖的鏈?zhǔn)酱鎯?chǔ)表示。

1、線性鏈表
　　線性鏈表也稱為單鏈表，其每個(gè)一節(jié)點(diǎn)中只包含一個(gè)指針域。對(duì)鏈表進(jìn)行插人、刪除運(yùn)算時(shí)只需改變節(jié)點(diǎn)中指針域的值。
　�。�1） 在指針一P后插人指針9的關(guān)鍵運(yùn)算步驟：        
q ↑. link：＝P↑．link：
        p ↑. link：＝q；
　　（２）刪除指針P后繼節(jié)點(diǎn)q的關(guān)鍵運(yùn)算步驟：
        q：＝p↑ . link；
        p↑. link：＝q↑．link；
　�。�3）在第一個(gè)節(jié)點(diǎn)（或稱頭節(jié)點(diǎn)）前插人一個(gè)指針P的關(guān)鍵運(yùn)算步驟：
        p↑. link：＝head；
          head：二P；
　　（４）刪除表中頭節(jié)點(diǎn)的關(guān)鍵運(yùn)算步驟：
        head：＝head↑ . link：

 2、雙鏈表
　　在雙鏈表中，每個(gè)節(jié)點(diǎn)中設(shè)置有兩個(gè)指針域，分別用以指向其前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。rlink指向節(jié)點(diǎn)的后繼，llink指向節(jié)點(diǎn)的前驅(qū)，這樣的結(jié)構(gòu)方便向后和向前查找。
　�。╨）若要在雙鏈表中刪除指針P所指的節(jié)點(diǎn)時(shí)，只需修改其前驅(qū)的rlink字段和后繼的Mink字段，步驟如下：
        p↑ . llink↑. rlink：＝p↑. rlink；
        P↑T．rlink↑. llink：＝P↑．llink；
　　 (2)如果要在指針P后面插人指針q所指的新節(jié)點(diǎn)，只需修改P指針?biāo)�指�?jié)點(diǎn)的rlink字段和原來(lái)后繼均Ilink字段，并重新設(shè)置q所指節(jié)點(diǎn)的Mink和rlink值，步驟如下：
        q ↑. Mink：＝P：
        q↑．rlink：＝P↑．rlink;
        P↑．rlink r. Rink：＝q；
        p↑．rlink：＝q;
 
3、可利用空間表
 
　　可利用空間表的作用是管理可用于鏈表插人和刪除的節(jié)點(diǎn)，當(dāng)鏈表插人需要一個(gè)新節(jié)點(diǎn)時(shí)，就從可利用空間表中刪除第一個(gè)節(jié)點(diǎn)，用這個(gè)節(jié)點(diǎn)去做鏈表插人；當(dāng)從鏈表中刪除一個(gè)節(jié)點(diǎn)時(shí)，就把這個(gè)節(jié)點(diǎn)插人到可利用空間表的第一個(gè)節(jié)點(diǎn)前面。