數(shù)據(jù)的組織　　 【核心知識精講精析】 浙教版（2019）高中信息技術(shù)選修1

選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》第一章數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.2數(shù)據(jù)的組織什么是數(shù)據(jù)結(jié)構(gòu)根據(jù)問題求解的需要，對數(shù)據(jù)進(jìn)行有效的整理和組織，并以一定的形式加以存儲和表示的過程稱為數(shù)據(jù)結(jié)構(gòu)。瑞士計算機(jī)科學(xué)家沃斯（N.Wirth）曾指出“算法+數(shù)據(jù)結(jié)構(gòu)=程序”數(shù)據(jù)結(jié)構(gòu)的概念

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。圖1.2.1數(shù)據(jù)元素及其包含的數(shù)據(jù)項

圖1.2.1所示二維表中，每一行實際內(nèi)容（也稱為一條記錄）就是數(shù)據(jù)元素，而每個元素又由5個數(shù)據(jù)項（“代碼”“名稱”“最新價格”“動態(tài)市盈”“流通股本”）組成。數(shù)據(jù)項是具有獨(dú)立含義的最小數(shù)據(jù)表示單位。1.數(shù)據(jù)元素（DataElement）數(shù)據(jù)結(jié)構(gòu)的概念2.數(shù)據(jù)類型（DataType）數(shù)據(jù)類型指的是具有相同性質(zhì)的計算機(jī)數(shù)據(jù)的集合及在這個數(shù)據(jù)集合上的一組操作。數(shù)據(jù)類型可以分為基本數(shù)據(jù)類型（也稱為原子數(shù)據(jù)類型）和結(jié)構(gòu)數(shù)據(jù)類型?；緮?shù)據(jù)類型由計算機(jī)編程環(huán)境提供，編程者可以在編程時直接用系統(tǒng)提供的標(biāo)識符進(jìn)行定義，如Python編程語言中的整型、實型、布爾型等。

結(jié)構(gòu)數(shù)據(jù)類型是在程序設(shè)計時利用基本數(shù)據(jù)類型構(gòu)造出的、復(fù)合的新類型。意思是我們把一些不同類型的數(shù)據(jù)組合成一個整體，如一個學(xué)生的學(xué)號、姓名、班級、年齡和成績等，雖然各個屬性分別屬于不同的數(shù)據(jù)類型，但是它們之間密切相關(guān)，各種信息都屬于同一個人。這時，可以聲明一個結(jié)構(gòu)型的數(shù)據(jù)類型，由多種數(shù)據(jù)類型，可以是基本數(shù)據(jù)類型，也可以是自定義的數(shù)據(jù)類型，組成一個集合?；緮?shù)據(jù)類型結(jié)構(gòu)數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)的概念3.數(shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。它包括了以下三個方面的內(nèi)容：①數(shù)據(jù)元素之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。②數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表示，也稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。③數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)施加的操作。如刪除、查找、插入數(shù)據(jù)等常見的數(shù)據(jù)結(jié)構(gòu)——數(shù)組李彤張強(qiáng)胡潔杜剛第1個第2個第3個第4個這批數(shù)據(jù)序列可用數(shù)組“a[1]="李彤"、a[2]="張強(qiáng)"、a[3]="胡潔"、a[4]="杜剛"”來表達(dá)。描述數(shù)據(jù)所處的位置或數(shù)據(jù)之間的前后順序關(guān)系，通過數(shù)組的下標(biāo)可以精確的訪問序列中的某個數(shù)據(jù)元素。常見的數(shù)據(jù)結(jié)構(gòu)——鏈表吳堅知道自己排在首位，王林知道排在自己前面的是吳堅，黃剛知道排在自己前面的是王林，李豐知道排在自己前面的是黃剛。有了這些相鄰人員之間的鏈接關(guān)系，即使休息時大家分散在各處，一旦需要集合，大家可以根據(jù)鏈接關(guān)系快速地按照原順序排成隊伍。雖然整隊前后每個人員的站位地點(diǎn)發(fā)生改變，但相互之間排隊的順序關(guān)系是不變的。只需要知道相鄰人員之間的前后順序關(guān)系，而對每個人員的位置信息并不作要求。常見的數(shù)據(jù)結(jié)構(gòu)——鏈表抽象化后的排隊鏈接關(guān)系

