1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Secțiunea 6: mai puțin confortabilă]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Universitatea Harvard]

3
00:00:05,040 --> 00:00:07,320
[Acest lucru este CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Bine. Bine ați venit la secțiunea 6.

5
00:00:11,840 --> 00:00:14,690
În această săptămână, vom vorbi despre structuri de date în secțiune,

6
00:00:14,690 --> 00:00:19,780
primul rând pentru că problema aceasta saptamana setat pe spellr

7
00:00:19,780 --> 00:00:24,410
face o grămadă de explorare diferite structuri de date.

8
00:00:24,410 --> 00:00:26,520
Există o mulțime de moduri diferite pe care le puteți merge cu set de probleme,

9
00:00:26,520 --> 00:00:31,570
și structurile de date pe care le cunoașteți mai multe despre, mai multe lucruri interesante pe care le puteți face.

10
00:00:31,570 --> 00:00:34,990
>> Deci, să începem. În primul rând vom vorbi despre stive,

11
00:00:34,990 --> 00:00:37,530
datele stack și coada de structuri care le vom discuta despre.

12
00:00:37,530 --> 00:00:40,560
Stive și cozile sunt foarte utile atunci când vom începe să vorbim despre graficele,

13
00:00:40,560 --> 00:00:44,390
care noi nu vom face atât de mult de acum.

14
00:00:44,390 --> 00:00:52,820
Dar ei sunt foarte bine pentru a înțelege una dintre cele mai mari structuri de date fundamentale ale CS.

15
00:00:52,820 --> 00:00:54,880
Descrierea din caietul de sarcini set de probleme,

16
00:00:54,880 --> 00:00:59,260
dacă îl trage în sus, vorbește despre stive fi înrudit cu

17
00:00:59,260 --> 00:01:05,239
gramada de tăvi de luat masa pe care le au în cantina la săli de mese

18
00:01:05,239 --> 00:01:09,680
în cazul în care atunci când personalul de mese vine si pune tăvile de luat masa afară după ce le-am curățat,

19
00:01:09,680 --> 00:01:12,000
ei stiva-le una peste alta.

20
00:01:12,000 --> 00:01:15,050
Și apoi, când copiii vin în pentru a obține produse alimentare,

21
00:01:15,050 --> 00:01:19,490
ei trageți tăvile de pe, în primul rând de sus o, apoi cea de sub ea, apoi cea de mai jos care.

22
00:01:19,490 --> 00:01:25,190
Deci, într-adevăr, în primul rând că tava de personalul de mese pus jos este ultima care se decolat.

23
00:01:25,190 --> 00:01:32,330
Ultima faptul că personalul pus pe mese este prima care se ia off pentru cină.

24
00:01:32,330 --> 00:01:38,100
În spec. set de probleme, pe care le puteți descărca dacă nu ați făcut deja,

25
00:01:38,100 --> 00:01:46,730
vorbim despre modelarea unei dumneavoastra Structura de date stivă folosirea acestui tip de struct.

26
00:01:46,730 --> 00:01:51,070
>> Deci, ceea ce am ajuns aici, acest lucru este similar cu ceea ce a fost prezentat în curs,

27
00:01:51,070 --> 00:01:58,120
cu excepția cazului în curs am prezentat acest lucru cu Ints ca spre deosebire de char * s.

28
00:01:58,120 --> 00:02:06,250
Acest lucru se întâmplă să fie o stivă care stochează ce?

29
00:02:06,250 --> 00:02:09,009
Daniel? Ce am stocarea în această stivă?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Coarde? Suntem >> stocarea șiruri în această stivă, exact.

31
00:02:15,260 --> 00:02:20,950
Tot ce trebuie să aibă, în scopul de a crea o stivă este o matrice

32
00:02:20,950 --> 00:02:23,920
cu o capacitate deosebită, care, în acest caz,

33
00:02:23,920 --> 00:02:28,020
Capacitatea este de gând să fie în toate capacele, deoarece este o constantă.

34
00:02:28,020 --> 00:02:36,340
Și apoi, în plus față de matrice, tot ce avem nevoie pentru a urmări este dimensiunea actuală a matrice.

35
00:02:36,340 --> 00:02:38,980
Un lucru de remarcat aici că e un fel de cool

36
00:02:38,980 --> 00:02:47,060
este că noi creăm structura de date stivuite pe partea de sus a unui alt structurii de date, matrice.

37
00:02:47,060 --> 00:02:50,110
Există mai multe moduri diferite de a pune în aplicare stive.

38
00:02:50,110 --> 00:02:54,250
Noi nu-l va face destul de încă, dar sperăm că după ce face problemele legate de-listă,

39
00:02:54,250 --> 00:03:00,520
veți vedea cum puteți implementa cu ușurință o stivă pe partea de sus a unei liste legate, de asemenea.

40
00:03:00,520 --> 00:03:02,640
Dar pentru moment, vom lipi de tablouri.

41
00:03:02,640 --> 00:03:06,350
Deci, din nou, tot ce avem nevoie este o matrice, iar noi trebuie doar să urmăriți dimensiunea matrice.

42
00:03:06,350 --> 00:03:09,850
[Sam] Ne pare rău, de ce ai spus stiva e pe partea de sus a siruri de caractere?

43
00:03:09,850 --> 00:03:13,440
Pentru mine se pare ca siruri de caractere sunt în stivă.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Da. Suntem crearea, ne luând în structura noastră de date matrice -

45
00:03:16,790 --> 00:03:22,130
E o întrebare foarte bună. Deci, întrebarea este de ce, pentru oamenii care se uită acest lucru online,

46
00:03:22,130 --> 00:03:24,140
de ce ne spun că stiva este pe partea de sus a siruri de caractere,

47
00:03:24,140 --> 00:03:27,990
deoarece aici se pare ca siruri de caractere sunt în interiorul stivei?

48
00:03:27,990 --> 00:03:31,050
Care este total caz.

49
00:03:31,050 --> 00:03:34,660
Ceea ce am fost referindu-se la faptul că a fost avem o structură de date matrice.

50
00:03:34,660 --> 00:03:39,290
Avem o serie de char * s, această matrice de siruri de caractere,

51
00:03:39,290 --> 00:03:45,300
și vom adăuga la faptul că, în scopul de a crea structura de date stivuite.

52
00:03:45,300 --> 00:03:48,620
>> Deci, o stivă este puțin mai complexă decât o matrice.

53
00:03:48,620 --> 00:03:51,890
Putem folosi o matrice pentru a construi un stack.

54
00:03:51,890 --> 00:03:55,810
Deci, asta e în cazul în care spunem că stiva este construit pe partea de sus a unei matrice.

55
00:03:55,810 --> 00:04:02,510
De asemenea, așa cum am spus mai devreme, putem construi o stivă pe partea de sus a unei liste legate.

56
00:04:02,510 --> 00:04:04,960
În loc de a folosi un tablou de a deține elemente noastre,

57
00:04:04,960 --> 00:04:10,070
am putea folosi o listă legat de a deține elemente noastre și de a construi în jurul valorii de stiva asta.

58
00:04:10,070 --> 00:04:12,420
Să mergem printr-o serie de exemple, se uită la un cod,

59
00:04:12,420 --> 00:04:14,960
pentru a vedea ce se intampla de fapt aici.

60
00:04:14,960 --> 00:04:23,400
Pe stânga, am aruncat ce struct stiva va arăta în memorie

61
00:04:23,400 --> 00:04:28,330
în cazul în care capacitatea au fost definite pentru a fi # patru.

62
00:04:28,330 --> 00:04:33,490
Avem nostru de patru-element de matrice char *.

63
00:04:33,490 --> 00:04:38,110
Avem strings [0], siruri de caractere [1], siruri de caractere [2], siruri de caractere [3],

64
00:04:38,110 --> 00:04:43,800
și apoi că spațiul ultima pentru întreg dimensiunea noastră.

65
00:04:43,800 --> 00:04:46,270
Are acest sens? Bine.

66
00:04:46,270 --> 00:04:48,790
Aceasta este ceea ce se întâmplă dacă ceea ce fac eu pe dreapta,

67
00:04:48,790 --> 00:04:55,790
care va fi codul meu, este să declare doar un struct, o struct stivuite numit uri.

68
00:04:55,790 --> 00:05:01,270
Aceasta este ceea ce primim. Acesta stabilește această amprentă în memorie.

69
00:05:01,270 --> 00:05:05,590
Prima întrebare aici este ceea ce sunt conținutul acestui struct stiva?

70
00:05:05,590 --> 00:05:09,250
Chiar acum sunt nimic, dar nu sunt în totalitate nimic.

71
00:05:09,250 --> 00:05:13,300
Sunt acest tip de gunoi. Nu avem nici o idee ce e în ele.

72
00:05:13,300 --> 00:05:17,000
Când ne-am declara e coșul de fum, suntem aruncat doar ca pe partea de sus în jos de memorie.

73
00:05:17,000 --> 00:05:19,840
E un fel de declarare int i, și nu-l inițializarea.

74
00:05:19,840 --> 00:05:21,730
Tu nu știi ce e acolo. Puteți citi ce e acolo,

75
00:05:21,730 --> 00:05:27,690
dar nu ar putea fi super util.

76
00:05:27,690 --> 00:05:32,680
Un lucru pe care doriți să vă amintiți întotdeauna să faceți este să inițializeze tot ce trebuie să fie inițializat.

77
00:05:32,680 --> 00:05:35,820
În acest caz, vom inițializa dimensiunea sa fie zero,

78
00:05:35,820 --> 00:05:39,960
pentru că o să se dovedesc a fi foarte important pentru noi.

79
00:05:39,960 --> 00:05:43,450
Am putea merge mai departe și a inițializa toate indicatoarele, toate s char *,

80
00:05:43,450 --> 00:05:49,670
să fie o valoare ușor de înțeles, probabil nul.

81
00:05:49,670 --> 00:05:58,270
Dar nu e totul necesar ca facem asta.

82
00:05:58,270 --> 00:06:04,200
>> Acum, cele două operațiuni principale de pe stivele sunt?

83
00:06:04,200 --> 00:06:07,610
Amintește cineva de la prelegere ce faci cu stive? Da?

84
00:06:07,610 --> 00:06:09,700
[Stella] Împingerea și popping? Exact >>.

85
00:06:09,700 --> 00:06:13,810
Împingerea și popping sunt cele două operațiuni principale de pe stive.

86
00:06:13,810 --> 00:06:17,060
Și ce împinge face? Se pune ceva >> pe partea de sus

87
00:06:17,060 --> 00:06:19,300
de stiva, apoi popping-l ia de pe.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Exact. Deci, împingând împinge ceva pe partea de sus a stivei.

89
00:06:23,150 --> 00:06:27,700
E ca și cum personalul de mese a pune o tava de servit masa în jos pe tejghea.

90
00:06:27,700 --> 00:06:33,630
Și popping este de a lua o tavă de mese de pe stivă.

91
00:06:33,630 --> 00:06:36,460
Să se plimbe prin câteva exemple de ceea ce se întâmplă

92
00:06:36,460 --> 00:06:39,720
când ne împinge lucrurile în stivă.

93
00:06:39,720 --> 00:06:45,110
Dacă ar fi să împingă șirul "Hello" pe stivă nostru,

94
00:06:45,110 --> 00:06:49,760
aceasta este ceea ce diagrama noastră ar arăta ca acum.

95
00:06:49,760 --> 00:06:53,410
Vezi ce se întâmplă?

96
00:06:53,410 --> 00:06:56,530
Am împins în primul element al array noastre siruri de caractere

97
00:06:56,530 --> 00:07:01,420
si am marit numarul nostru de a fi dimensiunea 1.

98
00:07:01,420 --> 00:07:05,340
Deci, dacă ne uităm la diferența dintre cele două diapozitive, aici a fost de 0, aici e înainte de împingere.

99
00:07:05,340 --> 00:07:08,690
Aici este după împingere.

100
00:07:08,690 --> 00:07:13,460
Înainte de a împinge, după împingere.

101
00:07:13,460 --> 00:07:16,860
Și acum avem un element din stivă nostru.

102
00:07:16,860 --> 00:07:20,970
E șirul "Bună ziua", și asta e tot.

103
00:07:20,970 --> 00:07:24,440
Orice altceva în matrice, în gama noastră siruri de caractere, este încă gunoi.

104
00:07:24,440 --> 00:07:27,070
Noi nu l-am inițializat.

105
00:07:27,070 --> 00:07:29,410
Să spunem că împinge un alt șir pe stivă nostru.

106
00:07:29,410 --> 00:07:32,210
Mergem să împingă "lumea" de pe acest timp.

107
00:07:32,210 --> 00:07:35,160
Deci, puteți vedea "lumea" aici merge pe partea de sus a "hello",

108
00:07:35,160 --> 00:07:40,040
și numărul de dimensiunea merge pana la 2.

109
00:07:40,040 --> 00:07:44,520
Acum putem împinge "CS50", și că voi merge pe partea de sus din nou.

110
00:07:44,520 --> 00:07:51,110
Dacă ne întoarcem, puteți vedea cum ne împinge lucrurile pe partea de sus a stivei.

111
00:07:51,110 --> 00:07:53,320
Și acum ajungem la pop.

112
00:07:53,320 --> 00:07:58,910
Când ne-am mi-a venit ceva de pe stivă, ce sa întâmplat?

113
00:07:58,910 --> 00:08:01,540
Oricine vezi diferența? E destul de subtil.

114
00:08:01,540 --> 00:08:05,810
[Student] dimensiune. Da >>, dimensiunea sa schimbat.

115
00:08:05,810 --> 00:08:09,040
>> Ce altceva ți-ar fi așteptat să se schimbe?

116
00:08:09,040 --> 00:08:14,280
[Student] siruri de caractere, prea. Corect >>. Siruri de caractere prea.

117
00:08:14,280 --> 00:08:17,110
Se pare că, atunci când faci în acest fel,

118
00:08:17,110 --> 00:08:21,960
pentru ca nu suntem copierea elementelor în stivă nostru,

119
00:08:21,960 --> 00:08:24,670
noi de fapt, nu trebuie să faci nimic, putem folosi doar dimensiunea

120
00:08:24,670 --> 00:08:28,630
pentru a ține evidența numărului de lucruri în gama noastră

121
00:08:28,630 --> 00:08:33,780
astfel încât atunci când ne pop din nou, din nou, am decrement doar dimensiunea noastră de până la 1.

122
00:08:33,780 --> 00:08:39,440
Nu e nevoie de a merge de fapt și să suprascrie nimic.

123
00:08:39,440 --> 00:08:41,710
Un fel de funky.

124
00:08:41,710 --> 00:08:46,520
Se pare că am de obicei, lasa doar lucrurile în pace, pentru că e mai puțin de lucru pentru noi să facem.

125
00:08:46,520 --> 00:08:50,060
Dacă noi nu trebuie să ne întoarcem și să suprascrieți ceva, atunci de ce o faci?

126
00:08:50,060 --> 00:08:54,150
Așa că atunci când am pop de două ori de pe stivă, tot ceea ce face este descreste marimea de cateva ori.

127
00:08:54,150 --> 00:08:59,120
Și din nou, aceasta este doar pentru că nu suntem copierea lucruri în stivă nostru.

128
00:08:59,120 --> 00:09:01,320
Da? Dă-i drumul.

129
00:09:01,320 --> 00:09:04,460
[Student, neinteligibil] >> Și apoi ce se întâmplă atunci când vă împinge ceva nou?

130
00:09:04,460 --> 00:09:08,570
Când vă împinge ceva nou, unde se duce?

131
00:09:08,570 --> 00:09:12,390
În cazul în care se duce, Vasile? Într-siruri de caractere >> [1]? Corect >>.

132
00:09:12,390 --> 00:09:14,530
De ce nu a mers in siruri [3]?

133
00:09:14,530 --> 00:09:19,410
[Vasile] Pentru că ați uitat că există ceva în șiruri [1] și [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Exact. Stivă noastră, în esență, "a uitat" că a fost exploatație pe nimic

135
00:09:24,040 --> 00:09:29,480
în șiruri [1] sau siruri de caractere [2], asa ca atunci cand apasam "woot",

136
00:09:29,480 --> 00:09:36,670
se pune doar că în element la siruri de caractere [1].

137
00:09:36,670 --> 00:09:41,590
Sunt acolo orice întrebări referitoare la modul de executare a lucrărilor, la un nivel de bază?

138
00:09:41,590 --> 00:09:45,160
[Sam] Deci, acest lucru nu este dinamică în nici un fel, în ceea ce privește cantitatea

139
00:09:45,160 --> 00:09:47,620
sau în ceea ce privește mărimea stivei?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Exact. Aceasta este - punctul a fost că acest lucru nu a fost un stack dinamic growning.

141
00:09:56,750 --> 00:10:02,850
Aceasta este o stivă care pot organiza, la cele mai multe, patru * e char, la cele mai multe patru lucruri.

142
00:10:02,850 --> 00:10:07,580
Dacă ar fi să încercăm și împinge un lucru cincea, ce crezi că ar trebui să se întâmple?

143
00:10:07,580 --> 00:10:11,870
[Elevii, neinteligibile]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Exact. Există o serie de lucruri care ar putea întâmpla.

145
00:10:14,600 --> 00:10:19,330
S-ar putea, eventual, SEG vina, in functie de ceea ce am fost -

146
00:10:19,330 --> 00:10:22,530
exact cum am fost de punere în aplicare back-end.

147
00:10:22,530 --> 00:10:31,740
S-ar putea suprascrie. Aceasta ar putea avea ca buffer overflow care am vorbit despre în clasa.

148
00:10:31,740 --> 00:10:35,240
Care ar fi cel mai evident care ar putea fi suprascrise

149
00:10:35,240 --> 00:10:42,370
în cazul în care am încercat să împingă un lucru in plus pe stivă nostru?

150
00:10:42,370 --> 00:10:44,550
Deci, te-a menționat un buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Care ar putea fi lucrul care ar fi scris peste sau călcat pe

152
00:10:47,870 --> 00:10:52,320
dacă am revărsat accidental prin încercarea de a împinge un lucru suplimentar?

153
00:10:52,320 --> 00:10:54,730
[Daniel, neinteligibil] Posibil >>.

154
00:10:54,730 --> 00:10:58,440
Dar inițial, ceea ce s-ar putea întâmpla? Ce se întâmplă dacă am încercat să împingă o patrulea lucru?

155
00:10:58,440 --> 00:11:06,220
S-ar putea suprascrie dimensiunea, cel puțin cu această schemă de memorie pe care le-am luat.

156
00:11:06,220 --> 00:11:10,880
>> În caietul de sarcini set de probleme, care este ceea ce am de gând să fie de punere în aplicare astăzi,

157
00:11:10,880 --> 00:11:16,030
ceea ce vreau să fac este doar întoarcă fals.

158
00:11:16,030 --> 00:11:20,030
Metoda noastră push este de gând să returneze o valoare boolean,

159
00:11:20,030 --> 00:11:22,920
și că valoarea Boolean va fi adevărată dacă reușește împingere

160
00:11:22,920 --> 00:11:29,730
și fals dacă nu putem împinge nimic mai mult, deoarece stiva este plin.

161
00:11:29,730 --> 00:11:33,620
Să plimbi printr-un pic de cod, care chiar acum.

162
00:11:33,620 --> 00:11:36,400
Iată funcția noastră împingere.

163
00:11:36,400 --> 00:11:40,380
Funcția noastră Apasă pentru un teanc este de gând să ia în șir pentru a pune pe stiva.

164
00:11:40,380 --> 00:11:45,820
Se va întoarce true dacă șirul a fost împins cu succes

165
00:11:45,820 --> 00:11:51,820
pe stivă și fals în caz contrar.

166
00:11:51,820 --> 00:11:59,740
Orice sugestii cu privire la ceea ce ar putea fi un lucru bun primul de a face aici?

167
00:11:59,740 --> 00:12:20,630
[Sam] Dacă dimensiunea este egal cu capacitatea de a reveni apoi fals?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Frumos de locuri de muncă.

169
00:12:23,320 --> 00:12:26,310
În cazul în care dimensiunea este capacitatea, vom reveni fals.

170
00:12:26,310 --> 00:12:29,270
Noi nu putem pune nimic mai mult în stivă nostru.

171
00:12:29,270 --> 00:12:36,900
În caz contrar, dorim să punem ceva pe partea de sus a stivei.

172
00:12:36,900 --> 00:12:41,670
Care este "partea de sus a stivei," initial?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Marimea 0? Marimea 0 >>.

174
00:12:43,650 --> 00:12:49,990
Care este partea de sus a stivei după e un singur lucru în stivă? Missy, știi?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. Dimensiune >> este una, exact. Vă păstrați adăugarea la dimensiunea,

176
00:12:52,720 --> 00:13:01,690
și de fiecare dată când pui în element nou la dimensiunea indicelui în matrice.

177
00:13:01,690 --> 00:13:05,470
O putem face cu acest tip de o linie, în cazul în care are sens.

178
00:13:05,470 --> 00:13:11,910
Deci, ne-am luat gama noastră siruri de caractere, vom accesa la pagina de index dimensiunea,

179
00:13:11,910 --> 00:13:14,780
și suntem doar de gând pentru a stoca * nostru char acolo.

180
00:13:14,780 --> 00:13:19,340
Observați cum nu exista nici copierea șir întâmplă pe aici,

181
00:13:19,340 --> 00:13:29,680
nici alocarea dinamica a memoriei?

182
00:13:29,680 --> 00:13:34,440
Și apoi Missy adus ceea ce avem acum de făcut,

183
00:13:34,440 --> 00:13:40,570
pentru că ne-ați stocat în șir locul adecvat în matrice,

184
00:13:40,570 --> 00:13:49,230
și ea a spus că a trebuit să incrementa dimensiunea de una, astfel încât suntem gata pentru următoarea împingere.

185
00:13:49,230 --> 00:13:53,950
Astfel încât să putem face asta cu s.size + +.

186
00:13:53,950 --> 00:13:59,330
În acest moment, ne-am împins în gama noastră. Care e ultimul lucru pe care trebuie să facem?

187
00:13:59,330 --> 00:14:10,110
[Student] Înapoi adevărat. Înapoi >> adevărat.

188
00:14:10,110 --> 00:14:14,690
Deci e destul de simplu, un cod destul de simplu. Nu prea mult.

189
00:14:14,690 --> 00:14:17,070
Odată ce v-ați înfășurat capul în jurul valorii de modul în care funcționează stivă,

190
00:14:17,070 --> 00:14:21,910
acest lucru este destul de simplu pentru a pune în aplicare.

191
00:14:21,910 --> 00:14:26,390
>> Acum, următoarea parte din aceasta este popping un șir de pe stivă.

192
00:14:26,390 --> 00:14:29,410
Am de gând să dea voi ceva timp pentru a lucra la acest bit un pic.

193
00:14:29,410 --> 00:14:34,320
E aproape, în esență opusul a ceea ce am făcut aici, în împingere.

194
00:14:34,320 --> 00:14:38,510
Ceea ce am făcut este de fapt - Hopa.

195
00:14:38,510 --> 00:14:48,160
Am pornit un aparat aici, iar în aparat,

196
00:14:48,160 --> 00:14:53,600
Am tras în sus problema set 5 caietul de sarcini.

197
00:14:53,600 --> 00:15:02,560
Dacă vom mări aici, putem vedea eu sunt la cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Ați baieti descărcat acest cod care este situat aici, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Bine. Dacă nu ați făcut acest lucru, asta chiar acum, foarte repede.

200
00:15:15,030 --> 00:15:22,130
O voi face în fereastra terminalul meu.

201
00:15:22,130 --> 00:15:25,090
De fapt am făcut-o aici. Da.

202
00:15:25,090 --> 00:15:34,730
Da, Sam? >> Am o întrebare despre ce ai spus paranteze s.string 's dimensiune a = str?

203
00:15:34,730 --> 00:15:42,910
Ce este str? Este definit ca undeva înainte, sau - oh, în str. char *?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Da, exact. Asta a fost argumentul. >> Oh, bine. Scuze.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Suntem specificând șirul de a împinge inch

206
00:15:49,470 --> 00:15:55,220
Altă întrebare care ar putea veni ca nu am vorbi despre aici a fost

207
00:15:55,220 --> 00:15:58,810
am luat de la sine că am avut această variabilă numită s

208
00:15:58,810 --> 00:16:02,710
care a fost în domeniul de aplicare și accesibile pentru noi.

209
00:16:02,710 --> 00:16:06,960
Am luat de la sine că e fost acest struct stiva.

210
00:16:06,960 --> 00:16:08,930
Deci, uită înapoi la acest cod împinge,

211
00:16:08,930 --> 00:16:13,450
puteți vedea că facem lucruri cu acest șir care s-au trecut în

212
00:16:13,450 --> 00:16:19,210
dar apoi dintr-o dată, suntem accesarea s.size, cum ar fi, în cazul în care au venit de la e?

213
00:16:19,210 --> 00:16:23,020
În codul care ne vom uita puțin în secțiunea arhiva

214
00:16:23,020 --> 00:16:27,100
și apoi lucrurile pe care le veți face în problema ta seturi,

215
00:16:27,100 --> 00:16:32,440
ne-am facut topul nostru struct o variabilă globală

216
00:16:32,440 --> 00:16:36,380
astfel încât să putem avea acces la aceasta în toate funcțiile noastre diferite

217
00:16:36,380 --> 00:16:40,630
fără a fi nevoie să treacă în jurul valorii de manual și se trece prin referire,

218
00:16:40,630 --> 00:16:44,870
face tot ceea ce fel de lucruri să-l.

219
00:16:44,870 --> 00:16:52,280
Ne inseala doar un pic, dacă vreți, pentru a face lucrurile mai frumos.

220
00:16:52,280 --> 00:16:57,430
Și asta e ceva ce facem noi aici, pentru că e pentru distractie, e mai ușor.

221
00:16:57,430 --> 00:17:02,800
De multe ori, veți vedea oameni fac acest lucru în cazul în care acestea au o mare structură de date

222
00:17:02,800 --> 00:17:07,750
care este operat pe cadrul programului lor.

223
00:17:07,750 --> 00:17:09,560
>> Să ne întoarcem pe la aparatul.

224
00:17:09,560 --> 00:17:15,240
Credeți toată lumea obține succes section6.zip?

225
00:17:15,240 --> 00:17:20,440
Toată lumea se dezarhivati ​​folosind section6.zip UnZip?

226
00:17:20,440 --> 00:17:27,200
Dacă te duci în secțiunea 6 director -

227
00:17:27,200 --> 00:17:29,220
Aah, peste tot -

228
00:17:29,220 --> 00:17:32,840
si tu lista ce e aici, vezi că ai trei variante diferite de fișiere. c..

229
00:17:32,840 --> 00:17:38,350
Ai o coadă, un SLL, care este individual-linked listă, precum și un stack.

230
00:17:38,350 --> 00:17:44,600
Dacă vă deschideți stack.c,

231
00:17:44,600 --> 00:17:47,330
puteți vedea că am luat acest struct definite pentru noi,

232
00:17:47,330 --> 00:17:51,330
struct exacta pe care tocmai am vorbit despre în diapozitive.

233
00:17:51,330 --> 00:17:56,340
Avem variabila noastră globală pentru stivă,

234
00:17:56,340 --> 00:18:00,110
avem funcția noastră împingere,

235
00:18:00,110 --> 00:18:04,230
și apoi ne-am luat funcția noastră pop.

236
00:18:04,230 --> 00:18:08,320
Voi pune codul pentru împinge înapoi pe diapozitiv aici,

237
00:18:08,320 --> 00:18:10,660
dar ceea ce mi-ar place ca voi să faceți este, la cele mai bune de capacitatea dumneavoastră,

238
00:18:10,660 --> 00:18:13,790
du-te și pune în aplicare funcția pop.

239
00:18:13,790 --> 00:18:18,480
După ce l-am implementat, puteți compila acest lucru cu a face stivă,

240
00:18:18,480 --> 00:18:22,540
și apoi executați executabil stivă rezultantă,

241
00:18:22,540 --> 00:18:28,390
și care se va desfășura în întregime acest cod de test aici care este în principal.

242
00:18:28,390 --> 00:18:31,060
Și principal are grija de a face, de fapt PUSH și POP apeluri

243
00:18:31,060 --> 00:18:33,220
și asigurându-vă că totul merge prin toate dreapta.

244
00:18:33,220 --> 00:18:36,820
De asemenea, acesta inițializează mărimea stack-ului chiar aici

245
00:18:36,820 --> 00:18:39,780
astfel încât să nu trebuie să vă faceți griji cu privire la inițializarea asta.

246
00:18:39,780 --> 00:18:42,310
Puteți presupune că acesta a fost corect inițializat

247
00:18:42,310 --> 00:18:48,000
de momentul în care accesați-l în funcția de pop.

248
00:18:48,000 --> 00:18:53,530
Are vreun sens?

249
00:18:53,530 --> 00:19:00,100
Deci, aici vom merge. Nu e codul de împingere.

250
00:19:00,100 --> 00:19:13,210
Eu voi da băieți 5 sau 10 minute.

251
00:19:13,210 --> 00:19:15,690
Și, dacă aveți orice întrebări în timp ce sunteți interimar de codificare,

252
00:19:15,690 --> 00:19:17,710
vă rugăm să cereți-le cu voce tare.

253
00:19:17,710 --> 00:19:23,080
Deci, dacă ajungi la un punct sensibil, doar cere.

254
00:19:23,080 --> 00:19:26,030
Lasă-mă să știu, să toată lumea știe.

255
00:19:26,030 --> 00:19:28,160
Lucrați cu vecinul tău.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Noi doar punerea în aplicare a pop acum? Doar >> pop.

257
00:19:30,360 --> 00:19:34,200
Deși aveți posibilitatea să copiați punerea în aplicare a împinge, dacă doriți

258
00:19:34,200 --> 00:19:37,780
astfel ca testarea va funcționa.

259
00:19:37,780 --> 00:19:41,940
Pentru că e greu pentru a testa lucruri intra in -

260
00:19:41,940 --> 00:19:49,030
sau, e greu pentru a testa lucruri popping dintr-o stivă în cazul în care nu există nimic în stivă pentru a începe cu.

261
00:19:49,030 --> 00:19:55,250
>> Ceea ce este pop ar trebui să fie revenirea? Elementul din partea de sus a stivei.

262
00:19:55,250 --> 00:20:01,260
Ar trebui să obțineți elementul de pe partea de sus a stivei

263
00:20:01,260 --> 00:20:05,780
și decrement apoi dimensiunea stivei,

264
00:20:05,780 --> 00:20:07,810
și acum ți-ai pierdut elementul pe partea de sus.

265
00:20:07,810 --> 00:20:11,420
Și apoi te vei întoarce elementul pe partea de sus.

266
00:20:11,420 --> 00:20:20,080
[Student, neinteligibil]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Deci, ce se întâmplă dacă faci asta? [Student, neinteligibil]

268
00:20:28,810 --> 00:20:34,000
Ce se întâmplă este termină accesați probabil, fie

269
00:20:34,000 --> 00:20:37,350
un element care nu a fost inițializat încă, astfel încât dumneavoastră de calcul

270
00:20:37,350 --> 00:20:39,990
a în cazul în care este ultimul element este oprit.

271
00:20:39,990 --> 00:20:46,260
Deci, aici, dacă observați, în apăsare, suntem accesarea siruri de caractere de la elementul s.size

272
00:20:46,260 --> 00:20:48,560
pentru că este un index nou.

273
00:20:48,560 --> 00:20:51,460
E partea de sus a noua stivă.

274
00:20:51,460 --> 00:21:01,100
Întrucât, în pop, s.size va fi spațiul următor,

275
00:21:01,100 --> 00:21:05,210
spațiu care este pe partea de sus a tuturor elementelor din stack-ul tău.

276
00:21:05,210 --> 00:21:10,050
Deci, elementul cel mai de sus, nu este la s.size,

277
00:21:10,050 --> 00:21:14,930
ci, mai degrabă, e sub ea.

278
00:21:14,930 --> 00:21:19,640
>> Un alt lucru de făcut atunci când - în pop,

279
00:21:19,640 --> 00:21:22,030
te trebuie să descrește dimensiunea.

280
00:21:22,030 --> 00:21:28,750
Dacă vă amintiți înapoi la diagrama micul nostru chiar aici,

281
00:21:28,750 --> 00:21:30,980
într-adevăr, singurul lucru pe care am văzut intampla atunci cand am sunat pop

282
00:21:30,980 --> 00:21:36,150
a fost faptul că această dimensiune a scăzut, în primul rând la 2, apoi la 1.

283
00:21:36,150 --> 00:21:42,620
Apoi, când am împins un element nou pe, el ar merge pe la fața locului propriu-zis.

284
00:21:42,620 --> 00:21:49,610
[Vasile] Dacă s.size este 2, atunci nu ar merge la elementul 2,

285
00:21:49,610 --> 00:21:54,400
si apoi ai vrea să pop ca element de off?

286
00:21:54,400 --> 00:21:59,510
Deci, dacă ne-am dus sa - >> Deci să ne uităm la acest lucru din nou.

287
00:21:59,510 --> 00:22:07,730
Dacă aceasta este stiva noastră în acest moment

288
00:22:07,730 --> 00:22:12,130
și numim pop,

289
00:22:12,130 --> 00:22:16,150
la care indicele este elementul cel mai de sus?

290
00:22:16,150 --> 00:22:19,300
[Vasile] La 2, dar o să pop 3. Corect >>.

291
00:22:19,300 --> 00:22:24,220
Deci, asta e în cazul în care dimensiunea noastră este 3, dar vrem să pop element la index 2.

292
00:22:24,220 --> 00:22:29,900
E ca un fel tipic de afara de cel pe care le au cu zero indexarea matrice.

293
00:22:29,900 --> 00:22:36,430
Deci, tu vrei să pop al treilea element, dar al treilea element nu este la indexul 3.

294
00:22:36,430 --> 00:22:39,430
Și motivul pentru care nu trebuie să faci asta minus 1 atunci când suntem împingându

295
00:22:39,430 --> 00:22:44,120
este că acum, observați că elementul cel mai de sus,

296
00:22:44,120 --> 00:22:47,600
dacă ar fi să împingă altceva pe stivă în acest moment,

297
00:22:47,600 --> 00:22:50,360
ne-am dori să-l împingă la indexul 3.

298
00:22:50,360 --> 00:23:03,550
Și doar așa se întâmplă că dimensiunea și indicii linia de sus atunci când sunteți împingându.

299
00:23:03,550 --> 00:23:06,960
>> Cine are un teanc de lucru punere în aplicare?

300
00:23:06,960 --> 00:23:09,690
Ai un stack de lucru unul. Nu v-ați pop lucru încă?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Da. Așa cred.

302
00:23:11,890 --> 00:23:14,610
Programul >> funcționează și nu SEG faulting, este imprimarea?

303
00:23:14,610 --> 00:23:17,520
Are imprima out "de succes" atunci când îl rulați?

304
00:23:17,520 --> 00:23:22,630
Da. Asigurați-stack, executați-l, în cazul în care se imprimă "de succes" si nu merge braț,

305
00:23:22,630 --> 00:23:26,000
atunci totul e bine.

306
00:23:26,000 --> 00:23:34,070
Bine. Să mergem pe la aparatul foarte repede,

307
00:23:34,070 --> 00:23:46,100
și vom merge prin asta.

308
00:23:46,100 --> 00:23:51,110
Dacă ne uităm la ceea ce se întâmplă pe aici cu pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, care a fost primul lucru pe care ai făcut-o?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Dacă s.size este mai mare decât 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Ok. Și de ce ai făcut asta?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Pentru a vă asigura că a fost ceva în interiorul stivei.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Corect. Doriți să testați pentru a vă asigura că s.size este mai mare decât 0;

314
00:24:10,950 --> 00:24:13,280
în caz contrar, ce vrei sa se intample?

315
00:24:13,280 --> 00:24:16,630
[Daniel] nul de returnare? Rentabilitatea >> null, exact.

316
00:24:16,630 --> 00:24:20,740
Deci, dacă s.size este mai mare decât 0. Atunci ce vom face?

317
00:24:20,740 --> 00:24:25,890
Ce facem dacă stiva nu este gol?

318
00:24:25,890 --> 00:24:31,210
[Stella] Tu descreste marimea? Tu >> descreste marimea, bine.

319
00:24:31,210 --> 00:24:34,440
Deci, cum ai făcut asta? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Mare. Și apoi ce-ai făcut?

321
00:24:37,030 --> 00:24:44,140
[Stella] Și apoi i-am spus retur s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Mare.

323
00:24:48,560 --> 00:24:51,940
În caz contrar, te vei întoarce null. Da, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] De ce nu are nevoie de a fi s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Da >>. >> Am înțeles.

326
00:24:58,430 --> 00:25:00,980
[Sam] M-am gândit că tu iei 1 din,

327
00:25:00,980 --> 00:25:04,290
atunci ai de gând să fie returnarea nu una care au cerut.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Și asta a fost doar ceea ce am vorbit despre această problemă cu toată 0 indicilor.

329
00:25:09,400 --> 00:25:11,380
Deci, dacă ne apropia din nou aici.

330
00:25:11,380 --> 00:25:15,650
Dacă ne uităm la tipul ăsta de aici, puteți vedea că, atunci când ne pop,

331
00:25:15,650 --> 00:25:19,340
suntem popping element la index 2.

332
00:25:19,340 --> 00:25:25,200
>> Așa că am reduce dimensiunea noastră în primul rând, apoi dimensiunea noastră coincide indexul nostru.

333
00:25:25,200 --> 00:25:39,650
Dacă noi nu descreste marimea prima, atunci avem de a face dimensiunea -1 și apoi decrementare.

334
00:25:39,650 --> 00:25:45,270
Mare. Toate bune?

335
00:25:45,270 --> 00:25:47,530
Orice întrebări cu privire la acest lucru?

336
00:25:47,530 --> 00:25:54,050
Există un număr de moduri diferite de a scrie aceasta, de asemenea.

337
00:25:54,050 --> 00:26:03,290
De fapt, putem face ceva, chiar - ce putem face cu o linie.

338
00:26:03,290 --> 00:26:05,770
Putem face o întoarcere de o linie.

339
00:26:05,770 --> 00:26:12,980
Deci, putem de fapt, înainte de a descreste ne întoarcem prin a face asta.

340
00:26:12,980 --> 00:26:18,320
Deci, pune - înainte de a s.size.

341
00:26:18,320 --> 00:26:22,060
Asta face linia cu adevarat dens.

342
00:26:22,060 --> 00:26:30,940
În cazul în care diferența dintre - marimea si. S.size--

343
00:26:30,940 --> 00:26:40,130
este faptul că această postfix - ei o numesc postfix, deoarece - vine dupa s.size--

344
00:26:40,130 --> 00:26:47,430
înseamnă că s.size este evaluat în scopul de a găsi indicelui

345
00:26:47,430 --> 00:26:50,410
așa cum este în prezent, atunci când această linie este executat,

346
00:26:50,410 --> 00:26:54,290
și apoi acest lucru - se întâmplă după ce linia este executat.

347
00:26:54,290 --> 00:27:00,340
Dupa element la s.size indicele este accesat.

348
00:27:00,340 --> 00:27:07,260
Și asta nu e ceea ce ne dorim, pentru ca vrem sa se intample prima descreștere.

349
00:27:07,260 --> 00:27:10,990
Othewise, vom fi accesarea matrice, în mod eficient, în afara limitelor.

350
00:27:10,990 --> 00:27:16,850
Vom fi accesarea elementului de mai sus, de fapt cea pe care am dori să o accesați.

351
00:27:16,850 --> 00:27:23,840
Da, Sam? Este mai rapid >> sau de a folosi memorie RAM mai puțin pentru a face într-o singură linie sau nu?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Sincer, într-adevăr depinde.

353
00:27:29,620 --> 00:27:34,220
[Sam, neinteligibil] >> Da, depinde. Puteți face trucuri compilatorului

354
00:27:34,220 --> 00:27:41,580
pentru a obține compilatorului să recunoască faptul că, de obicei, îmi imaginez.

355
00:27:41,580 --> 00:27:44,840
>> Deci, am menționat un pic despre asta optimizare compilator

356
00:27:44,840 --> 00:27:47,400
pe care le puteți face în compilarea,

357
00:27:47,400 --> 00:27:50,580
si asta e genul de lucru pe care un compilator ar putea fi în măsură să dau seama,

358
00:27:50,580 --> 00:27:54,710
ca oh, hei, poate că eu pot face acest lucru într-o singură operație,

359
00:27:54,710 --> 00:27:59,420
spre deosebire de încărcare variabilă în mărime de la RAM,

360
00:27:59,420 --> 00:28:03,770
decrementarea ea, stocarea-l înapoi, și apoi încărcarea înapoi din nou

361
00:28:03,770 --> 00:28:08,000
pentru a procesa restul de această operațiune.

362
00:28:08,000 --> 00:28:10,710
Dar de obicei, nu, acest lucru nu este genul de lucru

363
00:28:10,710 --> 00:28:20,770
care va face programul mult mai rapid.

364
00:28:20,770 --> 00:28:26,000
Orice întrebări mai multe stive?

365
00:28:26,000 --> 00:28:31,360
>> Deci, împingându-și popping. Dacă vreți să încercați ediția hacker,

366
00:28:31,360 --> 00:28:33,660
ceea ce am făcut în ediția hacker este, de fapt dispărut

367
00:28:33,660 --> 00:28:37,670
și a făcut acest teanc să crească dinamic.

368
00:28:37,670 --> 00:28:43,190
Provocarea nu este în primul rând aici, în funcție de împingere,

369
00:28:43,190 --> 00:28:48,820
să dau seama cum de a face ca matrice să crească

370
00:28:48,820 --> 00:28:52,450
cum vă păstrați apăsarea mai multe elemente și mai mult pe la stiva.

371
00:28:52,450 --> 00:28:56,000
E de fapt, nu prea mult cod suplimentar.

372
00:28:56,000 --> 00:29:00,080
Doar un apel la - va trebui să vă amintiți pentru a primi apeluri la malloc acolo în mod corespunzător,

373
00:29:00,080 --> 00:29:03,310
și dau apoi cand ai de gând să sun realloc.

374
00:29:03,310 --> 00:29:06,090
Asta e o provocare distractiv dacă ești interesat.

375
00:29:06,090 --> 00:29:11,550
>> Dar, pentru moment, să trecem mai departe, și hai să vorbim despre cozile.

376
00:29:11,550 --> 00:29:15,680
Derulați pe aici.

377
00:29:15,680 --> 00:29:19,340
Coada este un frate apropiat al stivei.

378
00:29:19,340 --> 00:29:25,380
Deci, în stivă, lucrurile care au fost puse în ultima

379
00:29:25,380 --> 00:29:28,810
au fost primele lucruri care urmează să fie apoi preluate.

380
00:29:28,810 --> 00:29:33,600
Am luat acest ultimul, primul ieșit, sau LIFO, prin care se dispune.

381
00:29:33,600 --> 00:29:38,390
Întrucât, în coadă, cum te-ai astepta de la atunci când sunteți în picioare, în linie,

382
00:29:38,390 --> 00:29:41,980
prima persoană pentru a obține în linie, primul lucru pentru a intra în coada de așteptare,

383
00:29:41,980 --> 00:29:47,630
este primul lucru care devine preluate din coada.

384
00:29:47,630 --> 00:29:51,490
Cozile sunt, de asemenea, adesea folosite atunci când avem de-a face cu grafice,

385
00:29:51,490 --> 00:29:55,560
ca și cum am vorbit despre scurt cu stive,

386
00:29:55,560 --> 00:30:00,260
și cozile sunt, de asemenea, la îndemână pentru o grămadă de alte lucruri.

387
00:30:00,260 --> 00:30:06,180
Un lucru care vine de multe ori încearcă să mențină, de exemplu,

388
00:30:06,180 --> 00:30:12,310
o listă de elemente de sortat.

389
00:30:12,310 --> 00:30:17,650
Și tu poți face acest lucru cu o matrice. Puteți menține o listă sortată de lucruri într-o matrice,

390
00:30:17,650 --> 00:30:20,650
dar în cazul în care devine complicat este atunci va trebui să găsească întotdeauna

391
00:30:20,650 --> 00:30:26,160
locul potrivit pentru a insera următorul lucru.

392
00:30:26,160 --> 00:30:28,250
Deci, dacă aveți o serie de numere, 1 la 10,

393
00:30:28,250 --> 00:30:31,630
și apoi doriți să extindeți că la toate numerele de la 1 100,

394
00:30:31,630 --> 00:30:33,670
și vei primi aceste numere în ordine aleatorie și încearcă să mențină totul

395
00:30:33,670 --> 00:30:40,650
sortate ca te duci prin, vei sfârși având de a face o mulțime de schimbare.

396
00:30:40,650 --> 00:30:43,910
Cu anumite tipuri de cozi și anumite tipuri de structuri de date care stau la baza,

397
00:30:43,910 --> 00:30:46,670
puteți să vă păstrați de fapt destul de simplu.

398
00:30:46,670 --> 00:30:50,640
Nu trebuie să adăugați ceva și apoi remaniere totul de fiecare dată.

399
00:30:50,640 --> 00:30:56,770
De asemenea, nu trebuie să faci o mulțime de deplasare a elementelor interne din jur.

400
00:30:56,770 --> 00:31:02,990
Când ne uităm la o coadă, veți vedea că - de asemenea, în queue.c în secțiunea cod -

401
00:31:02,990 --> 00:31:10,950
struct că am dat de tine este cu adevărat similară cu struct pe care v-am dat pentru un teanc.

402
00:31:10,950 --> 00:31:13,770
>> Există o singură excepție de la acest lucru, și că o singură excepție

403
00:31:13,770 --> 00:31:21,700
este că avem acest număr întreg suplimentară numită cap,

404
00:31:21,700 --> 00:31:28,120
și capul de aici este pentru a ține evidența capul cozii,

405
00:31:28,120 --> 00:31:32,160
sau primul element din coada.

406
00:31:32,160 --> 00:31:37,470
Cu o stivă, noi am fost capabil de a urmări elementul care am fost pe punctul de a prelua,

407
00:31:37,470 --> 00:31:40,800
sau partea de sus a stivei, folosind doar dimensiunea,

408
00:31:40,800 --> 00:31:44,220
întrucât, cu o coadă, avem de a face cu capete opuse.

409
00:31:44,220 --> 00:31:49,000
Încercăm să tac lucruri pe la final, dar apoi lucrurile se întoarcă de pe front.

410
00:31:49,000 --> 00:31:54,640
Atât de eficient, cu capul, avem indicele de începutul cozii,

411
00:31:54,640 --> 00:31:58,920
și dimensiunea ne dă indicele de sfârșitul cozii de așteptare

412
00:31:58,920 --> 00:32:03,730
astfel încât să putem prelua lucruri din cap și se adaugă lucruri pe coada.

413
00:32:03,730 --> 00:32:06,890
Întrucât, cu stivă, am fost doar vreodată de-a face cu partea de sus a stivei.

414
00:32:06,890 --> 00:32:08,900
Am avut niciodată pentru a accesa partea de jos a stivei.

415
00:32:08,900 --> 00:32:12,220
Am adăugat doar lucrurile la început și a luat lucrurile de pe partea de sus

416
00:32:12,220 --> 00:32:17,470
asa ca nu am nevoie de acel câmp suplimentar în interiorul nostru struct.

417
00:32:17,470 --> 00:32:20,590
Asta face, în general, un sens?

418
00:32:20,590 --> 00:32:27,670
Bine. Da, Charlotte? [Charlotte, neinteligibil]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Asta-i o mare problema, iar asta a fost una care a venit în curs.

420
00:32:32,660 --> 00:32:36,290
Poate mers pe jos prin câteva exemple de ce va ilustra

421
00:32:36,290 --> 00:32:41,400
nu vrem să folosiți șiruri [0] ca șef al cozii.

422
00:32:41,400 --> 00:32:46,770
>> Deci, ne imaginăm că avem coadă nostru, vom numi coadă.

423
00:32:46,770 --> 00:32:49,210
La început, când am doar o instanțiat,

424
00:32:49,210 --> 00:32:53,330
când ne-am tocmai a declarat, nu am inițializat nimic.

425
00:32:53,330 --> 00:32:56,790
E tot gunoiul. Deci, desigur, vrem să ne asigurăm că vom inițializa

426
00:32:56,790 --> 00:33:00,950
atât dimensiunea și domeniul cap să fie 0, ceva rezonabil.

427
00:33:00,950 --> 00:33:05,770
Am putea merge mai departe și, de asemenea, null la elementele din coadă noastră.

428
00:33:05,770 --> 00:33:09,930
Și pentru a face acest potrivi diagramă, observăm că acum coada noastră poate deține doar trei elemente;

429
00:33:09,930 --> 00:33:13,150
întrucât stiva noastră ar putea deține patru, coada noastră poate deține doar trei.

430
00:33:13,150 --> 00:33:18,680
Și asta e doar pentru a face potrivi diagrama.

431
00:33:18,680 --> 00:33:26,150
Primul lucru care se întâmplă aici este că redați șirul "hi".

432
00:33:26,150 --> 00:33:30,380
Și la fel cum am făcut și cu stiva, nimic teribil de diferit aici,

433
00:33:30,380 --> 00:33:39,230
am arunca șir pe la siruri de caractere [0] și va incrementa dimensiunea noastră de 1.

434
00:33:39,230 --> 00:33:42,720
Noi redați "la revedere", acesta este pus pe.

435
00:33:42,720 --> 00:33:45,870
Deci, acest lucru arata ca o stivă pentru cea mai mare parte.

436
00:33:45,870 --> 00:33:53,230
Am pornit la drum aici, element nou, element nou, dimensiunea ține merge în sus.

437
00:33:53,230 --> 00:33:56,330
Ce se întâmplă în acest moment atunci când vrem să dequeue ceva?

438
00:33:56,330 --> 00:34:01,280
Atunci când vrem să dequeue, care este elementul pe care dorim să dequeue?

439
00:34:01,280 --> 00:34:04,110
[Vasile] Coarde [0]. Zero >>. Exact dreapta, Vasile.

440
00:34:04,110 --> 00:34:10,960
Dorim să scape de primul șir, aceasta, "hi".

441
00:34:10,960 --> 00:34:13,170
Deci, ceea ce a fost un alt lucru care a schimbat?

442
00:34:13,170 --> 00:34:17,010
Observați atunci când mi-a venit ceva de pe stivă, am schimbat doar dimensiunea,

443
00:34:17,010 --> 00:34:22,080
dar aici, ne-am luat o pereche de lucruri care schimbărilor.

444
00:34:22,080 --> 00:34:27,440
Nu numai schimbarea dimensiunea, dar schimbările cap.

445
00:34:27,440 --> 00:34:31,020
Acest lucru se întoarce la punctul de Charlotte mai devreme:

446
00:34:31,020 --> 00:34:38,699
de ce avem acest cap, precum și?

447
00:34:38,699 --> 00:34:42,110
Are sens acum, Charlotte? Cam >> de.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Natură? Deci, ce sa întâmplat atunci când am dequeued?

449
00:34:47,500 --> 00:34:54,340
Ce a capului face asta acum este interesant?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, pentru că sa schimbat - în regulă. Înțeleg.

451
00:34:56,449 --> 00:35:02,090
Deoarece capul - în cazul în care capul este îndreptat la schimbările în ceea ce privește locația.

452
00:35:02,090 --> 00:35:07,200
Nu mai e întotdeauna un index de zero. >> Da, exact.

453
00:35:07,200 --> 00:35:17,660
Ce sa întâmplat a fost în cazul dequeueing elementul de mare

454
00:35:17,660 --> 00:35:20,590
a fost făcut și nu am mai avut acest domeniu cap

455
00:35:20,590 --> 00:35:26,880
pentru ca am fost sunat mereu acest șir la 0 indicele capul cozii noastre,

456
00:35:26,880 --> 00:35:30,170
atunci vom avea de a schimba restul cozii în jos.

457
00:35:30,170 --> 00:35:36,010
Ne-ar trebui să treacă "la revedere" de la siruri de caractere de la [1] la siruri de caractere [0].

458
00:35:36,010 --> 00:35:38,760
Și siruri de caractere [2] până la siruri de caractere [1].

459
00:35:38,760 --> 00:35:43,050
Și vom avea de a face acest lucru pentru intreaga lista de elemente,

460
00:35:43,050 --> 00:35:45,110
matrice întreaga de elemente.

461
00:35:45,110 --> 00:35:50,490
Și când facem acest lucru cu o matrice, care devine cu adevărat costisitoare.

462
00:35:50,490 --> 00:35:53,340
Deci, aici, nu e mare lucru. Noi avem doar trei elemente din gama noastră.

463
00:35:53,340 --> 00:35:57,230
Dar dacă am avea o coadă de o mie de elemente sau un milion de elemente,

464
00:35:57,230 --> 00:36:00,060
și apoi dintr-o dată, vom începe a face o grămadă de dequeue cheamă pe toți într-o buclă,

465
00:36:00,060 --> 00:36:03,930
lucrurile sunt într-adevăr de gând să încetinească, deoarece schimbă totul în jos în mod constant.

466
00:36:03,930 --> 00:36:07,320
Știi, schimba cu 1, schimbare de 1, schimbare de 1, schimbare de 1.

467
00:36:07,320 --> 00:36:13,650
În schimb, vom folosi acest cap, o numim "pointer", chiar dacă nu e chiar un pointer

468
00:36:13,650 --> 00:36:16,430
în sens strict, nu e un tip de pointer.

469
00:36:16,430 --> 00:36:19,410
Nu e un * int sau un char * sau ceva de genul asta.

470
00:36:19,410 --> 00:36:28,930
Dar e îndreptat sau care indică capul cozii noastre. Da?

471
00:36:28,930 --> 00:36:38,800
>> [Student] Cum dequeue știe să pop doar off tot ceea ce este de la cap?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Cum dequeue știe cum să pop de pe orice e la cap? Corect >>, da.

473
00:36:43,620 --> 00:36:49,050
Ce >> se uită la ce este doar câmpul este setat la cap.

474
00:36:49,050 --> 00:36:52,710
Deci, în acest caz în primul rând, dacă ne uităm aici,

475
00:36:52,710 --> 00:36:55,690
capul nostru este 0, 0 index. Corect >>.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Deci doar spune bine, bine, elementul de la indexul 0, șirul "hi",

477
00:37:00,500 --> 00:37:03,050
este elementul de la capul de coada noastră.

478
00:37:03,050 --> 00:37:05,570
Deci, vom dequeue tipul ăla.

479
00:37:05,570 --> 00:37:09,800
Și care va fi elementul care se returnata apelantului.

480
00:37:09,800 --> 00:37:14,540
Da, Saad? Deci, capul >> stabilește în esență - în cazul în care ai de gând să-l Indicele?

481
00:37:14,540 --> 00:37:17,750
Asta e începutul de ea? Da >>. Bine >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Asta e din ce în ce nou început pentru gama noastră.

483
00:37:22,900 --> 00:37:28,930
Deci, atunci când dequeue ceva, tot ce trebuie să faceți este să accesați elementul de la indexul q.head,

484
00:37:28,930 --> 00:37:32,240
și care va fi elementul pe care doriți să dequeue.

485
00:37:32,240 --> 00:37:34,930
De asemenea, trebuie să descrește dimensiunea.

486
00:37:34,930 --> 00:37:39,430
Vom vedea într-un pic în cazul în care lucrurile devin un pic mai complicat cu acest lucru.

487
00:37:39,430 --> 00:37:46,520
Noi dequeue, și acum, dacă ne redați din nou,

488
00:37:46,520 --> 00:37:51,300
în cazul în care ne redați?

489
00:37:51,300 --> 00:37:55,000
În cazul în care nu elementul următor merge în coada noastră?

490
00:37:55,000 --> 00:37:57,980
Spune că vrem să redați șirul "CS".

491
00:37:57,980 --> 00:38:02,240
În care indicele va merge? [Elevii] Coarde [2]. Doi >>.

492
00:38:02,240 --> 00:38:04,980
De ce 2 și nu 0?

493
00:38:04,980 --> 00:38:13,570
[Vasile] Pentru că acum capul este 1, astfel că e la fel ca la începutul listei?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Corect. Și ce denotă sfârșitul listei?

495
00:38:21,220 --> 00:38:23,290
Ceea ce am fost utilizați pentru a desemna sfârșitul cozii noastre?

496
00:38:23,290 --> 00:38:25,970
Capul este capul cozii noastre, începutul cozii noastre.

497
00:38:25,970 --> 00:38:29,530
Care este sfârșitul cozii noastre? [Studenții] Size. Dimensiune >>, exact.

498
00:38:29,530 --> 00:38:36,360
Deci, elemente de noile noastre merg în mărime de la, precum și elementele pe care le luăm desprinde de pe la cap.

499
00:38:36,360 --> 00:38:45,390
Când ne-am redați elementul următor, vom aceasta punerea în mărime de la.

500
00:38:45,390 --> 00:38:48,530
[Student] Înainte de a pune că, în desi, dimensiunea a fost de 1, nu?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Corect. Deci, nu destul de la dimensiunea. + Dimensiune nu, +1, dar capul +.

502
00:38:55,690 --> 00:38:59,990
Pentru ca am mutat totul de suma de cap.

503
00:38:59,990 --> 00:39:14,270
Deci, aici, acum avem o coadă de dimensiune 1, care începe de la indexul 1.

504
00:39:14,270 --> 00:39:20,730
Coada este indicele 2. Da?

505
00:39:20,730 --> 00:39:25,780
>> [Student] Ce se întâmplă când șiruri dequeue [0], precum și șiruri "sloturi de memorie în

506
00:39:25,780 --> 00:39:29,420
doar te golit, practic, sau pur și simplu uitate?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Da. În acest sens, suntem doar le uita.

508
00:39:34,700 --> 00:39:42,640
Dacă am fost stocarea copii ale acestora pentru -

509
00:39:42,640 --> 00:39:46,310
multe structuri de date va stoca adesea copii proprii ale elementelor

510
00:39:46,310 --> 00:39:51,760
astfel încât persoana care administrează structura de date nu trebuie să vă faceți griji

511
00:39:51,760 --> 00:39:53,650
despre unde toate aceste indicii vor.

512
00:39:53,650 --> 00:39:56,000
Structura de date montate pe la tot, pentru a deține toate copiile,

513
00:39:56,000 --> 00:39:59,580
pentru a vă asigura că totul persistă în mod corespunzător.

514
00:39:59,580 --> 00:40:03,140
Cu toate acestea, în acest caz, aceste structuri de date doar, pentru simplitate,

515
00:40:03,140 --> 00:40:05,580
nu sunt de luare de copii de tot ceea ce suntem stocarea în ele.

516
00:40:05,580 --> 00:40:08,630
[Student] Deci, este aceasta o gamă continuă de -? Da >>.

517
00:40:08,630 --> 00:40:14,350
Dacă ne uităm înapoi la ceea ce a fost de definiția acestei structuri, este.

518
00:40:14,350 --> 00:40:19,110
E doar o matrice standard, ca si cum ai văzut,

519
00:40:19,110 --> 00:40:24,280
o serie de * e char.

520
00:40:24,280 --> 00:40:26,340
Face asta -? Da >>, am fost doar întrebam

521
00:40:26,340 --> 00:40:29,130
în cazul în care veți rula în cele din urmă de memorie, într-o anumită măsură,

522
00:40:29,130 --> 00:40:32,330
dacă aveți toate aceste locuri goale în matrice ta?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Da, e un punct bun.

524
00:40:36,390 --> 00:40:41,530
>> Dacă ne uităm la ceea ce sa întâmplat acum la acest punct,

525
00:40:41,530 --> 00:40:46,350
ne-am umplut coadă nostru, se pare ca.

526
00:40:46,350 --> 00:40:50,390
Dar nu am cu adevărat umplut coada noastră

527
00:40:50,390 --> 00:40:57,710
pentru că avem o coadă care este mărimea 2, dar aceasta începe la indicele 1,

528
00:40:57,710 --> 00:41:02,160
pentru că în cazul în care indicatorul nostru central este.

529
00:41:02,160 --> 00:41:08,400
Ca spuneai, ca element de siruri de caractere de la [0], la indexul 0, nu este cu adevărat acolo.

530
00:41:08,400 --> 00:41:10,450
Nu e în coada noastră mai.

531
00:41:10,450 --> 00:41:16,460
Noi pur si simplu nu sa deranjat să meargă și să-l suprascrie atunci când l-am dequeued.

532
00:41:16,460 --> 00:41:18,700
Deci, chiar daca se pare ca ne-am alerga afară de memorie, noi chiar nu avem.

533
00:41:18,700 --> 00:41:23,270
Că la fața locului este disponibil pentru noi de a utiliza.

534
00:41:23,270 --> 00:41:29,310
Comportamentul caz, dacă ar fi să încercăm și primul dequeue ceva

535
00:41:29,310 --> 00:41:34,420
ca "la revedere", care ar pop pa off.

536
00:41:34,420 --> 00:41:38,460
Acum coada noastră începe de la indexul 2 și este de dimensiuni 1.

537
00:41:38,460 --> 00:41:42,240
Și acum, dacă vom încerca să redați ceva nou, să zicem 50,

538
00:41:42,240 --> 00:41:47,880
50 ar trebui să meargă în acest loc, la index 0

539
00:41:47,880 --> 00:41:51,270
deoarece este încă disponibilă pentru noi. Da, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Asta se întâmplă în mod automat?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Aceasta nu se intampla destul de automat. Trebuie să faci matematică

542
00:41:56,150 --> 00:42:00,380
pentru a face să funcționeze, dar în esență, ceea ce am făcut este tocmai am înfășurat în jurul valorii de.

543
00:42:00,380 --> 00:42:04,070
[Saad] Și este în regulă dacă acest lucru are o gaura in mijlocul ei?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Este, dacă putem face matematica funcționeze în mod corespunzător.

545
00:42:08,720 --> 00:42:15,470
>> Și se dovedește că nu e așa de greu de fapt de a face cu operatorul mod.

546
00:42:15,470 --> 00:42:20,040
Deci, doar cum am facut cu Cezar si chestii cripto,

547
00:42:20,040 --> 00:42:25,190
folosind Mod, putem ajunge să-și încheie în jurul valorii de lucruri și să păstreze merge

548
00:42:25,190 --> 00:42:28,090
în jurul valorii de și în jurul și în jurul nostru, cu coadă,

549
00:42:28,090 --> 00:42:32,180
menținându că indicatorul se deplasează în jurul capului.

550
00:42:32,180 --> 00:42:38,840
Observați că dimensiunea este respectând întotdeauna numărul de elemente de fapt, în cadrul coada.

551
00:42:38,840 --> 00:42:43,110
Și e doar indicatorul care ține capul de ciclism prin intermediul.

552
00:42:43,110 --> 00:42:49,660
Dacă ne uităm la ce sa întâmplat aici, dacă ne întoarcem la început,

553
00:42:49,660 --> 00:42:55,020
și te uiți doar ce se întâmplă cu cap

554
00:42:55,020 --> 00:42:58,240
când ne redați ceva, nu sa întâmplat nimic la cap.

555
00:42:58,240 --> 00:43:00,970
Când ne-am enqueued altceva, nu sa întâmplat nimic la cap.

556
00:43:00,970 --> 00:43:04,130
Imediat ce am dequeued ceva, capul se duce de unul.

557
00:43:04,130 --> 00:43:06,600
Noi enqueued ceva, nu se întâmplă nimic la cap.

558
00:43:06,600 --> 00:43:11,060
Când ne-am dequeue ceva, toate dintr-o dată capul se incrementează.

559
00:43:11,060 --> 00:43:14,660
Când ne-am redați ceva, nu se întâmplă nimic la cap.

560
00:43:14,660 --> 00:43:20,240
>> Ce s-ar întâmpla în acest moment, dacă ar fi să dequeue ceva nou?

561
00:43:20,240 --> 00:43:23,240
Orice gânduri? Ce s-ar întâmpla cu capul?

562
00:43:23,240 --> 00:43:27,190
Ce ar trebui să se întâmple la cap

563
00:43:27,190 --> 00:43:32,990
dacă ar fi să dequeue altceva?

564
00:43:32,990 --> 00:43:35,400
Capul este acum la indexul 2,

565
00:43:35,400 --> 00:43:38,920
ceea ce înseamnă că șeful coada este siruri de caractere [2].

566
00:43:38,920 --> 00:43:44,280
[Student] Care returnează 0? Aceasta >> trebuie să revină la 0. Acesta ar trebui să înfășurați în jurul valorii de spate, exact.

567
00:43:44,280 --> 00:43:48,440
Până în prezent, de fiecare dată când am sunat dequeue, am fost adăugând unul la cap,

568
00:43:48,440 --> 00:43:50,960
adăuga unul la cap, adăugați una la cap, adăugați una la cap.

569
00:43:50,960 --> 00:43:58,400
De îndată ce indicatorul capul ajunge la indicele de ultima gama noastră,

570
00:43:58,400 --> 00:44:05,650
atunci trebuie să-l încheie în jurul valorii de înapoi la început, du-te inapoi la 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Ce determină capacitatea de coadă într-o stivă?

572
00:44:09,900 --> 00:44:13,120
[Hardison] În acest caz, tocmai am fost folosind o constantă # definit. Bine >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] În fișierul în sine. C, poti sa te duci în bălegar și cu un pic

574
00:44:19,590 --> 00:44:21,710
și să-l la fel de mare sau cât de puțin, după cum doriți.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Deci, atunci când faci o coadă, cum faci calculatorul știu

576
00:44:25,310 --> 00:44:29,120
cât de mare vrei să fie stiva?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Aceasta este o întrebare foarte bună.

578
00:44:31,700 --> 00:44:34,800
Există o serie de moduri. Una este de a defini doar o în față

579
00:44:34,800 --> 00:44:42,050
și spun acest lucru este mergi la a fi o coadă care are 4 elemente sau 50 de elemente sau 10.000.

580
00:44:42,050 --> 00:44:45,430
Alt mod este de a face ceea ce oamenii hacker-ilor editia fac

581
00:44:45,430 --> 00:44:52,310
și de a crea funcții pentru a avea coada ta să crească dinamic, ca mai multe lucruri se adaugă inch

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Deci, pentru a merge cu prima opțiune, ceea ce sintaxa folositi

583
00:44:54,740 --> 00:44:57,830
pentru a spune programului ce este dimensiunea cozii?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Așa că hai să ieșim din asta.

585
00:45:04,780 --> 00:45:12,650
Sunt încă în stack.c aici, așa că am de gând doar pentru a defila până la partea de sus aici.

586
00:45:12,650 --> 00:45:17,920
Poți să vezi asta aici? Aceasta este # define capacitate de 10.

587
00:45:17,920 --> 00:45:24,600
Și acest lucru este aproape exact aceeași sintaxă pe care o avem pentru coadă.

588
00:45:24,600 --> 00:45:28,390
Cu excepția cazului în coada de așteptare, ne-am luat acest domeniu struct în plus aici.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, m-am gândit capacitatea de a însemnat capacitatea de șir.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. Asta e. >> lungimea maximă a cuvântului. >> Am înțeles.

591
00:45:36,770 --> 00:45:41,180
Da. Capacitatea de aici - asta e un mare punct.

592
00:45:41,180 --> 00:45:44,000
Și acest lucru este ceva care este dificil

593
00:45:44,000 --> 00:45:49,480
pentru că ceea ce am declarat aici este o matrice de char * s.

594
00:45:49,480 --> 00:45:52,770
Un tablou de pointeri.

595
00:45:52,770 --> 00:45:56,690
Aceasta este o serie de caractere.

596
00:45:56,690 --> 00:46:01,690
Aceasta este, probabil, ceea ce ai văzut când ai fost declararea tampoane dvs. pentru dosar I / O,

597
00:46:01,690 --> 00:46:06,840
atunci când ați fost crearea de siruri de caractere manual pe stiva.

598
00:46:06,840 --> 00:46:09,090
Cu toate acestea, ceea ce am ajuns aici este o matrice de char * s.

599
00:46:09,090 --> 00:46:13,400
Deci e un tablou de pointeri.

600
00:46:13,400 --> 00:46:18,350
De fapt, dacă ne zoom înapoi și ne uităm la ceea ce se întâmplă pe aici

601
00:46:18,350 --> 00:46:23,140
în prezentare, veți vedea că elementele reale, datele de caractere

602
00:46:23,140 --> 00:46:26,180
nu este stocată în matrice în sine.

603
00:46:26,180 --> 00:46:42,690
Ce este stocată în gama noastră aici sunt indicii ale datelor caracter.

604
00:46:42,690 --> 00:46:52,560
Bine. Deci am văzut cum dimensiunea cozii este ca doar cu stivă,

605
00:46:52,560 --> 00:46:58,670
dimensiunea respectă întotdeauna numărul de elemente în prezent în coada de așteptare.

606
00:46:58,670 --> 00:47:02,720
După efectuarea 2 enqueues, dimensiunea este 2.

607
00:47:02,720 --> 00:47:07,110
După efectuarea unei dequeue dimensiunea este acum 1.

608
00:47:07,110 --> 00:47:09,330
După ce ați făcut o altă Puneți în coadă dimensiunea este înapoi până la 2.

609
00:47:09,330 --> 00:47:12,340
Deci, cu siguranta dimensiunea respectă numărul de elemente în coada de așteptare,

610
00:47:12,340 --> 00:47:15,580
și apoi capul ține doar de ciclism.

611
00:47:15,580 --> 00:47:20,210
Se pleaca de la 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Și de fiecare dată când ne numim dequeue, indicatorul cap se incrementează la indicele următor.

613
00:47:25,620 --> 00:47:29,930
Și dacă capul este pe cale de a trece peste, acesta buclele înapoi în jurul valorii de la 0.

614
00:47:29,930 --> 00:47:34,870
Deci, cu asta, putem scrie funcția dequeue.

615
00:47:34,870 --> 00:47:40,200
Și vom lăsa funcția Puneți în coadă pentru voi să pună în aplicare în schimb.

616
00:47:40,200 --> 00:47:45,880
>> Când ne-am dequeue un element din coadă noastre,

617
00:47:45,880 --> 00:47:55,490
ceea ce a fost primul lucru pe care Daniel a făcut-o când am început să scrie funcția de pop pentru stack-uri?

618
00:47:55,490 --> 00:48:00,490
Lasă-mă să aud de la cineva care nu a vorbit încă.

619
00:48:00,490 --> 00:48:06,710
Să vedem, Saad, îți amintești ce a făcut ca Daniel primul lucru când a scris pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Nu a fost, a fost - >> El a testat pentru ceva.

621
00:48:08,860 --> 00:48:12,140
[Saad] Dacă dimensiunea este mai mare decât 0. Exact >>.

622
00:48:12,140 --> 00:48:14,390
Și ce a fost asta de testare pentru?

623
00:48:14,390 --> 00:48:19,090
[Saad] Acest lucru a fost de testare pentru a vedea dacă există ceva în interiorul matrice.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Da. Exact. Deci nu poți pop nimic din stivă dacă e goală.

625
00:48:23,210 --> 00:48:26,510
De asemenea, nu puteți dequeue orice, de la o coadă dacă e goală.

626
00:48:26,510 --> 00:48:30,420
Care este primul lucru pe care ar trebui să facem, în funcție de dequeue noastră aici, nu crezi?

627
00:48:30,420 --> 00:48:33,860
[Saad] Dacă dimensiunea este mai mare decât 0? Da >>.

628
00:48:33,860 --> 00:48:37,710
În acest caz, am de fapt doar testat pentru a vedea dacă acesta este 0.

629
00:48:37,710 --> 00:48:42,240
În cazul în care este 0, putem intoarce null.

630
00:48:42,240 --> 00:48:45,280
Dar exact aceeași logică.

631
00:48:45,280 --> 00:48:49,110
Și să continuăm cu asta.

632
00:48:49,110 --> 00:48:54,600
În cazul în care dimensiunea nu este 0, în cazul în care este elementul pe care dorim să dequeue?

633
00:48:54,600 --> 00:48:58,550
[Saad] La cap? Exact >>.

634
00:48:58,550 --> 00:49:01,720
Putem trage doar din primul element din coada noastră

635
00:49:01,720 --> 00:49:07,040
prin accesarea element la cap.

636
00:49:07,040 --> 00:49:14,630
Nebun nimic.

637
00:49:14,630 --> 00:49:19,620
După aceea, ceea ce ar trebui să facem? Ce are să se întâmple?

638
00:49:19,620 --> 00:49:23,740
Care a fost alt lucru despre care am vorbit în dequeue?

639
00:49:23,740 --> 00:49:28,130
Două lucruri trebuie să se întâmple, pentru că coada noastră sa schimbat.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reducerea dimensiunii. Avem >> pentru a reduce dimensiunea, și de a crește cap? Exact.

641
00:49:35,640 --> 00:49:40,600
Pentru a crește cap, nu putem pur și simplu crește orbește cap, minte.

642
00:49:40,600 --> 00:49:45,080
Noi nu doar putem face queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Trebuie să includă, de asemenea, acest mod de capacitate.

644
00:49:51,630 --> 00:49:54,740
Și de ce nu am modez de capacitate, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Pentru că trebuie să-și încheie în jurul valorii de. Exact >>.

646
00:49:58,680 --> 00:50:04,750
Am Mod de capacitatea pentru că are să-și încheie în jurul valorii de înapoi la 0.

647
00:50:04,750 --> 00:50:07,400
Deci, acum, în acest moment, putem face ceea ce a spus Daniel.

648
00:50:07,400 --> 00:50:12,700
Putem descreste marimea.

649
00:50:12,700 --> 00:50:29,170
Și apoi ne putem întoarce pur și simplu elementul de care a fost la partea de sus a cozii.

650
00:50:29,170 --> 00:50:34,000
Se pare un fel de noduros la început. S-ar putea avea o întrebare. Ne pare rău?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] De ce e mai întâi la partea de sus a cozii? În cazul în care nu a mers?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Ea vine de la patra linie din partea de jos.

