javascript算法描述2

[RainZhai]

集合 set类实现

function Set(){
  this.dataStore = [];
  this.add = add;
  this.remove = remove;
  this.size = size;
  this.union = union;
  this.intersect = intersect;
  this.subset = subset;
  this.difference = defference;
  this.show = show;
}

function add(data){
  if(this.dataStore.indexOf(data)<0){
    this.dataStore.push(data);
    return true;
  }else{
    return false;
  }
}

function remove(data){
  var pos = this.dataStore.indexOf(data);
  if(pos>-1){
    this.dataStore.slice(pos,1);
    return true;
  }else{
    return false;
  }
}

function show(){
  return this.dataStore;
}

function contains(data){
  if(this.dataStore.indexOf(data)>-1){
    return true;
  }else{
    return false;
  }
}

function union(set){
  var tempSet = new Set();
  for(var i=0; i<this.dataStore.length; ++i){
    tempSet.add(this.dataStore[i]);
  }
  for(var i=0; i<set.dataStore.length; ++i){
    if(!tempSet.contains(set.dataStore[i]))
    tempSet.dataStore.push(set.dataStore[i]);
  }
  return tempSet;
}

function intersect(set){
  var tempSet = new Set();
  for(var i=0; i<this.dataStore.length; ++i){
    if(set.contains(this.dataStore[i]))
    tempSet.add(this.dataStore[i]);
  }
  return tempSet;
}

function subset(set){
  if(this.size()>set.size()){
    return false;
  }else{
    for each(var member in this.dataStore){
      if(!set.contains(member)){
        return false;
      }
    }
  }
  return true;
}

function size(){
  return this.dataStore.length;
}

function difference(set){
  var tempSet = new Set();
  for(var i=0; i<this.dataStore.length; ++i){
    if(!set.contains(this.dataStore[i])){
      tempSet.add(this.dataStore[i])
    }
  }
  return tempSet;
}

[RainZhai]

二叉树

function Node(data, left, right){
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}

function show(){
  return this.data;
}

function BST(){
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder;
}

function insert(data){
  var n = new Node(data, null, null);
  if(this.root == null){
    this.root = n;
  }else{
    var current = this.root;
    var parent;
    while(true){
      parent = current;
      if(data<current.data){
        current = current.left;
        if(current == null){
          parent.left = n;
          break;
        }
      }else{
        current = current.right;
        if(current == null){
          parent.right = n;
          break;
        }
      }
    }
  }
}

//中序遍历
function inOrder(node){
  if(!(node==null)){
    inOrder(node.left);
    putstr(node.show + "    ")
    inOrder(node.right);
  }
}

//先序遍历
function preOrder(node){
  if(!(node==null)){
    putstr(node.show + "    ")
    preOrder(node.left);
    preOrder(node.right);
  }
}

//后序遍历
function postOrder(node){
  if(!(node==null)){
    postOrder(node.left);
    postOrder(node.right);
    putstr(node.show + "    ")
  }
}

[RainZhai]

在二叉树上查找

//查找最小值
function getMin(){
  var current = this.root;
  while(current.left!=null){
    current = current.left;
  }
  return current.data;
}
//查找最大值
function getMax(){
  var current = this.root;
  while(current.right!=null){
    current = current.right;
  }
  return current.data;
}
//查找给定值
function find(data){
  var current = this.root;
  while(current!=null){
    if(current.data == data){
      return current;
    }else if(data<current.data){
      current = current.left;
    }else{
      current = current.right;
    }
  }
  return null;
}

二叉树上删除节点

function remove(data){
  root = removeNode(this.root, data);
}

function removeNode(node, data){
  if(node == null){
    return null;
  }
  if(data==node.data){
    if(node.left == null && node.right == null){
      return null;
    }
    if(node.left == null){
      return node.right;
    }
    if(node.right == null){
      return node.left;
    }
    var tempNode = getSmallest(node.right);
    node.data = tempNode.data;
    node.right = removeNode(node.right, tempNode.data);
    return node;
  }else if(data < node.data){
    node.left = removeNode(node.left,data);
    return node;
  }else {
    node.right = removeNode(node.right, data);
    return node;
  }
}

[RainZhai]

图

//顶点
function Vertex(label){
  this.label = label;
}
//边
//adj[]数组
//图
function Graph(v){
  this.vertices = v;
  this.edges = 0;
  this.adj = [];
  for(var i =0; i<this.vertices; ++i){
    this.adj[i] = [];
    this.adj[i].push("");
  }
  this.addEdge = addEdge;
  this.toString = toString;
}

function addEdge(v, w){
  this.ajd[v].push(w)
  this.adj[w].push(v)
  this.edges++;
}

