1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
Даг Lloyd: Добра,
так да гэтага моманту вы знаходзіцеся

3
00:00:05,990 --> 00:00:09,020
верагодна, даволі добра знаёмыя
з масівамі і сувязнымі спісамі

4
00:00:09,020 --> 00:00:10,950
які з'яўляецца два асноўных
структуры дадзеных мы

5
00:00:10,950 --> 00:00:16,810
казалі аб для падтрымання набораў
Дадзеныя падобных тыпаў дадзеных арганізаваны.

6
00:00:16,810 --> 00:00:19,080
>> Цяпер мы збіраемся казаць
аб некалькіх варыяцый

7
00:00:19,080 --> 00:00:20,330
масіваў і звязаных спісаў.

8
00:00:20,330 --> 00:00:22,362
У гэтым відэа мы збіраемся
казаць пра стэкаў.

9
00:00:22,362 --> 00:00:25,320
У прыватнасці, мы збіраемся казаць
аб структуры дадзеных, названай стос.

10
00:00:25,320 --> 00:00:28,510
Нагадаем, ад папярэдніх абмеркаванняў
аб паказальніках і памяці,

11
00:00:28,510 --> 00:00:32,060
што стэк таксама
Назва для сегмента памяці

12
00:00:32,060 --> 00:00:34,980
дзе статычна аб'яўлена
memory-- памяці, што вы

13
00:00:34,980 --> 00:00:38,730
імя, зменныя, якія вы называеце, і інш
Cetera і функцыянальныя кадры, якія мы таксама

14
00:00:38,730 --> 00:00:41,000
існуюць кадры стэка выклікаў.

15
00:00:41,000 --> 00:00:45,421
Так што гэта структура дадзеных, стэка
ня сегмент стэка памяці.

16
00:00:45,421 --> 00:00:45,920
ДОБРА.

17
00:00:45,920 --> 00:00:46,890
>> Але тое, што стэк?

18
00:00:46,890 --> 00:00:49,220
Так што гэта ў значнай ступені проста
адмысловы выгляд мадэлі

19
00:00:49,220 --> 00:00:51,190
які падтрымлівае дадзеныя ў арганізаваным парадку.

20
00:00:51,190 --> 00:00:53,760
І ёсць два вельмі
агульныя спосабы для рэалізацыі

21
00:00:53,760 --> 00:00:57,380
стэкі з дапамогай двух структур дадзеных
што мы ўжо знаёмыя,

22
00:00:57,380 --> 00:01:00,340
Масівы і звязаныя спісы.

23
00:01:00,340 --> 00:01:04,430
Што робіць стэк спецыяльныя з'яўляецца
спосаб, у якім мы ставім інфармацыі

24
00:01:04,430 --> 00:01:08,200
ў стэк, і, як мы
выдаліць інфармацыю з стэка.

25
00:01:08,200 --> 00:01:11,600
У прыватнасці, у штабелях
гэтае правіла толькі найбольш

26
00:01:11,600 --> 00:01:15,830
нядаўна дадалі элемент можа быць выдалены.

27
00:01:15,830 --> 00:01:17,660
>> Так што падумайце аб гэтым, як быццам гэта стэк.

28
00:01:17,660 --> 00:01:21,170
Мы кладка інфармацыю
на вяршыні сабе,

29
00:01:21,170 --> 00:01:24,271
і толькі рэч, на вяршыні
палі могуць быць выдаленыя.

30
00:01:24,271 --> 00:01:27,020
Мы не можам выдаліць рэч пад
таму што ўсё астатняе будзе

31
00:01:27,020 --> 00:01:28,020
калапс і зваліцца.

32
00:01:28,020 --> 00:01:32,580
Так што мы сапраўды будуем стэк,
мы тады павінны выдаліць па частках.

33
00:01:32,580 --> 00:01:36,590
З-за гэтага мы звычайна называем
да стэку ў якасці мадэлі LIFO,

34
00:01:36,590 --> 00:01:38,940
апошні прыйшоў, першы.

35
00:01:38,940 --> 00:01:42,290
ЛИФО, апошні прыйшоў, першым сышоў.

36
00:01:42,290 --> 00:01:45,635
>> Так з-за гэтага абмежаванні на
як можна дадаць інфармацыю

37
00:01:45,635 --> 00:01:49,080
і выдаляецца з стэка, там сапраўды
толькі дзве рэчы мы можам зрабіць са стэкам.

38
00:01:49,080 --> 00:01:52,010
Мы можам націснуць, які з'яўляецца
тэрмін, які выкарыстоўваецца для дадання

39
00:01:52,010 --> 00:01:55,130
новы элемент у верхняй частцы
стэк, або калі стэк не існуе

