[音乐播放]
扬声器1：好吧。
每个人都欢迎回款。
我希望大家都成功 从你的测验回收
从上周。
我知道这是一个有点疯狂的时候。
正如我之前说，如果你是 的标准偏差之内，
真的不担心，尤其是 一个不太舒适的部分。
这是什么地方，你应该的。
>> 如果你做得很好，那么真棒。
荣誉给你。
如果你觉得你需要 多一点点的帮助，请
随时到达 出任何的转录因子。
我们都在这里帮忙。
>> 这就是为什么我们教。
这就是为什么我在这里每周一为你 球员和在办公时间星期四休息。
因此，请随时让我知道 如果你担心什么
或者，如果有对任何竞猜 你真的想解决的问题。
>> 因此，对于今天的议程 所有关于数据结构。
其中一些只是要公正 为了让你熟悉这些。
你可能永远不会实现 他们在这个类中。
有些人你会的， 像你的拼写PSET。
>> 你有你的选择 哈希表和尝试的。
所以我们一定会去在那些。
这将是肯定更有种 高电平部分的今天，虽然
因为有很多人，如果 我们进入的实施细则
所有这些，我们不会 甚至可以通过链接列表
也许哈希表的一点点。
>> 所以多多包涵。
我们不打算做 尽可能多的编码这个时候。
如果您有任何关于它的问题 或者你想看到它实现的
还是自己试试看， 我绝对推荐
要study.cs50.net，这 具有所有的这些例子。
这将有我的学习认证 用音符，我们
倾向于使用以及一些编程 练习，特别是对事
如链表和二进制 树木堆栈和线索。
这么少的较高水平，这 也许是很好的你们。
>> 所以这样，我们就开始吧。
而且，yes--测验。
我想绝大多数人谁是 我的部分有你的测验，
但任何人进来，或某种原因，你 不这样做，他们就在这里，在前面。
>> 所以链表。
我知道这种云 您的测验前备份。
这是一周前 我们了解了这一点。
但是，在这种情况下，我们只 走多一点点深入。
>> 那么，为什么我们会选择一个 链表一个数组？
有什么区别呢？
是吗？
>> 听众：您还可以扩大一个链接 列出与数组的固定大小。
扬声器1：没错。
数组有固定的大小，而一 链表具有可变的大小。
因此，如果我们不知道如何 我们多么希望存储，
链表给我们带来了很大的 办法做到这一点，因为我们可以只
添加另一个节点上，并添加上 另一个节点，并添加另一个节点上。
但可能是一个权衡？
有谁还记得权衡 数组和链表之间？
Mmhmm​​？
>> 听众：你必须 经过一路
通过该链接的表 发现列表中的一个元素。
在一个阵列，可以 只要找到一个元素。
>> 扬声器1：没错。
因此，与arrays--
>> 听众：[听不清]。
>> 扬声器1：数组，我们有 什么叫做随机访问。
也就是说，如果我们要的是 有史以来第五点名单
或第五点是我们 数组，我们只要抓住它。
如果它是一个链表，我们有 遍历，对不对？
所以，在访问一个元素 一个阵列是恒定时间，
而用一个链表的那样 最有可能是线性的时间，因为也许
我们的元件是一路在末端。
我们有过的一切进行搜索。
因此，所有这些数据 我们要去结构
要在花多一点的时间， 哪些长处和底片。
什么时候我们可能要 使用一个比其他？
这就是种的 更大的东西拿走。
>> 因此，我们必须在这里 定义一个节点。
这就像在一个元素 我们的链表，对不对？
所以，我们都很熟悉 我们的typedef结构，
我们走过去，在回顾过去的时候。
它基本上只是创造 我们可以使用另一种数据类型。
>> 在这种情况下，它的一些节点 这将在一定整数。
然后什么是第二部分在这里？
任何人吗？
>> 听众：[听不清]。
>> 扬声器1：是啊。
这是一个指向下一个节点。
因此，这实际上应该是在这里。
这类型的指针 节点到下一件事情。
而这正是他们 包括我们的节点。
凉爽。
>> 好吧，所以用搜索，因为我们 只是说前手，如果你
要通过搜索， 你必须真正迭代
通过您的链接列表。
因此，如果我们要寻找的数量 9，我们将开始在我们的头上
并指向我们开始 我们的链表，对不对？
我们说好，这是否 节点包含数字9？
不是吗？
>> 好吧，去下一个。
遵循它。
它包含数字9？
号
按照下一个。
>> 因此，我们必须以实际循环 通过我们的链接列表。
我们不能只是去直接到9。
如果你们真的想 看到一些伪代码在那里。
在这里，我们有一些搜索功能 这需要in--需要做些什么呢？
你有什么感想？
那么容易的。
这是什么？
听众：[听不清]。
扬声器1：我们正在寻找的数量。
对不对？
什么会这样对应？
这是一个指针？
>> 听众：一个节点。
>> 扬声器1：节点列表 我们正在寻找的，对不对？
因此，我们有一些节点的指针位置。
这是一个点，那将 通过我们的名单实际上迭代。
我们设置它等于列表 因为这只是
设置它等于 开始我们的链表。
>> 虽然它不为NULL，而 我们还有东西在我们的列表中，
检查，看看是否有节点 我们正在寻找的数字。
返回true。
否则，更新它，对不对？
>> 如果为NULL，我们退出我们 while循环并返回false
因为这意味着我们还没有找到它。
每个人都得到如何工作的？
行。
>> 因此，与插入，你 有三种不同的方式。
您可以预先准备，可以追加 你可以插入到什。
在这种情况下，我们 打算做一个预先准备。
有谁知道这些 3案件可能会有所不同？
>> 所以在前面加上意味着你把 它在列表的前面。
因此，这将意味着，不管 你的节点，无论
价值是什么，你要 把它放在这里在前面，好不好？
这将成为第一 元素在列表中。
>> 如果您添加它，它是怎么回事 去你的列表的后面。
并插入到什意味着你 打算把实际进入的地方
它让你的链接列表进行排序。
同样，你如何使用 这些，当你使用
他们会根据你的情况而有所不同。
如果不需要 进行排序，在前面加上趋于
是大多数人 使用，因为你不知道
要经过整个列表 寻找到底添加它，对不对？
你可以把它贴对世权。
>> 因此，我们将通过一个 插入1现在。
这么一件事，我要去 强烈建议在此PSET
是画出来的东西，一如既往。
这是你更新是非常重要的 以正确的顺序你的指针
因为如果你更新它们 稍微乱序，
你要结束了 失去你的列表的一部分。
>> 因此，例如，在这种情况下，我们 告诉头只点1。
如果我们只是做了 不保存这个1，
我们不知道是什么 1应指向现在
因为我们已经失去了什么 该负责人指出。
所以，有一点要记住 当你做了预先准备
是拯救什么 头分排名第一，
然后重新分配它，然后更新 你的新节点应该指向。
在这种情况下，这是为了做到这一点的方法之一。
>> 因此，如果我们做了这种方式 在这里我们只是重新分配头，
我们失去了我们的基本 整个列表，对不对？
做到这一点的方法之一是有1个点 接下来，再有头点1。
或者，你可以种不喜欢的 临时存储，这是我所津津乐道。
>> 但是，重新分配你的 以正确的顺序指针
将是非常，非常 重要的是这个PSET。
否则，你将有一个哈希 表或一个尝试，这只是将要
的话只有部分是你 想要再you're-- mmhmm？
听众：什么是临时 存储的东西你在说什么？
扬声器1：临时存储。
所以基本上另一 这样你可以这样做
是存放东西的脑袋，像 存放临时变量。
其分配到1 然后更新1点
以什么头用来指向。
这种方式显然是 因为你更优雅
不需要一个临时值，但 只是提供了另一种方式来做到这一点。
而我们实际上做有 一些代码这一点。
所以对于链表，我们 实际上有一些代码。
所以在此处插入，这是预先考虑。
所以这个进入它的头。
>> 所以第一件事情，你需要 当然，创造你的新节点，
并检查是否为NULL。
总是好的。
然后你需要指定的值。
当你创建一个新的节点，你 不知道它的指向下一个，
所以你想要初始化为NULL。
如果它最终指向事 否则，它就会被重新分配，它的罚款。
如果这是第一件事情 在列表中，则需要
指向null，因为 这是该列表的末尾。
>> 所以后来插入的话，我们在这里看到我们 被分配了节点的下一个值
是什么头， 这就是我们不得不在这里。
这就是我们只是做了。
然后我们分配头点 我们的新节点，因为要记住，
新是一些指针到一个节点， 而这正是头是什么。
这就是为什么我们 有这个箭头访问。
很酷吧？
Mmhmm​​？
>> 听众：我们得 初始化新的下一位第一为NULL，
或者我们只是把它初始化为头？
>> 扬声器1：新下一个 需要为NULL启动
因为你不知道 那里将是。
此外，这是怎么样的 就像一个范例。
你将其设置为NULL只是为了 确保你所有的基地都覆盖
你这样做，任何重新分配前 你总是保证它会
被指向的特定值 与像一个垃圾值。
因为，是的，我们分配 新的自动接下来，
但它更多的只是像 好的做法进行初始化
以这种方式，并重新分配。
>> 好了，现在双链表。
我们怎么想的？
有什么不同 双向链表？
>> 所以在我们的链表，我们可以 只朝一个方向，对不对？
我们只有下一个。
我们只能往前走。
>> 用一个双向链表， 我们还可以向后移动。
因此，我们不仅 我们要存储号码，
我们有它指向下一个 当我们刚刚从。
所以这允许 一些更好的遍历。
>> 因此，双向链表节点， 非常相似的，对不对？
唯一不同的是，现在我们 有下一个和前一个。
这是唯一的区别。
>> 所以，如果我们要在前面或append--我们 没有任何代码此向上这里 -
但如果你要尝试 插入，最重要的事情
就是你需要 确保你分配
无论你以前和你 下一个指针正常。
因此，在这种情况下，你会 不仅初始化旁边，
在初始化以前。
如果我们在列表的头部，我们 不但使头部等于新，
但我们的新的前应 点了头，对吧？
>> 这是唯一的区别。
如果你想有更多的实践 这些用链表，用插入，
与删除，插入带 成什锦列表，
请查看study.cs50.net。
有一群伟大的演习。
我极力推荐他们。
我希望我们有时间去通过他们 但有很多数据结构
打通。
>> 好了，哈希表。
这可能是最 您PSET有用位
在这里，因为你将要 执行其中的一个或一试。
我真的很喜欢哈希表。
他们很酷。
>> 所以基本上什么 发生的情况是一个哈希表
当我们真正需要迅速 插入，删除和查找。
这些都是东西，我们 在哈希表中优先考虑。
他们可以得到相当大的， 但我们会尝试用看，
有些事情是要大得多。
>> 但基本上，所有的散列 表是散列函数
告诉你哪个桶把每 您的数据，每一个在你的元素。
一个简单的方法去思考一个哈希表 是它的事情只是水桶，
对不对？
所以，当你被排序的东西 就像他们的名字的第一个字母，
这有点像一个哈希表。
>> 所以，如果我是组你们是 到谁的名字开始组
用A看过来，或者谁的生日 在一月，二月，三月，
什么，那就是有效 创建哈希表。
它只是创造了水桶 你的元素进行排序成
这样您就可以找到他们更容易。
所以这样一来，当我需要 找一个你，
我没有搜索 通过您的每一个名字。
我可以想，哦，我知道， 丹妮的生日是in--
听众：--April。
扬声器1：四月。
所以，我期待在我的四月 斗，与任何运气，
她会在那里唯一的一个， 我的时间是在这个意义上不变，
而如果我要看看 通过一大堆的人，
这将花费更长的时间。
因此，哈希表是真的只是水桶。
简单的方法，他们的看法。
>> 因此，关于一个很重要的事情 哈希表是一个散列函数。
所以事情我刚才讲的，像 您的名字的第一个字母
或者你的生日月， 这些想法，
真关联到哈希函数。
这是确定的只是一个方式，也 斗你是元素进入，OK？
因此，对于这pset中，你可以看一下 几乎任何你想要的哈希函数。
>> 并不一定是你自己。
有一些很酷的的人了 那里，做各种疯狂的数学。
如果你想使你的 拼写检查超快，
我肯定会 看看其中的一个。
>> 但也有在 简单的，如计算
的话，总和一样 每个字母的数。
计算总和。
用于确定桶。
他们也有难办的 就像所有的A的位置，
所有的B的在这里。
这些中的任何一个。
>> 基本上，它只是告诉你哪个 数组索引你的元素应该进入。
刚刚决定bucket-- 这是所有的哈希函数是。
所以在这里，我们有一个例子是 字符串的只是第一信
我只是在谈论。
>> 所以，你有一些散，这仅仅是 您的字符串减去A的第一个字母，
这会给你一些 介于0和25号。
和你想要做的是什么 确保这代表
您的散列的大小table-- 多少个水桶也有。
许多这类 散列函数，它们是
将要返回的值可能 要远远高于桶的数量
那你确实有 在哈希表
所以你需要 肯定和那些国防部。
否则，它会说， 哦，应该是在5000桶
但你只有30 水桶中的哈希表。
当然，我们都知道这是 会导致一些疯狂的错误。
所以一定要确保由于MOD 您的哈希表的大小。
凉爽。
所以碰撞。
是每个人都好这么远吗？
Mmhmm​​？
>> 听众：为什么会 返回这样一个庞大的价值呢？
>> 扬声器1：根据不同的算法 您的哈希函数使用。
有些人会做 疯狂繁殖。
它的所有有关获取 一个均匀分布，
所以他们做一些真正 有时是疯狂的事情。
就这样。
还要别的吗？
行。
>> 所以碰撞。
基本上，正如我刚才所说， 在最好的情况下，
任何斗我看看是 将有一件事，
所以我没有看全，对不对？
我不是知道它的存在，或者它 不，这是我们真正想要的。
但是，如果我们有数万 数据点和小于号
桶，我们将有 碰撞中，最终的东西
即将要结束了 斗已经有一个元素。
>> 所以，问题是，什么样 我们在这种情况下怎么办？
我们该怎么办？
我们已经有了的东西呢？
难道我们只是把它扔出去？
>> 号
我们必须保持他们两个。
这样的方式，我们 通常做的是什么吗？
是什么数据结构 我们刚才讲？
听众：链表。
扬声器1：链表。
所以，现在的，而不是每个这些 水桶只是有一个元素，
它会包含一个链接列表 这被散列到它的元素。
好了，大家都种得出来的？
因为我们不能有一个数组 因为我们不知道有多少东西
将要在那里。
链表可以让我们 刚刚确切的数字，
被散列成水桶，对不对？
>> 所以线性探测是 基本上这idea--
这是应对碰撞的一种方式。
你可以做的是，如果在这 情况下，浆果被散列到1
我们已经有了 那里的东西，你只要
继续下去，直到 你找到一个空槽。
这是一种方式来处理它。
另一种方式来处理 它是我们刚才
called--链接 列表被称为链接。
>> 所以这个想法，如果工作 您的哈希表，你认为
比大得多 您的数据集，或者如果你
想尝试和减少链接 直到它的绝对必要。
因此，有一点是线性的 探测手段明显
您的散列函数 是不是很实用
因为你要使用到结束 您的散列函数，得到一个点，
你的线阵探头向下 一些地方可用。
但现在，当然，任何事情 别人说结束了那里，
你将不得不 搜索甚至进一步下跌。
>> 而且还有很多更 搜索的费用
进入输入一个元素 在现在的哈希表，对不对？
而现在，当你去尝试和发现 浆果再次，你要凑吧，
而且它会说， 哦，在斗1看，
而且它不会是 在斗1，所以你
将不得不穿越 通过对这些休息。
所以，它有时是有用的， 但在大多数情况下，
我们要指出， 链接是你想做的事。
>> 所以，我们谈到了这点。
我得到了我自己一点点前进。
但链基本上是 在哈希表中的每一桶
仅仅是一个链表。
>> 这样的另一种方式，或更多的技术 这样，想到一个哈希表
是，它只是一个数组 链表，哪
你写你的字典时， 而你试图加载它，
想到它是一个 链表的数组
将使它更容易 为您初始化。
>> 听众：所以哈希表 具有预定的大小，
像水桶的[听不清]？
>> 扬声器1：没错。
所以它有一组数 你determine--桶
这你们应该 随便玩。
它可以是很酷 看看会发生什么
当你改变你的桶数。
但是，是的，它有一个 桶的设置数量。
是什么让你满足的 因为你需要很多元素
这是单独的链接，你 已在每个桶链表。
这意味着你的哈希表 会完全大小
你需要它，对不对？
这就是链表的整点。
凉爽。
>> 所以每个人都需要帮助吗？
行。
啊。
刚刚发生了什么？
现在真的。
猜猜谁是杀害我。
>> OK，我们要进入 尝试，这是一个有点疯狂。
我喜欢的哈希表。
我觉得他们真的很酷。
尝试凉爽了。
>> 因此，没有人记得一试的是？
你应该已经走了过来 它简要地讲？
你还记得那种它是如何工作的？
听众：我只是点头 我们也去了吧。
扬声器1：我们过目一下。
OK，我们真的要去 在它现在是我们在说什么。
>> 听众：这是一个检索树。
>> 扬声器1：是啊。
这是一个检索树。
真棒。
所以，有一点这里要注意的是，我们 正在寻找单个字符
在这里，对不对？
>> 所以在我们的哈希函数，我们 所寻找的单词作为一个整体，
现在我们正在寻找更多的 在人物了吧？
因此，我们有麦克斯韦在这里和孟德尔。
所以基本上一个try--的方式来思考 这个是每个层次在这里
是字母数组。
因此，这是你的根结在这里，对不对？
这具有的所有字符 字母的每一个字的开始。
>> 和你想要做的是什么 说好，我们有一些M个字。
我们要寻找麦克斯韦，所以 我们去的M.和M点整
另外一个数组，其中每 总之，只要存在
是一个具有一个字 作为第二个字母，
只要有一个字 有B作为第二个字母，
它将有一个指针 去一些旁边的数组。
>> 有可能不是一个 词MP的东西，
所以在此P位置 数组，它只是为NULL。
它会说，OK，没有字 即有m个后跟一个P，好不好？
因此，如果我们仔细想想，每个 这些较小的事情之一
实际上是其中之一 到Z大阵列从A
那么，什么可能的事情之一 这是怎样的一个尝试的缺点呢？
>> 听众：大量的内存。
>> 扬声器1：这是一吨的记忆，不是吗？
每一个这些块在这里 代表26位，26个元素的数组。
因此，试图获得令人难以置信的太空沉重。
>> 但他们都非常快。
如此令人难以置信的速度快，但 真是浪费空间。
那种有图 哪一个你想要的。
这是真的很酷您PSET， 但他们占用了大量的内存，
所以你权衡。
是吗？
>> 听众：有没有可能 建立一个尝试，然后
一旦你把所有的 你need--在它的数据
我不知道这是否会是有意义的。
我摆脱所有 NULL字符，但随后
你就不能够索引them--
>> 扬声器1：您仍然需要他们。
>> 听众： - 每次以相同的方式。
扬声器1：是啊。
您需要NULL字符来让 你知道，如果有没有一个字出现。
奔你有什么，你想要什么？
行。
好了，所以我们要 去多一点点
进入技术细节的背后 一试，并通过一个实例运行。
>> 好了，这是同样的事情。
而在一个链表，我们的主要 那种of--什么是我想要的字？ -
像积木是一个节点。
在一个尝试，我们也有一个节点， 但它的定义不同。
>> 因此，我们有一些布尔值， 代表实际上无论是词
存在于这个位置，然后 我们有一些阵这里 - 或者更确切地说，
这是一个指向 阵列的27个字符。
这是因为，在这种情况下，这 27--我相信在座的各位都是这样，等待，
有字母表中的26个字母。
为什么我们有27？
>> 这样根据不同的 要实现这种方式，
这是从一个pset中那 允许撇号。
所以这就是为什么额外的之一。
您还可以有一些 情况下，空终止
被包含的所述一个 即它允许为字符，
这就是他们如何检查 看它是否是该字的结束。
如果您有兴趣，请查看 凯文的视频study.cs50，
以及维基百科 一些很好的资源在那里。
>> 但是，我们要通过正中下怀 您可能如何工作，通过一试
如果你正在考虑之一。
因此，我们有一个超级简单的在这里， 有句话“蝙蝠”和“缩放”在其中。
正如我们看到的在这里， 在这里这个小空间
代表了我们的布尔值， 说，是的，这是一个字。
然后这有我们 字符数组，对不对？
>> 所以，我们要通过 发现在这个尝试“蝙蝠”。
所以，从高层开始，对不对？
我们知道，B对应 第二索引，所述第二元件
在这个阵列中，因为a和b。
所以大约第二个。
>> 它说，OK，冷静，按照成 下一个阵列，因为如果我们记得，
这并不是说所有这些 实际上包含元件。
这些阵列中的每一个 包含一个指针，对不对？
这是做一个重要的区别。
>> 我知道这是要be--尝试的 真的很难得上是第一次，
所以，即使是这样的 第二次或第三次
而且它仍然是一种 看似很难的，
我保证，如果你去观看 短期再度明天
这可能会使得很多更有意义。
这需要大量的消化。
我有时仍然很 象，等等，什么是一试？
我该如何使用呢？
>> 所以我们B在这种情况下， 这是我们的第二个索引。
如果我们有，比方说，C或 d或任何其他字母，
我们需要映射回索引 我们的数组的对应。
因此，我们将采取类似rchar，我们只是 减去掀起了将其映射到0〜25。
大家好，我们怎么样 地图我们的角色？
行。
>> 所以我们去的第二个和我们 看，是的，它不是为NULL。
我们可以继续在下一个数组。
所以我们去到这一个阵列在这里。
>> 和我们说，好了，现在我们 需要看到，如果是在这里。
为空或做它 其实往前走？
所以实际上移动 转发此数组中。
我们说好，t是我们的最后一个字母。
所以我们去到T的索引。
然后我们继续前进 因为有另一个。
而这一次，基本上说，是的， 它说，有一句话这里 -
如果你遵循这一点， 路径，你已经到了
在一个字，这是我们所知道的是“蝙蝠”。
是吗？
>> 听众：是不是标准有 为索引0，然后有一个排序的1
或有在结束了吗？
>> 扬声器1：第
因此，如果我们回头看我们的 在这里声明，这是一个布尔值，
所以它在你的节点自身的元素。
所以它不是数组的一部分。
凉爽。
所以，当我们完成我们的话，我们很 在这个数组，我们想要做的
是做一个检查，这是一个单词。
在这种情况下，它会返回是。
>> 所以，关于这一点，我们知道“动物园” - 我们知道，作为人类的“动物园”是一个词，
对不对？
但尽量会在这里 说，不，它不是。
它会说，因为我们 没有指定它作为这里一个字。
尽管我们可以遍历 通过对这个阵列中，
这种尝试会说，不， 动物园是不是在你的字典
因为我们还没有 指定它是这样。
>> 因此从另一个角度做that-- 哦，对不起，这一项。
所以在这种情况下，“动物园”是不 一个字，但它是在我们的尝试。
但在这其中，说我们想让它 介绍词“洗澡”，会发生什么
是我们遵循through-- B，A，T。
我们在这个数组中， 我们去寻找小时。
>> 在这种情况下，当我们 看指针小时，
它指向NULL，好不好？
所以，除非它是明确的 指着另一个数组，
你以为所有的指针 在这个阵列指向空。
所以在这种情况中，h是指向 为null，所以我们不能做任何事情，
因此它也将返回 假的，“洗澡”是不是在这里。
所以，现在我们实际上 要经过
怎么会，我们实际上说 该“动物园”是我们的尝试。
我们如何将“动物园”到我们试试？
所以在我们开始以相同的方式 我们的链表，我们从根开始。
如有疑问，开始 这些东西的根源。
>> 我们会说，OK，Z。
ž存在于此，并且它的作用。
所以你移动到 你的下一个阵列，好不好？
然后就下单， 我们说好，不Ø存在吗？
它的作用。
这再次。
>> 等我们下单，我们已经说过了， OK，“动物园”已经存在这里。
所有我们需要做的是设置此相等 为true时，有一个词出现。
如果你遵循了一切 到该点之前，
这是一个字，所以只 设置它等于这样的。
是吗？
>> 听众：所以后来做了 意思是“巴”是一个字也？
>> 扬声器1：第
因此，在这种情况下，“巴”，我们会得到 在这里，我们想说的是一个字，
并且它仍然是否定的。
行？
Mmhmm​​？
>> 听众：所以一旦你是一个 一句话，你说是，那么它
将包含去米？
>> 扬声器1：所以这个必须做 with--你加载此研究。
你说的“动物园”一词。
当你去check-- 喜欢，说你想说的话，
在这个字典里“动物园”的存在？
你只会搜索“动物园” 然后检查，看它是否是一个字。
你永远不会动 通过对米，因为这不是
您要查找的内容。
>> 因此，如果我们真的想 添加“洗澡”这个尝试，
我们会做同样的事情 当我们用做“动物园”
除了我们看到，当我们 尝试，并得到为h，它不存在。
所以，你可以认为这是试图 以添加新节点插入到一个链表，
所以我们需要添加另一个 其中的一个阵列，像这样。
然后我们要做的是，我们刚刚成立的H 这个数组指向这个元素。
>> 然后什么我们要在这里做？
添加它等于true 因为它是一个字。
凉爽。
我知道。
尝试都不是最激动人心的。
相信我，我知道。
>> 这么一件事与尝试实现， 我说，他们是非常有效的。
因此，我们已经看到了他们 占用大量的空间。
种他们混淆。
那么，为什么我们曾经使用过这些？
我们使用这些，因为他们是 令人难以置信的高效。
>> 因此，如果你曾经期待 一个字，你是唯一的
由字的长度的限制。
所以，如果你正在寻找一个 字是一个长度为5的，
你永远只能将不得不 让最多5攀比，好不好？
所以它使基本上是一个常数。
就像插入和查询 基本上都是固定的时间。
>> 所以，如果你能永远得到 东西在一定的时间，
这是因为它得到不错的。
你不能得到更好的比 固定时间为这些事情。
以便为所述一个 尝试了巨大的加号。
>> 但它是一个很大的空间。
样的，所以你必须决定 什么对你更重要。
而在今天的电脑， 空间的一个尝试可能最多
也许不影响 你那么多，但也许
你在处理事情 有远远更多的东西，
并尝试恰恰是不合理的。
是吗？
>> 听众：等等，让你有26 在每一个人信吗？
>> 扬声器1：Mmhmm​​。
是啊，你有26。
你有一些是字标记，然后 你有26球在每个人。
他们正在point--
>> 听众：和每一个26， 难道他们各有26？
>> 扬声器1：是的。
这就是为什么，因为你可以 看，它扩展相当迅速。
行。
所以，我们要进入树， 我觉得喜欢的是更简单，大概会
是一个可爱的小死缓 从那里尝试。
所以希望你们中的大多数 以前看过一棵树。
不喜欢漂亮 外面的人，这是我
不知道是否有人 去户外最近。
我去采摘苹果本周末， 哦，我的天哪，这是美丽的。
我不知道叶子 可以看看那个漂亮。
>> 所以这只是一棵树，对不对？
这只是一些节点，并且它 指着一堆其他节点。
正如你在这里看到，这是 样一个反复出现的主题。
节点指向的节点是怎么样的 许多数据结构的本质。
这只是取决于我们如何 让他们指向对方
以及我们如何遍历 通过他们，我们如何
插入的东西，它决定 各自不同的特性。
>> 所以只是一些术语， 我以前使用过。
所以，根本是不管是在最高层。
这就是我们总是开始。
你可以把它作为负责人也。
但对于树木，我们往往 称其为根部。
>> 凡是在底部这里 - 在非常，非常bottom--
都认为叶。
因此，随之而来的 整棵树的事，对不对？
叶子是在你的树的边缘。
>> 然后我们也有几个 术语谈论有关节点
给对方。
因此，我们有父母， 孩子和兄弟姐妹。
所以在这种情况下，图3是 父的5，6和7。
因此，家长无论是 一步以上不管你是
参照，所以才 就像一个家庭树。
但愿，这是所有有点 位比尝试更直观。
>> 兄弟姐妹是任何有 同样的父母，对不对？
他们在这里的同一水平。
然后，因为我是 他说，孩子们刚
无论是低于一步 有问题的节点，好不好？
凉爽。
这样的二进制树。
任何人都可以猜测的一 二叉树的特点是什么？
>> 听众：最多两片叶子。
>> 扬声器1：没错。
所以，最大的两片叶子。
因此，在这个人之前，我们有这个 这有三个，但在一个二叉树，
你有最多两个 每个父母的孩子，对不对？
还有一个 有趣的特性。
有谁知道？
二叉树。
>> 所以二叉树将拥有一切 在the--这个人是不是sorted--
但在一个排序二叉树， 一切都在正确的
大于父 一切都在左边
小于母体。
并且已经交了白卷 问题之前，那么好就知道了。
因此，我们定义这个方式， 再次，我们有另一个节点。
这看起来非常相似呢？
双
>> 听众：链表
>> 扬声器1：双链表，对不对？
因此，如果我们替换此 有一个和下一个，
这将是一个双向链表。
但是，在这种情况下，我们实际上 有左，右，仅此而已。
否则，它是完全相同的。
我们还有元素 你要找的，
而你只需要两个指针 要去什么是下一个。
是啊，所以二叉搜索树。
如果我们发现，一切都在 这里是更大than--
或立即的一切 这里的权利
是大于一切 这里是小于。
>> 所以，如果我们通过搜索，它 看起来应该非常接近二分查找
在这里，对不对？
除外，而不是找 在一半的阵列，
我们只是在寻找在任左 侧或右侧的树。
所以就有点简单，我想。
>> 所以，如果你的根是空的， 显然这只是假的。
而如果它的存在，很明显这是真的。
如果是小于，我们寻找的左侧。
如果是大于， 我们搜查的权利。
它是完全一样的二进制搜索， 只是一个不同的数据结构
我们使用。
代替数组， 它只是一个二叉树。
>> OK，栈。
而且，看起来我们 可能有一点点时间。
如果我们这样做，我很高兴去 在任何这一次。
OK，所以栈。
有谁还记得stacks-- 一摞任何特点？
>> 好了，我们大多数人，我想， 在餐厅吃饭halls--
就像我们可能不喜欢。
但很明显，你可以把一叠 从字面上就如同一摞托盘
或堆叠的事情。
和什么是重要的 要知道的是，它的
something--特征 我们把它叫做by--是后进先出法。
有谁知道这代表着什么？
Mmhmm​​？
>> 听众：后进先出。
>> 扬声器1：没错，后进先出。
所以，如果我们知道，如果我们的东西堆放 起来，最简单的事情抢off--
也许我们唯一可以抢 关闭如果我们的协议栈是大enough--
是顶级元素。
所以，无论是放在 last--我们在这里看到，
不管是推 在大多数recently--是
将成为第一 我们流行过，东西好不好？
>> 所以，我们在这里是 另一个typedef结构。
这真的只是喜欢 在数据结构速成班，
所以有很多扔向你们。
我知道。
因此，另一种结构。
耶的结构。
>> 在这种情况下，它的一些指针 到具有一定容量的阵列。
因此，这代表了我们的协议栈 在这里，像我们实际的数组
这是我们持有的元素。
然后在这里我们有一些大小。
>> 而通常情况下，你要保持 曲目有多大的堆栈
因为它是怎么回事，让 你要做的就是，如果你知道的大小，
它可以让你说的， 好吧，我是在能力？
我可以添加些什么？
它也告诉你 在您的堆栈的顶部
那么你知道你 其实可以起飞。
而这实际上是要 有一点更清楚这里。
>> 因此，对于推，一件事，如果你 是有史以来实施推，
我只是说，你的 栈的大小有限，对不对？
我们的阵列有一些能力。
这是一个数组。
这是一个固定大小的，所以我们需要 确保我们不会把更多
到我们的数组要比我们 实际上有空间。
>> 所以，当你创建一个推 功能，你做的是说好第一句话，
做我的空间我的筹码？
因为如果我不这样做，对不起， 我不能存储你的元素。
如果我这样做，那么你想存储 它在堆栈的顶部，对不对？
>> 这就是为什么我们有 跟踪我们的规模。
如果我们不保持我们这样规模的轨道， 我们不知道放在哪里。
我们不知道有多少东西 在我们的数组了。
就像明明有方法 也许你可以做到这一点。
你可以初始化所有设置为NULL 然后检查最新NULL，
但一个更容易的事情仅仅是 说，OK，跟踪大小。
就像我知道我有四个要素 在我的数组，所以接下来的事情
我们换上，我们 将存储在索引4。
然后，当然，这意味着 你已经成功地推的东西
到你的筹码，你 要增加大小
让你知道你是如此 那你可以把更多的东西。
>> 所以，如果我们试图弹出 事关栈，
可能是什么的第一件事 我们要检查？
你想采取 事关你的筹码。
你肯定有 在堆栈中的东西吗？
号
所以，什么才是我们要检查？
>> 听众：[听不清]。
扬声器1：检查的大小？
尺寸。
因此，我们要检查，如果看 我们的规模是大于0，OK？
如果是，那么我们需要减小 我们的规模由0和返回。
为什么呢？
>> 在第一个我们 推，我们推
上的尺寸，然后更新的大小。
在这种情况下，我们正在递减大小 然后把它关闭，它拔毛
从我们的数组。
为什么会那样做？
所以，如果我有一件事对我的筹码， 这将是我的尺寸在这一点？
1。
>> 何为元素1储存在哪里？
什么指标？
听众：0。
扬声器1：0。
所以在这种情况下，我们 总是需要使sure--
而不是返回 大小减去1，因为我们
知道我们的元素是 将要被存储在1以下
无论我们的规模是，这 只需要照顾它。
这是一个稍微更优雅的方式。
我们只是减小了 大小，然后返回大小。
Mmhmm​​？
>> 观众：我想刚才在一般情况下， 为什么会这个数据结构
是有益的？
>> 扬声器1：这取决于你的环境。
因此对于一些理论， 如果你的工作with-- OK，
让我看看，如果有一个有利的1 那就是超过外面有利
的CS。
随着栈，任何时候你需要 跟踪事
是最近添加的是当 你将要使用的堆栈。
>> 我想不出一个好 举例说，现在。
但每当最近 事情是对你最重要，
这是一个堆栈时， 将是有用的。
我试图想，如果 有一个很好的这一点。
如果我觉得一个很好的例子，在未来 20分钟后，我一定会告诉你的。
>> 但总体而言，如果有什么事， 就像我说的最多的，其中，最近
最重要的是，这是 其中，一摞用武之地。
而队列是一种相反的。
和所有的小狗狗。
这不是很大的，对不对？
我觉得我应该 只是有一个小兔子的视频
右中的中间 节为你们
因为这是一个强烈的部分。
>> 这样一个队列。
基本上一个队列是像一条线。
你们我敢肯定，使用这种日常生活， 就像在我们的食堂。
因此，我们必须去 并得到我们的托盘，我
确保你有排队等候 刷卡或让你的食物。
>> 因此，区别就在这里 是，这是FIFO中。
所以，如果是后进先出后进，先 出，先进先出是先入先出。
因此，这是不管你把 第一次是你最重要的。
所以，如果你在等待 在line--可以吗
想象一下，如果你去了 去获得新的iPhone
并且它是一个堆栈，其中 最后一个人符合了它​​的第一，
人们会互相残杀。
>> 所以FIFO，我们都很熟悉 在这里，在现实世界中，
而这一切，是因为有实际 种重现这一整条生产线
和排队结构。
如此而用栈， 我们有push和pop。
同一个队列，我们​​有 入队和出队。
所以排队的基本含义 把它放到后面，
和出队采取的手段 断从前面。
因此，我们的数据结构是一 稍微有点复杂。
我们有第二个事情防不胜防。
>> 因此，没有了头，这 正是堆栈，对不对？
这是相同的结构的堆叠。
唯一不同的是，现在我们 有这个头，这你怎么看
是要跟踪的？
>> 听众：第一个。
>> 扬声器1：对， 我们把第一件事。
我们的队列的头。
谁是排在第一位。
好吧，如果我们做排队。
再次，与任何 这些数据结构
因为我们处理的是一个数组， 我们需要检查一下，如果我们有空间。
>> 这有点像我说 你们这些家伙，如果你打开​​一个文件，
你需要检查空。
与任何这些堆栈 和队列，你需要
看看是否有空间，因为我们 处理一个固定尺寸数组，
我们看到这里 - 0，1都达5。
那么，我们在这种情况下是检查 看看我们仍然有空间。
是我们的规模小于容量是多少？
>> 如果是这样，我们需要将其存储在 尾部，我们更新我们的规模。
那么，什么可能的尾巴在这种情况下？
它没有明确地写出来。
我们将如何保存呢？
什么尾巴呢？
>> 因此，让我们步行穿过这个例子。
因此，这是一个大小为6的数组，对不对？
而我们现在所拥有的，我们的规模是5。
而当我们把它放在，这是怎么回事 进入第五个指标，对不对？
因此，存储在尾部。
>> 另一种方式来写尾部也只是 是我们的数组大小的指标，对不对？
这是5号。
接下来的事情将要进入5。
很酷吧？
行。
它变得稍微复杂 当我们开始用头搞乱。
是吗？
>> 听众：这是否意味着我们 会宣布一个数组，
是五行长 那么，我们要添加到它？
>> 扬声器1：第
所以在这种情况下，这是一个堆栈。
这将宣布 作为规模6的数组。
在这种情况下，我们 只有一个剩余空间。
>> 好了，有一件事是在这 情况下，如果我们的头是0，
那么我们就可以在大小添加。
但它变得有点棘手 因为实际上，他们
不具备滑动 对于这一点，所以我要去
画之一，因为它不是 曾经想象中的那么简单，你
开始摆脱的东西。
因此，而用栈 你永远只能有
担心大小是什么 当你添加的东西上，
一个队列，你还需要 确保你的头被占，
由于对队列一件很酷的事情 是，如果你没有能力，
你其实可以把它环绕。
>> OK，所以一件事 - 哦， 这是可怕的粉笔。
有一点要考虑的是这种情况。
我们就做五。
好了，我们要 说的头就在这里。
这是0，1，2，3，4。
>> 头的存在，并 请有东西在其中。
我们要添加的东西，对吧？
于是事情，我们需要 知道的是，头总是
要移动这样的， 然后循环回到我的身边，好不好？
>> 所以这个队列有空间的，对不对？
它有空间，在一开始， 那种此相反的。
因此，我们需要做的是我们 需要计算的尾巴。
如果你知道你的 头没有移动，尾巴
只是你的数组 大小的指标。
>> 但在现实中，如果你使用一个队列， 你的脑袋可能是被更新。
所以，你需要做的是 实际计算的尾巴。
所以，我们做的是这个公式 在这里，我打算让你
你们想想，和 然后我们会谈论它。
因此，这是能力。
>> 所以这实际上 给你一个办法做到这一点。
因为在这种情况下，是什么？
我们的头是1，我们的规模是4。
如果我们这国防部5，我们得到0， 这是我们应该输入它。
>> 如此则在下一情况下， 如果要做到这一点，
我们说，好吧，让我们出列的东西。
我们出列了。
我们拿出这个元素，对不对？
>> 现在我们的头指指点点， 我们要在另一件事情补充。
这基本上是 回到我们这行的，对不对？
队列可以在阵列周围包裹。
这是主要区别之一。
堆栈，你不能做到这一点。
>> 随着队列，您可以 因为所有的事项
是，你知道什么 最近被添加。
因为一切都在以复加 此向左方向，在这种情况下，
然后环绕，你可以 继续投入新元素
在阵列的前 因为它不是真的
阵列的前面了。
你能想到的初 数组的地方你的头居然是。
>> 所以这个公式是怎么 你计算你的尾巴。
这是否有道理？
行。
OK，出列，然后 你们有10分钟
要问我任何澄清的问题 你想要的，因为我知道这很疯狂。
>> 好吧，所以在相同的方式 - 我不知道你们注意到了，
但CS是所有关于模式。
东西是相当多的 同样的，只需用很小的调整。
这里这么一回事。
我们需要检查一下，看看我们是否真正 有东西在我们的队列，对不对？
说好，是我们的规模大于0？
凉爽。
>> 如果我们这样做，那么我们把我们的头，这 就是我刚才在这里展示。
我们更新我们的头要多一个。
然后我们减了 尺寸，并返回该元素。
>> 有更具体 在study.cs50.net代码，
我强烈建议你 通过它，如果你有时间，
即使它只是一个伪代码。
如果你们想通过谈话 与我一对一，请让我
知道了。
我很乐意。
数据结构中，如果 你把CS 124，你会
知道数据结构变得非常 乐趣，这是刚刚开始。
>> 所以，我知道这很难。
没关系。
我们奋斗。
我还是做了。
所以不要太担心了。
>> 但是，这基本上是你 在数据结构速成班。
我知道这是一个很大。
还有什么是我们 想去一遍？
任何我们想通过谈话？
是吗？
>> 顾客：这个例子，所以 新尾为0了吗？
扬声器1：是的。
听众：OK。
所以后来经历， 你有1加4 or--
>> 扬声器1：所以你是说， 当我们想要去做到这一点了吗？
听众：是的。
所以，如果你搞清楚out--在哪里 你计算从该尾？
>> 扬声器1：所以尾巴 是in--我改变了这一点。
所以在这里本实施例中，这是 我们正在寻找，确定的数组？
因此，我们必须在1，2，3和4的东西。
因此，我们有我们的头是等于1 这一点，我们的大小等于4
在这一点上，对不对？
>> 大家都同意的话？
所以我们做头部加上大小，这 给我们5，然后我们用5国防部。
我们得到0，这告诉我们，0 哪里是我们的尾巴，在那里我们有空间。
>> 听众：什么是上限？
>> 扬声器1：容量。
抱歉。
所以这是你的数组的大小。
是吗？
>> 听众：[听不清]前 我们返回的元素？
>> 扬声器1：因此，我们将 前往或返回的那一刻？
因此，如果我们移动一个，减小尺寸是多少？
坚持，稍等。
我肯定忘了另外一个。
没关系。
没有另一个公式。
是的，你会想返回 头，然后将其移回。
>> 听众：OK，因为在这 点，头是0，
然后，你要回 指数0，然后使头1？
>> 扬声器1：没错。
我认为还有另一种 公式有点像这样。
我没有在这上面我的头 我不想给你错了。
但我认为这是完全有效的 比方说，OK，保存该element--什么
头部的元素is--递减的 大小，移动你的头了，而归
无论这个元素。
这是完全有效的。
行。
我觉得这不是 像most--你不
要走出这里 喜欢，是的，我知道尝试。
我得到了这一切。
没关系。
我保证。
但是数据结构的东西， 它需要大量的时间来用于获得。
最难的可能是1 的东西，我认为，在使用过程中。
>> 因此，它肯定需要 重复和期待at--我
真的不知道链表 直到我做了太多与他们，
在同样的方式，我没有 真正了解指针
直到我已经教了两个 多年来，做自己的pset它。
这需要大量的重申和时间。
最终，它会有种点击。
>> 但在此期间，如果你有实物 的高水平的理解什么
这些干什么，他们的优点 和cons--这就是
我们真的倾向于强调， 特别是在介绍过程。
喜欢，为什么我们使用 试试在一个数组？
喜欢，什么是阳性 并且其中的每个的底片？
>> 和理解的取舍 每个这些结构之间
是什么是更重要的现在。
可以有一个疯 两个问题那
要问你实现或推 实施POP或入队和出队。
但在大多数情况下，具有 更高层次的认识和更
一个直观的把握是 比实际更重要
能够实现它。
>> 这会是真的真棒，如果在座的各位 能够走出去，去实现一个尝试，
但我们知道它并不一定 最合理的事情，现在。
但是你可以在你的pset，如果你想 到，然后你会得到实践，
然后也许你会 真正了解它。
是吗？
>> 听众：好，那么哪些是 我们的意思，在pset中使用？
我是否需要使用其中的一个？
扬声器1：是的。
所以，你有你的选择。
我在这种情况下猜测，我们可以 说说PSET一点点
因为我跑过这些。
因此，在你的pset，你有你的 选择尝试或哈希表。
有些人会尝试 并使用布隆过滤器，
但这些在技术上是不正确的。
因为他们的概率性质， 他们给假阳性的时候。
他们冷静地审视之中，虽然。
强烈推荐看 在他们最少。
但是，你有你的选择 一个哈希表，并一试的。
而这将是哪里 你在你的字典中加载。
>> 你需要选择 您的散列函数
你需要选择多少 铲斗有，它会有所不同。
就像如果你有更多的桶， 也许它会跑得更快。
但是，也许你就是在浪费一个 很多空间的方式，虽然。
你必须弄明白。
Mmhmm​​？
>> 听众：你之前说 我们可以用其它散列函数
我们不必 创建一个哈希函数？
>> 扬声器1：是的，没错。
因此，从字面上你的哈希函数， 像谷歌“散列函数”
并寻找一些很酷的人。
你是不是有望建成 你自己的哈希函数。
人一生 论文对这些东西。
>> 所以不用担心构建自己的。
找到一个网上开始。
他们中的一些，你必须 操纵一点点
以确保返回类型匹配 及诸如此类的东西，所以在开始时，
我会建议使用一些 真的很简单，也许只是
哈希的第一个字母。
然后，一旦你有工作， 结合有冷却器的散列函数。
Mmhmm​​？
>> 听众：请问一个尝试是或 高效而只是更难，like--
>> 扬声器1：那么一试，我想， 直觉是难以实现
但是非常快的。
但是，占用了更多的空间。
同样，你可以在优化这两个的 不同的方式和有办法to--
听众：我们怎样分级的呢？
它matter--
>> 扬声器1：所以你正常的分级方式。
你要对设计进行分级。
无论你的方式，你要 确保它的优雅，因为它可以
并作为有效的，因为它可以。
但是，如果你选择一个试或哈希 表的，只要它工作，
我们很高兴。
如果你使用的东西，哈希 第一个字母，这很好，
如可能喜欢的设计，明智的。
我们也到达 点这semester--
我不知道，如果你 球员noticed--如果你
PSET等级下降一点点 因为设计和诸如此类的东西的，
这是完全正常的。
它让到一个地步，你 程序正变得越来越复杂。
还有更多的地方 你可以改善。
>> 所以这是完全正常的。
这并不是说你 您PSET做差。
这只是我们是很难对你现在。
所以每个人的感觉吧。
我只是分级所有pset中。
我知道每个人都感觉到了。
>> 所以不用担心。
如果您有任何问题， 之前的pset或方法可以改善，
我尝试了具体的意见 的地方，但有时它的后期
我累了。
是否有任何其他的东西 关于数据结构？
我敢肯定，你们真的不 要谈他们了，
但如果有，我很高兴 走过去了，还有什么
讲座从过去 上周，上一周。
>> 我知道，上周所有检讨， 我们可能已经跳过了一些检讨
从讲座。
还有没有其他问题我可以回答？
好了，没事了。
好了，你们早出去15分钟。
>> 我希望这至少是半很有帮助， 我会看到你下周的家伙，
或周四的办公时间。
是否有小吃请求 下周，它的东西吗？
因为我忘了今天的糖果。
我带过去的糖果 上周，但它是哥伦布日，
所以就像六个人谁 有四袋糖果的自己。
我可以带星形图案 再次，如果你喜欢。
星形图案？
OK，听起来不错。
有一个伟大的日子，伙计们。