求一个数据结构实现：动态数组

thewisp1

使用1个整数作为句柄，可以添加 / 删除整数元素（删除后其他元素序号可以变化），可以按序号得到元素值，可以获得元素数量。允许重复元素。
其实很类似于group吧，只不过是存整数元素的..

API有 create - 创建一个新的空的“动态数组”并返回整数句柄。删除。添加元素，删除元素，按序号得到元素，基于内容比较2个动态数组等。

要求只用integer 和 array实现！！

thewisp1

接口需求。。。native可以无视。。总之就是function

native DynamicArrayCreate             takes nothing                         returns integer
native DynamicArrayCreateInitialSize  takes integer initialSize             returns integer
native DynamicArrayDestroy            takes integer darr                    returns nothing
native DynamicArrayClear              takes integer darr                    returns nothing
native DynamicArrayHasElement         takes integer darr, integer element   returns boolean
native DynamicArrayAppendElement      takes integer darr, integer element   returns nothing
native DynamicArrayResize             takes integer darr, integer newSize   returns nothing
native DynamicArrayRemoveElement      takes integer darr, integer element   returns nothing
native DynamicArraySize               takes integer darr                    returns integer
native DynamicArrayMerge              takes integer darr1, integer darr2    returns nothing
native DynamicArrayDifference         takes integer darr1, integer darr2    returns nothing
native DynamicArrayEqual              takes integer darr1, integer darr2    returns boolean
native DynamicArrayContains           takes integer darr1, integer darr2    returns boolean
native DynamicArraySwap               takes integer darr1, integer darr2    returns nothing
native DynamicArrayFront              takes integer darr1                   returns integer
native DynamicArraySet                takes integer darr1, integer index, integer value returns nothing
native DynamicArrayGet                takes integer darr1, integer index    returns integer
native DynamicArrayClone              takes integer darr1                   returns integer
native UnitGrabAll                    takes integer darr                    returns nothing

疯人￠衰人

不考虑效率么？

可以实现的方式只有Location了

http://bbs.islga.org/read-htm-tid-26756.html
http://bbs.islga.org/read-htm-tid-28075.html
http://bbs.islga.org/read-htm-tid-26924.html

Location的点使用的是Real
有效数字式8位
过大的存储内容会产生BUG
可以使用间接存储的方式
比如组成一个极大整数的数组

数组变量系统
这个基本上能满足你的要求把
不过效率没有保证

cctvfive（豆腐）也写了个类似的系统
似乎也不错
具体在哪里可以问橙子……

----------- 帖子于 18:51 更新 --------- 之前内容发布于 18:48 ------------

http://bbs.islga.org/read-htm-tid-26840.html
这里

cccty1l

试着写了下，有写函数不知道什么作用，你补充下吧

Contains有点难，如果现在的函数OK的话，那我就补充下。

[codes=jass]
globals
    integer array DyA_value
    integer array DyA_qian
    integer array DyA_hou
    integer DyA_num=1
    integer array DyA_arrsize
endglobals

function DyA_NewNum takes nothing returns integer
    local integer i=DyA_num
    local integer next=DyA_hou

    if(next==0)then
        set next=i+1
        if(next>8191)then
            return 0
        endif
    endif
    set DyA_num=next
    set DyA_value=0
    return i
endfunction

function DyA_DelNum takes integer i returns nothing
    set DyA_hou=DyA_num
    set DyA_num=i
endfunction

function DyA_DelNums takes integer x,integer y returns nothing
    set DyA_hou[y]=DyA_num
    set DyA_num=x
endfunction

function DyA_SetValue takes integer i,integer value returns nothing
    set DyA_value=value
endfunction

function DyA_Findnum_hou takes integer i,integer x returns integer
    loop
        exitwhen x==1
        set i=DyA_hou
        set x=x-1
    endloop
    return i
endfunction

function DyA_Findnum_qian takes integer i,integer x returns integer
    set i=DyA_qian
    loop
        exitwhen x==1
        set i=DyA_qian
        set x=x-1
    endloop
    return i
endfunction

function DyA_Deljiedian takes integer i returns nothing
    local integer x=DyA_hou
    local integer y=DyA_qian
    set DyA_hou[y]=x
    set DyA_qian[x]=y
    call DyA_DelNum(i)
endfunction
[/codes]

[codes=jass]
function DynamicArrayCreate takes nothing returns integer
    local integer i=DyA_NewNum()
    set DyA_qian=i
    set DyA_hou=i
    set DyA_arrsize=1
    return i
endfunction

function DynamicArrayCreateInitialSize takes integer initialSize returns integer
    local integer i=DyA_NewNum()
    local integer x=i
    local integer y=i
    set DyA_arrsize=initialSize
    loop
        exitwhen initialSize==1
        set y=DyA_NewNum()
        set DyA_hou[x]=y
        set DyA_qian[y]=x
        set initialSize=initialSize-1
        set x=y
    endloop
    set DyA_hou[x]=i
    set DyA_qian=x
    return i
