数据结构专升本资料第四周.doc

第五章 多维数组和广义表5.1 数组的定义一、数组的定义数组（Arrays）是由一组类型相同的数据元素构造而成的。它的每个元素由一个值和一组下标确定。二维数组每个元素aij均属于两个向量：第i行的行向量和第j列的列向量。最多可以有两个直接前驱和两个直接后继。二、 数组的顺序存储结构数组的顺序存储结构指的是用一组连续的存储单元依次存放数组元素。 l 行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。 l 列优先顺序：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。 二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占d个存储单元，则aij的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)n+j-1d 对应C语言的二维数组：DataType Amn; 数组Amn的两个下标的下界均为0，上界分别为m-1、n-1，每个数据元素占k个存储单元，二维数组中任一元素ai,j的存储位置可由下列公式确定。 loci,j=loc0,0+( n * i + j ) * k 其中，loc0,0是A00的存储位置，它是该二维数组的起始地址。loci,j是Aij的存储位置。这个式子确定了C语言的二维数组元素的位置和下标的关系。5.2 矩阵的压缩存储实际工程问题中推导出的数组常常是高阶、含大量零元素的矩阵，或者是些有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储.n 压缩存储：相同值的多个非零元素占用一个存储单元；零元素不分配存储单元。 一、特殊矩阵所谓特殊矩阵（Special Matrices）是指非零元素或零元素的分布有一定规律的矩阵。 几种特殊矩阵的压缩存储： l 对称矩阵 在一个n阶方阵A中，若元素满足下述性质：aij=aji0i，jn-1 则称A为对称矩阵。如图所示：存储元素为：1,5,0,1,8,9,3,0,2,5,7,0,6,1,3，共15个。n 对于对称矩阵,可以为每一对对称元素分配一个存储空间,因此将n*n个元素压缩存放到 n（n+1）/2 个单元中.n 一般,可以将下三角的元素存放在一维数组s0,n(n+1)/2-1中 。则sk和矩阵元素aij之间存在一一对应的关系，： i（i+1）/2+j 当ij,下三角 k = j（j+1）/2+i 当ij ,上三角0i，jn-1l 三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主角线）中的元素均为常数c。下三角矩阵正好相反，它的主对角线上方均为常数c。在多数情况下，三角矩阵的常数c为零。 上三角矩阵中，sak和aij的对应关系是： k=i*(2n-i+1)/2+j-i 当ij /常数c的存储位置下三角矩阵中，sak和aij的对应关系是： l 对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如图所示： 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。二、稀疏矩阵设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵（Sparse Matrix）。 当用三元组来表示非零元时，对稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。 1、三元组表按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素的值外，还必须记下它所在行和列的位置（i,j）。即用一个三元组（i,j, aij ）唯一确定了矩阵A的一个非零元素。若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表，我们将该线性表的顺序存储结构称为三元组表（List of 3-tuples）。 三元组表类型描述： 第六章 树和二叉树6.1 树的概念一、树的定义与表示法树（Tree）是n(n0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： 有且仅有一个特定的称为根（Root）的结点； 其余的结点可分为m(m0)个互不相交的子集T1，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树（Subtree）。 树的递归定义刻化了树的固有特性，即一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。 从该定义可知：只有一个结点的树，该结点为根结点；多个结点的树，除根结点之外，它的M棵子树T1，T2，Tm也是树，且互不相交。 二、树的表示法：树形表示法 嵌套集合表示法 凹入表表示法 广义表表示法 三、树的有关术语l 结点：树的结点包含一个数据元素及若干指向其子树的分支。l 度（Degree）：一个结点拥有的子树数称为该结点的度。 l 树的度：一棵树的度是指该树中结点的最大度数。 l 叶子（Leaf）和分支结点：度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点。除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。 l 双亲（Parents）和孩子（Child）：树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。 l 兄弟（Sibling）和堂兄弟：同一个双亲的孩子称为兄弟。双亲在同一层的结点互为堂兄弟。l 祖先（Ancestor）和子孙（Descendant）：一个结点的祖先是指从树的根到该结点所经分支上的所有结点（包括根结点）。一个结点的子树的所有结点都称为该结点的子孙。 l 结点的层数（Level）：是从根起算，设根的层数为1，其余结点的层数等于其双亲结点的层数加1。 l 树的高度（Height）：树中结点的最大层数称为树的高度或深度（Depth）。 l 有序树（Ordered Tree）和无序树（Unordered Tree）：若将树中每个结点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树；否则称为无序树。 在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。l 森林（Forest）：是m(m0)棵互不相交的树的集合。 对树中每个结点而言，其子树的集合即为森林；反之，给一个森林加上一个结点，使原森林的各棵树成为所加结点的子树，便得到一棵树。6.2 二叉树一、 二叉树的定义l 二叉树（Binary Tree）是n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。若二叉树为空集，则称为空二叉树。二叉树是有序的，它的每个结点至多只有两棵子树，且有左、右之分，不能互换；左右子树也可以是空二叉树。l 二叉树的基本形态空二叉树 仅有根结点的二叉树 右子树为空的二叉树 左子树为空的二叉树 左右子树均非空的二叉树 二、二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i1）。性质2： 深度为k的二叉树至多有2k-1个结点（k1）。性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n21三、 二叉树的特殊形态l 满二叉树（Full Binary Tree）：一棵深度为k且有2k-1个结点的二叉树。 特点1：二叉树的所有分支结点都存在左子树和右子树 特点2：二叉树的所有叶子结点都在同一层上l 完全二叉树（Complete Binary Tree）：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。 特点1：叶子结点只可能在层次最大的两层上出现 特点2：对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为 L 或 L+1 性质4： 具有n个结点的完全二叉树的深度为log2n+1性质5： 如果对一棵有n个结点的完全二叉树（其深度为log2n+1）的结点按层序编号（从第1层到第log2n+1层，每层从左到右），则对任一结点i（1in），有 如果 i=1，则结点i是二叉树的根，无双亲；如果 i1，则其双亲PARENT(i)是结点i/2。 如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。 如果2i+1n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。如果i为奇数且不为1，则其左兄弟的编号是i-1；否则，无左兄弟。如果i为偶数且小于n，则其右兄弟的编号是i+1；否则，无右兄弟。四、 二叉树的存储结构1、 顺序存储结构就是用一组连续的存储单元来存放二叉树的各结点信息。 顺序存储结构可以用一个一维数组来顺序存储二叉树中所有结点的数据信息，并通过数组元素的下标关系来反映完全二叉树中结点间的逻辑关系。一般的二叉树也必须按完全二叉树的形式来存储，这将造成存贮的浪费。在最坏的情况下，一个深度为k且只有k个结点的单支树（树中无度为2的结点）却需2k-1个存储分量。 2、 链式存储结构二叉树的链式存储结构是用链来建立树中结点之间的关系，二叉树的这种链式存储结构我们通常称为二叉链表。 在含有n个结点的二叉链表中有n+1个空链域。6.3遍历二叉树遍历（Traversal）：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。 从二叉树的递归定义可知，二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L,D,R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD六种遍历二叉树的方案。若限定先左后右，则只有前三种情况，分别称之为前序遍历，中序遍历和后序遍历。 l 前序遍历 前序遍历（Preorder Traversal）亦称先序遍历，定义为： 若二叉树为空，则空操作；否则，执行下列步骤： （1）访问根结点 （2）遍历左子树 （3）遍历右子树 l 中序遍历 中序遍历（Inorder Traversal）定义为： 若二叉树为空，则空操作；否则，执行下列步骤： （1）遍历左子树 （2）访问根结点 （3）遍历右子树 l 后序遍历 后序遍历（Postorder Traversal）定义为： 若二叉树为空，则空操作；否则，执行下列步骤：（1）遍历左子树 （2）遍历右子树 （3）访问根结点 /*前序遍历二叉树*/void Preorder(BinTree T)if(T)printf(%c,T-data);/*访问结点*/Preorder(T-lchild);Preorder(T-rchild);/*中序遍历二叉树*/void Inorder(BinTree T)if(T)Inorder(T-lchild);printf(%c,T-data);/*访问结点*/Inorder(T-rchild);/*后序遍历二叉树*/void Postorder(BinTree T)if(T)Postorder(T-lchild);Postorder(T-rchild);printf(%c,T-data);/*访问结点*/按层次遍历二叉树对二叉树进行遍历还可以从上到下，从左到右按层次进行。二叉树用链式存储结构表示时，按层遍历的算法实现（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；算法：void LevelOrder(BTree *BT) if (!BT) exit; InitQueue(Q); p=BT; /初始化/访问根结点，并将根结点入队 Visite(p); EnQueue(&Q,p); while (!QueueEmpty(Q) /当队非空时重复执行下列操作 DeQueue(&Q,&p); /出队 if (p-Lchild) Visite(p-Lchild) ; EnQueue(&Q,p-Lchild); /处理左孩子 if (p-Rchild) Visite(p-Rchild);EnQueue(&Q,p-Rchild); /处理右孩子 l 构造二叉链表 基于先序遍历构造二叉链表算法。 /*构造二叉链表*/void CreateBinTree(BinTree &T)char ch;scanf(%c,&ch);if(ch= )T=NULL;elseT=(BinTNode *)malloc(sizeof(BinTNode