大2上數據結構

1、數據結構第五章 數組與廣義表 主講人主講人: :劉波劉波本章要點本章要點v深入掌握數組的相關概念深入掌握數組的相關概念,數組元素順序存儲數組元素順序存儲位置的計算方法位置的計算方法v掌握對特殊矩陣進行壓縮時的下標變換公式掌握對特殊矩陣進行壓縮時的下標變換公式.v了解稀疏矩陣的壓縮存儲方法了解稀疏矩陣的壓縮存儲方法v掌握廣義表的結構特點及其存儲表示方法掌握廣義表的結構特點及其存儲表示方法數組的定義數組的定義v數組的定義方式數組的定義方式1一個一個n維數組類型可以定義為其數組元素為維數組類型可以定義為其數組元素為n-1維數組的一維數組類型維數組的一維數組類型.當當n=1時時,n維數組就退化為定長的

2、線性表，每維數組就退化為定長的線性表，每個元素不可再分解。個元素不可再分解。1, 11 , 10 , 11, 111101, 00100.nmmmnnnmaaaaaaaaaA數組的定義（數組的定義（2）v數組定義方式數組定義方式2（抽象數據類型數組）（抽象數據類型數組）ADT Array 數據對象：數據對象：ji=0,1,bi-1, i=1,2,3,n. D=aj1j2jn|n(0)稱為數組維數，稱為數組維數，bi是數組第是數組第i維的長度，維的長度，ji是數組元素的第是數組元素的第i維下標，維下標， aj1j1jn ElemSet 數據關系：數據關系：R=R1，R2，,Rn Ri=| 0 j

3、k bk-1,1 k n, k i, 0 jji i b bi i-2,-2, aj1jijn, aj1ji+1jn D,i=2,n 數組的定義（數組的定義（3） 基本操作基本操作: InitArray(&A, n, bound1,boundn) /構造數構造數組組A,維數維數n,各維長度各維長度bound1,boundn DestroyArray(&A) /銷毀數組銷毀數組A Value(A, &e, index1,indexn) /將指定的將指定的A元素賦給元素賦給e Assign(&A, e, index1,indexn) /將將e的值賦給所指定的的值賦給所指定的A的元素的元素 ADT

4、Array數組的順序存儲數組的順序存儲v二維數組二維數組Am n元素元素aij, 0 i m-1,0 j n-1存儲結構存儲結構v以行序為主序以行序為主序 Loc(i, j)=Loc(0,0)+(n*i+j) L Lv以列序為主序以列序為主序 Loc(i, j)=Loc(0,0)+(m*j+i) L Lvn n維數組的數據元素存儲地址維數組的數據元素存儲地址( (以第一維優(yōu)先存儲以第一維優(yōu)先存儲) ) Loc(j Loc(j1 1,j,j2 2, ,j jn n)=Loc(0,0,)=Loc(0,0,)+(b)+(b2 2 b bn n j j1 1 + + b b3 3 b bn n j j

5、2 2+ b+ bn n j jn-1n-1+j+jn n) ) L L 矩陣mnmmnnaaaaaaaaa.212222111211矩陣的存儲矩陣的存儲v特殊矩陣特殊矩陣矩陣中的元素排列是有規(guī)律的矩陣中的元素排列是有規(guī)律的矩陣的非零元素很少矩陣的非零元素很少v壓縮存儲壓縮存儲為多個值相同的元素只分配一個存儲空間為多個值相同的元素只分配一個存儲空間對零元素不分配空間對零元素不分配空間1423417232012341275173510對稱矩陣示例對稱矩陣示例對稱矩陣對稱矩陣v性質性質:在在n階矩陣階矩陣A中中, aij=aji, 1 i, j nv壓縮存儲壓縮存儲:只存主對角線只存主對角線以上或

6、以下以上或以下元素元素(包括主對角線包括主對角線)?？捎靡痪S數組存儲?？捎靡痪S數組存儲。v減少存儲空間減少存儲空間:n2-n(n+1)/2v下三角元素下三角元素aij,(i j)與一維數組與一維數組Sak (1 k n)元素的元素的對應關系對應關系 k=i(i-1)/2+j-1v上三角元素上三角元素aij,(i j)與一維數組與一維數組Sak元素的對應關系元素的對應關系 k=j(j-1)/2+i-1Sa下標下標 k=0 1 2 3 4 n(n+1)/2-2 n(n+1)/2-1 a00a10a11a20a21an-1,n-3an-1,n-2an-1,n-1對角矩陣對角矩陣v性質性質:一個一個n

