1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Раздзел 6: менш камфортна]

2
00:00:02,730 --> 00:00:05,040
[Nate Хардисон] [Harvard University]

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
мы кажам пра мадэліраванне stucture стэка дадзеных з дапамогай такой структуры.

26
00:01:46,730 --> 00:01:51,070
>> Такім чынам, што мы маем тут, гэта падобна на тое, што была прадстаўлена ў лекцыі,

27
00:01:51,070 --> 00:01:58,120
акрамя лекцыі мы прадставілі гэта з цэлымі, а не сімвал * с.

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
У нас ёсць масіў сімвалаў * з, гэта масіў радкоў,

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
калі ёмістасць была # вызначаецца як чатыры.

62
00:04:28,330 --> 00:04:33,490
У нас ёсць нашы чатыры элемента масіў сімвалаў *.

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
які будзе свой код, гэта проста абвясціць структуру, складзеныя структура называецца с.

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 я, а не яго ініцыялізацыі.

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
Мы маглі б пайсці далей і ініцыялізаваць ўсе паказальнікі, усё сімвал S *

80
00:05:43,450 --> 00:05:49,670
каб быць зразумелымі некаторыя значэння, верагодна, нулявы.

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
[Stella] Націск і пляскаць? >> Менавіта так.

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
Калі б мы былі націснуць на радок "прывітанне" на наш стэк,

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
Гэта радок "прывітанне", і гэта ўсё.

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
Такім чынам, вы можаце бачыць "свет" тут ідзе зверху "прывітанне",

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], таму, калі мы націскаем "Woot»,

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
Гэта стэка, які можа быць ня больш за чатыры знакаў * з, не больш за чатыры рэчаў.

142
00:10:02,850 --> 00:10:07,580
Калі б мы былі, каб паспрабаваць падштурхнуць 1/5 рэч, што вы думаеце павінна адбыцца?

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
Але на пачатковым этапе, што можа здарыцца? Што, калі мы спрабавалі праштурхнуць 1/4 рэч?

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
тое, што мы хочам зрабіць, гэта проста вяртанне ілжывым.

158
00:11:16,030 --> 00:11:20,030
Нашы метаду прымусовай збіраецца вярнуць лагічнае значэнне,

159
00:11:20,030 --> 00:11:22,920
і што лагічнае значэнне будзе сапраўдным, калі штуршок паспяхова

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
Ён збіраецца вярнуцца дакладна, калі радок была паспяхова выцеснілі

165
00:11:45,820 --> 00:11:51,820
ў стэку, а ў адваротным выпадку.

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
[Хардисон] Bingo. Добрая праца.

169
00:12:23,320 --> 00:12:26,310
Калі памер мае патэнцыял, мы збіраемся вярнуцца ілжывым.

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
[Missy] One. >> Памер адзін, сапраўды. Вы працягвайце дадаваць да памеру,

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
і мы толькі збіраемся, каб захаваць наш сімвал * у там.

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
А потым Missy выхоўвалі, што мы цяпер павінны зрабіць,

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
[Студэнт] Вярнуцца праўда. >> Вярнуцца праўда.

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 'ы дужках памер = вул?

203
00:15:34,730 --> 00:15:42,910
Што такое СТА? Хіба што пэўная дзесьці раней, ці - о, у знак вул *?

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
Мы лічылі само сабой якія разумеюцца, што ў нас была гэтая зменная з

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
ааа, паўсюль -

228
00:17:29,220 --> 00:17:32,840
і вы пералічыце тое, што тут, вы бачыце, што ў вас ёсць тры розных. з файламі.

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
А галоўнае клапоціцца пра справу робіць штуршок і поп-званкі

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
[Данііл] Мы проста ажыццяўленні поп прама цяпер? >> Проста поп-музыкі.

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
на самай справе, адзінае, што мы бачылі, адбываецца, калі мы называлі поп-

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, то не было б перайсці да элемента 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
Daniel, што было першае, што вы зрабілі?

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
[Данііл] Return нуль? >> Вярнуцца нулявы, гэта дакладна.

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
[Stella] Вы паменшыце памер? >> Вы памяншэння памеру, усё ў парадку.

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
[Stella] І тады я сказаў вяртання s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Хардисон] Вялікі.

