00:00
好,我们来继续讲解,那么在我们做这个数据结构算法之前呢,我们来看实际编程中遇到的几个问题。好,第一个大家看这有一段Java代码,没问题吧,大家都能看懂,他是在做一件什么事啊,给了一个字符串。然后呢,我这用了一个string.replace all,然后呢,我说要把Java换成上规股。这个方法大家应该都见过吧,就是用来做替换的,那么现在我要问的是,就是这个方法的提供者,他在进行一个字符串替换时,他是怎么做的?它里面肯定会有一个算法来支撑。对吧,他肯定会有一个算法。那么这个算法你要能看得懂。你要能看得懂,如果说我们在做一个程序开发的时候,看不懂别人底层的代码,那显然你自己去优化也无从谈起。
01:01
对不对,所以说这个方法呢,就是研究字符串替换的一个效率,或者是它的一个算法,它的一个方式是什么样子的,那现在我问大家一个问题哈,就说我要求同学们用单链表,这有一个面试题。用单链表表示字符串内及字符串节点内的定义,并依次实现它的构造函数,计算它的长度。串赋值,判断两个串是否相等,求子串,两串拼接等等,那注意看到这里面这个函数的概念呢,就是我们Java里面的方法。这个题是我们当时学数据结构的时候给的一个一个题,那么同学们可以看到,如果这道题你没有学过单链表,你也完成不了这个题。而单链表正是数据结构的一种。我们可以看一下打开。打开我们这个一个一一个案例,比如说以前我们在讲这个数据结构的时候呢,出了很多的练习题,其中有个题就是链表,我们打开lawyer。
02:12
好,我往下看一看啊,你看当时我们讲的这个数据结构的内容很多,你看每个题呢,都还是有一定难度的,其中有一个题就是刚才我给同学们看的那道题。好,我们看这道题。这道题它的要求其实很明确,就是用单链表来实现字符串的相关功能。而单链表就是数据结构的一种。这个单链表就是一种数据结构。数据结构,那如果说我们没有把单链表学会,显然这个题你就完成不了,是不是?对吧,所以说我们可以看到它这个要求其实是建立在我们对单链表了解的基础上才能去完成的,我们再来看第二个题,这个题呢。是一个比较经典的,同学们也玩过的一个游戏,是五子棋程序,大家看这道题,它有这么一个要求,就是第一个呢,判断游戏的输赢。
03:11
就是黑子营还是男子营?那么五子棋肯定是大家都知道这个规则了,只要五五颗子连成555个子连成一串,那么就算是赢了,那你是不是要写个算法?第二个他还要求有一个存盘,大家看这里有个叫存档退出,还有一个叫续上局。那你如果要完成这两个功能,还有一个悔棋,你看就是这一步我不满意,我要毁一步。同学们想这个游戏或者这个算法让你们去做,你们会怎么做呢?你们会怎么做呢?显然这里面就会用到一些这样的一些内容,比如说我来做一个分析,首先你会把这个棋盘。这是不是有个棋盘呢?你要把这个棋盘映射成。对,你要把它映射成一个二维数组。
04:03
你是不是应该映射成一个二维数组?那么这个二维数组呢,你。在这个二位数组里面肯定会保留各个点吗?就是别人下一个指的时候呢,这个二位数组上就有一个点来记录它是一个黑子还是一颗蓝子,然后二位数组在存盘的候,肯定要把它写入文件。写入文件。这样呢,就实现了一个存档退出对吧,存档退存档的一个功能。那么反过来我们要续上去又怎么做呢?肯定要去读取文件,读文件过后呢,你会把它重新恢复成原先的二维数组,然后把这个二位数再恢复成我们这个棋盘的显示。棋盘形式,这个呢,就叫虚上举。啊就叫接着上举啊接上举接着。
05:02
接着上去。是这意思吧,是这意思吧,那你想这里面如果你没有学会二维数组,显然这个也完成不了,而且作为一个好的代码,你还要考虑一个问题,什么问题呢?就是压缩的问题,你看在我们这个棋盘里面,其实我们只放了五个点,五个棋子,但是这个棋盘却很大。期盼就很大,那你能不能使用一种压缩的方式来做呢?其实这里可以的,这个二维数组有一种数组叫什么呢?就是我们的稀疏数组。悉数数组,它就可以完成一个压缩和解压的一个效果,就是到时我把这个。二位数组呢,把它先把它转成稀数数组,然后把系数数组写入文件,如果你没有学系数数组这个数据结构,你也搞不定,同样为了达到这个解压的功能呢,我们读文件的时候,其实先把它读成了一个稀疏数组,然后再把它转成一个二维数组,再把它转成棋盘说看这里数组这种数据结构。
06:10
的重要性就凸显出来了。明白,我们再看一个案例。这个案例呢,是一个非常之经典的约瑟夫问题,也叫丢手帕问题。我记得当年我参加工作之前做一个面试题,就是一个约瑟夫,我记得当时应该是在unix下面用C语言写的。也是用呃,环形列表来解决的这个约瑟夫问题呢,它很简单,它是这么一个要求,他说有一群小孩,我就直接给大家念一念啊,他说有一群小孩呢,围成一圈。比如说有N个人做成一圈,约定从第K个人开始,从一报数。数到M的这个人呢,就出列,而下一位呢,又从一开始报数,数到M又出列,以此类推,问出队的顺序,这个序列号是什么?
07:01
就是。这个出圈的这个小孩,他的一个编号序列。这个题其实是一个很经典的。可以用什么来解决呢?可以用我们所谓的这个叫做单循环链表。单循环链表,单循环链表也叫单向环形链表,就是这个地方会用到什么呢?说白了这方就会用到我们的所谓的单向。环形链表。环形链表来解决。二链表来解决,那如果你没有学过单线环境列表这个问题呢?说实话你只能用数组来解决了。你只用数字来解决,那么单线环形链表呢,也是我们后面要讲的一个重点,后面呢,我们会用单线环形列表来解决约瑟夫问题,它会形成一个出对编号的序列,到时间大家认真听,所以你看约瑟夫问题你学完单线环线,单线环线列表你就用可以用这种数据结构,数据结构来解决就会很形象,如果你没有学这个呢,说实话还是有些困难的。
08:08
对吧,就像我刚才讲的,如果你没有学系数数组,你最多也只能做到一个,把它转成二维数组就行了,但是你学完系数数组呢,你可以对这个程序进行一个优化,就是可以用较少的数据来保存我们这个棋盘。明白,我们再看一个小案例,其他算法,你比如说在我们面试的时候呢,经常会遇到这样一些问题,比如公交车画图矩阵,查找单词路径等等。那么求和男子这样的一些问题。那么我们来看。这些问题会用到哪些算法呢?比如说修路问题,修路问题它其实就是求我们的最小生成数。最小生成,呃,最小深数这个问题它会用到什么算法呢?可以用我们的普里姆。
09:01
普里姆算法来解决最短路径可以用什么算法呢?最短路径这个问题呢,其实可以用我们的弗洛伊德算法来搞定,叫弗洛伊德算法来搞定,那么汉洛塔这个问题,刚才其实我们已经看到了,它可以用回溯法哦,叫分制,分制算法。这个啊,分治。算法来搞定,而八皇后问题呢?可以用什么算法来搞定呢?八皇后问题可以用回溯法。回溯。回溯法A回溯啊,回溯法搞定,因此你看我们提出的这些问题呢,要么是用数据结构,要么是用算法来搞定的,显然我们后面的这个要求。较高,你比如说。我们要用这个修路问题,我们要解决修路问题,那你首先要先学这个数,数是一种数据结构,明白我的意思吧,数是一种数据结构。
10:06
数据结构,但是你光会数你这个修路问题,或者叫最小生成数这个问题你是解决不了的,你还得学这个算法,也就是说数据结构加算法才能搞定我们这个最小生成数问题。明白老师在讲什么吗?你比如说最短路径问题。最短路径哦,这个是图啊,这个地方最小升出也可能是图,那么最短路径问题呢,它也可能是一个图加一个算法来解决的,比如注意中心,它可能是个图,图这个结构再加一个算法来搞定的,明白我的意思吧。那呃地汉洛塔呢,它其实是用用到我们这个递归了。因此我们在解决一个问题的时候,往往是数据结构跟算法综合起来解决的。而前面我给同学们看的像这种。
11:01
像这种啊,比如说五子棋这个呢,你学一个数据结构,其实基本上就可以搞定,因为它的算法比较简单。对吧,自己就可以写出来,明白我在说什么,就说有些问题我们用一个数据结构就搞定了,而有些问题你数据结构加算法才能搞定。就是我要阐述这个问题。好,那最后呢,我们再简单的说一下我们数据结构包括哪些内容,数据结构我重点讲的是线性结构和非线性结构,线性结构什么意思,简单的聊一聊。聊聊线性结构,它。啊,干脆这样子啊,线性结构和非线性结构呢,我们放在下一个下一个章节讲,我们先把刚才讲的这几个常见问题进行一个简单板书。好,刚才我们讲的是几个实际编程问题引出的一些讨论,来吧,同学们,我们列一列。
12:00
刚才我们讲到。这有一个Java的问题是吧,这是个Java问题,这个呢,我看的问题一。啊,我们写到这儿就是问题一。问题一,这个问题一呢,我阐述的是一个字符串替换问题。是吧,字符串替换。替换问题。对吧,替换问题。OK,我给他列一个小标题,那么具体来说呢,就是这一部分内容,我这直接截个小图。好吧,很简单。放到这里来。那这里面呢,我们可以看到这道题呢,就需要用到什么呢?诶做一个小结,需要使用到使用到单链表。单链表这个数据结构如果你没学,那就搞不定,因为这有个题嘛,单链表来实现。那么我们再看第二个,第二个呢是一个五子棋程序的一个问题。
13:01
对吧,那这个问题呢。诶,这个问题我们来列到注意诶。放一个啊这个问题。那么五子棋这个问题。好,我在这儿找一找啊,无字提问题。这是一个游戏对吧,游戏人家提的要求呢,也非常的明确,他说要求来判断,要求你写一个算法来判断它的这个输赢,那这里面我们分析出来。这边需要用到什么呢?需要用到二维数组这种数据结构以及什么呢?系数数组进行优化。其实到这个题呢,你不需要专门学什么算法也能搞定,因为它比较简单。它比较简单,好,我们再来看下面的问题,就相对来说啊,就是诶这个问题也是约瑟夫这个是一个丢手帕问题呢,其实用单向环形链表就可以搞定,也比较简单。
14:01
这是我提出的两个问题是吧?提出的两个点给大家放到这里来。OK。好,然后呢,这个地方我们做一个小结啊,小结啊,完成这个丢手帕问题,或者叫约瑟夫问题。约瑟问题。需要什么呢?需要使用到单向环形链表。环形链表。这个数据链表。这个数据结构。那么这个时候呢,也不需要专门的学算法也能搞定。后面我又举了几个案例,下面这几个案例就是光有数据结构还搞不定呢,还得有专门的算法才能搞定。你比如说刚才我们所说的,求这个最小生成数。啊,最这个最小声一般是加权的啊,就是加权的。加全职的,加这个全职的。
15:01
OK,那么需要用到数这个结构,或者是图这个结构,然后加一个算法,再比如说最短路径问题就是图加一个E的算法。这样你才能搞定好。这是我们所说的其他算法的问题。我也把它罗列到我们的笔记中去。非常简单。给大家放一个小图。对吧,发一个图过后呢,我这里做了一个小的总结。放这来。这么几点。给他编一个号吧,简单一点。好,那通过这几个实际编程中遇到的问题呢?我们明白数据结构跟算法的一个区别,以及它的联系,再总结一下,就说简单的一些问题,使用数据结构。基本上咱们就可以搞定了,对于一些比较复杂的问题,比如说求最小生成数,或者是求最短路径呢,我们要有专门的数据结构再加算法才能搞定,明白这意思吧。
16:01
好,那关于这块呢,我们先讲解到这里。
我来说两句