DAVID MALAN: Très bien, bienvenue. C'est CS50. C'est le début de la septième semaine. Donc ça a été un certain temps, donc je pensais que nous avions prendre un tour d'horizon de ce que nous quittés et où nous allons maintenant. 

Donc cette chose pourrait ici avoir causé une certaine angoisse au premier abord. Mais espérons que vous commencez à s'acclimater à ce que cela désigne ici - étoile qui représente un pointeur, ce qui est tout ce qui, en termes plus simples? Il s'agit donc d'une adresse. 

Donc, c'est l'adresse de quelque chose en mémoire. Et nous avons commencé à peler les couches Il ya quelques semaines, des choses comme GetString et d'autres fonctions tout ce temps ont été revient adresses des choses en mémoire, comme le l'adresse du premier caractère de certaines séquences. 

Donc, nous avons également introduit valgrind, qui vous commencerez à utiliser pour résoudre ce problème régler, en particulier pour la prochaine problème réglé ainsi. Et valgrind fait quoi pour nous? Il vérifie les fuites de mémoire, et il vérifie également pour abus de mémoire. 

Il peut, avec une certaine probabilité, détecter si votre code va toucher mémoire qu'il ne devrait tout simplement pas. Donc, pas nécessairement une fuite, mais si vous aller au-delà des limites de certaines tableau, et que vous exécutez en fait valgrind et induire ce comportement tout valgrind est en marche dans votre programme est fonctionne à l'intérieur de celui-ci, vous aurez messages comme celui-ci - «invalide écrire des taille 4 », qui, rappelons quelques il ya quelques semaines signifiait que je devais accidentellement comme sur un int trop loin au-delà des limites d'un tableau. Et si la taille 4 signifie ici que la taille de cette int particulier. 

Alors, prenez réconfort dans le fait que la sortie de valgrind, le format de celui-ci, est tout simplement atroce. Il est vraiment difficile de voir à travers le désordre pour l'information intéressante. Donc ce que nous avons fait ici est juste extrait une partie du couple de plus lignes intéressantes. Mais se rendre compte que 80% de valgrind de sortie va être un peu distraction. 

Il suffit de regarder pour des motifs de ce genre - droite invalide, nulle lire, 40 octets et un nombre de blocs sont certainement perdus, mots-clés comme ça. Et ce que vous voyez est quelque espérons genre de trace de ce qui fonctionne le erreur est en fait po Dans ce cas là, dans quelle branche d' mon code était apparemment l'erreur? 

26 dans un fichier appelé memory.c, qui était l'exemple que nous jouions avec à l'époque. Donc, ce n'est probablement pas dans malloc. C'était probablement dans mon code à la place. Nous allons donc voir ce nouveau et de nouveau avant longtemps. 

Alors scanf, cela est venu dans un quelques formes jusque-là. Nous avons vu sscanf brièvement. C'était quelque chose d'un certain nombre de vous plonge dans dans votre préparations pour le quiz. Et scanf est en fait ce que le CS50 bibliothèque a été utilise sous l' hotte pendant un certain temps afin pour obtenir des entrées de l'utilisateur. 

Par exemple, si je me déplace vers le CS50 appareil ici, laissez-moi ouvrir un exemple aujourd'hui que l'on appelle scanf-0.c Et c'est super simple. C'est juste quelques lignes de code. Mais il démontre vraiment comment getInt a travaillé tout ce temps. 

Dans ce programme, ici, à la ligne 16 , Un avis que je déclare un int. Donc, pas de pointeurs, rien de magique là, juste un int. Puis, dans la ligne 17, je l'invite de utilisateur pour un certain nombre, s'il vous plaît. Puis à la fin de 18, j'utilise scanf ici. Et je l'ai précisé, un peu comme printf, que je m'attends devis unquote pour cent i. 

Donc pour cent i, bien sûr, désigne un int. Mais remarquez que le second argument de scanf est. Comment décririez-vous la deuxième argument après la virgule? Qu'est-ce que c'est? 

C'est l'adresse de x. Donc, c'est utile car en fournissant scanf avec l'adresse de x, ce qui ne qui leur permettent cette fonction à faire? Non seulement y aller, mais aussi faire quoi? 

Faire un changement à elle. Parce que vous pouvez y aller, c'est une sorte de comme une carte à un emplacement dans la mémoire. Et tant que vous fournissez scanf, ou une autre fonction avec une telle carte, qui fonction peut y aller, et pas seulement regardez la valeur, mais il peut aussi modifier cette valeur, ce qui est utile si le but dans la vie de scanf est d' numériser entrée de l'utilisateur, en particulier à partir du clavier. Et f désigne la mise en forme, tout comme printf, le f désigne un format chaîne que vous voulez imprimer. 

Donc en bref, cette ligne 18 dit simplement: essayez de lire un int de l'utilisateur de clavier et stocker à l'intérieur de x, à quelle que soit l'adresse x arrive à vivre à. Et puis enfin, la ligne 19 dit simplement: merci pour l'int, dans ce cas. 

Alors laissez-moi aller de l'avant et faire cela. Donc, assurez-scanf 0. Permettez-moi d'aller de l'avant et agrandir Je vais courir avec cette points slash scanf 0. Nombre, s'il vous plaît? 50. Merci pour le 50. Donc, c'est assez simple. 

Maintenant, ce que n'est-il pas fait? Ce n'est pas faire tout un tas de vérification d'erreur. Par exemple, si je ne coopèrent pas, et je ne tape pas dans un certain nombre, mais au lieu que j'écris quelque chose comme «bonjour», c'est juste un peu étrange. Et l'une des choses les CS50 bibliothèque a été fait pour nous depuis un certain temps, c'est que reprompting et reprompting. 

La tentative de rappel phrase était dans cs50.c, et c'est la raison pour laquelle dans getInt la bibliothèque CS50 est en fait un ensemble de bouquet de longues lignes, parce que nous sommes la vérification des trucs stupides comme ça. L'utilisateur at donne pas nous, en fait, un int? At-il nous donner quelque chose comme une lettre alphabétique? Si oui, nous voulons détecter que et hurler à eux. 

Mais les choses deviennent plus intéressantes Dans l'exemple suivant. Si je vais à scanf-1.c, quelle est la chose qui est fondamentalement modifiée dans cette prochaine exemple? J'utilise char *, bien sûr, au lieu d'int. 

Donc, c'est intéressant, parce que char *, rappelons-le, est vraiment juste l' même chose en tant que chaîne. Alors, il se sent comme c'est peut-être un super- implémentation simple de GetString. Mais j'ai épluché la couche de la bibliothèque CS50, donc je suis appel de cette char * maintenant. Voyons donc où, plus que partout ailleurs, nous allons mal. 

Ligne 17 - Je le répète, s'il vous plaît donnez-moi quelque chose, dans ce cas, d'une chaîne. Et puis dans la ligne suivante, j'appelle scanf, de plus, ce qui lui donne un code de format, mais cette fois pour cent s. Et puis cette fois, je suis ce qui lui donne un tampon. 

Maintenant, remarquez, je ne suis pas à l'aide l'esperluette. Mais pourquoi est-ce probablement OK ici? Parce que ce qui est déjà tampon? C'est déjà un pointeur. C'est déjà une adresse. 

