DAVID MALAN: Très bien. Bienvenue à CS50. C'est le début de la semaine 8. Et rappelons que problème posé 5 terminée avec un peu d'un défi. Donc, en supposant que vous avez récupéré tout votre Les boursiers de l'enseignement et des photographies de CA dans le fichier card.raw, vous êtes admissible maintenant trouver tous ces gens, et Un heureux gagnant marcher jusqu'à la maison avec une de ces choses, le mouvement de saut appareil que vous pouvez utiliser pour finale projets, par exemple. 

Ceci, chaque année, conduit à un peu de frayeurs. Et donc ce que je pensais faire est de partager avec vous quelques-unes des notes qui ont allé en arrière sur la liste du personnel de la fin. Par exemple, hier soir, citation unquote, à partir de l'un des employés membres: «Je viens d'avoir un coup d'étudiant à ma porte pour prendre une photo avec moi. Stalkers, je vous dis. "Commencé assez descriptive et puis nous avons déménagé à une heure ou deux plus tard: «J'ai eu une étudiant qui m'attendait après l'article et il avait tous nos noms et photos sur quelques feuilles de papier. "Très bien. Alors organisé, mais pas tout ce qui pourtant rampant. 

Puis: «J'étais hors de la ville ce week-end, et quand je suis rentré, il y en avait un dans ma chambre à coucher. "[rires] DAVID MALAN: citation suivante d'un personnel membre », un étudiant est venu à ma maison à Somerville à 4 heures ce matin. "Next personnel, "je suis arrivé à mon hôtel à San Francisco et un étudiant attendait me dans le hall avec trois reflex numériques ". Type d'appareil. «Je ne suis même pas sur le personnel de ce semestre, mais un étudiant fait irruption dans ma maison ce matin et enregistré le tout avec Google Glass. "Et puis enfin, "Au moins 12 personnes ont été avidement en attendant pour moi quand je suis sorti de mon limousine, puis je réveillé. "Très bien. Donc, parmi les photographies, comme vous pouvez rappelons-le, sont cet homme là, qui vous pourrait savoir que Milo Banana, qui vit avec Lauren Carvalho, notre tête enseignement Fellow. Milo, Milo, viens ici garçon. Milo. Milo. Rappelez-vous, il porte en verre Google, de sorte nous allons vous montrer tout cela après. Donc, c'est Milo si vous souhaitez prendre une photo avec lui par la suite. Si vous souhaitez regarder dehors au public y. OK. C'est une bonne séquence. Eh bien, Milo Banana. Oh, ne fais pas ça. 

[Rires] 

OK. Ainsi, un mot alors sur ce qui nous attend, parce que nous commençons à la transition, cette semaine précisément, à partir de C dans un environnement de ligne de commande pour PHP et JavaScript et SQL et HTML et CSS dans un environnement basé sur le Web, nous serons vous équiper avec tout le plus de connaissances pour projets finaux potentiels. À cette fin, le cours a un tradition d'organiser des séminaires qui portent sur des sujets tangentiels au cours. Très liée à la programmation et à le développement d'applications et ainsi de suite, mais pas nécessairement exploré par propre syllabus du cours. 

Donc, si vous pourriez être intéressé par un ou plus des séminaires de cette année, s'inscrire à cs50.net/seminar. Il ya des séminaires âgées à cs50.net/seminars. Et sur la liste à ce jour pour cette année sont des applications Web étonnants avec Ruby on Rails, qui est une alternative langue de PHP. Computational Linguistics. Introduction à iOS, qui est le plate-forme qui est utilisée pour l'iPhone et l' développement iPad. JavaScript pour les applications Web, nous couvrirons , mais à ce séminaire, vous irez plus en détail. 

Leap mouvement, donc nous allons effectivement avoir une certaine de nos amis de Leap Motion l'entreprise elle-même, rejoignez-nous. Demain, en effet, de fournir un séminaire pratique, si de vous intéresser. Meteor.js, une technique alternative pour l'utilisation de JavaScript n'est pas dans un navigateur, mais sur un serveur. Node.js, ce qui est beaucoup Dans cette veine ainsi. Design élégant Android. Android est une alternative très populaire pour iOS et Windows Phone et d'autres plates-formes mobiles. And Web Security Active Defense. 

Donc en fait, si vous souhaitez à s'engager dans ce domaine, laissez-moi prendre note de cela. Nous sommes très heureux de dire que nos amis de Leap Mouvement, qui est une startup - cet appareil vraiment juste venu il ya quelques mois - a gracieusement fait don de 30 de ces appareils à la classe pour que de nombreux étudiants, si que vous souhaitez emprunter du matériel vers la fin de semestre et l'utiliser pour un projet final réel. Ils soutiennent un certain nombre de langues. Aucun d'entre eux C, aucun d'entre eux PHP, réaliser une ou plusieurs de ces séminaires pourraient être d'intérêt. Et chacun d'entre eux sera tourné en Si vous n'êtes pas en mesure y assister en personne. Le calendrier sera annoncé via e-mail que nous renforçons chambres. 

Et enfin, si vous allez à projects.cs.50.net, il s'agit d'un site web nous maintenons chaque année que nous invitons les gens de la communauté, les professeurs, départements, le personnel et les à l'extérieur du CS50 à proposer des idées de projets. Choses d'intérêt à des groupes d'étudiants. Choses d'intérêt pour les ministères. Donc, ne mettez-y si vous êtes en difficulté l'incertitude quant à ce que vous vous aimeraient aborder. 

Donc, la dernière fois, nous avons introduit un doute structure de données plus complexes que nous avions vu ces dernières semaines. Nous avions été en utilisant des tableaux assez heureusement comme utile si structure de données simpliste. Ensuite, nous avons introduit ces derniers, qui sont bien sûr liés listes. Et ce qui était l'une des motivations pour l'introduction de cette structure de données? Ouais? Qu'est-ce que c'est? 

AUDIENCE: taille dynamique. 

DAVID MALAN: taille dynamique. Ainsi, alors que dans le tableau, vous devez connaître sa taille à l'avance quand vous allouez il. Dans la liste liée, vous n'avez pas avoir le savoir. Vous pouvez juste malloc, ou plus généralement, allouer un montant supplémentaire noeud, pour ainsi dire, à tout moment vous voulez insérer d'autres données. Et le noeud n'a pas de sens prédéterminé. C'est juste un terme générique décrivant une sorte de conteneur que nous sommes à l'aide de notre structure de données pour stocker quelque élément d'intérêt, qui, dans ce cas se trouvent être des entiers. 

Mais il ya toujours un compromis. Ainsi nous obtenons tailles dynamiques des données structure, mais à quel prix payons-nous? Quel est l'inconvénient des listes chaînées? Ouais? 

AUDIENCE: nécessite plus de mémoire. 

DAVID MALAN: Il faut plus de mémoire, comment exactement? 

AUDIENCE: [inaudible]. 

DAVID MALAN: Exactement. Alors maintenant, nous avons pointeurs prenant mémoire supplémentaire que nous avons précédemment n'avait pas besoin, parce que l'avantage d'un tableau, bien sûr, est que tout est contigu, dos à dos à dos, ce qui vous donne accès aléatoire. Parce que, tout en utilisant des crochets notation, ou plus techniquement pointeur arithmétique, addition très simple, vous pouvez accéder à n'importe quel éléments en temps constant. Et en fait, c'est le genre d'allusion à un autre prix que nous payons avec un liste chaînée. 

