數(shù)據(jù)結(jié)構(gòu)和算法02課件13線性表

1、數(shù)據(jù)結(jié)構(gòu)和算法作者：小甲魚(yú)讓編程改變世界Change the world by program單鏈表的整表刪除當(dāng)我們不打算使用這個(gè)單鏈表時(shí)，我們需要把它銷(xiāo)毀（真狠，不要就給別人嘛，還銷(xiāo)毀）。其實(shí)也就是在內(nèi)存中將它釋放掉，以便于留出空間給其他程序或軟件使用。單鏈表整表刪除的算法思路如下：聲明結(jié)點(diǎn)p和q；將第一個(gè)結(jié)點(diǎn)賦值給p，下一結(jié)點(diǎn)賦值給q；循環(huán)執(zhí)行釋放p和將q賦值給p的操作；單鏈表的整表刪除我們說(shuō)好的代碼呢？ClearList.c單鏈表的整表刪除這段算法代碼里，常見(jiàn)的錯(cuò)誤就是有同學(xué)會(huì)覺(jué)得q變量沒(méi)有存在的必要，只需要在循環(huán)體內(nèi)直接寫(xiě)free(p); p = p-next; 即可？可這個(gè)世上沒(méi)有無(wú)

2、緣無(wú)故的愛(ài)，這樣做會(huì)帶來(lái)什么問(wèn)題呢？要知道p是一個(gè)結(jié)點(diǎn)，它除了有數(shù)據(jù)域，還有指針域。當(dāng)我們做free(p);時(shí)候，其實(shí)是對(duì)它整個(gè)結(jié)點(diǎn)進(jìn)行刪除和內(nèi)存釋放的工作。而我們整表刪除是需要一個(gè)個(gè)結(jié)點(diǎn)刪除的，所以我們就需要q來(lái)記載p的下一個(gè)結(jié)點(diǎn)。這就好比*。單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)我們分別從存儲(chǔ)分配方式、時(shí)間性能、空間性能三方面來(lái)做對(duì)比。存儲(chǔ)分配方式：順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的元素。單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)時(shí)間性能：查找順序存儲(chǔ)結(jié)構(gòu)O(1)單鏈表O(n)插入和刪除順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長(zhǎng)一半的元素，時(shí)間

3、為O(n)單鏈表在計(jì)算出某位置的指針后，插入和刪除時(shí)間僅為O(1)單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)空間性能：順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了，容易造成空間浪費(fèi)，分小了，容易發(fā)生溢出。單鏈表不需要分配存儲(chǔ)空間，只要有就可以分配，元素個(gè)數(shù)也不受限制。綜上所述對(duì)比，我們得出一些經(jīng)驗(yàn)性的結(jié)論：若線性表需要頻繁查找，很少進(jìn)行插入和刪除操作時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)。若需要頻繁插入和刪除時(shí)，宜采用單鏈表結(jié)構(gòu)。單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)比如說(shuō)游戲開(kāi)發(fā)中，對(duì)于用戶(hù)注冊(cè)的個(gè)人信息，除了注冊(cè)時(shí)插入數(shù)據(jù)外，絕大多數(shù)情況都是讀取，所以應(yīng)該考慮用順序存儲(chǔ)結(jié)構(gòu)。而游戲中的玩家的武器或者裝備列表，隨著玩家的游戲過(guò)程中，可能會(huì)隨時(shí)增加或刪除，此時(shí)再用順序存儲(chǔ)就不太合適了，單鏈表結(jié)構(gòu)就可以大展拳腳了。當(dāng)線性表中的元素個(gè)數(shù)變化較大或者根本不知道有多大時(shí)，最好用單鏈表結(jié)構(gòu)，這樣可以不需要考慮存儲(chǔ)空間的大小問(wèn)題。單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)而如果事先知道線性表的大致長(zhǎng)度，比如一年12個(gè)月，一周就是星期一至星期日共七天，這種用順序存儲(chǔ)結(jié)構(gòu)效率會(huì)高很多?？傊€性表的順序存儲(chǔ)結(jié)構(gòu)和單鏈表結(jié)構(gòu)各有其優(yōu)缺點(diǎn)，不能簡(jiǎn)單的說(shuō)哪個(gè)好，哪個(gè)不好，需要根據(jù)實(shí)