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