数据结构封装


阅读数: 次   

数据结构

一些数据结构的JS实现

1. 前缀树封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Trie {
            constructor(){
                this.sons = {};
            }

        Trie.prototype.insert = function(word) {
            let node = this.sons;
            for(let c of word) {
                if(!node[c]) {
                    node[c] = {}
                }
                node = node[c];
            }
            node.isEnd = true;
        };

        Trie.prototype.search = function(word) {
            let node = this.sons;
            for(let c of word) {
                if(!node[c]) return false;
                node = node[c];
            }
            return node.isEnd==true ? true : false;
        };

        Trie.prototype.startsWith = function(prefix) {
            let node = this.sons;
            for(let c of prefix) {
                if(!node[c]) return false;
                node = node[c];
            }
            return true;
        };
  }

2. 树状数组及线段树封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
例题:单点修改 LC307
树状数组和线段树具有相似的功能，但他俩毕竟还有一些区别：
        树状数组能有的操作，线段树一定有；
        线段树有的操作，树状数组不一定有。
        树状数组的代码要比线段树短，思维更清晰，速度也更快，在解决一些单点修改的问题时，树状数组是不二之选。整体的时间复杂度O(nlog_2n)空间复杂度O(n)

        //树状数组  二叉索引树  观察这棵树结构，可以发现叶子结点的二进制的最后一位为1。接下来的结点为倒数第二位为1....
        某元素的父结点为该结点加上此结点的二进制截出最后一位的1(后面会讲的lowBit函数)。
        如6(110)+2(010)=8(1000)

        // 上来先把三个方法写出来
        {
            int[] tree;
            int lowbit(int x) {// x不能等于0, 否则会进入死循环, 所以树状数组通常使用的下标会执行+1操作
                return x & -x;
            }
            // 查询前缀和的方法
            int query(int x) {
                int ans = 0;
                for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
                return ans;
            }
            // *****在树状数组 x 位置中增加值 u  即找到1所在结点，然后用lowBit函数依次自下而上更新其所有父结点******
            void add(int x, int u) {//n:树状数组长度
                for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
            }
        }

            // 初始化「树状数组」，要默认数组是从 1 开始
            {
                for (int i = 0; i < n; i++) add(i + 1, nums[i]);
            }

            // 使用「树状数组」：
            {   
                void update(int i, int val) {
                    // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - nums[i]
                    add(i + 1, val - nums[i]); 
                    nums[i] = val;
                }
                
                int sumRange(int l, int r) {
                    return query(r + 1) - query(l);
                }
            }

/********************************************************************************************************/
        //线段树  单点修改例题模板
        关于线段树设计的几种操作：
        void build(int u, int l, int r)：含义为从编号为 u 的节点开始，构造范围为 [l,r] 的树节点；
        void update(int u, int x, int v)：含义为从编号为 u 的节点开始，在 x 位置增加 v；
        更具一般性（涉及区间修改）的操作应该为 void update(int u, int l, int r, int v)，代表在 [l,r] 范围增加 v；
        int query(int u, int l, int r)：含义为从编号为 u 的节点开始，查询 [l,r] 区间和为多少。
        注意：对于编号为 u 的节点而言，其左子节点的编号为 u << 1，其右节点的编号为 u << 1 | 1。

        var Node = function(l, r) {
            this.l = l
            this.r = r
            this.v = 0
        }

        var NumArray = function(nums) {
            const n = nums.length
            this.tr = new Array(n * 4)
            this.nums = nums
            this.build(1, 1, n)
            for(let i = 0; i < n; i++)
                this.update_tree(1, i + 1, nums[i])
        };

        NumArray.prototype.build = function(u, l, r) {
            this.tr[u] = new Node(l, r)
            if(l < r) {
                const mid = l + r >> 1
                this.build(u << 1, l, mid)
                this.build(u << 1 | 1, mid + 1, r)
            }
        }

        NumArray.prototype.update_tree = function(u, x, v) {
            if(this.tr[u].l == x && this.tr[u].r == x) {
                this.tr[u].v += v
                return
            }
            const mid = this.tr[u].l + this.tr[u].r >> 1
            if(x <= mid)
                this.update_tree(u << 1, x, v)
            else
                this.update_tree(u << 1 | 1, x, v)
            this.pushup(u)
        }

        NumArray.prototype.query = function(u, l, r) {
            if(l <= this.tr[u].l && this.tr[u].r <= r)
                return this.tr[u].v
            let ans = 0
            const mid = this.tr[u].l + this.tr[u].r >> 1
            if(l <= mid)
                ans += this.query(u << 1, l, r)
            if(mid < r)
                ans += this.query(u << 1 | 1, l, r)
            return ans
        }

        NumArray.prototype.pushup = function(u) {
            this.tr[u].v = this.tr[u << 1].v + this.tr[u << 1 | 1].v
        }

        NumArray.prototype.update = function(index, val) {
            this.update_tree(1, index + 1, val - this.nums[index])
            this.nums[index] = val
        };

        NumArray.prototype.sumRange = function(left, right) {
            return this.query(1, left + 1, right + 1)
        };