Et disons ce mot de «confondre», permettez-moi de il suffit d'appeler c'est, par exemple, pour simplicité. Mais je l'ai appelé tampon parce que dans général, dans la programmation, si vous avez un morceau de mémoire, qui une chaîne vraiment seulement, vous pourriez l'appeler un tampon. C'est un endroit pour stocker des informations. 

Semblable à des choses comme YouTube, lorsque ils tampon, pour ainsi dire, que signifie simplement que c'est le téléchargement de morceaux l'Internet et les stocker dans une tableau local, un morceau de la mémoire locale afin que vous pouvez regarder plus tard sans il sauter ou accroché vous pendant la lecture. 

Donc, il ya un problème cependant, parce que je dis scanf, s'attendre à une Chaîne de l'utilisateur. Voici l'adresse du un morceau de la mémoire. Mettez cette chaîne là. Pourquoi est-ce lié donner nous trouble, si? 

Qu'est-ce que c'est? Suis-je autorisé à accéder la partie de la mémoire? Vous savez, je ne sais pas. Parce a tampon été initialisé à quelque chose? Pas vraiment. Et c'est ce que nous avons appelé une valeur d'ordures, qui n'est pas un mot formel. Cela signifie simplement que nous n'avons aucune idée de ce que les bits sont à l'intérieur des quatre octets qui J'ai réparti comme tampon. 

Je n'ai pas appelé malloc. J'ai certainement pas appelé GetString. Alors, qui sait ce qui est réellement à l'intérieur du tampon? Et pourtant dire scanf aveuglément, allez-y et mettre ce que l'utilisateur a tapé. 

Donc ce qui est susceptible de causer dans notre code si nous courons? Probablement une erreur de segmentation. Peut-être pas, mais probablement une erreur de segmentation. Et je dis peut-être pas parce que parfois vous le faites, parfois vous n'obtenez pas une erreur de segmentation. Parfois vous avez juste avoir de la chance, mais il est néanmoins va être un bug dans notre programme. 

Alors laissez-moi aller de l'avant et de compiler cela. Je vais faire de la façon old school. Alors clang dash 0, scanf-1, scanf-1.c, Entrée. Oops, trop vieille école. Voyons voir. Où ai-je aller? Oh, char buffer d'*. Oh, merci - Enregistrer, OK - très vieille école. Très bien, ça fait un moment. 

Donc, je viens de sauvé le fichier après faisant que temporaire changer il ya un instant. Et maintenant, j'ai compilé manuellement avec Clang. Et maintenant, je vais aller de l'avant et exécuter scanf-1, Entrée. Chaîne s'il vous plaît. Je vais taper dans «bonjour». 

Et maintenant, voici où, franchement, printf CAN est un peu ennuyeux. Ce n'est pas vraiment aller à erreur de segmentation dans ce cas. Printf est un peu spécial car il est tellement superbe couramment utilisé que printf est essentiellement faire nous une faveur et la réalisation, ce n'est pas un pointeur valide. Permettez-moi de prendre sur moi de tout imprimer dans parenthèses nulle, voire si ce n'est pas nécessairement ce nous nous attendions. 

Donc, nous ne pouvons pas vraiment facilement induire une erreur de segmentation avec cela, mais clairement cette n'est pas le comportement que je voulais. Alors quelle est la solution simple? Eh bien, dans scanf-2, permettez-moi de proposer que au lieu d'allouer une réalité juste char *, laissez-moi être un peu plus intelligent sur cela, et laissez-moi allouer un tampon comme une séquence de 16 caractères. 

Donc, je peux faire cela dans un couple des manières. Je ne pouvais absolument utiliser malloc. Mais je peux revenir à deux semaines lorsque J'avais juste besoin de tout un tas d' caractères. C'est juste un tableau. Alors laissez-moi plutôt redéfinir tampon à être un ensemble de 16 caractères. 

Et maintenant, quand je passe tampon - et c'est quelque chose que nous n'avons pas parler dans deux semaines - mais vous pouvez traiter un tableau comme si c'est une adresse. Techniquement, comme nous l'avons vu, ils sont un peu différent. Mais scanf ne m'en voudra pas si vous lui passez le nom d'un tableau, parce que ce Clang fera pour nous, c'est essentiellement traiter le nom de ce tableau comme l'adresse du bloc de 16 octets. 

Donc, c'est mieux. Cela signifie maintenant que je peux espérons procédez comme suit. Permettez-moi de faire un zoom arrière pour un moment et faire faire scanf-2, compilé OK. Maintenant, permettez-moi de ne suis slash scanf-2. Chaîne s'il vous plaît. "Bonjour." Et il semblait fonctionner pour le moment. 

Mais quelqu'un peut proposer un scénario dans laquelle il ne pourrait pas continuer à travailler? Ouais? Quelque chose de plus de 16 caractères. Et en fait, nous pouvons être un peu plus précis. Quelque chose de plus puis 15 caractères, parce que vraiment, nous devons garder à l'esprit que nous avons besoin que les anti-slash zéro implicitement à la fin de la chaîne, qui est un côté scanf sera typiquement prendre soin de nous. 

Permettez-moi de faire quelque chose comme - Parfois, nous pouvons simplement le laisser comme ça. OK, donc nous avons maintenant induit l' notre erreur de segmentation. Pourquoi? Parce que j'ai tapé à plus de 15 personnages, et c'est pourquoi nous avons fait mémoire touché que j'ai fait ne devrait pas avoir. 

Alors, quelle est vraiment la solution ici? Eh bien, si nous avons besoin d'une chaîne plus longue? Eh bien, nous faisons peut-être 32 octets. Eh bien, si ce n'est pas assez de temps? Comment environ 64 octets? Et si ce n'est pas assez de temps? Comment environ 128 ou 200 octets? Ce qui est vraiment la solution ici, dans la cas général, si nous ne savons pas dans l'avance ce que l'utilisateur va taper? 

C'est juste une sorte de grosse douleur dans le cul, pour être honnête, ce qui explique pourquoi le Bibliothèque CS50 a quelques dizaines de lignes de Code qui mettent en œuvre collectivement GetString chaîne d'une manière que nous n'avons pas doivent savoir à l'avance ce que l' utilisateur va taper. En particulier, si vous regardez en arrière cs50.c d'il ya deux semaines, vous verrez GetString qui ne fait pas utiliser scanf de cette façon. Plutôt, il lit un caractère à la fois. 

En raison d'une bonne chose à propos lecture d'un caractère est que nous pouvons nous assurer de toujours avoir au moins un caractère. Je peux simplement déclarer un char, puis prendre ces mesures véritablement bébé à juste lire un caractère à une moment à partir du clavier. Et puis, ce que vous verrez GetString ne fait que chaque fois qu'il s'exécute sur, disons, 16 octets de mémoire, il utilise malloc, ou un de ses cousin, à allouer plus de mémoire, la copie l'ancienne mémoire dans le nouveau, puis ramper ainsi, obtenir un caractère à la fois, et quand il est à court de cette morceau de mémoire, le jette, grabs un gros morceau de la mémoire, copie ancienne dans de nouveaux et répète. Et c'est vraiment une douleur à fait mettre en œuvre quelque chose d'aussi simple que La contribution d'un utilisateur. 