Qu'advient-il de la durée de fonctionnement de quelque chose comme la recherche, si je veux trouver une certaine valeur et à l'intérieur d'une liste chaînée? Qu'est-ce que mon temps à courir devenir? Big O n. Si c'est réglé pour? Que faire si la structure de données est triée? Puis-je faire mieux que grand O n pour la recherche? Non, parce que dans le pire des cas, il peut très bien être triés, mais le nombre vous cherchez peut-être grand. Il pourrait être le numéro 100, qui pourrait arriver à être tout le moyen à la fin. Et parce que vous ne pouvez accéder à un linked liste dans cette mise en œuvre par chemin de son premier noeud, vous êtes encore un peu de chance. Vous devez traverser toute chose du premier au dernier afin de trouver cette grande valeur comme 100. Ou pour déterminer s'il s'agit d' même pas là. 

Donc, nous ne pouvons pas faire ce que l'algorithme dans un ensemble de données structure qui ressemble à ceci? Nous ne pouvons pas faire de recherche binaire, parce que recherche binaire nécessaire que nous avions accès aléatoire. Nous pourrions simplement sauter d'un endroit à emplacement sans avoir à suivre ces miettes de pain dans la forme l'ensemble de ces pointeurs. 

Maintenant, comment at-on en œuvre? Eh bien, si nous allons à l'écran ici, si nous pouvons ré-écrire rapidement ces données Structure - mon écriture n'est pas si grand ici, mais nous allons essayer. Alors struct typedef, et qu'ai-je voulez appeler cette chose ici? Node. Donc, je vais nous avons commencé. Et maintenant, ce qui doit être à l'intérieur de la structure de données pour que seuls liste chaînée? Combien de champs? 

Donc deux. L'un est assez facile. Alors int n. Et nous pourrions appeler n ce que nous voulons, mais il devrait être un int si nous sommes mettre en œuvre une liste chaînée pour ints. Et maintenant, qu'est-ce que la seconde domaine en être ainsi? Struct noeud *. Donc, si je fais noeud struct *, puis je peut appeler cela aussi que je veux, mais juste pour être clair, je vais appeler à côté, comme nous l'avons fait. Et puis je vais fermer mes accolades. 

Et maintenant, que la dernière fois, Je mets noeud ici. Mais si je suis en déclarant ceci est aussi un noeud, pourquoi ai-je pris la peine d'être si verbose ici en déclarant struct * noeud suivant, par opposition à juste noeud * à côté? Ouais? 

AUDIENCE: [inaudible]. 

DAVID MALAN: Exactement. Exactement. Parce que C vous prend vraiment littéralement et ne voit que la définition de noeud chemin ici-bas, vous ne pouvez pas référer ici. Donc, nous avons ce genre de préemption déclaration ici, qui est certes plus bavard. Struct noeud, ce qui signifie nous pouvons maintenant y accéder à l'intérieur de la structure de données. 

Et en passant, parce que c'est devenir un peu plus subjective maintenant, l'étoile ne peut techniquement faire ici, il peut aller ici, il peut même aller dans le milieu. Nous avons adopté, dans le guide de style pour cours, la convention de mise l'étoile juste à côté des données type, qui, dans ce cas, serait nœud de structure. Mais réaliser dans un grand nombre de manuels et références en ligne, vous pourriez effectivement voir de l'autre côté. Mais juste se rendre compte que les deux seront effectivement travaillez et vous devez simplement être cohérente. 

Très bien. C'était donc notre déclaration du nœud de structure. Mais ensuite nous avons commencé à faire plus choses sophistiquées. Par exemple, nous avons décidé d'introduire quelque chose comme une table de hachage. Donc, voici une table de hachage de taille n, indexé à partir de 0 en haut à gauche de n moins 1 en bas à gauche. Cela pourrait être un hash table pour rien. Mais ce genre de choses ne nous parlons sur l'utilisation d'une table de hachage pour? Stockage quoi? 

Noms. Nous pourrions faire des noms comme nous avons fait la dernière fois. Et vraiment, vous pouvez stocker n'importe quoi. Et nous verrons ce message dans PHP et JavaScript. Une table de hachage est une belle sorte de Suisse Couteau qui vous permet de stocker à peu près tout ce que vous voulez à l'intérieur de il en associant des touches avec des valeurs. Touches de valeurs. 

Or, dans ce cas simple, notre touches sont que des chiffres. Nous mettons en place une table de hachage tableau comme un tableau. Et si les touches sont 0, 1, 2, et ainsi de suite. Et nous, en tant qu'êtres humains, a décidé dernier semaine que vous savez quoi, si nous sommes aller à des noms de magasins, disons simplement arbitrairement, mais assez raisonnablement, supposons que Alice, une un nom, va juste être indexé dans 0. Et Bob, un nom B, sera indexé en 1, et ainsi de suite. Donc, nous avons eu une correspondance entre les entrées, qui sont des chaînes, et le hachage endroits, qui sont des nombres. 

Donc, ce processus est généralement connu comme une fonction de hachage, et vous pouvez vraiment mettre en œuvre dans le code. Si je voulais mettre en œuvre une fonction de hachage qui fait exactement ce que nous vient d'être décrit de la dernière fois, je pourrais déclarer une fonction qui prend comme entrée par exemple - et nous allons le faire sur cette écran ici. Si je voulais mettre en place une table de hachage fonction, je pourrais dire quelque chose comme ça. 

Il va retourner un int. Ça va être appelé hash, et c'est va accepter comme argument une chaîne, ou nous pouvons être plus appropriée maintenant, et dire char *, nous l'appellerons s. Et puis tout cette fonction a à faire, en fin de compte, est de retour int. Maintenant, comment il le fait qui pourrait ne pas être si évident. Je vais mettre en œuvre ce sans aucune forme de contrôle d'erreur pour le moment. Je vais juste dire aveuglément, le retour tout ce qui est à l support 0, moins, disons, capitale un point-virgule. 

Totalement rompu. Ce n'est pas parfait parce que un, si s est nul? Les mauvaises choses vont se passer. Deux, si la première lettre de cette nom n'est pas une majuscule? Cela ne va pas tourner bien fonctionné non plus. Il pourrait être une lettre minuscule ou non une lettre du tout. Donc totalement marge d'amélioration ici, mais c'est l'idée de base. 

Qu'est-ce que nous avons décrit la semaine dernière verbalement seulement un processus de mappage pour Alice 0 à 1 et Bob peuvent être exprimés certainement plus formulaically comme C fonctionner ici. Appelé à nouveau hash, prend une chaîne comme entrée, puis en quelque sorte fait quelque chose avec cette entrée pour produire un signal de sortie. Non contrairement à notre description de la boîte noire que nous avons longtemps fait. Je ne sais pas comment cela pourrait être travailler sous la hotte. 

Pour le jeu de problème 6, l'un des défis c'est à vous de décider ce que sera votre fonction de hachage être? Que se passe-être à l'intérieur de ce noir boîte, et sans doute, ce sera un peu plus intéressant que cela, et nettement plus sujettes à l'erreur vérifier que ce particulier mise en oeuvre. 

Mais des problèmes peuvent survenir, non? Si nous avons une structure de données telle que cette une, c'est quoi l'un des problèmes vous pouvez exécuter dans le temps que vous insérez de plus en plus des noms dans l' table de hachage? Vous obtenez collisions, non? Que faire si vous avez Alice et Aaron, deux personnes dont les noms arrivé à commencer par A? Cela soulève la question, où vous mettre le second un tel nom? 

Eh bien, vous pourriez naïvement il suffit de mettre où Bob appartient, mais Bob est genre de vissé si vous essayez d' insérer son nom à côté et il n'y a pas de place pour lui. Donc, vous pourriez mettre Bob où Charlie est, et vous pouvez imaginer ce très rapidement sombrer dans un peu de désordre. Quelque chose de linéaire à la fin, où vous suffit de rechercher le tout à la recherche d'Alice ou de Bob ou Aaron ou Charlie. 

