day24_集合/20-尚硅谷-Java语言高级-Java版数据结构简述

好，这个集合这一章呢，咱们就讲完了，那集合这一章包括咱们前面讲过的数组，这是跟数据结构呢关系最密切的两个章节，嗯，那么在大家这个笔试面试的时候呢，基本上也不会专门去考察你这个数据结构了，但是他可以通过我们现有学习的知识呢，去间接的考察大家的数据结构，那就相当于通过集合咱们涉及到一些底层源码，包括呢前面的数组，但数组的呢，又没有什么可考的啊，就是非常直接的一个结构啊，你去扭一下，然后呢，通过角标呢去填数据。啊，那么实际上咱们见到release呢，就是非常典型的这数组的一个封装。大家呢，呃，也可以呢，你自己造一个AR arrest嗯，你自己可以造个啊，就是呢，你对现有的这个数度一个封装提供呢，哎，增删改查的方法啊就就可以了，只不过呢，大家没有必要这样去做，开发中呢，都给你现场的，你直接用就完了啊，那么会用这是第一个层面，第二层面呢，你要关心它里边到底怎么做的。啊，那A呢，相对还比较简单，那比它复杂的话呢，我们就提到了，像哈map除了数组还有链表啊，那八当中除了列表呢，还有红黑数，包括呢，像吹side tree map，那就专门就是红黑树啊，那树呢，就属于我们树叶结构当中一种典型的结构了，那咱们呢，借着这个机会呢，给大家稍微呢去说一下这个数据结构啊，只是简要的去说，那大家在大学当中呢，数据结构呢，在理工科的这个专业当中，应该是专门的一门课了。

可能是这个选修等等是吧，这可以讲呢，讲一学期，讲一学期之后呢，你发现最后还是什么也不会是吧？啊关键原因就在于你没有用，你没有用上啊，所以呢，咱们这块呢，如果单纯的去讲数据结构呢，也会比较枯燥，讲完以后大家可能也留不下来什么，那借着这个集合的话呢，你就知道哦，里边原来哪些东西在用这个数据结构啊，你就能够更清楚了啊，就能更清楚了，包括呢啊，有些时候呢，我们用这种数据结构也行，用这种数据结构也行，那你就得考虑哪个效率更高，这是我们学习它的一个目的啊。

那这块呢，咱们就不多说了啊，直接呢上来讲一讲，这呢我呃三个框啊，看着挺小的啊，这个展开的话呢，这个就就多了啊。嗯呃，先是一个简单的概述哈，说是为什么要讲这个数据结构啊，F4以下，呃，这个我放在里边这个图啊，其实图挺大的啊，但是这个，呃，这也不是个收费版的，所以这块图呢，我也没办法去调这个大小啊，咱们就简单看一下啊啊，任何一个有志于从事it领域的人员来说是吧？啊，数学结构都是一门啊，和计算机硬件软件相关的学科啊，就说它的重要性的啊，这个咱们就不多说了啊，数学结构这样一门课，大家呢，在大学中学的话，应该会涉及到这样的几个内容，第一个叫数据的逻辑关系，第二个数据的存储结构。啊，然后第三个叫排序算法，第四个呢叫查找或者叫搜索。啊，通常呢，这本书呢，就叫数据结构与算法，那算法呢，其实他没有展开说特别多啊啊至少呢，会说这样的两个排序相关和查找或者叫搜索相关的行啊那这块呢，我下边列这样几个图呢，想说明的就是呃，有数据结构跟没有数据结构的一个区别，说数据结构呢，啊，我们给大家举一个实际场景，就好比呢去打仗这个图不是很清楚了啊啊这个打仗这个事儿呢，就好比大家去写代码啊这两个基本是吻合，那你打仗这个战场就是大家呢开发的你用的这个软件和硬件环境，那么你战场当中这个敌人就是现在你要完成的这个项目或模块的功能。

