数组与广义表教学.ppt

第五章 数组与广义表,5.1 数组的定义 5.2 数组的顺序表现和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 5.6 广义表的递归算法,5.1 数组的定义,数组：按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。有一维数组A5、二维数组A55、三维数组A555、多维数组等。 二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。,2,5.2 数组的顺序表现和实现,二维数组以行为主的顺序存储 Loc(aij)=Loc(a11)+(i-1)n+(j-1)*L 其中 L=sizeof(datatype),3,2. 二维数组以列为主的顺序存储 其中 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 矩阵的压缩存储,下三角矩阵： A为N*N阶方阵 存储方式： 1.按行存储 2.按列存储 3.压缩存储,6,用长度为n(n1)/2的一维数组B， 一行接一行存放A中下三角部分的元素。,7,用长度为n(n1)/2的一维数组B， 一列接一列存放A中下三角部分的元素。,8,9,2.对称矩阵的压缩存储,10,3.三对角矩阵的压缩存储,11,用一个长度为3n2的一维数组B存放三条对角线上的元素,12,13,4.一般稀疏矩阵的表示,稀疏矩阵的三列二维数组表示 十字链表,14,稀疏矩阵的三列二维数组表示,15,(1)非零元素所在的行号i； (2)非零元素所在的列号j； (3)非零元素的值V。 即每一个非零元素可以用下列三元组表示： （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行的第一个非零元素 （如果有的话）在三列二维数组B中的行号； NUM(k)表示稀疏矩阵A中第k行中非零元素的个数。 POS(1)2 POS(k)POS(k1)NUM(k1) ， 2km,20,构造POS与NUM向量 输入：与稀疏矩阵A对应的三列二维数组B。 输出：POS与NUM向量。 PROCEDURE POSNUM(B，POS，NUM) tB(1，3) 非零元素个数 mB(1，1) 稀疏矩阵行数 FOR k1 TO m DO NUM(k)0 置NUM向量初值 FOR k2 TO t1 DO NUM(B(k,1)NUM(B(k,1)1设置NUM向量 POS(1)2 FOR k2 TO m DO POS(k)POS(k1)NUM(k1) 设置POS向量 RETURN,21,矩阵转置,22,23,输入：稀疏矩阵A的三列二维数组表示。 输出：转置矩阵D（三列二维数组表示）。 PROCEDURE TRAN(A，D) kA(0，2) 转置稀疏矩阵B的行数 tA(0，3) 非零元素个数 D(0，1)k； D(0，2)A(0，1)； D(0，3)A(0，3) 置转置矩阵信息 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,用十字链表表示稀疏矩阵的结构特点 (1)稀疏矩阵的每一行与每一列均用带表头结点的循环链 表表示。 (2)表头结点中的行域与列域的值均置为0 （即row0，col0）。 (3)行、列链表的表头结点合用，且这些表头结点通过值 域（即val）相链接，并再增加一个结点作为它们的 表头结点H，其行、列域值分别存放稀疏矩阵的行数 与列数。 只要给出头指针H的值，便可扫描到稀疏矩阵中的任意一个非零元素。,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时，表的第一个元素d1称为广义表的表头(head)，除此之外，其它元素组成的表 (d2, d3, , dn)称为广义表的表尾(tail ),定义: （列表）n ( n 0 )个元素有限序列，记作 A = (d1, d2, d3, , dn) A是表名，di是表元素，可以是数据元素(称为原子或单元素),也可以是表 (称为子表),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 ),广义表特性 有次序性 有深度(层次) 可共享 可递归,展开后所含括号的层次数,小写：原子；大写：子表,深度：1,深度：1,深度：2,深度：3,深度：,例：,A()与A()不同,任一非空广义表的表头可能是原子或子表；表尾必定是子表,长度为0，空表,长度为1，表头与表尾均为(),38,5.5 广义表的存储结构 结点定义,typedef struct GLNode int tag; union DataType data; struct GLNode *dlink; dd; struct GLNode *linkp; GList;,指向本层下一个结点,指向含子表第一个元素的结点,39,删除某子表第一个结点,40,每个子表增设表头结点 tp指向含第一个元素的结点 hp留作自用,41,5.6 广义表递归算法的实现 #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,练习,1. 写出顺序存贮的栈置空，进栈，出栈的算法。 2. 写出链接存贮的栈置空，进栈，出栈的算法。 3、写出二分法顺序查找存序表的算法。 4、写出f(n)=n!的递归算法，并画出4！的栈的变化过程 5、写出求 g(m,n)= 0 (当m=0,n=0时)，g(m,n)=g(m-1,2n)+n (当m0,n=0时)的递归算法，并画出g(5,2) 时的栈的变化过程。 6、假设以带头结点的循环链表表示队列，并且只设一个指针指向队列的尾部，不设头指针试编写相应的置空队列，入队列，和出队列的算法。,45,7、设有一个单向循环链表，其结点含三个域|：pre,data,next,其中data是数据域，next为指针域，其值为后继结点的地址，pre也为指针域，值为空（null)