2.2數(shù)組與鏈表教學設計人教-中圖版高中信息技術選擇性必修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

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