扬声器1：好吧，所以这是 CS50这是五个星期结束。 而记得我们最后一次 开始寻找在票友数据 即开始解决结构 问题，即开始引入 新的问题，但关键就在这 是线程的排序，我们 开始做从节点到节点。 因此，这当然是 一个单向链表。 而由单链表， 我的意思是只有一个 每个这些节点之间线程。 原来，你可以做票友 像双向链表 因此，你有一个箭头 要在两个方向上，这 可以帮助具有一定的效率。 但这个问题是否解决？ 有什么问题没有解决这个？ 为什么我们关心在星期一？ 为什么在理论上，我们没在意周一？ 它做什么？ 听众：我们可以动态地调整它的大小。 扬声器1：OK，所以我们可以 动态地调整其大小。 干得好你们俩。 所以，你可以动态调整这个 数据结构，而阵列， 回想一下，你必须知道 先验多少空间你想 如果你需要更多一点的 空间，你是那种运气。 你必须创建一个全新的阵列。 你必须将所有的 从一个到另一个数据， 最终释放旧阵列 如果可以的话，然后继续。 这只是感觉非常昂贵，非常 效率低，而且确实可以。 但是，这是不是所有的好。 我们付出的代价，究竟是什么1 较为明显的价格上涨，我们 通过使用链表买单？ 听众：我们必须使用 为每一个双层空间。 扬声器1：是啊，所以我们需要 至少两倍的空间。 事实上，我意识到这张照片的 甚至有点误导， 因为在许多现代的CS50 IDE 计算机，一个指针或地址 事实上并非四个字节。 这是很多时候，这些 天8字节，这 装置的底部最 在现实中的矩形有 是那种两倍 大如我所绘制的， 您正在使用三倍的手段 多的空间，我们可能有其他方式。 现在，在同一时间，我们 还在说话字节，对不对？ 我们不一定讲 MB或GB， 除非这些数据结构变大。 所以，今天我们开始考虑 我们可以如何发掘数据 更有效地如果 事实上，数据变得更大。 但是，让我们试着规范化 操作第一 你可以在这些干什么 种数据结构。 因此，像一个链接 清单普遍支持 操作像删除， 插入，和搜索。 什么做我的意思？ 这只是意味着，通常情况下， 如果人们使用链表， 他们或者其他人实施 如删除，插入功能， 和搜索，这样你就可以 确实做了什么 有用的数据结构。 因此，让我们快速浏览一下 我们如何可能实现 一些代码，一个链表如下。 所以，这只是一些C代码， 甚至没有一个完整的程序 我真的很快刮起了一阵。 这不是在网上分销 码，因为它不会实际运行。 但是请注意，我只是 有评论说， 点点点，有什么东西 在那里，点点点，东西在那里。 而且，我们只是看看 什么多汁的部件。 因此，在三线， 记得，这是现在 我们提出声明最后一个节点 时间，这些矩形物体中的一个。 它具有我们称之为为N的INT， 但我们可以把它叫做什么， 再一个结构节点明星叫旁边。 而仅仅是明确的，即第二 线，对线6条，那是什么？ 它是什么做的我们呢？ 因为它确实看起来更 神秘的比我们平常的变量。 听众：这使得它搬过来的。 扬声器1：这使得它搬过来的。 和更精确， 它将存储的地址 这意味着是该节点的 语义旁边，对不对？ 所以它不会 不一定移动任何东西。 它只是要 存储一个值，这是 将是地址 一些其他节点的， 这就是为什么我们说结构 节点明星，明星表示 的指针或地址。 好了，现在，如果你认为我们有 这款N提供给我们，让我们 假设别人有 插入一大堆整数 成一个链表。 并且链表是 一些点指向 一个变量调用列表的 在这里作为参数传递， 我怎么去行 14实现搜索？ 换句话说，如果我实现 功能，其目的在生活中 是采取一个int，然后 开始的链表， 这是一个指向该链接的表。 像第一，谁我认为大卫 是我们的志愿者在周一， 他指着 整个链表， 就好像我们传递 大卫在这里我们的论点。 我们如何去遍历这个名单？ 嗯，事实证明，即使 指针是比较新的，现在对我们来说， 我们可以相对做到这一点 直截了当。 我要继续前进， 声明临时变量 按照惯例，只是走 被称为指针或PTR， 但你可以把它称为任何你想要的。 而且我要初始化 它到列表的开头。 所以，你可以种想到这 作为我的老师有一天， 那种指着别人 在我们人类作为志愿者。 所以，我是一个临时变量，它是 只是指向同一件事 我们不约而同地命名 志愿者大卫也指出。 现在，当指针 不为空，因为召回 那空是一些特殊的标记值 所述标定列表的末尾， 因此，虽然我不指着 地面像我们过去的志愿者 是，让我们继续 并做到以下几点。 如果pointer--和那种我现在想 做我们的学生做了 结构 - 如果指针点下一个 equals--相反，如果指针点N等于 等于变量N，所述 这就是被传入的说法， 那么我想继续 说返回true。 我已经发现了内部数N 我的一个链表节点。 但点不再 工作在这样的背景下， 因为指针，PTR，是 确实是一个指针，地址， 我们实际上可以精彩 使用最后一张语法 那种品牌： 直观感觉，实际上 用一个箭头这里，这意味着从去 该地址中的整数那里。 所以这是非常相似 精神点运算符， 但因为指针不是指针 而不是实际的结构本身， 我们只是用箭头。 因此，如果当前节点是我的 临时变量，我指着 是不是N，我该怎么想干什么？ 好了，我的志愿者 我们曾在这里的一天， 如果我的第一个人是不是一个我 想，也许第二个人是不是 一个我想要的，第三，我 需要保持身体移动。 像我怎么通过列表步骤？ 当我们有一个数组，你 只是不喜欢我加再加。 但在这种情况下，它足以 做指针，获取，指针，下一个。 换句话说，下一个字段 就像所有的左手 我们在周一志愿者 分别使用以指向某些其它节点。 那是他们的下一个邻居。 所以，如果我想一步，通过这个名单， 我不能只是做我加再加了， 我反而不得不说 我，指针，是怎么回事 等于任何下一个字段是 下一字段，下一个字段是 下面所有这些左手 我们有在舞台上指点 一些后续值。 如果我打通 那整个循环， 最后，我打空没有 发现ñ然而，我刚刚返回false。 如此反复，所有我们在这里做， 按照刚才的图片， 开始通过指向 开头的名单大概。 然后我检查，是价值 我在寻找等于九？ 如果是的话，我还真和我完成了。 如果没有，我更新了我的手， AKA指针，指向 下一个箭头的位置， 那么下一个箭头的位置， 和下一个。 我只是在这个数组中行走。 如此反复，谁在乎呢？ 什么样的事情，这是一种成分呢？ 嗯，记得我们介绍 栈的概念，这 是一个抽象数据类型的范围内，因为它是 不是C的东西，它不是一个CS50的事情， 这是一个抽象的概念，在这一理念 堆叠的东西上彼此之上 可以在实施 不同的方式束。 我们提出了一种方法是用 阵列，或具有一个链表。 而事实证明，规范地，一 栈支持至少两个操作。 而时髦的话是推，以 推动东西压入堆栈， 像在一个新的盘 食堂，或流行， 这意味着以除去最上层 从堆栈中的餐盘 大厅里，然后也许有些 其他操作为好。 那么，如何可能，我们定义结构 我们现在调用堆栈？ 好了，我们有所有必要的 语法我们所掌握的C.我说， 给我一个类型定义 一摞内部的结构， 我要说的是一个数组， 一大堆的数字，然后大小。 因此，换句话说，如果我想 在代码来实现这一点， 让我去那种公正， 画什么，这是说。 因此，这是说，给我一个 那一定阵列结构， 我不知道是什么能力， 这显然​​有些不变，我已经 其他地方定义，这很好。 但是，假如这只是之一， 二，三，四，五。 所以容量为5。 里面这个元素我 结构将被称为数字。 然后，我需要 其他变量明显 最初我打算叫大小 到规定初始化为零。 如果有什么的 堆栈，大小是零， 而且它在数量上的垃圾值。 我不知道里面有什么了，只是还没有。 所以，如果我要推 东西压入堆栈， 假设我调用函数推，并 我说推50，喜欢50号， 在这里，你会建议 我画它在这个数组？ 有五种不同的可能的答案。 你想去哪里推的50号？ 如果这里的目标，再次拨打 功能推，传递一个参数 50，我在哪里放呢？ 五possible-- 20％的几率 的猜测正确。 是吗？ 听众：最右。 扬声器1：最右。 现在有25％的几率 的猜测正确。 所以这实际上是罚款。 按照惯例，我会说一个数组， 我们一般将开始在左边， 但我们可以肯定 开始在合适的。 因此，这里的扰流板会是我 可能将其绘制在左边， 就像在一个正常的数组，其中 我开始从左到右。 但是，如果你可以翻转 算术，罚款。 这只是不是常规的。 好吧，我需要做一个 更多的变化，虽然。 现在，我已经把东西 压入堆栈，接下来会发生什么？ 好吧，我得增加尺寸。 因此，让我继续前进，只是 更新这，这是零。 而不是现在，我要去 放中的值之一。 现在假设我推另一 数压入堆栈，如51。 好了，我一定要多一个 变化，这是向上的大小两种。 再假设我推多了一个 数入堆栈像61， 现在我需要更新的大小多一个 时间，并获得值3作为大小。 现在假设我叫流行。 现在流行，按照惯例， 不带参数。 用栈，整 点盘隐喻 是你没有自由裁量权 去得到那个盘子，你所能做的 是流行最上面的 堆栈，只是因为。 这就是这个数据结构一样。 因此，通过这种逻辑，如果我 要说流行，会发生什么了吗？ 所以61。 那么，什么是真正的计算机 打算做的内存？ 什么是我的代码有什么关系？ 你会建议 我们改变在屏幕上？ 应该怎么改？ 对不起？ 所以我们摆脱61。 所以，我绝对可以做到这一点。 我可以摆脱61。 然后还有什么其他 改变需要发生？ 尺寸可能有回去两种。 所以，这很好。 但是且慢，大小 刚才是三。 让我们做一个快速的完整性检查。 我们是怎么知道我们 想摆脱的61？ 因为我们大跌眼镜。 所以我有第二个属性的大小。 等一下，我 回想起2周 当我们开始谈论 阵列，在这位置为零， 这是位置之一，这是位置 二，这是位置三个，四个， 它看起来像 大小之间的关系 而我想要的元素删除 从阵列似乎只是什么？ 尺寸减一。 所以，这就是如何为人类 我们知道61是第一位的。 怎么样的电脑会知道？ 当你的代码，你很可能 想做大小减一， 所以三减一为两个，并且 意味着我们要摆脱61。 然后，我们的确可以更新 这样大小的体积，现在 进入三到只有两个。 而刚需迂腐，我要去 提议我做的，对不对？ 你直观地提出 正确我应该摆脱61。 但是，有一种没有我 那种摆脱了61？ 我已经有效地忘记 它的实际存在。 而回想起PSET4，如果你读过 有关取证的文章中，PDF 我们有你们看，或者你 将读取本周PSET4。 回想一下，这其实是有密切关系的 计算机取证的整体思路。 什么是电脑一般不为 它只是忘记在那里的东西是， 但它并没有去和像 试着刮出来或重写 这些位与零和一 或一些其它的随机图案 除非你自己这样做的故意。 所以，你的直觉是 好吧，让我们摆脱61。 但在现实中，我们没有理会。 我们只需要忘记， 它的存在，通过改变我们的规模。 现在有这个堆栈的一个问题。 如果我继续推动东西 压入堆栈，什么是 显然不会发生 在短短的几分钟时间？ 我们将用尽空间。 而我们该怎么办？ 那种我们搞砸了。 此实现不让 我们调整阵列，因为使用 这个语法，如果你 回想起每周二， 一旦你已经声明 阵列的大小， 我们还没有看到一个机制，但在这里 可以改变阵列的大小。 事实上C没有这个功能。 如果你说给我五 国道主干线，称他们的数字， 这就是你要得到它。 所以我们现在要做的是周一，有 表达一个解决方案的能力 虽然，我们只需要调整 我们的叠层的定义 不要被一些硬编码的数组， 但只是以存储一个地址。 现在，这是为什么？ 现在，我们只需要坦然面对 事实证明我的程序运行时， 我大概会 要问的人， 多少个号码，你想存储？ 因此，输入有来自某处。 但是，一旦我知道， 号码，然后我可以 使用什么功能给 我的内存块？ 我可以用malloc。 我可以说，任何数量的 字节，我想回去了这些国道主干线。 而且我必须存储在数字 可变这里这个结构里面 应该是什么？ 究竟进入 在这种情况下的数字？ 是啊，一个指向第一 该内存块的字节， 或更具体地，地址 第一这些字节。 如果它是一个不事 字节或十亿字节， 我只需要关心的第一个。 因为什么样的malloc担保， 我的操作系统担保， 是，存储器I组块 得到的，这将是连续的。 还有的不会是空白。 所以，如果我问50 字节或1000个字节， 他们都将是 背靠背回来。 而只要我还记得有多大，怎么 很多我要求，我所需要知道的 是第一个这样的地址。 所以，现在我们已经在代码的能力。 虽然，这将带我们 更多的时间来写这件事， 我们现在可以通过重新分配内存 只是存储不同的地址有 如果我们想要一个更大的，甚至 较小的组块的存储器。 因此，在这里一个权衡。 现在，我们得到的活力。 我们仍然有 contiguousness我自称。 因为malloc的给我们 一个连续的内存块。 但是，这将是一个痛苦 脖子对我们来说，程序员， 实际代码了。 这只是更多的工作。 我们需要的代码类似于我是什么 刚才撞了。 非常可行，但增加了复杂性。 因此开发时，程序员 时间是另一个资源 我们可能需要花 一段时间来获得新的功能。 然后当然还有一个队列。 我们不会进入这个 之一，很多细节。 但它在精神上非常相似。 我可以实现一个队列， 其相应的操作， 入队或出队，像添加或删除， 它是说这只是一个华丽的方式， 入队或出队，如下。 我只能给自己一个结构 一遍的数的阵列， 一遍的尺寸， 但为什么我现在需要 跟踪一个队列的前面的？ 我并不需要知道 前面我堆栈。 好吧，如果我再一 queue--就让我们很难 它编码具有到五 整数这里可能。 因此，这是零，一，二，三，四。 这将是 拨打的号码了。 而这将是所谓的大小。 为什么不充分 以刚才的大小？ 好吧，让我们推动这些相同的数字。 所以我pushed--我入队，或推。 现在，我将排队50，然后 51，然后61，和点点点。 所以这是入队。 我入队的50，然后51，然后61。 这看起来相同 到烟囱迄今 但我确实需要做出一个改变。 我需要更新这个尺寸，所以我去 从零到一到两到三现在。 我如何出列？ 与出队会发生什么？ 谁应该打这个名单第一 如果是该行的苹果专卖店？ 所以50。 因此，它是有点棘手这个时候。 而上一次是超级 易只是做大小减一， 我得到我的数组的末尾有效 其中数字是，它消除61。 但我不希望删除61。 我想利用50，谁 在那里，在上午5:00 排队的 新的iPhone或诸如此类的东西。 所以，要摆脱50，我 不能仅仅做到这一点，对不对？ 我可以划掉50。 但是，我们刚才说了，我们 不必如此肛门 以划掉或隐藏数据。 我们可以忘记它在哪里。 但是，如果我现在改变我的尺寸， 二，这是足够的信息 知道什么是我的排队怎么回事？ 并不是的。 就像我的尺寸是两个，而是 哪里排队开始， 尤其是如果我仍然有 那些相同的标号在存储器中。 50，51，61。 所以，我需要记住 现在所在的前面。 所以，我提出了 在那里，我们将刚才叫 第N次前，其初始 价值应该是什么呢？ 零，列表仅仅是个开始。 但现在除了递减 规模，我们只是增加了前面。 现在，这里是另外一个问题。 所以一旦我继续前进。 假设这是数 像121，124，然后，该死， 我的空间。 但是且慢，我不是。 所以在这一点中的故事， 假设尺寸是一，二， 三个，四个，所以假设 大小为4，前一个， 所以51是在前面。 我想提出另一个号码在这里， 但是，该死，我出了空间。 但我不是真的，对不对？ 我在哪里可以把一些 附加价值，如171？ 是的，我能正中下怀 回去那边了吧？ 然后过了50，或 只是简单地覆盖它与171。 如果你想知道为什么 我们的数字变得如此随意， 这些通常采取计算机 科学课程在哈佛CS50之后。 但是，这是一个很好的优化， 因为现在我没有浪费的空间。 我还是要记住 有多大这个东西是总。 它共有五次总。 因为我不希望 开始覆盖51。 所以，我现在还在外面的空间， 从而前同样的问题。 但是你可以看到现在 在你的代码，你可能 有一点写更多 复杂性来实现这一目标。 而事实上，运营商所 C语言可能让 你神奇地做到这一点的圆？ 是的模运算符， 百分号。 那么，有什么样的酷的队列， 尽管我们不断吸引数组 因为这些象直线，如果 那种认为关于这个问题，弯曲 作为周围一圈，然后就 一种直觉它的工作精神 我觉得有点更干净。 你仍然必须执行 在代码中的心智模式。 所以并不难， 最终，实施， 但我们还是失去了size--相当， 能力来调整，除非我们做到这一点。 我们必须摆脱的数组，我们 它与单个指针替换， 然后地方在我的代码我有 一个叫什么函数来实际创建 数组拨打的号码？ malloc或一些类似 功能，没错。 在栈或队列的任何问题。 是吗？ 好问题。 你会用什么在这里模。 所以一般地，在使用 MOD，你会做 同的大小 整体的数据结构。 因此，像五容量，如果 这是不变的，可能是参与。 但只是在做模数5 可能是不足够的， 因为我们需要知道我们是否 环绕在这里或在这里或在这里。 所以，你可能还 将要涉及到 事物的大小，或 前面的变量也是如此。 所以，它只是这个比较 简单的算术表达式， 但模将是关键因素。 所以，短片，如果你会的。 一个动画，一些 人们在另一所大学 放在一起，我们已经 适用于本次讨论。 它涉及杰克学习 有关队列和统计数据的事实。 电影：曾几何时， 有一个叫杰克的家伙。 当它来交朋友， 杰克没有一个诀窍。 于是杰克就去找了 最流行的家伙，他知道。 他到楼，问道，我该怎么办？ 娄看到他的朋友 真的很心疼。 好了，他开始，就 看你如何打扮。 你没有任何的衣服 以不同的面貌？ 是的，杰克说。 我当然有。 来我家， 我会告诉他们你。 于是他们去了杰克的。 和杰克表明娄盒 在那里他保持他的所有衬衫， 和他的裤子，他的袜子。 楼继伟说，我看你有没有 你的衣服在一堆。 你为什么不穿些 其他人曾经在一段时间？ 杰克说，好吧，当我 脱去衣服和袜子， 我把它们洗干净，并把 他们走在框中。 然后是下一个 早晨，起来我一跳。 我去的箱子，并得到 我的衣服上。 娄很快就意识到 这个问题与杰克。 他不停的衣服，光盘， 并且堆叠的书籍。 当他伸手 一些阅读或磨损， 他会选择顶部的书或内衣。 然后，当他完成，他 会把它的右后卫。 回到它会去，在堆栈的顶部。 我知道解决的办法， 说胜利响亮。 你需要学习 开始使用一个队列。 娄花了杰克的衣服， 他们挂在衣柜里。 而当他已经清空 盒子，他只是扔。 然后他说，现在的杰克，在年底 当天，穿上你的衣服左边 当你把他们带走。 然后明天早上，当你 看到阳光，让你的衣服 在右边，从行的末端。 你难道不明白吗？说楼。 这将是那么好。 你会冲刷一切的一次 你穿的东西之前两次。 而随着一切都在排队 在他的衣柜和书架， 杰克开始感觉 十分肯定自己。 娄所有的感谢和 他精彩的队列。 扬声器1：好吧，这是可爱的。 那么，什么是怎么回事 在现在的引擎盖下？ 我们有三分球， 我们拥有的malloc， 我们有能力创造 内存占为己有块 动态。 所以这是一个图片我们 瞥见就在几天前。 我们真的不纠缠 就可以了，但这张照片 已经持续下 现在引擎盖几个星期。 所以这代表，只是 我们已经绘制一个矩形， 您的计算机的内存。 也许你的电脑，或者CS50 ID，具有存储器或RAM一个千兆字节 两个千兆字节或四个。 这其实并不重要。 您的操作系统 Windows或Mac OS或Linux， 基本上可以让你的程序 认为它能够访问 到的全部 您的计算机的内存， 即使你可能正在运行 多程序同时应用。 因此，在现实中，没有真正发挥作用。 但它是一种一种假象 给所有的程序。 所以，如果你有内存2音乐会，这 是怎样的计算机可能会想到它。 现在，巧合的是，其中一个 事，内存这些领域之一， 被称为堆。 实际上，任何时候 迄今在编写代码 你已经被称为 功能，比如主。 回想一下，任何时候我已经 得出计算机的内存， 我总是吸引排序 一半的矩形的这里 也懒得说话 关于什么的上面。 因为当主被调用时，我要求 你得到这个条子的记忆 该下降这里。 如果主称为函数 像掉期，以及交换到这里。 而事实证明，这是 其中，它的结束了。 在被称为堆的东西 在你的计算机的内存中。 现在在一天结束时， 这仅仅是解决了。 这就像一个字节零， 字节之一字节2十亿。 但是，如果你仔细想想 因为这样的矩形对象， 我们所做的每一个 一次，我们调用一个函数 分层存储新的切片。 我们给这个函数片 自身的存储器的工作。 现在回忆起来，这是非常重要的。 因为如果我们确实有 类似的交换 像A和B两个局部变量 我们改变这些值从一个和两个 两个和一个，召回 当交换返回， 这是因为虽然这片 内存只是走了。 在现实中，它仍然 有取证。 而一些仍然居然有。 但在概念上，这是因为 虽然它完全消失了。 所以主不知道任何工作 这是在交换功能完成后， 除非它实际上是通过这些 通过指针或引用参数。 现在，从根本上解决 该问题与交换 通过地址传递的东西研究。 但事实证明也是如此，什么是 已经持续了上面那一部分 矩形的这段时间是 但有更多的内存在那里。 动态当你 分配内存， 无论是GetString的，里面的这 我们在CS50已经为你做 图书馆，或者，如果你们 调用malloc和要求 对于一大块的操作系统 存储器，它不是来自堆栈。 它来自另一个地方 在您的计算机的内存 这就是所谓的堆。 而这没有什么不同。 这是相同的RAM。 这是同样的内存。 这只是在RAM那达 那里，而不是到这里。 所以，这是什么意思？ 好吧，如果你的电脑有 的存储器量有限 与堆栈长大，所以 说话，堆，根据 这一箭，越来越大了。 换句话说，每 一次调用malloc， 你被赋予了片 的存储器从上方 那么也许更低一点，然后一点点 低，每次调用malloc的时候， 堆，它的使用情况， 是一种成长， 日益密切的是什么？ 堆栈。 那么，这似乎是一个好主意吗？ 我的意思是，它并不真正清楚 如果你只可以做什么 具有存储器的有限数量。 但是，这肯定是不好的。 这两个箭头都在一个 当然崩溃彼此。 而事实证明，坏家伙，人们谁 与节目特别好， 并试图侵入电脑， 可以利用这个现实。 事实上，我们考虑 一个小片段。 因此，这是你可以阅读的一个例子 关于维基百科上的更详细。 我们将向您在 文章，如果好奇。 但是有一般的攻击 被称为缓冲区溢出的 只要已经存在了作为人类 不得不操纵能力 计算机的内存，尤其是在C中 所以这是一个非常随意的程序， 但让我们从下往上看。 主要为焦炭ARGC ARGV明星。 所以这是一个程序，它 命令行参数。 和所有主要的也显然是通话 一个函数，调用它F代表简单。 它在传递什么？ ARGV之一。 因此，它传递到f中的任何 的话，就是用户键入 在之后的提示 节目的名字都没有。 那么像撒或的Vigenere，这 你可能还记得与ARGV做。 那么，什么是F？ ˚F接受一个字符串 作为其唯一的参数， AKA一个char明星，同 首先，作为一个字符串。 而这就是所谓的任意 禁止在这个例子。 然后焦炭C 12， 只是外行人的话说， 什么是CHARÇ支架12做的我们呢？ 它是什么呢？ 分配内存，专 12个字节为12个字符。 没错。 然后最后一行，搅拌， 副本，你可能没见过。 这是一个字符串拷贝 功能，其目的在生活中 是复制它的第二个参数 到了第一个参数， 但只达到一个 一定数量的字节。 所以第三个参数说： 你应该有多少个字节复制？ 条的长度， 无论用户键入。 及内容 酒吧，该字符串，是 拷贝到存储指向在C. 因此，这似乎是一种愚蠢的，它是。 这是一个人为的例子， 但它代表 一类攻击向量的， 一种方式攻击的程序。 一切都很好，好，如果用户 在一个字那是11个字符类型 或更少，加上反斜杠零。 如果在用户键入超过什么 11或12或20或50个字符？ 这是什么程序该怎么办？ 潜在的赛格故障。这是怎么回事 要盲目照搬一切都在酒吧起来 其长度，这是 从字面上的一切吧， 到地址指向C.但Ç 只抢先给出12个字节。 但是，没有任何额外的检查。 有没有，如果条件。 有没有错误检查在这里。 所以这个计划是什么 要做的只是一味的 一件事复制到其他。 所以，如果我们得出这样的 作为一个图片，这里的 内存空间只是一个条子。 所以，注意在底部，我们 有局部变量吧。 这样的指针，那将store-- 而当地的论点，即是 将存储字符串吧。 然后请注意只是 它在一组的上方， 因为每次你问的时间 为存储器的栈上， 它会一点点 它形象地上面， 我们已经得到了12个字节有通知。 顶部左边的一个是C支架为零， 底部正确的是C支架11。 这是多么的电脑 要打好它。 因此，只要凭直觉，如果酒吧有更多的 超过12个字符共包括 反斜杠零，在哪里 12的C支架12要去？ 或者说在这里是第12个 字符或13个字符， 第一百字去 结束了在图片？ 高于或低于？ 对，因为即使 栈本身是向上增长， 一旦你把东西在 它，它的设计的原因， 放存储器从上到下。 所以，如果你有超过12个字节， 你将开始覆盖吧。 现在，这是一个错误，但它的 不是一个真正的大问题。 但是，这是一个大问题，因为有 更多的东西在内存回事。 因此，这里是我们如何能够 把你好，是明确的。 如果我输入打招呼的提示。 H-E-L-L-O反斜杠零，在结束了 这12个字节，而且我们的超级安全。 一切都很好。 但是，如果我输入一些东西 时间越长，可能是 要潜入酒吧空间。 但更糟糕的是，事实证明 出这么长的时间， 即使我们从来没有谈过 它的堆栈用于其他的东西。 这不只是局部变量。 C是一个非常低的水平的语言。 排序，并偷偷 使用堆栈也 要记住，当 函数被调用，什么 地址是以前的功能， 因此它可以跳转回该功能。 因此，当主呼叫交换，其中 的事情压入堆栈 不只是交换局部变量， 或者它的参数，还偷偷推 入堆栈为代表 这里由红切片， 是主要的地址物理 在计算机的内存， 这样，当交换完成时，计算机 知道我需要回到主 并完成执行的主要功能。 所以，现在这样是很危险的，因为如果 中公比你好更多的用户类型， 使得用户的输入则会覆盖 或将覆盖红色的部分， 逻辑上，如果计算机的 只是要盲目地承担 在这片红色的字节 地址到它应该返回， 如果对手是足够聪明或 幸运地把字节序列 还有，看起来像一个地址， 但它的代码的地址 他或她想要的计算机 而不是主要的执行？ 换句话说，如果什么 用户在提示符下敲入， 不只是一些 无害喜欢你好， 但它实际上代码是等价 删除所有该用户的文件？ 或者通过电子邮件发送密码到我吗？ 或者，开始记录自己的 按键，对不对？ 有一种方法，让我们今天的规定， 他们可以输入不只是打招呼 世界还是他们的名字， 他们可能根本 通过在代码中，零和 的，该计算机 错误的代码和一个地址。 因此，尽管有些抽象，如果 足够的对抗代码用户类型 我们将归纳这里 答：是的攻击或敌对。 所以只要坏的东西。 我们不关心 数字或零或1 今天，这样你最终 覆盖的红色款， 请注意字节的顺序。 Ø835℃零八零。 现在，维基百科的文章在这里 建议，如果你现在居然开始 标签在您的计算机中的字节 内存，维基百科的文章是什么 的提出的是，如果有什么的地址 除此之外左字节为80℃0 3508。 换句话说，如果坏家伙是 与他或她的代码足够聪明 实际上把一些在这里， 对应于编码的地址 他或她注入 插入电脑，你 可以欺骗计算机 为做任何事情。 删除文件，电子邮件 事，嗅探您的流量， 从字面上什么事情都可能会 注入到计算机。 所以缓冲区溢出 进攻的核心 仅仅是一个愚蠢，愚蠢 数组压倒一切的 没有它的边界检查。 这是什么是超级危险 同时超级强大 在C是，我们确实有 访问在存储器的任何位置。 这取决于我们的程序员， 谁写的原代码 检查所有的织补长度 阵列，我们正在操纵。 所以要清楚，有什么解决？ 如果我们回滚到该 代码，我不应该只是 改变杆的长度，什么 别的我应该检查？ 还有什么我应该做的到 防止这种攻击完全？ 我不想只是一味地说 你要复制的字节数 作为是条的长度。 我想说，复制为 许多字节都在酒吧 向上到分配 存储器，或12最大限度。 所以，我需要某种形式的if条件 ，做检查吧的长度， 但如果超过12，我们只是硬编码 12的最大可能距离。 否则所谓缓冲 溢出攻击可能发生。 在这些幻灯片的底部， 如果你好奇阅读更多 是真正的原创文章 如果你想看看。 但现在，其中的价格 在这里付出了效率低下。 所以这是一个快速 低水平看看什么 现在出现的问题，我们 有权访问的计算机的存储器中。 但另一个问题，我们 已经迷迷糊糊周一 这仅仅是低效率 的一个链表。 我们又回到了线性时间。 我们不再有一个连续的数组。 我们没有随机访问。 我们不能用方括号。 我们实际上不得不使用whil​​e循环 像我刚才写的。 但在周一，我们宣称我们能 悄悄放回效率的境界 实现东西是 对数也许，或者最好的是， 甚至东西是 所谓一定时间。 那么，如何才能做到这一点通过使用这些新的 工具，这些地址，这些指针， 和线程我们自己的东西呢？ 好吧，假设 在这里，这些都是一堆 我们要存储在数字 高效的数据结构和搜索。 我们完全可以后退到周 二，把这些放到一个数组， 并使用二进制搜索寻找他们。 分而治之。 而事实上，你写的 在PSET3二进制搜索， 在那里你实现find程序。 但是你知道吗。 还有一种更 这样做的聪明的方式。 这是一个有点多 成熟，它可能 让我们看到了为什么二进制 搜索是如此之快。 首先，我们来介绍 树的概念。 其中，即使在 样的现实树 成长就是这样，在计算机世界 学他们那种向下生长 就像一个家庭树，在这里你有 你的祖父母或曾祖父母 或者诸如此类的东西在上面，族长和 家族的女家长，只有一个 所谓根，节点，下面 这是它的孩子， 下面这是它的孩子，或 它的后代更普遍。 任何人都挂 家庭的底部 树，除了是 最年轻的家庭， 也可以只是一般 称为树的叶子。 因此，这只是一堆 词和定义 对于一些所谓电脑一棵树 科学，就像一个家庭树。 但是，还有票友变身 的树木，其中之一 被称为一个二分搜索树。 你可以种挑逗 除了这个东西做什么。 那么，它的二进制在什么意义？ 哪里二进制从何而来吗？ 对不起？ 这与其说是一个非此即彼的。 它更，每个节点具有无 两个以上的孩子，我们在这里看到。 在一般情况下，一个tree--和 你的父母和祖父母 可以有很多孩子或 孙子，因为他们真正想要的， 所以比如有，我们有三个 关闭该右手节点的孩子， 但在一个二叉树，一个节点具有 零个，一个或两个孩子最大限度。 这是一个很好的属性， 因为如果它的上限由二， 我们将能够 得到一点点的日志基地二期 行动回事大势所趋。 因此，我们有一些东西对数。 但是，更详细的介绍了一下。 搜索树指数是 布置成使得左孩子的 值大于根。 而它的右子是 比根大。 换句话说，如果你把所有的 节点，在这张照片中圈， 并期待在其左 儿童和其右孩子， 第一应小于， 第二应大于。 因此，合理性检查55。 它的左子是33。 它的不足。 55，其右孩子是77。 它是大于。 这是一个递归定义。 我们可以检查每个人的那些 节点和相同的图案将举行。 那么什么是不错的 二叉搜索树，是 这一块，我们可以实现它 有一个结构，就这样。 而且即使我们扔 很多结构在你的， 他们是有点 直观现在有希望。 语法仍然是神秘的肯定， 但一个节点在该内容 context--和我们保持 使用这个词的节点， 无论是一个矩形 屏幕或圆上， 它只是一些通用的容器， 在这种情况下，一棵树的，像一个 我们看到，我们需要一个整数。 在每个节点 然后我需要两个指点指点 到左子和右子， 分别。 所以这就是我们如何 实现在一个结构。 怎么可能我在代码中实现它？ 好吧，让我们快速浏览 看看这个小小的例子。 这不是功能，但我已经 复制并粘贴该结构。 如果我的函数的二进制 搜索树被称为搜索， 而这需要两个参数， 整数N和一个指针 到一个节点，以便一个指向树 或一个指向树的根， 我该如何去寻找N + 嗯，首先，因为我 处理球， 我会做一个全面的检查。 如果树等于等于空，是N 在这棵树还是没有这棵树？ 这是不可能的，对不对？ 如果我过去的空， 有什么也没有。 我干脆 一味地说，返回false。 如果你给我什么，我当然不能 找到任何数量N.那么还有什么可能我 现在检查？ 我会说好东西如果N 小于任何位于树节点 我一直在流传N值。 换句话说，如果数字我 寻找，N，小于节点 那我看。 和节点我期待 在被称为树， 和前面的例子召回 得到的价值指针， 我用的是箭头符号。 因此，如果N小于树箭头 N，我想概念去左边。 我如何搜索明示离开？ 需要明确的是，如果这是 图片中的问题， 我已经过了那个最上面 箭头指针下降。 这是我的树指针。 我指着树的根。 我期待说，对于 数44，随意。 比44少或 超过55显然更大？ 所以这是不到。 所以这一点，如果条件适用。 所以概念上，我该怎么想 搜索下一个，如果我在寻找44？ 是吗？ 没错，我想 搜索左子， 或该图象的左侧的子树。 而事实上，让我通过 图片到这里 就一下，因为 我也不会划伤了这一点。 如果我从这里开始在55，和 我知道，值44 我在寻找是 左边的，它是一种 像撕开电话簿 一半或撕裂树的一半。 我不再去在乎 这整个树的一半。 然而，奇怪的是在条款 结构，这件事情在这里 始于33，这本身 是二叉查找树。 我之前说的，因为这个词递归 的确这是一个数据结构，它 顾名思义就是递归。 你可能有一个树是这个 大，但它的每一个孩子 代表一棵树只是有点小。 而不是它是爷爷 或奶奶，现在它只是妈妈 or--我不能say--没有妈妈 或爸爸，那将是不可思议。 相反，两个孩子有 会像兄弟和姐妹。 新一代的家族树。 但在结构上，这是同样的想法。 而事实证明，我有一个函数 与我可以搜索二进制搜索 树。 这就是所谓的搜索。 我在树的箭头左边搜索对于N 否则，如果N大于该值 我目前在。 55中的故事刚才。 我有一个调用的函数 搜索，我可以只 通过N本和递归搜索 子树和刚刚回归 不管这个答案。 否则我这里有一些最后的基本情况。 是什么最终的情况？ 树为null。 我现在不是在寻找的价值 比小于它或更大 或等于它。 而且我可以说等于 相等，但在逻辑上是 相当于只是说人在这里。 所以，真正的是我找到的东西。 因此，希望这是一个 更引人注目的例子 比愚蠢的西格玛功能 我们做了一些讲课回来， 其中，使用循环是一样简单 计算了从一个所有的数字 为N.这里用的数据结构 这本身就是递归 定义和递归拉，现在我们 要表达自己的能力 在代码本身是递归的。 因此，这是这里的完全相同的代码。 所以，我们能解决什么其他的问题？ 因此，一个快人一步远离 树木只是一瞬间。 这里，说，德国国旗。 还有的显然是一个 模式这个标志。 而且还有很多的 在世界上的标志是 是这么简单的条件 它们的颜色和图案。 但是，假如这个存储为 .gif或JPEG格式，或位图或平， 任何图形文件格式 与你熟悉， 其中一些我们 在PSET4玩。 这似乎并不值得保存 黑色像素，黑色像素，黑像素， 点，点，点，一大堆 黑色像素的第一扫描线， 或行，然后一大堆 同样的，然后一大堆 的相同，然后一个 一大堆的红色像素， 红像素，红色像素，然后整体 一束黄色的像素，黄色的，对不对？ 有这样的效率在这里。 你将如何直观地 压缩德国国旗 如果其实现为一个文件？ 像什么信息能不 懒得为了存储在磁盘上 从喜欢减少我们的文件大小 一兆字节到千字节，东西 小？ 其中位于冗余 这里要清楚？ 你该怎么办？ 是吗？ 没错。 为什么不，而不是记住 每一次缝补像素的颜色 就像你做的PSET4 与位图文件格式， 你为什么不只是代表 像素的最左边的列，例如 一堆黑色像素，一串 红，和一堆黄色， 然后不知怎么竟编码 重复这个想法100倍 或者重复这个1000倍？ 其中100或者1000是 只是一个整数，所以你 可以逃脱只是一个单一的数字 而不是数百或数千 的追加像素。 事实上，这就是我们如何 可以压缩的德国国旗。 和 现在来谈谈法国国旗？ 还有一点某种 脑力锻炼，这标志 可以压缩更多的磁盘上？ 德国国旗或法国的 标志，如果我们采取这种做法？ 德国国旗，因为有 更水平的冗余。 而在设计上，许多图形文件 格式确实工作作为扫描线 水平。 他们可以工作 垂直，只是人类 决定多年前，我们会 一般认为事情排 由行，而不是逐列。 所以，事实上，如果你是 看文件 德国国旗和法国的大小 标志，只要分辨率 相同的，相同的宽度 和高度，这其中 这里将是更大，因为你 不得不重复自己的三倍。 你必须指定蓝色，重复 自己，白，重复自己，红色， 重复自己。 你不能只是全力以赴 的方式向右边。 和作为一旁，以使 清除压缩 无处不在，如果这些 从video--四个帧您 可能还记得，影片 或视频一般是 就像每秒29或30帧。 这就像一个小翻转书，你 只是看到图像，图像，图像，图像， 图像只是超级快，所以它看起来像 屏幕上的演员们动人。 这里有一个大黄蜂 一束花的顶部。 虽然它可能是一种 很难看到的第一眼， 唯一移动 这部电影是蜜蜂。 什么是愚蠢的有关存储 视频解压缩？ 这是一种浪费存储视频 四个几乎相同的图像， 不同仅仅是因为那里的蜂。 你可以扔掉最 该信息 只记得，例如， 第一帧和最后一帧， 如果你的关键帧 听说过这个词， 而只是存储在 中间那里的蜂。 而你也不必 存储所有的粉红色， 和蓝色，并在该 绿色价值观为好。 因此，这是只说 压缩是无处不在。 这是一个技术，我们经常使用 或者认为理所当然，这些天。 但是你如何压缩文本？ 你怎么去压缩的文本？ 那么，每一个人物的 ascii的是一个字节或八个比特。 这就是那种愚蠢的，对不对？ 因为你可能A型 而E和I和O和U很多 往往比像W或Q或Z， 根据所用的语言 你写的肯定。 所以我们为什么要使用 八位的每一个字母， 包括最不 流行的信，对不对？ 为什么不使用较少的位 超人气的信件， 像E，你猜的东西 首先在命运之轮， 并使用更多的比特用于 冷门信吗？ 为什么呢？ 因为我们只是要 使用这些较不频繁。 嗯，事实证明，有有 已经提出这样做​​的尝试。 如果你的等级召回 学校或高中，莫尔斯电码。 莫尔斯电码具有点 和破折号，可以 沿导线作为发送 声音或某种信号。 但摩尔斯电码是一个超级干净。 这是怎样的一个双星系统中 你必须点或破折号。 但是，如果你看到，例如，两个点。 或者，如果你想给操作 谁是这样嘟，嘟，嘟， 蜂鸣声，创下了小触发 该发送信号， 如果，接收方，接收两个 点，你有没有收到什么样的信息？ 完全是任意的。 一世？ 一世？ 还是什么about--还是我？ 也许这只是二号E的吧？ 因此，有这个问题 可解码与莫尔斯 代码，从而除非 人向您发送消息 实际上暂停，因此您可以排序的 看到或听到的字母之间的差距， 这是不够的只是 送的零和一的流， 或者点和线， 因为有歧义。 E是一个点，因此，如果您 看到两个点或听到两个点， 也许这两架E的或者它的One I. 因此，我们需要一个系统，是一个 小比这更聪明。 所以叫一个人霍夫曼年 前想出正是这一点。 因此，我们只是要 采取快速浏览 如何树是有密切关系这一点。 假设这是一些 要发送愚蠢的消息， 只是A，B组成，C的D'和E的， 但有很多冗余这里。 这并不意味着是英语。 这不是加密的。 这只是一个愚蠢的消息 有很多重复。 所以，如果你真的算出来的所有 A的，B公司，C公司，D的，和E的，这里的 频率。 字母的20％是 A的，字母的45％ 为E的，和其他三个频率。 我们人手点算在那里 而只是做数学。 所以，事实证明， 霍夫曼，前一段时间， 意识到这一点，你知道 什么，如果我开建 一棵树，或森林的树木，如果你愿意， 如下所示，我可以做以下。 我想给一个节点到每个 我关心的字母 我要去存储 该节点的内 频率作为一个浮点 值，或者你可以使用它的N，也 但是我们只用一个浮点数在这里。 而算法 他提出的是你 借此森林单个节点 树木，所以超短树， 你开始与连接它们 新的群体，新的父母，如果你愿意。 而你做到这一点，选择 两个最小频率的时间。 于是，我花了10％和10％。 我创建了一个新的节点。 而我所说的新节点20％。 这两个节点结合我下？ 这是一个有点暧昧。 因此，有一些角落情况下 考虑，而是让事情变得漂亮， 我会选择20％ - 我现在忽略了孩子。 我会选择20％ 15％和绘制两条新边。 而现在这两个节点 我逻辑组合？ 忽略所有的孩子，所有的 孙子，只看根 现在。 这两个节点我绑在一起？ 第二点和0.35。 因此，让我得出两个新的边缘。 然后，我只有一个了。 因此，这里的一棵树。 而且它被画刻意 看那种漂亮， 但是请注意，边缘有 也被贴上零和一。 因此，所有的左边缘都为零 随意，但始终。 所有的右侧边缘的那些。 还等什么霍夫曼提出， 如果要表示B， 而不是表示数字66作为 一个ascii其长度为八个整位， 你知道吗，刚刚店 图案零，零，零， 零，因为这是路径 从我的树，霍夫曼先生的树， 从根叶。 如果你想存储 E，相比之下，不 发送代表E.八位 相反，派位的是什么模式？ 一。 什么是好的关于这 E是最流行的字母， 而你正在使用的 最短的代码吧。 接下来最流行 信看起来 是A.所以，有多少位 他才建议用是什么？ 零点一。 而且因为它的实现 因为这棵树，现在 让我规定有 无歧义的莫尔斯 码，因为所有的 你关心的信 是在这些边缘的末端。 所以，这只是一个 应用一棵树。 这is--我会波 我的手在这你如何 有可能实现这是一个C结构。 我们只需要结合 一个符号，就像一个char， 和在频率左右。 但是，让我们看两个 最后的例子，你会 得到相当熟悉后， 测验零习题集五位。 因此，有该数据结构 称为哈希表。 而一个哈希表是怎么样的 冷却在于它具有水桶。 假设有四个桶 在这里，只有四个空格。 下面是一副扑克牌，并在这里被 俱乐部，铁锹，俱乐部，钻石，俱乐部， 钻石，俱乐部，钻石， clubs--所以这是随机的。 心，hearts--所以我 bucketizing所有输入这里。 而一个哈希表的需求 看你的输入​​， 然后把它放在一个特定的 基于你所看到的地方。 这是一个算法。 而我使用的是超 简单的视觉算法。 其中最困难的部分是 记住哪些图片是。 再有就是总共四个东西。 现在堆栈的长势，这 是故意设计的东西在这里。 还有什么我可以做什么？ 所以实际上我们在这里有一个 一群老同学考试用书。 假设一堆 学生的名字都在这里。 这里有一个更大的哈希表。 而不是四个桶， 我有，比方说26。 我们不想去借钱26 从外面[事情？安嫩伯格？]，所以 这里共有五次代表 A到Z.如果我 看到学生的名称以A， 我打算把他或她的测验那里。 如果有人以C开头，在那里， A--实际上，并不想这样做。 B进入到这里。 所以，我有A和B和C和 现在这里的另一个学生。 但是，如果这个散列表是 以与阵列实现， 我有点拧 在这一点上，对不对？ 那种我需要把这个地方。 因此，我可以解决这个问题的一个方法是，所有的 没错，A占线，B忙，C忙。 我打算把他D.因此，在 首先，我有随机即时访问 每个桶的学生。 但是，现在这是一种下放 弄成线性的， 因为如果我要寻找的人 其名称开头，我点击这里。 但如果不是这种甲 学生，我正在寻找， 那种我要开始检查 水桶，因为我做了什么 是那种线性 探测数据结构。 一个说笨方法只是看 第一个可用的开放， 并把作为一个B计划，可以这么说， 或者在这种情况下的计划D，则值 在该位置代替。 这仅仅是这样，如果你已经 有26个地点，并没有学生 名为Q或Z或喜欢的事 即，至少你正在使用的空间。 但是，我们已经看到了更多的 聪明的解决方案，在这里，对不对？ 你会怎么做，而不是 如果你有一个碰撞？ 如果两个人有 该名称的，会是什么 是一个更聪明或更 直观的解决方案不仅仅是 把一个其中D应该是？ 为什么不让我走 外[？安嫩伯格？] 喜欢的malloc，另一个节点，把它 在这里，然后把这里的学生。 所以，我基本上是有 一些类型的数组，， 或者更优雅的，因为我们是 开始看到一个链表。 因此一个哈希表的结构 这可能看起来就像这样， 但更聪明，你的东西被称为 分离链，从而哈希表 很简单，是一个数组，每个 其元素不是数字， 本身是一个链表。 使您获得超快速访问 决定在哪里你的价值散列到。 就像用卡的例子， 我做了超级快速决策。 心放在这里，钻石放在这里。 同样在这里，一个放在这里， ð放在这里，B放在这里。 因此，超快速的查找窗口，如果 你碰巧遇到一个案例 在这里你有碰撞，二 人具有相同的名称，以及再 你刚开始把它们连接起来。 也许你让他们排序 按字母顺序，也许你不知道。 但至少现在我们有活力。 因此，一方面，我们有超级快 固定的时间和形式的线性时间 如果这些链表参与 开始变得有点长。 因此，这种愚蠢的， 令人讨厌的笑话年前。 在CS50黑客马拉松， 当学生入住， 一些TF或CA每年 认为这是有趣忍受 像这样的一个标志，它只是 也就是说，如果你的名字开始与A， 走这条路。 如果你的名字开始 用A，B，去this-- OK， 这很有趣，也许在以后的学期。 但是，还有一个 这样，太的方式。 回过头来的。 因此，有这种结构。 这是我们最后一次 结构的今天， 这是一些所谓的线索。 T-R-I-E，这对于某些原因是短 检索，但它被称为线索。 因此，一个线索是另一个有趣 汞合金很多这样的想法。 这是一棵树，这是我们以前见过。 这不是一个二叉搜索树。 这是一个树的任何数量的孩子， 但每一个线索的孩子 是一个数组。 大小的数组，说，26或者27 如果你想支持复姓名字 还是在人的名字撇号。 所以这是一个数据结构。 而如果你从上 到底，就像如果你 顶一下节点有，男，是 指向左边的事情存在， 然后将其A，X，W，E，L，L。这是 只是一种数据结构，任意地 是存储人的名字。 和麦克斯韦是刚刚以下存储 数组的数组阵列的路径。 但令人惊讶的有关线索是 如此，而一个链表，甚至 一个数组，我们曾经得到的最好的是 线性时间或对数时间寻找 有人了。 在一个线索的此数据结构中，如果 我的数据结构中有一个名字 而我在寻找麦克斯韦，我 要找到他很快。 我只是寻找M-A-X-W-E-L-L。是否 此数据结构中，通过对比， 如果N是一百万，如果有一个 在这种数据结构万个名字， 麦克斯韦仍然将是 发现刚刚M-A-X-W-E-L-L后 脚步。 而David-- D-A-V-I-D的步骤。 换句话说，通过建立 一种数据结构，是 得到了所有这些阵列的，所有这些都 本身支持随机访问， 我可以开始寻找达人的 使用的时候这是一个量的名字 成比例的数量不限 的东西，在数据结构中， 像一百万现有名称。 花费的时间我找的金额 的M-A-X-W-E-L-L的这种数据结构是 比例不到 的数据结构的大小， 但对名称的长度。 而现实的 名字我们仰视 永远不会长疯了。 也许有人有10个字符 名，20个字符的名称。 这当然是有限的，对不对？ 有地球上的人谁 有最长可能的名称， 但这个名字是一个常数 值长，对不对？ 它并不在任何意义上有所不同。 因此，在这种方式中，我们 实现了数据结构 这是恒定的时间查找。 它采取了一些措施 根据输入的长度， 的名字，但没有数量 在数据结构中。 因此，如果我们加倍名的数量 从十亿一二十亿明年， 发现麦克斯韦是要采取 的七个步骤完全相同的数 找到他。 因此，我们似乎已经达到 我们神圣的运行时间的法宝。 因此，一对夫妇的快速公告。 测验零快到了。 更多的是在球场上的网站 在接下来的几天。 周一的lecture--这是一个节日 你们是哈佛在星期一。 这不是在纽黑文， 所以我们采取了类 纽黑文的演讲在星期一。 一切都将被拍摄下来， 和流现场像往常一样， 但让今天的结束 用30秒的剪辑 所谓的“深度思考” 通过Daven法纳姆，这 在周六的启发，去年 夜直播的“深度思考” 杰克得心应手，这 现在应该是有意义的。 电影：现在，“深 思考“由Daven法纳姆。 哈希表。 扬声器1：好吧，这就是它了。 我们会看到你下周。 道格：要看到它在行动。 所以，让我们来看看这个现在。 所以在这里，我们有一个排序的数组。 IAN：道格，你能继续前进，重新启动 这只是一秒，请。 好吧，相机滚动，所以 的动作，当你准备好，道格，好不好？ 道格：好的，所以我们 这里是一个未排序的数组。 我也有色的所有元素 红色，以表明它是，事实上， 未分类。 所以记得的第一件事情，我们做的 是我们排序阵列的左半。 然后我们排序的权利 一半的阵列。 雅达，雅，达，雅，达， 我们把它们合并起来。 我们有一个完全排序的数组。 所以这是如何归并排序工作。 IAN：哇，哇，哇， 切，切，切，切。 道格，你不能随便亚达，雅，达， 雅-DA，通过归并排序的方式。 道格：我只是做了。 没关系。 我们是好去。 我们只是不停地滚动。 所以无论如何， 伊恩：你有解释 它比更充分。 这只是还不够。 道格：伊恩，我们不 需要回去之一。 没关系。 所以无论如何，如果我们继续merge-- 伊恩，我们在拍戏的中间。 伊恩：我知道。 我们不能只是亚达，雅，达， 雅-DA，通过全过程。 你必须解释为什么 双方得到合并在一起。 道格：但我们已经 解释了两个sides-- 伊恩：你刚才表示 他们合并数组。 道格：他们知道这个过程。 他们是很好。 我们已经讨论了10次， 伊恩：你刚才跳过权权。 我们要回一个，你 不能你丫达，雅，达权。 好了，回到之一。 道格：我要回去 通过所有的幻灯片？ 我的上帝。 这就像第六次，伊恩。 没关系。 伊恩：好的。 你准备好了吗？ 太好了。 动作。