




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、2020/8/3,第5章,1,第4章 數(shù)組,前幾章討論的線性結(jié)構(gòu)中的數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型,元素的值是不再分解的。本章討論一種特殊的線性表,其特殊性在于,表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結(jié)構(gòu)。,2020/8/3,第5章,2,一維數(shù)組(Array)是n(n1)個(gè)相同類型數(shù)據(jù)元素a0,a1,an-1構(gòu)成的有限序列,且該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中。由此可見(jiàn),一維數(shù)組可以看成是一個(gè)線性表或一個(gè)向量,一維數(shù)組的定義類似于采用順序存儲(chǔ)的線性表。 對(duì)于一維數(shù)組,一旦a0的存儲(chǔ)地址Loc(a0)確定,若每個(gè)數(shù)據(jù)元素占用L個(gè)存儲(chǔ)單元,則任一數(shù)據(jù)元素ai的存儲(chǔ)地址Loc(ai)可由以下公式求出:
2、Loc(ai)= Loc(a0)+i*L 一維數(shù)組中任一數(shù)據(jù)元素的存儲(chǔ)地址可直接計(jì)算得到,因此,一維數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。,4.1 數(shù)組,2020/8/3,第5章,3,二維數(shù)組可以看成是一維數(shù)組的推廣。設(shè)A是一個(gè)有m行、n列的二維數(shù)組,則A可以表示為:,2020/8/3,第5章,4,顯然,在二維數(shù)組中,每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo),在行方向上和列方向上都存在一個(gè)線性關(guān)系,即存在兩個(gè)直接前驅(qū)和兩個(gè)直接后繼(邊界除外)。 可以看成是由m個(gè)行向量組成的向量,也可以看成是n個(gè)列向量組成的向量。 行向量形式:把每一行看成是一個(gè)數(shù)據(jù)元素,2020/8/3,第5章,5,列向量形式:把每一列看成是一個(gè)數(shù)據(jù)元
3、素 二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組。,2020/8/3,第5章,6,三、多維數(shù)組 同理,三維數(shù)組中的數(shù)據(jù)元素(邊界除外)最多可有三個(gè)直接前驅(qū)和三個(gè)直接后繼??梢园讶S以上的數(shù)組稱為多維數(shù)組,多維數(shù)組中的數(shù)據(jù)元素(邊界除外)可有多個(gè)直接前驅(qū)和多個(gè)直接后繼,故多維數(shù)組是一種非線性結(jié)構(gòu)。 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ù)組。,2020/8/3,第5章,7,數(shù)組具有以下性質(zhì): 1.數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定,一旦定義了一個(gè)數(shù)組,其數(shù)據(jù)元素?cái)?shù)目不再有增減變化; 2.數(shù)組中的每個(gè)數(shù)據(jù)元素具有相同的數(shù)據(jù)
4、類型; 3. 數(shù)組中的每個(gè)數(shù)據(jù)元素都和一組唯一的下標(biāo)相對(duì)應(yīng); 4. 數(shù)組是一種隨機(jī)存取結(jié)構(gòu),可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。,2020/8/3,第5章,8,數(shù)組的順序表示和實(shí)現(xiàn),由于數(shù)組一般不作插入或刪除操作,一旦建立了數(shù)組,則結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)。因此,適合采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組。本章中,僅重點(diǎn)討論二維數(shù)組的存儲(chǔ),三維及三維以上的數(shù)組可以作類似分析。 由于存儲(chǔ)單元是一維的結(jié)構(gòu),而二維數(shù)組是個(gè)多維的結(jié)構(gòu),則用一組連續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定問(wèn)題。 兩種順序存儲(chǔ)方式: 以行序?yàn)橹餍颍ㄐ袃?yōu)先順序) 以列序?yàn)橹餍颍袃?yōu)先順序),2020/8/3,第5章
5、,9,一、以行序?yàn)橹餍颍?1存放規(guī)則 行優(yōu)先順序也稱為低下標(biāo)優(yōu)先或右邊下標(biāo)優(yōu)先于左邊下標(biāo)。具體實(shí)現(xiàn)時(shí),按行號(hào)從小到大的順序,先將第一行中元素全部存放好,再存放第二行元素,第三行元素,依次類推 BASIC語(yǔ)言、PASCAL語(yǔ)言、C/C+語(yǔ)言都是按行優(yōu)先順序存放的。 例如,對(duì)二維數(shù)組Amn ,可用如下形式存放到內(nèi)存:a00,a01,a0n-1,a10,a11,., a1 n-1,am-1 0 , am-1 1,am-1 n-1。即二維數(shù)組按行優(yōu)先存放到內(nèi)存后,變成了一個(gè)線性序列(線性表)。,2020/8/3,第5章,10,2地址計(jì)算 假設(shè)二維數(shù)組Amn每個(gè)元素占L個(gè)字節(jié),元素aij的存儲(chǔ)地址應(yīng)為第
6、一個(gè)元素的地址加上排在aij前面的元素所占用的單元數(shù),而aij 的前面有i行(0i-1)共in個(gè)元素,而第i行上aij前面又有j個(gè)元素,故aij的前面一共有in+j個(gè)元素,設(shè)a00的地址為L(zhǎng)OC(a00),則aij的地址為: LOC(aij)=LOC(a00)+(in+j)L 同理,三維數(shù)組Amnp按低下標(biāo)優(yōu)先存放的地址計(jì)算公式為: LOC(aijk)=LOC(a000)+(inp+jp+k)L,2020/8/3,第5章,11,二、以列序?yàn)橹餍颍?1存放規(guī)則 列優(yōu)先順序也稱為高下標(biāo)優(yōu)先或左邊下標(biāo)優(yōu)先于右邊下標(biāo)。具體實(shí)現(xiàn)時(shí),按列號(hào)從小到大的順序,先將第一列中元素全部存放好,再存放第二列元素,第三
7、列元素,依次類推 在FORTRAN語(yǔ)言中,數(shù)組是按列優(yōu)先順序存放的。例如,二維數(shù)組Amn,可以按如下的形式存放到內(nèi)存:a00, a10, am-10, a01,a11, , am-1 1, a0 m-1,a1m-1,., am-1 n-1。 即二維數(shù)組按列優(yōu)先存放到內(nèi)存后,也變成了一個(gè)線性序列(線性表)。,2020/8/3,第5章,12,2地址計(jì)算 與行優(yōu)先存放類似,若知道第一個(gè)元素的內(nèi)存地址,則同樣可以求得按列優(yōu)存放的某一元素aij的地址。 對(duì)二維數(shù)組有: LOC(aij)=LOC(a00)+(jm+i)L 對(duì)三維數(shù)組Amnp按高下標(biāo)優(yōu)先存放的地址計(jì)算公式為: LOC(aijk)=LOC(a
8、000)+(kmn+jm+i)L,2020/8/3,第5章,13,例1:對(duì)C語(yǔ)言中的二維數(shù)組 A54,計(jì)算: 1)數(shù)組A中的元素?cái)?shù)目; 2)若數(shù)組A的起始地址為2000,且每個(gè)數(shù)組元素長(zhǎng)度為32位(即4個(gè)字節(jié)),求數(shù)組元素A32的內(nèi)存地址。 解: 1)該數(shù)組的元素?cái)?shù)目共有5*4=20個(gè)。 2)由于C語(yǔ)言中數(shù)組的行、列下界均為0,該數(shù)組行下標(biāo)為04,列下標(biāo)為03,并采用行序?yàn)橹餍虻拇鎯?chǔ)方式,有: LOC(a32)=LOC(a00)+(i*n+j)*L =2000+(3*4+2)*4 =2056,2020/8/3,第5章,14,例2:二維數(shù)組A中,每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié),行下標(biāo)i從0到7,列下標(biāo)
9、j從0到9,從首地址SA開(kāi)始存放在存儲(chǔ)器內(nèi),該數(shù)組按列存放時(shí),元素A47的起始地址為 。 A. SA+141 B. SA+180 C. SA+222 D. SA+225,解:LOC(a47)=LOC(a00)+(j *m+ i)*L = SA+(7*8+4)*3 = SA+180,2020/8/3,第5章,15,例3:對(duì)于二維數(shù)組A0.20.5,當(dāng)按行優(yōu)先順序存儲(chǔ)時(shí),元素A23是第幾個(gè)元素?當(dāng)按列優(yōu)先順序存儲(chǔ)時(shí),元素A24是第幾個(gè)元素?,解:m=3,n=6 當(dāng)按行優(yōu)先順序存儲(chǔ)時(shí),元素A23的序號(hào)為: 1+i*n+j=1+2*6+3=16 其中1表示元素A00 當(dāng)按列優(yōu)先順序存儲(chǔ)時(shí),元素A24的
10、序號(hào)為: 1+j*m+i=1+4*3+2=15,2020/8/3,第5章,16,4.2 矩陣的壓縮存儲(chǔ),矩陣是很多科學(xué)與工程計(jì)算問(wèn)題中研究的數(shù)學(xué)對(duì)象。在此,我們感興趣的不是矩陣本身,而是如何存儲(chǔ)矩陣的元從而使矩陣的各種運(yùn)算能有效地進(jìn)行。 通常,用高級(jí)語(yǔ)言編制程序時(shí),都是用二維數(shù)組來(lái)存儲(chǔ)矩陣元。 然而,在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣,同時(shí)在矩陣中有許多值相同的元素或者是零元素。有時(shí)為了節(jié)省存儲(chǔ)空間,可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。所謂壓縮存儲(chǔ)是指:為多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間;對(duì)零元不分配空間。 假若值相同的元素或者零元素在矩陣中的分布有一定規(guī)律,則我們稱此類矩陣為特殊矩陣;反之,稱為
11、稀疏矩陣。下面分別討論它們的壓縮存儲(chǔ)。,2020/8/3,第5章,17,特殊矩陣 1. 對(duì)稱矩陣 若一個(gè)n階方陣A中元素滿足下列條件: aij=aji 其中 0 i, jn-1 則稱A為對(duì)稱矩陣。,2020/8/3,第5章,18,為節(jié)約存儲(chǔ)空間,只存儲(chǔ)對(duì)角線及對(duì)角線以上的元素,或者只存對(duì)角線及對(duì)角線以下的元素。即為每一對(duì)對(duì)稱元素分配一個(gè)存儲(chǔ)空間,則可將n2個(gè)元壓縮存儲(chǔ)到n(n+1)/2個(gè)元的空間中。不失一般性,我們可以行序?yàn)橹餍虼鎯?chǔ)其下三角(包括對(duì)角線)中的元素。 假設(shè)以一維數(shù)組sa0.n(n+1)/2-1作為n階對(duì)稱矩陣A的存儲(chǔ)結(jié)構(gòu),則sak和矩陣元aij之間存在著一一對(duì)應(yīng)的關(guān)系。,2020
12、/8/3,第5章,19,若ij,則aij在下三角形中。aij之前的i行(從第0行到第i-1行)共有1+2+i=i*(i+1)/2個(gè)元素,在第i行上,aij之前恰有j個(gè)元素(即ai0,ai1,ai,j-1),因此aij之前共有k個(gè)元素: k=i*(i+1)/2+j ij, 0kn(n+1)/2-1,若ij,則aij是在上三角矩陣中。因?yàn)閍ij=aji,所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到: k=j*(j+1)/2+i ij,0 kn(n+1)/2-1 矩陣A中任意元素aij和sak之間存在如下關(guān):,2020/8/3,第5章,20,2.三角矩陣 以主對(duì)角線劃分,三角矩陣有上三角矩陣和下三角
13、矩陣兩種。 所謂上(下)三角矩陣是指矩陣的主對(duì)角線的下(上)方(不包括對(duì)角線)的元素均為常數(shù)c或零的n階矩陣。 如圖所示。在大多數(shù)情況下,三角矩陣常數(shù)為零。,2020/8/3,第5章,21,除了和對(duì)稱矩陣一樣只存儲(chǔ)其上(下)三角中的元之外,再加一個(gè)存儲(chǔ)常數(shù)c的存儲(chǔ)空間即可。三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間,其余的元素正好有n*(n+1)/2個(gè),這樣共存儲(chǔ)了n*(n+1)/2+1個(gè)元素,因此,三角矩陣可壓縮存儲(chǔ)到向量sa0.n(n+1)/2中,其中c存放在向量的最后一個(gè)分量中。 對(duì)于下三角矩陣,任意元素aij與sak 的對(duì)應(yīng)關(guān)系和對(duì)稱矩陣情形類似:,2020/8/3,第5章,22,對(duì)于上
14、三角矩陣,存儲(chǔ)思想與下三角矩陣類似,按行優(yōu)先順序存儲(chǔ)上三角部分,最后存儲(chǔ)對(duì)角線下方的常量。對(duì)于第0行,存儲(chǔ)n個(gè)元素,第1行存儲(chǔ)n-1個(gè)元素,第p行存儲(chǔ)(n-p)個(gè)元素,aij的前面有i行,則有: (n-0)+(n-1) +(n-(i-1)=i*(2n-i+1)/2 個(gè)元素,而在當(dāng)前行中,aij 前面有j-i個(gè)元素;所以,aij之前共有 i*(2n-i+1)/2+(j-i)個(gè)元素,因此它在sak中的下標(biāo)為:k=i*(2n-i+1)/2+j-i。 綜上所述,元素aij與sak的對(duì)應(yīng)關(guān)系為:,2020/8/3,第5章,23,3.對(duì)角矩陣 若一個(gè)n階方陣A所有的非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域
15、中,區(qū)域外的值全為0,則稱為對(duì)角矩陣。其主對(duì)角線上下方各有b條次對(duì)角線,稱b為矩陣半帶寬,(2b+1)為矩陣的帶寬。對(duì)于半帶寬為b(0b(n-1)/2)的對(duì)角矩陣,其|i-j|=b的元素aij不為零,其余元素為零。下圖為半帶寬為b的對(duì)角矩陣和b=1的三對(duì)角矩陣 :,2020/8/3,第5章,24,對(duì)于b=1的三對(duì)角矩陣A,只需將其非零元素aij存儲(chǔ)到一維數(shù)組sak中。除第0行和第n-1行是2個(gè)元素外,每行的非零元素都是3個(gè),因此,需存儲(chǔ)的元素個(gè)數(shù)為3n-2。 對(duì)于不在第0行的非零元素aij來(lái)說(shuō), 在它前面存儲(chǔ)了矩陣的前i行元素,這些元素的總數(shù)為2+3(i-1)。 若aij是本行中需存儲(chǔ)的第1個(gè)
16、元素,則k=2+3(i-1)=3i-1,此時(shí),j=i-1,即k=2i+i-1=2i+j。 若ai,j是本行中需存儲(chǔ)的第2個(gè)元素,則k=2+3(i-1)+1=3i,此時(shí),j=i,即k=2i+i=2i+j。 若aij是本行中需存儲(chǔ)的第3個(gè)元素,則k=2+3(i-1)+2=3i+1,此時(shí),j=i+1,即k=2i+i+1=2i+j。 歸納起來(lái)有k=2i+j。,2020/8/3,第5章,25,對(duì)稱矩陣、三角矩陣和對(duì)角矩陣的壓縮存儲(chǔ)方法,是把有一定分布規(guī)律的值相同的元素(包括0)壓縮存儲(chǔ)到一個(gè)向量中。并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系,這樣的壓縮存儲(chǔ)只需在算法中按公式就可求出矩陣元素的存儲(chǔ)地址
17、,即可實(shí)現(xiàn)隨機(jī)存取。,2020/8/3,第5章,26,4.3稀疏矩陣 非零元較零元少,且分布沒(méi)有一定規(guī)律的矩陣稱為稀疏矩陣。 假設(shè)在m*n的矩陣中,有t個(gè)元素不為零。令=t/(m*n),稱為矩陣的稀疏因子。通常認(rèn)為0.05時(shí)稱為稀疏矩陣。 如何進(jìn)行稀疏矩陣的壓縮存儲(chǔ)呢? 按照壓縮存儲(chǔ)的概念,只存儲(chǔ)稀疏矩陣的非零元。因此,除了存儲(chǔ)非零元的值以外,還必須同時(shí)記下它所在行和列的位置(i,j)。反之,一個(gè)三元組(i, j, aij)唯一確定了矩陣A的一個(gè)非零元。由此,稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。,2020/8/3,第5章,27,例如,下列三元組表 (1,2,12),(1,3,9)
18、,(3,1,-3), (3,6,14), (4,3,24) , (5,2,18),(6,1,15), (6,4,-7) 加上(6,7)這一對(duì)行、列值便可作為下圖中矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。,2020/8/3,第5章,28,一、三元組順序表 假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表,則可得稀疏矩陣的一種壓縮存儲(chǔ)方式,稱為三元組順序表。 /稀疏矩陣的三元組順序表存儲(chǔ)表示 #define MAXSIZE 12500 /非零元個(gè)數(shù)的最大值 typedef struct int i,j; ElemType e; Triple; typedef struc
19、t Triple dataMAXSIZE+1;/ 非零元三元組表,data0未用, int mu,nu,tu;/矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) TSMatrix;,data域中表示非零元的三元組是以行序?yàn)橹餍蝽樞蚺帕械?2020/8/3,第5章,29,稀疏矩陣的轉(zhuǎn)置運(yùn)算 轉(zhuǎn)置運(yùn)算是一種最簡(jiǎn)單的矩陣運(yùn)算。對(duì)于一個(gè)m*n的矩陣M,它的轉(zhuǎn)置矩陣T是一個(gè)n*m的矩陣,且aij=bij,1in,1jm。,2020/8/3,第5章,30,顯然,一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣仍然是稀疏矩陣。假設(shè)a和b是TSMatrix型的變量,分別表示矩陣M和T。那么,如何由a得到b呢?,0 1 2 3 4 5 6 7 8,0 1 2 3 4 5 6 7 8,a.data b.data,2020/8/3,第5章,31,從分析a和b之間的差異可見(jiàn),只要做到: (1)將矩陣的行列值相互交換; (2)將每個(gè)三元組中的i和j相互調(diào)換; (3)重排三元組之間的次序 便可實(shí)現(xiàn)矩陣的轉(zhuǎn)置。前二條是容易做到的,關(guān)鍵是如何實(shí)現(xiàn)第三條。即如何使b.
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山里踏雪活動(dòng)方案
- 展廳寵物活動(dòng)方案
- 小紅帽公司活動(dòng)策劃方案
- 山西省基礎(chǔ)教育活動(dòng)方案
- 布丁酒店活動(dòng)方案
- 工作迎新活動(dòng)方案
- 小學(xué)生居家游戲活動(dòng)方案
- 小柴米充值活動(dòng)方案
- 盡快落實(shí)活動(dòng)方案
- 師生環(huán)保進(jìn)社區(qū)活動(dòng)方案
- GB/T 31848-2015汽車貼膜玻璃貼膜要求
- 圖書(shū)管理系統(tǒng)畢業(yè)論文參考文獻(xiàn)精選,參考文獻(xiàn)
- 行政法培訓(xùn)講義課件
- 中國(guó)當(dāng)代舊體詩(shī)選讀幻燈片
- 吉林省全省市縣鄉(xiāng)鎮(zhèn)衛(wèi)生院街道社區(qū)衛(wèi)生服務(wù)中心基本公共衛(wèi)生服務(wù)醫(yī)療機(jī)構(gòu)信息名單目錄995家
- 倔強(qiáng)的小紅軍-精講版課件
- 信息隱藏與數(shù)字水印課件(全)全書(shū)教學(xué)教程完整版電子教案最全幻燈片
- 公開(kāi)招聘社區(qū)居委專職工作人員考試筆試、面試題集及相關(guān)知識(shí)(11套試題含答案)
- 三相負(fù)荷(380V)及單相(220V)最大供電距離計(jì)算表及電壓降計(jì)算表
- 中職數(shù)學(xué)基礎(chǔ)模塊下冊(cè)《等差數(shù)列》ppt說(shuō)課稿
- 計(jì)算機(jī)網(wǎng)絡(luò)專業(yè)畢業(yè)論文:網(wǎng)上鮮花銷售系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
評(píng)論
0/150
提交評(píng)論