>> INTERLOCUTEUR 1: Très bien, alors nous sommes de retour.
Bienvenue à CS50.
C'est la fin de la semaine sept ans.
Donc, rappelons que la dernière fois, nous avons commencé en regardant un peu plus sophistiqué
des structures de données.
Depuis, jusqu'à présent, nous n'avions vraiment à notre disposition était présent, un tableau.
>> Mais avant de nous écartons le tableau en tant que non tout ce qui intéressant, ce qui fait qu'il
est en réalité, ce sont quelques-uns des avantages de ces données simples
la structure jusqu'à présent?
Quel est le bon?
Pour autant que nous avons vu?
Qu'est-ce que tu as?
Rien.
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Qu'est-ce que c'est?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: taille fixe.
OK, alors pourquoi est de taille fixe si bon?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: OK, donc c'est efficace le sens que vous pouvez allouer une
montant fixe de l'espace, qui nous l'espérons C'est précisément autant
l'espace que vous voulez.
Il pourrait donc être absolument un plus.
>> Ce qui est un autre aspect d'un tableau?
Ouais?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Tout le - désolé?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: toutes les cases de la mémoire ou à côté de l'autre.
Et c'est utile - pourquoi?
C'est tout à fait vrai.
Mais comment pouvons-nous exploiter cette vérité?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Exactement, nous pouvons garder une trace de où tout est juste en sachant
une adresse, à savoir l'adresse de l' premier octet de ce bloc de mémoire.
Or, dans le cas de la chaîne, l'adresse du premier
chevalier dans cette chaîne.
Et à partir de là, nous pouvons trouver la fin de la chaîne.
Nous pouvons trouver le deuxième élément, le troisième élément, et ainsi de suite.
>> Et si la fantaisie façon de décrire ce que caractéristique est que les tableaux nous donnent
accès aléatoire.
Juste en utilisant le crochet notation et un numéro, vous pouvez passer à
un élément spécifique dans le tableau en temps constant, grand O
d'un seul, pour ainsi dire.
>> Mais il ya eu quelques inconvénients.
Qu'est-ce un tableau fait pas très facilement?
Quel est-il pas bon?
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Qu'est-ce que c'est?
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Développer la taille.
Ainsi, les inconvénients du tableau sont exactement le contraire de ce que l'
upsides sont.
Donc, l'un des inconvénients est que c'est une taille fixe.
Donc vous ne pouvez pas vraiment cultiver.
Vous pouvez réaffecter une plus grande partie de mémoire, puis déplacez les éléments anciens
dans le nouveau tableau.
Et puis libérer le vieux tableau, pour Ainsi, en utilisant malloc ou un analogue
fonction appelée realloc, qui réaffecte mémoire.
>> Realloc, en passant, essaie de vous donner mémoire qui est à côté de la matrice
que vous avez déjà.
Mais il pourrait faire bouger les choses autour de tout.
Mais en bref, c'est cher, non?
Parce que si vous avez un morceau de la mémoire de cette taille, mais vous voulez vraiment un
de cette taille, et vous souhaitez conserver les éléments d'origine, vous avez
moins un processus de copie de temps linéaire qui doit se produire à partir de
ancien tableau à nouveau.
Et la réalité est demande au fonctionnement Système à plusieurs reprises et
nouveau pour de gros morceaux de la mémoire peut commencer vous coûter un certain temps ainsi.
Donc, c'est à la fois une bénédiction et une malédiction dissimuler le fait que ces tableaux
sont de taille fixe.
Mais si nous introduisons la place quelque chose comme ce que nous avons appelé une alternance
liste, nous obtenons quelques bons côtés et quelques inconvénients ici aussi.
>> Ainsi, une liste chaînée est tout simplement un ensemble de données Structure composée de struct C dans cette
cas où une structure, le rappel est juste un récipient pour un ou plusieurs spécifique
types de variables.
Dans ce cas, qu'est-ce que les types de données semblent être à l'intérieur de la structure qui
dernière fois que nous avons appelé un nœud?
Chacun de ces rectangles est un nœud.
Et chacun des petits rectangles à l'intérieur de celui-ci est un type de données.
Quels types disions-nous ils étaient lundi?
Ouais?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Une variable et un pointeur, ou Plus précisément, un int, pour n,
et un pointeur vers le bas.
Les deux personnes se trouvent être 32 bits, à moins sur un ordinateur comme ça CS50
Appareil, et ils sont donc provenant à parts égales de la taille.
>> Alors, qu'est-ce que l'aide du pointeur mais pour apparemment?
Pourquoi ajouter cette flèche maintenant, quand les tableaux étaient si belle et propre et simple?
Quel est le pointeur fait pour nous dans chacun de ces nœuds?
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Exactement.
C'est vous dire où le prochain est.
Donc je sorte d'utiliser l'analogie de l'aide d'un fil de trier des
enfiler ces nœuds ensemble.
Et c'est exactement ce que nous faisons avec pointeurs parce que chacun de ces
des morceaux de la mémoire peuvent ou non être contiguë, dos à dos à dos
à l'intérieur de RAM, parce que chaque fois que vous appeler malloc dire, donnez-moi assez
octets pour un nouveau nœud, il pourrait soit ici ou il peut s'agir ici.
C'est peut-être ici.
Vous ne savez tout simplement pas.
>> Mais l'utilisation de pointeurs dans les adresses de ces nœuds, vous pouvez coudre les
ensemble d'une manière qui est visuellement comme une liste même si ces choses sont
tout étalé tout au long de votre un ou Vos deux ou vos quatre gigaoctets de RAM
à l'intérieur de votre propre ordinateur.
>> Ainsi la baisse, alors, une liste chaînée, c'est quoi?
Qu'est-ce qu'un prix nous sommes apparemment payer?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Plus d'espace, non?
Nous avons, dans ce cas, a doublé le montant de l'espace parce que nous sommes passés
de 32 bits pour chaque noeud, pour chaque int, alors maintenant 64 bits parce que nous devons
maintenir un pointeur près aussi.
Vous obtenez plus d'efficacité si votre struct est plus grande que cette chose simple.
Si vous avez réellement un élève à l'intérieur qui est un couple de cordes pour
nom et la maison, peut-être un numéro d'identification, peut-être quelques autres domaines tout à fait.
>> Donc si vous avez une assez grande structure, peut-être que le coût du pointeur est
pas une grosse affaire.
C'est un peu un cas d'angle qui nous stockons une telle primitive simple
à l'intérieur de la liste liée.
Mais le point est le même.
Vous êtes certainement dépenser plus mémoire, mais vous obtenez
flexibilité.
Parce que maintenant, si je veux ajouter un élément au début de cette liste,
Je dois attribuer un nouveau nœud.
Et je dois mettre à jour seulement ceux flèches en quelque sorte en déplaçant simplement
quelques conseils autour.
>> Si je veux insérer quelque chose dans l' milieu de la liste, je n'ai pas d'
pousser tout le monde à part, comme nous l'avons fait dans Le passé semaines avec nos bénévoles qui
représenté un tableau.
Je peux attribuer un nouveau nœud et puis il suffit de pointer les flèches
des directions différentes, car il ne doivent rester en situation réelle
mémoire d'une véritable ligne comme je l'ai dessiné ici à l'écran.
>> Et puis enfin, si vous souhaitez insérer quelque chose à la fin de la liste, c'est
encore plus facile.
C'est une sorte de notation arbitraire, mais 34 de l'aiguille, prendre une supposition.
Quelle est la valeur de son pointeur plus susceptibles sorte tiré de comme un vieux
antenne de l'école là-bas?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: C'est probablement nulle.
Et en effet, ce qui est à un auteur représentation de nul.
Et c'est nul parce que vous devez absolument besoin de savoir où la fin d'une alternance
liste, de peur que vous continuez à suivre et la suite et la suite de ces flèches
à une certaine valeur d'ordures.
Donc nul signifiera qu'il n'y a pas plus de nœuds à la droite du numéro 34,
dans ce cas.
>> Nous proposons donc que nous pouvons mettre en œuvre ce nœud dans le code.
Et nous avons vu ce genre de syntaxe avant.
Typedef juste définit un nouveau type de nous, nous donne un synonyme comme
chaîne était pour char *.
Dans ce cas, il va nous donner notation abrégée afin que nœud de struct
peut au contraire être simplement écrit que noeud, ce qui est beaucoup plus propres.
C'est beaucoup moins verbeux.
>> A l'intérieur d'un nœud est apparemment un int appelé n, puis un noeud struct *
ce qui signifie exactement ce que nous voulions le flèches à dire, un pointeur vers un autre
noeud du même type de données exacte.
Et je propose que nous pourrions mettre en place un fonction de recherche comme celui-ci, qui, à
première vue, pourrait sembler un peu complexe.
Mais voyons les choses en contexte.
>> Permettez-moi de passer à l'appareil ici.
Permettez-moi d'ouvrir un fichier appelé Liste zéro point h.
Et qui ne contient que la définition que nous juste vu il ya un instant que ces données
Type appelée un nœud.
Donc, nous avons mis cela dans un fichier h dot.
>> Et en passant, même si cette programme que vous allez voir est
pas tout à fait complexe, il est en effet convention lors de l'écriture d'un programme de
mettre les choses comme les types de données, de tirer constantes, parfois, à l'intérieur de votre
fichier d'en-tête et pas nécessairement dans votre fichier C, certainement lorsque votre
programmes deviennent plus gros et plus grand, de sorte que vous savez où regarder tant pour
documentation dans certains cas, ou pour bases de ce genre, les
définition d'un certain type.
>> Si j'ouvre maintenant la liste zéro point c, remarqué quelques petites choses.
Il comprend quelques fichiers d'en-tête, la plupart des dont nous avons vu auparavant.
Il inclut son propre fichier d'en-tête.
>> Et en passant, pourquoi c'est à double citations ici, contrairement à l'angle
parenthèses sur la ligne qui J'ai souligné il?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Ouais donc c'est un fichier local.
Donc, si c'est un fichier local de votre propre ici sur la ligne 15, par exemple, vous utilisez
les guillemets au lieu des chevrons.
>> Maintenant, c'est assez intéressant.
Remarquez que j'ai déclaré un mondial variable dans ce programme sur la ligne 18
appelé en premier, l'idée étant que c'est va être un pointeur vers le premier
nœud dans ma liste chaînée, et j'ai initialisée à null, parce que j'ai
attribué aucune réelle nœuds pour l'instant.
>> Donc cela représente, imagé, ce que nous vu il ya un moment dans l'image comme
ce pointeur à l'extrême côté gauche.
Donc, en ce moment, ce pointeur n'a pas encore d'une flèche.
Il est plutôt juste nul.
Mais il représente ce que sera l' l'adresse du premier réelle
noeud de cette liste.
J'ai donc mis en œuvre un mondial parce que, comme vous le verrez, tout cela
programme fait dans la vie est mise en œuvre une liste liée pour moi.
>> Maintenant, j'ai quelques prototypes ici.
J'ai décidé de mettre en œuvre des fonctionnalités telles que suppression, insertion, la recherche et
traversal -
le dernier étant juste promenade à travers la liste, l'impression de ses éléments.
Et maintenant voici ma routine principale.
Et nous n'allons pas passer trop de temps sur ceux-ci puisque c'est en quelque sorte, nous espérons
vieux chapeau maintenant.
>> Je vais faire ce qui suit, pendant que l'utilisateur coopère.
Alors là, je vais imprimer ce menu.
Et j'ai formaté comme proprement que je le pouvais.
Si l'utilisateur saisit en un, ce qui signifie ils veulent supprimer quelque chose.
Si l'utilisateur tape en deux, ce qui signifie ils veulent insérer quelque chose.
Et ainsi de suite.
Je vais inviter ensuite puis d'une commande.
Et puis je vais utiliser getInt.
>> Donc, c'est une très simple menuing interface où vous avez juste à taper
un certain nombre de cartographie à une de ces commandes.
Et maintenant, j'ai une belle interrupteur propre déclaration qui va allumer
quel que soit l'utilisateur a tapé po
Et si ils ont tapé un, je vais appeler supprimer et se briser.
Si ils ont tapé deux, je vais appeler insérer et se briser.
>> Et maintenant remarquerez que j'ai mis chaque de ceux-ci sur la même ligne.
C'est juste une décision stylistique.
Typiquement, nous avons vu quelque chose comme ça.
Mais j'ai décidé, franchement, mon programme regardé plus lisible car
il n'y avait que quatre cas se contenter d'énumérer comme ça.
Utilisation tout à fait légitime de section.
Et je vais le faire aussi longtemps que le utilisateur n'a pas tapé zéro, que je
décidé signifiera qu'ils veulent cesser de fumer.
>> Alors maintenant, remarque ce que je suis allons faire ici.
Je vais libérer la liste apparemment.
Mais plus à ce sujet dans un instant.
Voyons d'abord exécuter ce programme.
Alors permettez-moi de faire un terminal plus grand fenêtre, point barre oblique liste 0.
Je vais aller de l'avant et insérez par taper deux, un nombre comme 50, et maintenant
vous verrez la liste est maintenant de 50.
Et mon texte défile juste un peu.
Alors maintenant, notez la liste contient le nombre 50.
>> Faisons un autre insert en prenant deux.
Nous allons taper le numéro comme tel.
Liste est maintenant l'un, puis 50.
Donc, c'est juste une représentation textuelle de la liste.
Et nous allons insérer un nombre plus comme le nombre 42, qui est, espérons-
va finir dans le milieu, parce que ce programme en particulier trie
éléments comme il les inserts.
Donc, il nous l'avons.
Programme super simple qui pourrait absolument avoir utilisé un tableau, mais je
arriver à être en utilisant une liste chaînée juste pour que je puisse dynamique
grandir et rétrécir.
>> Donc, nous allons jeter un oeil pour la recherche, si je trois commandes de fonctionner, je veux chercher
pour, par exemple, le nombre 43.
Et rien ne semble avoir été trouvé, parce que je suis rentré sans réponse.
Donc, nous allons le faire à nouveau.
Rechercher.
Cherchons à 50, ou plutôt rechercher pour 42, qui a une belle
peu de sens subtil.
Et j'ai trouvé le sens de la vie là-bas.
Numéro 42, si vous ne savez pas la référence, Google il.
Très bien.
Que s'est-il ce programme fait pour moi?
C'est juste m'a permis d'insérer ainsi loin et rechercher des éléments.
>> Allons de l'avant rapide, puis, à cette fonction nous regarda
le lundi comme un teaser.
Donc cette fonction, je prétends, les recherches pour un élément dans la liste en premier
une, demandant à l'utilisateur, puis en appelant GetInt pour obtenir une réelle int
que vous souhaitez rechercher.
>> Ensuite remarquer cela.
Je vais créer une variable temporaire en ligne 188 appelé pointeur -
PTR -
aurait appelé cela rien.
Et c'est un pointeur vers un noeud parce que j'ai dit il ya noeud *.
Et je l'initialiser soit égale à d'abord en sorte que j'ai effectivement ma
doigt, pour ainsi dire, sur le très premier élément de la liste.
Donc, si ma main droite est ici PTR je suis pointant vers la même chose que le premier
est pointé.
>> Donc, maintenant de retour dans le code, ce qui arrive ensuite -
il s'agit d'un paradigme commun lors de l'itération sur une structure comme une
liste chaînée.
Je vais faire ce qui suit pointeur n'est pas égal à null, donc tout
mon doigt ne pointe pas à un nul valeur, si le pointeur flèche n est égal à n.
Nous remarquons d'abord que n est ce que l' tapé par l'utilisateur GetInts appeler ici.
>> Et pointeur flèche n veut dire quoi?
Eh bien, si nous revenons à l'image ici, si j'ai un doigt pointé vers
que le premier nœud contenant neuf, le flèche signifie essentiellement aller à ce
nœud et saisir la valeur à l'emplacement n, Dans ce cas, le champ de données appelée n.
>> Soit dit en passant - et nous avons vu ce couple il ya quelques semaines lorsque quelqu'un a demandé -
cette syntaxe est nouveau, mais il ne nous donner des pouvoirs que nous
ne pas avoir déjà.
Quelle était cette phrase équivaut à utiliser dot notation et la star d'un couple
Il ya quelques semaines, lorsque nous décollée cette couche un peu prématurée?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Exactement, c'était étoiles, et puis ce fut étoile point n, avec
parenthèses ici, qui ressemble, Franchement, je pense que beaucoup
plus énigmatique à lire.
Mais Star Pointer, comme toujours, moyens y aller.
Et une fois que vous y êtes, quelles données domaine voulez-vous accéder?
Eh bien, vous utilisez la notation par point d'accès un champ de données de structures, et je
veulent spécifiquement n.
>> Franchement, je dirais cette est juste plus difficile à lire.
Il est plus difficile de se rappeler où ne les parenthèses vont, l'
étoiles et tout ça.
Ainsi, le monde a adopté un certain syntaxique sucre, pour ainsi dire.
Juste une façon sexy de dire, c'est l'équivalent, et
peut-être plus intuitive.
Si le pointeur est en effet un pointeur, l' moyens de notation fléchées y aller et trouver
le terrain dans ce cas appelé n.
>> Donc, si je trouve, notez ce que je fais.
Je suffit d'imprimer, j'ai trouvé pour cent i, brancher la valeur de cette int.
J'appelle dormir pendant une seconde juste genre de pause choses à l'écran pour
donner à l'utilisateur une seconde pour absorber ce qui vient de se passer.
Et puis, je me casse.
Sinon, je fais quoi?
Je mets à jour le pointeur à l'égalité la flèche du pointeur prochaine.
>> Donc, juste pour être clair, cela signifie aller là-bas, en utilisant ma notation de la vieille école.
Donc, cela signifie simplement aller à n'importe quel que vous pointez, qui dans la très
premier cas, c'est que je fais remarquer à la structure à neuf en elle.
Donc, je suis allé là-bas.
Et puis, signifie la notation par point, obtenir la valeur lors de la prochaine.
>> Mais la valeur, même si elle est dessinée comme étroite, est juste un nombre.
Il s'agit d'une adresse numérique.
Donc cette seule ligne de code, si écrit comme ça, le plus énigmatique
Ainsi, ou comme ça, le peu plus manière intuitive, signifie simplement déplacer ma main
à partir du premier noeud à la suivante, puis la suivante, puis le
suivant, et ainsi de suite.
>> Donc, nous ne nous attarderons pas sur l'autre implémentations d'insérer et de supprimer
et la traversée, dont les deux premières qui sont assez impliqués.
Et je pense que c'est assez facile à obtenir perdu quand il le faire verbalement.
Mais ce que nous pouvons faire ici est essayer de déterminer comment
mieux de le faire visuellement.
Parce que je voudrais proposer que si nous insérer les éléments dans cette
liste existante, qui comporte cinq éléments -
9, 17, 22, 26, et 33 -
si je devais mettre en œuvre ce dans code, j'ai besoin de considérer comment s'y prendre
prendre.
>> Et je vous propose de prendre des mesures de bébé de sorte que, dans ce cas, je veux dire, quels sont
les scénarios possibles que nous pourraient rencontrer en général?
Lorsque la mise en œuvre d'un insert lié liste, cela arrive juste à être un
exemple précis de la taille de cinq ans.
Eh bien, si vous voulez insérer un numéro, comme, disons, le numéro un, et
le maintien de l'ordre de tri, où fait évidemment le numéro un besoin d'
aller dans cet exemple précis?
Comme au début.
>> Mais ce qui est intéressant, c'est que là si vous voulez insérer un dans cette
liste, ce pointeur particulière doit être mis à jour apparemment?
Première.
Je dirais donc, c'est le premier cas que nous pourrions envisager, une
scénario impliquant l'insertion d'au le début de la liste.
>> Allons arrachez peut-être un aussi facile ou même cas plus facile, relativement parlant.
Supposons que je veux insérer l' Numéro 35 dans l'ordre.
Il appartient évidemment là-bas.
Alors qu'est-ce pointeur évidemment va être mis à jour dans ce scénario?
34 de la pointeur de devenir non nulle mais l'adresse de la structure
contenant le numéro 35.
C'est donc deux cas.
Donc, déjà, je suis une sorte de quantification la quantité de travail que j'ai à faire ici.
>> Et enfin, le cas du milieu est évident En effet, dans le milieu, si je veux
insérer quelque chose comme, disons 23, qui va entre le 23 et le 26, mais
maintenant les choses deviennent un peu plus impliqué parce que ce
pointeurs doivent être changées?
Donc 22 doit évidemment être changé parce qu'il ne peut pas pointer vers 26 plus.
Il doit pointer vers le nouveau nœud Je vais devoir répartir en appelant
malloc ou quelque chose d'équivalent.
>> Mais ensuite, j'ai aussi besoin que le nouveau nœud, 23 dans ce cas, d'avoir son pointeur
pointant à qui?
26.
Et il va y avoir une ordre des opérations ici.
Parce que si je fais ça bêtement, et je par exemple début au début de
la liste, et mon but est d'insérer 23.
Et je vérifie, appartient-il ici, près de neuf?
No.
Appartient-elle ici, à côté de 17?
No.
Est-ce qu'il appartient ici à côté de 22?
Oui.
>> Maintenant, si je suis fou ici, et pas pensant que cela à travers, je pourrais
allouer mon nouveau nœud pour 23.
Je pourrais mettre à jour le pointeur de le nœud appelé 22, pointant
il au nouveau nœud.
Et puis qu'est-ce que je dois mettre à jour le pointeur du nouveau nœud de l'être?
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Exactement.
Pointant à 26.
Mais dammit si je n'avais pas déjà mettre à jour Le pointeur de 22 pour pointer vers ce type, et
maintenant j'ai orphelins, le reste de la liste, pour ainsi dire.
Donc, l'ordre des opérations ici va être importante.
>> Pour ce faire, je pourrais voler, disons, six bénévoles.
Et nous allons voir si nous ne pouvons pas le faire visuellement au lieu du code-sage.
Et nous avons une belle contrainte boules pour vous aujourd'hui.
OK, que diriez-vous un, deux, dans le arrière - sur la fin il.
trois, quatre, deux d'entre vous les gars sur la fin.
Et cinq, six.
Bien sûr.
Cinq et six ans.
Tous droits et nous viendrons à vous les gars la prochaine fois.
Très bien, allez vers le haut.
>> Très bien, puisque vous êtes ici en premier, aimeriez-vous être celui maladroitement
Google en verre ici?
D'accord, donc, OK, verre, enregistrer une vidéo.
OK, vous êtes bon pour aller.
>> D'accord, donc si vous les gars peut venir ici, j'ai préparé à l'avance
quelques chiffres.
Très bien, venez par ici.
Et pourquoi ne vas-tu pas un peu en outre cette façon.
Et Voyons, quel est votre nom, avec le verre de Google?
>> ETUDIANT: Ben.
>> INTERLOCUTEUR 1: Ben?
OK, Ben, vous serez d'abord, littéralement.
Donc, nous allons vous envoyer à la fin de l'étape.
Bon, et ton nom?
>> ETUDIANT: Jason.
>> INTERLOCUTEUR 1: Jason, OK vous aurez être le numéro neuf.
Donc, si vous voulez suivre Ben ça.
>> ETUDIANT: Jill.
>> INTERLOCUTEUR 1: Jill, vous allez être 17, qui, si j'avais fait ce plus
intelligemment, je n'aurais commencé à l'autre extrémité.
Vous allez de cette façon.
22.
Et vous êtes?
>> ETUDIANT: Marie.
>> INTERLOCUTEUR 1: Marie, vous serez 22.
Et votre nom?
>> ETUDIANT: Chris.
>> INTERLOCUTEUR 1: Chris, vous serez 26.
Et puis enfin.
>> ETUDIANT: Diana.
>> INTERLOCUTEUR 1: Diana, vous serez 34.
Donc, vous venez par ici.
>> Très bien, si parfait triés commander déjà.
Et nous allons aller de l'avant et faire ce afin que nous puissions vraiment -
Ben vous êtes juste un peu de recherche out dans le néant là.
OK, nous allons donc aller de l'avant et illustrent cette en utilisant des armes, tout comme je l'étais, exactement,
ce qui se passe.
Alors allez-y et donnez-vous un pied ou deux entre vous.
Et aller de l'avant et pointer d'une main pour celui qui vous doit être dirigée à
sur cette base.
Et si vous êtes nul suffit de pointer tout droit vers le sol.
OK, tout va bien.
>> Alors maintenant, nous avons une liste chaînée, et laissez-moi propose que je vais jouer le rôle de
PTR, donc je ne vais pas porter ce autour.
Et puis - quelqu'un convention stupide - vous pouvez appeler ce que vous voulez -
pointeur prédécesseur, pointeur pred -
c'est juste le surnom que nous avons donné à notre exemple de code pour la main gauche.
L'autre main qui va être maintenant trace de qui est qui dans le
suivant les scénarios.
>> Alors suppose, d'abord, je tiens à arrachez ce premier exemple d'insertion, par exemple
20, dans la liste.
Donc, je vais avoir besoin de quelqu'un pour incarner le numéro 20 pour nous.
J'ai donc besoin de quelqu'un malloc de l'auditoire.
Venez sur place.
Quel est votre nom?
>> ETUDIANT: Brian.
>> INTERLOCUTEUR 1: Brian, tout droit, de sorte que vous est le noeud contenant 20.
Très bien, venez par ici.
Et évidemment, où ne Brian appartient-il?
Ainsi, au milieu de - en fait, Attendez une minute.
Nous faisons cela en panne.
Nous faisons cela beaucoup plus difficile qu'elle doit être au premier abord.
OK, nous allons libre Brian et realloc Brian en cinq ans.
>> OK, maintenant nous voulons insérer Brian que cinq.
Alors venez ici à côté de Ben pour un instant.
Et vous pouvez sans doute dire où cette histoire va.
Mais nous devons penser soigneusement à l'ordre des opérations.
Et c'est justement ce visuel qui va s'aligner
avec ce code échantillon.
Donc ici, je n'ai PTR pointant initialement pas à Ben, en soi, mais quel que soit le
valeur qu'il contient, qui dans ce cas est - quel est votre nom?
>> ETUDIANT: Jason.
>> INTERLOCUTEUR 1: Jason, donc Ben et moi sommes montrant Jason en ce moment.
Alors maintenant, je dois déterminer, où est Brian appartient-il?
Donc la seule chose que j'ai accès à en ce moment, c'est son élément de données n.
Donc, je vais vérifier, n'est- Brian moins de Jason?
La réponse est vrai.
>> Que faut-il maintenant se passer, dans le bon ordre?
J'ai besoin de mettre à jour le nombre de pointeurs Au total dans cette histoire?
Lorsque ma main est toujours pointée vers Jason, et votre main - si vous voulez
mettez votre main comme, en quelque sorte, je Je ne sais pas, un point d'interrogation.
OK, c'est bon.
>> Très bien, alors vous avez quelques candidats.
Soit Ben, moi ou Brian ou Jason ou tout le monde, qui
pointeurs doivent changer?
Combien au total?
>> OK, donc deux.
Mon pointeur ne compte pas vraiment plus parce que je suis juste temporaire.
Donc, ce sont ces deux gars, sans doute, Ben et Brian.
Alors permettez-moi de proposer que nous mettons à jour Ben, depuis qu'il est premier.
Le premier élément de cette liste va maintenant être Brian.
Donc, point de Ben à Brian.
OK, et maintenant?
>> Qui se fait à qui?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: OK si Brian a pour pointer vers Jason.
Mais ai-je perdu la trace de ce pointeur?
Est-ce que je sais où Jason est?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: je le fais, car je suis le pointeur temporaire.
Et sans doute, je n'ai pas changé pour pointer vers le nouveau nœud.
Donc, nous ne pouvons tout simplement avoir point de Brian à qui je suis pointé.
Et nous avons terminé.
Donc un cas, l'insertion à l' au début de la liste.
Il y avait deux étapes principales.
D'abord, nous devons mettre à jour Ben, puis nous devons également mettre à jour Brian.
Et puis je n'ai pas besoin de s'embêter se promènent à travers le reste de l'
liste, car nous avons déjà trouvé son lieu, parce qu'il appartenait à l'
à gauche du premier élément.
>> D'accord, donc assez simple.
En fait, se sent comme nous sommes presque ce qui en fait trop compliqué.
Donc, nous allons maintenant arrachez la fin de la liste, et de voir où
la complexité commence.
Donc, si aujourd'hui, je alloc de l'auditoire.
Tout le monde veut jouer 55?
Bon, j'ai vu votre première main.
Venez sur place.
Ouais.
Quel est votre nom?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Habata.
OK, venez sur place.
Vous serez le numéro 55.
Donc, vous, bien sûr, appartenez à la fin de la liste.
Donc, nous allons rejouer la simulation avec moi étant le PTR pour un instant.
Donc, je vais d'abord faire remarquer à Ben tout est pointé.
Nous sommes tous les deux pointant désormais à Brian.
Donc 55 n'est pas inférieur à cinq.
Donc, je vais me mettre à jour par pointant vers la prochaine pointeur de Brian, qui
maintenant, c'est bien sûr Jason.
55 n'est pas moins de neuf, donc Je vais mettre à jour PTR.
Je vais mettre à jour PTR Je vais mettre à jour PTR.
Et je vais - hmm, ce qui est votre nom?
>> ETUDIANT: Diana.
>> INTERLOCUTEUR 1: Diana pointe, bien sûr, à nulle avec sa main gauche.
Alors d'où vient réellement Habata appartiennent clairement?
Pour la gauche, ici.
Alors, comment puis-je savoir la mettre ici Je crois que j'ai merdé.
Parce que ce qui est PTR art ce moment-là?
NULL.
Ainsi, même si, visuellement, nous pouvons évidemment voir tous ces
gars ici sur scène.
Je n'ai pas gardé la trace de la précédente personne dans la liste.
Je n'ai pas un doigt pointé sur, Dans ce cas, le numéro de noeud 34.
>> Donc, nous allons réellement commencer ce cours.
Alors maintenant, je n'ai réellement besoin une seconde variable locale.
Et c'est ce que vous verrez dans le échantillon réel du code C, alors que je vais,
quand je mets à jour ma main droite pour pointer Jason, laissant ainsi derrière Brian, je
mieux commencer à utiliser ma main gauche pour jour où j'étais, de sorte que je vais
grâce à cette liste -
plus maladroitement que je comptais maintenant ici visuellement -
Je vais aller à l' fin de la liste.
>> Cette main est encore nul, ce qui est assez inutile, sauf pour indiquer
Je suis clairement à la fin de la liste, mais maintenant, au moins, j'ai cette
pointeur prédécesseur pointant ici, maintenant ce que les mains et les pointeurs doivent
être mis à jour?
Dont la main que vous voulez pour reconfigurer le premier?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: OK, donc Diana.
Où voulez-vous faire remarquer Pointeur vers la gauche de Diana à?
À 55 ans, vraisemblablement, de sorte que nous avons inséré là.
Et où doit-55 pointeur aller?
Vers le bas, soit nulle.
Et mes mains, à ce stade, ne le font pas importance car ils étaient juste
variables temporaires.
Alors maintenant, nous avons terminé.
>> Ainsi, la complexité supplémentaire là-bas - et ce n'est pas si difficile à mettre en œuvre,
mais nous avons besoin d'une variable secondaire à faire vous que avant que je passe mon droit
Par contre, je mets à jour la valeur de ma gauche main, pointeur pred dans ce cas, si
que j'ai un pointeur de fuite de garder une trace de l'endroit où je me trouvais.
Maintenant, en passant, si vous songez à ce à travers, cela se sent comme c'est un
peu ennuyeux d'avoir à garder la trace de cette main gauche.
>> Que serait une autre solution à ce problème ont été?
Si vous avez à remodeler les données structure que nous parlons
traverse en ce moment?
Si ce genre de juste se sent un peu ennuyeux d'avoir, comme, deux pointeurs
en passant par la liste, qui d'autre pourrait ont, dans un monde idéal, maintenu
l'information dont nous avons besoin?
Ouais?
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Exactement.
Droit si il ya en fait un intéressant germe d'une idée.
Et cette idée d'un pointeur précédent, pointant vers l'élément précédent.
Que faire si je viens incarné qui à l'intérieur de lui-même la liste?
Et il va être difficile de visualiser ceci sans tout le papier
tomber au sol.
Mais supposons que ces gars-là utilisés à la fois de leurs mains pour avoir un précédent
pointeur, et un pointeur suivant, ainsi mise en œuvre de ce que nous appellerons un doublement
liste chaînée.
Cela me permettra sorte de retour en arrière, beaucoup plus facilement sans moi, l'
programmeur, d'avoir à garder suivre manuellement -
vraiment manuellement -
de l'endroit où j'avais été précédemment dans la liste.
Donc, nous ne le ferons pas.
Nous allons garder les choses simples parce que c'est va venir à un prix deux fois plus
beaucoup d'espace pour les pointeurs, si vous voulez une deuxième.
Mais c'est effectivement un commun Structure de données connu en tant que
doublement liste chaînée.
>> Faisons le dernier exemple ici et mettre ces gars sortir de leur misère.
Alors malloc 20.
Venez sur place à partir de l'allée là-bas.
Bon, quel est votre nom?
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Pardon?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Demeron?
OK venir sur place.
Vous serez 20.
Vous allez évidemment appartiennent entre 17 et 22.
Alors permettez-moi d'apprendre ma leçon.
Je vais commencer à pointer pointant à Brian.
Et je vais avoir ma main gauche seulement mettre à jour à Brian que je passe à
Jason, le contrôle fait 20 moins de neuf?
No.
Est de 20 à moins de 17?
No.
Est de 20 à moins de 22?
Oui.
Alors qu'est-ce pointeurs ou les mains doivent changer où ils pointant maintenant?
>> Ainsi, nous pouvons faire 17 pointant à 20.
Donc, c'est très bien.
Où voulons-nous faire remarquer votre pointeur maintenant?
A 22 ans.
Et nous savons où 22 est, encore une fois merci à mon pointeur temporaire.
Donc, nous sommes OK là.
Donc à cause de ce stockage temporaire J'ai gardé la trace de l'endroit où tout le monde est.
Et maintenant, vous pouvez vous rendre visuellement dans laquelle vous appartenez, et maintenant nous avons besoin de 1, 2, 3,
4, 5, 6, 7, 8, 9 boules d'effort, et une salve d'applaudissements pour
ces gars-là, si nous le pouvions.
Bien fait.
>> [Applaudissements]
>> INTERLOCUTEUR 1: Très bien.
Et vous pouvez garder les morceaux de papier comme souvenirs.
>> Très bien, alors, croyez-moi, c'est beaucoup plus facile de marcher à travers ce avec
l'homme qu'elle ne l'est avec le code réel.
Mais ce que vous trouverez dans un instant Maintenant, est-ce même - oh, merci.
Merci -
c'est que vous verrez que les mêmes données la structure, une liste chaînée, peut effectivement
être utilisée comme un bloc de construction à encore plus des structures de données complexes.
>> Et de réaliser aussi le thème ici est que nous avons absolument introduit plus
complexité dans la mise en œuvre de cet algorithme.
Insertion, et si nous sommes allés à travers elle, suppression et la recherche, est un peu
plus compliqué que cela était avec un tableau.
Mais nous gagnons un certain dynamisme.
Nous obtenons une structure de données d'adaptation.
>> Mais encore une fois, nous payons un prix d'avoir une certaine complexité supplémentaire, à la fois dans
sa mise en œuvre.
Et on nous donne l'accès aléatoire.
Et pour être honnête, il n'y a pas de belles lame propre, je peux vous donner que
dit ici, c'est pourquoi une liste chaînée c'est mieux que un tableau.
Et en rester là.
Parce que le thème récurrent maintenant, même d'autant plus dans les semaines à venir, est
qu'il n'y a pas nécessairement une réponse correcte.
>> C'est pourquoi nous avons séparé l'axe de la conception de séries de problèmes.
Il sera très sensible au contexte si vous souhaitez utiliser ces données
structure ou de celui-là, et il sera dépendra de ce qui compte pour vous en termes
des ressources et de la complexité.
>> Mais permettez-moi de proposer que les données idéales la structure, le saint graal, serait
quelque chose qui est constante de temps, indépendamment de la quantité de choses est
à l'intérieur, il ne serait pas étonnant si une Structure de données renvoyé en réponse
constante de temps.
Oui.
Ce mot est dans votre énorme dictionnaire.
Ou non, ce mot n'est pas.
Or un tel problème.
Eh bien nous allons voir si nous ne pouvons pas au moins faire un pas dans cette direction.
>> Permettez-moi de proposer une nouvelle structure de données qui peut être utilisé pour différentes choses,
dans ce cas appelé une table de hachage.
Et donc nous sommes en fait à en regardant à une rangée, dans ce cas, et
un peu arbitrairement, j'ai dessiné cette table de hachage comme un tableau avec une sorte de
tableau à deux dimensions -
ou plutôt il est dépeint ici comme deux matrice bidimensionnelle - mais c'est juste
un tableau de taille 26, de sorte que si nous appeler le tableau de tableau, le support de table
zéro est le rectangle en haut.
Support tableau 25 est le rectangle au fond.
Et voilà comment je pourrais tirer des données structure dans laquelle je veux stocker
noms des personnes.
>> Ainsi, par exemple, et je ne vais pas attirer l' Tout ça ici sur la tête, si je
eu ce tableau, que je vais maintenant appeler une table de hachage, ce qui est nouveau
emplacement zéro.
Cet emplacement est ici une, et ainsi de suite.
Je prétends que je veux utiliser ces données la structure, pour les besoins du débat,
pour stocker les noms des personnes, Alice et Bob et Charlie et d'autres noms.
Alors, pensez à ce moment que les débuts de, disons, un dictionnaire
avec beaucoup de mots.
Ils ressemblent à des noms dans notre exemple.
Et c'est tout aussi pertinente, peut-être, la mise en œuvre d'un correcteur orthographique, comme nous l'
pourrait par problème posé six.
>> Donc, si nous avons un tableau de taille total de 26 de sorte que c'est l'endroit 25e
au fond, et je prétends que Alice est le premier mot dans le dictionnaire d'
Les noms que je veux insérer dans la RAM, dans cette structure de données, où sont
instincts vous disent que c'est Alice nom devrait aller dans ce tableau?
>> Nous avons 26 options.
Lorsque nous voulons la mettre?
Nous voulons qu'elle en support zéro, non?
A pour Alice, appelons ça nul.
Et B seront un, et C sera deux.
Nous allons donc écrire Le nom d'Alice ici.
Si nous insérons Bob, son nom sera ici.
Charlie va aller ici.
Et ainsi de suite à travers cette structure de données.
>> Il s'agit d'une structure de données merveilleux.
Pourquoi?
Eh bien, quelle est la durée de insérer le nom d'un homme dans cette
structure de données en ce moment?
Étant donné que ce tableau est mis en œuvre, vraiment, comme un tableau.
Eh bien il est temps constant.
C'est l'ordre d'un.
Pourquoi?
>> Eh bien, comment déterminez-vous où Alice appartient?
Vous regardez quelle lettre de son nom?
La première.
Et vous pouvez y arriver, si c'est une chaîne, simplement en regardant chaîne
Support zéro.
Ainsi, le caractère zéro de la chaîne.
C'est facile.
Nous l'avons fait dans la crypto il ya des semaines d'affectation.
Et puis une fois que vous savez que Alice lettre majuscule A, nous pouvons soustraire
off 65 ou au capital A lui-même, qui nous donne zéro.
Donc, nous savons maintenant que Alice appartient au lieu de zéro.
>> Et d'un pointeur sur ces données la structure, en quelque sorte, combien de temps
faut-il pour trouver l'emplacement zéro dans un tableau?
Juste une seule étape, à droite Il est temps constant en raison de la vive nous
proposée était une caractéristique d'un tableau.
Donc en bref, comprendre ce que l'indice du nom d'Alice, qui est, en
ce cas est A, ou disons simplement résoudre que à zéro, où B est un et C est
deux, pensant que les est la constante de temps.
J'ai juste à regarder sa première lettre, déterminer où zéro est une
tableau est également constante de temps.
Donc, techniquement c'est comme deux mesures dès maintenant.
Mais c'est toujours constant.
Nous appelons donc ce grand O d'un seul, c'est pourquoi nous avons Alice inséré dans ce tableau en
constante de temps.
>> Mais bien sûr, je vais être naïf ici, non?
Que faire si il ya une Aaron dans la classe?
Ou Alicia?
Ou tous les autres noms commençant par A. Où allons-nous mettre
que personne, pas vrai?
Je veux dire, en ce moment il ya seulement trois les gens sur la table, alors peut-être nous
devrait mettre Aaron au lieu zéro un deux trois.
>> Bon, je pourrais mettre un ici.
Mais alors, si on cherche à insérer dans David cette liste, où ne vont David?
Maintenant, notre système commence à casser en bas, à droite?
Parce que maintenant, David finit ici si Aaron est en fait ici.
Et maintenant cette idée d'avoir un structure de données propre qui nous donne
insertions de temps constants n'est plus constante de temps, parce que je dois
vérifier, oh, merde, quelqu'un est déjà à l'emplacement d'Alice.
>> Permettez-moi de sonder le reste de ces données la structure, à la recherche d'un endroit pour mettre
quelqu'un comme le nom d'Aaron.
Et cela aussi est en train prendre le temps linéaire.
En outre, si vous voulez maintenant de trouver le Aaron dans cette structure de données, et on
vérifier, et le nom d'Aaron n'est pas ici.
Idéalement, vous voulez juste dire Aaron pas dans la structure de données.
Mais si vous ne commencez à faire de la place pour Aaron où il aurait dû être un D
ou un E, vous, le pire des cas, vérifiez la structure de données tout en
auquel cas il incombe en quelque chose linéaire dans la taille de la table.
>> Alors bon, je vais arranger ça.
Le problème ici, c'est que j'avais 26 éléments dans ce tableau.
Permettez-moi de le changer.
Oups.
Permettez-moi de le modifier de sorte que, au lieu d'être des taille 26 au total, notez le fond
index va changer à n moins 1.
Si 26 est clairement trop petit pour l'homme » noms, parce qu'il ya des milliers d'
noms du monde, nous allons juste faire en 100 ou 1000 ou 10000.
Disons simplement allouer beaucoup plus d'espace.
>> Bien que ne diminue pas nécessairement la probabilité que nous n'aurons pas deux
personnes avec des noms commençant par A, et Ainsi, vous alliez essayer de mettre un
noms au lieu de zéro encore.
Ils vont quand même entrer en collision, ce qui signifie que nous avons encore besoin d'une solution pour mettre
Alice et Aaron et Alicia et autres des noms commençant par A d'ailleurs.
Mais combien d'un problème est le suivant?
Quelle est la probabilité que vous avoir des collisions dans un ensemble de données
structure de ce type?
>> Eh bien, permettez-moi - nous reviendrons à cette question ici.
Et regardez comment nous pourrions résoudre en premier.
Laisse-moi ôter cette proposition ici.
Ce que nous venons de décrire est un algorithme, une heuristique appelée linéaire
sondage dans lequel, si vous avez essayé d'insérer quelque chose dans ces données
la structure, qui est appelé une table de hachage, et il n'y a pas de place là-bas, vous
véritablement sonder la structure de données vérification, est-ce disponible?
Est-ce disponible est cette disposition?
Est-ce disponible?
Et quand il est enfin, vous insérez le nom que vous avez initialement prévu
d'ailleurs à cet endroit.
Mais dans le pire des cas, le seul endroit pourrait être le fond même des données
la structure, la fin du tableau.
>> Alors linéaire sondage, dans le pire des cas, dégénérait en un algorithme linéaire où
Aaron, s'il arrive à être inséré dernier dans cette structure de données, il pourrait
entrer en collision avec ce premier emplacement, mais puis terminer par la malchance à la toute fin.
Ce n'est donc pas une constante temps graal pour nous.
Cette approche de l'insertion des éléments dans une structure de données appelée un hachage
tableau ne semble pas être la constante de temps du moins pas dans le cas général.
Il peut dégénérer en quelque chose de linéaire.
>> Alors que faire si nous résolvons collisions un peu différemment?
Alors, voici un plus sophistiqué approcher de ce qui est encore
appelée une table de hachage.
Et par hachage, en aparté, que Je veux dire, c'est l'indice que
J'ai parlé plus tôt.
Pour quelque chose de hachage peut être considéré comme un verbe.
>> Donc, si vous hachage Alice c'est un nom, une fonction de hachage, pour ainsi dire,
doit retourner un nombre.
Dans ce cas, est nulle si elle appartient à emplacement zéro, un, si elle appartient à
une localisation, et ainsi de suite.
Donc, ma fonction de hachage a été jusqu'ici super simple, uniquement en regardant le
première lettre du nom de quelqu'un.
Mais une fonction de hachage prend comme entrée un morceau de données, un
chaîne, un int, peu importe.
Et il crache généralement un certain nombre.
Et ce nombre est l'endroit où ces données élément appartient à une structure de données
connu ici comme une table de hachage.
>> Il suffit donc de manière intuitive, c'est un contexte légèrement différent.
Cette réalité se réfère à un exemple impliquant des anniversaires, le cas
il pourrait y avoir le plus grand nombre 31 jours dans le mois.
Mais qu'est-ce que cette personne décide d' faire dans le cas d'une collision?
Contexte être maintenant, pas une collision noms, mais une collision anniversaires,
Si deux personnes ont le même anniversaire sur Le 2 Octobre, par exemple.
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Ouais, donc nous avons ici la mise à profit des listes chaînées.
Ainsi, il semble un peu différemment que nous avons tiré plus tôt.
Mais nous semblons avoir à un tableau sur le côté gauche.
C'est un indice, sans raison particulière.
Mais c'est toujours un tableau.
C'est un tableau de pointeurs.
Et chacun de ces éléments, chacun de ces cercles ou des barres obliques - La barre oblique
soit nulle - chacune de ces pointeurs est apparemment pointant vers
quelle structure de données?
Une liste chaînée.
>> Alors maintenant, nous avons la capacité de coder en dur dans notre programme
la taille de la table.
Dans ce cas, nous savons qu'il ya jamais plus de 31 jours à un mois.
Donc, le codage en dur une valeur comme 31 est raisonnable dans ce contexte.
Dans le cadre de noms, le codage en dur 26 n'est pas déraisonnable Ce sont des gens
Les noms ne commencent avec, par exemple, l'alphabet impliquant de A à Z.
>> Nous pouvons entasser tous dans ces données Structure tant que, lorsque nous aurons une
collision, nous ne mettons pas les noms ici, nous pensons que la place de ces cellules
pas comme des chaînes elles-mêmes, mais aussi pointeurs vers, par exemple, Alice.
Et puis Alice peut avoir un autre pointeur à un autre nom commençant par
A. Et Bob va réellement ici.
>> Et si il ya un autre nom commence avec B, il se retrouve ici.
Et ainsi de chacun des éléments de cette tableau à deux, si nous avons conçu ce une
peu plus intelligemment -
s'allumer -
si nous avons conçu ce un peu plus habilement, devient maintenant une donnée adaptatifs
la structure, où il n'ya pas de limite stricte sur le nombre d'éléments que vous pouvez insérer
en elle, parce que si vous n'avez une collision, c'est très bien.
Il suffit d'aller de l'avant et l'annexer au ce que nous avons vu il ya un peu était
connue sous le nom d'une liste liée.
>> Eh bien nous allons mettre en pause pendant un moment.
Quelle est la probabilité d'une collision en premier lieu?
A droite, je suis peut plus penser, peut-être Je suis sur les directions techniques à ce problème,
parce que vous savez quoi?
Oui, je peux venir avec arbitraire exemples sur le dessus de ma tête comme
Allison et Aaron, mais en réalité, compte tenu d'une distribution uniforme de
entrées, soit des insertions aléatoires dans une structure de données, ce qui est vraiment
la probabilité d'une collision?
Bien s'avère, il s'agit en fait très élevé.
Permettez-moi de généraliser cette problème, c'est que cela.
>> Donc, dans une chambre de n CS50 étudiants, ce qui est la probabilité qu'au moins
deux élèves dans la salle avoir la même date d'anniversaire?
Donc, il ya quoi. quelques Hund -
200, 300 gens d'ici et plusieurs centaine de personnes à la maison aujourd'hui.
Donc, si vous vouliez nous demander ce que c'est la probabilité que deux personnes
dans cette pièce ayant la même date d'anniversaire, nous pouvons comprendre cela.
Et je prétends fait il ya deux les personnes ayant la même date d'anniversaire.
>> Par exemple, personne ne avoir anniversaire aujourd'hui?
Hier?
Demain?
D'accord, donc il se sent comme je vais d'avoir à faire ce 363 ou plus si
fois pour réellement comprendre Si nous avons une collision.
Ou on pourrait faire cela mathématiquement plutôt que péniblement
faire.
Et proposer ce qui suit.
>> Je propose donc que nous pourrions modéliser l' probabilité de deux personnes ayant le
même jour que la probabilité de 1 moins la probabilité de personne ayant
le même anniversaire.
Donc, pour obtenir cela, et ce n'est que le façon élégante de la rédaction du présent, pour l'
première personne dans la chambre, il ou elle peut avoir l'une quelconque de la possible
anniversaires supposant 365 jours de l'année, avec mes excuses aux personnes atteintes
le 29e anniversaire Février.
>> Donc, la première personne dans cette salle est libre d'avoir un certain nombre de anniversaires
sur les 365 possibilités afin que nous ferons ce que 365 divisé par 365,
qui est une.
La prochaine personne dans la salle, si l'objectif est d'éviter une collision, ne peut
avoir son anniversaire sur la façon plusieurs jours possibles?
364.
Donc, le deuxième terme de cette expression est faisant essentiellement que les maths pour nous
en soustrayant off un jour possible.
Et puis, le lendemain, le lendemain, l' lendemain vers le bas pour le nombre total
de personnes dans la salle.
>> Et si l'on considère alors, quel est alors la probabilité de ne pas avoir tout le monde
anniversaires uniques, mais encore une fois 1 moins que, ce que nous obtenons est une expression
qui peut très fantaisiste ressembler à ceci.
Mais il est plus intéressant d'examiner visuellement.
Il s'agit d'un tableau où sur l'axe des x est le nombre de personnes dans la salle, l'
nombre d'anniversaires.
Sur l'axe des y est la probabilité d'une collision, deux personnes
ayant la même date d'anniversaire.
>> Et les plats à emporter à partir de cette courbe est que, dès que vous arrivez à comme 40
étudiants, vous êtes-vous à une probabilité de 90% combinatorically des deux
personnes ou plus ayant le même anniversaire.
Et une fois que vous arrivez à 58 personnes comme il est près de 100% de chance les deux
personnes dans la salle vont avoir la même anniversaire, même si il ya
365 ou 366 seaux possibles, et seulement 58 personnes dans la salle.
Juste statistiquement vous êtes susceptible d' obtenir collisions, qui en bref
motive cette discussion.
Que même si nous obtenons de fantaisie ici, et commencez à avoir ces chaînes, nous sommes encore
va avoir collisions.
>> Alors que se poser la question, quel est le coût de faire des insertions et des suppressions
dans une structure de données comme ça?
Eh bien laissez-moi vous proposer -
et permettez-moi de revenir à l'écran sur ici - si nous avons des éléments N dans le
liste, donc si nous essayons d'insérer n éléments, et nous avons
combien au total seaux?
Disons total de 31 seaux dans le cas des anniversaires.
Quelle est la longueur maximale d'un de ces chaînes potentiellement?
>> Si encore il ya 31 possible anniversaires dans un mois donné.
Et nous sommes en train de s'agglutiner tout le monde -
En fait, c'est un exemple stupide.
Faisons 26 place.
Donc, si effectivement avoir des personnes dont les noms commencer par A à Z, donnant ainsi
nous 26 possibilités.
Et nous utilisons une structure de données comme celle que nous venons de voir, par lequel nous avons
un tableau de pointeurs, dont chacun pointe vers une liste liée, où l'
première liste est tout le monde avec le nom Alice.
La deuxième liste est tout à l' le nom commence par A, à partir
avec B, et ainsi de suite.
>> Quelle est la durée probable de chacune des ces listes si l'on suppose un bien propre
Répartition des noms de A à Z à travers la structure de données entier?
Il ya n personnes dans la structure de données divisé par 26, si elles sont bien
étaler sur toute la structure de données.
Ainsi, la longueur de chacun de ceux-ci chaînes est n divisé par 26.
Mais en gros notation O, c'est quoi?
Qu'est ce que c'est vraiment?
Donc, c'est vraiment juste n, non?
Parce que nous avons dit dans le passé, ugh que vous divisez par 26.
Oui, en réalité, il est plus rapide.
Mais en théorie, il n'est pas fondamentalement tout cela rapidement.
>> Donc, nous ne semblons pas être tant que ça rapprocher de ce Saint-Graal.
En fait, c'est juste le temps linéaire.
Heck, à ce point, pourquoi ne pas nous il suffit d'utiliser une énorme liste chaînée?
Pourquoi ne pas simplement utiliser un énorme tableau pour stocker les noms des
tout le monde dans la salle?
Eh bien, est-il encore quelque chose convaincant sur une table de hachage?
Est-il encore quelque chose de convaincant sur une structure de données
qui ressemble à ceci?
Cette.
>> ETUDIANT: [inaudible].
>> ENCEINTE 1: Oui, et encore si c'est juste un algorithme en temps linéaire, et un
la structure de données en temps linéaire, pourquoi ne pas simplement stocker le nom de tout le monde dans une grande
tableau ou dans une grande liste chaînée?
Et cesser de faire des CS d'autant plus difficile qu'elle doit être?
Ce qui est convaincant à ce sujet, même si j'ai gratté it out?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: insertions ne sont pas?
Plus cher.
Alors insertions potentiellement pourrait encore être constante de temps, même si vos données
la structure ressemble à ceci, un tableau de pointeurs, dont chacun est dirigé vers
éventuellement une liste chaînée.
Comment pourriez-vous réaliser constant insertion de temps de noms?
Collez-le sur le devant, à droite?
>> Si nous sacrifions un objectif de conception de plus tôt, là où nous voulions garder
Le nom de tout le monde, par exemple, triée, ou tous les numéros sur scène triés,
Supposons que nous avons une non triés liste chaînée.
Il ne nous coûte une ou deux étapes, comme dans le cas de Ben et Brian
précédemment, à insérer un élément à le début de la liste.
Donc, si nous ne nous préoccupons pas de tri tous des noms commençant par A ou tout
les noms commençant par B, nous pouvons encore atteindre insertion de temps constant.
Maintenant regardant Alice ou Bob ou tout autre nom plus généralement est encore quoi?
Il est grand O de n divisé par 26, dans le cas idéal où tout le monde est uniformément
distribué, où il ya le plus grand nombre de A car il ya de Z, qui est probablement
irréaliste.
Mais c'est toujours linéaire.
>> Mais ici, nous revenons au point de notation asymptotique être
théoriquement vrai.
Mais dans le monde réel, si je prétends que mon programme peut faire quelque chose 26 fois
plus rapide que le vôtre, dont le programme allez-vous préférer utiliser?
La vôtre ou la mienne, qui est 26 fois plus rapide?
De façon réaliste, la personne dont est 26 fois plus rapide, même si théoriquement
nos algorithmes fonctionnent de la même asymptotique temps d'exécution.
>> Permettez-moi de proposer un autre solution tout à fait.
Et si cela ne veut pas souffler votre esprit, nous sommes hors des structures de données.
Alors c'est un trie -
genre d'un nom stupide.
Il vient de récupérations, et le mot est orthographié trie, t-r-i-e, en raison de
récupération de cours ressemble à Trie.
Mais c'est l'histoire du mot trie.
>> Donc un trie est en effet un certain type d'arbre, et c'est aussi un jeu de ce mot.
Et même si vous ne pouvez pas tout voir avec cette visualisation, une trie est un
arbre structuré comme un arbre généalogique avec un ancêtre dans la partie supérieure et beaucoup
des petits-enfants et arrière-petits- Comme les feuilles sur le fond.
Mais chaque noeud dans un trie est un tableau.
Et c'est dans un tableau - et LET'S simplifier à l'extrême pour un moment - c'est un
tableau, dans ce cas, de taille 26, où chaque nœud est à nouveau un tableau de taille
26, où l'élément de rang zéro en ce que matrice représente A, et le dernier
élément dans chacun de ces tableau représente Z.
>> Je propose donc que ces données la structure, connue comme une structure arborescente, peut être
utilisé également pour stocker les mots.
Nous avons vu il ya un instant comment nous pourrions stocker mots, ou dans ce cas les noms, et nous
vu plus haut comment nous pouvons stocker des nombres, mais si nous nous concentrons sur des noms ou des chaînes
ici, notez ce qui est intéressant.
Je prétends que le nom Maxwell est à l'intérieur de cette structure de données.
Où voyez-vous Maxwell?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Sur la gauche.
Donc ce qui est intéressant avec ces données structure est plutôt que de stocker l'
chaîne M-A-X-W-E-L-L oblique zéro, tout contiguë, ce que vous faites place
est la suite.
Si c'est un trie comme structure de données, chacun des nœuds dont est encore un tableau,
et vous voulez stocker Maxwell, vous devez d'abord index et ainsi de noeud de la racine, de sorte
parler, le nœud le plus haut, à l'emplacement M, à droite, de sorte
à peu près dans la moyenne.
Et puis à partir de là, vous suivez un pointeur à un enfant nœuds, pour ainsi dire.
Ainsi, dans le sens de l'arbre généalogique, vous suivez le bas.
Et qui vous mènera vers un autre nœud sur la gauche, il ya, ce qui est
juste un autre tableau.
>> Et puis si vous voulez stocker Maxwell, vous trouverez le pointeur qui représente
A, qui est celui-là.
Ensuite, vous passez au nœud suivant.
Et remarquez - c'est pourquoi le tableau de un peu décevant -
ce nœud super look minuscule.
Mais à droite de cette est Y et Z. C'est juste l'auteur a tronqué
image de sorte que vous avez réellement voir les choses.
Sinon cette image serait extrêmement large.
Alors maintenant, vous indice dans l'emplacement X, puis W, E, puis L, puis L. Ensuite, ce qui est
cette curiosité?
>> Eh bien, si nous utilisons ce genre de nouvelle prendre sur la façon de stocker une chaîne dans un
structure de données, vous avez encore besoin d' essentiellement cocher dans les données
Structure qu'un mot se termine ici.
En d'autres termes, chacun de ces nœuds en quelque sorte a se rappeler que nous
effectivement suivi toutes ces pointeurs et sont en laissant un peu
mie de pain au fond ici de cette Structure pour indiquer M-A-X-W-E-L-L est
En effet, dans cette structure de données.
>> Donc, nous pourrions procéder comme suit.
Chacun des noeuds dans l'image que nous venons de scie a un, un tableau de la taille 27.
Et il est maintenant 27, car en p fixé six, nous allons vous donner réellement une apostrophe,
afin que nous puissions avoir des noms comme O'Reilly et d'autres avec des apostrophes.
Mais même idée.
Chacun de ces éléments dans l' tableau pointe vers une structure
noeud, donc juste un nœud.
Donc, ce n'est pas sans rappeler de notre liste chaînée.
>> Et puis j'ai un booléen, que je vais appelez mot, qui va juste être
vrai si un mot se termine à cette noeud de l'arbre.
Il représente effectivement la petite triangle, nous avons vu il ya un instant.
Donc, si un mot se termine à ce nœud dans le arbre, ce champ de texte sera vrai,
qui est conceptuellement cochant ou nous nous appuyons ce triangle, oui, il
est un mot ici.
>> Il s'agit donc d'un trie.
Et maintenant, la question est, qu'est-ce est sa durée?
Est-il grand O de n?
Est-ce autre chose?
Eh bien, si vous avez n noms de ces données la structure, Maxwell étant juste un des
eux, quelle est la durée de d'insérer ou de trouver Maxwell?
Quelle est la durée de fonctionnement l'insertion de Maxwell?
S'il ya d'autres noms n déjà dans le tableau?
Ouais?
>> ETUDIANT: [inaudible].
>> INTERLOCUTEUR 1: Ouais, c'est la longueur du nom, non?
Alors M-a-x-w-e-l-l il se sent comme ce algorithme est grand O de sept ans.
Maintenant, bien sûr, le nom variera en longueur.
Peut-être que c'est un nom court.
C'est peut-être un nom plus long.
Mais ce qui est important ici, c'est que c'est un nombre constant.
Et c'est peut-être pas vraiment constant, Mais Dieu, si réaliste, dans un
dictionnaire, il ya probablement une certaine limite le nombre de lettres dans un
Le nom de la personne dans un pays donné.
>> Et si nous pouvons supposer que valeur est une constante.
Je ne sais pas ce que c'est.
Il est probablement plus grand que nous pensons qu'il est.
Parce qu'il ya toujours un coin cas avec un nom fou longtemps.
Alors, appelons-k, mais il ya toujours un constant sans doute, parce que chaque
nom dans le monde, au moins dans un pays en particulier, est que la longueur ou
plus courte, il est donc constant.
Mais quand nous avons dit que quelque chose est grand O d'une valeur constante, qu'est-ce que
vraiment équivalent à?
C'est vraiment la même chose comme disant constante de temps.
>> Maintenant, nous sommes en quelque sorte de tricherie, pas vrai?
Nous sommes en quelque sorte l'effet de levier un peu de théorie ici pour dire que bien, de l'ordre de k est
vraiment il suffit de commander d'un seul, et il est temps constant.
Mais il est vraiment.
Parce que l'idée fondamentale ici est que si nous avons n noms déjà dans cette
structure de données, et nous insert Maxwell, est la quantité de temps qu'il nous faut pour
insérer Maxwell à toutes les personnes touchées par combien d'autres personnes
sont dans la structure de données?
Ne semble pas l'être.
Si j'avais un milliard de plus d'éléments à ce trie, puis insérez Maxwell, est
il du tout affecté?
No.
Et ce n'est pas comme des données jour structures que nous avons vu jusqu'à présent, où
le temps d'exécution de votre algorithme est complètement indépendante de la quantité d'
substance est ou n'est pas déjà en ce que la structure de données.
>> Et ainsi, avec cette offre vous est désormais un occasion pour p fixé six, qui sera
de nouveau impliquer la mise en œuvre de votre propre correcteur orthographique, la lecture en 150.000
termes, la meilleure façon de stocker cette n'est pas nécessairement évident.
Et si j'ai aspiré à trouver le Saint-Graal, je n'ai pas
prétendre qu'il est un trie.
En fait, une table de hachage peut très bien s'avérer beaucoup plus efficace.
Mais ce ne sont là -
ce n'est que l'une des décisions de conception vous aurez à faire.
>> Mais en fermant prenons 50 ou plus secondes pour jeter un œil à ce qui se trouve
prochaine semaine à venir et au-delà, nous transition à partir de cette ligne de commande
monde si les programmes C à des choses web fondé et langages comme PHP et
JavaScript et de l'Internet lui-même, protocoles comme HTTP, que vous avez
pris pour acquis pendant des années maintenant, et j'ai tapé plus chaque
jour, peut-être, ou vu.
Et nous allons commencer à peler la des couches de ce qui est l'Internet.
Et quel est le code qui sous-tend les outils d'aujourd'hui.
Donc 50 secondes de ce teaser ici.
Je vous donne guerriers du Net.
>> [LECTURE VIDEO]
>> -Il est venu avec un message.
Avec un protocole qui lui est propre.
Il est venu à un monde de pare-feu cruels, routeurs insensible, et les dangers loin
pire que la mort.
Il est rapide.
Il est fort.
Il est TCPIP.
Et il a votre adresse.
Guerriers du filet.
>> [FIN LECTURE VIDÉO]
>> INTERLOCUTEUR 1: C'est ainsi que l'internet doit travailler dès la semaine prochaine.