the data structure implementation in golang (数据结构的go语言实现, 队列:queue; 散列表:hashtable; 二叉平衡树:avl-tree......)
dataStructure index
linkedList
package linkedList
type Node struct {
data interface{}
next *Node
}
type LinkedList struct {
head *Node
size int
}
type ILinkedList interface {
AddToFirst(data interface{})
AddToLast(data interface{})
Show() (res []interface{})
Get(index int) *Node
GetPrev(index int) *Node
Add(index int, data interface{}) bool
Delete(index int) bool
Reverse() *LinkedList
ValueOf(data interface{}) (index int)
}
queue
package queue
type Node struct {
Data interface{}
Next *Node
}
type Queue struct {
head *Node
tail *Node
size int
}
type IQueue interface {
// 入队列
EnQueue(data *Node) *Queue
// 出队列
DeQueue() *Node
// 构造入队列数据节点
Data(data interface{}) *Node
// 获取队列第一个元素,不出队列
Peek() *Node
// 队列是否为空
IsEmpty() bool
// 队列数据数量
Size() int
// 打印队列
Show()
}
hashTable
package hashTable
type Options struct {
// hashtable容量，设置默认桶容量
Capacity uint
// 负载因子 0<= x <=1
LoadFactor float64
// 是否记录扩容log
Debug bool
}
type Entry struct {
key interface{}
value interface{}
next *Entry
}
type IHashTable interface {
// 添加
Put(key interface{}, value interface{}) error
// 获取key对应的值
Get(key interface{}) interface{}
// 删除
Remove(key interface{}) error
// 当前hashtable的数据量
Size() int
// 是否为空
IsEmpty() bool
// 打印每一个hash槽内的内容
Show()
}
tree
AVL tree
package avl
type AvlNode struct {
data int
left *AvlNode
right *AvlNode
}
type AVLTree struct {
root *AvlNode
size int
}
type IAVLTree interface {
// 添加节点
Add(data int) *AVLTree
// 树宽
Width() int
// 树的最大深度
Depth()
// 树的节点数
Size() int
// 横向按层打印树
Show()
}
binarySearchTree
package binarySearchTree
//const btdemo = `二叉树示例
// 10
//8 21
// 11 30
// 28 50
// 29
//`
type IBinarySearchTree interface {
// 插入
Insert(i int) bool
// 查找
Search(i int) *BinarySearchTree
// 最大
MaxNode() *BinarySearchTree
// 最小
MinNode() *BinarySearchTree
// 前序遍历
PreOrder() []int
// 中序遍历
InOrder() []int
// 后续遍历
PostOrder() []int
// 删除
Delete(i int) bool
// 最大深度
Depth() int
// 最小深度
DepthMin() int
// 宽度
}
type BinarySearchTree struct {
Data int
Left, Right *BinarySearchTree
}
stack
package stack
type IStack interface {
Push(data interface{}) bool
Pop() interface{}
Length() int
Show()
}
type Node struct {
data interface{}
next *Node
}
binaryHeap
package binaryHeap
type IBinaryHeap interface {
Add(data int)
AddSlice(data []int)
Length() int
BuildMax(dataLen int)
BuildMin(dataLen int)
SortAsc()
SortDesc()
Show()
}
type BinaryHeap struct {
data []int
}