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

1、第5章 數(shù)組和廣義表學(xué)習(xí)要點(diǎn): 了解數(shù)組的兩種存儲(chǔ)表示方法，掌握行序?yàn)橹鞯拇鎯?chǔ)結(jié)構(gòu)中的地址計(jì)算方法掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)三元組表示的矩陣運(yùn)算方法掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法5.1 數(shù)組的定義數(shù)組-線性表的擴(kuò)展，其表中的數(shù)據(jù)元素本身也是一個(gè)數(shù)據(jù)結(jié)構(gòu)。抽象數(shù)據(jù)類型定義：ADT Array 數(shù)據(jù)對(duì)象： Daj1,j2, .,ji,jn| aj1,j2, .,ji,jnElemSet, ji =0,.,bi -1, i=1,2,.,n 數(shù)據(jù)關(guān)系： RR1, R2, ., Rn Ri | 0 jkbk -1, 1kn 且k

2、i, 0 ji bi -2, aj1,. ji,. jn , aj1, .ji+1, .jnD, i=2,.,n ADT Array 基本操作:數(shù)組元素的第i維下標(biāo)數(shù)組的維數(shù)第i維的長(zhǎng)度n維數(shù)組中有 個(gè)數(shù)據(jù)元素：每個(gè)元素都受著n個(gè)關(guān)系的約束。每個(gè)關(guān)系中，元素aj1j2jn(0jibi-2)都有一個(gè)直接后繼元素。每個(gè)元素對(duì)應(yīng)一組下標(biāo)(j1,j2,jn)，每個(gè)下標(biāo)的取值范圍是0jibi-1，bi為第i維的長(zhǎng)度。InitArray(&A, n, bound1, ., boundn) 操作結(jié)果：若維數(shù) n 和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。DestroyArray(&A) 操作結(jié)果：銷毀

3、數(shù)組A。ni=1Value(A, &e, index1, ., indexn) 初始條件：A是n維數(shù)組，e為元素變量，隨后是n 個(gè)下標(biāo)值。 操作結(jié)果：若各下標(biāo)不超界，則e賦值為所指定的A 的元素值，并返回OK。Assign(&A, e, index1, ., indexn) 初始條件：A是n維數(shù)組，e為元素變量，隨后是n 個(gè)下標(biāo)值。 操作結(jié)果：若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。二維數(shù)組的ADT定義： 數(shù)據(jù)對(duì)象: D = aij | 0ib1-1, 0 jb2-1, aijElemSet 數(shù)據(jù)關(guān)系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1

4、COL = | 0ib1-1, 0 jb2-2數(shù)組的向量形式定義：二維數(shù)組Amn，以m行n列的矩陣形式表示： A=(0, 1, , p) (p=m-1或n-1)其中，每一個(gè)j是一個(gè)列向量形式的線性表： j=(a0j, a1j, , am-1,j) 0jn-1行向量形式的線性表： i=(ai0, ai1, , ai,n-1) 0im-1Amn=(a00a01a0,n-1), (a10a11a1,n-1), , (am-1,0am-1,1am-1,n-1)二維數(shù)組類型定義： typedef ElemType Array2mn; typedef ElemType Array1n; typedef A

5、rray1 Array2m;5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組類型的特點(diǎn):只有引用型操作，沒有加工型操作(插入和刪除)；數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一個(gè)一維的結(jié)構(gòu)。有兩種順序映象的方式：以行序?yàn)橹餍?低下標(biāo)優(yōu)先)例如：以列序?yàn)橹餍?高下標(biāo)優(yōu)先)稱為基地址或基址二維數(shù)組A中任一元素ai,j 的存儲(chǔ)位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L (5-1)a0,0a1,0a0,1a1,1a0,2a1,2每一行元素的個(gè)數(shù)注意：如果基址的下標(biāo)為(1,1)，公式的變化！n維數(shù)組行序?yàn)橹餍?/p>

6、存儲(chǔ)位置的映象關(guān)系：稱式(5-2)為 n 維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。數(shù)組的順序存儲(chǔ)表示：#include /標(biāo)準(zhǔn)頭文件，提供宏va_start、 /va_arg和va_end用于存取變長(zhǎng)參數(shù)表#define MAX_ARRAY_DIM 8typedef struct ElemType *base; /數(shù)組元素基址，由InitArray分配 int dim; /數(shù)組維數(shù) int *bounds; /數(shù)組維界基址，由InitArray分配 int *constants; /數(shù)組映像函數(shù)常量基址，由InitArray分配Array;其中 cn = L，ci-1 = bi

