某种程度上可动态分配的栈和队列

cctvfive

第一次在GA发主题帖,有点紧张....

这是研究中途弄的一点东西,看到最近大家都在研究数组存储,所以发上来一起交流下.
第一个是动态栈,第二个是动态队列.由于我自己使用不需要太大尺度的栈和队列,所以直接就用了一个数组...嗯,所以在通用性上还有所限制.
另外,由于时间关系,只是简单测试了一下.不保证逻辑结构完全正确,不过想必大家应该能看懂我的思路吧.
[jass]//多栈共享存储空间--可动态分配的栈
globals
    integer array StackData
    integer array StackPriorElementPointer  
    integer array StackTop
endglobals

//! textmacro Get_Rec takes NAME
globals
    integer $NAME$Top=1
    integer array $NAME$Pointer
    boolean array $NAME$IsBeingUsed
endglobals

function $NAME$Get_Int takes nothing returns integer
    local integer temp=$NAME$Pointer[$NAME$Top]
    if temp==0 then
        set temp=$NAME$Top
    endif
    set $NAME$Top=$NAME$Top+1
    if temp>8191 then
        return 0
    endif
    set $NAME$IsBeingUsed[temp]=true
    return temp
endfunction

function $NAME$Rec_Int takes integer i returns nothing
    set $NAME$IsBeingUsed=false
    set $NAME$Top=$NAME$Top-1
    set $NAME$Pointer[$NAME$Top]=i
endfunction
//! endtextmacro
//! runtextmacro Get_Rec("StackData")
//! runtextmacro Get_Rec("StackName")

function CreateStack takes nothing returns integer
    local integer stack=StackNameGet_Int()
    if StackNameIsBeingUsed[stack] then
        set StackTop[stack]=0
        return stack
    endif
    return 0
endfunction

function IsStackEmpty takes integer stack returns boolean
    if StackNameIsBeingUsed[stack] then
        return StackTop[stack]==0      
    endif
    return true
endfunction

function GetStackLength takes integer stack returns integer
    local integer top
    local integer length=0
    if StackNameIsBeingUsed[stack] then
       set top=StackTop[stack]
       loop
           exitwhen top==0
           set length=length+1
           set top=StackPriorElementPointer[top]
        endloop
        return length
    endif
    return 0
endfunction

//压栈
function Push takes integer stack, integer i returns nothing
    local integer top
    local integer next
    if StackNameIsBeingUsed[stack] then                     
        set top=StackTop[stack]                           
        set next=StackDataGet_Int()                             
        if StackDataIsBeingUsed[next] then                     
            set StackPriorElementPointer[next]=top        
            set StackTop[stack]=next                     
            set StackData[next]=i                                                               
        endif
    endif
endfunction

//退栈
function Pop takes integer stack returns integer
    local integer top=StackTop[stack]
    local integer prior
    if (StackNameIsBeingUsed[stack] and top!=0) then
        set prior=StackPriorElementPointer[top]         
        call StackDataRec_Int(top)                        
        set StackTop[stack]=prior                     
        return StackData[top]                          
    endif
    return -174
endfunction

//取得栈顶元素的值
function GetTop takes integer stack returns integer
    local integer top=StackTop[stack]
    if (StackNameIsBeingUsed[stack] and top>0) then
        return StackData[top]      
    endif
    return -174   
endfunction

function ClearStack takes integer stack returns nothing
    local integer top
    local integer prior   
    if (not StackNameIsBeingUsed[stack]) then
        return
    endif   
    set top=StackTop[stack]
    loop
        exitwhen top==0
        set prior=StackPriorElementPointer[top]
        call StackDataRec_Int(top)
        set top=prior
    endloop
    set StackTop[stack]=0
endfunction

