ENCEINTE 1: Très bien, donc cela est CS50 Ceci est la fin de la semaine de cinq. Et de rappeler que la dernière fois nous commencé à regarder les données fantaisistes structures qui ont commencé à résoudre problèmes, qui ont commencé à introduire des de nouveaux problèmes, mais la clé de cette était le genre de filetage que nous commencé à faire de nœud à nœud. Donc, cela est bien sûr une liste chaînée. Et par chaînée, Je veux dire il ya juste un faufiler entre chacun de ces nœuds. Avère que vous pouvez faire colombophile des choses comme des listes doublement chaînées par lequel vous avez une flèche aller dans les deux sens, ce qui peut aider avec une certaine efficacité. Mais cela a résolu le problème? Quel problème est-ce à résoudre? Pourquoi avons-nous soucions le lundi? Pourquoi, en théorie, ne nous nous soucions le lundi? Qu'est ce que ça fait? 

PUBLIC: Nous pouvons dynamiquement redimensionner. 

ENCEINTE 1: OK, alors nous pouvons redimensionner dynamiquement. Bravo à vous deux. Ainsi, vous pouvez redimensionner dynamiquement cette Structure de données, alors un tableau, rappel, vous avez à connaître priori comment vous voulez beaucoup d'espace et si vous avez besoin d'un peu plus espace, vous êtes un peu hors de la chance. Vous devez créer un tout nouveau tableau. Vous devez déplacer tous vos les données d'un à l'autre, finalement libérer l'ancien tableau si vous le pouvez, et ensuite procéder. Qui se sent juste très coûteux et très inefficace, et en effet il peut être. Mais ce ne sont pas tous bons. Nous payons un prix, ce qui a été l'un des prix plus évidentes, nous payer en utilisant une liste chaînée? 

PUBLIC: Nous devons utiliser espace double pour chacun. ENCEINTE 1: Ouais, donc nous avons besoin au moins deux fois autant d'espace. En fait, je me rendis compte de cette image même un peu trompeur, parce que sur CS50 IDE dans un lot de moderne ordinateurs, un pointeur ou une adresse est pas en fait quatre octets. Il est très souvent ceux-ci huit jours octets, ce qui des moyens le plus bas rectangles là dans la réalité sont sorte de deux fois grand que ce que je l'ai dessiné, ce qui signifie que vous utilisez trois fois plus autant d'espace que nous pourrions avoir autrement. Maintenant, dans le même temps, nous sommes parle encore octets, non? Nous ne parlons pas nécessairement mégaoctets ou gigaoctets, sauf si ces structures de données deviennent grands. 

Et aujourd'hui, nous commençons à considérer comment nous pourrions explorer les données plus efficacement en cas de fait, les données devient plus grand. Mais nous allons essayer de canoniser les premières opérations que vous pouvez faire sur ces les types de structures de données. Donc, quelque chose comme un lien liste prend généralement en charge Les opérations telles que supprimer, insérer et rechercher. Et qu'est-ce que je veux dire par là? Cela signifie juste que généralement, si les gens utilisent liste chaînée, ils ou quelqu'un d'autre a mis en place fonctions telles que supprimer, insérer, et la recherche, afin que vous puissiez réellement faire quelque chose utile avec la structure de données. Donc, nous allons jeter un coup d'œil comment nous pourrions mettre en œuvre un peu de code pour une liste chaînée comme suit. 

Donc, ceci est juste un peu de code C, même pas un programme complet que je très rapidement fouetté. Il est pas en ligne dans la distribution code, car il ne sera pas réellement fonctionner. Mais remarquez que je viens avec un commentaire dit, Dot Dot Dot, il ya quelque chose là, Dot Dot Dot, quelque chose là. Et disons simplement Regardons ce que les parties sont juteuses. Donc, sur la ligne de trois, Rappelons que ce est maintenant nous avons proposé de déclarer un nœud dernière temps, l'un de ces objets rectangulaires. Il a un int que nous appellerons N, mais nous pourrions l'appeler quelque chose, puis une star du noeud de struct appelé prochaine. Et juste pour être clair, ce deuxième ligne, sur la ligne de six, ce qui est qui? Que fait-il pour nous? Parce qu'il ressemble certainement plus cryptique que nos variables habituelles. 

PUBLIC: Il fait bouger plus d'un. 

ENCEINTE 1: Il fait bouger plus d'un. Et pour être plus précis, il va stocker l'adresse du noeud qui est destiné à être sémantiquement à côté de lui, non? Donc, il ne va pas déplacer nécessairement quelque chose. Il va juste stocker une valeur, qui est va être l'adresse d'un autre noeud, et voilà pourquoi nous avons dit struct noeud étoiles, l'étoile dénotant un pointeur ou une adresse. OK, maintenant si vous supposer que nous avons ce N disponible pour nous, et nous allons supposer que quelqu'un d'autre a inséré tout un tas d'entiers dans une liste chaînée. Et cette liste est liée pointée par un certain point une variable appelée liste qui est adoptée ici en tant que paramètre, comment puis-je aller sur la ligne 14 mise en œuvre de la recherche? En d'autres termes, si je suis la mise en œuvre fonction dont le but dans la vie est de prendre un int, puis le début d'une liste chaînée, qui est un pointeur vers la liste chaînée. Comme la première, qui, je pense David était notre bénévole le lundi, il pointait toute la liste chaînée, il est comme si nous passons David en tant que notre argumentation ici. Comment allons-nous traverser cette liste? Eh bien, il se trouve que même si pointeurs sont relativement nouvelle pour nous maintenant, nous pouvons le faire relativement carrément. 

Je vais aller de l'avant et déclarer une variable temporaire par convention va tout simplement d'être appelé pointeur, ou PTR, mais vous pourriez l'appeler ce que vous voulez. Et je vais initialiser au début de la liste. Ainsi, vous pouvez sorte de penser de cette comme me l'enseignant, l'autre jour, sorte de pointage à quelqu'un parmi nos humains en tant que bénévoles. Je suis donc une variable temporaire qui est pointant simplement la même chose que notre hasard nommé David a également été bénévole soulignant. Maintenant, alors que le pointeur est non nulle, parce rappel que nulle est une valeur sentinelle spéciale la délimite la fin de la liste, Ainsi, alors que je ne suis pas au pointage sol comme notre dernière bénévoles était, Allons de l'avant et faire ce qui suit. Si pointer-- et maintenant je veux sorte de de faire ce que nous avons fait avec l'étudiant structure-- si le pointeur point à côté equals-- plutôt, si le pointeur point N est égal est égal à la variable N, la l'argument qui a été transmis, alors je veux aller de l'avant et dire return true. Je l'ai trouvé le numéro N intérieur de l'un des nœuds de ma liste chaînée. Mais le point plus qui fonctionne dans ce contexte, parce pointeur, PTR, est en effet un pointeur, une adresse, Nous pouvons en fait merveille enfin utiliser un morceau de syntaxe ce genre de marques sens intuitif et effectivement utiliser une flèche ici, ce qui signifie aller de cette adresse à l'entier là dans. Il est donc très similaire dans esprit de l'opérateur point, mais parce que le pointeur est pas un pointeur et pas une structure elle-même, nous utilisons simplement la flèche. 

Donc, si le noeud courant que moi, variable temporaire, me montre du doigt N est pas, qu'est-ce que je veux faire? Eh bien, avec mes volontaires humains que nous avons eu ici l'autre jour, si mon premier humain est pas celui que je veut, et peut-être le deuxième homme est pas celui que je veux, et le troisième, je besoin de bouger physiquement. Comme comment puis-je passerai une liste? Quand nous avons eu un tableau, vous juste fait comme je l'ai plus plus. Mais dans ce cas, il suffit de faire pointeur, obtient, pointeur, à côté. En d'autres termes, le champ suivant est comme toutes les mains gauches que nos volontaires humains lundi utilisaient pour pointer vers un autre nœud. Ce sont leurs prochains voisins. 

Donc, si je veux passer en revue cette liste, Je ne peux pas le faire, je plus plus plus, Je dois dire à la place I, pointeur, va à égale quel que soit le champ suivant est, le champ suivant est, le champ suivant est, suivant toutes ces mains gauches que nous avions sur le pointage de scène pour certaines valeurs suivantes. Et si je reçois par que l'ensemble de l'itération, et enfin, je frappe null ne pas avoir N trouvé encore, je reviens tout simplement fausse. Encore une fois, tout ce que nous faisons ici, selon l'image il ya un instant, commence en pointant à la début de la liste sans doute. Et puis je vérifie, est la valeur Je cherche égal à neuf? Si oui, je reviens vrai et je suis fait. Si non, je mets à jour ma main, Alias ​​pointeur, pour pointer à l'emplacement de la prochaine flèche, et puis l'emplacement de la prochaine flèche, et la suivante. Je suis tout simplement la marche à travers ce réseau. 

