中的數(shù)據(jù)結(jié)構(gòu)

中的數(shù)據(jù)結(jié)構(gòu)第一頁，共三十一頁，2022年，8月28日一、數(shù)據(jù)的組織形式字段：也稱數(shù)據(jù)項，是數(shù)據(jù)中最基本的、不可分的和有名字的數(shù)據(jù)元素。（齒輪零件號、材料牌號、模數(shù)、齒寬等）記錄：相關(guān)的字段組成一個記錄，它是字段的集合。這種記錄也稱為邏輯記錄文件：相同性質(zhì)記錄的集合就是文件。數(shù)據(jù)庫：是存儲在計算機內(nèi)部，可以按需要使用的、通用的、綜合性的、減少重復存儲程序的數(shù)據(jù)的集合。（數(shù)據(jù)庫不只是文件的集合，還蘊涵對文件的重新組織，以便最大限度的減少文件中的重復數(shù)據(jù)，并增強數(shù)據(jù)文件之間和文件數(shù)據(jù)之間的相互聯(lián)系）數(shù)據(jù)庫管理系統(tǒng)（DBMS）：應用程序從數(shù)據(jù)庫中存取數(shù)據(jù)，是在數(shù)據(jù)庫管理系統(tǒng)控制下，根據(jù)應用程序中的命令進行的。第二頁，共三十一頁，2022年，8月28日二、數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指用戶表達數(shù)據(jù)的形式，也稱為數(shù)據(jù)的邏輯描述。分為：順序結(jié)構(gòu)、樹狀結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)。1、順序關(guān)系的數(shù)據(jù)結(jié)構(gòu)（順序結(jié)構(gòu)）是最簡單的邏輯結(jié)構(gòu)，數(shù)據(jù)節(jié)點是順序排列的。因此每一節(jié)點只與它前一個和后一個節(jié)點相聯(lián)系，節(jié)點間只存在著線性位置關(guān)系，故也稱線性并列表。線性并列表是x(1),x(2),…,x(n)(n0)的集合，其約束條件為：當n>0時，x(1)是第一個節(jié)點，第k個節(jié)點x(k)(1<k<n)的前一節(jié)點是x(k-1)，后一節(jié)點是x(k+1)，最后節(jié)點為x(n)。數(shù)組就是該結(jié)構(gòu)的例子。第三頁，共三十一頁，2022年，8月28日在線性并列表中，棧和隊列是用得最廣泛的兩種重要數(shù)據(jù)結(jié)構(gòu)。棧：限定只能在表的一端進行插入和刪除的線性表。該端稱棧頂，另一端稱棧底。遵循“后進先出”原則。機械裝拆是其例子。隊列：限定只能在表的一端進行插入、另一端進行刪除的線性表。插入端稱隊尾，刪除端稱隊首。遵循“先進先出”原則。工件在流水線上的情況是其例子。進棧出棧進隊出隊隊首隊尾棧頂棧底第四頁，共三十一頁，2022年，8月28日2、樹狀層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)（樹狀結(jié)構(gòu)）該結(jié)構(gòu)的數(shù)據(jù)元素之間具有從屬關(guān)系的層次結(jié)構(gòu)。機器部件4部件3部件2部件1組件3組件2組件1零件3零件2零件1AB1B2B3B4C1C2C3D1D2D3樹狀結(jié)構(gòu)只有一個根節(jié)點，稱為樹根。樹狀結(jié)構(gòu)的特點是下一層中的節(jié)點只能有一條連線與它的上一層的一個節(jié)點相連。樹根樹葉子樹根第一層第二層第三層第四層深度：層次數(shù)；度：節(jié)點孩子數(shù)；樹的度：最大的節(jié)點度。第五頁，共三十一頁，2022年，8月28日3、網(wǎng)狀關(guān)系的數(shù)據(jù)結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）該結(jié)構(gòu)能表達數(shù)據(jù)間更復雜的關(guān)系。網(wǎng)狀結(jié)構(gòu)與樹狀結(jié)構(gòu)的主要區(qū)別：樹狀結(jié)構(gòu)的下層節(jié)點只能與一個上層節(jié)點連接，而網(wǎng)狀結(jié)構(gòu)的下層節(jié)點可與幾個上層節(jié)點連接。第六頁，共三十一頁，2022年，8月28日三、數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)即數(shù)據(jù)在計算機內(nèi)的存儲形式。設(shè)計好數(shù)據(jù)的邏輯結(jié)構(gòu)后，系統(tǒng)通過特定的軟件把數(shù)據(jù)以及數(shù)據(jù)間的關(guān)系按一定的形式存入計算機存儲器中，構(gòu)成這些數(shù)據(jù)的存儲結(jié)構(gòu)，即物理結(jié)構(gòu)。把邏輯結(jié)構(gòu)變換成物理結(jié)構(gòu)的過程，稱為映射。邏輯結(jié)構(gòu)設(shè)計一般多從用戶的要求來考慮，而存儲結(jié)構(gòu)設(shè)計除考慮數(shù)據(jù)的邏輯結(jié)構(gòu)外，還要考慮存儲資源的充分利用、減少存取時間、便于數(shù)據(jù)修改、提高系統(tǒng)可靠性等存儲結(jié)構(gòu)本身的一些特點和要求。邏輯結(jié)構(gòu)與物理結(jié)構(gòu)兩者一般不一致，同一邏輯結(jié)構(gòu)可以映射出多種物理結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)有兩種最基本方式：順序式與鏈式。第七頁，共三十一頁，2022年，8月28日1、順序存儲結(jié)構(gòu)數(shù)據(jù)按一定順序連續(xù)存放在計算機的存儲單元中，不使用其它單元作為輔助信息。是一種最簡單的存儲方式，數(shù)據(jù)元素間相隔固定距離，數(shù)據(jù)在邏輯上的順序與它在計算機內(nèi)的順序是一致的。如一元數(shù)組，任一元素A(i)的地址ai,可用公式：

