Programming in Lua(Thrid Edition)笔记---11 Data Structures

Veröffentlicht am

11 Data Structures

  • 取长度运算符’#’从1算起

    1
    2
    3
    4
    5
    a = {}
    for i = -5, 5 do
    	a[i] = 0
    end
    print(#a) --> 5

  • 矩阵实现：1、table的table，mt[i][j] = 0；2、一维table，mt[(i - 1 * M) + j] = 0或者mt[s .. ":" .. t] = 0

  • 链表

    1
    2
    3
    4
    5
    6
    7
    list = nil
    list = {next = list, value = v}
    local l = list
    while l do
    	<visit l.value>
    	l = l.next
    end

  • 队列，只能操作头尾元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    List = {}
    function List.new()
    	return {fist = 0, last = -1}
    end
    function List.pushfirst(list, value)
    	local first = list.first - 1
    	list.first = first
    	list[first] = value
    end
    function List.pushlast(list, value)
    	local last = list.last + 1
    	list.last = last
    	list[last] = value
    end
    function List.popfirst(list)
    	local first = list.first
    	if first > list.last then error("list is empty") end
    	local value = list[first]
    	list[first] = nil -- to allow garbage collection
    	list.first = first + 1
    	return value
    end
    function List.poplast(list)
    	local last = list.last
    	if list.first > last then error("list is empty") end
    	local value = list[last]
    	list[last] = nil -- to allow garbage collection
    	list.last = last - 1
    	return value
    end

  • 集合

    1
    2
    3
    4
    5
    6
    function Set(list)
    	local set = {}
    	for _, l in ipairs(list) do set[l] = true end
    	return set
    end
    reserved = Set{"while", "end", "function", "local",}

  • bag(multiset)，多重集合

    1
    2
    3
    4
    5
    6
    7
    function insert(bag, element)
    	bag[element] = (bag[element] or 0) + 1
    end
    function remove(bag, element)
    	local count = bag[element]
    	bag[element] = (count and count > 1) and count - 1 or nil
    end

  • 字符串缓冲区，对于大量读入数据，由于用..连接字符串都需要新建一个字符串然后拷贝，所以以下代码不可取，会大大浪费时间和空间

    1
    2
    3
    4
    local buff = ""
    for line in io.lines() do
    	buff = buff .. line .. "\n"
    end

读入整个文件：

1
io.read("*a")

用table.concat()连接一个table的字符串：

1
2
3
4
5
local t = {}
for line in io.lines() do
	t[#t + 1] = line .. "\n"
end
local s = table.concat(t, "\n") .. "\n"

table.concat()第二个参数为字符串之间的分隔符，最后一个..仍会将字符串复制一份，优化：

1
2
t[#t + 1] = ""
s = table.concat(t, "\n")

  • 图，节点与节点名之间的映射：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    local function name2node(graph, name)
    	local node = graph[name]
    	if not node then
    		-- node does not exist; create a new one
    		node = {name = name, adj = {}}
    		graph[name] = node
    	end
    	return node
    end

从文件读入一个图：

1
2
3
4
5
6
7
8
9
10
11
12
13
function readgraph()
	local graph = {}
	for line in io.lines() do
		-- split line in two names
		local namefrom, nameto = string.match(line, "(%S+)%s+(%S+)")
		-- find corresponding nodes
		local from = name2node(graph, namefrom)
		local to = name2node(graph, nameto)
		-- adds 'to' to the adjacent set of 'from'
		from.adj[to] = true
	end
	return graph
end

找两节点之间的路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function findpath(curr, to, path, visited)
	path = path or {}
	visited = visited or {}
	if visited[curr] then  -- node already visited
		return nil         -- no path here
	end
	visited[curr] = true   -- mark node as visited
	path[#path + 1] = curr -- add it to path
	if curr == to then     -- final node?
		return path
	end
	-- try all adjacent nodes
	for node in pairs(curr.adj) do
		local p = findpath(node, to, path, visited)
		if p then return p end
	end
	path[#path] = nil      -- remove node from path
end