Donc encore une fois, qui se soucie? Comme quoi est-ce un ingrédient pour? Eh bien, rappelons que nous avons lancé la notion d'une pile, qui est de type dans la mesure où une donnée abstraite comme il est pas une chose de C, il est pas une chose de CS50, il est une idée abstraite, cette idée de empiler sur des choses dessus de l'autre qui peut être mis en œuvre dans des grappes de différentes manières. Et une façon que nous avons proposé était avec un tableau, ou avec une liste chaînée. Et il se trouve que canoniquement, un pile prend en charge au moins deux opérations. Et les mots à la mode sont poussée, à pousser quelque chose sur la pile, comme un nouveau plateau dans le salle à manger, ou de la pop, ce qui signifie pour enlever le plus élevé plateau de la pile dans la salle salle, et puis peut-être un peu d'autres opérations ainsi. Alors, comment pouvons-nous définir la structure que nous appelons maintenant une pile? 

Eh bien, nous avons tout le nécessaire la syntaxe à notre disposition en C. Je dis, me donner une définition de type de une structure à l'intérieur d'une pile, Je vais dire est un tableau, d'un tas ensemble de nombres, puis la taille. Donc, en d'autres termes, si je veux à mettre en œuvre dans votre code, laissez-moi partir et juste sorte de dessiner ce que cela veut dire. Donc, cela veut dire, me donner un la structure qui a obtenu un tableau, et je ne sais pas quelle est la capacité, il est apparemment une constante que je l'ai définis ailleurs, et ça va. Mais supposons qu'il est juste un, deux, trois, quatre, cinq. Donc, la capacité est de 5. Cet élément intérieur de ma structure sera appelée numéros. Et puis je besoin d'un une autre variable apparemment appelé taille qui d'abord je vais à prévoir est initialisée à zéro. Si il n'y a rien dans la pile, la taille est égale à zéro, et il est des valeurs parasites en nombre. Je ne sais pas ce qu'il ya dedans pour l'instant. 

Donc, si je veux pousser quelque chose sur la pile, suppose que je l'appelle la fonction Push, et Je dis pousser 50, comme le nombre 50, où voulez-vous proposer Je dessine dans ce tableau? Il ya cinq réponses différentes possibles. Où voulez-vous de pousser le numéro 50? Si le but ici, encore une fois, appeler le fonction Push, passer dans un argument 50, où dois-je le mettre? Cinq possible-- 20% de chances de deviner correctement. Oui? 

AUDIENCE: Extrême droite. 

ENCEINTE 1: Extrême droite. Il ya maintenant une chance de 25% de deviner correctement. Donc, ce serait effectivement bien. Par convention, je vais le dire avec un tableau, nous aurions commence généralement à gauche, mais nous pourrions certainement commence à la droite. Donc, le spoiler ici serait que je suis va probablement dessiner sur la gauche, Tout comme dans un tableau normal où Je commencer à aller de gauche à droite. Mais si vous pouvez retourner l'arithmétique, très bien. Il est tout simplement pas conventionnelle. OK, je dois faire un plus de changement cependant. Maintenant que je l'ai poussé quelque chose sur la pile, ce qui est la prochaine étape? 

Très bien, je dois augmenter la taille. Alors laissez-moi aller de l'avant et juste mettre à jour ce qui était de zéro. Et au lieu maintenant, je vais de mettre en la valeur un. Et maintenant suppose que je pousse un autre numéro sur la pile, comme 51. Eh bien, je dois faire un de plus changement, qui est à la taille deux. Et puis suppose que je pousse un de plus numéro sur la pile comme 61, maintenant je dois mettre à jour la taille d'un plus temps, et obtenir la valeur 3 comme la taille. Et maintenant, je suppose appelle pop. Maintenant, pop, par convention, ne prenez pas un argument. Avec une pile, l'ensemble point de la métaphore de plateau est que vous ne disposez pas de la discrétion d'aller chercher ce plateau, tout ce que vous pouvez faire est pop la plus haute un de la pile, juste parce que. Voilà ce que cette structure de données fait. 

Ainsi, en ce que si la logique I dire pop, ce qui se détache? Donc 61. Donc ce qui est vraiment l'ordinateur va faire dans la mémoire? Qu'est-ce que mon code a à voir? Que proposeriez-vous nous changeons sur l'écran? Qu'est-ce qui devrait changer? Pardon? Nous sommes tellement débarrassés de 61. Donc, je peux certainement le faire. Et je peux me débarrasser de 61. Et puis ce que les autres le changement doit se produire? Taille a probablement revenir à deux. Et alors ça va. Mais attendez une minute, la taille il ya un moment était trois. Disons simplement faire une vérification de cohérence rapide. Comment avons-nous savons que nous voulait se débarrasser de 61? Parce que nous sommes popping. Et donc je dois cette seconde taille de la propriété. 

Attendez une minute, je suis repensant à deux semaines lorsque nous avons commencé à parler tableaux, où cela était l'emplacement zéro, ce fut l'un emplacement, ce fut emplacement deux, cet emplacement est trois, quatre, il semble que le relation entre la taille et l'élément que je veux supprimer à partir du tableau semble juste être quoi? Taille moins un. Et voilà comment en tant qu'êtres humains nous savons 61 vient en premier. Comment est l'ordinateur va savoir? Lorsque votre code, où vous avez probablement vouloir faire la taille moins un, donc trois moins un est de deux, et que signifie que nous voulons nous débarrasser de 61 ans. Et puis, nous pouvons en effet de mettre à jour la taille de sorte que la taille maintenant va de trois à deux seulement. Et juste pour être pédant, je vais de proposer que je suis fait, non? Vous avez proposé intuitivement correctement je devrais me débarrasser de 61. Mais avoir pas que je sorte de sorte d'débarrassé de 61? Je l'ai effectivement oublié qu'il est vraiment là. Et penser à PSET4, si vous avez lu l'article sur la médecine légale, le PDF que nous devions vous les gars lire, ou vous lira cette semaine pour PSET4. Rappelons que ce soit réellement germane à l'idée de la criminalistique informatique. Qu'est-ce que le fait généralement un ordinateur est il oublie juste où quelque chose est, mais il ne va pas et comme essayer de gratter sur ou override ces bits avec zéros et de uns ou quelque autre motif aléatoire sauf si vous vous le faire volontairement. Donc, votre intuition était droite, débarrassons-nous de 61 ans. Mais en réalité, nous ne devons pas la peine. Nous avons juste besoin d'oublier que il est là en changeant notre taille. 

Maintenant, il ya un problème avec cette pile. Si je continue à pousser les choses sur la pile, ce qui est évidemment va se passer en un temps de quelques instants? Nous allons manquer d'espace. Et que faisons-nous? Nous sommes en quelque sorte des foutus. Cette mise en œuvre ne laisse pas nous redimensionner le tableau, parce que l'utilisation cette syntaxe, si vous penser à la deuxième semaine, une fois que vous avez déclaré la taille d'un tableau, nous avons pas encore vu où un mécanisme vous pouvez changer la taille du tableau. Et en effet, C n'a pas cette fonctionnalité. Si vous dites me donner cinq NTHS, appeler les numéros, voilà tout, vous allez obtenir. Donc, nous faisons maintenant à partir de lundi, avons la capacité à exprimer une solution cependant, nous avons juste besoin de tordre la définition de notre pile de ne pas être d'un tableau codé en dur, mais juste pour stocker une adresse. 

Maintenant, pourquoi est-ce? Maintenant, nous devons juste être à l'aise avec le fait que lorsque mon programme court, Je vais sans doute avoir à demander l'humain, combien de numéros voulez-vous stocker? Donc, l'entrée doit venir de quelque part. Mais une fois que je sais que nombre, alors je peux juste utiliser ce fonctionnement pour donner moi un morceau de la mémoire? Je peux utiliser malloc. Et je peux dire un certain nombre de octets Je veux revenir pour ces NTHS. Et tout ce que je dois stocker dans les numéros la variable ici à l'intérieur de cette structure devrait être quoi? Ce qui se passe réellement dans le numéros dans ce scénario? Oui, un pointeur vers le premier octet de ce morceau de mémoire, ou plus spécifiquement, l'adresse du premier de ces octets. N'a pas d'importance si elle est l'un octets ou un milliard d'octets, Je dois juste se soucier de la première. Parce que ce que les garanties de malloc et mes garanties de système d'exploitation, est ce que le bloc de mémoire que je obtenir, ça va être contigus. Il ne va pas y avoir des lacunes. Donc, si je l'ai demandé 50 octets ou 1000 octets, ils vont tous être dos à dos à dos. Et aussi longtemps que je me souviens comment grand, comment que je demandais, tout ce que je dois savoir est la première adresse. 