組織、處理一批數(shù)據(jù)時，若不關(guān)心數(shù)據(jù)實際所處的具體位置，而只需知道數(shù)據(jù)之間相互鏈接的順序時，可以借鑒上面的方法。在計算機(jī)科學(xué)中，這種方法的具體實現(xiàn)形式就是鏈表。常見的數(shù)據(jù)結(jié)構(gòu)——鏈表單向鏈表雙向鏈表基于單向鏈表的循環(huán)鏈表指針：用了指示一個數(shù)據(jù)存儲地址的變量。數(shù)據(jù)域單項鏈表的基礎(chǔ)上每個結(jié)點(diǎn)增加一個指向前驅(qū)結(jié)點(diǎn)的連接常見的數(shù)據(jù)結(jié)構(gòu)——隊列有序排隊上車的乘客有序排隊接客的出租車乘客排隊時先到的總是從隊伍的頭部出去（出隊）上車，而后到的乘客則必須在隊伍的尾部加入（入隊）。同時，為了確保有序，人們總是規(guī)定不能從隊伍的中間部位插隊。常見的數(shù)據(jù)結(jié)構(gòu)——隊列

用計算機(jī)程序處理數(shù)據(jù)時，有時也需要將數(shù)據(jù)進(jìn)行“排隊”，并遵循現(xiàn)實中排隊的規(guī)律，對數(shù)據(jù)進(jìn)行“先進(jìn)先出”FIFO（FirstInFirstOut）且中間不能“插隊”的組織和操作，計算機(jī)科學(xué)家由此發(fā)明了“隊列”這種數(shù)據(jù)結(jié)構(gòu)。常見的數(shù)據(jù)結(jié)構(gòu)——棧彈匣的裝彈過程（入棧）子彈進(jìn)出彈匣的過程具有下列特點(diǎn)：①整個裝置只有一端開放（最上端），而且進(jìn)、出只能在這一端進(jìn)行。②彈匣中的子彈成一縱隊排列。③任何子彈進(jìn)出彈匣的規(guī)律是“先進(jìn)后出、后進(jìn)先出”，即最先裝入彈匣的子彈最后才能被彈出，而最后裝入彈匣的子彈則最先被彈出。問題與討論在文字處理軟件Word中輸入若干文字，然后刪除其中部分文字，再輸入若干文字。然后進(jìn)行“撤消”操作（按Ctrl+Z鍵，或者單擊撤消操作快捷按鈕“”）。觀察各個操作后的現(xiàn)象，回答下列問題。（1）根據(jù)“撤消”操作所產(chǎn)生的結(jié)果，說明Word中符號輸入及撤消操作中，內(nèi)部所依托的數(shù)據(jù)結(jié)構(gòu)是哪種數(shù)據(jù)結(jié)構(gòu)？為什么？（2）結(jié)合自己的經(jīng)歷，談?wù)勀男┬畔⑾到y(tǒng)中也采用了棧這種數(shù)據(jù)結(jié)構(gòu)。一筒羽毛球十進(jìn)制轉(zhuǎn)二進(jìn)制拓展鏈接線性表是由零個或多個數(shù)據(jù)元素組成的有限序列，數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系。線性表是一種基本的、常見的數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)需要向線性表中添加或者刪除元素。數(shù)組、隊列、鏈表都是線性表的特殊形式。應(yīng)用實例：現(xiàn)在假設(shè)有7個數(shù)據(jù)元素的線性表，以刪除數(shù)據(jù)元素3為例進(jìn)行分析。53406821、數(shù)組存儲：從a[0]開始找到數(shù)組元素“3”需要查找_______次，刪除“3”后，其后續(xù)數(shù)組元素需要往前移動___________次，a[6]的值為__________2、單鏈表存儲：從第一個結(jié)點(diǎn)的數(shù)據(jù)元素“5”開始找到數(shù)組元素“3”需要查找_______次，刪除該結(jié)點(diǎn)后，其后續(xù)結(jié)點(diǎn)需要往前移動___________次，此時鏈表中數(shù)據(jù)元素的個數(shù)為__________252206應(yīng)用實例：現(xiàn)在假設(shè)有7個數(shù)據(jù)元素的線性表，以刪除數(shù)據(jù)元素3為例進(jìn)行分析。53406823、隊列存儲：從隊首查找到數(shù)組元素“3”需要查找_______次，刪除“3”后，為保持原隊列其他數(shù)據(jù)元素的次序不變，還需要出隊___________次，入隊_______次，次隊列中數(shù)據(jù)元素的個數(shù)為___個。2、棧存儲：從棧頂查找需要出棧_____次找到數(shù)組元素“3”，刪除該元素后，為了保持棧內(nèi)其他元素的次序不變，還需入棧___________次.255621常見的數(shù)據(jù)結(jié)構(gòu)——樹數(shù)據(jù)元素前面只有一個元素，后面可以有0個或多個元素相鄰，所有元素之間的關(guān)系特征像一顆倒放的樹。常見的數(shù)據(jù)結(jié)構(gòu)——樹問題與討論分小組討論，舉出在生活和信息系統(tǒng)中用樹組織數(shù)據(jù)的例子，并用樹結(jié)構(gòu)描述數(shù)據(jù)之間的關(guān)系特征。公司和部門各級領(lǐng)導(dǎo)關(guān)系學(xué)科思維導(dǎo)圖等請畫出其他結(jié)構(gòu)圖？數(shù)據(jù)結(jié)構(gòu)的作用姓名班級滾鐵圈打彈子拍紙板竹蜻蜓跳繩踢毽子陳濤932楊瓊351金凱245吳敏1613朱剛強(qiáng)6517……………………1.設(shè)計算法解決問題離不開數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)統(tǒng)計前，需要先收集數(shù)據(jù)并將數(shù)據(jù)按照既有的邏輯關(guān)系進(jìn)行結(jié)構(gòu)化組織，可以用一張表格來組織數(shù)據(jù)并表示數(shù)據(jù)之間的邏輯關(guān)系。數(shù)據(jù)結(jié)構(gòu)的作用2.不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同xm(i)bj(i)d1(i)d2(i)d3(i)d4(i)d5(i)d6(i)sum(i)陳濤9302000楊瓊3000051金凱2045000吳敏1610300朱剛強(qiáng)6501070……………………其中的bjdf(j)表示第j班的總分（1）用一維數(shù)組組織數(shù)據(jù)程序代碼：數(shù)據(jù)結(jié)構(gòu)的作用2.不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同xm(i)a(i,1)a(i,2)a(i,3)a(i,4)a(i,5)a(i,6)a(i,7)a(i,8)陳濤9302000楊瓊3000051金凱2045000吳敏1610300朱剛強(qiáng)6501070……………………（2）用二維數(shù)組組織數(shù)據(jù)程序代碼：其中的bjdf(j)表示第j班的總分?jǐn)?shù)據(jù)結(jié)構(gòu)的作用2.不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同二維數(shù)組程序?qū)崿F(xiàn)：一維數(shù)組程序?qū)崿F(xiàn)：不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同數(shù)據(jù)合并案例生產(chǎn)廠家總會根據(jù)各地產(chǎn)品銷量的數(shù)據(jù)分析來預(yù)估市場情況，并為后續(xù)調(diào)整生產(chǎn)規(guī)劃、完善營銷策略提供依據(jù)。

