# data-structures-and-algorithms

**Repository Path**: anzhiruo_code/data-structures-and-algorithms

## Basic Information

- **Project Name**: data-structures-and-algorithms
- **Description**: 数据结构与算法总结
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-05-27
- **Last Updated**: 2021-11-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构

## 数组结构

JavaScript中的数组结构封装的很好了,直接调API就完事了,所以就不总结了

数组的优点:

​	1.通过下标去获取信息,查找速度非常块

​	2.缺点是增删操作非常耗费性能



## 栈结构(Stack)

### 概念

1.栈结构是一种受限的线性结构,与之相似的是数组结构,数组可以在任意位置删除或添加,而栈结构不可以

2.栈结构只能后进先出,一层层堆叠,要想删除或添加,只能从上往下删除,或从底部往上面添加

3.栈的底部叫栈底,顶部叫栈顶,添加叫做入栈/压栈/进栈,删除叫做出栈/弹栈/退栈

4.栈有俩种实现方式,一种是基于数组,一种是基于链表,JavaScript中本身没有链表



### 生活实例

​	1.堆叠的盘子

​	2.堆叠的作业本

​	3......



### 程序实例

​	1.函数调用栈(A函数中调用了B函数,B函数中调用了C,则栈结构会先把A压入栈,然后再压入B,C,等到C执行完,弹出栈,B弹出,A最后弹出)

​	2.......



### 栈结构总结

​	栈结构是一种受限的线性结构,它的特点是**后进先出**(LIFO)



### 栈结构面试题

​	1.

![](README.assets/%E6%A0%88%E7%BB%93%E6%9E%84%E9%9D%A2%E8%AF%95%E9%A2%98-1622107331691.png)

​	解题思路:

​		本体的意思是哪些出栈的顺序是可能发生的,而进栈的顺序也不是连续的,不然的话只有一种可能了(123456),因此,我们需要根据答案来判断,首先是A答案,5先出栈,这就说明6已经在栈底了,然后5在6的上面,然后最上面的5出栈没问题,然后再把4压入栈,然后4出栈,这也是可以的,然后3再进栈,随后出栈,然后6出栈,然后再压入1,再出来,所以A答案没问题,再看B答案,4出栈,就代表此时,6在栈底5在倒数第二,倒数第三是4,此时栈顶的就是4,然后再按A答案的思路来解题,确认B也没问题,CD答案同样处理,得出C答案不可能是出栈的序列



### 栈结构代码实现

![](README.assets/%E8%87%AA%E5%AE%9A%E4%B9%89%E6%A0%88%E7%9A%84%E6%96%B9%E6%B3%95.png)

```
	//栈结构数组的实现,后面还有基于链表的实现
	class Stack{
            //模拟栈
            items = [];

            //1.push压栈
            push(element){
                return this.items.push(element);
            }

            //2.pop弹栈
            pop(){
                return this.items.pop();
            }

            //3.peek返回栈顶元素
            peek(){
                return this.items[this.items.length-1]
            }

            //4.isEmpty栈是否为空
            isEmpty(){
                return this.items.length>0 ? false : true;
            }

            //5.size查看栈的长度
            size(){
                return this.items.length;
            }

            //6.toString打印栈的内容
            toString(){
                let str= '';
                this.items.forEach(val => str += val+'  ');
                return str;
            }

        }
```

### 栈结构实现十进制转二进制

```
	//例子:将十进制转成二进制,dec:十进制的缩写,bin:二进制的缩写,2:to
        function dec2bin(decNum) {
            //创建栈实例  
            let s = new Stack();
            //循环压入十进制数模2的值,十进制转二进制的算法:除2取余
            while(decNum>0){
                s.push(decNum % 2)
                //更新十进制数
                decNum = Math.floor(decNum / 2)
            }
            let bin = '';
            //循环拼接弹栈的值
            while(!s.isEmpty()){
                bin += s.pop();
            }
            //返回二进制值
            return bin;
        }
```



## 队列(Queue)

### 概念

1.队列也是一种受限的线性结构

2.队列最前面的叫前端,最后的叫后端

3.它只能在前端删除元素,在后端添加元素,特点是先进先出



### 队列总结

​	只能在前端删除元素,在后端添加元素,先进先出