3. Set封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class mySet {
           constructor(optionsArr = []) {
               if (!(optionsArr instanceof Array)) throw Error('参数只能为数组')
               this.list = {}
               this.size = optionsArr.length
               optionsArr.forEach(val => {
                   this.list[val] = val
               })
           }
           
           add(val) {
               if (!this.list[val]) {
                   this.list[val] = val
                   this.size++
                   return true
               }
               return false
           }

           has(val) {
               if (val !== null &;&; typeof val === 'object') return false
               return this.list.hasOwnProperty(val)
           }

           delete(val) {
               if (this.list[val]) {
                   delete this.list[val]
                   this.size--
                   return true
               }
               return false
           }

           clear() {
               this.list = {}
               this.size = 0
           }

           keys() {
               return Object.values(this.list)
           }

           values() {
               return Object.values(this.list)
           }
           
           entries() {
               return Object.entries(this.list).map(item => {
                   item[0] = item[1]
                   return item
               })
           }

           forEach(callback) {
               let keys = this.keys()
               for (let i = 0; i < keys.length; i++) {
                   callback(keys[i], keys[i], this)
               }
           }

       }

4. 哈希表封装基于数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
class hashTable {
           constructor() {
               this.map = [];
               this.size = 0;// 数据的存储量
               this.max = 7;// 容量长度最好为质数,利于数据在容器中均匀分布
           }

           //哈希函数
           getHash(key， size) {
               //定义一个hashCode
               let hashCode = 0;
               for (let i = 0; i < key.length; i++) {
                   hashCode += hashCode * 37 + key.charCodeAt(i);
               }
               //范围压缩 求余获得位置下标
               let index = hashCode % size;
               return index;
           }

           size(){
               return this.size;
           }


           // 新增&修改
           set(key, value) {
               // 1.通过哈希函数获取到存储位置的下标
               let index = this.getHash(key,this.max);
               // 2.判断这个位置是否有存储内容
               this.storage[index] = this.storage[index] == null ? [] : this.storage[index];
               // 3.判断是修改还是新增
               for(let i = 0;i < this.storage[index].length;i++){
                   // 修改
                   if(this.storage[index][i][0] === key){
                       this.storage[index][i][1] = value;
                       return
                   }
               }
               // 新增
               this.storage[index].push([key,value]);
               // 4.存储数量+1
               this.size++;
               // 5.判断是否需要扩容
               if(this.size > this.max * 0.75){
                   this.resize(this.getPrime(this.max * 2))
               }
           }

           has(key) {
               return !!this.map[this.getHash(key, this.max)];
           }
           //获取
           get(key) {
               // 1.通过哈希函数获取到位置下标
               let index = this.getHash(key,this.max);
               // 2.判断此位置处是否为空
               let bucket = this.storage[index];
               if(bucket == null) return null;
               // 3.线性查找此位置中存储的数据
               for(let i = 0; i < bucket.length;i++){
                   // 找到返回数据
                   if(bucket[i][0] === key){
                       return bucket[i][1]
                   }
               }
               // 没找到返回null
               return null
           }
           //删除
           delete(key) {
               if (this.has(key)) {
               this.map[this.getHash(key, this.max)] = undefined;
               this.size--;
               }
           }

           clear() {
               this.map = [];
               this.size = 0;
           }

