《Lua程序设计第四版》 第二部分14~17章自做练习题答案 ...

Lua程序设计第四版第二部分编程实操自做练习题答案，带⭐为重点。
14.1 ⭐

该函数用于两个稀疏矩阵相加

1. function martixAdd(a, b)
2.     local c = {}
3.     for i = 1, #a, 1 do
4.         c[i] = {}
5.         for k, v in pairs(a[i]) do
6.             c[i][k] = v
7.         end
8.     end
9.     for i = 1, #b, 1 do
10.         for k, v in pairs(b[i]) do
11.             c[i][k] = (c[i][k] or 0) + v
12.             c[i][k] = (c[i][k] ~= 0) and c[i][k] or nil
13.         end
14.     end
15.     return c
16. end
18. A = {{
19.     [5] = 1
20. }, {}, {
21.     [1] = 3,
22.     [3] = 4
23. }, {}, {
24.     [4] = -1
25. }}
27. B = {{
28.     [2] = 2
29. }, {}, {
30.     [1] = -3,
31.     [4] = -3
32. }, {
33.     [3] = 8
34. }, {
35.     [1] = 7
36. }}
38. for k, v in pairs(martixAdd(A, B)) do
39.     for j, i in pairs(v) do
40.         print(k .. "行", j .. "列", i)
41.     end
42. end

复制代码

14.2

改写队列的实现，使得当队列为空时两个索引都返回0

1. function listNew()
2.     return {
3.         _first = 0,
4.         _last = -1,
5.         first = function()
6.             if _first > _last then
7.                 return 0
8.             end
9.             return _first
10.         end,
11.         last = function()
12.             if _first > _last then
13.                 return 0
14.             end
15.             return _last
16.         end
17.     }
18. end
20. l = listNew()
21. -- 模拟空队列
22. l._first = 10
23. l._last = 9
24. print(l.first, l.last)

复制代码

14.3

修改图所用的数据结构，使得图可以保存每条边的标签。该数据结构应该使用包括两个字段的对象来表示每一条边，即边的标签和边指向的节点。与邻接集合不同，每一个节点保存的是从当前节点出发的边的集合。

1. local function name2node(graph, name)
2.     local node = graph[name]
3.     if not node then
4.         graph[name] = {
5.             name = name,
6.             edges = {}
7.         }
8.         node = graph[name]
9.     end
10.     return node
11. end
13. function readgraph(file)
14.     local graph = {}
15.     f = io.open(file, 'r')
16.     for l in f:lines() do
17.         local name1, name2, edgeLabel = string.match(l, "(%S+)%s+(%S+)%s+(%S+)")
18.         local from = name2node(graph, name1)
19.         local to = name2node(graph, name2)
20.         table.insert(from.edges, {
21.             ["label"] = edgeLabel,
22.             ["adj"] = to
23.         })
24.     end
25.     return graph
26. end
28. graph = readgraph("graph.txt")
29. for k, v in pairs(graph) do
30.     for _, v in pairs(v.edges) do
31.         print(k, v.label, v.adj.name)
32.     end
33. end
35. [[
36. C       1       D
37. C       3       E
38. D       1       C
39. D       7       E
40. A       4       B
41. A       2       D
42. B       1       D
43. B       4       C
44. ]]

复制代码

1. A B 4
2. A D 2
3. B D 1
4. D C 1
5. C D 1
6. B C 4
7. D E 7
8. C E 3

复制代码

14.4 ⭐

使用14.3的表示方式，其中边的标签代表两个终端节点之间的距离。该函数使用Dijkstra算法寻找两个指定节点之间的最短路径。