40
00:01:55,130 --> 00:01:58,550
і мы ствараем яго з нуля,
стварэнне стэка, у першую чаргу

41
00:01:58,550 --> 00:02:00,110
будзе настойваць.

42
00:02:00,110 --> 00:02:04,990
А потым поп, гэта свайго роду CS
тэрмін, які выкарыстоўваецца для выдалення найбольш нядаўна

43
00:02:04,990 --> 00:02:08,330
дададзены элемент з вяршыні стэка.

44
00:02:08,330 --> 00:02:11,130
>> Такім чынам, мы будзем глядзець на абедзве
рэалізацыі, заснаваныя як масіў

45
00:02:11,130 --> 00:02:13,120
і звязаныя спіс, заснаваны.

46
00:02:13,120 --> 00:02:14,870
І мы збіраемся
пачаць з масівам аснове.

47
00:02:14,870 --> 00:02:19,990
Дык вось асноўная ідэя аб тым, што
структура дадзеных стэка масіў на аснове

48
00:02:19,990 --> 00:02:21,140
будзе выглядаць.

49
00:02:21,140 --> 00:02:23,740
У нас ёсць вызначэнне набранага тут.

50
00:02:23,740 --> 00:02:27,790
Унутры што ў нас ёсць два члены
або поля структуры.

51
00:02:27,790 --> 00:02:29,880
У нас ёсць масіў.

52
00:02:29,880 --> 00:02:32,400
І зноў я з дапамогай
адвольнае тып дадзеных Значэнне.

53
00:02:32,400 --> 00:02:35,180
>> Такім чынам, гэта можа быць любы тып дадзеных,
INT знак ці некаторыя іншыя дадзеныя

54
00:02:35,180 --> 00:02:37,080
увядзіце створанае раней.

55
00:02:37,080 --> 00:02:39,861
Таму ў нас ёсць масіў ёмістасцю памеру.

56
00:02:39,861 --> 00:02:44,010
Ёмістасць быўшы фунт вызначаецца сталай,
магчыма, дзе-то ў нашым файле.

57
00:02:44,010 --> 00:02:47,550
Так ужо заўважыць з гэтым прыватнасці
Рэалізацыя мы якая абмяжоўвае

58
00:02:47,550 --> 00:02:49,800
самі, як правіла, быў
у выпадку з масівамі,

59
00:02:49,800 --> 00:02:53,170
якія мы не можам змяніць памер дынамічна,
дзе ёсць пэўная колькасць

60
00:02:53,170 --> 00:02:55,450
максімуму элементы, якія
мы можам паставіць у нашым стэку.

61
00:02:55,450 --> 00:02:57,930
У дадзеным выпадку гэта элементы ёмістасці.

62
00:02:57,930 --> 00:03:00,310
>> Мы таксама адсочваць
верхняя частка стэка.

63
00:03:00,310 --> 00:03:04,350
Што элементам з'яўляецца самым
нядаўна дадаў у стэк?

64
00:03:04,350 --> 00:03:07,470
І так мы адсочваем, што
ў зменнай называецца верхняй.

65
00:03:07,470 --> 00:03:11,692
І ўсё гэта атрымлівае загорнуты разам
у новы тып дадзеных, званай стэк.

66
00:03:11,692 --> 00:03:13,400
І як толькі вы стварылі мы
гэта новы тып дадзеных

67
00:03:13,400 --> 00:03:15,410
мы можам разглядаць яго як
любы іншы тып дадзеных.

68
00:03:15,410 --> 00:03:20,970
Мы можам аб'явіць стэка S, гэтак жа, як
мы маглі б зрабіць Int х, або сЬаг у.

69
00:03:20,970 --> 00:03:22,990
І калі мы кажам, стэк
з, а тое, што адбываецца

70
00:03:22,990 --> 00:03:26,420
што мы атрымаем набор
ўсталяваць памяць у бок для нас.

71
00:03:26,420 --> 00:03:28,770
>> У гэтым выпадку магутнасць
Я, мабыць, вырашыў

72
00:03:28,770 --> 00:03:33,470
10, таму што я атрымаў
адна пераменная тыпу стэка

73
00:03:33,470 --> 00:03:35,320
які змяшчае два полі памятаю.

74
00:03:35,320 --> 00:03:38,330
Масіў, у дадзеным выпадку адбываецца
быць масівам цэлых лікаў

75
00:03:38,330 --> 00:03:40,440
як у выпадку ў большасці маіх прыкладаў.

76
00:03:40,440 --> 00:03:43,996
І яшчэ цэлая пераменная
здольны захоўваць вяршыні,

77
00:03:43,996 --> 00:03:45,870
найбольш нядаўна дадаў
элемент стэка.

