DAVID J. Malan: Très bien. Alors, bienvenue à la première CS50 post-mortem pour un quiz. Nous avons pensé que nous inaugurons cette tradition cette année. Et ce sera l'occasion de marcher à travers la solutions au quiz. Et nous allons accélérer ou ralentir en fonction sur les intérêts de ceux qui sont ici. 

Alors vous êtes probablement ici parce que vous êtes intéressé par la façon dont vous pourriez avoir ou aurait répondu à certaines de ces problèmes. Alors, pourquoi ne pas prendre un coup d'oeil à cette section en premier? Donc obtenir cordes. Cela vous a donné trois versions différentes d'un programme qui a été, en fin de compte, destiné à obtenir une chaîne d'un utilisateur. Qu'il soit ou non fait que était gauche à vous de déterminer. 

Et nous avons demandé à la question 0, supposons que la version 1 est compilé et exécuté. Pourquoi le programme pourrait erreur de segmentation? À première vue, toutes les suggestions pourquoi? Ouais. 

PUBLIC: Je me souviens avoir vu cela dans un exemple précédent de la recherche à la char * s et voir l'analyse des s et voir parce que c'est un pointeur, comment at-il affecté ce que vous numérisez en? Est-il s ou l'adresse de s? 

DAVID J. Malan: OK. Bon. En fin de compte, la source de tout problème est sans doute va réduire à cette variable s. Et c'est en effet une variable. Le type de variable de données qui est char *, ce qui signifie qu'il va contenir l'adresse d'un caractère. Et c'est là que réside l'intuition. Il va contenir l'adresse de un caractère ou, plus généralement, la l'adresse du premier caractère à ensemble un bloc de caractères. 

Mais le hic, c'est que l analyse, le but dans vie, est donnée une adresse donnée et un code de format, comme% s, lecture une chaîne dans la partie de la mémoire à cette adresse. Mais parce qu'il n'y a pas de signe égal avant que sur le premier point-virgule ligne de code, parce que nous n'avons pas fait allouer une mémoire avec malloc, parce qu'il n'a pas fait allouer un tableau d'une certaine taille, tout que vous faites est la lecture à l'utilisateur de saisie au clavier dans une certaine complet valeur des ordures, qui est en s par défaut. Donc chances sont que vous allez erreur de segmentation si cette adresse n'a pas tellement se être une valeur que vous pouvez, en fait, écrire. Si mal de ne pas attribuer votre mémoire il. 

Donc, à la question 1, nous avons demandé, supposons que la version 2 est compilé et exécuté. Pourquoi ce programme pourrait erreur de segmentation? Alors celui-ci est moins buggé. Et il n'y a vraiment qu'une seule façon évidente où vous pouvez déclencher une erreur de segmentation ici. Et c'est thématique. Chaque fois que nous utilisons c dans la mémoire, ce qui pourriez-vous faire pour induire une erreur de segmentation avec la version 2? 

AUDIENCE: Si vous utilisez cette entrée en une chaîne qui est plus long que 49 caractères. 

DAVID J. Malan: Exactement. Chaque fois que vous voyez quelque chose de longueur fixe quand il s'agit d'un tableau, votre radar doit s'éteindre que cela pourrait être problématique si vous n'êtes pas la vérification de la limites d'un tableau. Et c'est ça le problème ici. Nous sommes encore en utilisant scanf. Nous sommes encore en utilisant% s, ce qui signifie essayer pour lire une chaîne de l'utilisateur. Cela va être lu dans s, qui, à ce stade, est effectivement l' adresse d'un bloc de mémoire ou son équivalent. C'est le nom d'un tableau des caractères de la mémoire. 

Mais c'est exactement ce que, si vous lisez une chaîne c'est plus de 49 caractères, 49 car vous avez besoin de place pour la barre oblique inverse 0, vous allez déborder ce tampon. Et vous pourriez avoir de la chance et être capable de écrire un caractère 51e, 52e, 53e. Mais à un moment donné, le système d'exploitation va dire, non. Ce n'est certainement pas la mémoire vous êtes autorisé à toucher. Et le programme va erreur de segmentation. 

Alors là, les heuristiques doivent être tout fois que vous avez longueur fixe, vous avez pour s'assurer que vous vérifiez la longueur de tout ce que vous essayez à lire en elle. 

PUBLIC: Donc, pour résoudre cela, vous pourrait ont eu une déclaration de vérifier effectivement est la longueur supérieure ou inférieur à? 

DAVID J. Malan: Absolument. Vous avez juste une condition qui dit que, si le - ou plutôt vous ne savez pas nécessairement à l'avance combien de caractères utilisateur va saisir, parce vous avez poule et l'oeuf. Pas jusqu'à ce que vous l'avez lu avec scanf pouvez-vous savoir combien de temps il est. Mais à ce moment, il est trop tard, parce que vous avez déjà lu dans certains bloc de mémoire. Donc, en passant, les évite de bibliothèque CS50 cette question tout à fait, le rappel en utilisant fgetc. Et il lit un caractère à la fois, la pointe des pieds le long, sachant que vous ne peut pas déborder un caractère si vous lisez un à la fois. 

Le hic, c'est avec rappel de GetString est que nous devons constamment re-taille ce morceau de mémoire, ce qui est juste une douleur. Il ya beaucoup de lignes de code pour le faire. Donc, une autre approche consisterait à effectivement utiliser un cousin, si de parler, de scanf. Il existe des variantes d'un grand nombre de ces fonctions qui vérifient le fait longueur de combien de caractères vous pouvez lire au maximum. Et vous pouvez spécifier, ne lisez pas plus de 50 caractères. Ce serait donc une autre approche, mais moins accommodante de grandes entrées. 

Donc la question 2 demande, supposons que la version 3 est compilé et exécuté. Pourquoi ce programme pourrait erreur de segmentation? Alors celui-ci est en fait le même répondre, même si elle regarde un peu amateur. Nous utilisons malloc, qui se sent comme nous nous donner plus d'options. Et puis nous les libérant la mémoire à la fin. Il est encore à seulement 50 octets de mémoire. Donc, nous pourrions encore essayer de lire en 51, 52, 1000 octets. Il va erreur de segmentation pour exactement la même raison. 

Mais il ya une autre raison. Quoi d'autre pourrait malloc retour en plus l'adresse d'un bloc de mémoire? Il pourrait retourner null. Et parce que nous ne sommes pas la vérification des que, nous pourrions faire quelque chose stupide pour une autre raison, qui est que nous pourrions être disons scanf, lisons l'entrée de l'utilisateur à partir du clavier en 0 emplacement, Alias ​​nulle. Et que, aussi, sera certainement déclencher une erreur de segmentation. Donc, pour l'objectif de la jeu-questionnaire, nous le ferions ont accepté soit de ceux en raison valable. L'un est identique. On est un peu plus nuancée. 

Enfin, en ce qui concerne le programme de utilisation de la mémoire, comment faire la version 2 et la version 3 diffèrent? Donc, pour ce que ça vaut, nous avons vu un approvisionnement apparemment inépuisable de possible réponses à cette. Et parmi les réponses des personnes, ce que nous étions espérant, mais nous accepté d'autres choses, était une mention de la fait que la version 2 utilise la pile dite. Version 3 utilise le tas. Et fonctionnellement, ce n'est pas vraiment faire tout ce que beaucoup de différence. A la fin de la journée, nous sommes encore juste obtenir 50 octets de mémoire. 

Mais c'était l'une des réponses possibles que nous cherchions à. Mais vous verrez, que vous obtenez vos questionnaires retrait de la TF, que nous avons accepter d'autres discussions de leur usages disparates de mémoire ainsi. Mais la pile et le tas aurait été une réponse facile pour aller avec. Vous avez des questions? Je vous donne Rob. 

ROB BOWDEN: Donc problème 4. C'est celui où vous avez eu à remplir dans le nombre d'octets de tous ces différents types utilisés. Donc la première chose que nous voyons. Supposons une architecture 32 bits, comme cet appareil de CS50. Donc, l'une des choses fondamentales sur Architectures 32 bits, qui nous dit exactement la taille d'un pointeur va comme dans l'architecture. 

Donc, immédiatement, nous savons que tout pointeur type est 32 bits ou 4 octets. Donc, en regardant ce tableau, un * le noeud est un type pointeur. Cela va être 4 octets. noeud struct *, c'est littéralement identique à noeud étoiles. Et donc que ça va être 4 octets. String, de sorte qu'il ne ressemble pas à un pointeur encore, mais le typedef, un chaîne est juste un char *, qui est un type pointeur. Donc cela va être 4 octets. 

Donc, ces trois sont les 4 octets. Maintenant, le nœud et l'élève sont un peu plus compliqué. Donc, en regardant noeud et étudiant, nous voyons nœud comme un entier et un pointeur. Et l'étudiant est deux pointeurs à l'intérieur de celui-ci. Ainsi, au moins pour notre cas ici, la manière que nous finissons par le calcul de la taille de cette structure est juste ajouter jusqu'à tout c'est à l'intérieur de la structure. 

Donc, pour le noeud, nous avons un nombre entier, qui est de 4 octets. Nous avons un pointeur, qui est de 4 octets. Et si un nœud va de prendre 8 octets. Et de même pour l'étudiant, nous avons une pointeur qui est 4 octets et un autre pointeur qui est de 4 octets. Donc, cela va mettre fin à par être de 8 octets. Donc noeud et étudiant sont de 8 octets. Et ces trois sont les 4 octets. Questions à ce sujet? Oui. 

PUBLIC: Est-il était un 64-bit architecture, serait que doubler tous? 

ROB BOWDEN: Il ne serait pas doubler tous. Donc, l'architecture 64 bits, il, encore une fois, changements cette chose fondamentale que pointeur est maintenant de 64 bits. Ouais. Ainsi, un pointeur est de 8 octets. Donc, ce qui avait 4 octets vont être 8 octets. Un étudiant, qui était de deux points, bien, maintenant il va de 8 octets, 8 octets. Il va faire 16 octets. 

Mais un noeud est toujours 4 octets. Donc, ce pointeur va être de 8 octets. C'est 4 octets. Ainsi, un noeud ne va pour être de 12 octets. D'autres questions sur celui-là? Donc, la suivante, celles-ci sont les codes d'état HTTP. Et vous aviez à décrire les circonstances en vertu de laquelle les forces vous sera retourné. un problème que j'ai entendu des étudiants ont, c'est qu'ils ont essayé de faire la erreurs soient sur la fin du client. Alors, quand nous essayons d'en faire la demande sur le serveur, quelque chose se passe mal sur notre fin. Mais en général, ces codes sont étant renvoyé par le serveur. Donc, nous voulons comprendre ce qui se passe bien ou mal sur le serveur qui provoque ces choses doivent être retournés. Alors pourquoi pourrait retour d'un serveur code d'état 200? Des pensées? 

Ouais. Donc, quelque chose avec succès la demande a traversé. Et ils sont en mesure de retourner tout ce que vous avez demandé. Donc, tout allait bien. Qu'en est-il 302 trouvée? Ouais. 