//删除栈
function DestroyStack takes integer stack returns nothing
    local integer top
    local integer prior
    if (not StackNameIsBeingUsed[stack]) then
        return
    endif
    set top=StackTop[stack]
    loop
        exitwhen top==0
        set prior=StackPriorElementPointer[top]
        call StackDataRec_Int(top)
        set top=prior
    endloop
    call StackNameRec_Int(stack)
endfunction[/jass]

下面是队列的代码:

[jass]//多队列共享存储空间--可动态分配的队列
globals
    integer array QueueData
    integer array QueueNextElementPointer
    integer array QueueHead
    integer array QueueEnd
endglobals

//! textmacro Get_Rec takes NAME
globals
    integer $NAME$Top=1
    integer array $NAME$Pointer
    boolean array $NAME$IsBeingUsed
endglobals

function $NAME$Get_Int takes nothing returns integer
    local integer temp=$NAME$Pointer[$NAME$Top]
    if temp==0 then
        set temp=$NAME$Top
    endif
    set $NAME$Top=$NAME$Top+1
    if temp>8191 then
        return -1
    endif
    set $NAME$IsBeingUsed[temp]=true
    return temp
endfunction

function $NAME$Rec_Int takes integer i returns nothing
    set $NAME$IsBeingUsed=false
    set $NAME$Top=$NAME$Top-1
    set $NAME$Pointer[$NAME$Top]=i
endfunction
//! endtextmacro
//! runtextmacro Get_Rec("QueueData")
//! runtextmacro Get_Rec("QueueName")

//创建一个空队列
function CreateQueue takes nothing returns integer
    local integer queue=QueueNameGet_Int()
    local integer head   
    if QueueNameIsBeingUsed[queue] then
        set head=QueueDataGet_Int()
        if QueueDataIsBeingUsed[head] then
            set QueueHead[queue]=head
            set QueueEnd[queue]=head
            return queue
        endif
    endif
    return 0
endfunction

//清空一个队列
function ClearQueue takes integer queue returns nothing
    local integer head
    local integer end
    local integer temp
    if (not QueueNameIsBeingUsed[queue]) then
        return
    endif   
    set head=QueueHead[queue]
    set end=QueueEnd[queue]
    set temp=head
    loop
        exitwhen temp==end
        set temp=QueueNextElementPointer[temp]
        call QueueDataRec_Int(head)
    endloop
    set QueueEnd[queue]=head
endfunction

//判断一个队列是不是为空
function IsQueueEmpty takes integer queue returns boolean
    if QueueNameIsBeingUsed[queue] then
        return QueueHead[queue]==QueueEnd[queue]      
    endif
    return true
endfunction

//获取队列长度,因为感觉这个函数不是必须得,所以没有单独用变量存储长度
function GetQueueLength takes integer queue returns integer
    local integer head
    local integer end
    local integer length
    if QueueNameIsBeingUsed[queue] then
        set head=QueueHead[queue]
        set end=QueueEnd[queue]
        loop
            exitwhen head==end
            set length=length+1
            set head=QueueNextElementPointer[head]
        endloop
        return length      
    endif
    return 0
endfunction

//入列
function EnQueue takes integer queue, integer i returns nothing
    local integer end
    local integer next
    if QueueNameIsBeingUsed[queue] then
        set end=QueueEnd[queue]                           
        set next=QueueDataGet_Int()                           
        if QueueDataIsBeingUsed[next] then
            set QueueNextElementPointer[end]=next        
            set QueueEnd[queue]=next                                       
            set QueueData[next]=i                  
        endif
    endif
endfunction

//出列
function DeQueue takes integer queue returns integer
    local integer head=QueueHead[queue]
    local integer end=QueueEnd[queue]
    local integer next
    if (QueueNameIsBeingUsed[queue] and head!=end) then
        call QueueDataRec_Int(head)
        set next=QueueNextElementPointer[head]
        set QueueHead[queue]=next   
        return QueueData[next]                                 
    else
        return -174
    endif
endfunction

