《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
让我们在下一节里看看结构设计模式。
下一篇:
上一篇: