[數據結構]-AVL樹

前言

作者：小蝸牛向前沖

名言：我可以接受失敗，但我不能接受放棄

??如果覺的博主的文章還不錯的話，還請點贊，收藏，關注👀支持博主。如果發現有問題的地方歡迎?大家在評論區指正

目錄

一、AVL樹基本知識

1、概念

2、節點定義

3、插入

二、AVL樹的旋轉

1、右單旋

2、左單旋

?3、左右雙旋

4、?右左雙旋

三、AVL樹的測試?

1、測試的補充代碼

2、測試?

?本期學習目標：清楚什么是AVL樹，模擬實現AVL樹，理解四種旋轉模型。?

一、AVL樹基本知識

1、概念

? ? ? ?二叉搜索樹雖可以縮短查找的效率，但如果數據有序或接近有序二叉搜索樹將退化為單支樹，查 找元素相當于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數學家G.M.Adelson-Velskii 和E.M.Landis在1962年 發明了一種解決上述問題的方法：當向二叉搜索樹中插入新結點后，如果能保證每個結點的左右 子樹高度之差的絕對值不超過1(需要對樹中的結點進行調整)，即可降低樹的高度，從而減少平均 搜索長度。

一棵AVL樹或者是空樹，或者是具有以下性質的二叉搜索樹：

  • 它的左右子樹都是AVL樹
  • 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)

?

2、節點定義

template<class k,class v>
struct AVLTreeNode
{pair<k, v>_kv;AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;AVLTreeNode<k, v>* _parent;int _bf;//balance factor//帶參數的構造函數AVLTreeNode(const pair<k,v>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

這里我們定義了三叉鏈來定義節點，最為特殊的是我們相對于二叉樹，我們多了一個平衡?因子，這是維持AVL特性的關鍵，下面我們將圍繞此展開對AVL樹的構建。

注意：平衡因子 =?右樹的高度-左樹的高度

3、插入

AVL樹就是在二叉搜索樹的基礎上引入了平衡因子，因此AVL樹也可以看成是二叉搜索樹。那么 AVL樹的插入過程可以分為兩步：

1. 按照二叉搜索樹的方式插入新節點

2. 調整節點的平衡因子

對于插入最為重要的是平衡因子的更新，下面我們將討論更新平衡因子情況：

是否要在更新平衡因子，要根據子樹的高度：
1、如果parent->_bf==0,者說明以前的parent->_bf==-1或者parent->_bf==1
即是以前是一邊高一邊低，現在是插入到矮的一邊，樹的高度不變，不更新

2、如果parent->_bf==-1或者parent->_bf==-1，者以前parent->_bf==0
即是以前樹是均衡的，現在插入讓一邊高了
子樹的高度變了，要向上更新

3 、如果parent->_bf==-2或者parent->_bf==2，者以前parent->_bf==-1或者parent->_bf==1
現在樹嚴重不平衡，讓樹旋轉維持結構

//插入
bool Insert(const pair<k, v>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;//找插入位置while (cur){//插入元素大于比較元素if (cur->_kv.first < kv.first){parent = cur;//繼續往右樹走cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;//繼續往左樹走cur = cur->_left;}else//插入元素于樹中元素相等，不插入{return false;}}cur = new Node(kv);//鏈接節點if (parent->_kv.first > kv.first){parent->_left = cur;//更新parentcur->_parent = parent;}else{parent->_right = cur;//更新parentcur->_parent = parent;}//更新平衡因子while (parent)//parent為空，就更新到了根{//新增在樹節點左邊，parent->bf--//新增在樹節點右邊，parent->bf++if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//是否要在更新平衡因子，要根據子樹的高度：//1、如果parent->_bf==0,者說明以前的parent->_bf==-1或者parent->_bf==1//即是以前是一邊高一邊低，現在是插入到矮的一邊，樹的高度不變，不更新//2、如果parent->_bf==-1或者parent->_bf==-1，者以前parent->_bf==0//即是以前樹是均衡的，現在插入讓一邊高了//子樹的高度變了，要向上更新//3 、如果parent->_bf==-2或者parent->_bf==2，者以前parent->_bf==-1或者parent->_bf==1//現在樹嚴重不平衡，讓樹旋轉維持結構//旋轉：//1、讓子樹的高度差不差過1//2、旋轉過程中也要保存搜索樹結構//3、邊更新平衡因子//4、讓這課樹的高度保存和之前一樣(旋轉結束，不影響上層結構)if (parent->_bf == 0){break;}else if (parent->_bf == -1 || parent->_bf == 1){cur = parent;parent = parent->_parent;}//旋轉else if (parent->_bf == -2 || parent->_bf == 2){//左單旋轉if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}//右單旋else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//左右雙旋else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//右左雙旋else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}//旋轉完成,平衡因子已經更新跳出循環break;}else{assert(false);}}
}

二、AVL樹的旋轉

如果parent->_bf==-2或者parent->_bf==2，者以前parent->_bf==-1或者parent->_bf==1
現在樹嚴重不平衡，讓樹旋轉維持結構：

旋轉的要求：

