[MUSIQUE LECTURE] DAVID J. Malan: Très bien. C'est CS50. C'est la semaine de cinq continué, et nous de bonnes nouvelles et de mauvaises nouvelles. Donc, de bonnes nouvelles, c'est que CS50 lance ce vendredi. Si vous souhaitez vous joindre à nous, la tête de l'URL d'habitude ici. Nouvelles encore meilleures, pas exposé lundi prochain le 13. Un peu moins de meilleures nouvelles, questionnaire zéro est mercredi prochain. Plus de détails peuvent être trouvé à l'adresse ici. Et au cours des deux prochains jours nous allons remplir les blancs en ce qui concerne les chambres que nous avons réservé. De meilleures nouvelles, c'est qu'il ya aurez une révision des cours à l'échelle séance prochain Lundi dans la soirée. Restez à l'écoute pour le cours de site pour l'emplacement et les détails. Les articles, même si elle est un vacances, rencontrera également ainsi. Meilleures nouvelles, lecture vendredi prochain. Il s'agit donc d'une tradition de nous avoir, selon le programme. Just-- ça va être incroyable. Vous allez voir des choses comme structures de données de temps constant des tables et des arbres et des essais hachage. Et nous allons parler de problèmes d'anniversaire. Tout un tas de choses attend vendredi prochain. Dáccord. Quoi qu'il en soit. Donc, rappelons que nous avons été en se concentrant sur cette image de ce qui est l'intérieur de la mémoire de notre ordinateur. Donc, la mémoire vive ou RAM est l'endroit où les programmes exister alors que vous êtes les exécuter. Si vous double-cliquez sur un icône pour exécuter un programme ou double-cliquez sur un icône pour ouvrir certains fichiers, il est chargé de votre disque conduire ou lecteur à état solide dans la RAM, Random Access Memory, où il vit jusqu'à ce qu'il s'éteigne, le couvercle se ferme pour ordinateur portable, ou vous quittez le programme. 

Maintenant que la mémoire, de qui vous avez probablement 1 gigaoctet ces jours, 2 gigaoctets, voire beaucoup plus, est généralement aménagé pour un programme donné dans ce genre de forme rectangulaire modèle conceptuel lequel nous avons la pile au fond et un tas d'autres choses en tête. La chose au sommet nous avons vu sur cette photo mais jamais parlé est le segment dit le texte. segment de texte est juste une façon élégante de dire les zéros et de uns que composer votre programme compilé réelle. 

Ainsi, lorsque vous double-cliquez sur Microsoft Word sur votre Mac ou PC, ou lorsque vous exécutez point slash Mario sur un Ordinateur Linux à votre fenêtre de terminal, les zéros et de uns qui composent Word ou Mario sont stockés temporairement dans la mémoire vive de votre ordinateur dans la soi-disant segment de texte pour un programme particulier. Ci-dessous, qui va initialisé et les données non initialisées. Ce sont des choses comme des variables globales, que nous n'avons pas utilisé beaucoup de, mais à l'occasion, nous avons eu des variables globales ou statique des chaînes définies que est dur mots comme "bonjour" codé qui ne sont pas pris en de l'utilisateur qui sont codés en dur dans votre programme. 

Maintenant, au bas nous disposer la pile dite. Et la pile, jusqu'à présent, nous avons été à l'aide de quels types de besoins? Qu'est-ce la pile été utilisé? Ouais? 

PUBLIC: Fonctions. 

DAVID J. Malan: Pour les fonctions? Dans quel sens pour les fonctions? 

PUBLIC: Lorsque vous appelez une fonction, la arguments sont copiés sur la pile. 

DAVID J. Malan: Exactement. Lorsque vous appelez une fonction, son arguments sont copiés sur la pile. Ainsi, tout les X ou Y ou de A ou de B que vous êtes de passage dans une fonction sont temporairement mis sur la dite pile, comme l'un des Annenberg plateaux de la salle à manger, et aussi des choses comme les variables locales. Si votre fonction foo ou votre échange fonction des variables locales ont, comme température, ces deux retrouver dans la pile. Maintenant, nous ne serons pas trop parler , mais ces variables d'environnement en bas, nous avons vu tout à l'heure quand Je suis futzing au clavier un jour et j'ai commencé à accéder à des choses comme argv 100 ou argv 1000, juste elements-- j'oublie mais que la numbers-- n'étaient pas censés être consultée par moi. Nous avons commencé à voir quelques-uns symboles funky, sur l'écran. C'était soi-disant variables d'environnement comme paramètres globaux pour mon programme ou pour mon ordinateur, pas rien à voir avec la récente bug que nous avons discuté, Shellshock, que cela a été dont souffre un très petit nombre d'ordinateurs. 

Maintenant, enfin, dans la mise au point d'aujourd'hui nous allons finalement être sur le tas. Ceci est un autre morceau de la mémoire. Et tout cela fondamentalement mémoire est la même chose. C'est le même matériel. Nous sommes juste une sorte de le traitement de différents groupes d'octets à des fins différentes. Le tas va également être le cas variables et la mémoire que vous demandez à partir du système d'exploitation est temporairement stockée. 

Mais il ya une sorte de problème ici, que l'image implique. Nous avons sorte de deux navires sur le point d'entrer en collision. Parce que, comme vous utilisez de plus en plus de la pile, et comme nous le voyons aujourd'hui avant, que vous utilisez de plus en plus de la tas, sans doute de mauvaises choses peuvent se produire. Et en effet, nous pouvons induire que intentionnellement ou non. Ainsi, le cliffhanger dernier temps était de ce programme, qui ne sert pas tout fonctionnelle autre but que de démontrer comment vous comme un mauvais gars peut effectivement prendre avantage de bogues dans le programme de quelqu'un et prendre en charge un programme ou même une Système d'ordinateur serveur ou ensemble. Il suffit donc de regarder brièvement, vous remarquer que le principal en bas prend en ligne de commande arguments, comme par argv. Et elle a un appel à une fonction f, essentiellement une fonction anonyme appelée f, et c'est en passant dans argv [1]. 

Donc, quelles que soient les mot types d'utilisateurs dans au l'invite après le nom de ce programme, et alors cette fonction arbitraire jusqu'à haut, f, prend dans une chaîne, Alias ​​char *, comme nous avons commencé à discuter, et il appelle simplement qu'il «bar». Mais nous pourrions appeler ça. Et puis, il déclare, à l'intérieur de f, un tableau de caractères appelé c-- ces 12 caractères. 

Maintenant, par l'histoire que je racontais il ya un moment, où dans la mémoire c est, ou sont ces 12 Chars va finir? Juste pour être clair. Ouais? 

PUBLIC: Sur la pile. 

DAVID J. Malan: Sur la pile. Donc, c est une variable locale. Nous demandons 12 caractères ou 12 octets. Ceux vont finir par sur la pile dite. Maintenant, enfin, est cette autre fonction c'est en fait très utile, mais nous ne l'avons pas vraiment utilisé nous-mêmes, strncopy. Cela signifie copie de chaîne, mais que n lettres, n caractères. Alors n caractères seront copié de bar au c. Et combien? La longueur de la barre. En d'autres termes, que une ligne, strncopy, va copier bar efficacement à c. 

Maintenant, juste sorte de prévoir la morale de cette histoire, ce qui est potentiellement problématique ici? Même si nous vérifions la longueur de bar et passer dans strncopy, Quelle est votre intestin vous dit est encore cassé sur ce programme? Ouais? 

PUBLIC: Ne comprend pas salle pour le caractère nul. DAVID J. Malan: Ne comprend pas salle pour le caractère nul. Potentiellement, contrairement à la pratique passée, nous n'avons pas encore avoir autant comme un atout 1 à tenir compte de ce caractère nul. Mais c'est encore pire que cela. Que sommes nous n'arrivons pas à faire? Ouais? 

