第五章 数组与广义表

1、|第第1章章 绪论绪论|第第2章章 线性表线性表|第第3章章 串串|第第4章章 栈与队列栈与队列第第5章章 数组和广义表数组和广义表|第第6章章 树和二叉树树和二叉树|第第7章章 图图|第第8章章 查找查找|第第9章章 排序排序|5.1 5.1 数组数组|5.2 5.2 特殊矩阵的压缩存储特殊矩阵的压缩存储|5.3 5.3 广义表广义表|5.1.1 一维数组一维数组|5.1.2 多维数组多维数组|数组是一组相同数据类型的数据元素的集合，数组元素数组是一组相同数据类型的数据元素的集合，数组元素按次序存储于一个地址连续的内存空间中。按次序存储于一个地址连续的内存空间中。|数组元素在数组中的位置通常

2、称为数组的下标。数组元素在数组中的位置通常称为数组的下标。5.1 数组的定义数组的定义|数组分配内存空间的方式有数组分配内存空间的方式有2种种z静态数组静态数组：声明时给出数组元素个数。当程序开始运行时，：声明时给出数组元素个数。当程序开始运行时，数组即获得系统分配的一块地址连续的内存空间。静态数数组即获得系统分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。组所占用的内存空间由系统自动管理。z动态数组动态数组：声明时不指定数组长度。当程序运行中需要使：声明时不指定数组长度。当程序运行中需要使用数组时，向系统申请数组的存储单元空间，并给出数组用数组时，向系统申请数组的存储单

3、元空间，并给出数组长度。当数组使用完之后，需要向系统归还所占用的内存长度。当数组使用完之后，需要向系统归还所占用的内存空间。空间。|在在Java中，数组元素既可以是简单数据类型，也可以是中，数组元素既可以是简单数据类型，也可以是引用类型。而且引用类型。而且Java中的数组都是动态数组。中的数组都是动态数组。5.1.1 一维数组一维数组5.1.2 多维数组多维数组a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =以二维数组为例，以二维数组为例，数组和广义表均

4、是元素为复合结构的线性结构。数组和广义表均是元素为复合结构的线性结构。1 多维数组的概念多维数组的概念2. 多维数组的遍历多维数组的遍历 :以以行序行序为主序为主序:可以看成可以看成 A = ( 1， 2， ， m )T. . .其中其中 i 是一个是一个行向量行向量形式的线性表，形式的线性表，1im i = ( ai 1，ai 2， ，ai n ). . .a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =PASCAL、C按照某种次序访问一个数据结构中的

5、所有元素，并且每按照某种次序访问一个数据结构中的所有元素，并且每个数据元素恰好访问一次，称为对该数据结构的遍历。个数据元素恰好访问一次，称为对该数据结构的遍历。可以看成可以看成 A = ( 1， 2， ， n ). . .其中其中 j 是一个是一个列向量列向量形式的线性表，形式的线性表，1jn j = ( a1 j，a2 j， ，amj )T. . .a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =以以列序列序为主序为主序:FORTRAN3. 多维数组的

6、顺序存储结构多维数组的顺序存储结构数组一旦被定义，其数组一旦被定义，其维数维数和和维界维界就不再改变，故通常就不再改变，故通常采用采用 。如何将多维数组结构转换对应一组连续的存储单元？如何将多维数组结构转换对应一组连续的存储单元？顺序存储结构顺序存储结构以列序为主序以列序为主序a11a21 am,1a12a22 am,2 2a1,n am,na2 2,n 1 2 na11 a12 a13 a1,na21 a22 a23 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn 1 2 . . . n以行序为主序以行序为主序a11a1

7、2 a1,na21a22 a2 2,n am,1 1 am,n am,2 2 1 2 ma11 a12 a13 a1,na21 a22 a23 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn 1 2 m. . .对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置?a11a12 a1,na21a22 a2 2,n am,1 1 am,n am,2 2 1 2 m 设数组以设数组以行序行序为主序。为主序。二维数组二维数组 Amn 数组元素数组元素 aij 的存储

