第三章 集合、稀疏矩阵和广义表.pptVIP

第3章 集合、稀疏矩阵和广义表 3.4 稀疏矩阵 假定有一个电信总局和五个支局，总局到其各支局间的通信如图所示。五个支局依次编为1，2，3，4，5号,总局编为6号。 3.4.1稀疏矩阵的定义 1.稀疏矩阵的概念 稀疏矩阵:非零元素的个数远远小于零元素的个数 2.稀疏矩阵的三元组线性表示 在计算机中存储矩阵的一般方法是用数组存储,元素一一对应； 对于稀疏矩阵来说，存储大量的零元素会浪费大量存储空间； 用三元组存储稀疏矩阵中的每一个元素： （行号i，列号j，数值aij） 用三元组线性表存储整个稀疏矩阵： （(1,1,3),(1,4,5),(2,3,-2), (3,1,1),(3,3,4),(3,5,6),(5,3,-1)) 3.4.2 稀疏矩阵的存储结构 顺序存储结构与链接存储结构 1.顺序存储 struct Triple{//表示一个元素的三元组 int row,col; ElemType val; }; struct SMatrix {//稀疏矩阵的顺序存储类型 int m,n,t; Triple sm[MaxTerms + 1]; }； //三元组的线性表 2.链接存储 (1)带行指针向量的链接存储 2.链接存储 (1)带行指针向量的链接存储 struct LMatrix { //m行单链表的表头指针 int m,n,t; TripleNode* vector[MaxRows + 1]; //0分量未用 }; (2)十字链接存储 每个三元组结点既处于同一行的单链表中,有处于同一列的单链表中。 struct CrossNode { int row,col; ElemType val; CrossNode *right, *down; }; struct CLMatrix { int m,n,t; CrossNode * rv[MaxRow + 1]; //Row CrossNode *cv[MaxColumns + 1];//Column }; 3.5 广义表 (General Lists ) 1.表示方式 广义表是n ( ? 0 )个表元素组成的有限序列，记作: LS = (a0, a1, a2, …, an-1) 或LS (a0, a1, a2, …, an-1) ai是表元素，它可以是表元素(是一个广义表，用大写字母)，可以是单元素(称为原子，用小写字母)。 2.图形表示 A = ( ) B = (e) C = (a,(b, c, d ) ) 3.表的深度： 括号嵌套的最大次数； 根结点到每个树枝结点所经过结点个数的最大值； E( (a,(a,b),((a,b),c))) 3.5.2 广义表的存储结构 ---递归的数据结构 补充：广义表的两个操作 1. Head( )或GetHead( ) 得到广义表的表头元素（单元素or表元素） 2. Tail( )或GetTail( ) 得到广义表的表尾，除表头元素之外的剩余元素组成的子表（肯定是广义表） 例1：A=(a,b,c,d) Head(A)=a Tail(A)=(b,c,d) 例2：若Head(L)=Tail(L),则 L=((a),a) 注：a并不是代表单元素 练习： 1.A=((a,b,c,d)),则Head(A)= Tail(A)= 2.已知广义表LS=(a,(b,c,d),e),运用head和tail函数取出原子b的运算是 Head(Head(Tail(LS))) 3.设广义表L=((),()),则Head(L),Tail(L),L的长度和深度分别为多少 Head(L)长度为0，深度为1 Tail(L)长度为1，深度为2 L长度为2，深度为2 4.Tail(Head(((a,b),(c,d))))=? (b) 5. P129习题3-2 6.已知两个4×5的稀疏矩阵的三元组表分别如下,请画出这两个稀疏矩阵之和的三元组表。 * * 0 0 0 -1 0 0