[Música tocando] 

[REPRODUCIÓN DE VIDEO] 

-El Está mentindo. 

-Sobre que? 

-Eu Non sei. 

-Entón, ¿Que sabemos? 

-Iso Ás 9:15, Ray Santoya estaba no cadro electrónico. -Si. Entón a pregunta é, o que estaba facendo en 09:16? 

-Shooting A nove milímetros en algo. Quizais el viu o tire. 

-ou Estaba traballando con el. 

Espera. Volva un. 

-O Que ve? 

-Trazer A cara superior pantalla completa. 

Cristais -His. 

-Hai Unha reflexión. 

-É O equipo de béisbol Nuevitas. Ese é o seu logotipo. 

-E Está falando con quen está a usar esa chaqueta. 

[FIN DE REPRODUCIÓN] 

DAVID Malan: Todo ben. Esta é CS50 e iso é un pouco máis de [inaudível] coa que está xogar con problema establecer catro. Hoxe comezamos a mirar un pouco máis profundamente para isto chamadas punteiros, que a pesar de ser un tema moi misterioso, verifícase que vai a ser o medio a través do cal nós Pode comezar a construír e montar programas moito máis sofisticado. Pero o que fixemos o mércores pasado por medio dalgúns claymation primeiro. Polo tanto, este, recall, é Binky e usamos lo para dar un ollo a un programa que realmente non fai nada de interesante, pero revelou algúns problemas. Entón, para comezar hoxe, por que non podemos andar rapidamente a través de algúns destes pasos, tentar destilar en termos de humanos exactamente o que está a suceder aquí e por que iso é malo, e, a continuación, seguir adiante e realmente comezar a construír algo con esta técnica? Entón, eses foron os primeiros dúas liñas neste programa e en termos leigos, que son estas dúas liñas facendo? Alguén que é razoablemente cómodo co que está declarado na pantalla? Cales son esas dúas liñas que fan? Non é todo o que diferente dunha semana, pero hai algún novo símbolo especial. Si? Volver alí. 

Audiencia: Declarando punteiros? DAVID Malan: Diga novo? Audiencia: Declarando punteiros? DAVID Malan: Declarando e punteiros Imos refinala-lo un pouco máis. Audiencia: [inaudível] dirección e, a continuación, x y. DAVID Malan: E, a continuación, abordar. Entón, especialmente o que estamos facendo é que estamos a declarar dúas variables. Estas variables, con todo, van para ser do tipo int estrela, que significa concreto eles van para almacenar a dirección de un int, respectivamente, X e Y. Agora hai calquera valores? Hai algún enderezos reais nestes dúas variables neste momento no tempo? Non. É só chamados valores de lixo. Se realmente non asignar un variable, o que estaba na RAM anteriormente vai cubrir con ceros e as dúas desas variables. Pero aínda non sabemos o que son e que é será a clave para por que Binky perdeu a cabeza a semana pasada. 

Polo tanto, este foi o claymation encarnación do presente en que ten só dúas variables, pequenos anacos circulares de arxila, que pode almacenar variables, pero canto as frechas implicadas enriba suxiren, eles non están realmente apuntando a calquera lugar coñecido per se. Entón, despois, tivo esta liña, e esta era novo a semana pasada, malloc para a memoria asignación, que é só un xeito elegante de dicir ao sistema operativo, Linux ou Mac OS ou Windows, hey, me dea un pouco de memoria, e todo o que ten que dicir o sistema operativo é o que cando pedíndolle para a memoria. El non vai importar co vai facer con el, pero ten que dicir ao funcionamento sistema que por medio de malloc. Si? 

Audiencia: Canto? DAVID Malan: Canto? Canto en bytes, e así, este, de novo, un exemplo artificial, está só dicindo, dáme o tamaño dun int. Agora, o tamaño dun int é de catro bytes ou 32 bits. Polo tanto, esta é só unha forma de dicindo, hey, sistema operativo, dáme catro bytes de memoria que podo usar a miña disposición, e, especialmente, o que fai retorno malloc respecto para ese anaco de catro bytes? Audiencia: Enderezo? DAVID Malan: O enderezo. O enderezo dese anaco de catro bytes. Exactamente. E iso é o que está almacenado en definitiva, en x e é por iso que nós realmente non importa o que o número de que dirección é, se é OX1 ou ox2 ou algún enderezo hexadecimal enigmática. Nós só coidar pictoricamente que esa variable x é agora apuntando a que o anaco de memoria. Así, a frecha representa un punteiro, ou máis especificamente, un enderezo de memoria. Pero, de novo, non importa tipicamente o que estes enderezos son reais. Agora, esta liña di o que en termos leigos? Estrela x recibe 42 punto e coma. O que significa isto? Quere ir? Non arranhe seu pescozo. 

Audiencia: O enderezo x está no 42. 

DAVID Malan: O enderezo de x é a 42. Non é ben así. Tan preto, pero non completamente, porque non hai a estrela que está prefixing este x. Por iso, necesitamos axustar un pouco. Si? 

Audiencia: O valor que punteiro x está a apuntar cara é de 42. DAVID Malan: Aceptar. O valor que o punteiro x é apuntando para, digamos, será 42, ou dito doutra forma, a estrela x di, ir a calquera outro enderezo está x, tanto se se trata dunha Oxford Rúa 33 ou Oxford Street ou OX1 ou ox33, calquera que sexa que dirección numérico é, estrela x é a dereferencing x. Entón, vai a este enderezo e a continuación, poñer o número 42 alí. Así que sería un xeito equivalente a dicir iso. Entón, iso é todo moi ben e, a continuación, que representaría a imaxe deste xeito, onde nós engadimos o 42 a ese pedazo de catro bytes no lateral dereita, pero esta liña foi onde as cousas deron mal ea cabeza de Binky estalou fóra neste punto, porque cousas malas suceden cando vostede dereference valores de lixo ou cancelar a referencia válida punteiros, e digo non válido porque neste momento no historia, o que está dentro y? Cal é o valor de base y nas poucas etapas pasadas? Si? Que é iso? 

Audiencia: Este enderezo. DAVID Malan: Este enderezo. Debe ser un enderezo pero teño inicializar-lo? Entón eu non teño aínda. Entón, o que é coñecido por ser aí? É só un valor de lixo. Podería ser calquera enderezo de cero a 2 millóns se ten dous Gb de RAM, ou cero a 4 millóns se ten ten catro gigabytes de memoria RAM. É un valor de lixo, pero o problema é que o sistema operativo, se non lle deu que pedazo de memoria especialmente que estás ir, vai xeralmente para causar o que vimos como un fallo de segmento. Entón, en realidade, calquera de vostedes que teñen esforzouse en problemas no horario de oficina ou en problemas que é máis xeralmente con tentando descubrir un fallo de segmentación, que xeralmente significa está tocando un segmento de memoria que non debe ser. Está tocando memoria que o sistema operativo non ten permítelle tocar, se é por ir demasiado lonxe na súa matriz ou a partir de agora, se é porque está tocando memoria que é só un valor de lixo. 

Así facendo estrela x aquí é tipo de comportamento indefinido. Vostede non debe facelo porque as probabilidades son, o programa só vai fallar, porque está dicindo, vaia a este enderezo e non ten idea de onde este enderezo realmente é. Así, o sistema operativo é probable indo para frear o seu programa como resultado e, de feito, iso é o que pasou alí para Binky. Entón, finalmente, fixado Binky este problema con este. Así que o programa en si foi fallo. Pero se especie de avanzar e executar esta liña no seu lugar, y é igual x significa só o que quere dirección é un x, tamén poñelas y. 

