第+5+章+数组和广义表

1、数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中1、数组的定义和顺序存储方式；、数组的定义和顺序存储方式； 2、特殊矩阵的压缩存储；、特殊矩阵的压缩存储； 3、稀疏矩阵；、稀疏矩阵； 4、广义表的概念、表示及基本操作；、广义表的概念、表示及基本操作； 广义表存储结构的实现。广义表存储结构的实现。 教学内容教学内容 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中5.1 数组的定义数组的定义 数组：数组：

2、按一定格式排列起来的按一定格式排列起来的 具有具有的数据元素的集合。的数据元素的集合。 一维数组：一维数组：若线性表中的数据元素为非结构的简单元素，若线性表中的数据元素为非结构的简单元素， 则称为一维数组。则称为一维数组。 一维数组的逻辑结构：一维数组的逻辑结构：线性结构。定长的线性表。线性结构。定长的线性表。 声明格式：声明格式： 数据类型数据类型 变量名称变量名称长度长度； 例：例：int num5 = 0，1，2，3，4; 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中191817161514131211109876543210num45

3、 二维数组：二维数组：若一维数组中的数据元素又是一维数组结构，若一维数组中的数据元素又是一维数组结构， 则称为二维数组。则称为二维数组。 非线性结构非线性结构 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, 0020100nmmmmnnnmaaaaaaaaaaaaA数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 在在 C 语言中，一个二维数组类型也可以定义为语言中，一个二维数组类型也可以定义为 一维数组类型（其分量类型为一维数组类型），即：一维数组类型（其分量类型为一维数组类型），即： typedef elemtype array2mn; 等价于：等价于： typedef elemtype array1n; typedef array1 arr

5、ay2m; 声明格式：声明格式： 数据类型数据类型 变量名称变量名称行数行数 列数列数 ； 例：例：int num5 8 ; 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 三维数组：三维数组：若二维数组中的元素又是一个一维数组结构，若二维数组中的元素又是一个一维数组结构， 则称作三维数组。则称作三维数组。 n 维数组：维数组：若若 n -1 维数组中的元素又是一个一维数组结构，维数组中的元素又是一个一维数组结构， 则称作则称作 n 维数组。维数组。 数组特点：数组特点：定义后，维数和维界不再改变。定义后，维数和维界不再改变。 数组基本操作：数

6、组基本操作：除了结构的初始化和销毁之外，除了结构的初始化和销毁之外， 只有取元素和修改元素值的操作。只有取元素和修改元素值的操作。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中数组的抽象数据类型的定义数组的抽象数据类型的定义 ADT Array 数据对象：数据对象：Da j1 j2 jn | ji = 0, ., bi -1, i = 1, 2, ., n, n (0) 称为数组的维数，称为数组的维数， bi 是数组第是数组第 i 维的长度，维的长度， ji 是数组元素的第是数组元素的第 i 维下标，维下标， a j1 j2 jnElemSe

7、t 数据关系：数据关系：RR1, R2, ., Rn Ri |0jkbk -1, 1kn 且且 ki, 0jibi - 2, aj1jijn , aj1ji+1jnD, i = 2, ., n 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中数据对象数据对象: : 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二维数组的抽象数据类型的数据对象和数据关系的定义

8、二维数组的抽象数据类型的数据对象和数据关系的定义 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中基本操作：基本操作： InitArray(&A, n, bound1, ., boundn) 操作结果：操作结果：若维数若维数 n 和各维长度合法，则构造相应的数组和各维长度合法，则构造相应的数组 A， 并返回并返回 OK。 DestroyArray(&A) 操作结果：操作结果：销毁数组销毁数组 A。 Value(A, &e, index1, ., indexn) 初始条件：初始条件：A 是是 n 维数组，维数组，e 为元素变

9、量，随后是为元素变量，随后是 n 个下标值。个下标值。 操作结果：操作结果：若各下标不超界，则若各下标不超界，则 e 赋值为所指定的赋值为所指定的A的元素值，的元素值， 并返回并返回 OK。 Assign(&A, e, index1, ., indexn) 初始条件：初始条件：A 是是 n 维数组，维数组，e 为元素变量，随后是为元素变量，随后是 n 个下标值。个下标值。 操作结果：操作结果：若下标不超界，则将若下标不超界，则将 e 的值赋给所指定的的值赋给所指定的A的元素，的元素， 并返回并返回 OK。 ADT Array 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制

