数据结构数组课件

1、1第5章 数组和广义表 数据结构（Java版）（第3版）第5章 数组和广义表5.1 数组5.2 特殊矩阵的压缩存储5.3 广义表数据结构（Java版）（第3版）目的和要求目的：线性结构到非线性结构的过渡，了解包含子结构的线性结构，理解链式存储结构在表达非线性数据结构中的作用。内容：使用二维数组表示矩阵及运算；三角矩阵、对称矩阵、稀疏矩阵等各种压缩存储方法实现矩阵运算；广义表的概念、双链表示和实现。要求：理解多维数组的存储结构；熟悉特殊矩阵的压缩存储方法；掌握稀疏矩阵三元组从顺序表、行的单链表到十字链表等到多种存储结构的演变过程；理解广义表的概念，熟悉广义表的存储结构。重点：讨论多种由顺序存储结

2、构和链式存储结构有机结合的存储结构，以矩阵为例，研究在相同的逻辑结构（矩阵）和操作要求（矩阵运算）情况下，根据各种矩阵的不同特性，采用多种存储结构实现矩阵运算。 难点：稀疏矩阵的多种存储和实现，广义表的存储和 实现。 实验：特殊矩阵和广义表的存储和运算。4一、教学内容：1、数组的定义和顺序存储方式；2、特殊矩阵的压缩存储；3、稀疏矩阵4、广义表的概念、表示及基本操作；广义表存储结构的实现。二、教学要求：1、了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；2、掌握对特殊矩阵进行压缩存储时的下标变换公式；3、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表

3、示稀疏矩阵时进行矩阵运算采用的处理方法；4、掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。 第5章 数组和广义表5第5章 数组和广义表目的：了解包含子结构的线性结构。要求：理解多维数组的存储结构，了解 特殊矩阵压缩存储，了解广义表。重点：难点：广义表的表示和实现。75.1 数组数组定义 数组分为一维数组和多维数组。数组的维数是由数组的下标的个数确定的：一个下标称为一维数组一个下标以上的数组称为多维数组从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列数组是二元组的一个集合85.1.1 一维数组一维数组是指下标的个

4、数只有一个的数组，有时称为向量，是最基本的数据类型在java 中需要事先声明，程序才能够在编译过程中预留内存空间声明的格式一般是： = new ；一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作10一维数组的存储由此可见，求数组中数据元素的地址，已知条件必须是知道第一个元素的地址，然后主要是找出该元素之前已经存储了多少个数据元素。在一维数组中，只要知道任何一个元素的地址即可求出其它元素的地址，但在多维数组中，已知条件必须是第一个数据元素地址。 5.1.1 一维数组115.1.1 一维数组数组分配内存空间的方式有2种静态数组：声明时给出数组元

5、素个数。当程序开始运行时，数组即获得系统分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。动态数组：声明时不指定数组长度。当程序运行中需要使用数组时，向系统申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系统归还所占用的内存空间。数组容量不够时，不能就地扩容。前面的做法是，申请一个更大容量的数组并进行数组元素复制。在Java中，数组元素既可以简单数据类型，也可以是引用类型。而且Java中的数组都是动态数组。125.1.2 多维数组多维数组多维数组是指下标的个数有两个以上，我们比较常用的是二维数组（因为三维以上的数组存储可以简化为二维数组的存储）。下面以二维数

6、组为例说明多维数组。二维数组的声明同一维数组。格式为： =new size1 size2;145.1.2 多维数组二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。因此，多维数组是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。155.1.2 多维数组对于数组与线性表的关系的两种不同理解，可图示如下，以三维数组array534为例：175.1.2

7、 多维数组由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。185.1.2 多维数组静态多维数组的顺序存储结构以二维数组的顺序存储为例说明，二维数组在顺序存储时一般有两种：行优先顺序：存储时先按行从小到大的顺序存储，在每一行中按列号从小到大存储。列优先顺序：存储时先按列从小到大的顺序存储，在每一列中按行号从小到大存储。以上的两种存储顺序中，第一个被存放的元素总是第

