DOUG LLOYD：所以在CS50，我们已经介绍 大量不同的数据结构， 对？ 我们已经看到阵列和链接 列表和哈希表， 和尝试，堆栈和队列。 我们还学了一点 关于树和堆， 但实际上这些都只是结束 了是变化的一个主题。 真的有这些 样的四个基本思路 这一切可以归结为。 数组，链表， 哈希表，和尝试。 就像我说的，有 一些变化在他们身上， 但是这是非常 多去总结 一切，我们要谈 有关本类C的条件 但如何做这些所有的措施了，对不对？ 我们已经讨论过的利弊 每对他们单独的视频中， 但有很多数字 越来越抛来抛去。 有很多的一般 想法得到抛来抛去。 让我们尝试和巩固 它变成一个地方。 让我们权衡利弊反对 的利弊，并考虑 该数据结构 可能是正确的数据 结构特定的情形， 什么样的数据要存储。 你不一定总是需要 使用超快速插入，删除， 和查找一个线索的，如果你真的 不在乎插入和删除 太多。 如果你只需要快速随机 访问，也许一个数组更好。 因此，让我们提炼出。 让我们来谈谈四个的 主要类型的数据结构的 我们已经谈到，和 刚看的时候，他们可能是很好的， 当他们也许不会这么好。 所以，让我们开始阵列。 所以插入，这是一种不好的。 

在插入数组的结束是确定的， 如果我们建立一个数组，因为我们去。 但是，如果我们需要插入 元素融入到中间， 回想起插入 排序，有很多 中移动在那里，以适应一个元素。 所以，如果我们要插入 任何地方，但一个数组的末尾， 这可能不是那么大。 

同样，删除，除非我们 删除从阵列的端部， 恐怕也没有那么大，如果 我们不想留出空白的差距， 通常我们不知道。 我们要删除的元素， 那么几分使其再次贴身。 因此删除从要素 一个数组，也没有那么大。 

查找，虽然是很大的。 我们有随机访问， 恒定的时间查找。 我们只是说有七个，我们走 阵列搬迁七人。 我们说20，与进入 阵列搬迁20。 我们没有迭代的对面。 这是相当不错的。 

阵列也比较容易进行排序。 我们谈了排序每次 算法，如选择排序​​， 插入排序，冒泡排序，合并 排序，我们总是用数组来做到这一点， 因为数组是很容易 排序，相对于所述的数据结构 我们已经看到了这么远。 

他们也比较小。 这里没有很多额外的空间。 你只留出完全一样多的 因为你需要把你的数据， 而这几乎是它。 因此，他们是非常小 而高效的方式。 但另一个缺点，不过， 是，它们被固定在尺寸。 我们必须明确的声明如何 大，我们希望我们的阵是， 我们只有一次机会吧。 我们不能增大和缩小它。 

如果我们需要扩大或缩小它，我们 需要声明一个全新的阵列， 复制所有的元素 第一阵列到第二阵列。 如果我们失算了 的时候，我们需要再次做到这一点。 没有那么大。 所以数组不给我们的灵活性 有元素的变量的号码。 

用一个链表， 插入是很容易的。 我们只是钉到前。 删除也非常的方便。 我们必须找到的元素。 这涉及到一些搜索。 

但是，一旦你找到了元 你要找的，所有你需要做的 是改变一个指针， 可能是两个，如果你有 链接列表中 - 一个双 链表，rather-- 然后你可以自由的节点。 你没有转移 周围的一切。 你只需要改变两个指针， 所以这是相当快。 

查找不好，虽然，对不对？ 为了让我们能够找到一个 在一个链表中的元素， 无论是单独或双重链接， 我们必须线性搜索。 我们必须开始在开始和 移动端，或开始在年底招 到开始处。 我们没有随机访问了。 因此，如果我们做一个 大量的搜索，也许 链表是不 对我们这么好。 

他们也很 难以理清，对不对？ 只有这样，你可以 真正排序链表 是排序为你构建它。 但是，如果你解决它，你 构造它，你不再 进行快速插入了。 你不只是套结 东西到前。 你必须找到 合适的地方把它， 然后你插 变得几乎一样糟糕 作为插入到一个数组。 所以链表不 因此非常适合对数据进行排序。 

