[Powered by Google Translate] [6周，续] [戴维·J·马兰] [哈佛大学] 这是CS50。[CS50.TV] 这是CS50，这是第6周结束。 所以CS50x，哈佛大学的第一EDX主动参与课程 确实在过去的这个星期一推出。 如果你想别人在互联网上窥见一斑 现在跟随着，您可以前往x.cs50.net的。 这将您重定向到适当的位置上edx.org， 这是和其他来自麻省理工学院和伯克利的课程，现在住。 你必须注册一个帐户，你会发现，该材料是大致相同的 你这学期，虽然几个星期延迟，为我们做好一切准备。 但现在学生在CS50x将看到的是一个接口，像这个一样。 这一点，例如，Zamyla问题集0领先的演练。 在登录到edx.org，一个CS50x学生看到了各种各样的事情 你希望看到的一门课程：在周一的演讲， 周三，各种短裤，习题的演练，PDF文件的讲座。 此外，你在这里看到，机器翻译 中文，日语，西班牙语，意大利语，英语成绩单， 和一大堆其他的语言，肯定会是不完美的 我们推出了所谓的API以编程方式使用， 或应用程序编程接口，从谷歌 ，使我们能够转换成其他语言英语。 但由于精彩的一百多名志愿者精神， 随机的人在互联网上获悉的参与 在这个项目中，我们将逐步得到改善这些翻译的质量 的人，我们的计算机已经纠正错误。 

事实证明了，我们有一些更多的学生显示周一最高上比我们最初的预期。 事实上，现在CS50x的有100,000人在家里。 因此，知道你是所有的一部分，这使本课程在计算机科学的就职类的 更为广泛的教育，更广泛地访问。 而现在的现实是，这些大量的网上课程， 他们一开始都是非常高的数字，我们似乎已经在这里完成。 但这个目标，最终，CS50x是真正的终点线可能获得尽可能多的人。 在设计上，CS50x将要提供从过去的这个星期一 所有2013年4月15日通过的方式，让学校的人谁也承担其他地方， 工作，家庭，其他冲突一样，有了更多的灵活性 潜入这门课程，其中，可以肯定地说， 相当雄心勃勃地做，如果仅在短短3个月期间，通常学期的课程。 但是，这些学生将被处理同样的问题集，观看相同的内容， 具有相同的短裤和访问。 因此，认识到我们都是真的，在此一并。 的CS50x的最终目标之一是不只是为了让尽可能多的人 终点线，给他们新发现的计算机科学的理解 和编程，但也让他们有这样的经验共享。 50在校园的定义特征之一，我们希望， 这种共同体验，是好还是坏，有时， 但具有这些人打开到左边和右边， 和办公时间的黑客马拉松和公平。 这一点做起来难，在网上与人的人， 但CS50x有史以来第一次CS50世博会，将于4月结束 这将是我们的想法的网游改编的公平 这些成千上万的学生都将被邀请提交1  -  2分钟的视频， 无论是他们最后的项目或视频截屏挥手打招呼 谈论他们的项目和演示， 很像你的前任在这里做在校园内的公平， 所以，到学期结束，是希望能够有一个全球性的展览 的的CS50x学生的最终项目，就像等待着你这个月在这里的校园生活。 所以，在未来几个月内。 

10万名学生，不过，随着而来的，是需要一些更多的CA。 既然你们正在开辟的线索，并采取CS50 数周提前EDX的人对这种物质的释放， 实现我们很乐意涉及许多我们自己的学生尽可能的这一举措， 在学期期间以及今年冬天和今年春天。 所以，如果你想参与CS50x的， 特别参加上的EDX CS50x讨论，版本的CS50讨论的， 你们中许多人已经在校园内使用，网上公告板， 请做头，URL，让我们知道你是谁， 因为我们很乐意建立一个团队的学生和工作人员和教师的一致好评 在校园简单地打顺和帮助。 当他们看到一个问题，这是他们熟悉的， 你听到学生报告一些错误的地方，在一些国家，在互联网上， 而且铃响了，因为你也有同样的问题 希望在D厅前一段时间，那么你可以附和和分享自己的经验。 所以，请不要参加，如果你想。 

计算机科学课程在哈佛有一个传统的位， CS50其中，有一些服装，有些衣服，你可以自豪地穿 在学期结束，颇为自豪地说，你完成CS50 并把CS50之类的，我们一直在努力让学生参与 在这个过程中尽可能多，因此我们邀请， 在这段时间的学期，学生提交设计 使用Photoshop或任何工具，选择你想使用 如果你是一个设计师，提交设计T-恤和运动衫 和太阳伞和小头巾的狗，我们现在等。 一切是那么的 - 奖每年展出 过程的网站store.cs50.net。 一切都按成本有销售，但该网站只运行 并允许人们选择自己喜欢的颜色和设计。 所以，我想我们只是分享一些去年的设计 在网站上，除了这一个在这里，它是每年的传统。 “每一天我在赛格Faultn的”是去年的意见书， 这仍然是校友。 我们在这其中，“CS50，成立于1989年。” Bowdens，罗布，是去年非常流行。 “鲍登队”诞生了，这个设计提交，当中最畅销的。 由于这一个在这里。很多人有“鲍登发烧”的销售日志。 实现，这可能是你的设计，在互联网上。 在这个问题上的下一个问题的更多细节设置来。 

工具：你已经有一些风险，并希望现在 与GDB的一些实践经验， 这是，当然，一个调试器，让您操作 你的程序在一个相当低的水平，做什么样的事情呢？ GDB让你做什么呢？ 是吗？给我的东西。 [学生回答，不知所云] 好。步入功能，让你不只是要键入run 并有计划通过其整体的打击，打印出来的东西输出到标准输出。 相反，你可以通过线的步骤，方法是键入下一个 走行线或步骤潜入功能，通常是你写的。 什么GDB让你这样做吗？是吗？ [学生回答，不知所云] 打印变量。所以，如果你想你的程序里面做了一点反省 而不必诉诸printf语句写入所有的地方， 你可以只打印一个变量或显示一个变量。 像GDB调试器，你还能做什么呢？ [学生回答，不知所云] 没错。您可以设置断点，你可以说破的执行 在主要功能或函数foo。 你可以说123线中断执行。 断点是一个真正强大的技术 因为如果你有一个一般意义上的你的问题所在 可能的是，你不浪费时间的程序全部通过加强。 基本上，您可以在那里跳，然后开始打字 -  步进通过它与步骤或下一个或等。 但类似GDB勾的是，它可以帮助你的人， 找到你的问题，并找出你的错误。 它并不一定能找到他们这么大的给你。 

