第五部分数组与广义表教学课件.ppt
《第五部分数组与广义表教学课件.ppt》由会员分享,可在线阅读,更多相关《第五部分数组与广义表教学课件.ppt(46页珍藏版)》请在三一文库上搜索。
1、第五章 数组与广义表,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. 二维数组以
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
3、,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行的第一个非零元素 (
4、如果有的话)在三列二维数组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(
5、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;
6、 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,其行、列域值
7、分别存放稀疏矩阵的行数 与列数。 只要给出头指针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
8、= 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
9、) 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_c
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 部分 数组 广义 教学 课件
链接地址:https://www.31doc.com/p-3124338.html