[音乐播放]
>> DAVID马兰：这是CS50。
这是二者的开始和 end--像literally--差不多结束
六个星期。
>> 我想我会分享 一个有趣的事实点点。
我从一本拉到了 过去学期的数据集。
你可能还记得，我们要求你在每个 P组的形式，如果你已经在网上看过
或者，如果你已经亲自出席。
这里是数据。
所以今天是非常可预测性。
但是，我们想花一点 然而时间与您联系。
有人想猜测为什么这个 图中是那么的锯齿，上下，上下，
所以一贯？
做什么每个峰 和波谷代表什么？
>> 听众：[听不清]
DAVID马兰：确实是这样。
而更有趣的是，上帝保佑， 我们举行一次讲座上周五
在学期的开始， 这就是我们看到发生了什么。
所以今天，我们参加了位 更多关于数据结构。
并给你更多的是固体 对问题的思维模式五，
这就是现在了。
拼写错误，其中，我们将 交给你一个文本文件，大约10万
再加上英语单词， 你将有
弄清楚如何巧妙地加载它们 入存储器，到RAM中，使用一些数据
您所选择的结构。
>> 现在，这样的一个数据结构可以 是，但可能不应该，
在相当简单的链表， 这是我们去年推出的时间。
和一个链表至少有 1优势的阵列。
什么是一个优点 链表可以说是？
>> 听众：插入。
>> DAVID马兰：插入。
你是什​​么意思？
>> 听众：任何位置 名单[听不清]。
>> DAVID马兰：好。
所以，你可以插入一个元素的地方 要在列表的中间
无需洗牌什么， 我们得出的结论，在我们的分类
讨论，是不是 一定是好事，
因为它需要时间来实际移动 所有这些人的左边或右边。
所以用一个链表，你可以 刚分配使用malloc，一个新的节点，
然后更新了几个 pointers--二，三次手术max--
而我们能够插槽人 中的任意位置成一个列表。
>> 还有什么是有利的 关于链表？
是吗？
>> 听众：[听不清]
DAVID马兰：完美。
完美的。
这真是动力。
和你没有犯， 事先，以一些固定的大小
内存块，就像你会 用一个数组，则上行其中
是，你只能分配上的节点 需求从而只用尽可能多的空间
当你真正需要的。
通过与数组相反，你可能会 一不小心分配太少。
然后它只是去 是在颈部疼痛
重新分配一个新的更大的阵列中，复制 一切都结束了，释放旧阵列，
然后将您的业务。
或者更糟的是，你可能会分配方式 更多的内存比实际需要，
所以你将有一个非常 人烟稀少的阵列，可以这么说。
>> 因此，一个链表为您提供了这些 活力和灵活性的优势
与插入和缺失。
但肯定要有付出了代价。
其实，一个主题 探索对测验为零
一对夫妇的取舍 我们已经看到迄今。
那么，什么是付出了代价或 下行的链接列表？
是啊。
>> 听众：没有随机访问。
>> DAVID马兰：没有随机访问。
但谁在乎呢？
随机存取听起来并不引人注目。
>> 听众：[听不清]
DAVID马兰：没错。
如果你想有 一定的算法 -
让我真正提出 在特定的二进制搜索，这
是我们使用相当bit-- 如果你没有随机访问，
你不能这样做简单的算术题 找到喜欢的中间元件的
和跳跃的权利吧。
你代替不得不开始在所述第一 元素，并从左边线搜索
向右如果你想找到 中间的或任何其他元件。
>> 听众：它可能需要更多的内存。
>> DAVID马兰：需要更多的内存。
哪里是额外的 成本从内存中来？
>> 听众：[听不清]
DAVID马兰：没错。
在这里这种情况下，我们有 链表为整数，
但我们正在加倍 的内存量
我们需要同时存储这些指针。
现在少了一个大问题，因为 您的结构得到较大
与你存储不是一个数字，但 也许学生或其他物体。
但有一点毫无疑问依然存在。
等数的操作的 上链表被称为
是N--线性的大O。
之类的东西插入或搜索 或缺失的情况下的元素
正好是在最末端 无论是排序或不列表。
>> 有时候，你可能会得到幸运和 这些操作使下界
也可能是恒定的时间，如果你 一直在寻找的第一个元素，
例如。
但最终，我们承诺 实现了制胜法宝
数据结构，或 一些近似物，
通过固定时间的方式。
我们可以发现元素或添加元素 或删除列表中的元素？
我们将很很快就会看到。
而事实证明，一个 我们的机制
要开始用至今， 在P年利用设置5，
实际上是非常熟悉的。
例如，如果这是一串 考试图书，其中每一个
有一个学生的第一 它的名字和姓氏，
我去接他们从 在考试结束后，
而且他们都非常 多以随机的顺序，
我们要着手整理 这些考试，因此一旦分级
它只是一个极大的方便， 快交出他们回来了
学生按字母顺序排列。
什么你的直觉会 一摞这样的考试？
>> 好吧，如果你像我一样，你 可以看出这是米，
所以我要那种把这个成， 如果这是我的表或我的楼，
我的东西蔓延 out--或我的数组really--
我可以把所有的小姐在那里。
呵呵。
这里有一个答，所以我可能 把作为过来。
呵呵。
这里的另一个A.我要去 把该在这里。
这里有一个Z.这里是另一个M.所以 我可能会开始做桩这样的。
然后，也许我以后会​​去 样的，非常挑剔-LY排序
个别桩。
但问题是，我想看看 那个我手输入
我会做一些计算 基于该输入决定。
如果以A开头，把它放在那边。
如果它以Z开头，把它放在 在那里，一切都在两者之间。
>> 因此，这是一种技术，是 一般被称为hashing-- H-A-S-H--
这通常意味着要为 输入，并使用该输入来计算
的值，通常是一个数字，那 号为索引到一个存储
容器，如一个数组。
所以，换句话说，我可能有一个 散列函数，像我一样在我的脑海，
如果我看到有人的 谁的名字开始与A，
我要去映射 零在我的脑海。
如果我看到有人用Z，我 要映射至25日在我头上
然后它放入 最后最桩。
>> 现在，如果你觉得不是我的大脑 但一个C程序，有什么数字可能
你靠什么来实现同样的结果呢？
换句话说，如果 有ASCII字符A，
你如何确定 什么桶把它呢？
你可能不希望 把它放进水桶65，这
会像那边 没有很好的理由。
你在哪里要放 在它的ASCII值是多少？
你想去哪里做的ASCII 值拿出一个更聪明的水桶
把它呢？
>> 听众：负A.
>> DAVID马兰：是啊。
因此，减去或减 特别是65，如果是
资本A.或98，如果 这是一个小写。
所以这将允许我们，很 简单，非常算术，
把东西放到这样一个水桶。
所以，事实证明，我们实际上做 这个问题，以及即使有测验。
>> 所以，你可能还记得你的盘旋 封面上的教学老乡的名字。
而TF的名字被组织 到这些列的字母顺序，
好了，不管你信不信， 当所有80加上我们
聚在一起的那天晚上等级， 在我们的分级过程中的最后一步
是散列测验变成了大 地板在[听不清]空间
并奠定了大家的测验出来 在他们TF的确切顺序
在盖的名称，因为 那么它对于我们来说容易得多
通过使用线性搜索 搜索或某种聪明
对于TF找到他或 她的学生的测验。
>> 所以这个想法散列 你将看到的是
功能相当强大实际上是非常 司空见惯，非常直观，
很像也许是分而 征服是零一周。
我快进到黑客马拉松 几年前。
这是Zamyla和一对夫妇的 其他工作人员的问候学生
因为他们进来了。
我们有一大堆折叠 表中有与名称标签。
我们有名称标签组织 有喜欢当那边
和ZS的那边。
这样一来，课题组的一个非常巧妙 写这个的说明
为天。
而在本学期的第12周 所有的非常有意义，每个人都
知道该怎么做。
但是，任何时候，你已经 排队以同样的方式，
你实现 散列相同的概念。
因此，让我们正式那么一点点。
这里是一个数组。
它绘制的是一个小 宽只是描绘，直观，
我们不妨把字符串 在这样的事情。
这阵 显然是大小共26件。
而且东西被称为 表随意。
但是，这仅仅是一个艺术家的再现 什么样的哈希表可能。
>> 这样一个哈希表现在将要 是一个更高层次的数据结构。
在一天结束时 我们即将看到你
可以实现一个哈希表，该表 很像登机
在黑客马拉松就像这样 表用于排序的考试书籍。
但一个哈希表 这个排序高水平的
概念，可以使用一个数组 在底层实现它，
或者它可以使用一个长列表，或者甚至 也许一些其他的数据结构。
而现在这就是theme--回吐 一些基本的成分
就像一个数组，这个建筑 现在阻止长名单
，看到什么，我们可以建立 关于这些的顶端，像成分
成一个配方，使得越来越多的 有趣的和有用的最终结果。
>> 所以用哈希表 我们可以实现它
在内存中形象地这样，但 怎么可能它实际上被编码吗？
好吧，也许因为简单地说就是这个。
如果产能全部大写，只是 一些constant--比如26，
为alphabet--的26个字母 我可以叫我的变量表，
我也许会说，我要去 把炭明星在那里，或字符串。
因此，它是如此简单，如果你 要实现一个哈希表。
然而，这真的只是一个数组。
但同样，一个散列 表是现在我们所会
调用一个抽象数据类型，这只是 排序在最前面的概念分层
东西更现实 现在喜欢一个数组。
>> 现在，该怎么办才好 关于解决问题？
嗯，刚才我已经奢侈 这里有足够的表空间
这样我就可以把 测验的任何地方我想要的。
这样可能会去这里。
ZS可能会去这里。
小姐可能会去这里。
然后我有一些额外的空间。
但是，这是一个有点作弊权 因为现在这个表，如果我真的
想到这是一个数组，只是 一些将要固定的尺寸。
>> 所以，从技术上说，如果我拉 了另一名学生的测验
看看，哦，这个人的 名称与A开始过，
我有点想要把它放在那里。
但是，当我把它放在那里，如果 这个表确实表示一个数组，
我会被覆盖或重挫 谁该学生的测验是。
对不对？
如果这是一个数组，只有一件事可以 走在这些细胞或元件。
所以，我种有 挑选。
>> 刚才那种下面我 被骗了，做这个还是我
只是一种堆叠 他们在彼此之上。
但是，这并不是要在代码中飞翔。
那么，我能放 第二个学生的名字
是A，如果所有我是这样的 可用的表空间？
而且我用三个插槽，它 貌似有只是少数人。
你该怎么办？
听众：[听不清]
DAVID马兰：是啊。
也许我们只是保持简单。
对不对？
它不适合在这里我想把它。
所以我打算把它放在 技术上，其中A，B会去。
当然，现在，我开始 画自己陷入了困境。
如果我去一个学生 他的名字实际上是B，
现在乙将要被移动一点点 未来，为可能发生的事情，是的，
如果这是一个B中，现在它已去这里。
>> 所以这非常迅速 可能成为问题，
但它是一个技术，实际上是 被称为线性探测，
因此你只要考虑你 阵列是沿着线。
正中下怀，你探头或 检查每个可用的元素
寻找一个备有现货。
而且只要你找到 1，你在那里将其删除。
>> 现在，这个价格现在正在支付 这个解决方案是什么？
我们有一个固定大小的数组， 当我插入的名字
进去，至少在最初阶段，有什么 插入的运行时间
为把学生 在右边的桶测验？
什么大O？
>> 听众：N。
DAVID马兰：我听说的n大O。
事实并非如此。
但我们将梳理出 为什么在短短的一瞬间。
还有什么会是什么？
>> 听众：[听不清]
DAVID马兰：让我做视觉。
因此，假设这是字母S.
>> 听众：这是之一。
DAVID马兰：这是之一。
对不对？
这是一个数组，它 意味着我们有随机访问。
如果我们认为这 零，这为25，
我们认识到， 哦，这是我的输入S，
我当然可以转换 S，一个ASCII字符，
到一个相应的数字 零到25之间
然后立即 把它原来的位置。
>> 但当然，当我到达 第二个人谁的名字是A或B或C
最后，如​​果我用了 线性探测作为我的解决方案，
的运行时间 插入在最坏的情况下
实际上是要下放成什么样？
我也听到了这里 正确的早期。
听众：[听不清]
DAVID马兰：所以这是正确一次 有一个足够大的数据集。
这样，一方面，如果 阵列足够大
和你的数据是稀疏的话，你 得到这个美丽的固定时间。
但只要你开始 越来越多的元素，
而只是统计上你 更多的人信
A作为自己的名称或字母 B时，它可能潜在
下放成更线性的。
所以，不是很完美。
所以，我们可以做的更好？
>> 那么，什么是我们的 之前的解决方案时，我们
希望有更多的比活力 像一个数组允许的？
听众：[听不清]
DAVID马兰：没有介绍什么？
是啊。
这样一个链表。
好吧，让我们看看一个链接 清单可能对我们不是做的。
那么，让我建议大家 画图如下。
现在这是一个不同的 从例图
从不同的文本，实际上，这 实际上是用粒度31的阵列。
而笔者简单 决定散列字符串
不基于该人的姓名， 但基于其生日。
不论该月，他们得出 如果你在第一次一个月的正在诞生
或一个月的31日，笔者 基于该值会出现乱码，
从而被散布的名字出一个位 不仅仅是26点可能会允许。
也许这是一个小更均匀 比用字母去，
当然，因为有可能 更多的人在世界上的名字
开始的被肯定比 其他一些英文字母。
所以，也许这是一个小 更均匀，假定
均匀分布 的婴儿跨越了一个月。
>> 但是，当然，这仍然是不完美的。
对不对？
我们有冲突。
多人在这 数据结构仍然
具有相同的出生日期的至少 你不论一个月。
但什么笔者做了什么？
好吧，看来我们有一个数组 在左侧的垂直绘制，
但是这只是一个艺术家的再现。
不要紧，什么方向，你 画一个数组，它仍然是一个数组。
这是什么的显然是一个数组？
>> 听众：链表。
>> DAVID马兰：是啊。
它看起来像它的一个 阵列的链表。
如此反复，这点排序 利用这些数据结构现在的
作为成分更多 有趣的解决方案，
你完全可以采取 基本一样的阵列，
然后拿更多的东西 有趣像一个链表
甚至将它们组合成一个更 更有趣的数据结构。
事实上，这也将 被称为哈希表
由此，阵列是 真哈希表，
但是哈希表中有 链，可以这么说，
可增大或缩小基础上， 你想要的元素的数量插入。
>> 现在，因此，什么是 在运行的时候吗？
如果我要插入人 他的生日是10月31日
在那里他或她去吗？
行。
在最底层的地方说31。
这就是完美的。
那是一定的时间。
但是，如果我们发现了什么别人 他的生日，让我们来看看，
十月，十一月，12月31日？
哪里是他或她会去吗？
同样的事情。
两步虽然。
这是恒定的，虽然不是吗？
行。
目前，它是。
但在一般情况下， 越来越多的人加入我们，
概率，我们要 得到越来越多的碰撞。
>> 现在，这是一个小 更好，因为在技术上
现在我的连锁店可以在 在最坏的情况下多久？
如果我插入N多人进入这个多 复杂的数据结构，N多人，
在最坏的情况下，它会为n。
为什么呢？
>> 听众：因为如果每个人都 有相同的生日，
他们将成为一条线。
DAVID马兰：完美。
这可能是一个有点做作， 但真正在最坏的情况下，
如果每个人都拥有相同的生日， 给你的投入，
你将有一个 大量的长链。
所以，你可以把它称为一个 哈希表，但实际上它是
只是一个大规模的链表 一大堆浪费的空间。
但在一般情况下，如果我们假定 至少生日是uniform--
它可能不是。
我正在做这件事。
但是，如果我们假定，对于 就事论事
它们是，那么在理论上，如果 这是垂直的表示
数组的，那么希望你 将得到的是，你知道链，
大致相同的长度，其中每个 这些代表月中的某一天。
>> 现在，如果有31天的月份， 这意味着我的运行时间真的
为n超过31大O，这 感觉比线性好。
但是，什么是我们的一个 承诺一两个星期
以前，每当它来表达 一个算法的运行时间？
刚刚只看高次项。
对不对？
31绝对是有帮助的。
但是，这仍然是n个大O。
但主题之一 问题设置5
将是对 承认绝对的，
渐近，理论上 这种数据结构
没有比刚刚好 一台庞大的链表。
而事实上，在最坏的情况下，这 哈希表可能下放成。
>> 但在现实世界中，我们人类 那自己的Mac或PC或其他
而正在运行真实世界 软件在真实世界中的数据，
该算法你要选哪个？
而其中，需要结束步骤或 一种采用N以31级分
找一些数据块或 找了一些资料？
我的意思是，绝对是31品牌 在现实世界中的差。
这是快31倍。
而我们人类是肯定 要明白这一点。
>> 因此，实现二分法 之间居然有
说起理论上的东西 和渐近这无疑
具有价值，因为我们已经看到， 但在现实世界中，
如果你关心只是使 人类对幸福的通用输入，
你很可能要接受 事实证明，是的，这是线性的，
但它的速度更快31倍 比线性可能。
而且更重要的是，我们不只是要 做一些乱像一个生日，
我们可以花一点 更多的时间和聪明
想想我们可能会做， 定一个人的名字，也许
他们的出生日期相结合的 成分搞清楚的东西
这是真正的多 均匀，少锯齿，
这么说不是这幅画 目前表明它可能是。
在代码中，我们如何才能实现呢？
那么，让我建议大家 只是借用一些语法，我们已经
使用几次迄今。
我要去定义 一节点，该节点再次
是一个通用术语，只是一些 容器为一些数据结构。
我要建议 字符串会在那里。
但是，我们要开始服用 这些培训轮子掉了。
>> 没有更多的CS50库 真的，除非你想
将其用于您的最终 项目，这是好的，
但现在我们要拉回来了 窗帘，说这只是一个char明星。
所以这个词有将是 有问题的人的名字。
现在我有一个链接 这里下一个节点
使这些代表 每个节点
在链中，潜在地， 的一个链表。
>> 现在该怎么办，我宣布 哈希表本身？
我如何申报这整个结构？
好了，说真的，就像我用一个指针 以列表的只是第一元件
之前，同样我能说 我只需要一堆指针
实现这整个哈希表。
我将有一个数组 所谓表为哈希表。
这将是规模生产能力。
这就是很多元素可以适应它。
并且每个在此这些元素的 阵列将是一个节点的明星。
为什么呢？
那么，每个这张照片，就是我 执行哈希表作为
有效地在一开始仅仅是 这个数组，我们已经垂直绘制，
其每个的平方 代表一个指针。
那那些有斜杠 通过他们只是空。
和那些有 箭头要正确
在实际指向实际的节点， 人体工程学的链接列表的开始。
>> 所以在这里的话，我们怎么可能 实现一个哈希表，该表
实现独立的链接。
现在，我们可以做的更好？
好吧，我答应最后一次 我们可以实现一定的时间。
我种了你 固定的时间在这里，
但后来说不是真的 固定的时间，因为它仍
依赖于总上 元件的数目
你输入到 的数据结构。
但是，假如我们这样做。
让我回到屏幕在这里。
也让我在这里预测这件事，清楚 在屏幕上，并且假设我这样做。
假设我想插入的名字 Daven在为我的数据结构。
>> 所以我想插入一个字符串 Daven成的数据结构。
如果我不使用什么 哈希表，但我用
一些更树状 就像一个家族树，其中
你有一些根本的 顶部，然后节点和叶
那去向下和向外。
假设这时，我才 要插入Daven的
到什么是当前一个空列表。
我要做到以下几点：我 要在这个家庭创建节点
树状数据结构，它看起来 有点像这样的，其中每一个
矩形有，比方说， 现在26在里面的元素。
和每个小区的 在这阵是怎么回事
代表字母表的字母。
>> 具体来说，我要去治疗 这是A，那么B，然后是C，则D，
这一个在这里。
所以这将有效地 代表字母D.
但插入所有Daven年代 名字我需要做多一点。
所以我首先要散列，可以这么说。
我要去看看第一个字母 在Daven的这显然是一个D，
我要去分配 看起来一个节点
像this--一个大的矩形大 够以适应整个字母表。
>> 现在D被完成。
现在A. D-A-V-E-N是目标。
所以，现在我什么都做的就是这一点。
当我开始D的通知 没有指针那里。
这是垃圾值的那一刻， 或者我可以把它初始化为空。
不过，让我赶上去 这个想法建立一个树。
让我分配一个又一个的这些 节点中有26个元素。
>> 你知道吗？
如果这仅仅是在存储器中的节点 我使用malloc创建，用一个struct
因为我们很快就会看到， 我该怎么办this--
我会从画一个箭头 这代表的D-下来的东西
该新节点。
而现在，第一个下一个 信Daven的名字，
V-- D-A-V--我要继续前进 并得出另一个节点是这样，
由此，此处的V族元素，其 我们将绘制的instance--哎呦。
我们不会画在那里。
它会去这里。
>> 然后，我们要 认为这是V.
再往下在这里我们要索引 下来从V到我们会考虑E.
然后从这里，我们要 去这里有这些节点之一。
现在我们有一个问题来回答。
我需要以某种方式表明， 我们在字符串Daven的结束。
所以，我可以把它空。
>> 但是，如果我们有Daven的 全名也，其
是，正如我们已经说过，达文波特？
所以，如果Daven是什么 实际上是一个子串，
一个更长的字符串的前缀？
我们不能仅仅永久 什么也不说是怎么回事
去那里，因为我们可以 切勿将像达文波特一个字
入该数据结构
>> 所以，我们可以做的是 把这些元素
因为也许有两个 他们中的元素。
一个是一个指针，的确， 因为我一直在做。
所以每个这些框 不只是一个小区。
但是，如果顶部 埃德蒙顿底部一个人的
要为null，因为 有没有达文波特，只是还没有。
如果那顶一个 为一些特殊的价值？
而这将是一个小 很难得出它这种规模。
但是，假如它只是一个复选标记。
检查。
D-A-V-E-N是一个字符串 在此数据结构中。
>> 同时，如果我有更多的空间 在这里，我所能做的P-O-R-T，
我可以把检查的节点 有字母T在最后。
因此，这是一个大规模 复杂的外观的数据结构。
和我的笔迹 肯定没有帮助。
但是，如果我想插入的东西 否则，考虑一下我们会怎么做。
如果我们希望把大卫， 我们会遵循同样的逻辑，D-A-V，
但现在我想指出，在未来 元素不是从E，但是从我到D.
因此，有将是 在这棵树多个节点。
我们将不得不调用malloc更多。
但是，我不想做一个 这幅画的一塌糊涂。
所以让我们来看看1 一个已经预先制定
像这样与不点，点， 点，但只是略阵列。
但每个节点 在这棵树在这里
表示同一件事 - 数组的大小26雷。
>> 或者，如果我们想成为 现在真的很合适，有什么
如果某人的名字 一个撇号，让我们
假设每个节点实际上具有 像27指数在里面，不只是26。
所以这个现在将是一个数据 结构称为trie-- T-R-I-E。
一个线索，这是假想 历史上的一棵树一个聪明的名字
这对优化 当然，检索，其中，
拼写与I-E所以它的线索。
但是，这是对线索的历史。
>> 因此，一个线索是这样的树状数据 就像一个家庭树结构
最终表现那样。
这里是一个又一个的例子 一大堆别人的名字。
但现在的问题 手头有什么
我们获得了通过引入可以说是一个更 复杂的数据结构，和一，
坦率地说，使用了大量的内存。
>> 因为即使， 此刻，我只
使用D的指针和 A和V和ES和NS，
我在浪费大量的内存赫克。
但是，在这里我度过一个资源， 我倾向于不争回另一个。
所以，如果我花了更多的空间， 什么是可能的希望吗？
那我花少了什么？
听众：更少的时间。
DAVID马兰：时间。
现在为什么会这样呢？
那么，什么是插 时间，在目前大O方面，
像Daven一个名字 或者达文波特还是大卫？
好吧，Daven是五个步骤。
达文波特将九个步骤， 所以这将是一个几个步骤。
大卫将五个步骤为好。
因此，这些都是具体的 数字，但肯定有
的上限的 长别人的名字。
而事实上，在该问题 台五规范，
我们要提出 它的东西
这是40-一些多字符。
>> 实际上，没有人有 一个无限长的名字，
这就是说，一个长度 名称或字符串的长度，我们可能
有一定的状态 结构可以说是什么？
这是不变的。
对不对？
这可能是一个很大的不变样 40多岁的，但它是恒定的。
它有多少不依赖 其它名称是在该数据结构中。
换句话说，如果我 想现在插入
科尔顿或加布里埃尔或抢或Zamyla或 艾莉森或贝琳达或任何其他名称
从工作人员到该数据 结构，是在运行时间
中插入其他名称 将要在所有受影响的
被多少其他元素 在已经将数据结构？
它不是。
对不对？
由于我们有效地利用 这个多层哈希表。
和运行时间 这些操作
取决于不上的数 这是在数据结构中的元素
或者被最终将 是在数据结构中，
但在什么具体的长度是多少？
>> 该字符串是 插入，这确实让
这种渐进恒 一时间 - 大O。
坦率地说，就在 现实世界中，这
指插入Daven的名字取 像五个步骤，或者达文波特9
步骤或大卫五个步骤。
这是相当不错的小的运行时间。
而且，事实上，这是一个非常 好东西，尤其是当
它不依赖于总量 在那里的元素个数。
那么如何才能实现我们这个 这种结构的代码？
这是一个多一点 复杂，但它仍然是
只是一个应用 基本构建块。
我要重新定义 我们节点如下：
布尔称为word--这 可以被称为什么。
但布尔代表 我画了一个对号。
是的。
这是一个字符串的末尾 在此数据结构中。
>> 并且，当然，节点星 有指儿童。
而且，事实上，就像 一个家谱，你
会考虑节点 被挂
一些家长的底部 元素是儿童。
这样一来，孩子们将要 是27的数组，第27届1
摆明了撇号。
我们要进行排序 的特殊情况。
所以，你可以有一定 名称以撇号。
甚至连字符应 去那里，但你
见P组5，我们只关心 有关信件和单引号。
>> 然后你怎么代表 数据结构本身？
你怎么代表根 这个线索的，可以这么说？
嗯，就像一个链表，你 需要一个指针的第一个元素。
有线索，你只需要1 指向此线索的根。
从那里，你可以散列 你的路陷的越来越深
以在结构中每一个其他节点。
因此，简单地用这个就可以 我们代表的结构。
>> 现在Meanwhile--呵呵，问题。
>> 听众：什么是布尔字？
>> DAVID马兰：BOOL字 只是这款C化身
什么，我描述 在这里，在这个盒子
我开始分裂各 数组的元素分为两部分。
之一是一个指向下一个节点。
其它必须是 类似的复选框
要说的是，有一个 字Daven说到此为止，
因为我们不想要的， 此刻，戴夫。
>> 即使戴夫将是一个 合法的一句话，他不是在特里
还没有。
和D是不发一言。
和D-A是不是一个单词或一个名称。
因此，复选标记 表示只有当你
打这个节点是 字符前面的路
实际上，你已经插入一个字符串。
这就是所有的布尔 那里是做给我们。
>> 在尝试任何其他问题？
是啊。
>> 听众：什么是重叠？
如果你有一个戴夫和Daven？
DAVID马兰：完美。
如果你有一个戴夫和Daven？
所以，如果我们插入，说一个绰号， 对于David-- Dave-- D-A-V-E？
其实，这是超级简单。
因此，我们只是要带四个步骤。
D-A-V-E。和我有什么要 做一次，我打了四节点？
只是去检查。
我们已经好到哪里去。
完成的。
四个步骤。
固定时间渐近。
现在我们已经表明，无论戴夫 和Daven是在结构中的字符串。
所以不存在问题。
并注意存在 Daven的没能
需要更多的时间或更少 时间戴夫，反之亦然。
>> 那么还有什么可以，现在我们怎么办？
我们以前使用过这个隐喻 托盘代表什么。
但事实证明，一个 托盘堆实际上是
示范的另一个抽象数据 类型 - 一个更高层次的数据结构
这在最后的日子就是 像阵列或链接的列表
什么更现实。
但它是一个更有趣 概念的概念。
堆栈，这样的 托盘在这里马瑟
通常被称为 只是that--堆栈。
>> 并且在这种类型的数据结构 你有两个operations--
你有一个叫推 添加的东西到堆栈，
就像把另一盘 备份在堆栈的顶部。
然后弹出，这意味着你 把最上面的托盘掉。
但是，什么是关键关于堆栈是 它有这种奇怪的特点。
由于食堂工作人员 重新排列的托盘为下一顿饭，
这是怎么回事是 真正了解学生如何
这种数据结构进行交互？
听众：他们将弹出一关。
DAVID马兰：他们要去 弹出一关，希望上面。
否则，它只是一种愚蠢 一路走到底。
对不对？
该数据结构并没有真正允许 你至少要抢底盘
很容易。
因此，有这种奇怪的 属性堆栈
在最后一个项目是 将成为第1列。
和计算机科学家称之为 这LIFO--后进先出。
它实际上确实有 有趣的应用程序。
它并不一定那么明显一些 其他人，但它确实能是有用的，
它确实能实现 在几个不同的方式。
>> 所以一个，实际上，让 我不要潜入了。
让我们这样做吧。
让我们来看看一个几乎在 同样的想法，但它是一个更公平一点。
对不对？
如果你是这些球迷的一个男孩或 女生真的喜欢苹果产品
而你在上午03点00分就醒了 排队在一些商店
获得最新的iPhone，你 可能排队这样的。
>> 现在队列很刻意的名字命名。
这是一条线，因为有 一些公平吧。
对不对？
种它将如果你吸 到了那里在Apple Store第一
但你有效的最底部 托盘是因为苹果公司的员工，然后
流行的最后一个人谁 实际上得到的线。
因此，栈和队列，即使 在功能上，他们是那种same--的
它只是这个集合 资源，这是
要发展和shrink--还有的 这种公平性方面吧，
至少在现实世界中， 其中，操作你锻炼
是根本不同的。
一个stack--队列 rather--据说有
两个操作：N队列和D队列。
或者你可以给他们打电话 任何数目的东西。
但是，你只是想捕捉 一个是增加的概念
和一个最终被减去。
>> 现在的发动机罩的下面，两者的堆栈 和队列可以实现怎么样？
我们不会进入代码 这是因为在较高的水平
思想是那种比较明显。
我的意思是，人类该怎么办？
如果我是第一人，在苹果 存储，这是前门，
你知道，我要站在这里。
和旁边的人的 站在这里。
那么，什么数据结构 适合于一个队列？
>> 听众：队列。
DAVID马兰：嗯，一个队列。
当然可以。
还有什么？
>> 听众：链表。
>> DAVID马兰：一个链接 列出你可以实现。
和链表是好的，因为这样 而不是可任意长长
具有一些固定的数 人在店里。
但也许一个固定的数 地方是合法的。
因为如果他们只有像20 iPhone手机的第一天，也许
它们只需要尺寸的阵列 20代表该队列，这
只是现在说一旦我们开始讨论 关于这些较高级别的问题，
你可以实现它 在任何数量的方式。
还有的可能只是要 是一个折衷在空间和时间
或只是在自己的代码的复杂性。
>> 那么堆栈？
好了，一个栈，我们已经看到太多 可能仅仅是这些托盘。
而且你可以实现这个数组。
但在某些时候，如果你使用一个数组， 什么事情要发生在托盘
你想放下？
行。
你只打算 能走这么高。
我认为，在马瑟他们 实际上凹进的开放。
所以，事实上，它几乎 像奥美使用
固定大小的阵列， 因为你只能
在开放符合这么多托盘 墙壁向下跌破人们的膝盖。
因此，可能是 说是一个数组，
但我们可以肯定的实施 更一般地用一个链表。
>> 那么，关于另一个数据结构？
我拉起另一个视觉这里。
像这个怎么在这里？
为什么会到没有它是有用的 一些花哨的线索，这
我们看到了这些非常宽的节点， 其中每一个是在一个数组中？
但是，如果我们做更多的事情 简单地说，就像一个老同学的家谱，
每一个在这里的节点 只是存储号码。
而不是一个名称或后裔 只是存储了一些类似这样的。
>> 好了，我们行话使用 数据结构是既尝试
和树木，其中一个线索，再次，是 只有一个的节点阵列，
依然是你可能会 从小学使用
当你犯了一个家庭 tree--叶和根
树和儿童 父母和兄弟姐妹物。
我们可以实现一个树， 例如，作为简单的了。
树，如果它作为一个节点，一个 这些圆，其具有数，
它不会有 1指针，而是两个。
而且只要你加入 第二个指针，
实际上现在做排序 的二维数据
结构在存储器中。
很像一个二维 数组，你可以
有种类的二维 链表但那些
下面的模式 那里没有周期。
这是一个真正的有一棵树 了祖父母的方式在这里再
一些家长和孩子 孙子和曾孙。
等等。
>> 但是，什么是真正的整洁对此也 只是逗你一些代码，
从调用递归 一段时间回来，因此
你写一个函数，该函数调用自身。
这是一个美丽的机会 实施东西
像递归，因为考虑这一点。
>> 这是一个树。
我已经有点肛门如何 我把整数到街上。
正因如此，它有一个特殊的 名称 - 二叉查找树。
现在，我们已经听说二进制 搜索，但你能
从这个东西的名字倒着工作？
什么是我如何的格局 插入整数到这棵树？
它不是随意的。
这里也有一些图案。
是啊。
>> 听众：在左边较小的。
>> DAVID马兰：是啊。
较小的是在左侧。
更大的是在右侧。
这样，真正的语句是 家长大于它的左孩子，
但比其右孩子少。
而这仅仅是一个连 递归定义语言
因为你可以应用 相同的逻辑的每一个节点
而且它仅塔底 如果你出去，基本情况
会的，当你打一个 叶子，可以这么说，
凡请假没有孩子更进一步。
>> 现在，你怎么可能找到44号？
你会从根开始，说，嗯。
55不是44，我想去 正确的还是我想往左走？
显然，你想要去左边。
所以它就像手机 在二进制搜索本书实例
更普遍。
但我们实现它 现在多了几分动态
不是一个数组可以允许。
而事实上，如果你想看看 在代码中，第​​一眼肯定。
它看起来像一大堆线。
但它的美丽很简单。
如果你想实现一个功能 所谓的搜索，其目的在生活中
是要搜索的一个值 像N，整数，
和你在一pointer--正在通过 一个指向根的节点，
那棵树的相当，从 您可以访问其他的一切，
注意如何直截了当地 你可以实现的逻辑。
如果树是空， 显然它不存在。
让我们只返回false。
对不对？
如果你把它什么都没有， 有什么也没有。
>> 否则，如果n小于 树箭头N--现在箭头N，
记得我们推出超 短暂的一天，
那只是意味着去参考 指针看看所谓的n个场。
因此，这意味着去那里 看看所谓的n个场。
所以，如果N，你给出的值，小于 比在树木整数的值，
你想去哪儿去了？
向左转。
>> 所以，注意递归。
我returning--不正确的。
不假。
我回来什么的答案 是通过调用自己，路过
的n再次，这是多余的， 但什么是略有不同呢？
我怎么做的问题更小？
我传递的第二个 参数，该树的不根，
但左子在这种情况下。
所以我通过左边的孩子。
>> 同时，如果n是大于 该节点目前，我正在看，
我搜索的右侧。
否则，如果树不为空，而 如果元素不是向左
它并不是正确的， 什么是奇妙的情况？
实际上我们发现，节点 的问题，所以我们返回true。
>> 所以我们刚刚触及表面 现在一些数据结构。
在问题设置5，你会 再进一步探讨这些，
你会得到你的设计 选择如何去了解这一点。
我想缔结 仅仅30秒的预告片
下周及以后有什么在等待着。
>> 正如我们begin--谢天谢地你可能 慢慢think--我们的转型
从C和下部的世界 层次的实现细节，
一个世界里，我们可以采取的 理所当然地认为别人终于
实现了这些数据 结构对于我们来说，
我们将开始了解 现实世界是指实施
基于网络的程序和 网站更普遍
并且也很安全 我们只已经影响
开始划伤的表面上。
这是什么等待着我们 在未来的日子里。
>> [视频回放]
>> - 他想出了一个消息， 有协议的所有他自己的。
他来到了残酷的世界 防火墙，路由器漠不关心，
和危险远远比死还要痛苦。
他的速度快。
他是强大的。
他是TCP / IP，和他有你的地址。
“勇士的网。”
[完视频回放]
DAVID马兰：下周即将。
我们会看到你呢。
[视频回放]
- 和现在，“深度思考” 通过Daven法纳姆。
-David总是开始 与讲座，“好吧。”
心动不如行动，“这里的解决方案 本周的问题集“
或者“我们给大家一个A？”
[笑气]
[完视频回放]