  • 讓子樹的高度差不差過1
  • 旋轉過程中也要保存搜索樹結構
  • 邊更新平衡因子
  • 讓這課樹的高度保存和之前一樣(旋轉結束，不影響上層結構)

旋轉的分類：?

  • 新節點插入較高左子樹的左側—左左：右單旋
  • 新節點插入較高右子樹的右側—右右：左單旋
  • 新節點插入較高左子樹的右側—左右：先左單旋再右單旋
  • 新節點插入較高右子樹的左側—右左：先右單旋再左單旋

1、右單旋

對于可能出現右旋轉的情況的子樹是多樣的

?這里我們可以根據需要進行右單旋轉抽像圖進行理解

?

代碼實現：?

//右單旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;//b做60的右parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;//60做30的右subL->_right = parent;parent->_parent = subL;//60就是以前的根節點if (ppNode == nullptr){_root = subL;subL->_parent = ppNode;}else{//上層父節點的左邊是子樹的parentif (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}//更新平衡因子parent->_bf = subL->_bf = 0;
}

2、左單旋

?

代碼實現：

?

void RotateL(Node * parent)
{Node* subR = parent->_right;//父節點的右子樹Node* subRL = subR->_left;//右樹的左樹//讓60左邊鏈接到30的右邊parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* ppNode = parent->_parent;//讓30變成60的左邊subR->_left = parent;parent->_parent = subR;//subR就是根節點if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{//上層父節點的左邊是子樹的parentif (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}//子樹父節點和上層父節點鏈接subR->_parent = ppNode;}//更新平衡因子parent->_bf = subR->_bf = 0;
}

?3、左右雙旋

對于雙旋轉來說：節點新增的位置不同，平衡因子最終也會不同，這里我們要進行分類討論：

對于雙旋轉來說，最為重要的平衡因子的更新。?

?代碼實現：

//左右雙旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;//記錄subLR的平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//根據不同情況更新平衡因子if (bf == 1)//在c點處新增(在subLR的右子樹新增){subLR->_bf = 0;parent->_bf = 0;subL->_bf = -1;}else if(bf == -1) // 在b點處新增(在subLR的左子樹新增){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 0) //自己就是增點{subLR->_bf = 0;parent->_bf = 0;subL->_bf = 0;}else{assert(false);}
}

4、?右左雙旋

這里同樣也要進行分類討論：

?

代碼實現：?

//右左雙旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;//記錄subLR的平衡因子int bf = subRL->_bf;RotateR (parent->_right);RotateL(parent);//根據不同情況更新平衡因子if (bf == 1)//在c點處新增(在subLR的右子樹新增){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1) // 在b點處新增(在subLR的左子樹新增){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0) //自己就是增點{subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

三、AVL樹的測試?

