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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Wszystko w porządku,
więc przez ten punkt jesteś

3
00:00:05,990 --> 00:00:09,020
chyba dość znajomo
z tablicami i powiązanych list

4
00:00:09,020 --> 00:00:10,950
która jest dwa podstawowe
struktury danych mamy

5
00:00:10,950 --> 00:00:16,810
mówił o do przechowywania zestawów
Dane podobnych typów danych zorganizowane.

6
00:00:16,810 --> 00:00:19,080
>> Teraz będziemy rozmawiać
o kilku wariantach

7
00:00:19,080 --> 00:00:20,330
na tablicach i połączonych listach.

8
00:00:20,330 --> 00:00:22,362
W tym filmie mamy zamiar
mówić o stosach.

9
00:00:22,362 --> 00:00:25,320
W szczególności będziemy rozmawiać
o strukturę danych zwaną stos.

10
00:00:25,320 --> 00:00:28,510
Przypomnijmy, od poprzednich dyskusjach
o wskaźniki i pamięci,

11
00:00:28,510 --> 00:00:32,060
że stos jest również
nazwa dla segmentu pamięci

12
00:00:32,060 --> 00:00:34,980
gdzie statycznie oświadczył
Pamięć memory--, że cię

13
00:00:34,980 --> 00:00:38,730
wymienić, zmienne, że nazwa, i
cetera i funkcji ramki, które również

14
00:00:38,730 --> 00:00:41,000
istnieją połączenia ramki stosu.

15
00:00:41,000 --> 00:00:45,421
Więc jest to struktura danych stos
Nie segment stosu pamięci.

16
00:00:45,421 --> 00:00:45,920
OK.

17
00:00:45,920 --> 00:00:46,890
>> Ale co to jest stos?

18
00:00:46,890 --> 00:00:49,220
Więc jest to dość dużo tylko
Specjalny rodzaj konstrukcji

19
00:00:49,220 --> 00:00:51,190
który utrzymuje dane w sposób zorganizowany.

20
00:00:51,190 --> 00:00:53,760
I nie ma dwóch bardzo
wspólne sposoby realizacji

21
00:00:53,760 --> 00:00:57,380
stosy za pomocą dwóch struktur danych
że jesteśmy już znane,

22
00:00:57,380 --> 00:01:00,340
tablice i związane listy.

23
00:01:00,340 --> 00:01:04,430
Co sprawia, że ​​specjalny stos jest
sposób, w jaki możemy umieścić informacje

24
00:01:04,430 --> 00:01:08,200
w stos, i sposób, w jaki
usunięcia informacji ze stosu.

25
00:01:08,200 --> 00:01:11,600
W szczególności w stosy
zasada jest tylko najbardziej

26
00:01:11,600 --> 00:01:15,830
Ostatnio dodany element może zostać usunięty.

27
00:01:15,830 --> 00:01:17,660
>> Więc pomyśl o tym tak, jakby to stos.

28
00:01:17,660 --> 00:01:21,170
Jesteśmy palowania informacji
na szczycie sobie,

29
00:01:21,170 --> 00:01:24,271
i tylko co na górze
stosu mogą być usunięte.

30
00:01:24,271 --> 00:01:27,020
Nie możemy usunąć coś pod spodem
bo wszystko inne będzie

31
00:01:27,020 --> 00:01:28,020
zwinąć i przewrócić.

32
00:01:28,020 --> 00:01:32,580
Tak naprawdę budują stosu,
następnie musimy usunąć kawałek po kawałku.

33
00:01:32,580 --> 00:01:36,590
W związku z tym, że często odnoszą
do komina jako struktury LIFO

34
00:01:36,590 --> 00:01:38,940
trwać, pierwsze wyszło.

35
00:01:38,940 --> 00:01:42,290
LIFO, trwać, pierwsze wyszło.

36
00:01:42,290 --> 00:01:45,635
>> Tak więc z powodu tego ograniczenia
jak informacja może być dodany do

37
00:01:45,635 --> 00:01:49,080
i usunięte ze stosu, tam naprawdę
tylko dwie rzeczy, które możemy zrobić ze stosem.

38
00:01:49,080 --> 00:01:52,010
Możemy wcisnąć, który jest
Termin używamy do dodawania

39
00:01:52,010 --> 00:01:55,130
Nowym elementem na szczycie
stosu lub gdy papier nie istnieją

40
00:01:55,130 --> 00:01:58,550
i tworzymy od podstaw,
tworząc stos w pierwszej kolejności