Ainsi, vous pouvez utiliser scanf. Vous pouvez utiliser d'autres fonctions similaires. Et beaucoup de manuels scolaires et en ligne exemples font, mais ils sont tous vulnérables à ce genre de problème. Et en fin de compte, se faire une erreur de segmentation est assez ennuyeux. Ce n'est pas bon pour l'utilisateur. 

Mais dans le pire des cas, ce qui ne il fondamentalement mettre votre code au risque d'? Une sorte d'attaque, potentiellement. Nous avons parlé d'une telle attaque - débordement de la pile. Mais en général, si vous êtes autorisé à débordement de tampon, comme nous avons fait un Il ya quelques semaines, avec juste écrit plus de "bonjour" sur la pile, vous peut en effet prendre le relais, potentiellement, un ordinateur, ou tout au moins à obtenir des données qui ne vous appartient pas. 

Donc en bref, c'est pourquoi nous avons les roues de formation. Mais maintenant, nous commençons à les enlever, que nos programmes ne doivent plus, nécessairement, entrée de l'utilisateur. Mais dans le cas du problème posé six, votre contribution proviendra d'une énorme fichier de dictionnaire avec 150 certains quelques mille mots. 

Ainsi, vous n'aurez pas à vous soucier de entrée arbitraire de l'utilisateur. Nous allons vous donner quelques hypothèses sur ce fichier. Toutes les questions sur des pointeurs ou scanf ou saisie de l'utilisateur en général? 

D'accord, donc un coup d'œil puis à une fuite sujet il ya deux semaines. Et c'est cette notion de structure. Non pas que - cette notion de structure, qui était quoi? Qu'est-ce que struct faire pour nous? 

Définir - désolé? Définir un type de variable. Donc, en quelque sorte. Nous sommes en fait la combinaison de deux sujets. Donc, avec typedef, rappelons que nous pouvons déclarer un type de la nôtre, comme un synonyme, comme chaîne de char *. Mais en utilisant typedef struct et, nous pouvons vraiment créer nos propres structures de données. 

Par exemple, si je retourne dans gedit ici pendant un moment, et je vais de l'avant et faire quelque chose comme, permettez-moi à sauver ce que, disons, structs.c temporairement, je vais juste à aller de l'avant et de comprendre standardio.h, void main int. Et puis ici, suppose que je veux d'écrire un programme qui stocke plusieurs étudiants provenant de plusieurs maisons, par exemple. Donc, c'est comme un registrariat base de données de quelque sorte. 

Donc, si je dois le nom d'un étudiant, je pourrait faire quelque chose comme nom char *, et je ferai quelque chose comme - en fait, nous allons utiliser la bibliothèque CS50 juste un moment pour en faire une peu plus simple, afin que nous puissions emprunter ces dizaines de lignes de code. Et nous allons simplement garder les choses simples. Nous gardons chaîne, et maintenant GetString. 

Donc je prétends maintenant que j'ai enregistré le nom de certains élèves, et la maison de certains élèves, simplement en utilisant des variables comme nous l'avons fait et dans une semaine. Mais supposons que je veux maintenant soutenir plusieurs étudiants. D'accord, donc mes instincts sont à faire chaîne name2, obtient GetString, string house2 obtient GetString. Et puis notre troisième étudiant, Faisons name3 GetString. 

D'accord, c'est donc j'espère frappant vous comme une sorte de stupide, car ce processus est vraiment jamais aller à la fin, et il va tout simplement faire mon code semble pire et de pire en pire. Mais nous avons résolu cela aussi dans deux semaines. Quelle était notre solution relativement propre lorsque nous avons eu plusieurs variables de l' même type de données qui sont tous reliés, mais nous ne voulions pas ce gâchis atroce des variables du même nom? Qu'avons-nous fait à la place? 

Donc, je pense que j'ai entendu quelques endroits. Nous avons eu un tableau. Si vous souhaitez plusieurs instances d' quelque chose, pourquoi ne pas nettoyer tout cela et dire simplement, donnez-moi tableau appelé noms? 

Et pour l'instant, nous allons coder en dur 3. Et alors me donner un autre tableau appelé maisons, et laissez-moi Code maintenant difficile 3. Et j'ai massivement nettoyé le plaisante que je viens de créer. Maintenant, j'ai toujours codé en dur 3, mais même le 3 pourrait venir de manière dynamique à partir de l' l'utilisateur ou argv, ou analogue. Donc, c'est déjà plus propre. 

Mais ce qui est gênant à ce sujet est que maintenant, même si un nom est en quelque sorte fondamentalement lié à la maison de l'étudiant - c'est un étudiant que j'ai vraiment vouloir représenter - J'ai maintenant deux rangées parallèles dans le sens où ils sont le même taille, et les noms support 0 vraisemblablement cartes jusqu'aux maisons support 0, et les noms Support 1 cartes aux maisons support 1. En d'autres termes, cet étudiant vit dans cette maison, et que d'autres élèves vit dans cette autre maison. Mais sûrement ce qui pourrait être fait encore plus proprement. 

Eh bien, il peut, en fait. Et permettez-moi d'aller de l'avant et ouvrir jusqu'à structs.h, et vous aurez Voir cette idée ici. Remarquez que j'ai utilisé typedef, comme vous fait allusion il ya un instant de déclarer notre propre type de données. Mais je suis également en utilisant cette autre mot-clé appelé struct qui me donne une nouvelle la structure de données. 

Et cette structure de données je prétends va d'avoir deux choses à l'intérieur de il - une chaîne appelée nom, et une chaîne appelée maison. Et le nom que je vais donner à cette structure de données va d'être appelé étudiant. Je pourrais l'appeler ce que je veux, mais sémantiquement faire sens pour moi dans mon esprit. 

Alors maintenant, si j'ouvre une meilleure version du programme j'ai commencé à écrire là, permettez-moi de faire défiler vers le haut. Et il ya encore quelques lignes de code ici, mais je me concentrerai pour le moment sur une. J'ai déclaré une constante appelée étudiants et codé en dur 3 pour l'instant. Mais maintenant, remarquez comment propre mon code commence à arriver. 

Dans la ligne 22, je déclare éventail d'étudiants. Et remarquez cet élève est apparemment maintenant un type de données. Parce que dans la partie supérieure de ce fichier, notez J'ai inclus ce fichier d'en-tête que je me suis arrêtée il ya quelques instants. Et ce fichier d'en-tête avait tout simplement cette définition d'un étudiant. 

Alors maintenant, j'ai créé mes propres données personnalisées Type que les auteurs de C années Il ya ne pense pas que de l'avance. Mais pas de problème. Je peux le faire moi-même. Il s'agit donc d'un tableau appelé les étudiants, chacun des membres dont est une structure de l'élève. Et je veux que trois d'entre eux dans le tableau. 

Et maintenant, que fait le reste de ce programme? J'ai besoin de quelque chose un peu arbitraire. Donc, de ligne 24 avant, I itérer de 0 à 3. Je demande alors à l'utilisateur Le nom de l'étudiant. Et puis-je utiliser GetString comme avant. Puis-je demander à la maison de l'étudiant, et j'utilise GetString comme avant. 

Mais remarquez - légèrement nouveau morceau de syntaxe - Je peux encore l'indice de la i-ème étudiant, mais comment puis-je obtenir les données spécifiques à l'intérieur du champ de la structure? Eh bien, ce qui est apparemment le nouveau morceau de syntaxe? C'est juste de l'opérateur point. 

