等級考試三級數(shù)據(jù)庫考點(diǎn)分析：數(shù)據(jù)結(jié)構(gòu)與算法

2．2線性表

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

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

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

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

考點(diǎn)5鏈　表

　　鏈表分為線性鏈表和非線性鏈表二線性鏈表是線性表的鏈?zhǔn)酱鎯Ρ硎�，非線性鏈表是非線性數(shù)據(jù)結(jié)構(gòu)樹和圖的鏈?zhǔn)酱鎯Ρ硎尽?/P>

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

 2、雙鏈表
　　在雙鏈表中，每個節(jié)點(diǎn)中設(shè)置有兩個指針域，分別用以指向其前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。rlink指向節(jié)點(diǎn)的后繼，llink指向節(jié)點(diǎn)的前驅(qū)，這樣的結(jié)構(gòu)方便向后和向前查找。
　�。╨）若要在雙鏈表中刪除指針P所指的節(jié)點(diǎn)時，只需修改其前驅(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字段和原來后繼均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)鏈表插人需要一個新節(jié)點(diǎn)時，就從可利用空間表中刪除第一個節(jié)點(diǎn)，用這個節(jié)點(diǎn)去做鏈表插人；當(dāng)從鏈表中刪除一個節(jié)點(diǎn)時，就把這個節(jié)點(diǎn)插人到可利用空間表的第一個節(jié)點(diǎn)前面。