数据结构第5章 数组和广义表

1、2017/10/1912017/10/192第第5章章 数组和广义表数组和广义表 前面前面4章介绍的数据结构的共同特点章介绍的数据结构的共同特点： (1) 都属于线性数据结构；都属于线性数据结构； (2) 每种数据结构中的数据元素，都作为原子数据，不再每种数据结构中的数据元素，都作为原子数据，不再进行分解。进行分解。 本章讨论的两种数据结构本章讨论的两种数据结构：数组和广义表数组和广义表，其共同特点是：，其共同特点是： (1) 从逻辑结构上看它们，可看成是线性结构的一种扩展；从逻辑结构上看它们，可看成是线性结构的一种扩展； (2) 数据结构元素本身也是一种数据结构。数据结构元素本身也是一种数据

2、结构。2017/10/1935.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.5 广义表的存储结构广义表的存储结构5.4 广义表的定义广义表的定义5.3 矩阵的压缩存储矩阵的压缩存储第第5章章 数组和广义表数组和广义表2017/10/194 数组：数组：按一定格式排列起来的按一定格式排列起来的 具有具有的数据元素的集合。的数据元素的集合。 一维数组：一维数组：若线性表中的数据元素为非结构的简单若线性表中的数据元素为非结构的简单 元素，则称为一维数组。元素，则称为一维数组。 一维数组的逻辑结构：一维数组的逻辑结构：线性结构。定长的线性表。线性结构。定长的线性表。 5

3、.1 数组的定义数组的定义2017/10/195191817161514131211109876543210num45 二维数组：二维数组：若一维数组中的数据元素又是一维数组结构，若一维数组中的数据元素又是一维数组结构， 则称为二维数组。则称为二维数组。 非线性结构非线性结构 num5 = 0，1， 2，3，4; A=( 0, 1, p) (p = m-1 or n-1) j=(a0j,a1j,am-1,j) 0jn-1 i=(ai0,ai1,ai,n-1) 0im-1 二维数组逻辑结构二维数组逻辑结构 线性结构线性结构定长的线性表定长的线性表每一个数据元素每一个数据元素 既在一个行表中，既在

4、一个行表中， 又在一个列表中。又在一个列表中。 该线性表的每个数据元素该线性表的每个数据元素 也是一个定长的线性表。也是一个定长的线性表。 1, 12 , 11 , 10 , 11, 11211101, 0020100nmmmmnnnmaaaaaaaaaaaaA5.1 数组的定义数组的定义2017/10/196 三维数组：三维数组：若二维数组中的元素又是一个一维数组若二维数组中的元素又是一个一维数组 结构，则称作三维数组。结构，则称作三维数组。 n 维数组：维数组：若若 n -1 维数组中的元素又是一个一维数维数组中的元素又是一个一维数 组结构，则称作组结构，则称作 n 维数组。维数组。 数组

5、特点：数组特点：定义后维数和维界不再改变。定义后维数和维界不再改变。 数组基本操作：数组基本操作：除了结构的初始化和销毁之外，除了结构的初始化和销毁之外， 只有存取元素和修改元素值的操作。只有存取元素和修改元素值的操作。 5.1 数组的定义数组的定义2017/10/197数组的抽象数据类型的定义数组的抽象数据类型的定义 ADT Array 数据对象：数据对象：D=aj1 j2 jn | ji = 0, ., bi -1, i = 1, 2, ., n, n (0) 称为数组的维数，称为数组的维数， bi 是数组第是数组第 i 维的长度，维的长度， ji 是数组元素的第是数组元素的第 i 维下标

6、，维下标， a j1 j2 jnElemSet 数据关系：数据关系：RR1, R2, ., Rn Ri |0jkbk -1, 1kn 且且 ki, 0jibi - 2, aj1jijn , aj1ji+1jnD, i = 2, ., n 共有多少个对象？共有多少个对象？5.1 数组的定义数组的定义2017/10/198数据对象数据对象: : D = aij | 0 i b1 - 1, 0 j b2 - 1 数据关系数据关系: : R = ROW, COL ROW = | 0 i b1 - 2, 0 j b2 - 1 COL = | 0 i b1 - 1, 0 j b2 - 2二维数组的抽象数据

