javascript算法描述

[RainZhai]

列表:

function List(){
  this.listSize = 0;
  this.pos = 0;
  this.dataStore = [];
  this.clear = clear;
  this.find = find;
  this.toString = toString;
  this.insert = insert;
  this.append = append;
  this.remove = remove; 
  this.front = front;
  this.end = end;
  this.prev = prev;
  this.next = next;
  this.length = next;
  this.currPos = currPos;
  this.moveTo = moveTo;
  this.getElement = getElement;
  this.contains =  contains;
}

function append(element){
  this.dataStore[this.listSize++] = element;
}

function find(element){
  for(var i = 0;i<this.dataStore.length;++i){
    if(this.dataStore[i] == element){
      return i;
    }
  }
  return -1;
}

function remove(element){
  var foundAt = this.find(element);
  if(fonndAt>-1){
    this.dataStore.splice(foundAt,1);
    --this.listSize;
    return true;
  }
  return false;
}

function length(){
  return this.listSize;
}

function toString(){
  return this.dataStore;
}

function insert(element, after){
  var insertPos = this.find(after);
  if(insertPos>-1){
    this.dataStore.splice(insertPos+1,0,element);
  }
}

function clear(){
  delete this.dataStore;
  this.dataStore = [];
  this.listSize = this.pos = 0;
}

function contains(){
  for(var i = 0;i<this.dataStore.length; ++i){
    if(this.dataStore[i]==element){
      return true;
    }
  }
  return false;
}

function front(){
  this.pos = 0;
}

function end(){
  this.pos = this.listSize-1;
}

function prev(){
  if(this.pos>0){
    --this.pos; 
  }
}

function next(){
  if(this.pos<this.listSize-1){
    ++this.pos; 
  }
}

function currPos(){
  return this.pos;
}

function moveTo(pos){
 this.pos = pos;
}

function getElement(){
  return this.dataStore[this.pos];
}

遍历方式 for(names.front();names.currPos()<names.length;names.next()){ console.log(names.getElement()); }

[RainZhai]

//栈 function Stack() { this.dataStore = []; this.top = 0; this.push = push; this.pop = pop; this.peek = peek; this.clear = clear; this.length = length; }

function push(e) { this.dataStore[this.top++] = e; }

function peek() { return this.dataStore[this.top - 1]; }

function pop() { return this.dataStore[--this.top]; }

function clear() { return this.top = 0; }

function length() { return this.top; }

var s = new Stack(); s.push("dav"); s.push("ff"); s.push("rr"); console.log("length:"+s.length()) console.log(s.peek()); var poped = s.pop(); console.log("poped elemnts is:"+ poped) console.log(s.peek()); s.push("xx"); console.log(s.peek()); s.clear(); console.log("length:"+s.length()) console.log(s.peek()); s.push("cff"); console.log(s.peek());

[RainZhai]

//队列 function Queue() { this.dataStore = []; this.enqueue = enqueue; this.dequeue = dequeue; this.front = front; this.back = back this.toString = toString; this.empty = empty; }

function enqueue(e) { this .dataStore .push(e); }

function dequeue() { this .dataStore .shift(); }

function front() { return this.dataStore[0]; }

function back() { return this.dataStore[this.dataStore.length - 1]; }

function toString() { var retStr = ""; for (var i = 0; i < this.dataStore.length; ++i) { retStr += this.dataStore[i] + "\n"; } return retStr; }

function empty() { if (this.dataStore.length == 0) { return true; } else { return false; } }

var q = new Queue(); q.enqueue("jj") q.enqueue("gg") q.enqueue("rr") console.log(q.toString()); q.dequeue(); console.log(q.toString()); console.log("front: "+q.front()); console.log("back: "+q.back());

[RainZhai]

链表

function Node(e){
  this.element = e;
  this.next = null;
}

function LList(){
 this.head = new Node("head");
 this.find = find;
 this.insert = insert;
 this.display = display;
 this.findPrevious = findPrevious;
 this.remove = remove;
}

function remove(item){
  var prevNode = this.findPrevious(item);
  if(!(prevNode.next==null)){
    prevNode.next = prevNode.next.next;
  }
}

function findPrevious(item){
  var currNode = this.head;
  while(currNode.next!=null && currNode.next.element!=item){
    currNode = currNode.next;
  }
  return currNode;
}

function find(item){
  var currNode = this.head;
  while(currNode.element!=item){
    currNode = currNode.next;
  }
  return currNode;
}

function insert(newEle, item){
  var newNode = new Node(newEle);
  var current = this.find(item);
  newNode.next = current.next;
  current.next = newNode;
}

function display(){
  var currNode = this.head;
  while(!(currNode.next==null)){
    console.log(currNode.next.element);
    currNode = currNode.next;
  }
}

var cities = new LList();
cities.insert("a","head");
cities.insert("b","a");
cities.insert("c","b");
cities.display();
cities.remove("b");
cities.display();

[RainZhai]

//双向链表

function Node(e) { this.element = e; this.next = null; this.previous = null; }

function LList() { this.head = new Node("head"); this.find = find; this.insert = insert; this.display = display; this.findLast = findLast; this.dispReverse = dispReverse; this.remove = remove; }

