第五部分數(shù)組與廣義表教學ppt課件

1、第五章 數(shù)組與廣義表5.1 數(shù)組的定義5.2 數(shù)組的順序表現(xiàn)和實現(xiàn)5.3 矩陣的緊縮存儲5.4 廣義表的定義5.5 廣義表的存儲構(gòu)造5.6 廣義表的遞歸算法5.1 數(shù)組的定義 數(shù)組：按一定格式陳列起來的一列同一屬性的工程,是一樣類型的數(shù)據(jù)元素的集合。有一維數(shù)組A5、二維數(shù)組A55、三維數(shù)組A555、多維數(shù)組等。 二維數(shù)組：每一行都是一個線性表，每一個數(shù)據(jù)元素既在一個行表中，又在一個列表中。 2mnmmnnnmaaaaaaaaaA.2122221112115.2 數(shù)組的順序表現(xiàn)和實現(xiàn)二維數(shù)組以行為主的順序存儲 Loc(aij)=Loc(a11)+(i-1)n+(j-1)*L 其中 L=sizeo

2、f(datatype)32. 二維數(shù)組以列為主的順序存儲 其中 L=sizeof(datatype)45 Loc(aij)=Loc(a11)+(i-1)n+(j-1)*L Loc(aij)=Loc(a11)+(j-1)m+(i-1)*L5.3 矩陣的緊縮存儲下三角矩陣： A為N*N階方陣存儲方式： 1.按行存儲 2.按列存儲 3.緊縮存儲6用長度為n(n1)/2的一維數(shù)組B，一行接一行存放A中下三角部分的元素。7用長度為n(n1)/2的一維數(shù)組B，一列接一列存放A中下三角部分的元素。892.對稱矩陣的緊縮存儲103.三對角矩陣的緊縮存儲11用一個長度為3n2的一維數(shù)組B存放三條對角線上的元素1

3、2134.普通稀疏矩陣的表示稀疏矩陣的三列二維數(shù)組表示十字鏈表14稀疏矩陣的三列二維數(shù)組表示15(1)非零元素所在的行號i；(2)非零元素所在的列號j；(3)非零元素的值V。即每一個非零元素可以用以下三元組表示： i，j，V161，3，31，8，13，1，94，5，75，7，66，4，26，6，37，3，5177，8，81，3，31，8，13，1，94，5，75，7，66，4，26，6，37，3，51819POS(k)表示稀疏矩陣A中第k行的第一個非零元素 假設(shè)有的話在三列二維數(shù)組B中的行號；NUM(k)表示稀疏矩陣A中第k行中非零元素的個數(shù)。 POS(1)2 POS(k)POS(k1)NUM

