JASON HIRSCHHORN: Bienvenue à tous à la Section Seven. Nous sommes dans la semaine de sept de cours. Et ce prochain jeudi C'est Halloween donc je suis habillé comme une citrouille. Je ne pouvais pas plier et mettre sur mes chaussures, et c'est pourquoi je suis juste porter des chaussettes. Je suis également rien porter sous cela, je ne peux pas l'enlever si c'est distraire de vous. Je m'excuse d'avance pour cela. Vous n'avez pas besoin d'imaginer ce qui se passe. Je porte des boxeurs. Il est donc tout bon. 

J'ai une histoire plus pourquoi je suis habillé comme une citrouille, mais je vais sauf que pour plus tard dans cette section parce que je ne veux pour commencer. Nous avons beaucoup de choses passionnantes d'aller au cours de cette semaine. La plupart d'entre eux sont directement liés à ce l'ensemble des problèmes de la semaine, les fautes d'orthographe. Nous allons aller plus liée listes et les tables de hachage pour l'ensemble de la section. Je mets cette liste chaque semaine, une liste de ressources pour vous pour vous aider à le matériel sur ce cours. Si, à une perte ou si la recherche d'une plus d'informations, consultez l'un des ces ressources. 

Encore une fois, pset6 est des fautes d'orthographe, l'ensemble de processeurs de cette semaine. Et il vous encourage aussi, et je vous encourager, d'utiliser un autre ressources spécifiquement pour ce jeu de processeurs. En particulier, les trois que j'ai figurant sur l'écran - gdb, que nous avons été familiarisés avec et utilisent depuis un certain temps maintenant, est va être très utile cette semaine. Alors, j'ai mis que ici. Mais chaque fois que vous travaillez avec C, vous devriez toujours utiliser gdb pour déboguer vos programmes. Cette semaine Valgrind aussi. Est-ce que quelqu'un sait ce que valgrind t-il? 

PUBLIC: Il vérifie les fuites de mémoire? 

JASON HIRSCHHORN: Valgrind Détecter les fuites de mémoire. Donc, si vous quelque chose dans votre malloc programme, vous demandez de la mémoire. A la fin de votre programme, vous avez d'écrire gratuitement sur tout ce que vous avez malloced pour donner la mémoire de retour. Si vous n'écrivez pas libre à la fin et votre programme arrive à une conclusion, tout va automatiquement être libéré. Et pour les petits programmes, il est pas un gros problème. Mais si vous écrivez un long fonctionnement programme qui ne quitte pas, nécessairement, en quelques minutes ou un quelques secondes, puis des fuites de mémoire peut devenir une affaire énorme. 

Donc, pour pset6, on s'attend à ce que vous aurez zéro fuites de mémoire avec votre programme. Pour vérifier s'il ya des fuites de mémoire, valgrind exécuter et il vous donnera quelques belles sortie vous permettant de savoir si ou tout n'était pas libre. Nous pratiquons avec elle plus tard aujourd'hui, je l'espère. 

Enfin, la commande diff. Vous avez utilisé quelque chose de semblable à ce dans pset5 avec l'outil coup d'oeil. Vous a permis de regarder à l'intérieur. Vous avez également utilisé diff, aussi, par le problème réglé spec. Mais en vous autorisé à comparer deux fichiers. Vous pouvez comparer le fichier bitmap et d'info-têtes d'une solution de personnel et votre solution en pset5 si vous avez choisi d'utiliser. Diff vous permettra de faire ainsi. Vous pouvez comparer la réponse correcte pour Le problème de cette semaine mis à votre réponse et voir si elle s'aligne ou voir où les erreurs sont. 

Donc, ce sont trois bons outils vous devez utiliser pour cette semaine, et vérifier définitivement votre programme avec ces trois outils avant de se tourner po Encore une fois, comme je l'ai dit chaque semaine, si vous avez des commentaires pour moi - à la fois positive et constructive - n'hésitez pas à diriger sur le site au bas de cette diapositive et entrée là. J'apprécie vraiment tout et tous les commentaires. Et si vous me donnez des choses spécifiques que Je peux faire pour améliorer ou que je suis faisant ainsi que vous voudriez que je continue, je prends cela à coeur et vraiment essayer dur à écouter à vos commentaires. Je ne peux pas promettre que je vais faire tout, même si, comme le port d'un citrouille costume chaque semaine. 

Donc, nous allons passer la majeure partie de article, comme je l'ai mentionné, en parlant de listes chaînées et les tables de hachage, qui sera directement applicable à la problème réglé cette semaine. Les listes chaînées, nous allons passer en revue relativement rapidement, car nous avons passé un peu juste du temps qui passe au-dessus de l'article. Et donc nous allons aller droit dans le problèmes de codage pour les listes chaînées. Et puis à la fin, nous allons parler hash tables et comment ils s'appliquent à ce Le problème de la semaine défini. 

Vous avez vu ce code avant. Il s'agit d'une structure, et elle consiste à définir quelque chose de nouveau appelé un nœud. Et à l'intérieur d'un noeud y est un nombre entier ici et là est un pointeur vers un autre noeud. Nous avons vu cela avant. Cela a été à venir pour un couple de semaines maintenant. Il combine des pointeurs, qui nous avons été travailler avec, et les structures qui permettent nous combinons deux différents choses dans un type de données. 

Il ya beaucoup de choses à l'écran. Mais tout cela devrait être relativement familier avec vous. Sur la première ligne, nous déclarer un nouveau nœud. Et puis à l'intérieur que le nouveau noeud, j'ai mis en ce que l'entier le noeud à une. Nous voyons sur la ligne suivante, je fais un printf, mais j'ai grisé la commande printf parce que la très partie importante est cette ligne ici - new_node.n. Qu'est-ce que le point signifie? 

PUBLIC: Ouvrez le nœud et évaluer la valeur de n pour cela. 

JASON HIRSCHHORN: C'est tout à fait exact. Point signifie accéder à la partie n de ce nouveau noeud. Cette ligne suivante fait quoi? Michael. 

PUBLIC: Il crée un autre noeud qui va pointer vers le nouveau nœud. 

JASON HIRSCHHORN: Donc, ce n'est pas créer un nouveau nœud. Il crée un quoi? 

PUBLIC: Un pointeur. 

JASON HIRSCHHORN: Un pointeur vers un noeud, comme indiqué par ce noeud * ici. Donc il crée un pointeur vers un noeud. Et qui est-ce nœud pointe à, Michael? 

PUBLIC: New noeud? 

JASON HIRSCHHORN: New noeud. Et c'est pointant là parce que nous avons donné l'adresse du nouveau noeud. Et maintenant, dans cette ligne, nous voyons deux manières différentes de exprimer la même chose. Et je tenais à souligner la façon dont ces deux choses sont les mêmes. Dans la première ligne, nous déréférencer le pointeur. Donc, nous allons vers le noeud. C'est ce que signifie cette étoile. Nous avons déjà vu cela avec des pointeurs. Allez à ce nœud. C'est entre parenthèses. Et alors accéder via l'opérateur point l'élément n de ce noeud. 

Donc, c'est prendre la syntaxe nous avons vu ici et maintenant utiliser avec un pointeur. Bien sûr, il obtient le genre d'occupation si vous écrivez ces parenthèses - cette étoile et point. Il est un peu occupé. Donc, nous avons un peu de sucre syntaxique. Et cette ligne ici - ptr_node-> n. Cela ne exactement la même chose. Donc, ces deux lignes de code équivalent et fera exactement la même chose. 

Mais je tenais à ceux avant d'aller plus loin pour que vous compreniez que vraiment cette chose ici est juste du sucre syntaxique pour le déréférencement le pointeur et puis aller à n partie de cette structure. Une question sur ce toboggan? OK. 

Nous allons donc passer par un couple des opérations que vous pouvez faire sur listes chaînées. Une liste chaînée, rappel, est une série de nœuds qui pointent vers une autre. Et nous commençons généralement avec un pointeur appelé la tête, en général, qui pointe vers la première chose dans la liste. Ainsi, sur la première ligne, ici, nous ont d'abord notre origine L. Donc, cette chose que vous pouvez penser - ce texte ici vous pouvez penser que juste le pointeur nous avons stocké que quelque part les points au premier élément. Et dans cette liste chaînée nous avons quatre nœuds. Chaque noeud est une grosse boîte. La grande boîte à l'intérieur du grand boîte est la partie entière. Et puis nous avons une partie de pointeur. 

Ces boîtes ne sont pas à échelle, car la taille est un nombre entier, en octets? Quelle maintenant? Quatre. Et la taille est un pointeur? Quatre. Alors, vraiment, si nous devions dessiner ce à l'échelle les deux cases serait de la même taille. Dans ce cas, nous voulons insérer quelque chose dans la liste chaînée. Vous pouvez donc voir ici nous insertion cinq Nous traversons par la liste chaînée, trouver où cinq va, et puis insérez-le. 

Brisons que vers le bas et aller un peu plus lentement. Je vais rappeler à la carte. Donc, nous avons notre nœud cinq qui nous avons créé dans mallocs. Pourquoi tout le monde rit? Je plaisante. OK. Nous avons donc malloced cinq. Nous avons créé ce noeud ailleurs. Nous l'avons prêt à aller. Nous commençons à l'avant de notre liste à deux. Et nous voulons insérer dans un mode de tri. 

