資源簡介

學習任務單
課程基本信息
學科 信息技術 年級 高三 學期 秋季
課題 2.2.1 鏈表的概念、特性及其基本操作
學習目標
1. 理解鏈表的概念和特性。 2. 掌握鏈表的基本操作。
課前學習任務
1. 復習教材中數組的概念、特性及其基本操作。
2. 結合數組的特性和基本操作，針對如下例子設計數組以組織和存儲關鍵數據： ① 處理全班同學的信息，時常需要進行信息訪問； ② 處理學校外來人員信息，進校時登記信息，出校時移除信息。
課上學習任務
【學習任務一】認識鏈表 為了滿足鏈表能在兩個方向都能進行遍歷的需求，請在圖1為每個節點補充正確的前驅指針。 存儲地址數據區域前驅指針后繼指針0“黃剛”11“李豐”-12“王林”03“吳堅”-12
圖1 雙向鏈表存儲結構圖 【學習任務二】鏈表基本操作 存儲地址數據區域后繼指針0“杜剛+1xx.”21“張強+1xx.”32“李彤+1xx.”-13“李豐+1xx.”0
（1）“杜剛”出校，在下圖修改節點指針鏈接，并在上述存儲結構圖中進行相應修改：
（2）“胡潔”在“張強”之前入校，在下圖修改節點指針鏈接，并在上述存儲結構圖中進行相應修改：
（3）“李彤”出校，在下圖修改節點指針鏈接，并在上述存儲結構圖中進行相應修改：
（4）“胡潔”出校，在下圖修改節點指針鏈接，并在上述存儲結構圖中進行相應修改：
【小結】與數組的操作做比較，各自的操作效率（選填：較高/較低） 操作數組鏈表訪問插入刪除
【學習任務三】實踐鞏固——約瑟夫問題 n個人排成一圈，從某個人開始，按照順時針方向從1開始依次編號。從編號為1的人開始順時針“1，2，3，···，m，1，2，3，···，m”報數，報到m（m大于1）的人退出圈子。這樣不斷循環下去，圈子里的人數將不斷減少。由于人數是有限的（n個），因此最終會只剩下一個人，試問最后剩下的人的初始編號是多少？ 分析上述問題，按照如下步驟進行實踐：（在完成本任務時，可以在推薦學習資源處查閱相關知識） （1）抽象與建模 該問題中的關鍵數據是： 。 簡述問題解決的計算模型： （2）設計鏈表與算法 鏈表設計： 鏈表中節點的數據區域保存 ，指針區域保存 。 算法設計 （3）模擬實現 ① 共5個人圍成圈，創建由5個節點組成的單循環鏈表，完善如下存儲結構。 節點地址數據區域后繼指針0112233445
② 從鏈表第一個節點開始順時針循環報數，每報到3的節點從鏈接關系中刪除。并在上述結構中及時修改相關節點的指針。最后留在圈子內的初始編號： 。

展開更多......

收起↑