Python高效编程大数据 爬虫Python AI Sql

Nim 语言实现单链表

2019-10-31  本文已影响0人  Python高效编程

这一节,我们来介绍单链表这种数据结构。

简介

单链表是一种逻辑上连续,而在内存存储位置不连续的线性结构。使用单链表,在插入和删除已知节点时,可以以 O(1) 的时间复杂度完成。

单链表由一个个节点组成,每个节点包含当前元素,以及下一个节点的位置信息。就和网页上的连接类似,一个页面不仅有当前信息,还包含下一个网页的连接信息。通过指针或者引用,我们就可以像浏览网页那样,过渡到下一个节点。

Nim 语言简介

我们使用 Nim 语言实现系列数据结构。Nim 语言是一种高效而优雅的系统级编程语言,具体介绍可以查看 Nim 语言官网。

https://nim-lang.org/
Nim 中文社区
https://nim-cn.com/

单链表的基本结构

首先创建单个节点,每个节点保存当前信息,以及下一个节点的位置信息。在 Nim语言中 ref 相当于指针或者引用, 我们使用 type 声明类型,星号表明该函数可以被其他模块访问。T 是 Nim 中的泛型,代表这个函数可以支持任意合理的类型,比如 int, float 等类型。object 就和面向对象语言的类差不多,可以继承。

value 代表当前元素的信息,next 指向下一个节点。

# 微信公众号 Nim 编程
type
  SinglyNodeObj*[T] = object
    value*: T
    next*: ref SinglyNodeObj[T]
  SinglyNode*[T] = ref SinglyNodeObj[T]

下面让我们定义一个单链表,单链表有两个属性,node 表示单链表保存的节点信息,而 lastNode 则表示指向单链表的尾部。定义一个 lastNode 属性,可以让我们以 O(1) 的时间复杂度在单链表尾部插入节点。

type
  SinglyList*[T] = ref object
    node*: SinglyNode[T]
    lastNode*: SinglyNode[T]

定义函数

我们刚才定义了单链表的底层数据表示,接下来让我们定义操作这些数据的函数。

首先我们希望创建一个空的节点,因为 result 是 ref 类型,所以我们需要先给它分配内存,只需 new 一下就行了。Nim 会自动初始化,假设 elem 是 int 类型,value 就被初始化为 0,而 next 则被初始化为 nil。

显然创建一个空节点,我们只需给 result 的 value 属性赋值即可。

proc newSinglyNode*[T](elem: T): SinglyNode[T] = 
  new(result)
  result.value = elem

下一步,我们需要创建一个单链表,类似的分配变量。我们首先创建一个首节点,这个节点和后续节点有些不同。在逻辑上,我们不考虑该节点的 value 属性,只保存下一个节点的信息,和 lastNode 类似,起到哨兵作用。之后,我们让 lastNode 指向头部节点。到此为止,一个空的单链表就创建完成了。

proc newSinglyList*[T](): SinglyList[T] = 
  new(result)
  result.node = SinglyNode[T](next:nil)
  result.lastNode = result.node

接下来,我们看头部插入节点。我们新建节点 node,让 node 节点的 next 属性指向第一个节点,接着再让头部节点的 next 属性指向新建节点。

proc prepend*[T](list: SinglyList[T], elem: T) = 
  var 
    p = list.node
    node = newSinglyNode(elem=elem)
  node.next = p.next
  p.next = node

然后,我们在尾部插入节点,也比较容易。新建节点 node,让尾部节点的 next 属性指向 node,接着让 lastNode 节点指向 node。

proc insert*[T](list: SinglyList[T], elem: T) =
  var 
    p = list.lastNode
    node = newSinglyNode(elem=elem)
  p.next = node
  list.lastNode = p.next

在单链表插入指定节点。首先我们查找指定元素对应的个节点,接着在该节点的后面插入新节点。

proc find*[T](list: SinglyList[T], elem: T): SinglyNode[T] = 
  result = list.node
  while (result != nil) and (result.value != elem):
    result = result.next

proc insert*[T](list: SinglyList[T], pos: SinglyNode[T], elem: T) =
  if pos.isLast:
    list.insert(elem)
  var p = new SinglyNode[T]
  p.value = elem
  p.next = pos.next
  pos.next = p

删除单链表出现的第一个指定元素。

proc delete*[T](list: SinglyList[T], elem: T) = 
  var p = findPrevious[T](list, elem)
  if p == nil: return
  if p.next.isLast:
    list.lastNode = p
    p.next = nil
  if not p.isLast:
    p.next = p.next.next

打印节点信息。

proc `$`[T](list: SinglyList[T]): string = 
  while list.isEmpty:
    return "empty"
  var p = list.node.next
  while p != nil:
    result &=  $p.value & "->" 
    p = p.next 
  result &= "tail"

迭代节点元素。

iterator items*[T](list: SinglyList[T]): T = 
  var p = list.node.next
  while p.next != nil:
    yield p.value
    p = p.next
    
iterator pairs*[T](list: SinglyList[T]): tuple[idx: int, value: T] = 
  var 
    p = list.node.next
    idx = 0
  while p.next != nil:
    yield (idx, p.value)
    p = p.next    

示例

when isMainModule:
  let a = newSinglyList[int]()
  a.insert(12)
  a.insert(8)
  a.insert(17)
  a.insert(12)
  a.insert(8)
  a.prepend(9)
  a.insert(17)
  let t1 = a.find(17)
  a.insert(t1, 99)
  a.prepend(87)
  a.delete(8)
  a.delete(12)
  echo a
# output 87->9->17->99->12->8->17->tail

欢迎关注# 微信公众号 Nim 编程, Nim 中文社区官网 https://nim-cn.com/

上一篇 下一篇

猜你喜欢

热点阅读