AUDIENCE: Le serveur était à la recherche pour ce que vous avez demandé. Mais il ne pouvait pas le trouver. Donc, il ya une erreur. 

ROB BOWDEN: Donc, le serveur était à la recherche de ce que vous vouliez. Il suffit donc de regarder ici, 302 trouvés, il était capable de le trouver. 

PUBLIC: Je suis désolé. Trouvé signifie qu'ils ont le trouver. Désolé. 

ROB BOWDEN: Donc 302 trouvé. Le serveur est capable de trouver ce que vous vouliez. 

PUBLIC: Mais ce n'est pas l'afficher? 

ROB BOWDEN: La différence entre 302 et 200 ce qu'il est sait ce que vous voulez. Mais ce n'est pas exactement où vous vouliez poser. Donc 302 est une redirection typique. Donc, vous avez demandé une page. Il sait, oh, je veux pour vous rendre ce. Mais ce n'est à une URL différente. Alors bon, vous voulez vraiment cela. 

DAVID J. Malan: C'est une pièce qui dit que nous avons donné vous les gars une redirection fonction qui utilise la fonction d'en-tête qui, à son tour, imprimé sur l'emplacement, côlon, puis l'URL à laquelle vous souhaitez rejeter l'utilisateur. Même si vous n'avez pas 302 explicitement là, c'est ce que PHP comme par magie insérer comme en-tête dire exactement ce que Rob il - trouvé. Mais allez plutôt ici. 

ROB BOWDEN: OK. Alors que sur 403 interdit? 

PUBLIC: Je pense que c'est ce que le serveur est essentiellement dire que le client ne peut pas accéder à la page d'accueil. 

ROB BOWDEN: Alors oui. Eh bien, la réponse typique nous avons attendre quelque chose comme, les fichiers chmodded ne sont pas convenablement. C'est probablement dans quelles circonstances vous les avez vus. Mais il ya une raison pour laquelle le client pourrait être en faute. Il ya en fait un autre code de statut - 401. Ce sont donc très similaires. 

401 est non autorisée. Et 403 est interdite. Et si vous exclusivement non autorisée obtenir si vous n'êtes pas connecté Mais vous connectant pourrait signifier que vous êtes autorisé. Mais si vous êtes déjà connecté et vous n'ont toujours pas l'autorisation, alors vous pouvez également obtenir interdite. Donc, si vous êtes connecté et que vous n'avez pas autorisation, est aussi interdite quelque chose que vous pouvez obtenir. 

DAVID J. Malan: Et le mécanisme par lequel ces problèmes sont habituellement résolu sur le serveur est par ce commandement? Chmod, si il est, en effet, un des autorisations émettre sur le fichier ou répertoire. 

ROB BOWDEN: Puis 404 not found. Ouais. Donc, contrairement à 302 où il n'était pas exactement où vous vous demandez, mais il sait ce vous voulez, cela, il a juste aucune idée de ce que vous voulez. Et vous ne demandez pas quelque chose de valable. 418 Je suis une théière, puis 500 serveur interne. Alors, pourquoi pourriez-vous obtenir cela? 

Donc, une erreur de segmentation - En fait, je ne sais pas le classement norme pour cela. Mais si votre code PHP avait quelque chose de mal à cela, en théorie, il pourrait en fait une erreur de segmentation, et dans ce cas, cette 500 Erreur interne du serveur, quelque chose est le problème avec votre serveur de configuration. Ou il ya une erreur de syntaxe dans votre code PHP. Ou quelque chose de mauvais se passe. 

DAVID J. Malan: Nous n'avons erreur de segmentation parmi les réponses de quelques personnes. Et techniquement, il pourrait se produire. Mais ce serait un PHP, le programme écrit par d'autres personnes, en fait crashait, qui que si ces personnes vissé et écrit du code bogué dans leur interprète serait PHP lui-même une erreur de segmentation. Ainsi, même si 500 est comme une erreur de segmentation dans l'esprit, c'est presque toujours le résultat d'un problème de fichier de configuration avec votre serveur Web ou, comme l'a dit Rob, une erreur de syntaxe, comme vous ne pas fermer une citation. Ou vous avez perdu un point-virgule quelque part. 

PUBLIC: Donc, pour l'ensemble de processeurs de navette, je pense que quand je l'ai fait une fois que j'ai cliqué sur le navigateur, mais rien n'est venu jusqu'à, ce qu'ils appelaient la page blanche. Mais c'était à cause de ce code. Je pense que c'était JavaScript, non? 

ROB BOWDEN: Ouais. 

PUBLIC: Est-ce que l'erreur encore monter? 

ROB BOWDEN: Donc, vous n'auriez pas eu cette erreur parce que tout du point de vue le serveur Web était tout à fait bien. Mais vous avez demandé index.html. Vous avez demandé shuttle.js et service.js. Et il a pu retourner avec succès à vous toutes ces choses - 200. OK. C'est seulement lorsque le navigateur a essayé de interpréter le code JavaScript C'est comme, attendez, ce n'est pas erreur JavaScript valide. D'autres questions? Très bien. 

DAVID J. Malan: Alors, la prochaine a été de numéro 11. Et 11 était le plus effrayant pour beaucoup de gens. Donc, la chose la plus importante à noter ici était que ce n'était, en effet, environ une liste doublement chaînée. Mais ce n'était pas le même que l'année dernière problème de liste doublement chaînée, qui ne vous donne pas la mise en garde que la liste pourrait, en fait, être non triés. 

Donc, le fait que la liste était non triés et le fait que ce mot était Souligné il était destiné à transmettre que c'est en fait une simplification de ce qui autrement aurait été un problème plus difficile et un plus long. Ainsi, une erreur courante ici était d'avoir mis La solution de l'an dernier sur votre bien pager, puis il suffit de copier aveuglément que bas que la réponse, qui est le droit répondre à une autre question dans le même esprit. Mais les subtilités ici ont été les suivants. 

Donc un, nous avons un noeud déclarée et défini de la manière habituelle ici. Ensuite, nous avons défini la liste des être un mondial pointeur initialisé à null. Puis, apparemment, il ya deux fonctions nous avons des prototypes pour ici, insert et à enlever. Et puis nous avons un exemple de code ici de faire un tas d'insertions. Et puis nous vous demandons de compléter le la mise en oeuvre de l'insert ci-dessous dans cette d'une manière qu'il insère dans la liste n en temps constant, a également souligné, même si déjà présent. 

Donc, la beauté d'être en mesure d'insérer en temps constant, c'est qu'il implique que vous devez insérer le nouveau nœud où? Dans l'avant. Ainsi, il élimine, heureusement, au moins l'un des cas qui nécessitaient encore plus de lignes de code, comme elle l'a fait l'année dernière et même en classe quand nous parlé à travers ce genre de chose avec les humains et avec une certaine verbale pseudo-code. Ainsi, dans la solution ici, nous allons sauter sur à celle qui vient d'avoir un visuel sur l'écran. 

Notez que nous faisons ce qui suit. Et aussi remarquer l'autre simplification était que, même si c'est déjà présent, alors cela signifie, même si le nombre est déjà là, vous pouvez il suffit d'insérer un autre aveugle copie. Et que, aussi, était destiné à être un simplification, afin que vous puissiez concentrer, en réalité, une partie de la plus partie intellectuellement intéressant et pas seulement une vérification d'erreur supplémentaire compte tenu du temps limité. 

Donc, dans cette solution de l'échantillon, nous allouons un pointeur sur la main gauche l'autre ici à un noeud. Maintenant, sachez que pointeur, comme Rob dit, n'est que de 32 bits. Et il ne contient pas réellement une adresse jusqu'à ce que vous assigner l'adresse. Et nous le faisons sur la droite côté avec malloc. Comme un bon citoyen, nous vérifions que malloc n'est pas, en fait, nul, de sorte que nous ne créons pas accidentellement une erreur de segmentation ici. Et chaque fois que vous utilisez malloc dans la vie, vous devrait être le contrôle de null, de peur vous avez un bug subtil. 

Puis on initialise que nulle par attribution n et précédent et suivant. Et dans ce cas là, je initialisé précédente null, parce que cette nouvelle nœud va être la nouvelle au début de ma liste. Donc, il va y avoir rien devant elle. Et je veux ajouter essentiellement la liste existante vers le nouveau nœud par réglage suivant égal à lui-même la liste. Mais je ne suis pas seulement encore fini. Donc, si la liste elle-même existait déjà, et il y avait au moins un noeud déjà en place, si ce n'est la liste ici et insérer un nouveau noeud, je devez vous assurer que mon ancien noeud des points en arrière pour mon nouveau nœud, parce que c'est, encore une fois, une liste doublement chaînée. 

Donc, nous faisons un test de cohérence. Si la liste n'est pas nul, si il ya déjà un ou plusieurs noeuds là-bas, puis ajouter que la référence au verso pour ainsi dire. Et puis la dernière chose dont nous avons besoin à faire est effectivement de mettre à jour le mondial liste variable elle-même au point à ce nouveau noeud. Ouais. 

PUBLIC: Dans la flèche du pointeur [Inaudible] est égal à zéro, est-ce que face à la liste parce que la liste est nulle? 

DAVID J. Malan: Nan. C'est tout simplement que je sois proactive Attention, en ce que si c'est mon liste originale avec peut-être quelques nœuds ici et je insérer mon nouveau nœud ici, il va y à rien ici. Et je tiens à saisir cette idée par la mise en avant nulle sur le nouveau nœud. Et sans doute, si mon code est correct et il n'y a pas d'autre moyen pour insérer nœuds autres que cette fonction, sans doute, même si la liste a déjà un ou plusieurs noeuds en elle, probablement l' liste, le premier noeud, aurait un pointeur null précédente de lui-même. 

PUBLIC: Et un suivi. La raison pour laquelle vous mettez le pointeur égaux prochaines liste est vous faites le pointeur avant la liste en ce qu'il a de pointage à l'autre, je suppose - Je ne - énumère juste? 

DAVID J. Malan: Exactement. Et nous allons donc effectivement considérer deux cas ici vraiment, même si le pour nous les considérons n'est pas tout à fait le même que le numéro de code. Mais à un niveau élevé, si cela représente la liste et cela est un processeur 32 bits pointeur, le scénario le plus simple est que la valeur est nulle par défaut. Et si je veux insérer le numéro 50 a été le premier nombre. Donc, je vais aller de l'avant et d'allouer un noeud, qui va contenir trois domaines - n, précédente et suivante. 

Je vais mettre le numéro 50 ici, parce que ce sera n. Ce sera la prochaine. Et ce sera précédente. Et si ce que je fais dans ce cas? Eh bien, je viens de faire la ligne 1 ici. Pointer n obtient n. Je puis dire, précédente devrait obtenir nulle. Donc cela va être nul. Ensuite, je vais dire ensuite va obtenir la liste. 

Et cela fonctionne très bien. C'est nul. Et si je dis, le nouveau nœud de côté domaine devrait obtenir tout ce que c'est. Alors que l'autre met nulle là. Et puis la dernière chose Je faire est de vérifier ici. Si la liste n'est pas égale à zéro, mais il est égal à zéro, de sorte que nous sautons tout à fait. Et si je ne fais que la prochaine liste obtient pointeur, ce qui se traduit graphiquement dans une photo comme ça. C'est donc un scénario. 