由于數(shù)據(jù)量巨大，為了充分運(yùn)用分布式處理的優(yōu)勢，總部會要求各下屬地區(qū)上報數(shù)據(jù)時，按各產(chǎn)品銷量進(jìn)行從大到小的排序?？偛渴盏綌?shù)據(jù)后的第一件事是將所有數(shù)據(jù)合并并按照銷量進(jìn)行降序排序（從大到?。瑸榱送瓿蓴?shù)據(jù)合并和整理工作，總部數(shù)據(jù)分析員小剛需要設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)和算法。不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同分析：

小剛可以用一個二維數(shù)組存儲所有下屬地區(qū)的產(chǎn)品銷量數(shù)據(jù)，然后直接運(yùn)用排序算法進(jìn)行降序排序。如果利用既有數(shù)據(jù)已是分塊有序的特點(diǎn)，設(shè)計新的數(shù)據(jù)結(jié)構(gòu)和算法，則處理效率可以得到相應(yīng)的提升。

各個地區(qū)的數(shù)據(jù)合并問題可以簡化為2個地區(qū)的數(shù)據(jù)合并問題，當(dāng)2個地區(qū)的數(shù)據(jù)合并完成后，剩余各地區(qū)的數(shù)據(jù)合并就可以按照同樣方式完成。因此，接下來著重分析2個地區(qū)的數(shù)據(jù)合并問題。不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同第一步抽象與建模設(shè)第1個地區(qū)共有n個產(chǎn)品銷量數(shù)據(jù)，第2個地區(qū)共有m個產(chǎn)品銷量數(shù)據(jù)。為了簡化描述，突出核心部分的分析，考慮將問題抽象為n個有序整數(shù)和m個有序整數(shù)的合并問題，具體的問題模型如下：已知一個降序排列的整數(shù)數(shù)列A：a1，a2，a3，…，an以及一個降序排列的整數(shù)數(shù)列B：b1，b2，b3，…，bm