因此，我们推出了一天style50，这是一个简短的命令行工具 尝试的样式代码比你多一点点干净的人，可能会做的事。 但是，也真的是只是一个审美的东西。 但事实证明，有这样的工具，称为Valgrind的是多了几分神秘的使用。 乍看之下，它的输出是十恶不赦神秘的。 但它的奇妙有用的，特别是现在，我们在这个词的一部分， 在你开始使用malloc和动态内存分配。 事情都可能很快真的，真的错了。 因为如果你忘记释放你的记忆，你解引用NULL指针， 或者你解引用一些垃圾的指针，什么是典型的症状，结果呢？ 赛格故障。这个核心，你会得到一定数目的字节或兆字节的文件 表示该程序的内存状态时坠毁， 但你的程序，最终段故障，分割故障， 这意味着什么糟糕的事情发生几乎总是与 记忆体相关的错误，你的某个地方制定。 因此，Valgrind的帮助你找到这样的事情。 这是一个工具，你运行，如GDB，你编译你的程序后， 但不是直接运行你的程序，你运行Valgrind的 传递给你的程序，只是像你这样的GDB。 现在，使用，以获得最佳的输出类型， 有点长，所以在屏幕的顶部在那里你会看到Valgrind的-V。 “-V”几乎普遍意味着冗长的，当你在Linux计算机上使用程序。 因此，这意味着你可能会比默认情况下，吐出更多的数据。 “ - 泄漏检查十足。”这只是说检查所有可能的内存泄漏， 错误，我可能会。这一点，也与Linux程序，是一种常见的范例。 一般来说，如果你有一个命令行参数，这是一个“开关”， 这应该改变程序的行为，它是一个单一的字母， 它的-V，但如果这就是切换，只需通过设计的程序员， 是一个完整的字或者一组字，启动命令行参数 - 。 这些都只是人的惯例，但你会看到他们越来越多地。 然后，最后，“a.out格式”是在这个特定的例子中的程序的任意名称。 这里的一些有代表性的输出。 