Alors maintenant, nous avons la capacité dans le code. Quoique, ça va nous prendre plus de temps pour écrire cette place, nous pourrions maintenant réaffecter que la mémoire par simplement mémoriser une adresse différente il si nous voulons une plus grande ou même un morceau plus petit de la mémoire. Donc ici pour un hors commerce. Maintenant, nous arrivons dynamisme. Nous avons toujours contiguousness Je prétendant. Parce que malloc nous donnera un morceau de la mémoire contiguë. Mais cela va être une douleur dans le cou pour nous, le programmeur, à coder réellement. Il est juste plus de travail. Nous avons besoin d'un code semblable à ce que je faisais taper sur il ya un instant. Très faisable, mais il ajoute à la complexité. Et donc le temps de développeur, programmeur Il est encore une autre ressource que nous pourrions avoir besoin de dépenser peu de temps pour obtenir de nouvelles fonctionnalités. Et puis bien sûr il ya une file d'attente. Nous ne rentrerons pas dans ce un dans beaucoup de détails. Mais il est très similaire dans l'esprit. Je pourrais mettre en œuvre une file d'attente, et ses opérations correspondantes, enqueue ou dequeue, comme ajouter ou supprimer, il est juste une façon de dire qu'il colombophile, enqueue ou dequeue, comme suit. Je peux juste me donner une struct a cette fois le tableau d'un certain nombre, a cette fois une taille, mais pourquoi dois-je maintenant de garder une trace de l'avant de la file d'attente? Je ne l'ai pas besoin de savoir l'avant de ma pile. Eh bien, si je encore pour un queue-- Disons simplement dur coder comme ayant comme cinq entiers dans ici potentiellement. Donc, cela est zéro, un, deux, trois, quatre. Cela va être appelé de nouveau les numéros. Et ce sera appelée taille. 

Pourquoi est-il ne suffit pas d'avoir juste la taille? Eh bien, nous allons pousser ces mêmes numéros sur. Donc, je pushed-- je en file d'attente, ou poussé. Maintenant, je vais ENQUEUE 50, puis 51, puis 61, et Dot Dot Dot. Voilà donc enqueue. Je en file d'attente 50, puis 51, puis 61. Et cela semble identique pour une pile à ce jour, sauf que je ne dois faire un changement. Je dois mettre à jour cette taille, donc je vais de zéro à un à deux à trois maintenant. Comment puis-je DEQUEUE? Qu'est-ce qui se passe avec dequeue? Qui doit se détacher de cette première liste si elle est la ligne sur l'Apple Store? Donc 50. Donc, il est un peu plus délicat cette fois. Considérant que la dernière fois qu'il a été super facile de simplement faire la taille moins un, Je reçois à la fin de mon tableau efficacement où les chiffres sont, il supprime 61. Mais je ne veux pas retirer 61. Je veux profiter de 50 ans, qui était là à 5h00 faire la queue pour le nouvel iPhone ou autres joyeusetés. Et donc de se débarrasser des 50, je ne peut pas simplement faire cela, non? Je peux rayer 50. Mais nous venons de dire, nous ne doivent pas être si anal à gratter ou de masquer les données. Nous ne pouvons tout simplement d'oublier d'où il est. 

Mais si je change ma taille maintenant deux, cette information est suffisante savoir ce qui se passait dans ma file d'attente? Pas vraiment. Comme ma taille est de deux, mais où la file d'attente ne commencent, surtout si je dois encore ces mêmes nombres dans la mémoire. 50, 51, 61. Donc, je dois me rappeler maintenant où le front est. Et comme je l'ai proposé jusqu'à là, nous venons d'appeler Avant Nième, dont la première valeur aurait dû être quoi? Zero, que le début de la liste. Mais maintenant, en plus de décrémentation la taille, nous avons juste incrémenter l'avant. Maintenant, voici un autre problème. Donc, une fois je continue. Supposons que ce est le nombre de comme 121, 124, puis, merde, Je suis hors de l'espace. Mais attendez une minute, je ne suis pas. Donc, à ce moment de l'histoire, Supposons que la taille est un, deux, trois, quatre, de sorte que le supposer la taille est de quatre, l'avant est un, donc 51 est à l'avant. Je veux mettre un autre numéro ici, mais, bon sang, je suis hors de l'espace. Mais je ne suis pas vraiment, non? Où pourrais-je mettre un peu valeur ajoutée, comme 171? Ouais, je pouvais juste genre de revenir sur là, non? Et puis traverser le 50, ou simplement le remplacer par 171. Et si vous vous demandez pourquoi nos numéros se sont tellement aléatoire, ceux-ci sont souvent prises ordinateur cours de sciences à Harvard après CS50. Mais ce fut une bonne optimisation, parce que maintenant je ne suis pas gaspiller de l'espace. Je dois encore rappeler l'ampleur de cette chose est totale. Il est cinq heures au total. Parce que je ne veux pas commencera à remplacer les 51. Alors maintenant, je suis encore plus d'espace, de sorte que le même problème que précédemment. Mais vous pouvez voir comment l'entreprise dans votre code, vous avez probablement avoir à l'écrire un peu plus la complexité de faire que cela se produise. Et en fait, ce que l'opérateur en C permet probablement vous faites cette magie la circularité? Ouais l'opérateur modulo, le signe pour cent. Alors, quel est plutôt cool sur une file d'attente, même si nous gardons les tableaux de dessin que ces lignes droites comme, si vous sorte de penser à cela comme courbe autour d'un cercle, puis juste intuitivement cela fonctionne sorte de mental Je pense un peu plus proprement. Vous auriez encore à mettre en œuvre ce modèle mentale dans le code. Donc, pas si difficile, en fin de compte, à mettre en oeuvre, mais nous perdons toujours le size-- plutôt la possibilité de redimensionner, à moins que nous faisons cela. 

Nous devons nous débarrasser de la matrice, nous le remplacer par un seul pointeur, puis quelque part dans mon code, je dois Un appel qui fonctionne pour créer réellement le tableau des numéros appelés? Malloc, ou quelques similaires fonction, exactement. Des questions sur piles ou des files d'attente. Ouais? Bonne question. Que voulez-vous utiliser modulo ici. Donc, en général, lors de l'utilisation mod, vous ferait avec la taille de la structure de données ensemble. Donc, quelque chose comme cinq ou capacité, si il est constant, est probablement impliqué. Mais juste faire modulo cinq est sans doute pas suffisante, parce que nous devons savoir faire nous enrouler autour ici ou ici ou ici. Donc, vous êtes probablement aussi allez vouloir impliquer la taille de la chose, ou la variable avant ainsi. Donc, il est juste ce relativement expression arithmétique simple, mais modulo serait l'ingrédient clé. 

Donc court métrage si vous voulez. Une animation que certaines les gens d'une autre université mettons ensemble que nous avons adapté à cette discussion. Elle implique l'apprentissage de la Jack faits sur les files d'attente et les statistiques. 

FILM: Il était une fois, il y avait un gars nommé Jack. Quand il est venu à se faire des amis, Jack n'a pas de talent. Donc, Jack est allé parler à la plus gars populaire qu'il savait. Il est allé à Lou et a demandé, Que dois-je faire? Lou a vu que son ami était vraiment en détresse. Eh bien, il a commencé, juste regardez comment vous êtes habillé. Ne vous avez des vêtements avec un regard différent? Oui, dit Jack. Je fais bien sûr. Venez à ma maison et Je vais leur montrer à vous. Ils partirent donc à Jack. Et Jack a montré Lou la boîte où il a gardé toutes ses chemises, et son pantalon, et ses chaussettes. Lou a dit: Je vois que vous avez tous vos vêtements dans un tas. Pourquoi ne portez-vous pas un peu d'autres de temps en temps? 

Jack dit, eh bien, quand je enlever les vêtements et les chaussettes, Je les lave et mets les dans la boîte. Vient ensuite la prochaine matin, et jusqu'à je hop. Je vais à la boîte et obtiens mes vêtements sur le haut. Lou a rapidement réalisé le problème avec Jack. Il a gardé des vêtements, des CD, et des livres de la pile. Quand il a atteint pour quelque chose à lire ou à l'usure, il choisirait le livre dessus ou sous-vêtements. Puis, quand il a été fait, il mettrait le droit de retour. Retour il irait, sur le dessus de la pile. Je sais que la solution, dit un fort triomphante. Vous devez apprendre à commencer à utiliser une file d'attente. Lou a pris les vêtements de Jack et les pendu dans le placard. Et quand il avait vidé la boîte, il a juste le lança. 