Ainsi, au lieu que nous avons proposé, au lieu de simplement linéairement sondage pour les espaces ouverts et plopping les noms là-bas, nous proposé une approche plus fantaisistes. Une table de hachage en œuvre encore avec un tableau d'index, mais le type de données ces indices étaient maintenant des pointeurs. Pointeurs vers quoi? Les pointeurs vers des listes chaînées. 

Parce que le rappel d'une liste liée est vraiment juste un pointeur vers un noeud, et le noeud possède un champ à côté, et que le noeud présente une zone suivante, et ainsi de suite. Ainsi, vous pouvez maintenant penser à ce tableau sur le côté gauche d'une table de hachage en tant que conduisant à une liste liée. L'avantage de ce qui est si vous obtenez un collision entre Alice et Aaron, que faites-vous avec le deuxième telle personne? Vous attachez simplement lui à l' extrémité, ou même le début de cette liste liée. 

Et en fait, disons simplement nouilles à travers que pour une seconde. Où serait le plus logique? Si j'insère Alice et elle finit à le premier emplacement, puis j'essaie de insérer le nom d'Aaron, et il ya évidemment une collision, devrais-je mettre lui au début de la liste liée? C'est à ce premier emplacement, ou à la fin? 

AUDIENCE: [inaudible]. 

DAVID MALAN: OK. J'ai entendu commencer. Pourquoi au début? 

AUDIENCE: [inaudible]. 

DAVID MALAN: OK. C'est alphabétique, donc c'est bien. C'est un bon établissement. Il va me faire gagner du temps potentiellement. Il ne sera pas me laisser faire une recherche binaire, mais je pourrait au moins être en mesure de sortir d'une boucle si je me rends compte, eh bien, je suis bien passé étaient Aaron serait dans ce triés liste chaînée. Je n'ai pas à perdre mon temps à regarder tout le chemin vers la fin. Donc, c'est raisonnable. Sinon, pourquoi auriez-vous besoin d'insérer le nom de la collision à l' au début de la liste? Qu'est-ce que c'est? 

AUDIENCE: [inaudible]. 

DAVID MALAN: Il pourrait prendre un certain temps pour obtenir à la fin de la liste. Et en fait, plus longtemps et plus longtemps. Les autres noms que vous insérez A commencer par le plus que chaîne va se faire. Le plus qui reliait liste va se faire. Donc, vous êtes vraiment juste perdre votre temps. Peut-être que vous êtes mieux maintenant temps d'insertion constant, grand O 1, en mettant toujours le nom à entrer en collision le début de la liste liée, et ne pas se soucier autant sur le tri. 

Quelle est la meilleure solution? On ne sait pas. Il genre de dépend de ce que l' distribution, ce que le modèle est des noms que vous avez inséré. Ce n'est pas nécessairement une réponse évidente. Mais ici, encore une fois, est une occasion de conception. 

Alors nous avons regardé cette chose, qui est vraiment l'autre grande opportunité P-set 6. Et de réaliser, si vous n'avez pas déjà, Zamyla plonge dans ces deux hachage, tables et essaie, plus en détail. Et la présentation vidéo est intégré dans le p-ensemble spec. Ce fut un trie - T-R-I-E. Et ce qui est intéressant à propos de ce n'était que le temps d'exécution de recherche d'un nom, comme Maxwell dernière fois, était grand O de quoi? Qu'est-ce que c'est? 

AUDIENCE: Le nombre de lettres. 

DAVID MALAN: Nombre de lettres. J'ai entendu deux choses. Nombre de lettres et de constante de temps. Allons donc à cette première. Le nombre de lettres. Eh bien, cette structure de données, le rappel est Comme un arbre, un arbre de la famille, chacun des nœuds dont sont constitués de tableaux. Et ces tableaux sont des pointeurs vers d'autres tels noeuds, ou d'autres comme les tableaux dans l'arbre. 

Donc, si nous voulions déterminer ensuite si Maxwell est ici, je pourrais aller à la première rangée, au sommet de l'arbre, le soi-disant racine, haut de le trie, puis suivez le pointeur m, puis l'un pointeur, alors x, w, e, l, l. Et puis, quand je vois un symbole spécial, désigné ici comme un triangle. Dans le code, vous verrez que nous vous proposons implémenté comme un bool, juste dire oui ou non, un mot s'arrête ici. 

Eh bien, une fois que nous sommes allés à M-A-X-W-E-L-L, qui ressemble à sept, peut-être huit si nous allons un passé il, huit étapes pour trouver Maxwell. Ou appelons-le K. Mais rappelons dernier temps, j'ai fait valoir que s'il ya réaliste une longueur maximale d'un mot, comme des personnages quelque 40 impairs, une longueur maximale implique une valeur constante. Alors, vraiment, oui, c'est techniquement grand O de 8 ou 7, ou vraiment grand O de K. Mais si il ya un bouchon fini sur ce K pourrait être, c'est une constante. Et il est donc grand O de 1 à la fin de la journée. 

Pas dans le monde réel. Pas quand vous avez réellement commencer à regarder votre horloge comme le fonctionnement de votre programme. Il est absolument va être un peu plus lent que vraiment constant le temps avec une seule étape. Il va y avoir sept ou huit étapes, mais c'est beaucoup, beaucoup mieux qu'un algorithme comme Big O n que dépend de la taille de ce qui est dans l' la structure de données. 

Remarquez la hausse ici est que nous pouvons insérer plus d'un million de noms dans cette structure de données, mais combien d'autres mesures est ce que ça va nous prendre pour trouver Maxwell dans ce cas? Aucun. Il n'est pas affecté. Et à ce jour, je ne pense pas que nous avons vu un exemple d'une structure de données ou un algorithme qui a été complètement affectée par externe comportements comme ça. Mais cela ne peut pas être étonnant. Cela ne peut pas être la seule solution pour le p-ensemble 

Et ce n'est pas le cas. Ce n'est pas nécessairement les données la structure devrait graviter autour de vous, parce que, comme les tables de hachage, faire des compromis. Quel est le prix que vous payez ici? Mémoire. Je veux dire, c'est une atroce quantité de mémoire. Et vous ne pouvez pas tout voir ici parce que L'auteur de cette image évidemment tronqué tous les tableaux, et nous ne voyons pas beaucoup de A et B et C et Q et Y de et Z de ces matrices. Mais ils sont là. 

Chacun de ces nœuds est un tableau entier d'environ 26 octets ou plus, chacun de qui représente une lettre. 27 dans notre cas, de sorte que nous pouvons soutenir apostrophes dans l'ensemble du problème. Donc, cette structure de données est vraiment, vraiment dense et large. Et cela seul pourrait finir par ralentir les choses, ou au moins vous coûter une beaucoup plus d'espace. Mais encore une fois, nous pouvons tirer comparaisons ici. 

Rappelons ya quelque temps, nous avons réalisé beaucoup temps d'exécution plus excitant dans le tri lorsque nous utilisons le tri par fusion, mais le prix nous avons payé pour atteindre n log n pour fusion Trier nécessaire que nous dépensons plus quelle ressource? Plus d'espace. Nous avions besoin d'un réseau secondaire de copier les gens dans, tout comme nous avons fait ici sur scène. Encore une fois, pas de gagnants, mais juste conception subjective décisions à prendre. 

