跳至主要內容
Heap

heap 是一种常见的数据结构,本周将带大家来了解一下 Go 语言标准库中的 Heap 包,首先在此之前我们需要对堆(heap) 有所概念,简单理解就是用数组实现的完全二叉树,在 Go 官方概述中有这样说道“堆是一棵树,其属性是每个节点都是其子树中的最小值节点”,那么堆的属性又是什么呢?

所谓的“堆属性”指的就是最大堆与最小堆,这两者之间最大的区别在于数据的排列方式不同,如图 1 所示在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小,在 Go 语言中所采用的是最小堆,树中最小的元素是根,索引为 0。


通过刚刚的讲述想必我们已经对堆有了一个基础的概念,那问题来了,虽然堆在物理结构上是一个一维的数组,但在存储逻辑上是一棵完全二叉树,所以堆的数据结构是非线性的,那它即没有指针指向当前节点的父节点或子节点,也没有多余的空间用来存储当前节点信息,我们该如何对当前节点元素完成父子节点的定位操作。


王泽权大约 10 分钟GoGo
List

今天给大家带来的是 Go 语言提供的内置容器 List,内部的实现原理是双链表,列表能够高效地进行任意位置的元素插入和删除操作。

List struct && Element struct

老规矩我们先从数据结构中看起,从 code - 1 中我们可以看到 List 包中的数据结构一共有两个分别为 List 和 Element,通过这两个数据结构组成为 Go 语言提供的内置容器 List 结构,接下来就让我们去看一看这两个数据结构。

List 数据结构,当前数据结构中包含 root 和 len 两个字段,从注解中我们可以了解到 root 为“哨兵”列表元素,不算在当前 List 链表元素中且结构体中 len 的长度属性中不记录 root 节点。


王泽权大约 10 分钟GoGo
Ring

今天给大家带来的是 Go 语言提供的内置容器 Ring,简单理解 Ring 就是一个双向循环链表,但 Ring 并没有表头与表尾的概念,Ring 的表头与表尾相连,构成一个环。

Ring 数据结构

老规矩我们先来了解一下 Ring 的数据结构,从 code - 1 中我们可以看到 Ring 的数据结构分别由两个指针 next、prev 和用于存储数据的 value 组成,首先从指针的命名中我们也可以得出是指向下一个或上一个 Ring 类型,简单思考一下,如图 1 通过这种数据结构我们可以创建一个环状的数据结构,有点像循环队列。

// src/container/ring/ring.go

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
type Ring struct {
	next, prev *Ring
	Value      any // for use by client; untouched by this library
}

王泽权大约 8 分钟GoGo
Sort

本周给大家带来的是 Go 语言标准库中的 sort 包, 该包提供了对切片和用户定义的集合进行排序的操作。

Introduce

在本篇文章开始之前,我们需要先对 sort 包中的内容要有一个大致的了解,这对于我们接下来的学习有很大的帮助,如图 1 所示画出一个大概的关系图,要知道 sort 包并不只是有排序功能的。


Data Type

首先我们先从 sort 中的数据类型看起,在刚刚所看的图 1 中我们可以看到 sort 包中,共定义了四种数据类型,其中有三种是我们一般情况下经常会用到的数据类型,Go 语言的开发者们已经为我们写好了所需要的方法,而除去这三种基础类型后,还提供了一个接口类型,我们只需要在我们定义的数据类型中实现了接口中的三个方法就可以完成排序操作。


王泽权大约 11 分钟GoGo
Channel

本周我们来看 Go 语言中的 channel,作为 Go 语言核心的数据结构,也是作为 goroutine 之间的通信方式,下面我们将通过一些测试代码来开始本周的 channel 的学习。

Overview

从 channel 关键字上来看大致意思为“管道”,如图 1 所示作为 Go 语言中 Goroutine 之间的通信方式。


Statement

channel 共有两种形式,分别是 Unbuffered channels 与 Buffered channels,在此之前我们需要先知道,这两种形式是如何声明的。


王泽权大约 8 分钟GoGo
String

类型说明

在 Go 语言中所提供的字符串(string)是一种基础的数据类型,在编程开发中几乎随时都会使用,本篇文章将会介绍字符串(string)的知识,帮助你更好的理解它。

// src/builtin/builtin.go

// string is the set of all strings of 8-bit bytes, conventionally but not
// necessarily representing UTF-8-encoded text. A string may be empty, but
// not nil. Values of string type are immutable.
type string string

王泽权大约 7 分钟GoGo
Slice

在上一篇中我们简单的了解了 slice ,在这一篇中我们将继续深入了解一下。

Slice 数据结构

首先我们先来看一下 Slice 的数据结构,从 code - 1** **中我们可以看到 Slice 是由 3 部分构成,首先第一是名为 unsafe.Pointer(通用指针类型) 类型的 array,从命名中我们可以得知它是一个指向 Array 的指针,其余两个皆为 int 类型分别为 len 和 cap 分别代表 Slice 当前的长度,另一个代表 Slice 当前的容量。

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

王泽权大约 5 分钟GoGo
Array

Go 语言中的数组可以简单理解为存储同一种数据类型且存储数量(长度)固定的序列,数组在规划内存的详细布局时很有用,它不仅是切片的构建块,Go 语言中许多基础的数据结构都是通过数组来实现数据的存储工作。

数组这个概念在许多语言中皆有存在,而 Go 语言是一门属于 C 语言家族的编程语言,但在 Go 语言和 C 语言中,数组的工作方式有很大的不同。

package main

import (
	"fmt"
    "reflect"
)

func show(x [4]int) {
    fmt.Printf("Address(Array) = %p --> %d\n", &x, x)
}

func compare(x [4]int, y [5]int) {
    fmt.Printf("copyArray == compareArray  %t \n", reflect.TypeOf(x) == reflect.TypeOf(y))
}

func main() {
    Array := [4]int{ 0, 1, 2, 3 }
    var copyArray [4]int
    var compareArray [5]int
    copyArray = Array

    fmt.Printf("copyArray --> %d \n", copyArray)
    fmt.Printf("Address(Array) = %p --> %d\n", &Array, Array)
    fmt.Printf("Address(copyArray) = %p --> %d\n", &copyArray, copyArray)
    show(Array)
    compare(copyArray, compareArray)
}

// L22: copyArray --> [0 1 2 3] 
// L23: Address(Array) = 0xc0000a0000 --> [0 1 2 3]
// L24: Address(copyArray) = 0xc0000a0020 --> [0 1 2 3]
// L25: Address(Array) = 0xc0000a00c0 --> [0 1 2 3]
// L26: copyArray == compareArray  false

王泽权大约 5 分钟GoGo