锐客网

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 - 实现单链表及链表操作】



    链表 lua