項目二+研究學(xué)校教學(xué)管理相關(guān)數(shù)據(jù)的組織處理-+初識數(shù)據(jù)結(jié)構(gòu)-高中信息技術(shù)同步精品課堂（滬科版2019選擇性必修1）

項目二研究學(xué)校教學(xué)管理相關(guān)數(shù)據(jù)的組織處理

—初識數(shù)據(jù)結(jié)構(gòu)010203熟悉數(shù)據(jù)結(jié)構(gòu)，了解數(shù)據(jù)結(jié)構(gòu)在解決問題時的作用。理解學(xué)生基本數(shù)據(jù)之間有的內(nèi)在關(guān)系以及處理這些數(shù)據(jù)的時候如何存儲。學(xué)習(xí)目標(biāo)了解數(shù)據(jù)對象、數(shù)據(jù)元素和數(shù)據(jù)項的定義。04了解抽象數(shù)據(jù)類型以及熟練掌握抽象數(shù)據(jù)類型的作用。01問題導(dǎo)入導(dǎo)入某學(xué)校為了對學(xué)生進行管理，每年新生入校都要登記注冊各種信息，諸如姓名、性別、出生日期、家庭地址等。學(xué)校要為每位新生分配班級學(xué)號。中途學(xué)生轉(zhuǎn)學(xué)轉(zhuǎn)班，學(xué)校要刪除或修改學(xué)生信息。那同學(xué)們知道怎么操作才能方便快捷的整理這些信息么？1.從教學(xué)管理相關(guān)數(shù)據(jù)認(rèn)識數(shù)據(jù)的邏輯結(jié)構(gòu)表中的每一行構(gòu)成一個學(xué)生的一條信息，包括學(xué)號、姓名、性別、出生日期等?？梢钥闯?，除第一個和最后一個學(xué)生外，每個學(xué)生都分別與前一個學(xué)生和后一個學(xué)生相鄰，形成一對一的關(guān)系。這張按一定順序排列的表，就是解決學(xué)生管理問題的模型（線性表，將在后續(xù)項目詳細展開介紹）。當(dāng)學(xué)生信息被輸入計算機后，就成為計算機處理的對象。表中每一行代表一條學(xué)生基本數(shù)據(jù)，稱為數(shù)據(jù)元素，它由學(xué)號、姓名、性別、出生日期等組成，其中的每一項稱為數(shù)據(jù)項。所有各條學(xué)生基本數(shù)據(jù)一起構(gòu)成一個集合（學(xué)生基本數(shù)據(jù)表），稱為數(shù)據(jù)對象。數(shù)據(jù)元素之間存在一對一的關(guān)系的邏輯結(jié)構(gòu)稱為線性結(jié)構(gòu)。生活中還有很多這樣的例子，如員工管理系統(tǒng)、訂票系統(tǒng)等。在這類問題中，一個共同特點是所處理的對象之間存在簡單的一對一的線性關(guān)系。基于此，可以獲得解決該類問題的數(shù)學(xué)模型。通過設(shè)計算法，計算機能夠完成對這些數(shù)據(jù)元素查找、插入和刪除等操作。這就是一類數(shù)據(jù)結(jié)構(gòu)——線性數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)除了學(xué)科教學(xué)工作外，學(xué)校還有許多教學(xué)管理工作。為了提高管理效率，須按照一定的工作任務(wù)和目標(biāo)，將成員按不同的工作性質(zhì)、職務(wù)、崗位組合起來，形成層次恰當(dāng)、結(jié)構(gòu)合理的有機整體。以班級管理為例，一般學(xué)校都設(shè)有如圖2-2所示的組織管理結(jié)構(gòu)：其中，校長（分管校長）領(lǐng)導(dǎo)各年級組長，各年級組長分別領(lǐng)導(dǎo)本年級各班班主任。他們之間存在著一對多的關(guān)系，所構(gòu)成的邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。邏輯結(jié)構(gòu)為樹形結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)屬于非線性數(shù)據(jù)結(jié)構(gòu)。圖2-2班級管理組織結(jié)構(gòu)示例上述學(xué)生信息表存儲到計算機內(nèi)時，不僅要存儲每一條學(xué)生基本數(shù)據(jù)，還要借助它們在存儲器中的相對位置來表示線性關(guān)系。表2-2所示的是學(xué)生信息表的一種存儲結(jié)構(gòu)。假設(shè)存儲地址為一個十進制數(shù)（實際存儲地址是一串二進制數(shù)），首地址為200，每條學(xué)生基本數(shù)據(jù)占用30個存儲單元（一個存儲單元的大小為一個字節(jié)），即一條數(shù)據(jù)的存儲空間大小為30個字節(jié)。2.了解教學(xué)管理相關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)從上圖中看到數(shù)據(jù)元素是按照學(xué)生信息表中的順序依次存儲在地址連續(xù)的存儲空間中的，一對一的邏輯關(guān)系從存儲位置的前后順序能直接反映出來。如第一個學(xué)生楊陽的數(shù)據(jù)存儲在地址為200的存儲空間內(nèi)，它后續(xù)的盧聲凱的數(shù)據(jù)就存儲在地址為230的存儲空間內(nèi)，以此類推，依次由低地址向高地址存儲，直到存儲好最后一個數(shù)據(jù)元素。思考與討論如果存儲地址不連續(xù)，是否能表示線性關(guān)系？除了順序存儲結(jié)構(gòu)外，還可以用其他方式來存儲數(shù)據(jù)元素。假定給數(shù)據(jù)元素（每條學(xué)生記錄）附加一個后繼結(jié)點的地址，用于存放下一個數(shù)據(jù)元素的存儲地址，則可得到表2-3所示的存儲結(jié)構(gòu)。鏈?zhǔn)絻Υ娼Y(jié)構(gòu)在這種存儲方式下，數(shù)據(jù)元素的存儲地址可以是連續(xù)的，也可以是不連續(xù)的。每個存儲空間存儲了數(shù)據(jù)元素（稱為數(shù)據(jù)域）和后繼結(jié)點（下一個數(shù)據(jù)元素）的存儲地址（稱為指針域），地址0表示結(jié)束。這一存儲方式也可以用圖2-4表示。這種存儲結(jié)構(gòu)稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。3.了解數(shù)據(jù)類型和抽象數(shù)據(jù)類型計算機的內(nèi)存容量是有限的，而做兩個個位數(shù)的加法或兩個位數(shù)不同的小數(shù)的加法，顯然需要的空間大小可以不同。計算機研究者通過對不同數(shù)據(jù)進行分類的方法——數(shù)據(jù)類型，來描述不同數(shù)據(jù)的集合，為不同類型的數(shù)據(jù)分配了大小恰當(dāng)?shù)膬?nèi)存空間。所有高級語言都定義了一系列的數(shù)據(jù)類型。以Python語言為例，基本數(shù)據(jù)類型也可以分為：?原子類型——數(shù)字型（numbers，包括整型int和實數(shù)型float）、字符串型（string）?結(jié)構(gòu)類型——元組（tuple）、列表（list）、字典（dict）教學(xué)管理數(shù)據(jù)中，班級學(xué)生人數(shù)是整型，學(xué)生成績是實數(shù)型，學(xué)生的姓名是字符串型等。除了上述基本數(shù)據(jù)類型外，Python語言還通過定義類（class）來實現(xiàn)結(jié)構(gòu)類型。例如，用“classstudent：”就可以定義包含學(xué)號、姓名等多個數(shù)據(jù)項的結(jié)構(gòu)類型。這時，student就相當(dāng)于是一種記錄類型，student的變量（一般稱對象）就可以存放學(xué)生信息數(shù)據(jù)元素了。數(shù)據(jù)類型還有一個作用是定義了對數(shù)據(jù)的一些操作。這些操作在程序設(shè)計語言中是直接使用運算符或函數(shù)來實現(xiàn)的，如將班級學(xué)生人數(shù)相加得出年級學(xué)生人數(shù)，在Python中為T=a1+a2+a3+a4（假設(shè)有4個班級，每個班級的人數(shù)分別為a1、a2、a3、a4），這就是基于整數(shù)類型上的一種操作（加法運算）。計算機編程者在編程時，不需要關(guān)心整數(shù)在計算機中是如何表示的，計算機是如何分配相應(yīng)的存儲空間，如何實現(xiàn)加法操作的。事實上，各種計算機，不管是大型機、小型機、PC、平板電腦、PDA，甚至是智能手機都擁有“整數(shù)”類型，也需要整數(shù)間的運算，實現(xiàn)方法可能有所不同，但在計算機編程者看來，它們都是相同的，原因就在于整數(shù)類型定義的數(shù)學(xué)特性相同。這就是抽象的意義。從這個層面來看，整型其實是一個抽象數(shù)據(jù)類型。當(dāng)然，抽象數(shù)據(jù)類型不僅僅指已經(jīng)定義并實現(xiàn)的數(shù)據(jù)類型（如整型、字符串型等），還可以是計算機編程者對現(xiàn)實問題進行抽象后，在設(shè)計軟件程序時自己定義的數(shù)據(jù)類型。以學(xué)生信息管理問題為例，對其進行抽象后，可以得出數(shù)據(jù)對象是學(xué)生信息這一數(shù)據(jù)元素的集合，此集合中數(shù)據(jù)元素之間的關(guān)系是一對一的線性關(guān)系。如果在此數(shù)學(xué)模型基礎(chǔ)上定義插入、刪除等一組基本操作，就形成一種抽象數(shù)據(jù)類型。該抽象數(shù)據(jù)類型可以如下所示：抽象數(shù)據(jù)類型中被定義過的基本操作，是通過編寫出相應(yīng)的程序模塊實現(xiàn)的。以后用計算機解決此類問題時，凡是要用到這些基本操作，直接調(diào)用這些程序模塊即可，而不必每次重新編寫程序，大大降低了程序員的重復(fù)勞動。例如，將某兩個班級的學(xué)生數(shù)據(jù)定義為上述抽象數(shù)據(jù)類型后，調(diào)用其基本操作（如下面代碼中框出的部分）就可以實現(xiàn)將兩個班學(xué)生數(shù)據(jù)的合并（用Python語言編寫）。1.Python中列表屬于抽象數(shù)據(jù)類型嗎？為什么？2.使用抽象數(shù)據(jù)類型有何好處？02知識鏈接1.數(shù)據(jù)數(shù)據(jù)是對客觀事物的描述，是記錄下來的某種可以識別的符號，在計算機科學(xué)中，數(shù)據(jù)是指所有能被輸入計算機中，且能被計算機處理的符號的集合，是計算機加工處理的對象。這些符號必須具備兩個前提：可以輸入到計算機中和能被計算機程序處理。例如，學(xué)生基本信息輸入到計算機中后，可以通過計算機程序進行插入、修改等處理。數(shù)據(jù)不僅僅包括數(shù)值型數(shù)據(jù)，還包括字符、圖像等非數(shù)值型數(shù)據(jù)。2.數(shù)據(jù)元素數(shù)據(jù)元素是組成數(shù)據(jù)的、有一定意義的基本單位，是數(shù)據(jù)這個集合中的個體，也被稱為記錄。如表現(xiàn)在“學(xué)生基本信息表”中，就是某一學(xué)生的一條記錄。3.數(shù)據(jù)項數(shù)據(jù)項是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，“學(xué)生基本信息表”中每個學(xué)生的學(xué)號、姓名、性別等都是數(shù)據(jù)項。4.數(shù)據(jù)對象數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。例如，整數(shù)數(shù)據(jù)對象是集合N={...，-2，-1，0，1，2，...}，字母字符數(shù)據(jù)對象是集合C={A，B，...，Z，a，b，...z}，而學(xué)生基本信息表也是一個數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，涉及邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及運算（操作）三個方面。1.邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系。它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有四類基本結(jié)構(gòu)，如圖2-5所示。它們的復(fù)雜程度依次遞進。（1）集合結(jié)構(gòu)。這種結(jié)構(gòu)的數(shù)據(jù)元素除了同屬于一個集合外，它們之間沒有其他關(guān)系。各個數(shù)據(jù)元素是“平等”的，它們的共同屬性是“同屬于一個集合”。例如，一組隨機沒有規(guī)律的數(shù)字組成的集合，就是一個集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)。這種結(jié)構(gòu)的數(shù)據(jù)元素之間是一對一的關(guān)系。例如，把學(xué)生信息數(shù)據(jù)按照其入學(xué)報到的時間先后順序進行排列，將構(gòu)成一個線性關(guān)系。（3）樹形結(jié)構(gòu)。這種結(jié)構(gòu)的數(shù)據(jù)元素之間存在一種一對多的關(guān)系。例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。這種結(jié)構(gòu)的數(shù)據(jù)元素是多對多的關(guān)系。例如，若任意兩個城市之間有直線或間接的通信線路，就可構(gòu)成圖狀結(jié)構(gòu)。其中，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)屬于非線性結(jié)構(gòu)。存儲結(jié)構(gòu)存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示，即數(shù)據(jù)元素及其之間的關(guān)系在計算機中的表示，也稱為物理結(jié)構(gòu)。如何反映數(shù)據(jù)元素之間的邏輯關(guān)系，是實現(xiàn)存儲結(jié)構(gòu)的重點和難點。數(shù)據(jù)元素在計算機中有兩種最基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。數(shù)據(jù)元素在計算機內(nèi)可以用一個結(jié)點來表示。（1）順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是把數(shù)據(jù)元素按順序存放在地址連續(xù)的存儲單元中，其數(shù)據(jù)之間的邏輯關(guān)系和存儲關(guān)系是一致的，即借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。計算機會在內(nèi)存儲器中開辟一段地址連續(xù)的存儲單元空間依次存放數(shù)據(jù)，即第一個數(shù)據(jù)放在第一個位置，第二個數(shù)據(jù)放在第二個位置……如圖2-6所示，其中1001，1002…表示存儲地址，d1，d2…表示數(shù)據(jù)。由于只要知道了首地址，就可以隨機存取任意位置上的數(shù)據(jù)元素，所以也可以稱順序存儲結(jié)構(gòu)為隨機存取存儲結(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)無須占用一整塊存儲空間，它把數(shù)據(jù)元素存放在任意的存儲單元中。鏈?zhǔn)酱鎯Y(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰。數(shù)據(jù)元素之間的關(guān)系借助于指針來表示，即給每個數(shù)據(jù)元素附加一個指針用于存放后繼數(shù)據(jù)元素的存儲地址，這樣通過這個存儲地址就可以找到相關(guān)數(shù)據(jù)元素的位置，如圖2-7所示。（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)顯然，鏈?zhǔn)酱鎯Y(jié)構(gòu)存放數(shù)據(jù)時要比順序存儲結(jié)構(gòu)靈活，不用關(guān)心數(shù)據(jù)存在哪里，只要有一個相應(yīng)的存儲地址就能找到它了?？傊?，邏輯結(jié)構(gòu)是面向問題的，而存儲結(jié)構(gòu)是面向計算機的，其目的是將數(shù)據(jù)及其邏輯關(guān)系存儲到計算機內(nèi)存中。數(shù)據(jù)的運算也稱為操作，主要包括對數(shù)據(jù)進行刪除、插入、訪問、修改和查找等。3.運算數(shù)據(jù)結(jié)構(gòu)的作用如今需要用計算機解決大量的非數(shù)值計算問題，這些問題通常不能通過列方程、解方程等數(shù)學(xué)方法求解，而是需要用諸如線性表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)來描述。求解這類問題的做法通常是：（1）從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型；（2）設(shè)計一個解此模型的算法；（3）編程并進行調(diào)試，直至最終得到解答。其中，抽象出數(shù)學(xué)模型，其實質(zhì)是分析問題，從中提取出操作對象，并找出這些操對象之間的關(guān)系，而數(shù)據(jù)結(jié)構(gòu)正是實際問題中的操作對象以及這些對象間關(guān)系的數(shù)學(xué)象。因此，要解決非數(shù)值計算問題，必須研究如何合理組織數(shù)據(jù)，并采用適當(dāng)?shù)拇鎯Y(jié)構(gòu)來存儲，才能設(shè)計出合理的算法，提升程序的運行和存儲效率。這正是數(shù)據(jù)結(jié)構(gòu)的作用所在。數(shù)據(jù)類型數(shù)據(jù)類型是一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。高級程序設(shè)計語言的每一個變量、常量、表達式都有一個所屬的確定的數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了在程序執(zhí)行期間變量或表達式所有可能取值的范圍，以及在這些值上允許進行的操作。例如，某語言整數(shù)類型取值范圍[-maxint,maxint]（maxint是依賴特定的計算機的最大整數(shù)），定義在其上的一組操作為：加、減、乘、除、整除和取模等。按“值”的不同特性，高級程序語言中的數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型，如整型、字符型等，原子類型的值是不可分解的；還有一種是結(jié)構(gòu)類型，是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且每個成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。例如，定義一個記錄類型，記錄包含姓名、性別等。抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型的定義與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)，即只考慮在數(shù)據(jù)元素集合上能完成什么操作，而不考慮如何完成。例如，前面所說的整數(shù)類型，無論加減乘除操作是如何運算的，對于用戶來說，這些操作的性質(zhì)不會變。這就是抽象的意義。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型中對數(shù)據(jù)對象和數(shù)據(jù)運算進行了聲明，對數(shù)據(jù)對象的表示和數(shù)據(jù)