主頁(yè) > 知識(shí)庫(kù) > 使用go實(shí)現(xiàn)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

使用go實(shí)現(xiàn)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

熱門(mén)標(biāo)簽:湛江crm外呼系統(tǒng)排名 重慶慶云企業(yè)400電話到哪申請(qǐng) 鄭州智能語(yǔ)音電銷(xiāo)機(jī)器人價(jià)格 寧波語(yǔ)音外呼系統(tǒng)公司 宿遷便宜外呼系統(tǒng)代理商 不封卡外呼系統(tǒng) 地圖標(biāo)注免費(fèi)定制店 仙桃400電話辦理 上海極信防封電銷(xiāo)卡價(jià)格

1 golang常見(jiàn)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

1.1 鏈表

舉單鏈表的例子,雙向鏈表同理只是多了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
	}
}

1.2 可變數(shù)組

可變數(shù)組在各種語(yǔ)言中都非常常用,在golang中,可變數(shù)組語(yǔ)言本身已經(jīng)實(shí)現(xiàn),就是我們的切片slice。

1.3 棧和隊(duì)列

1.3.1 原生切片實(shí)現(xiàn)棧和隊(duì)列

棧:先進(jìn)后出,后進(jìn)先出,類(lèi)似彈夾

隊(duì)列:先進(jìn)先出

golang中,實(shí)現(xiàn)并發(fā)不安全的棧和隊(duì)列,非常簡(jiǎn)單,我們直接使用原生切片即可。

1.3.1.1 切片原生棧實(shí)現(xià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)
}
1.3.1.2 切片原生隊(duì)列實(shí)現(xiàn)
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)
}

1.3.2 *并發(fā)安全的棧和隊(duì)列

1.3.2.1 切片實(shí)現(xiàn)并發(fā)安全的棧并發(fā)安全的棧
// 數(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
}
1.3.2.2 切片實(shí)現(xiàn)并發(fā)安全的隊(duì)列隊(duì)列結(jié)構(gòu)
// 數(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
}

1.4 字典Map和集合Set

1.4.1 Map

字典也是程序語(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

1.4.2 Set

我們可以借助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
}

1.5 二叉樹(shù)

二叉樹(shù):每個(gè)節(jié)點(diǎn)最多只有兩個(gè)兒子節(jié)點(diǎn)的樹(shù)。

滿二叉樹(shù):葉子節(jié)點(diǎn)與葉子節(jié)點(diǎn)之間的高度差為 0 的二叉樹(shù),即整棵樹(shù)是滿的,樹(shù)呈滿三角形結(jié)構(gòu)。在國(guó)外的定義,非葉子節(jié)點(diǎn)兒子都是滿的樹(shù)就是滿二叉樹(shù)。我們以國(guó)內(nèi)為準(zhǔn)。

完全二叉樹(shù):完全二叉樹(shù)是由滿二叉樹(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、先序遍歷:先訪問(wèn)根節(jié)點(diǎn),再訪問(wèn)左子樹(shù),最后訪問(wèn)右子樹(shù)。

2、后序遍歷:先訪問(wèn)左子樹(shù),再訪問(wèn)右子樹(shù),最后訪問(wèn)根節(jié)點(diǎn)。

3、中序遍歷:先訪問(wèn)左子樹(shù),再訪問(wèn)根節(jié)點(diǎn),最后訪問(wèn)右子樹(shù)。

4、層次遍歷:每一層從左到右訪問(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)
		}
	}

}

到此這篇關(guān)于用go實(shí)現(xiàn)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)go實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

您可能感興趣的文章:
  • Golang中數(shù)據(jù)結(jié)構(gòu)Queue的實(shí)現(xiàn)方法詳解
  • Go語(yǔ)言模型:string的底層數(shù)據(jù)結(jié)構(gòu)與高效操作詳解
  • 淺析go中的map數(shù)據(jù)結(jié)構(gòu)字典
  • 淺談?dòng)肎o構(gòu)建不可變的數(shù)據(jù)結(jié)構(gòu)的方法
  • golang數(shù)據(jù)結(jié)構(gòu)之golang稀疏數(shù)組sparsearray詳解

標(biāo)簽:安康 儋州 海南 電子產(chǎn)品 西雙版納 青海 物業(yè)服務(wù) 遼寧

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《使用go實(shí)現(xiàn)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)》,本文關(guān)鍵詞  使用,實(shí)現(xiàn),常見(jiàn),的,數(shù)據(jù)結(jié)構(gòu),;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題,煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《使用go實(shí)現(xiàn)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)》相關(guān)的同類(lèi)信息!
  • 本頁(yè)收集關(guān)于使用go實(shí)現(xiàn)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章