1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Rozdział 6: Mniej Comfortable]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[To jest CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Dobrze. Witamy w dziale 6.

5
00:00:11,840 --> 00:00:14,690
W tym tygodniu będziemy mówić o strukturach danych w przekroju,

6
00:00:14,690 --> 00:00:19,780
głównie dlatego, że w tym tygodniu problemu ustawić na spellr

7
00:00:19,780 --> 00:00:24,410
robi cała masa różnych struktury danych eksploracji.

8
00:00:24,410 --> 00:00:26,520
Istnieje kilka różnych sposobów, można przejść do zestawu problemów,

9
00:00:26,520 --> 00:00:31,570
i więcej struktur danych znasz, tym więcej fajnych rzeczy można zrobić.

10
00:00:31,570 --> 00:00:34,990
>> Więc zaczynajmy. Najpierw będziemy rozmawiać o stosy,

11
00:00:34,990 --> 00:00:37,530
stosu i kolejki struktury danych, że będziemy o tym mówić.

12
00:00:37,530 --> 00:00:40,560
Stosy i kolejki są naprawdę pomocne, gdy zaczynamy mówić o wykresach,

13
00:00:40,560 --> 00:00:44,390
którego nie będziemy robić tak dużo teraz.

14
00:00:44,390 --> 00:00:52,820
Ale oni są naprawdę dobrze zrozumieć jedną z wielkich podstawowych struktur danych CS.

15
00:00:52,820 --> 00:00:54,880
Opis w specyfikacji zestaw problemów,

16
00:00:54,880 --> 00:00:59,260
jeśli wyciągnij go, opowiada o stosach jako pokrewny

17
00:00:59,260 --> 00:01:05,239
stos tac gastronomicznych, że masz w stołówce w salach jadalnych

18
00:01:05,239 --> 00:01:09,680
gdzie, kiedy personel dining przychodzi i stawia zasobników stołować po ich czyścić je,

19
00:01:09,680 --> 00:01:12,000
one stosu je jeden na drugim.

20
00:01:12,000 --> 00:01:15,050
I wtedy, gdy dzieci są w celu zdobycia pożywienia,

21
00:01:15,050 --> 00:01:19,490
ciągną się zasobniki pierwszy góry jeden, a następnie jeden pod nią, a następnie jeden poniżej.

22
00:01:19,490 --> 00:01:25,190
Tak więc, w efekcie, pierwszy podajnik personel dining odłożyć jest ostatnim, który jest zdjęty.

23
00:01:25,190 --> 00:01:32,330
Ostatni, że personel dining wprowadzone jest pierwszą, która zostanie zdjęta na kolację.

24
00:01:32,330 --> 00:01:38,100
W zestawie problemu w specyfikacji, którą można pobrać, jeśli jeszcze go nie masz,

25
00:01:38,100 --> 00:01:46,730
mówimy o modelowanie stucture danych stosu przy użyciu tego rodzaju struktury.

26
00:01:46,730 --> 00:01:51,070
>> Więc co tu mamy, to jest podobne do tego, co zostało przedstawione w wykładzie

27
00:01:51,070 --> 00:01:58,120
wyjątkiem wykładu przedstawiliśmy to z liczb całkowitych, w przeciwieństwie do char * s.

28
00:01:58,120 --> 00:02:06,250
To będzie stos przechowujący co?

29
00:02:06,250 --> 00:02:09,009
Daniel? Co my przechowywania tego stosu?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Jesteśmy przechowywania ciągów w tym stosie, dokładnie.

31
00:02:15,260 --> 00:02:20,950
Wszystko, co musisz mieć, aby utworzyć stos jest tablicą

32
00:02:20,950 --> 00:02:23,920
danego pojemności, które w tym przypadku,

33
00:02:23,920 --> 00:02:28,020
pojemność będzie wielkimi literami, ponieważ jest stała.

34
00:02:28,020 --> 00:02:36,340
, A następnie, w uzupełnieniu do tablicy wszystkie potrzebne śledzenie jest obecny rozmiar tablicy.

35
00:02:36,340 --> 00:02:38,980
Warto zauważyć tutaj, że to fajne

36
00:02:38,980 --> 00:02:47,060
jest to, że mamy do tworzenia struktury danych ułożone na szczycie innej struktury danych, tablicy.

37
00:02:47,060 --> 00:02:50,110
Istnieją różne sposoby, aby wdrożyć stosy.

38
00:02:50,110 --> 00:02:54,250
Nie zrobi to dość jeszcze, ale mam nadzieję, że po wykonaniu linkowane listy problemów

39
00:02:54,250 --> 00:03:00,520
zobaczysz, jak łatwo można zaimplementować stos na górze połączonej listy, jak również.

40
00:03:00,520 --> 00:03:02,640
Ale teraz będziemy trzymać się tych tablic.

41
00:03:02,640 --> 00:03:06,350
Więc jeszcze raz, wszystko, czego potrzebujesz to tablica i po prostu trzeba śledzić rozmiar tablicy.

42
00:03:06,350 --> 00:03:09,850
[Sam] Przepraszam, dlaczego jest tak, że pan powiedział, że stos jest na szczycie ciągów?

43
00:03:09,850 --> 00:03:13,440
Dla mnie wydaje się, że ciągi są w stos.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Tak. Tworzymy bierzemy naszą strukturę danych do tablicy -

45
00:03:16,790 --> 00:03:22,130
to jest dobre pytanie. Więc pytanie jest, dlaczego, dla ludzi, którzy oglądają ten online,

46
00:03:22,130 --> 00:03:24,140
to dlaczego mówi się, że stos jest na szczycie strun,

47
00:03:24,140 --> 00:03:27,990
bo tu wygląda jak struny są wewnątrz stosu?

48
00:03:27,990 --> 00:03:31,050
Co jest zupełnie inaczej.

49
00:03:31,050 --> 00:03:34,660
Co miałem na myśli to, że mamy strukturę danych tablicy.

50
00:03:34,660 --> 00:03:39,290
Mamy tablicę char * s, to tablicę ciągów,

51
00:03:39,290 --> 00:03:45,300
i mamy zamiar dodać do tego, aby stworzyć ułożone struktury danych.

52
00:03:45,300 --> 00:03:48,620
>> Więc stos jest nieco bardziej skomplikowana niż tablicy.

53
00:03:48,620 --> 00:03:51,890
Możemy używać tablicy zbudować stos.

54
00:03:51,890 --> 00:03:55,810
Więc to, gdzie mówimy, że stos jest zbudowany na górze tablicy.

55
00:03:55,810 --> 00:04:02,510
Podobnie, jak powiedziałem wcześniej, możemy zbudować stos na górze połączonej listy.

56
00:04:02,510 --> 00:04:04,960
Zamiast używać tablicy do przechowywania naszych elementów,

57
00:04:04,960 --> 00:04:10,070
możemy użyć połączonej listy trzymać nasze elementy i zbudować stos wokół niego.

58
00:04:10,070 --> 00:04:12,420
Przejdźmy przez kilka przykładów, patrząc na niektóre kodu,

59
00:04:12,420 --> 00:04:14,960
zobaczyć, co się właściwie dzieje.

60
00:04:14,960 --> 00:04:23,400
Po lewej stronie, mam zwalony co to struct stos będzie wyglądać w pamięci

61
00:04:23,400 --> 00:04:28,330
jeśli pojemność zostały # definiuje się cztery.

62
00:04:28,330 --> 00:04:33,490
Mamy nasze cztery elementu tablicy char *.

63
00:04:33,490 --> 00:04:38,110
Mamy łańcuchy [0], smyczki [1], łańcuchy [2], nicie [3],

64
00:04:38,110 --> 00:04:43,800
, a następnie, że w zeszłym przestrzeń dla naszej całkowitej wielkości.

65
00:04:43,800 --> 00:04:46,270
Czy to ma sens? Okay.

66
00:04:46,270 --> 00:04:48,790
To jest to, co się stanie, jeśli to, co robię na prawo,

67
00:04:48,790 --> 00:04:55,790
który będzie mój kod, to po prostu stwierdzenie, struct, struct stos nazywane s.

68
00:04:55,790 --> 00:05:01,270
To jest to, co mamy. Ustanawia ona ten ślad w pamięci.

69
00:05:01,270 --> 00:05:05,590
Pierwsze pytanie o to, jakie są zawartość tej struktury stosu?

70
00:05:05,590 --> 00:05:09,250
Teraz są one niczym, ale nie są one zupełnie nic.

71
00:05:09,250 --> 00:05:13,300
Są tego rodzaju śmieci. Nie mamy pojęcia, co jest w nich.

72
00:05:13,300 --> 00:05:17,000
Kiedy deklarujemy s stosu, po prostu rzuca, że ​​w dół na szczycie pamięci.

73
00:05:17,000 --> 00:05:19,840
To trochę tak jak stwierdzenie, a nie int i inicjalizacji.

74
00:05:19,840 --> 00:05:21,730
Nie wiem, co jest w środku. Można przeczytać, co tam jest,

75
00:05:21,730 --> 00:05:27,690
ale to nie może być super pomocny.

76
00:05:27,690 --> 00:05:32,680
Jedną rzeczą, którą chcesz, aby zawsze pamiętać, aby zrobić to zainicjować cokolwiek musi być zainicjowany.

77
00:05:32,680 --> 00:05:35,820
W tym przypadku, mamy zamiar zainicjować rozmiar wynosi zero,

78
00:05:35,820 --> 00:05:39,960
dlatego, że zamierza okazać się dla nas bardzo ważne.

79
00:05:39,960 --> 00:05:43,450
Możemy pójść dalej i zainicjować wszystkie wskaźniki, wszystko char s *,

80
00:05:43,450 --> 00:05:49,670
być jakiś zrozumiały wartość, prawdopodobnie null.

81
00:05:49,670 --> 00:05:58,270
Ale to nie jest konieczne, że całkowicie to zrobić.

82
00:05:58,270 --> 00:06:04,200
>> Teraz, dwa główne operacje na stosach są?

83
00:06:04,200 --> 00:06:07,610
Ktoś pamięta z wykładu, co zrobić ze stosami? Tak?

84
00:06:07,610 --> 00:06:09,700
[Stella] Pushing i popping? >> Dokładnie.

85
00:06:09,700 --> 00:06:13,810
Pchanie i popping to dwa główne operacje na stosach.

86
00:06:13,810 --> 00:06:17,060
A co Push zrobić? >> To stawia coś na górze

87
00:06:17,060 --> 00:06:19,300
stosu, a następnie popping zdejmuje.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Dokładnie. Więc popychanie pcha coś na górze stosu.

89
00:06:23,150 --> 00:06:27,700
To jak oddanie pracowników jadalni tacę jadalną na ladę.

90
00:06:27,700 --> 00:06:33,630
I popping bierze tacę jadalną off stosu.

91
00:06:33,630 --> 00:06:36,460
Przejdźmy przez kilka przykładów tego, co się dzieje

92
00:06:36,460 --> 00:06:39,720
kiedy wcisnąć rzeczy do stosu.

93
00:06:39,720 --> 00:06:45,110
Gdybyśmy mieli naciskać ciąg "Hello" na nasz stosu

94
00:06:45,110 --> 00:06:49,760
jest to, co nasz diagram będzie wyglądał tak jak teraz.

95
00:06:49,760 --> 00:06:53,410
Zobacz, co się dzieje?

96
00:06:53,410 --> 00:06:56,530
Mamy wepchnięty do pierwszego elementu naszej tablicy ciągów

97
00:06:56,530 --> 00:07:01,420
i podniósł naszą liczbę rozmiar będzie 1.

98
00:07:01,420 --> 00:07:05,340
Więc jeśli spojrzymy na różnicę między dwoma zjeżdżalniami, tutaj było 0, tu przed naciśnięciem.

99
00:07:05,340 --> 00:07:08,690
Tu jest po naciśnięciu.

100
00:07:08,690 --> 00:07:13,460
Przed naciśnięciem po push.

101
00:07:13,460 --> 00:07:16,860
A teraz mamy jeden element w naszej stosie.

102
00:07:16,860 --> 00:07:20,970
Jest to ciąg znaków "hello", a to jest to.

103
00:07:20,970 --> 00:07:24,440
Wszystko inne w tablicy, w naszej tablicy ciągów, nadal śmieci.

104
00:07:24,440 --> 00:07:27,070
Nie zainicjowany go.

105
00:07:27,070 --> 00:07:29,410
Powiedzmy, że wcisnąć inny ciąg na nasz stos.

106
00:07:29,410 --> 00:07:32,210
Będziemy naciskać "świat" w tym czasie.

107
00:07:32,210 --> 00:07:35,160
Więc widać, "świat" tu idzie na górze "hello",

108
00:07:35,160 --> 00:07:40,040
Ilość i rozmiar wzrasta do 2.

109
00:07:40,040 --> 00:07:44,520
Teraz możemy wcisnąć "CS50", i że pójdzie na wierzchu ponownie.

110
00:07:44,520 --> 00:07:51,110
Jeśli wrócimy, można zobaczyć, jak mamy popychanie rzeczy na wierzchu stosu.

111
00:07:51,110 --> 00:07:53,320
A teraz mamy do pop.

112
00:07:53,320 --> 00:07:58,910
Kiedy wpadliśmy coś z stosu, co się stało?

113
00:07:58,910 --> 00:08:01,540
Ktoś widzi różnicę? Jest to dość subtelne.

114
00:08:01,540 --> 00:08:05,810
[Student] rozmiar. >> Tak, zmienił się rozmiar.

115
00:08:05,810 --> 00:08:09,040
>> Co jeszcze spodziewać się zmienić?

116
00:08:09,040 --> 00:08:14,280
[Student] Łańcuchy, too. >> Racja. Łańcuchy też.

117
00:08:14,280 --> 00:08:17,110
Okazuje się, że kiedy robisz to w ten sposób,

118
00:08:17,110 --> 00:08:21,960
ponieważ nie jesteśmy kopiowanie elementów do naszego komina,

119
00:08:21,960 --> 00:08:24,670
tak naprawdę nie trzeba nic robić, możemy po prostu użyć rozmiaru

120
00:08:24,670 --> 00:08:28,630
śledzenie liczby rzeczy w naszej tablicy

121
00:08:28,630 --> 00:08:33,780
tak, że kiedy pojawi znowu, znowu po prostu zmniejszyć naszą wielkość w dół do 1.

122
00:08:33,780 --> 00:08:39,440
Nie ma potrzeby, aby faktycznie przejść i zastąpić wszystko.

123
00:08:39,440 --> 00:08:41,710
Trochę funky.

124
00:08:41,710 --> 00:08:46,520
Okazuje się, że zazwyczaj po prostu zostawić wszystko w spokoju, bo to mniej pracy dla nas zrobić.

125
00:08:46,520 --> 00:08:50,060
Jeśli nie mamy wrócić i zastąpić coś, to dlaczego to robisz?

126
00:08:50,060 --> 00:08:54,150
Kiedy więc pojawiają się dwa razy w stosie, to wszystko robi, to zmniejszamy rozmiar A kilka razy.

127
00:08:54,150 --> 00:08:59,120
I znowu, to tylko dlatego, że nie jesteśmy kopiowania rzeczy do naszego komina.

128
00:08:59,120 --> 00:09:01,320
Tak? Śmiało.

129
00:09:01,320 --> 00:09:04,460
[Student, niezrozumiały] >> I co wtedy się dzieje po naciśnięciu coś znowu?

130
00:09:04,460 --> 00:09:08,570
Po naciśnięciu coś znowu, gdzie to idzie?

131
00:09:08,570 --> 00:09:12,390
Dokąd ona, Basil? >> Into ciągów [1]? >> Racja.

132
00:09:12,390 --> 00:09:14,530
Dlaczego nie pójść na ciągi [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Bo zapomniałem, że było coś w ciągach [1] i [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Dokładnie. Nasz stos zasadniczo, "zapomniał", że był trzymając się niczego

135
00:09:24,040 --> 00:09:29,480
w ciągach [1] lub łańcuchy [2], więc kiedy push "woot",

136
00:09:29,480 --> 00:09:36,670
to po prostu, że stawia na element na strunach. [1]

137
00:09:36,670 --> 00:09:41,590
Czy są jakieś pytania na temat jak to działa, na poziomie podstawowym?

138
00:09:41,590 --> 00:09:45,160
[Sam], więc nie jest w żaden sposób dynamiczny, w odniesieniu do ilości

139
00:09:45,160 --> 00:09:47,620
lub w odniesieniu do wielkości stosu?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Dokładnie. To jest - w tym, że nie było to dynamicznie growning stosu.

141
00:09:56,750 --> 00:10:02,850
Jest to stosu, które może pomieścić co najwyżej cztery char * s, co najwyżej czterech rzeczy.

142
00:10:02,850 --> 00:10:07,580
Jeśli mielibyśmy spróbować nacisnąć jeden piąta rzecz, co myślisz powinno się zdarzyć?

143
00:10:07,580 --> 00:10:11,870
[Studenci, niezrozumiały]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Dokładnie. Istnieje wiele rzeczy, które mogą się wydarzyć.

145
00:10:14,600 --> 00:10:19,330
Mogłaby ona seg winy, w zależności od tego, co było -

146
00:10:19,330 --> 00:10:22,530
jak dokładnie zostaliśmy realizacji back-end.

147
00:10:22,530 --> 00:10:31,740
To może zastąpić. Może mieć to przepełnienie bufora, które mówiliśmy w klasie.

148
00:10:31,740 --> 00:10:35,240
Jaki byłby najbardziej oczywistą rzeczą, że może być zastąpiony

149
00:10:35,240 --> 00:10:42,370
jeśli próbowała wcisnąć dodatkowe rzeczy na naszej stos?

150
00:10:42,370 --> 00:10:44,550
Więc mowa przepełnienie bufora.

151
00:10:44,550 --> 00:10:47,870
Co może być rzeczą, która się nadpisać lub nadepnął na

152
00:10:47,870 --> 00:10:52,320
jeśli przepełniła przypadkowo, próbując wcisnąć dodatkowe rzeczy?

153
00:10:52,320 --> 00:10:54,730
[Daniel, niezrozumiały] >> Możliwe.

154
00:10:54,730 --> 00:10:58,440
Ale na początku, co może się zdarzyć? Co jeśli próbowała wcisnąć jeden czwarta rzecz?

155
00:10:58,440 --> 00:11:06,220
To może zastąpić rozmiar, przynajmniej z tego wykresu pamięci, które mamy.

156
00:11:06,220 --> 00:11:10,880
>> W opisie zestawu problemów, co jest, co mamy zamiar być wdrożenie dziś

157
00:11:10,880 --> 00:11:16,030
co chcę zrobić, to return false.

158
00:11:16,030 --> 00:11:20,030
Nasza metoda Push będzie zwracać wartość logiczną,

159
00:11:20,030 --> 00:11:22,920
oraz, że wartość logiczna będzie prawdziwa jeśli uda Push

160
00:11:22,920 --> 00:11:29,730
i false jeśli nie możemy wcisnąć nic więcej, ponieważ stos jest pełny.

161
00:11:29,730 --> 00:11:33,620
Przejdźmy przez trochę tego kodu teraz.

162
00:11:33,620 --> 00:11:36,400
Tu jest nasza funkcja push.

163
00:11:36,400 --> 00:11:40,380
Nasza funkcja nacisk na stosie ma zamiar wziąć w ciągu umieścić na stosie.

164
00:11:40,380 --> 00:11:45,820
To się zwróci true, jeśli ciąg powodzeniem pchnął

165
00:11:45,820 --> 00:11:51,820
na inny stos i false.

166
00:11:51,820 --> 00:11:59,740
Wszelkie sugestie na temat tego, co może być dobrą rzeczą, aby zrobić tutaj?

167
00:11:59,740 --> 00:12:20,630
[Sam] Jeśli wielkość równa zdolności następnie powrócić fałsz?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Niezła robota.

169
00:12:23,320 --> 00:12:26,310
Jeśli rozmiar jest pojemność, mamy zamiar wrócić false.

170
00:12:26,310 --> 00:12:29,270
Nie możemy umieścić coś więcej w naszej stosie.

171
00:12:29,270 --> 00:12:36,900
W przeciwnym razie, chcemy umieścić coś na górze stosu.

172
00:12:36,900 --> 00:12:41,670
Co to jest "top stosu", początkowo?

173
00:12:41,670 --> 00:12:43,650
[Daniel] rozmiar 0? Rozmiar 0 >>.

174
00:12:43,650 --> 00:12:49,990
Jaki jest szczyt stosu po jednej rzeczy na stosie? Missy, wiesz?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. Rozmiar >> jest, dokładnie. Ciągle dodanie do wielkości,

176
00:12:52,720 --> 00:13:01,690
i za każdym razem jesteś wprowadzenie nowego elementu w wielkości indeksu w tablicy.

177
00:13:01,690 --> 00:13:05,470
Możemy to zrobić z tego rodzaju jednolinijkowych, jeśli to ma sens.

178
00:13:05,470 --> 00:13:11,910
Więc mamy naszą tablicę ciągów, jedziemy do niego dostęp w indeksie wielkości,

179
00:13:11,910 --> 00:13:14,780
i jesteśmy po prostu będzie przechowywać nasz char * w tam.

180
00:13:14,780 --> 00:13:19,340
Zauważ, jak nie ma kopiowanie ciąg tutaj dzieje,

181
00:13:19,340 --> 00:13:29,680
no dynamiczna alokacja pamięci?

182
00:13:29,680 --> 00:13:34,440
A następnie Missy wychowany, co teraz mamy zrobić,

183
00:13:34,440 --> 00:13:40,570
bo mamy przechowywać ciąg w odpowiednim miejscu w tablicy,

184
00:13:40,570 --> 00:13:49,230
i powiedziała, że ​​musimy zwiększyć rozmiar o jeden tak, że jesteśmy gotowi na kolejny push.

185
00:13:49,230 --> 00:13:53,950
Więc możemy zrobić z s.size + +.

186
00:13:53,950 --> 00:13:59,330
W tym momencie, mamy wepchnięty naszej tablicy. Jaka jest ostatnia rzecz, którą musimy zrobić?

187
00:13:59,330 --> 00:14:10,110
[Student] Zwraca true. Powrót >> prawda.

188
00:14:10,110 --> 00:14:14,690
Więc to jest bardzo proste, bardzo prosty kod. Nie za dużo.

189
00:14:14,690 --> 00:14:17,070
Po owinięte wokół twojej głowie jak stos działa

190
00:14:17,070 --> 00:14:21,910
jest to bardzo proste do wykonania.

191
00:14:21,910 --> 00:14:26,390
>> Teraz, następna część to ciąg popping off stosu.

192
00:14:26,390 --> 00:14:29,410
Mam zamiar dać wam trochę czasu na pracę na tym trochę mało.

193
00:14:29,410 --> 00:14:34,320
To prawie zasadniczo odwrotnością tego, co zrobiliśmy tutaj, w push.

194
00:14:34,320 --> 00:14:38,510
Co zrobiłem jest faktycznie - oops.

195
00:14:38,510 --> 00:14:48,160
Mam uruchomieniu systemu jakieś urządzenie tutaj, a także w urządzenia,

196
00:14:48,160 --> 00:14:53,600
Mam podciągnięte problemu ustawić 5 specyfikacji.

197
00:14:53,600 --> 00:15:02,560
Jeśli przybliżyć tutaj widzimy, że jestem w cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Czy wy pobrać ten kod, który jest umieszczony tutaj section6.zip?

199
00:15:08,590 --> 00:15:15,030
Dobrze. Jeśli tego nie zrobiłeś, zrób to teraz, naprawdę szybko.

200
00:15:15,030 --> 00:15:22,130
Zrobię to w moim oknie terminala.

201
00:15:22,130 --> 00:15:25,090
I rzeczywiście zrobił to tutaj. Tak.

202
00:15:25,090 --> 00:15:34,730
Tak, Sam? >> Mam pytanie, dlaczego nie powiedziałeś s.string 's wsporniki o rozmiarze = str?

203
00:15:34,730 --> 00:15:42,910
Co to jest str? Jest zdefiniowana gdzieś przed, lub - o, w char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Tak, dokładnie. To był argument. >> Oh, w porządku. Przepraszam.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Jesteśmy określający ciąg do pchania w.

206
00:15:49,470 --> 00:15:55,220
Inne pytanie, które mogą wymyślić, że tak naprawdę nie było tu mówić o

207
00:15:55,220 --> 00:15:58,810
braliśmy za pewnik, że mieliśmy tę zmienną o nazwie s

208
00:15:58,810 --> 00:16:02,710
które było w zasięgu i dostępnej dla nas.

209
00:16:02,710 --> 00:16:06,960
Wzięliśmy za pewnik, że to było s struct stos.

210
00:16:06,960 --> 00:16:08,930
Więc patrząc na to pchającej kodu,

211
00:16:08,930 --> 00:16:13,450
widać, że robimy rzeczy z tego łańcucha, który dostał przekazanego

212
00:16:13,450 --> 00:16:19,210
ale potem nagle, mamy dostęp s.size, jak, skąd s pochodzi?

213
00:16:19,210 --> 00:16:23,020
W kodzie, że będziemy patrzeć w archiwum sekcji

214
00:16:23,020 --> 00:16:27,100
i rzeczy, które będziesz robił w swoim problemie ustawia,

215
00:16:27,100 --> 00:16:32,440
zrobiliśmy nasz stack struct zmienną globalną

216
00:16:32,440 --> 00:16:36,380
tak, że możemy mieć do niego dostęp w wszystkich naszych funkcji różnych

217
00:16:36,380 --> 00:16:40,630
bez konieczności ręcznego przekazać go i przekazać je przez referencję,

218
00:16:40,630 --> 00:16:44,870
nie wszystkie tego rodzaju rzeczy do niego.

219
00:16:44,870 --> 00:16:52,280
Jesteśmy po prostu oszukuje trochę, jeśli chcesz, aby rzeczy ładniejsze.

220
00:16:52,280 --> 00:16:57,430
I to jest coś, co robimy tutaj, ponieważ jest to dla zabawy, to jest łatwiejsze.

221
00:16:57,430 --> 00:17:02,800
Często zobaczysz ludzie robią to, jeśli ma jedną dużą strukturę danych

222
00:17:02,800 --> 00:17:07,750
, która jest eksploatowana na w ich programie.

223
00:17:07,750 --> 00:17:09,560
>> Wróćmy nad do urządzenia.

224
00:17:09,560 --> 00:17:15,240
Czy każdy z powodzeniem uzyskać section6.zip?

225
00:17:15,240 --> 00:17:20,440
Wszyscy rozpakuj go za pomocą section6.zip rozpakować?

226
00:17:20,440 --> 00:17:27,200
Jeśli pójdziesz do sekcji 6 katalogu -

227
00:17:27,200 --> 00:17:29,220
aah, w każdym miejscu -

228
00:17:29,220 --> 00:17:32,840
i listy co tu widzisz, że masz trzy różne pliki. c.

229
00:17:32,840 --> 00:17:38,350
Masz kolejki, SLL, która jest pojedynczo-linked lista oraz stos.

230
00:17:38,350 --> 00:17:44,600
Po otwarciu stack.c,

231
00:17:44,600 --> 00:17:47,330
widać, że mamy ten struct zdefiniowany dla nas,

232
00:17:47,330 --> 00:17:51,330
Dokładna struktura, że ​​właśnie mówi się w slajdach.

233
00:17:51,330 --> 00:17:56,340
Mamy naszą zmienną globalną na stosie,

234
00:17:56,340 --> 00:18:00,110
mamy naszą funkcję push

235
00:18:00,110 --> 00:18:04,230
a my mamy naszą pop funkcję.

236
00:18:04,230 --> 00:18:08,320
Powiem kod dla odepchnąć się na slajdzie tutaj

237
00:18:08,320 --> 00:18:10,660
ale to, co chcę wam zrobić, to najlepiej, jak potrafisz,

238
00:18:10,660 --> 00:18:13,790
idź i wdrożenie pop funkcję.

239
00:18:13,790 --> 00:18:18,480
Po realizacji, można skompilować z make stos,

240
00:18:18,480 --> 00:18:22,540
a następnie uruchom otrzymany plik wykonywalny stosu,

241
00:18:22,540 --> 00:18:28,390
i że będzie działał cały ten kod testu na dół to w menu głównym.

242
00:18:28,390 --> 00:18:31,060
I główny zajmuje faktycznie dokonywania push i pop połączenia

243
00:18:31,060 --> 00:18:33,220
i upewnić się, że wszystko idzie po całej prawej stronie.

244
00:18:33,220 --> 00:18:36,820
Również inicjuje rozmiar stosu tutaj

245
00:18:36,820 --> 00:18:39,780
więc nie musisz się martwić o inicjowanie tego.

246
00:18:39,780 --> 00:18:42,310
Można założyć, że został poprawnie zainicjowany

247
00:18:42,310 --> 00:18:48,000
przez czas, że masz do niego dostęp w pop funkcji.

248
00:18:48,000 --> 00:18:53,530
Czy to ma sens?

249
00:18:53,530 --> 00:19:00,100
Tak więc zaczynamy. Jest Push kod.

250
00:19:00,100 --> 00:19:13,210
Dam wam 5 lub 10 minut.

251
00:19:13,210 --> 00:19:15,690
A jeśli masz jakiekolwiek pytania w międzyczasie, gdy jesteś kodowania,

252
00:19:15,690 --> 00:19:17,710
poproś go głośno.

253
00:19:17,710 --> 00:19:23,080
Więc jeśli masz do kłucia, po prostu zapytaj.

254
00:19:23,080 --> 00:19:26,030
Daj mi znać, niech wszyscy wiedzą.

255
00:19:26,030 --> 00:19:28,160
Praca z sąsiadem też.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Właśnie wdrażanie pop teraz? >> Tylko pop.

257
00:19:30,360 --> 00:19:34,200
Choć można skopiować realizację naciśnięciem jeśli chcesz

258
00:19:34,200 --> 00:19:37,780
tak, że próby będą działać.

259
00:19:37,780 --> 00:19:41,940
Ponieważ trudno jest przetestować rzeczy z dostaniem się do -

260
00:19:41,940 --> 00:19:49,030
lub, że trudno przetestować rzeczy wychodziły z komina, jeśli nie ma nic w stosie, aby rozpocząć.

261
00:19:49,030 --> 00:19:55,250
>> Co to ma być pop powrocie? Element z wierzchu stosu.

262
00:19:55,250 --> 00:20:01,260
To ma się uzyskać element z wierzchu stosu

263
00:20:01,260 --> 00:20:05,780
i zmniejszyć wielkość stosu

264
00:20:05,780 --> 00:20:07,810
a teraz straciliśmy element na szczycie.

265
00:20:07,810 --> 00:20:11,420
A potem wrócisz element na górze.

266
00:20:11,420 --> 00:20:20,080
[Student, niezrozumiały]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Więc co się stanie, jeśli to zrobić? [Student, niezrozumiały]

268
00:20:28,810 --> 00:20:34,000
Co kończy się dzieje, to prawdopodobnie jesteś dostępu albo

269
00:20:34,000 --> 00:20:37,350
Element, który nie został zainicjowany jeszcze, więc Twoja kalkulacja

270
00:20:37,350 --> 00:20:39,990
z których ostatni element jest wyłączony.

271
00:20:39,990 --> 00:20:46,260
Więc tutaj, jeśli zauważysz, w push, mamy dostęp do ciągów w s.size elementu

272
00:20:46,260 --> 00:20:48,560
bo to nowy indeks.

273
00:20:48,560 --> 00:20:51,460
Jest to nowy szczyt stosu.

274
00:20:51,460 --> 00:21:01,100
Natomiast w pop, s.size będzie obok miejsca,

275
00:21:01,100 --> 00:21:05,210
przestrzeń, która znajduje się na szczycie wszystkich elementów w swoim stosie.

276
00:21:05,210 --> 00:21:10,050
Więc najwyżej położony element nie jest na s.size,

277
00:21:10,050 --> 00:21:14,930
ale raczej jest pod nim.

278
00:21:14,930 --> 00:21:19,640
>> Innych rzeczy do zrobienia, kiedy - w pop,

279
00:21:19,640 --> 00:21:22,030
jest to trzeba zmniejszyć rozmiar.

280
00:21:22,030 --> 00:21:28,750
Jeśli pamiętasz z powrotem do naszego małego diagramu tu,

281
00:21:28,750 --> 00:21:30,980
naprawdę, jedyne, co widzieliśmy dzieje kiedy zadzwoniliśmy pop

282
00:21:30,980 --> 00:21:36,150
Rozmiar był że spadła, pierwszy 2, a następnie do 1.

283
00:21:36,150 --> 00:21:42,620
Następnie, gdy pchnął nowy element o, to iść w odpowiednim miejscu.

284
00:21:42,620 --> 00:21:49,610
[Basil] Jeśli s.size jest 2, to nie byłoby to do elementu 2,

285
00:21:49,610 --> 00:21:54,400
a potem chcesz pop tego elementu off?

286
00:21:54,400 --> 00:21:59,510
Więc jeśli poszliśmy do - >> Więc spójrzmy na to jeszcze raz.

287
00:21:59,510 --> 00:22:07,730
Jeśli jest to nasz stack w tym momencie

288
00:22:07,730 --> 00:22:12,130
i wzywamy pop,

289
00:22:12,130 --> 00:22:16,150
w której indeks jest najwyżej położony element?

290
00:22:16,150 --> 00:22:19,300
[Basil] W 2, ale to będzie pop 3. >> Racja.

291
00:22:19,300 --> 00:22:24,220
Więc to, gdzie nasz rozmiar jest 3, ale chcemy, aby wyjąć elementu o indeksie 2.

292
00:22:24,220 --> 00:22:29,900
To takie typowe dla rodzaju, przez jednego, że trzeba się z zerowym indeksowania tablic.

293
00:22:29,900 --> 00:22:36,430
Więc chcę pop trzeci element, ale trzeci element nie jest w indeksie 3.

294
00:22:36,430 --> 00:22:39,430
A powodem nie mamy zrobić tego minus 1, gdy jesteśmy popychanie

295
00:22:39,430 --> 00:22:44,120
jest, ponieważ teraz można zauważyć, że na samej górze element,

296
00:22:44,120 --> 00:22:47,600
gdybyśmy wcisnąć coś innego na stosie w tym punkcie,

297
00:22:47,600 --> 00:22:50,360
chcielibyśmy przesunąć o indeksie 3.

298
00:22:50,360 --> 00:23:03,550
A tak się składa, że ​​rozmiar i wskaźniki kolejce kiedy pchania.

299
00:23:03,550 --> 00:23:06,960
>> Kto ma działającą implementację stosu?

300
00:23:06,960 --> 00:23:09,690
Masz pracy stos jeden. Czy masz pop pracuje jeszcze?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Tak. Myślę, że tak.

302
00:23:11,890 --> 00:23:14,610
Program >> ucieka i nie seg Błąd, to drukowanie?

303
00:23:14,610 --> 00:23:17,520
Czy to wydrukować "sukces", kiedy go uruchomić?

304
00:23:17,520 --> 00:23:22,630
Tak. Producent stos, uruchom go, jeśli wypisuje "sukces" i nie wykracza boom

305
00:23:22,630 --> 00:23:26,000
wtedy wszystko jest dobrze.

306
00:23:26,000 --> 00:23:34,070
Dobrze. Chodźmy do urządzenia bardzo szybko,

307
00:23:34,070 --> 00:23:46,100
i będziemy przechodzić przez to.

308
00:23:46,100 --> 00:23:51,110
Jeśli spojrzymy na to, co tu się dzieje z popem,

309
00:23:51,110 --> 00:23:55,220
Daniel, co było pierwszą rzeczą, którą zrobiłem?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Jeśli s.size jest większe niż 0,.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Dobra. I dlaczego to robisz?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Aby upewnić się, że jest coś w środku stosu.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Racja. Chcesz przetestować, aby upewnić się, że s.size jest większa niż 0;

314
00:24:10,950 --> 00:24:13,280
inaczej, co chcesz, aby się stało?

315
00:24:13,280 --> 00:24:16,630
[Daniel] zwróć NULL? Zerowy Powrót >>, dokładnie.

316
00:24:16,630 --> 00:24:20,740
Tak więc, jeśli s.size jest większe niż 0,. Więc co zrobimy?

317
00:24:20,740 --> 00:24:25,890
Co mamy zrobić, gdy stos nie jest pusty?

318
00:24:25,890 --> 00:24:31,210
[Stella] You zmniejszyć rozmiar? >> You zmniejszyć rozmiar, okay.

319
00:24:31,210 --> 00:24:34,440
Więc jak to zrobić? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. I co wtedy zrobiłeś?

321
00:24:37,030 --> 00:24:44,140
[Stella] A potem powiedziałem powrót s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
W przeciwnym razie zwróci null. Tak, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Dlaczego to nie trzeba być s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? >> Tak. >> Jasne.

326
00:24:58,430 --> 00:25:00,980
[Sam] myślałem, bo bierzesz 1 out,

327
00:25:00,980 --> 00:25:04,290
następnie masz zamiar się z powrotu nie jeden, że prosiła.

328
00:25:04,290 --> 00:25:09,400
[Hardison] I to było właśnie to, że rozmawiamy o tej całej kwestii 0 indeksów.

329
00:25:09,400 --> 00:25:11,380
Jeśli więc Powiększ tutaj.

330
00:25:11,380 --> 00:25:15,650
Jeśli spojrzeć na tego faceta tutaj, można zobaczyć, że kiedy pojawiają,

331
00:25:15,650 --> 00:25:19,340
jesteśmy popping element o indeksie 2.

332
00:25:19,340 --> 00:25:25,200
>> Więc zmniejszyć nasze rozmiaru, potem nasz rozmiar pasuje do naszego indeksu.

333
00:25:25,200 --> 00:25:39,650
Jeśli nie będziemy zmniejszać rozmiar, potem musimy zrobić rozmiar -1 a następnie ubytek.

334
00:25:39,650 --> 00:25:45,270
Great. Wszystko dobrze?

335
00:25:45,270 --> 00:25:47,530
Wszelkie pytania w tej sprawie?

336
00:25:47,530 --> 00:25:54,050
Istnieje wiele różnych sposobów, w tym, jak i zapisu.

337
00:25:54,050 --> 00:26:03,290
W rzeczywistości, możemy zrobić coś jeszcze - możemy zrobić w jednej linijce.

338
00:26:03,290 --> 00:26:05,770
Możemy zrobić jednego wiersza powrót.

339
00:26:05,770 --> 00:26:12,980
Tak naprawdę możemy zmniejszyć przed wrócimy by to robić.

340
00:26:12,980 --> 00:26:18,320
Więc wprowadzenie - przed s.size.

341
00:26:18,320 --> 00:26:22,060
To sprawia, że ​​linia bardzo gęsta.

342
00:26:22,060 --> 00:26:30,940
W przypadku, gdy różnica między - s. Wielkości i s.size--

343
00:26:30,940 --> 00:26:40,130
jest to, że postfix - nazywają to postfix powodu - jest po s.size--

344
00:26:40,130 --> 00:26:47,430
Oznacza to, że jest s.size oceniane w celu znalezienia indeksu

345
00:26:47,430 --> 00:26:50,410
Obecnie, jak gdy linia jest wykonywane,

346
00:26:50,410 --> 00:26:54,290
a to - dzieje się po linii zostanie wykonany.

347
00:26:54,290 --> 00:27:00,340
Po elementem na s.size indeksu jest dostępny.

348
00:27:00,340 --> 00:27:07,260
I to nie jest to, co chcemy, bo chcemy ubytek nastąpi pierwsze.

349
00:27:07,260 --> 00:27:10,990
Othewise, jedziemy do dostępu do tablicy, skutecznie, poza granicami.

350
00:27:10,990 --> 00:27:16,850
Zamierzamy być dostęp element nad tym, że tak naprawdę chcesz uzyskać dostęp.

351
00:27:16,850 --> 00:27:23,840
Tak, Sam? >> Czy to szybciej lub użyć mniej pamięci RAM, aby w jednej linii, czy nie?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Szczerze mówiąc, to naprawdę zależy.

353
00:27:29,620 --> 00:27:34,220
[Sam, niezrozumiały] >> Tak, to zależy. Można robić sztuczki kompilatora

354
00:27:34,220 --> 00:27:41,580
uzyskać kompilatora do uznania, że ​​zazwyczaj, wyobrażam sobie.

355
00:27:41,580 --> 00:27:44,840
>> Więc już wspomniałem trochę o tych rzeczy optymalizacji kompilatora

356
00:27:44,840 --> 00:27:47,400
że można to zrobić w gromadzeniu,

357
00:27:47,400 --> 00:27:50,580
i to jest jedna z tych rzeczy, które kompilator może być w stanie dowiedzieć się,

358
00:27:50,580 --> 00:27:54,710
jak Hej, może uda mi się to wszystko zrobić w jednej operacji,

359
00:27:54,710 --> 00:27:59,420
w przeciwieństwie do ładowania różnych rozmiarach w pamięci RAM,

360
00:27:59,420 --> 00:28:03,770
zmniejszanie go, zapisując go z powrotem, a następnie ładowanie go ponownie

361
00:28:03,770 --> 00:28:08,000
przetwarzanie resztę tego działania.

362
00:28:08,000 --> 00:28:10,710
Ale zazwyczaj, nie, to nie jest coś takiego

363
00:28:10,710 --> 00:28:20,770
że zamierza uczynić swój program znacznie szybciej.

364
00:28:20,770 --> 00:28:26,000
Jeszcze jakieś pytania na stosach?

365
00:28:26,000 --> 00:28:31,360
>> Więc popychanie i popping. Jeśli chcecie wypróbować edycję hakerów,

366
00:28:31,360 --> 00:28:33,660
co zrobiliśmy w wydaniu hakerów faktycznie odszedł

367
00:28:33,660 --> 00:28:37,670
i uczynił ten stos rośnie dynamicznie.

368
00:28:37,670 --> 00:28:43,190
Wyzwaniem jest tu głównie w pchającej funkcji

369
00:28:43,190 --> 00:28:48,820
dowiedzieć się, jak zrobić, że tablica rosnąć

370
00:28:48,820 --> 00:28:52,450
jak przeć coraz więcej elementów na do stosu.

371
00:28:52,450 --> 00:28:56,000
To faktycznie nie za dużo dodatkowego kodu.

372
00:28:56,000 --> 00:29:00,080
Wystarczy wywołanie - trzeba pamiętać, aby wywołania malloc tam prawidłowo,

373
00:29:00,080 --> 00:29:03,310
a następnie dowiedzieć się, kiedy masz zamiar zadzwonić realloc.

374
00:29:03,310 --> 00:29:06,090
To zabawa, wyzwanie, jeśli jesteś zainteresowany.

375
00:29:06,090 --> 00:29:11,550
>> Ale na razie, przejdźmy dalej, i porozmawiajmy o kolejkach.

376
00:29:11,550 --> 00:29:15,680
Przewiń tutaj.

377
00:29:15,680 --> 00:29:19,340
Kolejka jest blisko rodzeństwem stosie.

378
00:29:19,340 --> 00:29:25,380
Więc w stosie rzeczy, które zostały wprowadzone w ostatnim

379
00:29:25,380 --> 00:29:28,810
Były to pierwsze rzeczy, aby następnie zostać przywrócony.

380
00:29:28,810 --> 00:29:33,600
Mamy ten ostatni do, pierwszy z lub LIFO, zamawiania.

381
00:29:33,600 --> 00:29:38,390
Natomiast w kolejce, jak można oczekiwać od kiedy stoisz w kolejce,

382
00:29:38,390 --> 00:29:41,980
pierwszym, który się w kolejce, to pierwszą rzeczą, aby dostać się do kolejki,

383
00:29:41,980 --> 00:29:47,630
Jest to pierwsza rzecz, która zostanie pobrana z kolejki.

384
00:29:47,630 --> 00:29:51,490
Kolejki są również często stosowane, gdy mamy do czynienia z wykresami,

385
00:29:51,490 --> 00:29:55,560
jak rozmawialiśmy krótko z stosów

386
00:29:55,560 --> 00:30:00,260
a kolejki są również przydatne dla kilka innych rzeczy.

387
00:30:00,260 --> 00:30:06,180
Jednym jest rzeczą, że często próbuje się utrzymać na przykład

388
00:30:06,180 --> 00:30:12,310
sortowana lista elementów.

389
00:30:12,310 --> 00:30:17,650
I można to zrobić z tablicy. Można zachować posortowaną listę rzeczy w tablicy,

390
00:30:17,650 --> 00:30:20,650
ale gdzie, który dostaje trudne jest wtedy zawsze musisz znaleźć

391
00:30:20,650 --> 00:30:26,160
odpowiednie miejsce, aby włożyć kolejną rzecz.

392
00:30:26,160 --> 00:30:28,250
Więc jeśli masz tablicę liczb, 1 do 10,

393
00:30:28,250 --> 00:30:31,630
i chcesz rozszerzyć, że do wszystkich liczb od 1 do 100,

394
00:30:31,630 --> 00:30:33,670
i dostajesz te numery w kolejności losowej i próbuje utrzymać wszystko

395
00:30:33,670 --> 00:30:40,650
posortowane jak przejść, możesz skończyć konieczności zrobić wiele zmienia.

396
00:30:40,650 --> 00:30:43,910
W przypadku niektórych rodzajów kolejek i pewnych typów podstawowych struktur danych,

397
00:30:43,910 --> 00:30:46,670
rzeczywiście można przechowywać dość proste.

398
00:30:46,670 --> 00:30:50,640
Nie masz jeszcze coś dodać, a następnie przetasować całą rzecz za każdym razem.

399
00:30:50,640 --> 00:30:56,770
Ponadto nie trzeba zrobić wiele przesunięcie elementów wewnętrznych wokół.

400
00:30:56,770 --> 00:31:02,990
Kiedy patrzymy na kolejki, widać, że - również w queue.c w kodzie sekcji -

401
00:31:02,990 --> 00:31:10,950
struct że mamy wam jest naprawdę podobna do struktury, że dała ci na stosie.

402
00:31:10,950 --> 00:31:13,770
>> Jest jeden wyjątek od tej, i że jeden wyjątek

403
00:31:13,770 --> 00:31:21,700
jest to, że mamy tę dodatkową liczbę całkowitą o nazwie Głowa,

404
00:31:21,700 --> 00:31:28,120
i głowa o to do śledzenia na czele kolejki,

405
00:31:28,120 --> 00:31:32,160
lub pierwszy element w kolejce.

406
00:31:32,160 --> 00:31:37,470
Z komina, byliśmy w stanie śledzić elementu że byliśmy do pobierania,

407
00:31:37,470 --> 00:31:40,800
lub górę stosu, przy użyciu tylko wielkość,

408
00:31:40,800 --> 00:31:44,220
podczas gdy w kolejce, mamy do czynienia z przeciwległych końcach.

409
00:31:44,220 --> 00:31:49,000
Próbujemy tack rzeczy na końcu, ale potem wrócić rzeczy z przodu.

410
00:31:49,000 --> 00:31:54,640
Tak skutecznie, z głową, mamy wskaźnik początku kolejki

411
00:31:54,640 --> 00:31:58,920
Rozmiar i daje indeks koniec kolejki

412
00:31:58,920 --> 00:32:03,730
tak, że możemy odzyskać rzeczy z głowy i dodać rzeczy do ogona.

413
00:32:03,730 --> 00:32:06,890
Podczas gdy w stosie, to były zawsze tylko do czynienia z wierzchu stosu.

414
00:32:06,890 --> 00:32:08,900
Nigdy nie było dostępu do stosem.

415
00:32:08,900 --> 00:32:12,220
Mamy tylko dodane rzeczy na górę i wziął się rzeczy z góry

416
00:32:12,220 --> 00:32:17,470
więc nie trzeba, że ​​dodatkowe pole wewnątrz naszej struktury.

417
00:32:17,470 --> 00:32:20,590
Czy to generalnie ma sens?

418
00:32:20,590 --> 00:32:27,670
Dobrze. Tak, Charlotte? [Charlotte, niezrozumiały]

419
00:32:27,670 --> 00:32:32,660
[Hardison] To wielkie pytanie, i to taki, który pojawił się na wykładzie.

420
00:32:32,660 --> 00:32:36,290
Może idąc przez kilka przykładów zilustruje, dlaczego

421
00:32:36,290 --> 00:32:41,400
nie chcemy użyć strings [0] jako kierownika kolejki.

422
00:32:41,400 --> 00:32:46,770
>> Więc wyobraź sobie, że mamy kolejkę, będziemy nazywać to kolejka.

423
00:32:46,770 --> 00:32:49,210
Na początku, kiedy to właśnie instancja,

424
00:32:49,210 --> 00:32:53,330
kiedy właśnie ogłosiła, że ​​nie byliśmy zainicjowany niczego.

425
00:32:53,330 --> 00:32:56,790
To wszystko bzdury. Więc oczywiście chcemy się upewnić, że mamy zainicjować

426
00:32:56,790 --> 00:33:00,950
zarówno wielkość i pola głowa do 0, coś uzasadnione.

427
00:33:00,950 --> 00:33:05,770
Możemy także pójść dalej i wartość null z elementów w naszej kolejce.

428
00:33:05,770 --> 00:33:09,930
I aby ten schemat pasuje zauważyć, że teraz nasza kolejka może pomieścić tylko trzy elementy;

429
00:33:09,930 --> 00:33:13,150
natomiast nasz stack mogły pomieścić cztery, nasza kolejka może pomieścić tylko trzy.

430
00:33:13,150 --> 00:33:18,680
A to tylko w celu dopasowania diagramu.

431
00:33:18,680 --> 00:33:26,150
Pierwszą rzeczą, która dzieje się tutaj to my enqueue ciąg "hi".

432
00:33:26,150 --> 00:33:30,380
I tak jak zrobiliśmy to z komina, nic strasznie tu inne,

433
00:33:30,380 --> 00:33:39,230
rzucamy ciąg na co ciągów [0] i zwiększamy nasz rozmiar o 1.

434
00:33:39,230 --> 00:33:42,720
Mamy enqueue "bye", to dostaje wprowadzone.

435
00:33:42,720 --> 00:33:45,870
Tak to wygląda jak stos dla większości.

436
00:33:45,870 --> 00:33:53,230
Zaczęliśmy tu nowy element, nowy element, rozmiar utrzymuje rośnie.

437
00:33:53,230 --> 00:33:56,330
Co się dzieje w tym momencie, kiedy chcemy coś z kolejki?

438
00:33:56,330 --> 00:34:01,280
Kiedy chcemy z kolejki, który jest elementem, który chcemy z kolejki?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Dokładnie tak, Basil.

440
00:34:04,110 --> 00:34:10,960
Chcemy pozbyć się pierwszego ciągu, tym razem, "Hi".

441
00:34:10,960 --> 00:34:13,170
Więc co było Inna sprawa, że ​​się zmieniło?

442
00:34:13,170 --> 00:34:17,010
Zauważ, kiedy wpadliśmy coś z stosu, po prostu zmienił rozmiar,

443
00:34:17,010 --> 00:34:22,080
ale tutaj mamy kilka rzeczy, które zmieniają się.

444
00:34:22,080 --> 00:34:27,440
Nie tylko zmienić rozmiar, ale zmiany głowy.

445
00:34:27,440 --> 00:34:31,020
To jest powrót do punktu Charlotte wcześniej:

446
00:34:31,020 --> 00:34:38,699
dlaczego mamy tę głowę, jak również?

447
00:34:38,699 --> 00:34:42,110
Czy jest sens teraz, Charlotte? >> Jakby.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Rodzaj? Więc co się stało, kiedy rozkolejkowywana?

449
00:34:47,500 --> 00:34:54,340
Co głowa to zrobić teraz jest interesujące?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, ponieważ zmieniły się - w porządku. Rozumiem.

451
00:34:56,449 --> 00:35:02,090
Ponieważ głowica - gdzie głowa wskazuje na zmiany w zakresie lokalizacji.

452
00:35:02,090 --> 00:35:07,200
To już nie zawsze zero jeden indeks. >> Tak, dokładnie.

453
00:35:07,200 --> 00:35:17,660
Co się stało, gdyby dequeueing wysoką elementu

454
00:35:17,660 --> 00:35:20,590
zostało zrobione i nie mamy tego pola głowy

455
00:35:20,590 --> 00:35:26,880
bo byliśmy zawsze nazywając ten ciąg na 0 indeksu szef naszej kolejki,

456
00:35:26,880 --> 00:35:30,170
wtedy musielibyśmy przenieść resztę kolejki w dół.

457
00:35:30,170 --> 00:35:36,010
Musielibyśmy przesunąć "bye" od strun [1] do strun [0].

458
00:35:36,010 --> 00:35:38,760
I smyczki [2] aż do struny. [1]

459
00:35:38,760 --> 00:35:43,050
I chcemy to zrobić dla całej listy elementów,

460
00:35:43,050 --> 00:35:45,110
cały szereg elementów.

461
00:35:45,110 --> 00:35:50,490
A gdy robimy to z tablicy, że robi się naprawdę kosztowne.

462
00:35:50,490 --> 00:35:53,340
Więc, nie wielkiego. Mamy tylko trzy elementy naszej tablicy.

463
00:35:53,340 --> 00:35:57,230
Ale jeśli mieliśmy kolejkę tysiąca elementów lub milion elementów,

464
00:35:57,230 --> 00:36:00,060
a potem nagle, zaczniemy kilka Dequeue wzywa wszystkich w pętli,

465
00:36:00,060 --> 00:36:03,930
rzeczy są naprawdę będzie spowalniać, ponieważ zmienia wszystko w dół stale.

466
00:36:03,930 --> 00:36:07,320
Wiesz, przesunięcie o 1, przesunięcie o 1, przesunięcie o 1, przesunięcie o 1.

467
00:36:07,320 --> 00:36:13,650
Zamiast wykorzystać tę głowę, nazywamy to "wskaźnik", choć tak naprawdę to nie wskaźnik

468
00:36:13,650 --> 00:36:16,430
w ścisłym znaczeniu, to nie jest typ wskaźnika.

469
00:36:16,430 --> 00:36:19,410
To nie int * lub char * lub coś w tym jest.

470
00:36:19,410 --> 00:36:28,930
Ale to wskazanie lub wskazania głowę naszej kolejki. Tak?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Jak Dequeue wiem po prostu zasnąć, co jest w głowie?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Jak Dequeue umieć zasnąć, co znajduje się w głowie? Prawo >> tak.

473
00:36:43,620 --> 00:36:49,050
>> Co to patrząc na to tylko, co pole głowa jest ustawiona.

474
00:36:49,050 --> 00:36:52,710
Tak więc w tym pierwszym przypadku, jeśli przyjrzymy się właśnie tutaj,

475
00:36:52,710 --> 00:36:55,690
nasza głowa jest 0, 0 index. >> Racja.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Więc po prostu mówi w porządku, dobrze, element o indeksie 0, ciąg "hi",

477
00:37:00,500 --> 00:37:03,050
Element jest na czele naszej kolejki.

478
00:37:03,050 --> 00:37:05,570
Więc jedziemy z kolejki tego faceta.

479
00:37:05,570 --> 00:37:09,800
I to będzie element, który zostanie zwrócony do rozmówcy.

480
00:37:09,800 --> 00:37:14,540
Tak, Saad? >> Więc głowa zasadzie ustawia - gdzie idziesz do indeksu to?

481
00:37:14,540 --> 00:37:17,750
To początek tego? >> Tak. >> Okay.

482
00:37:17,750 --> 00:37:22,900
[Hardison] To staje się nowy początek naszej tablicy.

483
00:37:22,900 --> 00:37:28,930
Więc kiedy usunie z niej coś, wszystko co musisz zrobić, to przejść do elementu o indeksie q.head,

484
00:37:28,930 --> 00:37:32,240
i będzie to element, który chcesz odłączyć z kolejki.

485
00:37:32,240 --> 00:37:34,930
Trzeba też zmniejszyć rozmiar.

486
00:37:34,930 --> 00:37:39,430
Zobaczymy za chwilę, gdy robi się trochę trudne z tym.

487
00:37:39,430 --> 00:37:46,520
Mamy z kolejki, a teraz, jeśli enqueue ponownie,

488
00:37:46,520 --> 00:37:51,300
gdzie mamy enqueue?

489
00:37:51,300 --> 00:37:55,000
Gdzie pójść następny element w naszej kolejce?

490
00:37:55,000 --> 00:37:57,980
Że chcemy enqueue ciąg "CS".

491
00:37:57,980 --> 00:38:02,240
Do której indeks to pójdzie? [Studenci] Strings [2]. >> Two.

492
00:38:02,240 --> 00:38:04,980
Dlaczego 2 a nie 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Bo teraz głowa jest 1, tak jak to jest na początku listy?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Racja. I, co oznacza koniec listy?

495
00:38:21,220 --> 00:38:23,290
O czym my używany do oznaczać koniec naszej kolejki?

496
00:38:23,290 --> 00:38:25,970
Głowa jest głową naszego kolejce, początek naszej kolejki.

497
00:38:25,970 --> 00:38:29,530
Co to jest koniec naszej kolejki? [Studenci] rozmiar. >> Size, dokładnie.

498
00:38:29,530 --> 00:38:36,360
Tak więc nasze nowe elementy iść w rozmiarze, a elementy, które zdjąć spaść na głowę.

499
00:38:36,360 --> 00:38:45,390
Kiedy skolejkowania następny element, mamy wprowadzenie go w rozmiarze.

500
00:38:45,390 --> 00:38:48,530
[Student] Przed umieszczeniem że chociaż rozmiar był 1, prawda?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Racja. Więc nie dość w rozmiarze. + Rozmiar nie, +1, ale głowa +.

502
00:38:55,690 --> 00:38:59,990
Ponieważ wszystko przesunięte o kwotę głowy.

503
00:38:59,990 --> 00:39:14,270
Więc, teraz mamy kolejkę wielkości 1, który rozpoczyna się od indeksu 1.

504
00:39:14,270 --> 00:39:20,730
Ogon jest indeks 2. Tak?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Co się dzieje, gdy z kolejki strings [0], a łańcuch 'sloty pamięci

506
00:39:25,780 --> 00:39:29,420
prostu się opróżnić, w zasadzie, lub po prostu zapomnieć?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Tak. W tym sensie, po prostu zapomina je.

508
00:39:34,700 --> 00:39:42,640
Jeśli byliśmy przechowywania kopii nich -

509
00:39:42,640 --> 00:39:46,310
wiele struktur danych często zapisywać swoje własne kopie elementów

510
00:39:46,310 --> 00:39:51,760
tak, że osoba zarządzająca struktury danych nie trzeba się martwić

511
00:39:51,760 --> 00:39:53,650
gdzie wszystkie te wskaźniki idą.

512
00:39:53,650 --> 00:39:56,000
Struktura danych trzyma się wszystko trzyma na wszystkich egzemplarzach,

513
00:39:56,000 --> 00:39:59,580
aby upewnić się, że wszystko nadal odpowiednio.

514
00:39:59,580 --> 00:40:03,140
Jednakże, w tym przypadku po prostu tych strukturach, dla uproszczenia,

515
00:40:03,140 --> 00:40:05,580
nie tworzenia kopii wszystkiego co mamy przechowywanie w nich.

516
00:40:05,580 --> 00:40:08,630
[Student] Więc to jest ciągła tablica -? >> Tak.

517
00:40:08,630 --> 00:40:14,350
Jeśli spojrzymy na to, co było definicja tej struktury, to jest.

518
00:40:14,350 --> 00:40:19,110
To jest po prostu zwykła tablica, jakbyś zobaczył,

519
00:40:19,110 --> 00:40:24,280
tablica char * s.

520
00:40:24,280 --> 00:40:26,340
Czy to -? >> Tak, zastanawiałam się

521
00:40:26,340 --> 00:40:29,130
jeśli będziesz w końcu zabraknie pamięci, do pewnego stopnia,

522
00:40:29,130 --> 00:40:32,330
jeśli wszystkie te puste miejsca w swojej tablicy?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Tak, to jest dobry punkt.

524
00:40:36,390 --> 00:40:41,530
>> Jeśli spojrzymy na to, co się stało teraz w tym miejscu,

525
00:40:41,530 --> 00:40:46,350
mamy wypełniony naszą kolejkę, to wygląda.

526
00:40:46,350 --> 00:40:50,390
Ale tak naprawdę nie wypełni naszą kolejkę

527
00:40:50,390 --> 00:40:57,710
bo mamy kolejkę, która jest rozmiar 2, ale zaczyna się od indeksu 1,

528
00:40:57,710 --> 00:41:02,160
bo tam nasz wskaźnik głowa.

529
00:41:02,160 --> 00:41:08,400
Jak mówisz, że element na strunach [0], o indeksie 0, nie jest tak naprawdę istnieje.

530
00:41:08,400 --> 00:41:10,450
To nie leży w naszej kolejce już.

531
00:41:10,450 --> 00:41:16,460
My po prostu nie przeszkadzało iść i go zastąpić, gdy rozkolejkowywana go.

532
00:41:16,460 --> 00:41:18,700
Dlatego, mimo że wygląda na to, że zabrakło pamięci, naprawdę nie.

533
00:41:18,700 --> 00:41:23,270
To miejsce jest dostępne dla nas w użyciu.

534
00:41:23,270 --> 00:41:29,310
Właściwe zachowanie, jeśli mielibyśmy spróbować i pierwszy rozkolejkowania coś

535
00:41:29,310 --> 00:41:34,420
jak "cześć", które pojawiają bye off.

536
00:41:34,420 --> 00:41:38,460
Teraz nasza kolejka zaczyna się od indeksu 2 i ma wielkość 1.

537
00:41:38,460 --> 00:41:42,240
A teraz, jeśli spróbujemy i enqueue coś ponownie, powiedzmy 50,

538
00:41:42,240 --> 00:41:47,880
50 powinny znaleźć się w tym miejscu o indeksie 0

539
00:41:47,880 --> 00:41:51,270
bo jest jeszcze dostępna dla nas. Tak, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Czy to dzieje się automatycznie?

541
00:41:53,630 --> 00:41:56,150
[Hardison] To nie dzieje się to automatycznie. Musisz zrobić matematyki

542
00:41:56,150 --> 00:42:00,380
aby to działało, ale w istocie to, co zrobiliśmy to my właśnie owinięta.

543
00:42:00,380 --> 00:42:04,070
[Saad] I to jest w porządku, czy to ma dziurę w środku to?

544
00:42:04,070 --> 00:42:08,720
[Hardison] To jest, jeśli możemy math działać prawidłowo.

545
00:42:08,720 --> 00:42:15,470
>> I okazuje się, że to naprawdę nie jest trudno zrobić z operatorem mod.

546
00:42:15,470 --> 00:42:20,040
Więc tak jak zrobiliśmy to z Cezarem i rzeczy crypto,

547
00:42:20,040 --> 00:42:25,190
pomocą mod, możemy dostać rzeczy do zawinięcia i wracamy

548
00:42:25,190 --> 00:42:28,090
wokół i wokół i wokół z naszej kolejki,

549
00:42:28,090 --> 00:42:32,180
utrzymując, że wskaźnik głowa porusza.

550
00:42:32,180 --> 00:42:38,840
Zauważ, że rozmiar jest zawsze szanując liczbę elementów rzeczywistości w kolejce.

551
00:42:38,840 --> 00:42:43,110
I to tylko wskazówka, że ​​głowa trzyma wypady rowerowe.

552
00:42:43,110 --> 00:42:49,660
Jeśli spojrzymy na to, co się tutaj stało, jeśli wrócimy do początku,

553
00:42:49,660 --> 00:42:55,020
i po prostu zobaczyć, co się dzieje w głowie

554
00:42:55,020 --> 00:42:58,240
kiedy enqueue coś, nic się nie stało w głowę.

555
00:42:58,240 --> 00:43:00,970
Kiedy kolejkowane coś innego, nic się nie stało w głowę.

556
00:43:00,970 --> 00:43:04,130
Szybko, jak to rozkolejkowywana coś, głowa idzie w górę o jeden.

557
00:43:04,130 --> 00:43:06,600
Mamy kolejkowane coś, nic nie dzieje się w głowę.

558
00:43:06,600 --> 00:43:11,060
Kiedy usunie z niej coś, nagle głowa zostanie zwiększony.

559
00:43:11,060 --> 00:43:14,660
Kiedy enqueue coś, nic nie dzieje się w głowę.

560
00:43:14,660 --> 00:43:20,240
>> Co by się stało w tym momencie, jakbyśmy byli z kolejki coś znowu?

561
00:43:20,240 --> 00:43:23,240
Wszelkie myśli? Co by się stało w głowę?

562
00:43:23,240 --> 00:43:27,190
Co powinno się stać z głową

563
00:43:27,190 --> 00:43:32,990
gdybyśmy dequeue coś innego?

564
00:43:32,990 --> 00:43:35,400
Głowa teraz jest o indeksie 2,

565
00:43:35,400 --> 00:43:38,920
co oznacza, że ​​na czele kolejki jest strings [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Które zwraca 0? >> Warto powrócić do 0. Należy owinąć powraca, dokładnie.

567
00:43:44,280 --> 00:43:48,440
Do tej pory, za każdym razem zadzwoniliśmy z kolejki, byliśmy dodając jeden do głowy,

568
00:43:48,440 --> 00:43:50,960
dodać jeden do głowy, dodać jeden do głowy, dodać jeden w głowę.

569
00:43:50,960 --> 00:43:58,400
Jak tylko wskaźnik głowy dostaje się do ostatniego indeksu w naszej tablicy,

570
00:43:58,400 --> 00:44:05,650
wtedy mamy do zawijania go wokół na początku, wrócić do 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Co określa zdolność kolejki w stosie?

572
00:44:09,900 --> 00:44:13,120
[Hardison] W tym przypadku, właśnie zostały używając # zdefiniowana stała. >> Okay.

573
00:44:13,120 --> 00:44:19,590
[Hardison] W rzeczywistej. Plik C, można iść i błoto z nim trochę bitów

574
00:44:19,590 --> 00:44:21,710
i sprawiają, że tak duża lub tak mało jak chcesz.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Więc kiedy robisz mu kolejkę, jak zrobić komputer wie

576
00:44:25,310 --> 00:44:29,120
jak duży chcesz stos być?

577
00:44:29,120 --> 00:44:31,700
[Hardison] To wielkie pytanie.

578
00:44:31,700 --> 00:44:34,800
Istnieje kilka sposobów. Jednym z nich jest po prostu zdefiniować go z przodu

579
00:44:34,800 --> 00:44:42,050
i powiedzieć, że to będzie kolejka, która ma 4 elementów lub 50 elementów lub 10.000.

580
00:44:42,050 --> 00:44:45,430
Innym sposobem jest robić to, co ludzie robią wydanie hakerów

581
00:44:45,430 --> 00:44:52,310
i tworzenie funkcji, aby Twoja kolejka rośnie dynamicznie więcej rzeczy po dodaniu w.

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Więc iść z pierwszej opcji, co składnia używasz

583
00:44:54,740 --> 00:44:57,830
aby poinformować program, co jest rozmiar kolejki?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Więc z tego wyjdziemy.

585
00:45:04,780 --> 00:45:12,650
Wciąż jestem w stack.c tutaj, więc jestem po prostu będzie przewijać się do góry tutaj.

586
00:45:12,650 --> 00:45:17,920
Możesz sprawdzić to tutaj? To jest # define pojemności 10.

587
00:45:17,920 --> 00:45:24,600
A to jest prawie dokładnie taka sama składnia, że ​​mamy do kolejki.

588
00:45:24,600 --> 00:45:28,390
Wyjątkiem w kolejce, że mamy dodatkowe pole struct tutaj.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, myślałem, pojemność oznacza zdolność do łańcucha.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Że to jest maksymalna długość słowa. >> Jasne.

591
00:45:36,770 --> 00:45:41,180
Tak. Pojemność tutaj - to świetny punkt.

592
00:45:41,180 --> 00:45:44,000
I to jest coś, co jest trudne

593
00:45:44,000 --> 00:45:49,480
bo to, co mamy zgłaszać tutaj jest tablica char * s.

594
00:45:49,480 --> 00:45:52,770
Tablica wskaźników.

595
00:45:52,770 --> 00:45:56,690
To jest tablica znaków.

596
00:45:56,690 --> 00:46:01,690
To jest chyba to, co widziałem, kiedy już deklarując swoje bufory dla pliku I / O,

597
00:46:01,690 --> 00:46:06,840
kiedy byłaś tworząc ciągi ręcznie na stosie.

598
00:46:06,840 --> 00:46:09,090
Jednak to, co my tu mamy to tablica char * s.

599
00:46:09,090 --> 00:46:13,400
Więc jest to tablica wskaźników.

600
00:46:13,400 --> 00:46:18,350
Właściwie, jeśli Powiększ się i patrzymy na to, co się tu dzieje

601
00:46:18,350 --> 00:46:23,140
w prezentacji, można zobaczyć, że rzeczywiste elementy, dane znakowe

602
00:46:23,140 --> 00:46:26,180
nie są przechowywane w tablicy sam.

603
00:46:26,180 --> 00:46:42,690
Co jest przechowywane w naszej tablicy tu są wskaźnikami do danych znakowych.

604
00:46:42,690 --> 00:46:52,560
Okay. Więc widzieliśmy jak wielkość kolejki jest tak jak z komina,

605
00:46:52,560 --> 00:46:58,670
rozmiar zawsze szanuje liczbę elementów w kolejce.

606
00:46:58,670 --> 00:47:02,720
Po wykonaniu 2 kolejkuje, rozmiar jest 2.

607
00:47:02,720 --> 00:47:07,110
Po dokonaniu Dequeue rozmiar jest teraz 1.

608
00:47:07,110 --> 00:47:09,330
Po wykonaniu kolejnego Enqueue rozmiar jest z powrotem do 2.

609
00:47:09,330 --> 00:47:12,340
Więc rozmiar zdecydowanie przestrzega liczbę elementów w kolejce,

610
00:47:12,340 --> 00:47:15,580
a następnie szef odsuwa rowerze.

611
00:47:15,580 --> 00:47:20,210
To idzie z 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
I za każdym razem wywołujemy Dequeue, wskaźnik zostaje zwiększony głowa do następnego indeksu.

613
00:47:25,620 --> 00:47:29,930
A jeśli szef ma zamiar przejść w pętli powraca do 0.

614
00:47:29,930 --> 00:47:34,870
Więc z tym, możemy napisać rozkolejkowania funkcję.

615
00:47:34,870 --> 00:47:40,200
I zamierzamy opuścić Dodaje funkcję dla wy wdrożyć zamiast.

616
00:47:40,200 --> 00:47:45,880
>> Kiedy usunie z niej elementu z naszej kolejki,

617
00:47:45,880 --> 00:47:55,490
, co było pierwszą rzeczą, że Daniel zrobił, gdy zaczęliśmy pisać pop funkcję stosów?

618
00:47:55,490 --> 00:48:00,490
Pozwól mi usłyszeć od kogoś, kto nie mówi jeszcze.

619
00:48:00,490 --> 00:48:06,710
Zobaczmy, Saad, pamiętasz co Daniel zrobił jak pierwszą rzeczą, kiedy pisał pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] nie było, to było - >> on testowany na coś.

621
00:48:08,860 --> 00:48:12,140
[Saad] Jeśli rozmiar jest większy niż 0. >> Dokładnie.

622
00:48:12,140 --> 00:48:14,390
A co to było za badanie?

623
00:48:14,390 --> 00:48:19,090
[Saad] To było badanie, aby zobaczyć, czy jest coś w środku tablicy.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Tak. Dokładnie. Więc nie można wyskoczyć coś z komina, czy jest pusty.

625
00:48:23,210 --> 00:48:26,510
Podobnie, nie można z kolejki nic z kolejki, jeśli jest pusty.

626
00:48:26,510 --> 00:48:30,420
Co jest pierwszą rzeczą jaką należy zrobić w naszej funkcji Dequeue tutaj, jak myślisz?

627
00:48:30,420 --> 00:48:33,860
[Saad] Jeśli rozmiar jest większy niż 0? >> Tak.

628
00:48:33,860 --> 00:48:37,710
W tym przypadku, mam właściwie tylko testowane, aby zobaczyć, czy jest 0.

629
00:48:37,710 --> 00:48:42,240
Jeśli jest 0, możemy powrócić null.

630
00:48:42,240 --> 00:48:45,280
Ale dokładnie to samo logika.

631
00:48:45,280 --> 00:48:49,110
I niech nadal się z tym.

632
00:48:49,110 --> 00:48:54,600
Jeśli rozmiar nie jest 0, gdzie jest element, który chcemy z kolejki?

633
00:48:54,600 --> 00:48:58,550
[Saad] Na głowie? >> Dokładnie.

634
00:48:58,550 --> 00:49:01,720
Możemy tylko wyciągnąć pierwszy element w naszej kolejce

635
00:49:01,720 --> 00:49:07,040
przez dostęp do elementu w głowicy.

636
00:49:07,040 --> 00:49:14,630
Nic szalony.

637
00:49:14,630 --> 00:49:19,620
Po tym, co powinniśmy zrobić? Co musi się stać?

638
00:49:19,620 --> 00:49:23,740
Jaka była druga rzecz, że rozmawialiśmy o tym w Dequeue?

639
00:49:23,740 --> 00:49:28,130
Dwie rzeczy muszą się zdarzyć, ponieważ nasza kolejka się nie zmieniło.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Zmniejszenie rozmiaru. >> Musimy zmniejszyć rozmiar i zwiększać głowę? Dokładnie.

641
00:49:35,640 --> 00:49:40,600
Aby zwiększyć głowę, nie możemy po prostu ślepo zwiększyć głowę, pamiętam.

642
00:49:40,600 --> 00:49:45,080
Nie możemy po prostu zrobić queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Musimy także ten mod przez pojemności.

644
00:49:51,630 --> 00:49:54,740
I dlaczego mod przez pojemność, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Ponieważ ma do zawinięcia. >> Dokładnie.

646
00:49:58,680 --> 00:50:04,750
Mod przez nas, ponieważ ma zdolności do zawijania powraca do 0.

647
00:50:04,750 --> 00:50:07,400
Więc teraz, w tym momencie, możemy zrobić to, co powiedział Daniel.

648
00:50:07,400 --> 00:50:12,700
Możemy zmniejszyć rozmiar.

649
00:50:12,700 --> 00:50:29,170
A następnie po prostu może zwrócić element, który był na początku kolejki.

650
00:50:29,170 --> 00:50:34,000
To wygląda trochę gnarly na początku. Może masz pytanie. Przepraszam?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] co jest najpierw na początku kolejki? Gdzie to iść?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Pochodzi z czwartej linii od dołu.

653
00:50:42,480 --> 00:50:46,060
Po przetestować, aby upewnić się, że nasza kolejka nie jest pusta,

654
00:50:46,060 --> 00:50:54,100
możemy wyciągnąć char * najpierw musimy wyciągnąć element, który siedzi przy indeksie głowy

655
00:50:54,100 --> 00:50:58,680
naszej tablicy, naszej tablicy smyczki, >> i telefon, że pierwszy?

656
00:50:58,680 --> 00:51:04,500
[Hardison] I nazywamy to pierwsze. Tak.

657
00:51:04,500 --> 00:51:09,850
Wystarczy śledzić na tym, dlaczego uważasz, że musieliśmy to zrobić?

658
00:51:09,850 --> 00:51:18,270
[Sam] Każdy pierwszy jest po prostu powrót q.strings [q.head]? >> Tak.

659
00:51:18,270 --> 00:51:23,830
>> Ponieważ robimy to zmieniających q.head z funkcją MOD,

660
00:51:23,830 --> 00:51:27,810
i nie ma sposobu, aby to zrobić w ciągu linii powrotnej również.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Dokładnie. Jesteś na miejscu. Sam jest całkowicie na miejscu.

662
00:51:31,640 --> 00:51:36,800
Powodem musieliśmy wyciągnąć pierwszy element w naszej kolejce i zapisać je w zmiennej

663
00:51:36,800 --> 00:51:43,030
dlatego ten wiersz gdzie właśnie q.head,

664
00:51:43,030 --> 00:51:47,030
istnieje operator mod tam nie coś, co możemy zrobić, to

665
00:51:47,030 --> 00:51:51,230
i go w życie na głowie bez - w jednej linii.

666
00:51:51,230 --> 00:51:54,480
Więc rzeczywiście wyciągnąć pierwszy element, a następnie ustawić głowę,

667
00:51:54,480 --> 00:52:00,430
dopasować rozmiar, a następnie powrócić element, że wyciągnięta.

668
00:52:00,430 --> 00:52:02,680
I to jest coś, co zobaczymy później wymyślić

669
00:52:02,680 --> 00:52:04,920
związane listy, jak bawić się z nimi.

670
00:52:04,920 --> 00:52:08,410
Często kiedy uwolnienie lub usuwania powiązanych list

671
00:52:08,410 --> 00:52:13,500
trzeba pamiętać, następny element, obok wskaźnika z połączonej listy

672
00:52:13,500 --> 00:52:16,330
Przed oddaniem bieżącego.

673
00:52:16,330 --> 00:52:23,580
Bo inaczej wyrzucić informacje o to, co zostało na liście.

674
00:52:23,580 --> 00:52:34,160
Teraz, jeśli się do danego urządzenia, można otworzyć queue.c--x z tego.

675
00:52:34,160 --> 00:52:39,390
Więc jeśli mogę otworzyć queue.c, pozwól mi powiększyć tutaj

676
00:52:39,390 --> 00:52:44,970
zobaczysz, że masz podobne wyglądającego pliku.

677
00:52:44,970 --> 00:52:49,200
Podobne wyglądający plik, co mieliśmy wcześniej z stack.c.

678
00:52:49,200 --> 00:52:54,690
Mamy naszą struct do kolejki określonej tak, jak widzieliśmy na slajdach.

679
00:52:54,690 --> 00:52:59,870
>> Mamy Dodaje funkcję, która jest dla Ciebie zrobić.

680
00:52:59,870 --> 00:53:04,340
I mamy rozkolejkowania funkcję tutaj.

681
00:53:04,340 --> 00:53:06,870
Dequeue funkcja w pliku jest niewykonane,

682
00:53:06,870 --> 00:53:13,230
ale będę umieścić go z powrotem w programie PowerPoint, tak aby można ją wpisać, jeśli chcesz.

683
00:53:13,230 --> 00:53:16,690
Tak przez kolejne 5 minut lub tak, macie pracować Kolejkuj

684
00:53:16,690 --> 00:53:22,570
który jest prawie na odwrót z kolejki.

685
00:53:22,570 --> 00:53:29,560
Nie musisz dostosować głowę kiedy skolejkowania, ale co masz do regulacji?

686
00:53:29,560 --> 00:53:38,920
Rozmiar. Więc kiedy enqueue głowa pozostaje nietknięty, rozmiar zostanie zmieniony.

687
00:53:38,920 --> 00:53:46,920
Ale zajmuje to trochę - trzeba będzie się bawić z tym mod

688
00:53:46,920 --> 00:53:57,560
aby dowiedzieć się dokładnie, co indeks nowy element należy umieścić w.

689
00:53:57,560 --> 00:54:03,080
Więc dam wam trochę, umieścić usunie z niej z powrotem na slajdzie,

690
00:54:03,080 --> 00:54:05,200
i jak macie pytania, krzyczeć je tak, że możemy

691
00:54:05,200 --> 00:54:09,220
wszyscy mówią o nich jako grupie.

692
00:54:09,220 --> 00:54:13,960
Ponadto, z rozmiaru don't - kiedy zmienić rozmiar, zawsze można po prostu -

693
00:54:13,960 --> 00:54:18,720
masz do mod rozmiar kiedykolwiek? [Daniel] L. >> Nie masz mod rozmiar, prawa.

694
00:54:18,720 --> 00:54:24,260
Ponieważ rozmiar będzie zawsze, jeśli Jeste - przy założeniu, że zarządzanie rzeczy właściwie,

695
00:54:24,260 --> 00:54:30,840
Rozmiar zawsze będzie w zakresie od 0 do 3.

696
00:54:30,840 --> 00:54:38,680
Gdzie masz mod kiedy robisz Enqueue?

697
00:54:38,680 --> 00:54:41,060
[Student] Tylko w głowie. >> Tylko w głowie, dokładnie.

698
00:54:41,060 --> 00:54:44,620
I dlaczego masz mod w ogóle Kolejkuj?

699
00:54:44,620 --> 00:54:48,830
Kiedy jest sytuacja, w której trzeba by mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Jeśli masz rzeczy w przestrzeni, jak na przestrzeni 1 i 2,

701
00:54:53,630 --> 00:54:55,950
a następnie trzeba było coś dodać na 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Tak, dokładnie. Więc jeśli Twój wskaźnik głowa jest na samym końcu,

703
00:55:02,570 --> 00:55:14,210
lub jeśli rozmiar oraz Twoja głowa jest większa, czy raczej będzie się owinąć wokół kolejki.

704
00:55:14,210 --> 00:55:17,830
>> Więc w tej sytuacji, że mamy tutaj na slajdzie teraz,

705
00:55:17,830 --> 00:55:24,370
jeśli chcę enqueue coś teraz,

706
00:55:24,370 --> 00:55:31,110
chcemy enqueue coś o indeksie 0.

707
00:55:31,110 --> 00:55:35,450
Więc jeśli spojrzeć na których 50 idzie, a ja nazywam enqueue 50,

708
00:55:35,450 --> 00:55:40,840
nie przechodzi się na dole. To idzie w 0 indeksu.

709
00:55:40,840 --> 00:55:44,160
Zastępuje on "Hi", który został już wyjęty z kolejki.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Nie dbasz, że usunie z niej już?

711
00:55:46,210 --> 00:55:50,550
Dlaczego nic z głowy w Kolejkuj?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, więc nie jesteś modyfikacji głowicy, przepraszam.

713
00:55:55,770 --> 00:56:02,310
Ale trzeba użyć operatora mod, gdy masz dostęp do

714
00:56:02,310 --> 00:56:04,250
element, który chcesz enqueue gdy masz dostęp

715
00:56:04,250 --> 00:56:06,960
Kolejnym elementem w kolejce.

716
00:56:06,960 --> 00:56:10,960
[Basil] Ja tego nie zrobiłem, i mam "sukces" na tam.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, rozumiem, co mówisz.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Więc nie zrobił - po prostu zrobiła na q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Tak. Właśnie zmienił strony, nie zrobiłem nic z głowy.

720
00:56:20,670 --> 00:56:24,300
[Hardison] W rzeczywistości nie trzeba zresetować głowę być cokolwiek,

721
00:56:24,300 --> 00:56:31,650
ale kiedy indeks do tablicy ciągów,

722
00:56:31,650 --> 00:56:39,500
trzeba rzeczywiście iść do przodu i obliczyć gdzie Kolejnym elementem jest

723
00:56:39,500 --> 00:56:44,230
bo witka stos, następny element w stosie zawsze

724
00:56:44,230 --> 00:56:48,740
w indeksie odpowiadających wielkości.

725
00:56:48,740 --> 00:56:55,850
Jeśli spojrzymy na nasz funkcji Push stosu,

726
00:56:55,850 --> 00:57:03,100
zawsze możemy rzucać w naszym nowym elementem w prawo na wielkość indeksu.

727
00:57:03,100 --> 00:57:06,710
Mając na uwadze, ze w kolejce, nie możemy tego zrobić

728
00:57:06,710 --> 00:57:10,340
bo jeśli jesteśmy w tej sytuacji,

729
00:57:10,340 --> 00:57:18,130
jeśli kolejkowane 50 nasz nowy ciąg pójdzie w prawo na strunach [1]

730
00:57:18,130 --> 00:57:20,540
których nie chcemy robić.

731
00:57:20,540 --> 00:57:41,200
Chcemy mieć nowy łańcuch iść o indeksie 0.

732
00:57:41,200 --> 00:57:44,320
>> Czy ktoś - tak? [Student] Mam pytanie, ale to naprawdę nie jest związane.

733
00:57:44,320 --> 00:57:48,160
Co to znaczy, gdy ktoś po prostu wywołuje coś pred wskaźnik?

734
00:57:48,160 --> 00:57:51,260
Co to jest nazwa skrót? Wiem, że to tylko nazwa.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred wskaźnik? Zobaczmy. W jakim kontekście?

736
00:57:59,110 --> 00:58:01,790
[Student] To było dla wkładki. Mogę zapytać, później, jeśli chcesz

737
00:58:01,790 --> 00:58:03,920
bo to naprawdę nie jest związane, ale po prostu -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Z kodem insert Dawida z wykładu?

739
00:58:07,300 --> 00:58:10,860
Możemy wyciągnąć, że i porozmawiać o tym.

740
00:58:10,860 --> 00:58:15,550
Porozmawiamy o tym dalej, raz mamy do połączonych listach.

741
00:58:15,550 --> 00:58:21,440
>> Więc bardzo szybko sprawdzić, co enqueue funkcja wygląda.

742
00:58:21,440 --> 00:58:26,530
Co było pierwszą rzeczą, że ludzie starali się robić w enqueue linii? W tej kolejce?

743
00:58:26,530 --> 00:58:29,960
Podobny do tego, co zrobił dla stosu pchania.

744
00:58:29,960 --> 00:58:32,080
Co zrobiłeś, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, niezrozumiały]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Dokładnie. Jeśli (q.size POJEMNOŚCI ==) -

747
00:58:45,700 --> 00:58:54,720
Muszę wystawić szelki we właściwym miejscu - return false.

748
00:58:54,720 --> 00:59:01,370
Przybliż trochę. Okay.

749
00:59:01,370 --> 00:59:03,800
Teraz, co jest kolejną rzeczą, że mieliśmy zrobić?

750
00:59:03,800 --> 00:59:11,370
Podobnie jak w przypadku stosu i dodaje się na właściwym miejscu.

751
00:59:11,370 --> 00:59:16,010
A więc to, co było dobre miejsce, aby wstawić to?

752
00:59:16,010 --> 00:59:23,170
Ze stosem to wielkość indeksu, z tym, że to nie do końca to.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Mam q.head--lub - q.strings? >> >> Tak.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod CAPACITY]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Prawdopodobnie chcesz umieścić nawiasy wokół tego