653
00:50:42,480 --> 00:50:46,060
După ce am testat pentru a se asigura că coada noastră nu este gol,

654
00:50:46,060 --> 00:50:54,100
am scoate char * în primul rând, am scoate elementul care stă la indicele de cap

655
00:50:54,100 --> 00:50:58,680
de matrice noastre, a noastra matrice siruri de caractere, >> și apelul pe care mai întâi?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Și noi numim prima. Da.

657
00:51:04,500 --> 00:51:09,850
Doar pentru a urmări asta, de ce crezi că am avut de a face asta?

658
00:51:09,850 --> 00:51:18,270
[Sam] Fiecare primul se întoarce doar q.strings [q.head]? Da >>.

659
00:51:18,270 --> 00:51:23,830
Deoarece >> facem asta schimbare de q.head cu funcția mod,

660
00:51:23,830 --> 00:51:27,810
și nu există nici o modalitate de a face acest lucru în termen de retur, de asemenea,.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Exact. Ești la fața locului. Sam e la fața locului în totalitate pe.

662
00:51:31,640 --> 00:51:36,800
Motivul pentru care a trebuit să scot primul element din coada noastră și depozitați-l într-o variabilă

663
00:51:36,800 --> 00:51:43,030
se datorează faptului că această linie în cazul în care am avut doar q.head,

