[Powered by Google Translate] [Semaine 6, suite]
[David J. Malan] [Université de Harvard]
[C'est CS50.] [CS50.TV]
C'est CS50 et c'est la fin de la semaine 6.
Donc CS50x, l'un des premiers cours de Harvard impliqués dans l'initiative EDX
en effet débuté lundi dernier.
Si vous souhaitez avoir un aperçu de ce que d'autres sur l'Internet
suivent désormais avec, vous pouvez vous diriger vers x.cs50.net.
Cela vous redirigera vers l'endroit approprié sur edx.org,
ce qui était le cas cela et d'autres cours du MIT et Berkeley vivons aujourd'hui.
Vous devez vous inscrire pour un compte, vous verrez que le matériau est sensiblement le même
que vous avez eu ce semestre, bien que quelques semaines retardés, comme nous l'avons tout préparer.
Mais ce que les élèves CS50x allons voir maintenant est une interface tout à fait comme celui-ci.
C'est, par exemple, est le leader Zamyla procédure pas à pas pour 0 problème posé.
Lors de la connexion à edx.org, un étudiant CS50x voit le genre de choses
vous vous attendez à voir dans un cours: la conférence pour le Lundi,
conférence pour le mercredi, shorts divers, les ensembles de problèmes, les soluces, les fichiers PDF.
En outre, comme vous le voyez ici des traductions automatiques,
des transcriptions anglaises en chinois, japonais, espagnol, italien,
et tout un tas d'autres langues qui sera certainement imparfaite
comme nous les déployer par programmation en utilisant ce qu'on appelle une API,
ou de l'interface de programmation d'application, à partir de Google
qui nous permet de convertir l'anglais vers d'autres langues.
Mais grâce à la formidable esprit de certains bénévoles, plus de cent,
des gens au hasard sur l'Internet qui ont aimablement offert de s'impliquer
dans ce projet, nous allons progressivement améliorer la qualité de ces traductions
en ayant humains corriger les erreurs que nos ordinateurs ont fait.
>> Ainsi, il s'avère que nous avions quelques élèves plus se présenter le lundi que nous avons prévu initialement.
En fait, maintenant CS50x compte 100.000 personnes suivantes long à la maison.
Alors réalisez que vous êtes tous partie de cette classe inaugurale de faire ce cours en informatique
l'éducation en général, plus largement, accessible.
Et la réalité est aujourd'hui, avec certains de ces cours en ligne massivement,
ils commencent tous ces chiffres très élevés, comme il semble que nous avons fait ici.
Mais l'objectif, à terme, pour CS50x est vraiment d'amener les gens autant à la ligne d'arrivée le plus possible.
De par sa conception, CS50x va être offert à partir de ce lundi
tout au long de Avril 15, 2013, de sorte que les gens qui ont pris des engagements scolaires ailleurs,
travail, famille, d'autres conflits et autres, ont un peu plus de flexibilité
avec laquelle se plonger dans ce cours, qui, il suffit de dire,
est assez ambitieuse faire si ce n'est au cours des trois mois pendant un semestre d'habitude.
Mais ces étudiants seront la lutte contre les jeux même problème, l'affichage du contenu même,
l'accès à des courts-circuits identiques et similaires.
Donc rendons compte que nous sommes tous dans le même bateau vraiment.
Et l'un des objectifs ultimes de CS50x n'est pas juste pour les gens que de nombreux
à la ligne d'arrivée et de leur donner cette nouvelle compréhension de l'informatique
et de la programmation, mais aussi de les faire vivre cette expérience partagée.
L'une des caractéristiques déterminantes de 50 sur le campus, nous l'espérons,
a été ce genre d'expérience commune, pour le meilleur ou pour le pire, parfois,
mais comportant ces personnes de se tourner vers la gauche et vers la droite,
les heures de bureau et et le Hackathon et la foire.
C'est un peu plus difficile à faire que les gens en personne en ligne,
mais CS50x se terminera en Avril avec la première CS50 Expo,
qui sera une adaptation en ligne de notre idée de la foire
où ces milliers d'étudiants seront tous invités à soumettre un 1 - à 2 minutes de vidéo,
soit un screencast de leur projet final ou une vidéo d'eux en agitant bonjour
et de parler de leur projet et faire des démonstrations,
tout comme vos prédécesseurs l'ont fait ici sur le campus à la foire,
de sorte qu'à la fin de semestre, l'espoir est d'avoir une exposition mondiale
projets des étudiants CS50x »final, un peu comme ce qui vous attend en Décembre sur le campus.
Donc plus à ce sujet dans les mois à venir.
>> Avec 100.000 étudiants, cependant, est un besoin pour un peu plus de CA.
Étant donné que vous les gars sont ici ouvre la voie et de prendre CS50
plusieurs semaines à l'avance de la libération de cette matière à des gens sur EDX,
rendons compte que nous aimerions faire participer le plus grand nombre de nos propres étudiants que possible à cette initiative,
à la fois au cours du semestre ainsi que cet hiver et ce printemps.
Donc, si vous souhaitez vous impliquer dans CS50x,
notamment en joignant le CS50x Discuter, la version de EDX CS50 discuter,
beaucoup d'entre vous ont utilisé sur le campus, le tableau d'affichage en ligne,
s'il vous plaît ne la tête à cette URL, laissez-nous savoir qui vous êtes,
parce que nous aimerions mettre en place une équipe d'étudiants et du personnel et du corps professoral aussi bien
sur le campus qui sont tout simplement jouer le jeu et un coup de main.
Et quand ils voient une question qui est familier,
ce que vous entendiez un étudiant de rapports d'un bug quelque part là-bas dans certains pays sur l'Internet,
et que sonne une cloche parce que vous aussi eu ce même problème
dans votre salle d-il ya quelque temps, je l'espère, vous pouvez carillon et partager votre propre expérience.
Alors s'il vous plaît partager si vous le souhaitez.
>> Cours d'informatique à l'Université Harvard ont un peu une tradition,
CS50 parmi eux, d'avoir une certaine vêtements, des vêtements, que vous pouvez porter avec fierté
à la fin de semestre, en disant assez fièrement que vous avez terminé CS50
et a pris CS50 et autres, et nous essayons toujours de faire participer les élèves
dans ce processus autant que possible, par lequel nous inviter,
à cette époque de l'semestre, les étudiants à présenter des projets
l'aide de Photoshop, ou tout autre outil de choix que vous souhaitez utiliser
si vous êtes un designer, à présenter des projets pour les T-shirts et sweat-shirts
et des parasols et des bandanas pour chiens petits, nous avons maintenant et ainsi de suite.
Et tout est alors - les lauréats chaque année sont ensuite exposées
sur le site Web du cours à store.cs50.net.
Tout est vendu au prix coûtant, mais le site fonctionne tout simplement lui-même
et permet aux gens de choisir les couleurs et les dessins qu'ils aiment.
J'ai donc pensé que nous venions de partager quelques-unes des conceptions de l'an dernier
qui étaient sur le site en plus de celui-là, qui est une tradition annuelle.
"Chaque jour je Seg Faultn" était l'un des soumissions année dernière,
qui est toujours disponible là-bas pour les anciens.
Nous avons eu celui-ci, "CS50, Established 1989».
Un de nos Bowdens, Rob, était très populaire l'an dernier.
"L'équipe Bowden" est né, cette conception a été présenté, parmi les meilleurs vendeurs.
Comme ce fut celui-là. Beaucoup de gens avaient "Fever Bowden", selon les journaux de vente.
Sachez que ce que pourrait maintenant être votre conception là-bas, sur l'Internet.
Plus de détails à ce sujet dans le prochain problème établit à venir.
>> Un outil de plus: vous avez eu une certaine exposition et nous espérons maintenant
une certaine expérience pratique avec GDB,
qui est, bien sûr, un débogueur et vous permet de manipuler
votre programme à un niveau assez bas, en faisant ce genre de choses?
Qu'est-ce que GDB vous laisser faire?
Ouais? Donne-moi quelque chose. [Réponse de l'étudiant, inintelligible]
Bon. Entrez dans la fonction, de sorte que vous n'avez pas seulement pour saisir run
et avoir le coup programme à travers son intégralité, l'impression des choses sur la sortie standard.
Au contraire, vous pouvez faire défiler ligne par ligne, soit en tapant prochaine
aller ligne par ligne par ligne ou pas à plonger dans une fonction, généralement celui qui vous écrit.
Quels sont les autres GDB vous laisser faire? Ouais? [Réponse de l'étudiant, inintelligible]
Imprimer variables. Donc, si vous voulez faire un peu d'introspection à l'intérieur de votre programme
sans avoir à recourir à l'écriture d'instructions printf un peu partout,
il vous suffit d'imprimer une variable ou d'afficher une variable.
Que pouvez-vous faire avec un débogueur GDB comme?
[Réponse de l'étudiant, inintelligible]
Exactement. Vous pouvez définir des points d'arrêt, vous pouvez dire l'exécution pause
à la fonction principale ou la fonction foo.
Vous pouvez dire que l'exécution pause à la ligne 123.
Et les points d'arrêt sont une technique très puissante
parce que si vous avez une idée générale de l'endroit où votre problème
est probablement, vous n'avez pas à perdre du temps parcourant intégralité du programme.
Vous pouvez sauter à droite essentiellement là-bas et puis commencez à taper -
pas à pas à travers elle à l'étape suivante ou ou analogue.
Mais le hic avec quelque chose comme GDB est qu'il vous aide, les ressources humaines,
trouver vos problèmes et trouver des bugs.
Elle ne trouvent pas nécessairement leur beaucoup pour vous.
>> Donc, nous avons introduit le style50 autre jour, qui est un outil de commande en ligne à court
qui tente de styliser votre code un peu plus propre que toi, l'être humain, pourrait avoir fait.
Mais ça aussi, c'est vraiment juste une chose esthétique.
Mais il s'avère qu'il ya cette autre outil appelé Valgrind qui est un peu plus obscure à utiliser.
Sa sortie est atrocement énigmatique au premier abord.
Mais il est merveilleusement utile, surtout maintenant que nous sommes dans la partie de l'expression
où vous commencez à utiliser malloc et allocation dynamique de mémoire.
Les choses peuvent aller très, très mal rapidement.
Parce que si vous oubliez de libérer votre mémoire, ou vous déréférencez certains pointeur NULL,
ou vous déréférencez certains pointeur de déchets, ce qui est généralement le symptôme que les résultats?
Seg faute. Et vous obtenez ce fichier de base un certain nombre de kilo-octets ou méga-octets
qui représente l'état de la mémoire de votre programme quand il s'est écrasé,
mais votre programme en fin de compte seg défauts, faute de segmentation,
ce qui signifie que quelque chose de mauvais s'est produit presque toujours liés
d'une erreur liée à la mémoire que vous avez fait quelque part.
Donc Valgrind vous aide à trouver des choses comme ça.
C'est un outil que vous exécutez, comme GDB, une fois que vous avez compilé votre programme,
mais plutôt que d'exécuter votre programme directement, vous exécutez Valgrind
et vous lui passez votre programme, comme vous le faites avec GDB.
Maintenant, l'utilisation, pour obtenir le meilleur type de sortie,
est un peu long, donc là au sommet de l'écran, vous verrez Valgrind-v.
"-V" signifie verbose presque universellement lorsque vous utilisez des programmes sur un ordinateur Linux.
Donc, cela signifie cracher plus de données que vous pourriez par défaut.
»- Fuite-check = plein." Ceci est juste que chèque de toutes les fuites de mémoire possibles,
erreurs que j'ai pu réaliser. Cela, aussi, est un paradigme commun avec des programmes Linux.
En règle générale, si vous avez un argument de ligne de commande qui est un "switch",
qui est censé modifier le comportement du programme, et c'est une seule lettre,
c'est-v, mais si ça marche, tout simplement par la conception du programmeur,
est un mot entier ou une série de mots, l'argument de ligne de commande commence par -.
Ce ne sont que des conventions de l'homme, mais vous les verrez de plus en plus.
Et puis, enfin, «a.out» est le nom arbitraire pour le programme dans cet exemple particulier.
Et voici quelques sorties représentant.
>> Avant de nous pencher sur ce que cela signifie, permettez-moi de passer à un extrait de code ici.
Et laissez-moi passer ce hors de la voie, bientôt,
et nous allons jeter un coup d'oeil à memory.c, qui est ce petit exemple ici.
Donc, dans ce programme, permettez-moi de faire un zoom sur les fonctions et les questions.
Nous avons une fonction principale qui appelle une fonction, f,
et puis qu'est-ce que f procédez à faire, en anglais un peu technique?
Qu'est-ce que f procéder à faire?
Que diriez-vous, je vais commencer par la ligne 20, et l'emplacement de l'étoile n'a pas d'importance,
mais je vais être compatible avec les dernière conférence ici.
Quelle est la ligne 20 ne pour nous? Sur le côté gauche. Nous allons le décomposer davantage.
Int * x: qu'est-ce que ça fait?
D'accord. Il a déclarer un pointeur, et maintenant nous allons être encore plus technique.
Qu'est-ce que ça veut dire, très concrètement, pour déclarer un pointeur? Quelqu'un d'autre?
Ouais? [Réponse de l'étudiant, inintelligible] Trop loin.
Alors que vous lisez à la droite du signe égal.
Concentrons-nous juste sur la gauche, juste sur int * x.
Cela ne "déclarer" un pointeur, mais maintenant, nous allons plonger plus profondément à cette définition.
Qu'est-ce que concrètement, techniquement veut dire? Ouais?
[Réponse de l'étudiant, inintelligible]
D'accord. Il se prépare à enregistrer une adresse dans la mémoire.
Bon. Et nous allons prendre un peu plus loin, c'est la déclaration d'une variable, x, c'est 32 bits.
Et je sais que c'est parce que les 32 bits -?
Ce n'est pas parce que c'est un int, parce que c'est un pointeur dans ce cas.
Un hasard si c'est une seule et même chose avec un int,
mais le fait qu'il ya l'étoile il signifie qu'il s'agit d'un pointeur
et dans l'appareil, comme avec de nombreux ordinateurs, mais pas tous, les pointeurs sont 32 bits.
Le matériel plus moderne comme les derniers Mac, les PC dernière génération, vous pourriez avoir des pointeurs 64 bits,
mais dans l'appareil, ces choses sont de 32 bits.
Donc, nous allons normaliser sur ce point. Plus concrètement, l'histoire se déroule comme suit:
Nous "déclarer" un pointeur, ça veut dire quoi?
Nous nous préparons à stocker une adresse mémoire.
Qu'est-ce que ça veut dire?
Nous créons une variable appelée x qui prend 32 bits
qui sera bientôt stocker l'adresse d'un entier.
Et c'est probablement à peu près aussi précis que nous pouvons obtenir.
C'est très bien aller de l'avant afin de simplifier le monde et je dis juste déclarer un pointeur appelé x.
Déclarer un pointeur, mais se rendre compte et de comprendre ce qui se passe réellement
même dans ces quelques rares personnages.
>> Maintenant, celui-ci est presque un peu plus facile, même si c'est une expression plus longue.
Donc, ce qui est ce que ça fait, ça a souligné aujourd'hui: «malloc (10 * sizeof (int));" Ouais?
[Réponse de l'étudiant, inintelligible]
Bon. Et je vais le prendre là-bas. C'est allocation d'un bloc de mémoire pour dix entiers.
Et maintenant, nous allons plonger dans un peu plus profond, c'est l'attribution d'un bloc de mémoire pour dix entiers.
Quel est alors le retour de malloc?
L'adresse de ce morceau, ou, plus concrètement, l'adresse du premier octet de ce morceau.
Comment alors que je suis, le programmeur, de savoir où ce morceau de mémoire doit se terminer?
Je sais que c'est contigus. Malloc, par définition, vous donnera un espace contigu de mémoire.
Aucune lacune en elle. Vous avez accès à tous les octets dans ce morceau,
dos à dos à dos, mais comment puis-je savoir où la fin de ce morceau de mémoire est?
Lorsque vous utilisez malloc? [Réponse de l'étudiant, inintelligible] Bon.
Vous n'avez pas. Vous devez vous rappeler.
Je dois me rappeler que j'ai utilisé la valeur 10, et je ne semble même pas avoir fait ici.
Mais le fardeau de la preuve repose entièrement sur moi. Strlen, que nous sommes devenus un peu tributaire des chaînes,
fonctionne uniquement en raison de cette convention d'avoir \ 0
ou ce caractère spécial nul, NUL, à la fin d'une chaîne.
Cela ne tient pas seulement pour les morceaux arbitraires de la mémoire.
C'est à vous. Ainsi, la ligne 20, puis, alloue un bloc de mémoire
qui peut stocker des dix nombres entiers, et elle stocke l'adresse du premier octet
de ce bloc de mémoire de la variable x appelé.
Ergo, qui est un pointeur. Ainsi, la ligne 21, malheureusement, c'était une erreur.
Mais tout d'abord, que fait-il? Elle dit magasin à l'emplacement 10, 0 indexées,
du morceau de la mémoire appelée x la valeur 0.
>> Donc remarquer un certain nombre de choses sont en cours.
Même si x est un pointeur, rappelle il ya quelques semaines
que vous pouvez toujours utiliser la notation de tableau de style carré support.
Parce que c'est en fait l'abréviation main notation pour l'arithmétique des pointeurs plus cryptique l'avenir.
où l'on ferait quelque chose comme ceci: Prenez l'adresse x, se déplacer de 10 points au-dessus de,
puis aller à ce que l'adresse est stockée à cet emplacement.
Mais franchement, c'est juste atroce à lire et se familiariser avec.
Ainsi, le monde utilise généralement les crochets juste parce que c'est tellement plus humain-amical à lire.
Mais c'est ce qui se passe vraiment sous le capot;
x est une adresse, pas un tableau en soi.
Donc, ce n'est stockage 0 à l'emplacement 10 dans x.
Pourquoi est-ce mauvais? Ouais?
[Réponse de l'étudiant, inintelligible] Exactement.
Nous avons seulement attribuer dix entiers, mais nous comptons de 0 lors de la programmation en C,
si vous avez accès à 0 10 1 2 3 4 5 6 7 8 9 mais non.
Alors, soit le programme va à la faute segment ou il n'est pas.
Mais nous ne savons pas vraiment, ce qui est une sorte de comportement non déterministe.
Cela dépend vraiment de savoir si nous sommes chanceux.
S'il s'avère que le système d'exploitation ne me dérange pas si je utiliser cet octet supplémentaire,
même si elle ne l'a pas donné à moi, mon programme pourrait ne pas tomber en panne.
Il est brut, c'est buggé, mais vous ne pourriez pas voir ce symptôme,
ou vous pouvez le voir seulement de temps en temps.
Mais la réalité est que le bogue est, en fait, là-bas.
Et c'est vraiment un problème si vous avez écrit un programme qui vous voulez être correcte,
que vous avez vendu le programme que les gens utilisent que chaque de temps en temps se bloque
parce que, bien sûr, ce n'est pas bon. En fait, si vous avez un téléphone Android ou un iPhone
et vous télécharger des applications de nos jours, si vous avez déjà eu une application tout simplement arrêter,
tout d'un coup il disparaît, c'est presque toujours le résultat d'un problème lié à la mémoire,
où le programmeur foutu et un pointeur déréférencé
qu'il ou elle ne devrait pas avoir, et le résultat de l'iOS ou Android est juste de tuer le programme tout à fait
plutôt que le comportement est indéterminé risque ou une sorte de compromis de sécurité.
>> Il ya un autre bug dans ce programme en plus de celui-ci.
Qu'ai-je raté dans ce programme?
Je n'ai pas pratiqué ce que j'ai prêché. Ouais?
[Réponse de l'étudiant, inintelligible] Bon.
Je n'ai pas libéré de la mémoire. Donc, la règle d'or maintenant
doit être à tout moment vous appeler malloc, vous devez appeler gratuitement lorsque vous avez fini d'utiliser cette mémoire.
Maintenant, quand devrais-je libérer cette mémoire?
Probablement, en supposant que cette première ligne était correcte, je veux le faire ici.
Parce que je ne pouvais pas, par exemple, le faire ici-bas. Pourquoi?
Juste hors de portée. Ainsi, même si nous parlons de pointeurs,
c'est une semaine 2 ou 3 question, où x est seulement une portée à l'intérieur des accolades où elle a été déclarée.
Alors vous avez certainement ne peut pas le libérer là-bas. Ma seule chance pour la libérer est à peu près après la ligne 21.
Il s'agit d'un programme assez simple, il est assez facile une fois que vous sorte de votre esprit enveloppé
autour de ce que le programme fasse, où les erreurs ont été.
Et même si vous ne le voyez pas dans un premier temps, j'espère que c'est un peu évident maintenant
que ces erreurs sont assez faciles à résoudre et facile à faire.
Mais quand un programme est de plus de 12 lignes de long, c'est 50 lignes, 100 lignes de long,
marche à travers votre code ligne par ligne, en pensant par là logiquement,
est possible, mais pas particulièrement amusant à faire, sans cesse à la recherche de bugs,
et il est aussi difficile à faire, et c'est pourquoi un outil comme Valgrind existe.
Laissez-moi aller de l'avant et faire ceci: laissez-moi ouvrir ma fenêtre de terminal,
et ne me laisse pas il suffit d'exécuter la mémoire, car la mémoire semble bien se passer.
Je deviens chanceux. Qui va octet supplémentaire à la fin de la matrice
ne semble pas y avoir trop de problèmes.
Mais permettez-moi, tout de même, faire un test de cohérence, ce qui signifie juste pour vérifier
si oui ou non il s'agit en fait correcte.
>> Alors, faisons valgrind-v - Fuite-check = plein,
puis le nom du programme dans ce cas est la mémoire, pas a.out.
Alors laissez-moi aller de l'avant et de le faire. Appuyez sur Entrée.
Cher Dieu. Il s'agit de sa sortie, et c'est ce que je faisais allusion tout à l'heure.
Mais, si vous apprenez à lire toutes les bêtises ici,
plupart de ceci est juste sortie de diagnostic, ce n'est pas très intéressant.
Que votre œil veut vraiment être cherchez est fait mention de l'erreur ou non valide.
Les mots qui suggèrent des problèmes.
Et en effet, nous allons voir ce qui va mal ici-bas.
J'ai un résumé en quelque sorte, «en usage à la sortie:. 40 octets de blocs de 1"
Je ne suis pas vraiment sûr de ce bloc est encore, mais 40 octets
sent réellement comme je pouvais trouver où ça vient.
40 octets. Pourquoi sont 40 octets en usage à la sortie?
Et plus précisément, si nous défiler vers le bas ici,
pourquoi ai-je définitivement perdu 40 octets? Ouais?
[Réponse de l'étudiant, inintelligible] Parfait. Oui, exactement.
Il y avait dix entiers, et chacun d'entre eux est la taille de 4 ou 32 bits,
donc j'ai perdu exactement 40 octets parce que, comme vous l'avez proposé, je n'ai pas dit libre.
C'est un bug, et maintenant nous allons regarder vers le bas un peu plus loin et de voir à côté de cela,
«Invalide écrire de taille 4." Maintenant, c'est quoi?
Cette adresse est exprimée la notation de base ce qui, apparemment?
C'est hexadécimal, et chaque fois que vous voyez un numéro commençant par 0x,
cela signifie hexadécimal, que nous avons fait le chemin du retour, je pense, l'article pset 0 de questions,
qui était juste de faire un exercice d'échauffement, la conversion de décimal en hexadécimal en binaire et ainsi de suite.
Hexadécimal, juste par convention humaine, est généralement utilisé pour représenter des pointeurs
ou, plus généralement, les adresses. C'est juste une convention,
parce que c'est un peu plus facile à lire, c'est un peu plus compact que quelque chose comme décimal,
et binaire est inutile pour la plupart des êtres humains à utiliser.
Alors maintenant, qu'est-ce que cela signifie? Eh bien, on dirait qu'il s'agit d'une écriture non valide
de taille 4 à la ligne 21 du memory.c.
Donc, revenons à la ligne 21, et en effet, c'est ici que nulle écriture.
Donc, Valgrind ne va pas tout à fait tenir ma main et me dire ce que la solution est,
mais il détecte que je fais une écriture non valide.
Je touche 4 octets qui je ne serais pas, et apparemment c'est parce que,
comme vous l'avez souligné, je fais [10] au lieu de [9] au maximum
ou [0] ou quelque chose entre les deux.
Avec Valgrind, de réaliser n'importe quel moment vous êtes en train d'écrire un programme
qui utilise des pointeurs et utilise de la mémoire, et malloc, plus précisément,
certainement prendre l'habitude de courir aussi longtemps
mais très facilement copié et collé le commandement de Valgrind
pour voir si il ya des erreurs qui s'y trouvent.
Et ça va être énorme à chaque fois que vous voyez la sortie,
mais simplement analyser visuellement à travers toute la production et de voir si vous voyez des erreurs mentionne
ou des avertissements ou invalide ou perdu.
Tous les mots qui vous ressemble vissés quelque part.
Alors rends compte que c'est un nouvel outil dans votre boîte à outils.
>> Maintenant, le lundi, nous avons eu tout un tas de gens viennent ici
et représenter la notion d'une liste chaînée.
Et nous avons introduit la liste chaînée comme une solution à ce problème?
Ouais? [Réponse de l'étudiant, inintelligible] Bon.
Les tableaux ne peuvent pas avoir la mémoire ajoutée.
Si vous allouer un tableau de taille 10, c'est tout ce que vous obtenez.
Vous pouvez appeler une fonction comme realloc si vous avez initialement appelé malloc,
et qui peut tenter d'augmenter le tableau si l'espace vers l'extrémité de celui-ci
que personne d'autre utilise, et s'il n'y a pas, il va juste te trouver une plus grosse part ailleurs.
Mais alors, il va copier tous les octets dans le nouveau tableau.
Cela sonne comme une solution très correcte.
Pourquoi est-ce disgracieux?
Je veux dire que cela fonctionne, les humains ont résolu ce problème.
Pourquoi avons-nous besoin de le résoudre, lundi, avec des listes chaînées? Ouais?
[Réponse de l'étudiant, inintelligible] Il pourrait prendre un certain temps.
En fait, chaque fois que vous appelez malloc ou calloc ou realloc, ce qui est encore un autre,
chaque fois que vous, le programme, parlons du système d'exploitation,
vous avez tendance à ralentir le programme.
Et si vous faites ce genre de choses dans les boucles, vous êtes vraiment ralentir les choses.
Tu ne vas pas à le remarquer pour la plus simple des programmes de "Hello World" de type,
mais dans des programmes beaucoup plus importants, en demandant au système d'exploitation encore et encore pour la mémoire
ou de la remettre encore et encore tendance à ne pas être une bonne chose.
De plus, c'est juste une sorte de plan intellectuel - c'est une perte de temps totale.
Pourquoi allouer de la mémoire de plus en plus, le risque de copier tout dans le nouveau tableau,
si vous avez une alternative qui vous permet d'allouer de la mémoire seulement autant que vous avez réellement besoin?
Il ya donc des avantages et des inconvénients dans ici.
Un des avantages est que nous avons dynamisme.
Peu importe où les segments de mémoire sont qui sont libres,
Je peux juste une sorte de créer ces miettes de pain via les pointeurs
d'enchaîner ma liste entière reliés entre eux.
Mais je payer au moins un prix.
>> Que dois-je renoncer à obtenir des listes chaînées?
Ouais? [Réponse de l'étudiant, inintelligible] Bon.
Vous avez besoin de plus de mémoire. Maintenant, j'ai besoin d'espace pour ces pointeurs,
et dans le cas de cette liste liée simple, super-
qui ne cherche qu'à stocker des entiers, qui sont 4 octets, nous disons
De plus, un pointeur de 4 octets, alors maintenant je suis littéralement doublé
la quantité de mémoire J'ai besoin juste pour stocker cette liste.
Mais encore une fois, c'est un compromis constant en informatique
entre le temps et l'espace et le développement, l'effort et d'autres ressources.
Ce qui est un autre inconvénient de l'utilisation d'une liste chaînée? Ouais?
[Réponse de l'étudiant, inintelligible]
Bon. Pas aussi facile d'accès. On ne peut plus tirer parti de
semaine 0 comme principes diviser pour régner.
Et plus précisément, la recherche binaire. Parce que même si nous, les humains
peut voir à peu près où le milieu de cette liste est,
l'ordinateur ne connaît que cette liste chaînée commence à l'adresse appelée en premier.
Et c'est 0x123 ou quelque chose comme ça.
Et la seule façon le programme peut trouver l'élément central
est en fait de rechercher toute la liste.
Et même alors, il a littéralement pour rechercher toute la liste parce
même une fois que vous atteignez l'élément central en suivant les pointeurs,
vous, le programme, n'ont aucune idée de combien de temps cette liste est, potentiellement,
jusqu'à ce que vous atteignez la fin de celui-ci, et comment savez-vous par programmation
que vous êtes à la fin d'une liste chaînée?
Il s'agit d'un pointeur NULL spéciale, à nouveau, une convention.
Plutôt que d'utiliser ce pointeur, nous ne voulons certainement pas que ce soit une valeur ordures
pointant hors de la scène, quelque part, nous voulons que ce soit la main vers le bas, NULL,
afin que nous ayons ce terminus dans cette structure de données afin de savoir où elle se termine.
>> Que faire si nous voulons manipuler ce?
Nous avons fait plus de cela visuellement, et avec les humains,
mais que faire si nous voulons faire une insertion?
Ainsi, la liste initiale était de 9, 17, 20, 22, 29, 34.
Et si on a ensuite voulu espace malloc pour le numéro 55, un nœud pour elle,
puis nous voulons insérer 55 dans la liste comme nous l'avons fait le lundi?
Comment pouvons-nous faire cela? Eh bien, Anita est arrivé et elle a essentiellement marchait dans la liste.
Elle a commencé le premier élément, puis la suivante, l'autre, l'autre, l'autre, le lendemain.
Enfin frappé la gauche tout en bas
et réalisé oh, c'est la valeur NULL. Donc manipulation de pointeurs ce qui devait être fait?
La personne qui se trouvait à la fin, numéro 34, avait besoin de sa main gauche levée
pour pointer à 55, 55 avaient besoin de leur bras gauche vers le bas pour être le nouveau terminateur NULL. Terminé.
Assez facile à insérer 55 dans une liste triée.
Et comment cela pourrait-il regarder?
>> Permettez-moi aller de l'avant et d'ouvrir quelques exemple de code ici.
Je vais ouvrir gedit, et laissez-moi ouvrir deux fichiers en premier.
L'un est list1.h, et laissez-moi vous rappeler que c'était le morceau de code
que nous avons utilisé pour représenter un nœud.
Un nœud possède à la fois un int appelé n et un pointeur appelé prochain juste des points à la chose suivante dans la liste.
C'est désormais dans un fichier. H. Pourquoi?
Il ya cette convention, et nous n'avons pas profité de cette énorme quantité de nous-mêmes,
mais la personne qui a écrit fonctions printf et autres
donné comme un cadeau pour le monde de toutes ces fonctions en écrivant un fichier appelé stdio.h.
Et puis il ya string.h, et puis il ya map.h, et il ya tous ces fichiers h
que vous pourriez avoir vu ou utilisé pendant la durée écrit par d'autres personnes.
En général, dans les fichiers. H sont les seules choses comme typedefs
ou des déclarations de types personnalisés ou des déclarations de constantes.
Vous ne mettez pas les implémentations des fonctions »dans les fichiers d'en-tête.
Vous avez mis, au contraire, seulement leurs prototypes.
Vous mettez les choses que vous voulez partager avec le monde ce dont ils ont besoin
afin de compiler leur code. Donc, juste pour entrer dans cette habitude,
nous avons décidé de faire la même chose. Il n'ya pas beaucoup de list1.h,
mais nous avons mis quelque chose qui pourrait être d'intérêt pour les gens dans le monde
qui veulent utiliser notre implémentation liste chaînée.
Maintenant, dans list1.c, je ne vais pas passer par toute cette affaire
parce que c'est un peu long, ce programme, mais nous allons l'exécuter réel rapidement à l'invite.
Permettez-moi de compiler list1, permettez-moi alors de fonctionner list1 et ce que vous verrez est
nous avons simulé un programme simple peu ici
qui va me permettre d'ajouter et de supprimer des numéros à une liste.
Alors laissez-moi aller de l'avant et de type 3 pour les 3 options du menu.
Je veux insérer le nombre - nous allons faire le premier numéro, qui était de 9,
et maintenant je me dit que la liste est maintenant 9.
Permettez-moi aller de l'avant et faire une autre insertion, alors j'ai frappé l'option 3 du menu.
Quel numéro dois-je veux insérer? 17.
Entrée. Et je ferai juste un plus.
Permettez-moi d'insérer le numéro 22.
Nous avons donc les débuts de la liste chaînée que nous avions sous forme de diaporama il ya un instant.
Comment est cette insertion se passe réellement?
En effet, 22 est maintenant à la fin de la liste.
Donc, l'histoire nous dit sur scène le lundi et récapitulé tout à l'heure
doit effectivement être le cas dans le code.
Jetons un coup d'oeil. Permettez-moi de faire défiler vers le bas dans ce fichier.
Nous allons passer rapidement sur certaines fonctions,
mais nous allons descendre à, disons, la fonction d'insertion.
>> Voyons comment nous allons sur l'insertion d'un nouveau nœud dans cette liste chaînée.
Où est la liste déclarée? Eh bien, nous allons faire défiler tout le chemin vers le sommet,
et remarquez que ma liste est liée essentiellement déclaré comme un pointeur unique qui est initialement NULL.
Donc, je suis en utilisant une variable globale ici, qui en général nous avons prêché contre
parce que cela rend votre code un peu désordonné de maintenir,
C'est en quelque sorte de paresseux, le plus souvent, mais ce n'est pas paresseux et ce n'est pas mal et c'est pas mal
si le seul but de votre programme dans la vie est de simuler une liste chaînée.
Ce qui est exactement ce que nous faisons.
Ainsi, plutôt que de déclarer cela en principal et ensuite de le transmettre à toutes les fonctions
nous avons écrit à ce programme, nous avons plutôt réaliser oh, disons simplement la rendre globale
parce que le but de ce programme est de démontrer une et une seule liste chaînée.
Alors qui se sent bien. Voici mes prototypes, et nous n'allons pas passer par tout cela,
mais j'ai écrit une fonction de suppression, une fonction de recherche, une fonction d'insertion, et une fonction transversale.
Mais nous allons maintenant redescendre à la fonction d'insertion
et de voir comment celui-ci fonctionne ici.
Insérer est en ligne - ici nous allons.
Insérez. Donc, il ne prend aucun argument, parce que nous allons demander à
l'intérieur d'utilisateur de cette fonction pour le nombre qu'ils veulent insérer.
Mais d'abord, nous nous préparons à leur donner un peu d'espace.
C'est une sorte de copier-coller à partir de l'exemple des autres.
Dans ce cas, nous avons été l'attribution d'un int, cette fois, nous allouons un nœud.
Je ne me souviens pas vraiment combien d'octets est un nœud, mais c'est très bien.
Sizeof peut comprendre cela pour moi.
Et pourquoi suis-je vérifier pour NULL dans la ligne 120?
Qu'est-ce qui pourrait mal tourner dans la ligne 119? Ouais?
[Réponse de l'étudiant, inintelligible]
Bon. Tout pourrait être le cas que j'ai demandé trop de mémoire
ou quelque chose ne va pas et le système d'exploitation ne dispose pas de suffisamment d'octets à me donner,
il signale autant en retournant NULL, et si je ne vérifie pas que
et je aveuglément continuer à utiliser l'adresse de retour, il pourrait être NULL.
Il pourrait y avoir une valeur inconnue, pas une bonne chose si je ne -
fait ne sera pas une valeur inconnue. Il pourrait être NULL, alors je ne veux pas
à en abuser et de risquer de le déréférencement.
Si cela arrive, je viens de rentrer et nous allons faire comme si je n'avais pas récupérer toute la mémoire du tout.
>> Sinon, je dis à l'utilisateur me donner un numéro à insérer, j'appelle notre getInt vieil ami,
puis ce fut la nouvelle syntaxe, nous avons présenté le lundi.
«Newptr-> n 'signifie prendre l'adresse qui vous a été donné par malloc
qui représente le premier octet d'un objet nouveau noeud,
puis aller sur le terrain appelé n.
Une petite question quiz: Ceci est équivalent à ce que la ligne plus énigmatique de code?
Comment aurais-je pu écrire ce? Vous voulez prendre un coup de poignard?
[Réponse de l'étudiant, inintelligible]
Bon. Utilisation de la n., Mais ce n'est pas tout à fait aussi simple que cela.
Qu'est-ce que je dois d'abord faire? [Réponse de l'étudiant, inintelligible]
Bon. J'ai besoin de faire newptr.n *.
Donc, cela veut dire nouveau pointeur est évidemment une adresse. Pourquoi?
Parce qu'elle a été renvoyée par malloc. Le newptr * disant: «y aller»,
puis une fois que vous y êtes, vous pouvez alors utiliser le plus familier. n,
mais cela ressemble un peu laid, surtout si nous, les humains vont
tirer des pointeurs avec des flèches tout le temps, le monde a standardisé sur cette notation fléchée,
qui fait exactement la même chose.
Donc, vous utilisez uniquement le -> la notation lorsque la chose sur la gauche est un pointeur.
Sinon, si c'est une structure réelle, utilisez le n..
Et puis ceci: Pourquoi dois-je initialiser newptr-> suivant à NULL?
Nous ne voulons pas d'une main gauche pend hors de la fin de la scène.
Nous voulons qu'il pointant vers le bas, ce qui signifie la fin de cette liste
pourrait être à ce nœud, donc nous assurez-vous qu'il est NULL.
Et, en général, initialiser vos variables ou vos membres de données et structures
à quelque chose est juste bonne pratique.
Se contenter de laisser les déchets existent et continueront d'exister en général, vous obtient dans l'ennui
si vous avez oublié de faire quelque chose plus tard.
>> Voici quelques cas. Là encore, c'est la fonction d'insertion,
et la première chose que je vérifie, c'est si la variable appelée en premier,
cette variable globale est NULL, ce qui signifie qu'il n'ya pas de liste chaînée.
Nous avons inséré aucun nombre, il est donc trivial pour insérer ce numéro actuel
dans la liste, parce qu'il appartient seulement au début de la liste.
Donc, ce fut quand Anita vient d'être debout ici seul, en faisant semblant
personne d'autre était ici sur la scène jusqu'à ce que nous avons prévu un noeud,
alors elle pourrait lever la main pour la première fois,
si tout le monde était venu sur la scène après sa lundi.
Or, ici, il s'agit d'un petit chèque où je dois dire que si le nouveau nœud de valeur de n
<est la valeur de n dans le premier noeud de courant,
cela signifie qu'il ya une liste liée qui a commencé.
Il ya au moins un noeud dans la liste, mais ce nouveau type
appartient avant, donc nous devons faire bouger les choses autour.
En d'autres termes, si la liste a commencé avec seulement, disons,
juste le numéro 17, c'est le - en fait, nous pouvons faire cela plus clairement.
Si nous commençons notre histoire avec un pointeur ici appelé en premier,
et d'abord il est NULL, et nous indiquer le numéro 9,
le nombre 9 appartient clairement au début de la liste.
Donc, supposons que nous venons de malloced l'adresse ou le numéro 9 et le mettre ici.
Si le premier est de 9 par défaut, le premier scénario, nous avons discuté signifie simplement que le point let de ce gars ici,
laisser ce que NULL; nous avons maintenant le numéro 9.
Le prochain numéro nous voulons insérer est de 17.
17 appartient ici, donc nous allons devoir faire quelques pas à pas à travers cette logique.
Alors disons plutôt que, avant de faire cela, supposons que nous voulions insérer le numéro 8.
>> Donc, juste pour une question de commodité, je vais faire ici.
Mais rappelez-vous, malloc peut mettre presque n'importe où.
Mais pour l'amour du dessin, je vais le mettre ici.
Donc, prétendre que je viens alloué un noeud pour le numéro 8, ce qui est NULL par défaut.
Que doit maintenant se passer? Un certain nombre de choses.
Nous avons fait cette erreur sur scène le lundi où nous avons mis à jour un pointeur comme ça,
puis a fait cela, et puis nous avons affirmé - nous orphelin tout le monde sur scène.
Parce que tu ne peux pas - l'ordre des opérations est important ici,
parce que maintenant nous avons perdu ce noeud 9 qui est juste une sorte de flotter dans l'espace.
Ce n'était donc pas la bonne approche lundi.
Nous devons d'abord faire quelque chose d'autre.
L'état du monde ressemble à ceci. Au départ, 8 ont été alloués.
Quelle serait une meilleure façon d'insérer 8?
Au lieu de mettre à jour ce premier pointeur, juste mettre à jour celui-là à la place.
Nous avons donc besoin d'une ligne de code qui va transformer ce caractère NULL
dans un pointeur pointant réelle qui est au noeud 9,
et alors nous pouvons en toute sécurité d'abord changer pour pointer vers ce gars ici.
Maintenant, nous avons une liste, une liste chaînée, de deux éléments.
Et qu'est ce que cela fait ressembler ici?
Si l'on regarde le code, vous remarquerez que j'ai fait exactement cela.
Je l'ai dit newptr, et dans cette histoire, newptr pointait à ce gars-là.
>> Alors laissez-moi d'attirer encore une chose, et je l'aurais laissé place un peu plus pour cela.
Alors pardonnez le dessin minuscule.
Ce gars-là est appelé newptr.
C'est la variable, nous avons déclaré quelques lignes plus haut, dans la ligne - juste au-dessus 25.
Et elle pointe à 8. Donc, quand je dis newptr-> suivant, cela signifie aller à la struct
qui est pointé par newptr, nous voici donc, allez-y.
Ensuite, la flèche est dit obtenir le champ suivant, puis l'= est mis disant quelle valeur?
La valeur qui était en première valeur qui était le premier?
Première pointait sur ce nœud, ce qui signifie que cela devrait maintenant pointer vers ce nœud.
En d'autres termes, ce qui semble bien un désordre ridicule avec mon écriture,
ce qui est une idée simple de transférer ces flèches autour
se traduit par le code avec juste cette ligne de commande.
Stockez ce qui est en premier dans le champ suivant, puis mettre à jour ce premier fait.
Allons de l'avant et avancer rapidement dans une partie de cette,
et ne regarder que cette insertion queue pour l'instant.
Supposons que je arriver au point où je trouve que le prochain champ de certains node est NULL.
Et à ce moment de l'histoire, un détail qui Je passe sur
c'est que j'ai introduit un autre pointeur vers le haut ici, à la ligne 142, pointeur prédécesseur.
Pour l'essentiel, à ce stade de l'histoire, une fois que la liste est longue,
J'ai en quelque sorte besoin de marcher avec deux doigts, parce que si je vais trop loin,
retenir dans une liste unique de longueur, vous ne pouvez pas revenir en arrière.
Donc cette idée de predptr est mon doigt vers la gauche, et newptr - pas newptr.
Un autre pointeur qui est ici est mon autre doigt, et je suis juste un peu de marche dans la liste.
C'est pourquoi ce qui existe. Mais nous allons seulement considérer l'un des cas plus simples ici.
Si le champ suivant ce pointeur est NULL, ce qui est la conséquence logique?
Si vous êtes parcourant cette liste et que vous frappez un pointeur NULL?
Vous êtes à la fin de la liste, et ainsi le code pour ensuite ajouter à cet élément supplémentaire
est en quelque sorte la intuitif prendra ce nœud dont la prochaine pointeur est NULL,
c'est donc le moment NULL, et le changer, même si, comme l'adresse du nouveau noeud.
Donc, nous ne faisons que tirer dans le code la flèche que l'on a sur scène en levant la main gauche de quelqu'un.
>> Et le cas que je vais saluer mes mains pour le moment,
juste parce que je pense qu'il est facile de se perdre quand nous le faisons dans ce genre d'environnement,
est la vérification de l'insertion au milieu de la liste.
Mais juste intuitivement, ce qui doit se passer si vous voulez comprendre
où un certain nombre appartient au milieu, c'est que vous avez à marcher
avec plus d'un doigt, plus d'un pointeur,
savoir où il appartient de vérifier est l'élément <l'actuel,
> L'actuel, et une fois que vous trouver cet endroit,
alors vous devez faire ce genre de jeu de bonneteau où vous vous déplacez les pointeurs vers de très près.
Et cette réponse, si vous le souhaitez à la raison grâce à cela à la maison sur votre propre,
se résume simplement à ces deux lignes de code, mais l'ordre de ces lignes est super important.
Parce que si vous laissez tomber la main de quelqu'un et d'élever quelqu'un d'autre dans le mauvais ordre,
encore une fois, vous pourriez vous retrouver orphelins de la liste.
Pour résumer conceptuellement plus, l'insertion de la queue est relativement simple.
L'insertion à la tête est aussi relativement simple,
mais vous avez besoin de mettre à jour un pointeur supplémentaire cette fois
à serrer le numéro 5 dans la liste ici,
puis insertion dans le milieu implique un effort encore plus,
faire très attention à insérer le numéro 20 dans son emplacement correct,
qui est comprise entre 17 et 22.
Donc, vous avez besoin de faire quelque chose comme le nouveau nœud de 20 points à 22,
puis, le pointeur du noeud qui doit être mis à jour dernier?
Il a 17 ans, fait à l'insérer.
Encore une fois, je vais reporter le code réel pour que la mise en œuvre particulière.
>> À première vue, c'est un peu écrasante, mais c'est vraiment juste une boucle infinie
qui est en boucle, en boucle, en boucle, en boucle, et de briser dès que vous appuyez sur le pointeur NULL,
à quel point vous pouvez faire de l'insertion requise.
Ce, alors, est représentatif code lié insertion liste.
Cela faisait un peu beaucoup, et il se sent comme nous avons résolu un problème,
mais nous avons mis en place une toute autre histoire. Franchement, nous avons passé tout ce temps
le grand O et Ω et la gestion du temps, en essayant de résoudre les problèmes plus rapidement,
et ici, nous faisons un grand pas en arrière, il se sent.
Et pourtant, si l'objectif est de stocker des données,
il se sent comme le Saint Graal, comme nous l'avons dit, le lundi serait vraiment
pour stocker des choses instantanément.
>> En effet, supposons que nous avons mis de côté la liste liée pour un moment
et nous avons plutôt introduit la notion d'une table.
Et nous allons juste penser à une table pour un moment comme un tableau.
Ce tableau et ce cas a ici quelque 26 éléments, de 0 à 25,
et supposons que vous aviez besoin de quelque morceau de stockage pour les noms:
Alice et Bob et Charlie, etc.
Et vous avez besoin d'une structure de données pour stocker ces noms.
Eh bien, vous pouvez utiliser quelque chose comme une liste chaînée
et on pouvait marcher sur la liste d'insérer Alice avant que Bob et Charlie après que Bob et ainsi de suite.
Et, en fait, si vous voulez voir le code comme ça en passant,
savons que dans list2.h, nous faisons exactement cela.
Nous n'irons pas à travers ce code, mais il s'agit d'une variante du premier exemple
qui introduit un autre struct nous avons vu auparavant appelé étudiant,
et puis ce qu'il stocke en fait dans la liste chaînée est un pointeur vers une structure étudiant
plutôt que d'un simple entier peu, n.
Alors rends compte qu'il ya code, il implique que les chaînes réelles,
mais si l'objectif à portée de main vraiment maintenant est de s'attaquer au problème de l'efficacité,
ça ne serait pas bien si on nous donne un objet appelé Alice,
nous voulons la mettre dans le bon emplacement dans une structure de données,
il se sent comme ça serait vraiment sympa de mettre juste Alice,
dont le nom commence par A, dans le premier emplacement.
Et Bob, dont le nom commence par B, dans le deuxième emplacement.
Avec un tableau, ou nous allons commencer à l'appeler une table, une table de hachage à l',
nous pouvons faire exactement cela. Si on nous donne un nom comme Alice,
une chaîne comme Alice, où mettez-vous A-l-i-c-e?
Nous avons besoin d'un hueristic. Nous avons besoin d'une fonction pour prendre un peu comme Alice entrée
et retourner une réponse: «Mettez Alice à cet endroit."
Et cette fonction, cette boîte noire, va être appelée une fonction de hachage.
>> Une fonction de hachage est quelque chose qui prend une entrée, comme «Alice»,
et revient à vous, en général, l'emplacement numérique dans une structure de données où Alice appartient.
Dans ce cas, notre fonction de hachage devrait être relativement simple.
Notre fonction de hachage doit dire que, si on vous donne "Alice", le personnage que je dois m'en soucier?
La première. Donc, je regarde [0], puis-je dire si [0] caractère est A, retourner le nombre 0.
Si c'est B, renvoyer 1. Si c'est C, retourner 2, et ainsi de suite.
Tous les index 0, et qui me permettrait d'insérer Alice et Bob, puis puis Charlie et ainsi de suite
dans cette structure de données. Mais il ya un problème.
Que faire si Anita arrive à nouveau?
Où allons-nous mettre Anita? Son nom, lui aussi, commence par la lettre A,
et il se sent comme nous avons fait un gâchis encore plus grand de ce problème.
Nous avons maintenant insertion immédiate, insertion constante de temps, dans une structure de données
plutôt que pire des cas linéaire,
mais que pouvons-nous faire avec Anita dans ce cas?
Quels sont les deux options, vraiment? Ouais?
[Réponse de l'étudiant, inintelligible] Bon, alors nous pourrions avoir une autre dimension.
C'est bien. Ainsi, nous pouvons construire des choses en 3D comme nous en avons parlé verbalement le lundi.
On pourrait ajouter un autre accès ici, mais je suppose que non, je suis en train de garder ce simple.
Le but ici est tout à avoir rapidement accès en temps constant,
donc c'est ajouter trop de complexité.
Quelles sont les autres options lorsque vous essayez d'insérer Anita dans cette structure de données? Ouais?
[Réponse de l'étudiant, inintelligible] Bon. Donc, nous pourrions passer tout le monde vers le bas,
comme Charlie coups de coude vers le bas Bob et Alice, et puis nous avons mis Anita où elle veut vraiment être.
>> Bien sûr, maintenant, il ya un effet secondaire de cette.
Cette structure de données est probablement utile non pas parce que nous voulons insérer les gens une fois
mais parce que nous voulons vérifier si elles sont là plus tard
si nous voulons imprimer tous les noms dans la structure de données.
Nous allons faire quelque chose avec ces données par la suite.
Alors maintenant, nous avons sorte de vissé sur Alice, qui n'est plus où elle est censée être.
Bob n'est pas non plus, ni Charlie.
Alors peut-être que ce n'est pas une si bonne idée.
Mais en fait, c'est une option. Nous pourrions passer tout le monde vers le bas,
ou diable, Anita est venu tard dans le jeu, pourquoi ne pas simplement mettre Anita
pas ici, pas ici, pas ici, nous allons juste lui mettre un peu plus bas dans la liste.
Mais ce problème commence à transférer à nouveau.
Vous pourriez être en mesure de trouver instantanément Alice, sur la base de son prénom.
Et Bob instantanément, et Charlie. Mais alors vous cherchez Anita,
et vous voyez, hein, Alice est sur le chemin.
Eh bien, laissez-moi vérifier ci-dessous Alice. Bob n'est pas Anita.
Charlie n'est pas Anita. Oh, il ya Anita.
Et si vous continuez ce train de la logique jusqu'au bout,
quel est le temps le pire des cas en cours d'exécution de la recherche ou de l'insertion Anita dans cette nouvelle structure de données?
Il est O (n), pas vrai?
Parce que dans le pire des cas, il ya Alice, Bob, Charlie. . .
tout le chemin vers le bas pour quelqu'un qui s'appelle «Y», il n'y a donc qu'une seule place à gauche.
Heureusement, nous n'avons pas de celui qui est appelé "Z", nous avons donc mis Anita tout en bas.
>> Nous n'avons pas vraiment résolu ce problème.
Alors peut-être nous avons besoin d'introduire cette troisième dimension.
Et il s'avère que, si nous ne nous introduire cette troisième dimension,
nous ne pouvons pas faire cela parfaitement, mais le Saint-Graal va devenir de
constante de temps d'insertion et les insertions dynamiques, afin que
nous n'avons pas coder en dur un tableau de taille 26.
Nous pouvons insérer autant de noms que nous voulons, mais nous allons prendre notre pause de 5 minutes ici
puis le faire correctement.
Très bien. J'ai mis en place l'histoire assez artificiellement il
en choisissant Alice et Bob, puis puis Charlie et Anita,
dont le nom était évidemment entrer en collision avec Alice.
Mais la question que nous a pris fin lundi avec c'est à quel point est-il probable
que vous obtenez ce genre de collisions? En d'autres termes,
si on commence à utiliser cette structure sous forme de tableau, ce qui est vraiment juste un tableau,
dans ce cas, de 26 emplacements,
si nos entrées sont plutôt uniformément répartie?
Ce n'est pas artificiellement Alice et Bob et Charlie David et ainsi de suite par ordre alphabétique,
elle est répartie uniformément sur A à Z.
>> Peut-être que nous allons avoir de la chance et nous n'allons pas avoir deux A ou deux B
avec une probabilité très élevée, mais comme quelqu'un l'a souligné,
si nous généralisé ce problème et ne pas faire de 0 à 25
mais, disons, de 0 à 364 ou de 65 ans, souvent le nombre de jours dans une année normale,
et a posé la question: «Quelle est la probabilité que deux d'entre nous dans cette salle ont le même anniversaire?"
En d'autres termes, quelle est la probabilité que deux d'entre nous ont un nom commençant par A?
Le genre de question est la même, mais cet espace d'adressage,
cet espace de recherche, est plus grand dans le cas des anniversaires,
parce que nous avons tant de jours de plus que l'année lettres dans l'alphabet.
Quelle est la probabilité d'une collision?
Eh bien, nous pouvons penser de ce par déterminer le calcul en sens inverse.
Quelle est la probabilité de collisions pas?
Eh bien, cette expression ici dit que ce qui est la probabilité
s'il n'y a qu'une seule personne dans cette salle, qu'ils ont un anniversaire unique?
C'est 100%. Parce que s'il ya une seule personne dans la salle,
son anniversaire peut être l'un des 365 jours de l'année.
Ainsi, les options 365/365 me donne une valeur de 1.
Donc, la probabilité en question en ce moment est à seulement 1.
Mais s'il ya une deuxième personne dans la chambre,
quelle est la probabilité que leur anniversaire est différent?
Il ya seulement 364 jours possibles, en ignorant les années bissextiles,
pour leur anniversaire de ne pas entrer en collision avec d'autres personnes.
Donc 364/365. Si une tierce personne arrive, c'est 363/365, et ainsi de suite.
Alors nous gardons multipliant ces fractions, qui sont de plus en plus petits,
de comprendre quelle est la probabilité que nous avons tous des anniversaires uniques?
Mais nous pouvons, bien sûr, il suffit de prendre cette réponse et de le retourner dans
et faire 1 moins tout cela, une expression que nous finirons par obtenir
si vous vous rappelez le dos de vos livres de maths, ça ressemble un petit quelque chose comme ça,
qui est beaucoup plus facile à interpréter graphiquement.
Et ce graphique ici est sur l'axe x le nombre d'anniversaires,
ou le nombre de personnes qui ont leur anniversaire, et sur l'axe y est la probabilité d'un match.
Et ce que cela veut dire, c'est que si vous avez, disons, même,
nous allons choisir quelque chose comme 22, 23.
S'il ya 22 ou 23 personnes dans la salle,
la probabilité que deux de ces très peu de gens vont avoir la même date d'anniversaire
est en fait super haute, combinatoire.
50% de chances que dans une classe de seulement 22 personnes, un séminaire, pratiquement,
2 de ces personnes vont avoir le même anniversaire.
Parce qu'il ya tellement de façons dont vous pouvez avoir le même anniversaire.
Pire encore, si vous regardez le côté droit de la carte,
au moment où vous avez une classe avec 58 élèves en elle,
la probabilité de 2 personnes fêtant leur anniversaire est super, super rapide, près de 100%.
Maintenant, c'est une sorte de faits amusants sur la vie réelle.
>> Mais les conséquences, maintenant, pour les structures de données et le stockage d'informations
signifie que juste en supposant que vous avez une belle, propre, la distribution uniforme des données
et vous avez un tableau assez grand pour contenir un tas de choses
ne signifie pas que vous allez amener les gens dans des endroits uniques.
Vous allez avoir des collisions. Donc, cette notion de hachage, comme on l'appelle,
prenant une entrée comme "Alice" et le masser en quelque sorte
puis reprendre une réponse comme 0 ou 1 ou 2.
Pour en revenir une sortie de cette fonction est en proie à cette probabilité de collision.
Alors, comment pouvons-nous gérer ces collisions?
Eh bien, sur le premier cas, nous pouvons prendre l'idée qui a été proposée.
Nous pouvons simplement passer tout le monde vers le bas, ou peut-être, un peu plus simplement,
plutôt que tout le monde déménagement d'autre, nous allons simplement passer Anita au fond de la place disponible.
Donc, si Alice est 0, Bob est en 1, Charlie est dans 2,
nous allons simplement mettre Anita à l'emplacement 3.
Et c'est une technique de structures de données appelées linéaire sondage.
Linéaire parce que vous êtes juste marcher cette ligne, et que vous êtes en quelque sorte de sondage
pour les spots de la structure de données.
Bien sûr, cela dégénérait en O (n).
Si la structure de données est vraiment complet, il ya 25 personnes qui y déjà,
puis Anita arrive, elle se retrouve à ce qui serait emplacement Z, et c'est très bien.
Elle s'inscrit toujours, et nous pouvons la retrouver plus tard.
>> Mais cela était contraire à l'objectif d'accélérer les choses.
Alors que faire si nous introduit à la place de cette troisième dimension?
Cette technique est généralement appelé chaînage séparé, ou ayant des chaînes.
Et quelle table de hachage est présent, cette structure tabulaire,
votre table est juste un tableau de pointeurs.
Mais ce que ces pointeurs indiquent peut deviner quoi?
Une liste chaînée. Alors que faire si nous prenons le meilleur de ces deux mondes?
Nous utilisons des tableaux pour les indices initiaux
dans la structure de données afin que nous puissions vous déplacer instantanément au [0] [1], [30] ou ainsi de suite,
mais pour que nous ayons une certaine souplesse et nous pouvons monter Anita et Alice et Adam
et toute autre Un nom,
nous avons au contraire laisser l'autre axe croître arbitrairement.
Et nous avons finalement, à partir de lundi, ont cette capacité expressive avec liste chaînée.
Nous pouvons cultiver une structure de données arbitrairement.
Sinon, nous pourrions juste faire un énorme 2-dimensionnel,
mais cela va être une situation terrible si l'une des lignes dans un tableau à 2 dimensions
n'est pas assez grand pour la personne supplémentaire dont le nom se passe de commencer avec A.
A Dieu ne plaise que nous devons réaffecter une énorme structure de 2-dimensionnelle
simplement parce qu'il ya tant de gens nommés A,
surtout quand il ya si peu de gens nommés Z quelque chose.
Il va juste être une structure très clairsemée données.
Donc, ce n'est pas parfait par tous les moyens, mais maintenant nous avons au moins la possibilité
pour trouver instantanément où Alice ou Anita appartient,
au moins sur le plan de l'axe vertical,
puis nous avons juste à décider où placer Anita ou Alice dans cette liste chaînée.
Si l'on ne se soucient pas le tri des choses, comment pourrait-on insérer rapidement Alice dans une structure comme ça?
Il est temps constant. Nous index dans [0], et s'il n'y a pas de son,
Alice va au début de la liste liée.
Mais ce n'est pas une affaire énorme. Parce que si Anita vient ensuite le long de
un certain nombre d'étapes plus tard, d'où vient Anita appartiennent?
Eh bien, [0]. POO. Alice est déjà dans cette liste chaînée.
>> Mais si on ne se soucie pas de trier ces noms,
on peut juste se déplacer sur Alice, insert Anita, mais même cela est la constante de temps.
Même s'il n'y a Alice et Adam et tous ces autres noms A,
ce n'est pas vraiment de les déplacer physiquement. Pourquoi?
Parce que nous venons de faire ici avec la liste chaînée, qui sait ont été ces nœuds sont de toute façon?
Tout ce que vous avez à faire est de déplacer les miettes de pain.
Déplacez les flèches autour, vous n'avez pas besoin de se déplacer physiquement toutes les données autour.
Ainsi, nous pouvons insérer Anita, dans ce cas, instantanément. Constante de temps.
Nous avons donc constante de temps de recherche, et en temps constant insertion de quelqu'un comme Anita.
Mais un peu simpliste du monde.
Que faire si nous voulons trouver plus tard Alice?
Combien de pas est ce que cela va prendre?
[Réponse de l'étudiant, inintelligible]
Exactement. Le nombre de personnes avant d'Alice dans la liste chaînée.
Ce n'est donc pas tout à fait parfaite, parce que notre structure de données, encore une fois, a cet accès vertical
puis il a ces listes chaînées suspendus - en fait, il ne faut pas dessiner un tableau un.
Il a ces listes chaînées accroché à ce qui ressemble à un petit quelque chose comme ça.
Mais le problème est que si Alice et Adam et tous ces autres noms A
finissent de plus en plus là-bas,
trouver quelqu'un pourrait finir par prendre un tas d'étapes,
bcause vous devez parcourir la liste chaînée,
qui est une opération linéaire.
Alors, vraiment, alors, le temps d'insertion est finalement O (n), où n est le nombre d'éléments dans la liste.
Divisé par, disons arbitrairement appeler m, où m est le nombre de listes chaînées
que nous avons dans cet axe vertical.
En d'autres termes, si nous voulons vraiment supposent une distribution uniforme des noms,
totalement irréaliste. Il ya évidemment plus de quelques lettres que d'autres.
>> Mais si nous supposons pour le moment une distribution uniforme,
et nous avons n personnes au total, et m chaînes au total
à notre disposition, alors la longueur de chacune de ces chaînes
assez va simplement être le total de n divisé par le nombre de chaînes.
Donc n / m. Mais c'est là que nous pouvons être tout mathématiquement intelligent.
m est une constante, parce qu'il ya un nombre fixe de celles-ci.
Vous allez déclarez votre tableau au début,
et nous ne sommes pas le redimensionnement de l'axe vertical. Par définition, qui reste fixe.
C'est seulement l'axe horizontal, pour ainsi dire, les choses changent.
Donc, techniquement, c'est une constante. Alors maintenant, le temps d'insertion
est à peu près O (n).
Pour que ne se sent pas tout ce que beaucoup mieux.
Mais quelle est la vérité? Eh bien, tout ce temps, pendant des semaines,
nous avons dit O (n ²). O (n), n 2 x ², - n, divisé par 2. . . ech.
C'est juste ² n. Mais maintenant, dans cette partie de la session,
nous pouvons commencer à parler du monde réel.
Et n / m est absolument plus vite que tout seul n.
Si vous avez un millier de noms, et vous les briser en plusieurs seaux
de sorte que vous n'avez que dix noms dans chacune de ces chaînes,
absolument chercher dix choses va être plus rapide que mille choses.
Et si l'un des ensembles de problèmes à venir va vous mettre au défi
à penser exactement que même si, ouais,
asymptotiquement et mathématiquement, cela reste seulement linéaire,
qui aspire en général en essayant de trouver des choses.
En réalité, il va être plus rapide que celui
en raison de ce diviseur.
Et donc il ya encore va être ce compromis
et ce conflit entre la théorie et la réalité,
et l'un des boutons commence à tourner à ce point au cours du semestre
est plus de la seule réalité que nous sorte de préparer pour la fin de semster,
que l'on introduit dans le monde de la programmation web,
où vraiment, la performance va compter parce que vos utilisateurs vont
commencent à sentir et d'apprécier les décisions de conception pauvres.
>> Alors, comment allez-vous mettre en œuvre une alternance - une table de hachage avec 31 éléments?
Et l'exemple précédent a été arbitrairement sur les anniversaires.
Si quelqu'un a un anniversaire de Janvier Février 1 ou 1, nous les mettrons dans ce seau.
Si c'est 2 Janvier 2 Février Mars 2, nous les mettrons dans ce seau.
C'est pourquoi il avait 31 ans. Comment pouvez-vous déclarer une table de hachage?
Il peut être assez simple, table * noeud est mon nom arbitraire pour lui, [31].
Cela me donne 31 pointeurs vers des noeuds,
et cela me permet d'avoir 31 des pointeurs vers des listes chaînées
même si ces chaînes sont initialement NULL.
Qu'est-ce que je veux mettre si je veux conserver "Alice", "Bob", "Charlie"?
Eh bien, nous avons besoin d'envelopper ces choses dans une structure
parce que nous devons faire remarquer Alice à Bob, pour pointer vers Charlie, et ainsi de suite.
Nous ne pouvons pas avoir les noms seuls, pour que je puisse créer une nouvelle structure appelée nœud ici.
>> Qu'est-ce qu'un nœud actuel? Qu'est-ce qu'un nœud dans cette nouvelle liste liée?
La première chose, appelé mot, est le nom de la personne.
LONGUEUR, sans doute, se rapporte à la longueur maximale du nom d'un être humain,
quelle qu'elle soit, 20, 30, 40 caractères dans le cas d'angle fous,
et +1 est pour quoi? C'est juste le caractère NULL supplémentaire, \ 0.
Donc, ce nœud est enveloppant "quelque chose" à l'intérieur de lui-même,
mais il déclare aussi appelé un pointeur prochaine
afin que nous puissions chaîne Alice à Bob à Charlie et ainsi de suite.
Peut être NULL, mais ne doit pas nécessairement l'être.
Toute question relative à ces tables de hachage? Ouais?
[Étudiant posant la question, inintelligible] Tableau - bonne question.
Pourquoi est-ce le mot char dans un tableau plutôt que char *?
Dans cet exemple quelque peu arbitraire, je ne voulais pas avoir à recourir
à malloc pour chacun des noms d'origine.
Je voulais déclarer une quantité maximale de mémoire pour la chaîne
pour que je puisse copier dans la structure Alice \ 0 et ne pas avoir à traiter avec malloc et free, etc.
Mais je ne pouvais le faire que si je voulais être plus conscients de l'utilisation de l'espace. Bonne question.
Essayons donc de généraliser l'écart de cette
et de se concentrer le reste de la journée sur les structures de données plus généralement
et d'autres problèmes que nous pouvons résoudre en utilisant les mêmes principes
même si les structures de données elles-mêmes peuvent différer dans le détail.
>> Ainsi, il s'avère en informatique, les arbres sont très fréquents.
Et vous pouvez penser à une sorte d'arbre comme un arbre de la famille,
où il ya des racines, une matriarche ou patriarche,
grand-mère ou grand-père ou une version antérieure de retour,
sous lequel sont maman et papa ou frères et sœurs divers ou autres.
Ainsi, une structure d'arborescence des nœuds et il a des enfants,
généralement 0 ou plusieurs enfants pour chaque noeud.
Et une partie du jargon que vous voyez sur cette photo ici
est l'un des petits enfants ou petits-enfants sur les bords
qui n'ont pas de flèches qui en émanent,
ce sont les feuilles que l'on appelle, et toute personne à l'intérieur
est un noeud interne, vous pouvez appeler ça le long de ces lignes.
Mais cette structure est assez commun. Celui-ci est un peu arbitraire.
Nous avons un enfant sur la gauche, nous avons trois enfants sur la droite,
deux enfants en bas à gauche.
Donc, nous pouvons avoir différentes tailles d'arbres, mais si nous commençons à normaliser les choses,
et vous pouvez vous rappeler cette vidéo de Patrick sur binaire de recherche à partir d'un court précédente
en ligne, recherche binaire ne doit pas être mis en œuvre avec un tableau
ou des morceaux de papier sur un tableau noir.
Supposons que vous vouliez stocker vos numéros dans une structure plus sophistiquée des données.
Vous pouvez créer un arbre comme celui-ci.
Vous pourriez avoir un noeud déclaré à C, et ce nœud peut avoir au moins deux éléments à l'intérieur de celui-ci.
L'un est le numéro que vous souhaitez mémoriser, et l'autre est - bien, nous avons besoin d'une autre.
L'autre est ses enfants.
Alors, voici une autre structure de données. Cette fois-ci, un noeud est défini comme le stockage d'un nombre n
puis deux pointeurs, l'enfant gauche et à droite l'enfant.
Et ils ne sont pas arbitraires. Ce qui est intéressant à propos de cet arbre?
>> Quelle est la tendance dans la façon dont nous avons posé cette out ou comment Patrick le mit dans sa vidéo?
C'est un peu évident qu'il ya un tri qui se passe ici,
mais quelle est la règle simple? Ouais?
[Réponse de l'étudiant, inintelligible]
Parfait. Si vous jeter un regard sur cela, vous voyez les petits chiffres sur la gauche,
grands nombres sur la gauche, mais c'est vrai pour chaque nœud.
Pour chaque nœud, son fils gauche inférieure à ce qu'elle et son enfant le droit supérieur à celui-ci.
Ce que cela signifie est maintenant si je veux chercher cette structure de données pour, par exemple, le nombre 44,
Je dois commencer à la racine, parce que l'ensemble de ces structures de données plus complexes maintenant,
nous avons seulement un pointeur vers une chose, le commencement.
Et dans ce cas, le début est la racine. Ce n'est pas l'extrémité gauche,
c'est la racine de cette structure. Alors que je vois ici a 55 ans, et je suis à la recherche 44.
Quelle direction dois-je aller?
Eh bien, je veux aller à gauche, parce que, évidemment, vers la droite va être trop grand.
Donc remarquer ici, vous êtes en quelque sorte le plan conceptuel couper l'arbre en deux
parce que vous n'allez jamais jusqu'à la droite.
Alors maintenant, je vais partir de la 55 à la 33. Elle est trop petite d'un nombre.
Je suis à la recherche de 44 ans, mais maintenant je sais pas si 44 est dans cet arbre, je peux rendre à l'évidence vers la droite.
Encore une fois, je suis d'élagage de l'arbre en deux.
C'est à peu près identique, conceptuellement, à l'annuaire téléphonique.
Elle est identique à ce que nous avons fait avec les papiers sur le tableau noir,
mais c'est une structure plus sophistiquée qui nous permet de réellement faire
cette diviser et conquérir par la conception de l'algorithme,
et en fait, en traversant une structure comme celle - oups.
Traversant une structure comme celle-ci, où il est seulement «aller de cette façon ou aller dans ce sens»,
signifie tout ce code qui pliait votre esprit d'abord quand sa mise en œuvre dans la section
ou en marchant à travers elle à la maison, pour la recherche binaire, en utilisant la récursivité ou itération,
c'est une douleur dans le cou. Trouvez l'élément du milieu, puis faites votre arrondi vers le haut ou vers le bas.
>> Il ya une beauté à ce que nous pouvons maintenant utiliser la récursivité à nouveau,
mais beaucoup plus propre. En effet, si vous êtes au numéro 55 et que vous voulez trouver 44,
vous allez à gauche dans ce cas, que faites-vous? Vous exécutez l'algorithme exactement la même.
Vous vérifiez la valeur du nœud, puis vous allez à gauche ou à droite.
Ensuite, vous vérifiez la valeur du nœud, aller à gauche ou à droite.
Ceci est parfaitement adapté à la récursivité.
Ainsi, même si dans le passé nous avons fait quelques exemples assez arbitraires impliquant la récursivité
qui n'ont pas besoin d'être récursive, avec stuctures de données,
en particulier les arbres, c'est une parfaite application de cette idée de prendre un problème,
elle diminue, et ensuite de résoudre le même type d', mais plus petite, d'un programme.
>> Donc, il ya une autre structure de données que l'on peut présenter.
Celui-ci est conçu de prime abord de regarder cryptique, mais celui-ci est incroyable.
C'est donc une structure de données appelée trie, trie, qui est héritée de la récupération des mots,
qui ne se prononce pas re-essayer-val, mais c'est ce que le monde appelle ces choses. Tente. T-r-i-e.
Il s'agit d'une structure arborescente d'une certaine sorte, mais chacun des nœuds dans un trie
semble être quoi? Et c'est un peu trompeur, car c'est le genre de abrégées.
Mais il semble que chaque nœud de la structure arborescente est en fait un tableau.
Et même si l'auteur de ce schéma ne l'a pas montré,
dans ce cas, cette trie est une structure de données dont le but dans la vie est de stocker des mots
comme A-l-i-c-e ou b-O-n.
Et la façon dont ce stocke les données Alice et Bob et Charlie et Anita et ainsi de suite
est-il utilise un tableau de manière à stocker Alice dans une structure arborescente,
on commence par le nœud racine qui ressemble à un tableau,
et il a été écrit en notation abrégée.
L'auteur omis abcdefg parce qu'il n'y avait pas de noms avec cela.
Ils ne montrent M et P et T, mais dans ce cas,
Passons loin de Alice et Bob et Charlie pour certains noms qui sont ici.
Maxwell est en fait dans ce schéma.
Alors, comment le magasin M auteur-a-x-w-e-l-l?
Il ou elle a commencé à le nœud racine, et se rendit à [M], donc environ 13, l'emplacement 13 dans le tableau.
Puis, à partir de là, il ya un pointeur.
Un pointeur menant à un autre tableau.
De là, l'auteur indexé dans ce tableau à l'emplacement A, comme le montre il ya en haut à gauche,
et puis il ou elle a suivi ce pointeur à un autre tableau,
et alla le pointeur à l'endroit X.
Ensuite, dans le prochain emplacement gamme W, E, L, L, et ainsi de suite,
et enfin, nous allons effectivement essayer de mettre une photo à cette question.
À quoi ressemble un noeud comme dans le code?
Un nœud dans une structure arborescente contient un tableau de pointeurs vers d'autres nœuds.
Mais il a aussi obtenu d'être une sorte de valeur booléenne, du moins dans cette mise en œuvre.
Il m'arrive de l'appeler is_word. Pourquoi?
Parce que lorsque vous insérez Maxwell, vous n'êtes pas l'insertion
rien dans cette structure de données.
Vous n'êtes pas écrit M. Vous n'êtes pas écrire X.
Tout ce que vous faites, c'est à la suite des pointeurs.
Le pointeur qui représente M, alors le pointeur qui représente A,
alors que le pointeur représente X, alors W, E, L, L,
mais ce que vous devez faire à la fin est une sorte de go, vérifier, je suis arrivé à cet endroit.
Il y avait un mot qui se termine ici, dans la structure de données.
>> Alors qu'est un trie est vraiment rempli de l'auteur a choisi de représenter
ces terminus de petits triangles.
Cela signifie simplement que le fait que ce triangle est ici, cette valeur booléenne true
signifie que si vous allez vers l'arrière dans l'arborescence,
ce qui signifie un mot nommé Maxwell est à cet égard.
Mais le mot, foo, par exemple,
n'est pas dans l'arbre, parce que si je commence à le nœud racine ici en haut,
Il n'y a aucun pointeur f, pas de pointeur o, o pas de pointeur. Foo n'est pas un nom dans ce dictionnaire.
Mais par contre, la restructuration, t-u-r-i-n-g. Encore une fois, je n'ai pas stocker t ou u ou r ou i ou n ou g.
Mais je n'ai magasin dans cette structure de données d'une valeur de vrai chemin ici-bas dans ce nœud - dans l'arbre
en définissant cette valeur booléenne de is_word à true.
Ainsi, un trie est une sorte de méta cette structure très intéressante,
où vous n'êtes pas vraiment stocker les mots eux-mêmes pour ce type de dictionnaire.
Pour être clair, vous êtes juste stocker oui ou non, il ya un mot qui se termine ici.
>> Maintenant, quel est l'implication?
Si vous avez 150.000 mots dans un dictionnaire que vous essayez de stocker dans la mémoire
en utilisant quelque chose comme une liste chaînée,
vous allez avoir 150.000 nœuds de votre liste chaînée.
Et trouver un de ces mots par ordre alphabétique pourraient en O (n).
Le temps linéaire. Mais dans le cas présent d'une structure arborescente,
quelle est la durée de trouver un mot?
Il s'avère que la beauté ici, c'est que même si vous avez déjà 149.999 mots dans ce dictionnaire,
comme mis en oeuvre avec cette structure de données,
combien de temps faut-il pour trouver ou insérez une personne de plus dans les détails, comme Alice, Alice?
Eh bien, ce n'est que 5, peut-être 6 étapes pour le caractère de fin.
Parce que le presense d'autres noms dans la structure
ne pas obtenir de la manière d'insérer Alice.
En outre, trouver Alice fois il ya 150.000 mots dans ce dictionnaire
ne pas mettre dans votre manière de trouver Alice à tous,
car Alice est. . . . . ici, parce que j'ai trouvé une valeur booléenne.
Et s'il n'y a pas boolean true, alors Alice n'est pas dans cette structure de données de mots.
En d'autres termes, le temps de fonctionnement de trouver des choses et en insérant les choses dans cette nouvelle
structure de données arborescente est O - il n'est pas n.
Parce que le presense de 150.000 personnes n'a aucun effet sur Alice, il semble.
Alors que nous appellerons k, où k est la longueur maximale d'un mot en anglais
qui est généralement pas plus de 20-quelque chose caractères.
Si k est une constante. Ainsi, le Saint-Graal, nous semblons avoir trouvé maintenant
est celle d'une structure arborescente, la constante de temps pour des inserts, pour les recherches, de délétions.
Parce que le nombre de choses déjà dans la structure,
qui ne sont pas encore physiquement. Encore une fois, ils sont juste une sorte de coché, oui ou non,
n'a aucun impact sur sa durée future.
>> Mais il doit bien y avoir un hic, sinon nous n'aurions pas perdu autant de temps
sur toutes ces structures de données autres que pour arriver enfin à l'un des secrets c'est incroyable.
Alors quel prix payons-nous pour atteindre cette grandeur ici? L'espace.
Cette chose est énorme. Et la raison pour laquelle l'auteur
n'a pas le présenter ici, notez que toutes ces choses qui ressemblent à des tableaux,
il n'a pas tiré le reste de l'arbre, le reste de la structure arborescente,
parce qu'ils sont tout simplement pas pertinents à l'histoire.
Mais tous ces nœuds sont super large, et chaque noeud de l'arbre prend
26 ou en fait, pourrait être de 27 caractères, car dans ce cas, j'ai été y compris l'espace pour l'apostrophe
afin que nous puissions avoir des mots apostropha.
Dans ce cas, ce sont des tableaux de large. Ainsi, même si elles ne sont pas picutured,
cela prend une énorme quantité de RAM.
Qui pourrait être bien, especilly dans le matériel moderne,
mais c'est le compromis. Nous recevons moins de temps en dépensant plus d'espace.
Alors, où est-ce tout va?
Eh bien, faisons - nous allons voir ici.
Faisons un saut à ce gars là.
>> Croyez-le ou non, autant de plaisir que C a été pendant un certain temps maintenant,
nous atteignons le point le semestre où il est temps de passer à des choses plus modernes.
Les choses à un niveau supérieur. Et même si pour les deux prochaines semaines
nous allons continuer à nous plonger dans le monde des pointeurs et gestion de la mémoire
pour obtenir que le confort avec lequel nous pouvons construire,
la fin du jeu est finalement d'introduire, ironiquement, pas cette langue.
Nous passerons, comme 10 minutes à parler de HTML.
Toutes HTML est un langage de balisage, et ce qui est un langage de balisage
est cette série de parenthèses ouvertes et fermées supports qui disent «faire de cette audacieuse»
«Faire ce italique» «faire ce centrée.
Ce n'est pas tout ce qui intellectuellement intéressant, mais c'est super utile.
Et ce n'est certainement omniprésente de nos jours.
Mais ce qui est puissant sur le monde du HTML, et la programmation web, plus généralement,
est de construire des choses dynamiques; écrire du code dans des langages comme PHP ou Python ou Ruby ou Java ou C #.
Vraiment, quelle que soit la langue de votre choix, et générer une page HTML dynamique.
Générer quelque chose qui s'appelle CSS dynamiquement.
Feuilles de style en cascade, ce qui est aussi de l'esthétique.
Ainsi, même si, aujourd'hui, si je vais à un certain site Web comme Google.com familier,
et je vais voir, développeur, voir la source, qui peut-être vous avez fait avant,
mais allez voir la source, ce truc ressemble probablement assez cryptique.
Mais c'est le code sous-jacent qui implémente Google.com.
Sur l'extrémité avant. Et en fait, tout cela est moelleux choses esthétique.
C'est CSS ici. Si je continue à défiler vers le bas nous aurons des choses à code couleur.
Il s'agit HTML. Code de Google ressemble à un gâchis, mais si je fait ouvrir une autre fenêtre,
nous pouvons voir une certaine structure à ce sujet.
Si j'ouvre cette place, remarquez ici, c'est un peu plus lisible.
Nous allons voir avant longtemps, cette balise, [mot] est une balise,
HTML, tête, corps, div, script, zone de texte, la durée, centré, div.
Et cela est également trier des cryptique l'avenir, à première vue,
mais tout ce gâchis suit certains schémas et des modèles reproductibles,
de sorte que dès que nous aurons les bases vers le bas, vous serez en mesure d'écrire du code comme ceci
puis de manipuler le code comme ceci utilisant un autre langage, appelé JavaScript.
Et JavaScript est un langage qui s'exécute à l'intérieur d'un navigateur
aujourd'hui que nous utilisons sur les terrains de Harvard, de l'outil de magasinage cours qui utilise google maps
pour vous donner un tas de dynamisme, Facebook vous donne pour montrer mises à jour d'état instantanés,
Twitter qu'il utilise pour vous montrer tweets instantanément.
Tout cela, nous allons commencer à nous plonger po
Mais pour y arriver, nous avons besoin de comprendre quelque chose sur l'Internet.
Ce clip ici est juste une minute, et supposons pour l'instant c'est, en fait,
comment l'Internet fonctionne comme un teaser pour ce qui est sur le point de venir. Je vous donne "Warriors of the Net".
>> [♫ ♫ musique chorale lente]
[Narrateur Homme] Il est venu avec un message.
Avec un protocole qui lui est propre.
[♫ ♫ musique électronique plus rapide]
Il est venu à un monde de pare-feu cool, insouciant routeurs,
et les dangers bien pires que la mort.
Il est rapide. Il est fort. Il est TCP / IP, et il a votre adresse.
Warriors of the net.
[Malan] La semaine prochaine, alors. L'Internet. Programmation Web. C'est CS50.
[CS50.TV]