在我们看这可能意味着什么，让我过去在这里的代码片段。 让我感动了这一点的方式，即将推出， 让我们来看看在memory.c，这是这短短的例子。 因此，在这个程序中，让我放大的功能和问题。 我们有一个main函数中调用一个函数，F， 然后什么f进行，稍有技术的英语吗？ 什么f继续做吗？ 怎么样，我会与第20行开始，恒星的位置并不重要， ，但我会是一致的最后一次演讲。 什么是第20行为我们做什么？在左手侧。我们将打破它进一步下降。 诠释：什么是干什么的？ 好吧。它声明一个指针，现在让我们更技术。 是什么意思，很具体，声明一个指针呢？别人吗？ 是吗？ [学生回答，难以理解太远。 所以，你正在阅读的右手边等号。 让我们把注意力集中在左侧，刚刚于int * X。 “声明”的指针，但现在我们来看看在更深的这一定义。 这是什么具体的，技术上是什么意思？是吗？ [学生回答，不知所云] 好吧。准备保存内存中的地址。 好。让我们进一步采取这一步，它声明了一个变量x，这是32位。 我知道这是32位，因为 - ？ 这不是因为它是一个int，因为它是一个指针，在这种情况下。 巧合的是，它是一个和同一个int， 但事实上，有明星，有指这是一个指针 在家电，与许多计算机中，但不是所有的，指针是32位。 在更现代化的硬件，如最新的Mac电脑，最新的电脑，你可能有64位指针， 但在家电，这些东西都是32位的。 因此，我们将标准化这一点。更具体的是，故事的结局如下： 我们的“声明”指针，这是什么意思呢？ 我们准备存放的内存地址。 这是什么意思呢？ 我们创建了一个变量x 32位 不久将存储的地址的整数。 这是大概准确的，我们可以得到的。 这是向前迈进简化了世界，只说声明一个指向名为x。 声明一个指针，但认识和理解到底发生了 甚至在短短的几个字符。 

现在，这几乎是一点点变得更容易，即使它是一个较长的表达式。 那么，是什么做的，现在的突出“的malloc（10 *表示sizeof（int））;”是吗？ [学生回答，不知所云] 好。我要了。它分配的内存块的十个整数。 现在让我们略深潜水，它是一大块的十个整数的内存分配。 什么是malloc的返回呢？ 这个块的地址，或更具体而言，该块的第一个字节的地址。 我又如何，程序员，知道在哪里，内存块的结束？ 我知道，这是连续的。定义的malloc，给你一个连续的内存块。 无间隙。您可以访问该块中的每个字节， 背靠背回来了，但我怎么知道是这个内存块的结束吗？ 当你使用malloc吗？ [学生回答，不知所云]好。 你不知道。你要记住。 我一定要记住，我用的值是10，我什至不似乎都做了，在这里。 但责任完全在我身上。 STRLEN，我们已经变得稍微依赖于字符串， 不仅是因​​为本公约的\ 0 这种特殊的空字符，NUL，在字符串的结尾。 这并不持有的只是任意的内存块。 这是给你的。因此，第20行，然后，分配的内存块 可以存储10的整数，并且其存储的第一个字节的地址 该块内存中的变量x。 埃尔戈，这是一个指针。所以，不幸的是，第21行是一个错误。 但首先，它是什么做的？说店在位置10，0索引， 名为x的值为0的内存块。 

因此，注意两件事情是怎么回事。 即使x是一个指针，记得几个星期前 你仍然可以使用阵列式方括号。 因为这实际上是简单的记法更神秘的前瞻性指针的算术运算。 在这里我们会做这样的事情：地址x，移动10个点， 然后去那里的地址存储在该位置。 但坦率地说，这仅仅是残酷的，并得到舒适的。 因此，世界上通常使用方括号只是因为它是更人性化的阅读。 但是，这到底发生了什么引擎盖下的; x是一个地址，而不是一个数组，每本身。 因此，这是存储0 10英寸x位置。 这是为什么不好？是吗？ [学生回答，不知所云]没错。 我们只分配了10整数，但我们从0数C语言编程时， 所以你必须为0 1 2 3 4 5 6 7 8 9，但不为10的访问。 因此，无论是程序要赛格故障或事实并非如此。 但是，我们真的不知道，这是一个不确定的行为。 这真的取决于我们是否得到幸运。 如果原来的操作系统，如果我不介意使用额外的字节， 即使它不给我，我的程序可能不会崩溃。 它的原料，它的马车，但你可能看不到症状， 您可能会看到它在一段时间内只有一次。 但现实的情况是，错误，其实是有。 它的确是有问题的，如果你写了一个程序，你想要是正确的， 你卖的程序的人都在用，每一次在一段时间内崩溃 因为，当然，这是不好的。事实上，如果你有一个Android手机或iPhone 你下载的应用程序，这些天，如果你曾经有过一个应用程序退出， 突然消失，几乎总是一些与内存相关的问题的结果， 程序员搞砸了，并取消引用指针 他或她不应该有，和iOS或Android的结果是完全中止程序 而不是风险不确定的行为或某种安全漏洞。 

这个计划除了这一个，还有另外一个错误。 还有什么我搞砸了这个项目？ 我还没有练什么我传福音。是吗？ [学生回答，不知所云]好。 我还没有释放的内存。因此，经验法则 必须随时调用malloc，你必须调用完成后，使用该内存。 现在，当我将要释放内存呢？ 也许，我会假设这第一行是正确的，要做到这一点。 例如，因为我不能做到这一点在这里。为什么呢？ 刚出来的范围。因此，即使我们谈论的指针， 这是一个星期2或3个问题，其中x是仅在范围内的大括号，它被宣布。 所以，你绝对不能释放它。我唯一​​的机会，以释放后，大约是21行。 这是一个相当简单的程序，它是相当容易，一旦你种你的心包裹 周围有什么程序在做，其中的错误。 而且，即使你没有看到它在第一，希望它现​​在有点明显 这些错误很容易地解决，很容易实现。 但是，当一个程序长超过12行，50行，100行， 步行通过您的代码行，想通过它在逻辑上， 是可能的，但不是特别有趣的事情，不断地寻找错误， ，它也是很难做到的，这就是为什么这样的工具Valgrind的存在。 让我继续这样做：让我打开我的终端窗口， 让我不只是运行内存，因为内存似乎是罚款。 我得到幸运。去，额外的字节阵列的结尾 似乎不成为问题太多。 但是，让我尽管如此，做一个理智的检查，这只是意味着要检查 这是否实际上是正确的。 

因此，让我们做的valgrind-V  - 泄漏检查=完全， 然后在这种情况下的程序的名称是存储器，而不是a.out的。 所以，让我继续这样做。按下回车键。 亲爱的上帝。这是它的输出，这就是我前面提到的。 但是，如果你学习阅读的废话， 这是诊断输出，是不是很有趣。 你的眼睛真正要寻找的是没有提到的错误或无效的。 建议问题的词。 事实上，让我们看看会发生什么错在这里。 我有某种形式的一个总结，“在使用中在出口处：1块40个字节。” 我真的不知道块还没有，但40字节 其实感觉我可以找出其中，来自。 40个字节。为什么是40个字节在出口中使用吗？ 更具体地，如果我们向下滚动这里， 为什么我肯定失去了40个字节？是吗？ [学生回答，不知所云]完美。是的，没错。 有10的整数，和每个人是4位或32位的大小， 所以我已经失去了精确的40个字节，因为，你的建议，我并没有所谓的自由。 这是一个错误，现在就让我们来看看远一点，看到旁边， “无效的写大小为4。”现在这是什么？ 这里地址是什么基准符号，显然是吗？ 这是十六进制的，任何时候你看到一个数字，以0x开头， 这意味着我们回来的路上，我想，问题的pset 0的部分，十六进制， 这是刚刚做的热身运动，十进制转换为十六进制，二进制等等。 十六进制，只是人的惯例，通常用来表示指针 或者，更普遍的是，地址。这只是一个惯例， 因为这是一个有点更容易阅读，这是一个小更紧凑，比什么是小数， 二进制文件是无用的为大多数人类使用。 所以，现在这是什么意思呢？嗯，它看起来像有一个无效的写 大小为4的第21行上的memory.c。 所以，让我们回到第21行，而事实上，这里是无效的写。 因此，Valgrind是不会完全握住我的手，告诉我的解决办法是什么， 但它是检测，我做了一个无效的写。 我接触的4个字节，我不应该，显然这是因为， 正如你指出的，我做的[10]而不是[9]最大限度地 或[0]或介于两者之间。 使用Valgrind，实现任何时间，你现在写一个程序 使用指针和使用内存，和malloc更具体地说， 肯定的习惯运行此长 但很容易复制和粘贴命令的Valgrind的 看在那里，如果有一些错误。 这将是压倒性的，每次你看到的输出， 只是解析视觉上所有的输出，看看你看到提到的错误 或警告无效或丢失。 任何的话听起来像你搞砸了某个地方。 所以，意识到这是一个新的工具，在您的工具箱。 

现在，在周一，我们有一大堆的人来这里 并代表一个链接的列表的概念。 我们介绍了链表作为一个解决什么问题？ 是吗？ [学生回答，不知所云]好。 数组不能有内存添加到他们。 如果你分配一个大小为10的数组，这就是你所得到的。 你可以调用一个函数，如果你像realloc的最初叫的malloc， ，并且可以试种阵列朝向它的结束，如果有足够的空间 没有其他人使用，而且，如果有，它会找到你一个更大的块其他地方。 然后将所有的这些字节复制到新的数组。 这听起来像一个非常正确的解决方案。 这是为什么缺乏吸引力？ 我的意思是，人类已经解决了这个问题。 为什么我们需要周一链表来解决它？是吗？ [学生回答，不知所云]这可能需要很长的时间。 事实上，在任何时候，当你调用malloc或realloc或calloc，这又是另外一个， 任何时候，你的程序，所谈的操作系统， 你会减慢程序速度下降。 如果你正在做这类的东西在循环中，你真的放缓下来的东西。 你不会注意到这一点的最简单的“Hello World”类型的程序， 但在更大的计划，要求操作系统一而再，再而内存 或给它一次又一次的往往不是一件好事。 另外，它只是形式的智力 - 这是一个完全是浪费时间。 为什么越来越多的内存分配，风险将所有内容复制到新的数组， 如果你有一个选择，让你真正需要的，你只有尽可能多的内存分配？ 所以在这里的长处和短处。 现在的长处之一是，我们有活力。 无所谓的内存块，是免费的， 我只是有点创建这些面包屑通过指针 我的整个链表串在一起。 但我支付至少一价。 

我不得不放弃在获得链表是什么？ 是吗？ [学生回答，不知所云]好。 你需要更多的内存。现在我需要为这些指针的空间， 的情况下，这个超级简单的链表 只要存储4个字节的整数，这是我们一直在说 ，指针为4个字节，所以现在我已经一倍 我只需要存储此列表的内存量。 但是，这是一个不断权衡计算机科学 在时间和空间和发展，精力和其他资源。 使用链表的另一个缺点什么？是吗？ [学生回答，不知所云] 好。不容易获得。我们不能再利用 0周的原则，如分而治之。 更具体地，二进制搜索。因为即使我们人类 大致可以看到这个列表的中间， 计算机只知道这个链表开始的地址，称为第一。 这是为0x123或类似的东西。 而唯一的方式，程序可以找到中间的元素 实际上是搜索整个列表。 即使如此，它的字面搜索整个列表，因为 甚至当你达到的中间元素的指针， 你的计划，这份名单是不知道多久，潜在的， 直到你击中结束的时候，你怎么知道编程的 你在一个链表的结束？ 有一个特殊的NULL指针，如此反复，一个惯例。 而不是使用这个指针，我们绝对不希望它是一些垃圾的价值 指向阶段的地方，我们希望它是手，NULL， 因此，我们有这个总站在这种数据结构，所以我们知道它在哪里结束。 

如果我们要操作的呢？ 我们做了最重要的，这在视觉，与人类， 但如果我们想要做的插入，该怎么办呢？ 因此，原来的名单是9，17，20，22，29，34。 如果我们想的malloc空间为55号，它的节点， 然后我们要插入55到列表中，就像我们上周一？ 如何才能做到这一点呢？那么，梅艳芳走过来，她基本上走的列表。 她的第一个元素，然后开始下，下，下，下，下一个。 终于击中了左侧的一路下滑 并实现了哦，这是NULL。那么，什么指针操作需要做的吗？ 谁的人就结束了，34号，需要提高他的左手 在55点，55需要他们的指点下成为新的NULL终止的左手臂。完成。 很容易插入55到排序的列表。 如何看？ 

让我去进取，不断开拓这里的一些代码示例。 我会打开gedit的，让我第一次打开两个文件。 一个是list1.h，我只想提醒的是，这是代码块 我们用来代表一个节点。 节点具有一个int n和一个指针，只是点称为下一个在列表中的下一件事。 这是现在的。h文件。为什么呢？ 有这样的约定，和我们没有优势，这是一个巨大的量自己， 但人谁写printf和其他功能 给作为礼物送给世界所有这些功能编写一个名为stdio.h中。 然后string.h中，然后有map.h，并有所有这些h文件 期内别人写的，你可能已经看到或使用。 一般来说，在那些h文件是唯一的东西，如类型定义。 或自定义类型或声明的常量的声明。 你不把在头文件中的函数的实现。 你说，而不是，只是他们的原型。 你把你想分享的东西与他们所需要的世界 为了编译自己的代码。因此，只要进入这个习惯， 我们决定做同样的事情。没有太多的list1.h 但我们已经把人在世界上可能有兴趣的东西， 要使用我们的链接列表实现。 现在，在list1.c，我不会去通过这整个事情 因为这是一个有点长，这个程序，但让我们迅速在提示符下运行。 让我编list1的，让我运行list1的，你会看到什么 我们模拟了一个简单的小程序，在这里 这是怎么回事，让我来添加和删除号码的列表。 所以，让我去进取型和3型的菜单选项3。 我想插入数字 - 让我们做的第一个数字，这是9， 现在我告诉我说，的列表现在9。 让我继续前进，做的是另一套插入，所以我打选项3。 我要插入什么号码？ 17。 输入。我会做更多的只是一个。 让我插入22号。 因此，我们已经有了一个初步的链接列表，我们刚才在幻灯片的形式。 这是怎么插入实际发生的事情吗？ 事实上，图22是现在在列表的末尾。 这样的故事告诉我们在舞台上周一，刚才扼 必须实际发生的代码。 让我们一起来看看。让我在这个文件中，向下滚动。 我们会掩饰一些的功能， 但我们会去，说，插入功能。 

让我们看一下如何去到这个链表中插入一个新的节点。 名单在哪里申报？好吧，让我们滚动的方式在最顶端， 注意到，我基本上宣布链表作为一个单一的指针，这是最初NULL。 所以我用一个全局变量，在一般情况下我们所鼓吹反对 因为它使你的代码有点乱来维持， 这是一种懒惰的，通常，但它不是懒惰，这是没有错的，它不坏 如果你的程序的唯一目的是模拟一个链接列表。 而这正是我们正在做的。 因此，而不是宣布在主，然后将它传递给每一个功能 我们已经写了这个程序，而不是实现哦，让我们使全球 因为这项计划的整个目的是展示一个且只有一个链表。 所以，感觉还可以。下面是我的原型，我们不会通过所有这些， 但我写的删除功能，查找功能，插入功能，和移动功能。 但现在，让我们往回走的插入功能 如何在这里工作。 插入上线 - 在这里，我们走了。 插入。因此，它不带任何参数，因为我们要问 他们要插入的数目这个功能的用户内部。 但首先，我们准备给他们一些空间。 这是复制并粘贴到其他的例子。 在这种情况下，我们被分配一个int，这一次我们分配一个节点。 我真的不记得有多少个字节的节点，但是这很好。 SIZEOF能明白这一点对我来说。 我为什么要检查是否为NULL在第120行吗？ 什么可能会出错，在第119行吗？是吗？ [学生回答，不知所云] 好。只要可能的情况下，我问了太多的内存 什么错误的，操作系统没有足够的字节给我， 所以它的信号尽可能多的返回NULL，如果我不检查 我只是一味地继续使用返回的地址，也可能是NULL。 这可能是一些未知的值不是一件好事，除非I  -  其实不会是一个未知的值。这可能是NULL，所以我不希望 滥用它，，风险提领。 如果出现这种情况，我只是返回，我们会假装就像我没有得到任何内存在所有。 

否则，我告诉用户给我一些插入，我呼吁我们的老朋友调用getInt， 然后，这是新的语法，我们（星期一）推出。 “newptr-> N”是指你的地址是由malloc 这代表一个新的节点对象的第一个字节， 然后去到外地，称为n。 一点点小问题：这是相当于什么更神秘的代码行吗？ 我还能这样写呢？要采取刺？ [学生回答，不知所云] 好。使用N，但它不是一件简单的事情，因为这。 我首先需要做什么？ [学生回答，不知所云] 好。我需要做newptr.n。 因此，这是说，显然是一个新的指针地址。为什么呢？ 因为它是malloc返回的。 * newptr说：“去那里”， 然后，一旦你有，那么你可以使用比较熟悉，N， 但这只是看起来有点难看，特别是如果我们人类要 画箭头的指针，所有的时间，世界上有该箭头符号标准化， 这不完全一样的事情。 所以，你只能使用 - >符号的东西，左边是一个指针。 否则，如果它是一个真正的结构，使用，N。 那么这：为什么我初始化newptr的 - >下一个到NULL？ 我们不希望一个悬空的左手的结束阶段。 我们要垂直向下，这意味着列表末尾 可能是在这个节点，所以我们最好确保它是NULL。 而且，在一般情况下，初始化的变量或数据成员和结构 的东西是很好的做法。 只要让垃圾的存在和继续存在一般，让你有麻烦 如果你忘了以后做一些事情。 

这里有一个少数情况下。这又是插入功能， 我检查的第一件事是，如果该变量被称为第一， 这个全局变量是NULL，这意味着有没有链表。 我们没有插入任何数字，所以它是微不足道的插入此数 到列表中，因为它只是属于在开始该列表。 因此，这是当Anita只是站着一个人在这儿，假装 舞台上没有其他人在这里，直到我们分配了一个节点， 然后她可以提高她的手，第一次， 如果每个人都来了之后，她在舞台上周一。 现在在这里，我不得不说这是一个小的检查，如果新节点的n值 <n的值，在当前的第一个节点， 这意味着有一个链表的开始。 在列表中至少有一个节点，但这个新来的家伙 属于在它之前，所以我们需要左右移动的东西。 换句话说，如果该列表已经开始，只是让我们说， 仅仅是17号，这就是 - 实际上，我们可以做到这一点更清楚。 如果我们开始我们的故事指针在这里被称为第一， 它最初是NULL，我们插入了9号， 数字9明显属于在开始该列表。 因此，让我们假装我们只是malloced的地址或9号，并把它放在这里。 默认情况下，如果第一个是9，第一种情况下，我们讨论的只是意味着我们的角度这家伙在这里， 离开这个NULL;现在我们的9号。 我们要插入的下一个数字是17。 17属于这里，所以我们将不得不做一些逻辑步通过。 因此，让我们相反，在我们这样做，让我们假设，我们想插入数字8。 

所以，只是为方便起见，我在这里要绘制。 但请记住，malloc的可以把它的大多数地方。 但是，对于图形的缘故，我准备把它放在这里。 因此，我假装刚刚分配的节点8号，默认情况下，这是NULL。 现在有什么发生？一对夫妇的事情。 （星期一）在舞台上犯这样的错误，我们更新了指针这样的， 这样做，然后我们要求 - 我们孤立在舞台上的其他人。 因为你不能做到 - 在这里操作的顺序是很重要的， 因为现在我们已经失去了，只是漂浮在太空中的这个节点9。 因此，这是不正确的方法（星期一）。 我们首先必须做其它的事情。 世界的状态看起来是这样的。最初，8个已分配。 什么的插入8将是一个更好的办法吗？ 而不是先更新这个指针，只需更新，而不是这一个在这里。 因此，我们需要把这个NULL字符的代码行的 成实际的指针，该指针指向节点9， 然后我们就可以安全地改变首先指出这家伙在这里。 现在，我们有一个列表，链表，两个元素。 这是什么实际上看起来像这里吗？ 如果我们的代码，请注意，我已经做了。 我已经说过了newptr，在这个故事中，newptr指着这家伙。 

因此，让我画一件事，我应该留下多一点空间。 所以请原谅小的小客厅。 这家伙叫newptr。 这是变量，我们宣布的几行，行 - 刚刚25岁以上。 和它的指向到8。所以当我说newptr  - >下，这意味着到结构 被指出在的newptr，所以我们在这里，去那里。 箭头说获得下一个字段，那么“=”是说把什么样的价值？ 这是在什么样的价值是在第一的价值？ 首先是指向这个节点上，这样就意味着现在应该在这个节点。 换句话说，看起来虽然是一个荒谬的乱用我的笔迹， 什么是一个简单的想法，只是将这些箭头围 转化为代码，仅这一项衬垫。 存储在第一位的下一个字段，然后更新第一个实际上是什么样的。 让我们继续前进，快进一些这方面的， 并期待只在这条尾巴插入。 假如我得到的地步，我发现，一些节点的下一个字段是NULL。 而故事中的一个细节，在这一点上，我掩饰 是，我已经介绍了另一种指针在142行，前身指针。 从本质上讲，在这一点上的故事，列表后，获得长期， 我种需要用两个手指走，因为如果我走的太远， 记得在一个单一的长列表，你可以不走回头路。 因此，这个想法predptr是我的左的手指，newptr的 - 而不是newptr。 另一个指针，这里是我的手指，我只是种走的列表。 这就是为什么存在。但是，让我们只考虑一个简单的情况下在这里。 如果该指针的下一个字段是空的，什么是合乎逻辑的含义吗？ 如果你遍历这个列表，你打一个NULL指针吗？ 你在列表末尾，这样的代码，然后追加一个额外的元素 是一种直观的将采取该节点的指针为NULL， 因此，这是目前NULL，并改变它，但是，要在新的节点的地址。 所以我们仅仅是画在代码中的箭头，，我们提请在舞台上提高一个人的左手。 

而且，我会挥挥手，在目前的情况下， 只是因为我认为这是很容易迷失在这样的环境中，当我们这样做， 在列表的中间插入检查。 但是，仅仅凭直觉，需要做些什么，如果你想弄清楚 其中一些号码是属于中间的是你必须走 使用一个以上的手指，多个指针， 揣摩出它所属的检查是元素<当前， >目前，一旦你找到那个地方， 然后，你做这样的骗局，你周围移动指针非常仔细。 的答案，如果你想在自己的家里，原因通过 归结只是这两行代码，但这些生产线的顺序是超级重要的。 因为，如果你把别人的手和提高别人的错误的顺序， 再次，你可能最终成为孤儿的名单。 总结的尾部插入多个概念，是相对简单的。 在头插入也比较简单， 但这个时候，你需要更新一个额外的指针 挤5号到列表中， 然后在中间插入涉及更加努力， 在正确的位置，非常小心地将20号， 这是在17和22之间。 所以，你需要做这样的事情有新的节点20点到22点， 然后，哪一个节点的指针，因此需要更新最后？ 17，要真正将其插入。 所以，再一次，我要推迟，特别是实施的实际代码。 

乍一看，这是一个有点势不可挡，但它实际上只是一个无限循环 的循环，循环，循环，循环，而打破，只要你打的NULL指针， 在这一点，你可以做必要的插入。 那么，这是代表链表插入代码。 这是种了很多，而且感觉就像我们已经解决了一个问题， 但我们已经推出了另一个。坦率地说，我们已经花了所有时间 大O的Ω和运行时间，试图解决问题更迅速， 在这里，我们采取的大倒退，感觉。 然而，如果目标是存储数据， 那感觉就像圣杯，为我们周一表示，是否真的会 即时存储的东西。 

事实上，假设我们确实放下了一会儿链表 我们，而不是推出一个表的概念。 我们只是觉得一个表作为数组的时刻。 这个数组，这种情况下，这里有26个元素，从0到25， 假设你需要的存储块的名称： Alice和Bob和Charlie之类的。 你需要一些数据结构来存储这些名字。 好了，你可以使用的东西像一个链表 ，你可以走之前，Bob和Charlie后，鲍勃列表中插入爱丽丝等等。 而且，事实上，如果你想看到这样的代码，顺便说一句， 我知道，在list2.h，我们做的正是。 我们不会去通过这个代码，但是这是第一个例子中的一个变种 引入了一个其他的struct我们以前见过的所谓的学生， 再有什么实际存储在链表中是一个指针，指向一个学生结构 而不是一个简单的小整数n。 所以实现的代码，涉及到实际的字符串， 但如果目标在手，现在确实是要解决效率问题， 不会是很好，如果我们给一个叫爱丽丝的对象， 我们希望把她一个数据结构的正确位置， 感觉它会是非常好的，只是把爱丽丝， 名称开头为A，在第一个位置。 和Bob，他的名字开始的B，在第二个位置。 有了一个数组，或让我们从一张桌子，一个哈希表， 我们可以这样做。如果我们有一个“爱丽丝梦游仙境”的名称，如， 一个字符串，如爱丽丝，你在哪里放的-l-I-C-E？ 我们需要一个hueristic。我们需要一个函数来采取一些“爱丽丝梦游仙境”的输入​​，比如 并返回一个答案，“把爱丽丝在这个位置。” 而这个函数，这个黑盒子，将被称为散列函数。 

散列函数是一些需要输入，如“爱丽丝”， ，然后返回给你，通常情况下，其中，在一些数据结构中的数字的位置艾丽斯属于。 在这种情况下，我们的散列函数应该是相对简单的。 我们的散列函数应该说，如果你是“爱丽丝”，我应该关心哪些字符？ 第一个。因此，我期待在[0]，然后我说，如果[0]字符是A，返回0。 如果是B，则返回1。如果它的C，返回2，等等。 共0指数，这将让我插入Alice和Bob，这样查理等等 到这样的数据结构中。但是，有一个问题。 如果梅艳芳吗？ 我们把安妮塔？她的名字也以字母A开头， 感觉就像我们对这个问题做了一个更大的烂摊子。 现在，我们有直接的插入，插入固定的时间，到一个数据结构 最坏情况下的，而不是线性的， 但与梅艳芳在这种情况下，我们可以做吗？ 这两个选项是什么，真的吗？是吗？ [学生回答，不知所云]好吧，所以我们可以有另一个维度。 这是很好的。因此，我们可以建立在三维像我们谈论口头上周一。 在这里我们可以添加另一个访问，但没有，我想保持这个简单的假设。 这里的目标是立即有固定时间的访问， 因此，公司增加太多的复杂性。 其他选项时，试图将这个数据结构梅艳芳是什么？是吗？ [学生回答，不知所云]好。因此，我们可以把其他人都下来， 像查理Bob和Alice引起了下来，然后，我们把梅艳芳，她真的想成为。 

当然，现在，这有一个副作用。 可能是有用的，不是因为我们要插入的人一旦这个数据结构 但是，因为我们要检查，如果他们晚 如果我们想打印出所有的数据结构中的名称。 我们要做的事情，最终与此数据。 所以，现在我们已经搞砸了，谁的爱丽丝不再，她应该是。 也不是鲍勃，也不是查理。 因此，也许这不是一个好主意。 但事实上，这是一种选择。我们可能会改变每个人都下来， 心里很不舒服，梅艳芳来晚了的游戏，为什么我们不能只是把梅艳芳 不在这里，不在这里，而不是在这里，我们只是把她一点点在列表中上下。 但是，这个问题再次开始下放。 你也许能够找到爱丽丝瞬间，她的名字。 和Bob瞬间，查理。但是，然后你看梅艳芳， 你看，嗯，爱丽丝的方式。 好了，让我查一下下面的爱丽丝。鲍勃是不是梅艳芳。 查理是不是梅艳芳。哦，还有梅艳芳。 如果你继续搭乘火车，逻辑的方式， 什么是最坏情况下的运行时间发现或插入到这个新的数据结构梅艳芳？ 这是O（n）的，对不对？ 因为在最坏的情况下，有爱丽丝，鲍勃，查理。 。 。 一路下跌命名为“Y”的人，所以只有一个点离开。 值得庆幸的是，我们有没有一个叫“Z”，所以我们把梅艳芳在最底层。 

我们还没有真正解决这个问题。 所以，也许我们需要引入第三维。 而事实证明，如果我们不引进这第三个维度， 我们不能这样做完美，但圣杯得到 固定时间的插入和动态插入，所以 我们没有进行硬编码的大小为26的数组。 我们可以将许多名字，因为我们希望，但让我们在这里休息5分钟 然后做正确。 好的。我的故事，漂亮的人为有 通过选择爱丽丝，然后Bob，然后查理，然后梅艳芳， 他的名字显然是要碰撞与爱丽丝。 但我们周一结束的问题是它是如何可能的是 你会得到这些种类的冲突？换言之， 如果我们开始使用此表格的结构，这是真的只是一个数组， 在这种情况下，26个地点， 如果我们的输入，而不是均匀分布的，怎么办？ 这不是人为Alice和Bob和Charlie和David等按字母顺序， 它均匀地分布在从A到Z 

也许我们会得到幸运的，我们不会有两个A或B的 具有非常高的概率，但有人指出， 如果我们广义这个问题，而不是0到25 但是，例如，从0到364或65，往往是一个典型的一年中的天数， 并提出这样的问题，“什么是概率在这个房间里，我们两个人有相同的生日吗？” 它的另一种方式，什么是概率，我们两个人有一个名字开头的吗？ 样的问题是相同的，但这个地址空间， 本次搜索空间的生日是大的情况下， 因为我们有这么多天，今年比字母在字母表。 的冲突概率是什么？ 好了，我们可以把这个搞清楚数学相反的方向。 没有碰撞的概率是什么？ 好了，在这里说，这表达的概率 如果只有一个人在这个房间里，他们有一个独特的生日？ 这是100％。因为如果只有一个人在房间里， 他或她的生日可以是任何365天的一年。 因此，三百六十五分之三百六十五选项给了我一个值为1。 所以，此刻的概率问题是只有1。 但是，如果有一个人在房间里， 什么是他们的生日的概率是不同的？ 只有364天，忽略闰年， 他们的生日没有碰撞与其他人。 因此，364/365。如果第三人来，它是363/365，并依此类推。 因此，我们将这些分数相乘，这是越来越小， 弄清楚，我们所有的人都有独特的生日的概率是多少？ 但我们可以，当然，只是这个答案和翻转 和1负所有这一切，我们最终会得到一个表达 如果你还记得你的数学书的背面，它看起来有点像这样， 这是更容易理解的图形。 这里这个图形的x轴方向上的数量的生日， 或人与生日，和在y轴上的数量是一个匹配的概率。 这是什么说的是，如果你有，比方说，甚至， 让我们选择像22，23。 如果有22或23人在房间里， 的概率是那些极少数的两个人有相同的生日 实际上是超级高，组合性。 50％的几率只有22人，研讨会，几乎一类， 2的那些人有相同的生日。 因为有这么多的方法，让你可以有相同的生日。 更糟的是，如果你右手边的图表， 的时候，你有一个类，它有58名学生， 2人的生日的概率是超级，超级高，几乎100％。 现在，这是一种现实生活中的一个有趣的事实。 

但所带来的影响，现在，数据结构和存储信息 也就是说，假设你有一个漂亮，干净，均匀分布的数据 你有一个足够大的数组，以适应一堆东西 并不意味着你会得到人们的独特的地方。 你要去有冲突。所以这个散列的概念，因为它是所谓的， 输入像“爱丽丝”和按摩以某种方式 然后取回如0或1或2的答案。 从该函数获取一些输出正困扰着这个碰撞的概率。 那么，我们如何处理这些冲突？ 那么，在一种情况下，我们可以采取的想法，建议。 我们就可以转移倒众人，或也许，多了几分简单， 而不是移动所有的人，让我们只是梅艳芳的底部备有现货。 因此，如果Alice是0，鲍勃是1，查理是2， 我们只是把梅艳芳在位置3。 这是一个数据结构称为线性探测技术。 线性的，因为你走这条线，和你有几分试探 可用的点的数据结构中。 当然，这种不满转化为O（n）。 如果数据结构确实充分，已经有25人， ，然后袁咏仪走来，她结束了在什么位置Z，这很好。 她仍然适用，我们能找到她。 

但是，这是相反的目标，加快东西。 那么，如果我们不是介绍了这第三个维度？ 这种技术通常被称为单独的链接，或链。 是怎样的一个哈希表，这个表结构， 你的表是一个指针数组。 但是，这些指针指向的是你猜怎么着？ 链表。那么，如果我们把这些世界最好的吗？ 我们使用数组的初始指标 到的数据结构，这样我们就可以即刻前往[0] [1]，[30]等等， 但是，我们有一定的灵活性，我们可以适合梅艳芳，爱丽丝和亚当 和任何其他的名称， 我们，而不是让其他轴增长到任意。 截至周一，我们终于有链接列表，表达能力。 我们可以任意增长数据结构。 另外，我们可以只让一个巨大的二维数组， 一个2维阵列中的行，但是这将是一个可怕的情况，如果一个 不够大，更多的人，他的名字恰好开始A. 上帝保佑，我们必须重新分配一个巨大的二维结构 正因为有这么多的人命名为A， 特别是当有所以几个人命名为Z东西。 这将是一个非常稀疏的数据结构。 因此，它不是完美的，任何手段，但至少现在我们有能力 Alice或梅艳芳属于立即找到， 至少在纵轴条款， 然后我们只需要决定把梅艳芳或翘在这个链表。 如果我们不关心排序的事情，如何迅速，我们将爱丽丝成这样的结构吗？ 这是恒定的时间。我们的指数为[0]，如果没有一个人的存在， 艾丽斯在该链接的列表的开始。 但是，这不是一个大问题。因为如果梅艳芳然后是沿 一些步数后，梅艳芳属于吗？ 那么，[0]。面向对象编程。爱丽丝已经在该链接的列表。 

但是，如果我们不关心这些名称进行排序， 我们就可以将爱丽丝过来，插入梅艳芳，但即使是恒定的时间。 即使有爱丽丝和亚当和所有这些其他的地名， 它不是真正的转移他们的身体。为什么呢？ 因为我们刚刚在这里做的与链表，谁知道，这些节点呢？ 所有你必须​​做的是移动的面包屑。 将周围的箭头，你没有实际移动周围的任何数​​据。 因此，我们可以将梅艳芳，在这种情况下，瞬间。固定的时间。 因此，我们有固定时间的查找，插入固定时间的像梅艳芳的人。 但一种过于简单化的世界。 如果我们以后要找到爱丽丝吗？ 如果我们以后要找到爱丽丝吗？ 多少个步骤是，将要采取的吗？ [学生回答，不知所云] 没错。爱丽丝还没链表中的人数。 所以它不是很完美，因为我们的数据结构，再有这样的垂直通道 然后它有这些链表挂 - 实际上，让我们画一个数组。 这些链接列表，挂它看起来有点像这样。 但问题是，如果爱丽丝和亚当和所有这些其他的地名 结束了越来越多的那边， 发现有人可以结束了一堆的步骤， bcause你必须遍历链表， 这是一个线性操作。 所以，真的，那么，最终的插入时间是O（n），其中n是列表中的元素的数量。 除以，让我们随意m，其中m是多少链表 ，我们已经在此垂直轴。 换句话说，如果我们真正假设均匀分布的名称， 完全不现实的。显然有比别人更多一些字母。 

但是，如果我们假定为均匀分布的那一刻起， 我们有N总的人，和m总链 提供给我们，然后每个这些链的长度 相当简单的将是的总量中，n链的数目除以。 所以N / M。但在这里，我们可以将所有数学聪明。 m是一个常数，因为有一个固定数量的这些。 你会开始申报您的阵列， 我们不调整的垂直轴。根据定义，即固定不变的。 这是唯一的横轴，可以这么说，这改变。 因此从技术上讲，这是一个常数。所以，现在，在插入时间 几乎是O（n）的。 这样就不会觉得所有的东西更好。 但是，什么是真相吗？那么，这一切的时间，几个星期， 我们一直在说为O（n²）。 O（N），2×N“， -  N，再除以2。 。 。 ECH。 这是仅仅局限于N²。但现在，这部分的学期， 我们可以开始再次谈论真实的世界。 N / M是绝对的速度比仅仅局限于N孤独。 如果你有一万余名，你将它们分解为多个桶 所以，你有这些链中只有10名， 绝对搜索的十件事将是快千余件事情。 因此，即将到来的习题会向你挑战 即使认为正是，是啊， 渐近和数学，这还只是线性的， 它吸收一般时试图找东西。 在现实中，它要快于 因为这个除数。 因此，有再一次将是这种权衡 理论和现实之间的冲突， 和一个旋钮将在本学期开始转向在这一点上 是更现实的一个，因为我们准备semster的结束， 为大家介绍一下世界的网络编程， 真的，性能要算，因为你的用户要 开始感受和欣赏糟糕的设计决策。 

那么，你如何去实施一个链接 - 哈希表的31个元素呢？ 前面的例子中任意生日。 如果有一个人生日1月1日或2月1日，我们将把它们放在这个桶。 如果这是1月2日，2月2日，3月2日，我们将把它们放在这个桶。 这就是为什么它是31。如何声明一个哈希表？ 它可以是非常简单的，的节点*表是我的任意名称，[31]。 这给了我31节点的指针， ，让我有31个指针链表 即使这些链是最初为NULL。 把我想要什么，如果我想存储“爱丽丝”，“鲍勃”，“查理”吗？ 好了，我们需要用这些东西在一个结构 因为我们需要爱丽丝来指向给Bob，指向查理，等等。 我们不能只单独的名字，这样我就可以创建一个新的结构，称为节点在这里。 

什么是实际的节点？在这个新的链表节点是什么？ 第一件事情，叫字，是人的名字。 据推测，LENGTH，涉及一个人的名字的最大长度， 不管它是什么，20，30，40个字符疯狂的角落的情况下， +1是为了什么？这仅仅是额外的NULL字符，\ 0。 因此，这个节点是包装内的“东西”本身， 但同时也宣告了一个指针称为未来 这样我们就可以链Alice给Bob查理等等。 可以为NULL，但不一定必须。 这些哈希表的任何问题吗？是吗？ [学生提问，不知所云]数组 - 很好的问题。 字符数组中的字，而不是仅仅的char *这是为什么？ 在这个有点乱的例子，我不想诉诸 对malloc为原来的名称。 我想声明的字符串的最大内存量 这样我就可以复制到结构爱丽丝\ 0，而不必处理malloc和free之类的。 但我能做到这一点，如果我想成为更加自觉地空间使用。这个问题问得好。 因此，让我们尝试概括距离 和聚焦今天的其余部分上的数据结构，更一般 和其他问题，我们能够解决使用相同的基本面 即使自己的数据结构可能有所不同，在他们的资料。 

因此，原来在计算机科学中，树是非常常见的。 你能想到的树排序，就像一个家庭树， 那里的一些根，有的女家长或族长， 爷爷奶奶或或更早回来， 下面是和爸爸妈妈或各种兄弟姐妹等。 因此，一个树结构的节点和它的孩子， 通常每个节点的0个或更多的孩子。 还有一些的专用术语，你在这张照片上看到的 任何小的孩子或孙子的边缘 谁没有从他们身上发出的箭头， 这些是所谓的叶子，并在里面的任何人 是一个内部节点，沿着这些线路，你可以把它叫做什么。 但是，这种结构是很常见的。这其中的任意一点。 我们有一个孩子在左边，我们有三个孩子的权利， 两个孩子的左下角。 因此，我们可以有不同大小的树木，但如果我们开始规范的东西， 您可能还记得二进制从帕特里克的视频上搜索从以前的短 在线，二进制搜索不具有要实现的一个数组 或纸片在黑板上。 假设你想在一个更复杂的数据结构来存储您的数字。 你可以创建一个这样的树。 你可以有一个在C中声明的节点，该节点可以有它的内部的至少两种元素。 一个是你要存储的号码，另一个是 - 好了，我们需要一个更。 另一种是它的孩子。 因此，这里的另一种数据结构。这时候，一个节点被定义为存储号码Ň 然后两个指针;左孩子和右孩子。 他们不是任意的。这棵树有什么有趣的吗？ 

在已经奠定了这一点，或如何帕特里克奠定了它在他的影片有什么模式？ 这是一种明显的，有一些排序怎么回事， 但什么是简单的规则吗？是吗？ [学生回答，不知所云] 完美的。如果你看一眼这，你会看到在左侧的小数字， 大号码的左侧，但为每个节点，这是真的。 对于每个节点，其左子小于，大于它的右子树。 这意味着什么，现在是，如果我要搜索这个数据结构，也就是说，44号， 我必须从根开始，因为所有的这些更复杂的数据结构现在， 我们只有一件事，有一个指针开始。 在这种情况下，一开始是根。这不是左端， 它的这种结构的根目录中。所以我在这里看到的是55岁，和我期待的44。 我想往哪个方向去？ 嗯，我想往左走，因为很明显，在右边将是太大了。 所以，注意在这里，你样的概念上砍了一半的树 因为你永远也不会下降的右手边。 所以，现在我从55到33。这是过于小了一些。 我在寻找44，但现在我知道，如果44是在这棵树，我可以去显然是正确的。 所以，再一次，我修剪树的一半。 这几乎是相同的概念上的电话簿。 这是相同的，我们所做的在黑板上的文件， 但它是一个更复杂的结构，使我们能够真正做到 这种分而治之的算法设计， 而事实上，穿越这样的结构 - 哎呦。 遍历这样的结构，它只是“走这条路还是走那条路。” 意味着所有的代码，弯曲你的心灵第一次执行时第 在家里或步行通过，为二进制搜索，使用递归或迭代， 这是一个痛苦的脖子上。中间的元素，然后做你的四舍五入向上或向下。 

有一个美丽了，因为我们现在可以再次使用递归， 但更干净。事实上，如果你在55号和您想要寻找44， 在这种情况下，你向左走，然后你会怎么做？您可以运行相同的算法。 检查节点的值，然后你去左边或右边。 然后检查节点的值，向左走还是向右。 这是非常适合递归。 因此，即使在过去，我们已经做了一些非常随意的，涉及递归的例子 没有需要的是递归的，数据钢结构， 特别是树木，这是一个完美的应用这个想法的一个问题， 缩小，然后解决相同类型的，但较小的，程序。 

所以，我们可以引进另一种数据结构。 这一个是在第一眼就看神秘的，但是这一次是惊人的。 因此，这是一个数据结构称为特里，特里，这是继承的词检索， 没有明显的重试时间间隔，但是这就是世人所谓的这些东西。尝试。 T-R-I-E。 它是一个某种形式的树结构，但在一个Trie树的每个节点 似乎是什么？这是一个有点误导，因为它是一种简称。 但它看起来像这trie树中的每个节点实际上是一个数组。 即使此图的作者并没有表现出它， 在这种情况下，这个线索是一种数据结构，其目的在生活中是存储词语 A-L-I-C-E或B-O-B等。 的方式，此数据存储Alice和Bob和Charlie和梅艳芳等等 是使用一个数组来存储，爱丽丝在特里， 它看起来像一个数组的根节点开始， 它被写在速记符号。 笔者省略，ABCDEFG，因为有没有名字。 他们仅表现为M和P和T，但在这种情况下， 让搬走Alice和Bob和Charlie一些名字在这里。 麦克斯韦实际上是在此图中。 那么，如何做的作者店M-X-W-E-L-L？ 他或她的根节点开始，并到[M]，因此，大约13时，13日在数组中的位置。 然后从那里，有一个指针。 导致另一个数组的指针。 从那里到该数组的索引位置A，作为描绘在左上角， 那么他或她跟着到另一个数组，指针， 去的指针位置X. 然后，在下一数组位置W，E，L，L，等等， 最后，让我们真正尝试把图片。 节点看起来像在代码中做了什么？ trie树中的一个节点包含多个节点的指针数组。 但也有，至少在这个实现了某种形式的布尔值。 我碰巧把它称为is_word。为什么呢？ 因为当你插入麦克斯韦，你不插入 任何东西到这个数据结构。 你不写M.你不写X. 你做的是以下指针。 表示M，接着是表示A的指针，该指针的指针，该指针 然后指针，表示X，则W，E，L，L， 但结束时你需要做的是去，检查排序，我达到了这个位置。 有在数据结构中的一个词，在这里结束。 

那么什么是特里真的是充满了笔者选择了代表 这些小三角总站。 这只是意味着这样一个事实，这个三角形在这里，这个布尔值true; 也就是说，如果你往后走的树， 这意味着名为Maxwell是在这一个字。 但这个词foo的，例如， 是不是在树中，因为如果我开始在这里的根节点在顶部， 有没有F指针，无O指针，无O指针。 foo不是在这本字典的名称。 但相反的是，图灵，T-U-R-I-N-G。同样，我没有存储t或u r或i或N或G。 但我没有商店这个数据结构中的值的正确的方法，在这里在此节点 - 树 这个布尔值is_word设置为true。 因此，trie树是种很有趣的元结构， 你不是真正的存储的话自己这种字典。 要清楚，你只是存储“是”或“否”，有一个词在这里结束。 

现在有什么含义？ 如果你有15万字，在字典中，你想存储在内存中 使用类似的链接列表， 你将有15节点的链表。 发现这些词的字母顺序排列，可能需要O（n）的时间。 线性时间。但是，在这里的情况下的线索， 什么是运行时间找到一个词？ 原来，这里的美景，即使你已经在这本字典有149,999个字， 如使用该数据结构实现， 找到或插入多一个人进认为，像爱丽丝，爱丽丝需要多少时间？ 嗯，这是只有5个，也许6个步骤的尾随字符。 由于结构中的其他名称presense 没有得到中的插入爱丽丝的方式。 此外，寻找爱丽丝曾经在这本字典有15万字 在用自己的方式寻找爱丽丝在没有得到， 因为Alice。 。 。 。 。在这里，因为我发现一个布尔值。 如果没有布尔值true，则Alice是不是这个数据结构中的话。 换言之，找东西和插入到这个新的东西的运行时间 数据结构的特里是O  - 它不是N。 因为presense 15万人没有“爱丽丝梦游仙境”的影响，它似乎。 因此，让我们把它k，其中k是一个英语单词的最大长度 这是通常不超过20的东西字符。 因此，k是常数。所以我们现在似乎已经找到了圣杯 是的特里，不变的插入，查找，删除。 由于已经在结构的数目的事情， 这是甚至没有亲临现场。同样，他们只是排序的检查，“是”或“否”， 没有影响其未来的运行时间。 

但还有了一个catch，否则我们不会浪费这么多时间 在所有这些其他的数据结构，最终得到的秘密是惊人的。 所以，我们要付出什么样的价格在这里实现这一伟大吗？空间。 这件事是巨大的。的原因，笔者 并不会出现在这里，请注意，所有的这些东西，看起来像阵列， 他没有画出其余的树，其余的特里， 因为他们只是不相关的故事。 但是，所有的这些节点是超级宽，树中的每个节点占用 26实际上，可能是27个字符，因为在这种情况下，我包括空间中的所有格符号 这样我们就可以有apostrophized的话。 在这种情况下，这些都是宽阵列。因此，即使他们没有picutured， 这占用了大量的内存。 这可能是罚款，especilly在现代的硬件， 但是这是一个折衷。我们得到了更短的时间内，花更多的空间。 那么，这是怎么回事？ 好吧，让我们做的 - 让我们在这里看到的。 让我们做一个跳转到这个家伙在这里。 

不管你相信与否，尽可能多的乐趣为C已经有一段时间了， 我们到达点在本学期的时间过渡到更现代的东西。 在更高层次上的事情。即使在接下来的几个星期 我们仍然会继续埋头在世界上的指针和内存管理 得到安慰，使我们可以再建， 比赛结束，最终还是引进，具有讽刺意味的​​是，这不是语言。 我们会花10分钟，谈论HTML一样。 所有的HTML是一种标记语言，一种标记语言是什么 这些系列开放式支架和封闭括号，说'这个大胆的“ “这斜体”，“使这个中心的。” 这是不是所有的智力有趣的，但它是超级有用的。 它肯定是无所不在的这些天。 但是，什么是功能强大的HTML世界，更普遍的Web编程， 建立动态的东西的语言，如PHP或Python或Ruby或Java或C＃编写代码。 真的，无论你选择的语言，并动态地生成HTML。 被称为CSS动态生成的东西。 级联样式表，这也是对美学。 因此，即使今天，如果我去一些喜欢熟悉的Google.com网站， 我去查看，开发人员，查看源代码，也许你以前做过， 但要查看源代码，这东西可能看起来很神秘的。 但是，这是基本的代码，实现Google.com。 在前端。而实际上这是蓬松的美学的东西。 这是CSS在这里。如果我继续向下滚动，我们会得到一些颜色编码的东西。 这是HTML。谷歌的代码看起来像一个烂摊子，但如果我真的打开不同的窗口， 在此，我们可以看到一些结构。 如果我打开这件事，请注意，这是一个有点更具可读性。 我们不久会看到这个标签，[字]是一个标签， HTML，头部，身体，DIV，脚本，文本区，跨度为中心的分区。 这也有几分神秘的前瞻性乍看之下， 但这个烂摊子遵循一定的模式和重复的模式， 因此，一旦我们得到的基本知识，你就可以写这样的代码 然后操作使用另一种语言，称为JavaScript代码。 JavaScript是一种语言，运行在浏览器 今天，我们用哈佛的课程，该课程的购物工具，谷歌地图使用 给你一大堆的活力，Facebook让你显示的即时状态更新， Twitter的使​​用它来显示你的鸣叫瞬间。 所有这一切，我们将开始埋头进来。 但到了那里，我们需要了解一些关于互联网。 这个夹子在这里只是一分钟之久，现在让我们假设这是，其实， 如何在互联网什么来捉弄人。我给你“勇士的净。” 

[♫合唱音乐的慢♫] 男解说员，他带着一个消息。 随着自己的协议。 [♫更快的电子音乐♫] 他来到一个世界的酷防火墙的，漠不关心的路由器， 远远比死还要痛苦和危险。 他速度非常快。他的强者。他是TCP / IP，和他有你的地址。 勇士的净。 [马兰]下周。互联网。 Web编程。这是CS50。 [CS50.TV]