PUBLIC: [inaudible] DAVID J. Malan: Parfait. Nous avons codé en dur 12 assez arbitraire. Ce n'est pas tant la problème, mais le fait que nous ne sommes même pas vérifier si la longueur de la barre est inférieure à 12, dans ce cas, il va être sûr de le mettre dans la mémoire appelé c que nous avons prévu. En effet, si la barre est comme 20 caractères, cette fonction semble être la copie 20 caractères de bar en c, ce qui prendre au moins 8 octets qu'il ne doit pas l'être. C'est l'implication ici. 

Donc, en résumé, le programme cassé. Pas une grosse affaire. Peut-être vous obtenez une erreur de segmentation. Nous avons tous eu des bugs dans les programmes. Nous pourrions tous avoir des bugs dans les programmes dès maintenant. Mais quelle est la conséquence? Eh bien, voici une version zoomée de que l'image de la mémoire de mon ordinateur. C'est le bas de ma pile. Et en effet, tout au fond est ce qui est appelé pile routine parent, façon élégante de dire que c'est principale. Alors que celui qui appelle la fonction f que nous parlons. C'est donc la partie inférieure de la pile. L'adresse de retour est quelque chose de nouveau. Il a toujours été là, toujours été dans cette image. Nous n'avons jamais attiré l'attention sur elle. Parce qu'il s'avère que le chemin c fonctionne est que quand une fonction appelle une autre, non seulement les arguments que fonction se poussé sur la pile, non seulement locale de la fonction les variables sont poussés sur la pile, quelque chose qui s'appelle une adresse de retour obtient également mis sur la pile. Plus précisément, si les appels principaux Foo, principaux de propre adresse dans la mémoire, bœuf quelque chose, efficace qui est mis sur la pile de sorte que lorsque f est fait exécuter sait où pour revenir en arrière dans le texte segment, afin de poursuivre l'exécution. 

Donc, si nous sommes ici sur le plan conceptuel, en principal, alors f est appelée. Comment savoir qui f au contrôle de la main en arrière? Eh bien, ce petit Ariane en rouge ici, appelé l'adresse de retour, il suffit contrôles, ce qui est ce que l'adresse de retour? Oh, laissez-moi revenir au principal ici. Et c'est un peu d'une simplification, parce que les zéros et de uns pour principal sont techniquement ici dans le segment de la technologie. Mais c'est l'idée. fa a juste besoin de savoir ce que à l'endroit où le contrôle va finalement de retour. 

Mais la façon dont les ordinateurs ont longtemps posé des choses comme les variables locales et arguments est comme ça. Ainsi, dans le haut de cette image dans bleu est le cadre de pile pour f, de sorte que tous de la mémoire que f est précisément à l'aide. Ainsi donc, vous remarquerez que bar est dans cette image. Bar était son argument. Et nous avons réclamé que les arguments de fonctions sont poussés sur la pile. Et C, bien sûr, est aussi dans cette image. 

Et seulement à des fins de notation, remarquer dans le coin supérieur gauche est ce que serait c support 0 et ensuite légèrement vers le bas vers la droite c est le support 11. En d'autres termes, vous pouvez l'imaginer qu'il ya une grille d'octets y, qui est d'abord en haut à gauche, en bas de laquelle est la dernière de ces 12 octets. 

Mais maintenant essayer d'avancer rapidement. Qu'est-ce qui va se passer si nous passons dans un bar de chaîne qui est plus long que c? Et nous ne sommes pas vérifier si il est en effet plus que 12. Quelle partie de cette image va écrasés par les octets 0, 1, 2, 3, dot dot dot, 11, puis mauvais, 12, 13 à 19? Qu'est-ce qui va se passer ici, si vous déduisez de la commande c 0 que le support est sur le dessus et c support 11 est une sorte de duvet vers la droite? Ouais? 

PUBLIC: Eh bien, il va pour remplacer la barre char *. 

DAVID J. Malan: Ouais, on dirait vous allez écraser l'omble bar *. Et pire, si vous envoyez dans un très long chaîne, vous pourriez même remplacer quoi? L'adresse de retour. Qui encore une fois, c'est comme un navigation pour indiquer au programme où pour revenir au moment où f se fait appelé. 

Alors, que les méchants font généralement est si ils viennent à travers un programme qu'ils sont curieux de savoir si c'est exploitable, poussette de manière qu'il ou elle peut prendre avantage de ce bug, en général, ils ne reçoivent pas ce droit la première fois. Ils commencent juste à envoyer, par exemple, chaînes aléatoires dans votre programme, soit au clavier, ou franchement ils ont probablement écrire un petit programme à juste génèrent automatiquement des chaînes, et commencer à taper sur votre programme par envoi en lots de différentes entrées à des longueurs différentes. 

Dès que votre programme plante, c'est une chose étonnante. Parce que cela signifie qu'il ou elle a découvert ce qui est probablement en effet un bug. Et puis ils peuvent obtenir plus intelligent et commencer à se concentrer plus étroitement sur la façon d'exploiter ce bug. En particulier, ce qu'il ou elle pourrait faire est d'envoyer, dans le meilleur des cas, bonjour. No big deal. C'est une chaîne qui est suffisamment court. Mais que faire si il ou elle envoie, et nous généralisons comme, attaque code-- si zéros et ceux qui font des choses comme rm-rf, que retirer tout depuis le disque dur ou envoyer du spam ou en quelque sorte attaquer la machine? 

Ainsi, si chacun de ces lettres A représente juste, conceptuellement, attaque, attaque, attaque, attaque, certains mauvais code que quelqu'un d'autre a écrit, mais si cette personne est assez intelligent non seulement inclure tous de ces RM-RFS, mais aussi voir ses dernières octets un nombre qui correspond à l'adresse de son ou son propre code d'attaque qu'il ou elle a passé en tout en fournissant à l'invite, vous pouvez effectivement tromper l'ordinateur en remarquant lorsque f est faite d'exécution, oh, il est temps pour moi de sauter retourner à l'adresse de retour rouge. Mais parce qu'il ou elle a en quelque sorte chevauchement que l'adresse de retour avec leur propre numéro, et ils sont assez intelligents avoir configuré que nombre de renvoyer, comme vous voir dans le super top coin gauche là, l'adresse réelle de l'ordinateur de la mémoire de certains de leur code d'attaque, un méchant peut tromper l'ordinateur dans l'exécution de son propre code. 

Et ce code, encore une fois, peut être n'importe quoi. Il est généralement appelé Code coquille, qui est juste une façon de dire que ce n'est pas généralement quelque chose d'aussi simple que rm-rf. C'est en fait quelque chose comme Bash, ou un programme réel qui lui donne ou son contrôle programmatique pour exécuter toute autre chose qu'ils veulent. Donc en bref, tout cela découle du simple fait que ce bug ne vérifiant pas impliqué les limites de votre réseau. Et parce que la façon les ordinateurs fonctionnent, c'est qu'ils utiliser la pile de efficace, sur le plan conceptuel, bas sur place, mais alors les éléments vous appuyez sur la pile croître de haut en bas, c'est incroyablement difficile. Maintenant, il ya des façons de contourner cela. Et franchement, il ya des langues avec lesquelles travailler autour de cela. Java est à l'abri, par exemple, à cette question. Parce qu'ils ne vous donnent pas des pointeurs. Ils ne vous donnent pas adresses de mémoire directs. Donc, avec ce pouvoir que nous avons de toucher quoi que ce soit dans la mémoire nous voulons vient, certes, de grands risques. 

Alors gardez un œil sur. Si, franchement, dans les mois ou les années à venir, à tout moment vous découvrirez certains exploitation d'un programme ou d'un serveur, si jamais vous voyez un soupçon de quelque chose comme une attaque par débordement de tampon, ou débordement de pile est un autre type d'attaque, dans le même esprit, inspire autant que le site Web de nom, si vous le savez, il est tout simplement parler débordant de la taille de caractère certain tableau ou d'un tableau plus général. Toutes les questions, puis, à ce sujet? N'essayez pas ceci à la maison. 