756
00:59:42,740 --> 00:59:48,830
tak, że jesteśmy coraz odpowiednie pierwszeństwo i tak że jest cleart wszystkim.

757
00:59:48,830 --> 00:59:55,800
I ustawić równe? >> Aby ulicy? >> Aby ul. Great.

758
00:59:55,800 --> 01:00:00,160
A teraz, co jest ostatnią rzeczą, że mamy do czynienia?

759
01:00:00,160 --> 01:00:06,780
Podobnie jak to miało miejsce w stosie. >> Zwiększ rozmiar? >> Zwiększ rozmiar.

760
01:00:06,780 --> 01:00:13,830
Boom. , A następnie, od rozrusznika kodem właśnie wrócił false domyślnie

761
01:00:13,830 --> 01:00:27,460
chcemy to zmienić na true, jeśli wszystko idzie przez i wszystko idzie dobrze.

762
01:00:27,460 --> 01:00:33,050
Dobrze. To dużo informacji dla sekcji.

763
01:00:33,050 --> 01:00:39,480
Nie jesteśmy całkiem koniec. Chcemy mówić bardzo szybko o listach pojedynczo-linked.

764
01:00:39,480 --> 01:00:44,010
Powiem to tak, możemy wrócić do niego później.

765
01:00:44,010 --> 01:00:50,850
Ale wróćmy do naszej prezentacji na slajdach tylko kilka.