Et celui que vous parliez est précisément ce genre de situation, où nous avons déjà une liste d'un noeud. Et si je retourne dans l'original énoncé du problème, la prochaine nous allons insérer par exemple est de 34, juste pour l'intérêt de la discussion. Donc, je vais juste bien établir que plus ici. Je viens de malloced. Supposons que je vérifie pour nulle. 

Maintenant, je vais initialiser n à 34. Et ce sera n. Ce sera la prochaine. Et ce sera précédente. Faisons en sorte que je n'ai pas obtenir en arrière. Précédent vient en premier dans la définition. Permettez-moi de résoudre ce problème. C'est précédente. C'est ensuite. Même si ceux-ci sont identiques, gardons-conforme. 

Précédent. C'est ensuite. Donc, je viens malloced mon billet, vérifié pour nulle, attribué 34 dans le nœud. Précédent devient nulle. Ce qui me donne cela. Obtient prochaine liste. Donc, la liste est la suivante. Donc, c'est la même chose maintenant que ce dessin flèche, de sorte qu'ils pointent vers une dans le même. Et puis je vérifie si la liste n'est pas égal à zéro. Et ce n'est pas cette fois. Ensuite, je vais faire la liste précédente obtient pointeur. 

Donc, la liste précédente se PTR. Donc, ce qui a pour effet de mettre une flèche graphique ici. Et cela devient un peu ondulée, les lignes. Et puis, enfin, je mets à jour liste pour pointer vers pointeur. Alors maintenant, cela souligne ce type. Et maintenant, faisons un rapide test de cohérence. 

Voici la liste, qui est la variable globale. Le premier noeud est, en effet, 34, parce que Je ne fais que suivre cette flèche. Et c'est correct parce que je veux insérer au début de la liste tous les nouveaux noeuds. Son champ suivant m'amène à ce gars. Si je continue, je frappe est à côté nulle. Donc, il n'y a plus de liste. Si je frappe précédente, je reçois sauvegarder où je m'attendais. 

Donc, il ya encore quelques conseils, de toute évidence, à manipuler. Mais le fait que vous a dit de faire ce en temps constant signifie que vous ne un nombre fini de choses vous êtes autorisé à le faire. Et quel est ce nombre? Il pourrait être une étape. Il pourrait être deux. Il pourrait être de 1000 marches. Mais c'est fini, ce qui signifie que vous ne pouvez pas ont toute sorte de boucle passe ici, pas de récursivité, pas de boucles. Il a juste à être des lignes codées en dur code que nous avons dans cet échantillon. 

Donc le problème suivant 12 nous a demandé de compléter la mise en œuvre de supprimer ci-dessous de façon à ce qu'il supprime n à partir de la liste dans le temps linéaire. Donc, vous avez un peu plus marge de manœuvre maintenant. Vous pouvez supposer que n, si présent dans la liste, sera présent pas plus d'une fois. Et que trop est censé être basé quiz une hypothèse simplificatrice, de sorte que si vous trouvez le nombre 50, quelque part dans la liste, vous ne faites pas aussi à vous soucier de continuer à parcourir, à la recherche de tous les possibles copie de 50, ce qui ne devrait déléguer dans une certaine minutie dans un temps limité. 

Donc, avec supprimer, celui-ci était certainement plus difficile et plus code à écrire. Mais à première vue, franchement, il pourrait ressembler à quelque chose comme écrasante et il n'ya aucun moyen que vous pourriez avoir arriver à un quiz. Mais si nous nous concentrons sur les différentes étapes, espérons-le, il va soudainement vous frapper que chacun de ces individus étapes est logique évidente rétrospectivement. Donc, nous allons jeter un coup d'oeil. 

Alors d'abord, on initialise le pointeur être la liste elle-même. Parce que je veux avoir le temps linéaire, que les moyens Je vais avoir une boucle. Et une voie commune pour itérer sur la les noeuds dans une structure de liste ou un autre type de la structure est itérative à prendre un pointeur vers l'avant des données structure et puis il suffit de commencer la mise à jour et marcher votre chemin à travers la structure de données. Donc, je vais faire exactement cela. 

Alors que pointeur, ma variable temporaire, n'est pas égal à zéro, nous allons aller de l'avant et vérifier. Ai-je de la chance? Est le domaine de n dans le noeud Je suis actuellement regardant égale à la nombre Je cherche? Et si oui, faisons quelque chose. Maintenant, remarquez ce si la condition entoure la totalité lignes de code suivantes. C'est la seule chose qui m'importe - trouver un numéro en question. Donc, il n'y a pas d'autre, ce qui simplifie choses conceptuellement un peu. 

Mais maintenant, je me suis rendu, et vous pourriez avoir seulement réalisé ce après réflexion à travers un peu, il est en fait deux cas ici. On est où le nœud est à l' au début de la liste, qui est un peu ennuyeux, parce que c'est un cas particulier, parce que vous avez à traiter avec cette chose, qui est la seule anomalie. Partout ailleurs dans la liste, c'est la même chose. Il ya un noeud précédent et une prochaine noeud, le noeud précédent, le noeud suivant. Mais ce gars-là est un peu spécial s'il est au début. 

Donc, si le pointeur est égale à la liste elle-même, si je suis au début de la liste et j'ai trouvé n, j'ai besoin de faire une ou deux choses. Un, j'ai besoin de changer de liste pointer vers le champ suivant, 50. Alors suppose que je suis en train pour éliminer 34. Donc, ce gars a aller loin dans un instant. 

Donc, je vais vous dire, la liste obtient pointeur prochaine. Eh bien, c'est le pointeur. Suivant est orientée vers le haut ici. Cela change la flèche droite maintenant pour pointer vers ce type ici. Maintenant, rappelez-vous, nous avons une variable temporaire. Nous n'avons donc pas orphelins tous les nœuds, car j'ai aussi ce gars dans mon la mise en œuvre de supprimer. Alors maintenant, si la liste elle-même n'est pas nul, J'ai besoin de fixer un petit quelque chose. 

J'ai besoin de faire maintenant s'assurer que cette flèche, qui est préalablement pointant 50-34, ça doit aller, parce que si je suis en train de se débarrasser de 34, 50 avaient mieux ne tienne pas sorte de retour de référence à lui comme le flèche suggéré. Donc je l'ai fait cette ligne. Alors je suis fait. Cette affaire est en fait assez facile. Coupant la tête de la liste est relativement simple. 

Malheureusement, il ya cette bloc gênant autre. Alors maintenant, je dois tenir compte le cas où il ya quelque chose dans le milieu. Mais il n'est pas trop mauvais, sauf pour cette syntaxe. Donc, si je ne suis pas au début de la liste, je suis quelque part au milieu. Et cette ligne dit ici, début quel que soit le nœud que vous êtes. Aller au champ suivant du noeud précédent et souligner que le pointeur. 

Faisons-le imagé. Qui devenait compliqué. Donc, si j'ai un champs précédents ici - nous allons le faire - champs suivants ici. Je vais simplifier mes pointeurs plutôt que de tirer tout un tas de les choses aller et retour qui sillonnent de l'autre. Et maintenant, disons simplement que c'est 1, 2, 3 pour les besoins du débat, même mais qui ne s'aligne pas avec le problème en question. 

Alors, voici ma liste chaînée. Je suis en train de retirer deux dans ce version de l'histoire. Donc, j'ai mis à jour le pointeur de être orienté vers ce type. Donc, c'est PTR. Il est pointée ici. C'est la liste, qui existe le monde comme avant. Et il pointant ici, peu importe quoi. Et maintenant, je suis en train de retirer deux. 

Donc, si le pointeur pointe ici, je suis va suivre, apparemment, l' pointeur précédente, ce qui me met à 1. Je puis aller à dire que la prochaine domaine, ce qui m'amène vers ce boîte ici, va égal pointeur prochaine. Donc, si ce pointeur, c'est à côté. Cela signifie que cette flèche besoins pour pointer vers ce type. 

Alors, que cette ligne de code vient fait un peu de cela. Et maintenant, cette recherche comme un pas dans la bonne direction. Nous voulons essentiellement pour couper 2 sur du milieu de 1 et 3. Il est donc logique que nous voulons voie ce pointeur autour d'elle. Donc, la prochaine ligne est de vérifier si le pointeur est à côté pas nul, il ya en effet quelqu'un le droit de 2, cela signifie que nous devons également faire un petit bout ici. 

J'ai donc besoin de vous maintenant pour suivre ce pointeur et mettre à jour le pointeur précédente sur ce gars-là à faire un peu d'un contourner ici le point ici. Et maintenant, visuellement c'est agréable. C'est un peu désordonné en ce que il ya pas un dirigeant à la 2 plus. 2 pointe vers la gauche. Et 2 pointe vers la droite. Mais il peut faire ce qu'il veut, parce il est sur le point de se libérer. Et ce n'est pas grave ce que ces valeurs sont plus. 

Ce qui est important, c'est que le reste gars routent ci-dessus et en dessous de lui maintenant. Et en effet, c'est ce que nous ferons par la suite. Nous pointeur libre, ce qui signifie que nous disons la système d'exploitation, vous êtes les bienvenus pour récupérer ce. Et puis enfin, nous reviendrons. Autres implicitement, si nous n'ont pas encore retourné, nous devons continuer à chercher. Donc pointeur est égal pointeur à côté juste signifie déplacer ce gars ici. Déplacez ce gars ici. Déplacez ce gars ici si, en fait, nous n'avons pas trouvé le nombre nous cherchons encore. 

Donc, franchement, il semble tout à fait écrasante, je pense que, dans un premier temps coup d'oeil, surtout si vous avez lutté avec ce pendant le test alors voir quelque chose comme ça. Et vous tape sur le dos. Eh bien, il n'ya aucun moyen je pourrais avoir arriver à ce sur le quiz. Mais je dirais, vous pouvez, si vous cassez vers le bas dans ces individuel cas et seulement à pied à travers elle attentivement, mais, il est vrai, sous des circonstances stressantes. 

Heureusement, la situation a tout heureux. Vous pouvez dessiner ce dans n'importe quel nombre de façons. Vous n'avez pas à faire le chassé-croisé chose ici. Vous pouvez le faire avec droit lignes de ce genre. Mais l'essentiel de ce problème, en général, était de se rendre compte que la image dans le final devrait ressembler un peu quelque chose comme ça, parce que constante de temps implique que vous gardez brouillage et de brouillage et bloque le nouveaux nœuds au début de la liste. Vous avez des questions? Probablement le plus difficile de certainement des questions de codage. 

PUBLIC: Donc est semblable à la liste la tête dans les exemples précédents. 

DAVID J. Malan: Exactement, exactement. Juste un nom différent pour une variable globale. Dans le monde entier quoi? 

