基本数据结构和算法的 Golang 实现

记得大一上《数据结构》的时候，老师一开始就跟我们讲：

程序 = 数据结构 + 算法

虽然知道这个很重要，但说实话这几年在项目中确实也没怎么用到过真正意义上的数据结构和算法。

当然这可能跟 Java / C# 等偏应用层的语言做了高度封装有关，像链表、哈希表等都帮你实现好了。

但是，一直觉得作为一个有追求的程序员，绝对不能仅仅满足于会用，还要“知其所以然”。

如果放任这些理论知识随着时间流逝逐渐”恢复出厂设置”，最后必定沦为只会搬砖的纯码农。

去年买了一本《算法导论》，但是觉得编排的比较“混乱”，而且太过注重算法分析和数学推导，不够接地气，因此基本只翻了下，没写过一行代码。

前段时间偶然看到知乎上有人推荐《算法》这本书，看了下编排很清晰，不像前者那样各种穿插，最后还有一个专门讲字符串的部分；更注重图表和示例程序，而不是数学证明。

为了在看书的时候能顺利点，所以决定先自己把基本的数据结构和查找排序算法温习一遍。

Golang 作为一门纯粹的、类 C 的系统编程语言，没有那么多类型封装，个人觉得很适合写算法，顺便还能巩固下指针的用法（Java 写多了这项技能确实会退化）。

因为篇幅有限，不可能展示所有详细代码，只列出代码链接和主要操作。(完整项目地址)

数据结构

func (list *LinkedList) Size() int
func (list *LinkedList) Reverse()
func (list *LinkedList) IndexOf(value interface{}) int
func (list *LinkedList) Get(index int) interface{}
func (list *LinkedList) GetFirst() interface{}
func (list *LinkedList) GetLast() interface{}
func (list *LinkedList) Add(value interface{}, index int)
func (list *LinkedList) AddToFirst(value interface{})
func (list *LinkedList) AddToLast(value interface{})
func (list *LinkedList) RemoveAt(index int)
func (list *LinkedList) RemoveFirst()
func (list *LinkedList) RemoveLast()
func (stack *LinkedStack) Size() int
func (stack *LinkedStack) Push(value interface{})
func (stack *LinkedStack) Pop()
func (stack *LinkedStack) Peek() interface{}
func (queue *LinkedQueue) Size() int
func (queue *LinkedQueue) Add(value interface{})
func (queue *LinkedQueue) Remove()
func (queue *LinkedQueue) Peek() interface{}
func (hashMap *LinkedHashMap) Put(key int, value interface{}) 
func (hashMap *LinkedHashMap) Get(key int) interface{}
func (hashMap *LinkedHashMap) Remove(key int)
func (hashMap *LinkedHashMap) Clear()
func (tree *BinarySearchTree) Add(value int)
func (tree *BinarySearchTree) Remove(value int)
func (tree *BinarySearchTree) Search(value int) *BinaryTree
func (tree *BinarySearchTree) Traverse()
func (tree *BinarySearchTree) TraverseByLevel()
func (heap *BinaryHeap) Size() int
func (heap *BinaryHeap) Add(data int)
func (heap *BinaryHeap) RemoveMinimum() int
func (graph *Graph) BreadthFirstSearch(startVertex *Vertex)
func (graph *Graph) DepthFirstSearch(startVertex *Vertex)
func (graph *Graph) PrimMinimumSpanningTree(startVertex *Vertex)
func (graph *Graph) KruskalMinimumSpanningTree()
func (graph *Graph) DijkstraShortestPath(startVertex *Vertex, endVertex *Vertex)
func (graph *Graph) TopologicalSort()

排序算法

func SimpleBubbleSort(array []int)
func FlagSwapBubbleSort(array []int)
func FlagSwapPositionBubbleSort(array []int)
func InsertSort(array []int)
func SelectSort(array []int)
func QucikSort(array []int)

查找算法

func RecursionBinarySearch(sorted_array []int, target int) int
func NonRecursionBinarySearch(sorted_array []int, target int) int

字符串算法

func KMPSearch(source string, pattern string) int
func BMSearch(source string, pattern string) int