E así pictoricamente, temos esta representada con dúas frechas desde xe de y ligazón para o mesmo lugar. Así semanticamente, x é igual para y porque ambos daqueles almacenar a mesma enderezo, ergo apuntando para 42, e agora, cando di estrela y, vaia ao enderezo en y, este ten un efecto secundario interesante. Así, a dirección na que y é a mesmo que a dirección en x. Entón, se di que ir ao enderezo en y e cambie o valor para 13, Quen máis é afectado? X é, punto D, por así dicir, deben ser afectados tamén. 

E, de feito, como Nick tirei esta foto en claymation foi exactamente iso. Aínda que nós seguimos o punteiro y, acabamos no mesmo lugar, e así se estivésemos a imprimir out x ou y de pointee, entón veriamos o valor de 13. Agora, eu digo pointee ser consistente co vídeo. Programmers, ao meu coñecemento, nunca realmente dicir a palabra pointee, o que está apuntado no, pero a consistencia co vídeo, entende iso é todo o que era significaba nesa situación. Así dúbidas sobre claymation ou punteiros ou só malloc aínda? Non? Todo ben. 

Así, sen máis delongas, imos dar un ollo onde iso ten realmente foi utilizado durante algún tempo. Entón tivemos esta biblioteca CS50 que ten todas estas funcións. Usamos GetInt moito, GetString, probablemente GetLongLong anterior Na miña PSet un ou máis, pero o que está realmente a suceder? Ben, imos dar un ollo rápida por baixo do capuz con un programa que inspira por que nós dámoslle o CS50 biblioteca, e de feito como a semana pasada, que comezou a tomar os Rodas pequenas. Entón, iso agora está clasificada dun post-mortem que xa se arrastra dentro da biblioteca CS50, aínda que agora comezará a moverse lonxe dela para a maioría dos programas. 

Polo tanto, este é un programa chamado scanf 0. É super curta. El só ten estas liñas, pero introduce unha función chamada scanf que en realidade estamos indo a ver en un momento no interior da biblioteca CS50, aínda que dunha forma un pouco diferente. Polo tanto, este programa na liña 16 é declarar unha variable x. Entón me dea catro bytes por int. El dixo a usuario, número por favor, e, a continuación, esta é unha liña que interesante realmente une a semana pasada e este. Scanf, e, a continuación, entender que é preciso un formato de cadea, así como printf, % I significa un int, e, a continuación, leva un segundo argumento que parece un pouco descolados. É ampersand x, e para recordar, nós só vin iso xa a semana pasada. O que fai e comercial x representan? ¿Que facer en C e comercial? Si? 

Audiencia: O enderezo de. DAVID Malan: O enderezo de. Polo tanto, é o contrario o operador de estrela, mentres que o operador estrela di, ir Neste enderezo, o operador E comercial di, descubrir a dirección desa variable, e por iso esta é a clave, porque O propósito de scanf na vida é comprobar o usuario de a entrada do teclado, dependendo do que el ou ela tipos, e, a continuación, ler a entrada dese usuario nunha variable, pero nós viu nas últimas dúas semanas que a referida función de conmutación que intentou sen esforzo para aplicar só estaba roto. Lembre que coa función de intercambio, se nós só declarado A e B como ints, fixemos intercambiar con éxito o dúas variables dentro intercambio Así como con leite e DO, pero así como intercambio volveu, cal foi o resultado respecto a x e y, os valores orixinais? Nada. Si. Nada aconteceu naquela época, porque swaps cambiar só as súas copias locais, o que quere dicir, todos esta vez, sempre que temos foi pasando argumentos ás funcións, estamos só de paso copias destes argumentos. Pode facer que o que quere con eles, pero eles van ter ningún efecto sobre os valores orixinais. Entón, iso é problemático se quero ter unha función como scanf na vida, cuxo obxectivo é facer a pescudas a entrada do usuario desde o teclado e despois encher os espazos en branco, para falar, é dicir, dar unha variable como x un valor, porque se eu fose só para pasar x para scanf, se considerar a lóxica da última semana, scanf pode facer o que quere cunha copia de x, pero non podía cambiar permanentemente x salvo que damos scanf un mapa do tesouro, por así dicir, onde X marca o lugar, en que pasamos a dirección x para que scanf pode ir alí e realmente cambiar o valor de x. E así, de feito, todo que este programa fai se eu fai scanf 0, na miña fonte Directorio 5m, facer scanf 0, dot cortar scanf, número por favor 50, grazas ao 50. 

Polo tanto, non é tan interesante, pero o que está de feito a suceder é que así que eu chamo scanf aquí, o valor de x está sendo permanentemente cambiar. Agora, iso parece bo e bo, e de feito, Parece que realmente non precisa a biblioteca CS50 en todo máis. Por exemplo, imos realizar isto unha vez aquí. Déixeme reabrídelo por un segundo. Imos tentar un número por favor e en vez de dicir 50 como antes, imos só dicir non. OK, iso é un pouco raro. Aceptar. E só algunhas bobadas aquí. Por iso, non parece xestionar situacións erradas. Entón, necesitamos minimamente inicio engadindo un pouco de verificación de erros para asegurarse de que o usuario ten ingresaran nun número real como 50, porque, ao parecer, escribindo palabras non se detecta como problemática, pero probablemente debe ser. 

Imos ollar para esta versión agora que é miña tentativa de reimplementar GetString. Se scanf ten todo isto funcionalidade incorporada, por que fomos a xogar con estas Rodas pequenas como GetString? Ben, aquí é, quizais, o meu propio versión simple do GetString en que unha semana, eu podería dicir, dáme unha corda e chamalo de buffer. Hoxe, eu vou comezar só dicindo estrela char, que, recall, é só sinónimo. Parece asustado, pero é exactamente o mesmo. Entón me dea un buffer variable chamada que está indo a almacenar unha secuencia de caracteres, dicir a cadea user por favor, e, a continuación, como antes, imos tratar prestar esta lección scanf % S neste momento e, a continuación, pasar en tapón. Agora, unha comprobación de sanidade rápida. Por que non estou dicindo E comercial tapón esta vez? Inferir a partir do exemplo anterior. Audiencia: Char estrela é un punteiro. DAVID Malan: Exactamente, porque este tempo, char estrela xa é un punteiro, un enderezo, por definición, de estar alí aquela estrela. E se scanf espera un enderezo, basta só pasar tapón. Non preciso dicir tapón e comercial. Para os curiosos, podería facer algo así. El significado diferente. Isto lle daría un punteiro dun punteiro, o cal é en realidade unha cousa válida en C, pero para Agora, imos mantelo simple e manter a historia consistente. Eu só vou pasar en tapón e iso é correcto. O problema, porén, é este. Deixe-me ir adiante e executar ese programa tras compilalo. Fai scanf 1. Porra, meu compilador de pegando o meu erro. Dáme un segundo. Clang. Imos dicir que scanf-1.c. Aceptar. Alí imos nós. Necesítoo. CS50 ID ten varios configuración que protexen vostede contra ti mesmo. Eu precisaba desactivar os de executando clang manualmente polo de agora. Entón cadea por favor. Eu estou indo a ir adiante e escribir no meu mundo Ola favorito. OK, null. Isto non é o que eu escriba. Polo que é indicativo de que algo está mal. Deixe-me ir adiante e escriba nun tempo moi longo cadea. Grazas pola nulo e non sei se eu vou ser capaz de lanzalo. Imos tentar un pouco de copia pegar e ver se iso axuda. Pode pegar unha morea de presente. É en definitiva un maior cadea que o habitual. Nós só realmente escribilo. Non. Droga. Non comandar atopados. Entón, iso é non relacionado. Isto é porque eu colei algúns personaxes malos, pero iso acaba non vai traballar. 

