[Powered by Google Translate] [Setmana 6, continuació]
[David J. Malan] [Harvard University]
[Aquesta és CS50.] [CS50.TV]
Això és CS50 i aquest és el cap de setmana 6.
Així CS50x, un dels primers cursos de Harvard que participen en la iniciativa EDX
de fet va debutar aquest passat dilluns.
Si a vostè li agradaria fer una ullada al que altres en Internet
estan seguint juntament amb, vostè pot dirigir-se a x.cs50.net.
Això li redirigirà al lloc apropiat en edx.org,
que era on aquest i altres cursos del MIT i Berkeley ara vivim.
Vostè haurà de registrar-se per obtenir un compte, trobareu que el material és en gran part el mateix
com vostè ha tingut aquest semestre, encara que un parell de setmanes amb retard, ja que tenir tot llest.
Però el que els estudiants en CS50x ara es veu és una interfície bastant com aquest.
Això, per exemple, és Zamyla liderant el conjunt de problemes pas a pas per 0.
En iniciar la sessió en edx.org, un estudiant CS50x veu el tipus de coses
vostè esperaria veure en un curs: la conferència per al dilluns,
conferència per al dimecres, diversos curtmetratges, els butlletins de problemes, els tutorials, arxius PDF.
A més, com vostè veu aquí, les traduccions automàtiques
de les transcripcions anglès al xinès, japonès, espanyol, italià,
i un munt d'altres llengües que sens dubte serà imperfecta
tal com les desplegar mitjançant programació amb una cosa que es diu una API,
o interfície de programació d'aplicacions, des de Google
que ens permet convertir Anglès a altres idiomes.
Però gràcies al meravellós esperit d'alguns voluntaris més de cent,
persones a l'atzar a Internet que han ofert amablement a participar
en aquest projecte, que poc a poc va a millorar la qualitat de les traduccions
fent que els humans corregir els errors que els nostres equips han fet.
>> Així que resulta que hi havia uns quants estudiants més aparèixer dilluns del que inicialment s'esperava.
De fet, ara CS50x té 100.000 persones al llarg dels següents a casa.
Llavors s'adona que tots som part d'aquesta classe inaugural de fer aquest curs en ciències de la computació
educació en general, de manera més àmplia i accessible.
I la realitat és ara, amb alguns d'aquests cursos en línia massius,
tots ells comencen amb aquests nombres molt alts, com sembla que hem fet aquí.
Però l'objectiu, en última instància, per CS50x és realment fer que la gent com molts fins a la meta com sigui possible.
Pel seu disseny, CS50x serà ofert des de dilluns passat
fins el 15 d'abril de 2013, per la qual cosa les persones que tenen compromisos escolars en altres parts,
treball, família, altres conflictes i similars, tenen una mica més de flexibilitat
amb la qual submergir-se en aquest curs, que, n'hi ha prou amb dir,
és bastant ambiciosa fet si només en el transcurs de només tres mesos durant un semestre normal.
No obstant això, aquests estudiants seran fer front als butlletins de problemes mateixos, veient el mateix contingut,
tenir accés als mateixos pantalons curts i similars.
Així que adonar-se que tots som veritablement junts en això.
I un dels objectius finals de CS50x no és només per a la gent com molts
a la línia de meta i donar-los aquest nou coneixement de la informàtica
i la programació, sinó també per fer que aquesta experiència compartida.
Una de les característiques definitòries de 50 al campus, així ho esperem,
ha estat aquest tipus d'experiència comú, per bé o per mal, de vegades,
però tenint aquestes persones es tornin cap a l'esquerra i cap a la dreta,
i hores d'oficina i el hackathon i la fira.
És una mica més difícil que fer-ho en persona amb amics en línia,
però CS50x conclourà a l'abril amb la primera CS50 Expo,
que serà una adaptació en línia de la nostra idea de la fira
on aquests milers d'estudiants de tot seran convidats a presentar un 1 - a 2 minuts de vídeo,
ja sigui un screencast del seu projecte final o vídeo d'ells agitant hola
i parlant del seu projecte i li donem,
igual que els seus predecessors han fet aquí al campus de la fira,
de manera que per al final del semestre, s'espera tenir una exposició mundial
dels projectes dels estudiants CS50x 'finals, molt semblant a la que li espera aquest mes de desembre al campus.
Així que més que en els pròxims mesos.
>> Amb 100.000 estudiants, però, ve la necessitat d'un CAS mica més.
Tenint en compte que vostès estan obrint el camí aquí i prenent CS50
diverses setmanes abans del llançament d'aquest material a la gent en EDX,
adonem que li encantaria participar ja que molts dels nostres estudiants com sigui possible en aquesta iniciativa,
tant durant el semestre d'hivern, així com aquesta i la propera primavera.
Així que si vol participar en CS50x,
particularment en unir-se a CS50x tractar, la versió de EDX CS50 Discussió,
que molts de vostès s'han estat utilitzant al campus, al tauler d'anuncis en línia,
si us plau cap a aquesta URL, sabrem qui ets,
perquè ens encantaria construir un equip d'estudiants i professors i el personal per igual
al campus que estan simplement jugant bé i ajudant.
I quan veuen a una qüestió que és familiar per a ells,
que escolti un estudiant informar algun error en algun lloc allà fora en algun país a Internet,
i que sona una campana, ja que també tenia aquest mateix nombre
si d-hall fa algun temps, és d'esperar llavors vostè pot ficar la seva cullera i compartir la seva pròpia experiència.
Així que si us plau participar si li agradaria.
>> Cursos de ciències de la computació a la Universitat de Harvard té una mica d'una tradició,
CS50 entre ells, de tenir una mica de roba, una mica de roba, que es pot portar amb orgull
al final del semestre, dient molt orgullós d'haver acabat CS50
i va prendre CS50 i similars, i sempre intentem involucrar els estudiants
en aquest procés tant com sigui possible, mitjançant el qual convidem,
en aquesta època del semestre, els estudiants a presentar els seus dissenys
l'ús de Photoshop, o qualsevol eina de selecció que voleu utilitzar
si ets un dissenyador, a presentar els seus dissenys per a samarretes i dessuadores
i para-sols i mocadors per a gossos petits que ara tenim i similars.
I tot és llavors - els guanyadors de cada any després es va exhibir
a la pàgina web de l'assignatura en store.cs50.net.
Tot el que es ven a un cost allà, però el lloc web només en si funciona
i permet a les persones triar els colors i dissenys que els agraden.
Així que vaig pensar que acabàvem de compartir alguns dels dissenys de l'any passat
que eren al lloc web, a més d'aquest d'aquí, que és una tradició anual.
"Cada dia estic Seg Faultn" va ser una de les presentacions de l'any passat,
que encara es troba allà per antics alumnes.
Hem tingut aquest ", CS50, Established 1989".
Un dels nostres Bowdens, Rob, era molt popular l'any passat.
"Equip de Bowden" va néixer, aquest disseny va ser presentat, entre els més venuts.
Igual que aquest d'aquí. Molta gent tenia "febre Bowden", d'acord amb els registres de vendes.
Donar-se compte del que ara podria ser el disseny d'aquí, a Internet.
Més detalls sobre aquest problema al següent estableix per venir.
>> Una de les eines més: vostè ha tingut alguna exposició i espero que ara
una mica d'experiència pràctica amb GDB,
que és, per descomptat, un depurador i permet manipular
seu programa a un nivell bastant baix, fent que tipus de coses?
Què GDB permeten fer?
Sí? Dóna'm alguna cosa. [Resposta Estudiantil, inintel · ligible]
Bé. Entre en la funció, de manera que no només cal escriure run
i tenen el cop programa a través del seu totalitat, la impressió de les coses a la sortida estàndard.
Més aviat, vostè pot caminar a través de línia per línia, ja sigui escrivint proper
a anar línia per línia a línia o pas a submergir-se en una funció, típicament un que vostè va escriure.
Què més fa el BGF li permeten fer? Sí? [Resposta Estudiantil, inintel · ligible]
Imprimir variables. Així que si vostè vol fer una mica d'introspecció dins del seu programa de
sense haver de recórrer a escriure sentències printf per tot el lloc,
vostè pot imprimir una variable o mostrar una variable.
Què més es pot fer amb un depurador GDB com?
[Resposta Estudiantil, inintel · ligible]
Exactament. Pot establir punts d'interrupció, es pot dir que l'execució descans
en la funció principal o la funció foo.
Es pot dir que l'execució de descans a la línia 123.
I els punts d'interrupció són una tècnica molt poderosa
perquè si vostè té una idea general d'on és el seu problema
probablement és, vostè no ha de perdre temps passant a través de la totalitat del programa.
Vostè pot essencialment saltar allà i comenci a escriure -
pas a pas a través d'ell amb el pas o el següent o similar.
Però el problema amb alguna cosa com GDB és que t'ajuda, els recursos humans,
trobar els seus problemes i trobar els seus errors.
No necessàriament trobar tant per tu.
>> Així es va introduir el style50 altre dia, que és una eina de línia de comandes curt
que tracta de estilitzar el seu codi una mica més net que tu, l'ésser humà, podria haver fet.
Però això, també, és en realitat una cosa estètica.
Però resulta que hi ha aquesta altra eina anomenada Valgrind que és una mica més arcà d'usar.
La seva sortida és atroçment críptic a primera vista.
Però és meravellosament útil, sobretot ara que estem en la part del terme
on vas a començar a utilitzar malloc i l'assignació de memòria dinàmica.
Les coses poden anar molt, molt malament ràpidament.
Perquè si vostè s'oblida d'alliberar la seva memòria, o deixa de fer referència punter NULL,
o deixa de fer referència punter d'escombraries, el que sol ser el símptoma que els resultats?
Seg culpa. I s'obté l'arxiu base d'una certa quantitat de kilobytes o megabytes
que representa l'estat de la memòria del programa, quan es va estavellar,
però en última instància, el seu programa segons falles, falla de segmentació,
el que significa que alguna cosa dolenta ha passat gairebé sempre relacionats
a un error relacionat amb la memòria que vostè ha fet en algun lloc.
Així Valgrind ajuda a trobar coses com aquesta.
És una eina que s'executa, com GDB, després d'haver compilat el programa,
però en lloc d'executar el programa directament, es corre Valgrind
i es passa al seu programa, tal com ho fa amb GDB.
Ara, l'ús, per obtenir el millor tipus de sortida,
és una mica llarg, així que aquí dalt de la pantalla veuràs Valgrind-v.
"-V" gairebé universalment significa detallat quan vostè està utilitzant programes en un equip Linux.
Per tant, significa escopir més dades que vostè pot ser que per defecte.
"- Comprovar fugues = full." Això és només dir xec per totes les possibles pèrdues de memòria,
errors que vaig poder haver fet. Això, també, és un paradigma comú amb els programes de Linux.
En general, si vostè té un argument de línia d'ordres que és un "switch",
que se suposa que per canviar el comportament del programa, i és una sola lletra,
és-v, però si això canvia, només pel disseny del programador,
és una paraula completa o una sèrie de paraules, l'argument de línia d'ordres s'inicia amb -.
Aquests són només convencions humanes, però les veuràs cada vegada més.
I després, finalment, "a.out" és el nom arbitrari per al programa en aquest exemple en particular.
I aquí hi ha una sortida representativa.
>> Abans de veure el que això significa, deixa anar a un fragment de codi per aquí.
I m'ho dius a mi moure aquesta fora del camí, molt aviat,
i anem a fer una ullada a memory.c, que és aquest petit exemple aquí.
Així que en aquest programa, vull fer un zoom sobre les funcions i preguntes.
Tenim una funció principal que crida a una funció, f,
i llavors, què f procedir a fer, en anglès una mica tècnic?
Què fa f procedir a fer?
Què vaig a començar amb la línia 20, i la ubicació de l'estrella, no importa,
però només vaig a ser coherents amb l'última conferència.
Quina és la línia 20 és per a nosaltres? Al costat de mà esquerra. Anem a descompondre encara més.
Int * x: què fer?
Bé. Es declara un punter, i ara serem encara més tècnic.
Què vol dir, molt concretament, per declarar un punter? Algú més?
Sí? [Resposta Estudiantil, inintel · ligible] Massa lluny.
Així que vostè està llegint a la dreta del signe igual.
Anem a centrar-nos només en el costat esquerre, just a int * x.
Això significa "declarar" un punter, però ara anem a bussejar més profund a aquesta definició.
Què vol dir concretament, tècnicament significa? Sí?
[Resposta Estudiantil, inintel · ligible]
Bé. S'està preparant per guardar una direcció en la memòria.
Bé. I anem a prendre un pas més enllà, és declarar una variable, x, que és de 32 bits.
I jo sé que és de 32 bits perquè -?
No és perquè és un int, perquè és un punter en aquest cas.
La coincidència que és un i el mateix amb un int,
però el fet que no és l'estrella no vol dir que és un punter
i en l'aparell, com amb molts equips, però no tots, els punters són de 32 bits.
El maquinari més modern, com els últims Macs, els últims ordinadors, pot tenir punters de 64 bits,
però en l'aparell, aquestes coses són de 32 bits.
Així que anem a estandarditzar en això. Més concretament, la història va així:
Nosaltres "declarar" un punter, el que vol dir això?
Ens preparem per emmagatzemar una adreça de memòria.
Què significa això?
Creem una variable anomenada x que ocupa 32 bits
que aviat va a emmagatzemar la direcció d'un nombre enter.
I això és probablement tan precisos com puguem.
Està bé avançar a simplificar el món i dir declarar un punter anomenat x.
Declara un punter, però adonar i entendre el que realment està passant
fins i tot en tan sols aquests pocs caràcters.
>> Ara, aquest és gairebé una mica més fàcil, encara que és una expressió més llarga.
Llavors, què està fent això, això és ressaltada ara: "malloc (10 * sizeof (int));" Sí?
[Resposta Estudiantil, inintel · ligible]
Bé. I ho vaig a portar-hi. S'assigna una porció de memòria per a deu punts.
I ara anem a bussejar una mica més profund, és l'assignació d'una part de la memòria per a deu punts.
El que es malloc després tornar?
La direcció d'aquest bloc, o, més concretament, la direcció del primer byte d'aquest bloc.
Com llavors sóc el programador, per saber on és aquest tros de caps de memòria?
Jo sé que és contigua. Malloc, per definició, li donarà una part contigua de la memòria.
No hi ha espais en blanc. Vostè té accés a tots els bytes en aquest tros,
esquena amb esquena amb esquena, però com puc saber on és el final d'aquest tros de memòria és?
Quan s'utilitza malloc? [Resposta Estudiantil, inintel · ligible] Bé.
No ho saps. Vostè ha de recordar.
He de recordar que vaig fer servir el valor 10, i ni tan sols semblen haver fet això aquí.
No obstant això, la responsabilitat recau enterament sobre mi. Strlen, que ens hem tornat una mica dependents de les cadenes,
només funciona a causa d'aquesta convenció de tenir \ 0
o aquest caràcter especial nul, NUL, al final d'una cadena.
Això no es sosté per uns trossos arbitraris de la memòria.
Tot depèn de vostè. Així que la línia 20, a continuació, assigna un tros de memòria
que pot emmagatzemar deu números enters, i emmagatzema la direcció del primer byte
d'aquest bloc de memòria en la variable x es diu.
Ergo, que és un punter. Així que la línia 21, per desgràcia, va ser un error.
Però primer, què està fent? Està dient botiga al lloc 10, 0 indexat,
del bloc de memòria anomenat x el valor 0.
>> Així explica un parell de coses estan succeint.
Tot i que x és un punter, recuperarà un parell de setmanes
que encara es pot utilitzar la notació quadrada estil-matriu suport.
Perquè això és realment taquigrafia notació per l'aritmètica de punters més críptic de futur.
on anàvem a fer alguna cosa com això: neu la x, mogui més de 10 punts,
a continuació, anar-hi a qualsevol direcció s'emmagatzema en aquesta ubicació.
Però, francament, això no és més atroç de llegir i sentir-se còmode amb.
Així que el món sol utilitzar els claudàtors només perquè és molt més amigable per llegir.
Però això és el que realment està passant sota la campana;
x és una adreça no una matriu, per se.
Així que aquest és l'emmagatzematge de 0 a lloc 10 en x.
Per què és això dolent? Sí?
[Resposta Estudiantil, inintel · ligible] Exactament.
Només ens van assignar deu enters, però comptem des de 0 en programar en C,
pel que té accés a la 0 1 2 3 4 5 6 7 8 9, però no 10.
Així que, o el programa serà culpa seg o no ho és.
No obstant això, no se sap ben bé, el que és una mena de comportament no determinista.
Realment depèn de si tenim sort.
Si resulta que el sistema operatiu no li importa si utilitzo aquest byte extra,
tot i que no l'ha donat a mi, el meu programa no es pot bloquejar.
És cru, té fallades, però és possible que no vegi aquest símptoma,
o potser ho veig de tant en tant.
Però la realitat és que l'error és, de fet, existeix.
I és realment problemàtic si vostè ha escrit un programa que vols ser correcta,
que ha venut el programa que la gent està utilitzant que cada de tant en tant es bloqueja
perquè, és clar, això no és bo. De fet, si vostè té un telèfon Android o un iPhone
i descarregar aplicacions en aquests dies, si vostè ha tingut alguna vegada una aplicació per deixar de fumar just,
de sobte desapareix, que és gairebé sempre el resultat d'algun problema relacionat amb la memòria,
de manera que el programador pota i anul · la la referència d'un punter
que ell o ella no ha de tenir, i el resultat de iOS o Android és matar només el programa complet
en lloc dels comportaments de risc definits o algun tipus de compromís de seguretat.
>> Hi ha un error en aquest altre programa a part d'aquest.
Què més he cagat en aquest programa?
Jo no he practicat el que he predicat. Sí?
[Resposta Estudiantil, inintel · ligible] Bé.
No he alliberat la memòria. Així que la regla d'or ara
ha de ser en qualsevol moment de cridar malloc, de trucar lliure quan hagi acabat d'usar aquesta memòria.
Ara, quan anava jo a voler alliberar aquesta memòria?
Probablement, assumint aquesta primera línia era correcta, m'agradaria fer-ho aquí.
Perquè jo no podria, per exemple, ho fan aquí. Per què?
Just fora del seu abast. Així que, encara que estem parlant de punters,
aquesta és una setmana 2 o 3 qüestió, on x és només un abast dins de les claus on es va declarar.
Així que definitivament no es pot alliberar allà. La meva única oportunitat d'alliberar és més o menys després de la línia 21.
Aquest és un programa bastant senzill, era bastant fàcil una vegada que tipus de embolicar la seva ment
entorn al que el programa està fent, on són els errors eren.
I encara que no ho vaig veure al principi, esperem que sigui una mica obvi ara
que aquests errors són bastant fàcil de resoldre i fer fàcilment.
Però quan un programa té més de 12 línies de llarg, que és 50 línies, 100 línies de llarg,
caminant pel codi línia per línia, pensar-hi, lògicament,
És possible, però no gaire divertit de fer, constantment a la recerca d'errors,
i també és difícil de fer, i és per això que una eina com Valgrind existeix.
Deixin-me seguir endavant i fer això: m'ho dius a mi obrir la finestra de terminal,
I no tinc prou amb executar la memòria, perquè la memòria sembla estar bé.
Estic tenint sort. Que va a byte addicional al final de la matriu
no sembla ser massa problemàtic.
Però em deixa, però, fer una comprovació de validesa, la qual cosa significa per comprovar
si és o no és realment correcte.
>> Així que farem Valgrind-v - Fuga-check = complet,
i després el nom del programa en aquest cas és la memòria, no a.out.
Així que permetin-me anar endavant i fer-ho. Premeu Enter.
Estimat Déu. Aquesta és la seva sortida, i això és el que he fet referència abans.
Però, si aprens a llegir a través de tots els disbarats aquí,
la major part d'aquesta producció és només de diagnòstic que no és tan interessant.
El que l'ull realment vol estar buscant és qualsevol menció d'error o no vàlid.
Paraules que suggereixen problemes.
I, de fet, anem a veure el que va malament aquí baix.
Tinc un resum d'algun tipus, "en ús a la sortida:. 40 bytes en blocs de 1"
No estic realment segur del que un bloc és encara, però 40 bytes
en realitat se sent com si pogués esbrinar on que ve.
40 bytes. Per què són de 40 bytes en ús a la sortida?
I més concretament, si ens desplacem fins aquí,
Per què he perdut definitivament 40 bytes? Sí?
[Resposta Estudiantil, inintel · ligible] Perfect. Sí, exactament.
Hi havia deu números enters, i cada un d'ells és la mida de 4, o 32 bits,
així que he perdut 40 bytes precisament perquè, com vostè proposa, no he anomenat lliure.
Això és un error, i ara anem a mirar cap avall una mica més i veure al costat d'aquest,
"No vàlid escriure de mida 4". Ara, què és això?
Aquesta adreça s'expressa el que la notació de base, pel que sembla?
Això és hexadecimal, i cada vegada que veu un nombre que comença amb 0x,
significa hexadecimal, el que vam fer allà per, crec, conjunt de processadors 0 a la secció de preguntes,
que era només per fer un exercici d'escalfament, la conversió de decimal a hexadecimal a binari i així successivament.
Hexadecimal, només per convenció humana, generalment s'utilitza per representar els punters
o, més generalment, es dirigeix. És només una convenció,
perquè és una mica més fàcil de llegir, que és una mica més compacte que alguna cosa com decimal,
i binari és inútil per a la majoria dels éssers humans per al seu ús.
I ara què vol dir això? Bé, sembla que hi ha una escriptura no vàlid
de mida 4 en la línia 21 de memory.c.
Així que anem a tornar a la línia 21, i de fet, és que d'escriptura no vàlid.
Així Valgrind no se celebrarà del tot la meva mà i em digui el que la solució és,
però es detecta que estic fent una escriptura vàlida.
Estic tocant 4 bytes que no ha de ser, i pel que sembla això és perquè,
com vostè ha assenyalat, estic fent [10] en lloc de [9] màximament
o [0] o alguna cosa intermedi.
Amb Valgrind, es donen compte en qualsevol moment que ara estem escrivint un programa
que utilitza punters i utilitza la memòria, i malloc més específicament,
definitivament entrar en l'hàbit de córrer tant temps
però molt fàcil de copiar i enganxar comandaments de Valgrind
per veure si hi ha alguns errors en aquest país.
I serà aclaparador cada vegada que veus la sortida,
però només a través d'analitzar visualment la totalitat del producte i veure si vostè veu les mencions d'errors
o advertències o invàlida o perduda.
Les paraules que sonen com et vas equivocar en algun lloc.
Així que adonar-se que és una nova eina en la seva caixa d'eines.
>> Ara el dilluns, vam tenir un munt de gent ve fins aquí
i representar la noció d'una llista enllaçada.
I presentem la llista enllaçada com una solució a quin és el problema?
Sí? [Resposta Estudiantil, inintel · ligible] Bé.
Les matrius no poden tenir memòria que s'agrega a ells.
Si assigna una matriu de mida 10, això és tot el que hi ha.
Vostè pot trucar a una funció com realloc si inicialment anomenada malloc,
i que pot tractar de créixer la matriu si no hi ha espai cap al final d'ella
que ningú més està utilitzant, i si no hi ha, s'acaba de trobar un tros més gran a un altre lloc.
Però llavors es copiarà tots aquests bytes en la nova matriu.
Això sona com una solució molt correcta.
Per què és poc atractiu?
Vull dir que funciona, els éssers humans han resolt aquest problema.
Per què hem de resoldre el dilluns amb llistes enllaçades? Sí?
[Resposta Estudiantil, inintel · ligible] Podria ser molt llarg.
De fet, cada vegada que vostè està trucant malloc o calloc o realloc, que és una més,
qualsevol vostè temps, el programa, estan parlant amb el sistema operatiu,
que tendeixen a frenar el programa de sota.
I si vostè està fent aquest tipus de coses en els bucles, en realitat està alentint.
No vas a notar això per al més simple de "Hello World" programes de tipus,
però en programes molt més grans, fent que el sistema operatiu i una altra per a la memòria
o donar de nou una i altra vegada no sol ser una bona cosa.
A més, és només una espècie d'intel · lectual - és una completa pèrdua de temps.
Per què assignar més memòria i més, el risc de copiar tot en la nova matriu,
si vostè té una alternativa que li permet assignar memòria només el que realment necessita?
Així que hi ha avantatges i desavantatges a aquí.
Un dels avantatges és que ara tenim dinamisme.
No importa on els trossos de memòria són que són gratuïtes,
Només pot ordenar de crear aquestes molles de pa a través de punters
per encadenar la cistella sencera units entre si.
Però em pagar almenys un preu.
>> Què he de renunciar a obtenir llistes enllaçades?
Sí? [Resposta Estudiantil, inintel · ligible] Bé.
Vostè necessita més memòria. Ara necessito espai per a aquests indicadors,
i en el cas d'aquesta super llista enllaçada simple
que només està tractant d'emmagatzemar sencers, que són 4 bytes, seguim dient
així, un punter és de 4 bytes, de manera que ara hem duplicat literalment
la quantitat de memòria que necessita només per emmagatzemar aquesta llista.
Però una vegada més, es tracta d'un compromís constant en la informàtica
entre el temps i l'espai i el desenvolupament, l'esforç i altres recursos.
Quin és altra desavantatge d'usar una llista enllaçada? Sí?
[Resposta Estudiantil, inintel · ligible]
Bé. No és tan fàcil d'accedir. Ja no podem aprofitar
setmana 0 principis com dividir i conquerir.
I més específicament, la recerca binària. Perquè tot i que els éssers humans
pot veure més o menys on la meitat d'aquesta llista és,
l'equip només sap que aquesta llista enllaçada comença en la direcció anomenat primer.
I això és 0x123 o alguna cosa per l'estil.
I l'única manera que el programa pot trobar l'element central
en realitat és buscar tota la llista.
I tot i així, literalment, ha de buscar en tota la llista perquè
fins i tot una vegada que arribi l'element central seguint els punters,
et, el programa, no tenen idea de quant temps aquesta llista és, en potència,
fins arribar a la final de la mateixa, i com saber programació
que estem al final d'una llista enllaçada?
Hi ha un punter NULL especial, de manera que una vegada més, una convenció.
En lloc d'utilitzar aquest punter, definitivament no volem que sigui un valor escombraries
apuntant en algun lloc fora de l'escenari, volem que sigui la mà cap avall, NULL,
així que tenim aquest terme en aquesta estructura de dades perquè sapiguem on acaba.
>> Què passa si volem manipular això?
Vam fer la major part d'això visualment, i amb els éssers humans,
però el que si volem fer una inserció?
Així que la llista original de 9, 17, 20, 22, 29, 34.
I si després volia malloc espai per al número 55, un node per a això,
i després volem inserir 55 a la llista de la mateixa manera que vam fer el dilluns?
Com podem fer això? Bé, Anita es va acostar i ella va caminar essencialment la llista.
Ella va començar en el primer element, després el següent, el següent, el següent, el següent, el següent.
Finalment va colpejar la mà esquerra fins al fons
i es va adonar oh, aquest és NULL. Llavors, què manipulació de punters que havia de fer?
La persona que estava a l'extrem, número 34, necessitava la seva mà esquerra aixecada
per assenyalar als 55, 55 necessitaven el seu braç esquerre cap avall per ser el nou terminador NULL. Fet.
Bastant fàcil d'inserir 55 a una llista ordenada.
I com podria aquest aspecte?
>> Deixin-me seguir endavant i obrir alguns exemple de codi aquí.
Vaig a obrir gedit, i em va deixar obrir dos arxius primer.
Un d'ells és list1.h, i permetin-me recordar-los que aquest era el tros de codi
que es va utilitzar per representar un node.
Un node té tant una crida int n i un punter proper anomenat que simplement apunta el següent en la llista.
Que es troba ara en un arxiu. H. Per què?
Hi ha una convenció, i no s'han aprofitat d'això una quantitat enorme de nosaltres mateixos,
però la persona que va escriure funcions printf i altres
va donar com a regal al món totes aquestes funcions en escriure un fitxer anomenat stdio.h.
I després hi ha string.h, i després hi Map.h, i no tots aquests arxius h
que es pot haver vist o utilitzat durant el terme escrit per altres persones.
Normalment, en els. Arxius h són úniques coses com typedefs
o declaracions de tipus personalitzats o declaracions de constants.
No posar les implementacions funcions 'en els arxius de capçalera.
Es posa, en canvi, només els seus prototips.
Poses les coses que vols compartir amb el món el que necessiten
amb la finalitat de compilar el codi. Així que per entrar en aquest hàbit,
vam decidir fer el mateix. No hi ha molt a list1.h,
però hem posat alguna cosa que podria ser d'interès per a les persones en el món
que volen utilitzar la nostra aplicació llista enllaçada.
Ara, en list1.c, no vaig a anar a través de tot aquest assumpte
perquè és una mica llarg, aquest programa, però anem a executar realment ràpid en l'indicador.
Permetin-me compilar list1, deixa a continuació, executeu list1, i el que veurem és
hem simulat un programa petit i senzill aquí
que permetrà a mi per afegir i treure els números d'una llista.
Així que seguirem endavant i m'escrigui 3 per l'opció de menú 3.
Vull inserir el nombre - de deixar fer el primer nombre, que tenia 9 anys,
i ara em diuen que la llista és ara 9.
Deixa anar endavant i fer-ho una altra inserció, de manera que vaig arribar a l'opció de menú 3.
A quin nombre desitja inserir? 17.
Retorn. I faré un més.
Permetin-me introduir el número 22.
Així que tenim el començament de la llista enllaçada que teníem en forma de diapositives fa un moment.
Com és aquesta inserció succeint realment?
En efecte, 22 es troba ara al final de la llista.
Així que la història ens diu a l'escenari el dilluns i tornar a tapar just ara
en realitat ha d'estar succeint en el codi.
Anem a fer una ullada. Permetin-me baixi aquest arxiu.
Anem a passar per alt algunes de les funcions,
però anirem a, per exemple, la funció d'inserció.
>> Anem a veure com fem per inserir un nou node a la llista enllaçada.
On és la llista declarat? Bé, anem a recórrer tot el camí fins a la part superior,
i noti que la cistella enllaçada és essencialment declarada com a únic punter és NULL inicialment.
Així que estic utilitzant una variable global aquí, que en general hem predicat contra
perquè fa que el seu codi una mica complicat de mantenir,
és una espècie de mandrós, en general, però no és mandrós i no és dolent i no és dolent
si sol propòsit del seu programa en la vida és per simular una llista enllaçada.
Que és exactament el que estem fent.
Així que en lloc de declarar això en principal i després haver de passar a totes les funcions
hem escrit en aquest programa, en lloc realitzar oh, anem a fer-global
perquè tot el propòsit d'aquest programa és demostrar una i només una llista enllaçada.
Així que se sent bé. Aquí són les meves prototips, i no anem a anar a través de tots ells,
però vaig escriure una funció d'eliminació, una funció de recerca, una funció d'inserció, i una funció de desplaçament.
Però ara anem a anar de nou a la funció d'inserció
i veure com es treballa aquí.
Insert està en línia - aquí anem.
Insereix. Així que no té cap argument, perquè demanarem
l'usuari dins d'aquesta funció per al número que voleu inserir.
Però abans, ens preparem per donar-los una mica d'espai.
Aquesta és una espècie de copiar i enganxar des de l'altre exemple.
En aquest cas, l'estaven assignant un int, aquest cop estem assignant un node.
Jo no me'n recordo quants bytes d'un node és, però això està bé.
Sizeof pot adonar-se d'això per mi.
I per què estic comprovant NULL en la línia 120?
Què podria sortir malament en la línia 119? Sí?
[Resposta Estudiantil, inintel · ligible]
Bé. Només podria donar-se el cas que li he demanat massa memòria
o que alguna cosa va malament i el sistema operatiu no té suficients bytes per donar-me,
pel que assenyala tant en tornar NULL, i si no comproven que
i jo cegament procedir a utilitzar l'adreça retornada, pot ser NULL.
Podria ser algun valor desconegut, no és una bona cosa si no jo -
en realitat no serà un valor desconegut. Pot ser NULL, pel que no vull
per abusar-ne i arriscar-se a dereferencing ella.
Si això passa, jo acabo de tornar i anem a fer veure que no he tingut cap record en absolut.
>> En cas contrari, li dic a l'usuari donar-me un número per inserir, que dic la nostra getInt vell amic,
i aquesta era la nova sintaxi es va introduir el dilluns.
'Newptr-> n' significa prendre la direcció que li van donar per malloc
que representa el primer byte d'un objecte nou node,
i després anar al camp anomenat núm.
Una pregunta de la trivia poc: Això és equivalent al que la línia més críptica de codi?
Com podria jo haver escrit això? Vols prendre una punyalada?
[Resposta Estudiantil, inintel · ligible]
Bé. Usant el núm., Però no és tan simple com això.
Què és el primer que fer? [Resposta Estudiantil, inintel · ligible]
Bé. He de fer newptr.n *.
Així que això ens diu nou punter és òbviament una adreça. Per què?
Com que va ser retornat per malloc. El newptr * dient "anar-hi"
i després una vegada que estàs allà, llavors vostè pot utilitzar el més familiar. n,
però això només es veu una mica lleig, sobretot si els éssers humans es van a
elaborar indicadors amb fletxes tot el temps, el món s'ha estandarditzat en aquesta notació fletxa,
que fa exactament el mateix.
Pel que només utilitzi l'opció -> notació quan la cosa de l'esquerra és un punter.
En cas contrari, si es tracta d'una estructura real, utilitzeu el núm ..
I després això: Per què inicialitzar newptr-> següent a NULL?
No volem que una mà esquerra penjant fora de la final de l'etapa.
Volem que apunta cap avall, el que significa que al final d'aquesta llista
podria ser en aquest node, així que millor assegurar-se que és NULL.
I, en general, la inicialització de les variables o dels seus membres de dades i estructures
a alguna cosa que és només una bona pràctica.
Deixar simplement escombraries existeixen i seguiran existint generalment et fica en problemes
si vostè s'oblida de fer alguna cosa en el futur.
>> Aquí hi ha uns pocs casos. Això, de nou, és la funció d'inserció,
i el primer que comprovar és si la variable anomenada en primer lloc,
aquesta variable global és NULL, que vol dir que no hi ha llista enllaçada.
No hem introduït cap número, per la qual cosa és trivial per inserir aquest nombre actual
a la llista, ja que només pertany al començament de la llista.
Així que això va ser quan Anita estava dret allà sola, pretenent
no hi havia ningú més per aquí a l'escenari fins que ens van assignar un node,
llavors podria aixecar la mà per primera vegada,
si tothom havia arribat a l'etapa després d'ella el dilluns.
Ara aquí, aquest és un petit escac que he de dir si el nou node de valor de n
és <que el valor de n en el primer node actual,
això vol dir que hi ha una llista enllaçada que ha començat.
Hi ha almenys un node a la llista, però aquest noi nou
pertany davant seu, així que hem de moure les coses.
En altres paraules, si la llista ha començat amb només, diguem,
només el número 17, que és el - en realitat, no podem fer-ho més clarament.
Si comencem la nostra història amb un punter aquí es diu en primer lloc,
i al principi és NULL, i ens inseriu el número 9,
el número 9 pertany clarament al començament de la llista.
Així que anem a pretendre que només malloced l'adreça o el número 9 i el va posar aquí.
Si el primer és de 9 per defecte, el primer escenari hem parlat només de mig punt que anem a aquest tipus aquí,
deixar això com NULL, ara tenim el número 9.
El següent número que voleu inserir és de 17.
17 pertany per aquí, així que haurem de fer una mica de lògica pas a pas a través d'aquest.
Així que en el seu lloc, abans de fer això, anem a suposar que volem inserir el número 8.
>> Així que, per conveniència, vaig a trucar aquí.
Però recordi, malloc pot posar gairebé qualsevol lloc.
Però pel bé de dibuix, ho vaig a posar aquí.
Així que pretendre que acabo d'assignar un node per al número 8, el que és nul per defecte.
I ara què ha de passar? Un parell de coses.
Hem fet aquest error a l'escenari dilluns al que actualitza un punter d'aquest tipus,
després ho va fer, i després va afirmar - que han quedat orfes a tots els altres en l'escenari.
Perquè puc - l'ordre de les operacions aquí és important,
perquè ara que hem perdut aquest node 9, que és només una espècie de surar en l'espai.
Així que això no és l'enfocament correcte de dilluns.
Primer hem de fer alguna cosa més.
L'estat del món es veu així. Inicialment, 8 ha estat assignada.
Quina seria una millor manera d'inserir 8?
En comptes d'actualitzar aquest primer indicador, només actualitzar aquest d'aquí el seu lloc.
Així que tenim una línia de codi que es convertirà aquest caràcter NULL
en un indicador real que s'assenyala en el node 9,
i llavors amb seguretat pot canviar primer a assenyalar a aquest tipus aquí.
Ara tenim una llista, una llista enllaçada, de dos elements.
I què significa això realment es veuen com aquí?
Si ens fixem en el codi, observi que he fet exactament això.
He dit newptr, i en aquesta història, newptr assenyalava a aquest tipus.
>> Així que permetin-me treure una cosa més, i jo hauria d'haver deixat l'habitació d'una mica més d'això.
Així de perdonar el petit dibuix diminut.
Aquest noi es diu newptr.
Aquesta és la variable que declarem unes poques línies abans, en línia - just per sobre de 25.
I està apuntant a 8. Així que quan dic newptr-> següent, el que significa anar a l'estructura
que està sent apuntat per newptr, així que aquí estem, anar-hi.
A continuació, a la fletxa que diu obtenir el següent camp i faci el signe = diu quin valor posar allà?
El valor que es trobava en primer lloc, quin valor estava en primer lloc?
En primer lloc s'assenyala en aquest node, pel que significa això ara ha d'apuntar a aquest node.
En altres paraules, encara que el que sembla un embolic ridícul amb la meva lletra,
Què és una idea simple de moure només al voltant d'aquestes fletxes
es tradueix a codi amb només aquest traçador de línies.
Guardi el que està en primer lloc al següent camp i després actualitzar el primer que realment és.
Seguirem endavant i avanç ràpid a través d'alguna cosa d'això,
i que únicament busqui en aquesta inserció col per ara.
Suposem que arribo al punt en què em sembla que el següent camp d'un node és NULL.
I en aquest punt de la història, un detall que m'estic passant per alt
és que he introduït un altre punter fins aquí a la línia 142, el punter predecessor.
Essencialment, en aquest moment de la història, una vegada que la llista es fa llarga,
Jo com que hagi de caminar amb dos dits perquè si vaig massa lluny,
Recordo que en una sola llista llarga durada, no es pot tornar enrere.
Així que aquesta idea de predptr és meu dit esquerre, i newptr - no newptr.
Un altre indicador que aquí és el meu altre dit, i jo sóc només una mica de caminar a la llista.
És per això que existeix. Però considerarem només un dels casos més simples aquí.
Si el camp al costat d'aquest punter és NULL, quina és la implicació lògica?
Si vostè està travessant aquesta llista i et trobes amb un punter NULL?
Vostè és al final de la llista, de manera que el codi per afegir aquest element a continuació, un addicional
és un gènere del que intuïtiu prendrà aquest node la pròxima punter és NULL,
així que això és actualment NULL, i canviar, però, és l'adreça del nou node.
Així que estem dibuixant en el codi de la fletxa que dibuixem a l'escenari per aixecar la mà esquerra d'una persona.
>> I el cas que vaig a agitar les mans menys per ara,
només perquè crec que és fàcil perdre quan ho fem en aquest tipus d'entorn,
és la comprovació d'inserció en la part mitjana de la llista.
Però només intuïtivament, el que ha de passar si vostè vol esbrinar
on algun nombre s'ha de posar en el centre és que has de caminar
amb més d'un dit, més d'un punter,
esbrinar on ha d'estar per comprovar és l'element <l'actual,
> L'actual, i una vegada que trobi aquest lloc,
llavors vostè ha de fer aquest tipus de joc de la closca on es mouen al voltant dels punters amb molta cura.
I aquesta resposta, si ho desitja a la raó a través d'això a casa pel seu compte,
es redueix només a aquestes dues línies de codi, però l'ordre de les línies és súper important.
Perquè si li cau la mà d'algú i aixecar una altra persona en l'ordre equivocat,
una vegada més, que podria acabar deixant orfes a la llista.
Per resumir conceptualment més, la inserció de la cua és relativament senzill.
La inserció al cap és també relativament senzill,
però cal actualitzar un punter addicional en aquesta ocasió
per esprémer el número 5 a la llista aquí,
i després introduir-se en el medi implica un esforç encara més,
per inserir acuradament el número 20 en la seva ubicació correcta,
que és entre 17 i 22.
Així que cal fer alguna cosa com tenir el nou node de 20 punts a 22,
i, a continuació, punter que node necessita ser actualitzat per darrera?
És 17 que en realitat inserir.
Així que de nou, vaig a ajornar el codi real perquè l'aplicació particular.
>> A primera vista, és una mica aclaparador, però no deixa de ser un bucle infinit
que està llaç, llaç, llaç, llaç, i trencar tan aviat com es va colpejar el punter NULL,
moment en què vostè pot fer la inserció requerida.
Això, llavors, és el representant codi vinculat inserció llista.
Això va ser una mica molt, i se sent com que hem resolt un problema,
però hem introduït un altre conjunt. Francament, ens hem passat tot aquest temps
en gran O i Ω i el temps de funcionament, tractant de resoldre els problemes més ràpidament,
i aquí estem donant un gran pas cap enrere, se sent.
I, no obstant això, si l'objectiu és emmagatzemar les dades,
se sent com el Sant Grial, com vam dir el dilluns, seria realment
per guardar les coses a l'instant.
>> En efecte, suposem que hem fet la llista de banda per un moment vinculat
i que en comptes introduït el concepte d'una taula.
I anem a pensar en una taula per un moment com una matriu.
Aquesta matriu i aquest cas aquí té uns 26 elements, del 0 al 25,
i suposo que necessitava una mica tros d'emmagatzematge per als noms:
Alice i Bob i Charlie i similars.
I es necessita algun tipus d'estructura de dades per emmagatzemar aquests noms.
Bé, podries utilitzar alguna cosa com una llista enllaçada
i es podia caminar per la llista d'inserir Alice abans que Bob i Charlie després que Bob i així successivament.
I, de fet, si vostè vol veure un codi com el que en un a part,
Sabem que en list2.h, fem exactament això.
No entrarem a través d'aquest codi, però això és una variant del exemple primer
que introdueix una estructura que hàgim vist abans estudiant anomenat,
i llavors el que realment emmagatzema en la llista enllaçada és un punter a una estructura estudiant
en lloc d'un nombre enter petit i senzill, núm.
Així que adonar-se que hi ha codi cal implica cadenes reals,
però si l'objectiu que ens ocupa realment ara és abordar el problema de l'eficiència,
No seria bo si se'ns dóna un objecte anomenat Alice,
volem posar-la al lloc adequat en una estructura de dades,
se sent com que seria molt agradable per posar només Alice,
el nom comença amb A, a la primera ubicació.
I Bob, el nom comença per B, en la segona ubicació.
Amb una matriu, o anem a començar a cridar a una taula, una taula hash en què,
podem fer exactament això. Si ens donen un nom com Alice,
una cadena com Alice, on posar A-l-i-c-i?
Necessitem un hueristic. Necessitem una funció per prendre alguna entrada com Alícia
i tornar una resposta: "Posa Alice en aquest lloc."
I aquesta funció, aquest quadre de negre, es dirà una funció hash.
>> Una funció hash és una cosa que pren una entrada, com "Alice",
i torna a la qual, en general, la ubicació numèrica en alguna estructura de dades on Alice pertany.
En aquest cas, la nostra funció de hash ha de ser relativament simple.
La nostra funció hash ha de dir, si se li dóna "Alice", que el personatge em deu importar?
La primera d'elles. Així que miro [0], i després em diuen si [0] és un personatge, torni el número 0.
Si és B, tornarà 1. Si es tracta de C, tornar 2, i així successivament.
Tots índex 0, i que em permeti inserir Alice i Bob i Charlie i així successivament
en aquesta estructura de dades. Però hi ha un problema.
I si Anita ve una altra vegada?
On posem Anita? El seu nom també comença amb la lletra A,
i se sent com que hem fet un embolic encara més gran d'aquest problema.
Ara tenim la inserció immediata, inserció constant de temps, en una estructura de dades
en comptes de pitjor cas lineal,
però què podem fer amb Anita en aquest cas?
Quines són les dues opcions, de debò? Sí?
[Resposta Estudiantil, inintel · ligible] Bé, pel que podríem tenir una altra dimensió.
Això és bo. Així que podem construir coses en 3D com parlem verbalment dilluns.
Podríem afegir un altre accés aquí, però suposo que no, estic tractant de mantenir això simple.
L'objectiu general aquí és tenir immediat accés en temps constant,
de manera que està afegir massa complexitat.
Quines són les altres opcions quan es tracta d'inserir Anita en aquesta estructura de dades? Sí?
[Resposta Estudiantil, inintel · ligible] Bé. Així que ens podíem moure tots els altres cap avall,
com Charlie cops de colze per Bob i Alice, i després posem Anita on ella realment vol ser.
>> Per descomptat, ara, no hi ha un efecte secundari d'això.
Aquesta estructura de dades és probablement útil no perquè volem inserir la gent un cop
sinó perquè volem comprovar si estàs allà més tard
si volem imprimir tots els noms en l'estructura de dades.
Anem a fer alguna cosa amb aquestes dades amb el temps.
Així que ara tinc classe de fotut Alice, que ja no és on se suposa que ha de ser.
Ni Bob ni és Charlie.
Així que potser aquesta no és una idea tan bona.
Però en realitat, aquesta és una opció. Podríem passar a tothom,
o diables, Anita va arribar tard al joc, per què no acaba de posar Anita
aquí no, aquí no, aquí no, anem a posar una mica més avall en la llista.
Però el problema comença a delegar de nou.
Vostè pot ser capaç de trobar l'instant Alice, basada en nom seu.
I Bob instant, i Charlie. Però després buscar Anita,
i ja veus, hmm, Alice es troba en el camí.
Bé, deixa veure per sota d'Alice. Bob no és Anita.
Charlie no és Anita. Oh, no és Anita.
I si continua aquesta línia de la lògica fins al final,
Quin és el temps d'execució del pitjor cas de trobar o inserir Anita en aquesta nova estructura de dades?
És O (n), no?
Com que en el pitjor dels casos, no és Alice, Bob, Charlie. . .
tot el camí a algú que es diu "I", de manera que només hi ha un lloc a l'esquerra.
Afortunadament, no tenim a ningú anomenat "Z", així que vam posar Anita a la part inferior.
>> Realment no hem resolt aquest problema.
Així que potser cal introduir aquesta tercera dimensió.
I resulta que, si estem d'introduir aquesta tercera dimensió,
no podem fer això perfectament, però el Sant Grial s'aconseguirà
constant de temps d'inserció i les insercions dinàmics de manera que
no hem de codificar una matriu de mida 26.
Podem inserir tants noms com vulguem, però prendrem nostre fill de 5 minuts de descans aquí
i després fer-ho correctament.
Està bé. Vaig posar la història fins bastant artificial no
per l'elecció d'Alice i Bob i Charlie i Anita,
el nom va ser, òbviament, va a xocar amb Alice.
Però la pregunta que va acabar dilluns amb és com de probable és
que es podrien obtenir aquest tipus de col · lisions? En altres paraules,
si comencem a utilitzar aquesta estructura tabular, que és en realitat una matriu,
en aquest cas de 26 llocs,
I si en lloc nostres entrades estan uniformement distribuïts?
No és artificialment Alice i Bob i Charlie i David, i així successivament per ordre alfabètic,
està distribuïda uniformement sobre l'A a la Z.
>> Potser només haurem de tenir sort i que no tindrem dos A o B de dos
amb una probabilitat molt alta, però com algú ha assenyalat,
si es va generalitzar aquest problema i no fer 0-25
però, per exemple, de 0 a 364 o 65 anys, sovint el nombre de dies en un any típic,
i la pregunta, "¿Quina és la probabilitat que dos de nosaltres en aquesta sala tenen el mateix aniversari?"
Dit d'una altra manera, quina és la probabilitat que dos de nosaltres té un nom que comença amb A?
El tipus de pregunta és la mateixa, però aquest espai d'adreces,
aquest espai de recerca, és més gran en el cas d'aniversari,
perquè tenim més de tants dies l'any que les lletres de l'alfabet.
Quina és la probabilitat d'una col · lisió?
Bé, podem pensar en això per esbrinar les matemàtiques en sentit contrari.
Quina és la probabilitat de col · lisions no?
Doncs bé, aquesta expressió aquí diu que el que és la probabilitat
si hi ha una sola persona en aquest saló, que celebra el seu aniversari únic?
És 100%. Perquè si hi ha una sola persona a l'habitació,
seu aniversari pot ser qualsevol dels 365 dies de l'any.
Així que les opcions de 365/365 em dóna un valor d'1.
Així que la probabilitat que es tracti en el moment és només 1.
Però si hi ha una segona persona a l'habitació,
Quina és la probabilitat que el seu aniversari és diferent?
Només hi ha 364 dies possibles, fent cas omís dels anys de traspàs,
pel seu aniversari no xocar amb les altres persones.
Així que 364/365. Si una tercera persona entra, és 363/365, i així successivament.
Així que seguim multiplicant aquestes fraccions, que són cada vegada més petits,
per esbrinar quina és la probabilitat que tots nosaltres tenim aniversari únics?
Però podem, és clar, acaba de prendre aquesta resposta i donar-li la volta al voltant
i fer 1 menys tot això, una expressió que finalment va a aconseguir
si et recordes de la part posterior dels seus llibres de matemàtiques, es veu una mica d'alguna cosa com això,
que és molt més fàcil d'interpretar gràficament.
I aquí té aquest gràfic en l'eix x el nombre d'aniversari,
o el nombre de persones amb aniversari, i sobre l'eix i és la probabilitat d'una coincidència.
I el que això vol dir és que si vostè té, diguem, fins i tot,
anem a triar una cosa així com 22, 23.
Si hi ha 22 o 23 persones a la sala,
la probabilitat que dues d'aquestes poques persones tindran el mateix aniversari
en realitat és súper alta, combinatòria.
50% de probabilitat que en una classe de només 22 persones, un seminari, pràcticament,
2 de aquestes persones tindran el mateix aniversari.
Perquè hi ha moltes maneres en què vostè pot tenir el mateix aniversari.
Pitjor encara, si ens fixem en la part dreta de la taula,
pel temps que té una classe amb 58 estudiants en el mateix,
la probabilitat que dues persones que tenen un alt aniversari és super, super, prop del 100%.
Ara, això és una mena de fet de la diversió de la vida real.
>> Però les implicacions, ara, per les estructures de dades i emmagatzematge d'informació
significa que només suposant que té un bonic, net distribució uniforme de les dades
i té una àmplia prou gran per a un munt de coses
no vol dir que vostè va a fer que la gent en llocs únics.
Vas a tenir col · lisions. Així que aquesta noció de hashing, com se l'anomena,
tenint una entrada com "Alice" i el massatge d'alguna manera
i després tornar a una resposta com 0 o 1 o 2.
Tornant una mica de la sortida de funció que està plena d'aquesta probabilitat de col · lisió.
Com podem gestionar aquestes col · lisions?
Doncs bé, en el primer cas, podem prendre la idea que es suggereix.
Només podem canviar a tot el món, o potser, una mica més simple,
en comptes del món es mouen més, mourem Anita a la part inferior del lloc disponible.
Així que si Alice es troba en 0, Bob està en 1, Charlie està a 2,
només haurem de posar Anita del punt 3.
I aquesta és una tècnica en l'estructura de dades anomenada sondeig lineal.
Lineal perquè estàs caminant aquesta línia, i vostè és una espècie de sondeig
per als punts disponibles en l'estructura de dades.
Per descomptat, això es convertís en O (n).
Si l'estructura de dades és molt complet, hi ha 25 persones en el que ja,
i llavors Anita arriba, ella acaba en el que seria la ubicació Z, i això està bé.
Ella encara li queda, i podem trobar més tard.
>> Però això és contrari a l'objectiu d'accelerar les coses.
Llavors, què passaria si en comptes introduïda aquesta tercera dimensió?
Aquesta tècnica s'anomena generalment encadenament separat, o que té cadenes.
I el que una taula hash és, aquesta estructura tabular,
la taula és només un conjunt de punters.
Però el que els punters assenyalar és conjectura què?
Una llista enllaçada. I què si prenem el millor d'ambdós mons?
Nosaltres fem servir arrays per als índexs inicials
en l'estructura de dades de manera que a l'instant es pot anar a [0] [1], [30] o així successivament,
però perquè tinguem una mica de flexibilitat i podem encaixar Anita i Alice i Adam
i qualsevol altre Un nom,
en lloc de deixar que l'altre eix créixer arbitràriament.
I finalment, a partir de dilluns, tenen aquesta capacitat expressiva amb llista enllaçada.
Es pot conrear una estructura de dades arbitrària.
Com a alternativa, podríem fer una enorme varietat 2-dimensional,
però això serà una situació terrible si una de les files d'una matriu 2-dimensional
no és prou gran com perquè la persona addicional el nom passa a començar amb A.
Déu ens lliure d'haver de reassignar un enorme 2-dimensional estructura
només perquè hi ha tantes persones nomenades A,
especialment quan hi ha tan poques persones nomenades alguna cosa Z.
És només serà una estructura de dades molt escassos.
Així que no és perfecte, per qualsevol mitjà, però ara almenys tenim la capacitat
per trobar l'instant en què Alice o Anita pertany,
si més no en termes de l'eix vertical,
i llavors només hem de decidir on posar Anita o Alícia al país d'aquesta llista vinculada.
Si no es preocupen per resoldre les coses, amb quina rapidesa podem inserir Alice en una estructura com aquesta?
És temps constant. Ens índex en [0], i si no n'hi ha un,
Alice va al començament de la llista vinculada.
Però això no és un gran negoci. Perquè si Anita després ve
un cert nombre de passos més endavant, d'on Anita pertany?
Bé, [0]. Programació orientada a objectes. Alice es troba en aquesta llista enllaçada.
>> Però si no et fa res la classificació d'aquests noms,
que només pot moure a través d'Alice, inserir Anita, però fins i tot això és la constant de temps.
Encara que no hi ha Alice i Adam i tots aquests altres noms A,
en realitat no és que canviant físicament. Per què?
Com que acabem de fer aquí amb llista enllaçada, qui sap van ser aquests nodes són de totes maneres?
Tot el que has de fer és moure el pa ratllat.
Moveu les fletxes voltant, vostè no ha de moure físicament les dades al voltant.
Així que podem inserir Anita, en aquest cas, a l'instant. Constant de temps.
Així que tenim temps constant de recerca, i la constant de temps d'inserció d'algú com Anita.
Però espècie de simplificar en excés el món.
I si més endavant decidiu trobar Alice?
Quants passos es que prendrà?
[Resposta Estudiantil, inintel · ligible]
Exactament. El nombre de persones abans que Alícia al país de la llista enllaçada.
Així que no és del tot perfecte, perquè la nostra estructura de dades, un cop més, té aquest accés vertical
i llavors té aquestes llistes enllaçades que pengen - en realitat, no cal dibuixar una matriu.
Ha aquestes llistes enllaçades penjant d'ella que s'assembla una mica alguna cosa com això.
Però el problema és que si Alice i Adam i tots aquests altres noms un
acaben més i més enllà,
trobar algú podria acabar tenint un munt de passos,
bcause has de recórrer la llista enllaçada,
que és una operació lineal.
Així que en realitat, llavors, el temps d'inserció en última instància és O (n), on n és el nombre d'elements a la llista.
Dividit per, anem arbitràriament anomenem m, on m és el nombre de llistes enllaçades
que tenim en aquest eix vertical.
En altres paraules, si realment suposen una distribució uniforme dels noms,
totalment irreal. Òbviament hi ha més d'unes cartes que altres.
>> Però si suposem de moment una distribució uniforme,
i tenim n persones en total, i les cadenes de m totals
disponibles per a nosaltres, llavors la longitud de cadascuna d'aquestes cadenes
bastant simplement serà el total, n dividit pel nombre de cadenes.
Llavors n / m. Però aquí és on podem ser matemàticament tot llest.
m és una constant, ja que hi ha un nombre fix d'aquests.
Vostè va a declarar l'array al principi,
i no estem canviant la mida de l'eix vertical. Per definició, que roman fix.
És només l'eix horitzontal, per dir-ho, això està canviant.
Així que, tècnicament, és una constant. Així que ara, el temps d'inserció
és més o menys O (n).
Així que no se sent tot el que molt millor.
Però, què és la veritat? Bé, tot aquest temps, durant setmanes,
que hem estat dient O (n ²). O (n), 2 x n ², - n, dividit per 2. . . ech.
És només ² n. Però ara, en aquesta part del semestre,
podem començar a parlar sobre el món real de nou.
I n / m és absolutament més ràpid que només n sol.
Si vostè té mil noms, i els trenquen en cubs múltiples
de manera que només té deu noms en cadascuna d'aquestes cadenes,
buscant absolutament deu coses que serà més ràpid que un miler de coses.
I així, un dels conjunts de problemes futurs serà desafiar
a pensar exactament que tot i que, sí,
asimptòticament i matemàticament, això és només lineal,
que aspira, en general, quan es tracta de trobar les coses.
En realitat, serà més ràpid que el
perquè d'aquest divisor.
Així que hi ha de nou serà aquest trade-off
i aquest conflicte entre la teoria i la realitat,
i un dels comandaments començarà a girar en aquest punt en el semestre
és més aviat l'única realitat com una mena de preparació per a la final semster,
com es presenta el món de la programació web,
on realment, el rendiment explicarà perquè els usuaris van a
comença a sentir i apreciar les males decisions de disseny.
>> Llavors, com vostè va sobre la implementació d'un vinculat - una taula hash amb 31 elements?
I l'exemple anterior va ser arbitràriament els aniversaris.
Si algú té un aniversari l'1 de gener o l'1 de febrer, les posarem en aquest cub.
Si es tracta de 02 de gener, 2 de febrer, 2 de març, els posarem en aquest cub.
És per això que tenia 31 anys. Com es declara una taula hash?
Pot ser molt simple, taula * node és el meu nom arbitrari per a ell, [31].
Això em dóna 31 punters a nodes,
i que em permet tenir 31 punters a llistes enllaçades
fins i tot si aquestes cadenes són inicialment NULL.
Què és el que vull fer si vull guardar "Alice", "Bob", "Charlie"?
Bé, hem de embolicar les coses en una estructura
perquè necessitem Alice perquè apunti a Bob, perquè apunti a Charlie, i així successivament.
No podem tenir els noms sols, de manera que podria crear una nova estructura anomenada node aquí.
>> Què és un node real? Què és un node en aquesta nova llista lligada?
El primer, anomenat paraula, és el nom de la persona.
LONGITUD, presumiblement, es refereix a la longitud màxima del nom d'un ésser humà,
sigui el que sigui, 20, 30, 40 personatges en casos extrems bojos,
i un és per què? És només el caràcter NULL extra, \ 0.
Així que aquest node està acabant "alguna cosa" dins de si mateixa,
sinó que també declara un punter anomenat proper
perquè puguem cadena Alice a Bob a Charlie i així successivament.
Pot ser NULL, però no necessàriament ha de ser.
Qualsevol pregunta sobre aquestes taules hash? Sí?
[Estudiant que fa la pregunta, inintel · ligible] Matriu - bona pregunta.
Per què és aquesta paraula char en una matriu en lloc de només char *?
En aquest exemple un tant arbitrari, no vull haver de recórrer
a malloc per a cada un dels noms originals.
Jo volia declarar una quantitat màxima de memòria per a la cadena
perquè jo pogués copiar en l'estructura Alice \ 0 i no haver de bregar amb malloc i lliure i similars.
Però podria fer-ho si volia ser més conscients de l'ús de l'espai. Bona pregunta.
Així que anem a tractar de generalitzar lluny d'aquest
i enfocar la resta d'avui en estructures de dades més generalment
i altres problemes que es poden resoldre utilitzant els mateixos fonaments
tot i que les estructures de dades es poden diferir en els seus detalls.
>> Així que resulta en ciències de la computació, els arbres són molt comuns.
I es pot pensar en una espècie d'arbre com un arbre genealògic,
on hi ha algunes arrels, alguns matriarca o patriarca,
àvia o l'avi o l'esquena abans,
sota de la qual són mare i pare o germans diferents o similars.
Així que una estructura d'arbre té nodes i té fills,
normalment 0 o més fills de cada node.
I alguns de l'argot que vostè veu en aquest dibuix aquí
és qualsevol dels fills o néts petits a les vores
que no tenen fletxes que emanen d'ells,
aquestes són les fulles anomenats, i qualsevol persona a l'interior
és un node intern, es pot dir qualsevol cosa per l'estil.
No obstant això, aquesta estructura és bastant comú. Aquest és una mica arbitrària.
Tenim un nen de l'esquerra, tenim tres fills a la dreta,
dos nens a la part inferior esquerra.
Així que podem tenir diferents arbres de mida, però si comencem a normalitzar les coses,
i es pot recordar aquest vídeo de Patricio, en la recerca binària d'un curt anterior
recerca en línia, binari no ha de ser implementat amb una matriu
o trossos de paper en una pissarra.
Suposem que voleu emmagatzemar els nombres en una estructura de dades més sofisticada.
Es pot crear un arbre com aquest.
Podria tenir un node declara en C, i que el node pot tenir com a mínim dos elements del seu interior.
Un d'ells és el número que voleu emmagatzemar, i l'altre és - bé, necessitem un més.
Els altres són els seus fills.
Així que aquí està una altra estructura de dades. Aquesta vegada, un node es defineix com l'emmagatzematge d'un nombre n
i després dos punters, fill esquerre i el fill dret.
I no són arbitràries. El que és interessant sobre aquest arbre?
>> Quin és el patró de la manera en què hem establert això o com Patrick es presenta en el seu vídeo?
És bastant obvi que hi ha una classificació que passa aquí,
però quina és la regla simple? Sí?
[Resposta Estudiantil, inintel · ligible]
Perfecte. Si fes un cop d'ull a això, veurà els números petits a l'esquerra,
els grans nombres de l'esquerra, però això és cert per a cada node.
Per a cada node, el seu fill esquerre menor que ell, i el seu fill gran dret que ell.
El que això significa és que si vull cercar en aquesta estructura de dades per, per exemple, el número 44,
He de començar des de l'arrel, perquè igual que amb totes aquestes estructures de dades més complexes ara,
només tenim un punter a una sola cosa, el principi.
I en aquest cas, el principi és l'arrel. No és l'extrem esquerre,
que és l'arrel d'aquesta estructura. Així que veig aquí és de 55 anys, i estic buscant 44.
En quina direcció vull anar?
Bé, jo vull anar a l'esquerra, perquè, òbviament, a la dreta serà massa gran.
Així notar aquí, estàs de sort conceptualment tallar l'arbre per la meitat
perquè mai vas a baix a la dreta.
Així que ara me n'aniré de la 55 a la 33. És massa petit d'un nombre.
Estic buscant a 44, però ara sé que si 44 és en aquest arbre, puc anar, òbviament, a la dreta.
Així que de nou, estic podant l'arbre per la meitat.
És gairebé idèntic conceptualment a la guia telefònica.
És idèntic al que vam fer amb els papers a la pissarra,
però és una estructura més sofisticada que ens permet fer realitat
aquest divideix i venceràs per disseny de l'algorisme,
i, de fet, que travessa una estructura com aquesta - crits.
Travessant una estructura com aquesta, on és només "anar per aquest camí o anar per aquest camí"
significa tot el codi que es va inclinar a la seva ment en un primer moment, al posar-la en la secció
o caminar a través d'ell a casa, per a la recerca binària, utilitzant recursió o iteració,
és un dolor al coll. Busqui l'element central, a continuació, fer el seu arrodoniment cap amunt o cap avall.
>> Hi ha una bellesa en això perquè ara podem utilitzar la recursivitat de nou,
però molt més neta. De fet, si vostè és al número 55 i que desitja trobar 44,
vostè va a l'esquerra en aquest cas, llavors, què fa vostè? Vostè corre el mateix algoritme exacte.
Es comprova el valor del node, aneu a l'esquerra oa la dreta.
A continuació, comproveu el valor del node, aneu a l'esquerra oa la dreta.
Això s'adapta perfectament a la recursivitat.
Així que, encara que en el passat hem fet alguns exemples bastant arbitràries que impliquen recursió
que no tenia per què ser recursiu, amb stuctures de dades,
especialment els arbres, és una perfecta aplicació d'aquesta idea de tenir un problema,
contracció, i després resoldre el mateix tipus de, però més petit programa,.
>> Així que hi ha una altra estructura de dades que podem introduir.
Aquest està dissenyat a primera vista, sembla críptic, però això és increïble.
Així que aquesta és una estructura de dades anomenada triennis, triennis, que s'hereta de la recuperació de paraules,
que no es pronuncia re-try-val, però això és el que el món anomena aquestes coses. Tracta. T-r-i-i.
Es tracta d'una estructura d'arbre d'algun tipus, però cada un dels nodes en un triennis
sembla què? I això és una mica enganyós, ja que és una espècie de abreujat.
Però sembla que cada node en aquest trienni és en realitat una matriu.
I tot i que l'autor d'aquest diagrama no ho ha demostrat,
en aquest cas, aquest triennis és una estructura de dades el propòsit a la vida és per emmagatzemar paraules
com A-l-i-c-i o B-ob-.
I la manera com aquestes dades emmagatzema Alice i Bob i Charlie i Anita i altres
S'utilitza una matriu per emmagatzemar el qual Alícia al país d'un triennis,
es comença en el node arrel que s'assembla a una matriu,
i que ha estat escrit en notació abreujada.
L'autor omet abcdefg perquè no havia noms amb això.
Ells només va mostrar M i P i T, però en aquest cas,
passarem lluny d'Alice i Bob i Charlie a alguns noms que són aquí.
Maxwell és en realitat en aquest diagrama.
Llavors, com va fer l'autor botiga M-a-x-w-i-l-l?
Ell o ella va començar en el node arrel, i es va anar a [M], de manera més o menys 13, la 13 ª posició en la matriu.
Després, des d'allà, hi ha un punter.
Un punter que porta a una altra matriu.
A partir d'aquí l'autor indexada en aquesta matriu en la posició A, com es mostra a la part superior esquerra hi ha,
i llavors ell o ella va seguir a aquest punter a una altra matriu,
i se'n va anar al punter en la ubicació X.
Després, a la següent ubicació matriu W, E, L, L, i així successivament,
i, finalment, tractarem de posar en realitat una imatge a aquesta.
Com és un node com en el codi?
Un node en un trienni conté una matriu de punters a més nodes.
Però també cal ser algun tipus de valor booleà, si més no en aquesta implementació.
Passa que em diuen is_word. Per què?
Perquè quan vas a inserir Maxwell, vostè no està inserint
res en aquesta estructura de dades.
No estàs escrivint M. No estàs escrivint X.
Tot el que estem fent és seguir punters.
El punter que representa M, llavors el punter que representa A,
a continuació, el punter que representa X, llavors W, E, L, L,
però el que cal fer al final és una espècie d'anar, passar, vaig arribar a aquest lloc.
Hi havia una paraula que acaba aquí, en l'estructura de dades.
>> Llavors, què és realment un trienni plena i l'autor va triar per representar
aquestes estacions terminals amb petits triangles.
Això només vol dir que el fet d'aquest triangle és aquí, aquest valor booleà de true
vol dir que si vostè va cap enrere en l'arbre,
el que significa una paraula anomenada Maxwell està en això.
Però la paraula foo, per exemple,
No heu arbre, perquè si em poso en el node arrel fins aquí a la part superior,
No hi ha cap indicador f, o no punter, punter o no. Foo no és un nom en aquest diccionari.
Però per contra, Turing, t-o-r-i-n-g. Un cop més, no emmagatzemar o o t o r i o n o g.
Però ho vaig fer botiga en aquesta estructura de dades un valor de veritable camí aquí en aquest node - a l'arbre
establint aquest valor booleà de is_word a true.
Així que un trienni és una espècie d'aquesta estructura meta molt interessant,
on vostè no està realment emmagatzemar les paraules mateixes d'aquest tipus de diccionari.
Perquè quedi clar, només estàs emmagatzemant si o no, hi ha una paraula que acaba aquí.
>> Ara, quina és la implicació?
Si té 150.000 paraules en un diccionari que vostè està tractant d'emmagatzemar en la memòria
utilitzen una part com una llista enllaçada,
vostè va a tenir 150.000 nodes a la llista enllaçada.
I trobar una d'aquestes paraules alfabèticament podria prendre O (n) temps.
El temps lineal. Però en el cas aquí d'un triennis,
Quin és el temps de durada de la recerca d'una paraula?
Resulta que la bellesa aquí és que encara que vostè té ja 149.999 paraules en aquest diccionari,
tal com s'aplica amb aquesta estructura de dades,
Quant de temps es triga a trobar o inserir una persona més en això, com Alice, Alice?
Bé, és només 5, potser 6 passos per al caràcter final.
Com que el presense d'altres noms en l'estructura
no posar-se en el camí de la inserció d'Alice.
D'altra banda, la recerca d'Alice vegada hi ha 150.000 paraules en aquest diccionari
no posar-se en el seu camí de recerca d'Alice en absolut,
perquè Alice és. . . . . aquí, perquè em vaig trobar amb un valor booleà.
I si no hi ha valor booleà veritable, llavors Alícia no està en aquesta estructura de dades de paraules.
En altres paraules, el temps d'execució de trobar coses i la inserció de les coses en aquest nou
estructura de dades del trienni és de O - no és n.
Com que el presense de 150.000 persones no té efecte en Alice, sembla.
Així que anem a dir k, on k és la longitud màxima d'una paraula en anglès
que és típicament no més de 20-alguna cosa caràcters.
Així que k és una constant. Així que el Sant Grial sembla que hem trobat ara
és la d'un temps triennis, constant per les insercions, per les recerques, per les delecions.
Com que el nombre de coses que ja estan en l'estructura,
que ni tan sols són físicament allà. Un cop més, són només una espècie de marcat, si o no,
no té impacte en el seu temps de funcionament futur.
>> Però hi ha d'haver un parany, en cas contrari no hauria perdut tant de temps
en totes aquestes estructures de dades només per finalment arribar a la un secret que és increïble.
Llavors, ¿quin preu estem pagant per assolir aquesta grandesa en aquesta llista? Espai.
Aquesta cosa és enorme. I la raó que l'autor
no ho presentem aquí, noti que totes aquestes coses que s'assemblen a les matrius,
no va treure la resta de l'arbre, la resta de la triennis,
perquè no són només rellevants per a la història.
Però tots aquests ganglis són super àmplia, i cada node en l'arbre de presa
26 o en realitat, podria ser 27 caràcters perquè en aquest cas jo estava amb espai perquè l'apòstrof
perquè puguem tenir paraules apòstrof.
En aquest cas, es tracta d'àmplies gammes. Així que, encara que no estan picutured,
això pren una quantitat massiva de RAM.
El que podria estar bé, especilly en maquinari modern,
però aquesta és la compensació. Tenim menys temps per la despesa de més espai.
Llavors, on està tot això anirà?
Bé, anem a fer - anem a veure aquí.
Anem a fer un salt a aquest tipus aquí.
>> El creguis o no, tan divertit com C ha estat per algun temps,
estem arribant a un punt en el semestre en que és el moment de fer la transició a les coses més modernes.
Les coses en un nivell superior. I tot i que durant el proper parell de setmanes
encara ens segueixen ens submergim en el món dels punters i la gestió de memòria
per aconseguir que la comoditat amb la qual es pot construir,
al final del joc és en última instància a introduir, irònicament, no aquesta llengua.
Passarem, com 10 minuts parlant HTML.
Tots HTML és un llenguatge de marques, i el que és un llenguatge de marques
És aquesta sèrie de claudàtors oberts i tancats suports que diuen "fer aquesta audaç"
"Fer això" cursiva "fer aquesta centrada.
No és tot el que intel · lectualment interessant, però és molt útil.
I sens dubte és omnipresent en aquests dies.
Però el que és de gran abast sobre el món d'HTML i programació web en general,
està construint coses dinàmiques, a programar en llenguatges com PHP o Python o Ruby o Java o C #.
En definitiva, sigui quin sigui el seu idioma d'elecció és, i generar HTML dinàmicament.
Generació d'una cosa anomenada CSS dinàmicament.
Fulls d'estil en cascada, que és també l'estètica.
I així, tot i que, avui en dia, si vaig a algun lloc web Google.com com el familiar,
i vaig a veure, desenvolupador, edita, el que potser vostè ha fet abans,
però anem a veure el codi font, això probablement es veu bastant críptic.
Però aquest és el codi subjacent que implementa Google.com.
A la part davantera. I en realitat tot això és matèria estètica suau i esponjosa.
Aquest és el CSS aquí. Si mantinc el desplaçament cap avall aconseguirem algunes coses amb codis de color.
Això és HTML. Codi de Google sembla un embolic, però si realment obrir una finestra diferent,
podem veure certa estructura a aquesta.
Si obro això, notar aquí, que és una mica més llegible.
Anem a veure ben aviat aquesta etiqueta, [paraula] és una etiqueta,
HTML, cap, cos, div, l'escriptura, l'àrea de text, l'amplada, centrada, div.
I això és també una espècie de misteriós aspecte a primera vista,
però tot aquest embolic segueix certs patrons i els patrons repetibles,
de manera que una vegada que tinguem els fonaments baix, vostè serà capaç d'escriure codi com aquest
i després manipular codi com aquest fent servir un altre llenguatge, anomenat JavaScript.
I JavaScript és un llenguatge que s'executa dins d'un navegador
avui que utilitzem en els cursos de la Universitat de Harvard, per descomptat, comprar l'eina que utilitza Google maps
per donar-li un munt de dinamisme, Facebook et dóna per mostrar actualitzacions instantànies d'estat,
Twitter s'utilitza per mostrar missatges de twitter instant.
Tot això, començarem a submergir polz
Però per arribar-hi, hem d'entendre una mica sobre l'Internet.
El vídeo aquí és només un minut de durada, i suposarem per ara això és, de fet,
com funciona Internet com un teaser del que està per venir. Et dono "Guerrers de la Xarxa".
>> [♫ ♫ música lenta cor]
[Narrador] Ell va venir amb un missatge.
Amb un protocol de tots els seus.
[♫ ♫ música electrònica més ràpida]
Ell va venir a un món de tallafocs fresc, despreocupat routers,
i els perills molt pitjors que la mort.
És ràpid. És fort. Ell és TCP / IP, i té el seu domicili.
Els guerrers de la xarxa.
[Malan] La setmana que ve, llavors. La Internet. Programació web. Això és CS50.
[CS50.TV]