第三章 稀疏矩阵和广义表(jian)

1、7600070015000001800000240001400003000000000009120M3.1稀疏矩阵3.1.1稀疏矩阵的定义非零元素个数较少，且分布没有一定规律的矩阵第三章 稀疏矩阵和广义表三元组线性表表示：只存矩阵的行列维数和每个非零元素的行列下标及其值.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）唯一确定稀疏矩阵的运算概述：与用二维数组所表示的矩阵的运算相同,通常为求一个稀疏矩阵的转置,计算两个矩阵的和,计算两个矩阵的乘积等。首先，三元组用如

2、下记录结构定义： struct Triple int row, col; ElemType val; ; 其中row和col用来分别存储元素的行号和列号，val用来存储元素值。其次，一个稀疏矩阵的顺序存储类型定义如下： struct SMatrix int m, n, t; struct Triple smMaxTerms+1; ;3.1.2稀疏矩阵的存储结构1顺序存储结构2链接存储结构l带行指针向量的链接存储 需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为： struct TripleNode int row, col; /*存储行号和列号

3、*/ ElemType val; /*存储元素值*/ struct TripleNode* next; ; /*指向同一行的下一个结点*/ 为便于访问每一个单链表，需要使用一个行指针向量（即一维数组），该向量中的第i个分量（即对应数组中下标为i的元素）用来存储稀疏矩阵中第i行所对应的单链表的表头指针。带行指针向量的链接存储类型定义如下： struct LMatrix int m, n, t; struct TripleNode* lmMaxRows+1; ; 其中，lm向量用来存储m个行单链表的表头指针，MaxRows为全局变量，其值要大于等于所存储矩阵的行数。如对应以上矩阵的带行指针向量的链

4、接存储u十字链表Y设行指针数组和列指针数组，分别指向每行、列第一个非零元Y结点定义row col valdownright34008000450003A113418225234v十字链接存储3.2.1 稀疏矩阵的运算 稀疏矩阵的建立稀疏矩阵的建立稀疏矩阵的输出稀疏矩阵的输出 3.2 广义表广义表 3.2.1 广义表的定义 广义表广义表（generalized list）简称表，它是线性表的推广。一个广义表是n(n0)个元素的一个序列，当n=0时则称为空表。在一个非空的广义表中，其元素可以是某一确定类型的对象(这种元素被称做单元素)，也可以是由单元素构成的表(这种元素可相对地被称做子表或表元素)

5、。显然，广义表的定义是递归的，广义表是一种递归的数据结构。 设ai为广义表的第i个元素，则广义表的一般表示与线性表相同： (a1,a2,ai,ai+1,an) 其中n表示广义表的长度，即广义表中所含元素的个数，n0。 同线性表一样，也可以用一个标识符来命名一个广义表，如用LS命名上面的广义表，则为： LS=(a1,a2,ai,ai+1,an) 在广义表的讨论中，为了把单元素同表元素区别开在广义表的讨论中，为了把单元素同表元素区别开来，一般用小写字母表示单元素，用大写字母表示来，一般用小写字母表示单元素，用大写字母表示表，如：表，如： A=( ) B=(e) C=(a,(b,c,d) D=(A,

6、B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c)若用圆圈表示表（表元素）若用圆圈表示表（表元素）,用方框表示单元素，用方框表示单元素，用线段把表和它的元素（元素结点应在其表结点的用线段把表和它的元素（元素结点应在其表结点的下方）连接起来，则可得到一个广义表的图形表示。下方）连接起来，则可得到一个广义表的图形表示。如上面五个广义表的图形表示如图如上面五个广义表的图形表示如图3-6所示。所示。3.2.2 广义表的存储结构广义表的存储结构 struct GNode int tag; /标志域标志域 union ElemType data; /单元素数值单元素数值

7、struct GNode* sublist; /表元素的表头指针表元素的表头指针 ; struct GNode* next; ; /指向其后继结点的指针域指向其后继结点的指针域=0 单元素结点单元素结点=1 子表结点子表结点以上五个广义表的链接存储结构的示意图如下：以上五个广义表的链接存储结构的示意图如下： 3.2.3 广义表的运算广义表的运算广义表的运算主要有求广义表的长度和深度，向广义表的运算主要有求广义表的长度和深度，向广义表插入元素和从广义表中查找或删除元素，建广义表插入元素和从广义表中查找或删除元素，建立广义表的存储结构，打印广义表等。由于广义表立广义表的存储结构，打印广义表等。由于

8、广义表是一种递归的数据结构，所以对广义表的运算一般是一种递归的数据结构，所以对广义表的运算一般采用递归的算法。采用递归的算法。求广义表的长度求广义表的长度 在广义表中，在广义表中，同一层次的每个结点是通过同一层次的每个结点是通过next域域链接起来的，所以可把它看做是由链接起来的，所以可把它看做是由next域链接起域链接起来的单链表。来的单链表。因此求广义表的长度是求单链表的长因此求广义表的长度是求单链表的长度。递归算法如下：度。递归算法如下： int LenthGList(struct GNode* GL) if(GL!=NULL) return 1+LenthGList(GL-next); else return 0; 求广义表的深度求广义表的深度 广义表深度的递归定义是它等于所有子表中表的最大深度广义表深度的递归定义是它等于所有子表中表的最大深度加加1，若一个表为空或仅由单元素所组成，则深度为，若一个表为空或仅由单元素所组成，则深度为1。算。算法如下：法如下： int DepthGList(struct GNode* GL)