задний план
В отличие от C++, в golang уже есть общая высокоуровневая структура данных, такая как stl. Поэтому, если вам нужны стеки, очереди, связанные списки и другие структуры данных, вам нужно реализовать их самостоятельно.
Ниже приведены некоторые часто используемые структуры данных.
связанный список
Односвязный список — это цепочка структур данных доступа.Связный список состоит из одного или нескольких узлов, и каждый узел имеет указатель на следующий узел. Ниже приведена реализация связанного списка с узлами как int.
package list
type List struct {
Head * ListNode
length int
}
type ListNode struct {
Next *ListNode
Data int
}
func (p *List) AddNode(data int) {
if p.Head == nil {
p.Head = new(ListNode)
}
var node = &ListNode {
Data : data,
}
currentNext := p.Head.Next
p.Head.Next = node
node.Next = currentNext
}
func (p *List) Lenth() int {
return p.length
}
// delete specified pos
func (p *List) DeleteWithPos(pos int) {
if pos + 1 > p.length {
return
}
var i int
pre := p.Head
for {
if i == pos {
pre.Next = pre.Next.Next
}
pre = pre.Next
i++
}
return
}
func (p *List) DeleteWithData(data int) {
pre := p.Head
for {
if pre.Next == nil {
break
}
if data == pre.Next.Data {
pre.Next = pre.Next.Next
}
pre = pre.Next
}
return
}
очередь
Очереди похожи на очереди в жизни. Характеристика FIFO (первый пришел, первый ушел, первый пришел, первый ушел). Кто первым встанет в очередь, тот и выйдет первым. Например, если вы идете в банк, чтобы положить деньги, в очереди 10 человек, первый человек, который встанет в очередь, а именно № 1, должен быть первым, кто займется делом.
Затем посмотрите, как golang реализует очередь:
package queue
import (
"errors"
)
type Queue []interface{}
func (queue *Queue) Len() int {
return len(*queue)
}
func (queue *Queue) IsEmpty() bool {
return len(*queue) == 0
}
func (queue *Queue) Cap() int {
return cap(*queue)
}
func (queue *Queue) Push(value interface{}) {
*queue = append(*queue, value)
}
func (queue *Queue) Pop() (interface{}, error) {
theQueue := *queue
if len(theQueue) == 0 {
return nil, errors.New("Out of index, len is 0")
}
value := theQueue[0]
*queue = theQueue[1:len(theQueue)]
return value, nil
}
куча
Структура данных «первым пришел — последним ушел». Сцена стога в жизни может соответствовать ведру с рисом, и тот рис, который кладут первым, вынимают в конце. Здесь интерфейс используется для реализации относительно общего стека.
package stack
import "errors"
type Stack []interface{}
func (stack Stack) Len() int {
return len(stack)
}
func (stack Stack) IsEmpty() bool {
return len(stack) == 0
}
func (stack Stack) Cap() int {
return cap(stack)
}
func (stack *Stack) Push(value interface{}) {
*stack = append(*stack, value)
}
func (stack Stack) Top() (interface{}, error) {
if len(stack) == 0 {
return nil, errors.New("Out of index, len is 0")
}
return stack[len(stack)-1], nil
}
func (stack *Stack) Pop() (interface{}, error) {
theStack := *stack
if len(theStack) == 0 {
return nil, errors.New("Out of index, len is 0")
}
value := theStack[len(theStack)-1]
*stack = theStack[:len(theStack)-1]
return value, nil
}
Суммировать
Выше приведены несколько распространенных расширенных структур данных.В сочетании со встроенными структурами данных golang они уже могут справиться с разработкой большинства бизнес-сценариев. Более сложные структуры данных, такие как списки пропуска, бинарные деревья, сбалансированные бинарные деревья и кучи, будут представлены позже.