endfunction

function DynamicArrayDestroy takes integer darr returns nothing
    set DyA_arrsize[darr]=0
    call DyA_DelNums(darr,DyA_qian[darr])
endfunction

function DynamicArrayClear takes integer darr returns nothing
    local integer i=darr
    loop
        set DyA_value=0
        set i=DyA_hou
        exitwhen i==darr
    endloop
endfunction

function DynamicArrayHasElement takes integer darr,integer element returns boolean
    local integer i=darr
    loop
        if(element==DyA_value)then
            return true
        endif
        set i=DyA_hou
        exitwhen i==darr
    endloop
    return false
endfunction

function DynamicArrayAppendElement takes integer darr,integer element returns nothing
    local integer i=DyA_NewNum()
    local integer x=DyA_qian[darr]
    set DyA_value=element
    set DyA_hou=darr
    set DyA_qian=x
    set DyA_hou[x]=i
    set DyA_qian[darr]=i
    set DyA_arrsize[darr]=DyA_arrsize[darr]+1
endfunction

function DynamicArrayMerge takes integer darr1,integer darr2 returns nothing
    local integer x=DyA_qian[darr1]
    local integer y=DyA_qian[darr2]
    set DyA_hou[x]=darr2
    set DyA_hou[y]=darr1
    set DyA_qian[darr2]=x
    set DyA_qian[darr1]=y
    set DyA_arrsize[darr1]=DyA_arrsize[darr1]+DyA_arrsize[darr2]
    set DyA_arrsize[darr2]=0
endfunction

function DynamicArrayResize takes integer darr,integer newSize returns nothing
    local integer size=DyA_arrsize[darr]
    local integer x
    if(size<newSize)then
        call DynamicArrayMerge(darr,DynamicArrayCreateInitialSize(newSize-size))
        return
    elseif(size==newSize)then
        return
    elseif(size>newSize)then
        if(newSize<=0)then
            call DynamicArrayDestroy(darr)
            return
        else
            if(newSize<size/2)then
                set x=DyA_Findnum_hou(darr,newSize)
            elseif(newSize>=size/2)then
                set x=DyA_Findnum_qian(darr,size-newSize+1)
            endif
            call DyA_DelNums(DyA_hou[x],DyA_qian[darr])
            set DyA_hou[x]=darr
            set DyA_qian[darr]=x
        endif
    endif
    set DyA_arrsize[darr]=newSize
endfunction

function DynamicArrayRemoveElement takes integer darr,integer element returns nothing
    local integer size=DyA_arrsize[darr]
    local integer i=darr
    if(size<=0)then
        return
    elseif(size==1)then
        if(DyA_value==element)then
            set DyA_value=0
        endif
    else
        if(DyA_value==element)then
            set DyA_value=DyA_value[DyA_hou]
            call DyA_Deljiedian(DyA_hou)
            set DyA_arrsize[darr]=size-1
            return
        endif
        set i=DyA_hou
        loop
            exitwhen i==darr
            if(DyA_value==element)then
                call DyA_Deljiedian(i)
                set DyA_arrsize[darr]=size-1
                return
            endif
            set i=DyA_hou
        endloop
    endif
endfunction

function DynamicArrayRemoveElementAll takes integer darr,integer element returns nothing
    local integer size=DyA_arrsize[darr]
    local integer i=darr
    if(size<=0)then
        return
    elseif(size==1)then
        if(DyA_value==element)then
            set DyA_value=0
        endif
    else
        set i=DyA_hou
        loop
            exitwhen i==darr
            if(DyA_value==element)then
                call DyA_Deljiedian(i)
                set size=size-1
            endif
            set i=DyA_hou
        endloop
        if(DyA_value==element)then
            if(size==1)then
                set DyA_value=0
            else
                set DyA_value=DyA_value[DyA_hou]
                call DyA_Deljiedian(DyA_hou)
                set DyA_arrsize[darr]=size-1
            endif
        endif
    endif
endfunction

function DynamicArraySize takes integer darr returns integer
    return DyA_arrsize[darr]
endfunction

//function DynamicArrayDifference takes integer darr1,integer darr2 returns nothing

function DynamicArrayEqual takes integer darr1,integer darr2 returns boolean
    local integer x=darr1
    local integer y=darr2

    if(DyA_arrsize[x]!=DyA_arrsize[y])then
        return false
    else
        loop
            if(DyA_value[x]!=DyA_value[y])then
                return false
            endif
            set x=DyA_hou[x]
            set y=DyA_hou[y]
            exitwhen x==darr1
        endloop
    endif
    return true