8、一行第一列的数据元素，所以该元素的地址是我们的已知条件。195.1.2 多维数组以二维数组arr23为例：205.1.2 多维数组215.1.2 多维数组以行序为主序（按行存储）的方法： “左”下标优先 以列序为主序（按列存储）的方法： “右”下标优先225.1.2 多维数组多维数组同样在二维数组中比较典型的是计算数据的存储位置。假设二维数组是m*n的二维数组（共有m行，每行有n列）。第一个数据元素的地址是loc(a11)，则第i行第j列的数据元素的地址的计算公式应为（按照行优先顺序存储）：loc(aij)=loc(a11)+（i-1）*n+j-1*c假设下标从1开始，我们需要计算出i行前面已

9、经存储了i-1行元素，每行有n个元素，共有（i-1）*n个数据元素，在第i行元素中，j列之前有j-1个数据元素，共有（i-1）*n+j-1个元素，每个元素占有c个存储单元，只要乘以c就可以了。其中loc(aij)表示第i 行第j列数据元素的内存的起始位置，loc(a11)表示第一个数据元素的内存位置，c表示每个数据元素所占有的内存空间的大小，如果下标从0开始，只要不用减1即可。 245.1.2 多维数组多维数组按此公式可以推广到多维数组的数据元素的地址计算（假设按照行优先顺序存储）： m行n 列纵标为k的三维数组，假设第一个元素的地址是loc(a111)，如果按行优先顺序存储，i行j列纵标为p

10、的数据元素的地址为（可以将它分解为二维数组）： loc(aijp)=loc(a111)+(i-1)*n*k+(j-1)*k +p-1*c;如果下标从0开始，只要不用减1即可。读者可以从以上的地址公式中可以找出一定的地址计算规律：多维数组中按行优先计算公式用一个下标乘以后面的最大值。 数据结构（Java版）（第3版）5.1 数组（1）静态顺序存储 行主序列主序 275.1.2 多维数组【例5.1】 矩阵类。本例声明Matrix类表示矩阵，成员table是一个元素类型为整型的二维数组。add()方法实现两个矩阵相加。28矩阵运算主要有矩阵加、矩阵减、矩阵乘、矩阵转置等。矩阵加（C=A+B）定义为

11、public class Matrix private int value;数据结构（Java版）（第3版）【例5.1】 矩阵类。设 ，有设 ，有设 ，有设 ，有305.2 特殊矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。315.2特殊矩阵的压缩存储但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造

12、成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。325.2特殊矩阵的压缩存储所谓矩阵的压缩存储，也就是在存储数组时，尽量减少存储空间，但是数组中的每个元素必须存储，所以在矩阵存储中，如果有规律可寻，只要存储其中一部分，而另一部分的存储地址可以通过相应的算法将它计算出来，从而占有比较少的存储空间达到存储整个矩阵的目的，称为矩阵的压缩存储。矩阵的压缩存储仅是针对特殊矩阵的；而对于没有规律可循的二维数组则不能够使用压缩存储。二维数组（矩阵）的压缩存储一般有三种，它们分别是对称矩阵、稀疏矩阵和三角矩阵。三种矩阵中以稀疏矩阵

13、比较常见。 33三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 5.2 矩阵的压缩存储 34 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到数组sa0.n(n+1

14、)/2中，其中c存放在数组的最后一个元素中5.2 矩阵的压缩存储 数据结构（Java版）（第3版）5.2.1 三角矩阵的压缩存储三角矩阵的压缩存储（1）线性压缩存储三角矩阵 36三角矩阵 （1）下三角矩阵下三角矩阵的压缩存放与对称矩阵用下三角形式存放类似，但必须多一个存储单元存放上三角部分元素，使用的存储单元数目为n(n+1)/2+1。故可以将nn的下三角矩阵压缩存放到只有n(n+1)/2+1个存储单元的数组中，假设仍按行优先存放，这时sk与aij的对应关系为： i(i+1)/2+j ij，i 、j0 k= n(n+1)/2 ij 5.2 矩阵的压缩存储 三角矩阵 数据结构（Java版）（第3

