dsg

package module
v1.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 18, 2022 License: GPL-3.0 Imports: 4 Imported by: 1

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Float64CompFunc 

func Float64CompFunc(v1 Value, v2 Value) int

func FloatHeapSort 

func FloatHeapSort(data []Value)

func HeapSort 

func HeapSort(data []Value, cmf CompFunc)

堆排序: 从大到小.

func IntCompFunc 

func IntCompFunc(v1 Value, v2 Value) int

func IntHeapSort 

func IntHeapSort(data []Value)

Types

type AvlNode added in v1.1.0 

type AvlNode struct {
	// contains filtered or unexported fields
}

func InitAvlNode added in v1.1.0 

func InitAvlNode(v Value, comp_func CompFunc) *AvlNode

func (*AvlNode) Add added in v1.1.0 

func (root *AvlNode) Add(v Value) (new_root *AvlNode, new_deeper int)

func (*AvlNode) BalanceLeft added in v1.1.0 

func (root *AvlNode) BalanceLeft() *AvlNode

func (*AvlNode) BalanceRight added in v1.1.0 

func (root *AvlNode) BalanceRight() *AvlNode

func (*AvlNode) GetHeight added in v1.1.0 

func (root *AvlNode) GetHeight() int

func (*AvlNode) Print added in v1.1.0 

func (root *AvlNode) Print(level int)

func (*AvlNode) Remove added in v1.1.0 

func (root *AvlNode) Remove(v Value) (new_root *AvlNode, junk *AvlNode)

func (*AvlNode) RemoveLeftMostDescendant added in v1.1.0 

func (root *AvlNode) RemoveLeftMostDescendant() (new_root *AvlNode, junk *AvlNode)

func (*AvlNode) RestoreLeftBalance added in v1.1.0 

func (root *AvlNode) RestoreLeftBalance(oldbf int) *AvlNode

func (*AvlNode) RestoreRightBalance added in v1.1.0 

func (root *AvlNode) RestoreRightBalance(oldbf int) *AvlNode

type AvlTree added in v1.1.0 

type AvlTree struct {
	// contains filtered or unexported fields
}

func InitAvlTree added in v1.1.0 

func InitAvlTree(comp_func CompFunc) *AvlTree

func InitFloatAvlTree added in v1.1.0 

func InitFloatAvlTree() *AvlTree

func InitIntAvlTree added in v1.1.0 

func InitIntAvlTree() *AvlTree

func (*AvlTree) Add added in v1.1.0 

func (tr *AvlTree) Add(v Value)

func (*AvlTree) Print added in v1.1.0 

func (tr *AvlTree) Print()

func (*AvlTree) Remove added in v1.1.0 

func (tr *AvlTree) Remove(v Value)

type Chain 

type Chain struct {
	// contains filtered or unexported fields
}

* Hash 非叶节点结构, 若其子节点为叶节点, 则 len(sublist) = 0,

  • head 指向首个子节点, tail 指向最后一个子节点.
  • 若其子节点为非叶节点, 则 head = tail = nil, sublist 指向子节点数组,
  • n 为子节点个数.

type CompFunc 

type CompFunc func(v1 Value, v2 Value) int

type Hash 

type Hash struct {
	// contains filtered or unexported fields
}

* Hash 结构

func InitHash 

func InitHash(n int, ktoi KeyToIndexFunc, comp CompFunc) *Hash

func InitTreeHash 

func InitTreeHash(n []int, ktoi KeyToIndexFunc, comp CompFunc) *Hash

func (*Hash) AddData 

func (hash *Hash) AddData(key Value, value Value)

* 向 hash 中增加一个叶节点.

  • \param hash 待增加hash
  • \param key 增加节点的 key
  • \param value 增加节点的 value

func (*Hash) Clear 

func (hash *Hash) Clear()

func (*Hash) GotoChain 

func (hash *Hash) GotoChain(ind []int) *Chain

* 跳转到 hash 的某个非叶节点

  • \param ind 位置索引

func (*Hash) InitSubHash 

func (hash *Hash) InitSubHash(ind []int, n int)

func (*Hash) RemoveData 

func (hash *Hash) RemoveData(key Value)

* 删除 hash 中以 key 为索引的节点

  • \param hash 待删除节点所在的 hash
  • \param key 待删除节点的索引 (key)

func (*Hash) Search 

func (hash *Hash) Search(key Value) (value Value)

* 核心函数, 利用 Hash 完成查找,

  • \param hash 已经建立好的 Hash
  • \param key 待查找的 key
  • \param value 返回查找得到的 value (nil: 没找到)

func (*Hash) SearchChain 

func (hash *Hash) SearchChain(key Value) *Chain

