[Jouer de la musique] 

[LECTURE VIDÉO] 

-Il ment. 

-Sur quoi? 

-Je ne sais pas. 

-Alors Que savons-nous? 

-Que À 9:15, Ray Santoya était au guichet automatique. -Ouais. Donc la question est, ce qui faisait-il à 09h16? 

-Shooting Millimètre 9 à quelque chose. Peut-être qu'il a vu le tireur d'élite. 

-Ou Travaillait avec lui. 

-Attendez. Retour d'un. 

-Que vois-tu? 

-Amener Son visage jusqu'à plein écran. 

-Son Verres. 

-Il Ya une réflexion. 

-C'est L'équipe de baseball Nuevitas. Voilà leur logo. 

-Et Il parle celui qui est vêtu cette veste. 

[FIN LECTURE] 

DAVID MALAN: Très bien. Ceci est CS50 ce qui est un peu plus de [inaudible] avec lequel vous êtes barboteurs avec le problème fixé quatre. Aujourd'hui, nous commençons à regarder un peu plus profondément à ces choses appelées pointeurs, qui, même si elle est un sujet très mystérieux, il se trouve que ça va être les moyens par lesquels on peut commencer à construire et montage programmes beaucoup plus sophistiqués. Mais nous l'avons fait mercredi dernier par le biais de certains claymation premier. Donc cela, rappel, est Binky et nous lui avons utilisé à jeter un oeil à un programme qui n'a pas vraiment faire quelque chose d'intéressant, mais il a fait apparaître quelques problèmes. Donc, pour commencer aujourd'hui, pourquoi ne nous marchons pas rapidement à travers quelques-uns de ces étapes, essayer de distiller dans les termes de droits exactement ce qui se passe ici et pourquoi cela est mauvais, et puis passer et réellement commencer à construire quelque chose avec cette technique? Voilà donc la première deux lignes dans ce programme et en termes simples, ce qui ces deux lignes sont en train de faire? Quelqu'un qui est assez confortable avec ce qui est déclaré sur l'écran? Quels sont ces deux lignes qui font? Il est pas tout à fait différente de la première semaine, mais il ya un nouveau symbole spécial. Ouais? Là-bas. 

AUDIENCE: Déclarer pointeurs? DAVID MALAN: Dites à nouveau? AUDIENCE: Déclarer pointeurs? DAVID MALAN: pointeurs déclarer et nous allons l'affiner un peu plus. AUDIENCE: [inaudible] Adresse x puis y. DAVID MALAN: Et puis répondre. Donc exactement ce que nous faisons est nous déclarons deux variables. Ces variables, cependant, vont être des étoiles de type int, qui plus précisément des moyens ils vont stocker l'adresse d'un int, respectivement, x et y. Maintenant, y at-il des valeurs? Y at-il des adresses réelles dans ces deux variables à ce point dans le temps? Non. Il est juste que l'on appelle des valeurs parasites. Si vous ne donnez pas de fait variables, ce qui était dans la mémoire RAM précédemment va remplir avec des zéros et les deux de ces variables. Mais nous ne savons pas encore ce qu'ils sont et ce est va être la clé pour expliquer pourquoi Binky perdu la tête la semaine dernière. 

Donc, ce fut la pâte à modeler incarnation de cette par lequel vous avez seulement deux des variables, petites pièces circulaires d'argile, qui peut stocker des variables, mais comme les flèches enveloppées suggèrent, ils ne sont pas réellement pointant partout connue en soi. Alors nous avons eu cette ligne, et ce était nouveau la semaine dernière, malloc pour la mémoire l'allocation, qui est juste une façon élégante de dire le système d'exploitation, Linux ou Mac OS ou Windows, hey, donnez-moi un peu de mémoire, et tout ce que vous avez à dire le système d'exploitation est ce que lorsque vous demandez pour la mémoire. Il ne va pas se soucier de ce vous allez faire avec elle, mais vous ne devez dire à l'exploitation ce système par le biais de malloc. Ouais? 

Public: Combien? DAVID MALAN: Combien? Combien en octets, et ainsi, cela, encore une fois, un exemple artificiel, est en train de dire, me donner la taille d'un int. Or, la taille d'un int est quatre octets ou 32 bits. Donc, cela est juste une façon de dire, hey, système d'exploitation, me donner quatre octets de mémoire que je peux utiliser à ma disposition, et plus précisément, qu'est-ce que retour malloc par rapport à ce morceau de quatre octets? AUDIENCE: adresse? DAVID MALAN: L'adresse. L'adresse de ce morceau de quatre octets. Exactement. Et voilà ce qui est stocké en fin de compte en x et qui est pourquoi nous faisons pas vraiment soucier de ce que le nombre de adresse, si elle est OX1 ou ox2 ou une adresse hexadécimale cryptique. Nous nous soucions peu imagée que cette variable x est maintenant pointant vers ce bloc de mémoire. Donc, la flèche représente un pointeur, ou plus précisément, une adresse de mémoire. Mais encore une fois, nous ne nous soucions pas habituellement ce sont les adresses réelles. Maintenant, cette ligne indique ce qui en termes simples? Étoile obtient 42 x virgule. Qu'est-ce que cela signifie? Tu veux partir? Ne pas rayer votre cou. 

PUBLIC: L'adresse de x est au 42. 

DAVID MALAN: L'adresse de x est à 42. Pas assez. Si près, mais pas tout à fait, car il ya l'étoile qui est précéder cette x. Nous avons donc besoin de tordre un peu. Ouais? 

PUBLIC: La valeur que le pointeur x pointe vers est 42. DAVID MALAN: OK. La valeur que le pointeur x est pointant vers, disons, doit être 42, ou, autrement dit, la star x dit, aller à quelque adresse est en x, que ce soit 1 Oxford Street ou 33 Oxford Street ou OX1 ou OX33, quel que soit cette adresse numérique est, star du x est le déréférencement de x. Alors, allez à cette adresse et puis mettre le numéro 42 il. Donc, ce serait une de façon équivalente de dire que. Voilà donc tout va bien puis nous représenter l'image comme suit où nous avons ajouté 42 à la partie de quatre que octets sur le côté droit, mais cette ligne était où les choses ont mal tourné et la tête de Binky sauté descendre à ce point, parce que de mauvaises choses arrivent quand vous déréférencer des valeurs parasites ou vous déréférencer invalide pointeurs, et je dis non valide car à ce stade dans le histoire, ce qui est à l'intérieur de y? Quelle est la valeur de y en fonction sur les dernières étapes? Ouais? Qu'est ce que c'est? 

PUBLIC: Une adresse. DAVID MALAN: Une adresse. Il devrait être une adresse mais ai-je initialisé il? Je dois donc pas encore. Donc ce qui est connu pour être là-dedans? Il est juste une certaine valeur d'ordures. Il pourrait être une adresse de zéro à 2 milliards si vous avez deux concerts de RAM, ou zéro à 4 milliards d'euros si vous avez obtenu quatre gigaoctets de RAM. Il est une valeur d'ordures, mais le problème est que le système d'exploitation, si elle ne vous a pas donné ce morceau de mémoire spécifiquement que vous essayez d'aller à, il est généralement va causer ce nous avons vu comme un défaut de segmentation. Donc, en fait, aucun d'entre vous qui ont lutté à problèmes aux heures de bureau ou des problèmes qui est plus généralement à essayer de comprendre une erreur de segmentation, cela signifie généralement vous touchez un segment de mémoire que vous ne devriez pas être. Vous mémoire toucher que le système d'exploitation n'a pas vous a permis de toucher, que ce soit en allant trop loin dans votre tableau ou à partir de maintenant, si il est parce que vous touchez mémoire qui est juste une certaine valeur d'ordures. 

Ce faisant, star du x est ici genre de comportement indéfini. Vous ne devriez jamais le faire parce que les cotes sont, le programme va juste pour dormir, parce que vous dites, aller à cette adresse et vous avez aucune idée où cette adresse est réellement. Ainsi, le système d'exploitation est susceptible va crasher votre programme à la suite et, en fait, que ce ce qui est arrivé à Binky. En fin de compte, Binky fixé ce problème avec cela. Alors que le programme lui-même était viciée. Mais si vous sorte d'aller de l'avant et d'exécuter cette ligne à la place, y est égal à x signifie simplement ce que Adresse est un x, aussi le mettre en y. 

