[Powered by Google Translate] [第6周] [戴维·J·马兰] [哈佛大学] 这是CS50。[CS50.TV] 这是CS50，这是第6周开始，这样一对夫妇的新工具现在可供您利用，其中第一个被称为CS50风格。奇怪的是，如果你是像我这样的教学研究员，你可能已经看到了一个程序，其风格看起来有点像这样。也许你开始削减一些角落深夜，否则你会稍后处理，然后一个TF或CA在办公时间内。然后，我们很难读。，此代码在语法上是正确的，它会编译，它实际上运行。但它绝对不是一个风格的5。但是现在，如果我们去到这个目录并请注意，我有conditions2.c 我运行这个新的命令，style50，在这个文件conditions2.c，输入，注意，它告诉我，它已经程式化。 Gedit的注意到，该文件已经在磁盘上更改，如果我点击重新加载，你所有的问题，现在实现自动化。 [掌声] 这是我们做这个周末的事情之一。要认识到，它是不完善的，因为有一些代码，，那根本不会是完美的样式，但现在意识到这是一个工具，你可以利用如果仅仅是为了收拾一些更errantly放在花括号等。但更引人注目的是CS50检查。 CS50检查，你其实可以执行相同的正确性测试对自己的代码，教学研究员能。这是一个命令行实用程序，现在在家电只要你做按update50 pset的4种规格，并使用它基本上是这样的。运行该命令check50。然后，你将在一个命令行参数，或更普遍地被称为一个开关或标志。一般情况下，有连字符的事情，被称为一个开关一个命令行程序，-c指定你要运行的检查。要运行的测试，你唯一标识此字符串， 2012/pset4/resize。换句话说，这只是一个任意的，但唯一的字符串我们用来唯一识别的pset 4的正确性测试。然后指定一个空间分隔的列表中的文件要上传 CS50检查分析。举例来说，如果我进入我的解决方案为resize.c这里让我打开了一个更大的终端窗口和我继续运行让我们check50-C 2012/pset4/resize说的，然后我继续前进，指定的文件名， resize.c，然后按Enter键，它会压缩，它上传时，它会检查，我只是一大堆的测试失败。在左上角的一个红说，resize.c和BMP存在。这是测试。这是我们的问题。它的不开心，因为得到的答案是假的。白色它下面的文本说，预计bmp.h存在的，而这仅仅是我的错。我忘了把它上传，所以我需要这两个文件上传， resize.c和bmp.h. 但现在发现所有其他测试是黄色的，因为他们还没有遇到，等的笑脸是垂直的，因为他既不快乐也不悲伤，但我们必须纠正这个问题，在红色之前的其他检查运行。让我来解决这个问题。让我放大并重新运行此，这一次bmp.h 在命令行上，输入，现在如果一切顺利的话，要检查，然后返回一个结果，屏住呼吸，所有的绿色，这意味着我做的真的很好的pset 4。你可以看到和推断的描述性文字在这里它到底是什么，我们测试。我们测试了第一个不存在的文件吗？然后，我们测试的不resize.c编译吗？然后，我们测试它不能调整一个1x1像素的BMP，调整大小的因素，当n为1。现在，如果你不知道n是什么，你会当你潜入的pset 4，但是，仅仅是进行仔细的检查，以确保你不调整大小图像，如果在所有的大小调整系数为1。如果相反，它会调整到2x2正确的1x1像素的1x1像素的BMP 当n是2，则同样地，矿形成相应。总之，这是，一，采取交叉手指的等式就在你提交你的pset。你会确切地知道你的TF很快就会知道当你去提交一些这些问题集，也是教学的动机是真的把这样的机会在你面前，当你知道一个先验有代码中的错误，并没有被通过的测试，你可以把前面的更有效的时间来解决这些问题而不是失分，从你的TF，得到的反馈，然后走了，“啊，”我应该已经猜到了。现在，至少有一个工具，以帮助您找到。这不是要指出其中的错误，但它会告诉你什么是它的症状。现在，实现不一定详尽的测试。只是因为你得到满屏幕的绿色笑脸并不意味着你的代码是完美的，但它确实意味着已通过一定的测试规范所规定的。有时候，我们将不会公布检查。比如，侦探小说，一个方面的pset 4，是一种令人失望的，如果我们给你的答案，因为它是什么，而且也透露了一些方法来谁的人是在这红色的噪音。该规范将在未来的指定pset的5起什么检查为你存在。你会发现底部有这个白色的URL。就目前而言，这仅仅是诊断输出。如果您访问该URL时，你会得到一大堆疯狂的，神秘的消息，欢迎您翻阅，但它主要是为工作人员这样我们就可以诊断和调试check50本身的错误。没有废话不多说，让我们继续前进，到我们离开的地方。 CS50库我们想当然的几个星期，但上周，我们开始脱皮层之一。我们开始搁置赞成什么，而不是字符串吗？ [学生]字符。 CHAR *，这一直是一个char *，但现在我们不必假装它是一个真正的数据类型的字符串。相反，它一直为char *各种各样的代名词，字符串是一个字符序列，那么，为什么它的意义表示为char *的字符串？什么是一个char *的背景下，这个概念的一个字符串表示？是的。>> [学生]：第一个字符。好，第一个字符，但不完全的第一个字符。 [学生]。好，第一个字符的地址。这是需要在计算机的内存中表示字符串只是其第一个字节的唯一地址。你甚至不知道它有多长因为你的身影，动态吗？ [学生]：字符串长度。您可以调用字符串的长度，优秀的，但如何字符串的长度？它有什么作用呢？是啊。 [学生]：保持下去，直到你得到的空字符。是的，没错，它只是遍历一个for循环，while循环，表示无论从*到结束，并结束 \ 0，所谓的空字符，NUL，不要混淆为null，这是一个指针，会在谈话中再次。我们剥开一层调用getInt，然后在GetString的，我们接过来一看，和调用这些功能，还是真的， GetString时，使用一定的函数实际解析，是读或分析用户的输入。那是什么新功能？ scanf或sscanf的。它实际上是在几个不同的口味。的scanf，sscanf的，有fscanf。现在，虽然，让我们专注于最容易说明的，让我去进取，不断开拓的家电这样的文件，scanf1.c。这是一个超级简单的程序，但是，做一些事情，我们从来没有做过没有帮助的CS50库。这从用户得到一个int。它是如何工作的呢？那么，在那里的第16行中，注意到，我们声明一个int称为x，在这一点上的故事， x的值是什么？ [听不见的学生反应] 大卫M.]右，谁知道，一些垃圾的价值可能在17，我们只是告诉用户给我一个号码，请步和第18步是它得到有趣的。 scanf函数似乎借用一个想法从printf的，因为它在引号中使用这些格式代码。％d是一个十进制数。但是，为什么我通过在＆X是x？前者是正确的。是啊。 [听不见的学生反应] 没错，如果这项计划的目标，如的函数调用getInt本身，是一个int的用户，我可以通过功能所有的变量，但我想，如果我不通过引用传递或地址或指针，所有的目的的代名词，那么这个函数有没有能力改变这个变量的内容。这将通过在副本一样的马车版本的Swap 我们已经谈到了几次。但是，这样＆X，我从字面上传递什么？ [学生]的地址。>> x的地址。这就像scanf函数调用的函数绘制地图，并在这里说，这些都是在计算机的内存块的方向，你可以去存储一些整数中。为了sscanf的，现在做的，什么样的运营商，什么样的语法是要使用即使我们不能看到它，因为别人写了这个功能吗？换句话说 - 那是什么？ [学生]：X读。还有的将是一些阅读，但只有考虑到这里的x。，如果scanf函数是通过x的地址，语法，什么样的运营商是必然存在的地方内部，使scanf函数scanf函数的实现其实可以写一个2号线到该地址吗？是啊，所以*。回想一下，*是我们的反引用运算符，这实际上意味着去那里。一旦你已经交给一个地址，是这里的情况， scanf的可能是，如果我们环顾四周，它的源代码 * x或相当于真正去到该地址，并把一定的价值。现在，scanf是如何从键盘输入的，我们会挥动我们手中的今天。只是假设操作系统允许sscanf的谈用户的键盘，但在这一点上，现在在第19行中，当我们简单地打印出x，它似乎是 scanf函数把一个int x中。这正是scanf是如何工作的，记得上周这也正是GetString和调用getInt和其他家庭的功能最终的作品，尽管略有差异，如sscanf的，这意味着一个字符串，而不是扫描的键盘。但是，让我们来看看在这一点差异。在scanf2，其实我搞砸了。什么是错的，我会隐藏的评论来解释尽可能多的这个程序有什么不妥，第2版？技术可能。它看起来不错。它很好地缩进，但好了，怎么样让我们修剪下来，以更短的问题吗？第16行。第16行做精确，但技术的英语是什么？开始有点尴尬。是的，迈克尔。 [学生]：它指向一个字符串的第一个字母。好了，很近的。让我有一点点进行调整。指向一个字符串的第一个字母，你声明一个变量叫做缓冲都将指向一个字符串的首地址，或者更确切地说，将指向更具体的一个字符。请注意，它实际上没有指向任何地方，因为没有任何赋值操作符。有没有等号，所以我们正在做的是所谓的缓冲区分配变量。它正好是32位的，因为它是一个指针，和缓冲区的内容想必最终将包含一个字符的地址，但现在，缓冲包含什么？只是一些假的，谁知道，一些垃圾的价值，因为我们并没有显式初始化，所以，我们不应该做任何假设。好了，现在17行，什么17行办呢？也许这将温暖起来。它打印一个字符串，对不对？它打印出字符串请。第18行是一种熟悉的，现在在我们刚刚看到的方差但具有不同的格式代码，所以在第18行中，我们在这里告诉scanf函数是一个内存块的地址。我希望你能响在一个字符串中，暗示的％s的，但问题是，我们并没有在这里做了几件事情。的问题之一是什么呢？ [学生]：它试图取消引用一个空指针。好，空，否则未知的指针。你交给scanf函数的地址，但你刚才说刚才该地址是一些垃圾的价值，因为我们没有实际分配任何东西，所以你告诉scanf函数有效地去把一个字符串，但我们不知道这里还所以我们并没有实际分配的内存的缓冲区。此外，你甚至也没有告诉scanf函数吗？假设这是一个内存块，它是不是垃圾的价值，但你还是没有告诉scanf的一些重要的东西。 [学生]：它实际上是符号。与符号，所以在这种情况下，它没关系。因为缓冲区已经被声明为一个指针 *的语法，我们并不需要使用符号，因为它是一个地址，但我想我听到了这里。 [学生]：它有多大？好，我们没有告诉scanf函数有多大，这个缓冲区，这意味着即使缓冲区的指针，我们说scanf函数，把一个字符串在这里，但在这里，可能是2个字节，也可能是10个字节，它可能是一个兆字节。 scanf函数不知道，因为这是一个内存块据推测，它不是一个字符串还。这只是一个字符串，一旦你写个字符，\ 0到该内存块。现在，它只是一些的内存块。 scanf函数不知道什么时候停止写入到该地址。如果你还记得我随意在键盘上键入一些例子，在过去的尝试缓冲区溢出，正是和我们聊上周五。如果攻击者以某种方式注入到你的程序中一个更大的字或句子或短语，那么你，希望你可以溢出一个内存块，它可以有不良后果，如在整个程序本身。我们需要以某种方式解决这个问题。让我缩小，进入第3版的这个方案。这是一个稍微好一点。在这个版本中，发现其中的差别。在第16行，我再次声明一个变量叫做缓冲，但究竟是什么呢？这是一个数组的16个字符。这是一件好事，因为这意味着我现在可以告诉scanf函数这里是一个实际的内存块。现在为指针的数组，你几乎可以认为，即使他们不是实际上是等效的。他们会在不同的上下文中有不同的表现。但它肯定是缓冲区被引用的情况下， 16个连续的字符，因为这是一个数组是和现在已经有好几个星期。在这里，我说的，scanf是这里的一大块的内存。这一次，它实际上是一个内存块，但为什么这个程序仍然可利用的呢？什么仍然是错的？我说给我16个字节，但是， [学生]：如果输入超过16？没错，如果用户键入17个字符或1700个字符是什么？事实上，让我们看看如果我们不能现在绊倒这个错误。这是更好，但并不完美。让，我继续运行编译这个程序，使scanf3的。让我跑scanf3，字符串，请：您好，我们似乎会好起来的。让我尝试稍长，你好。好吧，让我们不打招呼，你今天怎么，Enter键。在这里获得一种幸运，让我们说，你好，你怎么样。该死的。好了，我们是幸运的。让我们来看看，如果我们能够解决这个问题。不，它不会让我抄。让我们再试一次。所有权利。我们会看到，我可以假装多久焦点，而这样做。该死的。这是相当合适的，其实。我们走吧。点而成。，尴尬的，但它也是，它也是引起极大的混乱的来源之一编写程序时有错误的，因为他们表现自己有时在一段时间内只有一次。现实的情况是，即使你的代码被彻底打破，它可能只被彻底打破了曾经在一段时间内因为有时候，基本上会发生什么是操作系统分配一点点更多的内存比你实际需要的不管是什么原因，所以没有其他人使用的内存块的16个字符，所以，如果你去17，18，19，不论如何，这不是什么大不了的。现在，计算机，即使在这一点上，不崩溃其他的东西，可能最终使用的字节数17或18或19，在这一点，你把你的数据有，但过长，要覆盖潜在的一些其他功能。它不一定是要保持不变，但不一定会导致段故障。但是，在这种情况下，我终于提供了足够的字符，我基本上是超出了我的内存段，咣当，操作系统的说：“对不起，这是没有好，分割故障。” 让我们来看看，如果现在仍然在我的目录请注意，我这里有这个文件，核心。请注意，这是再次呼吁一个核心转储。它本质上是一个文件，其中包含你的程序的内存中的内容在点，它坠毁，只是为了尝试一个简单的例子：在这里让我去和运行gdb上scanf3的，然后指定了第三个参数，称为核心，并注意在这里，如果我列出的代码，像往常一样，我们就可以用gdb开始步行通过这个节目，我可以运行它，并尽快为我打的步骤，在gdb的命令只要我打了潜在的车线后键入一个巨大的字符串，我将能够识别在这里。更多关于这一点，虽然，在部分核心转储等，让您可以闲逛内将核心转储看到在哪一行的计划失败。然后在指针和地址的任何问题？因为今天开始，我们要开始考虑是理所当然的，这些东西存在我们知道究竟是什么。是。 [学生]：为什么你没有把符号的部分这个问题问得好。为什么我没有把一个符号的字符数组，因为我以前的我们的例子吗？简短的回答是数组是有点特别。你几乎可以认为一个缓冲区实际上是一个地址，它只是发生的情况下，方括号表示法是一个方便的，这样我们就可以进入支架，支架1，托架2，而无需使用*符号。这是一个有点善意的谎言，因为数组和指针，其实是有点不同，但他们往往但并不总是可以互换使用。总之，当一个函数需要一个指针，指向一个内存块，您可以通过malloc返回的地址，，我们将看到的malloc再过不了多久，你可以通过它的名称的数组。你不必做符号的数组，因为他们已经基本上和地址。这是一个例外。让他们特别的方括号。你可以把一个符号旁边的缓冲区？不能在这种情况下。这是行不通的，因为这个角落的情况下，数组是不太实际的地址。但是，我们也许会回来，不久与其他的例子。让我们尝试在这里解决的一个问题。我们有一个数据结构，我们已经使用了一段时间被称为数组。典型的例子，这就是我们刚。但数组有一定的积极以及不利的缺点。数组是不错的，为什么呢？什么是一件事，你喜欢你喜欢的阵列有关数组的范围内吗？方便他们什么？引人注目的是什么？为什么我们向他们介绍摆在首位？是啊。 [学生]：他们可以存储大量的数据，你不必使用整个的事情。您可以使用一节。好，一个阵列，可以存储大量的数据，你不一定必须使用它的所有，所以你可以overallocate，这可能是方便的，如果你事先不知道有多少的期望。 GetString的是一个完美的例子。 GetString时，我们写的，不知道多少个字符，所以事实上，我们可以分配的连续内存块还是不错的。数组也解决一个问题，我们现在看到几个星期前您的代码开始下放一些非常糟糕的设计。回想一下，我创建了一个叫大卫的学生结构，然后这实际上是一种替代方法，虽然有一个名为name的变量与另一个变量，我认为，房子，和另一个变量称为ID，因为在这个故事中，我想介绍一些其他像Rob到程序中，所以后来我决定等待一分钟，我要重命名这些变量。让我们把我的NAME1，ID1，house1。让我们把抢夺的名称2，house2，ID2。但是，然后等待一分钟，汤米？然后，我们有三个变量。我们引进了别人，四组变量。世界开始变得混乱非常迅速，所以我们引入了结构，什么是引人注目的一个结构？什么是一个C结构让你这样做吗？这是今天真的很尴尬。什么？>> [听不见的学生反应] 是啊，特别是上，typedef可以让你创建一个新的数据类型，结构，struct关键字，让你封装概念上相关的数据块此后他们类似的学生。这是很好的，因为现在我们可以模拟更排序的概念相一致的概念，一个学生在一个变量而不是任意具有一个为一个字符串，一个用于一个ID，等等。数组是不错的，因为他们让我们开始清理我们的代码。但现在是一个缺点的数组？你能不能做？是啊。 [学生]：你要知道它有多大。你要知道它有多大，所以它是一种痛苦。那些具有编程经验知道，在很多语言中，如Java，你可以问一个内存块，特别是一个数组，究竟有多大，其长，财产，可以这么说，这是真的很方便。在C语言中，你甚至可以不调用strlen一般的数组由于strlen，因为这个词所暗示的，是唯一的字符串，你可以计算出字符串的长度，因为这个人的惯例有一个\ 0，而是一个数组，更一般地，仅仅是一块内存。如果它是一个整型数组，不会有一些特殊的字符在结束等着你。你要记住一个数组的长度。数组的另一个缺点抬头的GetString本身。数组的另一个缺点什么？主席先生，只有你和我。 [听不见的学生反应] >>这是什么？它的声明在堆栈中。好了，在堆栈上声明。你为什么不这样呢？ [学生]：因为它得到重用。它得到重用。好吧，如果你使用一个数组分配内存，例如，你不能返回它，因为它是在栈上。好吧，这是一个缺点。怎么样的数组？一旦你分配它，你种旋，如果你需要更多的空间比阵列。然后，我们介绍，召回时，malloc，这给了我们动态分配内存的能力。但是，如果我们尝试了完全不同的世界？如果我们想解决这些问题，一对夫妇的我们，而不是我的笔已经睡着了，在这里，如果我们不是想实质上是创建了世界上不再像吗？这是一个数组，当然，这种恶化，一旦我们打到最后的数组，我现在不再有另一个整数或其它字符的空间。如果我们什么样的先发制人说好了，为什么我们不能放松这个要求是，所有这些内存块是连续的背靠背，为什么不，当我需要一个int或一个字符，只要给我空间，其中之一吗？当我需要，给我另一个空间，当我需要，给我一个空间。优势是，如果别人在这里，占用内存没什么大不了的。我会承担这额外的内存块，那么这个人。现在，唯一的缺点是，几乎感觉就像我有一大堆不同的变量。这感觉就像是5个不同的变量潜在的。但是，如果我们偷的想法字符串据此，我们以某种方式连接这些东西放在一起从理论上讲，和什么如果我这样做吗？这是我很差绘制的箭头。但是，假如这些内存块指出的，这家伙，谁没有兄弟姐妹在他的右边，有没有这样的箭头。其实，这是什么所谓的链接列表。这是一个新的数据结构，使我们能够分配的内存块，然后又一次，另一个，然后再在任何时候，我们要在一个程序，我们还记得，他们都以某种方式相关的从字面上链接在一起，我们这样做，形象地在这里有一个箭头。但是，在代码中，会是什么机制，通过它，你可以以某种方式连接，几乎一样从头开始，另一块块？我们可以用一个指针，对不对？因为真正的箭头，从左上角的正方形，这家伙在这里，这其中，包含在这个广场不只是一些整数，不只是一些字符，但如果我真的分配一点点额外的空间，所以，现在，我的每一个内存块，即使这要花费我，其中之一的内存块，现在看起来多了几分矩形被用于一个数字，如数字1，如果这个家伙，然后存储数字2，这其他的内存块，用于箭头，或者更具体而言，一个指针。并想我存储在这里，我使用它来指向那个家伙，现在这家伙，让我们假设我只需要三个这样的内存块。我会画一条线，表明空。有没有额外的字符。事实上，这是我们如何去执行而这就是所谓的一个链表。链表是一种新的数据结构，它是一个敲门砖票友数据结构着手解决问题沿线Facebook的类型的问题，谷歌型的问题你有巨大的数据集，它不再削减连续存储一切，并使用类似线性搜索甚至一些像二进制搜索。你想更好的运行时间。事实上，人们的圣杯，我们将讨论在本周晚些时候或明年是一种算法，其运行时间是恒定的。换句话说，它总是以相同的时间量无论有多大的投入，这确实是引人注目的，甚至更多的东西比数。这是什么在屏幕上呢？每个矩形正是我刚才画的手。但事情的方式在左边是一个特殊的变量。这将是一个单一的指针，因为有一个问题一个链表，因为这些东西被称为，是，你必须挂到链表的一端。就像一个字符串，你必须知道的第一个字符的地址。同样的处理链表。你必须知道的第一个内存块的地址因为从那里，你可以达到每一个。不利的一面。我们付出什么样的价格，这种多功能的具有动态相当大的数据结构，如果我们需要更多的内存，做工精细，只是分配一个块，并画一个指针旧到新的尾的列表吗？是啊。 [学生]：这需要约两倍的空间。它需要两倍的空间，所以这绝对是一个缺点，我们已经看到了这时间，空间和灵活性之间的权衡前现在，我们需要的不是这些数值分别为32位。我们真正需要的数字64，32和32，用于将指针。但是，嘿，我有2 GB的RAM。添加另外32位在这里和这里似乎并不认为大不了的。但对于大型数据集，它肯定加起来到字面上的两倍多。的另一个缺点什么，或什么功能，我们放弃了，如果我们是代表一个链表，而不是一个数组列表的东西，？ [学生]：您可以向后遍历。您可以向后遍历，所以你种拧如果你走从左至右使用for循环或while循环然后你会意识到，“哦，我想回到开始的名单。” 你不能因为这些指针只由左到右的箭头表示。现在，你可以记住列表的开始与另一个变量，但要记住，这是一个复杂的。一个数组，不管你走多远，你总是可以做减，减，减，减回到来处。另一个缺点是什么？是啊。 [听不见的学生问题] ，所以你可以你实际上只是提出了一个双向链表数据结构，而事实上，你会增加这些矩形的另一个指针 “其他方向，上攻现在你就可以遍历来回，的缺点是，现在你正在使用三次尽可能多的内存，我们使用并且还加入复杂的代码，你写得到它的权利。但这些都可能是非常合理的折衷，，如果反转更重要的是。是啊。 [学生]：你也不能有一个2D链接列表。好，你可以不真的有一个二维链表。你可以。这不是那么容易达到的阵列。与数组一样，你做开放式的支架，封闭的支架，打开支架，封闭支架，，你会得到一些的二维结构。你可以实现一个2维链表如果你这样做附加你提出的第三个指针，这些东西，如果你认为你的另一个列表3D风格从屏幕到我们所有人来说，这仅仅是某种形式的另一个产业链。我们能做到这一点，但它不是简单，只要键入开括号，方括号。是啊。 [听不见的学生问题] 好，所以这是一个真正的踢球者。这些已经消瘦了，我们喜欢哦，二进制搜索算法，您可以搜索阵列上的数字板或电话簿，以便更迅速，如果您使用分而治之二进制搜索算法，，但二进制搜索需要两个假设。其中，该数据被排序。现在，我们可以推测这个排序，所以也许这不是一个问题，但还承担二进制搜索你有随机存取的号码列表，阵列允许您进行随机存取，随机存取，我的意思是，如果你是一个数组，你需要多少时间支架0？一人操作，你只需要使用[0]和你说得对。没有考虑到位置10多少步？一步，你只是去[10]你的存在。相比之下，你怎么在一个链表到第10的整数？因为你只记得，你必须从头开始一个链表的开始，就像一个字符串被记住它的第一个字符的地址，并发现第10整数或10字符串中的字符，你必须搜索整个该死的东西。同样，我们还没有解决所有的问题。我们正在推出新的，但它实际上取决于你想要什么设计。在实施方面，我们可以借用一个想法，学生结构。它的语法很相似，但现在的想法是多了几分抽象比房子，名称和ID。不过，我建议，我们可以有一个数据结构的C 被称为节点，在幻灯片上显示的最后一个字，里面一个节点，一个节点是在计算机科学只是一个普通的容器。它通常画成一个圆或正方形或长方形，因为我们已经做了。这个数据结构中，我们有一个int，N，所以这是我想存储的号码。但是，这是什么第二线，结构节点下的吗？为什么这是正确的，这个东西发挥什么样的作用，即使这是一个有点神秘的第一眼？是啊。 [听不见的学生反应] 没错，*排序的战利品，这是某种类型的指针。这个指针的名字是任意下，但我们可以把它叫做我们想要的东西，但什么该指针指向？ [学生]：另一个节点。>>没错，它指向到另外一个这样的节点。现在，这是排序的好奇心，C. 回想一下，C被读取由编译器从上到下，从左到右，这意味着，如果 - 这是一个有点不同，从我们所做的与学生。当我们定义一个学生，我们实际上没有一个字。刚才说的typedef。然后，我们必须int的ID，字符串名称，字符串的房子，然后学生在底部的结构。此声明是一个有点不同，因为，再次，C编译器是一个有点哑。这只是要读从上到下，因此，如果到达2号线下一个被声明，它认为，哦，这里有一个变量称为下。这是一个指针，指向一个结构节点。编译器就是要实现一个结构节点是什么？我从来没有听说过这件事之前，因为这个词节点，否则可能不会出现直到底部，所以有这样的冗余。你说结构节点，然后你就可以缩短以后于typedef在这里，这是因为我们所引用的结构本身的内部结构。这是一个疑难杂症有。一些有趣的问题出现。我们已经有了一个数字列表。我们怎么插入？我们如何搜索呢？我们如何删除它？尤其是现在，我们必须管理所有这些指针。你以为指针有点令人费解当你有一个，他们只是想读取一个int。现在我们就来操纵整个列表的价值。为什么我们不把我们的5分钟的休息时间，在这里，然后我们会带一些人在舞台上这样做。 C是更多的乐趣时，它的行动了。哪些人会从字面上是第一吗？好了，就行了。你是第一个。谁愿意为9？好吧，9。 9怎么样？ 17？这里一个小团体。 22和26，前排。然后怎么样的人在那里被指出。你有34个。好吧，34就行了。首先是在那里。好了，你们四个。我们谁也说9？谁是我们的9？谁真正想要的是9？好吧，来吧，是9。在这里，我们走了。 34，我们将满足你在那里。第一部分是使自己看起来像他一样。 26，22，17，良好的。如果你能站到一边，因为我们要malloc你在某一时刻。好，好。好，很好，所以让我们在这里问几个问题。实际上，什么是你的名字吗？“梅艳芳。梅艳芳，没关系，在这里。梅艳芳样的帮助我们解决了一个相当简单的问题，第一，你是怎么做的，而不是一个值是否在列表中呢？现在，请注意，第一，这里所代表的卢卡斯，是有点不同的，所以他的一张纸是故意侧身因为它不是相当高，不占用多少位，即使在技术上他有相同尺寸的纸张，只是旋转。但他是一个有点不同，他只有32位的指针，所有这些家伙都是64位，其中一半是多少，其中一半是指针。但指针没有描述的，所以如果你们能有点笨拙用左手指向旁边的人给你。你是34号。你叫什么名字？阿里。阿里，所以实际上，保存的文件在你的右手，左手向下的直线。表示空的左侧。现在我们的人的照片是非常一致的。这实际上是指针的工作方式。如果你能一点点堆砌方式，所以我不是在用自己的方式。梅艳芳在这里，找到我的22号，但假设一个约束的不是人拿着纸片，但是这是一个列表，你只需要卢卡斯开始因为他是名符其实的第一个指针。假设你自己是一个指针，所以你也有能力指向的东西。你为什么不首先指向的正是卢卡斯指着吗？好，让我在这里制定了这一点。为了讨论的方便，让我拉了一个空白页。你怎么拼写你的名字吗？“梅艳芳。好了，梅艳芳。比方说节点*阿尼塔·卢卡斯。好了，我们不应该给你打电话卢卡斯。我们应该先打电话给你。这是为什么，其实与现实在这里？其中，第一个已经存在。大概是首先被分配在这里的某个地方。节点*首先，它被分配的名单不知何故。我不知道这是怎么发生的。这发生在上课前开始。这个链表人类已创建。在这一点上的故事，这是所有在Facebook上显然后在这一点上的故事，梅艳芳已被初始化为等于第一，这并不意味着在卢卡斯，梅艳芳点。相反，她指着他指出在因为相同的地址里面的Lucas的32位 - 1，2，3 - 现在也Anita的32位 - 1，2，3的内侧。找到22。你将如何去这样做呢？那是什么？>>指向任何。点什么，所以，尽管它作为最好的，你可以在这里行动。好，好，现在你指着你叫什么名字22？ “拉蒙，拉蒙。，所以拉蒙同比增长22。现在，您已经做了检查。拉蒙== 22，如果是的话，例如，我们可以返回true。让我，而这些人站在这里，有点笨拙让我做的东西像Bool快速找到。我要继续前进，并说（节点列表，诠释n）。跟你说，我马上就回来。我只需要编写一些代码。现在我要继续前进，并做到这一点，节点梅艳芳=列表。我要继续前进，并指出，虽然（袁咏仪！= NULL）。这里的比喻还是有点捉襟见肘，但（袁咏仪！= NULL），我想这样做吗？我需要一些方法的引用梅艳芳指向的整数。在过去，当我们有结构，其中节点是我们使用点符号，我们会这样说 anita.n，但这里的问题是，Anita是不是结构本身。她是什么人？她是一个指针，所以真的，如果我们想用这点表示法这是怎么回事看故意有点神秘我们必须做这样的事情去任何Anita的左手指向然后得到该领域称为n。 Anita是一个指针，但*梅艳芳是什么？你觉得什么，当你去Anita是指什么？一个结构，一个节点，一个节点，召回，有一个字段称为n 因为它，记得，这2场，下和n，我们刚才也看到了这里。为了真正模仿的代码，我们可以这样做，并说，如果（（*梅艳芳）N = N），我在寻找的n。请注意，该功能是通过我关心的数量。然后我就可以继续做类似返回true。否则，如果不是这样的情况下，我想这样做吗？我该如何翻译的代码有什么梅艳芳这样做直观地走在列表中呢？我应该怎么做模拟梅艳芳的左侧，采取这样的步骤，一步到左边？ [听不见的学生回应] >>那是什么？ [听不见的学生反应] 好，不是一个坏主意，但在过去，当我们已经做到了这一点，我们已经做了梅艳芳+ + 因为这会增加数字1〜梅艳芳，这通常指向旁边的人，像拉蒙旁边的人，他或他旁边的人的路线。但是这还不是相当不错的，在这里，因为这是什么东西在内存中的样子吗？不是这样的。我们必须禁用。它看起来像这样在内存中，即使我已经开了1个和2个和3靠近彼此，如果我们真的模拟这个可以你的家伙，而仍指向相同的人，你们中的一些采取随机退后一步，一些你一个随机的一步吗？这个烂摊子仍是一个链表，但这些人可能是在内存中的任何地方，阿尼塔+ +没有去上班，为什么呢？什么位置梅艳芳+ +？谁知道。这是一些其他的价值，只是恰巧被插在所有的这些节点的机会，因为我们不使用一个数组。我们分配每个节点。好吧，如果你们可以清理自己回来了。最后，我提议，而不是梅艳芳+ +，而不是做梅艳芳得到好，为什么我们不走任何Anita是指向，然后做下？换句话说，我们去拉蒙，他的22号，然后，接下来就是虽然梅艳芳模仿他的左手指针。但她不会走的更远，因为我们比拉蒙发现有22。但是，这将是这个想法。现在，这是一个神烂摊子。说实话，没有人会永远记住这个语法，幸运的是，它实际上是有点故意的，哦，你没有实际看到我写的是什么。如果可以的话，这将是更具吸引力的。瞧！在幕后，我解决这样的问题。阿妮塔，采取这一步骤的左侧，首先，我们去的地址，Anita是指向和在那里她会发现不只有N，我们只是检查比较的缘故，但你也将寻找下一个 - 在这种情况下，拉曼左手指着在列表中的下一个节点。但是，这是我前面提到的神的烂摊子，但事实证明，输出C让我们简化了这一点。而不是写（梅艳芳），我们可以改为只写梅艳芳 - > N，和它的功能完全一样的东西，但它是一个更直观的，这是一个很大的图片更符合我们一直画这一切的时候使用箭头。最后，在课程结束后，我们需要做的吗？还有一个剩余的代码行。回报是什么？假的，因为如果我们通过整个循环 Anita是，事实上，空，这意味着她千里迢迢到列表末尾她指着你叫什么名字呢？阿里。>>阿里的左手，这是空的。现在，Anita是空的，我意识到你只是站在这里，笨拙的地狱因为我要去独白，但我们会涉及到你在短短的时刻。 Anita是空的故事，在这一点上，因此while循环结束，我们必须返回false，因为如果她得到了Ari的空指针的方式来再有就是没有，她试图在列表中的号码。我们可以清洁过，但是这是一个很好的实现，那么遍历函数，一个链接列表的功能。它仍然是线性搜索，但它不是简单+ +指针 + +变量i，因为现在我们不能猜这些节点，其中每个都在存储器中。我们有字面上跟随面包屑的踪迹，或者更具体地说，指针，从一个节点到另一个。现在，让我们尝试另一种。安妮塔，你要回来吗？我们为什么不继续分配从观众的另外一个人吗？ malloc的，你叫什么名字？“丽贝卡。丽贝卡。 Rebecca一直malloced，从观众，她现在存储55号。现在在手的目标是梅艳芳插入丽贝卡到链表，在合适的地方。到这儿来了一会儿。我已经做了这样的事情。我已经做了节点*。你叫什么名字呢？瑞贝卡，瑞贝卡。>>还好。丽贝卡得到的malloc（如sizeof（节点））。就像我们在过去的分配学生和诸如此类的事情，比如，我们需要的大小的节点，所以现在瑞贝卡是指什么？丽贝卡她的内部具有两个字段，其中之一是55。让我们做什么，丽贝卡 - > = 55。但后来丽贝卡 - >未来应像现在，她的手是怎么样的，谁知道？它指向一些垃圾的价值，那么，为什么不为好措施我们至少要做到这一点，使左手在她的身边。现在，梅艳芳，把它从这里开始。你有瑞贝卡已被分配。继续前进，发现我们应该把丽贝卡。好，非常好。好了，好了，现在我们需要你提供一点方向，所以你已经达到了阿里。他的左手是空的，但丽贝卡显然属于正确的，让我们怎么改变这个链表为了插入到适当的位置丽贝卡？如果你可以从字面上将根据需要周围人的左手，我们会解决这个问题的方式。好，好，同时，丽贝卡的左手在她的身边。这是太容易了。让我们尝试分配的 - 我们做得差不多了，20。好了，就行了。 20已分配的，所以让我去，说在这里再次我们刚刚做了的节点*萨德。我们拥有的malloc（如sizeof（节点））。然后，我们做完全相同的语法，因为我们做了前20，我会尽下= NULL，现在是Anita的插入到链表中，如果你能玩，相同的作用。执行。好，好。现在仔细想想，然后再开始移动周围的左手。您的今天得到了最尴尬的角色。谁的手应先移走？好了，等等，我听到一些不。如果有些人会礼貌地帮助解决一个尴尬的境地。谁的左手也许应该首先更新吗？是啊。 [学生]萨阿德。好了，萨阿德的，为什么有关系吗？ [听不见的学生反应] 好，因为如果我们把你叫什么名字？>>马歇尔。马歇尔，如果我们先动了手，空，现在，我们已经从字面上孤立在此列表中的四个人因为他是唯一指向拉蒙和每个人的左，所以更新该指针是坏的。我们的撤消。好，现在继续前进，将适当的左手指向拉蒙。这感觉有点多余。现在有两个人指着拉蒙，但因为现在我们怎么更新列表？另一方面，移动吗？好极了，现在我们失去了任何记忆了吗？没有那么好，让我们来看看，如果我们不能打破这一次。 Mallocing最后一次，5号。在后面，一路下来吧。这是非常令人兴奋的。 [掌声] 你叫什么名字？“罗恩。罗恩，好吧，你是malloced 5号。我们刚刚执行的代码几乎相同，这些只用一个不同的名字。优秀。现在，梅艳芳，运气好的话插入到列表中的5号。好，？好极了，所以这是真正的三个案件总数的三分之一。我们第一次有人结束时，丽贝卡。然后，我们在中间的人。现在我们在开始时，并且在该示例中，已经有人我们现在有更新卢卡斯的第一次因为现在在列表中的第一个元素指向一个新的节点，谁，依次指向在节点号9。这是一个巨大的尴尬的示范，我敢肯定，所以这些家伙又大又圆的掌声，如果你能。很好地完成。这就是全部。作为一个小的内存，您可以保留您的纸片。事实证明，这样做的代码是不是很简单，只是动动手左右和指向指针的不同的东西。但意识到，当它来的时候实现的东西，如一个链表或它的一个变种，如果你专注于真正这些基本因素，一口大小的问题，我必须弄清楚，是这只手，这手，否则，什么是一个相当复杂的程序可以，其实这样相当简单的积木。让我们把事情仍然在一个更复杂的方向。我们现在有链表的概念。我们也有感谢的建议有一个双向链表，这看起来几乎是一样的，但现在我们有两个内部指针的结构，而不是一个，我们也许可以调用这些指针的前面和后面的或左或右，但我们做的，其实，需要其中的两个。代码将是更复杂一点。梅艳芳将不得不做更多的工作在这里的舞台上。但是，我们可以肯定实现该种结构。但是，在运行时间方面，将运行时间梅艳芳一个链表中找到一个数n？还是大O n的，所以它是没有更好的线性搜索。不过，我们不能做二进制搜索。为什么会这样呢？你不能跳来跳去。尽管我们很明显的看到在舞台上的所有人类，和Anita目测它说，“这里是中间的列表中。” 她不知道，如果她的计算机程序因为她唯一锁存到的情况下开始卢卡斯，谁是第一个指针。她一定要遵循这些链接，数她，直到她找到大致的中间，即使如此，她不知道，当她到达中间除非她去所有的方式结束弄清楚有多少，然后回溯，而且也将是很难的，除非你有某种形式的双向链表。解决一些问题，但介绍他人。约一个完全不同的数据结构呢？这是一个照片的托盘Mather中楼，在这种情况下，我们有一个数据结构，我们也种已经在谈论。我们谈论中的堆栈内存的情况下，而这样的刻意命名，是因为堆栈在内存方面实际上是一个数据结构，有越来越多的东西，在它的上面分层。但有趣的事情堆栈，因为在现实的情况下，是，它是一种特殊的数据结构。它是一个数据结构，从而使第一元件是的最后一个元素。如果你是第一个托盘入堆栈，你要不幸的是，最后一个托盘从堆栈中，而这并不一定是件好事。相反，你可以考虑一下周围的其他方法，最后是第一个出来的。现在，你的任何方案，浮现在脑海中有一个堆栈数据结构，具有该属性中的最后一个，第一个出来的，实际上是吸引力？这是一件好事吗？这是一件坏事吗？这绝对是一件坏事，如果托盘不尽相同他们都是不同的颜色或诸如此类的东西，你想要的颜色是所有的方式在底部。当然，你不能，不花大力气。你必须从顶部开始，一路下滑。同样，如果你是其中之一，这些风扇男孩试图让iPhone和排队等待了一夜的人在这样的地方吗？那岂不是很好，如果苹果专卖店一个堆栈的数据结构吗？耶？不仅如此吗？这只是良好的人显示在最后一分钟，然后被拔了队列。而事实上，这样的倾向的事实，我说队列实际上是一致的，我们所说的这种数据结构，在现实中的顺序很重要，你想中的第一个，是第一个如果仅仅是为了人类的公平。一般情况下，我们将调用一个队列的数据结构。事实证明，除了链表，我们就可以开始使用这些相同的基本思路开始创建新的，不同类型的解决方案的问题。例如，在堆栈的箱子中，我们可以表示一个堆栈使用的数据结构是这样的，我会提出。在这种情况下，我宣布一个结构，我已经说过了这种结构的内部是一个数字数组变量的大小，我会打电话给这件事情一个堆栈。现在，为什么会发生这种实际工作？在堆栈的情况下，我可以得出这样有效地在屏幕上为一个数组。这里是我的筹码。这是我的号码。我们将吸引他们，因为这，这，这，这，这。然后，我这里有一些其他的数据成员，被称为大小，所以这是大小，这是数字，集体，在这里代表整个iPad的一个堆栈结构。现在，默认情况下，大小大概已经有被初始化为0，里面有什么数字阵列最初当我第一次分配的数组？垃圾。谁知道？它实际上并不重要。它并不重要，如果这是1，2，3，4，5，完全随机我的结构中存储的运气不好，因为只要我知道的堆栈大小为0，则我知道编程方式，不看任何数组中的元素。不要紧，那里有什么。不要看他们，将一个大小为0的含义。但是，假设现在我先走，然后插入到堆栈中的东西。我想插入数字5，所以我把这里的5号，，然后我放下吗？现在我想放下的大小，现在的堆栈大小为1。如果我继续前进，插入数字，让我们说，7下吗？，然后被更新为2，然后我们会做9，然后这被更新为3。但有趣的功能，现在该堆栈的是，如果我想弹出，我应该删除哪一个元素的堆栈的东西，可以这么说吗？ 9将是去的第一件事情。应该如何改变图片，如果我想从栈中弹出一个元素，很像一个托盘Mather中？是的。>> [学生]：设置大小为2。没错，我做的是设置大小为2，和与阵列我该怎么办？我没有做任何事情。我可以，只是肛门，把一个0或-1的东西来表示这是不是一个合法的值，但它并不重要，因为我可以记录以外的数组本身它有多长所以，我知道，只有在此数组中的前两个元素。现在，如果我去了，8号添加到这个数组中，如何改变图片吗？这将成为8，而且这变成3。我在这里省几个小钱。现在，我们有5个，7，8，和我们回来了大小为3。这是非常简单的实现，但我们什么时候这样的设计决策感到后悔吗？什么时候的事情开始去非常，非常错误吗？是啊。 [听不见的学生反应] 当你想回去拿你的第一个元素进去，原来，在这里即使堆栈引擎盖下的是一个数组，这些数据结构，我们已经开始谈论一般也被称为抽象的数据结构，他们是如何实现的完全是除了点。就像一个堆栈的数据结构应该是添加支持操作上推，一个托盘推入堆栈，和流行音乐，从堆栈中删除一个元素，那就是它。如果你是下载别人的代码已经实施这个东西叫做堆栈，这个人会写只有两个函数，你push和pop，在生活中，其唯一目的将这样做。你或他或她是谁实施该计划本来完全是一个决定如何实现引擎盖下方的压入和弹出的语义入栈和出栈的功能。我已经在这里做了一个有点短视的决定通过实施这个简单的数据结构，为什么我的筹码呢？当这个数据结构的突破？在什么情况下我必须返回一个错误，当用户调用push，例如？ [学生]：如果没有更多的空间。没错，如果没有更多的空间，如果我超过容量，这是全部大写的，因为它表明它是某种全局常量。好吧，那么我只是将不得不说，“对不起，我不能把另一个值到堆栈上，“就像在奥美。在某些时候，他们会打那个小柜的顶部。在堆栈中没有更多的空间或能力，在这一点有某种错误。他们必须把元素的其他地方，其他地方的盘，或无处。现在，我们的队列，可以实现略有不同。队列是有一点不同，引擎盖下的，它可以实现作为一个数组，但为什么，在这种情况下，我建议也有一个头元素的列表头，前面的列表，线的第一人，在苹果商店，除了大小？为什么我需要一个额外的数据吗？回想一下号码是什么如果我画如下。现在假设这是一个队列，而不是一个栈，是一样的苹果专卖店排队的差异是公平的。在列表中的开始，在这种情况下，5号线中的第一个人他或她将要被让进店的第一。让我们做到这一点。假设，这是我的队列的状态，在这一刻的时候，和现在的苹果专卖店打开的第一人，5号，是导致进店。如何更改我的图片，我去排队第一人在前面的行？那是什么？>> [学生]：更改队列。改变头，所以就消失了。在现实中，它仿佛如何做到这一点？在现实中，虽然这家伙消失。 7号做什么实际的店吗？他们将向前迈出一大步。但我们体会到，当涉及到阵列移动周围的事物吗？这是一种浪费你的时间了，对不对？为什么你要那么肛门有第一人行开始的，在物理上的内存块的开始？这是完全不必要的。为什么呢？我只记得什么呢？>> [听不见的学生反应] 没错，我只记得这个额外的数据成员头现在的列表头的不再是0，它是刚才。现在，它实际上是数字1。就这样，我得到了轻微的优化。只是因为我去排队的人从行的行开始在苹果专卖店但这并不意味着每个人都有转移，召回是线性的操作。相反，我可以只花费固定的时间然后实现更快的响应。但我付出的价格是获得额外的性能而不是转移大家的吗？是啊。>> [听不见的学生反应] 可以添加更多的人，好了，这个问题是正交的事实，我们周围的人不转移。它仍然是一个数组，所以我们是否转移大家或不哦，我明白你的意思，好吧。其实，我同意你在说什么的，因为它几乎就像现在，我们永远不会使用这个数组开始了因为，如果我删除，然后删除7。但我只把人民的权利。我感觉就像是在浪费空间，最后，我的队列分解成什么都没有，因此，我们可能只是人们概括的，我们可以认为这个数组真的为某种圆形结构，但我们用C做什么运营商在那种环绕吗？ [听不见的学生回应] >>模运算符。这将是一个有点恼人认为，你是怎么做到的环绕，，但我们可以做到这一点，我们就可以开始把人民的利益，在曾经被认为是该行的前面，但我们只记得谁是实际的行头其实是与这头变量。什么，如果不是，最终，我们的目标是，看数字，我们在这里所做过的舞台上与梅艳芳，但我们希望所有这些世界最好的吗？我们希望有更多的复杂性比数组因为我们希望能够动态增长的数据结构。但是，我们不希望拥有的东西，我们指出在第一堂课是不是一个最佳的算法，线性搜索。事实证明，就可以了，事实上，实现或至少接近恒定的时间，有人喜欢梅艳芳，她的数据结构配置，如果她是一个链表，不是一个堆栈，而不是一个队列中，可以，在事实上，拿出一个数据结构，允许她看的东西，什字，不只是数字，我们会打电话给固定的时间。而事实上，展望未来，在这个类中的一个pset时几乎总是一个拼写检查的实施，据此，我们给你再次约15万英文单词，我们的目标是加载到内存中，并迅速成为能够回答问题的形式这个词是拼写是否正确？那真是糟透了，如果你不得不遍历所有15万字来回答这个问题。但是，事实上，我们会看到，我们可以在非常非常快的时间内做到这一点。这将涉及执行一些所谓的哈希表，即使乍看之下这件事情被称为哈希表是怎么回事让我们实现这些超快速的响应时间，事实证明，其实也有一个问题。当谈到时间来执行这件事情，再次，我老毛病又犯了。我是唯一一个在这里。当谈到时间落实这件事情被称为哈希表，我们将不得不做出决定。这件事情应该多大究竟是什么？当我们开始这个哈希表中插入数字，我们如何将它们存储在这样一种方式，我们可以得到他们回来了，很快我们得到了他们？但是，我们会看到不久这个问题的当每个人的生日是在课堂上是相当有密切关系。事实证明，在这个房间里，我们已经有了几百人，这样的可能性，我们两个人有相同的生日可能是相当高的。如果只有40，我们在这个房间里吗？什么是赔率的两个人具有相同的生日吗？ [学生]超过50％。是啊，超过50％。事实上，我什至带来了一个图表。事实证明，这是真的只是一个预演如果只有58我们在这个房间里，我们的概率为2 具有相同的生日是巨大的，几乎100％，而这会为我们造成的伤害一大堆周三。随着中说，让我们休会这里。上周三，我们会看到你。 [掌声] [CS50.TV]