8、位置为的存储位置为Loc(ai,j) =Loc(a1,1)是是a1,1的存储位置；的存储位置；存储密度为存储密度为1；1例，例，Loc(a2,2) =+ ( i-1)n + (j-1)Loc(a1,1)Loc(a1,1) + n +1例例1:一个二维数组一个二维数组A,行下标的范围是行下标的范围是1到到6,列下标的范围是列下标的范围是0到到7,每每个数组元素用相邻的个数组元素用相邻的6个字节存储个字节存储,存储器按字节编址存储器按字节编址;那么那么,这个这个数组占数组占 个字节。个字节。例例2:已知二维数组已知二维数组Am,m按行存储的元素地址公式是：按行存储的元素地址公式是：Loc(aij)

9、=Loc(a11)+(i-1)*m+(j-1)*K , 按列存储的公式是？按列存储的公式是？例例3计算机系考研题计算机系考研题：设数组设数组a160, 170的基地址为的基地址为2048，每个元素占每个元素占2个存储单元，若以列序为主序顺序存储，则元素个存储单元，若以列序为主序顺序存储，则元素a32,58的的 存储地址为存储地址为 。答：答：Volume=m*n*L= 6 * (7+1) * 6=48*6 =288288答答:Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 尽管是方阵,公式仍不同答答:Loc(aij) = Loc(a11) + (m (j-1) + i-1

10、) lLoc(a32,58)=2048+(60*(58-1)+32-1)*28950注意审题注意审题,以列为主序以列为主序!|设二维数组中的每一个数组元素设二维数组中的每一个数组元素Aij占用占用6个字节个字节,行下行下标标i从从0到到8,列下标列下标j从从2到到5,1)则二维数组则二维数组A共占用共占用_(1)_个字节个字节;2)A中中6行和行和4列的数组元素共占用列的数组元素共占用_(2)_个字节个字节;3)若按行优先顺序存放二维数组若按行优先顺序存放二维数组A,其第一个数组元素存放其第一个数组元素存放的首字节号为的首字节号为1000(十进制十进制),则最后一个数组元素存放则最后一个数组元

11、素存放的首字节为的首字节为_(3)_4)数组元素数组元素A34的首字节号为的首字节号为_(4)_9行行4列列 36*6 2.（9+4-1）*63.1000+216-6 4. 1000+（3*4+（4-2）*61. 数组数组A中中,每个元素每个元素A的长度为的长度为3个字节个字节,行下标行下标i从从1到到8,列列下标下标j从从1到到10,从首地址从首地址SA开始连续存放在存储器内开始连续存放在存储器内,存存放该数组至少需要的单元数是放该数组至少需要的单元数是?2. 数组数组A中中,每个元素每个元素A的长度为的长度为3个字节个字节,行下标行下标i从从1到到8,列列下标下标j从从1到到10,从首地址

12、从首地址SA开始连续存放在存储器内开始连续存放在存储器内,该该数组按行存放时数组按行存放时,元素元素A85的起始地址为的起始地址为?3. 数组数组A中中,每个元素每个元素A的长度为的长度为3个字节个字节,行下标行下标i从从1到到8,列列下标下标j从从1到到10,从首地址从首地址SA开始连续存放在存储器内开始连续存放在存储器内,该该数组按列存放时数组按列存放时,元素元素A58的起始地址为的起始地址为?240SA+222 SA+(8-1)*10+(5-1)*3SA+180 SA+(8-1)*8+(5-1)*3实际中，存在许多特殊矩阵，例如在矩阵中有许多实际中，存在许多特殊矩阵，例如在矩阵中有许多值

13、相值相同同的元素或者的元素或者零元素零元素。 10 0 10 0 10 0 10 0 0. . . . . . . . . . . . .用定长数组存储造成浪费。用定长数组存储造成浪费。5.2 特殊矩阵的压缩存储特殊矩阵的压缩存储为了节省存储空间，需要对这类矩阵进行为了节省存储空间，需要对这类矩阵进行压缩存储压缩存储。压缩存储压缩存储是指为是指为多个值相同多个值相同的元素只分配一个存储空间；的元素只分配一个存储空间；对对零元素零元素不分配空间。不分配空间。 对称矩阵对称矩阵 对角矩阵对角矩阵 稀疏矩阵稀疏矩阵 三角矩阵三角矩阵对称矩阵是满足 aij= aji 性质的n阶矩阵(1i,jn)。可以