1. local function name2node(graph, name)
2.     local node = graph[name]
3.     if not node then
4.         graph[name] = {
5.             name = name,
6.             edges = {}
7.         }
8.         node = graph[name]
9.     end
10.     return node
11. end
13. function readgraph(file)
14.     local graph = {}
15.     f = io.open(file, 'r')
16.     for l in f:lines() do
17.         local name1, name2, edgeLabel = string.match(l, "(%S+)%s+(%S+)%s+(%S+)")
18.         local from = name2node(graph, name1)
19.         local to = name2node(graph, name2)
20.         table.insert(from.edges, {
21.             ["label"] = edgeLabel,
22.             ["adj"] = to
23.         })
24.     end
25.     return graph
26. end
28. graph = readgraph("graph.txt")
29. for k, v in pairs(graph) do
30.     for _, v in pairs(v.edges) do
31.         print(k, v.label, v.adj.name)
32.     end
33. end
35. function Dijkstra(graph, a, b)
36.     -- 点不存在
37.     if not graph[a] or not graph[b] then
38.         return nil
39.     end
40.     local D = {}
41.     local T = {}
42.     -- D 加入起点
43.     D[graph[a]] = 0
44.     -- T 加入其他点,初始化可达最短距离为正无穷大
45.     for name, node in pairs(graph) do
46.         if name ~= a then
47.             T[node] = math.maxinteger
48.         end
49.     end
50.     -- 当D中不包含b点时循环
51.     while not D[graph[b]] do
52.         -- 根据 D 迭代 T 可达最短距离
53.         for node, d in pairs(D) do
54.             for _, edge in pairs(node.edges) do
55.                 if not D[edge.adj] then
56.                     local newD = d + tonumber(edge.label)
57.                     T[edge.adj] = math.min(T[edge.adj], newD)
58.                 end
59.             end
60.         end
61.         -- 选择 T 可达距离最小的点
62.         local tmp = nil
63.         for node, d in pairs(T) do
64.             tmp = tmp or node
65.             if d < T[tmp] then
66.                 tmp = node
67.             end
68.         end
69.         -- 如果没有点被选中，退出循环
70.         if T[tmp] == math.maxinteger then
71.             return nil
72.         end
73.         -- 将前面选择到的点加入D,并从T删除
74.         D[tmp] = T[tmp]
75.         T[tmp] = nil
76.     end
77.     return D[graph[b]]
78. end
80. d = Dijkstra(graph, "A", "E")
81. if not d then
82.     print("无路径")
83. end
84. print(d)
86. -- 具体路径计算为 A->E 路径距离 - (X->E 路径距离) == A -> X 路径距离
87. -- 即 A->X->E

复制代码

15.1~15.2

修改序列化函数，使其带缩进地输出嵌套表，并添加["key"]=value的语法

1. function serialize(o, tab)
2.     tab = tab or 1
3.     local t = type(o)
4.     if t == "number" or t == "string" or t == "boolean" or t == "nil" then
5.         io.write(string.format("%q", o))
6.     elseif t == "table" then
7.         io.write("{\n")
8.         for k, v in pairs(o) do
9.             io.write(string.rep("   ", tab))
10.             io.write(" [", string.format("%s", serialize(k)), "] = ")
11.             serialize(v, tab + 1)
12.             io.write(",\n")
13.         end
14.         io.write(string.rep("   ", tab))
15.         io.write("}")
16.     else
17.         error("cannot serialize a" .. t)
18.     end
19. end
21. A = {
22.     B = {
23.         E = "dog",
24.         H = {
25.             F = "PIG",
26.             G = "goose"
27.         }
28.     },
29.     C = "apple",
30.     D = 114514,
31.     I = {1, 2, 3, {4, 5, 6}}
32. }
34. serialize(A)
36. [[
37. {
38.     ["C"] = "apple",
39.     ["D"] = 114514,
40.     ["I"] = {
41.        [1] = 1,
42.        [2] = 2,
43.        [3] = 3,
44.        [4] = {
45.           [1] = 4,
46.           [2] = 5,
47.           [3] = 6,
48.          },
49.       },
50.     ["B"] = {
51.        ["E"] = "dog",
52.        ["H"] = {
53.           ["G"] = "goose",
54.           ["F"] = "PIG",
55.          },
56.       },
57.    }
58. ]]

复制代码

15.3

修改15.2，使其只在必要时，当键为字符串而不是合法标识符时才使用形如["key"]=value的语法

1. function serialize(o, tab)
2.     tab = tab or 1
3.     local t = type(o)
4.     if t == "number" or t == "string" or t == "boolean" or t == "nil" then
5.         io.write(string.format("%q", o))
6.     elseif t == "table" then
7.         io.write("{\n")
8.         for k, v in pairs(o) do
9.             io.write(string.rep("   ", tab))
10.             if type(k) == "string" and string.match(k, "[%a_]+[%w_]*") then
11.                 io.write("  ", k, "  = ")
12.             else
13.                 io.write(" [")
14.                 serialize(k)
15.                 io.write("] = ")
16.             end
17.             serialize(v, tab + 1)
18.             io.write(",\n")
19.         end
20.         io.write(string.rep("   ", tab))
21.         io.write("}")
22.     else
23.         error("cannot serialize a" .. t)
24.     end
25. end
27. A = {
28.     B = {
29.         E = "dog",
30.         H = {
31.             F = "PIG",
32.             G = "goose"
33.         }
34.     },
35.     C = "apple",
36.     D = 114514,
37.     I = {1, 2, 3, {4, 5, 6}}
38. }
40. serialize(A)
42. [[
43. {
44.      C  = "apple",
45.      D  = 114514,
46.      I  = {
47.        [1] = 1,
48.        [2] = 2,
49.        [3] = 3,
50.        [4] = {
51.           [1] = 4,
52.           [2] = 5,
53.           [3] = 6,
54.          },
55.       },
56.      B  = {
57.         E  = "dog",
58.         H  = {
59.            G  = "goose",
60.            F  = "PIG",
61.          },
62.       },
63.    }
64. ]]