766
01:00:50,850 --> 01:00:53,790
Więc enqueue jest TODO, teraz zrobiliśmy to.

767
01:00:53,790 --> 01:00:57,430
>> Teraz rzućmy okiem na list pojedynczo-linked.

768
01:00:57,430 --> 01:01:00,040
Rozmawialiśmy o nich nieco trochę więcej w wykładzie.

769
01:01:00,040 --> 01:01:02,540
Jak wielu z was widział demo gdzie mieliśmy ludzi

770
01:01:02,540 --> 01:01:08,220
niezgrabnie wskazując na każdego innych numerów i gospodarstwo? >> Byłem w tym.

771
01:01:08,220 --> 01:01:16,620
>> Co nie myślicie? Zrobiłem, mam nadzieję demystify te trochę?

772
01:01:16,620 --> 01:01:25,990
Z listy, okazuje się, że mamy do czynienia z tego rodzaju, które zamierzamy połączyć węzeł.

773
01:01:25,990 --> 01:01:32,520
Zważywszy, że z kolejki i stosu musieliśmy przypisać struktury, że chcemy zadzwonić kolejkę w stosie,

774
01:01:32,520 --> 01:01:34,860
mieliśmy te nowe kolejki w rodzaju stosu,

775
01:01:34,860 --> 01:01:39,240
tutaj lista jest tak naprawdę składa się z kilka węzłów.

