[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]