中的數(shù)據(jù)結(jié)構(gòu)第一頁，共三十一頁，編輯于2023年，星期五一、數(shù)據(jù)的組織形式字段：也稱數(shù)據(jù)項(xiàng)，是數(shù)據(jù)中最基本的、不可分的和有名字的數(shù)據(jù)元素。（齒輪零件號、材料牌號、模數(shù)、齒寬等）記錄：相關(guān)的字段組成一個(gè)記錄，它是字段的集合。這種記錄也稱為邏輯記錄文件：相同性質(zhì)記錄的集合就是文件。數(shù)據(jù)庫：是存儲在計(jì)算機(jī)內(nèi)部，可以按需要使用的、通用的、綜合性的、減少重復(fù)存儲程序的數(shù)據(jù)的集合。（數(shù)據(jù)庫不只是文件的集合，還蘊(yùn)涵對文件的重新組織，以便最大限度的減少文件中的重復(fù)數(shù)據(jù)，并增強(qiáng)數(shù)據(jù)文件之間和文件數(shù)據(jù)之間的相互聯(lián)系）數(shù)據(jù)庫管理系統(tǒng)（DBMS）：應(yīng)用程序從數(shù)據(jù)庫中存取數(shù)據(jù)，是在數(shù)據(jù)庫管理系統(tǒng)控制下，根據(jù)應(yīng)用程序中的命令進(jìn)行的。第二頁，共三十一頁，編輯于2023年，星期五二、數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指用戶表達(dá)數(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é)點(diǎn)是順序排列的。因此每一節(jié)點(diǎn)只與它前一個(gè)和后一個(gè)節(jié)點(diǎn)相聯(lián)系，節(jié)點(diǎn)間只存在著線性位置關(guān)系，故也稱線性并列表。線性并列表是x(1),x(2),…,x(n)(n0)的集合，其約束條件為：當(dāng)n>0時(shí)，x(1)是第一個(gè)節(jié)點(diǎn)，第k個(gè)節(jié)點(diǎn)x(k)(1<k<n)的前一節(jié)點(diǎn)是x(k-1)，后一節(jié)點(diǎn)是x(k+1)，最后節(jié)點(diǎn)為x(n)。數(shù)組就是該結(jié)構(gòu)的例子。第三頁，共三十一頁，編輯于2023年，星期五在線性并列表中，棧和隊(duì)列是用得最廣泛的兩種重要數(shù)據(jù)結(jié)構(gòu)。棧：限定只能在表的一端進(jìn)行插入和刪除的線性表。該端稱棧頂，另一端稱棧底。遵循“后進(jìn)先出”原則。機(jī)械裝拆是其例子。隊(duì)列：限定只能在表的一端進(jìn)行插入、另一端進(jìn)行刪除的線性表。插入端稱隊(duì)尾，刪除端稱隊(duì)首。遵循“先進(jìn)先出”原則。工件在流水線上的情況是其例子。進(jìn)棧出棧進(jìn)隊(duì)出隊(duì)隊(duì)首隊(duì)尾棧頂棧底第四頁，共三十一頁，編輯于2023年，星期五2、樹狀層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)（樹狀結(jié)構(gòu)）該結(jié)構(gòu)的數(shù)據(jù)元素之間具有從屬關(guān)系的層次結(jié)構(gòu)。機(jī)器部件4部件3部件2部件1組件3組件2組件1零件3零件2零件1AB1B2B3B4C1C2C3D1D2D3樹狀結(jié)構(gòu)只有一個(gè)根節(jié)點(diǎn)，稱為樹根。樹狀結(jié)構(gòu)的特點(diǎn)是下一層中的節(jié)點(diǎn)只能有一條連線與它的上一層的一個(gè)節(jié)點(diǎn)相連。樹根樹葉子樹根第一層第二層第三層第四層深度：層次數(shù)；度：節(jié)點(diǎn)孩子數(shù)；樹的度：最大的節(jié)點(diǎn)度。第五頁，共三十一頁，編輯于2023年，星期五3、網(wǎng)狀關(guān)系的數(shù)據(jù)結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）該結(jié)構(gòu)能表達(dá)數(shù)據(jù)間更復(fù)雜的關(guān)系。網(wǎng)狀結(jié)構(gòu)與樹狀結(jié)構(gòu)的主要區(qū)別：樹狀結(jié)構(gòu)的下層節(jié)點(diǎn)只能與一個(gè)上層節(jié)點(diǎn)連接，而網(wǎng)狀結(jié)構(gòu)的下層節(jié)點(diǎn)可與幾個(gè)上層節(jié)點(diǎn)連接。第六頁，共三十一頁，編輯于2023年，星期五三、數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)即數(shù)據(jù)在計(jì)算機(jī)內(nèi)的存儲形式。設(shè)計(jì)好數(shù)據(jù)的邏輯結(jié)構(gòu)后，系統(tǒng)通過特定的軟件把數(shù)據(jù)以及數(shù)據(jù)間的關(guān)系按一定的形式存入計(jì)算機(jī)存儲器中，構(gòu)成這些數(shù)據(jù)的存儲結(jié)構(gòu)，即物理結(jié)構(gòu)。把邏輯結(jié)構(gòu)變換成物理結(jié)構(gòu)的過程，稱為映射。邏輯結(jié)構(gòu)設(shè)計(jì)一般多從用戶的要求來考慮，而存儲結(jié)構(gòu)設(shè)計(jì)除考慮數(shù)據(jù)的邏輯結(jié)構(gòu)外，還要考慮存儲資源的充分利用、減少存取時(shí)間、便于數(shù)據(jù)修改、提高系統(tǒng)可靠性等存儲結(jié)構(gòu)本身的一些特點(diǎn)和要求。邏輯結(jié)構(gòu)與物理結(jié)構(gòu)兩者一般不一致，同一邏輯結(jié)構(gòu)可以映射出多種物理結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)有兩種最基本方式：順序式與鏈?zhǔn)?。第七頁，共三十一頁，編輯?023年，星期五1、順序存儲結(jié)構(gòu)數(shù)據(jù)按一定順序連續(xù)存放在計(jì)算機(jī)的存儲單元中，不使用其它單元作為輔助信息。是一種最簡單的存儲方式，數(shù)據(jù)元素間相隔固定距離，數(shù)據(jù)在邏輯上的順序與它在計(jì)算機(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第八頁，共三十一頁，編輯于2023年，星期五2、鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲單元不是按邏輯結(jié)構(gòu)的順序分配的，數(shù)據(jù)元素在存儲器中可按任意順序存放在任意位置上，數(shù)據(jù)元素的邏輯元素順序與在存儲器內(nèi)部的存放順序可以不同。為了能正確地存放數(shù)據(jù)元素，隨同每一個(gè)元素的存儲還必須存儲另一個(gè)元素的地址，稱為鏈指針。每個(gè)存儲單元由數(shù)據(jù)域和指針域兩部分構(gòu)成。數(shù)據(jù)域存放節(jié)點(diǎn)的值；指針域用來實(shí)現(xiàn)關(guān)系，即用來存放與該節(jié)點(diǎn)有某種關(guān)系的節(jié)點(diǎn)的存儲單元地址。這種通過指針來實(shí)現(xiàn)邏輯結(jié)構(gòu)中的順序關(guān)系的方法，稱為鏈接法或鏈地址法。第九頁，共三十一頁，編輯于2023年，星期五左圖為磁盤中的實(shí)際存儲結(jié)構(gòu)，其存儲結(jié)構(gòu)的模型如右圖。R1R4R2R3R1R2R3R4*數(shù)據(jù)域指針域結(jié)束標(biāo)記盡管鏈接法的物理存儲結(jié)構(gòu)分散而不按邏輯順序，但通過指針仍可按順序來存儲各記錄，實(shí)現(xiàn)邏輯結(jié)構(gòu)的順序關(guān)系。這樣物理存儲獨(dú)立于邏輯結(jié)構(gòu)，是鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本特點(diǎn)。第十頁，共三十一頁，編輯于2023年，星期五鏈?zhǔn)酱鎯π枰~外的存儲空間來存放指針，占用的存儲區(qū)域較大。但節(jié)點(diǎn)的插入和刪除比較簡單，可以不改變原來的物理存儲結(jié)構(gòu)，只需要改變相應(yīng)的指針域數(shù)據(jù)即可實(shí)現(xiàn)。R1R2R3R4鏈地址法的數(shù)據(jù)結(jié)構(gòu)又可分為鏈結(jié)構(gòu)、環(huán)結(jié)構(gòu)、樹結(jié)構(gòu)。R5*R6刪除節(jié)點(diǎn)R4插入節(jié)點(diǎn)R610111112131420121314地址142012第十一頁，共三十一頁，編輯于2023年，星期五正向鏈結(jié)構(gòu)R1R2R3R4反向鏈結(jié)構(gòu)R5*R1*R2R3R4R5雙向鏈結(jié)構(gòu)R1*R2R3R4*環(huán)結(jié)構(gòu)R1R2R3R4R5第十二頁，共三十一頁，編輯于2023年，星期五樹結(jié)構(gòu)：在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，可以設(shè)置多個(gè)指針，分別指向多個(gè)不同的存儲單元，從而可以構(gòu)成多種多樣復(fù)雜的物理結(jié)構(gòu)，實(shí)現(xiàn)數(shù)據(jù)間更為復(fù)雜的邏輯關(guān)系。定長方式：一具有最大度數(shù)的節(jié)點(diǎn)結(jié)構(gòu)作為該樹所有節(jié)點(diǎn)的結(jié)構(gòu)。A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C90000第十三頁，共三十一頁，編輯于2023年，星期五A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C9不定長方式：每個(gè)節(jié)點(diǎn)增加一個(gè)存放度數(shù)的域，節(jié)點(diǎn)的長度隨著度數(shù)的增加而增加。3324第十四頁，共三十一頁，編輯于2023年，星期五四、二叉樹1、二叉樹的邏輯結(jié)構(gòu)二叉樹是一種不同于樹的數(shù)據(jù)結(jié)構(gòu)，它的每個(gè)節(jié)點(diǎn)至多有兩棵子樹，子樹有左右之分，即不能顛倒。二叉樹可以是空的，其深度與度的定義與樹同。滿二叉樹：深度為k的有2k-1個(gè)節(jié)點(diǎn)的二叉樹。順序二叉樹：深度為k、節(jié)點(diǎn)為n的二叉樹，它從1到n的序號與深度為k的滿二叉樹的節(jié)點(diǎn)序號相同。完全二叉樹：節(jié)點(diǎn)的度數(shù)或者為0、或者為2的二叉樹。第十五頁，共三十一頁，編輯于2023年，星期五2、二叉樹的存儲結(jié)構(gòu)對于滿二叉樹或順序二叉樹：可用順序存儲形式。對于節(jié)點(diǎn)i，若i=1，此節(jié)點(diǎn)是根節(jié)點(diǎn)；若i=k，k/2是節(jié)點(diǎn)i的雙親節(jié)點(diǎn),節(jié)點(diǎn)2k是節(jié)點(diǎn)i的左孩子,節(jié)點(diǎn)2k+1是節(jié)點(diǎn)i的右孩子。對于一般二叉樹：通常采用鏈表結(jié)構(gòu)。此存儲結(jié)構(gòu)特點(diǎn)：節(jié)省存儲空間，可用公式隨機(jī)地訪問每個(gè)節(jié)點(diǎn)和它的雙親節(jié)點(diǎn)及左、右孩子，但不便于刪除或插入運(yùn)算。該存儲結(jié)構(gòu)會多占一些存儲空間，但便于刪除或插入運(yùn)算。每個(gè)節(jié)點(diǎn)設(shè)三個(gè)域：值域存放節(jié)點(diǎn)的值，左子樹域存放左子樹的地址，右子樹域存放右子樹的地址。第十六頁，共三十一頁，編輯于2023年，星期五3、二叉樹的遍歷遍歷二叉樹是按一定的規(guī)律走遍二叉樹的的每個(gè)節(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)被訪問一次且只訪問一次。即按一定規(guī)律將二叉樹的的節(jié)點(diǎn)排成一個(gè)線性序列。由于二叉樹是由根節(jié)點(diǎn)、左子樹、右子樹三個(gè)基本單元組成的，若能依次遍歷著三部分信息，就能遍歷整個(gè)二叉樹。按根節(jié)點(diǎn)、左子樹、右子樹三者不同的先后次序遍歷，可得到六種遍歷二叉樹的方案，即：根節(jié)點(diǎn)、左子樹、右子樹左子樹、根節(jié)點(diǎn)、右子樹左子樹、右子樹、根節(jié)點(diǎn)根節(jié)點(diǎn)、右子樹、左子樹右子樹、根節(jié)點(diǎn)、左子樹右子樹、左子樹、根節(jié)點(diǎn)左邊三種是按照先左后右的次序，是常用的遍歷方式。第十七頁，共三十一頁，編輯于2023年，星期五先序遍歷先序遍歷的次序是：若二叉樹為空，則退出；否則，訪問根節(jié)點(diǎn)，遍歷左子樹，遍歷右子樹，退出。ABDHECFGIVoidpreorder(structbtree*node){if(!node)return;printf(“%d”,node->data);preorder(node->lchild);preorder(node->rchild);}第十八頁，共三十一頁，編輯于2023年，星期五中序遍歷中序遍歷的次序是：若二叉樹為空，則退出；否則，遍歷左子樹，訪問根節(jié)點(diǎn)，遍歷右子樹，退出。ABDHECFGIVoidinorder(structbtree*node){if(!node)return;inorder(node->lchild);printf(“%d”,node->data);inorder(node->rchild);}第十九頁，共三十一頁，編輯于2023年，星期五后序遍歷后序遍歷的次序是：若二叉樹為空，則退出；否則，遍歷左子樹，遍歷右子樹，訪問根節(jié)點(diǎn)，退出。ABDHECFGIVoidpostorder(structbtree*node){if(!node)return;postorder(node->lchild);postorder(node->rchild);printf(“%d”,node->data);}第二十頁，共三十一頁，編輯于2023年，星期五4、樹的二叉樹表示一般的樹可以轉(zhuǎn)換為二叉樹。當(dāng)以鏈表作為樹的存儲結(jié)構(gòu)時(shí)，樹的先序遍歷與后序遍歷可借用遍歷二叉樹的方法。樹轉(zhuǎn)化為二叉樹的規(guī)則：樹的根節(jié)點(diǎn)作為二叉樹的根節(jié)點(diǎn)；根節(jié)點(diǎn)最左端的孩子作為二叉樹的左子樹；根節(jié)點(diǎn)左端第二個(gè)孩子是左端第一個(gè)孩子的右子樹。樹轉(zhuǎn)化為二叉樹的過程：保留每個(gè)節(jié)點(diǎn)與最左孩子的邊，去掉其余邊；連接每個(gè)節(jié)點(diǎn)與其原相鄰兄弟節(jié)點(diǎn)的邊；以樹根節(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)45°，即可。第二十一頁，共三十一頁，編輯于2023年，星期五示例說明ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI保留去掉連邊轉(zhuǎn)旋第二十二頁，共三十一頁，編輯于2023年，星期五五、圖形數(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)指的是直接存入計(jì)算機(jī)內(nèi)的存儲結(jié)構(gòu)。圖形數(shù)據(jù)可分為幾何信息與拓?fù)湫畔纱箢悺缀涡畔⑹潜硎緲?gòu)成圖形的幾何元素的量值大小。拓?fù)湫畔⑹潜硎緢D形的幾何元素之間的連接關(guān)系。第二十三頁，共三十一頁，編輯于2023年，星期五1、確定圖形形狀的完整信息圖形形狀的信息包括兩個(gè)方面：頂點(diǎn)信息（幾何信息）與連接關(guān)系信息（拓?fù)湫畔ⅲ１?給出了長方體各頂點(diǎn)的坐標(biāo)值，是最基本信息（幾何信息）。表3表示了各邊的起點(diǎn)號與終點(diǎn)號，體現(xiàn)出頂點(diǎn)與邊之間的聯(lián)系，是長方體的拓?fù)湫畔?。它們共同?gòu)成了長方體最基本的圖形形狀信息數(shù)據(jù)。第二十四頁，共三十一頁，編輯于2023年，星期五說明幾何信息與拓?fù)湫畔⑷币徊豢?。只有連接關(guān)系而無頂點(diǎn)信息，不能繪出圖形；只有頂點(diǎn)信息而無連接關(guān)系，也不能唯一地確定圖形形狀，往往會產(chǎn)生二義性。第二十五頁，共三十一頁，編輯于2023年，星期五2、單個(gè)三維形體的存儲結(jié)構(gòu)目前采用的三維形體的數(shù)據(jù)結(jié)構(gòu)有三種：單鏈三表結(jié)構(gòu)、雙鏈表的翼邊結(jié)構(gòu)、雙鏈三表結(jié)構(gòu)。若不考慮形體之間的相互聯(lián)系，而只研究一個(gè)形體在計(jì)算機(jī)內(nèi)的表示，則通常只需要面、棱邊、頂點(diǎn)三張表，用單鏈指示它們之間的連接關(guān)系即可，即單鏈三表結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)關(guān)系清楚，節(jié)省存儲空間，查找不麻煩。但不太適合對形體頻繁進(jìn)行交互修改，修改一個(gè)面，則整個(gè)鏈表內(nèi)容幾乎要全部隨之改。第二十六頁，共三十一頁，編輯于2023年，星期五單鏈三表結(jié)構(gòu)把形體的拓?fù)潢P(guān)系與幾何信息結(jié)合在一起進(jìn)行處理，不利于拓?fù)潢P(guān)系相同而尺寸、形狀不同的形體。雙鏈表的翼邊結(jié)構(gòu)是在數(shù)據(jù)結(jié)構(gòu)中分別處理形體拓?fù)浜蛶缀涡畔ⅰ耐膺呌^察平面立體時(shí)，可以看到每一個(gè)棱邊都有左右兩個(gè)鄰面及構(gòu)成著兩面的四個(gè)鄰邊，像是長出的翅膀，故稱為翼邊結(jié)構(gòu)。在體素拼合的幾何造型中，最