>> [音乐播放]
>> [视频回放]
>> - 他在说谎。
>> -关于什么？
>> -我不知道。
>> - 所以我们怎么知道？
>> - 即在9:15，雷 Santoya是在自动取款机。
- 是啊。
所以，问题是，什么样 是他在9:16做什么？
>> -Shooting的9毫米的东西。
也许他看到了狙击手。
>> - 或者是和他一起工作。
>> -Wait。
回到之一。
>> -你看到了什么？
>> -Bring脸上了整个屏幕。
>> -His眼镜。
>> - 存在的一种反映。
>> - 它是在努埃维塔斯棒球队。
这是他们的标志。
>> - 和他交谈 谁穿着那件夹克衫。
>> [结束播放]
>> DAVID马兰：好的。
这是CS50，这是一个有点多 的[听不清]与你
有问题的涉足设4。
今天我们先来了解一下多一点 深入这些东西叫做三分球，
这即使它 一个非常神秘的话题，
事实证明，这是怎么回事 是通过何种途径，我们
可以开始构建和组装 更复杂的方案。
但是我们做到了上周三 一些粘土动画的第一种方式。
所以这一点，召回，是 宾基，我们用他
要看一看一个程序， 真的没有做什么有趣的事，
但它确实揭示了一些问题。
因此，为了从今天开始，我们为什么不走 快速通过几个步骤，
尝试提炼到人的方面 什么是怎么回事
为什么这是不好的，然后继续前进 而真正开始构建的东西
这种技术？
因此，这些是第一 该程序中的两行
在通俗地说，是什么 在这两条线在做什么？
有人谁是相当舒适 用什么屏幕上的声明？
什么是这两条线在做什么？
这还不是所有的 从一周不同，
但有一些新的特殊符号。
是吗？
回到那里。
>> 听众：声明指针？
DAVID马兰：再说一遍吗？
听众：声明指针？
DAVID马兰：声明指针和 让我们来完善它多一点点。
听众：[听不清] 地址X，那么y。
DAVID马兰：然后解决。
那么具体是什么，我们正在做 是我们宣布的两个变量。
这些变量，虽然，将会 是int类型的明星，哪
更具体地指 他们将要存储
一个int的地址， 分别使用x和y。
现在还有什么价值？
有没有在这些任何实际地址 两个变量在这个时间点？
第
这只是所谓的垃圾值。
如果你不实际分配 变量，无论是在RAM中
以前是要填补零 和那些这两个变量。
但是，我们还不知道 它们是什么，这就是
将是关键，为什么宾基 上周失去了他的头。
>> 因此，这是粘土动画 这个化身
因此你只有两个变量， 小环形件粘土，
可以存储的变量，但作为 该包裹起来箭头提示，
他们不是真正指向 到任何地方本身已知。
于是，我们有这条线，这 是新的，上周的malloc内存
分配，这仅仅是一个奇特的方式 告诉操作系统，Linux的的
或Mac OS或Windows， 嘿，给我一些记忆，
而你要告诉 操作系统
就是要求它的内存时。
它不会去关心什么 你会用它做什么，
但你需要告诉工作 什么系统由malloc的方式。
是吗？
>> 听众：多少钱？
DAVID马兰：多少钱？
多少字节，所以，这再次 一个人为的例子，只是说，
给我一个int的大小。
一个int现在，大小 是四字节或32位。
因此，这只是一种方式 他说，嘿，操作系统，
给我4个字节的内存 我可以用在我手上，
具体有哪些呢 malloc的收益相对于
以四个字节块？
听众：地址？
DAVID马兰：地址。
四个字节块的地址。
没错。
所以这就是所储存的最终 在x和这就是为什么我们真的不
关心的是，数 地址是，无论是OX1或OX2
或者一些神秘的十六进制地址。
我们只关心形象化 那该变量x是现在
指向的内存块。
这样的箭头表示的指针，或 更具体地说，存储器地址。
但是再次，我们并不关心通常 什么样的实际地址。
现在，这条线说： 什么通俗地说？
星x被42分号。
这是什么意思？
你想去？
不要划伤你的脖子。
>> 听众：x的地址是在42。
>> DAVID马兰：x的地址是42位。
不太。
如此接近，但并不完全，因为有 多数民众赞成这个前缀X中的明星。
因此，我们需要调整一点点。
是吗？
>> 听众：值了 指针x被指向的是42。
DAVID马兰：OK。
的值，该指针x是 指着，让我们说，应是42，
或者换一种方式，星 x说，去到任何地址
在X，无论是1牛津 街或33牛津街
或OX1或ox33，无论 该数字地址，
明星x是x的间接引用。
所以去该地址并 然后把数字42出现。
因此，这将是一个 的话说，相当于途径。
所以这一切都很好，然后 我们将代表图象
如下所示，我们已经添加 42到四个是块
字节上的右手边，但 这条线是那里的东西去了歪
和宾基的头部弹出 关于这一点，
因为不好的事情发生时， 取消引用垃圾值
或取消引用无效 指针和我说无效
因为在这一点上，在 故事，什么是Y的内部？
什么是Y的基础价值 在过去的几个步骤？
是吗？
那是什么？
>> 听众：一个地址。
DAVID马兰：地址。
它应是一个地址 但我初始化呢？
所以我还没有。
那么，什么是已知的在那里？
这只是一些垃圾的价值。
它可以是从零到任何地址 2十亿，如果你的RAM 2演出，
或零4个十亿，如果你已经 有4 GB的RAM。
这是一些垃圾的价值， 但问题是
操作系统， 如果没有给你
该内存块专 你试图去，
它通常会导致什么 我们已经看到了一个分段错误。
所以，事实上，任何你们谁 在挣扎于办公时间问题
或者问题，更 通常，试图找出
段错误， 这通常意味着
你触摸的段 内存，你不应该。
你触摸内存 操作系统有不
让你触摸，无论是 通过去太远阵列
或者从现在开始，无论是 那是因为你接触
内存仅仅是一些垃圾的价值。
>> 这样算下来星X这里是 那种不确定的行为。
你不应该这样做，因为赔率 是，该方案只是将崩溃，
因为你说， 去这个地址
你不知道在哪里 该地址实际上是。
因此操作系统很可能 将你的程序崩溃
因此，事实上，这是 那里发生的事情来宾基。
所以，最后，宾基固定 此问题与此。
这样程序本身是有缺陷的。
但是，如果你之类的锐意进取 并执行此行，而不是，
Ÿ度等于x只是意味着什么 地址是一个X，也把它的年。
>> 因此形象化，我们已经 有两个箭头表示这
从x和从y中指点 同一个地方。
因此语义，x等于 为y，因为这两项的
都存储相同 地址，ERGO指着42，
而现在，当你说明星 Y，转到地址Y，
这有一个有趣的副作用。
因此，在y中的地址是 同样的事情在X中的地址。
所以，如果你说去地址 在Y和值更改为13，
还有谁受影响？
X的，点D，可以这么说， 应该受到影响。
>> 事实上，尼克怎么画了这幅画 在粘土动画正是这一点。
即使我们按照指针 Y，我们结束了在同一个地方，
所以，如果我们要打印 出X或Y的指针对象，
那么我们将看到13的值。
现在，我说指针对象是 与视频一致。
程序员，我 知识，从来没有真正
说一句话指针对象， 这是尖
在，但对于一致性 与视频，实现
这一切，这是 意味着在这种情况下。
因此，对粘土动画有任何疑问 或指针或malloc的，只是还没有？
没有？
好吧。
>> 因此，没有进一步的 废话不多说，让我们一起来看看
在其中，这实际上已经 已经使用了一段时间。
因此，我们有这个CS50库 这得到了所有这些功能。
我们使用调用getInt很多，GetString的， 也许更早GetLongLong
在我的PSET一左右，但 什么实际已经持续？
好吧，让我们快速浏览一下 罩在一个程序下方那
激励我们为什么给你CS50 图书馆，实际上截至上周，
我们开始采取这些 训练车轮关闭。
因此，这是现在排序 一个死后是什么
已经持续 在CS50库中，
即使我们现在将开始移动 远离它对于大多数程序。
>> 因此，这是一个名为scanf函数0的程序。
它的超级短。
它只是这些行，但它 引入了一个函数调用scanf函数
那我们究竟要看到 片刻CS50库里面，
尽管在一个稍微不同的形式。
所以这个方案行16 正在申报一个变量x。
所以给我四个字节为一个int。
它在告诉用户， 号码请，然后
这是一个有趣的行 上周实际联系在一起
和这个。
scanf函数，然后发现它需要一个 格式字符串，就像printf的，
％我是指一个int，然后它需要一个 这看起来有点第二个参数
时髦。
它的符号x和召回， 我们只有这一次看到上周。
这是什么符号的x代表？
C语言是什么符号呢？
是吗？
>> 听众：地址。
DAVID马兰：的地址。
因此，它是相反的 星运营商，
而明星接线员说，去 这个地址，符号运算符
说，计算出 这个变量的地址，
所以这是关键，因为 scanf函数的人生目标
是扫描用户的 从键盘输入，
根据不管他或她 类型，然后读取该用户的输入
成可变的，但我们 在过去两个星期看到
这是交换功能，我们 试图轻松实现
刚刚打破。
回想一下，与交换功能， 如果我们只是宣布A和B为整数，
我们也成功地交换 互换中的两个变量
只是想用牛奶和OJ， 但只要换回来了，
结果是什么就 x和y，原始值？
什么也没有。
是啊。
什么都没有发生的时候，因为 掉期只改变它的本地副本，
这就是说，所有 这个时候，每当我们已经
被传入的参数 到功能，我们
刚好路过的那些参数的拷贝。
你可以用那些 无论你想和他们在一起，
但他们将不得不无 上的原始值影响。
因此，这是有问题的，如果你 想拥有像scanf函数的函数
在生活中，其目的是要扫描 用户的从键盘输入
然后填补空白，所以 说话，就是给如x变量
一个值，因为如果我是 只是传递X到scanf函数，
如果你考虑最后的逻辑 本周，scanf函数可以为所欲为
与x的拷贝，但它不能 永久x更改，除非我们放弃
scanf的藏宝图，可以这么说， 因此，其中的X标记的位置，
我们通过x的地址，以便 scanf函数可以去那里其实是一个改变
x的值。
所以，事实上，所有的 这个程序会
如果我做的scanf 0，在我的源代码 5米目录，使scanf函数0，
点斜线scanf函数，数 请50，感谢50。
>> 因此，它不是那么有趣， 但什么是确实发生的事情
是，只要我打电话 的scanf这里，x的值
被永久改变。
现在，这似乎不错， 好，而且，事实上，它
看起来我们并不真正需要的 在CS50库在所有了。
例如，让我们运行 这一次在这里。
让我重新打开第二个。
让我们尝试了一些，请与 而不是说50像以前一样，
我们只能说没有。
OK，这是一个有点怪异。
行。
而只是一些废话这里。
因此，它似乎并没有 处理错误的情况。
因此，我们需要最小的开始 加入一些错误检查
以确保用户具有 键入的实​​际数目的像50，
因为很明显打字的话 不被检测为有问题的，
但它可能应该是。
>> 让我们来看看这个版本现在是 我试图重新实现的GetString。
如果scanf函数有这一切 功能内置，
为什么我们已经涉足这些 培训车轮状的GetString？
好了，下面也许是我自己 简单的GetString版本
因此一个星期前，我可能会说， 给我一个字符串，并将其命名为缓冲区。
今天，我要开始只是 话说焦明星，其中，召回，
它只是代名词。
它看起来可怕，但它 同样的事情。
所以给我一个变量叫做缓冲 那将存放的字符串，
告诉用户字符串请 然后，就像以前一样，
让我们尝试借用这一课的scanf ％S这个时候再通过缓冲区。
现在，一个快速的完整性检查。
为什么我不能说 符号缓冲这段时间？
从前面的例子推断。
听众：字符明星是一个指针。
DAVID马兰：没错， 因为这个时候，炭
星已经是一个指针，一个地址， 由明星在那里的定义。
并且如果scanf的期望一个地址， 它足以只是为了打发在缓冲区中。
我不需要说了连字符缓冲区。
对于好奇的，你可以 做这样的事情。
它将有不同的意义。
这会给你一个指针 一个指针，它实际上是
一个有效的东西在C中，但对于 现在，让我们保持简单
和保持故事的连贯。
我只是要传递 缓冲，这就是正确的。
这个问题虽然是这样的。
让我继续前进，运行这个 编译后的程序。
让scanf函数1。
该死的，我的编译器 抓住我的错误。
给我一秒钟。
锵。
比方说，scanf函数，1.C。
行。
在那里，我们走了。
我需要它。
CS50 ID有不同 配置设置
保护您免受自己。
我需要禁用那些 手动运行铛这个时候。
所以字符串请。
我要继续前进，并键入 在我最喜欢的Hello World。
OK，空。
这不是我所输入的。
因此，它指示 什么是错的。
让我继续前进，键入 在很长的字符串。
感谢您的空，我不知道 如果我将能够让它崩溃。
让我们试着一点点副本 粘贴，看看这会有所帮助。
刚贴了很多本。
这绝对是一个更大的 字符串比平常。
让我们真的把它写。
第
该死的。
找不到命令。
所以这是不相关的。
那是因为我粘贴 一些不好的字，
但事实证明这是行不通的。
>> 让我们试试这个曾经多，因为 它更多的乐趣，如果我们真的崩溃了。
让我们输入这个，现在，我 要复制一个很长的字符串
现在就让如果我们看看 可能会崩溃这件事。
请注意，我省略了空间和 新的生产线和分号
和所有时髦的人物。
输入。
而现在的网络只是正在缓慢。
我按住Command-V键太长，清晰。
该死的！
找不到命令。
>> 行。
那么，问题是 尽管如此以下。
那么什么是真正会 与此声明
的第16行字符星缓冲？
所以，我是什么让 当我宣布一个指针？
所有我得到是一个四字节的值 所谓的缓冲区，但什么是它的内部
眼下？
这只是一些垃圾的价值。
因为任何时候你声明一个变量 在C，它只是一些垃圾的价值，
我们已经开始 绊倒这个现实。
现在，当我告诉scanf函数， 去这个地址
并把在不管用户类型。
如果在用户键入你好 世界上，还有，我在哪里放呢？
缓冲区是一个垃圾的价值。
>> 所以这有点像一个箭头 该指针谁知道在哪里。
也许它指向 这里在我的记忆中。
因此，当用户 类型的hello world，
该计划试图把 字符串的hello world反斜线0
该内存块。
但是高概率，但 显然不是100％的概率，
计算机将要然后崩溃 程序，因为这不是
内存我应该被允许触摸。
因此，在短期，这一计划是 有缺陷的正是这个原因。
我根本没有做什么的？
有哪些步骤我省略了，就像 我们省略了与宾基的第一个例子？
是吗？
>> 听众：内存分配？
>> DAVID马兰：内存分配。
我还没有实际分配 任何内存该字符串。
所以我们可以在几个方式解决这个问题。
第一，我们可以保持简单 而事实上，现在你
将开始看到一个模糊 之间有什么行
数组是什么，一个字符串是什么 炭明星，字符什么数组
是。
下面是第二个例子 涉及字符串和通知
所有我已经在网上做了 16是不是说，
该缓冲区将是一个char 明星，一个指向一个内存块，
我会很主动地给 我自己一个缓冲的16个字符，
而事实上，如果你熟悉 与术语缓冲，
大概从影片的世界里， 其中，一个视频缓冲，缓冲，
缓冲。
那么，什么是连接这里？
YouTube的嘛，里面 和视频播放器内
通常是一个数组 这是大于16。
它可能是大小为一的阵列 兆字节，也许10兆，
进入该数组做您的浏览器 下载一个一大堆字节，
一大堆的兆字节 视频和视频播放器，
YouTube的还是谁的，开始 从阵列读取的字节数，
任何时候你看到的 字缓冲，缓冲，
这意味着该播放器具有 得到该数组的末尾。
该网络是如此缓慢，它并没有 回填数组有更多的字节
所以你出位 以显示给用户。
>> 因此，缓冲区是一个恰当的词在这里是 它只是一个数组，一个内存块。
这将解决这个问题 因为事实证明
你可以把数组，就好像 他们的地址，即使缓冲区
仅仅是一个符号，它是一个 字符序列，缓冲液，
这对我来说是非常有用的，程序员， 你可以通过周围的名字
就好像它是一个 指针，就好像它
是一个组块的地址 内存为16个字符。
所以这是说，我可以通过 scanf函数正是那个词
所以现在，如果我做这个节目， 让scanf函数2，点斜线scanf函数2，
和类型的hello world， 回车，即时间 -
>> 嗯，什么事？
字符串请。
我做了什么错？
世界您好，缓冲区。
你好世界。
嗯，我知道它在做什么。
行。
因此，它的读了 直到第一空间。
因此，让我们骗了就一下 说我只是想输入的东西
真的长的很像，这是一个长句子 这是一个，两个，三个，四个，五个，
六，七，八，九， 10，11，12，13，14，15，16。
行。
这的确是一个长句子。
所以，这句话是 长度超过16个字符
所以当我按下回车键， 什么会发生？
那么，在的这种情况下， 故事，我宣布缓冲区
实际上是一个数组 有16个字符蓄势待发。
这样一，二，三，四，五，六， 七，八，九，十，十一，十二，十三，十四，
15，16。
所以16个字符，而现在，当我 读这样的事情是一个长期的
一句话，是什么将要发生的 那我要读这是一个漫长
S-E-N-T-E-N-C-E，句子。
>> 因此，这是故意 一件坏事，我
不断书写超越 我的数组的边界，
超出了我缓冲器的边界。
我能得到幸运和程序 将继续运行，并没有在意，
但一般来说，这 确实会崩溃我的程序，
它是在一个错误我 代码的那一刻，我一步
超越界限 该数组的，因为我
不知道这是否是 必然要崩溃
或者，如果我只是要得到幸运。
因此，这是有问题的，因为在 这种情况下，它似乎工作
让我们铤而走险这里，即使 在IDE似乎容忍了不少
of--
>> 在那里，我们走了。
最后。
所以我能看到这唯一的一个。
所以，我只是有很多好玩的打字 出了很长的实际短语
它肯定超过 16个字节，因为我
输入在这个疯狂的长期多线 短语，然后看到发生了什么。
该程序试图在打印 然后得到一个分段错误
和段错误是当 这样的事情发生
和操作系统说 不，不能触摸的记忆。
我们会杀了 该方案完全。
>> 因此，这似乎是有问题的。
我已经提高了该计划的实施 至少有一些记忆，
但是这似乎局限 该函数的GetString，这是让
一些有限的长度为16的字符串。
所以，如果你想支持更长 句子超过16个字符，
你是做什么？
那么，你可以增加 此缓冲器32的大小
或者说似乎有点短。
为什么我们不只是做 它1000，但推回。
什么是直觉的反应 只是通过避免这种问题
我的缓冲更大，像1000字符？
通过实施GetString的这种方式。
什么是好还是坏吗？
是吗？
听众：如果你绑定了很多 的空间，你不使用它，
那么你就不能重新分配空间。
DAVID马兰：没错。
这是浪费的，只要你不 实际上需要那些字节的900
可是你要求 1000共无论如何，
你只是占用更多的内存 比你需要到用户的计算机上，
毕竟，一些 你已经遇到
在生活中，当你 运行很多程序
和他们吃了大量的内存， 这实际上可能会影响性能
和用户的经验 在电脑上面。
所以这是一种懒的解决方案， 可以肯定，相反，
这不仅造成浪费，什么问题 仍然存在，即使我让我的缓冲区
1000？
是吗？
>> 听众：字符串的长度为1001。
DAVID马兰：没错。
如果字符串的长度为1001， 你有相同的问题，
和我的观点，我会 就在这时，使其2000年，
但你不知道 推进它应该多大，
然而，我必须编译我的程序 之前，让人们使用和下载
它。
因此，这也正是那种 东东的CS50库尝试
帮助我们，我们将只一瞥 一些底层实现的
这里，但这是CS50点C.这 是一直在CS50 IDE文件
所有这几个星期你一直在使用。
这是预编译的。而你 一直在使用它自动
由具有的性质 冲大号CS50标志铿锵，
但如果我向下滚动，通过所有的 这些功能，这里是GetString的，
而只给你一个 什么样的味道是怎么回事，
让我们快速浏览一下 的相对复杂性。
这不是一个超长 功能，但我们没有
必须考虑所有的硬盘约 如何去得到的字符串。
>> 因此，这里是我的缓冲区和我 显然初始化为null。
当然，这是在 同样的事情为char明星，
但我决定 实施CS50库
如果我们要 是完全动态的，
我事先不知道有多大的根本 字符串用户会希望得到的。
所以我要开始 只有一个空字符串
我要去建立尽可能多 记忆，因为我需要适合用户字符串
如果我没有 够了，我要去问
操作系统为更多的内存。
我打算把他们的串 成的存储器的更大的块
我要去释放或释放 内存不够大块
我们正要 反复地做到这一点。
>> 因此，快速浏览， 这里只是一个变量
与我要去跟踪 的我的缓冲器的容量。
我多少字节可以装？
这里有一个变量n与 而我要继续
跟踪有多少字节实际上是 缓冲器或用户已键入。
如果你还没有见过这个，你 可以指定就像一个int变量
是无符号的，它顾名思义， 意味着它的非负的，为什么会
我曾经想打扰指定 即一个int不只是一个int，
但它是一个unsigned int？
这是一个非负的int。
什么是[听不清]是什么意思？
>> 听众：它描述了一个量 内存，可以[听不清]。
>> DAVID马兰：是的。
所以，如果我说的符号，这其实是 给你一个额外的内存一位
它似乎有点傻，但如果你 拥有更多的内存一位，那
意味着你有两倍多 你可以代表值，
因为它可以是一个0或1。
因此，在默认情况下，一个int可以大致 负2十亿一路
达正2十亿。
这些都是大的范围，但 它是一种浪费还是
如果你只关心 尺寸，这只是直觉
应该是非负或 正或0，那么，
你为什么要浪费2十亿 为负数的可能值
如果你从来没有打算使用它们？
所以说无符号的，现在我的INT可以 介于0和约4十亿。
>> 因此，这里只是一个int下原因 我们不会进入刚才的
为什么它是一个int，而不是 一个char，但这里是
发生了什么事情的要点 上，并且一些你
可能使用，例如，在 即使在PSET 4龟etc功能
或之后，我们会看到它 又在问题设置五，
龟etc是不错的，因为作为名称 那种，有点arcanely表明，
这是一个函数， 获取一个字符等等，
有什么本质上的区别 什么，我们正在做的GetString的
是我们没有使用 scanf的以相同的方式。
我们沿着一步一步的只是爬行 以上的任何用户已键入中，
因为我们总是可以分配一个 字符，所以我们总能安全地
看一个字符的时间，和 神奇的开始发生在这里。
我要向下滚动到 此功能的中间
只是简单介绍一下这个功能。
就像有一个 malloc函数，有
一个realloc函数，其中的realloc 让你重新分配一块内存
并使它更大或更小。
所以长话短说，并与 一波我的手今天，
知道什么样的GetString 正在做的是它的排序
的神奇成长或 缓冲收缩作为用户
类型在他或她的字符串。
>> 因此，如果用户键入一个 短字符串，该代码
仅分配足够 存储器以适应串。
如果用户保持打字 我一次又一次做到了
又一次，好吧，如果 缓冲区的最初这个大
和程序实现，对 等一下，我的空间，
这将增加一倍 缓冲区的大小
然后加倍缓冲区的大小 而且确实增加一倍代码，
如果我们看一下在这里，它是 只是这个聪明的一班轮。
你可能没见过这种语法 之前，但如果你说明星等于，
这是同样的事情， 说产能的2倍。
因此，它只是不断翻番 所述缓冲器的容量
然后告诉realloc的给 本身更多的内存。
>> 现在，顺便说一句，有 在这里等功能
我们不会考虑任何细节 比其他的调用getInt显示，
我们使用的GetString的调用getInt。
我们检查，这不是 空，其中，召回，
是特殊的值， 意味着出事了。
我们是内存不足。
更好地检查了。
而我们返回的警戒值。
但我会推迟到的意见，以 为什么然后我们用这个表弟scanf函数的
所谓sscanf的和原来 该sscanf的，或字符串scanf函数，
让你看看就行了 用户键入，让你
本质上分析它，就是我 这里做的是我要告诉sscanf的，
分析任何用户具有 键入并确保％我，
有在它的整数，并且我们不会 进入今天究竟为什么有还
一％C在这里，但简而言之允许 我们检测是否用户已键入
在一些号码后伪造的。
因此原因，调用getInt和GetString 告诉你重试，重试，重试
是因为所有的 我们编写的代码，
它种在看用户的输入 在确保它完全数字
或者它是一个真正的浮动 点值等，
这取决于什么样的价值 您正在使用的功能。
>> 呼。
行。
这是一个拗口 但问题在这里
我们有原因 这些培训车轮
是因为在最低水平， 还有就是这么多的事情
可以去错了，我们想 抢先处理
这些东西肯定是在 最早的几个星期之类的，
但现在PSET四个PSET五 以后你会发现它更对
你还要你更强大 对解决这些类型的问题
你自己。
上的GetString或调用getInt有问题吗？
是吗？
>> 听众：你为什么会增加一倍 所述缓冲器的容量
而不是仅仅增加 它的具体数额？
>> DAVID马兰：好问题。
为什么我们的身份倍增 缓冲器的相
只是增加它 一些常数值？
这是一个设计决策。
我们刚刚决定，因为它往往 有点贵的时间，聪明的问
操作系统 内存，我们没有
要最终进入 这种情况对于大串
我们被要求 连连操作系统
一次又一次的 快速连续的内存。
因此，我们刚刚决定，多少有些 任意但我们希望合理，
如此，你知道吗，让我们 试图获得超越自我
而只是一味增加了一倍它使 我们最小化的倍量
我们必须调用malloc或 realloc的，但总的判断
在没有知道的调用 什么样的用户可能需要输入内容。
这两种方式可能是值得商榷的。
可以说不错。
>> 因此，让我们来看看一对夫妇 的内存等副作用，
事情可能出错 和工具，你可以
用它来捕获这些类型的错误。
原来大家，即使 check50没有告诉你一样多，
一直在写越野车 因为一个星期代码，
即使所有check50测试 过去了，即使你和你的TF
超级信心 你的代码按预期工作。
您的代码已被马车或 有缺陷的，所有的你，
在使用CS50库 被泄漏内存。
你一直在问的操作系统 对于存储器在大多数的节目
你写的，但你 从来没有真正赋予它回来。
你所谓的GetString 和调用getInt和GetFloat，
但GetString的，你 从来没有所谓unGetString或给
返回的字符串或类似的，但我们已经看到 是的GetString确实分配内存
由malloc或方式这 功能realloc的，这仅仅是
在精神上非常相似， 然而，我们已经
询问操作系统以 存储器和存储器连连
但从来没有给它回来。
>> 现在，顺便说一句，事实证明， 当程序退出，所有内存
自动释放。
所以它没有一个巨大的交易。
它不会打破 IDE或放慢改革的步伐，
但是当程序执行 一般内存泄漏
而他们正在运行很长一段时间。
如果你见过那些愚蠢的小 在Mac OS或沙漏沙滩球
在Windows上它是一种 减缓或思考或思维
或者只是真正开始 慢如蜗牛，
它很可能可以 内存泄漏的结果。
谁写的程序员 您正在使用的软件
要求对内存的操作系统 每隔几分钟，每隔一小时。
但是，如果你正在运行的 软件，即使是
最小化您的电脑 几个小时或几天，
你可能会问了越来越多 内存和从来没有真正使用它
所以你的代码可能是，或 程序可能泄漏内存，
如果你开始泄漏内存， 还有其他程序内存少，
而且其效果是 慢都记录下来。
>> 现在，这是迄今为止的一个 最残暴的方案
你将有机会 在CS50运行，只要
作为其输出甚至比更深奥 铿锵的或做的或任何命令
我们之前已经运行线方案，但 值得庆幸的是，镶嵌在其输出
一些超有用的技巧， 将是有益的无论是PSET 4
不然肯定P设定五位。
所以Valgrind是一个工具， 可用于看
程序中的内存泄漏。
这是相对简单的运行。
你跑Valgrind的，然后，连 虽然这是一个有点冗长，
短跑冲刺泄漏检查 等于满，然后点
斜线和你的程序的名称。
因此，Valgrind的会后运行程序 并在程序的最后
运行它退出前， 为您提供了另一个提示，
它会分析你的 虽然它已经正在运行的程序
并告诉你你泄露 任何内存和更好的是，
你触碰内存 不属于你？
它无法赶上一切，但它的 在最醒目的东西很不错。
>> 因此，这里是有经营我的一个例子 这个节目，有跑Valgrind的，
在调用程序 记忆，我要去
以突出的线条 最终我们感兴趣的。
因此，有更多的分心 我已经从幻灯片中删除。
但是，让我们只看看这是什么 程序能够告诉我们的。
它能够告诉我们的东西 像大小为4无效写。
换句话说，如果你触碰到内存， 特别是4字节的内存
你不应该有， 的valgrind可以告诉你。
无效的写大小为4。
你感动了四个字节 你不应该有。
你在哪儿做的？
这是美。
记忆点C线21就是你 搞砸了，这就是为什么它是有帮助的。
就像GDB，它可以帮助 点你在实际的错误。
>> 现在，这一个多一点 冗长的，如果不是混乱。
在1块40个字节肯定 在负的战绩1 1的丢失。
这意味着什么？
嗯，这只是意味着你问 40个字节，你从来没有给它回来。
你叫的malloc，或者您叫 GetString的和操作系统
给你40个字节，但你永远不 释放或者释放内存，
而公平地说，我们从来没有展示 你如何回馈内存。
原来有一个超 所谓的自由简单的功能。
有一个参数的东西 你想免费或给予回复，
但40个字节，显然， 这个方案
已经失去了线 内存20 C点。
>> 因此，让我们看到这个计划。
这是超级没用。
它不仅展现 此特定错误。
因此，让我们一起来看看。
下面是主要的和主要的，通知，电话 一个函数调用f和再返回。
所以不是那么有趣。
什么是f执行？
请注意，我并​​没有原型麻烦。
我想保持代码 尽可能小。
所以我把F时上部主 这很好，当然，
对于这样的短期课程。
因此，F不返回任何东西和做 不能带什么，但它确实做到这一点。
它声明，很像 在宾基例如，
一个名为x的指针是怎么回事 存储一个int的地址。
所以这是左手侧。
在英语中，什么是 右手边做什么？
有人吗？
这是什么做的我们呢？
是吗？
>> 听众：[听不清] 倍int的大小
它是10倍，[听不清]
DAVID马兰：好，让我来总结。
因此，分配足够的空间为10整数 或10，什么是一个int的大小，
它的四个字节，所以10次4 40，使右手边，我已经
高亮显示的是给我40个字节， 存储第一字节的地址
成X个。
而现在最后，而这里的地方 这个程序有错误，什么是
错线21基于该逻辑是什么？
有什么不对线21？
是吗？
听众：你不能 索引X [听不清]。
DAVID马兰：是的。
我不该指数成X个这样的。
所以语法，没关系。
什么是好的是，就像你 可以把一个数组名
就好像它是一个指针，同样 你可以把一个指针，仿佛它是
一个数组，这样我就可以在语法 例如x支架的东西，X架我，
但10是有问题的。
为什么呢？
>> 听众：因为它不是内。
>> DAVID马兰：这不是 里面的内存块。
什么是最大的价值，我应该 可以把这些方括号？
9，0到9。
因为零索引。
因此，从0到9就可以了。
支架10是不好的， 但是，每一次回忆，虽然
我似乎尽量让CS50的IDE 坠毁通过键入假值，
它并不总是合作， 而事实上，你经常
幸运只是因为 操作系统不
请注意，您可以轻微 通过一些内存块，
因为你住在技术上 您的段，但更多介绍
在一个操作系统类， 所以像这样
可以很容易被忽视。
你的程序永远不会崩溃 持续但也许曾经在一段时间。
>> 因此，让我们尝试的valgrind 这一点，和这里的
在这里，我们会变得不知所措 通过瞬间的输出。
因此，请Valgrind的内存泄漏检查 等于全点斜线内存。
这里就是为什么我保证 这将压倒。
以下是Valgrind的，下面是 一个程序员，有些年份ago-
决定这将是一个好主意 为输出的样子。
因此，让我们理解这一点。
因此，所有对左手的方式 侧面没有很好的理由
是程序的进程ID 我们只需运行，唯一标识符
对于该方案，我们只是跑。
我们删除了从 滑动，但也有
在这里一些有用的信息。
>> 让我们向上滚动到顶部。
这里就是我们的开始。
因此，它不是所有的东西输出。
下面是无效的写 对21行大小4。
那么，什么是第21行？
第21行正是 这一点，这是有道理的
我是在有效 写4个字节，因为我
试图把这个整数， 它可以是任何东西，
这恰好是 零，但是我想
把它在一个位置 这不属于我。
此外，到这里，40在一个字节 块肯定是失去了在创纪录的1。
这是因为当我调用malloc 在这里，我从来没有真正释放内存。
>> 那么，如何才能解决这个问题？
让我继续前进，是一个小更安全 并做9那儿​​，让我在这里免费的X。
这是新的功能，为今天。
如果我现在重新运行使内存点斜线， 让我们在其上运行的valgrind再次，
最大限度地发挥我的窗口，然后按Enter。
现在，这是很好的。
他们埋葬好消息 在这一切的输出。
所有堆块是免费的。
我们会回来的东西堆 是，但无泄漏是可能的。
因此，这只是另一种 工具的工具箱
使用它可以开始 现在发现这样的错误。
>> 但是让我们看看有什么 更可以去错在这里。
现在让我们来转变 其实解决问题。
顺便说一句，如果这将缓解一 混乱或紧张一点，
这是现在好笑。
是啊。
这是相当不错的。
因为指针 地址和地址
一般都是按照惯例 写的十六进制。
哈，哈，这个现在好笑。
总之，让我们现在 其实解决的一个问题。
这一直是超级， 超低水平迄今为止，
而我们实际上可以做有益 事情与这些低级别的细节。
>> 因此，我们介绍了几个星期 前的阵列的概念。
数组是不错的，因为 很难清理我们的代码
因为如果我们想写 程序有多个学生
或多个名称和房屋及 宿舍，学院和所有这一切，
我们可以存储的一切更 干净的阵列的内部。
但提出一个缺点 阵列的迄今。
即使你没有自己遭受它 在一个程序，只是本能地，
什么是坏事 有关阵列，也许？
我听到一些杂音。
听众：这很难 改变大小。
DAVID马兰：这很难 改变大小。
你不能改变大小 阵列的，实际上，本身
在C.你可以分配另一个数组， 从旧的移动一切
到新的，现在 有一些额外的空间，
但它不喜欢 如Java或Python语言
或任何数目的其他的 与语言的一些你
可能是熟悉的，你 可以只保留添加的东西
令人作呕到数组的结尾。
当你有一个数组 大小6，这是它的大小，
和这么多喜欢这个主意更早 具有一定大小的缓冲区，
你必须猜测出大门 你想要什么尺寸它是什么？
如果你猜过大， 你就是在浪费空间。
如果你猜过小， 不能存储的数据，至少
没有更多的工作。
>> 所以今天，多亏了指针，我们可以 开始拼接起来自己的自定义
数据结构，以及在 其实，这里的东西
看起来有点多 神秘的第一眼，
但是这就是我们会打电话给一个链接 列表，它的名字样的总结
它。
它的号码的列表，或者在 这种情况下，数字的列表，
但它可能是任何一个列表，但 它连接在一起的箭头的方式，
而只是采取一种猜测 有什么方法
我们要能 缝合在一起，
有点像爆米花用线， 一个链表矩形吗？
它的数字？
什么是底层语言功能？
>> 听众：一个指针。
>> DAVID马兰：一个指针。
所以，每一个箭在这里代表 指针或只是一个地址。
因此，换句话说，如果我想 来存储数字列表，
我不能只保存它，如果我想 增长和收缩的能力
我的数据结构中的阵列。
因此，我需要有一点 更复杂，
但是请注意，这 图片一种暗示
如果你拿到的小线程 一切都连接在一起，
也许并不难，以腾出空间 其中的两个矩形之间
两个这些节点，因为我们将开始 美其名曰，放入一个新的节点，
然后用一些新的线程，只 沟三个节点一起，
第一个，最后一个，并且所述一个 您刚刚插入中间。
>> 事实上链表， 一个数组不同的，是动态的。
它可以成长，它可以 收缩而你不知道
有知道或关心提前如何 你要多少数据被存储，
但事实证明，我们是一个小 小心如何实现这一点。
因此，首先让我们来看看我们如何实现 其中一个小矩形。
这很容易实现一个int。
你刚才说INT n和再 你得到的4个字节为一个int，
但我怎么得到一个int，正调用它， 再一个指针，让我们称之为下一个。
我们可以把这些 什么东西我们要
但我需要一个自定义的数据结构。
是吗？
>> 听众：＆符号[听不清]。
>> DAVID马兰：所以符号，我们将用它来 获得一个节点的地址可能。
但是，我们需要另一个 C的顺序功能
给我创造的能力 这个自定义的矩形，这种风俗
变量，如果你愿意，在内存中。
听众：一个结构。
DAVID马兰：一个结构。
从上周还记得，我们推出 结构，这种相对简单的关键词
这让我们做这样的事情。
Ç没有配备数据 结构被称为学生。
它配备了int和float和char和 这样，但它不来学生，
但我们可以创建一个学生数据类型， 学生结构，这种语法
这里。
你会一次又一次地看到这一点。
所以不要担心 记忆中的关键字，
但关键字，重要的是 只是一个事实，即我们所说的结构
然后我们把它称为学生和内 学生的是一个名字和一个房子
或者宿舍等。
>> 所以现在的今天，让我们提出这一点。
我加了几句话，但是如果我想 实现这个矩形的
既得到了一个int和 指针，你知道吗，我
要声明一个叫做节点结构。
我也是，在它的内部，会说 一个节点，这个矩形，有一个int
我们将称之为n和 它具有一个下一个指针。
这是一个有点冗长， 但如果你仔细想想，
那些出现在画面中的箭头 刚才是什么数据类型？
每个这些箭头的指向 数据结构是什么类型？
这不是指着刚本身一个int。
它指向 整个矩形的事情
那长方形的东西， 我们说，被称为一个节点。
所以，我们种得 递归定义该这样
一个节点，我们会说， 将包含一个名为-n的INT
并呼吁下及指针 数据结构的类型向其中
该指针指向显然是 将是结构节点。
>> 因此，这是烦人详细 而刚需迂腐，
我们之所以不能 只是这么一说，坦率地说
看起来很多更具可读性， 是因为回想一下，C了解
东西从上到下，从左到右。
这不是直到我们得到了分号 该关键字的节点确实存在。
因此，如果我们希望有这样的 数据的内部循环参考
结构，我们不得不这样做，在哪里 我们说结构节点在顶部，这
给我们描述了这样一个更长的路 的事情，然后在里面我们说结构节点，
然后在最后一行 我们说，没事，C，顺便说一下，
只需拨打这个整个该死 事情的一个节点，并停止
共使用关键字结构。
因此，这只是有点句法 伎俩，最终让我们创造
一些看起来完全一样。
>> 因此，如果我们现在假设我们可以 用C实现这个东西，
我们如何做实际上 开始遍历这个？
唉，其实，我们所要做的就是 遍历从左至右，只是
一种插入节点或删除节点 或搜索东西的地方，我们希望，
但要做到这一点，让我们继续前进，使 事情变得更真实，因为这
已经超低水平迄今。
会有人从字面上想成为第一个？
行。
上来吧。
你叫什么名字？
>> 大卫：大卫。
DAVID马兰：大卫。
很高兴认识你。
我也是。
好吧。
我们需要一个9号。
还不如先，也许是。
OK，号码9。
一个数字17，请。
让我回去远了一点。
22号，请和 怎么样靠后
如果我能看到任何的手 与所有的光或没有。
有人正在被自愿在那里。
难道你要来了？
你的前臂用力往上走。
OK，17。
22。
26下来。
谁都想 forcefully--上来吧。
一个实际的志愿者。
>> 所以很快，如果 你们可以安排
自己只是喜欢 屏幕上的节点。
谢谢。
你会是26。
好吧，快速推出。
所以，我是大卫，你也是？
大卫：大卫。
DAVID马兰：你是谁？
杰克：杰克。
苏：苏。
亚历克斯：亚历克斯。
拉斐尔：拉斐尔。
泰勒：泰勒。
DAVID马兰：泰勒。
优秀的。
所以，这些都是我们的志愿者 今天和前进
和转移一点的方式， 而只是继续前进，保持
牵着你的号码，你的或你的 第一个迹象，用你的左手，
继续前进，只是实施 这些箭头，只是
让你的左手是名副其实 指着无论你应该点
在，给自己一些空间，以便 我们可以直观地看到你的手臂居然
指点，你可以只点 那种在地面罚款。
>> 所以在这里我们有一个链表， 两个，三个，四个，五个节点最初
并请注意，我们有这个特殊的 指针一开始谁的
关键，因为我们必须跟踪 全长列表莫名其妙。
这些家伙，即使他们离开 以对，背靠背在内存中，
他们实际上可以在任何地方 在计算机的存储器中。
因此，这些人可能是 在舞台上的任何地方静置
这很好，只要他们 实际上指着对方，
但为了方便， 干净简洁，我们将
只是吸引他们从左到右像 这一点，但可能有大量的空白
在这些节点之间。
>> 现在，如果我想实际插入一些 新的价值，让我们继续前进，做到这一点。
我们有机会现 选择另一个节点。
说让我们与mallocing 55开始。
会有人介意的malloc？
好了，上来吧。
你叫什么名字？
彩虹：彩虹。
DAVID马兰：彩虹？
好吧。
malloc的彩虹。
上来吧。
所以，现在我们要问自己， 算法，我们可以把55。
所以，我们都知道， 显然，她很可能
所属如果我们尝试 保持这个排序
如果你们能带一个 退一步所以我们不脱落
舞台上，那将是巨大的。
所以实际上，彩虹， 从这里开始了我，
因为我们的电脑现在可以 只看到一个变量的时间。
因此，如果这是第一个节点。
请注意，他不是一个节点， 他只是一个指针，
这就是为什么他的画是 指针只大小，不
其中的一个完整的矩形。
因此，我们要检查每个 迭代比9 55少？
第
比17 55少了呢？
第
比22少？
比26少？
比34少？
所以现在，很明显 彩虹所属的结尾。
所以要明确，什么 是你的名字，泰勒？
>> 泰勒：泰勒。
DAVID马兰：所以之中泰勒 左手和彩虹的手在这里，
谁的手需要在什么指向 为了将55进这个名单？
什么是我们需要做什么？
是吗？
>> 听众：泰勒的手 需要指向左边。
>> DAVID马兰：没错。
所以插入一个节点 成列表的末尾
很简单，因为泰勒刚 必须指向，而不是在地面
或者我们叫它空， null是那种没有
指针或特 零指针，你
要指向用你的左手 手彩虹，然后彩虹，
其中，如果你的左 一方面可能是点？
向下。
这并不好，如果她的手是排序 在这里或排序的任何指点过的
哪一条路。
这将被视为 垃圾值，
但如果她指向 一些已知的价值，我们将
称之为零或零，这是确定 因为我们在这一个术语
我们知道名单现在就完成了。
>> 那么，什么是另一种 比较简单的情况下？
难道我们的malloc 5？
上来吧。
你叫什么名字？
蒂芬妮：蒂芙尼。
DAVID马兰：对不起？
蒂芬妮：蒂芙尼。
DAVID马兰：蒂芙尼。
好吧。
蒂芙尼一直malloced 用值5。
上来吧。
这一次是比较容易过，但 让我们考虑为了操作了。
这是很容易 与泰勒在末端。
号码5是当然小于9， 所以，我们有大卫，我们有蒂芙尼，
什么是你的名字吗？
>> 杰克：杰克。
>> DAVID马兰：杰克。
蒂芙尼，杰克和大卫。
谁的手，应该首先更新？
你想在这里做？
有一对夫妇可能的方式，但 另外还有一个或多个错误的方法。
>> 听众：先从最左边。
>> DAVID马兰：先从最左边。
谁是最左边的位置呢？
听众：第一。
>> DAVID马兰：OK。
因此，开始与第一，你在哪里 要更新大卫的手中呢？
听众：迈向5。
DAVID马兰：OK。
于是，大卫点五 或蒂芙尼在这里，现在呢？
>> 听众：蒂​​芙尼指向9？
DAVID马兰：完美的，除了宾基的 正中下怀头掉了下来，对不对？
因为这有什么错 这幅画从字面上？
听众：没有指向。
DAVID马兰：没有什么是 指着杰克了。
我们已经从字面上孤立9 17，我们已经从字面上
泄漏的这一切的记忆，因为 首先更新大卫的手，这是
精细因为它是正确的 现在在蒂凡尼指出，
但如果没有人有 深谋远虑地指向杰克，
那么，我们已经失去了 全部的列表。
因此，让我们撤消。
所以这是一件好事， 绊倒，但现在，让我们纠正。
我们应该怎么做第一呢？
是吗？
>> 听众：蒂​​芙尼应指向在9？
DAVID马兰：我不能 得到这个机会给你。
谁应该指向的9？
>> 听众：蒂​​芙尼。
>> DAVID马兰：好的。
因此蒂芙尼应在9第一点。
因此，蒂芙尼应 在一个相同的值
大卫，这似乎 多余的了片刻，
但是这很好，因为现在，第二 步骤中，我们可以更新大卫的手
为指向凡尼，然后如果 只是一种清洁我们的东西了
好像这是一种春天般的， 现在这是一个正确的插入。
所以，优秀的。
所以，现在我们快到了。
让我们插入一个决赛 值就像值20。
如果我们能malloc的最后一个志愿？
上来吧。
所以这一块是一个有点棘手。
但实际上，该代码我们 写作，尽管口头上，
就像有一群 如果现在的条件下，对​​不对？
我们有一个条件 若属于检查
在最后，也许是开始。
我们需要某种形式循环到 发现在中间的地方。
因此，让我们做到这一点与你叫什么名字？
>> 艾瑞克：埃里克。
>> DAVID马兰：埃里克？
埃里克。
很高兴认识你。
因此，我们有20个。
超过五少？
第
超过九少？
第
比17少？
第
行。
他属于这里 你的名字又是什么？
苏：苏。
DAVID马兰：苏。
亚历克斯：亚历克斯。
DAVID马兰：苏，亚历克斯和？
艾瑞克：埃里克。
DAVID马兰：埃里克。
谁的手先获取更新？
>> 听众：埃里克。
行。
因此，Eric的应指向哪里？
在22。
好。
现在，下一步是什么？
然后苏可指向埃里克 而现在，如果你们只是
使一些空间，这是罚款 在视觉上，现在我们所做的插入。
现在让我们考虑一个问题，但 非常感谢你对我们的志愿者。
非常出色地完成。
您可以保留这些，如果你喜欢。
我们有一个可爱的临别礼物，如果 你每次想借此压力球。
让我传递下来。
那么，什么是这个外卖？
这似乎是惊人的 只要我们现在有
引入了一个替代的 阵列事实并非如此局限
到一些固定尺寸的阵列。
他们可以动态地增长。
>> 但是，就像我们已经看到在周 过去，我们从来没有得到任何东西是免费的，
喜欢肯定有一个权衡在这里。
因此，与一个链接的上涨空间 列表，是这种活力？
这种能力成长，坦率地说， 我们可以做删除
并根据需要，我们有可能缩小。
是我们付出什么样的代价？
两倍的空间，首先。
如果你看一下图片，不再 我是存储整数列表。
我存储的列表 整数加指针。
所以我加倍的空间量。
现在，也许这不是这样的 什么大不了的4个字节，8个字节，
但它当然可以加 弥补大型数据集。
什么是另一个缺点？
是吗？
>> 听众：我们要 遍历它们一个接酮。
DAVID马兰：是的。
我们必须遍历它们一个接一个。
你知道吗，我们放弃了这个超级 括号的方便的功能，
符号，更恰当 称为随机存取，
在这里我们可以自己跳 到单个元素
但现在，如果我仍然有 我的志愿者在这里，
如果我想找到 22号，我不能只
跳转到支架上一些东西。
我要看看在列表中，多 像我们的搜索例子线，
找到数22。
因此，我们似乎已经付出了代价那里。
但是，我们还是能够 解决其他问题。
>> 其实，我来介绍一下 只是一对夫妇的视觉效果。
所以，如果你已经下降到 马瑟饭堂最近，
你还记得自己 栈这样的托盘，
我们从借来的这些 课前安嫩伯格。
所以这个栈托盘，不过， 代表实际
一个计算机科学的数据结构。
有一个数据结构 在计算机科学
被称为栈非常漂亮 适合于正是这种视觉。
因此，如果每一个托盘的是不是一个 托盘但像一些，我想
存储的数字，我 可以放一到这里，
我可以把另一个倒在这里， 并不断堆积号码
对彼此，什么是顶部 这个可能有帮助
是什么含义 这种数据结构？
哪个号码，我可以拉出来 第一个最方便？
最近期看跌的存在。
>> 所以，这就是我们所说的 计算机科学后进先出的数据结构。
后进先出。
我们将不久为什么看 现在可能是有用的，但对于，
只是考虑物业。
而且它是一种愚蠢的，如果你想 有关如何食堂做的。
他们每次清洁托盘 把最新鲜的人之上，
你可以有一个以前干净 但最终很脏乱，尘土飞扬
托盘在最底层 如果你从来没有真正
得到的，该底部 堆栈，因为你
不断把新的， 干净的人在它的上面。
同样的事情可能会发生 在一家超市了。
如果你有一个陈列柜 牛奶每次CVS
或者谁得到更多的牛奶， 你刚才推的牛奶
你已经拥有的背部和 你把新的锋线，
你将有一些非常讨厌 牛奶在数据结构的末尾，
因为它总是在底部或 等效它总是在后面。
>> 但还有另一种方式来思考 排队的数据和例如，此。
如果你是其中的一个人谁喜欢 排队的苹果专卖店外
当一个新的产品来 出来，你可能
不使用堆栈数据 结构，因为你
会疏远其他人谁是 排队购买一些新的玩具。
相反，你可能使用 什么样的数据结构的
或者是什么样的制度 在现实世界？
希望这是一条线，或更多 正确或更多的英国状，一个队列。
而事实证明队列也是 数据结构，计算机科学，
但一个队列具有一个非常 不同的属性。
这不是后进先出法。
后进先出。
上帝保佑。
这是不是FIFO。
先入先出。
这是一件好事 为公平起见
当然，当你排队 早上起来的超级早。
如果你第一次那里，你 想要得到第一个为好。
>> 所以，所有的这些数据， 结构，队列，栈
和其他人一束束，原来你 可以认为这是只是一个数组。
这是一个数组，也许 一个固定大小为4，但它会
是种不错的，如果我们可以只堆 托盘几乎可以无限高的，如果我们
有那么多的托盘或数字。
因此，也许我们要 使用链表这里，
但权衡将是 可能我们需要更多的内存，
需要多一点的时间，但我们 不限制叠层的高度，
就像奥美的陈列柜 可能限制堆栈的大小，
等等这些都是设计决策或 可供我们选择大势所趋。
因此，这些数据 结构，我们已经开始
看到新的上限可能 什么以前是超级快
当我们将离开 今天关在哪里
我们希望能得到 上周三，我们将
开始看数据 结构让我们搜索
通过日志结束时间的数据了。
并且我们看到了，记得，在零一周 和一个用二进制搜索或除法
和征服。
这是回来了，更好的是， 圣杯这个星期三
将要拿出 运行真正的数据结构
或者理论上 恒定时间，由此
不要紧多少 千万甚至上亿的东西
我们已经在该数据结构中，它会 需要我们持续的时间，也许一步
两个步骤或10个步骤， 但步骤常数
通过该数据结构进行搜索。
这的确将是制胜法宝 但更多的是在周三。
见雅则。
>> [音乐播放]