Très bien. Alors, comment à ce sujet? Toute personne qui reconnaît D-Hall? OK. Donc, trois d'entre nous. Mather House. Il s'agit donc pour la salle de Mather. Je parie que toutes les salles à manger ont piles de plateaux comme celui-ci. Et c'est réellement représentatives de quelque chose que nous avons évidemment déjà vu. Nous l'avons appelé littéralement une pile. Et la pile, en fonction de votre la mémoire de l'ordinateur, est l'endroit où les données va tandis que les fonctions sont appelées. 

Par exemple, quels types de choses vont sur la pile par rapport à l' disposition de la mémoire, nous avons discuté ces dernières semaines? Qu'est-ce que c'est? 

AUDIENCE: appels à des fonctions. 

DAVID MALAN: Je suis désolé. 

AUDIENCE: appels à des fonctions. 

DAVID MALAN: appels à des fonctions, mais Plus précisément, ce qui est à l'intérieur de chacune des ces cadres? Quel genre de choses? Ouais. Donc, les variables locales. Chaque fois que nous avions besoin d'un espace de stockage local, comme un argument, ou int I, ou int temp, ou quelle que soit la locale variable, nous avons été mettre que dans la pile. Et nous appelons cela une pile parce que de cette idée de superposition. Tout genre de matchs avec la réalité, le concept de ceux-ci. 

Mais il s'avère que la pile peut également être considéré comme une structure de données, un alternative à un tableau, une alternative d'une liste chaînée. Quelque chose conceptuellement plus intéressant qui peut être encore implémenté en utilisant soit des personnes choses, mais c'est un autre type de structure de données à l'appui, vraiment, seules deux opérations. Mais vous pouvez ajouter le colombophile fonctionnalités que celles-ci. Mais ce sont les bases - push et pop. 

Et l'idée d'une pile est que si je avoir ici, avec ou sans Annenberg savoir, un plateau d'à côté par le chiffre 9 sur elle. Il suffit donc un int. Et je tiens à pousser ce sur les données structure, qui est actuellement vide. Considérons ce bas de la pile. Je voudrais pousser ce numéro 9 sur le pile, et maintenant il est juste là. 

Mais la chose intéressante à propos d'une pile c'est que si je veux maintenant pousser une autre valeur, comme 17, et je pousse ce sur la pile, je vais le faire la seule chose intuitive, je vais juste pour le mettre là où nous les humains serait enclin à le mettre, sur le dessus. Mais ce qui est intéressant maintenant est, comment puis-je obtenir à 9? Vous savez, je ne suis pas sans un certain effort. 

Donc ce qui est intéressant à propos de une pile, c'est que de par leur conception, c'est une structure de données LIFO. Façon idiote de décrire dernier entré, premier sorti. Donc, le dernier numéro de à cette époque était de 17. Donc, si je veux quelque chose de pop off de la pile, il ne peut être que 17. Donc, il ya une ordonnance de opérations ici, où le dernier élément en doit être le premier à sortir. D'où l'acronyme, LIFO. 

Alors pourquoi cela pourrait-il être utile? Sont leurs contextes dans lesquels vous feriez vouloir une structure de données comme ça? Eh bien, il a certainement été utile à l'intérieur d'un ordinateur. Alors systèmes d'exploitation utilisent clairement cette type de structure de données pour les cheminées. Nous verrons aussi la même idée quand il s'agit de pages Web. Donc, cette semaine et la semaine prochaine et au-delà, et que vous commencez à mettre en œuvre web pages dans un langage appelé HTML, vous pouvez en fait utiliser une structure de données comme ce afin de déterminer si la page est correctement formaté. Parce que nous allons voir toutes les pages Web suivent une sorte de hiérarchie, une échancrure qui, à la fin de la journée, une structure d'arbre sous la hotte. Donc, plus que dans un peu. 

Mais pour l'instant, nous allons proposer pour un moment, comment pourrions-nous nous y prendre représentant ce que la pile est? Permettez-moi de proposer que nous mettons en œuvre une pile avec du code comme ceci. Ainsi, une pile va avoir à l'intérieur de celui-ci deux choses, un tableau, appelés plateaux, juste pour être compatibles avec la démo. Et chacun des éléments de cette matrice va être un type int. Et la capacité est sans doute quoi? Parce que je n'ai pas écrit l' définition complète ici. 

C'est probablement le maximum taille du tableau. Et c'est probablement déclarée comme un dièse définir dans la partie supérieure du dossier, un certain sorte de constante comme le laisse entendre la seule capitalisation. Donc quelque part la capacité est définie que la taille maximale possible. Pendant ce temps, à l'intérieur de la structure de données connue comme une pile, il y aura être un entier vient de connaître simplement que la taille. 

Donc, si je devais représenter ce moment imagée, supposons que cette ensemble boîte noire représente ma pile. A l'intérieur de celui-ci est deux variables. Donc, je vais attirer l' premier comme taille. Et le second, je vais pour dessiner comme un tableau. 

Mais juste pour garder les choses ordonnée, Normalement, je devrais dessiner un tableau comme , mais c'est le genre de belle si nous comparons la réalité, ou correspondre au modèle mental. Alors laissez-moi plutôt dessine le tableau verticalement, ce qui est juste, encore une fois, L'interprétation de l'artiste. Ça n'a pas vraiment d'importance ce que est sous la hotte. Et nous dirons que, par défaut, capacité va être trois. Ce sera donc l'emplacement 0, ce sera emplacement 1, ce sera emplacement 2. 

Si je soudoyer avec une boule de stress, serait Quelqu'un comme pour se lever et courir le embarquer ici juste un instant? OK, vu votre première main. Venez sur place. Très bien. Donc, je crois que c'est Steven. Venez sur place. Très bien. 

Mais supposons maintenant nous revenir en arrière pour la première état du monde où je venez de déclarer une pile, et c'est va avoir une capacité trois. Mais la taille n'a pas encore été déterminée. Plateaux n'a pas encore été déterminée. Alors, quelques questions d'abord. Et permettez-moi de vous donner micro afin que vous puissiez participer plus activement. 

Alors, quelle est à l'intérieur de la taille en ce moment dans le temps si tout ce que j'ai fait, c'est déclaré une pile à une ligne de code? 

STEVEN: Pas beaucoup. 

DAVID MALAN: OK, pas beaucoup. Savons-nous ce qu'il ya à l'intérieur de la taille, savons-nous ce qu'il ya dedans de ce tableau ici? 

STEVEN: Juste code aléatoire, non? Just - 

DAVID MALAN: Ouais, je vais appeler le code, mais aléatoire - 

STEVEN: Things. 

DAVID MALAN: Des choses comme aléatoire 

STEVEN: Bits. 

DAVID MALAN: Bits, pas vrai? Donc, les valeurs d'ordures, non? Alors permutations de 0 et de 1. Les restes d'usages antérieurs de cette mémoire. Et nous ne savons pas vraiment ce que les valeurs sommes, si nous attirons généralement les des points d'interrogation. 

Donc la première chose que nous sommes probablement va vouloir faire ici - et permettez-moi de vous donner ce domaine à l'intérieur de là un nom - plateaux. Que devrions-nous initialiser vraisemblablement taille si nous voulons commencer à utiliser cette pile? 

STEVEN: Plateau est sous 3. 

DAVID MALAN: Donc, OK. Pour être clair, la capacité est déclarée ailleurs que trois. Et c'est ce que j'ai utilisé à allouer le tableau. Taille va se référer à combien de les plateaux sont actuellement sur la pile. 

STEVEN: Zéro. 