為了測試我們模擬實現的AVL樹是否成功，還需要進行檢查

1、測試的補充代碼

樹的高度：

int Height()
{return _Height(_root);
}
//求樹的高度
int _Height(Node* root)
{//樹高度為0if (root == nullptr){return 0;}//遞歸求左樹的高度int Lh = _Height(root->_left);//遞歸求右樹的高度int Rh = _Height(root->_right);return  Lh > Rh ? Lh + 1 : Rh + 1;
}

檢查平衡因子

	//檢測平衡因子bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_bf << endl;cout << rightHeight - leftHeight << endl;cout << root->_kv.first << "平衡因子異常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}

中序遍歷

	void InOrder()//這是為了解決在外面調用,不好傳根的問題{_InOrder(_root);}//中序遍歷void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

2、測試?

完整代碼：

#pragma once
#include<time.h>
#include<assert.h>template<class k,class v>
struct AVLTreeNode
{pair<k, v>_kv;AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;AVLTreeNode<k, v>* _parent;int _bf;//balance factor//帶參數的構造函數AVLTreeNode(const pair<k,v>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};
template<class k, class v>
struct AVLTree
{typedef AVLTreeNode<k,v> Node;
public://插入bool Insert(const pair<k, v>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;//找插入位置while (cur){//插入元素大于比較元素if (cur->_kv.first < kv.first){parent = cur;//繼續往右樹走cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;//繼續往左樹走cur = cur->_left;}else//插入元素于樹中元素相等，不插入{return false;}}cur = new Node(kv);//鏈接節點if (parent->_kv.first > kv.first){parent->_left = cur;//更新parentcur->_parent = parent;}else{parent->_right = cur;//更新parentcur->_parent = parent;}//更新平衡因子while (parent)//parent為空，就更新到了根{//新增在樹節點左邊，parent->bf--//新增在樹節點右邊，parent->bf++if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//是否要在更新平衡因子，要根據子樹的高度：//1、如果parent->_bf==0,者說明以前的parent->_bf==-1或者parent->_bf==1//即是以前是一邊高一邊低，現在是插入到矮的一邊，樹的高度不變，不更新//2、如果parent->_bf==-1或者parent->_bf==-1，者以前parent->_bf==0//即是以前樹是均衡的，現在插入讓一邊高了//子樹的高度變了，要向上更新//3 、如果parent->_bf==-2或者parent->_bf==2，者以前parent->_bf==-1或者parent->_bf==1//現在樹嚴重不平衡，讓樹旋轉維持結構//旋轉：if (parent->_bf == 0){break;}else if (parent->_bf == -1 || parent->_bf == 1){cur = parent;parent = parent->_parent;}//旋轉else if (parent->_bf == -2 || parent->_bf == 2){//左單旋轉if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}//右單旋else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//左右雙旋else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//右左雙旋else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}//旋轉完成,平衡因子已經更新跳出循環break;}else{assert(false);}}}void RotateL(Node * parent){Node* subR = parent->_right;//父節點的右子樹Node* subRL = subR->_left;//右樹的左樹//讓60左邊鏈接到30的右邊parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* ppNode = parent->_parent;//讓30變成60的左邊subR->_left = parent;parent->_parent = subR;//subR就是根節點if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{//上層父節點的左邊是子樹的parentif (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}//子樹父節點和上層父節點鏈接subR->_parent = ppNode;}//更新平衡因子parent->_bf = subR->_bf = 0;}//右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//b做60的右parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;//60做30的右subL->_right = parent;parent->_parent = subL;//60就是以前的根節點if (ppNode == nullptr){_root = subL;subL->_parent = ppNode;}else{//上層父節點的左邊是子樹的parentif (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}//更新平衡因子parent->_bf = subL->_bf = 0;}//左右雙旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//記錄subLR的平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//根據不同情況更新平衡因子if (bf == 1)//在c點處新增(在subLR的右子樹新增){subLR->_bf = 0;parent->_bf = 0;subL->_bf = -1;}else if(bf == -1) // 在b點處新增(在subLR的左子樹新增){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 0) //自己就是增點{subLR->_bf = 0;parent->_bf = 0;subL->_bf = 0;}else{assert(false);}}//右左雙旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//記錄subLR的平衡因子int bf = subRL->_bf;RotateR (parent->_right);RotateL(parent);//根據不同情況更新平衡因子if (bf == 1)//在c點處新增(在subLR的右子樹新增){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1) // 在b點處新增(在subLR的左子樹新增){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0) //自己就是增點{subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}int Height(){return _Height(_root);}//求樹的高度int _Height(Node* root){//樹高度為0if (root == nullptr){return 0;}//遞歸求左樹的高度int Lh = _Height(root->_left);//遞歸求右樹的高度int Rh = _Height(root->_right);return  Lh > Rh ? Lh + 1 : Rh + 1;}bool IsAVLTree(){return _IsBalance(_root);}//檢測平衡因子bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_bf << endl;cout << rightHeight - leftHeight << endl;cout << root->_kv.first << "平衡因子異常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}void InOrder()//這是為了解決在外面調用,不好傳根的問題{_InOrder(_root);}//中序遍歷void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};void TestAVLTree1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };/*int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };*/int a[] = { 30,60,90 };AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsAVLTree() << endl;
}
void TestAVLTree2()
{srand(time(0));const size_t N = 100000;AVLTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand();t.Insert(make_pair(x, x));/*cout << t.IsAVLTree() << endl;*/}cout << t.IsAVLTree() << endl;
}

