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

《第三章 集合、稀疏矩阵和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章集合、稀疏矩阵和广义表3.4稀疏矩阵假定有一个电信总局和五个支局，总局到其各支局间的通信如图所示。五个支局依次编为1，2，3，4，5号,总局编为6号。3.4.1稀疏矩阵的定义1.稀疏矩阵的概念稀疏矩阵:非零元素的个数远远小于零元素的个数000-100000000060401000-200005003A=行数m=5,列数n=6,非零元素个数t=72.稀疏矩阵的三元组线性表示在计算机中存储矩阵的一般方法是用数组存储,元素一一对应；对于稀疏矩阵来说，存储大量的零元素会浪费大量存储空间；用三元组存储稀疏矩阵中的每一个元素：（行号i，列号j，数值aij

2、）用三元组线性表存储整个稀疏矩阵：（(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.顺序存储structTriple{//表示一个元素的三元组introw,col;ElemTypeval;};structSMatrix{//稀疏矩阵的顺序存储类型intm,n,t;Triplesm[MaxTerms+1];}；//三元组的线性表rowcolval-135653433113-232541311Valcolprow用三元组线性表顺

3、序存储表示稀疏矩阵1234567下标2.链接存储(1)带行指针向量的链接存储structTripleNode{//三元组的结点introw,col;ElemTypeval;TripleNode*next;};2.链接存储(1)带行指针向量的链接存储11314523-253-131133435654321rowcolvalnextstructLMatrix{//m行单链表的表头指针intm,n,t;TripleNode*vector[MaxRows+1];//0分量未用};(2)十字链接存储每个三元组结点既处于同一行的单链表中,有处于同一列

4、的单链表中。structCrossNode{introw,col;ElemTypeval;CrossNode*right,*down;};rowcolvaldownright列向量行向量111111132134562134514523-233435631153-1structCLMatrix{intm,n,t;CrossNode*rv[MaxRow+1];//RowCrossNode*cv[MaxColumns+1];//Column};3.5广义表(GeneralLists)3.5.1广义表的定义线性表的推广，但本身不是线性

5、表与线性表的区别：组成元素可以不同1.表示方式广义表是n(0)个表元素组成的有限序列，记作:LS=(a0,a1,a2,…,an-1)或LS(a0,a1,a2,…,an-1)ai是表元素，它可以是表元素(是一个广义表，用大写字母)，可以是单元素(称为原子，用小写字母)。A=()//空表，长度为0B=(e)//单个元素，长度为1C=(a,(b,c,d))//两个元素a和(b,c,d)，长度为2D=(A,B,C)=((),(e),(a,(b,c,d)))//长度为3E=((a,(a,b),((a,b),c)))//长度为12.图形表示A=()B=(e)

6、C=(a,(b,c,d))AeBCabcde表元素D(A(),B(e),C(a,(b,c,d)))E((a,(a,b),((a,b),c)))AeBCabcdDaaabcEb可递归3.表的深度：括号嵌套的最大次数；根结点到每个树枝结点所经过结点个数的最大值；E((a,(a,b),((a,b),c)))aaabcEb3.5.2广义表的存储结构---递归的数据结构tag=1sublistnext表结点tag=0datanext可以顺序存储吗？StructGLNode{booltag;union{ElemTypedata;GLNode*sublist;}

7、;GLNode*next;};A=()A=()带表头附加结点的广义表的链接存储结构B=(e)C=(a,(b,c,d))补充：广义表的两个操作1.Head()或GetHead()得到广义表的表头元素（单元素or表元素）2.Tail()或GetTail()得到广义表的表尾，除表头元素之外的剩余元素组成的子表（肯定是广义表）例1：A=(a,b,c,d)Head(A)=aTail(A)=(b,c,d)例2：若Head(L)=Tail(L),则L=((a),a)注：a并不是代表单元素练习：1.A=((a,b,c,d)),则Head(A)=Tail(A)=2.

8、已知广义表LS=(a,(b,c,d),e),运用head和tail函数取出原子b的运算是Head(Head(Tail(LS