数据结构(Java)-第5章

1、基本内容1.数组的定义和运算数组的定义和运算 第第5章章 数组和广义表数组和广义表 2.数组顺序存储结构数组顺序存储结构 3.矩阵的压缩存储矩阵的压缩存储 4.广义表广义表5.数组项目实践数组项目实践 NEXT Neusoft1、数组（、数组（array）的定义）的定义数组数组是由是由n个（个（n1）具有相同数据类型的数据元素（）具有相同数据类型的数据元素（a0，a1，ai-1，ai，ai+1，an-1）构成的有限序列，并且这些数据元素占用）构成的有限序列，并且这些数据元素占用一片地址连续的内存单元。在一片地址连续的内存单元。在Java语言中，数组的本身是堆中的对语言中，数组的本身是堆中的对象

2、，它能保存基本类型变量或其他对象的引用。在使用数组之前，象，它能保存基本类型变量或其他对象的引用。在使用数组之前，需要声明并构造数组。需要声明并构造数组。例如：声明一个用于保存学生考试成绩的一维数组例如：声明一个用于保存学生考试成绩的一维数组scores，即，即double scores;然后构造数组，然后构造数组，scores = new double5;一一. 数组的定义和运算数组的定义和运算NEXT Neusoft2、数组的运算、数组的运算数组的基本操作主要有以下数组的基本操作主要有以下3种，以一维数组为例：种，以一维数组为例：（1）求数组的长度：）求数组的长度：length（）（）初始

3、条件：数组已存在。初始条件：数组已存在。操作结果：返回数组中数据元素的个数。操作结果：返回数组中数据元素的个数。（2）取值：）取值：getValue（index）初始条件：数组已存在。初始条件：数组已存在。操作结果：返回数组下标为操作结果：返回数组下标为index的数组元素的值。的数组元素的值。（3）赋值：）赋值：setValue（index，newValue）初始条件：数组已存在。初始条件：数组已存在。操作结果：将数组下标为操作结果：将数组下标为index的数组元素的值设置为的数组元素的值设置为newValue。NEXT Neusoft 二、二、数组顺序存储结构数组顺序存储结构 1、一维数组

4、、一维数组一维数组一维数组占用一片地址连续的内存单元，设数组第一个元素占用一片地址连续的内存单元，设数组第一个元素a0 的存储地的存储地址为，每个元素占用址为，每个元素占用c字节，则数组任意一个元素字节，则数组任意一个元素ai的存储地址为：的存储地址为：2、多维数组、多维数组以以二维数组二维数组为例，一个为例，一个m行行n列的二维数组如下所示：列的二维数组如下所示：0()()iLoc aLoc aic 0001020,11011121,11,01,11,21,1nnm nmmmmnaaaaaaaaAaaaaNEXT Neusoft二维数组的两种存储方式二维数组的两种存储方式NEXT Neuso

5、ft【例例5.1】有二维数组有二维数组double arr=new double45，试问：，试问：（1）数组）数组arr中存放多少个数据元素？数组中存放多少个数据元素？数组arr总共占用多少字节的存储总共占用多少字节的存储空间？空间？（2）假设数组）假设数组arr的首地址（数组一个元素的地址）为的首地址（数组一个元素的地址）为8000，如果采用，如果采用按行为主序的存储方式，则数组元素按行为主序的存储方式，则数组元素arr23的存储地址是多少？的存储地址是多少？NEXT Neusoft 三、三、矩阵的压缩存储矩阵的压缩存储 1、三角矩阵、三角矩阵三角矩阵分为上三角矩阵和下三角矩阵。三角矩阵分

6、为上三角矩阵和下三角矩阵。上三角矩阵上三角矩阵是指矩阵的主对角是指矩阵的主对角线（不包括主对角线）下方的元素均为常数线（不包括主对角线）下方的元素均为常数c或零的或零的n阶方阵；阶方阵；下三角矩下三角矩阵阵是指矩阵的主对角线（不包括主对角线）上方的元素均为常数是指矩阵的主对角线（不包括主对角线）上方的元素均为常数c或零或零的的n阶方阵。阶方阵。 （a）上三角矩阵）上三角矩阵 （b）下三角矩阵）下三角矩阵0001020,111121,11,1nnn nnnaaaacaaaAccca 0010111,01,11,21,1n nnnnnnacccaaccAaaaa NEXT Neusoft（1）下三