10、作：制作：计算机科学与技术系 徐振中数组特点：数组特点：维数和维界不变。维数和维界不变。 数组基本操作：数组基本操作：初始化、销毁、取元素、修改元素值。初始化、销毁、取元素、修改元素值。 5.2 数组的顺序表示和实现数组的顺序表示和实现 一般不做插入和删除操作。一般不做插入和删除操作。 一般都是采用一般都是采用顺序存储结构顺序存储结构来表示数组。来表示数组。 数组可以是多维的，但存储数据元素的内存单元地址数组可以是多维的，但存储数据元素的内存单元地址 是一维的，因此，在存储数组结构之前，需要解决将是一维的，因此，在存储数组结构之前，需要解决将 多维关系映射到一维关系的问题。多维关系映射到一维关

11、系的问题。 两种顺序存储方式两种顺序存储方式 以行序为主序以行序为主序 (低下标优先低下标优先) BASIC、COBOL和和PASCAL 以列序为主序以列序为主序 (高下标优先高下标优先) FORTRAN 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中以行序为主序存放：以行序为主序存放： . a1, n-1 . a11 a10 a0, n-1 . a01 a0001n -1m*n -1n二维数组中任一元素二维数组中任一元素 aij 的存储位置的存储位置 LOC(i, j) = LOC(0, 0) + (b2ij )L 某个元素的地址就是它前面所

12、有行某个元素的地址就是它前面所有行 所占的单元加上它所在行前面所有列元所占的单元加上它所在行前面所有列元 素所占的单元数之和。素所占的单元数之和。 基地址或基址基地址或基址 二维数组的映象函数二维数组的映象函数 a00 a01 . a0, n-1 a10 a11 . a1, n-1 .数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中按列序为主序存放按列序为主序存放 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,

13、 1 . am-1, n-1 .二维数组中任一元素二维数组中任一元素 aij 的存储位置的存储位置 LOC(i, j) = LOC(0, 0) + (b1ji )L 某个元素的地址就是它前面所有列某个元素的地址就是它前面所有列 所占的单元加上它所在列前面所有行元所占的单元加上它所在列前面所有行元 素所占的单元数之和。素所占的单元数之和。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中例例 1：一个二维数组：一个二维数组 A，行下标的范围是，行下标的范围是 1 到到 6，列下标，列下标 的范围是的范围是 0 到到 7，每个数组元素用相邻的，每个数

14、组元素用相邻的 6 个字节个字节 存储，存储器按字节编址。那么，这个数组的体积存储，存储器按字节编址。那么，这个数组的体积 是是 个字节。个字节。 答：答： Volume = mnL = (6 1 + 1) (7 0 + 1) 6 = 486 = 288 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中例例 2：某校计算机系考研题某校计算机系考研题 设数组设数组 A059, 069 的基地址为的基地址为 2048，每个元素占，每个元素占 2 个个 存储单元，若存储单元，若以列序为主序以列序为主序顺序存储，则元素顺序存储，则元素 A31, 57 的

15、存储的存储 地址为地址为 。 解：解：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.1 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中5.3 矩阵的压缩存储矩阵的压缩存储 矩阵定义矩阵定义：一个由一个由 mn 个元素排成的个元素排成的 m 行（横向）行（横向） n 列（纵向）的表。列（纵向）的表。 mnmmnn

16、aaaaaaaaa.212222111211 矩阵的常规存储矩阵的常规存储： 将矩阵描述为一个二维数组。将矩阵描述为一个二维数组。 矩阵的常规存储的特点矩阵的常规存储的特点： 可以对其元素进行随机存取；可以对其元素进行随机存取； 矩阵运算非常简单；存储的密度为矩阵运算非常简单；存储的密度为 1。 不适宜常规存储的矩阵：不适宜常规存储的矩阵：值相同的元素很多且呈某种规律值相同的元素很多且呈某种规律 分布；零元素多。分布；零元素多。 矩阵的压缩存储：矩阵的压缩存储：为多个相同的非零元素只分配一个存储为多个相同的非零元素只分配一个存储 空间；对零元素不分配空间。空间；对零元素不分配空间。 数据结构数

17、据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中5.3.1 特殊矩阵特殊矩阵 特殊矩阵：特殊矩阵：元素值的排列具有一定规律的矩阵。元素值的排列具有一定规律的矩阵。 对称矩阵、下（上）三角矩阵、对角线矩阵等。对称矩阵、下（上）三角矩阵、对角线矩阵等。 1、对称矩阵、对称矩阵 在一个在一个 n 阶方阵阶方阵 A 中，若元素满足下述性质：中，若元素满足下述性质： aij = aji 1 i, j n 则称则称 A 为为对称矩阵对称矩阵。 3160715203629810080573151nnnnnnaaaaaaaaa.212221212111数据结构数据结构 第

