1
00:00:00,000 --> 00:00:01,000
[Powered by Google Translate] [Rozdział 6] [Więcej Comfortable]

2
00:00:01,000 --> 00:00:04,000
[Rob Bowden] [Harvard University]

3
00:00:04,000 --> 00:00:09,000
[To jest CS50.] [CS50.TV]

4
00:00:09,000 --> 00:00:11,000
>> Możemy udać się do naszej sekcji pytań.

5
00:00:11,000 --> 00:00:17,000
Wysłałem adres URL miejsca wcześniej.

6
00:00:17,000 --> 00:00:22,000
Początek sekcji pytań powiedzieć-

7
00:00:22,000 --> 00:00:26,000
widocznie nie jestem całkowicie unsick-jest to bardzo proste pytanie

8
00:00:26,000 --> 00:00:28,000
po prostu to, co jest valgrind?

9
00:00:28,000 --> 00:00:30,000
Co valgrind zrobić?

10
00:00:30,000 --> 00:00:34,000
Ktoś chce powiedzieć, co valgrind robi?

11
00:00:34,000 --> 00:00:36,000
[Student] Kontrole wyciekiem pamięci.

12
00:00:36,000 --> 00:00:41,000
Tak, valgrind jest ogólny sprawdzania pamięci.

13
00:00:41,000 --> 00:00:44,000
To, w końcu, mówi, jeśli masz jakieś przecieki pamięci,

14
00:00:44,000 --> 00:00:49,000
co jest głównie to, czego używasz go, ponieważ jeśli chcesz

15
00:00:49,000 --> 00:00:54,000
dobrze w zestawie problem lub jeśli chcesz

16
00:00:54,000 --> 00:00:59,000
dostać się na wielkim statku, trzeba mieć żadnych przecieków pamięci w ogóle,

17
00:00:59,000 --> 00:01:01,000
oraz w przypadku gdy masz przeciek pamięci, że nie można znaleźć,

18
00:01:01,000 --> 00:01:04,000
również pamiętać, że w każdym przypadku otwierania pliku

19
00:01:04,000 --> 00:01:07,000
i jeśli nie zamknąć, to wyciek pamięci.

20
00:01:07,000 --> 00:01:10,000
>> Wiele osób poszukuje jakiegoś węzła, który oni nie zwalniając

21
00:01:10,000 --> 00:01:15,000
kiedy tak naprawdę, nie zamknąć słownika w etapie pierwszym.

22
00:01:15,000 --> 00:01:19,000
Informuje także, jeśli masz jakieś nieważne czyta lub pisze

23
00:01:19,000 --> 00:01:22,000
co oznacza, że ​​jeśli spróbujesz ustawić wartość

24
00:01:22,000 --> 00:01:26,000
to jest poza koniec stosu i nie zdarzy się seg winy

25
00:01:26,000 --> 00:01:30,000
ale valgrind go łapie, jak nie powinno być rzeczywiście pisanie tam,

26
00:01:30,000 --> 00:01:33,000
a więc na pewno nie powinien mieć żadnej z tych albo.

27
00:01:33,000 --> 00:01:38,000
Jak używać Valgrind?

28
00:01:38,000 --> 00:01:42,000
Jak używać Valgrind?

29
00:01:42,000 --> 00:01:45,000
>> To ogólne pytanie

30
00:01:45,000 --> 00:01:49,000
niby go uruchomić i patrzeć na wyjściu.

31
00:01:49,000 --> 00:01:51,000
Wyjście jest ogromny wiele razy.

32
00:01:51,000 --> 00:01:54,000
Jest też zabawa błędy gdzie jeśli masz jakieś strasznie źle

33
00:01:54,000 --> 00:01:59,000
dzieje się w pętli, to będzie to w końcu powiedzieć: "Zbyt wiele błędów.

34
00:01:59,000 --> 00:02:03,000
Mam zamiar zatrzymać liczenie teraz ".

35
00:02:03,000 --> 00:02:08,000
Jest to w zasadzie tekstowych wyjście, że trzeba analizować.

36
00:02:08,000 --> 00:02:13,000
W końcu powie to żadnych wycieków pamięci, które masz,

37
00:02:13,000 --> 00:02:16,000
Jak wiele bloków, które mogą być przydatne, ponieważ

38
00:02:16,000 --> 00:02:20,000
jeśli jest to jeden blok unfreed, to jest to zazwyczaj łatwiej znaleźć

39
00:02:20,000 --> 00:02:23,000
niż 1.000 bloki unfreed.

40
00:02:23,000 --> 00:02:26,000
1.000 bloki unfreed prawdopodobnie oznacza jesteś nie zwalniając

41
00:02:26,000 --> 00:02:30,000
połączonego listy w odpowiedni sposób, czy coś.

42
00:02:30,000 --> 00:02:32,000
To się valgrind.

43
00:02:32,000 --> 00:02:35,000
>> Teraz mamy naszą sekcję pytań,

44
00:02:35,000 --> 00:02:38,000
których nie trzeba pobrać.

45
00:02:38,000 --> 00:02:41,000
Możesz kliknąć na moje imię i pociągnij je w przestrzeni.

46
00:02:41,000 --> 00:02:44,000
Kliknij teraz na mnie.

47
00:02:44,000 --> 00:02:46,000
Wersja 1 będzie stos, które robimy w pierwszej kolejności.

48
00:02:46,000 --> 00:02:55,000
Wersja 2 będzie kolejka, a wersja 3 będzie pojedynczo połączonej listy.

49
00:02:55,000 --> 00:02:58,000
Zaczynając od naszego stosu.

50
00:02:58,000 --> 00:03:02,000
Jak mówi tutaj, stos jest jednym z najbardziej podstawowych,

51
00:03:02,000 --> 00:03:07,000
podstawowe struktury danych informatyki.

52
00:03:07,000 --> 00:03:11,000
Bardzo prototypowy przykład

53
00:03:11,000 --> 00:03:13,000
Stos tac w sali jadalnej.

54
00:03:13,000 --> 00:03:16,000
Jest to w zasadzie, kiedy tylko zostały wprowadzone do komina

55
00:03:16,000 --> 00:03:20,000
ktoś powie: "O, jak stos tac".

56
00:03:20,000 --> 00:03:22,000
Można umieścić zasobników up.

57
00:03:22,000 --> 00:03:24,000
Potem, gdy idziesz do ściągania podajnika

58
00:03:24,000 --> 00:03:31,000
pierwszy podajnik wychodzi wyciągnął jest ostatnim, który został wprowadzony na stos.

59
00:03:31,000 --> 00:03:34,000
Stos także-jak to mówi tu

60
00:03:34,000 --> 00:03:37,000
mamy segment pamięci zwany stos.

61
00:03:37,000 --> 00:03:40,000
I dlaczego jest on nazywany stos?

62
00:03:40,000 --> 00:03:42,000
>> Bo jak struktury danych stosu,

63
00:03:42,000 --> 00:03:46,000
popycha i wyskakuje ramek stosu na stos,

64
00:03:46,000 --> 00:03:53,000
gdzie stosu ramki są jak określonego połączenia funkcji.

65
00:03:53,000 --> 00:03:57,000
I jak stos, zawsze będziesz musiał wrócić

66
00:03:57,000 --> 00:04:03,000
z wywołaniem funkcji, zanim będzie można dostać się do niższych ramek stosu ponownie.

67
00:04:03,000 --> 00:04:08,000
Nie można mieć główną wywołać bar wywołać foo bar i powrócić do głównej bezpośrednio.

68
00:04:08,000 --> 00:04:14,000
To zawsze musi przestrzegać poprawnej stos pchania i popping.

69
00:04:14,000 --> 00:04:18,000
Dwie operacje, jak powiedziałem, to push i pop.

70
00:04:18,000 --> 00:04:20,000
Są to uniwersalne warunki.

71
00:04:20,000 --> 00:04:26,000
Powinieneś wiedzieć, i połóż w kategoriach stosów nie wiem co.

72
00:04:26,000 --> 00:04:28,000
Zobaczymy, kolejki są trochę inne.

73
00:04:28,000 --> 00:04:32,000
To naprawdę nie ma uniwersalnego terminu, ale push i pop są uniwersalne dla stosów.

74
00:04:32,000 --> 00:04:34,000
Push jest po prostu umieścić na stosie.

75
00:04:34,000 --> 00:04:37,000
Pop jest zdjąć ze stosu.

76
00:04:37,000 --> 00:04:43,000
I widzimy tutaj mamy typedef struct stos,

77
00:04:43,000 --> 00:04:46,000
mamy więc ciągi char **.

78
00:04:46,000 --> 00:04:51,000
Nie daj się zastraszyć żadnej **.

79
00:04:51,000 --> 00:04:54,000
To będzie w końcu jest tablica łańcuchów

80
00:04:54,000 --> 00:04:58,000
lub tablica wskaźników do znaków, gdzie

81
00:04:58,000 --> 00:05:00,000
wskaźniki do znaków bywają ciągi.

82
00:05:00,000 --> 00:05:05,000
To nie musi być ciągi, ale tutaj, to będziemy w ciągi.

83
00:05:05,000 --> 00:05:08,000
>> Mamy tablicę ciągów.

84
00:05:08,000 --> 00:05:14,000
Mamy rozmiar, co oznacza, ile elementy są obecnie na stosie,

85
00:05:14,000 --> 00:05:19,000
a następnie mamy zdolność, która jest jak wiele elementów może być na stosie.

86
00:05:19,000 --> 00:05:22,000
Pojemność powinna rozpocząć jako coś większego niż 1,

87
00:05:22,000 --> 00:05:27,000
ale rozmiar ma zamiar rozpocząć w 0.

88
00:05:27,000 --> 00:05:36,000
Teraz są w zasadzie trzy sposoby można myśleć stosie.

89
00:05:36,000 --> 00:05:39,000
Cóż, jest prawdopodobnie więcej, ale są dwa sposoby

90
00:05:39,000 --> 00:05:43,000
można wdrożyć za pomocą tablicy, czy można wdrożyć przy użyciu połączonej listy.

91
00:05:43,000 --> 00:05:48,000
Połączone listy są rodzajem trywialny aby stosy od.

92
00:05:48,000 --> 00:05:51,000
Jest to bardzo łatwe do wykonania przy użyciu stosu połączonych list,

93
00:05:51,000 --> 00:05:55,000
więc, jedziemy do stosu przy użyciu tablic

94
00:05:55,000 --> 00:05:59,000
a następnie za pomocą tablic, tam również dwa sposoby, można o tym myśleć.

95
00:05:59,000 --> 00:06:01,000
Wcześniej, kiedy powiedział, że mamy zdolność do stosu,

96
00:06:01,000 --> 00:06:04,000
więc możemy dopasować element na stosie.

97
00:06:04,000 --> 00:06:09,000
>> Jeden sposób, to może się zdarzyć, to tak szybko, jak trafisz 10 elementy, a następnie gotowe.