664
00:51:43,030 --> 00:51:47,030
nu e operatorului mod acolo nu este ceva ce putem face

665
00:51:47,030 --> 00:51:51,230
și l-au produce efecte de la cap, fără a - într-o singură linie.

666
00:51:51,230 --> 00:51:54,480
Deci, avem de fapt de a scoate primul element, apoi ajustați capul,

667
00:51:54,480 --> 00:52:00,430
ajusta dimensiunea, și a reveni apoi elementul pe care am scos.

668
00:52:00,430 --> 00:52:02,680
Și acest lucru este ceva pe care le vom vedea mai târziu, veni cu

669
00:52:02,680 --> 00:52:04,920
Lista de preturi legate, după cum am juca în jurul valorii de cu ei.

670
00:52:04,920 --> 00:52:08,410
De multe ori atunci când sunteți eliberarea sau eliminare a listelor legate de

671
00:52:08,410 --> 00:52:13,500
aveți nevoie să vă amintiți urmatorul element, indicatorul următoare a unei liste legate

672
00:52:13,500 --> 00:52:16,330
înainte de a înstrăina actual.

673
00:52:16,330 --> 00:52:23,580
Pentru că altfel vă aruncați informații a ceea ce a mai rămas din lista.

674
00:52:23,580 --> 00:52:34,160
Acum, dacă te duci la aparatul dumneavoastră, deschideți-queue.c-x din asta.

