数据结构C语言版第5章数组和广义表.ppt

《数据结构C语言版第5章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构C语言版第5章数组和广义表.ppt（64页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构 第五章第五章 数组和广义表数组和广义表 数数 组组 和和 广广 义义 表表 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 1、数组的定义和顺序存储方式；、数组的定义和顺序存储方式；2、特殊矩阵的压缩存储；、特殊矩阵的压缩存储；3、稀疏矩阵；、稀疏矩阵；4、广义表的概念、表示及基本操作；、广义表的概念、表示及基本操作；广义表存储结构的实现。广义表存储结构的实现。教学内容教学内容 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 5.1 数组的定义数组的定义 数组：数组：按一定格式排列起来的按一定格式排列起来的 具有具有相同类型相同类型相同类型相同类型的数据元

2、素的集合。的数据元素的集合。一维数组：一维数组：若线性表中的数据元素为非结构的简单元素，若线性表中的数据元素为非结构的简单元素，则称为一维数组。则称为一维数组。一维数组的逻辑结构：一维数组的逻辑结构：线性结构。定长的线性表。线性结构。定长的线性表。声明格式：声明格式：数据类型数据类型 变量名称变量名称长度长度；例：例：int num5=0，1，2，3，4;数据结构数据结构 第五章第五章 数组和广义表数组和广义表 二维数组：二维数组：若一维数组中的数据元素又是一维数组结构，若一维数组中的数据元素又是一维数组结构，则称为二维数组。则称为二维数组。非线性结构非线性结构 num5=0，1，2，3，4;

3、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 二维数组的逻辑结构二维数组的逻辑结构 线性结构线性结构定长的线性表定长的线性表每一个数据元素每一个数据元素 既在一个行表中，既在一个行表中，又在一个列表中。又在一个列表中。该线性表的每个数据元素该线性表的每个数据元素 也是一个定长的线性表。也是一个定长的线性表。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 在在 C 语言中，一个二维数组类型也可以定义为语言中，一个二维数组类型也可以定义为 一维数组类型（其分量类型为一维数组类型），即：一维数组

4、类型（其分量类型为一维数组类型），即：typedef elemtype array2mn;等价于：等价于：typedef elemtype array1n;typedef array1 array2m;声明格式：声明格式：数据类型数据类型 变量名称变量名称行数行数 列数列数；例：例：int num5 8;数据结构数据结构 第五章第五章 数组和广义表数组和广义表 三维数组：三维数组：若二维数组中的元素又是一个一维数组结构，若二维数组中的元素又是一个一维数组结构，则称作三维数组。则称作三维数组。n 维数组：维数组：若若 n-1 维数组中的元素又是一个一维数组结构，维数组中的元素又是一个一维数组结构

5、，则称作则称作 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 jnElemSet 数据关系：数据关系：RR1,R2,.,Rn Ri|0jkbk-1,1kn 且且 ki,0jibi-2,aj1jijn,aj1ji+1jnD,i=2,.,n 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 数据对象数据对象:D=aij|0 i

7、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二维数组的抽象数据类型的数据对象和数据关系的定义二维数组的抽象数据类型的数据对象和数据关系的定义 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 基本操作：基本操作：InitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数若维数 n 和各维长度合法，则构造相应的数组和各维长度合法，则构造相应的数组 A，并返回并返回 OK。DestroyArray(&A)操作结果：操作结果：销毁数组销毁数组 A。V

8、alue(A,&e,index1,.,indexn)初始条件：初始条件：A 是是 n 维数组，维数组，e 为元素变量，随后是为元素变量，随后是 n 个下标值。个下标值。操作结果：操作结果：若各下标不超界，则若各下标不超界，则 e 赋值为所指定的赋值为所指定的A的元素值，的元素值，并返回并返回 OK。Assign(&A,e,index1,.,indexn)初始条件：初始条件：A 是是 n 维数组，维数组，e 为元素变量，随后是为元素变量，随后是 n 个下标值。个下标值。操作结果：操作结果：若下标不超界，则将若下标不超界，则将 e 的值赋给所指定的的值赋给所指定的A的元素，的元素，并返回并返回 O

9、K。ADT Array 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 数组特点：数组特点：结构固定结构固定结构固定结构固定维数和维界不变。维数和维界不变。数组基本操作：数组基本操作：初始化、销毁、取元素、修改元素值。初始化、销毁、取元素、修改元素值。5.2 数组的顺序表示和实现数组的顺序表示和实现 一般不做插入和删除操作。一般不做插入和删除操作。因为因为因为因为 所以：所以：所以：所以：一般都是采用一般都是采用顺序存储结构顺序存储结构来表示数组。来表示数组。注意：注意：注意：注意：数组可以是多维的，但存储数据元素的内存单元地址数组可以是多维的，但存储数据元素的内存单元地址 是一维的

