网站建设 设备,建设人才库网站,上海十大科技公司,邢台网站建设平台本博文较为完整的实现了go的链表、栈#xff0c;队列#xff0c;树#xff0c;排序#xff0c;链表包括顺序链表#xff0c;双向链表#xff0c;循环链表#xff0c;队列是循环队列#xff0c;排序包含冒牌、选择
1.链表
1.1 顺序链表
type LNode struct {data intn…本博文较为完整的实现了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.Tops.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.rear1)%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[index1:], in[index1:], 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.rear1)%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.Tops.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[j1] {arr[j], arr[j1] arr[j1], 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*21 n; parent child {child parent*2 1if child ! n-1 arr[child] arr[child1] {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 fmtfunc 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]TmpL} else {tmpA[Tmp] arr[R]TmpR}}for L LeftEnd {tmpA[Tmp] arr[L]LTmp}for R RightEnd {tmpA[Tmp] arr[R]RTmp}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, Center1, RightEnd)Merge(arr, tmpA, L, Center1, 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]TmpL} else {tmpA[Tmp] A[R]TmpR}}for L LeftEnd {tmpA[Tmp] A[L]TmpL}for R RightEnd {tmpA[Tmp] A[R]TmpR}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, ilength, ilength*2-1)}if ilength N {Merge(A, tmpA, i, ilength, 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, Low1, right)} else {InsertionSort(A[left:], right-left1)}
}
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)
}