//取得队列首元素的值
function GetHead takes integer queue returns integer
    local integer head=QueueHead[queue]
    local integer end=QueueEnd[queue]
    if (QueueNameIsBeingUsed[queue] and head!=end) then
        return QueueData[QueueNextElementPointer[head]]      
    else
        return -174
    endif   
endfunction

//删除队列
function DestroyQueue takes integer queue returns nothing
    local integer head
    local integer end
    local integer next
    if (not QueueNameIsBeingUsed[queue]) then
        return
    endif
    set head=QueueHead[queue]
    set end=QueueEnd[queue]
    loop
        exitwhen head==end
        set next=QueueNextElementPointer[head]
        call QueueDataRec_Int(head)
        set head=next
    endloop
    call QueueNameRec_Int(queue)
endfunction[/jass]

最后简单来个2-10之间的进制转换,说明下栈的用法.至于队列...还想不出啥例子来..
[jass]//进制转换,输出结果为十进制整数,可以转成字符串看
function Conversion takes integer a, integer b returns integer
    local integer temp
    local integer result=a
    local integer forLoopA=0
    local integer stack=CreateStack()
    loop
        exitwhen result/b==0
        set temp=result-result/b*b
        set result=result/b
        call Push(stack,temp)
        set forLoopA=forLoopA+1
    endloop
    call Push(stack,result)
    set result=0
    set temp=10
    loop
        exitwhen IsStackEmpty(stack)
        set result=result*temp+Pop(stack)
        set forLoopA=forLoopA+1
    endloop
    call DestroyStack(stack)
    return result
endfunction[/jass]

疯人￠衰人

恩，还是用了VJ
果然不懂了……

cctvfive

那些VJ只是为了节省劳动力而已...跟核心部分没多大关系.


发现有些地方的代码在去掉Debug之后很囧.........修改下..

cccty1l

呃，我也提不出什么建设性的意见，就简单说一下吧。

首先是cctvfive你的帖子http://bbs.wow8.org/thread-99140-1-3.html，呵呵，我觉得太好了，之前我对一些概念性的东西并不了解，看了之后清楚了好多。

然后在里面你介绍和剖析了很多方法，关于struct和UnitDataSystem中方法，我觉得struct的方法是更好的，但是你使用的是后者，如果你使用前者的话，文本宏Get_Rec中的布尔值数组是可以不用的，vJ中是靠赋值为-1做到的吧。同时，参考我在拉链Hash中的代码，使用struct方法的时候，我们可以把那个数组用做两个用途，也就是节省了一个数组。

呃，不知道我说清楚了没有。

cctvfive

嗯,两种方法,差距也不会很大吧.

把文本宏去掉,利用struct的方法最少需要5个数组和4个整数变量(3+(1,2)+(1,2)),UnitDataSystem则最少需要5个数组和2个整数(3+(1,1)+(1,1)).几经修改,最后还是改成了后者.嗯嗯,两个IsBeingUsed都不是必须的..

cccty1l

非也，使用正确的话必定可以节省一个数组。

现在，我们一起看你的代码，如果我没有看错的话，数组StackTop[]指向链表的头部，数组StackPriorElementPointer[]指向一个节点的下一个节点，数组StackData[]用于存储数据，其余的两个数组使用了我在UnitDataSystem中使用的方法。其中数组StackNamePointer[]作用与数组StackTop[]相关，而StackDataPointer[]作用与数组StackPriorElementPointer[]相关，接下来的代码可以把上述相关的2组数组合并起来，也就是使用3个整数数组和4个整数变量完成之前的功能。(PS:貌似有个布尔值数组不能节省下来，嗯，或者是我的方法需要改进？)

[codes=jass]globals
    integer Top_F=0
    integer Top_N=1
    integer array Top
    boolean array TopIsBeingUsed

    integer Next_F=0
    integer Next_N=1
    integer array Next

    integer array Data
endglobals

