数组与广义表1.ppt

第五章 数组,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义与存储,5.1 数组的定义,维数和维界 二维数组的类型定义: 等价于 typedef ElemType Array1n; typedef Array1 Array2m; typedef ElemType Array2mn; Array2 A; 二维的数组 = 定长的线性表 a11 a12 a13 . a1n a21 a22 a23 . a2n Amxn= am1 am2 am3 . amn Amxn= (a11,a12,a13,.a1n),(a21,a22,a23,.a2n),.,(am1,am2,am3,.amn),数组的抽象数据类型,ADT Array 数据对象：D = aj1j2.jn | n(0)称为数组的维数,bi是数组第i维的长度, ji是数组元素的第i维下标, aj1j2.jnElemset 数据关系： R=R1 , R2 . Rn Ri = aj1.ji.jn, aj1.ji+1.jn |0 jk bk-1, 1 k n, aj1.ji.jn, aj1.ji+1.jn D。 基本操作： InitArray( Assign(&A,e, index1,index2,.,indexn) ADT Array,5.2 数组的顺序表示和实现,除了初始化和销毁之外, 数组一般只有存取操作和修改元素值的操作. 通常不作删除和插入. 行序为主序:(C语言,PASCAL, BASIC等) Amxn= (a11,a12,a13,.a1n,a21,a22,a23,.a2n,.am1,am2,am3,.amn) LOC1,1 为基地址: LOCi,j = LOC1,1 + (n*(i-1)+j-1)*L (1=i=m, 1=j=n, 每个数据元素占L个存储单元),例5.1: 若 L=2, LOC1,1 = 1000,LOC3,4 = LOC1,1 + (5*(3-1)+4-1)*L = 1000 + 13 * 2 = 1026 LOC0,0 为基地址: LOCi,j = LOC0,0 + (n*i+j)*L (0=im, 0=jn, 每个数据元素占L个存储单元) LOCi,j,k = LOC0,0,0 + (n*h*i+ h*j + k)*L (0=im, 0=jn, 0=kh, 每个数据元素占L个存储单元),a11 a12 a13 a14 a15 A4x5 = a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45,一般n维数组的列主元存储地址计算公式,b1,b2,.,bn是n维的维界,数组元素A(j1,j2,.,jn)的存储位置为 LOCj1,j2,.jn= LOC0,0,.,0 + (b2*b3*.*bn*j1 + b3*.*bn*j2 + + bn*jn-1 + jn )*L n-1 n = LOC0,0,.,0 + ( ji bk + jn)*L i=1 k=i+1 例: 在C语言中,设 数组A5678的首地址为 2000, 每个元素占2个字节; 求元素A3454的地址. LOC3,4,5,4 = 2000 + (6*7*8*3 + 7*8*4 + 8*5 + 4)*2 = 2000 + ( 336*3 + 56*4 + 8*5 + 1*4)*2 = 2000 + (1008 + 224 + 40 + 4)*2 = 4552,列序为主序: (FORTRAN),Amxn= (a11,a21,a31,.am1),(a12,a22,a32,.am 2),.(a1n,a2n,a3n,.amn) LOC1,1 为基地址: LOCi,j = LOC1,1 + (m*(j-1)+i-1)*L (1=i=m, 1=j=n, 每个数据元素占L个存储单元) 例5.2: 若 L=2, LOC1,1 = 1000 LOC3,4 = LOC1,1 + (4*(4-1)+3-1)*L = 1000 + 14 * 2 = 1028 LOC0,0 为基地址: LOCi,j = LOC0,0 + (m*j+i)*L (0=i=m, 0=j=n, 每个数据元素占L个存储单元) LOCi,j,k = LOC0,0,0 + (m*(n*k)+j)+i) *L,a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45,数组顺序存储的表示和实现,InitArray(Array 若各下标不超界,则e赋值为所指定的A的元素值,并返回OK Assign(Array &A, ElemType e, .) 若各下标不超界,则将e的值赋给所指定的A的元素,并返回OK,0 1 . dim-1,#include #define MAX_ARRAY_DIM 8 typedef struct ElemType *base; int dim; int *bounds; int *constants; Array;,Status InitArray(Array ,InitArray(A,4,5,6,7,8);,base,dim (4),bounds,constants,elemtotal-1,7,0 1 2 3,8,6,5,336,1,Array A5678;,8,56,0,5*6*7*8,补充：va函数的定义和va宏 C语言支持va函数，作为C语言的扩展-C+同样支持va函数，但在C+中并不推荐使用，C+引入的多态性同样可以实现参数个数可变的函数。不过，C+的重载功能毕竟只能是有限多个可以预见的参数个数。比较而言，C中的va函数则可以定义无穷多个相当于C+的重载函数，这方面C+是无能为力的。va函数的优势表现在使用的方便性和易用性上，可以使代码更简洁。C编译器为了统一在不同的硬件架构、硬件平台上的实现，和增加代码的可移植性，提供了一系列宏来屏蔽硬件环境不同带来的差异。 ANSI C标准下，va的宏定义在stdarg.h中，它们有：va_list，va_start()，va_arg()，va_end()。,/ 例2：求任意个自然数的平方和： int SqSum(int n1, .) va_list arg_ptr; int nSqSum = 0, n = n1; va_start(arg_ptr, n1); while (n 0) nSqSum += (n * n); n = va_arg(arg_ptr, int); va_end(arg_ptr); return nSqSum; / 调用时 int nSqSum = SqSum(7, 2, 7, 11, -1);,可变参数函数的原型声明格式为： type VAFunction(type arg1, type arg2, ); 参数可以分为两部分：个数确定的固定参数和个数可变的可选参数。函数至少需要一个固定参数，固定参数的声明和普通函数一样；可选参数由于个数不确定，声明时用“表示。固定参数和可选参数公同构成一个函数的参数列表。 借助上面这个简单的例2，来看看各个va_xxx的作用。 va_list arg_ptr：定义一个指向个数可变的参数列表指针； va_start(arg_ptr, argN)：使参数列表指针arg_ptr指向函数参数列表中的第一个可选参数，说明：argN是位于第一个可选参数之前的固定参数，（或者说，最后一个固定参数；之前的一个参数），函数参数列表中参数在内存中的顺序与函数声明时的顺序是一致的。如果有一va函数的声明是void va_test(char a, char b, char c, )，则它的固定参数依次是a,b,c，最后一个固定参数argN为c，因此就是va_start(arg_ptr, c)。,va_arg(arg_ptr, type)：返回参数列表中指针arg_ptr所指的参数，返回类型为type，并使指针arg_ptr指向参数列表中下一个参数。 va_copy(dest, src)：dest，src的类型都是va_list，va_copy()用于复制参数列表指针，将dest初始化为src。 va_end(arg_ptr)：清空参数列表，并置参数指针arg_ptr无效。说明：指针arg_ptr被置无效后，可以通过调用va_start()、va_copy()恢复arg_ptr。每次调用va_start() / va_copy()后，必须得有相应的va_end()与之匹配。参数指针可以在参数列表中随意地来回移动，但必须在va_start() va_end()之内。,Status DestroyArray(Array ,销毁数组A,若ap所指的各下标值合法, 则求出该元素在A中的位置,Status Locate(Array A, va_list ap, int ,i,off,A是n维数组, e为元素变量, 随后是n个下标值; 若各下标不超界, 则e赋值为所指定的A的元素值,并返回OK,Status Value(Array A, ElemType ,i,off,e,A是n维数组, e为元素变量, 随后是n个下标值;若各下标不超界,则将e的值赋给所指定的A的元素,并返回OK,Status Assign(Array ,i,off,主程序及例子,main() Array A; int i,j,e; InitArray( ,实验与习题,理论习题 5.1, 5.2, 5.3, 5.6 5.8 实验题: 写一个主程序来上机验证数组的顺序存储结构的四个基本操作；并计算A=B+C 3 4 5 6 9 7 5 3 B = 7 8 9 10 C = 2 4 6 8 1 2 3 4 3 6 9 12 5.18,5.3 矩阵的压缩存储,矩阵: 二维数组 特殊矩阵: 大量重复元素或大量0元素 稀疏矩阵: 大量0元素 压缩存储: 重复元素只分配一个存储空间,0元素不分配存储空间,5.3.1 特殊矩阵,对称矩阵: aij = aji (1 1时, aij = 0, (1=i,j=n),对称矩阵: aij = aji (1=i,j=n) 存储元素数: 1+2+.+n = n(n+1)/2,一维数组SA1n(n+1)/2作为数组A下三角元素的 存储结构: SAk = a11, a21, a22, a31, . , an1, . , ann k = 1 2 3 4 n(n-1)/2+1 n(n+1)/2 SAk和Ai, j的一一对应关系: i(i-1)/2 + j 当 i = j k = j(j-1)/2 + i 当 i j,例5.3 对称矩阵,n = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15 一维数组SA115作为数组A的存储结构: SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5) 如: a5,3 = a3,5 = 7 k = 5(5-1)/2 + 3 = 13 故:sa13 = 7,下三角矩阵: 当ij时, aij = 0, (1=i, j=n),同样用一维数组SA1n(n+1)/2作为数组A非零元素的存储结构: sak和ai, j的一一对应关系: sak, k = i(i-1)/2 + j ai, j = (当 i = j) 0 (当 i j),例5.4 下三角矩阵,4 0 0 0 0 5 2 0 0 0 A = 3 1 3 0 0 2 5 2 8 0 1 6 7 9 5 如: a5,3 = 7 k = 5(5-1)/2 + 3 = 13 故:sa13 = 7 但 a3,5 = 0,三对角矩阵: 当|i-j| 1时, aij = 0, (1=i,j=n),a11 a12 0 0 . 0 a21 a22 a23 0 . 0 Anxn = 0 a32 a33 a34 . 0 0 0 0 . ann-1 ann 一维数组SA13*n-2作为数组A下三角元素的存储结构: SAk=a11,a12,a21,a22,a23,a32,a33,a34,.,ann-1,ann k = 1 2 3 4 5 6 7 8 3n-3 3n-2,sak和ai,j的一一对应关系: sak, k = 3*(i-1) + j-i+1, ai, j = 当 |i - j|1,例5.5 三对角矩阵,4 3 0 0 0 5 2 2 0 0 A = 0 1 0 4 0 0 0 2 8 7 0 0 0 9 5 一维数组SA13*5-2作为数组A的存储结构: SA=(4 3 5 2 2 1 0 4 2 8 7 9 5) 如: a5,4 = 9 k = 3*(5-1) + 4-5+1 = 12 故:sa12 = 9,5.3.2 稀疏矩阵 通常稀疏因子0.05时称为稀疏矩阵.,例5.6 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 M= -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7 0 18 0 0 0 0 0 0 0 0 0 0 0 15 0 0 -7 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 M: mu x nu (6x7) T: nu x mu (7x6) M是T的转置,稀疏矩阵的存储结构 一. 三元组顺序表,M: i j e T: i j e 1 2 12 1 3 -3 1 3 9 1 6 15 3 1 -3 2 1 12 3 6 14 2 5 18 4 3 24 3 1 9 5 2 18 3 4 24 6 1 15 4 6 -7 6 4 -7 6 3 14,三元组顺序表结构定义,#define MAXSIZE 12500 typedef struct int i, j; Elemtype e; Triple; typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; TSMatrix; TSMatrix M, T;,M.datap .i .j .e,0 1 2 ,maxsize,求稀疏矩阵M的转置矩阵T TSMatrix M,T;,0 1 2 3 4 5 6 7 8,0 1 2 3 4 5 6 7 8,M.datap .i .j .e,T.dataq .i .j .e,求稀疏矩阵M的转置矩阵T,Status TransposeSMatrix(TSMatrix M,TSMatrix / TransposeSMatrix,求稀疏矩阵转置的算法复杂度,其算法复杂度是 O(nu*tu) 而一般矩阵的转置算法的复杂度是O(mu*nu): for ( col =1; col= nu; +col) for ( row =1; row= mu; +row) Tcolrow = Mrowcol; 所以,当tu = mu*nu 时, 算法复杂度是 O(nu*nu*mu) 当tu mu*nu 时,才适用,求稀疏矩阵M的转置矩阵T的 快速方法,为了减少算法复杂度,增加两个向量 num 和 cpot: numcol: M中第 col 列中非零元素的个数; cpotcol:M中第col列中的第一个非零元素在T.data中的位置; 有: cpot1 = 1; cpotcol = cpotcol-1+numcol-1 2= col=m.nu,例5.6 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 M= -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7 0 18 0 0 0 0 0 0 0 0 0 0 0 15 0 0 -7 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 例5.6的向量 num 和 cpot: col 1 2 3 4 5 6 7 num 2 2 2 1 0 1 0 cpot 1 3 5 7 8 8 9,Status FastTransposeSMatrix(TSMatrix M,TSMatrix / FastTransposeSMatrix,col 1 2 3 4 5 6 7 num 2 2 2 1 0 1 0 cpot 1 3 5 7 8 8 9,求稀疏矩阵转置的快速算法的 算法复杂度,其算法复杂度是 O(nu+tu) 当tu = mu*nu 时,算法复杂度是 O(nu*mu) 当tu mu*nu 时, 时间复杂度将小得多,#define MAXRC 100 typedef struct int i, j; Elemtype e; Triple; typedef struct Triple dataMAXSIZE+1; int rposMAXRC+ 1; int mu,nu,tu; RLSMatrix;,二.行逻辑链接的顺序表 指出每一行的第一个非零元素在三元组中的位置,M.rposrow,例5.7 矩阵的乘法 Q = M x N M: m1 x n1 N: m2 x n2 当n1 = m2时,求两个稀疏矩阵的乘积的算法,Q初始化; if (M和N均是非零矩阵) for(arow = 1; arow=M.mu;+arow) ctemp = 0; 计算Q中第arow行的积并存入ctemp中; 将ctemp中非零元压缩存储到Q.data; ,Status MultiSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix ,时间复杂度: ctemp 的时间复杂度是 O(M.mu X N.nu);,求Q所有非零元的时间复杂度是 O(M.tu X N.tu/N.mu); 压缩存储的时间复杂度是O(M.tu X N.tu/N.mu); 时间复杂度是: O(M.mu X N.nu + M.tu X N.tu/N.mu); for( i = 1; i=m1; +i) for( j = 1; j=n2; +j) Qij = 0; for( k = 1; k=n1; +k) Qij += Mik * Nkj; / 算法复杂度是 O(m1*n1*n2),三、 稀疏矩阵的链式存储结构：十字链表,优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。,在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有两个域：,right： 用于链接同一行中的下一个非零元素； down：用以链接同一列中的下一个非零元素。,十字链表中结点的结构示意图：,十字链表的结构类型说明如下：,typedef struct OLNode int row, col; /*非零元素的行和列下标*/ ElementType value; struct OLNode * right,*down; /*非零元素所在行表列表的后继链域*/ OLNode; *OLink; typedef struct OLink * row_head, *col_head; /*行、列链表的头指针向量*/ int m, n, len; /*稀疏矩阵的行数、列数、非零元素的个数*/ CrossList;,建立稀疏矩阵的十字链表算法：,CreateCrossList (CrossList * M) /*采用十字链表存储结构，创建稀疏矩阵M*/ if(M!=NULL) free(M); scanf( /*生成结点*/,if(M-row_headi=NULL) M-row_headi=p; else /*寻找行表中的插入位置*/ for(q=M-row_headi; q-right /*完成插入*/ ,5.4 广义表,广义表也是线性表的一种推广。广义表也是n个数据元素（d1，d2，d3，dn）的有限序列，但不同的是，广义表中的di既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，dn）。GL是广义表的名字，通常用大写字母表示。n是广义表的长度。若 di是一个广义表，则称di是广义表GL的子表。 在GL中， d1是GL的表头，其余部分组成的表（d2，d3，dn）称为GL的表尾。由此可见，广义表的定义是递归定义的。,l D=（） 空表；其长度为零。,lA=(a，(b，c)表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。,lB=（A，A，D）长度为3的广义表，其前两个元素为表A，第三个元素为空表D。,lC=（a，C） 长度为2递归定义的广义表，C相当于无穷表C=（a，（a，（a，（）。,例如：,head(A)=a 表A的表头是a。 tail(A)=(b，c) 表A的表尾是(b，c) ，广义表的表尾一定是一个表。,从上面的例子可以看出：,（1）广义表的元素可以是子表，而子表还可以是子表，由此，广义