数据结构

作者: szn好色仙人 | 来源:发表于2018-05-05 22:22 被阅读0次

IOS开发_数据结构
py基础
思维导图之数据结构+算法
数据结构与算法分析：大纲]
数据结构：数组
数据结构—概述
OVS 源码分析整理
01. 数据结构与算法绪论
数据结构与算法 - 查找
C#之数据结构（上）

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;
}