數(shù)據(jù)結(jié)構(gòu)課件第五章數(shù)組

1、第五章 數(shù)組和廣義表信息安全系 王靖亞5.5 廣義表5.1 數(shù)組的定義5.3 特殊矩陣及其壓縮存儲5.4 稀疏矩陣本章主要內(nèi)容5.2 數(shù)組的存儲結(jié)構(gòu)5.1多維數(shù)組 5.1.1多維數(shù)組的概念 1一維數(shù)組 一維數(shù)組可以看成是一個線性表或一個向量，在計算機(jī)內(nèi)是存放在一塊連續(xù)的存儲單元中。2二維數(shù)組二維數(shù)組可以看成是向量的推廣。 例如，設(shè)A是一個有m行n列的二維數(shù)組，則A可以表示為：行優(yōu)先的數(shù)組：可以將二維數(shù)組A看成是由m個行向量X0，X1， ，Xm-1T組成，其中，Xi=( ai0, ai1, .,ain-1)， 0im-1；列優(yōu)先的數(shù)組：也可以將二維數(shù)組A看成是由n個列向量Y0, Y1, ,Yn-

2、1組成，其中 Yi=(a0i, a1i, .,am-1i)， 0in-1。 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組一旦建立，結(jié)構(gòu)中的數(shù)組元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動，即它們的邏輯結(jié)構(gòu)就固定下來了，不再發(fā)生變化。采用順序存儲結(jié)構(gòu)表示數(shù)組順理成章。1. 行優(yōu)先順序行優(yōu)先順序也稱為低下標(biāo)優(yōu)先。具體實現(xiàn)時，按行號從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，依次類推 在BASIC語言、 PASCAL語言、 C/C+語言等高級語言程序設(shè)計中，都是按行優(yōu)先順序存放的。 例如，對Amn二維數(shù)組，a00、 a01、 a0n-1；A10、a11、.a1 n-1；am-1 0、am

3、-1 1、am-1 n-1。 即二維數(shù)組按行優(yōu)先存放到內(nèi)存后，變成了一個線性序列（線性表）。2地址計算 設(shè)a00的內(nèi)存地址為LOC(a00)，則aij的內(nèi)存地址按等差數(shù)列計為:LOC(aij)=LOC(a00)+（in+j）L。同理，三維數(shù)組Amnp按行優(yōu)先存放的地址計算公式為：LOC(aijk)=LOC(a000)+(inp+jp+k)L。5.3 特殊矩陣的壓縮存儲 5.3.1 特殊矩陣 假如值相同的元素或者零元素在矩陣中的分布有一定的規(guī)律,則稱這類矩陣為特殊矩陣.若一個n階方陣A中元素滿足下列條件： aij=aji 其中 0 i, jn-1 ，則稱A為對稱矩陣。1對稱矩陣 例如，下圖是一個

4、3*3的對稱矩陣。2三角矩陣 （1）上三角矩陣即矩陣上三角部分元素是隨機(jī)的，而下三角部分元素全部相同（為某常數(shù)C）或全為0。 上三角矩陣 11,11,1110,0100.- - n n nn acccaacaaa （2）下三角矩陣即矩陣的下三角部分元素是隨機(jī)的，而上三角部分元素全部相同（為某常數(shù)C）或全為0。 111,11,0111000.-,nnnnaaacaacca 下三角矩陣 3對角矩陣 若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。例如，下圖為77的三對角矩陣（即有三條對角線上元素非0）。 66