7、階方陣的所階方陣的所有非零元素都集中在以有非零元素都集中在以主對角為中心的帶狀區(qū)主對角為中心的帶狀區(qū)域中域中v壓縮存儲壓縮存儲:將非零元素將非零元素存儲到一維數組中存儲到一維數組中11340006921000177300002059000123004544433433322322211211aaaaaaaaaaa稀疏矩陣稀疏矩陣v性質性質:矩陣中大多數元素值為矩陣中大多數元素值為0,元素分布沒有一元素分布沒有一定規(guī)律定規(guī)律.v設在設在m n矩陣中矩陣中,有有t個元素不為零個元素不為零,稀疏因子為稀疏因子為: =t/(m n)n) 0.05時時,稱為稀疏矩陣稱為稀疏矩陣v壓縮存儲方式壓縮存儲方式

8、:三元組順序存儲三元組順序存儲鏈表存儲鏈表存儲稀疏矩陣示例稀疏矩陣示例0200000000000210010070003三元組順序表三元組順序表v形式描述形式描述: (i, j, aij)v存儲表示存儲表示 #define MAXSIZE 12500 typedef struct int i,j; ElemType e; Triple; 三元組順序表三元組順序表(2)typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; /矩陣的行數矩陣的行數,列數和非零元個數列數和非零元個數 TSMatrix; 存儲特點存儲特點: 非零元在表中按行序有序存儲非零

9、元在表中按行序有序存儲; 最后一行一個元素在最后一行一個元素在data中的序號為中的序號為tu. v示例 0200000000000210010070003 i j e 1 1 3 1 5 7 2 3 -1 3 1 -1 3 2 -2 5 4 2 A.Data A.mu=5 A.nu=5 A.tu=6A=稀疏矩陣的轉置算法稀疏矩陣的轉置算法v方法方法1：按列序遞增轉置法：按列序遞增轉置法 算法的基本思想是：按照被轉置矩陣算法的基本思想是：按照被轉置矩陣M的的“列序列序”（即轉置后（即轉置后T的行序）遞增的順序的行序）遞增的順序進行轉置，并依次送入轉置后矩陣的三元組進行轉置，并依次送入轉置后矩陣

10、的三元組表中，則轉置后矩陣的三元組表恰好是以表中，則轉置后矩陣的三元組表恰好是以“行序為主序行序為主序” Status TransposeSMaxtrix(TSMatrix M, TSMaxtrix &T) /求求M的轉置矩陣的轉置矩陣TT.mu=M.nu; T.nu=M.mu; T.tu=M.Tu; if (T.tu) q=1; /q為為T.data數組下標數組下標,從從1開始開始 for (col=1;col=M.nu;+col) /按按M.data的列讀取的列讀取 for (p=1;p=M.tu;+p) /對所有非零元素對所有非零元素 if (M.datap.j= =col) T.dat

11、aq.i=M.datap.j; T.dataq.j= M.datap.i; T.dataq.e=M.datap.e; +q; return OK; 算法的復雜度為算法的復雜度為O(M.nuM.mu) v方法方法2 2：快速轉置算法：快速轉置算法 需要設需要設num和和cpot兩個數組。兩個數組。numcol表示矩陣表示矩陣M中第中第col列的非零元素個列的非零元素個數；數；數組數組cpotcol表示矩陣表示矩陣M第第col列中第一個非列中第一個非零元素在零元素在T.data中恰當的存儲位置。中恰當的存儲位置。存在下列公式：存在下列公式： 1 1; 1 1 colnumcolcpotcolcpo

12、tcpotvoid FastTransposeSMatrix (TSMatrix M, TSMaxtrix &T) /求求M的轉置矩陣的轉置矩陣TT.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if (T.tu) for (col=1;colM.nu;+col) numcol=0; for (t=1;tM.tu;t+) numM.datat.j+; /統(tǒng)計統(tǒng)計M中每一列含非零元個數中每一列含非零元個數 cpot1=1;/求第求第col列中第一個非列中第一個非零元在零元在T.data中的序號中的序號 for (col=2;colM.nu;+col) cpotcol=cpotcol

13、-1 +numcol-1;vfor (p=1;p M.tu;+p) v col=M.datap.j; /取取M.data的列號存放到的列號存放到col中中v q=cpotcol; /q為為T中當前存儲位置中當前存儲位置v T.dataq.i=M.datap.j;v T.dataq.j=M.datap.i;v T.dataq.e=M.datap.e;v cpotcol=cpotcol+1; /計算第計算第col列中下一個非零元素列中下一個非零元素存儲位置存儲位置v /forv /ifvv時間復雜度為時間復雜度為O(M.nu+M.tu) 行邏輯鏈接的順序表行邏輯鏈接的順序表v目的目的:便于隨機存儲