675
00:52:34,160 --> 00:52:39,390
Deci, dacă am deschide queue.c, lasă-mă să mări aici,

676
00:52:39,390 --> 00:52:44,970
veți vedea că aveți un fișier cu aspect asemănător.

677
00:52:44,970 --> 00:52:49,200
Similar cu aspect fișier la ceea ce am avut mai devreme, cu stack.c.

678
00:52:49,200 --> 00:52:54,690
Avem struct nostru pentru coada de definit așa cum am văzut-o pe slide-uri.

679
00:52:54,690 --> 00:52:59,870
>> Avem funcția noastră Puneți în coadă, care este pentru tine să faci.

680
00:52:59,870 --> 00:53:04,340
Și avem funcția dequeue aici.

681
00:53:04,340 --> 00:53:06,870
Funcția dequeue în fișier este pusă în aplicare,

682
00:53:06,870 --> 00:53:13,230
dar voi pune înapoi pe PowerPoint, astfel încât puteți să-l introduceți în, dacă doriți.

683
00:53:13,230 --> 00:53:16,690
Deci, pentru următorii 5 minute sau cam asa ceva, voi lucra la Puneți în coadă

684
00:53:16,690 --> 00:53:22,570
care este aproape opusul a dequeue.

685
00:53:22,570 --> 00:53:29,560
Nu trebuie să se adapteze cap cand esti enqueueing, dar ceea ce nu trebuie să se adapteze?

