1.2數(shù)據(jù)的組織結(jié)構(gòu)高中信息技術(shù)/教科版/選擇性必修1目錄1.情景導入2.新知講授3.上機練習4.自主探究5.課堂小結(jié)6.拓展練習1.情境導入隨著信息技術(shù)的普及和深入應(yīng)用，人們需要面對越來越多的數(shù)據(jù)資源，如圖書館中海量的圖書數(shù)據(jù)、學校里教職員工和學生的數(shù)據(jù)、鐵路運輸部門的列車運行線路數(shù)據(jù)等。在使用和處理這些數(shù)據(jù)資源的過程中，我們需要研究如何組織數(shù)據(jù)來提高數(shù)據(jù)的使用效率。探秘校園數(shù)據(jù)你會發(fā)現(xiàn)這些數(shù)據(jù)是怎樣組織的嗎，它們的組織會有什么不同嗎？2.新知講授

任務(wù)一

探究校園數(shù)據(jù)的組織結(jié)構(gòu)請你找到指定書目

任務(wù)一

活動1探究圖書館的圖書數(shù)據(jù)組織方式圖書的數(shù)據(jù)元素包括

、

、

。

書名索書號書本碼放的順序書架上排列的圖書示意圖

任務(wù)一

活動1探究圖書館的圖書數(shù)據(jù)組織方式根據(jù)圖中圖書的擺放方式，將索書號和書名填寫在下面括號里的橫線上。(160101詩經(jīng))-......-(160116西游記)—（

）—（

）—（

）。160117三國演義160118紅樓夢160119水滸傳填一填

任務(wù)一

活動1探究圖書館的圖書數(shù)據(jù)組織方式填一填如果查找圖書時，每次只能看到一本書，那么要找到其中的《三國演義》，需要一個什么過程?把你的方法填寫在下面的橫線上。從(160101詩經(jīng))開始，

。

從左到右，按照索書號從小到大的順序，逐本圖書進行書名的比對，直到160117號圖書的書名比對成功如果從書架上取走《三國演義》后，又放到了《詩經(jīng)》的右面，那么書架上的圖書擺放會變成什么狀態(tài)?將索書號和書名填寫在下面括號里的橫線上。(160101詩經(jīng))—(

)-……-（160116西游記

）—（

）—（

）。160117三國演義160118紅樓夢160119水滸傳

任務(wù)一

活動1探究圖書館的圖書數(shù)據(jù)組織方式線性結(jié)構(gòu)數(shù)據(jù)元素之間的排列次序存在一種明確的先后關(guān)系，這樣的數(shù)據(jù)組織方式稱為線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，除了最后一個元素，每個元素都有一個唯一的后繼元素，所有元素都排成一個線性序列。線性結(jié)構(gòu)是計算機信息系統(tǒng)中最基本和最常見的數(shù)據(jù)組織結(jié)構(gòu)。超市的商品銷售管理、倉庫賬目管理、學校食堂就餐刷卡消費記錄等也都采用線性結(jié)構(gòu)來組織數(shù)據(jù)。

任務(wù)一

活動2探究學生社團的數(shù)據(jù)組織方式學生社團組織結(jié)構(gòu)之間存在什么樣的關(guān)系呢？想一想學生社團組織機構(gòu)存在一種層次關(guān)系，一個上層機構(gòu)可以關(guān)聯(lián)多個下層結(jié)構(gòu)。

任務(wù)一

活動2探究學生社團的數(shù)據(jù)組織方式假設(shè)把學生社團組織機構(gòu)抽象成一個數(shù)據(jù)集合，那么每個機構(gòu)就是這個集合中的一個數(shù)據(jù)元素。請分析以下問題：1.學生社團中心和各分社團之間存在什么樣的關(guān)系？2.科技社團包含哪幾個社團？藝術(shù)社團包含哪幾個社團？3.信息學奧賽和生物學奧賽均屬于什么社團？存在一對多的對應(yīng)關(guān)系，以及上下層的對應(yīng)關(guān)系?？萍忌鐖F包含航模社團、DI社團、機器人社團；藝術(shù)社團包含合唱團和舞蹈團。學科競賽社團