Puis il dit, maintenant Jack, à la fin de le jour, mettez vos vêtements sur la gauche quand vous mettez les éloigner. Puis demain matin lorsque vous voir le soleil, vos vêtements sur la droite, à partir de la fin de la ligne. Ne voyez-vous pas? a déclaré Lou. Ce sera tellement agréable. Vous portez une fois tout avant que vous portez quelque chose deux fois. Et avec tout dans les files d'attente dans son placard et étagère, Jack a commencé à se sentir tout à fait sûr de lui-même. Tout cela grâce à Lou et sa merveilleuse file d'attente. ENCEINTE 1: Très bien, il est adorable. Donc, ce qui a été vraiment va sur sous le capot maintenant? Que nous avons des pointeurs, que nous avons malloc, que nous avons la capacité de créer morceaux de mémoire pour nous dynamiquement. Donc, ce que nous est une image entrevu l'autre jour. Nous ne sommes pas vraiment demeurons sur elle, mais cette image a été en dessous de passe le capot pendant des semaines maintenant. Et cela représente donc, juste un rectangle que nous avons établi, la mémoire de votre ordinateur. Et peut-être votre ordinateur, ou CS50 ID, dispose d'un gigaoctet de mémoire vive ou RAM ou deux gigaoctets ou quatre. Il n'a pas vraiment d'importance. Votre système d'exploitation Windows ou Mac OS ou Linux, permet essentiellement votre programme à penser qu'il a accès pour la totalité de la mémoire de votre ordinateur, même si vous pourriez exécuter plusieurs programmes à la fois. Donc, en réalité, cela ne fonctionne pas vraiment. Mais il est une sorte d'illusion donné à tous vos programmes. Donc, si vous aviez deux concerts de RAM, ce est de savoir comment l'ordinateur peut penser. 

Maintenant, par hasard, l'un de ces choses, l'un de ces segments de mémoire, est appelée une pile. Et en effet tout moment à ce jour dans l'écriture de code que vous avez appelé un fonction, par exemple principal. Rappelons que chaque fois que je l'ai la mémoire de l'ordinateur dessinée, Je dessine toujours sorte de la moitié d'un rectangle ici et ne vous embêtez pas à parler sur ce qui est ci-dessus. Parce que quand principale est appelée, je prétends que vous obtenez ce ruban de mémoire qui descend ici. Et si principale appelée fonction comme swap, ainsi échange va ici. Et il se trouve, qui est où il est de se retrouver. Sur ce qu'on appelle une pile l'intérieur de la mémoire de votre ordinateur. Or, à la fin de la journée, cette adresse est juste. Il est comme octet nul, un octet, l'octet 2 milliards de dollars. Mais si vous pensez à ce sujet que cet objet rectangulaire, tout ce que nous faisons tous les fois que nous appelons une fonction est superposition d'une nouvelle tranche de mémoire. Nous donnons à cette fonction une tranche de sa propre mémoire pour travailler avec. 

Et maintenant rappeler que cela est important. Parce que si nous ne disposons quelque chose comme de swap et deux variables locales telles que A et B et nous changeons les valeurs d'un et deux à deux et un, le rappel que lorsque swap de revient, il est comme si cette tranche de mémoire est tout simplement disparu. En réalité, il est toujours il médicolégal. Et quelque chose est encore vraiment là. Mais conceptuellement, il est aussi si elle est complètement disparu. Et principale ne sait pas tout le travail cela a été fait dans cette fonction d'échange, sauf si elle est effectivement passé dans les arguments par pointeur ou par référence. Maintenant, la solution fondamentale à ce problème avec l'échange d' se passe des choses dans d'adresse. Mais il se trouve, aussi, ce qui est été passe au-dessus de la partie du rectangle tout ce temps est Pourtant, il ya plus de mémoire là-haut. Et quand vous dynamiquement allouer de la mémoire, si elle est à l'intérieur de GetString, qui nous avons fait pour vous dans le CS50 bibliothèque, ou si vous les gars appeler malloc et demander le système d'exploitation pour un morceau de mémoire, il ne vient pas de la pile. Il vient d'un autre lieu dans la mémoire de votre ordinateur qui est ce qu'on appelle le tas. Et ce ne est pas différent. Il en est de même de RAM. Il est la même mémoire. Il est juste de la RAM qui est en place il lieu d'ici-bas. 

Et qu'est-ce que cela signifie? Eh bien, si votre ordinateur possède une quantité limitée de mémoire et la pile grandit, donc de parler, et le tas, selon à cette flèche, est de plus en plus bas. En d'autres termes, chaque fois que vous appelez malloc, vous étant donné une tranche de mémoire à partir de ci-dessus, alors peut-être un peu plus bas, puis un peu inférieur, à chaque fois que vous appelez malloc, le tas, il est l'utilisation, est une sorte de croissant, de plus en plus de proche en proche à quoi? La pile. Donc, cela semble être une bonne idée? Je veux dire, où il est pas vraiment clair ce que vous pouvez faire si vous ne avoir une quantité limitée de mémoire. Mais cela est certainement mauvais. Ces deux flèches sont sur un Crash Course pour l'autre. 

Et il se trouve que méchant, les gens qui sont particulièrement bonnes avec la programmation, et d'essayer de pirater des ordinateurs, peut exploiter cette réalité. En fait, nous allons examiner un petit extrait. Donc, ceci est un exemple que vous pouvez lire environ plus en détail sur Wikipedia. Nous vous indiquerons au article si curieux. Mais il ya une attaque générale connu comme dépassement de tampon qui existe aussi longtemps que les humains ont eu la possibilité de manipuler la mémoire de l'ordinateur, en particulier en C. Donc, ce programme est très arbitraire, mais nous allons le lire de bas en haut. Principale dans argC omble étoiles argv. Donc, il est un programme qui prend arguments de ligne de commande. Et tout ne principale est apparemment appel une fonction, appeler F pour plus de simplicité. Et il passe en quoi? Argv d'un. Donc, il passe dans ce que F le mot est que l'utilisateur a tapé à l'invite après la le nom de programme du tout. Donc, un peu comme César ou Vigenère, qui vous pourriez faire rappeler avec argv. 

Alors, quelle est F? F prend dans une chaîne que son seul argument, Alias ​​une star de char, même chose, comme une chaîne. Et il a appelé arbitrairement bar dans cet exemple. Et puis char c 12, seulement en termes simples, ce qui est char c support 12 faire pour nous? Qu'est-ce qu'il fait? Allocation de mémoire, en particulier 12 octets pour 12 caractères. Exactement. Et puis la dernière ligne, remuer et copie, vous avez sans doute pas vu. Ceci est une copie de chaîne fonction dont le but dans la vie est de copier son deuxième argument dans son premier argument, mais seulement jusqu'à un certain nombre d'octets. Ainsi, le troisième argument dit, combien d'octets vous devez copier? La longueur de la barre, quelle que soit l'utilisateur a tapé dans. Et le contenu de bar, cette chaîne, sont copié dans la mémoire pointé au C. 

Donc, cela semble un peu stupide, et il est. Il est un exemple artificiel, mais il est représentatif d'une classe de vecteurs d'attaque, une façon d'attaquer un programme. Tout est beau et bon si l'utilisateur types dans un mot qui est 11 caractères ou moins, ainsi que la barre oblique inverse zéro. Que faire si les types d'utilisateurs dans plus de 11 ou 12 ou 20 ou 50 caractères? Quel est ce programme va faire? Faute potentiellement seg. Ça va de copier aveuglément tout en bar jusqu'à à sa longueur, qui est littéralement tout en bar, dans l'adresse pointée à C. Mais C a seulement préventivement donné que 12 octets. Mais il n'y a pas de vérification supplémentaire. Il n'y a pas si les conditions. Il n'y a pas ici de vérifier l'erreur. 

Et donc ce que ce programme est va faire est aveuglément copier une chose à l'autre. Et si nous tirons cette comme une image, voici juste un petit morceau de l'espace mémoire. Donc remarquons au fond, nous avoir la barre variable locale. Donc, ce pointeur qui va store-- plutôt cet argument locale qui est allez stocker la barre de chaîne. Et puis notez simplement au-dessus d'une pile, parce que chaque fois que vous demandez pour la mémoire sur la pile, il va un peu au-dessus imagé, Notez que nous avons 12 octets il. L'un en haut à gauche est C support de zéro et celui en bas à droite est C support 11. Voilà à quel point les ordinateurs va jeter dehors. Il suffit donc intuitivement, si la barre a plus de 12 caractères au total, y compris la barre oblique inverse zéro, où est le 12 ou le support de C 12 va aller? Ou plutôt où est le 12e caractère ou le caractère 13, le caractère centième aller pour finir dans l'image? Dessus ou en dessous? 

