跳转到内容

BlitzMax/模块/数据结构/链表

Add links
来自维基教科书，开放的书籍，面向开放的世界

链表允许您有效地向对象集合中添加和删除对象。

要创建链表，请使用 CreateList 函数。

使用 ListAddFirst 或 ListAddLast 将对象添加到链表中。这两个函数都返回一个链接对象，该对象可用于稍后使用 RemoveLink 函数删除该对象。您也可以使用 ListRemove 函数删除对象。但是，这不像使用 RemoveLink 那样高效，因为列表必须先搜索要删除的对象。

要访问链表中的所有对象，您可以使用 EachIn 循环。

列表与数组

[编辑 | 编辑源代码]

重要的是要记住，链表中的基于索引的访问速度相对较慢。对于您想要索引的每个项目，链表必须遍历其内部链接，直到找到请求的索引，而数组可以直接访问任何位置的任何值。

您可能会问：“那么为什么要使用链表呢？” 将值插入到数组的中间是一个“昂贵”的操作，您必须将插入位置之后的所有项目在数组中向下移动一位，然后在创建的空间中插入新值。在链表中，您只需重定向链接之间的指针，您就可以立即将值插入到列表的中间。

通常最好在您需要对数据进行许多更改时使用链表，而在您需要频繁地随机访问数据时使用数组。如果您需要对数组进行许多插入和删除操作，您可以使用 ListFromArray 将其转换为列表，然后使用 ListToArray 将编辑后的列表转换回数组。

类型

[编辑 | 编辑源代码]
[编辑 | 编辑源代码]

TList 使用的链接对象

方法
  • 值
  • NextLink
  • PrevLink
  • 移除

TLink：方法

[编辑 | 编辑源代码]
值

方法 Value:Object()

描述：返回与该链接关联的对象。

示例: 

' value.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FindLink("Item 2")

Print String(link.Value())
NextLink

方法 NextLink:TLink()

描述：返回列表中的下一个链接。

示例: 

' nextlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FindLink("Item 2")

Print String(link.NextLink().Value())
PrevLink

方法 PrevLink:TLink()

描述：返回列表中的上一个链接。

示例: 

' prevlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FindLink("Item 2")

Print String(link.PrevLink().Value())
移除

方法 Remove()

描述：从列表中删除链接。

TListEnum

[编辑 | 编辑源代码]

TList 使用的枚举器对象，用于实现 Eachin 支持。

TList

[编辑 | 编辑源代码]

链表

方法
  • 清空
  • IsEmpty
  • 包含
  • AddFirst
  • AddLast
  • 第一
  • 最后
  • RemoveFirst
  • RemoveLast
  • FirstLink
  • LastLink
  • InsertBeforeLink
  • InsertAfterLink
  • FindLink
  • ValueAtIndex
  • 计数
  • 移除
  • 交换
  • 复制
  • 反转
  • Reversed
  • 排序
  • ToArray
函数
  • FromArray

TList：方法

[编辑 | 编辑源代码]
清空

方法 Clear()

描述：清空链表

信息：从 list 中删除所有对象。

IsEmpty

方法 IsEmpty()

描述：检查列表是否为空

返回：如果列表为空，则返回 True，否则返回 False

包含

方法 Contains( value:Object )

描述：检查列表是否包含某个值

返回：如果列表包含 value，则返回 True，否则返回 False

AddFirst

方法 AddFirst:TLink( value:Object )

描述：将对象添加到列表的开头

返回：一个链接对象

AddLast

方法 AddLast:TLink( value:Object )

描述：将对象添加到列表的末尾

返回：一个链接对象

第一

方法 First:Object()

描述：返回列表中的第一个对象

信息：如果列表为空，则返回 Null。

示例: 

' first.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Print String(list.First())
最后

方法 Last:Object()

描述：返回列表中的最后一个对象

信息：如果列表为空，则返回 Null。

示例: 

' last.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Print String(list.Last())
RemoveFirst

方法 RemoveFirst:Object()

描述：删除并返回列表中的第一个对象。

信息：如果列表为空，则返回 Null。

示例: 

' removefirst.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

list.RemoveFirst()

Local item:Object
For item = EachIn list
	Print String(item)
Next
RemoveLast

方法 RemoveLast:Object()

描述：删除并返回列表中的最后一个对象。

信息：如果列表为空，则返回 Null。

示例: 

' removelast.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

list.RemoveLast()