15、版）（2）使用三角形的二维数组压缩存储三角矩阵 405.2 矩阵的压缩存储 对称矩阵若n 阶矩阵A中的元素满足以下条件： aij=aji i1，j1 则称为n阶对称矩阵。对于对称矩阵，如果不采用压缩存储，占有的存储单元有n2个，因为是对称矩阵，所以只要存储对角的数据元素和一半的数据元素即可，占有的存储单元有n（n-1）/2个存储单元中。如果我们以行序为主序存储其下三角（包括对角线）的元素，其上三角的元素可以推算出来。415.2 矩阵的压缩存储 对称矩阵如果用一维数组存储一个对称矩阵，只要将对称矩阵存储在一个最大下标为n（n-1）/2的一维数组S中即可。此时按照行优先顺序存储，数据元素aij与数

16、组S的下标k的对应关系为（why?）： i(i-1)/2 +j-1 当ij时 k= j(j-1)/2 + i-1 当ij时425.2 矩阵的压缩存储 对称矩阵对于任意给定的一组下标（i，j），均可在S中找到元素aij，反之，对所有元素都能够确定在S中位置，当ij时，根据对称矩阵的性质推算即可。由此可以看出对称矩阵的存储可以使用一维数组S存储，占用的空间不再是n2，而是n（n-1）/2空间减少了接近一半，实现了二维数组的压缩存储。43 （1）只存放下三角部分由于对称矩阵关于主对角线对称，故我们只需存放主对角线及主对角线以下的元素。这时， a00存入s0，a10 存入s1，a11存入 s2，具体参

17、见图5-4。这时sk与aij的对应关系为： i(i+1)/2+j 当 ij k= j(j+1)/2+i 当 ij 上面的对应关系读者很容易推出：当ij 时，aij在下三角部分中，aij前面有i行，共有1+2+3+i个元素，而aij是第i行的第j个元素，即有k=1+2+3+i+j=i(i+1)/2+j；当ij时，交换i与j即可。故sk与aij的对应关系为： i*n- +j-i 当ij k= j*n- +i-j 当ij46数据结构（Java版）（第3版）2.对称矩阵的压缩存储 数据结构（Java版）（第3版）3.对角矩阵的压缩存储 495.2 稀疏矩阵稀疏矩阵对稀疏矩阵很难下一个确切的定义，它只是

18、一个凭人们的直觉来理解的概念。一般认为，一个较大的矩阵中，零元素的个数相对于整个矩阵元素的总个数所占比例较大时，该矩阵就是一个稀疏矩阵。例如，有一个66阶的矩阵A，其36个元素中只有8个非零元素，那么，可以称矩阵A为稀疏矩阵。50515.2 稀疏矩阵稀疏矩阵稀疏矩阵一般是指矩阵中的大部分元素为零，仅有少量元素非零的矩阵称为稀疏矩阵；或者说矩阵A（m n）中有S个非零元素，如果S远远小于矩阵的元素总数，称A为稀疏矩阵。稀疏矩阵的存储一般只要保存非零元素即可，对于零元素可以不与保存，这样可以实现稀疏矩阵的压缩存储。 525.2 稀疏矩阵稀疏矩阵稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则如下

19、：每一个非零元素占有一行，每行中包含非零元素所在的行号、列号、非零元素的数值。53表示稀疏矩阵的三元组 (0,2,11)，(0,4,17)，(1,1,20)，(3,0,19)，(3,5,28)，(4,4,50)行号列号元素值rowcolumnvalue54555.2 稀疏矩阵稀疏矩阵如果每个非零元素按照此种方法存储，虽然能够完整地描述非零元素，但如果矩阵中有整行（或整列）中没有非零元素，此时可能不能够还原成原来的矩阵所以为了完整地描述稀疏矩阵，在以上描述的情况下，如果增加一行的内容，该行包括矩阵的总的行数、矩阵的总的列数，矩阵中非零元素的个数，就可以还原为原来的矩阵描述了。 56例如，下列三元