function showGraph(){
  for(var i=0; i<this.vertices; ++i){
    console.log(i+"->");
    for(var j=0; j<this.vertices; ++j){
      if(this.adj[i][j] != undefined){
        console.log(this.adj[i][j] +" ");
      }
    }
  }
}

深度优先搜索

this.marked = [];
for(var i=0; i<this.vertices; ++i){
  this.marked[i] = false;
}

function dfs(v){
  this.marked[v] = true;
  if(this.adj[v]!=undefined){
    console.log("visited vertex:  "+v);
  for(varw in this.adj[v]){
    if(!this.marked[w]){
      this.dfs(w);
    }
  }
}
}

g = new Graph(5);
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,3)
g.addEdge(2,4)
g.showGraph();
g.dfs(0);

广度优先搜索

functionj bfs(s){
  var queue = [];
  this.marked[s] = true;
  queue.push(s);
  while(queue.length > 0){
    var v = queue.shift();
    if(v==undefined){
      console.log("visited vertex:  "+v);
    }
    for(var w in this.adj[v]){
      if(!this.marked[w]){
        this.edgeTo[w] = v;
        this.marked[w] = true;
        queue.push(w);
      }
    }
  }
}

g = new Graph(5);
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,3)
g.addEdge(2,4)
g.showGraph();
g.bfs(0);

[RainZhai]

查找最短路径

this.edgeTo = []; 添加到graph类
function pathTo(v){
  var source = 0;
  if(!this.hasPathTo(v)){
    return undefined;
  }
  var path = [];
  for(var i = v; i!=source; i= this.edgeTo[i]){
    path.push(i);
  }
  path.push(s);
  return path;
}

function hashPathTo(v){
  return this.marked[v]
}

g = new Graph(5);
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,3)
g.addEdge(2,4)
var vertex = 4;
while(paths.length>0){
  if(paths.length>1){
    log(paths.pop() + "-")
  }else{
    log(paths.pop())
  }
}

拓扑排序算法

function topSort(){
  var stack = [];
  var visited = [];
  for(var i=0; i<this.vertices; i++){
    visited[i] = false;
  }
  for(var i=0; i<this.vertices; i++){
    if(visited[i] == false){
      this.topSortHelper(i,visited, stack)
    }
  }
  for(var i=0; i<stack.length; i++){
    if(stack[i] != undefined && stack[i] != false){
      log(this.vertexList[stack[i]]);
    }
  }
}

function topSortHelper(v, visited, stack){
  visited[v] = true;
  for(var w in this.adj[v]){
    if(!visited[w]){
      this.topSortHelper(visited[w],visited, stack)
    }
  }
  stack.push(v);
}

[RainZhai]

排序算法

//冒泡排序
function bubbleSort(){
  var numElements = this.dataStore.length;
  var temp;
  for(var outer = numElements; outer>=2; --outer){
    for(var inner = 0; inner<=outer-1; ++inner){
      if(this.dataStore[inner] > this.dataStore[inner+1]){
        swap(this.dataStore, inner, inner+1)
      }
    }
    console.log(this.toString());
  }
}

//选择排序
function selectionSort(){
  var min, temp;
  for(var outer = 0; outer <= this.dataStore.length-2; ++outer){
    min = outer;
    for(var inner = outer +1; inner <=this.dataStore.length -1; ++inner){
      if(this.dataStore[inner] < this.dataStore[min]){
        min = inner;
      }
      swap(this.dataStore, outer, min)
    }
  }
}

//插入排序
function insertionSort(){
  var temp, inner;
  for(var outer = 1; outer <= this.dataStore.length-1; ++outer){
    temp = this.dataStore[outer];
    inner = outer
    while(inner>0 && (this.dataStore[inner - 1] >= temp )){
      this.dataStore[inner] = this.dataStore[inner - 1];
      --inner;
    }
    this.dataStore[inner] = temp;
  }
}

[RainZhai]

//希尔排序

function shellsort(){
  for(var g=0; g < this.gaps.length; ++g){
    for(var i = this.gaps[g]; i< this.dataStore.length; ++i){
      var temp = this.dataStore[i];
      for(var j=i; j>=this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]){
        this.dataStore[j] = this.dataStore[j - this.gaps[g]];
      }
      this.dataStore[j] = temp;
    }
  }
}

//动态间隔希尔排序

function shellsort1(){
  var N = this.dataStore.length;
  var h =1;
  while(h< n/3){
    h = 3*h+1;
  }
  while(h>=1){
    for(var i=h; i<N; i++){
      for(var j=i;i>=h&& this.dataStore[j] < this.dataStore[j-h];j-=h){
        swap(this.dataStore,j,j-h);
      }
    }
    h = (h-1)/3;
  }
}

var nums = new CArray(100);
nums.setData();
console.log(nums.toString());
nums.shellsort1();
console.log(nums.toString());