《Learn Data Structures and Algorithms with Golang》作者：Bhagvan Kommadi

列表(Lists)

列表是元素的一个序列。每个元素带有一个向前或向后的链接，可以连接到另一个元素。元素可以包含其他额外的属性。这种数据结构是一种容器的基本类型。列表有一个可变化的长度，并且与数组相比，开发者能够移除或增加元素更加容易。在列表里的数据项在内存或磁盘上不必是连续的。链表是由Allen Newell, Cliff Shaw和Herbert A. Simon在RAND公司提出的。

首先，可以在Go语言中使用列表，正如下面例子显示的那样；在列表上调用PushBack方法可以新增元素，列表位于container/list包内：

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main
// importing fmt and container list packages
import (
  "fmt"
  "container/list"
)
// main method
func main() {
  var intList list.List
  intList.PushBack(11)
  intList.PushBack(23)
  intList.PushBack(34)
  for element := intList.Front(); element != nil; element=element.Next() {
    fmt.Println(element.Value.(int))
  }
}

通过for循环遍历这个列表，以及通过Value方法访问这些元素的值。

运行下面的命令：

go run list.go

在下一节里让我们看看元组。

元组(Tuples)

元组是一个有限且排序的元素列表。它是一个把数据分组的数据结构。元组通常是不可改变的顺序集合。元素具有不同数据类型的相关字段。唯一改变元组的方式是改变字段。操作符，例如+和*，可以适用于元组。一条数据库记录可看成一个元组。在下面的例子里，计算整数的幂级数(power series)并且将这个整数的平方和立方作为元组返回：

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main
// importing fmt package
import (
  "fmt"
)
//gets the power series of integer a and returns tuple of square of a
// and cube of a
func powerSeries(a int) (int,int) {
  return a*a, a*a*a
}

这个main方法调用powerSeries方法并传3作为参数。平方和立方值从这个方法返回：

// main method
func main() {
  var square int
  var cube int
  square, cube = powerSeries(3)
  fmt.Println("Square ", square, "Cube", cube)
}

运行下面的命令：

go run tuples.go

元组在powerSeries函数里被命名，如下面代码所示：

func powerSeries(a int) (square int, cube int) {
  square = a*a
  cube = square*a
  return
}

如果有一个错误，它可以用元组传递，如下面代码所示：

func powerSeries(a int) (int, int, error) {
  square = a*a
  cube = square*a
  return square,cube,nil
}

堆(Heaps)

堆是基于heap属性的数据结构。这种堆数据结构可以用在选择(selection)算法，图(graph)算法，k路归并(k-way merge)算法。例如操作查找，归并，插入，键改变和删除都是在堆上执行。堆是Go语言container/heap包的部分。根据堆排序(最大堆)属性，存储在每个结点上的值都要大于或等于子结点的值。

如果按降序排序，它被认为是最大堆；否则，它是最小堆。堆数据结构是由J.W.J.Williams在1964年为堆排序算法而提出的。它不是一个完全排序的数据结构，而是部分排序的。下面的例子显示了如何使用container/heap包创建一个堆数据结构：

//main package has examples shown
//in Hands-On Data Structures and algorithms with Go book
package main
// importing fmt package and container/heap
import (
  "container/heap"
  "fmt"
)
// integerHeap a type
type IntegerHeap []int
// IntegerHeap method - gets the length of integerHeap
func (iheap IntegerHeap) Len() int { 
  return len(iheap) 
}
// IntegerHeap method - checks if element of i index is less than j index
func (iheap IntegerHeap) Less(i, j int) bool { 
  return iheap[i] < iheap[j] 
}
// IntegerHeap method -swaps the element of i to j index
func (iheap IntegerHeap) Swap(i, j int) { 
  iheap[i], iheap[j] = iheap[j], iheap[i] 
}

IntegerHeap 类型有一个Push方法，可以把带interface值的项推进：

//IntegerHeap method -pushes the item
func (iheap *IntegerHeap) Push(heapintf interface{}) {
  *iheap = append(*iheap, heapintf.(int))
}
//IntegerHeap method -pops the item from the heap
func (iheap *IntegerHeap) Pop() interface{} {
  var n int
  var x1 int
  var previous IntegerHeap = *iheap
  n = len(previous)
  x1 = previous[n-1]
  *iheap = previous[0 : n-1]
  return x1
}
// main method
func main() {
  var intHeap *IntegerHeap = &IntegerHeap{1,4,5}
  heap.Init(intHeap)
  heap.Push(intHeap, 2)
  fmt.Printf("minimum: %d\n", (*intHeap)[0])
  for intHeap.Len() > 0 {
    fmt.Printf("%d \n", heap.Pop(intHeap))
  }
}

运行下面的命令：

go run heap.go

让我们在下一节里看看结构设计模式。

下一篇：《Golang学习数据结构和算法》中文版 第3篇

上一篇：《Golang学习数据结构和算法》中文版 第1篇