ROB BOWDEN: OK. Donc, c'est celui où vous eu à écrire le paragraphe. Certaines personnes ont écrit des essais pour cette question. Mais vous avez juste besoin d'utiliser ces six conditions pour décrire ce qui arrive quand vous essayez de contacter facebook.com. Je vais donc parler à travers le processus en utilisant tous ces termes. Donc, dans notre navigateur, nous tapons facebook.com et appuyez sur Entrée. Donc, notre navigateur va construire un HTTP demandent que ça va envoyer par un processus à Facebook pour Facebook pour nous répondre avec la HTML de sa page. 

Alors, quel est le processus par où la requête HTTP obtient effectivement à Facebook? Alors d'abord, nous devons traduire Facebook.com. Il suffit donc donné le nom Facebook.com, d'où vient réellement la requête HTTP besoin d'aller? Nous avons donc besoin de traduire Facebook.com à une adresse IP, qui unique identifie quelle machine nous fait voulez envoyer cette demande à. Votre ordinateur portable dispose d'une adresse IP. Tout ce connecté à Internet dispose d'une adresse IP. 

Donc, DNS, Domain Name System, qui est ce qui va gérer la traduction de facebook.com à une adresse IP vous voulez vraiment communiquer. Donc, nous contactons les serveurs DNS et par exemple, ce qui est facebook.com? Il dit, oh, c'est l'adresse IP 190,212 quelque chose, quelque chose, quelque chose. Très bien. Maintenant, je sais ce que la machine Je souhaite contacter. 

Alors vous envoyez votre requête HTTP au cours de cette machine. Alors, comment obtient-il de cette machine? Eh bien, la demande va de routeur à rebondissement. Rappelez-vous l'exemple de la classe, où nous avons effectivement vu la route que le paquets ont quand nous avons essayé à communiquer. On l'a vu sauter par-dessus l'Atlantique Océan, à un moment ou autre. 

Ainsi, le dernier port terme. Donc, c'est maintenant sur votre ordinateur. Vous pouvez avoir plusieurs choses actuellement la communication avec l'Internet. Donc, je peux être en cours d'exécution, par exemple, Skype. Je pourrais avoir un navigateur ouvert. Je pourrais avoir quelque chose qui torrenting fichiers. Donc, toutes ces choses sont communiquant avec l' internet d'une certaine façon. 

Ainsi, lorsque votre ordinateur reçoit des données de l'Internet, comment ça savoir ce que l'application fait veut que les données? Comment sait-il si ce particulier données est destiné à la torrenting demande par opposition pour le navigateur web? C'est donc dans le but de ports que toutes ces applications ont selon un port sur votre ordinateur. Donc, votre navigateur dit, hey, Je suis à l'écoute sur le port 1000. Et votre programme de torrenting dit, Je suis à l'écoute sur le port 3000. Et Skype dit, je suis en utilisant le port 4000. 

Ainsi, lorsque vous obtenez des données qui appartient l'une de ces applications, les données est marqué par quel port il fait doivent être envoyés le long de. Donc, cela dit, oh, j'appartiens au port 1000. Je sais que je dois transmettre cette le long de mon navigateur. Donc, la raison pour laquelle il est pertinent ici est que les serveurs Web ont tendance à écouter sur le port 80. Donc, lorsque je communique avec Facebook.com, je suis communiquant avec une machine. Mais je dois dire que le port de cette machine que je veux communiquer. Et des serveurs Web ont tendance à être écoute sur le port 80. 

S'ils voulaient, ils pouvaient l' de façon à ce qu'il présente comme sur le port 7000. Et puis dans un navigateur web, j'ai pu saisir manuellement Facebook.com: 7000 envoyer la demande au port 7000 du serveur Web de Facebook. 

DAVID J. Malan: Et dans ce cas, même si nous n'avons pas besoin que les gens mentionner, dans ce cas, quel port serait la demande fait aller? Essayez à nouveau. Exactement. Ne cherche pas pour cela, mais une subtilité c'est là n'en dernier. 

ROB BOWDEN: Donc, le HTTPS, car il est spécifiquement pour l'écoute crypté, c'est sur le port 4430. 

PUBLIC: Et emails sont 25, non? 

DAVID J. Malan: Outbound e-mails, 25, oui. 

ROB BOWDEN: Je ne sais même pas plus de le - tous les plus basses ont tendance à être réservée aux choses. Je pense que tout sous 1024 est réservé. 

PUBLIC: Pourquoi dites-vous 3 était le mauvais numéro? 

ROB BOWDEN: Parce que dans une adresse IP, il ya quatre groupes de chiffres. Et ils sont de 0 à 255. Donc 192.168.2.1 est une commune adresse IP du réseau local. Notez tous ceux qui sont à moins de 255. Alors, quand j'ai commencé avec 300, que ne pourrait éventuellement avoir l'un des numéros. 

DAVID J. Malan: Mais ce clip idiot de - était-ce CSI, où ils avaient une nombre qui était trop grand pour l'adresse IP. 

ROB BOWDEN: Toutes les questions à ce sujet? Le prochain changement si complet dans sujet, mais nous avons ce tableau PHP pour les maisons dans le quad. Et nous avons une liste non ordonnée. Et nous voulons imprimer chaque élément de la liste juste contenant le nom de la maison. Nous avons donc une boucle foreach. Donc n'oubliez pas, la syntaxe est foreach tableau comme élément du tableau. Ainsi, grâce à chaque itération de la boucle, maison va prendre sur l'un des valeurs à l'intérieur de la matrice. 

A la première itération, maison seront Cabot Chambre. Sur un deuxième itération, maison sera être Courier Maison et ainsi de suite. Ainsi, pour chaque quad que la maison, nous sommes juste aller à imprimer - vous pouvez aussi fait l'écho - l'élément de la liste, puis le nom de la maison et puis fermez l'élément de liste. Les accolades sont facultatives ici. 

Et puis nous avons également dit dans la question lui-même, n'oubliez pas de fermer la liste non ordonnée tag. Nous devons donc quitter le mode PHP pour ce faire. Ou nous aurions pu écho à la fermer liste non ordonnée tag. 

DAVID J. Malan: Aussi bien ici serait ont été d'utiliser une ancienne école pour boucle avec un $ i = 0 0 et en utilisant les chiffres à déterminer la longueur du rayon. Tout à fait bien trop, juste un peu verbeux. 

PUBLIC: Donc, si vous alliez [Inaudible], feriez-vous - J'ai oublié ce que la boucle [inaudible] est. Souhaitez-vous $ quad support i? 

DAVID J. Malan: Exactement. Oui, exactement. 

ROB BOWDEN: Autre chose? 

DAVID J. Malan: Très bien. Compromis. Il y avait donc des grappes de réponses possible pour chacun de ceux-ci. Nous avons été vraiment juste à la recherche de quelque chose de convaincant pour une tête et un inconvénient. Et le numéro 16 a demandé, valider les utilisateurs ' entrée côté client, comme avec JavaScript à la place du côté serveur, comme avec PHP. Alors, quel est l'envers de faire côté client? 

Eh bien, l'une des choses que nous avons proposées est que vous réduisez la latence, parce que vous ne pas avoir à se soucier contact avec le serveur, ce qui pourrait prendre un peu millisecondes ou même un couple de secondes en évitant que juste et validation de l'entrée côté client des utilisateurs en déclenchement d'un gestionnaire de soumettre et vérifier simplement, ne leur type quelque chose dans de nom? Ont-ils quelque chose de type dans l'adresse e-mail? Ont-ils choisi un dortoir de le menu déroulant? 

Vous pouvez leur donner une rétroaction instantanée en utilisant l'ordinateur de gigahertz ou ce qu'ils ont c'est effectivement sur leur bureau. Donc, c'est juste une meilleure utilisation l'expérience généralement. Mais une baisse de faire côté client validation, si vous le faites sans aussi faire la validation côté serveur est que la plupart des personne sortant de CS50 sait que vous pouvez envoyer toutes les données que vous voulez à un serveur quelconque de plusieurs manières. Franchement, dans la plupart n'importe quel navigateur, vous pouvez cliquer partout dans les paramètres et juste désactiver JavaScript, ce qui serait, donc désactiver toute forme de validation. 

Mais vous pouvez aussi rappeler que même moi fait des choses mystérieuses dans la classe à l'aide telnet et fait semblant d' être un navigateur en envoyant get des requêtes à un serveur. Et ce n'est certainement pas en utilisant n'importe quel JavaScript. C'est juste moi tapant des commandes à un clavier. Alors, vraiment, tout programmeur dans suffisamment confort avec le web et HTTP pourrait envoyer toutes les données qu'il ou elle veut à un serveur sans validation. Et si votre serveur n'est pas aussi vérifier, ont-ils me donnent un nom, est ce fait une adresse de courriel valide, a fait ils choisissent un dortoir, vous pourriez finir jusqu'à l'insertion de faux ou tout simplement données vierge dans votre base de données, ce qui a probablement ne va pas être une bonne chose si vous supposez qu'il était là. 

Donc, c'est une réalité gênante. Mais en général, côté client validation est grande. Mais cela signifie deux fois plus de travail. Bien qu'il n'en existe divers les bibliothèques, les bibliothèques JavaScript pour exemple, que faire de ce bien, beaucoup moins de maux de tête. Et vous pouvez réutiliser une partie du code côté serveur, côté client. Mais ne se rendent compte qu'il est généralement travail supplémentaire. Ouais. 

PUBLIC: Donc, si nous venons dit moins sûr - 

DAVID J. Malan: [RIRES] Ugh. Ce sont toujours les plus difficiles ceux à statuer. 

ROB BOWDEN: Ce serait ont été acceptées. 

DAVID J. Malan: Quoi? 

ROB BOWDEN: J'ai créé ce problème. Cela aurait été accepté. 

DAVID J. Malan: Ouais. 

PUBLIC: Cool. 

ROB BOWDEN: Mais nous n'avons pas accepté pour la première - bien, ce que nous cherchions est quelque chose comme vous n'avez pas à communiquer avec le serveur. Nous n'avons pas accepté simplement plus rapide. 

PUBLIC: Qu'en est-il ne pas recharger la page? 

ROB BOWDEN: Oui. C'était une réponse acceptée. 

DAVID J. Malan: Tout où nous nous sentions il était plus probable qu'improbable probable que vous saviez ce que vous étiez dire, qui est un dur Ligne pour tracer parfois. Utilisation d'une liste liée à la place d'un tableau à maintenir un liste de nombres entiers triés. Ainsi, une hausse nous citons souvent lié listes qui ont motivé leur ensemble l'introduction était vous obtenez dynamisme. Ils peuvent se développer. Ils peuvent diminuer. Donc, vous n'avez pas à sauter à travers des cerceaux pour créer effectivement plus de mémoire avec un tableau. Ou vous n'avez pas à juste dire, désolé, utilisateur. Le tableau est rempli. Ainsi la croissance dynamique de la liste. Un inconvénient que des listes chaînées? 

PUBLIC: Il est linéaire. Recherche sur liste chaînée est linéaire au lieu de ce que vous vous connectez po 