Nous n'avons pas vraiment vu cela auparavant. Vous l'avez vu dans pset cinq si vous avez plongé déjà avec les fichiers bitmap. Mais le point signifie juste à l'intérieur de cette struct ou plusieurs champs, donnent dot nom, ou me donner maison dot. Cela signifie aller à l'intérieur de la structure et obtenir ces domaines particuliers. 

Qu'est-ce que le reste de ce programme? Ce n'est pas tout ce que sexy. Remarquez que je itérer de 0 à 3 fois, et je crée simplement un Anglais phrase comme telle et telle chose est de telle ou une telle maison, en passant le nom de point de le i-ème étudiant et leur maison ainsi. 

Et puis enfin, maintenant nous allons commencer à obtenir anale à ce sujet, maintenant que nous sommes familier avec ce que malloc et d'autres fonctions ont été faisant tout ce temps. Pourquoi dois-je libérer la fois le nom et la maison, même si je ne pas appeler malloc? 

GetString fait. Et ce fut le sale petit secret pour plusieurs semaines, mais a GetString été une fuite mémoire dans le placer tout le semestre à ce jour. Et Valgrand sera finalement révéler ce à nous. 

Mais ce n'est pas une grosse affaire, parce que je sais que je ne peux tout simplement libérer le nom et la maison, bien que techniquement, pour être super, super sûr, je serais faire un peu de vérification d'erreur ici. Quels sont vos instincts vous disent? Que devrais-je vérifiais pour avant que je libère ce qui est un chaîne, alias laquelle un char *? 

Je devrais vraiment vérifier si les étudiants support i nom dot ne égal nulle. Puis ce sera OK pour aller de l'avant et gratuit ce pointeur, et même ou dans l'autre un aussi. Si les étudiants support i maison dot n'est pas égale à null, ce sera maintenant protéger contre le boîtier d'angle dans laquelle GetString retourne quelque chose comme nulle. Et nous avons vu il ya un instant, printf volonté nous protéger ici en disant simplement null, ce qui va avoir l'air bizarre. Mais au moins, il ne sera pas une erreur de segmentation, comme nous l'avons vu. 

Eh bien, permettez-moi de faire autre chose ici. struct-0 est une sorte de programme stupide parce que j'entre toutes ces données, puis il a perdu une fois le programme terminé. Mais permettez-moi d'aller de l'avant et faire ça. Permettez-moi de faire le terminal fenêtre un peu plus grand. Permettez-moi de struct-1, qui est une nouvelle version de ce. 

Je vais zoom avant un peu. Et maintenant, permettez-moi de courir dot slash struct-1. Nom de l'élève - David Mather, nous allons faire Rob Kirkland, Faisons Lauren Leverett. Ce qui est intéressant est maintenant préavis - et je sais que cela parce que J'ai écrit le programme - il ya maintenant un fichier sur mon actuel répertoire appelé students.csv. Certains d'entre vous ont vu ceux-ci dans le monde réel. 

Qu'est-ce qu'un fichier CSV? Valeurs séparées par des virgules. C'est un peu comme un pauvre homme La version d'un fichier Excel. C'est un tableau de lignes et de colonnes vous pouvez ouvrir dans un logiciel comme Excel, ou des chiffres sur un Mac. 

Et si j'ouvre ce fichier ici sur gedit, Avis - et les chiffres ne sont pas là. C'est juste GEdit dire moi numéros de ligne. Avis sur la première ligne de cette fichier est David et Mather. La ligne suivante est Rob virgule Kirkland. Et la troisième ligne est Lauren virgule Leverett. 

Alors qu'est-ce que j'ai créé? J'ai maintenant écrit un programme en C qui efficacement peut générer des feuilles de calcul qui peut être ouvert dans un programme comme Excel. Pas tout à fait de contraindre un ensemble de données, mais si vous avez beaucoup plus grands morceaux de données que vous voulez réellement manipuler et faire des graphiques et de les aiment, c'est peut-être une façon de créer ces données. En outre, CSVs sont réellement superbe commune juste pour stocker des données simples - Yahoo Finance, par exemple, si vous obtenez cotations boursières par leur soi-disant API, le service gratuit qui vous permet de Stock obtenir up-to-the-date actuelle citations pour les entreprises, ils de les restituer à l' super simple format CSV. 

Alors, comment avons-nous fait cela? Eh bien remarquer, la plupart de ce programme de pratiquement les mêmes. Mais remarquez ici, plutôt que print les élèves dehors, sur la ligne 35 avant, je prétends que j'économise le étudiants sur le disque, si vous enregistrez un fichier. 

Donc, notez que je suis déclarer une FILE * - maintenant, c'est un peu une anomalie dans C. Pour une raison quelconque, FILE est tout en majuscules, ce qui n'est pas comme la plupart des autres types de données en C. Mais c'est un haut- type de données, FILE *. Et je déclarer un pointeur vers un fichier, comment vous pouvez penser. 

fopen signifie fichier ouvert. Quel fichier que vous voulez ouvrir? Je veux ouvrir un fichier que je veux appeler arbitrairement students.csv. Je pourrais appeler ça que je veux. 

Et puis prendre une supposition. Qu'est-ce que le second argument à fopen probablement dire? Droite, w pour écrire, pourrait r pour être lu. Il ya pour append si vous voulez ajouter des lignes et non écraser le tout. 

Mais je veux juste de créer ce fichier une fois, donc je vais utiliser devis unquote w. Et je sais que seulement pour l'avoir lu la documentation, ou la page de manuel. Si le fichier n'est pas nulle - en d'autres termes, Si tout va bien là-bas - permettez-moi de parcourir la étudiants de 0 à 3. 

Et maintenant, remarquez qu'il ya quelque chose un tant soit peu différent sur la ligne 41 ici. Ce n'est pas printf. C'est fprintf pour le fichier printf. Donc, il va écrire dans le fichier. Quel fichier? Celui dont le pointeur que vous spécifiez comme premier argument. 

Ensuite, nous spécifions une chaîne de format. Ensuite, nous spécifions que nous voulons chaîne plug-in pour le premier pour cent s, et puis une autre variable ou le second pour cent s. Ensuite, nous fermons le dossier avec fclose. Que je libère la mémoire comme avant, même si Je devrais aller en arrière et ajouter quelques vérifications pour NULL. 

Et c'est tout. fopen, fprintf, fclose me donne l' possibilité de créer des fichiers texte. Maintenant, vous verrez dans le problème ensemble cinq, ce qui implique images, vous utiliserez fichiers binaires au lieu. Mais, fondamentalement, l'idée est la même, même si les fonctions dont vous aurez voir sont un peu différentes. 

Donc visite éclair, mais vous obtiendrez trop familier avec le fichier I/O-- entrée et de sortie - avec pset cinq. Et des questions sur le bases initiales ici? Ouais? 

Que faire si vous essayez de dégager une valeur nulle? Je crois que, à moins libre a obtenu un peu plus convivial, vous pouvez potentiellement une erreur de segmentation. En lui passant NULL est mauvais parce que je n'aime pas croire sans la peine de vérifier pour vous, parce que cela pourrait éventuellement être une perte de temps pour qu'il puisse lui-même faire pour tout le monde dans le monde. Bonne question, cependant. 

