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

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