[音乐播放] ANDI鹏：欢迎来到第6个星期 我们从标准的偏离 周二部分时间 下午这个可爱的星期天早晨。 谢谢大家了 加入我的今天，但严重的是， 掌声雷动。 这是一个相当大的努力。 我几乎没有，甚至使它 在时间，但它是确定。 所以，我知道所有的你， 刚刚去到测验。 首先，欢迎 另一面的那个。 其次，我们会谈论它。 我们将讨论的测验。 我们将谈论如何 你正在做的类。 你会没事的。 我有你的测验为 你在这里结束， 所以如果你们想带 看看吧，完全罚款。 所以很快我们开始的前 今天的议程如下。 正如你所看到的，我们是 基本上速射 通过一大堆数据结构 真的，真的，真的很快。 如此，因此，它不会被 超级互动的今天。 这将只是我的一种喊 事情是你，如果我迷惑你， 如果我走得太快，让我知道。 他们只是各种数据 结构，并作为部分 您pset获取如此 即将到来的一周，你会 被要求执行其中的一个， 两人或许them--他们两个 在你的pset中。 好了，我只是要 开始与一些公告。 我们一起去了栈和队列的更多的 深度比我们的测验以前那样。 我们一起去了挂 再次，再次列出， 更深入的比 我们在测验前了。 然后我们来谈谈哈希 表，树和尝试，这 都是很必要的PSET。 然后我们将介绍一些 有用的技巧pset5。 好了，测验0。 平均为58％。 这是非常低的，所以你们所有 按照表现非常，非常好 接着就，随即。 好看多了，经验法则是，如果你是 内的平均值的标准偏差 特别是因为我们正处在一个较小 舒适的部分，你完全罚款。 你的轨道上。 生活很好。 我知道它的可怕认为 我喜欢这个测验40％。 我要失败，这个类。 我答应你，你不 要失败的类。 你完全罚款。 对于那些你们谁得到了 平均，令人印象深刻的，令人印象深刻， 像，认真做得很好。 我让他们和我在一起。 随时来让他们 在段的末端。 我们如果您有任何我知道， 问题，与他们的问题。 如果我们增加了你的分数 错了，让我们知道。 好了，pset5，这是一个非常 奇怪的一周耶鲁大学的意义 我们的PSET是由于 周三中午，包括 晚一天，所以它实际上 在周二中午理论上所致。 大概没有人完成 在周二中午。 这是完全正常。 我们将有办公时间 今晚以及周一晚上。 和所有的部分将于本周 实际上变成车间， 您可以随意弹出的 你想要的任何部分， 他们会是怎样的迷你PSET 讲习班上的帮助。 因此，作为这样的，这是唯一的部 在这里我们教材。 所有其他部分将集中 专门对pset的帮助。 是吗？ 听众：在哪里上班时间？ ANDI彭：办公时间 tonight--哦，很好的问题。 我想今晚办公时间 在蒂尔或共享。 如果你在网上查询CS50 你去办公时间， 应该有一个时间表 告诉您所有的人都。 我知道，无论是今晚 或者明天是水鸭， 我想我们可以有 公地的晚上。 我不确定。 好问题。 检查CS50。 酷，任何有关的问题 计划在未来像三个日子吗？ 我保证你们喜欢大卫 说，这是在山顶上。 你们是几乎没有。 仅仅三天。 到达那里，然后我们都来了。 我们将有一个很好的CS-免费休息。 欢迎回来。 我们将深入到网络 编程与开发， 事情是非常有趣的对比 一些其他的pset的。 而这将是凄凉， 我们有很多的乐趣。 我们将有更多的糖果。 对不起，糖果。 我忘了糖果。 这是一个粗糙的早晨。 所以，你们是几乎没有， 而且我非常自豪的你们的。 好了，栈。 谁爱杰克的问题 和他的衣服上的测验？ 没人？ 好吧。 所以基本上，你可以 图片杰克，这个家伙在这里， 喜欢拿衣服 出栈的顶部， 他把它放回 之后，他在堆栈的完成。 因此以这种方式，他从未 似乎越来越 到的底部 堆在他的衣服。 所以，这样的描述 基本的数据结构 一个堆栈是如何实现的。 从本质上讲，想想 协议栈的任何栈对象 你把东西到顶部， 那么你从顶部弹出出来。 因此，后进先出法是我们喜欢的缩写 以use--后进先出。 所以，最后到的顶部 栈是第一个出来。 这样一来，两个词 我们喜欢联想 与被称为push和pop。 当你把一些东西到 堆栈和你的流行回来了。 所以我想这是种 抽象的概念，对于那些你 谁希望看到像 这实际执行 在现实世界中。 你们有多少人写了一篇文章， 也许就像一个小时之前，这是由于， 你不小心删除了一个巨大的 大块的它，就像不小心？ 然后呢控制做 我们用它来把它放回去？ 控制-Z，是吗？ 控制-Z，所以倍量 控制-Z已经救了我的命， 救了我的屁股，每次 该真实通过烟囱实现。 基本上所有的信息 这是您的Word文档， 它被压入和弹出的意愿。 所以基本上每当你 删除任何东西，你的流行回来了。 然后，如果你需要它回来，你 推，这是控制-C一样。 所以，现实世界中的功能 多么简单的数据结构 可以帮助你的日常生活。 因此，一个结构的方式， 我们实际上创建一个堆。 我们定义类型结构，然后 我们把它在底部堆。 和栈内， 我们有两个参数 我们基本上可以操纵， 所以我们有字符的字符串星能力。 所有这一切是做 正在创建一个数组 我们可以存储任何你想要的 我们可以判断其能力。 能力是刚刚最大金额 项目我们可以把这个数组。 INT大小是保持计数器 跟踪有多少项目是目前 在栈。 所以后来我们就可以跟踪，A， 无论有多大的实际堆栈， 和，B多少该堆栈的 我们充满因为我们不希望 溢出超过了我们的能力。 因此，例如，这个可爱的 问题是你的测验。 从本质上讲，我们如何推动 到堆栈的顶部。 很简单。 如果你看看吧， 我们将穿行于此。 如果[听不清] size-- 请记住，当你 要访问任何 一个结构内的参数， 你做struct.parameter的名称。 在这种情况下，s是 我们的叠层的名称。 我们要访问的大小 这一点，所以我们做s.size。 所以只要尺寸不 等于能力，长 因为它是低于产能， 要么就在这里工作。 你想访问内 你的筹码，所以s.strings， 你打算把新号码 要插入到那里。 远的不说，我们将要 插入INTñ压入堆栈， 我们可以做s.strings， 括号，s.size等于ñ。 由于尺寸是我们 当前有在堆栈 如果我们要推动 它，我们刚刚访问 无论大小，则 叠层的当前饱胀， 我们推INTñ到它。 然后我们要确保 我们也递增了n个大小， 所以我们可以跟踪我们已经 增加了一个额外的东西到堆栈中。 现在我们有一个更大的尺寸。 这是否在这里是有意义的 大家，如何在逻辑上是否可行？ 这是一种快捷。 听众：你可以走了 在s.stringss.strings [s.size]了吗？ ANDI彭：当然，有什么呢 s.size目前给我们？ 听众：这是当前大小。 ANDI鹏：没错，所以 目前的指数，我们的规模是， 所以我们希望把新的整数 我们要插入s.size。 那有意义吗？ 因为s.strings，所有的 是是阵列的名称。 所有这是访问 我们的结构内的数组， 因此，如果我们想 将正成指数， 我们可以只访问 使用括号s.size。 凉。 好吧，流行，我伪出来 为你们这些家伙，但类似的概念。 那有意义吗？ 如果尺寸大于 大于零，则 知道你想要拿东西 出，因为如果尺寸不 大于零，则 有没有在堆栈中。 所以，你只需要执行 这段代码，它只能 弹出如果有什么流行。 所以如果尺寸更大 大于0，我们减去大小。 我们减小大小，然后返回 无论是内部的，因为 通过弹出，我们要 无论是存储的访问 在堆栈的顶部的索引。 一切有意义吗？ 如果我让你们写了这一点， 将你们能写出来？ OK，你们可以玩它。 不用担心，如果你不明白这一点。 我们没有时间去编写 它今天因为我们 得到了很多这些结构 穿过去，但本质 伪代码，非常，非常相似推。 只要跟着逻辑。 请确保你所访问的所有 你的结构功能正常。 是吗？ 听众：请问这些幻灯片和 这整个事情高达今天十岁上下的？ ANDI彭：始终，是的。 我会尽量把 这像一个小时后。 我会通过电子邮件大卫，大卫将尝试 把它像在此之后一个小时。 好了，接下来我们进入这个其他 可爱的数据结构称为队列。 正如你们所看到的，一 队列，对于我们中间英国， 所有这是一条线。 那么相反的是 你觉得一个堆栈， 队列是什么 在逻辑上，你认为它是。 它保持由FIFO的规则， 这是先入先出。 如果你是第一个 一个在行，你 第一个 出来的线。 所以，我们喜欢把这种 在出队，并排入队列。 如果我们想要添加的东西 我们的队列中，我们入队。 如果我们要离队，或采取 一些东西，我们出队。 因此，同样的道理，我们是那种 创建固定大小的元素，我们 可以存储一定的 的事情，但是我们也可以 改变我们正在把 他们的内部参数 基于什么类型 功能我们想要的。 所以栈，我们希望最后 酮，N是第一个出来。 排队是我们要的第一件事情 在成为第一件事出去。 因此，结构型 定义，你可以看到， 这是一个有点不同 从什么堆栈是 因为我们不仅要保持 轨道的其中该尺寸是目前， 我们也想跟踪头 以及我们当前有。 所以我觉得它更容易 如果我画这件事。 因此，让我们想象一下，我们已经有了一个队列， 所以我们说，头就在这里。 该行的负责人，让我们 只是说这是目前在那里， 我们要插入 事到队列。 我要去基本上调用大小 是同样的事情，尾， 哪里的队列的末尾。 远的不说大小就在这里。 那么，如何切实 东西插入到队列中？ 什么样的指标，我们要放置 在这里我们要插入。 如果这是开头的 排队，这是它的结束 或者它的大小，我们在哪里 要添加的下一个对象？ 听众：[听不清] ANDI鹏：没错，你想添加 它取决于你写的。 这要么是空白，或为空。 所以，你想可能添加 在这里，因为如果大小is-- 如果这些都满了，你想 将其添加在这里，对不对？ 所以这就是，虽然非常非常 简单，不太总是正确的 因为主要的区别 队列和堆之间 是，队列可以 实际上被操纵 使头部的变化 这取决于你想上哪儿 您的线索年初启动。 其结果，你的尾巴 也不会改变。 所以看看 此代码现在。 正如你们也被要求 写出来的测验，入队。 也许我们会聊过为什么 答案是什么。 在一个我不太适合这一行， 但本质上这一段代码 应该是在一行上。 花想30秒。 看看，看看为什么 这是，它是这样的。 非常，非常相似的结构，非常，非常 类似的结构与前面 堆叠除了可能 一行代码。 而这一行代码 确定的功能。 它真的与众不同 从一摞一个队列。 任何人想采取刺 在解释为什么你 拿到这里这个复杂的事情？ 我们看到的回报我们 美妙的朋友模量。 正如你们很快就会到来 在编程认识到， 几乎任何时候，你需要的东西 环绕什么， 模将是这样做的方式。 因此，了解的是，没有人想 尝试解释该行代码？ 是的，所有的答案都 接受和欢迎。 听众：你是在跟我说话？ ANDI彭：是的。 听众：哦，不后悔。 ANDI彭：好，让我们 穿行此代码。 所以，当你想 添加的东西到一个队列， 在可爱的情况下头部发生 是在这里，这很容易让我们 刚走到最后 插入的东西，对不对？ 但是队列的整点 头部实际上可以动态地 不同的地方改变我们 希望我们的Q的开始是， 正因为如此，在尾 也不会改变。 所以，想象一下，这是不是 排队，而是这是队列。 比方说，头就在这里。 比方说，我们的队列看上去像这样。 如果我们想转向哪里 该行的开始是， 假设我们转向头 这种方式和尺寸在这里。 现在我们要添加一些 此队列，但你们可以看到， 它不是那么简单，只是 添加任何的尺寸后， 因为那样的话，我们用完 我们的实际数组的边界。 当我们要真正增加在这里。 这是一个队列的美 是我们的，视觉上 看起来像行是这样的， 但是，当存储在数据结构中， 他们给它像一个循环。 它种环绕 到前以同样的方式 该行也可以换 各地根据地方你 希望该行的开头是。 因此，如果我们拿 往下看这里，让我们 说我们想创造一个 函数调用排队。 我们希望加INT n为进的Q值。 如果q.size q--我们会打电话给我们的数据 结构 - 如果我们的queue.size不 等于能力，或者 这是不到容量， q.strings是我们q内的阵列。 我们要设置 这等于q.heads， 这是在这里，再加上q.size 模量由容量，这 包裹我们回在这里。 所以在这个例子中，索引 头是1，对吧？ 大小的指数为0，1，2，3，4。 因此，我们可以做到1加4模 我们的产能是5。 是什么给我们？ 什么是索引 这样来的？ 听众：0。 ANDI彭：0， 恰好就在这里， 所以我们希望能够 插入到这里。 所以这个公式在这里种 仅适用于任何数字 不同的地方你 头部和你的尺寸是。 如果你知道这些 事情是，你知道 正是您要插入 您的队列后，无论是。 这是否有意义给大家？ 我知道怎样的一个大脑 传情特别是因为这 排在你竞猜的善后工作。 但希望大家 现在可以理解 为什么这个解决方案或本 功能是，它是这样的。 任何人都有点不清楚的是什么？ 好。 所以现在，如果你 要离队，这 是我们的头会转向 因为如果我们要出列， 我们不取下q的末端。 我们要起飞的头，对不对？ 因此，作为结果，磁头会改变， 这就是为什么当你入队， 你必须保持跟踪 在这里你的头，你的尺寸 是能够插入 到正确的位置。 所以，当你出列， 我还伪出来。 随意，如果你想 尝试编码了这一点。 要移动头部，对不对？ 如果我想离队，我 将移动头以上。 这将是头部。 而我们目前的规模会 减去因为我们不再 在阵列中四个元素。 我们只有三个，然后我们要 返回不管里面储存 头部，因为我们希望借此 值出所以非常相似的栈。 只要你参加 来自不同的地方， 你必须重新分配指针 不同的地方作为一个结果。 从逻辑上讲，每个人都遵循？ 大。 好了，我们要商量了一下 更深入的了解链表 因为他们将是非常，非常有价值 您在本周的过程 pset中。 链表，因为你们 能记住，一切又都 是有一定的节点节点 两者的值和一个指针值 连接在一起的 通过这些指针。 因此如何在结构 我们在这里创建一个节点，我们 是int n，这个是什么 在商店或字符串值n 或者任何你想 调用它，焦炭星ñ。 结构节点星，这是指针 要在每个节点上， 你将有 对下一个指针点。 你得头 链表那 要指出的其余部分 等等，等等的值 直到你最终到达终点。 而这最后一个节点仅仅是 要没有一个指针。 这将指向 空，这就是当 你知道你已经打了 您的链接列表的末尾 就是当你的最后一个指针 不指向任何东西。 因此，我们要去多一点的 关于深入怎么一会可能 搜索一个链表。 记住是一些 该链表的缺点 诗句关于搜索的阵列。 数组可以二进制搜索，但 你为什么不能做，在一个链表？ 听众：因为他们都是互相联系在一起， 但你不太知道在哪里 [听不清]。 ANDI彭：是的，正是这样记 一个数组的辉煌 是事实，我们有 随机存取存储器，其中 如果我想从指数值 六，我可以说，指数六， 给我的价值。 那是因为数组排序 在一个连续的内存空间 在一个地方，而 一种链表 是随机散布各地， 而只有这样，你可以找到一个 是通过指针，告诉你 的，其中该下一个节点是地址。 所以作为结果，只有这样 通过一个链接列表来搜索 是线性搜索。 因为我完全不知道在哪里 在该链接的表的第12值是， 我必须遍历全部 那链接列表中的一个 由一个从头部到第一节点， 到第二个节点，到第三节点， 一路下来，直到我终于搞定 到这个节点，我要找的是。 因此在这个意义上说，搜索 上链表总是n。 它总是ñ。 它总是以线性时间。 这样一来，代码中 我们实现这一点，而这 有点新的你们，因为你们 人还没有真正谈过或曾经 在如何看到指针 通过搜索指针， 因此，我们将演练 这个非常，非常缓慢。 所以布尔检索，权， 让我们想象一下，我们希望 创建一个名为函数 搜索返回true 如果您发现里面的链接的价值 列表，并将否则返回false。 节点明星名单 目前只是指针 在你的链接列表中的第一项。 INT N是你的价值 搜寻在该列表中。 因此，节点星指针等于名单。 这意味着我们正在设置 和创建的指针 到列表的内部该第一个节点。 每个人都和我在一起？ 因此，如果我们当中去 回到这里，我会 初始化指针指向 无论头部的名单。 然后，一旦你到这里， 同时指针不等于空， 所以这是我们在其中循环 将要随后遍历 我们因为什么列表的其余部分 发生在指针等于null？ 我们知道，我们have-- 听众：[听不清] ANDI鹏：没错，所以我们知道， 我们已经达到列表的末尾，对不对？ 如果你回到这里，每个节点 应指向另一节点 等等等等 直到你打最后 您链表的尾部， 它具有一个指针，只是 不点不是没有其他任何地方。 所以你基本上知道 你的名单仍然有上升 直到指针不等于 null，因为一旦它等于空， 你知道，有没有更多的东西。 所以这是循环，其中我们 将有实际的搜索。 而如果pointer--你看 那种箭功能那里？ 因此，如果指针指向为n，如果 在n等于等于n个指针， 因此，这意味着，如果 你是指针 在每个结束搜索 节点实际上等于值 你要找的话 要返回true。 所以基本上，如果你在一个节点 有你正在寻找的价值， 你知道你已经 能够成功地搜索。 否则，你要设置 指针到下一个节点。 这就是这条线在这里做。 指针等于下一个指针。 每个人都看到了的工作？ 而且基本上你要只 遍历列表的全部， 重置每一次，直到你的指针 你最终击中列表的末尾。 你知道有没有 更多的节点进行搜索， 然后你就可以返回false 因为你知道，哦，好吧， 如果我已经能够搜索 通过列表的全部。 如果在这个例子中，如果我想 寻找值10， 我开始在头， 我搜索一路下跌， 而我最终得到了这一点，这 一个指针指向空， 我知道，废话，我想10不 这个名单是因为我找不到它。 而我在列表的末尾。 而在这种情况下，你知道 我将返回false。 让那浸泡在一点点。 这将是非常 重要的是你的pset中。 它的逻辑很简单，也许 语法只是实现它。 你们想使 确保你理解。 凉。 好了，我们怎么会 插入节点，右， 到列表中，因为记住 是什么的有什么好处， 具有的链接列表与 在存储方面的阵列？ 听众：这是动态的， 所以它更容易用于： ANDI鹏：没错， 所以它是动态的， 意味着它可以扩大和缩小 取决于用户的需要。 因此，在这个意义上，我们并不需要 浪费不必要的内存，因为我 如果我不知道有多少值要 存储，它没有任何意义，我 创建因为数组 如果我想存储10个值 我创建的1000阵列，这是 大量浪费的内存，配发。 这就是为什么我们要使用一个链接 列表能够动态 改变或缩小我们的规模。 而这样就使得插入 有点复杂。 既然我们不能随意访问元素 将我们的数组的方式。 如果我想插入元素 进入第七个指标， 我只是将它插入 进入第七个指标。 上一个链表，它不 很容易地工作， 所以如果我们想插入 这里一个在该链接的表， 在视觉上，它很容易看到。 我们只是希望将其插入那里， 就在列表的开头， 后头部右侧。 但在其中，我们有方式重新分配 指针是不是有点绕口 或者，从逻辑上讲，这是有道理的，但 你要确保你拥有了它 完全下来，因为 你想的最后一件事 是重新分配的指针的 我们在这里做的方式。 如果取消引用 从头指针为1， 然后突然的的 您的链接列表的其余部分 是丢失，因为你还没有真正 创建的临时任何东西。 这是指着2。 如果重新分配的指针，那么 列表的其余部分完全丧失。 所以，你想成为 非常非常小心这里 先分配 无论从任何你指针 要插入到哪里 你想，然后你 可以取消引用列表的其余部分。 因此，这适用于任何地方 你想插入。 如果要插入的 头，如果你想在这里回答， 如果要插入的 最后，好了，我到底 猜你只想 有没有指针，但你 要确保你不 失去你的列表的其余部分。 你总是要确保 你的新节点指向 对任何你 要插入， 然后您可以添加链接上。 大家都清楚了吗？ 这将是 一个真正的问题。 其中一个最重要的问题 你要对你的pset 是，你要尝试创建 链表和插入件事情 但当时只是失去了 剩下的链表中。 而你要像我 不知道为什么会这样？ 而且这是一个痛苦的经历 并搜索所有的指针。 我保证你在这pset中， 书写和绘画这些节点出 将是非常，非常有帮助。 所以，你可以完全跟踪 在那里所有的指针， 什么错， 您所有的节点， 你需要做的访问或 插入或删除，或任何人。 每个人都好有吗？ 凉。 因此，如果我们想看看代码？ 哦，我不知道，如果我们 可以看到the--好了， 顶部所有它是一个功能 在这里我们要命名插入 插入INT n为进链表。 我们将穿行于此。 这是一个很大的代码，有很多新的语法。 我们会没事的。 所以在顶部，每当 我们要创建什么 什么我们需要做的，特别是如果你 希望它不被存储在栈上 但在堆？ 我们去的malloc，对不对？ 因此，我们要创建一个指针。 节点，指针，新的平等 MALLOC一个节点的大小 因为我们要创建的节点。 我们想要的量 内存节点占用 将予配发的 创建新的节点。 然后我们要去检查 查看是否有新的equals等于空。 还记得我们说什么？ 不管你的malloc， 要做就要你总是做什么？ 你必须经常检查，看看 无论是否是空。 例如，如果你的工作 系统完全​​满， 如果你在没有更多的内存 所有你尝试的malloc， 它会返回null为您服务。 所以，如果你尝试使用它 当它指向空， 你不打算能 来访问该信息。 所以，正因为如此，我们希望使 相信只要你mallocing， 你总是检查，如果看到 给你的内存为空。 如果不是，那么我们可以将 与我们的代码的其余部分。 所以，我们要 初始化新节点。 我们要做新的n等于ñ。 然后我们要做的 设置新的新指针 为null，因为现在我们不这样做 想要的任何东西它指向。 我们不知道在哪里 它会放你， 然后，如果我们想 在头部插入， 那么我们就可以重新分配 指针的头部。 每个人都遵循的逻辑 在那里发生的事情？ 我们所要做的是创建一个新的 节点，设置指针为空， 然后重新分配 它的头部，如果我们 知道我们要在头部，将其插入。 然后将头是要 指向新的节点。 每个人都与该行吗？ 所以这是一个两步过程。 你必须先分配 无论你正在创建。 设置指针到 引用，然后你 能种非关联化 第一个指针 并指出其向新的节点。 不管你想要去插入， 该逻辑要成立。 这有点像分配 临时变量。 请记住，你已经有了 确保你 不要失去跟踪，如果你换了。 你要确保你有一个 那种保持临时变量 轨道，其中那些事儿 存储，让你 不丢失任何价值的过程 像瞎搞吧。 OK，这样的代码将出现在这里。 你们采取部分后的样子。 它会在那里。 所以我想如何做 这种差异，如果我们想要 插入到中间或结束？ 有没有人有什么想法 伪代码作为逻辑参照 我们将采取如果我们想要 将其插入中间？ 因此，如果我们想在将其插入 头，我们所要做的就是创建一个新的节点。 我们设定的指针 新节点的任何头部， 然后我们设置了头 新的节点，对不对？ 如果我们想将其插入到中间 名单，你会我们有什么关系？ 听众：它仍然 是类似的过程 像分配指针 然后，指派该指针， 但我们必须找到那里。 ANDI鹏：没错，所以完全 但你同样的过程 必须找到在什么地方你 希望该新指针进入， 所以如果我要插入到 中间的链接列表中 - 确定， 让我们说这是我们的链表。 如果我们想，就在这里插， 我们要创建一个新的节点。 我们要去的malloc。 我们要创建一个新的节点。 我们将分配 指针在这里这个节点。 但问题是不同 从其中头部是 是，我们确切地知道 其中头。 这是正确的，在第一次，对吗？ 但在这里，我们一定要保持跟踪 在那里我们将其插入。 如果我们插入我们 在此节点，我们有 以确保该 一个先前到该节点 是一个重新分配的指针。 所以，那么你必须种 跟踪两件事情。 如果你跟踪，其中这 节点当前的插入。 您还可以跟踪在哪里 那你看前面的节点 也有。 每个人都好有吗？ 好。 如何插入结束了吗？ 如果我想将其添加这里 - 如果我想 到一个新的节点添加到列表的末尾， 怎么可能我去这样做？ 听众：那么目前， 最后一个人指着空。 ANDI彭：是的。 没错，所以这一块 目前指向知道， 所以我想，在这个意义上，它是 很容易添加到列表的末尾。 所有你需要做的是设置 等于空，然后繁荣。 就在那里，很容易。 很简单。 非常相似的 头，但在逻辑上你 想确保该步骤 你迈出做任何的这个， 您关注的沿。 这是很容易的，在中间 你的代码，陷入上， 哦，我有这么多的三分球。 我不知道在哪里 任何指向。 我甚至不知道我在哪个节点。 这是怎么回事？ 放松，平静下来，深呼吸。 绘制出你的链接列表。 如果你说，我知道在什么地方 我需要插入到这 我知道如何重新分配我 指针，多，更容易图片 out--多，更容易不 迷失在你的代码的漏洞。 每个人都与该行吗？ 好。 所以我想一个概念，我们还没有 真之前谈到现在， 我猜你可能 不会遇到太大yet-- 它是一种先进的concept-- 是，我们其实有一个数据 结构，称为一个双向链表。 所以当你们看到的， 所有我们正在做的是创造 一个实际值，额外 指针在我们每个节点 也指向前一个节点。 因此，我们不仅有我们的 节点指向下一个。 他们还指出，前一个。 我将忽略这两个现在。 所以，那么你有一个链 可以移动两种方式， 然后它是一个更容易一些 从逻辑上跟随。 喜欢这里，而不是 饲养的，哦轨道，我 要知道，这个节点是 一个，我不得不重新分配， 我可以去这里 只是拉前面的。 后来我知道确切位置 也就是说，然后你 不必遍历 整体链表。 这是一个更容易一些。 但正因为如此，你必须加倍 指针的量， 这是内存的两倍。 这是一个很大的指针跟踪。 这是一个有点复杂，但它的 多一点人性视 你试图完成什么。 所以这种类型的数据 结构完全存在， 和结构是非常非常 简单以外的所有你遇到的， 而不只是一个指向下， 你也有一个指针以前。 这就是差异。 每个人都好有吗？ 凉。 好了，所以现在我 要真正花可能 像15至20分钟或散装 在节剩下的时间中 谈论哈希表。 有多少你们的 已经阅读pset5规范呢？ 好了，好了。 这比通常的50％以上。 好的。 所以当你们将会看到， 你在pset5挑战 将实施字典 在这里装载了14万字 我们给你和拼写检查 这对所有的文字。 我们会给你随机 文学作品的。 我们会给你奥德赛。 我们会给你伊利亚特。 我们会给你王牌大贱谍。 而你的挑战 将是拼写检查 在所有的每一个字 这些字典 本质上与我们的拼写检查器。 所以有几部分组成 创建这个PSET的， 首先你想成为 能够实际加载 所有的话到您的 字典，然后你 希望能够 拼写检查所有的人。 所以，正因为如此，你将需要 一个数据结构可以做到这一点快 并有效地和动态。 所以我想最简单的 办法做到这一点，你 可能会创建一个数组，对不对？ 存储的最简单的方法就是你 可以创造14万字的数组 而只是把它们都在那里和 然后通过二进制搜索遍历他们 或者通过选择或不是 - 遗憾的是真实的排序。 你可以对它们进行排序，然后遍历它们 由二进制搜索或者只是线性搜索 和公正的最后的话，但 需要大量的内存， 这不是很有效。 因此，我们要开始 说起制作方法 我们的运行时间更有效。 而我们的目标是获得 定时间，其中 这几乎就像阵列，其中 你有即时访问。 如果我想搜索什么， 我希望能够公正， 热潮，发现它完全，并将其拉出。 等的结构，其中 我们将变得非常接近 到能够访问恒定 当时，这圣杯 在恒编程 时间被称为哈希表。 于是大卫前面提到的 [听不清]在演讲一点点， 但我们要真正 下潜深，本周 对多数民众赞成有关一片 如何哈希表的工作原理。 这样的方式，一个散列 表作品，例如， 如果我想存储一堆话，一 一堆英文单词的， 我可以在理论上把 香蕉，苹果，猕猴桃，芒果，对， 和哈密瓜所有的只是一个数组。 他们都可以融入其中，并且被找到。 这将会是一种痛苦来 通过搜索和访问， 但这样做的更简单的方法是 我们实际上可以建立一个结构 所谓的哈希表，其中我们的哈希值。 我们通过运行所有的钥匙 散列函数，一个方程， 这将它们全部纳入 某种形式的值 那我们就可以存储到 链表基本上阵列。 所以在这里，如果我们想 存储英文单词， 我们可能潜在只是，我不知道 知道了，把所有的第一个字母 成某种形式的数目。 因此，例如，如果我想 一个是同义词apple-- 或为0的索引，和 乙的同义词1， 我们可以有26项 可以只是存储 所有的字母 字母表，我们将开始。 然后我们就可以有 苹果0的指数。 我们的指数有香蕉 1，哈密瓜2的指数， 等，等等。 就这样，如果我想搜索 我的哈希表和访问苹果， 我知道苹果开始 一个A，我确切地知道 它必须是和散列 表索引0，因为 函数的先前分配。 所以，我不知道，我们是 用户程序在哪里 你将被控 arbitrarily--不要随意， 与试图若有所思 想好方程 要能传播 你所有的价值观 在某种程度上，他们可以轻松地访问 后来在与像一个公式 你，你自己，知道了。 所以，在这个意义上，如果我想去 芒果，我知道，哦，它以M开头。 它必须是12的索引处。 我没有通过任何搜索。 我知道exactly--我可以只去 12和指数拉出了这一点。 每个人都清楚如何 哈希表的功能的工作？ 这是一种只是一个更复杂的阵列。 这就是它。 好。 所以我想，我们碰到 这个问题是什么 发生，如果您有多个事 这给你同样的指数？ 所以说我们的功能，所有这 做的是采取的第一个字母 并把它转换成一个 相应的0至25指数。 这是完全正常，如果 你只有每个之一。 但第二启动 有更多的，你 将有什么所谓的冲突。 所以，如果我尝试插入埋到一个哈希 表中已经有香蕉就可以了， 有什么事情发生时， 您尝试插入呢？ 坏事情，因为香蕉 在索引中已存在 您希望将其存储研究。 种浆果是喜欢啊，我该怎么办？ 我不知道哪里去了。 我该如何解决呢？ 等会有种你们 看到我们做这个棘手的事情 在这里，我们实际上可以种 创建链接的列表中我们的阵列。 这样一来，最简单的方法 思考这个问题， 所有的哈希表是一个 数组链表。 因此，在这个意义上说，必须 这个美丽的指针数组， 然后在每个指针 该值，在该索引， 可实际却指向其他的东西。 所以你把所有这些不同的 链条脱落一个大阵。 所以在这里，如果我 要插入浆果， 我知道，行，我要输入 它通过我的哈希函数。 我将结束与指数 1，然后我将能够有 此只是一小的子集 巨大的14万字的字典。 然后，我来找找看 通过该1/26。 而这样的话我可以插入 之前或之后香蕉浆果 在这种情况下？ 之后，对不对？ 所以，你会想 香蕉之后插入这个节点， 所以你要插入 在该链接列表的尾部。 我要回去 这一张幻灯片， 所以你们可以看到 哈希函数的工作。 所以散列函数是这样的方程 你正在运行的一种输入 通过获得任何指数 你希望它朝着分配。 因此，在这个例子中，所有我们想要 做的是采取的第一个字母， 把它转换成一个指数，那么我们 可以存储我们的散列函数在。 所有我们在这里所做的是我们 转换的第一个字母。 所以keykey [0]只是第​​一个字母 我们遇到的任何字符串， 我们通过研究。 我们要转换，要上，和 我们用大写字母A减去， 因此，所有的做 给我们提供了一些 在其中我们可以散列我们的价值观上。 然后，我们将 返回哈希模量的大小。 要非常，非常小心 因为，从理论上说，在这里 您的哈希值可以是无穷大。 它可能只是去和和。 这可能是一些非常， 真正大的价值， 但因为你的哈希表 你已经创建只有26指数， 你要确保你的 modulusing让你 不run--它是相同的 为您的queue--事 这样你就不会跑出 您的散列函数的底部。 你想换回来各地 在[听不清]时相同的方式 你必须像一个非常， 非常大的信，你 不想，要 刚跑出结束。 这里同样的事情，你要确保 它不流失年底通过包装 周围的表的顶部。 所以，这只是一个很 简单的哈希函数。 所有这一切确实是拿第一 不管我们输入的字母是 并把它转换成一个索引 我们可以把我们的哈希表。 是啊，所以我之前说的， 我们解决冲突的方式 在我们的哈希表有， 我们所说的，链接。 所以，如果你试图插入多 字开头同样的事情， 你将有一个哈希值。 鳄梨和苹果，如果你 通过我们的散列函数运行它， 将会给你 数相同，为0的数目。 这样一来，我们的方式解决是 样的，我们实际上可以将它们链接 通过链表在一起。 因此在这个意义上， 你们可以看样 如何数据结构 我们已经预先设定 像葡萄干链表样 可走到连成一片。 然后你就可以创建远 更有效的数据结构 可以处理更大的量 数据，动态调整不同 您的需要。 大家都清楚了吗？ 大家一种明确 在这里会发生什么？ 如果我想insert--什么是 水果有，我不知道开始， B，比其他浆果，香蕉。 听众：黑莓。 ANDI彭：黑莓，黑莓。 哪里黑莓跑到这里？ 好了，我们实际上已经没有排序 这还没有，但理论上 如果我们想有这样的 按字母顺序排列， 应该在哪里黑莓何去何从？ 听众：[听不清] ANDI鹏：没错，在这里后，对不对？ 但因为它是非常困难的 reorder--我想这是给你们。 你们可以完全 实现任何你想要的。 的更有效的方式 对这样做也许 将是您的排序链接 列出按字母顺序， 所以，当你 插入的事情，你想 以确保将其插入 按字母顺序 让那么当你 试图寻找他们， 你不必穿越一切。 你知道确切位置 它是，它更容易。 但是，如果你种得 东西随意穿插， 你仍然会有 到反正遍历。 所以，如果我想只 黑莓在这里插入 我想搜索 它，我知道，哦，黑莓 必须先从1的指数，所以我 认识瞬时只搜索1。 然后，我可以种 遍历链表 直到我到黑莓， 和then--是吗？ 听众：如果你想create-- 我想这样是一个非常简单的哈希 功能。 如果我们想做的事 多层，像的， 好了，我们要分成 像所有字母文字 然后再次喜欢上另一组 内的字母， 在我们把如哈希 哈希表内的表， 或者像函数中的一个函数？ 或者是that-- ANDI彭：所以，你的散列 function--你的哈希表 因为你希望它可以大。 因此，在这个意义上，我认为 这是非常容易的，很 简单对我来说，只是排序依据 在第一个单词的字母。 所以有唯一的26选项。 我只能得到26选项 0至25，因为它们只能 开始从A到Z，但如果你想 添加，或者，更复杂 或更快的运行时间，以你的 哈希表，你绝对 可以做各种各样的事情。 你可以让你自己 公式，让你 在更多的分销您 的话，那么当你搜索， 这将更快。 这完全取决于你的家伙 要如何实现这一点。 把它看成仅仅桶。 如果我想有 26桶，我要去 整理东西到这些水桶。 但我将有一大堆 的东西在每个桶， 所以如果你想让它 更快，更高效， 让我有一百桶。 但你必须找出一个 这样的事情进行排序，使他们 在适当的水桶他们应该研究。 但是当你真正 想看看那个桶， 它的速度快了很多，因为有 在每个桶少的东西。 所以，是的，这其实 的伎俩你们在pset5 是，你会 面临的挑战是只创建 什么是最有效的 功能，你能想到的是 能够存储和查询这些值。 完全取决于你们 然而，要做到这一点， 但是这是一个非常好的点。 那什么逻辑你 要开始思考 是，好了，我为什么不赚更多的桶。 然后，我要搜索 更少的东西，然后也许我 有一个不同的哈希函数。 是啊，有很多方法可以做到这一点 PSET，有些人比别人快。 我完全将只是看看 快速是最快你们会 能够得到您的功能才能生效。 OK，每个人都好于 链接和哈希表？ 它实际上是一个非常简单的 概念，如果你想想看。 所有这是区分什么 您的输入是成桶， 对它们进行排序，然后搜索 列出了还有的关联。 凉。 好了，现在我们有一个不同的排序 数据结构，这就是所谓的一棵树。 让我们去谈谈尝试 这是明显不同的， 但在同一类别。 从本质上讲，所有的一棵树，而不是 对组织数据以线性方式 一个哈希表does--您 知道的，它有一个顶部和一个底部 然后你有种链接关闭它 - 一对 树有你所说的根上面， 然后它有它周围的叶子。 所以，你在这里 仅仅是顶节点 指向其他节点，该点 到更多的节点，依此类推等等。 所以你就必须拆分分支机构。 这是组织的只是以不同的方式 数据，因为我们把它称为一棵树， 你们just--这只是 模拟出看起来像一棵树。 这就是为什么我们把它叫做树。 哈希表看起来像一个表。 树看起来就像一棵树。 所有这是一个独立的 节点组织方式 根据你的需求是什么。 所以，你有一个根， 那么你有叶子。 该办法，我们可以特别 想想这是一个二叉树， 二叉树只是一个 树的特定类型 其中每个节点仅分 于，在最大，其他两个节点。 所以，在这里你有不同的 对称性在你的树 这使得一种更加便捷地查询 在什么样的价值观，你是因为你 始终左或右。 从未有像从左侧第三 向左或从左侧的第四。 这只是你有左，右 你可以搜索上述两种的。 所以这是为什么有用吗？ 的方式，这是 有用的是，如果你正在寻找 通过值来搜索，对不对？ 而不是执行二进制 在一个错误数组搜索， 如果你想成为能够插入节点 并带走节点的意愿，也 保存搜索 二进制搜索的能力。 因此，在这种方式中，我们是那种 tricking--记得当时我们 说链表不能二进制搜索？ 样的，我们正在创建一个数据结构 该技巧，进入工作。 所以因为链表是线性的， 它们只能链接一前一后。 那种我们可以有 不同类型的指针 该点不同的节点 这可以帮助我们与搜索。 所以在这里，如果我想 有一个二进制搜索树， 我知道，我的中间，如果55。 我只是要创建 因为我的中间，因为我的根， 然后我将有 值剥离它。 所以在这里，如果我要去寻找 66的价值，我可以在55开始。 这比55 66更高？ 的确是这样，所以我知道我每亩搜索 I N这棵树的右指针。 我去77。 行，是66小于或大于77？ 它的不足，所以你知道，哦， 具有是左节点。 所以，我们在这里种保护 所有有关数组伟大的事情， 所以像动态调整 的对象，是 能够插入和删除随意， 而不必担心固定 量的空间。 我们仍然保留所有的 那些美好的事物 同时还能够保存 登录并搜索二进制搜索的时间 我们只是以前 能够得到一个短语。 酷派数据结构，种 复杂的实现，该节点。 正如你所看到的，它 是节点的结构 是，你有一个左 和一个右指针。 这就是它。 因此，而不是仅仅 具有一个X或先前。 你有一个左或右，然后 有种你可以将它们链接在一起 然而，你选择。 OK，我们实际上会 只需要几分钟的时间。 所以我们要回去这里。 正如我以前说过， 我种解释 后面我们如何逻辑 通过这样做搜索。 我们要尝试 pseudocoding了这一点，看看 样的，如果我们可以应用 二进制搜索的同样的逻辑 到不同类型的数据结构。 如果你们想采取像情侣 分钟，只是想想这一点。 好。 好吧，我要去 其实只是给你the--没有， 我们将谈论的伪代码第一位。 因此，没有人想 给刺伤了什么 你想要做的时候第一件事情 你开始搜索？ 如果我们正在寻找 66的价值，什么是 我们想要做的，如果第一件事 我们要的二进制搜索这棵树？ 听众：你想要看的权利 看看左边，看到[听不清] 更大的数字。 ANDI彭：是的，没错。 所以，你要看看你的根。 有很多方法可以调用 它，你的父节点的人说。 我想说的根因 这就像树的根。 你要看看 你的根节点，而你 要看到的是66更大 大于或小于55。 而如果它是大于，很好，这是 大于，在这里我们想看看吗？ 我们在哪里现在要进行搜索，对不对？ 我们要搜索 这种树的右半边。 因此，我们有，方便，一 指针指向右侧。 而这样的话，我们可以设置 我们新的根是77。 我们可以去到哪里 指针指向。 嗯，哦，在这里我们开始 77，我们可以只 递归一次又一次做到这一点。 通过这种方式，你有种 的有一个功能。 你有搜索你的一种方式 只需重复一遍又一遍又一遍， 这取决于你想看看 直到你最终得到的值 您正在搜索。 合理？ 我要告诉你的实际 代码，这是一个很大的代码。 没有必要惊慌。 我们将讨论通过它。 当然没有。 这只是伪代码。 好了，这仅仅是伪代码， 这是一个有点复杂， 但它完全罚款。 下面大家一起在这里吗？ 如果根是空的，回报 假的，因为这意味着 你甚至不用任何那里。 如果根n是价值，因此，如果 恰好是你看一， 那么你要返回true 因为你知道你发现了它。 但如果该值小于 小于n的根，你 要搜索左 子或左叶， 无论你怎么称呼它。 并且如果该值大于根， 你要寻找合适的树， 然后只需运行功能 通过搜索一次。 如果根是空的，这是 意味着你已经走到了尽头？ 这意味着你没有 更多更多的叶子进行搜索， 那么你知道，哦，我 猜想这是不是在这里 因为此前我已经通过看 整个事情，它是不是在这里， 它只是可能不会在这里。 这是否有意义给大家？ 所以，它就像二进制搜索保存 链表的功能。 凉，所以第二类型 数据结构，你们的 可以尝试实现你的PSET， 你只需要选择一种方法。 但是，也许是一个替代方法 哈希表就是我们所说的一个线索。 所有的一个线索是一个 树的特定类型 有一个去其他值的值。 所以具有代替二进制 树在这个意义上，只有一个 东西可以指向两个，可以有 一件事情点很多很多的东西。 本质上，阵列 其中你店内 指针指向其他阵列。 那么我们如何在节点 将定义一个线索 就是我们希望有一个 布尔，C字，对吧？ 所以该节点是布尔 像真的还是假的， 首先在头 该数组，这句话吗？ 其次，你想拥有指针 到任何人，其余都是。 一个有点复杂，有点抽象，但 我将解释那是什么一切手段。 因此，这里，在顶部，如果 有一个数组已经声明， 在这里你有一个布尔节点 存储在前面的值 告诉你的是这句话吗？ 这难道不是一个字？ 然后你有 阵列的其余部分的 实际存储所有的 什么可能是可能。 因此，举例来说，像 顶部有 的第一件事，说真的还是 假，是或否，这是一个词。 然后你有0到26 您可以存储的字母。 如果我想在这里搜索 对于蝙蝠，我去顶 我找B.我发现中的B我 数组，所以我知道，行，为B字？ B是不发一语，所以这样 我必须继续寻找。 我从B和我期待的 指针乙组分朝 我看到另一个信息阵列， 相同的结构，我们有过的。 而这里 - 哦，下 信[听不清]是A. 因此，我们期待在该数组。 我们发现第八值， 然后我们来看看，看看，哦， 哎，就是一个字，是B-A字？ 它不是一个字。 我们一定要继续寻找。 所以接下来我们来看看哪里 的一个点的指针， 并且它指向的另一种方式 我们有更多的价值存储。 而最终，我们得到 B-A-T，它是一个字。 这样一来，下一次 你看，你会 有，是的，办理入住手续， 此布尔函数是真实的。 所以在这个意义上，我们是一种 具有数组的树。 所以，你可以种向下搜索。 而不是散列函数，并且 通过链表分配值， 你可以实现一个 特里，搜索downwords。 真的，真的复杂的东西。 不容易想到，因为我很喜欢 随地吐痰，这么多的数据结构进行 你，但确实有种大家 理解这个逻辑的作品？ 嗯不错。 因此，B-A-T，然后 你要搜索。 你要去的下一次 看，哦，嘿嘿，这是真的， 因此，我知道这一定是一个字。 同样的事情了动物园。 因此，这里的事情，现在，如果我们 想寻找动物园，现在， 目前动物园是不是 字我们的字典 因为，正如你们所看到的， 我们有一个布尔首位 返回true是在放大的末端。 我们有Z-O-O-M。 所以在这里，我们实际上并不具备 这个词，动物园，在我们的字典 因为此复选框未选中。 因此，计算机不 知道动物园是一个字 因为我们已经一路 保存它，只有变焦这里 实际上有一个布尔值 一个已经变成事实。 因此，如果我们要插入的 一句话，动物园，为我们的字典， 我们怎么会去这样做？ 什么是我们必须做的，以确保我们的 计算机知道的是Z-O-O是一个字 而不是第一个字为Z-O-O-M？ 听众：[听不清] ANDI鹏：没错，我们 要确保这 这里，该布尔值是 检查过，这是真的。 Z-O-O，然后我们要去检查， 因此，我们确切地知道，哎，动物园是一个单词。 我要告诉 电脑，这是一个词，以便 计算机检查时， 它知道动物园是一个词。 因为记住所有这些数据 结构，这很容易让我们 说，哦，蝙蝠的一个词。 动物园的一个词。 Zoom的一个词。 但是当你构建它， 电脑不知道。 所以，你必须准确地告诉它 在什么时候，这是一个词？ 在什么时候是它不是一个字？ 而在什么时候做我 需要搜索事情， 和在什么时候，我需要去下一个？ 每个人都清楚的是什么？ 凉。 因此然后是 的问题，我们怎么会 去插入的东西 这实际上不是吗？ 所以，我们只能说，我们要插入 这个词，洗澡，到我们的线索。 正如你们可以看到像目前 所有我们现在已经是B-A-T， 和这个新的数据结构 曾有一品脱的 指着空，因为我们假设 即，哦，还有后B-A-T没有的话， 为什么我们需要保持 该T之后有东西 但问题出现了，如果我们做的你 想有来后一个字 T的。 如果你有浴缸，你 会想要一个H的权利。 所以，我们要做到这一点的方法是 我们要创建一个单独的节点。 我们没有配发任何金额 内存为这个新阵， 而且我们要重新分配指针。 我们将分配 H，首先，此空， 我们要摆脱。 我们将有 轰点向下。 如果我们看到一个H，我们希望它 去别的地方。 在这里，我们可以勾选肯定。 如果我们的T后击中H，OH， 那么我们知道这是一个词。 布尔将会返回true。 每个人都清楚如何发生的？ 好。 所以基本上，所有的 这些数据结构 我们已经讨论了今天，我已经 走了过来他们真的，真的快 而不是在得多 细节，这就是确定。 一旦你开始搞乱 有了它，你会 保持在那里的轨道 所有的指针， 什么在事情你 数据结构，等等。 他们将是非常有用的， 它是由你 家伙完全弄清楚如何 你想实现的东西。 因此pset4，5--哦，那是错误的。 Pset5是拼写错误。 正如我之前说的，你要去，一旦 再次，从我们这里下载源代码。 还有的将是三个主要的 事情你会被下载。 你会下载字典， KERS和文本。 所有这些东西都是有 无论是词词典 我们希望你检查 或信息测试 我们希望你能拼写检查。 这样一来，字典 我们给你准备 给你，我们要实际的话 你以某种方式存储的方式，是 比的阵列更有效。 然后将文本是 会是什么我们是 要求您进行拼写检查，以确保 所有的话有真实的话。 对这样一来，三大板块 计划，我们会给你 被称为dictionary.c， dictionary.h和speller.c。 因此所有dictionary.c确实是 你在要求执行。 它加载的话。 它拼写检查他们，并确保 一切都正确插入。 diction.h只是一个库文件 声明所有的这些功能​​。 而speller.c，我们打算给你。 你不需要修改任何它。 所有speller.c确实是拿去， 它装载，检查它的速度， 检验了怎么样的基准 很快你能够做到的事情。 这是一个拼写检查。 只要不惹它，但要 确保你明白它在做什么。 我们用一个函数调用的getrusage的 测试你的法术性能 检查器。 它所做的基本测试 一切都在你的字典的时间， 所以一定要了解它。 注意不要乱用，或 否则事情将无法正常运行。 而大宗这一挑战的是 你们真的修改dictionary.c。 我们打​​算给你 14万字的字典中。 我们将会给你一个文本 文件中有这些话， 我们希望你能够组织 成一个哈希表或字典树 因为当我们问你拼 check--想象一下，如果你的法术 检查像荷马的奥德赛。 这就像这个巨大的，巨大的考验。 如果每一个想象 一句话，你不得不看 通过140,000值的数组。 这将采取永远 为您的机器上运行。 这就是为什么我们要组织我们 数据转换成更有效的数据结构 如哈希表或字典树。 然后你们可以种 当您搜索的访问 事情更容易，更快速。 所以要小心，以解决冲突。 你会得到一堆 开头A的话 你会得到一堆话 开头B.由你 男人要如何解决它。 或许还有更多 高效的散列函数 比仅仅是第一信 一些东西，所以这是给你 样的人做任何你想要的。 也许你想添加 所有的来信。 也许你想喜欢做奇怪的事情 到账户的字母数， 随你。 截至你们要如何做。 如果你想要做一个哈希表，如果你 想尝试一个线索，完全取决于你。 我会提前发出警告的时间的你 线索通常是有点困难 只是因为有很多 更多的指针来跟踪。 但是，完全取决于你们。 这是更有效 在大多数情况下。 你要真正能够保持 跟踪你所有的指针的。 像做同样的事情 我在这里做什么。 当你试图插入 值到一个哈希表或删除， 请确保你 真的跟踪 对这里的一切是因为 这是因为，如果我真的很容易 试图插入之类的词，安迪。 远的不说，这是一个 真正的字，词，刘德华， 成的话一个巨大的列表。 如果我只是碰巧重新分配 指针错误，哎呀， 有去的全部 我的链接列表的其余部分。 现在唯一的一句话让我 已经是安迪，现在 所有的在该换言之 词典已经丢失。 所以你要确保你 跟踪所有的指针的 否则，你会得到 巨大的问题，在你的代码。 画的东西出来仔细一步一步来。 这使得它更容易想到的。 最后，要能 测试你的程序的性能 在大板。 如果你们拿 看CS50现在， 我们有什么所谓的大板。 它是最快的评分表 在所有的CS50的拼写检查倍 现在，我觉得像10上方 有时，我觉得其中八是工作人员。 我们真的希望你们击败我们。 我们所有的人都试图实现 最快的代码成为可能。 我们希望你们来尝试挑战 我们并实现比我们快 能够。 所以这是真的 第一次，我们是 要求你们做一个PSET的 你真的可以为所欲为方法 你想。 我总是说，这是更接近 以现实生活中的解决方案，对吗？ 我说，嘿，我需要你这样做。 建立一个程序，它为我。 做到这一点，但是你想要的。 我只知道，我要快。 这就是你的挑战，在这个星期。 你这家伙，我们要 给你一个任务。 我们将会给你一个挑战。 然后就看你们 完全只是弄清楚 什么是最快捷和最 有效的方式来实现这一点。 是吗？ 听众：我们是否允许，如果 要研究更快的方法 做哈希表在网上，我们可以做 这一点，引用别人的代码？ ANDI彭：是的，完全罚款。 所以，如果你们看 规范，有一条线 在规范中，说你们 完全自由地研究哈希 上有哪些功能 的更快的散列函数 通过为运行的东西 只要你引用的代码。 因此，一些人已经 想通了快速的方法 中做快速拼写检查器， 方式存储的信息。 完全取决于你的家伙，如果你 想只取了吧？ 请确保您引用。 这里的挑战真的 我们正在试图测试 是确保你知道 你倒过来指针。 至于你实现 实际的散列函数 而未来与像 数学要做到这一点， 你们可以研究什么 方法在线你们想要的。 是吗？ 听众：我们能不能​​只举 使用[听不清]？ ANDI彭：是的。 你可以在你的评论， 你可以举出像，哦， 从亚达采取亚达， 亚达，哈希函数。 任何人有任何问题吗？ 实际上，我们轻轻松松 通过板块今日。 我将在这里为 回答问题也是如此。 此外，正如我所说，办公室 今晚和明天小时。 该规范在本周其实是 超级简单和超短期阅读。 我建议考虑看看，刚 阅读它的全部内容。 而Zamyla实际上引导您 通过每个功能 你需要实现，所以它的 非常，非常清楚如何做的一切。 只是为了确保你 跟踪指针。 这是一个非常具有挑战性的pset。 这不是挑战，因为喜欢， 哦，其概念是这么多 困难，或者你要学会 这么多新的语法方式 你做的最后PSET。 这PSET是困难的，因为 有这么多的三分球， 然后这是非常，非常容易，一旦 你在你的代码中的错误不能 找到该错误是。 而如此完整和你绝对信心 家伙能够击败我们的[听不清] 拼写。 其实，我没有任何书面矿 然而，但我要写我的。 你写的，而因此 你，我会写我的。 我会尽量让 我的比你快。 我们将看到谁拥有最快的国家之一。 ，是的，我会看到所有的 你们在这里在星期二。 我将运行就像一个PSET车间一种。 所有部分的这 本周是PSET车间， 所以你们有很多机会 求助，办公时间一如既往， 我真的很期待 看完所有的人“的代码。 我测验在这里，如果你 你们要来得到这些。 就这样。