Droit, parce que même si la pile se pousse vers le haut, une fois que vous avez mis des choses dans ce, pour des raisons de conception, met la mémoire de haut en bas. Donc, si vous avez plus de 12 octets, vous allez commencer à remplacer bar. Voilà un bug, mais il est pas vraiment un gros problème. Mais il est un gros problème, car il ya plus de choses se passe dans la mémoire. Alors, voici comment nous pourrions mettre bonjour, pour être clair. Si je tapé dans bonjour à l'invite. Barre oblique inverse zéro H-E-L-L-O, finit dans les ces 12 octets, et nous sommes très sûr. Tout est bien. Mais si je tape quelque chose plus, il est potentiellement va glisser dans l'espace bar. Mais pire encore, il se sur tout ce temps, même si nous ne l'avons jamais parlé elle, la pile est utilisé pour d'autres choses. Il n'y a pas que les variables locales. 

C est un langage de très faible niveau. Et ce genre de secret utilise la pile aussi se souvenir quand un fonction est appelée, ce qui l'adresse est de la fonction précédente, de sorte qu'il peut revenir en arrière à cette fonction. Ainsi, lorsque les appels principaux échanger, entre les choses ont poussé sur la pile ne sont pas simplement les swaps variables locales, ou de ses arguments, aussi secrètement poussé sur la pile comme représenté par la tranche rouge ici, est l'adresse du principal physiquement dans la mémoire de votre ordinateur, de sorte que lorsque swap est fait, l'ordinateur sait que je dois retourner au principal et terminer l'exécution de la fonction principale. Donc, cela est dangereux maintenant, parce que si les types d'utilisateurs dans plus de bien bonjour, de telle sorte que l'entrée de l'utilisateur aplatit ou remplace cette section rouge, logiquement, si de l'ordinateur juste aller à assumer aveuglément que les octets dans cette tranche rouge sont l'adresse à laquelle elle doit retourner, si l'adversaire est assez intelligent ou la chance de mettre une séquence d'octets il qui ressemble à une adresse, mais il est l'adresse du Code qu'il ou elle veut l'ordinateur à exécuter au lieu de principale? 

En d'autres termes, si ce que le utilisateur tape à l'invite, est pas seulement quelque chose comme inoffensive bonjour, mais il est en fait le code qui est équivalent supprimer tous les fichiers de cet utilisateur? Ou envoyer leur mot de passe pour moi? Ou commencer à enregistrer leur frappes, non? Il ya une façon, disons stipulent aujourd'hui, qu'ils pouvaient saisir non seulement bonjour monde ou de leur nom, qu'ils pouvaient essentiellement passer dans le code, et de zéros celles que l'ordinateur erreurs à la fois le code et une adresse. Donc, bien que quelque peu abstraite, si le types d'utilisateurs en code assez contradictoire que nous allons généralisons ici A. A est l'attaque ou adversaires. Il suffit donc de mauvaises choses. Nous ne nous soucions pas de la les numéros ou les zéros ou aujourd'hui, de telle sorte que vous vous retrouvez écraser cette section rouge, remarquerez que séquence d'octets. O 835 C zéro huit zéro. Et maintenant, comme l'article de Wikipedia ici a proposé, si vous commencez maintenant réalité étiqueter les octets dans votre ordinateur de la mémoire, ce que l'article de Wikipedia est proposante est que, si l'adresse de l'octet haut à gauche est 80 C 0 3508. 

En d'autres termes, si le méchant est assez intelligent avec son code de mettre réellement un certain nombre ici que correspond à l'adresse du code il ou elle injecté dans l'ordinateur, vous peut tromper l'ordinateur en faire quelque chose. Suppression de fichiers, e-mailing choses, renifler votre trafic, littéralement tout ce que pourrait être injecté dans l'ordinateur. Et si un débordement de tampon attaque à sa base est juste un stupide, stupide impérieuse d'un tableau ne disposent pas de ses frontières vérifiés. Et voici ce que est super dangereux et en même temps super puissant C est dans ce que nous avons en effet l'accès à n'importe où dans la mémoire. Il est à nous, les programmeurs, qui écrivent le code original pour vérifier la longueur de reprise de tout tableaux que nous manipulation. Donc, pour être clair, quelle est la solution? Si nous revenir à cette code, je ne devrais pas simplement changer la longueur de la barre, ce qui dois-je vérifierai? Que dois-je faire pour empêcher cette attaque entièrement? Je ne veux pas juste dire aveuglément que vous devez copier autant d'octets comme l'est la longueur de la barre. Je tiens à dire, comme copier le nombre d'octets que sont en bar jusqu'à la alloué la mémoire, ou 12 au maximum. Donc je besoin d'une sorte de condition if qui ne vérifie la longueur de la barre, mais si elle dépasse 12, on code juste dur 12 comme la distance maximale possible. Sinon le tampon dite attaque de dépassement peut arriver. Au bas de ces lames, Si vous êtes curieux de lire la suite est l'article original réel Si vous souhaitez jeter un oeil. 

Mais maintenant, parmi les prix payés ici était inefficacités. Ce qui fut une rapide faible niveau look à quel des problèmes peuvent survenir maintenant que nous avoir accès à la mémoire de l'ordinateur. Mais un autre problème que nous déjà trébuché lundi était juste l'inefficacité d'une liste chaînée. Nous sommes de retour à temps linéaire. Nous ne sommes plus un tableau contigu. Nous ne disposons pas accès aléatoire. Nous ne pouvons pas utiliser la notation crochet. Nous avons littéralement à utiliser une boucle while comme celui que je écrit il ya un moment. Mais lundi, nous avons affirmé que nous pouvons grimper à nouveau dans le domaine de l'efficacité la réalisation de quelque chose qui est logarithmique peut-être, ou mieux encore, peut-être même quelque chose qui est dite constante de temps. Alors, comment pouvons-nous le faire en utilisant ces nouveaux outils, ces adresses, ces pointeurs, et le filetage choses de notre propre? Eh bien, supposons que ici, ce sont un tas des nombres que nous voulons stocker dans un structure de données et de recherche efficace. Nous ne pouvons absolument revenir en arrière pour la semaine deux, jeter ceux-ci dans un tableau, et les rechercher en utilisant la recherche binaire. Diviser et conquérir. Et en fait, vous avez écrit recherche binaire dans PSET3, où vous en œuvre le programme de recherche. Mais vous savez quoi. Il ya une sorte de plus façon intelligente de le faire. Il est un peu plus sophistiqué et ce peut-être nous permet de voir pourquoi binaire la recherche est tellement plus rapide. Premièrement, nous allons introduire la notion d'un arbre. Qui, même si dans arbres de type de réalité grandir comme ça, dans le monde de l'informatique la science, ils poussent à la baisse type de comme un arbre de la famille, où vous avez vos grands-parents ou grands-parents ou quoi au sommet, le patriarche et la matriarche de la famille, un seul dite racine, noeud, ci-dessous Quelles sont ses enfants, ci-dessous, qui sont ses enfants, ou ses descendants plus généralement. Et quiconque pendait le fond de la famille arbre, en plus d'être le plus jeune dans la famille, peut aussi être juste générique appelle les feuilles de l'arbre. 

Donc, ceci est juste un tas des mots et des définitions pour quelque chose appelé un arbre dans l'ordinateur la science, un peu comme un arbre généalogique. Mais il ya incarnations fantaisistes des arbres, dont l'un est appelé un arbre de recherche binaire. Et vous pouvez sorte de taquinerie Outre ce que cette chose fait. Eh bien, il est binaire dans quel sens? D'où vient le binaire viennent ici? Pardon? Il est pas tellement un ou. Il est plus que chacun des noeuds n'a pas plus de deux enfants, que nous voyons ici. En général, un tree-- et vos parents et grands parents peut avoir autant d'enfants ou petits-enfants qu'ils veulent réellement, et ainsi par exemple, il nous en avons trois enfants hors de ce nœud de la main droite, mais dans un arbre binaire, un noeud a zéro, un ou deux enfants au maximum. Et voilà une belle propriété, parce que si elle est couronnée par deux, nous allons être en mesure de obtenir un peu logarithme en base deux l'action se passe ici en fin de compte. Donc, nous avons quelque chose logarithmique. Mais plus sur cela dans un instant. Des moyens pour rechercher arbre que les chiffres sont agencé de telle sorte que l'enfant de gauche La valeur est supérieure à la racine. Et son enfant droite est plus grande que la racine. En d'autres termes, si vous prenez un des nœuds, les cercles dans cette image, et regarde à sa gauche enfant et son droit de l'enfant, le premier devrait être inférieure à, le second doit être supérieure. Donc, test de cohérence 55. Il a laissé l'enfant est de 33. Il est moins. 55, son droit de l'enfant est 77. Il est supérieur. Et voilà une définition récursive. Nous pourrions vérifier chaque un de ceux nœuds et le même schéma tiendrait. 