78
00:03:45,870 --> 00:03:50,290
Так адна чарка, што мы
проста вызначаецца як выглядае гэта.

79
00:03:50,290 --> 00:03:53,190
Гэта акно, якое змяшчае
масіў з 10, што

80
00:03:53,190 --> 00:03:57,280
будзе цэлыя лікі ў гэтым выпадку і
іншы цэлая пераменная існуе ў зялёны

81
00:03:57,280 --> 00:04:00,010
для ўказанні вяршыні стэка.

82
00:04:00,010 --> 00:04:02,600
>> Каб ўсталяваць у верхняй частцы
Стэк мы проста кажам s.top.

83
00:04:02,600 --> 00:04:04,890
Вось як мы доступ да
поля структуры водгуку.

84
00:04:04,890 --> 00:04:10,460
s.top роўны 0 эфектыўна
робіць гэта на наш стэк.

85
00:04:10,460 --> 00:04:12,960
Такім чынам, яшчэ раз мы маем дзве аперацыі
што мы можам выканаць у цяперашні час.

86
00:04:12,960 --> 00:04:14,270
Мы можам націснуць, і мы можам поп-музыкі.

87
00:04:14,270 --> 00:04:15,635
Давайце пачнем з штуршка.

88
00:04:15,635 --> 00:04:18,260
Зноў жа, націснуўшы дадае новы
Элемент да вяршыні стэка.

89
00:04:18,260 --> 00:04:21,460
>> Так што мы павінны зрабіць у
гэты масіў рэалізацыя на аснове?

90
00:04:21,460 --> 00:04:23,210
Ну ў агульным,
функцыя проталківанія збіраецца

91
00:04:23,210 --> 00:04:26,160
мець патрэбу, каб прыняць
паказальнік на стэк.

92
00:04:26,160 --> 00:04:28,610
Зараз вазьміце другі і думаць пра гэта.

93
00:04:28,610 --> 00:04:32,840
Чаму мы хацелі б прыняць
паказальнік на стэк?

94
00:04:32,840 --> 00:04:36,830
Нагадаем, ад папярэдніх відэа на
Пераменная маштабы і паказальнікі,

95
00:04:36,830 --> 00:04:42,350
што адбудзецца, калі мы толькі што адправіў
стэк, S, а ў якасці параметру?

96
00:04:42,350 --> 00:04:45,770
Што будзе на самой справе прайшло там?

97
00:04:45,770 --> 00:04:49,430
Памятаеце мы ствараем копію
калі мы перадаць яго ў функцыю

98
00:04:49,430 --> 00:04:51,160
калі мы не выкарыстоўваць паказальнікі.

99
00:04:51,160 --> 00:04:55,380
І таму гэтая функцыя штурхаць патрэбы
прымаць паказальнік на стэк

100
00:04:55,380 --> 00:04:59,160
так што мы на самай справе змены
стэк мы маем намер змяніць.

101
00:04:59,160 --> 00:05:03,060
>> Іншая справа, штуршок, верагодна, хоча, каб
прыняць гэта элемент дадзеных значэнне тыпу.

102
00:05:03,060 --> 00:05:06,970
У гэтым выпадку, зноў жа, цэлы лік,
мы збіраемся дадаць да вяршыні стэка.

103
00:05:06,970 --> 00:05:08,680
Такім чынам, мы атрымалі нашы два параметру.

104
00:05:08,680 --> 00:05:11,310
Што мы збіраемся
Цяпер зрабіць ўнутры штуршок?

105
00:05:11,310 --> 00:05:14,860
Ну, проста, мы проста збіраемся дадаць
гэты элемент у верхняй частцы стэка

106
00:05:14,860 --> 00:05:22,860
а затым змяніць дзе верх
стэк, што S кропка верхняе значэнне.

107
00:05:22,860 --> 00:05:25,639
Так што гэта тое, што функцыя
дэкларацыя штуршок

108
00:05:25,639 --> 00:05:27,680
можа выглядаць у
на аснове масіва рэалізацыя.

109
00:05:27,680 --> 00:05:30,967
>> Зноў жа, гэта не жорсткі і хуткі правіла
што вы маглі б змяніць гэта, і ёсць

110
00:05:30,967 --> 00:05:32,050
гэта вар'іраваць рознымі спосабамі.

111
00:05:32,050 --> 00:05:33,840
Магчыма, ёй аб'яўлена на глабальным узроўні.

112
00:05:33,840 --> 00:05:36,180
І таму вы нават не трэба
прайсці гэта ў якасці параметру.

113
00:05:36,180 --> 00:05:39,125
Гэта зноў толькі
агульны выпадак штуршок.

114
00:05:39,125 --> 00:05:41,000
І ёсць розныя
спосабы яго рэалізацыі.