Imos tentar que unha vez máis, porque é máis divertido se realmente lanzalo. Imos escribir isto e agora, eu son indo para copiar unha cadea moi longa e agora imos ver se nós pode bater esa cousa. Repare que eu omitido espazos e novas liñas correo comas e todos os personaxes de funky. Intro. E agora a rede só sendo lento. I preme Command-V moito tempo, claro. Droga! Non comandar atopados. 

Aceptar. Ben, o punto é con todo, o seguinte. Entón, o que está realmente a suceder sobre a presente declaración de tapón estrela carácter na liña 16? Entón, o que estou a recibir cando declarar un punteiro? Todo o que eu estou a recibir é un valor de catro bytes chamado de buffer, pero o que está dentro dela no momento? É só un valor de lixo. Porque calquera momento declarar unha variable en C, é só un valor de lixo, e estamos empezando a viaxe sobre esta realidade. Agora, cando digo scanf, vaia a este enderezo e poñer o que o usuario escribe. Se o usuario escribe Ola mundo, así, onde me gustaría poñelas? Buffer é un valor de lixo. 

Entón, iso é como unha especie de frecha que está a apuntar quen sabe onde. Quizais está apuntando ben aquí na miña memoria. E así, cando o usuario tipo en Ola mundo, o programa tenta poñer o Ola mundo secuencia barra invertida 0 nese anaco de memoria. Pero, con alta probabilidade, pero claramente non o 100% de probabilidade, o ordenador vai entón fallar o programa porque este non é memoria que eu debería ser permitido tocar. Así, en breve, este programa é fallo para exactamente ese motivo. Eu fundamentalmente non estou facendo o que? Que medidas teñen omitir, así como nós omitimos co primeiro exemplo de Binky? Si? 

Audiencia: reserva de memoria? 

DAVID Malan: distribución de memoria. Eu realmente non teño asignado calquera memoria para esa secuencia. Así, podemos fixar iso nun par de formas. Un, podemos mantelo simple e, de feito, agora está comezará a ver unha indefinición das liñas entre o que unha matriz é, o que é unha cadea, o que é un Char estrela, o que unha matriz de caracteres é. Aquí está o segundo exemplo envolvendo cordas e aviso todo o que eu fixen en liña 16 é, en vez de dicir tapón que vai ser un char estrela, un punteiro para un bloque de memoria, Vou dar moito proativamente me un buffer para 16 caracteres, e de feito, se está familiarizado co termo de tamponamento, probablemente dende o mundo dos vídeos, onde un buffer de vídeo é, de tamponamento, buffering. Ben, cal é a conexión aquí? Ben, interior de YouTube e dentro players de vídeo xeralmente é unha matriz que é maior que 16. Pode ser unha matriz de tamaño megabyte, quizais 10 megabytes, e para esa matriz fai seu navegador descargar unha morea de bytes, un grupo enteiro de megabytes de vídeo e reprodutor de vídeo, YouTube ou de quen queira que estea, comeza lendo os bytes de matriz que, e en calquera momento ve o palabra buffering, buffering, que significa que o xogador posúe unha fin dese array. A rede é tan lento que non ten recarreguen a matriz con máis bytes e entón está fóra de bits para amosar para o usuario. 

Entón tapón é un termo apt aquí en que é só unha matriz, unha peza de memoria. E iso vai resolve-lo pois parece que que pode tratar matrices como se son enderezos, aínda tapón é só un símbolo, é unha secuencia de caracteres, buffer, que é útil para min, o programador, pode pasar ao redor do seu nome como se fose un punteiro, coma se foron a dirección dun anaco de memoria para 16 caracteres. Entón, iso é para dicir, podo pasar o scanf exactamente esa palabra e agora, se eu fai este programa, facer scanf 2, punto scanf barra 2, e escriba Ola mundo, Intro, que tempo-- 

Hmm, o que pasou? Corda por favor. O que eu fixen de malo? Ola, mundo, buffer. Hola Mundo. Ah, eu sei o que está facendo. Aceptar. Entón está lendo-se ata que o primeiro espazo. Entón, imos enganar por só un momento e dicir que eu só quería escribir algo realmente longa como esta é unha frase longa iso é un, dous, tres, catro, cinco, seis, sete, oito, nove, 10, 11, 12, 13, 14, 15, 16. Aceptar. En realidade, é unha frase longa. Entón, esta frase é máis de 16 caracteres e entón cando prema Intro, o que vai pasar? Ben, neste caso do tapón historia, eu declarara para ser realmente unha matriz con 16 caracteres preparado para ir. Entón, un, dous, tres, catro, cinco, seis, sete, oito, nove, 10, 11, 12, 13, 14, 15, 16. Así, 16 caracteres, e agora, cando ler en algo así como este é un longo sentenza, o que vai pasar é que eu vou ler este é un longo S-E-N-A-C-N-C-E, frase. 

Polo tanto, esta é deliberadamente algo malo que eu continuar a escribir máis aló do límites da miña matriz, máis alá do meu tapón. Eu podería ter sorte e do programa seguirá a funcionar e non me importa, pero dun modo xeral, esta vai realmente bater o meu programa, e é un erro no meu codificar o momento que eu paso máis alá desa matriz, porque Non sei se é necesariamente vai fallar ou se eu estou indo só para ter sorte. Entón, iso é problemático porque en Neste caso, parece funcionar e imos tratar o destino aquí, aínda o IDE parece tolerar un pouco de-- 

Alí imos nós. Finalmente. Entón, eu son o único que pode ver iso. Entón, eu só tiña unha chea de diversión dixitación unha frase real moi longo que seguramente excedido 16 bytes, porque ingresaran nesta longa multi-liña tolo frase, a continuación, teña en conta o que pasou. O programa intentou imprimir lo e, a continuación, ten un fallo de segmento e fallos de segmentación é cando algo como isto ocorre eo sistema operativo di non, non pode tocar esa memoria. Nós imos matar o programa completo. 

Polo tanto, este parece problemático. Eu mellorei o programa polo cal polo menos, ter algunha memoria, pero isto parece limitarse o GetString función para cordas de un tempo finito 16. Entón, se quere apoiar máis frases que 16 caracteres, que fas? Ben, pode aumentar o tamaño desta reserva para 32 ou parecer tipo de short. Por que non imos só facer que 1000, pero empurrar cara atrás. Cal é a resposta intuitivamente de só evitar este problema, facendo meu buffer maior, como 1.000 caracteres? Ao aplicar GetString deste xeito. O que é bo ou malo aquí? Si? Audiencia: Se conectar unha morea de espazo e non usalo, entón non pode redistribuir ese espazo. DAVID Malan: Absolutamente. É un desperdicio na medida en que se non o fai realmente precisa deses 900 bytes e aínda así está pedindo 1.000 en total de calquera xeito, só está consumindo máis memoria o ordenador do usuario do que precisa, e despois de todo, algúns xa atopou na vida que cando está executando moitos programas e eles están comendo moita memoria, isto pode realmente afectar o desempeño e experiencia do usuario no ordenador. Entón, ese é o tipo de solución preguiceiro, con certeza, e, inversamente, non é só un desperdicio, cal é o problema aínda permanece, aínda que fago o meu tapón 1000? Si? 

