在游戏制作中我们经常需要存储一些离散的对象数据,比如道具箱里的道具,经常需要执行插入和删除操作,而且道具之间没有联系是无序排列的.有些人会说直接用数组不就得了,但是有大量数据存储时的数组的删除插入操作的效率是很低的。
因此我们需要哈希表这样的可以提供快速的插入和删除，查找操作的数据结构，不论哈希表中有多少数据，插入和删除操作只需要接近常量的时间：即O(1)的时间级。
既然这么好那么我们的AS可以实现吗？当然可以！AS发展到AS2.0，已经成为在语法上更接近于Java + Pascal的面向对象的语言.如今,伴随着Flash8的发行,使得这种脚本语言添加了运行速度更加快捷,后台技术连接的更加方便等优点.因此我们完全可以用AS来实现一些常用数据结构。
首先我们先要实现有序链表，顾名思义，链表就是一种像链一样的数据结构，类似数组，但是不同的是链表每个节点一般都至少包括一个数据项和一个指向下个节点的指针,而且有序链表的数据是按顺序排列的。
建议大家把类都放到包里,这样便于以后查找和使用,这里我把这些类放在名为util的包里面.
有序链表的实现:
链表结点类:
classutil.Link
{
publicvariData;//dataitem(key)
publicvardData;
publicvarnext:util.Link;//nextlinkinlist
//------------------------------------------------------------
publicfunctionLink(id,dd)//constructor
{
iData=id;//(’next’isautomatically
dData=dd;
}//settonull)
//------------------------------------------------------------
publicfunctiondisplayLink():Void//displayourself
{
trace("{"+iData+","+dData+"}");
}
}//endclassLink
有序链表类:
import util.Link;//注意要导入我们前边的Link类！
classutil.SortedList
{
privatevarfirst:Link;//reftofirstlistitem
//------------------------------------------------------------
publicfunctionSortedList()//constructor
{first=null;}
//------------------------------------------------------------
publicfunctioninsert(theLink:Link):Void//insertlink,inorder
{
varkey=theLink.iData;
varprevious:Link=null;//startatfirst
varcurrent:Link=first;
//untilendoflist,
while(current!=null&&key>current.iData)
{//orcurrent>key,
previous=current;
current=current.next;//gotonextitem
}
if(previous==null)//ifbeginningoflist,
first=theLink;//first-->newlink
else//notatbeginning,
previous.next=theLink;//prev-->newlink
theLink.next=current;//newlink-->current
}//endinsert()
publicfunctiondeleteD(key):Void//deletelink
{//(assumesnon-emptylist)
varprevious:Link=null;//startatfirst
varcurrent:Link=first;
//untilendoflist,
while(current!=null&&key!=current.iData)
{//orkey==current,
previous=current;
current=current.next;//gotonextlink
}
//disconnectlink
if(previous==null)//ifbeginningoflist
first=first.next;//deletefirstlink
else//notatbeginning
previous.next=current.next;//deletecurrentlink
}//enddelete()
//------------------------------------------------------------
publicfunctionfind(key):Link//findlink
{
varcurrent:Link=first;//startatfirst
//untilendoflist,
while(current!=null&¤t.iData<=key)
{//orkeytoosmall,
if(current.iData==key)//isthisthelink?
returncurrent;//foundit,returnlink
current=current.next;//gotonextitem
}
returnnull;//didn’tfindit
}//endfind()
//------------------------------------------------------------
publicfunctiondisplayList():Void
{
trace("List(first-->last):");
varcurrent:Link=first;//startatbeginningoflist
while(current!=null)//untilendoflist,
{
current.displayLink();//printdata
current=current.next;//movetonextlink
}
trace("");
}
}//endclassSortedList
哈希表的实现:
哈希表类:
importutil.Link;//注意要导入我们前边的Link类！
importutil.SortedList;//注意要导入我们前边的SortedList类！
classutil.HashTable
{
privatevarhashArray:Array;//arrayoflists
privatevararraySize:Number;
//------------------------------------------------------------
publicfunctionHashTable(size:Number)//constructor
{
arraySize=size;
hashArray=newArray(arraySize);//createarray
for(varj=0;j<arraySize;j++)//fillarray
hashArray[j]=newSortedList();//withlists
}
//------------------------------------------------------------
publicfunctiondisplayTable():Void
{
for(varj=0;j<arraySize;j++)//foreachcell,
{
trace(j+".");//displaycellnumber
hashArray[j].displayList();//displaylist
}
}
//------------------------------------------------------------
publicfunctionhashFunc(key):Number//hashfunction
{
returnkey%arraySize;
}
//------------------------------------------------------------
publicfunctioninsert(theLink:Link):Void//insertalink
{
varkey=theLink.iData;
varhashVal=hashFunc(key);//hashthekey
hashArray[hashVal].insert(theLink);//insertathashVal
}//endinsert()
//------------------------------------------------------------
publicfunctiondeleteD(key):Void//deletealink
{
varhashVal=hashFunc(key);//hashthekey
hashArray[hashVal].deleteD(key);//deletelink
}//enddelete()
//------------------------------------------------------------
publicfunctionfind(key):Link//findlink
{
varhashVal=hashFunc(key);//hashthekey
vartheLink:Link=hashArray[hashVal].find(key);//getlink
returntheLink;//returnlink
}
//------------------------------------------------------------
}//endclassHashTable
哈希表的哈希函数hashFunc(key)我们可以自行设计，我这里用了最简单的求模运算。哈希函数设计的好坏决定着哈希表的各项操作的效率。
哈希表的使用:
varitemTable=newHashTable(6);//声明一个哈希表对象,并定义空间大小为6;
varitem:Array=newArray("cupper","herb","knife","tinymedal","cloth","milk");
for(vari=0;i<6;i++){
vartlink=newLink(6*i,item[i]);//声明一个链表结点,第一个参数为key值,第二个为想要存入的对象,这里是道具名;
itemTable.insert(tlink);//将结点插入哈希表;
}
itemTable.displayTable();//展示哈希表中的数据;
//大家可以试试其他查找和删除操作;