Bien. Donc malloc a été jusqu'ici notre nouveau ami en qui nous pouvons allouer de la mémoire que nous ne savons pas nécessairement dans avance que nous voulons si nous n'avons pas de coder en dur dans notre numéros de programme comme 12. Une fois que l'utilisateur indique dans quelle mesure données qu'il ou elle veut à l'entrée, nous pouvons malloc que beaucoup de mémoire. 

Donc malloc il s'avère, à l' mesure où nous l'avons utilisé, explicitement la dernière fois, puis vous les gars l'ont utilisé pour GETSTRING inconsciemment pour plusieurs semaines, tous de la mémoire malloc vient du tas dite. Et c'est pourquoi getString, par exemple, peut allouer de la mémoire dynamiquement sans savoir ce que vous êtes aller taper à l'avance, vous restituer un pointeur vers la mémoire, et que la mémoire est toujours la vôtre à garder, même après GETSTRING rendements. Parce que d'un rappel après tout ce que l' pile est constamment monter et descendre, de haut en bas. Et dès qu'il va vers le bas, cela signifie que toute la mémoire cette fonction utilisée doit pas être utilisé par quelqu'un d'autre. C'est des valeurs parasites maintenant. 

Mais le tas est ici. Et ce qui est bien, c'est que malloc lorsque malloc alloue de la mémoire ici, il n'est pas affecté par la en grande partie, par la pile. Et si toute fonction peut accéder mémoire qui a été malloc'd, même par une fonction comme getString, même après avoir été retourné. 

Maintenant, c'est l'inverse de malloc est libre. Et en effet, la règle que vous doivent commencer à adopter est tout, tout, chaque fois que vous utilisez malloc vous devez vous utiliser gratuitement, par la suite, sur ce même pointeur. Tout ce temps nous avons écrit buggy, du code bogué, pour de nombreuses raisons. Mais dont l'un a été en utilisant la bibliothèque CS50, qui lui-même est délibérément buggy, il perd de la mémoire. Chaque fois que vous avez appelé getString au cours des dernières semaines nous demandons au fonctionnement système, Linux, pour mémoire. Et vous n'avez jamais donné une fois de retour. Et ce n'est pas, en pratique, une bonne chose. 

Et Valgrind, l'un des outils introduits dans Pset 4, est tout de vous aider maintenant trouver des bogues comme ça. Mais heureusement pour Pset 4 vous n'avez pas besoin d'utiliser la bibliothèque de CS50 ou getString. Donc, tous les bogues liés à la mémoire sont en fin de compte va être votre propre. 

Donc malloc est plus que juste commode à cet effet. Nous pouvons en fait maintenant résoudre fondamentalement différents problèmes, et fondamentalement résoudre des problèmes plus efficacement que par la promesse de la semaine zéro. Jusqu'à présent, c'est le plus sexy structure de données que nous avons eu. Et par la structure de données que je viens de dire une façon de conceptualiser la mémoire d'une manière qui va au-delà en disant: c'est un int, c'est un car. Nous pouvons commencer les choses du cluster ensemble. 

Donc, un tableau ressemblait à ceci. Et ce qui était essentiel dans environ une tableau est qu'il vous donne back-to-back des morceaux de mémoire, dont chacun va être du même type, int, int, int, int, ou char, char, char, car. Mais il ya quelques inconvénients. Ceci par exemple, est un tableau de taille six. Supposons que vous remplissez ce tableau avec six numéros et puis, pour une raison quelconque, votre utilisateur souhaite donner vous un septième numéro. Où mettez-vous? 

Quelle est la solution si vous avez créer un tableau sur la pile, par exemple, il suffit de la semaine deux notation que nous avons présenté, des crochets avec un numéro à l'intérieur? Eh bien, vous avez six le nombre de ces cases. Quelles seraient vos instincts être? Où voudriez-vous dire? 

PUBLIC: [inaudible] 

DAVID J. Malan: Désolé? 

PUBLIC: Mettez-le sur la fin. 

DAVID J. Malan: Mettez-le sur la fin. Donc un peu plus vers la droite, en dehors de cette zone. Qui serait bien, mais il s'avère que vous ne pouvez pas faire cela. Parce que si vous ne l'avez pas demandé pour cette partie de la mémoire, il pourrait être par hasard que cette est utilisé par une autre variable tout à fait. Pensez une semaine ou deux alors que nous posions sur les noms de Zamyla et Davin et Gabe dans la mémoire. Ils étaient littéralement dos à dos à dos. Donc, nous ne pouvons pas nécessairement confiance que tout ce qui est ici est disponible pour moi d'utiliser. 

Alors quoi d'autre pourriez-vous faire? Eh bien, une fois que vous le sachiez besoin d'un tableau de taille sept, vous pourriez créer un tableau de taille sept, puis utilisez une boucle for ou une boucle while, copier dans le nouveau tableau, et puis en quelque sorte simplement se débarrasser de ce tableau arrêter ou tout simplement de l'utiliser. Mais ce n'est pas particulièrement efficace. En bref, les tableaux ne laissent pas vous redimensionnez dynamiquement. 

Donc, d'une part vous obtenez accès aléatoire, ce qui est incroyable. Parce qu'il nous permet de faire les choses comme diviser pour régner, recherche binaire, qui nous avons parlé sur l'écran ici. Mais vous vous peignez dans un coin. Dès que vous touchez la fin de votre tableau, vous avez à faire un très opération coûteuse ou écrire tout un tas de code maintenant traiter ce problème. 

Alors que faire si la place nous avons eu quelque chose qui s'appelle une liste, ou une liste liée en particulier? Et si au lieu d'avoir rectangles dos à dos à dos, nous avons rectangles qui laissent un peu peu de marge de manœuvre entre eux? Et même si je l'ai dessiné ce photo ou adapté cette image de l'un des textes ici d'être de retour à dos à dos très ordonnée, en réalité, l'un de ces rectangles pourrait être ici en mémoire. L'un d'eux pourrait être ici. L'un d'eux pourrait être ici, ici, et ainsi de suite. 

Mais que faire si nous avons tiré, dans ce cas, des flèches que le lien en quelque sorte ces rectangles ensemble? En effet, nous avons vu une technique incarnation d'une flèche. Qu'avons-nous utilisé au cours des dernières jours, sous le capot, est représentatif d'une flèche? Un pointeur, non? 

Alors que faire si, au lieu de simplement stocker les numéros, comme 9, 17, 22, 26, 34, si nous avons stocké pas seulement un numéro, mais un pointeur à côté de chaque numéro? Alors que tout comme vous enfiler une aiguille à travers tout un tas de tissu, les choses d'une certaine manière à lier ensemble, de même possible nous avec des pointeurs, comme incarné par des flèches ici, sorte de tisser ces rectangles individuels en utilisant efficacement un pointeur à côté de chaque numéro que souligne une certaine prochain numéro, qui souligne à son tour, un certain nombre prochaine? En d'autres termes, ce si nous voulions réellement de mettre en œuvre quelque chose comme ça? Eh bien, malheureusement, ces rectangles, au moins l'une avec 9, 17, 22, et ainsi de suite, ceux-ci ne sont plus placettes avec des chiffres simples. Le fond, rectangle 9 ci-dessous, par exemple, représente ce qui devrait soit un pointeur, 32 bits. Maintenant, je ne suis pas encore au courant de tout type de données en C qui vous donne non seulement un int un pointeur, mais tout à fait. 

Alors, quelle est la solution si nous voulons d'inventer notre propre réponse à cela? Ouais? 

PUBLIC: [inaudible] 

DAVID J. Malan: Qu'est-ce que c'est? 