啊，你把这个敌人打败了，现在你这个项目呢，模块呢就写完了啊，那么这个指挥官，指挥官就是你啊，你现在呢，就是指挥啊去完成去打败这个敌人，那你的这个士兵是什么呢？就是你写的一行的代码。啊，那就看你写的这银行代码牛不牛了，这个士兵呢厉不厉害了啊，那这里呢，就涉及到这个战术和策略啊，实际上提到叫术结构，就是说我打仗啊，没有战术和策略也照样能赢，有可能就人怼就行是吧，呃，人多点就已经往上怼啊，这个以多胜少，历史上的这个例子多了去了啊以多胜少那不是不会写到这个历史里边了，没啥可说的啊哎，所以历史上只会记录这个以少胜多的这个战役是吧？啊，这个以多胜少那呢谈不上牛啊啊就是你大不了写了一代马话就写的多一些啊，绕一些是吧？啊最后呢，也能出来也可以啊，但是呢，你要没有这个战术的话呢，经常打仗的话会事倍功半啊，你这个人多的才能够赢啊，否则的话呢，就很困难，但如果你要是有战术的话呢，还非常有这个规则的去调兵遣将啊，这个呢就可能叫事半功倍啊，事半功倍跟事倍功半啊，这个是不一样的啊，那这呢就相当于呃，你要想有战术，那就得去。

触底层的数据结构啊，接触相关的一些算法啊，那这呢就提到了一个数据结构的研究的这个内容，就是数据的一个逻辑结构和物理结构，哎，逻辑结构和物理结构，这是我们就要研究的目的啊，这个研究的内容目的呢，就是加快程序的一个执行速度，减少内存占用的空间啊，那这个战术也不是说一天呢就能学会的，那数据结构呢也是一样啊，需要大家呢慢慢的去积累啊，去积累学习好就过了啊，数据结构的一个具体应用场景啊F4这呢只是举了几个简单的例子啊，啊这呢，比如说大家在这个玩游戏，玩游戏的时候呢，你看到有一个山啊，那我现在怎么去描述这个山，我就可以把这个地图呢，打成很多块。

啊，这个图呢，从上往下看呢，就是这样的一个情况，这个情况里边这个山呢，就是占据了这里边的EFHG这样的几块，啊那这个呢，描述一下，其实就是一个树形结构。啊，那数据结构里边呢，这这几个点啊，它表示出来的就是一个山啊这样的一个关系啊呃，还有呢，比如说这个最短路径，这个大家呢，从从咱们这个位置呢，到天安门啊，你看怎么走最短，首先呢，有很多种路径啊，哪个最短，这个呢，也需要考虑我们用数据结构的这个知识啊，搜索理论，那这个呢，用的太多了，现在呢，基本上大家用的任何一个应用呢，多少都会提供这个搜索功能。

啊，你去这个淘宝也好，去京东也好啊，它也都有相关的这个搜索功能啊，那这块呢，就涉及到我把数据呢，首先要存储起来，接下来要考虑的就是如何能够高效的把数据呢进行一个查询。啊，那大家呢，也有这个大数据专业的，那就更得考虑这个事了。啊，一个呢是存储，第二呢查询，当然呢还需要做的是去挖掘用户的信息，实现个性化的推荐啊啊这呢都是我们要后边呢，后续学习的一些内容，他的一些底子呢，就是都涉及到这个数据结构，然后呢，呃，这个人咱们原来也提过啊叫啊尼克拉斯沃斯提过这句话，算法加数结构等于程序啊然后呢，说完这句话以后获奖了，拿到这个坦图灵奖啊呃，那么它这句话里边呢，提到了算法和数据结构啊这呢我写了一段红色的话啊，这个红色话呢，大家去体会一下，说程序能否快速而高效的完成预定的任务，取决于是否选对了数据结构。

