数据结构 链表的lua实现 仿照C++中list 实现

write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie

vector我就没有用lua实现了，实现个list就很别扭了。事实上太仿照C++标准库的list了，所以可能没有很好的发挥lua的特点，有点要说的就是，lua中table的赋值都是引用赋值的浅拷贝，这点在实现list的时候发挥了关键作用，不然没有指针的lua要实现一个列表都成为不可能了：）

程序最后还附加了一个符合lua迭代器特点的迭代器，不然老是用CListIterator的话，可能都会怀疑自己用的还是不是lua了，呵呵

?这里想提出的一点就是lua中实在是没有一个可用的debug工具，注意我的措辞，是连一个可用的都没有，更别提好用的了。相对而言C++有VS+gdb,python用pydb，bash有bashdb,而lua什么都没有！lua for windows的那个scite别提多不好用了，clidebug,xdblua,RemDebug等等我都用过，甚至官网提到的几个IDE我都试用了一下，通通的不能用，可能是因为lua升级了的原因（记得scite在原来是可用的），郁闷死我了。作为一个两百多行的list代码，没有一个可用的调试工具，简直就是噩梦（也许没有那么夸张，但是的确浪费了我很多本来简单调试就可以发下你的问题），唉。。。。。在没有好用的lua调试工具之前，我甚至都有点不想给自己找罪受了。再也不写太多的lua代码了。最多在小程序中用print和assert勉强写写吧。其实感觉lua本身对于调试的支持是很到位的了，为什么却没有好用的工具呢？唉。。。。。。。。。。这就是普及的好处了。。。。。真有时间，哥们自己DIY一个用用算了。

-----在对lua的调试工具不再抱希望的时候，调整了一下lua的PATH设置，随便折腾了一下scite,结果又可以正常调试了，faint.............有的时候就是这么莫名奇妙，我折腾了3天（准确的是3天的晚上），试了n种工具，结果都有问题，结果今天莫名奇妙就好了，谁说的来着，你编的认为已经没有bug的软件总会在某一天莫名崩溃。。。。这一点在工作以来我是深有体会了，问题是，某个有bug，已经不能正常运行的软件怎么在某一天莫名的好了呢？。。。。呵呵。

总之，还是对lua的调试工具不满，起码，没有能够让我能用putty挂在linux下好好调试的工具：）总不能每次在那边写完都考回来在windows下调试吧？。。。（现在好像也只能这样了）

?