10、，因此，在存储数组结构之前，需要解决将是一维的，因此，在存储数组结构之前，需要解决将 多维关系映射到一维关系的问题。多维关系映射到一维关系的问题。两种顺序存储方式两种顺序存储方式 以行序为主序以行序为主序(低下标优先低下标优先)BASIC、COBOL和和PASCAL 以列序为主序以列序为主序(高下标优先高下标优先)FORTRAN 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 以行序为主序存放：以行序为主序存放：a amm-1,-1,n n-1-1 .a amm-1,1-1,1 a amm-1,0-1,0 .a1,n-1 .a11 a10 a0,n-1 .a01 a0001n-1m*

11、n-1n二维数组中任一元素二维数组中任一元素 aij 的存储位置的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)L 某个元素的地址就是它前面所有行某个元素的地址就是它前面所有行 所占的单元加上它所在行前面所有列元所占的单元加上它所在行前面所有列元 素所占的单元数之和。素所占的单元数之和。基地址或基址基地址或基址 二维数组的映象函数二维数组的映象函数 a00 a01 .a0,n-1 a10 a11 .a1,n-1 a amm-1,0-1,0 a amm-1,1 -1,1 .a amm-1,-1,n n-1-1 .数据结构数据结构 第五章第五章 数组和广义表数组和广义表 按列序为主序存

12、放按列序为主序存放 01m-1m*n-1m am-1,n-1 .a1,n-1 a0,n-1 .am-1,1 .a11 a01 a amm-1,0-1,0 .a a1010 a a0000 a a0000 a01 .a0,n-1 a a1010 a11 .a1,n-1 a amm-1,0-1,0 am-1,1 .am-1,n-1 .二维数组中任一元素二维数组中任一元素 aij 的存储位置的存储位置 LOC(i,j)=LOC(0,0)+(b1ji)L 某个元素的地址就是它前面所有列某个元素的地址就是它前面所有列 所占的单元加上它所在列前面所有行元所占的单元加上它所在列前面所有行元 素所占的单元数之

13、和。素所占的单元数之和。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 例例 1：一个二维数组：一个二维数组 A，行下标的范围是行下标的范围是 1 到到 6，列下标，列下标 的范围是的范围是 0 到到 7，每个数组元素用相邻的，每个数组元素用相邻的 6 个字节个字节 存储，存储器按字节编址。那么，这个数组的体积存储，存储器按字节编址。那么，这个数组的体积 是是 个字节。个字节。答：答：Volume=mnL =(6 1+1)(7 0+1)6 =486=288 288 288 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 例例 2：某校计算机系考研题某校计算机系考研题 设数组

14、设数组 A059,069 的基地址为的基地址为 2048，每个元素占，每个元素占 2 个个 存储单元，若存储单元，若以列序为主序以列序为主序顺序存储，则元素顺序存储，则元素 A31,57 的存储的存储 地址为地址为 。解：解：LOC(i,j)=LOC(31,57)=LOC(0,0)+(b1ji)L =2048+(605731)2 =8950 89508950 a00 a01 a0,69 a10 a11 a1,69 a59,0 a59,1 a59,69 a31,57 作业：作业：5.1 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 5.3 矩阵的压缩存储矩阵的压缩存储 矩阵定义矩阵定

15、义：一个由一个由 mn 个元素排成的个元素排成的 m 行（横向）行（横向）n 列（纵向）的表。列（纵向）的表。矩阵的常规存储矩阵的常规存储：将矩阵描述为一个二维数组。将矩阵描述为一个二维数组。矩阵的常规存储的特点矩阵的常规存储的特点：可以对其元素进行随机存取；可以对其元素进行随机存取；矩阵运算非常简单；存储的密度为矩阵运算非常简单；存储的密度为 1。不适宜常规存储的矩阵：不适宜常规存储的矩阵：值相同的元素很多且呈某种规律值相同的元素很多且呈某种规律 分布；零元素多。分布；零元素多。矩阵的压缩存储：矩阵的压缩存储：为多个相同的非零元素只分配一个存储为多个相同的非零元素只分配一个存储 空间；对零元