323
00:24:48,560 --> 00:24:51,940
У адваротным выпадку вы вернецеся нулявы. Так, Сэм?

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
у адрозненне ад загрузкі памер зменнай з аператыўнай памяці,

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
Проста выклік - вы павінны памятаць, каб атрымаць званкі на таНос там належным чынам,

373
00:29:00,080 --> 00:29:03,310
, А затым высветліць, калі вы збіраецеся тэлефанаваць пераразмеркаваць.

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
Добра. Так, Шарлота? [Charlotte, неразборліва]

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
у той час як наш стэк можа правесьці чатыры, наша чаргу можа мець толькі тры.

430
00:33:13,150 --> 00:33:18,680
І гэта толькі каб зрабіць схему патрэбным.

431
00:33:18,680 --> 00:33:26,150
Першае, што тут адбываецца, што мы пастаноўкі ў чаргу радка "прывітанне".

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]. >> Zero. Цалкам дакладна, Васіль.

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
[Charlotte] О, таму што яна змянілася - усё ў парадку. Разумею.

451
00:34:56,449 --> 00:35:02,090
Таму што галава - дзе галава паказвае на змены ў плане размяшчэння.

452
00:35:02,090 --> 00:35:07,200
Гэта ўжо не заўсёды нулявога азначніка. >> Так, менавіта так.

453
00:35:07,200 --> 00:35:17,660
Тое, што адбылося, калі dequeueing высокага элемента

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 * ці сімвал * ці што-небудзь падобнае.

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
Што ў канцы нашай чарзе? [Студэнты] Size. >> Памер, дакладна.

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
масіў сімвалаў S *.

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
таму што ў нас чарга гэта памер 2, але ён пачынаецца з індэкса 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
>> І аказваецца, што гэта на самай справе не так ужо цяжка зрабіць з модом аператара.

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
[Charlotte] Што вызначае здольнасць чэргі ў стэку?

572
00:44:09,900 --> 00:44:13,120
[Хардисон] У гэтым выпадку, мы проста выкарыстоўвалі # вызначана пастаянная. >> Добра.

573
00:44:13,120 --> 00:44:19,590
[Хардисон] У рэальным. Файл C, вы можаце пайсці і скінуць з яе трохі

574
00:44:19,590 --> 00:44:21,710
і зрабіць гэта як вялікі або як мала, як вы хочаце.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Такім чынам, калі вы робіце гэта чарзе, як вы робіце кампутара ведаю

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
>> [Charlotte] Так, каб пайсці з першым варыянтам, які сінтаксіс вы выкарыстоўваеце

583
00:44:54,740 --> 00:44:57,830
паказаць праграме, што памер чарзе?

584
00:44:57,830 --> 00:45:04,780
[Хардисон] Ah. Такім чынам, давайце з гэтага.

585
00:45:04,780 --> 00:45:12,650
Я ўсё яшчэ ў stack.c тут, так што я проста хачу, каб пракруціць да самага верху тут.

586
00:45:12,650 --> 00:45:17,920
Вы можаце ўбачыць гэта прама тут? Гэта # вызначыць ёмістасць 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
[Charlotte] О, я думаў, што магутнасць азначае здольнасць да радка.

590
00:45:32,760 --> 00:45:36,770
[Хардисон] Ah. >> Што гэта максімальная даўжыня слова. >> Ёсць.

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
таму што мы абвясцілі тут масіў сімвалаў S *.

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
Гэта, напэўна, тое, што вы бачылі, калі вы былі вашы аб'явы буфераў для файлавага ўводу / вываду,

597
00:46:01,690 --> 00:46:06,840
калі вы стваралі радкі ўручную ў стэку.

598
00:46:06,840 --> 00:46:09,090
Аднак тое, што мы маем тут уяўляе сабой масіў сімвалаў S *.

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 ставіць у чаргу, памер 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, мы можам вярнуцца нулявы.

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
Мы павінны таксама ўключаць гэты мод па магутнасці.