任務(wù)一

活動1探究圖書館的圖書數(shù)據(jù)組織方式樹形結(jié)構(gòu)數(shù)據(jù)元素分屬于不同的層次，一個上層元素可以關(guān)聯(lián)一個或多個下層元素，整個結(jié)構(gòu)中只有一個最上層數(shù)據(jù)元素，這樣的數(shù)據(jù)組織結(jié)構(gòu)像一棵倒放的樹，稱為樹形結(jié)構(gòu)，簡稱樹，最上層的數(shù)據(jù)元素稱為根。根

任務(wù)一

活動3探究校園參觀路線的數(shù)據(jù)組織方式如果把校園示意圖抽象成一個數(shù)據(jù)集合，那么圖中的每個參觀點就是這個集合中的一個數(shù)據(jù)元素。

任務(wù)一

活動3探究校園參觀路線的數(shù)據(jù)組織方式學校商店學生餐廳高中教學樓學校正門幼兒園圖書館教師辦公樓學生宿舍初中教學樓學校公園（

）（

）補全空缺元素體育運動中心實驗樓如果從學校正門出發(fā)，到達學校公園，寫出至少3條參觀路線。學校商店學生餐廳高中教學樓學校正門幼兒園圖書館教師辦公樓學生宿舍初中教學樓學校公園體育運動中心

實驗樓

方

案1學校商店學生餐廳高中教學樓學校正門幼兒園圖書館教師辦公樓學生宿舍初中教學樓學校公園體育運動中心

實驗樓

方

案2學校商店學生餐廳高中教學樓學校正門幼兒園圖書館教師辦公樓學生宿舍初中教學樓學校公園體育運動中心

實驗樓

方

案3還有其他參觀路線嗎？

任務(wù)一

活動1探究圖書館的圖書數(shù)據(jù)組織方式圖狀結(jié)構(gòu)數(shù)據(jù)元素之間可以有一對一、一對多或多對多的相互關(guān)系，這樣的數(shù)據(jù)組織方式稱為圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)分別表示了不同復(fù)雜程度的數(shù)據(jù)元素之間的關(guān)聯(lián)及布局。這些數(shù)據(jù)元素之間邏輯上的排列和對應(yīng)關(guān)系就是數(shù)據(jù)的邏輯結(jié)構(gòu)。計算機如何存儲數(shù)據(jù)？內(nèi)存是電腦上特別重要的存儲器，為系統(tǒng)和軟件的運行提供足夠的內(nèi)存空間，計算機中所有程序的運行也都是在內(nèi)存中進行的。內(nèi)存其實是一塊很大的空間，這么大的空間不可能只是為了存放一個數(shù)據(jù)，那怎么才能有效的使用好這塊空間呢?所以我們把內(nèi)存劃分成一個個小的內(nèi)存單元，每個內(nèi)存單元都可以相對獨立的存放一些數(shù)據(jù)。如此一來內(nèi)存就可以被有效的使用了。

任務(wù)二

活動1設(shè)計校園數(shù)據(jù)的存儲方式但值得注意的是，內(nèi)存只用于暫時性的存放程序和數(shù)據(jù)，一旦關(guān)閉電源或發(fā)生斷電，其中的程序和數(shù)據(jù)將會丟失。了解內(nèi)存的基本結(jié)構(gòu)程序運行過程中直接使用的數(shù)據(jù)都保存在計算機的內(nèi)存儲器(簡稱內(nèi)存)中。內(nèi)存的基本結(jié)構(gòu)是線性排列的一批存儲單元。每個單元的大小相同，可以保存1字節(jié)大小的數(shù)據(jù)。內(nèi)存單元具有唯一的編號，稱為地址。內(nèi)存單元地址為從0開始的連續(xù)正整數(shù)。0123m-2m-1

任務(wù)二

活動1設(shè)計校園數(shù)據(jù)的存儲方式