7、 ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n(5-2)例如：設(shè)按行序?yàn)橹餍虼鎯?chǔ)整數(shù)數(shù)組A9358時(shí)，第一個(gè)元素的字節(jié)地址是100，每個(gè)整數(shù)占四個(gè)字節(jié)。則LOC(a1111)=？ LOC(a3125)=？解：由題可知，b1=9，b2=3，b3=5，b4=8。又L=4(字節(jié))，則 c4=4，c3=b4c4=84=32， c2=b3c3=532=160，c1=b2c2=3160=480 LOC(a1111)= 100+(480*1+160*1+32*1+4*1)=776 LOC(a3125)= 100+(480*3+160*1

8、+32*2+4*5)=1784第i維的下標(biāo)值每個(gè)數(shù)據(jù)元素占用的存儲(chǔ)空間大小Status InitArray(Array A, int dim, ) /若維數(shù)dim和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。 if (dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim * sizeof(int); if (!A.bounds) exit(OVERFLOW); /若各維長(zhǎng)度合法，則存入A.bounds，并求出A的元素總數(shù)elemtotal elemtotal=1; va_start(ap, dim); /初

9、始化變量ap(可變參數(shù))，運(yùn)行后ap指向第一個(gè) /可變參數(shù)的堆棧地址 for (i=0; idim; +i) A.boundsi=va_arg(ap, int); /返回可變參數(shù)，類型為int if (A.boundsi0; -i) A.constantsi=A.boundsi+1 * A.constantsi+1; return OK;其它操作實(shí)現(xiàn)見教材P94P95。5.3 矩陣的壓縮存儲(chǔ)5.3.1 特殊矩陣定義：值相同的元素或者零元素在矩陣中的分布有一定規(guī)律的矩陣。若n階矩陣A中的元素滿足下述性質(zhì)：aij=aji 1i, jn 則稱為n階對(duì)稱矩陣。存儲(chǔ)方式：以行序?yàn)橹餍虼鎯?chǔ)矩陣的下三角(包

10、括對(duì)角線)中的元。存儲(chǔ)空間：n(n+1)/2一維數(shù)組san(n+1)/2中元素sak和矩陣元aij的對(duì)應(yīng)關(guān)系：例如：當(dāng)ij當(dāng)ijA44=sa10:12536847910(5-3)思考：如何推導(dǎo)式(5-3)的關(guān)系？第i行之前已經(jīng)有i-1行元素被存儲(chǔ)，且每一行只有i個(gè)元素。因此，前i-1行共有：1+2+(i-1)個(gè)元素。則aij的一維位置為，再加上第i行前j-1個(gè)元素： i(i-1)/2+j-1？三角矩陣：下(上)三角矩陣：矩陣的上(下)三角(不包括對(duì)角線)中的元均為常數(shù)c或零的矩陣。增加一個(gè)存儲(chǔ)常數(shù)c的存儲(chǔ)空間。例如：下三角矩陣對(duì)角矩陣：所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。Ann

11、=思考：上三角矩陣中元素與一維數(shù)組元素的對(duì)應(yīng)關(guān)系式？1jin課后作業(yè)P32：5.55.3.2 稀疏矩陣何謂稀疏矩陣？假設(shè) m 行 n 列的矩陣含 t 個(gè)非零元素，則稱為稀疏因子。通常認(rèn)為 0.05 的矩陣為稀疏矩陣。產(chǎn)生的問題:零值元素占了很大空間;計(jì)算中進(jìn)行了很多和零值的運(yùn)算；遇除法，還需判別除數(shù)是否為零。解決問題的原則：盡可能少存或不存零值元素；盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；操作方便。 即：能盡可能快地找到與下標(biāo)值(i, j)對(duì)應(yīng)的元素能盡可能快地找到同一行或同一列的非零值元壓縮存儲(chǔ)方法：只存儲(chǔ)非零元！三元組順序表：一個(gè)三元組(i, j, aij)唯一確定矩陣A的一個(gè)非零元。例如：(1,

12、2, 12), (1, 3, 9), (3, 1, -3), (3, 6, 14), (4, 3, 24), (5, 2, 18), (6, 1, 15), (6, 4, -7)存儲(chǔ)表示：#define MAXSIZE 12500 typedef struct int i, j; /非零元的行下標(biāo)和列下標(biāo) ElemType e; / 非零元的值 Triple; / 三元組類型typedef struct Triple dataMAXSIZE + 1; /行序?yàn)橹餍蚺帕?int mu, nu, tu; /矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) TSMatrix; / 稀疏矩陣類型如何求轉(zhuǎn)置矩陣？用常規(guī)的二