7、类型的数据对象和数据关系的定义二维数组的抽象数据类型的数据对象和数据关系的定义 5.1 数组的定义数组的定义2017/10/199基本操作：基本操作： InitArray(&A, n, bound1, ., boundn) 操作结果：操作结果：若维数若维数 n 和各维长度合法，则构造相应的和各维长度合法，则构造相应的 数组数组 A，并返回，并返回 OK。 DestroyArray(&A) 操作结果：操作结果：销毁数组销毁数组 A。 Value(A, &e, index1, ., indexn) 初始条件：初始条件：A 是是 n 维数组，维数组，e 为元素变量。为元素变量。 操作结果：操作结果：

8、若各下标不超界，则若各下标不超界，则 e 赋值为所指定的赋值为所指定的 A 的元素值，并返回的元素值，并返回 OK。 Assign(&A, e, index1, ., indexn) 初始条件：初始条件：A 是是 n 维数组，维数组，e 为元素变量。为元素变量。 操作结果：操作结果：若下标不超界，则将若下标不超界，则将 e 的值赋给所指定的的值赋给所指定的 A 的元素，并返回的元素，并返回 OK。 ADT Array 5.1 数组的定义数组的定义2017/10/19105.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.5 广义表的存储结构广义表的存储结构5.4 广

9、义表的定义广义表的定义5.3 矩阵的压缩存储矩阵的压缩存储第第5章章 数组和广义表数组和广义表2017/10/1911数组特点：数组特点：维数和维界不变。维数和维界不变。 数组基本操作：数组基本操作：初始化、销毁、取元素、改元素值。初始化、销毁、取元素、改元素值。 一般不做插入和删除操作。一般不做插入和删除操作。 一般都是采用一般都是采用顺序存储结构顺序存储结构来表示数组。来表示数组。 数组可以是多维的，但存储数据元素的内存单元数组可以是多维的，但存储数据元素的内存单元 地址是一维的，因此，在存储数组结构之前，需地址是一维的，因此，在存储数组结构之前，需 要解决将多维关系映射到一维关系的问题。

10、要解决将多维关系映射到一维关系的问题。 以行序为主序以行序为主序 (低下标优先低下标优先) BASIC、COBOL和和PASCAL 以列序为主序以列序为主序 (高下标优先高下标优先) FORTRAN 5.2 数组的顺序表示和实现数组的顺序表示和实现2017/10/1912以行序为主序存放：以行序为主序存放： . a1, n-1 . a11 a10 a0, n-1 . a01 a0001n -1m*n -1n二维数组中任一元素二维数组中任一元素 aij 的存储位置的存储位置 LOC(i, j) = LOC(0, 0) + (b2ij )L 某个元素的地址就是它前面所有行某个元素的地址就是它前面所

11、有行 所占的单元加上它所在行前面所有列元所占的单元加上它所在行前面所有列元 素所占的单元数之和。素所占的单元数之和。 基地址或基址基地址或基址 二维数组的映象函数二维数组的映象函数 a00 a01 . a0, n-1 a10 a11 . a1, n-1 .5.2 数组的顺序表示和实现数组的顺序表示和实现2017/10/1913以列序为主序存放以列序为主序存放 01m -1m*n -1mam-1, n-1. a1, n-1a0, n-1 . am-1, 1 . a11 a01 a01 . a0, n-1 a11 . a1, n-1 am-1, 1 . am-1, n-1 .二维数组中任一元素二维

12、数组中任一元素 aij 的存储位置的存储位置 LOC(i, j) = LOC(0, 0) + (b1ji )L 某个元素的地址就是它前面所有列某个元素的地址就是它前面所有列 所占的单元加上它所在列前面所有行元所占的单元加上它所在列前面所有行元 素所占的单元数之和。素所占的单元数之和。 5.2 数组的顺序表示和实现数组的顺序表示和实现2017/10/1914同理，对三维数组同理，对三维数组Ab1b2b3,可以看成可以看成b1个个b2 b3的二维数组，的二维数组，若首元素的存储地址为若首元素的存储地址为LOC0,0,0,则元素则元素ai00的存储地址为的存储地址为LOC(i,0,0)=LOC(0,

13、0,0)+(i b2 b3)*L这是因为该元素之前有这是因为该元素之前有i个个b2 b3的二维数组，所以的二维数组，所以LOC(i,j,k)=LOC(0,0,0)+(i b2 b3 +j b3 +k)*L推广到一般情况，可得到推广到一般情况，可得到 n 维数组数据元素存储位置的映像关系维数组数据元素存储位置的映像关系LOC(j1,j2,jn)=LOC(0,0,0)+(b2bnj1+ b3bnj2+bn jn-1+ jn) L 称为称为 n 维数组的映像函数。维数组的映像函数。数组元素的存储位置是其下标数组元素的存储位置是其下标的线性函数的线性函数5.2 数组的顺序表示和实现数组的顺序表示和实现

