手撸golang 基本数据结构与算法 图的搜索 深度优先/广度优先

最近阅读我的第一本算法书(【日】石田保辉；宫崎修一)

创新互联专注于平城网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供平城营销型网站建设，平城网站制作、平城网页设计、平城网站官网定制、微信小程序开发服务，打造平城网络公司原创品牌,更为您提供平城网站排名全网营销落地服务。

本系列笔记拟采用golang练习之

graph_visit_test.go

顶点接口

图的遍历器接口

顶点的实现

候选节点队列接口. 候选节点的选择方式不同, 决定了是深度优先还是广度优先.

LIFO堆栈, 实现INodeQueue接口

FIFO队列, 实现INodeQueue接口

遍历器, 实现IGraphVisitor接口

(end)

C，C++，MATLAB，Python，Go 哪个比较适合写算法

仅仅就学习算法，还是C++/Java/C#最适合。

首先，没泛型的语言未必工作不好用，我司现在服务端代码几乎都是go，但是没有泛型，写通用的代码就是不好用。我用Go把半本《算法》实现了一遍，移植了Haskell 的 Parsec 库。这些代码大部分都在我团队的项目里实际使用。你要说 Go 有多熟练未必，但是要说它在语言功能上有多少坑我倒是挺熟悉。没泛型的话算法实现起来太坑人了，别的不说 float32/float64/int8/int16/int32/int64/int 这些数值类型你能都覆盖么？如果只是基于某一组有限的数据类型和问题领域实现一遍，用 go 倒是不错，它环境配置容易，不太依赖ide，但是对ide还是比较友好的，天然集成test，编译快速，模型简单，学习容易，可以说是我用过的静态编译型语言里最像动态脚本语言，最适合快速开发微型工具的。

其次，Python/Ruby 这类语言其实不太适合练习算法实现，它们太“高级”了。例如用Python的时候，你很难规避它的内置容器List和Dict，这些东西封装了太多东西，在学习的过程中容易被干扰。另外没有静态的类型控制，在学习过程中也会失去一些知识。倒不是就会导致你后半生这部分都不能自理，但是需要另外学习。

在我的经验，要学习算法，C++/C#/Java 仍然是比较好的选择，它们的泛型已经比较成熟，能够在学习中建立比较完备的知识概念。可以找到一些比较好的IDE用，我个人其实在工作中不怎么用IDE，但是算法学习的时候，有个不错的IDE可以帮你跟踪代码的运行过程，还能比较容易的做性能分析，这样就可以用动态、直观、形象的视角去理解和观察算法。这对学习非常有帮助。

如果只是在一个特定的领域做知识学习的工具，其实C++反而不算很难，C++的难度主要在于覆盖的领域太广泛，当你要做一个专业的C++程序员，要掌握的东西就太多了。

个人不太建议用C去学习这些东西，需要处理太多跟问题本身无关的事情了。

2022 年将成为主导的顶级编程语言

编程语言是程序员（开发人员）用来与计算机进行通信的计算机语言。它是用任何特定语言（C、C++、Java、Python）编写的一组指令，用于执行特定任务。编程语言主要用于开发桌面应用程序、网站和移动应用程序。以下是 2022 年最流行的顶级语言。

Python

Python 是由 Guido van Rossum 于 1980 年代后期在荷兰构建的。Python 最初是作为 Java 在行业中的竞争对手而构建的，后来逐渐流行起来。目前，Python 在研究人员和开发人员社区中都非常受欢迎。Python 在 IEEE Spectrum 的语言排名中名列前茅，得分为满分 100。此外，Python 也很受尊重，支持率高达 44.1%。

Python 几乎适用于任何事物。Django 和 Flask 可用于 Web 开发，而 Jupyter 和 Spyder 等科学工具则用于分析和研究目的。如果您喜欢自动化，Selenium 可以帮助您！该语言的灵活性使 Python 几乎可以在任何地方使用。到目前为止，这些是 Python 中比较流行的产品。Python 的巨大支持基础（仅次于 JavaScript）产生了大量使用该语言的包、框架，甚至是成熟的开源软件。