            // 哈希表扩容&缩容
           resize(newlimit){
               // 1.用oldStorage承载之前的数据
               let oldStorage = this.storage;
               // 2.重置storage
               this.storage = [];
               this.max = newlimit;
               this.count = 0;

               // 3.遍历 将之前的数据重新存储到新的storage中
               for(var i = 0; i < oldStorage.length; i++){
                   let bucket = oldStorage[i];
                   if(bucket == null) continue;
                   for(var j = 0; j < bucket.length; j++){
                       let tuple = bucket[j];
                       this.put(tuple[0],tuple[1])
                   }
               }
           }

           // 判断是否是质数
           isPrime(num){
           let temp = parseInt(Math.sqrt(num));
           for(var i = 2; i <= temp; i++){
               if(num % i === 0){
                   return false
               }
           }
           return true
       }

           // 获取质数
           getPrime(num){
               while(!this.isPrime(num)){
                   num++
               }
               return num
           }
   }

5. 堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
大根堆 未封装 递归的
        有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆：
        shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。
        shiftDown(): 如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”。
        shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 O(log n)。

        基于这两个原始操作还有一些其他的操作：

        insert(value): 在堆的尾部添加一个新的元素，然后使用 shiftUp 来修复堆。
        remove(): 移除并返回最大值（最大堆）或者最小值（最小堆）。为了将这个节点删除后的空位填补上，需要将最后一个元素移到根节点的位置，然后使用 shiftDown 方法来修复堆。


        let heap = [];
        function swap(idx1,idx2){
          let temp;
          temp = heap[idx1];
          heap[idx1] = heap[idx2];
          heap[idx2] = temp;
        }

        function shiftup(idx){//子点
          let _idx = Math.floor((idx - 1) / 2);//parent
          if(idx != 0 && heap[_idx] < heap[idx]){
          swap(_idx,idx);
          shiftup(_idx);
            }
        }

        function shiftDown(idx){//父点
          if(idx * 2 + 1 < heap.length && heap[idx * 2 + 1] > heap[idx]){
            swap(idx * 2 + 1,idx);
            shiftDown(idx * 2 + 1);
          }else if(idx * 2 + 2 < heap.length && heap[idx * 2 + 2] > heap[idx]){
            swap(idx * 2 + 2,idx);
            shiftDown(idx * 2 + 2);
          }
        }

        function insert(val){
          heap.push(val);
          shiftup(heap.length - 1);//从下往上冒
        }

        function remove(){
          swap(0,heap.length - 1);
          heap.pop();
          shiftDown(0);
          return heap[0];//从上往下 堆
        }
        insert(1);
        insert(3);
        insert(2);
        insert(5);
        remove();
        insert(4);
        insert(6);
        remove();
        console.log(heap);//4
        
        
        
     小根堆 封装 迭代的    例题:数组中第k大的数字LC215
        
        树变 真实数组也要变
        class MinHeap{
            constructor(data=[]){
                this.data = data
                this.comparator = (a,b)=>a-b
            }
            size(){
                return this.data.length
            }
            swap(index1,index2){
                [this.data[index1],this.data[index2]] = [this.data[index2],this.data[index1]]
            }
            offer(val){
                this.data.push(val)
                this.size()>1 && this.bubbleUp(this.size()-1)
            }
            bubbleUp(index){
                while(index>0){//循环替代递归
                    let parentIndex = (index-1)>>1
                    if(this.comparator(this.data[index],this.data[parentIndex])<0){
                        this.swap(index,parentIndex)
                        index = parentIndex
                    }else{
                        break
                    }
                }
            }
            peek(){
                return this.data[0]
            }
            poll(){//shift()
                if(this.size() ==0) return
                let res = this.data[0]
                let last = this.data.pop()
                if(this.size()!=0){
                    this.data[0] = last//替换替代删除
                    this.bubbleDown(0)
                }
                return res
            }
            bubbleDown(index){
                let lastIndex = this.size()-1
                while(true){//循环替代递归
                    let leftIndex  = index*2+1
                    let rightIndex = index*2+2
                    let findIndex = index
                    if(leftIndex<= lastIndex &&
                    (this.comparator(this.data[leftIndex],this.data[findIndex])<0)){
                        findIndex = leftIndex
                    }
                    if(rightIndex<= lastIndex &&
                    (this.comparator(this.data[rightIndex],this.data[findIndex])<0)){
                        findIndex = rightIndex
                    }
                    if(findIndex!=index){
                        this.swap(index,findIndex)
                        index = findIndex
                    }else{
                        break
                    }
                }
            }
        }
        var findKthLargest = function(nums, k) {
            let minHeap = new MinHeap()
            for(let x of nums){
                if(minHeap.size()<k){
                    minHeap.offer(x)
                }else if(minHeap.peek() <x){
                    minHeap.poll()
                    minHeap.offer(x)
                }
            }
            return minHeap.peek()
        };