776
01:01:39,240 --> 01:01:45,920
W ten sam sposób, że ciągi są tylko kilka znaków wszystko ułożone obok siebie.

777
01:01:45,920 --> 01:01:50,650
Połączonej listy jest tylko węzeł i inny węzeł, a inny węzeł i inny węzeł.

778
01:01:50,650 --> 01:01:55,080
I zamiast rozbijając wszystkie węzły ze sobą i przechowywanie ich ciągły

779
01:01:55,080 --> 01:01:58,090
wszystkie obok siebie w pamięci,

780
01:01:58,090 --> 01:02:04,470
mając ten następny wskaźnik umożliwia przechowywanie węzłów gdziekolwiek, na chybił trafił.

781
01:02:04,470 --> 01:02:10,500
Rodzaj, a następnie przewodem do ich razem z jednego punktu do drugiego.

782
01:02:10,500 --> 01:02:15,850
>> A co było zaletą, że miał ponad tablicy?

783
01:02:15,850 --> 01:02:21,680
Powyżej przechowywania wszystkiego contiguously prostu trzymaliśmy się obok siebie?

784
01:02:21,680 --> 01:02:24,190
Pamiętasz? Tak? Dynamiczna alokacja pamięci >>?

785
01:02:24,190 --> 01:02:27,220
Dynamiczna alokacja pamięci >> w jakim sensie?