### 生活实例

​	1.排队上厕所

​	2.排队买东西

### 程序实例

​	1.打印队列

​	2.线程队列



### 队列结构的代码实现

1.基于数组的实现

![](README.assets/%E8%87%AA%E5%AE%9A%E4%B9%89%E9%98%9F%E5%88%97%E7%9A%84%E6%96%B9%E6%B3%95.png)

```
class Queue{
            items = []

            //向队列尾部添加一个或多个元素
            enqueue(element){
                return this.items.push(element)
            }

            //移除队列的第一项,并返回移除的元素
            dequeue(){
                return this.items.shift();
            }

            //返回队列的第一个元素,最先添加的也是最先被移除的
            front(){
                return this.items[0];
            }

            //判断队列是否为空,是则返回true,否则返回false
            isEmpty(){
                return this.items.length == 0;
            }

            //返回队列包含的元素个数
            size(){
                return this.items.length;
            }

            //打印队列中的元素
            toString(){
                let str = '';
                for (const val of this.items) {
                    str += val+'  ';
                }
                return console.log(str);
            }
        }
        let q = new Queue();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.toString(); */
```

2.基于链表的实现(暂未实现)

### 队列面试题:击鼓传花

```
		//面试题:击鼓传花
        /*规则:
            1.传入所有游戏人的名字,然后传入指定淘汰的数字,然后所有人安顺序数数,数到指定数字的人淘汰,其他人继续从头数数,知				道只剩下一个人,则游戏结束
            2.请找出最后的胜者.
        */
        function passGame(nameList,num) {  
            let q = new Queue();
            for (const val of nameList) {
                q.enqueue(val)
            }
            while(q.size()>1){
                for (let i = 0; i < num-1; i++) {
                    q.enqueue(q.dequeue())
                }
                q.dequeue()
            }

            let name = q.front();
            let nameIndex = nameList.indexOf(name);
            console.log('获胜者是:'+name+'. 对应的下标是:'+nameIndex);
        }
        let nameList = ['张三','李四','王五','王麻子','郭杰瑞','小红','李雷'];
        passGame(nameList,4); 
```



## 优先级队列

### 概念

​	1.普通的队列只会先处理前端的元素,但是优先级队列会根据元素的级别来判断谁该优先处理,比较完优先级后才会得出正确的队列位置

​	2.每个元素不再是一个数据,还包含了数据的优先级

​	3.在添加方式中,根据优先级放入正确的位置



### 生活实例

​	1.高铁的座位等级

​	2.飞机的舱位

​	3.医院急诊科,患者的生病严重程度

### 程序实例

​	1.线程的优先程度



### 优先级队列的实现

```
	class PriorityQueue{
            items = [];

            //实现插入方法,priority值越小,则优先级越高
            enqueue(element,priority){
                let queueElement = {element,priority};

                //如果插入的队列为空,则不用排序直接比较
                if(this.items.length == 0){
                    this.items.push(queueElement);
                }else{//否则需要比较优先级进行排序
                    //判断元素是否完成了插入,如果已进入队列则将标记置为true,否则不变
                    let flag = false;
                    for (let i = 0; i < this.items.length; i++) {
                        if(this.items[i].priority > queueElement.priority){
                            //把新元素插入到队列中的正确位置上
                            this.items.splice(i,0,queueElement);
                            //将是否插入队列的位置,置为true;
                            flag = true;
                            //元素已经插入,则直接跳出循环
                            break;
                        }
                    }
                    //如果没有完成插入,则代表此元素优先级最低,需要放到队列后端
                    if(!flag){
                        this.items.push(queueElement);
                    }
                }
            }

            //移除队列的第一项,并返回移除的元素
            dequeue(){
                return this.items.shift();
            }

            //返回队列的第一个元素,最先添加的也是最先被移除的
            front(){
                return this.items[0];
            }

            //判断队列是否为空,是则返回true,否则返回false
            isEmpty(){
                return this.items.length == 0;
            }

            //返回队列包含的元素个数
            size(){
                return this.items.length;
            }

            //打印队列中的元素
            toString(){
                console.log(this.items);
            }
        }
        let q = new PriorityQueue();
        q.enqueue('qwe',10);
        q.enqueue('wto',20);
        q.enqueue('ass',30);
        q.enqueue('tgp',89);
        q.enqueue('otg',15);
        q.enqueue('adc',11);
        q.toString();
```



