使用go实现常见的数据结构

1 golang常见数据结构实现

1.1 链表

举单链表的例子,双向链表同理只是多了pre指针。

定义单链表结构:

type LinkNode struct {
	Data int64
	NextNode *LinkNode
}

构造链表及打印链表:

func main() {

	node := new(LinkNode)
	node.Data = 1

	node1 := new(LinkNode)
	node1.Data = 2
	node.NextNode = node1 // node1 链接到 node 节点上

	node2 := new(LinkNode)
	node2.Data = 3
	node1.NextNode = node2 // node2 链接到 node1 节点上

	// 顺序打印。把原链表头结点赋值到新的NowNode上
	// 这样仍然保留了原链表头结点node不变
	nowNode := node
	for nowNode != nil {
		fmt.Println(nowNode.Data)
		// 获取下一个节点。链表向下滑动
		nowNode = nowNode.NextNode
	}
}

1.2 可变数组

可变数组在各种语言中都非常常用,在golang中,可变数组语言本身已经实现,就是我们的切片slice。

1.3 栈和队列

1.3.1 原生切片实现栈和队列

栈:先进后出,后进先出,类似弹夹

队列:先进先出

golang中,实现并发不安全的栈和队列,非常简单,我们直接使用原生切片即可。

1.3.1.1 切片原生栈实现
func main() {
	// 用切片制作一个栈
	var stack []int
	// 元素1 入栈
	stack = append(stack, 1, 5, 7, 2)
	// 栈取出最近添加的数据。例如[1,5,7,2] ,len = 4
	x := stack[len(stack)-1] // 2
	// 切掉最近添加的数据,上一步和这一步模仿栈的pop。
	stack = stack[:len(stack)-1] // [1,5,7]
	fmt.Printf("%d", x)
}
1.3.1.2 切片原生队列实现
func main() {

	// 用切片模仿队列
	var queue []int
	// 进队列
	queue = append(queue, 1, 5, 7, 2)
	// 队头弹出,再把队头切掉,模仿队列的poll操作
	cur := queue[0]
	queue = queue[1:]

	fmt.Printf("%d", cur)
}

1.3.2 *并发安全的栈和队列

1.3.2.1 切片实现并发安全的栈并发安全的栈
// 数组栈,后进先出
type Mystack struct {
 array []string // 底层切片
 size int // 栈的元素数量
 lock sync.Mutex // 为了并发安全使用的锁
}

入栈

// 入栈
func (stack *Mytack) Push(v string) {
 stack.lock.Lock()
 defer stack.lock.Unlock()

 // 放入切片中,后进的元素放在数组最后面
 stack.array = append(stack.array, v)

 // 栈中元素数量+1
 stack.size = stack.size + 1
}

出栈

1、如果切片偏移量向前移动 stack.array[0 : stack.size-1],表明最后的元素已经不属于该数组了,数组变相的缩容了。此时,切片被缩容的部分并不会被回收,仍然占用着空间,所以空间复杂度较高,但操作的时间复杂度为:O(1)。

2、如果我们创建新的数组 newArray,然后把老数组的元素复制到新数组,就不会占用多余的空间,但移动次数过多,时间复杂度为: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]

 // 切片收缩,但可能占用空间越来越大
 //stack.array = stack.array[0 : stack.size-1]

 // 创建新的数组,空间占用不会越来越大,但可能移动元素次数过多
 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

 // 栈中元素数量-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 切片实现并发安全的队列队列结构
// 数组队列,先进先出
type Myqueue struct {
 array []string // 底层切片
 size int // 队列的元素数量
 lock sync.Mutex // 为了并发安全使用的锁
}

入队

// 入队
func (queue *Myqueue) Add(v string) {
 queue.lock.Lock()
 defer queue.lock.Unlock()

 // 放入切片中,后进的元素放在数组最后面
 queue.array = append(queue.array, v)

 // 队中元素数量+1
 queue.size = queue.size + 1
}

出队

1、原地挪位,依次补位 queue.array[i-1] = queue.array[i],然后数组缩容:queue.array = queue.array[0 : queue.size-1],但是这样切片缩容的那部分内存空间不会释放。

2、创建新的数组,将老数组中除第一个元素以外的元素移动到新数组。