总的来说，Python 可能对数据科学和机器学习有最大的支持。虽然还有其他语言（如 R 和 MATLAB）提供竞争，但 Python 是数据科学领域的严格统治者。机器学习中使用的大多数框架和库都仅用 Python 编写，如果想要学习机器学习（或一般的数据科学），它可能是最好的语言。

JavaScript

JavaScript 在这一点上几乎是行业领导者。JavaScript 最初于 1994 年作为 Netscape Navigator（当时最好的浏览器之一）的脚本语言而构建，它迅速崛起。直到 2008 年，Google 才在为 Google Chrome 构建 V8 引擎时设计了现代 JavaScript。最初由 Netscape 构建为 Java 的竞争对手，JavaScript 现在在开发领域拥有自己的空间。JavaScript 因其流行而被广泛认为是“互联网语言”。JavaScript 在开发者社区中的支持率最高——高达 67.7%。一般来说，JavaScript 适用于任何类型的开发活动，如移动应用程序开发、Web 开发、桌面应用程序开发等。

JavaScript 有各种各样的库和框架，可以在开发过程中使用。有用于前端开发的 Angular、Vue 和 React，而 Node.js 是一种用于后端开发的非常灵活的语言。Jest 和 Mocha 是两个灵活的工具，可帮助设置单元测试以检查功能是否按预期工作。当然，如果您对其中任何一个都不太满意，您可以在前端使用普通的 HTML、CSS 和 JavaScript——就这么简单！由于来自世界各地开发人员的巨大支持，JavaScript 拥有任何语言都可以夸耀的最多数量的支持包。尽管如此，人们继续构建越来越多的包，以增加使用该语言的便利性。

Java

Java 由 James Gosling、Mike Sheridan 和 Patrick Naughton 于 1991 年构建为“Oak”语言，是第一种在全球产生重大影响的语言。虽然新的编程语言使用与 C/C++ 相同的格式，但它融入了某些新思想，使其对更多人更具吸引力。Java 运行的原则是“一次编写，随处运行”——这意味着具有不同硬件和操作系统配置的系统可以轻松运行 Java 程序。

Java 也有各种各样的库和框架，它们在底层使用 Java。Java 用于通过 Spring 和 Hibernate 进行应用程序开发。JUnit 帮助我们为 Java 项目设置单元测试。最重要的是，Java 被用于开发原生 Android 应用程序（Android SDK 本身由 Java 开发工具包或 JDK 提供支持）。Java 可能是大多数人在大学或学校的计算机编程入门课程中被介绍的语言。Java 是用于向大众教授面向对象编程的语言。

Java 在分析和研究领域也备受推崇。Java 唯一的问题是目前该语言的支持包和项目很少。很少有社区参与——这是大多数主流语言都有的。尽管如此，Java 是一种非常容易掌握和学习的语言——这在一定程度上解释了该语言的吸引力。但是，要掌握某种形式的语言确实需要一些时间。

C++

也许人们在本文中可以期待的最令人震惊的答案之一是 C++。尽管是大多数人用来学习数据结构和算法概念的语言，但该语言本身在实际世界中却很少使用。C++ 最初由 Bjarne Stroustrup 于 1982 年创建，作为 C 编程语言的扩展，在接下来的几年中继续声名鹊起。

C++ 可用于分析、研究以及 游戏 内开发。流行的 游戏 开发引擎——虚幻引擎——使用 C++ 作为脚本语言，用于构建 游戏 时可以定义的所有功能。C++ 在软件开发中也有广泛的用途。介于面向对象方法和面向方法方法之间，C++ 可以灵活地使用它生成的软件的性质。在 TIOBE 指数中排名第 4 意味着 C++ 至今仍具有吸引力。C++也广泛用于系统软件开发，比其他语言更容易理解。在操作系统等敏感领域使用 C++ 的主要原因是 C++ 程序的编译时间非常短。

C++ 可能拥有所有语言中最大的学习社区。大多数学生会开始他们的算法课程，用 C++ 构建树、链表、堆栈、队列和许多其他数据结构。当然，只要注意细节，它就很容易上手和学习，也很容易掌握。

Typescript