## 链表

### 单向链表的概念

​	1.链表的每一个元素都是由一个存储元素本身的节点和一个指向下一个元素的指针构成,它在内存中的存储空间不必连续

​	2.链表的优点是:1.可以进行很快的删除和插入2.大小可以无限的衍生下去3.链表创建时不必是连续的空间,可以灵活的管理内存

​	3.链表的缺点是:1.每次取值都要从头开始查找,效率较低.2.无法直接通过下标获取目标值



### 单向链表生活实例

​	1.链表非常类似于火车,火车头相当于链表的head(指向第一个节点),每截车厢都相当于一个节点,最后一个节点的指针指向null,如果链表		一个节点也没有,则head指向null



### 单向链表的实现

```js
	<script>
        /* 链表的常见方法
            1.append(element):向链表尾部添加一个新的项
            2.insert(position,element):向向链表的特定位置插入一个新的项
            3.get(position):获取对应位置的元素
            4.indexOf(element):返回元素在链表中的索引,如果元素中没有该索引则返回-1
            5.update(position,element):修改某个位置的元素
            6.removeAt(posotion):从链表的特定位置移除一项
            7.remove(element):从链表中移除一项
            8.isEmpty():如果链表中不包含元素返回true,否则返回false
            9.size():返回链表的长度
            10.toString():格式化输入链表的值

        */
        class LinkedList{
            head = null;
            length = 0;

            //1.append():追加节点到最后的方法
            append(data){
                //创建新添加的节点
                let newNode = new Node(data);
                
                //判断是否为第一个节点
                if(this.length == 0){ //是第一个节点
                    //把第一个节点赋值给head
                    this.head = newNode;
                }else{                //不是第一个节点
                    //找到最后一个节点
                    let current = this.head;
                    while(current.next){
                        current = current.next;
                    }
                    //把新节点赋值给最后一个节点的指针
                    current.next = newNode;
                }
                //链表增加一个长度
                this.length += 1;
            }

            //2.insert(position,element):向向链表的特定位置插入一个新的项
            insert(position,element){
                //边界值判断,不合法的位置需要直接终止
                if(position < 0 || position > this.length) return false;

                //先创建新的节点
                let newNode = new Node(element);

                //如果插入到第一个位置
                if(position === 0){
                    //先把新node的next的值赋为原来那个node(因为原来的node变成最后了)
                    newNode.next = this.head;
                    //把head指向新node
                    this.head = newNode;
                }else{ //插入到任意位置(包含了插入到最后的情况)
                    //定义标记,控制循环次数
                    let index = 0;
                    //定义变量更新当前节点
                    let current = this.head;
                    //定义变量用来保存更新前的节点
                    let pre = null;
                    //循环查找插入的位置
                    while(index++ < position){
                        //保存更新前的节点
                        pre = current;
                        //更新当前节点
                        current = current.next;
                    }
                    newNode.next = current;
                    pre.next = newNode;
                }
                this.length += 1;
                return true;
            }

            //理解上面俩个方法的话,其它方法其实很简单了
            //3.get():根据位置获取数据
            get(position){
                //边界值判定
                if(position < 0 || position >= this.length) return false;

                //获取当前节点
                let current = this.head;
                let index = 0;
                //如果index等于position的时候则代表找了,就停止
                while(index++ < position){
                    current = current.next;
                }
                //返回找到的值
                return current.data;
            }

            //4.indexOf(element):根据值获取值对应的下标
            indexOf(data){
                let current = this.head;
                let index = 0;
                //遍历条件为所有节点
                while(current){
                    //当前节点等于传入的值,就返回对应的下标
                    if(current.data === data){
                        return index;
                    }
                    //更新当前节点和当前节点对应的下标
                    current = current.next;
                    index++;
                }
                //没找到就返回-1
                return -1;
            }

            //5.update():修改某个位置的元素
            update(position,data){
                //边界值判定
                if(position < 0 || position >= this.length) return false;

                let current = this.head;
                let index = 0;
                while(index++ < position){
                    current = current.next;
                }
                current.data = data;
                return true;
            }

            //6.removeAt(posotion):从链表的特定位置移除一项
            removeAt(position){
                //边界值判定
                if(position < 0 || position >= this.length) return false;

                //分俩步走:1.移除第一项(0)2.移除其它项
                if(position === 0){
                    //移除第一项
                    this.head = this.head.next;
                }else{
                    //移除其它的项
                    let current = this.head;
                    let pre = null;
                    let index = 0;
                    while(index++ < position){
                        pre = current;
                        current = current.next;
                    }
                    pre.next = current.next;
                    return true;
                }

            }

            //10.toString():格式化输出链表
            toString(){
                if(this.length === 0){
                    console.log('链表为空!');
                }else{
                    //定义变量
                    let current = this.head;
                    let linkedStr = '';
                    let index = 0;
                    while(current){
                        linkedStr += current.data + ' ';
                        current = current.next;
                    }
                    return linkedStr;
                }
            }
        }

        //新节点对象
        class Node{
            data = null;
            next = null;
            constructor(data){
                this.data = data;
            }
        }

        //测试代码
        let linkedList = new LinkedList();
        
        //测试append方法
        linkedList.append('aaa');
        linkedList.append('bbb');
        linkedList.append('ccc');
        linkedList.append('ddd');
        linkedList.append('eee');

        console.log(linkedList.toString());
        //测试insert方法
        /* linkedList.insert(1,'aaa');
        console.log(linkedList.toString()); */
        
        //测试get方法
        /* console.log(linkedList.get(0));
        console.log(linkedList.get(3)); */

        //测试indexOf方法
        /* console.log(linkedList.indexOf('aaa'));
        console.log(linkedList.indexOf('eee'));
        console.log(linkedList.indexOf('ccc')); */
    
        //测试update方法
        /* linkedList.update(0,'ggg');
        linkedList.update(4,'vvv');
        linkedList.update(3,'sss');
        console.log(linkedList.toString()); */
    
        //测试removeAt(position)
        /* linkedList.removeAt(0);
        linkedList.removeAt(1);
        linkedList.removeAt(2);
        console.log(linkedList.toString()); */

        //其余方法略...
    </script>
```