Donc, si nous voyons deux et nous voulons mettre dans cinq ans, que faisons-nous lorsque nous voyons quelque chose de moins que nous? Qu'est-ce? Nous voulons insérer cinq dans ce liste chaînée, mettant triée. Nous voyons le numéro deux. Alors, que faisons-nous? Marcus? 

PUBLIC: Appelez le pointeur au noeud suivant. 

JASON HIRSCHHORN: Et pourquoi faire nous allons à la prochaine? 

PUBLIC: Parce que c'est la noeud suivant dans la liste. Et nous savons que cet autre emplacement. 

JASON HIRSCHHORN: Et cinq est supérieur supérieur à deux, en particulier. Parce que nous voulons garder triée. Ainsi cinq est supérieur à deux. Donc, nous passons à la suivante. Et maintenant, nous arrivons à quatre. Et ce qui se passe quand nous arrivons à quatre? 

Cinq est supérieur à quatre. Donc, nous continuons. Et maintenant, nous sommes à six. Et que voyons-nous à six? Oui, Carlos? 

PUBLIC: Six est supérieur à cinq. 

JASON HIRSCHHORN: Six est supérieur à cinq. C'est donc là que nous voulons pour insérer cinq. Cependant, gardez à l'esprit que si nous avoir un seul pointeur ici - c'est notre pointeur supplémentaire qui est traversant la liste. Et nous pointant à six. Nous avons perdu la trace de ce vient avant six. Donc, si nous voulons insérer quelque chose dans cette liste mettant triée, nous probablement besoin de combien de pointeurs? 

PUBLIC: Deux. 

JASON Hirschhorn: Deux. Un pour garder une trace de l'actuel un et un pour garder une trace de la précédente. Il ne s'agit que d'une liste chaînée. Il va de seulement une direction. Si nous avions une liste doublement chaînée, où tout pointait à la chose après et la chose avant, puis nous n'aurions pas besoin de le faire. Mais dans ce cas, nous ne voulons pas perdre trace de ce qui est venu avant nous dans le cas nous avons besoin d'insérer quelque part cinq dans le milieu. Disons que nous avons insérons neuf. Qu'est-ce qui se passerait quand nous sommes arrivés à huit? 

PUBLIC: Vous auriez à obtenir ce point zéro. Au lieu d'avoir point zéro vous auriez pour ajouter un élément et ensuite pointer à neuf. 

JASON Hirschhorn: Exactement. Donc, nous obtenons huit. Nous arrivons à la fin de la liste, car cette pointe sur null. Et maintenant, au lieu d'avoir à pointer null pointer nous avons à notre nouveau nœud. Et nous avons mis le pointeur dans notre nouveau nœud à null. Quelqu'un at-il des questions sur l'insertion? Que faire si je ne me soucie pas en gardant la liste triée? 

PUBLIC: Collez à l' début ou la fin. 

JASON Hirschhorn: Collez à le début ou la fin. Lequel faut-il faire? Bobby? Pourquoi la fin? 

PUBLIC: Parce que le début est déjà rempli. 

JASON Hirschhorn: OK. Le début est déjà rempli. Qui veut plaider contre Bobby. Marcus. 

PUBLIC: Eh bien, vous voulez probablement coller au début parce sinon, si vous mettez à la fin, vous auriez à parcourir la liste entière. 

JASON Hirschhorn: Exactement. Donc, si nous pensons à l'exécution, le l'exécution de l'insertion à la fin serait n, la taille de ce produit. Quelle est la grande exécution de O de l'insertion au début? Constante de temps. Donc, si vous ne vous souciez pas de garder quelque chose triée, beaucoup mieux à juste insérer au début de cette liste. Et cela peut être fait en temps constant. 

OK. Opération suivante est de trouver qui d'autre - nous avons formulé ce que la recherche. Mais nous allons regarder à travers le liste chaînée pour un objet. Les gars, vous avez vu le code de rechercher avant en cours. Mais nous sorte de juste fait avec insérer, ou au moins l'insertion, quelque chose triée. Vous regardez à travers, le noeud va par noeud, jusqu'à ce que vous trouviez le numéro que vous êtes cherchez. Qu'advient-il si vous atteignez la fin de la liste? Disons que je suis à la recherche de neuf et je atteindre la fin de la liste. Que faisons-nous? 

PUBLIC: Retour faux? 

JASON Hirschhorn: Retour faux. Nous n'avons pas trouvé. Si vous arrivez à la fin de la liste et vous n'avez pas trouvé le numéro que vous êtes cherchez, il n'est pas là. Une question sur trouver? S'il s'agissait d'une liste triée, ce qui serait être différent pour notre recherche? Ouais. 

PUBLIC: Il serait trouver la première valeur C'est plus grand que celui vous cherchez et puis retourner false. 

JASON Hirschhorn: Exactement. Donc, si c'est une liste triée, si nous arrivons à quelque chose qui est plus grand que ce nous recherchons, nous n'avons pas besoin de continuer à aller à la fin de la liste. Nous pouvons à ce moment return false parce que nous n'allons pas trouver. La question est maintenant, nous avons parlé garder les listes chaînées triés, les garder non triés. Ça va être quelque chose que vous êtes probablement avoir à penser quand le problème de codage fixé cinq si vous choisir une table de hachage avec distinct approche chaînage, qui nous en parlerons plus tard. 

Mais est-il utile de garder la liste trié et ensuite être capable d'avoir peut-être des recherches plus rapides? Ou vaut-il mieux insérer rapidement quelque chose dans l'exécution constante mais avoir plus de recherche? C'est un compromis là que vous arriver à décider ce qui est plus approprié pour votre problème spécifique. Et il n'y a pas nécessairement un réponse tout à fait raison. Mais c'est certainement une décision que vous obtenez à faire, et probablement bon pour défendre que, disons, un commentaire ou deux pourquoi vous avez choisi un sur l'autre. 

Enfin, la suppression. Nous avons vu la suppression. Il est similaire à la recherche. Nous attendons de l'élément. Disons que nous essayons de supprimer six. Donc, nous trouvons six ici. La seule chose que nous devons nous assurer que nous faire, c'est que tout ce que pointe vers six - comme nous le voyons dans l'étape deux ici - tout ce qui se pointant à six besoins à sauter six maintenant et être changé à quelle que soit six pointe. Nous ne voulons pas toujours orphelin le reste de notre liste en oubliant de mettre cette pointeur précédente. Et puis parfois, selon sur le programme, ils vont juste supprimer ce noeud tout. Parfois, vous aurez envie de revenir la valeur qui se trouve dans ce nœud. C'est comme ça que la suppression de travaux. Toutes les questions sur supprimer? 

PUBLIC: Donc, si vous allez à supprimer il, voulez-vous juste utiliser gratuitement parce on peut supposer qu'il a été malloced? 

JASON Hirschhorn: Si vous voulez libérer quelque chose qui est tout à fait exact et vous malloced elle. Disons que nous voulions y retourner cette valeur. Nous pourrions revenir six et gratuit ce nœud et appel gratuit sur elle. Ou nous aurions probablement appelons libre d'abord et puis revenir six. 

OK. Passons donc à la pratique de codage. Nous allons coder trois fonctions. Le premier est appelé insert_node. Ainsi, vous avez le code que je vous ai envoyé, et si vous regardez cela plus tard vous pouvez accéder au code linked.c sur le site Web de CS50. Mais dans linked.c, il ya quelques le squelette du code qui est déjà été écrit pour vous. Et puis il ya quelques fonctions vous devez écrire. 

Nous allons d'abord écrire insert_node. Et ce ne insert_node c'est insère un nombre entier. Et vous donner l'entier dans une liste chaînée. Et en particulier, vous devez pour maintenir la liste triée du plus petit au plus grand. En outre, vous ne voulez pas insérer les doublons. Enfin, comme vous pouvez le voir insert_node retourne un bool. Donc, vous êtes censé informer l'utilisateur si l'insert a été ou non succès en retournant true ou false. A la fin de ce programme - et pour ce stade, vous n'avez pas besoin à vous soucier de quoi que ce soit libérer. Donc, tout ce que vous faites, c'est de prendre un nombre entier et l'insérer dans une liste. 

C'est ce que je vous demande de faire maintenant. Encore une fois, dans le linked.c, qui vous ont tous, est le code de squelette. Et vous devriez voir vers le bas la déclaration de la fonction de l'échantillon. Toutefois, avant d'entrer dans le coder en C, je vous encourage fortement à aller à travers les étapes que nous avons été pratiquer chaque semaine. Nous avons déjà traversé une photo de ce. Donc, vous devriez avoir une certaine compréhension de la façon dont cela fonctionne. Mais je voudrais vous encourager à écrire certains pseudo avant de plonger po Et nous allons passer en revue pseudocode en tant que groupe. Et puis une fois que vous avez écrit votre pseudo, et une fois que nous avons écrit notre pseudo en tant que groupe, vous pouvez aller dans le codage en C 

Comme un heads-up, la fonction de insert_node est probablement la plus délicate de les trois nous allons écrire parce que je ajouter des contraintes supplémentaires à la programmation, en particulier, que vous n'allez pas à insérer une doublons et que la liste devrait rester triée. Donc, c'est un programme non trivial que vous avez besoin de coder. Et pourquoi ne pas vous prendre de cinq à sept minutes pour se mettre au travail sur le pseudo et le code. Et puis nous allons commencer part en groupe. Encore une fois, si vous avez des questions juste levez la main et je viendrai autour. . 

Nous faisons aussi généralement ceux-ci - ou je ne vous dis pas explicitement peut travailler avec les gens. Mais évidemment, je vous encourage fortement, si vous avez des questions, de demander à la voisin assis à côté de vous ou même travailler avec quelqu'un d'autre si vous voulez. Cela ne doit pas nécessairement être un individu activité silencieuse. 

Commençons par écrit un certain pseudo sur la carte. Qui peut me donner la première ligne de pseudo pour ce programme? Pour cette fonction, plutôt - insert_node. Alden? 

PUBLIC: Donc, la première chose que j'ai faite a été créer un nouveau pointeur vers le noeud et je initialisé il pointant vers le même chose qui liste pointe. 

JASON Hirschhorn: OK. Donc, vous créez un nouveau pointeur à la liste, de ne pas le noeud. 

PUBLIC: Droit. Ouais. 

JASON Hirschhorn: OK. Et puis qu'est-ce que nous voulons faire? Quoi de suite? Qu'est-ce que sur le nœud? Nous n'avons pas de nœud. Nous avons juste valeur. Si nous voulons insérer un noeud, qu'est-ce que nous besoin de faire avant que nous puissions même penser l'insérer? 

PUBLIC: Oh, désolé. nous avons besoin de malloc espace pour un nœud. 

JASON Hirschhorn: Excellent. Faisons - OK. Vous ne pouvez pas atteindre cette haute. OK. Nous allons descendre, puis nous utilisons deux colonnes. Je ne peux pas aller aussi - OK. Créez un nouveau nœud. Vous pouvez créer un autre pointeur à la liste ou vous pouvez simplement utiliser la liste telle qu'elle existe. Vous n'avez pas vraiment besoin de le faire. 

Donc, nous créons un nouveau nœud. Grand. C'est ce que nous faisons d'abord. Quelle est la prochaine? 

PUBLIC: Attendez. Faut-il créer un nouveau nœud maintenant ou devrions nous attendre à faire en sorte que il n'ya pas de doublons de noeud sur la liste avant que nous créons? 

JASON Hirschhorn: Bonne question. Tenons pour plus tard parce que la majorité du temps, nous allons créer un nouveau noeud. Donc, nous allons garder ici. Mais c'est une bonne question. Si nous créons et nous trouvons un double, ce qui devrait nous faisons avant de revenir? 

PUBLIC: libérer. 

JASON Hirschhorn: Ouais. Probablement le libérer. OK. Que faisons-nous après nous créer un nouveau nœud? Annie? 

PUBLIC: Nous mettons l' nombre dans le noeud? 

JASON Hirschhorn: Exactement. Nous mettons le nombre - nous malloc espace. Je vais laisser cette tout comme une ligne. Mais vous avez raison. Nous malloc espace, puis nous mettons le nombre po Nous pouvons même mettre le pointeur partie à null. C'est exactement ça. Et puis que dire de la suite? Nous avons tiré cette image sur la carte. Alors, que faisons-nous? 

PUBLIC: Nous allons dans la liste. 

JASON Hirschhorn: Aller dans la liste. OK. Et qu'est-ce que nous vérifions à chaque noeud. Kurt, qu'est-ce que nous vérifions pour chaque noeud? 

PUBLIC: Voir si la valeur de n de ce noeud est supérieure à la valeur de n de notre noeud. 

JASON Hirschhorn: OK. Je vais faire - ouais, OK. C'est donc n - Je vais dire si la valeur est supérieure que ce nœud, alors que faisons-nous? 

PUBLIC: Eh bien, nous insérons la chose juste avant que. 

JASON Hirschhorn: OK. Donc, si c'est plus que cela, alors nous voulons insérer. Mais nous voulons insérer juste avant parce que nous devons aussi être garder la trace, alors, de ce qui était avant. Donc insérer avant. Nous avons probablement manqué quelque chose donc plus tôt. Nous avons probablement besoin d'être maintenant une trace de ce qui se passe. Mais nous reviendrons là-bas. Donc, quelle est la valeur est inférieure à? Kurt, que faisons-nous si valeur est inférieure à? 

PUBLIC: Ensuite, vous continuez à aller sauf si c'est la dernière. 

JASON Hirschhorn: j'aime ça. Alors, allez au nœud suivant. Sauf si c'est le dernier - nous allons probablement vérifiant que dans les termes d'une condition. Mais oui, noeud suivant. Et cela devient trop faible, donc nous allons passer ici. Mais si - peut tous voir cela? Si nous sommes égaux que faisons-nous? Si la valeur que nous essayons d'insérer est égale à la valeur de ce noeud? Ouais? 

PUBLIC: [inaudible]. 

JASON Hirschhorn: Ouais. Compte tenu de cette - Marcus est juste. Nous aurions pu peut-être fait quelque chose de différent. Mais étant donné que nous l'avons créé, ici nous devons libérer et revenir ensuite. Oh boy. Est-ce mieux? Comment ça? OK. Gratuit et que faisons-nous revenir, [inaudible]? OK. Avons-nous oublié quelque chose? Alors, où allons-nous garder la trace du noeud avant? 

PUBLIC: Je pense que ce serait aller après créer un nouveau nœud. 

JASON Hirschhorn: OK. Donc, au début nous allons probablement - oui, nous pouvons créer un pointeur vers une nouvelle nœud, comme un pointeur de noeud précédent et un pointeur de nœud actuel. Donc, nous allons insérer ici. Créer actuelle et précédente des pointeurs vers des noeuds. Mais quand avons-nous ajustons ces pointeurs? Où pouvons-nous faire dans le code? Jeff? 

PUBLIC: - des conditions de valeur? 

JASON Hirschhorn: Quels un en particulier? 

PUBLIC: Je suis juste confondu. Si la valeur est supérieure à ce noeud, ce que cela signifie pas que vous voulez aller au noeud suivant? 

JASON HIRSCHHORN: Donc, si notre valeur est supérieure à la valeur de ce nœud. 

PUBLIC: Oui, alors vous voudriez aller plus loin dans la ligne, non? 

JASON HIRSCHHORN: Droit. Donc, nous n'avons pas l'insérer ici. Si la valeur est inférieure à ce nœud, puis nous allons à la prochaine nœud - ou alors nous insérer avant. 

PUBLIC: Attendez, qui est ce noeud et qui est la valeur? 

JASON HIRSCHHORN: Bonne question. Valeur par cette définition de fonction c'est ce que l'on nous donne. Donc, la valeur est le nombre qu'on nous donne. Donc, si la valeur est inférieure à cette nœud, nous avons besoin de temps pour insérer. Si la valeur est supérieure à ce noeud, nous allons vers le noeud suivant. Et revenir à la question initiale, cependant, où - 

PUBLIC: Si la valeur est supérieure que ce nœud. 

JASON HIRSCHHORN: Et si que faisons-nous ici? Sweet. C'est exact. Je vais juste écrire mise à jour des pointeurs. Mais oui, avec l'actuel vous mettre à jour à pointer vers la suivante. Autre chose qui nous manque? Je vais donc saisir cette coder dans gedit. Et tandis que je fais cela, vous pouvez avoir un quelques minutes de plus pour travailler sur le codage dans cette C. 

J'ai donc entrée du pseudo. Une note rapide avant que nous commencions. Nous pourrions ne pas être en mesure de complètement terminer ce dans tous les trois de ces fonctions. Il est des solutions correctes pour eux que je vais envoyer sur vous les gars après l'article, et il sera être affiché sur CS50.net. Donc, je ne vous encourage pas à aller voir les sections. Je vous encourage à essayer ces sur votre posséder, puis utiliser la pratique problèmes pour vérifier vos réponses. Ceux-ci ont tous été conçus pour près s'identifier et adhérer à ce vous avez à faire sur l'ensemble des problèmes. Donc, je ne vous encourage à pratiquer cette sur votre propre et utiliser le code de vérifiez vos réponses. Parce que je ne veux passer à hacher tables à un certain moment dans la section. Donc, nous ne pourrions pas passer à travers tout cela. Mais nous ferons aussi bien que nous pouvons maintenant. 

OK. Commençons. Asam, comment pouvons-nous créer un nouveau nœud? 

PUBLIC: Vous n'avez struct *. 

JASON HIRSCHHORN: Donc, nous avoir que ici. Oh, désolé. Vous disiez struct *. 

PUBLIC: Et puis [? genre?] nœud ou un nœud de c. 

JASON HIRSCHHORN: OK. Je vais l'appeler new_node afin que nous puissions rester cohérent. 

PUBLIC: Et vous voulez définir ce que à la tête, le premier noeud. 

JASON HIRSCHHORN: OK. Alors maintenant, ce pointage à - si ce n'a pas encore créé un nouveau nœud. Ceci est juste pointe vers le premier noeud dans la liste. Comment puis-je créer un nouveau nœud? Si j'ai besoin d'espace pour créer un nouveau nœud. Malloc. Et comment grand? 

