目录
树是由N(N>=0)个结点组成的一个具有层次关系的有限集合,因此树是一种逻辑上为非线性的数据结构。
树的根结点没有前驱结点,除根结点以外的所有结点有且只有一个前驱结点。在树中所有结点可以与零个或者多个后继结点。子树是不相交的,并且在N个结点的树中有N-1条边,因此树是递归定义的。
树最常见的结构是孩子兄弟表示法,每一个结点都有存储数据的变量,指向左边第一个孩子结点的指针和指向右边相邻兄弟结点的指针。
二叉树是一种特殊的树结构,其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于
2 的结点);并且二叉树的子树有左右之分,其次序不能任意颠倒,因此二叉树是有序树。若将其左、右子树颠倒,则成为另一棵不同的二叉树。即使树中结点只有一棵子树,也要区分它是左子树还是右子树。
与树相似,二叉树也以递归的形式定义。二叉树是N(N≥ 0)个结点的有限集合:
二叉树的五种基本形态:
几个特殊的二叉树:
二叉树的性质:
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。所以在实际使用中只有堆才会使用数组来存储。
二叉树的链式存储有两种表示方式,一种是二叉链,也就是每一个结点中有存储数据的变量,指向左孩子的指针与指向右孩子的指针;另一种是三叉链,也就是每一个结点中有存储数据的变量,指向左孩子的指针,指向右孩子的指针以及指向双亲的指针。
堆是一种数据结构,它与操作系统的虚拟进程地址空间中的堆是两回事。堆的逻辑结构是一颗特殊的完全二叉树,它要求双亲结点中的数据要大于或者小于其左右孩子结点中的数据;而堆的物理结构是由动态数组来实现的。
堆可以分为大根堆与小根堆。设数组a存储着堆中的数据,大根堆就是双亲结点的数据大于其左右孩子结点的数据(a i >= a 2*i + 1 && a i >= a 2*i + 2);小根堆就是双亲结点的数据小于其左右孩子结点的数据(a i <= a 2*i + 1 && a i <= a 2*i + 2)。
根据堆的性质我们可以知道,在大根堆中根结点的数据值是最大的,而在小根堆中根结点的数据值是最小的。
堆的基本操作,先用大根堆进行演示,操作小根堆与操作大根堆的思路是一样的,只需要将判断大小条件修改一下就可以进行大小根堆的切换。
因为堆的物理结构是数组,所以堆的初始化与销毁与动态顺序表一样。
入堆的操作就是先将数据插入到数组最后一个位置上,数据插入完成后再进行向上调整。向上调整的基本思路就是让插入的数据与其双亲结点的数据进行比较,如果插入的数据比其双亲结点的数据大,则将插入的数据与双亲数据交换,直到有双亲数据比插入数据大或者插入数据已经换到根结点就停止。
void HeapPush(Heap* ph, HeapDataType x) // 入堆
{
assert(ph);
if (ph->size == ph->capacity) // 检查容量
{
int newCapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
HeapDataType* tmp = (HeapDataType*)realloc(ph->a, sizeof(HeapDataType) * newCapacity);
if (!tmp)
{
perror("realloc fail\n");
return;
}
ph->a = tmp;
ph->capacity = newCapacity;
}
ph->a[ph->size++] = x; // 先将数据插入数组
AdjustUp(ph->a, ph->size-1); // 进行向上调整
}
出堆的操作不能直接将根结点的数据删除,否则会把数据打乱,造成堆不再是大根堆,而且再次调整成大根堆的代价很大。正确的出堆操作是将根结点的数据与数组中最后一个结点的数据进行交换,然后将换上来的结点数据与其左右孩子进行调整直到大根堆复原。向下调整的基本思路是先选出左右孩子中数据大的那一个结点(小根堆就是选出小的那一个结点),再将数据大的那一个结点与其双亲结点比较,如果选出来的那一个数据大的孩子结点比双亲结点的数据大则进行交换,直到换上来的结点成了叶子结点或者选出的那一个孩子结点比换上来的结点小就停止交换。
void HeapPop(Heap* ph) // 出堆
{
assert(!HeapEmpty(ph)); // 如果堆为空则不能出堆
assert(ph);
HeapSwap(&(ph->a[0]), &(ph->a[ph->size - 1])); // 最后一个结点与根结点交换
ph->size--;
AdjustDown(ph->a, 0, ph->size); // 进行向下调整
}
堆排序的操作只要用到向上调整与向下调整的思想就可以。堆排序的操作分为两步:第一步建堆,建堆可以向下建堆也可以向上建堆,但向下建堆的效率比向上建堆的效率高。第二步就是排序,将堆顶的元素与最后一个元素交换,交换之后采用向下调整让次大或者次小的元素到堆顶,依次往复,直到有序。所以,如果需要升序就建大根堆,需要降序就建小根堆。
// 头文件
typedef int HeapDataType; // 数据类型
typedef struct Heap
{
HeapDataType* a; // 数组首地址
int size; // 数据个数
int capacity; // 数组容量
}Heap;
void HeapSwap(HeapDataType* n1, HeapDataType* n2);
void HeapPrint(Heap* ph);
void HeapInit(Heap* ph);
void HeapDestroy(Heap* ph);
void HeapPush(Heap* ph, HeapDataType x);
void HeapPop(Heap* ph);
HeapDataType HeapTop(Heap* ph);
bool HeapEmpty(Heap* ph);
int HeapSize(Heap* ph);
void AdjustDown(HeapDataType* a, int parent, int size);
void AdjustUp(HeapDataType* a, int child);
void HeapSort(HeapDataType* a, int size);
// 源文件
void HeapSwap(HeapDataType* n1, HeapDataType* n2) // 交换结点的数据
{
assert(n1 && n2);
HeapDataType tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}
void HeapPrint(Heap* ph) // 打印
{
assert(ph);
for (int i = 0; i < ph->size; i++)
{
printf("%d ", ph->a[i]);
}
printf("\n");
}
void HeapInit(Heap* ph) // 初始化
{
assert(ph);
ph->a = NULL;
ph->size = ph->capacity = 0;
}
void HeapDestroy(Heap* ph) // 销毁
{
assert(ph);
if (ph->a)
{
free(ph->a);
ph->a = NULL;
ph->size = ph->capacity = 0;
}
}
void AdjustUp(HeapDataType* a, int child) // 向上调整
{
assert(a);
int parent = (child - 1) / 2; // 获取双亲结点的下标
// while (parent >= 0)这样的条件会多进入一次循环,并且if (a[child] >= a[parent])这样判断会死循环
while (child > 0) // 如果孩子结点的下标小于等于0则停止,调整完成
{
if (a[child] >= a[parent]) // 如果插入的数据小于其双亲数据则进行调整否则跳出循环
{
HeapSwap(&(a[child]), &(a[parent])); // 交换数据
child = parent; // 迭代
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(Heap* ph, HeapDataType x) // 入堆
{
assert(ph);
if (ph->size == ph->capacity) // 检查容量
{
int newCapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
HeapDataType* tmp = (HeapDataType*)realloc(ph->a, sizeof(HeapDataType) * newCapacity);
if (!tmp)
{
perror("realloc fail\n");
return;
}
ph->a = tmp;
ph->capacity = newCapacity;
}
ph->a[ph->size++] = x; // 先将数据插入数组
AdjustUp(ph->a, ph->size-1); // 进行向上调整
}
void AdjustDown(HeapDataType* a, int parent, int size) // 向下调整
{
assert(a);
int child = parent * 2 + 1; // 先假设左孩子大
while (child < size) // 结束条件不能是while (parent < size)否则会越界
{
if ((child + 1 < size) && a[child + 1] > a[child]) // 如果右孩子比左孩子大则孩子下标改为右孩子
{
child++;
}
if (a[child]>a[parent]) // 孩子比双亲大则交换
{
HeapSwap(&(a[parent]), &(a[child])); // 交换
parent = child; // 迭代
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//void AdjustDown(HeapDataType* a, int parent, int size) // 向下调整--递归
//{
// assert(a);
//
// int child = parent * 2 + 1;
//
// if (child + 1 < size && a[child + 1] < a[child])
// {
// child++;
// }
//
// if (child >= size)
// {
// return;
// }
//
// if (a[child] < a[parent])
// {
// HeapSwap(&(a[child]), &(a[parent]));
// }
//
// AdjustDown(a, child, size);
//}
void HeapPop(Heap* ph) // 出堆
{
assert(!HeapEmpty(ph)); // 如果堆为空则不能出堆
assert(ph);
HeapSwap(&(ph->a[0]), &(ph->a[ph->size - 1])); // 最后一个结点与根结点交换
ph->size--;
AdjustDown(ph->a, 0, ph->size); // 进行向下调整
}
HeapDataType HeapTop(Heap* ph) // 获取根的数据
{
assert(!HeapEmpty(ph));
assert(ph);
return ph->a[0]; // 根的数据就是存储在数组的第一个位置
}
bool HeapEmpty(Heap* ph) // 判空---若堆为空返回true否则返回false
{
assert(ph);
return ph->size == 0;
}
int HeapSize(Heap* ph) // 数据元素的个数
{
assert(ph);
return ph->size;
}
void HeapSort(HeapDataType* a, int size) // 堆排序---大根堆
{
建堆---向上建堆 O(N*logN)
//for (int i = 1; i < size; i++)
//{
// AdjustUp(a, i);
//}
// 建堆---向下建堆 O(N)
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, i, size);
}
// 排序 O(N*logN)
int end = size - 1;
while (end > 0)
{
HeapSwap(&(a[0]), &(a[end]));
AdjustDown(a, 0, end);
end--;
}
}
文章浏览阅读1.6w次,点赞8次,收藏41次。生活中我们无时不刻不都要在网站搜索资源,但就是缺少一个趁手的资源搜索网站,如果有一个比较好的资源搜索网站可以帮助我们节省一大半时间!今天小编在这里为大家分享5款超厉害的资源搜索网站,每一款都可以让你的资源丰富精彩!网盘传奇一款最有效的网盘资源搜索网站你还在为找网站里面的资源而烦恼找不到什么合适的工具而烦恼吗?这款网站传奇网站汇聚了4853w个资源,并且它每一天都会持续更新资源;..._最全资源搜索引擎
文章浏览阅读4.5k次,点赞5次,收藏18次。阅读测试程序,设计一个Book类。函数接口定义:class Book{}该类有 四个私有属性 分别是 书籍名称、 价格、 作者、 出版年份,以及相应的set 与get方法;该类有一个含有四个参数的构造方法,这四个参数依次是 书籍名称、 价格、 作者、 出版年份 。裁判测试程序样例:import java.util.*;public class Main { public static void main(String[] args) { List <Book>_6-1 book类的设计java
文章浏览阅读613次,点赞28次,收藏27次。相比于以前的传统手工管理方式,智能化的管理方式可以大幅降低学校的运营人员成本,实现了校园导航的标准化、制度化、程序化的管理,有效地防止了校园导航的随意管理,提高了信息的处理速度和精确度,能够及时、准确地查询和修正建筑速看等信息。课题主要采用微信小程序、SpringBoot架构技术,前端以小程序页面呈现给学生,结合后台java语言使页面更加完善,后台使用MySQL数据库进行数据存储。微信小程序主要包括学生信息、校园简介、建筑速看、系统信息等功能,从而实现智能化的管理方式,提高工作效率。
传统上用户登陆状态会以 Session 的形式保存在服务器上,而 Session ID 则保存在前端的 Cookie 中;而使用 JWT 以后,用户的认证信息将会以 Token 的形式保存在前端,服务器不需要保存任何的用户状态,这也就是为什么 JWT 被称为无状态登陆的原因,无状态登陆最大的优势就是完美支持分布式部署,可以使用一个 Token 发送给不同的服务器,而所有的服务器都会返回同样的结果。有状态和无状态最大的区别就是服务端会不会保存客户端的信息。
文章浏览阅读784次。发表于10小时前| 2674次阅读| 来源TechCrunch| 19 条评论| 作者Jon EvansiOSAndroid应用开发产品编程语言JavaObjective-C摘要:即便Android市场份额已经超过80%,对于开发者来说,使用哪一个平台做开发仍然很难选择。本文从开发环境、配置、UX设计、语言、API、网络、分享、碎片化、发布等九个方面把Android和iOS_ios 开发角度
搜索引擎的发展历史可以追溯到20世纪90年代初,随着互联网的快速发展和信息量的急剧增加,人们开始感受到了获取和管理信息的挑战。这些阶段展示了搜索引擎在技术和商业模式上的不断演进,以满足用户对信息获取的不断增长的需求。
文章浏览阅读990次。对象特性是指控制对象的输出参数和输入参数之间的相互作用规律。放大系数K描述控制对象特性的静态特性参数。它的意义是:输出量的变化量和输入量的变化量之比。时间常数T当输入量发生变化后,所引起输出量变化的快慢。(动态参数) ..._控制对象特性
文章浏览阅读5.7w次,点赞50次,收藏276次。FRP搭建内网穿透1.概述:frp可以通过有公网IP的的服务器将内网的主机暴露给互联网,从而实现通过外网能直接访问到内网主机;frp有服务端和客户端,服务端需要装在有公网ip的服务器上,客户端装在内网主机上。2.简单的图解:3.准备工作:1.一个域名(www.test.xyz)2.一台有公网IP的服务器(阿里云、腾讯云等都行)3.一台内网主机4.下载frp,选择适合的版本下载解压如下:我这里服务器端和客户端都放在了/usr/local/frp/目录下4.执行命令# 服务器端给执_locyanfrp
文章浏览阅读687次。题目:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=93745#problem/A题意:给出r*c的01矩阵,可以翻转格子使得0表成1,1变成0,求出最小的步数使得每一行中1的个数相等,每一列中1的个数相等。思路:网络流。容量可以保证每一行和每一列的1的个数相等,费用可以算出最小步数。行向列建边,如果该格子是_uva12534
文章浏览阅读504次。1、Let's Encrypt 90天,支持泛域名2、Buypass:https://www.buypass.com/ssl/resources/go-ssl-technical-specification6个月,单域名3、AlwaysOnSLL:https://alwaysonssl.com/ 1年,单域名 可参考蜗牛(wn789)4、TrustAsia5、Alpha..._csdn alphassl免费申请
文章浏览阅读1.6k次。测试算法的性能 很多时候我们需要对算法的性能进行测试,最简单的方式是看算法在特定的数据集上的执行时间,简单的测试算法性能的函数实现见testSort()。【思想】:用clock_t计算某排序算法所需的时间,(endTime - startTime)/ CLOCKS_PER_SEC来表示执行了多少秒。【关于宏CLOCKS_PER_SEC】:以下摘自百度百科,“CLOCKS_PE_算法性能测试
文章浏览阅读1.2k次。fromhttps://towardsdatascience.com/finding-lane-lines-simple-pipeline-for-lane-detection-d02b62e7572bIdentifying lanes of the road is very common task that human driver performs. This is important ..._lanedetectionlite