任務(wù)二

活動1設(shè)計校園數(shù)據(jù)的存儲方式對內(nèi)存單元數(shù)據(jù)的存取都通過地址進行，數(shù)據(jù)對象可能占據(jù)多個內(nèi)存單元。如何獲取數(shù)據(jù)對象的內(nèi)存地址及其所占內(nèi)存單元數(shù)量？Python語言中內(nèi)置了返回數(shù)據(jù)對象的地址及其所占內(nèi)存單元數(shù)量的函數(shù)。i()函數(shù)返回數(shù)據(jù)對象的地址，數(shù)據(jù)對象的__sizeof__

方法則返回數(shù)據(jù)對象的“尺寸”，即占據(jù)內(nèi)存單元的數(shù)量。語句a=2018，將整數(shù)對象2018賦值給變量a，通過id(a)知道整數(shù)對象的地址;a.__sizeof__()則返回整數(shù)對象占用的內(nèi)存單元數(shù)量。返回數(shù)據(jù)對象的地址返回數(shù)據(jù)對象占據(jù)內(nèi)存單元的數(shù)量3.上機練習練一練變量名地址長度countermilesname

任務(wù)二

活動1設(shè)計校園數(shù)據(jù)的存儲方式以下代碼是在Python中對變量的賦值，請根據(jù)提示完成下表。01.counter=100

#整型變量02.miles=1000.0

#浮點型變量03.name="alice"

#字符串2824544.自主探究數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示方式稱為存儲結(jié)構(gòu)，存儲結(jié)構(gòu)的不同主要體現(xiàn)在數(shù)據(jù)元素之間相鄰關(guān)系的表示上，多個數(shù)據(jù)元素之間的相鄰關(guān)系則既可以按順序依次存儲來表示，也可以通過記錄相鄰數(shù)據(jù)元素的地址來鏈接引用。

任務(wù)二

活動2設(shè)計圖書數(shù)據(jù)的存儲方式存儲單元中可以存放數(shù)據(jù)，并通過地址來訪問，數(shù)據(jù)可能會占據(jù)多個存儲單元。同時存儲單元中也可以存放地址，這樣邏輯上相鄰的數(shù)據(jù)，不必存放在相鄰的存儲單元，可以通過鏈接地址來引用。假設(shè)圖書管理系統(tǒng)為每一本圖書的數(shù)據(jù)分配了32個字節(jié)來保存索書號和書名，并將書架上的書按照順序來存儲。請仔細觀察下圖，填寫其中的圖書數(shù)據(jù)和相應(yīng)的內(nèi)存單元地址。

任務(wù)二

活動2設(shè)計圖書數(shù)據(jù)的存儲方式160101詩經(jīng)……地址65536地址66016160116西游記160117三國演義160118紅樓夢160119水滸傳地址

地址地址660486608066112

任務(wù)二

活動2設(shè)計圖書數(shù)據(jù)的存儲方式地址65536地址66016地址66048地址66080地址66112……在這種相鄰存儲的結(jié)構(gòu)中，數(shù)據(jù)元素占據(jù)的內(nèi)存單元數(shù)量是固定的，只要知道了前一個數(shù)據(jù)元素的地址，就能確定下一個數(shù)據(jù)元素的地址。圖書數(shù)據(jù)地址=

+（索書號-

）*

6553616010132實際上，每個數(shù)據(jù)元素的地址構(gòu)成一個等差數(shù)列，其首項為第一個數(shù)據(jù)元素的地址，公差為數(shù)據(jù)元素的大小尺寸，其通項的下標可以用索書號來表示。把邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置上相鄰的存儲單元中，數(shù)據(jù)元素之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，這種存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)。

任務(wù)二