Donc, ce qui est agréable dans un arbre binaire de recherche, est celui-là, nous pouvons mettre en œuvre avec une struct, juste comme ça. Et même si nous jetons beaucoup de structures à votre, ils sont peu intuitive maintenant je l'espère. La syntaxe est encore obscur pour sûr, mais le contenu d'un noeud dans cette context-- et nous gardons en utilisant le mot node, que ce soit un rectangle sur l'écran ou d'un cercle, il est juste un conteneur générique, dans ce cas, d'un arbre, tel que celui nous avons vu, nous avons besoin d'un entier dans chacun des noeuds et puis je besoin de deux pointeurs pointage à l'enfant gauche et la droite enfant, respectivement. Voilà donc comment nous pourrions mettre en œuvre que dans une structure. Et comment pourrais-je mettre en œuvre dans le code? Eh bien, nous allons jeter un rapide regarder ce petit exemple. Il est non fonctionnel, mais je l'ai copié et collé cette structure. Et si ma fonction pour un binaire arbre de recherche est appelé recherche, et cela prend deux arguments, un nombre entier N et d'un pointeur à un noeud, de sorte qu'un pointeur vers l'arborescence ou un pointeur vers la racine d'un arbre, comment puis-je aller sur la recherche de N? Eh bien, d'abord, parce que je suis traitement des pointeurs, Je vais faire une vérification de cohérence. Si égaux d'arbres égal nulle, est N dans cet arbre ou non dans cet arbre? Il ne peut pas être, non? Si je suis passé null, il n'y a rien. Je pourrais tout aussi bien aveuglément dire return false. Si vous me donnez rien, je ne peux pas sûrement trouver un certain nombre N. Alors quoi d'autre pourrais-je vérifie maintenant? Je vais bien dire d'autre si N est inférieur à ce qui est au niveau du noeud de l'arbre que je ai été remis valeur N. En d'autres termes, si le nombre je suis la recherche de N, est inférieur au nœud que je suis à la recherche. Et le nœud je cherche est appelé à arbre, et de rappeler à partir de l'exemple précédent pour obtenir la valeur dans un pointeur, Je l'utilise la notation de flèche. Donc, si N est inférieur Arbre Sous- N, je veux aller conceptuellement gauche. Comment puis-je exprimer recherchez quitté? Pour être clair, si cela est l'image en question, et je l'ai été adoptée que le plus haut flèche pointant vers le bas que ça. Voilà mon pointeur de l'arbre. Je fais remarquer à la racine de l'arbre. Et je suis à la recherche par exemple, pour le nombre 44, arbitrairement. 44 est inférieur ou évidemment supérieure à 55? Il est donc moins. Et donc cela si l'état applique. Donc, sur le plan conceptuel, ce que je veux rechercher prochaine si je suis à la recherche pour les 44? Ouais? 

Exactement, je veux chercher l'enfant à gauche, ou le sous-arbre gauche de cette image. Et en fait, permettez-moi de grâce la photo ici pour un instant, depuis Je ne peux pas rayer cela. Si je commence ici à 55 ans, et Je sais que la valeur 44 Je cherche est de la gauche, il est un peu comme de déchirer le livre de téléphone dans la moitié ou déchirement de l'arbre en deux. Je ne ai plus à se soucier toute cette moitié de l'arbre. Et pourtant, curieusement en termes de la structure, cette chose ici que commence par 33, qui se est un arbre de recherche binaire. Je l'ai dit le mot récursive avant parce en effet ceci est une structure de données qui par définition est récursive. Vous pourriez avoir un arbre qui est présent grand, mais chacun de ses enfants représente un arbre un peu plus petite. Au lieu d'être grand-père ou grand-mère, maintenant il est juste maman ou-- Je ne peux pas say-- pas maman ou papa, ce serait bizarre. Au contraire, les deux enfants là-bas serait comme frère et sœur. Une nouvelle génération de l'arbre généalogique. Mais structurellement, il est la même idée. Et il se trouve que je dois une fonction avec laquelle je peux chercher une recherche binaire arbre. Il est appelé recherche. Je cherche N dans l'arbre flèche gauche sinon si N est supérieur à la valeur que je suis actuellement à. 55 dans l'histoire il ya un instant. Je dois une fonction appelée la recherche que je peux juste N passer cela et rechercher de manière récursive le sous-arbre et juste retour quelle que soit cette réponse. Sinon je dois certains cas, de base finale ici. 

Quel est le dernier cas? Arbre est soit null. La valeur soit je cherche est inférieur à ce qu'il ou supérieure à celle ou égal à elle. Et je pourrais dire égale égal, mais logiquement, il est équivalent à simplement dire d'autre ici. Tant il est vrai que je trouve quelque chose. Il en est ainsi, espérons une exemple encore plus convaincante que la fonction de sigma stupide nous avons fait quelques conférences dos, où il était tout aussi facile à utiliser une boucle compter tous les chiffres de un N. Ici, avec une structure de données qui est lui-même de façon récursive définis et de manière récursive attirés, maintenant nous avoir la capacité de nous exprimer dans le code qui lui-même est récursive. Donc, cela est exactement le même code ici. 

Alors que d'autres problèmes que nous pouvons résoudre? Donc, un pas rapide loin de arbres pour un moment. Ici est, disons, le drapeau allemand. Et il ya clairement un motif à ce drapeau. Et il ya beaucoup de drapeaux dans le monde qui sont aussi simple que cela en termes de leurs couleurs et de motifs. Mais supposons que cela est stocké en tant que .GIF, Ou d'un JPEG ou bitmap, ou une table de ping, quel format de fichier graphique avec lequel vous êtes familier, dont certains que nous sommes jouer avec dans PSET4. Cela ne semble pas utile de stocker pixel noir, pixel noir, pixel noir, dot, point, point, tout un tas de pixels noirs pour la première ligne de balayage, ou une ligne, puis tout un tas de de même, puis un tas de même, puis une tas ensemble de pixels rouges, pixels rouges et les pixels rouges, puis tout un tas de pixels jaunes, jaune, non? 

Il ya une telle inefficacité ici. Comment feriez-vous intuitivement comprimer le drapeau allemand si la mise en œuvre dans un fichier? Comme quoi informations pouvons-nous pas peine stocker sur le disque afin pour diminuer la taille de notre fichier à partir comme un mégaoctet à un kilo-octet, quelque chose plus petit? Dans laquelle se trouve la redondance ici pour être clair? Que pourriez-vous faire? Ouais? Exactement. Pourquoi ne pas plutôt que de se rappeler la couleur de chaque pixel sacrément tout comme vous faites dans PSET4 avec le format de fichier bitmap, pourquoi ne vous représentez pas seulement le colonne de gauche de pixels, par exemple un tas de pixels noirs, un tas de rouge, et un tas de jaune, et puis juste en quelque sorte l'encoder idée de répéter cette 100 fois ou répéter cette 1000 fois? Où est 100 ou 1000 juste un nombre entier, de sorte que vous peut sortir avec un seul numéro au lieu de centaines ou de milliers de pixels supplémentaires. Et en effet, ce est comment nous pourrait comprimer le drapeau allemand. Et Maintenant, qu'en est-il le drapeau français? Et un peu une sorte de exercice mental, quel drapeau peut être comprimé plus sur le disque? Le drapeau allemand ou les Français drapeau, si nous prenons cette approche? Le drapeau allemand, parce qu'il ya plus de redondance horizontale. Et par la conception, de nombreux fichiers graphiques formats ne fonctionnent en effet comme les lignes de balayage horizontalement. Ils pourraient travailler verticalement, juste l'humanité il ya des années décidé que nous allons pensent généralement des choses rangée par ligne à la place de la colonne par colonne. Donc, en effet, si vous étiez à regarder le fichier taille d'un drapeau allemand et un français drapeau, tant que la résolution est de même, la même largeur et la hauteur, à celui-ci ici va être plus grand, parce que vous avoir à vous répéter trois fois. Vous devez spécifier bleu, répétez vous, blanc, répétez-vous, rouge, vous répétez. Vous ne pouvez pas aller tout le chemin vers la droite. Et en passant, à faire désactiver la compression est partout, si ceux-ci sont quatre trames d'une video-- vous pourrait rappeler qu'un film ou vidéo est en général comme 29 ou 30 images par seconde. Il est comme un petit flip book où vous juste voir l'image, l'image, l'image, l'image, l'image juste super rapide de sorte qu'il ressemble les acteurs sur l'écran sont en mouvement. Voici un bourdon sur dessus d'un bouquet de fleurs. Et si cela peut être une sorte de difficile de voir au premier coup d'œil, la seule chose se déplaçant dans ce film est l'abeille. 