686
00:53:29,560 --> 00:53:38,920
Dimensiunea. Deci, atunci când Puneți în coadă, capul rămâne neatins, dimensiunea devine schimbat.

687
00:53:38,920 --> 00:53:46,920
Dar aceasta nu ia un pic de - va trebui să joace în jurul valorii de cu mod

688
00:53:46,920 --> 00:53:57,560
să dau seama exact ce indicele element nou ar trebui să fie introdus la.

689
00:53:57,560 --> 00:54:03,080
Deci, voi da voi un pic, pus din nou pe dequeue diapozitiv,

690
00:54:03,080 --> 00:54:05,200
și, ca voi aveti intrebari, le strig, astfel încât să putem

691
00:54:05,200 --> 00:54:09,220
toate vorbesc despre ele ca un grup.

692
00:54:09,220 --> 00:54:13,960
De asemenea, cu dimensiunea nu - atunci când reglați dimensiunea, poți întotdeauna doar -

693
00:54:13,960 --> 00:54:18,720
aveți să mod dimensiunea vreodată? [Daniel] Nu >> Nu trebuie să mod mărimea, dreapta.

694
00:54:18,720 --> 00:54:24,260
Deoarece dimensiunea va fi întotdeauna, dacă Esti - presupunând că sunteți de gestionare lucruri în mod corespunzător,