這里我們分別進行簡單?TestAVLTree1()和用生成隨機數字生成的數字進行測試TestAVLTree2()

如果成功就會打印1.

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/161860.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/161860.shtml
英文地址，請注明出處：http://en.pswp.cn/news/161860.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

OpenGL 繪制線（Qt）

OpenGL 繪制線（Qt）

文章目錄 一、簡介二、實現代碼三、實現效果參考資料一、簡介 這里同樣對OpenGL中的繪制線操作進行封裝，便于后續的操作，很多形狀也都是基于線來生成的，如圓形等。 二、實現代碼 LineDrawable.h #ifndef LINE_DRAWABLE_H #define LINE_DRAWABLE_H#include
閱讀更多...
IBM ELM—系統工程全生命周期管理平臺

IBM ELM—系統工程全生命周期管理平臺

產品概述 Engineering Lifecycle Management是IBM提供的工程全生命周期管理組合工具&#xff0c;幫助企業降低開發成本&#xff0c;應對開發挑戰并更快地發展其流程和實踐。 隨著產品變得更加復雜且數字化&#xff0c;傳統的工程開發不再能及時且有效地滿足系統工程的復雜度&a…
閱讀更多...
【Django-DRF】多年md筆記第5篇：Django-DRF的Request、Response和視圖詳解

【Django-DRF】多年md筆記第5篇：Django-DRF的Request、Response和視圖詳解

本文從分析現在流行的前后端分離Web應用模式說起&#xff0c;然后介紹如何設計REST API&#xff0c;通過使用Django來實現一個REST API為例&#xff0c;明確后端開發REST API要做的最核心工作&#xff0c;然后介紹Django REST framework能幫助我們簡化開發REST API的工作。 Dj…
閱讀更多...
[點云分割] 基于最小切割的分割

[點云分割] 基于最小切割的分割

效果&#xff1a; 代碼&#xff1a; #include <iostream> #include <vector>#include <pcl/point_types.h> #include <pcl/io/pcd_io.h> #include <pcl/visualization/cloud_viewer.h> #include <pcl/filters/filter_indices.h> #include…
閱讀更多...
Can‘t open the append-only file: Permission denied

Can‘t open the append-only file: Permission denied