DAVID MALAN: Donc, il devrait être de zéro. Alors allez-y, et avec un doigt, dessiner une taille zéro. Très bien. Alors maintenant, ce qui est à l'intérieur de cette ici, nous ne savons pas. Ce sont vraiment juste des valeurs d'ordures. Donc, nous pourrions tirer des points d'interrogation, mais gardons la planche propre pour l'instant parce que ce n'est pas grave ce qui est là. Nous n'avons pas besoin d'initialiser le tableau à rien, parce que si nous savons que la taille de la pile est égale à zéro, eh bien, nous ne devrait pas être regardant quelque chose dans ce tableau de toute façon à ce point dans le temps. 

Supposez maintenant que je pousse le n ° 9 dans la pile. Comment devrions-nous mettre à jour la structure de données à l'intérieur de cette boîte noire? Quelles valeurs faut-il changer? 

STEVEN: Within - la taille? 

DAVID MALAN: OK. Taille devrait devenir quoi? 

STEVEN: Taille serait un. 

DAVID MALAN: OK. Taille devrait donc devenir un. Ainsi, vous pouvez le faire en deux manières. Permettez-moi de vous donner, dès maintenant votre le doigt est une gomme. Très bien. Alors maintenant votre doigt est une brosse. Très bien. Et maintenant, qu'est-ce qui doit changer, évidemment, dans la structure de données? 

STEVEN: Nous allons partir bas jusqu'à 9. 

DAVID MALAN: 9. OK, c'est bon. Donc, ne reste pas d'importance ce qui est en lieu une ou deux parce qu'ils sont valeurs d'ordures, mais il ne faut pas déranger là, à regarder parce que la taille est nous dire que seul le premier élément est en fait légitime. Alors maintenant, je pousse 17 sur la liste. Qu'advient-il de cette image? 

STEVEN: Donc la taille va aller à deux. 

DAVID MALAN: OK. Vous êtes gomme - oops. Vous êtes une gomme. 

STEVEN: Eraser. 

DAVID MALAN: Vous êtes un pinceau. 

STEVEN: Brush. 

DAVID MALAN: OK. Et quoi d'autre? 

STEVEN: Et puis nous - 

DAVID MALAN: Nous avons poussé 17. 

STEVEN: Nous collons 17 au-dessus, donc - 

DAVID MALAN: OK, c'est bon. 

STEVEN: - faire tomber. 

DAVID MALAN: Très bien. Il devient facile. Je ne vais pas vous aider à ce moment. Poussez 22. 

STEVEN: Terminé. Devenir une gomme. Je deviens un pinceau. Et puis je mets 22. 

DAVID MALAN: 22. Excellente. Donc, une fois de plus. Je vais maintenant pousser dans la pile 26. 

STEVEN: Ooh. Oh mon dieu. Vous m'avez vraiment pris au dépourvu. 

DAVID MALAN: Vous ne l'avez pas vu venir? 

STEVEN: Je n'ai pas vu venir. Pourrions-nous la capacité re-départ? 

DAVID MALAN: C'est une bonne question. Donc, nous avons sorte de nous peignons dans un coin ici. Il n'y a vraiment rien de bon sur pour Steven parce que nous avons prévu ce tableau statiquement, pour ainsi dire, à l'intérieur de la structure de données. Et nous avons essentiellement codé en dur qu'il soit de taille trois. Donc, nous ne pouvons pas vraiment le réaffecter. 

Nous pourrions si nous allions revenir, nous redéfinis plateaux d'être un pointeur qui Nous utilisons ensuite malloc à la mémoire de main. Parce que si nous avons la mémoire de le tas via malloc, nous pourrait alors libérer. Mais avant de le libérer, nous pourrions réaffecter un plus gros morceau de la mémoire, mettre à jour le pointeur, et ainsi de suite. Mais pour l'instant, c'est vraiment Le mieux qu'on puisse faire. Push et pop sont probablement va d'avoir à signaler une erreur. 

Ainsi, par exemple, notre mise en œuvre de poussée pourrait retourner un booléen qui précédemment retourné vrai, vrai, vrai. Mais la quatrième fois, il va falloir pour revenir faux, par exemple. Très bien. Très bien fait. Félicitations. Vous avez gagné votre boule de stress aujourd'hui. 

[Applaudissements] 

STEVEN: Je vous remercie. 

DAVID MALAN: Merci. OK, donc ce ne semble pas être beaucoup d'un pas en avant, non? Nous avons décrit cette structure de données. Il a été convaincant, non? Systèmes d'exploitation comme cela. Apparemment, le web peut faire usage de cela, et d'autres applications encore. Mais quelle limitation stupide que nous sommes sauvegarder pour trier de la semaine deux limites où nous avons fixé des tableaux de taille. 

Donc, il ya effectivement un couple de façons nous pourrions résoudre ce problème. Nous pourrions allouer dynamiquement le tableau, pas de coder en dur comme je l'ai fait ici, mais au lieu de re-déclarer ce, juste pour être clair, comme quelque chose comme ça. Int * plateaux, ne pas décider sur encore une capacité. Mais quand je déclare la pile ailleurs dans mon code, je pourrais alors appeler malloc, obtenir l'adresse d'un morceau de mémoire, et je ne pouvais assigner cette adresse à plateaux. 

Et puis, parce que c'est juste un morceau de mémoire, je pourrais continuer à utiliser carré Unité de support de la manière habituelle. Parce qu'encore une fois, il ya une sorte de ce équivalent fonctionnel de tableaux et morceaux de mémoire qui viennent retour de malloc. Nous pouvons traiter un comme l'autre en utilisant l'arithmétique de pointeur ou notation entre crochets. Donc, c'est une approche. 

Mais comment pourrions-nous mettre en œuvre cette même structure de données, potentiellement? Droite? Je me sens comme nous venons de régler cette problème comme il ya une semaine. Quelle était la solution à ce problème que Steven a couru en? Alors listes liées, à droite. 

Si le problème est que nous sommes en peinture nous dans un coin en allouant à l'avance trop peu de mémoire que nous puis avoir à traiter avec quelque sorte, eh bien, pourquoi ne pas simplement éviter que question tout à fait? Pourquoi ne pas simplement déclarer plateaux d'être un pointeur vers un noeud, ergo une liste chaînée, et puis tout simplement attribuer de nouveaux nœuds chaque fois que Steven nécessaire pour s'adapter à un nombre dans la structure de données. 

Donc, l'image aurait à changer. Ça ne va pas être aussi propre et aussi simple que un tableau de trois entiers. Maintenant, il va y avoir un pointeur vers une struct, et que struct va avoir un int et un pointeur prochaine. Il va conduire via ce pointeur à une autre structure d' une autre telle structure. Donc, l'image serait effectivement obtenir un peu malpropre. Et nous aurions flèches attachant tout ensemble. 

Mais c'est bien, non, parce que nous avons vu comment faire cela. Et une fois que vous obtenez à l'aise quelque chose comme une mise en œuvre liée liste, que vous avez à faire si vous choisir d'appliquer une table de hachage avec chaînage séparé pour p-set 6, vous pouvez utiliser en tant que bloc de construction, ou une ingrédient, ou dans Scratch parler, un procédure, quelque chose que vous mettez, vous créé votre propre morceau de puzzle que vous pourrez ensuite réutiliser. Compromis ainsi, mais les solutions possibles que nous avons effectivement vu auparavant. 

Donc, très souvent, vous voyez cela tous an ou deux, lorsque les rejets d'Apple quelque chose de nouveau, et tous les gens fous line up à l'extérieur de la Pomme Store pour acheter leur marginal moderniser le matériel. Je dis cela, c'est OK, parce que Je suis une de ces personnes. Alors, quel genre de structure de données pourrait représenter cette réalité? 

