1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [第6条：不太舒服]

2
00:00:02,730 --> 00:00:05,040
内特 - 哈迪森] [哈佛大学]

3
00:00:05,040 --> 00:00:07,320
这是CS50。[CS50.TV]

4
00:00:07,320 --> 00:00:11,840
好的。第6节。

5
00:00:11,840 --> 00:00:14,690
这个星期，我们将要讨论关于数据结构的部分，

6
00:00:14,690 --> 00:00:19,780
这主要是因为这周的问题上设置spellr

7
00:00:19,780 --> 00:00:24,410
做了一大堆不同的数据结构探索。

8
00:00:24,410 --> 00:00:26,520
有一堆不同的方式，你可以去的问题集中，

9
00:00:26,520 --> 00:00:31,570
和更多的数据结构，你知道的，你可以做很酷的事情。

10
00:00:31,570 --> 00:00:34,990
>> 因此，让我们开始吧。首先，我们要谈栈，

11
00:00:34,990 --> 00:00:37,530
栈和队列的数据结构，我们要谈的。

12
00:00:37,530 --> 00:00:40,560
栈和队列是非常有用的，当我们开始谈论图形，

13
00:00:40,560 --> 00:00:44,390
我们不打算现在做这么多的权利。

14
00:00:44,390 --> 00:00:52,820
但他们真的很好理解的一个大的基本数据结构的CS。

15
00:00:52,820 --> 00:00:54,880
问题集规范中的描述，

16
00:00:54,880 --> 00:00:59,260
如果你拉了起来，谈论类似于堆栈的

17
00:00:59,260 --> 00:01:05,239
桩，你必须在食堂，在食堂用餐托盘

18
00:01:05,239 --> 00:01:09,680
在那里，当在餐厅的工作人员来了，放出来后，他们已经清理了他们的用餐托盘，

19
00:01:09,680 --> 00:01:12,000
他们叠上其他顶级之一。

20
00:01:12,000 --> 00:01:15,050
然后，当孩子们在食物中获得，

21
00:01:15,050 --> 00:01:19,490
他们拉盘，先顶一个，然后它下面的一个，然后是下一个。

22
00:01:19,490 --> 00:01:25,190
所以，实际上，第一盘，就餐人员放下是最后一个被采取关闭。

23
00:01:25,190 --> 00:01:32,330
，餐厅工作人员把最后一个是第一个被关闭晚餐。

24
00:01:32,330 --> 00:01:38,100
在这个问题集的规格，您可以下载，如果你还没有的话，

25
00:01:38,100 --> 00:01:46,730
我们谈论建模堆栈中的数据的金盏使用这种结构。

26
00:01:46,730 --> 00:01:51,070
>> 因此，我们有什么，这是什么，提出了在课堂上，

27
00:01:51,070 --> 00:01:58,120
除了在课堂上，我们提出了这个int类型，而不是为char *。

28
00:01:58,120 --> 00:02:06,250
这将是一个堆叠中储存？

29
00:02:06,250 --> 00:02:09,009
丹尼尔？什么是存储在栈？

30
00:02:09,009 --> 00:02:15,260
[丹尼尔]字符串？ >>我们的字符串存储在栈，准确。

31
00:02:15,260 --> 00:02:20,950
你需要有以创建一个堆栈是一个数组

32
00:02:20,950 --> 00:02:23,920
一个特定的容量，在这种情况下，

33
00:02:23,920 --> 00:02:28,020
能力将是全部大写，因为它是一个常数。

34
00:02:28,020 --> 00:02:36,340
然后在除了阵列，我们需要跟踪的是电流大小的数组。

35
00:02:36,340 --> 00:02:38,980
这里有一点要注意这是一种很酷

36
00:02:38,980 --> 00:02:47,060
是，我们正在创造的堆积之上的另一种数据结构，数组的数据结构。

37
00:02:47,060 --> 00:02:50,110
有不同的方法来实现栈。

38
00:02:50,110 --> 00:02:54,250
我们不会做还相当，但希望做链表的问题后，

39
00:02:54,250 --> 00:03:00,520
你会看到，你可以很容易地实现一个栈的链表。

40
00:03:00,520 --> 00:03:02,640
但现在，我们将坚持到阵列。

41
00:03:02,640 --> 00:03:06,350
所以，再一次，所有我们需要的是一个数组，我们只需要跟踪数组的大小。

42
00:03:06,350 --> 00:03:09,850
[三]对不起，那你为什么说堆栈的顶部的字符串？

43
00:03:09,850 --> 00:03:13,440
对我来说，似乎，像字符串是在栈。

44
00:03:13,440 --> 00:03:16,790
[哈迪森]是啊。我们正在创造的，我们正在做我们的数组的数据结构 - 

45
00:03:16,790 --> 00:03:22,130
这是一个很大的问题。所以，问题是，谁是看这个网上的人，

46
00:03:22,130 --> 00:03:24,140
为什么我们说堆栈顶部的字符串，

47
00:03:24,140 --> 00:03:27,990
因为在这里它看起来像两个字符串里面的堆栈吗？

48
00:03:27,990 --> 00:03:31,050
这是完全的情况下。

49
00:03:31,050 --> 00:03:34,660
我指的是，我们已经有一个数组的数据结构。

50
00:03:34,660 --> 00:03:39,290
我们已经得到的char *数组，这个数组的字符串，

51
00:03:39,290 --> 00:03:45,300
我们要加至，以创建数据结构的层叠。

52
00:03:45,300 --> 00:03:48,620
>> 因此，一个堆栈比数组稍微更复杂。

53
00:03:48,620 --> 00:03:51,890
我们可以使用一个数组来建立一个堆栈。

54
00:03:51,890 --> 00:03:55,810
所以这就是我们说的堆栈是建立在一个阵列的顶部。

55
00:03:55,810 --> 00:04:02,510
同样，正如我前面所说，我们可以建立一个堆栈上的链表。

56
00:04:02,510 --> 00:04:04,960
而不是使用一个数组来保存我们的元素，

57
00:04:04,960 --> 00:04:10,070
我们可以使用一个链表来保持我们的元素，并建立堆栈左右，。

58
00:04:10,070 --> 00:04:12,420
让我们通过几个例子，看一些代码，

59
00:04:12,420 --> 00:04:14,960
看看这里发生的一切。

60
00:04:14,960 --> 00:04:23,400
在左边的，我扔了下来，堆栈结构看起来就像在内存中

61
00:04:23,400 --> 00:04:28,330
如果能力在＃定义为4。

62
00:04:28,330 --> 00:04:33,490
我们有我们的四元素的char *数组。

63
00:04:33,490 --> 00:04:38,110
我们已经有了字符串[0]字符串[1]，字符串[2]，字符串[3]，

64
00:04:38,110 --> 00:04:43,800
然后就是最后我们的空间大小的整数。

65
00:04:43,800 --> 00:04:46,270
这有意义吗？好吧。

66
00:04:46,270 --> 00:04:48,790
这是发生什么，如果我做什么的权利，

67
00:04:48,790 --> 00:04:55,790
这将是我的代码，只需要声明一个结构，称为s的堆叠结构。

68
00:04:55,790 --> 00:05:01,270
这就是我们所得到的。它规定了这占用内存中。

69
00:05:01,270 --> 00:05:05,590
这里的第一个问题是，该堆栈结构的内容是什么？

70
00:05:05,590 --> 00:05:09,250
现在他们什么都不是，但不是完全没有。

71
00:05:09,250 --> 00:05:13,300
他们这种垃圾。我们不知道是什么。

72
00:05:13,300 --> 00:05:17,000
当我们宣布栈S，我们仅仅是用下来的内存上。

73
00:05:17,000 --> 00:05:19,840
这是一种类似于声明INT I，而不是初始化它。

74
00:05:19,840 --> 00:05:21,730
你不知道有什么可以做的。你可以在那里读什么，

75
00:05:21,730 --> 00:05:27,690
但它可能不会是有帮助的。

76
00:05:27,690 --> 00:05:32,680
你要永远记住做的一件事是初始化任何需要被初始化。

77
00:05:32,680 --> 00:05:35,820
在这种情况下，我们要初始化的大小是零，

78
00:05:35,820 --> 00:05:39,960
因为那将是对我们非常重要。

79
00:05:39,960 --> 00:05:43,450
我们可以继续前进，初始化的指针，所有的char * S，

80
00:05:43,450 --> 00:05:49,670
一些可以理解的价值，可能为null。

81
00:05:49,670 --> 00:05:58,270
但它不是完全必要的，我们做到这一点。

82
00:05:58,270 --> 00:06:04,200
>> 现在，这两个主要操作栈是什么？

83
00:06:04,200 --> 00:06:07,610
有人还记得演讲一摞摞你做了什么？是吗？