### 双向链表的概念

​	1.既可以从头遍历到尾,也可以从尾遍历到头

​	2.每个节点就有到前面节点的引用也有到下一个节点的引用

​	3.它的缺点是删除或插入时,需要处理四个引用,实现比较复杂,比单向链表占用更多的内存

​	4.图示如下:

![](README.assets/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8%E7%BB%93%E6%9E%84%E5%9B%BE%E7%A4%BA.png)

### 双向链表生活实例

​	1.记事本的实现,每行存储一个节点,上下行切换,双向链表随之切换



### 双向链表的实现

```
	<script>
        //双向链表类
        function Node(element) {
            this.element = element
            this.next = null
            this.previous = null
        }

        //根据数据查找节点
        function find(element) {
            var currentNode = this.head
            while (currentNode.element != element) {
                if (currentNode.next == null) {
                    console.log('can not find this node; maybe not have this node')
                    return 'error'
                }
                currentNode = currentNode.next
            }
            return currentNode
        }

        //插入
        function insert(newelement, currentelement) {
            var newNode = new Node(newelement)
            var currentNode = this.find(currentelement)
            if (currentNode === 'error') {
                console.log('无法插入，要插入节点不存在')
                return
            }
            if (currentNode.next != null) {
                newNode.next = currentNode.next
                currentNode.next = newNode
                newNode.previous = currentNode
                newNode.next.previous = newNode
            } else {
                currentNode.next = newNode
                newNode.previous = currentNode
            }
        }

        删除
        function remove(element) {
            var currentNode = this.find(element)
            if (currentNode === 'error') {
                console.log('要移除节点不存在')
                return
            }
            /*首先是不是头尾节点的情况*/

            if (currentNode.next != null && currentNode.previous != null) {
                currentNode.previous.next = currentNode.next
                currentNode.next.previous = currentNode.previous
                currentNode.next = null
                currentNode.previous = null
            } else if (currentNode.previous == null) {
                /*当是头节点的时候*/
                this.head = currentNode.next
                currentNode.next.previous = null
                currentNode.next = null
            } else if (currentNode.next == null) {
                /*当是尾节点的时候 */

                currentNode.previous.next = null
                currentNode.previous = null
            }
        }

        //打印
        function showlist() {
            var head = this.head
            do {
                console.log(head.element)
                head = head.next
            } while (head != null)
        }

        //初始化节点
        function initlist() {
            this.head = new Node('one')
            this.find = find
            this.insert = insert
            this.remove = remove
            this.showlist = showlist
            this.lastNode = lastNode
            this.append = append
        }

        //添加到最后
        function append(element) {
            var lastnode = this.lastNode()
            var newNode = new Node(element)
            lastnode.next = newNode
            newNode.previous = lastnode
        }

        //最后的节点
        function lastNode() {
            var head = this.head
            while (head.next != null) {
                head = head.next
            }
            return head
        }
        var list = new initlist()
        list.insert('two', 'one')
        list.insert('four', 'two')
        list.insert('three', 'two')

        // console.log(list.head.next)
        list.showlist()
        list.append('A')
        list.append('B')
        list.insert('B2', 'B')
        list.showlist()
        console.log(list.lastNode())
        // list.remove('one')
        // list.showlist()
        console.log(list.find('A').previous)
        // console.log(list.find('four').previous)
        // console.log(list.head.element)
    </script>
```



