数据结构课程的内 容1.5 数组1.5.1数组的定义及运算数组(array)是每一个程序设计语言中都具有的一种常 用数据类型，其中的每个数组元素必须具有相同的 数据类型。在ANSI C语言中，数组是作为一种预 定义数据类型由用户直接进行引用的。数组是长度固定的线性表数组是长度固定的线性表。所以，数组没有插入和删 除操作，只有存储和查询操作。 每一个数组元素都由一个值和一组下标组成。数组的 下标代表元素之间的关系。对每一组有定义的下标 ，都有一个与之相对应的值。 数组结构的特征：下标与值一一对应。注意：注意： 本章所讨论的数组与高级语言中的数组有所区别：高 级语言中的数组是顺序结构（计算机）；而本章的数组既可以 是顺序的，也可以是链式结构（数学），用户可根据需要选择 。讨论：“数组的处理比其它复杂的结构要简 单”，对吗？答：对的。因为： 数组中各元素具有统一的类型； 数组元素的下标一般具有固定的上界和 下界，即数组一旦被定义，它的维数和 维界就不再改变。 数组的基本操作比较简单，除了结构的 初始化和销毁之外，只有存取元素和修 改元素值的操作。二维数组的 特点：一维数组的特点：1个下标，ai 是ai+1的直接前驱2个下标，每个元素ai,j受到两个关 系（行关系和列关系）的约束：一个mn的二维数组可 以看成是m行的一维数 组，或者n列的一维数组 。N维数组的特点：n个下标，每个元素受到n个关系 约束一个n维数组可以看成是由若干个n1维数组组成 的线性表。a11 a12 a1na21 a22 a2n am1 am2 amn Amn=数组的顺序存储表示和实现问题：计算机的存储结构是一维的，而数组一般是 多维的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一 列序列，然后将这个线性序列存入存储器中 。 例如：在二维数组中，我们既可以规定按行存储， 也可以规定按列存储。注意： 若规定好了次序，则数组中任意一个元素的存放 地址便有规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所 不同； C和PASCAL中一般采用行优先顺序；FORTRAN采用 列优先。补充：计算二维数组元素地址的通式补充：计算二维数组元素地址的通式 设一般的二维数组是Ac1.d1, c2.d2，这 里c1,c2不一定是0。（子矩阵）无论规定行优先或列优先，只要知道以下三要素便可随 时求出任一元素的地址（这样数组中的任一元素便可以 随机存取！）：二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*Lac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=单个元素 长度aij之前的 行数数组基址总列数，即 第2维长度aij本行前面的 元素个数开始结点的存放地址（即基地址） 维数和每维的上、下界； 每个数组元素所占用的单元数则行优先存储时的地址公式为： LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L顺序存储方式：按低地址优先（或高地址优先）顺 序存入一维数组。行指针向量a11a12a1nam1am2amn补充： 链式存储方式：用带行指针向量的单链表来表示。（难点是多维数组与一维数组的地址映射关系）1.5.3 矩阵的压缩存 储讨论： 1. 什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存 储空间，且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵， 稀疏矩阵等。 4. 什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）重点介绍稀疏矩阵的压缩和相应的操作。1.5.3稀疏矩阵的存储表示稀疏矩阵的概念稀疏矩阵的概念 绝大多数元素为零，只有极少数非零元素的矩阵，这 种矩阵称为稀疏矩阵(sparse matrix)。2.2.稀疏矩阵的压缩存储稀疏矩阵的压缩存储问题： 如果只存储稀疏矩阵中的非零元素，那这些元素 的位置信息该如何表示？解决思路： 对每个非零元素增开若干存储单元，例如存放其 所在的行号和列号，便可准确反映该元素所在位 置。实现方法： 将每个非零元素用一个三元组（i，j，aij）来表 示，则每个稀疏矩阵可用一个三元组表来表示。稀疏矩阵的三元组表示法只存储稀疏矩阵中的非零元素，而不存储全部的零元素 。由于矩阵中的每个元素都是可以由所在行、所在列 和元素值惟一地确定，所以使用如下的三元组(triple):(行号域i ，列号域j，值域value)说明： 使用三元组(triple)表示稀疏矩阵中的非零元素。 行号域i:用于表示非零元素的行号； 列号域j：用于表示非零元素的列号。 值域Value：用于表示非零元素的值；对任何一个稀疏矩阵而言，可以将全部的非零元素使用三元组形式 进行表示，并按某种次序(如行主序或列主序）排列起来，再加 上一个表示该矩阵行数m、矩阵列数n和非零元素个数t的三元组 (m，n，t，)，就可以得到一个能惟一地确定稀疏矩阵的三元组 表。如，图1 .21所示的稀疏矩阵可表示成如表114和表1.15所 示的两个三元组表示。三元组顺序表用顺序存储结构表示的三元组表称之为三元组顺序表。这样可以直 观地将三元表作为一个具有三列的二维数组，也可以将三元组顺 序表看成是以三元组为数组元素的一维数组。不论是按三列的二 维数组还是按一维的三元组数组来表示，三元组的实质是致的 。图1.21中的稀疏矩阵，可以使用一个具有三列的二维数组(行 主序)来表示。一般地，一个mn，有t个非零元素的稀疏矩阵可用一个 t+1大小的一维数组表示。该数组的每一元素是一个三 元组。叫：三元组数组三元组数组。三元组数组中数组元素的定义：typedef struct int col;intcolumn;datatypevalue;TRIPLE; 例 1 ：三元素组表中的每个结点对应于稀疏矩 阵的一个非零元素，它包含有三个数据项，分 别表示该元素的 、 和 。 行下标列下标元素值例2：写出右图所示稀疏 矩阵的压缩存储形式。( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)，(4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7)法1：用线性表表示：0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0法2：用三元组矩阵表示 ：0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0 121213931-3351443245218611564-7注意：为更可靠 描述，通常再加 一行“总体”信 息：即总行数、 总列数、非零元 素总个数668ijvalue稀疏矩阵压缩存储的缺点：将失去随机存取功能！ 访问任何一个元素都要从头开始！如何解决？0 01 12 23 34 45 56 67 78 8法三：用带辅助向量的三元组表 示。方法： 增加2个辅助向量： 记录每行非0元素个数，用NUM（ i）表示； 记录稀疏矩阵中每行第一个非0元 素在三元组中的行号，用POS（i ）表示。7653211202NUM( i)6543POS( i )21i10 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0-7461516182524341453-3139311221866vji0 123456783用途：通过三元组高效访问稀疏矩 阵中任一非零元素。规律：POS(1)1POS(i)POS(i-1)+NUM(i-1)如何高效 ？3.3.稀疏矩阵的操稀疏矩阵的操 作作 0 12 9 0 0 0 0 0 0 0 0 0 -3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 00 0 3 0 0 15 12 0 0 0 18 09 0 0 24 0 0 0 0 0 0 0 -7 0 0 14 0 0 0 0 0 0 0 0 0 (1, 2, 12) (1, 3, 9 ) (3, 1, -3) (3, 5, 14) (4, 3, 24) (5, 2, 18) (6, 1, 15) (6, 4, -7)(1, 3, -3) (1, 6, 15) (2, 1, 12) (2, 5, 18) (3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)三 元 组 表 a.data三 元 组 表 b.data转置后MT（以转置运算为例）目的：答：肯定不正确！ 除了： （1）每个元素的行下标和列下标互换（即三元 组中的i和j互换）； 还应该：（2）T的总行数mu和总列数nu与M值不同（互换 ）；（3）重排三元组内元素顺序，使转置后的三元 组也按行（或列）为主序有规律的排列 。上述（1）和（2）容易实现，难点在（3）。若采用三元组压缩技术存储稀疏矩阵，只要把每 个元素的行下标和列下标互换，就完成了对该矩阵的 转置运算，这种说法正确吗？ 有两种实现方法压缩转置(压缩)快速转置提问：方法1：压缩转 置思路：反复扫描a.data中的列序，从小到大依次 进行转置。三 元 组 表 a.data三 元 组 表 b.data(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)(1, 2, 12) (1, 3, 9 ) (3, 1, -3) (3, 5, 14) (4, 3, 24) (5, 2, 18) (6, 1, 15) (6, 4, -7)1122col q1 2 3 4p1 2 3 41、主要时间消耗在查找M.datap.j=col的元素，由两 重循环完成: for(col=1; col数据结构课程的内 容1.7 树我们前面介绍了线性表及其几种重要的特例，如栈、 队列、数组和串。一般而言，线性结构只能用来描 述数据元素间的线性顺序关系，很难反映元素之间 的层次(或分支）关系。在本节中，我们将