[Powered by Google Translate] [Article 6] [Plus confortable]
[Rob Bowden] [Université de Harvard]
[C'est CS50.] [CS50.TV]
>> Nous pouvons aller à notre section de questions.
J'ai envoyé l'URL de l'espace avant.
Le début de la section de questions-dire
apparemment je ne suis pas entièrement unsick-est une question très facile
de tout ce qui est valgrind?
Qu'est-ce que valgrind faire?
Quiconque veut dire quoi valgrind-ce pas?
[Étudiant] Vérifie les fuites de mémoire.
Ouais, valgrind est un contrôleur de mémoire générale.
Il, à la fin, vous indique si vous avez des fuites de mémoire,
qui est la plupart du temps ce que nous l'utilisons pour parce que si vous voulez
bien dans l'ensemble problème ou si vous voulez
obtenir sur le grand tableau, vous devez avoir aucune fuite de mémoire que ce soit,
et dans le cas où vous avez une fuite de mémoire que vous ne pouvez pas trouver,
également garder à l'esprit que chaque fois que vous ouvrez un fichier
et si vous ne la fermez pas, c'est une fuite de mémoire.
>> Beaucoup de gens sont à la recherche d'un nœud qu'ils ne sont pas en libérant
alors qu'en réalité, ils n'ont pas fermé le dictionnaire dans la première étape.
Il vous indique également si vous avez des invalides lit ou écrit,
ce qui signifie que si vous essayez de définir une valeur
c'est au-delà de la fin du tas et il ne se passe pas de la faute seg
mais valgrind l'attrape, que vous ne devriez pas être fait par écrit là-bas,
et si vous avez certainement ne devrait avoir aucun de ceux qui soit.
Comment utilisez-vous valgrind?
>> C'est une question générale de
sorte de l'exécuter et regardez la sortie.
La sortie est accablant d'un grand nombre de fois.
Il ya aussi des erreurs amusantes où, si vous avez quelque chose de terriblement mal
passe dans une boucle, puis il finira par dire: «erreurs Beaucoup trop nombreux.
Je vais arrêter de compter désormais. "
Il s'agit essentiellement sortie textuelle que vous avez à analyser.
En fin de compte, il vous indiquera les fuites de mémoire que vous avez,
le nombre de blocs, ce qui peut être utile, car
si c'est un unfreed bloc, alors il est plus facile de trouver
de 1000 blocs unfreed.
1000 blocs unfreed signifie probablement que vous n'êtes pas libérer
vos listes liées de manière appropriée ou quelque chose.
C'est valgrind.
>> Maintenant, nous avons notre section de questions,
dont vous n'avez pas besoin de télécharger.
Vous pouvez cliquer sur mon nom et de les tirer vers le haut dans l'espace.
Maintenant, cliquez sur moi.
Révision 1 sera pile, ce qui nous faisons d'abord.
Révision 2 sera la file d'attente, et la révision 3 sera la liste simplement chaînée.
En partant avec notre pile.
Comme il est dit ici, une pile est l'un des plus basique,
structures de données fondamentales de l'informatique.
L'exemple prototypique est très
la pile de plateaux dans la salle à manger.
Il s'agit en fait chaque fois que vous êtes présenté à une pile,
quelqu'un va dire: «Oh, comme une pile de plateaux."
Vous empilez les bacs vers le haut.
Puis, quand vous allez tirer un plateau,
le premier plateau qui a tiré se est le dernier qui a été mis sur la pile.
La pile aussi, comme il est dit ci-
nous avons le segment de mémoire appelé la pile.
Et pourquoi est-il appelé la pile?
>> Parce que, comme une structure de données pile,
il apparaît des poussées et des cadres de pile sur la pile,
où les cadres de pile sont comme un appel spécifique d'une fonction.
Et comme une pile, vous aurez toujours de revenir
à partir d'un appel de fonction avant de pouvoir descendre dans les cadres de pile baisse à nouveau.
Vous ne pouvez pas avoir barre principale appel appel foo et bar retour directement principale.
Il a toujours eu à suivre la pile en poussant correcte et popping.
Les deux opérations, comme je l'ai dit, sont push et pop.
Ce sont des termes universels.
Vous devriez savoir push et pop en termes de piles, peu importe quoi.
Nous allons voir les files d'attente sont un peu différentes.
Il n'a pas vraiment un terme universel, mais push et pop sont universels pour les piles.
Push est simplement placé sur la pile.
Pop, c'est de prendre de la pile.
Et nous voyons ici, nous avons notre pile typedef struct,
nous avons donc chevalier cordes **.
Ne soyez pas effrayés par tout **.
Cela va finir par être un tableau de chaînes
ou un tableau de pointeurs de caractères, où
pointeurs vers les personnages ont tendance à être des chaînes.
Il n'a pas besoin d'être des chaînes, mais ici, ils vont être des chaînes.
>> Nous avons un tableau de chaînes.
Nous disposons d'une taille, ce qui représente le nombre d'éléments sont actuellement dans la pile,
et puis nous avons la capacité, qui est le nombre d'éléments peuvent être sur la pile.
La capacité devrait commencer comme quelque chose de plus grand que 1,
mais la taille va commencer à 0.
Maintenant, il ya essentiellement trois façons différentes que vous pouvez penser d'une pile.
Eh bien, il ya probablement plus, mais les deux principaux moyens sont
vous pouvez le mettre en œuvre à l'aide d'un tableau, ou vous pouvez le mettre en œuvre en utilisant une liste chaînée.
Listes chaînées sont un peu trivial de réaliser des empilements de.
Il est très facile de faire une pile en utilisant les listes chaînées,
Donc, ici, nous allons faire une pile en utilisant des tableaux,
puis en utilisant les tableaux, il ya aussi deux façons que vous pouvez penser à ce sujet.
Avant, quand je l'ai dit, nous avons une capacité de la pile,
afin que nous puissions répondre à un élément de la pile.
>> La manière dont on pourrait arriver, c'est que dès que vous touchez 10 éléments, puis vous avez terminé.
Vous savez peut-être qu'il ya une limite supérieure de 10 choses dans le monde
que vous n'aurez jamais plus de 10 choses sur votre pile,
Dans ce cas, vous pouvez avoir une borne supérieure sur la taille de votre stack.
Ou vous pourriez avoir votre pile sera sans bornes,
mais si vous faites un tableau, ce qui signifie que chaque fois que vous frappez 10 éléments,
alors vous allez devoir passer à 20 éléments, et quand vous frappez 20 éléments,
vous allez avoir à faire croître votre tableau à 30 éléments ou 40 éléments.
Vous allez avoir besoin d'augmenter la capacité, qui est ce que nous allons faire ici.
Chaque fois que nous arrivons à la taille maximale de notre pile,
quand nous pousser quelque chose d'autre, nous allons avoir besoin d'augmenter la capacité.
Ici, nous avons bouton poussoir déclaré bool (char * str).
Str char * est la chaîne qui nous pousse sur la pile,
et bool dit juste si nous avons réussi ou échoué.
>> Comment pouvons-nous échouer?
Qu'est-ce que la seule circonstance que vous pouvez penser
où nous aurions besoin de retourner faux?
Ouais.
[Étudiants] Si elle est pleine et nous utilisons une application bornée.
Ouais, alors comment pouvons-nous définir-il répondu
si elle est pleine et nous utilisons une application bornée.
Ensuite, nous reviendrons assurément faux.
Dès que nous avons atteint 10 choses dans le tableau, nous ne pouvons pas répondre à 11, donc on retourne faux.
Et si ce n'est pas borné? Ouais.
Si vous ne pouvez pas développer le réseau pour une raison quelconque.
Ouais, et alors la mémoire est une ressource limitée,
et finalement, si nous gardons les choses qui poussent sur la pile, encore et encore,
nous allons essayer et d'allouer un tampon plus grand pour s'adapter
la plus grande capacité, et malloc ou quoi que nous utilisons va renvoyer false.
Eh bien, malloc retourne null.
>> Rappelez-vous, chaque fois que vous jamais appeler malloc, vous devriez vérifier pour voir si elle
renvoie la valeur null ou bien c'est une déduction correcte.
Puisque nous voulons avoir une pile infinie,
le seul cas que nous allons être de retour est faux si nous essayons de
accroître la capacité et malloc ou quoi renvoie false.
Puis pop ne prend aucun argument,
et il renvoie la chaîne qui se trouve sur le dessus de la pile.
Quels qu'aient été les plus récemment poussé sur la pile est ce que la pop est de retour,
et il a également le retire de la pile.
Et remarquez qu'il retourne null s'il n'y a rien sur la pile.
Il est toujours possible que la pile est vide.
En Java, si vous êtes habitué à cela, ou d'autres langues,
essayent d'éclater à partir d'une pile vide peut provoquer une exception ou quelque chose.
>> Mais en C, null est une sorte de grand nombre de cas, la façon dont nous traitons ces problèmes.
Retournant une valeur null est de savoir comment nous allons indiquer que la pile est vide.
Nous avons fourni un code qui permettra de tester les fonctionnalités de votre pile, le
mettre en œuvre push et pop.
Ce ne sera pas une grande quantité de code.
Je le ferai-réalité, avant de faire cela, hint, hint-
si vous ne l'avez pas vu, malloc n'est pas la seule fonction
qui alloue la mémoire sur le tas pour vous.
Il ya une famille de fonctions alloc.
La première est malloc, que vous êtes habitué.
Ensuite, il ya calloc, qui fait la même chose que malloc,
mais il se met à zéro tout pour vous.
Si vous avez toujours voulu tout mettre à null après allouer de quelque chose
vous devriez venez d'utiliser calloc en premier lieu au lieu d'écrire
une boucle for à zéro sur l'ensemble du bloc de mémoire.
>> Realloc est comme malloc et a beaucoup de cas particuliers,
mais, fondamentalement, ce qui ne fait que realloc
il prend un pointeur qui avaient déjà été alloués.
Realloc est la fonction que vous voulez prêter attention à ici.
Il prend un pointeur qui avait déjà été renvoyé par malloc.
Disons que vous demandez à malloc un pointeur de 10 octets.
Puis, plus tard vous vous rendez compte que vous vouliez 20 octets,
si vous appelez realloc sur ce pointeur de 20 octets,
et realloc automatiquement copier tout pour vous.
Si vous venez d'appeler malloc encore une fois, comme je l'ai un bloc de 10 octets.
Maintenant, j'ai besoin d'un bloc de 20 octets,
donc si je malloc 20 octets, alors je dois copier manuellement au cours des 10 octets à partir de la première chose
dans la deuxième chose, puis la première chose gratuitement.
Realloc se chargera pour vous.
>> Notez la signature va être void *,
qui est juste en renvoyant un pointeur vers le bloc de mémoire,
puis void * ptr.
Vous pouvez penser void * comme un pointeur générique.
En règle générale, vous n'avez jamais traiter avec void *,
mais malloc retourne un void *, puis il est juste utilisé comme
ce qui se passe réellement comme un char *.
Le void * précédent, qui avait été renvoyée par malloc
va maintenant être transmis à realloc, puis la taille
est le nouveau numéro d'octets que vous souhaitez allouer, de sorte que votre nouvelle capacité.
Je vais vous donner quelques minutes, et de le faire dans notre espace.
Commencez avec la révision 1.
Je vous arrête, après espérons propos de suffisamment de temps pour mettre en œuvre poussoir,
et puis je vais vous donner une autre pause pour faire pop.
Mais ce n'est vraiment pas ce code beaucoup à tous.
La plupart du code est sans doute le truc en expansion, expansion de la capacité.
Ok, pas de pression pour être complètement terminé,
mais aussi longtemps que vous vous sentez comme vous êtes sur la bonne voie, c'est bien.
>> Quelqu'un at-il un code qu'ils se sentent à l'aise avec moi tirant vers le haut?
Ouais, je le ferai, mais quelqu'un at-il un code que je peux tirer vers le haut?
Ok, pouvez-vous commencer, sauvegardez, quel qu'il soit?
J'oublie toujours cette étape.
Bon, en regardant pousser,
voulez-vous expliquer votre code?
[Étudiants] Tout d'abord, j'ai augmenté la taille.
Je suppose que je devrais peut-être que, de toute façon, j'ai augmenté la taille,
et je vois si elle est inférieure à la capacité.
Et si elle est inférieure à la capacité, je ajouter dans le tableau que nous avons déjà.
Et si ce n'est pas le cas, je multiplie la capacité par 2,
et je réaffecter l'ensemble des chaînes à quelque chose avec une taille plus grande capacité actuellement.
Et puis, s'il échoue, je dis à l'utilisateur et retourner false,
et si tout va bien, puis j'ai mis la chaîne dans le nouveau spot.
>> [Rob B.] Notez également que nous avons utilisé un opérateur bit à bit agréable ici
à multiplier par 2.
Rappelez-vous, décalage à gauche est toujours va être multiplié par 2.
Décalage vers la droite est divisée par 2 tant que vous vous souvenez que cela signifie
diviser par 2 comme dans un entier divisé par 2.
Il pourrait tronquer un 1 ici ou là.
Mais décalage à gauche de 1 est toujours va être multiplié par 2,
à moins que vous déborder les limites de l'entier, et alors il ne sera pas.
Une remarque.
J'aime faire-cela ne va pas changer le codage d'une manière quelconque,
mais je voudrais faire quelque chose comme ça.
Il va réellement se rendre un peu plus longtemps.
Peut-être que ce n'est pas le cas parfait pour le montrer,
mais je tiens à le segmenter en ces blocs de-
ok, si ce qui se passe si, alors je vais faire quelque chose,
puis la fonction est réalisée.
Je n'ai pas besoin de faire défiler, puis mes yeux tout le long de la fonction
pour voir ce qui se passe après l'autre.
C'est le cas de ce qui se passe si, alors je viens de revenir.
Il a également l'avantage bien agréable de tout au-delà de ce
est maintenant décalé vers la gauche une fois.
Je n'ai plus besoin à proximité si vous avez déjà ridiculement longues files d'attente,
alors ces 4 octets peut vous aider, ainsi que la gauche est quelque chose de plus,
le moins accablé si vous vous sentez comme-bien, je dois me rappeler
Je suis actuellement dans une boucle while à l'intérieur d'une autre à l'intérieur d'une boucle for.
Partout où vous pouvez faire ce retour tout de suite, j'aime bien.
Il est totalement facultative et ne devrait en aucune façon.
>> [Étudiants] Faut-il une taille - dans l'état sûr?
La condition est sûr ici nous n'avons pas réussi à realloc, alors oui.
Remarquez comment dans l'état sûr, sans doute,
à moins que nous des trucs gratuits plus tard, nous sommes toujours voué à l'échec
peu importe combien de fois nous essayons de pousser quelque chose.
Si nous continuons à pousser, nous gardons la taille d'incrémentation,
même si nous ne mettons pas tout sur la pile.
Habituellement, nous ne incrémenter la taille jusqu'à ce
après nous avons réussi à le mettre sur la pile.
Nous le ferions, par exemple, que ce soit ici et ici.
Et puis, au lieu de dire s.size capacité ≤, c'est moins de capacité,
seulement parce que nous nous sommes déplacés où tout était.
>> Et rappelez-vous, le seul endroit où nous pourrions retourner faux
C'est ici, où realloc retourné null,
et s'il vous arrive de se rappeler d'erreur standard,
peut-être vous pourriez envisager ce cas, un endroit où vous voulez imprimer une erreur-type,
stderr afin fprintf au lieu de simplement imprimer directement sur la sortie standard.
Encore une fois, ce n'est pas une attente, mais si c'est une erreur,
tapez printf, alors vous voudrez peut-être faire imprimer sur la sortie standard au lieu de la sortie standard.
>> Quelqu'un at-il autre chose à noter? Oui.
[Étudiants] Pouvez-vous revenir sur la [inaudible]?
[Rob B.] Oui, le caractère binaire réelle de celui-ci ou tout simplement ce que c'est?
[Étudiants] Donc, vous le multipliez par 2?
[Rob B.] Ouais, en gros.
Dans la terre binaire, nous avons toujours notre série de chiffres.
Le passage de cette gauche de 1 Fondamentalement, il insère ici sur le côté droit.
Retour à cela, il suffit de se rappeler que tout en binaire
est une puissance de 2, cela représente donc 2 au 0,
2 à la présente 1, 2 présente au 2.
En insérant un 0 à droite maintenant, nous venons de passer tout entier.
Ce qui était de 2 à 0 est maintenant 2 à 1, est 2 à la 2.
Le côté droit que nous avons inséré
va nécessairement être égal à 0,
ce qui est logique.
Si jamais vous multiplier un nombre par 2, ça ne va pas finir impair,
de sorte que le 2 à la place 0 doit être égal à 0,
et c'est ce que j'ai mis en garde contre moitié avant est que si vous ne vous arrive de passer
au-delà du nombre de bits dans un entier,
alors ce 1 va finir par s'éteindre.
C'est le seul souci s'il vous arrive d'avoir affaire avec des capacités très grandes.
Mais à ce moment, alors vous avez affaire à un tableau de milliards de choses,
qui pourrait ne pas tenir dans la mémoire de toute façon.
>> Maintenant, nous pouvons arriver à la pop, ce qui est encore plus facile.
Vous pouvez faire comme si vous arrive d'apparaître tout un tas,
et maintenant vous êtes à la moitié de sa capacité à nouveau.
Vous pouvez realloc pour réduire la quantité de mémoire dont vous disposez,
mais vous n'avez pas à vous soucier de ce que, si le cas realloc ne sera
de plus en plus de mémoire, jamais rétrécissement de la mémoire,
qui va faire pop super-facile.
Maintenant, les files d'attente qui vont être comme des piles,
mais l'ordre dans lequel vous prenez les choses est inversé.
L'exemple type d'une file d'attente est une ligne,
donc je suppose que si vous étiez en anglais, je vous aurais dit
un exemple type d'une file d'attente est une file d'attente.
Donc, comme une ligne, si vous êtes la première personne en ligne,
vous vous attendez à être la première personne hors de la ligne.
Si vous êtes la dernière personne en ligne, vous allez être la dernière personne desservie.
Nous appelons ce modèle FIFO, alors que la pile LIFO est tendance.
Ces mots sont assez universel.
>> Comme les piles et au contraire des tableaux, des files d'attente, généralement, ne permettent pas l'accès aux éléments du milieu.
Ici, une pile, nous avons push et pop.
Ici, il nous arrive d'avoir appelé les enqueue et dequeue.
J'ai aussi entendu les appelait changement et unshift.
J'ai entendu des gens dire push et pop pour s'appliquer également aux files d'attente.
J'ai entendu insérer, supprimer,
de sorte push et pop, si vous parlez des piles, vous poussez et popping.
Si vous parlez de files d'attente, vous pouvez choisir les mots que vous souhaitez utiliser
pour l'insertion et le retrait, et il n'y a pas de consensus sur ce que devrait être appelé.
Mais ici, nous avons enqueue et dequeue.
Maintenant, la structure est presque identique à la structure de la pile.
Mais nous devons garder la trace de la tête.
Je suppose que c'est dit ici, mais pourquoi avons-nous besoin de la tête?
Les prototypes sont fondamentalement identiques à pousser et pop.
Vous pouvez penser que c'est push et pop.
La seule différence est la pop est de retour au lieu de la dernière, il est le premier retour.
2, 1, 3, 4, ou quelque chose.
Et voici le début.
Notre file d'attente est pleine, il ya donc quatre éléments qu'il contient.
La fin de notre file d'attente est actuellement de 2,
et maintenant nous allons insérer quelque chose d'autre.
>> Quand on veut insérer cette autre chose, ce que nous avons fait pour la version pile
est nous avons étendu notre bloc de mémoire.
Quel est le problème avec ça?
[Étudiants] Vous déplacez le 2.
Ce que j'ai dit avant sur la fin de la file d'attente,
ce n'est pas logique que nous commencions à 1,
alors nous voulons dequeue 1, puis dequeue 3, puis dequeue 4,
puis dequeue 2, puis dequeue celui-ci.
Nous ne pouvons pas utiliser realloc maintenant,
ou à tout le moins, vous devez utiliser realloc d'une manière différente.
Mais vous ne devriez pas simplement utiliser realloc.
Vous allez avoir à copier manuellement votre mémoire.
>> Il ya deux fonctions pour copier la mémoire.
Il ya memcopy et memmove.
Je suis en train de lire les pages de manuel pour trouver celui qui vous allez avoir à utiliser.
Bon, memcopy, la différence est
que memcopy et memmove, on manipule correctement le cas
où vous voulez copier dans une région qui se trouve à chevaucher la région
vous copiez à partir.
Memcopy ne pas y faire face. Memmove fait.
Vous pouvez penser que le problème-
disons que je veux copier ce gars-là,
ces quatre à ce gars-dessus.
En fin de compte, ce que le tableau devrait ressembler à
une fois la copie 2, 1, 2, 1, 3, 4, puis des trucs à la fin.
Mais cela dépend de l'ordre dans lequel nous avons fait copier,
car si nous ne considérons pas le fait que la région nous copier dans
chevauche celui que nous la copie de son
alors nous pourrions faire comme début ici, copier les 2 dans l'endroit où nous voulons aller,
puis déplacez les pointeurs vers l'avant.
>> Maintenant, nous allons être ici et ici, et maintenant nous voulons copier
ce mec sur ce gars et faire avancer nos pointeurs vers l'avant.
Ce que nous allons finir par avoir est de 2, 1, 2, 1, 2, 1
au lieu de la 2 appropriée, 1, 2, 1, 3, 4, car
2, 1 emportait sur l'original 3, 4.
Memmove gère cela correctement.
Dans ce cas, fondamentalement juste toujours utiliser memmove
parce qu'il le gère correctement.
Il n'est généralement pas effectuer de pire.
L'idée est plutôt de partir de début et la copie de cette façon
comme nous venons de faire ici, il commence à partir de la fin et copie dans,
et dans ce cas, vous ne pouvez jamais avoir un problème.
Il n'existe pas de perte de performance.
Toujours utiliser memmove. Ne vous souciez plus memcopy.
Et c'est là que vous allez devoir séparément Memmove
la portion enroulée autour de votre-file d'attente.
Pas de soucis si elle n'est pas complètement terminé.
C'est plus difficile que pile, push et pop.
>> N'importe qui ont n'importe quel code on pouvait travailler avec?
Même si complètement incomplète?
[Étudiants] Oui, c'est tout à fait incomplète, cependant.
Complètement incomplet est très bien tant que nous, on peut économiser de la révision?
J'ai oublier que chaque fois unique.
Bon, ignorant ce qui se passe quand nous avons besoin de redimensionner les choses.
Ignorer complètement redimensionnement.
Expliquez ce code.
Je vérifie tout d'abord si la taille est inférieure à la première copie de tous les
et puis après ça, je insérez-je prendre la tête + taille,
et je m'assure qu'il s'enroule autour de la capacité de la matrice,
et je insérer la nouvelle chaîne à cette position.
Puis-je augmenter la taille et renvoie true.
>> [Rob B.] C'est certainement l'un de ces cas où vous allez vouloir utiliser mod.
Tout type de cas où vous avez enroulant autour, si vous pensez enroulant autour,
la pensée immédiate devrait être mod.
Comme une optimisation rapide / rendre votre code une ligne plus courte,
vous remarquerez que la ligne qui suit immédiatement celui-ci
est juste la taille + +, donc vous fusionnez que dans cette ligne, la taille + +.
Maintenant, ici-bas, nous avons le cas
où nous n'avons pas assez de mémoire,
si nous augmentons notre capacité de 2.
Je suppose que vous pourriez avoir le même problème ici, mais nous pouvons l'ignorer maintenant,
où si vous n'avez pas d'augmenter votre capacité,
alors vous allez avoir à diminuer votre capacité de 2 à nouveau.
Une autre brève note est juste comme vous pouvez le faire + =,
vous pouvez également faire << =.
Presque tout peut aller devant égaux, + =, | =, & =, << =.
Char * nouveau, c'est notre nouveau bloc de mémoire.
Oh, là-bas.
>> Qu'est-ce que les gens pensent au sujet du type de notre nouveau bloc de mémoire?
[Étudiants] Il devrait être char **.
En repensant à notre structure ici,
cordes est ce que nous réaffectation.
Nous faisons un ensemble de stockage nouvelle dynamique pour les éléments dans la file d'attente.
Ce que nous allons attribuer à vos chaînes est ce que nous allouer de ce moment,
et si nouvelle va être de type char **.
Il va y avoir un tableau de chaînes.
Alors quel est le cas en vertu de laquelle nous allons revenir faux?
[Étudiants] Devrions-nous faire la char *?
[Rob B.] Oui, bonne idée.
[Étudiants] Qu'est-ce que c'était?
[Rob B.] Nous voulions faire la taille de char *, car nous ne sommes plus-
ce serait en fait un très gros problème parce que sizeof (char) serait de 1.
Char * sizeof va être de 4,
de sorte que beaucoup de fois quand vous faites affaire avec des entiers,
vous avez tendance à sortir avec elle parce que la taille de int et la taille de int *
sur un système 32-bit va être la même chose.
Mais ici, sizeof (char) et sizeof (char *) sont désormais va être la même chose.
>> Quelle est la situation où l'on retourne faux?
[Étudiants] Nouveau est nulle.
Oui, si le nouveau est nul, on retourne faux,
et je vais jeter ici-
[Étudiants] [inaudible]
[Rob B.] Oui, c'est très bien.
Vous pouvez soit le faire 2 fois la capacité ou 1 quart capacité et ensuite seulement le mettre ici-bas ou ailleurs.
Nous allons le faire comme nous l'avions.
Capacité >> = 1.
Et vous n'allez jamais avoir à vous inquiéter de perdre sa place le 1
parce que vous avez quitté décalée de 1, donc les 1 endroit est nécessairement un 0,
donc décaler à droite par 1, vous allez toujours bien.
[Étudiants] Avez-vous besoin de le faire avant le retour?
[Rob B.] Oui, cela n'a absolument aucun sens.
>> Supposons maintenant que nous allons finir par retourner true à la fin.
La façon dont nous allons faire ces memmoves,
nous devons faire attention à la façon dont nous le faisons.
Est-ce que quelqu'un a des suggestions sur la façon dont nous le faisons?
Voici notre départ.
Inévitablement, nous voulons commencer au début de nouveau
copie et les choses à partir de là, 1, 3, 4, 2.
Comment faites-vous cela?
Tout d'abord, je dois regarder à la page de manuel de memmove nouveau.
Memmove, l'ordre des arguments est toujours important.
Nous voulons que notre destination première, deuxième source d', troisième dimension.
Il ya beaucoup de fonctions qui inversent source et la destination.
Destination, d'origine a tendance à être un peu cohérente.
Déplacer, quel est-il de retour?
Elle renvoie un pointeur vers la destination, quelle qu'en soit la raison, vous voudrez peut-être cela.
Je peux le lire image, mais nous voulons aller dans notre destination.
>> Quelle est notre destination va être?
[Étudiants] Nouveau.
[Rob B.] Oui, et où allons-nous à partir de la copie?
La première chose que nous la copie est-ce 1, 3, 4.
Qu'est-ce que la mention-cette 1, 3, 4.
Quelle est l'adresse de ce 1?
[Étudiants] [inaudible]
[Rob B.] Tête + l'adresse du premier élément.
Comment pouvons-nous obtenir le premier élément dans le tableau?
[Étudiants] file d'attente.
[Rob B.] Oui, q.strings.
Rappelez-vous, ici, notre tête est de 1.
Bon sang. Je pense que c'est juste magique-
Ici, notre tête est de 1. Je vais changer ma couleur aussi.
Et voici cordes.
Cela, nous pouvons soit l'écrire comme nous l'avons fait ici
avec des têtes + q.strings.
Beaucoup de gens aussi écrire et q.strings [la tête].
Ce n'est pas vraiment moins efficace.
Vous pourriez penser que c'est vous le déréférencement, puis obtenir l'adresse d',
mais le compilateur va traduire ce que nous avions avant de toute façon, q.strings + tête.
De toute façon vous voulez penser.
>> Et combien d'octets que nous voulons copier?
[Étudiants] Capacité - tête.
Capacité - tête.
Et puis, vous pouvez toujours écrire sur un exemple
de voir si c'est vrai.
[Étudiants] Il doit être divisé par 2, alors.
Ouais, donc je suppose que nous pourrions utiliser la taille.
Nous avons encore la taille étant-
en utilisant la taille, on a une taille égale à 4.
Notre taille est de 4. Notre tête est 1.
Nous voulons copier ces 3 éléments.
C'est la vérification que cette taille - tête est correctement 3.
Et revenir ici, comme nous l'avons déjà dit,
si nous avons utilisé la capacité, alors nous aurions à diviser par 2
parce que nous avons déjà augmenté notre capacité, donc au lieu, nous allons utiliser la taille.
Que des copies de cette partie.
Maintenant, nous avons besoin de copier l'autre partie, la partie qui est à gauche du début.
>> Cela va Memmove dans quelle position?
[Étudiants] Taille Plus - tête.
Oui, nous avons déjà copié en taille - octets tête,
et donc où nous voulons copier les octets restants est nouveau
puis la taille minus-même, le nombre d'octets que nous avons déjà copié po
Et puis, où allons-nous à partir de la copie?
[Étudiants] Q.strings [0].
[Rob B.] Oui, q.strings.
On pourrait soit faire et q.strings [0].
Ce chiffre est nettement moins fréquent que cela.
Si ça va juste être 0, alors vous aurez tendance à voir q.strings.
C'est là que nous copiant à partir.
Combien d'octets ne nous reste à copier? >> [Étudiants] 10.
Droite.
[Étudiants] Faut-il multiplier 5 à 10 fois la taille des octets ou quelque chose?
Ouais, donc c'est de là qu'est-ce exactement que nous la copie?
[Étudiants] [inaudible]
Quel est le type de chose que nous la copie?
[Étudiants] [inaudible]
Ouais, donc le char * s que nous vous copiez, nous ne savons pas où ceux-ci sont en venir.
Eh bien, là où ils sont pointant vers, comme les cordes, on finit par le pousser vers la file d'attente
ou mise en file sur la file d'attente.
Lorsque les personnes viennent, nous n'avons aucune idée.
Nous avons juste besoin de garder une trace de la char * s eux-mêmes.
Nous ne voulons pas copier taille - octets tête.
Nous voulons copier taille - tête char * s,
donc nous allons multiplier par sizeof (char *).
Même ici-bas, la tête * sizeof (char *).
>> [Étudiants] Qu'en est-il [inaudible]?
Ce droit ici?
[Étudiants] Non, en dessous, la taille - tête.
[Rob B.] Ce droit ici?
L'arithmétique des pointeurs.
Comment l'arithmétique des pointeurs est d'aller travailler est
il se multiplie automatiquement par la taille du type que nous avons affaire.
Tout comme ici, nouvelle + (taille - tête)
est exactement équivalente à & [size - tête] nouveau
jusqu'à ce que nous nous attendons à ce que pour fonctionner correctement,
car si nous avons affaire à un tableau int, alors nous n'avons pas d'index par int-
ou si elle est de taille 5 et que vous voulez le 4ème élément, puis nous index dans la
int tableau [4].
Vous ne-[4] * taille de int.
Qu'il gère automatiquement, et dans ce cas
est littéralement équivalent, de sorte que le support de la syntaxe
va juste être converties à ce que dès que vous compilez.
C'est quelque chose que vous devez faire attention à ce que
lorsque vous ajoutez taille - tête
vous ajoutez pas un octet.
Vous n'êtes ajoutant un char *, qui peut être un octets ou quoi que ce soit.
>> D'autres questions?
Bon, dequeue va être plus facile.
Je vais vous donner une minute pour mettre en œuvre.
Oh, et je suppose que c'est la même situation
ce le cas enqueue, si nous sommes mise en file nulle,
peut-être que nous voulons y faire face, peut-être nous n'avons pas.
Nous n'allons pas refaire ici, mais même notre cas pile.
Si nous en file d'attente nulle, nous pourrions en faire abstraction.
N'importe qui ont un peu de code que je peux tirer vers le haut?
[Étudiants] J'ai juste dequeue.
La version 2 est que-bien.
Vous cherchez à faire?
[Étudiants] Tout d'abord, vous assurez-vous qu'il ya quelque chose dans la file d'attente
et que la taille est en baisse de 1.
Vous avez besoin de faire ça, et puis vous revenez la tête
et puis déplacez la tête jusqu'à 1.
Ok, donc il ya un cas coin, nous avons à considérer. Ouais.
[Étudiants] Si votre tête est au dernier élément,
alors vous ne voulez pas la tête pour pointer en dehors du tableau.
>> Oui, dès que la tête arrive à la fin de notre tableau,
quand nous dequeue, notre tête doit être modded à 0.
Malheureusement, nous ne pouvons pas le faire en une seule étape.
Je pense que la façon dont je serais probablement fixer, il est
cela va être un char *, ce que nous retournant,
quel que soit votre nom de variable veut être.
Ensuite, nous voulons mod tête par notre capacité
puis revenir ret.
Beaucoup de gens ici, ils pourraient faire-
c'est le cas de-vous verrez les gens faire si la tête
est supérieure à la capacité, faire la tête - la capacité.
Et qui vient travailler autour de ce mod est.
Chef mod = capacité est beaucoup plus propre
d'un emballage autour de la tête, si supérieure à la capacité de la tête - la capacité.
>> Des questions?
Ok, la dernière chose que nous avons laissé notre liste chaînée.
Vous pourriez être utilisé pour une partie du comportement liste chaînée si vous avez fait
des listes liées dans vos tables de hachage, si vous avez une table de hachage.
Je recommande fortement de faire une table de hachage.
Vous avez sans doute déjà fait un trie,
mais essais sont plus difficiles.
En théorie, ils sont asymptotiquement meilleur.
Mais il suffit de regarder le grand tableau,
et tente jamais faire mieux, et ils prennent plus de mémoire.
Tout à propos de tente finit par être pire pour les plus de travail.
C'est ce que David Malan solution est toujours
est-il toujours sa solution trie les messages, et voyons où il est actuellement.
Quel était-il sous, David J?
Il est n ° 18, si ce n'est pas terriblement mauvais,
et que ça va être l'un des meilleurs essais, vous pouvez penser
ou l'un des meilleurs essaie d'une structure arborescente.
N'est-il pas même sa solution originale?
Je me sens comme solutions de structure arborescente ont tendance à être plus dans cette gamme de utilisation de la RAM.
>> Aller en bas à en haut, et l'utilisation de la RAM est à un seul chiffre.
Descendez vers le bas, puis vous commencez à voir essaie
où vous aurez utilisation de la RAM absolument gigantesque,
et essais sont plus difficiles.
Pas tout à fait la peine, mais une expérience éducative si vous avez un.
La dernière chose est de notre liste chaînée,
et ces trois choses, piles, files et listes chaînées,
quelque chose de l'avenir vous jamais faire en informatique
supposerons que vous avez connaissance de ces choses.
Ils sont tellement fondamentale pour tout.
>> Listes chaînées, et ici nous avons une liste simplement chaînée va être notre mise en œuvre.
Qu'est-ce que signifie simplement chaînée par opposition aux doublement chaînée? Oui.
[Étudiants] Il souligne que pour que le pointeur suivant plutôt que de les pointeurs,
comme celui qui le précède et celle d'après.
Ouais, donc au format image, qu'est-ce que je viens de faire?
J'ai deux choses. J'ai image et l'image.
Dans le format d'image, nos individuellement listes chaînées,
inévitablement, nous avons une sorte de pointeur à la tête de notre liste,
puis au sein de notre liste, nous avons juste des pointeurs,
et peut-être cela indique une valeur nulle.
Ça va être votre dessin typique d'une liste simplement chaînée.
Une liste doublement chaînée, vous pouvez revenir en arrière.
Si je vous donne un nœud dans la liste, vous pouvez alors nécessairement se rendre à
un autre noeud dans la liste si elle est une liste doublement chaînée.
Mais si je te le troisième noeud dans la liste et c'est une liste simplement chaînée,
aucun moyen que vous allez jamais à obtenir les premier et second noeuds.
Et il ya des avantages et des inconvénients, et un plus évident
est vous prendre plus de taille, et vous devez garder une trace de l'endroit où ces choses sont pointant maintenant.
Mais nous ne se soucient simplement chaînée.
>> A peu de choses que nous allons devoir mettre en œuvre.
Votre typedef struct noeud, int i: struct noeud * suivant; nœud.
C'est typedef devrait être gravée dans votre esprit.
Quiz 1 doit être comme donner un typedef d'un nœud de liste chaînée,
et vous devriez être en mesure de mettre immédiatement griffonner que vers le bas
sans même y penser.
Je suppose que quelques questions, pourquoi avons-nous besoin struct ici?
Pourquoi ne peut-on pas dire noeud *?
[Étudiants] [inaudible]
Ouais.
La seule chose qui définit un noeud comme une chose
typedef est la même.
Mais à partir de ce point, lorsque nous sommes en quelque sorte l'analyse par cette définition struct noeud,
nous n'avons pas fini notre typedef encore, donc depuis le typedef n'est pas terminée,
noeud n'existe pas.
Mais struct noeud fait, et ce noeud ici,
cela pourrait aussi être appelé n'importe quoi d'autre.
Cela pourrait être appelé n.
Il pourrait être appelé nœud de liste chaînée.
Il pourrait être appelé n'importe quoi.
Mais ce noeud struct doit être appelé la même chose que ce noeud struct.
Ce que vous appelez cela doit aussi être ici,
et de telle sorte que répond également au second point de la question
C'est pourquoi, beaucoup de fois quand vous voyez structs et typedefs de structures,
vous verrez les structures anonymes où vous ne verrez typedef struct,
mise en œuvre de la structure, un dictionnaire, ou autre chose.
>> Pourquoi avons-nous besoin ici de dire nœud?
Pourquoi ne peut-il pas être une struct anonyme?
C'est presque la même réponse.
[Étudiants] Vous avez besoin de s'y référer dans la structure.
Oui, au sein de la structure, vous devez vous référer à la structure elle-même.
Si vous ne donnez pas la structure d'un nom, si c'est une struct anonyme, vous ne pouvez pas faire référence.
Et enfin et surtout, celles-ci ne devraient tous être un peu simple,
et ils devraient vous aider à réaliser si vous écrivez cela sur
que vous faites quelque chose de mal, si ce genre de choses n'ont pas de sens.
Last but not least, pourquoi cela at-il pour être struct noeud *?
Pourquoi ne pas simplement être struct noeud suivant?
[Étudiants] Pointeur vers la structure suivante.
C'est forcément ce que nous voulons.
Pourquoi ne pourrait-il jamais être struct noeud prochaine?
Pourquoi faut-il que le noeud de struct * à côté? Ouais.
[Étudiants] C'est comme une boucle infinie.
Ouais.
[Étudiants] Tout serait à la fois.
Oui, il suffit de penser comment nous ferions taille ou quelque chose.
Taille d'une structure est fondamentalement + ou - une tendance ici ou là.
C'est fondamentalement va être la somme des tailles des choses dans la structure.
Ce droit ici, sans rien changer, la taille va pas être facile.
Taille de noeud struct va être la taille de i + taille de la prochaine.
Taille de i va être 4. Taille de la prochaine va être 4.
Taille de noeud struct va être 8.
Si nous n'avons pas l'*, en pensant à sizeof,
puis sizeof (i) va être 4.
Taille de noeud struct est la prochaine va être la taille de i + taille du noeud struct prochaine
Taille + taille + i du nœud de structure suivante.
Ce serait une récursion infinie de nœuds.
C'est pourquoi c'est comme ça que les choses doivent être.
>> Encore une fois, c'est sûr que mémoriser,
ou au moins le comprendre assez que vous pouvez être en mesure de
la raison par la quelle il devrait ressembler.
Les choses que nous allons vouloir mettre en œuvre.
Si la longueur de la liste,
vous pouvez tricher et garder autour d'un
durée globale ou quelque chose, mais nous n'allons pas le faire.
Nous allons compter la longueur de la liste.
Nous avons contient, de sorte que c'est fondamentalement comme une recherche,
nous avons donc une liste chaînée d'entiers pour voir si cet entier est dans la liste chaînée.
Préfixe va insérer au début de la liste.
Append va insérer à la fin.
Insert_sorted va insérer dans la position dans la liste triée.
Type de Insert_sorted suppose que vous n'avez jamais utilisé prepend ou ajouter dans de mauvaises manières.
>> Insert_sorted lorsque vous implémentez insert_sorted-
disons que nous avons notre liste chaînée.
C'est ce que cela ressemble actuellement, 2, 4, 5.
Je veux insérer 3, tant et aussi longtemps que la liste elle-même est déjà trié,
il est facile de trouver où 3 appartient.
Je commence à 2.
Okay, 3 est supérieur à 2, alors je veux continuer.
Oh, 4 est trop grand, donc je sais pas 3 va passer entre 2 et 4,
et je dois fixer des pointeurs et tous ces trucs.
Mais si nous n'avons pas strictement d'utiliser insert_sorted,
comme nous allons simplement dire que je préfixer 6,
puis ma liste chaînée va devenir cela.
Il fait maintenant aucun sens, donc pour insert_sorted, vous pouvez simplement supposer
que la liste est triée, même si les opérations existent
qui peut l'amener à ne pas être triés, et c'est tout.
Trouver un insert utiles afin que ceux-sont les principales choses que vous allez avoir à mettre en œuvre.
>> Pour l'instant, prenez une minute pour faire la longueur et contient,
et ceux-ci devraient être relativement rapide.
Presque l'heure de fermeture, si quelqu'un a quelque chose pour la longueur ou contient?
Ils vont être à peu près identique.
[Étudiants] Longueur.
Voyons, révision.
D'accord.
Vous cherchez à faire?
[Étudiants] Je viens de créer un nœud de pointeur et l'initialiser d'abord, qui est notre variable globale,
puis-je vérifier pour voir si elle est nulle si je ne reçois pas un défaut segments et renvoient 0 si c'est le cas.
Sinon, je boucle, garder une trace de l'intérieur entier
combien de fois j'ai accédé à l'élément suivant de la liste
et dans la même opération d'incrémentation également accéder à cet élément réel,
et puis je continue faire la vérification pour voir si elle est nulle,
et si elle est nulle, alors il abandonne et retourne simplement le nombre d'éléments que j'ai consultés.
>> [Rob B.] Est-ce que quelqu'un a des commentaires sur quelque chose?
Cela semble correct bien sage.
[Étudiants] Je ne pense pas que vous devez le noeud == null.
Ouais, donc si le noeud == 0 return null.
Mais si le noeud == null alors ce-oh, il ya un problème de justesse.
C'était juste vous i retour, mais ce n'est pas dans la portée en ce moment.
Vous avez juste besoin int i, si i = 0.
Mais si le noeud est nulle, alors je continue toujours à 0,
et nous allons retourner 0, si ce cas est identique.
Un autre point commun est de conserver la déclaration
du noeud à l'intérieur de la boucle for.
Vous pourriez dire: oh, non.
Restons comme ça.
Je serais probablement mis int i = 0 ici,
alors noeud noeud * = première ici.
Et c'est sans doute comment-se débarrasser de cela maintenant.
C'est probablement la façon dont je l'ai écrit.
Vous pouvez aussi regarder-comme celui-ci.
Cette structure de boucle pour ici
devrait être presque aussi naturel pour vous que pour int i = 0
i est inférieure à la longueur de la rangée i + +.
Si c'est comme ça que vous itérer sur un tableau, c'est la façon dont vous itérer sur une liste chaînée.
>> Cela devrait être une seconde nature à un moment donné.
Avec cela à l'esprit, ce sera presque la même chose.
Vous allez avoir à parcourir une liste chaînée.
Si le nœud-Je n'ai aucune idée de ce que la valeur est appelée.
I nœud.
Si la valeur de ce noeud = i return true, et c'est tout.
Notez que la seule façon que nous ayons jamais retourner faux
si nous parcourir la liste entière liée et ne jamais revenir vrai,
si c'est ce que cela fait.
Comme un côté la note, nous n'obtiendrez probablement pas d'ajouter ou de précéder.
>> Rapide dernière note.
Si vous voyez le mot-clé static, alors disons statique int count = 0,
puis nous faisons count + +, vous pouvez tout simplement penser que c'est une variable globale,
même si je viens de le dire, ce n'est pas comment nous allons mettre en œuvre longueur.
Je le fais ici, et puis compter + +.
De toute façon, nous pouvons entrer un nœud dans notre liste chaînée nous incrémentation notre compte.
Le but de cela est ce que signifie le mot clé static.
Si je devais int count = 0 ce serait un habitué ancienne variable globale.
Que statique moyens int count, c'est qu'il est une variable globale pour ce fichier.
Il est impossible pour un autre fichier,
comme penser pset 5, si vous avez commencé.
Vous avez les deux speller.c, et vous avez dictionary.c,
et si vous venez de déclarer une chose globale, puis quelque chose dans speller.c
est accessible en dictionary.c et vice versa.
Les variables globales sont accessibles par n'importe quel fichier. C,
mais les variables statiques sont accessibles uniquement depuis le fichier lui-même,
donc à l'intérieur du vérificateur d'orthographe ou à l'intérieur de dictionary.c,
c'est un peu de la façon dont je déclarer ma variable pour la taille de mon tableau
ou la taille de mon nombre de mots dans le dictionnaire.
Comme je ne veux pas déclarer une variable globale que l'on ait accès à
J'ai vraiment ne se soucient que pour mes propres fins.
>> La bonne chose à ce sujet est aussi le nom de l'ensemble des choses collision.
Si un autre fichier tente d'utiliser une variable globale appelée comte, les choses vont mal, très mal,
si ça continue bien sûr les choses, et vous seul pouvez y accéder,
et nul autre ne peut, et si quelqu'un d'autre déclare une variable globale appelée comte,
il ne sera pas interférer avec votre variable statique appelée comptage.
C'est ce qui est statique. C'est une variable fichier global.
>> Questions sur quoi que ce soit?
Tous ensemble. Bye.
[CS50.TV]