《数组和广义表副本》由会员分享，可在线阅读，更多相关《数组和广义表副本（63页珍藏版）》请在金锄头文库上搜索。
1、数据结构 Data Structures 长江大学计算机科学学院第五章 数组和广义表F本章内容 5.1 数组的定义 5.2 数组的顺序表示 5.3 矩阵的压缩存储5.3.1 特殊矩阵5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构数据结构 Data Structures 长江大学计算机科学学院5.1数组的定义v数组是我们很熟悉的一种数据结构，它可以看 作线性表的推广。数组作为一种数据结构其特 点是结构中的元素本身可以是具有某种结构的 数据，但属于同一数据类型，比如：一维数组 可以看作一个线性表，二维数组可以看作“数 据元素是一维数组”的一维数组，三维数组可 以看作“数据元素
2、是二维数组”的一维数组， 依此类推。 v由于数组中各元素具有统一的类型，并且数组 元素的下标一般具有固定的上界和下界，因此 ，数组的处理比其它复杂的结构更为简单。多 维数组是一维数组的推广。2数据结构 Data Structures 长江大学计算机科学学院v例如，二维数组A： 5.1数组的定义(续)Amn=a11 a12 a1na21 a22 a2n am1 am2 amnv二维数组A可以看成是由m个行向量组成的向量 ，也可以看成是n个列向量组成的向量。v数组一旦被定义，它的维数和维界就不再改变 。因此，除了结构的初始化和销毁之外，数组 只有存取元素和修改元素值的操作。 3数据结构 Data
3、Structures 长江大学计算机科学学院v由于计算机的内存结构是一维的，因此用一维 内存来表示多维数组，就必须按某种次序将数 组元素排成一列序列，然后将这个线性序列存 放在存储器中。v数组一旦建立，结构中的元素个数和元素间的 关系就不再发生变化。因此，一般采用顺序存 储的方法来表示数组。5.2 数组的顺序表示4数据结构 Data Structures 长江大学计算机科学学院v行优先顺序或以行为主序存储方式：将数组元素 按行排列，第i+1个行向量紧接在第i个行向量后 面。以二维数组为例，按行优先顺序存储的线性 序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn
4、v在PASCAL、C等语言中，数组就是按行优先顺序存 储的。5.2 数组的顺序表示(续)Amn=a11 a12 a1na21 a22 a2n am1 am2 amnvLOC(aij)=LOC(a11)+(i-1)*n+j-1*d5数据结构 Data Structures 长江大学计算机科学学院v列优先顺序或以列为主序存储方式：将数组元素按 列向量排列，第j+1个列向量紧接在第j个列向量之 后，A的m*n个元素按列优先顺序存储的线性序列为 ：a11,a21,am1,a12,a22,am2,an1,an2,anmv在FORTRAN语言中，数组按列优先顺序存储。5.2 数组的顺序表示(续)Amn=a
5、11 a12 a1na21 a22 a2n am1 am2 amnvLOC(aij)=LOC(a11)+(j-1)*m+i-1*d6数据结构 Data Structures 长江大学计算机科学学院v行优先顺序先排最右的下标，从右到左 ，最后排最左下标。v列优先顺序先排最左下标，从右向左， 最后排最右下标。v例如：三维数组Am*n*p5.2 数组的顺序表示(续)7数据结构 Data Structures 长江大学计算机科学学院v只要知道开始结点的存放地址（即基地址）、维 数和每维的上、下界，以及每个数组元素所占用 的单元数，就可以将数组元素的存放地址表示为 其下标的线性函数。因此，数组中的任一元
6、素可 以在相同的时间内存取，即顺序存储的数组是一 个随机存取结构。数组存储的特点8数据结构 Data Structures 长江大学计算机科学学院v压缩存储：为多个值相同的非零元素只分配 一个存储空间；对零元素不分配空间。5.3 矩阵的压缩存储9数据结构 Data Structures 长江大学计算机科学学院v特殊矩阵：非零元素按照一定的规律分布。5.3.1特殊矩阵的压缩存储a1,1 a1,2 a1,na2,1 a2,2 a2,n ai,j an,1 an,2 an,naij=aji1 2 3 42 1 3 43 3 1 44 4 4 1对称矩阵v常见的特殊矩阵有对称矩阵、三角矩阵、对 角矩阵
7、等。对称矩阵：元素的值按照主对角线对称10数据结构 Data Structures 长江大学计算机科学学院5.3.1(续)对称矩阵的压缩存储对称矩阵1 2 3 42 1 3 43 3 1 44 4 4 11 2 3 42 1 3 4 3 3 1 4 4 4 4 11213314441数组B12345678910下标kv例如：一个4*4的对称矩阵。11数据结构 Data Structures 长江大学计算机科学学院5.3.1(续)对称矩阵的压缩存储对称矩阵数组Bai,jan,na1,1a2,1a2,2a3,11234km下标a1,1 a1,2 a1,na2,1 a2,2 a2,n ai,j an
8、,1 an,2 an,na1,1a2,1 a2,2 ai,j an,1 an,2 an,nk = ? m = ?v推广至一般情况，n*n的对称矩阵12数据结构 Data Structures 长江大学计算机科学学院5.3.1(续)三角矩阵的压缩存储1 0 0 02 1 0 03 3 1 04 4 4 11 2 3 40 1 3 40 0 1 40 0 0 1(a) 下三角矩阵(a) 上三角矩阵v三角矩阵：上(下)三角矩阵是指矩阵的下（上） 三角（不包括对角线）中的元素均为常数或零的n 阶矩阵，即非零元素的分布在矩阵中呈现为三角 形。 v例如：一个4*4的三角矩阵。13数据结构 Data Str
9、uctures 长江大学计算机科学学院5.3.1(续)三角矩阵的压缩存储1 8 8 82 1 8 83 3 1 84 4 4 11 2 3 49 1 3 49 9 1 49 9 9 1(c) 下三角矩阵(d) 上三角矩阵v例如：一个4*4的三角矩阵。14数据结构 Data Structures 长江大学计算机科学学院5.3.1(续)三角矩阵的压缩存储a0,0 a0,1 a0,2 a0,n-2 a0, n-1 a1,1 a1,2 a1,n-2 a1, n-1 ai,i ai,j ai, n-1 an-1, n-1 0a0,0 a0,1 a0,2 a0,3ai,jan-1, n-1b1 b2 b3
10、 b4bkbmk = ? m = ?v推广至一般情况，n*n的三角矩阵以行为主 序压缩存储15数据结构 Data Structures 长江大学计算机科学学院5.3.1(续)三角矩阵的压缩存储a0,0 a0,1 a0,2 a0,n-2 a0, n-1 a1,1 a1,2 a1,n-2 a1, n-1 ai,i ai,j ai, n-1 an-1, n-1 0a0,0 a0,1 a1,1 a0,2ai,jan-1, n-1b1 b2 b3 b4bkbmk = ? m = ?a1,2b5 a2,2b6v推广至一般情况，n*n的三角矩阵以列为主 序压缩存储16数据结构 Data Structures
11、 长江大学计算机科学学院5.3.1(续)三对角矩阵的压缩存储a0,0 a0,1 a1,0 a1,1 a1,2a2,1 a2,2 a2,3. ai,j . an-2,n-3 an-2,n-2 an-2,n-1an-1,n-2 an-1, n-1a0,0a0,1a1,0ai,j数组B 12k k+1m下标0.k = ? m = ?v对角矩阵是指所有的非零元素都集中在以主 对角线为中心的带状区域中。17数据结构 Data Structures 长江大学计算机科学学院v上述各种特殊矩阵，其非零元素的分布都是 有规律的，因此总能找到一种方法将它们压 缩存储到一维数组中，并且一般都能找到矩 阵中的元素与该
12、一维数组元素的对应关系， 通过这个关系，仍能对矩阵的元素进行随机 存取。5.3.1(续)特殊矩阵的压缩存储Example 18数据结构 Data Structures 长江大学计算机科学学院v什么是稀疏矩阵？简单说，设矩阵A中有s个 非零元素，若s远远小于矩阵元素的总数（ 即smn），则称A为稀疏矩阵。v设在矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认 为e0.05时称之为稀疏矩阵。5.3.2稀疏矩阵19数据结构 Data Structures 长江大学计算机科学学院5.3.2稀疏矩阵的压缩存储v在存储稀疏矩阵时，由于非零元素的分布一般 是没有规律的，因此在存
13、储非零元素的同时，还 必须同时记下它所在的行和列的位置（i,j)。反 之，一个三元组(i,j,aij)惟一确定了矩阵A的一 个非零元。因此，稀疏矩阵可由表示非零元的三 元组及其行列数唯一确定。20数据结构 Data Structures 长江大学计算机科学学院( (1,2,12), (1,3,9), (3,1,-3), (3,6,14),(4,3,24), (5,2,18), (6,1,15), (6,4,-7) )5.3.2稀疏矩阵的压缩存储M=0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0 0 7 0 0 0v例如，一个6*7的稀疏矩阵v稀疏矩阵中的非零元素21数据结构 Data Structures 长江大学计算机科学学院假设以顺序存储结构来表示三元组表，则可得到 稀疏矩阵的一种压缩存储方法三元组顺序表 。#define maxsize 10000typedef int datatype;typedef structint i,j;datatype v;triple; /* 三元组*/5.3
