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

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