## 集合

### 集合的概念

​	1.集合的实现方式是哈希表

​	2.集合的元素是无序的,元素不可重复

​	3.es6的Set类就是集合

### 集合的实现

![](README.assets/%E9%9B%86%E5%90%88%E7%9A%84%E5%B8%B8%E8%A7%81%E6%96%B9%E6%B3%95.png)

```js
	<script>
        class Set{
            //属性
            items = {}

            //集合中的常见方法
            //添加一个元素
            add(val){
                //判断是否重复
                if(this.has(val)) return false;
                //不重复则添加
                this.items[val] = val;
                //添加成功
                return true;
            }
            //集合中是否包含目标元素
            has(val){
                //判断集合中是否存在
                return this.items.hasOwnProperty(val);
            }
            //删除一个元素
            remove(val){
                //判断是否有这个要删除的元素
                if(this.has(val)){
                    //删除
                    delete this.items[val];
                    //删除成功
                    return true;
                }else{
                    //删除失败
                    return false;
                }
            }
            //清空集合
            clear(){
                this.items = {};
            }
            //集合的长度
            size(){
                //先获取集合的keys数组,然后再根据数组长度得到集合长度
                return Object.keys(this.items).length;
            }
            //集合的所有值
            values(){
                return Object.values(this.items);
            }
        }

        let list = new Set();

        //测试添加方法
        list.add('111');
        list.add('222');
        list.add('333');
        list.add('444');
        console.log(list.values());

        //测试remove方法
        /* list.remove('111');
        console.log(list.values()); */

        //测试size()
        //console.log(list.size());

        //测试clear()
        list.clear();
        //console.log(list.size());
    </script>
```

### 集合之间的操作

> 下面的代码是在已实现上面的集合的前提下运行的

```
		//集合间的操作
            //并集
            union(otherSet){
                let newSet = new Set();
                for (const item in this.items) {
                    newSet.add(item);
                }
                for(const val of otherSet.values()){
                    newSet.add(val);
                }
                return newSet;
            }
            
            //交集操作
            intersection(otherSet){
                let newSet = new Set();
                if(this.size() <= otherSet.size()){
                    this.values().forEach(element => {
                        if(otherSet.has(element)){
                            newSet.add(element);
                        }
                    });
                }else{
                    otherSet.values().forEach(element =>{
                        if(this.has(element)){
                            newSet.add(element);
                        }
                    });
                }
                return newSet;
            }
            
            //差集操作
            difference(otherSet){
                let newSet = new Set();

                this.values().forEach(val=>{
                    if(!otherSet.has(val)){
                        newSet.add(val);
                    }
                })
                return newSet;
            }
        
            //子集操作
            subset(otherSet){
                let flag = false;
                otherSet.values().forEach(val=>{
                    if(this.has(val)){
                        flag = true;
                    }else{
                        flag = false;
                    }
                });
                return flag;
            }
        }

        let list = new Set();

        //测试添加方法
        list.add('111');
        list.add('222');
        list.add('333');
        list.add('444');
        console.log(list.values());


        //测试union():并集
        /* let list2 = new Set();
        list2.add('aaa');
        list2.add('bbb');
        list2.add('222');
        list2.add('111');
        console.log(list2.values());
        console.log(list.union(list2).values()); */

        //测试intersection():交集
        /* let list2 = new Set();
        list2.add('aaa');
        list2.add('bbb');
        list2.add('222');
        list2.add('111');
        console.log(list2.values());
        console.log(list.intersection(list2).values()); */

        //测试difference(set):差集
        /* let list2 = new Set();
        list2.add('aaa');
        list2.add('bbb');
        list2.add('222');
        list2.add('111');
        console.log(list2.values());
        console.log(list.difference(list2).values()); */

        //测试subset():子集
        /* let list2 = new Set();
        list2.add('222');
        list2.add('111');
        list2.add('aaa');
        console.log(list2.values());
        console.log(list.subset(list2)); */
```



