《ch_5_数组和广义表(数据结构)》由会员分享，可在线阅读，更多相关《ch_5_数组和广义表(数据结构)（84页珍藏版）》请在金锄头文库上搜索。
1、1,第5章 数组和广义表,线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。 数组和广义表可以看成是线性表的扩展：表中的数据元素本身也是一个数据结构。,5.1 数组的定义,5.3 矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的存储结构,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 数组的定义和特点 定义,数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值,5.1 数组的类型定义,5,ADT Array 数据对象： Daj1,j2, .,ji,jn| ji
2、 =0,.,bi -1, i=1,2,n 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array,基本操作:,6,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,7,基本操作：,InitArray(&A, n, bound1, ., boundn),DestroyArray(&A),Value(A, &e, index1, .,
3、 indexn),Assign(&A, e, index1, ., indexn),8,InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。,9,DestroyArray(&A) 操作结果：销毁数组A。,10,Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。,11,Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组
4、，e为元素变量， 随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。,12,5.2 数组的顺序表示和实现,类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。,有两种顺序映象的方式: 1)以行序为主序(低下标优先)； 2)以列序为主序(高下标优先)。,13,例如：,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2
5、,a1,0,a1,1,a1,2,L,L,14,练习,二维数组A1218采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A97的地址为（ ）,LOC(i,j) = LOC(0,0) + (b1ji)L,429,15,例: 设一本书有b1页,每页有b2行,b3列,现在统计,在j1页,j2行,j3列的字符之前一共有多少字符.,j1*b2*b3+j2*b3+j3,0 jk bk -1,三维数组,16,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) +(j1*b2*bn + j2*b3*bn + + jn-1*bn +jn)*L,推广到一般情况，
6、可得到 n 维数组数据元素存储位置的映象关系,17,称为 n 维数组的映象函数。数组元素 的存储位置是其下标的线性函数。,其中 cn = L，ci-1 = bi ci , 1 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,压缩存储：为多个值相同的元素只分配一个存储空间；对零元不分配空间。 目的：节省存储空间。,基本概念,特殊矩阵：值相同的元素或零元在矩阵中的分布有一定的规律。(对称矩阵，三角矩阵，对角矩阵). 反之,称为稀疏矩阵.,5.3 矩阵的压缩存储,5.3.1 特殊矩阵,对称矩阵,对角矩阵,三角矩阵,n阶对称矩阵： aij=
7、aji 1i,j n,对称矩阵的压缩存储,21,问题：,假设以一维数组san(n+1)/2作为n阶对称阵的存储结构，则sak和矩阵元素aij存在怎样的对应关系？,下三角 上三角,2.以列序为主序存储上三角中的元,1.以行序为主序存储下三角中的元,Loc(aij)=Loc(a11)+ +(j-1) 设L为1,i(i-1),2,下（上）三角矩阵： 矩阵的上（下）三角中的元均为常数c或零的n阶矩阵。,前面i-1行元素个数,第i行元素个数,对角矩阵,假设 m 行 n 列的矩阵含 t 个非零元素，令 则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,稀疏矩阵：非零元较零元少,且分布没有一定规律
8、,5.3.2 稀疏矩阵,26,以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零。,27,1) 尽可能少存或不存零值元素；,解决问题的原则:,2) 尽可能减少没有实际意义的运算；,3) 操作方便。 即： 能尽可能快地找到与 下标值(i，j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元。,M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7）唯一确定,稀疏
9、矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,29,知识回顾 2011-10-11 （10）,数组的定义 特殊矩阵的压缩 稀疏矩阵的压缩,30,稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑链接的顺序表,三、 十字链表,31,#define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,一、三元组顺序表,typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; / 矩阵行数、列数和非
10、零元个数 TSMatrix; / 稀疏矩阵类型,32,稀疏矩阵的压缩存储方法 三元组顺序表,6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,m.data0 分别存放 矩阵行数，列数和非零元个数,33,如何求转置矩阵？,a b,34,用常规的二维数组表示时的算法,其时间复杂度为: O(munu),for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,35,用“三元组”表示时如何实现？,矩阵的行列值互换 下标i，j互换 重排次序,36,按
11、照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。 即：按照矩阵a的列序来进行转置。,方法1：,1 2 14,1 5 -5,2 2 -7,3 1 36,3 4 28,2 1 14,5 1 -5,2 2 -7,1 3 36,4 3 28,方法1：,Status TransposeSMatrix(TSMatrix M, TSMatrix /TransposeSMatrix,39,算法分析：,时间复杂度：O(nu.tu) 一般算法复杂度：O(mu.nu) 若tu和mu.nu是同一数量级，则O(mu.nu2) 因此，此算法仅适用于tumu.nu,如果能预先确定矩阵M中每一列（即
12、T中每一行）的第一个非零元在三元组中的位置，则转置时，便可直接放到恰当位置。,方法2：,转置前，应先求得M的每一列中非零元个数，进而求得每一列第一个非零元在转置阵T.data中应有的位置。,cpot1 = 1 cpotcol = cpotcol-1 + numcol-1,附设两个向量:num和cpot. numcol：表示矩阵M中第col列中非零元的个数 cpotcol：指示M中第col列的第一个非零元在T.data中的恰当位置,显然有,42,首先应该确定每一列的第一个非零元在三元组中的位置。,cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = c
13、potcol-1 + numcol-1;,1 2 14,1 5 -5,2 2 -7,3 1 36,3 4 28,2 1 14,5 1 -5,2 2 -7,1 3 36,4 3 28,矩阵的向量cpot的值,Status FastTransposeSMatrix(TSMatrix M, TSMatrix / 求第col列第一个非零元在三元组中的序号,cpot1 = 1 cpotcol = cpotcol-1 + numcol-1,for (p=1; p=M.tu; +p) col = M.datap.j; /对每个非零元，求他们的列坐标j q = cpotcol; /求第col列第一个非零元在三
14、元组中的序号 T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; /三元组中的i, j互换 T.dataq.e = M.datap.e; /非零元赋值 +cpotcol;/求同一列下一个非零元的序号，更新cpot /for, / if return OK; /FastTransposeSMatrix,46,分析算法FastTransposeSMatrix的时间复杂度：,时间复杂度为: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +
15、col) for (p=1; p=M.tu; +p) ,非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行中的非零元，则需从头开始进行查找。,三元组顺序表(有序的双下标法)特点:,typedef struct Triple dataMAXSIZE + 1; /非零元三元组表 int rposMAXRC + 1; /各行第一个非零元的位置表 int mu, nu, tu; /矩阵的行数、列数、非零元个数 RLSMatrix; / 行逻辑链接的顺序表类型,为了便于随机存取任意一行的非零元，需知道每一行的第一个非零元在三元组表中的位置，修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos。,二、行逻辑链接的顺序表 （带行链接信息的三元组表）,49,例如：给定一组下标，求矩阵的元素值,ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r /
