lua|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
endfunction Linklist.checkList(list)
-- body
if not list then print("链表不存在") return end
endfunction Linklist.checkIndex(list, index)
-- body
if index < 1 or index > list.length + 1 then
print("索引越界")
return
end
endfunction 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 = https://www.it610.com/article/data
list.length = list.length+1print("尾部添加节点成功")
return node
end-- 头部添加节点
function Linklist.addHead(list, data)
-- body
Linklist.checkList(list)--修改新节点和头节点的next
local newNode = {}
newNode.data = https://www.it610.com/article/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 = https://www.it610.com/article/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 = https://www.it610.com/article/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("链表销毁成功")
endLinklist.addByIndex = Linklist.insertByIndex
Linklist.removeByIndex = Linklist.deleteByIndex
Linklist.changeDataByIndex = Linklist.modifyDataByIndexlocal 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
13
27
316
420
-- display ok --
链表反转倒置成功
120
216
37
43
-- display ok --
链表清理成功
true
链表销毁成功
=====================我是分界线==============================【lua|Lua - 实现单链表及链表操作】
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 孩子不是实现父母欲望的工具——林哈夫
- opencv|opencv C++模板匹配的简单实现
- Node.js中readline模块实现终端输入
- java中如何实现重建二叉树
- 人脸识别|【人脸识别系列】| 实现自动化妆
- paddle|动手从头实现LSTM
- pytorch|使用pytorch从头实现多层LSTM