Audiencia: A cadea de lonxitude é 1.001. DAVID Malan: Exactamente. Se a secuencia de lonxitude é 1001, tes exactamente o mesmo problema, e polo meu argumento, eu o faría só, a continuación, facelo 2000, pero non sabe en avanzar o quão grande debe ser, e aínda, eu teño que compilar meu programa antes de deixar as persoas empregan e descargue lo. Polo tanto, este é o tipo de cousas que os intentos de biblioteca CS50 para axudarnos con e nós só vai mirar nalgúns dos implementación subxacente aquí, pero este é CS50 punto C. Este é o ficheiro que estivo en CS50 IDE todas estas semanas que está a usar. É precompilados e ten foi usalo automaticamente por natureza de ter o trazo L bandeira CS50 con clang, pero se eu rolar para abaixo a través de todos estas funcións, é aquí GetString, e só para lle dar un gústame o que está pasando, imos dar un ollo rápida en a relativa complexidade. Non é un super longa función, pero non o fixemos ten que pensar moito sobre todo como ir sobre a obtención de cordas. 

Entón aquí está o meu tapón e eu parecer Inicialize-o como nulo. Isto, naturalmente, é o mesmo como char estrela, pero eu decidir en execución da biblioteca CS50 que, se nós estamos indo a ser completamente dinámico, Non sei de antemán como grande dun usuarios de cordas van querer obter. Entón eu vou comezar con só unha cadea baleira e eu estou indo a construír o maior memoria como eu teño para se axustar á cadea user e se eu non teño suficiente, eu vou pedir o sistema operativo para máis memoria. Eu estou indo a ir a súa secuencia nun anaco grande de memoria e eu estou indo a liberar ou liberar o insuficientemente gran peza de memoria e nós só estamos indo para facelo de forma iterativa. 

Así, un ollo rápida, aquí é só unha variable coa que eu vou manter o control da capacidade do meu buffer. Cantos bytes eu pode caber? Aquí está unha variable n con que vou continuar o control de cantos bytes están realmente en o tapón ou que o usuario escribiu. Se non viu iso antes, pode especificar que unha variable como un int é non asinado, que como o seu nome indica, significa que é non negativo, e por que Nunca quero incomodar especificando que un int non é só un int, pero é un int non asinado? É un int non negativo. Que o [inaudível] significa? 

Audiencia: É describindo unha cantidade de memoria que pode ser [inaudível]. 

DAVID Malan: Yeah. Entón, se eu digo non asinado, este é, en realidade, dándolle un pouco de memoria extra e parece medio parvo, pero se ter un pouco de memoria adicional, que significa que ten o dobre valores que poden representar, porque pode ser un 0 ou un 1. Entón, por defecto, un int pode ser máis ou menos negativo de 2 millóns de todo o camiño ata positiva 2 millóns. Estas son grandes intervalos, pero aínda é tipo de desperdicio se só se preocupan tamaños, que intuitivamente debe ser non-negativo ou positivo ou 0, ben, entón, por que está perdendo 2 millóns Os valores posibles para números negativos se vostede non vai usalos? Así dicindo non asinado, agora meu int poida estar entre 0 e preto de 4 millóns. 

Entón aquí é só un int C por razóns Non imos entrar só agora como para por iso que é un int no canto dun char, pero aquí é a esencia do que está a suceder , E algúns de vostedes pode ser utilizando, por exemplo, a función fgetc mesmo en PSet catro ou despois desa data, imos velo novo no conxunto de problemas cinco, fgetc é bo porque como o nome tipo de, tipo de arcanely suxire, é unha función que recibe un personaxe e así, o que é fundamentalmente diferente sobre o que estamos facendo en GetString é que non estamos a usar scanf do mesmo xeito. Estamos só rastreando paso a paso sobre todo o que o usuario introduciu en, porque sempre podemos asignar unha char, e para que poidamos sempre con seguridade ollar para un carácter de cada vez, e a maxia comeza a ocorrer aquí. Eu estou indo a rolar para abaixo para medio desta función só para introducir brevemente esta función. Moi como hai un función malloc, hai unha función realloc onde realloc permite recolocar un bloque de memoria e facela máis ou menos. Entón, longa historia curta e con unha onda de man para hoxe, sabe que o que GetString está facendo é que é unha especie Magic de crecemento ou encollendo o tapón como o usuario tipo na súa cadea. 

Polo tanto, se o usuario escribe un corda curta, este código única aloca suficiente memoria para se axustar á cadea. Se o usuario mantén dixitación como eu fixen iso de novo e de novo e de novo, así, se o tapón do inicialmente esta gran eo programa entende, a agarde un minuto, eu estou fóra do espazo, que vai dobrar o tamaño do buffer e, a continuación, o dobre do tamaño do buffer eo código que fai a duplicación, se miramos para el aquí, é só iso intelixente one-Liner. Pode non ter visto esta sintaxe antes, pero se di que é igual a estrela, esta é a mesma cousa que dicindo veces capacidade para 2. El simplemente continúa dobrando a capacidade do tapón e, a continuación, dicindo realloc para dar Se que moito máis memoria. 

Agora, como un aparte, hai son outras funcións aquí que non imos ollar para calquera detalle ademais de mostrar en GetInt, usamos GetString en GetInt. Nós consideramos que non é null, o que, recall, é o valor especial que significa algo foi mal. Estamos con falta de memoria. Mellor comprobar a iso. E nós devolver un valor de sentinela. Pero eu vou retrasar para as observacións canto á por que e, a continuación, usar este primo de scanf chamado sscanf e botan que scanf sscanf, ou corda, permite que dea un ollo á liña que o usuario introduciu no e deixalo analiza-lo e, esencialmente, o que eu son facendo aquí é que eu estou dicindo a sscanf, analizar todo o que o usuario ten escritas e asegurarse de% i, existe un enteiro nel, e non imos entrar hoxe exactamente porque hai tamén un% c aquí, pero que, en poucas palabras permite nós para detectar se o usuario introduciu en algo falso despois do número. Entón a razón que GetInt e GetString dicirlle para repetir, repetir, repetir é por mor de todo que o código que escribimos, é unha especie de ollar para a entrada do usuario en asegurarse de que é totalmente numérico ou é un flotante real valor de punto ou semellante, dependendo do que o valor funcionar está a usar. 

Ufa. Aceptar. Isto foi un bocado pero o punto aquí é que a razón que tivemos as rodas de formación sobre é porque no nivel máis baixo, Hai só tantas cousas que pode dar mal que queriamos para xestionar cautelarmente isto seguramente no primeiras semanas de clase, pero agora con PSet catro e cinco e PSet ademais de vai ver que é máis ata ti, pero tamén é máis capaz de resolver este tipo de problemas Se. Calquera preguntas sobre GetString ou GetInt? Si? 

Audiencia: Por que ía dobrar a capacidade do tapón no canto de só aumentar polo que a cantidade exacta? 

DAVID Malan: Boa pregunta. Por que iríamos duplicar a capacidade do tapón en oposición só para aumenta-la por algún valor constante? Foi unha decisión deseño. Nós só decidimos que xa tende a ser un pouco caro, time-wise preguntar o sistema operativo para a memoria, non o fixemos quere acabar metendo unha situación para grandes cadeas que estabamos pedindo o sistema operativo novo e de novo e de novo e de novo en sucesión rápida para a memoria. Entón, nós só decidiu, un pouco arbitrariamente, pero esperamos razoablemente, que, xa sabe o que imos tentar chegar á fronte de nós mesmos e manter só dobrando o para que nós minimizar a cantidade de veces temos que chamar malloc ou realloc, pero un total de xuízo chamar a ausencia de saber o que os usuarios poden querer escribir. Ambas as formas poden ser discutible. Indiscutibelmente boa. 