// 出队
func (queue *Myqueue) Remove() string {
 queue.lock.Lock()
 defer queue.lock.Unlock()

 // 队中元素已空
 if queue.size == 0 {
 panic("empty")
 }

 // 队列最前面元素
 v := queue.array[0]

 /* 直接原位移动,但缩容后继的空间不会被释放
 for i := 1; i < queue.size; i++ {
 // 从第一位开始进行数据移动
 queue.array[i-1] = queue.array[i]
 }
 // 原数组缩容
 queue.array = queue.array[0 : queue.size-1]
 */

 // 创建新的数组,移动次数过多
 newArray := make([]string, queue.size-1, queue.size-1)
 for i := 1; i < queue.size; i++ {
 // 从老数组的第一位开始进行数据移动
 newArray[i-1] = queue.array[i]
 }
 queue.array = newArray

 // 队中元素数量-1
 queue.size = queue.size - 1
 return v
}

1.4 字典Map和集合Set

1.4.1 Map

字典也是程序语言经常使用的结构,golang中的字典是其自身实现的map结构。具体操作可以查看语言api

并发安全的map,可以定义结构,结构中有一个map成员和一个锁变量成员,参考并发安全的栈和队列的实现。go语言也实现了一个并发安全的map,具体参考sync.map的api

1.4.2 Set

我们可以借助map的特性,实现一个Set结构。

Set结构

map的值我们不适用,定义为空的结构体struct{}

// 集合结构体
type Set struct {
 m map[int]struct{} // 用字典来实现,因为字段键不能重复
 len int // 集合的大小
 sync.RWMutex // 锁,实现并发安全
}

初始化Set

// 新建一个空集合
func NewSet(cap int64) *Set {
 temp := make(map[int]struct{}, cap)
 return &Set{
 m: temp,
 }
}

往set中添加一个元素

// 增加一个元素
func (s *Set) Add(item int) {
 s.Lock()
 defer s.Unlock()
 s.m[item] = struct{}{} // 实际往字典添加这个键
 s.len = len(s.m) // 重新计算元素数量
}

删除一个元素

// 移除一个元素
func (s *Set) Remove(item int) {
 s.Lock()
 s.Unlock()

 // 集合没元素直接返回
 if s.len == 0 {
 return
 }

 delete(s.m, item) // 实际从字典删除这个键
 s.len = len(s.m) // 重新计算元素数量
}

查看元素是否在集合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
}

查看集合是否为空

// 集合是够为空
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 // 大小归零
}

将集合转化为切片

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 二叉树

二叉树:每个节点最多只有两个儿子节点的树。

满二叉树:叶子节点与叶子节点之间的高度差为 0 的二叉树,即整棵树是满的,树呈满三角形结构。在国外的定义,非叶子节点儿子都是满的树就是满二叉树。我们以国内为准。

完全二叉树:完全二叉树是由满二叉树而引出来的,设二叉树的深度为 k,除第 k 层外,其他各层的节点数都达到最大值,且第 k 层所有的节点都连续集中在最左边。

二叉树结构定义

// 二叉树
type TreeNode struct {
 Data string // 节点用来存放数据
 Left *TreeNode // 左子树
 Right *TreeNode // 右字树
}

树的遍历

1、先序遍历:先访问根节点,再访问左子树,最后访问右子树。

2、后序遍历:先访问左子树,再访问右子树,最后访问根节点。

3、中序遍历:先访问左子树,再访问根节点,最后访问右子树。

4、层次遍历:每一层从左到右访问每一个节点。

// 先序遍历
func PreOrder(tree *TreeNode) {
 if tree == nil {
 return
 }

 // 先打印根节点
 fmt.Print(tree.Data, " ")
 // 再打印左子树
 PreOrder(tree.Left)
 // 再打印右字树
 PreOrder(tree.Right)
}

// 中序遍历
func MidOrder(tree *TreeNode) {
 if tree == nil {
 return
 }

 // 先打印左子树
 MidOrder(tree.Left)
 // 再打印根节点
 fmt.Print(tree.Data, " ")
 // 再打印右字树
 MidOrder(tree.Right)
}

// 后序遍历
func PostOrder(tree *TreeNode) {
 if tree == nil {
 return
 }

 // 先打印左子树
 MidOrder(tree.Left)
 // 再打印右字树
 MidOrder(tree.Right)
 // 再打印根节点
 fmt.Print(tree.Data, " ")
}

按层遍历:

func Level(head *TreeNode) {

	if head == nil {
		return
	}

	// 用切片模仿队列
	var queue []*TreeNode
	queue = append(queue, head)

	for len(queue) != 0 {
		// 队头弹出,再把队头切掉,模仿队列的poll操作
		cur := queue[0]
		queue = queue[1:]

		fmt.Printf("%d", (*cur).Data)

		// 当前节点有左孩子,加入左孩子进队列
		if cur.Left != nil {
			queue = append(queue, cur.Left)
		}

		// 当前节点有右孩子,加入右孩子进队列
		if cur.Right != nil {
			queue = append(queue, cur.Right)
		}
	}

}

到此这篇关于用go实现常见的数据结构的文章就介绍到这了,更多相关go实现数据结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Golang中数据结构Queue的实现方法详解

    前言 本文主要给大家介绍了关于Golang中数据结构Queue实现的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 需求 队列的特性较为单一,基本操作即初始化.获取大小.添加元素.移除元素等.最重要的特性就是满足先进先出. 实现 接下来还是按照以前的套路,一步一步来分析如何利用Go的语法特性实现Queue这种数据结构. 定义 首先定义每个节点Node结构体,照例Value的值类型可以是任意类型,节点的前后指针域指针类型为node type node struct {

  • JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

    排序算法的介绍 排序也称排序算法 (Sort Algorithm),排序是将 一组数据 , 依指定的顺序 进行 排列的过程 . 排序的分类 1)  内部排序 : 指将需要处理的所有数据都加载 到 内部存储器(内存) 中进行排序. 2) 外部排序法: 数据量过大,无法全部加载到内 存中,需要借助 外部存储(文件等) 进行 排序. 常见的排序算法分类 算法的时间复杂度 度量一个程序(算法)执行时间的两种方法 1.事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,

  • 浅析go中的map数据结构字典

    1. map的使用 golang中的map是一种数据类型,将键与值绑定到一起,底层是用哈希表实现的,可以快速的通过键找到对应的值. 类型表示:map[keyType][valueType] key一定要是可比较的类型(可以理解为支持==的操作),value可以是任意类型. 初始化:map只能使用make来初始化,声明的时候默认为一个为nil的map,此时进行取值,返回的是对应类型的零值(不存在也是返回零值).添加元素无任何意义,还会导致运行时错误.向未初始化的map赋值引起 panic: ass

  • MongoDB系列教程(七):MongoDb数据结构详解

    首先,向数据库插入一条bjson数据 首先是定义文档,然后使用admin用户名密码登录,进入test数据库,向test数据库中插入此文档("表名称和表中的记录") 插入结果,查看mongoVUE如下图所示 从上图可以看出系统自带的三个数据库,local,admin,test,在加入一条记录的时候,会自动生成_id的自动标识. 我们再添加图片,可以使用mongoVUE添加,如下图所示. Collections:在mongodb中叫做集合,是文档的集合.无模式,可以存储各种各样的文档.类似

  • 浅谈用Go构建不可变的数据结构的方法

    共享状态是比较容易理解和使用的,但是可能产生隐晦以至于很难追踪的 bugs.尤其是在我们的数据结构只有部分是通过引用传递的.切片就是这么一个很好的例子.后续我会作出更加详细的讲解. 在处理经过多级变换或状态的数据时,不可变数据结构是非常有用的.不可变仅意味着原始结构是不可以被改变的,而每一个新的结构副本都是以新的属性值创建. 让我们看个简单的例子: type Person struct { Name string FavoriteColors []string } 显然,我们可以实例化一个Per

  • Go语言模型:string的底层数据结构与高效操作详解

    Golang的string类型底层数据结构简单,本质也是一个结构体实例,且是const不可变. string的底层数据结构 通过下面一个例子来看: package main import ( "fmt" "unsafe" ) // from: string.go 在GoLand IDE中双击shift快速找到 type stringStruct struct { array unsafe.Pointer // 指向一个 [len]byte 的数组 length in

  • 使用go实现常见的数据结构

    1 golang常见数据结构实现 1.1 链表 举单链表的例子,双向链表同理只是多了pre指针. 定义单链表结构: type LinkNode struct { Data int64 NextNode *LinkNode } 构造链表及打印链表: func main() { node := new(LinkNode) node.Data = 1 node1 := new(LinkNode) node1.Data = 2 node.NextNode = node1 // node1 链接到 nod

  • Java常见基本数据结构概览

    Java数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科.在Java数据结构中最常用的类型无外乎以下几种: Map接口 请注意,Map没有继承Collection接口,Map提供key到value的映射.一个Map中不能包含相同的key,每个key只能映射一个value. Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射. List接口 List是有序的Collection,用户能

  • Java常见基础数据结构

    目录 栈: 队列: 数组: 链表: 红黑树: 总结 栈: stack,又称堆栈,他是运算受限的线性表,其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行添加.查找.删除等操作. 简单的来说,采用该结构的集合,对元素的存取有如下几个特点 1.先进后出. 2.栈的入口.出口都是栈的顶端位置. 压栈:就是存元素,把元素存储到栈的顶端位置,栈中已有元素一次向栈底方向移动一个位置. 弹栈:就是取元素,把栈顶端的元素取出,栈中已有元素依次向栈顶方向移动一个位置. 队列: queue,简称队

  • Python常见数据结构详解

    本文详细罗列归纳了Python常见数据结构,并附以实例加以说明,相信对读者有一定的参考借鉴价值. 总体而言Python中常见的数据结构可以统称为容器(container).而序列(如列表和元组).映射(如字典)以及集合(set)是三类主要的容器. 一.序列(列表.元组和字符串) 序列中的每个元素都有自己的编号.Python中有6种内建的序列.其中列表和元组是最常见的类型.其他包括字符串.Unicode字符串.buffer对象和xrange对象.下面重点介绍下列表.元组和字符串. 1.列表 列表是

  • JavaScript数据结构与算法之链表

    链表简介 链表是一种常见的数据结构,也属于线性表,但不会按线性的顺序来储存数据.而是在每一个节点中,储存了下一个节点的指针.可以看图理解.(有C语言基础的可能比较好理解). 使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度),链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理. 接下来就是介绍两种常见的链表: 单向链表,双向链表在JavaScript中的实现. 单向链表 链表中最简单的形式就是单向链表,链表中的节点都包含两个部分,第一部分储存着自身信息,第

  • JavaScript数据结构之链表的实现

    前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

  • 理解数据结构

    从宏观上理解数据结构     1.数据结构对编程为什么如此重要? 现在就根据我自己的体会来为大家阐述一下数据结构对我们编程为什么如此重要.记得在开始学习编程的时候,对数据结构没什么概念,感觉编程就是那么回事,不用数据结构也能编出一大堆程序,然而我只能说那都是些小孩子过家家玩的小程序而已,程序中几乎没有用到多少数据,无论你怎么存储,程序运行起来都是很快的.然而当你为工程应用去编写程序的时候,那都是处理大批的数据,那时候就不能随便乱存储数据了,必须根据实际情况选择一种合适的数据结构来存储数据,从而能

  • 浅谈Python编程中3个常用的数据结构和算法

    本篇文章将介绍3种常见的数据结构和同数据有关的算法.此外,在collections模块中也包含了针对各种数据结构的解决方案. Python内置了许多非常有用的数据结构,比如列表(list).集合(set)以及字典(dictionary).就绝大部分情况而言,我们可以直接使用这些数据结构.但是,通常我们还需要考虑比如搜索.排序.排列以及筛选等这一类常见的问题. 本篇文章将介绍3种常见的数据结构和同数据有关的算法.此外,在collections模块中也包含了针对各种数据结构的解决方案. 1. 将序列

  • JS中的算法与数据结构之列表(List)实例详解

    本文实例讲述了JS中的算法与数据结构之列表(List).分享给大家供大家参考,具体如下: 前言 前端很少有机会接触到算法,大多都交互性的操作,所以不少前端工程师会抱着这么一种想法:我是做前端的,为什么要学数据结构与算法?没有数据结构与算法,我一样很好的完成工作.实际上,算法是一个宽泛的概念,我们平时写的任何代码都可以成为算法,它是对一个问题的解决方案的准确而完整的描述,是解决一系列问题的清晰指令,它代表着用系统的方法描述解决问题的策略机制.随着现在互联网的飞速发展,前端工程师已不是靠几个选择器操

  • JavaScript数据结构与算法

    目录 前言 数据结构 常见的数据结构 算法 算法的特征 算法的目标 总结 前言 数据结构与算法这个词相信大家都听过.了解过.学过,那为什么要学习数据结构与算法呢?我感觉有以下两个原因: 为了一个比较满意的Offer,现在去面试任何一家公司,不管你是前端还是后端,多多少少会问一些关于算法的问题: 编程需要,如果没有很好的数据结构与算法的功底,很多事情都是知其然不知其所以然,无法深入的学习,还有就是随着项目的复杂,数据量也随之变大,数据结构与算法可以更优雅的处理这些数据. 程序=数据结构+算法,是计

随机推荐