7、角矩阵）下三角矩阵以下三角矩阵为例，第以下三角矩阵为例，第1行有行有1个非零元素个非零元素a00，第，第2行有行有2个非零元素个非零元素a10和和a11。依次类推，第。依次类推，第i行有行有i+1个非零元素。矩阵中非零元素总数为：个非零元素。矩阵中非零元素总数为：利用下三角矩阵的规律，可以采用长度为（）的一维数组利用下三角矩阵的规律，可以采用长度为（）的一维数组B，行优先压，行优先压缩存储下三角矩阵中的元素，其中缩存储下三角矩阵中的元素，其中B 用于存放下三角矩阵中重复的常用于存放下三角矩阵中重复的常数数c。得出矩阵。得出矩阵 中任意一个元素中任意一个元素aij与一维数组与一维数组B的下标的下

8、标k( )之间的关系如下：之间的关系如下：10(1)(1)2ninni0(1)/2knnn nA(1)()2(1)()2iijijknnij NEXT Neusoft其中，其中，i为行下标，为行下标，j为列下标。假设每个元素占用为列下标。假设每个元素占用L个字节，当个字节，当 时时，元素，元素aij的地址为：的地址为：当当 时，元素时，元素aij的地址为：的地址为：下三角矩阵的压缩存储如下图所示：下三角矩阵的压缩存储如下图所示：ij()( 0)(1)/ 2)ijLoc aLoc BiijLij()( 0)(1)/ 2)ijLoc aLoc BnnLNEXT Neusoft（2）上三角矩阵）上三

9、角矩阵与下三角矩阵类似，上三角矩阵也可以采用压缩存储，上三角矩阵采用与下三角矩阵类似，上三角矩阵也可以采用压缩存储，上三角矩阵采用以列为主序存放矩阵元素较为方便。上三角矩阵中任意一个元素以列为主序存放矩阵元素较为方便。上三角矩阵中任意一个元素aij与一与一维数组维数组B的下标的下标k( )之间的关系如下：之间的关系如下：0(1)/ 2knn(1)()2(1)()2jjiijknnij NEXT Neusoft其中，其中，i为行下标，为行下标，j为列下标。假设每个元素占用为列下标。假设每个元素占用L个字节，当个字节，当 时时，元素，元素aij的地址为：的地址为：当当 时，元素时，元素aij的地址

10、为：的地址为：ijij()( 0)(1)ijLoc aLoc BjjiL()( 0)(1)/ 2)ijLoc aLoc BnnLNEXT Neusoft2、对称矩阵、对称矩阵在在n阶方阵中，若任意一个矩阵元素满足下述性质：阶方阵中，若任意一个矩阵元素满足下述性质：则称则称 为为n阶阶对称矩阵对称矩阵。在对称矩阵中，以主对角线。在对称矩阵中，以主对角线 为轴线的对称位置上矩阵元素值相等。因此，可以只存储对称矩阵的上为轴线的对称位置上矩阵元素值相等。因此，可以只存储对称矩阵的上三角或下三角元素，然后让每一对对称元素共享同一个存储单元即可。三角或下三角元素，然后让每一对对称元素共享同一个存储单元即可

11、。与三角矩阵类似，与三角矩阵类似，n阶对称矩阵中的阶对称矩阵中的 个元素可以被压缩存储到长个元素可以被压缩存储到长度为度为 的一维地址空间。的一维地址空间。1,1)ijjiaainjn n nA00111,1,nnaaan n(1)/ 2nnNEXT Neusoft采用长度为采用长度为 的一维数组的一维数组B，行优先压缩存储对称矩阵中的元素，得出，行优先压缩存储对称矩阵中的元素，得出矩阵中任意一个元素矩阵中任意一个元素aij与一维数组与一维数组B的下标的下标k( )之间的关系如下之间的关系如下：其中，其中，i为行下标，为行下标，j为列下标。假设每个元素占用为列下标。假设每个元素占用L个字节，取

