第2章初識數據結構2.2數組與鏈表教學設計教學背景信息科技是現代科學技術領域的重要部分，主要研究以數字形式表達的信息及其應用中的科學原理、思維方法、處理過程和工程實現。當代高速發展的信息科技對全球經濟、社會和文化發展起著越來越重要的作用。義務教育信息科技課程具有基礎性、實踐性和綜合性，為高中階段信息技術課程的學習奠定基礎。信息科技課程旨在培養科學精神和科技倫理，提升自主可控意識，培育社會主義核心價值觀，樹立總體國家安全觀，提升數字素養與技能。教材分析本節課的教學內容選自人教/地圖出版社選擇性必修1數據與數據結構第2章初識數據結構2.2數組與鏈表。數據作為描述事物的符號記錄，它不僅可以是數字，還可以是文字、字符、圖形、圖像、音頻和視頻等。中國漢字文化博大精深，一個字可能有多個含義，幾個字的排列順序不同，就可能會組成含義不同的詞句。例如，用“讀”“書”“好”三個字就可以組成“讀書好”“讀好書”“書好讀”等。從數據結構角度來看，漢字“讀”“書”“好”都是數據，其排列順序就是結構。計算機科學是一門研究信息表示和處理的科學，而信息的表示和組織直接關系到信息處理的效率。數據結構研究的是信息在計算機中的組織和存儲方式，程序設計依賴于一定的數據結構。因此，對數據及其結構的研究十分必要。本章將通過主題學習項目“管理個人書目”來理解數據結構和抽象數據類型的基本概念，認識數據結構在解決問題過程中的重要作用，以及抽象數據類型對數據處理的重要性。結合生活實際，通過問題分析與程序實現，理解數組、鏈表等概念，并能夠根據需求選擇合適的存儲方式。學情分析此節課針對的對象是高二年級的學生。學生學習過信息技術基礎知識，對計算機、網絡、物聯網等技術有基本了解:已經學習了Python語言的基本概念，并掌握了基本的結構和算法;對現代生活中的信息系統有所觀察和積累。本章圍繞主題“析說身邊數據”開展項目學習，從比較感興趣的身邊事例入手，自擬主題，并結合主題有目的地收集、整理和分析數據，認識數據的價值與意義，感受數據對生活的影響，并以多媒體作品的方式進行班內交流。教學目標1.能結合生活實際理解數組、鏈表的含義，并能編程實現其相關操作。2.理解數組、鏈表的區別，能根據不同的應用場景選擇合適的存儲方式。教學重點與難點教學重點:能結合生活實際理解數組、鏈表的含義，并能編程實現其相關操作。教學難點:能根據不同的應用場景選擇合適的存儲方式。教學方法與教學手段案例分析法、講授法、任務驅動法。教學過程問題導入體驗探索方隊與數據存儲我們的祖先曾創造了無與倫比的文化，而“和合”文化正是這其中的精髓之一。“和”指的是和諧、和平、中和等，“合”指的是匯合、融合、聯合等。這種“貴和尚中、善解能容，厚德載物、和而不同”的寬容品格，是我們民族所追求的一種文化理念。2008年北京奧林匹克運動會開幕式中的表演方隊（圖2.2.1）（參見教材P29）就完美展示了“和合”理念，向世界傳達出中國人民希望構建一個和平、和諧而更加美好世界的期待。思考：如果把圖2.2.1紅框方隊中的每個表演者視為一個數據，在計算機中如何存儲這些數據？存儲結構存儲結構，也稱物理結構，是邏輯結構在計算機中的存儲形式，它包括數據元素的存儲和數據元素之間關系的存儲。邏輯結構與存儲結構的關系為：邏輯結構是面向問題的，而存儲結構是面向計算機的。邏輯結構是數據結構的抽象，存儲結構是數據結構的實現，兩者綜合起來建立了數據元素之間的結構關系。思考活動醫院的秩序管理在醫院大廳里，常會看到這樣的情形：有人在繳費窗口前排隊，也有人零零散散坐在座位上等待叫號。思考：如果把每個排隊繳費或等待叫號看病的人均抽象為一個數據元素，在計算機中采取什么方式來存儲這些數據元素更為方便？按照數據元素之間關系的不同存儲方式，存儲結構可分為兩種基本類型：順序存儲結構和鏈式存儲結構。順序存儲結構是把邏輯上相鄰的數據元素存放在地址連續的若干存儲單元中，數據元素之間的邏輯關系由存儲單元的鄰接關系來體現。順序存儲結構是一種最基本的存儲結構，在高級程序設計語言中通常用數組類型來實現。鏈式存儲結構是把數據元素存放在任意的存儲單元中，這些存儲單元可以是連續的，也可以是不連續的。鏈式存儲結構在高級程序設計語言中通常用指針來實現。在順序存儲結構中，每個數據元素只需存儲數據元素信息即可。但在鏈式存儲結構中，除了存儲數據元素信息（數據域）外，還要存儲它的后繼元素的存儲地址（指針域），指針域中存儲的信息稱為指針或鏈。這兩部分信息組成鏈式存儲結構中的節點，如圖2.2.4（參見教材P31）所示。數組——順序存儲大多數實際問題中涉及的數據元素都有很多個，數組是存儲多個數據元素的重要方法。思考活動身高數據處理整型、浮點型等數據類型只能表示單一數據，現已采集10位女生的身高數據，如表2.2.1所示，需要計算這10位女生的平均身高。表2.2.110位女生的身高數據表學號身高/cm11622165316741555162616871598166916410160思考：1.如何在程序中定義變量來表示這些數據？2.如果有更多的數據，比如一個班或一個年級的學生身高數據，在程序中又怎么用變量來表示？數組數組是一組具有相同數據類型的數據元素的集合，占用一段連續的存儲空間，常用來實現數據的順序存儲。用下標代表數據元素在數組中的序號，一般地，數組下標自0開始編號。用數組名和下標來唯一地標識數組中的一個數據元素。例如，表2.2.1中的數據可用數組a來存儲，a[0]，a[1]，a[2]，...，a[9]分別存儲學生1，學生2，學生3，......，學生10的身高，如表2.2.2所示。其中，a是數組名，0，1，2，...，9是數組下標。標識數組中數據元素所需的下標個數可能不止一個，下標個數稱為數組的維數。只有一個下標的數組稱為一維數組，如上面介紹的數組a就是一維數組。有兩個下標的數組稱為二維數組，也常稱為矩陣。如圖2.2.6（參見教材P33）所示的圍棋棋盤需要用一個二維數組（如m）來表示，棋盤中的一個具體位置需要指定兩個下標才能唯一確定，如用m[0][0]來表示圖中左上角的位置，則m[18][18]表示圖中右下角的位置，其中第一個下標表示行號，第二個下標表示列號。一般而言，可以設置數組元素值為0，表示該位置沒有棋子；設置數組元素值為1，表示該位置為一方棋子；設置數組元素值為2，表示該位置為另一方棋子。數組的操作1.數組的初始化和賦值在Python中，可以通過列表類型“list”來實現對數組的操作。在程序中，可以使用以下方法為數組進行初始化和賦值操作。例如，aｘ[]表示數組a是一個空數組；b=[1，2，3，4，5，6，7，8，9]，表示數組b中有9個數據元素。鏈表——鏈式存儲數組的優點和缺點都在于元素存儲的集中方式和連續性。它的缺點具體表現為數組元素的插入和刪除需要大量移動數組中已有的元素，當數組中存儲的數據元素個數較多時，操作量將會很大。思考活動老鷹捉小雞”游戲與數據存儲如圖2.2.9（參見教材P36）所示的場景中，由老師身后的孩子們組成的隊伍有時會發生一些變化，例如，某個孩子插進隊伍中或單獨從隊伍中跑出來等。思考：如果我們把每個孩子抽象為一個數據元素，在計算機中采取哪種結構存儲這些數據元素更合適？鏈表鏈表指由多個節點（由數據域和指針域組成）鏈接成的序列，通過節點的指針域將多個節點按數據元素的邏輯順序鏈接在一起。每個節點只有一個指向后繼的指針域的鏈表稱為單鏈表。通常，我們將鏈表示意為用箭頭相鏈接的節點的序列，節點之間的箭頭表示指針域中的指針。鏈表的操作在Python中，可以通過“類”來實現對鏈表的操作。每個節點都是鏈表中的一個實例，鏈接在一起形成一個完整鏈表。實踐活動鏈表程序應用體驗式戶外拓展訓練獲得了越來越多年輕人的歡迎，其訓練項目豐富多樣，圖2.2.14（參見教材P42）所示為“畢業墻”項目：所有隊員按照教官的指示，利用人梯爬上4m的高墻，它強調學員之間的團結合作，共同完成同一個目標。某學校要組織學生參加這樣的戶外拓展活動，預案按照時間順序擬定了一些項目，但在活動過程中因為天氣的原因要將其中的兩個項目改為室內活動項目。查找資料，設計若干戶外和室內活動項目名稱。編寫程序，用鏈表的方式保存拓展項目名稱，并編寫程序實現增加、刪除的功能。數組與鏈表的比較數組和鏈表是兩種基本的存儲結構，它們在內存分配與使用上是不一樣的，有各自的特點。思考活動旅游景點名稱的存儲小明打算利用假期與家人外出度假，他們旅游的目的地是位于我國西南邊陲，有“彩云之南”美稱的云南省。他們有兩種可選方案：跟團游或自由行。思考：如果用數組或鏈表來存儲他們將要游覽的每個旅游景點的名稱，你會選擇哪種方案？請說明原因。數組和鏈表在存儲分配方式、空間性能和時間性能三方面都各有其特點，如表2.2.3所示。表2.2.3數組與鏈表的對比比較項目數組鏈表存儲分配方式數組用一段地址連續的存儲單元依次存儲數據元素，數據元素之間的邏輯關系通過存儲位置來體現鏈表用一組地址不要求連續的存儲單元存放數據元素，用指針來反映數據元素之間的邏輯關系空間性能數組需要一段連續的存儲空間，因此對內存的要求較高；由于數組中數據元素的邏輯結構可通過物理上的相對位置表現出來，故數組的存儲密度高鏈表不需要一段連續的存儲空間，因此對內存的要求不高；由于鏈表中數據元素的邏輯結構需通過指針來體現，故鏈表的存儲密度低時間性能數組是一種隨機訪問結構，對數組中任一元素都可以直接存取。而在數組中進行插入和刪除，平均要移動近一半的元素，當每個元素的信息量較大時，移動元素需要消耗較長的時間鏈表是一種順序訪問結構，要查找鏈表中的任一元素，都需從頭指針起開始查找，平均需要搜索半個鏈表。而在鏈表中的任何位置上進行插入和刪除，都只需要修改指針，不需要移動元素具體程序設計中，應該如何選擇存儲結構呢？當對數據元素進行的操作主要是元素查找，而很少做插入和刪除時，宜采用數組作為存儲結構。如果需要頻繁進行數據元素的插入和刪除操作，宜采用鏈表作為存儲結構。當程序中需要的元素個數變化較大或者不知道數據量有多大時，建議選擇鏈表結構，這樣可以不需要考慮存儲空間大小的問題。但如果事先知道元素的大致個數，采用數組的效率會高很多。總之，需要根據實際情況，客觀考慮采用哪種數據結構更能滿足程序功能和性能需求。在具體程序實現中，要綜合考量數組和鏈表的優缺點，才能最終選定比較適宜的實現方法。例：編程解決“約瑟夫環”問題。有41個人圍坐在一起排成一個圓圈，由第1個人開始報數，每數到3，此人就必須出列，然后再由下一位重新從1開始報數，直到所有人都出列為止。請問，最后一個出列的人所在的初始位置是什么？這其實是一個數學應用問題，可以描述為：已知n個人（以編號1，2，3，...，n分別表示）圍坐在一張圓桌周圍。約定從編號為1的人開始報數，數到k的那個人出列；下一個人又從1開始報數，數到k的那個人又出列......依此規律重復下去，直到圓桌周圍的人全部出列。簡化的“約瑟夫環”如圖2.2.15所示。要解決此問題，要求用戶輸入的內容包括：a.參加活動的人數，即n的值（編號1，2，3，...，n需要存放在數組或鏈表中）；b.出列的間隔數，即k的值。要求輸出的內容包括：a.出列人員的序號；b.最后出列人員的序號。根據上面的問題分析及輸入、輸出參數分析，可以選擇一種數據存儲結構，然后用算法來實現。項目實施編寫程序，管理個人書目一、項目活動請將喜歡的圖書列出一張書單。1.根據需求，選擇合適的數據結構對其進行存儲。2.編寫程序對該數據結構進行初始化、插入、刪除和查找等操作。3.給程序添加注釋，同時形成一份描述工作記錄的文字資料。4.整理程序及文檔，形成項目報告。小組之間開展交流。二、項目檢查完成“管理個人書目”的程序設計，并檢查程序段所實現的功能，程序沒有明顯錯誤，能正確運行。總結評價1.總結本章的核心概念與關鍵能力。2.根據自己的掌握情況填寫下表。學習內容掌握程度數據結構的基本概念□不了解□了解□理解抽象數據類型的概念□不了解□了解□理解數組、鏈表等基本數據結構的概念□不了解□了解□理解數組、鏈表的相關操作□不了解□了解□理解數組、鏈表的區別□不了解□了解□理解課后作業練習提升編寫程序，利用隨機函數，生成10個0～