41
00:01:58,550 --> 00:02:00,110
byłoby pchania.

42
00:02:00,110 --> 00:02:04,990
I wtedy pojawiają, to jest coś w rodzaju CS
Termin używamy usunąć ostatnio

43
00:02:04,990 --> 00:02:08,330
dodatkowy element z górnej części stosu.

44
00:02:08,330 --> 00:02:11,130
>> Tak więc mamy zamiar spojrzeć na oba
implementacje oparte zarówno tablica

45
00:02:11,130 --> 00:02:13,120
i połączone lista oparta.

46
00:02:13,120 --> 00:02:14,870
I będziemy
początek tablicy opartej.

47
00:02:14,870 --> 00:02:19,990
Tak tu jest podstawowa idea tego, co
struktura danych Stos układów w oparciu

48
00:02:19,990 --> 00:02:21,140
będzie wyglądać.

49
00:02:21,140 --> 00:02:23,740
Mamy tu definicję wpisywanych.

50
00:02:23,740 --> 00:02:27,790
Wewnątrz, że mamy dwóch członków
lub obszary struktury.

51
00:02:27,790 --> 00:02:29,880
Mamy tablicę.

52
00:02:29,880 --> 00:02:32,400
I znowu Używam
dowolna wartość typu danych.

53
00:02:32,400 --> 00:02:35,180
>> Więc może to być dowolny typ danych,
int char lub inne dane

54
00:02:35,180 --> 00:02:37,080
wpisz utworzony wcześniej.

55
00:02:37,080 --> 00:02:39,861
Więc mamy tablicę pojemności wielkości.

56
00:02:39,861 --> 00:02:44,010
Pojemność jest funt zdefiniowane stała,
może gdzieś indziej w naszym pliku.

57
00:02:44,010 --> 00:02:47,550
Więc zauważyć już w ten szczególny
Realizacja jesteśmy ograniczające

58
00:02:47,550 --> 00:02:49,800
sami, jak to zwykle
w przypadku tablic,

59
00:02:49,800 --> 00:02:53,170
których nie możemy dynamicznie zmieniać rozmiar,
gdzie istnieje pewna liczba

60
00:02:53,170 --> 00:02:55,450
maksimum elementów, które
możemy umieścić w naszym stosie.

61
00:02:55,450 --> 00:02:57,930
W tym przypadku jest to elementy pojemności.

62
00:02:57,930 --> 00:03:00,310
>> Mamy również śledzić
wierzchołek stosu.

63
00:03:00,310 --> 00:03:04,350
Element co jest najbardziej
Ostatnio dodania do stosu?

64
00:03:04,350 --> 00:03:07,470
A więc śledzić, że
w zmienną górze.

65
00:03:07,470 --> 00:03:11,692
A wszystko to zostanie opakowane razem
do nowego typu danych o nazwie stos.

66
00:03:11,692 --> 00:03:13,400
A kiedy jesteśmy stworzone
ten nowy typ danych

67
00:03:13,400 --> 00:03:15,410
możemy traktować jak
innego rodzaju danych.

68
00:03:15,410 --> 00:03:20,970
Możemy zadeklarować stosu s, podobnie jak
możemy zrobić, int lub char x, y.

69
00:03:20,970 --> 00:03:22,990
A kiedy mówimy stos
s, dobrze, co się dzieje

70
00:03:22,990 --> 00:03:26,420
jest dostajemy zestaw
Pamięć zarezerwowana dla nas.

71
00:03:26,420 --> 00:03:28,770
>> W tym charakterze przypadku
Ja najwyraźniej postanowił

72
00:03:28,770 --> 00:03:33,470
10 ponieważ ja dostałem
pojedyncza zmienna typu stos

73
00:03:33,470 --> 00:03:35,320
która zawiera dwa pola przypomnieć.

74
00:03:35,320 --> 00:03:38,330
Tablica, w tym przypadku będzie
być tablicą liczb całkowitych

75
00:03:38,330 --> 00:03:40,440
jak to jest w przypadku większości moich przykładach.

76
00:03:40,440 --> 00:03:43,996
I kolejna zmienna całkowita
zdolne do przechowywania górę,

77
00:03:43,996 --> 00:03:45,870
ostatnio dodany
element stosu.

78
00:03:45,870 --> 00:03:50,290
Więc jeden stos, co
po prostu zdefiniowane wygląda następująco.