function CreateStack takes nothing returns integer
    local integer stack=Top_F
    if stack!=0 then
        set Top_F=Top[stack]
    else
        set stack=Top_N
        if stack>8191 then
            return 0
        endif
        set Top_N=stack+1
    endif
    set TopIsBeingUsed[stack]=true
    return stack
endfunction

function IsStackEmpty takes integer stack returns boolean
    return not TopIsBeingUsed[stack] or Top[stack]==0
endfunction

function GetStackLength takes integer stack returns integer
    local integer top=Top[stack]
    local integer length=0
    if TopIsBeingUsed[stack] then
        loop
            exitwhen top==0
            set length=length+1
            set top=Next[top]
        endloop
    endif
    return length
endfunction

//压栈
function Push takes integer stack, integer i returns nothing
    local integer top=Top[stack]
    local integer next
    if TopIsBeingUsed[stack] then
        set next=Next_F
        if next!=0 then
            set Next_F=Next[next]
        else
            set next=Next_N
            if next>8191 then
                return
            endif
            set Next_N=next+1
        endif
        set Next[next]=top
        set Top[stack]=next
        set Data[next]=i
    endif
endfunction

//退栈
function Pop takes integer stack returns integer
    local integer top=Top[stack]
    local integer prior
    if TopIsBeingUsed[stack] and top!=0 then
        set prior=Next[top]
        set Next[top]=Next_F
        set Next_F=top
        set Top[stack]=prior
        return Data[top]
    endif
    return 0
endfunction

//取得栈顶元素的值
function GetTop takes integer stack returns integer
    local integer top=Top[stack]
    if TopIsBeingUsed[stack] and top!=0 then
        return Data[top]
    endif
    return 0
endfunction

function ClearStack takes integer stack returns nothing
    local integer top=Top[stack]
    local integer prior
    if TopIsBeingUsed[stack] and top!=0 then
        loop
            set prior=Next[top]
            exitwhen prior==0
            set top=prior
        endloop
        set Next[top]=Next_F
        set Next_F=Top[stack]
        set Top[stack]=0
    endif
endfunction

//删除栈
function DestroyStack takes integer stack returns nothing
    if TopIsBeingUsed[stack] then
        call ClearStack(stack)
        set Top[stack]=Top_F
        set Top_F=stack
        set TopIsBeingUsed[stack]=fasle
    endif
endfunction[/codes]

嗯，基本上照着你的代码抄下来的，注解就不用做了吧。

cccty1l

呃，貌似回的晚了。
刚才玩游戏去了，唉。
感觉LS的代码应该还是比较容易理解的吧，struct的方法正是因为可以两用我才决定使用它的，感觉如果不这样做的话，倒还不如直接用vJ。

-------------------修改的分隔线--------------------------------------

呃，补充一个，函数ClearStack 中包含了一个小技巧，这个技巧在你之后的队列的代码中应用的话会较好的提高效率，还请留意下。

cctvfive

嗯,的确,这样就可以省去重新加链接的麻烦了.学习之.

过两天有场考试,估计先得消失一段时间了,回来后再继续改进下,刚刚又有个新念头...

资源的分配回收和使用标记,貌似可以一个integer和一个integer array搞定....嗯,回来再说吧.现在脑子里很乱.

cccty1l

嗯，一个整数加一个数组确实是可以的，还是struct的方法，只是修改一点就可以了。代码如下：
[codes=jass]globals
    integer F=1
    integer array N
endglobals

function aaa takes nothing returns integer
    local integer x=F
    if x<=8191 then
        if N[x]!=0 then
            set F=N[x]
        else
            set F=x+1
        endif
        return x
    endif
    return 0
endfunction

function bbb takes integer x returns nothing
    set N[x]=F
    set F=x
endfunction[/codes]

嗯，很期待你的成品，我在此就尽点绵薄之力吧。

eff

。。。最近真的不少人在做这个东西呢。。其实翻翻数据结构与程序设计就好了嘛。。。