786
01:02:27,220 --> 01:02:31,780
[Student] W, że można zachować dzięki czemu jest większe i nie trzeba, aby przenieść całą tablicę?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Dokładnie. Więc z tablicy, gdy chcesz umieścić nowy element w środku,

788
01:02:40,940 --> 01:02:45,320
trzeba zmieniać wszystko, aby przestrzeń.

789
01:02:45,320 --> 01:02:47,880
I tak jak rozmawialiśmy z kolejki,

790
01:02:47,880 --> 01:02:50,080
dlatego utrzymać ten wskaźnik głowy,

791
01:02:50,080 --> 01:02:52,050
tak, że nie jesteśmy nieustannie zmienia rzeczy.

792
01:02:52,050 --> 01:02:54,520
Bo to ma drogie, jeśli masz duży wachlarz

793
01:02:54,520 --> 01:02:57,130
a ty ciągle robi te losowe wprowadzeniu.

794
01:02:57,130 --> 01:03:00,820
Zważywszy, że z listy, wszystko co musisz zrobić, to wyrzucić go na nowym węźle

795
01:03:00,820 --> 01:03:06,330
dostosować wskaźniki, i gotowe.

796
01:03:06,330 --> 01:03:10,940
Co do bani ten temat?

797
01:03:10,940 --> 01:03:16,830
Abstrahując od faktu, że to nie jest tak łatwo pracować jako tablica? Tak?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Cóż, myślę, że o wiele trudniej jest uzyskać dostęp do konkretnego elementu w połączonej listy?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Nie można po prostu przeskoczyć do dowolnego elementu na środku połączonej listy.