14、看出可以看出:对称矩阵中的元素对称矩阵中的元素，故只要，故只要存储矩阵中存储矩阵中或或中的元素，让每两个对称的元素中的元素，让每两个对称的元素共享一个存储空间，共享一个存储空间，的空间。能节约近的空间。能节约近一半的存储空间。一半的存储空间。1 5 1 3 75 0 8 0 01 8 9 2 63 0 2 5 17 0 6 1 3 a11 a21 a22 a31 a32 a33 an,1 an,2 an,3 an,nK= 0 1 2 3 4 5 n(n-1)/2 n(n+1)/2-1a11a21 a22a31 a32 a33 an,1 an,2 an,3 an,na11 a12 a13 a1n

15、a21 a22 a23 a2na31 a32 a33 a3n an1 an2 an3 annv当当ij时时,aij 在矩阵的在矩阵的下三角下三角中。中。在在aij 之前的之前的i-1行行(从第从第1行到第行到第i-1行行)共共有有1+2+i-1=i*(i-1)/2个元素个元素,在第在第i行行上上,aij 之前有之前有ai1,ai2,ai3,ai(j-1) 即即j-1个元个元素素,因此存储单元的下标因此存储单元的下标k有有: k = i(i-1)/2+( j-1)v当当ij 时时aij 在矩阵的在矩阵的上三角上三角中。中。由于由于aij=aji 所以交换上式所以交换上式i,j可得可得: k =

16、j( j-1)/2+( i-1)a11 a12 a13 a1na21 a22 a23 a2na31 a32 a33 a3n an1 an2 an3 ann公式不要死记硬背公式不要死记硬背应掌握其推导过程应掌握其推导过程二、三角矩阵二、三角矩阵所谓所谓下下(上上)三角矩阵三角矩阵是指矩阵的上是指矩阵的上(下下)三角三角(不包括对不包括对角线角线)中的元均为常数中的元均为常数 c 的的 n 阶矩阵。阶矩阵。a11a21 a22an1 1 an2 ann. . . . . . .C下三角矩阵下三角矩阵和对称矩阵基本一样，只需除存储其下和对称矩阵基本一样，只需除存储其下(上上)三角中的元三角中的元之外

17、，再增加一个存储单元存放之外，再增加一个存储单元存放 c 。k = i (i 1)2+ j - - 1当当 i j关键问题关键问题: 如何建立数组元如何建立数组元 SAk 和矩阵元和矩阵元 aij 之间的之间的一一对应关系。一一对应关系。k = 0123n(n+1)2- - 1n(n+1)2当当 i jn(n+1)2a11a21a22a31annca12 , ,a13 所有非所有非0元素都集元素都集中在以主对角线为中中在以主对角线为中心的带状区域。心的带状区域。它可以行为主它可以行为主,或或以对角线的顺序以对角线的顺序,将将其压缩到一维数组上。其压缩到一维数组上。a00 a01 a02 0 0

18、 0 0 0 0 0a10 a11 a12 a13 0 0 0 0 0 0a20 a21 a22 a23 a24 0 0 0 0 0 0 a31 a32 a33 a34 a35 0 0 0 0 0 0 a42 a43 a44 a45 a46 0 0 0 0 0 0 a53 a54 a55 a56 a57 0 0 0 0 0 0 a64 a65 a66 a67 a68 0 0 0 0 0 0 a75 a76 a77 a78 a79 0 0 0 0 0 0 a86 a87 a88 a89 0 0 0 0 0 0 0 a97 a98 a99oo一般情况一般情况oa11 a12a21 a22 a23a

19、32 a33 a34an,n-1-1 ann an-1-1,no三对角矩阵三对角矩阵关键问题关键问题: 如何建立数组元如何建立数组元 SAk 和矩阵元和矩阵元 aij 之间的一一之间的一一对应关系。对应关系。k=(3(i-1)-1)+(j-i+2)-1=2i + j - 3(| | i - - j | | 1)a11 a12a21 a22 a23 a32 a33 a34an,n-1-1 ann an-1-1, n-2-2 an-1-1, n-1 -1 an-1-1,n a43 a44 a450aij因因对角数对角数不不同而不同同而不同第第i(i1)行的第行的第j-i+2个非零元素个非零元素|1