??1 #!/usr/bin/env lua
??2
??3 -- require "std"
??4
??5 -- Node prototype
??6 CNode = {}
??7 function?CNode:New(data,prev,next)
??8 ????local?o = {}
??9 ????o.data = data
?10 ????o.prev = prev
?11 ????o.next?= next
?12 ????o.type?= "CNode"
?13 ????setmetatable(o,self)
?14 ????self.__index = self
?15 ????return?o
?16 end
?17
?18 -- iterator of list prototype like in C++
?19 CListIterator = {}
?20 function?CListIterator:New(a)
?21 ????assert(a ~= nil?and?
?22 ????type(a) == "table"??23 ????a.type?~= nil?and
?24 ????((a.type?== "CList") or?(a.type?== "CNode")),
?25 ????"Argument to new a CListIterator must be a CList object or a CNode object")
?26 ????
?27 ?????28 ????-- give it a type name
?29 ????o.type?= "CListIterator"
?30
?31 ????-- if a is a CList object then create a begin iterator for the object
?32 ????-- if a is a CNode object then return a iterator point to the node
?33 ????if?a.type?== "CList"?then
?34 ????????o.pos = a.head.next
?35 ????elseif?a.type?== "CNode"??36 ????????o.pos = a
?37 ????end
?38
?39 ????setmetatable(o,64);">?40 ????self.__index = self
?41 ?????42 end
?43
?44 function?CListIterator:IsEnd()
?45 ????return?not?self.pos.data
?46 end
?47
?48 function?CListIterator:Cur()
?49 ????return?self.pos
?50 end
?51
?52 function?CListIterator:MoveNext()
?53 ????self.pos = self.pos.next
?54 ????return?self
?55 end
?56
?57 function?CListIterator:MovePrev()
?58 ????self.pos = self.pos.prev
?59 ?????60 end
?61
?62 -- List prototype
?63 CList = {}
?64 function?CList:CreateIterator()
?65 ????return?CListIterator:New(self)
?66 end
?67
?68 function?CList:New()
?69 ?????70 ????o.head = CNode:New()
?71 ????o.head.prev = o.head
?72 ????o.head.next?= o.head
?73
?74 ????-- give it a type def
?75 ????o.type?= "CList"
?76 ????setmetatable(o,64);">?77 ????self.__index = self
?78 ?????79 end
?80
?81 function?CList:Insert(it,data)
?82 ????assert(it ~= nil,"Must pointer where to Insert")
?83 ????assert(type(it) == "table","Fisrt Argument must be a CListIterator(now it even not a table)")
?84 ????assert(type?~= nil,"Fisrt Argument must be a CListIterator(now it.type == nil)")
?85 ????assert(it.type?== "CListIterator","Fisrt Argument must be a CListIterator")
?86
?87 ????local?iter = CListIterator:New(self)
?88 ????local?node = CNode:New(data,it.pos.prev,it.pos)
?89 ????it.pos.prev.next?= node
?90 ????it.pos.prev = node
?91 ????return?CListIterator:New(node)
?92 end
?93
?94 function?CList:Begin()
?95 ????return?self:CreateIterator()
?96 end
?97
?98 function?CList:End()
?99 ????return?CListIterator:New(self.head)
100 end
101
102
103 function?CList:PushFront(data)
104 ????self:Insert(self:Begin(),64);">105 end
106
107 function?CList:PushBack(data)
108 ????self:Insert(self:End(),64);">109 end
110
111 function?CList:IsEmpty()
112 ????return?self:Begin().pos == self:End().pos
113 end
114
115 function?CList:Erase(it)
116 ????assert(not?it.data,"you can't erase the head")
117 ????it.pos.prev.next?= it.pos.next
118 ????it.pos.next.prev = it.pos.prev
119 ????it = nil
120 end
121
122 function?CList:PopFront()
123 ????assert(not?self:IsEmpty(),"Can't PopFront to a Empty list")
124 ????self:Erase(self:Begin())
125 end
126
127 function?CList:PopBack()
128 ????assert("Can't PopBack to a Empty list")
129 ????self:Erase(self:End():MovePrev())
130 end
131
132 function?CList:Clear()
133 ????while?not?self:IsEmpty() do
134 ????????self:Erase(self:Begin())
135 ????136 end
137
138 -- redefine global print to support the CList
139 p = _G.print
140 function?print(o)
141 ????if?o ~= nil?and?type(o) == "table"?142 ????????o.type?~= nil?and?o.type?== "CList"?143 ????????-- iterate like in C++ using CList and CListIterator feature
144 ????????local?it = o:CreateIterator()
145 ????????not?it:IsEnd() 146 ????????????io.write(it:Cur().data)
147 ????????????io.write(" ")
148 ????????????it:MoveNext()
149 ????????150 ????????io.write("/n")
151 ????else
152 ????????p(o)
153 ????154 end
155
156 -- test PushFront
157 print("/ntest: test PushFront and PopFront")
158 newlist = CList:New()
159 newlist:PushFront(10)
160 print(newlist)
161 newlist:PushFront(20)
162 print(newlist)
163 newlist:PushFront(30)
164 print(newlist)
165 newlist:PopFront()
166 print(newlist)
167 it = newlist:CreateIterator()
168 newlist:Erase(it)
169 print(newlist)
170 newlist:Clear()
171 print(newlist)
172
173
174 -- test PushBack
175 print("/ntest: test PushBack and popBack")
176 newlist = CList:New()
177 newlist:PushBack(10)
178 print(newlist)
179 newlist:PushBack(20)
180 print(newlist)
181 newlist:PushBack(30)
182 print(newlist)
183 newlist:PopBack()
184 print(newlist)
185 newlist:PopFront()
186 print(newlist)
187
188
189 -- test: insert at begin
190 print("/ntest: insert at begin ")
191 newlist = CList:New()
192 it = newlist:CreateIterator()
193 iter = newlist:Insert(it,10);
194 io.write("cur iterator:"?..??tostring(it.pos.data) .. " return iterator:"?.. tostring(iter.pos.data) .. "/n")
195 print(newlist)
196 iter = newlist:Insert(it,20);
197 io.write("cur iterator:"?..??tostring(it.pos.data) .. " return iterator:"?.. tostring(iter.pos.data) .. "/n")
198 print(newlist)
199 iter = newlist:Insert(it,30);
200 io.write("cur iterator:"?..??tostring(it.pos.data) .. " return iterator:"?.. tostring(iter.pos.data) .. "/n")
201 print(newlist)
202
203 -- test: insert at back
204 print("/ntest: insert at back")
205 newlist = CList:New()
206 it = newlist:CreateIterator()
207 it = newlist:Insert(it,64);">208 io.write("cur iterator:"?..??tostring(it.pos.data).."/n")
209 it = newlist:Insert(it,64);">210 io.write("cur iterator:"?..??tostring(it.pos.data).."/n")
211 it = newlist:Insert(it,64);">212 io.write("cur iterator:"?..??tostring(it.pos.data).."/n")
213 print(newlist)
214
215 -- iterate like in C++
216 print("/niterate like in C++")
217 it = newlist:CreateIterator()
218 while?219 ????io.write(it:Cur().data .. " ")
220 ????it:MoveNext()
221 end
222 print("/n")
223
224 -- closure list iterator to iterate
225 print("/nclosure list iterator to iterate")
226 function?list_iter(list)
227 ????local?cur = list.head
228 ????return?function()
229 ????????if?cur.next.data ~= nil?then?
230 ????????????cur = cur.next
231 ????????????return?cur.data
232 ????????????233 ????????end
234 end
235
236 for?v in?list_iter(newlist) do?
237 ????io.write(v .. " ")
238 end
239
240