Lua-単一チェーンテーブルおよびチェーンテーブル操作を実現


Luaが単一チェーンテーブルを実現する場合,ヘッダノードアドレスを格納する変数を一定に保つことに注意し,遍歴する必要がある場合は他の変数を割り当てて操作する.常にチェーンテーブル名変数(ヘッダノードアドレスを格納する変数、すなわちチェーンテーブル名.next=headNode)に安全にアクセスします.
--        table
local Linklist = {}

--    ,      
function Linklist.init()
    -- body
    local node = {}
    -- list      
    local list = node
    list.length = 0
    list.next = nil
    print("       ")
    --              
    return list, node
end

function Linklist.checkList(list)
    -- body
    if not list then print("     ") return end
end

function Linklist.checkIndex(list, index)
    -- body
    if index < 1 or index > list.length + 1 then
        print("    ")
        return
    end
end

function Linklist.checkAll(list, index)
    -- body
    Linklist.checkList(list)
    Linklist.checkIndex(list, index)
end

--       
function Linklist.addTail(list, node, data)
    -- body
    Linklist.checkList(list)

    --         
    node.next = {} 
    node = node.next
    node.next = nil
    node.data = data
    list.length = list.length+1
    
    print("        ")
    return node
end

--       
function Linklist.addHead(list, data)
    -- body
    Linklist.checkList(list)

    --          next
    local newNode = {}  
    newNode.data = data
    newNode.next = list.next
    list.next = newNode
    list.length = list.length+1
    print("        ")
end

--       
function Linklist.insertByIndex(list, index, data)
    -- body
    Linklist.checkAll(list, index)

    local j,k,l = index - 1, 0, list
    while k ~= j do
        k = k + 1
        l = l.next
    end

    --     
    local newNode = {}
    newNode.data = data
    newNode.next = l.next
    l.next = newNode
    list.length = list.length + 1
    print("        ")

end

--              
function Linklist.deleteByIndex(list, index)
    -- body
    Linklist.checkAll(list, index)

    local j,k,l = index - 1, 0, list
    while k ~= j do
        k = k + 1
        l = l.next
    end

    --      l.next
    d = l.next.data
    t = l.next.next
    l.next = nil
    l.next = t
    list.length = list.length - 1
    print("        ")
    
end

--         
function Linklist.modifyDataByIndex(list, index, data)
    -- body
    Linklist.checkAll(list, index)

    local l = list.next
    local k = 1
    while l do
        if k == index then
            l.data = data
            print("        ")
            return
        end
        l = l.next
        k = k + 1
    end
    print("    ")
end

--           
function Linklist.getDataByIndex(list, index)
    -- body
    Linklist.checkAll(list, index)

    local l = list.next
    local k = 1
    while l do
        if k == index then
            print("        ")
            return l.data
        end
        l = l.next
        k = k + 1
    end
    print("    ")
end

--       
function Linklist.reverse(list)
    -- body
    Linklist.checkList(list)

    -- p         q            pr    
    -- ret         
    local p, q= list.next, nil
    list.next = nil
    while p do
        pr = p.next
        p.next = q
        q = p
        p = pr
    end
    list.next = q
    print("        ")
    return list
end

--       
function Linklist.display(list)
    -- body
    Linklist.checkList(list)

    local l = list.next
    local x = 1
    while l do
        print(x .. "  " .. l.data)
        l = l.next
        x = x + 1
    end
    print('-- display ok --')
end

--       
function Linklist.isEmpty(list)
    -- body
    Linklist.checkList(list)

    return list.length == 0
end

--     ,     ,    ,     ,           
function Linklist.clear(list)
    -- body
    Linklist.checkList(list)

    while true do
        -- fNode      
        fNode = list.next
        --        
        if not fNode then  
            print("      ")
            break
        end
        t = fNode.next
        --   
        list.next = nil
        list.next = t
    end
    list.length = 0
end

--     
function Linklist.destory(list)
    -- body
    if list then
        Linklist.clear(list)
    end
    list = nil
    print("      ")
end

Linklist.addByIndex = Linklist.insertByIndex
Linklist.removeByIndex = Linklist.deleteByIndex
Linklist.changeDataByIndex = Linklist.modifyDataByIndex

local dList, curNode = Linklist.init()
print(Linklist.isEmpty(dList))
curNode = Linklist.addTail(dList, curNode, 6)
curNode = Linklist.addTail(dList, curNode, 7)
Linklist.addHead(dList, 7)
Linklist.insertByIndex(dList, 1, 1)
Linklist.insertByIndex(dList, 3, 3)
Linklist.addByIndex(dList, 6, 9)
Linklist.deleteByIndex(dList, 3)
Linklist.removeByIndex(dList, 4)
Linklist.modifyDataByIndex(dList, 4, 20)
Linklist.changeDataByIndex(dList, 3, 16)
Linklist.changeDataByIndex(dList, 1, 3)
print(Linklist.isEmpty(dList))
print(Linklist.getDataByIndex(dList, 3))
Linklist.display(dList)
Linklist.reverse(dList)
Linklist.display(dList)
Linklist.clear(dList)
print(Linklist.isEmpty(dList))
Linklist.destory(list)

print("=====================     ==============================")

実行結果は次のとおりです.
       
true
        
        
        
        
        
        
        
        
        
        
        
false
        
16
1  3
2  7
3  16
4  20
-- display ok --
        
1  20
2  16
3  7
4  3
-- display ok --
      
true
      
=====================     ==============================