98
00:06:09,000 --> 00:06:13,000
Być może wiesz, że istnieje górna granica 10 rzeczy na świecie

99
00:06:13,000 --> 00:06:16,000
że nigdy nie będziesz mieć więcej niż 10 rzeczy na stosie,

100
00:06:16,000 --> 00:06:20,000
w takim przypadku można mieć górną granicę wielkości twojego stacka.

101
00:06:20,000 --> 00:06:23,000
Albo możesz mieć swój stack jest nieograniczona,

102
00:06:23,000 --> 00:06:27,000
ale jeśli robisz tablicę, to oznacza, że ​​za każdym razem trafisz 10 elementów,

103
00:06:27,000 --> 00:06:29,000
wtedy będziesz miał wzrosnąć do 20 elementów, a gdy trafisz 20 elementów,

104
00:06:29,000 --> 00:06:33,000
będziesz musiał rozwijać swoją tablicę 30 elementów lub 40 elementów.

105
00:06:33,000 --> 00:06:37,000
Będziesz musiał zwiększyć pojemność, która jest, co mamy zamiar zrobić.

106
00:06:37,000 --> 00:06:40,000
Za każdym razem możemy osiągnąć maksymalny rozmiar naszego stosu

107
00:06:40,000 --> 00:06:46,000
kiedy wcisnąć coś jeszcze dalej, będziemy potrzebować, aby zwiększyć wydajność.

108
00:06:46,000 --> 00:06:50,000
Tutaj mamy zadeklarowane jako bool Push push (char * str).

109
00:06:50,000 --> 00:06:54,000
Char str * jest ciąg, że naciskają na stosie,

110
00:06:54,000 --> 00:06:58,000
i bool mówi tylko, czy nam się udało, czy nie.

111
00:06:58,000 --> 00:07:00,000
>> Jak nie?

112
00:07:00,000 --> 00:07:04,000
Co to jest tylko okoliczność, że można myśleć

113
00:07:04,000 --> 00:07:07,000
gdzie musimy wrócić fałsz?

114
00:07:07,000 --> 00:07:09,000
Tak.

115
00:07:09,000 --> 00:07:12,000
[Student] Jeśli jest pełna i używamy ograniczonego stosowania.

116
00:07:12,000 --> 00:07:17,000
Tak, więc jak można zdefiniować-odpowiedział

117
00:07:17,000 --> 00:07:23,000
jeśli jest to pełne i używamy ograniczoną realizację.

118
00:07:23,000 --> 00:07:26,000
Wtedy na pewno wrócimy false.

119
00:07:26,000 --> 00:07:31,000
Jak tylko trafiliśmy 10 rzeczy na tablicy, nie możemy zmieścić 11, więc return false.

120
00:07:31,000 --> 00:07:32,000
Co, jeśli to jest nieograniczona? Tak.

121
00:07:32,000 --> 00:07:38,000
Jeśli nie można rozwinąć tablicę z jakiegoś powodu.

122
00:07:38,000 --> 00:07:43,000
Tak, więc pamięć jest zasobem ograniczonym,

123
00:07:43,000 --> 00:07:51,000
iw końcu, jeśli mamy zachować rzeczy spychając na stosie w kółko,

124
00:07:51,000 --> 00:07:54,000
będziemy próbować i przydzielić większą tablicę, aby dopasować

125
00:07:54,000 --> 00:07:59,000
większa pojemność i malloc lub cokolwiek używamy będzie return false.

126
00:07:59,000 --> 00:08:02,000
Cóż, malloc zwróci null.

127
00:08:02,000 --> 00:08:05,000
>> Pamiętaj, że za każdym razem kiedyś zadzwonić malloc, powinno być sprawdzanie, czy

128
00:08:05,000 --> 00:08:12,000
zwraca NULL albo że jest odliczenie poprawności.

129
00:08:12,000 --> 00:08:17,000
Ponieważ chcemy mieć nieograniczony stos,

130
00:08:17,000 --> 00:08:21,000
Jedyny przypadek, będziemy się zwracać wartość false jest, jeśli staramy się

131
00:08:21,000 --> 00:08:26,000
zwiększenie zdolności i malloc lub cokolwiek zwraca false.

132
00:08:26,000 --> 00:08:30,000
Następnie pop przyjmuje żadnych argumentów,

133
00:08:30,000 --> 00:08:37,000
i zwraca łańcuch, który jest na górze stosu.

134
00:08:37,000 --> 00:08:41,000
Cokolwiek ostatnio na stos, co pop powraca,

135
00:08:41,000 --> 00:08:44,000
a także usuwa ze stosu.

136
00:08:44,000 --> 00:08:50,000
I zauważyć, że zwraca null, jeśli nie ma nic na stos.

137
00:08:50,000 --> 00:08:53,000
Jest zawsze możliwe, że stos jest pusty.

138
00:08:53,000 --> 00:08:55,000
W Javie, jeśli jesteś przyzwyczajony do tego, lub innych języków,

139
00:08:55,000 --> 00:09:01,000
próbuje wyskoczyć z pustego stosu może spowodować wyjątek, czy coś.

140
00:09:01,000 --> 00:09:09,000
>> Ale w C, null jest trochę dużo przypadków, w jaki sposób rozwiązania tych problemów.

141
00:09:09,000 --> 00:09:13,000
Wracając nieważne jest to, jak będziemy oznaczać, że stos jest pusty.

142
00:09:13,000 --> 00:09:16,000
Poniżej przedstawiamy kod, który będzie testować swój stosu funkcjonalność,

143
00:09:16,000 --> 00:09:19,000
wdrożenia wcisnąć i pop.

144
00:09:19,000 --> 00:09:23,000
To nie będzie dużo kodu.

145
00:09:23,000 --> 00:09:40,000
Będę-faktycznie, zanim to zrobimy, hint, hint-

146
00:09:40,000 --> 00:09:44,000
jeśli nie widziałeś, malloc nie jedyną funkcją jest

147
00:09:44,000 --> 00:09:47,000
która przydziela pamięć na stercie dla Ciebie.

148
00:09:47,000 --> 00:09:51,000
Istnieje rodzina funkcji Alloc.

149
00:09:51,000 --> 00:09:53,000
Pierwszy to malloc, która masz w zwyczaju.

150
00:09:53,000 --> 00:09:56,000
Potem jest calloc, który robi to samo, malloc,

151
00:09:56,000 --> 00:09:59,000
ale będzie zera wszystko dla ciebie.

152
00:09:59,000 --> 00:10:04,000
Jeśli kiedykolwiek chciał ustawić wszystko na null po mallocing coś

153
00:10:04,000 --> 00:10:06,000
nie powinno być używane tylko calloc na pierwszym miejscu zamiast pisać

154
00:10:06,000 --> 00:10:09,000
dla pętli do zera obecnie cały blok pamięci.

155
00:10:09,000 --> 00:10:15,000
>> Realloc jest jak malloc i ma wiele szczególnych przypadków,

156
00:10:15,000 --> 00:10:19,000
ale w zasadzie to, co robi, jest realloc

157
00:10:19,000 --> 00:10:24,000
zajmuje wskaźnik, które zostały już przydzielone.

158
00:10:24,000 --> 00:10:27,000
Realloc jest funkcja ma być zwrócenie uwagi na tutaj.

159
00:10:27,000 --> 00:10:31,000
To zajmuje wskaźnik, który już wrócił z malloc.

160
00:10:31,000 --> 00:10:35,000
Powiedzmy, że żądać od malloc wskaźnik z 10 bajtów.

161
00:10:35,000 --> 00:10:38,000
Potem zdajesz sobie sprawę, chciał 20 bajtów,

162
00:10:38,000 --> 00:10:42,000
więc zadzwonić realloc tego wskaźnika z 20 bajtów,

163
00:10:42,000 --> 00:10:47,000
i realloc automatycznie kopiować wszystko dla Ciebie.

164
00:10:47,000 --> 00:10:51,000
Jeśli po prostu nazywa malloc ponownie, tak jak ja masz bloku 10 bajtów.

165
00:10:51,000 --> 00:10:53,000
Teraz potrzebuję bloku 20 bajtów,

166
00:10:53,000 --> 00:10:58,000
więc jeśli malloc 20 bajtów, następnie trzeba ręcznie skopiować w ciągu 10 bajtów z pierwszych rzeczy,

167
00:10:58,000 --> 00:11:01,000
do drugiej rzeczy, a następnie wolne pierwsze.

168
00:11:01,000 --> 00:11:04,000
Realloc zajmie to za Ciebie.

169
00:11:04,000 --> 00:11:11,000
>> Wskazówka podpis będzie void *,

170
00:11:11,000 --> 00:11:15,000
który jest właśnie zwracając wskaźnik do bloku pamięci,

171
00:11:15,000 --> 00:11:17,000
Następnie void * ptr.

172
00:11:17,000 --> 00:11:22,000
Można myśleć o void * jako ogólny wskaźnik.

173
00:11:22,000 --> 00:11:27,000
Ogólnie rzecz biorąc, nie mamy do czynienia z void *,

174
00:11:27,000 --> 00:11:30,000
ale malloc zwraca void *, a potem to tylko używane jak

175
00:11:30,000 --> 00:11:34,000
To jest rzeczywiście będzie char *.

176
00:11:34,000 --> 00:11:37,000
Poprzedni void *, który został zwrócony przez malloc

177
00:11:37,000 --> 00:11:41,000
teraz będą przekazywane do realloc, a następnie rozmiar

178
00:11:41,000 --> 00:11:49,000
to nowa liczba bajtów, które chcesz przeznaczyć, tak więc nowe zdolności.

179
00:11:49,000 --> 00:11:57,000
Dam ci kilka minut, i robią to w naszej przestrzeni.

180
00:11:57,000 --> 00:12:02,000
Start z wersji 1.

181
00:12:16,000 --> 00:12:21,000
Wpadnę po ciebie o wystarczająco dużo czasu, mam nadzieję, że w celu realizacji Push,

182
00:12:21,000 --> 00:12:24,000
a potem dam ci kolejną przerwę zrobić pop.

183
00:12:24,000 --> 00:12:27,000
Ale to naprawdę nie jest dużo kodu jest w ogóle.

184
00:12:27,000 --> 00:12:35,000
Większość kodu jest prawdopodobnie rzeczy rozwija, rozszerzając możliwości.

185
00:12:35,000 --> 00:12:39,000
Dobra, nie ma ciśnienia być całkowicie wykonane,

186
00:12:39,000 --> 00:12:47,000
ale tak długo, jak czujesz, że jesteś na dobrej drodze, to jest dobre.

187
00:12:47,000 --> 00:12:53,000
>> Czy ktoś ma jakiś kod, oni czują się komfortowo ze mną ciągnie się?

188
00:12:53,000 --> 00:12:59,000
Tak, tak, ale czy ktoś ma żadnego kodu można podciągnąć?

189
00:12:59,000 --> 00:13:05,000
Ok, można uruchomić, zapisać go, co to jest?

