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条 关于为什么我一个故事 穿着南瓜服装。 它是一个悲伤的故事。 所以一定要确保你有 附近的一些组织。 但是,如果您有任何 的问题,我会坚持围绕 后段之外。 祝你好运问题组六。 和往常一样,如果您有任何 的问题,让我知道。