13、維數(shù)組表示時(shí)的算法：for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol; 其時(shí)間復(fù)雜度為: O(munu)M35T53用“三元組”表示時(shí)如何實(shí)現(xiàn)？按照T.data中三元組的次序，依次在M.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置，即按照矩陣M的列序來進(jìn)行轉(zhuǎn)置。1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28M35T53121415-522-7313634281336211422-7432851-5M35T53ijaijijaijStatus

14、TransposeSMatrix(TSMatrix M, TSMatrix &T) /采用三元組表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; /矩陣T的三元組順序表的下標(biāo) for (col=1; col=M.nu; +col) /按照M的列序進(jìn)行轉(zhuǎn)置 for (p=1; p=M.tu; +p) /依次掃描M的三元組順序 /表中的元素的列值 if (M.datap.j = col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q

15、; return OK;/TransposeSMatrix算法時(shí)間復(fù)雜度：O(nutu)適用于tumunu的情況！按照M.data中三元組的次序(M的行)進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入T中恰當(dāng)?shù)奈恢?。如何確定T中的位置？先求得M的每一列中非零元的個(gè)數(shù)；求得每一列的第一個(gè)非零元在T.data中應(yīng)有的位置。2cola.nu(5-4)Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numc

16、ol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; /M中每一列非零元的個(gè)數(shù) cpot1 = 1; for (col=2; col=M.nu; +col) /第col列中第一個(gè)非零元在 /T.data中的序號(hào) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / if return OK; / FastTransposeSMatrix 轉(zhuǎn)置矩陣元素col = M.datap.j;q = cpotcol;T.dataq.i = M.datap.j;T.dataq.j = M.datap.i;T.dat

17、aq.e = M.datap.e;+cpotcol時(shí)間復(fù)雜度為: O(nu+tu)tu和munu等數(shù)量級(jí)時(shí)，時(shí)間復(fù)雜度為: O(munu)三元組順序表(又稱有序的雙下標(biāo)法)的特點(diǎn)：非零元在表中按行序有序存儲(chǔ)，便于依行順序處理的矩陣運(yùn)算。行邏輯鏈接的順序表：將指示“行”信息的數(shù)組cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中，稱這種“帶行鏈接信息”的三元組表為行邏輯鏈接的順序表。#define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; /存儲(chǔ)各行第一個(gè)非零元的位置 int mu, nu, tu; RLSMatrix

18、; / 行邏輯鏈接順序表類型兩個(gè)矩陣相乘：Q=Mm1n1Nm2n2 (n1=m2)經(jīng)典算法：for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 當(dāng)M和N是稀疏矩陣并用三元組表存儲(chǔ)時(shí)，上述算法就不適用了！其時(shí)間復(fù)雜度為: O(m1n2n1)例如：則Q=MN為：它們的三元組M.data、N.data和Q.data分別為：ije11314522-1312ije12221131-2324ije12621-1324M.dataN.dataQ.data(5-5)分析：Q中元素：因此，對(duì)

