数据结构——提升篇

港控/mmm° 2022-11-25 00:40 44阅读 0赞

### 文章目录 ###

*  二叉树
 *   *  什么是堆
     *  堆的特性
     *  堆的应用
     *  使用到堆的情况
     *  自己设计一个二叉堆
     *  STL 提供的堆
 *  二分查找法
 *   *  思路:
     *  二叉搜索树
     *   *  特点
         *  优势
         *  缺点
     *  实现二叉搜索树
     *   *  确立数据之间的关系
         *  节点的创建
         *  实现功能
 *  哈希表
 *   *  哈希表的的概述
     *  哈希表的特点
     *   *  代价
     *  使用hash的容器
     *  设计哈希表
     *   *  地址查询
         *  线性探测
         *  分离链接
         *  哈希表结构
     *  ELF算法处理字符串

# 二叉树 #

## 什么是堆 ##

堆是一种数据结构  
最大堆,每次从数据中取出最大的元素  
最小堆,每次从数据中取出最小的元素  
堆通常是一一棵完全二叉树的数组对象

## 堆的特性 ##

堆中某个节点的值总是（最大堆）不大于或（最小堆）不小于其父节点的值;  
堆总是一棵完全二叉树。  
最大堆的根节点的值一定是最大的(反之最小堆根节点是最小的)  
二叉堆不用关心左右子树的大小

## 堆的应用 ##

内存中从堆中申请内存  
利用堆进行的一个排序 堆排序( Heap Sort )  
二叉堆是可用于实现高效优先队列的数据结构之一。

## 使用到堆的情况 ##

堆能够快速的找到元素中最大的那一个元素  
我们计算机操作系统,每次运行程序都只能运行一个任务每运行一次排序一次,效率非常低 (耗时大),使用堆能够快速找到最需要的那个程序  
下载文件的过程中也会用到堆,先将文件最小的那一个下载好,然后在去下载其他文件  
电脑AI 附近有敌人,最先攻击哪个敌人  
游戏中的防御塔  
常见的考试题目  
实现一个代码从1000000中取出前100名的数据

## 自己设计一个二叉堆 ##

堆中有以下功能

//插入元素
    void insert(type val);
     
    //取出元素
    type extract();
       
    //获取最大值
    type root();
    
    //堆是否为空
    bool empty();
    
    //判断是否满了，如果是vector实现的，可忽略
    bool full();
    
    //堆的大小
    int size();

## STL 提供的堆 ##

底层函数  
STL中为我们实现了一个底层的接口

头文件

#include <algorithm>

创建堆

make_heap(vec.begin(), vec.end(),comp);   
    // 可选参数 greate<>() less<>()

插入元素

push_heap(vec.begin(), vec.end());

删除元素

pop_heap(vec.begin(), vec.end())

堆排序

sort_heap(vec.begin(), vec.end());

优先队列  
STL中提供了一个底层用堆实现的容器,可以每次取出最大的元素

头文件

#include <queue>

容器名称

priority_queue

使用方法

priority_queue<int> pq;     //创建一个优先队列
    
    pq.push(20);                //插入数据
    
    pq.pop();                   //移除数据
    
    auto val=pq.top();          //取出最大的数据
    
    int size();                 // 返回队列内元素个数
        
    bool empty()                //判断是否为空

如何定义逆序的优先队列

priority_queue<int,vector<int>,greater<>> pq;

# 二分查找法 #

二分查找找法是一个查找算法,它的核心思想是进行数据折半查找

比如猜数字游戏

二分查找法的一个必要条件就是需要在有序的数组内才能使用

## 思路: ##

必须是在一个有序的数组内进行查找  
先取数组的中间下标,判断查找的数据  
如果大于,就在右边继续进行折半查找,否则在左边  
如果相等,就说明找到了,否则就没有找到

## 二叉搜索树 ##

二叉搜索树又称之为 二叉查找树 Binary Search Tree

简称 B Tree (B树)

### 特点 ###

二叉搜索树包含二叉树的特性

有左右两个孩子  
节点之间没有环状结构  
二叉搜索树的特性

树的最左边一定是最小的值  
树的最右边一定是最大的值  
二叉树左边的值一定都小于根节点的值  
二叉树右边的值一定都小于根节点左边的值  
每一个节点都符合二叉搜索树的特性

节点的左边比根节点要小  
节点的右边比根节点要大  
每个单独的节点也符合二叉搜索树的特性

### 优势 ###

高效的插入数据  
高效的删除数据  
动态的维护数据  
快速的找到数据的最大值  
快速找到数据最小值

### 缺点 ###

1.每次插入递增或递减的数据,效率反而变低

## 实现二叉搜索树 ##

### 确立数据之间的关系 ###

二叉树  
每个节点的键值大于左孩子  
每个节点的键值小于右孩子  
左右孩子为根仍是二叉搜索树  
不一定是一个完全二叉树

### 节点的创建 ###

template<typename K,typename V>
    struct Node
    {
        
        K key;
        V val;
        Node *left;
        Node *right;
        Node(K &k, V& v, Node *left = nullptr, Node *right = nullptr) 
            :key(k), val(v), left(left), right(right)
            {
        
            }
    };

### 实现功能 ###

//返回容器的大小
    int size();
    //判断是否为空
    bool empty()
    
    Node<k,V> min();                //获取最小值
    Node<k,V> max();                //获取最大值
    
    void pop_max();         //删除最大值             
    void pop_min();         //删除最小值
    
    void insert();          //插入数据
    void remove();          //移除数据
    
    V& find(K key);         //通过Key找到值引用

# 哈希表 #

## 哈希表的的概述 ##

哈希表又程为散列表(Hash table)  
它通过把关键值映射到表中一个位置来访问记录，以加快查找的速度,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间  
这个映射函数叫做散列函数，存放记录的数组叫做散列表

## 哈希表的特点 ##

哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。

高效的查找数据  
高效的插入数据  
高效去除重复元素

### 代价 ###

会消耗比较多的内存  
查找速度不是稳定的

## 使用hash的容器 ##

注意这是c++98时的容器,在c++11以后已经弃用了

*  hash\_map
 *  hash\_set
 *  hash\_multimap
 *  hash\_multiset
 *  用法 和 map, set,multimap 相似

`注意 他们之间内部的底层实现不一样,要实现的查找效果也不一样`

c++ 11标准的哈希容器

unordered_map
    unordered_multimap
    unordered_set
    unordered_multset

## 设计哈希表 ##

实现 inset remove search 三种基本功能

### 地址查询 ###

定义一个足够大的数组  
然后直接通过数字来进行查询

### 线性探测 ###

通过取余求出插入的位置  
每次遍历到结尾就从头的位置继续遍历  
数据的插入不应该大于容器的长度

### 分离链接 ###

用一个数组存放一个链表  
每次在数组的链表内插入数据

### 哈希表结构 ###

class Hash
    {
        
    public:
        //插入数据
        bool insert(int key);
    
        //删除数据
        bool remove(int key);   
    
        //搜索数据
        int search(int key);
    
        //是否为空
        bool empty();
    
        //当前数据大小
        int size();
    
        //是否满了
        bool full();
    }

## ELF算法处理字符串 ##

//字符串哈希
    //MOD 数组的长度 
    int ELF(const char *key)
    {
        
        unsigned long h=0;
        while(*key)
        {
        
            h = (h << 4) + *key++;
            unsigned long g = h & 0xF0000000L;
            if(g)
            h ^= g >> 24;
            h &= ~g;
        }
      return h % MOD;
    }