線性表順序與鏈?zhǔn)酱鎯Φ膶Ρ确治鰌pt課件

1、線性表順序與鏈?zhǔn)酱鎯Φ膶Ρ确治鼍€性表順序與鏈?zhǔn)酱鎯Φ膶Ρ确治鯾y 熊貓燒香熊貓燒香Page 2目錄目錄順序與鏈?zhǔn)酱鎯Φ臉?gòu)造對比順序與鏈?zhǔn)酱鎯Φ臉?gòu)造對比刪除算法的對比分析刪除算法的對比分析查找算法的對比分析查找算法的對比分析插入算法的對比分析插入算法的對比分析Page 301 順序與鏈?zhǔn)酱鎯Φ臉?gòu)造對比順序與鏈?zhǔn)酱鎯Φ臉?gòu)造對比一、順序存儲一、順序存儲 在計算機(jī)中用一組地址延續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素在計算機(jī)中用一組地址延續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素,稱作線性表的順稱作線性表的順序存儲構(gòu)造序存儲構(gòu)造.二、鏈?zhǔn)酱鎯Χ?、鏈?zhǔn)酱鎯?在計算機(jī)中用一組恣意的存儲單元存儲線性表的數(shù)據(jù)元

2、素在計算機(jī)中用一組恣意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是延續(xù)的這組存儲單元可以是延續(xù)的,也也可以是不延續(xù)的可以是不延續(xù)的). 稱作線性表的鏈?zhǔn)酱鎯?gòu)造稱作線性表的鏈?zhǔn)酱鎯?gòu)造. Page 402 插入算法的對比插入算法的對比n 順序存儲的插入順序存儲的插入n (1) 不用查找插入位置不用查找插入位置i，只需求判別，只需求判別i的合法位置，其范圍的合法位置，其范圍是是1iL.listsize闡明闡明線性表滿了，不能進(jìn)展插入數(shù)據(jù)元素操作，要添加存儲空線性表滿了，不能進(jìn)展插入數(shù)據(jù)元素操作，要添加存儲空間的分量或者作錯誤處置。間的分量或者作錯誤處置。 n (3) 將線性表的最后一個數(shù)據(jù)

3、元素到第將線性表的最后一個數(shù)據(jù)元素到第i-1個數(shù)據(jù)元素依次個數(shù)據(jù)元素依次往后挪動一個數(shù)據(jù)單元，空出第往后挪動一個數(shù)據(jù)單元，空出第i-1個位置的數(shù)據(jù)單元；個位置的數(shù)據(jù)單元； n (4)把新的數(shù)據(jù)元素插入到剛剛空出來的數(shù)據(jù)單元中，長把新的數(shù)據(jù)元素插入到剛剛空出來的數(shù)據(jù)單元中，長度度+1.Page 5n 鏈?zhǔn)酱鎯?gòu)造的插入鏈?zhǔn)酱鎯?gòu)造的插入n (1)鏈?zhǔn)酱鎯Φ木€性表做插入操作，不判別線性表能否滿，鏈?zhǔn)酱鎯Φ木€性表做插入操作，不判別線性表能否滿，但是要從頭指針開場，經(jīng)過循環(huán)語句但是要從頭指針開場，經(jīng)過循環(huán)語句while(n&ji-1)循循環(huán)查找第環(huán)查找第i-1個節(jié)點。個節(jié)點。 n (2)判別判

4、別i的合法性，的合法性，i的合法范圍是的合法范圍是1in,否那么就不合否那么就不合法。法。 n (3)懇求一個節(jié)點的存儲空間，并用一個指針變量指向這懇求一個節(jié)點的存儲空間，并用一個指針變量指向這個節(jié)點，把需求插入的數(shù)據(jù)元素賦值給這個節(jié)點的數(shù)據(jù)域個節(jié)點，把需求插入的數(shù)據(jù)元素賦值給這個節(jié)點的數(shù)據(jù)域中。中。 n (4)修正插入數(shù)據(jù)元素的指針，完成插入操作修正插入數(shù)據(jù)元素的指針，完成插入操作Page 603 刪除算法的對比分析刪除算法的對比分析n 順序存儲的刪除算法順序存儲的刪除算法 n (1)不用查找刪除位置不用查找刪除位置i，也不用另外判別線性表，也不用另外判別線性表能否為空，只需取值為能否為空，

5、只需取值為1inext&ji-1)循環(huán)循環(huán)查找需求刪除的第查找需求刪除的第i個節(jié)點個節(jié)點 n (2)判別第判別第i個節(jié)點的合法性，個節(jié)點的合法性，i的合法范圍是的合法范圍是1in，否那么不和法。否那么不和法。 n (3)修正刪除數(shù)據(jù)元素的指針，完成刪除操作修正刪除數(shù)據(jù)元素的指針，完成刪除操作 n (4)釋放刪除結(jié)點的存儲空間。釋放刪除結(jié)點的存儲空間。Page 804 查找算法的對比分析查找算法的對比分析n 順序存儲可以根據(jù)存儲數(shù)據(jù)元素要求不同而分成以下幾種算法：順序存儲可以根據(jù)存儲數(shù)據(jù)元素要求不同而分成以下幾種算法： n (1)順序查找算法，即以遍歷一切元素為目的，與每個數(shù)據(jù)元素進(jìn)展順