695
00:54:24,260 --> 00:54:30,840
dimensiunea va fi întotdeauna între 0 și 3.

696
00:54:30,840 --> 00:54:38,680
În cazul în care aveți să mod atunci când faci Puneți în coadă?

697
00:54:38,680 --> 00:54:41,060
[Student] Numai pentru cap. Numai >> pentru cap, exact.

698
00:54:41,060 --> 00:54:44,620
Și de ce trebuie să mod deloc în Puneți în coadă?

699
00:54:44,620 --> 00:54:48,830
Atunci când este o situație în care ar trebui să mod?

700
00:54:48,830 --> 00:54:53,630
[Student] Dacă aveți lucruri la spații, ca la spațiile 1 și 2,

701
00:54:53,630 --> 00:54:55,950
si apoi ai nevoie pentru a adăuga ceva la 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Da, exact. Deci, în cazul în care indicatorul este capul de la sfârșitul foarte,

703
00:55:02,570 --> 00:55:14,210
sau în cazul în care dimensiunea plus capul este mai mare, sau mai degrabă, se va incheia in jurul cozii.

704
00:55:14,210 --> 00:55:17,830
>> Deci, în această situație, faptul că avem aici pe diapozitiv chiar acum,

705
00:55:17,830 --> 00:55:24,370
dacă vreau să redați ceva chiar acum,

