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。