阿里云
为了无法计算的价值
打开APP
阿里云APP内打开
学习中心> Go语言核心编程 - 数据结构和算法> 正文

Go语言核心编程 - 数据结构和算法

47课时 |
1570人已学 |
免费
课程介绍

Go语言核心编程全套课程:

  1. 基础语法、数组、切片、Map
  2. 面向对象、文件、单元测试、反射、TCP编程
  3. 数据结构和算法(本课程)

Go语言简介

Go语言,也称为Golang,是Google开发的一种静态强类型、编译型、并发型,并具有垃圾回收功能的编程语言。

Go语言官网:https://golang.google.cn/

Go语言特性:

  • 跨平台的编译型语言(源代码编译生成机器语言,然后由机器直接执行机器码即可执行)
  • 语法接近C语言
  • 管道(channel),切片(slice),并发(routine)特性
  • 有垃圾回收的机制
  • 支持面向对象和面向过程的编程模式

Go 语言优势:

  • 编程模式比较简单,没有复杂的设计模式
  • 全部源码编译到一个文件,编译速度很快
  • 最新版本有动态库形式,对跨语言调用的支撑更到位
  • 开源框架比较成熟
  • 独有的语言特性和设计模式routine、channel、sync包支撑了海量并行的支持
  • 擅长于微服务开发、服务开发、Web API开发、分布式服务开发等
  • 对高并发、高性能的系统和服务支撑,Go语言对比其他语言有更快的开发速度,更高的开发效率

 

数据结构和算法的基本介绍

 

内容简介:

  1. 数据结构(算法)的介绍
  2. 数据结构和算法的关系
  3. 几个实际编程中遇到的问题

 

 

一、数据结构(算法)的介绍

(1)数据结构的介绍

数据结构就是数据的一种组织的一种方式,也就是在编程和解决实际问题过程中,很多程序员他们发现有很多实际要解决的问题,都可以通过一种结构,都可以通过一种通用的一种模型或者一种结构来解决,于是就产生了一种叫结构的东西。在结构基础之上,才能产生这个算法。

 

(2)数据结构的用处

数据结构有什么用?

数据结构可以这样理解,就好像去做程序的一个基本功一样。或者你去踢球,实际上有一样东西看起来没有什么用,比如奔跑的速度跟射门好像没有直接关系,但是跑得慢了,是永远不能把球带到球门上的,那么这个数据结构它是什么?

它就是像做程序员开发的一种,是很重要的一种内功,当把数据结构学完了之后,会突然发现,有好多这种比较麻烦的问题,如果用数据结构来解决,会发现很容易就解决了。如果脑海里面没有数据结构这个概念,会发现不知道怎么去解决,感觉一头雾水。

 

(3)应用案例分析

①比如原先我在工作的时候,我们 CEO 就跟我说:我这边给了你一堆用户的 ID ,然后他要求我不能过数据库,按照一个从小到大的顺序返回,但是不能过数据库,因为过数据库这么多 ID ,你过数据库,速度会变得很慢,数据库就撑不住,如果当时我没有学列表的插入方式,那我肯定就解决不了这问题,因为这个问题完全可以用列表来解决。因为列表,它是可以再从一个头结点,在加入的时候,在内存里面就形成一个列表,而且保证是从小到大,或者从大到小的顺序,然后把列表做好以后,直接把列表按照一种方式给你打回去,就可以了。

 

②再比如当时有这样一个东西,当时做这个项目时有这么一个小案例,很经典的两个案例,一个叫做排号,比如开发一个项目,这个项目就是让去做一个系统,那么这个系统就要解决一个问题,就是说哪个人来了,比如一个人来了,在银行要去办业务,办业务的话得讲一个先后顺序,它会有一个号,有一个业务员给一个客户服务完毕过后,他会按下这个键,该某某某号到我这来服务,然后这个人走了过后,另外有几个窗口,有五个六个十个都有可能,下面排队的客户有很多,服务完了之后,服务人员就按下红色按钮,说到我这里来,其实如果学过队列,就感觉有思路了,这其实就是队列,

 

先如下代码:

