【学习笔记】各种数据结构随笔记

链表

描述

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
链表的每个结点包括存储数据元素的数据域和存储下一个结点地址的指针域。每个链表的第一个节点就是链表的头，最后一个元素是链表的尾。
链表操作主要有搜索，插入和删除。时间复杂度均为O(n)。

分类

• 单向链表：指针域只有next指针指向下一个节点。单向链表的尾节点next=NULL。
• 双向链表：指针域有next指针指向下一个节点和prev指针指向前一个节点。双向链表的头指针prev=NULL，尾节点next=NULL。
• 循环链表：各个节点组成一个环。

链表的优缺点

优点

无需预先知道数据量大小，插入数据方便，可以充分利用计算机的内存空间。

缺点

需要额外的指针域，空间开销大。

C++ 实现一个链表（智能指针）

STL之链表

哈希表

描述

定义

散列表（hash table，也叫哈希表），是根据键（key）而直接访问在内存存储位置的数据结构。
它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
在理想情况下，不同的键会被转换为不同的索引值，但是在有些情况下，我们需要处理多个键被哈希到同一索引值的情况，这种情况叫做冲突。
哈希表是一个在时间和空间上作出权衡的经典例子，如果没有内存限制，那么可以直接将键作为数组的索引，那么所有的查找时间复杂度为O(1)，如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
哈希表结合数组与链表的特性，数据查找方便且内存占用宽松。
hash表支持的操作有三个，insert，search和delete。

哈希表的优缺点

优点

读取效率极高

缺点

• 数据越多，哈希表冲突的可能性越大，会增加操作的时间复杂度。
• 决定建立哈希表前，最好可以估计输入数据的size，不适合数据持续加入的场景。
• 哈希表中的元素是没有被排序的。

冲突处理

实现方法一：拉链法（单独链表法）

拉链式哈希表

上图记录了一个长度为16的数组，每个元素存储的是一个链表的头节点。

实现方法二：开放定址法

也叫做再散列法，基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
通用再散列函数：
Hi=（H（key）+di）% m i=1，2，…，n
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

• 线性探测法：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
  dii=1，2，3，…，m-1
• 二次探测再散列：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
  di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
• 伪随机探测再散列
  di=伪随机数序列

问题：聚集（Cluster，也翻译做“堆积”）的意思是，在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。

实现方法三：再哈希法

构造多个不同的哈希函数

实现方法四：建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

C++ 实现一个哈希表

首先，应该有一个HashItem的类，要包含元素键值key和存储值value。

class HashItem
{
    int key, val;
public:
    HashItem(int k, int v): key(k),val(v){}
    const int& getKey()
    {
        return key;
    }
    const int& getVal()
    {
        return val;
    }
};

建立哈希表的类，需要有插表，读表和删除的操作（本段代码未实现删除），并且要注意冲突处理，本代码段是用的开放定址法的线性探索法。

class HashTable
{
    static const int SIZE = 30;
    vector<shared_ptr<HashItem> > table;
public:
    HashTable()
    {
        table.reserve(SIZE);
    }
    ~HashTable()
    {}
    //put a new hashItem in hashTable
    void set(int key, int val)
    {
        int idx = key%SIZE;
        while(table[idx] && table[idx]->getKey() != key)
            idx = (idx+1) % SIZE; // Thinking about how to avoid endless loop
        shared_ptr<HashItem> tmp(new HashItem(key, val));
        swap(tmp, table[idx]);
    }
    //get a hashItem
    const int get(int key)
    {
        int idx = key%SIZE;
        while(table[idx] && table[idx]->getKey() != key)
            idx = (idx + 1) % SIZE; // Thinking about how to avoid endless loop
        return table[idx] ? table[idx]->getVal():-1;
    }
};

STL之哈希表

C++中，哈希表对应的容器是unordered_map(since C++ 11) 推荐替代hash_map。需要包含#include <unordered_map>

与map的区别
map对应的数据结构是红黑树，红黑树是一种近似于平衡的二叉查找树，数据是有序的。在红黑树上做查找操作的时间复杂度为O(logN)。而unordered_map对应哈希表，哈希表的特点就是查找效率高，时间复杂度为常数级别O(1)，而额外空间复杂度则要高出许多。
所以需要高效率查询的场景使用unordered_map，对内存大小敏感或者数据存储要求有序，用map。
使用自定义类
要使用哈希表，必须要有对应的计算散列值的算法以及判断两个值（或对象）是否相等的方法。
而在 C++ 中没有自动声明这类函数，STL 只为 C++ 常用类提供了散列函数，因此如果想在 unordered_map 中使用自定义的类，则必须为此类提供一个哈希函数和一个判断对象是否相等的函数（e.g. 重载 == 运算符）。
例：

class Person {
public:
    string phone;
    string name;
    string address;
explicit Person() {}
 // overload operator==
    bool operator==(const Person& p) {
        return this->phone == p.phone && this->name == p.name
            && this->address == p.address;
    }
};
// declare hash<Person>
namespace std {
 template <>
 struct hash<Person> {
     std::size_t operator()(const Person& p) const {
      using std::size_t;
      using std::hash;
      using std::string;
      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:
      return ((hash<string>()(p.phone)
        ^ (hash<string>()(p.name) << 1)) >> 1)
        ^ (hash<string>()(p.address) << 1);
     }
 };
}

unordered_map<string, Person> phoneMap;

void selectByPhone() {
    string phone;
    cout << "Input the phone number: "; cin >> phone;
    unordered_map<string, Person>::iterator it;
    int size = phoneMap.size();
    for(int pc = 0; pc < size; pc++) {
        if((it = phoneMap.find(phone)) != phoneMap.end()) {
            cout << "Query result: " << it->second << endl;
            return;
        }
    }
    cout << "Query result : target_not_found" << endl;
}