Local item:Object
For item = EachIn list
	Print String(item)
Next
FirstLink

方法 FirstLink:TLink()

描述：返回列表中的第一个链接，如果列表为空，则返回 null。

示例: 

' firstlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.FirstLink()

Print String(link.Value())
LastLink

方法 LastLink:TLink()

描述：返回列表中的最后一个链接，如果列表为空，则返回 null。

示例: 

' lastlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local link:TLink = list.LastLink()

Print String(link.Value())
InsertBeforeLink

方法 InsertBeforeLink:TLink( value:Object,succ:TLink )

描述：在指定的列表链接之前插入一个对象。

评论：此方法不检查给定的链接是否为空（可能会导致编译器错误）。

InsertAfterLink

方法 InsertAfterLink:TLink( value:Object,pred:TLink )

描述：在指定的列表链接之后插入一个对象。

评论：此方法不检查给定的链接是否为空（可能会导致编译器错误）。

示例: 

' insertafterlink.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")
list.AddLast("Item 4")

list.Remove("Item 3")
Local link:TLink = list.FindLink("Item 2")
If link <> Null Then list.InsertAfterLink("New Item 3!", link)

Local item:Object
For item = EachIn list
	Print String(item)
Next
FindLink

方法 FindLink:TLink( value:Object )

描述：返回列表中具有给定值的第一个链接，如果未找到，则返回 null。

ValueAtIndex

方法 ValueAtIndex:Object( index )

描述：返回给定索引处的链接的值。

信息：如果索引超出范围，则抛出异常（必须为 0..list.Count()-1 包含）。

示例: 

' valueatindex.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Print String(list.ValueAtIndex(1))
计数

方法 Count()

描述：计算列表长度

返回： list 中的对象数量。

移除

方法 Remove( value:Object )

描述：从链表中删除对象

信息：Remove 在列表中扫描指定的值并删除其链接。

交换

方法 Swap( list:TList )

描述：与指定的列表交换内容。

复制

方法 Copy:TList()

描述：创建列表的完全相同副本。

示例: 

' copy.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local clone:TList = list.Copy()

Local item:Object
For item = EachIn clone
	Print String(item)
Next
反转

方法 Reverse()

描述：反转列表的顺序。

Reversed

方法 Reversed:TList()

描述：创建一个新列表，它是此列表的反转版本。

示例: 

' reversed.bmx

Local list:TList = New TList

list.AddLast("Item 1")
list.AddLast("Item 2")
list.AddLast("Item 3")

Local reversed:TList = list.Reversed()

Local item:Object
For item = EachIn reversed
	Print String(item)
Next
排序

方法 Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )

描述：以升序（默认）或降序排序列表。

信息：用户类型应该实现一个 Compare 方法才能进行排序。

ToArray

方法 ToArray:Object[]()

描述：将列表转换为数组

返回：一个对象数组

TList：函数

[编辑 | 编辑源代码]
FromArray

函数 FromArray:TList( arr:Object[] )

描述：从数组创建列表

返回：一个新的链表

函数

[编辑 | 编辑源代码]

CreateList

[编辑 | 编辑源代码]

Function CreateList:TList()

描述: 创建一个链表

返回: 一个新的链表对象

示例: 

' createlist.bmx

' create a list to hold some objects

list:TList=CreateList()

' add some string objects to the list

ListAddLast list,"one"
ListAddLast list,"two"
ListAddLast list,"three"

' enumerate all the strings in the list

For a$=EachIn list
	Print a$
Next

ClearList

[编辑 | 编辑源代码]

Function ClearList( list:TList )

描述：清空链表

信息：从 list 中删除所有对象。

示例: 

' clearlist.bmx

Local list:TList = CreateList()

ListAddFirst(list, "Item 1")
ListAddFirst(list, "Item 2")

ClearList(list)

Local item:Object
For item = EachIn list
	Print String(item)
Next

CountList

[编辑 | 编辑源代码]

Function CountList( list:TList )

描述：计算列表长度

返回： list 中的对象数量。

注释: 请注意，此函数会遍历列表中的每个对象，这在频繁调用或列表很大时可能会很慢。

示例: 

' countlist.bmx

Local list:TList = CreateList()

ListAddFirst(list, "Item 1")
ListAddFirst(list, "Item 2")

Print CountList(list)

ListIsEmpty

[编辑 | 编辑源代码]

Function ListIsEmpty( list:TList )