比如说大家频繁的对list当中的数据呢，进行这个删除和插入啊，你呢选用的是a list，我呢用的是link list啊显然呢，这两个都能完成，完成你的功能需求，但是呢，效率不一样啊，就是因为你底层选的一个是数组，一个是链表。啊，体现出来的，这是数据结构能决定的问题，就是效率是不是高效。那么算法决定的是什么呢？程序是否能够清楚而正确的把问题解决，取决于算法。算法做一个排序，排完以后呢，发现还是乱的，也说明这个算法上写的有问题啊，它解决的是你正确与否的问题啊，是这样啊对总结算法呢，是为了解决实际问题而设计的，数据结构呢，是算法呢需要处理的一个问题的载体，一个数据到底怎么存啊，它是个载体，基于这样的一种存储，我们去写算法，就像说我是用数组存的，那我现在呢。

掉线了是吧。他掉线了吗？好了吧，没有重播一下啊，好了吧，刚才我碰到这个水晶头了啊嗯。哎，再回来说一下，就是数据结构呢，是算法它的一个问题的载体，嗯，比如说呢，我们现在呢，是用这个数组存的，你现在呢，想在这里边插入一条数据，你得先看啊，你这是数组啊，你要是数组的话呢，那我就得基于你这个数组，看看怎么去插入了啊，这个得往后移了，那你要是用这个链表的话呢，哎，那你得看啊，链表想插入，那我就不用往后移了啊，所以说呢，这个算法也都是基于这个数据结构来的啊，是这样数据结构研究对象，哎刚才提到了第一个是数据之间的逻辑关系，这个逻辑关系呢，我们总结为这样的几点，第一个呢，叫集合关系，最弱的一种关系，哎就像咱们原来稍微提过啊，说你在大街上看到个美女，说你俩之间有什么关系呢？

啊，唯一的一种关系就是恰好在某年某月某日啊，某时某分，在这个地方出现了画一个小圈，你俩呢，算是一种集合关系啊，很弱的一种关系，那么要强一点呢，就是线性关系，提到了叫一对一的关系啊，那么这个一对一的关系呢，叫线性关系，哎，我们对应的下边这个存储结构的话，就提到一个叫线性表，大家呢，如果你去翻看任何一种语言写的数据结构的话呢，哎，都会提到这样的几种结构，线性表里边又分成叫顺序表、链表站和队列。那接着啊，树形结构，它想描述的就是一对多的关系，就是一个数，数里边呢，我们主要关心的就是二叉树，哎网状想描述的就是多对多的关系，多对多呢，典型的这种存储结构当中的体现呢，就是哎JA法当中的图图模型，哎就是它这呢数据结构研究的对象呢，叫逻辑关系啊，那么另外一种呢，叫做存储结构，也叫做物理结构。

那这个存储结构我就没往下涨了，为什么呢？因为下边说的这些呢，其实都是它的物理结构。嗯，好，嗯，这个对应的两本书啊，一本书呢，这都是张二版的哈，呃，是这本书。那这本书我也买了哈，就是我也看了看，写的还挺好啊，呃，确实人家国外写的这种书吧，跟国内的这个还是不太一样的，国外的都比较国内的都比较生猛，上来就咔咔咔的这种知识是吧，特别干哈，国外的话呢，就是层层深入，一点点给你引进来。啊，这以前我看那个经济学的一本书，这个外国写的范里安啊写的那本书啊，写的特别漂亮啊，他在构建经济模型的时候呢，咱们知道经济模型就是涉及到群体的这个人是吧，他怎么去描述一开始的这个行为呢？他先假设有一个人，哎，那他就想一个场景，那就是鲁宾逊嘛，就鲁宾逊他自己是生产者，他自己消费啊一个经济模型啊，说清楚了以后，然后呢，诶俩人来了，俩人来怎么办呢？诶他不是有一个那个努力吗？

