《算法导论》读书笔记 PART 3

发布于 2020-02-25  117 次阅读


第三部分:数据结构

第10章.基本数据结构

10.1栈和队列

栈和队列是最基础的数据结构,栈实现了后进先出(LIFO)的策略,队列则实现了先进先出(FIFO)的策略,在算法竞赛中十分常用,实现既可以用手工模拟,又可以调用STL中的stack和queue。

10.2链表

链表是链式数据结构的一种,和数组不同的是,链表能够提供在O(1)的时间内往中间插入数据的操作,其主要思想是将数据想链条一样串成一串,前一个数据节点提供后一个数据节点的地址,但对于其中单个元素的访问时间就变成了O(n)级别。

自己写的基于链表的插入排序的class

class link_list
{
private:
    struct node
    {
        int v;
        node *next = NULL;
    };
    node *head = NULL;

public:
    bool empty()
    {
        return head == NULL;
    }
    void insert(int v)
    {
        if (empty())
        {
            node *t = new node;
            t->v = v;
            t->next = NULL;
            head = t;
            return;
        }
        node *pr = NULL;
        node *now = head;
        while (now != NULL && now->v < v)
        {
            pr = now;
            now = now->next;
        }
        if (pr == NULL)
        {
            now = new node;
            now->v = v;
            now->next = head;
            head = now;
            return;
        }
        else if (now == NULL)
        {
            now = new node;
            now->v = v;
            now->next = NULL;
            pr->next = now;
            return;
        }
        else
        {
            node *t = new node;
            t->v = v;
            t->next = now;
            pr->next = t;
            return;
        }
    }
    int top()
    {
        return head->v;
    }
    void pop()
    {
        node *t;
        t = head;
        head = head->next;
        delete t;
        return;
    }
    void clear()
    {
        while (!empty())
            pop();
    }
    vector<int> bianli()//输出遍历结果
    {
        vector<int> ans;
        node *now = head;
        while (now != NULL)
        {
            ans.push_back(now->v);
            now = now->next;
        }
        return ans;
    }
}

第11章.散列表(哈希表)

11.1直接寻址表

直接寻址表的思想就是把数组的里面的每个元素当做一个向量(链接)例如 arr[2]=3就代表了2->3这个向量,此操作方法在链式结构(数组模拟的链表),并查集等算法中十分常用。

11.2散列表

对于前面提到的直接选址表,其有一个缺点。假设有一向量a->b,当a很大时,就需要开很大的数组,当a的分布比较分散时,这将造成大量空间的浪费,因此我们就需要利用散列函数来讲数据映射到一个比较小的范围,此时向量的表示为

arr[hash(a)]= b//hash为散列函数

11.3.1除法散列表

很简单,直接通过取模操作进行散列(估计冲突死),mod通常取你数组的大小

inline hash(a) return a%mod

11.3.2乘法散列表

乘法散列表就是依次将元素里面的一部分加到散列值,再曾以某个特定的值,再取模,对于元素的选择,大整数可以选择每个数位,字符串可以选择每个字符

inline int ELFhash(char *key)
{
	unsigned long h = 0;
	unsigned long g;
	while( *key )
	{
		h =( h<< 4) + *key++;
		g = h & 0xf0000000L;
		if( g ) h ^= g >> 24;
		h &= ~g;
	}
	return h;
}//常用字符串hash板子

第12章:二叉搜索树

这一张主要讲了二叉搜索树的实现(二分查找不香嘛。。。。)

二叉搜索树基于二叉树,利用二叉树的性质,其插入操作满足一下三个条件

1.如果根节点为空就将要插入的元素插入。
2.如果要插入的元素小于其根节点,就将其插入左子树。
3.如果插入的的元素大于其根节点,就将其插入右子树。

基于上条件,二叉查找树拥有一下几条性质

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值。
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值。
  3. 任意节点的左、右子树也分别为二叉查找树。

其查找的时间复杂度为O(logn),可能会退化为O(n)

空间复杂度O(n)

又没找到题目QAQ

第13章:红黑树

13.1红黑树的性质

红黑树是二叉搜索树的一种,其主要解决了二叉搜索树时间复杂度会退化成O(n)的问题。

一棵红黑树满足一下5条性质:

  • 1.每个节点都有一个颜色的属性,要么是黑的,要么是红的
  • 2.根节点是黑色的
  • 3.每个叶节点是黑色的
  • 4.红色节点的儿子都是黑色的
  • 5.对于每个节点其所有到其下方叶子节点的路径所包含的黑色节点都是相同的
class bst {
private:

    struct Node {
        int value;
        bool color;
        Node *leftTree, *rightTree, *parent;

        Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }        

        Node* grandparent() {
            if(parent == NULL){
                return NULL;
            }
            return parent->parent;
        }

        Node* uncle() {
            if(grandparent() == NULL) {
                return NULL;
            }
            if(parent == grandparent()->rightTree)
                return grandparent()->leftTree;
            else
                return grandparent()->rightTree;
        }