## 字典

### 概念

​	1.在JavaScript中es6实现了集合和字典

​	2.字典的主要特点是一一对应的关系

​	3.字典中的key是不可重复的,而value是可以重复的

​	4.字典在有些编程语言中将映射关系称为Map(java中),python中称为字典

​	5.JavaScript中的字典和对象很像但并不是完全一样的

### 生活中的字典

​	1.中文字典:根据拼音去查汉字以及解释

​	2.英文字典:根据英文字母查找单词

### 字典的实现-略



## 哈希表

### 概念

​	1.哈希表的结构就是数组,

​	2.它的神奇之处的地方在于对下标值的一种变换,这种变换称之为哈希函数

​	3.通过哈希函数可以获取到HashCode

​	4.它的优点是能**很快的增删改查性能极高**,时间复杂度接近O(1)

​	5.它的缺点是,**它是无序的**,所以不能对它进行排序操作,**它的key值不可重复**

​	6.**哈希化**:将大数字转化成数组范围内下标的过程

​	7.**哈希函数**:通常我们会将单词转成大数字,大数字再进行哈希化的代码放在同一个函数中,这个函数称为哈希函数(核心)

​	8.哈希表:最终将数据插入到的这个数组,对整个的封装称为哈希表

​	9.冲突:俩个数据进行哈希函数转换后,得出同一个下标,这就是冲突

​	10.解决冲突的方法:

​		10.1.链地址法(也叫拉链法) :把产生冲突的下标存进一个数组或链表中(手动实现)

​		10.2.开放地址法:按一定步长去寻找空白的单元格来添加重复的数据

​	11.装载因子＝哈希项➗哈希表总长度,填装因子越大,效率越低,拉链法的装载因子理论上为无限大,开放地址法的装载因子最大为1(哈希项等于哈希表总长度)

​	12.哈希表的核心是哈希函数,它需要满足的条件有:

​		12.1快速的计算:好的哈希函数中尽可能少的使用除法和乘法,以为它的效率是比较低的

​		12.2均匀的分布:使得哈希项均匀分布可以尽可能少的减少冲突,从而不影响到效率



### 哈希表的实现