79
00:03:50,290 --> 00:03:53,190
Jest to skrzynka
tablica 10, co

80
00:03:53,190 --> 00:03:57,280
będą liczbami całkowitymi w tym przypadku i
kolejna zmienna istnieje liczba całkowita w zielone

81
00:03:57,280 --> 00:04:00,010
wskazanie górnej części stosu.

82
00:04:00,010 --> 00:04:02,600
>> Aby ustawić górze
Stos po prostu powiedzieć, s.top.

83
00:04:02,600 --> 00:04:04,890
W ten sposób możemy uzyskać dostęp do
pole wycofania struktury.

84
00:04:04,890 --> 00:04:10,460
s.top równa 0 skutecznie
robi to do naszego stosu.

85
00:04:10,460 --> 00:04:12,960
Więc znowu mamy dwie operacje
które możemy wykonać teraz.

86
00:04:12,960 --> 00:04:14,270
Możemy wcisnąć i możemy pop.

87
00:04:14,270 --> 00:04:15,635
Zacznijmy naciśnięciem.

88
00:04:15,635 --> 00:04:18,260
Ponownie, spychając jest dodanie nowego
Element na górze stosu.

89
00:04:18,260 --> 00:04:21,460
>> Więc co trzeba zrobić w
Realizacja na podstawie tej tablicy?

90
00:04:21,460 --> 00:04:23,210
Cóż w ogóle
Funkcja Push będzie

91
00:04:23,210 --> 00:04:26,160
potrzebować do zaakceptowania
Wskaźnik do stosu.

92
00:04:26,160 --> 00:04:28,610
Teraz Poświęć chwilę i pomyśl o tym.

93
00:04:28,610 --> 00:04:32,840
Dlatego chcielibyśmy, aby zaakceptować
wskaźnik do stosu?

94
00:04:32,840 --> 00:04:36,830
Przypomnijmy, od poprzednich filmów na
zmienny zakres i wskaźniki,

95
00:04:36,830 --> 00:04:42,350
co się stanie, jeśli po prostu wysłany
Stos, s, a jako parametr?

96
00:04:42,350 --> 00:04:45,770
Co by rzeczywiście być przekazywane tam?

97
00:04:45,770 --> 00:04:49,430
Pamiętaj, tworzymy kopię
kiedy przekazać go do funkcji

98
00:04:49,430 --> 00:04:51,160
chyba że używamy wskazówek.

99
00:04:51,160 --> 00:04:55,380
I tak ta funkcja pchania potrzeb
przyjąć wskaźnik do stosu

100
00:04:55,380 --> 00:04:59,160
tak, że jesteśmy rzeczywiście się zmienia
stos zamierzamy zmienić.

101
00:04:59,160 --> 00:05:03,060
>> Inna sprawa, Push prawdopodobnie chce
zaakceptować to element danych wartości typu.

102
00:05:03,060 --> 00:05:06,970
W tym przypadku znowu liczbą całkowitą
mamy zamiar dodać do szczytu stosu.

103
00:05:06,970 --> 00:05:08,680
Mamy więc nasze dwa parametry.

104
00:05:08,680 --> 00:05:11,310
Co my teraz
teraz zrobić wewnątrz push?

105
00:05:11,310 --> 00:05:14,860
Cóż, po prostu, po prostu zamiar dodać
ten element na wierzchu stosu

106
00:05:14,860 --> 00:05:22,860
a następnie zmienić w którym góra
stos jest, że s dot najwyższą wartość.

107
00:05:22,860 --> 00:05:25,639
Więc to jest to, co funkcja
zgłoszenie o naciśnięciem

108
00:05:25,639 --> 00:05:27,680
może wyglądać w sposób
Tablica oparte wdrożenie.

109
00:05:27,680 --> 00:05:30,967
>> Znowu nie jest to twardy i szybki przepis
że można to zmienić i mieć

110
00:05:30,967 --> 00:05:32,050
się zmieniać na różne sposoby.

111
00:05:32,050 --> 00:05:33,840
Być może ów jest uznany na całym świecie.

112
00:05:33,840 --> 00:05:36,180
A więc nawet nie trzeba
przekazać to jako parametr.

113
00:05:36,180 --> 00:05:39,125
To znowu tylko
Ogólnie przypadku naciśnięciem.

114
00:05:39,125 --> 00:05:41,000
I tam są różne
sposoby jego realizacji.

115
00:05:41,000 --> 00:05:42,810
Ale w tym przypadku nasze
Push zajmie