，將兩個數(shù)列合并形成一個新的有序數(shù)列C，使新數(shù)列仍按降序排列，即c1≥c2≥c3≥…≥ck≥ck+1≥…≥cn+m（其中ck∈A或者ck∈B）。請完成解決該問題的數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計。不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同第二步設(shè)計、描述算法1.基于數(shù)組的算法設(shè)計與描述（1）將數(shù)組a中所有元素存儲到數(shù)組c的前n個位置中；1234519161285a191612851234519161285b20151410412345678910c12345678910不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同第二步設(shè)計、描述算法1.基于數(shù)組的算法設(shè)計與描述（2）變量p賦值為0，將表示數(shù)組c中有效元素總個數(shù)的變量tot賦值為n；1234519161285a191612851234519161285b201514104c-1-1-1-1-10iptot12345678910不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同（3）將數(shù)組b中元素b(i)逐個插入到數(shù)組c中（1≤i≤m）：1916128512345201514104b201514104c-1-1-1-1-10iptot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時tot值增加1；④如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個位置，然后將b(i)存儲到c(p)中，同時tot值增加1。12345678910不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同（4）將數(shù)組b中元素b(i)逐個插入到數(shù)組c中（1≤i≤m）：1916128512345201514104b201514104c-1-1-1-10iptot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時tot值增加1；④如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個位置，然后將b(i)存儲到c(p)中，同時tot值增加1。pp②如果c(p)＞b(i)，那么使p值增加1；12345678910不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同（4）將數(shù)組b中元素b(i)逐個插入到數(shù)組c中（1≤i≤m）：1916128512345201514104b201514104c-1-1-10itot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接將b(i)存儲到c(p)中，同時tot值增加1；④如果c(p)≤b(i)，那么依次將c(tot)，c(tot–1)，…，c(p)向右移動一個位置，然后將b(i)存儲到c(p)中，同時tot值增加1。p12345678910不同數(shù)據(jù)結(jié)構(gòu)會導(dǎo)致處理效率的不同（4）將數(shù)組b中元素b(i)逐個插入到數(shù)組c中（1≤i≤m）：1916128512345201514104b201514104c-1-10itot①p值