DAVID J. Malan: Exactement. Recherche sur une liste chaînée est linéaire, même si elle est triée, parce que vous pouvez ne suivez ces miettes de pain, les pointeurs, à partir du début de la liste à la fin. Vous ne pouvez pas tirer parti de l'accès aléatoire et, ainsi, la recherche binaire, même si c'est triée, que vous pourriez faire avec un tableau. Et il ya aussi un autre coût. Ouais. 

PUBLIC: Mémoire inefficace? 

DAVID J. Malan: Ouais. Eh bien, je ne veux pas nécessairement dire inefficace. Mais il ne vous coûtera plus de mémoire, car vous avez besoin de 32 bits pour chaque noeud pour le pointeur supplémentaire, à moins pour une liste chaînée. Maintenant, si vous êtes seulement à stocker des nombres entiers et vous ajoutez le pointeur, c'est effectivement sorte de non-triviale. Il est de doubler la quantité de mémoire. Mais en réalité, si vous stockez un liste chaînée de struct, qui pourraient avoir 8 octets, 16 octets, encore plus que cela, c'est peut-être moins d'un coût marginal. Mais c'est un coût quand même. Donc, soit de ceux qui aurait été bien que des inconvénients. 

18. Utiliser PHP au lieu de C à écrire un programme en ligne de commande. Donc, ici, il est souvent plus rapide d'utiliser une langue comme PHP ou Ruby ou Python. Vous venez d'ouvrir rapidement un éditeur de texte. Vous avez beaucoup plus de fonctions s'offrent à vous. PHP a l'évier de la cuisine de fonctions, alors que dans C, vous ont très, très peu. En fait, les gars savent le à la dure que vous n'avez pas les tables de hachage. Vous n'avez pas liée listes. Si vous voulez ceux-ci, vous devez mettre en œuvre vous-même. 

Donc, une tête en PHP ou vraiment tout langage interprété est la rapidité avec lequel vous pouvez écrire du code. Mais un inconvénient, nous avons vu cela quand je rapidement fouettée un Misspeller mise en œuvre en cours à partir de PHP, est que l'utilisation d'un langage interprété est généralement plus lent. Et nous avons vu que manifestement avec un augmentation du temps de 0,3 secondes pour 3 secondes, en raison de l'interprétation ce qui se passe réellement. 

Un autre point positif était que vous ne pas avoir à compiler. Ainsi, il permet également d'accélérer le développement d'ailleurs, parce que vous n'avez pas deux étapes à l'exécution d'un programme. Vous n'avez qu'un seul. Et c'est à peu convaincante ainsi. En utilisant une base de données SQL au lieu de un fichier CSV pour stocker des données. Base de données pour SQL est utilisé pour pset7. Fichiers CSV vous n'avez pas utilisé beaucoup. Mais vous l'avez utilisé indirectement comme pset7 bien en parlant de Yahoo Finance. 

Mais CSV est juste comme un fichier Excel, mais super simple, où les colonnes sont juste démarquée par des virgules à l'intérieur d'un fichier de texte contraire. Et en utilisant une base de données SQL est un peu plus convaincante. Il s'agit d'une hausse, parce que vous avez des choses comme sélectionner et insérer et supprimer. Et vous obtenez, vraisemblablement, index MySQL et d'autres bases de données, comme Oracle, construire pour vous en souvenir, qui signifie que votre sélection n'est probablement pas va être top linéaire vers le bas. Il s'agit en fait va être quelque chose comme la recherche binaire ou quelque chose dans le même esprit. Ils sont donc généralement plus rapide. 

Mais un inconvénient est que c'est juste plus de travail. C'est plus d'efforts. Vous devez comprendre les bases de données. Vous devez mettre en place. Vous avez besoin d'un serveur pour exécuter que sur la base de données. Vous devez comprendre comment le configurer. Donc, ce ne sont que les sortes de compromis. Considérant que d'un fichier CSV, vous pouvez créer avec gedit. Et vous êtes bon pour aller. Il n'y a pas de complexité au-delà. 

L'utilisation d'un trie au lieu d'une table de hachage avec chaînage séparé pour stocker une dictionnaire des mots qui rappellent de pset5. Ainsi, une tente à l'envers, en théorie au moins, c'est quoi? Constante de temps, au moins si vous êtes hachage de chaque individu de l' lettres d'un mot, comme vous pourrait avoir pour pset5. C'est peut-être cinq, six tables de hachage hache si il ya cinq ou six lettres dans le mot. Et c'est très bien. Et si il ya une limite supérieure sur la façon longtemps vos mots pourraient être, c'est temps en effet asymptotiquement constant. 

Alors qu'une table de hachage avec distinct chaînage, le problème là avec cette type de structure de données est que l' performances de vos algorithmes habituellement dépend du nombre de choses déjà dans la structure de données. Et c'est certainement le cas avec chaînes, de sorte que le plus de choses que vous mettez dans une table de hachage, plus les chaînes vont, ce qui signifie dans le pire cas, la chose que vous cherchez peut-être est tout le chemin à la fin de l'une de ces chaînes, qui a effectivement dévolue en quelque chose de linéaire. 

Or, en pratique, il ne pouvait absolument être le cas que d'une table de hachage avec chaînes est plus rapide qu'un correspondant la mise en oeuvre de structure arborescente. Mais c'est pour diverses raisons, parmi qui sont essais utilisent un tas de mémoire qui peut, en effet, les choses lentement vers le bas, parce que vous n'obtenez pas belle avantages de ce qu'on appelle la mise en cache, où les choses qui sont proches les unes des en mémoire peut être consulté souvent plus rapidement. Et parfois, vous pouvez venir avec une fonction de hachage vraiment bon. Même si vous avez à perdre un peu de mémoire, vous pourriez, en effet, être en mesure de trouver les choses rapidement et pas aussi mauvais que linéairement. 

Donc en bref, il n'y avait pas nécessairement avec l'un de ces un ou même deux des choses spécifiques que nous recherchions. Vraiment quelque chose de persuasion comme une hausse qu'à la baisse généralement attiré notre attention. 

ROB BOWDEN: Donc, pour la hausse, nous avons fait pas accepter sur son propre "plus vite". Vous dû dire quelque chose à ce sujet. Même si vous avez dit théoriquement plus rapide, nous savions que vous sorte de compris qu'il est de 0 1. Et une table de hachage, en théorie, est différent de 0 sur 1. Mentionner quoi que ce soit sur l'exécution généralement vous avez obtenu les points. Mais "plus vite", la plupart des solutions sur le grand conseil qui ont été essais étaient objectivement plus lentement que des solutions qui étaient les tables de hachage. Donc, plus rapide, en soi, n'est pas vraiment vrai. 

DAVID J. Malan: Dom de dom dom. Je suis probablement le seul qui réalise c'est comme ça que c'est censé être prononcée, non? 

ROB BOWDEN: je n'avais aucune idée. 

DAVID J. Malan: Il fait sens dans ma tête. 

ROB BOWDEN: je fais celui-ci. OK. Donc, c'est celui où vous avez eu à tirer le schéma semblable à vous pourriez ont vu sur les examens passés. Donc, nous allons simplement regarder cela. Donc, à partir du noeud de HTML, nous avons deux enfants, la tête et le corps. Donc, nous bifurquons - tête et le corps. La tête a une balise de titre. Donc, nous avons un titre. 

Maintenant, la seule chose que beaucoup de gens oublié, c'est que ces nœuds de texte sont éléments à l'intérieur de cet arbre. Donc, ici nous arrive de les attirer par des ovales pour les différencier de ceux-ci types de noeuds. Mais remarquez aussi nous avons ici en haut, milieu et du bas finira par être les nœuds de texte. Donc oublier ceux était un peu d'une erreur commune. 

Le corps a trois enfants - ces trois divs. Donc div, div, div, puis le texte nœuds enfants de ces divs. C'est à peu près tout pour que les questions. 

DAVID J. Malan: Et il est intéressant de noter, même si nous ne nous attardons pas sur ces détails dans le temps que nous passons sur JavaScript que l'ordre fait, dans fait, la matière techniquement. Donc, si la tête vient avant dans le corps HTML, il devrait apparaître à la gauche du corps dans les DOM réelle. Que son est, en général, juste FYI, quelque chose qui s'appelle l'ordre du document, où ce qui importe. Et si vous étiez implémentez un analyseur, un programme qui lit le code HTML dans le bâtiment l'arbre en mémoire, pour être honnête, c'est probablement ce que vous intuitivement faire de toute façon - de haut en bas, de gauche à droite. 

ROB BOWDEN: Questions à ce sujet? Dois-je faire le prochain? 

DAVID J. Malan: Bien sûr. 

ROB BOWDEN: OK. Donc, c'est le dépassement de mémoire tampon question d'attaque. La principale chose à reconnaître ici est, bien, comment pourrait un tour de l'adversaire ce programme en exécution code arbitraire? Donc argv1, la première ligne de commande argument de ce programme, qui peut être longueur arbitraire. Mais ici nous utilisons memcpy pour copier argv1, qui ici est bar. Nous passons comme argument. Et c'est en prenant la barre de nom. 

Nous sommes donc memcpying bar dans ce tampon c. Combien d'octets sommes nous copions? Eh bien cependant beaucoup bar octets arrive à être à l'aide, la longueur de cet argument. Mais c est à seulement 12 octets de large. Donc, si on tape un argument de ligne de commande c'est plus de 12 octets, nous sommes va déborder ce notamment tampon. Maintenant, comment pourrait un adversaire tromper le programmer dans l'exécution de code arbitraire? 

Alors, n'oubliez pas que ici principal appelle foo. Et alors les appels principaux foo. Tirons cela. Donc, nous avons notre pile. Et principale a un cadre de pile en bas. À un certain moment, les appels principaux foo. Eh bien, tout de suite, les appels principaux foo. Et si foo obtient son propre cadre de pile. 

Maintenant, à un moment donné, foo va revenir. Et il est allé retours foo, nous avons besoin de savoir à quelle ligne de code à l'intérieur de nous principale étaient pour savoir où nous devrions reprendre en principal. Nous pouvons appeler foo de l'ensemble tas d'endroits différents. Comment savons-nous où revenir? Eh bien, nous avons besoin de stocker que quelque part. 

Donc, quelque part à droite ici, nous stockons où nous devrions revenir à une fois déclarations de foo. Et c'est l'adresse de retour. Alors, comment un adversaire peut profiter de ceci est le fait que ce tampon c est stocké, nous allons dire, ici, est c. Nous avons donc 12 octets pour c. C'est c. Et c'est l'anneau de la pile de foo. Donc, si l'utilisateur malveillant pénètre plus octets de 12 ou qu'ils entrent dans une commande argument de la ligne qui est plus de 12 caractères, puis nous allons déborder ce tampon. 

Nous pouvons continuer. Et à un moment donné, nous allons bien assez que nous commençons écraser cette adresse de retour. Donc, une fois que nous écraser l'adresse de retour, cela signifie que lorsque foo rendements, nous sommes de retour à l'endroit où la utilisateur malveillant est dit à par quelle que soit la valeur de son entrée, quel que soit le caractères entré par l'utilisateur. Et si l'utilisateur malveillant est en cours particulièrement intelligent, il peut avoir cette revenir à quelque part dans le printDef fonction ou quelque part dans le malloc fonction, n'importe où arbitraire. 

