九一免费国产,中文字幕破解无码HD,免费18网站,香蕉视频国产,国产亚洲精品久久久久动,亚洲乱亚洲乱妇,操逼免费视频大全,寡妇高潮一级

說在前面

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

教材文本

教材處理

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

學生任務單

任務1. 回顧數(shù)組和鏈表數(shù)據(jù)結構分別有何特征，思考如下問題：

（1）如何在數(shù)組中插入單個元素？需要移動哪些元素？

（2）如何在數(shù)組中刪除單個元素？需要移動哪些元素？

（3）如何在鏈表中插入單個節(jié)點？需要移動哪些節(jié)點或修改哪些指針？

（4）如何在鏈表中刪除單個節(jié)點？需要移動哪些節(jié)點或修改哪些指針？

任務2. 閱讀教材中“數(shù)據(jù)合并”材料，思考如下問題：

（1）基于數(shù)組的算法設計中，如何確定數(shù)組c的長度？初始化其右側元素值為-1的目的是什么？使用下圖演示依次將數(shù)組b的元素插入到數(shù)組c的過程，初始化i=0，p=0，tot=len(a)，思考整個過程中，變量i，p，tot的變化情況，以及程序結束后數(shù)組c的值為多少？

（2）基于鏈表的算法設計中，使用下圖演示依次將鏈表b的節(jié)點插入到鏈表a的過程，變量head_a，p1和p的含義分別是什么？若節(jié)點p的值小于節(jié)點q，需要如何修改指針？（即修改哪些變量的值）；反之，若節(jié)點p的值不小于節(jié)點q，又該修改哪些變量的值呢？

例如，將值為20的節(jié)點插入到鏈表a時，需要如何修改指針？請使用繪圖的方法，描述整個過程中，后繼指針的變化情況。

問題解析

任務1. （1）在數(shù)組中插入單個元素，需要確定插入位置的下標，將該位置及其后的元素依次右移1位，以騰出插入位置，再將新元素放到該位置。插入新元素6前后數(shù)組存儲數(shù)據(jù)如下圖所示：

（2）在數(shù)組中刪除單個元素，需要確定該元素的下標，依次將該元素右側的元素依次左移1位，讓右側元素覆蓋左側元素，以實現(xiàn)刪除效果。刪除元素7前后數(shù)組存儲數(shù)據(jù)如下圖所示：

（3）在單鏈表中插入單個節(jié)點，需要確定前驅節(jié)點pre在鏈表中的位置，設置新節(jié)點的指針指向pre的后繼節(jié)點，再修改pre的后繼指針指向新節(jié)點。插入新節(jié)點6前后鏈表存儲數(shù)據(jù)如下圖所示：

（4）在單鏈表中刪除單個節(jié)點，需要確定其前驅節(jié)點pre在鏈表中的位置，再修改pre的后繼指針指向被刪除節(jié)點的后繼節(jié)點。刪除節(jié)點7前后鏈表存儲數(shù)據(jù)如下圖所示：

任務2. （1）基于數(shù)組的算法設計中，數(shù)組c的長度等于數(shù)組a和b的長度之和；之所以初始化數(shù)組c右側元素值為-1，是因為在插入數(shù)組b的數(shù)據(jù)之前，數(shù)組c的實際元素只包含數(shù)組a的全部元素，可以把-1作為監(jiān)視哨，一旦c[p]的值為-1，則表示p已經(jīng)指向數(shù)組c實際數(shù)據(jù)的尾部，可以直接令c[p]=b[i]。但這樣做的前提是數(shù)組a和b中的數(shù)據(jù)均不能為-1，否則程序會出錯。更好的做法是判斷p與tot的值是否相等，若相等則表示p已指向數(shù)組c尾部。

使用下圖演示依次將數(shù)組b的元素插入到數(shù)組c的過程，初始化i=0，p=0，tot=len(a)。思考整個過程中，變量i，p，tot的變化情況，以及程序結束后數(shù)組c的值為多少？

算法設計如下：

① 若c[p]>=b[i]，則將p右移一位；

② 若c[p]==-1，則令c[p]=b[i]，并將tot右移一位；

③ 若c[p]<b[i]，則將c[p:tot]的元素依次右移一位，然后令c[p]=b[i]，并將tot右移一位；

④ 將i右移一位。循環(huán)執(zhí)行①-④，直至i越界。

程序結束后數(shù)組c，及各變量的值如下圖所示：

（2）基于鏈表的算法設計中，使用下圖演示依次將鏈表b的節(jié)點插入到鏈表a的過程，變量head_a表示鏈表a的頭指針，p指向鏈表a的當前節(jié)點，p1指向p的前驅節(jié)點；同理head_b表示鏈表b的頭指針，q指向鏈表b的當前節(jié)點，q1指向q的前驅節(jié)點。

將鏈表b的節(jié)點插入到鏈表a中時，若節(jié)點p的值不小于節(jié)點q，則先將p1指向p，再將p指向其后繼節(jié)點；若節(jié)點p的值小于節(jié)點q，則執(zhí)行如下操作：

① 將p1的后繼指針指向q；

② 將q1的后繼指針指向q的后繼節(jié)點；

③ 將p1指向q，并將p1的后繼指針指向p；

④ 將q指向q1的后繼節(jié)點。

例如，將鏈表b中值為20的節(jié)點q插入到鏈表a時，先將p1的后繼指針指向q，然后將q1的后繼指針指向q的后繼節(jié)點；再將p1指向q，并將p1的后繼指針指向p；最后將q指向q1的后繼節(jié)點。插入節(jié)點20后，鏈表示意圖如下所示：

插入全部節(jié)點后，鏈表示意圖如下所示：

課后作業(yè)

本節(jié)課的教學任務是通過示意圖動態(tài)演示分別使用數(shù)組和鏈表存儲數(shù)據(jù)和插入元素的過程，使學生掌握使用數(shù)組或鏈表存儲數(shù)據(jù)的方法，理解插入元素時游標或指針的變化情況。重在理解算法，無需編寫程序。

當然，待學生掌握更多編程知識后，我們也可以讓學生回過頭來編寫程序實現(xiàn)本案例功能；或者在使用示意圖動態(tài)演示插入元素過程后，讓學生運行教師編寫好的代碼，體驗程序運行過程。程序運行結果如下，請編程實現(xiàn)之。

需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

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

相關優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學習方式

Python算法之旅文章分類

“數(shù)據(jù)合并”教學思路