有关网站开发的知识,微擎 网站开发工具,百度网站内容,网站两侧广告目录
3.1.1 引子#xff08;顺序查找#xff09;
什么是树
查找
3.1.2 引子 二分查找例子(BinarySearch)
二分查找
3.1.3 引子 二分查找实现
二分查找代码
二分查找的启示
3.1.4 树的定义
一些基本术语#xff1a;
3.1.5 树的表示 3.1.1 引子#xff08;顺序查找…目录
3.1.1 引子顺序查找
什么是树
查找
3.1.2 引子 二分查找例子(BinarySearch)
二分查找
3.1.3 引子 二分查找实现
二分查找代码
二分查找的启示
3.1.4 树的定义
一些基本术语
3.1.5 树的表示 3.1.1 引子顺序查找
什么是树
在客观世界上许多事物存在层次关系。如人类社会的家谱、社会组织管理结构、省市县乡镇的分级计算机中为了还原这种结构使用了树这种数据结构。
那么为什么要使用这种层次结构因为分层组织在数据管理方面有更高的效率
下面以数据管理的基本操作之一查找为例来分析如何实现有效的查找
查找 实质根据某个给定的关键词K从集合R中找出与关键词K相同的数据 1. 静态查找
定义集合中的数据是固定的。没有插入和删除对数据集的操作只有查找。——比如一本出版字典实现一般使用数组存放数据方法顺序查找
2. 动态查找
定义集合中数据是动态变化的。对数据集的操作有查找、插入和删除。——比如一个论文数据库
顺序查找详解实际上就是遍历时间复杂度O(n)
typedef struct LNode *List;
struct LNode{ElementType Element[MaxSize];int length;
};int SequentialSearch(List Tbl,ElementType K)
{//遍历ElementType查找关键字为K的数据元素int i;Tbl-Element[0] K;//建立哨兵预先设立边界值而不需要每次都判断for(i Tbl-Length; Tbl-Element[i] ! K; i--);//查找成功返回下标不成功返回0return i;
}//不用哨兵的
int SequentialSearch(List Tbl,ElementType K)
{int i;//两个退循环条件i控制边界tbl检测是否相等for(i Tbl-Length; i0 Tbl-Element[i] ! K; i--);return i;
} 3.1.2 引子 二分查找例子(BinarySearch)
假设两个地点AB之间的高压电站有100w个从A向B输电某一天两个地方都突然停电了现在需要排查是哪里的电站出问题。如果一个一个排查过去平均需要50w次才能排查结束。如果先从最中央的一个电站开始排查再向断电的那一半的中间...每次折半查找那么只需要log2100000020次就可以排查完毕。
二分查找
前提数据元素的关键字需要是有序且连续存放退出条件1.初始时rightleft,结束时leftright二者错位说明查找失败2.查找成功返回 3.1.3 引子 二分查找实现
二分查找代码
//函数参数表为存放着数据的列表Tbl和要找的元素K
int BinarySearch(List Tbl, ElementType K)
{//定义左中右标识变量赋初值,-1为方便返回NoFoundint left,right,mid,NoFound -1;//初始左右边界先让左边界为最左侧元素右边界为表尾left 1;right Tbl-length;while(left right){mid (left right)/2;//若中值大于要找的元素Kif(K Tbl-Element[mid]){right mid - 1;//说明应该往左半侧找把右边界更新为此时的中值-1即可}else if(K Tbl-Element[mid]){left mid 1;}else{return mid;}}//如果找到了会提前退出循环没找到会返回NoFound即-1return NoFound;
}
这个算法的时间复杂度是对数级的O(logN)
二分查找的启示
由二分查找判断元素的顺序可以绘制出如下判定树 从图中可以发现
每个结点需要查找的次数刚好等于这个结点所在的层数查找次数的上限是这个判定树的深度如果有n个结点那么判定树的深度为[log2(N)]1平均查找次数ASL (每层个数*层数之和)/总结点数。此树ASL (12*24*34*4)/113
那么如果直接将数据存储成树这样的形式会不会对数据的查找更有裨益呢当然会。之后我们就将讲到查找树这种存储形式。 3.1.4 树的定义 树(Tree)n(n0)个结点构成的有限集合 空树n0即没有结点。其对应的是非空树。 对于任意一颗非空树它具备以下性质 树中有一个称为根Root的特殊结点用r表示 其余结点可分为m(m0)个互不相交的有限集T1、T2、...、Tm其中每个集合本身也是一棵树称为原来树的子树(SubTree) 非树
子树之间有相交
树—— 一种保证结点联通方式最小的连接方式
子树之间不能相交除根结点以外每个结点有且仅有一个父结点一颗N个结点的树有N-1条边 一些基本术语
结点的度结点子树个数有几个直接相连的子结点树的度树的所有结点中最大的度数树所有结点里子树最多的那一项子树的个数叶结点(Leaf)度为0的结点父结点(Parent)有子树的结点是其子树的根节点的父结点子结点(Child)也称孩子节点。若A结点是B结点的父结点则称B结点是A结点的子结点。兄弟结点(Sibiling)具有同一父结点的各结点彼此是兄弟结点路径和路径长度从结点n1到nk的路径为一个结点序列n1,n2,...,nk,ni是ni1的父结点。路径所包含边的个数为路径的长度。祖先结点(Ancestor)沿树根到某一结点路径上所有结点都是这个结点的祖先结点。层数高的是层数低的祖先子孙结点(Descendant)某一结点的子树中的所有结点是这个结点的子孙结点的层次(Level)规定根结点在一层其它任一结点的层数是其父结点层数1树的深度(Depth)树中所有结点中的最大层次是这棵树的深度 3.1.5 树的表示
知道了树的抽象结构和基本概念下面我们需要能在计算机中表示树这种结构。首先我们肯定是需要在已有的结构中选择一种。 使用结构链表 看似结构很像实则在实现过程中每个结点指向其他结点的个数并不相同结构不一定能囊括所有情况。那如果将所有的结点都设计成一个形式比如都留3个指针域有的结点可能只用一个但这样能保证结点结构统一处理方便。但当树的体积非常庞大时候这样的做法会造成巨大的浪费。
有一种较好的表示方法同样是使用结构链表的形式所有结点结构相同。每个结点包含两个指针域一个是FirstChild指向这个结点的第一个孩子结点另一个是NextSibiling指向它的下一个兄弟结点。这种形式的树我们称为二叉树(链表)
