|
|
|
《数据结构》自学方法指导 |
|
|
来源： 发布时间：2006-5-29 16:56:48 点击： |
由教材我们可以看出,不能只凭等式sq->front=sq->rear来判定循环队列的状态是空或是满。为此，有两种处理的方法：其一是另设一个标志位以区别队列是"空"还是"满"；其二是少用一个元素空间，以尾指针加1 等于头指针作为队列满的标志。其中第一种方法应用较普及，具体来说就是利用标志来区分造成sq->front=sq->rear的情况是在入队时发生或是在出队时发生。不难看出，前一种情况是队满，而后一种情况是队空。具体的算法参照书上的例子。
总而言之，栈的出入操作都在线性表的一端进行，而队列的出入操作分别在线性表的两端进行，这就是队列和栈最本质的区别。
14.二叉树的存储结构和遍历算法
二叉树(binary tree)是一种特殊的树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树主要有以下几个性质：
性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。
性质2：深度为k的二叉树至多有2k-1个结点，(k≥1)。
性质3：对任何一棵二叉树(如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为└1og2 n┘+1。
性质5：如果对一棵有n个结点的完全二叉树(其深度为└1og2n┘+ 1)的结点按层序编号(从第 1 层到第└log2n┘ + 1层，每层从左到右)，则对任一结点i(1≤i≤n),有
(1)如果i＝1，则结点i是二叉树的根，无双亲；如果i> 1，则其双亲PARENT(i)是结点(i/2)。
(2)如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。
(3)如果2i＋1＞n，则结点i 无右孩子；否则其右孩子RCHILD(i)是结点2i+ 1。
回顾二叉树的递归定义可知，二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L,D,R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD六种遍历二叉树的方案。若限定先左后右，则只有前三种情况，分别称之为先(根)序遍历，中(根)序遍历和后(根)序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。
先序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
(1)访问根结点；
(2)先序遍历左子树；
(3)先序遍历右子树。
中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
(1)中序遍历左子树；
(2)访问根结点；
(3)中序遍历右子树。
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
(1)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根结点。
遍历算法的语言描述形式随存储结构的不同而不同。我们在这里仅以先序遍历为例来进行详细说明。
void Preorder(node * bt){
/* 前序遍历二叉树递归算法 */
if (bt) {
visit(bt); //访问根结点
Preorder(bt->lchild); //访问左子树
Preorder(bt->rchild);//访问右子树
}
}
用二叉树来表示表达式 a+b*c/(d-e)-f*g
◇如果按照中序遍历此二叉树，得到的中序序列就是a+b*c/d-e-f*g
◇如果改用先序序列遍历，就将得到-+a/*bc-de*fg
◇而后序遍历将得到abc*de-/+fg*-
15.树和二叉树的关系
由于二叉树和树都可用二叉链表作为存储结构，则可以把二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。我们称该树与二叉树是相对应的。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，同样可导出森林和二叉树的对应关系。下图表示的是一棵树及其对应的二叉树。
这个一一对应的关系导致森林或树与二叉树可以相互转换，其形式如下： 一、森林转换成二叉树
如果F＝(T1,T2 …,Tm)是森林，则可按如下规则转换成一棵二叉树B＝(root，LB，RB)。
(1)若F为空，即m=0，则B为空树；
(2)若F非空，即m≠0，则B的根root即为森林中第一棵树的根ROOT(T1);B的左子树LB是从T1中根结点的子树森林F1={Tl1,Tl2，…，Tlm1} 转换而成的二叉树；其右子树 RB是从森林F'={T2，T3，…，Tm}转换而成的二叉树。
16.哈夫曼树及哈夫曼算法：
假设有n个权值{w1，w2，…，wn ｝，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为w，，则其中带权路径长度WPL最小的二叉树称。做最优二叉树或哈夫曼树。
哈夫曼(Huffman)最早给出了一个带有一般规律的算 法，俗称哈夫曼算法。现叙述如下：
(1)根据给定的n个权值…1，w2，…，wJ构成n棵二叉树的集合F＝{T1，T2，…，Tn)，其中每棵二叉树T1中只有一个带权为wi 的根结点，其左右子树均空。
(2)在下中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
(3)在下中删除这两棵树，同时将新得到的二叉树加入下中。
(4)重复(2)和(3)，直到下只含一棵树为止。这棵树便是哈夫曼树。
17.图的几个难以理解的基本概念
(1)连通图--对无向图，任意Vi<>Vj的两个顶点之间都存在路径
(2)强连通图--对有向图，任意Vi<>Vj的两个顶点之间都存在Vi→Vj，Vj→Vi的路径
(3)连通分量--无向图的极大连通子图
(4)强连通分量--有向图的极大连通子图
判断一个无向图是否为连通图或连通分量很容易，而判断一个 有向图是否为强连通图或强连通分量则比较困难，可采用下列方法，若一个有向图是强连通图或强连通分量，则一定能找到包含所有顶点在内的若干独立的有向回路。
(5)网路--边或弧带有权值的图，又称为带权图。
(6)生成树--图的无环连通子图
在一个图中究竟会有多少边或弧呢？我们先看看无向图：最少当然可能只有0条边，最多时即当任何两个顶点之间都有相联系的边时，边数将达到n*(n-1)/2。具有n*(n-1)/2条边的无向图我们称之为完全图。对于有向图，e的取值范围是0到n(n-1)，我们也把有n*(n-1)条弧的有向图称为有向完全图。对那些边或弧很少的图称之为稀疏图，反之称稠密图。有的时候，图的边或弧上还带有一个相关的数(称为权)，表示从一个顶点到另一个顶点的耗费，这种图就叫做网。
我们一般采用一些改进的方式来存储图，常用的有邻接表和十字链表等。下面我们以邻接表为例来说明一下:
邻接表(adjacency list)是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(或以vi为尾的弧)。很自然的，每个结点将由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图上的位置，链域(nextarc)指示下一条边或弧 的结点；数据域(info)存储和边或弧相关的信息，如权值等。
每个链表上附设一个表头结点。在每个表头结点中，除了设有链域之外，还有存储顶点vi的名或其它有关信息的数据域(vexdata)。这些表头结点通常以顺序结构的形式存储，以便能够随机访问任一顶点的链表。
下面的图将告诉你邻接表是如何构造出来的。
十字链表(ortholgonal list)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。这些结点根据顶点和弧的联系关系交织成网状，请见下图：本新闻共 6页,当前在第 4页 1 2 3 4 5 6 |
|
|
|
