lua之链表的实现

  1 -- lua链表的实现
  2 
  3 node = {}
  4 list = node
  5 
  6 --初始化，构建一个空表
  7 function init()
  8     list.data = 0 --我将头结点的数据域存放链表的长度，以免浪费空间
  9     list.next = nil
 10 end
 11 
 12 --向链表的尾部添加数据
 13 function addRear(d)
 14     node.next={}--建立一个节点，相当于malloc一个节点
 15     node = node.next
 16     node.next = nil
 17     node.data = d
 18     list.data = list.data + 1 -- 长度加1
 19 end
 20 
 21 --向链表的头部添加数据
 22 function addHead(d)
 23     newNode = {}--建立一个节点，相当于malloc一个节点
 24     newNode.data = d
 25     newNode.next = list.next
 26     list.next = newNode
 27     list.data = list.data + 1
 28 end
 29 
 30 
 31 --第i个位置 插入数据d   i>=1
 32 function insert(i,d)
 33     if i<1 then
 34         print(‘插入位置不合法‘)
 35         return
 36     end
 37 
 38     local j, k, l = i-1, 0, list
 39     -- 解决问题的核心是找到第j个位置
 40     while k<j do
 41         k=k+1
 42         l = l.next
 43         if not l.next then break end
 44     end
 45     if k ~= j then
 46         print(‘插入位置不合法‘)
 47         return
 48     end
 49 
 50     --开始插入
 51     newNode = {}
 52     newNode.next = l.next
 53     newNode.data = d
 54     l.next = newNode
 55     list.data = list.data + 1
 56 end
 57 
 58 
 59 --删除第i个位置的数据  i>=1，返回删除的数据的内容
 60 function del(i)
 61     if i<1 then
 62         print(‘删除位置不合法‘)
 63         return
 64     end
 65     local j, k ,l= i-1, 0,list
 66     while k<j do
 67         k=k+1
 68         l = l.next
 69         if not l.next then
 70             print(‘删除位置不合法‘)
 71             return
 72         end
 73     end
 74 
 75     d = l.next.data
 76     t = l.next.next -- 保存删除节点之后的链表内容
 77     l.next = nil --lua中让它等于nil就删除了
 78     l.next = t
 79     list.data = list.data - 1 -- 链表长度减1
 80     return d
 81 end
 82 
 83 
 84 --清除链表，操作完成后，链表还在，只不过为空
 85 function clear()
 86     if not list then -- 先判断链表是否还存在
 87         print(‘链表不存在‘)
 88     end
 89 
 90     while true do
 91         firstNode = list.next
 92         if not firstNode then -- 表示链表成为空表了
 93             break
 94         end
 95         t = firstNode.next -- 保存第一个节点之后的链表
 96         list.next = nil -- 删除
 97         list.next = t
 98     end
 99     list.data = 0 -- 将长度置0
100     print(‘-- clear ok --‘)
101 end
102 
103 -- 销毁链表
104 function destroy()
105     clear() -- 先清除链表
106     list = nil
107 end
108 
109 --获取list中的第i个元素 i>=1
110 function getData(i)
111     if not list then
112         print(‘链表不存在‘)
113         return
114     end
115     if i<1 then
116         print(‘位置不合法‘)
117         return
118     end
119 
120     local l = list.next -- l 指向第一个元素
121     local k = 1
122     while l do
123         l = l.next
124         k = k+1
125         if k == i then
126             return l.data
127         end
128     end
129 
130     print(‘位置不合法‘)
131 end
132 
133 --获取链表的长度
134 function getLen()
135     if not list then
136         print(‘链表不存在‘)
137         return
138     end
139     return list.data
140 end
141 
142 --打印链表的每一个元素
143 function display()
144     local l=list.next
145     while l do
146         print(l.data)
147         l = l.next
148     end
149     print(‘-- display ok --‘)
150 end
151 
152 --主方法
153 function main()
154     init() -- 初始化链表
155     addRear(5)
156     addRear(7)
157     addRear(10)
158     addHead(1) --向头部添加
159     addRear(20) --向尾部添加
160     insert(1,3) --在第1个位置插入3
161     insert(3,100) -- 在第三个位置插入100
162     display() -- 打印链表的每一个元素
163     print(‘请输入要删除的位置：‘)
164     pos = io.read(‘*number‘)
165     ret = del(pos)
166     if not ret then
167         print(‘删除失败‘)
168     else
169         print(‘你删除的是：‘,ret,‘\n删除后的链表内容为：‘)
170     end
171     -- 打印改变后内容
172     display()
173     --clear()
174     --display()
175 
176     i = 3
177     print(‘第‘..i..‘个元素内容是：‘,getData(i))
178     print(‘链表的的长度为：‘,getLen())
179 
180     destroy() -- 销毁链表
181     print (‘---- main ok ----‘)
182 end
183 
184 -- 程序的入口
185 main()