发布时间 : 星期一 文章数据结构-朱二周更新完毕开始阅读12798ad2c9d376eeaeaad1f34693daef5ef7132a
矩阵的转置是常见的一种矩阵运算。对于一个M*N的矩阵M，它的转置矩阵T是一个N*M的矩阵，且T(i,j)=M(j,i),1<=i<=n,1<=j<=m.一个稀疏矩阵的转置矩阵仍然是一个稀疏矩阵。如何求得矩阵M的转置矩阵T？
①将矩阵的行列值相互交换；
②将每个三元组中的i和j 相互调换；
③重排三元组之间的次序便可实现矩阵的转置。
其中①和②是容易做到的，关键是③。即如何使b.item中的三元组是以T的行(M的列)为主序依次排列的。有两种处理方法：
a)按照b.item中三元组的次序依次在a.item中找到相应的三元组进行转置。
换句话说，按照矩阵M的列序来进行转置。为了找到M的每一列中所有的非零元素，需要对其三元组表a.item从第一行起整个扫描一遍，由于a.item是以M的行序为主序来存放每个非零元的，由此得到的恰是b.item应有的顺序。
b)按照a.item中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。这种方法称为矩阵的快速转置。如果能预先确定矩阵M中每一列(即T中每一行)的第一个非零元在b.item中应有的位置，那么在对a.item中的三元组依次作转置时，便可直接放到b.item中恰当的位置上去。为了确定这些位置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.item中应有的位置。需要附设num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有：
?cpot[1]?1?[col?1]?cpot[col]?cpot[col?1]?num
(5)广义表
2?col?a.nu广义表的定义:广义表是线性表的推广的概念。广义表一般记作：
LS=(a1,a2,?,an)
其中LS为广义表的名称，n是长度。在线性表的定义中，ai只限于是单个元素，而在广义表的定义中， ai可是单个元素，也可广义表，分别称为LS的原子和子表。当广义表非空时，第一个元素称为LS的表头，称其余元素组成的表为LS的表尾。 广义表试例：
A=( ) A是一个空表，其长度为零
B=(e) B是只有一个原子e，其长度为1
C=(a,(b,c,d)) C的长度为2，两个元素分别为原子a和子表(b,c,d) D=(A,B,C) D的长度为3,3个元素都是列表，将子表的值代入后，有
D=(( ),(e),(a,(b,c,d)))
E=(a,E) 这是一个递归的表，它的长度为2。E相当于一个无限的列表E=(a,(a,(a,?))) 广义表的特点:
广义表的元素可以是子表，而子表的元素还可以是子表。广义表是一个多层次的结构。
广义表可以其他广义表所共享，其可以通过子表的名称来引用。 广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。 任何一个非空的广义表其表头可能是原子，也可能是子表，而其表尾必定为子表。
广义表的存储结构：
广义表的链式存储结构:由于广义表中的元素可具有不同的结构，因此难以采用顺序存储结构表示，而通常采用链式存储结构，每个元素可用一个结点表示。 结点结构:
①表结点
②原子结点
类型定义:
typedef emum {ATOM,LIST} ElemTag; typedef struct GLNode {
ElemTag tag; //共公部分，用于区分原子和表结点 union { //原子结点和表结点的联合部分 AtomType atom; //原子结点的值域 struct {struct GLNode *hp,*tp;}ptr; //ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表
尾
};
}*Glist; //广义表类型 （二）基本要求
(1) 了解数组的两种存储表示方法，并掌握数组在以行为主序的存储结构中的地
址计算方法；
(2) 掌握特殊矩阵压缩存储时的下标变换公式；
(3) 了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀
疏矩阵时进行矩阵运算采用的处理方法； (4) 掌握广义表的结构特点及其存储表示方法。 （三）重点、难点
重点：
本章重点掌握数组在以行或列为主序的存储结构中的地址计算方法、特殊矩阵进行压缩存储时的下标变换公式和三元组表示稀疏矩阵情况下的矩阵运算。 难点：
三元组表示稀疏矩阵时进行矩阵运算(如矩阵的转置)采用的处理方法； （四）作业及课外学习要求：
(1) 假设有二维数组A[1..6,0..7]，每个元素用相邻的6个字节存储，存储器按
字节编址。已知A的起始存储位置(基地址)为1000，计算：(1)数组A的体积(即存储量)；(2)数组A的最后一个元素A[6][7]的第一个字节的地址。 (2) 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，
另设三元组表C存放结果矩阵。
本知识点的讲授和学习，可以支撑“毕业要求1工程知识”中的“指标点1.1和1.2能够运用数学与自然科学基础知识，理解软件工程中涉及的相关科学原理；能够运用软件工程基础知识，解决复杂软件工程中涉及的相关工程问题”，使学生掌握将工程基础知识和本专业的基本理论知识向结合，锻炼学生的工程实践能力，并为后续课程的学习奠定理论基础。
第6章 树和二叉树 (10学时) （一）基本内容： （1）树的定义和基本术语
树的定义：
树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归定义。 常用术语：
结点：数据元素的内容及其指向其子树根的分支统称为结点。 结点的度：结点的分支数。 终端结点（叶子）：度为0的结点。 非终端结点：度不为0的结点。 结点的层次：树中根结点的层次为1，根结点子树的根为第2层，以此类推。 树的度：树中所有结点度的最大值。
树的深度：树中所有结点层次的最大值。
有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得
互换，则称为有序树，否则称为无序树。
森林：是m（m≥0）棵互不相交的树的集合。
在树结构中，结点之间的关系又可以用家族关系描述，定义如下： 孩子、双亲结点：子树的根称为这个结点的孩子，而这个结点又被称为孩子
的双亲。
子孙：以某结点为根的子树中的所有结点都被称为是该结点的子孙。 祖先：从根结点到该结点路径上的所有结点。 兄弟：同一个双亲的孩子之间互为兄弟。 堂兄弟：双亲在同一层的结点互为堂兄弟。 （2）二叉树的定义和性质
二叉树的定义：二叉树是另一种树形结构。它与树形结构的区别是： （a）每个结点最多有两棵子树； （b）子树有左右之分。
二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。
满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。 完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的
满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1－n的结点位置一一对应，则称这棵二叉树为完全二叉树。
二叉树的性质：
性质1：在二叉树的第i层上最多有2i-1个结点（i≥1）。 性质2：深度为K的二叉树最多有2K-1个结点（K≥1）。
性质3：对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的
结点个数为n2，则n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为 ?log2n?+1。其中，?log2n? 的
结果是不大于log2n的最大整数。
性质5：对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右
的顺序进行编号，则对任意一个结点i （1≤i≤n），都有：
如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲
结点的编号为 ?i/2?。
如果2i>n，则结点i没有左孩子(结点i为叶子结点)；否则其左孩子
结点的编号为2i。
如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。 （3）二叉树的存储结构
二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。
顺序存储结构:这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。
链式存储结构:在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。 （4）二叉树的遍历
二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。