Eh bien, appelons-le une file d'attente, une ligne. So British dirais que c'est typiquement une file d'attente de toute façon, c'est un joli nom. Et les deux opérations qu'une file d'attente prendra en charge que nous appellerons une enqueue opération et une opération dequeue, qui sont similaires dans esprit de push et pop. C'est juste une sorte de différent dans convention, ce que nous appelons ces derniers. Mais pour en file d'attente signifie quelque chose à ajouter ou insérer dans la structure de données. Pour dequeue signifie pour le supprimer. Mais alors que la pile était une des données LIFO la structure, une file d'attente est dans une première, d'abord sur la structure de données. 

Si vous êtes la première personne en ligne, vous serez la première personne à obtenir hors de la ligne et acheter votre nouvel appareil. Imaginez comment bouleversé ces personnes seraient si Apple a plutôt utilisé une pile, pour Ainsi, pour mettre en œuvre la cueillette de votre nouveau jouet. Donc, les files d'attente de sens, certes, et nous pouvons penser à toutes sortes de applications, sans doute, des files d'attente, surtout quand vous voulez l'équité. Alors, comment pouvons-nous mettre en œuvre ces en tant que structure de données? 

Eh bien, je propose que nous pourrions besoin de le faire de cette façon. Donc, je vais devoir maintenant nombres. Donc, nous allons rester simple et ne parler nécessairement en termes de plateaux. Seulement des chiffres que les gens de acquis. Capacité va, encore une fois, fixer le nombre total de personnes qui peuvent être en cette ligne, comme trois ou toute autre valeur. 

Mais je propose que j'ai besoin de garder une trace non seulement de la taille de l' file d'attente, combien de choses sont en elle. Donc, la taille est la taille actuelle, la capacité est la taille maximale. Juste encore une fois, nomenclature par convention. Pourquoi ai-je besoin d'un int supplémentaire à l'intérieur d'une file d'attente pour garder trace de qui est dans avant de la ligne? Pourquoi dois-je faire dans ce cas? 

Eh bien, comment est cette image va changer? Je peux probablement réutiliser plus de cette image. Permettez-moi d'aller de l'avant et d'effacer ce qu'il ya ici. Nous allons donner à cette légèrement nom différent ici. Débarrassons-nous du 17 Débarrassons du 9, débarrassons-nous de la 3. Et nous allons ajouter une autre chose. Je propose que j'ai besoin de garder une trace de l'avant de la liste, ce qui est juste va être un int ainsi. Et nous allons garder les choses simples. Aucune liste liée pour l'instant. 

Nous admettons que nous allons heurter à cette limite. Mais qu'est-ce que je veux voir se passer cette fois? Donc je suppose aller de l'avant et le premier personne vient en ligne, et c'est le numéro 9. Nous avons balles anti-stress. Puis-je voler, disons, deux ou trois personnes? Un, deux, trois? Venez sur place. Dès l'avant, parce que nous ferons celui-rapide. 

Chacun d'entre vous va maintenant être un garçon de ventilateur en ligne chez Apple. Vous ne recevrez pas de matériel Apple à la fin de ce bien. Très bien. Donc, vous êtes numéro 9, vous êtes numéro 17, numéro 22. Ces chiffres sont arbitraires, comme ID étudiant ou autres joyeusetés. Et dans quelques instants, nous allons commencer pour commencer à ajouter des choses. Et je vais courir le conseil ici ce temps. 

Donc dans ce cas, j'ai initialisé l'avant pour être - En fait, je ne m'inquiète pas vraiment ce que l' avant est, en raison de la taille est égale à zéro. Donc, cela pourrait tout aussi bien être un point d'interrogation. Ce sont tous des points d'interrogation. Alors maintenant, nous allons commencer à réellement voir personnes faisaient la queue à la boutique. 

Donc, si le numéro 9, vous êtes le premier là à 5 heures, aller de l'avant et la queue, ou la veille. OK. Alors maintenant 9 est ici. Ainsi, la figure 9 est à l'avant de la liste. Donc, je vais aller de l'avant et mettre à jour la taille de ces données actuelles Structure de ne pas être plus 0, mais pour être 1. Je vais mettre 9 à l' début de la liste. Permettez-moi d'aller de l'avant et basculer l'écran afin que nous puissions voir devant nous ici. 

Et maintenant, qu'est-ce que je veux de mettre à l'avant? Je vais garder la trace que l' avant de la file d'attente en ce moment est à l'emplacement 0. Parce que ce qui est à côté va se passer? Eh bien, maintenant, je suppose ENQUEUE 17 aussi. Embarquez en ligne là-bas. Et encore, le type de porte à l' magasin va être ici. Alors maintenant, j'ai ajouté 17. Et même si ces gars-là sont de blocage l'écran, c'est OK, parce que nous pouvons le voir ici. Désolé. 

PUBLIC: Nous pouvons passer - 

DAVID MALAN: Non, ce n'est pas grave. C'est énorme là-haut. Donc 17 est maintenant à l'intérieur de la file d'attente. J'ai besoin de mettre à jour qui domaines maintenant bien? OK, certainement taille. Et que diriez-vous avant? OK, no. Avant ne doit pas changer, parce que Contrairement à une pile, nous vouloir maintenir l'équité. Donc, si 9 est venu en premier, nous voulons 9 d'être le premier sur la ligne et dans le magasin. 

En fait, nous allons voir cela. Avant de nous insérons 22, nous allons aller de l'avant et dequeue 9. Quel est votre nom? 

AUDIENCE: Jake. 

DAVID MALAN: Jake va être retirés lors maintenant. Ainsi, vous obtenez de marcher dans le magasin. Et prétendre que le magasin est là-bas. Alors maintenant, ce qu'il faut - dit-dit-dit! Que faut-il maintenant? décision de conception. Donc pas un mauvais instinct, mais - quel est votre nom? 

AUDIENCE: David. 

DAVID MALAN: David. Alors, que fait David? Il essayait de tri de fixer les données structure et déménagement de son emplacement dans l'ancien emplacement de Jake. Et c'est très bien si nous sommes prêts à accepter cela comme une détail d'implémentation. Mais d'abord, nous allons mettre à jour les données Structure avant de faire cela. Parce que je ne suis pas aimer l'idée de tout les gens passer dans cette ligne. 

Ce n'est pas un gros problème si David fait avec une étape, mais encore une fois, pensez à lorsque nous avons eu huit volontaires sur le stade et nous avons fait comme insertion Trier, où nous devions commencer déplacer tout le monde autour. Cela m'a cher, non? Cela me fait grincer des dents sur grand O de N, O grand carré de n fois. Il ne se sent pas comme un résultat idéal. 

Donc, nous allons simplement mettre à jour ce sujet. Ainsi, la taille de la file d'attente n'est plus 2. C'est maintenant simplement 1. Mais je peux maintenant mettre à jour quelque chose Je n'ai pas mis à jour avant le début de la liste. Je ne pouvais tout simplement dire, c'est que 1 emplacement? Nous avons donc maintenant la valeur des ordures ici, valeur des ordures ici, et David dans le milieu de ces ordures. Mais la structure de données est encore intacte. 

Et en fait, je n'ai même pas besoin d' changer ancien numéro de Jake 9, car qui se soucie. J'ai maintenant suffisamment d'informations dans le taille que je sais qu'il ya une personne dans cette file d'attente. Et je sais que cette personne est à l'emplacement 1, et non 0. Je ne compte pas. Donc 1 ainsi. Ainsi, la structure de données est toujours OK. 

Eh bien, qu'est-ce qui se passe ensuite? Le enqueue Let - Quel est votre nom? 