function dispReverse() { var currNode = this.head; currNode = this.findLast(); while (currNode.previous != null) { console.log(currNode.element); currNode = currNode.previous; } }

function findLast() { var currNode = this.head; while (currNode.next != null) { currNode = currNode.next; } return currNode; }

function remove(item) { var currNode = this.find(item); if (!(currNode.next == null)) { currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } } / function findPrevious(item){ var currNode = this.head; while(currNode.next!=null && currNode.next.element!=item){ currNode = currNode.next; } return currNode; } /

function find(item) { var currNode = this.head; while (currNode.element != item) { currNode = currNode.next; } return currNode; }

function insert(newEle, item) { var newNode = new Node(newEle); var current = this.find(item); newNode.next = current.next; newNode.previous = current; current.next = newNode; }

function display() { var currNode = this.head; while (!(currNode.next == null)) { console.log(currNode.next.element); currNode = currNode.next; } }

var cities = new LList(); cities.insert("a", "head"); cities.insert("b", "a"); cities.insert("c", "b"); cities.display(); cities.remove("b"); cities.display(); cities.dispReverse();

/ //单向循环链表： function LList() { this.head = new Node("head"); this.head.next = this.head; this.find = find; this.insert = insert; this.display = display; this.findPrevious = findPrevious; } //循环会死循环，while循环需修改，检测头节点，到头节点退去循环 function display() { var currNode = this.head; while (!(currNode.next == null) && currNode.next.element != "head") { console.log(currNode.next.element); currNode = currNode.next; } } /

[RainZhai]

//字典 function Dictionary() { this.add = add; this.datastore = new Array(); this.find = find; this.remove = remove; this.showAll = showAll; this.count = count; this.clear = clear; }

function add(key, value) { this.datastore[key] = value; }

function find(key) { return this.datastore[key]; }

function remove(key) { delete this.datastore[key]; }

function showAll() { for (var key in Object.keys(this.datastore)) { console.log(key + "->" + this.datastore[key]) } }

function count() { var n = 0; for (var key in Object.keys(this.datastore)) { ++n; } return n; }

function clear() { var n = 0; for (var key in Object.keys(this.datastore)) { delete this.datastore[key]; } }

var book = new Dictionary(); book.add("aa", "123"); book.add("bb", "222"); book.add("cc", "444"); console.log(book.count()); console.log(book.find("bb")); book.showAll(); book.clear(); console.log(book.count()); // 添加排序功能 //function showAll(){ for(var key in // Object.keys(this.datastore).sort()){ // console.log(key+"->"+this.datasore[key]) } }

[RainZhai]

散列

function HashTable(){
  this.table = new Array(137);
  this.simpleHash = simpleHash;
  this.betterHash ＝ betterHash;
  this.showDistro = showDistro;
  this.put = put;
}

function put(data){
  //var pos = this.simleHash(data);
  var pos = this.betterHash(data);
  this.table[pos] = data;
}

function get(key){
  return this.table[this.betterHash(key)]
}

function simpleHash(data){
  var total = 0;
  for(var i = 0; i<data.length; ++i){
    total += data.charCodeAt(i);
  }
  console.log("hash value:"+data+"->"+total);
  return total % this.table.length;
}

function showDistro(){
  var n =0;
  for(var i=0; i<this.table.length; ++i){
    if(this.table[i]!=undefined){
      console.log(i+":"+this.table[i])
    }
  }
}

var names = ["sss","rrrr","ytee"];
var htable= new HashTable();
for(var i=0; i<names.length;++i){
  htable.put(names[i]);
}
htable.showDistro();

//更好的散列表
function betterHash(str, arr){
  cost H = 37;
  var total = 0;
  for(var i = 0; i<str.length; ++i){
    total += H* total +data.charCodeAt(i);
  }
  total = total % arr.length;
  console.log("hash value:"+str+"->"+total);
  return parseInt(total);
}

碰撞处理 开链法 function buildChains(){ for(var i =0; i<this.table.length; ++i){ this.table[i] = new Array(); } }

var names = ["sss","rrrr","ytee"]; var htable= new HashTable(); htable.buildChains(); for(var i=0; i<names.length;++i){ htable.put(names[i]); } htable.showDistro();

function put(key, data){ var pos = this.betterHash(key); var index = 0; if(this.table[pos][index] ==undefined){ this.table[pos][index+1] = data; } ++index; else{ while(this.table[pos][index] !=undefined){ ++index; } this.table[pos][index+1] = data; } }

function get(key){ var index = 0; var hash = this.betterHash(key); if(this.table[pos][index] ==key){ return this.table[pos][index+1]; } index+=2; else{ while(this.table[pos][index] !=key){ index+=2; } return this.table[pos][index+1]; } return undefined; }

线性探测法 构造函数加入： this.values = []; function put(key, data){ var pos = this.betterHash(key); if(this.table[pos]==undefined){ this.table[pos]= key; this.values[pos]= data; } else{ while(this.table[pos] !=undefined){ pos++; } this.table[pos]= key; this.values[pos]= data; } }

function get(key){ var hash = -1; hash = this.betterHash(key); if(hash>-1){ for(var i = hash; this.table[hash]!=undefined; i++){ if(this.table[hash]==key){ return this.values[hash]; } } } return undefined; }