16、素不分配空间。空间；对零元素不分配空间。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 5.3.1 特殊矩阵特殊矩阵 特殊矩阵：特殊矩阵：元素值的排列具有一定规律的矩阵。元素值的排列具有一定规律的矩阵。对称矩阵、下（上）三角矩阵、对角线矩阵等。对称矩阵、下（上）三角矩阵、对角线矩阵等。1、对称矩阵、对称矩阵 在一个在一个 n 阶方阵阶方阵 A 中，若元素满足下述性质：中，若元素满足下述性质：aij=aji 1 i,j n 则称则称 A 为为对称矩阵对称矩阵。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 对称矩阵上下三角中的元素数均对称矩阵上下三角中的元素数均 为：为：n(

17、n+1)/2 可可以行序以行序为主序将元素存放在一为主序将元素存放在一 个一维数组个一维数组 san(n+1)/2 中。中。对称矩阵的存储结构对称矩阵的存储结构 k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 以行序为主序存储下三角：以行序为主序存储下三角：a11a21a22a31a32 an1ann数据结构数据结构 第五章第五章 数组和广义表数组和广义表 则则 aij 和和 sak 存在着一一对应关系：存在着一一对应关系：aij 前的前的 i-1 行有行有 1+2+(i-1)=i(i-1)/2 个元素，在第个元素，在第 i 行上有行上有 j 个元素。个元素。因为因为aij=a

18、ji，所以只要交换上述，所以只要交换上述 对应关系式中的对应关系式中的 i 和和 j 即可。即可。k=0 1 2 3 4 n(n-1)/2 以行序为主序存储下三角：以行序为主序存储下三角：a11a21a22a31a32 an1ann数据结构数据结构 第五章第五章 数组和广义表数组和广义表 2、三角矩阵三角矩阵 以主对角线划分，三角矩阵有上（以主对角线划分，三角矩阵有上（下下）三角两种。上（）三角两种。上（下下）三角矩阵的下（三角矩阵的下（上上）三角（不含主对角线）中的元素均为常数。）三角（不含主对角线）中的元素均为常数。在大多数情况下，三角矩阵常数为零。在大多数情况下，三角矩阵常数为零。上三角

19、矩阵上三角矩阵下三角矩阵下三角矩阵 三角矩阵的存储：三角矩阵的存储：除了存储主对角线及上（除了存储主对角线及上（下下）三角中的元）三角中的元 素外，再加一个存储常数素外，再加一个存储常数 c 的空间。的空间。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 3、对角矩阵对角矩阵 在对角矩阵中，所有的非零元素集中在以主对角线为中心的在对角矩阵中，所有的非零元素集中在以主对角线为中心的 带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角 线上的元素之外，其余元素皆为零。线上的元素之外，其余元素皆为零。对角矩阵可按行优先顺序或对角

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

21、。M 由由(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)惟一确定矩阵的惟一确定矩阵的一个非零元。一个非零元。三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。数据结构数据结构 第五章第五章 数组和广义表数组和广义表#define MAXSIZE 12500 /假设非零元个数的最大值假设非零元个数的最大值 typedef struct int i,j;/该非零元的行列下

22、标该非零元的行列下标 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 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法顺序存储结构顺序存储结构 1、三元组顺序表、三元组顺序表 6 7 7 8 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7数据结构数据结构 第五章第五章 数组和广义表数组和广义表 转置矩阵：转置矩阵：转置矩阵：转

23、置矩阵：一个一个 mn 的矩阵的矩阵 M，它的转置它的转置 T 是一个是一个 nm 的矩阵，且的矩阵，且 T(i,j)=M j,i，1in，1jm，即即 M 的行是的行是 T 的列，的列，M 的列是的列是 T 的行。的行。求转置矩阵求转置矩阵 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 问题描述：问题描述：问题描述：问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩已知一个稀疏矩阵的三元组表，求该矩阵转置矩 阵的三元组表。阵的三元组表。i j tu 0 1 2 3 4 5 6 7 8 6 7 7 8 8 1 212 1 3 9 3 1-3 3 614 4 3 24 5 218

24、6 115 6 4-7 解决思路：解决思路：将矩阵行、列将矩阵行、列 维数互换维数互换 将每个三元组将每个三元组 中的中的 i 和和 j 相相 互调换互调换 重排三元组次重排三元组次 序，使序，使 b.data 中元素以中元素以 T 的的 行行(M的列的列)为为 主序。主序。M.data i j tu 0 1 2 3 4 5 6 7 8 7 6 6 8 8 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 6 6 8 8 2 1 12 3 1 9 1 3 -3 6 3

