[Powered by Google Translate] [第6条：不太舒服] 内特 - 哈迪森] [哈佛大学] 这是CS50。[CS50.TV] 好的。第6节。 这个星期，我们将要讨论关于数据结构的部分， 这主要是因为这周的问题上设置spellr 做了一大堆不同的数据结构探索。 有一堆不同的方式，你可以去的问题集中， 和更多的数据结构，你知道的，你可以做很酷的事情。 

因此，让我们开始吧。首先，我们要谈栈， 栈和队列的数据结构，我们要谈的。 栈和队列是非常有用的，当我们开始谈论图形， 我们不打算现在做这么多的权利。 但他们真的很好理解的一个大的基本数据结构的CS。 问题集规范中的描述， 如果你拉了起来，谈论类似于堆栈的 桩，你必须在食堂，在食堂用餐托盘 在那里，当在餐厅的工作人员来了，放出来后，他们已经清理了他们的用餐托盘， 他们叠上其他顶级之一。 然后，当孩子们在食物中获得， 他们拉盘，先顶一个，然后它下面的一个，然后是下一个。 所以，实际上，第一盘，就餐人员放下是最后一个被采取关闭。 ，餐厅工作人员把最后一个是第一个被关闭晚餐。 在这个问题集的规格，您可以下载，如果你还没有的话， 我们谈论建模堆栈中的数据的金盏使用这种结构。 

因此，我们有什么，这是什么，提出了在课堂上， 除了在课堂上，我们提出了这个int类型，而不是为char *。 这将是一个堆叠中储存？ 丹尼尔？什么是存储在栈？ [丹尼尔]字符串？ >>我们的字符串存储在栈，准确。 你需要有以创建一个堆栈是一个数组 一个特定的容量，在这种情况下， 能力将是全部大写，因为它是一个常数。 然后在除了阵列，我们需要跟踪的是电流大小的数组。 这里有一点要注意这是一种很酷 是，我们正在创造的堆积之上的另一种数据结构，数组的数据结构。 有不同的方法来实现栈。 我们不会做还相当，但希望做链表的问题后， 你会看到，你可以很容易地实现一个栈的链表。 但现在，我们将坚持到阵列。 所以，再一次，所有我们需要的是一个数组，我们只需要跟踪数组的大小。 [三]对不起，那你为什么说堆栈的顶部的字符串？ 对我来说，似乎，像字符串是在栈。 [哈迪森]是啊。我们正在创造的，我们正在做我们的数组的数据结构 -  这是一个很大的问题。所以，问题是，谁是看这个网上的人， 为什么我们说堆栈顶部的字符串， 因为在这里它看起来像两个字符串里面的堆栈吗？ 这是完全的情况下。 我指的是，我们已经有一个数组的数据结构。 我们已经得到的char *数组，这个数组的字符串， 我们要加至，以创建数据结构的层叠。 

因此，一个堆栈比数组稍微更复杂。 我们可以使用一个数组来建立一个堆栈。 所以这就是我们说的堆栈是建立在一个阵列的顶部。 同样，正如我前面所说，我们可以建立一个堆栈上的链表。 而不是使用一个数组来保存我们的元素， 我们可以使用一个链表来保持我们的元素，并建立堆栈左右，。 让我们通过几个例子，看一些代码， 看看这里发生的一切。 在左边的，我扔了下来，堆栈结构看起来就像在内存中 如果能力在＃定义为4。 我们有我们的四元素的char *数组。 我们已经有了字符串[0]字符串[1]，字符串[2]，字符串[3]， 然后就是最后我们的空间大小的整数。 这有意义吗？好吧。 这是发生什么，如果我做什么的权利， 这将是我的代码，只需要声明一个结构，称为s的堆叠结构。 这就是我们所得到的。它规定了这占用内存中。 这里的第一个问题是，该堆栈结构的内容是什么？ 现在他们什么都不是，但不是完全没有。 他们这种垃圾。我们不知道是什么。 当我们宣布栈S，我们仅仅是用下来的内存上。 这是一种类似于声明INT I，而不是初始化它。 你不知道有什么可以做的。你可以在那里读什么， 但它可能不会是有帮助的。 你要永远记住做的一件事是初始化任何需要被初始化。 在这种情况下，我们要初始化的大小是零， 因为那将是对我们非常重要。 我们可以继续前进，初始化的指针，所有的char * S， 一些可以理解的价值，可能为null。 但它不是完全必要的，我们做到这一点。 