190
00:13:05,000 --> 00:13:09,000
Zawsze zapominam, że krok.

191
00:13:09,000 --> 00:13:15,000
Ok, patrząc na dostarczaniu,

192
00:13:15,000 --> 00:13:18,000
chcesz wyjaśnić swój kod?

193
00:13:18,000 --> 00:13:24,000
[Tablica] pierwsze, że zwiększenie wielkości.

194
00:13:24,000 --> 00:13:28,000
Myślę, że może powinienem, że-tak, zwiększyłem rozmiar,

195
00:13:28,000 --> 00:13:31,000
i sprawdzić, czy jest mniejsza niż pojemność.

196
00:13:31,000 --> 00:13:36,000
A jeśli jest to mniej niż pojemność, dodać do tablicy, które już masz.

197
00:13:36,000 --> 00:13:42,000
A jeśli tak nie jest, pomnożyć możliwości przez 2,

198
00:13:42,000 --> 00:13:50,000
i realokacji tablicy ciągów do czegoś z większym rozmiarze zdolności teraz.

199
00:13:50,000 --> 00:13:55,000
A jeśli to się nie powiedzie, to poinformować użytkownika i zwraca fałsz,

200
00:13:55,000 --> 00:14:04,000
a jeśli to jest w porządku, to mogę umieścić napis w nowym miejscu.

201
00:14:04,000 --> 00:14:07,000
>> [Rob B.] Również zauważyć, że użyliśmy ładny operatory bitowe tutaj

202
00:14:07,000 --> 00:14:09,000
pomnożyć przez 2.

203
00:14:09,000 --> 00:14:11,000
Pamiętaj, lewy shift zawsze będzie mnożona przez 2.

204
00:14:11,000 --> 00:14:15,000
Prawy shift jest dzielona przez 2, tak długo, jak to możliwe, że oznacza to

205
00:14:15,000 --> 00:14:18,000
podzielić przez 2, jak w całkowitej podzielona przez 2.

206
00:14:18,000 --> 00:14:20,000
Może obciąć 1 tu czy tam.

207
00:14:20,000 --> 00:14:26,000
Ale przesunięcie w lewo o 1 zawsze będzie pomnożyć przez 2,

208
00:14:26,000 --> 00:14:32,000
chyba przepełnienie granice liczby całkowitej, a potem nie będzie.

209
00:14:32,000 --> 00:14:34,000
Komentarz z boku.

210
00:14:34,000 --> 00:14:39,000
Lubię robić, to nie będzie do zmiany kodu jakikolwiek sposób,

211
00:14:39,000 --> 00:14:48,000
ale podoba mi się zrobić coś takiego.

212
00:14:48,000 --> 00:14:51,000
To rzeczywiście będzie zrobić to nieco dłużej.

213
00:15:04,000 --> 00:15:08,000
Może to nie przypadek, aby pokazać doskonały to jest,

214
00:15:08,000 --> 00:15:14,000
ale lubię go w segmencie tych bloków-

215
00:15:14,000 --> 00:15:17,000
dobrze, jeśli to, jeśli się stanie, to mam zamiar zrobić coś,

216
00:15:17,000 --> 00:15:19,000
i funkcja jest wykonywana.

217
00:15:19,000 --> 00:15:22,000
I nie trzeba wtedy przewijać moje oczy w dół funkcji

218
00:15:22,000 --> 00:15:25,000
aby zobaczyć, co dzieje się po innym.

219
00:15:25,000 --> 00:15:27,000
To, czy to jeśli się zdarzy, po prostu wrócić.

220
00:15:27,000 --> 00:15:30,000
Ma też ładne dodatkowe korzyści poza tym wszystko

221
00:15:30,000 --> 00:15:33,000
obecnie przesunięta w lewo raz.

222
00:15:33,000 --> 00:15:40,000
I nie trzeba już-jeśli kiedykolwiek blisko absurdalnie długie linie,

223
00:15:40,000 --> 00:15:45,000
to te 4 bajty może pomóc, a także bardziej na lewo coś jest,

224
00:15:45,000 --> 00:15:48,000
mniej przytłoczeni czujesz, jeśli lubisz-w porządku, muszę zapamiętać

225
00:15:48,000 --> 00:15:53,000
Jestem obecnie w pętli wewnątrz z innego wewnątrz pętli for.

226
00:15:53,000 --> 00:15:58,000
Wszędzie można to zrobić natychmiast, I trochę jak.

227
00:15:58,000 --> 00:16:05,000
Jest to całkowicie opcjonalne i nie przewiduje się w żaden sposób.

228
00:16:05,000 --> 00:16:12,000
>> [Student] Czy należy rozmiar - w stanie, nie uda?

229
00:16:12,000 --> 00:16:19,000
Stan fail tu nie udało się nam realloc, więc tak.

230
00:16:19,000 --> 00:16:22,000
Zauważ, jak w stanie negatywnej, prawdopodobnie,

231
00:16:22,000 --> 00:16:26,000
chyba, że ​​darmowe rzeczy później, jesteśmy zawsze zawiedzie

232
00:16:26,000 --> 00:16:29,000
bez względu na to, ile razy próbujemy wcisnąć coś.

233
00:16:29,000 --> 00:16:32,000
Jeśli będziemy przeć, wciąż zwiększający rozmiary,

234
00:16:32,000 --> 00:16:36,000
mimo że nie stawiają nic na stos.

235
00:16:36,000 --> 00:16:39,000
Zazwyczaj nie zwiększamy wielkość aż

236
00:16:39,000 --> 00:16:43,000
po tym, jak udało się umieścić go na stosie.

237
00:16:43,000 --> 00:16:50,000
Chcemy to zrobić, powiedzieć, czy tu i tu.

238
00:16:50,000 --> 00:16:56,000
I wtedy zamiast powiedzieć s.size pojemności ≤, to mniej niż zdolności,

239
00:16:56,000 --> 00:17:01,000
tylko dlatego, że przeniósł się gdzie wszystko było.

240
00:17:01,000 --> 00:17:07,000
>> I pamiętaj, że jedynym miejscem, które moglibyśmy return false

241
00:17:07,000 --> 00:17:14,000
jest tutaj, gdzie realloc zwróciło null,

242
00:17:14,000 --> 00:17:19,000
i jeśli zdarzy się zapamiętać błąd standardowy,

243
00:17:19,000 --> 00:17:22,000
może warto rozważyć tę sprawę, w której chcesz wydrukować błąd standardowy,

244
00:17:22,000 --> 00:17:26,000
tak fprintf stderr zamiast drukowania bezpośrednio wyjście standardowe.

245
00:17:26,000 --> 00:17:31,000
Znowu, nie oczekuje się, ale jeśli jest to błąd,

246
00:17:31,000 --> 00:17:41,000
wpisz printf, to może chcesz, aby drukować na standardowe wyjście błędów, zamiast standardowego out.

247
00:17:41,000 --> 00:17:44,000
>> Ktoś ma coś jeszcze do uwagi? Tak.

248
00:17:44,000 --> 00:17:47,000
[Student] można przejść nad [niesłyszalny]?

249
00:17:47,000 --> 00:17:55,000
[Rob B.] Tak, rzeczywisty binariness z niego lub po prostu co to jest?

250
00:17:55,000 --> 00:17:57,000
[Student] Więc go pomnożyć przez 2?

251
00:17:57,000 --> 00:17:59,000
[Rob B.] Tak, w zasadzie.

252
00:17:59,000 --> 00:18:11,000
Binarnie ziemi, zawsze mamy nasz zestaw cyfr.

253
00:18:11,000 --> 00:18:22,000
Przesunięcie tego Wystawione przez 1 zasadzie wstawia go tutaj z prawej strony.

254
00:18:22,000 --> 00:18:25,000
Powrót do tego, po prostu pamiętać, że wszystko w formacie binarnym

255
00:18:25,000 --> 00:18:28,000
jest potęgą 2, więc to oznacza 2 do 0,

256
00:18:28,000 --> 00:18:30,000
Ten 2 do 1, w tym 2 do 2.

257
00:18:30,000 --> 00:18:33,000
Wstawiając 0 po prawej stronie teraz, po prostu przenieść wszystko od nowa.

258
00:18:33,000 --> 00:18:38,000
Co było do 0 2 jest teraz 2 do 1, jest 2 do 2.

259
00:18:38,000 --> 00:18:41,000
Po prawej stronie, że włożona

260
00:18:41,000 --> 00:18:44,000
jest koniecznie będzie 0,

261
00:18:44,000 --> 00:18:46,000
co ma sens.

262
00:18:46,000 --> 00:18:49,000
Jeśli kiedykolwiek pomnożyć liczbę przez 2, to nie skończy się dziwnie,

263
00:18:49,000 --> 00:18:54,000
więc 2 do 0 miejsce należy 0,

264
00:18:54,000 --> 00:18:59,000
i to jest to, co pół ostrzegał przed jest, jeśli się zdarzają, aby przesunąć

265
00:18:59,000 --> 00:19:01,000
poza liczbę bitów w liczby całkowitej,

266
00:19:01,000 --> 00:19:04,000
to ten 1 ma zamiar skończyć się wyłączyć.

267
00:19:04,000 --> 00:19:10,000
To jedyne zmartwienie jeśli zdarzy ci się mieć do czynienia z naprawdę dużych możliwościach.

268
00:19:10,000 --> 00:19:15,000
Ale w tym momencie, to masz do czynienia z tablicą miliardy rzeczy,

269
00:19:15,000 --> 00:19:25,000
które mogą nie pasować do pamięci tak.

270
00:19:25,000 --> 00:19:31,000
>> Teraz możemy przejść do muzyki pop, która jest jeszcze łatwiejsze.

271
00:19:31,000 --> 00:19:36,000
Można zrobić to tak, jeśli zdarzy ci się pop całą masę,

272
00:19:36,000 --> 00:19:38,000
a teraz jesteś na pół mocy ponownie.

273
00:19:38,000 --> 00:19:42,000
Można realloc aby zmniejszyć ilość pamięci masz,

274
00:19:42,000 --> 00:19:47,000
ale nie trzeba się martwić o to, więc tylko przypadek realloc będzie

275
00:19:47,000 --> 00:19:50,000
rośnie pamięć, nigdy kurczy pamięci

276
00:19:50,000 --> 00:19:59,000
co zamierza zrobić pop bardzo proste.

277
00:19:59,000 --> 00:20:02,000
Teraz kolejek, które będzie jak stosy,

278
00:20:02,000 --> 00:20:06,000
ale kolejność, że masz trochę rzeczy jest odwrócony.

279
00:20:06,000 --> 00:20:10,000
Prototypowy przykład kolejce jest linia,

280
00:20:10,000 --> 00:20:12,000
więc myślę, że gdybyś był angielski, to bym powiedział,

281
00:20:12,000 --> 00:20:17,000
prototypowy przykład kolejki jest kolejka.

282
00:20:17,000 --> 00:20:22,000
Tak jak w wierszu, jeśli jesteś pierwszą osobą w kolejce,