115
00:05:41,000 --> 00:05:42,810
Але ў гэтым выпадку наша
штуршок збіраецца прыняць

116
00:05:42,810 --> 00:05:48,540
два аргументу, паказальнік на стэк і
элемент дадзеных тыпу значэння, цэлага

117
00:05:48,540 --> 00:05:49,840
у гэтым выпадку.

118
00:05:49,840 --> 00:05:52,100
>> Такім чынам, мы заявілі з, мы
сказаў s.top роўная 0.

119
00:05:52,100 --> 00:05:55,969
Зараз давайце штурхаць
№ 28 у стэк.

120
00:05:55,969 --> 00:05:57,010
Ну што гэта значыць?

121
00:05:57,010 --> 00:05:59,600
Ну ў цяперашні час
Вяршыня стэка 0.

122
00:05:59,600 --> 00:06:01,350
І так, што ў асноўным
адбудзецца гэта

123
00:06:01,350 --> 00:06:05,820
мы збіраемся прытрымлівацца колькасць
28 у масіў размяшчэння 0.

124
00:06:05,820 --> 00:06:09,540
Даволі проста, ці не так, што
быў галоўным, і зараз мы добра ісці.

125
00:06:09,540 --> 00:06:12,910
І тады мы павінны змяніць тое, што
верхняя частка стэка будзе.

126
00:06:12,910 --> 00:06:15,130
Так што ў наступны раз
мы націскаем элемент у,

127
00:06:15,130 --> 00:06:18,017
мы збіраемся захоўваць яго ў
Размяшчэнне масіў, верагодна, не 0.

128
00:06:18,017 --> 00:06:20,100
Мы не хочам, каб перапісаць
што мы проста паставіць там.

129
00:06:20,100 --> 00:06:23,510
І таму мы будзем проста перанесьці зверху 1.

130
00:06:23,510 --> 00:06:24,890
Гэта, верагодна, мае сэнс.

131
00:06:24,890 --> 00:06:28,940
>> Цяпер, калі мы хочам, каб паставіць яшчэ адзін элемент
стэк, што мы хочам, каб падштурхнуць 33,

132
00:06:28,940 --> 00:06:33,190
а зараз мы проста зойме 33
і паклаў яго на масіў колькасці месцазнаходжання

133
00:06:33,190 --> 00:06:37,580
1, а затым змяніць у верхняй частцы нашага
стэк, каб быць масіў размяшчэнне нумар два.

134
00:06:37,580 --> 00:06:40,650
Так што, калі ў наступны раз мы хочам, каб
націснуць элемент у стэк,

135
00:06:40,650 --> 00:06:43,087
ён будзе пакласці ў вочка масіва 2.

136
00:06:43,087 --> 00:06:44,420
І давайце зробім гэта яшчэ раз.

137
00:06:44,420 --> 00:06:45,753
Мы штурхаць 19 ад стэкаў.

138
00:06:45,753 --> 00:06:48,940
Мы пакладзем 19 ў месцы масіва 2
і змяніць у верхняй частцы нашага стэка

139
00:06:48,940 --> 00:06:51,220
быць месца масіў 3
так што калі ў наступны раз мы

140
00:06:51,220 --> 00:06:54,780
трэба зрабіць штуршок, мы добра ісці.

141
00:06:54,780 --> 00:06:56,980
>> ОК, так што штурхае ў двух словах.

142
00:06:56,980 --> 00:06:57,830
Што пра выскокваюць?

143
00:06:57,830 --> 00:07:00,240
Так поппинг з'яўляецца свайго роду
аналаг націску.

144
00:07:00,240 --> 00:07:02,720
Гэта тое, як мы выдаліць дадзеныя з стэка.

145
00:07:02,720 --> 00:07:04,610
І наогул патрэбаў поп
зрабіць наступнае.

146
00:07:04,610 --> 00:07:07,600
Ён павінен прыняць паказальнік на
стэк, зноў у агульным выпадку.

147
00:07:07,600 --> 00:07:10,480
У некаторых іншых выпадках вы маглі
заявілі стэк ў глабальным маштабе,

148
00:07:10,480 --> 00:07:13,910
У гэтым выпадку вам не трэба, каб перадаць яго
У таму што ён ужо мае доступ да яго

149
00:07:13,910 --> 00:07:15,541
як глабальная пераменная.

150
00:07:15,541 --> 00:07:17,040
Але тады, што яшчэ трэба зрабіць?

151
00:07:17,040 --> 00:07:21,000
Ну, мы былі павялічваючы
верхняя частка стэка ў штуршок,

152
00:07:21,000 --> 00:07:24,050
так што мы, верагодна, захочуць
для памяншэння верхняй частцы стэка

