AS3的数据结构知识（参考Nshen的文章）

矫情吗；* 2022-09-20 09:08 112阅读 0赞

[http://www.nshen.net/dataStructure/2011/08/25/AS3-DataStructure.html][http_www.nshen.net_dataStructure_2011_08_25_AS3-DataStructure.html]

上面是nshen原文的链接，由于本人是软件工程软件维护方向，所以最近关注一下代码的积累与重用，同时也是为了以后正式走向开发岗位做些练习，可以将nshen总结的数据结构直接积攒起来以后重用：），我读了这篇文章，感觉写的很好，尤其是其中对游戏sprite的四叉树碰撞检测，这个在我当年直研考试曾经弄过一把四叉树，所以感觉很实用。下面是基于这篇文章做些个人的修改。

首先双向链表部分的get()方法，由于是双向链表，那么在遍历的时候就有正向遍历和反向遍历之分，在获取某个位置的元素时，如果该元素的index在链表的前一半，用正向遍历效率较高，后一半用反向遍历，所以我修改了get()方法如下。当然在链表很大的时候这样分别遍历效率会提高很多，如果链表较小则无所谓了

public function get(Index:uint):*
    {
        if(this._length <=0 || Index<0 || Index>this._length-1){
            return null;
        }
        var n:DListNode;
    /**
    *优化了一下，根据index为前一半还是
    *后一半选择正向遍历还是反向遍历
    **/
        if(Index <= _length/2){
        n = this.head;
        var i:uint = 0;
        while(i<Index)
        {
            i++;
            n=n.next;
        }
        }else {
        n = this.tail;
        var i:uint = _length-1;
        while(i > Index)
        {
            i--;
            n=n.prev;
        }
        }
        return n.data;
    }

另外nshen的代码中将tree转化成xml的时候，有个toXML方法，之前代码如下（我做过一点修改，下面会说）

/**
             * 输出xml能直接赋值给Flex的Tree组件的dataProvider属性
             *
             * 这段代码谁能看懂我服他，我自己都看不太懂，有好方法记得通知我。。。
             */
            public function toXML(Node:Tree = null):XML
            {
                var xmlStack:Array=[ ];
                if(Node == null)Node = this;
                var stack:Array = [Node];
                var s:String = "";
     
                while(stack.length>0)
                {
     
                    var t:* = stack.pop();
                    if(t is String)
                    {
                        s+=t;
                    }else
                    {
                        t = Tree(t);
                        s+="<node label='"+t.data+"'>";
                        if(t.children.length>0)
                        {
                            stack.push("</node>");
                        }else
                        {
                            s+="</node>";
                        }
                        var itr:DListIterator = t.children.getIterator();
                        itr.end();
                        while(itr.hasPrev())
                        {
                            stack.push(Tree(itr.node.data))
                            itr.prev();
                        }
                    }
                }
                return new XML(s);
            }

nshen提出了求好方法，于是我就献丑下。

发现其实那个方法是用栈来实现递归，由于xml文件的特殊性（需要一对标签），所以非递归的实现方式逻辑上就复杂了点，要将 入栈还要判断出栈的是否为字符串，于是我实现了个递归的方式。用栈实现非递归因为栈的后进先出特性，所以用的逆向遍历以达到和构建的树一样的节点顺序，用递归我就改成了正向遍历，关于字符串的+=和concat（）的效率问题，我暂时假定的是不考虑+=效率是否低下。

所以说递归用在树形遍历真是舒服：）

另外nshen中toxml方法有个参数，感觉不太舒服，于是我修改成了参数默认值为null，如果默认值为null，下面用if(Node == null)Node = this;判断改成this。这样如果只是想将树的某棵子树toxml就传参好了，否则就像调用toString（）一样直接调用，默认将本实例toxml。

我用递归实现的toxml方法如下：

public function toXML2():XML
            {
                var s:String = "";
                s = genXML(this);
                return new XML(s);
            }
     
            protected function genXML(t:Tree):String
            {
                var s:String = "";
                s += "<node label='"+t.data+"'>";
                var itr:DListIterator = t.children.getIterator();
                itr.start();
                while(itr.hasNext())
                {
                    s+=genXML(Tree(itr.node.data));
                    itr.next();
                }
                s += "</node>";
                return s;
            }

代码改的匆匆，跑了下nshen的测试用例，发现没错误就没有再检查，如果有程序有其他错误请联系我：）

[http_www.nshen.net_dataStructure_2011_08_25_AS3-DataStructure.html]: http://www.nshen.net/dataStructure/2011/08/25/AS3-DataStructure.html