复制代码

15.4

使其在可能时使用列表的构造器语法。例如应将表{14,15,19}序列化为{14,15,19}，而不是{[1] =14,[2]=15,[3]=19}，在遍历该部分的时候不要重复序列化。

1. function serialize(o)
2.     local typ = type(o)
3.     if typ == "number" or typ == "string" or typ == "boolean" or typ == "nil" then
4.         io.write(string.format("%q", o))
5.     elseif typ == "table" then
6.         io.write("{\n")
7.         local hash = {}
8.         -- 遍历列表并进行hash记录
9.         for i, v in ipairs(o) do
10.             serialize(v)
11.             io.write(",")
12.             hash[i] = true
13.         end
14.         _ = (#hash ~= 0) and io.write("\n") or nil
15.         -- 遍历除列表之外的所有元素
16.         for k, v in pairs(o) do
17.             if type(k) == "string" and string.match(k, "[%a_]+[%w_]*") then
18.                 io.write(" ", k, " = ")
19.             elseif hash[k] == true then
20.                 goto continue
21.                 -- do nothing
22.             else
23.                 io.write(" [")
24.                 serialize(k)
25.                 io.write("] = ")
26.             end
27.             serialize(v)
28.             io.write(",\n")
29.             ::continue::
30.         end
31.         io.write("}")
32.     else
33.         error("cannot serialize a" .. t)
34.     end
35. end
37. A = {
38.     B = {
39.         E = "dog",
40.         H = {
41.             F = "PIG",
42.             G = "goose"
43.         }
44.     },
45.     C = "apple",
46.     D = 114514,
47.     I = {1, 2, 3, {4, 5, 6}},
48.     [1] = 4,
49.     [2] = 3,
50.     [3] = 3,
51.     [5] = 4
52. }
54. serialize(A)
56. TEST = {
57.     4,
58.     3,
59.     3,
60.     [5] = 4,
61.     C = "apple",
62.     D = 114514,
63.     I = {1, 2, 3, {4, 5, 6}},
64.     B = {
65.         E = "dog",
66.         H = {
67.             G = "goose",
68.             F = "PIG"
69.         }
70.     }
71. }
73. [[
74. {
75. 4,3,3,
76. [5] = 4,
77. C = "apple",
78. D = 114514,
79. I = {
80. 1,2,3,{
81. 4,5,6,
82. },
83. },
84. B = {
85. E = "dog",
86. H = {
87. G = "goose",
88. F = "PIG",
89. },
90. },
91. }
92. ]]

复制代码

16.1

通常，在加载代码段时增加一些前缀很有用。该函数类似于函数load，不过会将第一个参数增加到待加载的代码段之前。
像原始的load函数一样，函数loadwithprefix应该既可以接收字符串形式的代码段，也可以通过函数进行读取。即使待加载的代码段是字符串形式的，函数loadwithprefix也不应该进行实际的字符串连接操作。相反，它应该调用函数load并传入一个恰当的读取函数来实现功能，这个读取函数首先返回要增加的代码，然后返回原始的代码段。

1. function loadWithPrefix(s, f)
2.     local tmp = 1
3.     return load(function()
4.         if tmp == 1 then
5.             tmp = 2
6.             return s
7.         elseif tmp == 2 then
8.             if type(f) == "string" then
9.                 tmp = 3
10.                 return f
11.             elseif type(f) == "function" then
12.                 return f()
13.             end
14.         else
15.             return nil
16.         end
17.     end)
18. end
20. f = loadWithPrefix("local x = 100;", "print(x)")
21. f()
23. f = loadWithPrefix("local x = 100;", io.lines('load.txt', '*L'))
24. f()

复制代码

16.2 ⭐

请编写一个函数mulitiload，该函数接收一组字符串或函数来生成函数。其他规则与16.1类似。

[code]function multiLoad(...)    local t = {...}    local i = 1    return load(function()        ::continue::        if i