116
00:05:42,810 --> 00:05:48,540
dwa argumenty, wskaźnik do stosu i
element danych wartości typu, Integer

117
00:05:48,540 --> 00:05:49,840
w tym przypadku.

118
00:05:49,840 --> 00:05:52,100
>> Więc oświadczył s, możemy
powiedział s.top równa 0.

119
00:05:52,100 --> 00:05:55,969
Teraz nacisnąć
Numer 28 na stos.

120
00:05:55,969 --> 00:05:57,010
Cóż, co to znaczy?

121
00:05:57,010 --> 00:05:59,600
Cóż obecnie
Szczyt stosu jest 0.

122
00:05:59,600 --> 00:06:01,350
A więc to, co jest w zasadzie
stanie się to

123
00:06:01,350 --> 00:06:05,820
będziemy trzymać numer
28 na miejscu tablicy 0.

124
00:06:05,820 --> 00:06:09,540
Całkiem proste, prawda, że
była najlepiej i teraz jesteśmy dobrze iść.

125
00:06:09,540 --> 00:06:12,910
I wtedy musimy zmienić to, co
wierzchołek stosu będzie.

126
00:06:12,910 --> 00:06:15,130
Tak, że następnym razem
my pchamy element w,

127
00:06:15,130 --> 00:06:18,017
mamy zamiar przechowywać w
położenie tablicy, prawdopodobnie nie 0.

128
00:06:18,017 --> 00:06:20,100
Nie chcemy, aby zastąpić
co po prostu umieścić tam.

129
00:06:20,100 --> 00:06:23,510
A więc musimy po prostu przenieść góry do 1.

130
00:06:23,510 --> 00:06:24,890
To chyba ma sens.

131
00:06:24,890 --> 00:06:28,940
>> Teraz, jeśli chcemy umieścić kolejny element
na stosie, że chcemy wcisnąć 33,

132
00:06:28,940 --> 00:06:33,190
a teraz jesteśmy po prostu zajmie 33
i umieścić go na tablicy liczby lokalizacji

133
00:06:33,190 --> 00:06:37,580
1, a następnie zmienić szczycie naszej
układać się tablica numer lokalizacji dwóch.

134
00:06:37,580 --> 00:06:40,650
Jeśli więc następnym razem chcemy
wcisnąć element na stosie

135
00:06:40,650 --> 00:06:43,087
to będzie umieścić w miejscu tablicy 2.

136
00:06:43,087 --> 00:06:44,420
I zróbmy to jeszcze raz.

137
00:06:44,420 --> 00:06:45,753
Będziemy naciskać 19 off stosów.

138
00:06:45,753 --> 00:06:48,940
Umieścimy 19 w miejscu tablicy 2
i zmienić na szczyt naszej stosie

139
00:06:48,940 --> 00:06:51,220
być lokalizacja tablicy 3
więc jeśli w czasie następnego my

140
00:06:51,220 --> 00:06:54,780
trzeba zrobić push jesteśmy dobrze iść.

141
00:06:54,780 --> 00:06:56,980
>> OK, tak że pcha w pigułce.

142
00:06:56,980 --> 00:06:57,830
Co popping?

143
00:06:57,830 --> 00:07:00,240
Więc popping jest to rodzaj
odpowiednik pchania.

144
00:07:00,240 --> 00:07:02,720
To, w jaki sposób usunąć dane ze stosu.

145
00:07:02,720 --> 00:07:04,610
A w ogólnych potrzeb pop
wykonać następujące czynności.

146
00:07:04,610 --> 00:07:07,600
Trzeba przyjąć wskaźnik do
stosu, również w przypadku ogólnym.

147
00:07:07,600 --> 00:07:10,480
W innym przypadku może
zadeklarowały stos na całym świecie,

148
00:07:10,480 --> 00:07:13,910
w takim przypadku nie ma potrzeby, aby go zdać
w, bo już ma do niego dostęp

149
00:07:13,910 --> 00:07:15,541
jako zmienną globalną.

150
00:07:15,541 --> 00:07:17,040
Ale to, co jeszcze musimy zrobić?

151
00:07:17,040 --> 00:07:21,000
Cóż my zwiększając
wierzchołek stosu w dostarczaniu,

152
00:07:21,000 --> 00:07:24,050
więc jesteśmy prawdopodobnie będzie chciał
aby zmniejszyć górną stosu

153
00:07:24,050 --> 00:07:25,009
w pop, prawda?

