中的數(shù)據(jù)結(jié)構(gòu)詳解演示文稿

中的數(shù)據(jù)結(jié)構(gòu)詳解演示文稿當(dāng)前第1頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)（優(yōu)選）中的數(shù)據(jù)結(jié)構(gòu)當(dāng)前第2頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)二、數(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ǎn)單的邏輯結(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)的例子。當(dāng)前第3頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)在線性并列表中，棧和隊(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ì)尾棧頂棧底當(dāng)前第4頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)

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)度。當(dāng)前第5頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)

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)連接。當(dāng)前第6頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)三、數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)即數(shù)據(jù)在計(jì)算機(jī)內(nèi)的存儲(chǔ)形式。設(shè)計(jì)好數(shù)據(jù)的邏輯結(jié)構(gòu)后，系統(tǒng)通過(guò)特定的軟件把數(shù)據(jù)以及數(shù)據(jù)間的關(guān)系按一定的形式存入計(jì)算機(jī)存儲(chǔ)器中，構(gòu)成這些數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，即物理結(jié)構(gòu)。把邏輯結(jié)構(gòu)變換成物理結(jié)構(gòu)的過(guò)程，稱為映射。邏輯結(jié)構(gòu)設(shè)計(jì)一般多從用戶的要求來(lái)考慮，而存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)除考慮數(shù)據(jù)的邏輯結(jié)構(gòu)外，還要考慮存儲(chǔ)資源的充分利用、減少存取時(shí)間、便于數(shù)據(jù)修改、提高系統(tǒng)可靠性等存儲(chǔ)結(jié)構(gòu)本身的一些特點(diǎn)和要求。邏輯結(jié)構(gòu)與物理結(jié)構(gòu)兩者一般不一致，同一邏輯結(jié)構(gòu)可以映射出多種物理結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)有兩種最基本方式：順序式與鏈?zhǔn)?。?dāng)前第7頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)

1、順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)按一定順序連續(xù)存放在計(jì)算機(jī)的存儲(chǔ)單元中，不使用其它單元作為輔助信息。是一種最簡(jiǎn)單的存儲(chǔ)方式，數(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當(dāng)前第8頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)