PUBLIC: Nouvelle structure. 

DAVID J. Malan: Ouais, alors pourquoi ne nous créons pas une nouvelle structure, ou en C, une structure? Nous avons vu struct avant, si brièvement, où nous avons traité avec une structure de l'étudiant comme ça, qui avait un nom et une maison. Dans Pset 3 évasion vous avez utilisé un ensemble de tas de GRECT et GOvals structs-- Stanford créé pour que informations se regroupent. Alors que faire si nous prenons cette même idée de les mots-clés "typedef" et "struct" et puis des choses spécifiques, étudiant, et d'évoluer dans ce qui suit: typedef struct node-- et le noeud est juste une informatique très générique terme de quelque chose dans une structure de données, un récipient dans une structure de données. Un noeud je prétends va avoir un int n, tout simple, et puis un peu plus cryptique, cette deuxième ligne, noeud de struct * prochaine. Mais en termes moins techniques, quelle est cette deuxième ligne de code à l'intérieur des accolades? Ouais? 

PUBLIC: [inaudible] DAVID J. Malan: A pointeur vers un autre nœud. Alors certes, la syntaxe un peu cryptique. Mais si vous lisez la lettre, est à côté du nom d'une variable. Quel est son type de données? C'est un peu verbeux cette fois, mais c'est de nœud de structure de type *. Chaque fois que nous avons vu quelque chose étoile, signifie que c'est un pointeur sur ce type de données. Alors est apparemment une prochaine pointeur vers un noeud de structure. 

Maintenant, ce qui est un noeud de structure? Eh bien, remarquez que vous voyez ces mêmes mots en haut à droite. Et en effet, vous voyez aussi le mot "Noeud" ici en bas à gauche. Et c'est en fait juste une commodité. Notez que dans notre définition de l'étudiant il ya le mot «étudiant» qu'une seule fois. Et c'est parce que l'élève Il ne s'agissait pas d'auto-référentielle. Il n'y a rien à l'intérieur d'un étudiant qui doit pointer vers un autre étudiant, persay. Ce serait en quelque sorte bizarre dans le monde réel. 

Mais avec un noeud dans un lié liste, nous ne voulons d'un noeud être référentielle à un objet similaire. Et remarquez le changement n'est pas ici juste ce qui est à l'intérieur des accolades. Mais nous ajoutons le mot «nœud» dans la partie supérieure, ainsi que ajouter à la partie inférieure au lieu de «étudiant». Et ce n'est qu'un détail technique de sorte que, encore une fois, votre structure de données peut être auto-référentiel, de sorte qu'une nœud peut pointer vers un autre tel noeud. 

Alors, quelle est cette fin de compte va signifier pour nous? Eh bien, l'un, ce genre de choses à l'intérieur est le contenu de notre nœud. Cette chose ici, en haut à droite, est tellement que, encore une fois, on peut se référer à nous-mêmes. Et puis les choses à l'extérieur, même si le noeud est un nouveau terme, peut-être, il est toujours le même comme étudiant et ce était sous le capot en SPL. 

Donc, si nous voulions maintenant pour commencer la mise en œuvre de cette liste chaînée, comment pourrions-nous traduire quelque chose comme ça à coder? Eh bien, nous allons voir juste un exemple d'un programme qui utilise en fait une liste chaînée. Parmi le code de distribution d'aujourd'hui est un programme appelé Liste zéro. Et si je n'ai plus ce que j'ai créé une super- interface graphique simple, interface utilisateur graphique, mais il est vraiment juste printf. Et maintenant, je me suis donné un peu le menu dire les options Supprimer, Insérer, Recherche, et le Traverse. Et Quitter. Ce sont des opérations communes sur un juste structure de données appelée une liste de lien. 

Maintenant, Supprimer va supprimer un numéro de la liste. Insérer va ajouter un numéro de la liste. Recherche va regarder pour numéro dans la liste. Et traverse est juste une façon élégante de dire, marcher à travers la liste, l'imprimer, mais c'est tout. Ne pas modifier en aucune façon. 

Essayons donc de cela. Allons de l'avant et de type 2. Et puis je vais insérer le numéro, dire 9. Entrée. Et maintenant, mon programme est juste programmée à-dire, la liste est maintenant 9. Maintenant, si je vais de l'avant et ne Insérez à nouveau, laisser moi aller de l'avant et zoom arrière et tape 17. Ma liste est maintenant 9, puis 17. Si je fais insérer à nouveau, nous allons sauter un. Au lieu de 22, comme par l'image que nous avons été regardant ici, permettez-moi d'intervenir avant et insérer 26 prochain. Je vais donc saisir 26. La liste est comme je le pense. Mais maintenant, juste pour voir si ce code va être souple, laissez-moi maintenant Type 22, dans lequel au moins conceptuellement, si nous sommes En gardant cela triée, qui est en effet va être un autre objectif en ce moment, devrait passer entre 17 et 26. Alors j'ai frappé sur Entrée. En effet, cela fonctionne. Et maintenant laissez-moi insérer le dernier, par l'image, 34. 

Bien. Donc pour l'instant je vais prévoir que Supprimer et le Traverse ainsi Rechercher font, en fait, travailler. En fait, si je ne cours Recherche, nous allons rechercher le numéro 22, Entrée. Il a trouvé 22. Donc, c'est ce que ce Liste programme Zéro fait. 

Mais qu'est-ce qui se passe réellement sur qui implémente ce? Eh bien, tout d'abord je pourrais avoir, et même Je n'ai, un fichier appelé list0.h. Et quelque part là-dedans est ce ligne, typedef, noeud de structure, alors j'ai mes accolades, int n, et alors struct-- quelle était la définition? noeud de Struct prochaine. Donc, nous avons besoin de l'étoile. Maintenant, techniquement, nous entrons dans l'habitude de dessiner ici. Vous pouvez voir les manuels et références en ligne le font là-bas. C'est fonctionnellement équivalent. En fait, il s'agit d'un peu plus typique. Mais je serai conforme à ce que nous avons fait la dernière fois et faisons. Et puis enfin, je vais le faire. 

Ainsi, dans un fichier d'en-tête quelque part, dans list0.h aujourd'hui, c'est cette définition de struct, et peut-être d'autres choses. Pendant ce temps, il ya list0c va être un certain nombre de choses. Mais nous allons tout simplement commencer et ne pas finir ce. List0.h est un fichier que je veux d'inclure dans mon dossier de C. Et puis à un moment je suis va avoir int, principal, annuler. Et puis je vais ont une certaine to-do c'est ici. Je vais aussi avoir un prototype, comme vide, la recherche, int, n, dont le but dans la vie est à rechercher un élément. Et puis ici je prétends en le code d'aujourd'hui, nulle recherche, int, n, pas de point-virgule, mais accolades ouvertes. Et maintenant, je veux chercher quelque sorte pour un élément dans la liste. Mais nous n'avons pas assez informations à l'écran pour l'instant. Je n'ai pas fait représenté la liste elle-même. Donc, d'une façon que nous pourrions mettre en œuvre une liste liée à un programme c'est que je sorte de veux faire quelque chose comme déclarer liste liée ici. Par souci de simplicité, je vais faire ce mondial, même si en général nous ne devrait pas faire trop. Mais il va simplifier cet exemple. Je tiens donc à déclarer une liste chaînée ici. Maintenant, comment pourrais-je faire cela? 

Voici la photo d'une liste chaînée. Et je n'aime pas vraiment savoir à l'instant comment Je vais aller de représenter tant de choses avec un seul variable de la mémoire. Mais penser en arrière un instant. Pendant tout ce temps, nous avons eu cordes, que nous avons ensuite révélé être des tableaux de caractères, que nous avons ensuite révélé être juste un pointeur pour le premier caractère dans un tableau de caractères que NULL résilié. Donc, par cette logique, et avec ce image type de l'ensemencement vos pensées, Qu'avons-nous besoin d'écrire en fait dans notre Code pour représenter une liste chaînée? Combien de ces informations devons-nous à saisir dans le code C, diriez-vous? Ouais? 