706
00:55:24,370 --> 00:55:31,110
vrem să redați ceva la index 0.

707
00:55:31,110 --> 00:55:35,450
Deci, dacă vă uitați la care merge 50, si eu sun Puneți în coadă 50,

708
00:55:35,450 --> 00:55:40,840
se duce acolo, la partea de jos. Se merge in 0 index.

709
00:55:40,840 --> 00:55:44,160
Acesta înlocuiește "hi", care a fost deja dequeued.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Nu ai grijă de faptul că, în dequeue deja?

711
00:55:46,210 --> 00:55:50,550
De ce nu-l face nimic cu capul în Puneți în coadă?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, deci nu ești modificarea cap, îmi pare rău.

713
00:55:55,770 --> 00:56:02,310
Dar trebuie să utilizați operatorul mod atunci când accesați

714
00:56:02,310 --> 00:56:04,250
elementul pe care doriți să o redați atunci când accesați

715
00:56:04,250 --> 00:56:06,960
elementul următor din lista de așteptare.

716
00:56:06,960 --> 00:56:10,960
[Vasile] n-am făcut asta, și m-am "succes" pe acolo.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, înțeleg ce vrei să spui.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Deci tu didn't - ai făcut la q.size?

719
00:56:16,240 --> 00:56:20,670
[Vasile] Da. Am schimbat doar fete, nu am făcut nimic cu cap.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Nu trebuie de fapt, pentru a reseta cap să fie ceva,

721
00:56:24,300 --> 00:56:31,650
dar atunci când indicele în matrice siruri de caractere,

722
00:56:31,650 --> 00:56:39,500
de fapt trebuie să mergeți mai departe și se calculează în cazul în care elementul următor este,

723
00:56:39,500 --> 00:56:44,230
deoarece lozie stivă, elementul următor în stiva a fost întotdeauna

724
00:56:44,230 --> 00:56:48,740
la indicele corespunzător dimensiunea.

725
00:56:48,740 --> 00:56:55,850
Dacă ne uităm înapoi la funcția noastră împinge stivă,

726
00:56:55,850 --> 00:57:03,100
am putea plunk mereu în elementul nostru nou dreptul la dimensiunea index.

727
00:57:03,100 --> 00:57:06,710
Întrucât, cu coada, nu putem face asta

728
00:57:06,710 --> 00:57:10,340
pentru că dacă suntem la această situație,

729
00:57:10,340 --> 00:57:18,130
dacă ne enqueued 50 nostru nou șir ar merge chiar la siruri de caractere [1]

730
00:57:18,130 --> 00:57:20,540
care noi nu vreau să fac.

731
00:57:20,540 --> 00:57:41,200
Ne dorim să avem șirul noua du-te la indicele 0.

732
00:57:41,200 --> 00:57:44,320
>> Are cineva - da? [Student] Am o întrebare, dar nu e chiar rude.

733
00:57:44,320 --> 00:57:48,160
Ce înseamnă atunci când cineva solicită doar ceva ca indicatorul pred?

734
00:57:48,160 --> 00:57:51,260
Care este acest nume scurt pentru? Știu că e doar un nume.

735
00:57:51,260 --> 00:57:59,110
[Hardison] indicatorul Pred? Să vedem. În ce context?

736
00:57:59,110 --> 00:58:01,790
[Student] A fost pentru inserare. Pot să vă întreb mai târziu, dacă doriți

737
00:58:01,790 --> 00:58:03,920
pentru că nu e într-adevăr legate, dar eu doar -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Din cod lui David se introduce de la curs?

739
00:58:07,300 --> 00:58:10,860
Putem trage în sus și faptul că vorbesc despre asta.

740
00:58:10,860 --> 00:58:15,550
Vom vorbi despre asta viitoare, odată ce vom ajunge la liste legate.

741
00:58:15,550 --> 00:58:21,440
>> Deci, haideți să uite foarte repede la ceea ce arata ca functia Puneți în coadă.

742
00:58:21,440 --> 00:58:26,530
Care a fost primul lucru pe care oamenii au încercat să facă în linia ta Puneți în coadă? În această coadă?

743
00:58:26,530 --> 00:58:29,960
Similar cu ceea ce ai făcut pentru stiva de împingere.

744
00:58:29,960 --> 00:58:32,080
Ce-ai făcut, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, neinteligibil]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Exact. În cazul în care (q.size == capacitate) -

747
00:58:45,700 --> 00:58:54,720
Am nevoie pentru a pune aparat dentar mele în locul potrivit - return false.

748
00:58:54,720 --> 00:59:01,370
Mări un pic. Bine.

749
00:59:01,370 --> 00:59:03,800
Acum, ce e urmatorul lucru pe care am avut de a face?

750
00:59:03,800 --> 00:59:11,370
La fel ca și cu stiva, și introduc la locul potrivit.

751
00:59:11,370 --> 00:59:16,010
Și deci ce era locul potrivit pentru a insera asta?

752
00:59:16,010 --> 00:59:23,170
Cu stiva a fost dimensiunea index, cu aceasta nu e chiar asa.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Am q.head-sau-- q.strings >>? Da >>.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod CAPACITATE]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Noi, probabil, doriți să puneți paranteze în jurul valorii de această

756
00:59:42,740 --> 00:59:48,830
astfel încât să ne apropiem corespunzătoare prioritate și, astfel încât este cleart pentru toată lumea.

757
00:59:48,830 --> 00:59:55,800
Și a stabilit care sunt egale? Pentru >> str.? Pentru >> Str. Mare.

758
00:59:55,800 --> 01:00:00,160
Și acum, ce e ultimul lucru pe care trebuie să facem?

759
01:00:00,160 --> 01:00:06,780
La fel cum am facut-o in stiva. Increment >> dimensiunea? Increment >> dimensiunea.

760
01:00:06,780 --> 01:00:13,830
Boom. Și apoi, din moment codul de pornire tocmai sa întors de fals în mod implicit,

761
01:00:13,830 --> 01:00:27,460
vrem să schimbăm acest lucru adevărat, dacă totul merge prin intermediul și totul merge bine.

762
01:00:27,460 --> 01:00:33,050
Bine. Aceasta este o mulțime de informații pentru secțiunea.

763
01:00:33,050 --> 01:00:39,480
Noi nu suntem destul de peste. Vrem să vorbim despre foarte repede singure legate de preturi.

764
01:00:39,480 --> 01:00:44,010
Voi pune asta ca să putem reveni la ea mai târziu.

765
01:00:44,010 --> 01:00:50,850
Dar haideți să ne întoarcem la prezentarea noastra pentru doar câteva mai multe diapozitive.

766
01:00:50,850 --> 01:00:53,790
Deci Puneți în coadă este TODO, acum l-am făcut.

767
01:00:53,790 --> 01:00:57,430
>> Acum, haideți să aruncăm o privire la individual-linked liste.

768
01:00:57,430 --> 01:01:00,040
Am vorbit despre acestea mai mult un pic în curs.

769
01:01:00,040 --> 01:01:02,540
Câți dintre voi au văzut demo-ul în cazul în care am avut oameni

770
01:01:02,540 --> 01:01:08,220
neîndemânatic arătând spre fiecare alte numere și deținerea? >> Am fost în asta.

771
01:01:08,220 --> 01:01:16,620
>> Ce voi credeți? Credeți că, demistificarea Sperăm că aceste pic un pic?

772
01:01:16,620 --> 01:01:25,990
Cu o listă, se pare că avem de a face cu acest tip de pe care vom apela un nod.

773
01:01:25,990 --> 01:01:32,520
Întrucât, cu coada si stiva am avut struct că vom numim coada în stivă,

774
01:01:32,520 --> 01:01:34,860
am avut aceste tipuri de coada nou în coșul de fum,

775
01:01:34,860 --> 01:01:39,240
aici o listă este într-adevăr doar alcătuit dintr-un grup de noduri.

776
01:01:39,240 --> 01:01:45,920
În același mod în care siruri de caractere sunt doar o adunatura de caractere toate aliniate una lângă alta.

777
01:01:45,920 --> 01:01:50,650
O listă legată este doar un nod și un alt nod și un alt nod și un alt nod.

778
01:01:50,650 --> 01:01:55,080
Și, mai degrabă decât zdrobitor toate nodurile împreună și stocarea lor contiguously

779
01:01:55,080 --> 01:01:58,090
regulă lângă altul în memorie,

780
01:01:58,090 --> 01:02:04,470
având în acest pointer lângă ne permite să stocați noduri ori de câte ori, în mod aleatoriu.

781
01:02:04,470 --> 01:02:10,500
Și apoi un fel de sârmă-le pe toate împreună pentru a indica de la una la alta.

782
01:02:10,500 --> 01:02:15,850
>> Și ce a fost marele avantaj că aceasta a avut mai mult de o matrice?

783
01:02:15,850 --> 01:02:21,680
Peste tot stocarea contiguously doar lipite unul lângă celălalt?

784
01:02:21,680 --> 01:02:24,190
Îți amintești? Da? >> Alocare dinamică a memoriei?

785
01:02:24,190 --> 01:02:27,220
>> Alocare dinamică a memoriei, în ce sens?

786
01:02:27,220 --> 01:02:31,780
[Student] În această puteți să vă păstrați acest site este mai mare și nu trebuie să se mute matrice întregul dvs.?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Exact. Deci, cu o matrice, atunci când doriți să puneți un element nou în mijlocul ei,

788
01:02:40,940 --> 01:02:45,320
va trebui să treacă totul pentru a face loc.

789
01:02:45,320 --> 01:02:47,880
Și ca și cum am vorbit despre cu coada,

790
01:02:47,880 --> 01:02:50,080
de aceea ținem că indicatorul cap,

791
01:02:50,080 --> 01:02:52,050
astfel încât să nu ne schimbă în mod constant lucruri.

792
01:02:52,050 --> 01:02:54,520
Pentru că devine scump, dacă v-ați luat-o matrice mare

793
01:02:54,520 --> 01:02:57,130
și ce faci în mod constant aceste insertii aleatorii.

794
01:02:57,130 --> 01:03:00,820
Întrucât, cu o listă, tot ce trebuie să faceți este să arunce pe un nou nod,

795
01:03:00,820 --> 01:03:06,330
ajusta indicii, și ați terminat.

796
01:03:06,330 --> 01:03:10,940
Ce e de rahat despre asta?

797
01:03:10,940 --> 01:03:16,830
În afară de faptul că nu este la fel de ușor de a lucra cu ca o matrice? Da?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Ei bine, cred că e mult mai greu de a accesa un element specific în lista de legat?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Nu poti sari doar la un element arbitrar în mijlocul listei legate.

800
01:03:30,470 --> 01:03:33,800
Cum trebuie să-l facem schimb? >> Trebuie să pas prin întregul lucru.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Da. Trebuie să treacă printr-o la un moment dat, unul la un moment dat.

802
01:03:35,660 --> 01:03:38,480
E un imens - este o durere.

803
01:03:38,480 --> 01:03:41,550
Care e celălalt - există un alt căderea în acest sens.

804
01:03:41,550 --> 01:03:45,340
[Vasile] Nu poți merge înainte și înapoi? Trebuie să mergi o singură direcție?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Da. Deci, cum putem rezolva asta, uneori?

806
01:03:48,570 --> 01:03:53,370
[Vasile] dublu-legate de preturi? Exact >>. Există liste dublu-legate.

807
01:03:53,370 --> 01:03:55,540
Există, de asemenea, - pare rau?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] E la fel ca utilizarea lucru pe care pred -

809
01:03:57,620 --> 01:04:01,090
Mi-am amintit, nu este faptul că ceea ce este chestia pred pentru?

810
01:04:01,090 --> 01:04:05,850
Nu este faptul că, în perioada de două ori și individual?

811
01:04:05,850 --> 01:04:10,020
[Hardison] Să ne uităm la ce anume făcea.

812
01:04:10,020 --> 01:04:15,760
Deci, aici vom merge. Iată lista codurilor.

813
01:04:15,760 --> 01:04:25,620
Aici avem predptr, aici. Asta e ceea ce a fost vorba?

814
01:04:25,620 --> 01:04:30,750
Deci asta a fost - el eliberarea o listă și încearcă pentru a stoca un pointer la el.

815
01:04:30,750 --> 01:04:35,000
Acest lucru nu este de două ori, exemplare individuale legate de liste de.

816
01:04:35,000 --> 01:04:40,090
Putem vorbi mai multe despre aceasta mai târziu, deoarece acest lucru este vorba despre eliberarea lista

817
01:04:40,090 --> 01:04:42,900
și vreau să arate alte lucruri mai întâi.

818
01:04:42,900 --> 01:04:51,480
dar e doar - e amintindu valoarea PTR

819
01:04:51,480 --> 01:04:54,170
[Student] Oh, e indicatorul precedenta? Da >>.

820
01:04:54,170 --> 01:05:04,070
Astfel încât să putem incrementa apoi ptr el însuși înainte de a ne apoi liber ceea ce este predptr.

821
01:05:04,070 --> 01:05:09,130
Pentru că nu putem gratuit ptr si apoi suna ptr = ptr viitoare, nu?

822
01:05:09,130 --> 01:05:11,260
Asta ar fi rău.

823
01:05:11,260 --> 01:05:20,940
Deci, hai sa vedem, înapoi la tipul ăsta.

824
01:05:20,940 --> 01:05:23,900
>> Un alt lucru rău despre preturi este că în timp ce cu o matrice