14、2017/10/1915例例 1：一个二维数组：一个二维数组 A，行下标的范围是，行下标的范围是 1 到到 6，列，列 下标的范围是下标的范围是 0 到到 7，每个数组元素用相邻的，每个数组元素用相邻的 6 个字节存储，存储器按字节编址。那么，这个字节存储，存储器按字节编址。那么，这 个数组的体积是个数组的体积是 个字节。个字节。 答：答： Volume = mnL = (6 1 + 1) (7 0 + 1) 6 = 486 = 288 5.2 数组的顺序表示和实现数组的顺序表示和实现2017/10/1916例例 2： 设数组设数组 A059, 069 的基地址为的基地址为 2048，每个元，

15、每个元 素占素占 2 个存储单元，若个存储单元，若以列序为主序以列序为主序顺序存储，则元素顺序存储，则元素 a31, 57 的存储地址为的存储地址为 。 解：解：LOC(i, j) = LOC(31, 57) = LOC(0, 0)+(b1ji )L = 2048 + (605731 )2 = 8950 a00 a01 a0, 69 a10 a11 a1, 69 a59, 0 a59, 1 a59, 69 a31, 57 5.2 数组的顺序表示和实现数组的顺序表示和实现2017/10/19175.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.5 广义表的存储结构广

16、义表的存储结构5.4 广义表的定义广义表的定义5.3 矩阵的压缩存储矩阵的压缩存储第第5章章 数组和广义表数组和广义表2017/10/1918 矩阵定义矩阵定义：一个由一个由 mn 个元素排成的个元素排成的 m 行（横向）行（横向） n 列（纵向）的表。列（纵向）的表。 mnmmnnaaaaaaaaa.212222111211 矩阵的常规存储：矩阵的常规存储： 将矩阵描述为一个二维数组。将矩阵描述为一个二维数组。 矩阵的常规存储的特点：矩阵的常规存储的特点： 可以对其元素进行随机存取；可以对其元素进行随机存取； 矩阵运算非常简单；存储的密度为矩阵运算非常简单；存储的密度为 1。 不适宜常规存储

17、的矩阵：不适宜常规存储的矩阵：值相同的元素很多且呈某种值相同的元素很多且呈某种 规律分布；零元素多。规律分布；零元素多。 矩阵的压缩存储：矩阵的压缩存储：为多个相同的非零元素只分配一个为多个相同的非零元素只分配一个 存储空间；对零元素不分配空间。存储空间；对零元素不分配空间。 5.3 矩阵的压缩存储矩阵的压缩存储2017/10/1919 特殊矩阵：特殊矩阵：元素值的排列具有一定规律的矩阵。元素值的排列具有一定规律的矩阵。 对称矩阵、下、上三角矩阵、对角线矩阵等对称矩阵、下、上三角矩阵、对角线矩阵等 1、对称矩阵 在一个 n 阶方阵 A 中，若元素满足下述性质： aij = aji 1 i, j

18、 n 则称 A 为对称矩阵。 3160715203629810080573151nnnnnnaaaaaaaaa.2122212121115.3 矩阵的压缩存储矩阵的压缩存储-特殊矩阵特殊矩阵2017/10/1920对称矩阵上下三角中的元素数均为：对称矩阵上下三角中的元素数均为： n(n + 1)/2 ?可可以行序以行序为主序将元素存放在一为主序将元素存放在一 个一维数组个一维数组 san(n+1)/2 中。中。 nnnnnnaaaaaaaaa212222111211对称矩阵的存储结构对称矩阵的存储结构 k = 0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 以行序为主序存储下三角：

