[音乐播放] 扬声器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，听起来不错。 有一个伟大的日子，伙计们。