endfunction

//function DynamicArrayContains takes integer darr1,integer darr2 returns boolean

function DynamicArraySwap takes integer darr1,integer darr2 returns nothing
    local integer x=DyA_arrsize[darr1]
    local integer y=DyA_arrsize[darr2]
    local integer a

    if(x<=0 or y<=0)then
        return
    endif

    if(x<=y)then
    else
        set a=darr1
        set darr1=darr2
        set darr2=a
    endif

    set x=darr1
    set y=darr2
    loop
        set a=DyA_value[x]
        set DyA_value[x]=DyA_value[y]
        set DyA_value[y]=a
        set x=DyA_hou[x]
        set y=DyA_hou[y]
        exitwhen x==darr1
    endloop
endfunction

//function DynamicArrayFront takes integer darr1 returns integer

function DynamicArraySet takes integer darr,integer index,integer value returns nothing
    local integer size=DyA_arrsize[darr]

    if(index>size or index<=0)then
        return
    elseif(index<=size/2)then
        set DyA_value[DyA_Findnum_hou(darr,index)]=value
    else
        set DyA_value[DyA_Findnum_qian(darr,size-index+1)]=value
    endif
endfunction

function DynamicArrayGet takes integer darr,integer index returns integer
    local integer size=DyA_arrsize[darr]

    if(index>size or index<=0)then
        return 0
    elseif(index<=size/2)then
        return DyA_value[DyA_Findnum_hou(darr,index)]
    endif
    return DyA_value[DyA_Findnum_qian(darr,size-index+1)]
endfunction

function DynamicArrayClone takes integer darr returns integer
    local integer size=DyA_arrsize[darr]
    local integer x=darr
    local integer i=DynamicArrayCreateInitialSize(size)

    loop
        set DyA_value=DyA_value[x]
        set x=DyA_hou[x]
        set i=DyA_hou
        exitwhen x==darr
    endloop

    return i
endfunction

//function UnitGrabAll takes integer darr returns nothing
[/codes]

----------- 帖子于 19:21 更新 --------- 之前内容发布于 19:17 ------------

就是用循环双向链表做的动态数组，总的上限就是8191。我只测试了没有书写错误，逻辑错误的话我慢慢排查下。

疯人￠衰人

这个是一个数组吧

LZ的需求不是任意时刻创建的可创建无限多个的么？

cccty1l

动态数组不表示无限吧，而且动态数组一般存的东西都不多吧。

我也不确定，不过这个勉强满足啦。

thewisp1

好强力呀。慢慢看。。
有几个问题问下，，
假如现在动态数组中有5个元素对应序号，增加一个，问增加的元素序号是多少？删除呢？序号是从0开始么？（忘了说要求序号从0）

一个动态数组的元素的序号总能维持对应 0 ~ (size-1) 么?不会出现漏空？

这个方法所有同时存在的动态数组元素数量总和不能超过8191是么？如果超过可以对玩家显示文字提醒下么？

hmm... 还有创建数组，删除数组，添加元素，按序号读取元素 这4个操作的效率分别是多少呢？

谢拉。。

cccty1l

哎呀，序号是从1开始的，我看看能不能修改吧。

动态数组的上限是8191，不够的话可以增加，在超过上限以后的排错跳出做的不完全，我还得修改下。

创建数组需要历遍，复杂度是O(n),
删除数组是O(1)，
添加元素是直接追加在数组尾（size+1），复杂度是O(1)，
删除单个元素需要历遍是O(n)，这个我做了两个函数，一个是删除第一个遇到的满足条件的元素，另一个是删除全部的满足条件元素，如果所有元素都被此函数删除了，那么数组长度变成1，存储的数值归零。
序号读取元素是O(n)，
Contains的判断应该是O(n^2)。

thewisp1

汗，如果读取元素是O(n).. 那么形如
loop
exitwhen i > size
get(array, i) .....
set i =i+1
endloop
也就是遍历每个元素做事情，是不是O(n^2)了？

使用比较频繁的是添加和删除元素，应该会是瓶颈
（就是给单位绑定一个创建好的数组，然后不断更新数据）

其次频繁的是遍历一个数组做判断等事情，比如有80个元素的数组遍历判断是否符合xxx。。。

hmm 我检查了一下实际需求，对添加元素，删除元素，得到元素的效率要求比较高。创建和删除数组相对次要一些。最好得到元素是O(1)，添加也是O(1)，删除不超过O(n)..

cccty1l

嗯 是啊，不过不用这么写啊，看最后的那个clone，只需要一次历遍就行了。

我可以增加一个函数，可以依次弹出数组中的数据。
你还是参考我在clone里的写法吧。

再要快的话，可能得要别的数据结构了吧。

cccty1l

应该是没有bug了。

附一测试图。