[Powered by Google Translate] [Semaine 4] [David J. Malan] [Université de Harvard] [C'est CS50.] [CS50.TV] D'accord, ce n'est CS50, et c'est le début de la semaine 4, et c'est l'un des algorithmes de tri plus lente possible. Lequel est-ce que nous venons de regarder là-bas? C'était en quelque sorte de bulle, dans le grand ordre O (n ^ 2) + somme, et en effet nous ne sommes pas les seuls dans ce monde à l'air de savoir ce tri à bulles est ou sa durée. En effet, il s'agissait d'une interview d'Eric Schmidt de Google et l'ancien sénateur Barack Obama seulement il ya quelques années. Maintenant, sénateur, vous êtes ici chez Google, et j'aime à penser de la présidence comme un entretien d'embauche. Maintenant, il est difficile d'obtenir un emploi en tant que président, et vous allez à travers les rigueurs maintenant. Il est également difficile d'obtenir un emploi chez Google. Nous avons des questions, et nous demandons à nos questions aux candidats, et celui-ci est de Larry Schwimmer. Les gars, vous pensez que je plaisante? C'est juste ici. Quel est le moyen le plus efficace de trier un million entiers 32 bits? [Rires] Bien- Je suis désolé. >> Non, non, non, non. Je pense que le tri à bulles serait la bonne façon de faire. Allez, qui lui a dit cela? La semaine dernière, rappelons nous avons pris une pause de code, au moins pour une journée, et a commencé à se concentrer sur quelques idées de plus haut niveau et de résolution de problèmes plus généralement dans le contexte de la recherche et de tri, et nous avons introduit quelque chose que nous n'avons pas frapper ce nom la semaine dernière, mais la notation asymptotique, le Big O, l'Oméga Big, et parfois la notation Big Theta, et ceux-ci étaient simplement des moyens de décrire le temps d'exécution des algorithmes, combien de temps cela prend pour un algorithme afin de fonctionner. Et vous vous souviendrez que vous avez parlé du temps de fonctionnement en fonction de la taille de l'entrée, que nous appelons généralement n, quel que soit le problème peut être, où n est le nombre de personnes dans la pièce, le nombre de pages d'un livre de téléphone, et nous avons commencé à écrire des choses sur comme O (n ^ 2) ou O (n) ou O (n log n), et même si le calcul n'a pas tout à fait si parfaitement et il était n ² - n / 2 ou quelque chose comme ça nous aurions plutôt que simplement jeter quelques-uns des termes d'ordre inférieur, et la motivation n'y est que nous voulons vraiment une sorte de manière objective d'évaluer l'exécution des programmes ou de la performance des algorithmes que, à la fin de la journée n'a rien à voir, par exemple, avec la vitesse de votre ordinateur aujourd'hui. Par exemple, si vous implémentez tri à bulles, ou vous mettre en œuvre le tri par fusion tri ou de sélection sur l'ordinateur d'aujourd'hui, un ordinateur de 2 GHz, et que vous l'exécutez, et il faut un certain nombre de secondes, l'année prochaine il ya un 3 GHz ou un ordinateur 4 GHz, et vous pourriez alors prétendre que "Wow, mon algorithme est maintenant deux fois plus vite », alors qu'en réalité, ce n'est évidemment pas le cas. C'est juste que le matériel a obtenu plus rapidement, mais votre ordinateur n'a pas, et si nous voulons vraiment jeter des choses comme multiples de 2 ou un multiple de 3 quand il s'agit de décrire les la rapidité ou la lenteur est un algorithme et vraiment se concentrer uniquement sur n ou un facteur de celui-ci, un certain pouvoir de celui-ci comme dans le cas des sortes de la semaine dernière. Et rappelons que, avec l'aide du tri par fusion nous avons pu faire beaucoup mieux que tri à bulles et tri par sélection et même le tri par insertion. Nous sommes descendus à n log n, et encore une fois, Rappelons que log n désigne généralement quelque chose qui grandit plus lentement alors n, alors n log n jusqu'ici était bon car il était inférieur à n ². Mais pour parvenir à n log n avec tri par fusion ce qui était le germe d'une idée de base que nous avons eu à effet de levier que nous avons également mobilisé de retour à la semaine 0? Comment avons-nous aborder le problème du tri habilement avec tri par fusion? Quelle a été la clé de vision, peut-être? N'importe qui. Bon, prenons un peu de recul. Décrivez le tri par fusion dans vos propres mots. Comment at-elle fonctionné? Bon, nous allons ramer à 0 par semaine. Ok, ouais. [Inaudible étudiant] Bon, bon, si nous avons divisé le tableau de nombres en 2 pièces. Nous avons classé chacun de ces morceaux, et on les fusionne, et nous avons vu cette idée avant de prendre un problème qui est ce grand et hacher dans un problème qui est ce gros ou grand comme ça. Rappelons l'exemple du livre de téléphone. Rappelons l'algorithme d'auto-comptage des semaines, tri afin de fusionner a été résumée par cette pseudo ici. Lorsque vous avez donné n éléments, d'abord c'était test de cohérence. Si n <2, alors ne rien faire du tout parce que, si n <2, alors n est égal à 0 ou 1 évidemment, et donc si c'est 0 ou 1 il n'y a rien à trier. Vous avez terminé. Votre liste est déjà triée trivialement. Mais sinon, si vous avez 2 ou plusieurs éléments aller de l'avant et de les diviser en 2 moitiés, gauche et droite. Trier chacune de ces moitiés, puis de fusionner les deux moitiés triés. Mais le problème ici est que, à première vue, cela se sent comme si nous étions en barque. Il s'agit d'une définition circulaire que si je vous ai demandé de trier ces n éléments et vous me dites "Bon, d'accord, nous allons trier les éléments n / 2 et ceux n / 2," alors ma prochaine question va être «Très bien, comment voulez-vous trier les n / 2 éléments?" Mais en raison de la structure de ce programme, parce qu'il ya ce scénario de base, pour ainsi dire, ce cas particulier, qui dit que si n est > Sara, tout droit. Kelly. >> Kelly et? Willy. >> Willy, Sara, Kelly et Willy. En ce moment, j'ai posé la question par quelqu'un d' combien de personnes sont en place sur cette scène, et je n'ai aucune idée. Il s'agit d'une très longue liste, et ainsi de la place, je vais faire ce truc. Je vais demander à la personne à côté de moi pour faire la plupart du travail, et une fois qu'elle se fait faire le gros du travail Je vais faire le moins de travail possible et juste ajouter 1 à ce que sa réponse est, alors allons-y. On m'a demandé combien de personnes sont sur scène. Combien de personnes sont sur scène à gauche de vous? La gauche de moi? >> D'accord, mais ne triche pas. C'est bon, c'est bon, mais si nous voulons continuer dans cette logique supposons que vous voulez même au pays de Pount ce problème à la gauche de vous, alors plutôt que de répondre directement aller de l'avant et juste renvoyer la balle. Oh, combien de personnes se trouvent à gauche de moi? Combien de personnes sont à gauche? 1. [Rires] Ok, donc 0, de sorte que maintenant Willy a fait est que vous avez retourné votre réponse ce sens en disant 0. Maintenant, que devez-vous faire? >> 1. Bon, vous êtes le 1, si vous dites: «Bon, je vais ajouter 1 à tout ce qui compte Willy était: «si 1 + 0. Vous êtes maintenant 1 pour votre réponse à la droite est désormais 1. >> Et le mien serait de 2. Bon, si vous prenez la réponse précédente de 1, ajoutant la quantité minimale de travail que vous voulez faire, ce qui est de +1. Vous avez maintenant 2, et que vous me remettre quelle valeur? 3, je veux dire, je suis désolé, 2. Bon. Eh bien, nous avons eu 0 à gauche. Puis nous avons eu 1, puis on ajoute 2, et maintenant tu me donnant le numéro 2, et si ce que je dis, ok, +1, 3. Il ya en effet 3 personnes debout à côté de moi sur cette scène, de sorte que nous aurions pu évidemment fait cela très linéaire, beaucoup de la façon évidente, mais qu'avons-nous vraiment faire? Nous avons pris un problème de taille 3 initialement. Nous avons ensuite il est tombé en panne à un problème de taille 2, alors un problème de taille 1, et enfin le scénario de base C'était vraiment, oh, il n'y a personne là-bas, à quel point Willy revint effectivement une réponse codée en dur une couple de fois, et le second a ensuite fait barboter jusqu'à, barboter, barboter, puis en ajoutant dans ce 1 un supplémentaire nous avons mis en œuvre cette idée de base de la récursivité. Maintenant, dans ce cas, il n'a pas vraiment résoudre un problème plus efficace alors que nous avons vu jusqu'à présent. Mais pensez à les algorithmes que nous avons fait sur scène ce jour. Nous avons eu 8 morceaux de papier sur le tableau noir, sur la vidéo quand Sean était à la recherche pour le numéro 7, et qu'at-il vraiment faire? Eh bien, il n'a pas fait n'importe quel type de diviser pour régner. Il n'a pas fait n'importe quel type de récursivité. Au contraire, il vient de faire cet algorithme linéaire. Mais lorsque nous avons lancé l'idée de numéros triés sur scène en direct la semaine dernière puis nous avons eu cet instinct d'aller vers le centre, à quel point nous avons eu une petite liste de taille 4 ou d'une autre liste de taille 4, et puis nous avons eu exactement le même problème, donc nous avons répété, répété, répété. En d'autres termes, nous recursed. Merci beaucoup à nos 3 bénévoles ici pour démontrer la récursivité avec nous. Voyons voir si nous ne pouvons pas faire cela maintenant un peu plus concrète, résoudre un problème nouveau que nous pouvions faire assez facilement, mais nous allons l'utiliser comme un tremplin pour la mise en œuvre de cette idée de base. Si je veux calculer la somme d'une série de chiffres, Par exemple, si vous passez dans le numéro 3, Je veux vous donner la valeur de sigma 3, de sorte que la somme de 3 + 2 + 1 + 0. Je veux revenir la réponse 6, donc nous allons implémenter cette fonction sigma, cette fonction de sommation que, de plus, prend en entrée, puis retourne la somme de ce nombre tout en bas à 0. Nous pourrions le faire assez simplement, non? Nous pourrions le faire avec une sorte de structure en boucle, alors laissez-moi aller de l'avant et obtenir cela a commencé. Inclure stdio.h. Permettez-moi de me mettre en principal de travailler ici. Sauvons ce que sigma.c. Alors je vais aller ici, et je vais déclarer un int n, et je vais faire ce qui suit pendant que l'utilisateur ne coopère pas. Pendant que l'utilisateur ne m'a pas donné un nombre positif laissez-moi aller de l'avant et de les inviter pour n = getInt, et permettez-moi de donner quelques instructions sur ce qu'il faut faire, de sorte printf ("Entier positif s'il vous plaît"). Juste une chose relativement simple comme celui-ci de sorte qu'au moment où nous avons atteint la ligne 14 nous avons maintenant un nombre entier positif sans doute au n. Maintenant, nous allons faire quelque chose avec elle. Permettez-moi aller de l'avant et de calculer la somme, alors int somme = sigma (n). Sigma est juste sommation, alors je vais juste écrire dans l'amateur moyen. Nous allons l'appeler sigma là. C'est la somme, et maintenant je vais imprimer le résultat, printf ("La somme est% d \ n", somme). Et puis je vais retourner 0 pour faire bonne mesure. Nous avons fait tout ce que ce programme nécessite l'exception de la partie la plus intéressante, qui est en fait de mettre en œuvre la fonction sigma. Permettez-moi de descendre ici vers le bas, et laissez-moi déclarer la fonction sigma. Il faut que ça prend une variable qui est de type entier, et quel type de données que je veux revenir sans doute à partir de sigma? Int, parce que je veux qu'il corresponde à mes attentes sur la ligne 15. Ici laissez-moi aller de l'avant et de mettre en œuvre cette d'une manière assez simple. Allons de l'avant et de dire la somme int = 0, et maintenant je vais avoir un peu de boucle ici qui va dire quelque chose comme ça, for (int i = 0; I <= nombre; i + +) somme + = i. Et puis je vais revenir somme. J'aurais pu en œuvre cette dans un certain nombre de façons. J'aurais pu utiliser une boucle while. J'aurais pu sauter en utilisant la variable somme si je voulais vraiment, mais en bref, nous avons seulement une fonction que si je n'ai pas gaffe déclare somme est 0. Puis il parcourt de 0 sur place par le nombre, et sur chaque itération, il ajoute que la valeur actuelle de la somme, puis retourne la somme. Maintenant, il ya une légère optimisation ici. C'est probablement une étape gaspillée, mais ainsi soit-il. C'est très bien pour l'instant. Nous sommes au moins d'être approfondie et va 0 tout le chemin sur un maximum. Pas très dur et assez simple, mais il s'avère que la fonction sigma nous avons la possibilité même comme nous l'avons fait ici sur scène. Sur la scène que nous venons compté combien de personnes étaient à côté de moi, mais si l'on voulait compter le nombre 3 + 2 + 1 sur le bas à 0 que nous pouvions même plate à une fonction que je vais plutôt décrire comme étant récursif. Ici, nous allons faire un rapide check santé mentale et assurez-vous que je n'ai pas gaffe. Je sais qu'il ya au moins une chose dans ce programme que je n'ai fait de mal. Quand j'ai frappé entrer vais-je obtenir toute sorte de me crier dessus? Que vais-je faire engueuler à propos? Ouais, j'ai oublié le prototype, donc je suis en utilisant une fonction appelée sigma sur la ligne 15, mais ce n'est pas déclaré avant la ligne 22, donc je meilleure façon proactive monter ici et de déclarer un prototype, et je dirai int sigma (nombre entier), et c'est tout. Il est mis en œuvre par le bas. Ou d'une autre façon, je pouvais résoudre ce problème, Je pourrais passer la fonction de là-haut, ce qui n'est pas mauvais, mais au moins quand vos programmes commencent à devenir long, franchement, Je pense qu'il ya une certaine valeur en ayant toujours principal en haut de sorte que vous dans le lecteur peut ouvrir le fichier et puis tout de suite voir ce que le programme fait sans avoir à chercher dans l' la recherche de cette fonction principale. Descendons à ma fenêtre de terminal ici, essayez de faire sigma sigma faire, et j'ai foiré ici aussi. Déclaration implicite de la fonction getInt signifie que j'ai oublié de faire quoi d'autre? [Inaudible étudiant] Bon, donc apparemment une erreur commune, nous allons donc mettre ce là-haut, cs50.h, et maintenant, revenons à ma fenêtre de terminal. Je vais effacer l'écran, et je vais relancer faire sigma. Il semble avoir compilé. Laisse-moi courir sigma. Je vais saisir le numéro 3, et je n'ai obtenez 6, donc pas un contrôle rigoureux, mais au moins il semble fonctionner à première vue, mais maintenant nous allons le déchirer, et nous allons tirer parti de fait l'idée de la récursivité, encore une fois, dans un contexte très simple de sorte que dans quelques semaines " quand nous commençons à explorer les structures de données plus fantaisistes que les tableaux nous avons un autre outil dans la boîte à outils avec lesquels manipuler ces structures de données comme nous le verrons. C'est l'approche itérative, l'approche à base de boucles. Permettez-moi maintenant plutôt le faire. Permettez-moi de dire à la place que la somme du nombre sur le bas à 0 est vraiment la même chose que + numéro sigma (nombre - 1). En d'autres termes, tout comme sur scène, je comptèrent sur le hasard pour chacune des personnes à côté de moi, et à leur tour en barque maintenu jusqu'à ce que nous touché le fond à Willy, qui a dû retourner une réponse codée en dur comme 0. Voici maintenant nous sommes même barque au sigma la même fonction que s'appelait à l'origine, mais l'idée fondamentale ici est que nous ne demandons pas sigma identique. Nous ne sommes pas passer au n. Nous sommes clairement en passant en nombre - 1, si un problème un peu plus petit, un peu plus petit problème. Malheureusement, ce n'est pas tout à fait une solution encore, et avant de nous fixons ce qui pourrait être sauter aussi évident à certains d'entre vous laissez-moi aller de l'avant et réexécutez: make. Il semble compiler bien. Permettez-moi de relancer sigma avec 6. Oups, permettez-moi de relancer sigma avec 6. Nous avons vu cela avant, mais le temps accidentellement dernière aussi. Pourquoi ai-je cette erreur de segmentation cryptique? Ouais. [Inaudible étudiant] Il n'y a aucun cas de base, et plus précisément, ce qui est probablement arrivé? Il s'agit d'un symptôme de ce comportement? Dites-le un peu plus fort. [Inaudible étudiant] C'est une boucle infinie efficace, et le problème avec les boucles infinies quand elles impliquent la récursivité dans ce cas, une fonction qui se fait appeler, ce qui se passe à chaque fois que vous appelez une fonction? Eh bien, pensez à la façon dont nous avons établi la mémoire dans un ordinateur. Nous avons dit qu'il ya ce morceau de mémoire appelée la pile qui se trouve en bas, et chaque fois que vous appelez une fonction de mémoire un peu plus se mettre sur cette dite pile contenant des variables locales de cette fonction ou de paramètres, si sigma sigma sigma appelle des appels appelle sigma  appelle sigma où vient cette fin de l'histoire? Eh bien, il finit par le montant total des dépassements de mémoire dont vous disposez sur votre ordinateur. Vous envahi le segment que vous êtes censé rester à l'intérieur, et vous obtenez cette erreur de segmentation, core dumped, et ce core dumped signifie, c'est que j'ai maintenant un fichier appelé core qui est un fichier contenant des zéros et des uns qui fait à l'avenir sera utile au diagnostic. Si ce n'est pas évident pour vous où votre bogue est vous pouvez réellement faire un peu d'analyse médico-légale, pour ainsi dire, sur ce fichier core dump, ce qui, encore une fois, c'est juste un tas de zéros et de uns qui représente l'essentiel de l'état de votre programme dans la mémoire le moment où il s'est écrasé dans cette voie. La solution ici est que nous ne pouvons pas aveuglément retourner sigma, le nombre + sigma d'un problème légèrement plus petit. Nous avons besoin d'une sorte de scénario de base ici, et quel devrait être le cas de base sans doute? [Inaudible étudiant] Bon, tant que le nombre est positif nous devrions renvoyer ce, ou, autrement dit, si le nombre est, par exemple, <= à 0 vous savez quoi, je vais aller de l'avant et retourner 0, un peu comme Willy a fait, et le reste, je vais aller de l'avant et retourner ce, donc ce n'est pas que beaucoup plus courte que la version itérative que nous attisé la première utilisation d'une boucle for, mais remarquez qu'il ya cette sorte d'élégance à elle. Au lieu de renvoyer un certain nombre et l'exécution de toutes ces maths et en ajoutant les choses avec des variables locales vous êtes au lieu dit «Bon, si c'est un problème très facile, comme le nombre est <0, permettez-moi de revenir immédiatement à 0. " Nous n'allons pas prendre la peine de soutien nombres négatifs, donc je vais coder en dur la valeur de 0. Mais sinon, pour mettre en œuvre cette idée de sommation tous ces chiffres ensemble, vous pouvez effectivement prendre une petite bouchée sortir de ce problème, tout comme nous l'avons fait ici, sur scène, ensuite botté le reste du problème à la personne suivante, mais dans ce cas la prochaine personne, c'est vous. C'est une fonction portant le même nom. Il suffit de passer ce un problème de plus en plus petits et plus petits à chaque fois, et même si nous n'avons pas des choses assez formalisées dans le code ici c'est exactement ce qui se passait à la semaine 0 avec l'annuaire. C'est exactement ce qui se passait dans les dernières semaines avec Sean et avec nos démonstrations de chercher des numéros. C'est en prenant un problème et en le divisant encore et encore. En d'autres termes, il existe un moyen maintenant de traduire cette construction du monde réel, ce concept de niveau supérieur de diviser pour régner et faire quelque chose de nouveau et de nouveau dans le code, donc c'est quelque chose que nous verrons à nouveau au fil du temps. Maintenant, en passant, si vous êtes nouveau récurrence que vous devriez au moins savoir maintenant pourquoi c'est drôle. Je vais aller à google.com, et je vais chercher quelques trucs et astuces sur la récursivité, entrez. Dites à la personne à côté de vous si elles n'étaient pas rire tout à l'heure. Vouliez-vous dire récursion? Vouliez-vous dire, ah, voilà. Bon, maintenant que c'est le reste du monde. Un oeuf de Pâques peu intégré quelque part dans Google. Soit dit en passant, l'un des liens que nous mettons sur le site Web du cours d'aujourd'hui est tout simplement cette grille de différents algorithmes de tri, certaines d'entre elles, nous avons examiné la semaine dernière, mais ce qui est bien à propos de cette visualisation que vous essayez d'envelopper votre esprit autour de diverses choses liées à des algorithmes sachez que vous pouvez très facilement maintenant commencer avec différents types d'entrées. Les entrées inversée toutes les entrées triées surtout, les entrées aléatoire et ainsi de suite. Comme vous tenter, encore une fois, la distinction entre ces choses dans votre esprit se rendre compte que cette URL sur le site Web du cours sur la page Conférences pourrait vous aider à raison par certains d'entre eux. Aujourd'hui, nous arrivons finalement à résoudre le problème depuis un certain temps, qui était que cette fonction d'échange n'a pas fonctionné, et quel était le problème fondamental de ce swap fonction, dont le but était, encore une fois, d'échanger une valeur ici et ici de sorte que ce qui se passe? Cela n'a pas réellement. Pourquoi? Ouais. [Inaudible étudiant] Justement, l'explication de cette bugginess tout simplement parce que lorsque vous appelez des fonctions en C et ces fonctions prennent des arguments, comme a et b ici, vous êtes de passage dans les copies de n'importe quelle valeur que vous fournissez à cette fonction. Vous ne fournissent pas les valeurs d'origine eux-mêmes, donc nous avons vu cela dans le contexte de buggyc, buggy3.c, qui avait l'air un petit quelque chose comme ça. Rappelez-vous que nous avons eu x et y initialisé à 1 et 2, respectivement. Nous avons ensuite imprimée sur ce qu'ils étaient. J'ai alors déclaré que je les échanger par téléphone au swap de x, y. Mais le problème était que l'échange a travaillé, mais seulement dans le cadre de l'échange lui-même fonctionner. Dès que nous avons atteint la ligne 40 de ces valeurs échangées ont été jetés, et donc rien dans l'origine la principale fonction était réellement changé du tout, donc si vous pensez à l'époque à quoi cela ressemble sur le plan de notre mémoire si ce côté gauche de la carte représente- et je ferai de mon mieux pour tout le monde de voir ce si celui-ci côté gauche de la carte représente, par exemple, votre mémoire vive, et la pile va se développer sur de cette façon, et que nous appelons une fonction comme principal et principal dispose de 2 variables locales x et y, nous allons décrire ceux que x ici, et nous allons les décrire comme y ici, et il faut mettre dans les valeurs 1 et 2, si ce n'est ici principal, et quand principale appelle la fonction d'échange du système d'exploitation donne la fonction de permutation son propre andain de mémoire sur la pile, son propre cadre sur la pile, pour ainsi dire. Elle alloue également 32 bits pour ces ints. Il arrive de les appeler a et b, mais c'est totalement arbitraire. Il aurait pu les appelait tout ce qu'il veut, mais ce qui arrive quand principale Swap appels est qu'il faut ce 1, place une copie là, il met une copie. Il ya 1 autre variable locale dans la pagination, mais, s'appelle comment? >> Tmp. Tmp, alors laissez-moi me donner un autre 32 bits ici, et qu'est-ce que je fais dans cette fonction? J'ai dit tmp int obtient un, donc un a 1, ce que j'ai fait lorsque nous avons joué la dernière fois avec cet exemple. Ensuite, un obtient b, alors b est 2, alors maintenant cela devient 2, et maintenant b obtient temp, temp est donc 1, alors maintenant b devient cela. C'est très bien. Il a travaillé. Mais dès que la fonction retourne mémoire swap disparaît de manière efficace afin qu'il puisse être réutilisé par une autre fonction dans le futur, et principal est bien évidemment totalement inchangé. Nous devons trouver un moyen de résoudre ce problème fondamental, et aujourd'hui, nous allons enfin avoir un moyen de le faire où nous pouvons introduire quelque chose qui s'appelle un pointeur. Il s'avère que nous pouvons résoudre ce problème pas par passage dans des copies de x et y mais en passant quoi, pensez-vous, à la fonction d'échange? Ouais, qu'en est-il l'adresse? Nous n'avons pas vraiment parlé des adresses dans beaucoup de détails, mais si ce tableau représente la mémoire de mon ordinateur nous pourrions certainement commencer la numérotation des octets dans ma RAM et dire que c'est l'octet # 1, c'est l'octet # 2, # 3 octets, N ° 4 octets, l'octet # ... 2 milliards d'euros si je dispose de 2 Go de RAM, si nous pourrions certainement trouver quelque régime arbitraire de numérotation pour tous les octets individuels dans la mémoire de mon ordinateur. Et si au lieu de swap quand je l'appelle plutôt que de passer à des copies de x et y pourquoi ne puis-je pas plutôt passer à l'adresse de x ici, l'adresse de y ici, essentiellement l'adresse postale de x et y, car alors échanger, s'il est informé de l'adresse dans la mémoire de x et y, alors échanger, si nous avons formé lui un peu, il pourrait conduire à cette adresse, pour ainsi dire, x et y modifier le numéro, puis route vers l'adresse de y, changer le numéro de là, même s'il n'est pas réellement obtenir des copies de ces valeurs lui-même, ainsi, même si nous en avons parlé comme étant la mémoire principale et cet échange comme étant la mémoire des puissants et la partie dangereuse de C est une fonction qui peut toucher n'importe où dans la mémoire de l'ordinateur, et c'est puissant que vous pouvez faire des choses très chics avec des programmes informatiques en C C'est dangereux parce que vous pouvez également visser en place très facilement. En fait, l'une des façons les plus communes pour les programmes de nos jours à être exploitée est encore pour un programmeur de ne pas se rendre compte qu'il ou elle est un ensemble de données permettant à écrire dans un emplacement mémoire qui n'a pas été prévu. Par exemple, il ou elle déclare un tableau de taille 10 mais essaie de mettre accidentellement 11 octets dans ce tableau de la mémoire, et vous commencez à toucher des parties de la mémoire qui ne sont plus valables. Juste à ce contexte, certains d'entre vous savez peut-être que le logiciel vous entraîne souvent des numéros de série ou les clés d'enregistrement, Photoshop et Word et des programmes de ce genre. Il existe des fissures, comme certains d'entre vous le savez, en ligne où vous pouvez exécuter un petit programme, et voila, pas plus d'une demande de numéro de série. Comment est-ce de travail? Dans de nombreux cas, ces choses sont tout simplement trouver dans les ordinateurs segments de texte dans zéros réels de l'ordinateur et ceux où est cette fonction où le numéro de série est demandé, et vous écrasez l'espace, ou alors que le programme est en cours d'exécution vous pouvez savoir où la clé est en fait stocké en utilisant ce qu'on appelle un débogueur, et vous pouvez craquer logiciels de cette façon. Cela ne veut pas dire que c'est notre objectif pour les deux prochains jours, mais il a de très réelles conséquences. Que l'on arrive à impliquer le vol de logiciels, mais il ya aussi des compromis machines complètes. En fait, lorsque les sites Web de nos jours sont exploitées et compromis et de données est une fuite et mots de passe sont volés cette très souvent trait à la mauvaise gestion de son mémoire, ou, dans le cas de bases de données, défaut d'anticipation entrée contradictoire, donc plus à ce sujet dans les semaines à venir, mais pour l'instant juste un avant-goût du genre de dégâts que vous pouvez faire pas tout à fait par comprendre comment les choses fonctionnent sous le capot. Allons de comprendre pourquoi il en est rompu avec un outil qui va devenir de plus en plus utiles que nos programmes deviennent plus complexes. Jusqu'à présent, quand vous avez eu un bug dans le programme comment avez-vous fait à ce sujet le débogage? Qu'est-ce que vos techniques sont à ce jour, que ce soit enseignée par votre carte de TF ou juste un autodidacte? [Étudiants] Printf. Printf, alors printf a probablement été votre ami, si vous voulez voir ce qui se passe à l'intérieur de votre programme vous venez de mettre printf ici, printf ici, printf ici. Puis vous l'exécutez, et vous obtenez tout un tas de choses sur l'écran que vous pouvez utiliser pour en déduire ce qui se passe mal dans votre programme. Printf tend à être une chose très puissante, mais c'est un processus très manuel. Vous devez mettre un printf ici, un printf ici, et si vous le mettez à l'intérieur d'une boucle que vous pourriez obtenir 100 lignes de sortie que vous avez alors de passer au crible. Ce n'est pas un mécanisme très convivial ou interactif pour les programmes de débogage, mais heureusement, il existe des solutions de rechange. Il s'agit d'un programme, par exemple, appelé GDB, le débogueur GNU, qui est un peu obscur dans la façon dont vous l'utilisez. C'est un peu complexe, mais franchement, c'est une de ces choses où si vous avez mis dans cette semaine et la suivante l'heure supplémentaire pour comprendre quelque chose comme GDB il vous fera économiser probablement des dizaines d'heures sur le long terme, Donc, avec cela, permettez-moi de vous donner un avant-goût de la façon dont ça fonctionne. Je suis dans ma fenêtre de terminal. Permettez-moi aller de l'avant et de compiler ce programme, buggy3. Il est déjà à jour. Permettez-moi de faire fonctionner tout comme nous avons fait un retour tout, et en effet, il est cassé. Mais pourquoi est-ce? Peut-être que j'ai foiré la fonction swap. Peut-être que c'est a et b. Je ne suis pas tout à fait les déplacer correctement. Permettez-moi aller de l'avant et de le faire. Plutôt que de simplement exécuter buggy3 laissez-moi plutôt exécuter ce programme GDB, et je vais lui dire de lancer buggy3, et je vais inclure un argument en ligne de commande,-tui, et nous allons mettre cela dans de futurs problèmes pour rappeler au spec. Et maintenant, cette interface en noir et blanc surgi qui, encore une fois, est un peu écrasante au premier abord, car il ya toute cette informations sur la garantie ici-bas, mais au moins il ya quelque chose de familier. Dans la partie supérieure de la fenêtre est mon code actuel, et si je défiler vers le haut ici permettez-moi de faire défiler jusqu'en haut de mon dossier, et en effet, il ya buggy3.c, et de l'avis au bas de cette fenêtre J'ai cette invite GDB. Ce n'est pas la même chose que mon invite normale John Harvard. Il s'agit d'une invite de commande qui va me permettre de contrôler GDB. GDB est un débogueur. Un débogueur est un programme qui vous permet de marcher à travers l'exécution de votre programme ligne par ligne par ligne, le long du chemin que vous voulez faire quelque chose au programme, même appeler des fonctions, ou à la recherche, plus important encore, à différentes valeurs de la variable d'. Allons de l'avant et de le faire. Je vais aller de l'avant et tapez run à l'invite GDB, si remarquerez en bas à gauche de l'écran, j'ai tapé courir, et j'ai appuyez sur Entrée, et qu'est-ce que cela fait? Il a littéralement couru mon programme, mais je n'ai pas vu beaucoup de quoi continuer ici parce que je n'ai pas vraiment dit le débogueur pour faire une pause à un moment précis dans le temps. Juste en tapant run exécute le programme. Je n'ai pas vraiment vu quelque chose. Je ne peux pas le manipuler. Au lieu de me laisser faire cela. À cette invite GDB laissez-moi plutôt taper introduction par effraction. Ce n'est pas ce que je voulais dire à taper. Disons plutôt que taper rupture principale. En d'autres termes, je veux mettre quelque chose qui s'appelle un point d'arrêt, qui porte bien son nom, car il risquerait de casser ou de pause exécution de votre programme à cet endroit particulier. Principal est le nom de ma fonction. Notez que GDB est assez malin. Il compris que se passe principal pour commencer à peu près à la ligne 18 de buggy3.c, puis notez ici en haut à gauche + b est juste à côté de la ligne 18. C'est en me rappelant que j'ai mis un point d'arrêt à la ligne 18. Cette fois, quand je tape course, je vais exécuter mon programme jusqu'à ce qu'il touche ce point d'arrêt, de sorte que le programme se met en pause pour moi à la ligne 18. Here we go, de fonctionner. Rien ne semble avoir eu lieu, mais préavis en bas à gauche démarrage du programme, buggy3, point d'arrêt 1 dans la ligne principale buggy3.c 18. Que puis-je faire maintenant? Remarquez que je peux commencer à taper des choses comme impression, pas printf, x impression, et maintenant c'est étrange. Le $ 1 est juste une curiosité, comme nous le verrons chaque fois que vous imprimez quelque chose que vous obtenez une nouvelle valeur de $. C'est ainsi que vous pouvez vous référer aux valeurs précédentes au cas où, mais pour l'instant ce n'est impression de me dire que la valeur de x, à ce moment de l'histoire est apparemment 134514032. Quoi? Où cela s'est-il encore venir? [Inaudible étudiant] En effet, c'est ce que nous appellerons une valeur ordures, et nous n'avons pas parlé encore, mais la raison pour laquelle vous initialiser les variables est évidemment de sorte qu'ils ont une certaine valeur que vous voulez leur donner. Mais le hic c'est rappeler que vous pouvez déclarer des variables comme je l'ai fait il ya un instant dans mon exemple sigma sans pour autant leur donner une valeur. Rappelez-vous ce que j'ai fait ici en sigma. Je déclare n, mais quelle valeur ai-je lui donner? Aucun, parce que je savais que, dans les quelques lignes qui suivent GetInt prendrait en charge le problème de mettre une valeur à l'intérieur de n. Mais à ce moment de l'histoire de la ligne 11 ligne 12 et la ligne 13 et la ligne 14 et tout au long de ces lignes de plusieurs quelle est la valeur de n? En C, vous ne savez pas. C'est généralement une valeur ordures, un certain nombre totalement aléatoire Il ne reste plus essentiellement une fonction précédente ayant été exécuté, de sorte que votre programme s'exécute Rappelons que la fonction reçoit, fonction, fonction. Tous ces cadres se mettre sur la mémoire, puis ceux de retour des fonctions, et comme je l'ai suggéré avec la gomme de leur mémoire est éventuellement réutilisés. Eh bien, il se trouve que cette variable x dans ce programme semble avoir contenu une valeur ordures comme 134514032 d'une certaine fonction précédente, pas un seul que j'ai écrit. Il pourrait être quelque chose qui vient efficacement avec le système d'exploitation, une fonction sous la hotte. D'accord, c'est très bien, mais nous allons maintenant passer à la ligne suivante. Si je tape "suivant" à mon invite GDB et je appuyez sur Entrée, remarquer que la mise en évidence se déplace vers le bas pour la ligne 19, mais la conséquence logique est que la ligne 18 a maintenant terminé son exécution, donc si j'ai de nouveau taper "print x" Je devrais maintenant voir 1, et en effet, je le fais. Encore une fois, les trucs $ est une façon de vous rappeler GDB ce que l'histoire d'impressions sont que vous avez fait. Maintenant, laissez-moi aller de l'avant et d'imprimer y, et en effet, y est une valeur folle aussi, mais pas une grosse affaire parce que la ligne 19, nous sommes sur le point de céder la valeur 2, alors laissez-moi entrer "à côté" de nouveau. Et maintenant nous sommes sur la ligne printf. Permettez-moi de faire x d'impression. Permettez-moi de faire y imprimer. Franchement, je suis un peu fatigué de l'impression de ce. Permettez-moi plutôt de type "x affichage" et "affichage y», et maintenant chaque fois que je tape une commande dans l'avenir Je vais rappeler de ce qui est x et y, ce qui est x et y, ce qui est x et y. Je peux aussi, en passant, tapez "locaux d'information." Info est une commande spéciale. Les sections locales signifie qu'il me montre les variables locales. Juste au cas où je ne sais plus ou il s'agit d'un fou, fonction complexe que moi ou quelqu'un d'autre a écrit habitants d'information vous indiquera ce sont toutes les variables locales à l'intérieur de cette fonction locale que vous pourriez soucier si vous voulez fouiller. Maintenant, printf est sur le point de signer, alors laissez-moi aller de l'avant et il suffit de taper "suivant". Parce que nous sommes dans cet environnement, nous ne sommes pas réellement le voir exécuter ici-bas, mais remarquez qu'il devient un peu mutilé ici. Mais remarquez qu'il est remplaçant l'écran là-bas, donc ce n'est pas un programme parfait ici, mais c'est bien parce que je peux toujours fouiller à l'aide d'impression si je veux. Permettez-moi de saisir la prochaine fois, et maintenant voici la partie intéressante. À ce stade de l'histoire y est 2, et x est 1, comme suggéré ici, et encore une fois, la raison pour laquelle il est automatiquement afficher maintenant, c'est parce que j'ai utilisé la commande x affichage et affichage y, donc le moment je tape suivante en théorie x et y doivent être permutés. Maintenant, nous savons déjà que ça ne va pas être le cas, mais nous verrons dans un instant comment on peut plonger plus profond pour comprendre pourquoi c'est vrai. Ensuite, et malheureusement, y est toujours de 2 et x est toujours 1, et je peux le confirmer. Imprimer x, y d'impression. En effet, aucun échange qui s'est réellement passé, nous allons donc commencer ce cours. Il est clair swap est cassé. Disons plutôt que taper «run» à nouveau. Permettez-moi de dire oui, je veux recommencer depuis le début, entrez. Maintenant, je suis de retour à la ligne jusqu'à 18 ans. Maintenant, remarquez x et y sont des valeurs parasites nouveau. Suivant, Suivant, Suivant, à côté. Si je m'ennuie je peux aussi simplement taper n pour la prochaine. Vous pouvez l'abréger à la séquence la plus courte possible des caractères. Le swap est désormais rompu. Débutons notre étude, si au lieu de taper à côté, maintenant je vais taper étape de sorte que je ne suis pas à pas à l'intérieur de cette fonction afin que je puisse passer au travers, alors j'ai frappé étape, puis entrez. Notez que les sauts en soulignant descendant plus bas dans mon programme à la ligne 36. Maintenant, quelles sont les variables locales? Les habitants d'infos. Rien pour l'instant parce que nous n'avons pas obtenu à cette ligne, nous allons donc aller de l'avant et de dire "suivant". Maintenant, nous semblons avoir tmp tmp impression,. Valeur des ordures, pas vrai? Je crois. Que diriez-vous d'imprimer une, print b, 1 et 2? En un instant, dès que je tape la prochaine fois tmp va prendre une valeur de 1, espérons-le, parce tmp va être affectée la valeur d'un. Maintenant, nous allons ne imprimer un b, d'impression, mais maintenant imprimer tmp, et c'est en effet 1. Permettez-moi de faire par la suite. Permettez-moi de faire par la suite. J'ai fini la fonction de permutation. Je suis toujours à l'intérieur de celui-ci dans la ligne 40, alors permettez-moi d'imprimer une, print b, et je me moque de ce tmp est. Il ressemble échange est correct quand il s'agit de permutation a et b. Mais si je maintenant taper prochaine, je reviens à la ligne 25, et bien sûr, si je tape dans x et y imprimée ils sont toujours inchangée, de sorte que nous n'avons pas résolu le problème. Mais le diagnostic peut-être maintenant avec ce programme GDB nous avons au moins obtenu un peu plus de compréhension ce qui va mal, sans avoir à litière notre code en mettant un printf ici, printf ici, printf ici, puis de l'exécuter encore et encore à essayer de comprendre ce qui va mal. Je vais aller de l'avant et de quitter de ce tout à fait avec arrêter de fumer. Il va alors dire: «Quittez toute façon?" Oui. Maintenant, je suis de retour à mon message normal, et je suis fait à l'aide de GDB. Soit dit en passant, vous n'avez pas besoin d'utiliser ce drapeau-tui. En fait, si vous l'omettez vous obtenez essentiellement la moitié inférieure de l'écran. Si je puis tapez grande pause, puis exécutez Je peux encore exécuter mon programme, mais ce qu'elle va faire, c'est plus textuellement juste me montrer la ligne en cours à la fois. Le tui-interface utilisateur textuelle, vous montre juste plus du programme à la fois, ce qui est probablement un peu conceptuellement plus facile. Mais, en vérité, je peux juste faire par la suite, suivant, suivant, et je vais voir une ligne à la fois, et si je veux vraiment voir ce qui se passe Je peux taper liste et de voir tout un tas de lignes voisines. Il ya une vidéo que nous avons demandé à ce que vous regardez pour le problème ensembles 3 dans lequel Nate couvre une partie de la complexité de GDB, et c'est une de ces choses, honnêtement, où un certain pourcentage non négligeable d'entre vous ne touchera jamais GDB, et ce sera une mauvaise chose parce que littéralement vous finirez par passer plus de temps plus tard ce semestre traquer les bugs, alors vous feriez si vous mettez dans cette demi-heure / heure cette semaine suivante et l'apprentissage à l'aise avec GDB. Printf était votre ami. GDB devrait maintenant être votre ami. Toutes les questions sur GDB? Et voici une liste rapide de quelques-unes des commandes les plus puissantes et utiles. Ouais. >> Pouvez-vous imprimer une chaîne? Pouvez-vous imprimer une chaîne? Tout à fait. Il ne doit pas seulement être des nombres entiers. Si une variable s est une chaîne suffit de taper dans l 'impression. Il va vous montrer ce que la variable chaîne est. [Inaudible étudiant] Il vous donnera l'adresse et la chaîne elle-même. Il vous montrera aussi. Et une dernière chose, juste parce que ce sont des bon de savoir aussi. Backtrace et le cadre, permettez-moi de plonger dans cette dernière fois, même programme exact avec GDB. Permettez-moi aller de l'avant et exécuter la version textuelle utilisateur interface, briser principale. Permettez-moi aller de l'avant et de courir à nouveau. Je suis ici. Maintenant, laissez-moi aller ensuite, suivant, suivant, suivant, suivant, étape, entrez. Et supposons maintenant que je suis maintenant en échange délibérément, mais je suis comme "Putain, quelle était la valeur de x?" Je ne peux pas faire plus x. Je ne peux pas y parce qu'ils ne sont pas dans la portée. Ils ne sont pas dans leur contexte, mais pas de problème. Je peux taper trace. Cela me montre toutes les fonctions qui ont exécutées jusqu'à ce point dans le temps. Notez que l'un sur le fond, main, s'aligne avec principal étant à la base de notre image ici. Le fait que d'échange ci-dessus est qu'il s'aligne avec swap étant au-dessus dans la mémoire ici, et si je veux revenir au menu principal temporairement je peux dire «cadre». Quel numéro? Principale est la trame n ° 1. Je vais aller de l'avant et de dire «cadre 1." Maintenant, je suis de retour dans main, et je peux imprimer x, et je peux imprimer y, mais je ne peux pas imprimer sur a ou b. Mais je peux si je dis: «Bon, attends une minute. Où était le swap?" Permettez-moi aller de l'avant et de dire "0 image." Maintenant, je suis de retour là où je veux être, et en passant, il ya d'autres commandes aussi, comme si vous êtes vraiment obtenir le typage s'ennuyer prochaine, prochain, prochaine, prochain, vous pouvez généralement dire des choses comme "10 next", et que fait défiler les 10 prochaines lignes. Vous pouvez également écrire «continuer» lorsque vous avez vraiment marre de pas à pas à travers elle. Continuer exécutera votre programme sans interruption jusqu'à ce qu'il rencontre un autre point d'arrêt, que ce soit dans une boucle ou plus bas dans votre programme. Dans ce cas, nous avons continué jusqu'à la fin, et le programme s'est terminé normalement. C'est une façon élégante, un processus de qualité inférieure. Tout le programme s'est terminé normalement. Plus sur cela dans la vidéo et le débogage des sessions à venir. C'était beaucoup. Prenons notre 5 minutes de pause ici, et nous reviendrons avec structs et les fichiers. Si vous avez plongé dans pset cette semaine déjà vous saurez que nous utilisons dans le code de distribution, le code source que nous fournissons à vous en tant que point de départ, de nouvelles techniques. En particulier, nous avons présenté ce nouveau mot-clé struct appelé, pour la structure, afin que nous puissions créer des variables personnalisées de toutes sortes. Nous avons également introduit la notion de fichier d'entrée de fichier I / O et de sortie, et c'est afin que nous puissions enregistrer l'état de votre conseil Scramble à un fichier sur le disque de sorte que les boursiers d'enseignement et je peux comprendre ce qui se passe à l'intérieur de votre programme sans avoir à jouer manuellement des dizaines de jeux de bousculade. Nous pouvons le faire plus manière automatisée. Cette idée d'une structure résout un problème assez convaincante. Supposons que nous voulons mettre en œuvre certains programmes qui tient en quelque sorte la trace des informations sur les élèves, et les élèves pourraient avoir, par exemple, une pièce d'identité, un nom et une maison dans un endroit comme Harvard, ce sont donc 3 morceaux de l'information nous voulons garder autour, alors laissez-moi aller de l'avant et commencer à écrire un petit programme ici, inclure stdio.h. Permettez-moi de faire comprendre cs50.h. Et puis commencer ma fonction principale. Je vais vous embêtez pas avec des arguments de ligne de commande, et ici je veux avoir un étudiant, alors je vais dire un élève a un nom, alors je vais dire «nom de chaîne." Alors je vais dire un étudiant dispose également d'un ID, id int sorte, et un étudiant a une maison, donc je vais aussi dire «maison chaîne." Alors, je vais commander ces petits une manière plus propre comme ça. Ok, maintenant j'ai 3 variables avec lesquelles représentent un étudiant, donc «un étudiant». Et maintenant, je veux remplir ces valeurs, alors laissez-moi aller de l'avant et dire quelque chose comme "Id = 123». Nom va se faire David. Disons que la maison va se faire Mather, et puis je vais faire quelque chose de façon arbitraire comme printf ("% s, dont l'ID est% d, vit dans% s. Et maintenant, qu'est-ce que je veux brancher ici, l'un après l'autre? Nom, id, maison, retourne 0. Bon, sauf si j'ai foiré quelque part ici Je pense que nous avons un très bon programme qui stocke un étudiant. Bien sûr, ce n'est pas du tout intéressant. Que faire si je veux avoir 2 étudiants? Ce n'est pas une grosse affaire. Je peux appuyer 2 personnes. Permettez-moi aller de l'avant et de mettre en valeur ce et de descendre ici, et je peux dire "id = 456" pour quelqu'un comme Rob qui vit à Kirkland. Bon, attendez, mais je ne peux pas appeler ces la même chose, et on dirait que je vais devoir copier ce, permettez-moi de dire que ce seront des variables de David, et laissez-moi obtenir des copies de ces documents pour Rob. Nous allons appeler ces Rob, mais cela ne va pas au travail maintenant parce que j'ai-attendre, me laisse passer à id1, nom1 et house1. Rob sera de 2, 2. Je dois changer ça ici, ici, ici, ici, ici, ici. Attendez, qu'est-ce à propos de Tommy? Faisons-le à nouveau. Évidemment, si vous pensez toujours que c'est une bonne façon de le faire, ce n'est pas, donc copier / coller mal. Mais nous avons résolu ce il ya une semaine. Quelle a été notre solution quand nous avons voulu avoir plusieurs instances d'un même type de données? [Etudiants] Tableau. Un tableau, donc je vais essayer de nettoyer tout ça. Permettez-moi de faire de la place pour moi en haut, et laissez-moi plutôt le faire ici. Nous allons appeler ces gens, et à la place, je vais dire "id int," et je vais appuyer 3 d'entre nous pour l'instant. Je vais dire "noms de chaîne," et je vais appuyer 3 d'entre nous, et puis je vais dire "maisons à cordes», et je vais appuyer 3 d'entre nous. Maintenant, ici, au lieu de faire ses propres David variables locales nous pouvons nous débarrasser de ceux-ci. Ça fait du bien que nous nettoyer cela. Je peux alors dire que David va être [0] et les noms [0] et les maisons [0]. Et puis Rob nous pouvons même gagner à ce sujet. Mettons cela ici-bas, donc il va être arbitrairement ids [1]. Il va y avoir des noms [1], puis enfin, les maisons [1]. Encore un peu fastidieux, et maintenant je dois comprendre cela, alors disons "noms [0], id [0], maisons [0], et nous allons pluriel cela. Ids, ids, ids. Et encore, je vais le faire, et là encore, je suis déjà recours à des copier / coller de nouveau, de sorte chances sont qu'il ya une autre solution ici. Je peux probablement nettoyer tout ça plus loin avec une boucle ou quelque chose comme ça, Donc en bref, c'est un peu mieux, mais se sent encore comme Je recours à copier / coller, mais même cela, je prétends, n'est pas vraiment fondamentalement la bonne solution parce Et si un jour nous décidons de vous savez quoi? Nous avons vraiment aurait dû stocker des adresses email pour David et Rob et tout le monde dans ce programme. Nous devrions également stocker des numéros de téléphone. Nous devrions également enregistrer des numéros de téléphone d'urgence. Nous avons tous ces éléments de données que nous voulons stocker, Alors, comment allez-vous faire cela? Vous déclarez un autre tableau en haut, puis vous ajoutez manuellement une adresse e-mail [0], adresse e-mail [1] David et Rob et ainsi de suite. Mais il ne s'agit que d'une hypothèse sous-jacente à cette conception que je suis en utilisant le système d'honneur de savoir que [I] dans chacun des réseaux de plusieurs se trouve juste à se référer à la même personne, afin [0] dans ids est le numéro 123, et je vais supposer que les noms [0] est la même personne le nom et maisons [0] est la maison de la même personne et ainsi de suite pour tous les différents tableaux que je crée. Mais remarquez qu'il n'y a aucun lien fondamental parmi ces 3 informations, id, name et la maison, même si l'entité que nous essayons de modèle à ce programme n'est pas des tableaux. Les tableaux sont exactement de cette manière programmatique de le faire. Ce que nous voulons modéliser dans notre programme est une personne comme David, une personne comme Rob l'intérieur de laquelle ou d'encapsulation est un nom et un ID et une maison. Peut-on en quelque sorte exprimer cette idée d'encapsulation par lequel une personne a une identité, un nom et une maison et ne pas recourir à ce hack vraiment où nous venons confiance que quelque chose support se réfère à la même entité humaine dans chacun de ces tableaux disparates? Nous pouvons y parvenir. Laissez-moi aller principal ci-dessus pour le moment, et laissez-moi créer mon propre type de données pour vraiment la première fois. Nous avons utilisé cette technique dans la lutte confuse, mais ici, je vais aller de l'avant et de créer un type de données, et vous savez quoi, je vais l'appeler étudiant ou une personne, et je vais utiliser typedef pour définir un type. Je vais dire que c'est une structure, et puis cette structure va être de l'étudiant type, disons, même si c'est un peu daté maintenant pour moi. Nous dirons "int id." On va dire «nom de chaîne." Ensuite, nous allons dire «maison chaîne" alors maintenant à la fin de ces quelques lignes de code J'ai simplement appris qu'il existe clang un type de données int ailleurs, en plus de chaînes, en plus de doubler, en plus des flotteurs. Dès cet instant dans la ligne 11 du temps, il ya maintenant un nouveau type de données appelé les étudiants, et maintenant je peux déclarer une variable étudiant où je veux, alors laissez-moi faire défiler ici pour les gens. Maintenant je peux me débarrasser de cela, et je peux redescendre à David ici, et David je peux vraiment dire que David, nous pouvons littéralement le nom de la variable après moi, va être de l'étudiant type. Cela peut sembler un peu bizarre, mais ce n'est pas si différent de déclarer quelque chose comme un int ou une chaîne ou un flotteur. Il se trouve juste à être appelé étudiant maintenant, et si je veux mettre quelque chose à l'intérieur de cette structure Je dois maintenant utiliser un nouveau morceau de syntaxe, mais il est assez simple, david.id = 123, david.name = "David" dans le capital D, et david.house = "Mather," et maintenant je peux me débarrasser de ce truc ici. Notez que nous avons redessiné notre programme vraiment une bien meilleure façon dans ce moment de notre programme reflète le monde réel. Il ya une notion du monde réel d'une personne ou d'un étudiant. Ici, nous avons maintenant une version C d'une personne ou plus précisément un étudiant. A l'intérieur de cette personne sont ces caractéristiques pertinentes, ID, le nom et la maison, donc Rob devient essentiellement la même chose ici-bas, si l'élève rob, et maintenant rob.id = 456, rob.name = "Rob". Le fait que la variable est appelée Rob est un peu vide de sens. Nous aurions pu appelé x, y ou z. Nous venons tout juste nommé Rob pour être sémantiquement cohérente, mais en réalité le nom est à l'intérieur de ce champ lui-même, alors maintenant j'ai cette. Cela ne veut pas trop envie de la meilleure conception de ce que j'ai codé en dur David. J'ai codé en dur Rob. Et j'ai encore de recourir à une copiez et collez chaque fois que je veux de nouvelles variables. Par ailleurs, je dois apparemment donner à chacun de ces variables un nom, même si je préfère de loin décrire ces variables  étudiants plus génériquement comme. Maintenant, nous pouvons fusionner les idées qui ont bien fonctionné pour nous et au lieu de dire: «Vous savez quoi, donnez-moi une variable appelée étudiants, et mangeons que ce soit de taille 3, "alors maintenant je peux affiner plus loin, se débarrasser de la main déclaré David, et je peux dire à la place quelque chose comme étudiants [0] ici. Je peux alors dire que les étudiants [0] ici, étudiants [0] ici, et ainsi de suite, et je peux faire le tour et nettoyer ça pour Rob. Je pourrais aussi aller sur maintenant peut-être l'ajout d'une boucle et en utilisant GetString et getInt pour obtenir effectivement ces valeurs à l'utilisateur. Je pourrais continuer sur l'ajout d'une constante parce que c'est généralement une mauvaise pratique de coder en dur un nombre arbitraire comme 3 ici et puis n'oubliez pas que vous devriez mettre pas plus de 3 étudiants en elle. Il serait sans doute préférable d'utiliser # define dans le haut de mon dossier et le facteur qui, donc en fait, laissez-moi aller de l'avant et de généraliser cela. Permettez-moi d'ouvrir un exemple qui est au milieu d'aujourd'hui exemples à l'avance, structs1. Il s'agit d'un programme plus complet qui utilise # define ici et dit que nous allons avoir 3 étudiants par défaut. Ici, je suis en déclarant une valeur de classe d'étudiants, si une classe d'étudiants, et maintenant je suis en utilisant une boucle juste pour rendre le code un peu plus élégant, peupler la classe avec l'entrée de l'utilisateur, afin d'itérer i = 0 sur place pour les étudiants, ce qui est 3. Et puis je demander à l'utilisateur de cette version  ce qui est l'ID de l'étudiant, et je l'obtenir avec getInt. Quel est le nom de l'étudiant, puis-je le faire avec GetString. Quelle est la maison de l'étudiant? Je me le procurer avec GetString. Et puis, au fond, j'ai tout simplement décidé de changer comment je vais imprimer ces cartes et d'utiliser effectivement une boucle, et qui suis-je imprimer? Selon le commentaire, je suis d'imprimer n'importe qui dans Mather, et c'est tellement Rob et Tommy et ainsi de suite, fait de Tommy dans Mather. Tommy et David serait imprimée dans ce cas, mais comment est-ce de travail? Nous n'avons pas vu cette fonction avant, mais faire une supposition quant à ce que cela fait. Compare les chaînes. C'est un peu non évidente comment il se compare des chaînes car il s'avère si elle retourne 0 signifie que les chaînes sont égales. Si elle retourne -1 signifie que l'on vient avant l'autre par ordre alphabétique, et si elle retourne +1 qui signifie que le mot vient d'autres par ordre alphabétique avant l'autre, et que vous pouvez consulter en ligne ou à la page de manuel pour voir exactement où est qui, mais tout cela est en train de faire, c'est que c'est en disant si le [i]. maison est égal à "Mather" alors allez-y et imprimer ainsi et est donc à Mather. Mais voici quelque chose que nous n'avons pas vu avant, et nous reviendrons sur ce sujet. Je ne me souviens pas avoir à le faire dans un de mes programmes. Free est apparemment référence à la mémoire, libération de la mémoire, mais quel souvenir je libère apparemment dans cette boucle au bas de ce programme? On dirait que je suis en libérant nom d'une personne et la maison d'une personne, mais pourquoi est-ce? Il s'avère que toutes ces semaines vous avez été en utilisant GetString nous avons été genre d'introduire un bogue dans chacune de vos programmes. GetString par la conception alloue de la mémoire pour qu'il puisse revenir à vous une chaîne, comme David, ou Rob, et vous pouvez alors faire ce que vous voulez avec cette chaîne dans votre programme parce que nous avons réservé la mémoire pour vous. Le problème, c'est tout ce temps, chaque fois que vous appelez GetString nous, les auteurs de GetString, ont demandé au système d'exploitation pour nous donner un peu de RAM pour cette chaîne. Donnez-nous un peu de RAM pour cette chaîne suivante. Donnez-nous un peu plus de RAM pour cette chaîne suivante. Qu'est-ce que vous, le programmeur, n'ont jamais fait nous donne que de retour de la mémoire, donc pour ces quelques semaines tous les programmes que vous avez écrit ont eu ce qu'on appelle un saut de mémoire par lequel ils continuer à utiliser mémoire de plus en plus à chaque fois que vous appelez GetString, et c'est très bien. Nous avons délibérément le faire dans les premières semaines parce que ce n'est pas si intéressant avoir à s'inquiéter de savoir où la chaîne est en venir. Tout ce que vous voulez, c'est le mot Rob revenir lorsque l'utilisateur le type po Mais aller de l'avant, nous avons maintenant de commencer à obtenir plus sophistiquée à ce sujet. Chaque fois que nous nous ferions mieux allouer de la mémoire finit par le remettre en arrière. Sinon, dans le monde réel sur votre Mac ou PC que vous pourriez avoir l'occasion expérimenté symptômes où votre ordinateur est de broyage pour une halte à terme ou le ballon de plage est juste stupide de filature occupant le l'ordinateur une attention entière et vous ne pouvez pas faire les choses. Cela peut s'expliquer par un certain nombre de bugs, mais parmi ces bugs possibles sont choses appelées fuites de mémoire par lequel quelqu'un qui a écrit ce morceau de logiciel vous utilisez ne se souvenait pas de libérer la mémoire qu'il ou elle a demandé au système d'exploitation pour, ne pas utiliser GetString, parce que c'est une chose CS50, mais en utilisant des fonctions similaires que demander au système d'exploitation pour la mémoire. Si vous ou de mauvaise manipulation, et jamais retourner cette mémoire un symptôme de ce que peut être un programme ralentit et freine et ralentit à moins que vous n'oubliez pas d'appeler gratuitement. Nous y reviendrons quand et pourquoi vous appelez gratuitement, mais nous allons aller de l'avant pour faire bonne mesure et essayez d'exécuter ce programme en particulier. Cela a été appelé structs1, entrez. Permettez-moi aller de l'avant et exécutez structs1, 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, et l'on voit David à Mather, de Tommy dans Mather. Ceci est juste un test de cohérence peu que le programme fonctionne. Maintenant, malheureusement, ce programme est un peu frustrant dans ce Je n'ai tout ce travail, j'ai tapé dans 9 différentes chaînes, appuyez sur Entrée, On m'a dit qui était à Mather, mais évidemment je savais qui était à Mather déjà parce que je l'ai tapé. Il serait moins agréable si ce programme ressemble plus à une base de données et il se souvient effectivement ce que j'ai tapé dans donc je ne plus jamais avoir à saisir ces dossiers des étudiants. Peut-être que c'est comme un système de registrariat. Nous pouvons le faire en utilisant cette technique connue sous le nom de fichier du fichier d'entrée I / O et de sortie, d'une manière très générique de dire chaque fois que vous voulez lire des fichiers ou écrire des fichiers vous pouvez le faire avec un certain ensemble de fonctions. Permettez-moi aller de l'avant et ouvrez ce structs2.c exemple, qui est presque identique, mais nous allons voir ce qu'il fait maintenant. Au sommet du dossier, je déclare une classe d'élèves. Je puis remplir la classe avec l'entrée de l'utilisateur, de sorte que ces lignes de code sont exactement comme avant. Ensuite, si je défiler vers le bas ici je imprimer tout le monde qui est à Mather arbitrairement comme avant, mais c'est une nouveauté intéressante. Ces lignes de code sont nouveaux, et ils introduisent quelque chose ici, FICHIER, tout en majuscules, et il a * ici aussi. Permettez-moi de passer ce cours ici, a * ici aussi. Cette fonction nous n'avons pas vu avant, fopen, mais cela signifie fichier ouvert, nous allons donc parcourir celles-ci, et c'est quelque chose que nous y reviendrons dans psets futures, mais cette ligne ouvre ici essentiellement un fichier appelé base de données, et il ouvre spécifiquement de telle manière qu'il puisse faire quoi pour elle? [Inaudible étudiant] Bon, alors "w" signifie simplement qu'il raconte le système d'exploitation ouvrir ce fichier de telle sorte que je puisse écrire dessus. Je n'ai pas envie de le lire. Je ne tiens pas à le regarder. Je tiens à le modifier et ajouter des choses potentiellement à elle, et le fichier va être appelée base de données. Cela pourrait être appelé n'importe quoi. Cela pourrait être database.txt. Cela pourrait être. Db. Cela pourrait être un mot comme foo, mais je arbitrairement choisi de nommer le fichier base de données. Il s'agit d'un test de cohérence peu que nous y reviendrons en détail au fil du temps, si fp, pour pointeur de fichier, ne pas NULL égale ce qui signifie que tout va bien. Longue histoire courte, les fonctions comme fopen parfois échouer. Peut-être que le fichier n'existe pas. Peut-être que vous êtes hors de l'espace disque. Peut-être que vous n'avez pas la permission de ce dossier, si fopen retourne quelque chose de grave n'est arrivé nulle. Inversement, si la fonction fopen ne retourne pas nulle tout va bien et je peux commencer à écrire dans ce fichier. Voici une nouvelle astuce. Il s'agit d'une boucle pour itérer sur qui est chacun de mes élèves, et cela a l'air si semblable à ce que nous avons fait avant, mais cette fonction est un cousin de printf fprintf appelé pour le fichier printf, et remarquez que c'est différent en seulement 2 façons. Premièrement, il commence par f au lieu de p, mais alors son premier argument est apparemment quoi? [Etudiants] du fichier. >> C'est un fichier. Cette chose appelée fp, que nous finirons par démêler ce qui est un pointeur de fichier, mais pour l'instant fp représente simplement le fichier que j'ai ouvert, si fprintf dit ici imprimer ID d'utilisateur pour le fichier, et non pas à l'écran. Imprimer le nom de l'utilisateur dans le fichier, et non pas à l'écran, la maison pour le fichier, et non pas à l'écran, puis ici, de toute évidence, fermez le fichier, puis ici-bas libérer la mémoire. La seule différence entre cette version 2 et la version 1 est l'introduction de la fonction fopen et ce fichier avec * et cette notion de fprintf, nous allons donc voir ce que le résultat final. Laissez-moi aller dans ma fenêtre de terminal. Permettez-moi de lancer structs2, entrez. On dirait que tout va bien. Nous allons relancer structs2. 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, entrez. On dirait qu'il se comportaient de la même chose, mais si je fais maintenant ls remarquez ce fichier est ici parmi tout mon code, base de données, nous allons donc ouvrir ce, gedit de base de données, et coup d'oeil. Ce n'est pas la plus sexy de formats de fichiers. C'est vraiment un morceau de ligne de données par ligne par ligne, mais ceux d'entre vous qui utilisent des fichiers Excel ou CSV, comma separated values, Je pourrais certainement utilisé à la place fprintf peut-être faire quelque chose comme ceci de sorte que je pouvais créer l'équivalent d'un fichier Excel en séparant par des virgules choses, et pas seulement les nouvelles lignes. Dans ce cas, si j'avais utilisé à la place des virgules au lieu de lignes nouvelles Je pourrais littéralement ouvrir ce fichier de base de données dans Excel si je plutôt fait ressembler à ceci. En bref, maintenant que nous avons le pouvoir d'écrire dans des fichiers nous pouvons maintenant commencer la persistance des données, en le gardant dans le disque afin que nous puissions garder l'information autour encore et encore. Notez quelques autres choses qui sont maintenant un peu plus familier. Au sommet de ce fichier C nous avons un typedef parce que nous avons voulu créer un type de données qui représente un mot, si ce type est appelé mot, et à l'intérieur de cette structure il est maintenant un peu plus fantaisistes. Pourquoi est un mot composé en apparence un tableau? Qu'est-ce qu'un mot juste intuitivement? C'est un tableau de caractères. Il s'agit d'une séquence de caractères dos à dos à dos. LETTRES tous les chapeaux se trouve être nous dire arbitrairement la longueur maximale d'un mot dans le dictionnaire que nous utilisons pour Scramble. Pourquoi dois-je avoir un +1? Le caractère nul. Rappelons quand nous avons l'exemple Bananagrams nous avions besoin d'une valeur spéciale à la fin de la parole, afin de garder une trace d'où les mots effectivement pris fin, et que la spécification du jeu de problème dit ici nous associer à un mot donné une valeur booléenne, un drapeau, pour ainsi dire, vrai ou faux. Avez-vous trouvé ce mot déjà, parce que nous nous rendons compte nous avons vraiment besoin d'un moyen de se rappeler non seulement ce qui est en un mot Scramble mais si vous, l'humain, ont trouvé de sorte que si vous trouvez le mot "the" vous ne pouvez pas il suffit de taper l', entrez, la, entrez, l', entrez et obtenez 3 points, 3 points, 3 points, 3 points. Nous voulons être en mesure à la liste noire de ce mot en fixant un bool à vrai si vous avez déjà trouvé, et c'est pourquoi nous il encapsulé dans cette structure. Maintenant, ici-bas dans la lutte confuse, il ya cette autre structure appelée dictionnaire. En l'absence ici est le mot typedef car dans ce cas nous avions besoin d'encapsuler l'idée d'un dictionnaire, et un dictionnaire contient tout un tas de mots, comme le laisse entendre ce tableau, et combien de ces mots sont-ils? Eh bien, quelle que soit cette taille variable appelée dit. Mais nous avons juste besoin d'un dictionnaire. Nous n'avons pas besoin d'un type de données appelé dictionnaire. Nous avons juste besoin d'eux, de sorte qu'il s'avère en C que si vous ne dites pas typedef, tu viens de dire struct, puis à l'intérieur des accolades vous mettez vos variables, puis vous mettez le nom. Ceci est un dictionnaire déclarant variable appelée qui ressemble à ceci. En revanche, ces lignes sont la création d'une structure de données appelée réutilisable mot que vous pouvez créer plusieurs copies d', tout comme nous avons créé plusieurs copies d'élèves. Qu'est-ce que cela en fin de compte nous permettre de faire? Permettez-moi de revenir en arrière dans, disons, un exemple plus simple d'une époque plus simple, et laissez-moi ouvrir, disons, compare1.c. Le problème ici est à portée de main pour réellement décoller la couche d'une chaîne et commencer à décoller ces roues de formation car il s'avère qu'une chaîne tout ce temps comme nous l'avons promis dans la semaine 1 vraiment juste un surnom, un synonyme de la bibliothèque CS50 pour quelque chose qui ressemble un peu plus cryptique, char *, et nous avons vu cette étoile avant. Nous l'avons vu dans le contexte de fichiers. Voyons maintenant pourquoi nous avons caché ce détail pour un certain temps maintenant. Voici un fichier appelé compare1.c, et demande à l'utilisateur apparemment pour 2 chaînes, s et t, et alors il essaie de comparer ces chaînes pour l'égalité dans la ligne 26, et si elles sont égales il dit, "Vous avez tapé la même chose», et s'ils ne sont pas égaux il dit, "Vous avez tapé choses différentes." Permettez-moi aller de l'avant et exécuter ce programme. Laissez-moi aller dans mon répertoire source, faire une compare1. Il compilé correct. Permettez-moi de lancer compare1. Je vais effectuer un zoom avant, entrez. Dis quelque chose. BONJOUR. Je vais dire quelque chose de nouveau. BONJOUR. Je n'ai vraiment pas taper des choses différentes. Je vais essayer encore une fois. BYE BYE. Certainement pas différent, donc ce qui se passe ici? Eh bien, ce qui est réellement par rapport à la ligne 26? [Inaudible étudiant] Oui, il s'avère qu'une chaîne, type de données, est une sorte de mensonge. Une chaîne est un char *, mais ce qui est un char *? Un char *, comme on dit, est un pointeur, et un pointeur est effectivement une adresse, un emplacement dans la mémoire de somme, et s'il vous arrive d'avoir tapé un mot comme BONJOUR, rappelle des discussions passées de chaînes C'est comme le mot BONJOUR. Rappelez-vous qu'un mot comme BONJOUR peut être représenté comme un tableau de caractères comme ceci et ensuite avec un caractère spécial appelé à la fin du caractère nul, comme le représente \. Quelle est en fait une chaîne? Notez que ceci est nombreux blocs de mémoire, et en fait, la fin de celui-ci n'est connu qu'une fois que vous regardez à travers toute la chaîne à la recherche pour le caractère nul spéciale. Mais si c'est un morceau de mémoire de la mémoire de mon ordinateur, nous allons arbitrairement que cette chaîne juste eu de la chance, et il s'est placé dès le début de la RAM de mon ordinateur. C'est octet 0, 1, 2, 3, 4, 5, 6 ... Quand je dis quelque chose comme GetString et je fais string s = GetString ce qui est vraiment retourné? Pour ces dernières semaines, ce qui est réellement stocké dans s n'est pas cette chaîne en soi, mais dans ce cas ce qui est stocké est le numéro 0 parce que ce qui fait réellement GetString est physiquement il ne retournera une chaîne. Cela ne veut même pas vraiment de sens conceptuel. Ce qu'il fait retour est un nombre. Ce nombre est l'adresse de la mémoire BONJOUR, et la chaîne s lors, si nous décoller cette couche, chaîne n'existe pas vraiment. C'est seulement une simplification dans la bibliothèque CS50. C'est vraiment quelque chose qui s'appelle char *. Char est logique car ce qui est un mot, comme BONJOUR? Eh bien, c'est une série de caractères, une série de caractères. Char * signifie que l'adresse d'un personnage, alors qu'est-ce que cela signifie pour retourner une chaîne? Une belle façon simple de retourner une chaîne est plutôt que d'essayer de comprendre comment je reviens à 5 ou 6 différents octets laissez-moi retourner à l'adresse de l'octet? La première. En d'autres termes, permettez-moi de vous donner l'adresse d'un caractère dans la mémoire. C'est ce char * représente l'adresse d'un caractère unique dans la mémoire. Appelez cette variable s. Conserver dans s cette adresse particulière, que j'ai dit est arbitraire 0, juste pour garder les choses simples, mais en réalité, c'est généralement un plus grand nombre. Attendez une minute. Si vous êtes seulement de me donner l'adresse du premier caractère, comment puis-je savoir ce que l'adresse est du caractère second, le troisième, le quatrième et le cinquième? [Inaudible étudiant] Vous ne savez où la fin de la chaîne est par le biais de cette astuce très pratique, Ainsi, lorsque vous utilisez quelque chose comme printf, ce qui littéralement printf prend comme argument, Rappelons que nous utilisons espace réservé ce% s, puis vous passez dans la variable qui est une chaîne de stockage. Qu'est-ce que vous êtes vraiment passer est l'adresse du premier caractère de cette chaîne. Printf utilise ensuite une boucle for ou une boucle while en recevant cette adresse, par exemple, 0, permettez-moi de le faire maintenant, printf ("% s \ n", s); Quand je l'appelle printf ("% s \ n", s), ce que je suis vraiment fournir printf avec est l'adresse du premier caractère à l'art, qui dans ce cas est arbitraire H. Comment ça printf savoir exactement quoi afficher sur l'écran? La personne qui a mis en œuvre printf mis en place une boucle while ou une boucle for qui dit que ce personnage ne égaler le caractère spécial null? Sinon, imprimez-le. Que diriez-vous celui-ci? Si ce n'est pas de l'imprimer, de l'imprimer, de l'imprimer, de l'imprimer. Oh, celui-ci est spécial. Arrêtez l'impression et retourner à l'utilisateur. Et c'est littéralement tout ce qui se passe sous le capot, et c'est beaucoup à digérer le premier jour de classe, mais pour l'instant c'est vraiment la pierre angulaire de tout comprendre qui a été passe à l'intérieur de la mémoire de notre ordinateur, et, finalement, nous allons taquiner cet appart avec un peu d'aide d'un de nos amis à Stanford. Professeur Nick Parlante à Stanford a fait cette séquence vidéo merveilleuse de toutes sortes de langues différentes qui ont introduit ce Binky Claymation peu de caractère. La voix que vous allez entendre dans quelques avant-première quelques secondes est celle d'un professeur de Stanford, et vous obtenez seulement 5 ou 6 secondes de ce moment, mais c'est la note sur laquelle nous allons terminer aujourd'hui et commencer mercredi. Je vous donne Fun pointeur avec Binky, l'aperçu. [♪ ♪ Musique] [Professeur Parlante] Hey, Binky. Réveillez-vous. Il est temps pour le plaisir pointeur. [Binky] Qu'est-ce que c'est? Renseignez-vous sur les pointeurs? Oh, ma bonne femme! Nous vous voir mercredi. [CS50.TV]