第二章软件基础知识课件.ppt

《第二章软件基础知识课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4数组2.4.1数组的顺序存储结构2.4.2规则矩阵的压缩2.4.3一般稀疏矩阵的表示2.4.1数组的顺序存储结构1.二维数组以行为主的顺序存储2.二维数组以列为主的顺序存储1.下三角矩阵的压缩存储2.4.2规则矩阵的压缩用长度为n(n＋1)/2的一维数组B，一行接一行存放A中下三角部分的元素。2.对称矩阵的压缩存储3.三对角矩阵的压缩存储用一个长度为3n－2的一维数组B存放三条对角线上的元素1.稀疏矩阵的三列二维数组表示2.4.3一般稀疏矩阵的表示(1)非零元素所在的行号i；(2)非零元素所在的列号j；(3)非零元素的值V。即每一个非零元素可以用下列三元组表示：（i

2、，j，V）（1，3，3）（1，8，1）（3，1，9）（4，5，7）（5，7，6）（6，4，2）（6，6，3）（7，3，5）（7，8，8）（1，3，3）（1，8，1）（3，1，9）（4，5，7）（5，7，6）（6，4，2）（6，6，3）（7，3，5）2.5树与二叉树2.5.1树的基本概念2.5.2二叉树及其基本性质2.5.3二叉树的存储结构2.5.4二叉树的遍历树的概念树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的

3、有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。树的表示bacghdefij树结构具有明显的层次关系，树是一种层次结构。根结点在第一层，如a结点(node)结点的度(degree)结点的子树个数叶子(leaf)结点度为0的结点树的度(degree)结点所处层次(level)根结点的层数为1，其余结点的层数为其父结点的层数加1树的高度（深度）(depth)树中结点的最大层数二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，

4、该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i0)二叉树的性质证明：i=1时，有2i-1=20=1，成立假定：i=k时性质成立；当i=k+1时，第k+1的结点至多是第k层结点的两倍，即总的结点个数至多为2×2k-1=2k故命题成立性质2高度为k的二叉树最多有2k-1个结点。(k1)证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质1可得二叉树的结点数至多为：20+21+22+23+…+2k-1=2k－1性质3对任何一棵二叉树,如果其叶结点

5、个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1证明：1、结点总数为度为0的结点加上度为1的结点再加上度为2的结点：n=n0+n1+n22、另一方面，二叉树中一度结点有一个孩子，二度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n=n1+2n2+13、两式相减，得到：n0=n2+1定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树。除最后一层外，每一层上的所有结点都有两个结点定义2完全二叉树(CompleteBinaryTree)除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。性质4具

6、有n个结点的完全二叉树的高度为log2n+1证明：设完全二叉树的高度为h，则有2h-1-11,则i的双亲为i/2若2*i<=n,则i的左子女为2*i；否则，i无左子女，必定是叶子结点，二叉树中i>n/2的结点必定是叶子结点若2*i+1<=n,则i的右子女为2

7、*i+1，否则，i无右子女若i为奇数,且i不为1，则其左兄弟为i-1，否则无左兄弟；若i为偶数,且小于n，则其右兄弟为i+1，否则无右兄弟i所在层次为log2(i)+11243568910711121314151617完全二叉树的数组表示一般二叉树的数组表示二叉树的存储数组表示单支树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。链表表示二叉树链表表示的示例二叉链表的静态结构树结点的描述typedefintdatatype;typedefstructnode{datatypedat