我们在Go语言当中使用的数学方法都来自与math包，其中math的子包中包含以下这些包：
math/big: 大整数的高精度计算实现
math/cmplx: 复数基本函数操作
math/rand: 伪随机数生成器
Go在数据结构方面主要有三大相关的标准包：
sort: 包含基本的排序方法
index/suffixary: 该包实现了后缀数组相关算法以支持许多常见的字符串操作
container: 该包实现了我们数据结构当中最常用的堆、链表和环的内容。
排序
数据集合排序
我们在对数据集合进行排序之前，需要实现sort.Interface接口的三个方法，来看一下其定义：
type Interface interface {
// 获取元素集合个数元素
Len() int
// 如果 i 索引的数据小于 j 所有的数据，返回 true，不会调用
Less(i, j int) bool
// 交换 i 和 j 索引得两个元素的位置
Swap(i, j int)
}
我们在实现了这三个方法后，就可以调用Sort()方法来进行排序了。其定义也很简单，只需要一个参数，也就是待排序的数据集合。
func Sort(data interface)
该包中还提供了一个IsSorted()函数，用来判断数据集合是否已经拍好顺序。
func IsSorted(data interface) {
n := data.Len()
for i := n - 1; i > 0; i-- {
if data.Less(i, i-1) {
return false
}
}
return true
}
我们来看一个具体的例子：
import (
"fmt"
"sort"
)
type StuInfo struct {
name string
score int
}
type StuInfos []StuInfo
func (s StuInfos) Len() int {
return len(s)
}
func (s StuInfos) Less(i, j int) bool {
return s[i].score < s[j].score
}
func (s StuInfos) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
func main() {
stus := StuInfos{
{"Alice", 95},
{"Bob", 91},
{"Cindy", 96},
{"David", 90},
}
fmt.Println("=====Original=====")
for _, stu := range stus {
fmt.Println(stu.name, ": " , stu.score)
}
fmt.Println()
sort.Sort(stus)
fmt.Println("=====After Sort=====")
for _, stu := range stus {
fmt.Println(stu.name, ": ", stu.score)
}
fmt.Println("Has been sorted?", sort.IsSorted(stus))
}
/** The result is:
David : 90
Bob : 91
Alice : 95
Cindy : 96
Has been sorted? true
*/
在这个程序当中，我们使用的是升序排序，那如果我们想要使用降序该怎么办呢？
也很简单，只需要修改Less()函数即可。
func (s StuInfos) Less(i, j int) bool {
return s[i].score > s[j].score
}
但其实还有一种方法，也很简单，那么就是Reverse()函数，这个函数我们在学习数据结构或者其他语言的时候会经常对反转函数这么命名，那么有了这个函数我们就不需要再修改Less()函数了。
func Reverse(data interface) Interface
在这里需要注意的是，Reverse()函数返回的是一个接口。
那么这样一来，我们就可以在刚才那个例子中使用Reverse()来实现成绩升序排序：
sort.Sort(sort.Reverse(stus))
for _, stu := range stus {
fmt.Println(stu.name, ": ", stu.score)
}
最后还有一个方法：Search()，该方法使用“二分查找” 算法来搜索某指定切片[0:n],定义如下：
func Search(n int, f func(int) bool) int
Search()函数的一个常用方式是搜索元素x是否已经在升序排好的切片s中：
x := 11
s := []int{3, 6, 8, 11, 45}
pos := sort.Search(len(s), func(i int) bool {return s[i] >= x })
if pos < len(s) && s[pos] == x {
fmt.Println("The position of ", x, "is: ", pos)
} else {
fmt.Println(x, " is not in slice.")
}
切片排序
我们知道sort包中是原生支持[]int、[]float64、[]string类型的，也就意味着这三种切片类型接口的内部实现是不需要我们自己去设置的。
1）[]int排序
sort包定义了一个IntSlice类型，并且实现了sort.Interface接口。在提供的sort.Ints()方法中就使用了这个IntSlice类型：
func Ints(a []int) { Sort(IntSlice(a)) }
所以，对[]int切片排序时会更常使用sort.Ints()，而不是直接使用IntSlice类型。
如果要查找整数x在切片a中的位置，相对于前面提到的Search()方法，sort包提供了SearchInts()：
func SearchInts(a []int, x int) int
2）[]float64排序
实现与Ints类似，与Sort()，IsSorted()，Search()相对应的三个方法：
func Float64s(a []float64)
func Float64AreSorted(a []float64) bool
func SearchFloat64s(a []float64, x float64) int
3）[]stirng排序
两个string对象之间的大小比较是基于"字典序"的，实现仍然与Ints类似，与Sort()，IsSorted()，Search()相对应的三个方法：
func Strings(a []string)
func StringsAreSorted(a []string) bool
func SearchStrings(a []string, x string) int
container
这个包实现了三个我们在数据当中会经常用到的三种数据结构：堆、链表和环。
堆
这里的堆使用的数据结构是使用的最小二叉树的存储方法，定义如下：
type Interface interface {
sort.Interface
Push(x interface{})
Pop() interface{}
}
从第二行代码我们看出来，堆的定义是继承自sort.Interface的。我们前面说过，实现一个sort.Interface是需要实现三个方法的，再加上堆本身的两个方法，因此我们在使用堆的时候，是需要实现五个方法的。结合前面所讲的，我们可以试着来实现一下这五个方法：
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(h)
x := old[n-1]
*h = old[0: n-1]
return x
}
链表
链表其实就是一个有prev和next指针的数组，它维护了两个type，要注意，这里就不再是接口了。
type Element struct {
next, prev *Element
list *List
Value interface{}
}
type List struct {
root Element
len int
}
除了定义之外，我们在来看一下list都对应着哪些方法：
type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List
func (l *List) Back() *Element
func (l *List) Prev() *Element
func (l *List) Init() *List
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素后插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在某个元素之前插入
func (l *List) Len() int
func (l *List) MoveAfter(e, mark *Element) // 把e元素移动到mark之后
func (l *List) MoveBefore(e, mark *Element) // 把e元素移动到mark之前
func (l *List) MoveToBack(e *Element) // 把e元素移动到链表最后
func (l *List) MoveToFront(e *Element) // 把e元素移动到链表最前面
func (l *List) PushBack(v interface{}) *Element // 在链表最后插入元素
func (l *List) PushBackList(other *List) // 在链表最后插入接上新链表
func (l *List) PushFront(v interface{}) *Element // 在链表头部插入元素
func (l *List) PushFrontList(other *List) // 在链表最前面插入接上新链表
func (l *List) Remove(e *Element) interface{} // 删除某个元素
环
环是数据结构当中最好用的一种数据结构，而且环的尾部就是头部，所以每个元素实际上就可以代表自身的这个环。因此我们只需要保持一个结构就可以：
type Ring struct {
next, prev *Ring
Value interface{}
}
我们在初始化环的时候一定要定义好环的大小，而且，环结构还提供了一个Do的方法，可以对整个环进行遍历，并对每个元素执行相应的功能。
package main
import (
"container/ring"
"fmt"
)
func main() {
ring := ring.New(3)
for i := 1; i <= 3; i++ {
ring.Value = i
ring = ring.Next()
}
sum := 0
ring.Do(func (p interface{}){
sum += p.(int)
})
fmt.Println("The result is: ", sum)
}
/**
The result is: 6
*/
我们可以看出，Do方法对于遍历环中每一个元素并执行相应功能的操作十分方便。
ring也提供了一些相应的方法：
type Ring
func Next(n int) *Ring
func (r *Ring) Do(f func(interface{}))
func (r *Ring) Len() int
func (r *Ring) Link(s *Ring) *Ring
func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前移动（n可以为负数）
func (r *Ring) Next() *Ring
func (r *Ring) Prev() *Ring
func (r *Ring) Unlink(n int) *Ring // 从当前元素开始，删除n个元素
网友评论