線性表復(fù)習(xí)知識(shí)點(diǎn)(共3頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上線性表的兩種存儲(chǔ)方式（原理，特點(diǎn)、各自的優(yōu)缺點(diǎn)） 知識(shí)點(diǎn)： 順序存儲(chǔ)結(jié)構(gòu)： 原理：使用數(shù)組，數(shù)組把線性表的數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存單位中 特點(diǎn)：線性表中邏輯上相鄰的數(shù)據(jù)元素在物理地址上也相鄰。 優(yōu)點(diǎn)：算法簡單，存儲(chǔ)密度大，空間單位利用效率高 缺點(diǎn)：需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，并且插入和刪除操作時(shí)需要移動(dòng)較多的數(shù)據(jù)元素。（可簡化為：插入或刪除元素時(shí)不方便） 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 原理：把存放數(shù)據(jù)元素的結(jié)點(diǎn)用指針域構(gòu)造成鏈。     

2、     特點(diǎn)：數(shù)據(jù)元素間的邏輯關(guān)系表現(xiàn)在結(jié)點(diǎn)的連接關(guān)系上          優(yōu)點(diǎn)：不需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除操作是不需要移動(dòng)數(shù)據(jù)元素（可簡化為：插入或刪除元素時(shí)很方便，使用靈活。）          缺點(diǎn)：存儲(chǔ)密度小，空間單位利用效率低頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）的含義？頭結(jié)點(diǎn)的作用是什么？ 知識(shí)點(diǎn):&#

3、160;·頭指針：指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。 ·頭結(jié)點(diǎn)：鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)。即頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個(gè)結(jié)點(diǎn)。 ·首結(jié)點(diǎn)：鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。  頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。 若設(shè)計(jì)的鏈表中帶頭結(jié)點(diǎn)，則無論插入或刪除的位置是首元結(jié)點(diǎn)還是其他結(jié)點(diǎn)，都不會(huì)改變頭指針的數(shù)值，即算法步驟都相同。； 若設(shè)計(jì)的鏈表中不帶頭結(jié)點(diǎn)，則算法步驟要分別考慮插入或刪除的位置是首元結(jié)點(diǎn)還是其他結(jié)點(diǎn)，因?yàn)閮煞N情況的算法步驟不同。

4、 總結(jié)為： 頭結(jié)點(diǎn)的作用主要是使插入和刪除等操作統(tǒng)一，在第一個(gè)元素之前插入元素和刪除第一個(gè)結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。線性表上定義的基本運(yùn)算：   ·構(gòu)造空表：Initlist（L）   ·求表長：Listlength（L）   ·取結(jié)點(diǎn)：GetNode（L，i）   ·查找：LocateNode（L，x）   ·插入：InsertList（L，x，

5、i）   ·刪除：Delete（L，i） 在順序表中實(shí)現(xiàn)的基本運(yùn)算：   ·插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為n/2；平均時(shí)間復(fù)雜度均為O（n）。     ·刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為（n-1）/2；平均時(shí)間復(fù)雜度均為O（n）。   線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息（即指針或鏈）。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)假定指針

6、p指向線性鏈表中的第i個(gè)數(shù)據(jù)元素，則p->next為指向線性鏈表中第i+1個(gè)數(shù)據(jù)元素的指針。即p->data為ai， p->next ->data為ai+1。 (*p)表示p所指向的結(jié)點(diǎn) (*p).dataÛp->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域 (*p).nextÛp->next表示p指向結(jié)點(diǎn)的指針域頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）的含義？頭結(jié)點(diǎn)的作用是什么？ 知識(shí)點(diǎn): ·頭指針：指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。 ·頭結(jié)點(diǎn)：鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)。即頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個(gè)結(jié)點(diǎn)。 ·首結(jié)點(diǎn)：鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。  頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。 若設(shè)計(jì)的鏈表中帶頭結(jié)點(diǎn)，則無論插入或刪除的位置是首元結(jié)點(diǎn)還是其他結(jié)點(diǎn)，都不會(huì)改變頭指針的數(shù)值，即算法步驟都相同。； 若設(shè)計(jì)的鏈表中不帶頭結(jié)點(diǎn)，則算法步驟要分別考慮插入或刪除的位置是首元結(jié)點(diǎn)還是其他結(jié)