[音乐播放] 道格·劳埃德:所以我们一直在缓慢接近 而接近该数据的圣杯 结构,一个我们可以插入 成,删除,并查找 在固定的时间。 对。 这是排序的目标。 我们希望能够做 事情非常,非常快。 难道我们发现这里的时候, 我们谈论的尝试? 好吧,让我们一起来看看。 因此,我们已经看到一些 不同的数据结构 该处理的映射 所谓键 - 值对, 一些映射数据块 其他一些数据片段 所以我们知道在哪里可以找到 在结构信息。 因此对于阵列,例如,该 关键是该元素索引或阵列 位置0或阵列1等。 和的值是数据 存在在该位置。 那么,什么是存储在阵列0? 什么是存储在阵列1与刚 0和1,这将是键。 利用哈希表是 排序相同的想法。 利用哈希表,我们有这个哈希 函数生成散列码。 所以关键是数据的哈希码。 和的值,特别是 我们谈到链接 在哈希表的视频, 是数据的链表 该散列到哈希码。 对。 那么另一种方法 这种方法有关系吗? 怎么样的方法,其中 键被保证是唯一的, 哈希表,在那里我们可以不像 结了两段数据 具有相同的哈希码。 然后,我们必须处理 通过两种探测以上 最好链接来解决这个问题。 所以,现在我们可以保证 我们的重点将是独一无二的。 如果我们的价值是什么 只是一些容易 作为真假,它告诉我们,无论是 不能说资料片 在结构上存在? 布尔可能是简单的一个位。 现实情况可能是一个 字节不是位的可能性较大。 但是,这是一个很大小于 存储可能是50个字符的字符串, 例如。 所以尝试,类似于哈希表, 其中结合阵列和链表, 尝试结合阵列, 结构,和指针 一起将数据存储在 一个有趣的方式,是 从相当不同 什么我们到目前为止看到的。 现在我们用数据作为路线图 导航这个数据结构。 如果我们可以按照 路线图,如果我们能 按照从数据 自始至终,我们将 知道是该数据 存在于线索。 如果我们不能按照地图 从意味着结束可言, 数据不能存在。 再次,键这里是 保证是唯一的。 所以一个哈希表不同的是,我们永远不会 必须处理的冲突在这里。 并没有两段数据 有完全相同的路线图 除非该数据是相同的。 如果我们插入约翰的话 我们寻找约翰。 这是两个相同的块 数据吧,我们期待通过。 但除此之外,任何 两个数据是 保证有独特的路线图 通过这个数据结构。 而且我们要看看 一会儿就好了一个视觉这一点。 我们将通过努力做到这一点 创建一个新的数据结构, 映射以下键值对。 在这种情况下,我们不打算使用 一些简单的布尔。 实际上,我们将存储字符串。 而该字符串是要 是一所大学的名字。 关键是要在今年 当大学成立。 所有年大学 将要四位数字。 因此,我们将使用这四个数字来 导航通过这个数据结构。 而且我们可以看到,同样,如何 我们这样做,在短短一秒钟。 在路径的末端, 我们将看到名称 对应的大学 到那个键,这四个数字。 后面一个线索的基本思想 就是我们有一个中央的路线。 所以,想想它像一棵树。 这是拼写相似 并在概念上树。 通常,当我们想到 树木在现实世界中, 他们有一个根目录是在 地面和他们向上生长 他们有分支机构 并且他们有叶。 与基本思路 一线索是完全一样的, 除了根锚定 竖立在天空。 和叶子是在底部。 因此,它是一种像服用一棵树 和刚刚翻转倒扣。 但仍有分支。 而这些将是我们的途径, 这些将是我们连接 从根到叶。 在这种情况下,这些 路径,这些分支 贴有告诉我们数字 去从那里我们走哪条路。 如果我们看到一个0,我们再往这个分支, 如果我们看到一个1,我们再往这个分支, 等等。 那么,这是什么意思? 嗯,这意味着, 在每一个结点 和中的每一个节点 中,每一个分支, 有10种可能的 的地方,我们可以走了。 因此,有10球 从每一个位置。 而这正是试图能得到 有点吓人的人 谁是没有很多 在计算机科学之前的经验。 但尝试是真的很漂亮真棒。 如果你有 有机会与他们一起工作 并且你愿意去挖掘,在 并与他们进行试验, 他们真的很有趣 数据结构一起工作。 如果我们要插入元素 到线索,我们需要做的 正在建设的正确道路 从根到叶。 以下是每一步都顺 的方式可能看起来像。 我们要定义一个新的数据 结构为一个新的节点称为线索。 和这些数据的内 结构有两片。 我们要保存 一所大学的名字。 而且我们要存储 指针数组 到相同类型的其他节点。 所以,再一次,这是排序 无处不在的概念 我们是,我们在10个可能的 的地方,我们可以走了。 如果我们看到一个0,我们走上这条分支。 如果我们看到一个1,这个分支, 等等等等等等。 如果说9,我们走上这条分支。 因此,在每一个结点, 我们可以去10个可能的地方。 因此,每个节点必须包含10个三分球 到其他节点,对其他10个节点。 我们要存储的数据是 大学只是名字。 因此,让我们建立一个线索。 让我们插入一对夫妇 的物品进入我们的线索。 因此,在最高层, 这是我们的根节点。 这可能将是什么 你会在全球范围内申报。 而你要在全球范围内保持 一个指向该节点始终。 你会说, 根等于和你 将自己的malloc字典树节点。 而且你永远也不会 再次触及根本。 你想每次 开始导航通过, 您设置另一个指针 等于根,如TRAV, 这是例子,我 在我的很多影片使用 在这里栈和队列 和链接列表等。 您可以设置另一个指针 所谓TRAV遍历。 并使用TRAV导航 通过的数据结构。 因此,让我们看看这个看起来。 所以,现在,是什么 没有一个节点是什么样子? 好了,就像我们的数据 结构声明指出, 我们有一个字符串,它 在这种情况下是空的。 这里没有什么。 和10指针数组。 而现在,我们只 在这个线索1个节点。 还有没有别的它。 因此,所有的10个国家 指针指向为null。 这就是红色表示。 让我们插入字符串哈佛。 让我们插入的大学 哈佛的这个线索,这 始建于1636年。 我们要使用的密钥, 1636年,告诉我们,我们是 将存储在哈佛的线索。 现在,我们如何才能做到这一点? 它可能是这个样子。 我们从根开始。 我们有这10个地方,我们可以走了。 根就像任何 该线索的其他节点。 有10个地方,我们可以从这里走。 我们在哪里可能要 去,如果关键的是1636? 这确实两个选项。 对。 我们可以建立从关键 从右到左,并开始与6。 或者我们可以建立从关键 从左到右,从1开始。 它可能更 直观的作为一个人 了解我们 刚去左到右。 所以,如果我想插入 哈佛的这个线索, 我可能要开始 通过从根开始, 看我10选项 在我面前,说 我想下井1路。 好。 现在,1路目前为空。 所以,如果我想继续沿着这条道路 插入这个元素为线索, 我对malloc一个新的节点,有1 点在那里,然后我好去。 所以我基本上是在 点我站在那里 在树或根 线索并有10个分支机构。 但是,每个分支都有 门在它的前面。 对。 因为没有什么别的有。 没有安全通道。 这意味着什么 下所有的分支。 如果我想开建 什么的,我想删除的大门。 我想删除的门 在1号的前面。 我希望走的。 我想建立 另一个地方,我去。 这就是我在这里所做的。 所以1不再指向空。 我说,这是安全的走下来这里。 我建了另一个节点。 当我到达这个节点,我 有另外的决定。 我要去哪里,从这里去? 好吧,我已经走了下来1。 所以,现在我可能要下井6。 对。 再有,我有10个位置,我可以选择。 现在让我们往下走6号。 所以我清除门 在号码6的前方。 而我走那里。 我建一个节点。 而且我已经达到了另一个结点。 再有,我有10个选择 为在那里我可以走了。 我搬到从1到6。 所以,现在我可能要到3。 3,没有什么地方我可以去。 所以我开道 和自己建​​一个新的空间。 然后再从3,我在哪里要去? 我想下去6。 而且,再一次,我不得不 清除做到这一点的方式。 所以,现在我用我的钥匙插入创建 节点,并开始建立这个线索。 我已经在根开始。 我已经走了下来1636。 现在我在底部 在该节点上存在。 你也许能 看到它在屏幕上。 它以黄色突出显示。 这就是我目前。 我的键完成。 我用尽我的钥匙每个位置上。 因此,我不能再往前走。 因此,在这点上,所有的余 真正需要做的是说好。 那种这就像找 下来在地上, 如果你设想 自己作为这种路径 具有不同的连接。 排序看不起排序和 喷在地面上画哈佛。 这就是此名称。 知道这是什么,在这个位置。 如果我们从根开始,我们下去 1,然后6,然后3,然后6, 我们在哪? 那么,如果我们往下看 我们看到哈佛,然后 我们知道,哈佛 成立于1636年的基础上的方式 我们正在实施这个数据结构。 所以这是希望简单。 我们要做两个插入。 并希望它会帮助 看到这样做的两倍以上。 现在,让我们插入另一所大学。 让我们耶鲁插入到这个线索。 耶鲁大学成立于1701年。 因此,我们将开始在 根,因为我们总是这样。 我们设定一个遍历指针。 我们将用它来移动通过。 我们要的第一件事情 做的是往下走的1路。 这是我们的关键的第一位。 但幸运的是,我们不这样做 做任何工作,这个时候。 1.路径已被清除。 我以前当我清除了 在1636插入哈佛大学。 因此,我可以安全地移动 下来1,只是去那里。 如果能下移1。 但现在,我想去7。 我扫清了道路6。 我知道,我可以放心地 继续向下进行6路径。 但我需要继续在7路径。 那么,我需要做什么? 嗯,就像以前一样,我只需要 清除门,走出去的方式, 并建立从7路一个新的节点。 像这样。 所以,现在我已经搬到1,然后7。 而现在发现,我有点 在这个新的支行。 对。 其他的一切,从16 对,我不关心。 我没有做任何事情16。 我做17的东西。 所以现在17,我要 排序这里开拓创新。 下一个数字我的关键是0。 我显然不能取得任何进展。 我刚刚建立了这个节点。 所以,我知道有没有 路径向前从这里开始。 所以,我必须作出一个自己。 所以,我的malloc一个新的节点 并具有0点出现。 再一次,我的malloc一个 新的节点,并有一个点出现。 再次,我已经用尽了我的钥匙,1701。 所以,我看下来,我喷漆耶鲁。 这是这个节点的名称。 所以,现在如果我以往任何时候都需要的,如果耶鲁看 在这个线索,我从根开始, 我下去1701,往下看。 如果我看到耶鲁喷雾 涂到地面,再 我知道耶鲁存在于这个线索。 让我们做一个。 让我们来达特茅斯插入到这个 特里,这是成立于1769年。 再从根开始。 我的钥匙我的第一个数字是1。 我可以肯定地向下移动,这条道路。 已经存在。 我的钥匙的下一个数字是7。 我可以肯定地向下移动,这条道路。 它的存在也是如此。 我的下一个是6。 从这里,从那里我目前 在这中间节点黄色那里, 6目前被锁定了。 如果我想要走这条路, 我必须建立它自己。 所以,我的malloc一个新的节点 并有6点在那里。 然后,再次,我 在这里开拓创新。 所以,我的malloc一个新的节点,以便从 这node--路径编号9-然后现在 如果我游1769年,我往下看。 没有什么目前 喷漆那里。 我可以写达特茅斯。 我也插 达特茅斯到线索。 所以这是插入 事情到线索。 现在,我们要寻找的东西。 我们如何寻找东西的线索? 嗯,这几乎是同样的想法。 现在我们只是使用的关键数字 看看我们是否能够从根本导航 到我们想去的线索。 如果我们在任何时候进入了死胡同,然后 我们知道,该元件不能存在 否则这条道路会 已经被清除。 如果我们让它一路 最后,我们需要做的 是往下看,看看是否是 我们正在寻找的元素。 如果是,成功。 如果不是的话,失败。 因此,让我们搜索 哈佛大学在这个线索。 我们从根开始。 并再次,我们要 创建一个遍历指针 做我们的动作我们。 从根我们知道 我们需要去第一个地方是1, 我们能做到这一点? 我们可以。 如果安全存在。 我们可以去那里。 现在,我们需要去下一个地方是6。 请问6路从这里存在吗? 是的,确实如此。 我们可以去6个路径。 而我们在这里结束。 我们可以去从这里的3路? 嗯,事实证明, 是的,存在了。 而且我们可以得到从这里的6路? 我们可以。 我们还没有完全回答 这个问题呢。 但还有一个更 步骤,这是现在 我们需要往下看, 看看这actually-- 如果我们要寻找的哈佛大学,是 我们发现后,我们用尽了钥匙吗? 在这个例子中,我们使用的是在这里, 这些年来始终是四位数字。 但是,你可能会使用的例子, 你是存储单词的词典。 因此,而不是具有10个三分球 我的位置,你可能有26。 一个用于每个字母。 还有一些话像蝙蝠, 这是批量的一个子集,例如。 所以,即使你到了 关键的结束,你看下来, 你可能不会看到什么 你正在寻找。 所以,你总是要遍历 整个路径,然后 如果你能够成功 遍历整个路径, 往下看,做一个最后的确认。 那是我在找什么? 好吧,我开始后往下看 在顶部和去1636。 我往下看。 我看到哈佛。 所以,是的,我成功了。 如果什么什么我在寻找 是不是在线索,虽然。 如果我在寻找普林斯顿, 该公司成立于1746年。 所以,1746成为我的钥匙 浏览该线索。 好吧,我从根开始。 我希望首位 到下山的1路。 我能做到吗? 我可以。 我可以下去从那里的7路? 是的,我可以。 存在了。 但我可以去​​从这里的4路? 这就像问一个问题,就可以 我继续向下的小广场 我在黄已经强调? 有什么也没有。 对。 有没有办法前进下来的4路。 如果普林斯顿在这个线索,即4 已被清除我们了。 因此在这一点上 我们已经到了一个死胡同。 我们不能再往前走。 因此,我们可以说,明确,没有。 普林斯顿并不在此线索存在。 那么,这意味着什么? 对。 有很多怎么回事。 有指针所有的地方。 而且,正如你所看到的 刚刚从图中, 有很多节点的 都是那种飞来飞去。 但是请注意,每次我们想时间 检查东西是否是在特里, 我们只有使4举动。 我们希望每一次 在线索中插入一些东西, 我们必须做出4的动作,有可能 mallocing沿途的一些东西。 但正如我们看到的,当我们插入 达特茅斯到线索, 有时一些路径的 可能已经被清除了我们。 所以作为我们的线索变得更大, 更大,我们有充分的时间少做工作 插入新事物 因为我们已把 内置了很多中间的 沿途分支。 如果我们永远只能来看看 4东西,4仅仅是一个常数。 那种我们确实正在接近 恒定的时间插入 和恒定的时间查找。 权衡,当然,在于 这个线索,因为你可能会说, 是巨大的。 这些节点中的每一个 占用了大量的空间。 但是,这是权衡。 如果我们要真正快速 插入,真的很快删除, 真正快速查找,我们要 有大量的数据到处乱飞。 我们必须预留了很大的空间 和存储器,用于该数据结构 存在。 所以这就是权衡。 但看起来我们 可能已经找到了它。 我们可能会发现, 数据结构的圣杯 与快速插入, 缺失和查找。 也许这将是一个 合适的数据结构 用于任何信息 我们试图店。 我是道格·劳埃德,这是CS50。