283
00:20:22,000 --> 00:20:24,000
można oczekiwać, aby być pierwszą osobą, z linii.

284
00:20:24,000 --> 00:20:31,000
Jeśli jesteś ostatnią osobą w linii, będą ostatnią osobą do serwisu.

285
00:20:31,000 --> 00:20:35,000
Nazywamy to wzór FIFO, natomiast stosu był wzór LIFO.

286
00:20:35,000 --> 00:20:40,000
Te słowa są dość powszechne.

287
00:20:40,000 --> 00:20:46,000
>> Podobnie jak stosy iw przeciwieństwie do tablic, kolejki zazwyczaj nie zezwala na dostęp do elementów w środku.

288
00:20:46,000 --> 00:20:50,000
Tutaj, stos, mamy push i pop.

289
00:20:50,000 --> 00:20:54,000
Tu stało się ich powołałem Kolejkuj i usunie.

290
00:20:54,000 --> 00:20:58,000
Słyszałem także je nazywa shift i unshift.

291
00:20:58,000 --> 00:21:02,000
Słyszałem, że ludzie mówią push i pop się również do kolejek.

292
00:21:02,000 --> 00:21:05,000
Słyszałem, wstawianie, usuwanie,

293
00:21:05,000 --> 00:21:11,000
tak naciskać i pop, jeśli mówisz o stosach, jesteś pchania i popping.

294
00:21:11,000 --> 00:21:16,000
Jeśli mówisz o kolejkach, można odebrać słowa chcesz użyć

295
00:21:16,000 --> 00:21:23,000
do wstawiania i usuwania, a nie ma zgody na to, co powinno być tzw.

296
00:21:23,000 --> 00:21:27,000
Ale tutaj mamy Kolejkuj i usunie.

297
00:21:27,000 --> 00:21:37,000
Teraz, struct wygląda niemal identycznie jak struct stosu.

298
00:21:37,000 --> 00:21:40,000
Ale musimy śledzić głowy.

299
00:21:40,000 --> 00:21:44,000
Myślę, że mówi się tu, ale po co nam głowę?

300
00:21:53,000 --> 00:21:57,000
Prototypy są zasadniczo identyczne z push i pop.

301
00:21:57,000 --> 00:21:59,000
Można myśleć o tym, jak naciśnięcie i popu.

302
00:21:59,000 --> 00:22:08,000
Jedyną różnicą jest to, pop powraca zamiast ostatniego, to pierwszy powrót.

303
00:22:08,000 --> 00:22:12,000
2, 1, 3, 4, lub coś.

304
00:22:12,000 --> 00:22:14,000
I tutaj jest początek.

305
00:22:14,000 --> 00:22:17,000
Nasza kolejka jest pełny, więc nie ma w niej cztery elementy.

306
00:22:17,000 --> 00:22:21,000
Koniec naszej kolejki jest obecnie 2,

307
00:22:21,000 --> 00:22:24,000
a teraz idziemy na wstawić coś innego.

308
00:22:24,000 --> 00:22:29,000
>> Kiedy chcemy wstawić, że coś innego, co zrobiliśmy dla wersji stosu

309
00:22:29,000 --> 00:22:36,000
jest, że przedłużyliśmy nasz blok pamięci.

310
00:22:36,000 --> 00:22:40,000
Jaki jest problem z tym?

311
00:22:40,000 --> 00:22:45,000
[Student] 2 przesuwa się.

312
00:22:45,000 --> 00:22:51,000
Co powiedziałem wcześniej o końcu kolejki,

313
00:22:51,000 --> 00:22:57,000
to nie ma sensu, że zaczynamy od 1,

314
00:22:57,000 --> 00:23:01,000
to chcemy Dequeue 1, następnie Dequeue 3, następnie Dequeue 4,

315
00:23:01,000 --> 00:23:05,000
następnie Dequeue 2, a następnie usunie z niej ten.

316
00:23:05,000 --> 00:23:08,000
Nie możemy użyć realloc teraz

317
00:23:08,000 --> 00:23:11,000
lub co najmniej, trzeba użyć realloc w inny sposób.

318
00:23:11,000 --> 00:23:15,000
Ale pewnie nie tylko funkcję realloc.

319
00:23:15,000 --> 00:23:18,000
Będziesz musiał ręcznie skopiować pamięć.

320
00:23:18,000 --> 00:23:21,000
>> Znajdują się dwie funkcje, aby skopiować pamięć.

321
00:23:21,000 --> 00:23:25,000
Jest memcopy i memmove.

322
00:23:25,000 --> 00:23:29,000
Jestem obecnie czytania stron podręcznika, aby zobaczyć, który z nich masz zamiar użyć.

323
00:23:29,000 --> 00:23:35,000
Okay, memcopy, różnica jest

324
00:23:35,000 --> 00:23:38,000
że memcopy i memmove, jeden obsługuje sprawę prawidłowo

325
00:23:38,000 --> 00:23:41,000
gdzie jesteś kopiowania do regionu, który dzieje się pokrywają region

326
00:23:41,000 --> 00:23:46,000
jesteś kopiowaniu.

327
00:23:46,000 --> 00:23:50,000
Memcopy nie poradzę. Memmove robi.

328
00:23:50,000 --> 00:23:59,000
Można myśleć o problemie, jak-

329
00:23:59,000 --> 00:24:09,000
powiedzmy, że chcesz skopiować tego faceta,

330
00:24:09,000 --> 00:24:13,000
te cztery do tego faceta.

331
00:24:13,000 --> 00:24:16,000
W końcu, co tablica powinna wyglądać

332
00:24:16,000 --> 00:24:26,000
kopia jest po 2, 1, 2, 1, 3, 4, a następnie kilka rzeczy na końcu.

333
00:24:26,000 --> 00:24:29,000
Ale to zależy od kolejności, w jakiej rzeczywiście kopiować,

334
00:24:29,000 --> 00:24:32,000
ponieważ, jeśli nie brać pod uwagę fakt, że w regionie mamy do kopiowania

335
00:24:32,000 --> 00:24:35,000
zachodzi jeden mamy kopiowaniu,

336
00:24:35,000 --> 00:24:46,000
to może zrobimy tak jak początek tutaj, skopiować 2 na miejsce chcemy się udać,

337
00:24:46,000 --> 00:24:52,000
następnie przenieść nasze wskazówki do przodu.

338
00:24:52,000 --> 00:24:56,000
>> Teraz będziemy się tutaj i tutaj, a teraz chcemy skopiować

339
00:24:56,000 --> 00:25:04,000
ten facet to facet i przenieść nasze wskazówki do przodu.

340
00:25:04,000 --> 00:25:07,000
Co zamierzamy skończyć się to 2, 1, 2, 1, 2, 1

341
00:25:07,000 --> 00:25:10,000
zamiast odpowiedniego 2, 1, 2, 1, 3, 4, ponieważ

342
00:25:10,000 --> 00:25:15,000
2, 1 overrode oryginalny 3, 4.

343
00:25:15,000 --> 00:25:19,000
Memmove uchwyty, które w pełnym zakresie.

344
00:25:19,000 --> 00:25:23,000
W tym przypadku, w zasadzie tylko zawsze używać memmove

345
00:25:23,000 --> 00:25:26,000
bo obsługuje go prawidłowo.

346
00:25:26,000 --> 00:25:29,000
Generalnie nie należy wykonywać żadnych gorzej.

347
00:25:29,000 --> 00:25:32,000
Chodzi o to, a nie od początku i w ten sposób kopiowania

348
00:25:32,000 --> 00:25:35,000
tak jak my po prostu nie tutaj, to zaczyna się od końca i kopiuje w,

349
00:25:35,000 --> 00:25:38,000
iw tym przypadku, nigdy nie można mieć problem.

350
00:25:38,000 --> 00:25:40,000
Nie ma wydajność utracone.

351
00:25:40,000 --> 00:25:47,000
Zawsze używaj memmove. Nie martw się o memcopy.

352
00:25:47,000 --> 00:25:51,000
I to, gdzie będziesz musiał osobno memmove

353
00:25:51,000 --> 00:26:01,000
owinięty wokół część kolejce.

354
00:26:01,000 --> 00:26:04,000
Nie martw się, jeśli nie całkowicie wykonane.

355
00:26:04,000 --> 00:26:10,000
To jest trudniejsze niż stosu, push i pop.

356
00:26:10,000 --> 00:26:15,000
>> Ktoś ma jakiś kod, możemy współpracować?

357
00:26:15,000 --> 00:26:21,000
Nawet jeśli zupełnie niekompletne?

358
00:26:21,000 --> 00:26:23,000
[Student] Tak, to jest całkowicie niekompletna, choć.

359
00:26:23,000 --> 00:26:27,000
Kompletnie niekompletny jest w porządku tak długo, jak my-można zapisać zmiany?

360
00:26:27,000 --> 00:26:32,000
I zapomnieć, że za każdym razem.

361
00:26:32,000 --> 00:26:39,000
Okay, ignorując, co się dzieje, kiedy trzeba zmienić rozmiar rzeczy.

362
00:26:39,000 --> 00:26:42,000
Całkowicie ignorować resize.

363
00:26:42,000 --> 00:26:49,000
Wyjaśnij ten kod.

364
00:26:49,000 --> 00:26:54,000
Ja kontroli pierwsze Jeżeli rozmiar jest mniejszy niż na wstępie kopii

365
00:26:54,000 --> 00:27:01,000
a następnie po tym, wstawić-biorę głowę + rozmiar,

366
00:27:01,000 --> 00:27:05,000
i upewnić się, że otacza pojemności macierzy,

367
00:27:05,000 --> 00:27:08,000
i wstawić nowy ciąg w tej pozycji.

368
00:27:08,000 --> 00:27:12,000
Następnie zwiększyć rozmiar i zwróci true.

369
00:27:12,000 --> 00:27:22,000
>> [Rob B.] Jest to zdecydowanie jeden z tych przypadków, w których masz zamiar chcesz używać mod.

370
00:27:22,000 --> 00:27:25,000
Każdy rodzaj wypadku, w którym został owijania wokół, jeśli uważasz, owijając się dookoła,

371
00:27:25,000 --> 00:27:29,000
natychmiastowa myśl powinna być mod.

372
00:27:29,000 --> 00:27:36,000
W szybkiej optymalizacji / make kod jeden wiersz krótszy,

373
00:27:36,000 --> 00:27:42,000
można zauważyć, że linia bezpośrednio po ten jeden

374
00:27:42,000 --> 00:27:53,000
jest to tylko rozmiar + +, więc scalić, że do tej linii, wielkość + +.

375
00:27:53,000 --> 00:27:58,000
Teraz tu mamy przypadek

376
00:27:58,000 --> 00:28:01,000
gdzie nie ma wystarczającej ilości pamięci,

377
00:28:01,000 --> 00:28:05,000
więc podnosimy naszą zdolność przy 2.