6. KMP算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
JS实现KMP算法  字符串匹配 应用:关键词搜索
        部分匹配表实现如下: next[i]
        function kmpGetStrPartMatchValue(str) {
            var prefix = [];
            var suffix = [];
            var partMatch = [];
            for(var i=0,j=str.length;i<j;i++){
                var newStr = str.substring(0,i+1);
                if(newStr.length == 1){
                    partMatch[i] = 0;
                } else {
                    for(var k=0;k<i;k++){
                        prefix[k] = newStr.slice(0,k+1);
                        suffix[k] = newStr.slice(-k-1);
                        if(prefix[k] == suffix[k]){
                            partMatch[i] = prefix[k].length;
                        }
                    }
                    if(!partMatch[i]){
                        partMatch[i] = 0;
                    }
                }
            }
            prefix.length = 0;
            suffix.length = 0;
            return partMatch;
        }
        回退算法
        function KMP(sourceStr,targetStr){
            var partMatchValue = kmpGetStrPartMatchValue(targetStr);
            var result = false;
            for(var i=0,j=sourceStr.length;i<j;i++){
                for(var m=0,n=targetStr.length;m<n;m++){
                    if(str.charAt(m) == sourceStr.charAt(i)){
                        if(m == targetStr.length-1){
                            result = true;
                            break;
                        } else {
                            i++;
                        }
                    } else {
                        if(m>0 && partMatchValue[m-1] > 0){
                            m = partMatchValue[m-1]-1;
                        } else {
                            break;
                        }
                    }
                }
                if(result){
                    break;
                }
            }
            return result;
        }

7. 封装一个优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
function PriorityQueue() {
        this.items = [];
        // 创建一个内部类,用于存放元素的内容和优先级
        function QueueElement(element, priority) {
            this.element = element;
            this.priority = priority;
        }
        // 插入方法
        PriorityQueue.prototype.entryQueue = function (ele, pri) {
            let element = new QueueElement(ele, pri);
            if (!this.items.length) {
                return this.items.push(element)
            }
            let isAdd = false;  // 用于判断是否在优先级比较当中插入了
            for (let i = 0; i < this.items.length; i++) {
                if (element.priority < this.items[i].priority) {
                    this.items.splice(i, 0, element);
                    isAdd = true;
                    break
                }
            }
            if (!isAdd) {
                return this.items.push(element)
            }
        }
        // 数据出队列
        PriorityQueue.prototype.outQueue = function () {
            return this.items.shift()
        }
        // 查看队列的第一个数据信息
        PriorityQueue.prototype.front = function () {
            return this.items[0]
        }
        // 判断队列是否为空
        PriorityQueue.prototype.isEmpty = function () {
            return this.items.length == 0
        }
        // 队列的长度
        PriorityQueue.prototype.size = function () {
            return this.items.length
        }
        // toString
        PriorityQueue.prototype.toString = function () {
            let str = '';
            for (let i = 0; i < this.items.length; i++) {
                str += this.items[i].element + '-' + this.items[i].priority + ' '
            }
            return str
        }
    }

    let pq = new PriorityQueue();
    pq.entryQueue('一般顾客', 1000)
    pq.entryQueue('二级顾客', 500)
    pq.entryQueue('vip顾客', 100)
    pq.entryQueue('svip顾客', 10)
    console.log(pq);
    console.log(pq.toString()); // svip顾客-10 vip顾客-100 二级顾客-500 一般顾客-1000
赏

Thanks

支付宝
微信

扫一扫，分享到微信

微信分享二维码
-->
-->

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很快啊~'<br><br>'敬请期待