154
00:07:25,009 --> 00:07:26,800
I wtedy oczywiście
jesteśmy również będzie chciał

155
00:07:26,800 --> 00:07:29,240
do zwrotu wartości, które usunąć.

156
00:07:29,240 --> 00:07:32,125
Jeśli dodajemy elementy, chcemy
aby elementy się później,

157
00:07:32,125 --> 00:07:34,000
prawdopodobnie w rzeczywistości
Aby zapisać je więc

158
00:07:34,000 --> 00:07:36,490
nie po prostu usunąć je z
stos, a następnie zrobić nic z nimi.

159
00:07:36,490 --> 00:07:38,500
Generalnie, jeśli będziemy
pchania i popping tutaj

160
00:07:38,500 --> 00:07:41,250
chcemy zapisać to
Informacje w znaczący sposób

161
00:07:41,250 --> 00:07:43,250
i tak to nie ma
sensu po prostu wyrzucić.

162
00:07:43,250 --> 00:07:46,380
Tak więc funkcja ta powinna
Prawdopodobnie zwracają wartość do nas.

163
00:07:46,380 --> 00:07:51,040
>> Tak to jest, co do deklaracji dla pop
może wyglądać nie w lewym górnym rogu.

164
00:07:51,040 --> 00:07:53,870
Ta funkcja zwraca
Dane wartości wpisz.

165
00:07:53,870 --> 00:07:56,320
Znowu byliśmy przy użyciu
liczb całkowitych w całym.

166
00:07:56,320 --> 00:08:01,916
I przyjmuje wskaźnik do stosu jako
jego jedynym argumentem lub jedynym parametrem.

167
00:08:01,916 --> 00:08:03,040
Więc co jest pop zamierza zrobić?

168
00:08:03,040 --> 00:08:07,990
Powiedzmy, że chcemy teraz
pop element off s.

169
00:08:07,990 --> 00:08:14,000
Więc pamiętaj, powiedziałem, że stosy są w zeszłym
, pierwsze wyszło, LIFO struktur danych.

170
00:08:14,000 --> 00:08:17,855
Który element będzie
usunięte ze stosu?

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

172
00:08:21,780 --> 00:08:24,150
Czy domyślasz 19?

173
00:08:24,150 --> 00:08:25,290
Dlatego, że masz rację.

174
00:08:25,290 --> 00:08:28,836
19 był ostatnim elementem dodaliśmy do
stos, kiedy pchali elementy, na,

175
00:08:28,836 --> 00:08:31,210
i tak to będzie pierwszy
elementem, który zostanie usunięty.

176
00:08:31,210 --> 00:08:34,780
To tak, jakbyśmy powiedział 28 oraz
następnie umieścić 33 na nim,

177
00:08:34,780 --> 00:08:36,659
i umieścić 19 na dodatek.

178
00:08:36,659 --> 00:08:40,650
Jedynym elementem, możemy zdjąć jest 19.

179
00:08:40,650 --> 00:08:45,019
>> Teraz w schemacie tutaj co zrobiłem
jest rodzajem usunięty 19 z tablicy.

180
00:08:45,019 --> 00:08:46,810
To nie jest właściwie
co będziemy robić.

181
00:08:46,810 --> 00:08:48,934
Jesteśmy po prostu się do rodzaju
z udawać, że nie ma.

182
00:08:48,934 --> 00:08:51,441
To jeszcze nie w
że miejsce w pamięci,

183
00:08:51,441 --> 00:08:54,190
ale jesteśmy po prostu będzie go zignorować
zmieniając jeszcze wierzchołka stosu

184
00:08:54,190 --> 00:08:56,080
z jest od 3 do 2.

185
00:08:56,080 --> 00:08:58,720
Więc gdybyśmy teraz wcisnąć
kolejny element, na stosie

186
00:08:58,720 --> 00:09:00,720
to ponad Napisać 19.

187
00:09:00,720 --> 00:09:03,990
>> Ale nie przejść przez kłopotów
z usunięciem 19 ze stosu.

188
00:09:03,990 --> 00:09:05,830
Możemy udawać, że go tam nie ma.

189
00:09:05,830 --> 00:09:11,107
Dla celów stosu go nie ma, jeśli
zmieniamy górną się 2 zamiast 3.

190
00:09:11,107 --> 00:09:12,690
W porządku, więc to było dość dużo.

191
00:09:12,690 --> 00:09:15,080
To wszystko, co musimy zrobić,
pop element wyłączony.

