[Lecture de musique]
ENCEINTE 1: Très bien.
Tout le monde souhaite un bon retour à la section.
Je vous souhaite à tous êtes avec succès récupéré de votre quiz
de la semaine dernière.
Je sais qu'il est un peu fou parfois.
Comme je le disais avant, si vous êtes à l'intérieur de l'écart-type,
ne vous inquiétez pas vraiment à ce sujet, en particulier pour une section moins à l'aise.
Voilà à peu près où vous devriez être.
>> Si vous avez fait une grande, alors impressionnant.
Bravo à vous.
Et si vous vous sentez comme vous avez besoin un peu plus d'aide, se il vous plaît
hésitez pas à atteindre sur l'une quelconque des TF.
Nous sommes tous ici pour aider.
>> Voilà pourquoi nous enseignons.
Voilà pourquoi je suis ici chaque lundi pour vous les gars et à les heures de bureau le jeudi.
Ainsi se il vous plaît sentez-vous libre pour me faire savoir si vous êtes inquiet au sujet quoi que ce soit
ou si il ya quelque chose sur le quiz que vous voulez vraiment faire face.
>> Donc, l'ordre du jour d'aujourd'hui est tout sur les structures de données.
Certains d'entre eux vont tout simplement être juste pour aideront à vous familiariser avec ces derniers.
Vous ne pouvez jamais mettre en œuvre les dans cette classe.
Certains d'entre eux vous voulez, comme pour votre correcteur orthographique pset.
>> Vous aurez le choix entre les tables et tente hachage.
Donc, nous allons certainement aller sur ceux-ci.
Ça va être certainement plus de genre d'une section de haut niveau aujourd'hui, cependant,
car il ya beaucoup d'entre eux, et si nous sommes allés dans les détails de mise en œuvre
sur l'ensemble de ceux-ci, nous ne serions pas même passer à travers les listes chaînées
et peut-être un peu de tables de hachage.
>> Donc garder avec moi.
Nous ne sommes pas allez faire autant de codage pour le moment.
Si vous avez des questions à ce sujet ou si vous voulez le voir mis en œuvre
ou essayer par vous-même, Je recommande vraiment
aller à study.cs50.net, qui a des exemples de tout cela.
Il va falloir mes présentations PowerPoint avec les notes que nous
ont tendance à utiliser ainsi que certains programmes exercices, en particulier pour les choses
comme les listes chaînées et binaire Arbres piles et les indices.
Donc peu au plus haut niveau, qui pourrait être agréable pour vous les gars.
>> Donc, avec cela, nous allons commencer.
Et aussi, des quiz yes--.
Je pense que la plupart d'entre vous qui sont dans ma section ont vos tests,
mais quelqu'un vient ou une raison quelconque vous ne sont pas, ils sont ici à l'avant.
>> Donc lié listes.
Je sais que ce genre de passe à sauvegarder avant votre quiz.
Ce fut la semaine avant que nous avons appris à ce sujet.
Mais dans ce cas, nous allons simplement aller un peu plus en profondeur.
>> Alors, pourquoi pourrions-nous choisir un liste chaînée sur un tableau?
Qu'est-ce qui les distingue?
Oui?
>> PUBLIC: Vous pouvez développer un lien la liste par rapport à la taille fixe d'un tableau.
ENCEINTE 1: Droit.
Un tableau a taille fixe alors un liste liée a une taille variable.
Donc, si nous ne savons pas comment beaucoup nous voulons stocker,
une liste chaînée nous donne une grande façon de le faire parce que nous pouvons seulement
ajouter sur un autre nœud et ajouter sur un autre nœud et ajouter sur un autre noeud.
Mais ce qui pourrait être un compromis?
Quelqu'un se souvient le compromis entre les tableaux et les listes chaînées?
Mmhmm?
>> Public: Vous devez passer par tout le chemin
à travers la liste chaînée trouver un élément dans une liste.
Dans un tableau, vous pouvez il suffit de trouver un élément.
>> ENCEINTE 1: Droit.
Donc, avec arrays--
>> PUBLIC: [inaudible].
>> ENCEINTE 1: Avec les tableaux, nous avons ce qu'on appelle l'accès aléatoire.
Signifie que si nous voulons ce qui est jamais le cinquième point de la liste
ou le cinquième point de notre tableau, nous suffit de la saisir.
Si il est une liste chaînée, nous avons pour parcourir, non?
Ainsi, l'accès à un élément en un tableau est la constante de temps,
alors avec une liste chaînée il serait probablement parce que peut-être temps linéaire
notre élément est tout le chemin à la fin.
Nous devons chercher à travers tout.
Donc, avec toutes ces données structures que nous allons
à dépenser un peu plus de temps, quels sont les avantages et les inconvénients.
Quand pourrions-nous vouloir utiliser l'un sur l'autre?
Et qui est le genre de plus grand chose à emporter.
>> Nous avons donc ici la définition d'un noeud.
Il est comme un élément notre liste liée, non?
Donc, nous sommes tous familiers avec nos struct typedef,
qui nous sommes allés en revue la dernière fois.
Il était tout simplement de la création un autre type de données que nous pourrions utiliser.
>> Et dans ce cas, il est un nœud qui tiendra un entier dans.
Et puis ce qui est de la deuxième partie ici?
Tout le monde?
>> PUBLIC: [inaudible].
>> ENCEINTE 1: Ouais.
Il est un pointeur vers le noeud suivant.
Ce qui devrait être fait ici.
Ceci est un pointeur de type nœud à la chose suivante.
Et qui est ce qu'ils englobe notre nœud.
Laisser refroidir.
>> Très bien, alors à la recherche, comme nous étions juste dire avant la main, si vous êtes
en passant par de la recherche, vous devez en fait itérer
à travers votre liste chaînée.
Donc, si nous sommes à la recherche pour le nombre 9, nous commencerions à notre siège
et que nous montre au début de notre liste liée, non?
Et nous disons, OK, est-ce noeud contient le numéro 9?
Non?
>> Tout droit, passer à la suivante.
Suivez-le.
Contient-il le numéro 9?
Non.
Suivre la suivante.
>> Nous devons donc en fait une itération à travers notre liste chaînée.
Nous ne pouvons pas aller directement à l'endroit où 9 est.
Et si vous les gars veulent vraiment voir pseudo-code là-haut.
Nous avons une fonction de recherche ici qui prend in-- que faut-il en?
Que pensez-vous?
Si facile un.
Qu'est-ce que ce est?
PUBLIC: [inaudible].
ENCEINTE 1: Le nombre que nous recherchons.
Droit?
Et qu'est-ce que cela correspond à?
Il est un pointeur vers?
>> PUBLIC: Un noeud.
>> ENCEINTE 1: Un nœud à la liste que nous cherchons à, non?
Nous avons donc des nœuds sont pointeur ici.
Ceci est un point qui va en fait itérer sur notre liste.
Nous l'avons réglé égal à la liste parce que ce juste
sa mise en égale à la début de notre liste chaînée.
>> Et bien qu'il soit pas NULL, alors que nous avons encore des choses dans notre liste,
vérifier pour voir si ce nœud a le nombre que nous recherchons.
Retour vrai.
Sinon, mettre à jour, non?
>> Si elle est nulle, nous sortons de notre boucle while et return false
parce que cela signifie que nous avons pas trouvé.
Est-ce que tout le monde se comment cela fonctionne?
D'accord.
>> Donc, avec insertion, vous faire de trois manières différentes.
Vous pouvez faire précéder, vous pouvez ajouter et vous pouvez insérer dans assorties.
Dans ce cas, nous sommes va faire un préfixe.
Est-ce que quelqu'un sait comment ceux trois cas peuvent différer?
>> Donc préfixe signifie que vous mettez il à l'avant de votre liste.
Donc, cela voudrait dire que peu importe ce que votre noeud est, peu importe
quelle est la valeur, vous allez de le mettre ici en face, OK?
Ça va être le premier élément dans votre liste.
>> Si vous ajoutez, il va pour aller à l'arrière de votre liste.
Et l'insérer dans un assortiment signifie que vous êtes va mettre réellement dans le lieu
où il maintient votre liste chaînée triée.
Encore une fois, la façon dont vous utilisez ceux et lorsque vous utilisez
les varieront en fonction de votre cas.
Si elle n'a pas besoin de être triés, préfixe tend
être ce que la plupart des gens utiliser parce que vous ne
avoir à passer par la liste complète pour trouver la fin de l'ajouter, non?
Vous pouvez simplement coller en plein.
>> Nous allons donc passer par une insertion 1 en ce moment.
Donc, une chose que je vais recommande fortement sur cette pset
est de tirer les choses, comme toujours.
Il est très important que vous mettez à jour vos pointeurs dans le bon ordre
parce que si vous mettez à jour les un peu hors de l'ordre,
vous allez finir par perdre des parties de votre liste.
>> Ainsi, par exemple, dans ce cas, nous sommes dire la tête à tout moment à 1.
Si nous faisons tout ce que sans enregistrer cette 1,
nous ne savons pas ce que 1 doit pointer maintenant
parce que nous avons perdu ce que la tête souligné.
Donc, une chose à retenir lorsque vous faites un préfixe
est de sauver ce qui le points de la tête à la première,
puis le réaffecter, puis mettre à jour ce que votre nouveau nœud doit pointer vers.
Dans ce cas, cela est une façon de le faire.
>> Donc, si nous avions fait de cette façon où nous venons de redéploiement de la tête,
nous perdons notre fondamentalement liste entière, non?
Une façon de le faire est d'avoir 1 point à prochaine, et alors point de tête à 1.
Ou vous pouvez faire un peu comme le stockage temporaire, dont je parlais.
>> Mais réaffectation votre pointeurs dans le bon ordre
va être très, très important pour ce jeu de processeurs.
Sinon, vous allez avoir une table de hachage table ou un essai qui vient va être
une partie seulement des mots que vous veulent et puis you're-- mmhmm?
Public: Quel a été le temporaire chose de stockage dont vous parliez?
ENCEINTE 1: Le stockage temporaire.
Donc, fondamentalement, un autre comme vous pouvez le faire
est stocker la tête de quelque chose, comme stocker la variable temporaire.
Assigner à 1 et puis mettre à jour 1 au point
à ce que la tête utilisé pour pointer.
De cette manière, est évidemment plus élégant parce que vous
ne pas avoir besoin d'une valeur temporaire, mais tout simplement d'offrir une autre façon de le faire.
Et nous avons effectivement un code pour cela.
Donc, pour la liste chaînée, nous avoir fait un peu de code.
Donc insérer ici, ce sont précéder.
Donc cette entrée à la tête.
>> Donc, première chose, vous devez créer votre nouveau nœud, bien sûr,
et vérifier la valeur NULL.
Toujours bon.
Et puis, vous devez affecter les valeurs.
Chaque fois que vous créez un nouveau nœud, vous ne sait pas ce qu'il pointe vers la prochaine,
si vous voulez initialiser à NULL.
Si elle ne finissent pointant vers quelque chose autre, il se réaffecté et il est très bien.
Si elle est la première chose dans la liste, il faut
au point sur null qui est la fin de la liste.
>> Alors pour l'insérer, nous voyons ici nous affectez la valeur suivante de notre nœud
à être ce que la tête est, qui est ce que nous avions ici.
Voilà ce que nous venons de faire.
Et puis nous sommes tête à un point attribuant à notre nouveau nœud, car rappelez-vous,
nouveau est quelque pointeur vers un noeud, et qui est exactement ce que la tête est.
Voilà exactement pourquoi nous avoir cette flèche accesseur.
Cool?
Mmhmm?
>> PUBLIC: Devons-nous initialiser un nouveau à côté de la valeur NULL première,
ou pouvons-nous simplement initialiser à la tête?
>> ENCEINTE 1: New prochaine doit être NULL pour commencer
parce que vous ne savez pas où il va être.
En outre, ce type est de Tout comme un paradigme.
Vous définissez égale à NULL juste pour faire assurer que toutes vos bases sont couvertes
avant de faire toute réaffectation de sorte que vous êtes toujours garanti que le
pointer sur une valeur spécifique par rapport à une valeur comme des ordures.
Parce que, oui, nous attribuons NOUVEAU automatiquement,
mais il est plus juste comme un bonnes pratiques pour l'initialiser
de cette façon et puis réaffecter.
>> OK, donc doublement lié listes maintenant.
Que pensons-nous?
Ce qui est différent avec doublement des listes chaînées?
>> Ainsi, dans nos listes chaînées, nous pouvons seulement se déplacer dans une direction, non?
Nous avons seulement à côté.
Nous ne pouvons aller de l'avant.
>> Avec une liste doublement chaînée, nous pouvons également revenir en arrière.
Donc, nous avons non seulement la nombre que nous voulons stocker,
nous avons où il pointe prochaine et où nous venons de.
Donc, ce qui permet de certains mieux traversée.
>> Nœuds donc doublement chaînées, très similaire, non?
La seule différence est maintenant que nous avoir un côté et un précédent.
Il est la seule différence.
>> Donc, si nous étions à précéder ou append-- nous ne pas avoir de code de cette place ici--
mais si vous deviez essayer et insérer, l'important
est que vous devez faire que vous affectez
à la fois votre précédente et votre pointeur suivant correctement.
Donc dans ce cas, vous feriez non seulement l'initialisation suivante,
l'initialisation précédente.
Si nous sommes à la tête de la liste, nous non seulement tenir tête égale nouvelle,
mais si notre nouvelle précédente pointer vers la tête, non?
>> Voilà la seule différence.
Et si vous voulez plus pratique avec ceux-ci avec les listes chaînées, avec insertion,
avec la suppression, avec insert dans une liste assortis,
se il vous plaît vérifier study.cs50.net.
Il ya un tas de grands exercices.
Je les recommande fortement.
Je souhaite que nous ayons le temps de les parcourir mais il ya beaucoup de structures de données
pour passer à travers.
>> OK, donc les tables de hachage.
Ceci est probablement la plus peu utile pour votre pset
ici parce que vous allez être mise en œuvre de l'un d'eux, ou un essai.
Je l'aime vraiment les tables de hachage.
Ils sont plutôt sympas.
>> Donc, fondamentalement, ce qui se passe est une table de hachage
est quand nous avons vraiment besoin rapide insertion, délétion, et recherche.
Ce sont les choses que nous sommes priorité à une table de hachage.
Ils peuvent devenir assez grand, mais comme nous le verrons avec essais,
il ya des choses qui sont beaucoup plus gros.
>> Mais fondamentalement, tout un hachage table est une fonction de hachage
qui vous dit qui seau de mettre chaque de vos données, chacun de vos éléments.
Une façon simple de penser à une table de hachage est qu'il est seulement seaux de choses,
droit?
Ainsi, lorsque vous triez les choses par comme la première lettre de leur nom,
qui est un peu comme une table de hachage.
>> Alors vous les gars si je devais groupe est en groupes de quiconque son nom commence
avec un cours ici, ou celui qui est l'anniversaire est en Janvier, Février, Mars,
que ce soit, qui est efficace la création d'une table de hachage.
Il est juste que la création de seaux vous triez vos éléments en
de sorte que vous pouvez les trouver plus facilement.
Ainsi de cette façon quand je dois pour trouver l'un de vous,
Je ne dois pas chercher par chacun de vos noms.
Je peux être comme, oh, je sais que L'anniversaire de Danielle est in--
PUBLIC: --April.
ENCEINTE 1: Avril.
Donc, je regarde dans ma Avril seau, et avec un peu de chance,
elle sera le seul là-bas et mon temps est constante en ce sens,
alors que si je dois regarder par tout un tas de gens,
ça va prendre beaucoup plus de temps.
Donc, tables de hachage ne sont réellement que des seaux.
Un moyen facile de penser à eux.
>> Donc, une chose très importante à propos une table de hachage est une fonction de hachage.
Donc, les choses que je viens de parler, comme votre première lettre de votre prénom
ou mois de votre anniversaire, ce sont des idées que
vraiment en corrélation avec une fonction de hachage.
Il est juste une façon de décider qui vous êtes la seau élément va dans, OK?
Donc, pour ce jeu de processeurs, vous pouvez rechercher à peu près toutes les fonctions de hachage que vous voulez.
>> Ne pas avoir à être votre propre.
Il y en a de vraiment cool sur il que font toutes sortes de mathématiques fou.
Et si vous voulez faire de votre correcteur orthographique super rapide,
I would definitely se pencher sur l'un de ceux.
>> Mais il ya aussi la les plus simples, comme calcul
la somme des mots, comme chaque lettre a un certain nombre.
Calculer la somme.
Qui détermine le godet.
Ils ont aussi les plus faciles que sont comme tous les A ici,
tous les B est ici.
L'un de ceux.
>> Fondamentalement, il vous indique juste que index de tableau de votre élément devrait aller en.
Il suffit de décider de la bucket-- tout est une fonction de hachage est.
Nous avons donc ici un exemple qui est que la première lettre de la chaîne
que je viens de parler.
>> Donc, vous avez une table de hachage qui est juste la première lettre de votre chaîne moins un,
qui vous donnera une nombre entre 0 et 25.
Et ce que vous voulez faire est veiller à ce que cela représente
la taille de votre hachage table-- combien il ya des godets.
Avec un grand nombre de ceux-ci Les fonctions de hachage, ils sont
va être le retour des valeurs qui pourraient être bien au-dessus du nombre de seaux
que vous avez fait dans votre table de hachage,
si vous avez besoin de faire sûr et mod par ceux-ci.
Sinon, il va dire, oh, il devrait être dans un seau 5000
mais vous avez seulement 30 seaux à votre table de hachage.
Et bien sûr, nous savons tous que ce va donner lieu à des erreurs folles.
Donc, assurez-vous de mod par la taille de votre table de hachage.
Laisser refroidir.
Donc collisions.
Tout le monde est bon à ce jour?
Mmhmm?
>> Public: Pourquoi ne serait-il retourner cette valeur massif?
>> ENCEINTE 1: Selon l'algorithme que votre fonction de hachage utilise.
Certains d'entre eux faire multiplication fou.
Et il est tout à obtenir une répartition,
de sorte qu'ils ne vraiment quelque parfois des choses folles.
Ce est tout.
Rien d'autre?
D'accord.
>> Donc collisions.
Au fond, comme je l'ai dit plus tôt, dans le meilleur des cas,
tout seau je regarde dans est va avoir une chose,
donc je ne dois pas regarder du tout, non?
Je sais que ce soit est là ou ce est pas, et que ce que nous voulons vraiment.
Mais si nous avons des dizaines de milliers de points de données et de moins de ce nombre
des seaux, nous allons avoir collisions où finalement quelque chose
va avoir à se retrouver dans un seau qui a déjà un élément.
>> Donc la question est, qu'est-ce faisons-nous dans ce cas?
Que faisons-nous?
Nous avons déjà quelque chose?
Devons-nous juste le jeter?
>> Non.
Nous devons garder les deux.
Ainsi, la manière que nous typiquement le faire est ce?
Quelle est la structure de données nous venons de parler?
PUBLIC: liste chaînée.
ENCEINTE 1: Une liste chaînée.
Donc, maintenant, à la place de chacun de ceux-ci seaux avoir un seul élément,
il va contenir une liste chaînée de les éléments qui ont été hachés en elle.
OK, tout le monde ne sorte de rendre cette idée?
Parce que nous ne pouvions pas avoir un tableau parce que nous ne savons pas combien de choses
vont être là.
Une liste chaînée nous permet de avoir juste le nombre exact que
sont hachés dans le seau, non?
>> Donc linéaire palpage essentiellement ce idea--
il est une façon de faire face à une collision.
Ce que vous pouvez faire est de savoir si, dans ce cas, Berry a été haché dans 1
et nous avons déjà quelque chose, que vous venez de
continuer jusqu'à ce que vous trouverez un emplacement vide.
Voilà une façon de le gérer.
L'autre façon de gérer il est avec ce que nous venons
called-- le lien liste est appelée chaînage.
>> Donc, cette idée fonctionne si votre table de hachage vous pensez
est beaucoup plus grande que vos données définies ou si vous
vouloir tenter de minimiser le chaînage jusqu'à ce qu'il soit absolument nécessaire.
Donc, une chose est linéaire sondage signifie évidemment
que votre fonction de hachage est pas tout à fait comme utile
parce que vous allez finir par utiliser votre fonction de hachage, se rendre à un point,
vous sondez linéaire jusqu'à un endroit qui est disponible.
Mais maintenant, bien sûr, rien d'autre qui se termine là-haut,
vous allez avoir à recherche encore plus loin.
>> Et il ya beaucoup plus Recherche frais que
va entrer dans un élément dans votre table de hachage maintenant, non?
Et maintenant quand vous allez essayer de trouver Berry à nouveau, vous allez hacher,
et il va dire, oh, regardez dans le seau 1,
et il ne va pas être dans le seau 1, de sorte que vous êtes
allez avoir à traverser sur le reste de ceux-ci.
Donc, il est parfois utile, mais dans la plupart des cas,
nous allons dire que chaînage est ce que vous voulez faire.
>> Donc nous en avons parlé plus tôt.
Je suis un peu en avance sur moi-même.
Mais chaînage est essentiellement que chaque seau dans votre table de hachage
est juste une liste chaînée.
>> Un autre moyen, plus ou technique Ainsi, de penser à une table de hachage
est qu'il est juste un tableau des listes chaînées, qui
quand vous écrivez votre dictionnaire et vous essayez de le charger,
penser comme un tableau de listes chaînées
il sera beaucoup plus facile pour vous d'initialiser.
>> Auditoire: Alors table de hachage a une taille prédéterminée,
comme un [inaudible] de seaux?
>> ENCEINTE 1: Droit.
Ainsi, il a un certain nombre de seaux que vous determine--
qui vous les gars devraient hésitez pas à jouer avec.
Il peut être assez cool pour voir ce qui se passe
que vous changez votre numéro de seaux.
Mais oui, il a une définir le nombre de seaux.
Qu'est-ce que vous permet d'ajuster comme autant d'éléments que vous avez besoin
est ce chaînage séparé où vous ont lié les listes dans chaque seau.
Cela signifie que votre table de hachage sera exactement la taille
que vous en avez besoin pour être, non?
Voilà tout l'intérêt de listes chaînées.
Laisser refroidir.
>> Donc, tout le monde il OK?
Bien.
Ah.
Qu'est-ce que vient de se passer?
Vraiment maintenant.
Devinez quelqu'un me tue.
>> OK, nous allons entrer dans essais, qui sont un peu fou.
Je l'aime tables de hachage.
Je pense qu'ils sont vraiment cool.
Essais sont cool, trop.
>> Donc ce que quelqu'un se rappeler ce un essai est?
Vous devriez avoir dépassé brièvement dans la leçon?
Vous souvenez-vous de sorte comment cela fonctionne?
PUBLIC: Je suis juste un signe de tête que nous sommes allés au-dessus.
ENCEINTE 1: On ne va dessus.
OK, nous allons vraiment aller plus il est maintenant ce que nous disons.
>> PUBLIC: Voilà pour un arbre de recherche.
>> ENCEINTE 1: Ouais.
Il est un arbre de recherche.
Impressionnant.
Donc, une chose à noter ici est que nous sont à la recherche à des caractères individuels
ici, non?
>> Alors avant avec notre fonction de hachage, nous étaient à la recherche sur les mots dans son ensemble,
et maintenant nous sommes à la recherche de plus les personnages, non?
Nous avons donc ici Maxwell et Mendel.
Donc, fondamentalement, un try-- une façon de penser à ce sujet est que chaque niveau ici
est une série de lettres.
Donc ceci est votre noeud racine ici, non?
Ceci présente tous les caractères de la alphabet pour le début de chaque mot.
>> Et ce que vous voulez faire est par exemple, OK, nous avons un mot M.
Nous allons chercher Maxwell, si nous allons à M. et M des points à un ensemble
autre un tableau où chaque mot, tant qu'il n'y
est un mot qui a une que la seconde lettre,
aussi longtemps que il ya un mot qui B a la deuxième lettre,
elle aura un pointeur aller d'un tableau à côté.
>> Il n'y a probablement pas un mot que MP quelque chose,
si à la position P en ce tableau, il serait tout simplement NULL.
Il dit, OK, il n'y a pas de mot qui a M suivie par un P, OK?
Donc, si nous pensons à ce sujet, chaque l'un de ces petits choses
est en fait un de ces grands tableaux de A à Z.
Donc, ce qui pourrait être l'une des choses qui est une sorte de inconvénient d'un essai?
>> PUBLIC: A beaucoup de mémoire.
>> ENCEINTE 1: Il ya une tonne de mémoire, non?
Chacun de ces blocs ici représente 26 places, 26 élément tableau.
Donc essais se incroyablement espace lourd.
>> Mais ils sont très rapides.
Incroyablement rapide mais vraiment espace inefficace.
Type d'avoir à comprendre celle que vous voulez.
Ce sont vraiment cool pour votre pset, mais ils prennent beaucoup de mémoire,
si vous négociez off.
Ouais?
>> PUBLIC: Serait-il possible de mettre en place un essai et ensuite
une fois que vous avez toutes les données dans ce que vous need--
Je ne sais pas si ce serait logique.
Je commençais à me débarrasser de toutes les Caractères NULL, mais
vous ne seriez pas en mesure d'indexer eux--
>> ENCEINTE 1: Vous devez toujours leur.
>> PUBLIC: - de la même façon à chaque fois.
ENCEINTE 1: Ouais.
Vous avez besoin des caractères NULL à laisser vous savez si il n'y a pas un mot là.
Ben ne vous avez quelque chose que vous voulez?
D'accord.
Très bien, nous allons donc d'aller un peu plus
dans le détail technique derrière essayer et travailler à travers un exemple.
>> OK, si cela est la même chose.
Alors que dans une liste chaînée, notre principal genre de-- quel est le mot que je veux? -
comme bloc de construction était un nœud.
Dans un essai, nous avons aussi un nœud, mais il est défini différemment.
>> Nous avons donc une certaine bool que représente en fait si un mot
existe à cet endroit, et puis nous avons une gamme ici-- ou plutôt,
ceci est un pointeur sur un tableau de 27 caractères.
Et ceci est pour, dans ce cas, cette 27-- Je suis sûr que vous êtes tous comme, attends,
il ya 26 lettres dans l'alphabet.
Pourquoi avons-nous 27?
>> Ainsi, en fonction de la comme vous le mettre en œuvre,
cela est d'un ensemble de processeurs que permis pour apostrophes.
Voilà pourquoi l'un de plus.
Vous aurez également à certains cas, le terminateur null
est inclus comme l'un des caractères qu'il est autorisé à être,
et voilà comment ils vérifient voir si elle est la fin du mot.
Si vous êtes intéressé, consultez La vidéo de Kevin sur study.cs50,
ainsi que Wikipedia a quelques bonnes ressources là-bas.
>> Mais nous allons passer par tout genre de la façon dont vous pouvez travailler à travers un essai
si on vous donne un.
Donc, nous avons un super-simple ici que a les mots "chauve-souris" et "zoom" en eux.
Et comme nous le voyons ici, ce petit espace ici
représente notre bool que dit, oui, cela est un mot.
Et puis cela a notre des tableaux de caractères, non?
>> Donc, nous allons passer par trouver "chauve-souris" dans cette tentative.
Donc, commencer par le haut, à droite?
Et nous savons que b correspond à le second index, le deuxième élément
dans ce tableau, parce que a et b.
Ainsi, approximativement la seconde.
>> Et il dit, OK, cool, suivre que dans le tableau suivant, parce que si nous nous souvenons,
il est pas que chacun de ceux-ci contient en fait l'élément.
Chacun de ces tableaux contient un pointeur, non?
Il est une distinction importante à faire.
>> Je sais que cela va être-- essais sont vraiment difficile d'obtenir sur la première fois,
même si cela est le deuxième ou troisième fois
et il est encore un peu de paraître difficile,
Je promets si vous allez montre court à nouveau demain,
il va probablement faire beaucoup plus de sens.
Il en faut beaucoup pour digérer.
Je suis encore parfois comme, attendez, ce qui est un essai?
Comment puis-je l'utiliser?
>> Nous avons donc b Dans ce cas, qui est notre deuxième indice.
Si nous avions, par exemple, ou c d ou toute autre lettre,
nous avons besoin de la carte que revenir à l'index de notre gamme que cela correspond à.
Nous serions donc prendre comme rchar et nous avons soustraire de un à map dans 0 à 25.
Tout le monde bien comment nous la carte de nos personnages?
D'accord.
>> Donc, nous allons à la seconde et nous voir que, oui, il est pas à NULL.
Nous pouvons passer à la prochaine série.
Donc, nous passons à la prochaine série ici.
>> Et nous disons, OK, maintenant nous besoin de voir si un est ici.
Une valeur NULL ou est-ce en fait aller de l'avant?
Ainsi, une se déplace effectivement transmettre dans ce tableau.
Et nous disons, OK, t est notre dernière lettre.
Donc, nous allons à la t à l'index.
Et puis nous allons de l'avant parce qu'il ya une autre.
Et celui-ci dit essentiellement que, oui, il dit qu'il ya un mot ici--
que si vous suivez cette chemin, vous êtes arrivés
à un mot, que nous connaissons est «chauve-souris».
Oui?
>> Public: Est-ce que la norme d'avoir comme l'indice 0 et alors une sorte à 1
ou d'avoir à la fin?
>> ENCEINTE 1: Non
Donc, si nous regardons en arrière à notre déclaration ici, il est un booléen,
il est donc son propre élément dans votre nœud.
Donc, il ne fait pas partie du tableau.
Laisser refroidir.
Donc, lorsque nous aurons terminé notre parole et nous sommes à ce tableau, ce que nous voulons faire
est faire un chèque de est-ce un mot.
Et dans ce cas, il reviendrait oui.
>> Donc, sur cette note, nous savons que "zoo" - nous savons que les humains qui "zoo" est un mot,
droit?
Mais sont essayer ici serait dire, non, il est pas.
Et ce serait dire que parce que nous ne pas avoir désigné comme un mot ici.
Même si nous pouvons traverser grâce à cette matrice,
cette tentative serait dire que, non, zoo est pas dans votre dictionnaire
parce que nous avons pas désigné comme tel.
>> Donc, une façon de faire that-- Oh, désolé, celui-ci.
Donc dans ce cas, "zoo" est pas un mot, mais il est dans notre essai.
Mais dans celui-ci, disons que nous voulons introduire le mot «bain», ce qui se passe
nous suivons est through-- b, a, t.
Nous sommes dans ce tableau, et nous allons à la recherche de h.
>> Dans ce cas, quand on regarder le pointeur à h,
il pointe vers NULL, OK?
Donc, sauf si elle est explicitement pointant vers un autre tableau,
vous supposez que tous les pointeurs dans ce tableau sont pointant vers null.
Donc dans ce cas, h pointe null si nous ne pouvons rien faire,
de sorte qu'il serait aussi revenir faux, "bain" est pas ici.
Alors maintenant, nous sommes en fait va passer par
comment pourrions-nous réellement dire que "zoo" est dans notre essai.
Comment pouvons-nous insérons "zoo" dans notre essai?
Donc, de la même façon que nous avons commencé avec notre liste chaînée, on commence à la racine.
En cas de doute, commencer à l'origine de ces choses.
>> Et nous disons, OK, z.
z existe dans ce domaine, et il le fait.
Donc, vous vous déplacez à votre prochain tableau, OK?
Et puis sur la suivante, nous disons, OK, ne o existe?
Il ne.
Ce nouveau.
>> Et ainsi de suite notre prochain, nous l'avons dit, OK, "zoo" existe déjà ici.
Tout ce que nous devons faire est de définir cette égalité à vrai qu'il ya un mot là.
Si vous aviez suivi tout jusqu'à avant ce moment,
il est un mot, si juste Le mettre à tel.
Oui?
>> AUDIENCE: le fait alors que signifie que «ba» est un mot aussi?
>> ENCEINTE 1: Non
Donc dans ce cas, "ba" nous aurions ici, nous dirions qu'il est un mot,
et il serait toujours pas.
D'accord?
Mmhmm?
>> Auditoire: Alors, une fois que vous est-il un mot et vous dites oui, alors il
contiendra d'aller à m?
>> ENCEINTE 1: Donc cela a à voir with-- vous chargez ce dans.
Vous dites "zoo" est un mot.
Quand vous allez à check-- comme, disons que vous voulez dire,
existe "zoo" dans ce dictionnaire?
Vous allez seulement à la recherche de "zoo" et puis vérifier pour voir si elle est un mot.
Vous ne réussirez jamais à se déplacer jusqu'à m parce que ce ne
ce que vous cherchez.
>> Donc, si nous voulions vraiment ajouter «bain» dans cette tentative,
nous ferions la même chose comme nous l'avons fait avec "zoo"
sauf que nous verrions que lorsque nous essayer d'obtenir à h, il ne existe pas.
Ainsi, vous pouvez penser à ce que d'essayer d'ajouter un nouveau nœud dans une liste chaînée,
de sorte que nous aurions besoin d'ajouter un autre l'un de ces tableaux, comme si.
Et puis ce que nous faisons est que nous venons de mettre la h élément de ce tableau montrant ce.
>> Et puis quoi voudrions-nous faire ici?
Ajoutez égale à vrai car il est un mot.
Laisser refroidir.
Je sais.
Essais ne sont pas le plus excitant.
Croyez-moi, je sais.
>> Donc, une chose à réaliser avec essais, Je l'ai dit, ils sont très efficaces.
Donc, nous avons vu qu'ils prendre une tonne d'espace.
Ils genre de confusion.
Alors, pourquoi aurions-nous jamais les utiliser?
Nous utilisons ces parce qu'ils sont incroyablement efficace.
>> Donc, si jamais vous êtes à la recherche un mot, vous êtes seulement
limitée par la longueur du mot.
Donc, si vous êtes à la recherche d'un mot qui est d'une longueur de cinq ans,
vous ne jamais devoir faire dans la plupart des cinq comparaisons, OK?
Et il est donc essentiellement une constante.
Comme insertion et lookup sont essentiellement constante de temps.
>> Donc, si vous pouvez toujours obtenir quelque chose en temps constant,
qui est aussi bon qu'il obtient.
Vous ne pouvez pas faire mieux que constante de temps pour ces choses.
Voilà donc l'un des d'énormes avantages d'essais.
>> Mais il ya beaucoup d'espace.
Donc, vous avez genre de décider ce qui est plus important pour vous.
Et sur les ordinateurs d'aujourd'hui, la espace que d'essayer peut prendre jusqu'à
peut-être ne pas affecter vous tant que ça, mais peut-être
vous avez affaire à quelque chose qui a beaucoup, beaucoup plus de choses,
et un essai est tout simplement pas raisonnable.
Oui?
>> PUBLIC: Attendez, si vous avez 26 lettres à chacun?
>> ENCEINTE 1: Mmhmm.
Ouais, vous avez 26.
Vous avez quelque soit mot marqueur et puis vous avez 26 pointeurs de chacun.
Et ils point--
>> Public: Et tous les 26, ne ils ont chacun 26?
>> ENCEINTE 1: Oui.
Et voilà pourquoi, comme vous pouvez voir, il se dilate très rapidement.
Bien.
Donc, nous allons entrer dans les arbres, ce qui Je me sens comme il est plus facile et sera probablement
être un petit sursis à partir de là essais.
Donc, je l'espère plus de vous ont vu un arbre avant.
Pas comme la jolie ceux à l'extérieur, que je
Je ne sais pas si quelqu'un est allé à l'extérieur récemment.
Je suis allé cueillir des pommes ce week-end, et oh mon dieu, elle était très belle.
Je ne savais pas feuilles pourrait regarder cette jolie.
>> Donc, ceci est juste un arbre, non?
Il est juste un noeud, et il des points à un tas d'autres nœuds.
Comme vous le voyez ici, ce sont une sorte de thème récurrent.
Nœuds pointant vers des nœuds est une sorte de l'essence de plusieurs structures de données.
Tout dépend de la façon dont nous ont eux pointent à l'autre
et la façon dont nous traversons à travers eux et comment nous
insérer choses qui détermine leurs différentes caractéristiques.
>> Il suffit donc de la terminologie, que je l'ai utilisé avant.
Alors racine est tout ce qui est en haut.
il est où nous commençons toujours.
Vous pouvez penser que la tête aussi.
Mais pour les arbres, nous avons tendance à reportez-vous à ce que la racine.
>> Tout au fond ici-- à la très, très bottom--
sont considérés comme les feuilles.
Donc, il va de pair avec la chose d'arbres entiers, non?
Les feuilles sont sur les bords de votre arbre.
>> Et puis nous avons aussi un couple de termes pour parler de nœuds en relation
à l'autre.
Donc, nous avons des parents, enfants, frères et sœurs.
Donc dans ce cas, 3 est le mère de 5, 6, et 7.
Ainsi, le parent est tout ce qui est un cran au dessus que vous êtes
référence, si juste comme un arbre généalogique.
Heureusement, tout cela est un peu peu plus intuitive que les essais.
>> Les frères et sœurs sont celles qui ont le même parent, non?
Ils sont sur le même niveau ici.
Et puis, comme je l'étais dire, les enfants sont tout simplement
ce qui est un cran en dessous le nœud en question, OK?
Laisser refroidir.
Ainsi, un arbre binaire.
Quelqu'un peut hasarder une hypothèse sur l'un des les caractéristiques de l'arbre binaire?
>> PUBLIC: Max deux feuilles.
>> ENCEINTE 1: Droit.
Ainsi, deux feuilles de max.
Ainsi, dans celui-ci avant, nous avions celui-ci qui avait trois, mais dans un arbre binaire,
vous avez un maximum de deux enfants par mère, non?
Il ya un autre caractéristique intéressante.
Est-ce que quelqu'un sait qui?
Arbre binaire.
>> Ainsi, un arbre binaire aura tout sur the-- celui-ci est pas sorted--
mais dans un arbre binaire triés, tout à droite
est plus grand que le parent, et tout à gauche
est inférieure à la mère.
Et cela a été un quiz question avant, si bon à savoir.
Donc, la façon dont nous définissons ce, de plus, nous avons un autre nœud.
Cela semble très similaire à ce que?
Deux fois plus
>> PUBLIC: Lié listes
>> ENCEINTE 1: Un double liste liée, non?
Donc, si nous remplaçons cette avec précédente et suivante,
ce serait une liste doublement chaînée.
Mais dans ce cas, nous avons effectivement avoir gauche et à droite et voilà.
Sinon, il est exactement le même.
Nous avons toujours l'élément vous cherchez,
et vous avez juste deux pointeurs aller à tout ce qui est à côté.
Ouais, donc arbre binaire de recherche.
Si nous remarquons, tout sur le ici est plus than--
ou tout de suite à droite ici
est plus grande que, tout ici est moins.
>> Donc, si nous étions à la recherche à travers, il devrait être très proche de recherche binaire
ici, non?
Sauf qu'au lieu de regarder à la moitié du tableau,
nous cherchons simplement à soit la gauche côté ou le côté droit de l'arbre.
Ainsi, il devient un peu plus simple, je pense.
>> Donc, si votre racine est NULL, Évidemment, il est juste faux.
Et si elle est là, évidemment, il est vrai.
Si elle est inférieure, nous cherchons la gauche.
Si elle est supérieure à, nous cherchons la droite.
Il est exactement comme la recherche binaire, seulement une structure de données différente
que nous utilisons.
Au lieu d'un tableau, il est juste un arbre binaire.
>> OK, piles.
Et aussi, il semble que nous pourrait avoir un peu de temps.
Si nous le faisons, je suis heureux d'y aller sur tout cela de nouveau.
OK, donc piles.
Est-ce que quelqu'un se souvient de ce stacks-- des caractéristiques d'une pile?
>> OK, donc la plupart d'entre nous, je pense, manger dans la salle halls--
autant que nous pouvons ne pas aimer à.
Mais évidemment, vous pouvez penser à une pile littéralement comme une pile de plateaux
ou une pile de choses.
Et ce qui est important à réaliser est qu'il est
la caractéristique quelque chose-- que nous appelons by-- est LIFO.
Est-ce que quelqu'un sait ce qui représente?
Mmhmm?
>> PUBLIC: dernier entré, premier sorti.
>> ENCEINTE 1: Droit, dernier entré, premier sorti.
Donc, si nous le savons, si nous empiler les choses jusqu'à, la chose la plus facile à saisir off--
et peut-être la seule chose que nous pouvons saisir hors si notre pile est grand enough--
est que l'élément supérieur.
Donc tout ce que a été mis sur last-- comme nous le voyons ici,
tout ce qui était poussé sur plus recently-- est
va être le premier chose que nous crever, OK?
>> Donc, ce que nous avons ici est une autre structure typedef.
Ceci est vraiment comme un Crash Course dans la structure de données,
donc il ya beaucoup jeté à vous les gars.
Je sais.
Donc, encore une autre structure.
Yay pour les structures.
>> Et dans ce cas, il est certain pointeur à un tableau qui a une certaine capacité.
Donc, ce qui représente notre pile ici, comme notre tableau réel
qui est maintenant nos éléments.
Et puis ici nous avons une certaine taille.
>> Et généralement, vous voulez garder piste de la taille de votre pile est
parce que ça va permettre que vous fassiez est si vous connaissez la taille,
il vous permet de dire, OK, je suis à la capacité?
Puis-je ajouter quelque chose de plus?
Et il vous dit aussi où le haut de votre pile
est si vous savez ce que vous peut réellement décoller.
Et ce qui se passe réellement à être un peu plus clair.
>> Donc, pour pousser, une chose, si vous étaient toujours à mettre en œuvre poussée,
comme je viens de le dire, votre pile a une taille limitée, non?
Notre gamme avait une certaine capacité.
Il est un tableau.
Il est de taille fixe, donc nous avons besoin de faire en sorte que nous ne mettons pas plus
dans notre tableau de nous pour avoir effectivement espace.
>> Ainsi, lorsque vous créez un bouton fonction, la première chose que vous faites est de dire, OK,
je dois espace dans ma pile?
Parce que si je ne le fais pas, désolé, Je ne peux pas enregistrer votre élément.
Si je le fais, alors vous voulez stocker au sommet de la pile, non?
>> Et c'est pourquoi nous avons de garder une trace de notre taille.
Si nous ne gardons pas trace de notre taille, nous ne savons pas où le mettre.
Nous ne savons pas combien de choses sont dans notre gamme déjà.
Comme de toute évidence il existe des moyens peut-être que vous pourriez le faire.
Vous pouvez initialiser tout à NULL et puis vérifier la dernière NULL,
mais une chose beaucoup plus facile est juste à-dire, OK, garder une trace de taille.
Comme je sais que je dois quatre éléments dans mon tableau, donc la chose suivante
que nous mettons sur, nous sommes allez stocker à l'indice 4.
Et puis, bien sûr, cela signifie que vous avez réussi à pousser quelque chose
sur votre pile, vous vouloir augmenter la taille
de sorte que vous savez où vous êtes si que vous pouvez pousser plus de choses sur.
>> Donc, si nous essayons de pop quelque chose de la pile,
ce qui pourrait être la première chose que nous voulons vérifier?
Vous essayez de prendre quelque chose de votre pile.
Êtes-vous sûr qu'il ya quelque chose dans votre pile?
Non.
Alors que peut-on vouloir vérifier?
>> PUBLIC: [inaudible].
ENCEINTE 1: Vérifier la taille?
Taille.
Donc, nous voulons vérifier si notre taille est supérieur à 0, OK?
Et si elle l'est, nous voulons diminuer notre taille par 0 et le retourner.
Pourquoi?
>> Dans la première, nous étions pousser, nous avons poussé le
sur la taille et la taille puis mis à jour.
Dans ce cas, nous décrémentation taille et puis l'enlever, arracher ce
de notre tableau.
Pourquoi pouvons-nous faire cela?
Donc, si je dois une chose sur ma pile, ce qui serait ma taille à ce point?
1.
>> Et où est stocké l'élément 1?
A quel indice?
PUBLIC: 0.
ENCEINTE 1: 0.
Donc dans ce cas, nous toujours besoin de faire sure--
au lieu de retourner taille moins 1, parce que nous
Sachez que notre élément est va être stocké à une moins
quelle que soit notre taille est, cette prend juste soin d'elle.
Il est une façon un peu plus élégant.
Et nous décrémentons juste notre taille et ensuite revenir taille.
Mmhmm?
>> PUBLIC: Je pense juste en général, Pourquoi serait-ce la structure de données
être bénéfique?
>> ENCEINTE 1: Cela dépend de votre contexte.
Donc, pour une partie de la théorie, si vous travaillez with-- OK,
laissez-moi voir si il est un bénéfique qui est avantageux à plus d'extérieur
de CS.
Avec des piles, à tout moment vous avez besoin de garder une trace de quelque chose qui
est le plus récemment ajouté est quand vous allez avoir à utiliser une pile.
>> Et je ne peux pas penser à une bonne exemple de ce droit maintenant.
Mais chaque fois que le plus récent chose est plus important pour vous,
qui est alors une pile va être utile.
Je suis en train de penser si il ya un bon pour cela.
Si je pense à un bon exemple dans la prochaine 20 minutes, je vais certainement vous dire.
>> Mais dans l'ensemble, si il ya quelque chose, comme je l'ai dit plus, où la plus récente
est le plus important, qui est où une pile entre en jeu.
Alors que les files d'attente sont un peu le contraire.
Et tous les petits chiens.
Est pas génial, non?
Je me sens comme je le devrais juste avoir une vidéo de lapin
en plein milieu de section pour vous les gars
parce que cela est une section intense.
>> Donc, une file d'attente.
Fondamentalement, une file d'attente est comme une ligne.
Vous les gars, je suis sûr que cette utilisation de tous les jours, tout comme dans nos salles à manger.
Nous devons donc aller dans et obtenir nos plateaux, je suis
que vous avez à attendre en ligne de glisser ou obtenir votre nourriture.
>> Donc, la différence ici est l'existence de ce type FIFO.
Donc, si LIFO était dernier entré, premier out, FIFO est premier entré, premier sorti.
Ce est donc là que vous avez mis la première est votre plus importante.
Donc, si vous attendiez dans un line-- vous pouvez
Imaginez si vous êtes allé à aller chercher le nouvel iPhone
et il avait une pile où le dernière personne en ligne a obtenu le premier,
les gens tuer les uns les autres.
>> Donc FIFO, nous sommes tous très familiers avec dans le monde réel ici,
et il a tout à voir avec effectivement sorte de recréer toute cette ligne
et la structure de file d'attente.
Ainsi, alors que la pile, nous avons poussée et pop.
Avec une file d'attente, nous avons en file d'attente et dequeue.
Donc en file d'attente signifie essentiellement mettre sur le dos,
et des moyens dequeue prennent hors de l'avant.
Donc, notre structure de données est un peu plus compliqué.
Nous avons un deuxième chose à garder la trace.
>> Donc, sans la tête, cette est exactement une pile, non?
Ceci est la même structure que celle d'une pile.
La seule chose différente est maintenant nous avoir cette tête, qui que pensez-vous
va suivre?
>> AUDIENCE: Le premier.
>> ENCEINTE 1: Droit, la première chose que nous avons mis en.
La tête de notre file d'attente.
Celui qui est en première ligne.
Très bien, si nous faisons en file d'attente.
Encore une fois, avec l'un des ces structures de données,
puisque nous avons affaire à un tableau, nous devons vérifier si nous avons de l'espace.
>> Ceci est un peu comme me dire vous les gars, si vous ouvrez un fichier,
vous devez vérifier pour nulle.
Avec l'une de ces piles et les files d'attente, vous devez
pour voir si il ya de l'espace parce que nous sommes traiter avec une matrice de taille fixe,
comme nous le voyons ici-- 0, 1 tout à 5.
Donc, ce que nous faisons dans ce cas est de vérifier pour voir si nous avons encore de la place.
Est notre taille inférieure à la capacité?
>> Si oui, nous avons besoin de les stocker à la queue et nous mettons à jour notre taille.
Alors, que peut-être la queue dans ce cas?
Il est pas explicitement écrit sur.
Comment pourrions-nous stocker?
Qu'est-ce que la queue être?
>> Donc, nous allons marcher à travers cet exemple.
Donc ceci est un tableau de taille 6, à droite?
Et nous avons en ce moment, notre taille est 5.
Et quand on le met dans, ça va pour aller dans le cinquième indice, non?
Donc stocker à queue.
>> Une autre façon d'écrire la queue serait juste être notre tableau à indice de la taille, non?
Cette taille est 5.
La prochaine chose va aller en 5.
Cool?
D'accord.
Il devient un peu plus compliqué quand nous commençons à jouer avec la tête.
Oui?
>> Public: Est-ce à dire que nous aurait déclaré un tableau
cinq éléments est longue et puis nous ajoutons sur elle?
>> ENCEINTE 1: Non
Donc dans ce cas, cela est une pile.
Ce serait déclarée comme un tableau de taille 6.
Et dans ce cas, nous juste avoir une gauche de l'espace.
>> OK, si une chose est dans ce cas, si notre tête est à 0,
alors nous ne pouvons l'ajouter à la taille.
Mais il ya un peu plus délicat parce qu'en fait, ils
ne pas avoir une diapositive pour cela, donc je vais
de tirer un parce qu'il est pas tout à fait aussi simple que cela une fois que vous
commencer à se débarrasser de choses.
Ainsi, alors que avec une pile vous ne devez jamais
à vous soucier de ce que la taille est lorsque vous ajoutez quelque chose sur,
avec une file d'attente, vous devez également faire vous que votre tête est représenté,
parce que quelque chose de cool à propos de files d'attente est que si vous n'êtes pas à pleine capacité,
vous pouvez réellement faire enrouler autour.
>> OK, donc on chose-- oh, cette craie est terrible.
Une chose à considérer est le cas.
Nous allons juste faire cinq.
OK, donc nous allons dire la tête est ici.
Ceci est égal à 0, 1, 2, 3, 4.
>> La tête est là, et se il vous plaît avoir des choses en eux.
Et nous voulons ajouter quelque chose à, non?
Donc, la chose que nous devons savoir est que la tête est toujours
va se déplacer de cette façon et ensuite bouclé autour, OK?
>> Donc, cette file d'attente possède un espace dédié, non?
Il possède un espace dédié au tout début, type de l'opposé de cela.
Donc, ce que nous devons faire est nous besoin de calculer la queue.
Si vous savez que votre tête n'a pas bougé, la queue
est juste à votre tableau l'indice de la taille.
>> Mais en réalité, si vous utilisez une file d'attente, votre tête est probablement mis à jour.
Donc ce que vous devez faire est en fait calculer la queue.
Donc, ce que nous faisons est cette formule ici, que je vais vous laisser
les gars pensent, et puis nous en reparlerons.
Donc, cette capacité est.
>> Donc, ce sera effectivement vous donner un moyen de le faire.
Parce que dans ce cas, quoi?
Notre siège est à 1, notre taille est 4.
Si nous mod que par 5, on obtient 0, qui est l'endroit où nous devrions elle entrée.
>> Alors dans le cas suivant, si nous devions le faire,
nous disons, OK, nous allons DEQUEUE quelque chose.
Nous DEQUEUE cela.
Nous prenons à cet élément, non?
>> Et maintenant, notre tête est pointé ici, et nous voulons ajouter une autre chose.
Ceci est essentiellement le arrière de notre ligne, non?
Les files d'attente peuvent enrouler autour du tableau.
Voilà l'une des principales différences.
Piles, vous ne pouvez pas faire cela.
>> Avec les files d'attente, vous pouvez parce que tout ce qui compte
est que vous savez ce que a été le plus récemment ajouté.
Puisque tout va être ajoutée dans cette direction vers la gauche, dans ce cas,
et puis envelopper, vous pouvez continuer à mettre de nouveaux éléments
à l'avant de la matrice car il est pas vraiment
l'avant de la rangée plus.
Vous pouvez penser le début de la tableau comme lorsque votre tête est en réalité.
>> Donc, cette formule est de savoir comment vous calculez votre queue.
Est-ce que cela a un sens?
D'accord.
OK, dequeue, puis vous les gars avez 10 minutes
à me poser des questions de clarification vous voulez, parce que je sais qu'il est fou.
>> Très bien, alors dans le même way-- Je ne sais pas si vous remarqué,
mais CS est tout au sujet des motifs.
Les choses sont à peu près la même, juste de petits réglages.
Donc même chose ici.
Nous avons besoin de vérifier pour voir si nous avons effectivement avoir quelque chose dans notre file d'attente, non?
Dire, OK, est notre taille supérieure à 0?
Laisser refroidir.
>> Si nous le faisons, alors nous passons notre tête, qui est ce que je viens de le démontrer ici.
Nous mettons à jour notre tête à être un plus.
Et puis nous avons notre décrémentons taille et retourner l'élément.
>> Il est beaucoup plus concret code sur study.cs50.net,
et je vous recommande vivement d'y aller à travers elle, si vous avez le temps,
même si elle est juste un pseudo-code.
Et si vous voulez les gars de parler à travers qui avec moi sur une base individuelle, se il vous plaît laissez-moi
savoir.
Je serais heureux de le faire.
Les structures de données, si vous prenez CS 124, vous aurez
savent que les structures de données deviennent très amusant et ce ne fait que commencer.
>> Donc, je sais qu'il est difficile.
Ce est OK.
Nous luttons.
Je le fais toujours.
Donc ne vous inquiétez pas trop à ce sujet.
>> Mais qui est fondamentalement votre Crash Course dans les structures de données.
Je sais qu'il est beaucoup.
Y at-il quelque chose que nous voudrait aller encore?
Tout ce que nous voulons parler à travers?
Oui?
>> Public: Pour cet exemple, si la nouvelle queue est à 0 sur cela?
ENCEINTE 1: Oui.
PUBLIC: OK.
Alors en passant par, vous auriez 1 plus 4 ou--
>> ENCEINTE 1: Donc vous disiez, quand nous voulons aller le faire à nouveau?
PUBLIC: Ouais.
Donc, si vous déterminez out-- où sont vous le calcul de la queue de dans tout cela?
>> ENCEINTE 1: Donc la queue Je suis in-- changé la donne.
Ainsi, dans cet exemple ici, ce fut le tableau que nous cherchons à, OK?
Donc, nous avons des choses en 1, 2, 3, et 4.
Donc, nous avons notre tête est égal à 1 à ce point, et notre taille est égale à 4
à ce moment, non?
>> Vous conviendrez que ce soit le cas?
Nous faisons donc la tête, plus la taille, qui nous donne 5, puis nous Mod par 5.
Nous obtenons 0, qui nous dit que 0 est où est notre queue, où nous avons de l'espace.
>> Public: Qu'est-ce qu'un bouchon?
>> ENCEINTE 1: La capacité.
Désolé.
Voilà donc la taille de votre tableau.
Oui?
>> PUBLIC: [Inaudible] avant nous revenons de l'élément?
>> ENCEINTE 1: Nous passons donc la la tête ou retourner le moment?
Donc, si nous passons un, diminuer la taille?
Attendez.
Je certainement oublié un autre.
Ça ne fait rien.
Il n'y a pas une autre formule.
Ouais, vous voulez retourner la tête, puis le reculer.
>> PUBLIC: OK, car à ce stade, la tête était à 0,
et puis vous voulez retourner index 0 et ensuite faire la tête 1?
>> ENCEINTE 1: Droit.
Je pense qu'il ya un autre formule un peu comme cela.
Je ne l'ai pas sur le dessus de ma tête comme Je ne veux pas vous donner le mauvais.
Mais je pense qu'il est tout à fait valable pour par exemple, OK, entreposer ce quel que soit element--
l'élément de tête est-- décrémenter votre taille, déplacez votre tête au-dessus, et retour
tout ce qui est élément.
Voilà tout à fait valable.
D'accord.
Je me sens comme ce ne sont pas comme le most-- vous n'êtes pas
va sortir d'ici comme, oui, je sais essais.
Je l'ai eu tout.
Ce est OK.
Je promets.
Mais les structures de données sont quelque chose que il faut beaucoup de temps pour s'y habituer.
Probablement l'un des plus difficiles choses, je pense que, dans le cours.
>> Donc, il faut certainement répétition et la recherche at-- je
ne savait pas vraiment les listes chaînées jusqu'à ce que je l'ai fait beaucoup trop avec eux,
de la même manière que je ne l'ai pas vraiment comprendre pointeurs
jusqu'à ce que je l'ai eu à enseigner pour deux ans et faire ma propre psets avec elle.
Il faut beaucoup de répétition et du temps.
Et finalement, il sorte de cliquer.
>> Mais en attendant, si vous avez genre une compréhension de haut niveau de ce que
ceux-ci ne, leurs avantages et qui est ce qui cons--
nous avons tendance vraiment à souligner, en particulier dans le cadre de l'intro.
Comme, pourquoi devrions-nous utiliser un essai sur un tableau?
Comme, ce sont les points positifs et négatifs de chacune des personnes?
>> Et de comprendre les compromis entre chacune de ces structures
est ce qui est beaucoup plus important en ce moment.
Il peut y avoir un fou question ou deux qui est
vais vous demander de mettre en œuvre poussée ou mettre en œuvre pop ou en file d'attente et dequeue.
Mais la plupart du temps, compte que compréhension supérieure de niveau et plus
d'une compréhension intuitive est en fait plus importante que
être en mesure de mettre en œuvre.
>> Ce serait vraiment génial si vous tous pourrait sortir et aller mettre en œuvre un essai,
mais nous comprenons qu'il est pas nécessairement la chose la plus raisonnable à l'heure actuelle.
Mais vous pouvez dans votre pset, si vous voulez à, et puis vous aurez la pratique,
et puis peut-être vous vraiment comprendre.
Oui?
>> PUBLIC: OK, donc ceux qui sont nous voulions dire à utiliser dans le jeu de processeurs?
Dois-je utiliser l'un d'eux?
ENCEINTE 1: Oui.
Donc, vous avez le choix.
Je suppose que dans ce cas, nous pouvons parler de l'ensemble de processeurs un peu
parce que je courais à travers ces.
Donc, à votre pset, vous avez votre choix d'essais ou tables de hachage.
Certaines personnes vont essayer et utiliser des filtres de floraison,
mais ceux-ci sont techniquement pas correct.
En raison de leur nature probabiliste, ils donnent parfois des faux positifs.
Ils sont en look cool, cependant.
Je le recommande vivement à la recherche à eux au moins.
Mais vous avez le choix entre une table de hachage et un essai.
Et cela va être le cas vous chargez dans votre dictionnaire.
>> Et vous aurez besoin de choisir votre fonction de hachage,
vous aurez besoin de choisir combien de seaux que vous avez, et il peut varier.
Comme si vous avez plus de seaux, ce sera peut courir plus vite.
Mais peut-être vous perdez un beaucoup d'espace de cette façon, si.
Vous devez comprendre.
Mmhmm?
>> Public: Vous avez dit avant que nous pouvons utiliser d'autres fonctions de hachage,
que nous ne devons pas créer une fonction de hachage?
>> ENCEINTE 1: Oui, à droite.
Donc littéralement pour votre fonction de hachage, comme google "fonction de hachage"
et chercher des étés frais.
Vous n'êtes pas censé construire vos propres fonctions de hachage.
Les gens passent leur thèses sur ces choses.
>> Ne vous inquiétez donc pas de construire votre propre.
Trouver une à commencer par ligne.
Certains d'entre eux vous devez manipuler un peu
à veiller à ce que les types de retour correspondent et ainsi de suite, si au début,
Je vous conseille d'utiliser quelque chose vraiment facile que peut-être juste
hache sur la première lettre.
Et puis une fois que vous avez ce travail, intégrant une fonction de hachage refroidisseur.
Mmhmm?
>> PUBLIC: Serait un essai ou être efficace, mais juste plus difficile à, like--
>> ENCEINTE 1: Donc un essai, je pense, est intuitivement difficile à mettre en œuvre
mais est très rapide.
Cependant, prend plus de place.
Encore une fois, vous pouvez optimiser à la fois de ceux qui en différentes façons et il existe des moyens to--
Public: Comment sommes-nous classés sur ce?
Est-ce matter--
>> ENCEINTE 1: Vous êtes donc classés de façon normale.
Vous allez être classé sur la conception.
Quelle que soit la façon dont vous le faites, vous voulez assurez-vous qu'il est aussi élégant que peut être
et aussi efficace que possible.
Mais si vous choisissez un essai ou hachage table, tant que cela fonctionne,
nous sommes heureux.
Et si vous utilisez quelque chose qui hachages sur la première lettre, qui est très bien,
comme peut-être comme du design.
Nous sommes également d'atteindre le point de cette semester--
Je ne sais pas si vous noticed-- gars si vous êtes
grades pset diminuent un peu en raison de la conception et ainsi de suite,
qui est parfaitement bien.
Il se fait à un point où votre programmes sont de plus compliqué.
Il ya plus de places vous pouvez améliorer.
>> Ainsi, il est parfaitement normal.
Il est pas que vous êtes faire pire sur votre pset.
Il est juste que nous allons être plus difficile sur vous maintenant.
Donc tout le monde se sent elle.
Je viens graduée tous vos psets.
Je sais que tout le monde se sent elle.
>> Alors ne soyez pas inquiet à ce sujet.
Et si vous avez des questions au sujet psets antérieures ou des façons dont vous pouvez améliorer,
Je tente de commenter le spécifique endroits, mais parfois il est tard
et je suis fatigué.
Y at-il d'autres choses sur les structures de données?
Je suis sûr que vous les gars ne le faites pas vraiment vouloir en parler plus,
mais si il ya, je suis heureux de passer en revue, ainsi que tout
de conférence dernier semaine ou la semaine dernière.
>> Je sais que la semaine dernière était tout contrôle, si nous avons peut-être sauté quelques examen
de conférence.
Toutes les autres questions auxquelles je peux répondre?
OK, d'accord.
Eh bien, les gars sortir 15 minutes plus tôt.
>> Je espère que cette était semi-utile au moins, et je vais vous voir les gars la semaine prochaine,
ou jeudi les heures de bureau.
Existe-t-il des demandes pour les collations pour la semaine prochaine, il est la chose?
Parce que je oublié bonbons aujourd'hui.
Je fis bonbons dernier semaine, mais il était Columbus Day,
donc il y avait comme six personnes avait quatre sacs de bonbons pour eux-mêmes.
Je peux apporter Starbursts nouveau si vous le souhaitez.
Starbursts?
OK, sonne bien.
Avoir un grand jour, les gars.