19、以行序为主序存储下三角： a11a21a22a31a32 an1ann5.3 矩阵的压缩存储矩阵的压缩存储-特殊矩阵特殊矩阵2017/10/1921 则则 aij 和和 sak 存在着存在着一一对应关系一一对应关系： jiijjjijiik 12)1( 12)1(当当当当aij 前的前的 i -1 行有行有 1+2+ (i -1)= i(i -1)/2 个元素，在个元素，在 第第 i 行上有行上有 j 个元素。个元素。 因为因为aij = aji，所以只要交，所以只要交 换关系式中的换关系式中的 i 和和 j 即可。即可。 nnnnnnaaaaaaaaa212222111211k= 0 1 2

20、 3 n(n-1)/2 以行序为主序存储下三角：以行序为主序存储下三角： a11a21a22a31an1ann 5.3 矩阵的压缩存储矩阵的压缩存储-特殊矩阵特殊矩阵2017/10/1922 2、三角矩阵三角矩阵 以主对角线划分，三角矩阵有上（以主对角线划分，三角矩阵有上（下下）三角两种。）三角两种。 上（上（下下）三角矩阵的下（）三角矩阵的下（上上）三角（不含主对角线）中）三角（不含主对角线）中 的元素均为常数。在大多数情况下，三角矩阵常数为零。的元素均为常数。在大多数情况下，三角矩阵常数为零。 nnnnaccaacaaa22211211nnnnaaacaacca21222111上三角矩阵上

21、三角矩阵下三角矩阵下三角矩阵 三角矩阵的存储：三角矩阵的存储：除了存储主对角线及上（除了存储主对角线及上（下下）三）三 角中的元素外，再加一个存储常数角中的元素外，再加一个存储常数 c 的空间。的空间。 5.3 矩阵的压缩存储矩阵的压缩存储-特殊矩阵特殊矩阵2017/10/1923 3、 对角矩阵对角矩阵 对角矩阵可按行优先顺序或对角线的顺序，将其压对角矩阵可按行优先顺序或对角线的顺序，将其压 缩存储到一维数组中，且也能找到每个非零元素和向量缩存储到一维数组中，且也能找到每个非零元素和向量 下标的对应关系。下标的对应关系。 nnnnnnaaaaaaaa1, 12322211211005.3 矩

22、阵的压缩存储矩阵的压缩存储-特殊矩阵特殊矩阵2017/10/1924设在 mn 的矩阵中有 t 个非零元素。 令 = t /(mn) 当 0.05 时称为。 存各非零元的值、行列位置和矩阵的行列数。存各非零元的值、行列位置和矩阵的行列数。 00070015000001800000240001400003000000000009120MM 由由 (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) 唯一确定唯一确定。 三元组三元组 (i, j, aij) 惟一

23、确定矩阵的惟一确定矩阵的一个非零元。一个非零元。 三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。 压缩比压缩比5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/192500070015000001800000240001400003000000000009120M#define MAXSIZE 12500 /假设非零元个数的最大值假设非零元个数的最大值 typedef struct int i, j; /该非零元的行列下标该非零元的行列下标 Elemtype e; Triple; typedef struct T

24、riple dataMAXSIZE + 1; int mu, nu, tu; /矩阵的行、列数和非零元个数矩阵的行、列数和非零元个数 TSMatrix;i j tu 0 1 2 3 4 5 6 7 8 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法顺序存储结构顺序存储结构 1、三元组顺序表、三元组顺序表 6 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -75.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1926 一个 mn 的矩阵 M，它的转置 T 是一个 nm 的矩阵，且 T (i, j) = M j, i，1i

25、n，1jm， 即 M 的行是 T 的列，M 的列是 T 的行。 求转置矩阵求转置矩阵 00070015000001800000240001400003000000000009120M00000000014000000007000000024009018000121500300T5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/192700070015000001800000240001400003000000000009120M00000000014000000007000000024009018000121500300T 已知一个稀疏矩阵的三元组表，求该矩阵已知一个稀疏矩

26、阵的三元组表，求该矩阵 转置矩阵的三元组表。转置矩阵的三元组表。 i j tu 0 1 2 3 4 5 6 7 8 6 1 212 1 3 9 3 1 -3 3 614 4 3 24 5 218 6 115 6 4 -7 解决思路：解决思路： 将矩阵行、列将矩阵行、列 维数互换维数互换 将每个三元组将每个三元组 中的中的 i 和和 j 相相 互调换互调换 重排三元组次重排三元组次 序，使序，使 T.data 中元素以中元素以 T 的的 行行 (M的列的列) 为为 主序。主序。 M.data i j tu 0 1 2 3 4 5 6 7 8 7 1 3 -3 1 615 2 112 2 518

27、3 1 9 3 424 4 6 -7 6 314T.data T.data i j tu 0 1 2 3 4 5 6 7 8 7 2 1 12 3 1 9 1 3 -3 6 3 14 3 4 24 2 5 18 1 6 15 4 6 -7 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1928方法一：方法一： 7 6 1 212 1 3 9 3 1 -3 3 614 4 3 24 5 218 6 115 6 4 -7T.data M.data 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 for (p =

28、1; p = ; + p) if ( M.datap.j = col ) T.dataq.i = M.datap.j ; T.dataq.j = M.datap.i ; T.dataq.e = M.datap.e; + q; q=1 /从第一个存储位置开始寻找从第一个存储位置开始寻找for (col = 1; col = ; + col) for (p = 1; p = ; + p) if ( M.datap.j = col ) T.dataq.i = M.datap.j ; T.dataq.j = M.datap.i ; T.dataq.e = M.datap.e; + q; 5.3 矩阵的

29、压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1929typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; /行、列、非零元数行、列、非零元数 TSMatrix; Status TransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q = 1; for (col = 1; col = ; + col) for (p = 1; p = ; + p) if ( M.datap.j = col ) T.dataq.i =

30、 M.datap.j ; T.dataq.j = M.datap.i ; T.dataq.e = M.datap.e; + q; return OK; / TransposeSMatrix 时间复杂度：时间复杂度：O(nu tu) 若若 tu 与与mu nu 同数量级同数量级? 则为：则为：O(mu nu2) 6 1 212 1 3 9 3 1 -3 3 614 4 3 24 5 218 6 115 6 4 -71 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 6 q p p q p q p 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏

31、矩阵稀疏矩阵2017/10/1930for (col = 1; col = nu; + col) for (row = 1; row = mu; + row) Tcolrow = Mrowcol; 一般矩阵转置算法：一般矩阵转置算法：一般矩阵转置算法时间复杂度：一般矩阵转置算法时间复杂度：O(mu ) 用三元组顺序表存储用三元组顺序表存储的矩阵转置算法的矩阵转置算法时间复杂度：时间复杂度：O(nu tu) 若若 tu 与与mu nu 同数量级，则为：同数量级，则为：O(mu ) 算法仅适用于算法仅适用于 tu mu nu 的情况。的情况。 用三元组顺序表存储稀疏用三元组顺序表存储稀疏矩阵节约存

32、储空间（矩阵节约存储空间（优点优点）；）； tu与与mu nu同数量级同数量级时，时，算法时间复杂度高（算法时间复杂度高（）；）； 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1931方法方法 2： 7 1 3 -3 1 615 2 112 2 518 3 1 9 3 424 4 6 -7 6 314 6 1 212 1 3 9 3 1 -3 3 614 4 3 24 5 218 6 115 6 4 -7T.data M.data 实施步骤：实施步骤： 1、确定、确定 M 的第的第 1 列的第列的第 1 个非零元在个非零元在 T.data 中的位置。中的位置。 3、确

33、定、确定 M 的第的第 col 列的第一个非零元在列的第一个非零元在 T.data 中的位置。中的位置。 2、确定、确定 M 的第的第 col -1 列的非零元个数。列的非零元个数。 存入数组存入数组 numM.nu 存入数组存入数组 cpotM.nu cpot1 = 1; cpotcol=cpotcol1+numcol1 2cola.nu col 1 2 3 4 5 6 7 num(col) 2 2 2 1 0 1 0 cpot(col) 1 3 5 7 8 8 9 col 1 2 3 4 5 6 7 num(col) 2 2 2 1 0 1 0 cpot(col) 5.3 矩阵的压缩存储矩

34、阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1932Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T ) / 采用三元组顺序表存储表示，求稀疏矩阵采用三元组顺序表存储表示，求稀疏矩阵 M 的转置矩阵的转置矩阵 T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) + numM.datat.j; / 求求 M 中各列非零元的个数中各列非零元的个数 cpot1 = 1;