192
00:09:15,080 --> 00:09:16,090
Zróbmy to jeszcze raz.

193
00:09:16,090 --> 00:09:18,610
Więc mam podświetlone na czerwono, to tu
wskazują, robimy kolejny telefon.

194
00:09:18,610 --> 00:09:19,720
Mamy zamiar zrobić to samo.

195
00:09:19,720 --> 00:09:20,803
>> Więc co się stało?

196
00:09:20,803 --> 00:09:23,670
Cóż, mamy zamiar przechowywać
33 w x i będziemy

197
00:09:23,670 --> 00:09:26,217
zmienić wierzchołek stosu 1.

198
00:09:26,217 --> 00:09:29,050
Tak, że gdybyśmy byli teraz, aby popchnąć
Element do stosu, które jesteśmy

199
00:09:29,050 --> 00:09:31,610
zamierza zrobić w tej chwili,
co się stanie

200
00:09:31,610 --> 00:09:36,367
jest jedziemy nadpisywania
Tablica liczba lokalizacja 1.

201
00:09:36,367 --> 00:09:38,950
Tak, że 33, który był jakby w lewo
tyle, że po prostu udawał

202
00:09:38,950 --> 00:09:44,390
już nie ma, po prostu dzieje
do sprać go i umieścić 40 tam zamiast.

203
00:09:44,390 --> 00:09:46,290
A potem, oczywiście,
od zrobiliśmy push,

204
00:09:46,290 --> 00:09:48,780
będziemy zwiększamy
Szczyt stosu od 1 do 2

205
00:09:48,780 --> 00:09:50,950
tak, że jeśli teraz dodać
kolejny element, to będziesz

206
00:09:50,950 --> 00:09:54,700
iść do tablicy liczby lokalizacji dwóch.

207
00:09:54,700 --> 00:09:57,590
>> Teraz związane listy są kolejnym
sposobem realizacji stosy.

208
00:09:57,590 --> 00:10:01,210
A jeśli tej definicji w sprawie
Ekran tutaj wygląda znajomo,

209
00:10:01,210 --> 00:10:04,260
to dlatego, że wygląda prawie
dokładnie takie same, w rzeczywistości

210
00:10:04,260 --> 00:10:07,790
to dość dużo jest dokładnie
same jako pojedynczo połączonego listy

211
00:10:07,790 --> 00:10:11,990
Jeśli pamiętacie z naszej dyskusji
pojedynczo związane list w innym filmie.

212
00:10:11,990 --> 00:10:15,510
Jedynym ograniczeniem tutaj
jest dla nas, jako programiści,

213
00:10:15,510 --> 00:10:17,900
nie wolno nam
wstawić lub usunąć losowo

214
00:10:17,900 --> 00:10:20,620
od pojedynczo połączonej listy
które mogliśmy wcześniej zrobić.

215
00:10:20,620 --> 00:10:25,820
Możemy tylko teraz wstawiać i usuwać z
z przodu lub z góry połączony

216
00:10:25,820 --> 00:10:26,320
lista.

217
00:10:26,320 --> 00:10:28,028
To naprawdę tylko
Różnica jednak.

218
00:10:28,028 --> 00:10:29,700
Jest to inaczej pojedynczo połączonej listy.

219
00:10:29,700 --> 00:10:32,060
To tylko ograniczenie
zastępując na siebie

220
00:10:32,060 --> 00:10:35,770
jako programistów
zmienia go na stosie.

221
00:10:35,770 --> 00:10:39,280
>> Zasadą jest tu zawsze utrzymać
wskaźnik na czele połączonej listy.

222
00:10:39,280 --> 00:10:41,520
Oczywiście, jest to ogólnie
Pierwsza ważna zasada.

223
00:10:41,520 --> 00:10:44,260
Dla pojedynczo związane listy i tak ci
Wystarczy tylko wskaźnik do głowy

224
00:10:44,260 --> 00:10:46,160
w celu uzyskania, że
Łańcuch w stanie odnieść

225
00:10:46,160 --> 00:10:48,596
do każdego innego elementu
w połączonej listy.

226
00:10:48,596 --> 00:10:50,470
Ale jest to szczególnie
ważne w stos.

227
00:10:50,470 --> 00:10:52,386
I tak na ogół jesteś
będzie rzeczywiście chcesz

228
00:10:52,386 --> 00:10:54,090
Ten wskaźnik jest zmienna globalna.