644
00:49:51,630 --> 00:49:54,740
І чаму мы мода на магутнасць, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Таму што ён мае, каб абгарнуць вакол. >> Менавіта так.

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
Мы выцягнуць з * Па-першае, мы выцягнуць элемент, які сядзіць на чале індэкса

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 з модом функцыі,

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
ёсць мод аператара там не тое, што мы можам зрабіць

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--х з гэтага.

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
Вы не павінны рэгуляваць галаву, калі вы enqueueing, але тое, што вы павінны наладзіць?

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
Дзе вы павінны мода, калі вы робіце пастаноўкі ў чаргу?

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
Калі сітуацыя, у якой вам давядзецца мода?

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
Але вы павінны выкарыстоўваць мод аператара, калі вы звяртаецеся

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
[Хардисон] Такім чынам, вы didn't - вы толькі што зрабілі ў 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
Што вы рабілі, Стэла?

745
00:58:32,080 --> 00:58:35,050
[Stella, неразборліва]

746
00:58:35,050 --> 00:58:45,700
[Хардисон] Менавіта так. Калі (q.size == ёмістасці) -

747
00:58:45,700 --> 00:58:54,720
Мне трэба паставіць маю дужкі ў патрэбным месцы - вярнуцца ілжывым.

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
Boom. А затым, паколькі стартавы код толькі што вярнуўся ілжывай па змаўчанні,

761
01:00:13,830 --> 01:00:27,460
Мы хочам змяніць гэта дакладна, калі ўсё праходзіць і ўсё ідзе добра.

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
але гэта проста - гэта памятаць значэнне PTR

819
01:04:51,480 --> 01:04:54,170
[Студэнт] О, гэта папярэдняй паказальнік? >> Так.

820
01:04:54,170 --> 01:05:04,070
Так што мы можам павялічыць PTR сябе, перш чым мы тады бясплатна, што з'яўляецца predptr.

821
01:05:04,070 --> 01:05:09,130
Паколькі мы не можам бясплатна PTR, а затым выклікаць PTR = 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
Такім чынам, вы бачыце, што ён не мае цэлалікавых значэнне ў ёй, не наступнага паказальніка ў ім.

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
Мы можам ўсталяваць яго ў нуль, які з'яўляецца добрым спосабам для пачатку.

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), што стварае яшчэ адзін вузел, але цяпер 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
І тады мы маглі б поп-і выдаліць 4, выдаліць 3, выдаліць 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
Такім чынам, вось што мы робім вузел структуры выкарыстаннем таНос.

878
01:09:09,830 --> 01:09:14,710
Так таНос мы выкарыстоўваем, таму што будзе выдзелена памяці для нас, для наступнага

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
Мы клапоцімся аб тым, каб праверыць, што наш таНос выкліку ўдалося.

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
Гэта, па сутнасці, як вяртаўся з галоўных,

903
01:10:50,440 --> 01:10:53,600
за выключэннем мы выкарыстоўваем выхад, таму што тут вяртанне не будзе нічога рабіць.

904
01:10:53,600 --> 01:10:57,140
Мы не ў асноўнай, так што вяртацца не выйсці з праграмы, як мы хочам.

905
01:10:57,140 --> 01:11:03,020
Таму мы выкарыстоўваем функцыю выхаду і даць яму код памылкі.

906
01:11:03,020 --> 01:11:11,890
Тады тут мы ўсталёўваем значэнне новага вузла поля, яго я поля роўным я, а потым падлучыць яго.

907
01:11:11,890 --> 01:11:15,530
Мы ўсталявалі наступны паказальнік новага вузла, каб паказаць на першы,

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 я = 0, <што заўгодна, я + +.

925
01:12:23,530 --> 01:12:34,920
Замест гэтага ён ініцыялізацыю нашай зменнай п будзе ў пачатку спісу.

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
Звязаны спіс эквіваленце + + п = п-> далей.

930
01:12:57,010 --> 01:13:00,410
>> Я дам вам запоўніць прабелы тут, таму што мы знаходзімся па-за часам.

931
01:13:00,410 --> 01:13:09,300
Але майце гэта на ўвазе, як вы працуеце на psets spellr.

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 і ПК?

937
01:13:28,920 --> 01:13:38,360
[Хардисон] Так. Я буду пасылаць завершана слайды і завяршыў стэк SLL і queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]