PUBLIC: Nous avons besoin d'un pointeur vers un noeud. DAVID J. Malan: Un pointeur vers un noeud. En particulier, le nœud qui serait votre instincts de garder un pointeur vers? 

AUDIENCE: Le premier nœud. 

DAVID J. Malan: Ouais, probablement que la première. Et remarquez, la première le noeud est de forme différente. C'est seulement la moitié de la taille de la structure, parce que c'est en effet seulement un pointeur. Donc, ce que vous pouvez en effet faire est de déclarer une liste chaînée à être de type noeud *. Et nous allons simplement appeler la première et l'initialiser à NULL. Donc nul, encore une fois, est venue dans l'image ici. Non seulement est nulle utilisé comme comme un spécial valeur de retour pour des choses comme getString et malloc, null est aussi le zéro pointeur, l'absence d'un pointeur, si vous voulez. Cela signifie simplement que rien n'est encore ici. Maintenant, la première, j'aurais pu appelé cette chose. J'aurais pu appelé "liste" ou n'importe quel nombre d'autres choses. Mais je l'appeler «première» de sorte que qu'il s'aligne avec cette image. Ainsi, tout comme une chaîne peut être représenté avec l'adresse de son premier octet, si possible une liste chaînée. Et nous verrons d'autres données structures sont représentées avec un seul pointeur, une flèche de 32 bits, pointant au premier noeud dans la structure. 

Mais maintenant, nous allons anticiper un problème. Si je suis seulement se souvenir dans mon programme l'adresse du premier noeud, le premier rectangle dans cette structure de données, ce qui avait mieux être le cas à propos de la mise en œuvre du reste de ma liste? Qu'est-ce que c'est un détail clé qui va de veiller à ce que cela fonctionne réellement? Et par "fonctionne réellement" je moyenne, un peu comme une chaîne, nous laisse partir du premier caractère au nom de Davin à la seconde, à la troisième, à la quatrième, à la fin, comment savons-nous quand nous sommes à la fin d'une liste chaînée qui ressemble à ceci? Quand il est nul. Et j'ai représenté cette sorte de comme un ingénieur puissance électrique, avec la petite mise à la terre symbole, en quelque sorte. Mais cela signifie simplement nulle dans ce cas. Vous pouvez dessiner n'importe quel nombre des moyens, mais cet auteur arrivé à utiliser ce symbole ici. 

Tant que nous sommes cordage tous ces noeuds ensemble, seulement à se rappeler où la première est, aussi longtemps que nous mettons un symbole spécial à le dernier noeud de la liste, et nous utiliserons nulle, parce que c'est ce que nous avons à notre disposition, cette liste est complète. Et même si je ne vous donne un pointeur vers le premier élément, vous, le programmeur, peut certainement accéder au reste de celui-ci. Mais laissons vos esprits se promener un peu, s'ils ne sont pas déjà tout ce qui est wandered-- va être le temps d'exécution de rien trouver dans cette liste? Merde, il est grand O de n, qui n'est pas mauvais, en toute équité. Mais il est linéaire. Nous avons renoncé à ce dispositif de tableaux en déplaçant plus vers cette image de façon dynamique tissés ensemble ou liés noeuds? Nous avons renoncé à accès aléatoire. Un tableau est agréable parce que tout mathématiquement est de retour à dos à dos à dos. Même si cette image semble assez, et même si elle ressemble à ces nœuds sont bien espacées, dans la réalité ils pourraient être n'importe où. Ox1, OX50, Ox123, Ox99, ces noeuds pourraient être n'importe où. Parce que malloc fait allouer de la mémoire dans le tas, mais partout dans le tas. Vous ne savez pas nécessairement que c'est va être dos à dos à dos. Et si cette image dans la réalité d' ne va pas être tout à fait cette jolie. 

Donc, il va prendre un peu de travailler à mettre en œuvre cette fonction. Donc, nous allons mettre en œuvre la recherche maintenant. Et nous allons voir une sorte de façon intelligente de le faire. Donc, si je suis une fonction de recherche et Je me donne une variable, entier n à chercher, j'ai besoin de savoir l' nouvelle syntaxe pour regarder à l'intérieur d'une structure qui est souligné, de trouver n. Donc, nous allons le faire. 

Alors d'abord je vais aller avant et déclarer un noeud *. Et je vais l'appeler pointeur, juste par convention. Et je vais de l'initialiser à la première. Et maintenant, je peux le faire dans un certain nombre de façons. Mais je vais prendre une approche commune. Alors que le pointeur n'est pas égal à nul, et c'est la syntaxe correcte. Et cela signifie juste faire ce qui suit, de sorte Tant que vous n'êtes pas en montrant rien. Qu'est-ce que je veux faire? 

Si pointeur point n, permettez-moi de revenir pour que, equals-- égal quoi? Quelle est la valeur que je cherche? Le n réel qui a été transmise. Alors, voici une autre caractéristique de C et de nombreuses langues. Même si le noeud de structure appelée a une valeur n, tout à fait légitime d'avoir aussi un argument locale ou variable appelé n. Parce que même nous, avec yeux de l'homme, peuvent distinguer ce que n est probablement différent de ce n. Parce que la syntaxe est différente. Vous avez un point et un pointeur, alors que celui-ci n'a pas une telle chose. Donc, c'est OK. C'est OK pour les appeler les mêmes choses. 

Si je trouve ne vous cela, je suis va vouloir faire quelque chose comme vous annonçons que nous avons trouvé n. Et nous allons laisser cela comme un commenter ou code pseudo. Sinon, et voici la partie intéressante, ce ce que je veux faire si le noeud courant est pas n contenant que je me soucie? Comment puis-je obtenir les résultats suivants? Si mon doigt à l' moment est PTR, et c'est pointant à quelque la première est dirigée vers, comment puis-je passer mon doigt au noeud suivant dans le code? Eh bien, ce qui est le fil d'Ariane que nous sommes va suivre dans ce cas? PUBLIC: [inaudible]. DAVID J. Malan: Ouais, donc la prochaine. Donc, si je reviens à ma code ici, en effet, je suis aller de l'avant et dire pointeur, qui est juste un variable-- temporaire c'est un nom bizarre, ptr, mais c'est comme temp-- Je vais mettre pointeur égal à tout ce pointeur is-- et encore une fois, cela va être un peu buggé pour un point moment-- prochaine. En d'autres termes, je vais prendre mon doigt qui est en montrant ce noeud ici et je vais vous dire, vous savez ce, jetez un oeil à la zone suivante et déplacez votre doigt pour quel que soit son pointé. Et cela va répéter, répéter, répéter. Mais quand est-ce mon doigt arrêter de faire quoi que ce soit? Dès que quelle ligne de coups de pied de code dans? PUBLIC: [inaudible] DAVID J. Malan: Si le point en pointeur n'est pas égale à null. À un certain moment de mon doigt va être montrant null et je vais réaliser c'est la fin de cette liste. Maintenant, c'est un peu mensonge pour plus de simplicité. Il s'avère que même si nous vient d'apprendre cette notation point pour les structures, pointeur n'est pas une structure. ptr, c'est quoi? Juste pour être plus tatillon. Il s'agit d'un pointeur vers un noeud. Ce n'est pas un noeud lui-même. Si je n'avais pas étoiles ici, pointeur absolutely-- c'est un nœud. C'est comme la première semaine déclaration d'une variable, même si le mot «nœud» est nouvelle. 