20、组表(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) 加上(6,7，8)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 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 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0

21、 0 0 0 0 0 0 0 0 0 0 0 0 0M=T=5.2 稀疏矩阵575.2 稀疏矩阵稀疏矩阵归纳起来，若一个稀疏矩阵有t个非零元素，则需要用t+1行的三元组来表示稀疏矩阵。到底矩阵何时使用三元组存储呢？一般对mn的矩阵来说，只要满足（t+1）*3m*n这个条件，使用三元组存储可以节省空间，否则更加浪费空间，也就没有必要使用三元组存储，所以稀疏矩阵中的非零元素的个数t是能否使用三元组存储的关键。 585.2 稀疏矩阵稀疏矩阵转换为三元组存储 首先应该将稀疏矩阵转换为三元组存储，然后才利用三元组的存储，实现对矩阵的各种运算。595.2 稀疏矩阵表5.1 稀疏矩阵三元组的顺序存储结构数组

22、下标行下标列下标数据元素值01111312233734384449数据结构（Java版）（第3版）2.稀疏矩阵三元组顺序表 （1）稀疏矩阵三元组顺序表类 public class SeqSparseMatrix int rows, columns; /矩阵行数、列数 SeqList list; /三元组顺序表数据结构（Java版）（第3版）2.稀疏矩阵三元组顺序表（2）获得或设置稀疏矩阵元素值（3）稀疏矩阵描述字符串 （4）稀疏矩阵相加 【例5.2】三元组顺序表表示的稀疏矩阵及其加法运算。625.2 稀疏矩阵三元组的链式存储结构1三元组单链表 数据结构（Java版）（第3版）4.稀疏矩阵行的单

23、链表 （1）稀疏矩阵三元组行的单链表类public class LinkedSparseMatrix int rows, columns; /矩阵行数、列数 SeqListPolySLinkedList list; /行指针顺序表，元素是多项式排序单链表数据结构（Java版）（第3版）4.稀疏矩阵行的单链表（2）获得或设置稀疏矩阵元素值（3）稀疏矩阵描述字符串 （4）稀疏矩阵相加 （5）深度拷贝及应用 655.2 稀疏矩阵三元组的链式存储结构3十字链表示数据结构（Java版）（第3版）（6）比较两个矩阵是否相等数据结构（Java版）（第3版）5.十字链表 数据结构（Java版）（第3版）十字链

24、表存储的稀疏矩阵类public class CrossNode /十字链表结点类 Triple data; /数据域表示三元组 CrossNode right, down; /right指向行的下一个结点，down指向列的下一个结点public class CrossLinkedSparseMatrix int rows, columns; /矩阵行数、列数 CrossNode rowheads,columnheads; /行、列指针数组 数据结构（Java版）（第3版）5.3 广义表5.3.1 广义表抽象数据类型5.3.2 广义表的存储结构5.3.3 广义表双链表示的实现 5.3.4 m元多项式的广义表表示705.3 广义表 广义表的定义广义表是线性表的扩展，具体定义为n（n0）个元素的有限集合。其中元素有以下两种类型：1）一个原子元素（指不可再分的元素）；2）一个可以再分的元素（或称为一个子表）。如果所有元素都是原子元素，则称为线性表，如果含有子表则是广义表。N的值是广义表的长度，如果n=0，称为空表。数据结构（Java版）（第3版）5.3.1 广义表抽象数据类型广义表定义 GList = (a0, a1, an-1)中国(北京, 上海, 江苏(南京, 苏州), 浙江(杭州), 广东(广州) L(a,