他们还非常小，大小明智的。 双链表略 比单链表较大， 这是稍大 比阵列，但它不是 大量的空间浪费。 因此，如果空间是非常宝贵的，但 不是一个真正的激烈的溢价， 这可能是正确的道路要走。 

哈希表。 插入到哈希表 是相当简单的。 它是一个两步过程。 首先，我们需要通过运行自己的数据 散列函数以获得散列码， 然后我们插入元素插入 哈希表在这个哈希码位置。 

缺失，类似于链表， 很容易，一旦你找到的元素。 你必须先找到它， 但是当你删除它， 你只需要更换 一对夫妇的指针， 如果你使用的是单独的链接。 如果你使用的探测， 或者如果你不 使用链接在所有 在哈希表， 缺失其实是很容易的。 所有你需要做的是哈希 数据，然后去那个位置。 假设你不 有任何冲突， 你就可以很快删除。 

现在，查找是那里的东西 变得有点复杂。 它是在平均水平 比链表。 如果您使用的是链接， 你还有一个链表， 这意味着你仍然有 搜索有损链表。 但是，因为你把你的链接 列表，将其分割在100或1000 或N在哈希表的元素，你 链表都是一个第n的大小。 他们都小得多。 您有n个链接列表，而不是 大小n的一个链表。 

所以这个真实世界的不变 因素，一般我们 不要谈论时间的复杂性， 没有真正发挥作用在这里。 所以查找仍然是线性的 如果你使用的链接进行搜索， 但该列表的长度 您正在搜索通过 很相比之下很短。 再次，如果排序是你的 目标这里，哈希表的 可能不是正确的道路要走。 只需使用一个数组，如果排序 对你真的很重要。 

他们可以运行大小的色域。 这是很难说是否 哈希表是大或小， 因为它实际上取决于 你有多大的哈希表。 如果你只打算将存储 在哈希表五行， 和你有一个哈希表 在这10,000个元素， 你可能会浪费了很多空间。 作为对比，你也可以 具有非常紧凑的哈希表， 但较小的哈希表得到， 每个那些链表的长 得到。 所以真的没有办法定义 完全是一个哈希表的大小， 但它可能是安全的 说这是一般 将是大于链接的 列表存储相同的数据， 但是比线索更小。 

并试图列第四 这些结构的 我们一直在谈论。 插入到一个线索是复杂的。 有很多动态 存储器分配， 尤其是在开始时， 因为你开始建立。 但它的恒定时间。 这只是人为因素 在这里，可以很棘手。 说完就遇到空指针，的malloc 空间，去那里，可能的malloc空间 从那里了。 的威胁因子排序 在动态内存分配指针 是的障碍清除。 但是，一旦你清除它，插入 其实说到很简单， 而且可以肯定的是恒定的时间。 

删除很容易。 所有你需要做的就是导航下来 夫妇指针和自由节点， 所以这是相当不错的。 查找也非常快。 它只是基于 长度的数据。 所以，如果您的所有数据是 五个字符的字符串， 例如，你存储5 在线索字符串， 只需要五个步骤 找到你要找的东西。 五是只是一个常数因子，因此 再次，插入，缺失，和查找 这里都是固定的时间，有效。 

另一件事是，你的线索是 其实那种已经排序，对吧？ 凭借我们如何是 插入元素， 由信去信 键，或数字通过钥匙位， 通常情况下，你的线索最终被 种排序为您打造它。 它并没有真正使 有意义的思考整理 以同样的方式，我们考虑 它使用数组或链表， 或哈希表。 但在某种意义上，你 当您去线索进行排序。 

当然，不利的一面，是 一个线索迅速变得巨大。 从每一个结点，你可能 have--如果你的密钥由数字， 你有其他10个 地方可以去，哪些 意味着每个节点 包含的信息 有关数据要存储 在该节点处，加10的指针。 其中，在CS50的IDE，为80个字节。 所以这是至少80个字节 您创建的每个节点， 而这还没有算上数据。 如果你的节点 字母代替数字， 现在你有26球 从每一个位置。 而26倍8大概是200 字节，或者类似的东西。 你有资本 和lowercase--可以 看到我要与这一点，对不对？ 您的节点​​可以得到真正 大，所以线索 本身，总体而言，可以 得到真正的大了。 因此，如果空间是在一个较高的 您的系统上的溢价， 一个线索可能不是正确的方式 走，即使它的其他好处 开始发挥作用。 我是道格·劳埃德。 这是CS50。