ai=a1+(i-1)l

(l為各數(shù)組元素占用的字節(jié)數(shù)）A(1)A(2)A(3)……A(n-2)A(n-1)A(n)a1a1+la1+2la1+(n-3)la1+(n-2)la1+(n-1)l第八頁，共三十一頁，2022年，8月28日2、鏈式存儲結(jié)構(gòu)存儲單元不是按邏輯結(jié)構(gòu)的順序分配的，數(shù)據(jù)元素在存儲器中可按任意順序存放在任意位置上，數(shù)據(jù)元素的邏輯元素順序與在存儲器內(nèi)部的存放順序可以不同。為了能正確地存放數(shù)據(jù)元素，隨同每一個元素的存儲還必須存儲另一個元素的地址，稱為鏈指針。每個存儲單元由數(shù)據(jù)域和指針域兩部分構(gòu)成。數(shù)據(jù)域存放節(jié)點的值；指針域用來實現(xiàn)關(guān)系，即用來存放與該節(jié)點有某種關(guān)系的節(jié)點的存儲單元地址。這種通過指針來實現(xiàn)邏輯結(jié)構(gòu)中的順序關(guān)系的方法，稱為鏈接法或鏈地址法。第九頁，共三十一頁，2022年，8月28日左圖為磁盤中的實際存儲結(jié)構(gòu)，其存儲結(jié)構(gòu)的模型如右圖。R1R4R2R3R1R2R3R4*數(shù)據(jù)域指針域結(jié)束標記盡管鏈接法的物理存儲結(jié)構(gòu)分散而不按邏輯順序，但通過指針仍可按順序來存儲各記錄，實現(xiàn)邏輯結(jié)構(gòu)的順序關(guān)系。這樣物理存儲獨立于邏輯結(jié)構(gòu)，是鏈式存儲結(jié)構(gòu)的基本特點。第十頁，共三十一頁，2022年，8月28日鏈式存儲需要額外的存儲空間來存放指針，占用的存儲區(qū)域較大。但節(jié)點的插入和刪除比較簡單，可以不改變原來的物理存儲結(jié)構(gòu)，只需要改變相應的指針域數(shù)據(jù)即可實現(xiàn)。R1R2R3R4鏈地址法的數(shù)據(jù)結(jié)構(gòu)又可分為鏈結(jié)構(gòu)、環(huán)結(jié)構(gòu)、樹結(jié)構(gòu)。R5*R6刪除節(jié)點R4插入節(jié)點R610111112131420121314地址142012第十一頁，共三十一頁，2022年，8月28日正向鏈結(jié)構(gòu)R1R2R3R4反向鏈結(jié)構(gòu)R5*R1*R2R3R4R5雙向鏈結(jié)構(gòu)R1*R2R3R4*環(huán)結(jié)構(gòu)R1R2R3R4R5第十二頁，共三十一頁，2022年，8月28日樹結(jié)構(gòu)：在鏈式存儲結(jié)構(gòu)中，可以設(shè)置多個指針，分別指向多個不同的存儲單元，從而可以構(gòu)成多種多樣復雜的物理結(jié)構(gòu)，實現(xiàn)數(shù)據(jù)間更為復雜的邏輯關(guān)系。定長方式：一具有最大度數(shù)的節(jié)點結(jié)構(gòu)作為該樹所有節(jié)點的結(jié)構(gòu)。A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C90000第十三頁，共三十一頁，2022年，8月28日A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C9不定長方式：每個節(jié)點增加一個存放度數(shù)的域，節(jié)點的長度隨著度數(shù)的增加而增加。3324第十四頁，共三十一頁，2022年，8月28日四、二叉樹1、二叉樹的邏輯結(jié)構(gòu)二叉樹是一種不同于樹的數(shù)據(jù)結(jié)構(gòu)，它的每個節(jié)點至多有兩棵子樹，子樹有左右之分，即不能顛倒。二叉樹可以是空的，其深度與度的定義與樹同。滿二叉樹：深度為k的有2k-1個節(jié)點的二叉樹。順序二叉樹：深度為k、節(jié)點為n的二叉樹，它從1到n的序號與深度為k的滿二叉樹的節(jié)點序號相同。完全二叉樹：節(jié)點的度數(shù)或者為0、或者為2的二叉樹。第十五頁，共三十一頁，2022年，8月28日2、二叉樹的存儲結(jié)構(gòu)對于滿二叉樹或順序二叉樹：可用順序存儲形式。對于節(jié)點i，若i=1，此節(jié)點是根節(jié)點；若i=k，k/2是節(jié)點i的雙親節(jié)點,節(jié)點2k是節(jié)點i的左孩子,節(jié)點2k+1是節(jié)點i的右孩子。對于一般二叉樹：通常采用鏈表結(jié)構(gòu)。此存儲結(jié)構(gòu)特點：節(jié)省存儲空間，可用公式隨機地訪問每個節(jié)點和它的雙親節(jié)點及左、右孩子，但不便于刪除或插入運算。該存儲結(jié)構(gòu)會多占一些存儲空間，但便于刪除或插入運算。每個節(jié)點設(shè)三個域：值域存放節(jié)點的值，左子樹域存放左子樹的地址，右子樹域存放右子樹的地址。第十六頁，共三十一頁，2022年，8月28日3、二叉樹的遍歷遍歷二叉樹是按一定的規(guī)律走遍二叉樹的的每個節(jié)點，使每個節(jié)點被訪問一次且只訪問一次。即按一定規(guī)律將二叉樹的的節(jié)點排成一個線性序列。由于二叉樹是由根節(jié)點、左子樹、右子樹三個基本單元組成的，若能依次遍歷著三部分信息，就能遍歷整個二叉樹。按根節(jié)點、左子樹、右子樹三者不同的先后次序遍歷，可得到六種遍歷二叉樹的方案，即：根節(jié)點、左子樹、右子樹左子樹、根節(jié)點、右子樹左子樹、右子樹、根節(jié)點根節(jié)點、右子樹、左子樹右子樹、根節(jié)點、左子樹右子樹、左子樹、根節(jié)點左邊三種是按照先左后右的次序，是常用的遍歷方式。第十七頁，共三十一頁，2022年，8月28日先序遍歷先序遍歷的次序是：若二叉樹為空，則退出；否則，訪問根節(jié)點，遍歷左子樹，遍歷右子樹，退出。ABDHECFGIVoidpreorder(structbtree*node){if(!node)return;printf(“%d”,node->data);preorder(node->lchild);preorder(node->rchild);}第十八頁，共三十一頁，2022年，8月28日中序遍歷中序遍歷的次序是：若二叉樹為空，則退出；否則，遍歷左子樹，訪問根節(jié)點，遍歷右子樹，退出。ABDHECFGIVoidinorder(structbtree*node){if(!node)return;inorder(node->lchild);printf(“%d”,node->data);inorder(node->rchild);}第十九頁，共三十一頁，2022年，8月28日后序遍歷后序遍歷的次序是：若二叉樹為空，則退出；否則，遍歷左子樹，遍歷右子樹，訪問根節(jié)點，退出。ABDHECFGIVoidpostorder(structbtree*node){if(!node)return;postorder(node->lchild);postorder(node->rchild);printf(“%d”,node->data);}第二十頁，共三十一頁，2022年，8月28日4、樹的二叉樹表示一般的樹可以轉(zhuǎn)換為二叉樹。當以鏈表作為樹的存儲結(jié)構(gòu)時，樹的先序遍歷與后序遍歷可借用遍歷二叉樹的方法。樹轉(zhuǎn)化為二叉樹的規(guī)則：樹的根節(jié)點作為二叉樹的根節(jié)點；根節(jié)點最左端的孩子作為二叉樹的左子樹；根節(jié)點左端第二個孩子是左端第一個孩子的右子樹。樹轉(zhuǎn)化為二叉樹的過程：保留每個節(jié)點與最左孩子的邊，去掉其余邊；連接每個節(jié)點與其原相鄰兄弟節(jié)點的邊；以樹根節(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)45°，即可。第二十一頁，共三十一頁，2022年，8月28日示例說明ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI保留去掉連邊轉(zhuǎn)旋第二十二頁，共三十一頁，2022年，8月28日五、圖形數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)是數(shù)據(jù)及其關(guān)系的抽象表示，此處圖形數(shù)據(jù)結(jié)構(gòu)指的是直接存入計算機內(nèi)的存儲結(jié)構(gòu)。圖形數(shù)據(jù)可分為幾何信息與拓撲信息兩大類。幾何信息是表示構(gòu)成圖形的幾何元素的量值大小。拓撲信息是表示圖形的幾何元素之間的連接關(guān)系。第二十三頁，共三十一頁，2022年，8月28日1、確定圖形形狀的完整信息圖形形狀的信息包括兩個方面：頂點信息（幾何信息）與連接關(guān)系信息（拓撲信息）。表2給出了長方體各頂點的坐標值，是最基本信息（幾何信息）。表3表示了各邊的起點號與終點號，體現(xiàn)出頂點與邊之間的聯(lián)系，是長方體的拓撲信息。它們共同構(gòu)成了長方體最基本的圖形形狀信息數(shù)據(jù)。第二十四頁，共三十一頁，2022年，8月28日說明幾何信息與拓撲信息缺一不可。只有連接關(guān)系而無頂點信息，不能繪出圖形；只有頂點信息而無連接關(guān)系，也不能唯一地確定圖形形狀，往往會產(chǎn)生二義性。第二十五頁，共三十一頁，2022年，8月28日2、單個三維形體的存儲結(jié)構(gòu)目前采用的三維形體的數(shù)據(jù)結(jié)構(gòu)有三種：單鏈三表結(jié)構(gòu)、雙鏈表的翼邊結(jié)構(gòu)、雙鏈三表結(jié)構(gòu)。若不考慮形體之間的相互聯(lián)系，而只研究一個形體在計算機內(nèi)的表示，則通常只需要面、棱邊、頂點三張表，用單鏈指示它們之間的連接關(guān)系即可，即單鏈三表結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)關(guān)系清楚，節(jié)省存儲空間，查找不麻煩。但不太適合對形體頻繁進行交互修改，修改一個面，則整個鏈表內(nèi)容幾乎要全部隨之改。第二十六頁，共三十一頁，2022年，8月28日單鏈三表結(jié)構(gòu)把形體的拓撲關(guān)系與幾何信息結(jié)合在一起進行處理，不利于拓撲關(guān)系相同而尺寸、形狀不同的形體。雙鏈表的翼邊結(jié)構(gòu)是在數(shù)據(jù)結(jié)構(gòu)中分別處理形體拓撲和幾何信息。從外邊觀察平面立體時，可以看到每一個棱邊都有左右兩個鄰面及構(gòu)成著兩面的四個鄰邊，像是長出的翅膀，故稱為翼邊結(jié)構(gòu)。在體素拼合的幾何造型中，