现在，这两个主要操作栈是什么？ 有人还记得演讲一摞摞你做了什么？是吗？ [斯特拉入栈和出栈？ “没错。 入栈和出栈的两个主要操作栈。 推做什么？ >>它把东西到顶部 栈，然后大跌眼镜把它关闭。 [哈迪森没错。因此，推，推压在堆栈的顶部上的东西。 这就像在餐厅工作人员的用餐托盘放在柜台上。 大跌眼镜的是一个餐盘堆栈。 让我们通过一对夫妇的例子发生了什么 当我们事情推入堆栈。 如果我们推到我们的堆栈字符串'hello'， 这是我们的图现在是什么样子。 看看会发生什么？ 我们推入我们的字符串数组的第一个元素 我们调升我们的规模数为1。 因此，如果我们看两个幻灯片之间的区别，在这里为0，前推。 这里是后推。 前推，后推。 现在，我们有我们的栈中的一个元素。 这是字符串“hello”，这就是它。 一切，在我们的字符串数组，数组中的垃圾。 我们没有初始化它。 比方说，我们推进另一个字符串到我们的堆栈。 我们要推动“世界”这个时间。 所以，你可以看到这里的“世界”顶部的“hello”， 和的大小计数上升到2。 现在，我们可以把“CS50”，那将再次走在上面。 如果我们回去吧，你可以看到我们如何推动事情的堆栈的顶部。 现在，我们得到流行。 当我们弹出的堆栈的东西，这是怎么回事？ 任何人看到其中的差别吗？这是很微妙的。 [学生]的大小。 “是的，变化的大小。 

你还有什么改变？ [学生]中的字符串。 “没错。的字符串。 事实证明，当你做它，这样一来， 因为我们还没有的元素复制到我们的堆栈， 我们其实并不需要做什么，我们就可以使用的大小 跟踪的一些事情在我们的数组 所以，当我们再次弹出，再次我们只是我们的规模递减下降到1。 有没有必要去和覆盖任何东西。 一种时髦的。 事实证明，我们通常只是离开的事情，因为这是我们做的工作的。 如果我们不回去，覆盖的东西，那么为什么这样做？ 所以，当我们的堆栈，弹出两次的，它是递减的大小了几次。 再次，这仅仅是因为我们并没有复制的东西到我们的堆栈。 是吗？来吧。 不知所云] >> [学生，然后会发生什么，当你把东西了吗？ 当你再次推的东西，它在哪里去了？ 到哪里去了，瓦西里？ >>转换成字符串[1]？ “没错。 它为什么不进入字符串[3]？ 因为它忘记了，有什么字符串中的[罗勒] [1] [2]？ [哈迪森没错。我们的栈，从本质上讲，“忘了”，这是到什么 [1]中的字符串或字符串[2]，因此，当我们把“活泉”， 它只是将字符串[1]的元素。 是否有任何问题，这是如何工作的，在一个基本的水平呢？ [三]因此，这是不以任何方式，在动态方面的金额 或条款的堆栈大小？ [哈迪森没错。这是 - 这一点，这是不是一个动态growning的堆栈。 这是一个堆栈，可容纳最多4的char *，最多四件事情。 如果我们试图和推动五分之一的事情，你认为应该发生的吗？ [学生，不知所云] [哈迪森没错。有一些事情会发生。 它可能会段错误，这取决于我们什么 -  我们究竟是如何实现的后端。 它可以覆盖。它可以有，我们在课堂上谈到，缓冲区溢出。 什么是最明显的事情，可能会被覆盖 如果我们试图把一个额外的东西，我们的堆栈吗？ 所以你提到的缓冲区溢出。 可能被写入或出丑的事情是什么 如果我们溢出意外试图把一个额外的东西吗？ [丹尼尔，不知所云] >>可能。 但在最初，可能会发生什么？如果我们试图把四分之一的事情吗？ 它可能会覆盖的大小，至少，我们已经有了这个内存图。 

在这个问题中集规范，这就是我们将要实施的今天， 我们做想做的事，只是返回false。 我们的push方法会返回一个布尔值， 和布尔值是true，如果成功推 假的，如果我们不能把任何东西更多，因为堆栈是满的。 让我们通过一点点的代码。 下面是我们的推送功能。 我们的推送功能的堆栈中的字符串放到栈中。 这将返回true，如果该字符串被成功地推 在堆栈，否则返回false。 什么可能是一个良好的第一件事就是在这里做的任何建议吗？ [三]如果大小等于能力，那么返回假的？ [哈迪森]宾果游戏。尼斯的工作。 如果大小的能力，我们将返回false。 我们不能把任何东西在我们的堆栈。 否则，我们要放东西的堆栈的顶部。 “堆栈的顶部，”最初是什么？ [丹尼尔]大小为0？大小为0。 后，有一件事在堆栈中的堆栈的顶部是什么？大小姐，你知道吗？ [大小姐]。 >>尺寸是的，没错。不断增加的大小， 每次你把新的元素在数组中的索引大小。 我们可以做这样的一个班轮，如果是有道理的。 所以，我们有我们的字符串数组，我们要访问它的规模指数， 我们只是在那里来存储我们的char *。 请注意有没有字符串复制在这里， 没有动态分配的内存？ 然后大小姐带来了什么，我们现在要做的， 因为我们的字符串存储在阵列中的适当位置， 她说，我们的规模递增，所以我们已经准备好为未来推。 因此，我们可以做到这一点，与s.size + +。 在这一点上，我们已经被推到我们的数组。我们必须做的最后一件事情是什么？ [学生]：返回true。 >>返回true。 因此，它是非常简单的，一个非常简单的代码。不太多。 一旦你已经包裹着你的头周围的堆栈是如何工作的， 这是非常简单的实现。 

现在，下一个的一部分，这是一个字符串关闭堆栈弹出。 我想给你们一些时间来工作，这是一个有点。 这几乎是本质上是相反的我们做了什么在推动。 我所做的其实是 - 哎呀。 我已经启动的器具，在这里，在家电， 我拉起的设置5规范的问题。 如果我们放大在这里，我们可以看到我在cdn.cs50.net/2012/fall/psets/pset5.pdf。 你们下载的代码，设在这里，section6.zip？ 好的。如果你还没有这样做，这样做，现在，真的很快。 我会做到这一点在我的终端窗口。 其实，我在这里做了。是啊。 是的，山姆？ >>我有一个问题，你为什么说s.string的括号内的大小= STR？ STR是什么？的是，以前在什么地方，或 - 哦，在char *海峡？ [哈迪森]是的，没错。这是的说法。哦，没关系。抱歉。 [哈迪森我们指定的字符串推入。 其他可能遇到的问题，我们并没有真正在这里谈论的是 我们想当然的，我们有这个变量称为s 这是在范围和访问。 我们采取理所当然地认为是这个堆栈结构。 所以回头看这推的代码， 你可以看到，我们正在做的东西与这个字符串的时候传递 但随后突然，我们访问s.size，如，走到哪儿呢？ 在代码中，我们要看看在一节中的存档 然后设置的东西，你会做你的问题， 我们已经取得了我们的协议栈结构的一个全局变量 这样我们就可以访问它，在我们所有的不同的功能 而无需手动传递它，并通过它的参考， 做所有这类的东西。 我们只是骗了一点点，如果你愿意，让事情变得更好的。 这就是我们在这里做的东西，因为它的乐趣，它更容易。 通常情况下，你会看到人们这样做，如果他们有一个很大的数据结构 在他们的程序中的操作。 

让我们回到的设备。 每个人都成功地得到section6.zip？ 每个人都将它解压缩使用解压缩section6.zip？ 如果你进入第6节目录 -  AAH，所有的地方 -  和你列出在这里，你看，你有三个不同的c文件。 你有一个队列中，SLL，这是单链表，和堆栈。 如果你打开​​stack.c， 你可以看到，我们已经为我们定义了这个结构， 确切的结构，我们刚才讲的幻灯片中。 我们已经得到了我们的全局变量的堆栈， 我们已经得到了我们的推送功能， 然后我们有我们的流行功能。 我会把代码的推背在幻灯片上， 但我想你们做的是，尽你的能力， 去实现弹出的功能。 一旦你实现了它，你就可以编译使堆栈， 然后运行生成的可执行堆栈， 将运行所有测试代码在这里，在主。 主要负责的实际push和pop调用 ，确保一切通过所有权利。 它也初始化堆栈的大小在这里 所以你不必担心初始化该。 你可以假设它被正确初始化 的时候，你访问它，在弹出的功能。 这是否有意义吗？ 所以，在这里，我们走了。有“推”的代码。 我给你们5分钟或10分钟。 如果你有任何问题，在此期间，当你编码， 请大声问他们。 所以，如果你得到一个棘手的问题，就问我。 让我知道，让其他人知道。 工作与你的邻居了。 [丹尼尔]我们只是实现POP现在好了吗？ >>只是弹出。 虽然你可以推，如果你想复制的实施 使测试工作。 因为它是难以测试的东西进入 -  或者，这是很难测试弹出堆栈出来的东西，如果没有任何堆栈中开始。 

流行音乐应该是返回是什么？从堆栈顶部的元素。 它应该得到元素的堆栈的顶部 然后递减堆栈的大小， 现在你已经失去了元素的顶部。 然后返回的元素在上面。 [学生，不知所云] [哈迪森]所以，如果你这样做，会发生什么？ [学生，不知所云] 最终发生的是什么，你可能访问任何 尚未初始化的元素，所以你的计算 最后一个元素是处于关闭状态。 所以在这里，如果你注意到，在推，我们访问在s.size元素的字符串 因为它是一个新的索引。 这是新的堆栈的顶部。 而在流行音乐，s.size将是下一个空格， 空间的所有元素在堆栈的顶部。 因此，最顶端的元素是不在s.size， 但相反，它是在它下面。 

其他的事情，当你 - 在弹出 你有递减的大小。 如果你还记得我们的小图就在这里， 真的，只有我们看到了发生的事情，当我们调用pop 是，这个尺寸下降，第一至第2，然后为1。 然后，当我们把一个新的元素，它会继续在适当的位置。 罗勒如果s.size 2，然后将它的元素， ，然后你要弹出该元素吗？ 因此，如果我们去了 - “”所以，让我们再看看这个。 如果这是我们在这一点上堆 我们称之为流行， 指数是最上面的元素吗？ [罗勒] 2，但它是怎么回事，弹出3。 “没错。 所以这就是我们的规模是3，但我们要流行的元素，索引2处。 这是典型的种关闭的，你有零的数组索引。 所以，你要弹出的第三个元素，但第三个元素是不是在索引3。 原因我们没有做到这一点减1，当我们正在推动 是因为现在，你注意到最上面的元素， 如果此时我们推入堆栈别的， 我们希望将它在索引3。 它只是发生的大小和排队的指数，当你推。 

谁拥有一个工作栈的实现？ 你已经有了一个工作中的堆叠。你有没有流行的工作吗？ 丹尼尔：是的。我是这么认为的。 >>程序的运行，而不是段的断层，它打印出来吗？ 它打印出来的“成功”，当你运行它呢？ 是啊。叠加，运行它，如果它打印出的“成功”，不繁荣， 然后，所有的好。 好的。让我们的设备真的很快， 我们将步行通过。 如果我们看一下这是怎么回事在这里的流行音乐， 丹尼尔，究竟是什么做的第一件事，你呢？ [丹尼尔]如果s.size是大于0。 [哈迪森]好吧。你为什么这样做呢？ [丹尼尔]为了确保堆栈中，有一种内在的东西。 [哈迪森权。你想进行测试，以确保，s.size大于0; 否则，你有什么要发生吗？ [丹尼尔]返回空值吗？ >>返回NULL，准确。 因此，如果s.size是大于0。那么什么是我们该怎么办？ 如果堆栈不为空，我们该怎么办？ [斯特拉]递减的大小吗？ >>您递减的大小，还行。 所以，你是怎么做到这一点呢？ >> s.size  - 。 [哈迪森大。然后你做了什么？ [斯特拉然后我说回s.string [s.size]。 [哈迪森大。 否则返回null。是的，山姆？ [三]为什么不需要s.size的+ 1？ [哈迪森]加1？ >>呀。 “知道了。 [三]我想因为你正在服用1个输出， 然后你要回来，他们要求的不是一个。 哈迪森而这正是我们在谈论这个问题的0指数。 因此，如果我们在这里放大。 如果我们看一下这家伙在这里，你可以看到，当我们弹出， 我们在弹出的元素索引2处。 

因此，我们减少我们的规模，我们的规模符合我们的索引中。 如果我们不递减的大小，那么我们需要做的大小，-1，然后递减。 大。所有的好？ 在此有任何疑问？ 有许多不同的方式来写这个问题，以及。 事实上，我们可以做一些事情，甚至 - 我们可以做一个班轮。 我们可以做一个单行的回报。 因此，我们实际上可以减小之前，我们通过这样做，返回。 因此，把 - 前s.size中。 这使该行真的很密集的。 凡 - 第大小和s.size  - 之间的差异 这个后缀 - 他们把它叫做后缀因为 - 来自后s.size  -  意味着s.size找到索引的目的评价 因为它是目前被执行时，这条线， 然后 - 发生后，该行被执行。 后的元素在索引s.size的访问。 这不是我们所希望的，因为我们希望首先发生递减。 Othewise，我们将要访问的阵列，有效地，出界了。 我们将要访问的元素，我们要访问一个以上。 是啊，山姆？ “是更快或使用较少的内存在同一行或不使？ [哈迪森说实话，这真的视情况而定。 [山姆店，不知所云] >>呀，视情况而定。你可以做编译器技巧 让编译器认识到，通常情况下，我想。 

所以，我们所提到的有关该编译器优化的东西一点点 您可以在编译， 这是一个编译器可能能够找出什么样的事情， 喜欢哦，嘿嘿，也许我可以做这一切在一次操作中， 而不是在从RAM加载的大小变量， 递减，其存储回，然后再重新加载 处理此操作的其余部分。 但通常情况下，没有，这是不诸如此类的事情， 这将会使你的程序显着更快。 任何更多的问题栈？ 

因此，入栈和出栈。如果你们想尝试的黑客版， 我们所做的黑客版实际上是走了 ，这个堆栈动态增长。 面临的挑战主要是在推功能在这里， 弄清楚如何使该数组中成长 当你继续推到堆栈上越来越多的内容。 它实际上是没有太多额外的代码。 只需要打一个电话 - 你必须记住要调用malloc（）有正确的， 然后当你要调用realloc的。 这是一个有趣的挑战，如果你有兴趣。 

但暂时，让我们继续前进，让我们来谈谈队列。 滚动经过这里。 队列是亲兄妹的堆栈。 所以在堆栈中的东西，放在最后 的第一件事情，然后进行检索。 我们已经得到这最后的，先出，或后进先出法，订货。 而在队列中，你所期待的，当你站在线， 线，第一件事就是到队列中的第一人， 是的第一件事就是被从队列中检索。 队列也经常被用来当我们正在处理的图形， 像我们谈到了简短的堆栈， 和队列的一堆其他东西也很方便。 一件事，经常试图保持，例如， 元素的排序列表。 你可以做到这一点的数组。您可以保持在一个数组的排序列表的东西， 但在变得复杂的是，那么你总是要找到 在适当的地方插入接下来的事情。 所以，如果你有一个数组的数字，从1到10， 然后你要扩大到所有的数字1到100， 你得到这些数字以随机顺序，并试图把一切都 排序，你通过，你最终做了很多的转移。 某些类型的队列和某些类型的底层数据结构， 实际上，你可以保持相当简单。 您不必添加一些东西，然后洗牌整个事情的时间。 你也做了很多的内部元素的转移。 当我们在看一个队列，你看 - 在queue.c也一节中的代码 -  的结构，我们已经给了你，我们给你一个堆栈的结构非常类似。 

有一个例外，唯一的例外 是，我们有这个额外的整数称为头， 和这里的头部为队列头的跟踪的 或在队列中的第一个元素。 用一个堆栈，我们能够跟踪我们要撷取的元素， 或堆栈顶部的，只是使用的大小， 而我们的队列，处理两端。 我们正在努力结束时粘性的东西，但然后返回从正面的东西。 因此，有效的是，用头，我们有队列的开头的索引， 和容量给我们的队列的末尾的索引 这样我们就可以获取事物从头部添加东西的尾巴。 鉴于带层叠，我们只处理堆栈的顶部。 我们从来没有访问堆栈的底部。 我们只添加东西到顶部，拿了东西的顶部 所以我们并不需要额外的内部结构领域。 一般有意义吗？ 好的。是的，夏洛特？ [夏洛特，不知所云] 哈迪森]这是一个很大的问题，这是一个在演讲。 也许走过的几个例子说明了为什么 我们不希望使用字符串[0]的队列的头。 

所以，想象一下，我们有我们的队列中，我们将调用它的队列。 在刚开始的时候，我们刚刚实例化它， 当我们刚刚宣布了它，我们还没有初始化任何东西。 这是所有的垃圾。当然，我们要确保我们初始化 的大小和头信息是0，一些合理的。 我们还可以继续前进，在我们的队列空出的元素。 此图配合，请注意，现在我们的队列只能容纳三要素; 而我们的堆叠可容纳四，我们的队列只能容纳3。 而这仅仅是使图适合。 这里发生的第一件事情是我们进行排队字符串“hi”。 就像我们与堆栈，这里没有什么可怕的不同， 我们抛出的字符串，字符串[0]和我们的规模递增1。 我们的入队“再见”，它被装出来的。 因此，这看起来就像一个堆栈的大部分。 我们这里，开始了新的元素，新元素，规模不断上升。 在这一点上会发生什么事时，我们要出列的东西吗？ 当我们要出列，这是我们要出列的元素吗？ [罗勒]字符串[0]。 >>零。没错，罗勒。 我们要摆脱的第一个字符串，这其中，“喜”字。 那么，是什么其他的事情，改变了吗？ 请注意，当我们突然出现的堆栈的东西，我们只是改变了大小， 但在这里，我们有一对夫妇的一些改变。 不仅的大小变化，但头部的变化。 这是要回到夏洛特点： 为什么我们有这个头呢？ 这是否有意义，夏洛特？ >>类的。 [哈迪森怎样的呢？到底发生了什么，当我们出列吗？ 什么头做的，现在是有趣的？ [夏洛特]哦，因为它改变了 - 好吧。我明白。 因为头 - 头指向的位置方面的变化。 它不再是零指数1。 >>是的，没错。 发生了什么事，如果出队的高元 做，我们没有这个头字段 因为我们总是在0指数，我们的队列的头，调用该字符串 然后，我们不得不转移，其余的队列。 我们不得不转向“再见”从字符串[1]的字符串[0]。 字符串[2]到字符串[1]。 我们不得不这样做的整个列表中的元素， 整个阵列的元素。 当我们这样做是一个数组，变得非常昂贵。 所以在这里，它不是一个大问题。我们只需要在数组中的三个要素。 但是，如果我们有一千或一万个元素的队列， 然后突然间，我们开始出列了一堆调用所有在一个循环中， 事情真的要放慢，因为它转移一切不断。 你知道吗，转移1，移位1 1，移位，移位1。 相反，我们使用这个头，我们把它称为一个“指针”，即使它不是一个真正的指针 从严格意义上讲，它不是一个指针类型。 这不是一个int *或char *或类似的东西。 但是，它指向或表示我们的队列的头。是吗？ 

[学生]：出队知道如何只弹出，无论是在头部？ [哈迪森如何出队知道如何弹出无论是在头吗？ “是的，是的。 >>什么，它看起来是，只是任何头字段被设置为。 因此，在这第一种情况下，如果我们看一下在这里， 我们的头是0，索引为0。 “没错。 [哈迪森]因此，它只是说，好吧，索引为0的元素，字符串“您好”， 在我们的队列头的元素。 因此，我们要出列，那家伙。 那将会是元素，该元素被返回给调用者。 是的，萨阿德吗？头“等基本设置 - 你要去的地方的索引呢？ 这是它的开始呢？ >>呀。 “好了。 哈迪森]这是我们的阵列成为新的开始。 所以，当你出列的东西，所有你所要做的是在索引访问元素q.head， 和将要出列的元素。 您还可以递减的大小。 我们会看到在事情变得有点棘手，这一点。 我们出列，而现在，如果我们再进行排队， 我们进行排队在哪里？ 在我们的队列中的下一个元素哪里？ 假设我们要排队的字符串“CS”。 到索引会去吗？ [学生]字符串[2]。 >>双。 为什么是2而不是0呢？ [罗勒]因为现在的头是1，所以这就像开始的列表吗？ [哈迪森权。表示最终的名单什么？ 我们来表示我们的队列？ 头是头，我们的队列中，开始我们的队列中。 我们的队列中的结局是什么？ [学生]大小。 >>大小，准确。 因此，我们的新的元素，在大小，并在头的元素，我们采取的脱落。 当我们加入队列的下一个元素，我们正在把它在大小。 [学生]：在您提出，虽然，大小为1，正确的吗？ [哈迪森权。因此，在大小相当。尺寸+，+1，+头。 因为我们将一切头量。 所以在这里，现在我们已经有了一个大小为1的队列开始在索引1。 尾巴是指数2。是吗？ 

[学生]：会发生什么事时，你出列字符串[0]，和字符串的内存插槽 一下就空了，基本上，或者只是忘了吗？ [哈迪森]是啊。从这个意义上说，我们只是忘记他们。 如果我们存储副本 -  许多数据结构往往会保存自己的副本的元素 管理的数据结构，使该人不必担心 所有这些指标都在哪里。 数据结构包含的一切，拥有所有的副本， 以确保这一切仍然存在，适当的。 然而，在这种情况下，这些数据结构只是为了简单起见， 不是我们的东西都存储在他们的副本。 [学生]：所以，这是一个连续的数组 - ？ “是的。 如果我们回头看，这种结构的定义是什么，它​​是。 这只是一个标准的数组，就像你看到的那样， 数组的char *。 那是 - ？是啊，我只是想知道 如果你最终会耗尽内存，在一定程度上， 如果您有您的阵列中的所有这些空点吗？ 哈迪森]是啊，这是一个很好的点。 

如果我们看看发生了什么事，现在在这一点上， 我们已经充满了我们的队列中，它的样子。 但是我们还没有真正填补了我们​​的队列 因为我们有一个队列的大小，但它在索引1开始， 因为这就是我们的头指针。 像你说的，在字符串的元素[0]，在0指数，是不是真的存在。 这不是在我们的队列中了。 我们只是懒得去和覆盖它时，我们出列。 因此，即使它看起来就像我们的内存已经用完了，我们真的没有。 这点是可供我们使用。 适当的行为，如果我们试图和第一个出列的东西 如“再见”，会弹出再见关闭。 现在，我们的队列开始索引2处，大小为1。 现在，如果我们试图再次进行排队东西，比如50， 50应该在这点指数0 因为它仍然为我们提供。是的，萨阿德吗？ [萨阿德并自动发生吗？ [哈迪森它不会自动发生相当。你必须做数学题 它的工作，但基本上是我们所做的就是我们刚刚缠。 [萨阿德是好，如果在它的中间有一个洞？ 哈迪森的是，如果我们能正确的数学工作。 

事实证明，这实际上是很难做到的mod运算符。 所以，就像我们与凯撒和加密东西， 使用模，我们可以得到的东西，以环绕，并保持下去 周围一圈又一圈与我们的队列中， 保持周围，头指针移动。 请注意，尺寸总是尊重的元素数实际上内的队列中。 而这仅仅是头指针，骑自行车通过。 如果我们看看这里发生了什么事，如果我们回到开头， 你只是看看会发生什么头 当我们进行排队的东西，什么都没有发生的头部。 当我们排队的其他东西，什么都没有发生的头部。 只要我们出列的东西，头一个。 我们排队的东西，什么也没有发生的头部。 当我们出列的东西，一下子头会增加。 当我们进行排队的东西，什么也没有发生的头部。 

在这一点上会发生什么，如果我们再次出列的东西吗？ 有什么想法？头会发生什么？ 什么是应该发生的头 如果我们出列别的东西吗？ 头现在是索引2处， 这意味着队列头部的字符串[2]。 [学生]：它返回0？ >>，它应该返回为0。它应该换点左右，准确。 到目前为止，我们每次叫出队，我们已经添加一个头， 添加一个头，加一个头，添加一个头。 一旦这个头指针到达最后一个索引在数组中， 然后，我们必须把它包起来开始回到身边，回到0。 [夏洛特]确定堆栈的队列中的能力？ [哈迪森在这种情况下，我们刚刚一直在使用一个＃定义的常量。 “好了。 [哈迪森在实际的文件，你可以去和淤泥一点点 大或小，你想要的。 [山猫]因此，当你正在做一个队列，怎么你的计算机知道 你想堆叠就可以有多大？ 哈迪森]这是一个很大的问题。 有一对夫妇的方式。一种是只定义了前 并说这将是一个队列中有4个元素或50个元素或10,000。 另一种方法是做的黑客版的人在做什么 并创建功能，让您的队列动态地增长，越是得不到的东西加进来 

[山猫]第一个选项，语法是什么您使用 告诉程序什么是队列的大小吗？ 哈迪森啊。所以，让我们离开这。 我仍然在这里stack.c，所以我只是要滚动到顶部。 在这里你能看到这种权利？这是的＃define能力10。 这几乎是完全相同的语法，我们已经为队列。 除了在队列中，在这里，我们已经得到了额外的结构域。 [夏洛特]哦，我想指的是容量为字符串的能力。 哈迪森啊。 >>这个​​词，它的最大长度。 “知道了。 是啊。这里的能力 - 这是一个伟大的点。 这是这是棘手的 因为我们已经在这里声明的是一个数组的char *。 数组的指针。 这是一个字符数组。 这可能是你见过的时候，你已经宣布你的缓冲区的文件I / O， 当你已经创建字符串手动在堆栈中。 然而，我们得到的是一个数组的char *。 因此，它是一个数组的指针。 其实，如果我们放大了，我们看看这是怎么回事 在演示文稿中，您将看到实际的元素，字符数据 没有被存储在数组本身。 什么是存储在我们的数组的指针的字符数据。 好吧。因此，我们已经看到了如何与堆栈，队列大小就像， 大小始终尊重当前队列中的元素的数量。 2 enqueue操作完毕后，大小为2。 在出队的规模现在是1。 在另一个排队的大小是高达2。 这样的大小在队列中，绝对尊重的元素数 头，然后不断循环。 从0-1-2，0-1-2，0-1-2。 每次我们调用出队，头指针会递增到下一个索引。 如果头走了过来，这回绕到0。 所以，我们可以编写出列的功能。 我们要离开排队功能来实现，而不是你们。 

当我们队列中取出一个元素，我们的队列中， 丹尼尔的第一件事情就是当我们开始写的堆栈弹出功能是什么？ 让我听到从别人谁没有发言。 让我们来看看，萨阿德，你还记得丹尼尔做的第一件事时，他写道：弹出？ [萨阿德]，它是 -  >>他测试的东西。 萨阿德]如果大小是大于0。 “没错。 那是什么测试？ 萨阿德测试，看看如果有什么事，里面的数组。 [哈迪森]是啊。没错。所以，你可以不弹出任何出栈，如果它是空的。 同样，你不能从队列中出列任何东西，如果它是空的。 什么是我们应该做的，我们出队函数的第一件事，你觉得呢？ 萨阿德]如果大小是大于0？ >>呀。 在这种情况下，我其实只是测试，看它是否为0。 如果是0，我们可以返回null。 但相同的逻辑。 让我们继续。 如果不为0，是我们要出列的元素？ 萨阿德在头吗？ “没错。 我们可以在我们的队列中拉出的第一个元素 通过访问的头部处的元素。 没有什么神秘的。 在那之后，我们应该怎么办？有什么发生呢？ 其他的事情，我们谈到在出队的是什么？ 有两件事情要发生，因为我们的队列已经改变。 [丹尼尔减少的大小。 >>我们必须缩小尺寸，并增加头部？没错。 为了增加头部，我们不能只是一味地增加了头，记住了。 我们可以不只是做queue.head的+ +。 我们也必须包括这个MOD的能力。 我们为什么要国防部的容量，Stella吗？ 斯特拉由于它具有环绕。 “没错。 我们的国防部的容量，因为它具有包装回绕到0。 所以，现在，在这一点上，我们可以做什么，丹尼尔说。 我们可以减小尺寸。 然后我们就可以返回的元素在队列的最前面。 它看起来有点粗糙第一。你可能有一个问题。你说什么？ 

[三]为什么是第一个在队列的最前面？哪里去了？ 哈迪森]从第四线从底部。 经过我们测试，以确保我们的队列不为空， 我们拉出来的char *首先，我们拉出来的元素，坐在头指数 我们的数组，字符串数组，“呼叫，第一呢？ [哈迪森]，我们称之为第一。是啊。 只是跟进，为什么你认为我们必须这样做吗？ [三]每个第一刚刚返回q.strings的[q.head？ >>呀。 “因为我们正在做这个不断变化的的q.head的MOD功能的， 有没有办法做到这一点也回线内。 [哈迪森没错。你点上。三是完全发现。 究其原因，我们在我们的队列中拉出的第一个元素，并将其存储到一个变量 是因为这条线我们刚刚q.head的， 有mod运算符在那里没有的东西，我们可以做的 并使其生效的头没有 - 在同一行。 因此，我们必须拿出的第一个元素，然后调整头， 调整大小，然后再回到我们拉出的元素。 而这点，我们将看到后与 链表，我们打他们。 很多时候，当你释放或处理链表 你需要记住的下一个元素，在未来的链表的指针 在处理当前。 因为否则你扔掉的左边列表中的信息。 现在，如果你去到您的设备，你打​​开queue.c-X了这一点。 所以，如果我打开queue.c，让我在这里变焦， 你会看到，你有一个外观类似的文件。 我们早前曾与stack.c外观类似的文件。 我们已经得到了我们的结构定义的队列，就像我们在幻灯片上看到的。 

我们有我们的排队功能，这是为你做的。 我们这里出列功能。 在该文件中的“出列”的功能未实现， 但我会把它备份，让您可以输入，如果你想在PowerPoint。 因此，在接下来的5分钟左右，你们的工作排队 这几乎是正好相反出列。 您不必调整头，当你入队，但你有什么调整吗？ 大小。所以，当你排队，头部保持不动，被改变的大小。 但它确实需要一点点 - 你将不得不发挥与模 弄清楚究竟什么样的指标应插入新的元素。 所以，我给你们一点点，把出列在幻灯片上， 你们有问题，喊出来，使我们可以 都在谈论他们作为一个群体。 此外，你不知道不知道 - 当你调整大小的尺寸，你永远可以 -  你有没有曾经国防部的大小吗？ [丹尼尔]第>>您不必国防部的大小，正确的。 因为大小总是会，如果让隐私无处藏 - 假设你正在管理的事情适当地， 的大小总是会在0和3之间。 你在哪儿于MOD当你在做排队吗？ [学生]的头。 “仅适用于头部，准确。 你为什么国防部在排队？ 的情况是，你必须为mod是什么时候？ [学生]：如果你有东西在空间，喜欢在空间1和2， 然后你需要添加的东西在0。 [哈迪森]是的，没错。所以，如果你的头指针是在最后， 如果你的尺寸加上你的头比较大，或者更确切地说，是怎么回事到环绕的队列。 

因此，在这种情况下，我们已经有了在这里在幻灯片上， 如果我现在要排队， 我们要排队什么的索引为0。 因此，如果你在50“，我称之为排队50， 它会在底部。它在索引0。 它取代了已经出列'嗨'。 [丹尼尔]不要你照顾，出队了吗？ 为什么它是做什么用头在排队吗？ [哈迪森]哦，这样你就不会修改的头，对不起。 但是，当你访问，你必须用mod运算符 你要排队，当你访问的元素 你的队列中的下一个元素。 瓦西里我没有做到这一点，我在那里的“成功”。 [丹尼尔：哦，我明白你在说什么。 [哈迪森所以，你并没有 - 你只是做了在q.size？ [罗勒]是啊。我只是改变了双方的，我没有做任何事情的头部。 [哈迪森]你实际上并不需要重设的头是什么， 但是当你到字符串数组中的索引， 你必须继续前进，计算出下一个元素是， 因为枝条堆栈中的下一个元素在堆栈总是 的大小相对应的索引。 如果我们回顾一下，在我们的压栈功能， 索引的大小，我们总是可以花掉我们的新元素。 而与队列，我们​​不能这样做， 因为如果我们在这种情况下， 如果我们排队的50我们新的字符串，字符串[1] 我们并不想这样做。 我们希望有新的字符串的索引为0。 

是否任何人 - 是吗？ [学生]：我有一个问题，但它不是真正相关。 当有人要求类似PRED指针是什么意思？ 那是什么名字的简称吗？我知道这只是一个名字。 哈迪森] PRED指针？让我们来看看。在什么情况下？ [学生]：这是插入。如果你想，我可以请你以后 因为它不是真正相关的，但我只是 -  [哈迪森从大卫的讲座插入代码？ 我们可以拉起来，说这些了。 我们将讨论下，一旦我们得到的链接列表。 

因此，让我们看排队的函数看起来像真的很快。 人的第一件事就是试图在您的排队线是什么？插入此队列中呢？ 类似的堆栈推你做了什么。 你做了什么，Stella吗？ [斯特拉，不知所云] [哈迪森没错。如果（q.size ==容量） -  在正确的地方，我需要把我的大括号 - 返回false。 在一点点放大。好吧。 现在什么是未来的事情，我们必须做的吗？ 与堆栈，就像插在正确的地方。 因此，什么是正确的位置插入，？ 与堆栈是索引的大小，这不是很。 [丹尼尔]我有q.head- -   -  >> q.strings的吗？ >>呀。 的q.strings q.head + q.size模能力]？ [哈迪森我们可能要加上括号解决这个问题 这样我们就得到适当的优先，所以，大家cleart。 和平等的吗？ >>海峡？ >>给乙方。大。 现在我们必须做的最后一件事是什么？ 就像我们在堆栈中。 >>增量的大小吗？ >>增量的大小。 轰。之后，从启动代码只是返回false默认情况下， 我们要更改为true，如果一切顺利，一切顺利。 好的。这是一个很大的信息部分。 我们不是挺了过来。我们要谈谈真的很快单链表。 我会把这，所以我们可以回去吧。 但是，让我们回到我们的介绍只是多了一些幻灯片。 因此，排队是的TODO，现在我们已经做到了。 

现在，让我们来看看在单链表。 在讲座中，我们谈到了这些多一点点。 有许多你们在这里我们看到的演示的人 笨拙地指向到相互持股数？ >>，我就在那。 “你们认为什么？这样做，希望神秘面纱这一点吗？ 与列表，事实证明，我们应对这种类型的，我们要调用一个节点。 而与队列和栈我们，我们会打电话给队列，栈的结构， 我们有这些新的队列，堆栈类型， 这里的列表实际上只是由一堆节点。 以同样的方式，字符串的字符只是一堆所有排队彼此相邻的。 链表是一个节点和另一个节点和另一个节点和另一个节点。 而不是砸的所有节点，并将其存储连续 所有彼此在内存中， 这下指针允许我们存储节点的地方，随意。 然后他们种线一起从一个点到下一个。 

是什么很大的优势，这有一个数组？ 连续超过存储一切只是停留彼此？ 你还记得吗？是吗？ >>动态内存分配？ >>动态内存分配在什么意义呢？ [学生]，你可以保持它大，你没有将你的整个阵列？ [哈迪森没错。因此，一个数组，当你想要把一个新的元素，它的中间， 你有改变一切，以腾出空间。 而像我们谈论的队列中， 这就是为什么我们保持头指针， 所以，我们不是不断变化的东西。 因为得到昂贵的，如果你有一个大数组 你经常做这些随机的插入。 而与列表，所有您需要做的是把它的新节点上， 调整指针，你就大功告成了。 什么吸什么呢？ 除了事实上，它是不容易的工作数组？是吗？ [丹尼尔]嗯，我想它要困难得多访问某个特定的链接列表中的元素？ [哈迪森你不能只是跳转到链表中的任意一个元素。 你怎么做，而不是吗？ >>您逐步完成整个事情。 [哈迪森]是啊。你必须去通过一次一个地，一次一个。 这是一个巨大的 - 这是一个痛苦。 有什么其他 - 这还有另一个倒台。 罗勒，您可以向前和向后走？你必须去一个方向吗？ [哈迪森]是啊。那么，我们如何解决这个问题，有时？ [罗勒]双链表？ “没错。有双链表。 也有 - 对不起吗？ 

[三]是一样PRED的事情， -  我想起来了，这不正是PRED的是吗？ 这不就是在双和单间？ [哈迪森]让我们看看他在做的究竟是什么。 所以，在这里，我们走了。下面的代码。 在这里，我们有predptr，在这里。这是你在​​谈论什么吗？ 因此，这是 - 他释放的名单，他试图保存一个指向它的指针。 这是不是双重，单链接列表。 我们可以稍后再谈谈这个问题，因为这是在谈论释放名单 我想告诉一些其他的东西。 但它只是 - 它记住的指针的值 [学生]：哦，这是前面的指针吗？ >>呀。 所以，我们就可以递增：指针本身之前，我们就可以自由predptr是什么。 因为我们不能免费指针，然后调用PTR =指针下，对不对？ 这将是坏的。 所以，让我们来看看，这个家伙。 

有关列表的其他坏事，而数组 我们只是有自己的堆栈彼此的所有元素， 在这里，我们也介绍了这个指针。 因此，有一个额外的内存块，我们使用 对于每一个元素，我们要存储在我们的名单。 我们得到的灵活性，但它是有代价的。 它配备了这个时间成本， ，它与此内存成本。 时间在这个意义上，我们现在必须在数组中的每个元素 找到在索引10中的一个，或者说，将有在一个数组中的索引10。 

真的很快，当我们图的这些名单， 通常我们认为在头部的列表或列表中的第一个指针 注意，这是一个真正的指针。 它只有4个字节。它本身不是一个实际的节点。 所以你看它有没有int值，没有next指针。 它实际上只是一个指针。 它要指向的东西，是一个实际的节点结构。 [三]一个指针，称为节点？ >>这是 - 没有。这是一个指向某种类型的节点。 它是一个指针的节点结构。哦，没关系。 图上的左，右侧列表符号。 我们可以将其设置为null，这是一个很好的方式开始。 当你图它，你要么写为空或通过它，你放了行这样的。 

使用列表的最简单的方法之一， ，我们要求你都前置和追加到两者之间的差异， 但在前面加上是肯定更容易。 当你在前面加上，这就是你的 - 当你预定（7） 你去创建节点结构 设置第一个指向它，因为现在，因为我们前面加上它， 它要在列表的开头。 如果我们预定（3），，创建另一个节点，但现在前7。 因此，我们本质上推动我们的名单上。 现在，你可以看到前置，有时人们把它推， 因为你推到你的列表中一个新的元素。 在前面的列表中删除它也很容易。 所以，人们往往会调用该弹出。 以这种方式，你可以模拟一个堆栈使用链表。 哎呀。很抱歉，现在我们正在为追加。所以，我们在这里前缀（7），现在我们预定（3）。 如果我们预先考虑别的东西到这个列表中，（4），如果我们预先考虑 然后，我们有4个，然后3，然后7。 那么我们就可以弹出并删除，删除，删除7。 通常情况下，更直观的方式来思考这个是附加的。 所以，我图表示出来，它看起来像什么与附加在这里。 在这里，追加（7）不看有什么不同 因为只有一个列表中的元素。 并追加（3）将它结束。 也许你可以看到现在的诀窍追加 是因为我们只知道该从哪里开始的列表， 要追加到一个列表，在列表中，你必须走一路 去年底，停止，然后建立您的节点，和普拉克一切的下降。 连接所有的东西。 因此，前置，作为我们只是洞穿这真的很快， 当你预先准备的列表，这是相当简单的。 

你让你的新节点，涉及到一些动态内存分配。 所以，在这里，我们正在做一个节点使用malloc的结构。 所以malloc的，我们正在使用的，因为这会为我们预留内存后 因为我们不希望这样 - 我们希望这记忆将持续很长一段时间。 我们得到了一个指针，我们只是分配的内存空间。 我们使用的节点的大小，我们不总结的领域。 我们不手动生成的字节数， 相反，我们使用sizeof，让我们知道我们得到适当的字节数。 我们一定要测试我们的malloc调用成功。 这是你想要做的一般。 在现代化的机器上，运行内存不足是不是一件容易 除非你分配一吨的东西，使一个巨大的名单， 但是，如果你的东西，比如说，像iPhone或Android， 你只有有限的内存资源，特别是如果你正在做的事情激烈。 所以这是很好的实践。 

请注意，我在这里已经使用了几个不同的功能 您已经看到了，是种新的。 因此，fprintf同于printf 除了它的第一个参数是你要打印其中的流。 在这种情况下，我们要打印到标准错误字符串 这是从标准outstream不同。 默认情况下，它显示了在同一个地方。 它也打印到​​终端，但你可以 -  使用这些命令，您了解，重定向技术 您了解了在托米的视频，你可以直接问题集4 不同的区域，然后退出，在这里，你的程序退出。 它本质上就像是从main返回， 除了我们使用exit因为这里的利润不会做任何事情。 我们不是主要的，因此返回不退出程序，像我们希望的。 因此，我们使用exit函数，并给它一个错误代码。 那么在这里我们设置新节点的值字段，其i现场等于我，然后我们其连接。 我们设置新节点的next指针指向第一， 那么首先将指向新的节点。 这些第一行代码中，我们实际上是在建立新的节点。 不是最后两行的这个功能，但第一的。 实际上，你可以拉成一个函数，一个辅助函数。 这通常我做什么，我拉出来的功能， 我把它类似于构建节点， 的前置功能保持相当小，仅有3行，然后。 我打电话到我的体型节点的功能，然后我线的一切行动。 

最后一点，我想告诉你， 我会让你做追加和自己的， 是如何遍历列表。 还有一堆不同的方法来遍历列表。 在这种情况下，我们要找到一个列表的长度。 因此，我们从长度= 0。 这是非常类似于写strlen的一个字符串。 这就是我要告诉你，这个循环在这里。 它看起来有点古怪，它不是一般的INT I = 0，我不管，我+ +。 相反，它的初始化我们的变量n的列表开始。 然后，我们的迭代变量不为空，我们继续前进。 这是因为，按照惯例，我们的名单将是无效的。 然后递增，而不是做+ +， 链表相当于+ +是n =正 - >下一个。 

我会让你填写在这里的差距，因为我们没时间了。 但记住这一点，当你在你的spellr的pset。 链表，如果你正在实现一个哈希表， 一定会非常方便。 这个成语循环的事情，使生活变得更加简单，希望。 如有任何疑问，速度够快吗？ [三]你会发出完成的SLL和SC？ [哈迪森]是啊。我会发出完成幻灯片和SLL协议栈和queue.cs的。 [CS50.TV]