線性表順序與鏈式存儲的對比分析參考幻燈片

1、線性表順序與鏈式存儲的對比分析,by 熊貓燒香,目錄,01 順序與鏈式存儲的結構對比,一、順序存儲 在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數據元素,稱作線性表的順序存儲結構. 二、鏈式存儲 在計算機中用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續(xù)的,也可以是不連續(xù)的).稱作線性表的鏈式存儲結構.,02 插入算法的對比,順序存儲的插入 (1)不用查找插入位置i，只需要判斷i的合法位置，其范圍是1L.listsize說明線性表滿了，不能進行插入數據元素操作，要增加存儲空間的分量或者作錯誤處理。 (3)將線性表的最后一個數據元素到第i-1個數據元素依次往后移動一個數

2、據單元，空出第i-1個位置的數據單元； (4)把新的數據元素插入到剛才空出來的數據單元中，長度+1.,鏈式存儲結構的插入 (1)鏈式存儲的線性表做插入操作，不判斷線性表是否滿，但是要從頭指針開始，通過循環(huán)語句while(n&ji-1)循環(huán)查找第i-1個節(jié)點。 (2)判斷i的合法性，i的合法范圍是1in,否則就不合法。 (3)申請一個節(jié)點的存儲空間，并用一個指針變量指向這個節(jié)點，把需要插入的數據元素賦值給這個節(jié)點的數據域中。 (4)修改插入數據元素的指針，完成插入操作,03 刪除算法的對比分析,順序存儲的刪除算法 (1)不用查找刪除位置i，也不用另外判斷線性表是否為空，只要取值為1iL.leng

3、th就包括了線性表判空操作和刪除位置的合法性判斷了，否則不合法。 (2)將線性表的第i+1個數據元素到最后一個數據元素依次往前移動一個數據單元，就算刪除了第i個數據元素?？蛇x擇是否保留刪除數據。 (3)線性表長度減1。(雖然最后一個數據元素仍然存在，但已經不是操作中的有用數據了),鏈式存儲的刪除算法 (1)鏈式存儲的線性表做刪除操作前，要從頭指針開始，通過循環(huán)語句while(p-next&ji-1)循環(huán)查找需要刪除的第i個節(jié)點 (2)判斷第i個節(jié)點的合法性，i的合法范圍是1in，否則不和法。 (3)修改刪除數據元素的指針，完成刪除操作 (4)釋放刪除結點的存儲空間。,04 查找算法的對比分析,

4、順序存儲可以根據存儲數據元素要求不同而分成以下幾種算法： (1)順序查找算法，即以遍歷所有元素為目標，與每個數據元素進行比較，若相等則查找成功，若遍歷后仍無相等元素則沒有查找的數據。 (2)折半查找是要求順序存儲和存儲的數據元素有序，查找時把給定的關鍵字與表中的中間位置元素進行比較，若相等就查找成功，若關鍵字比中間位置大，則下次在右半部分查找；反之則下次在左半部分查找，依次重復，直到遍歷所有數據元素也沒有找到與關鍵字相等的數據元素存在，則查找失敗。 (3)索引查找是把順序表(主表)中的數據元素等分成相等的幾部分(子表)，使后一個子表的所有數據元素均大于前一個子表的最大數據元素，并用每一個子表的

5、最大關鍵字建立索引表。進行查找時，將給定關鍵字先與索引表中的關鍵字進行比較，確定此關鍵字屬于哪一個子表，再在這個子表上進行查找。,鏈式存儲查找算法 鏈式存儲可以根據存儲數據元素要求的不同而分成以下幾種鏈表形式的查找算法： (1)單鏈表。只能從頭指針開始，一個結點接著一個結點地順序查找，不能找節(jié)點前驅，只能找結點后繼結點。 (2)循環(huán)鏈表?？梢詮念^指針開始，也可以從尾指針開始順序地查找結點的后繼元素。 (3)雙向鏈表。從頭指針開始順序查找結點，即可以查找結點的前驅元素，也可以查找結點的后繼元素。,05 優(yōu)缺點的對比,順序存儲 優(yōu)點： 1、隨機存取運算便捷。對表中任一結點都可在O(1)時間內直接取得 2、存儲密度大（1），存儲空間利用率高。 缺點： 1、插入和刪除運算不方便，平均要移動表中近一半的結點。信息量較大。 2、由于要求占用連續(xù)的存儲空間，存儲分配只能按最大存儲空間預先進行，可能造成空間浪費。 3、擴充容量需繼續(xù)申請。,鏈式存儲 優(yōu)點： 1、插入、刪除操作很方便，可通過修改結點的指針實現，無須移動元素。 2、方便擴充存儲空間。只要內存空間尚有空閑，就不會產生溢出。 缺點： 1、不能隨機存取元素。 2、存儲密度?。?），存儲空間利用率低,06 小結,1、順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插