星期五是吧？哎，有了星期五以后，哎，星期五是他奴隶啊，让星期五去生产，他来消费，哎有这种雇佣关系，哎又有一个模型，哎两个人的模型说清楚以后呢，然后接着呢，你就可以再扩展多人的模型了，哇，你看完以后你就发现哇，写的太好了是吧？哎，国外的这个书呢，很多都是这样子的啊，因为他们可以靠卖书生存啊，国内不行啊，你要一不小心写了一本好书好了啊，盗版的就出来了是吧？啊，你想靠这个挣钱呢，很困难啊啊所以大家呢，国内的人写书呢，主要就是想图个名声。啊，卖不卖，挣不挣钱不重要是吧？啊，所以很多人就自费写书啊，一说呢，我写了好几本书啊，咱们赵老师呢，也出现过这种情况啊，这个老师一过来先先让他做个自我介绍，他呢就不想介绍，从书包里咔咔掏出三本书来，这我写的书是吧？啊一看写的稀碎啊，啊不行啊，这个还有一本书呢，叫大话树结构，这是国内人写的啊，程杰写的这个大话叉叉叉系列啊，已经出来了啊，这两本书的话呢，其实不经意间我已经给大家发过是吧？

在第一部分那个数组当中，这不有电子书吗？这不就大话数据结构，这就是那个。哎，张二爷描述版啊这个啊，正版的啊，正版的电子书嘛，是吧，电子版啊啊然后啊，行这就过了哈，然后下边呢，是咱们这个中心这儿呢，我就不想呃细着给大家去展开来说这个事儿了哈，这个大家呢下来都可以看，哎，我想明确的点是什么呢？这儿呢，我提到叫真实结构。或者说呢，叫最基本的存储结构，这俩说的其实都是我们说的这个啊，叫存储结构啊，逻辑关系的这一说就过了，那么在这个存储结构这块的话呢，真实的结构主要呢，提到两个，第一个呢，叫做线性，线性表值顺序表，顺序表里边啊，或者你要静态数结构啊，就是数组，我这又加了一个list，因为list本质上来讲也是数组。

啊，也是数组，所以它们两个呢都可以叫做顺序表，顺序表的意思就是顺着一个挨一个去存，其实就是数组啊，底层我们确实有一个结构呢，就叫做数组啊，它是真实的一个结构，还有一个结构呢，叫做链表，链表呢典型实践在我们Java当中就是link list啊，那么这两种结构有什么特点呢？这个我写的已经很清楚了，我不一个一个带大家去过了，这两种结构呢，确实不太一样啊，典型的区别就是它呢，你想这个，呃，这个叫什么扩容啊，或者插入删除啊，这个效率又差一些啊，而他呢，正好相反，他就就擅长干这个事啊，它的缺点呢，就是这种结构你设计起来稍微麻烦一些。

啊，他呢就稍微哎简单容易理解一些啊呃，下边呢，就关于他们的这种图示啊，具体的操作呀，操作就涉及到读写呀，写是从头写还是呃这个这个呃从中间写还是从尾部写是吧？这呢就是具体展开，这个我写的很清楚啊，昨天给大家整理的这个内容啊这个列表呢，又分成这种好几种形式的，哎最基本的呢，叫单向列表，是这个样子的啊也可以有这种叫环形列表，最后一个呢，又指向第一个了，叫环形列表，还可以有这种双向列表，咱们讲的link list其实是双向列表啊，还有个呢，叫双向循环列表，哎，都可以的啊哎，然后关于它的读液操作啊，使用范围啊，这就不多说了，这个呢是咱们叫真实的内存结构，在内存里边呢，就是有这样两种结构的，下面呢，我们提到这个占。这个战队列。这个链表顺序表这四个，这四个统称为线性表，就是描述呢，是一对一的关系。