Microsoft Windows [版本 6.1.7601]

版权所有 <c> 2009 Microsoft Corporation. 保留所有权利。

C:\vaora\Adninistrator\Dosktop\尚硅谷 韩顺平 Go语言核心编程\课件\算法项目案例 资料\队列银行排队叫号>java Mybank

代码实现结果如下:

 

可以看到这里可以产生很多的,这个相当于是一个服务人员,他服务完了,去叫号,叫号过了,这个就飘过去,最后服务完毕,它有服务时间,服务完毕后大家都消失。如果在这种系统里,要没有队列的概念在里面,要怎么做到。

 

③再看一个案例,输入如下代码:

Microsoft Windows [版本 6.1.7601]

版权所有 <c> 2009 Microsoft Corporation. 保留所有权利。

C:\vaora\Adninistrator\Dosktop\尚硅谷 韩顺平 Go语言核心编程\课件\算法项目案例 资料\队列银行排队叫号>java Mybank

业务员 4 -> 1

业务员 1 -> 2

业务员 2 -> 3

业务员 3 -> 4

业务员 4 -> 5

业务员 2 -> 6

业务员 4 -> 7

业务员 1 -> 8

业务员 3 -> 9

业务员 2 -> 10

业务员 4 -> 11

业务员 1 -> 12

业务员 3 -> 13

代码测试结果为:

这里还写着业务员四号为谁服务,都有指向,肯定都玩过这种汉诺塔小游戏, Tutor 回撤,就是将这边的盘子 A 塔的,按照这个顺序搬到 C 塔,但是有个前提就是大小盘子才能上,小盘子在上面大盘子在下边,不能颠倒过来,那现在有这样一个题:

 

只有五个这样的盘子移动,一般的大脑是可以反应过来的,但是这个盘子要是64个的话,我估计一般人基本就 game over 了,全部搬过去的话,是一个非常复杂的过程,一般的人肯定是完成不了,但是如果你有这个回递归溯的思想,也能把它搞定,它已经告诉你怎么做了,这个底层就是一个小算法,其实它在这里就用到一些递归的东西,这个很标准的一步一步的走,按照这个流程,只要告诉它怎么做,它就可以把这个东西给做完,大概是20多步,不到30步,越到最后就越容易了,这就是它的一个很经典的一个小案例。

 

④比如以前谷歌专门做了一个算法编程大赛,里面还有很多经典的案例,比如磁盘问题、公交车问题、画图问题、举证查询单词路径问题、最短路径求和、篮子问题、扔石头问题等等,还有些做游戏的朋友,它一般都会做游戏,尤其是做大型游戏的,它涉及到很多算法,像做游戏一般都会考察算法,除非是中界面的,所以做游戏的一般会要求是学 C 加加的比较多一点,这里面它也会用到一些数据结构,在数据结构的基础上,才能产生算法,离开这个数据结构的算法也是可以的,但是很难,就是说算法在数据结构基础上,算法就显得更加的优雅,很有意思,如果离开数据结构,针对一些最基本的基本变量来搞算法,就会很难。

 

 

(4)小结

因为有些问题很复杂,所以我总结了两点,总结了数据结构是一门研究算法的学科,有了编程语言,也就有了数据结构,那么学好数据结构,可以编写出更加漂亮、更加效率高的代码,所以有时候去看有些比较厉害的人写的代码,短短的20行,看不懂写的是什么,有些200行,可能几分钟就看完了,如果给你20行代码,基本上你看不懂,根本不知道写的是什么,因为里面大量都是调用归宿或者叠加的一个算法,很麻烦,但是这种代码,往往比较有价值,所以学习数据结构还是很有好处的。那么学好这个数据结构,要考虑如何将生活中遇到的问题用程序去解决,所以曾经有一个外国人,他说程序就等于数据结构加算法,当然他这个角度是站在底层的一个角度,其实这句话也不能是完全正确,当然也不是错的,核心可以这么说,一个程序的核心是算法加数据结构,但是现在随着软件的发展,它融入了很多新的东西在里面,如果说程序只是等于数据加一个算法,那业务逻辑难道就不重要吗?