TypeScript 是 JavaScript 的超集，具有与 JavaScript 几乎相同的应用程序。TypeScript 可用于 Web 开发、移动应用程序开发、桌面应用程序开发等。在 StackOverflow 的最受欢迎语言列表中，TypeScript 是第二受欢迎的语言，受到 67.1% 的开发人员的喜爱（仅次于 Rust）。

TypeScript 主要是一种用于开发的语言，因此它对科学界没有太大吸引力。但是，由于 TypeScript 的新功能，可以预期它可能会激发更大程度的研究兴趣。该语言的技能上限比 JavaScript 低得多——并且 JavaScript 的许多“难以理解”的行为已在 TypeScript 中得到简化。换句话说，您将头撞到墙上的机会略小。

Golang

新语言正在迅速崛起，新的竞争者即将挑战 JavaScript 和 Python 拥有的宝座。由谷歌（两者的名字中都有“Go”！）主要是为了推进函数式编程的事业，Golang 在短时间内建立了大量的追随者。Golang 已经成为 StackOverflow 第五大最适合学习的语言，受到 62.3% 的开发人员的喜爱。

Golang 用于多个领域，用于开发强大的软件以及用于 Web 和移动应用程序的后端。目前，Golang 甚至支持一些基本的 Web 开发。虽然它仍处于取代 JavaScript 作为网络语言的阶段，但它正在迅速成为支持下一阶段网络的语言。

Golang 比此列表中的其他语言更难学习。此外，Golang 是一种开源语言，每次重大更新都会频繁更改，因此保持更新是必要的。

Dart

Dart 是工业领域发展最快的语言之一。谷歌在语言领域的贡献显着增加，以与微软的 TypeScript 日益流行的竞争相抗衡。Dart 因其简单性而受到世界各地程序员的高度喜爱。

Dart 用于多平台应用程序开发。与 JavaScript 一样，Dart 用于构建任何人都可以使用电子设备运行的软件。目前 Dart 最著名的用途是 Flutter 框架，Flutter 是一种用于移动应用程序开发的语言。最近的谷歌趋势表明，Flutter 尽管是一个较新的框架，但比 React Native 更受欢迎，后者是业界已经建立的移动应用程序开发框架。

Dart 比 JavaScript 更容易学习，并且能够很好地简化甚至难以理解的案例。随着市场上的 TypeScript 和 Dart 的出现，程序员在选择一种他们真正想要学习的语言时会面临多种选择。

Go小知识新解

1、值接收者和指针接收者

所谓指针接收者和值接收者这两个概念，用GO写了一阵子代码的人都了解了，这里只做简要说明一下，也就是对于一个给定结构，咱们对结构进行方法包装的时候，固定必传的参数，用来指向这个对象结构自身的一个参数，在go中也就是形式如下：

我们对结构体testStruct进行了包装，提供了两个方法，sum和modify，其中sum的方法接收者为a testStruct，这个就是值接收者，而modify的接收者为a *testStruct就是指针接收者，也就是说固定对象指针，一个传递的是指针地址，而另外一个直接传递的是结构值拷贝了

对指针有一定了解的，都可以知道，指针传递过去的，可以直接修改结构内部内容，而值传递过去的，无论如何修改这个接收者的数据，不会对原对象结构产生影响。而对于咱们包装结构对象的时候，到底是使用指针还是使用值接收者，这个实际上没有太大的定论，就我个人的观点来说，如果结构体占有的内存空间不大(kb级别)，而又不需要修改内部的，同时结构对象内部没有同步对象比如（sync包中的mutex,rwlock，waitgroup等之类的结构的话，可以直接值传递，实际上值copy也没有咱们想象的那么慢，很多时候，都用指针，最后的gc回收扫描可能都比咱们这个传递copy的消耗大） p="" /kb级别)，而又不需要修改内部的，同时结构对象内部没有同步对象比如（sync包中的mutex,rwlock，waitgroup等之类的结构的话，可以直接值传递，实际上值copy也没有咱们想象的那么慢，很多时候，都用指针，最后的gc回收扫描可能都比咱们这个传递copy的消耗大）

2、实现接口的值接收者和指针接收者有啥区别

也就是比如定义如下

这里面的值接收者和指针接收者有什么区别，这里咱来写一个测试