5、655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa 一個7X7的三對角矩陣 矩陣的壓縮存儲問題1對稱矩陣 因為矩陣Ann是對稱的，對稱的兩個元素可以共用一個存儲單元，這樣，原來n 階方陣需 n2個存儲單元，若采用壓縮存儲，僅需 n(n+1)/2個存貯單元，將近節(jié)約一半存貯單元.問題:如何將n階對稱方陣對應(yīng)存放到一個向量空間s0到s -1中?2)1(+nn例如，對于下圖的3*3的對稱矩陣。（1）只存放下三角部分（比較下面兩個公式） i(i -1)/2+j-1 當(dāng) ij k= j

6、(j-1)/2+ i -1 當(dāng) ij i(i+1)/2+j 當(dāng) ij k= j(j+1)/2+i 當(dāng) ij 3對角矩陣 對角矩陣中，所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣， a00 a01 a10 a11 a12 . . . an-2 n-1 an-1 n-2 an-1 n-1三對角矩陣 對這種矩陣，我們也可按行優(yōu)序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數(shù)為3n-2。a00a01 a10a11a12a21 a n-1 n-2a

7、 n-1 n-1K=0 1 2 3 4 5 3n-3 數(shù)組sa中的元素sak與三對角帶狀矩陣中的元素aij存在一一對應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個非零元素，在第i行，有j-i+1個非零元素，這樣，非零元素aij的地址為： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d=LOC(0,0)+(2i+j)*d 上例中，a34對應(yīng)著sa10。 k=2*i+j=2*3+4=10 a21對應(yīng)著sa5 k=2*2+1=5 由此，我們稱sa0.3*n-1是n階三對角帶狀矩陣A的壓縮存儲表示。5.3.2 稀疏矩陣稀疏矩陣：矩陣階數(shù)很大，非零元個數(shù)較少，零元很多，但非零元的排列沒

8、有一定規(guī)律的矩陣。1. 稀疏矩陣的存儲 (1) 三元組表在壓縮存放稀疏矩陣的非零元同時，若還存放此非零元所在的行號和列號，則稱為三元組表法，即稱稀疏矩陣可用三元組表進(jìn)行壓縮存儲，但它是一種順序存貯（按行優(yōu)先順序存放）。一個非零元有行號、列號、值，為一個三元組，整個稀疏矩陣中非零元的三元組合起來稱為三元組表。此時，數(shù)據(jù)類型可描述如下：#define maxsize 12500/定義非零元的最大數(shù)目typedef struct /定義一個三元組 int i,j; /非零元行、列號 datatype v; /非零元值Triple;typedef struct /定義稀疏矩陣 triple datam

9、axsize; /三元組表 int m,n,t; /稀疏矩陣行、列數(shù)、非零元個數(shù) TSMatrix; 00070015000001800000240001400003000000000009120- 稀疏矩陣M 稀疏矩陣M的三元組表見下圖 （2）帶行指針的鏈表 把具有相同行號的非零元用一個單鏈表連接起來，稀疏矩陣中的若干行組成若干個單鏈表，合起來稱為帶行指針的鏈表。 00070015000001800000240001400003000000000009120- 2. 稀疏矩陣的轉(zhuǎn)置運算 轉(zhuǎn)置是矩陣中最簡單的一種運算。對于一個mn的矩陣A，它的轉(zhuǎn)置B是一個nm的矩陣，且Bij=Aji，0in,

10、0jm。稀疏矩陣的轉(zhuǎn)置：將A轉(zhuǎn)置為B，就是將A的三元組表a.data變?yōu)锽的三元組表b.data將a.data中i和j 的值互換，則得到的b.data是一個按列優(yōu)先順序排列的三元組表。再將它的順序適當(dāng)調(diào)整，變成行優(yōu)先排列，即得到轉(zhuǎn)置矩陣B。（1）一般的矩陣轉(zhuǎn)置算法 for(col=0;col=n-1;+col) for(row=0;row=m;+row) tcolrow=mrowcol;（2）按照列序進(jìn)行矩陣轉(zhuǎn)置 由于A的列即為B的行，在a.data中，按列掃描，則得到的b.data必按行優(yōu)先存放。但為了找到A的每一列中所有的非零的元素，每次都必須從頭到尾掃描A的三元組表(有多少列，則掃描多少

11、遍)，這時算法描述如下：Void transmatrix(tripletable a,tripletable b) int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); q=0; for(col=0;cola.n;col+) for(p=0;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; 分析這個算法，主要的工作是在p和col的兩個循環(huán)中完成的，故算法的時間復(fù)雜度為O(n*t)

12、，即矩陣的列數(shù)和非零元的個數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法時間復(fù)雜度為O(n*m)。當(dāng)非零元素的個數(shù)t和m*n同數(shù)量級時，算法transmatrix的時間復(fù)雜度為O(n*n2)三元組順序表雖然節(jié)省了存儲空間，但時間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時還有可能增加算是法的難度。因此，此算法僅適用于t=m*n的情況（3）按照行序進(jìn)行轉(zhuǎn)置(快速轉(zhuǎn)置） 即按a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組放入b中恰當(dāng)?shù)奈恢?。若能在轉(zhuǎn)置前求出矩陣A的每一列col(即B中每一行)的第一個非零元轉(zhuǎn)置后在b.data中的正確位置potcol(0cola.cols)，那么在對a.data的三元

13、組依次作轉(zhuǎn)置時，只要將三元組按列號col放置到b.datapotcol中，之后將potcol內(nèi)容加1，以指示第col列的下一個非零元的正確位置。為了求得位置向量pot，只要先求出A的每一列中非零元個數(shù)numcol，然后利用下面公式： pot1=1 potcol=potcol-1+numcol-1 當(dāng)1cola.cols void fasttranstri(tritupletable b,tritupletable a) int p,q,col,k; int num1.a.n,copt1.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”

14、n); for(col=1;col=a.n;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j;cpot1=1;for(col=2;col=a.t;+col) cpotcol=cpotcol-1+numcol-1;for(p=1;p=1)非空，則a1是LS的表頭，其余元素組成的表(a1,a2,an)稱為LS的表尾。任何一個非空廣義表其表頭可能是原子表，也可能是廣義表，而其表尾必定是廣義表。5.5 廣義表的存儲結(jié)構(gòu)由于廣義表(a1,a2,a3,an)中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，（或是原子，或是廣義表），因此，難以用順序存儲結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?/p>

15、結(jié)構(gòu)，每個數(shù)據(jù)元素可用一個結(jié)點表示。由于廣義表中有兩種數(shù)據(jù)元素，原子或廣義表，因此，需要兩種結(jié)構(gòu)的結(jié)點：一種是表結(jié)點，一種是原子結(jié)點。 表結(jié)點由三個域組成：標(biāo)志域、指示表頭的指針域和指示表尾的指針域；而原子域只需兩個域：標(biāo)志域和值域（具體的存儲見P109)。 表結(jié)點 原子結(jié)點 tag=1 hp tp tag=0 atom題目1: 假設(shè)有二維數(shù)組A6x8，每個元素用相鄰的6 個字節(jié)存儲，存儲器按字節(jié)編址。已知A 的起始存儲地址（基地址）為1000，計算：數(shù)組A的存儲量；數(shù)組A的最后一個元素a57的第一個字節(jié)的地址；按行存儲時，元素a14的第一個字節(jié)的地址；按列存儲時，元素a47的第一個字節(jié)的地址

