1 00:00:00,000 --> 00:00:02,520 [Powered by Google Translate] [6周，续] 2 00:00:02,520 --> 00:00:04,160 [戴维·J·马兰] [哈佛大学] 3 00:00:04,160 --> 00:00:08,720 这是CS50。[CS50.TV] 4 00:00:08,720 --> 00:00:12,970 这是CS50，这是第6周结束。 5 00:00:12,970 --> 00:00:17,970 所以CS50x，哈佛大学的第一EDX主动参与课程 6 00:00:17,970 --> 00:00:20,590 确实在过去的这个星期一推出。 7 00:00:20,590 --> 00:00:23,460 如果你想别人在互联网上窥见一斑 8 00:00:23,460 --> 00:00:27,180 现在跟随着，您可以前往x.cs50.net的。 9 00:00:27,180 --> 00:00:30,350 这将您重定向到适当的位置上edx.org， 10 00:00:30,350 --> 00:00:34,160 这是和其他来自麻省理工学院和伯克利的课程，现在住。 11 00:00:34,160 --> 00:00:38,140 你必须注册一个帐户，你会发现，该材料是大致相同的 12 00:00:38,140 --> 00:00:42,170 你这学期，虽然几个星期延迟，为我们做好一切准备。 13 00:00:42,170 --> 00:00:46,930 但现在学生在CS50x将看到的是一个接口，像这个一样。 14 00:00:46,930 --> 00:00:50,040 这一点，例如，Zamyla问题集0领先的演练。 15 00:00:50,040 --> 00:00:54,230 在登录到edx.org，一个CS50x学生看到了各种各样的事情 16 00:00:54,230 --> 00:00:57,170 你希望看到的一门课程：在周一的演讲， 17 00:00:57,170 --> 00:01:01,650 周三，各种短裤，习题的演练，PDF文件的讲座。 18 00:01:01,650 --> 00:01:04,459 此外，你在这里看到，机器翻译 19 00:01:04,459 --> 00:01:08,390 中文，日语，西班牙语，意大利语，英语成绩单， 20 00:01:08,390 --> 00:01:12,810 和一大堆其他的语言，肯定会是不完美的 21 00:01:12,810 --> 00:01:15,840 我们推出了所谓的API以编程方式使用， 22 00:01:15,840 --> 00:01:18,360 或应用程序编程接口，从谷歌 23 00:01:18,360 --> 00:01:21,360 ，使我们能够转换成其他语言英语。 24 00:01:21,360 --> 00:01:24,100 但由于精彩的一百多名志愿者精神， 25 00:01:24,100 --> 00:01:26,940 随机的人在互联网上获悉的参与 26 00:01:26,940 --> 00:01:30,180 在这个项目中，我们将逐步得到改善这些翻译的质量 27 00:01:30,180 --> 00:01:35,790 的人，我们的计算机已经纠正错误。 28 00:01:35,790 --> 00:01:42,330 >> 事实证明了，我们有一些更多的学生显示周一最高上比我们最初的预期。 29 00:01:42,330 --> 00:01:48,980 事实上，现在CS50x的有100,000人在家里。 30 00:01:48,980 --> 00:01:54,430 因此，知道你是所有的一部分，这使本课程在计算机科学的就职类的 31 00:01:54,430 --> 00:01:57,370 更为广泛的教育，更广泛地访问。 32 00:01:57,370 --> 00:02:00,130 而现在的现实是，这些大量的网上课程， 33 00:02:00,130 --> 00:02:04,070 他们一开始都是非常高的数字，我们似乎已经在这里完成。 34 00:02:04,070 --> 00:02:08,759 但这个目标，最终，CS50x是真正的终点线可能获得尽可能多的人。 35 00:02:08,759 --> 00:02:12,000 在设计上，CS50x将要提供从过去的这个星期一 36 00:02:12,000 --> 00:02:17,430 所有2013年4月15日通过的方式，让学校的人谁也承担其他地方， 37 00:02:17,430 --> 00:02:20,990 工作，家庭，其他冲突一样，有了更多的灵活性 38 00:02:20,990 --> 00:02:23,640 潜入这门课程，其中，可以肯定地说， 39 00:02:23,640 --> 00:02:30,540 相当雄心勃勃地做，如果仅在短短3个月期间，通常学期的课程。 40 00:02:30,540 --> 00:02:34,190 但是，这些学生将被处理同样的问题集，观看相同的内容， 41 00:02:34,190 --> 00:02:36,350 具有相同的短裤和访问。 42 00:02:36,350 --> 00:02:38,990 因此，认识到我们都是真的，在此一并。 43 00:02:38,990 --> 00:02:42,360 的CS50x的最终目标之一是不只是为了让尽可能多的人 44 00:02:42,360 --> 00:02:45,720 终点线，给他们新发现的计算机科学的理解 45 00:02:45,720 --> 00:02:49,000 和编程，但也让他们有这样的经验共享。 46 00:02:49,000 --> 00:02:52,010 50在校园的定义特征之一，我们希望， 47 00:02:52,010 --> 00:02:56,260 这种共同体验，是好还是坏，有时， 48 00:02:56,260 --> 00:02:59,480 但具有这些人打开到左边和右边， 49 00:02:59,480 --> 00:03:01,830 和办公时间的黑客马拉松和公平。 50 00:03:01,830 --> 00:03:04,560 这一点做起来难，在网上与人的人， 51 00:03:04,560 --> 00:03:10,580 但CS50x有史以来第一次CS50世博会，将于4月结束 52 00:03:10,580 --> 00:03:13,630 这将是我们的想法的网游改编的公平 53 00:03:13,630 --> 00:03:18,250 这些成千上万的学生都将被邀请提交1 - 2分钟的视频， 54 00:03:18,250 --> 00:03:22,480 无论是他们最后的项目或视频截屏挥手打招呼 55 00:03:22,480 --> 00:03:24,490 谈论他们的项目和演示， 56 00:03:24,490 --> 00:03:27,610 很像你的前任在这里做在校园内的公平， 57 00:03:27,610 --> 00:03:31,400 所以，到学期结束，是希望能够有一个全球性的展览 58 00:03:31,400 --> 00:03:37,080 的的CS50x学生的最终项目，就像等待着你这个月在这里的校园生活。 59 00:03:37,080 --> 00:03:39,680 所以，在未来几个月内。 60 00:03:39,680 --> 00:03:43,640 >> 10万名学生，不过，随着而来的，是需要一些更多的CA。 61 00:03:43,640 --> 00:03:47,590 既然你们正在开辟的线索，并采取CS50 62 00:03:47,590 --> 00:03:51,630 数周提前EDX的人对这种物质的释放， 63 00:03:51,630 --> 00:03:55,330 实现我们很乐意涉及许多我们自己的学生尽可能的这一举措， 64 00:03:55,330 --> 00:03:58,720 在学期期间以及今年冬天和今年春天。 65 00:03:58,720 --> 00:04:01,620 所以，如果你想参与CS50x的， 66 00:04:01,620 --> 00:04:07,450 特别参加上的EDX CS50x讨论，版本的CS50讨论的， 67 00:04:07,450 --> 00:04:10,140 你们中许多人已经在校园内使用，网上公告板， 68 00:04:10,140 --> 00:04:13,040 请做头，URL，让我们知道你是谁， 69 00:04:13,040 --> 00:04:16,450 因为我们很乐意建立一个团队的学生和工作人员和教师的一致好评 70 00:04:16,450 --> 00:04:19,630 在校园简单地打顺和帮助。 71 00:04:19,630 --> 00:04:21,720 当他们看到一个问题，这是他们熟悉的， 72 00:04:21,720 --> 00:04:25,320 你听到学生报告一些错误的地方，在一些国家，在互联网上， 73 00:04:25,320 --> 00:04:27,450 而且铃响了，因为你也有同样的问题 74 00:04:27,450 --> 00:04:32,620 希望在D厅前一段时间，那么你可以附和和分享自己的经验。 75 00:04:32,620 --> 00:04:37,300 所以，请不要参加，如果你想。 76 00:04:37,300 --> 00:04:39,360 >> 计算机科学课程在哈佛有一个传统的位， 77 00:04:39,360 --> 00:04:44,730 CS50其中，有一些服装，有些衣服，你可以自豪地穿 78 00:04:44,730 --> 00:04:49,090 在学期结束，颇为自豪地说，你完成CS50 79 00:04:49,090 --> 00:04:51,830 并把CS50之类的，我们一直在努力让学生参与 80 00:04:51,830 --> 00:04:54,540 在这个过程中尽可能多，因此我们邀请， 81 00:04:54,540 --> 00:04:56,900 在这段时间的学期，学生提交设计 82 00:04:56,900 --> 00:04:59,330 使用Photoshop或任何工具，选择你想使用 83 00:04:59,330 --> 00:05:02,330 如果你是一个设计师，提交设计T-恤和运动衫 84 00:05:02,330 --> 00:05:06,100 和太阳伞和小头巾的狗，我们现在等。 85 00:05:06,100 --> 00:05:09,370 一切是那么的 - 奖每年展出 86 00:05:09,370 --> 00:05:12,700 过程的网站store.cs50.net。 87 00:05:12,700 --> 00:05:15,790 一切都按成本有销售，但该网站只运行 88 00:05:15,790 --> 00:05:18,330 并允许人们选择自己喜欢的颜色和设计。 89 00:05:18,330 --> 00:05:20,420 所以，我想我们只是分享一些去年的设计 90 00:05:20,420 --> 00:05:25,130 在网站上，除了这一个在这里，它是每年的传统。 91 00:05:25,130 --> 00:05:29,410 “每一天我在赛格Faultn的”是去年的意见书， 92 00:05:29,410 --> 00:05:32,290 这仍然是校友。 93 00:05:32,290 --> 00:05:35,820 我们在这其中，“CS50，成立于1989年。” 94 00:05:35,820 --> 00:05:39,010 Bowdens，罗布，是去年非常流行。 95 00:05:39,010 --> 00:05:43,480 “鲍登队”诞生了，这个设计提交，当中最畅销的。 96 00:05:43,480 --> 00:05:49,040 由于这一个在这里。很多人有“鲍登发烧”的销售日志。 97 00:05:49,040 --> 00:05:52,650 实现，这可能是你的设计，在互联网上。 98 00:05:52,650 --> 00:05:57,510 在这个问题上的下一个问题的更多细节设置来。 99 00:05:57,510 --> 00:06:00,330 >> 工具：你已经有一些风险，并希望现在 100 00:06:00,330 --> 00:06:02,350 与GDB的一些实践经验， 101 00:06:02,350 --> 00:06:04,570 这是，当然，一个调试器，让您操作 102 00:06:04,570 --> 00:06:09,500 你的程序在一个相当低的水平，做什么样的事情呢？ 103 00:06:09,500 --> 00:06:13,030 GDB让你做什么呢？ 104 00:06:13,030 --> 00:06:15,030 是吗？给我的东西。 [学生回答，不知所云] 105 00:06:15,030 --> 00:06:18,120 好。步入功能，让你不只是要键入run 106 00:06:18,120 --> 00:06:22,310 并有计划通过其整体的打击，打印出来的东西输出到标准输出。 107 00:06:22,310 --> 00:06:25,190 相反，你可以通过线的步骤，方法是键入下一个 108 00:06:25,190 --> 00:06:30,300 走行线或步骤潜入功能，通常是你写的。 109 00:06:30,300 --> 00:06:35,240 什么GDB让你这样做吗？是吗？ [学生回答，不知所云] 110 00:06:35,240 --> 00:06:38,100 打印变量。所以，如果你想你的程序里面做了一点反省 111 00:06:38,100 --> 00:06:41,500 而不必诉诸printf语句写入所有的地方， 112 00:06:41,500 --> 00:06:44,600 你可以只打印一个变量或显示一个变量。 113 00:06:44,600 --> 00:06:46,710 像GDB调试器，你还能做什么呢？ 114 00:06:46,710 --> 00:06:49,170 [学生回答，不知所云] 115 00:06:49,170 --> 00:06:52,080 没错。您可以设置断点，你可以说破的执行 116 00:06:52,080 --> 00:06:54,020 在主要功能或函数foo。 117 00:06:54,020 --> 00:06:56,800 你可以说123线中断执行。 118 00:06:56,800 --> 00:06:58,950 断点是一个真正强大的技术 119 00:06:58,950 --> 00:07:01,110 因为如果你有一个一般意义上的你的问题所在 120 00:07:01,110 --> 00:07:05,360 可能的是，你不浪费时间的程序全部通过加强。 121 00:07:05,360 --> 00:07:08,250 基本上，您可以在那里跳，然后开始打字 - 122 00:07:08,250 --> 00:07:10,970 步进通过它与步骤或下一个或等。 123 00:07:10,970 --> 00:07:14,340 但类似GDB勾的是，它可以帮助你的人， 124 00:07:14,340 --> 00:07:16,940 找到你的问题，并找出你的错误。 125 00:07:16,940 --> 00:07:19,470 它并不一定能找到他们这么大的给你。 126 00:07:19,470 --> 00:07:23,070 >> 因此，我们推出了一天style50，这是一个简短的命令行工具 127 00:07:23,070 --> 00:07:27,500 尝试的样式代码比你多一点点干净的人，可能会做的事。 128 00:07:27,500 --> 00:07:29,530 但是，也真的是只是一个审美的东西。 129 00:07:29,530 --> 00:07:34,110 但事实证明，有这样的工具，称为Valgrind的是多了几分神秘的使用。 130 00:07:34,110 --> 00:07:36,860 乍看之下，它的输出是十恶不赦神秘的。 131 00:07:36,860 --> 00:07:39,420 但它的奇妙有用的，特别是现在，我们在这个词的一部分， 132 00:07:39,420 --> 00:07:43,080 在你开始使用malloc和动态内存分配。 133 00:07:43,080 --> 00:07:45,420 事情都可能很快真的，真的错了。 134 00:07:45,420 --> 00:07:49,320 因为如果你忘记释放你的记忆，你解引用NULL指针， 135 00:07:49,320 --> 00:07:55,770 或者你解引用一些垃圾的指针，什么是典型的症状，结果呢？ 136 00:07:55,770 --> 00:07:59,470 赛格故障。这个核心，你会得到一定数目的字节或兆字节的文件 137 00:07:59,470 --> 00:08:02,990 表示该程序的内存状态时坠毁， 138 00:08:02,990 --> 00:08:05,730 但你的程序，最终段故障，分割故障， 139 00:08:05,730 --> 00:08:08,450 这意味着什么糟糕的事情发生几乎总是与 140 00:08:08,450 --> 00:08:11,750 记忆体相关的错误，你的某个地方制定。 141 00:08:11,750 --> 00:08:14,100 因此，Valgrind的帮助你找到这样的事情。 142 00:08:14,100 --> 00:08:17,720 这是一个工具，你运行，如GDB，你编译你的程序后， 143 00:08:17,720 --> 00:08:20,330 但不是直接运行你的程序，你运行Valgrind的 144 00:08:20,330 --> 00:08:23,960 传递给你的程序，只是像你这样的GDB。 145 00:08:23,960 --> 00:08:26,220 现在，使用，以获得最佳的输出类型， 146 00:08:26,220 --> 00:08:30,410 有点长，所以在屏幕的顶部在那里你会看到Valgrind的-V。 147 00:08:30,410 --> 00:08:35,350 “-V”几乎普遍意味着冗长的，当你在Linux计算机上使用程序。 148 00:08:35,350 --> 00:08:38,770 因此，这意味着你可能会比默认情况下，吐出更多的数据。 149 00:08:38,770 --> 00:08:45,510 “ - 泄漏检查十足。”这只是说检查所有可能的内存泄漏， 150 00:08:45,510 --> 00:08:49,430 错误，我可能会。这一点，也与Linux程序，是一种常见的范例。 151 00:08:49,430 --> 00:08:52,710 一般来说，如果你有一个命令行参数，这是一个“开关”， 152 00:08:52,710 --> 00:08:55,830 这应该改变程序的行为，它是一个单一的字母， 153 00:08:55,830 --> 00:09:00,310 它的-V，但如果这就是切换，只需通过设计的程序员， 154 00:09:00,310 --> 00:09:05,150 是一个完整的字或者一组字，启动命令行参数 - 。 155 00:09:05,150 --> 00:09:08,190 这些都只是人的惯例，但你会看到他们越来越多地。 156 00:09:08,190 --> 00:09:12,410 然后，最后，“a.out格式”是在这个特定的例子中的程序的任意名称。 157 00:09:12,410 --> 00:09:14,640 这里的一些有代表性的输出。 158 00:09:14,640 --> 00:09:22,890 >> 在我们看这可能意味着什么，让我过去在这里的代码片段。 159 00:09:22,890 --> 00:09:26,390 让我感动了这一点的方式，即将推出， 160 00:09:26,390 --> 00:09:32,120 让我们来看看在memory.c，这是这短短的例子。 161 00:09:32,120 --> 00:09:36,290 因此，在这个程序中，让我放大的功能和问题。 162 00:09:36,290 --> 00:09:39,430 我们有一个main函数中调用一个函数，F， 163 00:09:39,430 --> 00:09:45,590 然后什么f进行，稍有技术的英语吗？ 164 00:09:45,590 --> 00:09:49,760 什么f继续做吗？ 165 00:09:49,760 --> 00:09:53,680 怎么样，我会与第20行开始，恒星的位置并不重要， 166 00:09:53,680 --> 00:09:56,720 ，但我会是一致的最后一次演讲。 167 00:09:56,720 --> 00:09:59,910 什么是第20行为我们做什么？在左手侧。我们将打破它进一步下降。 168 00:09:59,910 --> 00:10:02,410 诠释：什么是干什么的？ 169 00:10:02,410 --> 00:10:04,940 好吧。它声明一个指针，现在让我们更技术。 170 00:10:04,940 --> 00:10:10,230 是什么意思，很具体，声明一个指针呢？别人吗？ 171 00:10:10,230 --> 00:10:15,050 是吗？ [学生回答，难以理解太远。 172 00:10:15,050 --> 00:10:17,060 所以，你正在阅读的右手边等号。 173 00:10:17,060 --> 00:10:20,290 让我们把注意力集中在左侧，刚刚于int * X。 174 00:10:20,290 --> 00:10:24,700 “声明”的指针，但现在我们来看看在更深的这一定义。 175 00:10:24,700 --> 00:10:28,330 这是什么具体的，技术上是什么意思？是吗？ 176 00:10:28,330 --> 00:10:31,940 [学生回答，不知所云] 177 00:10:31,940 --> 00:10:35,090 好吧。准备保存内存中的地址。 178 00:10:35,090 --> 00:10:40,680 好。让我们进一步采取这一步，它声明了一个变量x，这是32位。 179 00:10:40,680 --> 00:10:44,440 我知道这是32位，因为 - ？ 180 00:10:44,440 --> 00:10:47,390 这不是因为它是一个int，因为它是一个指针，在这种情况下。 181 00:10:47,390 --> 00:10:49,650 巧合的是，它是一个和同一个int， 182 00:10:49,650 --> 00:10:51,970 但事实上，有明星，有指这是一个指针 183 00:10:51,970 --> 00:10:57,300 在家电，与许多计算机中，但不是所有的，指针是32位。 184 00:10:57,300 --> 00:11:01,850 在更现代化的硬件，如最新的Mac电脑，最新的电脑，你可能有64位指针， 185 00:11:01,850 --> 00:11:04,160 但在家电，这些东西都是32位的。 186 00:11:04,160 --> 00:11:08,380 因此，我们将标准化这一点。更具体的是，故事的结局如下： 187 00:11:08,380 --> 00:11:10,820 我们的“声明”指针，这是什么意思呢？ 188 00:11:10,820 --> 00:11:12,810 我们准备存放的内存地址。 189 00:11:12,810 --> 00:11:15,530 这是什么意思呢？ 190 00:11:15,530 --> 00:11:19,810 我们创建了一个变量x 32位 191 00:11:19,810 --> 00:11:23,810 不久将存储的地址的整数。 192 00:11:23,810 --> 00:11:26,470 这是大概准确的，我们可以得到的。 193 00:11:26,470 --> 00:11:31,810 这是向前迈进简化了世界，只说声明一个指向名为x。 194 00:11:31,810 --> 00:11:35,380 声明一个指针，但认识和理解到底发生了 195 00:11:35,380 --> 00:11:38,490 甚至在短短的几个字符。 196 00:11:38,490 --> 00:11:42,040 >> 现在，这几乎是一点点变得更容易，即使它是一个较长的表达式。 197 00:11:42,040 --> 00:11:48,160 那么，是什么做的，现在的突出“的malloc（10 *表示sizeof（int））;”是吗？ 198 00:11:48,160 --> 00:11:52,350 [学生回答，不知所云] 199 00:11:52,350 --> 00:11:58,250 好。我要了。它分配的内存块的十个整数。 200 00:11:58,250 --> 00:12:02,190 现在让我们略深潜水，它是一大块的十个整数的内存分配。 201 00:12:02,190 --> 00:12:05,390 什么是malloc的返回呢？ 202 00:12:05,390 --> 00:12:10,390 这个块的地址，或更具体而言，该块的第一个字节的地址。 203 00:12:10,390 --> 00:12:14,080 我又如何，程序员，知道在哪里，内存块的结束？ 204 00:12:14,080 --> 00:12:18,340 我知道，这是连续的。定义的malloc，给你一个连续的内存块。 205 00:12:18,340 --> 00:12:21,240 无间隙。您可以访问该块中的每个字节， 206 00:12:21,240 --> 00:12:26,760 背靠背回来了，但我怎么知道是这个内存块的结束吗？ 207 00:12:26,760 --> 00:12:28,850 当你使用malloc吗？ [学生回答，不知所云]好。 208 00:12:28,850 --> 00:12:30,670 你不知道。你要记住。 209 00:12:30,670 --> 00:12:35,960 我一定要记住，我用的值是10，我什至不似乎都做了，在这里。 210 00:12:35,960 --> 00:12:41,000 但责任完全在我身上。 STRLEN，我们已经变得稍微依赖于字符串， 211 00:12:41,000 --> 00:12:45,860 不仅是因​​为本公约的\ 0 212 00:12:45,860 --> 00:12:48,840 这种特殊的空字符，NUL，在字符串的结尾。 213 00:12:48,840 --> 00:12:51,740 这并不持有的只是任意的内存块。 214 00:12:51,740 --> 00:12:58,590 这是给你的。因此，第20行，然后，分配的内存块 215 00:12:58,590 --> 00:13:02,590 可以存储10的整数，并且其存储的第一个字节的地址 216 00:13:02,590 --> 00:13:05,610 该块内存中的变量x。 217 00:13:05,610 --> 00:13:11,140 埃尔戈，这是一个指针。所以，不幸的是，第21行是一个错误。 218 00:13:11,140 --> 00:13:16,110 但首先，它是什么做的？说店在位置10，0索引， 219 00:13:16,110 --> 00:13:19,480 名为x的值为0的内存块。 220 00:13:19,480 --> 00:13:21,510 >> 因此，注意两件事情是怎么回事。 221 00:13:21,510 --> 00:13:25,420 即使x是一个指针，记得几个星期前 222 00:13:25,420 --> 00:13:29,440 你仍然可以使用阵列式方括号。 223 00:13:29,440 --> 00:13:36,180 因为这实际上是简单的记法更神秘的前瞻性指针的算术运算。 224 00:13:36,180 --> 00:13:40,320 在这里我们会做这样的事情：地址x，移动10个点， 225 00:13:40,320 --> 00:13:44,550 然后去那里的地址存储在该位置。 226 00:13:44,550 --> 00:13:48,090 但坦率地说，这仅仅是残酷的，并得到舒适的。 227 00:13:48,090 --> 00:13:52,900 因此，世界上通常使用方括号只是因为它是更人性化的阅读。 228 00:13:52,900 --> 00:13:55,140 但是，这到底发生了什么引擎盖下的; 229 00:13:55,140 --> 00:13:58,190 x是一个地址，而不是一个数组，每本身。 230 00:13:58,190 --> 00:14:02,410 因此，这是存储0 10英寸x位置。 231 00:14:02,410 --> 00:14:06,120 这是为什么不好？是吗？ 232 00:14:06,120 --> 00:14:17,370 [学生回答，不知所云]没错。 233 00:14:17,370 --> 00:14:21,100 我们只分配了10整数，但我们从0数C语言编程时， 234 00:14:21,100 --> 00:14:25,690 所以你必须为0 1 2 3 4 5 6 7 8 9，但不为10的访问。 235 00:14:25,690 --> 00:14:30,270 因此，无论是程序要赛格故障或事实并非如此。 236 00:14:30,270 --> 00:14:32,900 但是，我们真的不知道，这是一个不确定的行为。 237 00:14:32,900 --> 00:14:35,600 这真的取决于我们是否得到幸运。 238 00:14:35,600 --> 00:14:40,650 如果原来的操作系统，如果我不介意使用额外的字节， 239 00:14:40,650 --> 00:14:43,360 即使它不给我，我的程序可能不会崩溃。 240 00:14:43,360 --> 00:14:46,780 它的原料，它的马车，但你可能看不到症状， 241 00:14:46,780 --> 00:14:48,960 您可能会看到它在一段时间内只有一次。 242 00:14:48,960 --> 00:14:51,230 但现实的情况是，错误，其实是有。 243 00:14:51,230 --> 00:14:54,320 它的确是有问题的，如果你写了一个程序，你想要是正确的， 244 00:14:54,320 --> 00:14:58,840 你卖的程序的人都在用，每一次在一段时间内崩溃 245 00:14:58,840 --> 00:15:02,450 因为，当然，这是不好的。事实上，如果你有一个Android手机或iPhone 246 00:15:02,450 --> 00:15:05,550 你下载的应用程序，这些天，如果你曾经有过一个应用程序退出， 247 00:15:05,550 --> 00:15:10,040 突然消失，几乎总是一些与内存相关的问题的结果， 248 00:15:10,040 --> 00:15:12,830 程序员搞砸了，并取消引用指针 249 00:15:12,830 --> 00:15:18,670 他或她不应该有，和iOS或Android的结果是完全中止程序 250 00:15:18,670 --> 00:15:23,080 而不是风险不确定的行为或某种安全漏洞。 251 00:15:23,080 --> 00:15:25,950 >> 这个计划除了这一个，还有另外一个错误。 252 00:15:25,950 --> 00:15:30,180 还有什么我搞砸了这个项目？ 253 00:15:30,180 --> 00:15:32,740 我还没有练什么我传福音。是吗？ 254 00:15:32,740 --> 00:15:34,760 [学生回答，不知所云]好。 255 00:15:34,760 --> 00:15:36,880 我还没有释放的内存。因此，经验法则 256 00:15:36,880 --> 00:15:43,150 必须随时调用malloc，你必须调用完成后，使用该内存。 257 00:15:43,150 --> 00:15:45,610 现在，当我将要释放内存呢？ 258 00:15:45,610 --> 00:15:49,780 也许，我会假设这第一行是正确的，要做到这一点。 259 00:15:49,780 --> 00:15:55,710 例如，因为我不能做到这一点在这里。为什么呢？ 260 00:15:55,710 --> 00:15:57,860 刚出来的范围。因此，即使我们谈论的指针， 261 00:15:57,860 --> 00:16:04,830 这是一个星期2或3个问题，其中x是仅在范围内的大括号，它被宣布。 262 00:16:04,830 --> 00:16:11,000 所以，你绝对不能释放它。我唯一​​的机会，以释放后，大约是21行。 263 00:16:11,000 --> 00:16:15,170 这是一个相当简单的程序，它是相当容易，一旦你种你的心包裹 264 00:16:15,170 --> 00:16:17,870 周围有什么程序在做，其中的错误。 265 00:16:17,870 --> 00:16:20,500 而且，即使你没有看到它在第一，希望它现​​在有点明显 266 00:16:20,500 --> 00:16:23,870 这些错误很容易地解决，很容易实现。 267 00:16:23,870 --> 00:16:28,720 但是，当一个程序长超过12行，50行，100行， 268 00:16:28,720 --> 00:16:31,150 步行通过您的代码行，想通过它在逻辑上， 269 00:16:31,150 --> 00:16:35,110 是可能的，但不是特别有趣的事情，不断地寻找错误， 270 00:16:35,110 --> 00:16:38,340 ，它也是很难做到的，这就是为什么这样的工具Valgrind的存在。 271 00:16:38,340 --> 00:16:40,900 让我继续这样做：让我打开我的终端窗口， 272 00:16:40,900 --> 00:16:45,400 让我不只是运行内存，因为内存似乎是罚款。 273 00:16:45,400 --> 00:16:49,180 我得到幸运。去，额外的字节阵列的结尾 274 00:16:49,180 --> 00:16:51,060 似乎不成为问题太多。 275 00:16:51,060 --> 00:16:56,370 但是，让我尽管如此，做一个理智的检查，这只是意味着要检查 276 00:16:56,370 --> 00:16:58,320 这是否实际上是正确的。 277 00:16:58,320 --> 00:17:04,690 >> 因此，让我们做的valgrind-V - 泄漏检查=完全， 278 00:17:04,690 --> 00:17:07,520 然后在这种情况下的程序的名称是存储器，而不是a.out的。 279 00:17:07,520 --> 00:17:10,760 所以，让我继续这样做。按下回车键。 280 00:17:10,760 --> 00:17:14,109 亲爱的上帝。这是它的输出，这就是我前面提到的。 281 00:17:14,109 --> 00:17:17,550 但是，如果你学习阅读的废话， 282 00:17:17,550 --> 00:17:20,760 这是诊断输出，是不是很有趣。 283 00:17:20,760 --> 00:17:24,829 你的眼睛真正要寻找的是没有提到的错误或无效的。 284 00:17:24,829 --> 00:17:26,800 建议问题的词。 285 00:17:26,800 --> 00:17:29,340 事实上，让我们看看会发生什么错在这里。 286 00:17:29,340 --> 00:17:35,230 我有某种形式的一个总结，“在使用中在出口处：1块40个字节。” 287 00:17:35,230 --> 00:17:38,750 我真的不知道块还没有，但40字节 288 00:17:38,750 --> 00:17:41,260 其实感觉我可以找出其中，来自。 289 00:17:41,260 --> 00:17:45,030 40个字节。为什么是40个字节在出口中使用吗？ 290 00:17:45,030 --> 00:17:48,780 更具体地，如果我们向下滚动这里， 291 00:17:48,780 --> 00:17:54,520 为什么我肯定失去了40个字节？是吗？ 292 00:17:54,520 --> 00:17:59,520 [学生回答，不知所云]完美。是的，没错。 293 00:17:59,520 --> 00:18:03,540 有10的整数，和每个人是4位或32位的大小， 294 00:18:03,540 --> 00:18:08,300 所以我已经失去了精确的40个字节，因为，你的建议，我并没有所谓的自由。 295 00:18:08,300 --> 00:18:13,460 这是一个错误，现在就让我们来看看远一点，看到旁边， 296 00:18:13,460 --> 00:18:16,900 “无效的写大小为4。”现在这是什么？ 297 00:18:16,900 --> 00:18:21,150 这里地址是什么基准符号，显然是吗？ 298 00:18:21,150 --> 00:18:23,640 这是十六进制的，任何时候你看到一个数字，以0x开头， 299 00:18:23,640 --> 00:18:29,410 这意味着我们回来的路上，我想，问题的pset 0的部分，十六进制， 300 00:18:29,410 --> 00:18:34,090 这是刚刚做的热身运动，十进制转换为十六进制，二进制等等。 301 00:18:34,090 --> 00:18:39,220 十六进制，只是人的惯例，通常用来表示指针 302 00:18:39,220 --> 00:18:41,570 或者，更普遍的是，地址。这只是一个惯例， 303 00:18:41,570 --> 00:18:45,340 因为这是一个有点更容易阅读，这是一个小更紧凑，比什么是小数， 304 00:18:45,340 --> 00:18:47,720 二进制文件是无用的为大多数人类使用。 305 00:18:47,720 --> 00:18:50,840 所以，现在这是什么意思呢？嗯，它看起来像有一个无效的写 306 00:18:50,840 --> 00:18:54,480 大小为4的第21行上的memory.c。 307 00:18:54,480 --> 00:18:59,180 所以，让我们回到第21行，而事实上，这里是无效的写。 308 00:18:59,180 --> 00:19:02,640 因此，Valgrind是不会完全握住我的手，告诉我的解决办法是什么， 309 00:19:02,640 --> 00:19:05,520 但它是检测，我做了一个无效的写。 310 00:19:05,520 --> 00:19:08,800 我接触的4个字节，我不应该，显然这是因为， 311 00:19:08,800 --> 00:19:13,960 正如你指出的，我做的[10]而不是[9]最大限度地 312 00:19:13,960 --> 00:19:16,660 或[0]或介于两者之间。 313 00:19:16,660 --> 00:19:19,690 使用Valgrind，实现任何时间，你现在写一个程序 314 00:19:19,690 --> 00:19:24,190 使用指针和使用内存，和malloc更具体地说， 315 00:19:24,190 --> 00:19:27,080 肯定的习惯运行此长 316 00:19:27,080 --> 00:19:30,890 但很容易复制和粘贴命令的Valgrind的 317 00:19:30,890 --> 00:19:32,650 看在那里，如果有一些错误。 318 00:19:32,650 --> 00:19:34,820 这将是压倒性的，每次你看到的输出， 319 00:19:34,820 --> 00:19:39,430 只是解析视觉上所有的输出，看看你看到提到的错误 320 00:19:39,430 --> 00:19:43,190 或警告无效或丢失。 321 00:19:43,190 --> 00:19:46,200 任何的话听起来像你搞砸了某个地方。 322 00:19:46,200 --> 00:19:48,580 所以，意识到这是一个新的工具，在您的工具箱。 323 00:19:48,580 --> 00:19:51,270 >> 现在，在周一，我们有一大堆的人来这里 324 00:19:51,270 --> 00:19:53,150 并代表一个链接的列表的概念。 325 00:19:53,150 --> 00:20:00,970 我们介绍了链表作为一个解决什么问题？ 326 00:20:00,970 --> 00:20:04,590 是吗？ [学生回答，不知所云]好。 327 00:20:04,590 --> 00:20:06,530 数组不能有内存添加到他们。 328 00:20:06,530 --> 00:20:09,440 如果你分配一个大小为10的数组，这就是你所得到的。 329 00:20:09,440 --> 00:20:13,690 你可以调用一个函数，如果你像realloc的最初叫的malloc， 330 00:20:13,690 --> 00:20:17,580 ，并且可以试种阵列朝向它的结束，如果有足够的空间 331 00:20:17,580 --> 00:20:21,610 没有其他人使用，而且，如果有，它会找到你一个更大的块其他地方。 332 00:20:21,610 --> 00:20:25,040 然后将所有的这些字节复制到新的数组。 333 00:20:25,040 --> 00:20:28,310 这听起来像一个非常正确的解决方案。 334 00:20:28,310 --> 00:20:34,790 这是为什么缺乏吸引力？ 335 00:20:34,790 --> 00:20:36,940 我的意思是，人类已经解决了这个问题。 336 00:20:36,940 --> 00:20:40,710 为什么我们需要周一链表来解决它？是吗？ 337 00:20:40,710 --> 00:20:44,060 [学生回答，不知所云]这可能需要很长的时间。 338 00:20:44,060 --> 00:20:49,260 事实上，在任何时候，当你调用malloc或realloc或calloc，这又是另外一个， 339 00:20:49,260 --> 00:20:52,470 任何时候，你的程序，所谈的操作系统， 340 00:20:52,470 --> 00:20:54,310 你会减慢程序速度下降。 341 00:20:54,310 --> 00:20:57,470 如果你正在做这类的东西在循环中，你真的放缓下来的东西。 342 00:20:57,470 --> 00:21:00,740 你不会注意到这一点的最简单的“Hello World”类型的程序， 343 00:21:00,740 --> 00:21:04,300 但在更大的计划，要求操作系统一而再，再而内存 344 00:21:04,300 --> 00:21:07,520 或给它一次又一次的往往不是一件好事。 345 00:21:07,520 --> 00:21:11,210 另外，它只是形式的智力 - 这是一个完全是浪费时间。 346 00:21:11,210 --> 00:21:16,490 为什么越来越多的内存分配，风险将所有内容复制到新的数组， 347 00:21:16,490 --> 00:21:21,980 如果你有一个选择，让你真正需要的，你只有尽可能多的内存分配？ 348 00:21:21,980 --> 00:21:24,130 所以在这里的长处和短处。 349 00:21:24,130 --> 00:21:26,730 现在的长处之一是，我们有活力。 350 00:21:26,730 --> 00:21:29,100 无所谓的内存块，是免费的， 351 00:21:29,100 --> 00:21:32,070 我只是有点创建这些面包屑通过指针 352 00:21:32,070 --> 00:21:34,470 我的整个链表串在一起。 353 00:21:34,470 --> 00:21:36,470 但我支付至少一价。 354 00:21:36,470 --> 00:21:40,060 >> 我不得不放弃在获得链表是什么？ 355 00:21:40,060 --> 00:21:42,470 是吗？ [学生回答，不知所云]好。 356 00:21:42,470 --> 00:21:45,650 你需要更多的内存。现在我需要为这些指针的空间， 357 00:21:45,650 --> 00:21:47,900 的情况下，这个超级简单的链表 358 00:21:47,900 --> 00:21:51,410 只要存储4个字节的整数，这是我们一直在说 359 00:21:51,410 --> 00:21:54,240 ，指针为4个字节，所以现在我已经一倍 360 00:21:54,240 --> 00:21:57,290 我只需要存储此列表的内存量。 361 00:21:57,290 --> 00:21:59,680 但是，这是一个不断权衡计算机科学 362 00:21:59,680 --> 00:22:03,440 在时间和空间和发展，精力和其他资源。 363 00:22:03,440 --> 00:22:06,630 使用链表的另一个缺点什么？是吗？ 364 00:22:06,630 --> 00:22:10,150 [学生回答，不知所云] 365 00:22:10,150 --> 00:22:12,600 好。不容易获得。我们不能再利用 366 00:22:12,600 --> 00:22:15,530 0周的原则，如分而治之。 367 00:22:15,530 --> 00:22:18,220 更具体地，二进制搜索。因为即使我们人类 368 00:22:18,220 --> 00:22:20,400 大致可以看到这个列表的中间， 369 00:22:20,400 --> 00:22:25,840 计算机只知道这个链表开始的地址，称为第一。 370 00:22:25,840 --> 00:22:28,250 这是为0x123或类似的东西。 371 00:22:28,250 --> 00:22:30,990 而唯一的方式，程序可以找到中间的元素 372 00:22:30,990 --> 00:22:33,350 实际上是搜索整个列表。 373 00:22:33,350 --> 00:22:35,500 即使如此，它的字面搜索整个列表，因为 374 00:22:35,500 --> 00:22:38,950 甚至当你达到的中间元素的指针， 375 00:22:38,950 --> 00:22:42,380 你的计划，这份名单是不知道多久，潜在的， 376 00:22:42,380 --> 00:22:45,250 直到你击中结束的时候，你怎么知道编程的 377 00:22:45,250 --> 00:22:48,600 你在一个链表的结束？ 378 00:22:48,600 --> 00:22:51,120 有一个特殊的NULL指针，如此反复，一个惯例。 379 00:22:51,120 --> 00:22:53,870 而不是使用这个指针，我们绝对不希望它是一些垃圾的价值 380 00:22:53,870 --> 00:22:57,750 指向阶段的地方，我们希望它是手，NULL， 381 00:22:57,750 --> 00:23:01,530 因此，我们有这个总站在这种数据结构，所以我们知道它在哪里结束。 382 00:23:01,530 --> 00:23:03,410 >> 如果我们要操作的呢？ 383 00:23:03,410 --> 00:23:05,980 我们做了最重要的，这在视觉，与人类， 384 00:23:05,980 --> 00:23:07,630 但如果我们想要做的插入，该怎么办呢？ 385 00:23:07,630 --> 00:23:12,360 因此，原来的名单是9，17，20，22，29，34。 386 00:23:12,360 --> 00:23:16,730 如果我们想的malloc空间为55号，它的节点， 387 00:23:16,730 --> 00:23:20,730 然后我们要插入55到列表中，就像我们上周一？ 388 00:23:20,730 --> 00:23:23,690 如何才能做到这一点呢？那么，梅艳芳走过来，她基本上走的列表。 389 00:23:23,690 --> 00:23:27,500 她的第一个元素，然后开始下，下，下，下，下一个。 390 00:23:27,500 --> 00:23:29,500 终于击中了左侧的一路下滑 391 00:23:29,500 --> 00:23:34,480 并实现了哦，这是NULL。那么，什么指针操作需要做的吗？ 392 00:23:34,480 --> 00:23:37,980 谁的人就结束了，34号，需要提高他的左手 393 00:23:37,980 --> 00:23:46,220 在55点，55需要他们的指点下成为新的NULL终止的左手臂。完成。 394 00:23:46,220 --> 00:23:49,540 很容易插入55到排序的列表。 395 00:23:49,540 --> 00:23:51,800 如何看？ 396 00:23:51,800 --> 00:23:55,690 >> 让我去进取，不断开拓这里的一些代码示例。 397 00:23:55,690 --> 00:23:58,120 我会打开gedit的，让我第一次打开两个文件。 398 00:23:58,120 --> 00:24:02,050 一个是list1.h，我只想提醒的是，这是代码块 399 00:24:02,050 --> 00:24:04,920 我们用来代表一个节点。 400 00:24:04,920 --> 00:24:13,040 节点具有一个int n和一个指针，只是点称为下一个在列表中的下一件事。 401 00:24:13,040 --> 00:24:15,450 这是现在的。h文件。为什么呢？ 402 00:24:15,450 --> 00:24:19,090 有这样的约定，和我们没有优势，这是一个巨大的量自己， 403 00:24:19,090 --> 00:24:22,220 但人谁写printf和其他功能 404 00:24:22,220 --> 00:24:27,150 给作为礼物送给世界所有这些功能编写一个名为stdio.h中。 405 00:24:27,150 --> 00:24:30,950 然后string.h中，然后有map.h，并有所有这些h文件 406 00:24:30,950 --> 00:24:34,410 期内别人写的，你可能已经看到或使用。 407 00:24:34,410 --> 00:24:38,470 一般来说，在那些h文件是唯一的东西，如类型定义。 408 00:24:38,470 --> 00:24:42,310 或自定义类型或声明的常量的声明。 409 00:24:42,310 --> 00:24:47,890 你不把在头文件中的函数的实现。 410 00:24:47,890 --> 00:24:50,570 你说，而不是，只是他们的原型。 411 00:24:50,570 --> 00:24:53,050 你把你想分享的东西与他们所需要的世界 412 00:24:53,050 --> 00:24:55,640 为了编译自己的代码。因此，只要进入这个习惯， 413 00:24:55,640 --> 00:24:59,110 我们决定做同样的事情。没有太多的list1.h 414 00:24:59,110 --> 00:25:02,070 但我们已经把人在世界上可能有兴趣的东西， 415 00:25:02,070 --> 00:25:05,030 要使用我们的链接列表实现。 416 00:25:05,030 --> 00:25:08,040 现在，在list1.c，我不会去通过这整个事情 417 00:25:08,040 --> 00:25:11,390 因为这是一个有点长，这个程序，但让我们迅速在提示符下运行。 418 00:25:11,390 --> 00:25:15,720 让我编list1的，让我运行list1的，你会看到什么 419 00:25:15,720 --> 00:25:18,070 我们模拟了一个简单的小程序，在这里 420 00:25:18,070 --> 00:25:20,990 这是怎么回事，让我来添加和删除号码的列表。 421 00:25:20,990 --> 00:25:24,310 所以，让我去进取型和3型的菜单选项3。 422 00:25:24,310 --> 00:25:27,880 我想插入数字 - 让我们做的第一个数字，这是9， 423 00:25:27,880 --> 00:25:30,550 现在我告诉我说，的列表现在9。 424 00:25:30,550 --> 00:25:33,760 让我继续前进，做的是另一套插入，所以我打选项3。 425 00:25:33,760 --> 00:25:36,760 我要插入什么号码？ 17。 426 00:25:36,760 --> 00:25:39,220 输入。我会做更多的只是一个。 427 00:25:39,220 --> 00:25:41,720 让我插入22号。 428 00:25:41,720 --> 00:25:45,850 因此，我们已经有了一个初步的链接列表，我们刚才在幻灯片的形式。 429 00:25:45,850 --> 00:25:48,740 这是怎么插入实际发生的事情吗？ 430 00:25:48,740 --> 00:25:52,000 事实上，图22是现在在列表的末尾。 431 00:25:52,000 --> 00:25:55,050 这样的故事告诉我们在舞台上周一，刚才扼 432 00:25:55,050 --> 00:25:57,460 必须实际发生的代码。 433 00:25:57,460 --> 00:25:59,700 让我们一起来看看。让我在这个文件中，向下滚动。 434 00:25:59,700 --> 00:26:01,720 我们会掩饰一些的功能， 435 00:26:01,720 --> 00:26:05,630 但我们会去，说，插入功能。 436 00:26:05,630 --> 00:26:11,720 >> 让我们看一下如何去到这个链表中插入一个新的节点。 437 00:26:11,720 --> 00:26:14,550 名单在哪里申报？好吧，让我们滚动的方式在最顶端， 438 00:26:14,550 --> 00:26:19,970 注意到，我基本上宣布链表作为一个单一的指针，这是最初NULL。 439 00:26:19,970 --> 00:26:23,180 所以我用一个全局变量，在一般情况下我们所鼓吹反对 440 00:26:23,180 --> 00:26:25,280 因为它使你的代码有点乱来维持， 441 00:26:25,280 --> 00:26:29,080 这是一种懒惰的，通常，但它不是懒惰，这是没有错的，它不坏 442 00:26:29,080 --> 00:26:33,660 如果你的程序的唯一目的是模拟一个链接列表。 443 00:26:33,660 --> 00:26:35,460 而这正是我们正在做的。 444 00:26:35,460 --> 00:26:39,100 因此，而不是宣布在主，然后将它传递给每一个功能 445 00:26:39,100 --> 00:26:42,640 我们已经写了这个程序，而不是实现哦，让我们使全球 446 00:26:42,640 --> 00:26:47,060 因为这项计划的整个目的是展示一个且只有一个链表。 447 00:26:47,060 --> 00:26:50,700 所以，感觉还可以。下面是我的原型，我们不会通过所有这些， 448 00:26:50,700 --> 00:26:55,800 但我写的删除功能，查找功能，插入功能，和移动功能。 449 00:26:55,800 --> 00:26:59,080 但现在，让我们往回走的插入功能 450 00:26:59,080 --> 00:27:01,490 如何在这里工作。 451 00:27:01,490 --> 00:27:09,940 插入上线 - 在这里，我们走了。 452 00:27:09,940 --> 00:27:12,850 插入。因此，它不带任何参数，因为我们要问 453 00:27:12,850 --> 00:27:15,930 他们要插入的数目这个功能的用户内部。 454 00:27:15,930 --> 00:27:19,410 但首先，我们准备给他们一些空间。 455 00:27:19,410 --> 00:27:22,050 这是复制并粘贴到其他的例子。 456 00:27:22,050 --> 00:27:25,110 在这种情况下，我们被分配一个int，这一次我们分配一个节点。 457 00:27:25,110 --> 00:27:27,910 我真的不记得有多少个字节的节点，但是这很好。 458 00:27:27,910 --> 00:27:30,460 SIZEOF能明白这一点对我来说。 459 00:27:30,460 --> 00:27:33,340 我为什么要检查是否为NULL在第120行吗？ 460 00:27:33,340 --> 00:27:37,530 什么可能会出错，在第119行吗？是吗？ 461 00:27:37,530 --> 00:27:40,530 [学生回答，不知所云] 462 00:27:40,530 --> 00:27:43,440 好。只要可能的情况下，我问了太多的内存 463 00:27:43,440 --> 00:27:47,020 什么错误的，操作系统没有足够的字节给我， 464 00:27:47,020 --> 00:27:50,640 所以它的信号尽可能多的返回NULL，如果我不检查 465 00:27:50,640 --> 00:27:54,710 我只是一味地继续使用返回的地址，也可能是NULL。 466 00:27:54,710 --> 00:27:58,400 这可能是一些未知的值不是一件好事，除非I - 467 00:27:58,400 --> 00:28:00,590 其实不会是一个未知的值。这可能是NULL，所以我不希望 468 00:28:00,590 --> 00:28:02,550 滥用它，，风险提领。 469 00:28:02,550 --> 00:28:07,410 如果出现这种情况，我只是返回，我们会假装就像我没有得到任何内存在所有。 470 00:28:07,410 --> 00:28:12,270 >> 否则，我告诉用户给我一些插入，我呼吁我们的老朋友调用getInt， 471 00:28:12,270 --> 00:28:15,530 然后，这是新的语法，我们（星期一）推出。 472 00:28:15,530 --> 00:28:20,320 “newptr-> N”是指你的地址是由malloc 473 00:28:20,320 --> 00:28:23,490 这代表一个新的节点对象的第一个字节， 474 00:28:23,490 --> 00:28:26,860 然后去到外地，称为n。 475 00:28:26,860 --> 00:28:35,270 一点点小问题：这是相当于什么更神秘的代码行吗？ 476 00:28:35,270 --> 00:28:38,110 我还能这样写呢？要采取刺？ 477 00:28:38,110 --> 00:28:41,480 [学生回答，不知所云] 478 00:28:41,480 --> 00:28:44,870 好。使用N，但它不是一件简单的事情，因为这。 479 00:28:44,870 --> 00:28:47,090 我首先需要做什么？ [学生回答，不知所云] 480 00:28:47,090 --> 00:28:52,730 好。我需要做newptr.n。 481 00:28:52,730 --> 00:28:55,610 因此，这是说，显然是一个新的指针地址。为什么呢？ 482 00:28:55,610 --> 00:28:59,520 因为它是malloc返回的。 * newptr说：“去那里”， 483 00:28:59,520 --> 00:29:02,970 然后，一旦你有，那么你可以使用比较熟悉，N， 484 00:29:02,970 --> 00:29:05,730 但这只是看起来有点难看，特别是如果我们人类要 485 00:29:05,730 --> 00:29:10,360 画箭头的指针，所有的时间，世界上有该箭头符号标准化， 486 00:29:10,360 --> 00:29:12,320 这不完全一样的事情。 487 00:29:12,320 --> 00:29:16,070 所以，你只能使用 - >符号的东西，左边是一个指针。 488 00:29:16,070 --> 00:29:18,790 否则，如果它是一个真正的结构，使用，N。 489 00:29:18,790 --> 00:29:25,800 那么这：为什么我初始化newptr的 - >下一个到NULL？ 490 00:29:25,800 --> 00:29:28,610 我们不希望一个悬空的左手的结束阶段。 491 00:29:28,610 --> 00:29:31,630 我们要垂直向下，这意味着列表末尾 492 00:29:31,630 --> 00:29:34,980 可能是在这个节点，所以我们最好确保它是NULL。 493 00:29:34,980 --> 00:29:38,460 而且，在一般情况下，初始化的变量或数据成员和结构 494 00:29:38,460 --> 00:29:40,470 的东西是很好的做法。 495 00:29:40,470 --> 00:29:45,170 只要让垃圾的存在和继续存在一般，让你有麻烦 496 00:29:45,170 --> 00:29:48,650 如果你忘了以后做一些事情。 497 00:29:48,650 --> 00:29:51,590 >> 这里有一个少数情况下。这又是插入功能， 498 00:29:51,590 --> 00:29:54,930 我检查的第一件事是，如果该变量被称为第一， 499 00:29:54,930 --> 00:29:58,240 这个全局变量是NULL，这意味着有没有链表。 500 00:29:58,240 --> 00:30:02,460 我们没有插入任何数字，所以它是微不足道的插入此数 501 00:30:02,460 --> 00:30:05,240 到列表中，因为它只是属于在开始该列表。 502 00:30:05,240 --> 00:30:08,100 因此，这是当Anita只是站着一个人在这儿，假装 503 00:30:08,100 --> 00:30:11,390 舞台上没有其他人在这里，直到我们分配了一个节点， 504 00:30:11,390 --> 00:30:13,940 然后她可以提高她的手，第一次， 505 00:30:13,940 --> 00:30:17,420 如果每个人都来了之后，她在舞台上周一。 506 00:30:17,420 --> 00:30:22,900 现在在这里，我不得不说这是一个小的检查，如果新节点的n值 507 00:30:22,900 --> 00:30:27,370 00:30:29,930 这意味着有一个链表的开始。 509 00:30:29,930 --> 00:30:32,330 在列表中至少有一个节点，但这个新来的家伙 510 00:30:32,330 --> 00:30:37,230 属于在它之前，所以我们需要左右移动的东西。 511 00:30:37,230 --> 00:30:43,450 换句话说，如果该列表已经开始，只是让我们说， 512 00:30:43,450 --> 00:30:48,100 仅仅是17号，这就是 - 实际上，我们可以做到这一点更清楚。 513 00:30:48,100 --> 00:30:56,010 如果我们开始我们的故事指针在这里被称为第一， 514 00:30:56,010 --> 00:30:59,870 它最初是NULL，我们插入了9号， 515 00:30:59,870 --> 00:31:02,510 数字9明显属于在开始该列表。 516 00:31:02,510 --> 00:31:07,400 因此，让我们假装我们只是malloced的地址或9号，并把它放在这里。 517 00:31:07,400 --> 00:31:13,170 默认情况下，如果第一个是9，第一种情况下，我们讨论的只是意味着我们的角度这家伙在这里， 518 00:31:13,170 --> 00:31:15,790 离开这个NULL;现在我们的9号。 519 00:31:15,790 --> 00:31:18,280 我们要插入的下一个数字是17。 520 00:31:18,280 --> 00:31:22,420 17属于这里，所以我们将不得不做一些逻辑步通过。 521 00:31:22,420 --> 00:31:26,060 因此，让我们相反，在我们这样做，让我们假设，我们想插入数字8。 522 00:31:26,060 --> 00:31:28,650 >> 所以，只是为方便起见，我在这里要绘制。 523 00:31:28,650 --> 00:31:30,760 但请记住，malloc的可以把它的大多数地方。 524 00:31:30,760 --> 00:31:33,460 但是，对于图形的缘故，我准备把它放在这里。 525 00:31:33,460 --> 00:31:38,440 因此，我假装刚刚分配的节点8号，默认情况下，这是NULL。 526 00:31:38,440 --> 00:31:42,800 现在有什么发生？一对夫妇的事情。 527 00:31:42,800 --> 00:31:47,090 （星期一）在舞台上犯这样的错误，我们更新了指针这样的， 528 00:31:47,090 --> 00:31:51,890 这样做，然后我们要求 - 我们孤立在舞台上的其他人。 529 00:31:51,890 --> 00:31:54,350 因为你不能做到 - 在这里操作的顺序是很重要的， 530 00:31:54,350 --> 00:31:58,760 因为现在我们已经失去了，只是漂浮在太空中的这个节点9。 531 00:31:58,760 --> 00:32:01,150 因此，这是不正确的方法（星期一）。 532 00:32:01,150 --> 00:32:03,330 我们首先必须做其它的事情。 533 00:32:03,330 --> 00:32:06,280 世界的状态看起来是这样的。最初，8个已分配。 534 00:32:06,280 --> 00:32:10,550 什么的插入8将是一个更好的办法吗？ 535 00:32:10,550 --> 00:32:14,720 而不是先更新这个指针，只需更新，而不是这一个在这里。 536 00:32:14,720 --> 00:32:17,720 因此，我们需要把这个NULL字符的代码行的 537 00:32:17,720 --> 00:32:22,020 成实际的指针，该指针指向节点9， 538 00:32:22,020 --> 00:32:27,970 然后我们就可以安全地改变首先指出这家伙在这里。 539 00:32:27,970 --> 00:32:31,330 现在，我们有一个列表，链表，两个元素。 540 00:32:31,330 --> 00:32:33,580 这是什么实际上看起来像这里吗？ 541 00:32:33,580 --> 00:32:36,900 如果我们的代码，请注意，我已经做了。 542 00:32:36,900 --> 00:32:41,970 我已经说过了newptr，在这个故事中，newptr指着这家伙。 543 00:32:41,970 --> 00:32:45,520 >> 因此，让我画一件事，我应该留下多一点空间。 544 00:32:45,520 --> 00:32:48,540 所以请原谅小的小客厅。 545 00:32:48,540 --> 00:32:52,140 这家伙叫newptr。 546 00:32:52,140 --> 00:32:57,940 这是变量，我们宣布的几行，行 - 刚刚25岁以上。 547 00:32:57,940 --> 00:33:03,430 和它的指向到8。所以当我说newptr - >下，这意味着到结构 548 00:33:03,430 --> 00:33:07,910 被指出在的newptr，所以我们在这里，去那里。 549 00:33:07,910 --> 00:33:13,990 箭头说获得下一个字段，那么“=”是说把什么样的价值？ 550 00:33:13,990 --> 00:33:17,280 这是在什么样的价值是在第一的价值？ 551 00:33:17,280 --> 00:33:21,930 首先是指向这个节点上，这样就意味着现在应该在这个节点。 552 00:33:21,930 --> 00:33:25,660 换句话说，看起来虽然是一个荒谬的乱用我的笔迹， 553 00:33:25,660 --> 00:33:28,620 什么是一个简单的想法，只是将这些箭头围 554 00:33:28,620 --> 00:33:31,560 转化为代码，仅这一项衬垫。 555 00:33:31,560 --> 00:33:38,110 存储在第一位的下一个字段，然后更新第一个实际上是什么样的。 556 00:33:38,110 --> 00:33:40,900 让我们继续前进，快进一些这方面的， 557 00:33:40,900 --> 00:33:44,220 并期待只在这条尾巴插入。 558 00:33:44,220 --> 00:33:51,210 假如我得到的地步，我发现，一些节点的下一个字段是NULL。 559 00:33:51,210 --> 00:33:53,410 而故事中的一个细节，在这一点上，我掩饰 560 00:33:53,410 --> 00:33:58,170 是，我已经介绍了另一种指针在142行，前身指针。 561 00:33:58,170 --> 00:34:01,320 从本质上讲，在这一点上的故事，列表后，获得长期， 562 00:34:01,320 --> 00:34:04,800 我种需要用两个手指走，因为如果我走的太远， 563 00:34:04,800 --> 00:34:08,219 记得在一个单一的长列表，你可以不走回头路。 564 00:34:08,219 --> 00:34:13,659 因此，这个想法predptr是我的左的手指，newptr的 - 而不是newptr。 565 00:34:13,659 --> 00:34:17,199 另一个指针，这里是我的手指，我只是种走的列表。 566 00:34:17,199 --> 00:34:22,179 这就是为什么存在。但是，让我们只考虑一个简单的情况下在这里。 567 00:34:22,179 --> 00:34:26,620 如果该指针的下一个字段是空的，什么是合乎逻辑的含义吗？ 568 00:34:26,620 --> 00:34:30,840 如果你遍历这个列表，你打一个NULL指针吗？ 569 00:34:30,840 --> 00:34:35,780 你在列表末尾，这样的代码，然后追加一个额外的元素 570 00:34:35,780 --> 00:34:41,230 是一种直观的将采取该节点的指针为NULL， 571 00:34:41,230 --> 00:34:46,120 因此，这是目前NULL，并改变它，但是，要在新的节点的地址。 572 00:34:46,120 --> 00:34:52,260 所以我们仅仅是画在代码中的箭头，，我们提请在舞台上提高一个人的左手。 573 00:34:52,260 --> 00:34:54,070 >> 而且，我会挥挥手，在目前的情况下， 574 00:34:54,070 --> 00:34:58,020 只是因为我认为这是很容易迷失在这样的环境中，当我们这样做， 575 00:34:58,020 --> 00:35:00,600 在列表的中间插入检查。 576 00:35:00,600 --> 00:35:03,220 但是，仅仅凭直觉，需要做些什么，如果你想弄清楚 577 00:35:03,220 --> 00:35:06,600 其中一些号码是属于中间的是你必须走 578 00:35:06,600 --> 00:35:09,510 使用一个以上的手指，多个指针， 579 00:35:09,510 --> 00:35:12,920 揣摩出它所属的检查是元素<当前， 580 00:35:12,920 --> 00:35:15,450 >目前，一旦你找到那个地方， 581 00:35:15,450 --> 00:35:20,400 然后，你做这样的骗局，你周围移动指针非常仔细。 582 00:35:20,400 --> 00:35:23,850 的答案，如果你想在自己的家里，原因通过 583 00:35:23,850 --> 00:35:28,340 归结只是这两行代码，但这些生产线的顺序是超级重要的。 584 00:35:28,340 --> 00:35:31,390 因为，如果你把别人的手和提高别人的错误的顺序， 585 00:35:31,390 --> 00:35:34,580 再次，你可能最终成为孤儿的名单。 586 00:35:34,580 --> 00:35:39,500 总结的尾部插入多个概念，是相对简单的。 587 00:35:39,500 --> 00:35:42,940 在头插入也比较简单， 588 00:35:42,940 --> 00:35:45,580 但这个时候，你需要更新一个额外的指针 589 00:35:45,580 --> 00:35:47,930 挤5号到列表中， 590 00:35:47,930 --> 00:35:51,560 然后在中间插入涉及更加努力， 591 00:35:51,560 --> 00:35:56,130 在正确的位置，非常小心地将20号， 592 00:35:56,130 --> 00:35:58,350 这是在17和22之间。 593 00:35:58,350 --> 00:36:02,700 所以，你需要做这样的事情有新的节点20点到22点， 594 00:36:02,700 --> 00:36:08,470 然后，哪一个节点的指针，因此需要更新最后？ 595 00:36:08,470 --> 00:36:10,630 17，要真正将其插入。 596 00:36:10,630 --> 00:36:14,080 所以，再一次，我要推迟，特别是实施的实际代码。 597 00:36:14,080 --> 00:36:17,280 >> 乍一看，这是一个有点势不可挡，但它实际上只是一个无限循环 598 00:36:17,280 --> 00:36:21,770 的循环，循环，循环，循环，而打破，只要你打的NULL指针， 599 00:36:21,770 --> 00:36:24,590 在这一点，你可以做必要的插入。 600 00:36:24,590 --> 00:36:30,960 那么，这是代表链表插入代码。 601 00:36:30,960 --> 00:36:34,590 这是种了很多，而且感觉就像我们已经解决了一个问题， 602 00:36:34,590 --> 00:36:36,940 但我们已经推出了另一个。坦率地说，我们已经花了所有时间 603 00:36:36,940 --> 00:36:40,540 大O的Ω和运行时间，试图解决问题更迅速， 604 00:36:40,540 --> 00:36:43,270 在这里，我们采取的大倒退，感觉。 605 00:36:43,270 --> 00:36:45,380 然而，如果目标是存储数据， 606 00:36:45,380 --> 00:36:48,010 那感觉就像圣杯，为我们周一表示，是否真的会 607 00:36:48,010 --> 00:36:50,470 即时存储的东西。 608 00:36:50,470 --> 00:36:53,930 >> 事实上，假设我们确实放下了一会儿链表 609 00:36:53,930 --> 00:36:56,000 我们，而不是推出一个表的概念。 610 00:36:56,000 --> 00:36:59,110 我们只是觉得一个表作为数组的时刻。 611 00:36:59,110 --> 00:37:03,790 这个数组，这种情况下，这里有26个元素，从0到25， 612 00:37:03,790 --> 00:37:07,940 假设你需要的存储块的名称： 613 00:37:07,940 --> 00:37:10,350 Alice和Bob和Charlie之类的。 614 00:37:10,350 --> 00:37:12,880 你需要一些数据结构来存储这些名字。 615 00:37:12,880 --> 00:37:15,000 好了，你可以使用的东西像一个链表 616 00:37:15,000 --> 00:37:20,260 ，你可以走之前，Bob和Charlie后，鲍勃列表中插入爱丽丝等等。 617 00:37:20,260 --> 00:37:23,850 而且，事实上，如果你想看到这样的代码，顺便说一句， 618 00:37:23,850 --> 00:37:27,230 我知道，在list2.h，我们做的正是。 619 00:37:27,230 --> 00:37:30,610 我们不会去通过这个代码，但是这是第一个例子中的一个变种 620 00:37:30,610 --> 00:37:34,640 引入了一个其他的struct我们以前见过的所谓的学生， 621 00:37:34,640 --> 00:37:40,330 再有什么实际存储在链表中是一个指针，指向一个学生结构 622 00:37:40,330 --> 00:37:44,520 而不是一个简单的小整数n。 623 00:37:44,520 --> 00:37:46,900 所以实现的代码，涉及到实际的字符串， 624 00:37:46,900 --> 00:37:49,940 但如果目标在手，现在确实是要解决效率问题， 625 00:37:49,940 --> 00:37:53,380 不会是很好，如果我们给一个叫爱丽丝的对象， 626 00:37:53,380 --> 00:37:56,020 我们希望把她一个数据结构的正确位置， 627 00:37:56,020 --> 00:37:58,860 感觉它会是非常好的，只是把爱丽丝， 628 00:37:58,860 --> 00:38:01,180 名称开头为A，在第一个位置。 629 00:38:01,180 --> 00:38:05,270 和Bob，他的名字开始的B，在第二个位置。 630 00:38:05,270 --> 00:38:09,580 有了一个数组，或让我们从一张桌子，一个哈希表， 631 00:38:09,580 --> 00:38:13,650 我们可以这样做。如果我们有一个“爱丽丝梦游仙境”的名称，如， 632 00:38:13,650 --> 00:38:16,700 一个字符串，如爱丽丝，你在哪里放的-l-I-C-E？ 633 00:38:16,700 --> 00:38:20,540 我们需要一个hueristic。我们需要一个函数来采取一些“爱丽丝梦游仙境”的输入​​，比如 634 00:38:20,540 --> 00:38:24,610 并返回一个答案，“把爱丽丝在这个位置。” 635 00:38:24,610 --> 00:38:28,720 而这个函数，这个黑盒子，将被称为散列函数。 636 00:38:28,720 --> 00:38:32,330 >> 散列函数是一些需要输入，如“爱丽丝”， 637 00:38:32,330 --> 00:38:38,080 ，然后返回给你，通常情况下，其中，在一些数据结构中的数字的位置艾丽斯属于。 638 00:38:38,080 --> 00:38:40,830 在这种情况下，我们的散列函数应该是相对简单的。 639 00:38:40,830 --> 00:38:47,510 我们的散列函数应该说，如果你是“爱丽丝”，我应该关心哪些字符？ 640 00:38:47,510 --> 00:38:55,660 第一个。因此，我期待在[0]，然后我说，如果[0]字符是A，返回0。 641 00:38:55,660 --> 00:39:01,130 如果是B，则返回1。如果它的C，返回2，等等。 642 00:39:01,130 --> 00:39:05,940 共0指数，这将让我插入Alice和Bob，这样查理等等 643 00:39:05,940 --> 00:39:10,960 到这样的数据结构中。但是，有一个问题。 644 00:39:10,960 --> 00:39:13,060 如果梅艳芳吗？ 645 00:39:13,060 --> 00:39:17,510 我们把安妮塔？她的名字也以字母A开头， 646 00:39:17,510 --> 00:39:20,330 感觉就像我们对这个问题做了一个更大的烂摊子。 647 00:39:20,330 --> 00:39:24,380 现在，我们有直接的插入，插入固定的时间，到一个数据结构 648 00:39:24,380 --> 00:39:27,100 最坏情况下的，而不是线性的， 649 00:39:27,100 --> 00:39:29,510 但与梅艳芳在这种情况下，我们可以做吗？ 650 00:39:29,510 --> 00:39:34,110 这两个选项是什么，真的吗？是吗？ 651 00:39:34,110 --> 00:39:37,410 [学生回答，不知所云]好吧，所以我们可以有另一个维度。 652 00:39:37,410 --> 00:39:42,320 这是很好的。因此，我们可以建立在三维像我们谈论口头上周一。 653 00:39:42,320 --> 00:39:46,700 在这里我们可以添加另一个访问，但没有，我想保持这个简单的假设。 654 00:39:46,700 --> 00:39:50,160 这里的目标是立即有固定时间的访问， 655 00:39:50,160 --> 00:39:52,170 因此，公司增加太多的复杂性。 656 00:39:52,170 --> 00:39:55,970 其他选项时，试图将这个数据结构梅艳芳是什么？是吗？ 657 00:39:55,970 --> 00:39:58,610 [学生回答，不知所云]好。因此，我们可以把其他人都下来， 658 00:39:58,610 --> 00:40:03,040 像查理Bob和Alice引起了下来，然后，我们把梅艳芳，她真的想成为。 659 00:40:03,040 --> 00:40:05,660 >> 当然，现在，这有一个副作用。 660 00:40:05,660 --> 00:40:09,000 可能是有用的，不是因为我们要插入的人一旦这个数据结构 661 00:40:09,000 --> 00:40:11,250 但是，因为我们要检查，如果他们晚 662 00:40:11,250 --> 00:40:13,600 如果我们想打印出所有的数据结构中的名称。 663 00:40:13,600 --> 00:40:15,850 我们要做的事情，最终与此数据。 664 00:40:15,850 --> 00:40:20,810 所以，现在我们已经搞砸了，谁的爱丽丝不再，她应该是。 665 00:40:20,810 --> 00:40:23,880 也不是鲍勃，也不是查理。 666 00:40:23,880 --> 00:40:26,060 因此，也许这不是一个好主意。 667 00:40:26,060 --> 00:40:28,830 但事实上，这是一种选择。我们可能会改变每个人都下来， 668 00:40:28,830 --> 00:40:32,240 心里很不舒服，梅艳芳来晚了的游戏，为什么我们不能只是把梅艳芳 669 00:40:32,240 --> 00:40:35,870 不在这里，不在这里，而不是在这里，我们只是把她一点点在列表中上下。 670 00:40:35,870 --> 00:40:38,680 但是，这个问题再次开始下放。 671 00:40:38,680 --> 00:40:41,630 你也许能够找到爱丽丝瞬间，她的名字。 672 00:40:41,630 --> 00:40:44,320 和Bob瞬间，查理。但是，然后你看梅艳芳， 673 00:40:44,320 --> 00:40:46,360 你看，嗯，爱丽丝的方式。 674 00:40:46,360 --> 00:40:48,770 好了，让我查一下下面的爱丽丝。鲍勃是不是梅艳芳。 675 00:40:48,770 --> 00:40:51,850 查理是不是梅艳芳。哦，还有梅艳芳。 676 00:40:51,850 --> 00:40:54,720 如果你继续搭乘火车，逻辑的方式， 677 00:40:54,720 --> 00:41:00,690 什么是最坏情况下的运行时间发现或插入到这个新的数据结构梅艳芳？ 678 00:41:00,690 --> 00:41:03,280 这是O（n）的，对不对？ 679 00:41:03,280 --> 00:41:06,280 因为在最坏的情况下，有爱丽丝，鲍勃，查理。 。 。 680 00:41:06,280 --> 00:41:10,150 一路下跌命名为“Y”的人，所以只有一个点离开。 681 00:41:10,150 --> 00:41:13,950 值得庆幸的是，我们有没有一个叫“Z”，所以我们把梅艳芳在最底层。 682 00:41:13,950 --> 00:41:16,040 >> 我们还没有真正解决这个问题。 683 00:41:16,040 --> 00:41:19,890 所以，也许我们需要引入第三维。 684 00:41:19,890 --> 00:41:22,230 而事实证明，如果我们不引进这第三个维度， 685 00:41:22,230 --> 00:41:25,240 我们不能这样做完美，但圣杯得到 686 00:41:25,240 --> 00:41:28,370 固定时间的插入和动态插入，所以 687 00:41:28,370 --> 00:41:30,960 我们没有进行硬编码的大小为26的数组。 688 00:41:30,960 --> 00:41:34,400 我们可以将许多名字，因为我们希望，但让我们在这里休息5分钟 689 00:41:34,400 --> 00:41:38,790 然后做正确。 690 00:41:38,790 --> 00:41:46,020 好的。我的故事，漂亮的人为有 691 00:41:46,020 --> 00:41:48,670 通过选择爱丽丝，然后Bob，然后查理，然后梅艳芳， 692 00:41:48,670 --> 00:41:51,000 他的名字显然是要碰撞与爱丽丝。 693 00:41:51,000 --> 00:41:54,120 但我们周一结束的问题是它是如何可能的是 694 00:41:54,120 --> 00:41:56,370 你会得到这些种类的冲突？换言之， 695 00:41:56,370 --> 00:42:00,490 如果我们开始使用此表格的结构，这是真的只是一个数组， 696 00:42:00,490 --> 00:42:02,460 在这种情况下，26个地点， 697 00:42:02,460 --> 00:42:05,740 如果我们的输入，而不是均匀分布的，怎么办？ 698 00:42:05,740 --> 00:42:09,620 这不是人为Alice和Bob和Charlie和David等按字母顺序， 699 00:42:09,620 --> 00:42:12,380 它均匀地分布在从A到Z 700 00:42:12,380 --> 00:42:15,220 >> 也许我们会得到幸运的，我们不会有两个A或B的 701 00:42:15,220 --> 00:42:17,640 具有非常高的概率，但有人指出， 702 00:42:17,640 --> 00:42:20,730 如果我们广义这个问题，而不是0到25 703 00:42:20,730 --> 00:42:26,060 但是，例如，从0到364或65，往往是一个典型的一年中的天数， 704 00:42:26,060 --> 00:42:31,170 并提出这样的问题，“什么是概率在这个房间里，我们两个人有相同的生日吗？” 705 00:42:31,170 --> 00:42:34,600 它的另一种方式，什么是概率，我们两个人有一个名字开头的吗？ 706 00:42:34,600 --> 00:42:37,190 样的问题是相同的，但这个地址空间， 707 00:42:37,190 --> 00:42:39,940 本次搜索空间的生日是大的情况下， 708 00:42:39,940 --> 00:42:42,820 因为我们有这么多天，今年比字母在字母表。 709 00:42:42,820 --> 00:42:44,910 的冲突概率是什么？ 710 00:42:44,910 --> 00:42:48,410 好了，我们可以把这个搞清楚数学相反的方向。 711 00:42:48,410 --> 00:42:50,580 没有碰撞的概率是什么？ 712 00:42:50,580 --> 00:42:53,970 好了，在这里说，这表达的概率 713 00:42:53,970 --> 00:42:58,770 如果只有一个人在这个房间里，他们有一个独特的生日？ 714 00:42:58,770 --> 00:43:01,190 这是100％。因为如果只有一个人在房间里， 715 00:43:01,190 --> 00:43:03,940 他或她的生日可以是任何365天的一年。 716 00:43:03,940 --> 00:43:08,650 因此，三百六十五分之三百六十五选项给了我一个值为1。 717 00:43:08,650 --> 00:43:11,250 所以，此刻的概率问题是只有1。 718 00:43:11,250 --> 00:43:13,270 但是，如果有一个人在房间里， 719 00:43:13,270 --> 00:43:16,490 什么是他们的生日的概率是不同的？ 720 00:43:16,490 --> 00:43:20,680 只有364天，忽略闰年， 721 00:43:20,680 --> 00:43:23,580 他们的生日没有碰撞与其他人。 722 00:43:23,580 --> 00:43:31,920 因此，364/365。如果第三人来，它是363/365，并依此类推。 723 00:43:31,920 --> 00:43:35,790 因此，我们将这些分数相乘，这是越来越小， 724 00:43:35,790 --> 00:43:40,720 弄清楚，我们所有的人都有独特的生日的概率是多少？ 725 00:43:40,720 --> 00:43:43,570 但我们可以，当然，只是这个答案和翻转 726 00:43:43,570 --> 00:43:47,210 和1负所有这一切，我们最终会得到一个表达 727 00:43:47,210 --> 00:43:51,250 如果你还记得你的数学书的背面，它看起来有点像这样， 728 00:43:51,250 --> 00:43:54,590 这是更容易理解的图形。 729 00:43:54,590 --> 00:43:57,820 这里这个图形的x轴方向上的数量的生日， 730 00:43:57,820 --> 00:44:02,030 或人与生日，和在y轴上的数量是一个匹配的概率。 731 00:44:02,030 --> 00:44:06,060 这是什么说的是，如果你有，比方说，甚至， 732 00:44:06,060 --> 00:44:10,860 让我们选择像22，23。 733 00:44:10,860 --> 00:44:13,160 如果有22或23人在房间里， 734 00:44:13,160 --> 00:44:17,100 的概率是那些极少数的两个人有相同的生日 735 00:44:17,100 --> 00:44:19,560 实际上是超级高，组合性。 736 00:44:19,560 --> 00:44:23,450 50％的几率只有22人，研讨会，几乎一类， 737 00:44:23,450 --> 00:44:25,790 2的那些人有相同的生日。 738 00:44:25,790 --> 00:44:28,520 因为有这么多的方法，让你可以有相同的生日。 739 00:44:28,520 --> 00:44:31,110 更糟的是，如果你右手边的图表， 740 00:44:31,110 --> 00:44:34,040 的时候，你有一个类，它有58名学生， 741 00:44:34,040 --> 00:44:39,270 2人的生日的概率是超级，超级高，几乎100％。 742 00:44:39,270 --> 00:44:41,880 现在，这是一种现实生活中的一个有趣的事实。 743 00:44:41,880 --> 00:44:45,850 >> 但所带来的影响，现在，数据结构和存储信息 744 00:44:45,850 --> 00:44:51,100 也就是说，假设你有一个漂亮，干净，均匀分布的数据 745 00:44:51,100 --> 00:44:53,650 你有一个足够大的数组，以适应一堆东西 746 00:44:53,650 --> 00:44:59,360 并不意味着你会得到人们的独特的地方。 747 00:44:59,360 --> 00:45:03,810 你要去有冲突。所以这个散列的概念，因为它是所谓的， 748 00:45:03,810 --> 00:45:07,450 输入像“爱丽丝”和按摩以某种方式 749 00:45:07,450 --> 00:45:10,190 然后取回如0或1或2的答案。 750 00:45:10,190 --> 00:45:17,500 从该函数获取一些输出正困扰着这个碰撞的概率。 751 00:45:17,500 --> 00:45:19,530 那么，我们如何处理这些冲突？ 752 00:45:19,530 --> 00:45:21,940 那么，在一种情况下，我们可以采取的想法，建议。 753 00:45:21,940 --> 00:45:25,100 我们就可以转移倒众人，或也许，多了几分简单， 754 00:45:25,100 --> 00:45:29,870 而不是移动所有的人，让我们只是梅艳芳的底部备有现货。 755 00:45:29,870 --> 00:45:32,810 因此，如果Alice是0，鲍勃是1，查理是2， 756 00:45:32,810 --> 00:45:35,260 我们只是把梅艳芳在位置3。 757 00:45:35,260 --> 00:45:38,860 这是一个数据结构称为线性探测技术。 758 00:45:38,860 --> 00:45:41,310 线性的，因为你走这条线，和你有几分试探 759 00:45:41,310 --> 00:45:43,640 可用的点的数据结构中。 760 00:45:43,640 --> 00:45:46,210 当然，这种不满转化为O（n）。 761 00:45:46,210 --> 00:45:49,590 如果数据结构确实充分，已经有25人， 762 00:45:49,590 --> 00:45:54,120 ，然后袁咏仪走来，她结束了在什么位置Z，这很好。 763 00:45:54,120 --> 00:45:56,540 她仍然适用，我们能找到她。 764 00:45:56,540 --> 00:46:00,100 >> 但是，这是相反的目标，加快东西。 765 00:46:00,100 --> 00:46:02,530 那么，如果我们不是介绍了这第三个维度？ 766 00:46:02,530 --> 00:46:06,400 这种技术通常被称为单独的链接，或链。 767 00:46:06,400 --> 00:46:10,030 是怎样的一个哈希表，这个表结构， 768 00:46:10,030 --> 00:46:13,450 你的表是一个指针数组。 769 00:46:13,450 --> 00:46:18,230 但是，这些指针指向的是你猜怎么着？ 770 00:46:18,230 --> 00:46:21,970 链表。那么，如果我们把这些世界最好的吗？ 771 00:46:21,970 --> 00:46:26,500 我们使用数组的初始指标 772 00:46:26,500 --> 00:46:32,070 到的数据结构，这样我们就可以即刻前往[0] [1]，[30]等等， 773 00:46:32,070 --> 00:46:36,480 但是，我们有一定的灵活性，我们可以适合梅艳芳，爱丽丝和亚当 774 00:46:36,480 --> 00:46:38,630 和任何其他的名称， 775 00:46:38,630 --> 00:46:43,470 我们，而不是让其他轴增长到任意。 776 00:46:43,470 --> 00:46:47,340 截至周一，我们终于有链接列表，表达能力。 777 00:46:47,340 --> 00:46:49,530 我们可以任意增长数据结构。 778 00:46:49,530 --> 00:46:52,450 另外，我们可以只让一个巨大的二维数组， 779 00:46:52,450 --> 00:46:57,190 一个2维阵列中的行，但是这将是一个可怕的情况，如果一个 780 00:46:57,190 --> 00:47:01,280 不够大，更多的人，他的名字恰好开始A. 781 00:47:01,280 --> 00:47:04,200 上帝保佑，我们必须重新分配一个巨大的二维结构 782 00:47:04,200 --> 00:47:06,600 正因为有这么多的人命名为A， 783 00:47:06,600 --> 00:47:09,480 特别是当有所以几个人命名为Z东西。 784 00:47:09,480 --> 00:47:12,170 这将是一个非常稀疏的数据结构。 785 00:47:12,170 --> 00:47:15,400 因此，它不是完美的，任何手段，但至少现在我们有能力 786 00:47:15,400 --> 00:47:19,090 Alice或梅艳芳属于立即找到， 787 00:47:19,090 --> 00:47:21,090 至少在纵轴条款， 788 00:47:21,090 --> 00:47:25,850 然后我们只需要决定把梅艳芳或翘在这个链表。 789 00:47:25,850 --> 00:47:32,480 如果我们不关心排序的事情，如何迅速，我们将爱丽丝成这样的结构吗？ 790 00:47:32,480 --> 00:47:35,370 这是恒定的时间。我们的指数为[0]，如果没有一个人的存在， 791 00:47:35,370 --> 00:47:37,550 艾丽斯在该链接的列表的开始。 792 00:47:37,550 --> 00:47:40,000 但是，这不是一个大问题。因为如果梅艳芳然后是沿 793 00:47:40,000 --> 00:47:42,160 一些步数后，梅艳芳属于吗？ 794 00:47:42,160 --> 00:47:45,140 那么，[0]。面向对象编程。爱丽丝已经在该链接的列表。 795 00:47:45,140 --> 00:47:47,760 >> 但是，如果我们不关心这些名称进行排序， 796 00:47:47,760 --> 00:47:53,580 我们就可以将爱丽丝过来，插入梅艳芳，但即使是恒定的时间。 797 00:47:53,580 --> 00:47:57,010 即使有爱丽丝和亚当和所有这些其他的地名， 798 00:47:57,010 --> 00:47:59,410 它不是真正的转移他们的身体。为什么呢？ 799 00:47:59,410 --> 00:48:04,090 因为我们刚刚在这里做的与链表，谁知道，这些节点呢？ 800 00:48:04,090 --> 00:48:06,550 所有你必须​​做的是移动的面包屑。 801 00:48:06,550 --> 00:48:10,930 将周围的箭头，你没有实际移动周围的任何数​​据。 802 00:48:10,930 --> 00:48:14,610 因此，我们可以将梅艳芳，在这种情况下，瞬间。固定的时间。 803 00:48:14,610 --> 00:48:20,250 因此，我们有固定时间的查找，插入固定时间的像梅艳芳的人。 804 00:48:20,250 --> 00:48:22,740 但一种过于简单化的世界。 805 00:48:22,740 --> 00:48:28,510 如果我们以后要找到爱丽丝吗？ 806 00:48:28,510 --> 00:48:31,050 如果我们以后要找到爱丽丝吗？ 807 00:48:31,050 --> 00:48:35,690 多少个步骤是，将要采取的吗？ 808 00:48:35,690 --> 00:48:37,850 [学生回答，不知所云] 809 00:48:37,850 --> 00:48:40,950 没错。爱丽丝还没链表中的人数。 810 00:48:40,950 --> 00:48:45,420 所以它不是很完美，因为我们的数据结构，再有这样的垂直通道 811 00:48:45,420 --> 00:48:50,240 然后它有这些链表挂 - 实际上，让我们画一个数组。 812 00:48:50,240 --> 00:48:56,020 这些链接列表，挂它看起来有点像这样。 813 00:48:56,020 --> 00:48:59,110 但问题是，如果爱丽丝和亚当和所有这些其他的地名 814 00:48:59,110 --> 00:49:01,720 结束了越来越多的那边， 815 00:49:01,720 --> 00:49:04,810 发现有人可以结束了一堆的步骤， 816 00:49:04,810 --> 00:49:06,670 bcause你必须遍历链表， 817 00:49:06,670 --> 00:49:08,090 这是一个线性操作。 818 00:49:08,090 --> 00:49:14,270 所以，真的，那么，最终的插入时间是O（n），其中n是列表中的元素的数量。 819 00:49:14,270 --> 00:49:21,780 除以，让我们随意m，其中m是多少链表 820 00:49:21,780 --> 00:49:24,500 ，我们已经在此垂直轴。 821 00:49:24,500 --> 00:49:27,180 换句话说，如果我们真正假设均匀分布的名称， 822 00:49:27,180 --> 00:49:30,150 完全不现实的。显然有比别人更多一些字母。 823 00:49:30,150 --> 00:49:32,580 >> 但是，如果我们假定为均匀分布的那一刻起， 824 00:49:32,580 --> 00:49:37,350 我们有N总的人，和m总链 825 00:49:37,350 --> 00:49:40,630 提供给我们，然后每个这些链的长度 826 00:49:40,630 --> 00:49:44,380 相当简单的将是的总量中，n链的数目除以。 827 00:49:44,380 --> 00:49:48,900 所以N / M。但在这里，我们可以将所有数学聪明。 828 00:49:48,900 --> 00:49:53,030 m是一个常数，因为有一个固定数量的这些。 829 00:49:53,030 --> 00:49:54,620 你会开始申报您的阵列， 830 00:49:54,620 --> 00:49:58,450 我们不调整的垂直轴。根据定义，即固定不变的。 831 00:49:58,450 --> 00:50:01,220 这是唯一的横轴，可以这么说，这改变。 832 00:50:01,220 --> 00:50:04,760 因此从技术上讲，这是一个常数。所以，现在，在插入时间 833 00:50:04,760 --> 00:50:09,700 几乎是O（n）的。 834 00:50:09,700 --> 00:50:12,410 这样就不会觉得所有的东西更好。 835 00:50:12,410 --> 00:50:14,940 但是，什么是真相吗？那么，这一切的时间，几个星期， 836 00:50:14,940 --> 00:50:20,640 我们一直在说为O（n²）。 O（N），2×N“， - N，再除以2。 。 。 ECH。 837 00:50:20,640 --> 00:50:23,580 这是仅仅局限于N²。但现在，这部分的学期， 838 00:50:23,580 --> 00:50:25,560 我们可以开始再次谈论真实的世界。 839 00:50:25,560 --> 00:50:31,520 N / M是绝对的速度比仅仅局限于N孤独。 840 00:50:31,520 --> 00:50:35,170 如果你有一万余名，你将它们分解为多个桶 841 00:50:35,170 --> 00:50:37,820 所以，你有这些链中只有10名， 842 00:50:37,820 --> 00:50:41,670 绝对搜索的十件事将是快千余件事情。 843 00:50:41,670 --> 00:50:43,740 因此，即将到来的习题会向你挑战 844 00:50:43,740 --> 00:50:46,100 即使认为正是，是啊， 845 00:50:46,100 --> 00:50:49,520 渐近和数学，这还只是线性的， 846 00:50:49,520 --> 00:50:51,700 它吸收一般时试图找东西。 847 00:50:51,700 --> 00:50:54,530 在现实中，它要快于 848 00:50:54,530 --> 00:50:56,520 因为这个除数。 849 00:50:56,520 --> 00:50:58,310 因此，有再一次将是这种权衡 850 00:50:58,310 --> 00:51:01,390 理论和现实之间的冲突， 851 00:51:01,390 --> 00:51:03,550 和一个旋钮将在本学期开始转向在这一点上 852 00:51:03,550 --> 00:51:07,510 是更现实的一个，因为我们准备semster的结束， 853 00:51:07,510 --> 00:51:09,280 为大家介绍一下世界的网络编程， 854 00:51:09,280 --> 00:51:11,530 真的，性能要算，因为你的用户要 855 00:51:11,530 --> 00:51:14,880 开始感受和欣赏糟糕的设计决策。 856 00:51:14,880 --> 00:51:19,950 >> 那么，你如何去实施一个链接 - 哈希表的31个元素呢？ 857 00:51:19,950 --> 00:51:22,600 前面的例子中任意生日。 858 00:51:22,600 --> 00:51:26,190 如果有一个人生日1月1日或2月1日，我们将把它们放在这个桶。 859 00:51:26,190 --> 00:51:28,960 如果这是1月2日，2月2日，3月2日，我们将把它们放在这个桶。 860 00:51:28,960 --> 00:51:32,220 这就是为什么它是31。如何声明一个哈希表？ 861 00:51:32,220 --> 00:51:37,480 它可以是非常简单的，的节点*表是我的任意名称，[31]。 862 00:51:37,480 --> 00:51:42,400 这给了我31节点的指针， 863 00:51:42,400 --> 00:51:45,370 ，让我有31个指针链表 864 00:51:45,370 --> 00:51:48,800 即使这些链是最初为NULL。 865 00:51:48,800 --> 00:51:54,860 把我想要什么，如果我想存储“爱丽丝”，“鲍勃”，“查理”吗？ 866 00:51:54,860 --> 00:51:57,010 好了，我们需要用这些东西在一个结构 867 00:51:57,010 --> 00:52:00,530 因为我们需要爱丽丝来指向给Bob，指向查理，等等。 868 00:52:00,530 --> 00:52:04,940 我们不能只单独的名字，这样我就可以创建一个新的结构，称为节点在这里。 869 00:52:04,940 --> 00:52:08,310 >> 什么是实际的节点？在这个新的链表节点是什么？ 870 00:52:08,310 --> 00:52:11,840 第一件事情，叫字，是人的名字。 871 00:52:11,840 --> 00:52:14,340 据推测，LENGTH，涉及一个人的名字的最大长度， 872 00:52:14,340 --> 00:52:18,210 不管它是什么，20，30，40个字符疯狂的角落的情况下， 873 00:52:18,210 --> 00:52:22,680 +1是为了什么？这仅仅是额外的NULL字符，\ 0。 874 00:52:22,680 --> 00:52:27,410 因此，这个节点是包装内的“东西”本身， 875 00:52:27,410 --> 00:52:29,640 但同时也宣告了一个指针称为未来 876 00:52:29,640 --> 00:52:32,580 这样我们就可以链Alice给Bob查理等等。 877 00:52:32,580 --> 00:52:36,700 可以为NULL，但不一定必须。 878 00:52:36,700 --> 00:52:40,110 这些哈希表的任何问题吗？是吗？ 879 00:52:40,110 --> 00:52:46,190 [学生提问，不知所云]数组 - 很好的问题。 880 00:52:46,190 --> 00:52:50,120 字符数组中的字，而不是仅仅的char *这是为什么？ 881 00:52:50,120 --> 00:52:53,830 在这个有点乱的例子，我不想诉诸 882 00:52:53,830 --> 00:52:56,190 对malloc为原来的名称。 883 00:52:56,190 --> 00:52:59,530 我想声明的字符串的最大内存量 884 00:52:59,530 --> 00:53:06,020 这样我就可以复制到结构爱丽丝\ 0，而不必处理malloc和free之类的。 885 00:53:06,020 --> 00:53:11,710 但我能做到这一点，如果我想成为更加自觉地空间使用。这个问题问得好。 886 00:53:11,710 --> 00:53:14,780 因此，让我们尝试概括距离 887 00:53:14,780 --> 00:53:18,350 和聚焦今天的其余部分上的数据结构，更一般 888 00:53:18,350 --> 00:53:21,170 和其他问题，我们能够解决使用相同的基本面 889 00:53:21,170 --> 00:53:24,590 即使自己的数据结构可能有所不同，在他们的资料。 890 00:53:24,590 --> 00:53:27,910 >> 因此，原来在计算机科学中，树是非常常见的。 891 00:53:27,910 --> 00:53:29,760 你能想到的树排序，就像一个家庭树， 892 00:53:29,760 --> 00:53:31,830 那里的一些根，有的女家长或族长， 893 00:53:31,830 --> 00:53:34,540 爷爷奶奶或或更早回来， 894 00:53:34,540 --> 00:53:38,880 下面是和爸爸妈妈或各种兄弟姐妹等。 895 00:53:38,880 --> 00:53:42,500 因此，一个树结构的节点和它的孩子， 896 00:53:42,500 --> 00:53:45,260 通常每个节点的0个或更多的孩子。 897 00:53:45,260 --> 00:53:47,320 还有一些的专用术语，你在这张照片上看到的 898 00:53:47,320 --> 00:53:50,630 任何小的孩子或孙子的边缘 899 00:53:50,630 --> 00:53:52,330 谁没有从他们身上发出的箭头， 900 00:53:52,330 --> 00:53:55,070 这些是所谓的叶子，并在里面的任何人 901 00:53:55,070 --> 00:53:58,790 是一个内部节点，沿着这些线路，你可以把它叫做什么。 902 00:53:58,790 --> 00:54:01,430 但是，这种结构是很常见的。这其中的任意一点。 903 00:54:01,430 --> 00:54:04,930 我们有一个孩子在左边，我们有三个孩子的权利， 904 00:54:04,930 --> 00:54:06,830 两个孩子的左下角。 905 00:54:06,830 --> 00:54:10,740 因此，我们可以有不同大小的树木，但如果我们开始规范的东西， 906 00:54:10,740 --> 00:54:15,330 您可能还记得二进制从帕特里克的视频上搜索从以前的短 907 00:54:15,330 --> 00:54:19,490 在线，二进制搜索不具有要实现的一个数组 908 00:54:19,490 --> 00:54:21,410 或纸片在黑板上。 909 00:54:21,410 --> 00:54:25,490 假设你想在一个更复杂的数据结构来存储您的数字。 910 00:54:25,490 --> 00:54:27,680 你可以创建一个这样的树。 911 00:54:27,680 --> 00:54:35,290 你可以有一个在C中声明的节点，该节点可以有它的内部的至少两种元素。 912 00:54:35,290 --> 00:54:39,470 一个是你要存储的号码，另一个是 - 好了，我们需要一个更。 913 00:54:39,470 --> 00:54:41,540 另一种是它的孩子。 914 00:54:41,540 --> 00:54:45,150 因此，这里的另一种数据结构。这时候，一个节点被定义为存储号码Ň 915 00:54:45,150 --> 00:54:49,060 然后两个指针;左孩子和右孩子。 916 00:54:49,060 --> 00:54:52,100 他们不是任意的。这棵树有什么有趣的吗？ 917 00:54:52,100 --> 00:55:00,550 >> 在已经奠定了这一点，或如何帕特里克奠定了它在他的影片有什么模式？ 918 00:55:00,550 --> 00:55:02,790 这是一种明显的，有一些排序怎么回事， 919 00:55:02,790 --> 00:55:04,460 但什么是简单的规则吗？是吗？ 920 00:55:04,460 --> 00:55:08,350 [学生回答，不知所云] 921 00:55:08,350 --> 00:55:12,040 完美的。如果你看一眼这，你会看到在左侧的小数字， 922 00:55:12,040 --> 00:55:14,690 大号码的左侧，但为每个节点，这是真的。 923 00:55:14,690 --> 00:55:20,370 对于每个节点，其左子小于，大于它的右子树。 924 00:55:20,370 --> 00:55:25,210 这意味着什么，现在是，如果我要搜索这个数据结构，也就是说，44号， 925 00:55:25,210 --> 00:55:29,320 我必须从根开始，因为所有的这些更复杂的数据结构现在， 926 00:55:29,320 --> 00:55:31,910 我们只有一件事，有一个指针开始。 927 00:55:31,910 --> 00:55:35,010 在这种情况下，一开始是根。这不是左端， 928 00:55:35,010 --> 00:55:39,530 它的这种结构的根目录中。所以我在这里看到的是55岁，和我期待的44。 929 00:55:39,530 --> 00:55:41,430 我想往哪个方向去？ 930 00:55:41,430 --> 00:55:45,680 嗯，我想往左走，因为很明显，在右边将是太大了。 931 00:55:45,680 --> 00:55:49,050 所以，注意在这里，你样的概念上砍了一半的树 932 00:55:49,050 --> 00:55:51,700 因为你永远也不会下降的右手边。 933 00:55:51,700 --> 00:55:55,410 所以，现在我从55到33。这是过于小了一些。 934 00:55:55,410 --> 00:56:01,590 我在寻找44，但现在我知道，如果44是在这棵树，我可以去显然是正确的。 935 00:56:01,590 --> 00:56:04,460 所以，再一次，我修剪树的一半。 936 00:56:04,460 --> 00:56:06,780 这几乎是相同的概念上的电话簿。 937 00:56:06,780 --> 00:56:09,510 这是相同的，我们所做的在黑板上的文件， 938 00:56:09,510 --> 00:56:13,940 但它是一个更复杂的结构，使我们能够真正做到 939 00:56:13,940 --> 00:56:16,880 这种分而治之的算法设计， 940 00:56:16,880 --> 00:56:19,420 而事实上，穿越这样的结构 - 哎呦。 941 00:56:19,420 --> 00:56:22,870 遍历这样的结构，它只是“走这条路还是走那条路。” 942 00:56:22,870 --> 00:56:26,870 意味着所有的代码，弯曲你的心灵第一次执行时第 943 00:56:26,870 --> 00:56:31,270 在家里或步行通过，为二进制搜索，使用递归或迭代， 944 00:56:31,270 --> 00:56:35,060 这是一个痛苦的脖子上。中间的元素，然后做你的四舍五入向上或向下。 945 00:56:35,060 --> 00:56:39,230 >> 有一个美丽了，因为我们现在可以再次使用递归， 946 00:56:39,230 --> 00:56:43,760 但更干净。事实上，如果你在55号和您想要寻找44， 947 00:56:43,760 --> 00:56:48,450 在这种情况下，你向左走，然后你会怎么做？您可以运行相同的算法。 948 00:56:48,450 --> 00:56:51,560 检查节点的值，然后你去左边或右边。 949 00:56:51,560 --> 00:56:53,670 然后检查节点的值，向左走还是向右。 950 00:56:53,670 --> 00:56:56,710 这是非常适合递归。 951 00:56:56,710 --> 00:57:00,920 因此，即使在过去，我们已经做了一些非常随意的，涉及递归的例子 952 00:57:00,920 --> 00:57:03,430 没有需要的是递归的，数据钢结构， 953 00:57:03,430 --> 00:57:07,820 特别是树木，这是一个完美的应用这个想法的一个问题， 954 00:57:07,820 --> 00:57:12,920 缩小，然后解决相同类型的，但较小的，程序。 955 00:57:12,920 --> 00:57:14,590 >> 所以，我们可以引进另一种数据结构。 956 00:57:14,590 --> 00:57:18,760 这一个是在第一眼就看神秘的，但是这一次是惊人的。 957 00:57:18,760 --> 00:57:25,090 因此，这是一个数据结构称为特里，特里，这是继承的词检索， 958 00:57:25,090 --> 00:57:30,210 没有明显的重试时间间隔，但是这就是世人所谓的这些东西。尝试。 T-R-I-E。 959 00:57:30,210 --> 00:57:35,190 它是一个某种形式的树结构，但在一个Trie树的每个节点 960 00:57:35,190 --> 00:57:41,280 似乎是什么？这是一个有点误导，因为它是一种简称。 961 00:57:41,280 --> 00:57:45,960 但它看起来像这trie树中的每个节点实际上是一个数组。 962 00:57:45,960 --> 00:57:48,840 即使此图的作者并没有表现出它， 963 00:57:48,840 --> 00:57:54,130 在这种情况下，这个线索是一种数据结构，其目的在生活中是存储词语 964 00:57:54,130 --> 00:57:57,330 A-L-I-C-E或B-O-B等。 965 00:57:57,330 --> 00:58:02,480 的方式，此数据存储Alice和Bob和Charlie和梅艳芳等等 966 00:58:02,480 --> 00:58:06,970 是使用一个数组来存储，爱丽丝在特里， 967 00:58:06,970 --> 00:58:09,820 它看起来像一个数组的根节点开始， 968 00:58:09,820 --> 00:58:12,080 它被写在速记符号。 969 00:58:12,080 --> 00:58:15,070 笔者省略，ABCDEFG，因为有没有名字。 970 00:58:15,070 --> 00:58:19,150 他们仅表现为M和P和T，但在这种情况下， 971 00:58:19,150 --> 00:58:22,780 让搬走Alice和Bob和Charlie一些名字在这里。 972 00:58:22,780 --> 00:58:25,670 麦克斯韦实际上是在此图中。 973 00:58:25,670 --> 00:58:29,570 那么，如何做的作者店M-X-W-E-L-L？ 974 00:58:29,570 --> 00:58:36,990 他或她的根节点开始，并到[M]，因此，大约13时，13日在数组中的位置。 975 00:58:36,990 --> 00:58:40,750 然后从那里，有一个指针。 976 00:58:40,750 --> 00:58:42,760 导致另一个数组的指针。 977 00:58:42,760 --> 00:58:47,880 从那里到该数组的索引位置A，作为描绘在左上角， 978 00:58:47,880 --> 00:58:52,250 那么他或她跟着到另一个数组，指针， 979 00:58:52,250 --> 00:58:55,460 去的指针位置X. 980 00:58:55,460 --> 00:58:59,840 然后，在下一数组位置W，E，L，L，等等， 981 00:58:59,840 --> 00:59:03,090 最后，让我们真正尝试把图片。 982 00:59:03,090 --> 00:59:05,380 节点看起来像在代码中做了什么？ 983 00:59:05,380 --> 00:59:11,820 trie树中的一个节点包含多个节点的指针数组。 984 00:59:11,820 --> 00:59:16,090 但也有，至少在这个实现了某种形式的布尔值。 985 00:59:16,090 --> 00:59:18,770 我碰巧把它称为is_word。为什么呢？ 986 00:59:18,770 --> 00:59:22,670 因为当你插入麦克斯韦，你不插入 987 00:59:22,670 --> 00:59:25,300 任何东西到这个数据结构。 988 00:59:25,300 --> 00:59:27,480 你不写M.你不写X. 989 00:59:27,480 --> 00:59:30,240 你做的是以下指针。 990 00:59:30,240 --> 00:59:33,360 表示M，接着是表示A的指针，该指针的指针，该指针 991 00:59:33,360 --> 00:59:36,310 然后指针，表示X，则W，E，L，L， 992 00:59:36,310 --> 00:59:41,950 但结束时你需要做的是去，检查排序，我达到了这个位置。 993 00:59:41,950 --> 00:59:45,560 有在数据结构中的一个词，在这里结束。 994 00:59:45,560 --> 00:59:48,190 >> 那么什么是特里真的是充满了笔者选择了代表 995 00:59:48,190 --> 00:59:51,880 这些小三角总站。 996 00:59:51,880 --> 00:59:56,470 这只是意味着这样一个事实，这个三角形在这里，这个布尔值true; 997 00:59:56,470 --> 00:59:59,200 也就是说，如果你往后走的树， 998 00:59:59,200 --> 01:00:02,420 这意味着名为Maxwell是在这一个字。 999 01:00:02,420 --> 01:00:04,870 但这个词foo的，例如， 1000 01:00:04,870 --> 01:00:07,970 是不是在树中，因为如果我开始在这里的根节点在顶部， 1001 01:00:07,970 --> 01:00:14,030 有没有F指针，无O指针，无O指针。 foo不是在这本字典的名称。 1002 01:00:14,030 --> 01:00:22,460 但相反的是，图灵，T-U-R-I-N-G。同样，我没有存储t或u r或i或N或G。 1003 01:00:22,460 --> 01:00:29,820 但我没有商店这个数据结构中的值的正确的方法，在这里在此节点 - 树 1004 01:00:29,820 --> 01:00:33,030 这个布尔值is_word设置为true。 1005 01:00:33,030 --> 01:00:35,740 因此，trie树是种很有趣的元结构， 1006 01:00:35,740 --> 01:00:39,810 你不是真正的存储的话自己这种字典。 1007 01:00:39,810 --> 01:00:45,100 要清楚，你只是存储“是”或“否”，有一个词在这里结束。 1008 01:00:45,100 --> 01:00:46,430 >> 现在有什么含义？ 1009 01:00:46,430 --> 01:00:51,120 如果你有15万字，在字典中，你想存储在内存中 1010 01:00:51,120 --> 01:00:53,400 使用类似的链接列表， 1011 01:00:53,400 --> 01:00:56,870 你将有15节点的链表。 1012 01:00:56,870 --> 01:01:00,250 发现这些词的字母顺序排列，可能需要O（n）的时间。 1013 01:01:00,250 --> 01:01:04,370 线性时间。但是，在这里的情况下的线索， 1014 01:01:04,370 --> 01:01:09,210 什么是运行时间找到一个词？ 1015 01:01:09,210 --> 01:01:17,390 原来，这里的美景，即使你已经在这本字典有149,999个字， 1016 01:01:17,390 --> 01:01:20,170 如使用该数据结构实现， 1017 01:01:20,170 --> 01:01:25,560 找到或插入多一个人进认为，像爱丽丝，爱丽丝需要多少时间？ 1018 01:01:25,560 --> 01:01:30,640 嗯，这是只有5个，也许6个步骤的尾随字符。 1019 01:01:30,640 --> 01:01:32,880 由于结构中的其他名称presense 1020 01:01:32,880 --> 01:01:35,340 没有得到中的插入爱丽丝的方式。 1021 01:01:35,340 --> 01:01:39,640 此外，寻找爱丽丝曾经在这本字典有15万字 1022 01:01:39,640 --> 01:01:41,960 在用自己的方式寻找爱丽丝在没有得到， 1023 01:01:41,960 --> 01:01:46,880 因为Alice。 。 。 。 。在这里，因为我发现一个布尔值。 1024 01:01:46,880 --> 01:01:50,920 如果没有布尔值true，则Alice是不是这个数据结构中的话。 1025 01:01:50,920 --> 01:01:56,220 换言之，找东西和插入到这个新的东西的运行时间 1026 01:01:56,220 --> 01:02:01,920 数据结构的特里是O - 它不是N。 1027 01:02:01,920 --> 01:02:05,730 因为presense 15万人没有“爱丽丝梦游仙境”的影响，它似乎。 1028 01:02:05,730 --> 01:02:11,560 因此，让我们把它k，其中k是一个英语单词的最大长度 1029 01:02:11,560 --> 01:02:14,050 这是通常不超过20的东西字符。 1030 01:02:14,050 --> 01:02:17,940 因此，k是常数。所以我们现在似乎已经找到了圣杯 1031 01:02:17,940 --> 01:02:26,000 是的特里，不变的插入，查找，删除。 1032 01:02:26,000 --> 01:02:29,170 由于已经在结构的数目的事情， 1033 01:02:29,170 --> 01:02:32,600 这是甚至没有亲临现场。同样，他们只是排序的检查，“是”或“否”， 1034 01:02:32,600 --> 01:02:35,050 没有影响其未来的运行时间。 1035 01:02:35,050 --> 01:02:37,940 >> 但还有了一个catch，否则我们不会浪费这么多时间 1036 01:02:37,940 --> 01:02:41,460 在所有这些其他的数据结构，最终得到的秘密是惊人的。 1037 01:02:41,460 --> 01:02:46,410 所以，我们要付出什么样的价格在这里实现这一伟大吗？空间。 1038 01:02:46,410 --> 01:02:49,010 这件事是巨大的。的原因，笔者 1039 01:02:49,010 --> 01:02:52,400 并不会出现在这里，请注意，所有的这些东西，看起来像阵列， 1040 01:02:52,400 --> 01:02:55,400 他没有画出其余的树，其余的特里， 1041 01:02:55,400 --> 01:02:58,060 因为他们只是不相关的故事。 1042 01:02:58,060 --> 01:03:01,870 但是，所有的这些节点是超级宽，树中的每个节点占用 1043 01:03:01,870 --> 01:03:07,780 26实际上，可能是27个字符，因为在这种情况下，我包括空间中的所有格符号 1044 01:03:07,780 --> 01:03:09,980 这样我们就可以有apostrophized的话。 1045 01:03:09,980 --> 01:03:14,450 在这种情况下，这些都是宽阵列。因此，即使他们没有picutured， 1046 01:03:14,450 --> 01:03:18,190 这占用了大量的内存。 1047 01:03:18,190 --> 01:03:20,670 这可能是罚款，especilly在现代的硬件， 1048 01:03:20,670 --> 01:03:25,650 但是这是一个折衷。我们得到了更短的时间内，花更多的空间。 1049 01:03:25,650 --> 01:03:28,580 那么，这是怎么回事？ 1050 01:03:28,580 --> 01:03:32,640 好吧，让我们做的 - 让我们在这里看到的。 1051 01:03:32,640 --> 01:03:39,510 让我们做一个跳转到这个家伙在这里。 1052 01:03:39,510 --> 01:03:43,450 >> 不管你相信与否，尽可能多的乐趣为C已经有一段时间了， 1053 01:03:43,450 --> 01:03:48,130 我们到达点在本学期的时间过渡到更现代的东西。 1054 01:03:48,130 --> 01:03:50,950 在更高层次上的事情。即使在接下来的几个星期 1055 01:03:50,950 --> 01:03:54,580 我们仍然会继续埋头在世界上的指针和内存管理 1056 01:03:54,580 --> 01:03:57,210 得到安慰，使我们可以再建， 1057 01:03:57,210 --> 01:04:01,270 比赛结束，最终还是引进，具有讽刺意味的​​是，这不是语言。 1058 01:04:01,270 --> 01:04:03,330 我们会花10分钟，谈论HTML一样。 1059 01:04:03,330 --> 01:04:05,950 所有的HTML是一种标记语言，一种标记语言是什么 1060 01:04:05,950 --> 01:04:10,220 这些系列开放式支架和封闭括号，说'这个大胆的“ 1061 01:04:10,220 --> 01:04:12,000 “这斜体”，“使这个中心的。” 1062 01:04:12,000 --> 01:04:14,250 这是不是所有的智力有趣的，但它是超级有用的。 1063 01:04:14,250 --> 01:04:16,650 它肯定是无所不在的这些天。 1064 01:04:16,650 --> 01:04:19,450 但是，什么是功能强大的HTML世界，更普遍的Web编程， 1065 01:04:19,450 --> 01:04:25,910 建立动态的东西的语言，如PHP或Python或Ruby或Java或C＃编写代码。 1066 01:04:25,910 --> 01:04:30,360 真的，无论你选择的语言，并动态地生成HTML。 1067 01:04:30,360 --> 01:04:32,960 被称为CSS动态生成的东西。 1068 01:04:32,960 --> 01:04:35,810 级联样式表，这也是对美学。 1069 01:04:35,810 --> 01:04:41,360 因此，即使今天，如果我去一些喜欢熟悉的Google.com网站， 1070 01:04:41,360 --> 01:04:46,100 我去查看，开发人员，查看源代码，也许你以前做过， 1071 01:04:46,100 --> 01:04:49,800 但要查看源代码，这东西可能看起来很神秘的。 1072 01:04:49,800 --> 01:04:55,320 但是，这是基本的代码，实现Google.com。 1073 01:04:55,320 --> 01:04:57,940 在前端。而实际上这是蓬松的美学的东西。 1074 01:04:57,940 --> 01:05:01,740 这是CSS在这里。如果我继续向下滚动，我们会得到一些颜色编码的东西。 1075 01:05:01,740 --> 01:05:06,890 这是HTML。谷歌的代码看起来像一个烂摊子，但如果我真的打开不同的窗口， 1076 01:05:06,890 --> 01:05:09,380 在此，我们可以看到一些结构。 1077 01:05:09,380 --> 01:05:12,640 如果我打开这件事，请注意，这是一个有点更具可读性。 1078 01:05:12,640 --> 01:05:16,850 我们不久会看到这个标签，[字]是一个标签， 1079 01:05:16,850 --> 01:05:23,520 HTML，头部，身体，DIV，脚本，文本区，跨度为中心的分区。 1080 01:05:23,520 --> 01:05:26,770 这也有几分神秘的前瞻性乍看之下， 1081 01:05:26,770 --> 01:05:30,890 但这个烂摊子遵循一定的模式和重复的模式， 1082 01:05:30,890 --> 01:05:33,850 因此，一旦我们得到的基本知识，你就可以写这样的代码 1083 01:05:33,850 --> 01:05:37,550 然后操作使用另一种语言，称为JavaScript代码。 1084 01:05:37,550 --> 01:05:40,440 JavaScript是一种语言，运行在浏览器 1085 01:05:40,440 --> 01:05:44,380 今天，我们用哈佛的课程，该课程的购物工具，谷歌地图使用 1086 01:05:44,380 --> 01:05:48,660 给你一大堆的活力，Facebook让你显示的即时状态更新， 1087 01:05:48,660 --> 01:05:51,430 Twitter的使​​用它来显示你的鸣叫瞬间。 1088 01:05:51,430 --> 01:05:53,820 所有这一切，我们将开始埋头进来。 1089 01:05:53,820 --> 01:05:57,190 但到了那里，我们需要了解一些关于互联网。 1090 01:05:57,190 --> 01:06:01,130 这个夹子在这里只是一分钟之久，现在让我们假设这是，其实， 1091 01:06:01,130 --> 01:06:08,380 如何在互联网什么来捉弄人。我给你“勇士的净。” 1092 01:06:08,380 --> 01:06:14,720 >> [♫合唱音乐的慢♫] 1093 01:06:14,720 --> 01:06:20,450 男解说员，他带着一个消息。 1094 01:06:20,450 --> 01:06:23,770 随着自己的协议。 1095 01:06:23,770 --> 01:06:37,270 [♫更快的电子音乐♫] 1096 01:06:37,270 --> 01:06:41,330 他来到一个世界的酷防火墙的，漠不关心的路由器， 1097 01:06:41,330 --> 01:06:45,690 远远比死还要痛苦和危险。 1098 01:06:45,690 --> 01:06:55,400 他速度非常快。他的强者。他是TCP / IP，和他有你的地址。 1099 01:06:55,400 --> 01:06:59,250 勇士的净。 1100 01:06:59,250 --> 01:07:05,290 [马兰]下周。互联网。 Web编程。这是CS50。 1101 01:07:05,290 --> 01:07:08,290 [CS50.TV]