[Powered by Google Translate] [第6条] [舒适]
罗布·鲍登] [哈佛大学]
这是CS50。[CS50.TV]
>> 我们可以前往我们的部分问题。
我的空间，然后再发送URL。
开始部分的问题说
显然，我并不完全unsick是一个很简单的问题
究竟什么是Valgrind的？
Valgrind的是什么办？
任何人想要说什么Valgrind的吗？
[学生]：检查内存泄漏。
是啊，Valgrind是一个一般的内存检查。
，最终，它会告诉你，如果你有任何内存泄漏，
这主要是我们正在使用它，因为如果你想
问题集，或如果你想
大板，你需要有任何没有内存泄漏，
如果你有内存泄漏，你不能找到，
也请记住，每当你打开一个文件时，
，如果你不关闭它，这是一个内存泄漏。
>> 很多人都在寻找一些节点，他们不释放
真的，他们没有关闭字典中的第一步。
它也告诉你，如果你有任何无效的读取或写入，
这意味着，如果你尝试设置一个值
这超出堆的结束，它不会发生段故障
但Valgrind的捕获它，你不应该写在那里，
，所以你绝对不应该有任何的那些要么。
你如何使用Valgrind的吗？
>> 这是一个普遍的问题
种运行它，并期待在输出端。
输出压倒了很多次。
也很有趣，如果你有一些非常错误的事情的错误
发生在一个循环中，那么它最终会说，“太多的错误。
我要现在停止计数。“
它基本上是你要解析的文本输出。
最后，它会告诉你，你有任何内存泄漏，
有多少块，它可以是有用的，因为
如果是1块未释放，那么它通常更容易找到
超过1000块未释放。
千的块未释放可能意味着你不释放
您的链表是否恰当一些。
这是Valgrind的。
>> 现在，我们有我们的部分问题，
您不需要下载。
您可以点击我的名字和他们的空间。
现在点击我。
第1次修订将堆栈，这是我们正在做的第一个。
修订2将队列中，第三次修订版将是单向链表。
开始我们的堆栈。
因为它说，在这里，一个堆栈是一个最基本的，
计算机科学的基本数据结构。
很典型的例子是
在食堂的托盘堆。
它基本上是只要你被介绍到堆栈，
有人会说，“哦，就像一个堆栈的托盘。”
您堆叠纸盘。
然后，当你去拉一个托盘，
第一盘，但最近拉的是放在堆栈中的最后一个。
该协议栈也喜欢在这里说
我们有内存段称为堆叠。
为什么它被称为堆栈？
>> 因为像一个堆栈的数据结构，
它压入和弹出堆栈帧在堆栈上，
堆栈帧像一个特定的呼叫的功能。
就像一个堆栈，你将永远有返回
从一个函数调用之前，你可以下降到较低的堆栈帧。
您可以没有main调用foo调用酒吧和酒吧返回到主直接。
它总是遵循了正确的堆栈入栈和出栈。
就像我说的，这两个操作，push和pop。
这些都是普及条款。
你应该知道，在栈不管是什么方面的push和pop。
我们会看到队列是一种不同的。
它并没有真正有一个通用的术语，但是普遍的堆栈push和pop。
只是在栈上推。
流行是从堆栈中。
我们在这里看到的，我们有我们的typedef结构栈，
所以，我们的char *字符串。
不要害怕任何**。
这将是一个字符串数组
或字符数组的指针，其中
指向字符的指针往往是字符串。
它没有为字符串，但在这里，他们将是字符串。
>> 我们有一个字符串数组。
我们有一个大小，表示目前有多少元素在栈上，
然后我们有能力，这是可以在栈上有多少个元素。
容量应开始大于1，
但规模要开始为0。
现在，基本上有三种不同的方式，你能想到的堆栈。
嗯，有可能更多，但两种主要方式
你可以实现使用一个数组，也可以实现使用链表。
链表是一种微不足道的栈。
这是很容易使一个堆栈使用链表，
所以在这里，我们要制作堆栈使用数组，
，然后使用数组，有两种方式，你可以考虑一下。
在此之前，当我说我们有能力为堆栈，
因此，我们可以容纳一个元素在堆栈中。
>> 它可能发生的一种方式是，一旦你打10个元素，那么你就大功告成了。
你可能知道，有一个上限的10件事情在世界上
你永远也不会在栈上有10个以上的东西，
在这种情况下，你可以有你的堆栈的大小的上限。
或者你可以有你的堆栈是无界的，
但如果你正在做一个阵列，这意味着每一次你打10个元素，
那么你会增长到20个元素，当你打20个元素，
你将有增长数组的30个元素或40个元素。
你会需要增加的能力，这是我们要在这里做什么。
每一次我们达到我们的堆栈的最大大小，
当我们把别的事情上，我们将需要增加的能力。
在这里，我们推声明为布尔推（字符*海峡）。
的char * str是字符串，我们推入堆栈，
和bool只是说我们是否成功或失败。
>> 我们怎能不呢？
什么是唯一的情况下，你能想到的
在这里，我们需要返回false？
是啊。
[学生]：如果它是完整的，我们使用的是有界的实现。
是啊，所以我们定义，他说：
如果是完整的，和我们使用的是有界的实现。
然后，我们肯定会返回false。
只要我们打的10件事情在数组中，我们可以不适合11，所以我们返回false。
如果它是无界的，该怎么办？是啊。
如果出于某种原因，你不能扩展磁盘阵列。
是啊，所以内存是一种有限的资源，
最终，如果我们继续推动入堆栈的事情一遍又一遍，
我们要尝试分配一个更大的数组，以适应
产能较大，我们正在使用的malloc或任何会返回false。
好了，malloc将返回null。
>> 请记住，你曾经每一次调用malloc，你应该检查，看它是否
返回null，否则这是一个正确的扣除。
因为我们希望有一个无限的堆栈，
唯一的情况下，我们将要返回false，如果我们试图
增加的容量和malloc或任何返回false。
这时弹出不带任何参数，
并且它返回字符串，该字符串是在堆栈的顶部。
无论是最近被压入堆栈弹出返回，
它也把它从栈中删除。
发现，它返回null，如果在栈上有什么。
它始终是可能的堆栈是空的。
在Java中，如果你使用，或其他语言，
试图从一个空栈中弹出，可能会导致异常或什么的。
>> 但在C，空是种了很多的情况下，我们如何处理这些问题。
返回null是我们要如何表示的堆栈是空的。
我们提供的代码，将测试协议栈的功能，
实现push和pop。
这会不会是大量的代码。
我会实际上，在我们这样做之前，提示，提示
如果你还没有看到它时，malloc是不是唯一的功能
为您的堆分配内存。
有一个家庭的alloc函数。
首先是malloc的，你已经习惯了。
然后释放calloc，做同样的事情的malloc，
但它会为零，一切为你。
如果你曾经想将一切设置为null后mallocing的东西
你应该只是用来释放calloc，而不是写在首位
一个循环零出整个内存块。
>> 如malloc和realloc是有很多的特殊情况下，
但基本上什么realloc的是
它需要一个已经分配的指针，该指针。
realloc是你想要的功能，关注这里。
它需要一个已经从malloc返回的指针。
比方说，你从malloc要求10个字节的指针。
后来你意识到你需要20个字节，
所以你调用realloc的，20个字节的指针，
和realloc会自动复制过来的一切都​​是为了你。
如果你只是叫的malloc再次，像我有块10个字节。
现在我需要一个20字节的块，
因此，如果我malloc的20个字节，那么我必须手动复制10个字节的第一件事
进入第二件事情，然后自由的第一件事。
realloc的会为你处理。
>> 请注意，签名会是void *，
这是只返回一个指针，指向的内存块，
void *的指针。
作为一个通用的指针，你可以认为是void *。
一般情况下，你永远不处理用void *，
但malloc（）并返回一个void *，然后它只是用来像
这实际上是将是一个char *。
，以前的void * malloc返回的
现在要通过向realloc，然后大小
是你要分配的字节数，因此新的能力。
我给你一两分钟，这样做在我们的空间。
开始第1次修订。
我会停下来后，希望能有足够的时间执行推入，
然后，我给你做流行音乐的另一种突破。
但它确实是没有那么多的代码在所有。
大多数的代码可能扩大的东西，扩充产能。
好了，没有压力，完全做到，
但只要你觉得你是在正确的道路，这是很好的。
>> 没有人有任何的代码，他们与我拉起来感觉很舒服吗？
是的，我会的，但没有人有任何的代码，我可以拉起来吗？
好了，你可以启动，保存它，不管它是什么？
我总是忘了这一步。
好吧，看在推，
你要解释你的代码吗？
[学生]：首先，我增加的大小。
我想，也许我应该有，反正，我增加的大小，
我看看它的容量不足。
如果是容量不足，我添加到数组中，我们已经有了。
而且，如果不是的话，我的能力乘以2，
我和重新分配的字符串数组的东西，现在更大的容量大小。
然后如果失败了，我告诉用户并返回false，
如果它的罚款，然后我把字符串在新的位置。
>> [罗布B.还要注意，我们这里用一个漂亮的位运算符
乘以2。
请记住，左移总是要乘以2。
除以2，只要你记住，它意味着右移
除以2除以2的整数。
它可能会截断在这里或那里。
但左移1总是要被乘以2，
除非你的整数溢出边界，那么就不会是。
A面注释。
我喜欢做，这是不会改变的编码任何方式，
但我喜欢做这样的事情。
它实际上是要使其稍长。
这也许是不完美的情况下显示，
但我喜欢分割成块，
好吧，如果这一点，如果发生了，那么我要做的事情，
，然后函数完成的。
我不需要，然后一路向下滚动我的眼睛的功能
看看会发生什么后，其他。
如果这如果发生的话，我就回来。
它也有额外的好处，一切都超出了这个漂亮的
现在左移一次。
我不再需要，如果你曾经冗长得可笑的近线，
然后这4个字节可以提供帮助，也更左的东西，
少不堪重负，你觉得如果想好了，我一定要记住
我目前在一个while循环内的其他内的循环。
任何地方，你可以马上做到这一点回报，我倒是很喜欢。
这是完全可选的，并且预期不会以任何方式。
>> [学生]：应该有一个大小 - 在故障条件？
故障条件在这里，我们向realloc失败，所以，是的。
请注意，在故障条件下，据推测，
除非我们免费的东西，我们总是要失败
无论多少次，我们试推的东西。
如果我们继续推动我们不断递增，规模，
即使我们不把任何东西压入堆栈。
通常，我们不会增加的大小，直到
之后，我们已经成功地把它放在堆栈中。
我们将做到这一点，说，无论是在这里和这里。
然后，不要说s.size≤能力，它的容量小于，
只是因为我们搬到这里的一切。
>> 请记住，唯一的地方，我们可能会返回false
在这里，这里的realloc返回null，
如果你碰巧要记住标准错误，
也许你会认为这是一个情况下，你要打印一个标准的错误，
fprintf STDERR，而不是直接打印到标准输出。
再次，这是不是一种期望，但如果它是一个错误，
输入输出，那么你可能希望将它打印到标准错误，而不是标准输出。
>> 任何人还有什么要注意的吗？是。
[学生]：你去[听不清]？
[罗布B.]是的，或实际binariness，只是它是什么呢？
[学生]：所以你将它乘以2？
[罗布B.]是啊，基本上是这样。
在二进制的土地，我们总是有一组数字。
移此由1左侧基本上将它插入这里在右侧。
返回到这一点，只是记住，一切以二进制
是2的幂，所以这表示2到0，
这2到1，这2到2。
右侧插入一个0到现在，我们只是改变一切。
曾经被认为是2 0现在是2到1，2 2。
我们插入右侧，
一定是0，
这是有道理的。
如果你曾经一个数字乘以2，这不是要结束了奇数，
所以2〜0的地方应为0，
这是什么我一半警告说，如果你之前是发生转移
以外的一个整数中的比特数，
那么这个1是要最终会关闭。
这是唯一的担心，如果你碰巧要处理的非常大的能力。
但在这一点，那么你正在处理的数组数十亿美元的东西，
可能不适合到内存中了。
>> 现在，我们可以得到流行，这是更容易。
你可以不喜欢，如果你碰巧弹出一大堆，
现在你的一半容量。
你可以realloc的缩小的内存量，
但你不必担心，所以只有realloc的情况下，将是
日益增长的记忆，永远不会萎缩的内存，
这是会弹出超级简单的。
现在要像栈，队列，
但顺序是相反的，你拿东西出来。
队列中的典型例子是一条线，
所以我想，如果你是英语，我会说
一个典型的例子是一个队列的队列。
因此，像一条线，如果你是行的第一人，
您期望成为第一个出列的人。
如果你是行的最后一个人，你会是最后一个人服务。
我们称之为FIFO模式，而堆栈是后进先出法的模式。
这些话是非常普遍的。
>> 就像栈和，不像数组，队列通常不允许在中间的元素。
在这里，我们有一个堆栈，push和pop。
在这里，我们碰巧召他们入队和出队。
我也听到他们叫shift和unshift。
我已经听到有人说push和pop也适用于队列。
我听说插入，删除，
所以push和pop，如果你正在谈论有关栈，入栈和出栈。
如果你说的队列，你可以选择你要使用的话
插入和删除，是应该叫什么没有达成共识。
但在这里，我们有入队和出队。
现在，该结构看起来几乎相同的堆栈结构。
但是，我们必须跟踪头。
我想在这里说的，但为什么我们需要的头吗？
的原型基本上是相同的push和pop。
你可以把它看成push和pop。
唯一的区别是弹出的返回，而不是最后的，它的第一个返回。
2，1，3，4，或东西。
这里的开始。
我们的队列已经完全满了，所以有四个元素在里面。
结束我们的队列当前为2，
现在我们去插入别的东西。
>> 当我们要插入其他的东西，我们所做的堆栈版本
是我们扩大了我们的内存块。
这个是什么问题呢？
[学生]：你提出的2。
我说的队列结束前，
这没有任何意义，我们开始为1，
然后，我们要出列1，然后出队，出队4
然后出列，然后出列，这一个。
我们现在不能使用realloc，
最起码，你有，使用realloc以不同的方式。
但你可能不应该只是使用realloc。
你将必须手动复制你的记忆。
>> 有两个函数复制内存。
有存储器复制和memmove。
我目前正在读，看看哪一个你将要使用的手册页。
好了，存储器复制，不同的是
存储器复制和memmove，而正确处理的情况下
您在何处复制到一个区域发生重叠的区域
你复制。
存储器复制不处理。 Memmove。
你能想到的问题，
比方说，我要复制这个家伙，
这四个这家伙过来。
最后，该数组应该像
后的副本是2，1，2，1，3，4，然后在最后的一些东西。
但是，这是依赖于复制的顺序，
因为如果我们不考虑该地区的事实，我们复制到
我们复制重叠，
然后，我们可能不喜欢开始，在这里，我们想要去的地方复制2，
然后将指针向前发展。
>> 现在，我们要在这里和这里，现在我们要复制
这家伙在这个家伙的指针向前移动。
我们将最终得到的是2，1，2，1，2，1
而不是在适当的2，1，2，1，3，4，因为
2，推翻了原来的3，4。
Memmove处理是正确的。
在这种情况下，基本上只是使用memmove
因为它处理是正确的。
它一般不执行任何恶化。
我们的想法是开始，而不是从一开始就复制这种方式
就像我们刚刚在这里做的，从去年底开始和复制，
在这种情况下，你可以永远不会有问题。
有没有性能上的丢失。
请务必使用memmove。再也不用担心存储器复制。
这就是你要去的地方有单独memmove
包裹的部分，您的队列。
不用担心，如果没有完全做到。
这是更加困难比栈，推，和流行。
>> 任何人有任何的代码，我们可以使用？
即使完全不完整？
[学生]：是的，这是完全不完整的，虽然。
完全不完全是罚款，只要我们能为您节省修订？
我忘了，每一次。
好了，忽略了会发生什么，当我们需要调整的东西。
完全忽略调整大小。
解释一下这段代码。
我首先检查如果尺寸小于首先复印
，然后在那之后，我将我头+大小，
我要确保它环绕的数组的容量，
我在该位置插入新的字符串。
然后我增加的大小，并返回true。
>> 罗布B.]这是肯定的情况下，你会希望使用的模之一。
任何一种情况下，你已经环绕着，如果你认为周围包裹，
马上想到的应该是MOD。
作为一个快速优化/较短的一行代码，
您发现该行紧随
只是大小+ +，所以你合并入这行，大小+ +。
在这里，我们的情况下，
我们没有足够的内存，
所以我们提高我们的能力，2。
我想你可以在这里有同样的问题，但现在我们可以忽略它，
其中，如果你没有提高你的能力，
然后，你会想，以减少你的能力，2。
另一个短值得注意的是，就像你可以做+ =，
你也可以做<< =。
前平等，几乎什么都可以去，+ =，| =，＆=，<< =。
新的char *是我们的新的内存块。
哦，在这里。
>> 人怎么看我们的新的内存块的类型吗？
[学生]：应该是char **。
回想我们的结构在这里，
字符串是什么，我们重新分配。
我们正在一个全新的动态存储在队列中的元素。
我们要分配给你的字符串就是我们mallocing的，现在，
等新的将是一个char **。
这将是一个字符串数组。
那么，是什么的情况下，我们要返回false？
[学生]：我们应该做的char *？
罗布B.]是的，良好的通话。
[学生]：那是什么？
[罗布B.我们想要做的char *的大小，因为我们不再是
这实际上是一个很大的问题，因为大小（字符）将是1。
SIZEOF的char * 4，
所以很多时候，你正在处理int类型，
你会得到它，因为尺寸大小的int * int和
在32位的系统将是同样的事情。
但在这里，大小（字符）和sizeof（CHAR *）现在将是同样的事情。
>> 在我们返回false是什么情况？
[学生]是空的。
是的，如果新为空，则返回FALSE，
我要在这里摔倒
[学生] [听不清]
罗布B.]是啊，这是好的。
你既可以做2次，容量或容量移1，然后将其设置或任何。
我们会做到这一点，因为我们有它。
容量>> = 1。
你永远不会有担心失去的地方
因为你左移1，所以1的地方必然是一个0，
所以右移1，你仍然会好起来的。
[学生]：你需要做的是在返回之前？
罗布B.是的，这使得完全没有意义。
>> 现在假设我们要最终结束返回true。
方式我们要做这些memmoves的，
我们必须要小心我们如何做。
没有任何人有任何建议，我们如何做？
下面是我们的开始。
不可避免的是，我们要再次从头开始
和从那里复制的东西，1，3，4，2。
你是怎么做到的呢？
首先，我必须看的手册页memmove。
memmove，而参数的顺序是非常重要的。
我们希望我们的目标首先，源第二，规模第三。
有很多扭转源和目标的功能。
目标，源往往有些是一致的。
移动，它返回的是什么？
它返回一个指针到目的地，不管是什么原因，你可能想。
我能想象读它，但我们要进入我们的目的地。
>> 什么是我们的目标又如何呢？
[学生]。
罗布B.是的，和我们复制的呢？
我们要复印的第一件事情是这样的1，3，4。
这是-1，3，4。
这地址是什么？
这1的地址是什么？
[学生] [听不清]
[罗布B.]头+的第一个元素的地址。
我们怎样才能在数组的第一个元素？
[学生]：队列中。
罗布B.]是的，q.strings。
请记住，在这里，我们的头是1。
织补它。我只是觉得这是奇迹般地
在这里，我们的头是1。我要改变我的颜色。
这里是字符串。
这一点，我们可以把它写在这里我们做了
用头+ q.strings。
很多人也写它与q.strings的头。
这是不是真的任何效率不高。
你可能会认为它为您提领，然后得到的地址，
但编译器将它翻译成我们以前的事，反正，q.strings +头。
无论哪种方式，你要考虑它。
>> 我们要复制多少字节？
[学生]：能力 - 头。
能力 - 头。
然后你就可以一直写的一个例子
搞清楚，如果这是正确的。
[学生]：它需要除以2，然后。
是啊，所以我想我们可以使用大小。
我们仍然有大小，
使用大小，我们有大小等于4。
我们的规模是4。我们的头是1。
我们要复制这3个元素。
这就是合理性检查，尺寸 - 是正确的3头。
回来这里，就像我们之前说的，
如果我们使用的能力，那么我们就必须除以2
因为我们已经长大了我们的能力，所以不是，我们会使用大小。
副本的那部分。
现在，我们需要复制的其他部分，剩下的部分开始。
>> 这是怎么回事memmove到什么位置？
[学生]：加上大小 - 头。
是的，所以我们已经复制的大小 - 头字节，
，所以在这里我们要复制剩余的字节是新的
然后大小负好，我们的字节数已经复制英寸
然后我们复制的呢？
[学生]：Q.strings [0]。
罗布B.]是的，q.strings。
我们可以做和的q.strings [0]。
这是比这明显不太常见。
如果它只是为0，然后你会倾向于看q.strings。
这就是我们正在复制。
多少个字节我们还剩下复制？>> [学生]：10。
右。
[学生]：我们要乘5 - 10倍的大小的字节或什么的？
是啊，所以这是究竟是什么，我们复制吗？
[学生] [听不清]
我们在复制的东西的类型是什么呢？
[学生] [听不清]
是啊，这样的char *，我们复制，我们不知道那些来自。
好了，他们指着，像琴弦，我们最终将其推到队列中
或到队列中进行排队。
如果这些都来自我们不知道。
我们只需要跟踪的char *自己。
我们不希望复制的大小 - 头字节。
我们要复制的大小 - 头的char *，
所以，我们要乘这个大小（char *）的。
在这里，头*大小（CHAR *）。
>> [学生]：怎么样[听不见的？
这项权利在这里吗？
[学生]，下面的大小 - 头。
罗布B.这项权利在这里吗？
指针的算术运算。
指针运算是如何去上班
它会自动将的类型，我们正在处理的大小。
就像在这里，新+（大小 - 头）
是完全等同于和新的大小 - 头]
直到我们预计正常工作，
因为如果我们要处理的一个int数组，然后我们不要索引的INT-
如果它的大小为5，和你想的第4个元素，然后我们索引
int数组[4]。
你不 - [4] *大小的int。
来处理它，这种情况下自动
简直是等同的，所以括号的语法
只是要转换为只要你编译。
这件事情你需要小心
当你加入的大小 - 头
你是不是一个字节。
您要添加一个char *，它可以是一个字节或什么的。
>> 其他问题吗？
好了，出队会更容易。
我给你一分钟的时间来实现。
哦，我想这也是同样的情况
排队的情况下，如果我们入队空，
也许我们要处理它，也许我们不这样做。
我们不会再在这里，但我们的堆栈情况下相同。
如果我们加入队列为空，我们可能要忽略它。
任何人有一些代码，我可以拉起来吗？
[学生]：我只是出队。
第2版​​是没事。
你想说明什么？
[学生]：首先，你要确定有什么东西在队列中
而且其大小是由1。
你需要做的，然后返回头
然后将头1。
好了，所以我们必须考虑的一个角落的情况。是啊。
[学生]：如果你的头是在最后一个元素，
然后，你不想头指向阵列外。
>> 是啊，所以只要头打我们的阵列，
我们出列的时候，我们的头被改装为0。
不幸的是，我们不能做到这一点的一个步骤。
我想我可能会解决它是
这是怎么回事，我们正在返回，是一个char *
无论你的变量名要。
然后，我们希望我们的能力，国防部头
然后返回沤。
很多人在这里，他们可能会做
这种情况下，您看人家做头
大于产能，做头 - 能力。
而这仅仅是解决mod是什么。
头模能力是干净多了
一个周围环绕的比大于容量头 - 能力，如果头。
>> 有问题吗？
好了，我们剩下的最后一件事是我们的链表。
你可能会使用一些链表行为，如果你没有
在哈希表，链表，如果你做了一个哈希表。
我强烈建议做一个哈希表。
您可能已经做了特里，
但尝试都比较困难。
从理论上讲，他们是渐近更好。
但就在大板，
并尝试从来没有做的更好，，他们占用更多的内存。
一切有关尝试最终被更多的工作差。
这是大卫·马兰的解决方案始终是
是他的帖子他的特里的解决方案，让我们来看看他目前是。
他是干什么的“，DAVID J？
他是第18，所以这不是差得要命，
，这将是一个最好的尝试，你能想到的
或一个最好的尝试的线索。
这难道不是他原来的解决方案吗？
我觉得，像特里解决方案更倾向于在此范围内的内存使用。
>> 你下到最高层，和RAM的使用是在个位数。
向下朝下方，然后你开始看到试图
你在哪里得到绝对使用大量的RAM，
尝试都比较困难。
不完全是值得的，但教育经验，如果你没有一个。
最后一点是我们的链接列表，
，这三个东西，栈，队列，链表，
你做的任何未来的事情在计算机科学
假设你熟悉这些东西。
他们只不过是一切的根本。
>> 链接列表，在这里我们有一个单链表，将是我们实现。
什么是单链表，双向链表的意思，而不是？是。
[学生]：只点到下一个指针，而不是指针，
像一个前它和它的一前一后。
是啊，所以在图片格式上，我只是做吗？
我有两件事。我有图片，图片。
在图片格式上，我们的单链表，
不可避免地，我们有我们的列表的头指针种，
然后在我们的名单，我们只是有三分球，
也许这点为空。
这将是一个单向链表的典型示意图。
一个双向链表，你可以倒着走。
如果我给你列表中的任何一个节点，那么你就一定能获得
列表中的任何其他节点，如果它是一个双向链表。
但是，如果我让你在列表中的第三个节点，这是一个单向链表，
没有办法，你对你将要得到的第一个和第二个节点。
有利弊，一个明显的例子
是你采取了更多的大小，和你有这些东西现在都指向跟踪。
但是，我们只关心单链表的。
>> 有几件事情，我们将不得不实行。
你的typedef结构节点，INT I：结构节点下;节点。
该typedef应烧入你的心。
测验1应该是这样的一个typedef一个链表节点，
你应该能够立即潦草下来
甚至没有考虑它。
我猜一对夫妇的问题，为什么我们需要结构的吗？
我们为什么不能说的节点*？
[学生] [听不清]
是啊。
定义了一个节点的唯一的事情
是typedef本身。
但是这一点，当我们种的解析通过这个结构节点定义，
我们还没有完成我们的typedef，因为typedef还没有完成，
节点不存在。
但结构节点呢，这个节点在这里，
这也可以被称为什么都重要。
这可以被称为n。
它可以被称为链表的节点。
它可以被称为什么。
但是，这需要调用同样的事情，这个结构节点结构节点。
你也可以在这里，
等还回答了第二点的问题
这就是为什么有很多的时候，你看到的结构和类型定义的结构体，
你会看到匿名结构的话，你会看到typedef结构，
实施结构，字典，或其他。
>> 为什么我们在这里需要说的节点？
为什么不能是一个匿名的结构？
这几乎是同样的回答。
[学生]：您需要在struct来引用它。
是啊，在结构，你需要参考的结构本身。
如果你不给结构体的名称，如果它是一个匿名的结构，你可以不引用它。
最后，但并非最不重要的，这些都应该是有些简单的，
他们应该帮助你实现，如果你写下来
你做错了什么，如果这些事情是没有意义的。
最后但并非最不重要的一点是，为什么会发生这种结构节点*？
为什么它不能只是结构的节点吗？
[学生]：到下一个结构体的指针。
这是不可避免的，我们想要的东西。
为什么它永远不会是结构节点下？
为什么有是结构节点下的吗？是啊。
[学生]：这是一个无限循环。
是啊。
[学生]：这将是中的一​​个。
是啊，就认为我们将如何做大小或东西。
一个结构的大小基本上是+或 - 在这里或那里一些模式。
它基本上是要的事情，在结构尺寸的总和。
不改变任何东西，在这里，大小是一件容易的事。
结构节点的大小将是大小的i +尺寸的未来。
的i的大小将是4。下次的大小将是4。
结构节点的大小将是8。
如果我们不*，思维的sizeof
然后大小（ⅰ）将是4。
结构节点的大小未来将是结构节点下的大小为I +大小
+我+尺寸的结构节点下的大小。
这将是一个无限递归的节点。
这就是为什么这是怎么会事必须的。
>> 再次，一定记住，
或至少​​理解不够，你可以可以
通过它看起来应该像什么原因。
我们将要实现的事情。
如果列表长度
你可以欺骗，并保持周围
全球的长度或东西，但我们不打算这样做。
我们要算列表的长度。
我们已经包含，所以这基本上是一样的搜索，
所以我们有一个链表的整数，如果这个整数链表中。
前面加上要插入在列表的开头。
附加将要插入的结束。
Insert_sorted要插入排序列表中的位置。
Insert_sorted种假设你从来没有使用前置或附加在恶劣的方式。
>> 当你实施Insert_sorted insert_sorted -
比方说，我们有我们的链表。
这是它目前看起来，2，4，5。
我想插入3个，所以只要已排序的列表本身，
可以很容易地发现其中3属于。
我从2开始。
好了，3是大于2的，所以我想继续下去。
哦，是太大了，所以我知道要在2至4，
我有固定的指针和所有的东西。
但是，如果我们没有严格使用insert_sorted，
喜欢让我们只想说，我在前面加上6，
我的链接列表将成为这个。
现在，它没有任何意义，所以的insert_sorted，你可以假设
是对列表进行排序，即使操作
这可能会导致不进行排序，就是这样。
找到一个有用的插件，所以这些都是主要的事情，你将不得不实行。
>> 现在，花一分钟的长度和包含，
这些应该是比较快的。
接近关门时间，所以任何人有任何长度或包含？
他们将是几乎相同的。
[学生]：长度。
让我们来看看，修订工作。
好吧。
你想说明什么？
[学生]：我只是创建一个的指针节点，并把它初始化为第一，这是我们的全局变量，
然后我检查，看它是否为null，所以我没有得到段故障，并返回0，如果是这样的话。
否则，我遍历，跟踪的内的整数
多少次，我已经访问列表中的下一个元素
和在相同的增量操作也访问该实际元素，
然后我不断地检查，看它是否为NULL，
，如果它是空的，那么它中止，只是返回我访问过的元素。
>> [罗布B.]有没有人有任何意见什么？
这看起来精细的正确性明智的。
[学生]：我不认为你需要的节点== NULL。
是啊，所以如果节点== null返回0。
但如果节点== NULL，那么这个，哦，有一个正确的问题。
这只是你回到我的，但它现在不在范围之内。
你只需要我，所以我= 0。
但是，如果节点是空的，那么我仍然为0，
我们将返回0，所以这种情况是相同的。
另一种常见的是要保持的声明
节点内的for循环。
你可能会说，哦，不。
让我们保持它，因为这。
我可能会放INT I = 0在这里，
然后节点节点第一次在这里。
这可能是如何摆脱现在的这种。
这可能是我会怎么写。
你也可以看它是这样的。
在这里循环结构，这
应该是几乎一样自然地为int i = 0
i是小于数组的长度一+ +。
如果这就是你如何遍历一个数组，你这是怎么遍历一个链表。
>> 在某些时候，这应该是第二自然。
考虑到这一点，这将是几乎同样的事情。
你将要遍历一个链表。
如果节点的价值是什么，我不知道。
节点i。
如果该节点的值=返回true，这就是它。
请注意，只有这样，我们永远返回false
的是，如果我们遍历整个链表，永不返回true，
所以，这是什么做的。
作为一个方面说明，我们可能不会得到要前插或追加。
>> 快速最后一个音符。
如果你看到了static关键字，所以让我们说静态诠释计数= 0，
然后我们做数+ +中，你可以基本上认为它作为一个全局变量，
即使我只是说，这不是我们要如何落实长度。
我这样做是在这里，再算上+ +。
任何方式，我们就可以进入到我们的链接列表，我们正在增加我们的计算节点。
这点是static关键字意味着什么。
如果我刚做了诠释计数= 0，这将是一个普通的老全局变量。
静态诠释计数装置是什么，它​​是一个全局变量，这个文件。
这是不可能的其他一些文件，
想到的pset 5，如果你已经开始。
你有都speller.c，和你有dictionary.c，
和，如果你只是全球申报的事情，那么在speller.c
可以访问在dictionary.c，反之亦然。
全局变量。c文件的任何访问，
但静态变量只能在文件本身，
所以里面的法术检查或内部dictionary.c的，
这是我的数组的大小如何，我会宣布我的变量
我在字典中的单词数的大小。
因为我不希望声明一个全局变量，任何人都可以访问，
我真的只关心我自己的目的。
>> 好的事情也整个名称冲突的东西。
如果有其他文件试图使用一个全局变量数，事情会变得非常，非常错误的，
所以这很好地保持安全起见，只有你可以访问它，
并没有其他人就可以了，如果有人声明了一个全局变量数，
然后，它不会干扰您的静态变量数。
这是静态的。它是一个文件的全局变量。
>> 问题什么呢？
所有的设置。再见。
[CS50.TV]