练习14.9
- 练习 14.1：请编写一个函数，该函数用于两个稀疏矩阵相加。
首先，由于表并不对边界作限制，所以不能验证两个矩阵是否可以相加，我们默认认为可以相加。矩阵相加比较简单，只需要创建第三个表，然后分别把两个表里面的键值对加到第三个表里面去就可以了。
---@return table
---@param a table a = {{}, {}, {}}
---@param b table b = {{}, {}, {}}
function MatrixAdd(a, b)
local res = {}
for k, v in pairs(a) do --找到不为空的表 k 就是矩阵行号 v 是矩阵的一列
local tempTable = {}
for i, j in pairs(v) do --在一列中寻找不为空的元素， 最终元素的位置是 a[k][i] = j
tempTable[i] = j
end
res[k] = tempTable
end
for k, v in pairs(b) do
if res[k] then --首先应该查看对应的列存不存在，如果不存在就新建一个列，如果存在则查看对应的位置是否有值
for i, j in pairs(v) do
if res[k][i] then
res[k][i] = res[k][i] + j
else
res[k][i] = j
end
end
else
local tempTable = {}
for i, j in pairs(v) do
tempTable[i] = j
end
res[k] = tempTable
end
end
return res
end
local ta = {{1,2}, {3, 4}}
local tb = {{3,4}, {1, 2}}
local tc = {}
tc = MatrixAdd(ta, tb)
for _, v in pairs(tc) do
for _, j in pairs(v) do
io.write(j .. " ")
end
io.write("\n")
end
- 练习 14.2：改写示例 14.2 中队列的实现，使得当队列为空时两个索引都返回0。
DoubleEndedQueue = {
list = {first = 0, last = 0},
pushFirst = function(self, v)
if(self.list.first == 0) then
self.list.first = 1
self.list[self.list.first] = v
else
self.list.first = self.list.first + 1
self.list[self.list.first] = v
end
end,
pushLast = function(self, v)
if(self.list.last == 0) then
self.list.last = -1
self.list[self.list.last] = v
else
self.list.last = self.list.last - 1
self.list[self.list.last] = v
end
end,
popFirst = function(self)
if(self.list.first == 0) then
error("stack overflow",2)
else
local temp = self.list[self.list.first]
self.list[self.list.first] = nil
self.list.first = self.list.first - 1
return temp
end
end,
popLast = function(self)
if(self.list.last == 0) then
error("stack overflow", 2)
else
local temp = self.list[self.list.last]
self.list[self.list.last] = nil
self.list.last = self.list.last + 1
return temp
end
end
}
function DoubleEndedQueue:new(o)
o = o or {}
self.__index = self
setmetatable(o, self)
return o
end
local deq = DoubleEndedQueue:new()
deq:pushFirst(1)
deq:pushFirst(2)
deq:pushLast(3)
deq:pushLast(4)
print(deq:popFirst()) --> 2
print(deq:popFirst()) --> 1
print(deq:popLast()) --> 4
print(deq:popLast()) --> 3
- 练习 14.3：修改图所用的数据结构，使得图可以保存每条边的标签。该数据结构应该使用包括两个字段的对象来表示每一条边，即边的标签和边指向的节点。与邻接集合不同，每一个节点保存的是从当前节点出发的边的集合。
修改函数readgraph，使得该函数从输入文件中按行读取，每行由两个节点的名称外加边的标签组成。
不打算写
- 练习 14.4：假设图使用上一个练习的表示方式，其中边的标签代表两个终端节点之间的距离。请编写一个函数，使用 Dijkstra 算法寻找两个指定节点之间的最短路径。
不打算写