PUBLIC: La taille de la structure. 

JASON HIRSCHHORN: L' taille de la structure. Et quelle est la structure appelée? 

PUBLIC: Noeud? 

JASON HIRSCHHORN: Node. Donc malloc (sizeof (noeud)); nous donne l'espace. Et cette ligne - une chose est incorrecte sur cette ligne. Est new_node un pointeur vers une structure? C'est un nom générique. Qu'est ce que c'est - noeud, exactement. C'est un noeud *. Et que faisons-nous tout de suite après nous malloc quelque chose, Asan? Quelle est la première chose que nous faisons? Et si ça ne marche pas? 

PUBLIC: Oh, vérifier si elle des points au noeud? 

JASON HIRSCHHORN: Exactement. Donc, si vous new_node égaux égaux null, que faisons-nous? Cela renvoie un bool, cette fonction. Exactement. On dirait bien. Quelque chose à ajouter? Nous allons ajouter des choses à la fin. Mais que regarde jusqu'ici bon. Créer pointeurs actuels et antérieurs. Michael, comment puis-je faire cela? 

PUBLIC: Vous auriez faire un noeud *. Vous auriez à faire un pas pour new_node mais pour l' noeuds nous ont déjà. 

JASON HIRSCHHORN: OK. Ainsi, le nœud actuel nous sommes sur. Je vais appeler que Curr. Très bien. Nous avons décidé que nous voulons garder deux, parce que nous devons savoir ce qui est devant lui. Que font-ils initialisés à? 

PUBLIC: Leur valeur dans notre liste. 

JASON HIRSCHHORN: Alors, quelle est la première chose sur notre liste? Ou comment savons-nous où l' à partir de notre liste est? 

PUBLIC: N'est-il pas passé dans la fonction? 

JASON HIRSCHHORN: Droit. Elle a été adoptée en droit ici. Donc, si il est passé à la fonction, la début de la liste, ce qui devrait nous définir courant égal à? 

PUBLIC: Liste. 

JASON HIRSCHHORN: Liste. C'est exactement ça. Maintenant, il a l'adresse de le début de notre liste. Et que dire précédente? 

PUBLIC: Liste moins un? 

JASON HIRSCHHORN: Il ya rien devant elle. Alors, que pouvons-nous faire pour rien signifier? 

PUBLIC: Null. 

JASON HIRSCHHORN: Ouais. Cela sonne comme une bonne idée. Parfait. Merci. Parcourez la liste. Constantine, combien de temps allons-nous de passer par la liste? 

PUBLIC: jusqu'à arriver nulle. 

JASON HIRSCHHORN: OK. Donc, si, tandis que, pour la boucle. Que faisons-nous? 

PUBLIC: Peut-être une boucle? 

JASON HIRSCHHORN: Faisons une boucle for. OK. 

PUBLIC: Et nous disons pour - jusqu'à ce que le pointeur courant n'est pas égal à zéro. 

JASON HIRSCHHORN: Donc, si nous savons l' état, comment pouvons-nous écrire une boucle sur la base de cette condition. Quel genre de boucle devrions-nous utiliser? 

PUBLIC: Bien. 

JASON HIRSCHHORN: Ouais. Cela fait plus de sens en fonction hors de ce que vous dites. Si nous voulons juste aller en nous, il serait il suffit de savoir que cette chose, il serait sens de faire une boucle while. Alors que le courant n'est pas égal à zéro, si la valeur est inférieure à ce noeud. Akshar, donne-moi cette ligne. 

PUBLIC: Si le courant-> n n moins de valeur. Ou renverser cette tendance. Mettez cette tranche. 

JASON HIRSCHHORN: Désolé. 

PUBLIC: Changer le support. 

JASON HIRSCHHORN: Donc, si c'est supérieure à la valeur. Parce que c'est la confusion avec la commentaire ci-dessus, je vais le faire. Mais oui. Si notre valeur est inférieure à cette noeud, que faisons-nous? Oh. Je l'ai juste ici. Insérer avant. OK. Comment faisons-nous cela? 

PUBLIC: Est-il encore de moi? 

JASON HIRSCHHORN: Ouais. 

PUBLIC: Vous - new_node-> next. 

JASON HIRSCHHORN: Alors, quel est qui va égaler? 

PUBLIC: Il va courant égal. 

JASON HIRSCHHORN: Exactement. Et si l'autre - quoi d'autre avons-nous besoin de mettre à jour? 

PUBLIC: Vérifier si le passé est égal à zéro. 

JASON HIRSCHHORN: Si prev - si prev égal nulle. 

PUBLIC: Cela signifie qu'il va pour devenir le chef. 

JASON HIRSCHHORN: Cela signifie que il est devenu la tête. Alors que faisons-nous? 

PUBLIC: Nous faisons face est de new_node. 

JASON HIRSCHHORN: Head égaux new_node. Et pourquoi la tête ici, pas la liste? 

PUBLIC: Parce que la tête est une entreprise mondiale variable, qui est le lieu de départ. 

JASON HIRSCHHORN: Sweet. OK. Et - 

PUBLIC: Ensuite, vous n'avez d'autre prev-> égale prochaine new_node. Et puis vous revenez vrai. 

JASON HIRSCHHORN: Où faire nous avons mis fin à new_node? 

PUBLIC: Je voudrais - J'ai mis qu'au début. 

JASON HIRSCHHORN: Alors quelle ligne? 

PUBLIC: Après l'instruction if vérifier si elle est connue. 

JASON HIRSCHHORN: Juste ici? 

PUBLIC: je ferais new_node-> n est égale valeur. 

JASON HIRSCHHORN: Ça sonne bien. Probablement il est logique - nous ne faisons pas besoin de savoir ce que nous sommes sur la liste parce que nous ne traitons avec une seule liste. Donc une meilleure déclaration de fonction pour c'est juste pour se débarrasser de cette entièrement et il suffit d'insérer une valeur dans la tête. Nous n'avons même pas besoin de savoir quelle liste nous sommes po Mais je vais le garder pour le moment et puis changer à la mise à jour les diapositives et le code. Alors qu'il est bon pour le moment. Si la valeur - qui peut le faire en ligne? Si - que faisons-nous ici, Noah. 

PUBLIC: Si la valeur est supérieure que curr-> n - 

JASON HIRSCHHORN: Comment faire nous allons vers le noeud suivant? 

PUBLIC: Curr-> n est égal à new_node. 

JASON HIRSCHHORN: Donc n est quelle partie de la structure? L'entier. Et new_node est un pointeur sur un noeud. Alors quelle partie de Curr devrions nous mettre à jour? Si ce n'est pas n, alors quel est l'autre partie? Noé, ce qui est l'autre partie. 

PUBLIC: Oh, la prochaine. 

JASON HIRSCHHORN: Ensuite, exactement. Exactement. Suivant est la bonne. Et quoi d'autre avons-nous besoin de mettre à jour, Noah? 

PUBLIC: Les pointeurs. 

JASON HIRSCHHORN: Donc, nous courant mis à jour. 

PUBLIC: Précédent-> next. 

JASON HIRSCHHORN: Ouais. OK, nous ferons une pause. Qui peut nous aider ici? Manu, que devons-nous faire? 

PUBLIC: Vous avez à définir il égale à curr-> suivant. Mais le faire avant la ligne précédente. 

JASON HIRSCHHORN: OK. Autre chose? Akshar. 

PUBLIC: Je ne pense pas que vous êtes destiné à changer curr-> suivant. Je pense que vous êtes censé faire égaux curr curr-> next pour aller au noeud suivant. 

JASON HIRSCHHORN: Donc désolé, où? Sur quelle ligne? Cette ligne? 

PUBLIC: Ouais. Assurez-Curr égale curr-> suivant. 

JASON HIRSCHHORN: C'est correct parce que le courant est un pointeur vers un noeud. Et nous voulons qu'il pointe vers la prochaine nœud de ce qui se actuellement souligné. Curr lui-même a un côté. Mais si nous devions mettre à jour curr.next, nous serait mise à jour de la note réelle lui-même, pas où ce pointeur pointait. Qu'en est-il de cette ligne, si. Avi? 

PUBLIC: Précédent-> égaux prochaine Curr. 

JASON HIRSCHHORN: Encore une fois, si prev est un pointeur vers un noeud, prev-> se trouve à côté de la réelle pointeur dans le noeud. Donc, ce serait une mise à jour pointeur dans un noeud à Curr. Nous ne voulons pas de mettre à jour un pointeur dans un noeud. Nous voulons mettre à jour précédente. Alors, comment faisons-nous cela? 

PUBLIC: Il serait juste préc. 

JASON HIRSCHHORN: Droit. Précédent est un pointeur vers un noeud. Maintenant, nous sommes changeant à un nouveau pointeur vers un noeud. OK Passons bas. Enfin, cette dernière condition. Jeff, que faisons-nous ici? 

PUBLIC: Si la valeur est égal à curr-> n. 

JASON HIRSCHHORN: Désolé. Oh mon Dieu. Qu'est-ce? Valeur == curr-> n. Que faisons-nous? 

PUBLIC: Vous souhaitez libérer notre new_node, et alors vous revenez faux. 

