數(shù)組與廣義表教學(xué).pptVIP

第五章 數(shù)組與廣義表,5.1 數(shù)組的定義 5.2 數(shù)組的順序表現(xiàn)和實(shí)現(xiàn) 5.3 矩陣的壓縮存儲(chǔ) 5.4 廣義表的定義 5.5 廣義表的存儲(chǔ)結(jié)構(gòu) 5.6 廣義表的遞歸算法,5.1 數(shù)組的定義,數(shù)組：按一定格式排列起來的一列同一屬性的項(xiàng)目,是相同類型的數(shù)據(jù)元素的集合。有一維數(shù)組A5、二維數(shù)組A55、三維數(shù)組A555、多維數(shù)組等。 二維數(shù)組：每一行都是一個(gè)線性表，每一個(gè)數(shù)據(jù)元素既在一個(gè)行表中，又在一個(gè)列表中。,2,5.2 數(shù)組的順序表現(xiàn)和實(shí)現(xiàn),二維數(shù)組以行為主的順序存儲(chǔ) Loc(aij)=Loc(a11)+(i-1)n+(j-1)*L 其中 L=sizeof(datatype),3,2. 二維數(shù)組以列為主的順序存儲(chǔ) 其中 L=sizeof(datatype),4,5,Loc(aij)=Loc(a11)+(i-1)n+(j-1)*L Loc(aij)=Loc(a11)+(j-1)m+(i-1)*L,5.3 矩陣的壓縮存儲(chǔ),下三角矩陣： A為N*N階方陣 存儲(chǔ)方式： 1.按行存儲(chǔ) 2.按列存儲(chǔ) 3.壓縮存儲(chǔ),6,用長度為n(n1)/2的一維數(shù)組B， 一行接一行存放A中下三角部分的元素。,7,用長度為n(n1)/2的一維數(shù)組B， 一列接一列存放A中下三角部分的元素。,8,9,2.對(duì)稱矩陣的壓縮存儲(chǔ),10,3.三對(duì)角矩陣的壓縮存儲(chǔ),11,用一個(gè)長度為3n2的一維數(shù)組B存放三條對(duì)角線上的元素,12,13,4.一般稀疏矩陣的表示,稀疏矩陣的三列二維數(shù)組表示 十字鏈表,14,稀疏矩陣的三列二維數(shù)組表示,15,(1)非零元素所在的行號(hào)i； (2)非零元素所在的列號(hào)j； (3)非零元素的值V。 即每一個(gè)非零元素可以用下列三元組表示： （i，j，V）,16,（1，3，3） （1，8，1） （3，1，9） （4，5，7） （5，7，6） （6，4，2） （6，6，3） （7，3，5）,17,（7，8，8） （1，3，3） （1，8，1） （3，1，9） （4，5，7） （5，7，6） （6，4，2） （6，6，3） （7，3，5）,18,19,POS(k)表示稀疏矩陣A中第k行的第一個(gè)非零元素 （如果有的話）在三列二維數(shù)組B中的行號(hào)； NUM(k)表示稀疏矩陣A中第k行中非零元素的個(gè)數(shù)。 POS(1)2 POS(k)POS(k1)NUM(k1) ， 2km,20,構(gòu)造POS與NUM向量 輸入：與稀疏矩陣A對(duì)應(yīng)的三列二維數(shù)組B。 輸出：POS與NUM向量。 PROCEDURE POSNUM(B，POS，NUM) tB(1，3) 非零元素個(gè)數(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)2 FOR k2 TO m DO POS(k)POS(k1)NUM(k1) 設(shè)置POS向量 RETURN,21,矩陣轉(zhuǎn)置,22,23,輸入：稀疏矩陣A的三列二維數(shù)組表示。 輸出：轉(zhuǎn)置矩陣D（三列二維數(shù)組表示）。 PROCEDURE TRAN(A，D) kA(0，2) 轉(zhuǎn)置稀疏矩陣B的行數(shù) tA(0，3) 非零元素個(gè)數(shù) D(0，1)k； D(0，2)A(0，1)； D(0，3)A(0，3) 置轉(zhuǎn)置矩陣信息 IF (t0) RETURN kk1,24,struct 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； dkk.jan.i； dkk.van.v； kkkk1； return； ,25,十字鏈表,26,用十字鏈表表示稀疏矩陣的結(jié)構(gòu)特點(diǎn) (1)稀疏矩陣的每一行與每一列均用帶表頭結(jié)點(diǎn)的循環(huán)鏈 表表示。 (2)表頭結(jié)點(diǎn)中的行域與列域的值均置為0 （即row0，col0）。 (3)行、列鏈表的表頭結(jié)點(diǎn)合用，且這些表頭結(jié)點(diǎn)通過值 域（即val）相鏈接，并再增加一個(gè)結(jié)點(diǎn)作為它們的 表頭結(jié)點(diǎn)H，其行、列域值分別存放稀疏矩陣的行數(shù) 與列數(shù)。 只要給出頭指針H的值，便可掃描到稀疏矩陣中的任意一個(gè)非零元素。,27,28,29,30,十字鏈表的矩陣相加 #include struct node int row, col, val; struct node * 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-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); ,32,NODE *search_col_last(a,j) NODE * a ; int j; NODE * p, * h; int k: p = a; for (k=0; kright; h=p; while (p-down !=h) p=p-down; return (p); ,33,void 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-val+; ,34,NODE *create_mat() int m, n, t, i, j, k, v ; NODE * h; printf (“ Input 3 -tuples: n“ ) ; printf(“ % 3d: “, 0); scanf(“ %d, %d, %d“, ,35,NODE * mat_add(a,b) NODE * a, * b; NODE *c, *p, *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; ,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 ); ,36,NODE * mat_add(a,b) NODE * a, * b; NODE *c, *p, *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; ,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 ); ,n為表的長度, n = 0 的廣義表為空表 n 0時(shí)，表的第一個(gè)元素d1稱為廣義表的表頭(head)，除此之外，其它元素組成的表 (d2, d3, , dn)稱為廣義表的表尾(tail ),定義: （列表）n ( n 0 )個(gè)元素有限序列，記作 A = (d1, d2, d3, , dn) A是表名，di是表元素，可以是數(shù)據(jù)元素(稱為原子或單元素),也可以是表 (稱為子表),5.4 廣義表的定義,37,E = ( a, E ),D = ( ), ( e ), ( a, ( b, c, d ) ) ),E = (a, ( a, ( a, ) ) ),A = ( ),B = ( e ),C = ( a, ( b, c, d ) ),D = (A , B, C ),廣義表特性 有次序性 有深度(層次) 可共享 可遞歸,展開后所含括號(hào)的層次數(shù),小寫：原子；大寫：子表,深度：1,深度：1,深度：2,深度：3,深度：,例：,A()與A()不同,任一非空廣義表的表頭可能是原子或子表；表尾必定是子表,長度為0，空表,長度為1，表頭與表尾均為(),38,5.5 廣義表的存儲(chǔ)結(jié)構(gòu) 結(jié)點(diǎn)定義,typedef struct GLNode int tag; union DataType data; struct GLNode *dlink; dd; struct GLNode *linkp; GList;,指向本層下一個(gè)結(jié)點(diǎn),指向含子表第一個(gè)元素的結(jié)點(diǎn),39,刪除某子表第一個(gè)結(jié)點(diǎn),40,每個(gè)子表增設(shè)表頭結(jié)點(diǎn) tp指向含第一個(gè)元素的結(jié)點(diǎn) hp留作自用,41,5.6 廣義表遞歸算法的實(shí)現(xiàn) #include struct node int tag; union struct node *dlink; char data; dd; struct node *link; ; typedef struct node NODE;,42,NODE *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); ,43,int equal(s,t) NODE *s, *t; int x; if (s=NULL ,44,練習(xí),1. 寫出順序存貯的棧置空，進(jìn)棧，出棧的算法。 2. 寫出鏈接存貯的棧置空，進(jìn)棧，出棧的算法。 3、寫出二分法順序查找存序表的算法。 4、寫出f(n)=n!的遞歸算法，并畫出4！的棧的變化過程 5、寫出求 g(m,n)= 0 (當(dāng)m=0,n=0時(shí))，g(m,n)=g(m-1,2n)+n (當(dāng)m0,n=0時(shí))的遞歸算法，并畫出g(5,2) 時(shí)的棧的變化過程。 6、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)列的尾部，不設(shè)頭指針試編寫相應(yīng)的置空隊(duì)列，入隊(duì)列，和出隊(duì)列的算法。,45,7、設(shè)有一個(gè)單向循環(huán)鏈表，其結(jié)點(diǎn)含三個(gè)域|：pre,data,next,其中data是數(shù)據(jù)域，next為指針域，其值為后繼結(jié)點(diǎn)的地址，pre也為指針域，值為空（null)