[Jouer de la musique] ANDI PENG: Bienvenue à la semaine 6 de l'article. Nous dévié de notre norme section du temps du mardi après-midi pour ce beau dimanche matin. Merci pour tout le monde que joint à moi aujourd'hui, mais sérieusement, une salve d'applaudissements. Voilà un joli gros effort. Je failli ne même pas se rendre dans le temps, mais il a été OK. Donc, je sais que vous tous ont simplement rendu au quiz. Tout d'abord, bienvenue à le revers de la médaille. Deuxièmement, nous en reparlerons. Nous parlerons du quiz. Nous allons parler de la façon dont vous faites dans la classe. Ça ira. Je dois vos quiz pour vous à la fin d'ici, Donc, si vous voulez les gars à prendre un regard sur elle, tout à fait bien. Si vite avant que nous commencions, le l'ordre du jour d'aujourd'hui est comme suit. Comme vous pouvez le voir, nous sommes tir essentiellement rapide grâce à tout un tas de structures de données vraiment, vraiment, vraiment vite. Donc, à ce titre, il ne sera pas aujourd'hui super-interactive. Il va juste être moi sorte de crier choses que vous, et si je vous confondre, si je vais trop vite, faites le moi savoir. Ils sont juste différentes données structures, et dans le cadre de votre pset pour cette semaine prochaine, vous aurez être invité à mettre en œuvre l'un d'eux, peut-être deux des eux-- deux d'entre eux dans votre pset. OK, donc je vais juste commencer avec quelques annonces. Nous irons au-dessus des piles et des files d'attente plus dans profondeur que ce que nous avons fait avant le quiz. Nous allons passer en revue liés la liste de nouveau, une fois de plus, plus en profondeur que ce que nous avions avant le quiz. Et puis nous allons parler de hachage tables, arbres et essais, qui sont tous très nécessaire pour votre pset. Et puis nous allons passer en revue certaines conseils utiles pour pset5. OK, donc quizz 0. La moyenne était de 58%. Il était très faible, et tout ce que vous les gars a très, très bien en conformité avec ça. Pretty much, règle de base est que si vous êtes l'intérieur d'un écart-type de la moyenne surtout depuis que nous sommes dans un moins section confortable, vous êtes tout à fait bien. Vous êtes sur la bonne voie. La vie est belle. Je sais qu'il est effrayant de penser que Je suis comme un 40% sur ce quiz. Je vais à l'échec cette classe. Je vous promets, vous n'êtes pas aller à l'échec de la classe. Vous êtes tout à fait bien. Pour ceux d'entre vous qui a obtenu plus de la moyenne, impressionnante, impressionnante, comme, bien fait au sérieux. Je les ai avec moi. Sentez-vous libre de venir les faire à la fin de l'article. Faites-moi savoir si vous avez une questions, des questions avec eux. Si nous ajoutons votre score mal, laissez-nous savoir. OK, donc pset5, cela est vraiment semaine bizarre pour Yale dans le sens que notre pset est dû Mercredi à midi, y compris la fin du jour, il est donc en fait théoriquement dû mardi à midi. Probablement personne ne terminé Mardi à midi. Voilà tout à fait bien. Nous allons avoir des heures de bureau ce soir, ainsi que lundi soir. Et toutes les sections cette semaine effectivement être transformée en ateliers, donc sentir libre de pop une section que vous voulez, et ils seront sorte de mini-pset ateliers d'aide à ce sujet. Donc, en tant que telle, cette section est le seul où nous sommes matériel pédagogique. Toutes les autres sections se concentreront exclusivement sur l'aide pour le pset. Ouais? AUDIENCE: Où sont les heures de bureau? ANDI PENG: heures de bureau de ce soir Oh, bonne question. Je pense que les heures de bureau ce soir sont en Teal ou communes. Si vous cochez ligne CS50 et vous allez à des heures de bureau, il devrait y avoir un calendrier qui vous où ils sont tous dit. Je sais que ce soir soit ou demain est sarcelle d'hiver, et je pense que nous pouvons avoir communes pour l'autre soir. Je ne suis pas sûr. Bonne question. Vérifiez sur CS50. Cool, des questions concernant le calendrier pour la prochaine comme trois jours? Je vous promets que des gars comme David dit, ceci est le sommet de la colline. Les gars, vous y êtes presque. Seulement trois jours de plus. Allez-y, puis nous allons tous descendre. Nous aurons une pause agréable CS-libre. Nous y reviendrons. Nous allons plonger dans web la programmation et le développement, des choses qui sont très amusant comparés pour d'autres psets. Et ça va être froid, et nous aurons beaucoup de plaisir. Nous aurons plus de bonbons. Désolé pour les bonbons. Je oublié bonbons. Ce fut une matinée difficile. Alors vous les gars y êtes presque, et je suis vraiment fier de vous les gars. OK, donc piles. Qui aimait la question à propos de Jack et son vêtement sur le quiz? Personne? OK, c'est bon. Donc, essentiellement, que vous le pouvez Image Jack, ce gars-là, aime prendre les vêtements sur le dessus de la pile, et il la remet sur la pile après qu'il a fait. Donc, de cette manière, il n'a jamais semble se au fond de la empiler dans ses vêtements. Donc, ce genre de décrit la structure de base de données de la manière dont est mis en oeuvre d'une pile. Essentiellement, penser à un empiler comme toute pile d'objets où vous mettez les choses sur le dessus, et puis vous sautez les sortir par le haut. Donc LIFO est l'acronyme nous aimons à use-- Last In, First Out. Et ainsi de durer dans le haut de la pile est le premier qui sort. Et ainsi les deux termes nous aimons associer avec ce que l'on appelle poussée et pop. Quand vous poussez quelque chose sur le pile, et vous sautez le sauvegarder. Et donc je suppose que cela est une sorte de concept abstrait pour ceux d'entre vous qui veulent voir comme un mise en œuvre effective de cette dans le monde réel. Combien d'entre vous ont écrit un essai peut-être comme une heure avant l'échéance, et vous avez accidentellement supprimé un énorme morceau de celui-ci, comme par hasard? Et puis ce contrôle ne que nous utilisons pour le remettre? Ctrl-Z, ouais? Ctrl-Z, de sorte que le nombre de fois que Control-Z a sauvé ma vie, a sauvé mon cul, à chaque fois qui est implémenté par une cheminée. Essentiellement toutes les informations qui est sur votre document Word, il est poussé et a sauté à volonté. Et si essentiellement chaque fois que vous supprimer quoi que ce soit, vous sautez le sauvegarder. Et puis si vous avez besoin de retour, vous pousser, ce qui est ce que Control-C fait. Et si la fonction du monde réel de la structure de données comment simple peut vous aider avec votre vie quotidienne. Donc, une structure est la façon dont nous créons en fait une pile. Nous tapons définir struct, puis nous l'appelons pile au fond. Et au sein de la pile, nous avons deux paramètres que nous pouvons essentiellement manipuler, nous avons donc omble capacité cordes étoiles. Tout ce qu'il fait est la création d'un tableau que nous pouvons stocker ce que vous voulez que nous pouvons déterminer sa capacité. Capacité est juste le montant maximum de articles que nous pouvons mettre dans ce tableau. int size est le compteur qui maintient la trace de la façon dont de nombreux éléments sont actuellement dans la pile. Alors nous pouvons suivre, A, à la fois la taille de la pile est réelle, et, B, combien de cette pile nous avons rempli parce que nous ne voulons pas à déborder sur ce que notre capacité est. Ainsi, par exemple, cette belle question était sur votre quiz. Essentiellement, comment pouvons-nous poussons sur le dessus d'une pile. Assez simple. Si vous regardez, nous marcherons à travers cela. Si [inaudible] size-- rappelez-vous, chaque fois que vous vouloir accéder à tout paramètre dans une structure, vous faites le nom de la struct.parameter. Dans ce cas, s est le nom de notre pile. Nous voulons accéder à la taille de celui-ci, de sorte que nous faisons s.size. Donc, tant que la taille est pas égal à la capacité ou aussi longtemps comme il est inférieure à la capacité, soit serait travailler ici. Vous voulez accéder à l'intérieur de votre pile, donc s.strings, et vous allez mettre ce nouveau numéro que vous souhaitez insérer dans il. Disons simplement que nous voudrons insérer int n sur la pile, nous pourrions faire s.strings, crochets, s.size équivaut n. Parce que la taille est où nous sont actuellement dans la pile si nous allons pousser sur, nous accédons à juste où la taille est, la plénitude courant de la pile, et nous poussons l'int n sur elle. Et puis, nous voulons faire en sorte que nous sommes également incrémenter taille de la n, afin que nous puissions garder une trace de nous avons ajouté une chose supplémentaire à la pile. Maintenant, nous avons une plus grande taille. Est-ce ici de sens pour tout le monde, comment logiquement ça marche? Il était une sorte de rapide. AUDIENCE: Pouvez-vous revenir sur les s.stringss.strings [s.size] à nouveau? ANDI PENG: Bien sûr, si ce que fait s.size actuellement nous donner? PUBLIC: Il est la taille actuelle. ANDI PENG: Exactement, de sorte que le index courant que notre taille est à, et donc nous voulons mettre le nouvel entier que nous voulons insérer dans s.size. Cela a-t-il du sens? Parce s.strings, tout ce qui est est le nom du tableau. Tout ce qu'il est est l'accès à la réseau au sein de notre structure, et si nous voulons n placer dans cet indice, nous ne pouvons y accéder à l'aide de crochets s.size. Frais. Tout droit, pop, je Pseudocode it out pour vous les gars, mais concept similaire. Cela a-t-il du sens? Si la taille est supérieure à zéro, alors vous savez que vous voulez prendre quelque chose parce que si la taille est pas supérieur à zéro, alors vous rien avoir dans la pile. Donc, vous voulez seulement exécuter ce code, il ne peut pop si il ya quelque chose à la musique pop. Donc, si la taille est plus grande à 0, nous moins la taille. Nous décrémentons la taille et ensuite revenir tout ce qui est à l'intérieur de celui-ci, car en faisant éclater, nous voulons accès tout ce qui est stocké l'indice du sommet de la pile. Tout a un sens? Si je vous ai fait les gars écrivez ceci, feriez-vous les gars être capable de l'écrire? OK, les gars vous pouvez jouer avec elle. Pas de soucis si vous ne l'obtiennent pas. Nous ne disposons pas des temps de coder il aujourd'hui parce que nous avons a obtenu un grand nombre de ces structures à passer, mais essentiellement pseudo, très, très semblable à pousser. Il suffit de suivre le long de la logique. Assurez-vous d'accéder à toutes les caractéristiques de votre struct correctement. Ouais? AUDIENCE: Will ces diapositives et tout cela soit aujourd'hui à la rigueur? ANDI PENG: Toujours, oui. Je vais essayer de mettre cette place comme une heure après. Je vais écrivez-David, David va essayer de mettre en place comme une heure après cela. OK, alors nous entrons dans cette autre belle structure de données appelée une file d'attente. Comme vous les gars pouvez le voir ici, un file d'attente, pour les Britanniques parmi nous, tout ce qu'il est est une ligne. Donc, contrairement à ce que vous pensez est une pile, une file d'attente est exactement ce que logiquement vous pensez qu'il est. Il est tenu par les règles de FIFO, qui est First In, First Out. Si vous êtes le premier l'un dans la ligne, vous êtes le premier qui qui sort de la ligne. Donc, ce que nous aimons appeler cette est dequeueing et enqueueing. Si nous voulons ajouter quelque chose à notre attente, nous ENQUEUE. Si nous voulons dequeue, ou de prendre quelque chose, nous DEQUEUE. Alors même sens que nous sommes en quelque sorte la création d'éléments de taille fixe que nous peut stocker certaines les choses, mais nous pouvons aussi changer l'endroit où nous allons placer les paramètres à l'intérieur de sur la base de ce type de fonctionnalité que nous voulons. Donc, piles, nous voulions le dernier l'un, N pour être le premier à sortir. File d'attente est que nous voulons la première chose pour être la première chose sur. Ainsi, le type de structure définir, comme vous pouvez le voir, il est un peu différent de ce que la pile était parce que non seulement nous avons à garder trace d'où la taille est actuellement, nous voulons aussi garder une trace de la tête ainsi que là où nous sommes actuellement. Donc, je pense qu'il est plus facile si je tire cette place. Donc, imaginons que nous avons une file d'attente, alors disons la tête est ici. La tête de la ligne, nous allons juste dire que ce moment là, et nous voulons insérer quelque chose dans la file d'attente. Je vais appeler la taille essentiellement est la même chose que la queue, la fin de la mesure de votre file d'attente est. Disons simplement que la taille est juste ici. Alors, comment peut-on réalistement insérer quelque chose dans une file d'attente? Qu'est-ce que l'indice voulons-nous placer où nous voulons insérer dans. Si tel est le début de votre la file d'attente, ce qui est la fin de celui- ou de la taille de celui-ci, où allons-nous vouloir ajouter l'objet suivant? AUDIENCE: [inaudible] ANDI PENG: Exactement, vous voulez ajouter il selon vous ai écrit il. Soit ce est vide ou qui est vide. Donc, vous voulez probablement ajouter ici parce que si la taille est-- si ceux-ci sont tous pleins, vous voulez pour l'ajouter ici, non? Et donc voilà, alors que très, très simple, pas tout à fait toujours correct parce que la différence principale entre une file d'attente et une pile est ce que la file d'attente peut en fait être manipulé de sorte que les changements de tête selon l'endroit où vous voulez le début de votre signal pour commencer. Et en conséquence, votre queue va également changer. Et ainsi de jeter un oeil à ce code en ce moment. Comme vous les gars ont également été invités à écrire sur le quiz, enqueue. Peut-être nous parler à travers pourquoi la réponse était ce qu'elle était. Je ne pouvais pas tout à fait correspondre à cette ligne sur l'une, mais essentiellement ce morceau de code devrait être sur une seule ligne. Dépenser comme 30 secondes. Jetez un oeil et voir pourquoi ceci est la façon dont il est. Très, très similaire struct, très, très la structure est semblable au précédent empiler sauf peut-être une ligne de code. Et que une ligne de code détermine la fonctionnalité. Et ce qui différencie vraiment une file d'attente à partir d'une pile. Tout le monde veut prendre un coup de couteau à expliquer pourquoi vous avez obtenu cette chose compliquée ici? Nous voyons le retour de notre ami merveilleux module. Comme vous les gars viendra bientôt de reconnaître dans la programmation, presque chaque fois que vous besoin de quelque chose à enrouler autour de quoi que ce soit, module va être la façon de le faire. Donc, sachant que, personne ne veut pour tenter d'expliquer cette ligne de code? Oui, toutes les réponses sont acceptée et bienvenue. Public: Êtes-vous en train de me parler? ANDI PENG: Ouais. AUDIENCE: Oh, non désolé. ANDI PENG: OK, nous allons donc marcher à travers ce code. Ainsi, lorsque vous essayez de ajouter quelque chose sur une file d'attente, dans le cas de beau que la tête arrive à être ici, il est très facile pour nous juste aller à la fin insérer quelque chose, non? Mais tout l'intérêt d'une file d'attente est que la tête peut réellement dynamique changer en fonction de l'endroit où nous veulent le début de notre q soit, et en tant que tel, la queue va également changer. Et alors, imaginez que ce ne fut pas le la file d'attente, mais plutôt ce fut la file d'attente. Disons que la tête est ici. Disons que notre file d'attente ressemblait à ceci. Si nous voulions déplacer où le début de la ligne est, disons que nous sommes passés la tête de cette façon et tailles ici. Maintenant, nous voulons ajouter quelque chose à cette file d'attente, mais comme vous les gars pouvez le voir, il est pas aussi simple que de simplement ajouter tout ce qui est après la taille parce que nous manquons de limites de notre tableau réel. Où nous voulons vraiment ajouter est ici. Voilà la beauté de la file d'attente est que pour nous, visuellement ressemble à la ligne va comme ceci, mais lorsqu'il est stocké dans une structure de données, ils donnent comme comme un cycle. Ce type de enroule autour à l'avant de la même façon qu'une ligne peut également envelopper autour fonction de là où vous vouloir début de la ligne de l'être. Et si nous prenons un regarder vers le bas ici, nous allons disons que nous voulions créer un fonction appelée enqueue. Nous voulions ajouter int n dans ce q. Si q.size q-- nous appellerons que nos données structure-- si notre queue.size ne égal à la capacité ou si il est inférieure à la capacité, q.strings est la matrice au sein de notre q. Nous allons mettre en qui égale à q.heads, qui est ici, plus q.size module par la capacité, ce qui enveloppez-nous revenir ici. Donc, dans cet exemple, l'indice de la tête est une, non? L'indice de taille est égal à 0, 1, 2, 3, 4. Donc, nous pouvons faire une plus 4 module par notre capacité qui est de 5. Qu'est-ce que nous donner? Quel est l'indice que sort de cette situation? AUDIENCE: 0. ANDI PENG: 0, ce qui arrive à être ici, et nous voulons être en mesure à insérer dans ici. Et si cette équation ici genre des travaux juste avec tous les numéros selon l'endroit où votre tête et votre taille sont. Si vous savez ce que ceux les choses sont, vous le savez exactement où vous voulez insérer tout ce qui est après votre file d'attente. Est-ce que de sens pour tout le monde? Je sais une sorte de cerveau Teaser surtout depuis cette est venu à la suite de votre quiz. Mais nous espérons que tout le monde maintenant peut comprendre pourquoi cette solution ou cette fonction est la façon dont il est. Toute personne un peu clair à ce sujet? D'ACCORD. Et maintenant, si vous voulu dequeue, ce est où notre tête serait décalage parce que si nous devions dequeue, nous ne prenons pas au large de la fin de la q. Nous voulons enlever la tête, non? Donc, par conséquent, la tête va changer, et voilà pourquoi lorsque vous ENQUEUE, vous avez à garder une trace de où votre tête et votre taille doivent être en mesure d'insérer dans la position correcte. Et donc quand vous DEQUEUE, Je également pseudo-it out. Sentez-vous libre de si vous voulez à tenter de codage ceci. Vous souhaitez déplacer la tête, non? Si je voulais dequeue, je serait déplacer la tête au-dessus. Ce serait la tête. Et notre taille actuelle serait soustraire parce que nous ne avoir quatre éléments dans le tableau. Nous avons seulement trois, et ensuite nous voulons pour retourner tout ce qui était stocké à l'intérieur de la tête parce que nous voulons profiter de cette valeur de manière très similaire à la pile. Juste vous prenez d'un endroit différent, et vous avez à réattribuer votre pointeur au lieu différent en conséquence. Logiquement, tout le monde suit? Génial. OK, alors nous allons parler un peu plus en profondeur sur les listes chaînées car ils vont être très, très précieux pour vous au cours de cette semaine de psets. Les listes chaînées, comme vous les gars peuvent se souvenir, tout ce qu'ils sont sont des nœuds qui sont des noeuds de certains Les valeurs à la fois une valeur et un pointeur qui sont reliés entre eux par les pointeurs. Et donc la structure sur la façon nous créons un noeud ici est que nous avoir int n, ce qui est tout ce que la valeur dans un magasin ou une chaîne n ou ce que vous voulez appeler, l'omble étoiles n. Star noeud de structure, qui est le pointeur que vous voulez avoir dans chaque nœud, vous allez avoir ce point de pointeur vers la prochaine. Vous aurez la tête d'une liste liée qui est va pointer vers le reste de les valeurs ainsi de suite et ainsi de suite jusqu'à ce que vous atteindrez la fin. Et ce dernier noeud est juste aller de ne pas avoir un pointeur. Il va pointer vers null, et que lorsqu'il est vous savez que vous avez touché le fin de votre liste chaînée est lorsque votre dernière pointeur ne pointe pas sur quoi que ce soit. Donc, nous allons aller un peu plus dans profondeur sur la façon dont on le ferait peut- rechercher une liste chaînée. Rappelez-vous ce que sont certains de la inconvénients des listes chaînées versets un tableau concernant les recherches. Un tableau vous pouvez recherche binaire, mais pourquoi ne pouvez-vous faire cela dans une liste chaînée? AUDIENCE: Parce qu'ils sont tous connectés, mais vous ne savez pas très bien où [INAUDIBLE]. ANDI PENG: Ouais, exactement ainsi souvenir que la brillance d'un tableau était le fait que nous avions mémoire à accès aléatoire où si je voulais la valeur de l'indice six, je pourrais juste dire indice de six, me donner cette valeur. Et voilà car les tableaux sont classés dans un espace contigu de mémoire en un seul endroit, alors que type de listes chaînées sont entrecoupées de façon aléatoire tout autour, et la seule façon que vous pouvez en trouver un est grâce à un pointeur qui vous dit l'adresse de l'endroit où ce nœud suivant est. Et donc, par conséquent, la seule façon de recherche à travers une liste chaînée est la recherche linéaire. Parce que je ne sais pas exactement où la valeur 12 dans la liste chaînée est, Je dois parcourir l'intégralité de cette liste chaînée un par une tête à partir du premier noeud, au second noeud, au troisième noeud, tout le chemin jusqu'à ce que je reçois enfin à l'endroit où ce nœud que je cherche est. Et dans ce sens, la recherche sur une liste chaînée est toujours n. Il est toujours n. Il est toujours dans le temps linéaire. Et donc le code dans lequel nous mettons en œuvre cela, et cela est un peu nouveau pour vous les gars, puisque vous les gars ont pas vraiment parlé ou jamais pointeurs vu dans la façon de recherche à travers des pointeurs, donc nous allons marcher à travers cette très, très lentement. Donc, la recherche booléenne, à droite, Imaginons que nous voulons pour créer une fonction appelée recherche qui renvoie true si vous avez trouvé une valeur liée à l'intérieur du liste, et il retourne false sinon. Node étoiles est actuellement un peu le pointeur le premier élément de votre liste chaînée. int n est la valeur que vous êtes chercher dans cette liste. Donc pointeur noeud étoiles liste est égal. Cela signifie que nous mettons en place et la création d'un pointeur à ce premier noeud à l'intérieur de la liste. Tout le monde avec moi? Donc, si nous devions aller de retour ici, je devrais initialiser un pointeur qui pointe vers la tête de tout ce que la liste est. Et puis une fois que vous obtenez ici, tandis pointeur ne correspond pas à null, de sorte que soit la boucle dans laquelle nous sommes va être la suite traversant le reste de notre liste parce que ce qui se passe lorsque le pointeur est égal nulle? Nous savons que nous have-- AUDIENCE: [inaudible] ANDI PENG: Exactement, donc nous savons que nous avons atteint la fin de la liste, à droite? Si vous revenez ici, chaque noeud doit être dirigée vers un autre nœud et ainsi de suite jusqu'à ce que vous atteignez finalement la queue de votre liste chaînée, qui a un pointeur qui vient ne pointe pas ailleurs que non. Et si vous savez fondamentalement que votre liste, il est toujours en place jusqu'à ce pointeur ne correspond pas à null car une fois qu'il est égal à null, vous savez qu'il n'y a pas plus de choses. Voilà donc la boucle dans laquelle nous sommes allez avoir la recherche proprement dite. Et si les pointer-- voyez-vous ce genre de fonction de flèche il? Donc, si pointeur à n, si le pointeur au n est égal à égal n, ce qui signifie que si le pointeur que vous êtes chercher à l'extrémité de chaque nœud est en fait égale à la valeur vous cherchez, puis vous voulez retourner vrai. Donc, fondamentalement, si vous êtes à un nœud qui a la valeur que vous cherchez, vous savez que vous avez été capable de rechercher avec succès. Sinon, vous souhaitez définir votre pointeur vers le nœud suivant. Voilà ce que cette ligne ici est fait. Pointeur est égal pointeur à côté. Tout le monde voir comment que ça marche? Et essentiellement, vous allez tout simplement parcourir l'intégralité de la liste, réinitialiser votre pointeur à chaque fois jusqu'à vous a finalement atteint la fin de la liste. Et vous savez qu'il ya ne sont pas plusieurs noeuds de recherche à travers, et puis vous pouvez retourner false parce que vous savez que, oh, eh bien, si je suis en mesure de rechercher à travers la totalité de la liste. Si dans cet exemple, si je voulais pour trouver la valeur de 10, et je commence à la tête, et Je cherche tout le chemin vers le bas, et je suis finalement devenu à ce qui un pointeur qui pointe à null, Je sais que, merde, je suppose que 10 est pas cette liste parce que je ne pouvais pas trouver. Et je suis à la fin de la liste. Et dans ce cas, vous savez Je vais retourner faux. Disons que tremper dans un peu. Ce sera assez important pour votre pset. La logique de cela est très simple, peut-être syntaxiquement tout mettre en œuvre. Les gars, vous voulez faire vous que vous comprenez. Frais. OK, alors comment nous serions l'insertion des nœuds, à droite, dans une liste retenir, car quels sont les avantages de ce d'avoir une liste liée par rapport un tableau en termes de stockage? PUBLIC: Il est dynamique, il est donc plus facile to-- ANDI PENG: Exactement, il est si dynamique, qui signifie qu'il peut gonfler et se rétrécir en fonction des besoins de l'utilisateur. Et donc, dans ce sens, nous ne devons pas à perdre la mémoire inutile parce que je si je ne sais pas combien de valeurs que je veux au magasin, il n'a pas de sens pour moi pour créer un tableau parce si je veux stocker 10 valeurs et je crée un tableau de 1000, qui est beaucoup de mémoire gaspillée, alloué. Voilà pourquoi nous voulons utiliser un lien Liste de pouvoir dynamiquement modifier ou réduire notre taille. Et pour que rend l'insertion un peu plus compliqué. Puisque nous ne pouvons pas accéder au hasard éléments la façon dont nous aurions d'un tableau. Si je veux insérer un élément dans la septième indice, Je peux juste insérer dans la septième indice. Sur une liste chaînée, il ne fait pas tout à fait travailler aussi facilement, et donc si nous voulions insérer celui qui est ici dans la liste chaînée, Visuellement, il est très facile à voir. Nous voulons juste pour l'insérer là, dès le début de la liste, juste après la tête. Mais la façon dont nous devons réaffecter les pointeurs est un peu alambiquées ou, logiquement, il est logique, mais vous voulez vous assurer que vous avez complètement à cause la dernière chose que vous voulez est de réaffecter un pointeur du façon que nous faisons ici. Si vous déréférencer la pointeur de la tête aux 1, puis tout d'un coup la reste de votre liste chaînée est perdu parce que vous avez pas réellement un temporaire créé rien. Qui est dirigée à l'2. Si vous réattribuez le pointeur, puis le reste de votre liste est totalement perdu. Donc, vous voulez être très, très prudent ici d'abord attribuer le pointeur de tout ce que vous à insérer dans la mesure du vous voulez, puis vous peut déréférencer le reste de votre liste. Donc, cela vaut pour la mesure vous essayez de l'insérer dans. Si vous souhaitez insérer à la tête, si vous voulez répondre ici, si vous souhaitez insérer au la fin, ainsi, à la fin, je suppose que vous feriez tout avoir aucun pointeur, mais vous voulez vous assurer que vous ne le faites pas perdre le reste de votre liste. Vous voulez toujours vous assurer votre nouveau noeud pointe vers ce que vous à insérer dans, et puis vous pouvez ajouter le chaînage. Tout le monde est clair? Cela va être l'un des vrais problèmes. Une des plus grandes questions vous allez avoir sur votre pset est-ce que vous allez essayer de créer une liste liée et les choses insertion mais alors juste de perdre le reste de votre liste chaînée. Et vous allez être comme, je ne sais pas pourquoi ce qui se passe? Et il est une douleur pour passer et rechercher tous vos pointeurs. Et je vous garantis sur ce pset, écrire et dessiner sur ces nœuds sera très, très utile. Ainsi, vous pouvez complètement suivre d'où tous vos pointeurs sont, ce qui va mal, où tous vos nœuds sont, ce que vous devez faire pour accéder ou insérer ou de supprimer ou de l'un d'eux. Tout le monde bien avec qui? Frais. Donc, si nous voulions regarder le code? Oh, je ne sais pas si nous peut voir the-- OK, donc en haut tout ce qu'il est est une fonction insert nommé où nous voulons insérer int n dans la liste chaînée. Nous allons marcher à travers cela. Il ya beaucoup de code, un lot de la nouvelle syntaxe. Nous serons OK. Alors au sommet, à chaque fois nous voulons créer quelque chose qu'est-ce que nous devons faire, surtout si vous voulez qu'il ne sera pas stockée sur la pile mais dans le tas? Nous allons à un malloc, non? Donc, nous allons créer un pointeur. Noeud, pointeur, de nouvelles égaux malloc la taille d'un noeud parce que nous voulons que le noeud à créer. Nous voulons que le montant de mémoire qui prend un noeud être alloué pour la création d'un nouveau noeud. Et puis nous allons vérifier voir si de nouveaux égaux égal nulle. Rappelez-vous ce que nous disions? Quoi que vous malloc, que devez-vous toujours le faire? Vous devez toujours vérifier pour voir si oui ou non qui est nulle. Par exemple, si votre exploitation système était complètement plein, si vous aviez pas plus de mémoire au tous et vous essayez de malloc, il serait retourner null pour vous. Et si vous essayez de l'utiliser quand il pointait à null, tu ne vas pas à la mesure pour accéder à cette information. Et en tant que telle, nous voulions faire vous que chaque fois que vous allouer de, vous êtes toujours vérifier pour voir si que la mémoire qui vous est donné est nulle. Et si elle est non, alors nous pouvons nous déplacer avec le reste de notre code. Nous allons donc initialiser le nouveau nœud. Nous allons faire une nouvelle n est égal à n. Et puis nous allons faire mettre le pointeur sur la nouvelle nouvelle null parce que nous faisons en ce moment pas vouloir quelque chose pour elle pour pointer vers. Nous ne savons pas où il va vous mettre, et puis si nous voulons insérer à la tête, alors nous pouvons réaffecter le pointeur de la tête. Est-ce que tout le monde suit la logique d'où ça se passe? Tout ce que nous faisons est de créer une nouvelle noeud, le réglage du pointeur à null, puis la réaffectation à la tête si nous savons que nous voulons pour l'insérer à la tête. Et puis, la tête va pointer vers ce nouveau nœud. Tout le monde OK avec ça? Donc, il est un processus en deux étapes. Vous devez d'abord affecter tout ce que vous créez. Réglez ce pointeur à la référence, et ensuite vous peut sorte de déréférencer le premier pointeur et pointer vers le nouveau nœud. Partout où vous voulez l'insérer, que la logique va être vrai. Il est un peu comme l'attribution variables temporaires. Rappelez-vous, vous avez pour vous assurer que vous ne pas perdre de si vous échanger. Vous voulez vous assurer que vous avez une variable temporaire qui maintient type de trace d'où cette chose est stockée afin que vous ne pas perdre toute valeur au cours comme de déconner avec elle. OK, donc le code sera ici. Les gars, vous jetez un oeil après l'article. Il sera là. Donc je suppose que la façon dont le fait cela diffère si nous voulions à insérer dans le milieu ou la fin? Quelqu'un at-il une idée de ce qui est la pseudo que la référence logique que nous prendrions si nous voulions pour l'insérer dans le milieu? Donc, si nous voulions pour l'insérer à la tête, tout ce que nous faisons est de créer un nouveau nœud. Nous avons mis le pointeur de ce nouveau nœud à ce que la tête, puis nous avons mis la tête vers le nouveau nœud, non? Si nous voulions de l'insérer dans le milieu de la liste, qu'aurions-nous faire? Auditoire: ce serait encore être un processus similaire de l'attribution comme pointeur et puis en attribuant ce pointeur, mais nous aurions à s'y implanter. ANDI PENG: Exactement, si exactement le même processus, sauf vous avoir pour localiser exactement où vous veulent que le nouveau pointeur d'aller dans, donc si je veux insérer dans le milieu de films-- liée OK, disons que notre liste est lié. Si nous voulons insérer ici, nous allons créer un nouveau noeud. Nous allons malloc. Nous allons créer un nouveau nœud. Nous allons assigner le pointeur de ce noeud. Mais le problème qui diffère d'où la tête est est que nous savions exactement où la tête est. Il était à droite au premier, non? Mais ici nous avons à suivre d'où nous insérant dans. Si nous insérons notre noeud ici, nous avons pour vous assurer que le un précédent de ce noeud est celle qui réaffecte le pointeur. Alors vous devez sorte de garder la trace de deux choses. Si vous gardez une trace de l'endroit où cette noeud est actuellement insérer dans. Vous avez également de garder une trace de l'endroit où le nœud précédent que vous êtes à la recherche au était également là. Tout le monde bien avec qui? D'ACCORD. Comment sur l'insertion dans l'extrémité? Si je voulais ajouter ici-- si je voulais à ajouter un nouveau noeud à la fin de la liste, Comment pourrais-je m'y prendre? Auditoire: Alors, pour le moment, la dernière de celui pointé nulle. ANDI PENG: Ouais. Exactement, si celui- actuellement est fait de savoir, et donc je suppose que, dans ce sens, il est très facile d'ajouter à la fin de la liste. Tout ce que vous avez à faire est de définir ce égale à null puis essor. Juste là, très facile. Très simple. Très similaire à la tête, mais logiquement vous voulez vous assurer que les étapes vous prenez en direction de faire tout cela, vous suivez. Il est très facile de, au milieu de votre code, se laisser prendre sur, oh, je ai tellement de pointeurs. Je ne sais pas où rien pointe. Je ne sais même pas qui je suis sur le noeud. Ce qui se passe? Détendez-vous, calmez-vous, prenez une profonde respiration. Dessinez votre liste chaînée. Si vous le dites, je sais exactement où Je dois insérer cela dans et je sais exactement comment réaffecter mon pointeurs, beaucoup, beaucoup plus facile d'imaginer out-- beaucoup, beaucoup plus facile à pas se perdre dans les bugs de votre code. Tout le monde OK avec ça? D'ACCORD. Donc je suppose un concept que nous avons pas vraiment parlé avant aujourd'hui, et je suppose que vous probablement ne rencontrera beaucoup yet-- il est une sorte d'concept-- avancée est que nous avons fait un données structure appelée une liste doublement chaînée. Donc, comme vous les gars pouvez le voir, tout ce que nous faisons est la création une valeur réelle, un supplément de pointeur sur chacun de nos nœuds qui souligne également le noeud précédent. Ainsi, non seulement nous avons notre nœuds point à la suivante. Ils soulignent également à la précédente. Je vais ignorer ces deux maintenant. Alors vous avez une chaîne qui peut se déplacer dans les deux sens, et alors il est un peu plus facile à suivre logiquement long. Comme ici, au lieu de garder la trace de, oh, je faut savoir que ce noeud est celui que je dois réaffecter, Je peux juste aller ici et il suffit de tirer la précédente. Alors je sais exactement où qui est, et puis vous ne pas avoir à traverser le intégralité de la liste chaînée. Il est un peu plus facile. Mais en tant que telle, vous avez doublement la quantité de pointeurs, qui est le double de la quantité de mémoire. Il ya beaucoup de pointeurs à garder la trace. Il est un peu plus complexe, mais il est un peu plus convivial en fonction sur ce que vous essayez d'accomplir. Donc, ce type de données structure existe totalement, et la structure pour est très, très simple, sauf tout ce que vous rencontrez est, au lieu de simplement un pointeur vers la prochaine, vous avez également un pointeur vers précédente. Voilà toute la différence était. Tout le monde bien avec qui? Frais. Très bien, alors maintenant je suis pour vraiment passer probablement comme 15 à 20 minutes ou le vrac le reste du temps dans la section parler de tables de hachage. Combien d'entre vous les gars ont lu pset5 spec? Très bien, bon. Voilà plus élevé que les 50% de normalement. C'est bon. Donc, comme vous pourrez voir les gars, vous êtes défi dans pset5 sera de mettre en oeuvre un dictionnaire où vous chargez plus de 140.000 mots que nous vous donnons et vérification orthographique contre l'ensemble du texte. Nous vous donnerons aléatoire morceaux de la littérature. Nous vous donnerons L'Odyssée. Nous allons vous donner l'Iliade. Nous vous donnerons Austin Powers. Et votre défi sera de vérification orthographique chaque mot dans tous les de ces dictionnaires essentiellement avec notre correcteur orthographique. Et donc il ya quelques parties de la création de ce jeu de processeurs, D'abord, vous voulez être en mesure de réellement charger tous les mots dans votre dictionnaire, et puis vous veulent être en mesure de vérifier l'orthographe de chacun d'eux. Et en tant que tel, vous allez exiger une structure de données qui peut faire ce jeûne et de manière efficace et dynamique. Donc je suppose que le plus facile façon de le faire, vous serait probablement créer un tableau, non? La meilleure façon de stockage est vous peut créer un tableau de 140.000 mots et juste les placer tous là et puis traverser les par recherche binaire ou par des sélections ou pas-- Désolé que ça tri. Vous pouvez les trier et parcourir les par recherche binaire ou linéaire recherche juste et juste finales les mots, mais que prend une énorme quantité de mémoire, et il est pas très efficace. Et donc nous allons commencer parler de façons de faire notre temps de fonctionnement plus efficace. Et notre objectif est d'obtenir constante de temps où il est presque comme les tableaux, où vous avez un accès instantané. Si je voulais chercher quoi que ce soit, Je veux être capable de tout, perche, trouver exactement, et le sortir. Et ainsi une structure dans laquelle nous serons en train de devenir très proche pour être en mesure d'accéder constante temps, ce saint Graal la programmation de la constante le temps est appelée une table de hachage. Et si David mentionné précédemment, les [Inaudible] un peu de lecture, mais nous allons vraiment plongée dans une profonde cette semaine sur un morceau qui est en ce qui concerne comment une table de hachage fonctionne. Donc, la façon dont un hachage ouvrages de table, par exemple, si je voulais enregistrer un tas de mots, un tas de mots dans la langue anglaise, Je pourrais théoriquement mettre banane, pomme, kiwi, mangue, paire, et le cantaloup tout simplement sur un tableau. Ils pourraient tous intégrer et être trouver. Ce serait une sorte de douleur à parcourir et l'accès, mais le plus simple de le faire est que nous pouvons réellement créer une structure appelé une table de hachage où nous hachage. Nous courons tous nos clés à travers une fonction de hachage, une équation, que tous les tours en une sorte de valeur que nous pouvons stocker sur essentiellement un tableau de liste chaînée. Et ici, si nous voulions pour stocker des mots anglais, nous pourrions potentiellement juste, je ne fais pas savoir, mettez toutes les premières lettres en quelque sorte d'un certain nombre. Et ainsi, par exemple, si je voulais Un synonyme de apple-- ou avec l'indice de 0, et B soit synonyme de 1, nous pouvons avoir 26 entrées qui peut simplement stocker toutes les lettres de l' alphabet que nous allons commencer avec. Et alors nous pouvons avoir pomme à l'index de 0. Nous pouvons avoir la banane à l'index des 1, le cantaloup à l'index de 2, et ainsi de suite. Et donc si je voulais chercher ma table de hachage et l'accès pomme, Je sais que la pomme commence par un A, et je sais exactement qu'il doit être et le hachage tableau à l'index 0 parce de la fonction précédemment attribuée. Donc, je ne sais pas, nous sommes un programme utilisateur où vous serez facturé avec arbitrarily-- pas arbitrairement, à essayer de pensivement penser de bonnes équations pour être en mesure de se propager l'ensemble de vos valeurs d'une manière qu'ils peuvent facilement accéder il plus tard avec comme une équation que vous, vous-même, savent. Ainsi, dans le sens que si je voulais aller à mangue, je sais, oh, il commence par m. Il doit être à l'index des 12. Je ne dois pas chercher dans quoi que ce soit. Je sais exactly-- je pouvais aller à l'indice des 12 et tirez cela. Tout le monde sur la façon dont un clair La fonction de table de hachage des fonctionne? Il est un peu juste un tableau plus complexe. Voilà tout ce qu'il est. D'ACCORD. Donc je suppose que nous nous heurtons à cette question de ce que qui se passe si vous avez plusieurs choses qui vous donnent le même indice? Donc, dire que notre fonction, tout ce qu'il n'a fait que prendre cette première lettre et le transformer en un respective de 0 à 25 index. Cela est tout à fait bien si vous avez seulement un de chaque. Mais la deuxième vous commencez avoir plus, vous êtes va avoir ce qu'on appelle une collision. Donc, si je tente d'insérer l'enterrer dans un hachage table qui a déjà la banane sur elle, qu'est-ce qui va se passer quand vous essayez d'insérer cela? Les mauvaises choses parce que la banane existe déjà au sein de l'indice que vous souhaitez stocker dans. Berry genre de est comme, ah, je fais quoi? Je ne sais pas où aller. Comment puis-je résoudre ce problème? Et si vous les gars seront sorte de voyons que nous faisons cette chose délicate où nous pouvons sorte de réalité créer une liste liée dans nos tableaux. Et la meilleure façon de penser à ce sujet, tous table de hachage est une tableau de listes liées. Et donc, dans ce sens, vous avez ce beau tableau de pointeurs, puis chaque pointeur dans cette valeur, dans cet indice, peut effectivement pointer vers d'autres choses. Et si vous avez tous ces séparée les chaînes qui sortent d'un grand tableau. Et donc là, si je voulu insérer Berry, Je sais, OK, je vais à l'entrée à travers ma fonction de hachage. Je vais finir avec l'indice de 1, et puis je vais être en mesure d'avoir juste un petit sous-ensemble de cette 140.000 mots géant dictionnaire. Et puis, je peux simplement regarder 26.1 travers de cela. Et alors je peux juste insérer Berry soit avant ou après la banane dans ce cas? Après, non? Et si vous allez vouloir insérer ce noeud après la banane, et donc vous allez insérer à la queue de la liste liée. Je vais revenir à cette diapositive précédente, de sorte que vous pouvez voir comment les gars fonction de hachage fonctionne. Donc fonction de hachage est cette équation que vous sorte de votre entrée en cours d'exécution jusqu'à obtenir ce que l'index vous voulez affecter vers. Et donc, dans cet exemple, tout ce qu'on voulait à faire était de prendre la première lettre, le transformer en un indice, alors nous peut stocker que dans notre fonction de hachage. Tout ce que nous faisons ici est que nous sommes convertir la première lettre. Donc KeyKey [0] est tout simplement la première lettre de quelque chaîne que nous allons avoir, nous passons en. Nous convertir ce à supérieure, et nous soustrayant par majuscule, donc tout ce qui est fait nous donne un certain nombre dans lequel nous pouvons hachage sur nos valeurs. Et puis nous allons retourner hachage taille de module. Soyez très, très prudent parce que, théoriquement, ici votre valeur de hachage pourrait être infinie. Il pourrait simplement aller sur et sur et sur. Il pourrait être une vraiment, très grande valeur, mais parce que votre table de hachage vous avez créé a seulement 26 indices, vous voulez vous assurer que votre modulusing afin que vous ne run-- il est le même chose que votre queue-- de sorte que vous ne courez pas au large de la bas de votre fonction de hachage. Vous voulez de l'envelopper de retour autour de la même manière dans [inaudible] lorsque vous aviez comme un très, très grande lettre, vous je ne voulais pas que cela se il suffit d'exécuter l'extrémité. Même chose ici, vous voulez vous assurer que il ne coule pas la fin en enveloppant autour de la partie supérieure de la table. Donc, ceci est juste un très fonction de hachage simple. Tout ce qui n'a fait que prendre la première lettre quelle que soit notre entrée était et le transformer en un indice qui nous pourrions mettre dans notre table de hachage. Ouais, et ainsi que je l'ai dit avant, la manière dont nous résolvons les collisions dans notre hash tables éprouvent, ce que nous appelons, chaînage. Donc, si vous essayez d'insérer multiples mots qui commencent par la même chose, vous allez avoir une valeur de hachage. Les avocats et les pommes, si vous avez le lancer à travers notre fonction de hachage, vont vous donner la même nombre, le nombre de 0. Et la façon dont nous résoudre qui est que nous pouvons réellement sorte de lien entre eux ensemble via des listes chaînées. Et dans ce sens, vous les gars peuvent voir genre de la façon dont des structures de données nous avons précédemment fixons comme une liste liée raisin genre de peuvent se réunir en un seul. Et puis, vous pouvez créer autant structures de données plus efficaces qui peut gérer de grandes quantités de données, ce redimensionner dynamiquement en fonction sur vos besoins. Tout le monde est clair? Tout le monde sorte de clair sur ce qui se passe ici? Si je voulais insert-- ce qui est un fruit qui commence par, je ne sais pas, B, autres que les baies, les bananes. AUDIENCE: Blackberry. ANDI PENG: Blackberry, Blackberry. Où BlackBerry aller ici? Eh bien, nous avons fait pas trié encore, mais en théorie Si nous voulions avoir cette dans l'ordre alphabétique, où la mûre devrait aller? AUDIENCE: [inaudible] ANDI PENG: Exactement, après ici, non? Mais depuis il est très difficile de reorder-- Je suppose que cela est à vous les gars. Les gars, vous pouvez tout à fait mettre en œuvre tout ce que vous voulez. La façon la plus efficace de le faire peut-être serait de trier vos liée liste dans l'ordre alphabétique, et donc quand vous êtes l'insertion des choses, que vous voulez pour être sûr de les insérer dans l'ordre alphabétique de sorte que lorsque vous êtes alors en essayant de les rechercher, vous ne disposez pas de traverser tout. Vous savez exactement où il est, et il est plus facile. Mais si vous avez sorte de entrecoupées de choses au hasard, vous allez encore avoir pour traverser toute façon. Et si je voulais juste BlackBerry insérer ici et je voulais chercher il, je sais, oh, BlackBerry doit commencer par l'indice de 1, donc je connaître instantanément suffit de chercher à 1. Et puis je peux type de parcourir la liste chaînée jusqu'à ce que je reçois de BlackBerry, et alors-- ouais? Public: Si vous essayez de create-- Je suppose que ce genre est un hachage très simple fonction. Et si nous voulions faire de multiples couches de que, comme, OK, nous voulons séparer en comme toutes les lettres de l'alphabet et puis de nouveau à aimer un autre jeu de lettres alphabétiques dans ce cadre, mettons-nous comme un hachage tableau dans un tableau de hachage, ou comme une fonction au sein d'une fonction? Ou est that-- ANDI PENG: Donc, votre hachage function-- votre table de hachage peut être aussi grand que vous le souhaitez. Donc, dans ce sens, je pensais il était très facile, très simple pour moi de repose juste une sorte sur les lettres du premier mot. Et donc il ya seulement 26 options. Je ne peux obtenir 26 options de 0 à 25 car ils ne peuvent commencer de A à Z. Mais si vous voulez d'ajouter, peut-être, plus de complexité ou plus courir de temps à votre table de hachage des, vous avez absolument peut faire toutes sortes de choses. Vous pouvez faire votre propre équation qui vous donne plus la distribution dans votre mots, puis lorsque vous recherchez, ça va être plus rapide. Il est totalement à vous les gars comment vous voulez mettre en oeuvre. Pensez-y comme seulement seaux. Si je voulais avoir 26 seaux, je vais pour arranger les choses dans ces seaux. Mais je vais avoir un tas de choses dans chaque seau, donc si vous voulez faire plus rapide et plus efficace, laissez-moi avoir une centaine de seaux. Mais alors vous devez trouver un façon de régler les choses de sorte qu'ils sont dans le seau correcte ils devraient être dans. Mais alors, quand vous avez réellement vouloir regarder ce seau, il est beaucoup plus rapide car il ya moins de choses dans chaque seau. Et donc, oui, qui est en fait le truc pour vous les gars dans pset5 est que vous serez défié de créer simplement ce qui est le plus efficace fonction que vous pouvez penser à être capable de stocker et de vérifier ces valeurs. Totalement à vous les gars mais vous voulez le faire, mais qui est un très bon point. Que le genre de logique vous vouloir commencer à penser à est, bien, pourquoi dois-je pas faire plus seaux. Et puis je dois rechercher moins de choses, et alors peut-être que je avoir une fonction de hachage différent. Oui, il ya beaucoup de façons de le faire pset, certains sont plus rapides que d'autres. Je suis totalement d'aller voir à quel point était rapide les plus rapides vous les gars être en mesure d'obtenir vos fonctions à travailler. OK, tout le monde sur la bonne chaînage et de hachage tables? Il est en fait très simple comme un notion si vous pensez à ce sujet. Tout ce qu'il est est ce que la séparation vos entrées sont dans des seaux, les trier, puis en recherchant la énumère qu'il y est associé. Frais. Très bien, maintenant, nous avons une sorte différente de structure de données que l'on appelle un arbre. Allons et parlent essais qui sont nettement différentes, mais dans la même catégorie. Essentiellement, tout est un arbre à la place organiser les données de manière linéaire dans la qu'une table de hachage vous does-- le savez, il a un haut et un bas et puis vous type de lien hors de it-- une arbre a un top que vous appelez la racine, et puis il a des feuilles tout autour de lui. Et tout ce que vous avez ici est tout simplement le nœud supérieur que les points à d'autres noeuds, que les points à plusieurs noeuds, et ainsi de suite et ainsi de suite. Et donc vous avez juste branches fractionnement. Il est juste une façon différente d'organiser données, et parce que nous appelons un arbre, vous les gars just-- il est juste modélisé pour ressembler à un arbre. Voilà pourquoi nous appelons les arbres. Table de hachage ressemble à une table. Un arbre ressemble à un arbre. Tout ce qu'il est est un séparée façon d'organiser les nœuds en fonction de ce que sont vos besoins. Donc, vous avez une racine et alors vous avez des feuilles. La façon dont nous pouvons particulier penser est un arbre binaire, un arbre binaire est juste un type spécifique d'un arbre où chaque noeud seuls points à, au maximum, deux autres noeuds. Et là, vous avez distincte symétrie dans votre arbre qui le rend plus facile à genre de look à ce que les valeurs que vous êtes parce que vous toujours avoir une gauche ou un droit. Il n'y a jamais comme un tiers gauche de ou le quart gauche depuis le côté gauche. Il est juste que vous avez une gauche et une droite et vous pouvez rechercher soit des deux. Et pourquoi est-ce utile? La façon dont cela est est utile si vous êtes à la recherche de recherche à travers des valeurs, non? Plutôt que de mettre en œuvre binaire recherche dans un tableau d'erreur, si vous voulez être en mesure d'insérer noeuds et enlever les nœuds à volonté et aussi préserver la recherche capacités de recherche binaire. Donc, de cette manière, nous sommes en quelque sorte tricking-- souvenir lorsque nous ladite listes chaînées ne pouvez pas rechercher binaire? Nous sommes en quelque sorte de créer une structure de données que des astuces qui en travaillant. Et parce que les listes liées sont linéaires, elles sont liées seulement l'une après l'autre. Nous pouvons avoir de genre autre type de pointeurs ce point à différents noeuds qui peut nous aider à la recherche. Et ici, si je voulais avoir un arbre binaire de recherche, Je sais que mon milieu, si 55. Je vais juste pour créer ce que comme mon milieu, comme ma racine, et puis je vais devoir valeurs spin off de celui-ci. Donc, ici, si je vais à la recherche de la valeur de 66, je peux commencer à 55. Il est 66 supérieure à 55? Oui, il est, donc je sais que je cherche mus i n le droit pointeur de cet arbre. Je vais à 77. OK, est inférieur à 66 ou supérieur à 77? Il est moins, donc vous savez, oh, ce doit être le nœud gauche. Et ici nous sommes en quelque sorte de préserver toutes les grandes choses au sujet des tableaux, ainsi comme le redimensionnement dynamique des objets, étant capable d'insérer et de supprimer à volonté, sans avoir à se soucier du fixe quantité d'espace. Nous conservons encore tous ces choses merveilleuses tout en étant capable de conserver la log et le temps de recherche de recherche binaire que nous étions seulement auparavant en mesure d'obtenir une phrase. Structure de données Cool, sorte de complexe à implémenter, le nœud. Comme vous pouvez le voir, tout ce qu'il est la structure du noeud est que vous avez une gauche et un pointeur à droite. Voilà tout ce qu'il est. Donc, plutôt que de simplement ayant un X ou un précédent. Vous disposez d'un gauche ou droit, puis vous pouvez sorte de les relier entre eux Cependant vous le souhaitez. OK, nous allons en fait il suffit de prendre quelques minutes. Donc, nous allons revenir ici. Comme je le disais précédemment, Je sorte de expliquai la logique derrière la façon dont nous chercherait par ce biais. Nous allons essayer pseudocoding ceci à voir si nous pouvons appliquer le genre de même logique de recherche binaire à un type de structure de données différent. Si vous voulez les gars à prendre comme un couple minutes pour penser juste à ce sujet. D'ACCORD. Très bien, je vais en fait juste vous donner the-- pas, nous allons parler de la pseudo-première. Donc Quelqu'un veut- pour donner un coup de couteau à ce la première chose que vous voulez faire quand vous commencez la recherche est? Si nous sommes à la recherche la valeur de 66, ce qui est la première chose que nous voulons faire si nous voulons binaires de recherche cet arbre? AUDIENCE: Vous voulez regarder à droite et de regarder à gauche et voir [inaudible] plus grand nombre. ANDI PENG: Oui, exactement. Donc, vous allez regarder votre racine. Il ya beaucoup de façons que vous pouvez appeler , vos gens nœud parent dire. Je tiens à dire, car la racine qui est comme la racine de l'arbre. Vous allez regarder votre nœud racine, et vous êtes allez voir est 66 supérieure ou inférieur à 55. Et si elle est supérieure à, eh bien, il est supérieure, où voulons-nous chercher? Où voulons-nous pour chercher maintenant, non? Nous voulons rechercher la la moitié droite de cet arbre. Nous avons donc, idéalement, un pointeur qui pointe vers la droite. Et alors nous pouvons mettre en notre nouvelle racine soit 77. Nous pouvons simplement aller là où Positionnez le pointeur. Eh bien, oh, ici nous commençons à 77, et nous ne pouvons tout simplement le faire de manière récursive encore et encore. De cette façon, vous genre d'avoir une fonction. Vous avez une façon de chercher que vous peut simplement répéter encore et encore et encore, selon l'endroit où vous voulez regarder jusqu'à ce que vous obtenez finalement à la valeur que vous êtes à la recherche pour. Donner un sens? Je suis sur le point de vous montrer la réelle code, et il ya beaucoup de code. Pas besoin de paniquer. Nous parlerons à travers elle. En fait non. Ce était juste pseudo. OK, qui était juste le pseudo-code, qui est un peu complexe, mais il est tout à fait bien. Tout le monde suit le long ici? Si la racine est null, le retour faux parce que les moyens vous ne même pas quelque chose là-bas. Si la racine n est la valeur, de sorte que si elle se trouve être celui que vous cherchez à, alors vous allez retourner vrai parce que vous savez vous l'avez trouvé. Mais si la valeur est inférieure de racine de n, vous êtes aller chercher la gauche enfant ou la feuille de gauche, tout ce que vous voulez l'appeler. Et si la valeur est supérieure à la racine, vous allez chercher le bon arbre, puis il suffit d'exécuter la fonction grâce à la recherche à nouveau. Et si la racine est nulle, ce qui signifie que vous avez atteint la fin? Cela signifie que vous avez pas plus plus part à la recherche, alors vous savez, oh, je suppose qu'il est pas ici parce que, après, je l'ai regardé à travers toute chose et il est pas là, ça pourrait ne pas être ici. Est-ce que de sens pour tout le monde? Donc, il est comme la préservation de recherche binaire les capacités de listes chaînées. , Et de sorte que le deuxième type cool de la structure de données que vous les gars peut essayer de mettre en œuvre sur votre pset, il suffit de choisir une méthode. Mais peut-être une méthode alternative pour la table de hachage est ce que nous appelons un trie. Tout un trie est est un type spécifique de arbre a des valeurs qui vont à d'autres valeurs. Ainsi, au lieu d'avoir un binaire arbre dans le sens où seulement une chose peut pointer à deux, vous pouvez avoir Point à beaucoup, beaucoup de choses une chose. Vous avez essentiellement tableaux l'intérieur de laquelle vous stockez pointeurs qui pointent vers d'autres réseaux. Donc, le nœud de la façon dont nous définirait un trie est que nous voulons avoir une Boolean, c mot, non? Ainsi, le noeud est booléenne comme vrai ou faux, tout d'abord à la tête de ce tableau, est-ce un mot? Deuxièmement, vous voulez avoir des pointeurs à tout ce que le reste d'entre eux sont. Un peu complexe, un peu abstrait, mais Je vais vous expliquer ce que tous les moyens. Donc, ici, au sommet, si vous ont un tableau déclaré déjà, un noeud où vous avez un booléen valeur stockée à l'avant qui vous dit est-ce un mot? Est-ce pas un mot? Et puis vous avez la reste de votre tableau qui stocke en fait tout le possibilités de ce qu'il pourrait être. Ainsi, par exemple, comme au sommet, vous avez la première chose qui dit vrai ou faux, oui ou non, cela est un mot. Et puis vous avez de 0 à 26 les lettres que vous pouvez stocker. Si je voulais chercher ici pour les chauve-souris, je vais vers le haut et je regarde pour B. je trouve dans mon B tableau, et ainsi je sais, OK, est B un mot? B est pas un mot, donc ainsi Je dois continuer à chercher. Je vais de B, et je me réjouis à la pointeur qui pointe vers B et je vois un autre tableau de l'information, la même structure que nous avions avant. Et ici-- oh, la prochaine lettre de [inaudible] est A. Donc, nous regardons dans ce tableau. Nous trouvons la huitième valeur, puis nous attendons à voir, oh, Hey, est-ce un mot, est B-A un mot? Il est pas un mot. Nous devons continuer à chercher. Et alors nous nous tournons vers où le pointeur d'un point, et il pointe vers une autre façon que nous avons plus de valeur stockée. Et finalement, nous arrivons à B-A-T, qui est un mot. Et donc la prochaine fois vous regardez, vous allez d'avoir ce chèque de, oui, cette fonction booléenne est vraie. Et donc, en ce sens que nous sommes en quelque sorte d'avoir un arbre avec des tableaux. Alors vous pouvez type de recherche vers le bas. Plutôt que de hachage une fonction et attribuer des valeurs par liste chaînée, vous pouvez simplement mettre en œuvre une Trie qui recherche Oréal qu. Vraiment, vraiment compliqué choses. Pas facile de penser parce que je suis comme cracher autant de structures de données sur à vous, mais que tout le monde sorte de comprendre comment la logique de ce qui fonctionne? OK cool. Donc B-A-T, puis vous allez chercher. La prochaine fois que vous allez pour voir, oh, hé, il est vrai, donc je sais que ce doit être un mot. Même chose pour le zoo. Alors, voici la chose en ce moment, si nous voulu chercher zoo, en ce moment, actuellement zoo est pas un mot dans notre dictionnaire parce que, comme vous les gars peut le voir, le la première place que nous avons un booléen return true est à la fin de zoom. Nous avons Z-O-O-M. Et alors voici, nous ne disposons pas fait le mot, zoo, dans notre dictionnaire parce que cette case est décochée. Ainsi, l'ordinateur n'a pas sachez que le zoo est un mot parce que la façon que nous avons stocké, seulement un zoom ici a effectivement une valeur booléenne ce qui a été tourné vrai. Donc, si nous voulons insérer le mot, zoo, dans notre dictionnaire, comment pourrions-nous le faire de cela? Que devons-nous faire pour nous assurer que notre ordinateur sait que Z-O-O est un mot et pas le premier mot est Z-O-O-M? AUDIENCE: [inaudible] ANDI PENG: Exactement, nous voulez vous assurer que cette ici, cette valeur booléenne est coché qu'il est vrai. Z-O-O, puis nous allons vérifier que, nous savons donc exactement, hey, zoo est un mot. Je vais dire à la ordinateur qu'il est un mot si que, lorsque les contrôles de l'ordinateur, il sait que le zoo est un mot. Car rappelez-vous toutes ces données structures, il est très facile pour nous à-dire, oh, chauve-souris est un mot. Zoo est un mot. Zoom est un mot. Mais quand vous construire, l'ordinateur n'a aucune idée. Donc, vous avez à dire exactement à quel moment est-ce un mot? À quel moment est-il pas un mot? Et à quel moment dois-je besoin de chercher des choses, et à quel moment dois-je aller? Chacun claire de cela? Frais. Et puis vient le problème de comment pourrions-nous aller sur l'insertion de quelque chose qui est en fait pas là? Donc disons que nous voulons insérer le mot, salle de bain, dans notre trie. Comme vous les gars peuvent voir comme actuellement tout ce que nous avons maintenant est B-A-T, et cette nouvelle structure de données il y avait une pinte qui pointé nulle parce que nous supposons que, oh, il n'y a pas de mots après B-A-T, Pourquoi avons-nous besoin de garder avoir des choses après que T. Mais le problème se pose si nous faisons vous veulent avoir un mot qui vient après T de la. Si vous avez de bain, vous êtes allez vouloir un droit d'H. Et la façon dont nous allons faire est nous allons créer un noeud distinct. Nous ne sommes pas attribuons quelque quantité de mémoire pour cette nouvelle gamme, et nous allons réaffecter des pointeurs. Nous allons assigner le H, Tout d'abord, ce nul, nous allons débarrasser. Nous allons avoir les vers le bas du point H. Si nous voyons un H, nous voulons pour aller à un autre endroit. Ici, nous pouvons alors cocher oui. Si nous avons atteint un H après la T, oh, alors nous savons que cela est un mot. Le booléenne va revenir vrai. Tout le monde clair sur comment cela est arrivé? D'ACCORD. Donc, essentiellement, tous ces structures de données que nous avons dépassé aujourd'hui, je l'ai allé sur eux vraiment, vraiment vite et pas dans beaucoup de détail, et qui est OK. Une fois que vous commencez à déconner avec elle, vous serez garder la trace de l'endroit où tous les pointeurs sont, ce qui se passe dans votre structures de données, et cetera. Ils vont être très utile, et il est à vous les gars de figurer totalement comment vous voulez mettre en œuvre les choses. Et donc pset4, de 5-- oh, cela est faux. Pset5 est fautes d'orthographe. Comme je l'ai dit avant, vous allez, une fois à nouveau, télécharger le code source de nous. Il va y avoir trois principaux choses que vous allez télécharger. Vous télécharger les dictionnaires, KERS, et des textes. Toutes ces choses sont sont soit dictionnaires de mots que nous voulons que vous vérifiez ou l'essai de l'information que nous voulons que vous Vérifier l'orthographe. Et ainsi les dictionnaires nous donnons vous allez pour vous donner des mots réels que nous voulons de stocker en quelque sorte d'une manière qui est plus efficace qu'un tableau. Et puis les textes sont va être ce que nous sommes vous demandant de vérifier l'orthographe pour vous assurer tous les mots, il n'y a de vrais mots. Et ainsi les trois blocs de les programmes que nous vous donnerons dictionary.c sont appelés, dictionary.h, et speller.c. Et ainsi tout dictionary.c fait est ce que vous êtes invité à mettre en œuvre. Il charge mots. Il sort contrôles eux, et il fait en sorte que tout est correctement insérée. diction.h est juste un fichier de bibliothèque qui déclare toutes ces fonctions. Et speller.c, nous allons vous donner. Vous ne devez pas modifier quoi que ce soit. Tout est speller.c ne prendre que, le charge, vérifie la vitesse de celui-ci, teste l'indice de référence comme la façon dont rapidement, vous êtes en mesure de faire des choses. Il est un correcteur orthographique. Juste ne plaisante pas avec elle, mais assurez- sûr que vous comprenez ce qu'il fait. Nous utilisons une fonction appelée getrusage que teste les performances de votre sort vérificateur. Tout ce qu'il fait est essentiellement tester la le temps de tout dans votre dictionnaire, alors assurez-vous que vous le comprenez. Veillez à ne pas salir avec elle ou les autres choses ne seront pas fonctionner correctement. Et la majeure partie de ce défi est pour vous les gars de modifier vraiment dictionary.c. Nous allons vous donner 140.000 mots dans un dictionnaire. Nous allons vous donner un texte fichier qui a ces mots, et nous voulons que vous soyez en mesure d'organiser les dans une table de hachage ou un trie parce que quand nous vous demandons de préciser check-- imaginez si vous êtes sort la vérification comme l'Odyssée d'Homère. Il est comme ça énorme, énorme test. Imaginez si chaque simple mot que vous aviez à regarder à travers un réseau de 140.000 valeurs. Ce serait prendre une éternité pour votre machine de fonctionner. Voilà pourquoi nous voulons organiser notre données dans des structures de données plus efficaces comme une table de hachage ou un trie. Et puis vous les gars peuvent genre de l'accès lorsque vous recherchez les choses plus facilement et plus rapidement. Et soyez donc prudent de résoudre les collisions. Vous allez obtenir un tas des paroles de ce départ avec A. Vous allez obtenir un tas mots qui commencent par B. Jusqu'à vous les gars comment vous voulez le résoudre. Peut-être il ya plus fonction de hachage efficace que seulement la première lettre quelque chose, et que est à vous les gars de sorte de faire ce que vous voulez. Peut-être que vous voulez ajouter toutes les lettres ensemble. Peut-être que vous voulez voulez faire des choses bizarres pour tenir compte du nombre de lettres, peu importe. À vous les gars comment vous voulez faire. Si vous voulez faire une table de hachage, si vous vouloir essayer un trie, totalement à vous. Je vais vous avertir à l'avance que le Trie est généralement un peu plus difficile juste parce que il ya beaucoup plusieurs pointeurs de garder la trace. Mais totalement à vous les gars. Il est beaucoup plus efficace dans la plupart des cas. Vous voulez vraiment être en mesure de garder une trace de tous vos pointeurs. Comme faire la même chose que je faisais là. Lorsque vous essayez d'insérer des valeurs dans une table de hachage ou supprimer, assurez-vous que vous êtes vraiment garder la trace d'où tout est parce que il est vraiment facile car si je suis essayer d'insérer comme le mot, Andy. Disons simplement que ce est un vrai mot, le mot, andy, dans une liste géante de A mots. Si je viens d'arriver à réaffecter un mauvais pointeur, oops, il y va de l'intégralité des le reste de ma liste chaînée. Maintenant, le seul mot que je ont est Andy, et maintenant tous les autres mots du dictionnaire ont été perdus. Et si vous voulez vous assurer que vous garder une trace de tous vos pointeurs ou bien vous allez obtenir d'énormes problèmes dans votre code. Dessiner les choses avec soin, étape par étape. Il rend beaucoup plus facile de penser. Et enfin, vous voulez être en mesure de tester vos performances de votre programme sur le grand tableau. Si vous les gars prendre un regarder CS50 dès maintenant, nous avons ce qu'on appelle le grand tableau. Il est la feuille de pointage de la plus rapide épeler fois de contrôle dans l'ensemble de CS50 maintenant, je pense que le sommet comme 10 fois je pense que huit d'entre eux sont employés. Nous voulons vraiment que vous les gars à nous battre. Chacun d'entre nous ont essayé de mettre en œuvre le code le plus rapide possible. Nous voulons que vous les gars pour essayer de contester nous et mettre en œuvre plus rapidement que nous tous pouvoir. Et si cela est vraiment la première fois que nous sommes vous demandant de faire un gars qui pset vous pouvez vraiment faire quelle que soit la méthode tu veux. Je dis toujours, ce qui est plus apparenté à une solution de la vie réelle, non? Je dis, hey, je veux que vous faites cela. Construire un programme qui fait ça pour moi. Faites-le comme vous le voulez. Je sais juste que je veux jeûner. Voilà votre défi pour cette semaine. Vous les gars, nous allons pour vous donner une tâche. Nous allons vous donner un défi. Et puis, il est à vous les gars complètement juste comprendre ce qui est le plus rapide et le plus moyen efficace de mettre en œuvre cette. Ouais? AUDIENCE: Sommes-nous autorisés à se voulait la recherche des moyens plus rapides à faire des tables de hachage en ligne, nous pouvons faire que et de citer le code de quelqu'un d'autre? ANDI PENG: Oui, tout à fait bien. Donc, si vous les gars lire les spec, il ya une ligne dans la spécification qui dit que vous les gars sont totalement libre à la recherche hachage fonctions sur ce que sont certains des fonctions de hachage rapides faire tourner les choses à travers comme Tant que vous citez ce code. Ainsi, certaines personnes ont déjà compris des moyens rapides de faire des correcteurs d'orthographe, de la restauration rapide des moyens de stockage d'informations. Totalement à vous les gars si vous vouloir prendre tout ça, non? Assurez-vous que vous citez. Le défi ici vraiment que nous essayons de tester est de faire en sorte que vous savez votre chemin autour de pointeurs. Pour autant que vous la mise en œuvre la fonction réelle de hachage et à venir avec comme le calcul pour le faire, vous les gars peuvent faire des recherches quelle que soit méthodes en ligne vous les gars veulent. Ouais? AUDIENCE: Pouvons-nous citer que en utilisant le [inaudible]? ANDI PENG: Ouais. Vous pouvez tout simplement, dans votre commentaire, vous pouvez citer comme, oh, prise de bla, bla, yada, fonction de hachage. Quelqu'un at-il des questions? Nous avons en fait en coup de vent à travers la section aujourd'hui. Je serai ici à répondre à des questions aussi. Aussi, comme je le disais, bureau heures ce soir et demain. La spécification de cette semaine est en fait super facile et super court à lire. Je vous conseillerais de prendre un coup d'oeil, juste lire l'intégralité de celui-ci. Et Zamyla vous guide fait à travers chacune des fonctions vous avez besoin de mettre en œuvre, et il est donc très, très clair tout faire. Juste pour vous assurer que vous êtes garder la trace des pointeurs. Ceci est un jeu de processeurs très difficile. Ça ne conteste pas parce que, comme, oh, les concepts sont tellement plus difficile, ou que vous avez à apprendre tellement nouvelle syntaxe la manière que vous avez fait pour la dernière pset. Cette pset est difficile parce que il ya tellement de pointeurs, puis il est très, très facile à la fois vous avez un bogue dans votre code ne pourra pas pour trouver où est ce bug. Et si complète et la foi absolue en vous les gars pour être en mesure de battre notre [inaudible] orthographes. Je dois en fait pas une mine écrite encore, mais je suis en train d'écrire le mien. Ainsi, alors que vous écrivez vôtre, je vais écrire le mien. Je vais essayer de faire la mine plus rapide que le vôtre. Nous allons voir qui a le plus rapide d'un. Et ouais, je vais voir tout vous les gars ici mardi. Je vais lancer un type comme un atelier de pset. Toutes les sections ce semaine sont des ateliers de pset, de sorte que vous les gars avez beaucoup de possibilités de l'aide, les heures de bureau, comme toujours, et je vraiment hâte de lire tous le code de vos gars. Je dois quiz ici si vous les gars veulent venir obtenir ces. C'est tout.