[音乐播放] 戴维·J·马兰：好吧。 这是CS50。 这是本周五继续进行，我们 有一些好消息和一些坏消息。 好消息是，CS50 推出这个星期五。 如果您想加入我们的行列， 前往这里平时的网址。 更好的消息，没有演讲 下星期一13日。 略显不足更好的消息， 测验零点下周三。 更多细节可 在这个网址找到这里。 而在接下来的几天 我们将填补空白 与问候房间 我们将有保留。 更好的消息是，有将 是一个过程性的检讨 会议即将来临 周一晚上。 敬请关注过程的 网站的定位和细节。 部分，即使它是一个 假期，也将满足为好。 最好的消息，讲课下周五。 因此，这是一个传统，我们 有，按照教学大纲。 只是 - 这将是惊人的。 你会看到类似的东西 固定时间的数据结构 和哈希表和树和尝试。 我们将谈论的生日问题。 一大堆的东西 等待下周五。 行。 总之。 所以，记得，我们已经 重点是这幅画的是什么 我们内部的计算机内存。 这样存储器或RAM是其中的程序 你正在运行他们，而存在的。 如果你双击一个 图标来运行一些程序 或双击 图标打开某些文件， 它是从硬盘加载 驱动器或固态驱动器 到RAM中，随机存取存储器，其中 它生活，直到电源关闭， 笔记本电脑的盖子关闭， 或者你退出程序。 现在，记忆， 你可能有 1 GB的这些天，2 千兆字节，甚至更多， 一般布局 对于一个给定的程序 在这种长方形的 概念模型 由此我们有堆叠在底部 并在顶部一堆其他的东西。 在最高层的事 我们已经看到这个画面 之前，但从来没有说过 是所谓的文本段。 文段仅仅是一个奇特的方式 的话说，零和一的 撰写您的实际编译的程序。 所以，当你双击 微软的Word在您的Mac或PC， 或者当您运行点斜线马里奥在 Linux计算机在终端窗口中， 构成该零和一 字或马里奥被暂时存储 在所谓的计算机的RAM 文本段对特定的程序。 下面说去初始化 和未初始化的数据。 这东西像全局变量， 我们已经不能用了许多， 但有时，我们已经 有全局变量 或静态定义的字符串 是硬编码，如“你好”的话 未从用户采取 被硬编码到程序中。 现在，倒在底部我们 有所谓的堆栈。 和栈，迄今为止，我们已经 采用了什么样的目的？ 什么是栈被用来做什么？ 是吗？ 听众：功能。 戴维·J·马兰：功能？ 在什么意义上的功能呢？ 听众：当你调用一个函数时， 参数复制到堆栈中。 戴维·J·马兰：没错。 当你调用一个函数，它的 参数复制到堆栈中。 因此，某X的或Y的或A或B的 那你传递给函数 暂时放在 所谓堆栈， 就像安尼伯格之一 食堂托盘，也事 如局部变量。 如果你的富功能或您的交换 函数有局部变量， 如温度，这两个 最终在堆栈中。 现在，我们不会过多谈论 他们，但这些环境变量 在底部，我们看到前一段时间，当 我把玩在键盘1天 我开始访问事 像argv的100 ARGV 1,000 只是elements--我忘了 在numbers--但 不应该由我来访问。 我们开始看到一些 时髦的符号在屏幕上。 这些都是所谓的 环境变量 像全局设置我的 程序或我的电脑，而不是 无关的最近 错误，我们所讨论的， Shellshock，这一直 困扰着不少电脑。 现在，最后，在今天的重点 我们最终会在堆中。 这是记忆另一个块。 从根本上这一切 内存是同样的东西。 这是同样的硬件。 我们只是有点 对待不同的集群 的字节用于不同的目的。 堆也将会是在哪里 您请求的变量和内存 从操作系统 被暂时存储。 但有样的问题 这里，作为图像暗示。 我们的排序有两个 关于船舶碰撞。 因为当你使用越来越多 堆栈，并作为我们今天看到的 以后，当你使用更多的多 堆，肯定不好的事情可能会发生。 事实上，我们可以归纳出 有意或无意的。 所以最后扣人心弦 时间是这个程序， 这并没有起到任何功能 目的除了展示 如何为坏家伙竟然可以 利用漏洞在别人的程序 并接管程序，甚至是 整个计算机系统或服务器。 所以只是简单地一瞥，你 请注意，主底部 需要在命令行 参数，按ARGV。 它有一个调用一个函数f， 基本上叫做匿名函数 f和它传递的argv [1]。 因此，在任何字的用户类型 这个节目的名字后，在提示， 然后这个任意函数了 顶，F，需要一个字符串，又名char *的， 因为我们已经开始讨论， 它只是将其称为“巴”。 但我们可以把它叫做什么。 然后它声明，里面 楼字符数组的 所谓C-- 12这样的人物。 现在，这个故事我告诉 刚才，在内存 为c，或者是那些12 字符要结束了？ 只是要清楚。 是吗？ 听众：在堆栈中。 戴维·J·马兰：在堆栈中。 所以C是一个局部变量。 我们要求12个字符或12个字节。 那些将要结束了 在所谓的堆栈。 现在终于这等功能 这实际上是相当有用的， 但我们还没有真正使用 它自己，strncopy。 这意味着字符串拷贝，但 n只有字母，n个字符。 因此，n个字符会 从酒吧复制成C。 又有多少呢？ 条的长度。 因此，换句话说，即 一条线，strncopy， 将要复制 在有效的禁止到c。 现在，只是一种预测 这个故事的寓意， 什么是潜在的问题在这里吗？ 尽管我们正在检查的长度 酒吧，并向其传递到strncopy， 什么是你的直觉告诉你的是 还是打破这个计划？ 是吗？ 听众：不包括 房间空字符。 戴维·J·马兰：不包括 房间空字符。 潜在地，不像在 过去的实践中，我们甚至不 有这么多的加1 容纳空字符。 但比这更糟糕。 还有什么是我们不能做什么？ 是吗？ 听众：[听不清] 戴维·J·马兰：完美。 我们已经硬编码的12相当随意。 这是没有这么多的 的问题，但事实 我们甚至不检查，如果 条的长度是小于12， 在这种情况下，这将是 安全地把它放入内存 我们已经分配名为c。 事实上，如果酒吧是像 20个字符长， 这个功能似乎被复制 从酒吧到C，使20个字符 服用至少8个字节 它不应该。 这是这里的含义。 因此，在短期，断程序。 没有什么大不了的。 也许你会得到一个段错误。 我们都有过在程序中的bug。 我们都可能有缺陷 在节目现在。 但是，有什么寓意？ 嗯，这里是一个放大版本 那张照片是我的电脑的内存中。 这是我的堆栈的底部。 事实上，在最底层是什么 所谓的母常规堆栈，奇特的方式 的话说，就是主。 所以，无论谁调用的函数 ˚F，我们正在谈论的。 所以这是堆栈的底部。 返回地址是新的东西。 这是一直存在的， 一直在图片。 我们只是从来没有所谓的重视。 因为事实证明，C工作的方式是 当一个函数调用另一个， 不仅做到了参数的 功能得到压入堆栈， 不仅做到了功能的地方 得到的变量压入堆栈， 一些所谓的返回地址 也被放到堆栈。 特别是，如果主调用f​​oo，主要的 自己的地址在内存中，牛事， 有效地被放置到堆栈 这样，当f为完成执行它 知道在哪里可以跳回到文本 段，以继续执行。 所以，如果我们在这里概念， 在主，则f被调用。 如何˚F知道是谁 以手控回来？ 好了，这个小 面包屑红色在这里， 所谓的返回地址，这只是 支票，那是什么的返回地址？ 哦，让我跳回到主这里。 这就是一点点 过于简单化的， 因为在零和一 主在技术上 在这里，在高科技领域。 但是，这是这个想法。 ˚F 只是必须知道什么 到控制，最终又回到。 但是，电脑的方式 早就奠定了东西 如局部变量和 论点是这样的。 所以，在这张照片中名列前茅 蓝色是在f的栈帧，因此所有 存储器的使f 特别是使用。 所以因此，请注意 酒吧是在这张照片。 酒吧是它的参数。 我们宣称的参数 功能得到压入堆栈。 和c，当然是 同时在这张照片。 而就在符号上的目的， 注意在顶部左上角 是会什么C支架0 随后小幅回落向右 为c支架11。 所以，换句话说，你可以想像 这有一个字节格 还有，第一个是 左上角，底部其中 是最后的这12个字节。 但现在尽量快进。 什么是即将发生，如果我们通过 在一个字符串中的酒吧，是比C更久？ 而且我们不是，如果检查 这的确是超过12。 此图片的一部分是要 得到由字节0，1，2，3覆盖， 点点点，11，然后 糟糕，12，13至19？ 什么会发生在这里， 如果从订货推断 将c支架0顶部 和c支架11是有点下降 对吧？ 是吗？ 听众：嗯，这是怎么回事 覆盖char *的吧。 戴维·J·马兰：是的，它看起来像 你要覆盖char *的吧。 更糟糕的是，如果你发送一个很长的 字符串，你甚至可以覆盖哪些？ 返回地址。 这再次，就像是 面包屑告诉程序在哪里 在f回去 完成被调用。 那么，什么坏人通常做 是，如果他们遇到一个程序 他们很好奇是否 利用，越野车以这样的方式 他或她可以利用 优点是错误的， 一般他们没有得到 这种权利的第一次。 他们刚开始发送，例如， 随机字符串到你的程序， 是否在键盘 或者坦白地说，他们可能 写一个小程序只是 自动生成的字符串， 并开始通过敲打你的程序 派遣在许多不同的输入 在不同的长度。 只要你的程序崩溃， 这是一个了不起的事情。 因为这意味着他 或她已经发现 什么是可能的确是一个错误。 然后，他们可以得到更聪明 并开始关注更窄 如何利用这个bug。 特别是，他或她可能 要做的就是发送，在最好的情况下，你好。 没什么大不了的。 这是一个字符串，它是足够短。 但是，如果他或她送什么， 我们将其概括为， 攻击代码 - 让零 而那些做的事情 如RM-RF，即去除一切 从硬盘驱动器或发送垃圾邮件 或以某种方式攻击机？ 因此，如果每个这些 字母A代表公正， 从概念上讲，攻击，攻击， 攻击，攻击，一些不好的代码 别人写的，但 如果那人是足够聪明 不仅包括所有 那些RM-RFS的，但也 有他或她的最后几个字节 是一个数字，对应 到的地址他 或她自己的攻击代码 他（或她）在刚刚过去的 在提示符下提供的， 可以有效地欺骗电脑 为在f执行完毕注意到， 哦，是时候让我跳 回红返回地址。 但是，因为他或她有莫名其妙 重叠的返回地址 用自己的号码， 而且他们足够聪明 已配置的 数量是指，当你 看到超级顶 左上角有， 在计算机的实际地址 他们的一些攻击代码的内存， 坏人可以欺骗计算机 为执行他或她自己的代码。 而这些代码，再次可以是任何东西。 它通常被称为 shell代码，这仅仅是 的话说，这不是一个办法 通常一些简单的RM-RF。 它实际上是这样猛砸， 或实际的方案，让他 或她的程序控制执行 别的，他们想要。 因此，在短期，这一切 从一个简单的事实推导出 这个错误不涉及检查 阵列的界限。 而由于道路 计算机工作，他们 使用堆栈 有效的，在概念上， 底上了，但随后的元素 你推入堆栈增长自上而下， 这是令人难以置信的问题。 现在，有方法可以解决这个问题。 坦率地说，有语言 与合作解决这个问题。 Java是免疫，例如 这个特定问题。 因为他们不给你指点。 他们不给你 直接内存地址。 因此，与这种力量，我们有 在内存按兵不动 我们要来了，诚然，巨大的风险。 所以留意。 如果坦率地说，在未来数月 或几年来，随时 你读一些开发 中，一个程序或服务器 如果你曾经看到的东西的提示 就像一个缓冲区溢出攻击， 或堆栈溢出是另一种类型 攻击中，在精神上同样， 就像激发网站的 名字，如果你知道的话， 这一切都在谈论刚刚 满溢一些字符的大小 数组或数组中更普遍。 有任何疑问的话，在这？ 不要在家里尝试。 好吧。 所以malloc的迄今，我们的新 朋友，我们可以分配内存 我们不一定知道在 前进，我们希望让我们没有 硬编码到我们的 程序号像12。 一旦用户告诉我们有多少 数据他或她想要输入 我们的malloc那么多的记忆。 所以malloc的事实证明，在 程度上，我们一直在使用它， 明确地一次，然后 你们一直在使用它 为的GetString在不知不觉中进行 数周后，所有的malloc的内存的 来自于所谓的堆。 这就是为什么GetString的，例如 可以动态地分配内存 不知道你在做什么 将预先输入， 交给你回一个指向内存中， 而且内存还是你留着， 即使在形式返回。 由于召回毕竟该 堆栈是不断上升和下降， 向上和向下。 而一旦它进入 下，这意味着任何存储器 这个功能应该使用 不被其他人使用。 这是垃圾值了。 不过，堆在这里。 这有什么好看的malloc左右是 当这里的malloc分配内存时， 它没有影响，对 大多数情况下，由堆栈。 所以任何函数都可以访问 内存已malloc分配， 甚至像的GetString函数， 即使在它被返回。 现在，的malloc的逆是免费的。 事实上，规则你 需要开始采用 就是有，有，你用malloc任何时间 你必须自己使用免费的，最终， 在同样的指针。 这段时间我们一直在写 越野车，越野车的代码，有很多原因。 但其中一个已 使用CS50库， 本身是故意 越野车，它的内存泄漏。 任何你打电话的GetString时间 在过去的几个星期 我们问工作 系统，Linux的内存。 而你从来没有一次给它回来。 这不，在 练，是一件好事。 和Valgrind的，所述一个 在Pset的4引入的工具， 是所有关于帮助您 现在发现这样的错误。 不过，值得庆幸的是在Pset的4你不需要 使用CS50库或GetString的。 所以涉及到内存中的任何错误都 最终将是你自己。 所以malloc的不仅仅是 方便的用于此目的。 我们其实可以现在解决 从根本上不同的问题， 从根本上解决问题，更 有效地为每周为零的承诺。 到目前为止，这是最性感 数据结构，我们已经有。 并通过数据结构我的意思 概念化记忆的一种方式 在超越只是说一种方法， 这是一个int，这是一个字符。 我们可以开始集群的东西放在一起。 所以数组是这样的。 什么是对的关键 数组是可以让你 备份到后端的块 存储器，其中每个 将是相同的类型，整型， 整型，整型，整型，或CHAR，CHAR，CHAR， 字符。 但是有几个缺点。 此，例如，是 大小6的阵列。 假设你填充这个数组六 数字，然后，不管是什么原因， 您的用户想要得到 你第七号。 你在哪里放呢？ 有什么解决办法，如果你有 在堆栈上创建一个数组， 例如，刚与周 2符号，我们介绍了， 方括号与多家里面？ 好了，你已经有了6 在这些框中的数字。 什么你的直觉是什么？ 在那里你会想要把它？ 听众：[听不清] 戴维·J·马兰：对不起？ 听众：把它放在最后。 戴维·J·马兰：把它放在最后。 所以才过来的吧， 这个盒子的外面。 这将是很好的，但它 事实证明，你不能这样做。 因为如果你没有问 此块的存储器， 这可能是巧合，这 正在使用的一些其它变量 干脆。 回想一个星期左右的时候，我们奠定 出Zamyla和达文和Gabe的名字 在存储器中。 他们从字面上 回背靠背。 所以我们可以不必 相信凡是 在这里是供我使用。 所以，你还有什么可以做？ 那么，一旦你实现 要7号的数组， 你可以只创建一个 尺寸7的阵列，然后使用 for循环或while循环， 将其复制到新的数组， 然后不知何故刚刚摆脱 这个阵列或只是停止使用。 但是，这不是特别有效。 总之，阵列别让 您动态调整。 因此，一方面你 随机访问，这是惊人的。 因为它让我们做的事情 如分而治之， 二进制搜索，所有这些我们已经 就在屏幕上谈到。 但是你画自己陷入了困境。 只要你打 您的阵列的结尾， 你要做的很 昂贵的操作 或写一大堆代码 到现在处理这个问题。 所以，如果不是我们有什么 一些所谓的名单， 或链表特别？ 有如果，而不是 矩形回背靠背， 我们有长方形的留下一点 回旋余地在他们之间有点？ 而且即使我画这个 图片或改编此图片 从文本之一在这里要回 背对背的非常有序，在现实中， 这些矩形之一 可以在这里在存储器中。 其中一人可能是在这里。 其中一人可能是在这里， 在这里，等等。 但是，如果我们画了， 在这种情况下，箭头 不知怎的，这些链接 矩形组合在一起？ 事实上，我们已经看到了技术 化身箭头。 你有没有看到最近使用 天那，引擎盖底下， 是代表一个箭头的？ 一个指针，对不对？ 那么，如果，而不是 只存储该号码 像9，17，22，26，34， 如果我们不保存 只有一些，但指针 相邻的数目？ 所以这就像你会跟帖 针穿过一大堆面料， 不知何故搭售的东西 同时，同样可以 我们使用指针，作为 这里用箭头体现， 种编织在一起 这些单个矩形 通过有效地使用指针 旁边的每个数 指出了一些下一个号码，即 指向，反过来，一些未来数？ 因此，换句话说，什么 如果我们真正想要的 实行这样的事情？ 好可惜，这些矩形， 至少一个与9，17，22， 等等，这些都不再 漂亮的广场单号。 底部，矩形 以下如图9所示，例如， 代表什么应该 是一个指针，32位。 现在，我还不知道任何数据类型 在C中，让你不仅是一个整数 但指针干脆。 那么，有什么解决方案，如果我们想要 去创造我们自己的答案呢？ 是吗？ 听众：[听不清] 戴维·J·马兰：这是什么？ 对象：新的结构。 戴维·J·马兰：是啊，为什么 我们不创建一个新的结构， 或在C中，一个结构？ 我们已经看到结构之前，如果简单地说， 我们处理了一个学生结构 这样，谁的名称和一所房子。 在Pset的3分场您使用了全 一堆structs-- GRect和GOvals的 在斯坦福大学创建的 集群信息一起。 那么，如果我们采取同样的想法 关键字“类型定义”和“结构” 然后一些学生具体的东西， 并演变成以下这样的： typedef结构node--和节点 只是一个很普通的计算机科学 长期的东西，在数据结构中， 容器中的数据结构。 一个节点我要求都将有 一个整数N，完全明了， 然后多一点隐晦， 这第二条线，结构节点*旁边。 但在更短的技术术语， 什么是第二行 的花括号内的代码？ 是吗？ 听众：[听不清] 戴维·J·马兰：一 指针到另一个节点。 所以不可否认，语法有点神秘。 但是，如果你从字面上看它， 接下来是一个变量的名称。 什么是它的数据类型？ 这是一个有点冗长这个时候， 但它的类型结构节点*。 任何我们已经看到一些明星的时候，也 意味着它是一个指针，它指向的数据类型。 因此，下显然是一个 指针指向一个结构节点。 现在，是一个结构的节点？ 好了，请注意您看到的那些 同样的话，在右上角。 事实上，你也看到这个词 “节点”在这儿，在左下角。 这其实只是一个方便。 请注意，在我们学生的定义 有单词“学生”只有一次。 那是因为学生 对象不是自我指涉。 没有什么是学生的内部 需要指向另一名学生， PerSay的。 这将是某种 怪异在现实世界中。 但在一个节点链接 列表中，我们希望有一个节点 是参考了类似的对象。 等注意到这里的变化是不 只是什么花括号内。 但是我们加上“节点” 在顶部，以及 将其添加至底部 代替“学生”。 而这仅仅是一个技术细节 这样一来，同样，你的数据结构 可自行参照，让 节点可以指向另一个这样的节点。 那么，这是什么最终 将意味着我们呢？ 嗯，一，这里面的东西 是我们的节点的内容。 这东西在这里， 右上方，就是这么 即，再次，大家可以参考一下自己。 然后最外面的东西， 即使节点是一个新名词， 也许，它仍然是 一样的学生，什么 在SPL引擎盖下面。 因此，如果我们现在要开始 实施本链表， 怎么可能，我们翻译 像这样的代码？ 好吧，让我们看到一个 例如一个程序的 实际使用链表。 在今天的分销代码 是一个名为List零计划。 如果我运行这个，我创建了一个超 简单的图形用户界面，图形用户界面， 但它真的只是printf的。 现在我已经给自己几个菜单 选项​​ - 删除，插入，检索， 和导线。 并退出。 这是一个公正的常用操作 被称为链接列表数据结构。 现在，删除是要 删除了一些从列表中。 插入件的要加 数到列表中。 搜索是要去看看 对于列表中的号码。 和遍历仅仅是一个奇特的方式 的说法，漫步列表， 它打印出来，但仅此而已。 不要以任何方式改变它。 因此，让我们试试这个。 让我们继续前进，2型。 然后我要去 插入的数目，表示9。 输入。 现在我的计划就是 编程来说，列表是现在9。 现在，如果我继续前进， 不要再插入，让 我继续前进，缩小并输入17。 现在我的名单是9，那么17。 如果我做再次插入，让我们跳过之一。 相反22，按照图片中我们已经 一直在看这里，让我跳跃前进 并插入26下一页。 所以，我要输入26。 这份名单是我所期望的。 但现在，只是如果这个代码见 将是灵活的，现在让我 型22，其中至少有 从概念上讲，如果我们 保持此排序，这确实是 将是另一个目标，现在， 17和26之间应该在。 所以我敲回车。 事实上，工作的。 所以现在让我插入 最后，每个图片，34。 好吧。 所以现在让我规定 删除和遍历和搜索做的， 其实，工作。 事实上，如果我不执行搜索，让我们 搜索次数22，回车。 研究发现22。 所以这就是这个 程序清单零呢。 但实际上会 在实现这一点？ 嗯，首先我可能有，确实 我有一个文件名为list0.h。 而在某个地方有这样的 行，类型定义，结构节点， 然后，我有我的花括号，诠释n和 然后struct--究竟是什么定义？ 结构节点旁边。 因此，我们需要的明星。 现在，技术上我们进入 在这里画的习惯。 你可能会看到课本和 网上参考做那里。 它的功能相当的。 其实，这是一个小更典型。 但我会用什么样一致 我们做了最后的时间，做到这一点。 然后最后，我要做到这一点。 因此，在头文件 某处，在list0.h 今天是这个结构的定义， 也许一些其他的东西。 与此同时，在list0c有 将是一个几件事情。 但是，我们要公正 开始，而不是结束了。 List0.h是我想要的文件 包括在我的C文件。 然后在某个时候，我 将有整型，主要的，无效的。 然后我要去 有一些待办事项在这里。 我也将有一个 原型，如虚空，搜索，INT， N，在生活中，其目的是 要搜索的元素。 再往下这里我要求在 今天的码，无效搜索，INT，N， 别无分号，但开放的花括号。 现在我想以某种方式查询 对于该列表中的一个元素。 但是，我们没有足够的 但在屏幕上的信息。 我没有实际 表示该清单自身。 所以一个方法，我们可以实现 链表的程序 一种是我想要做的事 如声明成链表在这里。 为简单起见，我将做出 这一全球性的，尽管一般我们 不应该这样做太过分了。 但它可以简化这个例子。 所以，我想声明 链表在这里。 现在，我怎么可能这样做呢？ 这里有一个链接列表的画面。 我真的不 知道此刻如何 我打算去代表 只用一个这么多东西 变量在内存中。 但回想一下。 这一切的时候，我们已经有 字符串，我们再 发现是数组 字符，然后我们 显露只是一个指针 到的第一个字符 在字符数组 这是空终止。 所以通过该逻辑，以及与此 图像种类播种的想法， 有什么需要我们在实际编写我们 代码来表示链表？ 如何对这些信息多我们需要 捕捉到的C代码，你会说什么？ 是吗？ 听众：我们需要一个指向一个节点。 戴维·J·马兰：一个指针，指向一个节点。 特别是，该节点将您的 本能是要保持一个指针？ 听众：第一节点。 戴维·J·马兰：是啊， 可能只是第一个。 并注意，第一 节点是不同的形状。 它的结构只有一半的大小， 因为它确实只是一个指针。 那么，你的确可以做的就是声明 链表是类型的节点*。 而且，我们只是先称它为 并把它初始化为null。 所以空，再次，是未来 到这里的画面。 不仅是空作为像一种特殊的 搞什么的GetString返回值 和malloc，空也是零 指针，缺乏一个指针， 如果你愿意。 它只是意味着什么又是在这里。 现在开始，我会一直 所谓的事。 我可以把它叫做“名单” 或任何数目的其他事情。 但我把它称为“第一”，使 这行了这幅画。 所以就像一个字符串可以表示 其第一个字节的地址， 所以可以一个链表。 我们会看到其他数据 结构式来表示 只有一个指针， 一个32位的箭头，指向 在该结构中的第一个节点。 但现在，让我们期待一个问题。 如果我只记得 在我的程序中的地址 第一节点，所述第一 矩形在此数据结构中， 什么最好是对的情况下， 实现我的名单的其余部分？ 那是什么回事的关键细节 为确保这一点的实际工作？ 并通过“实际工作”我 意思是说，就像一个字符串， 让我们从第一个字符去 在达文的名称，以第二， 到第三，对 第四，到了最后， 我们怎么知道，当我们在最后 链表，看起来像这样？ 当它为空。 我已经表示这样的作为 像电​​气工程师可能， 与小接地 各种各样的符号。 但是，这只是意味着在这种情况下空。 您可以绘制任意数量 的方法，但笔者 发生在这里使用这个标志。 只要我们穿线 所有这些节点一起 只记得在哪里 第一个是，只要 当我们把一个特殊符号，在 在列表中的最后节点， 我们将使用空，因为这是 我们必须提供给我们， 该列表已完成。 即使我只给你一个指针 第一个元素，你，程序员， 当然可以访问它的其余部分。 但是，让我们让你的头脑 游荡了一点点， 如果他们不是已经 很wandered--什么 将要的运行时间 发现在这个名单什么？ 该死，这n个大O， 这是不坏，在公平性。 但它是线性的。 我们已经放弃了什么功能 阵列通过移动更多 对这张照片的动态 交织在一起或链接的节点？ 我们已经放弃了随机访问。 数组是不错的，因为 数学上的一切 是背靠背背靠背。 尽管这幅画 看起来很漂亮，甚至 虽然它看起来像这些节点 是很好的分开，在现实中 他们可以在任何地方。 OX1，OX50，Ox123，Ox99，这些 节点可以在任何地方。 因为做的malloc分配内存 离堆，但在任何地方堆。 你不一定知道它的 将是背靠背回来。 所以这幅画在现实中的 不会是今天这样漂亮。 因此，这将需要一些 努力实现这个功能。 现在让我们实现搜索。 我们将看到种类的 这样做的聪明的方式。 所以，如果我是一个搜索功能和 我给一个变量，整数n 寻找，我需要知道的 在里面寻找新的语法 一个结构，是的 指出，为求n。 因此，让我们做到这一点。 所以，首先我会去 未来，并宣布一个节点*。 我要去把它称为 指针，只是约定。 我要去把它初始化为先。 现在我可以做到这一点 在许多方面。 不过，我要采取的共同办法。 而指针不等于 空，这是有效的语法。 它只是意味着做到以下几点，那么 只要你不指着什么。 我该怎么想呢？ 如果指针点N，让我回来 到，equals--等于什么？ 我在寻找什么样的价值？ 这是通过在实际ñ。 因此，这里的另一特色 对C和许多语言。 即使所谓的结构节点 有一个n值，完全合法 也有当地的说法 或者叫变量n。 因为即使我们有 人眼可以分辨 这n是推测 不同于该n。 因为语法是不同的。 你有一个点和一个指针， 而这其中有没有这样的事情。 因此，这是确定。 这是确定的打电话给他们同样的事情。 如果我发现你这个，我是 会想要做的事 像大家宣布，我们发现Ñ。 我们会离开，作为一个 发表评论或伪代码。 否则，和这里的 有趣的部分，是什么 做我想做的事情，如果当前节点 不包含n个我在乎？ 我如何实现以下？ 如果我的手指在 此刻是PTR，它的 指着什么 第一是指向， 如何将我的手指 在代码中的下一个节点？ 那么，什么是我们的面包屑 要在这种情况下，遵循？ 听众：[听不清]。 戴维·J·马兰：是啊，所以下一步。 所以，如果我回到我的 这里的代码，事实上，我 要继续前进，说的指针，这 只是一个暂时的变量 - 这是 一个奇怪的名字，PTR，但 它就像temp-- 我要设置指针 等于任何指针is-- 又一次，这将是一个 小马车的moment--点下一步。 换句话说，我要去把我的 指的是指向该节点 在这里，我想说，你知道 什么，看看下一个字段 移动你的手指 不管它的指向。 并且这将 重复，重复，重复。 但是，什么时候我的手指 停止做了什么呢？ 只要什么码踢行？ 听众：[听不清] 戴维·J·马兰：如果同时点 指针不等于空。 在某些时候，我的手指的 将要指向空 我要去实现 这是该列表的末尾。 现在，这是一个小 善意的谎言的简单性。 事实证明，即使我们 刚刚得知这个点符号 对于结构，指针不是一个结构。 PTR是什么？ 只是要更挑剔。 这是一个指针，指向一个节点。 这不是一个节点本身。 如果我在这里没有明星，指针 absolutely--它是一个节点。 这就好比一个星期 变量声明， 即使单词“节点”是新的。 但只要我们引入了 明星，它现在是一个指针，指向一个节点。 但不幸的是你不能使用 点号的一个指针。 你必须使用箭头 符号，其中，引人注目的是， 是第一次的任何一块 语法看起来直观。 这从字面上看起来像一个箭头。 因此，这是一件好事。 而到这里字面上 看起来像一个箭头。 所以，我认为这是la--我不 想我过犯这里 - ì 认为这是最后的新作品 语法我们要看到的。 而幸运的是，这是真的 多一点直观。 现在，对于那些你们谁 可能更喜欢旧的方式， 你仍然可以使用点号。 但由于每星期一 谈话中，我们首先 需要去那里，去那 处理，然后访问字段。 因此，这也是正确的。 坦率地说，这是一个 有点迂腐。 你从字面上说，提领 指针和去那里。 然后抓住.N，现场叫ñ。 但坦率地说，没有人愿意 打字或阅读。 这样一来，发明了世界 箭头符号，其中 是等价的，相同的， 它只是语法糖。 对这个说法如此看中方式 看起来更好，看起来更简单。 所以现在我要做的一件事。 我会说“休息”一旦我 发现它，所以我不继续寻找它。 但是，这是依据 的搜索功能。 但它是一个容易得多，在 最后，不要穿行的代码。 这的确是正式实施 在今天的分销代码搜索。 我敢说，插不 特别有趣的穿行 在视觉上，也不是删除，甚至 虽然在这一天结束时 他们归结为公平 简单的启发式方法。 因此，让我们做到这一点。 如果你会幽默我在这里，我没有 把一堆压力球。 我带了一堆数字。 而我们能得到的只是一些志愿者 代表9，17，20，22，29和34？ 所以基本上每个人都 谁是今天。 这是一，二，三， 四，五，六人。 我一直在问go--看，没有 一个在后面举手。 好了，一，二，三，四， five--让我加载balance-- 6。 好了，你六上来吧。 我们需要其他人。 我们带来了额外的压力球。 如果你可以， 只是一瞬间，行 自己刚起来 喜欢这幅画在这里。 好吧。 让我们来看看，你叫什么名字？ 听众：安德鲁。 戴维·J·马兰：安德鲁， 你是9号。 很高兴认识你。 干得好。 听众：仁。 戴维·J·马兰：仁。 大卫。 号码17。 是吗？ 听众：我是朱莉娅。 戴维·J·马兰：朱莉娅大卫。 号码20。 听众：基督教。 戴维·J·马兰：基督教，大卫。 号码22。 和？ 听众：日本。 戴维·J·马兰：日本。 号码29。 所以，尽管获得in--嗯哦。 嗯哦。 待机。 20。 有没有人有一个标记？ 听众：我有一个夏普。 戴维·J·马兰：你有夏普？ 行。 并没有任何人有一张纸？ 保存了讲座。 来吧。 听众：我们已经知道了。 戴维·J·马兰：我们得到了它？ 好吧，谢谢你。 开始了。 从你是这样的？ 你刚才化险为夷。 所以29。 好吧。 í拼写错误29，但确定。 前进。 好吧，我给你 你的笔回暂时。 所以我们这些人在这里。 让我们有一个其他的。 加布，你要玩 这里的第一个元素？ 我们需要你来点 这些精美的乡亲。 所以，9，17，20，22，排序 29，然后34。 我们失去了一个人？ 我有一个34。 凡did--确定，谁愿意为34？ 好了，上来吧，34。 好吧，这将是 非常值得的高潮。 你叫什么名字？ 听众：彼得。 戴维·J·马兰：彼得，上来吧。 好吧，那么这里有一个 一大堆的节点。 每次你们都代表 其中的一个矩形。 和加布，稍奇 男人出来，表示第一。 所以他的指针是一个小一点 在屏幕上比其他人。 并且在这种情况下，每个你的左 手是怎么回事要么点下去， 从而表示空值，所以 只是没有指针， 或者它会被人指指点点 在你旁边的一个节点。 所以现在，如果你佩戴 喜欢的图片呀 在这里，继续和点 对方，用加布 在特定的指向 编号9表示的列表。 确定，34号，你的左手 应该只指向地面。 好了，这就是链表。 所以，这是该方案的问题。 事实上，这是代表 一类的问题 你可能会试图解决与代码。 你想最终将 一个新的元素到列表中。 在这种情况下，我们要 请尝试将数字55。 但是，将是 不同的情况来考虑。 事实上，这将是1 的大画面纪要这里，是， 什么是不同的情况。 什么是如果条件或不同 你的程序可能有分支机构？ 嗯，这个数字你要 插入，这是我们现在知道是55， 但如果你不知道 事先，我敢说 落入至少三个 可能出现的情况。 凡可能一个新的元素呢？ 听。结束或中间。 戴维·J·马兰：最后，在 的中间，或在开始时。 所以，我要求有至少 我们需要解决三个问题。 让我们选择什么样的可能 可以说是最简单的 之一，其中该新元素 属于开头。 所以我将有相当代码 如搜索，我只是写。 我要去有PTR，这 我在这里代表我的手指， 照常。 请记住，什么样的价值 我们曾初始化PTR什么？ 因此，我们初始化为null开始。 但后来我们做了一次，我们什么 是我们的搜索功能里？ 我们设置它等于第一次， 这并不意味着这样做。 如果我设置PTR等于一，什么 应我的手真的是指向？ 右。 所以，如果加布和我要去 这里是相等的值， 我们需要在两个点在9号。 因此，这是我们的故事的开始。 而现在这仅仅是简单的， 即使语法是新的。 概念上，这只是线性搜索。 是55等于9？ 或者说，让我们说不到9。 因为我想 找出放在哪里55。 9以上，小于17，小于 大于20，小于22，小于29， 小于34，没有。 所以，现在我们的情况下 一个上的至少三个。 如果我要插入55在这里，有什么 得到执行的代码需要行？ 请问这个图片 人类需要改变吗？ 我该怎么办我的左手？ 这应该是零开始， 因为我在列表的末尾。 什么应该发生 这里彼得，是吗？ 他显然会指向我。 所以，我要求有至少两条线路 在今天的示例代码代码 这是怎么回事实现这个 方案中加入55的尾巴。 而我能有一个人跳 起来，只是表示55？ 好吧，你是新的55。 所以现在，如果下一个 情景出现时， 我们要插入的 开始的时候还是这个列表的头？ 而你叫什么名字，号码55？ 听众：杰克。 戴维·J·马兰：杰克？ 好了，很高兴见到你。 欢迎登机。 所以，现在我们要 插入，比方说，数字5。 这里的第二种情况 3，我们想出了之前。 因此，如果5属于之初， 让我们来看看我们是如何发现这一点。 í初始化我的PTR 指针再次号码9。 我意识到，哦，5小于9。 因此，解决这个问题的图片我们。 谁的手里，Gabe的还是大卫 or--什么是数字9的名字？ 听众：仁。 戴维·J·马兰：仁的hands-- 其中，我们的手需要改变吗？ 好了，加布指着现在该怎么办？ 看着我。 我的新节点。 所以我就种做法 这里直观地看到它。 而与此同时我该怎么点呢？ 还在那里我指指点点。 所以，就是这样。 所以真的很需要一行代码修复 这个问题上，似乎。 好了，所以这是很好的。 而也有人是一个占位符，5？ 上来吧。 我们将让您下一次。 好吧，让now--和 顺便说一句，该名 我不是做明确提及的权利 现在，PRED指针，指针的前身 而新的指针，这是 只是名字定 在示例代码的指针或 我的手说的那种指着身边。 你叫什么名字？ 听众：恭。 戴维·J·马兰：恭。 欢迎登机。 好吧，让我们现在来考虑 一个稍微更恼人的情况， 由此我想插入 像26到这一点。 20？ 什么？ 这些are--好事，我们有这样的笔。 好吧，20。 如果有人能得到另一块 纸准备好了，就在case--所有权利。 呵呵，有意思。 嗯，这是一个例子 的讲座错误。 行，所以你叫什么名字来着？ 听众：朱莉娅。 戴维·J·马兰：朱莉娅，你可以弹出 出来，假装你从未在那里？ OK，这从来没有发生过。 谢谢。 因此，假设我们要插入 朱成这个链表。 她是20号。 当然，她的 将属于在 begin--不要在任何地步。 种那么你的手可 倒空或一些垃圾值。 让我们告诉了快速的故事。 我指着5号这段时间。 然后我检查9。 然后我检查17。 然后我检查22。 我意识到，哦，朱莉娅 需要22日前去。 因此，需要做些什么？ 谁的手里需要改变吗？ Julia的，我的，or-- 你叫什么名字来着？ 听众：基督教。 戴维·J·马兰：基督教还是？ 听众：安迪。 戴维·J·马兰：安迪。 基督教或安迪？ 安迪需要指向？ 朱莉娅。 好吧。 所以安迪，你想点的朱莉娅？ 但是且慢。 在故事迄今 我是一个排序 在电荷，在这个意义上， 指针的东西，是 在列表中移动。 我们可能对刘德华的名称，但 有没有所谓的可变安迪。 我们唯一的其他变量 第一，谁是由加布表示。 因此，这实际上是这样，为什么 到目前为止，我们已经没有必要了。 但现在在屏幕上有 预计值的指针再提起。 因此，让我更明确。 如果这是指针，我最好 得到一个小更智能 我的迭代。 如果你不介意我的经历在这里 再次，指指点点，指指点点。 不过，让我有一个预计值的指针， 前任的指针，这是 种指着 元我就在。 所以，当我去这里，现在 我的左手更新。 当我走在这里我的左手更新。 现在我不仅是一个指针 朱莉娅之后去的元素， 我仍然有一个指针 安迪，之前的元素。 所以，你有机会，基本上， 面包屑，如果你愿意， 到所有必要的指针。 所以，如果我指着 安迪和我还指着 在基督教，他的手 现在应该在别处指出？ 所以安迪现在可以指向朱莉娅。 朱莉娅现在可以指向基督徒。 因为她能复制我的 右手的指针。 并能有效地使你 回到这里这个地方。 所以，总之，即使此 正在美国种永 实际更新 链表，实现 该操作 是相对简单的。 它是一个，两个，三个 行代码最终。 但缠的 行的代码大概 有点逻辑，有效地 问这个问题，我们在哪里？ 难道我们在一开始， 中间还是结束了吗？ 现在，当然也有一些其他的 操作我们有可能实现的。 而这些图片在这里只是描述 我们刚刚与人类一样。 怎么样去除？ 如果我想，例如， 删除号码34或55， 我可能有同样的代码， 但我会需要一个或两个步骤。 因为什么是新的？ 如果我删除某人的尽头， 像一些55后34， 什么也有改变，因为我做到这一点？ 我不evict-- 你叫什么名字来着？ 听众：杰克。 戴维·J·马兰：杰克。 我不仅evict--免费杰克， 所以从字面上拨打免费杰克，或者至少 指针有过，但现在 有什么需要改变与彼得？ 他的手好开始朝下。 因为只要我一打电话免费 杰克，如果彼得还指着杰克 因此我继续穿越 列表和访问这个指针， 这时候我们的老朋友分割 故障实际上可能一命呜呼 因为我们已经给了 记忆回到杰克。 你可以呆在那里 笨拙的只是一瞬间。 因为我们只是一对夫妇 最终的操作考虑。 删除列表的头部， 或beginning--而这一次的 有点讨厌。 因为我们要知道，加布 是一种特殊的这一计划。 因为事实上，他有自己的指针。 他不只是被指向， 因为几乎所有的人在这里。 所以当表的标头是 拆除，谁的手里现在需要改变吗？ 你叫什么名字来着？ 听众：恭。 戴维·J·马兰：我是可怕的 在名称，显然。 因此，Christine和加布， 谁的手里需要改变 当我们试图删除恭， 5号，从图片？ 好了，让我们做加布。 Gabe的去点， 据推测，在9号。 但是，接下来应该发生？ 听众：恭应 为null [听不清]。 戴维·J·马兰：好，我们也许应该 make--听到“空”的地方。 听众：空和她的自由。 戴维·J·马兰：NULL是什么？ 听众：空和她的自由。 戴维·J·马兰：空和她的自由。 因此，这是很容易的。 它是完美的，你现在已经排序 站在那里，没有归属感。 因为你已经 从列表中去耦。 你一直有效 从列表中孤立。 因此，我们最好称之为自由现在 恭让的记忆回来了。 否则，每次我们 从列表中删除一个节点 我们可能会犯名单 短，但实际上不降低 在存储器的大小。 所以，如果我们继续增加和 添加，添加的东西的清单， 我的电脑可能会变慢 和慢， 因为我跑出来的 内存，即使我没有实际 用恭的字节 内存了。 那么，到底还有其他 场景course--去除， 在中间，除去 到了最后，正如我们所看到。 但更有趣的 现在的挑战是 将是准确地考虑 运行时间是什么。 这样不仅可以让您的 纸片，如果，加布， 你不会介意 每个人都有压力球。 非常感谢你对我们的链表 这里的志愿者，如果你能。 [掌声] 戴维·J·马兰：好吧。 因此，一对夫妇的分析 问题的话，如果我能。 我们以前见过这个符号， 大O和欧米茄，上限 和上下限 运行一些算法的时间。 所以让我们只考虑 几个问题。 一，我们说这 之前，有什么运行 搜索了时间 在大澳条款清单？ 什么是上限运行 搜索链接列表的时间 通过我们的志愿者在这里实现的？ 这n个大O，线性的。 由于在最坏的情况下， 元素，如55， 我们可能会寻找可能的地方 杰克，一路在末端。 不幸的是，一个数组不同 我们不能看上这个时候。 虽然我们所有的人都是 排序由小分子，5， 一路到更大的元素， 55，这通常是一件好事。 但到底是什么这样的假设 不再允许我们做什么？ 听众：[听不清] 戴维·J·马兰：再说一遍吗？ 听众：随机访问。 戴维·J·马兰：随机访问。 而反过来，这意味着我们不能 再使用弱零，直觉， 而显而易见使用二进制的 搜索和分而治之。 因为即使我们 人类能明显 看到刘德华或基督徒都 大致在表的中间， 我们只知道，作为一个 计算机通过略读列表 从一开始。 因此，我们已经放弃了随机访问。 n个这么大O，现在是上 必将在我们的搜索时间。 那么我们的搜索的欧米茄？ 什么是搜索上下限 在此列表中的一些数字？ 听众：[听不清] 戴维·J·马兰：再说一遍吗？ 听众：一。 戴维·J·马兰：一。 因此，一定的时间。 在最好的情况下，克里斯汀是 的确在列表的开头。 我们正在寻找 5号，所以我们找到了她。 所以，没什么大不了的。 但她一定是在 开始列表在此情况下的。 那么什么样删除？ 如果你想删除一个元素？ 什么是上界和下界 有关删除的东西从链接 上市？ 听众：[听不清] 戴维·J·马兰：再说一遍吗？ 听众：不适用。 戴维·J·马兰：n为 确的上限。 由于在最坏的情况下，我们尝试 删除杰克，就像我们刚刚做。 他一路底。 把我们永远的，或 n步找到他。 所以这是一个上限。 这是线性的，肯定的。 和最好的情况下的运行时间，或 在最好的情况下，下限 将恒定时间。 因为也许我们尝试删除 克里斯蒂娜，我们只是很幸运 她开头。 现在，等待一分钟。 加布也之初， 我们也必须更新加布。 所以这不只是一个步骤。 那么，这确实是恒定的 时，在最好的情况下， 去除的最小元素？ 它，即使它可能是两个， 3，甚至是100行的代码， 如果它的相同数量的 行，而不是在一些环路， 和独立的大小 名单的，绝对。 删除的元素 在列表的开头， 即使我们要处理 加布，仍然是固定的时间。 因此，这似乎是一个 巨大的倒退。 什么时间是浪费 如果，在周1周和 零，我们不但 伪代码，但实际的代码 实施东西的日志 基N，或登录，而是n的基地2个， 在其运行时间条件。 那么，为什么赫克，我们将要开始 使用类似链表？ 是啊。 听众：所以，你可以添加 元件的阵列。 戴维·J·马兰：所以，你可以 元素添加到数组中。 而这也是主题。 我们将继续看到 这个，这个权衡，多 就像我们已经看到了 权衡合并排序。 我们真的可以加快 搜索或排序，相反， 如果我们花多一点的空间， 有记忆的附加块 或数组的归并排序。 但是，我们花更多 空间，但我们节省时间。 在这种情况下，我们 放弃时间，但我们 获得的灵活性， 活力，如果你愿意， 这无疑是一个积极的功能。 我们也花了空间。 在什么意义上是一个链接 列出更贵 在空间不是一个数组方面？ 哪里是多余的空间来的呢？ 是吗？ 听众：[听不清]指针。 戴维·J·马兰：是的，我们 也具有指针。 因此，这是minorly烦人 在不再是 存储I只是一个int 表示一个int。 我存储一个int和 指针，这也是32位。 所以，我从字面上倍增 所涉及的空间量。 所以这是一个权衡，但 这是在整数的情况下。 假设你没有存放整型， 但是假设每个这些矩形 或者这些人被代表 一个字，一个英语单词 可能是五个字符，10 人物，更可能。 然后加入只有32多个位 也许是少了一个大问题。 如果每个学生什么 在演示 是字面上的学生结构的 有名字和房子，也许 电话号码和Twitter 处理等。 因此，所有的领域，我们开始 说起那天， 更大不了的 我们的节点变得更加有趣 和大花，嗯，一个额外的 指针只是将它们连接在一起。 不过说实在的，这是一个权衡。 事实上，代码 更复杂的，因为你会 看到通过略读 这特殊的例子。 但是，如果有什么 这里的一些制胜法宝。 如果我们不采取一步 倒退，但一个巨大的进步 并实现数据 结构，通过它我们 可以找到像杰克或元素 恭或任何其他元素 在这个阵列中的真正的固定时间？ 搜索是恒定的。 删除是恒定的。 插入件是恒定的。 所有这些操作都是恒定的。 这将是我们的制胜法宝。 而这正是我们 下次还会回升。 到时候见。