153
00:07:24,050 --> 00:07:25,009
ў поп-музыкі, ці не так?

154
00:07:25,009 --> 00:07:26,800
І тады, вядома,
мы таксама збіраемся хацець

155
00:07:26,800 --> 00:07:29,240
каб вярнуць значэнне, што мы выдаліць.

156
00:07:29,240 --> 00:07:32,125
Калі мы дадаем элементы, мы хочам
каб атрымаць элементы з пазней,

157
00:07:32,125 --> 00:07:34,000
мы, верагодна, на самай справе
хочаце захаваць іх, каб мы

158
00:07:34,000 --> 00:07:36,490
не проста выдаляць іх з
стэк, а затым нічога не рабіць з імі.

159
00:07:36,490 --> 00:07:38,500
Наогул, калі мы
штурхаючыся і з'яўляюцца тут

160
00:07:38,500 --> 00:07:41,250
мы хочам, каб захаваць гэта
Інфармацыя асэнсавана

161
00:07:41,250 --> 00:07:43,250
і так не робіць
сэнс толькі выкінуць яго.

162
00:07:43,250 --> 00:07:46,380
Так гэтая функцыя павінна
верагодна, вяртаць значэнне для нас.

163
00:07:46,380 --> 00:07:51,040
>> Так што гэта тое, што дэкларацыю для поп
можа выглядаць там у верхнім левым куце.

164
00:07:51,040 --> 00:07:53,870
Гэтая функцыя вяртае
Дадзеныя значэння тыпу.

165
00:07:53,870 --> 00:07:56,320
Зноў мы выкарыстоўвалі
цэлыя ўсім.

166
00:07:56,320 --> 00:08:01,916
І ён прымае паказальнік на стэк, як
яго адзінага аргументу або адзіным параметрам.

167
00:08:01,916 --> 00:08:03,040
Так што поп збіраецеся рабіць?

168
00:08:03,040 --> 00:08:07,990
Скажам, мы хочам, каб у цяперашні час
поп элемент прэч с.

169
00:08:07,990 --> 00:08:14,000
Так што памятаеце, я сказаў, што стэкі ў мінулым
у, першыя з ЛИФО, структур дадзеных.

170
00:08:14,000 --> 00:08:17,855
Які элемент будзе
быць выдаленыя з стэка?

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
Вы здагадаліся 19?

173
00:08:24,150 --> 00:08:25,290
Таму што вы былі б правы.

174
00:08:25,290 --> 00:08:28,836
19 быў апошні элемент, мы дадалі да
стэк, калі мы штурхалі элементы на,

175
00:08:28,836 --> 00:08:31,210
і так што гэта на першы
элемент, які атрымлівае выдаленыя.

176
00:08:31,210 --> 00:08:34,780
Гэта як калі б мы сказалі, 28, і
Затым пакласці 33 на ім,

177
00:08:34,780 --> 00:08:36,659
і пакласці 19 на вяршыні, што.

178
00:08:36,659 --> 00:08:40,650
Адзіны элемент, мы можам зняць гэта 19.

179
00:08:40,650 --> 00:08:45,019
>> Зараз у дыяграме тут, што я зрабіў
з'яўляецца свайго роду выдаленыя 19 з масіва.

180
00:08:45,019 --> 00:08:46,810
Гэта на самай справе не
тое, што мы збіраемся зрабіць.

181
00:08:46,810 --> 00:08:48,934
Мы проста збіраемся роду
з прыкінуцца, што гэта не існуе.

182
00:08:48,934 --> 00:08:51,441
Ён па-ранейшаму там, у
што вочка памяці,

183
00:08:51,441 --> 00:08:54,190
але мы толькі збіраемся ігнараваць
шляхам змены верхняй частцы стэка нашай

184
00:08:54,190 --> 00:08:56,080
ад таго, з 3 па 2.

185
00:08:56,080 --> 00:08:58,720
Так што, калі мы павінны былі падштурхнуць Цяпер
іншы элемент у стэк,

186
00:08:58,720 --> 00:09:00,720
было б больш пісаць 19.

187
00:09:00,720 --> 00:09:03,990
>> Але давайце не будзем прайсці праз цяжкасці
выдалення 19 з чаркі.

188
00:09:03,990 --> 00:09:05,830
Мы можам толькі рабіць выгляд, што не існуе.

189
00:09:05,830 --> 00:09:11,107
Для мэт стэка яго няма, калі
Мы змяніць верхнюю быць 2 замест 3.

190
00:09:11,107 --> 00:09:12,690
Добра, так што гэта было даволі шмат яго.

191
00:09:12,690 --> 00:09:15,080
Гэта ўсё, што нам трэба зрабіць,
поп элемент выключаны.