18、五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 对称矩阵上下三角中的元素数均对称矩阵上下三角中的元素数均 为：为： n(n + 1)/2 可可以行序以行序为主序将元素存放在一为主序将元素存放在一 个一维数组个一维数组 san(n+1)/2 中。中。 nnnnnnaaaaaaaaa212222111211对称矩阵的存储结构对称矩阵的存储结构 k = 0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 以行序为主序存储下三角：以行序为主序存储下三角： a11a21a22a31a32 an1ann数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制

19、作：计算机科学与技术系 徐振中 则则 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 3 4 n(n-1)/2 以行序为主序存储下三角：以行序为主序存储下三角： a11a21a2

20、2a31a32 an1ann数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 2、三角矩阵三角矩阵 以主对角线划分，三角矩阵有上（以主对角线划分，三角矩阵有上（下下）三角两种。上（）三角两种。上（下下） 三角矩阵的下（三角矩阵的下（上上）三角（不含主对角线）中的元素均为常数。）三角（不含主对角线）中的元素均为常数。 在大多数情况下，三角矩阵常数为零。在大多数情况下，三角矩阵常数为零。 nnnnaccaacaaa22211211nnnnaaacaacca21222111上三角矩阵上三角矩阵下三角矩阵下三角矩阵 三角矩阵的存储：三角矩阵的存储：除了存

21、储主对角线及上（除了存储主对角线及上（下下）三角中的元）三角中的元 素外，再加一个存储常数素外，再加一个存储常数 c 的空间。的空间。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 3、 对角矩阵对角矩阵 在对角矩阵中，所有的非零元素集中在以主对角线为中心的在对角矩阵中，所有的非零元素集中在以主对角线为中心的 带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角 线上的元素之外，其余元素皆为零。线上的元素之外，其余元素皆为零。 nnnnnnaaaaaaaa1, 12322211211

22、00 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到 一维数组中，且也能找到每个非零元素和向量下标的对应关系。一维数组中，且也能找到每个非零元素和向量下标的对应关系。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中5.3.2 稀疏矩阵稀疏矩阵 设在设在 mn 的矩阵中有的矩阵中有 t 个非零元素。个非零元素。 令令 = t /(mn) 当当 0.05 时称为时称为。 存各非零元的值、行列位置和矩阵的行列数。存各非零元的值、行列位置和矩阵的行列数。 00070015000001800000

23、240001400003000000000009120MM 由由 (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) 惟一确定矩阵的惟一确定矩阵的一个非零元。一个非零元。 三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中00070015000

24、001800000240001400003000000000009120M#define MAXSIZE 12500 /假设非零元个数的最大值假设非零元个数的最大值 typedef struct int i, j; /该非零元的行列下标该非零元的行列下标 Elemtype e; Triple; typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; /矩阵的行、列数和非零元个数矩阵的行、列数和非零元个数 TSMatrix;i j tu 0 1 2 3 4 5 6 7 8 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法顺序存储结构顺序存储结构

25、1、三元组顺序表、三元组顺序表 6 1 2 1 3 3 1 3 6 4 3 5 2 6 1 6 4数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 一个一个 mn 的矩阵的矩阵 M，它的转置，它的转置 T 是一个是一个 nm 的矩阵，且的矩阵，且 T (i, j) = M j, i，1in，1jm，即，即 M 的行是的行是 T 的列，的列，M 的列是的列是 T 的行。的行。 求转置矩阵求转置矩阵 00070015000001800000240001400003000000000009120M0000000001400000000700000002

26、4009018000121500300T数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中00070015000001800000240001400003000000000009120M00000000014000000007000000024009018000121500300T 已知一个稀疏矩阵的三元组表，求该矩阵转置矩已知一个稀疏矩阵的三元组表，求该矩阵转置矩 阵的三元组表。阵的三元组表。 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

27、 解决思路：解决思路： 将矩阵行、列将矩阵行、列 维数互换维数互换 将每个三元组将每个三元组 中的中的 i 和和 j 相相 互调换互调换 重排三元组次重排三元组次 序，使序，使 b.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 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

28、15 4 6 -7 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 方法一：方法一： 为找到为找到 M 中每一列所有非零元素，需对其三元组表中每一列所有非零元素，需对其三元组表 M.data 从第一行起扫描一遍。从第一行起扫描一遍。由于由于 M 的列是的列是 T 的行，且的行，且 T.data 中以中以 M 为主序，所以由此得到的为主序，所以由此得到的 T.data 必定是按必定是按存放的。存放的。 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 -