* 通过 key 查找 hash 的某个非叶节点,

  • \param hash 待查找的 hash
  • \param key 用于查找的 key

func (*Hash) SearchNode 

func (hash *Hash) SearchNode(key Value) (last *Node, pcc *Chain, result *Node)

* 通过 key 查找 hash 的某个叶节点,

  • \param hash 待查找的 hash
  • \param key 用于查找的 key
  • \param last 返回所得叶节点的前一个节点 (若为该树枝上的首个节点, 则返回 nil)
  • \param pcc 返回所得叶节点的父节点.
  • \param result 返回查找所得的节点.

type Heap 

type Heap struct {
	// contains filtered or unexported fields
}

func InitFloatHeap 

func InitFloatHeap() *Heap

func InitHeap 

func InitHeap(cmf CompFunc) *Heap

func InitIntHeap 

func InitIntHeap() *Heap

func (*Heap) Add 

func (hp *Heap) Add(value Value)

* 向 heap 中添加元素

func (*Heap) Get 

func (hp *Heap) Get(ind int) *Value

func (*Heap) GetLCInd 

func (hp *Heap) GetLCInd(ind int) int

return -1 if no child

func (*Heap) GetParInd 

func (hp *Heap) GetParInd(ind int) int

return -1 if no par (root)

func (*Heap) GetRCInd 

func (hp *Heap) GetRCInd(ind int) int

return -1 if no child

func (*Heap) GetSize 

func (hp *Heap) GetSize() int

func (*Heap) Pop 

func (hp *Heap) Pop() (value Value)

* 删除 heap 的根元素

func (*Heap) Rebuild 

func (hp *Heap) Rebuild(root int)

* 重建以索引 root 为根结点的子树重建堆

type Key 

type Key interface{}

type KeyToIndexFunc 

type KeyToIndexFunc func(key Key) (ind []int)

type LList 

type LList struct {
	// contains filtered or unexported fields
}

* 滑动数组表 (带索引链表)

func InitLList 

func InitLList(nbuf int) *LList

func (*LList) Flush 

func (ll *LList) Flush()

func (*LList) Get 

func (ll *LList) Get(ind int) (value *Value)

func (*LList) GetFirst 

func (ll *LList) GetFirst() (value *Value)

func (*LList) GetLast 

func (ll *LList) GetLast() (value *Value)

func (*LList) GetN 

func (ll *LList) GetN() int

func (*LList) Pop 

func (ll *LList) Pop() (value Value)

func (*LList) PopFirst 

func (ll *LList) PopFirst() (value Value)

func (*LList) Push 

func (ll *LList) Push(value Value) int

type Node 

type Node struct {
	// contains filtered or unexported fields
}

* Hash 叶节点结构

type PQueue 

type PQueue Heap

func InitPQueue 

func InitPQueue(cmf CompFunc) *PQueue

初始化优先队列

func (*PQueue) Add 

func (pq *PQueue) Add(value Value)

向优先队列中添加元素

func (*PQueue) Flush 

func (pq *PQueue) Flush()

清空优先队列

func (*PQueue) GetSize 

func (pq *PQueue) GetSize() int

获得优先队列长度

func (*PQueue) Pop 

func (pq *PQueue) Pop() (value Value)

从优先队列中取出最小元素 * \return -1: 队列空; 0: 成功

type Set 

type Set struct {
	// contains filtered or unexported fields
}

func InitSet 

func InitSet(size int) *Set

func (*Set) Co 

func (sres *Set) Co(s1 *Set)

func (*Set) CopyFrom 

func (oset *Set) CopyFrom(sset *Set) (is_err bool)

func (*Set) Diff 

func (sres *Set) Diff(s1 *Set, s2 *Set)

func (*Set) Empty 

func (s1 *Set) Empty()

func (*Set) Full 

func (s1 *Set) Full()

func (*Set) GetAllLabel 

func (set *Set) GetAllLabel() (labels []int)

func (*Set) GetLabel 

func (set *Set) GetLabel(ind int) bool

func (*Set) GetNLabel 

func (set *Set) GetNLabel() int

func (*Set) GetSize 

func (set *Set) GetSize() int

func (*Set) Inter 

func (sres *Set) Inter(s1 *Set, s2 *Set)

func (*Set) IsEmpty 

func (set *Set) IsEmpty() bool

func (*Set) Load 

func (set *Set) Load(fload io.Reader)

func (*Set) Save 

func (set *Set) Save(fsav io.Writer)

func (*Set) SetLabel 

func (set *Set) SetLabel(ind int, label bool)

func (*Set) Union 

func (sres *Set) Union(s1 *Set, s2 *Set)

type Value 

type Value interface{}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.