二叉树详讲（一）---完全二叉树、满二叉树、堆

1.树的概念及其结构

1.1树的概念

树是一种非线性数据结构，是一种种抽象数据类型，旨在模拟具有树状结构的节点之间的层次关系。一颗树由诺干个点和诺干条边组成。每棵树只有一个根节点，根节点向下延申又有子节点和叶子节点，叶子节点是树中度数为0的节点。

 这样一种由根节点向下扩展延申至叶子节点的结构看上去像是一颗倒着的树

其实我觉得从某种角度来说，其结构更像是树的根

除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继 因此，树是递归定义的。

 值得注意的是，在一棵树中，子树之间不能有交集。

1.2 树的相关概念 

概念含义
节点的度一个节点含有子树的个数 如B节点的度数为3
叶节点度为0的节点 如H、I、F、G节点
分支节点度不为0的节点，如B节点等
父节点一个节点的前驱节点 如B是E的父节点，C是G的父节点
子节点一个节点的后继节点 如H、I是E的子节点
兄弟节点 有同一个父节点的节点互为兄弟节点，如D、E、F互为兄弟节点，因为它们有同一个爸爸
树的度一棵树中，最大的节点的度称为树的度，如上图树的度为3
树的高度（深度）从根节点开始，根为第一层，其子节点为第二层，依次向下递增 上图树的高度为4
堂兄弟节点父节点不同但父节点的父节点相同，这样的节点互为堂兄弟节点，如F和G
节点的祖先从根节点到该节点路径的所有节点都是该节点的祖先节点，如E的祖先节点有B和A
子孙节点以该节点为根的子树的中任一节点都是该节点的子孙节点，如E、H、I节点都是B的子孙节点
森林由诺干棵互不相交的树的集合

1.3树的表示

由于树的结构是非线性的，相比于线性表来说表示就比较复杂，除了要存储值域以外，还要存下所有子节点甚至父节点的关系。

1.3.1双亲表示法

双亲表示法是指每个节点都有一个指向其父节点的指针，根节点的指针为NULL.

typedef int DataType;
struct Node
{
 struct Node* parent; // 指向父节点
 DataType _data; // 结点中的数据域
};

1.3.2孩子兄弟表示法

孩子兄弟表示法是指每个节点都存有指向第一个左孩子的指针和其兄弟的指针

 

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

1.3.3孩子表示法

每个节点都有存放其所有孩子的指针

typedef int DataType;
struct Node
{
 struct Node* Child1[N]; // 指针数组，存放所有孩子节点的指针
 DataType _data; // 结点中的数据域
};

 1.4树在实际中的运用（表示文件系统的目录树结构）

我们可以看到，我们的根目录就是树的根节点，其下面的各个文件夹都是它的子树

2.二叉树

2.1二叉树的概念

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

 2.2二叉树的递归定义

二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

上图是一颗二叉树，有根节点，和其左右子树组成 

其实任何一棵二叉树的组成都由这样的根节点、左右子树组成，左右子树可能为空。

任何一棵二叉树都由一下几种情况复合而成

2.3特殊的二叉树

2.3.1满二叉树

满二叉树除了最后一层的节点度数为0，其余节点的度数都为2，外观上看像一个三角形

给出一棵满二叉树： 

 

求满二叉树的节点数目

由于其特殊性质，我们很容易得出满二叉树的节点总数为2^k-1（假设k是满二叉树的高度）

求满二叉树的深度

假设有N个节点，其深度就为log2(N+1)

国外的满二叉树定义

 值得注意的是，美国及其国际上关于满二叉树的定义与国内是不一样的。

美国NIST定义满二叉树是满二叉树的节点度数要么为0，要么为2.

 

国际上认为上图也是满二叉树，但是不符合国内定义的满二叉树。 

2.3.2完全二叉树

 完全二叉树除了最后一层的节点度数可以不为2，其余节点的度数都为2，且度数不为2的节点数目最多只有一个。满二叉树是一种特殊的完全二叉树。

给出一颗完全二叉树： 

求完全二叉树的节点数目

 假设一颗完全二叉树的深度为k,那么这棵树的节点数量就是[2^(k-1),2^k-1）

满二叉树与完全二叉树的关系：

完全二叉树包含满二叉树，满二叉树是一种特殊的完全二叉树

2.4二叉树的性质（公式）（重要）

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^（i-1) 个结点.

二叉树每一层的节点容量是一个公比为2的等比数列，2^0 、2^1 、2^2.....2^(i-1)

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^i-1.

根据等比求和公式，S=a（1-q^n）/(1-q),将q=2,a=1，n=i 带入可得S(i)=2^i-1

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1