35、for (col=2; col=M.nu; +col) cpotcol = cpotcol -1 + numcol -1; / 求求 M 中各列的第一个非零元在中各列的第一个非零元在 T.data 中的序号中的序号 6 1 212 1 3 9 3 1 -3 3 614 4 3 24 5 218 6 115 6 4 -7 col 1 2 3 4 5 6 7 num(col) cpot(col) 60 0 0 0 0 0 0 1 1 1 1 2 2 2 1 1 3 5 7 8 8 9 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1933 for (p=1; p=M.tu;

36、 +p) / 转置矩阵元素转置矩阵元素 col = M.datap.j; q = cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; + cpotcol; / for / if return OK; / FastTransposeSMatrix 6 1 212 1 3 9 3 1 -3 3 614 4 3 24 5 218 6 115 6 4 -7 col 1 2 3 4 5 6 7 num(col) 2 2 2 1 0 1 0 cpot(col) 1 3 5 7 8 8 962 1 12

37、4 3 1 9 6 1 3 -3 2 6 3 14 9 3 4 24 7 2 5 18 5 1 6 15 3 4 6 -7 8 0 12345678 0 12345678 pqpqpqpqpqpqpqpq00000000014000000007000000024009018000121500300T5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1934Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T ) / 采用三元组顺序表存储表示，求稀疏矩阵采用三元组顺序表存储表示，求稀疏矩阵 M 的转置矩阵的转置矩阵 T T.