Et si imagée, nous avons cet représenté avec deux flèches à partir de x et de y pointage à la même place. Donc, sémantiquement, x est égal à y parce que ces deux sont le stockage de la même adresse, ergo pointant à 42, et maintenant, quand vous dites étoiles y, allez à l'adresse en y, cela a un effet secondaire intéressant. Donc, l'adresse dans l'est y même chose que l'adresse en x. Donc, si vous dites aller à l'adresse en y et modifiez la valeur à 13, Qui d'autre est concerné? X est, point D, pour ainsi dire, devraient être affectés ainsi. 

Et en effet, comment Nick a attiré cette image en pâte à modeler était exactement cela. Même si nous suivons le pointeur y, nous avons fini à la même place, et si nous étions à imprimer à x ou y de l'pointée, nous verrions alors la valeur de 13. Maintenant, je dis à être pointée compatible avec la vidéo. Programmeurs, à mon connaissance, jamais réellement dire le mot pointée, ce qui est pointu à, mais par souci de cohérence avec la vidéo, réaliser qui est tout ce qui était signifie dans cette situation. Donc, des questions sur claymation ou des pointeurs ou malloc pour l'instant? Non? Bien. 

Alors sans plus tarder, nous allons jeter un coup d'oeil à où cela a effectivement été utilisé pendant un certain temps. Donc, nous avons eu cette bibliothèque CS50 qui a obtenu toutes ces fonctions. Nous avons utilisé getint beaucoup, GetString, sans doute plus tôt GetLongLong dans mon PSet un ou deux, mais ce qui est réellement été en cours? Eh bien, nous allons jeter un coup d'œil sous le capot à un programme qui inspire pourquoi nous vous donnons la CS50 bibliothèque, et même la semaine dernière, nous avons commencé à prendre les roues de formation au large. Donc, cela est maintenant triée d'un post-mortem de ce que a été en cours intérieur de la bibliothèque CS50, même si nous allons maintenant commencer à bouger loin de la plupart des programmes. 

Alors ceci est un programme appelé scanf 0. Il est super court. Il a juste ces lignes, mais il introduit une fonction appelée scanf que nous allons vraiment voir dans un moment à l'intérieur de la bibliothèque CS50, quoique sous une forme légèrement différente. Donc, ce programme sur la ligne 16 est une variable x déclarant. Donc me donner quatre octets pour un int. Il a été dit utilisateur, Numéro s'il vous plaît, et ensuite ceci est une piste intéressante que cravates fait ensemble la semaine dernière et ça. Scanf, puis il faut un avis chaîne de format, tout comme printf, % i signifie un int, et puis il prend une Le deuxième argument qui ressemble un peu funky. Il est esperluette x, et de rappeler, nous ne avons vu cette semaine, une fois dernière. Qu'est-ce que esperluette x représente? Qu'est-ce que esperluette faire en C? Ouais? 

PUBLIC: L'adresse de la. DAVID MALAN: L'adresse de la. Il est donc à l'opposé de l'opérateur étoiles, tandis que l'opérateur star dit, aller à cette adresse, l'opérateur esperluette dit, comprendre la Adresse de cette variable, et si cela est essentiel, parce Le but de scanf dans la vie est de numériser l'utilisateur de entrée à partir du clavier, en fonction de ce qu'il ou elle types, puis lisez l'entrée de cet utilisateur dans une variable, mais nous vu dans les deux dernières semaines que cette fonction d'échange que nous essayé effort pour mettre en œuvre a été juste de rompre. Rappelons que la fonction d'échange, si nous vient de déclarer A et B comme ints, nous ne échangeons avec succès le deux variables à l'intérieur d'échange Tout comme avec le lait et JO, mais dès que swaps retourné, ce qui était le résultat en ce qui concerne pour x et y, les valeurs d'origine? Rien. Ouais. Rien ne se passa ce moment-là, parce swaps changent seulement ses copies locales, qui est-à-dire, tous les cette fois, chaque fois que nous avons été en passant arguments à des fonctions, nous sommes juste de passage des copies de ces arguments. Vous pouvez le faire avec cette ce que vous voulez avec eux, mais ils vont avoir pas effet sur les valeurs d'origine. Donc, ce qui est problématique si vous veulent avoir une fonction comme scanf dans la vie, dont le but est de scanner l'entrée de l'utilisateur à partir du clavier puis remplir les blancs, pour ainsi parler, qui est, lui donner une variable comme x une valeur, parce que si je devais juste passer x à Scanf, si vous considérez la logique de la dernière semaine, scanf peut faire ce qu'il veut une copie de x, mais il ne pouvait pas changer de façon permanente x moins que nous donnions Scanf une carte au trésor, pour ainsi dire, où x marque l'endroit, de sorte que nous passons à l'adresse de x sorte que scanf peut y aller et effectivement le changement la valeur de x. Et en effet, tous les que ce programme ne si je fais scanf 0, dans ma source Répertoire 5m, faire scanf 0, dot slash scanf, numéro s'il vous plaît 50, merci pour le 50. 

Donc, il est pas tout à fait intéressant, mais ce qui se passe en effet est que dès que je l'appelle Scanf ici, la valeur de x est modifié de façon permanente. Maintenant, cela semble agréable et bon, et, en fait, il semble que nous ne devons pas vraiment la bibliothèque de CS50 plus du tout. Par exemple, on devrait courir cette fois de plus ici. Permettez-moi de rouvrir pour une deuxième. Essayons un certain nombre et s'il vous plaît au lieu de dire 50 comme avant, disons simplement pas. OK, qui est un peu bizarre. D'ACCORD. Et juste des bêtises ici. Donc, il ne semble pas gérer des situations erronées. Nous devons donc minimalement début ajoutant un peu de contrôle d'erreur veiller à ce que l'utilisateur a tapé dans un nombre réel comme 50, parce que les mots apparemment taper est pas détecté comme étant problématique, mais il devrait probablement être. 

Regardons cette version maintenant que ce ma tentative de réimplémentons GetString. Si tout cela a scanf fonctionnalité intégrée, Pourquoi avons-nous été barboteurs avec ces roues de formation comme GetString? Eh bien, ici est peut-être mon propre version simple de GetString dans lequel il ya une semaine, je pourrais l'ai dit, me donner une chaîne et l'appeler tampon. Aujourd'hui, je vais commencer tout disant star de char, qui, rappelons, il est juste aussi. Il semble effrayant, mais il est exactement la même chose. Donc, me donner un tampon variable appelée cela va de stocker une chaîne, dire la chaîne de l'utilisateur s'il vous plaît, puis, comme avant, Essayons d'emprunter cette leçon scanf % s cette fois et ensuite passer dans un tampon. Maintenant, un test de cohérence rapide. Pourquoi suis-je ne dis pas esperluette tampon, cette fois? Déduire de l'exemple précédent. AUDIENCE: Char étoiles est un pointeur. DAVID MALAN: Exactement, parce que cette fois, char étoiles est déjà un pointeur, une adresse, par définition de cette étoile d'être là. Et si scanf attend une adresse, il suffit juste de passer dans un tampon. Je ne veux pas dire tampon de esperluette. Pour les curieux, vous pourriez faire quelque chose comme ça. Il aurait sens différent. Cela vous donne un pointeur à un pointeur, qui est en fait une chose valable dans C, mais pour maintenant, nous allons garder les choses simples et de garder l'histoire cohérente. Je vais passer en tampon et qui est exact. Le problème est que cela. Laissez-moi aller de l'avant et lance ce programme après le compiler. Assurez scanf 1. Merde, mon compilateur de attraper mon erreur. Donnez-moi une seconde. Clang. Disons scanf-1.c. D'ACCORD. Nous y voilà. J'en ai besoin. CS50 ID a divers les paramètres de configuration que vous protéger contre vous-même. Je devais désactiver celles de courir clang manuellement cette fois. Alors s'il vous plaît chaîne. Je vais aller de l'avant et tapez dans mon monde de bonjour favori. OK, null. Cela ne veut pas ce que je tapé. Donc, il est indicatif de quelque chose de se tromper. Laissez-moi aller de l'avant et tape dans une très longue chaîne. Merci pour le nul et je ne sais pas si je vais être capable de crasher. Essayons un peu de copie coller et voir si cela aide. Il suffit de coller beaucoup de cela. Il est certainement un plus grand chaîne que d'habitude. Disons simplement vraiment écrire. Non. Bon sang. Commande non trouvée. Voilà donc sans rapport. Voilà parce que je collais quelques mauvais caractères, mais cela se révèle ne va pas fonctionner. 