通过这个测试用例可以发现，指针接收者实现的接口可以同时支持转移到值接收者接口和指针接收者接口，而用值接收者实现的接口，则无法转移到使用指针接收者实现的接口，为啥子呢？目前网上或者各类资料上都是给的一个很官方很官方，而且很书面话难以理解的说明，大致意思如下：

这是目前网络或者各种资料上都是差不多是这样说的，看似讲了，实际上就说了一个结果，根本就没说出来一个为什么。这样的总结出来，一个初学者的角度来看，是很不好理解的，初学者要么就是死记硬背，要么就是生搬硬套，甚至直到写了好多好多代码了，都还没有搞明白一个为啥子，只是会用了而已，从长远来说这是不利于自身提高的。

有这两个本质点，咱们自己来思考一下，如果你来实现这个编译器的时候，用指针接收的时候，指针接收者，默认就能直接获取支持，而值接收者实现接口的咱们可以直接来一个解指针就变成了值，就能匹配上值接收者实现的接口了，反过来说，如果值接收者，此时要匹配指针接收者，如何匹配呢，取一个地址就变成了指针了，此时数据类型确实是匹配了，但是，地址指向的数据区不对了，因为我们刚刚说了值接收者拷贝了一个新值之后是完全的一个新的对象，这个新对象和原始对象一点关系都没有，咱们取地址，取的也是这个新对象地址，对这个地址进行操作，也是这个新对象的内部数据，和原始数据内部没有任何关系，所以由此就能推断出，这个是为啥子值接收者不能匹配上指针接收者，而指针接收者却可以匹配上值接收者了。

1、在某个作用域内部，所有定义的字符串的数据区相同

这个很好验证，代码如下：

2、字符串相加会产生一个新串

这个也很好验证

3、字符串真的是不可变的吗

实际上从字符串的结构

从这个结构，就能大致的推断出来，字符串设计成这样就不具备直接扩容+来增加新数据，而如果咱们直接使用string[index] = 'a'，用这种方式，就不能编译通过，官方也确定说字符串是不可变的。那么真的是不可变的吗？

通过上面的结构，在加上go的slice切片的数据结构

由此可见，咱们可以将字符串通过指针方式强转为一个byte数组指针，然后通过byte切片来修改，试试

编译通过，运行报错

unexpected fault address 0xae2e27

fatal error: fault

这个错误，基本上就是一个内存的保护错误，是写异常，所以说明了，这个肯定做了内存写保护，那么直接修改一下内存区的属性，去掉他的写保护，就能写了

以下代码都是在Win平台，Go1.18，Win上修改内存权限属性，使用VirtualProtect,代码如下

此时运行，就能发现tstr的内容被咱们变了，这种情况实际上在实际开发中不具有实际意义，因为本身在语言层面，已经做了层层限制，咱们这是属于非法强制的操作方式，是流氓行为，那么是否有比较温和一点的操作方式呢？答案是有的，且往下看。

通过上面，我们已经用到了字符串结构，切片结构，要想字符串内容可变，那么咱们自己构造字符串的数据内容区域，且让这个数据区木有内存写保护不就行了，内容区可变，GO原生态的byte数组不就行嘛，所以咱们自己构造一下

此时我们直接修改buffer的内容，就是直接修改了str的数据内容了。而又不会像前面的一样遇到内存写保护

4、字符串转换优化时可能碰到的坑

通过前面讨论的字符串的可变性的方法，咱们可以知道，很多时候，[]byte到字符串的转变，可以直接构造其结构，而共享数据，从而达到减少数据内存copy的方式来进行优化，再使用这些优化的时候，一定需要注意，字符串或者数组的生命周期，是否会存在被改写的情况，从而导致前后不一致的问题。

比如下面这段代码：

大家可以猜想一下，这个最后里面的数据mmp中，"test"的value是多少,"abcd"的value是多少，然后想想为什么，且等端午之后，再来分解

数据结构和算法对于每种编程语言都不一样吗

正好相反，对于每种语言都一样。它只是一种思想而已，只是具体在不同语言上的实现可能会有些差别……不过，除了 C 类和 Pascal 类语言以外，其它语言基本没有搞数据结构的意义。

分享名称：数据结构与算法go语言 go 结构
网页URL：http://lswzjz.com/article/hgspcd.html