一对一的关系，我前面一个元素，我呢是不是指向后有元素，再指向后有元素，这叫一对一的啊，这四个呢都叫这个线性表，只不过呢，这两个是真实存在的，这两个呢，是可以根据上边两个给它拼出来的，或者叫构建出来的啊这这个占占呢，呃叫stack，在咱们Java当中，这不是说确实有一个类呢，就叫做stack吗？咱们上午复习的时候不也提到了，它其实就是咱们这个VE的一个子类嘛。嗯，这个站的话呢，呃，既然你是用的vector VE底层用的数组，所以这个站结构目前咱们看到的它其实是用数组做的，那其实占其实也可以不用数独做，所以你看这个实现结构，我这块又写了啊，你可以呢，用顺序表去实现一个占，也可以用一个列表啊去实现一个占，各自有优缺点，所以说呢，这个站是基于他们两个造出来的啊，是出来的，这叫站结构，它的具体的这个特点当然就是先进后出，或者叫后进先出啊，哎，具体的运算。

哎，具体的使用场景。啊这样，哎，递归调用这不就典型的一个情况吗？还有咱们讲这个程序调用的时候呢，咱们在这个占空间里边加载变量加载的这个加载这个加载这个出来的时候呢，这个得先出。啊，这个都是站的这种使用场景啊，这呢就过了，然后下个呢叫做队列，这个队列跟这个站呢。不太一样啊，站呢它叫先进后出啊，这个我这也给放了几个，哎，我在这儿放了几个图啊F4啊大家呢，你去超市买买这个东西的时候呢，呃，一般呢，就是呃，这个售货员还是把那个呃东西先往里边放，再往外再往外再往外放，然后大家取的时候肯定先取这个。啊，都这样的啊，然后呢，呃，放在这个书也是一样，先放这本书，再放这边，再放这边，再放这边啊你拿的时候呢，也是先拿上边这个，或者大家呢，进电梯也是一样，先进的人呢，在最里边啊，最晚出来啊，都像一个站的一个特点，而这个队列呢，哎，点错了啊F4队列的话呢，是这个样子的啊，这个人是先来的，先进去的，他先进去，他就得先出来，他就要先进先出。

啊，然后后边人都得这样去排啊，这个里边跟咱们生活中不一样啊，比如说这是你你排来排去，突然说我不想买了，你这块就想走是吧，你就直接就走了，这时候呢，不能走啊，这个你要出去得从这出去，那前面人出去了，你得从这出去啊，就是一旦排好队不能中间走啊，哎，这是在咱们这个队列当中是这样子啊，只能有一个出口，不能从这想走就走啊，这是这个队列啊，具体在这一个图示呢，就是这个样子的。哎，这个样子的啊，哎，它的特点呢，叫先进先出，实际上呢，它呢怎么控制先进先出，你也可以考虑，它就是用个数组做的。

就用个数组做，嗯，数组做嗯，原来的普通数组，你想往哪填数据就往哪填，当然前提是你在有后边可能空的啊，在你前面有数据，这里边呢，你想往哪填就往哪填，没有限制，只不过呢，这个队列呢，我们对你操作数组这个事儿呢，有了一些限制了。你要想添加，你去这个尾部添加，你要想删除，删除呢，我不给你提供，哎指定索引了啊，就是一个空参的，你要删只是把这个删掉了，这个一删后边呢，紧接着往前移。啊，往前移，然后加一个就从尾部加删又得从前删，这样体现的不就是先进先出的一个特点嘛，啊就是这个样子的啊，这个队列在咱们后续讲课过程当中，大家会看到很多的这个使用场景啊，我们计算机处理各种事件，尤其典型的啊，消息队列，事件队列都是这样来做的。啊，后边我们会讲的，比如rabbit MQ是吧？哎，这个消息队列，呃，消息队列呢，谁先处理呢，是个队列的，谁先进来的，我就先处理谁。