192
00:09:15,080 --> 00:09:16,090
Давайце зробім гэта зноў.

193
00:09:16,090 --> 00:09:18,610
Так я вылучыў яго чырвоным тут, каб
паказваюць, што мы робім яшчэ адзін званок.

194
00:09:18,610 --> 00:09:19,720
Мы збіраемся зрабіць тое ж самае.

195
00:09:19,720 --> 00:09:20,803
>> Так што ж адбываецца далей?

196
00:09:20,803 --> 00:09:23,670
Ну, мы збіраемся захоўваць
33 х, і мы збіраемся

197
00:09:23,670 --> 00:09:26,217
змяніць вяршыні стэка 1.

198
00:09:26,217 --> 00:09:29,050
Так што, калі мы былі цяпер выпхнуць
элемент у стэк, які мы знаходзімся

199
00:09:29,050 --> 00:09:31,610
збіраецца зрабіць прама цяпер,
што адбудзецца

200
00:09:31,610 --> 00:09:36,367
з'яўляецца мы збіраемся перазапісу
Масіў месца № 1.

201
00:09:36,367 --> 00:09:38,950
Так што 33, што было свайго роду пакінулі
за што мы толькі рабілі выгляд,

202
00:09:38,950 --> 00:09:44,390
не існуе больш, мы толькі збіраемся
калашмаціць яго і пакласці 40 там замест.

203
00:09:44,390 --> 00:09:46,290
І тады, вядома,
Так як мы зрабілі штуршок,

204
00:09:46,290 --> 00:09:48,780
мы збіраемся, каб павялічыць
Вяршыня стэка ад 1 да 2

205
00:09:48,780 --> 00:09:50,950
так што калі мы цяпер дадаць
іншы элемент гэта будзе

206
00:09:50,950 --> 00:09:54,700
перайсці ў масіў месцазнаходжання нумар два.

207
00:09:54,700 --> 00:09:57,590
>> Цяпер, звязаныя спісы іншы
спосаб рэалізацыі стэкаў.

208
00:09:57,590 --> 00:10:01,210
І калі гэта вызначэнне на
Экран тут выглядае знаёмым для вас,

209
00:10:01,210 --> 00:10:04,260
гэта таму, што ён выглядае амаль
сапраўды гэтак жа, па сутнасці,

210
00:10:04,260 --> 00:10:07,790
гэта ў значнай ступені з'яўляецца менавіта
гэтак жа, як аднаразова звязанага спісу,

211
00:10:07,790 --> 00:10:11,990
калі вы памятаеце з нашага абмеркавання
односвязанны спісы ў іншым відэа.

212
00:10:11,990 --> 00:10:15,510
Адзінае абмежаванне тут
для нас, як праграмістаў,

213
00:10:15,510 --> 00:10:17,900
мы не дазволілі
ўставіць або выдаліць выпадкова

214
00:10:17,900 --> 00:10:20,620
ад аднакратна звязанага спісу
якія мы маглі б зрабіць раней.

215
00:10:20,620 --> 00:10:25,820
Толькі цяпер мы можам ўстаўляць і выдаляць з
пярэдняя або верхняя звязаны

216
00:10:25,820 --> 00:10:26,320
Спіс.

217
00:10:26,320 --> 00:10:28,028
Гэта сапраўды толькі
Розніца ж.

218
00:10:28,028 --> 00:10:29,700
Гэта ў адваротным выпадку аднакратна звязаны спіс.

219
00:10:29,700 --> 00:10:32,060
Гэта толькі абмежаванне
замена на сябе

220
00:10:32,060 --> 00:10:35,770
як праграмісты, што
змяняе яго ў чарку.

221
00:10:35,770 --> 00:10:39,280
>> Правіла тут заўсёды падтрымліваць
паказальнік на галаву звязанага спісу.

222
00:10:39,280 --> 00:10:41,520
Гэта, вядома, у агульным
важнае правіла ў першую чаргу.

223
00:10:41,520 --> 00:10:44,260
Для односвязанны спіс у любым выпадку вам
трэба толькі паказальнік на галаву

224
00:10:44,260 --> 00:10:46,160
для таго, каб мець, што
ланцужок павінна быць у стане звярнуцца

225
00:10:46,160 --> 00:10:48,596
да кожнага іншага элемента
у звязаным спісе.

226
00:10:48,596 --> 00:10:50,470
Але гэта прыватнасці,
Важна са стэкам.

227
00:10:50,470 --> 00:10:52,386
І так наогул вы
адбываецца на самай справе хочуць

228
00:10:52,386 --> 00:10:54,090
гэты паказальнік, каб быць глабальнай зменнай.