Essayons une fois de plus, parce il est plus amusant si on fait crasher. Disons tapez cela et maintenant, je suis aller à copier une très longue chaîne et maintenant nous allons voir si nous peut faire planter cette chose. Remarquez que je omis espaces et nouvelles lignes et des points-virgules et tous les personnages funky. Entrez. Et maintenant, le réseau vient d'être lent. Je tenais la touche Commande-V trop longtemps, clairement. Bon sang! Commande non trouvée. 

D'ACCORD. Eh bien, le point est néanmoins la suivante. Alors qu'est-ce qui se passe réellement avec cette déclaration de char buffer étoiles sur la ligne 16? Alors, que suis-je obtenir quand je déclare un pointeur? Tout ce que je veux en venir est une valeur de quatre octets appelé tampon, mais ce qui est intérieur de celui- en ce moment? Il est juste une certaine valeur d'ordures. Parce que chaque fois que vous déclarez une variable en C, elle est juste une certaine valeur d'ordures, et nous commençons à trébucher sur cette réalité. Maintenant, quand je dis scanf, aller à cette adresse et mettre ce que l'utilisateur tape dans. Si les types d'utilisateurs dans bonjour monde, eh bien, où dois-je le mettre? Est une valeur tampon d'ordures. 

Voilà donc un peu comme une flèche que cela pointant qui sait où. Peut-être il pointant ici dans ma mémoire. Et donc quand l'utilisateur types dans Bonjour tout le monde, le programme tente de mettre la Bonjour tout le monde chaîne barre oblique inverse 0 dans ce morceau de mémoire. Mais avec une forte probabilité, mais clairement pas 100% de probabilité, l'ordinateur va alors se bloquer le programme parce que ce ne sont pas souvenir que je devrais être autorisé à toucher. Donc en bref, ce programme est viciée précisément pour cette raison. Je fondamentalement pas faire quoi? Quelles sont les étapes que je omis, tout comme nous avons omis de premier exemple de Binky? Ouais? 

AUDIENCE: allocation de mémoire? 

DAVID MALAN: allocation de mémoire. Je ne suis pas réellement alloué toute la mémoire pour cette chaîne. Donc, nous pouvons résoudre ce problème dans un couple des manières. Un, nous pouvons garder les choses simples et en fait, maintenant vous êtes va commencer à voir un flou des lignes entre ce un tableau est, ce qui est une chaîne, quel omble étoiles est, ce qu'est un tableau de caractères est. Voici un deuxième exemple impliquant cordes et avis tout ce que je l'ai fait en ligne 16 est, au lieu de dire ce tampon va être un caractère étoiles, un pointeur vers un bloc de mémoire, Je vais donner très proactive moi un tampon pour 16 caractères, et en fait, si vous êtes familier avec le tampon terme, probablement du monde de la vidéo, où une vidéo est mise en mémoire tampon, en mémoire tampon, mise en mémoire tampon. Eh bien, quel est le lien ici? Eh bien, à l'intérieur de YouTube et à l'intérieur des lecteurs vidéo est généralement un tableau qui est plus grand que 16. Il pourrait être un tableau de taille un mégaoctet, peut-être 10 mégaoctets, et dans ce tableau ne votre navigateur télécharger tout un tas d'octets, tout un tas de mégaoctets de vidéo et le lecteur vidéo, De YouTube ou quiconque est, commence lire les octets de ce tableau, et chaque fois que vous voyez le mot tampon, tampon, cela signifie que le joueur a arrivé à la fin de ce tableau. Le réseau est si lente qu'elle n'a pas rempli le tableau avec plusieurs octets et vous êtes hors de bits à afficher pour l'utilisateur. 

Donc tampon est un terme approprié ici à ce que il est juste un tableau, un morceau de la mémoire. Et ce sera le fixer car il se trouve que vous pouvez traiter les tableaux comme si ils sont des adresses, même si le tampon est juste un symbole, il est un séquence de caractères, un tampon, qui est utile pour moi, le programmeur, vous pouvez passer autour de son nom comme si elle était une pointeur, comme si elle étaient l'adresse d'un morceau de mémoire pour 16 caractères. Voilà donc à dire, je peux passer l'scanf exactement ce mot et maintenant, si je fais ce programme, faire scanf 2, point barre oblique scanf 2, et tapez Bonjour tout le monde, Entrée, cela time-- 

Hmm, ce qui est arrivé? Chaîne s'il vous plaît. Qu'ai-je fait de mal? Bonjour tout le monde, tampon. Bonjour le monde. Ah, je sais ce qu'il fait. D'ACCORD. Donc, il est la lecture jusqu'à jusqu'à ce que le premier espace. Donc, nous allons tricher pendant un moment et dire que je voulais juste de taper quelque chose vraiment long comme ceci est une longue phrase voilà un, deux, trois, quatre, cinq, six, sept, huit, neuf, 10, 11, 12, 13, 14, 15, 16. D'ACCORD. Il est en effet une longue phrase. Donc, cette phrase est plus de 16 caractères et ainsi lorsque je tape Entrée, ce qu'il va se passer? Eh bien, dans ce cas de la tampon histoire, je l'avais déclaré étant en fait à une matrice avec 16 caractères prêt à aller. Donc, un, deux, trois, quatre, cinq, six, sept, huit, neuf, dix, onze, douze, treize, quatorze, 15, 16. Donc 16 caractères, et maintenant, quand je lire quelque chose comme ceci est un long phrase, qu'est-ce qui va se passer est que je vais lire dans ce est un long S-E-N-T-E-N-C-E, phrase. 

Donc, cela est délibérément une mauvaise chose que je continuer à écrire au-delà du limites de mon tableau, au-delà des limites de mon tampon. Je pourrais avoir de la chance et le programme va continuer à courir et pas de soins, mais en général, cette sera en effet planter mon programme, et il ya un bug dans mon coder le moment je fais un pas au-delà des limites de ce tableau, parce que je Je ne sais pas si elle est aller nécessairement à écraser ou si je vais juste avoir de la chance. Donc, ce qui est problématique parce que dans ce cas, il ne semble pas fonctionner et nous allons tenter le sort ici, même si l'IDE semble tolérer un peu de-- 

Nous y voilà. Finalement. Donc, je suis le seul qui peut voir cela. Donc, je viens d'avoir beaucoup de dactylographie amusant sur une très longue phrase réelle que certainement dépassé 16 octets, parce que je tapé dans cette longue ligne multi-fou phrase, puis notez ce qui est arrivé. Le programme a tenté imprimer et puis a obtenu une erreur de segmentation et des erreurs de segmentation est quand quelque chose comme cela se produit et le dit système d'exploitation Non, ne peut pas toucher cette mémoire. Nous allons tuer le programme tout à fait. 

Donc, cela semble problématique. Je me suis amélioré le programme en vertu duquel au moins avoir un peu de mémoire, mais cela semble confiner la fonction pour obtenir GetString certaines chaînes de longueur finie 16. Donc, si vous voulez soutenir plus peines de 16 caractères, Que faire? Eh bien, vous pouvez augmenter la taille de ce tampon à 32 ou qui semble sorte de court. Pourquoi ne faisons pas il 1000 mais repousser. Quelle est la réponse intuitivement seulement d'éviter ce problème en faisant mon buffer plus grand, comme 1000 caractères? En mettant en œuvre GetString cette façon. Ce qui est bon ou mauvais ici? Ouais? Public: Si vous liez un lot de l'espace et vous ne l'utilisez pas, alors vous ne pouvez pas réaffecter cet espace. DAVID MALAN: Absolument. Il est inutile dans la mesure où si vous ne le faites pas réellement besoin de ces 900 octets et pourtant vous demandez 1000 au total de toute façon, vous êtes juste de consommer plus de mémoire sur l'ordinateur de l'utilisateur que vous avez besoin, et après tout, certains de vous avez déjà rencontré dans la vie que lorsque vous êtes courir beaucoup de programmes et qu'ils mangent trop de mémoire, cela peut effectivement affecter les performances et l'expérience de l'utilisateur sur l'ordinateur. Voilà donc une sorte de solution paresseuse, pour sûr, et inversement, il est non seulement inutile, ce problème demeure, même si je fais mon mémoire tampon 1000? Ouais? 

