數(shù)據(jù)結(jié)構(gòu)多維數(shù)組及廣義表ppt課件

1、第四章 多維數(shù)組及廣義表 v前幾章引見的數(shù)據(jù)構(gòu)造都是線性構(gòu)造，數(shù)據(jù)元素都屬于原子類型，其值不分解運用。v本章討論的多維數(shù)組和廣義表是線性構(gòu)造的推行，從整體上看它們是多個元素組成的線性表，而從部分上看線性表中的數(shù)據(jù)元素不一定是原子類型，即數(shù)據(jù)元素又可以具有某種數(shù)據(jù)構(gòu)造。主要內(nèi)容：41 多維數(shù)組多維數(shù)組的邏輯構(gòu)造特征及存儲方式42 矩陣的緊縮存儲 特殊矩陣和稀疏矩陣的緊縮存儲43 廣義表廣義表的定義和運算 41 多維數(shù)組一、多維數(shù)組的邏輯構(gòu)造特征數(shù)組中的元素具有一樣類型，且下標普通具有固定的上界和下界。 數(shù)組可以是一維的，也可以是多維的。本章主要以二維數(shù)組為例來分析多維數(shù)組的邏輯構(gòu)造特征和存儲構(gòu)造

2、。 二維數(shù)組可以看成是由多個一維數(shù)組組成的。例如，二維數(shù)組Amn既可看成由m個行向量組成的線性表，也可看成是由n個列向量組成的線性表。 二維數(shù)組的邏輯構(gòu)造具有如下特征：a00為開場結(jié)點，它沒有直接前趨；am-1,n-1為終端結(jié)點，它沒有直接后繼；結(jié)點a0,n-1和am-1,0都有一個直接前趨和一個直接后繼；除以上四個結(jié)點外，第一行和第一列的元素都有一個直接前趨和兩個直接后繼，最后一行和最后一列的元素都有兩個直接前趨和一個直接后繼；其他的非邊境元素aij同時處于第i+1行的行向量中和第j+1列的列向量中，都有兩個直接前趨和兩個直接后繼。 二、多維數(shù)組的存儲 二維數(shù)組普通采用順序存儲。 由于內(nèi)存單

3、元是一維的線性關(guān)系，而二維數(shù)組中元素之間的關(guān)系是非線性的，所以假設(shè)要順序存儲二維數(shù)組，首先需求將二維數(shù)組中的元素按照某種原那么陳列成點的線性序列，然后再依次存放到延續(xù)的存儲單元中。 通常二維數(shù)組有行優(yōu)先和列優(yōu)先兩種陳列原那么。 1行優(yōu)先原那么，是指先陳列二維數(shù)組的第一行中的數(shù)據(jù)元素，再陳列第二行中的數(shù)據(jù)元素，以此類推。 2列優(yōu)先原那么，是指先陳列二維數(shù)組的第一列中的數(shù)據(jù)元素，再陳列第二列中的數(shù)據(jù)元素，以此類推。 數(shù)據(jù)元素的存儲地址可根據(jù)數(shù)組的首地址、元素的存儲空間大小及元素的序號三個信息計算出來，從而實現(xiàn)隨機存取。 假設(shè)二維數(shù)組Amn按行優(yōu)先原那么陳列，其線性序列為： a00，a01，a0,n

4、-1，a10，a11，a1,n-1，am-1,n-1 存儲后的內(nèi)存形狀如下圖: aij的地址為：LOCaij= LOCa00+in+j d 假設(shè)二維數(shù)組Amn按列優(yōu)先原那么陳列，那么線性序列為：a00，a10，am-1,0，a01，a11，am-1,1，am-1,n-1 存儲后的內(nèi)存形狀如下圖: aij的地址為：LOCaij= LOCa00+jm+i d 二維數(shù)組的邏輯特征和存儲方法可以很容易地推行到多維數(shù)組。例如三維數(shù)組可以看成是由二維數(shù)組組成的線性表，三維數(shù)組中的每個元素最多有三個直接前趨和三個直接后繼。同樣，行優(yōu)先原那么和列優(yōu)先原那么也可以推行到多維數(shù)組，按行優(yōu)先原那么時先排最右的下標，

5、按列優(yōu)先原那么時先排最左的下標。得到行優(yōu)先或列優(yōu)先序列后，可以把它們依次存放在延續(xù)的存儲空間中，這就是多維數(shù)組的順序存儲，同樣可實現(xiàn)隨機存取。 42 矩陣的緊縮存儲計算機在處置工程問題時，通常運用二維數(shù)組來存儲矩陣，但是實踐問題中的矩陣往往階數(shù)較大，而有效數(shù)據(jù)非零元素很少且分布沒有規(guī)律，假設(shè)用上面討論的二維數(shù)組存儲，其存儲密度小存儲了大量的零元素，浪費了存儲空間。 矩陣的緊縮存儲通常指在存儲數(shù)據(jù)元素時，只存儲非零元素，對零元素不分配空間；為多個一樣的非零元素分配一個存儲空間。下面分別討論特殊矩陣和稀疏矩陣的緊縮存儲。 一、特殊矩陣特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。例如，對稱矩陣

