您好,登錄后才能下訂單哦!
本篇文章為大家展示了golang項(xiàng)目中有哪些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu),內(nèi)容簡(jiǎn)明扼要并且容易理解,絕對(duì)能使你眼前一亮,通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。
golang 是Google開(kāi)發(fā)的一種靜態(tài)強(qiáng)類(lèi)型、編譯型、并發(fā)型,并具有垃圾回收功能的編程語(yǔ)言,其語(yǔ)法與 C語(yǔ)言相近,但并不包括如枚舉、異常處理、繼承、泛型、斷言、虛函數(shù)等功能。
舉單鏈表的例子,雙向鏈表同理只是多了pre指針。
定義單鏈表結(jié)構(gòu):
type LinkNode struct { Data int64 NextNode *LinkNode }
構(gòu)造鏈表及打印鏈表:
func main() { node := new(LinkNode) node.Data = 1 node1 := new(LinkNode) node1.Data = 2 node.NextNode = node1 // node1 鏈接到 node 節(jié)點(diǎn)上 node2 := new(LinkNode) node2.Data = 3 node1.NextNode = node2 // node2 鏈接到 node1 節(jié)點(diǎn)上 // 順序打印。把原鏈表頭結(jié)點(diǎn)賦值到新的NowNode上 // 這樣仍然保留了原鏈表頭結(jié)點(diǎn)node不變 nowNode := node for nowNode != nil { fmt.Println(nowNode.Data) // 獲取下一個(gè)節(jié)點(diǎn)。鏈表向下滑動(dòng) nowNode = nowNode.NextNode } }
可變數(shù)組在各種語(yǔ)言中都非常常用,在golang中,可變數(shù)組語(yǔ)言本身已經(jīng)實(shí)現(xiàn),就是我們的切片slice。
棧:先進(jìn)后出,后進(jìn)先出,類(lèi)似彈夾
隊(duì)列:先進(jìn)先出
golang中,實(shí)現(xiàn)并發(fā)不安全的棧和隊(duì)列,非常簡(jiǎn)單,我們直接使用原生切片即可。
func main() { // 用切片制作一個(gè)棧 var stack []int // 元素1 入棧 stack = append(stack, 1, 5, 7, 2) // 棧取出最近添加的數(shù)據(jù)。例如[1,5,7,2] ,len = 4 x := stack[len(stack)-1] // 2 // 切掉最近添加的數(shù)據(jù),上一步和這一步模仿棧的pop。 stack = stack[:len(stack)-1] // [1,5,7] fmt.Printf("%d", x) }
func main() { // 用切片模仿隊(duì)列 var queue []int // 進(jìn)隊(duì)列 queue = append(queue, 1, 5, 7, 2) // 隊(duì)頭彈出,再把隊(duì)頭切掉,模仿隊(duì)列的poll操作 cur := queue[0] queue = queue[1:] fmt.Printf("%d", cur) }
// 數(shù)組棧,后進(jìn)先出 type Mystack struct { array []string // 底層切片 size int // 棧的元素?cái)?shù)量 lock sync.Mutex // 為了并發(fā)安全使用的鎖 }
入棧
// 入棧 func (stack *Mytack) Push(v string) { stack.lock.Lock() defer stack.lock.Unlock() // 放入切片中,后進(jìn)的元素放在數(shù)組最后面 stack.array = append(stack.array, v) // 棧中元素?cái)?shù)量+1 stack.size = stack.size + 1 }
出棧
1、如果切片偏移量向前移動(dòng) stack.array[0 : stack.size-1],表明最后的元素已經(jīng)不屬于該數(shù)組了,數(shù)組變相的縮容了。此時(shí),切片被縮容的部分并不會(huì)被回收,仍然占用著空間,所以空間復(fù)雜度較高,但操作的時(shí)間復(fù)雜度為:O(1)。
2、如果我們創(chuàng)建新的數(shù)組 newArray,然后把老數(shù)組的元素復(fù)制到新數(shù)組,就不會(huì)占用多余的空間,但移動(dòng)次數(shù)過(guò)多,時(shí)間復(fù)雜度為:O(n)。
func (stack *Mystack) Pop() string { stack.lock.Lock() defer stack.lock.Unlock() // 棧中元素已空 if stack.size == 0 { panic("empty") } // 棧頂元素 v := stack.array[stack.size-1] // 切片收縮,但可能占用空間越來(lái)越大 //stack.array = stack.array[0 : stack.size-1] // 創(chuàng)建新的數(shù)組,空間占用不會(huì)越來(lái)越大,但可能移動(dòng)元素次數(shù)過(guò)多 newArray := make([]string, stack.size-1, stack.size-1) for i := 0; i < stack.size-1; i++ { newArray[i] = stack.array[i] } stack.array = newArray // 棧中元素?cái)?shù)量-1 stack.size = stack.size - 1 return v }
獲取棧頂元素
// 獲取棧頂元素 func (stack *Mystack) Peek() string { // 棧中元素已空 if stack.size == 0 { panic("empty") } // 棧頂元素值 v := stack.array[stack.size-1] return v }
獲取棧大小和判定是否為空
// 棧大小 func (stack *Mystack) Size() int { return stack.size } // 棧是否為空 func (stack *Mystack) IsEmpty() bool { return stack.size == 0 }
// 數(shù)組隊(duì)列,先進(jìn)先出 type Myqueue struct { array []string // 底層切片 size int // 隊(duì)列的元素?cái)?shù)量 lock sync.Mutex // 為了并發(fā)安全使用的鎖 }
入隊(duì)
// 入隊(duì) func (queue *Myqueue) Add(v string) { queue.lock.Lock() defer queue.lock.Unlock() // 放入切片中,后進(jìn)的元素放在數(shù)組最后面 queue.array = append(queue.array, v) // 隊(duì)中元素?cái)?shù)量+1 queue.size = queue.size + 1 }
出隊(duì)
1、原地挪位,依次補(bǔ)位 queue.array[i-1] = queue.array[i],然后數(shù)組縮容:queue.array = queue.array[0 : queue.size-1],但是這樣切片縮容的那部分內(nèi)存空間不會(huì)釋放。
2、創(chuàng)建新的數(shù)組,將老數(shù)組中除第一個(gè)元素以外的元素移動(dòng)到新數(shù)組。
// 出隊(duì) func (queue *Myqueue) Remove() string { queue.lock.Lock() defer queue.lock.Unlock() // 隊(duì)中元素已空 if queue.size == 0 { panic("empty") } // 隊(duì)列最前面元素 v := queue.array[0] /* 直接原位移動(dòng),但縮容后繼的空間不會(huì)被釋放 for i := 1; i < queue.size; i++ { // 從第一位開(kāi)始進(jìn)行數(shù)據(jù)移動(dòng) queue.array[i-1] = queue.array[i] } // 原數(shù)組縮容 queue.array = queue.array[0 : queue.size-1] */ // 創(chuàng)建新的數(shù)組,移動(dòng)次數(shù)過(guò)多 newArray := make([]string, queue.size-1, queue.size-1) for i := 1; i < queue.size; i++ { // 從老數(shù)組的第一位開(kāi)始進(jìn)行數(shù)據(jù)移動(dòng) newArray[i-1] = queue.array[i] } queue.array = newArray // 隊(duì)中元素?cái)?shù)量-1 queue.size = queue.size - 1 return v }
字典也是程序語(yǔ)言經(jīng)常使用的結(jié)構(gòu),golang中的字典是其自身實(shí)現(xiàn)的map結(jié)構(gòu)。具體操作可以查看語(yǔ)言api
并發(fā)安全的map,可以定義結(jié)構(gòu),結(jié)構(gòu)中有一個(gè)map成員和一個(gè)鎖變量成員,參考并發(fā)安全的棧和隊(duì)列的實(shí)現(xiàn)。go語(yǔ)言也實(shí)現(xiàn)了一個(gè)并發(fā)安全的map,具體參考sync.map的api
我們可以借助map的特性,實(shí)現(xiàn)一個(gè)Set結(jié)構(gòu)。
Set結(jié)構(gòu)
map的值我們不適用,定義為空的結(jié)構(gòu)體struct{}
// 集合結(jié)構(gòu)體 type Set struct { m map[int]struct{} // 用字典來(lái)實(shí)現(xiàn),因?yàn)樽侄捂I不能重復(fù) len int // 集合的大小 sync.RWMutex // 鎖,實(shí)現(xiàn)并發(fā)安全 }
初始化Set
// 新建一個(gè)空集合 func NewSet(cap int64) *Set { temp := make(map[int]struct{}, cap) return &Set{ m: temp, } }
往set中添加一個(gè)元素
// 增加一個(gè)元素 func (s *Set) Add(item int) { s.Lock() defer s.Unlock() s.m[item] = struct{}{} // 實(shí)際往字典添加這個(gè)鍵 s.len = len(s.m) // 重新計(jì)算元素?cái)?shù)量 }
刪除一個(gè)元素
// 移除一個(gè)元素 func (s *Set) Remove(item int) { s.Lock() s.Unlock() // 集合沒(méi)元素直接返回 if s.len == 0 { return } delete(s.m, item) // 實(shí)際從字典刪除這個(gè)鍵 s.len = len(s.m) // 重新計(jì)算元素?cái)?shù)量 }
查看元素是否在集合set中
// 查看是否存在元素 func (s *Set) Has(item int) bool { s.RLock() defer s.RUnlock() _, ok := s.m[item] return ok }
查看集合大小
// 查看集合大小 func (s *Set) Len() int { return s.len }
查看集合是否為空
// 集合是夠?yàn)榭? func (s *Set) IsEmpty() bool { if s.Len() == 0 { return true } return false }
清除集合所有元素
// 清除集合所有元素 func (s *Set) Clear() { s.Lock() defer s.Unlock() s.m = map[int]struct{}{} // 字典重新賦值 s.len = 0 // 大小歸零 }
將集合轉(zhuǎn)化為切片
func (s *Set) List() []int { s.RLock() defer s.RUnlock() list := make([]int, 0, s.len) for item := range s.m { list = append(list, item) } return list }
二叉樹(shù):每個(gè)節(jié)點(diǎn)最多只有兩個(gè)兒子節(jié)點(diǎn)的樹(shù)。
滿(mǎn)二叉樹(shù):葉子節(jié)點(diǎn)與葉子節(jié)點(diǎn)之間的高度差為 0 的二叉樹(shù),即整棵樹(shù)是滿(mǎn)的,樹(shù)呈滿(mǎn)三角形結(jié)構(gòu)。在國(guó)外的定義,非葉子節(jié)點(diǎn)兒子都是滿(mǎn)的樹(shù)就是滿(mǎn)二叉樹(shù)。我們以國(guó)內(nèi)為準(zhǔn)。
完全二叉樹(shù):完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的,設(shè)二叉樹(shù)的深度為 k,除第 k 層外,其他各層的節(jié)點(diǎn)數(shù)都達(dá)到最大值,且第 k 層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊。
二叉樹(shù)結(jié)構(gòu)定義
// 二叉樹(shù) type TreeNode struct { Data string // 節(jié)點(diǎn)用來(lái)存放數(shù)據(jù) Left *TreeNode // 左子樹(shù) Right *TreeNode // 右字樹(shù) }
樹(shù)的遍歷
1、先序遍歷:先訪(fǎng)問(wèn)根節(jié)點(diǎn),再訪(fǎng)問(wèn)左子樹(shù),最后訪(fǎng)問(wèn)右子樹(shù)。
2、后序遍歷:先訪(fǎng)問(wèn)左子樹(shù),再訪(fǎng)問(wèn)右子樹(shù),最后訪(fǎng)問(wèn)根節(jié)點(diǎn)。
3、中序遍歷:先訪(fǎng)問(wèn)左子樹(shù),再訪(fǎng)問(wèn)根節(jié)點(diǎn),最后訪(fǎng)問(wèn)右子樹(shù)。
4、層次遍歷:每一層從左到右訪(fǎng)問(wèn)每一個(gè)節(jié)點(diǎn)。
// 先序遍歷 func PreOrder(tree *TreeNode) { if tree == nil { return } // 先打印根節(jié)點(diǎn) fmt.Print(tree.Data, " ") // 再打印左子樹(shù) PreOrder(tree.Left) // 再打印右字樹(shù) PreOrder(tree.Right) } // 中序遍歷 func MidOrder(tree *TreeNode) { if tree == nil { return } // 先打印左子樹(shù) MidOrder(tree.Left) // 再打印根節(jié)點(diǎn) fmt.Print(tree.Data, " ") // 再打印右字樹(shù) MidOrder(tree.Right) } // 后序遍歷 func PostOrder(tree *TreeNode) { if tree == nil { return } // 先打印左子樹(shù) MidOrder(tree.Left) // 再打印右字樹(shù) MidOrder(tree.Right) // 再打印根節(jié)點(diǎn) fmt.Print(tree.Data, " ") }
按層遍歷:
func Level(head *TreeNode) { if head == nil { return } // 用切片模仿隊(duì)列 var queue []*TreeNode queue = append(queue, head) for len(queue) != 0 { // 隊(duì)頭彈出,再把隊(duì)頭切掉,模仿隊(duì)列的poll操作 cur := queue[0] queue = queue[1:] fmt.Printf("%d", (*cur).Data) // 當(dāng)前節(jié)點(diǎn)有左孩子,加入左孩子進(jìn)隊(duì)列 if cur.Left != nil { queue = append(queue, cur.Left) } // 當(dāng)前節(jié)點(diǎn)有右孩子,加入右孩子進(jìn)隊(duì)列 if cur.Right != nil { queue = append(queue, cur.Right) } } }
上述內(nèi)容就是golang項(xiàng)目中有哪些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu),你們學(xué)到知識(shí)或技能了嗎?如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。