25、14 3 4 24 2 5 18 1 6 15 4 6 -7 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 方法一：方法一：按按按按 MM 的列序转置的列序转置的列序转置的列序转置 为找到为找到 M 中每一列所有非零元素，需对其三元组表中每一列所有非零元素，需对其三元组表 M.data 从第一行起扫描一遍。从第一行起扫描一遍。由于由于 M 的列是的列是 T 的行，且的行，且 T.data 中以中以 M 行序行序行序行序为主序，所以由此得到的为主序，所以由此得到的 T.data 必定是按必定是按行优先行优先行优先行优先存放的。存放的。7 6 6 8 8 6 7 7 8 8 1 212

26、 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 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 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

27、)q=1;for(col=1;col=M.nuM.nu;+col)for(p=1;p=M.tuM.tu;+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 7 7 8 8 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

28、 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 7 7 6 8 8 q p p q p q p 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;一般矩阵转置算法：一般矩阵转置算法：一般矩阵转置算法时间复杂度：一般矩阵转置算法时间复杂度：O(mu nunu)用三元组顺序表存储用三元组顺序表存储的矩阵转置算法的矩阵转置算法时间复杂度：时间复杂度：O(nu tu)若若 tu 与与mu nu 同数量级，则为：同数量级，则为：O(mu nunu2 2)算

29、法仅适用于算法仅适用于 tu mu nu 的情况。的情况。结论结论结论结论 用三元组顺序表存储稀疏用三元组顺序表存储稀疏矩阵节约存储空间（矩阵节约存储空间（优点优点）；）；tu与与mu nu同数量级同数量级时，时，算法时间复杂度高（算法时间复杂度高（缺点缺点缺点缺点）；）；数据结构数据结构 第五章第五章 数组和广义表数组和广义表 方法二：方法二：按按按按 MM 的行序转置的行序转置的行序转置的行序转置 快速转置快速转置快速转置快速转置 7 6 6 8 8 1 3-3 1 615 2 112 2 518 3 1 9 3 424 4 6-7 6 314 6 7 7 8 8 1 212 1 3 9

30、3 1-3 3 614 4 3 24 5 218 6 115 6 4-7T.data M.data 实施步骤：实施步骤：1、确定、确定 M 的第的第 1 列的第列的第 1 个非零元在个非零元在 T.data 中的位置。中的位置。1 1 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

31、 5 6 7 num(col)2 2 2 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;+t)+numM.datat.j;/求求 M 中各列非零元的个