20、 稀疏矩阵的三元组稀疏矩阵的三元组|2 三元组的顺序存储结构三元组的顺序存储结构|3 三元组的链式存储结构三元组的链式存储结构稀疏矩阵稀疏矩阵非零元很少的矩阵。非零元很少的矩阵。稀疏因子稀疏因子: 设设 mn 的矩阵，有的矩阵，有 t 个非零元，令个非零元，令mnt= ，称，称为矩阵的稀疏因子。为矩阵的稀疏因子。通常认为通常认为 0.05 时称为时称为稀疏矩阵稀疏矩阵。|稀疏矩阵的非零元素由三部分组成：行下标、列下标稀疏矩阵的非零元素由三部分组成：行下标、列下标和矩阵元素值，这称为稀疏矩阵的三元组。和矩阵元素值，这称为稀疏矩阵的三元组。|用稀疏矩阵的三元组用稀疏矩阵的三元组序列序列表示为：表示

21、为：1,1,1,3,1,2,3,3,7,4,3,8,4,4,9。 9800070200000001A（2） 三元组的顺序存储结构三元组的顺序存储结构三元组三元组( i ，j ，aij )表示非零元素表示非零元素i 行数，行数，j 列数，列数，aij 非零元。非零元。M67 = 0 12 9 0 0 0 00 0 0 0 0 0 0- -3 0 0 0 0 14 00 0 0 24 0 0 0 00 0 18 0 0 0 0 01515 0 0 - -7 0 0 0i j aij1 2 121 3 93 1 - -33 6 14144 3 24245 2 18186 1 15156 4 -7-7

22、 SparseNode1类的一个对象表示稀疏矩阵的一个三元组，它类的一个对象表示稀疏矩阵的一个三元组，它只记录了稀疏矩阵中的一个元素的位置和值。只记录了稀疏矩阵中的一个元素的位置和值。public class SparseNode1 /稀疏矩阵的三元组表示的结点结构 public int row; /行下标 public int column; /列下标 public int data; /值 public SparseNode1(int i,int j,int k) row=i; column=j; data=k; public SparseNode1() this(0,0,0); publ

23、ic void output() /输出一个元素的三元组值 下面声明的下面声明的Sparse1类的一个对象则表示一个稀疏矩阵，类的一个对象则表示一个稀疏矩阵，成员成员table是一个数组表示的线性表，元素类型为是一个数组表示的线性表，元素类型为SparseNode1类。构造方法将一个稀疏矩阵转换成三元组表示法。类。构造方法将一个稀疏矩阵转换成三元组表示法。public class Sparse1 /稀疏矩阵的三元组顺序存储结构 protected SparseNode1 table; /数组，元素为三元组 public Sparse1(int mat1) /建立三元组表示 System.out

24、.println(稀疏矩阵:); int n=mat1.length; table=new SparseNode1 n*2; /估计数组长度 int i,j,k=0; for(i=0;imat1.length;i+) for(j=0;jmat1i.length;j+) public class Sparse1_ex public static void main(String args) int mat1=1,0,0,0, /稀疏矩阵稀疏矩阵 0,0,0,0, 2,0,7,0, 0,0,8,9; Sparse1 s1=new Sparse1(mat1); /一个对象表示一个稀疏一个对象表示一个

25、稀疏矩阵矩阵 s1.output(); 程序运行结果如下：程序运行结果如下：稀疏矩阵稀疏矩阵: 1 0 0 0 0 0 0 0 2 0 7 0 0 0 8 9稀疏矩阵三元组的顺序表示稀疏矩阵三元组的顺序表示: 行下标行下标 列下标列下标 值值table0 = 111table1 = 312table2 = 337table3 = 438table4 = 449table5 = nulltable6 = nulltable7 = null|数组长度不易设定，可能存在溢出与浪费问题。数组长度不易设定，可能存在溢出与浪费问题。|插入、删除操作不方便。若矩阵元素的值发生变化，一插入、删除操作不方便。若