12、个字节，取 ， ，则，则n阶方阵中任意元素阶方阵中任意元素aij的地址为：的地址为：(1)/ 2nn(1)()2(1)()2iijijkjjiij 0(1)/2knn max( , )ii jmin( , )ji j()( 0)(1)/ 2)ijLoc aLoc BiijLNEXT Neusoft3、对角矩阵、对角矩阵对角矩阵对角矩阵是指是指n阶方阵阶方阵 的所有非零元素都集中在以主对角线为中心的的所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在主对角线上、下方若干条对角带状区域中，即除了主对角线上和直接在主对角线上、下方若干条对角线上的元素之外，其余元素皆为零。如下

13、图所示，主对角线的两侧分别线上的元素之外，其余元素皆为零。如下图所示，主对角线的两侧分别有有d条次对角线，称条次对角线，称d为对角矩阵的半带宽，为对角矩阵的半带宽，2d+1为对角矩阵的带宽。例为对角矩阵的带宽。例如对角矩阵如对角矩阵A为：为：其半带宽其半带宽d=1，带宽为，带宽为3，类似这样的矩阵也被称作三对角矩阵。，类似这样的矩阵也被称作三对角矩阵。 0001101112212223323334aaaaaAaaaaaa 4344aan nANEXT Neusoft矩阵矩阵 中除第中除第0行外的任意元素行外的任意元素aij与一维数组与一维数组B的下标的下标k之间存在如下之间存在如下关系：关系：

14、n nA2+3i-1-1i jki j（ -1）+j-(i-1)=2i+j ()()NEXT Neusoft4、稀疏矩阵、稀疏矩阵稀疏矩阵稀疏矩阵（Sparse Matrix）是指具有较多非零元素且非零元素的分布无）是指具有较多非零元素且非零元素的分布无规律的矩阵。假设在规律的矩阵。假设在 的矩阵的矩阵 中，有中，有t个元素不为零，令个元素不为零，令 ，称称 为矩阵的稀疏因子。如果为矩阵的稀疏因子。如果 ，一般认为是稀疏矩阵。，一般认为是稀疏矩阵。 （1）三元组顺序表）三元组顺序表例如有矩阵例如有矩阵A如下所示：如下所示：m nm nA/()tm n0.05A NEXT Neusoft矩阵矩阵

15、A共有共有56个元素，其中大部分是零元素，只有个元素，其中大部分是零元素，只有3个非零元素。矩阵的稀疏因个非零元素。矩阵的稀疏因子，故子，故A为稀疏矩阵。可以用为稀疏矩阵。可以用三元组三元组按行为主序将按行为主序将A表示为一个线性表：表示为一个线性表：（0，1，6），（），（3，4，8），（），（6，7，5）。然后我们可以采用顺序存储结构的一维。然后我们可以采用顺序存储结构的一维数组来存放这个线性表，设为数组数组来存放这个线性表，设为数组array。数组。数组array与其对应的三元组表如表与其对应的三元组表如表5.1所示。所示。表表5.1 稀疏矩阵稀疏矩阵A的顺序存储的顺序存储数组数组Bi(

16、行标行标)j(列标列标)value（值）（值）array0016array1348array2675NEXT Neusoft/* 三元组结点类三元组结点类*/public class SMnode private int row;/行标行标private int column;/列标列标private int value;/矩阵元素的值矩阵元素的值/构造方法构造方法1public SMnode() this(0,0,0);/构造方法构造方法2public SMnode(int row, int column, int value) this.row = row;this.column = co

17、lumn;this.value = value;public int getColumn() return column;NEXT Neusoftpublic void setColumn(int column) this.column = column;public int getRow() return row;public void setRow(int row) this.row = row;public int getValue() return value;public void setValue(int value) this.value = value; NEXT Neusof

18、t接下来基于三元组顺序表来实现稀疏矩阵。对于稀疏矩阵来说，矩阵的接下来基于三元组顺序表来实现稀疏矩阵。对于稀疏矩阵来说，矩阵的行数、列数和存放非零元素的三元组是矩阵操作的基本数据。因此可以行数、列数和存放非零元素的三元组是矩阵操作的基本数据。因此可以把上述成分设计成稀疏矩阵类中的私有成员变量，其中三元组存放在一把上述成分设计成稀疏矩阵类中的私有成员变量，其中三元组存放在一个一维数组中，三元组的个数可以通过数组的个一维数组中，三元组的个数可以通过数组的length属性获得。属性获得。 public class SparseMatrix private SMnode tripleData;/三元组