6、序查找算法，即以遍歷一切元素為目的，與每個數(shù)據(jù)元素進(jìn)展比較，假設(shè)相等那么查找勝利，假設(shè)遍歷后仍無相等元素那么沒有查比較，假設(shè)相等那么查找勝利，假設(shè)遍歷后仍無相等元素那么沒有查找的數(shù)據(jù)。找的數(shù)據(jù)。n (2)折半查找是要求順序存儲和存儲的數(shù)據(jù)元素有序，查找時把給定折半查找是要求順序存儲和存儲的數(shù)據(jù)元素有序，查找時把給定的關(guān)鍵字與表中的中間位置元素進(jìn)展比較，假設(shè)相等就查找勝利，假的關(guān)鍵字與表中的中間位置元素進(jìn)展比較，假設(shè)相等就查找勝利，假設(shè)關(guān)鍵字比中間位置大，那么下次在右半部分查找；反之那么下次在設(shè)關(guān)鍵字比中間位置大，那么下次在右半部分查找；反之那么下次在左半部分查找，依次反復(fù)，直到遍歷一切數(shù)據(jù)元素

7、也沒有找到與關(guān)鍵左半部分查找，依次反復(fù)，直到遍歷一切數(shù)據(jù)元素也沒有找到與關(guān)鍵字相等的數(shù)據(jù)元素存在，那么查找失敗。字相等的數(shù)據(jù)元素存在，那么查找失敗。 n (3)索引查找是把順序表索引查找是把順序表(主表主表)中的數(shù)據(jù)元素等分成相等的幾部分中的數(shù)據(jù)元素等分成相等的幾部分(子子表表)，使后一個子表的一切數(shù)據(jù)元素均大于前一個子表的最大數(shù)據(jù)元，使后一個子表的一切數(shù)據(jù)元素均大于前一個子表的最大數(shù)據(jù)元素，并用每一個子表的最大關(guān)鍵字建立索引表。進(jìn)展查找時，將給定素，并用每一個子表的最大關(guān)鍵字建立索引表。進(jìn)展查找時，將給定關(guān)鍵字先與索引表中的關(guān)鍵字進(jìn)展比較，確定此關(guān)鍵字屬于哪一個子關(guān)鍵字先與索引表中的關(guān)鍵字進(jìn)

8、展比較，確定此關(guān)鍵字屬于哪一個子表，再在這個子表上進(jìn)展查找。表，再在這個子表上進(jìn)展查找。Page 9n 鏈?zhǔn)酱鎯Σ檎宜惴ㄦ準(zhǔn)酱鎯Σ檎宜惴?n 鏈?zhǔn)酱鎯梢愿鶕?jù)存儲數(shù)據(jù)元素要求的不同而分鏈?zhǔn)酱鎯梢愿鶕?jù)存儲數(shù)據(jù)元素要求的不同而分成以下幾種鏈表方式的查找算法：成以下幾種鏈表方式的查找算法： n (1)單鏈表。只能從頭指針開場，一個結(jié)點接著一單鏈表。只能從頭指針開場，一個結(jié)點接著一個結(jié)點地順序查找，不能找節(jié)點前驅(qū)，只能找結(jié)個結(jié)點地順序查找，不能找節(jié)點前驅(qū)，只能找結(jié)點后繼結(jié)點。點后繼結(jié)點。 n (2)循環(huán)鏈表?？梢詮念^指針開場，也可以從尾指循環(huán)鏈表。可以從頭指針開場，也可以從尾指針開場順序地查找結(jié)點的

9、后繼元素。針開場順序地查找結(jié)點的后繼元素。 n (3)雙向鏈表。從頭指針開場順序查找結(jié)點，即可雙向鏈表。從頭指針開場順序查找結(jié)點，即可以查找結(jié)點的前驅(qū)元素，也可以查找結(jié)點的后繼以查找結(jié)點的前驅(qū)元素，也可以查找結(jié)點的后繼元素。元素。Page 1005 優(yōu)缺陷的對比優(yōu)缺陷的對比n 順序存儲順序存儲n 優(yōu)點：優(yōu)點： n 1、隨機(jī)存取運(yùn)算便利。對表中任一結(jié)點都可在、隨機(jī)存取運(yùn)算便利。對表中任一結(jié)點都可在O(1)時間時間內(nèi)直接獲得內(nèi)直接獲得 n 2、存儲密度大、存儲密度大1，存儲空間利用率高。，存儲空間利用率高。n 缺陷：缺陷： n 1、 插入和刪除運(yùn)算不方便，平均要挪動表中近一半的結(jié)插入和刪除運(yùn)算不方

10、便，平均要挪動表中近一半的結(jié)點。信息量較大。點。信息量較大。 n 2、 由于要求占用延續(xù)的存儲空間，存儲分配只能按最大由于要求占用延續(xù)的存儲空間，存儲分配只能按最大存儲空間預(yù)先進(jìn)展，能夠呵斥空間浪費(fèi)。存儲空間預(yù)先進(jìn)展，能夠呵斥空間浪費(fèi)。 n 3、 擴(kuò)展容量需繼續(xù)懇求。擴(kuò)展容量需繼續(xù)懇求。Page 11n 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯 優(yōu)點：優(yōu)點： n 1、 插入、刪除操作很方便，可經(jīng)過修正結(jié)點的指針實現(xiàn)，插入、刪除操作很方便，可經(jīng)過修正結(jié)點的指針實現(xiàn)，無須挪動元素。無須挪動元素。n 2、 方便擴(kuò)展存儲空間。只需內(nèi)存空間尚有空閑，就不方便擴(kuò)展存儲空間。只需內(nèi)存空間尚有空閑，就不會產(chǎn)生溢出。會產(chǎn)生溢出。n 缺陷：缺陷： n 1、 不能隨機(jī)存取元素。不能隨機(jī)存取元素。 n 2、 存儲密度小存儲密度小1，存儲空間利用率低，存儲空間利用率低Page 1206 小結(jié)小結(jié)n 1、 順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。入、刪除這樣的動態(tài)操作