Très bien, alors ce genre de se nous un sujet intéressant. Le thème du jeu de problème cinq est criminalistique. Au moins c'est une partie de l'ensemble de problème. Forensics se réfère généralement à l' récupération des informations qui peuvent ou ne pas avoir été supprimé délibérément. Et donc j'ai pensé vous donner un rapide goût de ce qui se passe vraiment sur tous les cette fois sous l' capot de votre ordinateur. 

Par exemple, si vous avez à l'intérieur de votre ordinateur portable ou votre ordinateur de bureau une disque dur, c'est soit une mécanique appareil qui tourne en fait - il ya des choses circulaires appelés plateaux qui ressemble pas à ce que je juste eu à l'écran ici, mais c'est de plus en plus vieille école. Il s'agit d'un trois-et-un-demi-pouce disque dur. Et trois pouces et demi se réfère d' avec de la chose lorsque vous l'installez dans un ordinateur. 

Beaucoup d'entre vous les gars dans vos ordinateurs portables maintenant avoir les disques SSD ou disques SSD, qui n'ont pas de pièces mobiles. Ils sont plus comme RAM et moins comme ces dispositifs mécaniques. Mais les idées sont toujours les mêmes, certainement en ce qui concerne au problème posé cinq. 

Et si vous pensez maintenant un disque dur représente étant un cercle, qui Je vais dessiner comme ça ici. Lorsque vous créez un fichier sur votre ordinateur, qu'il s'agisse d'un SSD, ou en ce cas, un disque dur de vieille école, ce fichier comprend plusieurs bits. Disons que c'est ce 0 et 1, tout un tas de 0 et de 1. Donc, c'est tout mon disque dur. C'est apparemment un assez gros fichier. Et il utilise le 0 et de 1 à l' partie du plateau physique. 

Eh bien, quelle est la partie physique? Eh bien, il s'avère que sur un disque dur, au moins de ce type, il ya ces petits minuscules particules magnétiques. Et ils ont essentiellement nord et pôles sud à eux, de sorte que si vous tourner un de ces particules magnétiques Ainsi, vous pourriez dire que c'est représentant un 1. Et si c'est l'envers du Sud à au nord, vous pourriez dire que c'est ce qui représente un 0. 

Ainsi, dans le monde physique réel, c'est comment vous pourriez représenter quelque chose dans état binaire du 0 et un 1. Donc, c'est tout un fichier. Il ya tout un tas de magnétique des particules qui sont de cette façon ou leur De cette façon, la création de modèles de 0 et de 1. 

Mais il s'avère que lorsque vous enregistrez un fichier, certaines informations sont enregistrées séparément. Il s'agit donc d'une petite table, un répertoire, pour ainsi dire. Et je vais appeler ce nom de colonne, et Je vais appeler cet endroit de la colonne. 

Et je vais vous dire, supposons c'est mon CV. Mon resume.doc est stocké à emplacement, disons 123. Je vais toujours pour ce numéro. Mais il suffit de dire que, tout comme dans la mémoire RAM, vous pouvez prendre un disque dur c'est un gigaoctet ou 200 gigaoctets ou un téraoctet, et vous pouvez nombre de tous les octets. Vous pouvez numéroter tous les morceaux de 8 bits. 

Donc, nous allons dire que cette est l'emplacement 123. Donc ce répertoire à l'intérieur de mon exploitation système se souvient que mon CV est à l'emplacement 123. Mais ça devient intéressant lorsque vous supprimez un fichier. 

Ainsi, par exemple - et heureusement, la plupart du monde a pris sur cette - ce qui arrive quand vous faites glisser un fichier sur votre Mac OS Trash ou votre corbeille de Windows? Quel est le but de le faire? C'est évidemment pour se débarrasser du dossier, mais qu'est-ce que le fait de glisser tomber dans votre corbeille ou votre Corbeille faire sur un ordinateur? 

Absolument rien, vraiment. C'est un peu comme un dossier. Il s'agit d'un dossier spécial, pour être sûr. Mais est-il réellement supprimer le fichier? 

Eh bien, non, parce que certains d'entre vous sans doute ont été comme, oh putain, vous n'avez pas dire de le faire. Donc vous double cliquez sur le Corbeille. Vous avez poussé autour et vous avez récupéré le fichier juste en le faisant glisser sortir de là. Donc, clairement, ce n'est pas nécessairement le supprimer. 

OK, vous êtes plus intelligent que cela. Vous savez que, tout en le faisant glisser dans le Corbeille ne signifie pas vous vider la corbeille. Alors vous allez jusqu'à le menu, et vous dites Vider la corbeille ou sur Vider la Corbeille. Alors qu'est-ce qui se passe? 

Ouais, donc il est supprimé plus. Mais tout ce qui arrive est la suivante. L'ordinateur oublie où resume.doc était. 

Mais ce qui n'a pas changé apparemment dans l'image? Les bits, le 0 et de 1 que je prétends sont sur le site d'un certain aspect physique de le matériel. Ils sont toujours là. C'est juste l'ordinateur dispose d' oublié ce qu'ils sont. 

Donc, c'est essentiellement libéré le fichier de les bits de sorte qu'elles peuvent être réutilisées. Mais ce n'est que vous créez d'autres fichiers, et d'autres fichiers, en plus de fichiers sera probabiliste, ceux 0 et de 1, ces particules magnétiques, se réutilisés, côté à l'envers ou à l'endroit, pour d'autres fichiers, 0 et de 1. 

Alors, vous avez ce laps de temps. Et ce n'est pas du prévisible longueur, vraiment. Cela dépend de la taille de votre disque lecteur et le nombre de fichiers que vous avez et comment rapidement vous faire de nouveaux. Mais il ya cette fenêtre de temps pendant qui que ce fichier est toujours parfaitement recouvrable. 

Donc si jamais vous utilisez des programmes comme McAfee ou Norton pour essayer de récupérer données, tout ce qu'ils font est d'essayer de récupérer cette soi-disant répertoire pour comprendre où votre fichier a été. Et parfois, Norton et dira: fichier est de 93% récupérable. Eh bien, qu'est-ce que ça veut dire? Cela signifie simplement que dans un autre fichier coïncidence fini par utiliser, par exemple, ces morceaux de votre fichier d'origine. 

Donc ce qui est réellement impliqué à récupérer les données? Eh bien, si vous n'avez pas quelque chose comme Norton pré-installé sur votre ordinateur, le mieux que vous pouvez parfois faire est de regarder à l'intégralité du disque dur à la recherche d' schémas de bits. Et l'un des thèmes de jeu de problème cinq, c'est que vous allez consulter la équivalent d'un disque dur, un légiste l'image d'une carte flash compacte à partir d'une un appareil photo numérique, la recherche de la 0s et de 1 qui généralement, avec une grande probabilité, représentent l' démarrage d'une image JPEG. 

Et vous les gars peuvent récupérer les images par en supposant, si je vois ce modèle de bits sur l'image légiste, avec forte probabilité, qui marque le début d'un fichier JPEG. Et si je vois le même schéma encore, qui marque probablement le début d' autre JPEG, et un autre JPEG, ou un autre format JPEG. Et c'est généralement la façon dont récupération de données va fonctionner. Ce qui est bien JPEG est bien le format du fichier lui-même est peu complexe, au début de chaque telle fichier est en fait assez identifiable et simple, comme vous allez le voir, Si vous n'avez pas déjà. 

