第6章数组和广义表

1、1数组和广义表数组和广义表u数组和广义表数组和广义表逻辑上是线性结构的推广逻辑上是线性结构的推广u数数 组组：元素的结构相同元素的结构相同u广义表：广义表：元素的结构可以不同元素的结构可以不同 2第第6章章 数组和广义表数组和广义表 6.1 6.1 数组数组6.2 6.2 稀疏矩阵稀疏矩阵6.3 6.3 广义表广义表3数组数组 n(n1)个相同类型的数据元素构成的有限个相同类型的数据元素构成的有限序列。序列。逻辑表示：逻辑表示： A=(a1,a2,an)高级语言中的数组高级语言中的数组 int A10; char B45 ;6.1.1 数组的基本概念数组的基本概念4二维数组的定义二维数组的定义

2、 int a23; /声明声明A为整型数组类型为整型数组类型 typedef int A3; /定义类型为定义类型为A的一维数组变量的一维数组变量a A a2; 两个变量组成的一个数组，两个变量组成的一个数组，其中每一个变量都是数组其中每一个变量都是数组a01a00a12a11a10a02a0a1结论：结论：二维数组是一个特殊的一维数组，其每个数二维数组是一个特殊的一维数组，其每个数据元素又是一个一维数组。据元素又是一个一维数组。5 nmmmnnnmaaaaaaaaaA,2,1 ,22,21 ,2, 12, 11 , 1 将将Am*n简记为简记为A A=(a1,a2,ai,am)其中，其中，a

3、i=(ai,1,ai,2,ai,n) 二维数组二维数组 二维数组是一个特殊的线性表，其每个数据元素又二维数组是一个特殊的线性表，其每个数据元素又是一个线性表。是一个线性表。 任何多维数组都可以看作一个线性表，线性表中的任何多维数组都可以看作一个线性表，线性表中的每个数据元素又是一个线性表。每个数据元素又是一个线性表。 数组是线性表的推广。数组是线性表的推广。6数组作为数据类型的性质数组作为数据类型的性质1、数组中的、数组中的数据元素数目固定数据元素数目固定。一旦定义了。一旦定义了一个数组，其数据元素数目一个数组，其数据元素数目不再有增减变化不再有增减变化。2、数组中的数据元素具有、数组中的数据

4、元素具有相同的数据类型相同的数据类型。3、数组中的每个数据元素都和、数组中的每个数据元素都和一组唯一的下一组唯一的下标值标值对应。对应。4、数组是一种、数组是一种随机存储结构随机存储结构，可随机存取数，可随机存取数组中的任意数据元素。组中的任意数据元素。7数组的抽象数据类型数组的抽象数据类型ADT Array数据对象：数据对象： Daj1j2jn|ji是数组元素的第是数组元素的第i维下标，维下标，1jibi，bi是数组第是数组第i维的长维的长度，度，aj1j2jn ElemSet 数据关系：数据关系： R=r1,r2,rn ri=| 0jkbk-1, 1kn 且且 ki, 0jibi-2, a

5、j1jijn,aj1ji+1jn D, i=2,n基本操作：基本操作： Value(A,index1,indexn) 操作结果：若各下标不超界，返回数组操作结果：若各下标不超界，返回数组A的对应下标的元素值的对应下标的元素值 Assign(A,e,index1,indexn) 操作结果：若各下标不超界，将变量操作结果：若各下标不超界，将变量e的值赋给由的值赋给由n个下标确定的个下标确定的A的元素的元素 ADisp(A,b1,b2,bn) 操作结果：输出操作结果：输出n维数组维数组A的所有元素值的所有元素值ADT Array 特点：数组一般不做插入和删除操作特点：数组一般不做插入和删除操作86.

6、1.2 数组的存储结构数组的存储结构u类型特点类型特点: 只有只有引用型引用型操作操作 没有没有加工型加工型操作操作适合顺序存储适合顺序存储9一维数组中，一旦一维数组中，一旦a1的存储地址的存储地址LOC(a1)确定，并确定，并假设每个数据元素占用假设每个数据元素占用k个存储单元，则任一数据元个存储单元，则任一数据元素素ai的存储地址的存储地址LOC(ai)就可由以下公式求出：就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in)可见，一维数组中任一数据元素的存储地址可直可见，一维数组中任一数据元素的存储地址可直接计算得到接计算得到一维数组中任一数据元素可直接存取，是

