>> JASON HIRSCHHORN：欢迎大家 在第七节。
我们是在使用过程中七个星期。
而这个即将到来的周四 是万圣节，所以我
打扮得像个南瓜。
我不能弯腰，把上 我的鞋，所以这就是为什么我
只是穿着袜子。
我也没有下穿什么 这一点，所以我不能把它关闭，如果它的
分心给你。
我提前表示歉意。
你不需要想象 这是怎么回事。
我穿的拳击手。
所以，这一切都很好。
>> 我为什么我是一个较长的故事 打扮成一个南瓜，但我要去
保存后在本节 因为我确实想上手。
我们有很多令人兴奋的事情 走在这个星期。
他们大多直接涉及到这一点 本周的问题集，拼写错误。
我们打​​算是想在联 列表和哈希表
整个一节。
我每星期把这个名单了，名单 你来帮助您的资源
本课程的材料。
如果处于亏损状态，或者寻找一些 更多信息，请查看之一
这些资源。
>> 再次，pset6是拼写错误， 本周的pset中。
它也鼓励你，和我 鼓励你，使用一些其他的
资源专​​门为这个pset中。
特别是，这三个我已经 列出在屏幕上 -
gdb的，这是我们一直熟悉的 并一直在使用了一段时间了，是
打算这周是非常有益的。
所以，我把那在这里。
但每当你用C的工作， 你应该总是使用gdb来
调试程序。
这个星期也Valgrind的。
有谁知道什么Valgrind的呢？
>> 观众：它检查内存泄漏？
>> JASON HIRSCHHORN：Valgrind的 检查内存泄漏。
所以，如果你在malloc的东西你 程序，你要求的内存。
在程序结束时，你有 写免费的你已经一切
malloced给记忆回来了。
如果你不写免费在年底 你的程序涉及到一个结论，
一切都将自动 被释放。
而对于小程序，它的 不是什么大不了的事。
但是，如果你正在编写一个较长的运行 程序不会退出，
不一定，在一两分钟或中 几秒钟，然后内存泄漏
可以成为一个巨大的交易。
>> 所以对于pset6，期望是 你将有零内存泄漏与
你的程序。
要检查内存泄漏，运行的valgrind 它会给你一些不错的
输出让你知道是否 或不是一切是免费的。
我们将用它以后练 今天，有希望。
>> 最后，diff命令。
你用类似于它的东西 在pset5与偷看工具。
让你看看里面。
您也使用差异，同样，每 问题设置规范。
但允许你 比较两个文件。
你可以比较的位图文件和 一名工作人员解决方案信息标题和
在pset5你的解决方案，如果 您选择使用它。
差异可以让你 做到这一点，也是如此。
您可以比较正确的答案 本周的问题设置为你的答案
，看看它是否行向上或 其中误差。
>> 因此，这些都是三个好工具， 你应该使用这个星期，
一定要检查你的程序 这三个工具
将其入伙前
同样，正如我刚才所说的每一周， 如果您有任何意见对我来说 - 无论是
积极和建设性的 -
可以自由地前往网站 在这张幻灯片的底部
并且输入它。
我真的很感激任何 和所有的反馈。
如果你给我具体的东西， 我可以做些什么来改善或者说我
做得很好，你想我 继续，我采取的心脏和
真的努力去倾听 您的反馈。
我不能保证我会做 一切，不过，就像穿了
每周南瓜服装。
>> 因此，我们要花费大量的 部分，正如我所说，谈论
链表和哈希表，这 将直接适用于
问题本周设置。
链表我们就去了相对 很快，因为我们已经花了一个公平的位
的时间段去了它。
所以我们会得到直入 编码问题的链表。
然后在最后我们来谈谈 哈希表和它们如何适用于本
本周的问题集。
>> 你以前见过这个代码。
这是一个结构，它被定义 新的东西称为一个节点。
和一个节点内有一个整数 在这里，有一个指针
另一节点。
我们之前已经看到这一点。
这已经上来的 一对夫妇现在星期。
它结合了三分球，这是我们一直 与和结构，这让工作
我们将两个不同的 事成一种数据类型。
>> 有很多在屏幕上怎么回事。
但是，这一切应该是比较 熟悉你。
在第一行中，我们 声明一个新的节点。
然后将该新节点里面，我设置 一个在该节点的整数。
我们的下一行我做了见 printf命令，但我已经变灰
printf命令，因为真的 重要的是这条线在这里 -
new_node.n。
什么是圆点是什么意思？
>> 观众：转到节点， 评估它的N值。
>> JASON HIRSCHHORN：这是 完全正确。
点指访问n个部分 这个新的节点。
下面这一行做什么？
迈克尔。
>> 观众：它创建另一个节点 将指向新的节点。
>> JASON HIRSCHHORN：所以它不 创建新的节点。
它创建了一个什么？
>> 观众：一个指针。
>> JASON HIRSCHHORN：一个指针，指向一个节点， 通过该节点*这里所示。
因此它产生一个指针指向一个节点。
和哪一个节点指向它 到，迈克尔？
>> 观众：新的节点？
>> JASON HIRSCHHORN：新节点。
和它的指向那里，因为我们已经 赋予它新的节点的地址。
现在在这条线，我们看到 两种不同的方法
表达了同样的事情。
而我想指出如​​何将这些 两件事情是相同的。
在第一行中，我们解引用 指针。
所以我们去的节点。
这就是这个星号表示。
我们已经看到，之前与指针。
去那个节点。
这就是在括号中。
然后通过点操作符访问 该节点的n个元素。
>> 所以这走的语法 我们看到在这里和现在
使用它的指针。
当然，它得到的忙，如果样 你写的那些括号 -
这星和那点。
它变得有点忙。
因此，我们有一些语法糖。
而这条线就在这里 -
ptr_node - >ñ。
这做同样的事情。
因此，在这两行代码是 等效，并会尽
完全相同的事情。
>> 但我想指出那些之前 我们再往前走让你明白
真的这个东西在这里是 只是语法糖提领
的指针，然后将要 该结构的n个部分。
这个幻灯片有任何疑问？
确定。
>> 因此，我们要经过几个 操作，你可以做的
链表。
链表，召回，是一系列的 指向另一个节点。
而我们一般先从一个指针 称为头，一般地，一个指向
在列表中的第一件事情。
所以在第一行这里，我们 首先我们原装L。
所以，那个东西你能想到的 - 这 这里的文字，你能想到的作为
刚刚我们已经存储的指针 某处点
第一个元素。
而在这个链表 我们有四个节点。
每个节点都是一个大箱子。
里面的大较大的方框 框是整数部分。
然后我们有一个指针组成部分。
>> 这些箱子都没有吸引到 因为规模是多大
以字节为单位的整数
现在有多大？
四。
多大是一个指针？
四。
因此，其实，如果我们绘制 这个扩展的两个方块
将是相同的大小。
在这种情况下，我们希望插入 事到链表。
所以，你可以下来看看我们在这里插入 5，我们通过遍历
链表，找到其中5 去，然后将其插入。
>> 让我们打破了，去 多一点点慢。
我要指出的板。
因此，我们有我们的节点5的 我们在mallocs创建。
为什么大家都笑了？
只是在开玩笑。
确定。
因此，我们已经malloced五位。
我们创建这个节点 别的地方。
我们必须准备好去。
我们开始在前面 我们的名单有两个。
我们要插入 在已排序的方式。
>> 所以，如果我们看到了两个，我们希望把 五，我们该怎么做，当我们看到
东西不到我们？
什么？
我们要插入五成这 链表，保持它排序。
我们看到第二。
那么，我们该怎么办？
马库斯？
>> 观众：调用指针 到下一个节点。
>> JASON HIRSCHHORN：为什么做 我们去下一个？
>> 观众：因为它是 列表中的下一个节点。
而我们只知道其他位置。
>> JASON HIRSCHHORN：而且五是更大 大于2，尤其如此。
因为我们要保持它排序。
因此，五是大于二。
因此，我们就移动到下一个。
现在我们达到四。
而当我们达到四会发生什么？
>> 五是大于四。
因此，我们继续前进。
现在我们是在六人。
什么我们六看？
是的，卡洛斯？
>> 观众：六是大于五。
>> JASON HIRSCHHORN：六是 大于五。
所以这就是我们想要的 插入五位。
但是，请记住，如果我们 只有一个指针在这里 -
这是我们额外的指针，它是 遍历整个列表。
我们正在指向6。
我们已经失去了什么轨道 谈到前六。
因此，如果我们要插入到的东西 这个列表保持排序，我们
大概需要多少个三分球？
>> 观众：两个。
>> JASON HIRSCHORN：两个。
一个以跟踪当前的 1，一个用于跟踪
前一个。
这仅仅是一个单向链表。
那就只一个方向。
如果我们有一个双向链表，其中 一切都指向一点
之后和之前的事情了，然后 我们不需要那样做。
但在这种情况下，我们不希望失去 轨道的情况下，我们面前什么来
我们需要插入五个地方 在中间。
说我们被插入9。
什么时候会发生 我们得到了八？
>> 观众：你不得不 拿到零点。
而不必空点你不得不 添加一个元素，然后有
这点九。
>> JASON HIRSCHORN：没错。
所以我们得到8。
我们到达列表的末尾，因为 这是指向空。
而不是有和现在，它指向 空我们把它指向我们的新节点。
而我们在设置指针 我们的新节点为null。
没有任何人有任何疑问， 有关插入？
如果我不关心什么 保持排序的列表？
>> 观众：在坚持它 开始或结束。
>> JASON HIRSCHORN：在坚持它 的开始或结束。
哪一个才好呢？
鲍比？
为什么要结束了吗？
>> 观众：因为开始时 已经充满。
>> JASON HIRSCHORN：确定。
一开始已经充满。
谁想要反驳鲍比。
马库斯。
>> 观众：那么你可能想 把它贴在一开始，因为
否则，如果你把它在 最后，你不得不
遍历整个列表。
>> JASON HIRSCHORN：没错。
因此，如果我们正在考虑运行时， 在最后插入的运行时
将N，这个尺寸。
什么是插入的大O运行 在开始？
常量时间。
所以，如果你不关心保持 整理东西，好多只
插入此列表的开头。
并可以在常数时间内完成。
>> 确定。
接下来的操作就是找到，这是其它 - 我们这个措辞作为搜索。
但我们要看看通过 链表的一些对象。
你们已经看到代码 以前搜索的讲座。
样的，但我们只是做了它与 插入，或者至少插入
东西来分类的。
你通过，由节点将节点， 直到你发现你的号
寻找。
如果你达到会发生什么 该列表的末尾？
说我在找九和我 到达列表末尾。
我们该怎么办？
>> 观众：返回false？
>> JASON HIRSCHORN：返回false。
我们没有发现它。
如果到达列表的末尾， 你没有找到你的号
寻找的，它不是在那里。
大约有任何疑问找到？
如果这是一个排序的列表，会是什么 对我们的搜索有什么不同？
是啊。
>> 观众：它会找到的第一个值 这是大于1
你正在寻找和 然后返回false。
>> JASON HIRSCHORN：没错。
所以，如果这是一个排序的列表，如果我们得到 东西是比什么
我们要寻找的，我们不需要 继续前进到列表的末尾。
我们可以在这一点上返回false 因为我们不会找到它。
现在的问题是，我们已经讨论过 保持链表排序，
保持它们排序。
那将是什么你 可能将不得不去思考
当编码问题设置5，如果你 选择配有独立的哈希表
链接的方法，这 我们将在以后讨论。
>> 但它是值得的，以保持列表 排序，然后才能有可能
更快的搜索？
还是更快速插入 东西在不断的运行，但随后
有较长的搜索？
这是一个折中就在那里，你 去决定什么是更合适
针对您的具体问题。
而且也并不一定是 绝对正确的答案。
但它肯定是你的决定 做了，大概好保卫
在，也就是说，一个或两个注释为什么 你选择了一个比其他。
>> 最后，删除。
我们已经看到删除。
它类似于搜索。
我们期待的元素。
假设我们正在试图删除6。
因此，我们发现了六个就在这里。
我们必须确保我们的东西 做的是，无论是指向
6 - 正如我们在一步看 两下在这里 -
凡是指着六个需要 跳过6现在改为
无论6指向。
我们不希望永远孤儿的其余部分 通过忘记来设定我们的名单
以前的指针。
然后，具体情况取决于 上节目，他们就会
完全删除该节点。
有时候你会想回到 该值，在此节点。
所以这就是如何删除工作。
对任何问题删除？
>> 观众：所以，如果你要删除 它，你只需要使用免费的，因为
想必有人malloced？
>> JASON HIRSCHORN：如果你想释放 东西是完全正确的，你
malloced它。
假设我们想返回这个值。
我们可能会选出6位，然后免费 这个节点和呼叫免费就可以了。
或者，我们可能会调用free第一 然后选出6。
>> 确定。
因此，让我们继续前进练习编码。
我们要编写三个函数。
第一个被称为insert_node。
所以，你有我发邮件给你的代码， 如果你看这个以后
您可以访问代码linked.c 在CS50网站。
但在linked.c，有一些 框架代码的已经
已为你写好。
然后有一对夫妇的功能 你需要写。
>> 首先我们要 写insert_node。
什么insert_node呢 就是插入一个整数。
而你给的整数 成一个链表。
特别是，你需要 保持排序的列表
从最小到最大。
此外，您不希望 插入任何重复。
最后，你可以看到insert_node 返回一个布尔值。
所以你应该让用户知道 是否插入了
成功通过返回true或false。
在这个程序结束 -
而这个阶段你不需要 不用担心释放任何东西。
因此，所有你正在做的是采取一个整数 并将其插入到一个列表中。
>> 这就是我要问你现在要做的。
再次，在linked.c，你 全有，是框架代码。
你应该向底部看 示例函数声明。
然而，在进入它的编码 在C中，我强烈建议你去
经过的步骤，我们已经 每星期练习。
我们已经通过了 在此照片。
所以，你应该有一定的了解 是如何工作的。
但我会鼓励你写 跳水英寸之前的一些伪代码
我们要去投奔 伪代码为一组。
然后，一旦你写你的 伪代码，一旦我们写我们
伪代码为一组，你可以 进入编码它在C
>> 作为一名负责人时，insert_node功能 可能是最棘手的
三，我们要去写，因为我 增加了一些额外的限制，
你的编程，尤其是 你不会插入任何
重复，并且列表 应保持有序。
所以这是一个不平凡的程序 你需要的代码。
而你为什么不拿五到七 分钟，只是为了让工作在
伪代码和代码。
然后我们将开始 要为一组。
同样，如果你有任何问题，只是 举起你的手，我会回到你身边。
。
>> 我们一般做这些 -
或者我没有明确说你 能与人合作。
但很明显，我强烈鼓励你， 如果你有问题，问
邻居坐在你旁边 甚至是与别人合作
否则，如果你想。
这不必是一个单独的 沉默的活动。
>> 让我们开始写一些 伪代码在黑板上。
谁可以给我的第一行 伪代码对这一计划？
对于此功能，而 - insert_node。
奥尔登？
>> 观众：所以第一件事是 创建一个新的指针的节点和余
初始化它指向相同 东西的清单指向。
>> JASON HIRSCHORN：确定。
所以，你要创建一个新的指针 到列表中，而不是到该节点。
>> 观众：对。
是啊。
>> JASON HIRSCHORN：确定。
然后我们究竟想干什么？
什么之后呢？
怎么样的节点？
我们没有一个节点。
我们只是有一个值。
如果我们要插入一个节点，我们怎么办 需要之前，我们甚至可以先做
想想插入呢？
>> 观众：哦，对不起。
我们需要将malloc空间的节点。
>> JASON HIRSCHORN：优秀。
让我们做 -
确定。
无法达到那么高。
确定。
我们要往下走，然后 我们使用的是两列。
我不能去了 -
确定。
创建新的节点。
您可以创建另一个指针列表 或者你可以用列表作为它的存在。
你并不真的需要做到这一点。
>> 因此，我们创建了一个新的节点。
大。
这就是我们做的第一个。
下一步是什么？
>> 观众：请等待。
如果我们现在创建一个新的节点或 我们应该等待，以确保
有节点没有重复 名单上之前，我们创建它吗？
>> JASON HIRSCHORN：好问题。
让我们认为，对于后来因为 大部分我们将要创建的时间
一个新节点。
因此，我们会继续在这里。
但是，这是一个很好的问题。
如果我们创建它，我们发现 一式两份，又该
我们返回之前做的？
>> 观众：释放它。
>> JASON HIRSCHORN：是啊。
可能释放它。
确定。
我们之后我们做什么 创建一个新的节点？
安妮？
>> 观众：我们把 在节点数量？
>> JASON HIRSCHORN：没错。
我们把数字 - 我们用malloc空间。
我要离开了 所有为一行。
但你说得对。
我们malloc的空间，然后 我们把数英寸
我们甚至可以设置指针 它的一部分为null。
这是完全正确的。
再怎么样之后呢？
我们画了这幅画在黑板上。
那么，我们该怎么办？
>> 观众：我们通过列表。
>> JASON HIRSCHORN：穿过列表。
确定。
什么我们在每个节点检查。
库尔特，什么我们检查 于每个节点？
>> 观众：看有无N值的 该节点是大于n值
我们的节点。
>> JASON HIRSCHORN：确定。
我该怎么办 -
是的，确定。
所以它的北 -
我会说，如果值大于 比这个节点，那么我们怎么办？
>> 观众：好，那我们插入 前正确的事情。
>> JASON HIRSCHORN：确定。
所以，如果它大于这个， 那么我们要插入。
但我们要正确之前，将其插入 因为我们也将需要
跟踪，然后， 什么是以前。
所以之前插入。
因此，我们可能错过了什么 较早前。
我们可能需要被保留 轨道发生了什么事情。
但我们会回到那里。
那么，什么值小于？
库尔特，我们该怎么做，如果 值小于？
>> 观众：那你只是继续前进 除非它是最后一个。
>> JASON HIRSCHORN：我喜欢这样。
所以去到下一个节点。
除非它是最后一个 -
我们可能检查的 中的一个条件的条件。
但是，是的，下一个节点。
而且是越来越过低， 因此，我们将在这里搬过来。
但是，如果 -
大家可以看到这个？
如果我们是平等的我们该怎么做？
如果这个值我们试图插入 等于该节点的值？
是吗？
>> 观众：[听不清]。
>> JASON HIRSCHORN：是啊。
鉴于这一点 -
马库斯是正确的。
我们也可以或许做 不同的东西。
但鉴于我们已经创造了它，在这里 我们应该释放，然后返回。
哦男孩。
是更好吗？
怎么样？
确定。
免费，然后我们怎么办 返回[听不清]？
确定。
我们是否缺少什么？
那么，我们要跟踪 事先节点？
>> 观众：我觉得它会去 之后创建一个新的节点。
>> JASON HIRSCHORN：确定。
所以，在一开始我们可能会 -
是的，我们可以创建一个指向新 节点，就像前一个节点的指针和
当前节点的指针。
因此，让我们插入这里。
创建当前和以前 指向的节点。
但是，当我们调整这些指针？
我们在哪里做的代码？
杰夫？
>> 观众： - 值条件是什么？
>> JASON HIRSCHORN：哪 一个特殊？
>> 观众：我只是困惑。
如果值大于这个节点， 并不意味着你要去
到下一个节点？
>> JASON HIRSCHHORN：所以，如果我们的价值 大于该节点的值。
>> 观众：是啊，那你想要 进一步向下行去，对不对？
>> JASON HIRSCHHORN：对。
所以我们不要插入在这里。
如果值小于当前节点，然后 我们进入下一个节点 - 或者那我们
前插入。
>> 观众：等一下，这是本 节点，这是价值？
>> JASON HIRSCHHORN：好问题。
根据该函数的定义值 就是我们给出。
因此，价值是我们给出的数字。
因此，如果该值小于该 节点，我们需要时间来插入。
如果值大于这个节点， 我们去到下一个节点。
再回到原来的问题， 不过，在这里 -
>> 观众：如果值大于 比这个节点。
>> JASON HIRSCHHORN：所以 我们该怎么做吗？
甜蜜。
这是正确的。
我只是去写 更新指针。
但是，是的，与当前的 你会更新到
指向下一个。
别的我们缺少什么？
所以，我要输入此 编码成gedit的。
而我做到这一点，你可以有一个 夫妇多钟上班编码
这在C
>> 所以，我有输入的伪代码。
一个快速的音符在我们开始之前。
我们未必能够完全 在完成所有这
这三个功能。
有正确的解决办法 我会发电子邮件到你们
部后，它会 张贴在CS50.net。
所以我不鼓励你 去看看部分。
我鼓励你在尝试这些你 自己，然后用实践
问题来检查你的答案。
这些都被设计成紧密 与坚持什么
你所要做的习题集。
因此，我鼓励你练习这个 在你自己的，然后使用代码
检查你的答案。
因为我确实想移动到哈希 表在某些部分点。
因此，我们可能不会得到通过这一切。
但我们现在会做尽可能多的，我们可以。
>> 确定。
让我们开始吧。
阿萨姆，我们如何创建一个新的节点？
>> 观众：你STRUCT *。
>> JASON HIRSCHHORN：所以我们 有一个在这里。
哦，对不起。
你是说结构*。
>> 观众：然后[？样？] 节点或c节点。
>> JASON HIRSCHHORN：确定。
我要叫它new_node 所以我们可以保持一致。
>> 观众：你要设置的 头，第一个节点。
>> JASON HIRSCHHORN：确定。
所以，现在这个指向 - 所以这 还没有创建一个新的节点呢。
这仅仅是指向 列表中的第一个节点。
我如何创建一个新的节点？
如果我需要空间来创建一个新的节点。
malloc的。
有多大？
>> 观众：结构体的大小。
>> JASON HIRSCHHORN：该 该结构的大小。
和什么所谓的结构？
>> 观众：节点？
>> JASON HIRSCHHORN：节点。
所以的malloc（的sizeof（节点））; 给我们空间。
而就是这条线 -
有一件事是不正确的这条线。
是new_node一个指向结构的指针？
这是一个通用名称。
这是什么 -
节点，没错。
这是一个结点*。
右后我们该怎么做 我们malloc的东西，阿三？
什么是我们做的第一件事？
如果它不工作？
>> 观众：哦，检查它是否 指向的节点？
>> JASON HIRSCHHORN：没错。
所以，如果你new_node等于等于 空，我们该怎么做？
这会返​​回一个布尔值，此功能。
没错。
看起来不错。
什么要补充的吗？
我们会在末尾添加的东西。
但是，到目前为止，看起来不错。
创建当前和以前的指针。
迈克尔，我该怎么办呢？
>> 观众：你将不得不 做一个结点*。
你必须做一个不 为new_node但对于
节点我们已经有了。
>> JASON HIRSCHHORN：确定。
因此，在当前节点我们是在。
我会打电话给那个CURR。
好的。
我们已经决定，我们希望保持 2，因为我们需要知道
什么才。
他们得到什么初始化？
>> 观众：他们在我们的列表值。
>> JASON HIRSCHHORN：那么什么是 我们的名单上的第一件事？
或者，我们怎么知道在哪里 一开始我们的名单是什么？
>> 观众：是不是应该通过 进入功能？
>> JASON HIRSCHHORN：对。
它是通过在这里。
这样，如果它的传递给函数，该 启动列表中，我们应该怎样
设置电流等于？
>> 观众：列表。
>> JASON HIRSCHHORN：列表。
这是完全正确的。
现在，它拥有的地址 我们的列表的开始。
又是怎么回事以前？
>> 观众：原价减一？
>> JASON HIRSCHHORN：有 什么才。
所以，我们能做些什么来表示什么？
>> 观众：空。
>> JASON HIRSCHHORN：是啊。
这听起来是个好主意。
完美的。
谢谢。
经过列表。
康斯坦丁，多久我们要 要经过的名单？
>> 观众：直到我们到达空。
>> JASON HIRSCHHORN：确定。
所以，如果，而对于循环。
我们在做什么？
>> 观众：也许一个for循环？
>> JASON HIRSCHHORN：让我们做一个for循环。
确定。
>> 观众：我们说的 -
直到当前指针 不等于空。
>> JASON HIRSCHHORN：所以，如果我们知道 条件下，我们怎么能写一个循环
根据关闭的状态。
我们应该使用什么样的循环？
>> 观众：虽然。
>> JASON HIRSCHHORN：是啊。
这使得基于更有意义 关闭你说什么。
如果我们只是想进入我们它会 只知道那个东西，它将使
踏踏实实做一个while循环。
而当前不等于空值， 如果值小于该节点。
AKSHAR，给我这条线。
>> 观众：如果电流>Ñ Ñ​​低于价值。
或推翻。
开关的支架。
>> JASON HIRSCHHORN：对不起。
>> 观众：更换支架。
>> JASON HIRSCHHORN：所以，如果它是 比价值更大。
因为这是混乱的 上面的评论，我会做到这一点。
但肯定的。
如果我们的价值低于本 节点，我们该怎么做？
呵呵。
我就在这里。
前插入。
确定。
我们该怎么做呢？
>> 观众：是不是还是我？
>> JASON HIRSCHHORN：是啊。
>> 观众：你 -
new_node - >下一个。
>> JASON HIRSCHHORN：那么什么是 这将等于？
>> 观众：这将相等的电流。
>> JASON HIRSCHHORN：没错。
这样一来，其他 -
我们需要更新什么？
>> 观众：检查过去等于null。
>> JASON HIRSCHHORN：如果上一个 -
所以，如果前一个等于null。
>> 观众：这意味着它是怎么回事 成为头部。
>> JASON HIRSCHHORN：这意味着 它已经成为了头。
这样的话我们该怎么做？
>> 观众：我们做头部等于new_node。
>> JASON HIRSCHHORN：头 等于new_node。
以及为什么在这里头，没有列出？
>> 观众：因为头是一个全球性的 变量，它是起始位。
>> JASON HIRSCHHORN：甜。
确定。
和 -
>> 观众：那你别的上一页 - > 接下来等于new_node。
然后返回true。
>> JASON HIRSCHHORN：在哪里做 我们设置new_node结束了吗？
>> 观众：我会 -
我设置的开始。
>> JASON HIRSCHHORN：那么什么线？
>> 观众：在if语句 如果它被称为检查。
>> JASON HIRSCHHORN：就在这里？
>> 观众：我愿意做new_node - >Ñ 等于价值。
>> JASON HIRSCHHORN：听起来不错。
也许这是有道理的 - 我们不这样做 要知道我们是在什么名单
因为我们只处理 用一个列表。
因此，一个更好的函数声明为 这只是为了摆脱这种
完全和刚插入 一个值到头部。
我们甚至不需要知道 我们在做什么榜单中。
但我会保持它现在和 那么在更新变化
幻灯片和代码。
所以，看起来很不错的了。
如果值 - 谁可以做这行？
如果 -
我们该怎么做在这里，诺亚。
>> 观众：如果值大于 比CURR - >北 -
>> JASON HIRSCHHORN：如何做 我们进入下一个节点？
>> 观众：CURR-> n是 等于new_node。
>> JASON HIRSCHHORN：那么n是 什么样的结构的一部分？
整数。
和new_node是一个指针，指向的节点。
因此，我们应该更新什么CURR的一部分？
如果没有n，那么有什么其他部分？
诺亚，有什么其他部分。
>> 观众：呵呵，下次。
>> JASON HIRSCHHORN：下一步，没错。
没错。
接下来是正确的。
还有什么我们需要 更新，诺亚？
>> 观众：该指针。
>> JASON HIRSCHHORN：所以 我们更新了电流。
>> 观众：上一页 - >下一个。
>> JASON HIRSCHHORN：是啊。
OK，我们会暂停。
谁可以帮助我们在这里？
马努，我们应该怎样做？
>> 观众：你一定要设置 它等于CURR - >下一个。
但做到这一点之前的前行。
>> JASON HIRSCHHORN：确定。
还有别的吗？
AKSHAR。
>> 观众：我不认为你是 为了改变未来CURR->。
我觉得你的意思做CURR等于 CURR - >下次去到下一个节点。
>> JASON HIRSCHHORN：那么对不起，在哪里？
在哪一行？
这条线？
>> 观众：是啊。
让CURR等于CURR - >下一个。
>> JASON HIRSCHHORN：所以这是正确的 因为电流是
指针到一个节点。
我们希望它指向下一个 什么是越来越当前节点
指出。
CURR本身所具有的未来。
但如果我们要更新curr.next，我们 将更新的实际音符
本身，而不是这个地方 指针指着。
那么这条线，虽然。
阿维？
>> 观众：上一页 - >下一次等于CURR。
>> JASON HIRSCHHORN：如此反复，如果上一个是一个 指针指向一个节点，前值 - >下一个是
实际的指针中的节点。
所以这将是一个更新 指针在一个节点CURR。
我们不希望更新 指针中的一个节点。
我们要更新以前。
那么，如何才能做到这一点？
>> 观众：这纯粹是上一个。
>> JASON HIRSCHHORN：对。
上一个是指向的节点。
现在，我们正在改变到一个 新的指针的节点。
OK，让我们向下移动。
最后，这最后一个条件。
杰夫，我们该怎么做吗？
>> 观众：如果值是 等于CURR->ñ。
>> JASON HIRSCHHORN：对不起。
哦，我的天啊。
什么？
值== CURR->ñ。
我们该怎么办？
>> 观众：你会释放我们的new_node， 然后你会返回false。
>> JASON HIRSCHHORN：这是什么 我们已经写了这么远。
没有任何人有什么 加入我们做出过吗？
确定。
让我们试试吧。
控制可能到达终点 非void函数。
阿维，这是怎么回事？
>> 观众：你应该把回报 while循环的外面真的吗？
>> JASON HIRSCHHORN：我不知道。
难道你要我？
>> 观众：没关系。
号
>> JASON HIRSCHHORN：AKSHAR？
>> 观众：我觉得你的意思是 把返回false在年底
while循环。
>> JASON HIRSCHHORN：那么， 你希望它去？
>> 观众：像while循环之外。
所以，如果你退出while循环的方式 你已经走到了尽头，并
什么也没有发生过。
>> JASON HIRSCHHORN：确定。
那么，我们在做什么在这里？
>> 观众：你返回false 有作为。
>> JASON HIRSCHHORN：哦，我们 这样做在这两个地方？
>> 观众：是啊。
>> JASON HIRSCHHORN：确定。
我们是否应该去？
哦，我的天啊。
对不起。
我的屏幕道歉。
那种它吓坏了我们。
因此，选择一个选项。
零，每代码，退出程序。
一要插入一些东西。
让我们来插入三个。
插入未成功。
我要打印出来。
我没有任何东西。
确定。
也许这只是一个侥幸。
插一句。
没有成功。
确定。
让我们通过GDB真的快速运行 要看看是怎么回事。
>> 还记得GDB /姓名您的 计划将引领我们进入GDB。
是很多来处理？
闪烁的？
也许吧。
闭上你的眼睛，并采取一些深 如果你厌倦了喘气，呼吸的
看着它。
我在广发行。
什么是我做的第一件事在广发行？
我们必须搞清楚 这是怎么回事。
让我们来看看。
我们有六分钟图 发生了什么事情。
突破为主。
然后我该怎么办？
卡洛斯？
运行。
确定。
让我们选择一个选项。
又是什么Ñ办？
下一步。
是啊。
>> 观众：你没提 -
没有你说的那个头，那是 初始化为null开头。
不过，我想你说还行。
>> JASON HIRSCHHORN：让我们去 - 让我们来看看 在GDB中，然后我们就回去。
但它听起来像你已经有 一些想法发生了什么事情。
因此，我们要插入一些东西。
确定。
我们已经插入。
请输入一个整数。
我们会插入三个。
然后我在这行。
我该如何去开始调试 插入已知的功能？
哦，我的天啊。
这是一个很多。
是吓坏了很多吗？
>> 观众：哦，它死了。
>> JASON HIRSCHHORN：我刚 拉出来。
确定。
>> 观众：也许这是 导线的另一端​​。
>> JASON HIRSCHHORN：哇。
因此，底线 -
你说什么？
>> 观众：我说的技术上的讽刺 困难在这个类中。
>> JASON HIRSCHHORN：我知道。
如果我有过这部分控制权。
[听不清]
这听起来不错。
为什么你们不开始思考 我们可能做错了，
我们将回到90秒。
>> Avica，我要问你怎么走 里面insert_node调试它。
所以这是我们最后离开的。
我怎么进去insert_node，Avica， 检查是怎么回事？
什么GDB命令？
休息也不会带我里面。
请问侯爵夫人知道吗？
>> 观众：是什么？
>> JASON HIRSCHHORN：什么GDB命令 我用走这个函数里面？
>> 观众：步骤？
>> JASON HIRSCHHORN：通过步骤 S.这里面需要我。
确定。
New_node mallocing一些空间。
这一切看起来像它去。
让我们来看看new_node。
它得到了一些内存地址。
让我们来看看 -
这是正确的。
所以，这里的一切似乎 可以正常工作。
>> 观众：有什么区别 之间的P和显示器？
>> JASON HIRSCHHORN：P代表打印。
所以你问有什么 那这之间的区别？
在这种情况下，没有什么。
但一般有 一些差异。
而且你应该看看在GDB手册。
但在这种情况下，没有什么。
我们倾向于使用打印，但因为 我们并不需要做得更多，不
打印单个值。
>> 确定。
因此，我们对我们的代码80行， 设置节点* CURR等于列表。
让我们打印出CURR。
它等于列表。
甜蜜。
等待。
它等于什么。
这看起来不正确。
我们走吧。
这是因为在GDB中，右，如果 这是你在​​这行
还没有执行。
所以，你需要实际输入 执行下一行
之前看到它的结果。
所以，我们在这里。
我们只是执行这条线， 以前等于null。
如此反复，如果我们以前的打印 我们将不会看到什么奇怪。
但是，如果我们实际执行的 行，那么我们会看到
即该行的工作。
>> 因此，我们有CURR。
这些都是很好的。
对不对？
现在，我们在这条线就在这里。
虽然CURR不等于空。
那么，有哪些呢CURR相等？
我们只是看到它等于空。
我们把它打印出来。
我会再次把它打印出来。
所以是while循环 去执行？
>> 观众：号
>> JASON HIRSCHHORN：所以，当我输入了 行，你看我们跳了一路
下到谷底，返回false。
然后我们要返回false 然后回到我们的节目和
最终打印出来，就像我们所看到的， 插入没有成功。
因此，任何人有什么什么想法 我们需要做些什么来解决呢？
我要等到我看到 一对夫妇的手走了。
我们没有执行这个。
请记住，这是第一次 我们正在做的事情。
我不打算做一对夫妇。
我打算做几个。
因为一对夫妇意味着两。
我等了两个多。
>> 第一插入，CURR， 默认情况下等于null。
而这个循环只执行 如果CURR不为null。
所以，我怎么能解决这个问题呢？
我看见三只手。
我等了三个多。
马库斯，你有什么感想？
>> 观众：好吧，如果你需要它 执行一次以上，你只是
将其更改为一个do-whil​​e循环。
>> JASON HIRSCHHORN：确定。
这将解决我们的问题有关系吗？
>> 观众：在这种情况下，不因 事实上，该列表为空。
所以，那么你可能只需要添加 声明说，如果循环退出
那么你必须要在年底 在列表中，此时您
只需将其插入。
>> JASON HIRSCHHORN：我喜欢这样。
这是有道理的。
如果循环退出 -
因为它会在这里返回false。
所以，如果退出循环，然后我们在 该列表的末尾，或者也许是
启动列表中，如果有什么的 它，这是相同的端部。
所以，现在我们要插入 这里的东西。
那么，如何该代码看，马库斯？
>> 观众：如果你已经拿到了节点 malloced，你可以只说
new_node - >下一次等于null，因为 它必须是在末端。
或new_node - >下一个等于null。
>> JASON HIRSCHHORN：确定。
抱歉。
New_node - >下一个等于null 因为我们是在最后。
不把它英寸
我们如何把它在列表中？
右。
这只是设置它等于。
没有我们如何做实际上 把它在列表中？
什么是指向 列表的末尾？
>> 观众：头。
>> JASON HIRSCHHORN：对不起？
>> 观众：头指向 到该列表的末尾。
>> JASON HIRSCHHORN：如果有什么的 列表中，头是指向
列表的末尾。
所以说要工作 首先插入。
怎么样，如果有一对夫妇 列表中的东西呢？
不是我们不想设置 头等于new_node。
我们究竟想干什么呢？
是吗？
可能是以前的。
将这项工作？
回想一下，以前只是 一个指针指向一个节点。
和以前的是一个局部变量。
所以，这条线将设置一个局部变量， 以前，等于或
指向该新节点。
这实际上不会把它 在我们的名单，虽然。
我们如何把它在我们的名单？
Akchar？
>> 观众：我觉得你 做电流>下一个。
>> JASON HIRSCHHORN：确定。
CURR - >下一个。
所以，再一次，我们是下来的唯一理由 这里是有哪些呢电流等于？
>> 观众：等于null。
>> JASON HIRSCHHORN：还等什么 发生，如果我们做空 - >下一个？
我们究竟要得到什么？
我们会得到一个段错误。
>> 观众：做CURR等于null。
>> JASON HIRSCHHORN：这是同样的事情 如前一个，不过，因为有
我们设置一个局部变量 等于这个新的节点。
让我们回到我们的图片 中插入一些东西。
说我们要插入在最后 列表中的，所以就在这里。
我们有一个当前指针这是 指着空，以前的点
这是指向8。
那么，我们需要什么更新，AVI？
>> 观众：上一页 - >下一个？
>> JASON HIRSCHHORN：上 - >下一个是什么 我们要更新，因为这
实际上在插入 该列表的末尾。
我们仍然有一个缺陷，不过， 那我们要碰上。
那是什么错误？
是吗？
>> 观众：这将返回 假在这种情况下？
>> JASON HIRSCHHORN：哦，是的 要返回false。
但还有一个问题。
所以，我们需要把返回true。
>> 观众：以前还是否相等 在列表的顶部空？
>> JASON HIRSCHHORN：所以以前仍 等于null在开始的时候。
那么，如何才能克服呢？
是吗？
>> 观众：我觉得你可以做一个检查 前while循环，看它是否是
一个空的列表。
>> JASON HIRSCHHORN：确定。
因此，让我们去这里。
做一个检查。
如果 -
>> 观众：所以，如果头 等于等于null。
>> JASON HIRSCHHORN：如果头 等于等于null -
这会告诉我们，如果它是一个空列表。
>> 观众：然后你 做头等于新的。
>> JASON HIRSCHHORN：头 等于new_node？
还有什么我们需要做什么？
>> 观众：然后你返回true。
>> JASON HIRSCHHORN：不太。
我们缺少的一个步骤。
>> 观众：New_node未来 有指向空。
>> JASON HIRSCHHORN：没错，奥尔登。
然后我们就可以返回true。
确定。
但它仍然是一个好主意，做的事情 在列表的最后，对不对？
好的。
我们仍然可能真正得到 到该列表的末尾。
因此，这是代码罚款，如果我们在 列表结束，还有一些
列表中的东西呢？
对不对？
因为我们还有马库斯的想法。
我们可能会退出这个循环，因为 我们在列表的末尾。
所以，我们还是希望这 这里的代码了吗？
>> 观众：是的。
>> JASON HIRSCHHORN：是啊。
什么我们需要改变这？
真的。
这听起来不错 大家这么远吗？
任何人有任何 -
AVI，你有什么要补充的吗？
>> 观众：号
>> JASON HIRSCHHORN：确定。
因此，我们已经做了一些改动。
我们已经我们之前做这个检查 在去为一个空列表。
因此，我们采取了一个空列表的照顾。
在这里，我们把插入的护理 一些在列表的末尾。
因此，它似乎是这个while循环回吐 处理后事之间，
某处在列表中，如果有 在列表中的东西。
>> 确定。
让我们再次运行这个程序。
没有成功。
>> 观众：你没能成功。
>> JASON HIRSCHHORN：哦， 我没有做它。
好点，迈克尔。
让我们添加链接的化妆。
第87行有一个错误。
第87行。
奥尔登，这是你给我就行了。
什么是错的？
>> 观众：它必须为null。
>> JASON HIRSCHHORN：优秀。
完全正确。
它应为null。
让我们再次做。
编译。
确定。
让我们来插入三个。
该插入是成功的。
让我们把它打印出来。
哦，如果我们能检查。
但我们没有这样做的 但打印功能。
让我们进入别的东西。
我们应该怎样输入？
>> 对象：七。
>> JASON HIRSCHHORN：七？
>> 观众：是的。
>> JASON HIRSCHHORN：我们有一个赛格故障。
因此，我们得到了一个，但我们清楚地 不能得到两个。
它是5:07。
这样我们就可以调试这个 三分钟。
但我要离开这里，我们 并移动到哈希表。
但同样，答案这个代码 我将通过电子邮件发送给您的一点。
我们非常接近它。
我强烈鼓励你找出 这是怎么回事，并解决它。
所以我会向您发送电子邮件将该代码作为 加上良好的解决方案 -
提供可能的解决以后。
首先这个代码。
>> 另一件事我想我们以前做的 终点是我们还没有释放任何东西。
所以我想告诉你什么 Valgrind的样子。
如果我们运行Valgrind的边界 在我们的节目，。/挂钩。
再次，根据这张幻灯片，我们 应与某些类型的Valgrind的运行
选项​​，在这种情况 - 泄漏检查=满。
因此，让我们写的valgrind - 泄漏检查=满。
因此，这将运行Valgrind的 在我们的节目。
而现在的程序实际运行。
所以，我们要运行它，就像 之前，把东西英寸
我打算把三个。
这一工程。
我不会尝试把某事 别的，因为我们要
得到在这种情况下一个段错误。
所以我只是要退出。
>> 现在你看到这儿 泄漏和堆总结。
这些都是好东西， 你想看看。
因此堆汇总 - 它说，在使用 在出口 - 在一个块中8个字节。
一个块是 节点我们malloced。
Michael，你说一个节点是前八 叮咬，因为它具有整数
和指针。
所以这是我们的节点。
然后它说，我们使用的malloc 七次，我们释放
东西六次。
但我们从来没有所谓的自由，所以我没有 知道这是什么说什么。
>> 但我只想说，当你的 程序运行时，malloc的是被称为
在其他一些地方，我们 不必担心。
所以malloc的可能是所谓的 在一些地方。
我们并不需要担心的地方。
但是，这真的是我们。
这第一行是我们。
我们离开了该块。
而且你可以看到，这里 在泄漏概要。
仍可达 -
在一个块中8个字节。
这意味着，存储器 -
我们已经泄露内存。
肯定丢失了 -
有些东西失去了为好。
一般来说，你不会 看不到任何东西在那里。
仍然是可到达的地方一般 你会看到的东西，在那里你会想
看看，看看代码你应该 已释放，但你忘了释放。
>> 然后，如果这是不是这种情况， 如果我们做了免费的一切，
我们可以检查。
让我们只运行程序 不把任何东西。
你会看到这儿使用在出口 -
在零块零字节。
这意味着我们已经一无所有 当这个程序退出。
所以，在转弯前pset6，运行Valgrind的 并确保你没有
任何内存泄漏的程序。
如果您有Valgrind的任何问题， 随意伸手。
但是，这是你如何使用它。
很简单 - 看看你 有在使用中退出 -
在任何阻止任何字节。
>> 所以，我们正在努力插入节点上。
我有其他两个函数在这里 - 打印节点和自由节点。
再次，这些功能是 将是对你有好处练习
因为他们会帮你不仅 这些样品的练习，但也
关于这个问题集。
他们非常紧密映射到的东西 你将要做的
问题集。
但我想，以确保 我们接触的一切。
和哈希表也是至关重要的 我们正在做的这节
星期 - 或在习题集。
>> 所以，我们要完成的部分 谈论哈希表。
如果您发现我犯了一个 小哈希表。
这不是我们所谈论 但是，关于。
我们谈论的是一个不同的 类型的哈希表。
并在其核心，一个哈希表 是不是仅此而已
阵列加一个散列函数。
我们要谈的一点只是为了 确保每个人都明白一个
散列函数是。
而我现在告诉你，这是 无非两件事 -
数组和散列函数。
和这里的步骤，通过 而这个操作。
>> 还有我们的数组。
还有我们的函数。
特别是，散列函数需要 做了几件事情与此有关。
我要特别谈谈 关于这个问题集。
它可能会 走在一个字符串。
和什么样了回来？
是什么数据类型？
奥尔登？
您的散列函数返回？
一个整数。
原来这就是散列 表由 -
在阵列形式的表 和散列函数。
它是如何工作的？
它的工作分三个步骤。
我们给它一个关键。
在这种情况下，我们给它一个字符串。
我们每步1调用哈希函数 对关键，我们得到的一个值。
>> 具体来说，我们会说 我们得到的整数。
该整数，也有非常具体的 限制到什么是整数都可以。
在这个例子中，我们的阵 是大小三。
因此，可以认为整数是什么数字。
什么是有效值范围 该整数，这个返回类型
散列函数？
零，一和二。
散列函数的一点是要 找出该数组中的位置
在那里我们的关键是怎么回事。
只有三种可能 地方在这里 -
零个，一个或两个。
所以这个功能更好的回报 零个，一个或两个。
此数组中一些有效的指数。
>> 然后不同的地方返回， 你可以看到有数组开放
括弧中的值。
这就是我们把钥匙。
所以我们扔在南瓜， 我们得到了零。
在阵列支架0，我们把南瓜。
我们扔在猫，我们走出之一。
我们把猫的之一。
我们把蜘蛛。
我们得到了两次。
我们把蜘蛛在阵列上的两个。
这将是很好，如果 它的工作就像那个。
但不幸的是，正如我们将看到的， 这是一个比较复杂一点。
>> 在我们那里，任何问题 关于这个基本
建立一个哈希表？
这是确切的图像 我们画在黑板上。
但由于我们画在黑板上，我 我不打算再进入它。
从本质上讲键，神奇的黑盒子 - 或者在这种情况下，深青色盒 - 一个
散列函数把它们放在水桶。
而在这个例子中，我们是 不把这个名字。
我们把相关的电话 名称中的桶数。
但你很可能只是 把名字中的水桶。
>> 这是什么只是一个图片 我们画在黑板上。
我们有潜在的隐患，虽然。
而且有两个特别 幻灯片，我想去过。
第一个是对 散列函数。
所以我问的问题，什么 做一个好的哈希函数？
我给出两个答案。
首先是它的确定性。
在哈希函数的情况下， 这是什么意思？
是吗？
>> 观众：它可以找到 指数在常数时间？
>> JASON HIRSCHHORN：那 是不是这个意思。
但是这是一个很好的猜测。
别人有一个猜想 到这意味着什么？
一个好的哈希函数 是确定的？
安妮？
>> 观众：那一个键只能映射 哈希表在同一个地方。
>> JASON HIRSCHHORN：这是 完全正确。
每当你把南瓜， 它总是返回零。
如果你把南瓜和您的散列 函数返回零，但有一个
返回的东西概率 其他大于零 -
所以也许它可以返回人们有时 或其他两次 -
这不是一个好的哈希函数。
你说得对。
您的散列函数应该返回 完全相同的整数，在这种情况下，为
完全相同的字符串。
>> 也许它会返回完全相同的整数 对于完全相同的字符串
不分大小写的。
但在这种情况下，它仍然 确定性，因为多东西
被映射到相同的值。
这很好。
只要仅有一个 输出对于一个给定的输入。
>> 确定。
第二件事是，它 返回的有效索引。
我们长大了前面。
该散列函数 -
男孩哦 -
散列函数应该 返回的有效索引。
所以说 -
让我们回到这个例子。
我的散列函数计数 字母的单词。
这就是散列函数。
并返回该整数。
所以，如果我有A字，它的 要返回之一。
并且它会放一个就在这里。
如果我把这个词蝙蝠？
这将返回三个。
哪里蝙蝠去了？
>> 它不适合。
但它需要去的地方。
这是我的哈希表毕竟，和 一切都需要去的地方。
那么，应该蝙蝠去了？
有什么想法？
猜测？
良好的猜测？
>> 对象：零。
>> JASON HIRSCHHORN：为什么零？
>> 观众：因为3 模三是零？
>> JASON HIRSCHHORN：三 模3是零。
这是一个伟大的猜想， 这就是正确的。
因此，在这种情况下，它应该 大概走为零。
所以一个好的方法，以确保此哈希 函数只返回有效索引的
由该表的大小以模它。
如果通过模本的任何回报 3，你总是会得到
零个，一个，和2之间的东西。
如果这个总是返回七人， 你总是模三个人，你是
总是会得到同样的事情。
>> 所以它仍然确定性 如果你取模。
但是，这将确保您 从来没有得到的东西 -
无效的行业。
通常，模应该发生 您的哈希函数里面。
所以，你不必担心这一点。
你只要能保证 这是一个有效的指数。
这方面的问题 潜在的缺陷？
>> 确定。
我们在那里去。
下一个潜在的缺陷，并 这是大的。
如果哪两个键地图 为相同的值？
因此，有两种方法来处理这​​个问题。
第一个被称为线性 探测时，我敢
不打算走了过来。
但是你应该熟悉如何 的作品，这是什么。
>> 第二个我打算走了过来 因为这是一个多
人们可能会最终决定 在他们的问题集中使用。
当然，你不必。
但对于习题集，很多人 倾向于选择创建一个哈希表
有独立的链接来实现 他们的字典。
所以，我们要投奔这是什么意思 创建一个哈希表
单独的链接。
>> 所以我把南瓜。
它返回零。
我把南瓜在这里。
然后我把 -
什么是另一个万圣节为主题的东西吗？
>> 观众：糖果。
>> JASON HIRSCHHORN：糖果！
这是一个伟大的。
我把糖果和糖果 也使我为零。
我该怎么办？
任何想法？
因为那种大家都知道 什么单独的链接是。
因此，任何想法怎么办？
是啊。
>> 观众：把字符串 实际上哈希表中。
>> JASON HIRSCHHORN：所以我们要 绘制好主意在这里。
确定。
>> 观众：有哈希表 [听不清]
指向指针 一个列表的开头。
然后有南瓜是第一值 在链表和糖果是
在该链表中的第二个值。
>> JASON HIRSCHHORN：确定。
马库斯，这是优秀的。
我要打破下来。
马库斯是说不要 覆盖南瓜。
这将是坏。
不要把糖果别的地方。
我们打​​算把两者为零。
但我们要处理 这使他们由零
创建列表为零。
我们要创建的列表 一切映射到零。
我们学会了创造的最佳方式 可以增长和收缩的清单
动态不在 另一个数组。
所以不是一个多维数组。
但只创建一个链表。
>> 那么，他提出 -
我会得到一个新的 -
是创建一个指针数组， 的指针数组。
确定。
任何想法或暗示的是什么类型的 这个指针应该是什么？
马库斯？
>> 观众：指针来 -
>> JASON HIRSCHHORN：因为你 说一个链表，所以 -
>> 观众：节点的指针？
>> JASON HIRSCHHORN：节点的指针。
如果东西在我们的链接 列表是节点，那么他们
应该是节点的指针。
又哪里等于最初？
>> 观众：空。
>> JASON HIRSCHHORN：空。
所以这是我们的空的东西。
南瓜返回零。
我们该怎么办？
通过它走我吗？
其实，马库斯已经给了我。
别人走我走过它。
我们做什么，当我们 -
这看起来非常相似， 我们只是在做。
阿维。
>> 观众：我要去参加一个猜测。
所以，当你得到糖果。
>> JASON HIRSCHHORN：是啊。
好了，我们得到了南瓜。
让我们得到我们的第一个。
我们得到了南瓜。
>> 观众：确定。
南瓜返回零。
所以你把它放在那。
或者实际上，你把它 在链表。
>> JASON HIRSCHHORN：我们如何 把它放在链表？
>> 观众：呵呵，实际的语法？
>> JASON HIRSCHHORN：只是走 -
多说了。
我们该怎么办？
>> 观众：你刚才插入 它作为第一个节点。
>> JASON HIRSCHHORN：确定。
因此，我们有我们的节点，南瓜。
现在我怎么插入？
>> 观众：你分配 它的指针。
>> JASON HIRSCHHORN：哪个指标？
>> 观众：零指针。
>> JASON HIRSCHHORN：那么， 确实这一点呢？
>> 观众：为NULL现在。
>> JASON HIRSCHHORN：嗯， 它指向空。
但我把南瓜。
那么，它应该指向？
>> 观众：南瓜。
>> JASON HIRSCHHORN：南瓜。
没错。
所以这个指向南瓜。
并在执行此指针 在南瓜呢？
至
>> 观众：空。
>> JASON HIRSCHHORN：为NULL。
没错。
所以我们刚才插入的东西 成该链接的表。
我们只是写了这个代码来做到这一点。
几乎我们几乎得到了它 完全破解。
现在我们插入的糖果。
我们的糖果也变为零。
所以，我们做糖果什么？
>> 观众：这取决于是否 不是我们试图对它进行排序。
>> JASON HIRSCHHORN：这是 完全正确。
这取决于是否不 我们正在试图对它进行排序。
让我们假设我们不是 要排序。
>> 观众：那么，正如我们所讨论 之前，它最简单的只是把它
在一开始使指针 从零点到糖果。
>> JASON HIRSCHHORN：确定。
坚持住。
我创建的糖果就在这里。
所以这个指针 -
>> 观众：是啊，现在应该 是指向糖果。
再有从指针 糖果点南瓜。
>> JASON HIRSCHHORN：像这样？
并说我们得到了另一个 东西映射到零？
>> 观众：嗯，你只是 做同样的事情？
>> JASON HIRSCHHORN：做同样的事情。
所以在这种情况下，如果不 要保持它整理了
听起来相当简单。
我们带指针的指数 我们的哈希函数由下式给出。
我们有一点我们的新节点。
然后不管它是指向 以前 -
在这种情况下空，在 第二种情况南瓜 -
，不管它的指向 以前，我们添加到下一个的
我们的新节点。
我们要插入一些 在开始。
事实上，这是不是简单多了 试图保持列表排序。
但同样，搜索会 更复杂的在这里。
我们总是要走到最后。
>> 确定。
关于单独的链接有问题吗？
该怎么做？
请立即问他们。
我真的想确保你的所有 明白这一点之前，我们把头伸出。
>> 观众：你为什么把南瓜 和糖果到相同的
哈希表的一部分？
>> JASON HIRSCHHORN：好问题。
为什么我们把它们放在同一个 哈希表的一部分？
那么，在这种情况下，我们的散列函数 返回零为他们两个。
因此，他们需要去的指数为零 因为这就是我们要
找他们，如果我们曾经 想看看他们。
再次，用线性探测方法 我们不会把他们两个零。
但在不同的链方法， 我们打​​算把他们两个零
然后创建一个列表销为零。
>> 我们不希望覆盖南瓜 只是对于因为那时我们将
假设是南瓜 从来没有插入。
如果我们只是一味地一件事在 这将是坏的位置。
那么就没有 我们曾经的机会 -
如果我们曾经有一个重复的，那么我们 只会抹掉我们的初始值。
所以这就是为什么我们这样做的方法。
或者，这就是为什么我们选择了 - 但同样，我们 选择了不同的链接方式，
它还有许多其他的方法 人们可以选择。
这是否回答你的问题？
>> 确定。
卡洛斯。
线性探测将涉及 -
如果我们发现了一个碰撞为零，我们 看起来在一个景点，看是否
它是开放的，并把它放在那里。
然后我们来看看在未来的体育和 看看是否是公开的，把它放在那里。
因此，我们发现下一个可用的 开放式现场，把它放在那里。
还有没有其他问题？
是啊，AVI。
>> 观众：作为一个跟进的是， 你是什​​么下一个景点是什么意思？
在哈希表或链表。
>> JASON HIRSCHHORN：对于线性 编程，无链表。
哈希表上的下一个点。
>> 观众：确定。
因此，哈希表会 初始化为大小 -
像串数 你被插入？
>> JASON HIRSCHHORN：你会 希望它是真正的大。
是。
这里就是我们的图片 只是画在黑板上。
再次，我们有一个碰撞就在这里。
在152。
你会看到我们创建 链表关闭它。
再次，哈希表单独链接 做法是不是你
要为设置问题 6不过是一个很多
学生倾向于采取。
所以，关于这一点，让我们简要谈 之前，我们把头伸出约问题6，
然后我会跟大家分享一个故事。
我们有三分钟。
>> 问题组六。
你有四个功能 -
负载，检查，尺寸和卸载。
负载 -
好了，我们已经去 过载刚才。
我们画了负载在黑板上。
我们甚至开始编码了很多 插入一个链表。
所以负载不大于多 我们刚才一直在做。
>> 入住的是，一旦你有 装的东西。
这是相同的过程，因为这。
在那里你把相同的前两部分 事到哈希函数
并获得其值。
但是现在我们还没有插入。
现在，我们正在寻找它。
我的示例代码写的寻找 东西在一个链表。
我鼓励你练习了。
但直觉发现的东西是 非常类似于插入的东西。
事实上，我们发现画的图片 东西在一个链表，移动
通过直到你到了年底。
如果你到了结束，不能 找到它，那么它不存在。
所以这是支票，基本上。
>> 下一个是大小。
让我们跳过大小。
最后，你已经卸载。
卸载是我们还没有得出 在董事会或编码呢。
但我鼓励你去尝试它的编码 在我们的样本链表的例子。
但直觉上卸载 类似于自由 -
或者我的意思是类似的检查。
除了现在每次你要时间 通过，你不能简单地检查，
看看你是否有你的价值在那里。
但你服用的节点， 释放它，基本上。
这就是卸载要求你这样做。
免费一切你malloced。
所以，你经历了整个名单 再次，要通过整个哈希
表一次。
这个时候不检查 看看那里的东西。
刚解放那里的东西。
>> 终于大小。
大小应该得到实施。
如果不实现规模 -
我会说像这样。
如果你没有在完全相同实现规模 一行代码，包括
return语句，你是 不正确地做大小。
因此，请确保大小，完整的设计 点，你做的只有一个
行代码，其中包括 return语句。
>> 并且不收拾然而，Akchar。
做事勤奋。
我想说谢谢你们 前来部分。
有一个快乐的万圣节。
这是我的服装。
我会在周四穿着这 如果我看到你在上班时间。
如果您想了解更多一些 背景为这件衣服，觉得
免费检查出2011条 关于为什么我一个故事
穿着南瓜服装。
它是一个悲伤的故事。
所以一定要确保你有 附近的一些组织。
但是，如果您有任何 的问题，我会坚持围绕
后段之外。
祝你好运问题组六。
和往常一样，如果您有任何 的问题，让我知道。