Donc, nous allons regarder de plus près dessous le capot pour savoir exactement ce qui a été passe, et ce que ces 0 et de 1 sont, pour vous donner un peu plus d'un contexte de ce défi particulier. 

[LECTURE VIDEO] 

-Où votre PC stocke plus des données permanentes. Pour ce faire, les données transitent de RAM ainsi que des signaux de logiciels qui indiquent le disque dur comment stocker ces données. Les circuits de disques durs traduisent ces signaux en tension fluctuations. Ceux-ci, à leur tour, contrôlent le disque dur de pièces mobiles, certains des rares pièces mobiles laissés dans le informatique moderne. 

Certains des signaux de commande d'un moteur qui tourne plateaux revêtus de métal. Vos données sont effectivement stockées sur ces plateaux. D'autres signaux se déplacent de lecture / écriture têtes de lecture ou d' écrire des données sur les plateaux. Ce mécanisme aussi précis qu'un humain cheveux ne pouvait même pas passer entre le têtes et plateaux tournants. Pourtant, tout cela fonctionne à des vitesses fantastiques. 

[FIN LECTURE VIDÉO] 

DAVID MALAN: Zoom en un peu plus profonde maintenant à ce qui est effectivement sur ces plateaux. 

[LECTURE VIDEO] 

-Voyons ce que nous venons vu au ralenti. Quand une brève impulsion de l'électricité est envoyé à la tête de lecture / écriture, si flips sur une petite électromagnétique pour une fraction de seconde. L'aimant crée un champ, qui change la polarité d'un minuscule, minuscule partie des particules métalliques qui manteau de chaque surface du plateau. 

Une série de motifs de ces minuscules, zones chargées plan sur le disque représente un seul bit d' les données dans le nombre binaire système utilisé par les ordinateurs. Maintenant, si le courant est envoyé dans un sens à travers la tête lecture / écriture, la zone est polarisée dans une direction. Si le courant est envoyé dans l' sens inverse, l' la polarisation est inversée. 

Comment vous obtenez des données depuis le disque dur? Juste inverser le processus. Ce sont donc les particules sur le disque qui obtiennent le courant dans le lecture / écriture en mouvement. Mettez-les ensemble des millions de ces segments magnétisés, et vous avez un fichier. 

Maintenant, les morceaux d'un fichier unique peut être dispersés sur un lecteur de plateaux, un peu comme le gâchis de papiers sur votre bureau. Ainsi, un fichier supplémentaire spécial conserve la trace d'où tout est. Ne vous aimeriez avoir quelque chose comme ça? 

[FIN LECTURE VIDÉO] 

DAVID MALAN: OK, probablement pas. Alors, combien d'entre vous les gars grandi avec ça? OK, donc c'est de moins en moins mains chaque année. Mais je suis contente que tu sois au moins familier avec eux, parce que cela et notre propre livre démo, malheureusement, sont en train de mourir d'une très une mort lente ici de familiarité. 

Mais c'est ce que j'ai, au moins, de retour en lycée, l'utilisation utilisé pour les sauvegardes. Et c'était incroyable, parce que vous pourrait stocker 1,4 mégaoctets sur ce disque donné. Et ce fut la version haute densité, comme indiqué par la HD, qui présente à-dire avant les vidéos HD d'aujourd'hui. 

Densité standard était de 800 kilo-octets. Et avant cela, il y avait Disques de 400 kilo-octets. Et avant cela, il y avait 5 et 1/4 disques pouces, qui étaient de véritables disquette, et un peu plus large et plus grand que ces choses ici. Mais vous pouvez réellement voir le soi-disant aspect disquette de ces disques. 

Et fonctionnellement, ils sont en fait assez similaire aux disques durs d'au moins ce type. Encore une fois, les SSD dans les ordinateurs les plus récents travailler un peu différemment. Mais si vous vous déplacez cette petite languette métallique, vous pouvez voir un petit biscuit, ou plateau. 

Ce n'est pas métallique comme celui-ci. Celui-ci est en fait quelque cher matière plastique. Et vous pouvez sorte de se tortiller. Et vous avez trully juste essuyé quelques nombre de bits ou de particules magnétiques à partir de ce disque. 

Donc, heureusement, il n'y a rien à ce sujet. Si cette chose est la façon - et couvre vos yeux et à ceux de votre voisin - il vous suffit de retirer ce genre de ensemble hors de la gaine comme ça. Mais il ya un petit ressort, donc conscient de cela avec vos yeux. Alors maintenant, vous avez vraiment une disquette. 

Et ce qui est remarquable au sujet de cette est que dans la mesure où il s'agit d'une représentation à petite échelle d'un plus grand disque dur, ces choses sont super, super simple. Si vous pincez le fond des choses, maintenant que que chose de métallique est éteint, et le zeste les ouvrir, tout ce qu'il ya, c'est deux morceaux de feutre et le disque soi-disant disquette avec une pièce de métal à l'intérieur. 

Et il en va de la moitié des le contenu de mon disque. Il en va de l'autre moitié d'entre eux. Mais c'est tout ce qui tournait à l'intérieur de votre ordinateur antan. 

Et encore une fois, de mettre cela en perspective, quelle est la taille maximum de votre disques durs de nos jours? 500 gigaoctets, un téraoctet, peut-être en un ordinateur de bureau, 2 téraoctets, 3 téraoctets, 4 téraoctets, non? Il s'agit d'un mégaoctet, donner ou prendre, qui ne peut même pas tenir un MP3 classique anymore ces jours-ci, ou certains fichier musical similaire. 

Donc, un petit souvenir pour vous aujourd'hui, et également pour aider à contextualiser ce nous allons prendre pour acquis maintenant problème posé cinq. Donc, ce sont à vous. Alors permettez-moi de transition à l'endroit où sera passer la prochaine pset ainsi. Donc, nous avons maintenant mis cette page pour - oh, quelques annonces rapidement. 

Ce vendredi, si vous souhaitez rejoindre CS50 pour le déjeuner, aller à l'endroit habituel, cs50.net/rsvp. Et projet final - si par le programme, nous avons mis en ligne le spécification du projet final déjà. Sachez que cela ne signifie pas c'est dû en particulier bientôt. Il a publié, vraiment, juste pour obtenir vous les gars y penser. Et en effet, un super-importante pourcentage d'entre vous sera s'attaque projets finaux sur le matériel que nous n'ont même pas appris à la classe, mais sera dès la semaine prochaine. 

Remarquez, cependant, que la spec appelle à quelques différents composants de l' projet final. La première, dans quelques semaines, est une pré-proposition, un e-mail assez décontracté pour votre TF pour lui dire ou ce que vous êtes réfléchir à votre projet, avec Pas d'engagement. Proposition sera votre particulier engagement, en disant: ici, c'est ce que Je voudrais faire pour mon projet. Qu'en pensez-vous? Trop gros? Trop petit? Est-il gérable? Et vous voyez les spécifications pour plus de détails. 

