go数据结构学习笔记

本博文较为完整的实现了go的链表、栈，队列，树，排序，链表包括顺序链表，双向链表，循环链表，队列是循环队列，排序包含冒牌、选择

1.链表

1.1 顺序链表

type LNode struct {data intnext *LNode
}
type LinkList *LNode// 初始化链表
func InitList() *LNode {l := &LNode{}return l
}// 插入链表
func (l *LNode) ListInsert(index int, value int) {p := lj := 0for p != nil && j < index-1 {p = p.nextj++}if p == nil {fmt.Println(p, j, index-1)fmt.Println("链表插入出点问题")return}s := &LNode{data: value}s.next = p.nextp.next = s
}// 删除
func (l *LNode) ListDelete(value int) {p := l.nextvar q *LNodefor p != nil {if p.data == value {if q == nil {l.next = p.next} else {q.next = p.next}}q = pp = p.next}
}// 查找
func (l *LNode) ListSearch(value int) *LNode {p := l.nextfor p != nil {//fmt.Println(p.data)if p.data == value {return p}p = p.next}return nil
}// 修改
func (l *LNode) ListModify(oldValue int, value int) {search := l.ListSearch(oldValue)if search != nil {search.data = value}
}
func (l *LNode) PrintL() {p := l.next // 从头节点的下一个开始遍历for p != nil {fmt.Printf("%d ", p.data) // 打印数据p = p.next}
}
func main() {l := InitList()l.ListInsert(1, 1)l.ListInsert(1, 2)l.ListInsert(1, 3)l.ListInsert(1, 4)l.ListInsert(1, 5)l.ListInsert(1, 6)l.PrintL()l.ListDelete(4)fmt.Println()l.PrintL()p := l.ListSearch(2)if p != nil {fmt.Println("\np value is :", p.data)}l.ListModify(2, 55)l.PrintL()
}

1.2 循环链表

type CirNode struct {data intnext *CirNode
}var CirList *CirNode
var CirRear *CirNodefunc InitCirList() *CirNode {node := &CirNode{data: 0, next: nil}node.next = nodereturn node
}func CreateCList(l *CirNode, data []int, n int) {r := lvar s *CirNodefor i := 0; i < n; i++ {s = &CirNode{}s.data = data[i]fmt.Println(data[i])s.next = r.nextr.next = sr = s}
}// 打印
func (l *CirNode) PrintList() {p := l.nextfor p != l {fmt.Printf("%d ", p.data)p = p.next}fmt.Println()
}// 查找,修改,删除
func (first *CirNode) DeleteNode(index int) {p := first.nextpre := firstcnt := 1for p != first && cnt < index {pre = pp = p.nextcnt++}pre.next = p.next
}func (first *CirNode) SarchValue(value int) {p := first.nextfor p != first {if p.data == value {break}p = p.next}if p == first {fmt.Println("未找到")}
}// 修改
func (first *CirNode) ModifyValue(value int, ele int) {p := first.nextfor p != first {if p.data == value {p.data = elebreak}p = p.next}}
func main() {lst := InitCirList()data := []int{1, 2, 3, 4}CreateCList(lst, data, 4)lst.PrintList()lst.DeleteNode(2)lst.PrintList()lst.SarchValue(1)lst.SarchValue(2)lst.PrintList()lst.ModifyValue(1, 94)lst.PrintList()
}

1.3 双向链表

type DuLNode struct {data  intprior *DuLNodenext  *DuLNode
}// 增加，删除，查找，修改
func (dL *DuLNode) Add(i int, val int) {if dL.next == nil || i <= 0 {fmt.Println("插入位置错误")}p := dL.nextcnt := 1for p != dL && cnt < i {p = p.nextcnt++}s := &DuLNode{}s.data = vals.prior = p.priors.prior.next = ss.next = pp.prior = s}func (dL *DuLNode) Print() {p := dL.nextfor p != dL {fmt.Printf("%d ", p.data)p = p.next}
}
func (dL *DuLNode) SearchKey(val int) {p := dL.nextfor p != dL {if p.data == val {break}}if p == dL {fmt.Println("没找到")}
}
func (dL *DuLNode) ModifyKey(val int, ele int) {p := dL.nextfor p != dL {if p.data == val {break}}}
func main() {dL := &DuLNode{}dL.next = dLdL.prior = dLdL.Add(1, 1)dL.Add(1, 2)dL.Add(1, 3)dL.Add(1, 4)dL.Add(1, 5)dL.Add(1, 6)dL.Add(1, 7)dL.Add(1, 8)dL.Print()
}

2.栈

2.1 顺序栈

type SNode struct {data    []intTop     intMaxSize int
}var Stack *SNode
var PtrToStack *SNodefunc NewSNode(MaxSize int) *SNode {return &SNode{data: make([]int, MaxSize), Top: -1, MaxSize: MaxSize}
}// 判断堆栈是否空
func (s *SNode) IsEmpty() bool {return s.Top == -1
}// 判断堆栈是否为满
func (s *SNode) IsFull() bool {return s.Top == s.MaxSize-1
}// 压入堆栈
func (s *SNode) Push(v int) {if s.IsFull() {fmt.Println("栈满")return} else {s.Top++s.data[s.Top] = v}}// 出战
func (s *SNode) Pop() int {if s.IsEmpty() {fmt.Println("栈空")return -1} else {tmp := s.data[s.Top]s.Top--return tmp}
}
func main() {s := NewSNode(5)s.Push(1)s.Push(2)s.Push(3)s.Push(4)fmt.Println(s.Pop())fmt.Println(s.Pop())fmt.Println(s.Pop())fmt.Println(s.IsEmpty())fmt.Println(s.IsFull())
}

2.2 链式栈

type SNode struct {data intNext *SNode
}var Stack *SNode
var PtrToSNode *SNode// 创建一个链式栈
func CreateSNode() *SNode {s := &SNode{data: -1}s.Next = nilreturn s
}// 栈空
func (s *SNode) IsEmpty() bool {return s.Next == nil
}// 入栈
func (s *SNode) Push(val int) {p := &SNode{data: val, Next: s.Next}s.Next = p
}
func (s *SNode) Pop() int {if s.IsEmpty() {fmt.Println("出栈失败")return -1}p := s.Nextvalue := p.datas.Next = p.Nextreturn value}func main() {s := CreateSNode()s.Push(1)s.Push(2)s.Push(3)s.Push(4)s.Push(5)fmt.Println(s.Pop())fmt.Println(s.Pop())fmt.Println(s.IsEmpty())
}

3.队列

在这里插入代码片

3.1 顺序队列

type Queue struct {data    []intrear    intfront   intMaxSize int
}// 生成一个队列
func CreateQueue(size int) *Queue {q := &Queue{data: make([]int, size), rear: 0, front: 0, MaxSize: size}return q
}// 判断队列为空
func (q *Queue) IsEmpty() bool {return q.front == q.rear
}// 判断队列是否满
func (q *Queue) IsFull() bool {return (q.rear+1)%q.MaxSize == q.front
}// 入队
func (q *Queue) Enqueue(value int) {if q.IsFull() {fmt.Println("Queue full")return}q.rear = (q.rear + 1) % q.MaxSizeq.data[q.rear] = value
}// 出对
func (q *Queue) Dequeue() int {if q.IsEmpty() {fmt.Println("Queue empty")return -1}q.front = (q.front + 1) % q.MaxSizereturn q.data[q.front]
}func main() {q := CreateQueue(5)q.Enqueue(1)q.Enqueue(2)q.Enqueue(3)fmt.Println(q.Dequeue())fmt.Println(q.Dequeue())fmt.Println(q.IsEmpty())fmt.Println(q.IsFull())}

3.2 链式队列

type LNode struct {data intnext *LNode
}
type QNode struct {rear    *LNodefront   *LNodemaxSize int
}func initQueue(maxSize int) *QNode {var q = &QNode{rear:    nil,front:   nil,maxSize: maxSize,}return q
}// 入队
func (q *QNode) Enqueue(data int) {s := &LNode{data: data, next: nil}if q.IsEmpty() {q.rear = sq.front = sreturn}q.rear.next = sq.rear = s}// 队空
func (q *QNode) IsEmpty() bool {return q.rear == nil
}// 出队
func (q *QNode) DeQueue() int {if q.IsEmpty() {fmt.Println("Queue is empty")return -1}s := q.frontif q.front == q.rear {q.rear = nilq.front = nil} else {q.front = q.front.next}return s.data
}
func main() {s := initQueue(5)s.Enqueue(1)s.Enqueue(2)s.Enqueue(3)fmt.Println(s.DeQueue())fmt.Println(s.DeQueue())fmt.Println(s.IsEmpty())
}

4.树

4.1 遍历造树

package mainimport ("fmt"
)type Node struct {Data   byteLChild *NodeRChild *Node
}func postOrder(root *Node) {if root == nil {return}postOrder(root.LChild)postOrder(root.RChild)fmt.Printf("%c", root.Data)}
func Search(num byte, in []byte, lens int) int {for i := 0; i < lens; i++ {if in[i] == num {return i}}return -1
}func msn(pre []byte, in []byte, len int) *Node {if len <= 0 {return nil}index := Search(pre[0], in, len)root := &Node{Data: pre[0], LChild: nil, RChild: nil}root.LChild = msn(pre[1:], in, index)root.RChild = msn(pre[index+1:], in[index+1:], len-index-1)return root
}func main() {pre := []byte{'a', 'b', 'd', 'f', 'e', 'c', 'g', 'h', 'i'}in := []byte{'d', 'b', 'e', 'f', 'a', 'g', 'h', 'c', 'i'}root := msn(pre, in, len(in))postOrder(root)
}

4.2 树打印

package mainimport "fmt"// 遍历树
// 生成一课树
// 确定一颗二叉树
type TNode struct {data        intLeft, Right *TNode
}func InorderTraversal(bt *TNode) {if bt != nil {InorderTraversal(bt.Left)fmt.Printf("%d ", bt.data)InorderTraversal(bt.Right)}
}
func PreorderTraversal(bt *TNode) {if bt != nil {fmt.Printf("%d ", bt.data)PreorderTraversal(bt.Left)PreorderTraversal(bt.Right)}}
func PostorderTraversal(bt *TNode) {if bt != nil {PostorderTraversal(bt.Left)PostorderTraversal(bt.Right)fmt.Printf("%d ", bt.data)}
}
func GetHeight(bt *TNode) int {if bt != nil {HL := GetHeight(bt.Left)HR := GetHeight(bt.Right)var h intif HL > HR {h = HL} else {h = HR}return h + 1}return 0
}type Queue struct {data    []*TNoderear    intfront   intMaxSize int
}// 生成一个队列
func CreateQueue(size int) *Queue {q := &Queue{data: make([]*TNode, size), rear: 0, front: 0, MaxSize: size}return q
}// 判断队列为空
func (q *Queue) IsEmpty() bool {return q.front == q.rear
}// 判断队列是否满
func (q *Queue) IsFull() bool {return (q.rear+1)%q.MaxSize == q.front
}// 入队
func (q *Queue) Enqueue(value *TNode) {if q.IsFull() {fmt.Println("Queue full")return}q.rear = (q.rear + 1) % q.MaxSizeq.data[q.rear] = value
}// 出对
func (q *Queue) Dequeue() *TNode {if q.IsEmpty() {fmt.Println("Queue empty")return nil}q.front = (q.front + 1) % q.MaxSizereturn q.data[q.front]
}
func LevelOrder(root *TNode) {q := CreateQueue(6)q.Enqueue(root)for !q.IsEmpty() {dequeue := q.Dequeue()fmt.Printf("%d ", dequeue.data)if dequeue.Left != nil {q.Enqueue(dequeue.Left)}if dequeue.Right != nil {q.Enqueue(dequeue.Right)}}
}type SNode struct {data    []*TNodeTop     intMaxSize int
}var Stack *SNode
var PtrToStack *SNodefunc NewSNode(MaxSize int) *SNode {return &SNode{data: make([]*TNode, MaxSize), Top: -1, MaxSize: MaxSize}
}// 判断堆栈是否空
func (s *SNode) IsEmpty() bool {return s.Top == -1
}// 判断堆栈是否为满
func (s *SNode) IsFull() bool {return s.Top == s.MaxSize-1
}// 压入堆栈
func (s *SNode) Push(v *TNode) {if s.IsFull() {fmt.Println("栈满")return} else {s.Top++s.data[s.Top] = v}}// 出战
func (s *SNode) Pop() *TNode {if s.IsEmpty() {fmt.Println("栈空")return nil} else {tmp := s.data[s.Top]s.Top--return tmp}
}func InOrderTraversalV2(BT *TNode) {T := BTs := NewSNode(6)for T != nil || !s.IsEmpty() {for T != nil {s.Push(T)T = T.Left}if !s.IsEmpty() {T = s.Pop()fmt.Printf("%d ", T.data)T = T.Right}}
}func PreOrderTraverSalV2(BT *TNode) {T := BTs := NewSNode(6)for T != nil || !s.IsEmpty() {for T != nil {fmt.Printf("%d ", T.data)s.Push(T)T = T.Left}if !s.IsEmpty() {T = s.Pop()T = T.Right}}
}
func PrintLevel(bt *TNode) {if bt != nil {if bt.Left == nil && bt.Right == nil {fmt.Printf("%d ", bt.data)}PrintLevel(bt.Left)PrintLevel(bt.Right)}
}
func main() {fmt.Println("hello world")BtRoot := TNode{data: 1, Left: nil, Right: nil}Bt1 := TNode{data: 2, Left: nil, Right: nil}Bt2 := TNode{data: 3, Left: nil, Right: nil}Bt3 := TNode{data: 4, Left: nil, Right: nil}Bt4 := TNode{data: 5, Left: nil, Right: nil}BtRoot.Left = &Bt1BtRoot.Right = &Bt2Bt2.Left = &Bt3Bt2.Right = &Bt4PreorderTraversal(&BtRoot)fmt.Println("")InorderTraversal(&BtRoot)fmt.Println("")////PostorderTraversal(&BtRoot)//fmt.Println("")//fmt.Println(GetHeight(&BtRoot))//fmt.Println("-----------")//LevelOrder(&BtRoot)fmt.Println("")PreOrderTraverSalV2(&BtRoot)fmt.Println("")InOrderTraversalV2(&BtRoot)fmt.Println("")PrintLevel(&BtRoot)
}

5.排序

5.1 冒泡/ 选择/插入/堆排序

func BubbleSort(arr []int) []int {for i := 0; i < len(arr)-1; i++ {for j := 0; j < len(arr)-i-1; j++ {if arr[j] > arr[j+1] {arr[j], arr[j+1] = arr[j+1], arr[j]}}}return arr
}
func InsertSort(arr []int) []int {i := 0for p := 1; p < len(arr); p++ {temp := arr[p]for i = p; i > 0 && arr[i-1] > temp; i-- {arr[i] = arr[i-1]}arr[i] = temp}return arr
}func SelectSort(arr []int) []int {for i := 0; i < len(arr); i++ {minValue := ifor j := i + 1; j < len(arr); j++ {if arr[minValue] > arr[j] {minValue = j}}arr[i], arr[minValue] = arr[minValue], arr[i]}return arr
}func PercDown(arr []int, p int, n int) {var child intvar parent intx := arr[p]for parent = p; parent*2+1 < n; parent = child {child = parent*2 + 1if child != n-1 && arr[child] < arr[child+1] {child++}if x >= arr[child] {break} else {arr[parent] = arr[child]}}arr[parent] = x
}
func HeapSort(arr []int, n int) {i := -1for i = n / 2; i >= 0; i-- {PercDown(arr, i, n)}for i = n - 1; i >= 0; i-- {arr[0], arr[i] = arr[i], arr[0]PercDown(arr, 0, i)}
}func main() {s := []int{1, 8, 3, 2}fmt.Println(s)//s = BubbleSort(s)//fmt.Println(s)//s = InsertSort(s)//fmt.Println(s)//s = SelectSort(s)//fmt.Println(s)//HeapSort(s, len(s))fmt.Println(s)

5.2 快速/归并排序

package mainimport "fmt"func Merge(arr []int, tmpA []int, L int, R int, RightEnd int) {LeftEnd := R - 1Tmp := LNumElements := RightEnd - L + 1for L <= LeftEnd && R <= RightEnd {if arr[L] <= arr[R] {tmpA[Tmp] = arr[L]Tmp++L++} else {tmpA[Tmp] = arr[R]Tmp++R++}}for L <= LeftEnd {tmpA[Tmp] = arr[L]L++Tmp++}for R <= RightEnd {tmpA[Tmp] = arr[R]R++Tmp++}for i := 0; i < NumElements; i++ {arr[RightEnd] = tmpA[RightEnd]RightEnd--}
}func MSort(arr []int, tmpA []int, L int, RightEnd int) {var Center intif L < RightEnd {Center = (L + RightEnd) / 2MSort(arr, tmpA, L, Center)MSort(arr, tmpA, Center+1, RightEnd)Merge(arr, tmpA, L, Center+1, RightEnd)}
}
func MergeSort(arr []int, n int) {tmpA := make([]int, n)MSort(arr, tmpA, 0, n-1)
}
func main() {a := []int{1, 8, 2, 4, 6, 5}fmt.Println(a)MergeSort(a, len(a))fmt.Println(a)
}//Merge非地柜版本
func Merge(A []int, tmpA []int, L int, R int, RightEnd int) {LeftEnd := R - 1Tmp := LNumElements := RightEnd - L + 1for L <= LeftEnd && R <= RightEnd {if A[L] <= A[R] {tmpA[Tmp] = A[L]Tmp++L++} else {tmpA[Tmp] = A[R]Tmp++R++}}for L <= LeftEnd {tmpA[Tmp] = A[L]Tmp++L++}for R <= RightEnd {tmpA[Tmp] = A[R]Tmp++R++}for i := 0; i < NumElements; i++ {A[RightEnd] = tmpA[RightEnd]RightEnd--}
}
func MergePass(A []int, tmpA []int, N int, length int) {var i intvar j intfor i = 0; i <= N-2*length; i += 2 * length {Merge(A, tmpA, i, i+length, i+length*2-1)}if i+length < N {Merge(A, tmpA, i, i+length, N-1)} else {for j = i; j < N; j++ {tmpA[j] = A[j]}}
}func MergeSort(A []int, N int) {length := 1tmpA := make([]int, N)for length < N {MergePass(A, tmpA, N, length)length *= 2MergePass(tmpA, A, N, length)length *= 2}
}
func main() {a := []int{1, 8, 3, 2}fmt.Println(a)MergeSort(a, len(a))fmt.Println(a)
}func InsertionSort(A []int, N int) {for P := 1; P < N; P++ {tmp := A[P]i := Pfor ; i > 0 && A[i-1] > tmp; i-- {A[i] = A[i-1]}A[i] = tmp}
}func Median(A []int, Left int, Right int) int {Center := (Left + Right) / 2if A[Left] > A[Center] {A[Left], A[Center] = A[Center], A[Left]}if A[Left] > A[Right] {A[Right], A[Left] = A[Right], A[Left]}if A[Center] > A[Right] {A[Center], A[Right] = A[Center], A[Center]}A[Center], A[Right-1] = A[Right-1], A[Center]return A[Right-1]
}// 快速排序
func QSort(A []int, left int, right int) {CutOff := 10if right-left > CutOff {Privot := Median(A, left, right)Low := leftHigh := right - 1for {for Low++; A[Low] < Privot; Low++ {}for High--; A[High] > Privot; High-- {}if Low < High {A[Low], A[High] = A[High], A[Low]} else {break}}A[Low], A[right-1] = A[right-1], A[Low]QSort(A, left, Low-1)QSort(A, Low+1, right)} else {InsertionSort(A[left:], right-left+1)}
}
func QuickSort(data []int, N int) {QSort(data, 0, N-1)
}
func main() {arr := []int{1, 8, 3, 2}fmt.Println(arr)QuickSort(arr, len(arr))fmt.Println(arr)
}