>> 扬声器1：对，所以我们又回来了。
欢迎CS50。
是星期七月底。
所以记得，最后一次，我们开始 稍微复杂的看
的数据结构。
由于到现在为止，我们真的 在我们的处置是这样的，一个数组。
>> 但在此之前我们不会丢弃数组 所有有趣的，这的确
实际上，是一些什么 加上这个简单的数据
结构，从而有多远？
什么是它擅长的？
到目前为止，我们已经看到？
你得到了什么？
什么也没有。
>> 学生：[听不清]。
>> 扬声器1：那是什么？
>> 学生：[听不清]。
>> 扬声器1：固定尺寸。
OK，那么，为什么是固定大小的好，虽然？
>> 学生：[听不清]。
>> 扬声器1：确定的，所以它的效率 这个意义上，你可以分配一个
固定大小的空间，希望 恰恰是尽可能多
空间，只要你想。
所以这可能是一个绝对加分。
>> 一个数组的另一侧什么？
是吗？
>> 学生：[听不清]。
>> 扬声器1：所有的 - 对不起？
>> 学生：[听不清]。
>> 扬声器1：在内存中的所有箱子 或给对方。
这是有帮助的 - 为什么？
这是相当正确的。
但如何才能利用这一真理吗？
>> 学生：[听不清]。
>> 扬声器1：没错，我们可以跟踪 一切都只是知道
一个地址，即地址 该内存块的第一个字节。
或字符串的情况下， 地址的第一个
在该字符串中的字符。
并从那里，我们可以找到 结束的字符串。
我们可以找到的第二个元素， 第三个元素，依此类推。
>> 等花俏的手法描述， 特点是阵列给我们
随机访问。
只需使用方括号 符号和数字，你可以跳
一个特定的数组中的元素 在固定时间内，大O
之一，可以这么说。
>> 但也有一些缺点。
数组不是很容易做吗？
什么不擅长什么？
>> 学生：[听不清]。
>> 扬声器1：那是什么？
>> 学生：[听不清]。
>> 扬声器1：在规模扩大。
所以的缺点数组是 正好相反的是什么
一面是。
所以，一个缺点是 ，这是一个固定大小的。
所以你不能真正成长。
您可以重新分配更大的大块 内存中，然后将旧的元素
到新的数组。
然后释放旧的阵列， 例如，通过用malloc或类似的
函数调用realloc的， 重新分配内存。
>> REALLOC，顺便说一句，试图给你 内存阵列旁边
你已经有了。
但它也可能移动的东西 周围完全。
但总之，这是昂贵的，对不对？
因为如果你有一大块的内存 这个长度，但是你真的想要一个
这种规模，你要保留 你有原创要素，
大致的线性时间复制过程 需要发生
新的旧的阵列。
和现实要求的经营 系统一而再，再而
再大的内存块，就可以开始 花费你一些时间。
因此，它既是祝福和诅咒 伪装，但事实上，这些阵列
固定大小。
但是，如果我们引入，而不是东西 这样，我们称为联
列表中，我们得到了一些积极和 几个缺点在这里。
>> 所以一个链表是一个简单的数据 结构由C结构
情况下，当一个struct，召回，只是 用容器的一个或多个特定
类型的变量。
在这种情况下，什么数据类型 似乎是里面的结构，
我们最后一次称为一个节点？
这些矩形中的每一个是一个节点。
并且每个小矩形 里面它是一种数据类型。
什么样的类型，我们说 他们在周一？
是吗？
>> 学生：[听不清]。
>> 扬声器1：变量和指针，或 更具体地说，一个int，对n，
和指针底部。
两个那些碰巧是32位，在 至少在电脑上像这样CS50
电器，所以他们 得出同样的大小。
>> 那么，什么是使用指针 但显然？
为什么现在这个箭头数组时 这么漂亮，干净和简单的？
指针是什么做的 我们在这些节点中的每个节点？
>> 学生：[听不清]。
>> 扬声器1：没错。
它告诉你在哪里 下一个是。
所以我使用的比喻 使用一个线程来排序
线程这些节点连接在一起。
这正是我们正在做的 指针，因为每个这些
内存块可能会或可能不会 连续回背靠背
内部RAM，因为你每次 调用malloc说，给我足够的
字节一个新的节点，它可能 在这里，或者它可能是在这里。
这可能是在这里。
你只是不知道。
>> 但是，使用指针的地址 这些节点，你可以拼接
一起在视觉上看起来的方式 即使这些东西都像一个列表
传遍你的一个或 你的两个或4 GB的RAM
自己的电脑里面。
>> 所以下行，那么， 链表是什么？
什么是我们的价格 显然支付？
>> 学生：[听不清]。
>> 扬声器1：更多的空间，对不对？
在这种情况下，我们已经增加了一倍 空间，因为我们已经走了
从32位的每个节点，每个 INT，所以现在64位的，因为我们有
保持周围的指针。
你得到更多的效率，如果你的结构 是大于这个简单的事情。
如果你确实有一个学生里面 这是一对夫妇的字符串
名称和房子，也许是一个ID号， 也许其他一些领域完全。
>> 所以，如果你有一个足够大的结构， 那么也许成本的指针
没有什么大不了的。
这是一个位在一个角落的情况下 我们存储这样一个简单的原始
内的链接的列表。
但问题是相同的。
你肯定花更多 内存，但你得到
的灵活性。
因为现在如果我想添加一个元素 在此列表的开头，
我必须分配一个新的节点。
我有只更新那些 不知何故只是移动箭头
周围一些指针。
>> 如果我要插入到的东西 中间的列表，我不必
抛开众人推像我们一样 周过去与我们的志愿者
表示一个数组。
我可以只分配一个新的节点， 然后就点中的箭头
不同的方向，因为它不 必须保持以实际的
内存一个真正像我画的线 这里的屏幕上。
>> 最后，如​​果你想插入 在列表末尾的东西，这是
更容易。
这是任意符号， 但34的指针，以此来猜测。
其指针的价值是什么 可能拉有点像一个老
有学校天线？
>> 学生：[听不清]。
>> 扬声器1：这可能是空的。
事实上，这是一个作者的 表示空。
它是空的，因为你绝对 需要知道在哪里结束的联
名单，免得你保持以下 后，并按照这些箭头
一些垃圾值。
因此，空表示没有任何 更多的节点号为34的右侧，
在这种情况下。
>> 因此，我们提出，我们可以实现 这个节点的代码。
我们已经看到这种 之前的语法。
用typedef定义一个新类型 我们，为我们提供了这样的代名词
对于char *字符串。
在这种情况下，它给我们 速记符号，使结构节点
而是可以被写成 节点，它是干净了很多。
这是少了很多冗长。
>> 节点内显然是一个int 称为n和结构节点*
这意味着正是我们想要的 箭头的意思是，到另一个指针
完全相同的数据类型的节点。
我建议，我们可以实现一个 搜索这样的功能，这在
乍一看似乎 有点复杂。
但是，让我们来看看它在上下文中。
>> 让我去到这里的家电。
让我打开一个名为 列表零点H。
只包含的定义，我们 只是刚才也看到了这些数据
类型称为一个节点。
因此，我们已经把到一个点h文件。
>> 而顺便说一句，尽管这 程序，你将要看到的是
不是所有的，复杂的，它的的确确 当编写一个程序来公约
数据类型一样，把东西拉 有时，在里面你的常量
头文件不一定 你的C文件，当然，当你的
方案变得越来越大，从而使 你知道到哪里寻找既为
在某些情况下，文档或 基本这个样子，
某种类型的定义。
>> 如果我现在打开列表零点 C，注意的几件事情。
它包括了几个头文件，最 我们之前见过。
它包括其自己的头文件。
>> 顺便说一句，这就是为什么双 报价。在这里，相对于角度
括号就行了， 我已经强调了那里？
>> 学生：[听不清]。
>> 扬声器1：是啊，所以它是一个本地文件。
所以，如果你自己在这里的本地文件 第15行，例如，您可以使用
双引号，而不是 的尖括号。
>> 现在，这是一种有趣的。
注意，我已经宣布为全球 这个程序的第18行的变量
被称为第一想法是这是 将是一个指针指向第一个
在我的链表节点，并且我 初始化为null，因为我
没有分配任何实际 节点只是还没有。
>> 因此，这代表1973年，我们 刚才也看到了图片作为
该指针远 左手侧。
所以现在，该指针 不会有一个箭头。
相反，它仅仅是空的。
但它代表的会是怎样的 第一个实际的地址
在此列表中的节点。
所以，我已经实现了它是一个全球 因为，你会看到，这一切
计划并落实在生活中是 一个链表为我。
>> 现在我已经得到了一些原型。
我决定实现的功能，如 缺失，插入，搜索和
穿越 -
最后只是徒步穿越 列表，打印出它的元素。
而现在，这里是我的主程序。
并且我们不会花太多时间 这些，因为这是那种，希望
现在的旧帽子。
>> 我要做到以下几点： 而用户合作。
所以，我要打印 出此菜单。
我格式化它作为 干净，尽我所能。
如果用户在一个类型，即表示 他们要删除的东西。
如果用户有两种类型，即表示 他们要插入的东西。
等等。
我要提示 然后命令。
然后我要使用调用getInt。
>> 所以这是一个非常简单的menuing 界面，您只需要输入
一些映射到一个 这些命令。
现在我有一个漂亮干净的开关 语句要切换
无论用户输入。
而且，如果他们输入了一个，我会 调用delete和突破。
如果他们输入了两个，我会 调用插入和突破。
>> 现在请注意，我已经把每 这些在同一行上。
这是一种风格上的决定。
通常情况下，我们已经看到的东西 像这样。
但我刚刚决定，坦率地说，我的程序 看上去更具可读性，因为
它只有四个案件 像这样只列出。
完全合法使用样式。
我要做到这一点，只要 用户没有输入零，这是我
决定将意味着他们想戒烟。
>> 所以，现在发现我什么 要在这里做。
我要去显然释放的清单。
但在短短的时刻。
首先，让我们来运行这个程序。
因此，让我一个更大的终端 窗口，点斜线列表0。
我要继续前进并插入 50这样的数字，现在打字两
你会看到列表中现在是50。
我的文字只是滚动了一下。
所以，现在看到列表中包含 数字50。
>> 让我们做另一个采取两个插入。
让我们像一个输入的数量。
列表现在，接着为50。
所以这仅仅是一个文字表述 列表。
我们插入一个像 数字42，这是有希望的
要结束了，因为在中间 特别是各种程序
它插入他们的元素。
因此，我们有它。
超级简单的程序，可以 绝对使用一个数组，但我
碰巧使用一个链表 就这样我就可以动态地
增长和收缩。
>> 因此，让我们来看看搜索，如果我 运行命令三，我想搜索
，也就是说，43号。
显然并没有什么发现， 因为我回来没有反应。
因此，让我们再次做到这一点。
搜索。
50，或者更确切地说，搜索的搜索 42，有一个很好的
有点微妙的含义。
而且我发现有生命的意义。
42，如果你不知道 参考谷歌。
好的。
那么是什么为我做这个程序？
它只是让我插入从而 到目前为止，搜索元素。
>> 让我们快进，那么， 我们瞟了一眼那个函数
周一传情。
所以，我要求这个功能，搜索 第一列表中的一个元素
一，提示用户，然后调用 调用getInt得到一个实际的int
要搜索。
>> 然后注意到这一点。
我要创建一个临时变量 在第188行称为指针 -
PTR -
可以把它叫做什么。
这是一个节点的指针 因为我说有节点*。
我初始化它等于 首先，让我实际上是我的
手指，可以这么说，就非常 列表中的第一个元素。
所以，如果我的右手是PTR我 指向同一件事，第一
是否对准。
>> 现在，我们回到代码中， 接下来会发生什么 -
迭代时，这是一个共同的范式 像结构
链表。
我要做到以下几点，同时 指针不等于空，因此，
我的手指指着一些空 值，如果指针箭头n等于N。
我们首先会注意到，n是什么 用户输入每GetInts这里打电话。
>> 和指针箭头N意味着什么呢？
好吧，如果我们再回到这里的图片， 如果我有一个手指指着
九，即第一个节点 箭头基本上意味着去那
节点，并抢在位置n的值， 在这种情况下，数据字段称为N。
>> 顺便说一句 - 我们看到一对夫妇 星期前，当有人问 -
这个语法是新的，但它不 给我们的权力，我们
没有已经有了。
这句话是什么相当于使用 点符号和明星夫妇
星期前，当我们剥开 这一层有点过早？
>> 学生：[听不清]。
>> 扬声器1：没错，这是明星， 那么它是星点N，
括号在这里，它看起来， 坦率地说，我想了很多
更神秘的阅读。
但星级指针，一如既往 手段去那里。
而一旦你在那里，什么样的数据 现场你要访问吗？
那么你用点符号访问 一个结构的数据字段，我
特别希望N。
>> 坦率地说，我认为这 只是很难阅读。
这是很难记得在哪里 做括号走，
明星和一切。
因此，世界上采取了一些句法 糖，可以这么说。
只是一个性感的说法， 这是等价的，并且
或许更直观。
如果指针确实是一个指针， 箭头符号手段去那里找
在这种情况下，该领域称为N。
>> 所以，如果我找到它，发现我做什么。
我只是打印出来，我发现我％， 堵在这个int值。
我叫睡一秒钟只是一种 暂停在屏幕上的东西
给用户一个第二吸收 刚刚发生了什么。
然后我就打破。
否则，我该怎么办？
我更新指针等于 指针旁边的箭头。
>> 所以，仅仅是明确的，这意味着去 在那里，我的老学校的符号。
因此，这只是意味着去任何 你指出，这在很
第一种情况是，我指着 结构九。
所以，我去那里。
然后点符号表示， 在未来获得价值。
>> 但该值，即使它的绘制 作为窄，仅仅是一个数字。
这是一个数字地址。
所以这一行代码，无论 这样写，更神秘
的方式，还是这个样子，稍微 直观的方式，只是意味着移动我的手
从第一个节点到下一个， 然后下一个，然后
下一个，等等。
>> 因此，我们不会纠缠于其他 插入和删除的实现
和遍历，前两个 这是相当复杂的。
而且，我认为这是很容易得到 做口头丢失。
但我们可以在这里做什么 尝试，以确定如何
最好做视觉。
因为我会提出，如果我们 要插入元素
现有的名单，其中 有五个要素 -
9，17，22，26，33 -
如果我要实现这 代码，我需要考虑如何去
这样做。
>> 我建议采取小步 据此，在这种情况下，我的意思是什么
可能出现的情况，我们 可能遇到的一般？
当执行插入一个链接 名单，这恰好是一个
具体例的大小为5。
好吧，如果你要插入一个数字， 喜欢说的头号
保持排序顺序，其中 显然做一个需要数
走在这个具体的例子吗？
开始时一样。
>> 但有趣的是 如果你要插入到这个
列表中，需要什么特殊的指针 显然要更新？
第一。
所以，我认为，这是第一种情况 我们可能要考虑，
方案涉及于 在列表的开头。
>> 让我们为这事也许容易，甚至 更简单的情况下，相对来说。
假设我要插入 35号排序。
这显然​​属于那边。
那么，什么指针，显然是要 在这种情况下必须进行更新？
34的指针变得不空 但该结构的地址
含有数字35。
因此，案例二。
所以，我已经是量化排序 在这里我必须做多少工作。
>> 最后，明显的中间的情况下是 的确，如果我在中间，要
插入像说23，云 在23和26之间，但
现在事情变得有点更 因为涉及什么
指针需要改变吗？
因此，22显然需要改变 因为他不能点到26了。
他需要，以指向新节点 我将不得不通过调用分配
malloc或一些等价。
>> 但是，我也需要新的节点，23 在这种情况下，有它的指针
指向谁？
26。
而且也将是一个 这里的操作顺序。
因为如果我这样做愚蠢的是，我和 实例的开始处开始
列表中，我的目标是要插入23。
检查，它属于 在这里，近九？
号
它属于这里，未来17？
号
是否属于这里旁边22？
是。
>> 现在，如果我在这里很愚蠢的，而不是 通过思考，我可能
分配我的新节点上为23。
我可能会更新指针 节点称为22，指着
在新的节点。
然后我有什么更新 新节点的指针？
>> 学生：[听不清]。
>> 扬声器1：没错。
指着26。
但是，该死，如果我没有已经更新 22的指针指向这个家伙，
现在我有孤儿，其余 列表，可以这么说。
所以，这里的操作顺序 会是重要的。
>> 要做到这一点，我能偷， 说，六个月志愿者。
让我们来看看，如果我们不能做到这一点 视觉上，而不是代码明智。
我们有一些可爱的压力 今天为你的球。
OK，约一，两个，在 回 - 到底有没有。
三，四，双方你 家伙到底。
及五，六。
当然。
五和六。
好吧，我们还会回来 你们下一次。
好吧，我们就到了。
>> 所有的权利，因为你先在这里 你想成为一个笨拙
在谷歌的玻璃在这里？
好，那么，OK，玻璃， 录制视频。
OK，你去好。
>> 所有的权利，所以如果你们可以过来 在这里，我已经提前做好准备
一些数字。
好吧，我们在这里。
而你为什么不走一点 进一步的方式。
，让我们看看，你叫什么名字， 谷歌玻璃？
>> 学生：本。
>> 扬声器1：本？
OK，奔，你将是第一，从字面上。
因此，我们会向您发送 结束阶段。
所有的权利，和你的名字吗？
>> 学生：贾森。
>> 扬声器1：杰森，OK你 9号。
所以，如果你想遵循本办法。
>> 学生：吉尔。
>> 扬声器1：吉尔，你要去 17，如果我这样做
智能，我将不得不 在其另一端开始。
你走那条路。
22。
你是谁？
>> 学生：玛丽。
>> 扬声器1：玛丽，你会是22。
你的名字是什么？
>> 学生：克里斯。
>> 扬声器1：克里斯，你会是26。
然后最后。
>> 学生：戴安娜。
>> 扬声器1：戴安娜，你会是34。
所以你在这里。
>> 好吧，如此完美排序 已经订购。
，让我们继续前进，为此 这样我们就可以真的 -
奔你只是寻找一种 到无处存在。
OK，让我们继续前进，并描绘这个 使用武器，就像我，究竟
这是怎么回事。
因此，继续前进，给自己一个 步行或两个自己之间。
继续前进，用一只手点 你应该指向谁
在此基础上。
如果你只是指向空 直下到地板上。
OK，这样很好。
>> 所以现在我们有一个链表，让我 建议，我会发挥的作用
PTR，所以我不会打扰 携带这种左右。
然后 - 有人愚蠢的惯例 - 你可以调用任何你想要的 -
前身指针，泼尼松指针 -
它只是我们给的绰号 我们的示例代码，我的左手。
另一方面，要保持 谁是谁在跟踪
下面的场景。
>> 因此，假设，第一，我要拔掉 ，插入第一个例子，说
20，到列表中。
所以我需要有人来 体现我们20号。
所以我需要有人对malloc 从观众。
上来吧。
你叫什么名字？
>> 学生：布莱恩。
>> 扬声器1：布莱恩，所有的权利，所以你 须含20的节点。
好吧，我们在这里。
很显然， 不属于布赖恩？
因此，在中间 - 实际上， 等待一分钟。
我们这样做是为了
我们正在做这个了很多困难 比它需要的是在第一次。
OK，我们要免费布赖恩 和realloc的布赖恩五个。
>> 好了，现在我们要插入 布赖恩五个。
这样一来就在这里 本只是一瞬间。
你大概可以告诉 这个故事是怎么回事。
但是，让我们仔细想想 操作顺序。
和它的正是这种视觉 要排队
与示例代码。
所以，我在这里已经PTR最初指向 不奔，本身的，但在任何
重视他包含在这种情况下 - 再次你叫什么名字？
>> 学生：贾森。
>> 扬声器1：杰森，所以我和Ben 指着杰森在这一刻。
所以现在我必须确定， 布赖恩属于哪里？
那么唯一，我曾访问 现在是他的n个数据项。
所以我要来检查， 布赖恩小于贾森？
答案是真实的。
>> 那么现在需要什么发生， 以正确的顺序？
我需要更新多少指针 总在这个故事呢？
在哪里，我的手仍指向 杰森，和你的手 - 如果你想
把你的手，有点像，我 不知道，是一个问号。
好，好。
>> 好吧，让你拥有 几个候选人。
奔或I或布赖恩或杰森 或其他人，这
指针需要改变吗？
总共有多少人？
>> OK，所以两个。
我的指针并不真的无所谓了 因为我只是暂时的。
因此，它是这两个家伙，据推测， Ben和布赖恩。
所以我建议大家更新 奔，因为他是第一。
这个列表的第一个元素 现在将是布莱恩。
因此，本布赖恩点。
OK，现在该怎么办呢？
>> 谁被指出在谁？
>> 学生：[听不清]。
>> 扬声器1：确定Brian拥有 以指向贾森。
但我已经失去了该指针的轨道？
我知道Jason是吗？
>> 学生：[听不清]。
>> 扬声器1：我做的，因为我 暂时指针。
而据推测，我并没有改变 指向新的节点。
所以，我们可以简单地布赖恩点 我指着谁。
我们就大功告成了。
所以，在插入 开始的名单。
有两个关键步骤。
一，我们必须更新奔，然后 我们也有更新布赖恩。
然后我没有打扰 其余的疲惫
名单，因为我们已经找到了自己的 位置，因为他属于
左侧的第一个元素。
>> 所有的权利，所以非常简单。
事实上，感觉就像我们几乎 这太复杂了。
现在让我们为这事结束 列表，看到
开始的复杂性。
因此，如果现在，我的alloc从观众。
任何人想打55？
好吧，我先看到你的手。
上来吧。
嗯。
你叫什么名字？
>> 学生：[听不清]。
>> 扬声器1 Habata。
OK，就到了。
你会是55号。
所以，你，当然，属于 上面的列表末尾。
因此，让我们重播模拟与我 是PTR只是一瞬间。
所以，我首先要指向 无论奔指向。
我们都指向现在在布赖恩。
因此，图55是不小于5。
所以，我要更新自己的 Brian的下一个指针，指向谁
现在当然贾森。
图55是不小于9，所以 我要更新PTR。
我要更新的PTR 我更新的PTR。
我要去 - 嗯，有什么 你的名字吗？
>> 学生：戴安娜。
>> 扬声器1：戴安娜是指指点点，当然， 在null与她的左手。
那么，这实际上Habata 属于清楚吗？
到左边，在这里。
所以，我怎么知道在这里把她 我想我搞砸了。
因为PTR艺术 时间在这一刻？
NULL。
因此，即使，在视觉上，我们就可以 明显看到所有这些
这里的人在舞台上。
我以前没有记录 在列表中的人。
我没有手指指出， 在这种情况下，节点号为34。
>> 因此，让我们真正开始过。
所以，现在我居然需要 一个第二局部变量。
这是什么，你会看到在 实际样品的C代码，在那里，因为我去，
当我更新我的右手指向 杰森，从而留下布赖恩的背后，我
最好开始用我的左手 更新我在哪里，让我去
通过这个名单 -
比我预期的更笨拙 现在这里视觉 -
我会去的 列表末尾。
>> 这手仍是空的，这是非常 没用的，其他的比来表示
我很清楚在列表末尾， 但现在至少我有这个
前身指向这里，所以 现在是什么手和指针需要什么
要更新？
你想谁的手 先来重新配置？
>> 学生：[听不清]。
>> 扬声器1：OK，所以戴安娜的。
在哪里你想点 戴安娜的左指针？
在55中，据推测，从而使 我们已经有插入。
55指针应该在哪里去了？
向下，占空。
而我的手，在这一点上，不 不要紧，因为他们只是
临时变量。
所以，现在我们就大功告成了。
>> 所以额外的复杂性 - 它并不难实现，
但我们需要一个辅助变量 确定之前，我将我的权利
另一方面，我更新我的左值 另一方面，泼尼松指针在这种情况下，因此
我有一个尾随指针 跟踪我在哪里。
顺便说一句，如果你以为这 通过，这种感觉就像是一个
必须保持有点烦 跟踪这个左手。
>> 将另一种解决方案 这个问题已被？
如果你得到了重新设计数据 我们正在谈论的结构
通过吧？
如果这只是一种感觉有点 恼人的一样，两个指针
通过列表，谁还能 有，在一个理想的世界中，保持
我们所需要的信息？
是吗？
>> 学生：[听不清]。
>> 扬声器1：没错。
所以实际上是一个有趣的 胚芽的想法。
而前一个指针，这个想法 指向前一个元素。
如果我只是体现 列表本身的内部？
这将是难以想像 没有所有的纸张
掉落到地板上。
但是，假如这些人同时使用 他们手中没有先前
指针，和一个下一个指针，从而 执行什么，我们会打电话给一个双
链表。
这将允许我排序退， 更容易无我有，
程序员，不得不保持 手动跟踪 -
真正的手动 -
以前我一直 在列表中。
因此，我们将无法做到这一点。
我们将保持它的简单，因为这是 要来的价格，两倍
多的空间的指针， 如果你想要第二个。
但是，这确实是一个共同的 数据结构被称为一个
双向链表。
>> 让我们在这里做最后的例子把 这些家伙，他们的苦难。
所以malloc的20。
来吧从那里的过道。
好吧，你叫什么名字？
>> 学生：[听不清]。
>> 扬声器1：对不起？
>> 学生：[听不清]。
>> SPEAKER 1：Demeron的？
确定上来吧。
您应为20。
你显然要 属于17和22之间。
因此，让我吸取我的教训。
我要开始指针 指着布赖恩。
我要我的左手 只更新布莱恩，我谨
杰森，检查少做了20比9？
号
20小于17？
号
20小于22？
是。
那么，什么指针或手需要改变 他们指着呢？
>> 因此，我们可以做的17指向20。
所以这就是罚款。
我们要指出在哪里 你的指针现在？
在22。
我们知道22，再次感谢 我临时指针。
因此，我们有“确定”。
所以在这临时存储 我一直保留着的轨道，每个人都。
现在，你可以直观地去到哪里 属于你，现在我们需要1，2，3，
4，5，6，7，8，9个压力球， 和掌声雷动
这些家伙，如果我们能。
干得漂亮。
>> [掌声]
>> 扬声器1：所有权利。
您可能保持件 纸作为纪念。
>> 好，那么相信我，这是一个很大 更容易穿行
人类比它的实际代码。
但你会发现在短短的时刻 现在，是相同的 - 哦，谢谢你。
谢谢 -
是，你会发现相同的数据 结构，链表，实际上可以
可以使用作为构建块更 复杂的数据结构。
>> 实现过这里的主题是 我们绝对介绍
进入实施的复杂性 在此算法中。
插入，如果我们通过它去， 删除和搜索，是一个小的
比它更复杂 是一个数组。
但是，我们获得了一些活力。
我们得到一个自适应的数据结构。
>> 但同样，我们付出的代价有一些 额外的复杂性，无论是在
执行它。
我们放弃了随机访问。
而且说实话，有没有一些不错的 干净的玻片，我可以给你，
这里说的是为什么一个链表 优于数组。
离开它。
由于主题现在再次发生，甚至 更何况在未来几周内，
不一定 一个正确的答案。
>> 这就是为什么我们有独立的轴 问题集的设计。
这将是非常敏感的上下文 您是否要使用此数据
结构或那一个，会 取决于什么对你很重要条款
的资源和复杂性。
>> 但是，让我提出，理想的数据 结构，圣杯，将
东西是恒定的时间， 不论多少东西
在它里面，它不会是惊人的，如果一个 返回的数据结构答案
常量时间。
是。
这个词是在巨大的字典。
“或”否“，这个词是没有的。
或任何这样的问题。
那么让我们来看看，如果我们不能至少 走，一步步走向。
>> 让我提出了一个新的数据结构， 可用于不同的事情，
在这种情况下，所谓的哈希表。
所以我们实际上一眼 在一个数组中，在这种情况下，
有些武断，我画这 作为数组排序的哈希表
两维数组 -
或者更确切地说，它这里描绘为两 维数组 - 但是这仅仅是
大小为26的数组，例如，如果我们 调用数组桌，桌上托架
零是在顶部的矩形。
表托架25是矩形 在底部。
我这是怎么可能画出一个数据 我想存储结构中，
人的名字。
>> 因此，举例来说，我不会画 整个事情上的开销，如果我
该数组，我现在要 调用一个哈希表，这又是
零的位置。
这里是位置 一个，等等。
我要求，我想用这个数据 结构，为了讨论的方便，
存储人的名字，Alice和Bob 查理和其他类似的名称。
所以，现在觉得这个作为起点 ，也就是说，一个字典
有很多的话。
他们正好是名 在我们的例子。
这是太有密切关系，也许， 实施一个拼写检查，因为我们
可能问题设置6。
>> 所以，如果我们有一个总规模26阵列 因此，这是第25的位置
在底部，我要求爱丽丝 字典中的第一个字
名，我想插入RAM， 到该数据结构中，其中
爱丽丝的直觉告诉你， 在这个数组名称应该去？
>> 我们有26个选项。
如果我们想要把她吗？
我们希望她在支架为零，对不对？
为爱丽丝，我们称之为零。
和B，和C将有两个。
因此，我们打算写 爱丽丝的名字在这里。
如果我们再插入鲍勃，他 名称会去这里。
查理会去这里。
如此反复向下 这样的数据结构。
>> 这是一个美妙的数据结构。
为什么呢？
那么什么是运行时间 插入成这样的一个人的名字
数据结构的权利吗？
鉴于实施该表， 诚然，作为一个数组。
那么它的恒定时间。
这是一个顺序。
为什么呢？
>> 那么你如何确定 爱丽丝属于？
你看看她的名字的信吗？
第一。
在那里，你可以得到，如果它是一个字符串， 只是看着串
支架零。
因此，第0个字符的字符串。
这是很容易的。
我们已在加密 分配星期前。
然后，一旦你知道Alice的 字母是大写的A，我们可以减去
关闭65或资本A本身， 这给了我们为零。
因此，我们现在知道，爱丽丝属于 在零的位置。
>> 和给定的一个指针，指向这个数据 某种结构，多久？
它带我找到位置 阵列中的零？
只需一个步骤，这是恒定的时间 由于随机接入中，我们
建议的是一个数组的一个特征。
因此，在短期，搞清楚什么索引 Alice的名字，这是在
这种情况下，是A，或让刚刚解决 为零，其中B是C是
二，计算出 是恒定的时间。
我只是来看看她的第一个字母， 搞清楚其中零为
数组也是恒定的时间。
因此从技术上讲这是 像现在两个步骤。
但是，这仍然不变。
所以，我们称之为一大O，所以我们 爱丽丝插入到这个表中
常量时间。
>> 不过，当然，我 天真在这里，对不对？
如果在课堂上有亚伦？
还是艾丽西亚？
或任何其他的名字开始 A.我们要去哪里放
那人，对不对？
我的意思是，现在只有三个 老百姓餐桌上，所以也许我们
应该把亚伦的位置 零壹两三个。
>> 好吧，我可以在这里把A。
然而，如果我们尝试将大卫 这个名单，大卫去哪里？
现在，我们的系统开始打破 向下，向右？
因为现在，大卫在这里结束了 如果阿龙其实是在这里。
所以现在有一个整体思路 干净的数据结构，让我们
恒定的时间插入不再 恒定的时间，因为我有
检查，哦，该死的，有人已经 在爱丽丝的位置。
>> 让我探究这些数据的其余部分 结构，寻找一个位置把
有人喜欢亚伦的名字。
等也开始 线性时间。
此外，如果你现在想找到 亚伦在此数据结构，你
检查和亚伦的名字是不是在这里。
理想情况下，你只说亚伦 而不是在数据结构中。
但是，如果你开始做空间 亚伦那里应该有一个D
或E，你最坏的情况下，有检查 整个数据结构，在
这种情况下，移交到的东西 表的大小成线性关系。
>> 所以所有的权利，我会解决这个问题。
这里的问题是，我不得不 26此数组中元素。
让我改变它。
哎呀。
让我改变它，因此而幸福 大小26个，发现底部
指数将改变为n减1。
如果26显然是太小了人类的 的名字，因为有成千上万的
世界的名字，让我们使 在100或1000或10000。
让我们只分配更多的空间。
>> 嗯，这并不一定减少 的概率，我们不会有两个
人们起的名字， 所以，你要尝试将
名位置零。
他们还在碰撞， 意味着我们仍然需要一个解决方案，把
爱丽丝亚伦和艾丽西亚和其他 名开始与A别处。
但多少的问题是什么？
什么的概率 有碰撞在一个数据
这样的结构？
>> 好吧，让我 - 我们会回来的 这里这个问题。
看我们如何可能 先解决它。
让我拉起这个建议。
我们刚刚描述的是一种算法， 一个启发式称为线性
探测，即如果你试图插入 这里的东西在此数据
结构，该结构被称为一个哈希表， 而且也没有的房间里，你
真正探测的数据结构 检查，这是可用的？
这是这是可用？
这是？
而当它终于插入 名字，你原本打算
在该位置的其他地方。
但是，在最坏的情况下，唯一的现货 可能是最底层的数据
结构，数组的尽头。
>> 因此，线性探测，在最坏的情况下， 下放成线性算法
亚伦，如果他恰好是最后插入 这个数据结构中，他可能会
碰撞，该第一位置，但 然后结束坏运气的最末尾。
因此，这是不是一个常数 一次圣杯的我们。
这种方法插入元素 一种数据结构，称为散列
表不似乎是恒定的时间 至少不会在一般的情况下。
它可以下放成线性的东西。
>> 那么，如果我们解决冲突 有所不同呢？
因此，这里是一个更复杂 仍然接近
称为哈希表。
哈希，顺便说一句， 我的意思是指数
我前面提到的。
哈希的东西可以 想到作为一个动词。
>> 所以，如果你哈希爱丽丝一个名字， 哈希函数，可以这么说，
应该返回一个数字。
在这种情况下是零，如果她是属于 位置为零，如果她属于
的位置，等等。
所以，我的哈希函数迄今一直 超级简单，只看着
在别人的名字的第一个字母。
但是哈希函数需要 输入某些数据块，
一个整数，字符串，等等。
它吐出一个典型的数字。
而且这个数字是该数据 在数据结构中的元素属于
这里称为哈希表。
>> 所以只是凭直觉，这是一个 略有不同的上下文中。
这实际上是指一个例子 涉及的生日，
可能有多达 31月份中的天。
但是，什么人决定 做在发生碰撞时？
上下文，而不是现在的碰撞 名，生日，而是碰撞
如果两个人有相同的生日 10月2日，例如。
>> 学生：[听不清]。
>> 扬声器1：是啊，所以我们在这里有 利用链表。
因此，它看起来有点不同 把它比我们更早。
但是，我们似乎有一个数组 在左手侧。
这是一个索引，因为没有 特别的原因。
但它仍然是一个数组。
这是一个数组的指针。
每一元素，每个 这些圆圈或斜线 - 斜线
代表空 - 这些 指针显然指向
什么数据结构？
链表。
>> 所以，现在我们有能力 硬到我们的程序代码
表的大小。
在这种情况下，我们知道从未有 在一个月内超过31天。
所以硬编码值，如31 在这种情况下合理。
在名称的上下文中，硬编码 26是不讲理的人
名字才开始，例如， 涉及A到Z的字母
>> 我们可以塞进他们都到数据 只要结构，当我们得到一个
碰撞，我们不把这里的名字， 我们反而认为，这些细胞
不是字符串本身，而是作为 的指针，例如，爱丽丝。
然后爱丽丝可以有另一个指针 另一个名字开始
A.和鲍勃实际上是在这里。
>> 如果有另一个名字开始 B，他结束了在这里。
等各元素与该 表二，如果我们设计一个
更巧妙一点 -
来吧 -
如果我们设计了这个多一点 巧妙的，现在变成了一个自适应数据
结构，那里是没有硬性限制 你可以插入多少元素
到它，因为如果你这样做有 碰撞，这很好。
只要继续下去，并将它附加到 我们所看到的有点前
被称为一个链表。
>> 那么让我们来的暂停只是一瞬间。
碰撞的概率是什么 摆在首位？
对的，也许我过思考，也许 我在工程的这个问题，
因为你知道是什么吗？
是的，我可以拿出任意 关闭我的头顶部的例子喜欢
Allison和亚伦，但在现实中， 给定的均匀分布
投入，是一些随机插入 到一个数据结构，什么是真正的
碰撞的概率？
好吧原来，它实际上是 超高。
让我概括 问题是这个。
>> 因此，在一个房间里的n CS50学生，什么是 的概率，至少
两名学生在房间里 有相同的生日吗？
因此，有什么。几个洪德 -
200，300人在这里和几个 今天在家百余人。
所以，如果你要问自己什么 两个人的概率
在这个房间里有相同的生日， 我们可以弄清楚了这一点。
其实我要求有两个 同一天生日的人。
>> 举例来说，有没有人 今天生日吗？
昨天？
明天？
所有的权利，所以感觉像我要去 不得不做这363左右
次真正弄清楚 如果我们这样做，有碰撞。
或者，我们可以做到这一点数学 而不是繁琐
这样做。
并提出以下建议。
>> 所以，我建议，我们可以模拟 两个人的概率
同一天生日的概率为1 减去的概率没有一个具有
同一天生日。
所以就弄这个，这只是 花哨的编写方式，
在房间里的第一人，他或她 可以有任何其中一个可能的
生日的一年，假设365天 与人道歉
2月29日生日。
>> 因此，在这个房间里的第一人免费 有任意数量的生日
365的可能性，所以， 我们要做的，365除以365，
这是其中之一。
旁边的人在房间里，如果我们的目标 是为了避免碰撞时，也只能
有他或她的生日就如何 许多不同的可能的天？
364。
所以这个表达式中的第二项是 基本上这样做对我们的数学
通过减去一个可能的日子。
然后第二天，第二天， 第二天下来的总数
在房间里的人。
>> 如果我们再考虑，又是什么 的概率不是人人有
独特的生日，但1减去再次 ，我们得到了什么是一个表达式
可以很稀奇 这个样子。
但它更有趣 看视觉。
这是一个图表上的x轴 多少人在房间里，
生日数。
在y轴上的概率是 碰撞时，两个人
具有相同的生日。
>> 而从这个曲线是外卖 只要你喜欢40
同学们，你们是在90％的概率 ，combinatorically两个
人或以上有 同一天生日。
一旦你得到58人喜欢它的 几乎100％的机会两个
房间里的人将不得不 同一天生日，即使有
365或366个可能的桶， 只有58人在房间里。
只是统计学，你很可能会 得到的碰撞，在短
激励这个讨论。
即使我们得到看中这里， 开始这些连锁，我们还是
将有碰撞。
>> 所以引出了一个问题，什么是 成本做插入和删除
进入这样一个数据结构？
那么让我提出 -
并让我回到屏幕上对 在这里 - 如果我们有n个元素
列表，所以如果我们试图插入 n个元素，我们有
总共有多少桶？
比方说，共31桶 在的情况下的生日。
什么是最大长度为一个 这些链可能？
>> 如果再有31个可能 在一个给定月份的生日。
我们只是聚集大家 -
实际上这是一个愚蠢的例子。
让做26代替。
因此，如果实际拥有人名列 从A到Z，从而使
我们26的可能性。
我们使用一个数据结构，如 我们刚才看到的，据此，我们有
一个数组的指针，其中每个 指向一个链表地方的
第一份清单是每个人都 爱丽丝的名字。
第二个名单是每周与 命名开始，
为B，依此类推。
>> 什么可能各有长短 这些列表，如果我们假设一个干净的
从A到Z的名称分配 在整个数据结构？
有n个人的数据结构中 除以26，如果他们很好
摊开在整个 的数据结构。
因此，每个这些的长度 链为n除以26。
但在大O表示法，那是什么？
什么是真的？
所以这真的只是N，对不对？
因为我们说，在过去， 唉你除以26。
是的，在现实中，它是速度更快。
但是，从理论上讲，它不能从根本上 所有的更快。
>> 因此，我们不似乎是所有的东西 接近本圣杯。
事实上，这仅仅是线性时间。
哎呀，在这一点上，为什么我们不 只使用一个巨大的链表？
为什么我们不只是用一个巨大的 数组来存储的名称
每个人都在房间里吗？
嗯，还有东西 引人注目的一个哈希表？
还有一些引人注目的 关于数据结构的
看起来像这样吗？
此。
>> 学生：[听不清]。
>> 扬声器1：右键，并再次，如果它只是 一个线性时间算法，并有
线性时间的数据结构，我为什么不 只是在一个大的存储每个人的名字
阵列，或在一个大的链表？
停止CS这么更难 比它需要的吗？
什么是引人注目的，甚至 虽然我划出来？
>> 学生：[听不清]。
>> 扬声器1：插入都没有？
昂贵了。
因此，插入可能仍然 时间是恒定的，即使你的数据
结构看起来是这样的，琳琅满目的 指针，其中每个指向
潜在的链表。
你怎么能实现恒 时间插入的名字？
把它贴在了前面，对不对？
>> 如果我们牺牲一个设计目标 所说，我们希望保持
每个人的名字，例如，排序， 舞台上所有的数字排序，
假设我们有一个 未分类的链表。
我们只需花费一个或两个步骤， 像Ben和布莱恩的情况下
早些时候，插入一个元素 在列表的开头。
因此，如果我们不关心排序的所有 开头的名字或全部
以B开头的名字，我们仍然可以 实现恒定的时间插入。
现在回头Alice或Bob或任何名称 更普遍的仍是什么？
大O的n除以26，在 理想情况下，每个人的均匀
分布，其中有尽可能多的 有Z的，这可能是
不现实的。
但是，这仍然是线性的。
>> 但在这里，我们再回过头来点 渐近符号
理论上确实如此。
但在现实世界中，如果我要求 我的程序可以做一些26倍
速度比你的，其程序 你要喜欢使用？
你的还是我， 快26倍？
实际上，人是26 倍的速度，即使在理论上
我们的算法运行在相同的 渐近运行时间。
>> 让我提出一个不同的 完全的解决方案。
如果这不吹你的头脑， 我们的数据结构。
因此，这是特里 -
样的一个愚蠢的名字。
它来自检索，字 拼写特里，T-R-I-E，因为
当然检索听起来像特里。
但是，这是历史 的特里字。
>> 因此，一个特里确实是某种树， 它也是一上场就那个字。
即使你可以不太看到它 这个可视化，特里是一个
树结构，就像一个家庭树 在顶部和意见的一个祖先
孙子和重孙 离开底部。
但特里在每个节点是一个数组。
，它是在一个数组 - 让 过于简单化了一会儿 - 这是一个
阵列，在这种情况下，大小为26，其中 每个节点是数组的大小为
26的方法，其中在第零个元素 数组代表A，最后
在每个这样的元素 数组代表Z。
>> 所以，我建议，那么，这个数据 结构，称为一个特里，可
也用于存储字。
我们刚才也看到了，我们如何能够存储 的话，在这种情况下，名称，这样我们
前面所看到的，我们如何能够存储数字， 但如果我们专注于名或字符串
这里，发现什么有趣的。
我要求麦克斯韦的名字是 内的这样的数据结构。
你在哪里看到麦克斯韦？
>> 学生：[听不清]。
>> 扬声器1：在左边。
那么，有什么有趣的与此数据 而不是存储结构
串M-à-X-W-E-L-L反斜杠零，所有的 连续，就是你，而不是做
以下。
如果这是一个类似的数据结构的线索， 的每个节点又是一个数组，
，你想，你先存储麦克斯韦 指数和根的节点，所以
说话，最上面的节点， 右，所以在位置M，
大致可分为中间。
然后从那里，你遵循 一个子节点的指针，可以这么说。
所以家谱感， 你跟着它向下。
导致你到另一个节点 左边有，这是
只是另一个数组。
>> 然后，如果你想存储麦克斯韦， 你找到指针，表示
A，这是此人在这里。
然后你去到下一个节点。
和通知 - 这就是为什么图片的 有点自欺欺人 -
这个节点看起来超级微小的。
但是，这样做的权利是Y和Z。 这只是笔者已截断
图片，让你实际上 看到的东西。
否则这幅画 将是巨大的宽。
所以，现在你的索引位置X，然后 W，然后E，那么L，L，然后有什么
这种好奇心？
>> 那么，如果我们正在使用这种新 采取有关如何存储中的字符串
数据结构，你仍然需要 基本上在数据核对
结构词语到此为止。
换句话说，这些节点中的每个节点 不知何故要记住，我们
后面其实所有这些指针 并留下一点点
面包屑的底部，在这里对本 结构示意M-à-X-W-E-L-L
确实这个数据结构中。
>> 因此，我们可能会做如下。
我们只是在图片中的每一个节点 锯有一个大小为27的数组。
它现在27，因为在p设置6个， 实际上，我们就会给你一个撇号，
所以我们可以有名称，如奥赖利 和其他带撇号。
但同样的想法。
在这些元素 阵列指向一个struct
节点，所以只是一个节点。
因此，这很容易让人想起 我们的链表。
>> 然后我有一个布尔值，我将 致电字，这是只是要
如此，如果一个词结束 树中的节点。
它有效地代表小 三角形，我们刚才也看到了。
因此，如果有一个字在该节点处结束 树，那田字是真实的，
在概念上被检查过，或 我们绘制这个三角形，是有
这里是一个字。
>> 所以这是一个特里。
现在的问题是，什么 是它的运行时间？
它是大O的n？
是别的原因呢？
好吧，如果你有n个名字，在此数据 结构，麦克斯韦只是其中之一
他们，什么是运行时间 插入或找到马克斯韦尔？
什么是运行时间 插入麦克斯韦？
如果有n其他名称 已经在表中？
是吗？
>> 学生：[听不清]。
>> 扬声器1：是的，它的长度 的名字，对不对？
所以M-A-X-W-E-L-L，所以这样的感觉 算法是大O七。
现在，当然，该名称 将长短不一。
也许这是一个简短的名称。
也许这是一个较长的名称。
但这里的关键是， 这是一个常数。
也许这不是真的不变， 不过神来，如果实事求是，在
字典里，可能有一些限制 中的字母的数目
在某个特定国家的人的名字。
>> 因此，我们可以假设， 值是一个常数。
我不知道它是什么。
这也可能是大于 我们认为它是。
因为总有一些角落 一个疯狂的长名称的情况。
因此，让我们叫它K表，但它仍然是一个 常数，大概，因为每一个
命名在世界上，至少在 特定的国家，该长度或
短，所以它是恒定的。
但是，当我们已经说了一句大 O的一个恒定值，那是什么
真的等同吗？
这真的是同一件事 说恒定的时间。
>> 现在，我们是一种欺骗，对吧？
我们利用一些理论 这里要说的是，订单的k
真的只是为了一个， 和它的持续时间。
但它确实是。
因为这里的关键洞察力是 如果我们有n个名字已经在这
数据结构，我们插入麦克斯韦 是需要我们的时间量
在所有受影响的插入麦克斯韦 有多少人
在数据结构中？
似乎不。
如果我有一个10亿多元素 特里，然后插入麦克斯韦，
他在所有受影响？
号
而这不同于任何一天的数据 结构到目前为止，我们已经看到，其中
你的算法的运行时间是 完全独立的多少
东西已经是或不是 在该数据结构中。
>> 因此，与这提供了你现在是一个 机会对p六集，这将
再次涉及实施自己的 拼写检查器，读入150,000
的话，如何最有效地存储， 不一定是显而易见的。
虽然我渴望找到 圣杯，我不
声称，特里。
事实上，一个哈希表，很可能 被证明是更有效的。
但那些只是 -
这只是一个设计决策 你将不得不作出。
>> 但在收盘让我们50岁左右 秒采取偷看是什么样的
下周提前超出了我们的过渡 从这个命令行
世界上，如果C程序网络的事情 基于语言，如PHP，
JavaScript和互联网本身， 协议，如HTTP，你
理所当然的多年 现在，类型最
一天，也许，或可见一斑。
我们将开始剥开 层是什么是互联网。
什么是代码， 今天的基础工具。
所以，50秒这个传情。
我给你的净勇士。
>> [视频回放]
>> 他带来一个消息。
有了自己的协议。
他来到世界残忍防火墙， 漠不关心的路由器和危险远
比死亡更糟糕。
他的速度快。
他很强壮。
他的TCPIP。
他有你的地址。
勇士净。
>> [END视频播放]
>> 扬声器1：这是如何在互联网上 应下周工作。