Quelques semaines après que le statut rapport, qui est une façon similaire email décontracté à votre TF-à-dire à quel point loin derrière vous êtes dans votre finale la mise en œuvre du projet, suivie d' le CS50 Hackathon à laquelle tout le monde est invité, qui sera un événement à partir de 20h00 un soir jusqu'à 07h00 H le lendemain matin. Pizza, comme je peux l'ai mentionné la semaine zéro, wil sera servi à 21h00, La nourriture chinoise à 01:00. Et si vous êtes encore éveillé à 5h00, nous vous emmènerons à IHOP pour le petit déjeuner. 

Ainsi, le Hackathon est l'un des plus des expériences mémorables dans la classe. Ensuite, la mise en œuvre est due, et puis l'apogée CS50 Foire. Plus de détails sur tous ces dans les semaines à venir. 

Mais revenons à quelque chose vieille école - encore une fois, un tableau. Donc, un tableau était belle, parce qu'elle n'en résout problèmes comme nous avons vu qu'un Il ya actuellement des structures d'étudiants obtenir un peu hors de contrôle si nous veulent avoir un élève, étudiant deux, étudiant trois, étudiant dot dot dot, un nombre arbitraire d'étudiants. 

Donc, les tableaux, il ya quelques semaines, fondit en et résolu tous nos problèmes de pas savoir à l'avance combien de choses de quelque type que nous pourrions souhaiter. Et nous avons vu que struct peuvent nous aider mieux organiser notre code et le garder variables conceptuellement similaires, comme un nom et une maison, ensemble, de sorte que nous peut les traiter comme une seule entité à l'intérieur qui sont au nombre de plus petits morceaux. 

Mais tableaux présentent certains inconvénients. Quels sont certains des inconvénients Nous avons rencontré avec des tableaux jusqu'à présent? Qu'est-ce que c'est? Taille fixe - même si bien que vous pourriez être en mesure d'allouer de la mémoire pour une tableau, une fois que vous savez combien d'étudiants vous avez, combien de caractères que vous avez de l'utilisateur, une fois que vous avez alloué le tableau, vous avez genre de peinture vous dans un coin. 

Parce que vous ne pouvez pas insérer de nouveaux éléments dans le milieu d'un tableau. Vous ne pouvez pas insérer d'autres éléments à la fin d'un tableau. Vraiment, vous devez recourir à la création d'un tout nouveau tableau, comme nous en avons discuté, la copie de l'ancien dans le nouveau. Et encore une fois, c'est le mal de tête qui GetString traite pour vous. 

Mais encore une fois, vous ne pouvez même insérer quelque chose dans le milieu du tableau si le taux n'est pas entièrement rempli. Par exemple, si ce tableau ici de taille six seulement a cinq choses en elle, Eh bien, vous pouvez simplement virer quelque chose sur la fin. Mais que faire si vous voulez insérer quelque chose dans le milieu de l' tableau, même si cela peut avoir cinq des six choses en elle? 

Eh bien, qu'avons-nous faire quand nous avions tous de nos volontaires humains en scène semaines passé? Si nous voulions mettre quelqu'un ici, que ce soit ces gens comment faire avancer ce chemin, ou à ces gens comment faire avancer ce Ainsi, et qui est devenu cher. Le déplacement de personnes à l'intérieur d'un ensemble fini d'ajouter et coûtant nous le temps, donc beaucoup de notre n carré les temps de parcours comme le tri par insertion, pour Ainsi, dans le pire des cas. Alors tableaux sont grands, mais vous devez savez à l'avance la taille que vous voulez. 

Alors OK, voici une solution. Si je ne sais pas à l'avance combien d' étudiants que je pourrais avoir, et je sais une fois Je décide, cependant, je suis coincé avec qui de nombreux étudiants, pourquoi ne pas simplement toujours allouer le double d'espace que je pourrais penser que je dois? N'est-ce pas une solution raisonnable? 

De façon réaliste, je ne pense pas que nous sommes va avoir besoin de plus de 50 emplacements dans un tableau d'une classe moyenne taille, donc on va plutôt Round Up. Je vais faire 100 emplacements dans mon tableau, juste de sorte que nous pouvons certainement obtenir l' nombre d'étudiants, je m'attends à être dans une certaine classe de taille moyenne. Alors pourquoi ne pas rassembler et d'allouer plus de mémoire, typiquement, pour un tableau que vous pensez que vous pourriez même avoir besoin? Qu'est-ce que c'est facile refoulement à cette idée? 

Vous êtes en train de perdre la mémoire. Littéralement chaque programme que vous écrivez ensuite est peut-être en utilisant deux fois plus de mémoire que vous avez réellement besoin. Et c'est juste ne se sent pas comme un particulièrement solution élégante. De plus, il diminue juste le probabilité d'un problème. S'il vous arrive d'avoir un cours très populaire un semestre et vous avez 101 étudiants, le programme est encore face fondamentalement la même question. 

Donc, heureusement, il ya une solution à cette annonce à tous nos problèmes dans la forme des structures de données qui sont plus complexes que ceux nous avons vu jusqu'à présent. C'est, je prétends, c'est une liste chaînée. Il s'agit d'une liste de numéros - 9, 17, 22, 26, et 34 - qui ont été reliés entre eux par l'intermédiaire de ce que j'ai dessiné des flèches. 

En d'autres termes, si je voulais représenter un tableau, je pourrais faire quelque chose comme ça. Et je vais mettre cela sur le dessus dans un instant. Je pouvais faire - bonjour, tout droit. Stand by. Nouvel ordinateur ici, clair - Très bien. 

Donc, si j'ai ces chiffres dans le tableau - 9, 17, 22, 26, 24 - pas nécessairement à l'échelle. Bon, alors voici mon tableau - oh mon dieu. Bon, alors voici mon tableau. Oh mon dieu. 

[Rires] 

DAVID MALAN: Pretend. C'est trop d'effort pour revenir et corriger cela, il ya - 26. Nous avons donc cette série de 9, 17, 22, 26, et 34. Pour ceux d'entre vous peut voir l' erreur embarrassante Je viens de faire, il est là. 

Donc, je prétends que c'est une solution très efficace. J'ai réparti comme beaucoup ints que J'ai besoin - un, deux, trois, quatre, cinq ou six - et j'ai ensuite stocké les numéros à l'intérieur de cette matrice. Mais supposons, alors, je veux insérer une valeur comme le numéro 8? Alors, où faut-il aller? Supposons que je veux insérer un nombre identique 20. Alors, où faut-il aller? Quelque part au milieu, ou le nombre 35 doit aller quelque part à la fin. Mais je suis tout à fait hors de l'espace. 

Et c'est donc un enjeu fondamental des tableaux qui ne sont la solution. J'ai réclamé il ya un instant, GetString résout ce problème. Si vous souhaitez insérer un sixième numéro dans cette matrice, ce qui est au moins l'un Solution Vous pouvez retomber sur pour sûr, comme nous le faisons avec GetString? Qu'est-ce que c'est? 

Eh bien, le rendre plus grand est plus facile à dire qu'à faire. Nous ne pouvons pas nécessairement faire le tableau plus grand, mais que pouvons-nous faire? Faire un nouveau tableau qui est plus grand, de taille 6, ou peut-être la taille 10, si nous voulons de devancer les choses, puis copiez l'ancien tableau dans le nouveau, puis libérer l'ancien tableau. 