Mais encore plus intelligent est ce que si il a l'utilisateur revenir ici. Et puis vous commencez à exécuter ceux-ci sous forme de lignes de code. Donc, à ce moment, l'utilisateur peut entrer ce qu'il veut dans cette région. Et il a un contrôle complet sur votre programme. Questions à ce sujet? Donc la question suivante est terminée, le une ré-implémentation de foo de manière que ce n'est pas plus vulnérable. 

Donc, il ya deux façons vous auriez pu faire cela. Nous avons encore c seulement étant de longueur 12. Vous pourriez avoir changé cette dans le cadre de votre solution. Nous avons également ajouté un chèque à faire vous que la barre n'était pas nulle. Si vous n'avez pas besoin que pour un crédit complet. Nous allons donc vérifier d'abord la longueur de la chaîne de bar. Si elle est supérieure à 12, alors ne pas réellement faire la copie. Donc, c'est une façon de le fixer. 

Une autre façon de le fixer est la place de c ayant seulement être de longueur 12, l'ont être d'une longueur strlen (bar). Un autre moyen de fixation, il est à fait juste retour. Donc, si vous venais débarrasser de tous cela, si vous aviez supprimé toutes lignes de code, vous auriez obtenu crédit complet, puisque cette fonction ne fait pas accomplir quoi que ce soit. C'est la copie de la ligne de commande l'argument dans une certaine gamme de son cadre de pile locale. Et alors la chose est de retour. Et tout ce qu'il accompli est parti. Donc retour était aussi une suffisante moyen d'obtenir un crédit complet. 

DAVID J. Malan: Pas tout à fait l'esprit de la question, mais acceptable par le spec néanmoins. 

ROB BOWDEN: Questions sur tout cela? La seule chose que vous au moins nécessaire d'avoir la compilation du code. Ainsi, même si, techniquement, vous n'êtes pas vulnérable si votre code ne compiler, nous n'avons pas accepté cela. Pas de questions? OK. 

DAVID J. Malan: Voulez-vous à-dire ce titre? 

ROB BOWDEN: Non 

DAVID J. Malan: Donc, dans celui-ci, ce était soit bonne ou de mauvaises nouvelles. C'est littéralement le même problème comme le premier test. Et c'est à peu près la même problème pset1. Mais il a été volontairement simplifié pour être une pyramide plus simple, qui peut être une résolu avec un peu itération simple. Et vraiment, ce que nous recevions à ici n'est pas tant la logique, parce que probablement, à ce moment, vous êtes plus à l'aise que vous étiez dans la première semaine avec des boucles ou boucles pourquoi, mais vraiment à démêler que vous êtes un peu à l'aise avec l' notion que PHP n'est pas seulement ce que programmation. Il peut en fait être utilisé comme une langue d'écrire des programmes en ligne de commande. 

Et en effet, c'est ce que nous avons essayé attirer votre attention. Il s'agit d'un programme PHP en ligne de commande. Donc le code C ici, tandis que correct en C, pas corriger pour PHP. Mais le code est vraiment le même. Si vous comparez les solutions pour Quiz 0 contre Quiz 1, vous verrez que il est presque identique, sauf pour certains signes de dollar et de la l'absence d'un type de données. En particulier, si nous prenons un coup d'oeil ici, vous verrez que nous parcourons, dans ce cas, de 1 à travers 7. 

Nous aurions pu le faire index 0. Mais parfois, je pense que c'est juste mentalement plus facile de penser à des choses de 1 à 7. Si vous voulez un bloc, puis deux blocs, puis trois, puis point, point, dot sept. Nous avons j étant initialisé à 1 puis compter sur un maximum de i. Et tout ici est par ailleurs identique. Mais digne de mention sont un certain nombre de choses. Nous vous donnons ces deux lignes, ce premier un, goofily nommé un tralala pour claquement sec. Et qui spécifie seulement le chemin, la le filtre, dans lequel un programme peut être constaté que vous souhaitez utiliser d'interpréter ce fichier. 

Et puis la ligne après que, de bien sûr, signifie entrer en mode PHP. Et la ligne tout en bas signifie quitter le mode PHP. Et cela fonctionne, en général, avec interprété langues. C'est un peu ennuyeux si vous écrivez un programme dans un fichier appelé foo.php. Et puis vos utilisateurs doivent simplement rappelez-vous, OK, pour exécuter ce programme, je taper "espace de php foo.php." Genre ennuyeux si rien d'autre. Et il révèle également que votre programme est écrit dans PHP, ce qui n'est pas tout que d'éclairage pour l'utilisateur. 

Ainsi, vous pouvez supprimer le fichier. Php tout rappeler de conférence. Et vous pouvez réellement faire. / Foo si vous avez chmodded en le faisant exécutable. Donc chmod a + x foo aurait fait. Et si vous ajoutez aussi le toutim ici. Mais vraiment, le problème devenait à imprimer quelque chose comme ça. Pas de HTML, pas de code C certainement, juste un peu de PHP. Alors Milo est ensuite retourné dans le problème 25. Et en 25, on vous a donné ce qui suit code de squelette, qui était un page web assez simple. Et la partie juteuse HTML-sage est en baisse ici, où nous avons à l'intérieur du corps une forme qui a l'ID unique d'entrées l'intérieur de ce qui était deux entrées, l'une avec une idée de nom, un avec une idée de bouton. 

Le premier est de type texte, le deuxième de type submit. Et si nous vous avons donné, en fait, plus ingrédients que vous aviez besoin, juste pour vous avez eu des options qui pour résoudre ce problème. Strictement Vous n'avez pas besoin l'ensemble de ces identifiants. Mais il vous permet de résoudre de différentes manières. Et au sommet, vous remarquerez que l'objectif était de déclencher une fenêtre comme celle-ci - Bonjour, Milo! - pour faire apparaître dans le navigateur à l'aide la super simple, si pas laid, fonction d'alerte. Et si, en fin de compte, cela revient conceptuellement à l'écoute d'une certaine manière pour observations du côté client de forme , Pas le côté serveur, en quelque sorte répondre à cette présentation par saisir la valeur que l'utilisateur a tapé dans le champ de nom, puis afficher dans le corps d'une alerte. 

Donc, d'une manière que vous pouvez faire est avec jQuery, qui ressemble un peu syntaxiquement perplexe au premier abord. Vous pouvez le faire avec le code de DOM pur - document.getelement par ID. Mais jetons un coup d'œil à cette version. J'ai un couple d'importance des premières lignes. Donc un, nous avons cette ligne, qui est identique à ce que vous pourriez avoir vu dans, je crois, form2.html de la classe en semaine 9. Et cela est en train de dire, exécuter le code suivant lors le document est prêt. Ceci étant importante seulement parce pages HTML sont lues de haut en bas, de gauche à droite. 

Et donc, si vous essayez de faire quelque chose dans le code ici à certains DOM élément, certaines balises HTML, qui est en baisse ici, vous le faites trop tôt, parce que cela a même pas lu dans la mémoire. Donc, en disant ce document.ready ligne, nous disons, Voici un peu de code, navigateur. Mais ne pas exécuter jusqu'à ce que l'ensemble le document est prêt, c'est-à-DOM arbre existe dans la mémoire. Celui-ci est un peu plus simple, si syntaxiquement un peu différente, où que je dis, grab l'élément HTML dont l'unique, identificateur est entrées. C'est ce que la balise de hachage désigne, l'ID unique. Et puis je vais appeler. Présenter. 

Donc. Présenter ici est une fonction, sinon connue comme une méthode, c'est l'intérieur de l'objet sur la main gauche côté il que je n'ai pas mis en évidence. Donc, si vous pensez que des intrants comme un objet dans la mémoire - et en effet il est. Il s'agit d'un noeud dans un arbre - . Présenter des moyens quand ce formulaire cet ID est soumis, exécuter le code suivant. Je n'aime pas ce que le nom de la fonction est je suis d'exécution. Donc ici, je suis en utilisant, comme avant, ce qui est appelle la fonction de lambda ou un fonction anonyme. Ce n'est pas du tout intellectuel intéressant autre que lui n'a pas de nom, ce qui est bien si vous êtes seulement jamais à l'appeler une fois. Et à l'intérieur, il fait je m'occupe la soumission du formulaire. Je déclare d'abord une variable appelé valeur. Et puis quel est l'effet de cette partie ici souligné maintenant? Qu'est-ce que cela à un de haut niveau pour moi? 

PUBLIC: Il obtient la valeur que le l'utilisateur n'a pas dans le code HTML ci-dessous. Il obtient que ID, puis trouve la valeur de celui-ci. 

DAVID J. Malan: Exactement. Il saisit le nœud dont uniques identificateur est le nom. Il obtient la valeur à l'intérieur, qui est, sans doute, ce que l'utilisateur lui-même tapé. Et puis il stocke que dans le variable nommée valeur. En passant, vous pourriez aussi avoir fait cela un peu différemment. Tout à fait acceptable en faisant quelque chose valeur mensonge var obtient document.getElementById. Et c'est pourquoi il est un peu pénible de ne pas utiliser jQuery. "Nom". Valeur. Donc, tout à fait acceptable. Différentes façons de le faire. jQuery juste a tendance à être un peu plus concis et plus certainement plus populaire parmi les programmeurs. 

Maintenant, je fais un peu de bon sens vérifier, parce que dans le problème déclaration que nous avons explicitement dit, si la utilisateur n'a pas encore tapé son nommer, ne montrent pas une alerte. Mais vous pouvez vérifier que, par tout la vérification de la chaîne vide pour un entre guillemets s'il ya rien fait là-bas. Mais si ce n'est pas égal à entre guillemets, Je veux appeler alertes. Et la partie intéressante ici est que nous utilisons l'opérateur de plus, qui fait quoi en JavaScript? Concaténer. Donc, c'est comme phps opérateur point. Même idée, syntaxe légèrement différente. Et je suis en train de créer la chaîne vous avez vu sur la capture d'écran - Bonjour, ceci et cela. 

Et puis le dernier détail est le suivant. Pourquoi dois-je retourner faux à l'intérieur de cette fonction anonyme? 

PUBLIC: Il n'y a pas de valeur. Vous mettez en forme. Il dit simplement, si la valeur n'est pas égal à blanc, puis le faire. Il y avait un vide dans cette communication. 

DAVID J. Malan: OK. Attention tout de même. Il n'y a personne d'autre ici. Et ce retour est faux en dehors de la si les conditions. Donc, cette ligne en surbrillance, return false, exécute n'importe quoi et quand le formulaire est soumis. Qu'est-ce que le retour de faux à l'intérieur de ce gestionnaire d'événements, comme on l'appelle, l'événement en question étant soumission? 

PUBLIC: Parce que ne se produit qu'une seule fois. 

DAVID J. Malan: arrive une seule fois. Pas tout à fait. Ouais? 

PUBLIC: Il empêche la forme de à soumettre le comportement par défaut, ce qui rendrait le rechargement de la page. 