229
00:10:54,090 --> 00:10:56,574
Гэта, верагодна, будзе
яшчэ прасцей.

230
00:10:56,574 --> 00:10:58,240
Так якія аналагі штуршок і поп?

231
00:10:58,240 --> 00:10:58,740
Права.

232
00:10:58,740 --> 00:11:01,812
Так штурхае зноў дадае
новы элемент у стэк.

233
00:11:01,812 --> 00:11:03,770
У звязаным спісе
азначае, што мы будзем мець

234
00:11:03,770 --> 00:11:07,770
каб стварыць новы вузел, што мы
збіраемся дадаць у звязаным спісе,

235
00:11:07,770 --> 00:11:10,500
і вынікайце асцярожныя крокі
што мы прыводзім раней

236
00:11:10,500 --> 00:11:16,050
паасобку, звязаных спісаў, каб дадаць яго ў
ланцуг без разрыву ланцугу

237
00:11:16,050 --> 00:11:18,900
і страты або сіротамі любы
элементы звязанага спісу.

238
00:11:18,900 --> 00:11:21,820
І гэта ў асноўным тое, што, што
трохі кропля тэксту ёсць абагульняе.

239
00:11:21,820 --> 00:11:23,740
І давайце зірнем
ў яго ў выглядзе дыяграмы.

240
00:11:23,740 --> 00:11:24,823
>> Дык вось наш звязаны спіс.

241
00:11:24,823 --> 00:11:26,620
Гэта адначасова змяшчае чатыры элемента.

242
00:11:26,620 --> 00:11:30,420
І яшчэ выдатна Вось наш
стэк, які змяшчае чатыры элемента.

243
00:11:30,420 --> 00:11:36,030
І давайце казаць, што мы цяпер хочам
націснуць новы элемент на гэтым стэку.

244
00:11:36,030 --> 00:11:39,792
І мы хочам, каб падштурхнуць новае
Пункт чые дадзеныя значэнне 12.

245
00:11:39,792 --> 00:11:41,000
Ну, што мы будзем рабіць?

246
00:11:41,000 --> 00:11:43,420
Ну па-першае, мы збіраемся
Таноса прастору, дынамічна

247
00:11:43,420 --> 00:11:45,411
вылучыць месца для новага вузла.

248
00:11:45,411 --> 00:11:48,160
І, вядома, адразу ж пасля
мы зрабіць выклік Таноса мы заўсёды

249
00:11:48,160 --> 00:11:52,989
пераканайцеся, што для праверкі нуль,
таму што, калі мы атрымалі нулявы таму

250
00:11:52,989 --> 00:11:54,280
была нейкая праблема.

251
00:11:54,280 --> 00:11:57,570
Мы не хочам, каб разнаймення NULL гэтым
паказальнік ці вы будзеце пакутаваць няспраўнасць SEG.

252
00:11:57,570 --> 00:11:58,510
Гэта не добра.

253
00:11:58,510 --> 00:11:59,760
Такім чынам, мы malloced вузла.

254
00:11:59,760 --> 00:12:01,260
Мы будзем лічыць, што мы мелі поспех тут.

255
00:12:01,260 --> 00:12:06,090
Мы збіраемся паставіць 12 у
поле дадзеных гэтага вузла.

256
00:12:06,090 --> 00:12:11,570
Цяпер вы можаце ўспомніць, якія з нашых паказальнікаў
рухаецца побач, таму мы не разарваць ланцуг?

257
00:12:11,570 --> 00:12:15,100
У нас ёсць некалькі варыянтаў, але тут
адзінае, што адбываецца, каб быць бяспечным

258
00:12:15,100 --> 00:12:19,330
гэта ўсталяваць навіна наступная паказальнік
кропка ў старым чале спісу

259
00:12:19,330 --> 00:12:21,360
або тое, што хутка будзе
стары галава спісу.

260
00:12:21,360 --> 00:12:23,610
І цяпер, калі ўсе нашы
элементы злучаныя адзін з адным,

261
00:12:23,610 --> 00:12:27,370
мы можам проста перайсці спіс, каб паказаць
у тое ж месца, што новы робіць.

262
00:12:27,370 --> 00:12:33,550
І мы ў цяперашні час эфектыўна штурхнуў
Новы элемент на пярэдняй частцы стэка.

263
00:12:33,550 --> 00:12:36,420
>> Каб вылучыць Мы проста хочам
выдаліць гэта першы элемент.

264
00:12:36,420 --> 00:12:38,150
І так у асноўным тое, што
мы павінны зрабіць тут,

265
00:12:38,150 --> 00:12:40,050
а мы павінны знайсці другі элемент.