啊，很合理的一种想法啊，CPU的这个作业调度也是一样，谁先请求的，谁先要操作，我就先来处理谁啊是这样子的，哎，广度优先啊，下边提到这个图来广度优先了啊这后续内容，这呢是这个队列的一个事情啊，那么这个队列呢，你也可以用这这个这个叫什么？哎站哎不是占用这个链表来实现，我这写错了啊，用这个顺序表来实现这个队列。哎，你也可以呢，用这个链表呢来实现这个队列，就是它呢，还像是一个抽象的数据结构，这个抽象数据结构呢，这个我们叫a dt oftra data tap啊抽象沿本质上没有，它是我们通过现有存在的这两种结构给它造出来的一种结构啊队列你看用顺序表实现，你用列表实现各自的优缺点啊，都写了啊数数的话呢，哎，这呢，F4以下，这现实世界中的数长这样，咱们这个代码中的树呢，是倒着的啊，就比如说呢，生活中的这个公司的组织架构啊，家谱图。

啊，这个组谱图这样啊，哎，还有这呢，是咱们这个linus的一个文件系统，Windows呢也类似啊，往下展开啊，这呢都是属于这个树形结构的一种生活中的场景，那计算机中的树啊，长这个样子的，这里边涉及到一些具体的专有名词啊这呢就根据这个图你去看这些就行啊这个树数的话呢，它也是一个抽象的。啊，它是抽象的，它呢是针对于咱们的列表造出来的，咱们那会儿讲那个，呃，底层源码时候说过哈，你这是一个，比如叫一个node了，我这里边呢，又声明啊，这个node类型的两个变量，一个呢叫left，一个叫right，那就意味着你呢可以指向一个新的一个node，你也可以指向一个新的node，而这两个新的node呢，又同样的有两个node类型的变量，他们呢，接着往下去指。

哎，这边呢，就相当于我们啊，利用这个链表的这种结构呢，我们给它造出来的一个二叉树。哎，是这样子的啊啊，那么二叉树呢，是我们关注比较多的，就是它有两个分支啊，你要三个分支呢，就三叉树了，我们平常要用的话呢，也就是阿尔法术啊呃，这呢，关于这个常见树的一个，呃，到底谁包含谁，谁属于谁这样子的啊特例咱们提到了这个红黑树。啊，红运数啊啊具体的使用场景啊，这呢就不多说了啊，这个B加数呢，或者叫B数必减数这块呢，在咱们这个后面讲到数据库高级的时候呢，会提就数据库的这个索引，哎，咱们用的是这种必加数啊，在这个编码层面，这也不不具体展开了啊，用的是这种哈曼数啊，考虑带权重的一个阿尔塔术，在信息检索的时候呢，尽可能让这个数据呢，数据量小一些啊这是这样的场景啊，还有图图呢，就是多对多了。

啊，可以用这个链表呢来实现的啊，嗯，这块呢，有的时候，嗯，也不排除有的同学可能面试的时候会被问到哈，当然不是面试笔试会问问什么呢，就让你去便利啊。我这哦，我这在这个树这块没写了，我在这块的写了，图这块写了啊，深度优先，广度优先，诶我记得是写过呀。哎，在这儿呢，啊，这个数的话呢，它有广度优先和深度优先，在深度优先这块呢，提到过前序中序和后序。啊，这个呢，大家如果大学学过的话，你应该有点印象哈，啊有的同学可能会被碰到过啊，说给了你一个数，让你去前续中续后续的去变历叭，如像这个啊这就不在这展开说了啊大家呢，现在也没有必要呢先去研究这个问题啊下边这个图啊，这就不多讲了啊啊还有其他的这个一些结构，这呢，我主要呢提到的是数据结构啊，没有提这个算法哈，像这个排序啊，搜索呀就没有提了，哎通过刚才这样的一个简单讲解，大家能够有个印象什么呢？这是两个真实存在的底层结构，这些结构都是基于这些结构呢，给它又哎造出来的或者组合出来的是吧？哎，就是这叫抽象的数据结构啊行，这呢关于数据结构的一个简单介绍，每种结构的一个特点是什么，这里边呢，都给大家提供了下来呢，你愿意看看，可以展开去啊，读一下就行啊。