活動2設(shè)計圖書數(shù)據(jù)的存儲方式順序存儲結(jié)構(gòu)節(jié)省存儲空間。實現(xiàn)對數(shù)據(jù)元素的隨機存取，即每一個數(shù)據(jù)元素對應(yīng)個序號，由該序號可以直接計算出數(shù)據(jù)元素的存儲地址。VS不便于修改，對數(shù)據(jù)元素的插入、刪除運算要移動一系列的數(shù)據(jù)元素。社團數(shù)據(jù)的組織方式是樹形結(jié)構(gòu)，數(shù)據(jù)元素之間存在著層次關(guān)系和一對多的關(guān)系。對于這樣的數(shù)據(jù)關(guān)系，如何在內(nèi)存中存儲和表示呢?

任務(wù)二

活動3設(shè)計社團數(shù)據(jù)的存儲方式在制作幻燈片的時候，可以在幻燈片頁面中插入超鏈接，用超鏈接的方式實現(xiàn)頁面之間的任意跳轉(zhuǎn)，完成非順序播放的效果?；脽羝锏某溄樱鋵嵕褪潜４媪肆硪粡埢脽羝奈恢?，當單擊超鏈接的時候，通過位置定位指向另外一張幻燈片。

任務(wù)二

活動3設(shè)計社團數(shù)據(jù)的存儲方式根據(jù)超鏈接的思路，在內(nèi)存里除了存儲數(shù)據(jù)元素外，還可以存儲指向另一個數(shù)據(jù)元素的地址，這樣數(shù)據(jù)元素之間的關(guān)系就可以通過鏈接來表示了?！瓟?shù)據(jù)1地址2…數(shù)據(jù)3…數(shù)據(jù)2地址3…采取地址引用來鏈接數(shù)據(jù)元素，可以使邏輯上相鄰的數(shù)據(jù)元素在物理上不必相鄰，這樣就增加了數(shù)據(jù)操作的靈活性，尤其是插入數(shù)據(jù)元素時，不需要移動其他數(shù)據(jù)元素就可以完成此操作。

任務(wù)二

活動3設(shè)計社團數(shù)據(jù)的存儲方式數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)3數(shù)據(jù)4^Head數(shù)據(jù)1數(shù)據(jù)2Head數(shù)據(jù)3數(shù)據(jù)4^數(shù)據(jù)5

任務(wù)二

活動3設(shè)計社團數(shù)據(jù)的存儲方式下圖是學校藝術(shù)社團的組織結(jié)構(gòu)圖，請利用地址引用鏈接數(shù)據(jù)元素的方式，將藝術(shù)社團的數(shù)據(jù)存儲在表格所示的內(nèi)存單元中。

任務(wù)二

活動3設(shè)計社團數(shù)據(jù)的存儲方式藝術(shù)社團左右合唱團舞蹈團左右左右通俗合唱團左^右^美聲合唱團左^右^民族舞團左^右^現(xiàn)代舞團左^右^

任務(wù)二

活動2設(shè)計圖書數(shù)據(jù)的存儲方式在數(shù)據(jù)元素中附加存儲一個或多個內(nèi)存地址，指向邏輯上相鄰的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系不依賴于其所在的內(nèi)存單元順序，這種存儲結(jié)構(gòu)稱為鏈式存儲結(jié)構(gòu)。鏈式存儲結(jié)構(gòu)靈活。在數(shù)據(jù)元素中附加多個內(nèi)存地址，不僅可以實現(xiàn)線性結(jié)構(gòu)的存儲，還可實現(xiàn)樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)的存儲。VS操作比較復(fù)雜，且需要額外的存儲空間來保存鏈接地址。什么是數(shù)據(jù)結(jié)構(gòu)

任務(wù)二

活動1設(shè)計校園數(shù)據(jù)的存儲方式數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)并不是一一對應(yīng)的關(guān)系，每一種邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)，既可以用順序存儲結(jié)構(gòu)來實現(xiàn)也可以用鏈式存儲結(jié)構(gòu)來實現(xiàn)。5.課堂小結(jié)本節(jié)課通過幾個與校園生活密切相關(guān)的案例，展現(xiàn)了數(shù)據(jù)組織的三種邏輯結(jié)構(gòu)和兩種存儲結(jié)構(gòu)，包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)