Linkitetty lista-kirjasto

Oletko tehnyt jotain, mistä muut voisivat hyötyä. Postita vinkit tänne.
Post Reply
User avatar
Ilmuri
Developer
Developer
Posts: 277
Joined: Sun Aug 26, 2007 2:46 pm
Location: \o

Linkitetty lista-kirjasto

Post by Ilmuri »

Code: Select all

Const NODE_PREV = 4
Const NODE_NEXT = 8
Const NODE_DATA = 0
Const LIST_FIRST = 0
Const LIST_LAST = 4

Function MakeList()
	Dim list As integer
	list = MakeMEMBlock(4+4)
	Return list
End Function

Function MakeNode()
	Dim node As integer
	node = MakeMEMBlock(4+4+4)
	Return node
End Function


Function SetNode(node, val)
	PokeInt node, NODE_DATA, val 
End Function

Function GetNode(node)
	Return PeekInt(node, NODE_DATA)
End Function

Function GetPrev(node)
	Return PeekInt(node, NODE_PREV)
End Function

Function GetNext(node)
	Return PeekInt(node, NODE_NEXT)
End Function


Function GetFirst(list)
	Return PeekInt(list, LIST_FIRST)
End Function

Function GetLast(list)
	Return PeekInt(list, LIST_LAST)
End Function

Function InsertNodeAfter(list, node, newNode)
	PokeInt newNode, NODE_PREV, node ' newNode.prev = node
	PokeInt newNode, NODE_NEXT, PeekInt(node, NODE_NEXT) ' newNode.Next = node.Next
	If PeekInt(node, NODE_NEXT) = 0 Then
		PokeInt list, LIST_LAST, newNode ' list.Last = newNode
	Else
		PokeInt PeekInt(node,NODE_NEXT), NODE_PREV, newNode ' node.Next.prev = newNode
	EndIf
	PokeInt node, NODE_NEXT, newNode
End Function

Function InsertNodeBefore(list, node, newNode)
	PokeInt newNode, NODE_PREV, PeekInt(node, NODE_PREV) ' newNode.prev = node.prev
	PokeInt newNode, NODE_NEXT, node ' newNode.Next = node
	If PeekInt(node, NODE_PREV) = 0 Then
		PokeInt list, LIST_FIRST, newNode ' list.First = newNode
	Else
		PokeInt PeekInt(node,NODE_PREV), NODE_NEXT, newNode ' node.prev.Next = newNode
	EndIf
	PokeInt node, NODE_PREV, newNode
End Function


Function InsertNodeFirst(list, newNode)
	If PeekInt(list, LIST_FIRST) = 0 Then
		PokeInt list, LIST_FIRST, newNode ' list.First = newNode
		PokeInt list, LIST_LAST, newNode ' list.Last = newNode
		PokeInt newNode, NODE_PREV, 0 ' node.prev = 0
		PokeInt newNode, NODE_NEXT, 0 ' node.Next = 0
	Else
		InsertNodeBefore(list, PeekInt(list, LIST_FIRST), newNode) ' (list, list.First, newNode)
	EndIf
End Function	

Function InsertNodeLast(list, newNode)
	If PeekInt(list, LIST_LAST) = 0 Then
		InsertNodeFirst(list, newNode)
	Else
		InsertNodeAfter(list, PeekInt(list, LIST_LAST), newNode) '(list,list.Last, newNode)
	EndIf
End Function


Function RemoveNode(list, node)
	If PeekInt(node,NODE_PREV)=0 Then
		PokeInt list, LIST_FIRST, PeekInt(node, NODE_NEXT) ' list.First = node.Next
	Else
		PokeInt PeekInt(node, NODE_PREV), NODE_NEXT, PeekInt(node, NODE_NEXT) ' node.prev.Next = node.Next
	EndIf
	If PeekInt(node,NODE_NEXT)=0 Then
		PokeInt list, LIST_LAST, PeekInt(node, NODE_PREV) ' list.Last = node.prev
	Else
		PokeInt PeekInt(node, NODE_NEXT), NODE_PREV, PeekInt(node, NODE_PREV) ' node.Next.Prev = node.Prev
	EndIf
	DeleteMEMBlock node
End Function


Function PurgeList(list) '!!!EI POISTA DATAA!!!
	Dim temp As integer
	Dim node As integer
	temp = PeekInt(list, LIST_FIRST)
	node = temp
	While(node<>0)
		node = PeekInt(node, NODE_NEXT)
		DeleteMEMBlock temp
		temp = node
	Wend
End Function


Function PrintList$(list, c$)
	Dim node As integer
	Dim s As String
	node = PeekInt(list, LIST_FIRST)
	Repeat
		s$= s$ + PeekInt(node, NODE_DATA) + c$
		node = PeekInt(node, NODE_NEXT)
	Until node = 0
	Return Left(s$, Len(s$)-Len(c$))
End Function
Esimerkkitoteutus kahteen suuntaan linkitetystä listasta. Käyttö on toki itsestään selvää jos suinkin tietää mitä linkitetyt listat ovat. Mallia katsottu rankalla kädellä Wikipedian Linked lists-artikkelista. =[:{-
Listan voi käydä läpi vaikka tähän malliin:

Code: Select all

node = GetFirst(list)
While node<>0
	'tee jotain nodella
	node = GetNext(node)
Wend
Edistyneemmät käyttäjät toki jättävät käyttämättä funktiomäärää tuhlaavia wräpperifunktioita alusta, mieluiten jopa poistavat ne. Niiden tarkoitushan on vain siistiä koodia.
Teen käyttöesimerkin myöhemmin ellei joku muu sellaista ehdi rustaamaan.
CoolBasic henkilökuntaa
Kehittäjä
CoolBasic Classic
Post Reply