JASON HIRSCHHORN: C'est ce que nous avons écrit jusqu'ici. Quelqu'un at-il quoi que ce soit à ajouter avant que nous fassions? OK. Essayons. Le contrôle peut arriver à la fin d'une fonction non-nulle. Avi, ce qui se passe? 

PUBLIC: Êtes-vous censé mettre retour vrai à l'extérieur de la boucle while? 

JASON HIRSCHHORN: Je ne sais pas. Vous me voulez? 

PUBLIC: Peu importe. Non. 

JASON HIRSCHHORN: Akshar? 

PUBLIC: Je pense que vous vouliez mettre retour faux à la fin de la boucle while. 

JASON HIRSCHHORN: Alors, où voulez-vous aller? 

PUBLIC: Comme l'extérieur de la boucle while. Donc, si vous quittez la boucle while que des moyens que vous avez atteint la fin et ne s'est rien passé. 

JASON HIRSCHHORN: OK. Alors, que faisons-nous ici? 

PUBLIC: Vous revenez faux là aussi. 

JASON HIRSCHHORN: Oh, nous faire dans les deux endroits? 

PUBLIC: Ouais. 

JASON HIRSCHHORN: OK. Faut-il aller? Oh mon Dieu. Je suis désolé. Je m'excuse pour l'écran. C'est une sorte de flipper sur nous. Alors, choisissez une option. Zéro, par le code, quitte le programme. On insère quelque chose. Insérons trois. L'insert a échoué. Je vais imprimer. Je n'ai rien. OK. Peut-être que c'était juste un coup de chance. Insérez un. Pas réussi. OK. Lançons par GDB très rapidement de vérifier ce qui se passe. 

Rappelez-vous gdb. / Le nom de votre programme nous met dans GDB. Est-ce beaucoup à gérer? Le clignotant? Probablement. Fermez vos yeux et prendre un peu de profondeur respirations si vous êtes fatigués de voir les choses. Je suis dans GDB. Quelle est la première chose que je fais dans GDB? Nous devons comprendre ce qui se passe ici. Voyons. Nous avons six minutes pour comprendre ce qui se passe. Cassez principale. Et puis ce que je fais? Carlos? Exécutez. OK. Choisissons une option. Et ce ne N faire? Suivant. Ouais. 

PUBLIC: Vous n'avez pas mentionné - vous n'avez pas dit que la tête, il était initialisée à null au début. Mais je pensais que vous avez dit que c'était OK. 

JASON HIRSCHHORN: Allons - regardons dans GDB, et puis nous allons revenir. Mais il semble que vous avez déjà quelques idées sur ce qui se passe. Donc, nous voulons insérer quelque chose. OK. Nous avons insérer. S'il vous plaît entrer un entier. Nous allons insérer trois. Et puis je suis sur cette ligne. Comment puis-je démarrer le débogage l'insert fonction connue? Oh mon Dieu. C'est beaucoup. Est-ce que paniquer beaucoup? 

PUBLIC: Oh, il est mort. 

JASON HIRSCHHORN: Je ai sorti. OK. 

PUBLIC: C'est peut-être la l'autre extrémité du fil. 

JASON HIRSCHHORN: Wow. Ainsi, la ligne de fond - qu'avez-vous dit? 

PUBLIC: je l'ai dit l'ironie de la technique difficultés dans cette classe. 

JASON HIRSCHHORN: Je sais. Si seulement j'avais le contrôle de la partie. [Inaudible] Cela sonne bien. Pourquoi avez-vous les gars commencent pas à penser à ce que nous aurions pu faire de mal, et nous serons de retour en 90 secondes. 

Avica, je vais vous demander comment aller insert_node intérieur pour déboguer. C'est donc là que nous nous sommes quittés. Comment dois-je aller à l'intérieur insert_node, Avica, d'examiner ce qui se passe? Quelle commande GDB? Pause ne me prendrait pas à l'intérieur. Ne marquise sait? 

PUBLIC: Quoi? 

JASON HIRSCHHORN: Quelle commande GDB Que j'utilise pour aller à l'intérieur de cette fonction? 

PUBLIC: étape? 

JASON HIRSCHHORN: étape par S. Cela me prend à l'intérieur. OK. New_node allouer de l'espace. C'est tout ressemble à sa va. Examinons new_node. Il a obtenu une adresse mémoire. Voyons - c'est tout bon. Donc, tout ici semble travailler correctement. 

PUBLIC: Quelle est la différence entre P et l'affichage? 

JASON HIRSCHHORN: P pour imprimer. Et si vous vous demandez quelle est la différence entre cela et ce? Dans ce cas, rien. Mais en général, il ya certaines différences. Et vous devriez regarder dans le manuel GDB. Mais dans ce cas, rien. Nous avons tendance à utiliser l'impression, cependant, parce que nous n'avons pas besoin de faire beaucoup plus que imprimer une seule valeur. 

OK. Donc, nous sommes sur la ligne 80 de notre code, mettant le noeud * curr égale à la liste. Laissez-nous imprimons Curr. Elle est égale à la liste. Sweet. Attendez. Elle est égale à quelque chose. Cela ne semble pas juste. Nous y voilà. C'est parce que dans GDB, à droite, si c'est la ligne que vous êtes dessus n'a pas encore exécuté. Donc, vous devez taper effectivement prochaine pour exécuter la ligne avant de voir ses résultats. Donc nous sommes ici. Nous venons exécuté cette ligne, précédente est égal à zéro. Encore une fois, si nous imprimons précédente nous ne verrons pas quelque chose de bizarre. Mais si nous exécutons fait que ligne, puis nous verrons que cette ligne a travaillé. 

Nous avons donc Curr. Ce sont deux très bons. Droite? Maintenant, nous sommes sur cette ligne ici. Alors que curr n'est pas égal à zéro. Eh bien, qu'est-ce que curr égal? Nous venons de voir qu'il a égalé nulle. Nous avons imprimé le. Je vais l'imprimer à nouveau. Alors est ce que la boucle while va exécuter? 

PUBLIC: Non 

JASON HIRSCHHORN: Alors, quand j'ai tapé que ligne, vous voyez, nous avons sauté tout le chemin vers le bas, retourner false. Et puis nous allons revenir faux et revenir à notre programme et éventuellement imprimer, comme nous l'avons vu, l'insert n'a pas réussi. Donc, quelqu'un a des idées sur ce que nous devons faire pour résoudre ce problème? Je vais attendre jusqu'à ce que je vois un couple de mains se lèvent. Nous n'avons pas exécuter cette. Gardez à l'esprit, c'était la première chose que nous faisions. Je ne vais pas faire un couple. Je vais faire un peu. Parce que un couple deux moyens. Je vais attendre plus de deux. 

La première insertion, Curr, par défaut est égale à zéro. Et cette boucle ne s'exécute que si curr n'est pas nulle. Alors, comment puis-je contourner ce? Je vois trois mains. Je vais attendre plus de trois. Marcus, que pensez-vous? 

PUBLIC: Eh bien, si vous en avez besoin exécuter plus d'une fois, vous venez changer pour une boucle do-while. 

JASON HIRSCHHORN: OK. Est-ce que résoudre notre problème, si? 

PUBLIC: Dans ce cas, aucune raison de le fait que la liste est vide. Alors vous avez probablement juste besoin d'ajouter une déclaration que si la boucle s'arrête alors vous devez être à la fin de la liste, à laquelle vous pointez peut simplement insérer. 

JASON HIRSCHHORN: j'aime ça. C'est logique. Si la boucle sort - parce que ça va revenir faux ici. Donc, si la boucle s'arrête, alors nous sommes à la fin de la liste, ou peut-être l' le début d'une liste si il n'y a rien dans , ce qui est la même que la fin. Alors maintenant, nous voulons insérer quelque chose ici. Alors, comment est-ce que le code regardez, Marcus? 

AUDIENCE: Si vous avez déjà eu le nœud malloced, vous pouvez simplement dire new_node-> égaux prochain nulle car il doit être à la fin. Ou new_node-> égale prochain nulle. 

JASON HIRSCHHORN: OK. Désolé. New_node-> égaux prochaine null parce que nous sommes à la fin. Cela ne met pas po Comment pouvons-nous mettre dans la liste? Droite. C'est juste le mettre à égalité. Non, comment pouvons-nous réellement mettre dans la liste? Qu'est-ce qui pointant vers le fin de la liste? 

PUBLIC: Head. 

JASON HIRSCHHORN: Désolé? 

PUBLIC: Chef pointe à la fin de la liste. 

JASON HIRSCHHORN: S'il n'y a rien dans la liste, la tête est orientée vers la fin de la liste. Alors qui va travailler pour la la première insertion. Qu'en est-il si il ya un couple choses dans la liste? Que nous ne voulons pas mettre en diriger égale à new_node. Que voulons-nous y faire? Ouais? Probablement précédente. Est-ce que travailler? Rappelons que précédente est juste un pointeur vers un noeud. Et précédente est une variable locale. Donc, cette ligne sera de définir une variable locale, précédente, égale ou pointant vers ce nouveau nœud. Ce ne sera pas fait mettre dans notre liste, si. Comment pouvons-nous mettre dans notre liste? Akchar? 

PUBLIC: Je pense que vous faire current-> suivant. 

