javascript实现数据结构算法

深藏阁楼爱情的钟 2023-06-08 04:46 12阅读 0赞

###### 1.排序 ######

###### 2.全排列 ######

###### 3.栈 ######

class stack{ 
     constructor(){ 
       this.stack=[];
     }
     push(item){ 
     return this.stack.push(item)
     }
     pop(){ 
       return this.stack.pop();
     }
     getCount(){ 
       return this.stack.length;
     }
     isEmpty(){ 
       return this.stack.length===0;
     }
    }

###### 4.二叉树 ######

class Node { 
           constructor(value, left, right) { 
             this.value = value;
             this.left = left;
             this.right = right;
           }
         }
         class Btree { 
           constructor() { 
             this.list = [];
           }
           addRoot(node) { 
             if (node !== null) this.list.push(node);
           }
           addRight(pnode, node) { 
             this.list.push(node);
             pnode.right = node;
           }
           addLeft(pnode, node) { 
             this.list.push(node);
             pnode.left = node;
           }
           getNode(index) { 
             return this.list[index];
           }
           getNodeList() { 
             return this.list;
           }
         }
         var bTree = new Btree();
         bTree.addRoot(new Node(1, null, null));
         bTree.addRight(bTree.getNode(0), new Node(2, null, null));
         bTree.addLeft(bTree.getNode(0), new Node(3, null, null));
         console.log(bTree);

###### 5.链表 ######

数组与链表的优缺点比较：[https://blog.csdn.net/weibo1230123/article/details/82011889][https_blog.csdn.net_weibo1230123_article_details_82011889]  
单链表：[https://segmentfault.com/a/1190000017000988][https_segmentfault.com_a_1190000017000988]  
双向链表：[https://www.cnblogs.com/baiyangyuanzi/p/6689531.html][https_www.cnblogs.com_baiyangyuanzi_p_6689531.html]  
单循环链表：[https://www.cnblogs.com/baiyangyuanzi/p/6689531.html][https_www.cnblogs.com_baiyangyuanzi_p_6689531.html]  
双向循环链表：[https://www.cnblogs.com/zhuwq585/p/6075117.html][https_www.cnblogs.com_zhuwq585_p_6075117.html]

//单链表
      class Node { 
            constructor(value) { 
              this.value = value;
              this.next = null;
            }
          }
          class LinkNode { 
            constructor() { 
              this.length = 0;
    
              this.head = null;
            }
            //在末尾添加节点
            append(value) { 
              var node = new Node(value);
              var current;
              var previous;
              if (this.head === null) this.head = node;
              else { 
                current = this.head;
                while (current.next) { 
                  //找到末尾current.next=null的值 然后插入进去 就在末尾添加了
                  current = current.next;
                }
                current.next = node;
              }
              this.length++;
            }
            //在指定的位置添加节点
            insert(position, value) { 
              if (position >= 0 && position <= this.length) { 
                var node = new Node(value);
                var current = this.head;
                var previous;
                if (position === 0) { 
                  node.next = this.head;
                  this.head = node;
                } else { 
                  for (var i = 0; i < position; i++) { 
                    previous = current;
                    current = current.next;
                  }
                  previous.next = node;
                  node.next = current;
                }
                this.length++;
                return true;
              } else return false;
            }
            //删除指定数据节点
            removed(element) { 
              if (this.head != null) { 
                let node = new Node(element);
                let pervious;
                let nextNode;
                let current = this.head;
                while (current != node) { 
                  pervious = current;
                  current = current.next;
                  nextNode = current.next;
                }
    
                pervious.next = nextNode;
                this.length--;
                return true;
              } else { 
                return false;
              }
            }
    
            //删除指定位置节点
            removeAt(position) { 
              if (position >= 0 && position <= this.length) { 
                var current = this.head;
                var previous, nextNode;
                for (var i = 0; i < position; i++) { 
                  previous = current;
                  current = current.next;
                  nextNode = current.next;
                }
                previous.next = nextNode;
                this.length--;
                return true;
              } else { 
                return false;
              }
            }
    
            //查询节点的位置
            searchAt(value) { 
              if (this.head != null) { 
                let node = new Node(value);
                let current;
                let index = 0;
                if (this.head == node) { 
                  return 0;
                } else { 
                  current = this.head;
                  while (current != node) { 
                    current = current.next;
                    index++;
                  }
                  return index;
                }
              } else { 
                return -1;
              }
            }
            //根据位置查节点
            searchValue(position) { 
              var current = this.head;
              var previous, nextNode;
              var val;
              for (var i = 0; i < position; i++) { 
                current = current.next;
              }
              val = current.value;
              return val;
            }
          }
    
          var link = new LinkNode();
          link.append(5);
          link.append(4);
          link.append(3);
          link.append(2);
          link.insert(0, 1);
          // console.log(link.insert(1, 2));
          // console.log(link.insert(1, 3));
          // console.log(link.insert(1, 4));
          // console.log(link);
          // console.log(link.removeAt(1));
          // console.log(link);
          // console.log(link.removeAt(3));
          console.log(link);
          console.log(link.searchValue(1));

###### 队列 ######

//顺序存储队列 队列：先进先出
          class Queue { 
            constructor() { 
              this.queue = [];
            }
            push(value) { 
              this.queue.push(value);
              return true;
            }
            pop() { 
              return this.queue.shift();
            }
            getCount() { 
              return this.queue.length;
            }
            getQueue() { 
              return this.queue;
            }
          }
          var queue = new Queue();
          queue.push(1);
          queue.push(2);
          queue.push(3);
          queue.push(4);
          queue.push(5);
          console.log(queue.getCount());
          console.log(queue.getQueue());
          console.log(queue.pop());

###### 字典，散列表 ######

[https://www.cnblogs.com/jaxu/p/11302315.html][https_www.cnblogs.com_jaxu_p_11302315.html]

[https_blog.csdn.net_weibo1230123_article_details_82011889]: https://blog.csdn.net/weibo1230123/article/details/82011889
[https_segmentfault.com_a_1190000017000988]: https://segmentfault.com/a/1190000017000988
[https_www.cnblogs.com_baiyangyuanzi_p_6689531.html]: https://www.cnblogs.com/baiyangyuanzi/p/6689531.html
[https_www.cnblogs.com_zhuwq585_p_6075117.html]: https://www.cnblogs.com/zhuwq585/p/6075117.html
[https_www.cnblogs.com_jaxu_p_11302315.html]: https://www.cnblogs.com/jaxu/p/11302315.html