378
00:28:05,000 --> 00:28:09,000
Myślę, że można mieć ten sam problem, ale można ignorować to teraz,

379
00:28:09,000 --> 00:28:13,000
gdzie jeśli nie udało się zwiększyć pojemność,

380
00:28:13,000 --> 00:28:18,000
następnie będziesz chciał zmniejszyć moc o 2 ponownie.

381
00:28:18,000 --> 00:28:24,000
Kolejna krótka notatka jest jak można zrobić + =,

382
00:28:24,000 --> 00:28:30,000
można też zrobić << =.

383
00:28:30,000 --> 00:28:43,000
Prawie wszystko może iść przed równymi, + =, | =, & =, << =.

384
00:28:43,000 --> 00:28:52,000
Char * nowy jest nasz nowy blok pamięci.

385
00:28:52,000 --> 00:28:55,000
O, tutaj.

386
00:28:55,000 --> 00:29:02,000
>> Co ludzie myślą o rodzaju naszego nowego bloku pamięci?

387
00:29:02,000 --> 00:29:06,000
[Student] Powinno być char **.

388
00:29:06,000 --> 00:29:12,000
Wracając do naszej struktury tu,

389
00:29:12,000 --> 00:29:14,000
strings jest co mamy realokacji.

390
00:29:14,000 --> 00:29:21,000
Wykonujemy cały nowy dynamiczny przechowywania elementów w kolejce.

391
00:29:21,000 --> 00:29:25,000
Co mamy zamiar być przypisanie do stringów jest co mamy mallocing teraz,

392
00:29:25,000 --> 00:29:30,000
a więc nowy będzie char **.

393
00:29:30,000 --> 00:29:34,000
To będzie tablica łańcuchów.

394
00:29:34,000 --> 00:29:38,000
Więc co jest w przypadku, w których mamy zamiar wrócić fałsz?

395
00:29:38,000 --> 00:29:41,000
[Student] powinniśmy robić char *?

396
00:29:41,000 --> 00:29:44,000
[Rob B.] Tak, dobre połączenie.

397
00:29:44,000 --> 00:29:46,000
[Student] Co to było?

398
00:29:46,000 --> 00:29:49,000
[Rob B.] Chcieliśmy zrobić rozmiar char *, ponieważ nie jesteśmy już-

399
00:29:49,000 --> 00:29:53,000
to byłby rzeczywiście bardzo duży problem, ponieważ sizeof (char) będzie 1.

400
00:29:53,000 --> 00:29:55,000
Sizeof char * będzie 4,

401
00:29:55,000 --> 00:29:58,000
tak wiele razy, gdy masz do czynienia z wskazówki,

402
00:29:58,000 --> 00:30:01,000
masz tendencję do uciec z nim, ponieważ wielkość i rozmiar int int *

403
00:30:01,000 --> 00:30:04,000
na systemie 32-bitowym będą samo.

404
00:30:04,000 --> 00:30:09,000
Ale tutaj, sizeof (char) i sizeof (char *) są teraz będzie tak samo.

405
00:30:09,000 --> 00:30:15,000
>> Co to jest sytuację, w której zwracamy fałsz?

406
00:30:15,000 --> 00:30:17,000
[Student] Nowy jest null.

407
00:30:17,000 --> 00:30:23,000
Tak, jeśli nowy jest null, zwracamy false,

408
00:30:23,000 --> 00:30:34,000
i mam zamiar rzucić tu

409
00:30:34,000 --> 00:30:37,000
[Student] [niesłyszalne]

410
00:30:37,000 --> 00:30:39,000
[Rob B.] Tak, to jest w porządku.

411
00:30:39,000 --> 00:30:46,000
Można albo zrobić 2 razy pojemność lub Shift pojemności 1 i tylko ustawić go tutaj lub cokolwiek.

412
00:30:46,000 --> 00:30:52,000
Zrobimy to jak miał.

413
00:30:52,000 --> 00:30:56,000
Pojemność >> = 1.

414
00:30:56,000 --> 00:31:08,000
I nigdy nie będziesz musiał martwić się o utratę tego 1 w miejsce

415
00:31:08,000 --> 00:31:12,000
bo zostawili przesunięty o 1, więc 1 na miejsce koniecznie 0,

416
00:31:12,000 --> 00:31:16,000
więc prawo przesunięcia o 1, to wciąż będzie dobrze.

417
00:31:16,000 --> 00:31:19,000
[Student] Czy trzeba to zrobić przed powrotem?

418
00:31:19,000 --> 00:31:29,000
[Rob B.] Tak, to sprawia, że ​​absolutnie nie ma sensu.

419
00:31:29,000 --> 00:31:36,000
>> Załóżmy teraz zamierzamy skończyć powrotem prawda do końca.

420
00:31:36,000 --> 00:31:39,000
Sposób będziemy robić te memmoves,

421
00:31:39,000 --> 00:31:45,000
Musimy być ostrożni z tym, jak je zrobić.

422
00:31:45,000 --> 00:31:50,000
Czy ktoś ma jakieś sugestie, jak my ich?

423
00:32:17,000 --> 00:32:21,000
Oto nasz start.

424
00:32:21,000 --> 00:32:28,000
Nieuchronnie, chcemy rozpocząć na początku ponownie

425
00:32:28,000 --> 00:32:35,000
i rzeczy, kopia w stamtąd, 1, 3, 4, 2.

426
00:32:35,000 --> 00:32:41,000
Jak to zrobić?

427
00:32:41,000 --> 00:32:52,000
Po pierwsze, muszę patrzeć na stronie podręcznika memmove ponownie.

428
00:32:52,000 --> 00:32:57,000
Memmove, kolejność argumentów jest zawsze ważne.

429
00:32:57,000 --> 00:33:01,000
Chcemy, aby nasze miejsce pierwsze, drugie źródło, trzeci wymiar.

430
00:33:01,000 --> 00:33:06,000
Istnieje wiele funkcji, które w odwrotnej źródło i cel.

431
00:33:06,000 --> 00:33:11,000
Cel podróży, źródło wydaje się być spójne nieco.

432
00:33:17,000 --> 00:33:21,000
Move, co to jest powrót?

433
00:33:21,000 --> 00:33:27,000
Zwraca wskaźnik do miejsca przeznaczenia, niezależnie od przyczyny, że warto.

434
00:33:27,000 --> 00:33:32,000
Mogę zdjęcie czytać, ale chcemy, aby przenieść się do naszego celu.

435
00:33:32,000 --> 00:33:35,000
>> Co jest naszym celem będzie?

436
00:33:35,000 --> 00:33:37,000
[Student] Nowy.

437
00:33:37,000 --> 00:33:39,000
[Rob B.] Tak, a gdzie jesteśmy kopiowania z?

438
00:33:39,000 --> 00:33:43,000
Pierwszą rzeczą, którą kopiujesz to 1, 3, 4.

439
00:33:43,000 --> 00:33:50,000
To, co jest w tym-1, 3, 4.

440
00:33:50,000 --> 00:33:55,000
Jaki jest adres tej 1?

441
00:33:55,000 --> 00:33:58,000
Jaki jest adres tej 1?

442
00:33:58,000 --> 00:34:01,000
[Student] [niesłyszalne]

443
00:34:01,000 --> 00:34:03,000
[Rob B.] Head + adres pierwszego elementu.

444
00:34:03,000 --> 00:34:05,000
Jak dostajemy pierwszy element tablicy?

445
00:34:05,000 --> 00:34:10,000
[Student] Queue.

446
00:34:10,000 --> 00:34:15,000
[Rob B.] Tak, q.strings.

447
00:34:15,000 --> 00:34:20,000
Pamiętaj, że tu nasza głowa jest 1.

448
00:34:20,000 --> 00:34:24,000
Cholernie go. Po prostu myślę, że to magicznie

449
00:34:24,000 --> 00:34:29,000
Oto nasza głowa jest 1. Zamierzam zmienić kolor też.

450
00:34:29,000 --> 00:34:36,000
I tu jest łańcuchami.

451
00:34:36,000 --> 00:34:41,000
To, możemy albo napisać go tak jak my tutaj

452
00:34:41,000 --> 00:34:43,000
z głowy + q.strings.

453
00:34:43,000 --> 00:34:51,000
Wiele osób również napisać go i q.strings [głowa].

454
00:34:51,000 --> 00:34:55,000
To nie jest ani trochę mniej wydajny.

455
00:34:55,000 --> 00:34:58,000
Można by pomyśleć o tym, jak są dereferencji go, a następnie uzyskiwanie adresu,

456
00:34:58,000 --> 00:35:04,000
ale kompilator będzie przetłumaczyć go do tego, co mieliśmy przed tak, q.strings + głowica.

457
00:35:04,000 --> 00:35:06,000
Albo tak, jak chcesz myśleć.

458
00:35:06,000 --> 00:35:11,000
>> I ile bajtów chcemy skopiować?

459
00:35:11,000 --> 00:35:15,000
[Student] Pojemność - głowa.

460
00:35:15,000 --> 00:35:18,000
Pojemność - głowa.

461
00:35:18,000 --> 00:35:21,000
A potem zawsze można napisać przykład

462
00:35:21,000 --> 00:35:23,000
dowiedzieć się, czy to prawda.

463
00:35:23,000 --> 00:35:26,000
[Student] To musi być podzielona przez 2 wtedy.

464
00:35:26,000 --> 00:35:30,000
Tak, więc myślę, że możemy użyć rozmiaru.

465
00:35:30,000 --> 00:35:35,000
Mamy jeszcze rozmiar bycia-

466
00:35:35,000 --> 00:35:39,000
przy wielkości, mamy wielkość równą 4.

467
00:35:39,000 --> 00:35:42,000
Nasz rozmiar to 4. Nasza głowa jest 1.

468
00:35:42,000 --> 00:35:46,000
Chcemy skopiować te 3 elementy.

469
00:35:46,000 --> 00:35:54,000
To rozsądek sprawdzić czy rozmiar - głowica jest prawidłowo 3.

470
00:35:54,000 --> 00:35:58,000
I tu wracać, jak powiedziałem wcześniej,

471
00:35:58,000 --> 00:36:00,000
gdybyśmy zdolności, wtedy musielibyśmy podzielić przez 2

472
00:36:00,000 --> 00:36:04,000
bo już uprawiane nasze możliwości, więc zamiast tego, mamy zamiar wykorzystać rozmiar.

473
00:36:11,000 --> 00:36:13,000
Że egzemplarze tej części.

474
00:36:13,000 --> 00:36:18,000
Teraz musimy skopiować drugą część, część, która jest na lewo od początku.

475
00:36:18,000 --> 00:36:28,000
>> Że zamierza memmove w jakiej pozycji?

476
00:36:28,000 --> 00:36:32,000
[Student] Rozmiar Plus - głowa.

477
00:36:32,000 --> 00:36:38,000
Tak, tak, mamy już skopiowane w wielkości - bajty głowy,

478
00:36:38,000 --> 00:36:43,000
a więc tam, gdzie chcemy, aby skopiować bajtów pozostałych jest nowy