38、mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) + numM.datat.j; / 求求 M 中各列非零元的个数中各列非零元的个数 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol -1 + numcol -1; / 求求 M 中各列的第一个非零元在中各列的第一个非零元在 T.data 中的序号中的序号 for (p=1; p=M.tu; +p) / 转置矩阵元素

39、转置矩阵元素 col = M.datap.j; q = cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; + cpotcol; / for / if return OK; / FastTransposeSMatrix时间复杂度为时间复杂度为: O(nu + tu) 若若 tu 与与mu nu 同数量级，则为：同数量级，则为： 与经典算与经典算 法相同。法相同。 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1935 三元组顺序表又称三元组顺序表又称。 三元组顺序表的

40、三元组顺序表的：非零元在表中按行序有序存储，：非零元在表中按行序有序存储，因此因此。 三元组顺序表的三元组顺序表的：不能：不能随机随机存取存取。若按行号存取某。若按行号存取某 一行中的非零元，则需从头开始进行查找。一行中的非零元，则需从头开始进行查找。 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1936 2、行逻辑联接的顺序表（带行表的三元组）、行逻辑联接的顺序表（带行表的三元组） 在稀疏矩阵中若在稀疏矩阵中若随机存取随机存取任意一行的非零元任意一行的非零元 7 1 3 -3 1 615 2 112 2 518 3 1 9 3 424 4 6 -7 6 314 co

41、l 1 2 3 4 5 6 7 num(col) 2 2 2 1 0 1 0 cpot(col) 1 3 5 7 8 8 9在存储三元组表的同时存储一个行表在存储三元组表的同时存储一个行表 rpos （快速转置算法中（快速转置算法中“带行链接信息带行链接信息”的的 cpot ） 需知道每行首个非零元在三元组表中的位置需知道每行首个非零元在三元组表中的位置 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/19373、稀疏矩阵的链式存储结构：十字链表、稀疏矩阵的链式存储结构：十字链表它能够灵活地它能够灵活地插入插入因运算而产生的因运算而产生的新新的的非零元素非零元素， 因运算

42、而产生的因运算而产生的的的，实现矩阵的运算。，实现矩阵的运算。 在十字链表中，矩阵的每一个非零元素用一个结点在十字链表中，矩阵的每一个非零元素用一个结点 表示，该结点除了（表示，该结点除了（row，col，value）外，还有两个域：）外，还有两个域： right： 用于链接同一行中的下一个非零元素；用于链接同一行中的下一个非零元素； down：用以链接同一列中的下一个非零元素。：用以链接同一列中的下一个非零元素。 rowcolvaluedownright十字链表中结点的结构示意图：十字链表中结点的结构示意图： 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1938 0