Mais dès que nous introduisons une étoiles, c'est maintenant un pointeur vers un noeud. Et malheureusement, vous ne pouvez pas utiliser la notation par points pour un pointeur. Vous devez utiliser la flèche notation, qui, étonnamment, C'est la première fois qu'un morceau de la syntaxe semble intuitive. Cela ressemble littéralement comme une flèche. Et donc c'est une bonne chose. Et ici littéralement ressemble à une flèche. Donc, je pense que c'est la la-- je ne fais pas pense que je suis trop commettre ici-- je pense que c'est la dernière nouvelle pièce de la syntaxe que nous allons voir. Et heureusement, il est en effet un peu plus intuitive. 

Maintenant, pour ceux d'entre vous qui pourraient préférer l'ancienne, vous pouvez toujours utiliser la notation par points. Mais selon de lundi la conversation, nous avons d'abord besoin d'y aller, aller à cette répondre, puis accéder au champ. Donc, c'est aussi correct. Et franchement, c'est un peu plus pédant. Vous êtes littéralement dire, déréférencer le pointeur et y aller. Puis saisir .n, le champ appelé n. Mais franchement, personne ne veut taper ou lire. Et si le monde inventé la notation de la flèche, qui est équivalent, identique, c'est juste du sucre syntaxique. Ainsi, une façon élégante de dire ce semble meilleure, ou semble plus simple. 

Alors maintenant, je vais faire autre chose. Je vais dire "casser" une fois que je n'ai trouvé si je ne garde pas le chercher. Mais ce n'est l'essentiel d'une fonction de recherche. Mais il est beaucoup plus facile, dans le fin, de ne pas marcher dans le code. C'est en effet la mise en œuvre formelle de la recherche dans le code de distribution d'aujourd'hui. J'ose dire que insert n'est pas particulièrement amusant à parcourir visuellement, n'est pas non plus supprimer, même si à la fin de la journée ils se résument à assez heuristiques simples. 

Donc, nous allons le faire. Si vous aurez l'humour moi ici, je l'ai fait apporter un tas de balles anti-stress. J'ai apporté un tas de chiffres. Et pourrions-nous obtenir quelques bénévoles à représenter 9, 17, 20, 22, 29, et 34? Donc, essentiellement, tout le monde qui est ici aujourd'hui. C'était un, deux, trois, quatre, cinq, six personnes. Et j'ai demandé à go-- voir, pas un dans le dos soulève leurs mains. OK, un, deux, trois, quatre, five-- permettez-moi de charger balance-- six. OK, vous venez sur place six. Nous aurons besoin d'autres personnes. Nous avons apporté des boules de stress supplémentaires. Et si vous pouviez, pour un instant, ligne vous place juste comme cette image ici. 

Bien. Voyons, quel est votre nom? 

PUBLIC: Andrew. 

DAVID J. Malan: Andrew, vous êtes le numéro 9. Ravi de vous rencontrer. Voici. PUBLIC: Jen. DAVID J. Malan: Jen. David. Numéro 17. Oui? 

PUBLIC: Je suis Julia. 

DAVID J. Malan: Julia, David. Nombre 20. PUBLIC: Christian. DAVID J. Malan: Christian, David. Numéro 22. Et? 

PUBLIC: JP. DAVID J. Malan: JP. Numéro 29. Donc, aller de l'avant et obtenir in-- Uh oh. Uh oh. Veille. 20. Quelqu'un at-il un marqueur? PUBLIC: J'ai un Sharpie. DAVID J. Malan: Vous avez un Sharpie? Dáccord. Et quelqu'un at-il un morceau de papier? Enregistrer la conférence. Allons. PUBLIC: Nous avons obtenu. DAVID J. Malan: nous surprendre? Très bien, merci. Et c'est parti. Était-ce de vous? Vous venez d'enregistrer le jour. Donc 29. Bien. Je écorché 29, mais OK. Aller de l'avant. Très bien, je vais vous donner votre stylo momentanément. Nous avons donc ces gens ici. Ayons un autre. Gabe, voulez-vous jouer le premier élément ici? Nous aurons besoin de vous faire remarquer à ces bons gens. Donc, 9, 17, 20, 22, sorte de 29, puis 34. Avons-nous perdu quelqu'un? J'ai un 34. Où did-- OK, qui veut être 34? OK, venez sur place, 34. Très bien, ce sera vaut bien le point culminant. Quel est votre nom? 

PUBLIC: Peter. 

DAVID J. Malan: Peter, venez sur place. Bon, alors voici une tas ensemble de nœuds. Chacun de vous les gars représente l'un de ces rectangles. Et Gabe, le peu étrange Man Out, représente la première. Ainsi, son pointeur est un peu plus petit sur l'écran de tout le monde. Et dans ce cas, chacun de vos gauche mains va soit orienté vers le bas, représentant de ce fait nulle, de sorte que juste l'absence d'un pointeur, ou il va être dirigée à un nœud à côté de vous. 

Donc maintenant si vous ornez vous comme l'image ici, aller de l'avant et le point à l'autre, avec Gabe en particulier pointage à numéro 9 pour représenter la liste. OK, et le numéro 34, de la main gauche devrait seulement être dirigée vers le sol. 

OK, donc c'est la liste chaînée. Donc, c'est le scénario en question. Et en effet, c'est représentatif d'une classe de problèmes que vous pourriez essayer de résoudre avec le code. Vous souhaitez insérer en fin de compte un nouvel élément dans la liste. Dans ce cas, nous allons essayez d'insérer le numéro 55. Mais il y aura différents cas à considérer. Et en effet, cela va être un de l'ensemble de la situation des plats à emporter ici, est, quels sont les différents cas. Quels sont les différents si les conditions ou branches que votre programme pourrait avoir? 

Eh bien, le nombre que vous essayez de insert, dont nous savons maintenant à 55, mais si vous ne saviez pas à l'avance, si j'ose dire tombe dans au moins trois les situations possibles. Où peut-être un nouvel élément? PUBLIC: Et la fin ou au milieu. DAVID J. Malan: A la fin, dans au milieu, ou au début. Donc, je prétends qu'il ya au moins trois problèmes que nous avons besoin de résoudre. Choisissons ce qui est peut-être sans doute le plus simple un, où le nouvel élément appartient au début. Donc, je vais avoir le code tout à fait comme la recherche, que je viens d'écrire. Et je vais devoir ptr, qui Je représente ici avec mon doigt, comme d'habitude. 

Et rappelez-vous, quelle est la valeur avons-nous initialisons ptr? Donc, nous avons initialisé à null initialement. Mais alors qu'est-ce que nous faisons lorsque nous trouvaient à l'intérieur de notre fonction de recherche? Nous avons mis en elle égale à la première, qui ne signifie pas le faire. Si je mets ptr égale à la première, ce qui devrait être vraiment ma main pointant? Droite. Donc, si Gabe et moi allons être des valeurs égales ici, nous devons à la fois point numéro 9. 

Donc, ce fut le début de notre histoire. Et maintenant, c'est juste simple, même si la syntaxe est nouveau. Conceptuellement, cela est tout simplement la recherche linéaire. Is 55, égale à 9? Ou plutôt, disons moins de 9. Parce que je suis en train de savoir où mettre 55. Moins de 9, à moins de 17, moins de 20, moins de 22, moins de 29, moins de 34, no. Alors maintenant, nous sommes dans le cas l'un des au moins trois. 

Si je veux insérer 55 ici, ce lignes de code nécessaire pour se exécutés? Comment cette image de les humains ont besoin de changer? Que dois-je faire avec ma main gauche? Cela devrait être nulle au départ, parce que je suis à la fin de la liste. Et ce qui devrait arriver ici avec Peter, était-ce? Il va évidemment à pointer vers moi. Donc, je prétends qu'il ya au moins deux lignes de code dans le code à partir d'aujourd'hui de l'échantillon qui va mettre en œuvre cette scénario d'ajouter 55 à la queue. Et pourrais-je avoir quelqu'un hop et juste représenter 55? Très bien, vous êtes le nouveau 55. 

