資源簡介

(共47張PPT)
1.2數(shù)據(jù)的組織結(jié)構(gòu)
高中信息技術(shù)/教科版/選擇性必修1
目錄
1.情景導(dǎo)入
2.新知講授
3.上機練習(xí)
4.自主探究
5.課堂小結(jié)
6.拓展練習(xí)
1.情境導(dǎo)入
隨著信息技術(shù)的普及和深入應(yīng)用，人們需要面對越來越多的數(shù)據(jù)資源，如圖書館中海量的圖書數(shù)據(jù)、學(xué)校里教職員工和學(xué)生的數(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)。超市的商品銷售管理、倉庫賬目管理、學(xué)校食堂就餐刷卡消費記錄等也都采用線性結(jié)構(gòu)來組織數(shù)據(jù)。
任務(wù)一 活動2探究學(xué)生社團的數(shù)據(jù)組織方式
學(xué)生社團組織結(jié)構(gòu)之間存在什么樣的關(guān)系呢？
想一想
學(xué)生社團組織機構(gòu)存在一種層次關(guān)系，一個上層機構(gòu)可以關(guān)聯(lián)多個下層結(jié)構(gòu)。
任務(wù)一 活動2探究學(xué)生社團的數(shù)據(jù)組織方式
假設(shè)把學(xué)生社團組織機構(gòu)抽象成一個數(shù)據(jù)集合，那么每個機構(gòu)就是這個集合中的一個數(shù)據(jù)元素。請分析以下問題：
1.學(xué)生社團中心和各分社團之間存在什么樣的關(guān)系？
2.科技社團包含哪幾個社團？藝術(shù)社團包含哪幾個社團？
3.信息學(xué)奧賽和生物學(xué)奧賽均屬于什么社團？
存在一對多的對應(yīng)關(guān)系，以及上下層的對應(yīng)關(guān)系。
科技社團包含航模社團、DI社團、機器人社團；
藝術(shù)社團包含合唱團和舞蹈團。
學(xué)科競賽社團
任務(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ù)組織方式
學(xué)校商店
學(xué)生餐廳
高中教學(xué)樓
學(xué)校正門
幼兒園
圖書館
教師辦公樓
學(xué)生宿舍
初中教學(xué)樓
學(xué)校公園
（ ）
（ ）
補全空缺元素
體育運動中心
實驗樓
如果從學(xué)校正門出發(fā)，到達學(xué)校公園，寫出至少3條參觀路線。
學(xué)校商店
學(xué)生餐廳
高中教學(xué)樓
學(xué)校正門
幼兒園
圖書館
教師辦公樓
學(xué)生宿舍
初中教學(xué)樓
學(xué)校公園
體育運動中心
實驗樓
方 案 1
學(xué)校商店
學(xué)生餐廳
高中教學(xué)樓
學(xué)校正門
幼兒園
圖書館
教師辦公樓
學(xué)生宿舍
初中教學(xué)樓
學(xué)校公園
體育運動中心
實驗樓
方 案 2
學(xué)校商店
學(xué)生餐廳
高中教學(xué)樓
學(xué)校正門
幼兒園
圖書館
教師辦公樓
學(xué)生宿舍
初中教學(xué)樓
學(xué)校公園
體育運動中心
實驗樓
方 案 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ù)。
0
1
2
3
m-2
m-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.上機練習(xí)
練一練
變量名 地址 長度
counter
miles
name
任務(wù)二 活動1設(shè)計校園數(shù)據(jù)的存儲方式
以下代碼是在Python中對變量的賦值，請根據(jù)提示完成下表。
01. counter=100 #整型變量
02. miles=1000.0 #浮點型變量
03. name="alice" #字符串
28
24
54
1554397400400
1554431599728
1554433069680
4.自主探究
數(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
地址66016
160116西游記
160117三國演義
160118紅樓夢
160119水滸傳
地址
地址
地址
66048
66080
66112
任務(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ù)地址= +（索書號- ）*
65536
160101
32
實際上，每個數(shù)據(jù)元素的地址構(gòu)成一個等差數(shù)列，其首項為第一個數(shù)據(jù)元素的地址，公差為數(shù)據(jù)元素的大小尺寸，其通項的下標(biāo)可以用索書號來表示。
把邏輯上相鄰的數(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)，完成非順序播放的效果。
幻燈片里的超鏈接，其實就是保存了另一張幻燈片的位置，當(dāng)單擊超鏈接的時候，通過位置定位指向另外一張幻燈片。
任務(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ù)2
Head
數(shù)據(jù)3
數(shù)據(jù)4
^
數(shù)據(jù)5
任務(wù)二 活動3設(shè)計社團數(shù)據(jù)的存儲方式
下圖是學(xué)校藝術(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)稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。
鏈?zhǔn)酱鎯Y(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)也可以用鏈?zhǔn)酱鎯Y(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é)構(gòu)等邏輯結(jié)構(gòu)以及順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)等存儲結(jié)構(gòu)。
6.拓展練習(xí)
拓展練習(xí)
在學(xué)校藝術(shù)社團組織結(jié)構(gòu)圖上從左到右依次標(biāo)記數(shù)字，如圖所示。
①
②
③
④
⑤
⑥
⑦
拓展練習(xí)
（1）根據(jù)順序標(biāo)號畫出該社團組織的順序存儲結(jié)構(gòu)，完成下圖。
藝術(shù)社團
合唱團
舞蹈團
1
2
3
4
5
6
7
通俗合唱團
美聲合唱團
民族舞團
現(xiàn)代舞團
（2）通過觀察上下層順序標(biāo)號間的關(guān)系，得出已知一個數(shù)據(jù)元素的地址，求左右分支地址的通用公式。
假設(shè)一個數(shù)據(jù)元素的標(biāo)號是X，那么做分支數(shù)據(jù)元素的標(biāo)號是X*2，右分支數(shù)據(jù)元素的標(biāo)號是X*2+1。
下節(jié)課見！

展開更多......

收起↑