PUBLIC: La chaîne est de longueur 1001. DAVID MALAN: Exactement. Si votre chaîne est de longueur 1001, vous avez exactement le même problème, et par mon argumentation, je le ferais vient ensuite rendre 2000, mais vous ne savez pas dans avancer la taille qu'elle devrait être, et pourtant, je dois compiler mon programme avant de laisser les gens utilisent et téléchargement ce. Donc, cela est exactement le genre de choses que la bibliothèque essais CS50 pour nous aider avec et nous allons seulement regard à la mise en œuvre de certaines sous-jacent ici, mais cela est CS50 point C. Cette est le fichier qui a été sur CS50 IDE toutes ces semaines que vous avez déjà utilisé. Il est pré-compilé et vous avez été en utilisant automatiquement par la nature de l'comportant dash L CS50 indicateurs avec fracas, mais si je faire défiler tous ces fonctions, voici GetString, et juste pour vous donner une goût de ce qui se passe, nous allons jeter un coup d'oeil sur la relative complexité. Il est pas un super long fonction, mais on n'a pas avoir à réfléchir sérieusement à tous les comment s'y prendre pour obtenir des chaînes. 

Alors, voici ma mémoire tampon et je apparemment l'initialiser à NULL. Ceci, bien sûr, est le même chose en tant que char étoiles, mais je décidai de l'application de la bibliothèque CS50 que si nous allons être totalement dynamique, Je ne sais pas à l'avance la taille d'un les utilisateurs de chaîne vont vouloir obtenir. Donc, je vais commencer avec juste une chaîne vide et je vais construire autant mémoire que je dois adapter à la chaîne de l'utilisateur et si je ne ai pas assez, je vais demander à le système d'exploitation pour plus de mémoire. Je vais passer leur chaîne dans un plus gros morceau de la mémoire et je vais libérer ou libérer la insuffisamment grande partie de la mémoire et nous allons juste pour ce faire de manière itérative. 

Ainsi, un rapide coup d'œil, voici juste une variable avec laquelle je vais garder la trace de la capacité du tampon ma. Combien d'octets que je peux adapter? Voici une variable n avec que je vais continuer à trace de combien d'octets sont réellement dans le tampon ou que l'utilisateur a saisi. Si vous avez pas vu cela avant, vous peut spécifier qu'une variable comme un int est non signé, qui, comme son nom l'indique, signifie qu'il est non-négatif, et pourquoi Je veux plus jamais à se soucier spécifiant qu'un int est non seulement un int, mais il est un unsigned int? Il est un int non-négative. Qu'est-ce que le [inaudible] signifie? 

PUBLIC: Il est décrit une quantité de mémoire qui peut être [inaudible]. 

DAVID MALAN: Ouais. Donc, si je dis non signé, cela est effectivement vous donnant un peu de mémoire supplémentaire et il semble un peu ridicule, mais si vous avoir un peu de mémoire supplémentaire, que signifie que vous avez deux fois plus nombreux valeurs que vous pouvez représenter, car il peut être un 0 ou un 1. Donc, par défaut, un int peut être à peu près négative de 2 milliards de tout le chemin jusqu'à 2 milliards de positif. Ce sont de grandes plages, mais il est encore un peu de gaspillage si vous vous souciez seulement tailles, qui vient intuitivement devrait être non-négative ou positif ou 0, eh bien, pourquoi êtes-vous perdez 2 milliards valeurs possibles pour les nombres négatifs si vous allez jamais à les utiliser? Donc, en disant non signé, maintenant mon int peut être entre 0 et environ 4 milliards. 

Alors, voici juste un int C pour des raisons nous ne serons pas entrer dans ce moment que pourquoi il est un int place d'un char, mais voici l'essentiel de ce qui se passe sur, et certains d'entre vous on pourrait en utilisant, par exemple, la fonction fgetc même dans quatre PSet ou par la suite, nous verrons ce nouveau en problème posé cinq, fgetc est agréable parce que le nom en quelque sorte, suggère sorte de arcanely, il est une fonction qui obtient un caractère et ainsi, ce qui est fondamentalement différent à propos de ce que nous faisons dans GetString est que nous ne sommes pas à l'aide scanf de la même façon. Nous sommes juste rampant étape par étape sur ce que l'utilisateur a tapé dans, parce que nous pouvons toujours allouer un char, et ainsi nous pouvons toujours en toute sécurité regarder un omble à la fois, et la magie commence à se produire ici. Je vais faire défiler vers le bas pour Au milieu de cette fonction juste pour présenter brièvement cette fonction. Tout comme il ya une fonction malloc, il est une fonction de realloc où realloc vous permet de réaffecter une partie de la mémoire et le rendre plus grand ou plus petit. Tant histoire courte et une vague de ma main pour aujourd'hui, savoir que ce GetString fait est qu'il est en quelque sorte de magie croissance ou retrait du tampon en tant qu'utilisateur types dans sa chaîne. 

Donc, si l'utilisateur tape une courte chaîne, ce code seulement alloue assez mémoire pour adapter la chaîne. Si l'utilisateur maintient le typage comme je l'ai fait encore et encore et encore, eh bien, si le tampon de ce grand départ et le programme réalise, à attendez une minute, je suis hors de l'espace, il va doubler la taille de la mémoire tampon puis doubler la taille de la mémoire tampon et le code qui fait le doublement, si nous regardons ici, il est juste cette habile one-liner. Vous pourriez ne pas avoir vu cette syntaxe avant, mais si vous dites étoiles égale, cela est la même chose que disant fois de capacité 2. Donc, il ne cesse de doubler la capacité de la mémoire tampon puis dire realloc pour donner lui-même que beaucoup plus de mémoire. 

Maintenant, en aparté, il sont d'autres fonctions dans ici que nous ne regarderons pas dans les détails autre que de montrer dans getint, nous utilisons GetString dans getint. Nous vérifions qu'il est pas null, qui, rappelons, est la valeur spéciale qui signifie quelque chose a mal tourné. Nous sommes sortis de la mémoire. Mieux vérifier cela. Et nous revenons une valeur sentinelle. Mais je vais laisser les commentaires quant à pourquoi et puis nous utilisons ce cousin de scanf sscanf appelé et il se trouve que sscanf, ou une chaîne scanf, vous permet de jeter un oeil à la ligne l'utilisateur a tapé dans et vous laisser analyser essentiellement et ce que je suis fais ici est que je dis sscanf, analyser quel que soit l'utilisateur tapé dans et assurez-vous% i, il est un entier, et nous ne serons pas entrer aujourd'hui exactement pourquoi il ya aussi un c%, mais que, dans un mot permet de détecter si l'utilisateur a tapé dans quelque chose de faux après le numéro. Donc la raison pour laquelle getint et GetString vous dire à réessayer, réessayer, réessayez est cause de tous que le code que nous avons écrit, il est une sorte de regarder l'entrée de l'utilisateur en veillant à ce qu'il est entièrement numérique ou il est un flottant réelle valeur du point ou similaire, en fonction de ce que la valeur fonctionnez vous utilisez. 

Ouf. D'ACCORD. Ce fut une bouchée mais le point est ici que la raison pour laquelle nous avions ces roues de formation sur est parce que, au niveau le plus bas, Il ya tellement de choses qui peut aller mal que nous voulions pour traiter préventivement ces choses certainement dans le premières semaines de la classe, mais maintenant, avec PSet quatre et cinq et PSet au-delà de vous verrez qu'il est plus vers vous, mais aussi que vous êtes plus capable de résoudre ce genre de problèmes vous-même. Des questions sur GetString ou getint? Ouais? 

Public: Pourquoi voudriez-vous doubler la capacité de la mémoire tampon plutôt que de simplement augmenter par le montant exact? 

DAVID MALAN: Bonne question. Pourquoi voudrions-nous doubler la capacité du tampon plutôt que juste à l'aggraver par une certaine valeur constante? Il était une décision de conception. Nous avons juste décidé que parce qu'elle tend à être un peu cher temps-sage de demander le système d'exploitation pour mémoire, nous ne l'avons pas vouloir finir par entrer dans une situation pour les grandes chaînes que nous demandions l'OS encore et encore et encore et encore dans succession rapide pour la mémoire. Donc nous avons juste décidé, un peu arbitrairement, mais nous espérons raisonnablement, que, vous savez quoi, nous allons essayer de prendre de l'avance de nous-mêmes et juste continuer à doubler en sorte que nous minimisons la quantité de fois nous devons appeler malloc ou realloc, mais un jugement totale appeler en l'absence de savoir ce que les utilisateurs pourraient vouloir saisir. Les deux méthodes pourraient être défendable. Sans doute bonne. 

