[音乐播放] DAVID马兰：这是CS50。这是二者的开始和 end--像literally--差不多结束六个星期。我想我会分享一个有趣的事实点点。我从一本拉到了过去学期的数据集。你可能还记得，我们要求你在每个 P组的形式，如果你已经在网上看过或者，如果你已经亲自出席。这里是数据。所以今天是非常可预测性。但是，我们想花一点然而时间与您联系。有人想猜测为什么这个图中是那么的锯齿，上下，上下，所以一贯？做什么每个峰和波谷代表什么？听众：[听不清] DAVID马兰：确实是这样。而更有趣的是，上帝保佑，我们举行一次讲座上周五在学期的开始，这就是我们看到发生了什么。所以今天，我们参加了位更多关于数据结构。并给你更多的是固体对问题的思维模式五，这就是现在了。拼写错误，其中，我们将交给你一个文本文件，大约10万再加上英语单词，你将有弄清楚如何巧妙地加载它们入存储器，到RAM中，使用一些数据您所选择的结构。现在，这样的一个数据结构可以是，但可能不应该，在相当简单的链表，这是我们去年推出的时间。和一个链表至少有 1优势的阵列。什么是一个优点链表可以说是？听众：插入。 DAVID马兰：插入。你是什么意思？听众：任何位置名单[听不清]。 DAVID马兰：好。所以，你可以插入一个元素的地方要在列表的中间无需洗牌什么，我们得出的结论，在我们的分类讨论，是不是一定是好事，因为它需要时间来实际移动所有这些人的左边或右边。所以用一个链表，你可以刚分配使用malloc，一个新的节点，然后更新了几个 pointers--二，三次手术max-- 而我们能够插槽人中的任意位置成一个列表。还有什么是有利的关于链表？是吗？听众：[听不清] DAVID马兰：完美。完美的。这真是动力。和你没有犯，事先，以一些固定的大小内存块，就像你会用一个数组，则上行其中是，你只能分配上的节点需求从而只用尽可能多的空间当你真正需要的。通过与数组相反，你可能会一不小心分配太少。然后它只是去是在颈部疼痛重新分配一个新的更大的阵列中，复制一切都结束了，释放旧阵列，然后将您的业务。或者更糟的是，你可能会分配方式更多的内存比实际需要，所以你将有一个非常人烟稀少的阵列，可以这么说。因此，一个链表为您提供了这些活力和灵活性的优势与插入和缺失。但肯定要有付出了代价。其实，一个主题探索对测验为零一对夫妇的取舍我们已经看到迄今。那么，什么是付出了代价或下行的链接列表？是啊。听众：没有随机访问。 DAVID马兰：没有随机访问。但谁在乎呢？随机存取听起来并不引人注目。听众：[听不清] DAVID马兰：没错。如果你想有一定的算法 - 让我真正提出在特定的二进制搜索，这是我们使用相当bit-- 如果你没有随机访问，你不能这样做简单的算术题找到喜欢的中间元件的和跳跃的权利吧。你代替不得不开始在所述第一元素，并从左边线搜索向右如果你想找到中间的或任何其他元件。听众：它可能需要更多的内存。 DAVID马兰：需要更多的内存。哪里是额外的成本从内存中来？听众：[听不清] DAVID马兰：没错。在这里这种情况下，我们有链表为整数，但我们正在加倍的内存量我们需要同时存储这些指针。现在少了一个大问题，因为您的结构得到较大与你存储不是一个数字，但也许学生或其他物体。但有一点毫无疑问依然存在。等数的操作的上链表被称为是N--线性的大O。之类的东西插入或搜索或缺失的情况下的元素正好是在最末端无论是排序或不列表。有时候，你可能会得到幸运和这些操作使下界也可能是恒定的时间，如果你一直在寻找的第一个元素，例如。但最终，我们承诺实现了制胜法宝数据结构，或一些近似物，通过固定时间的方式。我们可以发现元素或添加元素或删除列表中的元素？我们将很很快就会看到。而事实证明，一个我们的机制要开始用至今，在P年利用设置5，实际上是非常熟悉的。例如，如果这是一串考试图书，其中每一个有一个学生的第一它的名字和姓氏，我去接他们从在考试结束后，而且他们都非常多以随机的顺序，我们要着手整理这些考试，因此一旦分级它只是一个极大的方便，快交出他们回来了学生按字母顺序排列。什么你的直觉会一摞这样的考试？好吧，如果你像我一样，你可以看出这是米，所以我要那种把这个成，如果这是我的表或我的楼，我的东西蔓延 out--或我的数组really-- 我可以把所有的小姐在那里。呵呵。这里有一个答，所以我可能把作为过来。呵呵。这里的另一个A.我要去把该在这里。这里有一个Z.这里是另一个M.所以我可能会开始做桩这样的。然后，也许我以后会去样的，非常挑剔-LY排序个别桩。但问题是，我想看看那个我手输入我会做一些计算基于该输入决定。如果以A开头，把它放在那边。如果它以Z开头，把它放在在那里，一切都在两者之间。因此，这是一种技术，是一般被称为hashing-- H-A-S-H-- 这通常意味着要为输入，并使用该输入来计算的值，通常是一个数字，那号为索引到一个存储容器，如一个数组。所以，换句话说，我可能有一个散列函数，像我一样在我的脑海，如果我看到有人的谁的名字开始与A，我要去映射零在我的脑海。如果我看到有人用Z，我要映射至25日在我头上然后它放入最后最桩。现在，如果你觉得不是我的大脑但一个C程序，有什么数字可能你靠什么来实现同样的结果呢？换句话说，如果有ASCII字符A，你如何确定什么桶把它呢？你可能不希望把它放进水桶65，这会像那边没有很好的理由。你在哪里要放在它的ASCII值是多少？你想去哪里做的ASCII 值拿出一个更聪明的水桶把它呢？听众：负A. DAVID马兰：是啊。因此，减去或减特别是65，如果是资本A.或98，如果这是一个小写。所以这将允许我们，很简单，非常算术，把东西放到这样一个水桶。所以，事实证明，我们实际上做这个问题，以及即使有测验。所以，你可能还记得你的盘旋封面上的教学老乡的名字。而TF的名字被组织到这些列的字母顺序，好了，不管你信不信，当所有80加上我们聚在一起的那天晚上等级，在我们的分级过程中的最后一步是散列测验变成了大地板在[听不清]空间并奠定了大家的测验出来在他们TF的确切顺序在盖的名称，因为那么它对于我们来说容易得多通过使用线性搜索搜索或某种聪明对于TF找到他或她的学生的测验。所以这个想法散列你将看到的是功能相当强大实际上是非常司空见惯，非常直观，很像也许是分而征服是零一周。我快进到黑客马拉松几年前。这是Zamyla和一对夫妇的其他工作人员的问候学生因为他们进来了。我们有一大堆折叠表中有与名称标签。我们有名称标签组织有喜欢当那边和ZS的那边。这样一来，课题组的一个非常巧妙写这个的说明为天。而在本学期的第12周所有的非常有意义，每个人都知道该怎么做。但是，任何时候，你已经排队以同样的方式，你实现散列相同的概念。因此，让我们正式那么一点点。这里是一个数组。它绘制的是一个小宽只是描绘，直观，我们不妨把字符串在这样的事情。这阵显然是大小共26件。而且东西被称为表随意。但是，这仅仅是一个艺术家的再现什么样的哈希表可能。这样一个哈希表现在将要是一个更高层次的数据结构。在一天结束时我们即将看到你可以实现一个哈希表，该表很像登机在黑客马拉松就像这样表用于排序的考试书籍。但一个哈希表这个排序高水平的概念，可以使用一个数组在底层实现它，或者它可以使用一个长列表，或者甚至也许一些其他的数据结构。而现在这就是theme--回吐一些基本的成分就像一个数组，这个建筑现在阻止长名单，看到什么，我们可以建立关于这些的顶端，像成分成一个配方，使得越来越多的有趣的和有用的最终结果。所以用哈希表我们可以实现它在内存中形象地这样，但怎么可能它实际上被编码吗？好吧，也许因为简单地说就是这个。如果产能全部大写，只是一些constant--比如26，为alphabet--的26个字母我可以叫我的变量表，我也许会说，我要去把炭明星在那里，或字符串。因此，它是如此简单，如果你要实现一个哈希表。然而，这真的只是一个数组。但同样，一个散列表是现在我们所会调用一个抽象数据类型，这只是排序在最前面的概念分层东西更现实现在喜欢一个数组。现在，该怎么办才好关于解决问题？嗯，刚才我已经奢侈这里有足够的表空间这样我就可以把测验的任何地方我想要的。这样可能会去这里。 ZS可能会去这里。小姐可能会去这里。然后我有一些额外的空间。但是，这是一个有点作弊权因为现在这个表，如果我真的想到这是一个数组，只是一些将要固定的尺寸。所以，从技术上说，如果我拉了另一名学生的测验看看，哦，这个人的名称与A开始过，我有点想要把它放在那里。但是，当我把它放在那里，如果这个表确实表示一个数组，我会被覆盖或重挫谁该学生的测验是。对不对？如果这是一个数组，只有一件事可以走在这些细胞或元件。所以，我种有挑选。刚才那种下面我被骗了，做这个还是我只是一种堆叠他们在彼此之上。但是，这并不是要在代码中飞翔。那么，我能放第二个学生的名字是A，如果所有我是这样的可用的表空间？而且我用三个插槽，它貌似有只是少数人。你该怎么办？听众：[听不清] DAVID马兰：是啊。也许我们只是保持简单。对不对？它不适合在这里我想把它。所以我打算把它放在技术上，其中A，B会去。当然，现在，我开始画自己陷入了困境。如果我去一个学生他的名字实际上是B，现在乙将要被移动一点点未来，为可能发生的事情，是的，如果这是一个B中，现在它已去这里。所以这非常迅速可能成为问题，但它是一个技术，实际上是被称为线性探测，因此你只要考虑你阵列是沿着线。正中下怀，你探头或检查每个可用的元素寻找一个备有现货。而且只要你找到 1，你在那里将其删除。现在，这个价格现在正在支付这个解决方案是什么？我们有一个固定大小的数组，当我插入的名字进去，至少在最初阶段，有什么插入的运行时间为把学生在右边的桶测验？什么大O？听众：N。 DAVID马兰：我听说的n大O。事实并非如此。但我们将梳理出为什么在短短的一瞬间。还有什么会是什么？听众：[听不清] DAVID马兰：让我做视觉。因此，假设这是字母S. 听众：这是之一。 DAVID马兰：这是之一。对不对？这是一个数组，它意味着我们有随机访问。如果我们认为这零，这为25，我们认识到，哦，这是我的输入S，我当然可以转换 S，一个ASCII字符，到一个相应的数字零到25之间然后立即把它原来的位置。但当然，当我到达第二个人谁的名字是A或B或C 最后，如果我用了线性探测作为我的解决方案，的运行时间插入在最坏的情况下实际上是要下放成什么样？我也听到了这里正确的早期。听众：[听不清] DAVID马兰：所以这是正确一次有一个足够大的数据集。这样，一方面，如果阵列足够大和你的数据是稀疏的话，你得到这个美丽的固定时间。但只要你开始越来越多的元素，而只是统计上你更多的人信 A作为自己的名称或字母 B时，它可能潜在下放成更线性的。所以，不是很完美。所以，我们可以做的更好？那么，什么是我们的之前的解决方案时，我们希望有更多的比活力像一个数组允许的？听众：[听不清] DAVID马兰：没有介绍什么？是啊。这样一个链表。好吧，让我们看看一个链接清单可能对我们不是做的。那么，让我建议大家画图如下。现在这是一个不同的从例图从不同的文本，实际上，这实际上是用粒度31的阵列。而笔者简单决定散列字符串不基于该人的姓名，但基于其生日。不论该月，他们得出如果你在第一次一个月的正在诞生或一个月的31日，笔者基于该值会出现乱码，从而被散布的名字出一个位不仅仅是26点可能会允许。也许这是一个小更均匀比用字母去，当然，因为有可能更多的人在世界上的名字开始的被肯定比其他一些英文字母。所以，也许这是一个小更均匀，假定均匀分布的婴儿跨越了一个月。但是，当然，这仍然是不完美的。对不对？我们有冲突。多人在这数据结构仍然具有相同的出生日期的至少你不论一个月。但什么笔者做了什么？好吧，看来我们有一个数组在左侧的垂直绘制，但是这只是一个艺术家的再现。不要紧，什么方向，你画一个数组，它仍然是一个数组。这是什么的显然是一个数组？听众：链表。 DAVID马兰：是啊。它看起来像它的一个阵列的链表。如此反复，这点排序利用这些数据结构现在的作为成分更多有趣的解决方案，你完全可以采取基本一样的阵列，然后拿更多的东西有趣像一个链表甚至将它们组合成一个更更有趣的数据结构。事实上，这也将被称为哈希表由此，阵列是真哈希表，但是哈希表中有链，可以这么说，可增大或缩小基础上，你想要的元素的数量插入。现在，因此，什么是在运行的时候吗？如果我要插入人他的生日是10月31日在那里他或她去吗？行。在最底层的地方说31。这就是完美的。那是一定的时间。但是，如果我们发现了什么别人他的生日，让我们来看看，十月，十一月，12月31日？哪里是他或她会去吗？同样的事情。两步虽然。这是恒定的，虽然不是吗？行。目前，它是。但在一般情况下，越来越多的人加入我们，概率，我们要得到越来越多的碰撞。现在，这是一个小更好，因为在技术上现在我的连锁店可以在在最坏的情况下多久？如果我插入N多人进入这个多复杂的数据结构，N多人，在最坏的情况下，它会为n。为什么呢？听众：因为如果每个人都有相同的生日，他们将成为一条线。 DAVID马兰：完美。这可能是一个有点做作，但真正在最坏的情况下，如果每个人都拥有相同的生日，给你的投入，你将有一个大量的长链。所以，你可以把它称为一个哈希表，但实际上它是只是一个大规模的链表一大堆浪费的空间。但在一般情况下，如果我们假定至少生日是uniform-- 它可能不是。我正在做这件事。但是，如果我们假定，对于就事论事它们是，那么在理论上，如果这是垂直的表示数组的，那么希望你将得到的是，你知道链，大致相同的长度，其中每个这些代表月中的某一天。现在，如果有31天的月份，这意味着我的运行时间真的为n超过31大O，这感觉比线性好。但是，什么是我们的一个承诺一两个星期以前，每当它来表达一个算法的运行时间？刚刚只看高次项。对不对？ 31绝对是有帮助的。但是，这仍然是n个大O。但主题之一问题设置5 将是对承认绝对的，渐近，理论上这种数据结构没有比刚刚好一台庞大的链表。而事实上，在最坏的情况下，这哈希表可能下放成。但在现实世界中，我们人类那自己的Mac或PC或其他而正在运行真实世界软件在真实世界中的数据，该算法你要选哪个？而其中，需要结束步骤或一种采用N以31级分找一些数据块或找了一些资料？我的意思是，绝对是31品牌在现实世界中的差。这是快31倍。而我们人类是肯定要明白这一点。因此，实现二分法之间居然有说起理论上的东西和渐近这无疑具有价值，因为我们已经看到，但在现实世界中，如果你关心只是使人类对幸福的通用输入，你很可能要接受事实证明，是的，这是线性的，但它的速度更快31倍比线性可能。而且更重要的是，我们不只是要做一些乱像一个生日，我们可以花一点更多的时间和聪明想想我们可能会做，定一个人的名字，也许他们的出生日期相结合的成分搞清楚的东西这是真正的多均匀，少锯齿，这么说不是这幅画目前表明它可能是。在代码中，我们如何才能实现呢？那么，让我建议大家只是借用一些语法，我们已经使用几次迄今。我要去定义一节点，该节点再次是一个通用术语，只是一些容器为一些数据结构。我要建议字符串会在那里。但是，我们要开始服用这些培训轮子掉了。没有更多的CS50库真的，除非你想将其用于您的最终项目，这是好的，但现在我们要拉回来了窗帘，说这只是一个char明星。所以这个词有将是有问题的人的名字。现在我有一个链接这里下一个节点使这些代表每个节点在链中，潜在地，的一个链表。现在该怎么办，我宣布哈希表本身？我如何申报这整个结构？好了，说真的，就像我用一个指针以列表的只是第一元件之前，同样我能说我只需要一堆指针实现这整个哈希表。我将有一个数组所谓表为哈希表。这将是规模生产能力。这就是很多元素可以适应它。并且每个在此这些元素的阵列将是一个节点的明星。为什么呢？那么，每个这张照片，就是我执行哈希表作为有效地在一开始仅仅是这个数组，我们已经垂直绘制，其每个的平方代表一个指针。那那些有斜杠通过他们只是空。和那些有箭头要正确在实际指向实际的节点，人体工程学的链接列表的开始。所以在这里的话，我们怎么可能实现一个哈希表，该表实现独立的链接。现在，我们可以做的更好？好吧，我答应最后一次我们可以实现一定的时间。我种了你固定的时间在这里，但后来说不是真的固定的时间，因为它仍依赖于总上元件的数目你输入到的数据结构。但是，假如我们这样做。让我回到屏幕在这里。也让我在这里预测这件事，清楚在屏幕上，并且假设我这样做。假设我想插入的名字 Daven在为我的数据结构。所以我想插入一个字符串 Daven成的数据结构。如果我不使用什么哈希表，但我用一些更树状就像一个家族树，其中你有一些根本的顶部，然后节点和叶那去向下和向外。假设这时，我才要插入Daven的到什么是当前一个空列表。我要做到以下几点：我要在这个家庭创建节点树状数据结构，它看起来有点像这样的，其中每一个矩形有，比方说，现在26在里面的元素。和每个小区的在这阵是怎么回事代表字母表的字母。具体来说，我要去治疗这是A，那么B，然后是C，则D，这一个在这里。所以这将有效地代表字母D. 但插入所有Daven年代名字我需要做多一点。所以我首先要散列，可以这么说。我要去看看第一个字母在Daven的这显然是一个D，我要去分配看起来一个节点像this--一个大的矩形大够以适应整个字母表。现在D被完成。现在A. D-A-V-E-N是目标。所以，现在我什么都做的就是这一点。当我开始D的通知没有指针那里。这是垃圾值的那一刻，或者我可以把它初始化为空。不过，让我赶上去这个想法建立一个树。让我分配一个又一个的这些节点中有26个元素。你知道吗？如果这仅仅是在存储器中的节点我使用malloc创建，用一个struct 因为我们很快就会看到，我该怎么办this-- 我会从画一个箭头这代表的D-下来的东西该新节点。而现在，第一个下一个信Daven的名字， V-- D-A-V--我要继续前进并得出另一个节点是这样，由此，此处的V族元素，其我们将绘制的instance--哎呦。我们不会画在那里。它会去这里。然后，我们要认为这是V. 再往下在这里我们要索引下来从V到我们会考虑E. 然后从这里，我们要去这里有这些节点之一。现在我们有一个问题来回答。我需要以某种方式表明，我们在字符串Daven的结束。所以，我可以把它空。但是，如果我们有Daven的全名也，其是，正如我们已经说过，达文波特？所以，如果Daven是什么实际上是一个子串，一个更长的字符串的前缀？我们不能仅仅永久什么也不说是怎么回事去那里，因为我们可以切勿将像达文波特一个字入该数据结构所以，我们可以做的是把这些元素因为也许有两个他们中的元素。一个是一个指针，的确，因为我一直在做。所以每个这些框不只是一个小区。但是，如果顶部埃德蒙顿底部一个人的要为null，因为有没有达文波特，只是还没有。如果那顶一个为一些特殊的价值？而这将是一个小很难得出它这种规模。但是，假如它只是一个复选标记。检查。 D-A-V-E-N是一个字符串在此数据结构中。同时，如果我有更多的空间在这里，我所能做的P-O-R-T，我可以把检查的节点有字母T在最后。因此，这是一个大规模复杂的外观的数据结构。和我的笔迹肯定没有帮助。但是，如果我想插入的东西否则，考虑一下我们会怎么做。如果我们希望把大卫，我们会遵循同样的逻辑，D-A-V，但现在我想指出，在未来元素不是从E，但是从我到D. 因此，有将是在这棵树多个节点。我们将不得不调用malloc更多。但是，我不想做一个这幅画的一塌糊涂。所以让我们来看看1 一个已经预先制定像这样与不点，点，点，但只是略阵列。但每个节点在这棵树在这里表示同一件事 - 数组的大小26雷。或者，如果我们想成为现在真的很合适，有什么如果某人的名字一个撇号，让我们假设每个节点实际上具有像27指数在里面，不只是26。所以这个现在将是一个数据结构称为trie-- T-R-I-E。一个线索，这是假想历史上的一棵树一个聪明的名字这对优化当然，检索，其中，拼写与I-E所以它的线索。但是，这是对线索的历史。因此，一个线索是这样的树状数据就像一个家庭树结构最终表现那样。这里是一个又一个的例子一大堆别人的名字。但现在的问题手头有什么我们获得了通过引入可以说是一个更复杂的数据结构，和一，坦率地说，使用了大量的内存。因为即使，此刻，我只使用D的指针和 A和V和ES和NS，我在浪费大量的内存赫克。但是，在这里我度过一个资源，我倾向于不争回另一个。所以，如果我花了更多的空间，什么是可能的希望吗？那我花少了什么？听众：更少的时间。 DAVID马兰：时间。现在为什么会这样呢？那么，什么是插时间，在目前大O方面，像Daven一个名字或者达文波特还是大卫？好吧，Daven是五个步骤。达文波特将九个步骤，所以这将是一个几个步骤。大卫将五个步骤为好。因此，这些都是具体的数字，但肯定有的上限的长别人的名字。而事实上，在该问题台五规范，我们要提出它的东西这是40-一些多字符。实际上，没有人有一个无限长的名字，这就是说，一个长度名称或字符串的长度，我们可能有一定的状态结构可以说是什么？这是不变的。对不对？这可能是一个很大的不变样 40多岁的，但它是恒定的。它有多少不依赖其它名称是在该数据结构中。换句话说，如果我想现在插入科尔顿或加布里埃尔或抢或Zamyla或艾莉森或贝琳达或任何其他名称从工作人员到该数据结构，是在运行时间中插入其他名称将要在所有受影响的被多少其他元素在已经将数据结构？它不是。对不对？由于我们有效地利用这个多层哈希表。和运行时间这些操作取决于不上的数这是在数据结构中的元素或者被最终将是在数据结构中，但在什么具体的长度是多少？该字符串是插入，这确实让这种渐进恒一时间 - 大O。坦率地说，就在现实世界中，这指插入Daven的名字取像五个步骤，或者达文波特9 步骤或大卫五个步骤。这是相当不错的小的运行时间。而且，事实上，这是一个非常好东西，尤其是当它不依赖于总量在那里的元素个数。那么如何才能实现我们这个这种结构的代码？这是一个多一点复杂，但它仍然是只是一个应用基本构建块。我要重新定义我们节点如下：布尔称为word--这可以被称为什么。但布尔代表我画了一个对号。是的。这是一个字符串的末尾在此数据结构中。并且，当然，节点星有指儿童。而且，事实上，就像一个家谱，你会考虑节点被挂一些家长的底部元素是儿童。这样一来，孩子们将要是27的数组，第27届1 摆明了撇号。我们要进行排序的特殊情况。所以，你可以有一定名称以撇号。甚至连字符应去那里，但你见P组5，我们只关心有关信件和单引号。然后你怎么代表数据结构本身？你怎么代表根这个线索的，可以这么说？嗯，就像一个链表，你需要一个指针的第一个元素。有线索，你只需要1 指向此线索的根。从那里，你可以散列你的路陷的越来越深以在结构中每一个其他节点。因此，简单地用这个就可以我们代表的结构。现在Meanwhile--呵呵，问题。听众：什么是布尔字？ DAVID马兰：BOOL字只是这款C化身什么，我描述在这里，在这个盒子我开始分裂各数组的元素分为两部分。之一是一个指向下一个节点。其它必须是类似的复选框要说的是，有一个字Daven说到此为止，因为我们不想要的，此刻，戴夫。即使戴夫将是一个合法的一句话，他不是在特里还没有。和D是不发一言。和D-A是不是一个单词或一个名称。因此，复选标记表示只有当你打这个节点是字符前面的路实际上，你已经插入一个字符串。这就是所有的布尔那里是做给我们。在尝试任何其他问题？是啊。听众：什么是重叠？如果你有一个戴夫和Daven？ DAVID马兰：完美。如果你有一个戴夫和Daven？所以，如果我们插入，说一个绰号，对于David-- Dave-- D-A-V-E？其实，这是超级简单。因此，我们只是要带四个步骤。 D-A-V-E。和我有什么要做一次，我打了四节点？只是去检查。我们已经好到哪里去。完成的。四个步骤。固定时间渐近。现在我们已经表明，无论戴夫和Daven是在结构中的字符串。所以不存在问题。并注意存在 Daven的没能需要更多的时间或更少时间戴夫，反之亦然。那么还有什么可以，现在我们怎么办？我们以前使用过这个隐喻托盘代表什么。但事实证明，一个托盘堆实际上是示范的另一个抽象数据类型 - 一个更高层次的数据结构这在最后的日子就是像阵列或链接的列表什么更现实。但它是一个更有趣概念的概念。堆栈，这样的托盘在这里马瑟通常被称为只是that--堆栈。并且在这种类型的数据结构你有两个operations-- 你有一个叫推添加的东西到堆栈，就像把另一盘备份在堆栈的顶部。然后弹出，这意味着你把最上面的托盘掉。但是，什么是关键关于堆栈是它有这种奇怪的特点。由于食堂工作人员重新排列的托盘为下一顿饭，这是怎么回事是真正了解学生如何这种数据结构进行交互？听众：他们将弹出一关。 DAVID马兰：他们要去弹出一关，希望上面。否则，它只是一种愚蠢一路走到底。对不对？该数据结构并没有真正允许你至少要抢底盘很容易。因此，有这种奇怪的属性堆栈在最后一个项目是将成为第1列。和计算机科学家称之为这LIFO--后进先出。它实际上确实有有趣的应用程序。它并不一定那么明显一些其他人，但它确实能是有用的，它确实能实现在几个不同的方式。所以一个，实际上，让我不要潜入了。让我们这样做吧。让我们来看看一个几乎在同样的想法，但它是一个更公平一点。对不对？如果你是这些球迷的一个男孩或女生真的喜欢苹果产品而你在上午03点00分就醒了排队在一些商店获得最新的iPhone，你可能排队这样的。现在队列很刻意的名字命名。这是一条线，因为有一些公平吧。对不对？种它将如果你吸到了那里在Apple Store第一但你有效的最底部托盘是因为苹果公司的员工，然后流行的最后一个人谁实际上得到的线。因此，栈和队列，即使在功能上，他们是那种same--的它只是这个集合资源，这是要发展和shrink--还有的这种公平性方面吧，至少在现实世界中，其中，操作你锻炼是根本不同的。一个stack--队列 rather--据说有两个操作：N队列和D队列。或者你可以给他们打电话任何数目的东西。但是，你只是想捕捉一个是增加的概念和一个最终被减去。现在的发动机罩的下面，两者的堆栈和队列可以实现怎么样？我们不会进入代码这是因为在较高的水平思想是那种比较明显。我的意思是，人类该怎么办？如果我是第一人，在苹果存储，这是前门，你知道，我要站在这里。和旁边的人的站在这里。和旁边的人的站在这里。那么，什么数据结构适合于一个队列？听众：队列。 DAVID马兰：嗯，一个队列。当然可以。还有什么？听众：链表。 DAVID马兰：一个链接列出你可以实现。和链表是好的，因为这样而不是可任意长长具有一些固定的数人在店里。但也许一个固定的数地方是合法的。因为如果他们只有像20 iPhone手机的第一天，也许它们只需要尺寸的阵列 20代表该队列，这只是现在说一旦我们开始讨论关于这些较高级别的问题，你可以实现它在任何数量的方式。还有的可能只是要是一个折衷在空间和时间或只是在自己的代码的复杂性。那么堆栈？好了，一个栈，我们已经看到太多可能仅仅是这些托盘。而且你可以实现这个数组。但在某些时候，如果你使用一个数组，什么事情要发生在托盘你想放下？行。你只打算能走这么高。我认为，在马瑟他们实际上凹进的开放。所以，事实上，它几乎像奥美使用固定大小的阵列，因为你只能在开放符合这么多托盘墙壁向下跌破人们的膝盖。因此，可能是说是一个数组，但我们可以肯定的实施更一般地用一个链表。那么，关于另一个数据结构？我拉起另一个视觉这里。像这个怎么在这里？为什么会到没有它是有用的一些花哨的线索，这我们看到了这些非常宽的节点，其中每一个是在一个数组中？但是，如果我们做更多的事情简单地说，就像一个老同学的家谱，每一个在这里的节点只是存储号码。而不是一个名称或后裔只是存储了一些类似这样的。好了，我们行话使用数据结构是既尝试和树木，其中一个线索，再次，是只有一个的节点阵列，依然是你可能会从小学使用当你犯了一个家庭 tree--叶和根树和儿童父母和兄弟姐妹物。我们可以实现一个树，例如，作为简单的了。树，如果它作为一个节点，一个这些圆，其具有数，它不会有 1指针，而是两个。而且只要你加入第二个指针，实际上现在做排序的二维数据结构在存储器中。很像一个二维数组，你可以有种类的二维链表但那些下面的模式那里没有周期。这是一个真正的有一棵树了祖父母的方式在这里再一些家长和孩子孙子和曾孙。等等。但是，什么是真正的整洁对此也只是逗你一些代码，从调用递归一段时间回来，因此你写一个函数，该函数调用自身。这是一个美丽的机会实施东西像递归，因为考虑这一点。这是一个树。我已经有点肛门如何我把整数到街上。正因如此，它有一个特殊的名称 - 二叉查找树。现在，我们已经听说二进制搜索，但你能从这个东西的名字倒着工作？什么是我如何的格局插入整数到这棵树？它不是随意的。这里也有一些图案。是啊。听众：在左边较小的。 DAVID马兰：是啊。较小的是在左侧。更大的是在右侧。这样，真正的语句是家长大于它的左孩子，但比其右孩子少。而这仅仅是一个连递归定义语言因为你可以应用相同的逻辑的每一个节点而且它仅塔底如果你出去，基本情况会的，当你打一个叶子，可以这么说，凡请假没有孩子更进一步。现在，你怎么可能找到44号？你会从根开始，说，嗯。 55不是44，我想去正确的还是我想往左走？显然，你想要去左边。所以它就像手机在二进制搜索本书实例更普遍。但我们实现它现在多了几分动态不是一个数组可以允许。而事实上，如果你想看看在代码中，第一眼肯定。它看起来像一大堆线。但它的美丽很简单。如果你想实现一个功能所谓的搜索，其目的在生活中是要搜索的一个值像N，整数，和你在一pointer--正在通过一个指向根的节点，那棵树的相当，从您可以访问其他的一切，注意如何直截了当地你可以实现的逻辑。如果树是空，显然它不存在。让我们只返回false。对不对？如果你把它什么都没有，有什么也没有。否则，如果n小于树箭头N--现在箭头N，记得我们推出超短暂的一天，那只是意味着去参考指针看看所谓的n个场。因此，这意味着去那里看看所谓的n个场。所以，如果N，你给出的值，小于比在树木整数的值，你想去哪儿去了？向左转。所以，注意递归。我returning--不正确的。不假。我回来什么的答案是通过调用自己，路过的n再次，这是多余的，但什么是略有不同呢？我怎么做的问题更小？我传递的第二个参数，该树的不根，但左子在这种情况下。所以我通过左边的孩子。同时，如果n是大于该节点目前，我正在看，我搜索的右侧。否则，如果树不为空，而如果元素不是向左它并不是正确的，什么是奇妙的情况？实际上我们发现，节点的问题，所以我们返回true。所以我们刚刚触及表面现在一些数据结构。在问题设置5，你会再进一步探讨这些，你会得到你的设计选择如何去了解这一点。我想缔结仅仅30秒的预告片下周及以后有什么在等待着。正如我们begin--谢天谢地你可能慢慢think--我们的转型从C和下部的世界层次的实现细节，一个世界里，我们可以采取的理所当然地认为别人终于实现了这些数据结构对于我们来说，我们将开始了解现实世界是指实施基于网络的程序和网站更普遍并且也很安全我们只已经影响开始划伤的表面上。这是什么等待着我们在未来的日子里。 [视频回放] - 他想出了一个消息，有协议的所有他自己的。他来到了残酷的世界防火墙，路由器漠不关心，和危险远远比死还要痛苦。他的速度快。他是强大的。他是TCP / IP，和他有你的地址。 “勇士的网。” [完视频回放] DAVID马兰：下周即将。我们会看到你呢。 [视频回放] - 和现在，“深度思考” 通过Daven法纳姆。 -David总是开始与讲座，“好吧。” 心动不如行动，“这里的解决方案本周的问题集“ 或者“我们给大家一个A？” [笑气] [完视频回放]