DAVID J. Malan: Exactement. Je suis donc surcharger le terme présenter ici, parce que je veux dire, la forme est être soumis. Mais comme vous le suggérez, ce n'est pas vraiment été soumis dans le vrai chemin HTTP. Lorsque vous cliquez sur Soumettre, en raison de notre gestionnaire onSubmit, nous intercepter que la soumission du formulaire pour ainsi dire. Nous alors faire notre chose avec du code JavaScript. Mais je suis de retour délibérément fausse, parce que je ne veux pas passer une fraction de seconde plus tard, est pour l'ensemble forme lui-même pour être soumis à la web serveur avec des paires clé-valeur en changeant l'URL à être quelque chose comme q = chats ou tout ce que nous avons fait, par exemple, dans la classe. Je ne veux pas que cela se produise, car il n'y a pas d'écoute du serveur pour cette former soumission. C'est purement fait dans le code JavaScript. Et c'est pourquoi je n'ai même pas eu un attribut action sur ma forme, parce que je n'ont pas l'intention pour que cela jamais aller sur le serveur. 

Donc, il est soumis. Mais nous intercepter cette forme présentation et de prévenir la défaillance comportement, ce qui est en fait de aller tout le chemin vers le serveur. 

PUBLIC: Donc garder côté client. 

DAVID J. Malan: Garder il côté client. Exactement. Ensuite, ce fut mon oh MySQL. 

ROB BOWDEN: OK. Donc, cette première question était généralement rude pour les gens. Bien que les plus tardifs se sont mieux passées. Donc vous aviez à choisir les données correctes types pour ces deux colonnes. Et deux d'entre elles ont une certaine choses à leur sujet que faire le choix difficile. Alors int n'était pas valide tapez pour nombre. La raison d'être d'un compte à 12 chiffres nombre, un int n'est pas assez grand pour stocker chiffres totaux. Donc un choix valable aurait été un grand int si vous arrivez à le savoir. Un autre choix aurait pu être un champ char de longueur 12. Donc, soit de ceux qui auraient travaillé. Int serait pas. 

Maintenant, l'équilibre, penser à pset7. Nous avons donc utilisé spécifiquement décimal stocker la valeur des actions ou - 

DAVID J. Malan: Cash. 

ROB BOWDEN: Cash. Nous avons utilisé décimal pour stocker la quantité de espèces que l'utilisateur dispose actuellement. Donc, la raison pour laquelle nous faisons cela est parce que, rappelez-vous, les flotteurs. Il ya virgule flottante en précision. Il ne peut pas stocker précisément la trésorerie valeurs comme nous veulent ici. Donc décimal est en mesure de précision magasin quelque chose à, dire, deux décimales. C'est pourquoi l'équilibre, nous voulons être décimal et non pas flotter. 

DAVID J. Malan: Et aussi, trop, bien il aurait été intelligent dans d'autres contextes à penser, peut-être ce C'est une chance pour un int. Je vais garder la trace de choses dans centimes. Parce que nous avons montré explicitement la valeur par défaut La valeur de l'être 100,00, qui signifie qu'il pourrait juste être un int. Et une autre subtilité trop avec le nombre c'est qu'il n'a pas été conçu être une question piège. Mais rappeler qu'un int dans MySQL, comme dans C, au moins dans la appareil, est de 32 bits. Et même si nous ne nous attendons pas à vous savoir exactement combien de chiffres que moyens, ne me souviens que le plus grand nombre vous pouvez potentiellement représenter avec un nombre de 32 bits est à peu près quoi? 

Quel est le nombre ne nous dit toujours? 2 à 32, ce qui est plus ou moins? Vous n'avez pas à savoir précisément. Mais est plus ou moins utiles dans la vie. C'est à peu près 4 milliards. Donc, nous avons dit que quelques fois. Je sais que j'ai dit que quelques fois. Et c'est à peu près 4 milliards. Et c'est une bonne règle de pouce de savoir. Si vous avez 8 bits, 256 est le nombre magique. Si vous avez 32 bits, 4 milliards de donner ou prendre. Donc, si vous venez d'écrire en baisse de 4 milliards de dollars, vous verrez que c'est moins de chiffres que 12, ce qui signifie qu'il n'y a manifestement pas assez expressivité de capturer une Numéro de compte à 12 chiffres. 

ROB BOWDEN: OK. Alors les autres se sont mieux passées. Supposons donc que la banque impose un mensuel $ 20 frais d'entretien sur tous les comptes. Avec ce requête SQL pourrait la banque déduire 20 $ pour chaque chef d'accusation, même si il en résulte des soldes négatifs? Donc, fondamentalement, il ya quatre principaux types de requêtes - insérer, sélectionnez, update et delete. Alors qu'est-ce que nous pensons que nous sommes allons utiliser ici? Mettre à jour. 

Donc, nous allons jeter un coup d'oeil. Donc, ici, nous mettons à jour. Qu'est-ce que la table-on à jour les comptes? Donc, la mise à jour des comptes. Et puis la syntaxe dit, ce dans les comptes à jour sommes-nous? Eh bien, nous de régler la balance égale à la valeur actuelle de l'équilibre moins 20. Donc, ce sera jour toutes les lignes des comptes, en soustrayant 20 $ l'équilibre. 

DAVID J. Malan: Une erreur courante ici, même si nous avons parfois pardonné il, était d'avoir fait du code PHP ici appel de la fonction de recherche ou la mise guillemets autour de tout ce qui n'ont pas besoin d'être là. 

ROB BOWDEN: N'oubliez pas que MySQL est une langue distincte du PHP. Il nous arrive d'écrire MySQL en PHP. Et PHP est alors de l'envoyer sur le serveur MySQL. Mais vous n'avez pas besoin de PHP afin de communiquer avec un serveur MySQL. 

DAVID J. Malan: Exactement. Donc pas de variables avec des signes de dollar devrait être dans ce contexte. Il peut juste faire tous les calculs à l'intérieur de la base de données elle-même. 

ROB BOWDEN: OK. Donc, la suivante. Est-ce le prochain? Ouais. Donc, avec ce que la requête SQL pourrait la banque récupérer les numéros de compte de sa riches clients, ceux qui soldes de plus de 1000? Alors, qui des quatre principaux types allons-nous faire ici? Sélectionnez. Donc, nous voulons sélectionner. Que voulons-nous pour choisir? Qu'est-ce que la colonne voulons-nous pour sélectionner? Nous voulons en particulier pour sélectionner le numéro. Mais si vous dites étoiles, nous également accepté. 

Donc, sélectionner le numéro de ce tableau? Comptes. Et puis la condition que nous voulons? Où solde supérieur à 1000. Nous avons également accepté une plus grande ou égal. Dernier. Avec ce requête SQL pourrait la banque près, c'est-à supprimer tous les comptes que a un solde de 0 $? Alors, qui des quatre sommes-nous allez vouloir utiliser? Supprimer. Donc, la syntaxe pour cela? Supprimer de ce tableau? Comptes. Et puis la condition à laquelle nous voulons supprimer - où l'équilibre est égal à zéro. Donc, supprimer toutes les lignes de comptes où le solde est nul. Questions sur l'un de ces? Vous voulez faire la queue? 

DAVID J. Malan: guide de la file d'attente. Ainsi, dans celui-ci, nous vous avons donné un peu structure familière que nous avons exploré une peu dans la classe à côté de structures, qui était une des données structure apparentée dans l'esprit. La différence mais avec une file d'attente est que nous avons dû rappeler en quelque sorte qui était à l'avant de la file d'attente, dans une large partie afin que nous puissions faire plus l'utilisation efficace de la mémoire, au moins si nous utilisions un tableau. 

Parce que le rappel, si nous avons un tableau, si, par exemple, c'est la face d' la file d'attente, si je reçois dans la file d'attente ici, et puis quelqu'un se met en ligne derrière moi, derrière moi, derrière moi, et une personne sort de la ligne, vous pourrait, comme nous l'avons vu certains de nos ressources humaines bénévoles en classe, ont tous passer de cette façon. Mais en général, ayant chacun faire quelque chose n'est pas la meilleure utilisation du temps dans un programme, car il signifie que votre algorithme est en cours dans ce asymptotique temps de fonctionnement? Il est linéaire. 

Et je me sens comme c'est un peu stupide. Si la personne suivante dans la ligne est la suivante personne qui est censé aller dans le magasin, ils n'ont pas tous à se déplacer ensemble. Laissez cette personne soit arrachée lorsque vient le temps, par exemple. Donc, nous pouvons économiser un peu de temps. Et de le faire que si, que des moyens que la tête de la file d'attente ou le avant de la file d'attente va passer progressivement plus profondément dans le tableau et finalement pourrait effectivement s'enrouler autour si nous utilisons une tableau pour stocker les gens dans cette file d'attente. Ainsi, vous pouvez presque penser à la tableau en tant que données circulaire la structure en ce sens. 

Donc, vous avez en quelque sorte à garder une trace de l' taille de celui-ci ou bien la fin de celui-ci et alors, où le début de celui-ci est. Nous proposons donc que vous déclarez une telle file d'attente, les appels il q, une seule lettre. Ensuite, nous proposons que l'avant soit initialisé à zéro et que la taille être initialisé à zéro. 

Donc maintenant, il n'y a rien à l'intérieur de cette file d'attente. Et nous vous demandons de compléter le mise en oeuvre de enqueue en dessous de telle sorte que la fonction ajoute au n la fin de q et retourne vrai. Mais si q est plein ou négatif, le fonction devrait plutôt retourner false. Et nous vous avons donné quelques d'hypothèses. Mais ils ne sont pas vraiment fonctionnel pertinente, c'est juste que bool existe, parce que, techniquement, bool ne exister dans C sauf si vous incluez une certain fichier d'en-tête. Donc ça a été juste assurez-vous qu'il ont pas est-ce un truc question genre de chose. 

Donc enqueue, nous avons proposé dans l'échantillon solutions à mettre en œuvre comme suit. Un, nous vérifions d'abord la facilité, les fruits mûrs. Si la file d'attente est pleine ou que le nombre vous essayez d'insérer est moins à zéro, qui nous dit dans le spécification du problème devrait pas être autorisé, parce que nous voulons que des valeurs non négatives, alors vous devriez juste return false immédiatement. Ainsi, certains relativement facile Vérification des erreurs. Si si vous voulez ajouter que réelle nombre, vous avez eu à faire un peu de penser ici. Et c'est là que c'est un peu ennuyeux mentalement, parce que vous devez comprendre comment gérer enveloppant. 

Mais le germe de l'idée ici c'est de intérêt pour nous est que enveloppant implique souvent une arithmétique modulaire et l'opérateur mod, du côté de pour cent, où vous pouvez passer d'une valeur supérieure à zéro, puis un et deux et trois, puis retourna à zéro, un et deux et trois, et ainsi de suite encore et encore. Donc, la façon dont nous proposons de faire est que nous ne voulons index dans la tableau appelé numéros où nos entiers se trouvent. Mais pour y parvenir, nous voulons d'abord faire quelle que soit la taille de la file d'attente n'est que puis ajouter à ce quelle que soit la avant de la liste est. Et l'effet de tout cela est de nous mettre à la bonne position dans la file d'attente et pas supposer que la première personne en ligne est, au début, qu'il ou elle pourrait absolument être si nous ont également déplacer tout le monde. Mais nous sommes en train de créer des emplois pour nous-mêmes si nous avons pris ce chemin particulier. 