有时候业务逻辑也是非常重要的,但是业务逻辑也要靠数据结构加算法来支撑。

 

 

二、数据结构和算法的关系

(1)什么是算法

算法首先是程序的灵魂。什么叫算法?

举个例子,比如将来做 go web方面的开发,那么都知道 go Web 开发一定要解决几个大的问题,就是一个高并发、海量吞吐,这些问题看web服务器, Web 服务器现在最厉害的是 NGKS ,就是比较厉害,写的比较坚如磐石,那么可能会说网站使用服务器集群、数据库读写分离和缓存技术,比如 readys 就可以跑得很快,就可以支撑大并发、高高并发和大流量,用的这些东西肯定是可以的,但是要深入的再问一句,这些优化技术又是怎么搞出来的?它的底层是什么?

 

最底层的还是算法,就是它之所以去做一个集群、做一个读写分离、做了一个缓存,它依靠算法,最简单例子读写分离,核心是什么?

 

当是 select 语句时,就去认为是读,当是其他操作,就认为是写这一个东西,就有很多算法在里面,难道仅仅靠一个 select 的一个关键词来判断吗?

 

肯定有些优化的东西,;再比如集群,集群完了之后,同时跑了16个或者32个后台,跑了那么多服务器,那么用什么样的算法,让各个服务器能够充分发挥它的最大效率,而且保证没问题,;再比如有些服务器,它为了防止死机,它一般都会有一个备用服务器,发现有一个服务器宕机了,它立马就冲上去了。

 

这些东西肯定要用网络,它同时还有算法,比如张三有一堆好友,那么这些对好友,它的状态,是每隔五分钟要把所有的好友全部放上去,问服务器要,不过不是一起要,他是分波要的,它怎么分波?

 

它先每次发十个过去,发十个过去过后,若果发现这十个几次都没有它,它应该是这样的,刚开始它要的人很多,比如现在有100个好友,可能第一次把100个全部发给你,突然他妻子就回国了,回国时它肯定用一个标识来标志它状态到了第二次,发现其中有些状态是稳定的,就要把这100个里面比较稳的塞出去,下次不要了,过后,再去要一个经常变化的人,等到有一段时间还得算一下,以前没有要的东西,用一个算法再把它提出来,里面有很复杂的东西,而且要的时候不是每次都像顶级服务器中间做一个缓存,而是它自己有。比如客户端做一个缓存的时候,这个地方每隔一天时间自动去客户端,去定时的要下服务器数据,所以它里面有很多算法在里边。

 

(2)算法结构

为什么不同的人写出来的代码,从功能上看是一样的,但是从效率上却有天壤之别,这句话只有去跟一些大工问,即真正做过核心开发的人,就会有感受,那么感受是最深是哪个地方?

 

那么走服务器数据库有什么问题?走数据库本身是没问题的,但是当量大时,数据库根本就支撑不了,我的瓶颈就在程序和数据库之间,就是数据的吞吐量在这挡不住,他说可以扩带宽,其实外部这一层可以用集群来解决,那么现在最难的地方还是程序跟数据库的交互,它很难去解决,同步怎么解决?

 

光一个数据库这么多并发都来了,会全部都卡在数据库,跑不动,全部堵在住了,然后他说现在你可以加宽带,一家流量没问题,大流量可以解决,大并发其实也不是问题,因为大并发有很多负载均衡也能解决,现在大型网站最难的地方还是在于程序和数据库,数据库启不起来一般都用读写分离,可是一写读写分离又出现很多问题,读写分离还有同步的问题,而且问题是数据表特别大的时候还要分表,分完表了过后,数据量再大,所有的优化最终还是要落实在代码的算法上,那这时能不能设计一种方案,减少对数据库的查询,同时还能够让程序正常运行,这就是他的一个设计理念。

 