Entón imos dar un ollo a un par doutros efectos secundarios de memoria, cousas que poden dar mal e ferramentas que pode usar para capturar estes tipos de erros. Acontece todo de ti, aínda que check50 non lle contou como moito, teñen escrito de buggy xa que un código de semana, mesmo se todas as probas son check50 pasou, e aínda que vostede eo seu TF son super seguros de que seu código funciona como previsto. O seu código foi buggy ou fallo na que todos vós, en usar a biblioteca CS50, foron fuga de memoria. Foi pedir ao sistema operativo para memoria na maioría dos programas escribiu, pero nunca realmente deu de volta. Chamou GetString e GetInt e GetFloat, pero con GetString, ten nunca chamou unGetString ou de- Volver corda ou similar, pero nós vimos GetString que fai reservar memoria por medio de malloc ou este realloc función, que non é máis que moi semellante en espírito, e aínda, fomos pedindo o sistema operativo para memoria e memoria de novo e de novo pero nunca dándolle de volta. 

Agora, como un aparte, verifícase que cando un programa remata, toda a memoria automaticamente liberado. Polo tanto, non foi un gran negocio. Non vai romper o IDE ou retardar as cousas, Pero cando os programas fan xeralmente baleirar memoria e eles están executando por un longo tempo. Se xa viu a pouco estúpido bola de praia en Mac OS ou a ampulheta en Windows, onde é unha especie de abrandar ou pensar ou pensar ou só realmente comeza para retardar a un rastreando, moi posiblemente podería ser o resultado dun escape de memoria. Os programadores que escribiron o software que está a usar pedir ao sistema operativo para a memoria cada poucos minutos, a cada hora. Pero se está executando o software, aínda que sexa minimizado no seu ordenador por horas ou días a fío, pode estar pedindo máis e máis memoria e nunca realmente usalo e para que o seu código pode ser, ou programas poden ser baleirado de memoria, e se comezar a baleirar memoria, hai menos memoria para outros programas, eo efecto é a retardar todo para abaixo. 

Agora, este é de lonxe un dos os programas máis atroces terá oportunidades para realizar en CS50, na medida como a súa produción é aínda máis esotérica que clang de ou facer ou o todo do comando programas de liña que xa executados antes, pero por sorte, incorporado na súa saída é algúns consellos útiles que super- ha ser útil tanto para PSet catro ou seguramente PConfigurar cinco. Entón valgrind é unha ferramenta que se pode usar para buscar para derrames de memoria no seu programa. É relativamente simple de executar. Corre valgrind e, a continuación, mesmo pero é un pouco detallado, trazo verificación de baleirado trazo é igual a plena e logo dot corte eo nome do seu programa. Entón valgrind, entón, facer o seu programa e, ao final do seu programa execución antes de que sae e dálle outro pedido, que vai analizar o seu programa mentres está a executarse e dicirlle que baleirar calquera memoria e mellor aínda, se tocar memoria que non pertence a vostede? Non pode incorporarse todo, pero é moi bo en incorporarse máis cousas. 

Entón aquí está un exemplo do meu ter prazo este programa, tendo run valgrind, nun programa chamado memoria, e eu vou para destacar as liñas que son en definitiva, de interese para nós. Polo tanto, hai aínda máis distraccións que teña eliminado do slide. Pero imos ver o que este programa é capaz de nos dicir. É capaz de nos dicir cousas como gravación válido de tamaño 4. Noutras palabras, se tocar en memoria, especialmente 4 bytes de memoria que non debe ter, valgrind te podo dicir iso. Write válido de tamaño 4. Vostede tocou catro bytes que non debe ter. Onde é que fai iso? Esta é a beleza. Dot liña memoria c 21 é onde asneira e é por iso que é útil. Moi parecido ao GDB, pode axudar sinala-lo ao erro real. 

Agora, este é un pouco máis detallado, se non confuso. 40 bytes en bloques de 1 son, en definitiva, perdido no rexistro de perda 1 de 1. Que significa iso? Ben, iso significa só que pediu 40 bytes e nunca deulle de volta. Vostede chamada malloc ou chamada GetString eo sistema operativo deulle 40 bytes, pero nunca liberadas ou que a memoria liberada, e para ser xusto, nunca amosar como para darlle a volta a memoria. Acontece aí é un super- función simple chamado libre. Recibe un argumento, a cousa quere liberar ou dar para atrás, 40 bytes, pero, ao parecer, neste programa foron perdidos na liña 20 de memoria punto c. 

Entón imos ver este programa. É super inútil. Isto só demostra este erro particular. Entón, imos dar un ollo. Aquí é principais e principais, observación, chamadas unha función chamada F e logo retorna. Entón, non todo o que interesante. O que fai f facer? Repare que eu non me incomoda con un prototipo. Eu quería manter o código o mínimo posible. Entón eu coloque f enriba principal e iso é bo, certamente, para programas curtos como este. Entón f non retorna nada e fai non levar nada, pero o fai. Declara, así como no exemplo Binky, un punteiro chamado x que está pasando para almacenar o enderezo dun int. Entón, iso é o lado esquerdo. En inglés, o que é o lado dereito facendo? Anyone? ¿Que é esta facendo por nós? Si? 

Audiencia: [inaudível] veces o tamaño dun int que é 10 veces que [inaudível] DAVID Malan: Boa e déixeme resumir. Entón reservar espacio suficiente para 10 enteiros ou 10, o que é do tamaño dun int, é catro bytes, polo que 10 veces 4 é 40, de xeito que o lado dereito que eu teño resaltado é darme 40 bytes e almacenar o enderezo do primeiro byte en x. E agora, por fin, e é aquí que este programa é buggy, o que é mal con liña 21 en base a que a lóxica? O que hai de malo con liña 21? Si? Audiencia: Non pode índice en x [inaudível]. DAVID Malan: Yeah. Non debería índice en x como esta. Entón sintaticamente, iso é OK. O que é bo é, moi parecido contigo pode tratar o nome dunha matriz como se fose un punteiro, semellante pode tratar un punteiro como se fose unha matriz, e para que eu poida sintaticamente x soporte dicir algo, x soporte i, pero a 10 é problemática. Por que? 

Audiencia: ¿Por que non é no interior. 

DAVID Malan: non dentro dese anaco de memoria. Cal é o maior valor que eu debería estar poñendo neses corchetes? 9, de 0 a 9. Debido a indexación cero. Entón, de 0 a 9 sería óptimo. Soporte 10 non é boa e pero, lembre-se, porén, cada vez Paréceme tentar facer CS50 IDE accidente, escribindo valores falsos, non sempre cooperar, e, de feito, moitas veces ter sorte de ser o sistema operativo non entender que nunca tan pouco pasar algún anaco de memoria, porque quedou dentro tecnicamente seu segmento, pero máis sobre iso nunha clase de sistemas operativos, e así por algo así podería facilmente pasar desapercibido. O seu programa non vai fallar consistente, pero quizais xa en moito tempo. 

E entón imos tentar valgrind sobre iso, e é aquí onde imos estar resaltado por saída momentaneamente. Entón, faga verificación de baleirado de memoria valgrind é igual a memoria barra punto cheo. E aquí está o porqué eu prometer poderían sobrecargar. Aquí está o que valgrind, aquí está o que programador, algúns anos- decidiu que sería unha boa idea para a saída a aparencia. Entón, imos dar sentido a iso. Entón, todo o camiño na da esquerda banda sen unha boa razón é o ID do proceso do programa nós só executado, o identificador único para o programa que nós só foi. Nós excluído que desde o slide, pero non é algunha información útil aquí. 

