《04 数组和广义表》由会员分享，可在线阅读，更多相关《04 数组和广义表（27页珍藏版）》请在金锄头文库上搜索。
1、数组由类型相同的数据元素构成的有序集合数组 几乎所有的高级程序设计语言中都将数组类型作为固有类型，在此我们以抽象数据类型的形式来讨论数组的定义和实现数组的ADT定义ADT Array数据对象：ji= 0,bi-1, i=1,2,nD = aj1j2jn| n称为数组的维数, bi是数组第i维的长度,ji是数组元素的第i维下标，aj1j2jn ElemSetR = R1, R2, , Rn /每个元素受到n个关系的约束Ri = | 0 jkbk-1, 1 k n 且k i0 ji bi-2,aj1jijn, aj1,ji+1jnD, i = 2,nP:InitArray(&A, n, bound
2、1, , boundn)DestoryArray(&A)Value(A, &e, index1, , indexn) /取出元素值Assign(&A, e, index1, , indexn) /给元素赋值ADT Array 数组的ADT定义 n维数组中含有 个数据元素，每个元素受到n个线形关系的约束，对应于一组下标(j1, , jn) n维数组可以看成是线性表的推广 数组一旦被定义，它的维数和维界就不再改变 数组结构操作 初始化、销毁、存取元素、修改元素 数组多用于静态数据处理，一般不作插入和删除操作bini1数组的顺序表示 数组采用顺序存储方式来实现 n维数组的数据元素的存储问题 必须约定
3、存放次序 因为存储单元是一维的，而数组是多维的 存储方案 以行序为主序，如C, J ava, Pascal, Basic等语言采用 以列序为主序，如Fortran语言采用 一旦定义了维数和各维长度，便可为数组分配存储空间 只要给出一组下标便可求得相应元素的存储位置，属于随机存储结构数据元素的存储问题 以一维数组为例如int Ab1, 共占用b1个整型存储单元给定下标值i，求对应元素的存储位置 Loc(i) = Loc(0) + i * L数组基址元素所占存储单元大小ALoc(0)01ib1-1LA0A1AiAb1-1数据元素的存储问题 以二维数组为例 如int Am, n, 共占用m*n个整型
4、存储单元 如行序为主序的存储方式(图a) 给定下标值i, j，求对应元素的存储位置Loc(i, j) = Loc(0, 0) + (n * i + j) * LALoc(0,0)A0,0A0,1A0,n-1A1,0A1,1A1,n-1Am-1,0Am-1,1Am-1, n-1数据元素的存储问题 以n维数组为例 如int Ab1,b2 ,bn,共占用b1*b2 *bn个整型存储单元 行序为主序的存储方式 给定下标值j1, j2, jn , 求对应元素的存储位置Loc(j1, j2, jn) = Loc(0, 0,0) + L *(b2* .*bn* j1 +b3* *bn* j2 + bn* j
5、n-1 +jn) 练习 用以行序为主序和以列序为主序分别写出三维数组A234的元素在内存中的存储次序练习：设线性表的每个元素占8个存储单元，第一个单元的存储地址为100，则第六个元素占用的最后一个存储单元的地址为 。(A)139 (B)140 (C)147 (D)148练习：设有二维数组A0.90.19，其每个元素占两个字节，第一个元素的存储地址为100，若按行优选顺序存储，则元素A6,6的存储地址为 ，若按列优选顺序存储，地址为256的存储单元所对应的元素为 。将一个A1.201.20 (注：下标均从1开始计)的矩阵，按行序为主存放，每个元素占4个存储单元，并且A1,2的存储地址是1004，
6、则A20,2的地址是（ ）C352(100+(6*20+6)*2)A8,72524 矩阵 通常使用二维数组来存储矩阵元素 矩阵的常见操作转置、相乘等void TransposeMatrix(int T, int M, mu, nu) /矩阵转置for (col = 1; col = j k =j(j-1)/2 + i 1 当i j a11a12 a1na21a22 a2n an1an2 annAa11a12a1na21a22aijan1an2ann0(n-1)*(n-1)saa11a21a31a32a33aijanna220n*(n-1)/2 -1k(i-1)*n+j特殊矩阵的压缩存储 如3*
7、3对称矩阵未压缩时，用二维数组存放，占用9 个单元压缩存放时，用一维数组存放，只需6 个单元如a32存放在sa4中a11a12a13a21a22a23a31a32 a33a11a21a31a32a33a2205saaij= aji特殊矩阵的压缩存储 三角矩阵下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵 三角矩阵的压缩存储只存储下(上)三角中的元素，再加一个存储常数c的空间即可特殊矩阵的压缩存储 对角矩阵所有非零元素都集中在以主对角线为中心的带状区域中 对角矩阵的压缩存储可按照某原则(或以行为主，或以对角线的顺序)将其压缩到一维数组中特殊矩阵的压缩存储 小
8、结特殊矩阵(如对称矩阵、三角矩阵、对角矩阵等)中，非零元素的分布有明显的规律，因此我们可以将其压缩存储到一维数组中，并找到每个非零元素在一维数组中的对应关系稀疏矩阵的压缩存储 稀疏矩阵 值相同的元素或零元素在矩阵中的分布无规律，且 非零元素个数/矩阵所有元素个数= 0.05 原理 只需存储矩阵中的非零元素所在的行号、列号和值 方法 三元组顺序表(*) 行逻辑联接顺序表 十字链表稀疏矩阵的压缩存储 三元组顺序表以顺序结构存储三元组表#define MAXSIZE 12500 /假设非零元素个数的最大值typedef structint i, j; /行号,列号ElemType e;/元素值Tri
9、ple; /三元组typedef structTriple dataMAXSIZE + 1; /非零元素三元组表，data0未用int mu, nu, tu;/行数，列数，非零元素个数TSMatrix; /三元组顺序表TSMatrix M; /矩阵M稀疏矩阵的压缩存储 如稀疏矩阵 采用三元组法压缩存储稀疏矩阵 按行号排序 不支持随机存取，对某行某非零元素访问时，可能需要扫描整个顺序表M =0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 01 2 121 3 93 1 -33
10、6 144 3 245 2 186 1 156 4 -7i j eM.data:M.mu = 6M.nu = 7M.tu = 8 采用三元组顺序表存储的矩阵的转置算法Status TransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;if (T.tu) /有非零元素，转置q = 1; /非零元素计数器for (col = 1; col = M.mu; +col) /按列for (p = 1; p = M.tu; +p) /在三元组中找if (M.datap.j = col) T.dataq
11、.i = M.datap.j;T.dataq.j = M.datap.i;T.dataq.e = M.datap.e;+q;return OK;1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j eM.data:M.mu = 6M.nu = 7M.tu = 8转置1 3 -31 6 152 1 123 1 93 4 244 6 -76 3 142 5 18i j eT.data:T.mu = 6T.nu = 7T.tu = 8思考 设有三维数组A1.21.23.4，请分别按行序和列序列出各元素。 对上三角矩阵，若采用以行序为主序的原则用一维数组
12、顺序存储其所有非零元素，试找出每个非零元素aij在一维数组中的对应关系。 若在m*n的矩阵中存在一个元素Ai，并满足：Ai,j是第i 行元素中的最小值，且是第j 列元素中的最大值，则称矩阵A有鞍点。试写一个算法，找出矩阵A的一个鞍点，若不存在鞍点，则返回提示信息。广义表 基本概念 广义表是线性表的推广，有层次特性和递归特性 广义表的形式化表示LS = (a1, a2, ai, , an), LS为表名，n为广义表的长度，ai可以是单个元素(称为原子)，也可以是广义表(称为子表) 当广义表非空时，称第一个元素a1为表头(Head)，其余元素组成的表(a2, an)为表尾(Tail) 。任何一个非
13、空广义表均可分解成表头和表尾。 广义表的深度为广义表中括弧的最大嵌套层数，原子的深度为0，空表的深度为1，其他均为子表最大深度加1 广义表的常见操作：求长度，求深度，求表头，求表尾等 广义表广泛应用于人工智能等领域广义表操作举例A = ( ) 空表，长度为0，深度为1B = (e) 长度为1 ，深度为1C = (a, (b, c, d) 长度为2 ，深度为2D = (A, B, C)长度为3，深度为3E = (a, E)，递归表，长度为2，深度为无穷F = ( ), (e), (a, (b,c,d)长度为3GetHead(B) = e GetTail(B) = ( )GetHead(D) = A GetTail(D) = (B, C)GetHead(E) = a GetTail(E) = EGetHead(GetTail(GetTail(F) = a典型运算：如广义表通常采用链式存储！
