環球實時：“數據合并”教學思路

說在前面

浙教版《選擇性必修一數據和數據結構》第一章是全書的導論，起到了提綱挈領的作用。其中“1.2.3數據結構的作用”，通過兩個案例來說明對同一問題的解決，可以依據不同數據結構來設計算法，其效率是不一樣的。兩個案例較為典型，且有一定難度，教師應根據學生實際，采用算法分析、代碼講解或過程演示等不同方法授課。

(資料圖片僅供參考)

教材文本

教材處理

教材雖然采用了一維數組來存儲數據，但其下標是從1開始的。為了便于編程，筆者把數組下標設置從0開始，并初始化i=0，p=0，tot=len(a)，如下圖所示。

學生任務單

任務1. 回顧數組和鏈表數據結構分別有何特征，思考如下問題：（1）如何在數組中插入單個元素？需要移動哪些元素？（2）如何在數組中刪除單個元素？需要移動哪些元素？（3）如何在鏈表中插入單個節點？需要移動哪些節點或修改哪些指針？（4）如何在鏈表中刪除單個節點？需要移動哪些節點或修改哪些指針？任務2. 閱讀教材中“數據合并”材料，思考如下問題：（1）基于數組的算法設計中，如何確定數組c的長度？初始化其右側元素值為-1的目的是什么？使用下圖演示依次將數組b的元素插入到數組c的過程，初始化i=0，p=0，tot=len(a)，思考整個過程中，變量i，p，tot的變化情況，以及程序結束后數組c的值為多少？（2）基于鏈表的算法設計中，使用下圖演示依次將鏈表b的節點插入到鏈表a的過程，變量head_a，p1和p的含義分別是什么？若節點p的值小于節點q，需要如何修改指針？（即修改哪些變量的值）；反之，若節點p的值不小于節點q，又該修改哪些變量的值呢？例如，將值為20的節點插入到鏈表a時，需要如何修改指針？請使用繪圖的方法，描述整個過程中，后繼指針的變化情況。問題解析任務1. （1）在數組中插入單個元素，需要確定插入位置的下標，將該位置及其后的元素依次右移1位，以騰出插入位置，再將新元素放到該位置。插入新元素6前后數組存儲數據如下圖所示：（2）在數組中刪除單個元素，需要確定該元素的下標，依次將該元素右側的元素依次左移1位，讓右側元素覆蓋左側元素，以實現刪除效果。刪除元素7前后數組存儲數據如下圖所示：（3）在單鏈表中插入單個節點，需要確定前驅節點pre在鏈表中的位置，設置新節點的指針指向pre的后繼節點，再修改pre的后繼指針指向新節點。插入新節點6前后鏈表存儲數據如下圖所示：（4）在單鏈表中刪除單個節點，需要確定其前驅節點pre在鏈表中的位置，再修改pre的后繼指針指向被刪除節點的后繼節點。刪除節點7前后鏈表存儲數據如下圖所示：任務2. （1）基于數組的算法設計中，數組c的長度等于數組a和b的長度之和；之所以初始化數組c右側元素值為-1，是因為在插入數組b的數據之前，數組c的實際元素只包含數組a的全部元素，可以把-1作為監視哨，一旦c[p]的值為-1，則表示p已經指向數組c實際數據的尾部，可以直接令c[p]=b[i]。但這樣做的前提是數組a和b中的數據均不能為-1，否則程序會出錯。更好的做法是判斷p與tot的值是否相等，若相等則表示p已指向數組c尾部。使用下圖演示依次將數組b的元素插入到數組c的過程，初始化i=0，p=0，tot=len(a)。思考整個過程中，變量i，p，tot的變化情況，以及程序結束后數組c的值為多少？算法設計如下：① 若c[p]>=b[i]，則將p右移一位；② 若c[p]==-1，則令c[p]=b[i]，并將tot右移一位；③ 若c[p]需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關優秀文章：

閱讀代碼和寫更好的代碼

最有效的學習方式

Python算法之旅文章分類

關鍵詞： 存儲數據 如下圖所示 數據結構