19、M.data中的每個(gè)元素(i, k, M(i, k)(1im1, 1kn1)，找到N.data中所有相應(yīng)的元素(k, j, N(k, j)(1km2, 1jn2)。利用行邏輯鏈接的順序表中N.rpos數(shù)據(jù)項(xiàng)，可以獲取N中所有相應(yīng)的元素。1im11jn2(5-6)row1234rposrow1235M和N相乘的操作：對(duì)Q的每一個(gè)元素設(shè)一個(gè)累計(jì)和變量ctemp；掃描數(shù)組M中每個(gè)元素M.datap(p=1, 2, ., M.tu)，找到N中所有滿足：M.datap.j=N.dataq.i 的元素N.dataq；求得M.datap和N.dataq乘積并累加到ctemp。ije11314522-1312

20、ije12221131-2324M.dataN.dataije12621-1324Q.data矩陣Q的存儲(chǔ)：將求得的Q中的元素按照行序依次存到一個(gè)一維數(shù)組中；然后掃描該數(shù)組，對(duì)Q進(jìn)行壓縮存儲(chǔ)。算法描述： Q初始化； if Q是非零矩陣 / 逐行求積 for (arow=1; arow=M.mu; +arow) / 處理M的每一行 ctemp = 0; / 累加器清零 計(jì)算Q中第arow行的積并存入ctemp 中； 將ctemp 中非零元壓縮存儲(chǔ)到Q.data； / for arow / if 稀疏矩陣相乘的算法精確描述：Status MultSMatrix (RLSMatrix M, RLSM

21、atrix N, RLSMatrix &Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩陣 for (arow=1; arow=M.mu; +arow) / 處理M的每一行，并壓縮存儲(chǔ)Q的非零元 / for arow / if return OK; / MultSMatrix ctemp = 0; / 當(dāng)前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /對(duì)當(dāng)前

22、行中每一個(gè)非零元找到對(duì)應(yīng)元在N中的行號(hào) brow=M.datap.j; if (brow N.mu ) t = N.rposbrow+1; /t控制N中當(dāng)前行非零元的提取 else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘積元素在Q中列號(hào) ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctemp

23、ccol; / if處理 的每一行M(M.muN.nu)(M.tuN.tu/N.mu)(M.muN.nu)總的時(shí)間復(fù)雜度：(M.muN.nu+M.tuN.tu/N.mu)若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個(gè)數(shù) M.tu = Mmn，N中非零元的個(gè)數(shù) N.tu = Nnp，相乘算法的時(shí)間復(fù)雜度就是 O(mp(1+nMN) ，當(dāng)M0.05 和N0.05及 n 1000時(shí)，相乘算法的時(shí)間復(fù)雜度就相當(dāng)于O(mp)理想的結(jié)果！十字鏈表：當(dāng)矩陣的非零元個(gè)數(shù)和位置在操作中變化較大時(shí)，不宜采用順序存儲(chǔ)結(jié)構(gòu)來表示三元組的線性表。采用鏈表表示：typedef struct OLNod

24、e int i, j; ElemType e; struct OLNode *right, *down; /該非零元所在行表和 /列表的后繼鏈域OLNode; *OLink;typedef struct OLink *rhead, *chead; /行和列鏈表頭指針向量基址，由 /CreateSMatrix分配 int mu, nu, tu;CrossList;矩陣M的十字鏈表如圖：11314522-13215.4 廣義表的定義又稱為列表(lists)，被廣泛用于人工智能等領(lǐng)域的表處理語言LISP語言中。抽象數(shù)據(jù)類型定義：ADT Glist 數(shù)據(jù)對(duì)象：Dei | i=1,2,.,n; n0;

25、eiAtomSet 或 eiGList, AtomSet為某個(gè)數(shù)據(jù)對(duì)象 數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in ADT Glist基本操作:基本操作：結(jié)構(gòu)的創(chuàng)建和銷毀： InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);狀態(tài)函數(shù)： GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);插入和刪除： InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e);遍歷： Traverse

26、_GL(L, Visit();廣義表是遞歸定義的線性結(jié)構(gòu)： LS = (1, 2, ., n )i可以是單個(gè)元素(原子)，也可以是廣義表(子表)。約定：用大寫字母表示廣義表的名稱，用小寫字母表示原子。例如: A = ( )長(zhǎng)度為0；深度為1 F = (d, (e)長(zhǎng)度為2；深度為2 D = (a,(b,c), F)長(zhǎng)度為2；深度為3 C = (A, D, F)長(zhǎng)度為3；深度為4 B = (a, B) = (a, (a, (a, . , ) ) )長(zhǎng)度為2廣義表的名稱廣義表的長(zhǎng)度表頭表尾注意：“表尾”是一個(gè)表！廣義表的深度：指廣義表包含的括號(hào)重?cái)?shù)。廣義表是一個(gè)多層次的線性結(jié)構(gòu)：廣義表的結(jié)構(gòu)特點(diǎn)：

27、廣義表中的數(shù)據(jù)元素有相對(duì)次序；廣義表的長(zhǎng)度定義為最外層包含的元素個(gè)數(shù)；廣義表的深度定義為所含括弧的重?cái)?shù)；廣義表可以共享；廣義表可以是一個(gè)遞歸的表。例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( )d( )bce注意:1. “原子”的深度為 0 2. “空表”的深度為 1 3. 遞歸表的深度是無窮值，長(zhǎng)度是有限值。任何一個(gè)非空廣義表LS = (1, 2, , n)均可分解為：表頭：Head(LS) = 1和表尾：Tail(LS) = (2, , n) 兩部分。例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )，則Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c)