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

1、第 5 章數(shù)組和廣義表第 5 章數(shù)組和廣義表5.1 數(shù)組的定義5.1 數(shù)組定義ADT Array 數(shù)據(jù)對(duì)象：ji=0,.,bi-1,i=1,2,.,n, D=aj1j2.jn|n0, aj1j2.jnElemSet 數(shù)據(jù)關(guān)系： R=R1,R2,.,Rn Ri=| aj1. ji.jn, aj1.ji+1.jn D 基本操作： InitArray(&A,n,bound1,.boundn) DestroyArray(&A) Value(A,&e,index1,.indexn) Assign(&A,e,index1,.indexn)ADT Array數(shù)組定義ADT Array二維數(shù)組可以將二維數(shù)組看

2、成一個(gè)定長的線性表，它的每個(gè)數(shù)據(jù)元素也是一個(gè)定長線性表。A=(a0,a1,.,ap);ai=(a0j,a1j,.am-1j)typedef ElemType Array2mn;typedef ElemType Array1n;typedef Array1 Array2m;二維數(shù)組可以將二維數(shù)組看成一個(gè)定長的線性表，它的每個(gè)數(shù)據(jù)元素(0,0)(m-1,n-1)二維數(shù)組，m 行，n 列元素個(gè)數(shù)：m*n每個(gè)元素由行、列兩個(gè)關(guān)系約束(0,0)(m-1,n-1)二維數(shù)組，m 行，n 列5.2 數(shù)組的順序表示和實(shí)現(xiàn)5.2 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)以行為主序 例： A32 A00, A01, A10, A11,

3、A20, A21 LOCij=LOC00+(n*i+j)*L L為每個(gè)元素占用的空間單元數(shù)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)以行為主序數(shù)組的順序存儲(chǔ)結(jié)構(gòu)以列為主序 例 A32 A00,A10,A20,A01,A11,A21 LOCij=LOC00+(m*j+i)*L L為每個(gè)元素占用的空間單元數(shù)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)以列為主序假設(shè)：b1,b2,b3,.bn為每一維的元素個(gè)數(shù)LOCj1,j2,.jn=LOC0,0,.,0 +(b2*b3.*bn*j1 + b3*.*bn*j2,+.+ bn*jn-1+jn)L=LOC0,0,.,0+( )L=LOC0,0,.,0+其中:cn=L,ci-1=bi*ci 1i=n假設(shè)：

4、b1,b2,b3,.bn為每一維的元素個(gè)數(shù)三維數(shù)組A684共6*8*4=192個(gè)元素假設(shè)：每個(gè)元素占據(jù)L=1個(gè)存儲(chǔ)單元b1=6, b2=8, b3=4, L=1則：c3=L=1 c2=c3*b3=c3*4=1*4=4 c1=c2*b2=4*8=4*8=32A342=0+32*3+4*4+2 =114三維數(shù)組A684共6*8*4=192個(gè)元素#include /可變長參數(shù)#define MAX_ARRAY_DIM 8typedef struct ElemType *base; /數(shù)據(jù)元素基址 int dim; /數(shù)組維數(shù) int *bounds; /每一維的元素個(gè)數(shù) int *constants

5、; /映像函數(shù)常數(shù)#include /可變長參數(shù)Status InitArray(Array &A,int dim,.) if (dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=new intdim; if (!A.bounds) exit(OVERFLOW); elemtotal=1; va_start(ap,dim); /初始化參數(shù)列表 for (i=0;idim;i+) A.boundsi=va_arg(ap,int); /讀取參數(shù) if (A.boundsi=0;i-) A.constantsi= A.boundsi+1*A.co

6、nstantsi+1; return OK; A.base=new ElemTypeelemtoStauts DestroyArray(Array &A) if (!A.base) return ERROR; delete A.base; A.base=NULL; if (!A.bounds) return ERROR; delete A.bounds; A.bounds=NULL; if (!contants) return ERROR; delete A.contants; A.contants=NULL; return OK;Stauts DestroyArray(Array &A)St