redis rdb aof-CSDN博客 Cant open the append-only file: Permission denied E:\Document_Redis_Windows\redis-2.4.5-win32-win64\64bit E:\Document_Redis_Windows\redis-2.4.5-win32-win64\64bit\redis.conf 還是不行&#xff0c;就要修改權限了&#xff0c;windows【完全控…
閱讀更多...
matlab 最小二乘擬合平面并與XOY平面對齊

matlab 最小二乘擬合平面并與XOY平面對齊

目錄 一、算法原理二、代碼實現1、繞原點對齊2、繞質心對齊三、結果展示1、繞原點對齊2、繞質心對齊四、測試數據本文由CSDN點云俠原創，原文鏈接。爬蟲網站自重。如果你不是在點云俠的博客中看到該文章，那么此處便是不要臉的爬蟲。 一、算法原理 首先，使用最小二乘擬合平面…
閱讀更多...
priority_queue簡單實現（優先級隊列）（c++）

priority_queue簡單實現（優先級隊列）（c++）

priority_queue priority_queue介紹邏輯實現框架調整算法adjust_up()adjust_down() 仿函數/比較函數仿函數特性 構造函數迭代器區間構造 完整優先級隊列代碼 priority_queue介紹 pri_que是一個容器適配器&#xff0c;它的底層是其他容器&#xff0c;并由這些容器再封裝而來。類…
閱讀更多...
C語言指針相關練習題

C語言指針相關練習題

? C語言指針相關練習題 文章目錄 C語言指針相關練習題題目一題目二題目三題目四題目五題目六題目七 題目一 #include <stdio.h> int main() {int a[5] { 1, 2, 3, 4, 5 };int *ptr (int *)(&a 1);printf( "%d,%d", *(a 1), *(ptr - 1));return 0; }…
閱讀更多...
[Unity+OpenAI TTS] 集成openAI官方提供的語音合成服務，構建海王暖男數字人

[Unity+OpenAI TTS] 集成openAI官方提供的語音合成服務，構建海王暖男數字人

1.簡述 最近openAI官方發布了很多新功能&#xff0c;其中就包括了最新發布的TTS語音合成服務的api接口。說到這個語音合成接口&#xff0c;大家可能會比較陌生&#xff0c;但是說到chatgpt官方應用上的聊天機器人&#xff0c;那個臺灣腔的海王暖男的聲音&#xff0c;可能就有印…
閱讀更多...
深度合成算法的基礎與原理

深度合成算法的基礎與原理

深度合成算法是人工智能領域中備受矚目的研究方向之一。它的應用范圍涵蓋了圖像合成、文本生成、音頻合成等多個領域&#xff0c;為人們提供了令人驚嘆的創新和娛樂體驗。本文將深入探討深度合成算法的基礎原理&#xff0c;了解它們是如何工作的以及它們在不同領域的應用。算法…
閱讀更多...
輕量封裝WebGPU渲染系統示例＜38＞- 動態構建WGSL材質Shader(源碼)

輕量封裝WebGPU渲染系統示例＜38＞- 動態構建WGSL材質Shader(源碼)

實現原理: 基于宏定義和WGSL功能文件實現 當前示例源碼github地址: https://github.com/vilyLei/voxwebgpu/blob/feature/rendering/src/voxgpu/sample/DynamicShaderBuilding.ts 當前示例運行效果: 此示例基于此渲染系統實現&#xff0c;當前示例TypeScript源碼如下&#x…
閱讀更多...
編寫bat程序 快速開啟 redis 服務

編寫bat程序 快速開啟 redis 服務

一鍵開啟redis服務 編寫txt文件&#xff0c;代碼如下&#xff1a;cd /d E:\Redis\Redis-x64-5.0.14.1 redis-server.exe redis.windows.conf這里的redis的安裝目錄記得改成自己的 將文件后綴的.txt改成.bat&#xff0c;然后雙擊運行就可以啦
閱讀更多...
前綴和及差分數組

前綴和及差分數組