26、矩阵元素的值发生变化，一个为零的元素变成非零元素，就要向线性表中插入一个个为零的元素变成非零元素，就要向线性表中插入一个三元组；若非零元素变成零元素，就要从线性表中删除三元组；若非零元素变成零元素，就要从线性表中删除一个三元组。为了保持线性表元素间的相对次序，进行一个三元组。为了保持线性表元素间的相对次序，进行插入和删除操作时，就必须移动元素。插入和删除操作时，就必须移动元素。1行的单链表示行的单链表示 将稀疏矩阵每行上的若干个非零元素作为结点链接成一个将稀疏矩阵每行上的若干个非零元素作为结点链接成一个单向链表，每条链表第单向链表，每条链表第1个结点的引用存放在数组中。个结点的引用存放在数组中

27、。 常用的链式存储结构有两种：行（列）的单链表示和常用的链式存储结构有两种：行（列）的单链表示和十字链表示。十字链表示。table1234column data next1112383749图图5.1 稀疏矩阵的行的单链表示稀疏矩阵的行的单链表示 其中，链表的每个结点由其中，链表的每个结点由3个成员组成：个成员组成：column（列下标），（列下标），data（值）和（值）和next（后继结点的引用）。（后继结点的引用）。Table数组元素存放每数组元素存放每条链表第条链表第1个结点的引用。个结点的引用。 声明稀疏矩阵以行的单链表示为如下的声明稀疏矩阵以行的单链表示为如下的SparseNode

28、2类：类：public class SparseNode2 /稀疏矩阵行的单链表示public int column; /列下标public int data; /值public SparseNode2 next; /后继结点的引用public SparseNode2(int i,int j)column=i;data=j;next=null;public SparseNode2() 下面的下面的Sparse2类实现稀疏矩阵的行的单链表示，成员类实现稀疏矩阵的行的单链表示，成员table是是一个数组，元素类型为一个数组，元素类型为SparseNode2类。构造方法是将一个稀疏类。构造方法是将一

29、个稀疏矩阵转换成行的单链表示。矩阵转换成行的单链表示。public class Sparse2 /稀疏矩阵行的单链表示protected SparseNode2 table; /数组元素引用链表的第1个结点public Sparse2(int mat1) /建立稀疏矩阵行的单链表示int n=mat1.length;table=new SparseNode2n+1;int i,j,k=0;SparseNode2 p=null,q;for(i=0;in;i+)p=tablei+1;for(j=0;j null table2=null table3= 1 2 - 3 7 - null table4

30、= 3 8 - 4 9 - null 按行的单链表示的稀疏矩阵，每个结点可以很容易地按行的单链表示的稀疏矩阵，每个结点可以很容易地找到行的后继结点，但很难找到列的后继结点。为充分表找到行的后继结点，但很难找到列的后继结点。为充分表示行和列的后继结点，可以采用十字链表示。示行和列的后继结点，可以采用十字链表示。 将行的单链表示和列的单链表示结合起来存储稀疏矩将行的单链表示和列的单链表示结合起来存储稀疏矩阵称为十字链表示。阵称为十字链表示。 1 2 3 412341 1 1 3 3 7 4 3 8 4 4 9 3 1 2 | 每个结点表示一个非零元素。每个结点有每个结点表示一个非零元素。每个结点有

31、5个成员：行个成员：行下标，列下标，值，行后继引用以及列后继引用。下标，列下标，值，行后继引用以及列后继引用。| 从行的角度看，需要一个数组存放行的单链的第从行的角度看，需要一个数组存放行的单链的第1个结个结点；同样，从列的角度看，还需要一个数组存放列的单链点；同样，从列的角度看，还需要一个数组存放列的单链的第的第1个结点。使用这种表示，各行的非零元素和各列的个结点。使用这种表示，各行的非零元素和各列的非零元素都分别链接在一起，最多有非零元素都分别链接在一起，最多有m+n条链。条链。| 对元素的查找可顺着所在行的链进行，也可以顺着所对元素的查找可顺着所在行的链进行，也可以顺着所在列的链进行。在列的链进行。|5.3.1 广义表的概