數(shù)據(jù)結(jié)構(gòu)與算法 課件 第5章 數(shù)組和廣義表

5.1數(shù)組

5.2特殊矩陣的壓縮存儲(chǔ)

5.3稀疏矩陣的壓縮存儲(chǔ)

5.4廣義表5.1數(shù)組5.1.1數(shù)組的基本概念數(shù)組中各元素具有相同的類型，數(shù)組元素具有值和確定元素位置的下標(biāo)。通常可以把一維數(shù)組稱為向量，多維數(shù)組是向量的擴(kuò)充。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界。因此，數(shù)組的處理比其他復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。一維數(shù)組可表示為An?=?[a1，a2，…，an]，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一個(gè)數(shù)組下標(biāo)，它具有線性表的結(jié)構(gòu)，即除了第一個(gè)元素和最后一個(gè)元素，每個(gè)元素存在一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素。二維數(shù)組可表示為3在二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在兩個(gè)前驅(qū)(前件)和兩個(gè)后繼(后件)；也可看作是以線性表為數(shù)據(jù)元素的線性表。也就是說(shuō)，一個(gè)m行n列的二維數(shù)組，可以看成由m個(gè)長(zhǎng)度為n的一維數(shù)組(行)所組成的線性表，也可以看成n個(gè)長(zhǎng)度為m的一維數(shù)組(列)所組成的線性表，即在n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n個(gè)下標(biāo)，受n個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系。它可看作是數(shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。多維數(shù)組是對(duì)線性表的擴(kuò)展，線性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中一般采用順序存儲(chǔ)結(jié)構(gòu)來(lái)存放數(shù)組。而內(nèi)存結(jié)構(gòu)是一維的，因此存放二維數(shù)組或多維數(shù)組，就必須按照某種順序?qū)?shù)組中的元素形成一個(gè)線性序列，然后將這個(gè)線性序列存放在內(nèi)存中。下面討論二維數(shù)組的存儲(chǔ)方式。1)行優(yōu)先順序存儲(chǔ)將數(shù)組元素按行向量的順序存儲(chǔ)，即第i+1行的元素存放在第i行的元素之后。元素存儲(chǔ)的線性序列為2)列優(yōu)先順序存儲(chǔ)將數(shù)組元素按列向量的順序存儲(chǔ)，即第j+1列的元素存放在第j列的元素之后。元素存儲(chǔ)的線性序列為在多數(shù)計(jì)算機(jī)語(yǔ)言中，二維數(shù)組都是按行優(yōu)先的順序存儲(chǔ)的，少數(shù)語(yǔ)言采用按列優(yōu)先的順序存儲(chǔ)。按照上述兩種存儲(chǔ)二維數(shù)組的線性序列，若已知數(shù)組存儲(chǔ)的起始地址，下標(biāo)的上、下界，以及每個(gè)數(shù)組元素所占用的存儲(chǔ)單元個(gè)數(shù)，就可以計(jì)算出元素aij的存儲(chǔ)地址，從而對(duì)數(shù)組元素隨機(jī)存取。例如，二維數(shù)組A[c1..d1,c2..d2]?按行優(yōu)先的順序存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占d個(gè)存儲(chǔ)單元，計(jì)算元素aij的地址公式為其中Loc(ac1c2)是數(shù)組的起始地址；元素aij前面的i-c1行中共有(i-c1)?×?(d2-c2+1)個(gè)元素，第i行上元素aij前面又有j-c2個(gè)元素。類似地，我們可以得出當(dāng)二維數(shù)組A[c1…d1，c2…d2]按列優(yōu)先的順序存儲(chǔ)在內(nèi)存中時(shí)，元素aij的地址計(jì)算公式為5.2特殊矩陣的壓縮存儲(chǔ)5.2.1三角矩陣在n階方陣中，以主對(duì)角線進(jìn)行劃分，如果矩陣的下三角(不包括主對(duì)角線)中的元素均為值相同的常數(shù)，則稱為上三角矩陣；反之稱為下三角矩陣。在多數(shù)情況下，三角矩陣的常數(shù)為零。這兩種三角矩陣如圖5.1所示。為簡(jiǎn)便起見(jiàn)，可以用向量A[0…n(n+1)/2]壓縮存儲(chǔ)三角矩陣，其中A[0]～A[n(n+1)/2-1]存儲(chǔ)矩陣下(上)三角中的元素，向量的最后一個(gè)分量A[n(n+1)/2]存儲(chǔ)三角矩陣中的常數(shù)。下三角矩陣按行優(yōu)先的順序存儲(chǔ)，A[k]與aij的對(duì)應(yīng)關(guān)系為上三角矩陣按列優(yōu)先的順序存儲(chǔ)，A[k]與aij的對(duì)應(yīng)關(guān)系為5.2.2對(duì)稱矩陣若n階方陣A中的元素關(guān)于主對(duì)角線對(duì)稱，即滿足下述性質(zhì)：則稱A為對(duì)稱矩陣。如果采用一維數(shù)組存儲(chǔ)矩陣中的上三角或下三角元素，使對(duì)稱的兩個(gè)元素共享同一個(gè)存儲(chǔ)空間，可以節(jié)省近一半的存儲(chǔ)空間。存儲(chǔ)n階對(duì)稱方陣時(shí)，一維數(shù)組的長(zhǎng)度為n(n+1)/2。同樣，可以用向量A[0…n(n+1)/2-1]壓縮存儲(chǔ)對(duì)稱矩陣。下三角矩陣按行優(yōu)先的順序存儲(chǔ)，A[k]與aij的對(duì)應(yīng)關(guān)系為對(duì)于上三角矩陣中的元素aij(i<j)，因?yàn)閍ij?=?aji，相當(dāng)于按列優(yōu)先的順序存儲(chǔ)，所以A[k]與aij的對(duì)應(yīng)關(guān)系為對(duì)于任意給定一組下標(biāo)(i，j)，均可在A[n(n+1)/2]中找到矩陣元素aij；反之，對(duì)所有的k?=?0，1，2…，