479
00:36:43,000 --> 00:36:48,000
a następnie rozmiar minus-dobrze, liczba bajtów mamy już skopiowane w.

480
00:36:48,000 --> 00:36:52,000
A potem dokąd kopiowania z?

481
00:36:52,000 --> 00:36:54,000
[Student] Q.strings [0].

482
00:36:54,000 --> 00:36:56,000
[Rob B.] Tak, q.strings.

483
00:36:56,000 --> 00:37:02,000
Mogliśmy albo zrobić i q.strings [0].

484
00:37:02,000 --> 00:37:05,000
Jest to znacznie mniej, niż ten często.

485
00:37:05,000 --> 00:37:14,000
Jeśli jest to tylko będzie 0, wtedy postrzegają q.strings.

486
00:37:14,000 --> 00:37:16,000
To gdzie mamy kopiowanie z.

487
00:37:16,000 --> 00:37:18,000
Ile bajtów nam zostało skopiować? >> [Student] 10.

488
00:37:18,000 --> 00:37:20,000
Racja.

489
00:37:20,000 --> 00:37:25,000
[Student] Czy musimy pomnożyć 5 - 10 razy wielkość bajtów lub coś?

490
00:37:25,000 --> 00:37:30,000
Tak, tak, to gdzie-co dokładnie mamy kopiowanie?

491
00:37:30,000 --> 00:37:32,000
[Student] [niesłyszalne]

492
00:37:32,000 --> 00:37:34,000
Jaki jest rodzaj rzeczy mamy do kopiowania?

493
00:37:34,000 --> 00:37:36,000
[Student] [niesłyszalne]

494
00:37:36,000 --> 00:37:41,000
Tak, tak, char * s, że jesteśmy kopiowania, nie wiemy, gdzie te pochodzą.

495
00:37:41,000 --> 00:37:47,000
No, gdzie oni wskazując, jak struny, to w końcu popychając ją na kolejkę

496
00:37:47,000 --> 00:37:49,000
lub enqueuing na kolejki.

497
00:37:49,000 --> 00:37:51,000
Gdzie te pochodzą, nie mamy pojęcia.

498
00:37:51,000 --> 00:37:56,000
Musimy tylko śledzić char * s sami.

499
00:37:56,000 --> 00:38:00,000
Nie chcemy skopiować rozmiar - bajtów głowy.

500
00:38:00,000 --> 00:38:03,000
Chcemy skopiować rozmiar - głowica char * s,

501
00:38:03,000 --> 00:38:11,000
więc mamy zamiar pomnożyć to przez sizeof (* char).

502
00:38:11,000 --> 00:38:17,000
Sam tu, głowa * sizeof (char *).

503
00:38:17,000 --> 00:38:24,000
>> [Student] Co o [niesłyszalne]?

504
00:38:24,000 --> 00:38:26,000
To właśnie tutaj?

505
00:38:26,000 --> 00:38:28,000
[Student] Nie, poniżej, że rozmiar - głowa.

506
00:38:28,000 --> 00:38:30,000
[Rob B.] To tutaj?

507
00:38:30,000 --> 00:38:32,000
Arytmetyczna wskaźnika.

508
00:38:32,000 --> 00:38:35,000
Jak arytmetyka wskaźnik idzie do pracy jest

509
00:38:35,000 --> 00:38:40,000
automatycznie mnoży przez rozmiar typu, że mamy do czynienia.

510
00:38:40,000 --> 00:38:46,000
Tak jak tutaj, nowy + (rozmiar - głowica)

511
00:38:46,000 --> 00:38:56,000
jest dokładnie odpowiednikiem & New [size - Head]

512
00:38:56,000 --> 00:39:00,000
aż oczekujemy, że działa poprawnie,

513
00:39:00,000 --> 00:39:04,000
ponieważ jeśli mamy do czynienia z int tablicy, to nie robimy indeksu przez int-

514
00:39:04,000 --> 00:39:07,000
lub jeśli jest to od wielkości 5 i chcesz 4-ej, to indeks do

515
00:39:07,000 --> 00:39:10,000
int tablica [4].

516
00:39:10,000 --> 00:39:14,000
Ci nie-[4] * rozmiar wew.

517
00:39:14,000 --> 00:39:21,000
Że obsługuje go automatycznie, a tym przypadku

518
00:39:21,000 --> 00:39:29,000
jest dosłownie odpowiednik, więc składnia wspornik

519
00:39:29,000 --> 00:39:34,000
jest po prostu się być konwertowane do tego tak szybko, jak skompilować.

520
00:39:34,000 --> 00:39:38,000
To jest coś, co musisz uważać, że

521
00:39:38,000 --> 00:39:42,000
podczas dodawania rozmiar - głowica

522
00:39:42,000 --> 00:39:45,000
dodawania nie jeden bajt.

523
00:39:45,000 --> 00:39:53,000
Jesteś dodanie jednego char *, który może być jedno bajtów lub cokolwiek.

524
00:39:53,000 --> 00:39:56,000
>> Inne pytania?

525
00:39:56,000 --> 00:40:04,000
Okay, Dequeue będzie łatwiejsze.

526
00:40:04,000 --> 00:40:11,000
Dam ci chwilę na wdrożenie.

527
00:40:11,000 --> 00:40:18,000
Aha, i myślę, że to jest ta sama sytuacja, gdy

528
00:40:18,000 --> 00:40:21,000
co enqueue przypadku, jeśli mamy enqueuing null,

529
00:40:21,000 --> 00:40:24,000
Może chcemy poradzić, może nie.

530
00:40:24,000 --> 00:40:27,000
Nie będzie to jeszcze raz tutaj, ale sam, jak naszym przypadku stosu.

531
00:40:27,000 --> 00:40:34,000
Jeśli enqueue null, możemy chcieć go zignorować.

532
00:40:34,000 --> 00:40:40,000
Ktoś ma jakiś kod można podciągnąć?

533
00:40:40,000 --> 00:40:45,000
[Student] Mam tylko z kolejki.

534
00:40:45,000 --> 00:40:56,000
Wersja 2 jest to, że-w porządku.

535
00:40:56,000 --> 00:40:59,000
Chcesz wyjaśnić?

536
00:40:59,000 --> 00:41:01,000
[Student] Po pierwsze, upewnij się, że jest coś w kolejce

537
00:41:01,000 --> 00:41:07,000
Rozmiar i spada do 1.

538
00:41:07,000 --> 00:41:11,000
Musisz to zrobić, a następnie powrót głowę

539
00:41:11,000 --> 00:41:13,000
a następnie przesuń głowę 1.

540
00:41:13,000 --> 00:41:19,000
Okay, więc nie jest to przypadek rogu mamy do rozważenia. Tak.

541
00:41:19,000 --> 00:41:24,000
[Student] Jeśli Twoja głowa jest na ostatnim elemencie

542
00:41:24,000 --> 00:41:26,000
potem nie chcesz głowa wskazać poza tablicę.

543
00:41:26,000 --> 00:41:29,000
>> Tak, więc jak tylko głową uderza koniec naszej tablicy,

544
00:41:29,000 --> 00:41:35,000
gdy z kolejki, nasza głowa powinna być modded powrotem do 0.

545
00:41:35,000 --> 00:41:40,000
Niestety, nie możemy tego zrobić w jednym kroku.

546
00:41:40,000 --> 00:41:44,000
Chyba tak pewnie to naprawić

547
00:41:44,000 --> 00:41:52,000
to będzie char *, co mamy powrót,

548
00:41:52,000 --> 00:41:55,000
niezależnie od nazwy zmiennej chce być.

549
00:41:55,000 --> 00:42:02,000
Następnie chcemy mod przez głowę naszej zdolności

550
00:42:02,000 --> 00:42:10,000
a następnie powrócić ret.

551
00:42:10,000 --> 00:42:14,000
Wiele osób tutaj mogą do-

552
00:42:14,000 --> 00:42:19,000
jest to przypadek-Zobaczysz zrobić osoby, głowa

553
00:42:19,000 --> 00:42:29,000
jest większa od mocy, czy głowę - pojemność.

554
00:42:29,000 --> 00:42:36,000
A to tylko pracy wokół tego, co mod jest.

555
00:42:36,000 --> 00:42:41,000
Szef mod pojemność = jest znacznie czystsze

556
00:42:41,000 --> 00:42:51,000
z owijania wokół niż gdyby głowa większa od głowy pojemności - pojemność.

557
00:42:51,000 --> 00:42:56,000
>> Pytania?

558
00:42:56,000 --> 00:43:02,000
Okay, ostatnią rzeczą, zostawiliśmy to naszej listy.

559
00:43:02,000 --> 00:43:07,000
Może zostać użyty do niektórych zachowań połączonej listy jeśli nie

560
00:43:07,000 --> 00:43:11,000
powiązany list w swoim hash tabel, jeśli nie tabeli mieszania.

561
00:43:11,000 --> 00:43:15,000
Gorąco polecam ten hash tabeli.

562
00:43:15,000 --> 00:43:17,000
Mogłeś już szereg Trie,

563
00:43:17,000 --> 00:43:23,000
ale stara się trudniejsze.

564
00:43:23,000 --> 00:43:27,000
W teorii, są asymptotycznie lepiej.

565
00:43:27,000 --> 00:43:30,000
Ale wystarczy spojrzeć na wielkim statku,

566
00:43:30,000 --> 00:43:35,000
i stara się nie robić lepiej i zajmują więcej pamięci.

567
00:43:35,000 --> 00:43:43,000
Wszystko o stara kończy się gorzej więcej pracy.

568
00:43:43,000 --> 00:43:49,000
To właśnie rozwiązanie Davida Malan zawsze jest

569
00:43:49,000 --> 00:43:56,000
jest on zawsze swoje posty trie rozwiązanie, i zobaczymy, gdzie obecnie jest.

570
00:43:56,000 --> 00:44:00,000
Co miał mocy, David J?

571
00:44:00,000 --> 00:44:06,000
On jest # 18, tak że nie jest strasznie zły,

572
00:44:06,000 --> 00:44:09,000
i że będzie to jeden z najlepszych stara można myśleć

573
00:44:09,000 --> 00:44:17,000
lub jedna z najlepszym z Trie próbuje.

574
00:44:17,000 --> 00:44:23,000
Czy to nie jest nawet jego oryginalne rozwiązanie?

575
00:44:23,000 --> 00:44:29,000
Czuję trie rozwiązania są bardziej w tym zakresie zastosowania RAM.

576
00:44:29,000 --> 00:44:33,000
>> Idź w dół do samej góry, a zużycie RAM jest w jednej cyfry.

577
00:44:33,000 --> 00:44:36,000
Przejdź w dół w kierunku dna, a następnie zaczniesz widzieć próbuje

578
00:44:36,000 --> 00:44:41,000
gdzie można uzyskać absolutnie ogromne zużycie pamięci RAM,

579
00:44:41,000 --> 00:44:45,000
i próbuje się trudniejsze.

