公司网站首页设计构想,做视频素材怎么下载网站,php做电子商城网站,网站ui标准文章目录 1 树1.1 树的概念与结构1.2 相关术语1.3 树的表示与运用场景1.3.1 运用场景 2. 二叉树2.1 概念与结构2.1.1 满二叉树2.1.2 完全二叉树 3. 顺序结构二叉树3.1 堆的引入3.1.1 概念与结构 3.2 功能实现3.2.1 堆的结构3.2.2 初始化、销毁 3.3 堆的插入数据3.3.1 向上调整算… 文章目录 1 树1.1 树的概念与结构1.2 相关术语1.3 树的表示与运用场景1.3.1 运用场景 2. 二叉树2.1 概念与结构2.1.1 满二叉树2.1.2 完全二叉树 3. 顺序结构二叉树3.1 堆的引入3.1.1 概念与结构 3.2 功能实现3.2.1 堆的结构3.2.2 初始化、销毁 3.3 堆的插入数据3.3.1 向上调整算法 3.4 堆是否为空3.5 删除堆顶数据3.5.1 向下调整算法3.5.2 获取堆顶数据3.5.2.1 求有效数据个数 3.6 向上(下)调整算法的复杂度比较3.6.1 向上调整算法时间复杂度3.6.2 向下调整算法时间复杂度 4. 代码实现 1 树
1.1 树的概念与结构
树是⼀种非线性的数据结构它是由 nn0 个有限结点组成⼀个具有层次关系的集合。 具有以下特点
具有根节点且根节点无前驱结点。除根结点外其余结点被分成 M(M0) 个互不相交的集合每⼀个集合又是⼀棵结构与树类似的子树。每棵子树的根结点仅有一个前驱结点但可以有多个互不相交的后驱结点。(若存在相交就是图了)
1.2 相关术语
子结点/孩子结点⼀个结点的子树的根结点称子结点 如上图B是A的子结点。父结点/双亲结点含有子结点的结点称为其子结点的父结点 如上图A是B的父结点。结点的度⼀个结点有几个子结点度就是多少如A的度为3F的度为0。树的度⼀棵树中最大的结点的度称为树的度 如上图树的度为3。叶子结点/终端结点度为 0 的结点称为叶结点 如上图 J、K、L… 等结点为叶结点。分支结点/非终端结点度不为 0 的结点 如上图 A、B、C、D… 等结点为分支结点。兄弟结点具有相同父结点的结点互称为兄弟结点(亲兄弟) 如上图 E、F 是兄弟结点。结点的层次从根开始定义起根为第 1 层根的⼦结点为第 2 层以此类推。树的高度或深度树中结点的最大层次 如上图树的高度为 4。结点的祖先从根到该结点所经分支上的所有结点如上图 A 是所有结点的祖先。子孙以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图所有结点都是A的子孙路径⼀条从树中任意节点出发沿父节点-子节点连接达到任意节点的序列如A到J的路径为A-B-E-J。森林由 mm0 棵互不相交的树的集合称为森林。
1.3 树的表示与运用场景
树的表示有很多种最常用的便是孩子兄弟表示法其很好地解决了结点和结点之间的关系。
struct TreeNode
{struct Node* child; // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data; // 结点中的数据域
};1.3.1 运用场景
文件系统是计算机存储和管理文件的⼀种方式它利用树形结构来组织和管理文件和文件夹。在文件系统中树结构被广泛应用它通过父结点和⼦结点之间的关系来表示不同层级的文件和文件夹之间的关联。
2. 二叉树
2.1 概念与结构
⼀棵二叉树是结点的⼀个有限集合该集合由⼀个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。 特点
不存在大于度大于2的结点二叉树有左右之分次序不能颠倒。
2.1.1 满二叉树
如果每⼀个层的结点数都达到最大值或满足结点总数是2k-1则这个二叉树就是满二叉树。 2k-1的公式推导 总的结点数20 21 22……2k-1 1 * (1 - 2k) / 1 - 2 2k-1
2.1.2 完全二叉树
规定根结点的层数为 1:
⼀棵非空二叉树的第i层上最多有 2i−1 个结点深度为 h 的二叉树的最大结点数是 2h − 1具有 n 个结点的满二叉树的深度 h log2 (n 1) ( log以2为底 n1 为对数) --满二叉树是特殊的完全二叉树。
3. 顺序结构二叉树
顺序结构存储是使用数组来存储在实现完全二叉树能减少空间浪费。
3.1 堆的引入
3.1.1 概念与结构 对于序号i对应的结点,若i0则(i-1)/2为父结点若i0则无父结点若2*i1n,则对应其左孩子若2*i2n,则对应其右孩子。
3.2 功能实现
3.2.1 堆的结构
由于堆底层是用数组实现的因此相似于顺序表其结构定义如下
typedef int HPDataType;
//定义堆的结构
typedef struct HeapNode
{HPDataType* arr;int size;//有效数据个数int capacity;//容量
}HP;3.2.2 初始化、销毁
这些代码实现已经在顺序表中介绍到。
//堆的初始化
void HPInit(HP* php)
{assert(php);php-arr NULL;php-size php-capacity 0;
}
//堆的销毁
void HPDesTroy(HP* php)
{assert(php);if (php-arr)free(php-arr);php-arr NULL;php-capacity php-size 0;
}3.3 堆的插入数据
熟悉了堆的概念与结构后我们清楚堆要不就是大根堆要不就是小根堆。问题在于插入数据后我们如何通过代码实现化成大根堆或者小根堆的形式由此我们提出了向上(下)调整算法也会带大家分析这两种算法哪种更好。
3.3.1 向上调整算法 3.4 堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}3.5 删除堆顶数据
在删除堆顶数据时先要判断堆是否为空因此采用assert。删除堆顶数据后如何让其再次成为大(小)根堆。 由此我们引入了向下调整算法。
3.5.1 向下调整算法
前提左右⼦树必须是⼀个堆才能调整。
3.5.2 获取堆顶数据
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php-arr[0];
}3.5.2.1 求有效数据个数
int HPSize(HP* php)
{assert(php);return php-size;
}3.6 向上(下)调整算法的复杂度比较
3.6.1 向上调整算法时间复杂度 根据大O表示法则O(n*log2n) -- 详见算法复杂度篇章
3.6.2 向下调整算法时间复杂度 根据大O表示法可见时间复杂度为O(n)
因此向下调整算法的时间复杂度更优。
4. 代码实现 Heap.h #define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
#includetime.htypedef int HPDataType;
//定义堆的结构
typedef struct HeapNode
{HPDataType* arr;int size;//有效数据个数int capacity;//容量
}HP;//堆的初始化
void HPInit(HP* php);
//堆的销毁
void HPDesTroy(HP* php);
//堆的插入数据
void HPPush(HP* php, HPDataType x);
//删除堆顶数据
void HPPop(HP* php);
//获取堆顶数据
HPDataType HPTop(HP* php);
//判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);//向上调整
void AdjustUp(HPDataType* arr, int child);
//向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
//交换
void Swap(int* x, int* y);Heap.c #define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.h//堆的初始化
void HPInit(HP* php)
{assert(php);php-arr NULL;php-size php-capacity 0;
}
//堆的销毁
void HPDesTroy(HP* php)
{assert(php);if (php-arr)free(php-arr);php-arr NULL;php-capacity php-size 0;
}
//交换
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
//向上调整
void AdjustUp(HPDataType* arr, int child)
{int parent (child - 1) / 2;while (child 0){//:大堆//:小堆if (arr[child] arr[parent]){//交换Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else {break;}}
}
//堆的插入数据
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否不足if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : 2 * php-capacity;//空间不足需要增容HPDataType* tmp (HPDataType*)realloc(php-arr, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(realloc fail!);exit(1);}//realloc成功php-arr tmp;php-capacity newCapacity;}php-arr[php-size] x;//向上调整AdjustUp(php-arr, php-size - 1);php-size;
}//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{int child parent * 2 1;while (child n){if (child 1 n arr[child] arr[child 1]){child;}//建小堆//建大堆if (arr[parent] arr[child]){Swap(arr[parent], arr[child]);parent child;child parent * 2 1;}else {break;}}
}
//删除堆顶数据
void HPPop(HP* php)
{assert(!HPEmpty(php));Swap(php-arr[0], php-arr[php-size - 1]);php-size--;//向下调整AdjustDown(php-arr, 0, php-size);
}
//获取堆顶数据
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php-arr[0];
}
//判空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}
//求size
int HPSize(HP* php)
{assert(php);return php-size;
}test.c #define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.hvoid test()
{HP hp;HPInit(hp);HPPush(hp, 1);HPPush(hp, 3);HPPush(hp, 2);HPPush(hp, 4);/*HPPop(hp);HPPop(hp);HPPop(hp);HPPop(hp);*/while (!HPEmpty(hp)){printf(%d , HPTop(hp));HPPop(hp);}HPDesTroy(hp);
}void test01()
{int arr[] { 14,51,31,21,23,32 };int n sizeof(arr) / sizeof(arr[0]);HP hp;HPInit(hp);//调用push将数组中的数据建堆for (int i 0;i n;i){HPPush(hp, arr[i]);}int i 0;while (!HPEmpty(hp)){arr[i] HPTop(hp);HPPop(hp);}for (int i 0;i n;i){printf(%d , arr[i]);}HPDesTroy(hp);
}int main()
{test();test01();//int arr[] { 14,51,31,21,23,32 };//int n sizeof(arr) / sizeof(arr[0]);Bubblesort(arr,n);//HeapSort(arr,n);//for (int i 0;i n;i)//{// printf(%d , arr[i]);//}//CreateDate();TopK();return 0;
}