Imos rodar ata o cumio. Aquí é onde comezamos. Polo tanto, non é tanto así de saída. Aquí está o que write válido 4 de tamaño na liña 21. Ben, o que era liña 21? Liña 21 foi exactamente este e ten sentido que eu estou no validamente escrito 4 bytes, porque eu son intentando poñer este número enteiro, o que podería ser calquera cousa, iso só pasa de ser cero, pero eu estou tentando para poñelas nun lugar que non pertence a min. Ademais, aquí abaixo, 40 bytes nun bloques son definitivamente perdidos en ficha 1. Porque cando eu chamar malloc aquí, eu nunca realmente liberar a memoria. 

Entón, como podemos solucionar isto? Deixe-me ir adiante e ser un pouco máis seguro e facer 9 alí e me deixe aquí libre x. Esta é a nova función para hoxe. Se eu agora realizar novamente facer corte de punto de memoria, imos realizar valgrind nel de novo, maximizar miña fiestra e prema Intro. Agora, é bo. Eles enterran a boa nova en todo este proceso de saída. Todos os bloques heap eran libres. Imos volver ao que o heap é, pero non hai fugas son posibles. Polo tanto, este é só un ferramenta para o seu kit de ferramentas co cal pode comezar a agora atopar erros como ese. 

Pero imos ver o que máis pode dar mal aquí. Transición Imos agora realmente resolver un problema. Como un aparte, se iso vai aliviar un pouco de confusión ou tensión, isto agora é divertido. Si. Iso é moi bo. Porque punteiros son enderezos e enderezos son, en xeral, por convención escrito con hexadecimal. Ha, ha, iso é divertido agora. En calquera caso, así que imos agora realmente resolver un problema. Isto foi super, super baixo-nivel, ata agora, e podemos realmente facer útil cousas con estes detalles de baixo nivel. 

Entón, nós introducimos algunhas semanas atrás, a noción dunha matriz. Unha matriz foi bo porque é difícil de limpar o noso código porque se quixésemos escribir programa con varios alumnos ou varios nomes e casas e dormitorios e facultades e todo iso, poderiamos almacenar todo máis limpa dentro dunha matriz. Pero propoñer unha desvantaxe dunha matriz, ata agora. Mesmo se non sufrín it yourself nun programa, só instintivamente, o que é algo malo sobre unha matriz, quizais? Escoito uns murmurios. Audiencia: É difícil para cambiar o tamaño. DAVID Malan: É difícil para cambiar o tamaño. Non pode cambiar o tamaño dunha matriz, de feito, por si só en C. Podes reservar outro array, mover todo, dende o antigo ao novo, e agora ter un espazo extra, pero non é como un linguaxe como Java ou Python ou calquera número de outros linguas que algúns de vós pode estar familiarizado onde pode simplemente seguir engadindo cousas saciedade despois dunha matriz. Cando ten unha serie de tamaño 6, que é o seu tamaño, e tan parecido a idea anterior tendo un tapón dun determinado tamaño, tes que adiviñar fóra da porta cal é o tamaño que queres que sexa? Se adiviñar moi grande, está perdendo espazo. Se adiviñar moi pequeno, Non se pode gardar os datos, polo menos, sen moito traballo. 

Entón, hoxe, grazas aos punteiros, podemos comezar a coser o noso propio costume estruturas de datos, e en feito, aquí é algo que parece un pouco máis enigmática, a primeira vista, pero iso é o que nós imos chamar un conectado lista, eo seu tipo de nome resume lo. É unha lista de números, ou en Neste caso, unha lista de números, pero pode ser unha lista de todo, pero ela ligados entre si a través de frechas, e só dar un palpite con cal técnica imos ser capaces para unir, tipo de como pipoca cun fío, unha ligada listas rectángulos aquí? Os seus números? Qué é o recurso de linguaxe subxacente? 

Audiencia: Un punteiro. 

DAVID Malan: Un punteiro. Entón cada un destes frechas representa aquí un punteiro ou só unha dirección. Polo tanto, noutras palabras, se eu queira para almacenar unha lista de números, Non podo simplemente almacena-lo se eu queira a capacidade para aumentar e diminuír miña estrutura de datos nunha matriz. Entón eu preciso ter un pouco máis sofisticación, de ter en conta que esta tipo de imaxe suxire que, se só ten pequenos temas conectar todo en conxunto, probablemente non é tan difícil de facer espazo entre dous destes rectángulos ou dous destes nós, como imos comezar chamando-os, coloque un novo nodo, e despois con unha nova liña, só abandonar os tres nós xuntos, a primeira, a última, e por un que acaba de introducir no medio. 

E, de feito unha lista ligada, ao contrario dunha matriz, é dinámico. Ela pode crecer e pode encoller e non fai Ten que saber ou importarlle con antelación como cantidade de datos que vai estar almacenando, pero resulta que temos que ser un pouco coidadoso sobre como aplicar iso. Entón, primeiro imos considerar como imos implementar un destes pequenos rectángulos. É doado de aplicar un int. Acaba de dicir int n e, a continuación, obtén 4 bytes para un int, pero como fago para obter un int, chamalo de n, e, a continuación, un punteiro, imos chamalo axiña. Poderiamos chamar estas cousas algo que queremos pero eu teño unha estrutura de datos personalizado. Si? 

Audiencia: Ampersand [inaudível]. 

DAVID Malan: Entón e comercial, imos utilizar para obter o enderezo dun nodo potencialmente. Pero precisamos doutro O recurso de C en orde para me dar a capacidade de crear este rectángulo costume, este costume variable se, na memoria. Audiencia: Unha struct. DAVID Malan: Unha struct. Teña en conta que a última semana, introducimos struct, esta palabra chave relativamente simple que nos permite facer cousas como esta. C non veu con un conxunto de datos estrutura chamada estudante. Ven con int e boia e carbón animal e tal, pero non vén co alumno, pero podemos crear un tipo de datos do alumno, unha estrutura estudante, con esta sintaxe aquí. E vai ver iso de novo e de novo. Non te preocupes Recordar as palabras clave, pero a palabra clave que é importante é só o feito de que nós dixemos struct e, a continuación, nós o chamamos estudante e no interior do alumno era un nome e unha casa ou un dormitorio ou similares. 

E agora, hoxe, imos propoñer iso. Eu engade algunhas palabras, pero se eu queira para aplicar este rectángulo que é ten tanto un int e un punteiro, vostede sabe, eu son vai declarar unha estrutura chamada nó. Eu tamén son, dentro del, vai dicir que un nó, rectángulo, ten un int e imos chamalo e n ten un punteiro próximo. E iso é un pouco detallado, pero se pensar sobre iso, as frechas que estaban na imaxe un momento atrás son de que tipo de datos? Cando cada un destes frechas apuntando está a que tipo de estrutura de datos? Non é só que apunta a un int per se. Está apuntando para o cousa toda rectangular e que cousa rectangular, nós dixemos, chámase nó. E entón nós medio que ten que recursivamente definir esta tales que un nó, digamos, contén un int chamado n e un punteiro chamado seguinte e no tipo de estrutura de datos para o que que os puntos de punteiro é, ao parecer, será nó struct. 

Polo tanto, este é irritante verboso e só para ser pedante, a razón pola que nós non podemos só dicir isto, que, a verdade, parece moito máis lexible, é porque recorda que C ler as cousas de arriba abaixo, de esquerda a dereita. Non é ata chegar a punto e coma que a palabra chave nó realmente existe. Polo tanto, se queremos ter ese tipo de referencia cíclico dentro dos datos estrutura, temos que facelo, onde dicimos nó struct na parte superior, que ofrécenos unha máis forma de describir este cousa, entón dentro dicimos nó struct, e despois na última liña podemos dicir, todo ben, C, a propósito, pode conectar a todo este maldito cousa que un nó e deixar usando a palabra chave struct completamente. Polo tanto, esta é só unha especie de sintáctica truco que finalmente nos permite crear algo que se parece exactamente con iso. 