6、、三角矩陣上三角陣和下三角陣及對角矩陣，特殊矩陣可以根據(jù)元素的分布規(guī)律來進展緊縮存儲。不同的特殊矩陣中元素的分布規(guī)律不同，緊縮存儲的方法也不同。1 1對稱矩陣對稱矩陣滿足aij=aji1i，jn的n階方陣稱為對稱矩陣。 對稱矩陣中的數(shù)據(jù)元素按主對角線對稱，只需存儲下三角或上三角中的元素即可。上三角或下三角中的元素可按行優(yōu)先或列優(yōu)先存儲。由此可得四種存儲方法： 行優(yōu)先順序存儲下三角列優(yōu)先順序存儲下三角行優(yōu)先順序存儲上三角列優(yōu)先順序存儲上三角。每種方法中元素的存儲地址都可以經(jīng)過公式計算出來，且具有隨機存取的特點。1行優(yōu)先順序存儲下三角行優(yōu)先順序存儲下三角 以圖以圖a所示的所示的n階方陣為例，行優(yōu)先

7、順序階方陣為例，行優(yōu)先順序存儲下三角時元素的陳列順序如圖存儲下三角時元素的陳列順序如圖b所示所示，存儲在一維數(shù)組中如圖，存儲在一維數(shù)組中如圖c所示。所示。 a n階對稱矩陣 b 行優(yōu)先順序存儲下三角c對應(yīng)的一維數(shù)組設(shè)長度為nn+1/2的數(shù)組sa存儲下三角中的元素。設(shè)矩陣下三角中的某一個元素aijij對應(yīng)存儲在一維數(shù)組的下標變量sak中，那么上三角中的某一個元素aiji0記為：LS =a1， a2， ，ai， an其中，LS是廣義表的名字。a1為廣義表的第一個元素，ai 為廣義表的第i個元素。顯然，廣義表是一種遞歸的數(shù)據(jù)構(gòu)造，由于廣義表中的數(shù)據(jù)元素還可以是廣義表。當廣義表中的一切元素都是原子時，

8、此廣義表就是線性表。 下面是一些廣義表的例子：1A=A是一個空表，其長度為0。2B=a，bB是一個長度為2的廣義表，它的兩個元素都是原子，因此它就是一個線性表。3C=c，B=c，a，bC是長度為2的廣義表，第一個元素是原子c，第二個元素是子表B。4D=B，C，d=a，b，c，a，b，dD是長度為3的廣義表，第一個元素和第二個元素都為子表，第三個元素為原子d。5E=a，E=a，a，a， E是長度為2的廣義表，第一個元素是原子，第二個元素是E本身，它是一個無限遞歸的廣義表。 廣義表還有其他的表示方法，如：1帶名字的廣義表表示：在每個表的前面冠以該表的名字A Ba，bCc，Ba，bD Ba，b，Cc

9、，a，b，dEa，Ea，Ea，E2廣義表的圖形表示 用非分支結(jié)點表示原子，用分支結(jié)點表示廣義表空表除外，空表中不含元素，所以也用非分支結(jié)點表示。廣義表分為：線性表、純表、再入表和遞歸表四種。當廣義表中的元素全部都是原子時，廣義表就是線性表，因此也可以說線性表是廣義表的一種特殊方式。上圖中的廣義表B就是一個線性表。假設(shè)廣義表中既包含原子，又包含子表，但沒有共享和遞歸，如廣義表C，那么此時的廣義表就是一棵樹將在第五章討論，稱這種廣義表為純表。允許結(jié)點的共享但不允許遞歸的廣義表為再入表，上圖中的廣義表D，子表B為共享結(jié)點，它既是表D的一個元素，又是子表C的一個元素。這樣的廣義表與數(shù)據(jù)構(gòu)造的圖形構(gòu)造對

10、應(yīng)將在第六章討論。允許遞歸的表稱為遞歸表，上圖中的廣義表E為遞歸表，表E是其本身的子表。遞歸表、再入表、純表、線性表之間的關(guān)系滿足：遞歸表 再入表 純表 線性表 廣義表可以兼容線性表、樹和圖等各種經(jīng)典的數(shù)據(jù)構(gòu)造，廣義表的大部分運算都與經(jīng)典數(shù)據(jù)構(gòu)造的運算類似。四個特殊的運算：取表頭HeadLS、取表尾TailLS、求表深、求表長。廣義表的表頭Head為廣義表的第一個元素，廣義表的表尾Tail為廣義表中除第一個元素外，剩下一切的元素組成的廣義表。對廣義表LS =a1， a2， ， an來說，取表頭、取表尾的運算定義為： HeadLS =a1，TailLS = a2， ， an 。例如：Heada，b= aTaila，b=bHeada= aTaila，b，c，a，b= c，a，b任何一個非空廣義表LS =a1， a2， ， an均可分解為表頭和表尾兩個部分。反之，一對表頭和表尾也可獨一確定一個廣義表。根據(jù)表頭、表尾的定義可知：任何一個非空廣義表的表頭是表中第一個元素，