Donc, nous allons jeter un oeil à un couple d'autres effets secondaires de la mémoire, choses qui peuvent mal se passer et des outils que vous pouvez utiliser pour attraper ces types d'erreurs. Il se trouve tout de vous, même si check50 ne vous a pas dit autant, ont écrit poussette Code depuis la première semaine, même si tous les tests sont check50 passé, et même si vous et votre TF sont convaincus que super- votre code fonctionne comme prévu. Votre code a été buggy ou viciée en ce que chacun d'entre vous, en utilisant la bibliothèque CS50, ont été fuite mémoire. Vous avez demandé le système d'exploitation pour la mémoire dans la plupart des programmes vous avez écrit, mais vous avez jamais réellement redonné. Vous avez appelé GetString et getint et GetFloat, mais avec GetString, vous avez jamais appelé unGetString ou donner String ou similaire, mais nous avons vu que GetString fait allouer de la mémoire par voie de malloc ou cette fonction realloc, qui est juste très similaire dans l'esprit, et pourtant, nous avons été demandant au système d'exploitation pour mémoire et la mémoire encore et encore mais jamais lui redonner. 

Maintenant, en aparté, il se trouve que quand un programme se ferme, la totalité de la mémoire est automatiquement libéré. Donc, cela n'a pas été une affaire énorme. Il ne va pas se casser la IDE ou ralentir les choses, Mais lorsque les programmes font généralement fuite de mémoire et ils sont en cours d'exécution pendant une longue période. Si vous avez déjà vu la petite bête ballon de plage dans Mac OS ou le sablier sur Windows où il est une sorte de ralentir ou de penser ou de penser ou commence vraiment de ralentir à une exploration, il pourrait être très probablement le résultat d'une fuite de mémoire. Les programmeurs qui ont écrit le logiciel que vous utilisez demander au système d'exploitation pour la mémoire toutes les quelques minutes, toutes les heures. Mais si vous utilisez la logiciel, même si elle est minimisé dans votre ordinateur pendant des heures ou des jours, vous demandez peut-être pour de plus en plus la mémoire et l'utiliser en fait jamais et ainsi votre code pourrait être, ou programmes pourraient être une fuite de mémoire, et si vous commencez à perdre la mémoire, il ya moins de mémoire pour les autres programmes, et l'effet est de tout ralentir. 

Maintenant, cela est de loin l'un des les programmes les plus atroces vous aurez l'occasion à fonctionner dans la mesure où CS50 que sa sortie est encore plus ésotérique que clang de faire ou de toute ou de la commande programmes en ligne que nous avons exécuté avant mais heureusement, noyé dans sa sortie est quelques conseils utiles que super- sera utile soit pour PSet quatre ou certainement PSEt cinq. Donc valgrind est un outil qui peut être utilisé pour comparer pour les fuites de mémoire dans votre programme. Il est relativement simple à exécuter. Vous exécutez valgrind puis, même si elle est un peu verbeux, dash chèque tableau de bord de fuite est égal à plein, puis dot slash et le nom de votre programme. Donc valgrind sera ensuite exécuter votre programme et à la fin de votre programme courir avant qu'il quitte et vous donne une autre invite, il va analyser votre programme alors qu'il avait couru et dites que vous avez-vous des fuites toute la mémoire et, mieux encore, avez-vous touchez mémoire ne vous appartiennent? Il ne peut pas attraper tout, mais il est assez bon à attraper la plupart des choses. 

Alors, voici un exemple de mon avoir couru ce programme, ayant couru valgrind, sur un programme appelé la mémoire, et je vais de mettre en évidence les lignes qui sont en fin de compte de l'intérêt pour nous. Donc, il ya encore plus de distractions que je l'ai supprimé de la diapositive. Mais voyons ce que cette programme est capable de nous dire. Il est capable de nous dire les choses comme écriture invalide de taille 4. En d'autres termes, si vous touchez la mémoire, en particulier 4 octets de mémoire que vous ne devriez pas avoir, valgrind peut vous le dire. Écriture invalide de taille 4. Vous avez abordé quatre octets que vous ne devriez pas avoir. Où avez-vous fait cela? Ceci est la beauté. Mémoire dot ligne de 21 c est là que vous foiré et voilà pourquoi il est utile. Tout comme GDB, il peut aider vous indiquer à l'erreur réelle. 

Maintenant, celui-ci est un peu plus verbose, sinon confus. 40 octets dans 1 blocs sont certainement perdu dans le dossier de la perte de 1 1. Qu'est-ce que cela veut dire? Eh bien, cela signifie simplement que vous avez demandé 40 octets et que vous ne lui avez donné dos. Vous avez appelé malloc ou vous avez appelé GetString et le système d'exploitation vous 40 octets, mais vous jamais donné libérés ou libérés que la mémoire, et pour être honnête, nous ne l'avons jamais montrons vous comment redonner la mémoire. Avère qu'il ya un Super simple fonction dite libre. Prend un argument, la chose vous voulez libérer ou donner en retour, mais 40 octets, apparemment, dans ce programme ont été perdus à la ligne 20 de la mémoire dot c. 

Voyons donc ce programme. Il est super inutile. Il démontre seulement cette erreur particulière. Donc, nous allons jeter un coup d'oeil. Voici principales et principaux, avis, les appels une fonction appelée rendements F puis. Donc, pas tout à fait intéressant. Qu'est-ce que f faire? Remarquez que je ne vous embêtez pas avec un prototype. Je voulais garder le code aussi minime que possible. Donc, je mets principal et f ci-dessus ça va, certainement, pour les programmes courts comme celui-ci. Donc f ne renvoie rien et fait rien prendre, mais il ne le faire. Il déclare, tout comme dans l'exemple Binky, un pointeur appelé x qui va pour stocker l'adresse d'un int. Voilà donc le côté gauche. En anglais, ce qui est le côté droit de faire? Toute personne? Quel est ce fait pour nous? Ouais? 

AUDIENCE: [inaudible] fois la taille d'un int qui est 10 fois que [inaudible] DAVID MALAN: Bon et permettez-moi de résumer. Donc allouer suffisamment d'espace pour 10 entiers ou 10, ce qui est de la taille d'un int, il est quatre octets, de sorte que 10 fois 4 est 40, de sorte que droite que je l'ai surbrillance est me donner 40 octets et stocker l'adresse du premier octet en x. Et maintenant, enfin, et voici où ce programme est bogué, ce qui est mal avec la ligne 21 basée sur cette logique? Quel est le problème avec la ligne 21? Ouais? AUDIENCE: Vous ne pouvez pas index dans x [inaudible]. DAVID MALAN: Ouais. Je ne devrais pas index dans x comme ça. Donc, syntaxiquement, qui est OK. Ce qui est bien est, un peu comme vous peut traiter le nom d'un tableau comme si elle est un pointeur, de façon similaire pouvez-vous traiter un pointeur comme si elle est un tableau, et je ne peux donc syntaxiquement dire x support de quelque chose, x support i, mais la figure 10 est problématique. Pourquoi? 

AUDIENCE: Parce qu'il est pas à l'intérieur. 

DAVID MALAN: Il est pas à l'intérieur de ce morceau de mémoire. Quelle est la plus grande valeur que je devrait être mise en ces crochets? 9, 0 à 9. Du fait de l'indexation zéro. Ainsi de 0 à 9 serait bien. Support 10 est pas bon et mais, rappeler que, chaque fois Il me semble essayer de faire CS50 IDE accident en tapant des valeurs fausses, il ne collabore pas toujours, et en effet, vous avez souvent avoir de la chance juste parce que le système d'exploitation ne fait pas vous remarquerez que très légèrement passer quelque morceau de la mémoire, parce que vous êtes resté au sein techniquement votre segment, mais plus sur ce dans une classe de systèmes d'exploitation, et ainsi de quelque chose comme ça pourrait très facilement passer inaperçue. Votre programme ne va jamais à planter systématiquement mais peut-être de temps en temps. 

Et donc nous allons essayer valgrind sur ce point, et voici où nous aurons dépassé par la sortie momentanément. Donc, assurez-mémoire chèque valgrind de fuite est égal à la mémoire pleine dot slash. Et voici pourquoi je promets ce serait submerger. Voici ce que valgrind, voici ce que un programmeur, certains ans- décidé que ce serait une bonne idée pour la sortie de ressembler. Faisons donc le sens de cette. Donc, tout le chemin à la main gauche côté sans raison valable est l'ID de processus du programme nous venons de courir, l'identifiant unique pour le programme que nous avons manqué. Nous avons supprimé qu'à partir de la diapositive, mais il quelques informations utiles ici. 