7、atus Locate(Array A,va_list ap,int &off) off=0; for (i=0;iA.dim;i+) ind=va_arg(ap,int); if (ind=A.boundsi) return OVERFLOW; off +=A.constantsi*ind; return OK;三維數(shù)組A684Status Locate(Array A,va_list Stauts Value(Array A,ElemType &e,.) va_start(ap,e); if (result=Locate(A,ap,off)=0) return result; e=*(A.

8、base+off); return OK;Stauts Value(Array A,ElemType Status Assign(Array &A,ElemType e,.) va_start(ap,e); if (result=Locate(A,ap,off)=j-1 ij2 0 0 0 02 4 7 9 5 7 52. 稀疏矩陣0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 06*7判定稀疏矩陣的標(biāo)準(zhǔn)：t/(m*n)T按照 T 中的順序在 M 中選擇相應(yīng)的元素并放入T中

9、。 時(shí)間復(fù)雜度 O(M.nu*M.tu)依次把 M 中的元素轉(zhuǎn)置到T中，再對(duì)T進(jìn)行排序。 時(shí)間復(fù)雜度 O(M.tu*log(M.tu)轉(zhuǎn)置方法 M-T按照 T 中的順序在 M 中選擇相應(yīng)的元素Stauts TransposeSMatrix(TSMatrix M,TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; for (col=1;col=M.nu;+col) /按列掃描 for (p=1;p=M.tu;+p) if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.data

10、p.i; T.dataq.e=M.datap.e; +q; return OK;時(shí)間復(fù)雜度：O(M.nu*M.tu)Stauts TransposeSMatrix(TSMatr三元組快速轉(zhuǎn)置1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -71 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14M T三元組快速轉(zhuǎn)置1 2 121 3快速轉(zhuǎn)置法元素一次定位時(shí)間復(fù)雜度O(M.nu+M.tu)快速轉(zhuǎn)置法元素一次定位for (col=1;col=M.nu;+=col) numcol=0;for (t=1;t=M.tu;+

11、t) +numM.datat.j;/累計(jì)每列的元素?cái)?shù)目計(jì)算各列第一個(gè)非零元素在T中的位置cpot1=1;for (col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1統(tǒng)計(jì)M中各列的非零元素個(gè)數(shù)for (col=1;col=M.nu;+=col)統(tǒng)計(jì)M1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -71 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14M T22210101 2 3 4 5 6 7num1357889cpot1 2 121 3 -3M Status Fa

12、stTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; 計(jì)算num,cpot的值； for (p=1;p=M.tu;+p) col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; cpotcol+; return OK; Status FastTransposeSMatrix(TS(2) 行邏輯鏈接表示法為了便于隨機(jī)存取任意一行的非零元素，需知道每一行的第一個(gè)非零元素在三元組表

13、中的位置。為此，將此信息保留在結(jié)構(gòu)體類型中。typedef struct Triple dataMAXSIZE+1; int rposMAXRC+1; int mu,nu,tu;RLSMatrix;(2) 行邏輯鏈接表示法為了便于隨機(jī)存取任意一行的非零元素，1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -71 2 3 4 5 6133567M.rposM.mu=6M.nu=7M.tu=8M.data1 2 121 2 3 行邏輯鏈接矩陣相乘Q m1*n2=Mm1*n1*N m2*n2 (n1=m2)for (i=1;i=m1;i+) for (j=1

14、;j=n2+j) Qij=0; for (k=1;k=n1;k+) Qij=Qij+Mik*Nkj 時(shí)間復(fù)雜度O(m1*n1*n2)行邏輯鏈接矩陣相乘Q m1*n2=Mm1*n1*N m2*相乘操作的特點(diǎn)兩個(gè)稀疏矩陣相乘，結(jié)果不一定是稀疏矩陣Qij= Mik*Nkj每個(gè)M.datap要與N中所有滿足條件 M.datap.j = N.dataq.i 的元素進(jìn)行相乘操作 相乘操作的特點(diǎn)兩個(gè)稀疏矩陣相乘，結(jié)果不一定是稀疏矩陣M=1 2 3 4 1235rpos1 1 31 4 52 2 -13 1 21 2 22 1 13 1 -23 2 4N=0 0 50 -1 0 02 0 0 00 20-2

15、40 03*44*21 2 3 134rposM=1 2 3 4 1235Q 初始化；if （M與N都不是零矩陣） for (arow=1;arow=M.mu; arow +) ctemp =0; 計(jì)算Q中第arow行的積并存入ctemp 中； 將ctemp 中非零元素壓縮存儲(chǔ)到Q.data； i,kk,.Q 初始化；i,kk,.Status MultSMatrix(RLSMatrix M, RLSMatrix 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) fo

16、r (arow=1;arow=M.mu;arow+) Ctemp=0; Q.rposarow=Q.tu+1; /Q的rpos值 if (arowM.mu) tp=M.rposarow+1; else tp=M.tu+1;Status MultSMatrix(RLSMatrix M for (p=M.rposarow;ptp;p+) brow=M.datap.j; /N中的位置 if (browN.mu) t=N.rposbrow+1; else t=N.tu+1; for (q=N.rposbrow;qt;q+) ccol=N.dataq.j; ctempccol+=M.datap.e*N.d

17、ataq.e; for (ccol=1;ccolMAXSIZE) return ERROR; Q.dataQ.tu=(arow,ccol,ctempccol); return OK; for (p=M.rposarow;pmnt; if (!(M.rhead=new OLinkm+1) exit(OVERFLOW); if (!(N.chead=new OLinkn+1) exit(OVERFLOW); M.rhead =M.chead =NULL; for (i=1;iije; if (!(p=new OLNode) exit(OVERFLOW): p-i=i;p-j=j;p-e=e; if

18、 (M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p; else for (q=M.rheadi;(q-right)&q-right-jright); p-right=q-right;q-right=p; if (M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p; else for (q=M.cheadj;(q-down)&q-down-idown); p-down=q-down;q-down=p; return OK; Status CreateSMatrix_OL(CrossL

19、十字鏈表相加 A+B-A分析相加后結(jié)點(diǎn)由三類組成原A中結(jié)點(diǎn) (Aij0,Bij=0)B 中結(jié)點(diǎn) (Aij=0,Bij0)A,B之和 (Aij0,Bij0)十字鏈表相加 A+B-A分析思路逐行一列一列比較(pa-jpb-j)或 pa行已處理完在A中插入Bij;(pa-jj)A移動(dòng)指針;(pa-j=pb-j)if 之和不為零 then 修改pa-e else 刪除pa；思路逐行一列一列比較注意由于每個(gè)結(jié)點(diǎn)處在兩個(gè)鏈表中,因而插入、刪除要同時(shí)對(duì)兩個(gè)方向的鏈表進(jìn)行。沒有破壞B十字鏈表。注意由于每個(gè)結(jié)點(diǎn)處在兩個(gè)鏈表中,因而插入、刪除要同時(shí)對(duì)兩個(gè)方5.4 廣義表的定義5.4 廣義表的定義廣義表的定義長度為

20、n的廣義表是一種數(shù)據(jù)結(jié)構(gòu) Lists=(D,R)D=di|i=1,2,.,n,n=0, 且diD0或di ListsR=LR LR=|d i-1, di屬于D，2=i=1 1=itag=ATOM) return 0; for (max=0,pp=L;pp;pp=pp-ptr.tp) dep=GListDepth(pp-ptr.hp); if (depmax) max=dep; return max+1;int GListDepth(GList L)復(fù)制廣義表非空廣義表由表頭和表尾唯一確定基本項(xiàng): 空表歸納項(xiàng): 分別復(fù)制表頭和表尾復(fù)制廣義表非空廣義表由表頭和表尾唯一確定Status CopyGList(GList &T,GList L) if (!L) T=NULL; /空表 else if (!(T=new GLNode) exit(OVERFLOW); T-tag=L-tag; if (L-tag=ATOM) T-data=L-data; else CopyGList(T-ptr.hp,L-ptr.hp); CopyGList(T-ptr.tp,L-ptr.tp); return OK;Status CopyGList(GList &T,GLisStatus CreateGList(GLisst