線性表復(fù)習(xí)知識點(diǎn).doc

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

2、儲密度小，空間單位利用效率低頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個元素結(jié)點(diǎn)）的含義？頭結(jié)點(diǎn)的作用是什么？知識點(diǎn) :頭指針：指向鏈表中第一個結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。頭結(jié)點(diǎn)：鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)。即頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個結(jié)點(diǎn)。 首結(jié)點(diǎn)：鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點(diǎn)。頭指針是指向鏈表中第一個結(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)，都不會改變頭指針的數(shù)值，即算法步驟都相同。； 若設(shè)計(jì)的鏈表中不帶頭結(jié)點(diǎn)，則算法步驟要分別考慮插入或刪除的位置是首元結(jié)點(diǎn)還是其他結(jié)點(diǎn)，因?yàn)閮煞N情況

3、的算法步驟不同。總結(jié)為：頭結(jié)點(diǎn)的作用主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。線性表上定義的基本運(yùn)算：構(gòu)造空表：Initlist （ L） 求表長：Listlength（L ） 取結(jié)點(diǎn)：GetNode（ L， i）查找：LocateNode（ L， x）插入：InsertList（ L， x， i ）刪除：Delete （ L， i）在順序表中實(shí)現(xiàn)的基本運(yùn)算：插入：平均移動結(jié)點(diǎn)次數(shù)為n/2 ；平均時間復(fù)雜度均為O （ n ）。刪除：平均移動結(jié)點(diǎn)次數(shù)為（ n-1 ） /2 ；平均時間復(fù)雜度均為O （ n ）。線性表的

4、鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個結(jié)點(diǎn)值的同時，還存儲了其后繼結(jié)點(diǎn)的地址信息（即指針或鏈）。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)-可編輯修改 -。假定指針p 指向線性鏈表中的第i 個數(shù)據(jù)元素，則p-next為指向線性鏈表中第i+1 個數(shù)據(jù)元素的指針。即p-data為 ai ， p-next-data為 ai+1 。(*p) 表示 p 所指向的結(jié)點(diǎn)(*p).datap-data表示 p 指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).nextp-next表示 p 指向結(jié)點(diǎn)的指針域頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個元素結(jié)點(diǎn)）的含義？頭結(jié)點(diǎn)的作用是什么？知識點(diǎn) :頭指針

5、：指向鏈表中第一個結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。頭結(jié)點(diǎn)：鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)。即頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個結(jié)點(diǎn)。 首結(jié)點(diǎn)：鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點(diǎn)。頭指針是指向鏈表中第一個結(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)，都不會改變頭指針的數(shù)值，即算法步驟都相同。； 若設(shè)計(jì)的鏈表中不帶頭結(jié)點(diǎn)，則算法步驟要分別考慮插入或刪除的位置是首元結(jié)點(diǎn)還是其他結(jié)點(diǎn)，因?yàn)閮煞N情況的算法步驟不同?？偨Y(jié)為：頭結(jié)點(diǎn)的作用主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針