AUDIENCE: Callen. 

DAVID MALAN: Callen. Allons ENQUEUE un Callen, et 22 est maintenant dans la file d'attente. Alors maintenant, ce qui doit changer ici? Avant ne va pas changer, évidemment. Taille va changer à 2 fois. Et 22 finit ici, 9 est toujours présent, mais c'est effectivement un valeur des ordures maintenant. C'est juste un vestige de Jake passé. 

Alors maintenant ce qui se passe si Je DEQUEUE David? Une dernière opération, dequeue David. Nous pourrions passer, mais je proposer LET'S faire le moins de travail possible. Maintenant, ma structure de données va sauvegarder la taille varie de 2 à 1. Mais l'avant de la file d'attente devient maintenant 2. Je n'ai pas besoin de modifier ces numéros pour l'instant, parce qu'ils sont seulement des valeurs parasites. 

Mais maintenant ce qui se passe? Supposons que je me ENQUEUE, 26? Je me sens chez moi ici. Je suis donc d'être en file d'attente. Donc je sorte de ma place ici. Et même si vous n'avez pas tout à fait apprécier cette visuellement sur la scène, parce que nous avons beaucoup de place, je devrais pas être ici, pourquoi? 

AUDIENCE: Vous êtes hors des limites. 

DAVID MALAN: C'est vrai. Je suis hors des limites. J'ai indexés au-delà de la des bornes de ce tableau. Je devrais être dans l'un des trois emplacements possibles. Maintenant, où est plus naturel d'aller? Je propose que nous à effet de levier une semaine un tour. L'opérateur mod, pourcentage. Parce que je suis techniquement debout à emplacement 3, mais je ne 3 capacité de mod, SO 3, un signe pour cent, 3 - capacité est 3. Qu'est-ce que c'est? Quel est le reste quand vous divisez 3 par 3? 0. 

Alors, qui me met été Jake était, ce qui est réellement bon. Alors maintenant, la mise en œuvre de cette chose va être un peu mal à la tête. C'est vraiment juste une ligne des maux de tête, de code. Mais au moins, maintenant, il ya des ordures valeur ici, mais il ya deux ints légitimes ici. Et je prétends que, maintenant que nous avons fait exactement ce que nous devons faire, aussi longtemps que nous changeons ce que Jake valeur était à 26. 

Nous avons maintenant suffisamment d'informations encore pour maintenir l'intégrité de cette structure de données. Nous sommes encore un peu de chance lorsque nous vouloir insérer quatre ou plus totale éléments, mais je peux au moins faire assez utilisation efficace de cette constante temps, en fait. Je n'ai pas à vous soucier de déplacement tout le monde, comme l'inclinaison de David était. 

Toutes les questions sur piles, ou cette file d'attente? 

AUDIENCE: Est-ce la raison pour laquelle vous avez besoin de taille afin que vous sachiez où d'avoir une personne? 

DAVID MALAN: Exactement. J'ai besoin de connaître la taille du tableau parce que j'ai besoin de savoir exactement comment nombre de ces valeurs sont légitimes, et pour que je puisse trouver où mettre la personne suivante. Exactement. La taille est - en fait, nous n'avons pas à jour ce moment. J'ai ajouté à 26. La taille est maintenant, pas 1, mais 2. Alors maintenant, c'est bien m'aide à trouver l' tête de la liste, qui n'est pas 0, pas 1, mais est égal à 2. La façade de la liste est en effet le numéro 22. Parce qu'il est venu en premier, alors il devrait être autorisés à entrer dans le magasin avant moi, même si visuellement je suis debout plus près du magasin. 

Tout va bien? Une salve d'applaudissements pour ces gars-là et nous allons leur faire sortir de là. 

[Applaudissements] 

DAVID MALAN: Je pourrais laisser vous gardez le plateau. Nous avons pu voir ce qui se passe si vous voulez, mais peut-être pas. Très bien. Alors quoi cela nous mène? Eh bien, permettez-moi de proposer qu'il y ait une Quelques autres structures de données que nous pourrions commencer à ajouter à notre trousse d'outils qui seront effectivement être tout à fait, tout à fait pertinent que nous plongeons dans des trucs web. Qui encore une fois, a une sorte de connexion d'arbres dans la forme de quelque chose qui s'appelle DOM, un document modèle d'objet. Mais nous verrons plus de que d'ici peu. 

Permettez-moi de proposer par définition que nous appeler arbre maintenant ce que vous savez peut-être que plus d'un arbre de la famille, où vous avoir un ancêtre à l' racines de l'arbre. Une matriarche patriarcale ou au Tout en haut de l'arbre. Sans leur conjoint, dans ce cas. Mais nous avons maintenant ce que nous appellerons enfants, qui sont les nœuds qui pendent hors l'enfant vers la gauche ou la droite enfant, flèches comme représenté ici. 

En d'autres termes, dans une structure de données d'arbre en informatique, un arbre a zéro ou plusieurs nœuds. Si elle a au moins un noeud, C'est ce qu'on appelle la racine. Ce sont les choses visuellement que nous tirons vers le haut. Et ce nœud, comme n'importe quel autre nœud, peut avoir zéro, un, ou deux, ou trois, Cependant beaucoup d'enfants ou le Structure de données prend en charge. Dans ce cas, la racine, stockant l' une valeur, a deux enfants, 2 et 3, de sorte que nous appelons généralement 2 à gauche enfant et le droit de l'enfant 3. 

Et puis, quand nous nous attelons à 5, 6, et 7, 6 pourrait appeler l'enfant du milieu. Si vous avez quatre enfants, il devient confus. Donc, nous cessons d'utiliser ce genre de raccourci verbalement. Mais c'est vraiment juste un arbre généalogique. Et les feuilles sont ici les nœuds eux-mêmes n'ont pas d'enfants. Ils pendent vers le bas de l'arbre. 

Alors, comment pouvons-nous mettre en œuvre un arbre a seulement deux enfants au maximum? Nous appelons cela un arbre binaire. Bi à nouveau deux sens, en ce cas, comme avec binaire. Et donc il peut avoir zéro, un, ou deux enfants au maximum. 

Je propose que nous mettons en œuvre le noeud pour cette structure avec un int n, puis deux pointeurs, l'un appelé à gauche, l'un appelé droit. Mais ce sont juste agréable conventions arbitraires. Et ce qui est bien maintenant, surtout si vous sorte de se débattait avec conceptuellement récursivité, ou pensait que ce n'était pas vraiment une solution à quoi que ce soit, surtout si vous pouviez à court de mémoire. Maintenant que nous parlons de données des structures et des algorithmes qui permettent nous traversons et les manipuler, s'avère que la récursivité revient dans beaucoup plus convaincant si elle n'est pas belle façon. 

Donc, ce que je propose est la mise en œuvre d'une fonction de recherche. Étant donné deux entrées - Alors, pensez à cela comme une boîte noire. Étant donné deux entrées, n, un int, et un pointeur sur un arbre, un pointeur vers une noeud, ou vraiment la racine d'un arbre, je prétendent que cette fonction peut renvoyer vrai ou faux, cette valeur n est à l'intérieur de cet arbre. 

À l'intérieur de cette boîte noire? Eh bien, quatre branches. La première vient des chèques. Si l'arbre est nulle, il suffit de retourner faux. S'il n'y a pas de noeud, il n'ya pas de n, il n'y a pas de numéro, juste return false. Si bien que, n, la valeur que vous cherchez pour, est inférieure à arbre flèche n, et juste pour être clair, qu'est-ce que cela veut dire quand J'écris arbre, puis sur la flèche notation, n? Exactement. Cela signifie que déréférencer pointeur appelé arbre. Allez-y, puis pénétrer à l'intérieur de cette nœud et obtenir son champ appelé n. Et puis comparer le n réel qui a été passé dans Recherche contre elle. 