Quel est muet sur le stockage vidéo non compressée? Il est une sorte de déchets à stocker de la vidéo que quatre images presque identiques que ne diffèrent que dans la mesure où lorsque l'abeille est. Vous pouvez jeter plus de cette information et rappelez-vous que, par exemple, la première image et la dernière image, cadres clés Si vous avez jamais entendu le mot, et juste stocker dans le milieu où l'abeille est. Et vous ne devez pas stocker la totalité de la rose, et le bleu, et de la valeurs vertes ainsi. Donc cela pour dire seulement que la compression est partout. Il est une technique que nous utilisons souvent ou tenir pour acquis ces jours. 

Mais comment ne vous compressez texte? Comment allez-vous comprimer texte? Eh bien, chacun des personnages dans ASCII est un octet, ou huit bits. Et cela est un peu idiot, non? Parce que vous avez probablement de type A et E et I et O et U a beaucoup le plus souvent comme W ou Q ou Z, en fonction de la langue dans laquelle vous écrivez certainement. Et alors pourquoi utilisons-nous huit bits pour chaque lettre, y compris les moins lettres populaires, non? Pourquoi ne pas utiliser moins de bits pour les lettres super populaire, comme E, les choses que vous devinez d'abord dans Roue de la Fortune, et utiliser plus de bits pour les lettres moins populaires? Pourquoi? Parce que nous allons juste utiliser moins fréquemment. 

Eh bien, il se trouve qu'il ya eu les tentatives faites pour ce faire été. Et si vous vous souvenez du grade l'école ou au lycée, le code Morse. Morse a points et tirets qui peuvent être transmis le long d'un fil comme des sons ou des signaux de quelque sorte. Mais le code Morse est un super propre. Il est une sorte de système binaire que vous avez des points ou des tirets. Mais si vous voyez, par exemple, deux points. Ou si vous pensez à l'opérateur qui va comme bip, bip, bip, bip, frapper un peu de déclenchement qui transmet un signal, si vous, le destinataire, reçoit deux points, quel message avez-vous reçu? Complètement arbitraire. 

JE? JE? Ou ce about-- ou moi? Peut-être qu'il était juste deux droit de l'E? Donc, il ya ce problème de décodabilité avec Morse code, de sorte que, sauf si le personne vous envoyer le message les pauses dans effectivement de sorte que vous pouvez trier des voir ou entendre les écarts entre les lettres, il ne suffit pas simplement pour envoyer un flux de zéros et de uns, ou points et de traits, parce qu'il ya ambiguïté. E est un point unique, donc si vous voir deux points ou entendre deux points, il est peut être deux de E ou peut-être il est l'un I. Nous avons donc besoin d'un système qui est un peu plus intelligent que cela. Ainsi, un homme du nom de Huffman ans Il ya venu avec exactement cela. Donc, nous allons juste de prendre un coup d'oeil rapide comment les arbres sont pertinentes à cet égard. Supposons que ce soit un peu stupide message que vous souhaitez envoyer, composé de seulement A, B, C et D de s E'S, mais il ya beaucoup de redondance ici. Il est pas censé être l'anglais. Il est pas crypté. Il est juste un message stupide avec beaucoup de répétition. Donc, si vous comptez réellement toutes les A'S, B, C de, D's, et E de, voici la fréquence. 20% des lettres sont A'S, 45% des lettres sont de E, et trois autres fréquences. Nous avons compté là-haut la main et juste fait le calcul. 

Donc, il se trouve que Huffman, il ya quelque temps, réalisé que, vous savez ce qui, si je commence bâtiment un arbre, ou une forêt d'arbres, si vous voulez, comme suit, je peux faire ce qui suit. Je vais donner un noeud à chaque des lettres que je me soucie et je vais stocker à l'intérieur de ce noeud les fréquences en flottant valeur, ou vous pouvez utiliser un N, aussi, mais nous allons simplement utiliser un flotteur ici. Et l'algorithme qui il a proposé est que vous prendre cette forêt de noeud unique arbres, arbres si super court, et vous commencez à les relier à de nouveaux groupes, de nouveaux parents, si vous voulez. Et vous faites cela en choisissant la deux plus petites fréquences à la fois. Je pris donc 10% et 10%. Je crée un nouveau nœud. Et je l'appelle le nouveau nœud de 20%. 

Quels sont les deux noeuds je combine ensuite? Il est un peu ambiguë. Donc, il ya certains cas de coin à envisager, mais de garder les choses assez, Je vais choisir 20% - Je l'ignore maintenant les enfants. Je vais choisir 20% et 15% et tracez deux nouveaux bords. Et maintenant, qui deux noeuds puis-je combiner logiquement? Ignorer tous les enfants, tous les petits-enfants, il suffit de regarder les racines maintenant. Quels sont les deux nœuds puis-je attacher ensemble? Point de deux et 0,35. Alors permettez-moi d'attirer deux nouveaux bords. Et puis je ne ai qu'une gauche. Alors, voici un arbre. Et il a été tiré délibérément à regarder sorte de joli, de remarquer que les bords ont également été marqué zéro et un. Donc tous les bords gauche sont à zéro arbitrairement, mais constamment. Tous les bons bords sont chers. 

Et donc ce que Hoffman proposé est, si vous voulez représenter un B, plutôt que de représenter le nombre 66 comme ASCII qui est entières huit bits, vous savez quoi, magasin juste le modèle zéro, zéro, zéro, zéro, parce que le chemin est de mon arbre, l'arbre de M. Huffman, de la feuille à partir de la racine. Si vous souhaitez enregistrer un E, en revanche, ne sont pas envoyer huit bits qui représentent un E. Au lieu de cela, envoyez ce motif de bits? One. Et ce qui est bon à ce sujet est que E est la lettre la plus populaire, et vous utilisez le le plus court code pour elle. La prochaine plus populaire lettre ressemble à elle était A. Et si le nombre de bits at-il proposer en utilisant pour cela? Zéro, un. 

Et parce qu'il est mis en œuvre comme cet arbre, pour l'instant laissez-moi stipule par il ya aucune ambiguïté quant à Morse code, parce que tous les lettres que vous vous souciez sont à la fin de ces bords. Voilà donc un seul application d'un arbre. Cette est-- et je vais vague ma main à ce comment vous pourrait mettre en œuvre ce que une structure C. Nous avons juste besoin de combiner un symbole, comme un char, et la fréquence à gauche et à droite. Mais regardons deux derniers exemples que vous aurez être assez familier avec après Quiz zéro problème réglé cinq. 

Donc, il ya la structure de données connu comme une table de hachage. Et une table de hachage est une sorte de refroidir en ce qu'il comporte des seaux. Et suppose qu'il ya quatre seaux ici, seulement quatre espaces. Voici un jeu de cartes, et est ici club, pelle, club, diamants, club, diamants, clubs, diamants, clubs-- ce est donc le hasard. Coeurs, hearts-- donc je suis bucketizing toutes les entrées ici. Et un besoins de table de hachage de regarder votre entrée, et puis le mettre dans un certain placer sur la base de ce que vous voyez. Il est un algorithme. Et je me sers d'un super- algorithme visuel simple. La partie la plus difficile de ce qui était rappelant ce que les photos étaient. Et puis il ya quatre choses totaux. 

