1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:11,137 [REPRODUCCIÓ DE MÚSICA] 3 00:00:11,137 --> 00:00:12,220 DAVID J. Malan: Molt bé. 4 00:00:12,220 --> 00:00:13,950 Això és CS50. 5 00:00:13,950 --> 00:00:18,560 Aquesta és la cinquena setmana va continuar, i ens tenir algunes bones notícies i males notícies. 6 00:00:18,560 --> 00:00:21,140 Així que bona notícia és que CS50 llança aquest divendres. 7 00:00:21,140 --> 00:00:24,430 Si vol unir-se a nosaltres, dirigir-se a l'adreça URL habitual aquí. 8 00:00:24,430 --> 00:00:28,670 Encara millor notícia, sense conferència dilluns 13. 9 00:00:28,670 --> 00:00:31,970 Una mica menys millors notícies, qüestionari de zero és dimecres que ve. 10 00:00:31,970 --> 00:00:33,840 Més detalls poden ser trobat en aquest URL aquí. 11 00:00:33,840 --> 00:00:36,340 I en els pròxims dies estarem omplint els espais en blanc 12 00:00:36,340 --> 00:00:39,234 pel que fa a les habitacions que haurem reservat. 13 00:00:39,234 --> 00:00:41,400 Millor notícia és que no vaig a ser un examen de tot el curs 14 00:00:41,400 --> 00:00:43,570 sessió el proper Dilluns a la nit. 15 00:00:43,570 --> 00:00:46,270 Estiguin atents al curs de lloc web per a la ubicació i detalls. 16 00:00:46,270 --> 00:00:49,290 Seccions, tot i que és un dia de festa, també es reunirà també. 17 00:00:49,290 --> 00:00:50,490 18 00:00:50,490 --> 00:00:52,940 Millors notícies, conferència divendres que ve. 19 00:00:52,940 --> 00:00:56,220 Així que aquesta és una tradició que tenir, segons el pla d'estudis. 20 00:00:56,220 --> 00:00:58,100 Sol-- que serà increïble. 21 00:00:58,100 --> 00:01:02,510 Vostè veurà coses com estructures de dades de temps constant 22 00:01:02,510 --> 00:01:04,730 i taules i arbres i tries de patata. 23 00:01:04,730 --> 00:01:07,150 I anem a parlar dels problemes d'aniversari. 24 00:01:07,150 --> 00:01:09,440 Un munt de coses espera divendres que ve. 25 00:01:09,440 --> 00:01:11,212 26 00:01:11,212 --> 00:01:12,200 Okay. 27 00:01:12,200 --> 00:01:13,190 De totes maneres. 28 00:01:13,190 --> 00:01:17,080 >> Així recordem que hem estat centrant-se en la imatge del que està 29 00:01:17,080 --> 00:01:18,980 dins de la memòria del nostre ordinador. 30 00:01:18,980 --> 00:01:22,875 Així, la memòria o la memòria RAM és on els programes existint mentre vostè els està corrent. 31 00:01:22,875 --> 00:01:25,215 Si feu doble clic a una icona per executar algun programa 32 00:01:25,215 --> 00:01:27,520 o feu doble clic en un icona per obrir algun arxiu, 33 00:01:27,520 --> 00:01:30,430 està carregada del seu disc conduir o unitat d'estat sòlid 34 00:01:30,430 --> 00:01:34,190 a la memòria RAM, memòria d'accés aleatori, on viu fins que es desconnecti l'alimentació, 35 00:01:34,190 --> 00:01:36,700 la tapa del portàtil es tanca, o sortir del programa. 36 00:01:36,700 --> 00:01:38,960 >> Ara que la memòria, de que és probable que tingui 37 00:01:38,960 --> 00:01:41,950 1 gigabyte aquests dies, 2 gigabytes, o fins i tot molt més, 38 00:01:41,950 --> 00:01:44,420 generalment es presenta per a un programa donat 39 00:01:44,420 --> 00:01:47,170 en aquest tipus de rectangular model conceptual 40 00:01:47,170 --> 00:01:50,860 amb la qual cosa tenim la pila a la part inferior i un munt d'altres coses a la part superior. 41 00:01:50,860 --> 00:01:53,140 La cosa a la part superior que hem vist en aquesta imatge 42 00:01:53,140 --> 00:01:55,670 abans, però mai es parla és l'anomenat segment de text. 43 00:01:55,670 --> 00:01:58,419 Segment de text és només una forma elegant de dir els zeros i uns que 44 00:01:58,419 --> 00:02:01,150 compondre el seu programa compilat real. 45 00:02:01,150 --> 00:02:03,910 >> Així que en fer doble clic Microsoft Word en el seu Mac o PC, 46 00:02:03,910 --> 00:02:08,030 o quan s'executa punt slash Mario en un Ordinador amb Linux a la finestra de terminal, 47 00:02:08,030 --> 00:02:12,460 els zeros i uns que componen Word o Mario s'emmagatzemen temporalment 48 00:02:12,460 --> 00:02:16,610 a la memòria RAM de l'ordinador en l'anomenat segment de text per a un programa en particular. 49 00:02:16,610 --> 00:02:19,080 A sota d'això va inicialitzat i dades sense inicialitzar. 50 00:02:19,080 --> 00:02:22,655 Això és una cosa similar a les variables globals, que nosaltres no hem fet servir molts, 51 00:02:22,655 --> 00:02:24,910 però en ocasions ens hem tingut variables globals 52 00:02:24,910 --> 00:02:28,819 o estàticament cordes definit que està codificat paraules com "hola" 53 00:02:28,819 --> 00:02:31,860 que no són preses en l'usuari des que estan codificats dur en el seu programa. 54 00:02:31,860 --> 00:02:34,230 >> Ara, avall a la part inferior que tenir l'anomenada pila. 55 00:02:34,230 --> 00:02:37,665 I la pila, fins ara, hem estat utilitzant per a quin tipus de propòsits? 56 00:02:37,665 --> 00:02:39,706 57 00:02:39,706 --> 00:02:40,997 El que la pila s'utilitza? 58 00:02:40,997 --> 00:02:41,160 Sí? 59 00:02:41,160 --> 00:02:42,070 >> AUDIÈNCIA: Funcions. 60 00:02:42,070 --> 00:02:43,320 >> DAVID J. Malan: Per a les funcions? 61 00:02:43,320 --> 00:02:44,980 ¿En quin sentit per a les funcions? 62 00:02:44,980 --> 00:02:48,660 >> AUDIÈNCIA: Quan es crida a una funció, el arguments es copien a la pila. 63 00:02:48,660 --> 00:02:49,660 >> DAVID J. Malan: Exactament. 64 00:02:49,660 --> 00:02:52,650 Quan es crida a una funció, la seva arguments es copien a la pila. 65 00:02:52,650 --> 00:02:56,330 Així que qualsevol X o Y o A o B de l' que està passant en una funció 66 00:02:56,330 --> 00:02:58,680 estan temporalment posar en l'anomenada pila, 67 00:02:58,680 --> 00:03:02,000 igual que un dels Annenberg safates de menjador, i també coses 68 00:03:02,000 --> 00:03:03,190 com a variables locals. 69 00:03:03,190 --> 00:03:06,290 Si la seva funció foo o el seu bescanvi funció té variables locals, 70 00:03:06,290 --> 00:03:08,602 com la temperatura, els dos acaben a la pila. 71 00:03:08,602 --> 00:03:11,560 Ara, no anem a parlar massa sobre ells, però aquestes variables d'entorn 72 00:03:11,560 --> 00:03:15,690 a la part inferior que vam veure fa un temps quan Em barallar en el teclat un dia 73 00:03:15,690 --> 00:03:20,050 i vaig començar a accedir a les coses com argv argv 100 o 1000, 74 00:03:20,050 --> 00:03:22,320 només elements-- oblit la numbers-- però això 75 00:03:22,320 --> 00:03:24,330 no se suposa que és visitada per mi. 76 00:03:24,330 --> 00:03:26,581 Comencem a veure algunes símbols de funky a la pantalla. 77 00:03:26,581 --> 00:03:28,330 Aquests eren els anomenats variables d'entorn 78 00:03:28,330 --> 00:03:32,390 com ajustos globals per a mi programa o per al meu equip, no 79 00:03:32,390 --> 00:03:37,090 no relacionat amb la recent error que hem discutit, 80 00:03:37,090 --> 00:03:39,670 Shellshock, que ha estat que afecta a un bon nombre d'ordinadors. 81 00:03:39,670 --> 00:03:42,960 >> Ara, finalment, en l'enfocament d'avui serem en última instància, en el munt. 82 00:03:42,960 --> 00:03:44,864 Aquesta és una altra part de la memòria. 83 00:03:44,864 --> 00:03:47,030 I fonamentalment tot això la memòria és la mateixa matèria. 84 00:03:47,030 --> 00:03:48,040 És el mateix maquinari. 85 00:03:48,040 --> 00:03:49,956 Som només una mena de el tractament de diferents grups 86 00:03:49,956 --> 00:03:51,460 de bytes per a diferents propòsits. 87 00:03:51,460 --> 00:03:56,540 El munt també estarà on variables i memòria que vostè demani 88 00:03:56,540 --> 00:03:58,810 des del sistema operatiu s'emmagatzema temporalment. 89 00:03:58,810 --> 00:04:01,890 >> Però hi ha una espècie de problema Aquí, com la imatge implica. 90 00:04:01,890 --> 00:04:05,261 Tenim sort de tenir dos vaixells a punt de xocar. 91 00:04:05,261 --> 00:04:08,010 Perquè com s'utilitza cada vegada més de la pila, i com el veiem avui en dia 92 00:04:08,010 --> 00:04:11,800 endavant, i quan s'utilitza cada vegada més de la munt, segurament les coses dolentes poden succeir. 93 00:04:11,800 --> 00:04:15,054 I, de fet, podem induir que amb o sense intenció. 94 00:04:15,054 --> 00:04:16,970 Així que el drama de suspens última temps era aquest programa, 95 00:04:16,970 --> 00:04:20,570 que no servirà qualsevol funcional propòsit que no sigui per demostrar 96 00:04:20,570 --> 00:04:24,750 com vostè com un tipus dolent en realitat pot prendre avantatge dels errors en el programa d'algú 97 00:04:24,750 --> 00:04:28,460 i fer-se càrrec d'un programa o fins i tot un sistema informàtic totalitat o servidor. 98 00:04:28,460 --> 00:04:31,660 Així que a primera vista breument, que notar que la principal a la part inferior 99 00:04:31,660 --> 00:04:34,510 pren en la línia d'ordres arguments, com per argv. 100 00:04:34,510 --> 00:04:38,480 I té una crida a una funció f, essencialment una funció sense nom diu 101 00:04:38,480 --> 00:04:40,250 f, i està passant en argv [1]. 102 00:04:40,250 --> 00:04:43,960 >> Així que qualsevol paraula que l'usuari escriu a l' el símbol darrere del nom d'aquest programa, 103 00:04:43,960 --> 00:04:49,310 i després aquesta funció arbitrària fins superior, f, porta en una cadena, conegut com char *, 104 00:04:49,310 --> 00:04:51,720 com hem començat a discutir, i que només ho diu "bar". 105 00:04:51,720 --> 00:04:53,310 Però podríem anomenar res. 106 00:04:53,310 --> 00:04:57,470 I llavors es declara, a l'interior de f, un conjunt de caràcters 107 00:04:57,470 --> 00:04:59,930 anomenat C-- 12 d'aquests personatges. 108 00:04:59,930 --> 00:05:03,580 >> Ara, per la història que explicava Fa un moment, quan en la memòria 109 00:05:03,580 --> 00:05:06,720 és c, o són els 12 Chars va a acabar? 110 00:05:06,720 --> 00:05:07,570 Perquè quedi clar. 111 00:05:07,570 --> 00:05:08,070 Sí? 112 00:05:08,070 --> 00:05:08,590 >> AUDIÈNCIA: A la pila. 113 00:05:08,590 --> 00:05:09,420 >> DAVID J. Malan: A la pila. 114 00:05:09,420 --> 00:05:10,720 Així que c és una variable local. 115 00:05:10,720 --> 00:05:14,079 Estem demanant 12 caràcters o 12 bytes. 116 00:05:14,079 --> 00:05:16,120 Aquests van a acabar en l'anomenada pila. 117 00:05:16,120 --> 00:05:18,530 Ara, finalment, és aquesta altra funció això és realment molt útil, 118 00:05:18,530 --> 00:05:20,571 però nosaltres no hem fet servir realment nosaltres mateixos, strncopy. 119 00:05:20,571 --> 00:05:21,550 120 00:05:21,550 --> 00:05:25,200 Això significa còpia de cadena, però només n lletres, n caràcters. 121 00:05:25,200 --> 00:05:31,990 Així n caràcters seran copiat de bar al c. 122 00:05:31,990 --> 00:05:32,980 I quants? 123 00:05:32,980 --> 00:05:34,110 La longitud de la barra. 124 00:05:34,110 --> 00:05:36,330 Així, en altres paraules, que una línia, strncopy, 125 00:05:36,330 --> 00:05:39,500 va a copiar prohibir de manera efectiva en l'c. 126 00:05:39,500 --> 00:05:42,340 >> Ara, només per tipus d'anticipar la moralitat d'aquesta història, 127 00:05:42,340 --> 00:05:44,750 el que és potencialment problemàtica aquí? 128 00:05:44,750 --> 00:05:49,710 Tot i que estem comprovant la longitud del bar i de passar-ho a strncopy, 129 00:05:49,710 --> 00:05:53,145 ¿Quin és el seu intestí dient és encara trencat sobre aquest programa? 130 00:05:53,145 --> 00:05:54,410 131 00:05:54,410 --> 00:05:55,220 Sí? 132 00:05:55,220 --> 00:05:57,491 >> AUDIÈNCIA: No inclou espai per al caràcter nul. 133 00:05:57,491 --> 00:05:59,990 DAVID J. Malan: No inclou espai per al caràcter nul. 134 00:05:59,990 --> 00:06:02,073 Potencialment, a diferència de pràctica del passat que ni tan sols 135 00:06:02,073 --> 00:06:04,810 tenir tant com un plus de l'1 al acomodar aquest caràcter nul. 136 00:06:04,810 --> 00:06:06,649 Però és encara pitjor que això. 137 00:06:06,649 --> 00:06:07,940 Què més estem fallant a fer? 138 00:06:07,940 --> 00:06:08,432 Sí? 139 00:06:08,432 --> 00:06:09,307 >> AUDIÈNCIA: [inaudible] 140 00:06:09,307 --> 00:06:15,440 141 00:06:15,440 --> 00:06:16,440 DAVID J. Malan: Perfect. 142 00:06:16,440 --> 00:06:18,490 Dur Hem codifiquem 12 bastant arbitrària. 143 00:06:18,490 --> 00:06:19,497 144 00:06:19,497 --> 00:06:21,330 Això no és tant la problema, però el fet 145 00:06:21,330 --> 00:06:25,630 que ni tan sols estem comprovant si la longitud de la barra és de menys de 12, 146 00:06:25,630 --> 00:06:28,530 en aquest cas serà segur per a posar-lo en la memòria 147 00:06:28,530 --> 00:06:30,260 anomenat c que hem assignat. 148 00:06:30,260 --> 00:06:32,960 En efecte, si la barra és com 20 caràcters de llarg, 149 00:06:32,960 --> 00:06:39,010 aquesta funció sembla estar copiant 20 personatges de bar al c, per tant 150 00:06:39,010 --> 00:06:41,310 tenint almenys 8 bytes que no ha de ser. 151 00:06:41,310 --> 00:06:42,690 Aquesta és la implicació aquí. 152 00:06:42,690 --> 00:06:44,347 >> Així que en breu programa, trencat. 153 00:06:44,347 --> 00:06:45,180 No com una gran cosa. 154 00:06:45,180 --> 00:06:46,360 Potser vostè aconsegueix un error de segmentació. 155 00:06:46,360 --> 00:06:47,651 Tots hem tingut errors en els programes. 156 00:06:47,651 --> 00:06:50,196 Tots nosaltres podríem tenir errors en els programes en aquests moments. 157 00:06:50,196 --> 00:06:51,320 Però quina és la implicació? 158 00:06:51,320 --> 00:06:54,390 Bé, aquí hi ha una versió ampliada a d' que la imatge de la memòria del meu ordinador. 159 00:06:54,390 --> 00:06:56,230 Aquest és el fons del meu stack. 160 00:06:56,230 --> 00:06:59,644 I, en efecte, en la part inferior és el que hi ha anomenada pila rutina pare, forma elegant 161 00:06:59,644 --> 00:07:00,560 de dir que és principal. 162 00:07:00,560 --> 00:07:03,772 Així que tot el que crida a la funció f que estem parlant. 163 00:07:03,772 --> 00:07:05,230 Així que aquesta és la part inferior de la pila. 164 00:07:05,230 --> 00:07:06,640 Direcció de retorn és una cosa nova. 165 00:07:06,640 --> 00:07:08,810 Sempre ha estat aquí, sempre ha estat en aquesta foto. 166 00:07:08,810 --> 00:07:10,440 Nosaltres mai cridem l'atenció sobre ell. 167 00:07:10,440 --> 00:07:15,290 Perquè resulta que la forma c funciona és que quan una funció crida a una altra, 168 00:07:15,290 --> 00:07:18,780 no només els arguments que funció get inserida en la pila, 169 00:07:18,780 --> 00:07:22,470 no només fer local de la funció variables de quedar relegats a la pila, 170 00:07:22,470 --> 00:07:26,820 cosa que es diu una adreça de retorn També aconsegueix posar a la pila. 171 00:07:26,820 --> 00:07:33,330 En concret, si les trucades principals Foo, principals pròpia direcció en la memòria, el bou alguna cosa, 172 00:07:33,330 --> 00:07:38,240 efectivament aconsegueix posar a la pila de manera que quan f es fa executar 173 00:07:38,240 --> 00:07:43,630 sap on per saltar de nou a en el text segment per tal de continuar amb l'execució. 174 00:07:43,630 --> 00:07:47,760 >> Així que si som aquí conceptualment, en principal, llavors f és cridat. 175 00:07:47,760 --> 00:07:50,200 Com se sap que f al control de la mà de tornada? 176 00:07:50,200 --> 00:07:52,020 Bé, aquest petit molla de pa en vermell aquí, 177 00:07:52,020 --> 00:07:54,978 anomenat el remitent, només xecs, el que és que la direcció del remitent? 178 00:07:54,978 --> 00:07:57,039 Oh, deixa saltar de nou al principal aquí. 179 00:07:57,039 --> 00:07:59,080 I això és una mica d'una simplificació excessiva, 180 00:07:59,080 --> 00:08:00,750 perquè els zeros i uns per principals són tècnicament 181 00:08:00,750 --> 00:08:01,967 aquí al segment de tecnologia. 182 00:08:01,967 --> 00:08:03,800 Però aquesta és la idea. f només ha de saber el que 183 00:08:03,800 --> 00:08:06,680 on el control en última instància es remunta. 184 00:08:06,680 --> 00:08:09,790 >> Però la forma en ordinadors han assegut durant molt de temps fora coses 185 00:08:09,790 --> 00:08:12,320 com les variables locals i arguments és així. 186 00:08:12,320 --> 00:08:17,180 Així que a la part superior d'aquesta imatge en blau és el marc de pila de f, de manera que tot 187 00:08:17,180 --> 00:08:19,630 de la memòria que f específicament utilitzeu. 188 00:08:19,630 --> 00:08:22,990 Així que en conseqüència, observi que bar està en aquesta foto. 189 00:08:22,990 --> 00:08:23,980 Bar era el seu argument. 190 00:08:23,980 --> 00:08:27,240 I reclamem que els arguments a funcions quedar relegats a la pila. 191 00:08:27,240 --> 00:08:29,910 I C, per descomptat, és També en aquesta imatge. 192 00:08:29,910 --> 00:08:33,520 >> I només per a propòsits de notació, compte en la cantonada superior esquerra 193 00:08:33,520 --> 00:08:37,020 és el que es c suport 0 i a continuació, una mica cap a la dreta 194 00:08:37,020 --> 00:08:38,220 c és el suport 11. 195 00:08:38,220 --> 00:08:41,240 En altres paraules, es pot imaginar que hi ha una reixa de bytes 196 00:08:41,240 --> 00:08:44,380 allà, primer dels quals és dalt a l'esquerra, part inferior de les quals 197 00:08:44,380 --> 00:08:48,360 és l'últim d'aquests 12 bytes. 198 00:08:48,360 --> 00:08:49,930 >> Però ara tractar d'avançar ràpidament. 199 00:08:49,930 --> 00:08:55,580 Què passarà si passem en un bar de cadena que és més de c? 200 00:08:55,580 --> 00:08:59,130 I no estem comprovant si és de fet més de 12. 201 00:08:59,130 --> 00:09:03,146 Quina part d'aquesta imatge va a aconseguir sobreescrit per bytes 0, 1, 2, 3, 202 00:09:03,146 --> 00:09:07,890 dot dot dot, 11, i després dolent, 12, 13 a través de 19? 203 00:09:07,890 --> 00:09:11,820 Què passarà aquí, si vostè deduir de l'ordenament 204 00:09:11,820 --> 00:09:14,790 que c abraçadora 0 està en la part superior i c abraçadora 11 és una espècie de sota 205 00:09:14,790 --> 00:09:15,812 a la dreta? 206 00:09:15,812 --> 00:09:16,796 Sí? 207 00:09:16,796 --> 00:09:19,260 >> AUDIÈNCIA: Bé, va sobreescriure bar char *. 208 00:09:19,260 --> 00:09:22,260 >> DAVID J. Malan: Sí, sembla que vostè va a sobreescriure char * bar. 209 00:09:22,260 --> 00:09:26,245 I pitjor encara, si vostè envia en un temps molt llarg cadena, que fins i tot podria sobreescriure què? 210 00:09:26,245 --> 00:09:27,460 211 00:09:27,460 --> 00:09:28,570 La direcció de retorn. 212 00:09:28,570 --> 00:09:31,380 Que al seu torn, és igual que un ruta de navegació per dir-li al programa on 213 00:09:31,380 --> 00:09:34,060 per anar de nou a quan f es fa la qual crida. 214 00:09:34,060 --> 00:09:37,140 >> Llavors, què nois dolents solen fer és si es troben amb un programa 215 00:09:37,140 --> 00:09:41,290 que són curiosos si és explotable, amb errors de forma 216 00:09:41,290 --> 00:09:43,550 que ell o ella pot prendre avantatge d'aquest error, 217 00:09:43,550 --> 00:09:45,720 generalment no reben aquesta bé la primera vegada. 218 00:09:45,720 --> 00:09:48,590 Només començar a enviar, per exemple, cadenes aleatòries en el seu programa, 219 00:09:48,590 --> 00:09:50,260 ja sigui en el teclat, o francament que probablement 220 00:09:50,260 --> 00:09:52,740 escriure un petit programa que acaba d' generen automàticament les cadenes, 221 00:09:52,740 --> 00:09:55,430 i començar a colpejar en el seu programa l'enviament de gran quantitat de diferents insums 222 00:09:55,430 --> 00:09:56,340 en diferents longituds. 223 00:09:56,340 --> 00:09:58,990 >> Tan aviat com els seus errors en el programa, això és una cosa increïble. 224 00:09:58,990 --> 00:10:01,020 Com que vol dir que ell o que ha descobert 225 00:10:01,020 --> 00:10:02,660 el que probablement és de fet un error. 226 00:10:02,660 --> 00:10:05,830 I llavors poden aconseguir més intel · ligent i començar a centrar-se més estretament 227 00:10:05,830 --> 00:10:07,420 sobre la forma d'explotar aquest error. 228 00:10:07,420 --> 00:10:11,480 En particular, el que ell o ella podria fer és enviar, en el millor dels casos, hola. 229 00:10:11,480 --> 00:10:12,210 No és gran cosa. 230 00:10:12,210 --> 00:10:14,750 És una cadena que és prou curt. 231 00:10:14,750 --> 00:10:18,100 Però i si ell o ella envia, i anem a generalitzar com, 232 00:10:18,100 --> 00:10:20,890 atac code-- tan zeros i els que fan les coses 233 00:10:20,890 --> 00:10:25,150 com rm-rf, de treure tot des del disc dur o enviar correu brossa 234 00:10:25,150 --> 00:10:27,000 o atacar d'alguna manera la màquina? 235 00:10:27,000 --> 00:10:29,570 >> Així que si cada un d'aquests lletres A només representa, 236 00:10:29,570 --> 00:10:32,380 conceptualment, atac, atac, atac, atac, algunes males codi 237 00:10:32,380 --> 00:10:36,410 que algú més va escriure, però si aquesta persona és prou intel · ligent 238 00:10:36,410 --> 00:10:40,790 no només per incloure tota d'aquests rm-RFS, sinó també 239 00:10:40,790 --> 00:10:46,100 tenir els seus últims bytes ser un número que correspon 240 00:10:46,100 --> 00:10:50,540 a la direcció del seu o el seu propi codi d'atac 241 00:10:50,540 --> 00:10:53,820 que ell o ella va passar en només proporcionant a l'indicador, 242 00:10:53,820 --> 00:10:58,760 es pot enganyar a l'ordinador amb eficàcia en adonar-se quan f es realitza l'execució, 243 00:10:58,760 --> 00:11:02,400 oh, és el moment perquè salti de nou a l'adreça de retorn vermell. 244 00:11:02,400 --> 00:11:06,070 Però com que ell o ella té d'alguna manera superposades que remet 245 00:11:06,070 --> 00:11:09,602 amb el seu propi número, i són prou intel · ligents 246 00:11:09,602 --> 00:11:11,560 haver configurat que número de referència, ja que 247 00:11:11,560 --> 00:11:13,740 veure en el top fantàstic cantonada esquerra hi ha, 248 00:11:13,740 --> 00:11:18,020 l'adreça real a l'ordinador de memòria d'alguns del seu codi d'atac, 249 00:11:18,020 --> 00:11:21,740 un noi dolent pot enganyar l'ordinador en l'execució del seu propi codi. 250 00:11:21,740 --> 00:11:23,700 >> I aquest codi, de nou, pot ser qualsevol cosa. 251 00:11:23,700 --> 00:11:26,120 Generalment, es diu codi shell, que és just 252 00:11:26,120 --> 00:11:29,030 una forma de dir que no és generalment una cosa tan simple com rm-rf. 253 00:11:29,030 --> 00:11:32,340 En realitat és com Bash, o un programa que li dóna 254 00:11:32,340 --> 00:11:37,230 o el seu control de programació per executar qualsevol altra cosa que ells volen. 255 00:11:37,230 --> 00:11:40,210 Així que en resum, tot això deriva del simple fet 256 00:11:40,210 --> 00:11:44,490 que aquest error en qüestió no comprovació els límits de la matriu. 257 00:11:44,490 --> 00:11:47,250 I a causa de la forma en equips de treball és que 258 00:11:47,250 --> 00:11:49,430 utilitzar la pila de efectivament, conceptualment, 259 00:11:49,430 --> 00:11:54,830 part inferior cap amunt, però després els elements vostè empeny a la pila creixi dalt a baix, 260 00:11:54,830 --> 00:11:56,624 això és molt problemàtic. 261 00:11:56,624 --> 00:11:58,290 Ara, hi ha maneres d'evitar aquest. 262 00:11:58,290 --> 00:12:00,800 I, francament, hi ha llengües amb el qual treballar al voltant d'això. 263 00:12:00,800 --> 00:12:03,100 Java és immune, per exemple, a aquest tema en particular. 264 00:12:03,100 --> 00:12:04,110 Perquè ells no et donen consells. 265 00:12:04,110 --> 00:12:05,943 Ells no et donen adreces de memòria directa. 266 00:12:05,943 --> 00:12:08,560 Així que amb aquest poder que tenim tocar res en la memòria 267 00:12:08,560 --> 00:12:11,580 volem que ve, sens dubte, un gran risc. 268 00:12:11,580 --> 00:12:12,430 >> Així que mantenir un ull cap a fora. 269 00:12:12,430 --> 00:12:14,596 Si, francament, en els mesos de o anys per venir, en qualsevol moment 270 00:12:14,596 --> 00:12:17,740 vostè llegeixi sobre cert tipus d'explotació d'un programa o un servidor, 271 00:12:17,740 --> 00:12:22,370 si vostè veu un indici d'alguna cosa com un atac de desbordament de memòria intermèdia, 272 00:12:22,370 --> 00:12:25,390 o desbordament de pila és un altre tipus d'atac, similar en esperit, 273 00:12:25,390 --> 00:12:28,770 tant com inspira el lloc web de nomenar, si ho coneix, 274 00:12:28,770 --> 00:12:33,170 tot està parlant només d' vessar la mida d'alguns de caràcter 275 00:12:33,170 --> 00:12:36,200 matriu o alguna varietat més general. 276 00:12:36,200 --> 00:12:38,822 Qualsevol pregunta, llavors, sobre això? 277 00:12:38,822 --> 00:12:39,780 No intenteu fer això a casa. 278 00:12:39,780 --> 00:12:41,620 279 00:12:41,620 --> 00:12:42,300 >> Bé. 280 00:12:42,300 --> 00:12:47,270 Així malloc fins ara ha estat el nostre nou amic en què podem assignar memòria 281 00:12:47,270 --> 00:12:50,540 que no sabem necessàriament en avancem que volem el que no tenim 282 00:12:50,540 --> 00:12:52,920 a codificar en la nostra números de programes com 12. 283 00:12:52,920 --> 00:12:55,550 Una vegada que l'usuari ens diu quant dades que ell o ella vol d'entrada, 284 00:12:55,550 --> 00:12:58,000 podem malloc que gran part de la memòria. 285 00:12:58,000 --> 00:13:01,484 >> Així malloc resulta, a la mesura que hem estat utilitzant, 286 00:13:01,484 --> 00:13:03,900 explícitament l'última vegada, i després vostès han estat utilitzant 287 00:13:03,900 --> 00:13:08,160 getString per saber-ho per diverses setmanes, tots els de la memòria de malloc 288 00:13:08,160 --> 00:13:09,820 prové de l'anomenada pila. 289 00:13:09,820 --> 00:13:13,852 I és per això getString, per exemple, pot assignar memòria dinàmicament 290 00:13:13,852 --> 00:13:16,060 sense saber el que ets va a escriure per endavant, 291 00:13:16,060 --> 00:13:21,520 de tornar un punter a la memòria, i que la memòria segueix sent teu per sempre, 292 00:13:21,520 --> 00:13:24,080 fins i tot després GetString rendiments. 293 00:13:24,080 --> 00:13:27,450 Perquè record després de tot el que l' pila està constantment pujant i baixant, 294 00:13:27,450 --> 00:13:27,950 amunt i avall. 295 00:13:27,950 --> 00:13:30,230 I tan aviat com va baix, això significa que qualsevol memòria 296 00:13:30,230 --> 00:13:33,030 aquesta funció emprada ha No ser utilitzat per cap altra persona. 297 00:13:33,030 --> 00:13:34,570 És valors d'escombraries ara. 298 00:13:34,570 --> 00:13:36,120 >> Però el munt és aquí dalt. 299 00:13:36,120 --> 00:13:39,360 I el que és bo de malloc és que quan malloc assigna memòria fins aquí, 300 00:13:39,360 --> 00:13:42,070 no està afectada, per a la major part, per la pila. 301 00:13:42,070 --> 00:13:46,000 I pel que qualsevol funció pot accedir memòria que s'ha malloc'd, 302 00:13:46,000 --> 00:13:49,120 fins i tot per una funció com getString, fins i tot després que es retorna. 303 00:13:49,120 --> 00:13:51,700 >> Ara, el contrari del malloc és gratis. 304 00:13:51,700 --> 00:13:53,900 I, en efecte, la regla que que hagi de començar a adoptar 305 00:13:53,900 --> 00:13:58,950 és qualsevol, qualsevol, qualsevol moment vostè utilitza malloc ha de vostè utilitzar lliure, amb el temps, 306 00:13:58,950 --> 00:14:00,280 en aquest mateix punter. 307 00:14:00,280 --> 00:14:03,289 Durant tot aquest temps hem estat escrivint amb errors, codi erroni, per moltes raons. 308 00:14:03,289 --> 00:14:05,580 Però un dels quals ha estat utilitzant la biblioteca d'CS50, que 309 00:14:05,580 --> 00:14:09,010 sí que és deliberadament amb errors, es perd memòria. 310 00:14:09,010 --> 00:14:11,410 Cada vegada que ha anomenat getString durant les últimes setmanes 311 00:14:11,410 --> 00:14:13,870 estem fent l'operació sistema, Linux, per a la memòria. 312 00:14:13,870 --> 00:14:15,780 I vostè mai una vegada donat per tu. 313 00:14:15,780 --> 00:14:17,730 I això no és, en practicar, una bona cosa. 314 00:14:17,730 --> 00:14:20,330 >> I Valgrind, un dels eines introduïdes en el joc de paràmetres 4, 315 00:14:20,330 --> 00:14:22,900 es tracta d'ajudar vostè ara trobar errors com aquest. 316 00:14:22,900 --> 00:14:27,060 Però per sort per Pset 4 no cal utilitzar la biblioteca CS50 o getString. 317 00:14:27,060 --> 00:14:31,220 Així que qualsevol error relacionats amb la memòria són en última instància, serà la seva. 318 00:14:31,220 --> 00:14:34,060 >> Així malloc és més que convenient per a aquest propòsit. 319 00:14:34,060 --> 00:14:37,420 En realitat, ara podem resoldre fonamentalment diferents problemes, 320 00:14:37,420 --> 00:14:41,640 i resoldre fonamentalment els problemes més eficaçment com per la promesa de la setmana zero. 321 00:14:41,640 --> 00:14:44,720 Fins al moment aquesta és la més sexy estructura de dades que hem tingut. 322 00:14:44,720 --> 00:14:47,804 I per l'estructura de les dades que acabo de dir una forma de memòria conceptualitzar 323 00:14:47,804 --> 00:14:50,720 d'una manera que va més enllà de només dir, aquest és un int, aquest és un char. 324 00:14:50,720 --> 00:14:52,930 Podem començar al costat de les coses de dispersió. 325 00:14:52,930 --> 00:14:54,460 >> Així que una matriu es veia així. 326 00:14:54,460 --> 00:14:57,270 I el que va ser clau en aproximadament una array és que et dóna 327 00:14:57,270 --> 00:14:59,724 back-to-back trossos de memòria, cadascun dels quals 328 00:14:59,724 --> 00:15:02,765 serà del mateix tipus, int, int, int, int o char, char, char, 329 00:15:02,765 --> 00:15:03,330 Char. 330 00:15:03,330 --> 00:15:04,496 Però hi ha alguns desavantatges. 331 00:15:04,496 --> 00:15:06,570 Això per exemple, és una matriu de mida 6. 332 00:15:06,570 --> 00:15:10,650 Suposem que vostè ompli aquesta matriu amb sis números i després, per les raons que siguin, 333 00:15:10,650 --> 00:15:13,187 l'usuari vol donar que un setè número. 334 00:15:13,187 --> 00:15:14,020 On el vas posar? 335 00:15:14,020 --> 00:15:15,490 336 00:15:15,490 --> 00:15:18,990 >> Quina és la solució si vostè té creat una matriu a la pila, 337 00:15:18,990 --> 00:15:22,030 per exemple, només amb la setmana 02:00 notació que hem introduït, 338 00:15:22,030 --> 00:15:23,730 d'claudàtors amb els números de l'interior? 339 00:15:23,730 --> 00:15:25,160 340 00:15:25,160 --> 00:15:27,260 Bé, vostè té sis els nombres en aquestes caixes. 341 00:15:27,260 --> 00:15:28,530 Quins serien els seus instints? 342 00:15:28,530 --> 00:15:29,973 On t'agradaria posar? 343 00:15:29,973 --> 00:15:30,860 >> AUDIÈNCIA: [inaudible] 344 00:15:30,860 --> 00:15:31,315 >> DAVID J. Malan: Ho sento? 345 00:15:31,315 --> 00:15:32,380 >> AUDIÈNCIA: Posa-ho al final. 346 00:15:32,380 --> 00:15:33,796 >> DAVID J. Malan: Posa-ho a l'extrem. 347 00:15:33,796 --> 00:15:35,880 Així que una mica més a la dreta, fora d'aquesta caixa de text. 348 00:15:35,880 --> 00:15:38,710 Què estaria bé, però resulta que no pot fer això. 349 00:15:38,710 --> 00:15:41,350 Perquè si no ho has demanat per aquesta part de la memòria, 350 00:15:41,350 --> 00:15:44,490 podria ser per casualitat que aquesta està sent utilitzat per alguna altra variable 351 00:15:44,490 --> 00:15:45,030 completament. 352 00:15:45,030 --> 00:15:49,210 Penseu de nou una setmana o així que quan ens fiquem al llit els noms Zamyla i Davin i Gabe de 353 00:15:49,210 --> 00:15:49,930 en la memòria. 354 00:15:49,930 --> 00:15:51,638 Eren, literalment, esquena amb esquena amb esquena. 355 00:15:51,638 --> 00:15:53,550 Així que no podem necessàriament confiar que qualsevol de 356 00:15:53,550 --> 00:15:55,800 aquí està disponible perquè jo usi. 357 00:15:55,800 --> 00:15:56,990 >> Llavors, què més podria fer? 358 00:15:56,990 --> 00:16:00,282 Bé, una vegada que adonar-se que necessitarà una matriu de mida 7, 359 00:16:00,282 --> 00:16:02,490 vostè podria crear un matriu de mida 7 després utilitzeu 360 00:16:02,490 --> 00:16:05,950 un bucle for o un bucle while, copiar-lo en la nova matriu, 361 00:16:05,950 --> 00:16:09,680 i llavors d'alguna manera simplement desfer-se de aquesta matriu o simplement deixi d'usar-lo. 362 00:16:09,680 --> 00:16:12,130 Però això no és particularment eficient. 363 00:16:12,130 --> 00:16:15,340 En resum, les matrius no deixen canviar la mida de forma dinàmica. 364 00:16:15,340 --> 00:16:17,900 >> Així que per una banda s'obté accés aleatori, que és increïble. 365 00:16:17,900 --> 00:16:20,108 Com que ens permet fer coses com divideix i venceràs, 366 00:16:20,108 --> 00:16:23,100 recerca binària, la qual cosa hem parlat a la pantalla aquí. 367 00:16:23,100 --> 00:16:24,950 Però es pinta a si mateix en una cantonada. 368 00:16:24,950 --> 00:16:27,810 Tan aviat com es va colpejar Al final de la seva matriu, 369 00:16:27,810 --> 00:16:29,980 vostè ha de fer un molt operació costosa 370 00:16:29,980 --> 00:16:33,910 o escriure un munt de codi de lluitar ara amb aquest problema. 371 00:16:33,910 --> 00:16:36,680 >> I què si el seu lloc, teníem cosa que es diu una llista, 372 00:16:36,680 --> 00:16:38,820 o una llista vinculada en particular? 373 00:16:38,820 --> 00:16:41,930 Què passa si en lloc d'haver rectangles esquena amb esquena amb esquena, 374 00:16:41,930 --> 00:16:45,730 hem rectangles que deixen una mica poc de marge de maniobra enmig d'ells? 375 00:16:45,730 --> 00:16:49,670 I tot i que he dibuixat aquest foto o adaptat aquesta foto 376 00:16:49,670 --> 00:16:54,696 d'un dels textos aquí per estar de nou a esquena amb esquena molt ordenada, en la realitat, 377 00:16:54,696 --> 00:16:56,820 un d'aquests rectangles podria ser de fins a aquí a la memòria. 378 00:16:56,820 --> 00:16:58,028 Un d'ells podria ser aquí. 379 00:16:58,028 --> 00:17:00,420 Un d'ells podria ser aquí dalt, aquí, i així successivament. 380 00:17:00,420 --> 00:17:02,910 >> Però el que si dibuixem, en aquest cas, les fletxes 381 00:17:02,910 --> 00:17:05,650 que d'alguna manera vincular rectangles junts? 382 00:17:05,650 --> 00:17:08,170 De fet, hem vist una tècnica encarnació d'una fletxa. 383 00:17:08,170 --> 00:17:09,839 384 00:17:09,839 --> 00:17:13,710 Què hem utilitzat en els últims dia que, sota la campana, 385 00:17:13,710 --> 00:17:15,210 és representativa d'una fletxa? 386 00:17:15,210 --> 00:17:16,290 387 00:17:16,290 --> 00:17:17,349 Un punter, oi? 388 00:17:17,349 --> 00:17:19,780 >> I què si, en lloc de emmagatzemar només els números, 389 00:17:19,780 --> 00:17:23,130 com 9, 17, 22, 26, 34, ¿I si no emmagatzemem 390 00:17:23,130 --> 00:17:27,079 només un nombre, però un punter costat de cada un d'aquests nombre? 391 00:17:27,079 --> 00:17:30,690 Així que igual que enfilar una agulla a través d'un grapat sencer de la tela, 392 00:17:30,690 --> 00:17:32,950 coses d'alguna forma de vinculació junts, de manera similar pot 393 00:17:32,950 --> 00:17:35,550 que amb els punters, com encarnat per fletxes aquí, 394 00:17:35,550 --> 00:17:38,550 tipus de teixir aquests rectangles individuals 395 00:17:38,550 --> 00:17:41,780 per la utilització eficaç d'un punter un al costat del número que 396 00:17:41,780 --> 00:17:46,065 apunta alguns següent nombre, que assenyala, al seu torn, alguns següent nombre? 397 00:17:46,065 --> 00:17:47,940 Així que en altres paraules, el que si en realitat volíem 398 00:17:47,940 --> 00:17:49,820 per implementar alguna cosa com això? 399 00:17:49,820 --> 00:17:53,610 Bé per desgràcia, aquests rectangles, almenys l'un amb 9, 17, 22, 400 00:17:53,610 --> 00:17:57,040 i així successivament, aquests ja no són boniques places amb números individuals. 401 00:17:57,040 --> 00:17:59,960 La part inferior, rectangle per sota de 9, per exemple, 402 00:17:59,960 --> 00:18:04,330 representa el que ha de ser un punter, 32 bits. 403 00:18:04,330 --> 00:18:09,460 Ara, encara no estic al corrent de qualsevol tipus de dades en C que li dóna no només un int 404 00:18:09,460 --> 00:18:11,630 però un punter per complet. 405 00:18:11,630 --> 00:18:15,020 >> Llavors, ¿quina és la solució si volem inventar la nostra pròpia resposta a això? 406 00:18:15,020 --> 00:18:15,760 Sí? 407 00:18:15,760 --> 00:18:16,640 >> AUDIÈNCIA: [inaudible] 408 00:18:16,640 --> 00:18:17,360 >> DAVID J. Malan: Què és això? 409 00:18:17,360 --> 00:18:17,880 >> AUDIÈNCIA: Nova estructura. 410 00:18:17,880 --> 00:18:19,590 >> DAVID J. Malan: Sí, i per què Per què no creem una nova estructura, 411 00:18:19,590 --> 00:18:20,920 o en C, una estructura? 412 00:18:20,920 --> 00:18:25,990 Hem vist estructures abans, encara que breument, on ens topem amb una estructura estudiant 413 00:18:25,990 --> 00:18:27,780 com aquest, que tenia un nom i una casa. 414 00:18:27,780 --> 00:18:31,980 En Pset 3 breakout vostè utilitza en el seu conjunt manat de GRect structs-- i GOvals 415 00:18:31,980 --> 00:18:34,810 que Stanford creat per informació de clúster junts. 416 00:18:34,810 --> 00:18:38,580 I què si prenem aquesta mateixa idea les paraules clau "typedef" i "struct" 417 00:18:38,580 --> 00:18:42,890 i després una mica de matèria específica de l'estudiant, i evolucionar això en el següent: 418 00:18:42,890 --> 00:18:46,210 typedef struct node-- i node és només una ciència de la computació molt genèric 419 00:18:46,210 --> 00:18:49,980 termini per a alguna cosa en una estructura de dades, un contenidor en una estructura de dades. 420 00:18:49,980 --> 00:18:53,900 Un node reclam tindrà 1 int n, totalment senzill, 421 00:18:53,900 --> 00:18:58,810 i després una mica més críptica, aquesta segona línia, el node struct * següent. 422 00:18:58,810 --> 00:19:01,300 Però en termes menys tècnics, el que és que la segona línia 423 00:19:01,300 --> 00:19:02,980 de codi dins de les claus? 424 00:19:02,980 --> 00:19:03,737 Sí? 425 00:19:03,737 --> 00:19:04,851 >> AUDIÈNCIA: [inaudible] 426 00:19:04,851 --> 00:19:06,600 DAVID J. Malan: Un punter a un altre node. 427 00:19:06,600 --> 00:19:09,910 Així que sens dubte, la sintaxi una mica críptic. 428 00:19:09,910 --> 00:19:13,250 Però si vostè llegeix literalment, següent és el nom d'una variable. 429 00:19:13,250 --> 00:19:14,410 Quin és el seu tipus de dades? 430 00:19:14,410 --> 00:19:18,206 És una mica verbós aquest moment, però és de tipus struct node *. 431 00:19:18,206 --> 00:19:22,960 Cada vegada que hem vist alguna cosa de l'estrella, que significa que és un punter a aquest tipus de dades. 432 00:19:22,960 --> 00:19:26,810 Així que la propera és pel que sembla un punter a un node d'estructura. 433 00:19:26,810 --> 00:19:28,310 >> Ara, què és un node d'estructura? 434 00:19:28,310 --> 00:19:31,044 Bé, s'observa que vegi els mateixes paraules a la part superior dreta. 435 00:19:31,044 --> 00:19:33,960 I, en efecte, es veu també la paraula "Node" aquí baix a la part inferior esquerra. 436 00:19:33,960 --> 00:19:35,640 I això és en realitat només una conveniència. 437 00:19:35,640 --> 00:19:39,930 Tingueu en compte que en la nostra definició estudiant aquí està la paraula "estudiant" només una vegada. 438 00:19:39,930 --> 00:19:42,510 I és que un estudiant objecte no era auto-referencial. 439 00:19:42,510 --> 00:19:45,340 No hi ha res a l'interior d'un estudiant que ha d'apuntar a un altre estudiant, 440 00:19:45,340 --> 00:19:45,610 persay. 441 00:19:45,610 --> 00:19:47,630 Això seria una mena de rar en el món real. 442 00:19:47,630 --> 00:19:50,880 >> Però amb un node en una lligat llista, si volem un node 443 00:19:50,880 --> 00:19:53,970 ser referencial a un objecte similar. 444 00:19:53,970 --> 00:19:57,900 I així compte del canvi aquí no és només el que està dins de les claus. 445 00:19:57,900 --> 00:20:00,800 Però afegim la paraula "node" a la part superior, així com 446 00:20:00,800 --> 00:20:02,930 d'afegir a la part inferior en lloc de "estudiant". 447 00:20:02,930 --> 00:20:06,000 I això és només un detall tècnic de manera que, de nou, l'estructura de dades 448 00:20:06,000 --> 00:20:11,380 pot ser auto-referencial, de manera que un node pot apuntar a una altra tal node. 449 00:20:11,380 --> 00:20:13,840 >> Llavors, què és aquesta última instància significarà per a nosaltres? 450 00:20:13,840 --> 00:20:17,560 Bé, un, això dins és el contingut del nostre node. 451 00:20:17,560 --> 00:20:19,360 Aquesta cosa aquí, a dalt a la dreta, és tan 452 00:20:19,360 --> 00:20:20,860 que, de nou, podem referir-nos a nosaltres mateixos. 453 00:20:20,860 --> 00:20:23,401 I després les coses més externa, tot i que el node és un nou terme, 454 00:20:23,401 --> 00:20:25,500 potser, que segueix sent el mateix que els estudiants i el que 455 00:20:25,500 --> 00:20:27,520 estava sota la caputxa en SPL. 456 00:20:27,520 --> 00:20:31,095 >> Així que si ara volíem començar l'aplicació d'aquesta llista enllaçada, 457 00:20:31,095 --> 00:20:33,220 ¿Com podríem traduir alguna cosa com això per a codificar? 458 00:20:33,220 --> 00:20:35,350 Bé, anem a veure un exemple d'un programa que 459 00:20:35,350 --> 00:20:36,840 en realitat utilitza una llista enllaçada. 460 00:20:36,840 --> 00:20:40,870 Entre codi de distribució d'avui és un programa que es diu Llista Zero. 461 00:20:40,870 --> 00:20:44,980 I si em quedo aquesta vaig crear un super GUI simple, interfície gràfica d'usuari, 462 00:20:44,980 --> 00:20:46,460 però no deixa de ser printf. 463 00:20:46,460 --> 00:20:50,930 I ara jo mateix he donat uns quants menú options-- Eliminar, Inserir, Cercar, 464 00:20:50,930 --> 00:20:51,750 i Traverse. 465 00:20:51,750 --> 00:20:52,630 I a Surt. 466 00:20:52,630 --> 00:20:55,970 Aquestes són operacions comuns en un sol estructura de dades coneguda com una llista d'enllaços. 467 00:20:55,970 --> 00:20:58,409 >> Ara, Eliminar va a suprimir un número de la llista. 468 00:20:58,409 --> 00:21:00,200 Inseriu va a afegir un número a la llista. 469 00:21:00,200 --> 00:21:02,181 La recerca es va a veure de nombre en la llista. 470 00:21:02,181 --> 00:21:04,930 I travessa és només una forma elegant de dir, caminar a través de la llista, 471 00:21:04,930 --> 00:21:06,245 imprimir-lo, però això és tot. 472 00:21:06,245 --> 00:21:07,720 No canvieu de cap manera. 473 00:21:07,720 --> 00:21:08,570 >> Així que anem a provar això. 474 00:21:08,570 --> 00:21:10,160 Seguirem endavant i tipus 2. 475 00:21:10,160 --> 00:21:12,710 I després vaig a inserir el nombre, per exemple 9. 476 00:21:12,710 --> 00:21:13,620 Intro. 477 00:21:13,620 --> 00:21:17,480 I ara el meu programa és només programada dir, la llista és ara 9. 478 00:21:17,480 --> 00:21:20,190 Ara, si em vaig per davant i no Inseriu de nou, deixar que 479 00:21:20,190 --> 00:21:23,680 em vaig per davant i allunyar i escric en 17. 480 00:21:23,680 --> 00:21:25,770 Ara la meva llista és 9, llavors de 17 anys. 481 00:21:25,770 --> 00:21:27,750 Si ho faig s'insereixi de nou, anem a saltar un. 482 00:21:27,750 --> 00:21:32,400 En lloc de 22, d'acord amb la imatge que hem estat veient aquí, deixa anar per davant 483 00:21:32,400 --> 00:21:34,630 i inseriu el 26 proper. 484 00:21:34,630 --> 00:21:36,230 Així que vaig a escriure 26. 485 00:21:36,230 --> 00:21:37,755 La llista és la que espero. 486 00:21:37,755 --> 00:21:40,630 Però ara, només per veure si el codi serà flexible, deixeu-me que ara 487 00:21:40,630 --> 00:21:43,520 tipus 22, que almenys conceptualment, si estem 488 00:21:43,520 --> 00:21:46,520 Tenint això ordenades, que és de fet serà un altre dels objectius en aquest moment, 489 00:21:46,520 --> 00:21:48,690 ha d'anar en entre el 17 i el 26. 490 00:21:48,690 --> 00:21:50,270 Així que vaig prémer Enter. 491 00:21:50,270 --> 00:21:51,380 De fet, això funciona. 492 00:21:51,380 --> 00:21:54,950 I ara permetin-me inserir el passat, per la imatge, 34. 493 00:21:54,950 --> 00:21:55,450 >> Bé. 494 00:21:55,450 --> 00:21:58,980 Així que per ara m'ho dius a mi estipulo que Esborrar i Traverse i Search fan, 495 00:21:58,980 --> 00:21:59,760 de fet, treballar. 496 00:21:59,760 --> 00:22:04,180 De fet, si jo corro recerca, anem a buscar el número 22, Enter. 497 00:22:04,180 --> 00:22:05,010 S'han trobat 22. 498 00:22:05,010 --> 00:22:07,580 Així que això és el que aquesta programa de llista Zero fa. 499 00:22:07,580 --> 00:22:10,230 >> Però el que realment està passant que implementa això? 500 00:22:10,230 --> 00:22:14,530 Bé, primer vaig a tenir, i de fet Jo tinc, un arxiu anomenat list0.h. 501 00:22:14,530 --> 00:22:16,540 502 00:22:16,540 --> 00:22:20,690 I en algun lloc existeix aquest línia, typedef, struct node, 503 00:22:20,690 --> 00:22:24,850 llavors tinc els meus claus, int n, i llavors struct-- quina és la definició? 504 00:22:24,850 --> 00:22:26,530 505 00:22:26,530 --> 00:22:28,545 Struct node següent. 506 00:22:28,545 --> 00:22:29,920 507 00:22:29,920 --> 00:22:31,045 Així que tenim l'estrella. 508 00:22:31,045 --> 00:22:33,420 Ara tècnicament ens fiquem en l'hàbit de dibuixar aquí. 509 00:22:33,420 --> 00:22:35,670 És possible que vegi els llibres de text i referències en línia ho fan allà. 510 00:22:35,670 --> 00:22:36,660 És funcionalment equivalent. 511 00:22:36,660 --> 00:22:37,980 De fet, aquest és una mica més típic. 512 00:22:37,980 --> 00:22:40,563 Però seré coherent amb el que que vam fer l'última vegada i fem això. 513 00:22:40,563 --> 00:22:42,350 I després, finalment, vaig a fer això. 514 00:22:42,350 --> 00:22:45,550 >> Així que en un arxiu de capçalera en algun lloc, en list0.h 515 00:22:45,550 --> 00:22:49,200 avui és aquesta definició struct, i potser algunes altres coses. 516 00:22:49,200 --> 00:22:52,580 Mentrestant, en list0c hi serà un parell de coses. 517 00:22:52,580 --> 00:22:54,740 Però anem a simplement iniciar i no acabar això. 518 00:22:54,740 --> 00:22:59,690 List0.h és un arxiu que vull incloure en el meu arxiu C. 519 00:22:59,690 --> 00:23:03,910 I després, en algun moment m'estic tindrà int, principal, anul·larà. 520 00:23:03,910 --> 00:23:06,530 I després vaig a tenen algunes coses per fer aquí. 521 00:23:06,530 --> 00:23:10,620 Jo també vaig a tenir una prototip, com buit, recerca, int, 522 00:23:10,620 --> 00:23:13,610 n, el propòsit a la vida és per buscar un element. 523 00:23:13,610 --> 00:23:18,310 I llavors aquí jo reclam a el codi d'avui, nul recerca, int, n, 524 00:23:18,310 --> 00:23:21,020 hi ha punt i coma, però les claus obertes. 525 00:23:21,020 --> 00:23:25,049 I ara vull buscar alguna manera un element en aquesta llista. 526 00:23:25,049 --> 00:23:27,340 Però nosaltres no tenim prou informació a la pantalla encara. 527 00:23:27,340 --> 00:23:29,800 No tinc en realitat representada la pròpia llista. 528 00:23:29,800 --> 00:23:33,070 Així que una manera que podríem aplicar una llista enllaçada en un programa 529 00:23:33,070 --> 00:23:37,520 està com que vull fer alguna cosa com declaren llista enllaçada aquí. 530 00:23:37,520 --> 00:23:40,520 Per simplificar, faré aquest mundial, tot i que en general, ens 531 00:23:40,520 --> 00:23:41,645 No hauríeu de fer massa. 532 00:23:41,645 --> 00:23:43,260 Però va a simplificar aquest exemple. 533 00:23:43,260 --> 00:23:45,890 Així que vull declarar una llista enllaçada aquí. 534 00:23:45,890 --> 00:23:47,010 Ara, com podria jo fer això? 535 00:23:47,010 --> 00:23:48,810 536 00:23:48,810 --> 00:23:50,750 >> Aquí hi ha la foto d'una llista enllaçada. 537 00:23:50,750 --> 00:23:53,030 I realment no em conèixer al moment com 538 00:23:53,030 --> 00:23:56,710 Vaig a anar sobre el que representa tantes coses amb un sol 539 00:23:56,710 --> 00:23:58,040 variable en la memòria. 540 00:23:58,040 --> 00:23:59,160 Però pensar de nou un moment. 541 00:23:59,160 --> 00:24:00,830 Durant tot aquest temps que hem tingut cordes, que després 542 00:24:00,830 --> 00:24:02,913 revelat a ser matrius de personatges, que després 543 00:24:02,913 --> 00:24:05,740 revelat a ser només un punter fins al primer caràcter 544 00:24:05,740 --> 00:24:08,890 en una matriu de caràcters això està acabada en nul. 545 00:24:08,890 --> 00:24:13,530 Així que per aquesta lògica, i amb aquest foto tipus de sembrar els seus pensaments, 546 00:24:13,530 --> 00:24:17,964 el que necessitem realment escrivim en la nostra codi per representar una llista enllaçada? 547 00:24:17,964 --> 00:24:21,130 Quina part d'aquesta informació necessitem capturar en codi C, què li diries? 548 00:24:21,130 --> 00:24:22,654 549 00:24:22,654 --> 00:24:23,154 Sí? 550 00:24:23,154 --> 00:24:24,738 >> AUDIÈNCIA: Necessitem un punter a un node. 551 00:24:24,738 --> 00:24:26,237 DAVID J. Malan: Un punter a un node. 552 00:24:26,237 --> 00:24:29,320 En particular, el que faria amb el seu node instints ser mantenir un punter? 553 00:24:29,320 --> 00:24:30,026 >> AUDIÈNCIA: El primer node. 554 00:24:30,026 --> 00:24:31,942 >> DAVID J. Malan: Sí, probablement només la primera. 555 00:24:31,942 --> 00:24:34,030 I noti, la primera node és una forma diferent. 556 00:24:34,030 --> 00:24:37,690 És només la meitat de la grandària de l'estructura, perquè és de fet només un punter. 557 00:24:37,690 --> 00:24:44,650 Així que el que realment pot fer és declarar una llista enllaçada sigui de node de tipus *. 558 00:24:44,650 --> 00:24:47,780 I anem a anomenar primer i inicialitzar a null. 559 00:24:47,780 --> 00:24:49,910 Així nul, de nou, és procedent en la imatge aquí. 560 00:24:49,910 --> 00:24:53,620 No només s'utilitza null com com un especial valor de retorn per a coses com getString 561 00:24:53,620 --> 00:24:57,770 i malloc, null és també el zero punter, la falta d'un punter, 562 00:24:57,770 --> 00:24:58,430 si es vol. 563 00:24:58,430 --> 00:25:00,309 Només vol dir que encara no hi ha res aquí. 564 00:25:00,309 --> 00:25:02,100 Ara en primer lloc, que hauria pogut cridat a aquest res. 565 00:25:02,100 --> 00:25:04,200 Jo podria haver anomenat "llista" o qualsevol nombre d'altres coses. 566 00:25:04,200 --> 00:25:06,960 Però jo estic anomenant "primer" perquè línies amunt amb aquesta imatge. 567 00:25:06,960 --> 00:25:10,280 Així que igual que una cadena es pot representar amb la direcció del seu primer byte, 568 00:25:10,280 --> 00:25:11,280 pel que pot una llista enllaçada. 569 00:25:11,280 --> 00:25:13,480 I veurem altres dades poden representar estructures 570 00:25:13,480 --> 00:25:16,700 amb només un punter, una fletxa de 32 bits, assenyalant 571 00:25:16,700 --> 00:25:18,740 en el primer node de l'estructura. 572 00:25:18,740 --> 00:25:20,340 >> Però ara anem a anticipar un problema. 573 00:25:20,340 --> 00:25:23,230 Si jo només estic recordant en el meu programa de la direcció 574 00:25:23,230 --> 00:25:27,220 del primer node, la primera rectangle en aquesta estructura de dades, 575 00:25:27,220 --> 00:25:31,760 el que havia ser millor el cas sobre el execució de la resta de la cistella? 576 00:25:31,760 --> 00:25:35,820 Què és un detall clau que està passant per assegurar que funciona en realitat? 577 00:25:35,820 --> 00:25:39,250 I per "realment funciona" I dir, com un string, 578 00:25:39,250 --> 00:25:42,180 ens deixa anar des del primer caràcter en el nom de Davin a la segona, 579 00:25:42,180 --> 00:25:44,755 a la tercera, a la quart, fins al final, 580 00:25:44,755 --> 00:25:47,880 Com sabem quan estem al final d'una llista enllaçada que té aquest aspecte? 581 00:25:47,880 --> 00:25:50,035 582 00:25:50,035 --> 00:25:50,660 Quan és nul. 583 00:25:50,660 --> 00:25:53,640 I jo he representat aquest tipus de com com una força enginyer elèctric, 584 00:25:53,640 --> 00:25:56,420 amb la poca terra símbol, de tota mena. 585 00:25:56,420 --> 00:25:58,246 Però això només significa nul en aquest cas. 586 00:25:58,246 --> 00:26:00,370 Vostè pot dibuixar qualsevol nombre maneres, però aquest autor 587 00:26:00,370 --> 00:26:02,800 passat a utilitzar aquest símbol aquí. 588 00:26:02,800 --> 00:26:06,260 >> Mentre estem encadenant tots aquests nodes entre si, 589 00:26:06,260 --> 00:26:08,600 només recordar on la primera és, sempre 590 00:26:08,600 --> 00:26:11,760 com posem un símbol especial a l'últim node de la llista, 591 00:26:11,760 --> 00:26:15,130 i farem servir nul, perquè això és el que tenim a la nostra disposició, 592 00:26:15,130 --> 00:26:16,480 aquesta llista és completa. 593 00:26:16,480 --> 00:26:20,190 I encara que jo només li donen un punter a el primer element, vostè, el programador, 594 00:26:20,190 --> 00:26:22,486 sens dubte pot accedir a la resta de la mateixa. 595 00:26:22,486 --> 00:26:24,360 Però anem a deixar que les seves ments passejar una mica, 596 00:26:24,360 --> 00:26:26,140 si no ho són ja bastant wandered-- el que és 597 00:26:26,140 --> 00:26:28,723 serà el temps d'execució de trobar res en aquesta llista? 598 00:26:28,723 --> 00:26:30,450 599 00:26:30,450 --> 00:26:33,470 Maleïda sigui, és gran O de n, qual cosa no és dolent, per ser justos. 600 00:26:33,470 --> 00:26:34,800 Però és lineal. 601 00:26:34,800 --> 00:26:37,980 Hem renunciat al que característica d'arrays movent més 602 00:26:37,980 --> 00:26:43,130 a la imatge de manera dinàmica entrellaçats o nodes vinculats? 603 00:26:43,130 --> 00:26:44,970 604 00:26:44,970 --> 00:26:46,687 Hem renunciat accés aleatori. 605 00:26:46,687 --> 00:26:48,770 Una matriu és agradable perquè tot matemàticament 606 00:26:48,770 --> 00:26:50,340 ha tornat a l'esquena amb esquena amb esquena. 607 00:26:50,340 --> 00:26:52,370 Tot i que aquesta foto es veu bastant, i fins i tot 608 00:26:52,370 --> 00:26:55,830 encara que sembla que aquests nodes estan ben separats, en realitat 609 00:26:55,830 --> 00:26:56,830 podrien estar en qualsevol part. 610 00:26:56,830 --> 00:27:01,590 Ox1, OX50, Ox123, Ox99, aquests nodes podrien estar en qualsevol part. 611 00:27:01,590 --> 00:27:05,960 A causa de malloc fa assignar memòria de la pila, però en qualsevol lloc en el munt. 612 00:27:05,960 --> 00:27:09,080 No necessàriament sap que és estarà esquena amb esquena amb esquena. 613 00:27:09,080 --> 00:27:12,460 I així aquesta foto a la realitat de No serà bastant aquesta bonica. 614 00:27:12,460 --> 00:27:16,140 >> Així que prendrà una mica de treballar per implementar aquesta funció. 615 00:27:16,140 --> 00:27:17,880 Així que anem a posar en pràctica la recerca ara. 616 00:27:17,880 --> 00:27:20,250 I anem a veure una mena de forma intel ligent de fer-ho. 617 00:27:20,250 --> 00:27:24,660 Així que si jo sóc una funció de recerca i Em donen una variable, sencer n 618 00:27:24,660 --> 00:27:28,490 a buscar, necessito saber la nova sintaxi per mirar dins 619 00:27:28,490 --> 00:27:32,400 d'una estructura que és assenyalat, per trobar n. 620 00:27:32,400 --> 00:27:33,210 Així que farem això. 621 00:27:33,210 --> 00:27:36,030 >> Així que primer vaig a anar endavant i declarar un node *. 622 00:27:36,030 --> 00:27:39,400 I jo vaig a dir- punter, només per convenció. 623 00:27:39,400 --> 00:27:41,710 I jo vaig a inicialitzar a primera. 624 00:27:41,710 --> 00:27:43,770 I ara que puc fer això en un nombre de maneres. 625 00:27:43,770 --> 00:27:45,436 Però em vaig a prendre un enfocament comú. 626 00:27:45,436 --> 00:27:50,180 Mentre punter no és igual a nul, i això és una sintaxi vàlida. 627 00:27:50,180 --> 00:27:54,550 I només significa fer el següent, de manera que sempre que vostè no està apuntant al no-res. 628 00:27:54,550 --> 00:27:55,800 Què vull fer? 629 00:27:55,800 --> 00:28:01,939 >> Si dot punter n, deixar-me tornar perquè, equals-- igual què? 630 00:28:01,939 --> 00:28:03,105 Quin valor que estic buscant? 631 00:28:03,105 --> 00:28:04,920 632 00:28:04,920 --> 00:28:06,590 El major real que va passar. 633 00:28:06,590 --> 00:28:09,020 Així que aquí està una altra de les característiques de C i molts idiomes. 634 00:28:09,020 --> 00:28:13,705 Tot i que el node d'estructura anomenada té un valor de n, totalment legítim 635 00:28:13,705 --> 00:28:17,530 tenir també un argument locals o variable anomenada n. 636 00:28:17,530 --> 00:28:20,085 Perquè nosaltres també, amb els ulls humans, poden distingir 637 00:28:20,085 --> 00:28:22,087 que aquest n és presumiblement diferent d'aquest n. 638 00:28:22,087 --> 00:28:23,420 Com que la sintaxi és diferent. 639 00:28:23,420 --> 00:28:26,211 Tens un punt i un punter, mentre que aquest no té tal cosa. 640 00:28:26,211 --> 00:28:27,290 Així que això està bé. 641 00:28:27,290 --> 00:28:29,120 Això està bé trucar les mateixes coses. 642 00:28:29,120 --> 00:28:32,380 >> Si jo et trobo això, estic voldrà fer alguna cosa 643 00:28:32,380 --> 00:28:35,000 com vam anunciar que ens trobem n. 644 00:28:35,000 --> 00:28:37,930 I això l'hi deixem com comentar o codi pseudocodi. 645 00:28:37,930 --> 00:28:40,190 Si no, i aquí hi ha la L'interessant, el que 646 00:28:40,190 --> 00:28:47,320 faig el que vull fer si el node actual no conté n que m'importa? 647 00:28:47,320 --> 00:28:50,700 Com puc aconseguir el següent? 648 00:28:50,700 --> 00:28:53,710 Si el meu dit a l' moment és PTR, i és 649 00:28:53,710 --> 00:28:55,920 que apunta al que sigui primer està apuntant a, 650 00:28:55,920 --> 00:28:59,290 Com puc moure el meu dit al següent node en el codi? 651 00:28:59,290 --> 00:29:01,915 Bé, quina és la ruta de navegació que estem seguirà en aquest cas? 652 00:29:01,915 --> 00:29:03,464 653 00:29:03,464 --> 00:29:04,380 AUDIÈNCIA: [inaudible]. 654 00:29:04,380 --> 00:29:05,630 DAVID J. Malan: Sí, així que la propera. 655 00:29:05,630 --> 00:29:06,640 656 00:29:06,640 --> 00:29:09,824 Així que si torno al meu codi aquí, de fet, estic 657 00:29:09,824 --> 00:29:12,990 seguirà endavant i dir punter, que és només una variable-- temporal és 658 00:29:12,990 --> 00:29:15,320 un nom estrany, ptr, però és com temp-- 659 00:29:15,320 --> 00:29:19,234 Vaig a establir punter igual al que sigui punter és-- 660 00:29:19,234 --> 00:29:22,150 i de nou, això serà un d'errors, per inserir un punt moment-- següent. 661 00:29:22,150 --> 00:29:23,551 662 00:29:23,551 --> 00:29:26,550 En altres paraules, em vaig a prendre el meu dit que està assenyalant a aquest node 663 00:29:26,550 --> 00:29:31,247 aquí i jo vaig a dir, ja saps què, mireu el següent camp 664 00:29:31,247 --> 00:29:33,330 i moure el dit per com sigui que s'assenyala a. 665 00:29:33,330 --> 00:29:35,163 I això va a repetir, repetir, repetir. 666 00:29:35,163 --> 00:29:37,630 Però quan ho fa el meu dit deixar de fer res en absolut? 667 00:29:37,630 --> 00:29:40,095 Tan aviat com quina línia de codi a puntades? 668 00:29:40,095 --> 00:29:40,970 AUDIÈNCIA: [inaudible] 669 00:29:40,970 --> 00:29:43,060 DAVID J. Malan: Si el punt mentre punter no és igual a null. 670 00:29:43,060 --> 00:29:44,900 En algun moment de la meva dit de estarà apuntant a nul 671 00:29:44,900 --> 00:29:47,070 i jo vaig a fer aquest és el final d'aquesta llista. 672 00:29:47,070 --> 00:29:48,910 Ara, això és una mica mentida piadosa per la simplicitat. 673 00:29:48,910 --> 00:29:51,580 Resulta que tot i que acaba d'assabentar aquesta notació de punts 674 00:29:51,580 --> 00:29:55,220 per a estructures, punter no és una estructura. 675 00:29:55,220 --> 00:29:56,580 ptr és què? 676 00:29:56,580 --> 00:29:58,350 Només per ser més primmirada. 677 00:29:58,350 --> 00:29:59,720 678 00:29:59,720 --> 00:30:01,360 És un punter a un node. 679 00:30:01,360 --> 00:30:03,120 No és un node en si. 680 00:30:03,120 --> 00:30:06,650 Si no tingués l'estrella aquí, punter absolutely-- és un node. 681 00:30:06,650 --> 00:30:08,650 Això és com una setmana declaració d'una variable, 682 00:30:08,650 --> 00:30:10,120 tot i que la paraula "node" és nova. 683 00:30:10,120 --> 00:30:13,860 >> Però tan aviat com s'introdueix un estrella, ara és un punter a un node. 684 00:30:13,860 --> 00:30:17,960 I, per desgràcia no es pot utilitzar la notació de punts per a un punter. 685 00:30:17,960 --> 00:30:21,070 Vostè ha de fer servir la fletxa notació, que, sorprenentment, 686 00:30:21,070 --> 00:30:23,470 és la primera vegada que un tros de sintaxi sembla intuïtiu. 687 00:30:23,470 --> 00:30:25,245 Això es veu, literalment, com una fletxa. 688 00:30:25,245 --> 00:30:26,370 I això és una bona cosa. 689 00:30:26,370 --> 00:30:28,995 I aquí baix, literalment, s'assembla a una fletxa. 690 00:30:28,995 --> 00:30:31,870 Així que crec que aquesta és la la-- no ho faig Crec que estic massa cometre aquí-- I 691 00:30:31,870 --> 00:30:34,120 Crec que és l'última peça nova de la sintaxi que veurem. 692 00:30:34,120 --> 00:30:36,500 I per sort, és de fet una mica més intuïtiu. 693 00:30:36,500 --> 00:30:40,090 >> Ara, per a aquells de vostès que podrien preferir la manera antiga, 694 00:30:40,090 --> 00:30:42,550 encara pot utilitzar la notació de punts. 695 00:30:42,550 --> 00:30:45,380 Però segons Dilluns de conversa, primer 696 00:30:45,380 --> 00:30:50,530 que hagi d'anar-hi, anar a aquest abordar, i després accedir al camp. 697 00:30:50,530 --> 00:30:51,897 Així que això també és correcte. 698 00:30:51,897 --> 00:30:53,730 I, francament, aquest és un poc més pedant. 699 00:30:53,730 --> 00:30:56,530 Vostè està literalment dient desreferenciar el punter i anar-hi. 700 00:30:56,530 --> 00:30:59,320 Llavors agafa .n, el camp anomenat n. 701 00:30:59,320 --> 00:31:01,370 Però, francament, ningú vol per escriure o llegir això. 702 00:31:01,370 --> 00:31:03,620 I així el món va inventar la notació fletxa, que 703 00:31:03,620 --> 00:31:06,980 és equivalent, idèntic, és només el sucre sintàctica. 704 00:31:06,980 --> 00:31:10,570 Així que una forma elegant de dir això es veu millor, o es veu més simple. 705 00:31:10,570 --> 00:31:12,296 >> Així que ara me'n vaig a fer una altra cosa. 706 00:31:12,296 --> 00:31:15,420 Vaig a dir "break" Una vegada que he trobar, així que no la guardo a la recerca d'ella. 707 00:31:15,420 --> 00:31:17,620 Però aquesta és l'essència d'una funció de cerca. 708 00:31:17,620 --> 00:31:21,710 Però és molt més fàcil, al final, no caminar a través del codi. 709 00:31:21,710 --> 00:31:25,570 Aquesta és de fet l'aplicació formal de recerca de codi de distribució actual. 710 00:31:25,570 --> 00:31:30,530 M'atreveixo a dir que la inserció no és particularment divertit caminar per 711 00:31:30,530 --> 00:31:33,180 visualment, ni tampoc eliminar, fins i tot encara que al final del dia 712 00:31:33,180 --> 00:31:35,460 es redueixen a bastant heurístiques simples. 713 00:31:35,460 --> 00:31:36,330 >> Així que farem això. 714 00:31:36,330 --> 00:31:39,250 Si vostè humor amb mi aquí, ho vaig fer portar un munt de boles d'estrès. 715 00:31:39,250 --> 00:31:40,620 Em va portar un munt de nombres. 716 00:31:40,620 --> 00:31:46,562 I podríem aconseguir uns pocs voluntaris per representar 9, 17, 20, 22, 29, i 34? 717 00:31:46,562 --> 00:31:48,270 Així que, essencialment tot el món qui està aquí avui. 718 00:31:48,270 --> 00:31:50,170 719 00:31:50,170 --> 00:31:52,760 Aquest va ser un, dos, tres, quatre, cinc, a sis persones. 720 00:31:52,760 --> 00:31:55,740 I m'han demanat que ir-- veure, no una a la part posterior aixeca les seves mans. 721 00:31:55,740 --> 00:32:01,910 Bé, un, dos, tres, quatre, cinc-- m'ho dius a mi carregar balanç-- 06:00. 722 00:32:01,910 --> 00:32:03,051 OK, anem fins a sis. 723 00:32:03,051 --> 00:32:04,050 Necessitarem altres persones. 724 00:32:04,050 --> 00:32:05,460 Vam portar boles d'estrès addicionals. 725 00:32:05,460 --> 00:32:08,200 I si pogués, per un moment, la línia 726 00:32:08,200 --> 00:32:10,490 vostès just t'agrada aquesta foto aquí. 727 00:32:10,490 --> 00:32:15,200 728 00:32:15,200 --> 00:32:15,959 >> Bé. 729 00:32:15,959 --> 00:32:17,125 Anem a veure, com et dius? 730 00:32:17,125 --> 00:32:17,550 >> AUDIÈNCIA: Andrew. 731 00:32:17,550 --> 00:32:18,800 >> DAVID J. Malan: Andrew, ets el número 9. 732 00:32:18,800 --> 00:32:19,540 Encantada de conèixer-te. 733 00:32:19,540 --> 00:32:20,400 Aquí tens. 734 00:32:20,400 --> 00:32:21,593 735 00:32:21,593 --> 00:32:22,176 AUDIÈNCIA: Jen. 736 00:32:22,176 --> 00:32:22,662 DAVID J. Malan: Jen. 737 00:32:22,662 --> 00:32:23,162 David. 738 00:32:23,162 --> 00:32:23,765 Número 17. 739 00:32:23,765 --> 00:32:24,950 740 00:32:24,950 --> 00:32:25,450 Sí? 741 00:32:25,450 --> 00:32:26,400 >> AUDIÈNCIA: Sóc Julia. 742 00:32:26,400 --> 00:32:26,980 >> DAVID J. Malan: Julia, David. 743 00:32:26,980 --> 00:32:27,545 Número 20. 744 00:32:27,545 --> 00:32:28,507 745 00:32:28,507 --> 00:32:29,340 AUDIÈNCIA: Cristià. 746 00:32:29,340 --> 00:32:30,715 DAVID J. Malan: Cristiano, David. 747 00:32:30,715 --> 00:32:31,541 Número 22. 748 00:32:31,541 --> 00:32:32,040 I? 749 00:32:32,040 --> 00:32:32,649 >> AUDIÈNCIA: JP. 750 00:32:32,649 --> 00:32:33,440 DAVID J. Malan: JP. 751 00:32:33,440 --> 00:32:34,880 Número 29. 752 00:32:34,880 --> 00:32:37,080 Així que endavant i obtenir en-- Uh oh. 753 00:32:37,080 --> 00:32:38,486 754 00:32:38,486 --> 00:32:38,985 Uh oh. 755 00:32:38,985 --> 00:32:39,650 756 00:32:39,650 --> 00:32:40,150 Standby. 757 00:32:40,150 --> 00:32:41,360 758 00:32:41,360 --> 00:32:42,390 20. 759 00:32:42,390 --> 00:32:43,682 Algú té un marcador? 760 00:32:43,682 --> 00:32:44,890 AUDIÈNCIA: Tinc un Sharpie. 761 00:32:44,890 --> 00:32:45,660 DAVID J. Malan: Tens 1 Sharpie? 762 00:32:45,660 --> 00:32:46,159 Okay. 763 00:32:46,159 --> 00:32:47,577 764 00:32:47,577 --> 00:32:49,160 I algú té un tros de paper? 765 00:32:49,160 --> 00:32:51,562 766 00:32:51,562 --> 00:32:52,270 Deseu la conferència. 767 00:32:52,270 --> 00:32:53,810 768 00:32:53,810 --> 00:32:55,362 Vingui. 769 00:32:55,362 --> 00:32:56,320 AUDIÈNCIA: el tenim. 770 00:32:56,320 --> 00:32:57,600 DAVID J. Malan: ho aconseguim? 771 00:32:57,600 --> 00:32:58,577 Molt bé, gràcies. 772 00:32:58,577 --> 00:33:01,380 773 00:33:01,380 --> 00:33:02,520 Aquí anem. 774 00:33:02,520 --> 00:33:03,582 ¿Era això de tu? 775 00:33:03,582 --> 00:33:04,540 Acabes de salvar el dia. 776 00:33:04,540 --> 00:33:05,670 777 00:33:05,670 --> 00:33:07,220 Així 29. 778 00:33:07,220 --> 00:33:10,510 779 00:33:10,510 --> 00:33:11,110 Bé. 780 00:33:11,110 --> 00:33:13,360 781 00:33:13,360 --> 00:33:14,890 El escric malament el 29, però no està malament. 782 00:33:14,890 --> 00:33:15,720 Seguir endavant. 783 00:33:15,720 --> 00:33:18,114 Molt bé, et donaré la seva ploma cap enrere momentàniament. 784 00:33:18,114 --> 00:33:19,280 Així que tenim a aquesta gent aquí. 785 00:33:19,280 --> 00:33:20,330 Anem a tenir un altre. 786 00:33:20,330 --> 00:33:23,750 Gabe, vols jugar el primer element en aquesta llista? 787 00:33:23,750 --> 00:33:25,705 Et necessitem perquè apunti a aquesta bona gent. 788 00:33:25,705 --> 00:33:26,930 789 00:33:26,930 --> 00:33:31,030 Així que 9, 17, 20, 22, espècie de 29, i després 34. 790 00:33:31,030 --> 00:33:32,160 791 00:33:32,160 --> 00:33:33,325 ¿Vam perdre a algú? 792 00:33:33,325 --> 00:33:33,950 Tinc un 34. 793 00:33:33,950 --> 00:33:36,730 On hizo-- bé, que vol ser 34? 794 00:33:36,730 --> 00:33:37,605 Bé, anem cap amunt, 34. 795 00:33:37,605 --> 00:33:39,280 796 00:33:39,280 --> 00:33:41,220 Molt bé, això serà bé val la pena el clímax. 797 00:33:41,220 --> 00:33:41,550 Quin és el teu nom? 798 00:33:41,550 --> 00:33:42,040 >> AUDIÈNCIA: Peter. 799 00:33:42,040 --> 00:33:43,456 >> DAVID J. Malan: Peter, anem a dalt. 800 00:33:43,456 --> 00:33:46,810 Molt bé, així que aquí té un tot grup de nodes. 801 00:33:46,810 --> 00:33:49,060 Cada un de vosaltres representa un d'aquests rectangles. 802 00:33:49,060 --> 00:33:51,930 I Gabe, el poc estrany l'home, representa en primer lloc. 803 00:33:51,930 --> 00:33:54,850 Així que el seu punter és una mica més petit a la pantalla de tots els altres. 804 00:33:54,850 --> 00:33:58,120 I en aquest cas, cadascun de la seva esquerra mans va a apuntar cap avall o bé, 805 00:33:58,120 --> 00:34:01,085 qual cosa representa una nul, de manera que només l'absència d'un punter, 806 00:34:01,085 --> 00:34:03,210 o que estarà apuntant en un node al costat de vostè. 807 00:34:03,210 --> 00:34:05,440 >> Així que ara mateix, si adornes vostès com la imatge 808 00:34:05,440 --> 00:34:07,585 aquí, seguir endavant i punt l'un a l'altre, amb Gabe 809 00:34:07,585 --> 00:34:11,030 en particular, apuntant a número 9 per representar la llista. 810 00:34:11,030 --> 00:34:14,050 Acceptar, i el número 34, la mà esquerra només han d'estar apuntant cap a terra. 811 00:34:14,050 --> 00:34:15,750 >> Acceptar, pel que aquesta és la llista enllaçada. 812 00:34:15,750 --> 00:34:17,580 Així que aquest és l'escenari en qüestió. 813 00:34:17,580 --> 00:34:20,210 I, de fet, això és representatiu d'una classe de problemes 814 00:34:20,210 --> 00:34:21,929 que vostè pot tractar de resoldre amb el codi. 815 00:34:21,929 --> 00:34:25,020 Vostè vol inserir en última instància un nou element a la llista. 816 00:34:25,020 --> 00:34:27,494 En aquest cas, anem a tractar d'inserir el número 55. 817 00:34:27,494 --> 00:34:28,500 818 00:34:28,500 --> 00:34:30,860 Però no serà diferents casos a considerar. 819 00:34:30,860 --> 00:34:34,409 I, de fet, això serà una de la gran imatge menjar per emportar aquí, és, 820 00:34:34,409 --> 00:34:35,659 ¿Quins són els diferents casos. 821 00:34:35,659 --> 00:34:39,120 Quins són els diferents si les condicions o branques que el seu programa podria tenir? 822 00:34:39,120 --> 00:34:42,024 >> Bé, el número al qual està intentant inserció, que ara sabem que ser 55, 823 00:34:42,024 --> 00:34:44,650 però si vostè no ho sabia per endavant, m'atreveixo a dir 824 00:34:44,650 --> 00:34:47,840 cau en almenys tres possibles situacions. 825 00:34:47,840 --> 00:34:49,717 On podria ser un nou element? 826 00:34:49,717 --> 00:34:51,050 AUDIÈNCIA: I al final o al mig. 827 00:34:51,050 --> 00:34:54,150 DAVID J. Malan: Al final, en el mitjà, o al principi. 828 00:34:54,150 --> 00:34:56,650 Així que jo reclam que hi ha almenys tres problemes que han de resoldre. 829 00:34:56,650 --> 00:34:58,691 Anem a triar el que és potser possiblement el més simple 830 00:34:58,691 --> 00:35:01,090 un, quan l'element nou pertany al principi. 831 00:35:01,090 --> 00:35:04,040 Així que vaig a tenir prou codi com la recerca, que només vaig escriure. 832 00:35:04,040 --> 00:35:07,670 I jo tindré ptr, que Vaig represento aquí amb el dit, 833 00:35:07,670 --> 00:35:08,370 com sempre. 834 00:35:08,370 --> 00:35:12,430 >> I recorda, quin valor vam inicialitzem ptr a? 835 00:35:12,430 --> 00:35:15,300 Així que hem inicialitzat en null inicialment. 836 00:35:15,300 --> 00:35:16,410 837 00:35:16,410 --> 00:35:19,770 Però llavors què vam fer una vegada que estaven dins de la nostra funció de cerca? 838 00:35:19,770 --> 00:35:20,940 839 00:35:20,940 --> 00:35:24,870 La fixem igual al primer, el que no vol dir fer això. 840 00:35:24,870 --> 00:35:25,890 841 00:35:25,890 --> 00:35:30,570 Si fix ptr igual al primer, el que ha de ser realment la mà apuntant a? 842 00:35:30,570 --> 00:35:31,070 Dreta. 843 00:35:31,070 --> 00:35:33,290 Així que si Gabe i jo anem ser valors iguals aquí, 844 00:35:33,290 --> 00:35:34,760 necessitem tant el punt en el número 9. 845 00:35:34,760 --> 00:35:36,420 >> Així que aquest va ser el començament de la nostra història. 846 00:35:36,420 --> 00:35:38,700 I ara això és només senzill, tot i que la sintaxi és nova. 847 00:35:38,700 --> 00:35:40,580 Conceptualment això és només cerca lineal. 848 00:35:40,580 --> 00:35:42,750 Is 55, igual a 9? 849 00:35:42,750 --> 00:35:45,559 O més aviat, diguem menys de 9. 850 00:35:45,559 --> 00:35:47,600 Perquè jo estic tractant d' esbrinar on posar 55. 851 00:35:47,600 --> 00:35:51,270 Menys de 9, a menys de 17, menys de 20, menys de 22, menys de 29, 852 00:35:51,270 --> 00:35:52,510 menys de 34, no. 853 00:35:52,510 --> 00:35:55,080 Així que ara estem en el cas un almenys tres. 854 00:35:55,080 --> 00:35:59,910 >> Si vull inserir 55 per aquí, el que línies de necessitat codi s'executen? 855 00:35:59,910 --> 00:36:01,890 Com funciona aquest quadre de els éssers humans han de canviar? 856 00:36:01,890 --> 00:36:03,181 Què faig amb la meva mà esquerra? 857 00:36:03,181 --> 00:36:04,530 858 00:36:04,530 --> 00:36:07,360 Això hauria de ser nul inicialment, perquè estic al final de la llista. 859 00:36:07,360 --> 00:36:09,318 I el que hauria de passar aquí amb Peter, oi? 860 00:36:09,318 --> 00:36:10,520 861 00:36:10,520 --> 00:36:12,430 Ell, òbviament, va apuntar a mi. 862 00:36:12,430 --> 00:36:15,580 Així que jo reclam que hi ha almenys dos línies de codi en el codi d'exemple a partir d'avui 863 00:36:15,580 --> 00:36:18,570 això va a implementar aquest escenari de l'addició de 55 a la cua. 864 00:36:18,570 --> 00:36:20,950 I podria tenir algú hop i només representen el 55? 865 00:36:20,950 --> 00:36:22,200 Molt bé, vostè és el nou 55. 866 00:36:22,200 --> 00:36:23,580 867 00:36:23,580 --> 00:36:27,054 >> Així que ara el que si que ve escenari es presenta, 868 00:36:27,054 --> 00:36:29,720 i volem inserir al començant o el cap d'aquesta llista? 869 00:36:29,720 --> 00:36:31,100 I quin és el seu nom, el número 55? 870 00:36:31,100 --> 00:36:31,420 >> AUDIÈNCIA: Jack. 871 00:36:31,420 --> 00:36:32,295 >> DAVID J. Malan: Jack? 872 00:36:32,295 --> 00:36:33,585 Bé, encantat de conèixer-te. 873 00:36:33,585 --> 00:36:34,210 Benvingut a bord. 874 00:36:34,210 --> 00:36:36,640 Així que ara anem a inserir, per exemple, el número 5. 875 00:36:36,640 --> 00:36:39,840 Aquí hi ha el segon cas de la 3 se'ns va ocórrer abans. 876 00:36:39,840 --> 00:36:43,050 Així que si 5 pertany al principi, anem a veure com ens trobem amb que fos. 877 00:36:43,050 --> 00:36:46,310 Puc inicialitzar meu ptr punter a número 9 de nou. 878 00:36:46,310 --> 00:36:49,140 I em vaig adonar, oh, 5 és menor que 9. 879 00:36:49,140 --> 00:36:50,880 Així que arreglar aquesta imatge per a nosaltres. 880 00:36:50,880 --> 00:36:54,820 ¿Quines mans, Gabe o David de o-- ¿com es diu el número del 9? 881 00:36:54,820 --> 00:36:55,740 >> AUDIÈNCIA: Jen. 882 00:36:55,740 --> 00:36:58,406 >> DAVID J. Malan: mans-- de Jen quina de les nostres mans que hagi de canviar? 883 00:36:58,406 --> 00:36:58,905 884 00:36:58,905 --> 00:37:00,970 OK, així que Gabe assenyala en què ara? 885 00:37:00,970 --> 00:37:01,640 En mi. 886 00:37:01,640 --> 00:37:02,750 Jo sóc el nou node. 887 00:37:02,750 --> 00:37:04,870 Així que vaig a classe de moviment aquí per veure-ho visualment. 888 00:37:04,870 --> 00:37:06,435 I mentrestant, què he d'assenyalar que? 889 00:37:06,435 --> 00:37:07,910 890 00:37:07,910 --> 00:37:09,020 Encara on sóc apuntant. 891 00:37:09,020 --> 00:37:10,000 Així que és això. 892 00:37:10,000 --> 00:37:13,717 Així que en realitat una línia d'arranjaments de codi aquest tema en particular, el que sembla. 893 00:37:13,717 --> 00:37:14,800 Molt bé, així que això és bo. 894 00:37:14,800 --> 00:37:17,580 I algú pot ser un marcador de posició per al 5? 895 00:37:17,580 --> 00:37:18,080 Anem amunt. 896 00:37:18,080 --> 00:37:20,270 897 00:37:20,270 --> 00:37:21,320 Et portarem la propera vegada. 898 00:37:21,320 --> 00:37:24,280 >> Molt bé, així que ara-- i Com acotació al marge, els noms 899 00:37:24,280 --> 00:37:28,510 No faré esment explícit del dret Ara, pred punter, punter predecessor 900 00:37:28,510 --> 00:37:31,260 i nou punter, que és només els noms donat 901 00:37:31,260 --> 00:37:35,280 en el codi d'exemple als punters o les meves mans, que és una espècie de apuntant voltant. 902 00:37:35,280 --> 00:37:36,060 Quin és el teu nom? 903 00:37:36,060 --> 00:37:36,700 >> AUDIÈNCIA: Christine. 904 00:37:36,700 --> 00:37:37,100 >> DAVID J. Malan: Christine. 905 00:37:37,100 --> 00:37:38,090 Benvingut a bord. 906 00:37:38,090 --> 00:37:42,180 Molt bé, així que considerarem ara un escenari lleugerament més molest, 907 00:37:42,180 --> 00:37:46,350 pel qual vull inserir alguna cosa així com 26 en això. 908 00:37:46,350 --> 00:37:47,090 20? 909 00:37:47,090 --> 00:37:47,590 Què? 910 00:37:47,590 --> 00:37:50,510 Aquests són-- bona cosa que tenim aquesta ploma. 911 00:37:50,510 --> 00:37:51,955 Molt bé, 20. 912 00:37:51,955 --> 00:37:53,640 913 00:37:53,640 --> 00:37:57,570 Si algú pot aconseguir una altra peça de paper a punt, per si cas-- bé. 914 00:37:57,570 --> 00:37:58,370 Oh, interessant. 915 00:37:58,370 --> 00:37:59,760 916 00:37:59,760 --> 00:38:02,390 Bé, això és un exemple d'un error de conferències. 917 00:38:02,390 --> 00:38:03,894 Acceptar quin és el teu nom? 918 00:38:03,894 --> 00:38:04,560 AUDIÈNCIA: Julia. 919 00:38:04,560 --> 00:38:07,559 DAVID J. Malan: Júlia, pot esclatar i pretendre que mai van estar aquí? 920 00:38:07,559 --> 00:38:09,040 OK, això mai va succeir. 921 00:38:09,040 --> 00:38:09,680 Gràcies. 922 00:38:09,680 --> 00:38:12,180 Així que suposem que volem inserir Julia a aquesta llista enllaçada. 923 00:38:12,180 --> 00:38:13,780 Ella és la número 20. 924 00:38:13,780 --> 00:38:15,530 I, per descomptat, ella és va a pertànyer al 925 00:38:15,530 --> 00:38:17,521 begin-- no connecti amb res encara. 926 00:38:17,521 --> 00:38:20,020 Així que la teva mà pot ser tipus de baix nul o algun valor escombraries. 927 00:38:20,020 --> 00:38:21,210 Diguem la història ràpida. 928 00:38:21,210 --> 00:38:22,980 Estic assenyalant en el número 5 d'aquest temps. 929 00:38:22,980 --> 00:38:23,880 Llavors comprovo setembre. 930 00:38:23,880 --> 00:38:25,130 Després reviso 17. 931 00:38:25,130 --> 00:38:26,247 Després reviso 22. 932 00:38:26,247 --> 00:38:27,650 933 00:38:27,650 --> 00:38:32,485 I m'adono, ooh, Julia ha d'anar abans dels 22. 934 00:38:32,485 --> 00:38:33,580 935 00:38:33,580 --> 00:38:34,660 Llavors, què ha de succeir? 936 00:38:34,660 --> 00:38:35,786 937 00:38:35,786 --> 00:38:36,910 ¿Quines mans han de canviar? 938 00:38:36,910 --> 00:38:38,360 Júlia, la meva, o-- Quin és el teu nom? 939 00:38:38,360 --> 00:38:39,230 >> AUDIÈNCIA: Cristià. 940 00:38:39,230 --> 00:38:40,060 >> DAVID J. Malan: Cristiano o? 941 00:38:40,060 --> 00:38:40,560 >> AUDIÈNCIA: Andy. 942 00:38:40,560 --> 00:38:40,905 >> DAVID J. Malan: Andy. 943 00:38:40,905 --> 00:38:41,654 Cristià o Andy? 944 00:38:41,654 --> 00:38:44,280 945 00:38:44,280 --> 00:38:45,690 Andy ha d'apuntar a? 946 00:38:45,690 --> 00:38:46,780 947 00:38:46,780 --> 00:38:47,341 Júlia. 948 00:38:47,341 --> 00:38:47,840 Bé. 949 00:38:47,840 --> 00:38:48,960 Així que Andy, què vols apuntar a Júlia? 950 00:38:48,960 --> 00:38:50,120 Però esperi un minut. 951 00:38:50,120 --> 00:38:53,260 En la història fins al moment, Jo sóc el tipus d'un 952 00:38:53,260 --> 00:38:56,800 a càrrec, en el sentit que punter és la cosa que és 953 00:38:56,800 --> 00:38:57,850 movent-se a través de la llista. 954 00:38:57,850 --> 00:39:00,800 Pot ser que tinguem un nom per Andy, però no hi ha variable anomenada Andy. 955 00:39:00,800 --> 00:39:04,320 L'única altra variable que tenim és en primer lloc, que està representat per Gabe. 956 00:39:04,320 --> 00:39:07,690 >> Així que això és en realitat la raó per tant Fins aquí no hem necessitat això. 957 00:39:07,690 --> 00:39:10,846 Però ara a la pantalla no és esmentar de nou de punter pred. 958 00:39:10,846 --> 00:39:11,970 Així que permetin-me ser més explícit. 959 00:39:11,970 --> 00:39:14,820 Si aquesta és punter, vaig tenir una millor ser una mica més intel · ligent 960 00:39:14,820 --> 00:39:15,950 sobre la meva iteració. 961 00:39:15,950 --> 00:39:19,580 Si no us importa la meva passar per aquí de nou, assenyalant aquí, assenyalant aquí. 962 00:39:19,580 --> 00:39:22,500 Però m'ho dius a mi tenir un punter pred, punter predecessor, que és 963 00:39:22,500 --> 00:39:24,740 espècie que apunta a la element que estava just a. 964 00:39:24,740 --> 00:39:27,330 Així que quan vaig aquí, ara les actualitzacions mà esquerra. 965 00:39:27,330 --> 00:39:29,370 Quan vaig allà a les actualitzacions de la mà esquerra. 966 00:39:29,370 --> 00:39:33,090 I ara tinc no només un punter a l'element que va darrere de Julia, 967 00:39:33,090 --> 00:39:36,300 Encara tinc un punter a Andy, l'element abans. 968 00:39:36,300 --> 00:39:39,430 Així que vostè té accés, en essència, pa ratllat, si es vol, 969 00:39:39,430 --> 00:39:41,500 a tots els punters necessaris. 970 00:39:41,500 --> 00:39:43,710 >> Així que si jo estic apuntant a Andy i jo també estic apuntant 971 00:39:43,710 --> 00:39:47,105 en cristià, les mans ara ha de ser assenyalat en un altre lloc? 972 00:39:47,105 --> 00:39:48,770 973 00:39:48,770 --> 00:39:51,960 Així que Andy ara pot apuntar a Julia. 974 00:39:51,960 --> 00:39:54,460 Julia ara pot apuntar Cristiano. 975 00:39:54,460 --> 00:39:56,950 Perquè ella pot copiar el meu punter de la mà dreta. 976 00:39:56,950 --> 00:40:00,044 I això et posa amb eficàcia de nou en aquest lloc aquí. 977 00:40:00,044 --> 00:40:02,460 Així que en resum, tot i que aquesta ens està prenent classe de sempre 978 00:40:02,460 --> 00:40:04,510 per actualitzar en realitat un llista enllaçada, s'adonen 979 00:40:04,510 --> 00:40:06,580 que les operacions són relativament simples. 980 00:40:06,580 --> 00:40:10,030 És d'un, dos, tres línies de codi en última instància. 981 00:40:10,030 --> 00:40:12,780 Però embolicat al voltant dels línies de codi, presumiblement, 982 00:40:12,780 --> 00:40:16,350 és que efectivament una mica de lògica fa la pregunta, ¿on som? 983 00:40:16,350 --> 00:40:18,970 Estem en el començament, el mitjà, o al final? 984 00:40:18,970 --> 00:40:21,890 >> Ara, sens dubte hi ha alguna altra operacions que podríem posar en pràctica. 985 00:40:21,890 --> 00:40:24,880 I aquestes fotos aquí només representen el que acabem de fer amb els éssers humans. 986 00:40:24,880 --> 00:40:26,080 Què passa amb l'eliminació? 987 00:40:26,080 --> 00:40:30,650 Si vull, per exemple, treure el número 34 o 55, 988 00:40:30,650 --> 00:40:34,680 Podria ser el mateix tipus de codi, però necessitaré un o dos passos. 989 00:40:34,680 --> 00:40:36,110 Perquè el que hi ha de nou? 990 00:40:36,110 --> 00:40:40,460 Si elimino algú al final, com el nombre 55 i després 34, 991 00:40:40,460 --> 00:40:42,995 el que també ha de canviar com jo que? 992 00:40:42,995 --> 00:40:44,870 He de no evict-- Quin és el teu nom? 993 00:40:44,870 --> 00:40:45,380 >> AUDIÈNCIA: Jack. 994 00:40:45,380 --> 00:40:46,255 >> DAVID J. Malan: Jack. 995 00:40:46,255 --> 00:40:49,770 He de no només evict-- lliure Jack, tan literalment trucar gratis Jack, o almenys 996 00:40:49,770 --> 00:40:53,530 el punter allà també, però ara el que cal canviar amb Peter? 997 00:40:53,530 --> 00:40:55,510 La seva mà millor començament que apunta cap avall. 998 00:40:55,510 --> 00:40:59,300 Perquè tan aviat com jo en dic gratuït Jack, si segueix apuntant de Pere en Jack 999 00:40:59,300 --> 00:41:02,530 i per tant segueixo recorrent la llista i l'accés aquest punter, 1000 00:41:02,530 --> 00:41:05,650 que és quan el nostre amic segmentació d'edat criticar realitat podria posar en. 1001 00:41:05,650 --> 00:41:07,860 Perquè ens hem donat la tornar la memòria a Jack. 1002 00:41:07,860 --> 00:41:10,760 >> Pot quedar-s'hi maldestrament per un moment. 1003 00:41:10,760 --> 00:41:13,410 Perquè tenim només un parell operacions finals a tenir en compte. 1004 00:41:13,410 --> 00:41:15,600 Extracció del cap de la llista, o la principi-- i aquest de 1005 00:41:15,600 --> 00:41:16,349 una mica molest. 1006 00:41:16,349 --> 00:41:19,640 Perquè hem de saber que Gabe és una espècie d'especial en aquest programa. 1007 00:41:19,640 --> 00:41:21,440 Perquè de fet, ell té el seu propi punter. 1008 00:41:21,440 --> 00:41:24,860 Ell simplement no està sent assenyalat, com gairebé tots els altres aquí. 1009 00:41:24,860 --> 00:41:28,112 >> Així que quan el cap de la llista és eliminat, les mans que hagi de canviar ara? 1010 00:41:28,112 --> 00:41:29,070 Quin és el teu nom? 1011 00:41:29,070 --> 00:41:29,450 >> AUDIÈNCIA: Christine. 1012 00:41:29,450 --> 00:41:31,408 >> DAVID J. Malan: Sóc horrible en noms, pel que sembla. 1013 00:41:31,408 --> 00:41:34,011 Així Christine i Gabe, les mans necessiti canviar 1014 00:41:34,011 --> 00:41:36,510 quan tractem d'eliminar Christine, número 5, de la foto? 1015 00:41:36,510 --> 00:41:37,550 1016 00:41:37,550 --> 00:41:38,820 OK, així que anem a fer-ho Gabe. 1017 00:41:38,820 --> 00:41:40,950 Gabe va a apuntar, presumiblement, al número 9. 1018 00:41:40,950 --> 00:41:42,230 1019 00:41:42,230 --> 00:41:44,642 Però el següent que hauria de passar? 1020 00:41:44,642 --> 00:41:46,600 AUDIÈNCIA: Christine ha ser nul [inaudible]. 1021 00:41:46,600 --> 00:41:50,244 DAVID J. Malan: OK, probablement hauríem make-- vaig sentir "nul" en algun lloc. 1022 00:41:50,244 --> 00:41:51,410 AUDIÈNCIA: Null i alliberar-la. 1023 00:41:51,410 --> 00:41:51,855 DAVID J. Malan: null què? 1024 00:41:51,855 --> 00:41:53,074 AUDIÈNCIA: Null i alliberar-la. 1025 00:41:53,074 --> 00:41:54,490 DAVID J. Malan: Null i alliberar-la. 1026 00:41:54,490 --> 00:41:55,422 Així que això és molt fàcil. 1027 00:41:55,422 --> 00:41:58,380 I és perfecte que ara ets una espècie de peu allà, que no pertany. 1028 00:41:58,380 --> 00:42:00,430 Perquè has estat desacoblat de la llista. 1029 00:42:00,430 --> 00:42:02,820 Has estat efectivament orfes de la llista. 1030 00:42:02,820 --> 00:42:07,770 I així ens havíem millor trucar gratis ara Christine de donar aquest memòria. 1031 00:42:07,770 --> 00:42:10,240 En cas contrari, cada vegada que eliminar un node de la llista 1032 00:42:10,240 --> 00:42:14,230 que podríem estar fent la llista més curt, però en realitat no disminuint 1033 00:42:14,230 --> 00:42:15,096 la mida en memòria. 1034 00:42:15,096 --> 00:42:17,720 I pel que si estem afegint i afegint, afegint coses a la llista, 1035 00:42:17,720 --> 00:42:19,280 el meu equip podria aconseguir més lent i més i més lent, 1036 00:42:19,280 --> 00:42:21,740 perquè m'estic quedant sense memòria, encara que no estic realment 1037 00:42:21,740 --> 00:42:25,580 usant bytes de Christine de la memòria més. 1038 00:42:25,580 --> 00:42:28,500 >> Així que al final hi ha una altra escenaris, de l'eliminació descomptat-- 1039 00:42:28,500 --> 00:42:30,640 en el medi, l'eliminació al final, com hem vist. 1040 00:42:30,640 --> 00:42:32,348 Però el més interessant repte ara és 1041 00:42:32,348 --> 00:42:34,770 serà considerar exactament el que el temps d'execució és. 1042 00:42:34,770 --> 00:42:36,640 Així que no només es pot mantenir un trossos de paper, si, Gabe, 1043 00:42:36,640 --> 00:42:38,640 que no li importaria donar tots una bola de la tensió. 1044 00:42:38,640 --> 00:42:42,100 Moltes gràcies a la nostra llista enllaçada de voluntaris aquí, si pogués. 1045 00:42:42,100 --> 00:42:45,320 >> [Aplaudiments] 1046 00:42:45,320 --> 00:42:46,700 >> DAVID J. Malan: Molt bé. 1047 00:42:46,700 --> 00:42:51,110 Així que un parell d'analítica preguntes després, si pogués. 1048 00:42:51,110 --> 00:42:59,670 Hem vist aquesta notació abans, gran O i omega, límits superiors 1049 00:42:59,670 --> 00:43:02,520 i cotes inferiors de la temps d'algun algorisme s'executa. 1050 00:43:02,520 --> 00:43:04,950 Així que anem a considerar només un parell de preguntes. 1051 00:43:04,950 --> 00:43:07,090 >> Un, i ho vam dir abans, el que és la gestió 1052 00:43:07,090 --> 00:43:10,647 temps de cerca d'un llista en termes de gran O? 1053 00:43:10,647 --> 00:43:13,480 Què és un límit superior en el funcionament temps de recerca una llista enllaçada 1054 00:43:13,480 --> 00:43:16,340 tal com s'aplica pels nostres voluntaris aquí? 1055 00:43:16,340 --> 00:43:17,820 És gran O de n, lineal. 1056 00:43:17,820 --> 00:43:20,630 Com que en el pitjor dels casos, l'element, com 55, 1057 00:43:20,630 --> 00:43:23,830 podríem estar buscant podríem estar on Jack era, tot el camí al final. 1058 00:43:23,830 --> 00:43:28,250 I, per desgràcia, a diferència d'una matriu no podem aconseguir la suposició aquest moment. 1059 00:43:28,250 --> 00:43:31,820 Malgrat tots els nostres éssers humans eren ordenats d'elements petits, 5, 1060 00:43:31,820 --> 00:43:35,900 tot el camí fins l'element més gran, 55, que sol ser una bona cosa. 1061 00:43:35,900 --> 00:43:38,815 Però què té aquesta suposició ja no ens permet fer? 1062 00:43:38,815 --> 00:43:39,775 1063 00:43:39,775 --> 00:43:40,650 AUDIÈNCIA: [inaudible] 1064 00:43:40,650 --> 00:43:40,920 DAVID J. Malan: Digui una altra vegada? 1065 00:43:40,920 --> 00:43:41,800 AUDIÈNCIA: Accés aleatori. 1066 00:43:41,800 --> 00:43:43,049 DAVID J. Malan: Accés aleatori. 1067 00:43:43,049 --> 00:43:46,330 I al seu torn, això significa que pot no ia utilitzar zeros feble, la intuïció, 1068 00:43:46,330 --> 00:43:49,365 i l'evidència de la utilització de binari buscar i dividir i conquerir. 1069 00:43:49,365 --> 00:43:51,240 Perquè tot i que els éssers humans podien òbviament 1070 00:43:51,240 --> 00:43:54,610 veure que Andy o cristià van ser més o menys en el medi de la llista, 1071 00:43:54,610 --> 00:43:57,670 només sabem que com ordinador amb una lectura ràpida de la llista 1072 00:43:57,670 --> 00:43:59,029 des del principi. 1073 00:43:59,029 --> 00:44:00,570 Així que ens hem donat fins que l'accés aleatori. 1074 00:44:00,570 --> 00:44:04,380 >> Així que gran O de n ara és el superior amb destinació en el nostre temps de recerca. 1075 00:44:04,380 --> 00:44:07,920 Què passa amb l'omega de la nostra recerca? 1076 00:44:07,920 --> 00:44:11,535 Quin és el límit inferior en la recerca per a algun nombre en aquesta llista? 1077 00:44:11,535 --> 00:44:12,410 AUDIÈNCIA: [inaudible] 1078 00:44:12,410 --> 00:44:13,040 DAVID J. Malan: Digui una altra vegada? 1079 00:44:13,040 --> 00:44:13,420 AUDIÈNCIA: Una. 1080 00:44:13,420 --> 00:44:13,800 DAVID J. Malan: Una. 1081 00:44:13,800 --> 00:44:14,760 Així que el temps constant. 1082 00:44:14,760 --> 00:44:17,020 En el millor dels casos, Christine és de fet, al principi de la llista. 1083 00:44:17,020 --> 00:44:19,020 I estem buscant número 5, de manera que la va trobar. 1084 00:44:19,020 --> 00:44:19,787 Així que no és gran cosa. 1085 00:44:19,787 --> 00:44:22,370 Però ella ha d'estar al a partir de la llista en aquest cas. 1086 00:44:22,370 --> 00:44:23,745 Què tal alguna cosa com ¿Eliminar? 1087 00:44:23,745 --> 00:44:24,717 1088 00:44:24,717 --> 00:44:26,300 Què passa si vostè vol suprimir un element? 1089 00:44:26,300 --> 00:44:29,200 Quin és el límit superior i el límit inferior sobre l'eliminació d'alguna cosa d'un vinculat 1090 00:44:29,200 --> 00:44:29,699 enumerar? 1091 00:44:29,699 --> 00:44:35,195 1092 00:44:35,195 --> 00:44:36,070 AUDIÈNCIA: [inaudible] 1093 00:44:36,070 --> 00:44:36,420 DAVID J. Malan: Digui una altra vegada? 1094 00:44:36,420 --> 00:44:37,067 AUDIÈNCIA: n. 1095 00:44:37,067 --> 00:44:38,900 DAVID J. Malan: n és de fet, el límit superior. 1096 00:44:38,900 --> 00:44:41,700 Com que en el pitjor dels casos que tractem eliminar Jack, com nosaltres ho vam fer. 1097 00:44:41,700 --> 00:44:43,050 Ell és tot el camí al final. 1098 00:44:43,050 --> 00:44:45,419 Ens porta per sempre, o n passos per trobar-lo. 1099 00:44:45,419 --> 00:44:46,460 Així que això és un límit superior. 1100 00:44:46,460 --> 00:44:47,430 Això és lineal, segur. 1101 00:44:47,430 --> 00:44:50,970 I el temps el millor dels casos en execució, o els límits inferiors en el millor dels casos 1102 00:44:50,970 --> 00:44:51,975 seria constant de temps. 1103 00:44:51,975 --> 00:44:54,600 Perquè potser tractem d'eliminar Christine, i acabem de tenir sort 1104 00:44:54,600 --> 00:44:55,558 ella està en el començament. 1105 00:44:55,558 --> 00:44:56,350 Espera un minut. 1106 00:44:56,350 --> 00:44:59,370 Gabe també era al principi, i també vam haver de actualitzar Gabe. 1107 00:44:59,370 --> 00:45:01,150 Així que no era només un pas. 1108 00:45:01,150 --> 00:45:04,210 Pel que és de fet constant temps, en el millor dels casos, 1109 00:45:04,210 --> 00:45:06,345 per eliminar l'element més petit? 1110 00:45:06,345 --> 00:45:07,360 1111 00:45:07,360 --> 00:45:10,960 És, tot i que podria ser dues, 3, o fins i tot 100 línies de codi, 1112 00:45:10,960 --> 00:45:14,000 si és el mateix nombre de línies, no en un bucle, 1113 00:45:14,000 --> 00:45:16,577 i independent de la mida de la llista, és clar. 1114 00:45:16,577 --> 00:45:18,660 Eliminar l'element a el principi de la llista, 1115 00:45:18,660 --> 00:45:21,940 fins i tot si hem de fer front a Gabe, encara estem a temps constant. 1116 00:45:21,940 --> 00:45:24,220 >> Així que això sembla una enorme pas enrere. 1117 00:45:24,220 --> 00:45:27,000 I el que una pèrdua de temps si, en la primera setmana i la setmana 1118 00:45:27,000 --> 00:45:30,250 zero no només vam tenir codi pseudocodi però el codi real 1119 00:45:30,250 --> 00:45:35,780 per posar en pràctica una cosa que és registre base de n, o ingressi, més aviat, de n, base 2, 1120 00:45:35,780 --> 00:45:37,150 quant al seu temps d'execució. 1121 00:45:37,150 --> 00:45:40,710 Així que per què diables hauria que vulgueu començar usant alguna cosa com una llista enllaçada? 1122 00:45:40,710 --> 00:45:41,517 Sí. 1123 00:45:41,517 --> 00:45:44,022 >> AUDIÈNCIA: Així que vostè pot afegir elements a la matriu. 1124 00:45:44,022 --> 00:45:46,230 DAVID J. Malan: Així que vostè pot afegir elements a la matriu. 1125 00:45:46,230 --> 00:45:47,550 I això també és temàtic. 1126 00:45:47,550 --> 00:45:49,740 I seguirem per veure això, aquesta compensació, molt 1127 00:45:49,740 --> 00:45:51,573 com hem vist un trade-off amb merge sort. 1128 00:45:51,573 --> 00:45:54,606 Realment podríem accelerar buscar o ordenar, més aviat, 1129 00:45:54,606 --> 00:45:57,480 si ens passem una mica més d'espai i tenir un tros addicional d'una memòria 1130 00:45:57,480 --> 00:45:58,760 o una matriu de tipus de combinació. 1131 00:45:58,760 --> 00:46:01,270 Però gastem més espai, però ens estalviem temps. 1132 00:46:01,270 --> 00:46:04,820 En aquest cas, estem renunciar a temps, però estem 1133 00:46:04,820 --> 00:46:08,170 guanyar flexibilitat, dinamisme si es vol, 1134 00:46:08,170 --> 00:46:10,280 que és sens dubte una característica positiva. 1135 00:46:10,280 --> 00:46:11,520 >> També ens estem gastant l'espai. 1136 00:46:11,520 --> 00:46:13,710 En quin sentit és un lligat enumerar més car 1137 00:46:13,710 --> 00:46:15,700 en termes d'espai d'una matriu? 1138 00:46:15,700 --> 00:46:18,379 1139 00:46:18,379 --> 00:46:19,920 On és l'espai extra ve? 1140 00:46:19,920 --> 00:46:20,460 Sí? 1141 00:46:20,460 --> 00:46:21,800 >> AUDIÈNCIA: [inaudible] punter. 1142 00:46:21,800 --> 00:46:23,310 >> DAVID J. Malan: Sí, també tenen el punter. 1143 00:46:23,310 --> 00:46:25,560 Així que això és molest minorly en què ja no sóc 1144 00:46:25,560 --> 00:46:27,780 Jo emmagatzemar només un int per representar un int. 1145 00:46:27,780 --> 00:46:30,990 Estic emmagatzemant 1 int i un punter, que també és de 32 bits. 1146 00:46:30,990 --> 00:46:33,470 Així que estic literalment duplicar la quantitat d'espai involucrat. 1147 00:46:33,470 --> 00:46:36,040 Així que això és un trade-off, però això és en el cas d'int. 1148 00:46:36,040 --> 00:46:39,580 Suposem que vostè no està emmagatzemant int, però suposem que cada un d'aquests rectangles 1149 00:46:39,580 --> 00:46:43,290 o cada un d'aquests éssers humans representava una paraula, una paraula en anglès que 1150 00:46:43,290 --> 00:46:46,430 podria ser 5 caràcters, 10 personatges, potser fins i tot més. 1151 00:46:46,430 --> 00:46:49,940 Després d'afegir només 32 més bits podria ser menys de gran cosa. 1152 00:46:49,940 --> 00:46:52,160 >> Què passaria si cada un dels estudiants a la manifestació 1153 00:46:52,160 --> 00:46:55,107 Estàvem literalment estructures estudiantils que tenen noms i cases i potser 1154 00:46:55,107 --> 00:46:57,065 números de telèfon i Twitter mànecs i similars. 1155 00:46:57,065 --> 00:46:59,564 Així que tots els camps que vam començar parlant l'altre dia, 1156 00:46:59,564 --> 00:47:02,410 molt menys d'un gran problema ja nostres nodes es posen més interessants 1157 00:47:02,410 --> 00:47:05,972 i gran per gastar, eh, un addicional indicador acaba de vincular entre si. 1158 00:47:05,972 --> 00:47:07,180 Però de fet, és un trade-off. 1159 00:47:07,180 --> 00:47:09,560 I, en efecte, el codi és més complex, ja que tindràs 1160 00:47:09,560 --> 00:47:11,770 veure amb una lectura ràpida a través aquest exemple particular. 1161 00:47:11,770 --> 00:47:14,302 Però i si hagués algun sant grial aquí. 1162 00:47:14,302 --> 00:47:17,010 Què passa si no prenem un pas cap enrere, però un gran pas cap endavant 1163 00:47:17,010 --> 00:47:19,180 i implementar una dada estructura a través de la qual 1164 00:47:19,180 --> 00:47:22,870 pot trobar elements com Jack o Christine o qualssevol altres elements 1165 00:47:22,870 --> 00:47:25,870 en aquesta matriu en la veritable constant de temps? 1166 00:47:25,870 --> 00:47:26,920 Hi és constant. 1167 00:47:26,920 --> 00:47:28,320 Eliminar constant. 1168 00:47:28,320 --> 00:47:29,570 Inseriu és constant. 1169 00:47:29,570 --> 00:47:32,260 Totes aquestes operacions són constants. 1170 00:47:32,260 --> 00:47:33,750 Aquest seria el nostre sant grial. 1171 00:47:33,750 --> 00:47:36,690 I aquí és on estem recollirà la propera vegada. 1172 00:47:36,690 --> 00:47:38,600 Ens veiem llavors. 1173 00:47:38,600 --> 00:47:39,371