web前端

基于js的数据结构总结

2018-01-24  本文已影响28人  刘相玉

11.filter:对数组中的每一项运行给定函数,则返回函数为true项组成的数组
12.sort:按照字母顺序对数组排序，支持传入指定排序方法的函数作为参数(当做字符串比较)
13.toString:将数组当做字符串返回
14.valueOf:将数组当做字符串返回
15.reduce:迭代累加

 <script>
  var arr=[3,6,9,10];
  var res=arr.reduce(function (pre,curr,index) {
    return pre+curr;
  })
  console.log(res);

</script>

5.链表
数组是链表的一种，但是数组的缺点是大小固定，从数组中插入或删除一个元素代价较高
链表的元素在内存中并不是连续的，每一个链表元素都有节点本身和指针组成（链表查找元素要从头开始）

     <script>
       function Linkedlist() {
        var Node=function (element) {//要添加的项
      this.element=element;
      this.next=null;
  }
     var length=0;
       var head=null;
       this.append=function (element) {
//             向列表中添加元素
       var node=new Node(element),
         current;
       if(head==null){
           head=node;//列表最后一个节点的下一个元素为null
       }else{
           current=head;
   //               循环列表知道找到最后一项
           while(current.next){
               current=current.next;
           }
    //               找到最后一项，将其next赋值为node,建立连接
           current.next=node;
       }
       length++;
   };
   this.insert=function (position,element) {};
   this.removeAt=function (position) {
    //           检查是否越界
       if()
   };
   this.move=function (element) {};
   this.indexOf=function (element) {};
   this.isEmpty=function (element) {
    this.size=function () {};
    this.toString=function () {};
    this.print=function () {}
   }
}
     </script>

节点有深度，节点的深度取决于祖先节点的数量
树的高度取决于所有节点深度的最大值

二叉树和二叉搜索树
二叉树的节点最多只有两个子节点，一个是左侧子节点，另一有右侧子节点

二叉搜索树：
左侧存储的节点比父节点小的值
右侧存储比父节点大或者相等的值

边：表示的是节点之间的关系
在双向链表中，每个节点有两个指针，一个指向下一个节点，一个指向上一个节点
同样在树中，每个节点也有两个指针，一个指向左侧子节点，一个指向右侧子节点
树中的方法：
insert(key):向树中插入新的键
search(key):在树中查找一个键，如果存在则返回true,否则返回false
inOrderTraverse():通过中序遍历的方式遍历所有的节点
PreOrderTraverse():通过先序遍历的方式遍历所有的节点
postOrderTraverse():通过后序的方式遍历所有的节点。
min():返回树中最小的键
max()；返回树中最大的键
remove(key):从树中删除某个键

  <script>
        function BinarySearchTree() {
    var Node=function (key) {//表示树的每一个节点
        this.key=key;
        this.left=null;
        this.right=null;

    };
    //        var root=null;
    var insertNode=function (node,newNode) {//实现插入节点的位置
        if(newNode.key<node.key){
            if(node.left==null){
                node.left=newNode;
            }else{
                insertNode(node.left,newNode);
            }
        }else{
            if(node.right==null){
                node.right=newNode;
            }else{
                insertNode(node.right,newNode);
            }
        }
    };
    var inOrderTraverseNode=function (node,callback) {
        if(node!==null){
            inOrderTraverseNode(node.left,callback);
            callback(node.key);
            inOrderTraverseNode(node.right,callback);//中序遍历从大到小的顺序排列的
        }
    };
    var preOrderTraverseNode=function (node,callback) {
        if(node!==null){
            callback(node.key);
            preOrderTraverseNode(node.left,callback);
            preOrderTraverseNode(node.right,callback);//优先于后代排列的方式
        }
    };
    var postOrderTraverseNode=function (node,callback) {
        if(node!==null){
            callback(node.key);
            postOrderTraverseNode(node.left,callback);
            postOrderTraverseNode(node.right,callback);
            callback(node.key);
        }
    };
      this.insert=function (key) {
          var newNode=new Node(key);//创建节点
          if(root==null){//判断是否特殊情况的第一个节点
              root=newNode;
          }else{
              insertNode(root,newNode);//把节点加入非根节点的位置
          }
      }
      this.inOrderTraverse=function (callback) {
          inOrderTraverseNode(root,callback);
      };
    this.preOrderTraverse=function (callback) {
        preOrderTraverseNode(root,callback);
    }
    this.postOrderTraverse=function (callback) {
        postOrderTraverseNode(root,callback);
    }
}
   </script>

有向图和无向图
强连通：如果图中的每个顶点都是双向连通的
1用邻接矩阵表示常见的图（arr[i][j]==1相邻 arr[i][j]==0不相邻）
2.使用邻接表表示图
3.使用关联矩阵表示图（边数比顶点多的情况）
图的遍历:可以寻找特定顶点或者寻找两个顶点之间的路径（思想：必须每个第一次访问的顶点）
1.广度优先（BFS） （队列）（先宽后深访问形式）
2.深度优先 (DFS) （栈） （先深度后广度的形式）
两种方法的不同点在于带访问顶点的数据结构不同

上一篇 下一篇

猜你喜欢

热点阅读