Mais quelle est la durée maintenant de ce processus? Il est grand O n, parce que la copie va vous coûter quelques unités de temps, donc pas idéal si nous devons allouer un nouveau tableau, qui va à consommer deux fois plus mémoire temporaire. Copiez neuf avec du vieux - Je veux dire, c'est juste un mal de tête, qui est, encore une fois, pourquoi nous avons écrit GetString pour vous. 

Alors, que pouvons-nous faire à la place? Eh bien, si notre structure de données a effectivement des lacunes en elle? Supposons que je relâche mon objectif d'avoir blocs contigus de mémoire, où 9 est juste à côté de 17, ce qui est juste à côté de 22, et ainsi de suite. 

Et supposons que 9 peut être ici en RAM, et 17 peuvent être ici en RAM, et 22 peut être plus ici dans la RAM. En d'autres termes, je n'ai pas besoin d'eux même dos à dos plus. Je dois juste quelque sorte enfiler une aiguille à travers chacun de ces nombres, ou chaque de ces nœuds, que nous appellerons l' rectangles comme je l'ai tiré les vers, rappeler comment se rendre à la dernière un tel noeud de la première. 

Alors, quelle est la construction de programmation nous avons vu tout récemment avec qui je peut mettre en œuvre ce thread, ou dessiné ici, avec qui je peux mettre en œuvre ces flèches? Pointeurs Donc, pas vrai? Si je allouer pas seulement un int, mais un nœud - et par noeud, je veux juste conteneur. Et visuellement, je veux dire un rectangle. Ainsi, un nœud doit apparemment pour contenir deux valeurs - l'int lui-même, et puis, comme le laisse entendre la moitié inférieure du rectangle, assez d'espace pour un int. 

Il suffit donc de penser à l'avenir ici, quelle est la taille de ce nœud, ce récipient en question? Combien d'octets pour l'int? Vraisemblablement 4, si ce n'est le même que d'habitude. Et puis, combien d'octets pour le pointeur? 4. Donc ce conteneur, ou ce nœud, est va être une structure de 8 octets. Oh, et c'est une heureuse coïncidence que nous avons introduit cette notion de une structure ou une structure C. 

Donc, je prétends que je veux prendre une étape vers cette plus sophistiqué mise en oeuvre d'une liste de numéros, un liste chaînée de chiffres, je dois faire un peu plus de réflexion à l'avant et déclarer non seulement un int, mais une struct que je vais l'appeler, de façon classique ici, noeud. Nous pourrions l'appeler tout ce que nous voulons, mais nœud va être thématique dans beaucoup des choses que nous commençons à examiner maintenant. 

A l'intérieur de ce noeud est un int n. Et puis, cette syntaxe, un peu bizarre au premier abord - struct noeud * à côté. Eh bien imagée, c'est quoi? C'est la moitié inférieure de le rectangle que nous avons vu Il ya juste un moment. 

Mais pourquoi dis-je struct noeud * plutôt que de simplement noeud *? Parce que si ce pointeur pointe sur un autre nœud, c'est juste l' l'adresse d'un noeud. C'est conforme à ce que nous avons discuté de pointeurs jusqu'à présent. Mais pourquoi, si je revendique cette structure est appelé nœud, dois-je dire struct nœud à l'intérieur ici? 

Exactement. C'est en quelque sorte une réalité stupide de C. Le typedef, pour ainsi dire, n'a pas encore arrivé. C est super littéral. Il lit votre code de recharge à bas, de gauche à droite. Et jusqu'à ce qu'il frappe qui virgule sur la ligne de fond, devinez ce qui ne exister en tant que type de données? Noeud, noeud entre guillemets. 

Mais en raison de la plus verbeux déclaration que j'ai faite sur la première ligne - noeud struct typedef - parce que cela est venu en premier, avant l' accolades, c'est un peu comme pré-éduquer Clang que vous connaître, donnez-moi une struct appelé nœud de structure. Franchement, je n'aime pas les choses d'appel struct noeud, struct noeud tout tout au long de mon code. Mais je ne l'utilise une fois, juste à l'intérieur, afin que je puisse efficacement créer une sorte de référence circulaire, non un pointeur vers moi en soi, mais un pointeur vers un autre de un type identique. 

Ainsi, il s'avère que sur une structure de données comme ça, il ya quelques les opérations qui pourraient être d'intérêt pour nous. Nous pourrions insérer dans une liste comme ça. Nous pourrions vouloir supprimer à partir d'une liste de ce genre. Nous pourrions vouloir consulter la liste pour un valeur, ou, plus généralement, traverse. Et traverse est juste une façon élégante de disant départ à gauche et déplacer tous le chemin vers la droite. 

Et remarquez, même avec cette légèrement plus structure de données sophistiqué, laissez- me propose que nous pouvons emprunter quelques-uns des les idées des deux dernières semaines et mettre en œuvre une fonction appelée chercher comme ça. Il va retourner true ou faux, indiquant, oui ou non, n est compris dans la liste. Son second argument est un pointeur à la liste lui-même, de sorte qu'une pointeur à un noeud. 

Tout ce que je vais ensuite faire est de déclarer une variable temporaire. Nous l'appellerons ptr par convention, pour pointer. Et je lui assigner égale à la au début de la liste. 

Et maintenant remarquer la boucle while. Tant que le pointeur n'est pas égal null, je vais vérifier. Est pointeur flèche n égal à le n qui a été adoptée en? Et attendez une minute - nouveau morceau de syntaxe. Qu'est-ce que la flèche tout d'un coup? Ouais? 

Exactement. Donc, alors qu'il ya quelques minutes, nous avons utilisé la notation par points pour accéder à quelque chose à l'intérieur d'un de la structure, si la variable vous avez n'est pas la struct lui-même, mais un pointeur vers une struct, Heureusement, un morceau de syntaxe finalement logique intuitive. La flèche signifie suivre le pointeur, comme nos flèches signifient généralement imagée et aller à le champ de données à l'intérieur. Alors flèche est la même chose que dot, mais vous utilisez quand vous avez un pointeur. 

Donc, pour récapituler puis, si le champ n à l'intérieur de la structure appelé pointeur égal à égal n, retourner vrai. Sinon, cette ligne ici - pointeur égaux pointeur suivante. Donc ce que cela fait, avis, c'est que si je je suis actuellement en montrant la struct contenant 9 et 9 n'est pas le numéro Je suis à la recherche - suppose que je suis à la recherche pour n égal à 50 - Je vais mettre à jour mon pointeur temporaire de ne pas remarquer à ce noeud plus, mais pointeur flèche à côté, ce qui va me mettre ici. 

Maintenant, j'ai réalisé un tourbillon mise en place. Le mercredi, nous allons effectivement faire ce avec certains humains et avec un peu plus Code à un rythme plus lent. Mais se rendre compte, nous sommes en train de faire nos données structures plus complexes afin que notre algorithmes peuvent devenir plus efficace, qui va être nécessaire pour pset six ans, lorsque nous chargeons en, encore une fois, ceux 150.000 mots, mais il faut le faire efficacement, et idéalement, créer un programme qui fonctionne pour nos utilisateurs de ne pas en linéaire, hors de n au carré, mais dans constante de temps, dans l'idéal. 

Nous vous verrons mercredi. 

Président: À la prochaine CS50, David oublie son scénario de base. 

DAVID MALAN: Et c'est comme ça que vous envoyez des messages texte avec C. Que le - 

[MESSAGE TEXTE DIVERS Sons de notification]