[Powered by Google Translate] [Section 6: Moins confortable] [Nate Hardison] [Université de Harvard] [C'est CS50.] [CS50.TV] Très bien. Bienvenue à la section 6. Cette semaine, nous allons parler de structures de données en coupe, principalement parce que le problème de cette semaine mis sur spellr fait un tas d'exploration structure différente des données. Il ya un tas de façons différentes que vous pouvez aller avec le problème posé, et les structures de données plus vous en savez, plus les choses cool que vous pouvez faire. 

Donc, nous allons commencer. D'abord nous allons parler de piles, les données de pile et la file d'attente des structures que nous allons parler. Les piles et les files d'attente sont vraiment utiles quand on commence à parler de graphiques, que nous n'allons pas faire beaucoup en ce moment. Mais ils sont vraiment bons pour comprendre l'une des grandes structures de données fondamentales du CS. La description de la spécification du jeu de problème, si vous tirez dessus jusqu'à, parle de piles comme s'apparente à la pile de plateaux repas que vous avez dans la cafétéria de salles à manger où manger quand le personnel arrive et met les plateaux repas après qu'ils les ont nettoyés, ils empiler les uns sur les autres. Et puis, quand les enfants viennent pour obtenir de la nourriture, ils tirent les plateaux off, d'abord celui du haut, puis celui ci-dessous, alors que celui ci-dessous. Donc, en effet, le premier plateau que le personnel de salle à manger poser est la dernière qui obtient enlevé. Le dernier repas que le personnel mis en est le premier qui obtient enlevé pour le dîner. Dans l'ensemble spec problème, que vous pouvez télécharger si vous n'avez pas déjà, nous parlons de la modélisation d'une stucture de données pile en utilisant ce type de structure. 

Donc, ce que nous avons ici, ce qui est similaire à ce qui a été présenté en conférence, sauf dans la conférence, nous avons présenté cela avec ints plutôt que char * s. Cela va être une pile qui stocke quoi? Daniel? Qu'est-ce qu'on stocker dans cette pile? [Daniel] Strings? Nous sommes >> stocker des chaînes dans cette pile, exactement. Tout ce que vous devez avoir afin de créer une pile est un tableau d'une capacité particulière, qui, dans ce cas, la capacité va être en majuscules parce que c'est une constante. Et puis, en plus du tableau, tout ce que nous devons suivre est la taille actuelle de la matrice. Une chose à noter ici c'est plutôt cool c'est qu'on création de la structure de données empilées l'une sur l'autre structure de données, la matrice. Il ya différentes façons de mettre en œuvre des piles. Nous ne le ferons pas tout à fait encore, mais nous espérons que, après avoir fait les problèmes de listes liées, vous verrez comment vous pouvez facilement mettre en œuvre une pile au-dessus d'une liste chaînée ainsi. Mais pour l'instant, nous nous en tiendrons aux tableaux. Encore une fois, tout ce qu'il faut est un tableau et nous avons juste besoin de suivre la taille du tableau. [Sam] Désolé, pourquoi est-ce que vous avez dit la pile est au-dessus des cordes? Pour moi, il semble que les chaînes sont dans la pile. [Hardison] Ouais. Nous créons, nous prenons notre tableau structure de données - c'est une très bonne question. Donc la question est pourquoi, pour les gens qui regardent cette ligne, pourquoi disons-nous que la pile est au-dessus des cordes, car ici, il semble que les chaînes sont à l'intérieur de la pile? Ce qui est totalement le cas. Ce que je faisais allusion à ce que nous avons une structure de données de tableau. Nous avons un tableau de char * s, ce tableau de chaînes, et nous allons ajouter à cela afin de créer la structure de données empilées. 

Ainsi, une pile est un peu plus complexe qu'un tableau. On peut utiliser un tableau pour construire une pile. C'est donc là que nous disons que la pile est construite au-dessus d'un tableau. De même, comme je l'ai dit plus tôt, nous pouvons construire une pile au-dessus d'une liste chaînée. Au lieu d'utiliser un tableau pour stocker nos éléments, nous pourrions utiliser une liste chaînée de tenir nos éléments et de construire la pile autour de cela. Passons en revue quelques exemples, en regardant un peu de code, pour voir ce qui se passe réellement ici. Sur la gauche, j'ai jeté ce que struct pile pourrait ressembler dans la mémoire si la capacité a été défini # au nombre de quatre. Nous avons nos quatre-élément de tableau char *. Nous avons cordes [0], strings [1], les chaînes [2], strings [3], et puis ce dernier espace entier de notre taille. Est-ce logique? D'accord. C'est ce qui arrive si ce que je fais sur la droite, qui sera mon code, est de simplement déclarer une structure, une structure empilée appelé s. C'est ce que nous obtenons. Il établit cette empreinte dans la mémoire. La première question ici est quel est le contenu de cette struct pile? En ce moment ils ne sont rien, mais ils ne sont pas tout à fait rien. Ils sont ce genre de déchets. Nous n'avons aucune idée de ce qu'il ya dedans. Lorsque nous déclarons s de la pile, nous ne faisons que jeter que sur le dessus de la mémoire. C'est un peu comme déclarer int i et pas l'initialiser. Vous ne savez pas ce qu'il ya dedans. Vous pouvez lire ce qu'il ya dedans, mais il ne serait pas super utile. Une chose que vous voulez toujours vous rappeler de le faire est d'initialiser tout ce qui doit être initialisé. Dans ce cas, nous allons initialiser la taille à zéro, parce que cela va se révéler très important pour nous. Nous pourrions aller de l'avant et d'initialiser tous les pointeurs, tous les s char *, avoir une certaine valeur compréhensible, probablement nulle. Mais ce n'est pas absolument nécessaire que nous le fassions. 

Maintenant, les deux principales opérations sur les piles sont? Quelqu'un se souvient de ce que vous faites conférence avec des piles? Oui? [Stella] poussage et de sauter? >> Exactement. Pousser et popping sont les deux principales opérations sur les piles. Et qu'est-ce poussoir faire? Il met quelque chose >> sur le dessus de la pile, et ensuite il enlève éclatement. [Hardison] Exactement. Si poussée pousse quelque chose sur le dessus de la pile. C'est comme mettre du personnel à manger un plateau repas sur le comptoir. Et éclatée prend un plateau repas hors de la pile. Passons en revue quelques exemples de ce qui se passe lorsque l'on pousse les choses dans la pile. Si nous devions pousser la chaîne 'Bonjour' sur notre pile, c'est ce que notre diagramme sera semblable à aujourd'hui. Voir ce qui se passe? Nous avons poussé dans le premier élément de notre tableau de chaînes et nous avons augmenté notre nombre de la taille à 1. Donc, si on regarde la différence entre les deux lames, ici était de 0, voici avant la poussée. Voici après la poussée. Avant la poussée, après la poussée. Et maintenant nous avons un élément dans notre pile. C'est la chaîne "bonjour", et c'est tout. Tout le reste du tableau, dans notre tableau de chaînes, est encore ordures. Nous n'avons pas initialisé. Disons que l'on pousse une autre chaîne sur notre pile. Nous allons pousser "monde" sur cette période. Ainsi, vous pouvez voir "monde" va ici au-dessus de «bonjour», et le nombre de la taille va jusqu'à 2. Maintenant, nous pouvons pousser "CS50", et que vous allez sur le dessus à nouveau. Si nous revenons, vous pouvez voir comment nous poussons les choses sur le dessus de la pile. Et maintenant, nous arrivons à la pop. Lorsque nous sommes passés quelque chose hors de la pile, ce qui s'est passé? Quelqu'un a vu la différence? Il est assez subtile. [Étudiants] La taille. >> Oui, la taille a changé. 

Que voulez-vous pu s'attendre à changer? [] Les étudiants cordes, aussi. Droit >>. Les cordes aussi. Il s'avère que lorsque vous faites de cette façon, parce que nous ne sommes pas copier les éléments dans notre pile, nous avons en fait ne pas avoir à faire quoi que ce soit, nous pouvons simplement utiliser la taille de garder une trace du nombre de choses dans notre tableau de sorte que lorsque nous retirons encore, encore que nous venons de diminuer notre taille en-dessous de 1. Il n'est pas nécessaire d'aller effectivement dans et écrasera tout. Sorte de funky. Il s'avère que nous avons généralement juste laisser faire parce que c'est moins de travail à faire pour nous. Si nous n'avons pas à revenir en arrière et remplacer quelque chose, alors pourquoi le faire? Ainsi, lorsque nous apparaître deux fois hors de la pile, qui ne fait que diminuer la taille d'une couple de fois. Et encore, c'est seulement parce que nous ne sommes pas copier des choses dans notre pile. Oui? Allez-y. [Étudiant, inintelligible] >> Et alors qu'est-ce qui se passe lorsque vous appuyez de nouveau quelque chose? Lorsque vous appuyez de nouveau quelque chose, où faut-il aller? Où faut-il aller, Basil? Dans cordes >> [1]? Droit >>. Pourquoi ne pas aller dans les chaînes [3]? [Basil] Parce qu'il a oublié qu'il y avait quoi que ce soit dans les chaînes [1] et [2]? [Hardison] Exactement. Notre pile, pour l'essentiel, a "oublié" qu'elle tenait à rien dans les chaînes [1] ou chaînes [2], alors quand nous pousser "woot", il met juste que dans l'élément à cordes [1]. Y at-il des questions sur la façon dont cela fonctionne, à un niveau de base? [Sam] Ce n'est donc pas en aucune façon dynamique, en termes de quantité ou en fonction de la taille de la pile? [Hardison] Exactement. C'est - le fait est que ce n'était pas une pile dynamiquement growning. Il s'agit d'une pile qui peut contenir, au plus, quatre char * s, au plus quatre choses. Si nous devions essayer de pousser un cinquième chose, que pensez-vous devrait se passer? [Etudiants, inintelligibles] [Hardison] Exactement. Il ya un certain nombre de choses qui pourraient arriver. Il pourrait éventuellement seg défaut, en fonction de ce que nous avons - comment exactement nous mettions en œuvre le back-end. Il pourrait écraser. Il pourrait avoir ce type buffer overflow dont nous avons parlé en classe. Quelle serait la chose la plus évidente qui pourrait être écrasé si nous avons essayé de pousser une chose supplémentaire sur notre pile? Donc, vous avez mentionné un buffer overflow. Quelle pourrait être la chose qui serait-il écrasé ou piétiné si nous débordé accidentellement en essayant de pousser une chose en plus? [Daniel, inintelligible] possible >>. Mais d'abord, qu'est-ce qui pourrait arriver? Que faire si nous avons essayé de pousser un quatrième chose? Il peut écraser la taille, du moins en ce diagramme mémoire que nous avons. 

Dans la spécification du jeu de problème, c'est ce que nous allons mettre en œuvre aujourd'hui, ce que nous voulons faire est de simplement renvoyer false. Notre méthode push va retourner une valeur booléenne, et que la valeur booléenne sera vrai si la poussée réussit et faux si l'on ne peut pas pousser plus rien parce que la pile est pleine. Parcourons un peu de ce code en ce moment. Voici notre fonction Push. Notre fonction Push pour une pile va prendre dans la chaîne à mettre sur la pile. Il va retourner true si la chaîne a réussi à pousser sur l'autre pile et faux. Toutes les suggestions sur ce qui pourrait être une bonne chose premier à faire ici? [Sam] Si la taille est égale à la capacité alors retourner faux? [Hardison] Bingo. Nice job. Si la taille est la capacité, nous allons retourner false. Nous ne pouvons pas mettre quelque chose de plus dans notre pile. Dans le cas contraire, nous voulons mettre quelque chose sur le dessus de la pile. Qu'est-ce que «le sommet de la pile», d'abord? [Daniel] Taille 0? >> Taille 0. Quel est le sommet de la pile après il ya une chose dans la pile? Missy, savez-vous? [Missy] One. Des tailles >> en est un, exactement. Vous continuez à ajouter à la taille, et chaque fois que vous mettez dans le nouvel élément à la taille de l'index dans le tableau. Nous pouvons le faire avec ce genre de one-liner, si cela fait sens. Donc, nous avons notre tableau de chaînes, nous allons y accéder à l'index taille, et nous allons juste pour stocker notre char * là-dedans. Remarquez comment il ya pas de copie de chaîne qui se passe ici, pas d'allocation dynamique de la mémoire? Et puis Missy élevé ce que nous devons faire maintenant, parce que nous avons stocké la chaîne à l'endroit approprié dans le tableau, et elle a dit que nous devions augmenter la taille par une afin que nous sommes prêts pour la prochaine poussée. Ainsi, nous pouvons le faire avec s.size + +. À ce stade, nous avons poussé dans notre tableau. Quelle est la dernière chose que nous devons faire? [Étudiants] Retourne true. >> Retour vrai. Donc, c'est assez simple, un code assez simple. Pas trop. Une fois que vous avez enveloppé autour de votre tête la façon dont la pile fonctionne, c'est assez simple à mettre en œuvre. 

Maintenant, la prochaine partie de cet éclatement est une chaîne hors de la pile. Je vais vous donner les gars un peu de temps pour travailler sur ce morceau un peu. C'est presque essentiellement l'inverse de ce que nous avons fait ici en push. Qu'est-ce que j'ai fait est fait - oups. J'ai démarré un appareil ici, et dans l'appareil, J'ai remonté le problème set 5 spécification. Si l'on zoom avant ici, nous pouvons voir que je suis à cdn.cs50.net/2012/fall/psets/pset5.pdf. Avez-vous les gars téléchargé ce code qui est situé ici, section6.zip? Très bien. Si vous n'avez pas fait cela, le faire dès maintenant, très rapidement. Je le ferai dans ma fenêtre de terminal. En fait, je l'ai fait ici. Ouais. Oui, Sam? >> J'ai une question à propos de pourquoi tu as dit entre parenthèses s.string 's de taille = str? Qu'est-ce que str? Est celle qui est définie quelque part, ou - oh, dans le char * str? [Hardison] Oui, exactement. C'est l'argument. >> Oh, d'accord. Désolé. [Hardison] Nous sommes en spécifiant la chaîne de pousser po L'autre question qui pourrait arriver que nous n'avons pas vraiment parler ici était nous avons pris pour acquis que nous avons eu cette variable appelée s qui était dans la portée et accessible pour nous. Nous avons pris pour acquis que s était cette structure de pile. Donc, en regardant en arrière à ce code poussée, vous pouvez voir que nous faisons des choses avec cette chaîne qui s'est passé dans mais tout d'un coup, nous accédons à s.size, comme, où avez-s vient-il? Dans le code que nous allons examiner dans la section archives et puis le truc que vous allez faire dans votre problème fixe, nous avons fait notre pile struct une variable globale afin que nous puissions avoir accès à toutes nos fonctions différentes sans avoir à entrer manuellement le faire circuler et de le passer par référence, faire tout ce genre de trucs à elle. Nous sommes juste triche un peu, si vous voulez, pour rendre les choses plus agréables. Et c'est quelque chose que nous faisons ici, car c'est pour le plaisir, c'est plus facile. Souvent, vous verrez des gens le faire si ils ont une grande structure de données qui a été opéré au sein de leur programme. 

Revenons sur l'appareil. Tout le monde a réussi à obtenir le section6.zip? Tout le monde le décompresser à l'aide section6.zip décompresser? Si vous allez dans le répertoire de l'article 6 - aah, dans tous les sens - et vous énumérer ce qui est ici, vous voyez que vous avez trois fichiers différents. c. Vous avez une file d'attente, un sll, qui est simplement chaînée liste, et une pile. Si vous ouvrez pile.c, vous pouvez voir que nous avons cette structure définie pour nous, la structure exacte que nous en avons parlé dans les diapositives. Nous avons notre variable globale pour la pile, nous avons notre fonction Push, et puis nous avons eu notre fonction de pop. Je vais mettre le code pour repousser sur la diapositive ici, mais ce que je voudrais vous les gars à faire est, au mieux de vos capacités, aller et mettre en œuvre la fonction de pop. Une fois que vous avez mis en place, vous pouvez compiler avec make cette pile, puis exécutez le fichier exécutable pile résultante, et qui se déroulera tout ce code de test ici-bas qui est en principale. Et principal prend soin de faire réellement le push et pop appels et faire en sorte que tout se passe à travers tous les droits. Il initialise également la taille de la pile ici de sorte que vous n'avez pas à vous soucier de ce que l'initialisation. On peut supposer qu'il a été correctement initialisé par le temps que vous y accédez à la fonction de pop. Est-ce logique? Alors on y va. Il s'agit du code poussoir. Je vais vous donner les gars 5 ou 10 minutes. Et si vous avez des questions dans l'intervalle pendant que vous êtes de codage, s'il vous plaît demandez-leur à haute voix. Donc, si vous arrivez à un point d'achoppement, il suffit de demander. Faites-moi savoir, je sais tout le monde. Travaillez avec votre voisin aussi. [Daniel] Nous ne faisons que mettre en œuvre pop en ce moment? >> Just pop. Bien que vous pouvez copier la mise en œuvre de la poussée, si vous souhaitez de sorte que le test fonctionne. Parce qu'il est difficile de tester des choses en obtenant - ou, il est difficile de tester des choses sautant hors d'une pile si il n'y a rien dans la pile pour commencer. 

Quelle est pop censé être de retour? L'élément à partir du haut de la pile. Il est censé récupérer l'élément hors du dessus de la pile puis diminuer la taille de la pile, et maintenant vous avez perdu l'élément sur le dessus. Et puis vous retournez l'élément sur le dessus. [Étudiant, inintelligible] [Hardison] Donc ce qui arrive si vous faites cela? [Étudiant, inintelligible] Ce qui finit par se produire, c'est que vous êtes probablement l'accès soit un élément qui n'a pas encore été initialisé, de sorte que votre calcul où le dernier élément est éteint. Donc ici, si vous remarquez, en push, nous accédons à cordes à l'élément s.size parce que c'est un nouvel indice. C'est le nouveau haut de la pile. Alors que dans la pop, s.size va être le prochain espace, l'espace qui est au-dessus de tous les éléments de votre pile. Ainsi, l'élément supérieur plus n'est pas s.size, mais plutôt, c'est en dessous. 

L'autre chose à faire quand vous - dans la pop, est que vous ne devez diminuer la taille. Si vous vous souvenez de notre petit diagramme ici, vraiment, la seule chose que nous avons vu se passe quand nous avons appelé pop est que cette taille baissé, premier à 2, puis à 1. Puis, quand nous avons poussé un nouvel élément sur, il irait à l'endroit approprié. [Basil] Si le s.size est 2, alors il ne serait pas aller à l'élément 2, puis que vous voudriez faire apparaître cet élément off? Donc, si nous sommes allés à - >> Donc, regardons encore une fois. Si telle est notre pile à ce moment- et nous appelons pop, au cours de laquelle l'indice est l'élément le plus? [Basil] A 2, mais il va pop 3. Droit >>. C'est donc là que notre taille est de 3, mais nous voulons faire apparaître l'élément à l'index 2. C'est ce genre typique de large par celui que vous avez avec le zéro-indexation des tableaux. Donc, vous voulez faire apparaître le troisième élément, mais le troisième élément n'est pas à l'index 3. Et la raison pour laquelle nous n'avons pas à le faire 1 moins quand nous poussons est parce qu'en ce moment, vous remarquez que l'élément de plus haut niveau, si nous devions pousser quelque chose d'autre sur la pile à ce moment-là, nous voulons pousser à l'index 3. Et il se trouve que la taille et les indices de s'aligner quand vous poussez. 

Qui a une implémentation de la pile de travail? Vous avez une pile de travail un. Avez-vous pop fonctionne pas encore? [Daniel] Oui. Je crois. Programme en cours d'exécution >> et non seg failles, c'est l'impression de sortir? Est-ce que l'imprimer "succès" lorsque vous l'exécutez? Ouais. Assurez-pile, l'exécuter, si elle imprime sur le «succès» et ne fait boum, alors tout est bon. Très bien. Passons en revue à l'appareil très rapidement, et nous marcherons à travers cela. Si nous regardons ce qui se passe ici avec la pop, Daniel, ce qui était la première chose que vous avez fait? [Daniel] Si s.size est supérieur à 0. [Hardison] D'accord. Et pourquoi as-tu fait cela? [Daniel] Pour s'assurer qu'il y avait quelque chose à l'intérieur de la pile. [Hardison] Droit. Vous voulez tester pour s'assurer que s.size est supérieur à 0; autrement, que voulez-vous qu'il se passe? [Daniel] null retour? Null Retour >>, exactement. Donc, si s.size est supérieur à 0. Alors qu'allons-nous faire? Que faisons-nous si la pile n'est pas vide? [Stella] Vous décrémenter la taille? Vous >> diminuer la taille, d'accord. Alors, comment avez-vous fait? >> S.size--. [Hardison] Grande. Et puis qu'est-ce que tu fais? [Stella] Et puis je l'ai dit retour s.string [s.size]. [Hardison] Grande. Sinon, vous retourner null. Oui, Sam? [Sam] Pourquoi faut-il pas besoin d'être s.size + 1? [Hardison] Plus 1? Ouais >>. >> Compris. [Sam] Je pensais que parce que vous prenez 1 sortie, alors vous allez être de retour n'est pas celui qu'ils ont demandé. [Hardison] Et c'était exactement ce dont nous parlions avec toute cette question des indices de 0. Donc, si nous faire un zoom avant ici. Si l'on regarde ce gars ici, vous pouvez voir que lorsque nous pop, nous éclater l'élément à l'index 2. 

Donc, nous diminuons notre première taille, notre taille correspond à notre index. Si nous ne diminue pas la taille d'abord, puis nous avons à faire taille -1 puis décrémentation. Grande. Tout va bien? Vous avez des questions à ce sujet? Il ya un certain nombre de façons différentes d'écrire aussi. En fait, nous pouvons faire quelque chose d'encore - que nous pouvons faire un one-liner. Nous pouvons faire un retour sur une ligne. Nous pouvons donc diminuer avant de retourner en faisant cela. Donc, mettre le - avant le s.size. C'est pourquoi cette gamme très dense. Lorsque la différence entre la -. Taille et la s.size-- est que cette postfix - ils l'appellent postfix parce que le - vient après le s.size-- signifie que s.size est évaluée aux fins de la constatation de l'indice tel qu'il est actuellement lorsque cette ligne est exécutée, et puis ce - qui se produit après la ligne est exécuté. Après l'élément à s.size indice est accessible. Et ce n'est pas ce que nous voulons, parce que nous voulons le décrément arriver premier. Othewise, nous allons accéder au tableau, de manière efficace, en dehors des limites. Nous allons accéder à l'élément ci-dessus celui que nous voulons effectivement accès. Ouais, Sam? Est-il plus rapide >> ou utiliser moins de mémoire vive pour faire une ligne ou pas? [Hardison] Honnêtement, cela dépend vraiment. [Sam, inintelligible] >> Ouais, ça dépend. Vous pouvez faire des tours de compilation pour obtenir le compilateur de reconnaître que, généralement, j'imagine. 

Alors nous l'avons mentionné un peu plus sur ce genre de choses optimisation du compilateur que vous pouvez faire à la compilation, et c'est le genre de chose qu'un compilateur pourrait être en mesure de comprendre, comme oh, hé, peut-être que je peux faire tout cela en une seule opération, au lieu de chargement dans la variable de taille de la mémoire vive, le décrémenter, le stocker revenir en arrière, puis de le charger de retour à nouveau à traiter le reste de cette opération. Mais en général, non, ce n'est pas le genre de chose qui va rendre votre programme beaucoup plus rapide. D'autres questions sur les piles? 

Donc, en poussant et popping. Si vous voulez les gars d'essayer l'édition pirate, ce que nous avons fait dans l'édition pirate est en fait augmenté et fait de cette pile croissance dynamique. Le défi consiste surtout ici dans la fonction Push, de comprendre comment faire grandir ce tableau que vous continuer à pousser les éléments de plus en plus sur la pile. Il s'agit en fait pas trop de code supplémentaire. Juste un appel à - vous avez à retenir pour obtenir les appels à malloc là correctement, et puis savoir quand vous allez appeler realloc. C'est un défi amusant si vous êtes intéressés. 

Mais pour le moment, nous allons passer à autre chose, et nous allons parler de files d'attente. Faites défiler ici. La file d'attente est un frère près de la pile. Ainsi, dans la pile, les choses qui ont été mis en dernière sont les premières choses à être récupérées. Nous avons ce dernier entré, premier sorti, ou LIFO, de la commande. Alors que dans la file d'attente, comme vous le souhaitiez partir du moment où vous êtes debout en ligne, la première personne à faire la queue, la première chose à faire dans la file d'attente, est la première chose qui se extraites de la file d'attente. Les files d'attente sont également souvent utilisés lorsque nous traitons avec des graphiques, comme nous en avons parlé brièvement avec des piles, et les files d'attente sont également à portée de main pour un tas d'autres choses. Une chose qui revient souvent est d'essayer de maintenir, par exemple, une liste triée des éléments. Et vous pouvez le faire avec un tableau. Vous pouvez gérer une liste triée des choses dans un tableau, mais lorsque cela devient délicat est alors, vous avez toujours de trouver l'endroit approprié pour insérer la chose suivante. Donc si vous avez un tableau de nombres, de 1 à 10, et puis vous voulez étendre cela à tous les chiffres de 1 à 100, et vous obtenez ces numéros dans un ordre aléatoire et en essayant de garder tout triées comme vous le passer, vous finissez par avoir à faire beaucoup de changement. Avec certains types de files d'attente et certains types de structures de données sous-jacentes, vous pouvez effectivement garder assez simple. Vous n'avez pas besoin d'ajouter quelque chose, puis remélanger le tout à chaque fois. Pas plus que vous avez à faire beaucoup de déplacement des éléments internes autour. Lorsque nous regardons une file d'attente, vous voyez que - même dans queue.c dans le code de section - la structure que nous vous avons donnée est vraiment similaire à la structure que nous vous avons toute une pile. 

Il ya une exception à cette règle, et que seule exception est que nous avons cet entier supplémentaire appelé la tête, et la tête ici, c'est pour garder la trace de la tête de la file d'attente, ou le premier élément dans la file d'attente. Avec une pile, nous avons réussi à garder la trace de l'élément que nous étions sur le point de récupérer, ou le haut de la pile, en utilisant simplement la taille, tandis que dans une file d'attente, nous allons avoir à faire face à des extrémités opposées. Nous essayons de virer de bord sur les choses à la fin, mais de remettre les choses à partir de l'avant. Donc, en réalité, avec la tête, nous avons l'indice du début de la file d'attente, et la taille nous donne l'indice de la fin de la file d'attente afin que nous puissions récupérer les choses de la tête et ajouter des choses à la queue. Alors qu'avec la pile, nous n'avons jamais traiter avec le haut de la pile. Nous n'avons jamais eu d'accéder au bas de la pile. Nous avons seulement ajouté des choses vers le haut et a pris les choses hors de la partie supérieure nous n'avons donc pas besoin de ce champ supplémentaire à l'intérieur de notre structure. Est-ce que généralement un sens? Très bien. Oui, Charlotte? [Charlotte, inintelligible] [Hardison] C'est une très bonne question, et c'est celui qui est venu en conférence. Peut-être la marche à travers quelques exemples vont illustrer pourquoi nous ne voulons pas d'utiliser des chaînes [0] à la tête de la file d'attente. 

Alors, imaginez ce que nous avons notre file d'attente, nous allons l'appeler file d'attente. Au début, quand nous avons tout juste instancié, quand nous venons-il déclaré, nous n'avons pas initialisé quoi que ce soit. C'est tous les déchets. Alors bien sûr, nous voulons faire en sorte que nous initialisons la taille et les domaines tête à 0, quelque chose de raisonnable. Nous pourrions aussi aller de l'avant et nulle sur les éléments dans notre file d'attente. Et pour rendre ce bon schéma, vous remarquerez que maintenant notre file d'attente ne peut contenir trois éléments; alors que notre pile peut tenir quatre, notre file d'attente ne peut contenir que trois. Et c'est juste pour faire le bon schéma. La première chose qui se passe ici, c'est que nous en file d'attente la chaîne "salut". Et tout comme nous l'avons fait avec la pile, rien de très différent ici, nous jetons sur la chaîne à cordes [0] et augmenter notre taille de 1. Nous en file d'attente "au revoir", il se fait mettre. Donc, cela ressemble à une pile pour la plupart. Nous avons commencé ici, nouvel élément, élément nouveau, la taille ne cesse d'augmenter. Qu'est-ce qui se passe à ce point quand nous voulons dequeue quelque chose? Quand nous voulons dequeue, qui est l'élément que nous voulons dequeue? [Basil] Strings [0]. >> Zéro. Exactement, Basil. Nous voulons nous débarrasser de la première chaîne, celui-ci, «salut». Alors quelle est l'autre chose qui a changé? Remarquez quand nous sommes passés quelque chose hors de la pile, nous avons juste changé les dimensions, mais ici, nous avons un certain nombre de choses qui changent. Non seulement le changement de taille, mais les changements à la tête. Cela va revenir au point de Charlotte tôt: pourquoi avons-nous cette tête aussi? Est-il judicieux aujourd'hui, Charlotte? Type d'>>. [Hardison] Type de? Donc ce qui s'est passé lorsque nous dequeued? Qu'est-ce que la tête faire maintenant est intéressant? [Charlotte] Oh, parce qu'il a changé - d'accord. Je vois. Parce que la tête - où la tête est orientée à l'évolution des termes de l'emplacement. Ce n'est plus toujours le seul indice zéro. >> Oui, exactement. Qu'est-ce qui s'est passé, si dequeueing l'élément haut a été fait et nous n'avons pas eu ce champ tête parce que nous avons toujours été d'appeler cette chaîne à 0 indexer la tête de notre file d'attente, alors nous aurions à passer le reste de la file d'attente vers le bas. Nous serions obligés de passer «au revoir» à partir de chaînes de caractères [1] pour les cordes [0]. Et strings [2] vers le bas pour cordes [1]. Et nous aurions dû le faire pour la liste complète des éléments, l'ensemble du réseau d'éléments. Et quand nous faisons cela avec un tableau, qui devient vraiment cher. Donc, ici, ce n'est pas une grosse affaire. Nous venons d'avoir trois éléments dans notre tableau. Mais si nous avions une file d'attente d'un millier d'éléments ou un million éléments, et puis tout d'un coup, nous commençons à faire un tas de dequeue appelle tous dans une boucle, les choses vont vraiment à ralentir car il se déplace tout vers le bas en permanence. Vous savez, passer par 1, passage de 1, passage de 1, passage de 1. Au lieu de cela, nous utilisons cette tête, on appelle cela un «pointeur», même si ce n'est pas vraiment un pointeur au sens strict, ce n'est pas un type pointeur. Ce n'est pas un int * ou char * ou quelque chose comme ça. Mais elle pointe ou indiquant la tête de notre file d'attente. Ouais? 

[Étudiants] Comment dequeue sais juste pop off tout ce qui est à la tête? [Hardison] Comment dequeue sais pas comment pour faire sauter tout ce qui est à la tête? Droit >>, ouais. >> Qu'est-ce qu'il regarde est juste quelque soit le domaine social est fixé à. Ainsi, dans ce premier cas, si l'on regarde ici, notre tête est 0, 0 index. Droit >>. [Hardison] Donc, il dit juste correct, eh bien, l'élément à l'index 0, la chaîne "salut", est l'élément à la tête de notre file d'attente. Donc, nous allons dequeue ce type. Et ce sera l'élément qui est retourné à l'appelant. Oui, Saad? Alors >> la tête définit essentiellement la - où vous allez l'index? C'est le début de celui-ci? Ouais >>. Ok >>. [Hardison] C'est de devenir le nouveau départ pour notre tableau. Ainsi, lorsque vous dequeue quelque chose, tout ce que vous avez à faire est accéder à l'élément à l'index q.head, et ce sera l'élément que vous voulez dequeue. Vous avez également à diminuer la taille. Nous verrons dans un instant où les choses deviennent un peu délicat avec cela. Nous dequeue, et maintenant, si nous en file d'attente à nouveau, où allons-nous en file d'attente? D'où vient l'élément suivant aller dans notre file d'attente? Disons que nous voulons en file d'attente la chaîne "CS". Dans laquelle index-il aller? [Les élèves] Strings [2]. Deux >>. Pourquoi 2 et pas 0? [Basil] Parce que maintenant, la tête est de 1, de sorte que c'est comme le début de la liste? [Hardison] Droit. Et ce qui indique la fin de la liste? Qu'est-ce qu'on utilise pour désigner la fin de notre file d'attente? La tête est la tête de notre file d'attente, le début de notre file d'attente. Quelle est la fin de notre file d'attente? [Etudiants] Taille. Taille >>, exactement. Ainsi, nos nouveaux éléments vont à sa taille, et les éléments que nous décoller sortir à la tête. Quand nous en file d'attente l'élément suivant, nous allons le mettre à sa taille. [Étudiants] Avant de mettre les choses en bien, la taille était de 1, non? [Hardison] Droit. Donc, pas tout à fait au format. + Taille, pas une, mais la tête +. Parce que nous sommes passés tout par la quantité tête. Donc, ici, maintenant nous avons une file d'attente de taille 1 qui commence à l'index 1. La queue est l'indice 2. Oui? 

[Étudiants] Qu'est-ce qui se passe quand vous dequeue cordes [0], ainsi que les chaînes «fentes de mémoire juste me vider, au fond, ou tout simplement oublié? [Hardison] Ouais. En ce sens, nous ne faisons que de les oublier. Si nous étions stocker des copies de - plusieurs structures de données enregistrerez souvent de leurs propres copies des éléments de sorte que la personne qui gère la structure de données n'a pas à se soucier d'où tous ces pointeurs sont en cours. La structure de données s'accroche à tout, s'accroche à toutes les copies, afin de s'assurer que tout subsiste en conséquence. Toutefois, dans ce cas, ces structures de données juste, pour plus de simplicité, ne sont pas de faire des copies de tout ce que nous vous stockez en eux. [Étudiants] Donc est-ce un réseau continu de -? Oui >>. Si nous regardons en arrière à ce que la définition était de cette structure, il est. C'est juste un tableau standard, comme vous avez vu, un tableau de char * s. Est-ce que -? >> Ouais, je me demandais si vous finirez par manquer de mémoire, dans une certaine mesure, si vous avez tous ces espaces vides dans votre tableau? [Hardison] Oui, c'est un bon point. 

Si l'on regarde ce qui s'est passé aujourd'hui à ce point, nous avons rempli notre file d'attente, elle ressemble. Mais nous n'avons pas vraiment rempli notre file d'attente parce que nous avons une file d'attente qui est de taille 2, mais il commence à l'index 1, parce que c'est là notre pointeur de tête est. Comme vous le disiez, cet élément à cordes [0], à l'indice 0, n'est pas vraiment là. Il n'est pas dans notre file d'attente plus. Nous n'avions tout simplement pas la peine d'y aller et l'écraser lorsque nous sortir de la file. Ainsi, même si on dirait que nous sommes à court de mémoire, nous n'avons pas vraiment. Cette tache est disponible pour nous à utiliser. Le comportement approprié, si nous devions essayer quelque chose et le premier dequeue comme "au revoir", qui apparaîtra au revoir au large. Maintenant, notre file d'attente commence à l'index 2 et est de taille 1. Et maintenant, si nous essayons quelque chose de nouveau en file d'attente et, disons 50, 50 doit aller dans cet endroit à l'index 0 parce qu'il est toujours disponible pour nous. Oui, Saad? [Saad] Est-ce que se faire automatiquement? [Hardison] Il ne se passe pas tout à fait automatiquement. Vous devez faire le calcul pour le faire fonctionner, mais essentiellement ce que nous avons fait, c'est que nous venons de enroulé autour. [Saad] Et est-ce correct si cela a un trou au milieu de celui-ci? [Hardison] Il est si on peut faire le calcul fonctionne de façon appropriée. 

Et il s'avère que ce n'est en fait pas si difficile à faire avec l'opérateur mod. Ainsi, tout comme nous l'avons fait avec César et les choses crypto, en utilisant mod, nous pouvons faire avancer les choses pour envelopper et continuer autour et autour et autour de notre file d'attente, garder ce pointeur de tête à se déplacer. Notez que la taille est toujours en respectant le nombre d'éléments réellement dans la file d'attente. Et c'est juste le pointeur de tête qui maintient le vélo à travers. Si l'on regarde ce qui s'est passé ici, si nous revenons au début, et vous venez de regarder ce qui se passe à la tête quand nous en file d'attente quelque chose, rien ne s'est passé dans la tête. Quand nous en file d'attente d'autre chose, rien ne s'est passé dans la tête. Dès que nous dequeued quelque chose, la tête monte par un. Nous en file d'attente quelque chose, rien ne se passe dans la tête. Quand nous dequeue quelque chose, tout d'un coup la tête est incrémenté. Quand nous avons quelque chose en file d'attente, rien ne se passe dans la tête. 

Que se passerait-il à ce point si nous devions dequeue quelque chose de nouveau? Toute pensée? Qu'arriverait-il à la tête? Que faut-il à la tête si nous devions dequeue quelque chose d'autre? La tête en ce moment est à l'indice 2, ce qui signifie que la tête de la file d'attente est strings [2]. [Étudiants] Qui retourne 0? >> Elle doit retourner à 0. Il faut envelopper retourna, exactement. Jusqu'à présent, chaque fois que nous avons appelé dequeue, nous avons ajouté un à la tête, ajouter une à la tête, ajouter une à la tête, ajouter une à la tête. Dès que le pointeur de tête arrive au dernier indice dans notre tableau, alors nous devons conclure retour vers le début, revenir à 0. [Charlotte] Qu'est ce qui détermine la capacité de la file d'attente dans une pile? [Hardison] Dans ce cas, nous venons avec une constante # défini. Ok >>. [Hardison] Dans le fichier réel. C, vous pouvez aller dans et dans la boue avec elle un peu et de le rendre aussi grand ou aussi peu que vous voulez. [Charlotte] Ainsi, lorsque vous faites une file d'attente, comment voulez-vous que l'ordinateur sait la taille que vous voulez que la pile de l'être? [Hardison] C'est une très bonne question. Il existe deux façons. La première est de simplement définir à l'avance et dire que cela va être une file d'attente qui possède 4 éléments ou 50 éléments ou 10.000. L'autre façon est de faire ce que les gens édition pirates font et créer des fonctions pour que votre file d'attente croissance dynamique en plus de choses sont ajoutés po 

[Charlotte] Donc, pour aller avec la première option, quelle syntaxe que vous utilisez pour indiquer au programme quelle est la taille de la file d'attente? [Hardison] Ah. Donc, nous allons sortir de cette. Je suis toujours dans pile.c ici, donc je vais juste pour faire défiler vers le haut ici. Pouvez-vous voir juste là? Il s'agit de la capacité de 10 # define. Et c'est presque la même syntaxe exacte que nous avons pour la file d'attente. Sauf dans la file d'attente, nous avons ce champ struct supplémentaire ici. [Charlotte] Oh, je pensais que la capacité signifie la capacité de la chaîne. [Hardison] Ah. >> Ca y est la longueur maximale d'un mot. >> Compris. Ouais. La capacité ici - c'est un excellent point. Et c'est quelque chose qui est difficile parce que ce que nous avons déclaré ici est un tableau de char * s. Un tableau de pointeurs. Il s'agit d'un tableau de caractères. C'est probablement ce que vous avez vu quand vous avez été la déclaration de vos tampons pour le fichier I / O, quand vous avez été la création de chaînes manuellement sur la pile. Cependant, ce que nous avons ici, c'est un tableau de char * s. Donc, c'est un tableau de pointeurs. En fait, si l'on zoom arrière et on regarde ce qui se passe ici dans la présentation, vous voyez que les éléments réels, les données de caractères ne sont pas stockées dans le tableau lui-même. Ce qui est stocké au sein de notre réseau ici sont des pointeurs vers les données de caractères. D'accord. Donc, nous avons vu comment la taille de la file d'attente est juste comme avec la pile, la taille respecte toujours le nombre d'éléments actuellement dans la file d'attente. Après avoir fait deux enqueues, la taille est 2. Après avoir fait une dequeue la taille est maintenant 1. Après avoir fait une autre enqueue la taille est remonté à 2. Ainsi, la taille respecte certainement le nombre d'éléments dans la file d'attente, puis la tête ne cesse de cyclisme. Il va de 0-1-2, 0-1-2, 0-1-2. Et chaque fois que nous appelons dequeue, le pointeur de tête est incrémenté à l'index suivant. Et si la tête est sur le point de passer en revue, il reboucle autour de 0. Donc, avec cela, nous pouvons écrire la fonction dequeue. Et nous allons quitter la fonction enqueue pour vous les gars pour mettre en œuvre la place. 

Quand nous dequeue un élément de notre file d'attente, ce qui était la première chose que Daniel fait lorsque nous avons commencé à écrire la fonction pop pour les piles? Permettez-moi entendre parler de quelqu'un qui n'a pas encore parlé. Voyons, Saad, vous rappelez-vous ce que Daniel a fait que la première chose quand il a écrit la pop? [Saad] Il y avait, c'était - >> Il a testé pour quelque chose. [Saad] Si la taille est supérieure à 0. >> Exactement. Et quel était ce test pour? [Saad] Cela a été tester pour voir s'il ya quelque chose à l'intérieur du tableau. [Hardison] Ouais. Exactement. Donc, vous ne pouvez pas récupérer quelque chose hors de la pile si elle est vide. De même, vous ne pouvez pas dequeue quoi que ce soit à partir d'une file d'attente si elle est vide. Quelle est la première chose que nous devons faire dans notre fonction dequeue ici, pensez-vous? [Saad] Si la taille est supérieure à 0? Ouais >>. Dans ce cas, je l'ai fait juste testé pour voir si elle est de 0. Si c'est 0, on peut retourner null. Mais la logique exactement la même. Et nous allons continuer avec cela. Si la taille n'est pas 0, où est l'élément que nous voulons dequeue? [Saad] A la tête? >> Exactement. Nous ne pouvons tout simplement retirer le premier élément dans notre file d'attente en accédant à l'élément de la tête. Rien de fou. Après cela, que devons-nous faire? Ce qui doit arriver? Quelle est la chose d'autre dont nous avons parlé dans dequeue? Deux choses doivent se produire, parce que notre file d'attente a changé. [Daniel] Réduire la taille. >> Nous devons réduire la taille et d'accroître la tête? Exactement. Pour accroître la tête, nous ne pouvons pas aveuglément augmenter la hauteur, souvenez-vous. Nous ne pouvons pas faire queue.head + +. Nous devons également comprendre ce mod par la capacité. Et pourquoi avons-nous la capacité de mod, Stella? [Stella] Parce qu'il a à enrouler autour. >> Exactement. Nous mod par la capacité, car il doit envelopper arrière autour de 0. Alors maintenant, à ce stade, nous pouvons faire ce que Daniel dit. Nous pouvons diminuer la taille. Et puis on peut simplement retourner l'élément qui était à la tête de la file d'attente. Il a l'air assez gnarly au premier abord. Vous pouvez poser une question. Désolé? 

[Sam] Pourquoi le premier en haut de la file d'attente? Où ça va? [Hardison] Il s'agit de la quatrième ligne du bas. Après nous tester pour s'assurer que notre file d'attente n'est pas vide, nous nous retirons char * d'abord, nous nous retirons l'élément qui est assis à la tête de l'indice de notre gamme, notre gamme de chaînes, >> et que le premier appel? [Hardison] Et nous appelons en premier. Ouais. Pour faire suite à ce sujet, pourquoi pensez-vous que nous devions faire cela? [Sam] Chaque premier revient tout juste q.strings [q.head]? Ouais >>. Parce que >> nous faisons cette évolution de la q.head avec la fonction mod, et il n'y a aucun moyen de le faire dans la conduite de retour également. [Hardison] Exactement. Vous êtes sur place. Sam est totalement justes. La raison pour laquelle nous avons dû retirer le premier élément dans notre file d'attente et le stocker dans une variable C'est parce que cette ligne où nous venions q.head, il ya l'opérateur mod là n'est pas quelque chose que nous pouvons faire et le faire entrer en vigueur sur la tête sans - sur une seule ligne. Donc, nous avons à tirer le premier élément, puis réglez la tête, ajuster la taille, puis retourner l'élément qui nous nous sommes retirés. Et c'est quelque chose que nous allons voir arriver plus tard avec listes chaînées, comme on joue avec eux. Souvent, quand vous libérer ou de l'élimination des listes chaînées vous devez vous rappeler l'élément suivant, le pointeur suivant d'une liste chaînée avant de disposer de l'actuel. Parce que sinon, vous jetez les informations de ce qui reste dans la liste. Maintenant, si vous allez à votre appareil, vous ouvrez queue.c-x-dehors de ça. Donc, si j'ouvre queue.c, laissez-moi un zoom avant ici, vous verrez que vous avez un fichier d'aspect semblable. D'aspect semblable fichier à ce que nous avions auparavant avec pile.c. Nous avons notre structure de file d'attente définie comme nous l'avons vu dans les diapositives. 

Nous avons notre fonction enqueue qui est à faire pour vous. Et nous avons la fonction dequeue ici. La fonction dequeue dans le fichier n'est pas implémenté, mais je vais le remettre en place sur le PowerPoint de sorte que vous puissiez le saisir, si vous le souhaitez. Donc, pour les 5 prochaines minutes, vous les gars travailler sur enqueue qui est presque à l'opposé de dequeue. Vous n'avez pas besoin d'ajuster la tête lorsque vous enqueueing, mais qu'est-ce que vous avez à régler? Taille. Ainsi, lorsque vous enqueue, la tête reste intacte, la taille est changée. Mais cela prend un peu de - vous aurez à jouer avec ce mod de comprendre exactement ce que l'indice le nouvel élément doit être inséré à. Alors je vais vous donner les gars un peu, mettez dequeue remonter sur la diapositive, et que vous les gars avez des questions, leur crier afin que nous puissions tout le monde parle d'eux comme un groupe. En outre, avec la taille que vous ne - lorsque vous réglez la taille, vous pouvez toujours juste - avez-vous de mod la taille sans cesse? [Daniel] No. >> Vous n'avez pas de mod de la taille, à droite. Parce que la taille sera toujours, si Tu es - en supposant que vous gérez les choses correctement, la taille sera toujours compris entre 0 et 3. Où avez-vous de mod quand vous faites enqueue? [Étudiants] Uniquement pour la tête. Seuls >> pour la tête, exactement. Et pourquoi avez-vous de mod du tout dans enqueue? Quand une situation dans laquelle vous auriez à mod? [Étudiants] Si vous avez des trucs à des espaces, comme à des espaces 1 et 2, et puis vous avez besoin d'ajouter quelque chose à 0. [Hardison] Oui, exactement. Donc, si le pointeur de votre tête est tout à la fin, ou si votre taille ainsi que votre tête est plus grand, ou plutôt, va s'enrouler autour de la file d'attente. 

Donc, dans cette situation que nous avons ici sur la diapositive en ce moment, si je veux quelque chose en file d'attente en ce moment, nous voulons quelque chose en file d'attente à l'index 0. Donc, si vous regardez où va le 50, et je l'appelle enqueue 50, il y descend en bas. Il va en index 0. Il remplace le «salut» qui a déjà été dequeued. [Daniel] Ne vous prenez soin de cela dans dequeue déjà? Pourquoi faut-il faire quelque chose avec la tête dans enqueue? [Hardison] Oh, si vous n'êtes pas modifier la tête, désolé. Mais vous devez utiliser l'opérateur mod lorsque vous accédez l'élément que vous voulez en file d'attente lorsque vous accédez l'élément suivant dans la file d'attente. [Basil] Je n'ai pas fait cela, et j'ai eu le «succès» de l'existence. [Daniel] Oh, je comprends ce que vous dites. [Hardison] Donc, vous didn't - vous venez de faire à q.size? [Basil] Ouais. Je viens de changer d'autre, je n'ai rien fait avec la tête. [Hardison] Vous n'avez pas réellement besoin de réinitialiser la tête d'être quoi que ce soit, mais quand vous indice dans le tableau de chaînes, vous avez réellement à aller de l'avant et de calculer l'endroit où l'élément suivant est, parce withe la pile, l'élément suivant dans votre pile était toujours à l'indice correspondant à la taille. Si nous regardons en arrière jusqu'à notre fonction push pile, on peut toujours débarquez dans notre élément nouveau à droite à la taille des index. Alors qu'avec la file d'attente, nous ne pouvons pas le faire parce que si nous sommes à cette situation, si nous en file d'attente 50 Notre nouvelle chaîne irait droit à cordes [1] que nous ne voulons pas faire. Nous voulons avoir la nouvelle chaîne aller à l'index 0. 

Est-ce que tout le monde - oui? [Étudiants] J'ai une question, mais ce n'est pas vraiment lié. Qu'est-ce que cela signifie quand quelqu'un appelle simplement quelque chose comme pointeur pred? Qu'est-ce que le nom court pour? Je sais que c'est juste un nom. [Hardison] pointeur Pred? Voyons voir. Dans quel contexte? [Étudiants] C'était pour l'insert. Je peux vous demander plus tard si vous voulez car ce n'est pas vraiment lié, mais je viens de - [Hardison] Du code d'insertion de David de conférence? Nous ne pouvons tirer que vous et parler. Nous en parlerons la prochaine, une fois que nous arrivons à des listes chaînées. 

Donc, nous allons très vite voir ce que la fonction enqueue ressemble. Quelle est la première chose que les gens ont essayé de le faire dans votre ligne de enqueue? Dans cette file d'attente? Semblable à ce que vous avez fait pour pousser la pile. Qu'avez-vous fait, Stella? [Stella, inintelligible] [Hardison] Exactement. Si (q.size CAPACITÉ ==) - J'ai besoin de mettre mon appareil au bon endroit - return false. Zoom dans un peu. D'accord. Maintenant, quelle est la prochaine chose que nous devions faire? Tout comme avec la pile, et inséré au bon endroit. Et quel était le bon endroit pour insérer ce? Avec la pile c'était taille de l'index, avec cela, il n'est pas tout à fait cela. [Daniel] J'ai q.head--ou - q.strings >>? >> Ouais. q.strings [+ q.head q.size mod CAPACITÉ]? [Hardison] Nous voudrez probablement mettre des parenthèses autour de cette de sorte que nous obtenons la priorité appropriée et si c'est cleart à tout le monde. Et définir ce que l'égalité? >> Pour str? >> Pour str. Grande. Et maintenant, quelle est la dernière chose que nous devons faire? Tout comme nous l'avons fait dans la pile. >> Incrémentation de la taille? >> Incrémentation de la taille. Boom. Et puis, depuis le code de démarrage juste retourné false par défaut, nous voulons changer cette option à true si tout se passe à travers et tout va bien. Très bien. C'est beaucoup d'informations pour la section. Nous ne sommes pas tout à fait terminée. Nous voulons parler très rapidement sur des liaisons simples listes liées. Je vais mettre cette place afin que nous puissions y revenir plus tard. Mais revenons à notre présentation pour juste un peu plus transparents. Donc enqueue est TODO, maintenant que nous avons fait. 

Maintenant, nous allons jeter un oeil à des liaisons simples listes liées. Nous avons parlé de ces un peu plus dans la conférence. Combien d'entre vous les gars vu la démo où nous avions des gens maladroitement pointant vers chacun des nombres et d'autres organisation? >> J'étais dans cette. >> Qu'est-ce que vous en pensez? Ai fait, je l'espère démystifier ces bits un peu? Avec une liste, il s'avère que nous avons affaire avec ce type que nous allons appeler un nœud. Alors que la file d'attente et la pile nous avions structures qui nous avions appellent file d'attente dans la pile, nous avions ces nouvelle file d'attente dans les types de pile, voici une liste est vraiment juste constituée d'un groupe de nœuds. De la même manière que les chaînes sont juste un tas de caractères tous alignés les uns à côté des autres. Une liste chaînée est juste un noeud et un autre noeud et un autre noeud et un autre noeud. Et plutôt que de casser tous les noeuds entre eux et de les stocker de manière contiguë tout juste à côté de l'autre dans la mémoire, avoir ce pointeur suivant nous permet de stocker les nœuds partout où, au hasard. Et puis, sorte de fil tous ensemble au point de l'un à l'autre. 

Et quel était le gros avantage que cela a eu sur un tableau? Sur tout stockage contiguë juste coincé à côté de l'autre? Vous vous souvenez? Ouais? L'allocation dynamique de la mémoire >>? >> Allocation de mémoire dynamique dans quel sens? [Étudiants] Dans ce que vous pouvez continuer à faire plus grand et vous n'avez pas à déplacer votre tableau entier? [Hardison] Exactement. Donc, avec un tableau, lorsque vous voulez mettre un élément nouveau dans le milieu, vous devez changer tout pour faire de la place. Et comme nous en avons parlé avec la file d'attente, c'est pourquoi nous gardons cela pointeur de tête, de sorte que nous ne sommes pas les choses changent constamment. Parce que devient cher si vous avez un grand tableau et vous êtes constamment à faire ces insertions aléatoires. Alors qu'avec une liste, tout ce que vous avez à faire est de le jeter sur un nouveau nœud, ajuster les pointeurs, et vous avez terminé. Ce qui craint à ce sujet? Mis à part le fait que ce n'est pas aussi facile de travailler avec comme un tableau? Ouais? [Daniel] Eh bien, je suppose que c'est beaucoup plus difficile d'accéder à un élément spécifique dans la liste chaînée? [Hardison] Vous ne pouvez pas accéder à un élément d'arbitraire dans le milieu de votre liste chaînée. Comment avez-vous de le faire à la place? >> Vous devez passer en revue l'ensemble de chose. [Hardison] Ouais. Vous devez passer par un à la fois, un à la fois. C'est un énorme - c'est une douleur. Quel est l'autre - il ya une autre chute à cela. [Basil] Vous ne pouvez pas aller de l'avant et vers l'arrière? Il faut y aller une seule direction? [Hardison] Ouais. Alors, comment pouvons-nous résoudre que, parfois? [Basil] doublement listes chaînées? >> Exactement. Il existe des listes doublement liés. Il ya aussi - excusez-moi? 

[Sam] Est-ce la même fonction que la chose que pred - Je viens de me rappeler, n'est-ce pas ce que la chose est pour pred? N'est-ce pas dans l'intervalle doublement et individuellement? [Hardison] Regardons exactement ce qu'il faisait. Alors on y va. Voici le code liste. Ici, nous avons predptr, ici. Est-ce que vous parlez? Donc, ce fut - il libère une liste et qu'il essaie de stocker un pointeur vers elle. Ce n'est pas le doublement, individuellement liés listes. Nous pouvons parler plus à ce sujet plus tard, car il est question ici de libérer la liste et je veux vous montrer quelques autres trucs d'abord. mais c'est juste - c'est se rappeler la valeur de ptr [Étudiants] Oh, c'est pointeur précédent? Ouais >>. Afin que nous puissions ensuite incrémenter ptr lui-même avant nous alors libre ce qui est predptr. Parce que nous ne pouvons pas libre ptr puis appelez ptr = ptr prochaine, non? Ce serait mauvais. Voyons donc, revenons à ce gars-là. 

L'autre point négatif est que sur les listes alors qu'avec un tableau il suffit de tous les éléments eux-mêmes empilés à côté de l'autre, ici nous avons également introduit ce pointeur. Il ya donc un morceau de mémoire supplémentaire que nous allons avoir à utiliser pour chaque élément que nous stockons dans notre liste. Nous obtenons la flexibilité, mais elle a un coût. Il est livré avec ce coût en temps, et il est livré avec ce coût trop de mémoire. Temps dans le sens que nous avons maintenant à passer en revue chaque élément dans le tableau pour trouver celui à l'indice 10, ou qui aurait été indice 10 dans un tableau. 

Juste très rapidement, quand on diagramme sur ces listes, généralement nous nous accrochons à la tête de la liste ou le premier pointeur de la liste et notez qu'il s'agit d'un pointeur vrai. C'est juste 4 octets. Ce n'est pas un nœud lui-même. Donc, vous voyez qu'il n'a pas de valeur int en elle, aucun pointeur à côté de lui. Il est littéralement juste un pointeur. Il va pointer vers quelque chose qui est une struct noeud réelle. [Sam] Un pointeur appelé nœud? Il s'agit d'>> - no. Il s'agit d'un pointeur vers quelque chose de noeud de type. Il s'agit d'un pointeur sur une struct noeud. >> Oh, d'accord. Schéma sur la gauche, le code sur la droite. On peut le mettre à null, ce qui est une bonne façon de commencer. Quand vous le diagramme, vous pouvez soit écrire comme nulle ou que vous mettez une ligne en travers comme ça. 

Une des façons les plus faciles de travailler avec des listes, et nous vous demandons de faire les deux prepend et ajouter de voir les différences entre les deux, mais préfixant est certainement plus facile. Lorsque vous faites précéder, c'est là que vous - lorsque vous prepend (7), vous allez créer la structure noeud et que vous définissez premier à pointer vers elle, parce que maintenant, depuis que nous avons préfixé, ça va être au début de la liste. Si nous prepend (3), qui crée un autre nœud, mais maintenant 3 sort avant le 7. Nous sommes donc essentiellement pousser les choses sur notre liste. Maintenant, vous pouvez voir que prepend, parfois, les gens l'appellent pousser, parce que vous poussez un nouvel élément sur votre liste. Il est également facile de supprimer à l'avant d'une liste. Alors, les gens appellent souvent que pop. Et de cette façon, vous pouvez émuler une pile en utilisant une liste chaînée. Oups. Désolé, maintenant nous entrons dans append. Nous voilà donc préfixé (7), maintenant nous prepend (3). Si nous préfixé quelque chose d'autre sur cette liste, si nous préfixé (4), alors nous aurions 4, puis 3 puis 7. Alors, on pourrait éclater et enlever 4, supprimer 3, supprimer 7. Souvent le moyen le plus intuitif de penser à ce sujet est en append. J'ai donc schématisé sur ce qu'il pourrait ressembler à ajouter ici. Ici, annexé (7) n'a pas l'air différent parce qu'il n'y a qu'un seul élément dans la liste. Et en ajoutant (3) qu'elle met à la fin. Peut-être que vous pouvez voir en ce moment le tour avec append est que, puisque nous ne savons où le début de la liste est, à ajouter à une liste que vous avez à marcher tout le chemin à travers la liste pour arriver à la fin, arrêtez, puis construire votre noeud et tout plunk vers le bas. Câblez toutes les choses en place. Donc, avec préfixe, comme nous venons déchiré par ce très rapidement, lorsque vous faites précéder d'une liste, il est assez simple. 

Vous faites votre noeud nouvelle, qu'elle implique une allocation dynamique de mémoire. Donc, ici, nous faisons une struct noeud en utilisant malloc. Donc malloc nous utilisons parce que vous mis de côté la mémoire pour nous pour plus tard parce que nous ne voulons pas cela - nous voulons que cette mémoire se perpétue pendant un long moment. Et nous obtenons un pointeur vers l'espace dans la mémoire que nous venons alloué. Nous utilisons la taille du noeud, nous n'avons pas la somme des champs. Nous n'avons pas générer manuellement le nombre d'octets, au lieu que nous utilisons sizeof afin que nous sachions que nous obtenons le nombre approprié d'octets. Nous nous assurons de tester que notre appel malloc réussi. C'est quelque chose que vous voulez faire en général. Sur les machines modernes, à court de mémoire n'est pas quelque chose qui est facile à moins que vous allouons une tonne de trucs et de faire une liste énorme, mais si vous construire des choses pour, disons, comme un iPhone ou un Android, vous ne disposer de ressources mémoire limitées, surtout si vous faites quelque chose d'intense. Donc, il est bon d'obtenir en pratique. 

Remarquez que j'ai utilisé un couple de différentes fonctions ici que vous avez vu ce sont des sortes de nouvelles. Donc fprintf est juste comme printf l'exception de son premier argument est le flux auquel vous souhaitez imprimer. Dans ce cas, nous voulons imprimer à la chaîne d'erreur standard qui est différente de la norme outstream. Par défaut, il se présente au même endroit. Il imprime aussi au terminal, mais vous pouvez - en utilisant les commandes que vous avez appris sur les techniques de redirection, vous avez appris à propos de la vidéo de Tommy pour 4 ensemble de problèmes, vous pouvez le diriger à différents domaines, puis quitter, ici, les sorties de votre programme. Il s'agit essentiellement comme un retour de principal, sauf que nous utilisons ici la sortie, car le retour ne fera rien. Nous ne sommes pas en principal, de sorte scrutin ne quitter le programme comme nous le voulons. Donc, nous utilisons la fonction de sortie et de lui donner un code d'erreur. Alors voilà nous avons mis en valeur le terrain du nouveau nœud, son champ i soit égale à i, puis on le câbler. Nous avons mis en pointeur à côté du nouveau nœud de souligner tout d'abord, et puis la première va maintenant pointer vers le nouveau nœud. Ces premières lignes de code, nous sommes en train de construire le nouveau nœud. Pas les deux dernières lignes de cette fonction, mais les premiers. Vous pouvez effectivement sortir dans une fonction, dans une fonction d'assistance. C'est souvent ce que je fais, c'est que je le sortir dans une fonction, Je l'appelle quelque chose comme noeud de construction, et qui maintient la fonction prepend assez petit, il est à seulement 3 lignes-là. Je fais un appel à ma fonction de noeud de construction, et puis tout fils je vers le haut. 

La dernière chose que je veux vous montrer, et je vous laisse faire append et tout ce que vous-même, est de savoir comment itérer sur une liste. Il ya un tas de façons différentes pour itérer sur une liste. Dans ce cas, nous allons trouver la longueur d'une liste. Nous commençons donc avec une longueur = 0. Ceci est très similaire à l'écriture strlen pour une chaîne. C'est ce que je veux vous montrer, cette boucle for ici. Il ressemble un peu branché, ce n'est pas l'habitude int i = 0, i <que ce soit, i + +. Au lieu de cela il est l'initialisation de notre variable n comme le début de la liste. Et puis, alors que notre variable d'itération n'est pas nul, nous continuons. C'est parce que, par convention, la fin de notre liste sera considérée comme nulle. Et puis, pour incrémenter, plutôt que de faire + +, l'équivalent de liste chaînée + + est N = N-> suivante. 

Je vous laisse combler les lacunes ici parce que nous manquons de temps. Mais gardez cela à l'esprit lorsque vous travaillez sur vos psets spellr. Listes chaînées, si vous implémentez une table de hachage, va certainement se révéler très utiles. Et ayant cet idiome pour boucler sur les choses vont rendre la vie beaucoup plus facile, je l'espère. Pour toute question, rapidement? [Sam] Est-ce que vous envoyez le rempli sll et sc? [Hardison] Ouais. Je vais envoyer des diapositives réalisées et pile sll rempli et queue.cs. [CS50.TV]