266
00:12:40,050 --> 00:12:43,540
У рэшце рэшт, што стане новым
галаву пасля таго як мы выдаліць першы.

267
00:12:43,540 --> 00:12:47,300
Так што мы проста павінны пачаць з
пачатак, рух на адну пазіцыю наперад.

268
00:12:47,300 --> 00:12:50,340
Пасля таго, як мы атрымалі правесці на адным
наперад, дзе мы ў цяперашні час

269
00:12:50,340 --> 00:12:53,850
мы можам выдаліць першы бяспечна
і тады мы можам проста перанесьці галаву

270
00:12:53,850 --> 00:12:57,150
паказаць на тое, што быў
Другі член, а затым у цяперашні час

271
00:12:57,150 --> 00:12:59,170
першы пасля гэтага
Вузел быў выдалены.

272
00:12:59,170 --> 00:13:01,160
>> Такім чынам, яшчэ раз, зірнуць
на яго як на дыяграме мы

273
00:13:01,160 --> 00:13:05,022
Цяпер хачу, каб поп
элемент з гэтага стэка.

274
00:13:05,022 --> 00:13:05,730
Дык што ж нам рабіць?

275
00:13:05,730 --> 00:13:08,188
Ну вы ў першую чаргу мы збіраемся стварыць
новы паказальнік, які збіраецца

276
00:13:08,188 --> 00:13:10,940
каб паказаць на тым жа месцы, у галаве.

277
00:13:10,940 --> 00:13:13,790
Мы збіраемся, каб перанесьці яго на адну пазіцыю
наперад, кажучы TRAV роўных

278
00:13:13,790 --> 00:13:17,510
TRAV побач, напрыклад, што
будзе прасоўваць паказальнік траву адзін

279
00:13:17,510 --> 00:13:19,324
Становішча наперад.

280
00:13:19,324 --> 00:13:21,240
Цяпер, калі мы атрымалі
правесці на першым элеменце

281
00:13:21,240 --> 00:13:24,573
праз паказальнік называецца спісу, а
Другі элемент з дапамогай паказальніка называецца

282
00:13:24,573 --> 00:13:28,692
Траў, мы можам бяспечна выдаліць, што
Першы элемент з стэка

283
00:13:28,692 --> 00:13:30,650
без страты астатніх
ланцуга, таму што мы

284
00:13:30,650 --> 00:13:32,358
ёсць спосаб спаслацца
на другі элемент

285
00:13:32,358 --> 00:13:34,780
наперад па шляху
паказальнік называецца TRAV.

286
00:13:34,780 --> 00:13:37,100
>> Так што цяпер мы можам вызваліць гэты вузел.

287
00:13:37,100 --> 00:13:38,404
Мы можам вызваліць спіс.

288
00:13:38,404 --> 00:13:41,320
І тады ўсё, што мы павінны зрабіць цяпер, гэта
рухацца спіс кропкі ў тое ж месца

289
00:13:41,320 --> 00:13:44,482
што робіць Trav, і мы накшталт таму
дзе мы пачалі, перш чым мы штурхнуў 12

290
00:13:44,482 --> 00:13:45,690
на, у першую чаргу, правільна.

291
00:13:45,690 --> 00:13:46,940
Гэта дакладна, дзе мы былі.

292
00:13:46,940 --> 00:13:48,840
У нас быў гэты стэк чатырох элементаў.

293
00:13:48,840 --> 00:13:49,690
Мы дадалі пяты.

294
00:13:49,690 --> 00:13:51,910
Мы штурхнуў пятую
элемент на, і затым мы

295
00:13:51,910 --> 00:13:55,980
выскачыў, што ў апошні час
дадаў элемент адступіць.

296
00:13:55,980 --> 00:13:58,816
>> Гэта сапраўды вельмі шмат
усё, што ёсць у стэкі.

297
00:13:58,816 --> 00:14:00,190
Вы можаце рэалізаваць іх у выглядзе масіваў.

298
00:14:00,190 --> 00:14:01,815
Вы можаце рэалізаваць іх у выглядзе звязаных спісаў.

299
00:14:01,815 --> 00:14:04,810
Ёсць, вядома, і іншыя
спосабы іх рэалізацыі, а таксама.

300
00:14:04,810 --> 00:14:09,060
У асноўным па гэтай прычыне мы павінны выкарыстоўваць
стэкі з'яўляецца падтрыманне дадзеных такім чынам,

301
00:14:09,060 --> 00:14:12,090
што ў апошні час дадаў
элемент гэта першае, што мы

302
00:14:12,090 --> 00:14:14,980
захочуць вярнуцца.

303
00:14:14,980 --> 00:14:17,900
Я Дуг Лойд, гэта CS50.

304
00:14:17,900 --> 00:14:19,926