JASON HIRSCHHORN: OK. curr-> suivant. Encore une fois, la seule raison pour laquelle nous en sommes ici, c'est ce que fait courant égal? 

PUBLIC: Equals nulle. 

JASON HIRSCHHORN: Et qu'est-ce qui se passe si nous faisons null-> next? Qu'est-ce qu'on va faire? Nous aurons une erreur de segmentation. 

PUBLIC: Do curr vaut NULL. 

JASON HIRSCHHORN: C'est la même chose comme précédent, cependant, car il ya une variable locale, nous mettons en place égal à ce nouveau noeud. Revenons à notre image l'insertion de quelque chose. Disons que nous sommes l'insertion à la fin de la liste, de sorte ici. Nous avons un pointeur courant qui est pointant à null et un point précédent C'est pointant à 8. Alors que devons-nous pour mettre à jour, Avi? 

PUBLIC: Précédent-> next? 

JASON HIRSCHHORN: Précédent-> est ce que la prochaine nous voulons mettre à jour parce que seront effectivement insérer à la fin de la liste. Nous avons encore un bug, si, que nous allons rencontrer. Quel est ce bug? Ouais? 

PUBLIC: Il va revenir faux dans ce cas? 

JASON HIRSCHHORN: Oh, est est va retourner false. Mais il ya un autre bug. Nous devons donc mettre en return true. 

PUBLIC: Ne précédente toujours à égalité nulle en haut de la liste? 

JASON HIRSCHHORN: encore Donc précédente est égal à zéro au début. Alors, comment pouvons-nous obtenir plus de cela? Ouais? 

PUBLIC: Je pense que vous pouvez faire un chèque avant la boucle while pour voir si c'est une liste vide. 

JASON HIRSCHHORN: OK. Allons donc ici. Faites une vérification. Si - 

PUBLIC: Donc, si la tête est égal à égal nulle. 

JASON HIRSCHHORN: Si la tête est égal à égal nulle - qui nous dira si c'est une liste vide. 

PUBLIC: Et puis vous faire face est de nouveau. 

JASON HIRSCHHORN: Head égaux new_node? Et quoi d'autre avons-nous besoin de le faire? 

PUBLIC: Et puis vous revenez vrai. 

JASON HIRSCHHORN: Pas tout à fait. Il nous manque une étape. 

PUBLIC: New_node prochaine doit indiquer la valeur null. 

JASON HIRSCHHORN: Exactement, Alden. Et puis nous pouvons retourner true. OK. Mais c'est toujours une bonne idée de faire des choses à la fin de la liste, non? Très bien. Nous pourrions encore réellement obtenir à la fin de la liste. Alors est ce code bien si nous sommes à la fin de la liste et il ya quelques choses dans la liste? Droite? Parce que nous avons toujours l'idée de Marcus. Nous pourrions sortir de cette boucle, car nous sommes à la fin de la liste. Ainsi voulons-nous toujours ce coder ici? 

PUBLIC: Oui. 

JASON HIRSCHHORN: Ouais. Et que devons-nous changer cela? Vrai. Est-ce que bon son à tout le monde à ce jour? Quelqu'un a une - Avi, avez-vous quelque chose à ajouter? 

PUBLIC: Non 

JASON HIRSCHHORN: OK. Nous avons donc fait quelques changements. Nous avons fait cette vérification avant est allé dans une liste vide. Donc, nous avons pris soin d'une liste vide. Et ici nous avons pris soin d'insérer quelque chose à la fin de la liste. Il semble donc que cette prise de boucle while soin des choses entre les deux, quelque part dans la liste si ya des choses dans la liste. 

OK. Courons de nouveau ce programme. Pas réussi. 

PUBLIC: Vous n'avez pas faites. 

JASON HIRSCHHORN: Oh, Je n'ai pas réussi. Bon point, Michael. Ajoutons une marque liée. Ligne 87 il ya une erreur. Ligne 87. Alden, c'est la ligne que vous m'avez donné. Quel est le problème? 

PUBLIC: Il doit être à null. 

JASON HIRSCHHORN: Excellent. Exactement. Il devrait être nulle. Faisons à nouveau. Compiler. OK. Insérons trois. L'insert a été réussie. Disons imprimer. Oh, si seulement nous pouvions vérifier. Mais nous n'avons pas fait la imprimer encore la fonction. Entrons autre chose. Que devons-nous conclure? 

PUBLIC: Seven. 

JASON HIRSCHHORN: Seven? 

PUBLIC: Oui. 

JASON HIRSCHHORN: Nous avons une erreur de segmentation. Donc, nous avons eu un, mais nous avons clairement ne peut pas avoir deux. Il est 05h07. Donc, nous pourrions déboguer ce pendant trois minutes. Mais je vais nous laisser ici et de passer aux différentes tables. Mais encore une fois, les réponses à ce code Je vais te l'envoyer dans un peu. Nous sommes très près de lui. Je vous encourage fortement à comprendre ce qui se passe ici et de le corriger. Donc, je vais vous envoyer ce code bien plus de la solution - probablement la solution par la suite. Première ce code. 

L'autre chose que je veux faire avant de nous finition est que nous n'avons pas libéré rien. Je tiens donc à vous montrer ce que valgrind ressemble. Si nous courons limites de valgrind sur notre programme. / lié. Encore une fois, selon cette diapositive, nous devrait fonctionner valgrind avec un certain type de possibilité, dans ce cas, - Fuite chèque = plein. Donc, nous allons écrire valgrind - Fuite chèque = plein. Donc, ce sera exécuter valgrind sur notre programme. Et maintenant, le programme fonctionne réellement. Donc, nous allons le faire fonctionner comme avant, mettre quelque chose po Je vais mettre trois. Cela fonctionne. Je ne vais pas essayer de mettre quelque chose d'autre parce que nous allons obtenir un faux segment dans ce cas. Donc, je vais juste arrêter de fumer. 

Et maintenant vous voyez ici fuir et résumé du tas. Ce sont les bonnes choses que vous voulez vérifier. Ainsi, le résumé de tas - il dit, en utilisation à la sortie - huit octets dans un bloc. C'est un bloc est l' nœud nous malloced. Michael, vous avez dit avant un nœud est de huit morsures, car il a l'entier et le pointeur. C'est donc notre nœud. Et puis il dit que nous avons utilisé malloc sept fois et nous avons libéré quelque chose de six fois. Mais nous n'avons jamais dit libre, donc je n'ai pas idée de ce que parle. 

Mais il suffit de dire que lorsque votre programme s'exécute, malloc est appelé dans d'autres endroits que nous n'ont pas besoin de s'inquiéter. Donc malloc a probablement été appelé dans certains endroits. Nous n'avons pas besoin de s'inquiéter où. Mais c'est vraiment nous. Cette première ligne, c'est nous. Nous avons quitté ce bloc. Et vous pouvez voir que ici dans le résumé de fuite. Toujours accessible - huit octets dans un bloc. Cela signifie que la mémoire - nous avons fui cette mémoire. Définitivement perdu - quelque chose est perdu pour de bon. En général, vous ne serez pas voir du tout. Toujours est généralement accessible où vous voyez les choses, où vous voulez à regarder pour voir ce code devrait ont libéré mais vous avez oublié de libérer. 

Et puis, si ce n'était pas le cas, si nous avons fait tout gratuit, nous pouvons vérifier cela. Disons simplement exécuter le programme ne pas mettre en quoi que ce soit. Vous verrez ici en usage à la sortie - de zéro octets blocs nuls. Cela signifie que nous n'avions plus rien lorsque ce programme est sorti. Donc, avant de tourner dans pset6, valgrind exécuter et assurez-vous que vous n'avez pas tout fuites de mémoire dans votre programme. Si vous avez des questions valgrind, n'hésitez pas à atteindre. Mais c'est la façon dont vous l'utilisez. Très simple - voir si vous ont utilisé à la sortie - les octets de tous les blocs. 

Donc, nous avons travaillé sur le noeud d'insertion. J'ai eu deux autres fonctions ici - imprimer noeuds et noeuds libres. Là encore, ce sont des fonctions qui sont va être bon pour vous de pratiquer car ils vous aideront non seulement avec ces exemples d'exercices, mais aussi sur le problème posé. Ils carte sur d'assez près aux choses vous allez avoir à faire dans le problème réglé. Mais je ne veux m'assurer nous touchons à tout. Et les tables de hachage sont également cruciales pour ce que nous faisons dans la section de ce semaines - ou dans le jeu de problème. 

Donc, nous allons terminer la section parler de tables de hachage. Si vous remarquez, j'ai fait une petite table de hachage. Ce n'est pas ce dont nous parlons sur, cependant. Nous parlons d'un autre type de tables de hachage. Et à sa base, une table de hachage n'est rien de plus qu'un tableau plus une fonction de hachage. Nous allons parler un peu juste assurez-vous que tout le monde comprend ce qu'est un fonction de hachage est. Et je vous dis maintenant qu'il est rien de plus que deux choses - une matrice et une fonction de hachage. Et voici les étapes à ce qui fonctionne. 