```
	<script>
        class HashTable {
            //实际保存数据的地方,用链表法解决冲突,所以storage的大概结构为:[[[key,val],[key,val]],[[key,val]]]
            storage = [];
            //哈希表中已保存的哈希项
            count = 0;
            //哈希表的总长度,这个长度可以自动变换的
            limit = 7;

            //哈希函数:str:字符数据,size:哈希表总长度(limit)
            hashFunc(str, size) {
                let hashFunc = 0;
                for (let i = 0; i < str.length; i++) {
                    //有一个尽量不会重复的hashFunc值
                    hashFunc = 37 * hashFunc + str.charCodeAt(i);
                }
                //取模后,下标值范围在0-size之间,最大不会等于size
                return hashFunc % size;
            }

            //put():插入和修改函数是同一个,因为在哈希表中,有则是修改,无则为插入
            /*实现步骤:
                1.根据key获取索引值 
                2.根据索引值获取桶(bucket)
                    2.1 如果桶不存在,则创建,并且防止该索引的位置
                3.判断是新增还是修改值
                    3.1如果有值则修改,没有值就插入
            */
            //达到目的:将数据插入到数组中
            put(key, val) {
                //获取hashCode,也可以说是storage数组的下标
                let index = this.hashFunc(key, this.limit);
                //console.log(index);
                //bucket是因为这个哈希表的设计是选择链地址法解决冲突才有bucket这个数组,这个数组中存着一个个hashCode重复的数据
                let bucket = this.storage[index];
                //如果这个位置还么有值,则需要创建
                if (bucket == null) {
                    bucket = [];
                    //把创建好的桶添加进哈希表
                    this.storage[index] = bucket;
                }

                for (let i = 0; i < bucket.length; i++) {
                    //里面有相同的key则表示需要修改
                    if (bucket[i][0] === key) {
                        bucket[i][1] = val
                        //修改完后就结束方法
                        return;
                    }
                }

                //如果不是修改,那么就执行插入
                bucket.push([key, val])
                //哈希表的长度加一
                this.count += 1;
            }

            //get(key)
            /*实现步骤:
                1.根据key获取索引值 
                2.根据索引值获取桶(bucket)
                3.如果桶为null,则直接返回-1,表示查找不到
                4.否则遍历桶,同时从桶中取出[key,val]数据,将取出的key与传入的key对比,有则返回,无则返回-1
            */
            get(key) {
                const index = this.hashFunc(key, this.limit);
                let bucket = this.storage[index];
                if (bucket == null) return -1;
                for (let i = 0; i < bucket.length; i++) {
                    if (bucket[i][0] === key) {
                        //把查找到的值返回出去
                        return bucket[i][1];
                    }
                }
                //桶里面也么有
                return -1;
            }

            /*remove(key):实现思路:
                1.根据key获取索引值 
                2.根据索引值获取桶(bucket)
                3.如果桶为null则返回删除元素不存在
                4.否则遍历桶,将key相等的项删除,没有相等的就表示删除的元素不存在              
            */
            remove(key) {
                const index = this.hashFunc(key, this.limit);
                let bucket = this.storage[index];
                if (bucket == null) return null;
                for (let i = 0; i < bucket.length; i++) {
                    if (bucket[i][0] === key) {
                        const val = bucket[i][1];
                        //将对应下标的桶值删除
                        bucket.splice(i, 1);
                        this.count -= 1;
                        //把删掉的值返回出去
                        return val;
                    }

                }
                //桶里面也么有
                return null;
            }

            //isEmpty():判断哈希表是否为空
            isEmpty() {
                return this.count === 0 ? true : false;
            }

            //size():返回哈希表中元素的个数
            size() {
                return this.count;
            }
        }

        //哈希表测试代码
        let ht = new HashTable();
        //测试添加
        ht.put('abc', '111');
        ht.put('bad', '222');
        ht.put('cdd', '333');
        console.log(ht.storage);

        //测试修改
        /* ht.put('aaa','444')
        console.log(ht.storage); */

        //测试删除
        console.log(ht.remove('cdd'));
        console.log(ht.storage);
    </script>
```

## 树结构

### 树的概念

​	1.树结构是非线性的	

​	2.已学数据结构各自的优缺点

数组和链表的:

![](README.assets/%E6%95%B0%E7%BB%84%E5%92%8C%E9%93%BE%E8%A1%A8%E7%BB%93%E6%9E%84%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9.png)

哈希表和树结构的

![](README.assets/%E5%93%88%E5%B8%8C%E8%A1%A8%E5%92%8C%E6%A0%91%E7%BB%93%E6%9E%84%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9.png)

​	2.树结构的一些术语

​		![](README.assets/%E6%A0%91%E7%9A%84%E6%9C%AF%E8%AF%AD1.png)

![](README.assets/%E6%A0%91%E7%9A%84%E6%9C%AF%E8%AF%AD2.png)

​	3.树的表示方法:儿子-兄弟表示法

![](README.assets/%E6%A0%91%E7%9A%84%E5%84%BF%E5%AD%90%E5%85%84%E5%BC%9F%E8%A1%A8%E7%A4%BA%E6%B3%95.png)



### 二叉树的概念

![](README.assets/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%A6%82%E5%BF%B5.png)

### 二叉树的特性

![](README.assets/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%89%B9%E6%80%A7.png)

### 二叉树的表示方法

​	1.数组

​	2.链表(常用)