Disons défiler jusqu'à sommet. Voici où nous avons commencé. Donc, il est pas tant que ça sortie. Voici ce que écriture invalide de la taille 4 à la ligne 21. Eh bien, ce qui était la ligne 21? Ligne 21 était exactement cela et il est logique que je suis dans valablement écrire 4 octets parce que je suis essayer de mettre cet entier, qui pourrait être quelque chose, il arrive juste pour être zéro, mais je suis en train pour le mettre à un endroit qui ne fait pas de moi. De plus, ici-bas, 40 octets dans un blocs sont définitivement perdus dans fiche 1. Cela est parce que quand je l'appelle malloc ici, je jamais réellement libérer la mémoire. 

Alors, comment pouvons-nous résoudre ce problème? Permettez-moi aller de l'avant et être un peu plus sûr et faire 9 là et laissez-moi ici gratuitement x. Ceci est la nouvelle fonction pour aujourd'hui. Si je ReRun maintenant faire mémoire de points slash, exécutons valgrind sur elle à nouveau, maximiser ma fenêtre et appuyez sur Entrée. Maintenant, il est bon. Ils enterrent les bonnes nouvelles dans l'ensemble de cette sortie. Tous les blocs de tas étaient libres. Nous allons revenir à ce que le tas est, mais pas de fuites sont possibles. Donc, ceci est juste un autre outil pour votre trousse à outils avec lequel vous pouvez commencer à maintenant trouver des erreurs comme ça. 

Mais voyons ce que plus peut aller mal ici. Laissez de transition maintenant résoudre réellement un problème. En aparté, si cela va soulager peu de confusion ou de tension, cela est maintenant drôle. Ouais. Cela est assez bon. Parce que les pointeurs sont des adresses et des adresses ayant généralement par convention écrit avec hexadécimal. Ha, ha, ça drôle maintenant. Quoi qu'il en soit, nous allons donc maintenant effectivement résoudre un problème. Cela a été super, super bas niveau à ce jour, et nous pouvons réellement faire utiles choses avec ces détails de bas niveau. 

Donc, nous avons introduit quelques semaines il ya la notion d'un tableau. Un tableau était bien car il est difficile de nettoyer notre code parce que si nous voulions écrire un programme avec plusieurs étudiants ou plusieurs noms et les maisons et dortoirs et des collèges et tout cela, nous pourrions tout stocker plus proprement à l'intérieur d'un tableau. Mais proposer un inconvénient d'un tableau jusqu'ici. Même si vous avez pas souffert soi-même dans un programme, juste instinctivement, ce qui est une mauvaise chose à propos d'un tableau, peut-être? Je entends quelques murmures. PUBLIC: Il est difficile pour modifier la taille. DAVID MALAN: Il est difficile pour modifier la taille. Vous ne pouvez pas modifier la taille d'un tableau, en fait, en soi, en C. Vous pouvez attribuer un autre tableau, déplacer tout de l'ancien dans le nouveau, et maintenant avoir un peu d'espace supplémentaire, mais il est pas comme un langage comme Java ou Python ou un nombre quelconque d'autres langues avec lesquelles certains d'entre vous connaissez peut-être où vous peut simplement continuer à ajouter des choses ad nauseam à la fin d'un tableau. Lorsque vous avez un tableau de taille 6, qui est sa taille, et ainsi de beaucoup l'idée plus tôt ayant une mémoire tampon d'une certaine taille, vous devez deviner hors de la porte quelle taille voulez-vous qu'il soit? Si vous devinez trop grand, vous perdez l'espace. Si vous devinez trop petite, vous ne peut pas stocker les données, au moins sans beaucoup plus de travail. 

Donc, aujourd'hui, grâce à des pointeurs, nous pouvons commencer assemblant notre propre personnalisé des structures de données, et fait, voici quelque chose qui ressemble un peu plus cryptique au premier coup d'œil, mais cela est ce que nous appellerons un lien liste, et son nom de genre résume ce. Il est une liste de numéros, ou ce cas, une liste de numéros, mais il pourrait être une liste de quelque chose, mais il est lié à l'autre par des flèches, et juste prendre une proposition avec quelle technique allons-nous être en mesure à assembler, un peu comme du pop-corn avec un fil, une liée listes rectangles ici? Ses numéros? Quelle est la fonction de la langue sous-jacente? 

PUBLIC: Un pointeur. 

DAVID MALAN: Un pointeur. Donc, chacun de ces flèches représente ici un pointeur ou tout simplement une adresse. Donc, en d'autres termes, si je veux pour stocker une liste de numéros, Je ne peux pas stocker si je veux la capacité à croître et à se rétrécir la structure de mon données dans un tableau. Donc, je dois avoir un peu plus de sophistication, mais remarquez que cette image type de suggère que si vous avez juste petits fils connectant tout ensemble, est probablement pas si difficile à faire de l'espace entre deux de ces rectangles ou deux de ces nœuds, comme nous allons commencer les appelant, mettre dans un nouveau nœud, et ensuite avec un nouveau fil, tout simplement abandonner les trois nœuds ensemble, la première, la dernière, et la une que vous venez d'insérer dans le milieu. 

Et en effet, une liste chaînée, contrairement à un tableau, est dynamique. Il peut se développer et il peut réduisez et vous ne le faites pas avoir à connaître ou de soins à l'avance comment beaucoup de données vous allez être stocker, mais il se trouve que nous devons être un peu attention à la façon de mettre en œuvre. Donc, d'abord nous allons examiner comment nous mettons en œuvre un de ces petits rectangles. Il est facile à mettre en œuvre un int. Vous dites simplement int n, puis vous obtenez 4 octets pour un int, mais comment puis-je obtenir un int, appelez ça n, puis un pointeur, appelons-le suivant. Nous pourrions appeler ces les choses ce que nous voulons mais je besoin d'une structure de données personnalisé. Ouais? 

AUDIENCE: Ampersand [inaudible]. 

DAVID MALAN: Donc esperluette nous allons utiliser pour obtenir l'adresse d'un noeud potentiellement. Mais nous avons besoin d'une autre caractéristique de C dans l'ordre de me donner la possibilité de créer ce rectangle de coutume, cette coutume variable si vous voulez, dans la mémoire. PUBLIC: Une struct. DAVID MALAN: Une struct. Rappelons que la semaine dernière, nous avons lancé struct, cette relativement simple mot-clé qui nous permet de faire des choses comme ça. C ne vient pas avec un ensemble de données structure appelée étudiant. Il est livré avec int et float et l'omble chevalier et tel, mais il ne vient pas avec l'élève, mais nous pouvons créer un type de données de l'étudiant, une structure d'étudiant, avec cette syntaxe Ici. Et vous verrez encore et encore. Donc, ne vous inquiétez pas mémoriser les mots-clés, mais le mot-clé qui est important est juste le fait que nous avons dit struct puis nous l'avons appelé étudiant et à l'intérieur de l'étudiant était un nom et une maison ou un dortoir ou similaire. 

Et maintenant aujourd'hui, nous allons proposer cette. Je ai ajouté quelques mots, mais si je veux de mettre en œuvre ce rectangle qui est a obtenu à la fois un int et un pointeur, vous savez quoi, je suis aller à déclarer une struct appelé noeud. Je suis aussi, à l'intérieur de celui-ci, va dire qu'un noeud, ce rectangle, a une int et nous appelons n et il dispose d'un pointeur à côté. Et cela est un peu verbeux, mais si vous pensez cela, les flèches qui étaient dans l'image il ya un moment sont de ce type de données? Où chacun de ces flèches est pointée à ce type de structure de données? Ça ne pointe pas juste pour un int en soi. Il est pointant vers le rectangulaire toute chose et cette chose rectangulaire, nous l'avons dit, est appelé un nœud. Et donc nous avons une sorte de à définir de manière récursive cette tels qu'un nœud, nous dirons, contiendra un int appelé n et un pointeur appelé prochaine et la type de structure de données dans laquelle que les points de pointeur est apparemment va être struct noeud. 