800
01:03:30,470 --> 01:03:33,800
Jak można to zrobić w zamian? >> Trzeba przejść przez to wszystko.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Tak. Musisz przejść przez jedną na raz, jeden na raz.

802
01:03:35,660 --> 01:03:38,480
Jest to ogromny - to ból.

803
01:03:38,480 --> 01:03:41,550
Co jest inny - nie ma innego upadek tego.

804
01:03:41,550 --> 01:03:45,340
[Basil] Nie można iść do przodu i do tyłu? Musisz iść w jednym kierunku?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Tak. Jak więc rozwiązać, że czasami?

806
01:03:48,570 --> 01:03:53,370
[Basil] podwójnie-linked list? >> Dokładnie. Jest podwójnie związane list.

807
01:03:53,370 --> 01:03:55,540
Są też - przepraszam?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] Czy to sam, jak użycie pred rzeczą, która -

809
01:03:57,620 --> 01:04:01,090
Właśnie sobie przypomniałem, że to, co nie jest pred rzecz jest?

810
01:04:01,090 --> 01:04:05,850
Czy nie jest to w między podwójnie i pojedynczo?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Przyjrzyjmy się, co dokładnie robi.

812
01:04:10,020 --> 01:04:15,760
Tak więc zaczynamy. Oto kod lista.

