数据结构
内容纲要
数据结构的讲解很少，而且零零散散的，把以前使用其他ECMAScript实现的整理再用Typescript重新记录下。
数组
一切从数组开始：
由于ECMAScript比较灵活，数组也一样，语法也简单：
let arr: number[] = [];
for(let i: number = 0; i < 1000000; i++) arr[i] = i ;
let startT: number = new Date().getTime();
let num: number = 500;
while(num > 0)
{
arr.splice(0, 1);
num--;
}
console.log("time:", new Date().getTime() - startT);
堆栈
堆栈遵循先进后出的规则，直接使用数组的push()和pop()就可以，所以ECMAScript的数组本身就是最好的堆栈。
队列
队列遵循先进先出，用数组做队列在浏览器里删除数组元素比较慢，服务器端没有测试。
let startT:number = new Date().getTime();
let queue:number[] = [];
for(let i:number = 0 ; i<100000 ;i++);
{
queue.push(i);
}
for(let i:number = 0 ; i<100000 ;i++)
{
queue.shift();
}
console.log(new Date().getTime() - startT);
可以采用双向链表方式，这种方式可以当作队列也可以当作堆栈，效率比直接操作数组高：
let startT: number = new Date().getTime();
let queue:DLinkedList = new DLinkedList();
//...
console.log(new Date().getTime() - startT);
链表
双向链表，删除数据比较快，单链表省内存（一点点内存也是内存），删除会慢很多。但随着ECMAScript 2015的普及，直接使用Iterator即可。
let l: DLinkedList = new DLinkedList();
l.push(1);
l.push(2);
l.push(3);
console.log(l,l.head,l.tail);
l.pop();
console.log(l,l.head,l.tail);
l.unshift(0);
console.log(l,l.head,l.tail);
l.shift();
console.log(l,l.head,l.tail);
l.push(3);
console.log(l,l.head,l.tail);
let it:DListIterator = l.getIterator();
for(it.start() ; it.hasNext(); it.next())
{
console.log(it.node.data);
}
it.start();
it.next();
l.remove(it);
l.remove(it);
console.log(l,l.head,l.tail);
l.insert(it,2);
console.log(l,l.head,l.tail);
l.insert(it,3);
console.log(l,l.head,l.tail);
哈希表
哈希表类似ECMAScript的Object和Map，但ECMAScript的Map更适合做哈希表。 在ECMAScript中，Object和Map都是动态的，赋值就 obj.abc = 123 ，map.set(“abc”, 123)，删除就 delete obj.abc，map.delete(“abc”):
//Object
let o: object = {};
o["key"] = obj;
delete o["key"];
//Map
let m: any = new Map();
m.set("key", map);
m.delete("key");
二叉树
数组和链表都叫线性结构，而树是典型的非线性数据结构，下面是普通树：
let tree:Tree = new Tree(0);
let itr:TreeIterator = tree.getIterator();
itr.appendChild(1);
itr.appendChild(2);
// 0
// / \
// 1 2
itr.down();
itr.appendChild(3);
// 0
// / \
// 1 2
// /
// 3
itr.up();
itr.appendChild(4);
// 0
// / | \
// 1 2 4
// /
// 3
itr.childEnd();
itr.down();
itr.prependChild(5);
itr.prependChild(6);
// 0
// / | \
// 1 2 4
// / /\
// 3 6 5
console.log(tree.dump());
实现一个简单的树形菜单思路：
/**
* 前序遍历
*/
public preorder(Node:Tree, Process:function):void
{
Process(Node)
let itr:DListIterator = Node.children.getIterator()
while(itr.hasNext())
{
preorder(Tree(itr.node.data),Process)
itr.next();
}
}
/**
* 后序遍历
*/
public postorder(Node:Tree,Process:function):void
{
let itr:DListIterator = Node.children.getIterator()
while(itr.hasNext())
{
postorder(Tree(itr.node.data),Process)
}
Process(Node)
}
优先队列是一种特殊的队列，它不是先入先出，而是入队的元素会自动按你指定顺序排列，先出队的永远是你指定的顺序里排最前面的。
当然这个优先队列可以用数组实现，每次入队就push，然后排一次序，出队pop就可以了，但是这样效率不佳，一般优先队列会使用二叉堆去实现。
二叉树是只有2个子节点的树，二叉堆是一种特殊的二叉树，他的每个父节点都比子节点大。
比如A*：
let priorityQueue:Heap =new Heap();
priorityQueue.enqueue(2);
priorityQueue.enqueue(6);
priorityQueue.enqueue(5);
priorityQueue.enqueue(8);
priorityQueue.enqueue(7);
priorityQueue.enqueue(4);
priorityQueue.enqueue(1);
priorityQueue.enqueue(3);
priorityQueue.enqueue(9);
console.log(priorityQueue); //9,8,5,7,6,4,1,2,3
console.log(priorityQueue.dequeue()); //9
console.log(priorityQueue.dequeue()); //8
console.log(priorityQueue.dequeue()); //7
console.log(priorityQueue.dequeue()); //6
console.log(priorityQueue.dequeue()); //5
console.log(priorityQueue.dequeue()); //4
console.log(priorityQueue.dequeue()); //3
console.log(priorityQueue.dequeue()); //2
console.log(priorityQueue.dequeue()); //1
//逆序排列
let f:function = function(a:int,b:int):int{return b-a};
let p:Heap =new Heap(f);
p.enqueue(2);
p.enqueue(6);
p.enqueue(5);
p.enqueue(8);
p.enqueue(7);
p.enqueue(4);
p.enqueue(1);
p.enqueue(3);
p.enqueue(9);
console.log(p.dequeue()); //1
console.log(p.dequeue()); //2
console.log(p.dequeue()); //3
console.log(p.dequeue()); //4
console.log(p.dequeue()); //5
console.log(p.dequeue()); //6
console.log(p.dequeue()); //7
console.log(p.dequeue()); //8
console.log(p.dequeue()); //9
Heap内部也是数组存储，它的算法有两个关键:
1) 如何用数组储存二叉树结构
比如原树状结构是：
// 4
// / \
// 3 0
// /\
// 1 2
会存成：[4,3,0,1,2]
2) 如何永远保持parent比child大
四叉树
四叉树通常用于2d游戏碰撞检测。如果是小球，用半径算出来就可以，但如果碰上复杂的图形用位图碰撞检测，浏览器很难承受。
四叉树的思想就是先屏幕分割，然后过滤出离自己很近的，有可能产生碰撞的进行碰撞检测。
不过经过研究，自己实现的四叉树会有漏检，这里就略过。
图
图由节点node和指针arc组成，图的遍历与树差不多，分为广度优先遍历和深度优先遍历。
图在游戏中通常用作保存地图，区块其实就是简化了指针之后的图，所以他们的理论是相通的：
class Astar
{
/**
* 距离启发函数
*/
public static distance(startNode:GraphNode,endNode:GraphNode):number
{
return Math.sqrt( (endNode.data.x - startNode.data.x)*(endNode.data.x - startNode.data.x) + (endNode.data.y - startNode.data.y)*(endNode.data.y - startNode.data.y))
}
/**
* 曼哈顿启发函数
*/
public static manhattan(startNode:GraphNode,endNode:GraphNode):number
{
return Math.abs(endNode.data.x - startNode.data.x)+Math.abs(endNode.data.y - endNode.data.y);
}
public static find(graph:Graph , startIndex:int,endIndex:int):array
{
for each (let n:AstarNode in graph.nodes)
{
n.f = n.g = n.f = 0
n.parent = null
}
let open:Heap = new Heap(function(a:AstarNode,b:AstarNode):number{return b.f - a.f});
let close:array = []
AstarNode(graph.getNode(startIndex)).f = 0
open.enqueue(graph.getNode(startIndex));
while(open.heap.length>0)
{
let cur:AstarNode = AstarNode(open.dequeue())
if(cur==graph.getNode(endIndex))return Astar.getPath(cur)
close.push(cur)
for each(let i:GraphArc in cur.arcs)
{
let test:AstarNode = AstarNode(i.targetNode)
if(close.indexOf(test)>=0)continue；
if(open.heap.indexOf(test)<0)
{
test.parent =cur
test.g = cur.getArc(test).weight
test.h = Astar.distance(test,graph.getNode(endIndex))
test.f = test.g + test.h
open.enqueue(test);
}else
{
if( cur.g+ cur.getArc(test).weight < test.g)
{
test.parent = cur
test.g = cur.g+ cur.getArc(test).weight
test.f = test.h+test.g
open.modify(test,test);
}
}
}
}
return []
}
public static getPath(node:AstarNode):array
{
let arr:array = [node]
while(node.parent)
{
arr.push(node.parent)
node = node.parent
}
return arr
}
}
code enjoy!😜😜😜
作者：indeex
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。