29、3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中typedef 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; co

30、l = ; + 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; 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

31、2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 6 q p p q p q p 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中for (col = 1; col = nu; + col) for (row = 1; row = mu; + row) Tcolrow = Mrowcol; 一般矩阵转置算法：一般矩阵转置算法：一般矩阵转置算法时间复杂度：一般矩阵转置算法时间复杂度：O(mu ) 用三元组顺序表存储的矩阵转置算法时间复杂度：用三元组顺序表存储的矩阵转置算法时间复杂度：O(nu tu) 若若 tu 与与mu nu 同

32、数量级，则为：同数量级，则为：O(mu ) 算法仅适用于算法仅适用于 tu mu nu 的情况。的情况。 用三元组顺序表存储稀疏矩阵节约存储空间（用三元组顺序表存储稀疏矩阵节约存储空间（优点优点）；）； tu与与mu nu同数量级时，同数量级时，算法时间复杂度高（算法时间复杂度高（）；）； 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中方法二：方法二： 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

33、 6 4 -7T.data M.data 实施步骤：实施步骤： 1、确定、确定 M 的第的第 1 列的第列的第 1 个非零元在个非零元在 T.data 中的位置。中的位置。 3、确定、确定 M 的第的第 col 列的第一个非零元在列的第一个非零元在 T.data 中的位置。中的位置。 2、确定、确定 M 的第的第 col -1 列的非零元个数。列的非零元个数。 存入数组存入数组 numM.nu 存入数组存入数组 cpotM.nu cpot1 = 1; cpotcol = cpotcol 1 + numcol 1 2cola.nu col 1 2 3 4 5 6 7 num(col) 2 2 2

34、 1 0 1 0 cpot(col) 1 3 5 7 8 8 9数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中Status 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;

35、+t) + numM.datat.j; / 求求 M 中各列非零元的个数中各列非零元的个数 cpot1 = 1; 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

