了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素

1、了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ) 結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基 本要求。熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作：查找、插入和刪除的算法。熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn):優(yōu)點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取

2、任一元素存儲(chǔ)空間使用緊湊 缺點(diǎn)插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充 2,3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息結(jié)點(diǎn)數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置口4二找| next (*P)表示P所指向的結(jié)點(diǎn) (*p),data0p-dat感示p指向結(jié)點(diǎn)的數(shù)據(jù)域y 可點(diǎn)。(*p),nextUp-Tiext表示p指向結(jié)點(diǎn)的指針域生成一個(gè)LN仙型新結(jié)點(diǎn)：p=(LinkL誼)碩0函蹤碩LN宓te);系統(tǒng)回收p結(jié)點(diǎn)：free(p)單鏈表特點(diǎn)它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