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

2、1組成，其中 Yi=(a0i, a1i, .,am-1i)， 0in-1。 5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組一旦建立，結(jié)構(gòu)中的數(shù)組元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)，即它們的邏輯結(jié)構(gòu)就固定下來了，不再發(fā)生變化。采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組順理成章。1. 行優(yōu)先順序行優(yōu)先順序也稱為低下標(biāo)優(yōu)先。具體實(shí)現(xiàn)時(shí)，按行號(hào)從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，依次類推 在BASIC語(yǔ)言、 PASCAL語(yǔ)言、 C/C+語(yǔ)言等高級(jí)語(yǔ)言程序設(shè)計(jì)中，都是按行優(yōu)先順序存放的。 例如，對(duì)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)存后，變成了一個(gè)線性序列（線性表）。2地址計(jì)算 設(shè)a00的內(nèi)存地址為L(zhǎng)OC(a00)，則aij的內(nèi)存地址按等差數(shù)列計(jì)為:LOC(aij)=LOC(a00)+（in+j）L。同理，三維數(shù)組Amnp按行優(yōu)先存放的地址計(jì)算公式為：LOC(aijk)=LOC(a000)+(inp+jp+k)L。5.3 特殊矩陣的壓縮存儲(chǔ) 5.3.1 特殊矩陣 假如值相同的元素或者零元素在矩陣中的分布有一定的規(guī)律,則稱這類矩陣為特殊矩陣.若一個(gè)n階方陣A中元素滿足下列條件： aij=aji 其中 0 i, jn-1 ，則稱A為對(duì)稱矩陣。1對(duì)稱矩陣 例如，下圖是一個(gè)

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

5、655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa 一個(gè)7X7的三對(duì)角矩陣 矩陣的壓縮存儲(chǔ)問題1對(duì)稱矩陣 因?yàn)榫仃嘇nn是對(duì)稱的，對(duì)稱的兩個(gè)元素可以共用一個(gè)存儲(chǔ)單元，這樣，原來n 階方陣需 n2個(gè)存儲(chǔ)單元，若采用壓縮存儲(chǔ)，僅需 n(n+1)/2個(gè)存貯單元，將近節(jié)約一半存貯單元.問題:如何將n階對(duì)稱方陣對(duì)應(yīng)存放到一個(gè)向量空間s0到s -1中?2)1(+nn例如，對(duì)于下圖的3*3的對(duì)稱矩陣。（1）只存放下三角部分（比較下面兩個(gè)公式） 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對(duì)角矩陣 對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角線為了中心的帶狀區(qū)域中，即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。下圖給出了一個(gè)三對(duì)角矩陣， a00 a01 a10 a11 a12 . . . an-2 n-1 an-1 n-2 an-1 n-1三對(duì)角矩陣 對(duì)這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺泶鎯?chǔ)。除第0行和第n-1行是2個(gè)元素外，每行的非零元素都要是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(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與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個(gè)非零元素，在第i行，有j-i+1個(gè)非零元素，這樣，非零元素aij的地址為： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d=LOC(0,0)+(2i+j)*d 上例中，a34對(duì)應(yīng)著sa10。 k=2*i+j=2*3+4=10 a21對(duì)應(yīng)著sa5 k=2*2+1=5 由此，我們稱sa0.3*n-1是n階三對(duì)角帶狀矩陣A的壓縮存儲(chǔ)表示。5.3.2 稀疏矩陣稀疏矩陣：矩陣階數(shù)很大，非零元個(gè)數(shù)較少，零元很多，但非零元的排列沒

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

9、axsize; /三元組表 int m,n,t; /稀疏矩陣行、列數(shù)、非零元個(gè)數(shù) TSMatrix; 00070015000001800000240001400003000000000009120- 稀疏矩陣M 稀疏矩陣M的三元組表見下圖 （2）帶行指針的鏈表 把具有相同行號(hào)的非零元用一個(gè)單鏈表連接起來，稀疏矩陣中的若干行組成若干個(gè)單鏈表，合起來稱為帶行指針的鏈表。 00070015000001800000240001400003000000000009120- 2. 稀疏矩陣的轉(zhuǎn)置運(yùn)算 轉(zhuǎn)置是矩陣中最簡(jiǎn)單的一種運(yùn)算。對(duì)于一個(gè)mn的矩陣A，它的轉(zhuǎn)置B是一個(gè)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是一個(gè)按列優(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、遍)，這時(shí)算法描述如下：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+; 分析這個(gè)算法，主要的工作是在p和col的兩個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為O(n*t)

12、，即矩陣的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法時(shí)間復(fù)雜度為O(n*m)。當(dāng)非零元素的個(gè)數(shù)t和m*n同數(shù)量級(jí)時(shí)，算法transmatrix的時(shí)間復(fù)雜度為O(n*n2)三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算是法的難度。因此，此算法僅適用于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中每一行)的第一個(gè)非零元轉(zhuǎn)置后在b.data中的正確位置potcol(0cola.cols)，那么在對(duì)a.data的三元

13、組依次作轉(zhuǎn)置時(shí)，只要將三元組按列號(hào)col放置到b.datapotcol中，之后將potcol內(nèi)容加1，以指示第col列的下一個(gè)非零元的正確位置。為了求得位置向量pot，只要先求出A的每一列中非零元個(gè)數(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)稱為L(zhǎng)S的表尾。任何一個(gè)非空廣義表其表頭可能是原子表，也可能是廣義表，而其表尾必定是廣義表。5.5 廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表(a1,a2,a3,an)中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，（或是原子，或是廣義表），因此，難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)

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

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

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