        Node* sibling() {
            if(parent->leftTree == this)
                return parent->rightTree;
            else
                return parent->leftTree;
        }
    };

    void rotate_right(Node *p){
        Node *gp = p->grandparent();
        Node *fa = p->parent;
        Node *y = p->rightTree;

        fa->leftTree = y;

        if(y != NIL)
            y->parent = fa;
        p->rightTree = fa;
        fa->parent = p;

        if(root == fa)
            root = p;
        p->parent = gp;

        if(gp != NULL){
            if(gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }

    }

    void rotate_left(Node *p){
        if(p->parent == NULL){
            root = p;
            return;
        }
        Node *gp = p->grandparent();
        Node *fa = p->parent;
        Node *y = p->leftTree;

        fa->rightTree = y;

        if(y != NIL)
            y->parent = fa;
        p->leftTree = fa;
        fa->parent = p;

        if(root == fa)
            root = p;
        p->parent = gp;

        if(gp != NULL){
            if(gp->leftTree == fa)
                gp->leftTree = p;
            else
                gp->rightTree = p;
        }
    }

    void inorder(Node *p){
        if(p == NIL)
            return;

        if(p->leftTree)
            inorder(p->leftTree);

        cout << p->value << " ";
                
        if(p->rightTree)
            inorder(p->rightTree);
    }

    string outputColor (bool color) {
        return color ? "BLACK" : "RED";
    }

    Node* getSmallestChild(Node *p){
        if(p->leftTree == NIL)
            return p;
        return getSmallestChild(p->leftTree);
    }

    bool delete_child(Node *p, int data){
        if(p->value > data){
            if(p->leftTree == NIL){
                return false;
            }
            return delete_child(p->leftTree, data);
        } else if(p->value < data){
            if(p->rightTree == NIL){
                return false;
            }
            return delete_child(p->rightTree, data);
        } else if(p->value == data){
            if(p->rightTree == NIL){
                delete_one_child (p);
                return true;
            }
            Node *smallest = getSmallestChild(p->rightTree);
            swap(p->value, smallest->value);
            delete_one_child (smallest);

            return true;
        }else{
           return false;
         }
    }

    void delete_one_child(Node *p){
        Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
        if(p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL){
            p = NULL;
            root = p;
            return;
        }
        
        if(p->parent == NULL){
            delete  p;
            child->parent = NULL;
            root = child;
            root->color = BLACK;
            return;
        }
        
        if(p->parent->leftTree == p){
            p->parent->leftTree = child;
        } else {
            p->parent->rightTree = child;
        }
        child->parent = p->parent;

        if(p->color == BLACK){
            if(child->color == RED){
                child->color = BLACK;
            } else
                delete_case (child);
        }

        delete p;
    }

    void delete_case(Node *p){
        if(p->parent == NULL){
            p->color = BLACK;
            return;
        }
        if(p->sibling()->color == RED) {
            p->parent->color = RED;
            p->sibling()->color = BLACK;
            if(p == p->parent->leftTree)
                //rotate_left(p->sibling());
                rotate_left(p->parent);
            else
                //rotate_right(p->sibling());
                rotate_right(p->parent);
        }
        if(p->parent->color == BLACK && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            delete_case(p->parent);
        } else if(p->parent->color == RED && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            p->parent->color = BLACK;
        } else {
            if(p->sibling()->color == BLACK) {
                if(p == p->parent->leftTree && p->sibling()->leftTree->color == RED
                        && p->sibling()->rightTree->color == BLACK) {
                    p->sibling()->color = RED;
                    p->sibling()->leftTree->color = BLACK;
                    rotate_right(p->sibling()->leftTree);
                } else if(p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
                        && p->sibling()->rightTree->color == RED) {
                    p->sibling()->color = RED;
                    p->sibling()->rightTree->color = BLACK;
                    rotate_left(p->sibling()->rightTree);
                }
            }
            p->sibling()->color = p->parent->color;
            p->parent->color = BLACK;
            if(p == p->parent->leftTree){
                p->sibling()->rightTree->color = BLACK;
                rotate_left(p->sibling());
            } else {
                p->sibling()->leftTree->color = BLACK;
                rotate_right(p->sibling());
            }
        }
    }

    void insert(Node *p, int data){
        if(p->value >= data){
            if(p->leftTree != NIL)
                insert(p->leftTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->leftTree = tmp;
                insert_case (tmp);
            }
        } else {
            if(p->rightTree != NIL)
                insert(p->rightTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->rightTree = tmp;
                insert_case (tmp);
            }
        }
    }

    void insert_case(Node *p){
        if(p->parent == NULL){
            root = p;
            p->color = BLACK;
            return;
        }
        if(p->parent->color == RED){
            if(p->uncle()->color == RED) {
                p->parent->color = p->uncle()->color = BLACK;
                p->grandparent()->color = RED;
                insert_case(p->grandparent());
            } else {
                if(p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
                    rotate_left(p);
                    p->color = BLACK;
                    p->leftTree->color = p->rightTree->color = RED;
                } else if(p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
                    rotate_right(p);
                    p->color = BLACK;
                    p->leftTree->color = p->rightTree->color = RED;
                } else if(p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_right(p->parent);
                } else if(p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_left(p->parent);
                }
            }
        }
    }

    void DeleteTree(Node *p){
        if(!p || p == NIL){
            return;
        }
        DeleteTree(p->leftTree);
        DeleteTree(p->rightTree);
        delete p;
    }
public:

    bst() {
        NIL = new Node();
        NIL->color = BLACK;
        root = NULL;
    }

    ~bst() {
        if (root)
            DeleteTree (root);
        delete NIL;
    }

    void inorder() {
        if(root == NULL)
            return;
        inorder (root);
        cout << endl;
    }

    void insert (int x) {
        if(root == NULL){
            root = new Node();
            root->color = BLACK;
            root->leftTree = root->rightTree = NIL;
            root->value = x;
        } else {
            insert(root, x);
        }
    }

    bool delete_value (int data) {
        return delete_child(root, data);
    }
private:
    Node *root, *NIL;
};

本部分基本都是基于红黑树的拓展,代码调试难度很大,因为要同时准备acm,先跳过这一部分。

第四部分:传说门

----------------------------------------------(持续更更新中)---------------------------------------------


💭💭💭💭💭💭