813
01:04:15,760 --> 01:04:25,620
Tutaj mamy predptr, tutaj. Czy to, co pan mówi?

814
01:04:25,620 --> 01:04:30,750
Tak to było - on uwolnienie listy i próbuje przechowywać wskaźnik do niego.

815
01:04:30,750 --> 01:04:35,000
To nie jest to podwójnie, pojedynczo Linked-list.

816
01:04:35,000 --> 01:04:40,090
Możemy porozmawiać o tym później, ponieważ to mówi o uwolnieniu listy

817
01:04:40,090 --> 01:04:42,900
i chcę pokazać inne rzeczy najpierw.

818
01:04:42,900 --> 01:04:51,480
ale to jest po prostu - jest pamiętanie wartości ptr

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, to wskaźnik poprzedzający? >> Tak.

820
01:04:54,170 --> 01:05:04,070
Tak, że możemy wtedy zwiększamy ptr sam zanim to wolne co predptr jest.

821
01:05:04,070 --> 01:05:09,130
Ponieważ nie możemy za darmo, a następnie wywołać ptr ptr = ptr obok, prawda?

822
01:05:09,130 --> 01:05:11,260
To byłoby złe.

823
01:05:11,260 --> 01:05:20,940
Zobaczmy więc, z powrotem do tego faceta.

824
01:05:20,940 --> 01:05:23,900
>> Inne złą rzeczą jest to, że podczas gdy list z tablicy