43、050000 10 203M11314531222-1 M.rhead M.chead 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/1939 04020 21 0 N21112231-2324 M.rhead M.chead 5.3 矩阵的压缩存储矩阵的压缩存储-稀疏矩阵稀疏矩阵2017/10/19405.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.5 广义表的存储结构广义表的存储结构5.4 广义表的定义广义表的定义5.3 矩阵的压缩存储矩阵的压缩存储第第5章章 数组和广义表数组和广义表2017/10/1941 广义表广义表（又称（又称

44、列表列表 Lists）是是n0个元素个元素 a0, a1, , an-1 的有限序列，其中每一个的有限序列，其中每一个ai 或者是或者是原子原子，或者是一个，或者是一个子表子表。 例：例：中国举办的国际足球邀请赛，参赛队名单可表示如下：中国举办的国际足球邀请赛，参赛队名单可表示如下： （阿根廷，巴西，德国，法国，阿根廷，巴西，德国，法国，（ ），西班牙，西班牙， 意大利，英国，意大利，英国，（国家队，鲁能，实德国家队，鲁能，实德） 在这个表中，韩国队应排在法国队后面，但由于其水平在这个表中，韩国队应排在法国队后面，但由于其水平 低未敢参加，成为空表。国家队、鲁能队、实德队均作为东低未敢参加，成

45、为空表。国家队、鲁能队、实德队均作为东 道主的参赛队参加，构成一个小的线性表，成为原线性表的道主的参赛队参加，构成一个小的线性表，成为原线性表的 一个数据元素。这种一个数据元素。这种。 单个单个元素元素 5.4 广义表的定义广义表的定义2017/10/1942广义表广义表通常记作：通常记作： LS = (a1，a2，an) 其中：其中： LS 为表名，为表名， n 为表的长度，为表的长度， 每一个每一个 ai 为表的元素。为表的元素。 习惯上，一般用习惯上，一般用表示表示，小写字母小写字母表示表示原子原子。 表头表头：若若 LS 非空非空 (n1 )，则其，则其第一个第一个元素元素 a1 就是