36、数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 for (p=1; p=M.tu; +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

37、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 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 pqpqpqpqpqpqpqpq00000000014000000007000000024009018000121500300T数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中Status FastTransposeSMatrix( TSMatri

38、x 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; for (col=2; col=M.nu; +col) cpotcol = cpotcol -1 + numcol -

39、1; / 求求 M 中各列的第一个非零元在中各列的第一个非零元在 T.data 中的序号中的序号 for (p=1; p=M.tu; +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时间复杂度为时间复杂度为: O(nu + tu) 若若 tu 与与mu nu 同数量级，则为：同数量级，则为： 与经典算

40、与经典算 法相同。法相同。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 三元组顺序表又称三元组顺序表又称。 三元组顺序表的三元组顺序表的：非零元在表中按行序有序存储，：非零元在表中按行序有序存储，因此因此。 三元组顺序表的三元组顺序表的：不能随机存取：不能随机存取。若按行号存取某。若按行号存取某 一行中的非零元，则需从头开始进行查找。一行中的非零元，则需从头开始进行查找。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 2、行逻辑联接的顺序表（带行表的三元组）、行逻辑联接的顺序表（带行表的三

41、元组） 在稀疏矩阵中，若要随机存取任意一行的非零元，需要知道在稀疏矩阵中，若要随机存取任意一行的非零元，需要知道 每一行的第一个非零元在三元组表中的位置，而这必须从第一个每一行的第一个非零元在三元组表中的位置，而这必须从第一个 元素起进行搜索查询。元素起进行搜索查询。 7 1 3 -3 1 615 2 112 2 518 3 1 9 3 424 4 6 -7 6 314 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 若在稀疏矩阵的存储结构中增加一个行表若在稀疏矩阵的存储结构中增加一个行表 rpos 快速转置算法

42、中的快速转置算法中的 cpot，指示稀疏矩阵中每行的，指示稀疏矩阵中每行的 非零元素在三元组表中的起始位置，则不必从第一个非零元素在三元组表中的起始位置，则不必从第一个 元素起进行搜索查询。称这种元素起进行搜索查询。称这种“带行链接信息带行链接信息”的三元的三元 组表为：组表为：。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中#define MAXSIZE 12500 /假设非零元个数的最大值假设非零元个数的最大值 typedef struct int i, j; /该非零元的行列下标该非零元的行列下标 Elemtype e; Triple;

43、 typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; /矩阵的行、列数和非零元个数矩阵的行、列数和非零元个数 TSMatrix;int rposMAXRC + 1; / 指示各行第一个非零元的位置指示各行第一个非零元的位置 两个稀疏矩阵相乘时，可以看出这种表示方法的优越性。两个稀疏矩阵相乘时，可以看出这种表示方法的优越性。 RLSMatrix; 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中矩阵乘法矩阵乘法 设矩阵设矩阵 M 是是 m1n1 矩阵，矩阵，N 是是 m2n2 矩阵；只有矩阵

44、；只有 n1 = m2 时，才能相乘得到结果矩阵时，才能相乘得到结果矩阵 Q = MN（一个（一个 m1n2 的矩阵）。的矩阵）。 矩阵相乘的经典算法：矩阵相乘的经典算法： for(i=1; i=m1; i+) for(j=1; j=n2; j+) Qij=0; for(k=1; k=n1; k+) Qij = Qij + Mik * Nkj; 04020 21 0 0050000 10 203NM 4060 10 NMQi i j j k k 不论是否为零，都要进行一次乘法运算。不论是否为零，都要进行一次乘法运算。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机

45、科学与技术系 徐振中 04020 21 0 0050000 10 203NM 4060 10 NMQ i j e 1 1 3 1 4 5 2 2 -1 3 1 2 i j e 1 2 2 2 1 1 3 1 -2 3 2 4 i j e Mi * N j; row 1 2 3 4rposrow 1 2 3 5 1 2 6 2 1 -1 3 2 4 0 0 6-1004 注意：注意：两个稀疏矩阵相乘的结果两个稀疏矩阵相乘的结果 不一定不一定是稀疏矩阵。是稀疏矩阵。 111111111000000111001001001数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科

46、学与技术系 徐振中int MulSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix *Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; / Q 初始化初始化 if (M.tu * N.tu != 0) / Q 是非零矩阵是非零矩阵 for (arow=1; arow=M.mu; +arow) /逐行处理逐行处理 M ctemp =0 ; / 当前行各元素的累加器清零当前行各元素的累加器清零 Q.rposarow = Q.tu + 1; if (arowM.mu) t

47、p=M.rposarow+1; else tp=M.tu+1; for (p=M.rposarow; pM.rposarow+1; +p) /对当前行中每一个非零元找到对应元在对当前行中每一个非零元找到对应元在 N 中的行号中的行号 brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+1; else t = N.tu+1; 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在乘积元素在Q中列号中列号 c

48、tempccol += M.datap.e * N.dataq.e; / for q / 求得求得Q中第中第crow( =arow)行的非零元行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if / for arow / if return OK; / MultSMatrix 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中上述算法的时间复杂度分析：上述算法的时间复杂度分析： 累加器累加器ctemp初始化初始化的时间复杂度为的

49、时间复杂度为 O(M.muN.mu) 求求Q的所有非零元的时间复杂度为的所有非零元的时间复杂度为 O(M.tuN.tu/N.mu) 进行压缩存储的时间复杂度为进行压缩存储的时间复杂度为 O(M.muN.nu) 总的时间复杂度就是总的时间复杂度就是 O(M.muN.nu + M.tuN.tu/N.mu)。 若若M是是m行行n列的稀疏矩阵，列的稀疏矩阵，N是是n行行p列的稀疏矩阵，则列的稀疏矩阵，则M中中 非零元的个数非零元的个数 M.tu = d Mmn，N中非零元的个数中非零元的个数 N.tu = d Nnp，相乘算法的时间复杂度就是，相乘算法的时间复杂度就是 O(mp (1+nd Md N)

50、 ，当，当d M0.05 和和d N0.05 及及 n m=m;M-n=n;M-len=t; If(!(M-row_head=(Olink*)malloc(m+1)sizeof(OLink) exit(OVERFLOW); If(!(M-col_head=(OLink * )malloc(n+1)sizeof(OLink) exit(OVERFLOW); M-row_head =M-col_head =NULL; /初始化行、列头指针向量，各行、列链表为空的链表初始化行、列头指针向量，各行、列链表为空的链表 for(scanf(&i,&j,&e);i!=0; scanf

51、(&i,&j,&e) if(!(p=(OLNode *) malloc(sizeof(OLNode) exit(OVERFLOW); p-row=i;p-col=j;p-value=e; /生成结点生成结点 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中if(M-row_headi=NULL) M-row_headi=p; else /*寻找行表中的插入位置寻找行表中的插入位置*/ for(q=M-row_headi; q-right&q-right-colright) p-right=q-right; q-ri

52、ght=p; /*完成插入完成插入*/ if(M-col_headj=NULL) M-col_headj=p; else /*寻找列表中的插入位置寻找列表中的插入位置*/ for(q=M-col_headj; q-down&q-down-rowdown) p-down=q-down; q-down=p; /*完成插入完成插入*/ 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中两个矩阵相加的算法描述：两个矩阵相加的算法描述： (1) 初始令初始令pa和和pb分别指向分别指向A和和B的第一行的第一个非零的第一行的第一个非零元素的结点，即元素

53、的结点，即paA.rhead1; pbB.rhead1; pre = NULL;且令且令hl初始化初始化 for (j=1; jjpb-j（即（即A的这一行中非零的这一行中非零元素已处理完），则需在元素已处理完），则需在A中插入一个中插入一个pb所指所指结点的复制结点。假设新结点的地址为结点的复制结点。假设新结点的地址为p，则，则A的行表的行表中的指针作如下变化：中的指针作如下变化：if pre = NULL rheadp-i=p;else pre-rightp; p-rightpa; pre = p;数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐

54、振中A的列链表中的指针也要作相应的改变。首先需从的列链表中的指针也要作相应的改变。首先需从hlp-j开始找到新结点在同一列中的前驱结点，并让开始找到新结点在同一列中的前驱结点，并让hlp-j指指向它，然后在列链表中插入新结点：向它，然后在列链表中插入新结点：if cheadp-j = NULL cheadp-j = p; p-down = NULL; else p-downhlp-j-down; hlp-j-downp; hlp-j = p; 若若pa-jpb-j且且pa-j!=0，则令，则令pa指向本行下一个指向本行下一个非零元结点，即非零元结点，即 prepa; papa-right; 若

55、若pa-j = pb-j，则将，则将B中当前结点的值加到中当前结点的值加到A中当中当前结点上，即前结点上，即pa-epb-e; 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中此时若此时若pa-e!=0，则指针不变，否则删除，则指针不变，否则删除A中该结点，即行表中该结点，即行表中指针变为：中指针变为：if pre = NULL rheadpa-i = pa-right;else pre-rightpa-right; p=pa; pa=pa-right; 同时，为了改变列表中的指针，需要先找到同一列中的前驱同时，为了改变列表中的指针，需要先找到同

56、一列中的前驱结点，且让结点，且让hlpa-j指向该结点，然后如下修改相应指针：指向该结点，然后如下修改相应指针：if cheadp-j = pcheadp-j = hlp-j = p-down; else hlp-j-downp-down; free (p);(3) 若本行不是最后一行，则令若本行不是最后一行，则令pa和和pb指向下一行的第一个指向下一行的第一个非零元结点，转非零元结点，转(2)；否则结束。；否则结束。此算法时间复杂度：此算法时间复杂度：O(ta+tb)数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中 广义表广义表（又称（又称列表

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

58、、鲁能队、实德队均作为东道主未敢参加，成为空表。国家队、鲁能队、实德队均作为东道主 的参赛队参加，构成一个小的线性表，成为原线性表的一个数的参赛队参加，构成一个小的线性表，成为原线性表的一个数 据元素。这种据元素。这种。 单个单个元素元素 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中广义表广义表通常记作：通常记作： LS = (a1，a2，an) 其中：其中： LS 为表名，为表名， n 为表的长度，为表的长度， 每一个每一个 ai 为表的元素。为表的元素。 习惯上，一般用习惯上，一般用表示表示，小写字母小写字母表示表示原子原子。 表头表头：

59、若若 LS 非空非空 (n1 )，则其，则其第一个第一个元素元素 a1 就是表头。就是表头。 记作记作 head(LS) = a1。 表头可以是原子，也可以是子表。表头可以是原子，也可以是子表。 表尾表尾：除表头之外的除表头之外的其它元素其它元素组成的组成的表表。 记作记作 tail(LS) = (a2, ., an)。 表尾不是最后一个元素，而是一个子表。表尾不是最后一个元素，而是一个子表。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 制作：制作：计算机科学与技术系 徐振中(1) A=( ) 例：例： 空表，长度为空表，长度为 0。 (2) B=( ) (3) C=(a, (b

60、, c) 长度为长度为 1，表头、表尾均为，表头、表尾均为 ( )。 长度为长度为 2，由原子，由原子 a 和子表和子表 (b, 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)。 数据结构数据结构 第五章第五章 数组和广义表数组和广义表