Donc, nous pouvons garder relativement simple. Nous ne devons pas oublier que nous venons de ajouter un int à la file d'attente. Et puis nous retournons juste vrai. Pendant ce temps, dans dequeue, nous avons demandé vous effectuez les opérations suivantes. Mettre en oeuvre de telle manière qu'elle dequeues, c'est Supprime et renvoie, l'int à l'avant de la file d'attente. Pour supprimer l'int, il suffit à l'oublier. Vous n'avez pas besoin de remplacer son bit. C'est donc encore vraiment là. Tout comme les données sur un disque dur, nous sommes juste en ignorant le fait qu'il est maintenant là. Et si q est vide, nous devons au lieu de retour négatif 1. Donc, cela se sent arbitraire. Pourquoi revenir négatif 1 au lieu de faux? Ouais. 

PUBLIC: Q est le stockage des valeurs positives. Puisque vous ne stockez des valeurs positives dans le q, négative est une erreur. 

DAVID J. Malan: OK, c'est vrai. Donc, parce que nous ne faisons que le stockage positif valeurs ou zéro, alors il est bien de retourner une valeur négative comme une sentinelle valeur, un symbole spécial. Mais vous réécrire l'histoire là, parce que la raison pour laquelle nous ne sommes que retour des valeurs non négatives c'est parce que nous voulons avoir une valeur de sentinelle. Donc, plus précisément, pourquoi ne pas simplement return false en cas d'erreur? Ouais. 

PUBLIC: Vous avez échoué à retourner un entier. 

DAVID J. Malan: Exactement. Et c'est là que C se assez contraignant. Si vous dites que vous allez pour renvoyer un int, vous avez pour retourner un int. Vous ne pouvez pas obtenir la fantaisie et commence à retourner un bool ou un flotteur ou une chaîne ou quelque chose comme ça. Maintenant, quant à lui, JavaScript et PHP et d'autres langues peuvent, en fait, avez-vous le retour différente types de valeurs. Et cela peut effectivement être utile, où vous pouvez retourner ints positifs, des zéros, ints négatifs ou faux ou nul pour signifier la même erreur. Mais nous n'avons pas cette polyvalence en C. 

Donc, avec dequeue, ce que nous proposer de faire est - 

ROB BOWDEN: Vous pouvez retourner false. C'est juste que le faux est hachage définir fausse à zéro. Donc, si vous retournez false, vous êtes de retour à zéro. Et le zéro est une chose valable dans notre file d'attente, alors négatif 1 n'est pas si faux qui est arrivé à être négative 1. Mais vous ne devriez pas même besoin de savoir que. 

DAVID J. Malan: C'est pourquoi je n'ai pas dit. 

ROB BOWDEN: Mais ce n'était pas vrai que vous ne pouvez pas retourner false. 

DAVID J. Malan: Bien sûr. Donc dequeue, remarquons que nous acceptons annuler comme argument. Et c'est parce que nous ne sommes pas tout en passant po Nous voulons juste enlever l'élément à l'avant de la file d'attente. Alors, comment pourrions-nous faire pour cela? Eh bien, d'abord, nous allons le faire test de cohérence rapide. Si la taille de la file d'attente est 0, il n'y a pas de travail à faire. Retour négative 1. Terminé. Voilà donc quelques lignes de mon programme. Alors que quatre lignes restent. 

Donc ici, je décide de diminuer la taille. Et la décrémentation de la taille effective signifie que j'oublie quelque chose est là. Mais je dois également mettre à jour où l'avant de les nombres sont. Donc, pour ce faire, j'ai besoin de faire deux choses. Je dois d'abord rappeler ce que le nombre est à l'avant de la file d'attente, parce que j'ai besoin de retourner cette chose. Donc, je ne veux pas oublier accidentellement à ce sujet, puis l'écraser. Je vais juste vous rappeler dans un int. 

Et maintenant, je veux mettre à jour q.front à q.front 1. Donc, si cela était la première personne à ligne, maintenant, je veux faire plus 1 à signaler à la personne suivante. Mais je dois gérer que enveloppant. Et si la capacité est une constante globale, cela va me permettre de m'assurer comme je le signale à la dernière personne à La ligne, l'opération de modulo apportera me remis à zéro à la avant de la file d'attente. Et qui gère l'enveloppant ici. Et puis je passe à retourner n. 

Maintenant, à proprement parler, je n'ai pas avoir à déclarer n. Je n'ai pas eu à le saisir et de le stocker temporairement, parce que la valeur est toujours là. Donc, je ne pouvais tout simplement faire la bonne arithmétique de renvoyer l'ancien chef de la file d'attente. Mais je me suis senti que c'était plus clair pour réellement saisir l'int, mettre n, et revenir ensuite que pour plus de clarté, mais pas strictement nécessaire. Psst. Ils sont tous prononçable dans ma tête. 

ROB BOWDEN: Donc première question est le problème de l'arbre binaire. Donc première question est, nous sommes Compte tenu de ces chiffres. Et nous voulons les insérer en quelque sorte dans ces noeuds de telle sorte qu'il est un valide arbre binaire de recherche. Donc la seule chose à retenir sur arbres binaires de recherche, c'est que ce n'est pas simplement que la chose à la gauche est inférieure à la chose et le droit est plus grande. Il doit être que la totalité de l'arbre à la gauche est inférieure, et la totalité de l'arbre vers la droite est plus grande. 

Donc, si je mets 34 ici en haut, puis J'ai mis 20 ici, donc c'est valable si loin, car 34 ici. 20 va à gauche. C'est donc moins. Mais je ne peux donc pas mettre 59 ici, parce même si 59 est sur la droite de 20, il est toujours sur la gauche de 34. Donc, avec cette contrainte à l'esprit, le meilleure façon de résoudre ce probablement problème est de quelque sorte de ces chiffres - si 20, 34, 36, 52, 59, 106. Et puis insérez les de gauche à droite. 

Donc 20 va ici. 34 Il en va ici. 36 Il en va ici. 52, 59, 106. Et vous pourriez également avoir compris avec certains de brancher et de réaliser, oh, attendez, je n'ai pas assez de numéros pour combler ce dans plus ici. J'ai donc besoin de reshift ce que mon itinéraire note va être. Mais remarquez que dans les trois derniers, si vous lisez de gauche à droite, il est en ordre croissant. 

Alors maintenant, nous voulons déclarer que la struct va être pour la noeuds de cet arbre. Alors que devons-nous en un arbre binaire? Nous avons donc une valeur de type int, donc une certaine valeur int. Je ne sais pas ce que nous appelions dans la solution - int n. Nous avons besoin d'un pointeur à l'enfant gauche et un pointeur vers la droite enfant. Donc ça va ressembler à ceci. Et il va effectivement regarder avant Quand le doublement chaînée liste des trucs, donc avis - Je vais avoir à faire défiler tous les En redescendant à problème 11. 

Alors notez qu'il semble identique à cela, sauf nous arrive juste à appeler ces des noms différents. Nous avons encore un nombre entier valeur et de deux pointeurs. C'est juste que, au lieu de traiter le pointeurs comme pointant à la chose suivante et la chose précédente, nous allons traiter les pointeurs pour pointer vers un enfant gauche et droit de l'enfant. OK. C'est donc notre nœud de structure. Et maintenant, la seule fonction nous devons mettre en œuvre en est traversée, qui nous voulons aller sur l'arbre, l'impression les valeurs de l'arbre de commande. 

Donc, en regardant ici, nous voudrions imprimer rupture 20, 34, 36, 52, 59, et 106. Comment nous accomplissons cela? Il est donc assez similaire. Si vous avez vu dans l'examen passé le problème que vous vouliez imprimer l'arbre entier avec des virgules entre les tout, il était en fait même plus facile que cela. Donc, voici la solution. Ceci est significativement plus facile si vous l'avez fait de manière récursive. Je ne sais pas si quelqu'un a tenté de le faire de manière itérative. 

Mais d'abord, nous avons notre scénario de base. Que faire si la racine est nulle? Ensuite, nous allons simplement revenir. Nous ne voulons pas d'imprimer quoi que ce soit. Sinon nous allons traverser récursive vers le bas. Imprimer le sous-arbre entier gauche. Donc tout imprimer moins que ma valeur actuelle. Et puis je vais me imprimer. Et puis je vais sur mon récursion sous-arbre entier droite, donc tout plus grande que ma valeur. Et cela va imprimer sur tout dans l'ordre. Questions sur la façon dont ce fait accomplit cela? 

PUBLIC: J'ai une question sur la [inaudible]. 

ROB BOWDEN: Donc, une façon d'aborder un problème récurrent est de penser juste à ce sujet comme vous devez penser sur tous les cas de coin. Donc, considérons que nous voulons imprimer ensemble cet arbre. Donc, tout ce que nous allons mettre l'accent sur est ce nœud particulier - 36. Les appels récursifs, nous semblant ceux qui travaillent juste. Donc, ici, cet appel récursif à traversée, nous sans même y penser à ce sujet, il suffit de traverser la gauche trois, imaginer qui imprime déjà 20 et 34 pour nous. Et puis, quand on a fini de manière récursive appeler déplacement sur la droite, qui va imprimer correctement 52, 59, et 106 pour nous. 

Donc, étant donné que cela peut imprimer 20, 34, et l'autre peut imprimer 52, 59, 108, tout ce que nous devons être en mesure de faire est d'imprimer nous-mêmes au milieu de cela. Donc imprimer tout avant nous. Imprimer soi-même, de sorte que l'impression de noeud courant 36, printf régulière, puis imprimer tout de nous. 

DAVID J. Malan: C'est là que la récursivité devient vraiment beau. C'est ce saut incroyable de foi où vous faites tout petit peu de travail. Et puis vous laissez quelqu'un d'autre faire le reste. Et que quelqu'un d'autre est, ironiquement, vous. Donc, pour les bons points graves, si défiler vers le haut sur les questions - 

ROB BOWDEN: Sur les questions? 

DAVID J. Malan: Et en bas un peu à les chiffres, personne ne sait où viennent ces chiffres? 

ROB BOWDEN: J'ai littéralement aucune idée. 

DAVID J. Malan: Ils apparaissent tout au long du questionnaire. 

PUBLIC: Sont-ils les mêmes numéros? 

DAVID J. Malan: Ces chiffres. Un petit oeuf de Pâques. Donc, pour ceux d'entre vous regarder en ligne à la maison, si vous pouvez nous dire par courriel à heads@CS50.net ce que l'importance de ces six nombres récurrents sont tout au long de Quiz 1, nous vous douche avec une attention spéciale à la finale conférence et une balle anti-stress. Nice, subtil. 

ROB BOWDEN: Les dernières questions sur quoi que ce soit sur le quiz?