580
00:44:45,000 --> 00:44:53,000
Nie całkowicie warto ale doświadczenie edukacyjnych jeśli nie jeden.

581
00:44:53,000 --> 00:44:56,000
Ostatnią rzeczą jest naszą listę,

582
00:44:56,000 --> 00:45:04,000
i te trzy rzeczy, stosy, kolejki, listy, a także połączone

583
00:45:04,000 --> 00:45:09,000
każda kolejna rzecz, którą kiedykolwiek zrobić w informatyce

584
00:45:09,000 --> 00:45:12,000
zakłada, że ​​posiadamy znajomość tych rzeczy.

585
00:45:12,000 --> 00:45:19,000
Są po prostu tak podstawą wszystkiego.

586
00:45:19,000 --> 00:45:25,000
>> Linked list, a tu mamy pojedynczo połączonej listy będzie nasza realizacja.

587
00:45:25,000 --> 00:45:34,000
Co to znaczy, pojedynczo połączone w przeciwieństwie do podwójnie powiązane? Tak.

588
00:45:34,000 --> 00:45:37,000
[Student] To tylko wskazuje na kolejny wskaźnik, a nie do wskaźników,

589
00:45:37,000 --> 00:45:39,000
jak ten, przed nim i po nim jeden.

590
00:45:39,000 --> 00:45:44,000
Tak, więc w formie graficznej, co ja zrobiłem?

591
00:45:44,000 --> 00:45:48,000
Mam dwie rzeczy. Mam obraz i obraz.

592
00:45:48,000 --> 00:45:51,000
W formacie obrazu, nasze pojedynczo połączone listy,

593
00:45:51,000 --> 00:45:57,000
nieuchronnie, mamy jakiś wskaźnik na czele naszej listy,

594
00:45:57,000 --> 00:46:02,000
a następnie w naszej liście, musimy tylko wskaźniki,

595
00:46:02,000 --> 00:46:05,000
a może to wskazuje na null.

596
00:46:05,000 --> 00:46:08,000
To będzie typowy rysunek pojedynczo liście powiązane.

597
00:46:08,000 --> 00:46:14,000
Podwójnie połączonej listy można przejść do tyłu.

598
00:46:14,000 --> 00:46:19,000
Jeśli wezmę dowolny węzeł na liście, a następnie można zawsze dostać się do

599
00:46:19,000 --> 00:46:23,000
innego węzła w, jeżeli jest to listy dwukierunkowe.

600
00:46:23,000 --> 00:46:27,000
Ale gdybym ci trzeci węzeł z listy i to pojedynczo połączonej listy,

601
00:46:27,000 --> 00:46:30,000
żaden sposób nie jesteś kiedykolwiek dostanie do węzłów pierwszym i drugim.

602
00:46:30,000 --> 00:46:34,000
I nie ma korzyści i detriments i jeden oczywisty

603
00:46:34,000 --> 00:46:42,000
jest Ci zajmują więcej rozmiar, i trzeba śledzić, gdzie te rzeczy są wskazując teraz.

604
00:46:42,000 --> 00:46:49,000
Ale interesują nas tylko pojedynczo połączone.

605
00:46:49,000 --> 00:46:53,000
>> Kilka rzeczy, które będziemy mieć do wdrożenia.

606
00:46:53,000 --> 00:47:00,000
Twoja typedef struct node, int i: struct node * next; węzeł.

607
00:47:00,000 --> 00:47:09,000
To typedef powinien być spalany w waszych umysłach.

608
00:47:09,000 --> 00:47:14,000
Quiz 1 powinno być jak dać typedef z węzła połączonej listy

609
00:47:14,000 --> 00:47:18,000
i powinieneś być w stanie natychmiast bazgroły, że w dół

610
00:47:18,000 --> 00:47:22,000
nawet nie myśląc o tym.

611
00:47:22,000 --> 00:47:27,000
Chyba kilka pytań, dlaczego musimy struct tutaj?

612
00:47:27,000 --> 00:47:32,000
Dlaczego nie możemy powiedzieć węzła *?

613
00:47:32,000 --> 00:47:35,000
[Student] [niesłyszalne]

614
00:47:35,000 --> 00:47:38,000
Tak.

615
00:47:38,000 --> 00:47:44,000
Jedyną rzeczą, która określa węzeł jako rzecz

616
00:47:44,000 --> 00:47:47,000
jest typedef sama.

617
00:47:47,000 --> 00:47:55,000
Ale od tego momentu, gdy jesteśmy rodzaju analizowania przez tą definicją węzła struct,

618
00:47:55,000 --> 00:48:01,000
nie skończyliśmy nasz typedef jeszcze, więc od typedef nie zostało zakończone,

619
00:48:01,000 --> 00:48:05,000
Węzeł nie istnieje.

620
00:48:05,000 --> 00:48:12,000
Ale struct node robi, a ten węzeł w tutaj,

621
00:48:12,000 --> 00:48:14,000
może to być również nazywane niczego innego.

622
00:48:14,000 --> 00:48:16,000
To może być nazywany N.

623
00:48:16,000 --> 00:48:19,000
Może być ona wywołana linked węzeł lista.

624
00:48:19,000 --> 00:48:21,000
Może być ona wywołana nic.

625
00:48:21,000 --> 00:48:26,000
Ale ten węzeł struct musi być wywoływana to samo, co ten węzeł struktury.

626
00:48:26,000 --> 00:48:29,000
To, co nazywasz to musi być również tutaj,

627
00:48:29,000 --> 00:48:32,000
również i tak, że drugi punkt odpowiedzi na pytanie

628
00:48:32,000 --> 00:48:37,000
dlatego-Wiele razy, gdy widzisz structury i typedef w elemencie,

629
00:48:37,000 --> 00:48:42,000
zobaczysz anonimowych przypisać struktury, gdzie można po prostu zobaczyć typedef struct,

630
00:48:42,000 --> 00:48:47,000
Realizacja struct, słownik, czy cokolwiek innego.

631
00:48:47,000 --> 00:48:51,000
>> Dlaczego tutaj nie trzeba powiedzieć węzeł?

632
00:48:51,000 --> 00:48:54,000
Dlaczego nie może być anonimowy struct?

633
00:48:54,000 --> 00:48:56,000
To prawie taka sama odpowiedź.

634
00:48:56,000 --> 00:48:58,000
[Student] Musisz odwołać się do niej w ramach struktury.

635
00:48:58,000 --> 00:49:04,000
Tak, w ramach struktury, trzeba odwołać się do samej struktury.

636
00:49:04,000 --> 00:49:10,000
Jeśli nie da struct nazwę, jeśli jest anonimowy struct, nie można odwoływać się do niego.

637
00:49:10,000 --> 00:49:17,000
I last but not least one powinny być w całości nieco proste,

638
00:49:17,000 --> 00:49:20,000
i powinny pomóc osiągnąć jeśli piszesz to w dół

639
00:49:20,000 --> 00:49:24,000
że robisz coś źle, jeśli tego rodzaju rzeczy nie mają sensu.

640
00:49:24,000 --> 00:49:28,000
Last but not least, dlaczego to ma być * węzeł struct?

641
00:49:28,000 --> 00:49:34,000
Dlaczego nie może być po prostu struct węzeł następny?

642
00:49:34,000 --> 00:49:37,000
[Student] Wskaźnik do następnej struktury.

643
00:49:37,000 --> 00:49:39,000
To nieuniknione, co chcemy.

644
00:49:39,000 --> 00:49:42,000
Dlaczego nigdy nie mógł to być węzeł struct następny?

645
00:49:42,000 --> 00:49:50,000
Dlaczego to musi być struct node * next? Tak.

646
00:49:50,000 --> 00:49:53,000
[Student] To jak nieskończoną pętlę.

647
00:49:53,000 --> 00:49:55,000
Tak.

648
00:49:55,000 --> 00:49:57,000
[Student] To wszystko będzie w jednym.

649
00:49:57,000 --> 00:50:02,000
Tak, tylko, że jak zrobimy rozmiaru czy coś.

650
00:50:02,000 --> 00:50:08,000
Rozmiar struktury jest zasadniczo + lub - niektóre wzór tu czy tam.

651
00:50:08,000 --> 00:50:15,000
Jest to w zasadzie będzie to suma wielkości rzeczy w struktury.

652
00:50:15,000 --> 00:50:18,000
To właśnie tutaj, nie zmieniając niczego, rozmiar będzie łatwe.

653
00:50:18,000 --> 00:50:24,000
Wielkość węzła struct będzie rozmiar I Standard + z następnym.

654
00:50:24,000 --> 00:50:27,000
Wielkość I będzie 4. Rozmiar następnego będzie 4.

655
00:50:27,000 --> 00:50:30,000
Wielkość węzła struct będzie 8.

656
00:50:30,000 --> 00:50:34,000
Jeśli nie ma *, myśląc o sizeof,

657
00:50:34,000 --> 00:50:37,000
następnie sizeof (i) będzie 4.

658
00:50:37,000 --> 00:50:43,000
Wielkość węzła struct następny będzie rozmiar I Standard + węzła struct kolejnego

659
00:50:43,000 --> 00:50:46,000
Rozmiar + z I Standard + struct kolejnego węzła.

660
00:50:46,000 --> 00:50:55,000
Byłoby nieskończonej rekurencji węzłów.

661
00:50:55,000 --> 00:51:00,000
Dlatego to jest to, jak rzeczy mają być.

662
00:51:00,000 --> 00:51:03,000
>> Ponownie, zdecydowanie zapamiętać, że

663
00:51:03,000 --> 00:51:06,000
lub przynajmniej zrozumieć tyle, że możesz być w stanie

664
00:51:06,000 --> 00:51:12,000
Powodem przez co powinno wyglądać.

665
00:51:12,000 --> 00:51:14,000
Rzeczy, które zamierzamy chcą wprowadzić.

666
00:51:14,000 --> 00:51:18,000
Jeśli długość listy-

667
00:51:18,000 --> 00:51:21,000
można oszukać i zachować wokół

668
00:51:21,000 --> 00:51:24,000
globalny długość czy coś, ale nie będziemy tego robić.

669
00:51:24,000 --> 00:51:28,000
Będziemy liczyć długość listy.

670
00:51:28,000 --> 00:51:34,000
Mamy zawiera, tak, że w zasadzie jak wyszukiwanie,

671
00:51:34,000 --> 00:51:41,000
więc mamy związane listę liczb całkowitych, aby sprawdzić czy całkowita jest w połączonej listy.

672
00:51:41,000 --> 00:51:44,000
PREPEND będzie wprowadzić na początku na liście.

673
00:51:44,000 --> 00:51:46,000
Append będzie wstawić na końcu.

674
00:51:46,000 --> 00:51:53,000
Insert_sorted będzie wstawić do sortowanie pozycji na liście.

675
00:51:53,000 --> 00:52:01,000
Insert_sorted rodzaju zakłada się, że nigdy nie używane prepend lub dołączyć w złych sposobów.