825
01:05:23,900 --> 01:05:26,520
avem doar toate elementele s-au stivuite unul lângă altul,

826
01:05:26,520 --> 01:05:29,050
aici am, de asemenea, au introdus acest indicator.

827
01:05:29,050 --> 01:05:34,060
Deci, există o bucată suplimentară de memorie pe care avem de a utiliza

828
01:05:34,060 --> 01:05:37,910
pentru fiecare element care ne stocarea în lista noastră.

829
01:05:37,910 --> 01:05:40,030
Primim flexibilitate, dar vine la un cost.

830
01:05:40,030 --> 01:05:42,230
Acesta este dotat cu acest cost de timp,

831
01:05:42,230 --> 01:05:45,270
și vine cu acest cost de memorie prea.

832
01:05:45,270 --> 01:05:47,800
Timpul în sensul că acum trebuie să treacă prin fiecare element în matrice

833
01:05:47,800 --> 01:05:58,670
pentru a găsi cea de la indexul 10, sau că ar fi fost indexurile 10 într-o matrice.

834
01:05:58,670 --> 01:06:01,230
>> Doar foarte repede, atunci când diagrama aceste liste,

835
01:06:01,230 --> 01:06:05,980
de obicei ne ținem pe cap de listă sau indicatorul prima listă

836
01:06:05,980 --> 01:06:08,010
și rețineți că acest lucru este un pointer adevărat.

837
01:06:08,010 --> 01:06:11,100
E doar 4 octeți. Acesta nu e un nod în sine.

838
01:06:11,100 --> 01:06:17,120
Deci, vedeți că nu are nici o valoare int în ea, nici indicatorul viitoare în ea.

839
01:06:17,120 --> 01:06:20,790
E literalmente doar un pointer.

840
01:06:20,790 --> 01:06:23,550
O să indice ceva care este un nod struct real.

841
01:06:23,550 --> 01:06:28,480
[Sam] Un indicator numit nod? Acest lucru este >> - nu. Acesta este un pointer la ceva de tip nod.

842
01:06:28,480 --> 01:06:32,540
Acesta este un pointer la un nod struct. >> Oh, bine.

843
01:06:32,540 --> 01:06:36,870
Diagrama pe codul de stânga, în dreapta.

844
01:06:36,870 --> 01:06:42,190
Ne putem seta la nul, care este o modalitate buna de a incepe.

845
01:06:42,190 --> 01:06:49,850
Când o diagramă, scrii, fie ca nul sau ai pus o linie prin ea place asta.

846
01:06:49,850 --> 01:06:53,910
>> Una dintre cele mai simple moduri de a lucra cu liste,

847
01:06:53,910 --> 01:06:57,430
și vă cerem nu atât PREFIX și adăugați pentru a vedea diferențele dintre cele două,

848
01:06:57,430 --> 01:07:01,320
dar este cu siguranta mai usor precedarea.

849
01:07:01,320 --> 01:07:05,790
Când prefixului, acest lucru este în cazul în care - atunci cand PREFIX (7),

850
01:07:05,790 --> 01:07:10,050
te duci și de a crea struct nod

851
01:07:10,050 --> 01:07:13,870
și vă configurați mai întâi la punctul la ea, pentru că acum, de când l-am prefixate,

852
01:07:13,870 --> 01:07:17,240
o să fie la începutul listei.

853
01:07:17,240 --> 01:07:22,540
Dacă ne PREFIX (3), care creează un alt nod, dar acum 3 vine înainte de 7.

854
01:07:22,540 --> 01:07:31,130
Deci, suntem în esență, împingând lucrurile pe lista noastră.

855
01:07:31,130 --> 01:07:34,720
Acum, puteți vedea că PREFIX, uneori, oamenii o numesc împinge,

856
01:07:34,720 --> 01:07:39,600
pentru ca esti împingând un element nou pe lista ta.

857
01:07:39,600 --> 01:07:43,270
Este, de asemenea, ușor pentru a șterge în fața unei liste.

858
01:07:43,270 --> 01:07:45,650
Deci, oamenii vor apela adesea că pop.

859
01:07:45,650 --> 01:07:52,200
Și în acest fel, aveți posibilitatea să emuleze o stivă utilizând o listă legată.

860
01:07:52,200 --> 01:07:57,880
Hopa. Ne pare rău, acum ne băgăm de adăugare. Deci, aici am prefixate (7), acum ne PREFIX (3).

861
01:07:57,880 --> 01:08:02,600
Dacă ne prefixate altceva pe această listă, în cazul în care vom prefixate (4),

862
01:08:02,600 --> 01:08:06,540
atunci vom avea 4 și apoi 3 și apoi 7.

863
01:08:06,540 --> 01:08:14,220
Deci, atunci am putea pop și scoateți 4, îndepărtați 3, scoateți 7.

864
01:08:14,220 --> 01:08:16,500
Adesea mod mai intuitiv să se gândească la acest lucru este cu adăugare.

865
01:08:16,500 --> 01:08:20,310
Așa că m-am diagrama ce ar arata cu adăugați aici.

866
01:08:20,310 --> 01:08:23,380
Aici, anexate (7) nu arata diferit

867
01:08:23,380 --> 01:08:25,160
pentru că nu există decât un singur element din listă.

868
01:08:25,160 --> 01:08:28,620
Și anexarea (3) îl pune la sfârșitul anului.

869
01:08:28,620 --> 01:08:31,020
Poate puteți vedea chiar acum truc cu append

870
01:08:31,020 --> 01:08:36,600
este că, deoarece știm numai în cazul în care la începutul listei este,

871
01:08:36,600 --> 01:08:39,450
pentru a adăuga la o listă, trebuie să meargă tot drumul prin lista de

872
01:08:39,450 --> 01:08:46,500
pentru a ajunge la final, opri, apoi nodul construi dvs. și tot ce Plunk jos.

873
01:08:46,500 --> 01:08:50,590
Legați toate lucrurile sus.

874
01:08:50,590 --> 01:08:55,170
Deci, cu PREFIX, așa cum ne-am rupt prin acest foarte repede,

875
01:08:55,170 --> 01:08:58,170
Atunci când adauge la o listă, e destul de simplu.

876
01:08:58,170 --> 01:09:02,960
>> Ai face nod nou, implica o anumită alocare de memorie dinamică.

877
01:09:02,960 --> 01:09:09,830
Deci, aici vom face o struct nod folosind malloc.

878
01:09:09,830 --> 01:09:14,710
Deci, suntem folosind malloc, pentru că vom retrase din circuitul agricol de memorie pentru noi pentru mai târziu

879
01:09:14,710 --> 01:09:20,350
pentru că nu vrem acest lucru - vrem această memorie să persiste pentru o lungă perioadă de timp.

880
01:09:20,350 --> 01:09:25,350
Și vom obține un pointer la spațiu în memorie pe care tocmai l-am alocat.

881
01:09:25,350 --> 01:09:29,260
Noi folosim dimensiunea nod, nu ne rezuma câmpurile.

882
01:09:29,260 --> 01:09:31,899
Noi nu generează manual numărul de octeți,

883
01:09:31,899 --> 01:09:39,750
în schimb vom folosi sizeof, astfel încât să știm că vei primi un număr corespunzător de octeți.

884
01:09:39,750 --> 01:09:43,660
Suntem asigurați-vă că pentru a testa apelul nostru malloc reușit.

885
01:09:43,660 --> 01:09:47,939
Acest lucru este ceva ce vrei să faci, în general.

886
01:09:47,939 --> 01:09:52,590
Pe mașinile moderne, în criză de memorie nu este ceva care e ușor

887
01:09:52,590 --> 01:09:56,610
daca nu esti alocarea o grămadă de lucruri și de a face o listă uriașă,

888
01:09:56,610 --> 01:10:02,220
dar dacă sunteți construirea chestii pentru, să zicem, cum ar fi un iPhone sau un Android,

889
01:10:02,220 --> 01:10:05,230
veți face dispun de resurse limitate de memorie, mai ales dacă faci ceva intens.

890
01:10:05,230 --> 01:10:08,300
Deci, este bine pentru a obține în practică.

891
01:10:08,300 --> 01:10:10,510
>> Observați că am folosit un cuplu funcții diferite aici

892
01:10:10,510 --> 01:10:12,880
pe care le-ați văzut că sunt un fel de noi.

893
01:10:12,880 --> 01:10:15,870
Deci, fprintf este la fel ca printf

894
01:10:15,870 --> 01:10:21,320
cu excepția primul argument este fluxul la care doriți să imprimați.

895
01:10:21,320 --> 01:10:23,900
În acest caz, dorim să imprimați șirul eroarea standard

896
01:10:23,900 --> 01:10:29,410
care este diferit de OutStream standard.

897
01:10:29,410 --> 01:10:31,620
În mod implicit se arată în același loc.

898
01:10:31,620 --> 01:10:34,600
Este, de asemenea, imprimă la terminalul, dar poți -

899
01:10:34,600 --> 01:10:38,790
folosind aceste comenzi ați învățat despre tehnicile de redirecționare,

900
01:10:38,790 --> 01:10:42,290
ați învățat despre în filme lui Tommy pentru set de probleme 4, puteți să-l direcționeze

901
01:10:42,290 --> 01:10:47,900
pentru diferite domenii; ieși, apoi, chiar aici, iese programul tău.

902
01:10:47,900 --> 01:10:50,440
E ca și cum, în esență se întorc din principal,

903
01:10:50,440 --> 01:10:53,600
cu excepția vom folosi de ieșire, deoarece aici revenirea nu va face nimic.

904
01:10:53,600 --> 01:10:57,140
Noi nu suntem în principal, astfel încât să nu ieși revenind program ca vrem.

905
01:10:57,140 --> 01:11:03,020
Deci, vom folosi funcția de ieșire și dau un cod de eroare.

906
01:11:03,020 --> 01:11:11,890
Atunci ne-am stabilit aici domeniu nou nod de valoare, câmpul I să fie egal cu I, iar apoi l-am sârmă sus.

907
01:11:11,890 --> 01:11:15,530
Am stabilit indicatorul noul nod de pe lângă punctul la primul,

908
01:11:15,530 --> 01:11:20,460
și apoi primul va indica acum la nod nou.

909
01:11:20,460 --> 01:11:25,120
Aceste linii de cod prima, suntem de fapt, construirea unui nod nou.

910
01:11:25,120 --> 01:11:27,280
Nu în ultimul două linii de această funcție, dar primele.

911
01:11:27,280 --> 01:11:30,290
Puteți trage efectiv într-o funcție, într-o funcție de ajutor.

912
01:11:30,290 --> 01:11:32,560
Asta e ceea ce fac eu de multe ori e, l-am scoate într-o funcție,

913
01:11:32,560 --> 01:11:36,040
Eu îi spun ceva de genul nod construi,

914
01:11:36,040 --> 01:11:40,410
și că păstrează funcția PREFIX destul de mic, e la doar 3 linii de atunci.

915
01:11:40,410 --> 01:11:48,710
Fac un apel la funcția mea nod construi, iar apoi m-am tot sârmă sus.

916
01:11:48,710 --> 01:11:51,970
>> Ultimul lucru vreau să-ți arăt,

917
01:11:51,970 --> 01:11:54,030
și voi lăsa să faci de adăugare și tot ce pe cont propriu,

918
01:11:54,030 --> 01:11:57,500
este cum să itera peste o listă.

919
01:11:57,500 --> 01:12:00,780
Există o grămadă de moduri diferite de a itera peste o listă.

920
01:12:00,780 --> 01:12:03,140
În acest caz, vom găsi lungimea unei liste.

921
01:12:03,140 --> 01:12:06,570
Deci, vom începe cu o lungime = 0.

922
01:12:06,570 --> 01:12:11,580
Acest lucru este foarte similar cu scrierea strlen pentru un șir.

923
01:12:11,580 --> 01:12:17,780
Aceasta este ceea ce vreau să vă arăt, asta pentru bucla chiar aici.

924
01:12:17,780 --> 01:12:23,530
Se pare cam înfricoșat, ea nu e obișnuită int i = 0, i <indiferent, i + +.

925
01:12:23,530 --> 01:12:34,920
În schimb se inițializează variabila n noastră de a fi începutul listei.

926
01:12:34,920 --> 01:12:40,620
Și apoi în timp ce variabila noastră iterator nu este nul, vom continua.

927
01:12:40,620 --> 01:12:46,340
Acest lucru se datorează faptului că, prin convenție, la sfârșitul listei noastre va fi nulă.

928
01:12:46,340 --> 01:12:48,770
Și apoi să incrementeze, mai degrabă decât a face + +,

929
01:12:48,770 --> 01:12:57,010
echivalentul lista legată de + + este n = n-> urmator.

930
01:12:57,010 --> 01:13:00,410
>> Te las să umple golurile de aici pentru că nu mai avem timp.

931
01:13:00,410 --> 01:13:09,300
Dar ține minte acest lucru în timp ce lucra la psets spellr tale.

932
01:13:09,300 --> 01:13:11,650
Lista de preturi legate, dacă punerea în aplicare a unui tabel hash,

933
01:13:11,650 --> 01:13:14,010
vor veni cu siguranță în foarte la îndemână.

934
01:13:14,010 --> 01:13:21,780
Și având această expresie pentru looping peste lucrurile se vor face viața mult mai ușoară, să sperăm.

935
01:13:21,780 --> 01:13:25,910
Orice întrebări, repede?

936
01:13:25,910 --> 01:13:28,920
[Sam] Va voi trimite SLL completat și sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Da. Voi trimite slide-uri completate și stiva SLL completat și queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]