[Powered by Google Translate] [Week 6, Vervolg] [David J. Malan] [Harvard University] [Dit is CS50.] [CS50.TV] Dit is CS50 en dit het einde van week 6. Dus CS50x, een van de eerste cursussen van Harvard die betrokken zijn bij de EDX-initiatief inderdaad debuteerde afgelopen maandag. Als u graag om een ​​glimp van wat anderen te krijgen op het internet volgen nu samen met, kunt u naar x.cs50.net. Dat leidt u naar de juiste plaats op edx.org, dat was waar deze en andere cursussen van MIT en Berkeley nu leven. Je moet aanmelden voor een account, je zult merken dat het materiaal grotendeels hetzelfde is als je hebt gehad dit semester, zij het een paar weken uitgesteld, als we alles klaar. Maar wat studenten in CS50x ziet nu een interface vrij als deze. Dit is bijvoorbeeld Zamyla leidt de walkthrough voor probleem set 0. Bij het aanmelden bij edx.org, een CS50x student ziet het soort dingen je zou verwachten te zien in een cursus: de lezing voor maandag, lezing voor woensdag, diverse borrels, het probleem sets, de walkthroughs, PDF's. Bovendien, als je hier ziet, machinevertalingen van het Engels transcripten in het Chinees, Japans, Spaans, Italiaans, en een hele hoop andere talen die zeker zal zijn onvolmaakt als rollen we ze uit programmatisch gebruik van iets genaamd een API, of application programming interface, van Google die ons in staat stelt om te zetten Engels naar deze andere talen. Maar dankzij de prachtige geest van zo'n honderd-plus vrijwilligers, willekeurige mensen op het internet die zo vriendelijk aangeboden hebben om mee te doen in dit project, zullen we geleidelijk aan het verbeteren van de kwaliteit van deze vertalingen door het hebben van mensen te corrigeren van de fouten die onze computers hebben gemaakt. Dus het blijkt dat we hadden een paar studenten opdagen op maandag dan we in eerste instantie verwacht. In feite, nu CS50x heeft 100.000 mensen langs thuis na. Dus beseffen dat je allemaal deel uit van deze eerste klasse van het maken van deze cursus in de informatica onderwijs meer in het algemeen, meer in het algemeen, toegankelijk. En de realiteit is nu, met een aantal van deze massale online cursussen, ze allemaal beginnen met deze zeer grote aantallen, zoals we lijken hier hebben gedaan. Maar het doel, uiteindelijk, voor CS50x is echt om zo veel mensen naar de finish als mogelijk. Door het ontwerp wordt CS50x zal worden aangeboden vanaf afgelopen maandag helemaal door 15 april 2013, zodat de mensen die de school verplichtingen elders, werk, gezin, andere conflicten en dergelijke, een beetje meer flexibiliteit waarmee te duiken in deze cursus, die, volstaat het om te zeggen, is vrij ambitieus gedaan als alleen in de loop van slechts drie maanden binnen een gebruikelijke semester. Maar deze studenten wordt de aanpak van hetzelfde probleem sets, het bekijken van dezelfde inhoud, toegang tot dezelfde shorts en dergelijke. Dus beseffen dat we allemaal echt in hetzelfde schuitje. En een van de einddoelen van CS50x is niet alleen om zo veel mensen naar de finish en geef ze dit pas ontdekte kennis van de informatica en de programmering, maar ook om ze te laten hebben dit gedeelde ervaring. Een van de definiërende kenmerken van 50 op de campus, hopen wij, is dit soort gemeenschappelijke ervaring, ten goede of ten kwade, soms, maar met deze mensen te schakelen naar links en naar rechts, en spreekuren en de Hackathon en de beurs. Het is een beetje moeilijker om dat te doen in persoon met mensen online, maar CS50x wordt afgesloten in april met de allereerste CS50 Expo, die zal een online aanpassing van ons idee van de beurs worden waar deze duizenden studenten zullen allemaal worden uitgenodigd om een ​​1 in te dienen - tot 2-minuten durende video, ofwel een screencast van hun laatste project of video van hen zwaaien gedag en praten over hun project en demonstreren van het, net als uw voorgangers hier hebben gedaan op de campus in de reële, zodat tegen het einde semester, de hoop is om een ​​globale tentoonstelling van de CS50x studenten afstudeeropdrachten, net als dat wat wacht u in december hier op de campus. Dus meer op dat in de komende maanden. Met 100.000 studenten echter is een behoefte aan een paar CA. Gezien het feit dat jullie zijn het pad hier laaiend en het nemen van CS50 enkele weken van tevoren release van dit materiaal aan de mensen op EDX, realiseren dat we graag zo veel van onze eigen studenten mogelijk te betrekken bij dit initiatief, zowel tijdens het semester als deze winter en komend voorjaar. Dus als je wilt om mee te doen in CS50x, vooral meedoen op CS50x Discuss, de EDX versie van CS50 te bespreken, die velen van jullie zijn met behulp van op de campus, de online bulletin board, doe hoofd naar die URL, laat het ons weten wie je bent, omdat we graag het opbouwen van een team van studenten en medewerkers en docenten zowel op de campus die gewoon mee te spelen en de helpende hand. En als ze zien een vraag die vertrouwd is voor hen, hoor je een student rapportage enkele bug ergens daar in sommige landen op het internet, en dat een belletje rinkelen, want je had ook hetzelfde probleem in uw d-hal enige tijd geleden, hopelijk dan kunt u klokkenspel in en deel uw eigen ervaring. Dus gelieve deelnemen als je zou willen. Wetenschap van de computer cursussen op Harvard hebben een beetje een traditie, CS50 onder hen, van het hebben van een aantal kleding, wat kleren, die je kunt trots dragen aan het einde semester, zeggende heel trots dat je klaar bent met CS50 en nam CS50 en dergelijke, en we altijd proberen om studenten te betrekken in dit proces zoveel mogelijk waarbij verzoeken wij, rond deze tijd van het semester, studenten dienen ontwerpen met behulp van Photoshop, of wat dan ook instrument van keuze die je wilt gebruiken als je een ontwerper, te ontwerpen voor T-shirts en sweatshirts te dienen en parasols en weinig Bandanas voor honden die we nu hebben en dergelijke. En alles is dan - de winnaars elk jaar worden dan tentoongesteld op de cursus op de website van store.cs50.net. Alles wordt verkocht tegen kostprijs daar, maar de website loopt gewoon zelf en stelt mensen in staat de keuze van de kleuren en ontwerpen die ze willen. Dus ik dacht dat we slechts enkele van de ontwerpen van vorig jaar te delen die op de website naast dit ene hier, dat is een jaarlijkse traditie. "Every Day Ik Seg Faultn" was een van de inzendingen van vorig jaar, dat is nog steeds beschikbaar zijn voor alumni. We hadden deze, "CS50, opgericht 1989." Een van onze Bowdens, Rob, was erg populair vorig jaar. "Team Bowden" was geboren, werd dit ontwerp ingediend, behoren tot de top verkopers. Zoals deze hier. Veel mensen hadden "Bowden Fever" volgens de verkoop-logs. Realiseer je dat dat nu kan er uw ontwerp, op het internet. Meer informatie hierover in het volgende probleem stelt komen. Nog een hulpmiddel: je hebt gehad wat blootstelling en hopelijk nu wat hands-on ervaring met GDB, dat is, natuurlijk, een debugger en stelt u in staat te manipuleren uw programma op een vrij laag niveau, het doen van wat voor soort dingen? Wat doet GDB laten doen? Ja? Geef me iets. [Student antwoord, onverstaanbaar] Goed. Stap in functie, dus je hoeft niet alleen maar te rennen typen en hebben het programma blaas door zijn geheel af te drukken dingen naar standaarduitvoer. In plaats daarvan kunt u door het regel voor regel, te typen volgende om line te gaan voor regel voor regel of stap te duiken in een functie, meestal een die je hebt geschreven. Wat doet GDB laten doen? Ja? [Student antwoord, onverstaanbaar] Print variabelen. Dus als je wilt een beetje introspectie doen binnenkant van uw programma zonder hun toevlucht nemen tot het schrijven van printf verklaringen all over the place, je kunt gewoon een variabel of geven een variabele. Wat kunt u doen met een debugger als GDB? [Student antwoord, onverstaanbaar] Precies. U kunt breekpunten, je kunt break uitvoering zeggen op de belangrijkste functie of de foo-functie. Je kunt zeggen break uitvoering op lijn 123. En breekpunten zijn echt een krachtige techniek want als je een algemeen gevoel van waar uw probleem waarschijnlijk is, hoeft u geen tijd te verspillen doorlopen geheel van het programma. U kunt in wezen springen daar en dan beginnen met typen - het doorlopen van het met stap of naast of iets dergelijks. Maar de vangst met zoiets als GDB is dat het je helpt, het menselijke, vind uw problemen en vind uw bugs. Het hoeft niet per se vinden ze zo veel voor je. Dus introduceerden we de andere dag style50, dat is een korte command-line tool die probeert om je code te stileren een beetje schoner dan u, de mens, zou kunnen hebben gedaan. Maar dat is ook eigenlijk gewoon een esthetische ding. Maar het blijkt dat er die andere tool genaamd Valgrind dat is een beetje meer geheimzinnige te gebruiken. De output is gruwelijk cryptisch op het eerste gezicht. Maar het is heerlijk handig, zeker nu we aan de kant van de term waar je begint te malloc en dynamische geheugentoewijzing te gebruiken. Dingen kunnen snel gaan echt heel erg verkeerd. Want als je vergeet om je geheugen vrij te maken, of je dereference enkele NULL pointer, of je wat afval pointerdereferentie, wat is meestal het symptoom dat de resultaten? Seg fout. En u krijgt deze kern-bestand van een bepaald aantal kilobytes of megabytes dat geeft de stand van het geheugen van uw programma toen het neerstortte, maar het programma uiteindelijk seg fouten, segmentatie fout, wat betekent dat er iets ergs gebeurd is bijna altijd gerelateerd naar een geheugenkaart-gerelateerde fout die je ergens gemaakt. Dus Valgrind helpt u dit soort dingen. Het is een tool die je, net als GDB, nadat je hebt gecompileerd uw programma, maar in plaats van direct uit te voeren het programma, loopt u Valgrind en u door te geven aan het uw programma, net zoals u dat doet met GDB. Nu, het gebruik, de beste vorm van uitvoer te krijgen, is een beetje lang, dus daar boven in het scherm zie je Valgrind-v. "-V" bijna universeel betekent verbose wanneer u gebruik maakt van programma's op een Linux-computer. Het betekent dus spugen meer gegevens dan je misschien standaard. "- Lek-check = vol." Dit wordt alleen maar zeggen check voor alle mogelijke geheugenlekken, fouten die ik zou hebben gemaakt. Ook dit is een veel voorkomende paradigma met Linux-programma's. Over het algemeen, als je een command line argument is dat een "switch", die verondersteld om het programma het gedrag te veranderen, en het is een enkele letter, het is-v, maar als dat is ingeschakeld, maar door het ontwerp van de programmeur, is een volledige woord of reeks woorden, de command line argument begint met -. Dit zijn slechts menselijke conventies, maar je zult steeds meer zien. En tenslotte "a.out" is de willekeurige naam van het programma in dit voorbeeld. En hier is een aantal representatieve output. Voordat we kijken naar wat dat zou kunnen betekenen, laat me over te gaan naar een fragment van de code hier. En laat mij dit uit te gaan van de weg, binnenkort, en laten we een kijkje nemen op memory.c, dat is deze korte voorbeeld. Dus in dit programma, laat me in te zoomen op de functies en vragen. We hebben de functie de belangrijkste die een functie aanroept, f, en wat is dan f overgaan tot, doen in een enigszins technisch Engels? Wat doet f gaan doen? Hoe zit het Ik zal beginnen met lijn 20, en de ster de locatie doet er niet toe, maar ik zal gewoon hier in overeenstemming zijn met de laatste lezing. Wat is lijn 20 voor ons doen? Aan de linkerkant. We breken het naar beneden verder. Int * x: wat betekent dat? Okay. Het is waarbij een pointer, en laten we nu nog meer technisch. Wat betekent het, heel concreet, met een pointer verklaren? Iemand anders? Ja? [Student antwoord, onverstaanbaar] Te ver. Dus je leest het rechterkant van het gelijkteken. Laten we focussen alleen op de linkerkant, net op int * x. Dit betekent "verklaren" een pointer, maar nu laten we duiken in dieper met die definitie. Wat betekent dat concreet, technisch bedoel je? Ja? [Student antwoord, onverstaanbaar] Okay. Het is klaar om een ​​adres op te slaan in het geheugen. Goed. En laten we verder nog een stap, het is declaratie van een variabele, x, dat is 32 bits. En ik weet dat het 32 ​​bits omdat -? Het is niet omdat het een int, want het is een pointer in dit geval. Toeval dat het een en het zelfde met een int, maar het feit dat er de ster er betekent dat het een pointer en in het apparaat, zoals bij veel computers, maar niet alle pointers zijn 32 bits. Op meer moderne hardware zoals de nieuwste Macs, de nieuwste pc's, misschien heb je 64-bits pointers, maar in het apparaat, deze dingen zijn 32 bits. Dus we zullen standaardiseren op dat. Meer concreet, het verhaal gaat als volgt: Wij "verklaren" een pointer, wat betekent dat? We bereiden om een ​​geheugenadres op te slaan. Wat betekent dat? Wij creëren een variabele genaamd x dat neemt 32 bits dat binnenkort slaat het adres van een integer. En dat is waarschijnlijk ongeveer net zo nauwkeurig als we kunnen krijgen. Het is fijn vooruit om de wereld te vereenvoudigen en gewoon zeggen dat verklaart een pointer genaamd x. Declareer een pointer, maar beseffen en begrijpen wat er eigenlijk aan de hand zelfs in slechts die paar tekens. Nu, dit is bijna een beetje makkelijker, ook al is het een langere uitdrukking. Dus wat dit doet, dat is nu gemarkeerd: "malloc (10 * sizeof (int));" Ja? [Student antwoord, onverstaanbaar] Goed. En ik zal daar nemen. Het is de toewijzing van een deel van het geheugen voor tien integers. En laten we nu duiken in iets dieper, het is de toewijzing van een deel van het geheugen voor tien integers. Wat is malloc vervolgens terug te keren? Het adres van dat stuk, of, meer concreet, het adres van de eerste byte van dat stuk. Hoe dan ben ik, de programmeur, om te weten waar dat stuk van het geheugen eindigt? Ik weet dat het aaneengesloten is. Malloc, per definitie, krijgt u een aaneengesloten stuk van het geheugen. Geen gaten in. U heeft toegang tot elke byte in dat stuk, rug aan rug aan rug, maar hoe weet ik waar het einde van dit stuk van het geheugen is? Wanneer u malloc? [Student antwoord, onverstaanbaar] Goed. Dat doe je niet. Je moet niet vergeten. Ik moet niet vergeten dat ik de waarde 10 gebruikt, en ik weet niet eens lijken dat hier hebben gedaan. Maar de verantwoordelijkheid ligt volledig op mij. Strlen, die we hebben enigszins afhankelijk voor strijkers, werkt alleen als gevolg van deze conventie van het hebben van \ 0 of deze speciale nul karakter NUL aan het einde van de string. Dat geldt niet voor slechts willekeurige stukken van het geheugen. Het is aan jou. Dus lijn 20, dan wijst een stuk van het geheugen dat kan tien integers, en slaat het adres van de eerste byte van dat deel van het geheugen in de variabele met de naam x. Ergo, die een pointer. Dus lijn 21, helaas, was een vergissing. Maar eerst, wat is het nou? Het zegt winkel op locatie 10, geïndexeerd 0, van het stuk van het geheugen genoemd x de waarde 0. Dus merken een paar dingen gaande zijn. Hoewel x is een pointer, herinneren van een paar weken geleden dat u kunt nog steeds gebruik maken van de array-stijl vierkante haken notatie. Want dat is eigenlijk de korte kant notatie voor de meer cryptische ogende pointers. waar we zouden zoiets als dit doen: Neem het adres x, u 10 plekken over, dan is er naar welke adres opgeslagen op die locatie. Maar eerlijk gezegd, dit is gewoon afschuwelijk om te lezen en comfortabel met te krijgen. Dus de wereld maakt meestal gebruik van de vierkante haken, alleen maar omdat het zo veel meer mensvriendelijke om te lezen. Maar dat is wat er werkelijk aan de hand onder de motorkap; x is een adres, geen array, per se. Dus dit is het opslaan van 0 op locatie 10 in x. Waarom is dit slecht? Ja? [Student antwoord, onverstaanbaar] Precies. We hebben alleen toegewezen tien ints, maar we rekenen van 0 bij het programmeren in C, zodat je toegang hebt tot 0 1 2 3 4 5 6 7 8 9, maar niet 10. Dus of het programma gaat seg fout of is het niet. Maar we weten niet echt, dit is een soort van een niet-deterministische gedrag. Het hangt af van het feit of we geluk. Als blijkt dat het besturingssysteem vindt het niet erg als ik die extra byte, ook al is niet gegeven aan mij, kan mijn programma niet crashen. Het is rauw, het is buggy, maar je zou niet zien dat symptoom, of je zou kunnen zien het maar een keer in de zoveel tijd. Maar de realiteit is dat de bug is, in feite is er,. En het is echt problematisch als je een programma geschreven dat u wilt juist, dat u hebt verkocht het programma dat mensen gebruiken die elke keer in een tijdje crasht omdat, natuurlijk, dit is niet goed. In feite, als je een Android telefoon of een iPhone en je apps downloaden deze dagen, als je ooit een app gewoon stoppen, alle van een plotselinge het verdwijnt, dat is bijna altijd het gevolg van een aantal geheugen-gerelateerde kwestie, waarbij de programmeur screwed up en dereferentie een pointer dat hij of zij niet moeten doen, en het resultaat van iOS of Android is om gewoon helemaal te doden het programma in plaats van het risico onbepaald gedrag of een soort van beveiliging compromis. Er is een andere bug in dit programma naast deze. Wat heb ik verpest in dit programma? Ik heb niet geoefend wat ik heb gepredikt. Ja? [Student antwoord, onverstaanbaar] Goed. Ik heb niet bevrijd van het geheugen. Dus de vuistregel nu moet elke keer als u belt malloc, moet u gratis bellen wanneer u klaar bent met behulp van dat geheugen. Nu, zou wanneer ik wil dit geheugen vrij te maken? Waarschijnlijk, ervan uitgaande dat deze eerste regel juist was, zou ik hier willen doen. Omdat ik niet kon, bijvoorbeeld, doe het hier beneden. Waarom? Net buiten het toepassingsgebied. Dus ook al hebben we het over pointers, dit is een week 2 of 3 probleem, waarbij x is alleen in omvang binnenkant van de accolades waar het werd verklaard. Dus je kan zeker niet daar bevrijden. Mijn enige kans om het te bevrijden is ongeveer na regel 21. Dit is een vrij eenvoudig programma, het was vrij eenvoudig als je eenmaal soort gewikkeld je geest rond wat het programma doet, waar de fouten waren. En zelfs als je niet zag op het eerste, hopelijk is het een beetje voor de hand nu dat deze fouten zijn vrij eenvoudig op te lossen en snel gemaakt. Maar wanneer een programma is meer dan 12 lijnen lang, het is 50 regels lang, 100 regels lang, wandelen door de code regel voor regel, denken door het logisch, is mogelijk, maar niet bijzonder leuk om te doen, voortdurend op zoek naar bugs, en het is ook moeilijk te doen, en dat is waarom een ​​tool als Valgrind bestaat. Laat me ga je gang en doe je dit: laat me open mijn terminal venster, en laat mij niet alleen het geheugen draaien, omdat het geheugen lijkt in orde. Ik krijg gelukkig. Ga dat extra byte aan het einde van de array lijkt niet te problematisch. Maar laat mij, toch, doe een sanity check, wat gewoon betekent controleren of dit daadwerkelijk correct. Dus laten we het doen valgrind-v - lek-check = vol, en vervolgens de naam van het programma is in dit geval het geheugen, niet a.out. Dus laat me ga je gang en doen. Druk op Enter. Dear God. Dit is de output, en dit is wat ik zinspeelde eerder. Maar, als je leert om hier te lezen door alle onzin, de meeste van deze is gewoon diagnostische uitvoer dat is niet zo interessant. Wat uw oog echt wil op zoek naar is enige vermelding van fout of ongeldig. Woorden die problemen stellen. En inderdaad, laten we eens kijken wat er fout gaat hier beneden. Ik heb een samenvatting van een soort, "in gebruik bij afrit:. 40 bytes in 1 blokken" Ik ben niet echt zeker wat een blok is nog niet, maar 40 bytes eigenlijk voelt het alsof ik kon achterhalen waar dat vandaan komt. 40 bytes. Waarom zijn 40 bytes in gebruik bij afslag? En meer in het bijzonder, als we naar beneden scrollen hier, waarom heb ik zeker verloren 40 bytes? Ja? [Student antwoord, onverstaanbaar] Perfect. Ja, precies. Er waren tien gehele getallen, en elk daarvan is grootte van 4 of 32 bits, dus ik heb verloren precies 40 bytes, omdat, zoals u voorgesteld, heb ik niet de zogenaamde vrije. Dat is een bug, en nu laten we eens kijken naar beneden verder een beetje en zien naast dit, "Ongeldige schrijven van grootte 4." Nu wat is dit? Dit adres wordt uitgedrukt wat basis notatie, blijkbaar? Dit is hexadecimaal, en elke keer zie je een nummer beginnend met 0x, het betekent hexadecimaal, die we al in, denk ik, sectie PSET 0's van vragen deed, en dat was alleen maar om een ​​warming-up oefening te doen, het omzetten van decimaal naar hex naar binair, enzovoort. Hexadecimaal, gewoon door menselijke conventie, wordt meestal gebruikt om pointers te vertegenwoordigen of, meer algemeen, richt. Het is gewoon een conventie, want het is een beetje makkelijker te lezen is, is het een beetje compacter dan iets als decimaal, en binaire is nutteloos voor de meeste mensen om te gebruiken. Dus nu wat betekent dit? Nou, het lijkt erop dat er een ongeldige schrijf van maat 4 op lijn 21 van memory.c. Dus laten we terug gaan naar lijn 21, en inderdaad, hier is dat ongeldig schrijven. Dus Valgrind is niet van plan om volledig m'n hand vasthouden en me vertellen wat de oplossing is, maar het is het opsporen van dat ik een ongeldige schrijven doen. Ik raak 4 bytes dat ik niet zou moeten zijn, en blijkbaar dat komt omdat, zoals u zegt, ik doe [10] in plaats van [9] maximaal of [0] of iets daar tussenin. Met Valgrind, realiseert elke keer dat je nu het schrijven van een programma dat pointers gebruikt en maakt gebruik van het geheugen, en malloc meer in het bijzonder, zeker krijgen in de gewoonte van het runnen van deze lange maar heel gemakkelijk gekopieerd en geplakt beheersing van Valgrind om te zien of er wat fouten in. En het zal overweldigend zijn elke keer zie je de output, maar gewoon ontleden door middel van visueel alle output en kijk of je ziet vermeldingen van fouten of waarschuwingen of ongeldige of verloren. Ieder woord dat klinkt alsof je genaaid ergens. Dus beseffen dat is een nieuwe tool in uw toolkit. Nu op maandag hadden we een hele hoop mensen komen hier en vertegenwoordigen de notie van een gekoppelde lijst. En introduceerden we de gekoppelde lijst als een oplossing voor welk probleem? Ja? [Student antwoord, onverstaanbaar] Goed. Arrays kan niet geheugen toegevoegd. Als u toewijzen een array van maat 10, dat is alles wat je krijgt. U kunt bellen naar een functie als realloc als je in eerste instantie genaamd malloc, en dat kan proberen de array groeien als er ruimte naar het einde van het dat niemand anders gebruikt, en als er niet, zal het gewoon vinden een groter stuk ergens anders. Maar dan zal het kopiëren al die bytes in de nieuwe array. Dit klinkt als een heel correcte oplossing. Waarom is dit niet aantrekkelijk? Ik bedoel het werkt, hebben mensen dit probleem opgelost. Waarom hebben we nodig om het op te lossen op maandag met gelinkte lijsten? Ja? [Student antwoord, onverstaanbaar] Het kan lang duren. In feite, elke keer dat je belt malloc of realloc of calloc, die nog is een andere, elke keer dat je het programma, zijn in gesprek met het besturingssysteem, je de neiging om het programma te vertragen. En als je aan het doen bent dit soort dingen in lussen, je bent echt vertragen dingen naar beneden. Je gaat niet naar deze merken voor de eenvoudigste van "hello world" type programma's, maar in veel grotere programma's, met de vraag het besturingssysteem opnieuw en opnieuw voor het geheugen of het geven van het terug opnieuw en opnieuw heeft de neiging om niet een goede zaak. Plus, het is gewoon soort van intellectueel - het is een complete verspilling van tijd. Waarom wijzen meer en meer geheugen, risico kopiëren alles in de nieuwe array, Als u een alternatief waarmee u toewijzen slechts zoveel geheugen als je eigenlijk nodig hebben? Dus er is plussen en minnen hier. Een van de pluspunten is nu dat we dynamiek hebben. Maakt niet uit waar de delen van het geheugen is dat vrij zijn, Ik kan gewoon soort van het maken van deze broodkruimels via pointers om mijn hele gelinkte lijst aaneenrijgen. Maar ik betaal ten minste een prijs. Wat moet ik opgeven bij het verkrijgen van gelinkte lijsten? Ja? [Student antwoord, onverstaanbaar] Goed. Je hebt meer geheugen. Nu moet ik ruimte voor deze pointers, en in het geval van deze super eenvoudige verbonden lijst dat alleen probeert te integers, die 4 bytes op te slaan, we blijven zeggen nou ja, een pointer is 4 bytes, dus nu heb ik letterlijk verdubbeld de hoeveelheid geheugen die ik nodig heb alleen maar om deze lijst op te slaan. Maar nogmaals, dit is een constante afweging in de informatica tussen tijd en ruimte en de ontwikkeling, inzet en andere middelen. Wat is een ander nadeel van het gebruik van een gekoppelde lijst? Ja? [Student antwoord, onverstaanbaar] Goed. Niet zo gemakkelijk te bereiken. We kunnen niet langer leverage week 0 principes als verdeel en heers. En meer specifiek, binaire zoekopdracht. Want ook al hebben we mensen kunnen grofweg zien waar het midden van deze lijst is, de computer weet alleen dat deze gekoppeld lijst begint op het adres genoemd eerste. En dat is 0x123 of zoiets. En de enige manier waarop het programma vindt de middelste element is om daadwerkelijk de hele lijst. En zelfs dan, het heeft letterlijk de hele lijst, omdat zelfs als je eenmaal het middelste element door het volgen van de aanwijzingen, u het programma, hebben geen idee hoe lang deze lijst is, potentieel, tot je het einde van het, en hoe weet je dat programmatisch dat je aan het eind van een gekoppelde lijst? Er is een speciale NULL pointer, dus nogmaals, een conventie. In plaats van gebruik van deze wijzer, we zeker niet willen dat het wat vuilnis waarde pointing podium ergens, we willen dat het met de hand naar beneden, NULL, zodat we dit eindpunt in deze datastructuur zodat we weten waar het eindigt. Wat als we willen dit te manipuleren? We hebben het grootste deel van deze visueel, en met mensen, maar wat als we willen een insertie doen? Zodat de oorspronkelijke lijst was 9, 17, 20, 22, 29, 34. Wat als we dan wilden malloc ruimte voor nummer 55, een knooppunt voor het, en dan willen we tot 55 in te voegen in de lijst net als wij op maandag? Hoe gaan we dit doen? Nou, Anita kwam en ze in wezen liep de lijst. Ze begon bij het eerste element, dan de volgende, de volgende, de volgende, de volgende, de volgende. Tenslotte raakte de linker helemaal naar beneden en gerealiseerd oh, dit is NULL. Dus wat wijzer manipulatie gedaan moest worden? De persoon die was op het einde, nummer 34, die nodig zijn linkerhand omhoog te wijzen op 55, 55 nodig hun linkerarm naar beneden te zijn de nieuwe NULL terminator. Gereed. Vrij gemakkelijk tot 55 in te voegen in een gesorteerde lijst. En hoe zou dit eruit? Laat me gaan en open te stellen wat code voorbeeld. Ik zal open gedit, en laat me open te stellen eerste twee bestanden. Een daarvan is list1.h, en laat me even aan herinneren dat dit het stuk code die we gebruikten een knooppunt vertegenwoordigen. Een knooppunt heeft zowel een int genoemd n en een pointer genaamd volgende die net wijst naar het volgende ding in de lijst. Dat is nu in een. H bestand. Waarom? Er is dit verdrag, en we hebben geen gebruik gemaakt van deze een enorme hoeveelheid onszelf, maar de persoon die schreef printf en andere functies gaf als een geschenk aan de wereld al die functies door het schrijven van een bestand genaamd stdio.h. En dan is er nog string.h, en dan is er map.h, en er is al die h bestanden die u zou kunnen hebben gezien of gebruikt gedurende de looptijd geschreven door andere mensen. Typisch in die. H bestanden zijn alleen dingen als typedefs of verklaringen van typen op maat of verklaringen van constanten. Je hoeft niet gezet functies 'implementaties in header-bestanden. Je zet in plaats daarvan alleen hun prototypes. U dingen die je wilt delen met de wereld zetten wat ze nodig hebben om hun compileren. Dus gewoon om in deze gewoonte, hebben we besloten om hetzelfde te doen. Er is niet veel in list1.h, maar we hebben gezet iets dat misschien van belang zijn voor mensen in de wereld die willen ons gelinkte lijst implementatie gebruiken. Nu, in list1.c, ik zal niet gaan door dit hele gebeuren want het is een beetje lang, dit programma, maar laten we snel leeg dat het echt achter de prompt. Laat me compileren list1, laat me dan list1 rennen, en wat je ziet is hebben we gesimuleerd een eenvoudig klein programma hier dat gaat staat u mij toe te voegen en te verwijderen nummers om een ​​lijst. Dus laat me gaan en typ 3 voor de menu-optie 3. Ik wil het aantal plaatsen - laten we het eerste nummer, dat is 9, en nu ik heb gehoord dat de lijst is nu 9. Laat me ga je gang en doe een ander inbrengen, dus ik sloeg menu-optie 3. Welk nummer moet ik wilt invoegen? 17. Enter. En ik doe nog een. Laat me steek de nummer 22. Dus hebben we het begin van de gekoppelde lijst die wij hadden in een diavoorstelling vorm een ​​ogenblik geleden. Hoe wordt deze toevoeging daadwerkelijk gebeurt? Inderdaad, 22 is nu aan het einde van de lijst. Dus het verhaal vertelden we op het podium op maandag en vatte juist nu moet daadwerkelijk gebeuren in de code. Laten we eens een kijkje nemen. Laat me naar beneden scrollen in dit bestand. We verdoezelen enkele van de functies, maar we zullen naar beneden gaan naar, laten we zeggen, de insert-functie. Laten we eens kijken hoe we gaan over het invoegen van een nieuw knooppunt in deze gelinkte lijst. Waar is de lijst verklaard? Nou, laten we gaat u helemaal op de top, en merk dat mijn gelinkte lijst in wezen wordt verklaard als een enkele pointer dat is in eerste instantie NULL. Dus ik ben met behulp van een globale variabele hier, die over het algemeen hebben we gepredikt tegen want het maakt je code een beetje rommelig te onderhouden, het is een soort van lui, meestal, maar het is niet lui en het is niet verkeerd en het is niet slecht Als je programma's enige doel in het leven is om te simuleren een gelinkte lijst. En dat is precies wat we doen. Dus in plaats van te verklaren dat in hoofd-en vervolgens door te geven aan elke functie we hebben geschreven in dit programma, hebben we in plaats daarvan realiseren oh, laten we gewoon maken het globale omdat het hele doel van dit programma is om aan te tonen een en slechts een gelinkte lijst. Dus dat voelt goed. Hier zijn mijn prototypes, en we zullen niet gaan door al deze, maar ik schreef een delete functie, een zoekfunctie, een insert-functie, en een traverse functie. Maar laten we nu terug naar beneden naar de insert-functie en zie hoe deze hier werkt. Insert is on line - hier gaan we. Invoegen. Dus het neemt geen argumenten, want we gaan om te vragen de gebruiker binnenkant van deze functie voor het nummer dat ze wilt invoegen. Maar eerst bereiden we om hen wat ruimte. Dit is een soort van kopiëren en plakken van de andere voorbeeld. In dat geval waren we de toerekening van een int, dit keer zijn we het toewijzen van een knooppunt. Ik heb niet echt herinneren hoeveel bytes een knooppunt is, maar dat is prima. Sizeof kan cijfer dat uit voor mij. En waarom krijg ik het controleren op NULL in lijn 120? Wat kan er mis gaan in de lijn 119? Ja? [Student antwoord, onverstaanbaar] Goed. Kon gewoon het geval dat ik heb gevraagd om te veel geheugen te of er iets mis is en het besturingssysteem niet genoeg bytes aan mij geven, dus het signaleert zo veel door terug te keren NULL, en als ik niet controleren of dat en ik blindelings te gaan gebruiken het adres terug, het kan NULL. Het zou een onbekende waarde, niet een goede zaak, tenzij ik - daadwerkelijk niet een onbekende waarde. Het zou kunnen zijn NULL, dus ik wil niet te misbruiken en risico dereferentie het. Als dat gebeurt, ik heb net terug en we zullen doen alsof ik niet terug enkele herinnering op alle. Anders, ik vertel de gebruiker geef me een nummer in te voegen, roep ik onze oude vriend GetInt, en dan was dit de nieuwe syntaxis introduceerden we op maandag. 'Newptr-> n' betekent neem het adres dat u werden gegeven door malloc overeenkomende met de eerste byte van een nieuw knooppunt object, en ga dan naar het veld met de naam n. Een beetje trivia vraag: Dit komt overeen met wat meer cryptische regel code? Hoe kon ik anders hebben geschreven dit? Wilt u een steek te nemen? [Student antwoord, onverstaanbaar] Goed. Met behulp van de. N, maar het is niet zo simpel als dit. Wat moet ik eerst doen? [Student antwoord, onverstaanbaar] Goed. Ik moet * newptr.n doen. Dus dit zegt nieuwe pointer is duidelijk een adres. Waarom? Omdat het werd teruggestuurd door malloc. De * newptr zeggen "er naartoe te gaan," en dan als je eenmaal daar bent, dan kunt u gebruik maken van de meer bekende. n, maar dit ziet er gewoon een beetje lelijk, vooral als wij mensen gaan trekken pointers met pijlen de hele tijd, de wereld is gestandaardiseerd op deze pijl notatie, die doet precies hetzelfde. Zodat u alleen gebruik maken van de -> notatie als het ding aan de linkerkant is een pointer. Anders, als het een echte struct, gebruik maken van de. N. En dan dit: Waarom moet ik initialiseren newptr-> naast NULL? We willen niet dat een loshangende linkerhand af van het einde van het podium. We willen het recht naar beneden, wat betekent dat het einde van deze lijst zou kunnen zijn op dit knooppunt, zodat we beter voor zorgen dat het NULL is. En, in het algemeen, het initialiseren van uw variabelen of uw gegevens leden en structs iets is gewoon goede praktijk. Gewoon laten vuilnis bestaan ​​en blijven over het algemeen bestaan ​​krijgt u in de problemen als je vergeet om iets te doen later. Hier zijn een paar gevallen. Ook dit is het inzetstuk functie en het eerste wat ik controleren is als de variabele genaamd eerste, dat globale variabele NULL is, dat betekent dat er geen gelinkte lijst. We hebben niet alle nummers geplaatst, dus het is triviaal te voegen dit huidige nummer in de lijst, aangezien zij tot net aan het begin van de lijst. Dus dit was toen Anita was gewoon staan ​​hier alleen, alsof niemand anders was hier op het podium tot we toegewezen een knooppunt, dan kon ze omhoog haar hand voor de eerste keer, als iedereen was gekomen op het podium na haar op maandag. Nu hier, dit is een beetje cheque waar ik moet zeggen dat als het nieuwe knooppunt de waarde van n is volgende, dat betekent naar de struct dat wordt gewezen door newptr, hier dus we zijn, er heen gaan. Vervolgens op de pijl zegt krijg het volgende veld, en vervolgens de = zegt gezet welke waarde er? De waarde die was in de eerste plaats; welke waarde was in de eerste? Eerste wees naar dit knooppunt, dus dat betekent dat dit moet nu wijzen op dit knooppunt. Met andere woorden, wat lijkt zij het een belachelijk Mess With My handschrift, wat is een eenvoudig idee van slechts het verplaatsen van deze pijlen rond vertaalt zich naar code met alleen deze one-liner. Bewaar wat er in eerste in het volgende veld en werk vervolgens wat eerst eigenlijk is. Laten we vooruit en vooruit gaan door een aantal van deze, en alleen kijken naar deze staart inbrengen voor nu. Stel dat ik bij het punt waar ik vind dat het volgende veld van een node NULL is. En op dit punt in het verhaal, een detail dat ik voorbij te gaan is dat ik een andere wijzer hier geïntroduceerde in lijn 142, voorganger wijzer. Wezen op dit punt in het verhaal, als de lijst krijgt lange, Ik soort van nodig om het te lopen met twee vingers, want als ik te ver gaan, remember in een enkel-lengte lijst, kunt u niet achteruit gaan. Dus dit idee van predptr is mijn linker vinger en newptr - niet newptr. Een andere aanwijzing dat hier is is mijn andere vinger, en ik ben gewoon een soort van het lopen van de lijst. Dat is waarom die er bestaat. Maar laten we slechts een van de eenvoudiger gevallen hier te overwegen. Als dat aanwijzer volgende veld NULL is, wat is de logische implicatie? Als u doorkruisen deze lijst en je raakt een NULL pointer? Je bent aan het einde van de lijst, en dus de code om dan voeg je dit een extra element is een soort van de intuïtieve zal dat knooppunt waarvan de volgende pointer NULL is, dus dit is momenteel NULL, en verander het, hoewel, om het adres van de nieuwe node. Dus we gewoon tekenen in code op de pijl die we trokken op het podium door het verhogen van iemands linkerhand. En het geval dat ik mijn handen zwaaien voor nu, gewoon omdat ik denk dat het makkelijk is om te verdwalen als we het doen in dit soort omgeving, is het controleren op invoegen op midden van de lijst. Maar net intuïtief, wat er moet gebeuren als je wilt om erachter te komen waar sommige nummer behoort in het midden is je hoeft niet te te lopen met meer dan een vinger meerdere pointer, erachter te komen waar het hoort door controle is het element De huidige, en zodra je die plaats, dan moet je dit soort shell spel te doen wanneer u de aanwijzingen om zeer zorgvuldig. En dat antwoord, als je wilt om te redeneren graag via dit thuis op uw eigen, neer alleen maar om deze twee regels code, maar de volgorde van die lijnen is super belangrijk. Want als je er bij neervalt iemands hand te verhogen en die van iemand anders in de verkeerde volgorde, weer, kan je uiteindelijk orphaning de lijst. Samenvattend meer conceptueel, invoering op de staart is betrekkelijk eenvoudig. Invoering op het hoofd is relatief eenvoudig, maar je moet een extra pointer updaten tijd naar nummer 5 hier knijpen in de lijst, en dan inbrengen in het midden gaat nog meer inspanning, om het getal 20 zeer zorgvuldig in te voegen in de juiste locatie, die tussen 17 en 22. Dus je moet iets doen als de nieuwe node 20 punten tot 22, en dan, welk knooppunt de wijzer moet worden bijgewerkt mee? Het is 17, om daadwerkelijk invoegen. Dus nogmaals, ik uitstellen van de eigenlijke code voor die specifieke toepassing. Op het eerste gezicht is het een beetje overweldigend, maar het is eigenlijk gewoon een oneindige lus dat is looping, lus, looping, looping, en het breken van zodra je de NULL pointer, op welk punt je kunt doen de nodige inbrengen. Dit is dan ook representatief gelinkte lijst code voor het invoegen. Dat was een soort van een veel, en het voelt alsof we een opgelost probleem, maar we hebben geïntroduceerd een hele andere. Eerlijk gezegd, we hebben al die tijd op grote O en Ω en looptijd, in een poging om problemen op te lossen sneller, en hier nemen we een grote stap terug, het voelt. En toch, als het doel is om gegevens op te slaan, het voelt als de Heilige Graal, zoals we al zeiden op maandag, zou echt om direct op te slaan dingen. In feite, stel dat we opzij zetten gelinkte lijst voor een moment deed en we in plaats daarvan introduceerde de notie van een tafel. En gewoon denken aan een tafel te laten voor een moment als een array. Deze array en dit geval heeft hier ongeveer 26 elementen, 0 tot en met 25, en stel dat u een aantal brok van opslag die nodig is voor namen: Alice en Bob en Charlie en dergelijke. En je moet een aantal gegevens structuur als die namen op te slaan. Nou, kunt u gebruik maken iets als een gekoppelde lijst en je kon lopen in de lijst plaatsen van Alice voor Bob en Charlie na Bob enzovoort. En, in feite, als je wilt code als dat zien als een terzijde, weet dat in list2.h, we doen precies dat. We zullen niet door deze code, maar dit is een variant van het eerste voorbeeld dat introduceert een andere struct we eerder gezien hebben zogenaamde student, en dan wat het eigenlijk slaat in de gelinkte lijst is een pointer naar een student structuur in plaats van een klein geheel getal, n. Dus beseffen dat er daar-code die inhoudt dat het werkelijke strijkers, maar als het doel bij de hand nu echt is het aanpakken van de efficiëntie probleem, zou het niet mooi zijn als we krijgen een object met de naam Alice, We willen haar in het juiste locatie in een datastructuur, het voelt alsof het zou echt leuk zijn om zomaar Alice, waarvan de naam begint met A, in de eerste locatie. En Bob, wiens achternaam begint met B, in de tweede plaats. Met een array, of laten we beginnen noemde het een tafel, een hash-tabel op dat, kunnen we precies dat te doen. Als we een naam als Alice, een string als Alice, waar moet je zet A-l-i-c-e? We hebben een hueristic. We hebben een functie om wat input als Alice te nemen en terug te keren een antwoord: "Zet Alice op deze locatie." En deze functie, deze zwarte doos, zal worden genoemd een hash-functie. Een hash-functie is iets dat een input neemt, zoals "Alice", en keert terug naar je, meestal, de numerieke locatie in sommige datastructuur waar Alice behoort. In dit geval moet onze hashfunctie relatief eenvoudig. Onze hashfunctie zou zeggen, als je "Alice", welk karakter moet ik de zorg over gegeven? De eerste. Dus ik kijk naar [0], en dan zeg ik als [0] karakter is A, het getal 0 terug te keren. Als het B, terug 1. Als het C terug 2, enzovoort. Alle 0-index, en dat me zou toestaan ​​om Alice en daarna Bob en dan Charlie steek enzovoort in deze gegevensstructuur. Maar er is een probleem. Wat als Anita langs komt weer? Waar komen we Anita? Haar naam ook begint met de letter A, en het voelt alsof we hebben gemaakt een nog grotere puinhoop van dit probleem. We hebben nu direct inbrengen, constante tijd inbrengen, in een datastructuur in plaats van worst-case lineair, maar wat kunnen we doen met Anita in dit geval? Wat zijn de twee opties, echt? Ja? [Student antwoord, onverstaanbaar] Oke, dus we konden een andere dimensie hebben. Dat is goed. Dus we kunnen dingen bouwen in 3D als we het over gehad verbaal op maandag. We kunnen toevoegen een ander toegangspunt hier, maar stel dat er geen, ik probeer te houden het simpel. Het hele doel hier is om direct een constante-time toegang, dus dat is het toevoegen van te veel complexiteit. Wat zijn andere opties wanneer het proberen om Anita te voegen in deze gegevens structuur? Ja? [Student antwoord, onverstaanbaar] Goed. Dus we konden verhuizen iedereen naar beneden, als Charlie duwtjes naar beneden Bob en Alice, en dan zetten we Anita, waar ze echt wil zijn. Natuurlijk, nu is er een bijwerking van dit. Deze datastructuur is waarschijnlijk nuttig, niet omdat we mensen willen invoegen keer maar omdat we willen om te controleren of ze er later als we willen afdrukken alle namen in de datastructuur. We gaan iets uiteindelijk doen met deze gegevens. Dus nu hebben we soort van genaaid Alice, die nu niet meer waar ze hoort te zijn. Ook is Bob, noch is Charlie. Dus misschien is dit niet zo'n goed idee. Maar inderdaad, dit is een optie. We kunnen verschuiven iedereen neer, of ach, Anita laat kwam om het spel, waarom we niet zomaar Anita niet hier, niet hier, niet hier, laten we haar er een beetje lager in de lijst. Maar dan het probleem weer begint te decentraliseren. Je zou direct in staat zijn om Alice te vinden, op basis van haar voornaam. En Bob direct, en Charlie. Maar dan moet je op zoek naar Anita, en je ziet, hmm, Alice in de weg. Nou, laat me controleren hieronder Alice. Bob is niet Anita. Charlie is niet Anita. O, er is Anita. En als je blijft die trein van de logica helemaal, wat is het worst-case looptijd van het vinden of het inbrengen van Anita in deze nieuwe datastructuur? Het is O (n), toch? Omdat in het ergste geval, er is Alice, Bob, Charlie. . . helemaal naar beneden om iemand met de naam "Y", dus er is maar een plek over. Gelukkig, we hebben geen een zogenaamde "Z", dus we Anita helemaal onderaan. We hebben niet echt dat probleem opgelost. Dus misschien kunnen we hoeven deze derde dimensie te introduceren. En het blijkt, als we introduceren deze derde dimensie, we kunnen niet perfect doen, maar de Heilige Graal zal krijgen constant-time inbrengen en dynamische inserties zodat we hoeven niet te hard-code een array van grootte 26. We kunnen invoegen zoveel namen als we willen, maar laten we hier nemen onze 5-minuten pauze en doe dat goed. Oke. Ik het verhaal op vrij kunstmatig er door te kiezen voor Alice en daarna Bob en dan Charlie en dan Anita, wiens naam was duidelijk zou botsen met Alice. Maar de vraag die we op maandag afgesloten met is gewoon hoe waarschijnlijk is het die u zou krijgen dit soort botsingen? Met andere woorden, als we beginnen aan deze tabellen structuur te gebruiken, dat is eigenlijk gewoon een array, in dit geval van 26 locaties, wat als onze ingangen in plaats daarvan worden gelijkmatig verdeeld? Het is niet kunstmatig Alice en Bob en Charlie en David enzovoort alfabetisch, het is gelijkmatig verdeeld over A tot en met Z. Misschien hebben we gewoon geluk en we gaan niet naar twee A's of twee B's hebben met een zeer hoge waarschijnlijkheid, maar als iemand opgemerkt, Als we gegeneraliseerde dit probleem niet 0-25 maar, laten we zeggen, 0 tot en met 364 of 65, vaak het aantal dagen in een typisch jaar, en stelde de vraag: "Wat is de kans dat twee van ons in deze kamer op dezelfde dag jarig zijn?" Met andere woorden, wat is de kans dat twee van ons een naam beginnend met A hebben? Het soort vraag is hetzelfde, maar deze adresruimte, deze zoekruimte, is groter in het geval van verjaardagen, want we hebben zo veel meer dagen in het jaar dan letters in het alfabet. Wat is de kans op een botsing? Nou, we kunnen denken dat dit door het uitzoeken van de wiskunde de tegenovergestelde manier. Wat is de kans dat er geen botsingen? Nou, deze uitdrukking hier zegt dat wat is de kans als er maar een persoon in deze kamer, dat ze een unieke verjaardag hebben? Het is 100%. Want als er maar een persoon in de kamer, zijn of haar verjaardag kan elk van de 365 dagen worden uit van het jaar. Dus 365/365 opties geeft me een waarde van 1. Dus de kans in kwestie op dit moment is slechts 1. Maar als er een tweede persoon in de kamer, wat is de kans dat hun verjaardag anders is? Er is maar 364 mogelijk dagen, het negeren van schrikkeljaren, voor hun verjaardag niet te botsen met de andere personen. Dus 364/365. Indien een derde komt, is 363/365, enzovoort. Dus we blijven vermenigvuldigen samen deze fracties, die worden steeds kleiner en kleiner, om erachter te komen wat is de kans dat wij allemaal uniek verjaardagen hebben? Maar dan kunnen we natuurlijk gewoon dat antwoord en draai het rond en doe 1 minus dat allemaal, een uitdrukking zullen we uiteindelijk wel als je nog op de achterkant van je wiskunde boeken, het ziet er een beetje zoiets als dit, die veel gemakkelijker grafisch uitgelegd. En deze grafiek heeft hier de x-as het aantal verjaardagen of aantal mensen met verjaardagen en op de y-as is de kans op een match. En wat dit zegt is dat als je, laten we zeggen, zelfs,, laten we kiezen voor iets als 22, 23. Als er 22 of 23 mensen in de kamer, de kans dat twee van die heel weinig mensen gaan op dezelfde dag jarig zijn is eigenlijk super hoog, combinatorieel. 50% kans dat in een klas van slechts 22 mensen, een seminar, praktisch, 2 van die mensen gaan op dezelfde dag jarig zijn. Omdat er zoveel manieren waarop u kunt op dezelfde dag jarig zijn. Erger nog, als je kijkt naar de rechterkant van de grafiek, tegen de tijd dat je een klasse met 58 studenten in het, de waarschijnlijkheid van 2 mensen die een verjaardag is super, super hoog, bijna 100%. Nu, dat is een soort van een leuk weetje over het echte leven. Maar de gevolgen, nu, voor datastructuren en het opslaan van informatie betekent dat gewoon aangenomen dat je een mooie, schone, gelijkmatige verdeling van de gegevens en je hebt een groot genoeg array een heleboel dingen te passen betekent niet dat je gaat om mensen op unieke locaties. Je zult botsingen hebben. Dus dit idee van hashing, zoals dat heet, het nemen van een ingang als "Alice" en masseren op een bepaalde manier en dan om terug een antwoord als 0 of 1 of 2. Om terug de output van die functie wordt geteisterd door deze waarschijnlijkheid van een botsing. Dus hoe kunnen we omgaan met die botsingen? Nou, op het ene geval, kunnen we het idee dat werd gesuggereerd. We kunnen gewoon verschuiven iedereen neer, of misschien, een beetje eenvoudiger, en niet verder iedereen, laten we Anita naar de onderkant van de beschikbare plek. Dus als Alice is in 0, Bob is in 1, Charlie is in 2, we zomaar Anita op locatie 3. En dit is een techniek in data structuren, genaamd lineaire sonderen. Lineaire omdat je gewoon wandelen deze lijn, en je bent soort van indringende beschikbare plaatsen in de datastructuur. Dit natuurlijk delegeert in O (n). Als de datastructuur is echt vol, er is 25 mensen in het al, en dan Anita langs komt, belandt ze op wat zou zijn locatie Z, en dat is prima. Ze past nog steeds, en we kunnen later haar vinden. Maar dit was in strijd is met het doel van het versnellen dingen. Dus wat als we in plaats daarvan deze derde dimensie ingevoerd? Deze techniek wordt in het algemeen de aparte chaining, of met kettingen. En wat een hash-tabel is nu, deze vlakke structuur, uw tafel is slechts een array van pointers. Maar wat die pointers wijzen naar is wat denk je? Een gelinkte lijst. Dus wat als we het beste van beide werelden? We gebruiken arrays voor de eerste indexen in de datastructuur zodat we direct naar [0] [1], [30] enzovoort, maar zo dat we enige flexibiliteit en wij kunnen passen Anita en Alice en Adam en andere A naam we in plaats daarvan laat de andere as willekeurig groeien. En we eindelijk, vanaf maandag, hebben dat expressieve mogelijkheden met gekoppelde lijst. We kunnen groeien een datastructuur willekeurig. Als alternatief kunnen we gewoon een grote 2-dimensionale array, maar dat gaat een vreselijke situatie zijn als een van de rijen in een 2-dimensionale array niet groot genoeg voor de extra persoon wiens naam toevallig beginnen A. God verhoede we een groot 2-dimensionale structuur opnieuw toe te wijzen gewoon omdat er zo veel mensen met de naam A, vooral als er zo weinig mensen met de naam Z iets. Het is gewoon gaat om een ​​zeer schaars datastructuur zijn. Dus het is niet perfect op enige wijze, maar nu hebben we in ieder geval de mogelijkheid om direct te vinden waar Alice of Anita behoort, althans wat de verticale as, en dan hebben we alleen maar te beslissen waar te Anita of Alice zet in deze gelinkte lijst. Als we niet de zorg over het sorteren dingen, hoe snel we voegen Alice in een structuur als deze? Het is constante tijd. We index in [0], en als niemand daar, Alice gaat aan het begin van dat gekoppelde lijst. Maar dat is niet een groot probleem. Want als Anita komt dan langs sommige aantal stappen later, Anita waar komt thuis? Nou ja, [0]. Oop. Alice is al in die gelinkte lijst. Maar als we niet de zorg over het sorteren van deze namen, we kunnen gewoon bewegen Alice over, insert Anita, maar zelfs dat is constante tijd. Zelfs als er Alice en Adam en al die andere A namen, Het is niet echt verschuiven hen fysiek. Waarom? Omdat we net gedaan hier met gelinkte lijst, wie weet zijn deze knooppunten zijn eigenlijk? Het enige wat je hoeft te doen is te bewegen het broodkruim. Verplaats de pijlen rond, je hoeft niet fysiek te verplaatsen van gegevens. Zodat we voegen Anita, in dat geval direct. Constante tijd. Dus we hebben constant-time lookup, en constant-time opname van iemand als Anita. Maar soort te simpel de wereld. Wat als we later willen Alice te vinden? Wat als we later willen Alice te vinden? Hoeveel stappen is dat nog duren? [Student antwoord, onverstaanbaar] Precies. Het aantal mensen dat voor Alice in de gelinkte lijst. Dus het is niet helemaal perfect, omdat onze data structuur, nogmaals, heeft deze verticale toegang en dan heeft deze gelinkte lijsten opknoping - in feite, laten we het niet maken het een een array. Het heeft deze gelinkte lijsten opknoping off van het dat ziet er een beetje iets als dit. Maar het probleem is als Alice en Adam en al die andere A namen uiteindelijk meer en meer daar, het vinden van iemand zou kunnen komen, het nemen van een heleboel stappen, bcause moet je de gelinkte lijst doorlopen, die een lineaire bewerking. Dus echt dan de insertie tijd uiteindelijk O (n), waarbij n het aantal elementen in de lijst. Gedeeld door, laten we willekeurig noemen m, waarbij m het aantal gekoppelde lijsten dat wij in deze verticale as. In andere woorden, als we aannemen werkelijk een gelijkmatige verdeling van namen totaal onrealistisch. Er is uiteraard meer van een aantal brieven dan anderen. Maar als we aannemen voor het moment een uniforme verdeling, en we hebben n totale mensen, en m totale ketens ons beschikbaar, dan is de lengte van elk van deze kettingen vrij eenvoudig zal het totaal n gedeeld door het aantal ketens zijn. Dus n / m. Maar hier is waar we zijn allemaal wiskundig slim. m is een constant, omdat er een vast aantal van deze. Je gaat uw array declareren aan het begin, en we zijn niet de grootte van het verticale as. Per definitie, blijft die vast. Het is alleen de horizontale as, om zo te zeggen, dat is aan het veranderen. Dus technisch is dit een constant. Dus nu, het inbrengen tijd is vrij veel O (n). Dus dat voelt niet zo heel veel beter. Maar wat is de waarheid hier? Nou, al die tijd, weken, we hebben gezegd O (n ²). O (n), 2 x n ², - n, gedeeld door 2. . . ech. Het is gewoon n ². Maar nu, in dit deel van het semester, kunnen we beginnen te praten over de echte wereld weer. En n / m is geheel sneller dan n alleen. Als je een duizend namen, en je breekt ze in meerdere emmers zodat u slechts tien namen in elk van deze ketens, absoluut zoeken tien dingen gaat worden sneller dan een duizend dingen. En dus een van de komende probleem sets zal je uitdagen na te denken over precies dat, ook al, ja, asymptotisch en wiskundig, dit is nog steeds gewoon lineair, die zuigt in het algemeen wanneer het proberen om dingen te vinden. In werkelijkheid gaat het om sneller te zijn dan dat hierdoor deler. En op dat moment nog weer gaat deze trade-off worden en dit conflict tussen theorie en werkelijkheid, en een van de knoppen zal gaan draaien op dit punt in de semester is van de werkelijkheid een als we soort voorbereiden end semster's, zoals we introduceren in de wereld van web programmeren, waar echt, is de prestaties gaat tellen, omdat uw gebruikers gaan beginnen te voelen en waarderen slecht ontwerp beslissingen. Dus hoe ga je over het implementeren van een gekoppelde - een hash table met 31 elementen? En het vorige voorbeeld was willekeurig over verjaardagen. Als iemand een verjaardag op 1 januari of 1 februari zullen we ze in de lege emmer. Als het 2 januari 2 februari 2 maart zullen we ze in de lege emmer. Daarom was het 31. Hoe verklaart u een hash table? Het kan vrij eenvoudig, knooppunt * tafel is mijn willekeurige naam voor het, [31]. Dit geeft me 31 verwijzingen naar knooppunten, en dat kan ik hebben 31 verwijzingen naar gelinkte lijsten zelfs als die ketens zijn in eerste instantie NULL. Wat wil ik zetten als ik wil opslaan "Alice", "Bob", "Charlie"? Nou, we moeten die dingen verpakken in een structuur omdat we wijzen op Alice Bob te wijzen op Charlie, enzovoort. We kunnen gewoon niet de namen alleen al, dus ik zou kunnen leiden tot een nieuwe structuur genaamd knooppunt hier. Wat is een echte knoop? Wat is een knooppunt in deze nieuwe gekoppelde lijst? Het eerste ding, genaamd woord, is voor de naam van de persoon. LENGTE, vermoedelijk, heeft betrekking op de maximale lengte van de naam van een mens, wat dat ook is, 20, 30, 40 tekens in gekke hoek gevallen, en +1 is voor wat? Het is gewoon de extra NULL karakter \ 0. Dus dit knooppunt inpakken "iets" in van zichzelf, maar het verklaart ook een pointer genaamd volgende zodat we kunnen keten Alice aan Bob om Charlie, enzovoort. Kan NULL zijn, maar hoeft niet per se zo te zijn. Eventuele vragen over deze hash tables? Ja? [Student vraagt ​​vraag, onverstaanbaar] Een array - goede vraag. Waarom is dit char woord in een array in plaats van alleen char *? In dit enigszins willekeurig voorbeeld, heb ik niet willen hebben hun toevlucht om malloc voor elk van de oorspronkelijke namen. Ik wilde een maximale hoeveelheid geheugen die verklaren voor de string zodat ik kon kopiëren naar de structuur Alice \ 0 en niet te maken hebben met malloc en free en dergelijke. Maar ik kon dat doen als ik wilde om meer bewust te zijn van de ruimte gebruik. Goede vraag. Dus laten we proberen weg te generaliseren van deze en de focus van de rest van vandaag op datastructuren meer in het algemeen en andere problemen die we kunnen oplossen met behulp van dezelfde grondbeginselen hoewel de data structuren zelf kunnen verschillen in hun gegevens. Zo blijkt in de informatica, bomen zijn zeer algemeen. En u kunt denken aan een boom als een soort stamboom, waar er een aantal wortels, sommige matriarch of patriarch, oma of opa of eerder terug, waar doorheen zijn vader en moeder of verschillende broers en zussen of iets dergelijks. Dus een boomstructuur heeft knooppunten en heeft kinderen meestal 0 of meer kinderen voor elk knooppunt. En sommige van het jargon dat u ziet in dit plaatje hier is een van de kleine kinderen of kleinkinderen aan de randen die geen pijlen die uitgaan van hen, dat zijn de zogenaamde bladeren en ieder aan de binnenzijde is een innerlijke knoop, je kunt het iets in die richting. Maar deze structuur is vrij normaal. Deze is een beetje arbitrair. We hebben een kind aan de linkerkant, we hebben drie kinderen aan de rechterkant, twee kinderen op de links onderaan. Dus we kunnen hebben verschillende maten bomen, maar als we beginnen om dingen te standaardiseren, en je zou kunnen herinneren deze uit video Patrick op binair zoeken van een eerdere korte online, binary search hoeft niet te worden uitgevoerd met een array of stukjes papier op een schoolbord. Stel dat je wilde je nummers op te slaan in een meer geavanceerde datastructuur. Je zou kunnen leiden tot een boom als deze. Je kan een knooppunt aangegeven in C en knooppunt dat ten minste twee elementen erin. Een daarvan is het nummer dat u wilt opslaan, en de andere is - nou ja, we moeten nog een. De andere is de kinderen. Dus hier is een andere datastructuur. Deze keer wordt een knooppunt gedefinieerd als opslaan van een aantal n en dan twee pointers, links en rechts kind kind. En ze zijn niet willekeurig. Wat is wetenswaardigs over deze boom? Wat is het patroon in de manier waarop we hebben gelegd dit uit of hoe Patrick haar bepaalde voorwaarden in zijn video? Het is een beetje voor de hand dat er een aantal sortering gebeurt hier, maar wat is het eenvoudige regel? Ja? [Student antwoord, onverstaanbaar] Perfect. Als je een blik werpen op deze, zie je de kleine aantallen aan de linkerkant, grote getallen aan de linkerkant, maar dat geldt voor elk knooppunt. Voor elk knooppunt de linker kind kleiner dan, en de rechter kind daarvan bedragen. Wat dit betekent is nu als ik wil deze datastructuur zoeken naar, laten we zeggen, het aantal 44, Ik moet om te beginnen bij de wortel, want zoals met al deze meer complexe data structuren nu, we hebben maar een pointer naar een ding, het begin. En in dit geval, het begin de wortel. Het is niet het linker uiteinde, het is de wortel van deze structuur. Dus ik zie hier is 55, en ik ben op zoek naar 44. Welke richting wil ik heen? Nou, ik wil naar links, want natuurlijk, het recht zal zijn te groot. Dus hier zien, je bent soort van conceptueel hakken de boom in de helft omdat je nooit naar beneden naar de rechterkant. Dus nu ga ik van de 55 naar de 33. Het is te klein van een getal. Ik ben op zoek naar 44, maar nu weet ik of 44 is in deze boom, ik kan uiteraard naar rechts. Dus nogmaals, ik ben het snoeien van de boom in de helft. Het is vrijwel identiek conceptueel aan het telefoonboek. Het is identiek aan wat we hebben gedaan met de papieren op het bord, maar het is een meer geavanceerde structuur die ons in staat stelt om daadwerkelijk te doen deze verdeel en heers door het ontwerp van het algoritme, en in feite, het doorkruisen van een structuur als deze - whoops. Verplaatsen van een structuur als deze, waar het maar "deze kant op of ga op die manier," betekent al dat code die je geest gebogen op het eerste bij de uitvoering van het in paragraaf of wandelen door het thuis, voor binaire zoeken, met behulp van recursie of iteratie, het is een pijn in de nek. Vind de middelste element, dan doe je boven of beneden afronden. Er is een schoonheid om dit, want we kunnen nu weer gebruik maken van recursie, maar veel schoner. Sterker nog, als je op het nummer 55 en u wilt tot 44 te vinden, ga je links in dit geval, wat doe je dan? Je loopt precies hetzelfde algoritme. U controleert de waarde van het knooppunt, dan ga je naar links of rechts. Dan moet je controleren de waarde van de knoop, ga links of rechts. Dit is perfect geschikt voor recursie. Dus ook al in het verleden hebben we gedaan wat vrij willekeurige voorbeelden waarbij recursie die niet moeten recursieve, met data Werking, vooral bomen, het is een perfecte toepassing van dit idee van het nemen van een probleem, krimpen, en vervolgens oplossen hetzelfde type, maar kleiner programma. Dus er is nog een datastructuur die we kunnen introduceren. Deze is ontworpen op het eerste gezicht om naar te kijken cryptisch, maar deze is geweldig. Dus dit is een gegevensstructuur genaamd een trie, trie, die is overgenomen van de woorden vinden, die niet uitgesproken re-try-val, maar dat is wat de wereld noemt deze dingen. Tries. T-r-i-e. Het is een boomstructuur van een soort, maar elk van de knooppunten in een trie lijkt te zijn wat? En dit is een beetje misleidend, want het is een soort van afgekorte. Maar het lijkt erop dat elk knooppunt in dit trie eigenlijk een array. En hoewel de auteur van dit diagram is niet aangetoond dat het, in dit geval trie een datastructuur tot doel in leven te slaan woorden als A-l-i-c-e of B-o-b. En de manier waarop deze data stores Alice en Bob en Charlie en Anita enzovoort wordt gebruikt om een ​​array waarbij Alice slaan in een Trie, We beginnen bij de root-node die eruit ziet als een array, en het is geschreven in steno notatie. De auteur weggelaten abcdefg omdat er geen namen mee. Ze toonde alleen M en P en T, maar in dit geval, Laten we uit de buurt van Alice en Bob en Charlie gaan om enkele namen die hier zijn. Maxwell is eigenlijk in dit schema. Dus hoe heeft de auteur winkel M-een-x-w-e-l-l? Hij begon bij het hoofdknooppunt en naar [M], dus ongeveer 13, de 13e plaats in het stelsel. Dan vanaf daar is er een pointer. Een pointer die naar een andere array. Van daar de auteur geïndexeerd in die array op locatie A, want er afgebeeld in de linkerbovenhoek, en dan is hij of zij gevolgd die pointer naar een andere array, en ging naar de wijzer op locatie X. Dan in de volgende matrix locatie W, E, L, L, enzovoort, en tot slot, laten we eigenlijk proberen om een ​​foto te maken aan deze. Hoe ziet een knooppunt eruit in de code? Een knooppunt in een trie bevat een array van pointers naar meer knooppunten. Maar er ook nog een soort van booleaanse waarde, althans in deze implementatie. Ik ben toevallig noem het is_word. Waarom? Want als je Maxwell invoegen, je bent niet invoegen niets in deze gegevensstructuur. U bent niet schrijft M. U bent niet X. schrijven Alles wat je aan het doen bent is na pointers. De wijzer dat M, dan is de pointer die A vertegenwoordigt vertegenwoordigt, vervolgens de aanwijzer dat X, dan W, E, L, L vertegenwoordigt, maar wat je moet doen op het einde is een soort van gaan, controleren, bereikte ik deze locatie. Er was een woord dat hier eindigt in de datastructuur. Dus wat een trie is echt gevuld met en de auteur koos ervoor om te vertegenwoordigen deze eindstations met driehoekjes. Dit betekent alleen dat het feit dat dit driehoek hier is, deze boolean waarde true betekent dat als je gaat achteruit in de boom, dat betekent dat een woord met de naam Maxwell is in deze. Maar het woord foo bijvoorbeeld is niet in de boom, want als ik beginnen bij de root node hier boven, Er is geen f aanwijzer, geen o wijzer, geen o pointer. Foo is niet een naam in dit woordenboek. Maar daarentegen turing, t-u-r-i-n-g. Nogmaals, ik heb niet op te slaan t of u of r of i of n of g. Maar ik heb op te slaan in deze datastructuur een waarde van ware weg hier beneden in deze node - in de boom door het instellen van deze boolean waarde van is_word op true. Dus een trie is een soort van deze zeer interessante meta-structuur, waar je niet echt het opslaan van de woorden zelf voor dit soort woordenboek. Voor alle duidelijkheid, je bent gewoon opslaan ja of nee, er is een woord dat hier eindigt. Nu, wat is de implicatie? Als je 150.000 woorden in een woordenboek dat u probeert op te slaan in het geheugen met behulp van iets als een gekoppelde lijst, je gaat tot 150.000 knooppunten in uw gekoppelde lijst hebben. En het vinden van een van die woorden alfabetisch kon nemen O (n) tijd. Lineaire tijd. Maar in het geval van een trie, wat is de looptijd van het vinden van een woord? Het blijkt de schoonheid hier is dat zelfs als je 149.999 woorden reeds in dit woordenboek, zoals die met deze gegevensstructuur, hoeveel tijd is er nodig om te vinden of plaats een persoon meer in dat, net als Alice, Alice? Nou, het is slechts 5, misschien 6 stappen voor de afsluitende karakter. Omdat de presense andere namen in de structuur niet in de weg van het invoegen van Alice. Bovendien, het vinden van Alice zodra er 150.000 woorden in dit woordenboek niet in de weg van het vinden van Alice helemaal niet, omdat Alice is. . . . . hier, want ik vond een booleaanse waarde. En als er geen boolean waar is, dan Alice niet in deze gegevensstructuur van woorden. Met andere woorden, de looptijd van het vinden dingen en plaatsen dingen in deze nieuwe datastructuur van trie is O van - het is niet n. Omdat de presense van 150.000 mensen heeft geen effect op Alice lijkt. Dus laten we noemen het k, waarbij k de maximale lengte van een woord in het Engels die typisch niet meer dan 20 iets tekens. Dus k een constante. Dus de Heilige Graal lijken we nu hebben gevonden is dat van een trie, constante tijd voor inserts, voor lookups, voor verwijderingen. Omdat het aantal zaken reeds in de structuur, die niet eens fysiek aanwezig. Nogmaals, ze zijn gewoon soort van afgevinkt, ja of nee, heeft geen invloed op de toekomstige looptijd. Maar er moet toch een addertje onder het gras, anders zouden we niet hebben zoveel tijd verspild op al deze andere gegevens structuren alleen maar om eindelijk het geheim een ​​dat is geweldig. Dus welke prijs betalen we dit grootheid hier te bereiken? Ruimte. Dit ding is enorm. En de reden dat de auteur hier niet aanwezig is, merken dat al deze dingen die eruit zien als arrays, hij niet de aandacht van de rest van de boom, de rest van de trie, omdat ze gewoon niet relevant voor het verhaal. Maar al deze knooppunten zijn super breed, en elke node in de boom neemt 26 of eigenlijk, kan 27 tekens zijn, omdat in dit geval was ik ook ruimte voor de apostrof zodat we konden hebben apostrophized woorden. In dit geval zijn grote arrays. Dus ook al zijn ze niet picutured, Dit neemt een enorme hoeveelheid RAM-geheugen. Welke zou wel goed, especilly in de moderne hardware, maar dat is de afweging. We krijgen minder tijd door het uitgeven van meer ruimte. Dus waar is dit allemaal? Nou, laten we het doen - laten we hier zien. Laten we een sprong naar deze man hier. Geloof het of niet, zo leuk als C is al geruime tijd, we het bereiken van het punt in het semester waar is het tijd om de overgang naar dingen meer modern. Dingen op een hoger niveau. En hoewel voor de komende paar weken we nog steeds om ons onder te dompelen in de wereld van de wijzers en geheugenbeheer om dat comfort waarmee we dan bouwen aan de slag, het eindspel is uiteindelijk ironisch te introduceren, en niet deze taal. We zullen, door te brengen als 10 minuten praten over HTML. Alle HTML is een opmaaktaal, en wat een opmaaktaal is is deze reeks open beugels en gesloten beugels die zeggen 'maken dit vet' 'Maken deze cursief', 'maken deze gecentreerd.' Het is niet zo intellectueel interessant, maar het is super handig. En het is zeker alomtegenwoordig deze dagen. Maar is wat krachtig over de wereld van HTML, en web programmeren meer in het algemeen, is het bouwen van dynamische dingen, het schrijven van code in talen als PHP of Python of Ruby of Java of C #. Echt, wat de taal van uw keuze is, en het genereren van HTML dynamisch. Het genereren van iets genaamd CSS dynamisch. Cascading style sheets, die ook over esthetiek. En dus zelfs al, vandaag, als ik naar sommige website zoals de bekende Google.com, en ik ga te bekijken, ontwikkelaar, brontekst bekijken, die misschien heb je eerder gedaan, maar gaat om de bron te bekijken, dit spul ziet er waarschijnlijk vrij cryptisch. Maar dit is de onderliggende code die Google.com implementeert. Aan de voorkant. En eigenlijk alles is pluizige esthetiek spul. Dit is CSS hier. Als ik blijf scrollen naar beneden zullen we nog wat gekleurde spul. Dit is HTML. Google's code ziet eruit als een puinhoop, maar als ik echt open te stellen een ander venster, we zien wat structuur daarvan. Als ik open dit op, hier op te merken, is het een beetje beter leesbaar. We gaan het duurde niet lang zien deze tag, [woord] is een tag, HTML, hoofd, lichaam, div, script, tekstgebied, spanwijdte, gecentreerd, div. En dit is ook sorteren van cryptische uitziende op het eerste gezicht, maar al deze puinhoop volgt bepaalde patronen, en herhaalbare patronen, dus dat als we eenmaal de basis naar beneden, zult u in staat om code zoals dit te schrijven en dan manipuleren code zoals deze met behulp van nog een andere taal, genaamd JavaScript. En JavaScript is een taal die binnen loopt van een browser vandaag aan dat we gebruiken op Harvard cursussen, voor de cursus shopping tool die gebruik maakt van Google maps om u een hele hoop van dynamiek, Facebook geeft u te laten zien instant statusupdates, Twitter gebruikt het om te laten zien tweets direct. Dit alles zullen we beginnen om ons te verdiepen in Maar om daar te komen, moeten we een beetje iets over het internet te begrijpen. Deze clip is hier slechts een minuut lang, en laten we aannemen dat voor nu is dit, in feite, hoe het internet werkt als een teaser voor wat er gaat komen. Ik geef je 'Strijders van het net. " [♫ Slow koor muziek ♫] [Mannelijk verteller] Hij kwam met een boodschap. Met een protocol al zijn eigen. [♫ Snellere elektronische muziek ♫] Hij kwam naar een wereld van firewalls, routers onverschillig, en gevaren veel erger dan de dood. Hij is snel. Hij is sterk. Hij is TCP / IP, en hij heeft uw adres. Strijders van het Net. [Malan] Volgende week, dan. The Internet. Web programmering. Dit is CS50. [CS50.TV]