19、顺序表三元组顺序表private int rows;/稀疏矩阵总行数稀疏矩阵总行数private int columns;/稀疏矩阵总列数稀疏矩阵总列数/构造方法构造方法1，指定三元组表长度，指定三元组表长度public SparseMatrix(int n) rows=0;columns=0;tripleData=new SMnoden;/为数组分配存储空间为数组分配存储空间for(int i=0;in;i+)tripleDatai=new SMnode();NEXT Neusoftpublic SparseMatrix(int sm ) /构造方法构造方法2，指定稀疏矩阵，指定稀疏矩阵ro

20、ws=sm.length;/矩阵行数矩阵行数columns=sm0.length;/矩阵列数矩阵列数int i,j,count=0; /count用于保存矩阵中非零元素个数用于保存矩阵中非零元素个数for(i=0;ism.length;i+)for(j=0;jsmi.length;j+)if(smij!=0)count+;/累加累加int k=0;tripleData=new SMnodecount;/为数组分配存储空间为数组分配存储空间for(i=0;ism.length;i+)for(j=0;jsmi.length;j+)if(smij!=0)tripleDatak=new SMnode(

21、i,j,smij);k+;NEXT Neusoft/输出稀疏矩阵的三元组表示输出稀疏矩阵的三元组表示public void showSparseMatrix()System.out.println(稀疏矩阵：稀疏矩阵：+rows+行行 +columns+列列+tripleData.length+个非零元素个非零元素n);System.out.println(矩阵的三元组顺序表如下：矩阵的三元组顺序表如下：n);System.out.println(行标行标t列标列标t元素值元素值n);for(int i=0;itripleData.length;i+)System.out.println(tr

22、ipleDatai.getRow()+t+tripleDatai.getColumn()+t+tripleDatai.getValue()+n); NEXT Neusoft【例例5.2】编写程序，基于三元组顺序表来存储稀疏矩阵，编写程序，基于三元组顺序表来存储稀疏矩阵，然后将该稀疏矩阵转置然后将该稀疏矩阵转置。【说明说明:】矩阵转置指的是将矩阵中每个元素的行列序号进行调换。矩阵转置指的是将矩阵中每个元素的行列序号进行调换。NEXT Neusoft（2）十字链表）十字链表对于任意的稀疏矩阵，每个非零元素用一个结点来表示，结点的结构如对于任意的稀疏矩阵，每个非零元素用一个结点来表示，结点的结构如下

23、图所示。可以看到，每个结点由五个域组成，其中三个数据域，下图所示。可以看到，每个结点由五个域组成，其中三个数据域，row存放元素所在的行号，存放元素所在的行号，column存放元素所在的列号，存放元素所在的列号，value存放元素的存放元素的值。其他两个指针域值。其他两个指针域down和和right分别存放列后继引用和行后继引用，分别存放列后继引用和行后继引用，分别用来链接在同列和同行中的下一个非零元素结点。分别用来链接在同列和同行中的下一个非零元素结点。 NEXT Neusoft例如有矩阵例如有矩阵B： 稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示 4 5BNEXT Neusoft四四、广义

24、表广义表 1、广义表的定义、广义表的定义广义表广义表是线性表的推广，线性表限定其中元素必须是原子类型，不能再分是线性表的推广，线性表限定其中元素必须是原子类型，不能再分解，而广义表中数据元素还可再分解，即是又一个广义表。一般记作：解，而广义表中数据元素还可再分解，即是又一个广义表。一般记作：LS=（a1，a2，ai-1，ai，ai+1，an）其中，其中，LS是广义表的名称，是广义表的名称，n是广义表的是广义表的长度长度，某一个数据元素，某一个数据元素ai可以是可以是单个元素（称为单个元素（称为原子原子），也可以是广义表（称为），也可以是广义表（称为子表子表）。当广义表）。当广义表LS非空非空时

25、，称第一个元素时，称第一个元素a1为广义表的为广义表的表头表头（Head），称其余元素组成的广义），称其余元素组成的广义表为表为表尾表尾（Tail）。广义表中所含括号的层数称为广义表的）。广义表中所含括号的层数称为广义表的深度深度。原子的。原子的深度为深度为0，空表的深度为，空表的深度为1。 NEXT Neusoft下面列举一些广义表的例子：下面列举一些广义表的例子：A=（）；（）；/广义表广义表A是空表，长度为是空表，长度为0，深度为，深度为1。B=（a，b）；）；/广义表广义表B长度为长度为2，深度为，深度为1。C=（c，B）=（c，（，（a，b）；）；/广义表广义表C长度为长度为2，两个