229
00:10:54,090 --> 00:10:56,574
To prawdopodobnie będzie
być nawet łatwiej.

230
00:10:56,574 --> 00:10:58,240
Więc jakie są analogi naciśnięciem i pop?

231
00:10:58,240 --> 00:10:58,740
Dobrze.

232
00:10:58,740 --> 00:11:01,812
Więc znów naciska dodaje
nowy element na stosie.

233
00:11:01,812 --> 00:11:03,770
W połączonej listy
oznacza, że ​​będziemy mieć

234
00:11:03,770 --> 00:11:07,770
do utworzenia nowego węzła, że ​​jesteśmy
zamiar dodać do połączonej listy,

235
00:11:07,770 --> 00:11:10,500
a następnie postępuj zgodnie z ostrożne kroki
że mamy opisane wcześniej

236
00:11:10,500 --> 00:11:16,050
w pojedynczo związane listy, aby dodać go do
łańcuch bez zerwania łańcucha

237
00:11:16,050 --> 00:11:18,900
oraz utraty lub osierocenia dowolny
elementy połączonej listy.

238
00:11:18,900 --> 00:11:21,820
I to w zasadzie co to
mała kropelka tekstu nie podsumowuje.

239
00:11:21,820 --> 00:11:23,740
I rzućmy okiem
na to jak na schemacie.

240
00:11:23,740 --> 00:11:24,823
>> Więc oto nasza związana lista.

241
00:11:24,823 --> 00:11:26,620
To jednocześnie zawiera cztery elementy.

242
00:11:26,620 --> 00:11:30,420
I bardziej doskonale Oto nasz
stos zawierający cztery elementy.

243
00:11:30,420 --> 00:11:36,030
I powiedzmy, że chcemy teraz
wcisnąć nowy element na tym stosie.

244
00:11:36,030 --> 00:11:39,792
A my chcemy pchnąć nowy
element, którego dane wartości to 12.

245
00:11:39,792 --> 00:11:41,000
No i co my teraz zrobimy?

246
00:11:41,000 --> 00:11:43,420
Cóż pierwszy będziemy
Przestrzeń malloc, dynamicznie

247
00:11:43,420 --> 00:11:45,411
przydzielić miejsca dla nowego węzła.

248
00:11:45,411 --> 00:11:48,160
I oczywiście natychmiast po
robimy wywołanie malloc zawsze

249
00:11:48,160 --> 00:11:52,989
upewnij się, aby sprawdzić, null,
bo jeśli mamy zerowy powrotem

250
00:11:52,989 --> 00:11:54,280
to był jakiś rodzaj problemu.

251
00:11:54,280 --> 00:11:57,570
Nie chcemy, aby dereference tej wartości null
wskaźnik lub będzie cierpieć usterki seg.

252
00:11:57,570 --> 00:11:58,510
To niedobrze.

253
00:11:58,510 --> 00:11:59,760
Więc my malloced węzła.

254
00:11:59,760 --> 00:12:01,260
Będziemy zakładać, mieliśmy sukces tutaj.

255
00:12:01,260 --> 00:12:06,090
Mamy zamiar umieścić 12 do
Pole danych danego węzła.

256
00:12:06,090 --> 00:12:11,570
Teraz wspominasz, które z naszych wskazówek
porusza się obok więc nie przerwać łańcuch?

257
00:12:11,570 --> 00:12:15,100
Mamy tu kilka opcji, ale
jedynym, który będzie bezpieczny

258
00:12:15,100 --> 00:12:19,330
jest ustawiony wskaźnik do następnej wiadomości
punkt do starego czele listy

259
00:12:19,330 --> 00:12:21,360
lub, co wkrótce będzie
stary szef listy.

260
00:12:21,360 --> 00:12:23,610
I teraz, że wszystkie nasze
elementy są połączone w łańcuch,

261
00:12:23,610 --> 00:12:27,370
możemy po prostu przejść listy wskazać
w tym samym miejscu, że nowe nie.

262
00:12:27,370 --> 00:12:33,550
I mamy teraz skutecznie pchnął
Nowy element na wierzch stosu.

263
00:12:33,550 --> 00:12:36,420
>> Pop Chcemy tylko
usunąć ten pierwszy element.

264
00:12:36,420 --> 00:12:38,150
I tak w zasadzie to, co
mamy tu do czynienia,

265
00:12:38,150 --> 00:12:40,050
dobrze musimy znaleźć drugi element.

