順序表與鏈表的異同點

1、順序表順序表存儲位置是相鄰連續(xù)的，可以隨即訪問的一種數(shù)據(jù)結(jié)構(gòu)，一個順序表在使用前必須指定起長度，一旦分配內(nèi)存，則在使用中不可以動態(tài)的更改。他的優(yōu)點是訪問數(shù)據(jù)是比較方便，可以隨即的訪問表中的任何一個數(shù)據(jù)。 鏈表鏈表是通過指針來描述元素關(guān)系的一種數(shù)據(jù)結(jié)構(gòu)，他可以是物理地址不連續(xù)的物理空間。不能隨即訪問鏈表元素，必須從表頭開始，一步一步搜索元素。它的優(yōu)點是：對于數(shù)組，可以動態(tài)的改變數(shù)據(jù)的長度，分配物理空間。 存儲空間的差異 順序表的存儲空間是靜態(tài)的，要求預(yù)先分配空間，程序執(zhí)行之前必須明確規(guī)定存儲的規(guī)模。（即事先對MAXSIZE要有合適的設(shè)定） 鏈表的存儲空間是動態(tài)分配的，只要是有內(nèi)存空間，就可動態(tài)申

2、請空間，不會產(chǎn)生溢出。因此，當(dāng)線性表的長度變化較大，難以估計其存儲規(guī)模時，以采用動態(tài)鏈表作為存儲結(jié)構(gòu)較好運算時間的差異順序存儲結(jié)構(gòu)是一種隨機存取結(jié)構(gòu)，便于元素的隨機訪問；鏈?zhǔn)浇Y(jié)構(gòu)是一種非隨機存取結(jié)構(gòu)，對任一結(jié)點的操作都必須是從頭指針開始順著鏈掃描才能取得;但是當(dāng)插入、刪除運算較多時，對順序表而言意味著大量數(shù)據(jù)元素的移動，而在鏈表中的任意位置上進(jìn)行插入和刪除，只需修改指針變量值即可 因此對于只進(jìn)行查找的運算而很少做到插入好刪除運算的應(yīng)用，宜采用順序存儲結(jié)構(gòu)；而需要經(jīng)常頻繁地進(jìn)行元素的插入和刪除運算的線性表，應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。程序設(shè)計語言順序表容易實現(xiàn)，在任何高級 語言中都有數(shù)組類型；鏈表的實現(xiàn)

3、要依靠于指針類型，但并不是所有高級語言都能提供指針類型。兩者的優(yōu)點 順序表：順序表： (1)方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。(2) 不用為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲開銷。(3)順序表具有按元素序號隨機訪問的特點。 鏈表鏈表 (1)插入、刪除時，只要找到對應(yīng)前驅(qū)結(jié)點，修改指針即可，無需移動元素； (2)采用動態(tài)存儲分配，不會造成內(nèi)存浪費和溢出。 兩者的缺點順序表順序表 （1）在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低。 （2）需要預(yù)先分配足夠大的存儲空間，估計過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出鏈表鏈表 （1）在有些語言中，不支持指針，不容易實現(xiàn)；