26、元素分别是，两个元素分别是原子元素原子元素c和子表和子表B，深度为，深度为2。D=（d，D）=（d，（，（d，（，（d，（，（d，（，（）；）；/广义表广义表D长度长度为为2，深度无穷，深度无穷E=（A）=（）；（）；/广义表广义表E非空，长度为非空，长度为1，元素是一个空表，深度，元素是一个空表，深度为为2。NEXT Neusoft2、广义表的图形表示、广义表的图形表示 广义表的图形表示中，采用圆圈表示广义表的图形表示中，采用圆圈表示子表子表，方块表示，方块表示原子原子，并用线段把，并用线段把表和它们的元素连接起来。表和它们的元素连接起来。图图5.7 A=（）；（）； 图图5.8 B=（a，

27、b）；）； NEXT Neusoft图图5.9 C=（c，B）=（c，（，（a，b）；）；图图5.10 D=（d，D）=（d，（，（d，（，（d，（，（d，（，（）；）； NEXT Neusoft3、广义表的性质、广义表的性质（1）广义表是一个多层次的结构。）广义表是一个多层次的结构。根据广义表的定义，广义表的元素可以是子表，而子表的元素仍然可以根据广义表的定义，广义表的元素可以是子表，而子表的元素仍然可以是子表。广义表中所含括号的层数称为广义表的深度。是子表。广义表中所含括号的层数称为广义表的深度。（2）一个广义表可以为其他广义表所共享）一个广义表可以为其他广义表所共享一个广义表可以作为多个

28、广义表的子表，通过该广义表的名称来引用。一个广义表可以作为多个广义表的子表，通过该广义表的名称来引用。（3）可递归性）可递归性如果一个广义表的子表之一是它自身，那么该广义表成为了一个递归表如果一个广义表的子表之一是它自身，那么该广义表成为了一个递归表。NEXT Neusoft4、广义表的运算、广义表的运算（1）创建广义表：）创建广义表：initGList()初始条件：广义表不存在。初始条件：广义表不存在。操作结果：创建一个空的广义表。操作结果：创建一个空的广义表。（2）插入数据元素：）插入数据元素：insert(x)初始条件：广义表已存在。初始条件：广义表已存在。操作结果：将新的数据元素操作结

29、果：将新的数据元素x插入到广义表的第一个位置。插入到广义表的第一个位置。（3）删除数据元素：）删除数据元素：delete()初始条件：广义表已存在。初始条件：广义表已存在。操作结果：删除广义表中的第一个数据元素，同时将广义表的长度减操作结果：删除广义表中的第一个数据元素，同时将广义表的长度减1。NEXT Neusoft（4）求长度：）求长度：length()初始条件：广义表已存在。初始条件：广义表已存在。操作结果：返回广义表的长度，即广义表中数据元素的个数。操作结果：返回广义表的长度，即广义表中数据元素的个数。（5）求深度：）求深度：getDepth()初始条件：广义表已存在。初始条件：广义表

30、已存在。操作结果：返回广义表的深度。操作结果：返回广义表的深度。（6）判断广义表是否为空：）判断广义表是否为空：isEmpty()初始条件：广义表已存在。初始条件：广义表已存在。操作结果：若广义表为空表，返回操作结果：若广义表为空表，返回true，否则返回，否则返回false。NEXT Neusoft（7）取表头：）取表头：getHead( )初始条件：广义表已存在。初始条件：广义表已存在。操作结果：判断广义表是否为空，如操作结果：判断广义表是否为空，如false则返回该广义表的第一个数据则返回该广义表的第一个数据元素。如元素。如true则返回则返回null。（8）取表尾：）取表尾：getTail()初始条件：广义表已存在。初始条件：广义表已存在。操作结果：判断广义表是否为空，如操作结果：判断广义表是否为空，如false则返回该广义表除第一个数据则返回该广义表除第一个数据元素外的所有其他元素。如元素外的所有其他元素。如true则返回则返回