825
01:05:23,900 --> 01:05:26,520
mamy tylko wszystkie elementy się ułożone obok siebie,

826
01:05:26,520 --> 01:05:29,050
Tutaj również mamy wprowadził ten wskaźnik.

827
01:05:29,050 --> 01:05:34,060
Więc jest dodatkowy fragment pamięci, że jesteśmy konieczności korzystania

828
01:05:34,060 --> 01:05:37,910
dla każdego elementu, że jesteśmy przechowywanie w naszej liście.

829
01:05:37,910 --> 01:05:40,030
Dostajemy elastyczność, ale to wiąże się z kosztami.

830
01:05:40,030 --> 01:05:42,230
Pochodzi z tych kosztów w czasie,

831
01:05:42,230 --> 01:05:45,270
i pochodzi z tego kosztu pamięci też.

832
01:05:45,270 --> 01:05:47,800
Czas w tym sensie, że mamy przejść przez każdego elementu w tablicy

833
01:05:47,800 --> 01:05:58,670
aby znaleźć jeden na indeksie 10, lub że byłby indeks 10 w tablicy.

834
01:05:58,670 --> 01:06:01,230
>> Po prostu bardzo szybko, kiedy wykres z tych list

835
01:06:01,230 --> 01:06:05,980
zazwyczaj trzymamy się na czele listy lub pierwszego wskaźnika na liście

836
01:06:05,980 --> 01:06:08,010
i pamiętać, że jest to prawdziwy wskaźnik.

837
01:06:08,010 --> 01:06:11,100
To tylko 4 bajty. To nie rzeczywisty węzeł sama w sobie.

838
01:06:11,100 --> 01:06:17,120
Więc widać, że nie ma w nim wartość int, nie obok wskaźnika w nim.

839
01:06:17,120 --> 01:06:20,790
Jest to dosłownie tylko wskaźnik.

840
01:06:20,790 --> 01:06:23,550
To będzie wskazywać na coś, co jest rzeczywiste struct node.

841
01:06:23,550 --> 01:06:28,480
[Sam] wskaźnik zwany węzeł? >> To jest - nie. Jest to wskaźnik na coś węzła typu.

842
01:06:28,480 --> 01:06:32,540
Jest to wskaźnik do struktury węzła. >> Oh, w porządku.

843
01:06:32,540 --> 01:06:36,870
Diagram po lewej, kod po prawej stronie.

844
01:06:36,870 --> 01:06:42,190
Możemy ustawić go na wartość null, co jest dobrym sposobem, aby rozpocząć.

845
01:06:42,190 --> 01:06:49,850
Gdy schemat, musisz albo napisać to za nieważną lub umieścić linię przez to podoba.

846
01:06:49,850 --> 01:06:53,910
>> Jednym z najprostszych sposobów do pracy z listami,

847
01:06:53,910 --> 01:06:57,430
i prosimy o nie zarówno prepend i dołączyć, aby zobaczyć różnice między nimi,

848
01:06:57,430 --> 01:07:01,320
ale poprzedzenie jest zdecydowanie łatwiejsze.

849
01:07:01,320 --> 01:07:05,790
Kiedy dołączy, to jest tam, gdzie - kiedy dokleja (7),

850
01:07:05,790 --> 01:07:10,050
idziesz i utworzyć struct node

851
01:07:10,050 --> 01:07:13,870
i ustawić pierwszy punkt do niego, bo teraz, skoro poprzedzany go,

852
01:07:13,870 --> 01:07:17,240
nie będzie na początku na liście.

853
01:07:17,240 --> 01:07:22,540
Jeśli prepend (3), który tworzy inny węzeł, ale teraz 3 jest przed 7.

854
01:07:22,540 --> 01:07:31,130
Więc jesteśmy w istocie popychanie rzeczy na naszej liście.

855
01:07:31,130 --> 01:07:34,720
Teraz widać, że dokleja, czasami ludzie nazywają to push,

856
01:07:34,720 --> 01:07:39,600
bo jesteś pchanie nowy element na liście.

857
01:07:39,600 --> 01:07:43,270
Jest także łatwy do usunięcia z przodu listy.

858
01:07:43,270 --> 01:07:45,650
Więc ludzie często nazywają to pop.

859
01:07:45,650 --> 01:07:52,200
I w ten sposób, możesz emulować stos za pomocą połączonej listy.

860
01:07:52,200 --> 01:07:57,880
Ups. Niestety, teraz dostajemy do dopisywania. Więc tutaj poprzedzany (7), teraz prepend (3).

861
01:07:57,880 --> 01:08:02,600
Jeśli mamy coś innego na poprzedzany tej liście, jeśli poprzedzany (4),

862
01:08:02,600 --> 01:08:06,540
wtedy musielibyśmy 4, a następnie 3 i 7.

863
01:08:06,540 --> 01:08:14,220
Więc możemy pop i usunąć 4, usuń 3, wyjmij 7.

864
01:08:14,220 --> 01:08:16,500
Często bardziej intuicyjny sposób, aby myśleć o to z dopisywania.

865
01:08:16,500 --> 01:08:20,310
Tak już diagramu, co to będzie wyglądać z dołączania tutaj.

866
01:08:20,310 --> 01:08:23,380
Tutaj, dołączany (7) nie wygląda inaczej

867
01:08:23,380 --> 01:08:25,160
bo jest tylko jeden element na liście.

868
01:08:25,160 --> 01:08:28,620
I dołączanie (3) stawia go na końcu.

869
01:08:28,620 --> 01:08:31,020
Może widzisz teraz sprawę z append

870
01:08:31,020 --> 01:08:36,600
jest to, że od kiedy tylko wiedzieć, gdzie początek listy jest

871
01:08:36,600 --> 01:08:39,450
aby dołączyć do listy trzeba chodzić przez całą drogę na liście

872
01:08:39,450 --> 01:08:46,500
aby dostać się do końca, zatrzymać, a następnie zbudować węzeł i wszystko wyłożenia.

873
01:08:46,500 --> 01:08:50,590
Podłączyć wszystkie rzeczy się.

874
01:08:50,590 --> 01:08:55,170
Więc z dokleja, jak po prostu oszukany przez to bardzo szybko,

875
01:08:55,170 --> 01:08:58,170
kiedy dołączy do listy, jest to dość proste.

876
01:08:58,170 --> 01:09:02,960
>> Dokonać w nowy węzeł, wiążą się z dynamicznej alokacji pamięci.

877
01:09:02,960 --> 01:09:09,830
Więc robimy struct node pomocą malloc.

878
01:09:09,830 --> 01:09:14,710
Więc malloc używamy bo że będzie uchylenie pamięć dla nas na później

879
01:09:14,710 --> 01:09:20,350
dlatego, że nie chcę tego - chcemy pamięć ta utrzyma się przez dłuższy czas.

880
01:09:20,350 --> 01:09:25,350
I otrzymujemy wskaźnik do miejsca w pamięci, że po prostu przydzielone.

881
01:09:25,350 --> 01:09:29,260
Używamy rozmiaru węzła, nie sumują pola.

882
01:09:29,260 --> 01:09:31,899
Nie ręcznie wygenerować liczbę bajtów,

883
01:09:31,899 --> 01:09:39,750
zamiast tego używamy sizeof abyśmy wiedzieli dostajemy odpowiednią liczbę bajtów.

884
01:09:39,750 --> 01:09:43,660
Dbamy, aby sprawdzić, że nasze wezwanie malloc udało.

885
01:09:43,660 --> 01:09:47,939
To jest coś, co chcesz robić w ogóle.

886
01:09:47,939 --> 01:09:52,590
Na nowoczesnych maszynach, uruchomiony z pamięci, nie coś, co łatwo jest

887
01:09:52,590 --> 01:09:56,610
chyba że przydział mnóstwo rzeczy i podejmowania ogromną listę,

888
01:09:56,610 --> 01:10:02,220
ale jeśli budujemy rzeczy dla, powiedzmy, jak iPhone lub Android,

889
01:10:02,220 --> 01:10:05,230
ty masz ograniczone zasoby pamięci, zwłaszcza jeśli robisz coś intensywne.

890
01:10:05,230 --> 01:10:08,300
Więc dobrze, aby w praktyce.

891
01:10:08,300 --> 01:10:10,510
>> Zauważ, że użyłem kilka różnych funkcji tutaj

892
01:10:10,510 --> 01:10:12,880
że widziałeś, że są trochę nowych.

893
01:10:12,880 --> 01:10:15,870
Więc fprintf jest tak jak printf

894
01:10:15,870 --> 01:10:21,320
chyba pierwszy argument jest strumień, do którego chcesz drukować.

895
01:10:21,320 --> 01:10:23,900
W tym przypadku chcemy wydrukować na standardowe ciąg błędu

896
01:10:23,900 --> 01:10:29,410
różni się od standardowego outstream.

897
01:10:29,410 --> 01:10:31,620
Domyślnie pokazuje się w tym samym miejscu.

898
01:10:31,620 --> 01:10:34,600
To także drukuje na terminalu, ale można -

899
01:10:34,600 --> 01:10:38,790
korzystania z tych poleceń, dowiedziałem się o, techniki przekierowania

900
01:10:38,790 --> 01:10:42,290
dowiedziałeś się o wideo Tommy'ego za zestaw problemów 4, można skierować ją

901
01:10:42,290 --> 01:10:47,900
w różnych obszarach, a następnie wyjść, tu, wychodzi swoim programie.

902
01:10:47,900 --> 01:10:50,440
To jest w istocie jak powrót z main,

903
01:10:50,440 --> 01:10:53,600
wyjątkiem używamy wyjścia bo tu powrót nie będzie nic robić.

904
01:10:53,600 --> 01:10:57,140
Nie jesteśmy w głównym, więc powrót nie wyjść z programu, jak chcemy.

905
01:10:57,140 --> 01:11:03,020
Więc używamy funkcji wyjścia i nadać mu kod błędu.

906
01:11:03,020 --> 01:11:11,890
To tutaj możemy ustawić nowy węzeł w pole wartości, jego pole i jest równy i, a potem podłączyć go.

907
01:11:11,890 --> 01:11:15,530
Wyznaczamy nowy węzeł następny wskaźnik, aby wskazywał pierwszy

908
01:11:15,530 --> 01:11:20,460
i najpierw się punktem do nowego węzła.

909
01:11:20,460 --> 01:11:25,120
Te pierwsze linie kodu, mamy właściwie budowy nowego węzła.

910
01:11:25,120 --> 01:11:27,280
Nie ostatnie dwie linie tej funkcji, ale te pierwsze.

911
01:11:27,280 --> 01:11:30,290
Rzeczywiście można wyciągnąć do funkcji, do funkcji pomocnika.

912
01:11:30,290 --> 01:11:32,560
To się często to, co mogę zrobić, to, I wyciągnąć ją do funkcji,

913
01:11:32,560 --> 01:11:36,040
Ja nazywam to coś węzła kompilacji

914
01:11:36,040 --> 01:11:40,410
i że trzyma prepend funkcja dość mały, to tylko 3 linie czasu.

915
01:11:40,410 --> 01:11:48,710
Mogę zadzwonić do mojej funkcji budowania węzłów, a potem wszystko drut.

916
01:11:48,710 --> 01:11:51,970
>> Ostatnią rzeczą chcę pokazać wam,

917
01:11:51,970 --> 01:11:54,030
i pozwolę zrobić append i to wszystko na własną rękę,

918
01:11:54,030 --> 01:11:57,500
jest jak iterować listę.

919
01:11:57,500 --> 01:12:00,780
Istnieje kilka różnych sposobów, aby iterować listę.

920
01:12:00,780 --> 01:12:03,140
W tym przypadku, mamy zamiar znaleźć długość listy.

921
01:12:03,140 --> 01:12:06,570
Więc zaczynamy o długości = 0.

922
01:12:06,570 --> 01:12:11,580
Jest to bardzo podobne do pisania strlen do łańcucha.

923
01:12:11,580 --> 01:12:17,780
To jest to, co chcę wam pokazać, to dla pętli tutaj.

924
01:12:17,780 --> 01:12:23,530
To wygląda trochę modny, nie jest to zwykle int i = 0, i <cokolwiek, i + +.

925
01:12:23,530 --> 01:12:34,920
Zamiast to inicjowanie naszą zmienną n być początek listy.

926
01:12:34,920 --> 01:12:40,620
I kiedy nasz iterator zmienna nie jest pusta, możemy iść dalej.

927
01:12:40,620 --> 01:12:46,340
To dlatego, że zgodnie z konwencją, koniec naszej listy będzie null.

928
01:12:46,340 --> 01:12:48,770
A następnie, aby zwiększyć, a nie robi + +,

929
01:12:48,770 --> 01:12:57,010
związane równoważne lista + + n = n-> następne.

930
01:12:57,010 --> 01:13:00,410
>> Dam ci wypełnić luki tutaj, ponieważ jesteśmy poza czasem.

931
01:13:00,410 --> 01:13:09,300
Ale o tym pamiętać podczas pracy nad swoimi psets spellr.

932
01:13:09,300 --> 01:13:11,650
Linked list, jeśli wdrożenie tabeli mieszania,

933
01:13:11,650 --> 01:13:14,010
na pewno bardzo się przydają.

934
01:13:14,010 --> 01:13:21,780
I posiadające ten idiom w pętli na rzeczy, że życie o wiele łatwiejsze, mam nadzieję.

935
01:13:21,780 --> 01:13:25,910
Wszelkie pytania, szybko?

936
01:13:25,910 --> 01:13:28,920
[Sam] Czy możesz wysłać wypełniony SLL i SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Tak. Będę wysyłać wypełnione slajdy i wypełniony stos SLL i queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]