Alors maintenant, que faire si la prochaine scénario se présente, et nous voulons ajouter à la début ou à la tête de cette liste? Et quel est votre nom, le numéro 55? 

PUBLIC: Jack. 

DAVID J. Malan: Jack? OK, nice to meet you. Bienvenue à bord. Alors maintenant, nous allons insérer, par exemple, le nombre 5. Voici le deuxième cas de la trois, nous est venu avec avant. Ainsi, si 5 appartient au début, nous allons voir comment nous trouvons cela. Je initialiser mon ptr pointeur vers le numéro 9 de nouveau. Et j'ai réalisé, oh, 5 est inférieur à 9. Donc, fixer cette image pour nous. Dont les mains, Gabe ou David ou-- quel est le nom de numéro 9? 

PUBLIC: Jen. 

DAVID J. Malan: la hands-- de Jen qui de nos mains il changer? OK, donc Gabe souligne à quel moment? Chez moi. Je suis le nouveau nœud. Donc, je vais juste sorte de mouvement ici pour voir visuellement. Et pendant ce temps qu'est-ce que je tiens à signaler que? Encore où je pointe. Alors, c'est ça. Donc vraiment une ligne de correctifs de code cette question, il semblerait. Très bien, alors c'est une bonne chose. Et quelqu'un peut-il être un espace réservé pour 5? Venez sur place. Nous vous aiderons à reprendre la prochaine fois. 

Très bien, alors maintenant-- et En aparté, les noms Je ne fais pas mention explicite de droit maintenant, pointeur pred, prédécesseur pointeur et nouveau pointeur, c'est seulement les prénoms dans l'exemple de code pour les pointeurs ou mes mains c'est le genre de pointage autour. Quel est votre nom? 

PUBLIC: Christine. 

DAVID J. Malan: Christine. Bienvenue à bord. Très bien, alors nous allons examiner maintenant un scénario un peu plus ennuyeux, par lequel je veux insérer quelque chose comme 26 dans cette. 20? Quoi? Ceux-ci soient: une bonne chose que nous ayons ce stylo. Très bien, 20. Si quelqu'un pouvait obtenir un autre morceau de papier prêt, juste à case-- tout droit. Oh, intéressant. Eh bien c'est un exemple d'un bug de conférence. OK alors quel est votre nom? PUBLIC: Julia. DAVID J. Malan: Julia, pouvez-vous pop sur et prétendre que vous étiez jamais là? OK, ce n'est jamais arrivé. Merci. Donc, supposons que nous voulons insérer Julia dans cette liste chaînée. Elle est le numéro 20. Et bien sûr, elle est va appartenir à la begin-- ne pointent pas à quoi que ce soit encore. Ainsi, votre main peut être genre de bas nulle ou une valeur à ordures. Disons l'histoire rapide. Je fais remarquer au numéro 5 cette fois. Ensuite, je vérifie 9. Ensuite, je vérifie 17. Ensuite, je vérifie 22. Et je me rends compte, ooh, Julia doit aller avant le 22. Alors, que faut-il faire? Dont les mains ont besoin de changer? Julia, la mienne, ou-- quel est votre nom? 

PUBLIC: Christian. 

DAVID J. Malan: Christian ou? 

PUBLIC: Andy. 

DAVID J. Malan: Andy. Christian ou Andy? Andy doit pointer à? Julia. Bien. Alors Andy, voulez-vous montrer à Julia? Mais attendez une minute. Dans l'histoire jusqu'à présent, Je suis le genre de l'un en charge, dans le sens où pointeur est la chose qui est déplacer dans la liste. Nous pourrions avoir un nom pour Andy, mais il n'y a pas variable appelée Andy. La seule autre variable que nous avons est la première, qui est représenté par Gabe. 

C'est en fait pourquoi donc Jusqu'à présent, nous n'avons pas besoin de cela. Mais maintenant, sur l'écran, il est parler à nouveau de pointeur pred. Alors permettez-moi d'être plus explicite. Si ce n'est pointeur, je ferais mieux de obtenir un peu plus intelligent sur mon itération. Si cela ne vous dérange pas ma passant par ici nouveau, pointant ici, pointant ici. Mais laissez-moi un pointeur pred, prédécesseur pointeur, c'est type de pointage à l' élément J'étais juste à. Donc, quand je vais ici, maintenant mes mises à jour de la main gauche. Quand je vais ici mes mises à jour de la main gauche. Et maintenant, j'ai non seulement un pointeur vers l'élément qui va après Julia, J'ai encore un pointeur vers Andy, l'élément avant. Donc, vous avez accès, en substance, chapelure, si vous voulez, pour tous les pointeurs nécessaires. 

Donc, si je montre Andy et je suis aussi pointer à Christian, dont les mains devrait maintenant être fait ailleurs? Donc Andy peuvent maintenant signaler à Julia. Julia peut maintenant indiquer à Christian. Parce qu'elle peut copier mon le pointeur de la main droite. Et qui vous met efficacement retour dans ce lieu ici. Donc en bref, même si ce est nous prendre sorte de toujours à mettre à jour une réalité liste chaînée, réaliser que les opérations de sont relativement simples. Il s'agit d'un, deux, trois lignes de code en fin de compte. Mais enroulé autour de ceux lignes de code vraisemblablement C'est un peu logique que efficace pose la question, où en sommes-nous? Sommes-nous au début, le milieu ou la fin? 

Maintenant, il ya certainement une autre opérations que nous pourrions mettre en œuvre. Et ces photos ici représentent seulement ce que nous venons de faire avec les humains. Qu'en est-il l'enlèvement? Si je veux, par exemple, supprimer le numéro 34 ou 55, Je pourrais avoir le même genre de code, mais je vais avoir besoin d'une ou deux étapes. Parce que ce qui est nouveau? Si je retire quelqu'un à la fin, comme le nombre de 55, puis 34, ce qui a aussi de changer ce que je fais cela? Je dois pas evict-- quel est votre nom? 

PUBLIC: Jack. 

DAVID J. Malan: Jack. Je dois non seulement evict-- libre Jack, si littéralement appeler sans Jack, ou au moins le pointeur là aussi, mais maintenant ce qui doit changer avec Peter? Sa main meilleur départ vers le bas. Parce que dès que j'appelle gratuitement sur Jack, si Peter pointant toujours à Jack et je garde donc traverser la liste et l'accès de ce pointeur, c'est là que notre vieil ami segmentation la faute pourrait en fait botter. Parce que nous avons donné l' sauvegarde de la mémoire de Jack. 

Vous pouvez y rester maladroitement pendant un moment. Parce que nous avons juste un couple opérations finales à prendre en compte. Démontage de la tête de la liste, ou la beginning-- et celui de un peu ennuyeux. Parce que nous devons savoir que Gabe est une sorte de spécial dans ce programme. Car en effet, il a son propre pointeur. Il ne s'agit pas seulement d'être pointé, comme presque tout le monde ici. 

Ainsi, lorsque la tête de la liste est enlevé, dont les mains ont besoin de changer maintenant? Quel est votre nom? 

PUBLIC: Christine. 

DAVID J. Malan: Je suis terrible au nom, apparemment. Donc, Christine et Gabe, dont les mains ont besoin de changer quand nous essayons de retirer Christine, numéro 5, à partir de l'image? OK, donc faisons Gabe. Gabe va pointer, sans doute, au numéro 9. Mais qu'est-ce qui doit se passer à côté? PUBLIC: Christine devrait nulle [inaudible]. DAVID J. Malan: OK, nous devrions probablement make-- j'ai entendu "null" quelque part. PUBLIC: Null et sa libre. DAVID J. Malan: Null quoi? PUBLIC: Null et sa libre. DAVID J. Malan: Null et sa libre. Donc, c'est très facile. Et c'est parfait que vous êtes maintenant sorte de se tenir là, ne faisant pas partie. Parce que vous avez été découplé de la liste. Vous avez effectivement été orphelins de la liste. Et si nous avions mieux appeler gratuitement dès maintenant sur Christine donner que la mémoire de retour. Sinon chaque fois que nous supprimer un noeud dans la liste nous pourrions faisons la liste plus courte, mais pas réellement décroissant la taille de la mémoire. Et si nous continuons d'ajouter et ajoutant, ajouter des choses à la liste, mon ordinateur pourrait devenir plus lent et plus lent et plus lent, parce que je suis à court de mémoire, même si je ne suis pas fait à l'aide de bytes de Christine de mémoire plus. 

