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. 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 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.