4、(k1) ， 2km20構(gòu)造POS與NUM向量輸入：與稀疏矩陣A對應的三列二維數(shù)組B。輸出：POS與NUM向量。PROCEDURE POSNUM(B，POS，NUM)tB(1，3) 非零元素個數(shù)mB(1，1) 稀疏矩陣行數(shù)FOR k1 TO m DO NUM(k)0 置NUM向量初值FOR k2 TO t1 DO NUM(B(k,1)NUM(B(k,1)1設(shè)置NUM向量POS(1)2FOR k2 TO m DO POS(k)POS(k1)NUM(k1) 設(shè)置POS向量RETURN21矩陣轉(zhuǎn)置2223輸入：稀疏矩陣A的三列二維數(shù)組表示。輸出：轉(zhuǎn)置矩陣D三列二維數(shù)組表示。PROCEDURE TRA

5、N(A，D)kA(0，2) 轉(zhuǎn)置稀疏矩陣B的行數(shù)tA(0，3) 非零元素個數(shù)D(0，1)k； D(0，2)A(0，1)； D(0，3)A(0，3) 置轉(zhuǎn)置矩陣信息IF (t0) RETURNkk124struct ab int i； int j； ET v；tran(a，d)struct ab *a， *d； int k，t，kk，m，n； ka0.j； t(int)(a0.v)； d0.ik； d0.ja0.i； d0.va0.v； if (t0) return； kk1； for (m1/0； m=k/k-1； m) for (n1； nt； n) if (an.jm) dkk.ian.j

6、； dkk.jan.i； dkk.van.v； kkkk1； return； 25十字鏈表26用十字鏈表表示稀疏矩陣的構(gòu)造特點(1)稀疏矩陣的每一行與每一列均用帶表頭結(jié)點的循環(huán)鏈 表表示。(2)表頭結(jié)點中的行域與列域的值均置為0 即row0，col0。(3)行、列鏈表的表頭結(jié)點合用，且這些表頭結(jié)點經(jīng)過值 域即val相鏈接，并再添加一個結(jié)點作為它們的 表頭結(jié)點H，其行、列域值分別存放稀疏矩陣的行數(shù) 與列數(shù)。只需給出頭指針H的值，便可掃描到稀疏矩陣中的恣意一個非零元素。27282930十字鏈表的矩陣相加#include struct node int row, col, val; struct n

7、ode * right, * down;typedef struct node NODE;NODE * a, * b, * c;NODE * create_null_mat(m,n)int m, n; NODE *h, * p, * q; int k; h = (NODE*)malloc (sizeof(NODE) ); h-row =m; h-col= n;h-val=0; h-right=h; h-down=h; p=h;for (k=0; kcol=1000;q-right=q;q-down=p-down;p-down=q; P=q; p=h;for (k=0;krow=1000 ; q

8、-down=q; q-right=p-right ; p-right=q; p=q; return(h); 31 NODE * search_row_last( a , i) NODE *a ; int i; NODE *p, *h; int k; p = a ; for (k=0; kdown; h=p; while (p-right!=h) p = p-right; return (p); 32NODE *search_col_last(a,j)NODE * a ; int j; NODE * p, * h;int k:p = a;for (k=0; kright;h=p;while (p

9、-down !=h) p=p-down;return (p); 33void insert_node(a,row,col,value). NODE * a; int row, col, value; NODE * p, * q, * r; p =search_row_last (a, row ); q =search_col_last(a,col); r= (NODE * )malloc(sizeof(NODE); r-row=row; r-col=col; r-val=value; r-right=p-right ; p-right=r; r-down=q-down; q-down=r; a

10、-val+; 34NODE *create_mat() int m, n, t, i, j, k, v ;NODE * h;printf ( Input 3 -tuples: n ) ;printf( % 3d: , 0);scanf( %d, %d, %d, &m,&n,&t);h=create_null_mat(m,n);for (k=1; krow, a-col);p = a-down; u =b-down;while (p!=a) q = p-right; v=u-right;while (q != p | v != u) if ( q-col = = v-co

11、l) if (q-val + v-val != 0) insert_node (c,q-row, q-col, q-val+v-val ); q=q-right ; v=v-right; else if (q-colcol ) insert_node (c, q-row, q-col, q-val ); q=q-right; else insert_node(c, v-row, v-col, v-val ); v=v-right; p=p-down; u = u-down; return (c ); 36NODE * mat_add(a,b)NODE * a, * b; NODE *c, *p

12、, *q, *u, *v;c = create_null_mat (a-row, a-col);p=a-down; u =b-down;while (p!=a) q=p-right; v=u-right;while (q!=p|v!=u) if (q-col=v-col) if (q-val+v-val!=0) insert_node (c,q-row,q-col, q-val+v-val); q=q-right ; v=v-right; elseif (q-colcol ) insert_node (c, q-row, q-col, q-val ); q=q-right; else inse

13、rt_node(c, v-row, v-col, v-val ); v=v-right; P=p-down; u = u-down;return (c );vn為表的長度, n = 0 的廣義表為空表vn 0時，表的第一個元素d1稱為廣義表的表頭(head)，除此之外，其它元素組成的表 (d2, d3, , dn)稱為廣義表的表尾(tail )定義: 列表n ( n 0 )個元素有限序列，記作 A = (d1, d2, d3, , dn)A是表名，di是表元素，可以是數(shù)據(jù)元素(稱為原子或單元素),也可以是表 (稱為子表)5.4 廣義表的定義37E = ( a, E )D = ( ), ( e

14、), ( a, ( b, c, d ) ) )E = (a, ( a, ( a, ) ) )A = ( )B = ( e )C = ( a, ( b, c, d ) )D = (A , B, C )A A是空表，長度為是空表，長度為0 0B B只需一個原子，長度為只需一個原子，長度為1 1D D長度為長度為3,3,三個子表三個子表 C C長度為長度為2,2,一個原子和子表一個原子和子表E E長度為長度為2,2,遞歸表遞歸表 廣義表特性v有次序性 v有深度(層次) v可共享 v 可遞歸展開后所含括號的層次數(shù)展開后所含括號的層次數(shù)小寫：原子；大寫：子表小寫：原子；大寫：子表深度：1深度：1深度：2

15、深度：3深度：例：例：nA()與A()不同n任一非空廣義表的表頭能夠是原子或子表；表尾必定是子表 長度為長度為0 0，空表，空表長度為長度為1 1，表頭與表尾均為，表頭與表尾均為()()385.5 5.5 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造結(jié)點定義結(jié)點定義 tag =1 dlink link 表結(jié)點表結(jié)點 tag =0 data link 原子結(jié)點原子結(jié)點typedef struct GLNode int tag; union DataType data; struct GLNode *dlink; dd; struct GLNode *linkp;GList;指向本層下一個結(jié)點指向本層下一個結(jié)

16、點指向含子表第一個元素的結(jié)點指向含子表第一個元素的結(jié)點391 1 0e 1 0a1 0b0c0d 1 11 1 1 0a1 刪除某子表第一個結(jié)點刪除某子表第一個結(jié)點A = ( )E = ( a, E )B = ( e )C = ( a, ( b, c, d ) )D = (A , B, C )401 1 10e 1 0a1 0b0c0d 111 0a1 11 11 1 1每個子表增設(shè)表頭結(jié)點tp指向含第一個元素的結(jié)點hp留作自用A = ( )E = ( a, E )B = ( e )C = ( a, ( b, c, d ) )D = (A , B, C )41 5.6 5.6 廣義表遞歸算法的

17、實現(xiàn)廣義表遞歸算法的實現(xiàn)#include #include struct node int tag;struct node int tag; union struct node union struct node * *dlink;dlink; char data; char data; dd; dd; struct node struct node * *link;link; ; ;typedef struct node NODE;typedef struct node NODE; tag =1 dlink link 表結(jié)點表結(jié)點 tag =0 data link 原子結(jié)點原子結(jié)點42 NO

18、DE *copy(p) NODE * p; NODE *q; if (P=NULL) return(NULL); q=(NODE * )malloc (sizeof(NODE); q-tag = p-tag; if (p-tag) q-dd.dlink=copy(p-dd.dlink); else q-dd.data=p-dd.data; q-link=copy(p-link); return(q); 1 0a1 0b0c0d 1q 0a1 0b0c0d 43 int equal(s,t) NODE *s, *t; int x; if (s=NULL& t=NULL) return(1); if (s!=NULL & t!=NULL) if (s-tag=t-tag) if (!s-tag) if (s-dd.data=t-dd.data) x=1; else x=0; else x=equal(s-dd.dlink, t-dd.dlink); if (x) return(equal(s-link,t-link); return(0); 1 0a1 0b0c0d