32、数中各列非零元的个数 cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;/求求 M 中各列的第一个非零元在中各列的第一个非零元在 T.data 中的序号中的序号 6 7 7 8 8 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)7 7 6 8 8 0 0 0 0 0 0 0 1 1 1 1 2 2 2 1 1 3 5 7 8 8 9 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 for(p=1;

33、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 7 7 8 8 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 97 7 6 8 8 2 1 12 4 3

34、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 pqpqpqpqpqpqpqpq数据结构数据结构 第五章第五章 数组和广义表数组和广义表 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;f

35、or(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)/转置矩阵元素转置矩阵元素 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

36、 OK;/FastTransposeSMatrix时间复杂度为时间复杂度为:O(nu+tu)若若 tu 与与mu nu 同数量级，则为：同数量级，则为：O O(mumu nunu)与经典算与经典算 法相同。法相同。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 三元组顺序表又称三元组顺序表又称有序的双下标法有序的双下标法有序的双下标法有序的双下标法。三元组顺序表的三元组顺序表的优点优点优点优点：非零元在表中按行序有序存储，：非零元在表中按行序有序存储，因此因此便于进行依行顺序处理的矩阵运算便于进行依行顺序处理的矩阵运算便于进行依行顺序处理的矩阵运算便于进行依行顺序处理的矩阵运算。三元

37、组顺序表的三元组顺序表的缺点缺点缺点缺点：不能：不能随机随机存取存取。若按行号存取某。若按行号存取某 一行中的非零元，则需从头开始进行查找。一行中的非零元，则需从头开始进行查找。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 2、行逻辑联接的顺序表（、行逻辑联接的顺序表（带行表的三元组带行表的三元组）在稀疏矩阵中，若要随机存取任意一行的非零元，需要知道在稀疏矩阵中，若要随机存取任意一行的非零元，需要知道 每一行的第一个非零元在三元组表中的位置，而这必须从第一个每一行的第一个非零元在三元组表中的位置，而这必须从第一个 元素起进行搜索查询。元素起进行搜索查询。7 6 6 8 8 1 3-

38、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 快速转置算法中的快速转置算法中的 cpot，指示稀疏矩阵中每行的指示稀疏矩阵中每行的 非零元素在三元组表中的起始位置，则不非零元素在三元组表中的起始位置，则不必从第一个必从第一个 元素起进行搜索查询。元素起进行搜索查询。称称这种这种“带行链接信息带行链接信息”的三元的三元 组表为：组表为：行逻辑联接的

39、顺序表行逻辑联接的顺序表行逻辑联接的顺序表行逻辑联接的顺序表。数据结构数据结构 第五章第五章 数组和广义表数组和广义表#define MAXSIZE 12500 /假设非零元个数的最大值假设非零元个数的最大值 typedef struct int i,j;/该非零元的行列下标该非零元的行列下标 Elemtype e;Triple;typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;/矩阵的行、列数和非零元个数矩阵的行、列数和非零元个数 TSMatrix;int rposMAXRC+1;/指示各行第一个非零元的位置指示各行第一个非零元的位置 两个稀疏

40、矩阵相乘时，可以看出这种表示方法的优越性。两个稀疏矩阵相乘时，可以看出这种表示方法的优越性。RLSMatrix;数据结构数据结构 第五章第五章 数组和广义表数组和广义表 矩阵乘法矩阵乘法 设矩阵设矩阵 M 是是 m1n1 矩阵，矩阵，N 是是 m2n2 矩阵；只有矩阵；只有 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;i i j j k k 不论是

41、否为零，都要进行一次乘法运算。不论是否为零，都要进行一次乘法运算。没必要！没必要！没必要！没必要！数据结构数据结构 第五章第五章 数组和广义表数组和广义表 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 Mik k *Nk kj;row 1 2 3 4rposrow 1 2 3 5 1 2 6 2 1-1 3 2 4 0 0 6-1004 注意：注意：两个稀疏矩阵相乘的结果两个稀疏矩阵相乘的结果 不一定不一定是稀疏矩阵。是稀疏矩阵。数据结构数据结构 第五章第五章 数组和广义表数组和广义表 int MulSMat

42、rix(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)tp=M.rposarow+1;else tp=M.tu+1;for(p=M.rposarow;pM.rposarow+1;

43、+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中列号中列号 ctempccol+=M.datap.e*N.dataq.e;/for q /求得求得Q中第中第crow(=arow)行的非零元行的非零元 for(ccol=1;ccol MAXSIZE)return ERROR

44、;Q.dataQ.tu=arow,ccol,ctempccol;/if /for arow /if return OK;/MultSMatrix 数据结构数据结构 第五章第五章 数组和广义表数组和广义表 上述算法的时间复杂度分析：上述算法的时间复杂度分析：累加器累加器ctemp初始化初始化的时间复杂度为的时间复杂度为 O(M.muN.mu)求求Q的所有非零元的时间复杂度为的所有非零元的时间复杂度为 O(M.tuN.tu/N.mu)进行压缩存储的时间复杂度为进行压缩存储的时间复杂度为 O(M.muN.nu)总的时间复杂度就是总的时间复杂度就是 O(M.muN.nu+M.tuN.tu/N.mu)。

45、若若M是是m行行n列的稀疏矩阵，列的稀疏矩阵，N是是n行行p列的稀疏矩阵，则列的稀疏矩阵，则M中中 非零元的个数非零元的个数 M.tu=d Mmn，N中非零元的个数中非零元的个数 N.tu=d Nnp，相乘算法的时间复杂度就是相乘算法的时间复杂度就是 O(mp(1+nd Md N)，当，当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)exi

46、t(OVERFLOW);M-row_head=M-col_head=NULL;/初始化行、列头指针向量，各行、列链表为空的链表初始化行、列头指针向量，各行、列链表为空的链表 for(scanf(&i,&j,&e);i!=0;scanf(&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 /*寻找行表中的插入位置寻找行表中

47、的插入位置*/for(q=M-row_headi;q-right&q-right-colright)p-right=q-right;q-right=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分别指向分别

48、指向A和和B的第一行的第一个非零的第一行的第一个非零元素的结点，即元素的结点，即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;数据结构数据结构 第五章第五章 数组和广义表数

49、组和广义表 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;若若pa-j=pb-j，则

50、将则将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;同时，为了改变列表中的指针，需要先找到同一列中的前驱同时，为了改变列表中的指针，需要先找到同一列中的前驱结点，且让结点，且让hlpa-j指向该结点，然后如下修改相应指针：指向该结