### 二叉搜索树

​	又名:二叉查找树、二叉排序树,英文缩写:BST

​	![](README.assets/%E4%BB%80%E4%B9%88%E6%98%AF%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.png)

### 二叉搜索树的特点

​	1.相对较小的值总是保持在左节点上,相对较大的值总是保持在右节点上



## 红黑树(很难)

### 简介

​	R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

### 概念

​	**（1）每个节点或者是黑色，或者是红色。**
​	**（2）根节点是黑色。**
​	**（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]**
​	**（4）如果一个节点是红色的，则它的子节点必须是黑色的。**
​	**（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。**

​	**注意**：
​		(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
​		(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

红黑树示意图如下：

![](README.assets/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9B%BE%E8%A7%A3.jpg)

### 红黑树的应用

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。
例如，Java集合中的[TreeSet](http://www.cnblogs.com/skywang12345/p/3311268.html)和[TreeMap](http://www.cnblogs.com/skywang12345/p/3310928.html)，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。



### 红黑树的基本操作

#### (一) 左旋和右旋

​	红黑树的基本操作是**添加**、**删除**。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。
旋转包括两种：**左旋** 和 **右旋**。下面分别对它们进行介绍。

#### (二) 添加

**第一步: 将红黑树当作一颗二叉查找树，将节点插入。**
    红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。
    好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！

**第二步：将插入的节点着色为"红色"。**
    为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
    将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。o(∩∩)o...哈哈

**第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。**
    第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？
    对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。
    对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
    对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。
    对于"特性(4)"，是有可能违背的！
    那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。

#### (三) 删除

​	将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：

**第一步：将红黑树当作一颗二叉查找树，将节点删除。**
    这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：
    ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
    ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
    ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。

**第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。**
    因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。



## 图

### 概念

​	1.图结构是一种与树结构有些相似的数据结构,图论是数学的一个分支

​	2.在数学概念上树是图的一种

​	3.以图为研究对象,研究顶点和边组成的图形的数学理论和方法

​	4.主要研究的目的是事物之间的关系,顶点代表事物,边代表俩个事物之间的关系

![](README.assets/%E5%9B%BE%E7%BB%93%E6%9E%84.png)

### 特点

​	1.一组顶点:通常用V(vertex)表示顶点的集合

​	2.一组边:通常用E(Edge)表示边的集合

​	3.边是顶点和顶点之间的连线

​	4.边可以是有向的,也可以是无向的

### 术语

​	1.顶点:图中的每个顶点,叫为度

​	2.邻点:一条边连接的俩个顶点

​	3.度:一个顶点的度是相邻顶点的数量

​	4.路径:路径是顶点v1,v2,v3....,vn的一个序列

​	5.简单路径:要求不包含重复的顶点

​	6.回路:第一个顶点和最后一个顶点相同的路径称为回路

​	7.无向图:所有的边没有方向

​	8.有向图:图中的边是有方向的

​	9.无权图:边没有带权重(边没有长度,宽度等概念)

​	10.有权图:边带有一定的权重(边长为多少等意思)

### 图的表示方法

​	1.邻接矩阵:矩阵其实就是数组来表示的,二维数组可以表示所有顶点的连接

![](README.assets/%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E8%A1%A8%E7%A4%BA%E6%B3%95.png)

​	2.邻接表:是图的一种链式存储结构，适用于有向图和无向图，对图中每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对有向图来说是以该顶点为弧尾的弧）

​	![](README.assets/%E9%82%BB%E6%8E%A5%E8%A1%A8.png)





# 算法



## 大O表示法

​	大O表示法：[算法](https://baike.baidu.com/item/算法/209025)的时间复杂度通常用[大O符号](https://baike.baidu.com/item/大O符号)表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“[时间复杂度](https://baike.baidu.com/item/时间复杂度/1894057)”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

![](README.assets/%E5%A4%A7O%E8%A1%A8%E7%A4%BA%E5%87%BD%E6%95%B0.png)

![](README.assets/%E5%A4%A7O%E8%A1%A8%E7%A4%BA%E7%9A%84%E6%96%B9%E6%B3%95.png)



## 排序算法

![](README.assets/%E5%B8%B8%E8%A7%81%E6%8E%92%E5%BA%8F.png)