84
00:06:07,610 --> 00:06:09,700
[斯特拉入栈和出栈？ “没错。

85
00:06:09,700 --> 00:06:13,810
入栈和出栈的两个主要操作栈。

86
00:06:13,810 --> 00:06:17,060
推做什么？ >>它把东西到顶部

87
00:06:17,060 --> 00:06:19,300
栈，然后大跌眼镜把它关闭。

88
00:06:19,300 --> 00:06:23,150
[哈迪森没错。因此，推，推压在堆栈的顶部上的东西。

89
00:06:23,150 --> 00:06:27,700
这就像在餐厅工作人员的用餐托盘放在柜台上。

90
00:06:27,700 --> 00:06:33,630
大跌眼镜的是一个餐盘堆栈。

91
00:06:33,630 --> 00:06:36,460
让我们通过一对夫妇的例子发生了什么

92
00:06:36,460 --> 00:06:39,720
当我们事情推入堆栈。

93
00:06:39,720 --> 00:06:45,110
如果我们推到我们的堆栈字符串'hello'，

94
00:06:45,110 --> 00:06:49,760
这是我们的图现在是什么样子。

95
00:06:49,760 --> 00:06:53,410
看看会发生什么？

96
00:06:53,410 --> 00:06:56,530
我们推入我们的字符串数组的第一个元素

97
00:06:56,530 --> 00:07:01,420
我们调升我们的规模数为1。

98
00:07:01,420 --> 00:07:05,340
因此，如果我们看两个幻灯片之间的区别，在这里为0，前推。

99
00:07:05,340 --> 00:07:08,690
这里是后推。

100
00:07:08,690 --> 00:07:13,460
前推，后推。

101
00:07:13,460 --> 00:07:16,860
现在，我们有我们的栈中的一个元素。

102
00:07:16,860 --> 00:07:20,970
这是字符串“hello”，这就是它。

103
00:07:20,970 --> 00:07:24,440
一切，在我们的字符串数组，数组中的垃圾。

104
00:07:24,440 --> 00:07:27,070
我们没有初始化它。

105
00:07:27,070 --> 00:07:29,410
比方说，我们推进另一个字符串到我们的堆栈。

106
00:07:29,410 --> 00:07:32,210
我们要推动“世界”这个时间。

107
00:07:32,210 --> 00:07:35,160
所以，你可以看到这里的“世界”顶部的“hello”，

108
00:07:35,160 --> 00:07:40,040
和的大小计数上升到2。

109
00:07:40,040 --> 00:07:44,520
现在，我们可以把“CS50”，那将再次走在上面。

110
00:07:44,520 --> 00:07:51,110
如果我们回去吧，你可以看到我们如何推动事情的堆栈的顶部。

111
00:07:51,110 --> 00:07:53,320
现在，我们得到流行。

112
00:07:53,320 --> 00:07:58,910
当我们弹出的堆栈的东西，这是怎么回事？

113
00:07:58,910 --> 00:08:01,540
任何人看到其中的差别吗？这是很微妙的。

114
00:08:01,540 --> 00:08:05,810
[学生]的大小。 “是的，变化的大小。

115
00:08:05,810 --> 00:08:09,040
>> 你还有什么改变？

116
00:08:09,040 --> 00:08:14,280
[学生]中的字符串。 “没错。的字符串。

117
00:08:14,280 --> 00:08:17,110
事实证明，当你做它，这样一来，

118
00:08:17,110 --> 00:08:21,960
因为我们还没有的元素复制到我们的堆栈，

119
00:08:21,960 --> 00:08:24,670
我们其实并不需要做什么，我们就可以使用的大小

120
00:08:24,670 --> 00:08:28,630
跟踪的一些事情在我们的数组

121
00:08:28,630 --> 00:08:33,780
所以，当我们再次弹出，再次我们只是我们的规模递减下降到1。

122
00:08:33,780 --> 00:08:39,440
有没有必要去和覆盖任何东西。

123
00:08:39,440 --> 00:08:41,710
一种时髦的。

124
00:08:41,710 --> 00:08:46,520
事实证明，我们通常只是离开的事情，因为这是我们做的工作的。

125
00:08:46,520 --> 00:08:50,060
如果我们不回去，覆盖的东西，那么为什么这样做？

126
00:08:50,060 --> 00:08:54,150
所以，当我们的堆栈，弹出两次的，它是递减的大小了几次。

127
00:08:54,150 --> 00:08:59,120
再次，这仅仅是因为我们并没有复制的东西到我们的堆栈。

128
00:08:59,120 --> 00:09:01,320
是吗？来吧。

129
00:09:01,320 --> 00:09:04,460
不知所云] >> [学生，然后会发生什么，当你把东西了吗？

130
00:09:04,460 --> 00:09:08,570
当你再次推的东西，它在哪里去了？

131
00:09:08,570 --> 00:09:12,390
到哪里去了，瓦西里？ >>转换成字符串[1]？ “没错。

132
00:09:12,390 --> 00:09:14,530
它为什么不进入字符串[3]？

133
00:09:14,530 --> 00:09:19,410
因为它忘记了，有什么字符串中的[罗勒] [1] [2]？

134
00:09:19,410 --> 00:09:24,040
[哈迪森没错。我们的栈，从本质上讲，“忘了”，这是到什么

135
00:09:24,040 --> 00:09:29,480
[1]中的字符串或字符串[2]，因此，当我们把“活泉”，

136
00:09:29,480 --> 00:09:36,670
它只是将字符串[1]的元素。

137
00:09:36,670 --> 00:09:41,590
是否有任何问题，这是如何工作的，在一个基本的水平呢？

138
00:09:41,590 --> 00:09:45,160
[三]因此，这是不以任何方式，在动态方面的金额

139
00:09:45,160 --> 00:09:47,620
或条款的堆栈大小？

140
00:09:47,620 --> 00:09:56,750
[哈迪森没错。这是 - 这一点，这是不是一个动态growning的堆栈。

141
00:09:56,750 --> 00:10:02,850
这是一个堆栈，可容纳最多4的char *，最多四件事情。

142
00:10:02,850 --> 00:10:07,580
如果我们试图和推动五分之一的事情，你认为应该发生的吗？

143
00:10:07,580 --> 00:10:11,870
[学生，不知所云]

144
00:10:11,870 --> 00:10:14,600
[哈迪森没错。有一些事情会发生。

145
00:10:14,600 --> 00:10:19,330
它可能会段错误，这取决于我们什么 - 

146
00:10:19,330 --> 00:10:22,530
我们究竟是如何实现的后端。

147
00:10:22,530 --> 00:10:31,740
它可以覆盖。它可以有，我们在课堂上谈到，缓冲区溢出。

148
00:10:31,740 --> 00:10:35,240
什么是最明显的事情，可能会被覆盖

149
00:10:35,240 --> 00:10:42,370
如果我们试图把一个额外的东西，我们的堆栈吗？

150
00:10:42,370 --> 00:10:44,550
所以你提到的缓冲区溢出。

151
00:10:44,550 --> 00:10:47,870
可能被写入或出丑的事情是什么

152
00:10:47,870 --> 00:10:52,320
如果我们溢出意外试图把一个额外的东西吗？

153
00:10:52,320 --> 00:10:54,730
[丹尼尔，不知所云] >>可能。

154
00:10:54,730 --> 00:10:58,440
但在最初，可能会发生什么？如果我们试图把四分之一的事情吗？

155
00:10:58,440 --> 00:11:06,220
它可能会覆盖的大小，至少，我们已经有了这个内存图。

156
00:11:06,220 --> 00:11:10,880
>> 在这个问题中集规范，这就是我们将要实施的今天，

157
00:11:10,880 --> 00:11:16,030
我们做想做的事，只是返回false。

158
00:11:16,030 --> 00:11:20,030
我们的push方法会返回一个布尔值，

159
00:11:20,030 --> 00:11:22,920
和布尔值是true，如果成功推

160
00:11:22,920 --> 00:11:29,730
假的，如果我们不能把任何东西更多，因为堆栈是满的。

161
00:11:29,730 --> 00:11:33,620
让我们通过一点点的代码。

162
00:11:33,620 --> 00:11:36,400
下面是我们的推送功能。

163
00:11:36,400 --> 00:11:40,380
我们的推送功能的堆栈中的字符串放到栈中。

164
00:11:40,380 --> 00:11:45,820
这将返回true，如果该字符串被成功地推

165
00:11:45,820 --> 00:11:51,820
在堆栈，否则返回false。

166
00:11:51,820 --> 00:11:59,740
什么可能是一个良好的第一件事就是在这里做的任何建议吗？

167
00:11:59,740 --> 00:12:20,630
[三]如果大小等于能力，那么返回假的？

168
00:12:20,630 --> 00:12:23,320
[哈迪森]宾果游戏。尼斯的工作。

169
00:12:23,320 --> 00:12:26,310
如果大小的能力，我们将返回false。

170
00:12:26,310 --> 00:12:29,270
我们不能把任何东西在我们的堆栈。

171
00:12:29,270 --> 00:12:36,900
否则，我们要放东西的堆栈的顶部。

172
00:12:36,900 --> 00:12:41,670
“堆栈的顶部，”最初是什么？

173
00:12:41,670 --> 00:12:43,650
[丹尼尔]大小为0？大小为0。

174
00:12:43,650 --> 00:12:49,990
后，有一件事在堆栈中的堆栈的顶部是什么？大小姐，你知道吗？

175
00:12:49,990 --> 00:12:52,720
[大小姐]。 >>尺寸是的，没错。不断增加的大小，

176
00:12:52,720 --> 00:13:01,690
每次你把新的元素在数组中的索引大小。

177
00:13:01,690 --> 00:13:05,470
我们可以做这样的一个班轮，如果是有道理的。

178
00:13:05,470 --> 00:13:11,910
所以，我们有我们的字符串数组，我们要访问它的规模指数，

179
00:13:11,910 --> 00:13:14,780
我们只是在那里来存储我们的char *。

180
00:13:14,780 --> 00:13:19,340
请注意有没有字符串复制在这里，

181
00:13:19,340 --> 00:13:29,680
没有动态分配的内存？

182
00:13:29,680 --> 00:13:34,440
然后大小姐带来了什么，我们现在要做的，

183
00:13:34,440 --> 00:13:40,570
因为我们的字符串存储在阵列中的适当位置，

184
00:13:40,570 --> 00:13:49,230
她说，我们的规模递增，所以我们已经准备好为未来推。

185
00:13:49,230 --> 00:13:53,950
因此，我们可以做到这一点，与s.size + +。

186
00:13:53,950 --> 00:13:59,330
在这一点上，我们已经被推到我们的数组。我们必须做的最后一件事情是什么？

187
00:13:59,330 --> 00:14:10,110
[学生]：返回true。 >>返回true。

188
00:14:10,110 --> 00:14:14,690
因此，它是非常简单的，一个非常简单的代码。不太多。

189
00:14:14,690 --> 00:14:17,070
一旦你已经包裹着你的头周围的堆栈是如何工作的，

190
00:14:17,070 --> 00:14:21,910
这是非常简单的实现。

191
00:14:21,910 --> 00:14:26,390
>> 现在，下一个的一部分，这是一个字符串关闭堆栈弹出。

192
00:14:26,390 --> 00:14:29,410
我想给你们一些时间来工作，这是一个有点。

193
00:14:29,410 --> 00:14:34,320
这几乎是本质上是相反的我们做了什么在推动。

194
00:14:34,320 --> 00:14:38,510
我所做的其实是 - 哎呀。

195
00:14:38,510 --> 00:14:48,160
我已经启动的器具，在这里，在家电，

196
00:14:48,160 --> 00:14:53,600
我拉起的设置5规范的问题。

197
00:14:53,600 --> 00:15:02,560
如果我们放大在这里，我们可以看到我在cdn.cs50.net/2012/fall/psets/pset5.pdf。

198
00:15:02,560 --> 00:15:08,590
你们下载的代码，设在这里，section6.zip？

199
00:15:08,590 --> 00:15:15,030
好的。如果你还没有这样做，这样做，现在，真的很快。

200
00:15:15,030 --> 00:15:22,130
我会做到这一点在我的终端窗口。

201
00:15:22,130 --> 00:15:25,090
其实，我在这里做了。是啊。

202
00:15:25,090 --> 00:15:34,730
是的，山姆？ >>我有一个问题，你为什么说s.string的括号内的大小= STR？

203
00:15:34,730 --> 00:15:42,910
STR是什么？的是，以前在什么地方，或 - 哦，在char *海峡？

204
00:15:42,910 --> 00:15:47,160
[哈迪森]是的，没错。这是的说法。哦，没关系。抱歉。

205
00:15:47,160 --> 00:15:49,470
[哈迪森我们指定的字符串推入。

206
00:15:49,470 --> 00:15:55,220
其他可能遇到的问题，我们并没有真正在这里谈论的是

207
00:15:55,220 --> 00:15:58,810
我们想当然的，我们有这个变量称为s

208
00:15:58,810 --> 00:16:02,710
这是在范围和访问。

209
00:16:02,710 --> 00:16:06,960
我们采取理所当然地认为是这个堆栈结构。

210
00:16:06,960 --> 00:16:08,930
所以回头看这推的代码，

211
00:16:08,930 --> 00:16:13,450
你可以看到，我们正在做的东西与这个字符串的时候传递

212
00:16:13,450 --> 00:16:19,210
但随后突然，我们访问s.size，如，走到哪儿呢？

213
00:16:19,210 --> 00:16:23,020
在代码中，我们要看看在一节中的存档

214
00:16:23,020 --> 00:16:27,100
然后设置的东西，你会做你的问题，

215
00:16:27,100 --> 00:16:32,440
我们已经取得了我们的协议栈结构的一个全局变量

216
00:16:32,440 --> 00:16:36,380
这样我们就可以访问它，在我们所有的不同的功能

217
00:16:36,380 --> 00:16:40,630
而无需手动传递它，并通过它的参考，

218
00:16:40,630 --> 00:16:44,870
做所有这类的东西。

219
00:16:44,870 --> 00:16:52,280
我们只是骗了一点点，如果你愿意，让事情变得更好的。

220
00:16:52,280 --> 00:16:57,430
这就是我们在这里做的东西，因为它的乐趣，它更容易。

221
00:16:57,430 --> 00:17:02,800
通常情况下，你会看到人们这样做，如果他们有一个很大的数据结构

222
00:17:02,800 --> 00:17:07,750
在他们的程序中的操作。

223
00:17:07,750 --> 00:17:09,560
>> 让我们回到的设备。

224
00:17:09,560 --> 00:17:15,240
每个人都成功地得到section6.zip？

225
00:17:15,240 --> 00:17:20,440
每个人都将它解压缩使用解压缩section6.zip？

226
00:17:20,440 --> 00:17:27,200
如果你进入第6节目录 - 

227
00:17:27,200 --> 00:17:29,220
AAH，所有的地方 - 

228
00:17:29,220 --> 00:17:32,840
和你列出在这里，你看，你有三个不同的c文件。

229
00:17:32,840 --> 00:17:38,350
你有一个队列中，SLL，这是单链表，和堆栈。

230
00:17:38,350 --> 00:17:44,600
如果你打开​​stack.c，

231
00:17:44,600 --> 00:17:47,330
你可以看到，我们已经为我们定义了这个结构，

232
00:17:47,330 --> 00:17:51,330
确切的结构，我们刚才讲的幻灯片中。

233
00:17:51,330 --> 00:17:56,340
我们已经得到了我们的全局变量的堆栈，

234
00:17:56,340 --> 00:18:00,110
我们已经得到了我们的推送功能，

235
00:18:00,110 --> 00:18:04,230
然后我们有我们的流行功能。

236
00:18:04,230 --> 00:18:08,320
我会把代码的推背在幻灯片上，

237
00:18:08,320 --> 00:18:10,660
但我想你们做的是，尽你的能力，

238
00:18:10,660 --> 00:18:13,790
去实现弹出的功能。

239
00:18:13,790 --> 00:18:18,480
一旦你实现了它，你就可以编译使堆栈，

240
00:18:18,480 --> 00:18:22,540
然后运行生成的可执行堆栈，

241
00:18:22,540 --> 00:18:28,390
将运行所有测试代码在这里，在主。

242
00:18:28,390 --> 00:18:31,060
主要负责的实际push和pop调用

243
00:18:31,060 --> 00:18:33,220
，确保一切通过所有权利。

244
00:18:33,220 --> 00:18:36,820
它也初始化堆栈的大小在这里

245
00:18:36,820 --> 00:18:39,780
所以你不必担心初始化该。

246
00:18:39,780 --> 00:18:42,310
你可以假设它被正确初始化

247
00:18:42,310 --> 00:18:48,000
的时候，你访问它，在弹出的功能。

248
00:18:48,000 --> 00:18:53,530
这是否有意义吗？

249
00:18:53,530 --> 00:19:00,100
所以，在这里，我们走了。有“推”的代码。

250
00:19:00,100 --> 00:19:13,210
我给你们5分钟或10分钟。

251
00:19:13,210 --> 00:19:15,690
如果你有任何问题，在此期间，当你编码，

252
00:19:15,690 --> 00:19:17,710
请大声问他们。

253
00:19:17,710 --> 00:19:23,080
所以，如果你得到一个棘手的问题，就问我。

254
00:19:23,080 --> 00:19:26,030
让我知道，让其他人知道。

255
00:19:26,030 --> 00:19:28,160
工作与你的邻居了。

256
00:19:28,160 --> 00:19:30,360
[丹尼尔]我们只是实现POP现在好了吗？ >>只是弹出。

257
00:19:30,360 --> 00:19:34,200
虽然你可以推，如果你想复制的实施

258
00:19:34,200 --> 00:19:37,780
使测试工作。

259
00:19:37,780 --> 00:19:41,940
因为它是难以测试的东西进入 - 

260
00:19:41,940 --> 00:19:49,030
或者，这是很难测试弹出堆栈出来的东西，如果没有任何堆栈中开始。

261
00:19:49,030 --> 00:19:55,250
>> 流行音乐应该是返回是什么？从堆栈顶部的元素。

262
00:19:55,250 --> 00:20:01,260
它应该得到元素的堆栈的顶部

263
00:20:01,260 --> 00:20:05,780
然后递减堆栈的大小，

264
00:20:05,780 --> 00:20:07,810
现在你已经失去了元素的顶部。

265
00:20:07,810 --> 00:20:11,420
然后返回的元素在上面。

266
00:20:11,420 --> 00:20:20,080
[学生，不知所云]

267
00:20:20,080 --> 00:20:28,810
[哈迪森]所以，如果你这样做，会发生什么？ [学生，不知所云]

268
00:20:28,810 --> 00:20:34,000
最终发生的是什么，你可能访问任何

269
00:20:34,000 --> 00:20:37,350
尚未初始化的元素，所以你的计算

270
00:20:37,350 --> 00:20:39,990
最后一个元素是处于关闭状态。

271
00:20:39,990 --> 00:20:46,260
所以在这里，如果你注意到，在推，我们访问在s.size元素的字符串

272
00:20:46,260 --> 00:20:48,560
因为它是一个新的索引。

273
00:20:48,560 --> 00:20:51,460
这是新的堆栈的顶部。

274
00:20:51,460 --> 00:21:01,100
而在流行音乐，s.size将是下一个空格，

275
00:21:01,100 --> 00:21:05,210
空间的所有元素在堆栈的顶部。

276
00:21:05,210 --> 00:21:10,050
因此，最顶端的元素是不在s.size，

277
00:21:10,050 --> 00:21:14,930
但相反，它是在它下面。

278
00:21:14,930 --> 00:21:19,640
>> 其他的事情，当你 - 在弹出

279
00:21:19,640 --> 00:21:22,030
你有递减的大小。

280
00:21:22,030 --> 00:21:28,750
如果你还记得我们的小图就在这里，

281
00:21:28,750 --> 00:21:30,980
真的，只有我们看到了发生的事情，当我们调用pop

282
00:21:30,980 --> 00:21:36,150
是，这个尺寸下降，第一至第2，然后为1。

283
00:21:36,150 --> 00:21:42,620
然后，当我们把一个新的元素，它会继续在适当的位置。

284
00:21:42,620 --> 00:21:49,610
罗勒如果s.size 2，然后将它的元素，

285
00:21:49,610 --> 00:21:54,400
，然后你要弹出该元素吗？

286
00:21:54,400 --> 00:21:59,510
因此，如果我们去了 - “”所以，让我们再看看这个。

287
00:21:59,510 --> 00:22:07,730
如果这是我们在这一点上堆

288
00:22:07,730 --> 00:22:12,130
我们称之为流行，

289
00:22:12,130 --> 00:22:16,150
指数是最上面的元素吗？

290
00:22:16,150 --> 00:22:19,300
[罗勒] 2，但它是怎么回事，弹出3。 “没错。

291
00:22:19,300 --> 00:22:24,220
所以这就是我们的规模是3，但我们要流行的元素，索引2处。

292
00:22:24,220 --> 00:22:29,900
这是典型的种关闭的，你有零的数组索引。

293
00:22:29,900 --> 00:22:36,430
所以，你要弹出的第三个元素，但第三个元素是不是在索引3。

294
00:22:36,430 --> 00:22:39,430
原因我们没有做到这一点减1，当我们正在推动

295
00:22:39,430 --> 00:22:44,120
是因为现在，你注意到最上面的元素，

296
00:22:44,120 --> 00:22:47,600
如果此时我们推入堆栈别的，

297
00:22:47,600 --> 00:22:50,360
我们希望将它在索引3。

298
00:22:50,360 --> 00:23:03,550
它只是发生的大小和排队的指数，当你推。

299
00:23:03,550 --> 00:23:06,960
>> 谁拥有一个工作栈的实现？

300
00:23:06,960 --> 00:23:09,690
你已经有了一个工作中的堆叠。你有没有流行的工作吗？

301
00:23:09,690 --> 00:23:11,890
丹尼尔：是的。我是这么认为的。

302
00:23:11,890 --> 00:23:14,610
>>程序的运行，而不是段的断层，它打印出来吗？

303
00:23:14,610 --> 00:23:17,520
它打印出来的“成功”，当你运行它呢？

304
00:23:17,520 --> 00:23:22,630
是啊。叠加，运行它，如果它打印出的“成功”，不繁荣，

305
00:23:22,630 --> 00:23:26,000
然后，所有的好。

306
00:23:26,000 --> 00:23:34,070
好的。让我们的设备真的很快，

307
00:23:34,070 --> 00:23:46,100
我们将步行通过。

308
00:23:46,100 --> 00:23:51,110
如果我们看一下这是怎么回事在这里的流行音乐，

309
00:23:51,110 --> 00:23:55,220
丹尼尔，究竟是什么做的第一件事，你呢？

310
00:23:55,220 --> 00:23:58,850
[丹尼尔]如果s.size是大于0。

311
00:23:58,850 --> 00:24:03,120
[哈迪森]好吧。你为什么这样做呢？

312
00:24:03,120 --> 00:24:05,610
[丹尼尔]为了确保堆栈中，有一种内在的东西。

313
00:24:05,610 --> 00:24:10,950
[哈迪森权。你想进行测试，以确保，s.size大于0;

314
00:24:10,950 --> 00:24:13,280
否则，你有什么要发生吗？

315
00:24:13,280 --> 00:24:16,630
[丹尼尔]返回空值吗？ >>返回NULL，准确。

316
00:24:16,630 --> 00:24:20,740
因此，如果s.size是大于0。那么什么是我们该怎么办？

317
00:24:20,740 --> 00:24:25,890
如果堆栈不为空，我们该怎么办？

318
00:24:25,890 --> 00:24:31,210
[斯特拉]递减的大小吗？ >>您递减的大小，还行。

319
00:24:31,210 --> 00:24:34,440
所以，你是怎么做到这一点呢？ >> s.size  - 。

320
00:24:34,440 --> 00:24:37,030
[哈迪森大。然后你做了什么？

321
00:24:37,030 --> 00:24:44,140
[斯特拉然后我说回s.string [s.size]。

322
00:24:44,140 --> 00:24:48,560
[哈迪森大。

323
00:24:48,560 --> 00:24:51,940
否则返回null。是的，山姆？

324
00:24:51,940 --> 00:24:55,510
[三]为什么不需要s.size的+ 1？

325
00:24:55,510 --> 00:24:58,430
[哈迪森]加1？ >>呀。 “知道了。

326
00:24:58,430 --> 00:25:00,980
[三]我想因为你正在服用1个输出，

327
00:25:00,980 --> 00:25:04,290
然后你要回来，他们要求的不是一个。

328
00:25:04,290 --> 00:25:09,400
哈迪森而这正是我们在谈论这个问题的0指数。

329
00:25:09,400 --> 00:25:11,380
因此，如果我们在这里放大。

330
00:25:11,380 --> 00:25:15,650
如果我们看一下这家伙在这里，你可以看到，当我们弹出，

331
00:25:15,650 --> 00:25:19,340
我们在弹出的元素索引2处。

332
00:25:19,340 --> 00:25:25,200
>> 因此，我们减少我们的规模，我们的规模符合我们的索引中。

333
00:25:25,200 --> 00:25:39,650
如果我们不递减的大小，那么我们需要做的大小，-1，然后递减。

334
00:25:39,650 --> 00:25:45,270
大。所有的好？

335
00:25:45,270 --> 00:25:47,530
在此有任何疑问？

336
00:25:47,530 --> 00:25:54,050
有许多不同的方式来写这个问题，以及。

337
00:25:54,050 --> 00:26:03,290
事实上，我们可以做一些事情，甚至 - 我们可以做一个班轮。

338
00:26:03,290 --> 00:26:05,770
我们可以做一个单行的回报。

339
00:26:05,770 --> 00:26:12,980
因此，我们实际上可以减小之前，我们通过这样做，返回。

340
00:26:12,980 --> 00:26:18,320
因此，把 - 前s.size中。

341
00:26:18,320 --> 00:26:22,060
这使该行真的很密集的。

342
00:26:22,060 --> 00:26:30,940
凡 - 第大小和s.size  - 之间的差异

343
00:26:30,940 --> 00:26:40,130
这个后缀 - 他们把它叫做后缀因为 - 来自后s.size  - 

344
00:26:40,130 --> 00:26:47,430
意味着s.size找到索引的目的评价

345
00:26:47,430 --> 00:26:50,410
因为它是目前被执行时，这条线，

346
00:26:50,410 --> 00:26:54,290
然后 - 发生后，该行被执行。

347
00:26:54,290 --> 00:27:00,340
后的元素在索引s.size的访问。

348
00:27:00,340 --> 00:27:07,260
这不是我们所希望的，因为我们希望首先发生递减。

349
00:27:07,260 --> 00:27:10,990
Othewise，我们将要访问的阵列，有效地，出界了。

350
00:27:10,990 --> 00:27:16,850
我们将要访问的元素，我们要访问一个以上。

351
00:27:16,850 --> 00:27:23,840
是啊，山姆？ “是更快或使用较少的内存在同一行或不使？

352
00:27:23,840 --> 00:27:29,620
[哈迪森说实话，这真的视情况而定。

353
00:27:29,620 --> 00:27:34,220
[山姆店，不知所云] >>呀，视情况而定。你可以做编译器技巧

354
00:27:34,220 --> 00:27:41,580
让编译器认识到，通常情况下，我想。

355
00:27:41,580 --> 00:27:44,840
>> 所以，我们所提到的有关该编译器优化的东西一点点

356
00:27:44,840 --> 00:27:47,400
您可以在编译，

357
00:27:47,400 --> 00:27:50,580
这是一个编译器可能能够找出什么样的事情，

358
00:27:50,580 --> 00:27:54,710
喜欢哦，嘿嘿，也许我可以做这一切在一次操作中，

359
00:27:54,710 --> 00:27:59,420
而不是在从RAM加载的大小变量，

360
00:27:59,420 --> 00:28:03,770
递减，其存储回，然后再重新加载

361
00:28:03,770 --> 00:28:08,000
处理此操作的其余部分。

362
00:28:08,000 --> 00:28:10,710
但通常情况下，没有，这是不诸如此类的事情，

363
00:28:10,710 --> 00:28:20,770
这将会使你的程序显着更快。

364
00:28:20,770 --> 00:28:26,000
任何更多的问题栈？

365
00:28:26,000 --> 00:28:31,360
>> 因此，入栈和出栈。如果你们想尝试的黑客版，

366
00:28:31,360 --> 00:28:33,660
我们所做的黑客版实际上是走了

367
00:28:33,660 --> 00:28:37,670
，这个堆栈动态增长。

368
00:28:37,670 --> 00:28:43,190
面临的挑战主要是在推功能在这里，

369
00:28:43,190 --> 00:28:48,820
弄清楚如何使该数组中成长

370
00:28:48,820 --> 00:28:52,450
当你继续推到堆栈上越来越多的内容。

371
00:28:52,450 --> 00:28:56,000
它实际上是没有太多额外的代码。

372
00:28:56,000 --> 00:29:00,080
只需要打一个电话 - 你必须记住要调用malloc（）有正确的，

373
00:29:00,080 --> 00:29:03,310
然后当你要调用realloc的。

374
00:29:03,310 --> 00:29:06,090
这是一个有趣的挑战，如果你有兴趣。

375
00:29:06,090 --> 00:29:11,550
>> 但暂时，让我们继续前进，让我们来谈谈队列。

376
00:29:11,550 --> 00:29:15,680
滚动经过这里。

377
00:29:15,680 --> 00:29:19,340
队列是亲兄妹的堆栈。

378
00:29:19,340 --> 00:29:25,380
所以在堆栈中的东西，放在最后

379
00:29:25,380 --> 00:29:28,810
的第一件事情，然后进行检索。

380
00:29:28,810 --> 00:29:33,600
我们已经得到这最后的，先出，或后进先出法，订货。

381
00:29:33,600 --> 00:29:38,390
而在队列中，你所期待的，当你站在线，

382
00:29:38,390 --> 00:29:41,980
线，第一件事就是到队列中的第一人，

383
00:29:41,980 --> 00:29:47,630
是的第一件事就是被从队列中检索。

384
00:29:47,630 --> 00:29:51,490
队列也经常被用来当我们正在处理的图形，

385
00:29:51,490 --> 00:29:55,560
像我们谈到了简短的堆栈，

386
00:29:55,560 --> 00:30:00,260
和队列的一堆其他东西也很方便。

387
00:30:00,260 --> 00:30:06,180
一件事，经常试图保持，例如，

388
00:30:06,180 --> 00:30:12,310
元素的排序列表。

389
00:30:12,310 --> 00:30:17,650
你可以做到这一点的数组。您可以保持在一个数组的排序列表的东西，

390
00:30:17,650 --> 00:30:20,650
但在变得复杂的是，那么你总是要找到

391
00:30:20,650 --> 00:30:26,160
在适当的地方插入接下来的事情。

392
00:30:26,160 --> 00:30:28,250
所以，如果你有一个数组的数字，从1到10，

393
00:30:28,250 --> 00:30:31,630
然后你要扩大到所有的数字1到100，

394
00:30:31,630 --> 00:30:33,670
你得到这些数字以随机顺序，并试图把一切都

395
00:30:33,670 --> 00:30:40,650
排序，你通过，你最终做了很多的转移。

396
00:30:40,650 --> 00:30:43,910
某些类型的队列和某些类型的底层数据结构，

397
00:30:43,910 --> 00:30:46,670
实际上，你可以保持相当简单。

398
00:30:46,670 --> 00:30:50,640
您不必添加一些东西，然后洗牌整个事情的时间。

399
00:30:50,640 --> 00:30:56,770
你也做了很多的内部元素的转移。

400
00:30:56,770 --> 00:31:02,990
当我们在看一个队列，你看 - 在queue.c也一节中的代码 - 

401
00:31:02,990 --> 00:31:10,950
的结构，我们已经给了你，我们给你一个堆栈的结构非常类似。

402
00:31:10,950 --> 00:31:13,770
>> 有一个例外，唯一的例外

403
00:31:13,770 --> 00:31:21,700
是，我们有这个额外的整数称为头，

404
00:31:21,700 --> 00:31:28,120
和这里的头部为队列头的跟踪的

405
00:31:28,120 --> 00:31:32,160
或在队列中的第一个元素。

406
00:31:32,160 --> 00:31:37,470
用一个堆栈，我们能够跟踪我们要撷取的元素，

407
00:31:37,470 --> 00:31:40,800
或堆栈顶部的，只是使用的大小，

408
00:31:40,800 --> 00:31:44,220
而我们的队列，处理两端。

409
00:31:44,220 --> 00:31:49,000
我们正在努力结束时粘性的东西，但然后返回从正面的东西。

410
00:31:49,000 --> 00:31:54,640
因此，有效的是，用头，我们有队列的开头的索引，

411
00:31:54,640 --> 00:31:58,920
和容量给我们的队列的末尾的索引

412
00:31:58,920 --> 00:32:03,730
这样我们就可以获取事物从头部添加东西的尾巴。

413
00:32:03,730 --> 00:32:06,890
鉴于带层叠，我们只处理堆栈的顶部。

414
00:32:06,890 --> 00:32:08,900
我们从来没有访问堆栈的底部。

415
00:32:08,900 --> 00:32:12,220
我们只添加东西到顶部，拿了东西的顶部

416
00:32:12,220 --> 00:32:17,470
所以我们并不需要额外的内部结构领域。

417
00:32:17,470 --> 00:32:20,590
一般有意义吗？

418
00:32:20,590 --> 00:32:27,670
好的。是的，夏洛特？ [夏洛特，不知所云]

419
00:32:27,670 --> 00:32:32,660
哈迪森]这是一个很大的问题，这是一个在演讲。

420
00:32:32,660 --> 00:32:36,290
也许走过的几个例子说明了为什么

421
00:32:36,290 --> 00:32:41,400
我们不希望使用字符串[0]的队列的头。

422
00:32:41,400 --> 00:32:46,770
>> 所以，想象一下，我们有我们的队列中，我们将调用它的队列。

423
00:32:46,770 --> 00:32:49,210
在刚开始的时候，我们刚刚实例化它，

424
00:32:49,210 --> 00:32:53,330
当我们刚刚宣布了它，我们还没有初始化任何东西。

425
00:32:53,330 --> 00:32:56,790
这是所有的垃圾。当然，我们要确保我们初始化

426
00:32:56,790 --> 00:33:00,950
的大小和头信息是0，一些合理的。

427
00:33:00,950 --> 00:33:05,770
我们还可以继续前进，在我们的队列空出的元素。

428
00:33:05,770 --> 00:33:09,930
此图配合，请注意，现在我们的队列只能容纳三要素;

429
00:33:09,930 --> 00:33:13,150
而我们的堆叠可容纳四，我们的队列只能容纳3。

430
00:33:13,150 --> 00:33:18,680
而这仅仅是使图适合。

431
00:33:18,680 --> 00:33:26,150
这里发生的第一件事情是我们进行排队字符串“hi”。

432
00:33:26,150 --> 00:33:30,380
就像我们与堆栈，这里没有什么可怕的不同，

433
00:33:30,380 --> 00:33:39,230
我们抛出的字符串，字符串[0]和我们的规模递增1。

434
00:33:39,230 --> 00:33:42,720
我们的入队“再见”，它被装出来的。

435
00:33:42,720 --> 00:33:45,870
因此，这看起来就像一个堆栈的大部分。

436
00:33:45,870 --> 00:33:53,230
我们这里，开始了新的元素，新元素，规模不断上升。

437
00:33:53,230 --> 00:33:56,330
在这一点上会发生什么事时，我们要出列的东西吗？

438
00:33:56,330 --> 00:34:01,280
当我们要出列，这是我们要出列的元素吗？

439
00:34:01,280 --> 00:34:04,110
[罗勒]字符串[0]。 >>零。没错，罗勒。

440
00:34:04,110 --> 00:34:10,960
我们要摆脱的第一个字符串，这其中，“喜”字。

441
00:34:10,960 --> 00:34:13,170
那么，是什么其他的事情，改变了吗？

442
00:34:13,170 --> 00:34:17,010
请注意，当我们突然出现的堆栈的东西，我们只是改变了大小，

443
00:34:17,010 --> 00:34:22,080
但在这里，我们有一对夫妇的一些改变。

444
00:34:22,080 --> 00:34:27,440
不仅的大小变化，但头部的变化。

445
00:34:27,440 --> 00:34:31,020
这是要回到夏洛特点：

446
00:34:31,020 --> 00:34:38,699
为什么我们有这个头呢？

447
00:34:38,699 --> 00:34:42,110
这是否有意义，夏洛特？ >>类的。

448
00:34:42,110 --> 00:34:47,500
[哈迪森怎样的呢？到底发生了什么，当我们出列吗？

449
00:34:47,500 --> 00:34:54,340
什么头做的，现在是有趣的？

450
00:34:54,340 --> 00:34:56,449
[夏洛特]哦，因为它改变了 - 好吧。我明白。

451
00:34:56,449 --> 00:35:02,090
因为头 - 头指向的位置方面的变化。

452
00:35:02,090 --> 00:35:07,200
它不再是零指数1。 >>是的，没错。

453
00:35:07,200 --> 00:35:17,660
发生了什么事，如果出队的高元

454
00:35:17,660 --> 00:35:20,590
做，我们没有这个头字段

455
00:35:20,590 --> 00:35:26,880
因为我们总是在0指数，我们的队列的头，调用该字符串

456
00:35:26,880 --> 00:35:30,170
然后，我们不得不转移，其余的队列。

457
00:35:30,170 --> 00:35:36,010
我们不得不转向“再见”从字符串[1]的字符串[0]。

458
00:35:36,010 --> 00:35:38,760
字符串[2]到字符串[1]。

459
00:35:38,760 --> 00:35:43,050
我们不得不这样做的整个列表中的元素，

460
00:35:43,050 --> 00:35:45,110
整个阵列的元素。

461
00:35:45,110 --> 00:35:50,490
当我们这样做是一个数组，变得非常昂贵。

462
00:35:50,490 --> 00:35:53,340
所以在这里，它不是一个大问题。我们只需要在数组中的三个要素。

463
00:35:53,340 --> 00:35:57,230
但是，如果我们有一千或一万个元素的队列，

464
00:35:57,230 --> 00:36:00,060
然后突然间，我们开始出列了一堆调用所有在一个循环中，

465
00:36:00,060 --> 00:36:03,930
事情真的要放慢，因为它转移一切不断。

466
00:36:03,930 --> 00:36:07,320
你知道吗，转移1，移位1 1，移位，移位1。

467
00:36:07,320 --> 00:36:13,650
相反，我们使用这个头，我们把它称为一个“指针”，即使它不是一个真正的指针

468
00:36:13,650 --> 00:36:16,430
从严格意义上讲，它不是一个指针类型。

469
00:36:16,430 --> 00:36:19,410
这不是一个int *或char *或类似的东西。

470
00:36:19,410 --> 00:36:28,930
但是，它指向或表示我们的队列的头。是吗？

471
00:36:28,930 --> 00:36:38,800
>> [学生]：出队知道如何只弹出，无论是在头部？

472
00:36:38,800 --> 00:36:43,620
[哈迪森如何出队知道如何弹出无论是在头吗？ “是的，是的。

473
00:36:43,620 --> 00:36:49,050
>>什么，它看起来是，只是任何头字段被设置为。

474
00:36:49,050 --> 00:36:52,710
因此，在这第一种情况下，如果我们看一下在这里，

475
00:36:52,710 --> 00:36:55,690
我们的头是0，索引为0。 “没错。

476
00:36:55,690 --> 00:37:00,500
[哈迪森]因此，它只是说，好吧，索引为0的元素，字符串“您好”，

477
00:37:00,500 --> 00:37:03,050
在我们的队列头的元素。

478
00:37:03,050 --> 00:37:05,570
因此，我们要出列，那家伙。

479
00:37:05,570 --> 00:37:09,800
那将会是元素，该元素被返回给调用者。

480
00:37:09,800 --> 00:37:14,540
是的，萨阿德吗？头“等基本设置 - 你要去的地方的索引呢？

481
00:37:14,540 --> 00:37:17,750
这是它的开始呢？ >>呀。 “好了。

482
00:37:17,750 --> 00:37:22,900
哈迪森]这是我们的阵列成为新的开始。

483
00:37:22,900 --> 00:37:28,930
所以，当你出列的东西，所有你所要做的是在索引访问元素q.head，

484
00:37:28,930 --> 00:37:32,240
和将要出列的元素。

485
00:37:32,240 --> 00:37:34,930
您还可以递减的大小。

486
00:37:34,930 --> 00:37:39,430
我们会看到在事情变得有点棘手，这一点。

487
00:37:39,430 --> 00:37:46,520
我们出列，而现在，如果我们再进行排队，

488
00:37:46,520 --> 00:37:51,300
我们进行排队在哪里？

489
00:37:51,300 --> 00:37:55,000
在我们的队列中的下一个元素哪里？

490
00:37:55,000 --> 00:37:57,980
假设我们要排队的字符串“CS”。

491
00:37:57,980 --> 00:38:02,240
到索引会去吗？ [学生]字符串[2]。 >>双。

492
00:38:02,240 --> 00:38:04,980
为什么是2而不是0呢？

493
00:38:04,980 --> 00:38:13,570
[罗勒]因为现在的头是1，所以这就像开始的列表吗？

494
00:38:13,570 --> 00:38:21,220
[哈迪森权。表示最终的名单什么？

495
00:38:21,220 --> 00:38:23,290
我们来表示我们的队列？

496
00:38:23,290 --> 00:38:25,970
头是头，我们的队列中，开始我们的队列中。

497
00:38:25,970 --> 00:38:29,530
我们的队列中的结局是什么？ [学生]大小。 >>大小，准确。

498
00:38:29,530 --> 00:38:36,360
因此，我们的新的元素，在大小，并在头的元素，我们采取的脱落。

499
00:38:36,360 --> 00:38:45,390
当我们加入队列的下一个元素，我们正在把它在大小。

500
00:38:45,390 --> 00:38:48,530
[学生]：在您提出，虽然，大小为1，正确的吗？

501
00:38:48,530 --> 00:38:55,690
[哈迪森权。因此，在大小相当。尺寸+，+1，+头。

502
00:38:55,690 --> 00:38:59,990
因为我们将一切头量。

503
00:38:59,990 --> 00:39:14,270
所以在这里，现在我们已经有了一个大小为1的队列开始在索引1。

504
00:39:14,270 --> 00:39:20,730
尾巴是指数2。是吗？

505
00:39:20,730 --> 00:39:25,780
>> [学生]：会发生什么事时，你出列字符串[0]，和字符串的内存插槽

506
00:39:25,780 --> 00:39:29,420
一下就空了，基本上，或者只是忘了吗？

507
00:39:29,420 --> 00:39:34,700
[哈迪森]是啊。从这个意义上说，我们只是忘记他们。

508
00:39:34,700 --> 00:39:42,640
如果我们存储副本 - 

509
00:39:42,640 --> 00:39:46,310
许多数据结构往往会保存自己的副本的元素

510
00:39:46,310 --> 00:39:51,760
管理的数据结构，使该人不必担心

511
00:39:51,760 --> 00:39:53,650
所有这些指标都在哪里。

512
00:39:53,650 --> 00:39:56,000
数据结构包含的一切，拥有所有的副本，

513
00:39:56,000 --> 00:39:59,580
以确保这一切仍然存在，适当的。

514
00:39:59,580 --> 00:40:03,140
然而，在这种情况下，这些数据结构只是为了简单起见，

515
00:40:03,140 --> 00:40:05,580
不是我们的东西都存储在他们的副本。

516
00:40:05,580 --> 00:40:08,630
[学生]：所以，这是一个连续的数组 - ？ “是的。

517
00:40:08,630 --> 00:40:14,350
如果我们回头看，这种结构的定义是什么，它​​是。

518
00:40:14,350 --> 00:40:19,110
这只是一个标准的数组，就像你看到的那样，

519
00:40:19,110 --> 00:40:24,280
数组的char *。

520
00:40:24,280 --> 00:40:26,340
那是 - ？是啊，我只是想知道

521
00:40:26,340 --> 00:40:29,130
如果你最终会耗尽内存，在一定程度上，

522
00:40:29,130 --> 00:40:32,330
如果您有您的阵列中的所有这些空点吗？

523
00:40:32,330 --> 00:40:36,390
哈迪森]是啊，这是一个很好的点。

524
00:40:36,390 --> 00:40:41,530
>> 如果我们看看发生了什么事，现在在这一点上，

525
00:40:41,530 --> 00:40:46,350
我们已经充满了我们的队列中，它的样子。

526
00:40:46,350 --> 00:40:50,390
但是我们还没有真正填补了我们​​的队列

527
00:40:50,390 --> 00:40:57,710
因为我们有一个队列的大小，但它在索引1开始，

528
00:40:57,710 --> 00:41:02,160
因为这就是我们的头指针。

529
00:41:02,160 --> 00:41:08,400
像你说的，在字符串的元素[0]，在0指数，是不是真的存在。

530
00:41:08,400 --> 00:41:10,450
这不是在我们的队列中了。

531
00:41:10,450 --> 00:41:16,460
我们只是懒得去和覆盖它时，我们出列。

532
00:41:16,460 --> 00:41:18,700
因此，即使它看起来就像我们的内存已经用完了，我们真的没有。

533
00:41:18,700 --> 00:41:23,270
这点是可供我们使用。

534
00:41:23,270 --> 00:41:29,310
适当的行为，如果我们试图和第一个出列的东西

535
00:41:29,310 --> 00:41:34,420
如“再见”，会弹出再见关闭。

536
00:41:34,420 --> 00:41:38,460
现在，我们的队列开始索引2处，大小为1。

537
00:41:38,460 --> 00:41:42,240
现在，如果我们试图再次进行排队东西，比如50，

538
00:41:42,240 --> 00:41:47,880
50应该在这点指数0

539
00:41:47,880 --> 00:41:51,270
因为它仍然为我们提供。是的，萨阿德吗？

540
00:41:51,270 --> 00:41:53,630
[萨阿德并自动发生吗？

541
00:41:53,630 --> 00:41:56,150
[哈迪森它不会自动发生相当。你必须做数学题

542
00:41:56,150 --> 00:42:00,380
它的工作，但基本上是我们所做的就是我们刚刚缠。

543
00:42:00,380 --> 00:42:04,070
[萨阿德是好，如果在它的中间有一个洞？

544
00:42:04,070 --> 00:42:08,720
哈迪森的是，如果我们能正确的数学工作。

545
00:42:08,720 --> 00:42:15,470
>> 事实证明，这实际上是很难做到的mod运算符。

546
00:42:15,470 --> 00:42:20,040
所以，就像我们与凯撒和加密东西，

547
00:42:20,040 --> 00:42:25,190
使用模，我们可以得到的东西，以环绕，并保持下去

548
00:42:25,190 --> 00:42:28,090
周围一圈又一圈与我们的队列中，

549
00:42:28,090 --> 00:42:32,180
保持周围，头指针移动。

550
00:42:32,180 --> 00:42:38,840
请注意，尺寸总是尊重的元素数实际上内的队列中。

551
00:42:38,840 --> 00:42:43,110
而这仅仅是头指针，骑自行车通过。

552
00:42:43,110 --> 00:42:49,660
如果我们看看这里发生了什么事，如果我们回到开头，

553
00:42:49,660 --> 00:42:55,020
你只是看看会发生什么头

554
00:42:55,020 --> 00:42:58,240
当我们进行排队的东西，什么都没有发生的头部。

555
00:42:58,240 --> 00:43:00,970
当我们排队的其他东西，什么都没有发生的头部。

556
00:43:00,970 --> 00:43:04,130
只要我们出列的东西，头一个。

557
00:43:04,130 --> 00:43:06,600
我们排队的东西，什么也没有发生的头部。

558
00:43:06,600 --> 00:43:11,060
当我们出列的东西，一下子头会增加。

559
00:43:11,060 --> 00:43:14,660
当我们进行排队的东西，什么也没有发生的头部。

560
00:43:14,660 --> 00:43:20,240
>> 在这一点上会发生什么，如果我们再次出列的东西吗？

561
00:43:20,240 --> 00:43:23,240
有什么想法？头会发生什么？

562
00:43:23,240 --> 00:43:27,190
什么是应该发生的头

563
00:43:27,190 --> 00:43:32,990
如果我们出列别的东西吗？

564
00:43:32,990 --> 00:43:35,400
头现在是索引2处，

565
00:43:35,400 --> 00:43:38,920
这意味着队列头部的字符串[2]。

566
00:43:38,920 --> 00:43:44,280
[学生]：它返回0？ >>，它应该返回为0。它应该换点左右，准确。

567
00:43:44,280 --> 00:43:48,440
到目前为止，我们每次叫出队，我们已经添加一个头，

568
00:43:48,440 --> 00:43:50,960
添加一个头，加一个头，添加一个头。

569
00:43:50,960 --> 00:43:58,400
一旦这个头指针到达最后一个索引在数组中，

570
00:43:58,400 --> 00:44:05,650
然后，我们必须把它包起来开始回到身边，回到0。

571
00:44:05,650 --> 00:44:09,900
[夏洛特]确定堆栈的队列中的能力？

572
00:44:09,900 --> 00:44:13,120
[哈迪森在这种情况下，我们刚刚一直在使用一个＃定义的常量。 “好了。

573
00:44:13,120 --> 00:44:19,590
[哈迪森在实际的文件，你可以去和淤泥一点点

574
00:44:19,590 --> 00:44:21,710
大或小，你想要的。

575
00:44:21,710 --> 00:44:25,310
[山猫]因此，当你正在做一个队列，怎么你的计算机知道

576
00:44:25,310 --> 00:44:29,120
你想堆叠就可以有多大？

577
00:44:29,120 --> 00:44:31,700
哈迪森]这是一个很大的问题。

578
00:44:31,700 --> 00:44:34,800
有一对夫妇的方式。一种是只定义了前

579
00:44:34,800 --> 00:44:42,050
并说这将是一个队列中有4个元素或50个元素或10,000。

580
00:44:42,050 --> 00:44:45,430
另一种方法是做的黑客版的人在做什么

581
00:44:45,430 --> 00:44:52,310
并创建功能，让您的队列动态地增长，越是得不到的东西加进来

582
00:44:52,310 --> 00:44:54,740
>> [山猫]第一个选项，语法是什么您使用

583
00:44:54,740 --> 00:44:57,830
告诉程序什么是队列的大小吗？

584
00:44:57,830 --> 00:45:04,780
哈迪森啊。所以，让我们离开这。

585
00:45:04,780 --> 00:45:12,650
我仍然在这里stack.c，所以我只是要滚动到顶部。

586
00:45:12,650 --> 00:45:17,920
在这里你能看到这种权利？这是的＃define能力10。

587
00:45:17,920 --> 00:45:24,600
这几乎是完全相同的语法，我们已经为队列。

588
00:45:24,600 --> 00:45:28,390
除了在队列中，在这里，我们已经得到了额外的结构域。

589
00:45:28,390 --> 00:45:32,760
[夏洛特]哦，我想指的是容量为字符串的能力。

590
00:45:32,760 --> 00:45:36,770
哈迪森啊。 >>这个​​词，它的最大长度。 “知道了。

591
00:45:36,770 --> 00:45:41,180
是啊。这里的能力 - 这是一个伟大的点。

592
00:45:41,180 --> 00:45:44,000
这是这是棘手的

593
00:45:44,000 --> 00:45:49,480
因为我们已经在这里声明的是一个数组的char *。

594
00:45:49,480 --> 00:45:52,770
数组的指针。

595
00:45:52,770 --> 00:45:56,690
这是一个字符数组。

596
00:45:56,690 --> 00:46:01,690
这可能是你见过的时候，你已经宣布你的缓冲区的文件I / O，

597
00:46:01,690 --> 00:46:06,840
当你已经创建字符串手动在堆栈中。

598
00:46:06,840 --> 00:46:09,090
然而，我们得到的是一个数组的char *。

599
00:46:09,090 --> 00:46:13,400
因此，它是一个数组的指针。

600
00:46:13,400 --> 00:46:18,350
其实，如果我们放大了，我们看看这是怎么回事

601
00:46:18,350 --> 00:46:23,140
在演示文稿中，您将看到实际的元素，字符数据

602
00:46:23,140 --> 00:46:26,180
没有被存储在数组本身。

603
00:46:26,180 --> 00:46:42,690
什么是存储在我们的数组的指针的字符数据。

604
00:46:42,690 --> 00:46:52,560
好吧。因此，我们已经看到了如何与堆栈，队列大小就像，

605
00:46:52,560 --> 00:46:58,670
大小始终尊重当前队列中的元素的数量。

606
00:46:58,670 --> 00:47:02,720
2 enqueue操作完毕后，大小为2。

607
00:47:02,720 --> 00:47:07,110
在出队的规模现在是1。

608
00:47:07,110 --> 00:47:09,330
在另一个排队的大小是高达2。

609
00:47:09,330 --> 00:47:12,340
这样的大小在队列中，绝对尊重的元素数

610
00:47:12,340 --> 00:47:15,580
头，然后不断循环。

611
00:47:15,580 --> 00:47:20,210
从0-1-2，0-1-2，0-1-2。

612
00:47:20,210 --> 00:47:25,620
每次我们调用出队，头指针会递增到下一个索引。

613
00:47:25,620 --> 00:47:29,930
如果头走了过来，这回绕到0。

614
00:47:29,930 --> 00:47:34,870
所以，我们可以编写出列的功能。

615
00:47:34,870 --> 00:47:40,200
我们要离开排队功能来实现，而不是你们。

616
00:47:40,200 --> 00:47:45,880
>> 当我们队列中取出一个元素，我们的队列中，

617
00:47:45,880 --> 00:47:55,490
丹尼尔的第一件事情就是当我们开始写的堆栈弹出功能是什么？

618
00:47:55,490 --> 00:48:00,490
让我听到从别人谁没有发言。

619
00:48:00,490 --> 00:48:06,710
让我们来看看，萨阿德，你还记得丹尼尔做的第一件事时，他写道：弹出？

620
00:48:06,710 --> 00:48:08,860
[萨阿德]，它是 -  >>他测试的东西。

621
00:48:08,860 --> 00:48:12,140
萨阿德]如果大小是大于0。 “没错。

622
00:48:12,140 --> 00:48:14,390
那是什么测试？

623
00:48:14,390 --> 00:48:19,090
萨阿德测试，看看如果有什么事，里面的数组。

624
00:48:19,090 --> 00:48:23,210
[哈迪森]是啊。没错。所以，你可以不弹出任何出栈，如果它是空的。

625
00:48:23,210 --> 00:48:26,510
同样，你不能从队列中出列任何东西，如果它是空的。

626
00:48:26,510 --> 00:48:30,420
什么是我们应该做的，我们出队函数的第一件事，你觉得呢？

627
00:48:30,420 --> 00:48:33,860
萨阿德]如果大小是大于0？ >>呀。

628
00:48:33,860 --> 00:48:37,710
在这种情况下，我其实只是测试，看它是否为0。

629
00:48:37,710 --> 00:48:42,240
如果是0，我们可以返回null。

630
00:48:42,240 --> 00:48:45,280
但相同的逻辑。

631
00:48:45,280 --> 00:48:49,110
让我们继续。

632
00:48:49,110 --> 00:48:54,600
如果不为0，是我们要出列的元素？

633
00:48:54,600 --> 00:48:58,550
萨阿德在头吗？ “没错。

634
00:48:58,550 --> 00:49:01,720
我们可以在我们的队列中拉出的第一个元素

635
00:49:01,720 --> 00:49:07,040
通过访问的头部处的元素。

636
00:49:07,040 --> 00:49:14,630
没有什么神秘的。

637
00:49:14,630 --> 00:49:19,620
在那之后，我们应该怎么办？有什么发生呢？

638
00:49:19,620 --> 00:49:23,740
其他的事情，我们谈到在出队的是什么？

639
00:49:23,740 --> 00:49:28,130
有两件事情要发生，因为我们的队列已经改变。

640
00:49:28,130 --> 00:49:35,640
[丹尼尔减少的大小。 >>我们必须缩小尺寸，并增加头部？没错。

641
00:49:35,640 --> 00:49:40,600
为了增加头部，我们不能只是一味地增加了头，记住了。

642
00:49:40,600 --> 00:49:45,080
我们可以不只是做queue.head的+ +。

643
00:49:45,080 --> 00:49:51,630
我们也必须包括这个MOD的能力。

644
00:49:51,630 --> 00:49:54,740
我们为什么要国防部的容量，Stella吗？

645
00:49:54,740 --> 00:49:58,680
斯特拉由于它具有环绕。 “没错。

646
00:49:58,680 --> 00:50:04,750
我们的国防部的容量，因为它具有包装回绕到0。

647
00:50:04,750 --> 00:50:07,400
所以，现在，在这一点上，我们可以做什么，丹尼尔说。

648
00:50:07,400 --> 00:50:12,700
我们可以减小尺寸。

649
00:50:12,700 --> 00:50:29,170
然后我们就可以返回的元素在队列的最前面。

650
00:50:29,170 --> 00:50:34,000
它看起来有点粗糙第一。你可能有一个问题。你说什么？

651
00:50:34,000 --> 00:50:37,260
>> [三]为什么是第一个在队列的最前面？哪里去了？

652
00:50:37,260 --> 00:50:42,480
哈迪森]从第四线从底部。

653
00:50:42,480 --> 00:50:46,060
经过我们测试，以确保我们的队列不为空，

654
00:50:46,060 --> 00:50:54,100
我们拉出来的char *首先，我们拉出来的元素，坐在头指数

655
00:50:54,100 --> 00:50:58,680
我们的数组，字符串数组，“呼叫，第一呢？

656
00:50:58,680 --> 00:51:04,500
[哈迪森]，我们称之为第一。是啊。

657
00:51:04,500 --> 00:51:09,850
只是跟进，为什么你认为我们必须这样做吗？

658
00:51:09,850 --> 00:51:18,270
[三]每个第一刚刚返回q.strings的[q.head？ >>呀。

659
00:51:18,270 --> 00:51:23,830
“因为我们正在做这个不断变化的的q.head的MOD功能的，

660
00:51:23,830 --> 00:51:27,810
有没有办法做到这一点也回线内。

661
00:51:27,810 --> 00:51:31,640
[哈迪森没错。你点上。三是完全发现。

662
00:51:31,640 --> 00:51:36,800
究其原因，我们在我们的队列中拉出的第一个元素，并将其存储到一个变量

663
00:51:36,800 --> 00:51:43,030
是因为这条线我们刚刚q.head的，

664
00:51:43,030 --> 00:51:47,030
有mod运算符在那里没有的东西，我们可以做的

665
00:51:47,030 --> 00:51:51,230
并使其生效的头没有 - 在同一行。

666
00:51:51,230 --> 00:51:54,480
因此，我们必须拿出的第一个元素，然后调整头，

667
00:51:54,480 --> 00:52:00,430
调整大小，然后再回到我们拉出的元素。

668
00:52:00,430 --> 00:52:02,680
而这点，我们将看到后与

669
00:52:02,680 --> 00:52:04,920
链表，我们打他们。

670
00:52:04,920 --> 00:52:08,410
很多时候，当你释放或处理链表

671
00:52:08,410 --> 00:52:13,500
你需要记住的下一个元素，在未来的链表的指针

672
00:52:13,500 --> 00:52:16,330
在处理当前。

673
00:52:16,330 --> 00:52:23,580
因为否则你扔掉的左边列表中的信息。

674
00:52:23,580 --> 00:52:34,160
现在，如果你去到您的设备，你打​​开queue.c-X了这一点。

675
00:52:34,160 --> 00:52:39,390
所以，如果我打开queue.c，让我在这里变焦，

676
00:52:39,390 --> 00:52:44,970
你会看到，你有一个外观类似的文件。

677
00:52:44,970 --> 00:52:49,200
我们早前曾与stack.c外观类似的文件。

678
00:52:49,200 --> 00:52:54,690
我们已经得到了我们的结构定义的队列，就像我们在幻灯片上看到的。

679
00:52:54,690 --> 00:52:59,870
>> 我们有我们的排队功能，这是为你做的。

680
00:52:59,870 --> 00:53:04,340
我们这里出列功能。

681
00:53:04,340 --> 00:53:06,870
在该文件中的“出列”的功能未实现，

682
00:53:06,870 --> 00:53:13,230
但我会把它备份，让您可以输入，如果你想在PowerPoint。

683
00:53:13,230 --> 00:53:16,690
因此，在接下来的5分钟左右，你们的工作排队

684
00:53:16,690 --> 00:53:22,570
这几乎是正好相反出列。

685
00:53:22,570 --> 00:53:29,560
您不必调整头，当你入队，但你有什么调整吗？

686
00:53:29,560 --> 00:53:38,920
大小。所以，当你排队，头部保持不动，被改变的大小。

687
00:53:38,920 --> 00:53:46,920
但它确实需要一点点 - 你将不得不发挥与模

688
00:53:46,920 --> 00:53:57,560
弄清楚究竟什么样的指标应插入新的元素。

689
00:53:57,560 --> 00:54:03,080
所以，我给你们一点点，把出列在幻灯片上，

690
00:54:03,080 --> 00:54:05,200
你们有问题，喊出来，使我们可以

691
00:54:05,200 --> 00:54:09,220
都在谈论他们作为一个群体。

692
00:54:09,220 --> 00:54:13,960
此外，你不知道不知道 - 当你调整大小的尺寸，你永远可以 - 

693
00:54:13,960 --> 00:54:18,720
你有没有曾经国防部的大小吗？ [丹尼尔]第>>您不必国防部的大小，正确的。

694
00:54:18,720 --> 00:54:24,260
因为大小总是会，如果让隐私无处藏 - 假设你正在管理的事情适当地，

695
00:54:24,260 --> 00:54:30,840
的大小总是会在0和3之间。

696
00:54:30,840 --> 00:54:38,680
你在哪儿于MOD当你在做排队吗？

697
00:54:38,680 --> 00:54:41,060
[学生]的头。 “仅适用于头部，准确。

698
00:54:41,060 --> 00:54:44,620
你为什么国防部在排队？

699
00:54:44,620 --> 00:54:48,830
的情况是，你必须为mod是什么时候？

700
00:54:48,830 --> 00:54:53,630
[学生]：如果你有东西在空间，喜欢在空间1和2，

701
00:54:53,630 --> 00:54:55,950
然后你需要添加的东西在0。

702
00:54:55,950 --> 00:55:02,570
[哈迪森]是的，没错。所以，如果你的头指针是在最后，

703
00:55:02,570 --> 00:55:14,210
如果你的尺寸加上你的头比较大，或者更确切地说，是怎么回事到环绕的队列。

704
00:55:14,210 --> 00:55:17,830
>> 因此，在这种情况下，我们已经有了在这里在幻灯片上，

705
00:55:17,830 --> 00:55:24,370
如果我现在要排队，

706
00:55:24,370 --> 00:55:31,110
我们要排队什么的索引为0。

707
00:55:31,110 --> 00:55:35,450
因此，如果你在50“，我称之为排队50，

708
00:55:35,450 --> 00:55:40,840
它会在底部。它在索引0。

709
00:55:40,840 --> 00:55:44,160
它取代了已经出列'嗨'。

710
00:55:44,160 --> 00:55:46,210
[丹尼尔]不要你照顾，出队了吗？

711
00:55:46,210 --> 00:55:50,550
为什么它是做什么用头在排队吗？

712
00:55:50,550 --> 00:55:55,770
[哈迪森]哦，这样你就不会修改的头，对不起。

713
00:55:55,770 --> 00:56:02,310
但是，当你访问，你必须用mod运算符

714
00:56:02,310 --> 00:56:04,250
你要排队，当你访问的元素

715
00:56:04,250 --> 00:56:06,960
你的队列中的下一个元素。

716
00:56:06,960 --> 00:56:10,960
瓦西里我没有做到这一点，我在那里的“成功”。

717
00:56:10,960 --> 00:56:13,370
[丹尼尔：哦，我明白你在说什么。

718
00:56:13,370 --> 00:56:16,240
[哈迪森所以，你并没有 - 你只是做了在q.size？

719
00:56:16,240 --> 00:56:20,670
[罗勒]是啊。我只是改变了双方的，我没有做任何事情的头部。

720
00:56:20,670 --> 00:56:24,300
[哈迪森]你实际上并不需要重设的头是什么，

721
00:56:24,300 --> 00:56:31,650
但是当你到字符串数组中的索引，

722
00:56:31,650 --> 00:56:39,500
你必须继续前进，计算出下一个元素是，

723
00:56:39,500 --> 00:56:44,230
因为枝条堆栈中的下一个元素在堆栈总是

724
00:56:44,230 --> 00:56:48,740
的大小相对应的索引。

725
00:56:48,740 --> 00:56:55,850
如果我们回顾一下，在我们的压栈功能，

726
00:56:55,850 --> 00:57:03,100
索引的大小，我们总是可以花掉我们的新元素。

727
00:57:03,100 --> 00:57:06,710
而与队列，我们​​不能这样做，

728
00:57:06,710 --> 00:57:10,340
因为如果我们在这种情况下，

729
00:57:10,340 --> 00:57:18,130
如果我们排队的50我们新的字符串，字符串[1]

730
00:57:18,130 --> 00:57:20,540
我们并不想这样做。

731
00:57:20,540 --> 00:57:41,200
我们希望有新的字符串的索引为0。

732
00:57:41,200 --> 00:57:44,320
>> 是否任何人 - 是吗？ [学生]：我有一个问题，但它不是真正相关。

733
00:57:44,320 --> 00:57:48,160
当有人要求类似PRED指针是什么意思？

734
00:57:48,160 --> 00:57:51,260
那是什么名字的简称吗？我知道这只是一个名字。

735
00:57:51,260 --> 00:57:59,110
哈迪森] PRED指针？让我们来看看。在什么情况下？

736
00:57:59,110 --> 00:58:01,790
[学生]：这是插入。如果你想，我可以请你以后

737
00:58:01,790 --> 00:58:03,920
因为它不是真正相关的，但我只是 - 

738
00:58:03,920 --> 00:58:07,300
[哈迪森从大卫的讲座插入代码？

739
00:58:07,300 --> 00:58:10,860
我们可以拉起来，说这些了。

740
00:58:10,860 --> 00:58:15,550
我们将讨论下，一旦我们得到的链接列表。

741
00:58:15,550 --> 00:58:21,440
>> 因此，让我们看排队的函数看起来像真的很快。

742
00:58:21,440 --> 00:58:26,530
人的第一件事就是试图在您的排队线是什么？插入此队列中呢？

743
00:58:26,530 --> 00:58:29,960
类似的堆栈推你做了什么。

744
00:58:29,960 --> 00:58:32,080
你做了什么，Stella吗？

745
00:58:32,080 --> 00:58:35,050
[斯特拉，不知所云]

746
00:58:35,050 --> 00:58:45,700
[哈迪森没错。如果（q.size ==容量） - 

747
00:58:45,700 --> 00:58:54,720
在正确的地方，我需要把我的大括号 - 返回false。

748
00:58:54,720 --> 00:59:01,370
在一点点放大。好吧。

749
00:59:01,370 --> 00:59:03,800
现在什么是未来的事情，我们必须做的吗？

750
00:59:03,800 --> 00:59:11,370
与堆栈，就像插在正确的地方。

751
00:59:11,370 --> 00:59:16,010
因此，什么是正确的位置插入，？

752
00:59:16,010 --> 00:59:23,170
与堆栈是索引的大小，这不是很。

753
00:59:23,170 --> 00:59:30,210
[丹尼尔]我有q.head- -   -  >> q.strings的吗？ >>呀。

754
00:59:30,210 --> 00:59:40,470
的q.strings q.head + q.size模能力]？

755
00:59:40,470 --> 00:59:42,740
[哈迪森我们可能要加上括号解决这个问题

756
00:59:42,740 --> 00:59:48,830
这样我们就得到适当的优先，所以，大家cleart。

757
00:59:48,830 --> 00:59:55,800
和平等的吗？ >>海峡？ >>给乙方。大。

758
00:59:55,800 --> 01:00:00,160
现在我们必须做的最后一件事是什么？

759
01:00:00,160 --> 01:00:06,780
就像我们在堆栈中。 >>增量的大小吗？ >>增量的大小。

760
01:00:06,780 --> 01:00:13,830
轰。之后，从启动代码只是返回false默认情况下，

761
01:00:13,830 --> 01:00:27,460
我们要更改为true，如果一切顺利，一切顺利。

762
01:00:27,460 --> 01:00:33,050
好的。这是一个很大的信息部分。

763
01:00:33,050 --> 01:00:39,480
我们不是挺了过来。我们要谈谈真的很快单链表。

764
01:00:39,480 --> 01:00:44,010
我会把这，所以我们可以回去吧。

765
01:00:44,010 --> 01:00:50,850
但是，让我们回到我们的介绍只是多了一些幻灯片。

766
01:00:50,850 --> 01:00:53,790
因此，排队是的TODO，现在我们已经做到了。

767
01:00:53,790 --> 01:00:57,430
>> 现在，让我们来看看在单链表。

768
01:00:57,430 --> 01:01:00,040
在讲座中，我们谈到了这些多一点点。

769
01:01:00,040 --> 01:01:02,540
有许多你们在这里我们看到的演示的人

770
01:01:02,540 --> 01:01:08,220
笨拙地指向到相互持股数？ >>，我就在那。

771
01:01:08,220 --> 01:01:16,620
“你们认为什么？这样做，希望神秘面纱这一点吗？

772
01:01:16,620 --> 01:01:25,990
与列表，事实证明，我们应对这种类型的，我们要调用一个节点。

773
01:01:25,990 --> 01:01:32,520
而与队列和栈我们，我们会打电话给队列，栈的结构，

774
01:01:32,520 --> 01:01:34,860
我们有这些新的队列，堆栈类型，

775
01:01:34,860 --> 01:01:39,240
这里的列表实际上只是由一堆节点。

776
01:01:39,240 --> 01:01:45,920
以同样的方式，字符串的字符只是一堆所有排队彼此相邻的。

777
01:01:45,920 --> 01:01:50,650
链表是一个节点和另一个节点和另一个节点和另一个节点。

778
01:01:50,650 --> 01:01:55,080
而不是砸的所有节点，并将其存储连续

779
01:01:55,080 --> 01:01:58,090
所有彼此在内存中，

780
01:01:58,090 --> 01:02:04,470
这下指针允许我们存储节点的地方，随意。

781
01:02:04,470 --> 01:02:10,500
然后他们种线一起从一个点到下一个。

782
01:02:10,500 --> 01:02:15,850
>> 是什么很大的优势，这有一个数组？

783
01:02:15,850 --> 01:02:21,680
连续超过存储一切只是停留彼此？

784
01:02:21,680 --> 01:02:24,190
你还记得吗？是吗？ >>动态内存分配？

785
01:02:24,190 --> 01:02:27,220
>>动态内存分配在什么意义呢？

786
01:02:27,220 --> 01:02:31,780
[学生]，你可以保持它大，你没有将你的整个阵列？

787
01:02:31,780 --> 01:02:40,940
[哈迪森没错。因此，一个数组，当你想要把一个新的元素，它的中间，

788
01:02:40,940 --> 01:02:45,320
你有改变一切，以腾出空间。

789
01:02:45,320 --> 01:02:47,880
而像我们谈论的队列中，

790
01:02:47,880 --> 01:02:50,080
这就是为什么我们保持头指针，

791
01:02:50,080 --> 01:02:52,050
所以，我们不是不断变化的东西。

792
01:02:52,050 --> 01:02:54,520
因为得到昂贵的，如果你有一个大数组

793
01:02:54,520 --> 01:02:57,130
你经常做这些随机的插入。

794
01:02:57,130 --> 01:03:00,820
而与列表，所有您需要做的是把它的新节点上，

795
01:03:00,820 --> 01:03:06,330
调整指针，你就大功告成了。

796
01:03:06,330 --> 01:03:10,940
什么吸什么呢？

797
01:03:10,940 --> 01:03:16,830
除了事实上，它是不容易的工作数组？是吗？

798
01:03:16,830 --> 01:03:22,980
[丹尼尔]嗯，我想它要困难得多访问某个特定的链接列表中的元素？

799
01:03:22,980 --> 01:03:30,470
[哈迪森你不能只是跳转到链表中的任意一个元素。

800
01:03:30,470 --> 01:03:33,800
你怎么做，而不是吗？ >>您逐步完成整个事情。

801
01:03:33,800 --> 01:03:35,660
[哈迪森]是啊。你必须去通过一次一个地，一次一个。

802
01:03:35,660 --> 01:03:38,480
这是一个巨大的 - 这是一个痛苦。

803
01:03:38,480 --> 01:03:41,550
有什么其他 - 这还有另一个倒台。

804
01:03:41,550 --> 01:03:45,340
罗勒，您可以向前和向后走？你必须去一个方向吗？

805
01:03:45,340 --> 01:03:48,570
[哈迪森]是啊。那么，我们如何解决这个问题，有时？

806
01:03:48,570 --> 01:03:53,370
[罗勒]双链表？ “没错。有双链表。

807
01:03:53,370 --> 01:03:55,540
也有 - 对不起吗？

808
01:03:55,540 --> 01:03:57,620
>> [三]是一样PRED的事情， - 

809
01:03:57,620 --> 01:04:01,090
我想起来了，这不正是PRED的是吗？

810
01:04:01,090 --> 01:04:05,850
这不就是在双和单间？

811
01:04:05,850 --> 01:04:10,020
[哈迪森]让我们看看他在做的究竟是什么。

812
01:04:10,020 --> 01:04:15,760
所以，在这里，我们走了。下面的代码。

813
01:04:15,760 --> 01:04:25,620
在这里，我们有predptr，在这里。这是你在​​谈论什么吗？

814
01:04:25,620 --> 01:04:30,750
因此，这是 - 他释放的名单，他试图保存一个指向它的指针。

815
01:04:30,750 --> 01:04:35,000
这是不是双重，单链接列表。

816
01:04:35,000 --> 01:04:40,090
我们可以稍后再谈谈这个问题，因为这是在谈论释放名单

817
01:04:40,090 --> 01:04:42,900
我想告诉一些其他的东西。

818
01:04:42,900 --> 01:04:51,480
但它只是 - 它记住的指针的值

819
01:04:51,480 --> 01:04:54,170
[学生]：哦，这是前面的指针吗？ >>呀。

820
01:04:54,170 --> 01:05:04,070
所以，我们就可以递增：指针本身之前，我们就可以自由predptr是什么。

821
01:05:04,070 --> 01:05:09,130
因为我们不能免费指针，然后调用PTR =指针下，对不对？

822
01:05:09,130 --> 01:05:11,260
这将是坏的。

823
01:05:11,260 --> 01:05:20,940
所以，让我们来看看，这个家伙。

824
01:05:20,940 --> 01:05:23,900
>> 有关列表的其他坏事，而数组

825
01:05:23,900 --> 01:05:26,520
我们只是有自己的堆栈彼此的所有元素，

826
01:05:26,520 --> 01:05:29,050
在这里，我们也介绍了这个指针。

827
01:05:29,050 --> 01:05:34,060
因此，有一个额外的内存块，我们使用

828
01:05:34,060 --> 01:05:37,910
对于每一个元素，我们要存储在我们的名单。

829
01:05:37,910 --> 01:05:40,030
我们得到的灵活性，但它是有代价的。

830
01:05:40,030 --> 01:05:42,230
它配备了这个时间成本，

831
01:05:42,230 --> 01:05:45,270
，它与此内存成本。

832
01:05:45,270 --> 01:05:47,800
时间在这个意义上，我们现在必须在数组中的每个元素

833
01:05:47,800 --> 01:05:58,670
找到在索引10中的一个，或者说，将有在一个数组中的索引10。

834
01:05:58,670 --> 01:06:01,230
>> 真的很快，当我们图的这些名单，

835
01:06:01,230 --> 01:06:05,980
通常我们认为在头部的列表或列表中的第一个指针

836
01:06:05,980 --> 01:06:08,010
注意，这是一个真正的指针。

837
01:06:08,010 --> 01:06:11,100
它只有4个字节。它本身不是一个实际的节点。

838
01:06:11,100 --> 01:06:17,120
所以你看它有没有int值，没有next指针。

839
01:06:17,120 --> 01:06:20,790
它实际上只是一个指针。

840
01:06:20,790 --> 01:06:23,550
它要指向的东西，是一个实际的节点结构。

841
01:06:23,550 --> 01:06:28,480
[三]一个指针，称为节点？ >>这是 - 没有。这是一个指向某种类型的节点。

842
01:06:28,480 --> 01:06:32,540
它是一个指针的节点结构。哦，没关系。

843
01:06:32,540 --> 01:06:36,870
图上的左，右侧列表符号。

844
01:06:36,870 --> 01:06:42,190
我们可以将其设置为null，这是一个很好的方式开始。

845
01:06:42,190 --> 01:06:49,850
当你图它，你要么写为空或通过它，你放了行这样的。

846
01:06:49,850 --> 01:06:53,910
>> 使用列表的最简单的方法之一，

847
01:06:53,910 --> 01:06:57,430
，我们要求你都前置和追加到两者之间的差异，

848
01:06:57,430 --> 01:07:01,320
但在前面加上是肯定更容易。

849
01:07:01,320 --> 01:07:05,790
当你在前面加上，这就是你的 - 当你预定（7）

850
01:07:05,790 --> 01:07:10,050
你去创建节点结构

851
01:07:10,050 --> 01:07:13,870
设置第一个指向它，因为现在，因为我们前面加上它，

852
01:07:13,870 --> 01:07:17,240
它要在列表的开头。

853
01:07:17,240 --> 01:07:22,540
如果我们预定（3），，创建另一个节点，但现在前7。

854
01:07:22,540 --> 01:07:31,130
因此，我们本质上推动我们的名单上。

855
01:07:31,130 --> 01:07:34,720
现在，你可以看到前置，有时人们把它推，

856
01:07:34,720 --> 01:07:39,600
因为你推到你的列表中一个新的元素。

857
01:07:39,600 --> 01:07:43,270
在前面的列表中删除它也很容易。

858
01:07:43,270 --> 01:07:45,650
所以，人们往往会调用该弹出。

859
01:07:45,650 --> 01:07:52,200
以这种方式，你可以模拟一个堆栈使用链表。

860
01:07:52,200 --> 01:07:57,880
哎呀。很抱歉，现在我们正在为追加。所以，我们在这里前缀（7），现在我们预定（3）。

861
01:07:57,880 --> 01:08:02,600
如果我们预先考虑别的东西到这个列表中，（4），如果我们预先考虑

862
01:08:02,600 --> 01:08:06,540
然后，我们有4个，然后3，然后7。

863
01:08:06,540 --> 01:08:14,220
那么我们就可以弹出并删除，删除，删除7。

864
01:08:14,220 --> 01:08:16,500
通常情况下，更直观的方式来思考这个是附加的。

865
01:08:16,500 --> 01:08:20,310
所以，我图表示出来，它看起来像什么与附加在这里。

866
01:08:20,310 --> 01:08:23,380
在这里，追加（7）不看有什么不同

867
01:08:23,380 --> 01:08:25,160
因为只有一个列表中的元素。

868
01:08:25,160 --> 01:08:28,620
并追加（3）将它结束。

869
01:08:28,620 --> 01:08:31,020
也许你可以看到现在的诀窍追加

870
01:08:31,020 --> 01:08:36,600
是因为我们只知道该从哪里开始的列表，

871
01:08:36,600 --> 01:08:39,450
要追加到一个列表，在列表中，你必须走一路

872
01:08:39,450 --> 01:08:46,500
去年底，停止，然后建立您的节点，和普拉克一切的下降。

873
01:08:46,500 --> 01:08:50,590
连接所有的东西。

874
01:08:50,590 --> 01:08:55,170
因此，前置，作为我们只是洞穿这真的很快，

875
01:08:55,170 --> 01:08:58,170
当你预先准备的列表，这是相当简单的。

876
01:08:58,170 --> 01:09:02,960
>> 你让你的新节点，涉及到一些动态内存分配。

877
01:09:02,960 --> 01:09:09,830
所以，在这里，我们正在做一个节点使用malloc的结构。

878
01:09:09,830 --> 01:09:14,710
所以malloc的，我们正在使用的，因为这会为我们预留内存后

879
01:09:14,710 --> 01:09:20,350
因为我们不希望这样 - 我们希望这记忆将持续很长一段时间。

880
01:09:20,350 --> 01:09:25,350
我们得到了一个指针，我们只是分配的内存空间。

881
01:09:25,350 --> 01:09:29,260
我们使用的节点的大小，我们不总结的领域。

882
01:09:29,260 --> 01:09:31,899
我们不手动生成的字节数，

883
01:09:31,899 --> 01:09:39,750
相反，我们使用sizeof，让我们知道我们得到适当的字节数。

884
01:09:39,750 --> 01:09:43,660
我们一定要测试我们的malloc调用成功。

885
01:09:43,660 --> 01:09:47,939
这是你想要做的一般。

886
01:09:47,939 --> 01:09:52,590
在现代化的机器上，运行内存不足是不是一件容易

887
01:09:52,590 --> 01:09:56,610
除非你分配一吨的东西，使一个巨大的名单，

888
01:09:56,610 --> 01:10:02,220
但是，如果你的东西，比如说，像iPhone或Android，

889
01:10:02,220 --> 01:10:05,230
你只有有限的内存资源，特别是如果你正在做的事情激烈。

890
01:10:05,230 --> 01:10:08,300
所以这是很好的实践。

891
01:10:08,300 --> 01:10:10,510
>> 请注意，我在这里已经使用了几个不同的功能

892
01:10:10,510 --> 01:10:12,880
您已经看到了，是种新的。

893
01:10:12,880 --> 01:10:15,870
因此，fprintf同于printf

894
01:10:15,870 --> 01:10:21,320
除了它的第一个参数是你要打印其中的流。

895
01:10:21,320 --> 01:10:23,900
在这种情况下，我们要打印到标准错误字符串

896
01:10:23,900 --> 01:10:29,410
这是从标准outstream不同。

897
01:10:29,410 --> 01:10:31,620
默认情况下，它显示了在同一个地方。

898
01:10:31,620 --> 01:10:34,600
它也打印到​​终端，但你可以 - 

899
01:10:34,600 --> 01:10:38,790
使用这些命令，您了解，重定向技术

900
01:10:38,790 --> 01:10:42,290
您了解了在托米的视频，你可以直接问题集4

901
01:10:42,290 --> 01:10:47,900
不同的区域，然后退出，在这里，你的程序退出。

902
01:10:47,900 --> 01:10:50,440
它本质上就像是从main返回，

903
01:10:50,440 --> 01:10:53,600
除了我们使用exit因为这里的利润不会做任何事情。

904
01:10:53,600 --> 01:10:57,140
我们不是主要的，因此返回不退出程序，像我们希望的。

905
01:10:57,140 --> 01:11:03,020
因此，我们使用exit函数，并给它一个错误代码。

906
01:11:03,020 --> 01:11:11,890
那么在这里我们设置新节点的值字段，其i现场等于我，然后我们其连接。

907
01:11:11,890 --> 01:11:15,530
我们设置新节点的next指针指向第一，

908
01:11:15,530 --> 01:11:20,460
那么首先将指向新的节点。

909
01:11:20,460 --> 01:11:25,120
这些第一行代码中，我们实际上是在建立新的节点。

910
01:11:25,120 --> 01:11:27,280
不是最后两行的这个功能，但第一的。

911
01:11:27,280 --> 01:11:30,290
实际上，你可以拉成一个函数，一个辅助函数。

912
01:11:30,290 --> 01:11:32,560
这通常我做什么，我拉出来的功能，

913
01:11:32,560 --> 01:11:36,040
我把它类似于构建节点，

914
01:11:36,040 --> 01:11:40,410
的前置功能保持相当小，仅有3行，然后。

915
01:11:40,410 --> 01:11:48,710
我打电话到我的体型节点的功能，然后我线的一切行动。

916
01:11:48,710 --> 01:11:51,970
>> 最后一点，我想告诉你，

917
01:11:51,970 --> 01:11:54,030
我会让你做追加和自己的，

918
01:11:54,030 --> 01:11:57,500
是如何遍历列表。

919
01:11:57,500 --> 01:12:00,780
还有一堆不同的方法来遍历列表。

920
01:12:00,780 --> 01:12:03,140
在这种情况下，我们要找到一个列表的长度。

921
01:12:03,140 --> 01:12:06,570
因此，我们从长度= 0。

922
01:12:06,570 --> 01:12:11,580
这是非常类似于写strlen的一个字符串。

923
01:12:11,580 --> 01:12:17,780
这就是我要告诉你，这个循环在这里。

924
01:12:17,780 --> 01:12:23,530
它看起来有点古怪，它不是一般的INT I = 0，我不管，我+ +。

925
01:12:23,530 --> 01:12:34,920
相反，它的初始化我们的变量n的列表开始。

926
01:12:34,920 --> 01:12:40,620
然后，我们的迭代变量不为空，我们继续前进。

927
01:12:40,620 --> 01:12:46,340
这是因为，按照惯例，我们的名单将是无效的。

928
01:12:46,340 --> 01:12:48,770
然后递增，而不是做+ +，

929
01:12:48,770 --> 01:12:57,010
链表相当于+ +是n =正 - >下一个。

930
01:12:57,010 --> 01:13:00,410
>> 我会让你填写在这里的差距，因为我们没时间了。

931
01:13:00,410 --> 01:13:09,300
但记住这一点，当你在你的spellr的pset。

932
01:13:09,300 --> 01:13:11,650
链表，如果你正在实现一个哈希表，

933
01:13:11,650 --> 01:13:14,010
一定会非常方便。

934
01:13:14,010 --> 01:13:21,780
这个成语循环的事情，使生活变得更加简单，希望。

935
01:13:21,780 --> 01:13:25,910
如有任何疑问，速度够快吗？

936
01:13:25,910 --> 01:13:28,920
[三]你会发出完成的SLL和SC？

937
01:13:28,920 --> 01:13:38,360
[哈迪森]是啊。我会发出完成幻灯片和SLL协议栈和queue.cs的。

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]