Donc à la fin il ya d'autres scénarios d'enlèvement course-- dans le milieu, l'élimination à la fin, comme nous l'avons vu. Mais le plus intéressant défi est maintenant va être de considérer exactement ce que le temps d'exécution est. Donc, non seulement vous pouvez garder votre morceaux de papier, si, Gabe, vous ne me dérangerait pas de donner chacun une balle anti-stress. Merci beaucoup à notre liste chaînée de bénévoles ici, s'il vous plaît. 

[Applaudissements] 

DAVID J. Malan: Très bien. Alors quelques analytique des questions puis, si je pouvais. Nous avons vu cette notation avant, grand O et l'oméga, les limites supérieures et des bornes inférieures sur le temps d'un algorithme en cours d'exécution. Donc, nous allons examiner tout quelques questions. 

Un, et nous l'avons dit avant, ce qui est le fonctionnement temps de recherche d'un liste en termes de grand O? Qu'est-ce que c'est une limite supérieure sur le fonctionnement temps de recherche d'une liste chaînée mis en œuvre par nos bénévoles ici? Il est grand O de n, linéaire. Parce que dans le pire des cas, l'élément, comme 55, nous pourrions être à la recherche d'pourrions être là où Jack était, tout le chemin à la fin. Et malheureusement, contrairement à un tableau nous ne pouvons pas obtenir la fantaisie cette fois. Même si tous nos humains étaient triés à partir de petits éléments, 5, sur toute la hauteur de l'élément plus grand, 55, c'est généralement une bonne chose. Mais qu'est-ce que cette hypothèse ne nous permet de faire? PUBLIC: [inaudible] DAVID J. Malan: Dites à nouveau? PUBLIC: accès aléatoire. DAVID J. Malan: accès aléatoire. Et à son tour, cela signifie que nous ne pouvons plus utiliser zéros faible, l'intuition, et l'évidence de l'utilisation binaire recherche et de diviser et conquérir. Parce que même si nous l'homme ne pouvait évidemment voir que Andy ou chrétienne étaient à peu près au milieu de la liste, nous savons seulement que comme un ordinateur en parcourant la liste dès le début. Nous avons donc renoncé à ce que l'accès aléatoire. 

Donc grand O n est maintenant la partie supérieure lié à notre temps de recherche. Qu'en est-il oméga de notre recherche? Quelle est la limite inférieure sur la recherche pour un nombre dans cette liste? PUBLIC: [inaudible] DAVID J. Malan: Dites à nouveau? PUBLIC: Un. DAVID J. Malan: One. Temps si constant. Dans le meilleur des cas, Christine est en effet, au début de la liste. Et nous sommes à la recherche numéro 5, alors nous l'avons trouvé. Donc, pas grand-chose. Mais elle a obtenu d'être à la au début de la liste dans ce cas. Qu'en est-il quelque chose comme Delete? Que faire si vous voulez supprimer un élément? Quelle est la limite supérieure et la limite inférieure sur la suppression de quelque chose d'un lien la liste? PUBLIC: [inaudible] DAVID J. Malan: Dites à nouveau? PUBLIC: n. DAVID J. Malan: n est en effet la borne supérieure. Parce que dans le pire des cas, nous essayons supprimer Jack, comme nous venons de le faire. Il est tout le chemin à la fin. Nous prend une éternité, ou n des mesures pour lui trouver. C'est donc une limite supérieure. C'est linéaire, bien sûr. Et le meilleur des cas durée, ou les limites inférieures dans le meilleur des cas serait temps constant. Peut-être parce que nous essayons de supprimer Christine, et nous obtenons juste de la chance elle est au début. Maintenant, attendez une minute. Gabe était aussi au début, et nous avons également de mettre à jour Gabe. Donc, ce n'était pas juste une étape. Ainsi est-il en effet constant temps, dans le meilleur des cas, à enlever l'élément le plus petit? Il est, même si cela peut être deux, trois, ou même 100 lignes de code, si c'est le même nombre de lignes, et non dans une certaine boucle, et indépendant de la taille de la liste, absolument. Suppression de l'élément à le début de la liste, même si nous devons faire face à Gabe, est encore temps constant. 

Donc, cela semble être un énorme pas en arrière. Et qu'est-ce une perte de temps si, dans la première semaine et la semaine zéro, nous avons eu non seulement code pseudo mais le code réel de mettre en œuvre quelque chose qui est journal de base n, ou connectez-vous plutôt de n, base 2, en fonction de sa durée de fonctionnement. Alors pourquoi diable aurions-nous envie de commencer en utilisant quelque chose comme une liste chaînée? Ouais. 

PUBLIC: Donc, vous pouvez ajouter éléments au tableau. DAVID J. Malan: Ainsi, vous pouvez ajouter des éléments au tableau. Et cela aussi est thématique. Et nous allons continuer à voir ce, ce compromis, beaucoup comme nous l'avons vu un compromis avec le tri par fusion. Nous ne pouvions accélérer recherche ou de tri, plutôt, si nous passons un peu plus d'espace et avoir un morceau supplémentaire d'un mémoire ou un tableau pour le tri par fusion. Mais nous passons plus de espace, mais nous gagnons du temps. Dans ce cas, nous sommes donner du temps, mais nous sommes gagner en flexibilité, dynamisme si vous voulez, qui est sans doute un élément positif. 

Nous sommes également passer espace. Dans quel sens est un lien liste plus cher en termes d'espace qu'un tableau? Où est l'espace supplémentaire vient? Ouais? 

PUBLIC: [inaudible] pointeur. 

DAVID J. Malan: Oui, nous ont également le pointeur. Donc, c'est gênant minorly en ce que je ne suis plus Je stocker juste un int pour représenter un int. Je stocker un int et un pointeur, qui est également 32 bits. Donc, je suis littéralement doubler la quantité d'espace impliqué. Donc, c'est un compromis, mais c'est dans le cas d'int. Supposons que vous n'êtes pas stocker int, mais supposons chacun de ces rectangles ou chacun de ces êtres humains représentait un mot, un mot anglais qui peut-être cinq caractères, 10 personnages, peut-être même plus. Puis en ajoutant seulement 32 plus de bits peut-être moins d'une grosse affaire. 

Et si chacun des élèves à la manifestation étaient littéralement struct étudiants qui ont des noms et des maisons et peut-être les numéros de téléphone et Twitter poignées et autres. Donc, tous les domaines, nous avons commencé parler l'autre jour, beaucoup moins d'un gros problème, nos nœuds deviennent plus intéressantes et gros pour passer, hein, un montant supplémentaire de pointeur juste pour les relier. Mais en fait, c'est un compromis. Et en effet, le code est plus complexe, car vous aurez voir en parcourant cet exemple particulier. Mais s'il y avait un texte sacré ici. Et si nous ne prenons pas une étape en arrière, mais un énorme pas en avant et mettre en œuvre un ensemble de données la structure par laquelle nous peut trouver des éléments comme Jack ou Christine ou tout autre élément dans ce tableau en vrai constante de temps? Recherche est constante. Supprimer est constante. Insérer est constante. Toutes ces opérations sont constants. Ce serait notre saint Graal. Et c'est là que nous va chercher la prochaine fois. Rendez-vous donc.