>> 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?