Donc, cela est fâcheusement verbose et juste pour être pédant, la raison pour laquelle nous ne pouvons pas juste dire ce qui franchement ressemble beaucoup plus lisible, est parce que c lire le rappel les choses de haut en bas, de gauche à droite. Il est pas jusqu'à ce que nous obtenons le point-virgule que le noeud mot-clé existe réellement. Donc, si nous voulons avoir ce genre de référence cyclique à l'intérieur des données la structure, nous avons à faire, où nous disons noeud struct au sommet, qui nous donne une façon de décrire ce plus chose, puis à l'intérieur nous disons noeud de struct, puis à la dernière ligne nous disons, tout droit, C, par la manière, il suffit d'appeler toute cette foutue chose et d'arrêter un noeud en utilisant tout à fait le mot-clé struct. Donc, cela est juste une sorte de syntaxique astuce qui permet en fin de compte nous créons quelque chose qui ressemble exactement à cela. 

Donc, si nous supposons maintenant que nous pouvons mettre en œuvre cette chose en C, comment pouvons-nous réellement commencer traversant ce? Eh bien, en fait, tout ce que nous avons à faire est itérer de gauche à droite et juste genre d'insérer ou de supprimer des noeuds noeuds ou chercher des choses là où nous voulons, mais pour ce faire, nous allons aller de l'avant et de faire les choses un peu plus réelle parce que cette a été faible niveau super jusqu'ici. Quelqu'un voudrait littéralement être le premier? D'ACCORD. Allez vers le haut. Comment t'appelles tu? 

DAVID: David. DAVID MALAN: David. Enchanté de faire votre connaissance. Moi aussi. Bien. Et nous avons besoin d'un numéro 9. Pas aussi bon que la première, peut-être. OK, le numéro 9. Un certain nombre 17, s'il vous plaît. Permettez-moi de revenir un peu plus loin. Nombre 22, s'il vous plaît, et que diriez-vous plus loin si je peux voir toutes les mains avec toute la lumière ou pas. Quelqu'un étant volontaire là. Voulez-vous venir? Votre avant-bras est de force à la hausse. OK, 17. 22. 26 descend. Quiconque voudrait forcefully-- Allez jusqu'à. Un volontaire réelle. 

Donc, très rapidement, si vous les gars pourraient organiser vous voulez juste les noeuds sur l'écran. Merci. Et vous serez 26. Toutes les bonnes introductions et rapide. Donc, je suis David et vous êtes aussi? DAVID: David. DAVID MALAN: Et vous êtes? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Excellente. Donc, ce sont nos bénévoles pour aujourd'hui et aller de l'avant et de passer un peu de cette façon, et juste aller de l'avant et de garder la tenue de vos numéros que vous êtes ou votre premier signe et l'aide de votre main gauche, aller de l'avant et juste mettre en œuvre ces flèches, tout simplement de sorte que votre main gauche est littéralement montrant tout ce que vous devez mentionner à, et vous donner une certaine marge de telle sorte que nous pouvons voir visuellement vos bras effectivement pointage, et vous pouvez simplement pointer sorte de au rez-est très bien. 

Nous avons donc ici une liste liée de l'une, deux, trois, quatre, cinq noeuds initialement, et remarquez que nous avons cette spéciale pointeur au début qui est clé parce que nous devons garder la trace de l'ensemble de la liste de la longueur d'une certaine manière. Ces gars-là, même si elles sont laissées à droite, dos à dos dans la mémoire, ils peuvent effectivement être partout dans la mémoire de l'ordinateur. Donc, ces gars-là pourraient être debout partout sur la scène et ça va, tant qu'ils sont effectivement pointant à l'autre, mais de garder les choses propre et simple, nous allons juste les dessiner à droite comme à gauche , mais il pourrait y avoir des lacunes massives entre ces noeuds. 

Maintenant, si je veux réellement insérer des nouvelle valeur, nous allons aller de l'avant et le faire. Nous avons maintenant l'occasion de choisir un autre nœud. Dites nous allons commencer avec les allouer de 55. Quelqu'un aurait l'esprit étant malloc? OK, venez sur place. Comment t'appelles tu? RAINBOW: arc en ciel. DAVID MALAN: Rainbow? Bien. Malloc arc. Allez vers le haut. Alors maintenant, nous devons nous demander algorithmique où nous pouvons mettre 55. Donc, nous le savons tous, évidemment, où elle a probablement appartient si nous essayons de garder cette triée Et si vous les gars pourrait prendre une du recul afin de ne pas tomber la scène, ce serait formidable. Donc en fait, Rainbow, recommencer ici avec moi, parce que nous, l'ordinateur peut maintenant ne verrez qu'une seule variable à la fois. Donc, si tel est le premier noeud. Notez qu'il est pas un nœud, il est juste un pointeur, et voilà pourquoi il a dessiné pour être seulement la taille d'un pointeur, pas un de ces rectangles pleins. Donc, nous allons vérifier à chaque itération est inférieure à 55 9? Non. Is 55, moins de 17? Non. Moins de 22? Moins de 26? Moins de 34? Et maintenant, évidemment Arc en ciel appartient à la fin. Donc, pour être clair, et ce était votre nom, Taylor? 

TAYLOR: Taylor. DAVID MALAN: Donc parmi Taylor main gauche et les mains de l'arc ici, dont la main a besoin de pointer ce qui, dans Afin d'insérer 55 dans cette liste? Que devons-nous faire? Ouais? 

AUDIENCE: la main de Taylor doit pointer gauche. 

DAVID MALAN: Exactement. Ainsi, l'insertion d'un nœud dans la fin de la liste est assez simple parce que Taylor simplement a signaler, au lieu de la terre ou nous l'appellerons null, null est en quelque sorte l'absence d'un pointeur ou un spécial pointeur zéro, vous êtes va pointer avec votre gauche main à Rainbow et Rainbow où si votre gauche main probablement Point? Vers le bas. Il est pas bon si sa main est en quelque sorte de pointer au large ici ou toute sorte de Quelle direction. Ce serait considéré comme une valeur d'ordures, mais si elle montre une certaine valeur connue, nous allons appeler zéro ou nulle, qui est OK parce que nous avons un terme dans ce et nous savons la liste est maintenant terminée. 

Alors, quel est l'autre cas relativement simple? Pourrions-nous malloc 5? Allez vers le haut. Comment t'appelles tu? TIFFANY: Tiffany. DAVID MALAN: Je suis désolé? TIFFANY: Tiffany. DAVID MALAN: Tiffany. Bien. Tiffany a été malloced avec la valeur 5. Allez vers le haut. Celui-ci est relativement facile aussi, mais nous allons examiner maintenant l'ordre des opérations. Il était assez facile avec Taylor à la fin. Nombre 5 est bien sûr moins de 9, et nous avons donc David, nous avons Tiffany, et quel était votre nom? 

JAKE: Jake. 

DAVID MALAN: Jake. Tiffany, Jake, et David. Dont la main devrait être mis à jour en premier? Que voulez-vous faire ici? Il ya quelques façons possibles, mais il ya aussi un ou des moyens plus mauvaises. 

AUDIENCE: Commencez par la plus à gauche. 

DAVID MALAN: Commencez par le plus à gauche. Qui est le plus à gauche ici, alors? AUDIENCE: Première. 

DAVID MALAN: OK. Donc, commencer par la première et où avez-vous vouloir mettre à jour les mains de David d'être? AUDIENCE: Vers la 5. DAVID MALAN: OK. Alors David, le point à cinq ou Tiffany ici, et maintenant? 

AUDIENCE: Tiffany pointe vers le 9? DAVID MALAN: Parfait, sauf de Binky la tête juste un peu tombé, non? Parce que ce qui ne va pas avec cette image littéralement? AUDIENCE: Rien pointe. DAVID MALAN: Rien pointant vers Jake maintenant. Nous avons littéralement orphelins 9 et 17, et nous avons littéralement fuyait de cette mémoire, parce que, par mise à jour de la main de David d'abord, que ce bien dans la mesure où il est correctement pointant à Tiffany maintenant, mais si personne ne l'avait prévoyance pour pointer vers Jake, alors nous avons perdu la totalité de cette liste. Donc, nous allons défaire. Donc, ce fut une bonne chose trébucher mais nous allons corriger maintenant. Que devrions-nous faire en premier lieu? Ouais? 

AUDIENCE: Tiffany doit pointer au 9? DAVID MALAN: je ne peux pas obtenir que près de vous. Qui devrait pointer le 9? 

AUDIENCE: Tiffany. 