怎么优化这些东西,其实就是现在所谓的一些缓存产品,那个时候没有缓存产品,所以那个都是程序员自己在想办法,所以就说了一句话:认为程序是有灵魂的,是有算法的,如果不想永远是个代码工人,那么就花时间要研究算法,一定要去最终要突破这个问题,如果想在架构上、在效率优化上,肯定要去多看一些这样的东西,否则代码肯定不保证,就好像两个人一样,其中有个人什么都不懂,两个人看起来长得都是一样的,比如我们坐汽车,从外形上看都是奔驰,但是里面的发动机完全不是一个档次,别人只要一开启,能把你扔到十万八千里,但从外型看,它也是奔驰,我也是奔驰,但你没看见内核是什么,所以看程序时,对外行来说,看你的程序就看漂不漂亮,内行要看要干什么、测测性能,这是讲了一个算法结构。

 

 

三、几个实际编程中遇到的问题

(1)Golang代码

比如现在有个字符串在进行 Replace ,如下:

func str main() {

var str string = “go,go,hello,world!”

str = string.Replace(str,”go”,”尚硅谷”,-1)

fmt.Println(str)

}

 

那么现在要求大家使用单链表来表示字符串内字符串节点类的定义,并依次实现它的构造函数、计算长度、串赋值、判断两串相不相等、求字串、两串的连接、求子串在串中位置等7个成员函数。这些函数本身是由 API 提供的,但是要自己去实现,当时在大学里面学的时候,也有很多的这个作业,当时主要是集中在 C 加加里,这个作业是在数据结构里面,其中一个链表,它就出了一个类似的题,大概是在第六题,这个用的是 C 加加来写的,这个东西看起来就吓人,当时给我们出了这样一个题:要用自己的数据结构来实现,是一堆;还让我们去做一个多项式,多项式要求写一个算法,计算两个多项式的乘积要用多项式来实现,这个还算是简单的,当然这个东西你要能写出来,肯定是需要好好去想一想的。

 

 

(2)一个五子棋程序

五子棋相对比较简单,也就判断输和赢,并可以完成存盘退出和继续上局的功能,如果去写一个算法,怎么判断输和赢,怎么效率更高一点。如下图是一个五子棋程序:

 

 

(3)约瑟夫问题(丢手帕问题)

约瑟夫问题是很经典的,如果这个东西用链表来完成,就特别简单,如果没有悬念表,只能用数组来解数组,解决起来就比较困难。就这速度解决约瑟夫问题,它的难度不小。他最经典问题也就是丢手帕问题,他设计一到一二到 N ,围成一圈,约定编号为K的这个人从K这个人开始报数,数到 M 的那个出列,然后下一个又从那个下一个人开始,又从一开始就数到 M 又出列,最后问哪个人出列最后留的是谁?这就是个算法,那么这个时候,可以用链表加上思想,形成一个算法,每个人的算法可能不一样,效率也会不一样。可以用一个不带头结点的循环链表来处理 Josephu 问题,先构成一个有 n 个结点的单循环链表,然后由 k 结点起从1开始计数,计到 m 时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。

 

 

(4)其他常见算法问题

如磁盘、公交车画图,邮差汉诺塔,那写完了之后就看到它,就能解决。汉诺塔为如下图:

 

 

(5)小结

把数据结构的一个需求,就记三句话:可以认为程序就是数据结构加算法,那么数据结构和算法又是什么关系?可以认为数据结构是算法的一个基础,就是说算法建立在数据结构基础之上,这个算法就会相对来说实现的更容易;

 

第二句话是:学完数据结构可以做什么事情?学完数据结构就可以解决这样的问题,当有一个实际需求摆在面前的时候,如果学了数据结构,相对比较容易把这个算法写出来,就是相对而言有工具了,就像有一天去盗墓,盗墓是不允许的,赤手空拳去盗墓,一进去 game over 了,有一天发现当你盗墓的时候,有很多秘籍,第一个要有秘籍,第二个有很多先进的工具,比如洛阳铲之类的,还有个罗盘,有一个曾经死去过大关皇帝的位置就能找到,

 

然后,洛阳铲一铲,然后,有一帮朋友帮你,就很容易把这个木盖弄起来,所以解决实际问题,如果没有工具,赤手空拳,这个事就很难做,就算数据结构只是算法的一个基础,但是离开这个数据结构,做一个算法很吃力。