676
00:52:01,000 --> 00:52:09,000
>> Insert_sorted kiedy wdrożenie insert_sorted-

677
00:52:09,000 --> 00:52:13,000
powiedzmy mamy naszej listy.

678
00:52:13,000 --> 00:52:18,000
To jest to, co obecnie wygląda, 2, 4, 5.

679
00:52:18,000 --> 00:52:24,000
Chcę wkładki 3, tak długo, jak długo jest już sama lista posortowane

680
00:52:24,000 --> 00:52:27,000
łatwo jest znaleźć gdzie 3 należy.

681
00:52:27,000 --> 00:52:29,000
I zaczynają się od 2.

682
00:52:29,000 --> 00:52:32,000
Okay, 3 jest większa niż 2, więc chcę iść dalej.

683
00:52:32,000 --> 00:52:35,000
Oh, 4 jest zbyt duży, więc wiem, 3 będzie przejść między 2 i 4,

684
00:52:35,000 --> 00:52:39,000
i muszę naprawić wskaźniki i wszystkie rzeczy.

685
00:52:39,000 --> 00:52:43,000
Ale jeśli nie będziemy ściśle stosować insert_sorted,

686
00:52:43,000 --> 00:52:50,000
jak powiedzmy I dołączy 6,

687
00:52:50,000 --> 00:52:55,000
wtedy moja linked lista będzie coraz to.

688
00:52:55,000 --> 00:53:01,000
Teraz nie ma sensu, więc dla insert_sorted, można po prostu założyć,

689
00:53:01,000 --> 00:53:04,000
że lista jest sortowana, choć istnieją operacje

690
00:53:04,000 --> 00:53:09,000
co może spowodować, że nie mają być sortowane, i to jest to.

691
00:53:09,000 --> 00:53:20,000
Znajdź przydatne insert-tak to główne rzeczy, które będziemy mieć do wdrożenia.

692
00:53:20,000 --> 00:53:24,000
>> Na razie, poświęć chwilę uwagi długości i zawiera,

693
00:53:24,000 --> 00:53:30,000
i te powinny być stosunkowo szybkie.

694
00:53:41,000 --> 00:53:48,000
Zbliża czasu zamknięcia, więc ktoś ma coś na długość lub zawiera?

695
00:53:48,000 --> 00:53:50,000
Będą się być niemal identyczne.

696
00:53:50,000 --> 00:53:57,000
[Student] Długość.

697
00:53:57,000 --> 00:54:01,000
Zobaczmy rewizji.

698
00:54:01,000 --> 00:54:04,000
Okay.

699
00:54:12,000 --> 00:54:15,000
Chcesz wyjaśnić?

700
00:54:15,000 --> 00:54:21,000
[Student] po prostu utworzyć węzeł wskaźnik i zainicjować go do pierwszego, który jest naszym zmiennej globalnej,

701
00:54:21,000 --> 00:54:27,000
, a potem sprawdzić, czy to jest zerowy, więc nie dostać SEG usterkę i zwraca 0, jeśli tak jest.

702
00:54:27,000 --> 00:54:34,000
W przeciwnym razie, w pętli, śledzenie terminie całkowitą

703
00:54:34,000 --> 00:54:38,000
ile razy mam dostęp do następnego elementu listy

704
00:54:38,000 --> 00:54:43,000
i w tej samej operacji, również dostęp do przyrostu, że rzeczywista elementu

705
00:54:43,000 --> 00:54:47,000
a ja ciągle się sprawdzić, czy to jest null,

706
00:54:47,000 --> 00:54:56,000
i jeśli jest pusta, to przerywa i po prostu zwraca liczbę elementów mam dostęp.

707
00:54:56,000 --> 00:55:01,000
>> [Rob B.] Czy ktoś ma jakieś uwagi na temat czegokolwiek?

708
00:55:01,000 --> 00:55:06,000
To wygląda dobrze poprawności mądry.

709
00:55:06,000 --> 00:55:10,000
[Student] Nie sądzę, trzeba węzeł == null.

710
00:55:10,000 --> 00:55:13,000
Tak, więc jeśli węzeł == null 0 powrotu.

711
00:55:13,000 --> 00:55:18,000
Ale jeśli node == null to ta-oh, jest kwestia poprawności.

712
00:55:18,000 --> 00:55:23,000
To było po prostu jesteś powrotu i, ale to nie jest w zakresie teraz.

713
00:55:23,000 --> 00:55:30,000
Trzeba tylko int i, tak i = 0.

714
00:55:30,000 --> 00:55:34,000
Ale jeśli węzeł jest pusta, to i nadal będzie 0,

715
00:55:34,000 --> 00:55:39,000
i zamierzamy wrócić 0, więc ta sprawa jest identyczna.

716
00:55:39,000 --> 00:55:48,000
Inną powszechną rzeczą jest przechowywanie deklaracji

717
00:55:48,000 --> 00:55:51,000
z wewnątrz węzła pętli for.

718
00:55:51,000 --> 00:55:54,000
Można powiedzieć, oh, no.

719
00:55:54,000 --> 00:55:56,000
Trzymajmy to jak ta.

720
00:55:56,000 --> 00:55:59,000
Prawdopodobnie umieścić int i = 0 tutaj

721
00:55:59,000 --> 00:56:05,000
następnie węzeł * node = pierwszy tutaj.

722
00:56:05,000 --> 00:56:11,000
I to jest chyba jak-pozbyć się tego teraz.

723
00:56:11,000 --> 00:56:14,000
Prawdopodobnie jest to w jaki sposób to napisałem.

724
00:56:14,000 --> 00:56:21,000
Można również, patrząc na to w ten sposób.

725
00:56:21,000 --> 00:56:25,000
To dla struktury pętli tutaj

726
00:56:25,000 --> 00:56:30,000
powinny być prawie tak naturalne dla ciebie jak dla int i = 0

727
00:56:30,000 --> 00:56:33,000
i jest mniejsza niż długość tablicy I + +.

728
00:56:33,000 --> 00:56:38,000
Jeżeli tak jest, w jaki sposób iteracyjne nad tablicy, jest to, w jaki sposób iteracyjne nad połączonej listy.

729
00:56:38,000 --> 00:56:45,000
>> To powinno być drugą naturą w pewnym momencie.

730
00:56:45,000 --> 00:56:50,000
Mając to na uwadze, to będzie prawie to samo.

731
00:56:50,000 --> 00:56:57,000
Będziesz chcą iterować połączonej listy.

732
00:56:57,000 --> 00:57:02,000
Jeśli węzeł-nie mam pojęcia, jaka jest wartość jest wywoływana.

733
00:57:02,000 --> 00:57:04,000
Gałąź i.

734
00:57:04,000 --> 00:57:15,000
Jeśli wartość w tym węźle = i zwraca true, i to jest to.

735
00:57:15,000 --> 00:57:18,000
Zauważ, że jedynym sposobem kiedykolwiek wrócimy false

736
00:57:18,000 --> 00:57:23,000
jest jeśli iterować całej listy połączonej i nigdy nie wracać prawda

737
00:57:23,000 --> 00:57:29,000
więc to co to robi.

738
00:57:29,000 --> 00:57:36,000
Jako side note-prawdopodobnie nie będzie dostać się do dołączania lub dołączy.

739
00:57:36,000 --> 00:57:39,000
>> Szybkie ostatnia uwaga.

740
00:57:39,000 --> 00:57:52,000
Jeśli widzisz słowa kluczowego static, więc powiedzmy, że static int count = 0,

741
00:57:52,000 --> 00:57:56,000
potem liczą + +, można w zasadzie myśleć o nim jako zmiennej globalnej,

742
00:57:56,000 --> 00:58:00,000
chociaż właśnie powiedziałem to nie jest to, jak będziemy realizować długość.

743
00:58:00,000 --> 00:58:06,000
Robię to tutaj, a następnie liczyć + +.

744
00:58:06,000 --> 00:58:11,000
Każdy sposób możemy wprowadzić do naszego węzła połączonej listy jesteśmy zwiększający nasz licznik.

745
00:58:11,000 --> 00:58:15,000
Punktem jest to, co statyczne keyword oznacza.

746
00:58:15,000 --> 00:58:20,000
Gdybym tylko miał int count = 0 byłoby regularne stary zmienną globalną.

747
00:58:20,000 --> 00:58:25,000
Oznacza to, co statyczne int Ilość jest, że jest to w tym zmienna globalna pliku.

748
00:58:25,000 --> 00:58:28,000
To jest możliwe w innym pliku,

749
00:58:28,000 --> 00:58:34,000
lubię myśleć Pset 5, jeśli już się rozpoczęły.

750
00:58:34,000 --> 00:58:39,000
Masz zarówno speller.c i masz dictionary.c,

751
00:58:39,000 --> 00:58:42,000
a jeśli po prostu zadeklarować coś globalnego, a następnie coś w speller.c

752
00:58:42,000 --> 00:58:45,000
mogą być dostępne w dictionary.c i odwrotnie.

753
00:58:45,000 --> 00:58:48,000
Zmienne globalne są dostępne dla każdego pliku. C,

754
00:58:48,000 --> 00:58:54,000
ale zmienne statyczne są dostępne tylko w ramach samego pliku,

755
00:58:54,000 --> 00:59:01,000
tak wewnątrz sprawdzania pisowni lub wewnątrz dictionary.c,

756
00:59:01,000 --> 00:59:06,000
jest to rodzaj jak ja deklaruję zmienną do rozmiaru mojego tablicy

757
00:59:06,000 --> 00:59:10,000
lub wielkości mojej liczby słów w słowniku.

758
00:59:10,000 --> 00:59:15,000
Ponieważ nie chcę, aby zadeklarować zmienną globalną, że każdy ma dostęp do

759
00:59:15,000 --> 00:59:18,000
I tak naprawdę tylko dbam o to dla własnych celów.

760
00:59:18,000 --> 00:59:21,000
>> Dobrą rzeczą jest to również cały stuff kolizji nazw.

761
00:59:21,000 --> 00:59:27,000
Jeśli inny plik próbuje użyć zmiennej globalnej o nazwie count, sprawy idą bardzo, bardzo źle,

762
00:59:27,000 --> 00:59:33,000
tak to ładnie utrzymuje rzeczy bezpieczne, a tylko można do niego dostęp,

763
00:59:33,000 --> 00:59:38,000
i nikt inny nie może, a jeśli ktoś deklaruje zmienną globalną o nazwie count,

764
00:59:38,000 --> 00:59:43,000
to nie będzie przeszkadzać w zmiennej statycznej o nazwie count.

765
00:59:43,000 --> 00:59:47,000
To, co jest statyczne. Jest to plik zmienną globalną.

766
00:59:47,000 --> 00:59:52,000
>> Pytania na cokolwiek?

767
00:59:52,000 --> 00:59:59,000
Wszystko gotowe. Bye.

768
00:59:59,000 --> 01:00:03,000
[CS50.TV]