[Powered by Google Translate] [Avis] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Université de Harvard]
>> [C'est CS50.] [CS50.TV]
>> Hey, tout le monde.
Bienvenue à la session d'examen pour Quiz 0, qui se déroule ce mercredi.
Ce que nous allons faire ce soir, je suis avec 3 autres fonds fiduciaires,
et ensemble, nous allons passer par un examen de ce que nous avons fait au cours jusqu'ici.
Il ne va pas à 100% complet, mais elle devrait vous donner une meilleure idée
de ce que vous avez déjà vers le bas et ce que vous avez encore besoin d'étudier avant mercredi.
Et n'hésitez pas à lever la main avec des questions comme nous allons le long,
mais gardez à l'esprit que nous aurons aussi un peu de temps à la fin-
si nous obtenons par le biais de quelques minutes pour faire de rechange à des questions générales,
donc gardez cela à l'esprit, et nous allons commencer au début de la semaine 0.
>> [Quiz 0 Commentaire!] [Partie 0] [Lexi Ross] Mais avant cela nous allons parler de
la logistique du quiz.
>> [Logistique] [Quiz aura lieu le mercredi 10/10 au lieu de la conférence]
>> [(Voir http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf pour plus de détails)] C'est le mercredi 10 Octobre.
>> C'est ce mercredi, et si vous allez à cette adresse ici,
qui est également accessible à partir CS50.net-il ya un lien vers elle-
vous pouvez voir les informations pour savoir où aller fondée sur
votre nom de famille ou de leur appartenance école ainsi que
il raconte exactement ce que le questionnaire couvrira et les types de questions que vous allez obtenir.
Gardez à l'esprit que vous aurez également l'occasion d'examiner pour le quiz en coupe,
afin que vos FO devrait aller sur certains problèmes pratiques,
et c'est une autre bonne occasion de voir où vous avez encore besoin d'étudier pour le quiz.
Commençons par le début avec Octets Bits 'n'.
Rappelez-vous un peu, c'est juste un 0 ou un 1,
et un octet est un ensemble de 8 de ces bits.
Penchons-nous sur cette collection de morceaux ici.
Nous devrions être en mesure de déterminer combien de bits il ya.
Où l'on compte il ya seulement 8 d'entre eux, huit unités 0 ou 1.
Et comme il ya 8 bits, cela fait 1 octet,
et nous allons la convertir en hexadécimal.
Hexadécimal est en base 16, et il est assez facile de convertir
un nombre en binaire, ce qui est ce que c'est, pour un certain nombre en hexadécimal.
Nous ne faisons que nous regardons groupes de 4,
et nous les convertir au chiffre hexadécimal approprié.
Nous commençons avec le groupe le plus à droite de 4, donc 0011.
Cela va être un 1 et un 2, donc ensemble qui fait 3.
Et puis, regardons l'autre bloc de 4.
1101. Cela va être un 1, un 4 et un 8.
Ensemble, ça va être de 13, ce qui rend D.
Et nous nous souviendrons que nous en hexadécimal ne pas simplement aller de 0 à 9.
Nous allons 0 à F, si bien qu'après 9, 10 correspond à A,
11 à B, et ainsi de suite où F est de 15.
Ici, 13 est un D,
afin de le convertir en décimal nous ne faisons que nous avons fait
traiter chaque situation comme une puissance de 2.
C'est un 1, un 2, zéro 4s, 8s zéro, un 16, et cetera,
et c'est un peu difficile à calculer dans votre tête, mais si nous allons à la diapositive suivante
nous pouvons voir la réponse à cette question.
>> Essentiellement, nous allons en face de la droite vers la gauche,
et nous multiplier chaque chiffre par la puissance correspondante de 2.
Et rappelez-vous, pour hexadécimal on note ces chiffres avec 0x au début
nous n'avons donc pas le confondre avec un nombre décimal.
Poursuivant, il s'agit d'un tableau ASCII,
et ce que nous utilisons pour ASCII est de cartographier de caractères en valeurs numériques.
Rappelez-vous dans le pset cryptographie, nous avons fait un usage intensif de la table ASCII
afin d'utiliser diverses méthodes de cryptographie,
le César et le chiffrement de Vigenère, pour convertir les différentes lettres
dans une chaîne selon la clé fournie par l'utilisateur.
Regardons d'un peu de maths ASCII.
Consultant d''P' + 1, en forme de caractères qui serait Q,
et n'oubliez pas que '5 '≠ 5.
Et de quelle façon pourrions-nous convertir entre ces 2 formes?
Ce n'est pas vraiment trop dur.
Afin d'obtenir 5 on soustrait '0 '
parce qu'il ya 5 places entre '0 'et '5'.
Pour aller dans l'autre sens nous suffit d'ajouter le 0,
donc c'est un peu comme l'arithmétique ordinaire.
N'oubliez pas que lorsque quelque chose doit guillemets autour de lui c'est un personnage
et correspond donc à une valeur dans la table ASCII.
S'engager dans des sujets plus généraux de l'informatique.
Nous avons appris ce qu'est un algorithme est et comment nous utilisons la programmation
d'implémenter des algorithmes.
Quelques exemples d'algorithmes sont quelque chose de vraiment simple, comme
vérifier si un nombre est pair ou impair.
Pour cela nous rappelle mod le nombre par 2 et vérifier si le résultat est 0.
Si c'est le cas, c'est encore plus. Sinon, c'est bizarre.
Et c'est un exemple d'un algorithme très basique.
>> Un peu d'un plus impliqué est binaire de recherche,
que nous allons passer en revue plus tard dans la session d'examen.
Et la programmation est le terme que nous utilisons pour prendre un algorithme
et les convertit en coder l'ordinateur peut lire.
2 exemples de programmation est Scratch,
qui est ce que nous avons fait dans la semaine 0.
Même si nous ne tapez pas sur le code, c'est une façon de mettre en œuvre
cet algorithme, qui imprime les nombres 1-10,
et ici nous faire la même chose dans le langage de programmation C.
Ceux-ci sont fonctionnellement équivalents, vient d'écrire dans des langues différentes ou de syntaxe.
Nous avons alors appris sur les expressions booléennes,
et un booléen est une valeur qui est soit vraie ou fausse,
et les expressions booléennes souvent ici
aller à l'intérieur de conditions, si (x ≤ 5),
eh bien, nous avons déjà mis en x = 5, alors que l'état va évaluer la valeur true.
Et si c'est vrai, quel que soit le code est sous la condition
va être évaluées par l'ordinateur, de sorte que chaîne va être imprimé
sur la sortie standard, et la condition de durée
se réfère à tout ce qui est à l'intérieur des parenthèses de l'instruction if.
Rappelez-vous tous les opérateurs.
N'oubliez pas que c'est && et | | quand nous essayons de combiner 2 ou plusieurs conditions,
== Pas de vérifier si = 2 choses sont égales.
Rappelez-vous que pour l'affectation = est alors == est un opérateur booléen.
≤, ≥, puis la finale 2 sont auto-explicatifs.
Une revue générale de la logique booléenne ici.
Et les expressions booléennes sont également importants dans les boucles,
que nous allons passer en revue maintenant.
Nous avons appris environ 3 types de boucles jusqu'à présent en CS50, for, while, et à faire pendant.
Et il est important de savoir que, bien que dans la plupart des
nous pouvons utiliser n'importe quel type de boucle généralement
il ya certains types de buts communs ou des motifs
dans la programmation qui appellent spécifiquement pour l'une de ces boucles
qui en font le. plus efficace ou élégant de le coder de cette façon
Passons en revue ce que chacune de ces boucles ont tendance à être utilisés le plus souvent.
>> Dans une boucle for nous avons généralement le savez déjà combien de fois nous voulons parcourir.
C'est ce que nous avons mis dans la condition.
Car, i = 0, i <10, par exemple.
Nous savons déjà que nous voulons faire quelque chose de 10 fois.
Maintenant, pour une boucle while, en général, nous n'avons pas nécessairement
combien de fois nous voulons que la boucle de s'exécuter.
Mais nous savons une sorte de condition que nous voulons qu'il
toujours vrai ou toujours faux.
Par exemple, si est réglé.
Disons que c'est une variable booléenne.
Alors c'est vrai que nous voulons le code d'évaluer,
donc un peu plus extensible, un peu plus générale que celle d'une boucle for,
mais toute boucle for peut également être converti en une boucle while.
Enfin, faire des boucles while, qui peuvent être plus délicate à comprendre tout de suite,
sont souvent utilisés lorsque l'on veut évaluer le premier code
avant la première fois que nous vérifier l'état.
Un cas d'utilisation commune pour une boucle Do While
c'est quand vous voulez pour obtenir l'entrée d'utilisateur, et vous savez que vous voulez demander à l'utilisateur
pour l'entrée au moins une fois, mais s'ils ne vous donnent pas une bonne entrée tout de suite
vous voulez garder leur demandant jusqu'à ce qu'ils vous donnent la bonne entrée.
C'est l'utilisation la plus courante d'une boucle Do While,
et regardons la structure réelle de ces boucles.
En général, ils ont toujours tendance à suivre ces tendances.
>> Sur la boucle de l'intérieur vous avez 3 composantes:
l'initialisation, généralement quelque chose comme int i = 0 où i est le compteur,
condition, là où nous voulons dire exécuter ce pour boucle tant que cette condition est toujours valable,
comme i <10, et enfin, mise à jour, qui est de savoir comment on incrémente
la variable de compteur à chaque point dans la boucle.
Une chose commune de voir qu'il ya seulement i + +,
ce qui signifie incrémenter i de 1 à chaque fois.
Vous pouvez aussi faire quelque chose comme i + = 2,
ce qui signifie ajouter 2 à i chaque fois que vous allez à travers la boucle.
Et puis la faire se réfère seulement à un code qui fonctionne effectivement dans le cadre de la boucle.
Et pour une boucle while, cette fois, nous avons fait l'initialisation en dehors de la boucle,
Ainsi, par exemple, disons que nous essayons de faire le même type de boucle que je viens de décrire.
Nous dirions int i = 0 avant que la boucle commence.
Alors nous pourrions dire tout i <10 ce faire,
de sorte que le même bloc de code comme précédemment,
et cette fois, la partie mise à jour du code, par exemple, i + +,
va en fait à l'intérieur de la boucle.
Et enfin, pour faire un tout, il est semblable à la boucle while,
mais nous devons nous rappeler que le code d'évaluer fois
avant que la condition est vérifiée, il est donc beaucoup plus de sens
si vous regardez dans l'ordre de haut en bas.
Dans un, faire boucle while évalue le code avant même de regarder l'état tout en
alors une boucle while, il vérifie d'abord.
Instructions et variables.
Lorsque nous voulons créer une nouvelle variable nous voulons d'abord l'initialiser.
>> Par exemple, un bar int initialise la variable bar,
mais il ne lui donne pas une valeur, alors quelle est la valeur bar maintenant?
Nous ne savons pas.
Il pourrait s'agir d'une valeur ordures qui a été précédemment stocké dans la mémoire là-bas,
et nous ne voulons pas d'utiliser cette variable
jusqu'à ce que nous lui donner une valeur,
si on le déclare ici.
Ensuite, nous avons l'initialiser à 42 ci-dessous.
Maintenant, bien sûr, nous savons que cela peut être fait sur une seule ligne, un bar int = 42.
Mais juste pour être clair les multiples étapes qui sont en cours,
la déclaration et l'initialisation se produisent séparément ici.
Il arrive sur une étape et la suivante, int baz = bar + 1,
cette déclaration ci-dessous, que baz incréments, de sorte qu'à la fin de ce bloc de code
si nous devions imprimer la valeur de baz il serait de 44
parce que nous déclarons et l'initialiser à 1 bar>
et puis nous l'incrémenter une fois de plus avec le + +.
Nous sommes allés au cours de cette brève joli, mais il est bon d'avoir un général
la compréhension de ce que les discussions et les événements sont.
Nous avons principalement fait dans Scratch,
de sorte que vous pouvez penser de threads que plusieurs séquences de code
exécute en même temps.
En réalité, il n'est probablement pas en cours d'exécution dans le même temps,
mais en quelque sorte abstraite, nous pouvons penser que c'est de cette façon.
>> Dans Scratch, par exemple, nous avons eu les sprites multiples.
On pourrait exécuter du code différente en même temps.
On peut se promener pendant que l'autre veut dire quelque chose
dans une autre partie de l'écran.
Les événements sont une autre façon de séparer la logique
entre les différents éléments de votre code,
et dans Scratch, nous avons pu simuler des événements en utilisant la diffusion,
et c'est en fait quand je reçois, pas quand j'entends,
mais essentiellement, c'est une façon de transmettre l'information
d'un sprite à l'autre.
Par exemple, vous voudrez peut-être de transmettre game over,
et quand un autre sprite qui reçoit game over,
il répond d'une certaine manière.
C'est un modèle important de comprendre la programmation.
Juste pour revenir sur la Semaine de base 0, ce que nous avons dépassé à ce jour,
Voyons ce programme C simple.
Le texte peut être un peu petite d'ici, mais je vais aller sur ce très rapide.
Nous avons inclus 2 fichiers d'en-tête en haut, cs50.h et stdio.h.
Nous sommes ensuite définir une limite constante appelée à être 100.
Nous sommes ensuite la mise en œuvre de notre fonction principale.
Comme nous n'avons pas utiliser des arguments de ligne de commande ici, nous devons mettre nulle
que les arguments en faveur principal.
Nous voyons ci-dessus int principale. C'est le type de retour, donc retourner 0 en bas.
Et nous utilisons CS50 fonction de bibliothèque obtenir int
de demander à l'utilisateur d'entrer, et nous le stocker dans cette variable x,
si nous déclarons x ci-dessus, et nous l'initialisons avec x = getInt.
>> Nous avons ensuite vérifier si l'utilisateur nous a donné de bonnes suggestions.
Si c'est LIMITE ≥ nous voulons retourner un code d'erreur 1 et affiche un message d'erreur.
Et enfin, si l'utilisateur nous a donné de bonnes suggestions
nous allons résoudre la quadrature du nombre et imprimer ce résultat.
Juste pour s'assurer que les personnes à la maison tous les succès
vous pouvez voir les étiquettes des différentes parties du code ici.
Je l'ai mentionné constants, les fichiers d'en-tête.
Oh, int x. Assurez-vous de se rappeler que c'est une variable locale.
Qu'il contraste d'une variable globale, dont nous parlerons à propos de
un peu plus tard dans la session d'examen,
et nous appelons la fonction de bibliothèque printf,
si nous n'avions pas inclus le fichier d'en-tête stdio.h
nous ne serions pas en mesure d'appeler printf.
Et je crois que la flèche qui a été coupé ici est orientée vers l'% d,
qui est une chaîne de formatage dans printf.
Il affirme imprimer cette variable comme un nombre,% d.
Et c'est tout pour la semaine 0.
Maintenant, Lucas va se poursuivre.
Hé, les gars. Mon nom est Lucas.
Je suis un étudiant en deuxième année dans la meilleure maison sur le campus, Mather,
et je vais vous parler un peu de la semaine 1 et 2,1.
[Semaine 1 et 2.1!] [Lucas Freitas]
Comme Lexi disais, quand nous avons commencé à traduire votre code à partir de zéro à C
l'une des choses que nous avons remarqué, c'est que vous ne pouvez pas simplement
écrire votre code et l'exécuter en utilisant un drapeau vert plus.
En fait, vous devez utiliser certaines mesures pour rendre votre programme C
devenir un fichier exécutable.
Fondamentalement, ce que vous faites quand vous écrivez un programme, c'est que
vous traduire votre idée dans un langage un compilateur peut comprendre,
Ainsi, lorsque vous écrivez un programme en C
ce que vous faites est en train d'écrire quelque chose que votre compilateur va comprendre,
puis le compilateur va traduire ce code
en quelque chose que votre ordinateur va comprendre.
>> Et le truc, c'est que votre ordinateur est vraiment très stupide.
Votre ordinateur ne peut comprendre 0 et de 1,
donc en fait dans les premiers ordinateurs des gens habituellement programmés
en utilisant 0 et de 1, mais pas plus, Dieu merci.
Nous n'avons pas besoin de mémoriser les séquences de 0 et de 1
pour une boucle ou une boucle de temps et ainsi de suite.
C'est pourquoi nous avons un compilateur.
Qu'est-ce qu'un compilateur fait est qu'il se traduit essentiellement le code C,
dans notre cas, à une langue que votre ordinateur va comprendre,
qui est le code de l'objet, et le compilateur que nous utilisons
est appelé bruit, donc c'est en fait le symbole de bruit.
Lorsque vous avez votre programme, vous devez faire 2 choses.
Tout d'abord, vous devez compiler votre programme, puis vous allez exécuter votre programme.
Pour compiler votre programme, vous avez beaucoup d'options pour le faire.
La première est de faire program.c clang
dans lequel le programme est le nom de votre programme.
Dans ce cas, vous pouvez voir qu'ils sont juste en disant "Hé, compiler mon programme."
Vous n'êtes pas en disant "Je veux que ce nom pour mon programme» ou quoi que ce soit.
>> La deuxième option est de donner un nom à votre programme.
Vous pouvez dire clang-o, puis le nom que vous souhaitez
le fichier exécutable d'être nommé, puis program.c.
Et vous pouvez aussi faire faire du programme, et de voir comment, dans les 2 premiers cas
J'ai mis. C, et dans le troisième je n'ai que des programmes?
Ouais, vous avez réellement ne faut pas mettre. C lorsque vous utilisez make.
Sinon, le compilateur qui se passe réellement à hurler à vous.
Et aussi, je ne sais pas si vous vous souvenez,
mais beaucoup de fois nous avons également utilisé lcs50-ou-lm.
C'est ce qu'on appelle la liaison.
Il indique simplement au compilateur que vous allez utiliser ces bibliothèques là,
donc si vous voulez utiliser cs50.h vous avez réellement besoin de taper
clang program.c-lcs50.
Si vous ne le faites pas, le compilateur ne va pas de savoir
que vous utilisez ces fonctions dans cs50.h.
Et lorsque vous voulez exécuter votre programme, vous avez 2 options.
Si vous avez program.c clang vous n'avez pas donner un nom à votre programme.
Vous devez l'exécuter en utilisant. / A.out.
A.out est un nom standard qui clang donne à votre programme si vous ne lui donnez pas un nom.
Sinon, vous allez faire. / Programme si vous avez donné un nom à votre programme,
et aussi si vous avez fait le programme le nom d'un programme va se faire
est déjà en cours à programmer le même nom que le fichier c.
Puis nous avons parlé des types de données et des données.
>> Fondamentalement, les types de données sont la même chose que de petites boîtes qu'ils utilisent
pour stocker des valeurs, si les types de données sont en fait juste comme Pokémons.
Ils viennent dans toutes les tailles et types.
Je ne sais pas si cela a un sens analogue.
La taille des données dépend en fait de l'architecture de la machine.
Toutes les tailles de données que je vais montrer ici
sont en fait pour une machine 32-bit, ce qui est le cas de notre appareil,
mais si vous êtes réellement coder votre Mac ou Windows aussi
vous allez probablement avoir une machine 64-bit,
donc n'oubliez pas que la taille des données que je vais montrer ici
sont fournies à la machine 32-bit.
Le premier que nous avons vu était un int,
ce qui est assez simple.
Vous utilisez int pour stocker un entier.
Nous avons également vu le caractère, le char.
Si vous souhaitez utiliser une lettre ou un petit symbole que vous allez probablement utiliser un char.
Un char a 1 octet, ce qui signifie 8 bits, comme Lexi dit.
Fondamentalement, nous avons une table ASCII qui a 256
les combinaisons possibles de 0 et de 1,
et puis quand vous tapez un char ça va traduire
le personnage que vous entrées un numéro que vous avez dans la table ASCII, comme Lexi dit.
Nous avons également le flotteur, que nous utilisons pour stocker des nombres décimaux.
Si vous voulez choisir 3.14, par exemple, vous allez utiliser un flotteur
ou un double qui est plus précis.
Un flotteur dispose de 4 octets.
Un double dispose de 8 octets, de sorte que la seule différence est la précision.
Nous avons aussi une longue qui est utilisé pour les nombres entiers,
et vous pouvez voir pour une machine 32-bit d'un int et un long ont la même taille,
de sorte qu'il n'a pas vraiment de sens d'utiliser une longue dans une machine 32-bit.
>> Mais si vous utilisez un ordinateur Mac et 64-bit, en fait un long a une taille 8,
donc cela dépend vraiment de l'architecture.
Pour la machine 32-bit il n'a pas de sens d'utiliser une longue vraiment.
Et puis un long terme, d'autre part, dispose de 8 octets,
il est donc très utile si vous voulez avoir un nombre entier plus.
Et enfin, nous avons chaîne, qui est en fait un char *,
qui est un pointeur sur un char.
Il est très facile de penser que la taille de la chaîne va être comme
le nombre de caractères que vous avez là,
mais en fait le même char *
a la taille d'un pointeur sur un caractère, qui est de 4 octets.
La taille d'un char * est de 4 octets.
Ce n'est pas grave si vous avez un petit mot ou une lettre ou quoi que ce soit.
Il va y avoir 4 octets.
Nous avons aussi appris un peu plus sur la coulée,
de sorte que vous pouvez le voir, si vous avez, par exemple, un programme qui dit
int x = 3, puis printf ("% d", x / 2)
Avez-vous les gars savent ce que ça va imprimer sur l'écran?
>> Quelqu'un? >> [Etudiants] 2.
1. >> 1, ouais.
Quand vous faites 3/2 ça va obtenir 1,5,
mais puisque nous utilisons un entier, il va ignorer la partie décimale,
et vous allez avoir 1.
Si vous ne voulez pas que cela se produise ce que vous pouvez faire, par exemple,
est de déclarer un flotteur y = x.
Alors x qui étaient de 3 va maintenant être 3.000 en y.
Et puis, vous pouvez imprimer le rapport y / 2.
En fait, je devrais avoir un 2. là-bas.
Il va faire 3.00/2.00,
et vous allez obtenir 1,5.
Et nous avons cette f .2 juste pour demander 2 unités décimales dans la partie décimale.
Si vous avez .3 f il va falloir effectivement 1,500.
Si c'est 2 que ça va être de 1,50.
Nous avons aussi le cas ici.
Si vous le faites float x = 3,14 et x vous printf
vous allez obtenir 3,14.
Et si vous faites l'int x = de x,
ce qui signifie traiter x comme un int et que vous imprimez x maintenant
vous allez avoir 3,00.
Est-ce logique?
Parce que vous êtes le premier traitement de x comme un nombre entier, de sorte que vous ne tenez pas compte de la partie décimale,
et puis vous imprimez x.
Et enfin, vous pouvez aussi le faire,
int x = 65, puis vous déclarez un char c = x,
et puis si vous imprimez le c vous allez effectivement d'obtenir
A, donc en gros ce que vous faites ici
se traduit par le nombre entier dans le caractère,
tout comme la table ASCII fait.
Nous avons aussi parlé des opérateurs mathématiques.
La plupart d'entre eux sont assez simples, donc +, -, *, /,
et aussi nous avons parlé de mod, qui est le reste d'une division de 2 nombres.
Si vous avez 10% 3, par exemple,
cela signifie diviser 10 par 3, et quel est le reste?
Il va y avoir 1, donc c'est vraiment très utile pour un grand nombre de programmes.
Pour Vigenère et César, je suis sûr que tous les gars utilisé mod.
À propos des opérateurs mathématiques, soyez très prudent lors de l'association * et /.
>> Par exemple, si vous faites (3/2) * 2 qu'allez-vous obtenir?
[Etudiants] 2.
Ouais, 2, parce 2.3 va être de 1,5,
mais puisque vous faites des opérations entre 2 entiers
vous êtes réellement aller juste de considérer 1,
puis 1 * 2 va être de 2, donc être très, très prudent
quand faire des calculs avec des nombres entiers, car
vous pourriez obtenir ce 2 = 3, dans ce cas.
Et aussi faire très attention à la priorité.
Vous devriez normalement utiliser des parenthèses pour être sûr que vous savez ce que vous faites.
Quelques raccourcis utiles, bien sûr, on est i + + ou i + = 1
ou en utilisant + =.
C'est la même chose que faire i = i + 1.
Vous pouvez également faire i - i ou - = 1,
qui est la même chose que i = i-1,
quelque chose de vous les gars utilisent beaucoup dans les boucles for, au moins.
En outre, pour *, si vous utilisez * = et si vous le faites, par exemple,
i * = 2 est la même chose que de dire i = i * 2,
et la même chose pour la division.
Si vous le faites i / = 2, c'est la même chose que i = i / 2.
>> Maintenant, sur les fonctions.
Vous les gars ont appris que les fonctions sont une très bonne stratégie pour sauver le code
tandis que vous programmez, donc si vous voulez effectuer la même tâche
dans le code encore et encore, sans doute vous souhaitez utiliser une fonction
juste pour que vous ne devez pas copier et coller le code maintes et maintes fois.
En fait, la principale est une fonction, et quand je vous montre le format d'une fonction
vous allez voir que c'est assez évident.
Nous utilisons également les fonctions de certaines bibliothèques,
par exemple, printf, GETIN, qui provient de la bibliothèque CS50,
et d'autres fonctions telles que toupper.
Toutes ces fonctions sont effectivement mises en œuvre dans d'autres bibliothèques,
et quand vous mettez les fichiers d'attache au début de votre programme
vous dites peut vous s'il vous plaît me donner le code pour les fonctions
donc je n'ai pas à les mettre en œuvre par moi-même?
Et vous pouvez également écrire vos propres fonctions, alors quand vous lancez la programmation
vous vous rendez compte que les bibliothèques ne disposent pas de toutes les fonctions dont vous avez besoin.
Pour le pset dernier, par exemple, nous avons écrit dessiner, bousculade, et rechercher,
et c'est très, très important d'être capable d'écrire des fonctions
parce qu'ils sont utiles, et nous les utilisons tout le temps dans la programmation,
et cela fait gagner beaucoup de code.
Le format d'une fonction est celle-ci.
Nous avons type de retour au début. Quel est le type de retour?
C'est juste au moment où votre fonction va revenir.
Si vous avez une fonction, par exemple, factorielle,
qui va calculer une factorielle d'un nombre entier,
sans doute il va retourner un entier aussi.
Ensuite, le type de retour va être int.
Printf est en fait un type de retour void
parce que vous n'êtes pas retourner quoi que ce soit.
Vous êtes juste l'impression des choses à l'écran
et quitter la fonction de suite.
Ensuite, vous avez le nom de la fonction que vous pouvez choisir.
Vous devriez être un peu raisonnable, comme ne choisissez pas un nom comme xyz
ou comme x2F.
Essayez de faire un nom qui a du sens.
>> Par exemple, si elle est factoriel, factorielle dire.
Si c'est une fonction qui va dessiner quelque chose, appelez-le dessiner.
Et puis nous avons les paramètres, qui sont également appelés arguments,
qui sont comme les ressources que votre fonction a besoin
à partir de votre code d'accomplir sa tâche.
Si vous voulez calculer la factorielle d'un nombre
sans doute vous avez besoin d'avoir un certain nombre de calculer une factorielle.
L'un des arguments que vous allez avoir est le nombre lui-même.
Et puis il va faire quelque chose et retourner la valeur à la fin
sauf s'il s'agit d'une fonction nulle.
Voyons un exemple.
Si je veux écrire une fonction qui additionne tous les chiffres dans un tableau d'entiers,
tout d'abord, le type de retour va être int
parce que j'ai un tableau d'entiers.
Et puis je vais avoir le nom de la fonction comme sumArray,
et puis il va prendre le tableau lui-même, à nums int,
puis la longueur du tableau et je sais combien de numéros que j'ai à résumé.
Ensuite, je dois initialiser une somme variable appelée, par exemple, à 0,
et chaque fois que je vois un élément dans le tableau je devrais l'ajouter à la somme, alors j'ai fait une boucle for.
Tout comme Lexi dit, vous faites int i = 0, i <longueur et i + +.
Et pour chaque élément dans le tableau que j'ai fait la somme + = nums [i],
et puis je suis retourné la somme, il est donc très simple, et il permet d'économiser beaucoup de code
si vous utilisez cette fonction, un grand nombre de fois.
Puis nous avons pris un coup d'oeil à conditions.
Nous avons if, else, et d'autre si.
Voyons quelle est la différence entre les deux.
Jetez un oeil à ces 2 codes. Quelle est la différence entre eux?
La première a-essentiellement les codes veux que vous disiez
si un nombre est +, -, ou 0.
Le premier dit que si il est> 0 alors c'est positif.
Si c'est = à 0 alors il est 0, et si elle est <0 alors il est négatif.
>> Et l'autre fait si, d'autre si, d'autre.
La différence entre les deux est que celui-ci va effectivement
vérifier si> 0, <0 ou = 0 trois fois,
donc si vous avez le numéro 2, par exemple, il va venir ici et dire
if (x> 0), et il va dire oui, alors je imprimer positive.
Mais même si je sais que c'est> 0 et il ne va pas être égal à 0 ou <0
Je vais toujours à faire est de 0, est-il <0,
donc je vais en fait à l'intérieur des ifs que je n'ai pas eu à
parce que je sais déjà que ça ne va pas pour satisfaire une de ces conditions.
Je peux utiliser le if, else if, else.
Il dit en substance si x = 0 je imprimer le positif.
Si ce n'est pas le cas, je vais aussi tester cela.
Si c'est 2 pas, je vais le faire.
En gros, si je devais x = 2 vous dirais
if (x> 0), oui, c'est imprimer cette.
Maintenant que je sais que c'est> 0 et qu'il a satisfait à la première, si
Je ne vais même pas d'exécuter ce code.
Le code s'exécute plus rapidement, en fait, 3 fois plus vite si vous l'utilisez.
Nous avons aussi appris and et or.
Je ne vais pas passer par cette raison Lexi déjà parlé.
C'est juste les opérateurs && et | opérateur |.
>> La seule chose que je vais dire, c'est faire attention lorsque vous avez 3 conditions.
Utilisez les parenthèses parce que c'est très déroutant quand vous avez une condition
et un autre ou un autre.
Utilisez les parenthèses juste pour être sûr que vos conditions de sens
parce que dans ce cas, par exemple, vous pouvez imaginer que
ce pourrait être la première condition et l'une ou l'autre
ou les 2 conditions réunies dans un et
ou le troisième, si juste être prudent.
Et enfin, nous avons parlé des commutateurs.
Un commutateur est très utile lorsque vous avez une variable.
Disons que vous avez une variable comme n
qui peut être 0, 1, ou 2, et pour chacun de ces cas,
vous allez effectuer une tâche.
Vous pouvez dire passer la variable, et il indique que
la valeur est alors comme valeur1 je vais faire,
et puis je me casse, ce qui signifie que je ne vais pas chercher à tout les autres cas
car nous avons déjà convaincu que le cas
puis valeur2 et ainsi de suite, et je peux aussi avoir un interrupteur par défaut.
Cela signifie que si elle ne répond à aucun des cas que j'ai eu
que je vais faire quelque chose d'autre, mais c'est facultatif.
C'est tout pour moi. Maintenant, nous allons Tommy.
Bon, ça va être la semaine 3 à la rigueur.
Ce sont quelques-uns des sujets que nous aborderons, crypto, de la portée, des tableaux, etc.
Juste un petit mot sur la cryptographie. Nous n'allons pas à marteler cette maison.
>> Nous l'avons fait dans le pset 2, mais pour le quiz assurez-vous que vous connaissez la différence
entre le chiffre de César et le chiffrement de Vigenère,
comment tant de ceux qui travaillent chiffres et ce que c'est que de crypter
et le texte déchiffrer à l'aide de ces 2 chiffres.
Rappelez-vous, le chiffrement de César tourne simplement chaque caractère du même montant,
en vous assurant de mod par le nombre de lettres dans l'alphabet.
Et le chiffrement de Vigenère, d'autre part, chaque caractère tourne
d'un montant différent, donc plutôt que de dire
tous les caractères rotation par 3 Vigenère tourne chaque caractère
d'une quantité différente en fonction de certains mots clés
où chaque lettre dans le mot-clé représente une certaine quantité différente
pour faire pivoter le texte en clair par.
Parlons d'abord à propos de la portée des variables.
Il ya 2 types de variables.
Nous avons des variables locales, et celles-ci vont être définis
en dehors de main ou à l'extérieur de toute fonction ou de bloc,
et ceux-ci seront accessibles n'importe où dans votre programme.
Si vous avez une fonction et cette fonction est une boucle while
la grande variable globale est accessible partout.
Une variable locale, d'autre part, est portée à l'endroit où elle est définie.
>> Si vous avez une fonction ici, par exemple, nous avons cette fonction g,
et à l'intérieur de g y est une variable appelée ici y,
ce qui signifie qu'il s'agit d'une variable locale.
Même si cette variable est appelée y
et cette variable est appelée Y Ces 2 fonctions
n'ont aucune idée de ce que chacun des autres variables locales sont.
D'autre part, ici nous disons int x = 5,
et cela est en dehors de la portée de n'importe quelle fonction.
Il est hors de la portée de main, c'est donc une variable globale.
Cela signifie que l'intérieur de ces 2 fonctions quand je dis x - x ou + +
Je accéder à la même x où y présente et ce y sont des variables différentes.
C'est la différence entre une variable globale et une variable locale.
En ce qui concerne la conception, parfois c'est probablement une meilleure idée
de garder les variables locales chaque fois que vous le pouvez
car avoir un tas de variables globales peut être vraiment déroutant.
Si vous avez un tas de fonctions tout modifier la même chose
vous pourriez oublier que si cette fonction modifie accidentellement ce monde,
et cette autre fonction ne le savent pas,
et il ne devenir assez déroutant, car vous aurez plus de code.
Garder les variables locales chaque fois que vous le pouvez
est la conception juste bon.
Tableaux, rappelez-vous, sont tout simplement des listes d'éléments du même type.
A l'intérieur de CI ne peut pas avoir une liste comme 1, 2.0, bonjour.
Nous ne pouvons pas faire cela.
>> Lorsque nous déclarons un tableau en C, tous les éléments doivent être du même type.
Ici, j'ai un tableau de 3 entiers.
Ici, j'ai la longueur du tableau, mais si je ne fais que le déclarant dans cette syntaxe
où je préciser ce que tous les éléments sont je n'ai pas besoin de cette technique 3.
Le compilateur est assez intelligent pour comprendre l'ampleur de la gamme devrait être.
Maintenant, quand je veux obtenir ou définir la valeur d'un tableau
c'est la syntaxe pour faire cela.
Ce sera effectivement modifier le deuxième élément du tableau, car, rappelez-vous,
numérotation commence à 0 et non à 1.
Si je veux lire cette valeur que je peux dire quelque chose comme int x = array [1].
Ou si je veux mettre cette valeur, comme je le fais ici,
Je peux dire array [1] = 4.
Ce temps d'accéder aux éléments par leur index
ou sa position ou où ils se trouvent dans le tableau,
et que l'inscription commence à 0.
Nous pouvons également avoir des tableaux de tableaux,
et c'est ce qu'on appelle un tableau multi-dimensionnel.
Lorsque nous avons un tableau multi-dimensionnel
cela signifie que nous pouvons avoir quelque chose comme des rangées et des colonnes,
et ce n'est qu'un moyen de visualiser telle ou penser.
Quand j'ai un tableau multi-dimensionnel qui signifie que je vais commencer à avoir besoin
plus de 1 index parce que si j'ai une grille
juste dire ce que vous êtes en ligne ne nous donne pas un numéro.
C'est vraiment juste nous donner une liste de numéros.
Disons que j'ai ce tableau ici.
J'ai un tableau appelé grille, et je dis que c'est 2 lignes et 3 colonnes,
et donc c'est une façon de le visualiser.
Quand je dis que je veux obtenir l'élément à [1] [2]
cela veut dire que parce que ce sont des rangées d'abord, puis des colonnes
Je vais passer à la ligne 1 depuis que j'ai dit 1.
>> Ensuite, je vais venir ici à la colonne 2, et je vais obtenir la valeur 6.
Donner un sens?
Tableaux multi-dimensionnels, rappelez-vous, sont techniquement juste un tableau de tableaux.
Nous pouvons avoir des tableaux de tableaux de tableaux.
Nous pouvons continuer, mais vraiment une façon de penser
comment cela est présenté et ce qui se passe est de le visualiser
dans une grille comme ça.
Quand nous passer des tableaux à des fonctions, ils vont se comporter
un peu différemment que lorsque nous passer des variables à des fonctions régulières
comme le passage d'un int ou un float.
Quand nous passons dans un type int ou char ou l'autre de ces autres données
nous avons juste pris un coup d'oeil si la fonction modifie
la valeur de cette variable que le changement ne va pas se propager jusqu'à
à la fonction appelante.
Avec un tableau, d'un autre côté, cela se produira.
Si je passe dans un tableau à une fonction et que cette fonction modifie certains éléments,
quand je reviens à la fonction qui l'a appelé
mon tableau est désormais va être différent, et le vocabulaire pour que
est tableaux sont passés par référence, comme nous le verrons plus tard.
Ceci est lié à la façon dont le travail des pointeurs, où ces types de données de base,
d'autre part, sont passés par valeur.
>> Nous pouvons penser que de faire une copie d'une variable, puis en passant à la copie.
Il n'a pas d'importance ce que nous faisons avec cette variable.
La fonction d'appel ne sera pas conscient qu'il a été modifié.
Les tableaux sont un peu différent à cet égard.
Par exemple, comme nous venons de le voir, le principal est simplement une fonction
qui peut prendre de 2 arguments.
Le premier argument de la fonction principale est argc, ou le nombre d'arguments,
et le second argument est appelé argv,
et ce sont les valeurs réelles de ces arguments.
Disons que j'ai un programme appelé this.c,
et je dis faire cela, et je vais exécuter ce à la ligne de commande.
Maintenant, pour passer des arguments à mon programme appelé cela,
Je pourrais dire quelque chose comme. / Cs c'est 50.
C'est ce que nous imaginons David à faire chaque jour sur le terminal.
Mais aujourd'hui, la principale fonction à l'intérieur de ce programme
a ces valeurs, alors argc est de 4.
Il serait peut-être un peu déroutant parce que vraiment nous sommes seulement de passage dans cs est 50.
C'est seulement 3.
Mais rappelez-vous que le premier élément de argv ou le premier argument
est le nom de la fonction elle-même.
Cela signifie donc que nous avons 4 choses ici,
et le premier élément sera. / ce.
Et ce sera représenté par une chaîne.
Ensuite, les éléments restants sont ce que nous avons tapé dans la suite du nom du programme.
Ainsi, tout comme en passant, que nous avons probablement vu dans pset 2,
rappelez-vous que la chaîne 50 est ≠ du 50 entier.
Donc, nous ne pouvons pas dire quelque chose comme, "int x = argv 3. '
>> C'est tout simplement pas de sens, car il s'agit d'une chaîne de caractères, ce qui est un entier.
Donc, si vous voulez convertir entre les 2, rappelez-vous, nous allons
avoir cette fonction magique appelé atoi.
Qui prend une chaîne et retourne l'entier représenté à l'intérieur de cette chaîne.
Donc, c'est une erreur facile à faire sur le questionnaire,
train de penser que ce sera automatiquement le type correct.
Mais il suffit de savoir que ceux-ci seront toujours chaînes
même si la chaîne contient uniquement un nombre entier ou un caractère ou un flotteur.
Alors maintenant, nous allons parler de temps de fonctionnement.
Lorsque nous aurons toutes ces algorithmes qui font toutes ces choses folles,
il devient vraiment utile de se poser la question: «Combien de temps prennent-ils?"
Nous représentons que par ce qu'on appelle la notation asymptotique.
Donc, cela signifie que - eh bien, disons que nous donnons notre algorithme
une entrée vraiment, vraiment, vraiment grand.
Nous voulons poser la question: «Combien de temps ça va prendre?
Combien d'étapes faut-il notre algorithme à exécuter
en fonction de la taille de l'entrée? "
Donc, la première façon, nous pouvons décrire moment de l'exécution est avec grand O.
Et c'est notre temps marche le pire des cas.
Donc, si on veut trier un tableau, et nous donnons notre algorithme un tableau
c'est dans l'ordre décroissant alors qu'il devrait être dans l'ordre croissant,
qui va être le pire des cas.
C'est notre limite supérieure de la durée maximale du temps de notre algorithme va prendre.
D'autre part, cette Ω va décrire le meilleur des cas le temps d'exécution.
Donc, si nous donnons un tableau déjà triés à un algorithme de tri,
combien de temps faut-il pour faire le tri?
Et cela, alors, décrit une borne inférieure sur le temps d'exécution.
Alors voici juste quelques mots qui décrivent moments les plus fréquents en cours d'exécution.
Ce sont dans l'ordre croissant.
Le temps le plus rapide en cours d'exécution que nous avons est appelé constante.
>> Cela signifie que peu importe le nombre d'éléments que nous donnons notre algorithme,
peu importe la taille de notre tableau est, le tri
ou faire tout ce que nous faisons pour l'ensemble prendra toujours le même laps de temps.
Donc, nous pouvons représenter que juste avec un 1, qui est une constante.
Nous avons également examiné lors de l'exécution logarithmique.
Donc, quelque chose comme la recherche binaire est logarithmique,
où nous avons réduit de moitié le problème à chaque fois
et puis les choses simplement obtenir plus à partir de là.
Et si jamais vous êtes écrit un joint de n'importe quel algorithme factorielle,
vous ne devriez pas considérer cela comme votre travail quotidien.
Lorsque nous comparons les temps de fonctionnement, il est important de garder à l'esprit ces choses.
Donc, si j'ai un algorithme qui est O (n), et quelqu'un d'autre
a un algorithme en O (2n) ce sont en fait asymptotiquement équivalente.
Donc, si nous imaginons que N soit un grand nombre comme undécante milliards d'euros:
alors quand nous comparons undécante milliards à quelque chose comme undécante milliards + 3,
tout à coup que 3 n'a pas vraiment faire une grosse différence plus.
C'est pourquoi nous allons commencer à considérer ces choses comme équivalentes.
Donc, des choses comme ces constantes ici, il ya 2 x ce, ou en ajoutant un 3,
ce ne sont que des constantes, et ceux-ci vont tomber en place.
Voilà pourquoi tous les 3 de ces durées de fonctionnement sont les mêmes que dire qu'ils sont en O (n).
De même, si nous avons 2 temps d'exécution d'autres, disons O (n + 2n ³ ²), nous pouvons ajouter
+ N, + 7, puis nous avons un autre moment de l'exécution, c'est juste O (n ³).
encore une fois, il s'agit de la même chose parce ceux-ci - ce ne sont pas les mêmes.
Ce sont les mêmes choses, désolé. Ce sont donc les mêmes que
ce n ³ va dominer cette 2n ².
>> Ce qui n'est pas la même chose est si nous avons manqué des moments comme O (n ³) et O (n ²)
car ce n ³ est beaucoup plus grande que ce n ².
Donc, si nous avons des exposants, tout à coup cela commence à la matière,
mais quand nous ne faisons que traiter avec des facteurs tels que nous sommes ici,
alors il ne va pas d'importance, car ils vont tout simplement à l'abandon.
Jetons un coup d'oeil à quelques-uns des algorithmes que nous avons vu jusqu'à présent
et parler de leur exécution.
La première façon de chercher un numéro dans une liste, que nous avons vu, était la recherche linéaire.
Et la mise en œuvre de la recherche linéaire est super simple.
Nous venons d'avoir une liste, et nous allons nous pencher sur chaque élément de la liste
jusqu'à ce qu'on trouve le nombre que nous recherchons.
Cela signifie donc que dans le pire des cas, en O (n).
Et le pire cas en l'espèce pourrait être si l'élément est
le dernier élément, puis en utilisant la recherche linéaire, nous devons regarder chaque élément
jusqu'à ce que nous arrivons à la dernière pour savoir que c'était en fait dans la liste.
Nous ne pouvons pas abandonner à mi-chemin et dire: «Ce n'est probablement pas là-bas."
Avec la recherche linéaire, nous devons regarder l'ensemble.
Le temps de fonctionnement meilleur des cas, d'autre part, est constante
parce que dans le meilleur des cas, l'élément que nous voulons, c'est juste le premier dans la liste.
Donc, il va falloir nous exactement 1 étape, peu importe la taille de la liste est
si nous cherchons le premier élément à chaque fois.
>> Ainsi, lorsque vous effectuez une recherche, rappelez-vous, il n'est pas nécessaire que notre liste soit triée.
Parce que nous allons simplement regarder par-dessus chaque élément, et il n'a pas vraiment d'importance
quel ordre ces éléments sont po
Un algorithme de recherche plus intelligente est quelque chose comme binaire de recherche.
Rappelez-vous, la mise en œuvre de la recherche binaire, c'est quand vous allez
continuer à chercher au milieu de la liste.
Et parce que nous cherchons au milieu, nous exigeons que la liste est triée
ou bien nous ne savons pas où est le milieu, et nous devons nous pencher sur
toute la liste pour le trouver, puis à ce moment nous sommes en train de perdre du temps.
Donc, si nous avons une liste triée et nous trouvons au milieu, nous allons comparer le milieu
à l'élément que nous recherchons.
Si elle est trop élevée, alors on peut oublier la moitié droite
parce que nous savons que si notre élément est déjà trop élevé
et tout à droite de cet élément est encore plus élevé,
alors nous n'avons pas besoin de chercher plus là.
Où d'autre part, si notre élément est trop faible,
nous savons tout sur la gauche de cet élément est également trop faible,
de sorte qu'il n'a pas vraiment de sens à chercher là non plus.
De cette façon, à chaque pas et à chaque fois que nous regardons le milieu de la liste,
nous allons réduire notre problème à moitié parce que tout d'un coup, nous savons
tout un tas de chiffres qui ne peuvent pas être celui que nous cherchons.
>> En pseudocode cela ressemble à quelque chose comme ça,
et parce que nous réduisons la liste en deux à chaque fois,
nos pires sauts temporels terme de linéaire à logarithmique.
Alors tout d'un coup, nous avons log-in étapes afin de trouver un élément dans une liste.
Le temps de fonctionnement meilleur des cas, cependant, est toujours constante
parce que maintenant, disons simplement que l'élément que nous voulons, c'est
toujours exactement au milieu de la liste originale.
Ainsi, nous pouvons développer notre liste aussi grande que nous voulons, mais si l'élément que nous cherchons se trouve au milieu,
puis il va seulement pour nous emmener étape 1.
C'est pour cela que nous sommes en O (log n) et Ω (1) ou constant.
Nous allons effectivement lancer la recherche binaire sur cette liste.
Donc, disons que nous sommes à la recherche de l'élément 164.
La première chose que nous allons faire est de trouver le point médian de cette liste.
Il se trouve que le milieu va se situent entre ces 2 numéros,
donc on va plutôt dire arbitrairement, chaque fois que le point médian se situe entre 2 numéros,
disons simplement arrondir.
Nous devons juste nous assurer que nous faisons cela chaque étape du chemin.
Donc, nous allons arrondir, et nous allons dire que 161 est le milieu de notre liste.
Si 161 <164, et chaque élément de la gauche de 161
est aussi <164, alors nous savons que ça ne va pas nous aider à tous
commencer à regarder par ici parce que l'élément que nous recherchons ne peut pas être là.
Donc, ce que nous pouvons faire, c'est nous pouvons simplement oublier que la moitié de toute la gauche de la liste,
et maintenant ne considère que le droit de compter des 161.
>> Encore une fois, c'est le point central; disons simplement arrondir.
175, est trop grand.
Donc, nous savons qu'il ne va pas nous aider à regarder ici ou là,
afin que nous puissions simplement jette ça et, finalement, nous allons frapper le 164.
Toutes les questions sur la recherche binaire?
Passons à autre chose de chercher dans une liste déjà triée
à prendre effectivement une liste de numéros dans un ordre quelconque
et de mettre cette liste dans l'ordre croissant.
Le premier algorithme, nous avons examiné a été appelé tri à bulles.
Et ce serait plus simple des algorithmes que nous avons vu.
Tri à bulles dit que quand les 2 éléments à l'intérieur de la liste sont hors de place,
signifiant qu'il ya un plus grand nombre vers la gauche d'un nombre inférieur,
alors nous allons les changer, parce que cela signifie que la liste sera
«Plus triés» qu'il ne l'était auparavant.
Et nous allons tout simplement continuer ce processus encore et encore et encore
jusqu'à ce que finalement le genre de bulle éléments à leur emplacement correct et nous avons une liste triée.
>> Le moment de l'exécution de ce qui se passe à O (n ²). Pourquoi?
Eh bien, parce que dans le pire des cas, nous allons prendre tous les éléments, et
nous allons finir par le comparant à tout autre élément dans la liste.
Mais dans le meilleur des cas, nous avons une liste déjà triée, bulle sorte de
tout va passer par une fois, dire "Non. Je n'ai pas fait de swaps, donc je suis fait."
Nous avons donc un temps meilleur des cas en cours d'exécution de Ω (n).
Lançons tri à bulles sur une liste.
Ou, disons simplement examiner certains pseudo-code très rapidement.
Nous voulons dire que nous voulons suivre, à chaque itération de la boucle,
de garder trace de si oui ou non nous avons changé tous les éléments.
Donc, la raison en est, nous allons nous arrêter quand nous n'avons pas échangé les éléments.
Ainsi, au début de notre boucle, nous n'avons pas échangé quoi que ce soit, donc nous allons dire que c'est faux.
Maintenant, nous allons parcourir la liste et comparer l'élément i de l'élément i + 1
et si c'est le cas, qu'il existe un plus grand nombre à la gauche d'un nombre plus petit,
puis nous allons juste pour les échanger.
>> Et puis nous allons vous rappeler que nous avons échangé un élément.
Cela signifie que nous avons besoin de passer par la liste d'au moins 1 plus de temps
parce que la condition dans laquelle il est arrêté lorsque la liste entière est déjà triées,
ce qui signifie que nous n'avons pas fait de swaps.
C'est pour cela que notre condition est ici en bas »tandis que certains éléments ont été échangés.
Alors maintenant, nous allons simplement regarder cette course sur une liste.
J'ai la liste 5,0,1,6,4.
Tri bulle va commencer tout le chemin à gauche, et il va de comparer
les éléments de I, de manière à 0 i + 1, qui est l'élément 1.
Il va dire, bien 5> 0, mais en ce moment 5 est vers la gauche,
donc j'ai besoin d'échanger le 5 et le 0.
Quand je les échanger, tout d'un coup je me procurer cette liste différente.
Maintenant, 5> 1, donc nous allons les échanger.
5 n'est pas> 6, donc nous n'avons pas besoin de faire quoi que ce soit ici.
Mais 6> 4, donc nous avons besoin d'échanger.
Encore une fois, nous avons besoin de parcourir toute la liste pour finalement découvrir
que ceux-ci sont hors d'usage, nous les échanger,
et en ce moment nous avons besoin de parcourir la liste 1 plus de temps
pour s'assurer que tout est dans l'ordre, et à ce genre de point de bulle est terminée.
Un autre algorithme pour la prise de certains éléments et en les triant est une sorte de sélection.
L'idée derrière tri par sélection, c'est que nous allons mettre en place une partie de la liste triée
1 élément à la fois.
>> Et la façon dont nous allons faire est de construire le segment gauche de la liste.
Et dans le fond, tous les - de chaque étape, nous allons prendre le plus petit élément que nous avons laissé
qui n'a pas encore été triés, et nous allons le déplacer dans ce segment triés.
Cela signifie que nous devons continuellement trouver l'élément minimum non triés
et ensuite prendre cet élément minimum et l'échanger contre quelque
laissé plus-élément qui n'est pas trié.
Le moment de l'exécution de ce qui se passe à O (n ²), car dans le pire des cas
nous avons besoin de comparer chaque élément à tous les autres éléments.
Parce que nous disons que si nous commençons à la moitié gauche de la liste, nous avons besoin
passer par l'ensemble du segment à droite pour trouver le plus petit élément.
Et puis, encore une fois, nous avons besoin d'aller sur la totalité du segment droit et
continuer sur cette maintes et maintes et maintes fois.
Cela va être n ². Nous allons avoir besoin d'une boucle pour l'intérieur d'une autre boucle for
ce qui suggère ² n.
Dans le meilleur des cas, la pensée, disons que nous lui donnons une liste déjà triée;
nous avons en fait ne font pas mieux que n ².
Parce tri par sélection n'a aucun moyen de savoir que
l'élément minimum est juste celui que je arriver à examiner.
Il reste encore à faire en sorte que ce soit effectivement le minimum.
>> Et la seule façon de s'assurer que c'est le minimum, en utilisant cet algorithme,
consiste à examiner chaque élément nouveau.
Alors, vraiment, si vous lui donnez - si vous donnez tri par sélection une liste déjà triée,
il ne va pas faire mieux que de lui donner une liste qui n'est pas encore triées.
Soit dit en passant, si elle arrive à être le cas que quelque chose est en O (quelque chose)
et l'oméga de quelque chose, nous pouvons simplement dire plus succinctement qu'il est θ de quelque chose.
Donc, si vous voyez que trouver n'importe où, c'est ce que cela veut dire tout simplement.
>> Si quelque chose ne thêta de n ², il est à la fois de grande taille O (n ²) et Ω (n ²).
Donc le meilleur des cas et le pire des cas, il ne fait pas de différence,
l'algorithme va faire la même chose à chaque fois.
Voilà donc ce que pseudocode pour le tri de sélection pourrait ressembler.
Essentiellement, nous allons dire que je veux parcourir la liste
de gauche à droite, et à chaque itération de la boucle, je vais passer
l'élément minimum dans cette partie de la liste triée.
Et une fois que je déplace quelque chose, je n'ai jamais besoin de regarder cet élément nouveau.
Parce que dès que je remplace un élément dans le segment gauche de la liste, c'est réglé
parce que nous faisons tout dans l'ordre croissant en utilisant des minimums.
Alors nous avons dit, d'accord, nous sommes à i position, et nous avons besoin de regarder tous les éléments
à droite de i pour trouver le minimum.
Cela signifie donc que nous voulons examiner de i + 1 à la fin de la liste.
Et maintenant, si l'élément que nous examinons actuellement est inférieure à notre minimum jusqu'à présent,
qui, rappelez-vous, nous commençons l'arrêt minimum pour être juste
quel que soit l'élément que nous sommes actuellement à; je suppose que c'est le minimum.
Si je trouve un élément qui est plus petit que cela, alors je vais dire, d'accord,
eh bien, j'ai trouvé un nouveau minimum.
Je vais me rappeler où ce minimum était.
>> Alors maintenant, une fois que je suis passé par ce segment de droite non triés,
Je peux dire que je vais permuter l'élément minimal de l'élément qui se trouve dans la position i.
Cela va constituer ma liste, mon triés partie de la liste de gauche à droite,
et nous n'avons pas toujours besoin de regarder un élément nouveau une fois dans la partie.
Une fois que nous avons échangé.
Alors lançons tri par sélection sur cette liste.
L'élément bleu ici va être le i, et l'élément rouge va être l'élément minimum.
Donc, je commence tout le chemin à gauche de la liste, donc à 5.
Maintenant, nous devons trouver l'élément minimum non triés.
Donc, nous disons 0 <5, alors 0 est mon nouveau minimum.
>> Mais je ne peux pas arrêter là, parce que même si nous pouvons reconnaître que 0 est le plus petit,
nous avons besoin de parcourir tout autre élément de la liste pour vous en assurer.
Donc 1 est plus grand, 6 est plus grand, 4 est plus grand.
Cela signifie que, après avoir examiné l'ensemble de ces éléments, j'ai déterminé 0 est le plus petit.
Donc, je vais échanger le 5 et le 0.
Une fois que j'échange, je vais me faire une nouvelle liste, et je sais que je n'ai jamais besoin de regarder que 0 fois
car une fois que je l'ai échangé, je l'ai triées et nous avons fini.
Maintenant, il se trouve que l'élément bleu est de nouveau le 5,
et nous avons besoin de regarder le 1, le 6 et le 4 pour déterminer que 1
est l'élément le plus petit minimum, donc nous allons échanger le 1 et le 5.
Encore une fois, nous avons besoin de regarder - comparer le 5 au 6 et le 4,
et nous allons échanger le 4 et le 5, et enfin, de comparer
ces 2 numéros et de les échanger jusqu'à ce que nous obtenions notre liste triée.
Toute question concernant tri par sélection?
D'accord. Passons au dernier sujet ici, et c'est la récursivité.
>> Récursivité, rappelez-vous, cette chose méta vraiment où une fonction
appelle à plusieurs reprises lui-même.
Donc, à un moment donné, alors que notre fuction est sans cesse se demandant,
il doit y avoir un moment où nous cessons de nous appeler.
Parce que si nous ne faisons pas cela, alors nous allons juste continuer à faire ce pour toujours,
et notre programme est tout simplement pas prêt à se terminer.
Nous appelons cette condition, le scénario de base.
Et le scénario de référence dit, plutôt que d'appeler une fonction encore une fois,
Je vais retourner une valeur.
Donc, une fois que nous avons retourné une valeur, nous avons cessé de nous appeler,
et le reste des appels que nous avons faites jusqu'ici peuvent également retourner.
Le contraire de l'hypothèse de base est le cas récursif.
Et c'est à ce moment que nous voulons faire un autre appel à la fonction que nous sommes actuellement po
Et nous avons probablement, mais pas toujours, à utiliser des arguments différents.
>> Donc, si nous avons une fonction appelée f, et f vient de m'appeler prendre 1 argument,
et nous venons de continuer à appeler f (1), f (1), f (1), et il se trouve que
l'argument 1 tombe sous le cas récursif, nous sommes encore jamais cesser.
Même si nous avons un cas de base, nous devons faire en sorte que finalement nous allons frapper ce cas de base.
Nous n'avons pas simplement continuer en restant dans ce cas récursif.
En général, lorsque nous nous appelons, nous allons probablement avoir un argument différent à chaque fois.
Voici une fonction récursive très simple.
Donc, ce sera de calculer la factorielle d'un nombre.
Jusqu'à haut nous avons ici notre scénario de base.
Dans le cas où n ≤ 1, nous n'allons pas faire appel à nouveau factorielle.
Nous allons nous arrêter, nous allons juste retourner une valeur.
Si ce n'est pas le cas, alors nous allons frapper notre cas récursif.
Notez ici que nous ne sommes pas seulement appel factorielle (n), parce que ce ne serait pas très utile.
Nous allons appeler factorielle de quelque chose d'autre.
>> Et si vous pouvez le voir, par la suite si nous adoptons une chose factorielle (5) ou,
nous allons faire appel factorielle (4) et ainsi de suite, et finalement nous allons frapper ce cas de base.
Donc, ça a l'air bon. Voyons voir ce qui se passe quand on fait exécuter ce.
Il s'agit de la pile, et disons que principal va appeler cette fonction avec un argument (4).
Donc, une fois factorielle voit et = 4, factorielle sera s'appeler elle-même.
Maintenant, tout à coup, nous avons factorielle (3).
Ainsi, ces fonctions vont continuer de croître jusqu'à ce que finalement nous avons atteint notre scénario de base.
À ce stade, la valeur de retour de ceci est le retour (nx la valeur de retour de cette intervention),
la valeur de retour de cette nx est la valeur de retour de cette.
Finalement, nous avons besoin de frapper un certain nombre.
En haut ici, nous disons retour 1.
Cela signifie qu'une fois que nous revenons ce nombre, on peut sauter ce de la pile.
Donc, ce factorielle (1) est fait.
Lorsque retourne 1, ce factoriels (1) revient, ce retour à 1.
La valeur de retour de cela, rappelez-vous, était nx la valeur de retour de cette.
Alors tout d'un coup, ce gars sait ce que je veux revenir 2.
>> Donc n'oubliez pas, la valeur de retour de cette nx est juste la valeur de retour ici.
Alors maintenant, nous pouvons dire 3 x 2, et enfin, ici, nous pouvons dire
cela va juste être 4 x 3 x 2.
Et une fois que ces retours, nous nous attelons à l'intérieur d'un seul entier de main.
Toute question relative à la récursivité?
Très bien. Il n'y a donc plus de temps pour les questions à la fin,
mais maintenant Joseph portera sur les sujets restants.
>> [Joseph Ong] Très bien. Alors, maintenant que nous avons parlé de récurrences,
parlons un peu de ce que le tri par fusion est.
Le tri par fusion est essentiellement une autre façon de trier une liste de nombres.
Et comment cela fonctionne-dire, avec une sorte de fusion, vous avez une liste, et ce que nous faisons est
nous disons, nous allons diviser ce en 2 moitiés.
Nous allons d'abord exécuter le tri par fusion à nouveau sur la moitié gauche,
alors nous courrons le tri par fusion sur la moitié droite,
et cela nous donne maintenant 2 moitiés qui sont triées, et maintenant nous allons combiner les deux moitiés ensemble.
C'est un peu difficile de voir sans exemple, nous allons donc passer par les mouvements et voir ce qui se passe.
Donc, vous commencez avec cette liste, nous l'avons divisé en 2 moitiés.
Nous courons le tri par fusion sur la moitié gauche d'abord.
Donc, c'est la moitié gauche, et maintenant nous les faire fonctionner grâce à cette liste encore
ce qui se passe dans le tri par fusion, puis nous attendons, encore une fois,
sur le côté gauche de cette liste et nous courons le tri par fusion sur elle.
Maintenant, nous nous attelons à une liste de 2 nombres,
et maintenant la moitié gauche est à seulement 1 élément de long, et nous ne pouvons
diviser une liste qui est seulement 1 élément dans la moitié, donc nous avons juste dire, une fois que nous avons 50,
qui est à seulement 1 élément, il est déjà triée.
>> Une fois que nous aurons fini avec ça, nous pouvons voir ce que nous pouvons
passer à la moitié droite de cette liste,
et 3 est également triée, et maintenant que les deux moitiés de cette liste sont triés
nous pouvons joindre à ces numéros de retour ensemble.
Nous cherchons donc à 50 et 3, 3 est plus petit que 50, donc il va en premier et ensuite 50 entre en jeu.
Maintenant, c'est fait, nous remontons à cette liste et trier c'est la moitié droite.
42 est son propre numéro, il est donc déjà triés.
Alors maintenant, nous comparons ces 2 et 3 est plus petit que 42, de sorte que se mettre en premier,
maintenant 42 se mettre, et 50 se mettre po
Maintenant, ce n'est trié, nous allons tous le chemin du retour vers le haut, 1337 et 15.
Eh bien, nous regardons à présent la moitié gauche de cette liste; 1337 est par elle-même si elle est triée et même 15.
Alors maintenant, nous combinons ces 2 numéros pour trier cette liste initiale, 15 <1337,
il en va en premier, puis 1337 va po
Et maintenant, nous avons trié les deux moitiés de la liste originale en haut.
Et tout ce que nous devons faire est de combiner celles-ci.
Nous regardons les 2 premiers numéros de la liste, 3 <15, donc ça va dans le tableau Tri.
15 <42, alors il va po Maintenant, 42 <1337, qui va po
50 <1337, donc il va po Et remarquez que nous avons juste pris 2 numéros hors de cette liste.
Donc, nous ne sommes pas seulement une alternance entre les 2 listes.
Nous cherchons simplement au début, et nous prenons l'élément
qui est plus petit, puis le mettre dans notre tableau.
Maintenant, nous avons fusionné tous les deux et nous avons fini.
>> Une question sur le tri par fusion? Oui?
[Étudiants] Si c'est diviser en différents groupes, pourquoi ne pas simplement le diviser une fois
et vous avez 3 et 2 dans un groupe? [Reste de l'inintelligible question]
La raison pour laquelle - si la question est, pourquoi ne peut-on pas simplement de les fusionner à cette première étape après nous les avoir?
La raison pour laquelle nous pouvons faire cela, commencez par les éléments les plus à gauche des deux côtés,
puis prendre le plus petit et le mettre dans, c'est que nous savons que ces
différentes listes sont triées dans les ordres.
Donc, si je regarde les éléments plus à gauche des deux moitiés,
Je sais qu'ils vont être les plus petits éléments de ces listes.
Donc, je peux les mettre dans les endroits les plus petits éléments de cette liste exhaustive.
D'autre part, si je regarde ces 2 listes au second niveau, là-bas,
50, 3, 42, 1337 et 15, ceux-ci sont non trié.
Donc, si je regarde 50 et 1337, je vais mettre 50 dans ma première liste.
Mais cela n'a pas vraiment de sens, car 3 est le plus petit élément de l'ensemble de ceux-ci.
Donc, la seule raison pour laquelle nous pouvons faire cette étape de combinaison est parce que nos listes sont déjà triés.
C'est pourquoi nous devons nous mettre tout le chemin vers le bas
parce que quand nous avons un nombre unique, vous savez qu'un seul numéro
en soi est déjà une liste triée.
>> Des questions? Non?
Complexité? Eh bien, vous pouvez voir qu'à chaque étape il ya un nombre finaux,
et nous pouvons diviser une liste dans le journal de moitié n fois,
et c'est là que nous obtenons ce log n x n la complexité.
Et vous verrez le meilleur des cas pour le tri fusion est n log n, et il se trouve
que le pire des cas, ou le Ω là-bas, est aussi n log n.
Quelque chose à garder à l'esprit.
Sur la route, nous allons passer à un fichier super basique I / O.
Si vous avez regardé Scramble, vous remarquerez que nous avions une sorte de système
où l'on pouvait écrire dans un fichier journal si vous lisez le code.
Voyons comment vous pourriez le faire.
Eh bien, nous avons fprintf, que vous pouvez considérer comme juste printf,
mais juste l'impression d'un fichier au lieu, et par conséquent le f au début.
Cette sorte de code ici, ce qu'il fait est, comme vous avez pu voir dans la lutte confuse,
il passe par votre impression de tableau à 2 dimensions rangée par rangée quels sont les chiffres.
Dans ce cas, imprime printf sur votre terminal ou ce que nous appelons la sortie standard de la section.
>> Et maintenant, dans ce cas, tout ce que nous avons à faire est de remplacer printf avec fprintf,
lui dire ce fichier que vous souhaitez imprimer, et dans ce cas il imprime juste sur ce fichier
au lieu de l'afficher sur votre terminal.
Eh bien, cela soulève la question: Où peut-on obtenir ce genre de fichier, pas vrai?
Nous avons passé connecter à ce fuction fprintf, mais nous n'avions aucune idée d'où il vient.
Eh bien, au début du code, ce que nous avions était ce bout de code ici,
qui dit essentiellement que le fichier ouvert appelle log.txt.
Que faisons-nous après cela est que nous devons faire en sorte que le fichier est ouvert avec succès.
Ainsi, il peut échouer pour de multiples raisons, vous n'avez pas assez d'espace sur votre ordinateur, par exemple.
Donc, il est toujours important avant de faire des opérations avec le fichier
que nous vérifions si ce fichier a été ouvert avec succès.
Alors qu'est-ce qu'un, c'est un argument de fopen, eh bien, nous pouvons ouvrir un fichier de plusieurs façons.
Ce que nous pouvons faire, c'est, nous pouvons lui passer w, ce qui signifie remplacer le fichier s'il existe déjà,
Nous pouvons passer un un, dont ils ajouter à la fin du fichier au lieu de l'écraser,
ou nous pouvons spécifier r, ce qui signifie, nous allons ouvrir le fichier en lecture seule.
Donc, si le programme tente d'apporter des modifications au fichier,
crier après eux et ne pas les laisser faire.
Enfin, une fois que nous en avons terminé avec le fichier, fini de faire des opérations sur elle,
nous devons nous assurer que nous fermez le fichier.
Et si à la fin de votre programme, vous allez les passer à nouveau
ce fichier que vous avez ouvert, et il suffit de fermer.
Donc, c'est quelque chose d'important que vous devez vous assurer que vous faites.
Alors, n'oubliez pas que vous pouvez ouvrir un fichier, vous pouvez écrire dans le fichier,
effectuer des opérations dans le fichier, mais alors vous devez fermer le fichier à la fin.
>> Toute question concernant le fichier de base d'E / S? Oui?
[Question étudiants, inintelligible]
Juste ici. La question est, d'où vient ce fichier log.txt apparaissent-elles?
Eh bien, si vous venez de lui donner log.txt, il le crée dans le même répertoire que l'exécutable.
Donc, si Tu es - >> [question étudiants, inintelligible]
Oui. Dans le même dossier, ou dans le même répertoire, comme vous l'appelez.
Maintenant, mémoire, pile et tas.
Alors, comment la mémoire est énoncé dans l'ordinateur?
Eh bien, vous pouvez imaginer la mémoire comme type de ce bloc ici.
Et dans la mémoire que nous avons ce qu'on appelle le tas coincé là-bas, et la pile qui est là-bas.
Et le tas pousse vers le bas et vers le haut de la pile grandit.
Alors que Tommy a mentionné - oh, bien, et nous avons ces 4 autres segments que je vais obtenir dans un instant -
Comme Tommy dit plus tôt, vous savez combien ses fonctions s'appellent eux-mêmes et d'appeler les uns les autres?
Ils construisent ce genre de cadre de pile.
Eh bien, si les appels principaux foo, foo se mettre sur la pile.
Foo appelle, bar get mettre sur la pile, et que se mettre sur la pile après.
Et à leur retour, ils reçoivent chacun enlevé la pile.
Qu'est-ce que chacun de ces lieux de mémoire et maintenez?
Eh bien, en haut, qui est le segment de texte, contient le programme lui-même.
Ainsi, le code machine, qui est là, une fois que vous compilez votre programme.
Ensuite, toute initialisation des variables globales.
>> Vous avez donc des variables globales dans votre programme, et vous dire que j'aime, a = 5,
que se mettre dans ce segment, et le droit en vertu de ce,
vous avez des données non initialisées mondiaux, ce qui est tout simplement un int,
mais vous ne dites pas que c'est égal à quoi que ce soit.
Réalisez ce sont des variables globales, de sorte qu'ils sont à l'extérieur du principal.
Donc, cela signifie que toutes les variables globales sont déclarées mais ne sont pas initialisés.
Alors, quelle est dans le tas? La mémoire allouée avec malloc, qui nous y reviendrons dans un peu.
Et enfin, avec la pile vous avez des variables locales
et toutes les fonctions que vous pourriez appeler dans n'importe lequel de leurs paramètres.
La dernière chose, vous n'avez pas vraiment besoin de savoir quelles sont les variables d'environnement font,
mais chaque fois que vous lancez le programme, il ya quelque chose associée, comme
il s'agit du nom de la personne qui dirigeait le programme.
Et cela va être une sorte de vers le bas.
En termes d'adresses de mémoire, qui sont des valeurs hexadécimales,
les valeurs qui sont au top start à 0, et ils vont tout le chemin vers le bas.
Dans ce cas, si vous êtes sur le système 32-bit,
l'adresse indiquée au bas va être 0x, suivie d'af, parce que c'est 32 bits,
qui est de 8 octets, et dans ce cas, correspond à 8 octets 8 chiffres hexadécimaux.
Donc ici vous allez avoir, comme, 0xffffff, et là-haut, vous allez avoir 0.
Alors, quels sont les pointeurs? Certains d'entre vous peuvent ne pas avoir parlé dans la section précédente.
mais nous sommes allés au-dessus de conférence, ainsi qu'un pointeur est juste un type de données
les magasins qui, au lieu d'une sorte de valeur comme 50, il stocke l'adresse d'un emplacement mémoire.
Comme ce mémoire [inintelligible].
Donc dans ce cas, ce que nous avons dit, nous avons un pointeur vers un entier ou un int *,
et il contient cette adresse hexadécimale de 0xDEADBEEF.
>> Donc, ce que nous avons, c'est que maintenant, ce pointeur à un endroit dans la mémoire,
et que c'est juste une, la valeur 50 est à cet emplacement mémoire.
Sur certains systèmes 32-bit, sur tous les systèmes 32-bits, les pointeurs prendre jusqu'à 32 bits ou 4 octets.
Mais, par exemple, sur un système 64-bit, les pointeurs sont 64 bits.
Donc, c'est quelque chose que vous aurez envie de garder à l'esprit.
Ainsi, sur un système d'extrémité bits, un pointeur est embouts longtemps.
Les pointeurs sont un peu difficile à digérer sans choses supplémentaires,
nous allons donc passer par un exemple d'allocation dynamique de mémoire.
Quelle allocation dynamique de mémoire fait pour vous, ou ce que nous appelons malloc,
il vous permet d'allouer une sorte de données à l'extérieur de l'appareil.
Ainsi, ces données est en quelque sorte plus permanente pendant toute la durée du programme.
Parce que, comme vous le savez, si vous déclarez x à l'intérieur d'une fonction, et que les retours de fonction,
vous n'avez plus accès aux données qui ont été stockées dans x.
Qu'est-ce pointeurs laissez-nous faire, c'est qu'ils nous stocker des valeurs de mémoire ou un magasin
dans un autre segment de mémoire, à savoir le tas.
Maintenant, une fois nous revenons sur la fonction, aussi longtemps que nous avons un pointeur
à cet emplacement dans la mémoire, ce que nous pouvons faire, c'est nous pouvons simplement regarder les valeurs de ce pays.
Voyons un exemple: Il s'agit de notre organisation de la mémoire à nouveau.
Et nous avons cette fonction, principal.
Ce qu'il fait est - d'accord, si simple, droite - int x = 5, c'est juste une variable sur la pile en principal.
>> D'un autre côté, maintenant, nous déclarons un pointeur qui appelle les giveMeThreeInts fonction.
Et maintenant nous allons dans cette fonction et nous créons un nouveau frame de pile pour elle.
Cependant, dans ce cadre de pile, nous déclarons int * temp,
qui mallocs 3 entiers pour nous.
Donc taille de int nous donnera le nombre d'octets de cette int est,
et malloc nous donne ce nombre d'octets d'espace sur le tas.
Donc dans ce cas, nous avons créé un espace suffisant pour 3 entiers,
et le tas est là-haut, c'est pourquoi je l'ai dessiné plus haut.
Une fois que nous aurons terminé, nous reviendrons ici, il vous suffit besoin de 3 ints de retour,
et il renvoie l'adresse, dans ce cas, plus que la mémoire où est.
Et nous avons mis pointeur = interrupteur, et là-haut, nous avons juste un autre pointeur.
Mais qu'est-ce que renvoie la fonction sont empilées et disparaît.
Donc température disparaît, mais nous maintenons l'adresse de l'endroit où
ces 3 entiers sont à l'intérieur du secteur.
Donc, dans cet ensemble, les pointeurs ont une portée limitée localement pour le cadre empilés,
mais la mémoire à laquelle ils se réfèrent est dans le tas.
>> Est-ce logique?
[Étudiants] Pourriez-vous répéter? >> [Joseph] Oui.
Donc, si je reviens un peu, vous verrez que temporaire alloué
de la mémoire sur le tas là-haut.
Alors, quand cette fonction, giveMeThreeInts retours, cette pile ici va disparaître.
Et avec elle l'une des variables, dans ce cas, ce pointeur qui a été alloué dans le châssis empilés.
Qui va disparaître, mais depuis notre retour temporaire
et nous avons mis pointeur = temp, le pointeur va maintenant pointer le même mémoire de lieu d'installation temporaire a été.
Alors maintenant, même si nous perdons temporaire, ce pointeur local,
nous avons toujours conserver l'adresse mémoire de ce qu'il était orienté vers l'intérieur de ce pointeur variable.
Des questions? Cela peut être un peu déroutant si un sujet vous n'êtes pas allé au-dessus de la section.
Nous pouvons, votre carte de TF va certainement aller au-dessus et bien sûr, nous pouvons répondre à des questions
à la fin de la session d'examen pour cela.
Mais c'est en quelque sorte d'un sujet complexe, et je n'ai plus d'exemples qui vont se présenter
qui aidera à clarifier ce que sont en réalité des pointeurs.
>> Dans ce cas, les pointeurs sont équivalentes aux tableaux,
si je peux utiliser ce pointeur comme la même chose comme un tableau int.
Donc, je suis d'indexation en 0, et en changeant le premier entier à 1,
changer le nombre entier de 2 secondes, et le troisième nombre entier de 3.
Donc plus sur les pointeurs. Eh bien, rappelez-Binky.
Dans ce cas, nous avons prévu un pointeur, ou nous avons déclaré un pointeur,
mais au début, quand je vient de déclarer un pointeur, ce n'est pas pointer vers n'importe quelle destination dans la mémoire.
C'est seulement à l'intérieur des valeurs parasites de celui-ci.
Donc, je n'ai aucune idée où ce pointeur pointe.
Il possède une adresse qui est juste remplie avec des 0 et des 1, où il a été initialement déclarée.
Je ne peux pas faire n'importe quoi avec ce que j'appelle malloc sur elle
et puis il me donne un peu d'espace sur le tas où je peux mettre des valeurs à l'intérieur.
Là encore, je ne sais pas ce qu'il ya dedans de cette mémoire.
Donc la première chose que j'ai à faire est de vérifier si le système avait assez de mémoire
de me rendre entier 1, en premier lieu, et c'est pourquoi je fais ce contrôle.
Si le pointeur est nul, ce qui signifie qu'il n'a pas assez d'espace ou qu'une autre erreur s'est produite,
donc je devrais quitter mon programme d'études.
Mais si c'était le cas réussir, maintenant je peux utiliser ce pointeur
et ce pointeur * fait est qu'il suit, où l'adresse est
à l'endroit où cette valeur est, et il définit le égal à 1.
Donc, ici, nous vérifions si la mémoire existé.
>> Une fois que vous savez qu'il existe, vous pouvez mettre dans l'
la valeur que vous voulez mettre dedans, dans ce cas 1.
Une fois que nous aurons fini avec elle, vous avez besoin de libérer ce pointeur
car nous avons besoin de revenir au système que la mémoire que vous avez demandé en premier lieu.
Parce que l'ordinateur ne sais pas quand nous aurons fini avec elle.
Dans ce cas, nous sommes explicitement dit, d'accord, nous en avons fini avec cette mémoire.
Si un autre processus dont il a besoin, un autre programme dont il a besoin, n'hésitez pas à aller de l'avant et de le prendre.
Ce que nous pouvons faire, c'est aussi nous pouvons simplement obtenir l'adresse des variables locales sur le plateau.
Donc x int est à l'intérieur du cadre empilés de main.
Et quand on utilise cette esperluette, ce et l'opérateur, ce qu'il fait est
il prend x, et x est à seulement quelques données en mémoire, mais il a une adresse.
Il est situé quelque part. Donc, en appelant & x, ce que cela fait est qu'il nous donne l'adresse de x.
En faisant cela, nous faisons le point pointeur à l'endroit où x est dans la mémoire.
Maintenant, nous n'avons tout simplement quelque chose comme * x, nous allons obtenir 5 arrière.
L'étoile est appelée, elle déréférencement.
Vous suivez l'adresse et vous obtenez la valeur de celui-ci qui y sont stockées.
>> Des questions? Oui?
[Étudiants] Si vous ne faites pas la chose la 3-pointu, at-il encore compiler?
Oui. Si vous ne faites pas la chose la 3-pointeur, il va continuer à compiler,
mais je vais vous montrer ce qui se passe en une seconde, et sans cela,
c'est ce que nous appelons une fuite de mémoire. Vous ne donnez pas le système
sauvegarder sa mémoire, donc après un certain temps le programme va s'accumuler
mémoire que ce n'est pas l'aide, et rien d'autre ne peut l'utiliser.
Si vous avez jamais vu Firefox avec 1,5 millions de kilo-octets sur votre ordinateur,
dans le gestionnaire de tâches, c'est ce qui se passe.
Vous avez une fuite de mémoire dans le programme qu'ils ne sont pas de la manipulation.
Alors, comment pointeur arithmétique travail?
Eh bien, l'arithmétique des pointeurs est une sorte d'indexation comme dans un tableau.
Dans ce cas, j'ai un pointeur, et ce que je fais, c'est que faire pointer pointeur vers le premier élément
de ce tableau de 3 entiers que j'ai attribués.
Alors maintenant, ce que je fais, star-pointeur change juste le premier élément de la liste.
Star Pointer +1 points plus ici.
Donc pointeur est ici, pointeur +1 est ici, pointeur +2 est ici.
>> Il suffit donc d'ajouter 1 est la même chose que se déplacer le long de cette baie.
Ce que nous faisons est, quand nous faisons une pointeur vous obtenez l'adresse par ici,
et afin d'obtenir la valeur ici, vous avez mis une étoile à partir de l'expression entière
pour le déréférencez.
Donc, dans ce cas, je vais régler le premier emplacement dans ce tableau à 1,
second emplacement à 2, et 3 de troisième emplacement.
Alors qu'est-ce que je fais ici, c'est que je l'impression de notre pointeur +1,
ce qui me donne juste 2.
Maintenant, je suis d'incrémentation du pointeur, afin pointeur est égale pointeur +1,
qui se déplace vers l'avant.
Et maintenant si je imprimer pointeur +1, +1 est maintenant pointeur 3,
qui dans ce cas imprime 3.
Et pour quelque chose de gratuit, le pointeur que je lui donne
doit être pointée vers le début du tableau que je viens de rentrer d'malloc.
Donc, dans ce cas, si je devais appeler 3 ici, ce ne serait pas juste,
parce que c'est dans le milieu du tableau.
Je dois soustraire pour se rendre à l'emplacement d'origine
place initiale du prénom avant que je puisse le libérer.
Donc, voici un exemple plus complet.
Dans ce cas, nous allouons 7 caractères dans un tableau de caractères.
>> Et dans ce cas, ce que nous faisons, c'est que nous bouclant sur les 6 premiers d'entre eux,
et nous leur mise à Z.
Ainsi, par int i = 0, i> 6, i + +,
Donc, je vais pointeur + vient de nous donner, dans ce cas,
pointeur, le pointeur +1, pointeur +2, le pointeur +3, et ainsi de suite, et ainsi de suite dans la boucle.
Qu'est-ce que ça va faire, c'est se que l'adresse, il déréférence pour obtenir la valeur,
et les changements que la valeur d'un Z.
Puis, à la fin n'oubliez pas que c'est une chaîne, pas vrai?
Toutes les chaînes doivent se terminer par le caractère nul final.
Donc, ce que je fais est en pointeur 6 Je mis le caractère nul de terminaison po
Et maintenant que je suis fondamentalement faire ici est la mise en œuvre d'une chaîne de printf, non?
>> Alors, quand est-ce printf maintenant quand il est arrivé à la fin d'une chaîne?
Quand il frappe le caractère nul final.
Donc, dans ce cas, mes pointeur d'origine au début de ce tableau.
Je imprimer sur le premier caractère. Je le déplacer plus d'un.
Je imprimer ce caractère sur. Je le déplacez sur.
Et je continue ainsi jusqu'à ce que j'arrive à la fin.
Et maintenant le pointeur de fin * va déréférencer cela et le caractère nul final retour.
Et donc ma boucle while s'exécute uniquement lorsque cette valeur n'est pas le caractère nul final.
Donc, maintenant je sors de sortir de cette boucle.
Et si je soustrais 6 de ce pointeur,
Je retourne tout le chemin vers le début.
Rappelez-vous, je fais cela parce que je dois aller au début afin de le libérer.
>> Donc, je sais que c'était beaucoup. Y at-il des questions?
S'il vous plaît, oui?
[Inintelligible question des étudiants]
Pouvez-vous dire que plus fort? Désolé.
[Étudiants] Sur la dernière diapositive juste avant de libérer le pointeur,
Où étiez-vous réellement changer la valeur du pointeur?
[Joseph] Donc, ici. >> [Étudiants] Oh, d'accord.
[Joseph] Donc, j'ai un pointeur de moins en moins, à droite,
qui déplace l'arrière d'une chose, et puis je l'ai libérer,
parce que ce pointeur est à signaler le début de la matrice.
[Étudiants] Mais ce ne serait pas nécessaire si vous aviez cessé après cette ligne.
[Joseph] Donc, si je m'étais arrêté après cela, ce serait considéré comme une fuite de mémoire,
parce que je n'ai pas couru la liberté.
[Étudiants] je [inintelligible], après les trois premières lignes où vous avez eu pointeur +1 [inintelligible].
[Joseph] Uh-huh. Alors, quelle est la question là-bas?
Désolé. Non, non. Allez, allez, s'il vous plaît.
[Étudiants] Donc, vous ne changez pas la valeur de pointeurs.
Vous n'auriez pas dû faire pointeur minus.
[Joseph] Oui, exactement.
Donc, quand je fais pointeur pointeur +1 et +2,
Je ne fais pointeur est égale pointeur +1.
Ainsi, le pointeur reste simplement faire remarquer au début du tableau.
C'est seulement quand je fais plus plus qu'il définit la valeur à l'intérieur du pointeur,
qu'il se déplace le long de cette réalité.
Très bien.
Plus de questions?
>> Encore une fois, si cela est une sorte de majorité, ce sera couvert en session.
Demandez à votre adjoint à l'enseignement à ce sujet, et nous pouvons répondre à des questions à la fin.
Et généralement, nous n'aimons pas faire cette chose moins.
Cela doit exiger de moi garder une trace de tout ce que j'ai décalé dans le tableau.
Donc, en général, c'est juste pour vous expliquer comment fonctionne l'arithmétique des pointeurs.
Mais ce que nous avons l'habitude j'aime faire, c'est que nous aimons pour créer une copie du pointeur,
puis nous allons utiliser cette copie lorsque nous déplacer dans la chaîne.
Donc, dans ces cas, vous utilisez la copie d'imprimer la totalité de la chaîne,
mais nous n'avons pas à faire comme pointeur moins 6 ou de garder une trace de combien nous avons emménagé dans ce domaine,
juste parce que nous savons que notre point de départ est toujours indiqué au début de la liste
et tout ce que nous avons modifié cette copie.
Donc, en général, modifier des copies de votre pointeur original.
N'essayez pas de régler de même - ne modifie exemplaires originaux.
Tenter de modifier seules les copies de l'original.
Donc, vous remarquez quand on passe la corde dans printf
vous n'avez pas besoin de mettre une étoile en face d'elle, comme nous l'avons fait avec tous les autres déréférence, non?
Donc, si vous imprimez la totalité de la chaîne s% s'attend à une adresse,
et dans ce cas un pointeur ou dans ce cas comme un tableau de caractères.
>> Caractères, char * s, et les tableaux sont la même chose.
Pointer est de personnages, et des tableaux de caractères sont la même chose.
Et donc, tout ce que nous avons à faire est de passer le pointeur.
Nous n'avons pas à passer de la même pointeur * ou quelque chose comme ça.
Ainsi, les tableaux et les pointeurs sont la même chose.
Quand vous faites quelque chose comme x [y] par ici pour un tableau,
ce qu'il fait sous le capot, c'est que c'est dit, d'accord, c'est un tableau de caractères,
c'est donc un pointeur.
Et si x est la même chose,
et si ce qu'il fait est qu'il ajoute y à x,
qui est la même chose que d'avancer dans la mémoire tant que ça.
Et maintenant, x + y nous donne une sorte d'adresse,
et nous déréférencez l'adresse ou suivez la flèche
à l'endroit où cet emplacement en mémoire est et nous obtenons la valeur de cet emplacement dans la mémoire.
Donc, si ces deux sont exactement la même chose.
C'est juste un sucre syntaxique.
Ils font la même chose. Ils sont juste différents syntactics un pour l'autre.
>> Alors, qu'est-ce qui peut mal tourner avec des pointeurs? Comme, beaucoup. D'accord. Ainsi, les mauvaises choses.
Certaines mauvaises choses que vous pouvez faire ne sont pas de vérifier si votre appel malloc retourne null, non?
Dans ce cas, je demande au système de me donner - ce qui est ce numéro?
Comme 2 milliards de fois 4, parce que la taille d'un entier de 4 octets.
Je suis en train de demander comme 8 milliards d'octets.
Bien sûr, mon ordinateur ne va pas être en mesure de me donner ce retour de mémoire.
Et nous n'avons pas vérifié si cela est nul, donc quand nous essayons de le déréférencer là-bas -
suivez la flèche à l'endroit où il va - nous n'avons pas cette mémoire.
C'est ce que nous appelons le déréférencement d'un pointeur NULL.
Et cela provoque une erreur de segmentation essentiellement vous.
C'est l'une des façons dont vous pouvez segfault.
D'autres mauvaises choses que vous pouvez faire - mais bon.
Qui a été déréférencement d'un pointeur NULL. D'accord.
D'autres mauvaises choses - ainsi, pour résoudre ce problème que vous venez de mettre un frein à y
qui vérifie si le pointeur est nul
et quitter le programme si il arrive que malloc retourne un pointeur nul.
C'est la bande dessinée xkcd. Les gens le comprends maintenant. En quelque sorte.
>> Ainsi, la mémoire. Et je suis allé à ce sujet.
Nous lançons un appel malloc dans une boucle, mais à chaque fois que nous appelons malloc
nous perdons la trace de où ce pointeur pointe vers,
parce que nous le démolir.
Ainsi, le premier appel à malloc me donne la mémoire ici.
Mes pointeurs de pointeurs à cela.
Maintenant, je n'ai pas le libérer, alors maintenant je appeler malloc nouveau.
Maintenant, il fait ici. Maintenant, ma mémoire est orienté par ici.
Pointant ici. Pointant ici.
Mais j'ai perdu la trace des adresses de toute la mémoire par ici que je allouée.
Et maintenant, je n'ai pas de référence à plus d'eux.
Donc, je ne peux pas les libérer en dehors de cette boucle.
Et donc, afin de réparer quelque chose comme ça,
si vous oubliez de libérer de la mémoire et vous obtenez cette fuite de mémoire,
Vous devez libérer de la mémoire à l'intérieur de cette boucle une fois que vous avez terminé avec lui.
Eh bien, c'est ce qui arrive. Je sais que beaucoup d'entre vous déteste ça.
Mais maintenant - yay! Vous obtenez comme 44.000 kilo-octets.
Donc, vous le libérer à la fin de la boucle,
et qui va tout simplement libérer la mémoire à chaque fois.
Essentiellement, le programme n'a pas de fuite de mémoire plus.
>> Et maintenant, quelque chose que vous pouvez faire est de libérer de la mémoire que vous avez demandé à deux reprises.
Dans ce cas, quelque chose malloc, vous changez sa valeur.
Vous le libérer une fois parce que vous avez dit que vous aviez fini avec elle.
Mais ensuite on libère à nouveau.
C'est quelque chose qui est assez mauvais.
Il ne va pas d'abord une erreur de segmentation,
mais après un moment ce que ce ne soit à double libération de ce corrompt la structure de votre tas,
et vous en apprendrez un peu plus à ce sujet si vous choisissez de prendre une classe comme CS61.
Mais, essentiellement, après un certain temps que votre ordinateur va se confondre
sur ce que sont les emplacements mémoire où et où il est stocké -
où les données sont stockées dans la mémoire.
Et ainsi de libérer un pointeur est deux fois une mauvaise chose que vous ne voulez pas faire.
>> D'autres choses qui peuvent mal se passer n'est pas en utilisant sizeof.
Donc, dans ce cas vous malloc 8 octets,
et c'est la même chose que deux entiers, non?
Donc, c'est tout à fait sûr, mais est-il?
Eh bien, comme Lucas a parlé sur différentes architectures,
les entiers sont de longueurs différentes.
Ainsi, sur l'appareil que vous utilisez, les entiers sont sur 4 octets,
mais sur un autre système, ils pourraient être de 8 octets ou ils pourraient être de 16 octets.
Donc, si je viens d'utiliser ce nombre ici,
ce programme pourrait fonctionner sur l'appareil,
mais il ne va pas allouer suffisamment de mémoire sur un autre système.
Dans ce cas, c'est ce que l'opérateur sizeof est utilisé pour.
Lorsque nous appelons sizeof (int), ce que ne fait
il nous donne la taille d'un entier sur le système que le programme est en cours d'exécution.
Donc, dans ce cas, sizeof (int) retourne quelque chose comme 4 sur l'appareil,
et maintenant cette volonté 4 * 2, qui est de 8,
qui est juste la quantité d'espace nécessaire pour deux entiers.
Sur un autre système, si un int est comme 16 octets ou 8 octets,
il va tout simplement de revenir suffisamment d'octets pour stocker ce montant.
>> Et enfin, les structures.
Donc, si vous voulez stocker un conseil sudoku en mémoire, comment pourrions-nous le faire?
Vous pourriez penser comme une variable pour la première chose,
une variable pour la deuxième chose, une variable pour la troisième chose,
une variable pour le quatrième chose - mal, non?
Ainsi, une amélioration que vous pouvez faire sur le dessus de cela est de faire un 9 x 9.
C'est très bien, mais que faire si vous voulez associer d'autres choses avec le conseil sudoku
comme ce que la difficulté du conseil d'administration est,
ou, par exemple, ce que votre score est, ou combien de temps il vous a fallu pour résoudre ce forum?
Eh bien, qu'est-ce que vous pouvez faire est que vous pouvez créer une structure.
Ce que je veux dire, c'est fondamentalement je définir cette structure par ici,
et je définir un conseil sudoku qui consiste en une planche qui est de 9 x 9.
>> Et ce qu'il a il a des pointeurs vers le nom du niveau.
Il a aussi x et y, qui sont les coordonnées de l'endroit où je suis maintenant.
Il a également passé du temps [inintelligible], et il a le nombre total de mouvements que j'ai entrés jusqu'ici.
Et dans ce cas, je peux regrouper tout un tas de données dans une seule structure
au lieu de l'avoir comme voler autour de la même différentes variables
que je ne peux pas vraiment suivre.
Et cela nous permet d'avoir juste la syntaxe agréable pour le référencement sorte de choses différentes à l'intérieur de cette structure.
Je peux juste faire board.board, et je reçois le conseil sudoku en arrière.
Board.level, je reçois combien il est difficile.
Board.x et board.y me donner les coordonnées de l'endroit où je pourrais être dans le conseil d'administration.
Et je suis donc accéder à ce que nous appelons les champs de la struct.
Ceci définit sudokuBoard, qui est un type que j'ai.
Et maintenant nous sommes ici. J'ai une variable appelée «conseil» de sudokuBoard type.
Et alors maintenant je peux accéder à tous les champs qui composent cette structure par ici.
>> Une question sur votre structs? Oui?
[Étudiants] Pour int x, y, vous avez déclaré à la fois sur une seule ligne? >> [Joseph] Uh-huh.
[Étudiants] Alors, pourriez-vous faire avec chacun d'eux?
Comme dans x, y virgule fois que le total?
[Joseph] Oui, vous pouvez certainement le faire, mais la raison pour laquelle j'ai mis x et y sur la même ligne -
et la question est pourquoi pouvons-nous simplement faire sur la même ligne?
Pourquoi ne pas simplement mettre tous ces sur la même ligne est
x et y sont liées les unes aux autres,
et ce n'est qu'un style plus correct, en un sens,
car il regroupe à deux choses sur la même ligne
ce genre comme de se rapporter à la même chose.
Et je viens de diviser celles-ci en dehors. C'est juste une chose style.
Il est fonctionnellement aucune différence.
D'autres questions sur structs?
Vous pouvez définir un Pokédex avec une struct.
Un Pokémon possède un numéro et il a une lettre, un propriétaire, un type.
Et puis, si vous avez un tableau de Pokémon, vous pouvez faire un Pokédex, non?
Ok, cool. Ainsi, les questions relatives structures. Ceux sont liés aux structures.
>> Enfin, GDB. Qu'est-ce que GDB vous laisser faire? Il vous permet de déboguer votre programme.
Et si vous n'avez pas utilisé GDB, je recommande à regarder le court
et aller juste au-dessus de ce que GDB est de savoir comment vous travaillez avec lui, comment vous pourriez l'utiliser,
et le tester sur un programme.
Et donc ce qui vous permet de faire GDB est-il permet de mettre en pause la [inaudible] de votre programme
et une ligne de pratique.
Par exemple, je veux suspendre l'exécution à la ligne 3 comme de mon programme,
et pendant que je suis à la ligne 3 je peux imprimer toutes les valeurs qui sont là-bas.
Et si ce que nous appelons comme une pause dans une ligne
est nous appelons cela de mettre un point d'arrêt sur cette ligne
et alors nous pouvons imprimer les variables à l'état du programme à ce moment-là.
>> Nous pouvons alors à partir de là passer en revue le programme ligne par ligne.
Et puis nous pouvons regarder l'état de la pile à l'heure.
Et donc pour pouvoir utiliser GDB, ce que nous faisons est que nous appelons bruit sur le fichier C,
mais nous devons lui passer le drapeau ggdb-.
Et une fois que nous aurons terminé avec ce que nous venons de lancer gdb sur le fichier de sortie qui en résulte.
Et si vous avez un peu de masse comme du texte comme celui-ci,
mais vraiment tout ce que vous avez à faire est de taper des commandes au début.
Pause principale met un point d'arrêt à principal.
Liste des 400 énumère les lignes de code autour de la ligne 400.
Et dans ce cas il vous suffit de regarder autour et dire, oh,
Je veux mettre un point d'arrêt à la ligne 397, qui est de cette ligne,
puis votre programme s'exécute dans cette étape et il va se casser.
Ça va faire une pause là, et vous pouvez imprimer, par exemple, la valeur de basse ou haute.
Et donc il ya un tas de commandes que vous devez savoir,
et ce diaporama montera sur le site,
donc si vous voulez juste faire référence à celles-ci ou comme les mettre sur vos feuilles de triche, n'hésitez pas.
>> Cool. C'était Jeu Revue 0, et nous allons rester dans les parages si vous avez des questions.
Très bien.
>> [Applaudissements]
>> [CS50.TV]