数据结构
2018-05-05 本文已影响0人
szn好色仙人
STL常用数据结构
数据结构 | 特色 |
---|---|
stack | 后进先出 |
list | 双向链表,支持快速增删元素,缺乏对随机访问的支持 |
forward_list | 单向链表 |
vector | 支持随机访问,支持尾端快速增删元素 |
deque | 支持随机访问,支持双端快速增删元素 |
queue | 先进先出 |
priority_queue | 优先级队列,在queue的基础上,增加了元素的优先级,将按照优先级排列元素 |
set | 有序集合,键值唯一 |
multiset | 关键字可重复出现的set |
unordered_set | 用哈希函数组织的set |
unordered_multiset | 哈希组织的set,关键字可重复出现 |
map | 有序关联数组,保存关键字-值对 |
multimap | 关键字可重复的map |
unordered_map | 用哈希函数组织的map |
unordered_multimap | 哈希函数组织的map,关键字可重复出现 |
- 无序容器默认使用 == 运算符来比较元素
- 测试时,应以Release版本直接运行为准,而非在vs中运行,二者相差有时候是天壤之别
有根树
- 二叉树
- 分支无限的有根树
散列表
- 本节来自算法导论第十一章,粗浅的总结了下,还有大量内容没有深入探查
- 直接寻址表
- 散列表
- 链接法解决冲突
- 散列函数:一个好的散列函数满足简单均匀散列假设,每个关键字都被等可能地散列到m个槽中的任意一个,并与其他关键字已散列到哪个槽无关
- 除法散列法:通过取k除以m的余数,将关键字k映射到第m个槽中,一般m取素数
- 乘法散列法:
- 全域散列法:略
二叉搜索树
- 二叉搜索树的性质
#include <cstdio>
#include <string>
#include <algorithm>
using std::string;
//用于打印时候的格式转换
template<typename TValue>
void ChangeToStr(TValue tValue, string& str);
template<>void ChangeToStr(int tValue, string& str)
{
char buff[100] = {};
sprintf_s(buff, "%d", tValue);
str = buff;
}
#define Template template<typename TKey, typename TValue>
#define NodeType SNode<TKey, TValue>
//二叉搜索树的节点
Template struct SNode
{
SNode() : pFather_(nullptr), pLeft_(nullptr), pRight_(nullptr),
tKey_(TKey()), tValue_(TValue()) {}
SNode* pFather_;
SNode* pLeft_;
SNode* pRight_;
TKey tKey_;
TValue tValue_;
};
//打印
Template void Print(const NodeType* pRootC)
{
if (pRootC)
{
Print(pRootC->pLeft_);
static string strTem;
ChangeToStr(pRootC->tValue_, strTem);
printf("%s ", strTem.c_str());
Print(pRootC->pRight_);
}
}
//搜索Key
Template NodeType* Search(const NodeType* pRootC, const TKey tKeyC)
{
auto pTem = pRootC;
while (pTem)
{
if (pTem->tKey_ > tKeyC)
{
pTem = pTem->pLeft_;
}
else if (pTem->tKey_ < tKeyC)
{
pTem = pTem->pRight_;
}
else
{
return const_cast<NodeType*>(pTem);
}
}
return nullptr;
}
//得到极值节点
Template NodeType* GetMinOrMax(const NodeType* pRootC, const bool bMin)
{
const NodeType* aTem[2] = { pRootC, pRootC };
if (bMin)
{
while (aTem[1])
{
aTem[0] = aTem[1];
aTem[1] = aTem[1]->pLeft_;
}
}
else
{
while (aTem[1])
{
aTem[0] = aTem[1];
aTem[1] = aTem[1]->pRight_;
}
}
return const_cast<NodeType*>(aTem[0]);
}
//得到Key前驱
Template NodeType* GetBefore(const NodeType* pNode)
{
if (pNode)
{
if (pNode->pLeft_)
{
return GetMinOrMax(pNode->pLeft_, false);
}
auto pFather = pNode->pFather_;
while (pFather && pNode == pFather->pLeft_)
{
pNode = pFather;
pFather = pFather->pFather_;
}
return pFather;
}
return nullptr;
}
//得到Key后继
Template NodeType* GetAfter(const NodeType* pNode)
{
if (pNode)
{
if (pNode->pRight_)
{
return GetMinOrMax(pNode->pRight_, true);
}
auto pFather = pNode->pFather_;
while (pFather && pNode == pFather->pRight_)
{
pNode = pFather;
pFather = pFather->pFather_;
}
return pFather;
}
return nullptr;
}
//插入
Template const bool Insert(NodeType*& pRoot, NodeType* pNewNode)
{
if (!pNewNode)
{
return false;
}
NodeType* pY = nullptr;
NodeType* pX = pRoot;
while (pX)
{
pY = pX;
if (pNewNode->tKey_ < pX->tKey_)
{
pX = pX->pLeft_;
}
else
{
pX = pX->pRight_;
}
}
pNewNode->pFather_ = pY;
if (!pY)
{
pRoot = pNewNode;
}
else if (pNewNode->tKey_ < pY->tKey_)
{
pY->pLeft_ = pNewNode;
}
else
{
pY->pRight_ = pNewNode;
}
return true;
}
//删除
Template const bool Delete(NodeType*& pRoot, const TKey tKeyC,
const bool bCheckC = false)
{
return Delete(pRoot, Search(pRoot, tKeyC), bCheckC);
}
//删除
Template const bool Delete(NodeType*& pRoot, NodeType* pDelNode,
const bool bCheckC = false)
{
if (!pRoot || !pDelNode)
{
return false;
}
if (bCheckC)
{
if (Search(pRoot, pDelNode->tKey_) != pDelNode)
{
//被删除的节点不在给定的树中
return false;
}
}
//用节点 pNewNode及其构成的树 代替节点 pOldNode及其构成的树
auto Replace = [&pRoot](NodeType* pOldNode, NodeType* pNewNode)
{
if (!pOldNode->pFather_)
{
pRoot = pNewNode;
}
else if (pOldNode->pFather_->pLeft_ == pOldNode)
{
pOldNode->pFather_->pLeft_ = pNewNode;
}
else
{
pOldNode->pFather_->pRight_ = pNewNode;
}
if (pNewNode)
{
pNewNode->pFather_ = pOldNode->pFather_;
}
};
//情况一:被删除的节点没有左孩子
if (!pDelNode->pLeft_)
{
Replace(pDelNode, pDelNode->pRight_);
return true;
}
//情况二:被删除的节点没有右孩子
if (!pDelNode->pRight_)
{
Replace(pDelNode, pDelNode->pLeft_);
return true;
}
//情况三:被删除的节点的两个孩子均存在
auto pMinNode = GetMinOrMax(pDelNode->pRight_, true);
if (pMinNode->pFather_ != pDelNode)
{
Replace(pMinNode, pMinNode->pRight_);
/*
1.pMinNode是最小节点说明其必定没有左节点
2.上句代码将pMinNode右节点构成的树接到pMinNode的位置上
*/
pMinNode->pRight_ = pDelNode->pRight_;
pMinNode->pRight_->pFather_ = pMinNode;
//用pMinNode来接管被删除节点的右节点构成的树
}
Replace(pDelNode, pMinNode);
pMinNode->pLeft_ = pDelNode->pLeft_;
pMinNode->pLeft_->pFather_ = pMinNode;
//用pMinNode来代替被删除的节点并用pMinNode来接管被删除节点的左节点构成的树
return true;
}
int main()
{
const int nCount = 20;
int aValue[nCount] = {};
int nTemValue = 0;
std::for_each(aValue, aValue + nCount, [&nTemValue](int& nTem)
{
nTem = nTemValue++;
});
std::random_shuffle(aValue, aValue + nCount);
SNode<int, int>* pRoot = nullptr;
SNode<int, int> aNode[nCount] = {};
for (int i = 0; i < nCount; ++i)
{
aNode[i].tKey_ = aValue[i];
aNode[i].tValue_ = aValue[i];
Insert(pRoot, aNode + i);
}
Print(pRoot);
auto nRe0 = Search(pRoot, 5);
auto nRe1 = Search(pRoot, 7);
auto nRe2 = GetMinOrMax(pRoot, false);
auto nRe3 = GetMinOrMax(pRoot, true);
printf("\nDel\n");
Delete(pRoot, 5);
Print(pRoot);
return 0;
}
红黑树
#include <cstdio>
#include <string>
#include <algorithm>
#include <cassert>
using std::string;
//用于打印时候的格式转换
template<typename TValue>
void ChangeToStr(TValue tValue, string& str);
template<>void ChangeToStr(int tValue, string& str)
{
char buff[100] = {};
sprintf_s(buff, "%d", tValue);
str = buff;
}
#define Template template<typename TKey, typename TValue>
#define NodeType SNode<TKey, TValue>
//红黑树的节点
Template struct SNode
{
SNode() : pFather_(nullptr), pLeft_(nullptr), pRight_(nullptr),
tKey_(TKey()), tValue_(TValue()), bRed_(true) {}
SNode* pFather_;
SNode* pLeft_;
SNode* pRight_;
TKey tKey_;
TValue tValue_;
bool bRed_;
};
//打印
Template void Print(const NodeType* pRootC)
{
if (pRootC)
{
Print(pRootC->pLeft_);
static string strTem;
ChangeToStr(pRootC->tValue_, strTem);
printf("%s, %s\n", pRootC->bRed_ ? "R" : "B", strTem.c_str());
Print(pRootC->pRight_);
}
}
Template const bool Insert(NodeType*& pRoot, NodeType* pNewNode)
{
/*******等同于二叉搜索树的插入代码******/
if (!pNewNode)
{
return false;
}
NodeType* pY = nullptr;
NodeType* pX = pRoot;
while (pX)
{
pY = pX;
if (pNewNode->tKey_ < pX->tKey_)
{
pX = pX->pLeft_;
}
else
{
pX = pX->pRight_;
}
}
pNewNode->pFather_ = pY;
if (!pY)
{
pRoot = pNewNode;
}
else if (pNewNode->tKey_ < pY->tKey_)
{
pY->pLeft_ = pNewNode;
}
else
{
pY->pRight_ = pNewNode;
}
/*******等同于二叉搜索树的插入代码******/
//旋转,分为左旋和右旋
auto Rotate = [&pRoot](NodeType* pX, const bool bLeftRotate)
{
if (bLeftRotate)
{
auto pY = pX->pRight_;
assert(pY);
pX->pRight_ = pY->pLeft_;
if (pY->pLeft_)
{
pY->pLeft_->pFather_ = pX;
}
pY->pFather_ = pX->pFather_;
if (!pX->pFather_)
{
pRoot = pY;
}
else if (pX == pX->pFather_->pLeft_)
{
pX->pFather_->pLeft_ = pY;
}
else
{
pX->pFather_->pRight_ = pY;
}
pY->pLeft_ = pX;
pX->pFather_ = pY;
}
else
{
auto pY = pX->pLeft_;
assert(pY);
pX->pLeft_ = pY->pRight_;
if (pY->pRight_)
{
pY->pRight_->pFather_ = pX;
}
pY->pFather_ = pX->pFather_;
if (!pX->pFather_)
{
pRoot = pY;
}
else if (pX == pX->pFather_->pLeft_)
{
pX->pFather_->pLeft_ = pY;
}
else
{
pX->pFather_->pRight_ = pY;
}
pY->pRight_ = pX;
pX->pFather_ = pY;
}
};
pNewNode->pLeft_ = nullptr;
pNewNode->pRight_ = nullptr;
pNewNode->bRed_ = true;
if (!pNewNode->pFather_)
{
pNewNode->bRed_ = false;
return true;
}
while(pNewNode->pFather_->bRed_)
{
if (pNewNode->pFather_ == pNewNode->pFather_->pFather_->pLeft_)
{
auto pY = pNewNode->pFather_->pFather_->pRight_;
if (pY && pY->bRed_)
{
pNewNode->pFather_->bRed_ = false;
pY->bRed_ = false;
pNewNode->pFather_->pFather_->bRed_ = true;
pNewNode = pNewNode->pFather_->pFather_;
}
else
{
if (pNewNode == pNewNode->pFather_->pRight_)
{
pNewNode = pNewNode->pFather_;
Rotate(pNewNode, true);
}
pNewNode->pFather_->bRed_ = false;
pNewNode->pFather_->pFather_->bRed_ = true;
Rotate(pNewNode->pFather_->pFather_, false);
}
}
else
{
auto pY = pNewNode->pFather_->pFather_->pLeft_;
if (pY && pY->bRed_)
{
pNewNode->pFather_->bRed_ = false;
pY->bRed_ = false;
pNewNode->pFather_->pFather_->bRed_ = true;
pNewNode = pNewNode->pFather_->pFather_;
}
else
{
if (pNewNode == pNewNode->pFather_->pLeft_)
{
pNewNode = pNewNode->pFather_;
Rotate(pNewNode, false);
}
pNewNode->pFather_->bRed_ = false;
pNewNode->pFather_->pFather_->bRed_ = true;
Rotate(pNewNode->pFather_->pFather_, true);
}
}
if (!pNewNode->pFather_)
{
break;
}
}
pRoot->bRed_ = false;
return true;
}
Template const bool Delete(NodeType* pRoot, NodeType* pNewNode)
{
return false;
}
int main()
{
const int nCount = 10;
int aValue[nCount] = {};
int nTemValue = 0;
std::for_each(aValue, aValue + nCount, [&nTemValue](int& nTem)
{
nTem = nTemValue++;
});
std::random_shuffle(aValue, aValue + nCount);
//8 1 9 2 0 5 7 3 4 6
SNode<int, int>* pRoot = nullptr;
SNode<int, int> aNode[nCount] = {};
for (int i = 0; i < nCount; ++i)
{
aNode[i].tKey_ = aValue[i];
aNode[i].tValue_ = aValue[i];
Insert(pRoot, aNode + i);
}
Print(pRoot);
return 0;
}