，都能確定元素A[k]在矩陣中的位置(i，j)。由此，稱A[n(n+1)/2]為n階對(duì)稱矩陣A的壓縮存儲(chǔ)，見(jiàn)圖5.2。圖5.3給出了一個(gè)4階對(duì)稱方陣，按行優(yōu)先的順序存儲(chǔ)下三角矩陣，按列優(yōu)先的順序存儲(chǔ)上三角矩陣。圖5.4是其存儲(chǔ)形式。5.2.3對(duì)角矩陣所謂對(duì)角矩陣，是指方陣中的所有非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域內(nèi)，帶狀區(qū)域之外的元素值均為零。帶寬為3的對(duì)角矩陣又稱為三對(duì)角矩陣，如圖5.5所示。顯然，當(dāng)?|i-j|?>?1時(shí)，元素aij為0。一般地，對(duì)于k對(duì)角矩陣(k為奇數(shù))，當(dāng)?|i-j|?>?(k-1)/2時(shí)，元素aij為0。n階三對(duì)角矩陣有3n-2個(gè)非零元素，采用向量A[0…3n-3]按行優(yōu)先的順序壓縮存儲(chǔ)三對(duì)角矩陣。每個(gè)非零元素與向量下標(biāo)的對(duì)應(yīng)關(guān)系為上述各種特殊矩陣的非零元素的分布都具有一定的規(guī)律，采用向量壓縮存儲(chǔ)，通過(guò)元素與向量的對(duì)應(yīng)關(guān)系，仍然可以對(duì)矩陣中的元素進(jìn)行隨機(jī)存取。5.3稀疏矩陣的壓縮存儲(chǔ)5.3.1稀疏矩陣的三元組表存儲(chǔ)將稀疏矩陣中的非零元素的行號(hào)、列號(hào)和元素值作為一個(gè)三元組(i,j,aij)，所有非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列，便得到一個(gè)結(jié)點(diǎn)均是三元組的線性表。我們將該線性表的順序存儲(chǔ)結(jié)構(gòu)稱為三元組表。在下面的討論中，三元組均以按行優(yōu)先的順序排列。在三元組表中，除了要表示非零元素之外，還需要表示矩陣的行、列數(shù)及非零元素的總個(gè)數(shù)。三元組表的結(jié)構(gòu)類型定義描述為設(shè)a為spmattrix型指針變量，圖5.6(a)所示的稀疏矩陣A的三元組表如圖5.6(b)所示。下面以矩陣的轉(zhuǎn)置為例，說(shuō)明采用三元組表的形式存儲(chǔ)稀疏矩陣，如何實(shí)現(xiàn)矩陣的轉(zhuǎn)置運(yùn)算。一個(gè)m?×?n的矩陣A，它的轉(zhuǎn)置矩陣B是一個(gè)n?×?m的矩陣，且A[i][j]?=?B[j][i]，1≤i≤m，1≤j≤n，即A的行是B的列，A的列是B的行。例如圖5.6(a)中的A和圖5.7(a)中的B互為轉(zhuǎn)置矩陣。為了敘述方便，下面將三元組表?*a中的成員a->data簡(jiǎn)稱為三元組表，因?yàn)橄鄬?duì)于其他成員而言，它是主要的。將A轉(zhuǎn)置為B，就是將A的三元組表a->data置換為B的三元組表b->data，如果只是互換a->data中i和j的內(nèi)容，那么所得到的b->data是按列存放的矩陣B的三元組表，還必須重新排列b->data中各結(jié)點(diǎn)的順序。由于A的列是B的行，如果按a->data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b->data必定是按行優(yōu)先的順序存放。算法的基本思想是：對(duì)a->data按列掃描n趟，在第col趟掃描中，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)、列號(hào)和元素值分別放入b->data的列號(hào)、行號(hào)和元素值中，即可得到B的按行優(yōu)先的壓縮存儲(chǔ)表示。以圖5.6和圖5.7為例，設(shè)col?=?1，則掃描a->data找到列號(hào)為1的三元組依次是(1,1,3)和(3,1,2)，存入b->data后為(1,1,3)和(1,3,2)，恰好為B中第1行的兩個(gè)非零元素。只要依次取col=1,2,3,4，即可得到a->data的轉(zhuǎn)置矩陣b->data。下面給出具體的算法。算法5.1矩陣的轉(zhuǎn)置(用三元組表存儲(chǔ)矩陣)。該算法的時(shí)間主要耗費(fèi)在col和ano的二重循環(huán)上，算法的時(shí)間復(fù)雜度為O(n?×?t)，t?<<m?×?n。而通常用二維數(shù)組表示矩陣時(shí)，其轉(zhuǎn)置算法的時(shí)間復(fù)雜度是O(m?×?n)。如果非零元素個(gè)數(shù)大于矩陣的行數(shù)，從轉(zhuǎn)置算法的時(shí)間復(fù)雜度來(lái)說(shuō)，采用三元組表存儲(chǔ)就不合適了，可考慮十字鏈表存儲(chǔ)。5.3.2稀疏矩陣的十字鏈表存儲(chǔ)當(dāng)矩陣的非零元素個(gè)數(shù)和位置在操作過(guò)程中變化較大時(shí)，不宜采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組的線性表。例如，對(duì)于“將矩陣B加到矩陣A上”的操作，由于非零元素的插入或刪除將會(huì)引起A.data中元素的移動(dòng)。對(duì)于這種情況，采用十字鏈表存儲(chǔ)稀疏矩陣更為恰當(dāng)。十字鏈表存儲(chǔ)稀疏矩陣的基本思想是將每個(gè)非零元素對(duì)應(yīng)的三元組作為鏈表的結(jié)點(diǎn)，結(jié)點(diǎn)由5個(gè)域組成，其結(jié)構(gòu)如圖5.8所示。結(jié)點(diǎn)的結(jié)構(gòu)體類型定義如下：圖5.9給出了一個(gè)3行4列有4個(gè)非零元素的稀疏矩陣存儲(chǔ)在十字鏈表的示意圖。我們可以看到同一行的非零元素結(jié)點(diǎn)通過(guò)right域鏈接成一個(gè)循環(huán)鏈表，同一列的非零元素結(jié)點(diǎn)通過(guò)down域鏈接成一個(gè)循環(huán)鏈表，每個(gè)非零元素既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)，整個(gè)矩陣構(gòu)成類一個(gè)十字交叉的鏈表，故稱這樣的存儲(chǔ)結(jié)構(gòu)為十字鏈表?？捎脙蓚€(gè)分別存儲(chǔ)行鏈表和列鏈表頭指針的一維數(shù)組表示，h[i]是其數(shù)組元素。5.4廣義表5.4.1廣義表的概念及基本運(yùn)算1．廣義表概述廣義表一般記作其中，LS是廣義表的名稱；n(≥0)是它的長(zhǎng)度。在線性表的定義中，ai(1≤i≤n)只限于單元素。而在廣義表的定義中，ai可以是單元素，也可以是廣義表，分別稱為廣義表LS的原子和子表。習(xí)慣上，用大寫(xiě)字母表示廣義表的名稱，用小寫(xiě)字母表示原子。當(dāng)廣義表LS非空時(shí)，稱第一個(gè)元素a1為L(zhǎng)S的表頭(Head)，稱其余元素組成的表(a2,a3,…,an)是LS的表尾(Tail)。因此，任何一個(gè)非空廣義表的表頭可能是單元素，也可能是廣義表，但其表尾一定是廣義表。顯然，廣義表的定義是一個(gè)遞歸的定義，因?yàn)樵诿枋鰪V義表時(shí)又用到了廣義表自身的概念。2．廣義表的特點(diǎn)從上述定義和例子可推出廣義表具有如下特點(diǎn)：(1)廣義表是一種線性結(jié)構(gòu)，其長(zhǎng)度為最外層包含的元素個(gè)數(shù)。(2)廣義表的元素可以是子表，而子表的元素還可以是子表，因此廣義表是一種多層次的結(jié)構(gòu)，可以用圖形象地表示。(3)一個(gè)廣義表可為其他廣義表所共享。(4)廣義表可以是一個(gè)遞歸的表，即廣義表也可以是其本身的一個(gè)子表。廣義表的這些特點(diǎn)對(duì)于它的應(yīng)用起到了很大的作用。廣義表可以看作是線性表的推廣，因此線性表只是廣義表的一個(gè)特例。由于廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下它可以兼容線性表、數(shù)組、樹(shù)和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)。例如可以將二維數(shù)組看作是廣義表，二維數(shù)組每行(或每列)作為子表來(lái)處理。由于廣義表具有線性表、數(shù)組、樹(shù)和圖這些常用數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可以有效地利用存儲(chǔ)空間，因此廣義表在許多領(lǐng)域都得到了廣泛的應(yīng)用。3．廣義表的基本操作廣義表作為一種數(shù)據(jù)結(jié)構(gòu)，也具有一組基本操作，常用的基本操作如下：(1)?InitGList(&L)；初始條件：廣義表L不存在。操作結(jié)果：創(chuàng)建空的廣義表L。(2)?GreatGList(&L,S)；初始條件：S是廣義表的書(shū)寫(xiě)形式串。操作結(jié)果：由S建立廣義表L。(3)?DestroyGList(&L)；初始條件：廣義表L存在。操作結(jié)果：銷毀廣義表L。(4)?CopyGList(&T,L)；初始條件：廣義表L存在。操作結(jié)果：由廣義表L復(fù)制得到廣義表T。(5)?GListLength(L)；初始條件：廣義表L存在。操作結(jié)果：求廣義表L的長(zhǎng)度，即元素個(gè)數(shù)。(6)?GListDepth(L)；初始條件：廣義表L存在。操作結(jié)果：求廣義表L的深度，所謂廣義表的深度是指廣義表中所包含的括號(hào)層數(shù)。(7)?GListEmpty(L)；初始條件：廣義表L存在。操作結(jié)果：判定廣義表L是否為空。(8)?GetHead(L)；初始條件：廣義表L存在。操作結(jié)果：取廣義表L的頭。(9)?GetTail(L)；初始條件：廣義表L存在。操作結(jié)果：取廣義表L的尾。(10)?InsertFirst_GL(&L,e)；初始條件：廣義表L存在。操作結(jié)果：插入元素e作為廣義表L的第一元素。(11)?DeleteFirst_GL(&L,e)；初始條件：廣義表L存在。操作結(jié)果：刪除廣義表L的第一元素，并用e返回其值。(12)?Traverse_GL(L,Visit())；初始條件：廣義表L存在。操作結(jié)果：遍歷廣義表L，用函數(shù)Visit處理每個(gè)元素。5.4.2廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表(a1,a2,…,an)中的數(shù)據(jù)元素可以是原子，也可以是子表，因此它是一種帶有層次的非線性結(jié)構(gòu)，難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)廣義表。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)較為靈活，易于解決廣義表的共享與遞歸問(wèn)題。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素都可以用一個(gè)結(jié)點(diǎn)來(lái)表示。根據(jù)結(jié)點(diǎn)形式的不同，廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又可以分為頭尾表示法和孩子兄弟表示法兩種不同的存儲(chǔ)形式。1.頭尾表示法如何設(shè)定結(jié)點(diǎn)的結(jié)構(gòu)？由于廣義表中的元素可以是子表，也可以是原子，由此需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：一種是表結(jié)點(diǎn)，用以表示子表；另一種是原子結(jié)點(diǎn)，用以表示原子。從5.4.1節(jié)可知：若子表不為空，則可分解為表頭和表尾；反之，一對(duì)確定的表頭和表尾可唯一確定子表。由此，一個(gè)表結(jié)點(diǎn)可由3個(gè)域組成，分別是標(biāo)志域、指向表頭的指針域和指向表尾的指針域，如圖5.11(a)所示。而原子結(jié)點(diǎn)只需標(biāo)志域和值域兩個(gè)域，如圖5.11(b)所示。標(biāo)志域tag=1，表示結(jié)點(diǎn)為表結(jié)點(diǎn)；tag=0，表示結(jié)點(diǎn)為原子結(jié)點(diǎn)。廣義表頭尾表示法的結(jié)點(diǎn)類型定義如下：頭尾表示法存儲(chǔ)廣義表有如下三個(gè)特點(diǎn)：(1)若廣義表為空表，則表頭指針為空。對(duì)于任何非空廣義表，其表頭指針均指向一個(gè)表結(jié)點(diǎn)，且該結(jié)點(diǎn)中的hp域指向廣義表的表頭(原子結(jié)點(diǎn)或者表結(jié)點(diǎn))，tp域