Voilà notre tableau. Il ya notre fonction. En particulier, les fonctions de hachage doivent faire une ou deux choses à ce sujet. Je vais parler spécifiquement sur ce problème réglé. Il va probablement prendre dans une chaîne. Et qu'est-ce que ça va revenir? Quel type de données? Alden? Votre fonction de hachage revenir? Un entier. Donc, c'est ce que le hachage table se compose de - une table sous forme de tableau et une fonction de hachage. Comment ça marche? Il fonctionne en trois étapes. Nous lui donnons une clé. Dans ce cas, nous lui donnons une chaîne. Nous appelons la fonction de hachage pour la première étape sur la touche et nous obtenons une valeur. 

Plus précisément, nous dirons nous obtenons un nombre entier. Cela entier, il ya très spécifique des limites à ce que peut être entier. Dans cet exemple, notre matrice est de taille trois. Donc, ce nombre peut être entier que. Quelle est la plage de valeurs valides pour ce nombre entier, le type de ce retour fonction de hachage? Zéro, un et deux. Le point de la fonction de hachage est de comprendre la place dans le tableau où notre clé va. Il n'y a que trois possibilités endroits ici - zéro, un ou deux. Donc, cette fonction meilleur rendement zéro, un ou deux. Certains indice valable dans ce tableau. 

Et puis en fonction de l'endroit où il retourne, vous pouvez y voir tableau ouvert entourer la valeur. C'est là que nous avons mis sur la touche. Alors que nous jetons dans la citrouille, nous sortons zéro. Au tableau support 0, nous avons mis la citrouille. Nous jetons les chats, nous sortons un. Nous mettons chat à un. Nous avons mis en araignée. Nous sortons deux. Nous mettons araignée au tableau support deux. Ce serait tellement bien si il a travaillé comme ça. Mais malheureusement, comme nous le verrons, c'est un peu plus compliqué. 

Avant d'y arriver, des questions de cette base mise en place d'une table de hachage? C'est une image d'exactement ce qui nous nous sommes inspirés du conseil. Mais puisque nous avons tiré sur le bord, je je ne vais pas aller dans davantage. Essentiellement touches, la boîte noire magique - ou dans ce cas, la boîte de sarcelle d'hiver - d'un fonction de hachage les met dans des seaux. Et dans cet exemple, nous sommes ne pas mettre le nom. Nous mettons le téléphone associé nombre de son nom dans le seau. Mais vous pourriez très bien juste mettre le nom dans le seau. 

C'est juste une image de ce nous avons dessiné sur la carte. Nous avons pièges potentiels, cependant. Et il ya deux en particulier diapositives que je veux y aller. La première est d'environ une fonction de hachage. J'ai donc posé la question, ce qui fait une bonne fonction de hachage? Je donne deux réponses. La première, c'est qu'il est déterministe. Dans le cadre de fonctions de hachage, qu'est-ce que cela signifie? Oui? 

PUBLIC: On peut trouver le indice en temps constant? 

JASON HIRSCHHORN: C'est n'est pas ce que cela signifie. Mais c'est une bonne proposition. Quelqu'un d'autre a une proposition ce que cela signifie? C'est une bonne fonction de hachage est déterministe? Annie? 

PUBLIC: C'est une clé ne peut être mappé à un seul endroit dans la table de hachage. 

JASON HIRSCHHORN: C'est tout à fait exact. Chaque fois que vous mettez dans la citrouille, elle retourne toujours zéro. Si vous mettez dans votre citrouille et hachage la fonction renvoie zéro mais a une probabilité de retourner quelque chose d'autre supérieur à zéro - alors peut-être il peut renvoyer l'un, parfois ou deux autres fois - ce n'est pas une bonne fonction de hachage. Vous avez parfaitement raison. Votre fonction de hachage doit retourner le même nombre entier exact, dans ce cas, pour la même chaîne exacte. 

Peut-être que renvoie le même nombre entier exact pour la même chaîne exacte indépendamment de la capitalisation. Mais dans ce cas, il est encore déterministe car plusieurs choses sont mappés sur la même valeur. C'est très bien. Tant qu'il n'y a qu'un seul sortie pour une entrée donnée. 

OK. La deuxième chose est qu'il retourne indices valides. Nous avons apporté jusqu'à l'heure. Cette fonction de hachage - oh boy - une fonction de hachage devrait retourner indices valides. Donc dire - Revenons à notre exemple. Ma fonction de hachage compte jusqu'à les lettres du mot. C'est la fonction de hachage. Et renvoie cet entier. Donc, si j'ai le mot A, il est va revenir un. Et il va mettre un ici. Qu'est-ce que si je mets le mot chauve-souris? Il va revenir trois. Où aller chauve-souris? 

Il ne convient pas. Mais il a besoin d'aller quelque part. C'est ma table de hachage après tout, et tout doit aller quelque part. Alors, où devrait aller chauve-souris? Des pensées? Devine? Bonnes suppositions? 

PUBLIC: zéro. 

JASON HIRSCHHORN: Pourquoi zéro? 

PUBLIC: Parce que trois modulo trois est égal à zéro? 

JASON HIRSCHHORN: Trois modulo trois est égal à zéro. C'est une grande proposition, et c'est exact. Donc, dans ce cas, il devrait probablement aller à zéro. Donc, une bonne façon de s'assurer que ce hachage fonction ne retourne indices valides est modulo par la taille de la table. Si vous modulo quel que soit ce rendement par trois, vous allez toujours obtenir quelque chose entre zéro, un, et deux. Et si cela retourne toujours sept, et vous avez toujours modulo par trois, vous êtes allant toujours à obtenir la même chose. 

Donc, il est toujours déterministe si vous modulo. Mais cela ne vous assurer que vous jamais obtenir quelque chose - un secteur valide. En règle générale, qui doit se faire modulo l'intérieur de votre fonction de hachage. Donc, vous n'avez pas besoin de s'inquiéter à ce sujet. Vous ne pouvez faire en sorte que il s'agit d'un indice valable. Toutes les questions sur ce écueil? 

OK. Et là nous allons. Suivant potentiel écueil, et c'est le grand. Que faire si deux touches carte à la même valeur? Donc, il ya deux façons de gérer cela. Le premier est appelé linéaire sondage, qui je suis ne vais pas y aller. Mais vous devez être familier avec la façon qui fonctionne et ce que c'est. 

La seconde, je vais aller sur parce que c'est celui qui a beaucoup les gens vont probablement finir par décider à utiliser dans leur ensemble de problème. Bien sûr, vous n'avez pas à. Mais, pour l'ensemble des problèmes, beaucoup de gens ont tendance à choisir de créer une table de hachage avec chaînage séparé pour mettre en œuvre leur dictionnaire. Donc, nous allons revenir sur ce que cela signifie pour créer une table de hachage avec chaînage séparé. 

Alors, j'ai mis en citrouille. Il renvoie zéro. Et je mets citrouille ici. Puis-je mettre dans - ce qui est une autre chose de Halloween sur le thème? 

PUBLIC: Candy. 

JASON HIRSCHHORN: Candy! C'est un grand. Je mets dans les bonbons, et des bonbons me donne aussi zéro. Que dois-je faire? Des idées? Parce que vous savez toutes sortes de ce chaînage séparé est. Donc, toutes les idées que faire? Ouais. 

PUBLIC: Mettre la chaîne en fait dans la table de hachage. 

JASON HIRSCHHORN: Donc, nous allons attirer la bonne idée ici. OK. 

PUBLIC: Vous avez la table de hachage [Inaudible] le pointeur qui pointe vers le début d'une liste. Et puis ont citrouille être la première valeur dans cette liste, et les bonbons être la deuxième valeur de cette liste chaînée. 

JASON HIRSCHHORN: OK. Marcus, qui était exceptionnel. Je vais faire une ventilation. Marcus dit ne le font pas remplacer la citrouille. Ce serait mauvais. Ne pas mettre des bonbons ailleurs. Nous allons les mettre à la fois à zéro. Mais nous allons faire face à les mettre à zéro par création d'une liste à zéro. Et nous allons créer une liste de tout ce qui mappée à zéro. Et la meilleure façon que nous avons appris à créer une liste qui peut croître et se rétrécir est dynamiquement pas à l'intérieur de un autre tableau. Donc, pas un tableau multi-dimensionnel. Mais il suffit de créer une liste chaînée. 

Donc, ce qu'il a proposé - Je vais me faire un nouveau - est de créer un tableau avec des pointeurs, un tableau de pointeurs. OK. Toute idée ou soupçon que soit le type de cette pointeurs devrait être? Marcus? 

PUBLIC: Les pointeurs vers - 

JASON HIRSCHHORN: Parce que vous dit une liste chaînée, si - 

PUBLIC: pointeurs de noeuds? 

JASON HIRSCHHORN: pointeurs de noeuds. Si les choses dans notre liée liste sont des nœuds, puis ils devraient être des pointeurs de noeuds. Et que font-ils égaux d'abord? 

PUBLIC: Null. 

JASON HIRSCHHORN: Null. Donc, il ya notre truc vide. rendements de citrouille zéro. Que faisons-nous? Me promener à travers elle? En fait, Marcus m'a déjà donné. Quelqu'un d'autre me promener à travers elle. Ce que nous faisons lorsque nous - cela semble très similaire à ce que nous ne faisions. Avi. 

PUBLIC: Je vais faire une supposition. Ainsi, lorsque vous obtenez des bonbons. 

