做设计找素材的+网站有哪些中国创业项目网

当前位置： 首页 > news >正文

做设计找素材的+网站有哪些,中国创业项目网,手机网站建设需求文档,自己创业做原公司一样的网站树 树的概念和结构 结构 在我们将堆之前#xff0c;我们先来了解一下我们的树。 我们的堆是属于树里面的一种#xff0c; 树是一种非线性结构#xff0c;是一种一对多的一种结构#xff0c;也就是我们的一个节点可能有多个后继节点#xff0c;当然也可以只有一个或者没…树 树的概念和结构 结构 在我们将堆之前我们先来了解一下我们的树。 我们的堆是属于树里面的一种 树是一种非线性结构是一种一对多的一种结构也就是我们的一个节点可能有多个后继节点当然也可以只有一个或者没有。我们的这些有限结点组成一个具有层次关系的集合我们把它叫做树是因为他的结构和一颗倒挂的数很像。 在我们的最上面的节点叫做根节点他没有前驱。我们树的其他节点具有0个或者多个后继节点。但是在只有一个前驱节点。因此树是递归定义的。数的子树是不能相交的。相交的话就是不是我们的树了是另外一种结构–图。 树的一些概念 结点的度一个结点含有的子树的个数称为该结点的度 如上图A的为6 叶结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等结点为叶结点 非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等结点为分支结点 双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点 孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点 兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点 树的度一棵树中最大的结点的度称为树的度 如上图树的度为6 结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推 树的高度或深度树中结点的最大层次 如上图树的高度为4 堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点 结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先 子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林 树的表示 我们的树由于太过于有多个后继节点导致我们的树在构建的时候会比较麻烦我们可以用我们的链表来表示也可以用数组来表示。 链式 对与我们用链式来存储我们的树的话就需要我们去去存储他的后继节点但是我们这里的节点的每个后继节点数目不同我们治理有一下个很好的方法—–孩子兄弟表示法。 就是我们只存下我们的第一个孩子节点在定义一个兄弟节点指向他的兄弟 节点这样当我们的节点具有同一个节点时候我们第一个孩子节点就会是这个孩子链的头结点我们沿着我们的兄弟指针就可以找到双亲的所有孩子节点。 typedef int DataType; struct Node {struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域 }; 数组 我们这里用数组存储主要是利用了双亲和孩子节点的下标关系。主要是存储二叉树的。 二叉树的相关知识 一棵二叉树是结点的一个有限集合该集合: 或者为空由一个根结点加上两棵别称为左子树和右子树的二叉树组成 特点 3. 二叉树不存在度大于2的结点 4. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 一张有意思的图
*特殊的二叉树 ** 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的性质 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有 个结点.若规定根结点的层数为1则深度为h的二叉树的最大结点数是 .2^(对任何一棵二叉树, 如果度为0其叶结点个数为 n1, 度为2的分支结点个数为n2 ,则有 n2n1 1对于孩子和双亲的关系如果我们给每个节点都标都标上序号的话如果为空我们也还是要为那个空节点保留下这个序号我们就可以发现一个双亲和他们的孩子节点的下标关系:左孩子父亲1右孩子父亲2 由于我们整数激素那取整 的关系我们利用孩子节点来求我们的父亲就可以写成父亲孩子-1/2若规定根结点的层数为1具有n个结点的满二叉树的深度h . (ps 是log以2为底n1为对数)。 数组存储二叉树 我使用数组存储还是利用了二叉树的那条双亲和孩子的序号关系我的通过计算下标就可以找到他们的双亲节点和孩子节点。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 如果我们的二叉树是一颗完全二叉树的话我们可以考虑用数组去存储这样操作起来会方便很多。 当然我们的树越接近满二叉树我们的数组存储效率会很高空间浪费的会很少。但是我们的二叉树的不是一个完全二叉树的话我们的存储效率会低很多我峨嵋你要按照双亲的关系来存储。那么那些空姐带你的地方我们是不可以存储值的。 下面我们要讲的堆就是一颗完全二叉树适合用我们的数组去存储。 堆 堆的概念及结构 如果有一个关键码的集合K { … }把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中并满足 且 ( 且 ) i 012…则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。 总来说就是我们的双亲节点的值总是大于小于我们的孩子节点 如果双亲总是大于我们的孩子节点就是大堆 双亲小于孩子节点的话就是小堆 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 第一个是小堆第二个是大堆。 堆的性质 堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。 堆的实现 我们实现我们的堆采用的是数组去存储的维护我们堆的结构体 typedef int HPDataType; typedef struct Heap {HPDataType _a;int _size;//数组里面有多少个有效数值int _capacity;//数组的空间大小 }Heap; 我们下面将我们堆实现的一些接口 void HeapInit(Heap* php); // 堆的销毁 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的删除 void HeapPop(Heap* hp); // 取堆顶的数据 HPDataType HeapTop(Heap* hp); // 堆的数据个数 int HeapSize(Heap* hp); // 堆的判空 int HeapEmpty(Heap* hp); //进行调整小堆,向上调整 void AdjustUp(HPDataType* data, int child); //交换 void Swag(int* a, int* b); //向下调整 void AdjustDown(HPDataType* data, int parents, int size);初始化 我们的初始化就是给我们结构体中的数组开辟空间不开也行给我们的指针置空。 代码 //堆的初始化 void HeapInit(Heap* php) {assert(php);php-_a (HPDataType*)malloc(sizeof(HPDataType) * 4);php-_capacity 4;php-_size 0; }堆的销毁 我们的销毁就是将我们的申请的空间还给我们的操作系统就行我们这里主要申请的空间就是我们的数组只需要将我们的数组释放就行。 代码 // 堆的销毁 void HeapDestory(Heap* hp) {assert(hp);free(hp-_a);hp-_capacity 0;hp-_size 0; }堆的向下调整算法 我们的向下调整算法有一个前提是L他们需要左右子树必须是堆才好去调整。 int array[] {27,15,19,18,28,34,65,49,25,37};我们这里建小堆 当我们的左右子树不是堆的时候就会导致他们的父子关系变化。 我们向下建堆的思想是我们的根和他的孩子中较小的进行比较如果他大于那个较小的孩子就进行交换交换后该节点再继续和他交换后的新的孩子进行比较如此一直到我们的这个节点小于他的较小的孩子节点或者一直到超出我们的书的最后的一个节点的下标(就是在我们树的最后一层他没有孩子节点了)。 例子 我们的小堆有一个特点是我们的根节点是堆中最小的数值这是因为我们的父亲节点一定小于孩子节点。 我峨嵋你大堆就是根接待你是数值最大的。 代码 //向下调整小堆 void AdjustDown(HPDataType* data, int parents,int size) {assert(data);int child parents * 2 1;while (child size-1){if ( child 1 size - 1 data[child] data[parents * 2 2])child parents * 2 2;if (data[child] data[parents]){//双亲比孩子大交换Swag(data[child], data[parents]);}else {break;}parents child;child parents * 2 1;} }堆的向上调整算法 我们的向上调整算法是从我们的最后一个节点来进行的。 我们找到最后一个节点的父亲通过他们的下标的关系我们将该节点进行比较如果我们的节点比他的父亲节点小就进行交换我们再继续和他的新父亲节点进行比较一直到他的父亲节点小于他或者我们这个节点来到了我们根节点的位置。 这里需要注意的循环条件的判定如果你是0的话就会导致死循环当年我们该节点来到我们的根节点位置下标为0南无我们用公式去算他的父亲节点0-1/2由于取整的特点这个的值还会是0并不会小于0
代码 //向上调整(小堆) void AdjustUp(HPDataType* data,int child) {int parents (child - 1) / 2;while (child 0){if (data[child] data[parents]){//双亲大于孩子要交换Swag(data[child], data[parents]);child parents;parents (parents - 1) / 2;}else {break;}} }往堆中插入 我们往堆中插入是先将我们的插入的元素放在我们的数组的最后一个位置。我们插入了之后还要是我们的数组仍然是个堆我们还要进行向上调整的操作我们只需要调整刚进入的新的元素。形成一个新的堆。 代码 // 堆的插入 void HeapPush(Heap* hp, HPDataType x) {assert(hp);int child hp-_size;//判断空间是否充足if (hp-_capacity hp-_size){hp-_capacity hp-_capacity * 2;hp-_a (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * hp-_capacity);if (hp NULL){perror(hp realloc!);return;}}//插入新的数据hp-_a[hp-_size] x;hp-_size;//小堆进行调整AdjustUp(hp-_a,child);}堆中元素的删除 我们删除元素如果删除我们的叶子节点显然是很容易的所以我们要删除的我们的根节点。 但是如果我们的将我们的根节点删除的话父子关系也会变乱出现了你的兄弟节点成为了你的父亲节点所以我们要先将我们的根节点和我们最后一个节点进行交换再将我们的数组的大小改变并不需要我们将值进行改变。交换之后我们的数组也不是一个堆了但是他的左右子树仍旧是一个小堆这是我们就可以进行向下调整重新将我们的数组变成一个新的堆。 代码 // 堆的删除 void HeapPop(Heap* hp) {//将根上面的值与我们的最后一个节点交换在进行调整assert(hp);Swag(hp-_a[0], hp-_a[hp-_size - 1]);hp-_size–;AdjustDown(hp-_a,0, hp-_size);}取堆顶的数据 我们只需要将我们的数组中下标为0的元素返回就行 代码 HPDataType HeapTop(Heap* hp) {assert(hp);return hp-_a[0]; }堆的判空和数据个数 我们结构体中定义了一个size变量来记录我们元素的个数只需要对这个只进行判断是否为0 // 堆的数据个数 int HeapSize(Heap* hp) {assert(hp);return hp-_size; } // 堆的判空 int HeapEmpty(Heap* hp) {assert(hp);return hp-_size 0 ? 1 : 0; }