AS3与数据结构

var arr:Array = []
for(var i:uint= 0 ;i<1000000;i++)arr[i]=i ;

var startT:Number = getTimer()
var num:uint = 500
while(num>0)
{
	arr.splice(0,1)
	num--
}
trace("time:",getTimer() - startT)

1000
0)
{
	arr[0] =arr[arr.length-1]
	arr.length -=1
	num--
}
trace(getTimer() - startT)

var queue:int = 0 ; i<100000 ;i++)
{
	queue.push(i);
}
100000 ;i++)
{
	queue.shift()
}
getTimer() - startT)

var queue:DLinkedList = new DLinkedList()
getTimer() - startT)

var l:DLinkedList = new DLinkedList()
l.push(1)
l.push(2)
l.push(3)
trace(l,l.head,l.tail) //[1,2,3] 1 3
l.pop()
l.unshift(0)
//[0,1,2] 0 2
l.shift()
l.push(//遍历,输出 1,3
var it:DListIterator = l.getIterator()
for(it.start() ; it.hasNext(); it.next())
{
	trace(it.node.data)
}
it.start()  // 索引归0
it.next()   
l.remove(it) //remove 2
l.remove(it) //remove 3
//[1] 1 1
l.insert(it,153)">2) 
l.insert(it,3,2] 1 2

var o:Object = {}
o["key"] = obj   //插入
delete o["key"]  //删除

var tree:Tree = new Tree(0);
var itr:TreeIterator = tree.getIterator()
itr.appendChild(1)
itr.appendChild(2) 

	  0  
	 / 
	1   2
	

itr.down()
itr.appendChild(3)
	

	 0  
	/ 
       2
      /
     3
	

itr.up()
itr.appendChild(4)

	  0  
	/ |  
       1  2  4
      /
     3
	

itr.childEnd()
itr.down()
itr.prependChild(5)
itr.prependChild(6)

	
	0  
      / |  
     4
    / /
   3	  6  5	
trace(tree.dump())

/**
* 前序遍历
*/
public function preorder(Node:Tree,Process:Function):void
{
	Process(Node)
	var itr:DListIterator = Node.children.getIterator()
	while(itr.hasNext())
	{
		preorder(Tree(itr.node.data),Process)
		itr.next();
	}
}

* 后序遍历
function postorder(Node:Tree,255)">Function):void
{
	var itr:DListIterator =  Node.children.getIterator()
	while(itr.hasNext())
	{
		postorder(Tree(itr.node.data),Process)
	}
	Process(Node)
	
}

var priorityQueue:Heap =new Heap() //新建二叉堆，默认从大到小排列
priorityQueue.enqueue(2) //入队9个数字
priorityQueue.enqueue(6)
priorityQueue.enqueue(5)
priorityQueue.enqueue(8)			
priorityQueue.enqueue(7)
priorityQueue.enqueue(4)
priorityQueue.enqueue(1)
priorityQueue.enqueue(3)
priorityQueue.enqueue(9)

trace(priorityQueue)  //输出9,8,5,7,6,4,3 ，发现并不是按顺序排列的
trace(priorityQueue.dequeue())  //9 但出队时就已经是排序好的了
//8
//7
//6
//5
//4
//3
//2
//1

//如果想要逆序排列，只需要提供一个compare Function，这个跟数组sort方法里的compareFunction参数一样，如下：

var f:Function = function(a:int,b:int):int{return b-a}
var 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(trace(p.dequeue()) //1
//9

4
     / 
    3   0
   /
  2

package examples.Astar
{
	import ds.Graph;
	import ds.GraphArc;
	import ds.GraphNode;
	import ds.Heap;
	
	class Astar
	{			
	 * 距离启发函数
 */
	static function 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))
	}
	 * 曼哈顿启发函数
function manhattan(startNode:GraphNode,255)">Number
	{
	Math.abs(endNode.data.x - startNode.data.x)+Math.abs(endNode.data.y - endNode.data.y);
	}
	 * 寻路
function find(graph:Graph , startIndex:endIndex:Array
	{
	//还原值
	for each (var n:AstarNode in graph.nodes)
	{
		n.f = n.g = n.f = 0
		n.parent = null
		
	}
	//根据f值升序排列 
	var open:Heap = new Heap(function(a:AstarNode,b:AstarNode):Number{return b.f - a.f}); 

	var close:Array = []
	//1，把起始节点添加到开启列表。
	AstarNode(graph.getNode(startIndex)).f =0	
	open.enqueue(graph.getNode(startIndex));
	//2，重复如下的工作：
	while(open.heap.length>0)
	{
		//a) 寻找开启列表中F值最低的节点。我们称它为当前节点。 
		var cur:AstarNode = AstarNode(open.dequeue())
		if(cur==graph.getNode(endIndex))return  Astar.getPath(cur) 
               //把目标格添加进了关闭列表，这时候路径被找到 
			 
		//b) 把它切换到关闭列表。
		close.push(cur)
		//c) 对相邻的格中的每一个？
		each(var i:GraphArc in cur.arcs)
		{
			var test:AstarNode = AstarNode(i.targetNode)
			//如果它不可通过或者已经在关闭列表中，略过它。
			if(close.indexOf(test)>=0)continue
			//如果它不在开启列表中，把它添加进去。
                        //把当前格作为这一格的父节点。记录这一格的F,G,和H值。
			
			if(open.heap.indexOf(test)<0)
			{						
				test.parent =cur
				test.g = cur.getArc(test).weight
				test.h = Astar.distance(test,graph.getNode(endIndex))
				// 这里使用距离启发值，原教程使用的曼哈顿启发函数
                                //可以替换成这句 Astar.manhattan(test,graph.getNode(endIndex))
				test.f = test.g + test.h
				open.enqueue(test);
			}else
			{
			 //如果它已经在开启列表中，用G值为参考检查新的路径是否更好。
                         //更低的G值意味着更好的路径。
			 //如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。
                         //如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。
				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 []
        }	
	function getPath(node:AstarNode):Array
	{
		Array = [node]
		while(node.parent)
		{
			arr.push(node.parent)
			node = node.parent
		}		
		return arr
	}
		
	}
}