46、表头。就是表头。 记作记作 head(LS) = a1。表头可是原子，也可是子表。表头可是原子，也可是子表。 表尾表尾：除表头之外的除表头之外的其它元素其它元素组成的组成的表表。 记作记作 tail(LS) = (a2, ., an)。 表尾不是最后一个元素，而是一个子表。表尾不是最后一个元素，而是一个子表。 5.4 广义表的定义广义表的定义2017/10/1943(1) A=( ) 例：例： 空表，长度为空表，长度为 0。 (2) B=( ) (3) C=(a, (b, c) 长度为长度为 1，表头、表尾均为，表头、表尾均为 ( )。 长度为长度为 2，由原子，由原子 a 和子表和子表 (b

47、, c) 构成。构成。 (4) D=(x, y, z) 表头为表头为 a ；表尾为；表尾为 (b, c)。 长度为长度为 3，每一项都是原子。，每一项都是原子。 (5) E=(C, D) 表头为表头为 x ；表尾为；表尾为 (y, z)。 (6) F=(a, F) 长度为长度为 2，每一项都是子表。，每一项都是子表。 表头为表头为 C ；表尾为；表尾为 (D)。 长度为长度为 2，第一项为原子第二项为它本身。，第一项为原子第二项为它本身。 F=(a, (a, (a, ) 表头为表头为 a ；表尾为；表尾为 (F)。 5.4 广义表的定义广义表的定义2017/10/1944广义表的性质广义表的性

48、质 (1) 广义表中的数据元素有相对广义表中的数据元素有相对； (2) 广义表的广义表的定义为最外层所包含元素的个数；定义为最外层所包含元素的个数； 如：如： C=(a, (b, c) 是长度为是长度为 2 的广义表。的广义表。 (3) 广义表的广义表的定义为该广义表定义为该广义表展开后展开后所含所含括号的重数括号的重数； A = (b, c) 的深度为的深度为 1，B = (A, d) 的深度为的深度为 2， C = (f, B, h) 的深度为的深度为 3。 “原子原子”的深度为的深度为 ; “空表空表”的深度为的深度为 。 (4) 广广义表可以为其他广义表义表可以为其他广义表；如：广义表

49、；如：广义表 B 就共享就共享 表表 A。在。在 B 中不必列出中不必列出 A 的值，而是通过名称来引用。的值，而是通过名称来引用。 (5) 广义表可以是广义表可以是的表。如：的表。如：F=(a, F)=(a, (a, (a, ) 递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值。5.4 广义表的定义广义表的定义2017/10/1945(6) 广义表是广义表是结构，广义表的元素可以是单元素，结构，广义表的元素可以是单元素， 也可以是子表，而子表的元素还可以是子表，也可以是子表，而子表的元素还可以是子表，。 可以用图形象地表示。可以用图形象地表示。 例：例： D=(E, F)

50、 其中其中： E=(a, (b, c) F=(d, (e) DadbceEF5.4 广义表的定义广义表的定义2017/10/1946 广义表广义表可看成可看成是线性表的推广是线性表的推广，线性表是广义表的特例线性表是广义表的特例。 广义表的结构相当灵活，在某种前提下，它可以兼容线广义表的结构相当灵活，在某种前提下，它可以兼容线 性表、数组、树和有向图等各种常用的数据结构。性表、数组、树和有向图等各种常用的数据结构。 当当二维数组的每行（或每列）作为子表处理时，二维数二维数组的每行（或每列）作为子表处理时，二维数 组即为一个广义表。组即为一个广义表。 另外，树和有向图也可以用广义表来表示。另外，

51、树和有向图也可以用广义表来表示。 由于广义表不仅集中了线性表、数组、树和有向图等常由于广义表不仅集中了线性表、数组、树和有向图等常 见数据结构的特点，而且可有效地利用存储空间，因此在计见数据结构的特点，而且可有效地利用存储空间，因此在计 算机的许多应用领域都有成功使用广义表的实例。算机的许多应用领域都有成功使用广义表的实例。 5.4 广义表的定义广义表的定义2017/10/1947取表头运算取表头运算 GetHead 和取表尾运算和取表尾运算 GetTail 若广义表若广义表 LS=(a1, a2, , an)， 则则 GetHead(LS) = a1 GetTail(LS) = (a2, ,

52、 an)。 取表头得到的结果可以是原子，也可以是一个子表。取表头得到的结果可以是原子，也可以是一个子表。 取表尾得到的结果取表尾得到的结果一定一定是一个子表。是一个子表。 例例: : D = ( E, F ) = (a, (b, c)，F ) GetHead( D ) = E GetTail( D ) = ( F ) GetHead( E ) = a GetTail( E ) = (b, c) GetHead(b, c) = (b, c) GetTail(b, c) = ( ) GetHead(b, c) = b GetTail(b, c) = (c) GetHead(c) = c GetTa

53、il(c) = ( ) 广义表基本运算广义表基本运算 5.4 广义表的定义广义表的定义2017/10/194848广义表的广义表的ADT定义定义ADT Glist 数据对象数据对象： Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in 基本操作：基本操作：(p107) ADT Glist5.4 广义表的定义广义表的定义2017/10/19495.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.5 广义表的存储结构广义表的存储结构5.4 广义表的定

54、义广义表的定义5.3 矩阵的压缩存储矩阵的压缩存储第第5章章 数组和广义表数组和广义表2017/10/1950由于广义表是递归定义的由于广义表是递归定义的 其元素可具有不同的结构其元素可具有不同的结构 （原子或列表）（原子或列表） 1、首尾链表、首尾链表 广义表（不空）广义表（不空） 用顺序存储结构表示用顺序存储结构表示 采用链式存储结构采用链式存储结构 （） 首尾表示法就是根据这一性质设计的一种存储方法。首尾表示法就是根据这一性质设计的一种存储方法。 表头表头 + 表尾表尾 分解分解 确定确定 5.5 广义表的存储结构广义表的存储结构2017/10/1951 结点的结构形式结点的结构形式 标志域标志域 tag = 1指示表头的指针域指示表头的指针域 hp 指示表尾的指针域指示表尾的指针域 tp 表结点由三个域组成表结点由三个域组成 tag = 1hptp原子结点由两个域组成原子结点由两个域组成 标志域标志域 tag = 0 值域值域 atom