14、任意一行的非零元素便于隨機存儲任意一行的非零元素v存儲表示存儲表示增加一個增加一個“行行”信息的輔助數組信息的輔助數組rpos typedef struct Triple dataMAXSIZE+1; /三元組表三元組表 int rposMAXRC+1; /各行第一個非零元素的位置數組各行第一個非零元素的位置數組 int mu,nu,tu; /矩陣的行數矩陣的行數,列數和非零元個數列數和非零元個數 RLSMatrix;問題問題: rposrow rposrow+1-1 分別代表什么分別代表什么? 兩個稀疏矩陣相乘求：求：Q=AB初始化初始化Q /Q.mu=A.mu;Q.nu=B.nu;Q.tu

15、=0;If (A.tu*B.tu!=0) /逐行求積和逐行求積和 for (arow=1;arow=A.mu;+arow) ctemp1B.nu=0; 計算計算Q中第中第arow行的積和并存入行的積和并存入ctemp 中中 將將ctemp 中非零元素壓縮到中非零元素壓縮到Q.data中中 兩個稀疏矩陣相乘兩個稀疏矩陣相乘v采用行邏輯連接的順序表存儲稀疏矩陣采用行邏輯連接的順序表存儲稀疏矩陣A和和B (1)對對A.data1A.tu中的每一元素中的每一元素(i,k,A(i,k) (1im1, 1jn1)，找到，找到B.data中所有對應的元中所有對應的元素素(k,j,B(k,j) (1im2,

16、1jn2)相乘并求累計和，相乘并求累計和，即關鍵要找到所有滿足即關鍵要找到所有滿足: A.datap.j=B.dataq.i的元素。的元素。 (2)兩個稀疏矩陣相乘的乘積不一定是稀疏矩陣，兩個稀疏矩陣相乘的乘積不一定是稀疏矩陣，乘積矩陣乘積矩陣Q中的元素是否為非零元素，只有在中的元素是否為非零元素，只有在求得其累加和后才能得到求得其累加和后才能得到。 兩個稀疏矩陣相乘的詳細算法兩個稀疏矩陣相乘的詳細算法 Status MultSMatrix(RLSMatrix A, RLSMatrix B, RLSMatrix Q) /求求QAB If (A.nu!=B.mu) return ERROR; Q

17、.mu=A.mu; Q.nu=B.nu; Q.tu=0; /初始化初始化Q if (A.tu*B.tu!=0) for (arow=1;arrow=A.mu;+arow) /處理處理A的每一行的每一行 ctemp =0; /當前行各元素累加器清零當前行各元素累加器清零 Q.rposarow=Q.tu+1; /計算當前行第一個非零元素計算當前行第一個非零元素 的位置的位置 if (arowA.mu) ca=A.rposarow+1; / ca為為A的下一行第一個非的下一行第一個非 零元素的位置零元素的位置 else ca=A.tu+1; /當前行為最后一行當前行為最后一行 詳細算法（詳細算法（2

18、） for (p=A.rposarow;pca;+p) /對當前行的每一非零元素對當前行的每一非零元素 brow=A.datap.j; /找到對應元素在找到對應元素在B中的行號中的行號 if (browB.mu) cb=B.rposbrow+1; / cb為為B的下一行第一個非的下一行第一個非 零元素的位置零元素的位置 else cb=B.tu+1; / brow為為B的最后一行的最后一行 for (q=B.rposbrow;qcb;+q) ccol=B.dataq.j; /乘積元素在乘積元素在Q中列號中列號 ctempccol= ctempccol+A.datap.e*B.dataq.e;

19、/for q /for p詳細算法（詳細算法（3） for (ccol=1;ccolMAXISIZE) return ERROR; Q.dataQ.tu=(arow,ccol,ctempccol); /if /for arow /if return OK; 鏈式存儲結構鏈式存儲結構v帶行指針向量的單鏈表表示法帶行指針向量的單鏈表表示法每行的非每行的非0元素鏈成一個單鏈表元素鏈成一個單鏈表每行的頭指針組成一個表頭指針數組每行的頭指針組成一個表頭指針數組鏈式存儲結構（鏈式存儲結構（2）v十字鏈表表示法十字鏈表表示法在鏈表中每個非在鏈表中每個非0元素用一個含元素用一個含5個域的結點表示個域的結點表示

20、.每行的頭指針組成一個一維數組每行的頭指針組成一個一維數組每列的頭指針組成一個一維數組每列的頭指針組成一個一維數組v十字鏈表的結點結構十字鏈表的結點結構 i j e down right1 3 2 42856-534723521-1A.cheadA.rhead 鏈式存儲結構鏈式存儲結構(3)v十字鏈表存儲表示十字鏈表存儲表示 typedef struct OLNode int i, j; Elemtype e; struct OLNode *right, *down; OLNode, *Olink; typedef struct Olink *rhead, *chead; int mu,nu,

21、tu; CrossList; 稀疏矩陣十字鏈表的創(chuàng)建稀疏矩陣十字鏈表的創(chuàng)建vvoid CreateSMatrix_OL(CrossList &A) /創(chuàng)建稀疏矩陣創(chuàng)建稀疏矩陣Av if (A) free(A);v scanf(&m,&n,&t); /輸入輸入A的行數、列數和非零元素個數的行數、列數和非零元素個數v A.mu=m; A.nu=n; A.tu=t;v if (!(A.rhead=(OLink*)malloc(m+1)*sizeof(OLNode) v exit(OVERFLOW);v if (!(A.chead=(OLink*)malloc(n+1)*sizeof(OLNode)

22、v exit(OVERFLOW);v A.rhead =A.chead =NULL; /初始化行、列頭指針向量初始化行、列頭指針向量v for (scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e) v /按任意順序輸入非零元素，按任意順序輸入非零元素，i為零時輸入結束為零時輸入結束v if (!(p=(OLNode *)malloc(sizeof(OLNode) exit(OVERFLOW);v p-i=i; p-j=j; p-e=e; /生成結點生成結點v 稀疏矩陣十字鏈表的創(chuàng)建稀疏矩陣十字鏈表的創(chuàng)建vif (A.rheadi=NULL|A.rheadi-jj) v p

23、-right=A.rheadi;v A.rheadi=p; v else v for (q=A.rheadi;(q-right)&q-right-jright); v /在行表中查找插入位置在行表中查找插入位置v p-right=q-right; q-right=p; /完成行插入完成行插入v if (A.cheadj=NULL|A.cheadj-ii) v p-down=A.cheadj;v A.cheadj=p; v else v for (q=A.cheadj;(q-down)&q-down-idown); v /在列表中查找插入位置在列表中查找插入位置v p-down=q-down;

24、q-down=p; /完成列插入完成列插入v v廣義表的定義廣義表的定義vLS=(a1,a2,an) 其中其中: ai是單個數據元素是單個數據元素(或稱為原子或稱為原子)或仍然是一或仍然是一個廣義表個廣義表(或稱子表或稱子表). n是其長度是其長度. 括號的層數為深度括號的層數為深度. 對于非空表對于非空表, a1是表頭是表頭,(a2,a3an)是表尾是表尾v例如例如: A=( ) B=(a, b) C=(a, b), c) D=(A, B, C)=( ), (a, b), (a, b), c) E=(a, E)=(a, (a, (a,.) F=(A)=( )廣義表的抽象數據類型定義廣義表的抽

25、象數據類型定義vADT GList v 數據對象：數據對象：D=ei|i=1,2,n;n0; eiAtomSetv 或或eiGList, AtomSet為某個數據對象為某個數據對象v 數據關系：數據關系：R=| ei-1,eiD,2in v 基本操作：基本操作：v InitGList(&L); /創(chuàng)建空的廣義鏈表創(chuàng)建空的廣義鏈表Lv CreateGList(&L, S); /由串由串S創(chuàng)建廣義表創(chuàng)建廣義表Lv DestroyGList(&L); /銷毀廣義表銷毀廣義表Lv CopyGList(&T, L); /由廣義表由廣義表L復制得到廣義表復制得到廣義表Tv GListLength(L);

26、/求廣義表的求廣義表的L的長度，即元素個數的長度，即元素個數v GListDepth(L); /求廣義表求廣義表L的深度的深度v 廣義表的抽象數據類型定義廣義表的抽象數據類型定義vGListEmpty(L); /判定廣義表判定廣義表L是否為空是否為空v GetHead(L); /取廣義表取廣義表L的頭的頭v GetTail(L); /取廣義表取廣義表L的尾的尾 v InsertFirst_GL(&L, e); /插入元素插入元素e作為廣義表作為廣義表L的的v 第一個元素第一個元素v DeleteFirst_GL(&L, &e); /刪除廣義表刪除廣義表L的第一個元素的第一個元素 v Traverse_GL(L, Visit(); /遍歷廣義表遍歷廣義表L，用，用V