Maintenant, les piles ont été de plus en plus, ce qui est une conception délibérée chose ici. Mais quoi d'autre pourrais-je faire? Donc en fait nous avons ici un tas de vieux livres d'examen de l'école. Supposons qu'un groupe de noms étudiants sont ici. Voici une grande table de hachage. Au lieu de quatre seaux, Je suis, disons 26. Et nous ne voulons pas aller emprunter 26 choses de [l'extérieur? Annenberg?], De sorte voici cinq qui représentent A à Z. Et si je voir un étudiant dont le nom commence par A, Je vais à son questionnaire mis là. Si quelqu'un commence par C, là-bas, A- effectivement, ne voulait pas le faire. B va ici. Donc, je dois A et B et C. Et voici maintenant un autre étudiant. Mais si cette table de hachage est mis en oeuvre avec un réseau, Je suis un peu foiré à ce point, non? Je sorte de besoin de le mettre quelque part. 

Donc, d'une manière que je peux résoudre ce problème est, tout à droite, un est occupé, B est occupé, C est occupé. Je vais le mettre dans D. Ainsi, à Premièrement, je dois accès instantané aléatoire à chacun des godets pour les étudiants. Mais maintenant, il est une sorte de dévolue en quelque chose linéaire, parce que si je veux chercher quelqu'un dont le nom commence par A, je vérifie ici. Mais si tel est le pas A étudiant, je suis à la recherche, Je dois sorte de commencer à vérifier les seaux, parce que ce que je faisais était en quelque sorte linéairement sonder la structure de données. Une façon stupide de dire il suffit de regarder pour la première ouverture disponibles, et de mettre comme un plan B, pour ainsi dire, ou le plan D dans ce cas, la valeur à cet endroit à la place. Ceci est juste de sorte que si vous avez obtenu 26 endroits et pas d'étudiants avec le nom Q ou Z, ou quelque chose comme que, au moins vous utilisez l'espace. 

Mais nous avons déjà vu plus solutions intelligentes ici, non? Que feriez-vous à la place si vous avez une collision? Si deux personnes ont Un nom, ce serait ont été plus intelligents ou plus solution intuitive que juste Mettre un où D est censé être? Pourquoi dois-je pas simplement aller dehors [? Annenberg?], comme malloc, un autre nœud, le mettre ici, et ensuite mettre qu'un étudiant ici. Alors que je dois essentiellement une sorte d'un tableau, ou peut-être avec plus d'élégance que nous sommes commençons à voir une liste chaînée. 

Et donc une table de hachage est une structure qui pourrait ressembler à cela, mais plus intelligemment, vous quelque chose appelé chaînage séparé, dans lequel une table de hachage est tout simplement un tableau, chacun des dont les éléments ne sont pas un certain nombre, est lui-même une liste chaînée. Alors que vous obtenez un accès ultra-rapide décider où votre valeur à hacher. Tout comme avec l'exemple des cartes, Je pris des décisions super rapide. Coeurs va ici, diamants va ici. Même ici, A va ici, D va ici, B va ici. Donc super rapides look-ups, et si vous arrive de courir dans un cas collisions où vous avez, deux les personnes ayant le même nom, eh bien vous venez de commencer les reliant. Et peut-être vous les gardez triées par ordre alphabétique, peut-être vous ne le faites pas. Mais au moins maintenant nous avons le dynamisme. Donc, d'une part, nous avons super rapide constante de temps, et le type de temps linéaire impliqués si ces listes chaînées commencer à obtenir un peu long. 

Donc, ce genre de stupide, Il ya plaisanterie ans geek. Au CS50 bidouille-o-thon, lorsque les élèves check-in, certains TF ou CA chaque année pense qu'il est drôle à mettre en place un signe de ce genre, où il vient signifie que si votre nom commence par un A, aller dans cette voie. Si votre nom commence avec un B, aller this-- OK, il est drôle peut-être plus tard dans le semestre. Mais il ya un autre façon de le faire, aussi. Revenez à cela. 

Donc, il ya cette structure. Et ceci est notre dernière la structure pour aujourd'hui, qui est quelque chose appelé un trie. T-R-I-E, qui pour une raison est courte pour la récupération, mais il est appelé Trie. Donc un trie est une autre intéressante amalgame de beaucoup de ces idées. Il est un arbre, que nous avons vu auparavant. Il est pas un arbre de recherche binaire. Il est un arbre avec un certain nombre d'enfants, mais chacun des enfants dans un trie est un tableau. Un tableau de taille, disons, 26 ou peut-être 27 si vous voulez soutenir noms trait d'union ou apostrophes dans les noms des personnes. 

Et si cela est une structure de données. Et si vous regardez de haut en bas, comme si vous regarder le nœud supérieur là, M, est pointant à la chose la plus à gauche il, qui est alors A, X, W, E, L, L. Ceci est seulement une structure de données qui arbitrairement est mémoriser les noms des personnes. Et Maxwell est stocké en suivant simplement un chemin de tableau en tableau en tableau. Mais ce qui est étonnant sur un trie est que, si une liste chaînée et même un tableau, le meilleur que nous ayons eu est temps linéaire ou logarithmique à la recherche du temps quelqu'un. Dans cette structure de données d'une trie, si ma structure de données a un nom dans ce et je suis à la recherche pour Maxwell, je suis va le trouver assez rapidement. Je viens de regarder pour M-A-X-W-E-L-L. Si cette structure de données, en revanche, si N est un million, si il ya un millions de noms dans cette structure de données, Maxwell va encore être détectable après seulement M-A-X-W-E-L-L étapes. Et étapes David-- D-A-V-I-D. En d'autres termes, en construisant une structure de données qui est obtenu l'ensemble de ces matrices, qui se soutenir l'accès aléatoire, Je peux commencer à chercher jusqu'à autrui nom en utilisant une quantité de temps qui est proportionnelle à pas le nombre des choses dans la structure de données, comme un million de noms existants. La quantité de temps qu'il me faut pour trouver M-A-X-W-E-L-L dans cette structure de données est pas proportionnelle à la taille de la structure de données, mais à la longueur du nom. Et réaliste le noms Nous sommes regardant ne vont jamais être fou longtemps. Peut-être quelqu'un a un caractère 10 nom, nom de 20 caractères. Il est certainement finie, non? Il est un être humain sur Terre qui a le nom le plus long possible, mais ce nom est une constante longueur de valeur, non? Il ne varie pas dans tous les sens. Donc, dans ce sens, nous avons atteint une structure de données qui est constante de temps look-up. Il prend un certain nombre de mesures en fonction de la longueur de l'entrée, mais pas le nombre de nom dans la structure de données. Donc, si nous doublons le nombre de noms l'année prochaine d'un milliard à deux milliards, constatation Maxwell va prendre exactement le même nombre de sept étapes pour le retrouver. Et si nous semblons avoir atteint notre saint Graal de la durée de fonctionnement. 

Alors quelques annonces rapides. Quiz zéro est à venir. Plus de détails sur ce que sur le site Web de cours au cours des prochains jours. Lundis lecture-- il est un jour férié ici à Harvard lundi. Il est pas à New Haven, nous sommes donc en prenant la classe à New Haven pour conférence le lundi. Tout sera filmé et retransmis en direct comme d'habitude, mais finissons aujourd'hui avec un deuxième clip 30 appelés "pensées profondes" par Daven Farnham, qui a été inspiré l'an dernier le samedi "Pensées profondes" de Night Live par Jack Handy, qui devrait maintenant donner un sens. 

FILM: Et maintenant, "Deep Pensées "de Daven Farnham. Table de hachage. 

ENCEINTE 1: Très bien, qui est pour l'instant. Nous vous verrons la semaine prochaine. 

DOUG: Pour le voir en action. Donc, nous allons jeter un oeil à ce droit maintenant. Donc, ici, nous avons un tableau non triés. 

IAN: Doug, pouvez-vous aller de l'avant et de redémarrage cela pour seulement une seconde, s'il vous plaît. Tout droit, caméras tournent, donc l'action chaque fois que vous êtes prêt, Doug, OK? DOUG: Très bien, alors ce que nous avons ici est un tableau non triés. Et je l'ai colorié tous les éléments rouge pour indiquer qu'il est, en fait, non triés. Donc, rappelons que la première chose que nous faisons est que nous trions la moitié gauche du tableau. Ensuite, nous trions le droit moitié de la matrice. Et ya-da, da-Ya, ya-da, nous fusionnons ensemble. Et nous avons un tableau complètement triée. Voilà donc comment fonctionne le tri par fusion. 

IAN: Whoa, whoa, whoa, couper, couper, couper, couper. Doug, vous ne pouvez pas simplement Ya-da, ya-da, Ya-da, votre chemin à travers le tri par fusion. 

DOUG: Je viens de faire. C'est bien. Nous sommes bon pour aller. Gardons laminage. De toute façon, 

IAN: Vous devez expliquer plus pleinement que cela. Voilà tout simplement pas assez. DOUG: Ian, nous ne faisons pas besoin de revenir à un. C'est bien. Donc de toute façon, si nous continuons avec merge-- Ian, nous sommes dans le milieu du tournage. 

IAN: Je sais. Et nous ne pouvons pas simplement Ya-da, ya-da, Ya-da, à travers l'ensemble du processus. Vous devez expliquer comment le deux côtés se fusionnés. 

DOUG: Mais nous avons déjà expliqué comment les deux sides-- 

IAN: Vous venez montré elle toute une gamme de fusion. DOUG: ils savent le processus. Ils vont bien. Nous avons dépassé dix fois. 

IAN: Vous venez sauté droit sur elle. Nous allons revenir à un, vous tu ne peux pas Ya-da, da ya-dessus. Tout droit, le dos à un. 

DOUG: Je dois retourner à travers toutes les diapositives? Mon Dieu. Il est comme la sixième fois, Ian. C'est bien. 

IAN: Très bien. Tu es prêt? Génial. Action.