7、一种一维数组中任一数据元素可直接存取，是一种随随机存储的机存储的结构。结构。一维数组的存储一维数组的存储10 矛盾：矛盾：计算机的存储结构是线性的、一维的计算机的存储结构是线性的、一维的 问题：问题：如何用线性的存储结构存放二维数组的元素？如何用线性的存储结构存放二维数组的元素？ 解决方法：解决方法： 1）以）以行序为主序行序为主序存储：存储： 先存储第先存储第1行，然后紧接着存储第行，然后紧接着存储第2行，最后存行，最后存储第储第m行行 2）以）以列序为主序列序为主序存储：存储： 先存储第先存储第1列，然后紧接着存储第列，然后紧接着存储第2列，最后存列，最后存储第储第n列列二维数组的存储二维

8、数组的存储11数组数组a23的顺序存储的顺序存储a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2行序为主序行序为主序a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2列序为主序列序为主序12 当二维数组当二维数组Am*n第一个数据元素第一个数据元素a1,1的存储地址的存储地址LOC(a1,1)和每个数据元素所占用的存储单元和每个数据元素所占用的存储单元k确定后，确定后，该二维数组中任一数据元素该二维数组中任一数据元素ai,j的存储地址可由下式的存储地址可由下式确定：确定： LOC(ai,j)=LOC(

9、a1,1)+(i-1)*n+(j-1)*k 同理可推出在以列序为主序的计算机系统中有：同理可推出在以列序为主序的计算机系统中有： LOC(ai,j)=LOC(a1,1)+(j-1)*m+(i-1)*k 以行序为主序以行序为主序13数组的顺序存储数组的顺序存储 设二维数组设二维数组A是：是： Ac1.d1,c2.d2(c1id1,c2jd2) 其中其中c1、c2和和d1、d2分别为二维数组分别为二维数组A的边界的的边界的下界和上界，每个数组元素占用下界和上界，每个数组元素占用k个存储单元个存储单元 LOC(i,j)=LOC(c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*k 14

10、例例6.1 对二维数组对二维数组float a54计算：计算： (1) 数组数组a中的数组元素数目；中的数组元素数目； (2) 若数组若数组a的起始地址为的起始地址为2000，且每个数组元素长，且每个数组元素长度为度为32位位(即即4个字节个字节)，数组元素，数组元素a32的内存地址。的内存地址。 解：该数组的元素数目共有解：该数组的元素数目共有5*4=20个。个。 由于由于C语言采用行序为主序的存储方式，则有：语言采用行序为主序的存储方式，则有： LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=205616 特殊矩阵：特殊矩阵：非零元素或零元素的分

11、布有一定非零元素或零元素的分布有一定规律规律 特别是在高阶矩阵的情况下，可以利用特殊特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律，对它们进行压缩存储，以便矩阵的规律，对它们进行压缩存储，以便节省节省存储空间存储空间 做法：做法：使多个相同的非零元素使多个相同的非零元素共享共享同一个存同一个存储空间，对零元素储空间，对零元素不分配不分配存储空间存储空间6.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储17 对称矩阵对称矩阵 n阶方阵阶方阵Ann 元素满足元素满足ai,j=aj,i(0i，jn-1) 对称矩阵中的元素关于主对角线对称，在存储时可对称矩阵中的元素关于主对角线对称，在存储时可只存储对

12、称矩阵中上三角或下三角中的元素，使得只存储对称矩阵中上三角或下三角中的元素，使得对对称的元素共享一个存储空间。称的元素共享一个存储空间。 n2个元素个元素压缩存储压缩存储到到n(n+1)/2个元素的空间中。个元素的空间中。1、对称矩阵的压缩存储、对称矩阵的压缩存储1, 11 , 10, 11, 11 , 10, 11,01 ,00,0nnnnnnaaaaaaaaaai,i（0in-1-1）对角线对角线ai,j（ij）上三角上三角ai,j（ij）下三角下三角18 n2个元素个元素 n(n+1)/2个元素个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bk21)i(i k=+

13、 j ij+ i ij21)j(j k= 0 1 2 3 2) 1( nn12) 1(nn以行序为主序存储其下三角的元素以行序为主序存储其下三角的元素a00a10a11a20an-1,0an-1,n-119上三角矩阵：上三角矩阵： 2)12(* ini2)1( nnk=+ j i ij时时ij时时下三角矩阵：下三角矩阵： jii2)1(* 2)1( nnk= ij时时ij时时1, 11, 11 , 11,01 ,00,0nnnnaaaaaac1, 11 ,0,1 , 10, 10,0nnnnaaaaaac20 2、 对角矩阵的压缩存储对角矩阵的压缩存储（略）（略） n阶对角矩阵：阶对角矩阵：n

14、阶方阵阶方阵A，满足其，满足其所有非零元素都所有非零元素都集中在以主对角线为中心的带状区域中集中在以主对角线为中心的带状区域中。 若其主对角线上下方各有若其主对角线上下方各有b条次对角线条次对角线，称，称b为为矩阵矩阵半带宽半带宽，(2b+1)为为矩阵的带宽矩阵的带宽。 对于半带宽为对于半带宽为b（0b(n-1)/2）的对角矩阵，其）的对角矩阵，其|i-j|b的元素的元素ai,j不为零，其余元素为零。不为零，其余元素为零。 . b条条 b条条 0 0 . 当当b1时称为时称为三对角矩阵三对角矩阵。其压缩地址计算公式如下：其压缩地址计算公式如下： k=2i+j 216.2 稀疏矩阵稀疏矩阵 非零

15、元素较少，分布无规律非零元素较少，分布无规律 稀疏因子：稀疏因子：= s/(m*n) = 0.05 由于分布无规律，存放非零元素由于分布无规律，存放非零元素必须同时存必须同时存放其在矩阵中的位置放其在矩阵中的位置，即下标和值一起存放，即下标和值一起存放 一个三元组唯一确定了稀疏矩阵中的一个非一个三元组唯一确定了稀疏矩阵中的一个非零元素零元素226.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 假设有一个假设有一个67阶稀疏矩阵阶稀疏矩阵A，A中元素如下中元素如下图所示。图所示。 47000000060000000500000000030000020000010076A 则对应的三元组线性表

16、为：则对应的三元组线性表为： (0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4)23稀疏矩阵的存储结构稀疏矩阵的存储结构 三元组线性表：三元组线性表： (0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4) 顺序存储结构三元组顺序表顺序存储结构三元组顺序表 链式存储结构十字链表链式存储结构十字链表 24三元组顺序表举例三元组顺序表举例 0009012700030008000000000200060A0700200000008009000003006120000Brcd01605-

17、223-831335740-12429rcd04-1210613324932-850-253725三元组顺序表三元组顺序表#define MaxSize typedef struct 三元组三元组int r,c; 非零元的行号、列号非零元的行号、列号 ElemType d; 非零元的值非零元的值 TupNode;typedef struct int rows,cols; 矩阵的行数、列数矩阵的行数、列数 int nums; /非零元个数非零元个数TupNode dataMaxSize; 三元组表三元组表TSMatrix; 下面的讨论假设按行有序存储。下面的讨论假设按行有序存储。26 (1) 从

18、一个二维稀疏矩阵创建其三元组表示从一个二维稀疏矩阵创建其三元组表示 以行序方式扫描二维矩阵以行序方式扫描二维矩阵A，将其非零的元素插入，将其非零的元素插入到三元组到三元组t的后面。的后面。 void CreatMat(TSMatrix &t,ElemType AMN) int i,j; t.rows=M; t.cols=N; t.nums=0; for (i=0;iM;i+) for (j=0;j=t.rows | j=t.cols) return false; while (kt.datak.r) k+;/*查找行查找行*/ while (kt.datak.c) k+;/*查找列查找

19、列*/ if (t.datak.r=i & t.datak.c=j) t.datak.d=x; /*存在这样的元素存在这样的元素 else /*不存在这样的元素时插入一个元素不存在这样的元素时插入一个元素*/ for (k1=t.nums-1;k1=k;k1-) /*元素后移元素后移*/ t.datak1+1.r=t.datak1.r; t.datak1+1.c=t.datak1.c; t.datak1+1.d=t.datak1.d; t.datak.r=i; t.datak.c=j; t.datak.d=x; t.nums+; return true; 29 (3) 将指定位置的元素

20、值赋给变量将指定位置的元素值赋给变量 x=Aij; 先在三元组中找到指定的位置，将其元素值赋给先在三元组中找到指定的位置，将其元素值赋给x。 bool Assign(TSMatrix t,ElemType &x,int i,int j) int k=0; if (i=t.rows | j=t.cols) return false; while (kt.datak.r) k+; while (kt.datak.c) k+; if (t.datak.r=i & t.datak.c=j) x=t.datak.d; else x=0; return true; 30 (4) 输出三元组

21、输出三元组 从头到尾扫描三元组从头到尾扫描三元组t，依次输出元素值。，依次输出元素值。 void DispMat(TSMatrix t) int i; if (t.nums=0) return;printf(“t%dt%dt%dn,t.rows,t.cols,t.nums); printf( -n); for (i=0;it.nums;i+) printf(t%dt%dt%dn,t.datai.r,t.datai.c, t.datai.d); 31 (5) 矩阵转置矩阵转置 对于一个对于一个mn的矩阵的矩阵Amn,其转置矩阵是一个其转置矩阵是一个nm的矩阵。的矩阵。设为设为Bnm,满足满足ai

22、,j=bj,i,其中其中0im-1,0jn-1。 0009012700030008000000000200060A0700200000008009000003006120000Brcd01605-223-831335740-12429rcd04-1210613324932-850-253732void TranTat(TSMatrix t,TSMatrix &tb) int p,q=0,v; /*q为为tb.data的下标的下标*/ tb.rows=t.cols; tb.cols=t.rows; tb.nums=t.nums; if (t.nums!=0) for (v=0;vt.co

23、ls;v+) for (p=0;p(N)?(M):(N) /*矩阵行列较大者矩阵行列较大者*/typedef struct mtxn int row; /*行号行号*/ int col;/*列号列号*/ struct mtxn *right,*down;/*向右和向下的指针向右和向下的指针*/ union int value; struct mtxn *link; tag; MatNode;/*十字链表类型定义十字链表类型定义*/38 6.3.1 广义表的定义广义表的定义广义表广义表简称表简称表，它是线性表的推广。，它是线性表的推广。一个广义表是一个广义表是n(n0)个元素的一个序列，若个元素

24、的一个序列，若n=0时时则称为空表。则称为空表。设设ai为广义表的第为广义表的第i个元素，则广义表个元素，则广义表GL的一般表的一般表示与线性表相同：示与线性表相同： GL=(a1,a2,ai,an)其中其中n表示广义表的长度，即广义表中表示广义表的长度，即广义表中所含元素的所含元素的个数个数，n0。如果如果ai是单个数据元素，则是单个数据元素，则ai是广义表是广义表GL的的原子；原子；如果如果ai是一个广义表，则是一个广义表，则ai是广义表是广义表GL的的子表。子表。 6.3 广义表广义表 39 (1)广义表中的数据元素有相对次序；广义表中的数据元素有相对次序； (2)广义表的长度定义为广义

25、表的长度定义为最外层最外层包含元素个数；包含元素个数； (3)广义表的深度定义为所含括弧的重数。其中，原子的深广义表的深度定义为所含括弧的重数。其中，原子的深度为度为0，空表的深度为，空表的深度为1； (4)广义表可以广义表可以共享共享；一个广义表可以为其他广义表共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；这种共享广义表称为再入表； (5)广义表可以是一个广义表可以是一个递归递归的表。一个广义表可以是自已的的表。一个广义表可以是自已的子表。这种广义表称为递归表。子表。这种广义表称为递归表。递归表的深度是无穷值，长递归表的深度是无穷值，长度是有限值度是有限值； (6)任何一个

26、非空广义表任何一个非空广义表GL均可分解为均可分解为表头表头head(GL) = a1和和表尾表尾tail(GL) = ( a2,an) 两部分。两部分。 广义表的特性广义表的特性40我们规定用小写字母表示原子，用大写字母表我们规定用小写字母表示原子，用大写字母表示广义表的表名。示广义表的表名。例如：例如： A=() B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c)分别求出上述各表的分别求出上述各表的表头、表尾、表头、表尾、深度和长度。深度和长度。 长度：长度：最外层最外层包含元素个数包含元素个数 深度：所含括

27、弧的深度：所含括弧的重数重数416.3.2 广义表的存储结构广义表的存储结构顺序存储结构：顺序存储结构：不能；不能；分析原因：分析原因： 1）广义表中的数据元素可以具有广义表中的数据元素可以具有不同的结构不同的结构； 2）广义表可以递归，广义表可以递归，很难分配很难分配固定大小的存储空间固定大小的存储空间链式存储结构链式存储结构关键是结点的定义关键是结点的定义 一类是单个元素结点，即一类是单个元素结点，即原子结点原子结点 一类是一类是子表结点子表结点42 每一个广义表的链式存储结构都有头结点，每一个广义表的链式存储结构都有头结点，且该头结点一定是一个表结点；且该头结点一定是一个表结点； 一个空

28、列表也存在头结点，结点的两个指针一个空列表也存在头结点，结点的两个指针域为域为NULL；广义表的存储结构广义表的存储结构-子表分析法子表分析法u结点结构结点结构子表结点子表结点tag=1sublistlink原子结点原子结点tag=0datalink指向该子表的第指向该子表的第一个结点一个结点指向该子表的下指向该子表的下一个结点一个结点43广义表的两种基本情况广义表的两种基本情况 为原子的情况为原子的情况 ： g3 0 a g1 1 g2 1 * * * * * * 第 1 个元素 第 2 个元素 第 n 个元素 空表空表 非空表非空表44例例 1 C=(a,(b,c,d) C a b c d

29、 C a b c d C 1 0 a 1 0 b 0 c 0 d 45例例 2A=( ) B=(e,f) C=(a,(b,c) D=(B,A,C) E=(a,E)1011000111ebca1111ABCDE0a0fw 结点结构结点结构子表结点子表结点tag=1hptptag=0atom原子结点原子结点广义表的链式存储结构广义表的链式存储结构 2 表头、表尾分析法表头、表尾分析法 任何一个非空的广义表都可以分解成表头和表尾两任何一个非空的广义表都可以分解成表头和表尾两部分，反之，一对确定的表头和表尾可唯一确定一部分，反之，一对确定的表头和表尾可唯一确定一个广义表个广义表 表尾是一个列表，表头可

30、以是原子，也可以是列表表尾是一个列表，表头可以是原子，也可以是列表广义表的链式存储结构广义表的链式存储结构 2B1011111111100001efabc0aCDEAA=( ) B=(e,f) C=(a,(b,c) D=(B,A,C) E=(a,E)练练 习习 画出下列广义表的两种存储结构图画出下列广义表的两种存储结构图( ),a,(b,(c,d),(e,f)49(1) 求广义表的长度求广义表的长度 在广义表中在广义表中,同一层次的每个结点是通过同一层次的每个结点是通过link域链接起来的域链接起来的,所以可把它看做是由所以可把它看做是由link域链接起来的单链表。这样，求广义域链接起来的单链

31、表。这样，求广义表的长度就是求单链表的长度。表的长度就是求单链表的长度。求广义表长度的非递归算法如下：求广义表长度的非递归算法如下： int GLLength(GLNode *g) /g为一个广义表头结点的指针为一个广义表头结点的指针 int n=0; g=g-val.sublist; /g指向广义表的第一个元素指向广义表的第一个元素 while (g!=NULL) n+; g=g-link; return n; 6.3.3 广义表的运算（略）广义表的运算（略）50对于带头结点的广义表对于带头结点的广义表g,广义表深度的递归定义广义表深度的递归定义是它等于所有子表中表的最大深度加是它等于所有子表中表的最大深度加1。若。若g为原子为原子,其深度为其深度为0。求广义表深度的递归模型求广义表深度的递归模型f()如下：如下：f(g)= 0 若若g为原子为原子 1 若若g为空表为空表MAXf(subg)+1 其他情况其他情况,subg为为g的子表的子表 (2) 求广义表的深度求广义表的深度51int GLDepth(GLNode *g) /求带头结点的广义表求带头结点的广义表g的深度的深度 int max=0,dep; if (g-tag=0) return 0; /为原子时返回为原子时返回0 g=g-val.sub