数据结构与算法JavaScript描述.
队列: 先进先出,尾添加,头删除.
<script type="text/javascript">
//队列,先进先出,尾添加,头删除.
function Queue() {
//
var _enqueue = function(element) {
this.dataStore.push(element);
}
//
var _dequeue = function() {
return this.dataStore.shift();
}
//
var _front = function() {
return this.dataStore[0];
}
//
var _back = function() {
return this.dataStore[this.dataStore.length - 1]
}
//
var _toString = function() {
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
}
//
var _empty = function() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
//
this.dataStore = [];
//
this.enqueue = _enqueue;
this.dequeue = _dequeue;
this.front = _front;
this.back = _back;
this.toString = _toString;
this.empty = _empty;
}
//
var q= new Queue();
q.enqueue('yujj');
q.enqueue('Zzc');
q.enqueue('Fjb');
console.log(q);
q.dequeue();
console.log(q);
//
console.log(q.toString());
//
console.log(q.front());
console.log(q.back());
//
</script>链表
<script type="text/javascript">
//链表,
function Llist(){
//内存单元
var Node = function(element) {
this.element = element;
this.next = null;
}
//查找
var _find = function(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
//添加单元
var _insert = function(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
//
newNode.next = current.next;
current.next = newNode;
}
//
var _display = function() {
var currNode = this.head;
while (!(currNode.next == null)) {
currNode = currNode.next;
}
}
//
var _findPrevious = function(item) {
var currNode = this.head;
while (!(currNode.next == null) && (currNode.next.element !== item)) {
currNode = currNode.next;
}
return currNode;
}
//删除单元
var _remove = function(item) {
var prevNode = this.findPrevious(item);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
}
//
this.head = new Node("head");
this.find = _find;
this.insert = _insert;
this.remove = _remove;
this.display = _display;
this.findPrevious = _findPrevious;
}
//
var cities = new Llist();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Alma", "Russellville");
cities.insert("yuq", "Conway");
//
cities.display();
console.log(cities);
cities.remove('Conway');
console.log(cities);
</script>栈:后进先出
<script type="text/javascript">
//栈
function Stack()
{
//入栈
var _push = function(element){
_this.dataStore[_this.top++] = element;
}
//出栈
var _pop = function(){
delete _this.dataStore[_this.top-1];
_this.top--;
// return data;
}
//返回栈顶元素
var _peek = function(){
return _this.dataStore[_this.top-1]
}
//
var _clear = function()
{
_this.dataStore = [];
_this.top = 0;
}
//
var _length = function()
{
return _this.top;
}
//
this.dataStore = [];
this.top = 0;
//
this.push = _push;
this.pop = _pop;
this.peek = _peek;
this.length = _length;
this.clear = _clear;
//
var _this = this;
}
var s = new Stack();
s.push('Yuq');
s.push('Yujj');
//
console.log(s);
s.pop();
console.log(s);
s.push('Zhcl');
console.log(s.length());
console.log(s);
//
console.log(s.peek());
s.push('Fujb');
console.log(s);
console.log(s.clear());
console.log(s);
console.log(s.peek());
</script>散列：
<script type="text/javascript">
function HashTable() {
//
var _simpleHash = function(data) {
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i);
}
//
return total % this.table.length;
}
//
var _betterHash = function(string) {
const H = 37;
var total = 0;
//
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
//
total = total % this.table.length;
//
if (total < 0) {
total += this.table.lenght - 1;
}
//
return parseInt(total);
}
//
var _showDistro = function() {
var n = 0;
for (var i = 0; i < this.table.length; ++i) {
if (this.table[i] != undefined) {
console.log(this.table[i]);
}
}
}
//
var _put = function(data) {
// var pos=this.simpleHash(data);
var pos = this.betterHash(data);
console.log(pos);
this.table[pos] = data;
}
//
this.table = new Array(137);
this.simpleHash = _simpleHash;
this.showDistro = _showDistro;
this.betterHash = _betterHash;
this.put = _put;
//this.get = _get;
}
//
var someNames = ['David', 'Jennifer', 'Donnie', 'Raymond', 'Cynthia', 'Mike', 'Clayton', 'Danny', 'Jonathan'];
var htable = new HashTable();
//
for (var i = 0; i < someNames.length; ++i) {
htable.put(someNames[i]);
}
//
console.log(htable);
//
htable.showDistro();
</script>字典
<script type="text/javascript">
//字典,key=>val 键值对
function Dictionary()
{
var _add = function(key,val)
{
this.datastore[key] = val;
this.datastore.length++;
}
//
var _find = function(key)
{
return this.datastore[key];
}
//
var _remove = function(key)
{
delete this.datastore[key];
this.datastore.length--;
}
//
var _showAll = function()
{
for(var key in Object.keys(this.datastore))
{
console.log(this.datastore[key]);
}
}
//
var _count = function()
{
var n=0;
for(var key in Object.keys(this.datastore))
{
++n;
}
return n;
}
//
var _clear = function()
{
for(var key in this.datastore)
{
delete this.datastore[key];
}
this.datastore.length = 0;
}
//
this.add = _add;
this.datastore = new Array();
this.find = _find;
this.remove = _remove;
this.showAll = _showAll;
this.count = _count;
this.clear = _clear;
}
//
var pbook = new Dictionary();
pbook.add("raymond",'123');
pbook.add("David",'345');
pbook.add("Cynthia","456");
//
pbook.remove('Cynthia');
//
console.log(pbook);
console.log(pbook.count());
console.log(pbook.find('David'));
//pbook.clear();
//
console.log(pbook);
</script>双向链表
<script type="text/javascript">
//双向链表
function Llist(){
//内存单元
var Node = function(element) {
this.element = element;
this.next = null;
this.previous =null;
}
//查找
var _find = function(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
//添加单元
var _insert = function(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
//
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
}
//
var _display = function() {
var currNode = this.head;
while (!(currNode.next == null)) {
currNode = currNode.next;
}
}
//
var _findPrevious = function(item) {
var currNode = this.head;
while (!(currNode.next == null) && (currNode.next.element !== item)) {
currNode = currNode.next;
}
return currNode;
}
//删除单元
var _remove = function(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;
}
}
//
var _findLast = function()
{
var currNode = this.head;
while(!(currNode.next == null))
{
currNode = currNode.next;
}
return currNode;
}
//
var _dispReverse = function()
{
var currNode = this.head;
currNode = this.findLast();
while(!(currNode.previous ==null))
{
console.log(currNode.element);
currNode = currNode.previous;
}
}
//
this.head = new Node("head");
this.find = _find;
this.insert = _insert;
this.remove = _remove;
this.display = _display;
this.findPrevious = _findPrevious;
this.findLast = _findLast;
this.dispReverse = _dispReverse;
}
//
var cities = new Llist();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Alma", "Russellville");
cities.insert("yuq", "Conway");
//
cities.display();
console.log(cities);
cities.remove('Conway');
console.log(cities);
</script>列表
<script type="text/javascript">
//列表描述
function list()
{
//
var _clear = function(){
delete _this.dataStore;
_this.dataStore = [];
_this.listsSize = _this.pos = 0;
}
//查找
var _find =function(element){
for(var i=0; i<_this.listsSize; i++)
{
if(_this.dataStore[i] === element)
{
_this.pos = i;
return i;
break;
}
}
return -1;
}
//
var _toString =function(){
return _this.dataStore.toString();
}
//
var _insert =function(element,after){
var insertPos = _this.find(after);
if(insertPos > -1)
{
_this.dataStore.splice(insertPos+1,0,element);
++_this.listsSize;
return true;
}
return false;
}
var _append =function(element){
_this.dataStore[_this.listsSize++] = element;
_this.pos++;
}
var _remove =function(element){
var foundAt = _find(element);
if(foundAt>-1)
{
_this.dataStore.splice(foundAt,1);
--_this.listsSize;
return false;
}
}
var _front =function(){
_this.pos=0;
}
var _end =function(){
_this.pos = this.listsSize-1;
}
var _prev =function(){
if(_this.pos > 0)
{
--this.pos;
}
}
var _next =function(){
if(_this.pos < _this.listsSize-1)
{
++_this.pos;
}
}
var _currPos =function(){
return _this.pos;
}
var _moveTo =function(position){
_this.pos = position;
}
var _getElement =function(){
return _this.dataStore[_this.pos];
}
var _length =function(){
return _this.listsSize;
}
var _contains =function(element){
for(var i =0; i<_this.dataStore.length; ++i)
{
if(_this.dataStore[i] == element)
{
return true;
}
}
return false;
}
//属性
this.listsSize = 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.currPos = _currPos;//返回当前位置
this.moveTo = _moveTo; //当前位置移动到指定位置
this.getElement = _getElement; //返回当前位置的元素
this.length = _length; //返回列表中元素个数
this.contaics = _contains; //判断值是否在列表中
//
var _this = this;
}
//
var names = new list();
//
names.append("Zcl");
names.append("Yyj");
names.append("Yuq");
names.append("Wpq");
names.append("Fjb");
names.append("Chj");
//
names.front();
names.next();
console.log(names);
//
names.next();
names.next();
names.prev();
console.log(names);
//
console.log(names.find('Wpq'));
//
//names.clear();
console.log(names);
names.insert('Insert','Wpq');
console.log(names);
names.remove('Wpq');
console.log(names);
names.end();
console.log(names);
console.log(names.currPos());
console.log(names.length());
console.log(names.contaics('Insert'));
</script>二叉树,递归遍历：
<script type="text/javascript">
/**
* 二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。
* 这一特性使得查找的效率很高。
*/
// http://blog.csdn.net/sjf0115/article/details/8645991
//二叉树
function Tree() {
//节点
var Node = function(data,left,right)
{
var _show = function()
{
return this.data;
}
//
this.data = data;
this.left = left;
this.right = right;
this.show = _show;
}
//添加节点
var _insert = function(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;
}
}
}
}
}
/*
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
*/
//中序遍历
var _inOrder = function(node)
{
if(!(node == null))
{
_inOrder(node.left);
_this.showData += node.show()+',';
_inOrder(node.right);
}
}
//先序遍历
var _proOrder = function(node)
{
if(!(node == null))
{
_this.showData += node.show()+',';
_proOrder(node.left);
_proOrder(node.right);
}
}
//后序遍历
var _postOrder = function(node)
{
if(!(node == null))
{
_postOrder(node.left);
_postOrder(node.right);
_this.showData += node.show()+',';
}
}
//先序遍历(非递归)
var _proOrder2 = function(node)
{
//模拟栈
var arr = [];
//p是遍历指针
var p = node;
//栈不空或者p不空时循环
while( p!=null || arr.length !=0)
{
if(p != null)
{
//存入栈中
arr.push(p);
_this.showData += p.show()+',';
//遍历左子树
p = p.left;
}
else
{
p = arr.shift();
p = p.right;
}
}
}
//中序遍历(非递归)
var _inOrder2 = function(node)
{
//
if(node == null)
{
return;
}
//
var stack = []; //创建一个空栈
var node_pop; //用来保存出栈节点
var pCur = node; //定义指向当前访问的节点的指针
//
while(pCur!=null || stack.length!=0)
{
if(pCur && pCur.left != null)
{
// stack.push(pCur);
pCur = pCur.left;
console.log(pCur);
}
else
{
// pCur && console.log(pCur.data);
if(pCur)
{
pCur = pCur.right;
}
//
while( pCur == null && stack.length!=0)
{
pCur = stack['0'];
console.log(pCur.data);
// pop_stack(stack,&node_pop);
pCur = pCur.right;
}
pCur = null;
//
}
}
}
//后序遍历(非递归)
var _postOrder2 = function(node)
{
//
if(node == null)
{
return;
}
//栈节点结构
var snode = function(node,num)
{
this.p = node; //p二叉树节点结构,
this.rvisited = num ? 1 :0 ; //rvisited:1代表p所指向的节点的右节点已被访问过
}
//栈
var stack = [];
var p =node;
//
while( p!= null)
{
if(p != null)
{
var _node = new snode(p);
stack.push(_node);
}
p = p.left;
}
//
while(!stack.length == 0)
{
var sn = stack['0'];
//若其右孩子已经被访问过，或是该元素没有右孩子.
if(sn.p.right == null || sn.rvisited)
{
p = stack.shift();
// console.log(p.p.data);
_this.showData += p.p.show()+',';
}
//若它的右孩子存在且rvisited为0，说明以前还没有动过它的右孩子，于是就去处理一下其右孩子。
else
{
sn.rvisited = 1;
sn.p ? (p = sn.p.right) : p = null;
//
while(p != null)
{
var _node = new snode(p);
stack.push(_node);
p = p.left;
}
}
}
}
//分层遍历,(按层次从上往下,从左往右[从右往左])
var _layerOrder = function(node)
{
var arr = [];
arr.push(node);
while(arr.length)
{
var pNode = arr.pop();
_this.showData += pNode.show()+',';
//
if(pNode.right != null)
{
arr.push(pNode.right);
}
if(pNode.left != null)
{
arr.push(pNode.left);
}
}
}
//查找最小值
var _getMin = function()
{
var current = this.root;
while(!(current.left ==null))
{
current = current.left;
}
return current.data;
}
//查找最大值
var _getMax = function()
{
var current = this.root;
while(!(current.right ==null))
{
current = current.right;
}
return current.data;
}
//查找
var _find = function(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;
}
}
}
//删除
var _remove = function(data)
{
this.root = this.removeNode(this.root,data);
}
//删除节点
var _removeNode = function(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 = this.getSmallest(node.right);
//
node.data = tempNode.data;
node.right = this.removeNode(node.right,tempNode.data);
return node;
}
else if(data < node.data)
{
node.left = this.removeNode(node.left,data);
return node;
}
else
{
node.right = this.removeNode(node.right,data);
return node;
}
}
//查找左边最小节点
var _getSmallest = function(treeNode)
{
var current = treeNode;
while(!(current.left ==null))
{
current = current.left;
}
return current;
}
//
this.root = null;
//添加
this.insert = _insert;
//递归遍历
this.inOrder = _inOrder;
this.proOrder = _proOrder;
this.postOrder = _postOrder;
this.layerOrder =_layerOrder;
//非递归遍历
this.proOrder2 = _proOrder2;
this.postOrder2 = _postOrder2;
this.inOrder2 = _inOrder2;
//查找
this.getMin = _getMin;
this.getMax = _getMax;
this.find = _find;
//删除
this.remove = _remove;
this.removeNode =_removeNode;
this.getSmallest = _getSmallest;
//
this.showData = '';
var _this = this;
}
//
var nums = new Tree();
//
nums.insert(56);
nums.insert(22);
nums.insert(81);
nums.insert(10);
nums.insert(30);
nums.insert(77);
nums.insert(92);
//
nums.insert(6);
nums.insert(11);
nums.insert(29);
nums.insert(32);
nums.insert(76);
nums.insert(78);
nums.insert(89);
nums.insert(94);
/* */
//
console.log(nums);
//
console.log("中序遍历:");
nums.inOrder(nums.root);
console.log(nums);
//
console.log("先序遍历:");
nums.showData = [];
nums.proOrder(nums.root);
console.log(nums);
//
console.log("后序遍历:");
nums.showData = [];
nums.postOrder(nums.root);
console.log(nums);
//
console.log("分层遍历:");
nums.showData = [];
nums.layerOrder(nums.root);
console.log(nums);
//
console.log("先序遍历(非递归):");
nums.showData = [];
nums.proOrder2(nums.root);
console.log(nums);
//
console.log("后序遍历(非递归):");
nums.showData = [];
nums.postOrder2(nums.root);
console.log(nums);
//
console.log("中序遍历(非递归):");
nums.showData = [];
nums.inOrder2(nums.root);
console.log(nums);
//
console.log("最小值:");
console.log(nums.getMin());
console.log("最大值:");
console.log(nums.getMax());
//
console.log("查找:92");
console.log(nums.find('92'));
//
console.log("删除节点:81");
nums.remove('81');
//
console.log("中序遍历:");
nums.showData = [];
nums.inOrder(nums.root);
console.log(nums);
//
</script>二叉树,非递归遍历：
<script type="text/javascript">
/**
* 二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。
* 这一特性使得查找的效率很高。
*/
// http://blog.csdn.net/sjf0115/article/details/8645991
//二叉树
function Tree() {
//节点
var Node = function(data,left,right)
{
var _show = function()
{
return this.data;
}
//
this.data = data;
this.left = left;
this.right = right;
this.show = _show;
}
//添加节点
var _insert = function(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;
}
}
}
}
}
/*
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
*/
//分层遍历,(按层次从上往下,从左往右[从右往左])
var _layerOrder = function(node)
{
var arr = [];
arr.push(node);
while(arr.length)
{
var pNode = arr.pop();
_this.showData += pNode.show()+',';
//
if(pNode.right != null)
{
arr.push(pNode.right);
}
if(pNode.left != null)
{
arr.push(pNode.left);
}
}
}
//先序遍历(非递归)
var _proOrder2 = function(node)
{
//模拟栈
var arr = [];
//p是遍历指针
var p = node;
//栈不空或者p不空时循环
while( p!=null || arr.length !=0)
{
if(p != null)
{
//存入栈中
arr.push(p);
_this.showData += p.show()+',';
//遍历左子树
p = p.left;
}
else
{
p = arr.shift();
p = p.right;
}
}
}
//中序遍历(非递归)
var _inOrder2 = function(node)
{
}
//后序遍历(非递归)
var _postOrder2 = function(node)
{
//栈节点结构
var snode = function(node,num)
{
this.p = node; //p二叉树节点结构,
this.rvisited = num ? 1 :0 ; //rvisited:1代表p所指向的节点的右节点已被访问过
}
//栈
var stack = [];
var p =node;
//
while( p!= null)
{
var _node = new snode(p);
stack.push(_node);
p = p.left;
}
//
while(!stack.length == 0)
{
var sn = stack['0'];
//若其右孩子已经被访问过，或是该元素没有右孩子.
if(sn.p.right == null || sn.rvisited)
{
p = stack.shift(); //出栈
_this.showData += p.p.show()+',';
}
//若它的右孩子存在且rvisited为0，说明以前还没有动过它的右孩子，于是就去处理一下其右孩子。
else
{
sn.rvisited = 1;
sn.p ? (p = sn.p.right) : p = null;
//
while(p != null)
{
var _node = new snode(p);
stack.push(_node);
p = p.left;
}
}
}
}
//
this.root = null;
//添加
this.insert = _insert;
//非递归遍历
this.proOrder2 = _proOrder2;
this.postOrder2 = _postOrder2;
this.inOrder2 = _inOrder2;
this.layerOrder = _layerOrder;
//
this.showData = '';
var _this = this;
}
//
var nums = new Tree();
//
nums.insert(56);
nums.insert(22);
nums.insert(81);
nums.insert(10);
nums.insert(30);
nums.insert(77);
nums.insert(92);
//
nums.insert(6);
nums.insert(11);
nums.insert(29);
nums.insert(32);
nums.insert(76);
nums.insert(78);
nums.insert(89);
nums.insert(94);
/* */
//
console.log("分层遍历(非递归):");
nums.showData = [];
nums.layerOrder(nums.root);
console.log(nums);
//
console.log("先序遍历(非递归):");
nums.showData = [];
nums.proOrder2(nums.root);
console.log(nums);
//
console.log("后序遍历(非递归):");
nums.showData = [];
nums.postOrder2(nums.root);
console.log(nums);
//
console.log("中序遍历(非递归):");
nums.showData = [];
nums.inOrder2(nums.root);
console.log(nums);
//
</script>