Entón, se nós agora podemos asumir aplicar esa cousa en C, como é que nós, en realidade, iniciar atravesando este? Ben, en realidade, todo o que temos que facer é iteración de esquerda a dereita e só tipo de introducir os nós ou eliminar nós ou buscar cousas onde queremos, pero para facelo, imos adiante e facer as cousas un pouco máis real, porque iso foi super-baixo nivel ata agora. Será que alguén literalmente quere ser o primeiro? Aceptar. Imos cara arriba. Cal é o teu nome? 

DAVID: David. DAVID Malan: David. Encantado de coñecerte. Eu tamén. Todo ben. E necesitamos un número 9. Non é tan bo como o primeiro, quizais. OK, número 9. Un número 17, por favor. Déixeme volver un pouco máis lonxe. Number 22, por favor, e e canto máis atrás se podo ver ningunha man con toda a luz ou non. Alguén está a ser ofreceu alí. Quere chegar? Seu antebrazo é forzado a subir. OK, 17. 22. 26 está a benvida para abaixo. Será que ninguén gusta de forcefully-- Imos cara arriba. Un voluntario real. 

Entón, moi rapidamente, se vostedes poderían organizar Se só como os nós na pantalla. Grazas. E vai ser 26. Todas as introducións certas e rápidas. Entón, eu estou David e tamén? DAVID: David. DAVID Malan: E é? Jake: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID Malan: Taylor. Excelente. Entón, eses son os nosos voluntarios para hoxe e ir adiante e cambiar un pouco desa forma, e só ir adiante e manter sostendo o seu número como é ou o seu primeiro sinal e coa man esquerda, dalle só aplicar esas frechas, só de xeito que a man esquerda é, literalmente, apuntando para o que ten que apuntar na, e dar-se un espazo para que vemos visualmente os brazos, en realidade, apuntando, e pode só apuntar tipo de cara ao chan está ben. 

Polo tanto, temos aquí unha lista ligada dun, dous, tres, catro, cinco nódulos inicialmente, e entender que temos este especial punteiro no inicio quen é clave, xa que hai que manter o control de toda a lista de lonxitude de algunha maneira. Eses faces, aínda que sexan deixadas á dereita, volve atrás na memoria, de feito, poden estar en calquera lugar na memoria do ordenador. Entón, estes faces poderían ser en pé en calquera lugar na fase e iso é bo, sempre que son de feito, apuntando para o outro, pero para manter as cousas limpo e simple, nós imos só deseña-los esquerda a dereita este, pero pode haber lagoas masivas entre eses nós. 

Agora, se eu quero realmente introducir algúns novo valor, imos adiante e facelo. Temos unha oportunidade agora para escoller un nó. Digamos que imos comezar con mallocing 55. Será que alguén podería me importa ser malloc? OK, imos cara arriba. Cal é o teu nome? RAINBOW: Arco da vella. DAVID Malan: Arco da vella? Todo ben. Malloc do arco da vella. Imos cara arriba. Polo tanto, agora temos que preguntarnos algorithmically onde podemos poñer 55. Entón, todos sabemos, obviamente, onde pode que pertence, se nós estamos tentando para manter este clasificado e se vós poderían tomar unha un paso atrás para que non caia o escenario, que sería óptimo. Entón, en realidade, Arco-Iris, comezar de novo aquí comigo, porque, como o ordenador pode agora só ve unha variable de cada vez. Así, se este é o primeiro no. Teña en conta que non é un nodo, el é só un punteiro, e é por iso que está deseñado para ser só o tamaño dun punteiro, non un deses rectángulos completos. Entón, nós estamos indo para comprobar en cada iteración é de 55 a menos de 9? Non. É de 55 a menos de 17? Non. Menos de 22? Menos de 26? Menos de 34? E agora, obviamente, Iris pertence ao final. Entón, para ser claro, e que era o seu nome, Taylor? 

TAYLOR: Taylor. DAVID Malan: Entón entre Taylor man esquerda e as mans do arco da vella aquí, cuxa man ten que apuntar cara a que en Para inserir 55 nesta lista? O que necesitamos facer? Si? 

Audiencia: a man de Taylor Debe apuntar esquerda. 

DAVID Malan: Exactamente. Entón, a inserción dun nodo ao final da lista é moi sinxelo, porque Taylor só ten a punto, en vez de para o chan ou imos chamalo nulo, nulo é unha especie de ausencia dun punteiro ou unha especial punteiro cero, está vai apuntar coa súa esquerda man no arco da vella e, a continuación, Arco iris, Onde debe a súa esquerda man, probablemente, apuntar? Down. Non é bo se a súa man é unha especie de apuntar fóra aquí ou calquera tipo de que xeito. Isto sería considerado un valor de lixo, pero se apunta algún valor coñecido, imos chamalo cero ou nulo, que é OK porque temos un termo neste e sabemos que a lista xa está completa. 

Entón, o que é outra caso relativamente simple? Poderiamos malloc 5? Imos cara arriba. Cal é o teu nome? TIFFANY: Tiffany. DAVID Malan: me desculpe? TIFFANY: Tiffany. DAVID Malan: Tiffany. Todo ben. Tiffany foi malloced co valor 5. Imos cara arriba. Este é relativamente fácil de máis, pero imos considerar a orde das operacións agora. Foi moi fácil con Taylor ao final. Número 5 é, por suposto, menos que 9, e por iso temos David, dispoñemos de Tiffany, e cal era o seu nome? 

Jake: Jake. 

DAVID Malan: Jake. Tiffany, Jake, e David. Cuxa man debe ser actualizado primeiro? O que quere facer aquí? Hai un par de formas posíbeis, mais hai tamén unha ou máis formas erradas. 

Audiencia: Comece máis á esquerda. 

DAVID Malan: Comece o máis á esquerda. Quen é o máis á esquerda aquí, entón? Audiencia: First. 

DAVID Malan: Aceptar. Entón comeza co primeiro e onde quere actualizar mans de David para ser? Audiencia: Cara a 5. DAVID Malan: Aceptar. Entón David, punto en cinco ou Tiffany aquí, e agora? 

Audiencia: Tiffany apunta para o 9? DAVID Malan: Perfecto, excepto de Binky cabeza só unha especie de caeu, non? Porque o que hai de malo con esta imaxe, literalmente? Audiencia: Nada está apuntando. DAVID Malan: Nada é apuntando a Jake agora. Temos literalmente orfo 9 e 17, e temos literalmente filtrou todo isto de memoria, porque, actualizar a man de David en primeiro lugar, que é ben, na medida en que é correctamente apuntando para Tiffany agora, pero se ninguén o clarividencia de apuntar Jake, entón perdemos o totalidade desa lista. Entón, imos desfacer. Así, foi bo para tropezar pero imos corrixir agora. O que temos que facer primeiro no seu canto? Si? 

Audiencia: Tiffany debería apuntar o 9? DAVID Malan: Non podo chegar tan preto de ti. Quen debería apuntar o 9? 

Audiencia: Tiffany. 