JASON HIRSCHHORN: Ouais. Eh bien, nous avons eu la citrouille. Soyons de notre premier. Nous avons eu la citrouille. 

PUBLIC: OK. rendements de citrouille zéro. Donc, vous le mettez dans cela. Ou fait, vous le mettez dans la liste chaînée. 

JASON HIRSCHHORN: Comment pouvons-nous mettre dans la liste chaînée? 

PUBLIC: Oh, la syntaxe réelle? 

JASON HIRSCHHORN: Il suffit de marcher - dire plus. Que faisons-nous? 

PUBLIC: Il suffit d'insérer comme le premier noeud. 

JASON HIRSCHHORN: OK. Donc, nous avons notre noeud, potiron. Et maintenant, comment puis-je l'insérer? 

PUBLIC: Vous affectez au pointeur. 

JASON HIRSCHHORN: Quels pointeur? 

AUDIENCE: Le pointeur à zéro. 

JASON HIRSCHHORN: Alors, où fait ce point? 

PUBLIC: Pour null dès maintenant. 

JASON HIRSCHHORN: Eh bien, il pointe vers null. Mais je suis en train de la citrouille. Alors, où faut-il signaler? 

PUBLIC: Pour potiron. 

JASON HIRSCHHORN: Pour potiron. Exactement. Donc, cela souligne la citrouille. Et d'où vient ce pointeur au point de citrouille? À 

PUBLIC: Null. 

JASON HIRSCHHORN: Pour null. Exactement. Donc, nous venons d'insérer quelque chose dans la liste chaînée. Nous venons d'écrire le code pour ce faire. Près de nous, il a presque réussi complètement craqué. Maintenant, nous insérons des bonbons. Notre bonbons va également à zéro. Alors, que faisons-nous avec des bonbons? 

PUBLIC: Cela dépend de si oui ou pas que nous essayons de faire le tri. 

JASON HIRSCHHORN: C'est tout à fait exact. Cela dépend de si oui ou non nous essayons de faire le tri. Supposons que nous ne sommes pas va faire le tri. 

PUBLIC: Eh bien, comme nous l'avons avant, le plus simple est juste de le mettre dès le début de sorte que le pointeur de points zéro à bonbons. 

JASON HIRSCHHORN: OK. Attendez. Permettez-moi de créer des bonbons ici. Donc, ce pointeur - 

PUBLIC: Ouais, doit maintenant pointer à bonbons. Avoir le pointeur de Point de potiron de sucrerie. 

JASON HIRSCHHORN: Comme ça? Et dire que nous avons un autre chose à la carte à zéro? 

PUBLIC: Eh bien, vous venez de faire la même chose? 

JASON HIRSCHHORN: Faites la même chose. Donc dans ce cas, si nous ne faisons pas vouloir garder triée il sons assez simple. Nous prenons le pointeur dans la indice donné par notre fonction de hachage. Nous avons ce point à notre nouveau nœud. Et puis tout ce qu'il pointait précédemment - dans ce cas, nul, dans le second cas citrouille - que, quel que soit son pointant vers précédemment, nous ajoutons dans le prochain de notre nouveau noeud. Nous insertion quelque chose au début. En fait, c'est beaucoup plus simple que en essayant de garder la liste triée. Mais encore une fois, la recherche sera plus compliqué ici. Nous aurons toujours à aller jusqu'au bout. 

OK. Une question sur le chaînage séparé? Comment cela fonctionne? S'il vous plaît demandez-leur maintenant. Je veux vraiment vous assurer que vous tous comprendre cela avant, nous nous dirigeons. 

PUBLIC: Pourquoi mettez-vous la citrouille et des bonbons dans la même partie de la table de hachage? 

JASON HIRSCHHORN: Bonne question. Pourquoi avons-nous les mettons dans le même partie de la table de hachage? Eh bien, dans ce cas, notre fonction de hachage retourne zéro pour chacun d'eux. Donc, ils ont besoin d'aller à indice zéro parce que c'est là que nous allons les chercher si jamais nous vouloir les regarder. Encore une fois, avec une approche linéaire sondage nous ne serions pas les mettre tous deux à zéro. Mais dans l'approche de la chaîne séparée, nous allons les mettre à la fois à zéro et puis créer une liste de zéro. 

Et nous ne voulons pas remplacer la citrouille simplement parce que alors nous allons supposons que la citrouille était jamais inséré. Si nous gardons juste une chose dans le emplacement qui serait mauvais. Ensuite, il n'y aurait pas chance de nous jamais - si jamais nous avions un double, puis nous serait tout simplement effacer notre valeur initiale. Voilà pourquoi nous faisons cette démarche. Ou c'est pourquoi nous avons choisi - mais encore une fois, nous a choisi l'approche de chaînage séparé, dont il existe de nombreuses autres approches on pourrait choisir. Est-ce que cela répond à votre question? 

OK. Carlos. Linéaire sondage impliquerait - si nous avons trouvé une collision à zéro, nous regarderait en place prochaine pour voir si elle était ouverte et l'a mis là. Et puis nous sommes dans le prochain sport et voir si c'était ouvert et le mettre là. Donc, nous trouvons la prochaine disponible endroit ouvert et le mettre là. D'autres questions? Ouais, Avi. 

PUBLIC: Comme un suivi à cela, Qu'entendez-vous par spot suivant? Dans la table de hachage ou dans une liste chaînée. 

JASON HIRSCHHORN: Pour linéaire programmation, pas de listes chaînées. Le prochain point sur la table de hachage. 

PUBLIC: OK. Ainsi, la table de hachage serait initialisé à la taille - comme le nombre de chaînes que vous insérez? 

JASON HIRSCHHORN: Vous feriez voulez qu'il soit vraiment grand. Oui. Voici une photo de ce que nous juste a attiré sur la carte. Encore une fois, nous avons une collision ici. à 152. Et vous verrez que nous avons créé une liste chaînée hors de lui. Encore une fois, la table de hachage chaînage séparé approche n'est pas celle que vous prendre les problèmes mis en six, mais est un que beaucoup de les étudiants ont tendance à prendre. Donc, sur cette note, parlons brièvement avant, nous nous dirigeons sur six problème, et puis je vais partager une histoire avec vous. Nous avons trois minutes. 

Problème réglé six. Vous disposez de quatre fonctions - charge, vérifier la taille et le déchargement. Charge - bien, nous y allons plus de charge en ce moment. Nous avons tiré la charge sur le plateau. Et nous avons même commencé à coder un grand nombre de insérer dans une liste chaînée. Donc, la charge n'est pas beaucoup plus que ce que nous venons de faire. 

Arrivée est une fois que vous avez quelque chose chargé. C'est le même processus que cela. Les mêmes deux premières parties où vous jetez quelque chose dans la fonction de hachage et obtenir sa valeur. Mais maintenant, nous ne sommes pas l'insérer. Maintenant, nous sommes à la recherche d'elle. J'ai des exemples de code écrit pour trouver quelque chose dans une liste chaînée. Je vous encourage à pratiquer cela. Mais trouver intuitivement que quelque chose assez similaire à l'insertion de quelque chose. En effet, nous avons établi une image de la recherche quelque chose dans une liste chaînée, déplacer par jusqu'à ce que vous avez à la fin. Et si vous avez obtenu à la fin et ne pouvait pas trouver, alors il n'est pas là. C'est donc chèque, essentiellement. 

Suivant est la taille. Passons taille. Enfin, vous avez décharger. Décharger est celui que nous n'avons pas tiré sur la carte ou encore codé. Mais je vous encourage à essayer coder dans notre échantillon exemple de liste chaînée. Mais décharger intuitivement est similaire à la libre - ou je veux dire, c'est même à vérifier. Sauf pour l'instant à chaque fois que vous allez à travers, vous n'êtes pas simplement de vérifier à voir si vous avez votre valeur il. Mais vous prenez ce nœud et le libérant, essentiellement. C'est ce déchargement vous demande de faire. Tout gratuit vous avez malloced. Donc, vous allez toute la liste nouveau, en passant par l'ensemble hachage table. Cette fois-ci ne vérifie pas pour voir ce qui est là. Juste libérer ce qui est là. 

Et enfin la taille. Taille devrait être mis en œuvre. Si vous ne mettez pas en œuvre la taille - Je vais dire comme ça. Si vous ne mettez pas en œuvre la taille exactement une ligne de code, y compris la déclaration de retour, vous êtes faire la taille correctement. Donc, assurez-vous que le format, pour la conception complète points, vous le faites dans exactement un ligne de code, y compris l'instruction de retour. 

Et ne pas emballer encore, Akchar. Eager Beaver. Je voulais vous dire merci les gars pour venir à l'article. Ayez un Halloween heureux. C'est mon costume. Je vais porter ce jeudi si je vous vois à des heures de bureau. Et si vous êtes curieux de savoir un peu plus fond à ce costume, se sentir n'hésitez pas à consulter la section 2011 pour un article sur pourquoi je suis portant le costume de citrouille. Et c'est une histoire triste. Donc, assurez-vous que vous avez certains tissus voisins. Mais sur ce point, si vous avez une questions que je vais rester l'extérieur, après l'article. Bonne chance problème réglé six. Et comme toujours, si vous avez une questions, laissez-moi savoir.