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

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

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

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