描述：检查列表是否为空

返回：如果列表为空，则返回 True，否则返回 False

示例: 

' listisempty.bmx

Local list:TList = CreateList()

Print ListIsEmpty(list)

ListAddFirst(list, "Item 1")

Print ListIsEmpty(list)

ListContains

[编辑 | 编辑源代码]

Function ListContains( list:TList,value:Object )

描述：检查列表是否包含某个值

返回：如果列表包含 value，则返回 True，否则返回 False

示例: 

' listcontains.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")

Print ListContains(list, "Item 2")
Print ListContains(list, "Item 3")

SortList

[编辑 | 编辑源代码]

Function SortList( list:TList,ascending=True,compareFunc( o1:Object,o2:Object )

描述: 对列表进行排序

注释: 可选的 ascending 和 compareFunc 允许修改默认排序方法。

示例: 

' sortlist.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 3")
ListAddLast(list, "Item 1")
ListAddLast(list, "Item 4")
ListAddLast(list, "Item 2")

SortList(list)

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListFromArray

[编辑 | 编辑源代码]

Function ListFromArray:TList( arr:Object[] )

描述：从数组创建列表

返回：一个新的链表

示例: 

' listfromarray.bmx

Local array:String[] = ["Item 1", "Item 2", "Item 3"]

Local list:TList = ListFromArray(array)

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListToArray

[编辑 | 编辑源代码]

Function ListToArray:Object[]( list:TList )

描述：将列表转换为数组

返回：一个对象数组

示例: 

' listtoarray.bmx

Local array:Object[]
Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")

array = ListToArray(list)

Local index:Int
For index = 0 To array.Length - 1
	Print String(array[index])
Next

SwapLists

[编辑 | 编辑源代码]

Function SwapLists( list_x:TList,list_y:TList )

描述: 交换两个列表的内容

示例: 

' swaplists.bmx

Local list:TList = ListFromArray(["Item 1", "Item 2", "Item 3"])
Local list2:TList = ListFromArray(["Item A", "Item B", "Item C"])

SwapLists(list, list2)

Local item:Object
For item = EachIn list
	Print String(item)
Next

For item = EachIn list2
	Print String(item)
Next

ReverseList

[编辑 | 编辑源代码]

Function ReverseList( list:TList )

描述: 反转列表元素的顺序

示例: 

' reverselist.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")

ReverseList(list)

Local item:Object
For item = EachIn list
	Print String(item)
Next
[编辑 | 编辑源代码]

Function ListFindLink:TLink( list:TList,value:Object )

描述: 在列表中查找链接

返回: 包含 value 的链接

注释: 如果未找到值，则返回 Null。

ListAddLast

[编辑 | 编辑源代码]

Function ListAddLast:TLink( list:TList,value:Object )

描述: 将一个对象添加到链表

返回：一个链接对象

示例: 

' listaddlast.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListAddFirst

[编辑 | 编辑源代码]

Function ListAddFirst:TLink( list:TList,value:Object )

描述: 将一个对象添加到链表

返回：一个链接对象

示例: 

' listaddfirst.bmx

Local list:TList = CreateList()

ListAddFirst(list, "Item 1")
ListAddFirst(list, "Item 2")

Local item:Object
For item = EachIn list
	Print String(item)
Next

ListRemove

[编辑 | 编辑源代码]

Function ListRemove( list:TList,value:Object )

描述：从链表中删除对象

信息: ListRemove 在列表中扫描指定的值并删除其链接。

注释: 这只删除该值的第一个实例。

示例: 

' listremove.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")
ListAddLast(list, "Item 2")

ListRemove(list, "Item 2") ' remove an object

Local item:Object
For item = EachIn list
	Print String(item)
Next
[编辑 | 编辑源代码]

Function RemoveLink( link:TLink )

描述：从链表中删除对象

信息: RemoveLink 比 ListRemove 更有效。

示例: 

' removelink.bmx

Local list:TList = CreateList()

ListAddLast(list, "Item 1")
ListAddLast(list, "Item 2")
ListAddLast(list, "Item 3")

Local link:TLink = ListFindLink(list, "Item 2") ' find a link
If link <> Null Then RemoveLink(link) ' remove it

Local item:Object
For item = EachIn list
	Print String(item)
Next
取自 "https://wikibooks.cn/w/index.php?title=BlitzMax/Modules/Data_structures/Linked_lists&oldid=2063446"
华夏公益教科书