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

第2章初識數(shù)據(jù)結(jié)構(gòu)2.1數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型教學(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.1數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型。數(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í)項(xiàng)目“管理個人書目”來理解數(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ù)”開展項(xiàng)目學(xué)習(xí)，從比較感興趣的身邊事例入手，自擬主題，并結(jié)合主題有目的地收集、整理和分析數(shù)據(jù)，認(rèn)識數(shù)據(jù)的價值與意義，感受數(shù)據(jù)對生活的影響，并以多媒體作品的方式進(jìn)行班內(nèi)交流。教學(xué)目標(biāo)1.理解數(shù)據(jù)結(jié)構(gòu)的概念，能夠用數(shù)據(jù)結(jié)構(gòu)表達(dá)數(shù)據(jù)的邏輯關(guān)系，認(rèn)識數(shù)據(jù)結(jié)構(gòu)在解決問題過程中的重要作用。2.理解抽象數(shù)據(jù)類型的概念，能夠?qū)μ囟ㄉ钋榫持械年P(guān)系進(jìn)行抽象，認(rèn)識抽象數(shù)據(jù)類型對數(shù)據(jù)處理的重要性。教學(xué)重點(diǎn)與難點(diǎn)教學(xué)重點(diǎn):理解數(shù)據(jù)結(jié)構(gòu)的概念，能夠用數(shù)據(jù)結(jié)構(gòu)表達(dá)數(shù)據(jù)的邏輯關(guān)系。教學(xué)難點(diǎn):能夠?qū)μ囟ㄉ钋榫持械年P(guān)系進(jìn)行抽象，認(rèn)識抽象數(shù)據(jù)類型對數(shù)據(jù)處理的重要性。教學(xué)方法與教學(xué)手段案例分析法、講授法、任務(wù)驅(qū)動法。教學(xué)過程問題導(dǎo)入體驗(yàn)探索田忌賽馬與數(shù)據(jù)結(jié)構(gòu)田忌賽馬的典故出自《史記·孫子吳起列傳》。忌數(shù)與齊諸公子馳逐重射。孫子見其馬足不甚相遠(yuǎn)，馬有上、中、下輩。于是孫子謂田忌曰：“君弟重射，臣能令君勝。”田忌信然之，與王及諸公子逐射千金。及臨質(zhì)，孫子曰：“今以君之下駟與彼上駟，取君上駟與彼中駟，取君中駟與彼下駟?！奔锐Y三輩畢，而田忌一不勝而再勝，卒得王千金。田忌采用孫臏的計策，沒有更換參賽馬匹，只調(diào)整了馬匹的參賽順序，就轉(zhuǎn)敗為勝，如圖2.1.1所示。如果把馬看成“數(shù)據(jù)”，把三匹馬的出場順序看成數(shù)據(jù)之間的“關(guān)系”，那么，相同的數(shù)據(jù)不同的關(guān)系，可得到不同的“數(shù)據(jù)結(jié)構(gòu)”，而不同的“數(shù)據(jù)結(jié)構(gòu)”對問題解決會產(chǎn)生重要影響。思考：從上述典故可以看出，使用相同的數(shù)據(jù)，采取不同的結(jié)構(gòu)，卻產(chǎn)生了不同的結(jié)果。生活中還有哪些類似的實(shí)例？數(shù)據(jù)結(jié)構(gòu)隨著計算機(jī)應(yīng)用的日益廣泛，計算機(jī)程序的規(guī)模越來越大，程序結(jié)構(gòu)越來越復(fù)雜。計算機(jī)在處理數(shù)據(jù)時不是只處理少數(shù)幾個無內(nèi)在聯(lián)系的數(shù)據(jù)，而是處理多個數(shù)據(jù)，并且這些數(shù)據(jù)之間是有一定內(nèi)在聯(lián)系的。此時，定義數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系就顯得十分重要。思考活動奇妙的文字組合中華文化源遠(yuǎn)流長，其中有非常多的成語典故閃耀著先賢的智慧。例如，“事倍功半”與“事半功倍”這兩個成語，其包含的文字完全相同，但由于文字所處的相對位置不同，即文字與文字之間的關(guān)系發(fā)生了改變，故而產(chǎn)生了截然不同的含義。思考：你能說出更多因文字位置改變而影響語義的類似詞語或語句嗎？基本概念和術(shù)語學(xué)生在入學(xué)的時候，通常需要填寫如表2.1.1所示的學(xué)生基本信息表。下面利用此表來解釋數(shù)據(jù)結(jié)構(gòu)的一些基本概念。表2.1.1學(xué)生基本信息表學(xué)號姓名性別出生日期0001陸宇男2002/09/020002王逸銘①男②2002/03/200003蘭若曦女2003/05/250004湯曉影女2003/03/26...數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是數(shù)據(jù)中的最小單位，通常用來描述一個屬性。例如，表2.1.1中的一個學(xué)生姓名就是一個數(shù)據(jù)項(xiàng)，如①所示。同樣，學(xué)號、性別、出生日期的值也均為數(shù)據(jù)項(xiàng)。數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機(jī)中通常作為一個整體來處理。一般來說，一個數(shù)據(jù)元素由多個數(shù)據(jù)項(xiàng)組成，具體包含哪些數(shù)據(jù)項(xiàng)，則取決于用戶的需求。例如，表2.1.1中，一個學(xué)生的基本信息就是一個數(shù)據(jù)元素，由學(xué)號、姓名、性別和出生日期這四個數(shù)據(jù)項(xiàng)組成，如②所示。數(shù)據(jù)元素還可以是一本書或一條借閱記錄等。數(shù)據(jù)對象（參見教材P20）中每個學(xué)生的基本信息均可被視作一個數(shù)據(jù)元素，它們都有學(xué)號、姓名、性別和出生日期四個數(shù)據(jù)項(xiàng)，若干學(xué)生的基本信息就構(gòu)成一個數(shù)據(jù)對象。在實(shí)際應(yīng)用中，被處理的數(shù)據(jù)元素通常具有相同的屬性，在不產(chǎn)生混淆的情況下，常將數(shù)據(jù)對象簡稱為數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)簡單地說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)對象中的數(shù)據(jù)元素都不是孤立存在的，而是相互之間存在著某種關(guān)系，這些關(guān)系稱為結(jié)構(gòu)。良好的數(shù)據(jù)結(jié)構(gòu)可以給程序帶來更高的運(yùn)行或存儲效率。數(shù)據(jù)結(jié)構(gòu)可采用如圖2.1.2（參見教材P21）所示的方式來定義。數(shù)據(jù)對象上的關(guān)系指屬于同一對象的數(shù)據(jù)元素之間的關(guān)系。例如，可以用<a,b>來表示數(shù)據(jù)元素a和b間的前驅(qū)、后繼關(guān)系，其中，a是b的前驅(qū)，b是a的后繼。顯然，<a,b>與<b,a>是不同的關(guān)系。例如，用“書”“讀”“好”三個字可以組成如圖2.1.3（參見教材P21）和圖2.1.4（參見教材P21）所示的兩種不同的數(shù)據(jù)結(jié)構(gòu)?！白x書好”的數(shù)據(jù)對象是｛書，讀，好｝，數(shù)據(jù)關(guān)系是｛<讀,書>，<書,好>｝，“讀”字在“書”字之前，“讀”為“書”的前驅(qū)，“書”為“讀”的后繼。“讀”無前驅(qū)，“好”無后繼?！昂米x書”的數(shù)據(jù)對象是｛書，讀，好｝，數(shù)據(jù)關(guān)系是｛<好,讀>，<讀,書>｝，“好”字在“讀”字之前，“好”為“讀”的前驅(qū)，“讀”為“好”的后繼?！昂谩睙o前驅(qū)，“書”無后繼。以上兩種數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)對象相同，但數(shù)據(jù)關(guān)系不同，因此是兩種不同的數(shù)據(jù)結(jié)構(gòu)。實(shí)踐活動構(gòu)造數(shù)據(jù)結(jié)構(gòu)用“事”“半”“功”“倍”四個字構(gòu)造至少兩種以上不同的數(shù)據(jù)結(jié)構(gòu)，參考圖2.1.3（參見教材P21）（參見教材P21）的方式來定義。根據(jù)不同的研究視角，數(shù)據(jù)結(jié)構(gòu)可以分為邏輯結(jié)構(gòu)和存儲（物理）結(jié)構(gòu)。本節(jié)詳細(xì)介紹邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)將在下一節(jié)進(jìn)行講解。邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)指從具體問題抽象出來的數(shù)學(xué)模型。它研究的是數(shù)據(jù)元素之間的邏輯關(guān)系，與具體的計算機(jī)無關(guān)。通常所說的數(shù)據(jù)結(jié)構(gòu)一般指邏輯結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特點(diǎn)，通常將邏輯結(jié)構(gòu)分為四種基本類型：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。下面利用表2.1.2來說明四種不同的數(shù)據(jù)結(jié)構(gòu)，并給出相應(yīng)數(shù)據(jù)結(jié)構(gòu)的圖形表示法。表2.1.2學(xué)生會部分成員基本信息表編號姓名性別所在班級所在部門職務(wù)001李元哲男高一1班宣傳部干事0002黃玉婉女高一2班體育部干事0003劉亮亮男高二3班宣傳部部長0004孟丹男高一8班宣傳部干事005孫亞菲女高一5班宣傳部干事006盧迪女高二2班宣傳部干事007王逸銘男高二6班體育部部長008蘭若曦女高二7班主席009黃佳怡女高二1班生活部部長010王曉敏女高二4班生活部干事在數(shù)據(jù)結(jié)構(gòu)的圖形表示法中，通常用中間標(biāo)有元素值的圓圈表示一個數(shù)據(jù)元素，一般也可稱之為數(shù)據(jù)節(jié)點(diǎn)，簡稱節(jié)點(diǎn)（又稱結(jié)點(diǎn)）。數(shù)據(jù)元素之間的關(guān)系則用圓圈之間的連線來表示。在表2.1.2中，一名學(xué)生的基本信息即可被看作一個數(shù)據(jù)元素，以下示意圖均以“編號”來標(biāo)識每一名學(xué)生的基本信息。a.學(xué)生會所有成員同屬于學(xué)生會，在不研究他們之間的其他關(guān)系的情況下，所有成員構(gòu)成一個集合結(jié)構(gòu)，如圖2.1.5（參見教材P23）所示。數(shù)據(jù)元素除了具有相同的屬性外，別無其他關(guān)系，這種結(jié)構(gòu)稱為集合結(jié)構(gòu)。（參見教材P23）所示。數(shù)據(jù)元素之間存在一對一的關(guān)系，這種結(jié)構(gòu)稱為線性結(jié)構(gòu)。c.學(xué)生會成員間職務(wù)的級別關(guān)系是分層的，這些數(shù)據(jù)元素可構(gòu)成一個樹形結(jié)構(gòu)。這種分層的結(jié)構(gòu)與人類社會的家族關(guān)系相似，因此在樹形結(jié)構(gòu)中，形象地將上層節(jié)點(diǎn)稱為雙親或父節(jié)點(diǎn)，將下層節(jié)點(diǎn)稱為孩子或子節(jié)點(diǎn)?？梢钥闯?，樹形結(jié)構(gòu)中每個數(shù)據(jù)元素至多只有一個父節(jié)點(diǎn)，但可以有多個子節(jié)點(diǎn)，其示意圖就像一棵倒長的樹，如圖2.1.7（參見教材P23）所示。沒有父節(jié)點(diǎn)的數(shù)據(jù)元素稱為根節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的數(shù)據(jù)元素稱為葉節(jié)點(diǎn)。數(shù)據(jù)元素之間存在一對多的關(guān)系，這種結(jié)構(gòu)稱為樹形結(jié)構(gòu)，可簡稱為樹。d.學(xué)生會干事之間存在的相互合作關(guān)系是多對多的，這些數(shù)據(jù)元素可構(gòu)成一個圖狀結(jié)構(gòu)，如圖2.1.8（參見教材P23）所示?？梢钥闯觯c樹形結(jié)構(gòu)不同，圖狀結(jié)構(gòu)的任意兩個數(shù)據(jù)元素之間都可能存在關(guān)系，因而，數(shù)據(jù)元素之間存在多對多的關(guān)系，這種結(jié)構(gòu)稱為圖狀結(jié)構(gòu)，可簡稱為圖。簡單來說，四種基本邏輯結(jié)構(gòu)的特點(diǎn)分別為：集合結(jié)構(gòu)的數(shù)據(jù)元素除了同屬一個數(shù)據(jù)對象外，別無其他關(guān)系；線性結(jié)構(gòu)的數(shù)據(jù)元素除了同屬一個數(shù)據(jù)對象外，數(shù)據(jù)元素之間存在一對一的關(guān)系；樹形結(jié)構(gòu)的數(shù)據(jù)元素除了同屬一個數(shù)據(jù)對象外，數(shù)據(jù)元素之間存在一對多的關(guān)系；圖狀結(jié)構(gòu)的數(shù)據(jù)元素除了同屬一個數(shù)據(jù)對象外，數(shù)據(jù)元素之間存在多對多的關(guān)系。其中，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)可統(tǒng)稱為非線性結(jié)構(gòu)。閱讀拓展高德納與數(shù)據(jù)結(jié)構(gòu)高德納（DonaldErvinKnuth，圖2.1.9）（參見教材P24）生于1938年，25歲畢業(yè)于美國加州理工學(xué)院數(shù)學(xué)系，獲得博士學(xué)位并留校任教。30歲時，他進(jìn)入斯坦福大學(xué)擔(dān)任計算機(jī)系教授。1968年，高德納創(chuàng)建了數(shù)據(jù)結(jié)構(gòu)的最初體系。他所著的《計算機(jī)程序設(shè)計藝術(shù)》第一卷《基本算法》是第一本較為系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。該系列著作一經(jīng)出版就震驚了世界。1974年，年僅36歲的高德納獲得計算機(jī)科學(xué)界的最高榮譽(yù)——圖靈獎。數(shù)據(jù)類型數(shù)據(jù)類型是按照值的不同進(jìn)行劃分的。例如，在用高級程序設(shè)計語言編寫的程序中，每個變量、常量或表達(dá)式都有各自的取值范圍，數(shù)據(jù)類型就是用來說明變量或表達(dá)式的取值范圍和所能進(jìn)行的操作的。思考活動Python中的數(shù)據(jù)類型在前面Python語言的程序設(shè)計學(xué)習(xí)過程中，曾經(jīng)接觸過Python的數(shù)據(jù)類型，如數(shù)值類型、字符串類型等。思考：除了上述的數(shù)據(jù)類型外，Python中還有哪些常用的數(shù)據(jù)類型？數(shù)據(jù)類型的概念數(shù)據(jù)類型是一組性質(zhì)相同的值的集合以及定義在這個集合上的一組操作的總稱。數(shù)據(jù)類型定義了兩個問題，即該類型的取值范圍，以及該類型允許使用的一組運(yùn)算。例如，16位整型數(shù)據(jù)的取值范圍是32768～+32767，可用的運(yùn)算有加、減、乘、除等。高級程序設(shè)計語言中的數(shù)據(jù)類型就是已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型的實(shí)例，如Python中的整型、浮點(diǎn)型等。抽象數(shù)據(jù)類型抽象是用于問題表示的重要思維工具。例如，可以將“原來有6個香蕉，吃掉2個后還剩幾個？”抽象表示成“62=？”，這里抽取了問題中的數(shù)量特性，而忽略了香蕉的顏色等不相關(guān)特性。一般意義上的抽象，就是忽略研究對象的具體或無關(guān)的特性，只抽取其一般或相關(guān)的特性。計算機(jī)科學(xué)中的抽象是將現(xiàn)實(shí)世界中的各種數(shù)量關(guān)系、空間關(guān)系、邏輯關(guān)系和處理過程等表示為計算機(jī)世界中的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)（順序、分支和循環(huán)等），或者說建立實(shí)際問題的計算模型?？梢哉f，抽象是簡化復(fù)雜現(xiàn)實(shí)問題的有效途徑。例如，地圖就是實(shí)際地形、地貌、地物等的抽象表示。抽象數(shù)據(jù)類型一般可以由數(shù)據(jù)對象、數(shù)據(jù)對象上的關(guān)系以及對數(shù)據(jù)對象的一組基本操作三個要素來定義。與數(shù)據(jù)結(jié)構(gòu)定義形式相對應(yīng)，抽象數(shù)據(jù)類型可用如圖2.1.10（參見教材P25）所示的方式來定義。圖2.1.11（參見教材P25）所示是一個抽象數(shù)據(jù)類型的定義示例。抽象數(shù)據(jù)類型把實(shí)際生活中的問題分解為多個小規(guī)模且容易處理的問題，然后建立一個計算機(jī)能處理的數(shù)據(jù)模型，把每個功能模塊的實(shí)現(xiàn)細(xì)節(jié)作為一個獨(dú)立的單元，并將其具體實(shí)現(xiàn)過程隱藏起來。高級程序設(shè)計語言中沒有提供的數(shù)據(jù)類型需要人為定義，可以通過建立抽象數(shù)據(jù)類型來實(shí)現(xiàn)，即抽象數(shù)據(jù)類型給程序員提供了構(gòu)造自定義數(shù)據(jù)類型的手段。實(shí)踐活動組合數(shù)的計算從n個不同元素中，任取m(m≤n)個元素并成一組，叫作從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(m≤n)個元素的所有組合的個數(shù)，叫作從n個不同元素中取出m個元素的組合數(shù)，用符號表示。分析：本程序要求用戶輸入n、m（m≤n）的值，同時這里定義n、m為正整數(shù)，根據(jù)求組合數(shù)的計算公式，要三次用到階乘（n!=1×2×3×...×n，0!=1）計算。因此，可以自定義一個函數(shù)來計算階乘，然后在程序中調(diào)用三次。理解組合數(shù)計算算法的思路，并將如下程序補(bǔ)充完整。技術(shù)支持自定義函數(shù)隨著程序的功能愈加強(qiáng)大，程序的規(guī)模也將隨之?dāng)U大，若把所有代碼寫在一起，就會使程序的可讀性越來越差、維護(hù)的難度越來越大。另外，當(dāng)程序中需要反復(fù)編寫同樣的語句段以實(shí)現(xiàn)相同的功能時，程序就會變得冗長。此時，就可以使用自定義函數(shù)實(shí)現(xiàn)程序的優(yōu)化。Python提供了許多內(nèi)建函數(shù)，此外，我們還可以創(chuàng)建自定義函數(shù)。在Python中，定義一個函數(shù)的標(biāo)準(zhǔn)方法是使用def語句，依次寫出函數(shù)名、括號、括號中的參數(shù)和冒號“:”，然后在縮進(jìn)塊中編寫函數(shù)體，函數(shù)的返回值用return語句返回。其格式如下：def函數(shù)名(參數(shù)):函數(shù)體return返回值以自定義一個判斷是否為成年人的函數(shù)get_age()為例：#判斷年齡defget_age(age):ifage>=18:return"成年人"else:return