2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)單元不是按邏輯結(jié)構(gòu)的順序分配的，數(shù)據(jù)元素在存儲(chǔ)器中可按任意順序存放在任意位置上，數(shù)據(jù)元素的邏輯元素順序與在存儲(chǔ)器內(nèi)部的存放順序可以不同。為了能正確地存放數(shù)據(jù)元素，隨同每一個(gè)元素的存儲(chǔ)還必須存儲(chǔ)另一個(gè)元素的地址，稱為鏈指針。每個(gè)存儲(chǔ)單元由數(shù)據(jù)域和指針域兩部分構(gòu)成。數(shù)據(jù)域存放節(jié)點(diǎn)的值；指針域用來(lái)實(shí)現(xiàn)關(guān)系，即用來(lái)存放與該節(jié)點(diǎn)有某種關(guān)系的節(jié)點(diǎn)的存儲(chǔ)單元地址。這種通過(guò)指針來(lái)實(shí)現(xiàn)邏輯結(jié)構(gòu)中的順序關(guān)系的方法，稱為鏈接法或鏈地址法。當(dāng)前第9頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)左圖為磁盤中的實(shí)際存儲(chǔ)結(jié)構(gòu)，其存儲(chǔ)結(jié)構(gòu)的模型如右圖。R1R4R2R3R1R2R3R4*數(shù)據(jù)域指針域結(jié)束標(biāo)記盡管鏈接法的物理存儲(chǔ)結(jié)構(gòu)分散而不按邏輯順序，但通過(guò)指針仍可按順序來(lái)存儲(chǔ)各記錄，實(shí)現(xiàn)邏輯結(jié)構(gòu)的順序關(guān)系。這樣物理存儲(chǔ)獨(dú)立于邏輯結(jié)構(gòu)，是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本特點(diǎn)。當(dāng)前第10頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)鏈?zhǔn)酱鎯?chǔ)需要額外的存儲(chǔ)空間來(lái)存放指針，占用的存儲(chǔ)區(qū)域較大。但節(jié)點(diǎn)的插入和刪除比較簡(jiǎn)單，可以不改變?cè)瓉?lái)的物理存儲(chǔ)結(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當(dāng)前第11頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)正向鏈結(jié)構(gòu)R1R2R3R4反向鏈結(jié)構(gòu)R5*R1*R2R3R4R5雙向鏈結(jié)構(gòu)R1*R2R3R4*環(huán)結(jié)構(gòu)R1R2R3R4R5當(dāng)前第12頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)樹結(jié)構(gòu)：在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，可以設(shè)置多個(gè)指針，分別指向多個(gè)不同的存儲(chǔ)單元，從而可以構(gòu)成多種多樣復(fù)雜的物理結(jié)構(gòu)，實(shí)現(xiàn)數(shù)據(jù)間更為復(fù)雜的邏輯關(guān)系。定長(zhǎng)方式：一具有最大度數(shù)的節(jié)點(diǎn)結(jié)構(gòu)作為該樹所有節(jié)點(diǎn)的結(jié)構(gòu)。A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C90000當(dāng)前第13頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)A1B1B3C8C3C2C1C9B2C5C4C7C6B1B2B3A1C1C2C3C4C5C6C7C8C9不定長(zhǎng)方式：每個(gè)節(jié)點(diǎn)增加一個(gè)存放度數(shù)的域，節(jié)點(diǎn)的長(zhǎng)度隨著度數(shù)的增加而增加。3324當(dāng)前第14頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)四、二叉樹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的序號(hào)與深度為k的滿二叉樹的節(jié)點(diǎn)序號(hào)相同。完全二叉樹：節(jié)點(diǎn)的度數(shù)或者為0、或者為2的二叉樹。當(dāng)前第15頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)2、二叉樹的存儲(chǔ)結(jié)構(gòu)對(duì)于滿二叉樹或順序二叉樹：可用順序存儲(chǔ)形式。對(duì)于節(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的右孩子。對(duì)于一般二叉樹：通常采用鏈表結(jié)構(gòu)。此存儲(chǔ)結(jié)構(gòu)特點(diǎn)：節(jié)省存儲(chǔ)空間，可用公式隨機(jī)地訪問(wèn)每個(gè)節(jié)點(diǎn)和它的雙親節(jié)點(diǎn)及左、右孩子，但不便于刪除或插入運(yùn)算。該存儲(chǔ)結(jié)構(gòu)會(huì)多占一些存儲(chǔ)空間，但便于刪除或插入運(yùn)算。每個(gè)節(jié)點(diǎn)設(shè)三個(gè)域：值域存放節(jié)點(diǎn)的值，左子樹域存放左子樹的地址，右子樹域存放右子樹的地址。當(dāng)前第16頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)3、二叉樹的遍歷遍歷二叉樹是按一定的規(guī)律走遍二叉樹的的每個(gè)節(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)被訪問(wèn)一次且只訪問(wè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)左邊三種是按照先左后右的次序，是常用的遍歷方式。當(dāng)前第17頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)先序遍歷先序遍歷的次序是：若二叉樹為空，則退出；否則，訪問(wèn)根節(jié)點(diǎn)，遍歷左子樹，遍歷右子樹，退出。ABDHECFGIVoidpreorder(structbtree*node){if(!node)return;printf(“%d”,node->data);preorder(node->lchild);preorder(node->rchild);}當(dāng)前第18頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)中序遍歷中序遍歷的次序是：若二叉樹為空，則退出；否則，遍歷左子樹，訪問(wèn)根節(jié)點(diǎn)，遍歷右子樹，退出。ABDHECFGIVoidinorder(structbtree*node){if(!node)return;inorder(node->lchild);printf(“%d”,node->data);inorder(node->rchild);}當(dāng)前第19頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)后序遍歷后序遍歷的次序是：若二叉樹為空，則退出；否則，遍歷左子樹，遍歷右子樹，訪問(wèn)根節(jié)點(diǎn)，退出。ABDHECFGIVoidpostorder(structbtree*node){if(!node)return;postorder(node->lchild);postorder(node->rchild);printf(“%d”,node->data);}當(dāng)前第20頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)4、樹的二叉樹表示一般的樹可以轉(zhuǎn)換為二叉樹。當(dāng)以鏈表作為樹的存儲(chǔ)結(jié)構(gòu)時(shí)，樹的先序遍歷與后序遍歷可借用遍歷二叉樹的方法。樹轉(zhuǎn)化為二叉樹的規(guī)則：樹的根節(jié)點(diǎn)作為二叉樹的根節(jié)點(diǎn)；根節(jié)點(diǎn)最左端的孩子作為二叉樹的左子樹；根節(jié)點(diǎn)左端第二個(gè)孩子是左端第一個(gè)孩子的右子樹。樹轉(zhuǎn)化為二叉樹的過(guò)程：保留每個(gè)節(jié)點(diǎn)與最左孩子的邊，去掉其余邊；連接每個(gè)節(jié)點(diǎn)與其原相鄰兄弟節(jié)點(diǎn)的邊；以樹根節(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)45°，即可。當(dāng)前第21頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)示例說(shuō)明ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI保留去掉連邊轉(zhuǎn)旋當(dāng)前第22頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)五、圖形數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)是數(shù)據(jù)及其關(guān)系的抽象表示，此處圖形數(shù)據(jù)結(jié)構(gòu)指的是直接存入計(jì)算機(jī)內(nèi)的存儲(chǔ)結(jié)構(gòu)。圖形數(shù)據(jù)可分為幾何信息與拓?fù)湫畔纱箢悺缀涡畔⑹潜硎緲?gòu)成圖形的幾何元素的量值大小。拓?fù)湫畔⑹潜硎緢D形的幾何元素之間的連接關(guān)系。當(dāng)前第23頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)1、確定圖形形狀的完整信息圖形形狀的信息包括兩個(gè)方面：頂點(diǎn)信息（幾何信息）與連接關(guān)系信息（拓?fù)湫畔ⅲ１?給出了長(zhǎng)方體各頂點(diǎn)的坐標(biāo)值，是最基本信息（幾何信息）。表3表示了各邊的起點(diǎn)號(hào)與終點(diǎn)號(hào)，體現(xiàn)出頂點(diǎn)與邊之間的聯(lián)系，是長(zhǎng)方體的拓?fù)湫畔?。它們共同?gòu)成了長(zhǎng)方體最基本的圖形形狀信息數(shù)據(jù)。當(dāng)前第24頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)說(shuō)明幾何信息與拓?fù)湫畔⑷币徊豢?。只有連接關(guān)系而無(wú)頂點(diǎn)信息，不能繪出圖形；只有頂點(diǎn)信息而無(wú)連接關(guān)系，也不能唯一地確定圖形形狀，往往會(huì)產(chǎn)生二義性。當(dāng)前第25頁(yè)\共有29頁(yè)\編于星期四\17點(diǎn)2、單個(gè)三維形體的存儲(chǔ)結(jié)構(gòu)目前采用的三維形體的數(shù)據(jù)結(jié)構(gòu)有三種：?jiǎn)捂溔斫Y(jié)構(gòu)、雙鏈表的翼邊結(jié)構(gòu)、雙鏈三表結(jié)構(gòu)。若不考慮形體之間的相互聯(lián)系，而只研究一個(gè)形體在計(jì)算機(jī)內(nèi)的表示，則通常只需要面、棱邊、頂點(diǎn)三張表，用單鏈指示它們之間的連接關(guān)系即可，即單鏈三表