假设有一棵二叉树n个顶点，那么可得一定有n-1条边。

n0表示节点度数为0的数目，n1表示度数为1的节点数目，n2表示度数为2的节点的数目

每一个度数为2的节点的出边都有两条，度数为1的节点出边有一条，省略度数为0的节点。所以总共的边数就是度数为2的节点与度数为1的节点的出边的总和，即为2*n2+n1

于是我们可根据边数关系列出等式  n-1=2*n2+n1...(1)

又根据n=n1+n2+n0...(2),联立等式（1）（2）消掉n，可得n2=n0-1。即n0=n2+1得证。

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= .log(2)(n+1)  (ps：log(2)(n+1) 是log以2 为底，n+1为对数)

根据性质2，深度为h的满二叉树的节点数目n=S(h)=2^h-1,可得h=log2(n+1).

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：

1. 若i>0，i位置节点的双亲（父亲节点）序号：(i-1)/2,i=0，i为根节点编号，无双亲节点

2. 若2i+1<n,存在左孩子序号：2i+1；若2i+1>=n（数组下标[0,n-1]）,无左孩子

3. 若2i+2<n,存在右孩子序号：2i+2；若2i+1>=n,无右孩子

图上的节点数n=7.

节点编号6的父节点编号为（6-1）/2=2

节点编号3的父节点编号为（3-1）/2=1

节点编号2的左孩子节点编号为2*2+1=5(5<n)

节点编号3没有左孩子，因为2*3+1=7，7=n

 2.5题目训练

注：以下题目中n0表示节点度数为0的数目，n1表示度数为1的节点数目，n2表示度数为2的节点的数目。h代表高度（深度），n代表节点总数目

题目1

某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A 不存在这样的二叉树

B 200

C 198

D 199

解析 ：

根据上述二叉树的性质，n0=n2+1,所以得到n0等于199+1=200，所以答案选B

题目2

在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A n

B n+1

C n-1

D n/2

解析：

首先容易想到n0+n1+n2=2n..... (1)

然后根据性质，n0=n2+1 ......(2)

联立（1）（2）得：n0=（2n-n1+1）/2

因为n1只能为1或者0，且n0是个整数，所以（2n-n1+1）一定得是个偶数才能整除2，所以n1一定为1。即得n0=2n/2=n.所以选A

 题目3

一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）

A 11

B 10

C 8

D 12

解析：

因为完全二叉树的节点数目跟高度的关系为n=[2^(h-1),2^h-1），所以易得

h>=log2(n+1)<==>  h<=10

h<log2(n+1) <==> h>9

由此可得h=10,所以答案选B

 2.6 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2.6.1顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树或者满二叉树，因为容易有空间的浪费。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

 

 可以看到，顺序存储非完全二叉树会造成空间的浪费。

2.6.2链式存储

二叉树树的链式存储结构指的是用链表来表示一棵二叉树，用链来表示节点之间的关系。

链表中每个结点通常由三个域组成，一个是存放数据的值域，另外两个则是分别存放左右孩子地址的指针域。

 

代码： 

typedef int DataType;
struct Node
{
 struct Node* _leftChild; // 指向左孩子结点
 struct Node* _rightChild; // 指向右孩子结点
 DataType _data; // 结点中的数据域
};

 3.堆

3.1堆的概念

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：ki<=k(2i+1)  且ki >=k(2i+2) ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

3.2堆的性质

1.堆中某个节点的值一定是不大于或者不小于其孩子节点的值（不大于其孩子节点是小根堆，不小于则是大根堆）

2.堆总是一颗完全二叉树

3.3判断是否为堆

给出以下关键字序列，判断是否为堆

1. 100,60,70,50,32,65 

100的下标为0，是根节点，因为100>60&&100>70,可以判断，如果该关键字序列是堆的话，也一定是大根堆。继续往后看，关键字60和70的左右孩子都不大于其父亲的值，所以该序列是堆，且为大根堆。

2. 60,70,65,50,32,100

 由前3个序列可以判断，如果该关键字序列是堆的话，也一定是小根堆。继续往后看，关键字70的左右孩子的值50，32都小于它，不符合小根堆性质。所以，这个序列不是堆。

 3.4堆的实现（c语言）

给出结构体定义：


typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;//顺序表
	int _size;//当前堆的节点数量
	int _capacity;//当前顺序表的容量
}Heap;

3.4.1向下调整法

我们用顺序表存储一颗完全二叉树，并且将这个完全二叉树维护成一个小根堆（大根堆同理），每当要插入节点，我们首先将其插在顺序表尾部，再从后往前，从子节点到父节点依次调整，如果子节点的值大于父节点的值，那么就进行交换，始终维护父节点不大于子节点的这一性质。