DAVID MALAN: Très bien. Donc Tiffany devrait premier point à la 9. Donc Tiffany devrait prendre sur une valeur identique à David, qui semble redondant pour un moment, mais cela est très bien, parce que maintenant, deuxième étape, nous pouvons mettre à jour la main de David à signaler, et puis si à Tiffany Nous venons genre de nettoyer les choses comme si cela est une sorte de printanier, voilà une bonne insertion. Donc excellente. Alors maintenant, nous y sommes presque. Insérons une dernière valeur comme la valeur 20. Si nous pouvions malloc un bénévole finale? Allez vers le haut. Alors celui-ci est un peu plus délicat. Mais vraiment, le code que nous sommes l'écriture, mais verbalement, est juste comme avoir un tas si les conditions de l'entreprise, non? Nous avions une condition vérifier si elle appartient à la fin, peut-être le début. Nous avons besoin d'une sorte de boucle trouver l'endroit dans le milieu. Donc, nous allons faire avec ce qui est votre nom? 

ERIC: Eric. 

DAVID MALAN: Eric? Eric. Enchanté de faire votre connaissance. Nous avons donc 20. Moins de cinq ans? Non. Moins de neuf? Non. Moins de 17? Non. D'ACCORD. Il appartient ici et vos noms sont à nouveau? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, et? ERIC: Eric. DAVID MALAN: Eric. Dont les mains ont besoin de se mettre à jour en premier? 

AUDIENCE: Eric. D'ACCORD. Donc, d'Eric devrait pointer où? A 22 ans. Bien. Et maintenant, quelle est la prochaine? Sue peut alors pointer Eric et maintenant, si vous les gars juste faire de la place, ce qui est bien visuellement, maintenant que nous avons fait de l'insertion. Donc, nous allons maintenant examiner une question, mais je vous remercie beaucoup pour nos bénévoles. Très bien fait. Vous pouvez garder ceux-ci, si vous le souhaitez. Et nous avons un beau cadeau d'adieu si vous seriez chaque aimez prendre une boule de stress. Permettez-moi de passer cette baisse. Alors quelle est la livraison de ce? Cela semble être incroyable dans la mesure où nous avons maintenant introduit une alternative à un tableau qui ne s'y limite pas à un tableau d'une certaine taille fixe. Ils peuvent se développer dynamiquement. 

Mais tout comme nous l'avons vu dans les semaines passé, nous ne sommes jamais rien pour rien, comme il ya sûrement un compromis ici. Donc, avec une tête d'un lien liste, est ce dynamisme? Cette capacité à croître et franchement, nous aurions pu faire de suppression et nous pouvions réduire si nécessaire. Quel prix payons-nous? Deux fois autant d'espace, tout d'abord. Si vous regardez l'image, pas plus suis-je stocker une liste d'entiers. Je stocker une liste des entiers ainsi que des pointeurs. Donc, je suis doublement de la quantité d'espace. Maintenant, peut-être que ce pas de nature une grosse affaire de 4 octets, 8 octets, mais il pourrait certainement ajouter pour de grands ensembles de données. Quel est un autre inconvénient? Ouais? 

PUBLIC: Nous devons traverser les une par une. DAVID MALAN: Ouais. Nous devons les traverser un par un. Vous savez quoi, nous avons renoncé à ce super fonction pratique du crochet notation, plus correctement connu comme l'accès aléatoire, où nous pouvons simplement sauter à un élément individuel mais maintenant, si je devais encore mes bénévoles ici, si je voulais trouver le numéro 22, je ne peux pas passer à quelque chose de support de quelque chose. Je dois regarder par-dessus la liste, beaucoup comme nos exemples DE LA RECHERCHE linéairement, pour trouver le numéro 22. Donc, nous semblons avoir payé un prix là-bas. Mais nous pouvons tout de même résoudre d'autres problèmes. 

En fait, permettez-moi de vous présenter juste un couple de visuels. Donc, si vous avez été jusqu'à Dining Hall Mather récemment, Vous vous souviendrez que leur piles de plateaux comme celui-ci, nous avons emprunté ces partir Annenberg avant la classe. Donc, cette pile de plateaux, même si, est représentatif effectivement d'une structure de données de la science informatique. Il y a une structure de données en informatique connu comme une pile qui très bien se prête à exactement ce visuel. Donc, si chacun de ces plateaux est pas un bac mais comme un certain nombre et je voulais à stocker des numéros, je pourrait mettre un ici-bas, et je pourrais mettre une autre ici-bas, et continuer l'empilage des numéros sur le dessus les uns des autres, et ce qui est potentiellement utiles à ce sujet est que ce qui est de l'implication de cette structure de données? Quel numéro puis-je sortir première la plus commode? Le plus récemment, on a mis là-bas. 

Voilà donc ce que nous appellerions en informatique, une structure de données LIFO. Dernier entré, premier sorti. Et nous verrons avant longtemps pourquoi qui pourraient être utiles, mais pour l'instant, il suffit de considérer la propriété. Et il est un peu stupide si vous pensez sur la façon dont la salle à manger fait. Chaque fois qu'ils plateaux propres et mettre la fraîcheur ceux sur le dessus, vous pourriez avoir un précédemment propre mais finalement très sale et poussiéreux le plateau tout en bas si vous jamais réellement aller au fond de cette pile, parce que vous venez continuer à mettre la nouvelle et celles propres sur le dessus. La même chose pourrait se produire dans un supermarché trop. Si vous avez une vitrine de lait et de tous les temps de CVS ou celui qui obtient plus de lait, vous venez de fourrer les laits vous avez déjà à l'arrière et vous mettez les nouveaux à l'avant, vous allez avoir un peu assez méchant lait à la fin de la structure de données, car il est toujours au fond ou équivalente il est toujours à l'arrière. 

Mais il ya une autre façon de penser alignant données et par exemple, cela. Si vous êtes une de ces personnes qui aime d'aligner à l'extérieur de magasins Apple quand un nouveau produit est livré , vous êtes probablement ne pas utiliser une pile de données la structure parce que vous aliénerait tout le monde qui est la queue pour acheter un nouveau jouet. Au contraire, vous êtes probablement à l'aide quel type de structure de données ou ce genre de système dans le monde réel? Espérons que cela est une ligne, ou plus correctement ou plus Colombie-like, une file d'attente. Et il se trouve une file d'attente est également un structure de données en informatique, mais une file d'attente a une très propriété différente. Il est pas LIFO. Dernier entré, premier sorti. Dieu pardonne. Il est à la place FIFO. Premier entré, premier sorti. Et cela est une bonne chose pour l'équité 'amour certainement lorsque vous doublure jusqu'à super tôt dans la matinée. Si vous y arrivez d'abord, vous vouloir sortir premier ainsi. 

Et si toutes ces données les structures, les files d'attente et des piles et grappes d'autrui, se révèle vous peut considérer cela comme un simple tableau. Ceci est un tableau, peut-être une taille fixe 4, mais ce serait être une sorte de bien si nous pouvions juste empiler plateaux presque infiniment grand si nous avoir autant de plateaux ou des numéros. Alors peut-être que nous voulons utiliser une liste liée ici, mais le compromis va être potentiellement que nous avons besoin de plus de mémoire, prend un peu plus de temps, mais nous ne limitent pas la hauteur de la pile, un peu comme la vitrine de Mather peut limiter la taille de la pile, et ce sont donc des décisions de conception ou options disponibles pour nous en fin de compte. Donc, avec ces données structures, nous avons commencé voir de nouvelles limites supérieures potentiellement sur ce qui était auparavant super rapide et où nous partirons off aujourd'hui et où nous espérons obtenir à est le mercredi, nous allons commencer à regarder une donnée structure qui nous permet de chercher grâce à des données dans le journal l'heure de fin de nouveau. Et nous avons vu que, rappelons-le, à la semaine zéro et l'autre avec la recherche binaire ou fracture et conquérir. Il va revenir et, mieux encore, le Saint-Graal pour ce mercredi sera à venir avec la structure de données qui fonctionne réellement ou théoriquement constante de temps, de sorte que il n'a pas d'importance combien de millions ou des milliards de choses nous avons dans la structure de données, il sera nous prendre constante de temps, peut-être une étape ou deux étapes ou 10 étapes, mais un nombre constant d'étapes de recherche à travers cette structure de données. Ce sera en effet le Saint Graal mais plus sur que le mercredi. See ya ensuite. 

[Jouer de la musique]