[Powered by Google Translate] [第6条] [舒适] 罗布·鲍登] [哈佛大学] 这是CS50。[CS50.TV] 我们可以前往我们的部分问题。我的空间，然后再发送URL。开始部分的问题说显然，我并不完全unsick是一个很简单的问题究竟什么是Valgrind的？ 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]