部分代码：
//向上调整
static void AdjustUp(HPDataType* a, int pos) {//pos为插入数据的下标
	assert(a);
	int child = pos;//从pos开始向上调整
	int parent = (pos - 1) / 2;//找到其父节点
	while (child > 0) {//递归向上找父节点，并判断是否要交换
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;//更新其父节点与子节点
			parent = (child - 1) / 2;
		}
		else {//一遇到不需要交换时，就立即停下来
			break;
		}
	}
}

 3.4.2向下调整法

当需要删除堆顶元素时，我们先交换堆顶元素和顺序表的最后一个元素，再把最后一个元素的值删除，这样变相的删除了堆顶元素。但是由于不知道此时堆顶元素是否符合小根堆的性质，则需要向下调整。从堆顶元素开始，判断是否不大于其孩子元素，如果否，为了保持小根堆的性质，需要与值最小的孩子交换，从上往下，从父节点到孩子节点，观察是否还需要交换，不需要则退出，或者是孩子节点>=size(没有孩子了)时退出。

代码：

//向下调整
static void AdjustDown(HPDataType* a, int Size) {//Size为当前顺序表的大小
	assert(a);
	int parent = 0;
	int child = parent * 2 + 1;
	while (child < Size) {//调整方式与向上调整一致
		if (child+1<Size&&a[child + 1] < a[child]) {
			child++;
		}
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

 3.4.3建立堆的时间复杂度

O(n)（n为节点的数量）

3.4.4堆的代码实现

3.4.4.1Heap.h头文件

定义结构体类型，声明各种函数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;
//堆的初始化
void InitHeap(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
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);
 3.4.4.2Heap.c源文件

具体实现各种函数功能，包括向上调整与向下调整函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void Swap(HPDataType* a, HPDataType* b) {
	HPDataType t = *a;
	*a = *b;
	*b = t;
}

//向上调整
static void AdjustUp(HPDataType* a, int pos) {//pos为插入数据的下标
	assert(a);
	int child = pos;//从pos开始向上调整
	int parent = (pos - 1) / 2;//找到其父节点
	while (child > 0) {//递归向上找父节点，并判断是否要交换
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;//更新其父节点与子节点
			parent = (child - 1) / 2;
		}
		else {//一遇到不需要交换时，就立即停下来
			break;
		}
	}
}
//向下调整
static void AdjustDown(HPDataType* a, int Size) {//Size为当前顺序表的大小
	assert(a);
	int parent = 0;
	int child = parent * 2 + 1;
	while (child < Size) {//调整方式与向上调整一致
		if (child+1<Size&&a[child + 1] < a[child]) {
			child++;
		}
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

//堆的初始化
void InitHeap(Heap* hp) {
	assert(hp);
	hp->_capacity = hp->_size = 0;
	hp->_a = NULL;
}
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n) {
	assert(hp && a);
	for (int i = 0; i < n; i++) {
		HeapPush(hp, a[i]);
	}
	//hp->_a = a;
	//hp->_capacity = hp->_size = n;
}
// 堆的销毁
void HeapDestory(Heap* hp) {
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

// 堆的插入
void HeapPush(Heap*hp, HPDataType x) {
	assert(hp);
	if (hp->_capacity == hp->_size) {
		//printf("hp->_capacity==%d", hp->_capacity);
		int newcap = hp->_capacity ==0?4:hp->_capacity*2;
		//printf("hp->_capacity==%d", newcap);
		HPDataType* temp = realloc(hp->_a,sizeof(HPDataType)* newcap);
		if (temp == NULL) {
			perror("realloc:fail");
		}
		hp->_a = temp;
		hp->_capacity = newcap;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
	AdjustUp(hp->_a, hp->_size - 1);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp) {
	assert(hp);
	return hp->_a[0];
}

// 堆的删除
void HeapPop(Heap* hp) {
	assert(hp);
	Swap(&hp->_a[0], &(hp->_a[hp->_size - 1]));
	hp->_size--;
	AdjustDown(hp->_a, hp->_size);
}
//获取数据个数
int HeapSize(Heap* hp){
	return hp->_size;
}

// 堆的判空
int HeapEmpty(Heap* hp) {
	return hp->_size == 0;
}
3.4.4.3test.c源文件

测试文件，测试各种函数功能是否正常

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
Heap hp;

int main() {
	InitHeap(&hp);
	int arr[10] = { 2,1,0,3,4,7,5,1,2,10 };
	HeapCreate(&hp, arr, 10);
	//printf("%d", HeapTop(&hp));
	/*for (int i = 0; i < 10; i++) {
		HeapPush(&hp, arr[i]);
	}*/
	while (!HeapEmpty(&hp)) {
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestory(&hp);
	return 0;
}

运行结果 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/188888.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

20231125硬盘电源线5线不能识别日立10T的硬盘的解决方法

20231125硬盘电源线5线不能识别日立10T的硬盘的解决方法

20231125硬盘电源线5线不能识别日立10T的硬盘的解决方法 2023/11/25 23:00 缘起&#xff0c;在拼多多买了2片10TB的7200rpm的日立二手硬盘。 型号&#xff1a;日立 mar-2018 10T硬盘 接上电脑&#xff0c;硬盘感觉在转动了【正常上电了。】 但是X99主板&#xff0c;在WIN10下就…
阅读更多...
人工智能面面观

人工智能面面观

人工智能简介 人工智能&#xff08;Artificial Intelligence&#xff0c;简称AI&#xff09;是一门研究如何使计算机能够模拟和执行人类智能任务的科学和技术领域。它致力于开发能够感知、理解、学习、推理、决策和与人类进行交互的智能系统。人工智能的背景可以追溯到上世纪50…
阅读更多...
DeepWalk代码实战-维基百科词条图嵌入可视化

DeepWalk代码实战-维基百科词条图嵌入可视化

准备工作&#xff1a; 从爬虫网站中爬取维基百科See also关联词条&#xff1a;https://densitydesign.github.io/strumentalia-seealsology/ 维基百科网站&#xff1a;https://www.wikipedia.org/ 爬取过程&#xff1a; 下载 tsv 文件&#xff1a; import networkx as nx # 图…
阅读更多...
详解#define

详解#define

我们要知道&#xff0c;#define后面定义的标识符只进行替换而不进行计算&#xff0c;我们不能根据惯性自动给它计算了&#xff0c;这样可能会出错。 目录 1.关于#define 1.1#define定义标识符 1.2#define定义宏 1.3#define的替换规则 2.#和## 1.# 2.## 3.带副作用的宏参…
阅读更多...
信息收集小练习

信息收集小练习

信息收集小练习 本文章无任何恶意攻击行为&#xff0c;演示内容都合规无攻击性 演示如何绕过cdn获取真实ip 使用多地ping该网站 发现有很多ip地址&#xff0c;证明有cdn 此处使用搜索引擎搜索&#xff0c;得到ip 演示nmap工具的常用参数 此处以testfire.net为例 使用多地p…
阅读更多...
Android逆向实战 - MIUI调起三方应用系统拦截弹窗分析

Android逆向实战 - MIUI调起三方应用系统拦截弹窗分析

近期&#xff0c;发现在部分Android手机调起其他应用时&#xff0c;会弹出一个系统弹窗拦截调起&#xff0c;需要用户二次确认。经过内部众测&#xff0c;发现绝大多数是小米手机&#xff0c;而且跟Android版本没有直接关系&#xff0c;猜测是MIUI某次升级引入的功能。这篇文章…
阅读更多...
OpenCV入门教程

OpenCV入门教程

本文旨在让你快速入门opencv。 OpenCV OpenCV是计算机视觉中最受欢迎的库&#xff0c;最初由intel使用C和C 进行开发的&#xff0c;现在也可以在python中使用。该库是一个跨平台的开源库&#xff0c;是免费使用的。OpenCV库是一个高度优化的库&#xff0c;主要关注实时应用程…
阅读更多...
Another app is currently holding the yum lock； waiting for it to exit...

Another app is currently holding the yum lock； waiting for it to exit...

今天使用yum进行下载的时候报错 解决办法&#xff1a; 执行 rm -f /var/run/yum.pid 然后重新运行yum指令即可&#xff0c;发现已经可以正常下载啦&#xff01;
阅读更多...
VScode

VScode

一、VSCode设置中文 1、首先我们打开vscode&#xff0c;进入编辑页面后点击左边栏的图示图标进入“EXTENSIONS”面板 2、进入后&#xff0c;在上方搜索“Chinese”&#xff0c;搜索到中文&#xff08;简体&#xff09;后&#xff0c;点击“install”按钮。 3、等待自动下载安装…
阅读更多...
STK Components 基础篇

STK Components 基础篇

1.开发包 STK Components 访问AGI官网&#xff0c;注册并登录后&#xff0c;从官网下载开发包&#xff1a;https://support.agi.com/downloads/&#xff0c;下载成功后可以申请许可证&#xff0c;AGI会向你注册的邮箱地址发送有效期半年的使用授权许可文件&#xff08;lic文件…
阅读更多...
基于 STM32 的温度测量与控制系统设计

基于 STM32 的温度测量与控制系统设计

本文介绍了如何基于 STM32 微控制器设计一款温度测量与控制系统。首先&#xff0c;我们将简要介绍 STM32 微控制器的特点和能力。接下来&#xff0c;我们将详细讨论温度传感器的选择与接口。然后&#xff0c;我们将介绍如何使用 STM32 提供的开发工具和相关库来进行温度测量和控…
阅读更多...
ubuntu20.04配置OpenCV的C++环境

ubuntu20.04配置OpenCV的C++环境

ubuntu20.04配置OpenCV的C环境 这里以opencv-3.4.16为例 复现https://github.com/raulmur/ORB_SLAM2此项目&#xff0c;需安装opencv及其他依赖&#xff0c;可见README.md详情 1.下载opencv源代码 https://opencv.org/releases/ 2.下载OpenCV的扩展包opencv_contrib&#x…
阅读更多...
排序算法-----基数排序

排序算法-----基数排序

目录 前言 基数排序 算法思想 ​编辑 算法示例 代码实现 1.队列queue.h 头文件 2.队列queue.c 源文件 3.主函数&#xff08;radix_sort实现&#xff09; 算法分析 前言 今天我想把前面未更新完的排序算法补充一下&#xff0c;也就是基数排序的一种&#xff0c;这是跟…
阅读更多...
小程序如何禁止指定用户访问？如何设置指定用户才能访问？

小程序如何禁止指定用户访问？如何设置指定用户才能访问？

​有些商家为了价格保密或者实行严格的会员制等原因&#xff0c;希望小程序能够限制某些人的访问或者设置指定人员才能访问。这种功能在小程序中&#xff0c;怎么支持这些功能呢&#xff1f;下面具体介绍。 一、禁止指定用户访问 禁止指定用户访问&#xff0c;可以通过小程序…
阅读更多...
【三极管锯齿波电路】2022-3-23

【三极管锯齿波电路】2022-3-23

缘由以晶体管作恒流源的锯齿波电路工作原理? - 24小时必答区
阅读更多...
【数据结构】树与二叉树（廿六）：树删除指定结点及其子树（算法DS）

【数据结构】树与二叉树（廿六）：树删除指定结点及其子树（算法DS）

文章目录 5.3.1 树的存储结构5. 左儿子右兄弟链接结构 5.3.2 获取结点的算法1. 获取大儿子、大兄弟结点2. 搜索给定结点的父亲3. 搜索指定数据域的结点4. 删除结点及其左右子树a. 逻辑删除与物理删除b. 算法DSTc. 算法解析d. 代码实现递归释放树算法DS e. 算法测试 5. 代码整合…
阅读更多...
基于C#实现三元组

基于C#实现三元组

我们知道矩阵是一个非常强大的数据结构&#xff0c;在动态规划以及各种图论算法上都有广泛的应用&#xff0c;当然矩阵有着不足的地方就是空间和时间复杂度都维持在 N2 上&#xff0c;比如 1w 个数字建立一个矩阵&#xff0c;在内存中会占用 1w*1w1 亿的类型空间&#xff0c;这…
阅读更多...
【人工智能】Chatgpt的训练原理

【人工智能】Chatgpt的训练原理

前言 前不久&#xff0c;在学习C语言的我写了一段三子棋的代码&#xff0c;但是与我对抗的电脑是没有任何思考的&#xff0c;你看了这段代码就理解为什么了&#xff1a; void computerMove(char Board[ROW][COL], int row, int col) {while (1){unsigned int i rand() % ROW, …
阅读更多...
BC76 [NOIP2008]ISBN号码

BC76 [NOIP2008]ISBN号码

#include<stdio.h> int main() {char arr[13]; //存放13位的ISBNint i, j;scanf("%s",arr);int s 0;for(i0, j1; i<11; i){if(arr[i] ! -){s (arr[i]-0)*j; //将字符换成int累加&#xff1a;0162……29158j; //执行if的时候加&#xff0c;不执行不加…
阅读更多...
Linxu 进程替换

Linxu 进程替换

进程替换的背景&#xff1a; 进程的替换我们需要调用execl这个接口,exxecl在3号手册&#xff0c;属于系统接口。 调用系统命令 execl 为了方便理解execl的作用&#xff0c;我们写一个程序&#xff1a; 单进程替换 我们发现运行结果是通过c库里的exec接口把系统命令 "l…
阅读更多...
最新文章

Copyright @ 2022~2023