次課-鏈表結(jié)點(diǎn)的插入和刪除.ppt

1、,首頁(yè),同學(xué)們加油,教案,主要內(nèi)容,單鏈表中結(jié)點(diǎn)插入算法實(shí)現(xiàn) 單鏈表中結(jié)點(diǎn)插入舉例 單鏈表中結(jié)點(diǎn)刪除算法實(shí)現(xiàn) 單鏈表中結(jié)點(diǎn)刪除舉例,鏈表結(jié)點(diǎn)的插入,在鏈表中插入結(jié)點(diǎn)有很多情況。 下面以帶附加頭結(jié)點(diǎn)的單鏈表為例進(jìn)行介紹。,單鏈表結(jié)點(diǎn)的插入（1）,在指定結(jié)點(diǎn)的后面插入新結(jié)點(diǎn) 插入過(guò)程圖示（在p結(jié)點(diǎn)后面插入新結(jié)點(diǎn)q）：,實(shí)現(xiàn)語(yǔ)句： q-next = p-next; p-next = q;,單鏈表結(jié)點(diǎn)的插入（2）,在指定結(jié)點(diǎn)的前面插入新結(jié)點(diǎn) 在p結(jié)點(diǎn)前面插入新結(jié)點(diǎn)q的步驟： （1）尋找p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，使s指向它。 （2）在s結(jié)點(diǎn)的后面插入q結(jié)點(diǎn)。 實(shí)現(xiàn)語(yǔ)句： s=head; while (s-nex

2、t!=p) s=s-next; q-next = s-next; s-next = q;,單鏈表結(jié)點(diǎn)的插入（3）,在值為x的結(jié)點(diǎn)后插入一個(gè)值為y的結(jié)點(diǎn) 步驟： （1）申請(qǐng)一個(gè)結(jié)點(diǎn)空間，用q指向它，并把y放入其中。 （2）在鏈表中查找值為x的結(jié)點(diǎn)，找到后用p指向它。 （3）在p結(jié)點(diǎn)后插入q結(jié)點(diǎn)。 實(shí)現(xiàn)語(yǔ)句：,看源程序(8_1),單鏈表結(jié)點(diǎn)的插入（4）,在值為x的結(jié)點(diǎn)前插入一個(gè)值為y的結(jié)點(diǎn) 步驟： （1）申請(qǐng)一個(gè)結(jié)點(diǎn)空間，用q指向它，并把y放入其中。 （2）在鏈表中查找值為x的結(jié)點(diǎn)，找到后用p指向它，pf指向它的前驅(qū)結(jié)點(diǎn)。 （3）在pf結(jié)點(diǎn)后插入q結(jié)點(diǎn)。 實(shí)現(xiàn)語(yǔ)句（兩種方法）：,看源程序(8_2)

3、,看源程序(8_3),返回,單鏈表結(jié)點(diǎn)插入舉例,【補(bǔ)例】將【例7-5】改成用菜單選擇實(shí)現(xiàn)，并在此基礎(chǔ)上增加插入功能。 分析 插入時(shí)，按照以下幾種情況進(jìn)行： （1）插入到鏈?zhǔn)住?（2）插入到鏈尾。 （3）插入到指定值的后面。 （4）插入到指定值的前面。,主函數(shù)模塊,【補(bǔ)例】將【例7-5】改成用菜單選擇實(shí)現(xiàn)，并在此基礎(chǔ)上增加插入功能。 主函數(shù)流程圖 源程序,運(yùn)行程序(8_4),看源程序(8_4),插入子模塊,【補(bǔ)例】將【例7-5】改成用菜單選擇實(shí)現(xiàn)，并在此基礎(chǔ)上增加插入功能。 插入子函數(shù)流程圖 源程序,運(yùn)行程序(8_4),看源程序(8_4),返回,思考：不用附加頭結(jié)點(diǎn)，任何修改？(8_6),鏈表結(jié)

4、點(diǎn)的刪除,在鏈表中刪除結(jié)點(diǎn)也有很多情況。 下面以帶附加頭結(jié)點(diǎn)的單鏈表為例進(jìn)行介紹。,單鏈表結(jié)點(diǎn)的刪除（1）,刪除指定結(jié)點(diǎn) 刪除過(guò)程圖示（刪除q結(jié)點(diǎn)的后繼結(jié)點(diǎn)p）：,實(shí)現(xiàn)語(yǔ)句： q-next = p-next; free(p);,單鏈表結(jié)點(diǎn)的刪除（2）,刪除值為x的結(jié)點(diǎn) 步驟： （1）在鏈表中查找值為x的結(jié)點(diǎn)，找到后用p指向它，q指向它的前驅(qū)結(jié)點(diǎn)。 （2）使p結(jié)點(diǎn)脫離鏈表。 （3）釋放p結(jié)點(diǎn)的內(nèi)存空間。 實(shí)現(xiàn)語(yǔ)句：,看源程序(8_5),返回,單鏈表結(jié)點(diǎn)刪除舉例,【補(bǔ)例】在【例7-5】的基礎(chǔ)上增加刪除功能。 分析 刪除時(shí)，按照以下幾種情況進(jìn)行： （1）刪除鏈?zhǔn)捉Y(jié)點(diǎn)。 （2）刪除鏈尾結(jié)點(diǎn)。 （3）刪除指定值的結(jié)點(diǎn)。,刪除子模塊,【補(bǔ)例】在【例7-5】的基礎(chǔ)上增加刪除功能。 刪除子函數(shù)流程圖 源程序,運(yùn)行程序(8_4),看源程序(8_4),思考：不用附加頭結(jié)點(diǎn)，任何修改？(8_6),任務(wù)相關(guān)部分,任務(wù)程序中的功能“添加一個(gè)學(xué)生”和“刪除一個(gè)學(xué)生”，實(shí)際上就是在鏈表中插入和刪除結(jié)點(diǎn)的過(guò)程。,本次課總結(jié),