前綴和 原數組x0x1x2x3x4x5前綴和數組x0x0x1x0x1x2x0x1x2x3x0x1x2x3x4x0x1x2x3x4x5前綴和數組代數形式x0’x1’x2’x3’x4’x5’ 計算原數組某區間的和 sum[x1,x2,x3] 利用前綴和計算 x3-x0 x0x1x2x3-x0 x1x2x3 差分數組 x0x1x2x3x4x5原數組x0x1x2x3x4x5差分數組x0x1-x0x…
閱讀更多...
模擬電路定理

模擬電路定理

模擬電路是指由電子元件、電路拓撲和信號處理單元等構成的電路&#xff0c;用于模擬現實世界中的信號和系統。在模擬電路中&#xff0c;有許多重要的定理和規律&#xff0c;下面列舉了一些常見的定理。 1. 基爾霍夫電流定律&#xff08;Kirchhoffs Current Law&#xff09; 基…
閱讀更多...
HTTP四大參數類型及請求參數的方式和如何接收

HTTP四大參數類型及請求參數的方式和如何接收

HTTP 請求中4大參數類型和接收方法。 1、請求頭參數head 請求頭參數顧名思義&#xff0c;是存放在請求頭中發送給服務器的參數&#xff0c;服務器通過解析請求頭獲取參數內容。通常會存放本次請求的基本設置&#xff0c;以幫助服務器理解并解析本次請求的body體。 參數形式如…
閱讀更多...
C++學習 --string

C++學習 --string

目錄 1&#xff0c; 什么是string 2&#xff0c; 創建string 3&#xff0c; 操作string 3-1&#xff0c; 賦值 3-1-1&#xff0c; 賦值() 3-1-1&#xff0c; 賦值(assign) 3-2&#xff0c; 修改 3-2-1&#xff0c; 拼接 3-2-1-1&#xff0c; 拼接() 3-2-1-2&#xff…
閱讀更多...
srs的webrtc信令分析

srs的webrtc信令分析

關于webrtc的流信令只有四個 /rtc/v1/publish/&#xff0c;這是推流接口&#xff0c;是推流客戶端跟SRS交換SDP的接口 /rtc/v1/play/&#xff0c;這是拉流接口&#xff0c;是拉流客戶端跟SRS交換SDP的接口 /rtc/v1/whip/&#xff0c;這也是推流接口&#xff0c;作用是也是交換…
閱讀更多...
C#開發的OpenRA游戲之屬性RenderSprites（8）

C#開發的OpenRA游戲之屬性RenderSprites（8）

C#開發的OpenRA游戲之屬性RenderSprites（8） 本文開始學習RenderSprites屬性，這個屬性是跟渲染有關的，因此它就攝及顏色相關的內容，所以我們先來學習一下調色板，這是舊游戲的圖片文件保存的格式，如果放在現代來看，不會再采用這種方法，畢竟現在存儲空間變大，便宜了，并…
閱讀更多...
JDBC 操作 SQL Server 時如何傳入列表參數

JDBC 操作 SQL Server 時如何傳入列表參數

本文是作為將要對 PostgreSQL 的 in, any() 操作的一個鋪墊&#xff0c;也是對先前用 JDBC 操作 SQL Server 的溫習。以此記錄一下用 JDBC 查詢 SQL Server 時如何傳遞一個列表參數。比如想像一下查詢語句 select * from users where id in (?) 我們是否能給這里的問題參數傳遞…
閱讀更多...
idea編譯問題導致接口調用不通

idea編譯問題導致接口調用不通

問題背景&#xff1a; 1.idea版本2021&#xff0c;springboot&#xff0c;父子maven項目&#xff0c;創建了一個新的model。啟動之后&#xff0c;調試controller接口&#xff0c;接口一直報404。 問題分析&#xff1a; 1.查看編譯后的文件&#xff0c;發現java代碼一直沒編譯…
閱讀更多...
最新文章

Copyright @ 2022~2023