Donc, si n est inférieur à la valeur n dans le nœud de l'arbre lui-même, eh bien, ça veut dire quoi? Cela ne veut rien dire à première vue. Droite? Tout comme lorsque vous avez un tableau d' valeurs, vous aimerez certainement appliquer binaire rechercher une forme de fracture et conquérir. Mais ce postulat avons-nous besoin de faire pour la recherche binaire de travailler à tous dans le livre de téléphone et exemples précédents? 

Comment faire pour être triés. Donc, nous allons préciser la définition de l'arbre ici pas être juste un arbre, ce qui peut avoir n'importe quel nombre d'enfants. Pas seulement un arbre binaire, qui peut a 0, 1 ou 2 au maximum. Mais, comme un arbre binaire de recherche, ou BST, qui est juste une façon élégante de dire une arbre binaire de telle sorte que chaque noeud de enfant gauche, s'il est présent, est inférieur au noeud. Et chaque enfant le droit de nœud, s'il est présent, est supérieure que le nœud lui-même. 

Donc, en d'autres termes, si vous deviez dessiner l'arbre out, tous les numéros sont soigneusement équilibré comme celui-ci de sorte que si vous avez 55 comme la racine, 33 peut aller à sa gauche parce que c'est moins de 55 ans. 77 peut aller à son droit parce que elle est supérieure à 55. Mais remarquez maintenant, la même définition, c'est une définition récursive verbalement, doit demander 33. Enfant de gauche de 33 doit être inférieure à lui, et à droite enfant de 33, 44, doit être plus grande que lui. 

Donc, c'est un arbre binaire de recherche, et Je propose, en utilisant un peu de récursivité, nous pouvons maintenant trouver n. Donc, si n est inférieur à la valeur n qui est noeud courant, je vais aller avant et plate, pour ainsi dire, et juste retourner quelle que soit la réponse est recherche de n sur le enfant de gauche de l'arbre. Notez à nouveau, cette fonction seulement s'attend à une étoile nœud, un pointeur à un noeud. Alors certes, je peux juste faire arbre flèche gauche, ce qui conduira moi vers un autre nœud. Mais quel est ce nœud? 

Eh bien, selon cette déclaration, gauche est juste un pointeur, de telle sorte que juste veut dire que je suis de passage à la fonction de recherche un pointeur différent, à savoir celui qui représente l'arbre de mon fils gauche. Donc dans ce cas, le pointeur à 33, si c'est notre échantillon d'entrée attendant, si n est supérieur à la valeur de n à l' nœud actuel dans l'arborescence, puis je suis aller de l'avant et botté de dégagement dans l'autre direction et juste dire, je n'aime pas savoir si cette valeur n est compris dans l'arbre, mais je sais pas si c'est le cas, c'est en bas de mon branche droite, pour ainsi dire. Alors permettez-moi j'appelle effectuer des recherches récursives, le passage d'un n fois, mais en passant dans un pointeur à mon enfant droite. 

En d'autres termes, si je suis actuellement à 55 et je suis à la recherche de 99, je sais que 99 est supérieur à 55, donc comme j'ai déchiré Il ya le téléphone semaines de livres et nous s'est bien passé, même sommes-nous va aller ici. Et je ne sais pas si c'est à ma droite enfant, et ce n'est pas, 77 est là, mais Je sais que c'est dans cette direction. J'appelle donc la recherche de mon enfant droite, 77, et laisser chiffre de recherche à partir il si 99 dans ce arbitraire exemple est vraiment là. 

Sinon, ce qui est le cas final? Si l'arbre est nulle est un cas. Si n est inférieur au noeud de courant de valeur est une autre affaire. Si n est supérieur à l'actuel La valeur de noeud est un troisième cas. Quel est le quatrième et dernier cas? Je pense que nous sommes hors des cas, non? Il faut que n est dans l' noeud courant que je suis sur. 

Donc, si je suis à la recherche de 55 à ce stade dans l'histoire, cette branche de l' arbre reviendrait vrai. Donc ce qui est intéressant ici, c'est que nous en fait, à la différence semaines passées, nous avons nature d'avoir deux cas de base. Et ils n'ont pas à être tout en haut. Le dessus est un cas de base, parce que si l' arbre est nul, il n'y a rien à faire. Il suffit de retourner un disque codé la valeur false. 

La branche inférieure est en quelque sorte le défaut, selon laquelle, si nous avons vérifié null, nous avons vérifié si elle doit être à gauche, mais il ne devrait pas être, nous avons vérifié si elle doit être juste, mais il ne devrait pas être, clairement, il doit être là où nous sommes. C'est un cas de base. Donc, il ya deux cas récursifs il pris en sandwich au milieu. Mais j'aurais pu écrire ce dans n'importe quel ordre. Je pensais que ça sorte de feutre naturel vérifier d'abord d'une erreur possible, puis vérifiez gauche, puis cochez à droite, puis supposons que vous êtes au niveau du noeud vous êtes réellement à la recherche d'. 

Alors pourquoi cela pourrait-il être utile? Ainsi, il s'avère - et permettez-moi de passer à un teaser ici c'est sur le web. Nous allons commencer à l'utiliser pas une langage de programmation au début, mais une langage de balisage. Un langage de balisage étant celui qui est dans le même esprit à la programmation langue, mais il ne vous donne pas l' capacité à vous exprimer logiquement. Il vous donne seulement la possibilité d' exprimez-vous structurellement. 

Où voulez-vous mettre quelque chose sur la page, la page Web? De quelle couleur voulez-vous faire? Quelle est la taille de la police voulez-vous faire? Quels mots vous font réellement voulez sur la page web? C'est donc un langage de balisage. Mais ensuite, nous allons présenter très rapidement JavaScript, qui est un à part entière le langage de programmation. Très similaire en apparence syntaxiquement à C, mais il va falloir un certain beau, plus puissant, plus fonctions conviviales. 

Et l'une des frustrations à cet point dans le semestre, c'est que nous allons Dès la mise en œuvre Speller en beaucoup moins lignes de code en utilisant d'autres langues C que lui-même permet, mais pour des raisons de nous allons bientôt comprendre. Ce sera le premier de ces page web. Il sera complètement décevante, le premier que nous faisons. Il sera tout simplement dire bonjour monde. Mais si vous ne l'avez jamais vu avant, c'est HTML, HyperText Markup Language. 

Si vous allez à une certaine option de menu en la plupart de n'importe quel navigateur, sur n'importe quelle page web sur l'Internet, vous pouvez voir le HTML que certaines personnes ont écrit à créer cette page web. Et il n'a probablement pas aussi bref ou aussi nette que cela. Mais il suivra le modèle de ceux-ci parenthèses ouvertes et les barres obliques et lettres et potentiellement chiffres. 

Je pensais que je vous donne un teaser de ce que vous serez en mesure de faire après avoir pris CS50. Permettez-moi de passer à cs.harvard.edu / rob, la page de notre propre Rob Bowden. Il a fait cela pour nous. Ainsi, vous serez bientôt en mesure de le faire. Et aussi, ce que vous avez entendu ce matin - ce que vous avez entendu ce matin - 

[HAMSTER DANCE MUSIC] 

- Vous aurez être capable de faire cela. Qui nous attend mercredi. Nous vous verrons ensuite. 

[HAMSTER DANCE MUSIC] DAVID MALAN: À la prochaine CS50 -