266
00:12:40,050 --> 00:12:43,540
W końcu, że stanie się nowym
udać się po usuwamy pierwszy.

267
00:12:43,540 --> 00:12:47,300
Więc po prostu trzeba zacząć od
początek, przejście o jeden do przodu.

268
00:12:47,300 --> 00:12:50,340
Gdy mamy trzymać na jednym
z przodu, gdzie obecnie

269
00:12:50,340 --> 00:12:53,850
to możemy usunąć pierwszy bezpiecznie
a następnie możemy po prostu przesunąć głowę

270
00:12:53,850 --> 00:12:57,150
zwrócić się do tego, co było
Drugi termin i teraz

271
00:12:57,150 --> 00:12:59,170
Jest to pierwsza potem
Węzeł został usunięty.

272
00:12:59,170 --> 00:13:01,160
>> Więc jeszcze raz, przyjrzeniu
na to jak na diagramie

273
00:13:01,160 --> 00:13:05,022
chcą teraz pop
elementem przy tego stosu.

274
00:13:05,022 --> 00:13:05,730
Więc co robimy?

275
00:13:05,730 --> 00:13:08,188
Cóż mamy pierwszy zamiar stworzyć
nowy wskaźnik, który będzie

276
00:13:08,188 --> 00:13:10,940
zwrócić się w tym samym miejscu, co w głowę.

277
00:13:10,940 --> 00:13:13,790
Mamy zamiar przenieść go o jedną pozycję
do przodu mówiąc równych TRAV

278
00:13:13,790 --> 00:13:17,510
TRAV obok na przykład, które
by przesunąć jednego wskaźnika trav

279
00:13:17,510 --> 00:13:19,324
pozycji do przodu.

280
00:13:19,324 --> 00:13:21,240
Teraz, gdy mamy
trzymać pierwszy element

281
00:13:21,240 --> 00:13:24,573
listę wskaźnik nazywa, a
Drugim elementem poprzez wskaźnik zwany

282
00:13:24,573 --> 00:13:28,692
trav, możemy bezpiecznie usunąć, że
Pierwszy element ze stosu

283
00:13:28,692 --> 00:13:30,650
bez utraty resztę
łańcucha, bo my

284
00:13:30,650 --> 00:13:32,358
mają sposób odnieść
do drugiego elementu

285
00:13:32,358 --> 00:13:34,780
przekazania w drodze
wskaźnik zwany trav.

286
00:13:34,780 --> 00:13:37,100
>> Więc teraz możemy uwolnić ten węzeł.

287
00:13:37,100 --> 00:13:38,404
Możemy uwolnić listę.

288
00:13:38,404 --> 00:13:41,320
I to wszystko, co musimy zrobić teraz jest
wykaz przejść do punktu w tym samym miejscu

289
00:13:41,320 --> 00:13:44,482
że trav robi, i jesteśmy z powrotem w rodzaju
gdzie zaczęliśmy zanim pchnął 12

290
00:13:44,482 --> 00:13:45,690
on na pierwszym miejscu w prawo.

291
00:13:45,690 --> 00:13:46,940
To jest dokładnie to, gdzie jesteśmy.

292
00:13:46,940 --> 00:13:48,840
Mieliśmy ten czterech elementów stosu.

293
00:13:48,840 --> 00:13:49,690
Dodaliśmy jedną piątą.

294
00:13:49,690 --> 00:13:51,910
Mamy pchnął piątą
Element na, a następnie

295
00:13:51,910 --> 00:13:55,980
Niedawno pojawiło, że większość
Element dodany wycofać.

296
00:13:55,980 --> 00:13:58,816
>> To naprawdę bardzo dużo
wszystko na stosy.

297
00:13:58,816 --> 00:14:00,190
Możesz wykonać je w tablicach.

298
00:14:00,190 --> 00:14:01,815
Możesz wykonać je w połączonych listach.

299
00:14:01,815 --> 00:14:04,810
Istnieją oczywiście inne
sposoby ich realizacji, jak również.

300
00:14:04,810 --> 00:14:09,060
Zasadniczo powodem użylibyśmy
Stosy jest przechowywanie danych w taki sposób,

301
00:14:09,060 --> 00:14:12,090
że ostatnio dodane
Element jest pierwszą rzeczą, że jesteśmy

302
00:14:12,090 --> 00:14:14,980
będzie chciał wrócić.

303
00:14:14,980 --> 00:14:17,900
Jestem Doug Lloyd, to CS50.

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