[Powered by Google Translate] [Semaine 6]
[David J. Malan] [Université de Harvard]
[C'est CS50.] [CS50.TV]
>> C'est CS50, et c'est le début de la semaine 6,
si un couple de nouveaux outils sont maintenant disponibles pour vous permettre de profiter,
dont le premier est appelé CS50 style.
Les chances sont, si vous êtes comme moi ou l'un des compagnons d'enseignement,
vous avez probablement vu un programme dont le style ressemble un petit quelque chose comme ça.
Peut-être que vous commencer à couper quelques virages tard dans la nuit, ou vous allez traiter avec elle plus tard,
puis un TF ou CA sont plus durant les heures de bureau.
Ensuite, il est difficile pour nous de lire.
Eh bien, ce code est syntaxiquement correct, et il faudra compiler, et il va vraiment fonctionner.
Mais ce n'est certainement pas un 5 pour le style.
>> Mais maintenant, si nous allons dans ce répertoire ci-
et remarquez que je n'ai conditions2.c-
et je lance cette nouvelle commande, style50, sur ce conditions2.c fichier, Entrée,
remarquez que ce n'est m'a informé qu'il a été stylisée.
Gedit remarqué que le fichier a été modifié sur le disque,
et si je clique sur recharger, tous vos problèmes sont maintenant automatisées.
[Applaudissements]
C'est l'une des choses que nous avons ce week-end.
Sachez qu'il est imparfait, car il ya peu de code
qu'il suffit de ne pas être en mesure de styliser parfaitement,
mais rends compte que c'est maintenant un outil, vous pouvez profiter de
si ce n'est que pour ranger quelques-uns des accolades plus errantly placé bouclés, etc.
>> Mais plus convaincant est maintenant CS50 Check.
Avec CS50 Check, vous pouvez réellement effectuer les tests exactitude mêmes
sur votre propre code que les boursiers d'enseignement sont capables.
Il s'agit d'un utilitaire de ligne de commande qui est maintenant dans l'appareil
dès que vous faites un update50 selon
pset 4 des spécifications, et vous l'utiliser essentiellement comme ça.
Vous exécutez la commande check50.
Puis vous passez un argument de ligne de commande, ou plus généralement connu comme un interrupteur ou un drapeau.
En général, les choses qui ont traits d'union sont appelé un commutateur
à un programme de ligne de commande,-c spécifie
les contrôles que vous souhaitez exécuter.
>> Les tests que vous souhaitez exécuter sont identifiés individuellement par cette chaîne,
2012/pset4/resize.
En d'autres termes, c'est juste une chaîne arbitraire mais unique
que nous utilisons pour identifier de manière unique les tests exactitude de 4 pset.
Et puis vous spécifiez une liste séparée par des espaces des fichiers que vous souhaitez télécharger
pour CS50 Vérifier fins d'analyse.
Par exemple, si je vais dans ma solution ici pour resize.c-
Permettez-moi d'ouvrir une fenêtre de terminal plus grand-
et je vais de l'avant et de fonctionner disons check50-c 2012/pset4/resize,
et puis je aller de l'avant et de préciser les noms des fichiers,
resize.c, puis appuyez sur Entrée, il compresse,
il télécharge, il vérifie, et je vient d'échouer tout un tas de tests.
L'une en rouge en haut à gauche indique que resize.c et bmp exister.
C'était le test. Telle était la question que nous posions.
Et c'est malheureux parce que la réponse était fausse.
Le texte blanc en dessous il est dit s'attendre bmp.h d'exister, et c'est tout simplement ma faute.
J'ai oublié de le charger, donc j'ai besoin de télécharger les deux fichiers,
resize.c et bmp.h.
Mais remarquez maintenant tous les autres tests sont en jaune parce qu'ils n'ont pas exécuté,
et si le smiley est verticale, car il n'est ni heureux ni triste,
mais nous devons remédier à ce problème en rouge avant les autres contrôles seront exécutés.
>> Permettez-moi de résoudre ce problème.
Permettez-moi de faire un zoom arrière et refaire cette, cette fois avec bmp.h aussi
sur la ligne de commande, entrez, et maintenant, si tout va bien,
il va vérifier et retourner un résultat des-retenez votre souffle-
tout en vert, ce qui signifie que je fais vraiment bien sur pset 4 pour autant.
Vous pouvez voir et en déduire le texte descriptif ici
exactement ce que c'est que nous avons testé.
Nous avons testé un premier temps ne les fichiers existent?
Nous avons ensuite testé de la compilation resize.c?
Puis nous avons testé n'est-il pas redimensionner une BMP 1x1 pixel lorsque n, le facteur de redimensionnement, est 1.
Maintenant, si vous n'avez aucune idée de ce qui n est, vous une fois que vous plonger dans pset 4,
mais c'est tout simplement une vérification de cohérence pour s'assurer que vous n'êtes pas le redimensionnement
une image du tout si le facteur de redimensionnement est 1.
Si, en revanche, il redimensionne un pixel 1x1 à un 1x1 à 2x2 pixel BMP correctement
lorsque n est 2, alors même, le mien fait en conséquence.
>> En bref, cela signifie, premièrement, prendre les croisant les doigts
de l'équation à droite avant de soumettre votre pset.
Vous saurez exactement ce que vous saurez bientôt TF
quand vous allez sur la soumission de certains de ces ensembles de problèmes,
ainsi que la motivation pédagogique est vraiment à mettre
l'occasion en face de vous de sorte que lorsque vous savez a priori
qu'il ya des bugs dans votre code et des essais qui ne sont pas passés,
vous pouvez mettre dans le temps plus efficace à l'avant pour résoudre ces problèmes
plutôt que de perdre des points, obtenir la rétroaction de votre carte de TF,
et puis aller, "Ahh", comme je l'aurais compris cela.
Maintenant, au moins il ya un outil pour vous aider à trouver ça.
Il ne va pas à signaler le bug, mais il vous dira
ce qui est symptomatique d'elle.
>> Maintenant, réaliser les tests ne sont pas nécessairement exhaustive.
Juste parce que vous obtenez un écran de verdure binettes
ne signifie pas que votre code est parfait, mais cela ne signifie
qu'il a adopté certains critères prescrits par la spécification.
Parfois, nous ne divulguerons pas les chèques.
Par exemple, polar, l'un des aspects de la pset 4,
est un peu décevant si nous vous donnons
la réponse à ce qu'il est, et il ya un certain nombre de façons de révéler
qui est la personne à qui le bruit rouge.
La spécification sera toujours préciser à l'avenir pour pset 5 Onward
ce qui vérifie existent pour vous.
Vous remarquerez qu'il ya cette URL blanc au fond.
Pour l'instant, ce n'est qu'une sortie de diagnostic.
Si vous visitez cette URL, vous aurez tout un tas de fous, messages cryptiques
que vous êtes les bienvenus pour regarder à travers, mais c'est surtout pour le personnel
afin que nous puissions diagnostiquer et déboguer des bugs dans check50 lui-même.
>> Sans tarder, nous allons passer à l'endroit où nous nous sommes quittés.
CS50 bibliothèque, nous avons pris pour acquis depuis quelques semaines,
mais la semaine dernière, nous avons commencé à éplucher une des couches de celui-ci.
Nous avons commencé à mettre de côté corde en faveur de ce lieu?
[Les élèves] Char.
Char *, qui a été un char * tout ce temps,
mais maintenant, nous n'avons pas de prétendre que c'est une chaîne de type de données réel.
Au contraire, il a été un synonyme de sortes de char *,
et une chaîne de caractères est une séquence de caractères,
alors pourquoi est-il sensé pour représenter des chaînes comme char * s?
Qu'est-ce qu'un char * représenter dans le cadre de ce concept d'une chaîne?
Ouais. >> [Étudiants] Le premier caractère.
Bon, le premier caractère, mais pas tout à fait le premier caractère.
Ce sont les étudiants-[] Adresse.
Bonne, l'adresse du premier caractère.
Tout ce qui est nécessaire pour représenter une chaîne en mémoire d'un ordinateur
est tout simplement l'adresse unique de sa première octet.
Vous n'avez même pas besoin de savoir combien de temps il est
parce que comment pouvez-vous comprendre cela de manière dynamique?
[Étudiants] longueur de la chaîne.
Vous pouvez appeler longueur de la chaîne, excellent, mais comment fonctionne-t-longueur de la chaîne?
Que faut-il faire? Ouais.
[Étudiants] Continuez jusqu'à ce que vous obtenez le caractère nul.
Oui, exactement, il parcourt seulement avec une boucle for, while,
que ce soit de * jusqu'à la fin, et la fin est représentée
par \ 0, le caractère soi-disant nul, nul,
à ne pas confondre avec nulle, ce qui est un pointeur,
qui entrera dans la conversation encore aujourd'hui.
>> Nous épluché une couche de getInt, puis nous avons pris un coup d'oeil à GetString,
et de rappeler que ces deux fonctions, ou bien,
GetString, utilisait une certaine fonction
à analyser en fait, qui est, de lire ou d'analyser, d'entrée de l'utilisateur.
Et quelle est cette nouvelle fonction?
Scanf ou sscanf. Il s'agit en fait de quelques saveurs différentes.
Il ya scanf, il ya sscanf, il ya fscanf.
Pour le moment, cependant, concentrons-nous sur le plus facile à illustrer,
et laissez-moi aller de l'avant et d'ouvrir dans l'appareil
un fichier comme celui-ci, scanf1.c.
Il s'agit d'un programme super simple,
mais qui fait quelque chose que nous n'avons jamais fait
sans l'aide de la bibliothèque CS50.
Cela devient un int à partir d'un utilisateur. Comment ça marche?
Eh bien, à la ligne 16 là-bas,
remarquerez que nous déclarons un int x appelés, et à ce moment de l'histoire,
quelle est la valeur de x?
[Réponse de l'élève inaudible]
[David M.] Droite, qui sait, une valeur des déchets potentiellement, donc en 17, que nous venons de dire à l'utilisateur
me donner un numéro, s'il vous plaît, et l'étape 18 est là que ça devient intéressant.
Scanf semble emprunter une idée de printf en ce qu'il utilise ces codes de format entre guillemets.
% D est bien sûr un nombre décimal.
Mais pourquoi suis-je en passant et x au lieu de seulement x?
Le premier est correcte. Ouais.
[Réponse de l'élève inaudible]
Justement, si l'objectif de ce programme, comme le getInt fonction elle-même,
est d'obtenir un int de l'utilisateur je peux passer des fonctions
toutes les variables que je veux, mais si je ne les passer par référence
ou par adresse ou par pointeur, tous synonymes à des fins d'aujourd'hui,
alors que la fonction n'a pas la possibilité de modifier le contenu de cette variable.
Cela passerait dans une copie tout comme la version buggy de swap de
que nous avons parlé quelques fois maintenant.
>> Mais à la place, et en faisant x, je suis littéralement en passant quoi?
[Étudiants] L'adresse. >> L'adresse de x.
C'est comme dessiner une carte pour la fonction scanf appelé et dit ici,
ce sont des indications pour un morceau de la mémoire de l'ordinateur
que vous pouvez aller stocker un entier po
Pour sscanf maintenant faire
quel opérateur, ce morceau de syntaxe est ce que ça va avoir à utiliser
même si nous ne pouvons pas le voir parce que quelqu'un d'autre a écrit cette fonction?
En d'autres termes - ce que c'est?
[Étudiants] X lire.
Il va y avoir un peu de lecture, mais seulement par rapport à x ici.
Si scanf est passé l'adresse de x,
syntaxiquement, ce exploitant est tenu d'exister quelque part
à l'intérieur de la mise en œuvre de sorte que scanf scanf
peut écrire un nombre à 2 à cette adresse?
Ouais, et alors le fichier *.
Rappelons que le * est notre opérateur de déréférencement, ce qui signifie essentiellement y aller.
>> Une fois que vous avez été remis une adresse, comme c'est le cas ici,
scanf est sans doute, si nous effectivement regardé autour de son code source,
fait * x ou l'équivalent d'aller effectivement à cette adresse et mettre un peu de valeur là-bas.
Maintenant, quant à la façon dont scanf prend son entrée à partir du clavier,
Nous allons saluer nos mains pour aujourd'hui.
Simplement supposer que le système d'exploitation permet de parler sscanf
au clavier de l'utilisateur, mais à ce point maintenant à la ligne 19,
quand nous suffit d'imprimer x, il semble être le cas
que scanf a mis en int x.
C'est exactement la façon dont fonctionne scanf, et de rappeler la semaine dernière
c'est exactement ce que GetString et getInt et son autre famille de fonctions
fonctionne en fin de compte, mais avec de légères différences comme sscanf,
ce qui signifie analyser une chaîne au lieu du clavier.
Mais nous allons jeter un oeil à un peu de variance de cela.
En scanf2, j'ai vraiment merdé.
Quel est le problème et je vais cacher le commentaire qui explique que très
ce qui ne va pas avec ce programme, la version 2?
Soyez aussi technique que possible cette fois.
Il semble assez bon.
C'est très joliment indenté, mais-
ok, que diriez-vous il faut bien tailler jusqu'à plus courtes questions?
Ligne 16. Quelle est la ligne 16 fait en anglais, mais précise technique?
Obtenir un peu maladroit. Oui, Michael.
[Étudiants] Il pointe vers la première lettre d'une chaîne.
>> Bon, à proximité. Permettez-moi de peaufiner un petit peu.
Attirant l'attention sur la première lettre d'une chaîne, vous déclarez une variable appelée tampon
qui pointe vers la première adresse d'une chaîne,
ou plutôt, qui pointera plus particulièrement à un char.
Remarquez que ce n'est pas réellement pointant nulle part parce qu'il n'y a pas d'opérateur d'affectation.
Il n'ya pas de signe égal, tout ce que nous faisons est l'allocation du tampon variable appelée.
Il se trouve que 32 bits parce que c'est un pointeur,
et le contenu du tampon sans doute finalement
contiendra l'adresse d'un char, mais pour l'instant, ce qui ne contiennent tampon?
Juste un peu faux, qui sait, une valeur ordures,
parce que nous n'avons pas explicitement initialisée, donc nous ne devrions pas présumer de rien.
Bon, alors maintenant la ligne 17 est-ce que la ligne 17 ne faire?
Peut-être que vous réchauffera jusqu'à présent.
Il imprime une chaîne, pas vrai?
Elle imprime à cordes s'il vous plaît.
>> La ligne 18 est une sorte de familier maintenant que nous venons de voir une variance de cette
mais avec un code de format différent, à la ligne 18,
nous disons ici scanf est l'adresse d'un bloc de mémoire.
Je veux que tu sonner dans une chaîne, comme le laisse entendre par% s,
mais le problème est que nous n'avons pas fait un certain nombre de choses ici.
Quel est l'un des problèmes?
[Étudiants] Il essaie de déréférencer un pointeur NULL.
Bon, pointeurs nuls ou tout simplement ailleurs inconnu.
Vous n'êtes remise scanf une adresse, mais vous venez de dire il ya un instant
que cette adresse est une valeur ordures parce que nous n'avons pas réellement l'attribuer à quelque chose,
et si vous dites scanf effectivement aller mettre une chaîne ici,
mais nous ne savons pas où est ici encore,
donc nous n'avons pas réellement la mémoire allouée pour le tampon.
Par ailleurs, ce que vous êtes aussi même pas dire scanf?
Supposons que ce fut un morceau de mémoire, et ce n'était pas une valeur ordures,
mais vous n'êtes pas encore dire quelque chose d'important scanf.
[Étudiants] Lorsqu'il est fait, l'esperluette.
Ampersand, dans ce cas, ce n'est pas grave.
Parce tampon est déjà déclaré comme un pointeur
avec la pièce * de la syntaxe, nous n'avons pas besoin d'utiliser esperluette
parce que c'est déjà une adresse, mais je pense que je l'ai entendu ici.
[Étudiants] Quelle est sa taille?
Bon, nous ne disons pas scanf l'ampleur de ce tampon est,
ce qui signifie que même si le tampon était un pointeur,
nous disons scanf, mettre une chaîne ici,
mais ici pourrait être de 2 octets, il pourrait être de 10 octets, ce pourrait être un méga-octet.
Scanf n'a aucune idée, et parce que c'est un morceau de mémoire
sans doute, ce n'est pas une chaîne pour le moment.
C'est seulement une fois que vous écrivez chaîne de caractères et un 0 \ à ce morceau de mémoire.
Maintenant, c'est juste une portion de mémoire.
Scanf ne saurez pas quand arrêter d'écrire à cette adresse.
>> Si vous vous rappelez quelques exemples dans le passé où je aléatoirement tapés sur le clavier
en essayant de déborder un tampon, et nous avons parlé vendredi au sujet exactement cela.
Si un adversaire injecte quelque sorte dans votre programme un mot beaucoup plus grand
ou phrase ou alors vous vous attendiez, vous pouvez dépassement
un morceau de mémoire, ce qui peut avoir des conséquences néfastes,
comme la prise en charge de l'ensemble du programme lui-même.
Nous avons besoin de résoudre ce problème en quelque sorte.
Permettez-moi de faire un zoom arrière et aller dans la version 3 de ce programme.
C'est un peu mieux.
Dans cette version, notez la différence.
A la ligne 16, je suis à nouveau déclarer une variable appelée tampon,
mais qu'est-ce maintenant?
C'est un tableau de 16 caractères.
C'est une bonne chose parce que cela signifie que je peux maintenant dire scanf
voici un morceau de mémoire réelle.
Vous pouvez presque penser à des tableaux comme étant des pointeurs maintenant,
même si elles ne sont pas réellement équivalente.
Ils vont se comporter différemment dans des contextes différents.
Mais c'est certainement le cas que le tampon est le référencement
16 caractères contigus parce que c'est ce tableau est un
et depuis quelques semaines maintenant.
>> Ici, je dis scanf voici un morceau de mémoire.
Cette fois-ci, c'est en fait un morceau de mémoire,
mais pourquoi est ce programme encore exploitable?
Qu'est-ce qui ne va pas encore?
Je l'ai dit de me donner 16 octets, mais-
[Étudiants] Que faire si ils tapent dans plus de 16?
Justement, si l'utilisateur tape 17 caractères ou 1700 caractères?
En fait, nous allons voir si nous ne pouvons pas trébucher sur cette erreur maintenant.
C'est mieux mais pas parfait.
Permettez-moi aller de l'avant et exécutez make scanf3 pour compiler ce programme.
Permettez-moi de lancer scanf3, String s'il vous plaît: bonjour, et il semble bien se passer.
Je vais essayer un peu plus long, bonjour.
Bon, on ne bonjour là-bas comment allez-vous aujourd'hui, Entrée.
Mise en sorte de chance ici, nous allons dire bonjour comment allez-vous y.
Merde.
Ok, donc nous avons été chanceux. Voyons voir si nous ne pouvons pas résoudre ce problème.
Non, ça ne va pas me laisser copier.
Essayons encore une fois.
Tout droit, stand by.
Nous allons voir combien de temps je peux faire semblant de se concentrer tout en faisant cela.
Merde. C'est plutôt le cas, effectivement.
Nous y voilà.
Point de fait.
>> Ceci, gênant mais il est aussi, il est également l'une des sources de grande confusion
lors de l'écriture des programmes qui ont des bugs parce qu'ils se manifestent
seulement de temps en temps, parfois.
La réalité est que même si votre code est complètement rompu,
elle ne peut être complètement rompu de temps en temps
parce que parfois, essentiellement ce qui se passe est le système d'exploitation alloue
un peu plus de mémoire que vous avez réellement besoin pour une raison quelconque,
et que personne d'autre utilise la mémoire juste après votre morceau de 16 caractères,
donc si vous allez à 17, 18, 19, peu importe, ce n'est pas une grosse affaire.
Maintenant, l'ordinateur, même si elle ne tombe pas en panne à ce moment-là,
pourrait éventuellement utiliser le numéro d'octet 17 ou 18 ou 19 pour autre chose,
au cours de laquelle pointer vos données que vous mettez là-bas, mais excessivement longue,
va se faire écraser éventuellement par une autre fonction.
Il ne va pas nécessairement de rester intact,
mais il ne sera pas nécessairement la cause d'un défaut seg.
Mais dans ce cas, je me suis finalement fourni suffisamment de caractères
essentiellement que je dépassé mon segment de mémoire, et bam,
le système d'exploitation a dit: «Désolé, ce n'est pas une erreur de segmentation bon."
>> Et nous allons voir maintenant si ce qui reste ici dans mon répertoire-
remarquerez que j'ai ce fichier ici, le noyau.
Notez que ceci est encore appelé un core dump.
Il s'agit essentiellement d'un fichier qui contient le contenu de la mémoire de votre programme
à l'endroit où il s'est écrasé,
et juste pour essayer un petit exemple ici me laisser aller ici
et exécuter gdb sur scanf3 puis spécifiez un troisième argument appelé core,
et noter ici que si je liste le code,
nous serons en mesure, comme d'habitude avec gdb pour commencer à marcher à travers ce programme,
et je peux le faire fonctionner et dès que j'ai touché, comme avec la commande étape dans gdb-
dès que j'ai touché la ligne potentiellement buggé après avoir tapé dans une chaîne énorme,
Je vais être en mesure de réellement identifier ici.
Plus à ce sujet, même si, dans la section en termes de core dump
et ainsi de suite de sorte que vous pouvez réellement fouiller à l'intérieur de la core dump
et de voir sur quelle ligne du programme que vous n'avez pas.
Toutes les questions, puis sur des pointeurs et des adresses?
Parce que, aujourd'hui, nous allons commencer en prenant pour acquis que ces choses existent
et nous savons exactement ce qu'ils sont.
Oui.
>> [Étudiants] Comment se fait que vous n'avez pas à mettre une esperluette à côté de la partie-
Bonne question.
Comment se fait je n'ai pas besoin de mettre une esperluette à côté du tableau de caractères comme je le faisais auparavant
avec la plupart de nos exemples?
La réponse courte est des tableaux sont un peu spéciale.
Vous pouvez presque penser un tampon comme étant réellement une adresse,
et il se trouve être le cas que la notation crochet
est une commodité afin que nous puissions aller dans le support 0, tranche 1,
tranche 2, sans avoir à utiliser la notation *.
C'est un peu un mensonge car les tableaux et les pointeurs
sont, en fait, un peu différent, mais ils peuvent souvent, mais pas toujours être utilisés de façon interchangeable.
En bref, quand une fonction attend un pointeur vers un bloc de mémoire,
vous pouvez passer soit une adresse qui a été renvoyée par malloc,
et nous verrons malloc nouveau avant longtemps, ou vous pouvez lui passer le nom d'un tableau.
Vous n'avez pas à le faire et commercial avec des tableaux parce qu'ils sont déjà
essentiellement comme des adresses.
C'est la seule exception.
Les crochets rendre spécial.
>> Pouvez-vous mettre une esperluette à côté du tampon?
Pas dans ce cas.
Cela ne marcherait pas parce que, encore une fois, de cette affaire coin
où les tableaux ne sont pas tout à fait en réalité adresses.
Mais nous allons peut-être revenir à ce que d'ici peu d'autres exemples.
Essayons de résoudre un problème ici.
Nous avons une structure de données que nous avons utilisé pendant un certain temps connu sous le nom d'un tableau.
Affaire au point, c'est ce que nous venons d'avoir.
Mais les tableaux ont une certaine aspects positifs et négatifs.
Les tableaux sont beaux pourquoi?
Qu'est-ce une chose que vous aimez, dans la mesure où vous aimez les tableaux-sur les tableaux?
Ce qui est pratique à leur sujet? Quel est-il intéressant?
Pourquoi avons-nous les présenter en premier lieu?
Ouais.
[Étudiants] Ils peuvent stocker beaucoup de données, et vous n'avez pas à utiliser un ensemble de chose.
Vous pouvez utiliser une section.
Bon, avec un tableau, vous pouvez stocker beaucoup de données,
et vous n'avez pas forcément besoin d'utiliser tout cela, afin que vous puissiez overallocate,
ce qui peut être pratique si vous ne savez pas à l'avance combien de quelque chose à attendre.
>> GetString est un parfait exemple.
GetString, écrit par nous, n'a aucune idée de combien de caractères à attendre,
donc le fait que nous pouvons allouer des blocs de mémoire contigus est bon.
Les tableaux aussi résoudre un problème que nous avons vu il ya quelques semaines maintenant
où votre code commence à se transformer en quelque chose de très mal conçu.
Rappelez-vous que j'ai créé une structure étudiant du nom de David,
puis qui était en fait une alternative, cependant,
d'avoir un nom de variable et une autre variable appelée s'appelait, je crois, maison,
et une autre variable appelée ID parce que dans cette histoire que j'ai ensuite voulu introduire quelque chose d'autre
comme Rob dans le programme, alors j'ai décidé d'attendre une minute,
J'ai besoin de renommer ces variables.
Appelons le mien nom1, ID1, house1.
Appelons Rob nom2, casa2, ID2.
Mais attendez une minute, ce à propos de Tommy?
Ensuite, nous avons eu trois autres variables.
Nous avons introduit quelqu'un d'autre, quatre ensembles de variables.
Le monde a commencé à déraper très rapidement,
donc nous avons introduit les structures, et ce qui est convaincant sur une structure?
Qu'est-ce qu'un struct C te laisser faire?
C'est vraiment bizarre aujourd'hui.
Quoi? >> [Réponse de l'élève inaudible]
Oui, précisément, typedef vous permet de créer un nouveau type de données,
et structure, le mot-clé struct, vous permet d'encapsuler
pièces conceptuellement liés ensemble de données
et ensuite les appeler quelque chose comme un étudiant.
>> C'était bien parce que maintenant nous pouvons modéliser
tri beaucoup plus de cohérence conceptuelle de la notion d'un étudiant dans une variable
plutôt que de manière arbitraire comportant une pour une chaîne, une pour une identification, et ainsi de suite.
Les tableaux sont bien car ils nous permettent de commencer à nettoyer notre code.
Mais ce qui est un inconvénient désormais d'un tableau?
Que pouvez-vous pas faire? Ouais.
[Étudiants] Vous devez savoir comment elle est grande.
Vous devez savoir comment elle est grande, il est donc une sorte de douleur.
Ceux d'entre vous ayant une expérience préalable de la programmation savons que dans beaucoup de langues,
comme Java, vous pouvez demander un morceau de mémoire, en particulier un tableau,
quelle est la taille que vous, avec une longueur, la propriété, pour ainsi dire, et c'est vraiment pratique.
En C, vous ne pouvez plus appeler strlen sur un tableau générique
car strlen, comme le mot l'indique, est que pour les chaînes,
et vous pouvez trouver la longueur d'une chaîne à cause de cette convention humaine
d'avoir un 0 \, mais un tableau, de manière plus générique, c'est juste un morceau de mémoire.
Si c'est un tableau d'entiers, il ne va pas être un caractère spécial
à la fin vous attend.
Vous devez vous rappeler de la longueur d'un tableau.
Un autre inconvénient d'un tableau élevé sa tête en lui-même GetString.
Ce qui est un autre inconvénient d'un tableau?
Monsieur, que vous et moi aujourd'hui.
[Réponse de l'élève inaudible] >> C'est quoi?
Il a déclaré sur la pile.
Okay, a déclaré sur la pile. Pourquoi tu n'aimes pas ça?
[Étudiants] Parce qu'il se réutilisé.
Il se réutilisé.
Bon, si vous utilisez un tableau à allouer de la mémoire,
vous ne pouvez pas, par exemple, le retourner parce que c'est sur la pile.
D'accord, c'est un désavantage.
Et que diriez-vous une autre avec un tableau?
Une fois que vous l'affecter, vous êtes un peu vissé si vous avez besoin de plus d'espace
que cette matrice a.
>> Ensuite, nous avons introduit, rappel, malloc, qui nous a donné la possibilité d'allouer dynamiquement de la mémoire.
Mais que faire si nous avons essayé un monde tout à fait différent?
Que faire si nous voulions résoudre quelques problèmes ces
donc nous avons au lieu-ma plume s'est endormi ici-
si on plutôt voulu essentiellement créer un monde qui n'est plus comme ça?
Il s'agit d'un tableau, et, bien sûr, ce genre de détériore une fois nous avons atteint la fin du tableau,
et maintenant je n'ai plus d'espace pour un autre entier ou un autre personnage.
Que si l'on sorte de manière préventive dites bien, pourquoi ne pas se détendre
cette condition que tous ces blocs de mémoire contigus être dos à dos,
et pourquoi pas, quand j'ai besoin d'un int ou un char,
donnez-moi de l'espace pour l'un d'eux?
Et quand j'ai besoin d'une autre, donne-moi un autre espace,
et quand j'ai besoin d'une autre, donne-moi un autre espace.
L'avantage de ce qui est maintenant que si quelqu'un d'autre
prend la mémoire ici, pas une grosse affaire.
Je vais prendre ce morceau de mémoire supplémentaire ici et puis celle-ci.
>> Maintenant, le seul hic, c'est que cela se sent presque comme je l'ai
tout un tas de différentes variables.
Cela ressemble à cinq variables différentes potentiellement.
Mais que faire si nous voler une idée à partir de chaînes
par lequel nous en quelque sorte le lien entre ces choses ensemble conceptuellement, et si je fait cela?
C'est ma flèche très mal rédigé.
Mais supposons que chacun de ces segments de mémoire
souligné à l'autre, et ce mec, qui n'a pas de frère ou sœur à sa droite,
n'a pas de flèche par exemple.
C'est en fait ce qu'on appelle une liste chaînée.
Il s'agit d'une nouvelle structure de données qui nous permet d'allouer un bloc de mémoire,
puis un autre, puis un autre, puis un autre, chaque fois que nous voulons
au cours d'un programme, et nous nous rappelons qu'ils sont tous en quelque sorte liée à
par littéralement les enchaîner ensemble, et nous l'avons fait de façon imagée ici avec une flèche.
Mais dans le code, ce qui serait le mécanisme par lequel vous pouviez vous connecter,
presque comme Scratch, un morceau à un autre morceau?
Nous pourrions utiliser un pointeur, pas vrai?
Parce que vraiment la flèche qui va de la place en haut à gauche,
ce gars-là à celui-ci, pourrait contenir à l'intérieur de ce carré
pas seulement certains entiers, et pas seulement quelques-uns char, mais que faire si j'ai effectivement alloué
un peu plus d'espace de sorte que maintenant,
chacun de mes morceaux de la mémoire, même si cela va me coûter,
regarde maintenant un peu plus rectangulaire dont l'un des blocs de mémoire
est utilisée pour un certain nombre, comme nombre 1,
et puis si ce gars stocke le numéro 2,
ce bloc de mémoire autre est utilisé pour une flèche,
ou, plus concrètement, un pointeur.
Et si je stocker le numéro 3 par ici pendant que je l'utiliser pour pointer vers ce type,
et maintenant ce mec, supposons que je ne veux trois morceaux tels de mémoire.
Je vais tracer une ligne à travers elle, indiquant nulle.
Il n'ya pas de personnage supplémentaire.
>> En effet, c'est ainsi que nous pouvons prendre pour la mise en œuvre
quelque chose qui s'appelle une liste chaînée.
Une liste chaînée est une nouvelle structure de données, et c'est un tremplin vers
structures de données beaucoup plus fantaisistes qui commencent à résoudre des problèmes
le long des lignes de type Facebook et Google problèmes de type problèmes
où vous avez d'énormes ensembles de données, et il ne le coupe
pour tout ranger côte à côte et utiliser quelque chose comme recherche linéaire
ou même quelque chose comme binaire de recherche.
Vous en voulez encore meilleurs temps de fonctionnement.
En fait, l'un des Saint Graal nous parlerons plus tard cette semaine ou la suivante
est un algorithme dont le temps d'exécution est constant.
En d'autres termes, il faut toujours la même quantité de temps, peu importe
la taille de l'entrée est, et ce serait effectivement convaincants,
plus encore que quelque chose logarithmique.
Quel est ce sur l'écran ici?
Chacun des rectangles est exactement ce que je viens a la main.
Mais la chose tout le chemin sur la gauche est une variable spéciale.
Ça va être un pointeur unique parce que le gotcha une
avec une liste chaînée, car ces choses sont dites,
c'est que vous avez à accrocher sur une extrémité de la liste chaînée.
>> Tout comme avec une chaîne, vous devez connaître l'adresse du premier caractère.
Beaucoup même pour les listes chaînées.
Vous devez connaître l'adresse du premier bloc de mémoire
parce que de là, vous pouvez atteindre tous les autres.
Baisse.
Quel prix payons-nous pour cette polyvalence d'avoir une dynamique
importante structure de données que si jamais nous avons besoin de plus de mémoire, très bien,
juste allouer un plus gros morceau et d'en tirer un pointeur de
l'ancienne à la nouvelle queue de la liste?
Ouais.
[Étudiants] Il occupe un espace deux fois plus cher.
Il occupe un espace deux fois plus, donc c'est vraiment un inconvénient, et nous avons vu ce
compromis avant entre temps et l'espace et la flexibilité
où maintenant, nous n'avons pas besoin de 32 bits pour chacun de ces nombres.
Nous avons vraiment besoin de 64, 32 pour le nombre et 32 ​​pour le pointeur.
Mais bon, j'ai 2 Go de RAM.
En ajoutant un autre 32 bits ici et là ne semble pas que les grandes d'un accord.
Mais pour les ensembles de données volumineux, il ajoute certainement à littéralement deux fois plus.
Ce qui est un autre inconvénient maintenant, ou ce qui est la particularité que nous abandonnons,
si l'on représente des listes de choses avec une liste chaînée et non un tableau?
[Étudiants] Vous ne pouvez pas traverser vers l'arrière.
Vous ne pouvez pas traverser vers l'arrière, de sorte que vous êtes un peu vissé si vous êtes à pied
de gauche à droite à l'aide d'une boucle ou d'une boucle tandis que
et puis vous vous rendez compte, "Oh, je veux revenir au début de la liste."
Vous ne pouvez pas parce que ces pointeurs aller de gauche à droite, comme les flèches indiquent.
>> Maintenant, vous pouvez rappeler le début de la liste avec une autre variable,
mais c'est une complexité à garder à l'esprit.
Un tableau, peu importe à quel point vous allez, vous pouvez toujours faire moins, moins, moins, moins
et retournez d'où vous venez.
Ce qui est un autre inconvénient ici? Ouais.
[Question étudiant inaudible]
Vous pourriez, si vous avez réellement vient de proposer une structure de données appelée une liste doublement chaînée,
et en effet, il faut ajouter un autre pointeur vers chacun de ces rectangles
qui va l'autre direction, la tête de laquelle
est maintenant que vous pouvez parcourir dans les deux sens,
l'inconvénient de ce qui est maintenant vous utilisez trois fois plus de mémoire que nous avons utilisé pour
et aussi ajouter de complexité en termes de code que vous devez écrire pour y arriver.
Mais ce sont peut-être tout compromis très raisonnables, si la reprise est plus important.
Ouais.
[Étudiants] Vous pouvez également avoir une liste 2D lié.
Bon, vous ne pouvez pas vraiment avoir une liste liée 2D.
Vous pourriez. Ce n'est pas aussi facile que d'un tableau.
Comme un tableau, vous ouvre la parenthèse, le support fermé, le support ouvert, fermé support,
et vous aurez une structure 2-dimensionnelle.
Vous pouvez implémenter une liste 2-dimensionnelle liée
si vous faites module que vous proposé-un pointeur troisième chacune de ces choses,
et si vous pensez à une autre liste venant à vous de style 3D
à partir de l'écran pour nous tous, qui est juste une autre chaîne en quelque sorte.
On pourrait le faire, mais ce n'est pas aussi simple que de taper crochet ouvrant, crochet. Ouais.
[Question étudiant inaudible]
Bon, c'est donc un kicker réel.
>> Ces algorithmes que nous avons langui plus, comme oh, recherche binaire,
vous pouvez rechercher un tableau de nombres sur la carte
ou un annuaire téléphonique beaucoup plus rapidement si vous utilisez diviser pour mieux régner
et un algorithme de recherche binaire, binaire de recherche, mais nécessitait deux hypothèses.
Un, que les données ont été classées.
Maintenant, nous pouvons sans doute garder cette triées,
alors peut-être que ce n'est pas un problème, mais également supposé recherche binaire
que vous avez eu accès aléatoire à la liste des numéros,
et un tableau vous permet d'avoir accès aléatoire, et par l'accès aléatoire,
Je veux dire si on vous donne un tableau, combien de temps vous faut-il
pour se rendre à tranche 0?
Une opération, il suffit d'utiliser [0] et que vous êtes là.
Combien d'étapes faut-il pour se rendre à l'emplacement 10?
Une étape, vous allez simplement dans [10] et vous y êtes.
En revanche, comment obtenez-vous à l'entier le 10ème d'une liste chaînée?
Vous devez commencer au début parce que vous souvenant seulement
le début d'une liste chaînée, tout comme une chaîne on se souvient
par l'adresse de son premier caractère, et de constater que 10th Int
ou que 10ème caractère dans une chaîne, vous devez rechercher le tout foutu.
>> Encore une fois, nous ne sommes pas résoudre tous nos problèmes.
Nous introduisons de nouvelles, mais cela dépend vraiment de ce que vous essayez de concevoir pour.
En termes de mise en œuvre, nous pouvons emprunter une idée de cette structure étudiant.
La syntaxe est très similaire, sauf que maintenant, l'idée est un peu plus abstrait
que la maison et le nom et l'ID.
Mais je vous propose que nous pourrions avoir une structure de données en C
qui est appelé nœud, comme le dernier mot sur la diapositive indique,
à l'intérieur d'un nœud et un nœud est juste un conteneur générique en informatique.
Il est généralement représenté comme un cercle ou un carré ou un rectangle comme nous l'avons fait.
Et dans cette structure de données, nous avons un int, n,
de sorte que c'est le nombre que je veux pour stocker.
Mais quelle est cette seconde ligne, struct noeud * suivant?
Pourquoi est-ce exact, ou le rôle que joue cette chose,
même si c'est un peu obscur à première vue?
Ouais.
[Réponse de l'élève inaudible]
Exactement, le genre * de butin que c'est un pointeur de quelque sorte.
Le nom de ce pointeur est arbitrairement prochaine,
mais nous aurions pu l'appelait tout ce qu'on veut, mais qu'est-ce que ce point pointeur?
[Étudiants] Un autre noeud. >> Exactement, il pointe vers un autre nœud tel.
>> Maintenant, c'est une sorte de curiosité de C.
Rappelons que C est lu par un compilateur haut en bas, de gauche à droite,
ce qui signifie que si-c'est un peu différent de ce que nous avons fait avec l'étudiant.
Lorsque nous avons défini un étudiant, nous avons fait n'a pas mis un mot là-bas.
Il vient d'être dit typedef.
Puis nous avons eu int id string name,, string maison,
puis élève au bas de la structure.
Cette déclaration est un peu différent parce que,
à nouveau, le compilateur C est un peu stupide.
Il va seulement à lire de haut en bas,
si elle atteint la 2ème ligne ici
où à côté est déclaré et il voit, oh, voici une variable appelée prochaine.
Il s'agit d'un pointeur vers un noeud de structure.
Le compilateur va réaliser ce qui est un nœud de structure?
Je n'ai jamais entendu parler de cette chose avant,
parce que le mot node pourraient autrement ne pas apparaître
jusqu'à ce que le fond, il ya donc cette redondance.
Vous avez à dire struct noeud ici, que vous pouvez ensuite raccourcir plus tard
grâce à typedef ici-bas, mais ce n'est parce
on référençant la structure elle-même à l'intérieur de la structure.
C'est la chasse aux sorcières celui-là.
>> Quelques problèmes intéressants vont se poser.
Nous avons une liste de nombres. Comment pouvons-nous insérer dans tout cela?
Comment pouvons-nous chercher? Comment peut-on supprimer de lui?
Surtout maintenant que nous devons gérer l'ensemble de ces pointeurs.
Vous pensiez que les pointeurs étaient en quelque sorte hallucinante
quand vous avez eu l'un d'eux essaie juste de lire un int à elle.
Maintenant, nous devons manipuler vaut une liste entière.
Pourquoi ne pas prendre notre pause de 5 minutes ici, et ensuite nous allons apporter
certaines personnes sur scène pour faire exactement cela.
>> C est beaucoup plus amusant quand il est mis en scène.
Qui aurait littéralement tiens à être le premier?
Bon, allez vers le haut. Vous êtes le premier.
Qui voudrait être de 9? Ok, 9.
Que diriez-9? 17?
Une petite clique ici. 22 et 26 de la rangée avant.
Et puis, que diriez-vous à quelqu'un là-bas pointé.
Vous êtes 34. Okay, 34, allez vers le haut.
La première est là-bas. Bon, tous les quatre d'entre vous.
Et qui sommes-nous dire pour 9?
Qui est notre 9?
Qui veut vraiment être de 9? Bon, allez, soit 9.
Nous y voilà.
34, nous allons vous rencontrer là-bas.
La première partie est de faire vous-même ressembler à ça.
26, 22, 17, bon.
Si vous pouvez supporter sur le côté, parce que nous allons vous malloc dans un instant.
>> Bien, bien.
Bon, excellent, nous allons donc poser quelques questions ici.
Et en fait, c'est quoi ton nom? >> Anita.
Anita, d'accord, viens par ici.
Anita va nous aider à résoudre sorte d'une question assez simple en premier,
qui est comment trouvez-vous si oui ou non une valeur est dans la liste?
Maintenant, remarquez que le premier, représenté ici par Lucas,
est un peu différent, et donc son morceau de papier est volontairement de côté
car ce n'est pas tout à fait aussi grand et ne prend pas autant de bits,
même si, techniquement, il a le même format de papier juste tourné.
Mais il est un peu différent en ce sens qu'il n'est que de 32 bits pour un pointeur,
et tous ces gars-là sont 64 bits, dont la moitié est du nombre, la moitié de ce qui est un pointeur.
Mais le pointeur n'est pas représenté, donc si vous pouviez un peu maladroitement
utiliser la main gauche pour pointer vers la personne à côté de vous.
Et vous êtes le numéro 34. Quel est ton nom?
Ari.
Ari, donc en fait, tenir le papier dans la main droite et la main gauche va vers le bas.
Vous déclarez nul sur la gauche.
>> Maintenant, notre image humaine est très cohérent.
C'est en fait la façon dont fonctionne pointeurs.
Et si vous pouvez froisser un peu de cette façon que je ne suis pas dans votre chemin.
Anita ici, trouvez-moi le numéro 22,
mais supposent une contrainte de ne pas les humains brandissant des bouts de papier,
mais il s'agit d'une liste, et vous avez seulement Lucas pour commencer
parce qu'il est littéralement le premier pointeur.
Supposons que vous êtes vous-même un pointeur, et si vous aussi vous avez la possibilité de pointer vers quelque chose.
Pourquoi ne pas commencer en pointant exactement ce que Lucas est dirigée vers?
Bon, et permettez-moi de mettre en oeuvre cette sur ici.
Juste pour le plaisir de la discussion, permettez-moi de tirer vers le haut d'une page blanche ici.
Comment pouvez-vous épeler votre nom? >> Anita.
Bon, Anita.
Disons noeud * anita = lucas.
Eh bien, il ne faut pas vous appeler lucas. On devrait appeler en premier.
Pourquoi est-ce, en fait, conformes à la réalité ici?
Un, premier existe déjà.
Première a été attribué sans doute quelque part ici.
* Noeud d'abord, et il a été alloué une liste quelque part.
Je ne sais pas comment c'est arrivé. Cela se passait avant la classe a commencé.
Cette liste chaînée de l'homme a été créé.
Et maintenant, à ce moment de l'histoire, tout cela va apparemment plus tard sur Facebook-
à ce stade de l'histoire, Anita a été initialisé pour être égale à la première,
ce qui ne veut pas dire que les points de Anita à Lucas.
Au contraire, elle montre ce qu'il fait à
parce que la même adresse que c'est à l'intérieur de Lucas 32 bits - 1, 2, 3 -
est maintenant aussi à l'intérieur de Anita 32 bits - 1, 2, 3.
>> Maintenant, trouver 22. Comment feriez-vous pour cela?
Qu'est-ce que Point? >> Pour que ce soit.
Pointez sur que ce soit, alors allez-y et agir du mieux que vous le pouvez ici.
Bon, bon, et maintenant vous pointez-quel est ton nom avec 22?
Ramon. >> Ramon, si Ramon est maintenant de 22.
Vous avez maintenant fait un chèque.
Est-ce que Ramon == 22, et si c'est le cas, par exemple, on peut retourner true.
Laissez-moi-tout ces gars-là rester ici un peu maladroitement-
laissez-moi faire quelque chose rapidement comme bool trouver.
Je vais aller de l'avant et de dire (nœud de la liste *, int n).
Je reviens tout de suite avec vous les gars. Je viens d'écrire un peu de code.
Et maintenant, je vais aller de l'avant et de faire, noeud * = anita liste.
Et je vais aller de l'avant et de dire tout (anita! = NULL).
>> La métaphore ici devient un peu tendu, mais tout (anita! = NULL), qu'est-ce que je veux faire?
J'ai besoin de faire référence aux
l'entier Anita est pointé.
Dans le passé, lorsque nous avons eu des structures, ce qui est un nœud,
nous avons utilisé la notation par point, et nous dire quelque chose comme
anita.n, mais le problème ici est que Anita n'est pas une structure en soi.
Quelle est-elle?
Elle est un pointeur, donc vraiment, si nous voulons utiliser cette notation pointée-
et cela va se pencher volontairement un peu obscur-
nous devons faire quelque chose comme aller à gauche tout ce Anita est dirigée vers
et ensuite obtenir le champ appelé n.
Anita est un pointeur, mais ce qui est anita *?
Que trouvez-vous quand vous allez à ce Anita est dirigée vers?
Une structure, un nœud et un nœud, le rappel, a un champ nommé n
car il a, rappel, ces 2 champs, à côté et n,
que nous avons vu il ya un instant ici.
>> Pour imiter cette réalité dans le code,
nous pourrions faire cela et dire if ((* anita). n == n), n que je suis à la recherche.
Notez que la fonction a été adoptée dans le nombre je me soucie.
Ensuite, je peux aller de l'avant et faire quelque chose comme vrai retour.
Sinon, si ce n'est pas le cas, qu'est-ce que je veux faire?
Comment puis-je traduire pour coder ce Anita l'a fait de manière intuitive en se promenant dans la liste?
Que dois-je faire ici pour simuler Anita prendre cette mesure à la gauche, c'est pas à gauche?
[Réponse de l'élève inaudible] >> Qu'est-ce que c'est?
[Réponse de l'élève inaudible]
Bon, pas une mauvaise idée, mais dans le passé, lorsque nous avons fait cela, nous avons fait anita + +
parce que ce serait ajouter le numéro 1, Anita,
qui seraient normalement pointer vers la prochaine personne, comme Ramon,
ou la personne à côté de lui, ou de la personne à côté de lui sur toute la ligne.
Mais ce n'est pas tout à fait bon ici, car qu'est-ce que cette chose ressemble à la mémoire?
Non pas que. Nous devons désactivez cette option.
Elle ressemble à ceci en mémoire, et même si j'ai dessiné 1 et 2 et 3 près de l'autre,
si nous avons vraiment simuler ce-pouvez-vous les gars, tout en montrant les mêmes personnes,
certains d'entre vous peut prendre un peu de recul aléatoire, certains d'entre vous une étape aléatoire de l'avant?
>> Ce désordre est encore une liste chaînée,
mais ces gars-là pourrait être n'importe où dans la mémoire,
de sorte anita + + ne va pas travailler pourquoi?
Quel est l'emplacement anita + +?
Qui sait.
C'est une autre valeur que se trouve juste à être interposé
parmi tous ces nœuds par hasard parce que nous ne sommes pas en utilisant un tableau.
Nous avons affecté chacun de ces nœuds individuellement.
Bon, si vous les gars vous pouvez nettoyer vers le haut.
Permettez-moi de proposer qu'au lieu de anita + +, nous avons plutôt faire anita se-
Eh bien, pourquoi ne pas aller à tout ce qui est dirigée vers Anita puis faire. prochaine?
En d'autres termes, nous allons à Ramon, qui est maintenant le numéro 22,
puis. prochaine comme si Anita serait copier son pointeur main gauche.
Mais elle ne voulait pas aller plus loin que Ramon car nous avons trouvé 22.
Mais ce serait l'idée. Maintenant, c'est un gâchis terrible dieu.
Honnêtement, personne ne pourra jamais se rappeler cette syntaxe, et, heureusement,
c'est en fait un peu délibéré-oh, vous n'avez pas vraiment vu ce que j'ai écrit.
Ce serait plus convaincant si vous le pouviez. Voila!
>> Dans les coulisses, j'ai été de résoudre le problème de cette façon.
Anita, à franchir le pas vers la gauche,
première fois, nous y allons à l'adresse que Anita est dirigée vers
et où elle se trouve, non seulement n, ce qui nous viens de vérifier pour fins de comparaison,
mais vous trouverez également à côté - dans ce cas,
Main gauche Ramon pointant vers le nœud suivant dans la liste.
Mais c'est le bordel de dieu terrible à laquelle j'ai fait allusion plus tôt,
mais il s'avère C nous permet de simplifier cette.
Au lieu d'écrire (* anita), on peut simplement écrire au lieu anita-> n,
et c'est exactement la même chose fonctionnellement, mais il est beaucoup plus intuitive,
et il est beaucoup plus conforme à l'image que nous avons attiré
tout ce temps à l'aide des flèches.
>> Enfin, qu'est-ce que nous devons faire à la fin de ce programme?
Il ya une ligne de code restant.
Retour quoi?
Faux, parce que si nous recevons à travers toute la boucle while
et Anita est, en fait, null, ce qui signifie qu'elle a fait tout le chemin jusqu'à la fin de la liste
où elle pointait au-quel est votre nom?
Ari main gauche. >> Ari, qui est nulle.
Anita est maintenant nul, et je me rends compte que vous êtes debout juste ici maladroitement dans les limbes
parce que je pars sur un monologue ici,
mais nous vous impliquer à nouveau dans quelques instants.
Anita est nulle à ce moment de l'histoire, de sorte que la boucle while se termine,
et nous devons retourner faux parce que si elle a eu tout le chemin vers un pointeur nul Ari
alors il n'y avait pas de numéro qu'elle cherchait dans la liste.
Nous pouvons nettoyer ça aussi, mais c'est une très bonne mise en œuvre, puis
une fonction de traversée, une fonction de recherche pour une liste chaînée.
C'est encore la recherche linéaire, mais ce n'est pas aussi simple que + + un pointeur
+ + ou une variable i, parce que maintenant nous ne pouvons pas deviner
où chacun de ces noeuds sont en mémoire.
Nous devons littéralement suivre les traces de chapelure ou, plus précisément,
pointeurs, pour aller d'un nœud à l'autre.
>> Maintenant, nous allons essayer un autre. Anita, tu veux revenir ici?
Pourquoi ne pas aller de l'avant et d'attribuer une autre personne de l'auditoire?
Malloc-quel est ton nom? >> Rebecca.
Rebecca. Rebecca a été malloced de l'auditoire,
et elle est désormais stocker le numéro 55.
Et l'objectif à portée de main est maintenant à Anita pour insérer
Rebecca dans la liste liée ici à sa place appropriée.
Venez par ici pour un moment.
J'ai fait quelque chose comme ça.
Je l'ai fait * noeud. Et quel est votre nom?
Rebecca. >> Rebecca, d'accord.
Rebecca se malloc (sizeof (noeud)).
Tout comme nous avons alloué des choses comme les étudiants et autres joyeusetés dans le passé,
nous avons besoin de la taille du noeud, alors maintenant Rebecca
est dirigée vers quoi?
Rebecca a deux champs à l'intérieur d'elle, dont l'une est 55.
Faisons ce que, rebecca-> = 55.
Mais alors rebecca-> suivant doit être-comme en ce moment, sa main est une sorte de qui sait?
C'est en montrant une certaine valeur ordures, alors pourquoi ne pas pour faire bonne mesure
nous avons au moins le faire pour que la main gauche est maintenant à ses côtés.
Maintenant, Anita, le prendre d'ici.
Vous avez Rebecca ayant été attribués.
Allez-y et trouver l'endroit où nous devrions mettre Rebecca.
Bien, très bien.
Bon, très bien, et maintenant nous avons besoin de vous donner un peu de sens,
si vous avez atteint Ari.
Sa main gauche est nulle, mais Rebecca appartient clairement à la droite,
Alors, comment avons-nous pour modifier cette liste chaînée
afin d'insérer Rebecca dans l'endroit approprié?
Si vous pouviez littéralement déplacer les mains des gens autour gauche, au besoin,
nous allons résoudre le problème de cette façon.
Bon, très bien, et en même temps, la main gauche de Rebecca est maintenant à côté d'elle.
>> C'était trop facile.
Essayons-nous sommes allouer presque fini, 20.
Bon, allez vers le haut.
20 a été alloué, alors laissez-moi aller de l'avant et je le répète ici
nous venons de faire saad * noeud.
Nous avons malloc (sizeof (noeud)).
Nous procédons alors à la même syntaxe exacte comme nous le faisions avant pour 20,
et je ferai la prochaine = NULL, et maintenant c'est à Anita
à vous d'ajouter dans la liste liée, si vous pouviez jouer ce rôle exactement la même.
Execute.
Bon, très bien.
Maintenant, réfléchissez bien avant de commencer à bouger la main gauche autour.
Vous, de loin, a obtenu le rôle le plus délicat aujourd'hui.
Dont la main doit être déplacé en premier?
Bon, attends, je viens d'entendre quelques-uns de pas.
Si certaines personnes poliment tiens à vous aider à résoudre une situation délicate ici.
Dont la main gauche doit être mis à jour premier peut-être? Ouais.
[Étudiants] de Saad.
Bon, Saad, pourquoi, si?
[Réponse de l'élève inaudible]
Bon, parce que si nous nous déplaçons-quel est ton nom? >> Marshall.
Marshall, si l'on bouge sa main d'abord vers null,
maintenant, nous avons littéralement orphelins quatre personnes dans cette liste
parce qu'il était le seul dirigeant à Ramon et tout le monde vers la gauche,
de sorte que la mise à jour du premier pointeur était mauvaise.
Nous allons annuler cela.
Bon, et maintenant aller de l'avant et de déplacer la main gauche tendue appropriée à Ramon.
Cela se sent un peu redondant.
Maintenant, il ya deux personnes pointant à Ramon, mais c'est très bien
parce que maintenant de quelle autre façon peut-on mettre à jour la liste?
Qu'est-ce d'autre part doit se déplacer?
Excellent, maintenant nous avons perdu toute la mémoire?
Non, tout va bien, nous allons voir si nous ne pouvons pas briser ce une fois de plus.
>> Allouer de la dernière fois, le numéro 5.
Tout le chemin à l'arrière, allez vers le bas.
C'est très excitant.
[Applaudissements]
Quel est ton nom? >> Ron.
Ron, d'accord, vous êtes malloced que le numéro 5.
Nous venons d'exécuter du code qui est presque identique à ceux-ci
avec juste un nom différent.
Excellent.
Maintenant, Anita, bonne chance insérer le numéro 5 dans la liste maintenant.
Bon, et?
Excellent, donc c'est vraiment le troisième de trois cas au total.
Nous avons d'abord eu quelqu'un au bout du compte, Rebecca.
Nous avons ensuite eu quelqu'un dans le milieu.
Maintenant, nous avons quelqu'un au début, et dans cet exemple,
nous avions maintenant de mettre à jour Lucas pour la première fois
parce que le premier élément de la liste doit maintenant pointer vers un nouveau nœud,
qui, à son tour, est dirigée vers le numéro de station 9.
>> Ce fut une démonstration extrêmement maladroit, j'en suis sûr,
si une salve d'applaudissements pour ces gars-là si vous le pouviez.
Bien joué.
Voilà tout. Vous pouvez garder vos morceaux de papier comme un peu de mémoire.
Il s'avère que le faire dans le code
n'est pas aussi simple que de passer les mains autour de
et pointant pointeurs à des choses différentes.
Mais se rendre compte que lorsque vient le temps de mettre en place quelque chose comme
une liste chaînée ou une variante de celui-ci si vous vous concentrez sur la réalité
ces principes fondamentaux, les problèmes bouchées que je dois comprendre,
est-ce cela la main ou cette main, se rendent compte que ce qui est par ailleurs un programme assez complexe
peut, en effet, être réduit à des blocs de construction relativement simples comme celui-ci.
>> Prenons les choses dans un sens encore plus sophistiquée.
Nous avons maintenant la notion de liste chaînée.
Nous avons aussi, grâce à la suggestion retourner là-bas, une liste doublement chaînée,
qui ressemble presque le même, mais maintenant nous avons deux pointeurs à l'intérieur de la structure
au lieu d'un, et nous pourrions probablement appeler ces pointeurs précédent et suivant
ou vers la gauche ou vers la droite, mais nous faisons, en effet, besoin de deux d'entre eux.
Le code serait un peu plus compliqué.
Anita aurait dû faire plus de travail ici sur la scène.
Mais nous pourrions certainement mettre en œuvre ce type de structure.
En termes de durée, cependant, quelle serait la durée de fonctionnement
pour Anita de trouver un nombre n dans une liste, maintenant?
Toujours grand O de n, donc ce n'est pas mieux que la recherche linéaire.
Nous ne pouvons pas faire de recherche binaire, même si, encore une fois.
Pourquoi était-ce le cas? Vous ne pouvez pas sauter partout.
Même si nous avons évidemment voir tous les humains sur la scène,
et Anita aurait pu eyeballed et dit: «Voici le milieu de la liste,"
elle ne voulait pas savoir que si elle était le programme informatique
parce que la seule chose qu'elle a dû s'accrocher à au début du scénario
était Lucas, qui était le premier pointeur.
Elle devra nécessairement suivre ces liens,
compter son chemin jusqu'à ce qu'elle trouve à peu près au milieu,
et même alors, elle ne va pas savoir quand elle atteint le milieu
à moins qu'elle ne va tout le chemin jusqu'à la fin pour comprendre combien ils sont,
puis fait marche arrière, et cela serait difficile à moins d'avoir
une liste doublement liée de quelque sorte.
>> La résolution de certains problèmes aujourd'hui, mais en introduisant d'autres.
Qu'en est-il une structure de données tout à fait différent?
C'est une photographie des plateaux de Mather House,
et dans ce cas, nous avons une structure de données que nous avons aussi un peu déjà parlé.
Nous avons parlé d'une pile dans le contexte de la mémoire,
et qui est en quelque sorte délibérément nommé parce que une pile dans les termes de mémoire
est en fait une structure de données qui a des trucs de plus en plus couches sur le dessus de celui-ci.
Mais la chose intéressante à propos d'une pile, comme c'est le cas dans la réalité,
c'est que c'est un type particulier de structure de données.
C'est une structure de données de sorte que le premier élément
est le dernier élément sur.
Si vous êtes le premier plateau à mettre sur la pile,
vous allez être malheureusement le dernier plateau à prendre de la pile,
et ce n'est pas nécessairement une bonne chose.
Inversement, vous pouvez penser dans l'autre sens,
le dernier est le premier sorti.
>> Maintenant, ne les scénarios viennent à l'esprit où avoir une pile
structure de données où vous avez cette propriété
du dernier entré, premier sorti, est en fait convaincante?
Est-ce une bonne chose? Est-ce une mauvaise chose?
C'est certainement une mauvaise chose si les plateaux ne sont pas tous identiques
et ils étaient tous différents coloris spéciaux ou autres joyeusetés,
et la couleur que vous voulez, c'est tout le chemin vers le bas.
Bien sûr, vous ne pouvez pas obtenir cela sans grand effort.
Vous devez commencer par le haut et de travailler votre chemin vers le bas.
De même, si vous étiez l'un de ces garçons ventilateur
qui attend toute la nuit essayant d'obtenir un iPhone et s'aligne
dans un endroit comme celui-ci?
Serait-il pas agréable si l'Apple Store
étaient une structure de données de la pile?
Yay? Nay?
Il est seulement bon pour les gens qui se présentent à la dernière minute
et puis obtenir arraché la file d'attente.
Et en effet, le fait que j'ai été tellement enclin à dire la file d'attente
est en fait conforme à ce que nous pourrions appeler ce type de structure de données,
un dans la réalité où l'ordre a son importance,
et que vous voulez le premier à être le premier à sortir
si ce n'est que pour des raisons d'équité humaine.
Nous appelons généralement qu'une structure de données file d'attente.
>> Il s'avère en outre des listes chaînées, nous pouvons commencer à utiliser ces mêmes idées de base
et commencer à créer de nouveaux types et différentes solutions aux problèmes.
Par exemple, dans le cas d'une pile, on pourrait représenter une pile
en utilisant une structure de données comme celui-ci, je vous propose.
Dans ce cas, j'ai déclaré une structure, et j'ai dit à l'intérieur de cette structure
est un tableau de nombres et une taille variable appelée,
et je vais appeler cette chose une pile.
Maintenant, pourquoi est-ce vraiment efficace?
Dans le cas d'une pile, je pouvais dessiner de façon efficace à l'écran sous forme de tableau.
Voici mon tapis. Ce sont mes numéros.
Et nous allons les tirer comme ça, ça, ça, ça, ça.
Et puis j'ai une autre membre de données ici,
qui est appelé la taille, si ce n'est la taille, et c'est le nombre,
et collectivement, l'iPad représente ici toute une structure de pile.
Maintenant, par défaut, la taille est sans doute arrivé à être initialisée à 0,
et ce qui est à l'intérieur de la matrice de nombres initialement
quand j'ai allouer un tableau?
Garbage. Qui sait? Et il n'a pas vraiment d'importance.
Ce n'est pas grave si c'est 1, 2, 3, 4, 5, complètement aléatoire
par la malchance stocké dans ma structure, car tant que je sais que la taille de la pile
est 0, alors je sais programme, ne regardez pas à l'un des éléments dans le tableau.
Ce n'est pas grave ce qui est là.
Ne les regardez pas, comme ce serait l'implication d'une taille de 0.
>> Mais supposons maintenant je vais de l'avant et insérer quelque chose dans la pile.
Je veux insérer le numéro 5, alors j'ai mis le numéro 5 ici,
et puis qu'est-ce que je mets ici?
Maintenant, je voudrais effectivement mis en baisse de 1 pour la taille,
et maintenant la pile est de taille 1.
Que faire si je aller de l'avant et insérez le nombre, disons, 7 next?
Cela devient alors mis à jour à 2, puis nous ferons 9,
et puis ce sera mise à jour à 3.
Mais la caractéristique intéressante de cette pile maintenant, c'est que
Je suis censé supprimer cet élément si je veux faire un saut
quelque chose hors de la pile, pour ainsi dire?
9 serait la première chose à faire.
Comment devrais changer l'image, si je veux faire apparaître un élément de la pile,
un peu comme un bac à Mather?
Ouais. >> [Étudiants] Régler la taille à 2.
Exactement, tout ce que je faire est de définir la taille à 2, et que dois-je faire avec le tableau?
Je n'ai pas à faire quoi que ce soit.
Je pourrais, juste pour être anal, mettre un 0 ou -1 il ou quelque chose pour signifier
que ce n'est pas une valeur légitime, mais ce n'est pas grave parce que
Je peux enregistrer à l'extérieur de la matrice elle-même combien de temps il est
de sorte que je sais qu'à regarder les deux premiers éléments de ce tableau.
Maintenant, si je vais ajouter le numéro 8 du présent tableau, comment changer l'image suivante?
Cela devient 8, et cela devient 3.
Je coupe quelques virages ici.
Maintenant, nous avons 5, 7, 8, et nous sommes de retour à une taille de 3.
C'est assez simple à mettre en œuvre,
mais quand allons-nous regrettons cette décision de conception?
Quand est-ce les choses commencent à aller mal, très mal? Ouais.
[Réponse de l'élève inaudible]
Lorsque vous voulez revenir en arrière et obtenir le premier élément que vous mettez dedans
>> Il s'avère ici, même si une pile est un tableau sous le capot,
ces structures de données que nous avons commencé à parler sont aussi généralement connu sous le nom
structures de données abstraites où comment ils mis en œuvre
est complètement hors de propos.
Une structure de données comme une pile est censé ajouter le support
opérations comme poussoir, qui pousse un plateau dans la pile,
et de la pop, ce qui supprime un élément de la pile, et c'est tout.
Si vous deviez télécharger le code de quelqu'un d'autre qui a déjà mis en œuvre
cette chose appelée une pile, cette personne aurait écrit
seulement deux fonctions pour vous, poussez et pop, dont le seul but dans la vie
serait de faire exactement cela.
Vous ou lui qui a appliqué ce programme
aurait été tout à fait le seul à décider comment mettre en œuvre
la sémantique de pousser et sauter sous le capot
ou la fonctionnalité de pousser et popping.
Et j'ai pris une décision un peu myope ici
en mettant en place ma pile avec cette structure de données simple pourquoi?
Quand est-ce cette pause structure de données?
À quel moment dois-je retourner une erreur lorsque l'utilisateur appelle push, par exemple?
[Étudiant] S'il n'y a pas plus de place.
Justement, s'il ya un espace pas plus, si j'ai dépassé la capacité,
ce qui est tout en majuscules, car il suggère que c'est une sorte de constante globale.
Eh bien, alors je vais juste avoir à dire: «Désolé, je ne peux pas pousser une autre valeur
sur la pile », un peu comme dans Mather.
>> À un certain moment, ils vont frapper la partie supérieure de ce petit cabinet.
Il n'y a plus d'espace ou de capacité de la pile, à quel point il ya une sorte d'erreur.
Ils doivent mettre l'élément ailleurs, le plateau ailleurs,
ou nulle part.
Maintenant, avec une file d'attente, nous avons pu mettre en œuvre un peu différemment.
Une file d'attente est un peu différent en ce que sous le capot, il peut être mis en œuvre
comme un tableau, mais pourquoi, dans ce cas, je propose
d'avoir aussi un élément de tête représentant la tête de la liste,
le début de la liste, la première personne en ligne sur l'Apple Store, en plus de la taille?
Pourquoi ai-je besoin d'une pièce supplémentaire de données ici?
Pensez à ce que le nombre est
si j'ai dessiné comme suit.
Supposons que c'est maintenant une file d'attente au lieu d'une pile,
la différence étant, tout comme l'Apple Store en file d'attente est juste.
La première personne en ligne au début de la liste, le numéro 5 dans ce cas,
il ou elle va être laissé dans le premier magasin.
Faisons-le.
Supposons que c'est l'état de ma file d'attente en ce moment dans le temps, et maintenant sur l'Apple Store
et ouvre la première personne, le numéro 5, est introduit dans le magasin.
Comment puis-je changer l'image, maintenant que j'ai dé-file d'attente la première personne
à l'avant de la ligne?
Qu'est-ce que c'est? >> [Étudiants] Changer la file d'attente.
Changer la tête, donc 5 disparaît.
En réalité, c'est comme si-la meilleure façon de faire cela?
En réalité, c'est comme si ce gars disparaît.
Qu'est-ce que le numéro 7 faire dans un magasin réel?
Ils prendraient un grand pas en avant.
>> Mais qu'avons-nous appris à apprécier quand il s'agit de tableaux
et déplacer des choses?
C'est une sorte de gaspillage de votre temps, pas vrai?
Pourquoi avez-vous besoin d'être aussi anale pour avoir la première personne
au début de la ligne à physiquement le début de la portion de mémoire?
C'est complètement inutile. Pourquoi?
Que pouvais-je me souviens à la place? >> [Réponse de l'élève inaudible]
Exactement, je ne pouvais me souviens de cette tête de l'élément de données supplémentaire
que maintenant à la tête de la liste n'est plus 0, ce qui était il ya un instant.
Maintenant, il est en fait le numéro 1. De cette façon, j'obtiens une optimisation légère.
Juste parce que je suis quelqu'un de-file d'attente à partir de la ligne au début de la ligne sur l'Apple Store
ne signifie pas que tout le monde doit passer, ce qui rappel est une opération linéaire.
Je peux passer du temps au lieu seule constante
et de réaliser ensuite une réponse beaucoup plus rapide.
Mais le prix que je paie ce qu'il faut gagner cette performance supplémentaire
et ne pas avoir à changer le monde?
Ouais. >> [Réponse de l'élève inaudible]
Pouvez ajouter d'autres personnes, eh bien, ce problème est orthogonal
au fait que nous ne sommes pas déplacer les gens autour.
C'est toujours un tableau, donc si oui ou non nous changeons tout le monde ou pas-
oh, je vois ce que tu veux dire, d'accord.
En fait, je suis d'accord avec ce que vous dites en ce qu'elle est presque comme si
nous sommes maintenant ne va jamais utiliser le début de ce tableau plus
parce que si je retire 5, puis-je supprimer 7.
Mais je ne mettre les gens vers la droite.
>> C'est comme si je perds mon espace, et finalement ma file d'attente se désintègre en rien du tout,
si nous pouvions avoir enveloppant les gens,
et l'on pourrait penser de ce tableau vraiment comme une sorte de structure circulaire,
mais nous utilisons ce que l'opérateur en C pour faire ce genre de bouclage?
[Réponse de l'élève inaudible] >> L'opérateur modulo.
Il serait un peu ennuyeux de penser à la façon dont tu fais l'enveloppant,
mais nous pourrions le faire, et nous avons pu commencer à mettre les gens à ce qui était à l'avant de la ligne,
mais nous venons de rappeler à cette variable la tête qui est le chef réel de la ligne est en réalité.
Que faire si, au contraire, notre but en fin de compte, cependant,
était de chercher des numéros, comme nous l'avons fait ici sur scène avec Anita,
mais nous voulons vraiment le meilleur de tous les mondes?
Nous voulons toujours plus sophistiquée tableau permet
parce que nous voulons que la capacité à se développer de manière dynamique la structure de données.
Mais nous ne voulons pas avoir à recourir à quelque chose que nous avons fait remarquer
dans la première conférence n'était pas un algorithme optimal,
que la recherche linéaire.
Il s'avère que vous pouvez, en effet, d'atteindre
ou au moins proche de la constante de temps, lequel quelqu'un comme Anita,
si elle configure sa structure de données ne soit pas une liste chaînée,
de ne pas être une pile, ne pas être une file d'attente, pourrait, en fait,
proposer une structure de données qui lui permet de regarder les choses,
même des mots, et pas seulement des chiffres, dans ce que nous appellerons la constante de temps.
>> Et en fait, l'avenir, l'un des psets dans cette classe est presque toujours
une mise en œuvre d'un correcteur orthographique, lequel
nous vous donnons encore quelques mots 150.000 anglais et le but est de
charger dans la mémoire de ceux et rapidement être en mesure de répondre aux questions de la forme
ce mot est correctement orthographié?
Et il serait vraiment sucer si vous deviez parcourir tous les 150.000 mots pour répondre.
Mais, en fait, nous allons voir ce que nous pouvons le faire en un temps très, très rapide.
Et cela va impliquer quelque chose appelé la mise en œuvre d'une table de hachage,
et même si à première vue, cette chose qu'on appelle une table de hachage va
laissez-nous atteindre ces superbes moments d'intervention rapide,
il s'avère qu'il ya en fait un problème.
Quand vient le temps de mettre en œuvre cette chose appelée de nouveau, je le fais à nouveau.
Je suis le seul ici.
Quand vient le temps de mettre en œuvre ce qu'on appelle une table de hachage,
nous allons devoir prendre une décision.
Quelle devrait être cette chose en réalité?
Et quand on commence à insérer des numéros dans cette table de hachage,
comment allons-nous à les stocker de manière
que nous pouvons les récupérer aussi vite que nous les avons en?
Mais nous verrons bientôt que cette question de
lorsque anniversaire de tout le monde est dans la classe sera tout à fait pertinent.
Il s'avère que dans cette salle, nous avons quelques centaines de personnes,
alors les chances que deux d'entre nous ont le même anniversaire est probablement assez élevé.
Que faire si il n'y avait que 40 d'entre nous dans cette salle?
Quelles sont les chances de deux personnes ayant la même date d'anniversaire?
[Les élèves] Plus de 50%.
Oui, plus de 50%. En fait, j'ai même apporté un graphique.
Il s'avère, et c'est vraiment juste un sneak preview-
s'il ya seulement 58 d'entre nous dans cette salle, la probabilité de 2 d'entre nous
ayant la même date d'anniversaire est extrêmement élevé, de près de 100%,
et que va causer tout un tas de mal pour nous le mercredi.
>> Cela dit, nous allons ajourner ici. Nous allons vous voir mercredi.
[Applaudissements]
[CS50.TV]