数据结构-持续更新

数据结构与算法

1.Stack

封装的代码:

2.Queue

封装的代码:

3.LinkedList

封装的代码:

// 链表就类似于火车头
function LinkedList() {
    // Node 为存储链表的数据
    function Node(data) {
        this.data = data;// 链表的数据
        this.next = null;// 链表指向下一个数据的指针
    }
    this.length = 0;
    this.head = null;

    // 在链表最后插入一个元素
    LinkedList.prototype.append = function (element) {
        let newNode = new Node(element);

        if (this.length == 0) {
            // 第一次插入,让head指向当前的这个元素
            this.head = newNode;
        } else {
            // 找到最后一个元素 在其的后面插入
            var current = this.head;// 这是第一个元素
            while (current.next) {
                current = current.next;
            }
            // 让最后一个元素指向当前添加的这个节点
            current.next = newNode;

        }
        this.length += 1;  //让当前的链表长度加1
    }

    // 链表数据的字符串形式
    LinkedList.prototype.toString = function () {
        let result = "";
        let current = this.head;
        while (current.next) {
            result += current.data;
            current = current.next;
        }
        result += current.data;
        return result;
    }

    // 向链表的某一个位置插入一个元素
    LinkedList.prototype.insert = function (data, position) {
        if (position < 0 || position > this.length) return false;
        let newNode = new Node(data);
        // 当前是第一个位置
        if (this.length == 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            // 不是第一个位置
            var current = this.head;// 链表的第一个元素
            let index = 0;
            let previous = null;
            while (index++ < position) {
                previous = current;// 前一个
                current = current.next; // 后一个
            }
            // 让前一个元素指向添加的这个元素 让添加的这个元素指向后一个元素
            previous.next = newNode;
            newNode.next = current;
        }
        this.length += 1;  //让当前的链表长度加1
    }

    // 获取指定位置的元素
    LinkedList.prototype.get = function (position) {
        if (position < 0 || position > this.length) return false;

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

    // 返回元素在列表中的索引，如果没有的话就返回-1
    LinkedList.prototype.indexOf = function (element) {
        let index = 0;
        var current = this.head;
        while (index < this.length) {
            if (current.data == element) {
                return index;
            }
            current = current.next;
            index += 1;
        }
        return -1;
    }

    // 修改位置的元素
    LinkedList.prototype.update = function (position, newData) {
        if (position < 0 || position > this.length) return false;
        var index = 0;
        var current = this.head;
        while (index++ < position) {
            current = current.next;
        }
        current.data = newData;
        return true;
    }

    // 移除指定位置的元素
    LinkedList.prototype.removeAt = function (position) {
        if (position < 0 || position > this.length) return false;
        // 如果移除的是第一个位置
        var current = this.head; // 第一个元素
        if (position == 0) {
            current = current.next;
            this.head = current;
        } else {
            // 让前一个元素指向后一个元素
            let index = 0;
            let previous = null;
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
            this.length -=1;
            return true;
        }

    }

    // 根据元素删除某一项
    LinkedList.prototype.remove = function (element) {
        let index = this.indexOf(element)
        this.removeAt(index);
        this.length -=1;
    }
    // 判断当前的列表是为空
    LinkedList.prototype.isEmpty = function () {
        return this.length === 0;
    }
    // 返回当前链表的长度
    LinkedList.prototype.size = function () {
        return this.length;
    }
}

4. DoubleLinkedList

封装的代码:

function DoubleLinkedList() {
    function Node(data) {
        this.data = data;
    }
    this.next = null;
    this.prev = null;
    this.length = 0;

    // 在双向链表的最后插入一个元素
    DoubleLinkedList.prototype.append = function (element) {
        let newNode = new Node(element);
        if (this.length == 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            // 插入的不是最后一个元素
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }

        this.length += 1;

    }

    // 在双向链表的指定位置插入一个元素
    DoubleLinkedList.prototype.insert = function (element, position) {
        if (position < 0 || position > this.length) return false;
        let newNode = new Node(element);
        if (this.length == 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            if (position == this.length) {
                this.tail.next = newNode;
                newNode.prev = this.tail;
                this.tail = newNode;
            } else if (position == 0) {
                // 说明是在第一个位置插入元素
                this.head.prev = newNode;
                newNode.next = this.head;
                this.head = newNode;

            } else {
                var current = this.head;
                let index = 0;
                let previous = null;
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                // 与之前的单项链表相比 这里只是多操作了几个索引
                current.prev = newNode;
                newNode.next = current;
                previous.next = newNode;
                newNode.prev = previous;
            }
        }
        this.length += 1;
    }

    // 获取指定位置的元素
    DoubleLinkedList.prototype.get = function (position) {
        if (position < 0 || position > this.length) return false;
        var current = this.head;
        var index = 0;
        while (index++ < position) {
            current = current.next;
        }
        return current.data;
    }
    // 返回元素在列表中的索引，如果没有的话就返回-1
    DoubleLinkedList.prototype.indexOf = function (element) {
        var current = this.head;
        var index = 0;
        while (index < this.length) {
            if (current.data == element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }
    // 修改位置的元素
    DoubleLinkedList.prototype.update = function (position, newData) {
        if (position < 0 || position > this.length) return false;
        var current = this.head;
        var index = 0;
        while (index++ < position) {
            current = current.next;
        }
        current.data = newData;
    }
    // 移除指定位置的元素
    DoubleLinkedList.prototype.removeAt = function (position) {
        if (position < 0 || position > this.length) return false;
        var current = this.head;  // 第一个元素
       if(this.length ==1){
            this.head = null ;
            this.tail = null ;
       }else{
        if (position == 0) {
            this.head = current.next;
        } else if (position == this.length-1) {
            // 删除的是最后一个元素
           this.tail.prev.next = null; // 让最后一个元素的前一个元素的next指向null
           this.tail = this.tail.prev;
        } else {
            // 中间的元素
            let index = 0;
            while (index++ < position) {
                current = current.next;
            }
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
       }
        this.length -= 1;
    }
    // 根据元素删除某一项
    DoubleLinkedList.prototype.remove = function (element) {
        let index = this.indexOf(element);
        this.removeAt(index);
    }
    DoubleLinkedList.prototype.isEmpty = function () {
        return this.length == 0;
    }
    DoubleLinkedList.prototype.size = function () {
        return this.length;
    }
    DoubleLinkedList.prototype.toString = function () {
        this.backString();
    }
    // 正向遍历返回字符串格式
    DoubleLinkedList.prototype.forwardString = function () {
        let current = this.head;
        let resultStr = " ";
        while (current) {
            resultStr += current.data;
            current = current.next;
        }
        return resultStr;
    }
    // 反向遍历返回字符串格式
    DoubleLinkedList.prototype.backString = function () {
        let current = this.tail;
        let resultStr = " ";
        while (current) {
            resultStr += current.data;
            current = current.prev;
        }
        return resultStr;
    }
}

5. Set

function Set() {
    this.item = {

    }
    // 向集合中添加一个元素
    Set.prototype.add = function (value) {
        this.item[value] = value;
        return true;
    }
    // 从集合中移除一个元素
    Set.prototype.remove = function (value) {
        if (!this.item[value]) return false;
        delete this.item[value];
        return true;
    }
    // 判断某个值在不在这个集合中
    Set.prototype.has = function (value) {
        return this.item[value] ? true : false
    }
    // 清除集合中的所有元素
    Set.prototype.clear = function () {
        this.item = {}
    }
    // 返回集合中所以包含的元素个数
    Set.prototype.size = function () {
        return Object.keys(this.item).length;
    }
    // 返回一个包含集合中所有值的元素
    Set.prototype.values = function () {
        return Object.keys(this.item);
    }
    // 并集
    Set.prototype.unionSet = function (set) {
        let newSet = new Set();
        let values = this.values();

        for (let key in values) {
            newSet.add(values[key]);
        }
        let newValues = set.values();
        for (let key in newValues) {
            newSet.add(newValues[key]);
        }
        return newSet;
    }
    // 交集
    Set.prototype.intersectionSet = function (set) {
        let set2 = new Set();
        // 遍历A 取出a里面的元素 判断b中有没有这个元素
        let values = this.values();
        for(var i=0 ;i<values.length ;i++){
            if(set.has(values[i])){
                set2.add(values[i])
            }
        }
        return set2;
    }


    // 差集
    Set.prototype.diffentSet = function (set) {
        let set2 = new Set();
        // 遍历A 取出a里面的元素 判断b中是不是没有这个元素
        let values = this.values();
        for(var i=0 ;i<values.length ;i++){
            if(!set.has(values[i])){
                set2.add(values[i])
            }
        }
        return set2;
    }
    // 子集
    Set.prototype.subSet = function (set) {
        let set2 = new Set();
        let values = this.values();
        for(var i=0 ;i<values.length ;i++){
            if(!set.has(values[i])){
                return false;
            }
        }
        // 如果循环结束了还没有false 那说明是包含的
        return true;
    }
}

6. Hash

function HashTable() {
    this.storage = [];
    this.count = 0;
    this.limit = 7;

    // 封装一个hash函数
    HashTable.prototype.hashFunc = function (str, size) {
        // 将一个单词转成一个非常大的数字
        var hashCode = 0;
        for (var i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i);
        }
        // 再通过这个非常大的数据转成下标值,size是数组的长度
        console.log(hashCode)
        return hashCode % size;
    }
    // 插入和修改的操作
    HashTable.prototype.put = function (key, value) {
        var index = this.hashFunc(key, this.limit);
        var bucket = this.storage[index];
        if (bucket == null) {
            bucket = [];
            this.storage[index] = bucket;
        }
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] == key) {
                bucket[i][1] = value;
            }
        }
        bucket.push([key, value]);
        // 判断是否需要进行扩容
        if (this.count > this.limit * 0.75) {
            let newLimit = this.limit * 2;
            while (this.isPrimeNumber(newLimit)) {
                newLimit++;
            }

        }

        this.count += 1;
    }




    // 删除元素
    HashTable.prototype.remove = function (key) {
        var index = this.hashFunc(key, this.limit);
        var bucket = this.storage[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] == key) {
                bucket.splice(i, 1);
                this.count--;
                return;
            }
        }
        // 判断是否需要进行扩容
        if (this.count < this.limit * 0.25) {
            let newLimit = Math.floor(this.limit / 2);
            while (this.isPrimeNumber(newLimit)) {
                newLimit++;
            }

        }
    }

    // 获取一个元素
    HashTable.prototype.get = function (key) {
        var index = this.hashFunc(key, this.limit);
        var bucket = this.storage[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] == key) {
                return bucket[i][1];
            }
        }
        return false;
    }

    // 是不是为空
    HashTable.prototype.isEmpty = function () {
        return this.count == 0;
    }

    // HashTable的长度
    HashTable.prototype.size = function () {
        return this.count;
    }
    // 是不是质数
    HashTable.prototype.isPrimeNumber = function (number) {
        if (!Number.isInteger(number)) return;
        var temp = parseInt(Math.sqrt(number))
        for (let i = 2; i < temp; i++) {
            if (temp % i == 0) {
                return false
            }
        }
        return true;
    }
    HashTable.prototype.expand = function (newLimit) {
        // 将之前的hashTable保存起来
        let oldStorage = this.storage;
        // 全部重置
        this.limit = newLimit;
        this.count = 0;
        this.storage = [];
        // 遍历oldStorage中的每一项
        for (let i = 0; i < oldStorage.length; i++) {
            var bucket = oldStorage[i];
            if (bucket == null) continue;
            // 再遍历每一项里的每一项 把他们添加到新的HashTable中去
            for (let k = 0; k < bucket.length; k++) {
                this.put(bucket[k][0], bucket[k][1]);
            }
        }

    }
}