16、；題目2：假設(shè)按低下標(biāo)優(yōu)先存儲整數(shù)數(shù)組A9X3X5X8 時，第一個元素的字節(jié)地址是100，每 個整數(shù)占四個字節(jié)。問a3125的存儲地址 是什么？ 二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)的范圍從0到8，列下標(biāo)的范圍從1到10，則M至少需要_ _個字節(jié)，M的第8列和第5行共占_個字節(jié)，若M按行優(yōu)先方式存儲，M85的起始地址與M按列優(yōu)先方式存儲時的_元素的起始地址一致。 A、 90 ; 114; M58 B、 180; 54; M89 C、 240; 60; M09 D、 540; 108; M310數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到

17、10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為（）。 A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+225 3、二維A1020采用列序為主方式存儲，每個元素占一個存儲單元，并且A00的存儲地址是200，則A612的地址是_。4、二維數(shù)組A10.205.10采用行序為主方式存儲，每個元素占4個存儲單元，并且A105的存儲地址是1000，則A189的地址是_。 設(shè)有一個1010的對稱矩陣A，將其下三角部分按行存放在一個一維數(shù)組B中，A00存放于B0中，那么A85存放于B中什么位置？設(shè)有一個nn的對稱矩陣A，將其上三角部分按行存放在一個一維數(shù)組B中，A00存放于B0中，那么第i行的對角元素Aii存放于B中（ ）處。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/21.畫出下面廣義表的存儲結(jié)構(gòu)圖，并求它的深度 ( (a) , b), ( ( ( ), d), (e, f) )2.已知下圖為廣義表的存儲結(jié)構(gòu)，寫出它所表示的廣義表設(shè)HAEDp為求廣義表p的表頭函數(shù)，TAILp為求廣義表p的表尾函數(shù)，其中是函數(shù)的符號，給出下列廣義表的運算結(jié)果：HEAD（