DAVID Malan: Todo ben. Entón Tiffany que primeiro punto no 9. Entón Tiffany que tomar nun valor idéntico David, que parece redundante, por un momento, pero iso é bo porque agora, segundo paso, podemos actualizar a man de David para ligar a Tiffany, e entón se Nós medio que limpar as cousas coma se este é o tipo de primavera-like, agora que é unha inserción correcta. Así excelente. Polo tanto, agora estamos case alí. Imos introducir un final, valor como o valor 20. Se puidésemos malloc un voluntario final? Imos cara arriba. Entón, este é un pouco máis complicado. Pero, realmente, o código estamos escribir, aínda que verbalmente, é como ter unha chea as condicións de agora, non? Tivemos unha condición comprobando se pertence ao final, quizais o principio. Necesitamos a algún tipo de bucle para atopar o punto no medio. Entón imos facelo co que é o seu nome? 

ERIC: Eric. 

DAVID Malan: Eric? Eric. Encantado de coñecerte. Polo tanto, temos 20. Menos de cinco? Non. Menos de nove? Non. Menos de 17? Non. Aceptar. Pertence aquí e seus nomes son de novo? SUE: Sue. DAVID Malan: Sue. ALEX: Alex. DAVID Malan: Sue, Alex, e? ERIC: Eric. DAVID Malan: Eric. Cuxas mans necesitas estar actualizado en primeiro lugar? 

Audiencia: Eric. Aceptar. Entón Eric debe apuntar cara a onde? Aos 22 anos. Bo. E agora o que é o próximo? Súe pode, entón, ligar a Eric e agora, se vostedes só facer un espazo, o que é bo visualmente, agora que fixemos a inserción. Entón, imos agora considerar unha pregunta, pero moitas grazas para os nosos voluntarios. Moi ben feito. Pode manter estes, se lle gusta. E nós temos un fermoso agasallo de despedida se vostede cada gustaría ter unha bola de estrés. Déixeme só pasar isto para abaixo. Entón, cal é o takeaway deste? Este parece ser incrible na medida en que temos agora Presentar unha alternativa para unha matriz que non é tan confinado para unha matriz de algún tamaño fixo. Poden crecer de forma dinámica. 

Pero moito como vimos en semanas pasado, nunca conseguir nada de balde, como seguramente hai un trade-off aquí. Así, cun Upside dun conectado lista, é ese dinamismo? Esta capacidade de crecer e, a verdade, que poderiamos ter feito de exclusión e poderiamos encoller corresponda. Cara a un prezo que estamos pagando? Dúas veces máis espazo, en primeiro lugar. Se ollar para a foto, non máis Eu son almacenar unha lista de enteiros. Estou almacenando unha lista de enteiros máis punteiros. Entón, eu estou dobrando a cantidade de espazo. Agora, quizais iso non é tan un gran negocio 4 bytes, 8 bytes, pero certamente podería engadir Se a grandes conxuntos de datos. ¿Que é outra desvantaxe? Si? 

Audiencia: Temos que atravesalo-los un por un. DAVID Malan: Yeah. Temos que atravesa-los un por un. Vostede sabe o que, que deron este super recurso conveniente de corchete notación, máis propiamente coñecido como acceso aleatorio, onde podemos simplemente saltar a un elemento individual pero agora eu tiña meus voluntarios aquí, se eu quería atopar o número 22, eu non podo só ir para soporte algo algo. Teño que ollar sobre a lista, moi como os nosos exemplos de investigación de forma lineal, para atopar o número 22. Entón, nós parecen pagado un prezo alí. Pero a xente pode, con todo, resolver outros problemas. 

De feito, deixe-me presentar só un par de elementos visuais. Entón, se foi para abaixo para Mather do Comedor recentemente, ten que se lembrar que a súa pilas de bandexas coma este, nós emprestamos estes desde Annenberg antes da clase. Polo tanto, esta pila de bandexas, porén, en realidade, é representativa dunha estrutura de datos informática. Existe unha estrutura de datos en ciencia da computación coñecida como unha pila que moi ben préstase a exactamente ese visual. Por iso, cada unha destas bandexas non é un bandexa, pero como un número e eu quería para almacenar números, eu podería poñer un aquí en baixo, e eu podería poñer outro aquí en baixo, e continuar empilhado números enriba do outro, e que está potencialmente útil sobre esta é que o que é a implicación desta estrutura de datos? Que número podo retirar primeiro o máis cómodo? O máis recentemente, un posto alí. 

Entón é iso que nós chamariamos en ciencia da computación unha estrutura de datos LIFO. Último a entrar, primeiro en saír. E veremos pronto por que que pode ser útil, pero, polo momento, basta considerar o inmoble. E é unha especie de idiota se pensas sobre como o salón-comedor fai. Cada vez que bandexas limpas e poñer os máis frescos na parte superior, podería ter unha limpo anteriormente pero, finalmente, moi sucio e empoeirado bandexa na parte inferior se nunca realmente chegar ao fondo da referida pila, porque só manter poñendo o novo e os limpos enriba dela. O mesmo pode ocorrer nun supermercado tamén. Se tes un caso de exhibición de leite e cada vez CVS ou quen recibe máis leite, só empurrar os leites xa ten a parte de atrás e poñer os novos na fronte, terá algúns bastante desagradable leite ao final da estrutura de datos, porque sempre no fondo ou equivalentemente sempre na parte de atrás. 

Pero hai outra forma de pensar sobre aliñados datos e por exemplo, isto. Se é unha desas persoas que lle gusta a liña de fóra de tendas de Apple cando un novo produto vén fóra, probablemente está Non usar unha pila de datos estrutura porque alienaria todos os outros que se facendo cola para mercar algún xoguete novo. Pola contra, probablemente está a usar que tipo de estrutura de datos ou que tipo de sistema no mundo real? Esperemos que sexa unha liña, ou máis ou que máis británico-like, unha cola. E verifícase unha cola é tamén un estrutura de datos en ciencia da computación, pero unha fila ten unha moi propiedade diferente. Non é LIFO. Último a entrar, primeiro en saír. Deus me libre. É, en vez FIFO. Primeiro en entrar, primeiro en saír. E iso é bo de xustiza amor ' seguramente cando está aliñados super inicio da mañá. Se chegar alí primeiro, quere saír primeiro tamén. 

E así todos estes datos estruturas, colas e pilas e acios de outros, acaba por ti pode pensar niso como só unha matriz. Esta é unha matriz, quizais un tamaño fixo 4, pero tiña ser unha especie de bo se puidésemos simplemente amontoar bandexas case infinitamente alto se teñen que moitas bandexas ou números. Entón, talvez queremos usar unha lista ligada aquí, pero o trade-off será potencialmente que necesitamos máis memoria, leva un pouco máis de tempo, pero nós non limitar a altura da pila, así como escaparate de Mather pode limitar o tamaño da pila, e así que estas son decisións de proxecto ou opcións dispoñibles para nós en última instancia. Así, con estes datos estruturas, comezan vendo novos límites superiores potencialmente sobre o que anteriormente foi super rápido e onde imos deixar fóra hoxe e onde imos esperar a chegar a é o mércores, nós imos comezar a ollar para un conxunto de datos estrutura que nos permite buscar a través de datos en rexistro tempo final de novo. E vimos que, lembre, a semana de cero e un con busca binaria ou dividir e conquistar. Vén de volta e mellor aínda, o Santo Graal para este mércores será a de chegar co estrutura de datos que corre verdadeiramente ou en teoría constante de tempo, a través de que non importa cantas millóns ou billóns de cousas temos na estrutura de datos, será levarnos tempo constante, quizais un paso ou dous pasos ou 10 pasos, pero os números de pasos constantes para buscar esa estrutura de datos. Que de feito será o Santo Graal pero máis sobre iso o mércores. See ya entón. 

[Música tocando]