[Powered by Google Translate] [Semana 6] [David J. Malan] [Harvard University] [Esta é CS50.] [CS50.TV] 

Este é CS50, e este é o inicio da semana 6, así un par de novas ferramentas están dispoñibles para vostede aproveitar, o primeiro dos cales é chamado CS50 estilo. As probabilidades son, se vostede é como eu ou calquera dos compañeiros de ensino, probablemente xa viu un programa cuxo estilo parece un pouco algo como isto. Quizais comezar a cortar algúns cantos, tarde de noite, ou vai tratar con isto máis tarde, e entón un TF ou CA vén máis durante o expediente. Entón é difícil para nós ler. Ben, este código é sintaticamente correcta, e ha compilar e vai realmente funcionar. Pero definitivamente non é un 5 para o estilo. 

Pero agora, se imos a este directorio aquí- e entender que eu teño conditions2.c- e eu corro este novo mando, style50 nesta conditions2.c arquivo, intro entender que me informou de que foi estilizado. Gedit entendeu que o ficheiro foi modificado no disco, e se eu premer en recargar, todos os seus problemas están agora automatizado. [Aplausos] Iso é unha das cousas que fixemos este fin de semana. Entender que é imperfecto porque hai algún código que simplemente non será capaz de estilizar perfectamente, pero que esta é agora unha ferramenta que pode aproveitar de só para aparcar algunhas das claves máis errantly colocado cacheados e afíns. 

Pero o máis interesante é agora CS50 Check. Con CS50 Check, realmente pode realizar as probas de corrección mesmos no seu propio código que os compañeiros de ensino son capaces de. Este é unha utilidade de liña de comandos que vén agora o aparello así que fai unha update50 por pset catro especificacións, e usalo esencialmente coma este. Corre o check50 mando. Entón pasa un argumento de liña de comandos, ou, máis xeralmente coñecido como un interruptor ou unha bandeira. Xeralmente, as cousas que teñen guións son chamados un interruptor a un programa de liña de comandos, así c especifica as comprobacións que quere executar. 

As probas que quere executar son identificados individualmente por esa secuencia, 2012/pset4/resize. Noutras palabras, iso é só unha secuencia arbitraria, senón única que usan para identificar probas 4 pset de corrección. E entón especificar unha lista separada por espazo de arquivos que quere cargar Comproba a CS50 para a análise. Por exemplo, se eu ir para a miña solución aquí para resize.c- deixe-me abrir un maior terminal de ventá e eu ir adiante e executar digamos check50-c 2012/pset4/resize, e entón eu ir adiante e especificar os nomes dos ficheiros, resize.c, e prema a tecla Enter, el comprime, el leva, el verifica, e eu só fallou unha morea de probas. O de vermello na esquina superior esquerda di que resize.c e BMP existe. Ese foi o exame. Esa foi a pregunta que nós fixemos. E é infeliz porque a resposta era falsa. O texto en branco debaixo di esperar bmp.h de existir, e iso é simplemente culpa miña. Eu esquezo de envialo, entón eu teño subir dous arquivos, resize.c e bmp.h. Pero agora observar todos os outros probas son en amarelo porque non correr, e así o rostro sorrinte é vertical, porque non é nin feliz nin triste, pero temos que resolver este problema en vermello antes de esas outras comprobacións será executado. 

Deixe-me corrixir isto. Deixe-me afastar e executar de novo esa, esta vez con bmp.h tamén na liña de comandos, Intro, e agora, se todo funcionar ben, que vai comprobar e voltar un resultado-Manteña a respiración- todo verde, o que significa que eu estou indo moi ben en pset 4 ata agora. Podes ver e deducir do texto descritivo aquí exactamente que é o que probamos. Probar primeiro é que os arquivos existen? A continuación, probar fai compilación resize.c? Entón nós probamos non é redimensionar unha BMP 1x1 pixel cando n, o factor de cambio de tamaño, é 1. Agora, se non ten idea do que n é, vai unha vez que mergullo pset 4, pero que simplemente é unha comprobación de sanidade para asegurarse de que non é o redimensionamento unha imaxe en todos, o factor de cambio de tamaño é 1. Se, polo contrario, el redimensiona un pixel 1x1 para un 1x1 pixel BMP para 2x2 correctamente cando n é 2, entón de forma semellante, formas mina de conformidade. 

En suma, este é significativo, un, tome a travesía dos dedos fóra da ecuación dereita antes de enviar o seu pset. Vostede saberá exactamente o que o seu TF logo saberá cando vai sobre o envío de algúns deses conxuntos de problemas, e tamén a motivación pedagóxica é realmente poñer a oportunidade na fronte de ti para que, cando sabe a priori que non hai erros no seu código e probas que non están sendo pasados, pode pór máis eficaz do tempo na fronte para resolver estes problemas en vez de perder puntos, obter feedback do seu TF, e despois ir, "Ahh," como eu debería ter percibido iso. Agora, polo menos, hai unha ferramenta para axudar a atopar isto. El non vai apuntar onde é o problema, pero el vai dicir o que é un síntoma da mesma. 

Agora realizar as probas non son necesariamente exhaustiva. Só porque ten unha pantalla chea de verde Smiley Faces non significa que o seu código é perfecto, pero iso non significa que pasou algunhas probas prescritos pola especificación. Ás veces a xente non vai liberar cheques. Por exemplo, whodunit, un dos aspectos da pset 4, e tipo de decepcionante se nós lle damos a resposta para o que é, e hai unha serie de formas para revelar quen é a persoa que o ruído vermello. A especificación será sempre especificar no futuro para pset en diante 5 o que verifica existir para ti. Vostede vai entender que hai esa URL en branco no fondo. Polo momento, esta é só a saída de diagnóstico. Se visitar a URL, vai ter unha morea de tolos, mensaxes enigmáticas que está invitado a ollar a través, pero é sobre todo para o persoal para que poidamos diagnosticar e depurar erros en check50 si. 

Sen delongas, imos seguir adiante de onde paramos. CS50 biblioteca tomamos para concedida por algunhas semanas, pero, a continuación, a semana pasada, comezamos a descascada cara atrás unha das capas do mesmo. Comezamos poñendo de lado cadea en favor do que en vez diso? [Os alumnos] Char. * Char, que foi un char * todo este tempo, pero agora non temos que finxir que é un tipo cadea de datos real. En vez diso, foi sinónimo de sorte para char *, e unha cadea é unha secuencia de caracteres, Entón, por que será que ten sentido para representar cadeas como char * s? O que fai un char * representan no contexto dese concepto dunha cadea? Si >> [Estudante] O primeiro carácter. Bo, o primeiro carácter, pero non é así o primeiro carácter. É unha [Os alumnos] Enderezo. Bo, o enderezo do primeiro carácter. Todo o que é necesario para representar unha cadea na memoria dun ordenador é só o enderezo único do byte primeiro. Non ten sequera saber canto tempo é pois como pode descubrir iso dinamicamente? [Estudante] lonxitude cadea. Pode chamar lonxitude da corda, excelente, pero como funciona a lonxitude da corda? O que fai? Si [Estudante] Continúe indo ata chegar o carácter nulo. Si, exactamente, el só interactúa con un loop for, while, calquera que sexa a partir de * ata o final, e que o final está representada por \ 0, o personaxe chamado nulo, nulo, non debe ser confundida coa nulo, o que é un punteiro, que entrará en conversa de novo hoxe. 

Nós descascada unha capa de GetInt, e despois demos un ollo no GetString, e lembrar que estas dúas funcións, ou realmente, GetString, estaba usando unha determinada función para realmente analizar, é dicir, ler ou analizar, a entrada do usuario. E o que foi que nova función? Scanf ou sscanf. El realmente ven en algúns sabores diferentes. Hai scanf, hai sscanf, hai fscanf. De momento, porén, imos centrar o máis facilmente ilustrado, e deixe-me ir adiante e abrir o dispositivo un arquivo como este, scanf1.c. Este é un programa super sinxelo, pero que fai algo que nunca fixemos sen a axuda da biblioteca CS50. Este recibe un int dun usuario. Como funciona isto? Ben, na liña 16 hai, entender que declaramos un int x chamado, e neste momento da historia, o que é o valor de x? [Resposta do alumno inaudível] [David M.] Dereito, quen sabe, algún valor lixo potencialmente, así, o 17, nós só dicir que o usuario me dar un número, por favor, e paso 18 é onde está interesante. Scanf parece prestar unha idea de printf en que el usa eses códigos de formato entre comiñas. D% é, naturalmente, un número decimal. Pero por que estou pasando & x no canto de só x? O primeiro é correcta. Si [Resposta do alumno inaudível] Exactamente, o obxectivo do programa, como o GetInt propia función, é para ter unha int usuario que pode pasar funcións todas as variables que quero, pero eu non paso-los por referencia ou por enderezo ou punteiro, todos sinónimos para fins de hoxe, a continuación, que a función non ten capacidade de cambiar o contido da variable. Isto pasaría nunha copia así como a versión de buggy de intercambio que xa falamos sobre algunhas veces agora. 

Pero en vez diso, facendo & x, eu estou literalmente pasando o que? [Alumno] O enderezo. >> O enderezo de x. É como debuxar un mapa para a función chamada scanf e dicindo aquí, Estas son as direccións para un bloque de memoria no ordenador que pode ir almacenar algún enteiro dentro Para que sscanf para facer agora que o operador, o que parte da sintaxe é que vai ter que usar aínda que non poida velo porque alguén escribiu esa función? Noutras palabras - o que é iso? [Estudante] X ler. Non vai ser unha lectura, pero só en relación á x aquí. Se scanf está pasado o enderezo de x, sintaticamente, o operador está obrigado a existir nalgún lugar dentro de implantación, de xeito que scanf scanf Pode realmente escribir un número de 2 a ese enderezo? Si, entón o *. Lembre-se de que o * é o noso operador dereference, o que esencialmente significa ir máis alá. 

Así que ten sido entregado un enderezo, como é o caso aquí, scanf é, probablemente, se nós realmente mirou ao redor do seu código fonte está facendo * x ou o equivalente a realmente ir a este enderezo e poñer un valor alí. Agora, o xeito no que scanf recibe a entrada do teclado, imos trasfega as mans para fóra para hoxe. Basta asumir que o sistema operativo permite que sscanf para falar para o teclado do usuario, pero neste punto agora na liña 19, cando simplemente imprimir x, parece ser o caso scanf que puxo un int en x. Isto é exactamente como scanf funciona, e lembrar a semana pasada é exactamente como GetString e GetInt ea súa outra familia de funcións finalmente funciona, aínda que con lixeira variación como sscanf, o que significa dixitalizar unha cadea no canto do teclado. Pero imos dar un ollo a unha pequena variación desta. En scanf2, realmente errou. O que está mal, e eu vou ocultar o comentario que explica como moi o que está mal con este programa, a versión 2? Sexa tan técnico como posible neste momento. Parece moi bo. É ben recuado, pero- Ok, que tal imos poda-la cara abaixo para preguntas máis curtos? Liña 16. O que é liña 16 facendo en inglés, pero precisa técnico? Quedando un pouco raro. Si, Michael. [Estudante] Está apuntando para a primeira letra dunha cadea. 

Ok, preto. Deixe-me axustar iso un pouco. Apuntando para a primeira letra dunha cadea, está declarando unha variable chamada tapón que pode apuntar para o primeiro enderezo dunha cadea, ou sexa, que apuntar máis precisamente a unha char. Teña en conta que non é realmente apuntando para calquera lugar, porque non hai operador de asignación. Non hai signo igual, entón todo o que estamos facendo é asignación de reserva variable chamada. El pasa a ser de 32 bits porque é un punteiro, E o contido de tapón, finalmente, presuntamente conterá un enderezo de un char, pero por agora, o que tapón contén? Só algúns teito, quen sabe, algún valor de lixo, porque non explicitamente inicializar, non debemos asumir nada. Ok, entón agora é a liña 17-o que fai a liña 17 ten? Quizais que vai quentar iso. Ela imprime unha cadea, non? Ela imprime Cordas por favor. 

Liña 18 é unha especie de familia agora que acabamos de ver unha variación deste pero cun código de formato diferente, por iso, en liña 18, estamos dicindo scanf aquí é o enderezo dun bloque de memoria. Eu quero que tocar unha corda, como implicado por% s, pero o problema é que non temos feito algunhas cousas aquí. O que é un dos problemas? [Estudante] Está tentando dereference un punteiro nulo. Bo, punteiros nulos ou só outro xeito descoñecido. Vostede está entregando scanf un enderezo, pero dixo hai pouco que ese enderezo é algún valor lixo porque realmente non atribúe-lo a nada, e por iso está dicindo scanf efectivamente ir colocar unha corda aquí, pero non sei onde aquí aínda é, entón nós realmente non teño memoria alocada para buffer. Ademais, o que tampouco, aínda dicindo scanf? Supoña que este era un anaco de memoria, e non era un valor de lixo, pero aínda non está dicindo scanf algo importante. [Estudante] onde realmente é, o comercial. Ampersand, polo tanto, neste caso, está todo ben. Porque o buffer xa está declarado como un punteiro coa peza * de sintaxe, non necesitamos usar e comercial porque é xa un enderezo, pero eu creo que oín-lo aquí. [Estudante] Como grande é? Bo, non estamos dicindo scanf quão grande ese buffer é, o que significa que, aínda que fose un tapón punteiro, estamos dicindo scanf, colocar unha corda aquí, pero aquí pode ser de 2 bytes, que pode ser de 10 bytes, que podería ser un megabyte. Scanf non ten idea, e porque este é un anaco da memoria presuntamente, non é unha secuencia aínda. É só unha corda unha vez que escribir caracteres e un \ 0 para o bloque de memoria. Agora é só un anaco de memoria. Scanf non vai saber cando deixar de escribir a este enderezo. 

Se lembrar algúns exemplos no pasado que eu aleatoriamente tecleados no teclado tentando estourar un buffer, e falamos o venres sobre exactamente isto. Se un adversario de algunha maneira, inxecta no seu programa unha palabra moi grande ou frase ou ben estaba esperando pode invadida unha peza de memoria, que pode ter consecuencias malas, como asumir todo o programa en si. Necesitamos corrixir isto de algunha maneira. Deixe-me afastar e ir para a versión 3 do programa. Isto é un pouco mellor. Nesta versión, notar a diferenza. Na liña 16, estou de novo declarar unha variable chamada tapón, pero o que é iso agora? É unha matriz de 16 caracteres. Iso é bo, porque iso significa que podo agora dicir scanf aquí é unha peza de memoria real. Vostede case pode pensar en matrices como punteiros, agora, aínda que eles non son realmente equivalentes. Se comportan de xeito diferente en diferentes contextos. Pero é certamente o caso de que o buffer é referencia 16 caracteres contiguos porque é iso que é unha matriz e foi por algunhas semanas agora. 

Aquí, eu estou dicindo scanf aquí está un anaco da memoria. Esta vez é na verdade un anaco da memoria, senón porque é que este programa aínda explorável? O que hai de malo aínda? Eu dixen me dar 16 bytes, pero- [Alumno] O que se tipo en máis de 16 anos? Exactamente, e se o usuario escribe 17 caracteres ou carácter 1700? En realidade, imos ver se non podemos tropezar este erro agora. É mellor, pero non perfecto. Deixe-me ir adiante e executar facer scanf3 para compilar este programa. Déixame correr scanf3, cadea por favor: Ola, e parece que estamos ben. Deixe-me tentar un pouco máis, Ola alí. Ok, imos facer Ola alí como está hoxe, Intro. Obtendo tipo de sorte aquí, imos dicir Ola alí como está. Drogas. Ok, entón tivemos sorte. Imos ver se non podemos fixar iso. Non, iso non me vai deixar copiar. Imos tentar de novo. Todo ben, prepara-se. Imos ver canto tempo podo finxir foco mentres aínda está facendo iso. Drogas. Iso é moi apropiado, en realidade. Alí imos nós. Punto fixo. 

Isto, embaraçando aínda que tamén sexa, é tamén unha das fontes de gran confusión ao escribir programas que teñen erros, porque se manifestan só de cando en vez, ás veces. A realidade é que, mesmo se o código está completamente roto, el só podería ser completamente roto de cando en vez porque ás veces, esencialmente, o que pasa é que o sistema operativo aloca un pouco máis de memoria do que realmente precisa, por calquera razón, e para que ninguén máis está a usar a memoria pronto tras o seu anaco de 16 caracteres, por iso, se vai para 17, 18, 19, calquera que sexa, non é un negocio tan grande. Agora, o ordenador, aínda que non falla nese punto, Pode, eventualmente, usar o número de bytes de 17 ou 18 ou 19 para outra cousa, momento no que os datos que poñer alí, aínda que excesivamente longo, vai ser substituídas potencialmente por algunha outra función. Non é necesariamente vai permanecer intacta, pero non vai necesariamente provocar un fallo seg. Pero, neste caso, eu finalmente desde caracteres suficientes que esencialmente superado meu segmento de memoria, e listo, o sistema operativo, dixo: "Sentímolo, iso non é fallo de segmento de boa calidade." 

E imos ver agora o que permanece aquí no meu directorio entender que eu teño ese arquivo aquí, o núcleo. Nótese que esta é unha vez máis chamado core dump. É esencialmente un arquivo que contén o contido da memoria do seu programa ao momento en que deixou de funcionar, e só para tratar un pequeno exemplo aquí, deixe-me entrar aquí e executar o gdb no scanf3 e seleccione un terceiro argumento chamado núcleo, e notar aquí que eu listar o código, nós imos ser capaces, como de costume co gdb para comezar a camiñar a través deste programa, e eu poida executa-lo e así que eu bater-como co comando paso na gdb- así que alcanzou a liña de buggy potencialmente despois de escribir unha secuencia enorme, Eu vou ser capaz de realmente identificar-lo aquí. Máis sobre iso, con todo, na sección en termos de core dumps e así por diante, así que realmente pode bisbilhotar dentro do core dump e ver en que liña o programa non ten. Algunha preguntas, entón en punteiros e enderezos? Porque hoxe, imos comezar a tomar por certo que esas cousas existen e sabemos exactamente o que son. Si 

[Estudante] Como é que non tes que poñer un comercial ao lado da parte Boa pregunta. Como é que eu non teño que poñer un comercial ao lado da matriz de caracteres como eu fixen anteriormente coa maioría dos nosos exemplos? A resposta curta é matrices son un pouco especial. Vostede case pode pensar un tapón como realmente un enderezo, e iso só pasa de ser o caso de que a notación de colchete é unha conveniencia para que poidamos entrar en soporte 0, franxa 1, franxa 2, sen ter que utilizar a notación *. Isto é un pouco de unha mentira porque as matrices e punteiros son, en realidade, un pouco diferente, pero que moitas veces pode, pero non sempre ser usados ​​indistintamente. En suma, cando a función está esperando un punteiro para un bloque de memoria, pode pasar un enderezo que foi retornado por malloc, e imos ver malloc novo antes de tempo, ou pode pasarlle o nome dunha matriz. Non ten que facer comercial con matrices porque eles xa están esencialmente, como enderezos. Esa é a única excepción. Os corchetes fan especiais. 

Vostede podería poñer un comercial á beira do tapón? Non neste caso. Iso non vai funcionar porque, de novo, desta esquina caso onde matrices non son moi realmente enderezos. Pero imos quizais volva para que en pouco tempo con outros exemplos. Imos tentar resolver un problema aquí. Temos unha estrutura de datos que temos benvida a empregar durante algún tempo coñecida como unha matriz. O caso en cuestión, é o que acabamos de ter. Pero matrices teñen algún upsides e inconvenientes. Matrices son agradables porque? ¿Que é unha cousa que lle gusta, na medida en que lle gusta matrices-sobre matrices? O que é conveniente sobre eles? O que é interesante? Por que nós presenta-los en primeiro lugar? Si [Estudante] Poden almacenar unha gran cantidade de datos, e non ten que usar unha cousa toda. Pode usar unha sección. Bo, con unha matriz pode almacenar unha gran cantidade de datos, e non necesariamente ten que usar todo isto, para que poida overallocate, o que pode ser cómodo se non sabe de antemán cantos de algo que esperar. 

GetString é un exemplo perfecto. GetString, escrito por nós, non ten idea de cantos chars que esperar, de xeito que o feito de que podemos reservar bloques de memoria contigua é bo. Matrices tamén resolver un problema que vimos hai unhas semanas agora onde o código empeza a transformarse en algo moi mal deseñado. Lembre que eu creei unha estrutura estudante chamado David, e despois que foi realmente unha alternativa, porén, a ter unha variable chamada nome e outra variable chamada, eu creo, casa, e outra variable chamada ID, porque nesa historia entón eu quería introducir algo máis Rob gusta o programa, entón eu decidir esperar un minuto Eu teño cambiar o nome destas variables. Imos chamar de meu nome1, ID1, house1. Imos chamar Rob nome2, house2, ID2. Pero, entón, agarde un minuto, o que dicir de Tommy? Entón tivemos tres variables máis. Nós introducimos a alguén, catro conxuntos de variables. O mundo comezou a ficar confuso moi rapidamente, para que introduciu estruturas, eo que é interesante sobre unha estrutura? O que fai un struct C permiten que fai? É realmente estraño hoxe. O que? >> [Resposta do alumno inaudível] Si, en concreto, typedef permite crear un novo tipo de datos, e estrutura, a palabra clave struct, permite encapsular pezas conceptualmente relacionados de datos xunto e, posteriormente, chamalos de algo así como un estudante. 

Isto foi bo, porque agora podemos modelar especie moito máis consistente conceptualmente a noción dun estudante nunha variable en vez de ter unha forma arbitraria para unha cadea, un a un ID, e así por diante. Matrices son bos porque nos permiten comezar a limpar o noso código. Pero o que é unha desvantaxe agora dunha matriz? O que non pode facer? Si [Estudante] Ten que saber o quão grande é. Ten que saber como é grande, por iso é un tipo de dor. Aqueles de vós con experiencia previa en programación sabe que unha morea de linguas, como Java, pode pedir un anaco de memoria, especialmente dunha matriz, quão grande é vostede, cunha lonxitude de, propiedade, por así dicir, e iso é realmente cómodo. C, non pode sequera chamarse strlen nunha matriz xenérica porque strlen, como a palabra indica, é só para cordas, e pode descubrir a lonxitude dunha cadea a causa deste convenio humana de ter un \ 0, pero un conxunto, máis xenericamente, é só unha peza de memoria. Se é unha matriz de enteiros, non vai ser un carácter especial ao final esperando por ti. Ten que lembrar a lonxitude dunha matriz. Outro punto negativo dunha matriz elevou a súa cabeza GetString si. O que é outra desvantaxe dunha matriz? Señor, só eu e vostede hoxe. [Resposta do alumno inaudível] >> E o que? El é declarado na pila. Ok, declarou na pila. Por que non gusta? [Estudante], porque é reutilizada. El está reutilizados. Ok, se usa unha matriz para reservar memoria non pode, por exemplo, devolve-lo, porque é na pila. Ok, iso é unha desvantaxe. E canto a outro con unha matriz? Unha vez que afecta-lo, é do tipo parafuso, se precisa de máis espazo que a matriz ten. 

Entón, nós introducimos, malloc recall, que nos deu a capacidade de asignar dinamicamente a memoria. Pero o que se intentou un mundo completamente diferente? O que se quería resolver algúns destes problemas por iso, en vez miña pluma-dorme aquí- o que se quería esencialmente en vez de crear un mundo que xa non é así? Trata-se dunha matriz, e, por suposto, este tipo de deterioración, xa que alcanzou o fin da matriz, e agora non ten máis espazo para outro enteiro ou outro personaxe. E se nós medio que preventivamente dicir ben, por que non imos relaxarse esta esixencia de que todos eses anacos de memoria ser contiguo volta atrás, e por que non, cando eu teño un int ou char, me dea espazo para un deles? E cando eu ter outro, dá-me un outro espazo, e cando precisa de outro, dáme un outro espazo. A vantaxe de que agora é que, se alguén leva a memoria por aquí, non é gran cousa. Vou levar este anaco adicional de memoria aquí e despois este. 

Agora, o único problema aquí é que está case se sente como eu teño todo un conxunto de variables diferentes. Iso séntese como cinco diferentes variables potencialmente. Pero o que se roubar unha idea de cordas en que, dalgún xeito vincular estas cousas xuntas conceptualmente, e que se eu fixese iso? Esta é a miña frecha moi mal deseñado. Pero supoña que cada un destes anacos de memoria apuntou para o outro, e este cara, que non ten ningún irmán á súa dereita, non ten ningunha frecha tal. Este é de feito o que se chama unha lista ligada. Esta é unha nova estrutura de datos que nos permite reservar un bloque de memoria, despois outra, despois outra, despois outra, a calquera hora que queremos durante un programa, e lembre que todos eles son de algunha maneira relacionados por, literalmente, encadeando os, e nós fixemos iso pictoricamente aquí cunha frecha. Pero no código, o que sería o mecanismo a través do cal puidese dalgún xeito se conectar, case como scratch, un anaco de outro anaco? Nós poderiamos usar un punteiro, non? Porque realmente a frecha que vai da praza superior esquerda, este cara aquí a esta, podería conter dentro da praza non só algúns ints, non só algúns char, pero o que si realmente alocada un pouco de espazo extra para que agora, Cada un dos meus anacos de memoria, aínda que iso me vai custar, agora parece un pouco máis longo no que un dos bloques de memoria é usado para un número, así como o número 1, e, a continuación, se este tipo almacena o número 2, este anaco de outra memoria é usada para unha frecha, ou máis concretamente, un punteiro. E supoña que almacenar o número 3 por aquí, mentres eu uso iso para apuntar para este cara, e agora este cara, imos supor que eu só quero eses tres anacos de memoria. Vou debuxar unha liña por iso, indicando nulo. Non hai personaxe adicional. 

En realidade, esta é a forma na que podemos ir sobre a aplicación de algo que se chama unha lista ligada. Unha lista ligada é unha nova estrutura de datos, e é un trampolín para a moi afeccionado estruturas de datos que comezan a resolver problemas ao longo das liñas de Facebook tipo de problemas e problemas de tipo Google onde ten enormes conxuntos de datos, e xa non corta para almacenar todo de forma contigua e utilizar algo como procura lineal ou mesmo algo así como investigación binaria. Queres mesmo mellores tempos de execución. De feito, un dos obxectivos primordiais imos falar máis tarde esta semana ou a próxima é un algoritmo cuxo tempo de carreira é constante. Noutras palabras, ten sempre a mesma cantidade de tempo, non importa como é grande a entrada, e que sería de feito interesante, ata máis que algo logarítmica. ¿Que é iso na pantalla aquí? Cada un dos rectángulos é o que eu deseño a man. Pero a cousa toda a maneira á esquerda é unha variable especial. Vai ser un punteiro único porque a única pegadinha con unha lista ligada, como esas cousas son chamados, é que ten para coller a unha final da lista de relacionados. 

Así como cunha corda, ten que saber o enderezo do primeiro carácter. Mesmo para listas ligadas. Ten que saber o enderezo do primeiro anaco de memoria porque de alí, pode chegar a calquera outro. Desvantaxe. Cal é o prezo que estamos pagando por esa versatilidade de ter un dinámicamente estrutura de datos de tamaño considerable que se algunha vez precisa de máis memoria, todo ben, simplemente reservar un anaco e deseñar un punteiro de da antiga para a nova cola da lista? Si [Estudante] É preciso espazo de preto de dúas veces máis. El ocupa un espazo dúas veces maior, de xeito que é sempre unha desvantaxe, e vimos que cambio antes entre tempo e espazo e flexibilidade onde por agora, non precisamos de 32 bits para cada un deses números. Nós realmente necesitamos de 64, 32 o número e 32 para o punteiro. Pero, ei, eu teño 2 gigabytes de memoria RAM. Engadindo máis 32 bits aquí e aquí non parece que de un gran negocio. Pero para grandes conxuntos de datos, en definitiva engade-se, literalmente, o dobre. O que é outra desvantaxe agora, ou o que é o que imos característica desistir, representar listas de cousas con unha lista ligada e non unha matriz? [Estudante] Non pode atravesa-lo cara atrás. Vostede non pode cruzalo cara atrás, entón é do tipo parafuso, se está camiñando de esquerda a dereita, cun loop ou un loop while e entón entender, "Oh, eu quero volver para o inicio da lista." Vostede non pode porque estes punteiros só ir de esquerda a dereita, como as frechas indican. 

Agora, vostede podería lembrar o inicio da lista, con outra variable, pero iso é unha complexidade para manter presente. Unha matriz, non importa o quão lonxe vai, sempre pode facer menos, menos, menos, menos e volver de onde veu. O que é outra desvantaxe aquí? Si [Pregunta estudante inaudível] Vostede podería, entón realmente acaba de propoñer unha estrutura de datos chamado de lista doblemente ligada, e, en realidade, lle gustaría engadir outro punteiro a cada un deses rectángulos que vai outra dirección, ao contrario do que é que agora pode atravesar a outro, a desvantaxe de que agora está a usar tres veces máis memoria que acostumabamos e tamén aumentar a complexidade en termos de código que ten que escribir para acertar. Pero todos estes son quizais compensacións razoables, a reversión é máis importante. Si [Estudante] Tamén non pode ter unha lista 2D vinculado. Bo, non pode realmente ter unha lista 2D conectados. Vostede podería. Non é tan fácil como unha matriz. Como un array, fai soporte aberto, soporte pechada, soporte aberto, pechado soporte, e terá unha estrutura 2-dimensional. Vostede podería aplicar unha lista de 2-dimensional conectados Se engadir, como propuxo un punteiro terceiro cada unha desas cousas, e pensar en outra lista que vén vostede estilo 3D da pantalla para todos nós, que é só unha outra corrente de calquera tipo. Nós poderiamos facelo, pero non é tan sinxelo como escribir soporte aberto, colchete. Si [Pregunta estudante inaudível] Bo, entón iso é un retroceso real. 

Estes algoritmos que temos pined máis, como oh, busca binaria, pode buscar unha matriz de números na tarxeta ou un libro de teléfono moito máis rápido utilizar dividir e conquistar é un algoritmo de procura binaria, pero busca binaria necesarios dous supostos. Un, que os datos foron clasificados. Agora, podemos manter este presuntamente clasificados, quizais por iso non é unha preocupación, pero de busca binaria tamén asumiu que tivo acceso aleatorio a lista de números, e unha matriz permite que teña acceso aleatorio, e de acceso aleatorio, Quero dicir, se está dado unha matriz, canto tempo leva para ti para chegar ao soporte de 0? Unha operación, pode usar [0] e está aí. Cantos pasos que hai que para chegar ao lugar 10? Un paso, é só ir a [10] e está alí. Por outra banda, como comeza o número enteiro 10 nunha lista ligada? Ten que comezar ao principio, porque só está lembrando o inicio dunha lista ligada, como unha cadea está lembrado polo enderezo do seu primeiro char, e ao descubrir que int 10 ou que o carácter 10 en unha secuencia, ten que buscar a cousa toda. 

De novo, non estamos resolvendo todos os nosos problemas. Estamos introducindo novos, pero realmente depende do que está intentando proxectar a. En termos de aplicación do presente, podemos pedir unha idea de que a estrutura do alumno. A sintaxe é moi semellante, só que agora, a idea é un pouco máis abstracto casa e nome e ID. Pero propoño que nós poderíamos ter unha estrutura de datos en C que se chama nodo, como a última palabra sobre o slide suxire, dentro dun nodo, e un nó é só un contenedor xenérico en ciencia da computación. Xeralmente é deseñada como un círculo ou un cadrado ou rectángulo, como temos feito. E nesta estrutura de datos, que ten un int, n, de xeito que é o número que eu queira gardar. Pero o que é esa segunda liña, struct node * próximo? Por que iso é correcto, ou cal o papel que este xogo cousa, aínda que sexa un pouco enigmática, a primeira vista? Si [Resposta do alumno inaudível] Exactamente, por iso o tipo * do espólio que é un punteiro de calquera tipo. O nome deste punteiro é arbitrariamente seguinte pero poderiamos chamar calquera cousa que queremos, pero o que fai este punto punteiro para? [Estudante] Outro nó. >> Exactamente, el apunta a outro nodo tal. 

Agora, iso é unha especie de curiosidade de C. Lembre que C é lido por un top compilador para abaixo, de esquerda a dereita, que significa que se iso é un pouco diferente do que fixemos co alumnado. Cando definimos un estudante, que se non poñer unha palabra alí. El só dixo typedef. Entón tivemos int id nome, corda, corda casa, e, a continuación, na parte inferior do estudante da estrutura. Esta declaración é un pouco diferente, porque, novo, o compilador C é un pouco idiota. El só vai ler de arriba para abaixo, así que se atinxe a liña 2 aquí onde próxima está declarada e ve Oh, aquí está unha variable chamada seguinte. É un punteiro para un nó de estrutura. O compilador vai entender o que é un nodo de estrutura? Eu nunca oín falar desa cousa antes, porque o nodo palabra non poderían aparecer ata o fondo, para que haxa esta redundancia. Ten que dicir no struct aquí, o que pode reducir máis tarde grazas a typedef aquí, pero iso é porque estamos referenciando a estrutura en si no interior da estrutura. Esa é a única pegadinha aí. 

Algúns problemas interesantes van xurdir. Temos unha lista de números. Como imos introducir nel? Como é que imos procura-lo? Como podemos eliminar iso? Especialmente agora que temos que xestionar todos eses punteiros. Vostede pensou punteiros eran unha especie de alucinante cando tiña un deles só tentando ler un int para el. Agora, temos que manipular o valor dunha lista enteira. Por que non imos tomar o noso intervalo de 5 minutos aquí, e entón nós imos levar algunhas persoas ata o escenario para facer exactamente isto. 

C é moito máis divertido cando é encenado. Quen ía literalmente quere ser o primeiro? Ok, imos alí cara arriba. Vostede está en primeiro lugar. Quen quere ser o 9? Ok, 9. Como preto de 9? 17? A panelinha aquí. 22 e 26 en que a liña da fronte. E entón, que tal alguén alí sendo apuntada. Está 34. Ok, de 34 anos, vén para arriba. Primeiro está alí. Ok, todos os catro de vós. E quen foi que dixo para 9? Quen é o noso 9? Quen realmente quere ser 9? Todo ben, imos alí, ser 9. Aquí imos nós. 34, nós imos atopalo por alí. A primeira parte é facervos ollar como aquel. 26, 22, 17, bo. Se pode estar ao lado, porque estamos indo a malloc vostede nun momento. 

Bo, moi bo. Ok, excelente, así que imos pedir un par de preguntas aquí. E, en realidade, cal é o seu nome? >> Anita. Anita, todo ben, veña ata aquí. Anita vai axudar a resolver un tipo de pregunta moi simple, en primeiro lugar, que é como atopar ou non un valor está na lista? Agora, observe que o primeiro, representado aquí por Lucas, é un pouco diferente, e por iso o seu anaco de papel é deliberadamente de lado porque non é tan alto e non toma-se como moitos bits, Aínda que tecnicamente ten o mesmo tamaño de papel só rodado. Pero é un pouco diferente, xa que el ten só 32 bits para un punteiro, e todos eses caras son de 64 bits, a metade dos cales é o número, a metade dos cales é un punteiro. Pero o punteiro non é retratado, por iso, se vostedes puidesen un pouco sen xeito Use a man esquerda para apuntar para a persoa ao seu lado. E é o número 34. Cal é o seu nome? Ari. Ari, polo tanto, en realidade, manter o papel na súa man dereita, ea man esquerda vai directo para abaixo. Vostede declara nulo á esquerda. 

Agora o noso retrato humano é moi consistente. Isto é, en realidade, como os punteiros traballar. E se pode amasar un pouco desa forma que eu non estou no seu camiño. Anita aquí, atopar-me o número 22, pero asumir unha restricción de non seres humanos seguro anacos de papel, pero esta é unha lista, e só ten Lucas para comezar porque é, literalmente, o primeiro punteiro. Supoña que vostede mesmo é un punteiro, e que tamén ten a capacidade de apuntar algo. Por que non comezar por apuntar exactamente o que Lucas está a apuntar? Bo, deixe-me e aprobar isto aquí. Só por unha cuestión de debate, deixe-me tirar para arriba unha páxina en branco aquí. Como se escribe o seu nome? >> Anita. Ok, Anita. Digamos nodo * Anita = Lucas. Ben, non debemos chamalo de Lucas. Debemos chamalo primeiro. Por que iso é de feito consistente coa realidade aquí? Un primeiro xa existe. Primeiro foi asignado nalgún lugar, presumiblemente, aquí enriba. * Primeiro no, e que foi asignada unha lista de algunha maneira. Eu non sei como isto aconteceu. Iso aconteceu antes da clase comezar. Esta lista ligada de seres humanos foi creado. E agora, neste momento da historia, todo iso é ir en Facebook, aparentemente, máis tarde, neste punto da historia, Anita foi inicializada para ser igual ao primeiro, o que non significa que os puntos de Anita en Lucas. En vez diso, ela apunta para o que apunta a pois o mesmo enderezo que está dentro de 32 bits - Lucas 1, 2, 3 - agora tamén dentro de 32 Anita bits - 1, 2, 3. 

Agora, atopar 22. Como vai facer sobre iso? O que é que o punto? >> Para o que sexa. Apunte para o que quere, entón vai adiante e actuar para fóra o mellor que poida aquí. Bo, bo, e agora está a apuntar o que é o seu nome, con 22? Ramón. >> Ramon, entón Ramón está seguro 22. Xa fixo un cheque. O Ramón == 22, e se é así, por exemplo, podemos volver verdade. Deixe-me, mentres estes faces estar aquí un pouco sen xeito, deixe-me facer algo axiña, como bool atopar. Eu estou indo a ir adiante e dicir (lista * nodo, int n). Eu estarei de volta con vós. Eu só teño que escribir un código. E agora eu estou indo a ir adiante e facelo, o * Anita = lista. E eu estou indo a ir adiante e dicir ao mesmo tempo (Anita! = NULL). 

A metáfora aquí está quedando un pouco estirado, pero mentres (Anita! = NULL), o que quero facer? Eu teño algunha forma de referenciar o enteiro que Anita está a apuntar. No pasado, cando se estruturas, o que é un nodo, usamos a notación de punto, e queremos dicir algo así como anita.n, pero o problema aquí é que Anita non é unha estrutura en si. O que é? Ela é un punteiro, por iso mesmo, se quere usar esta notación de punto e este vai mirar deliberadamente un pouco enigmática- temos que facer algo, como ir a man esquerda o que Anita está a apuntar cara e en seguida, obter o campo chamado n. Anita é un punteiro, pero o que é * Anita? ¿Que pensas cando vai para o que Anita está a apuntar? A estrutura, un nó e un nó de recordo, ten un campo chamado n porque, lembre, estes dous campos, próximos e n, que vimos hai pouco aquí. 

Para realmente imitar iso no código, poderiamos facer, e dicir se ((* Anita). n == n), o n que eu estou buscando. Teña en conta que a función foi aprobada no número que me interesa. Entón eu podo ir adiante e facer algo como certo retorno. Outra cousa, se este non é o caso, o que quero facer? Como traduzo para codificar o que Anita fixo intuitivamente andando a través da lista? ¿Que debo facer aquí para simular Anita dar ese paso cara á esquerda, que paso a esquerda? [Resposta do alumno inaudível] >> ¿Que é iso? [Resposta do alumno inaudível] Bo, non é unha idea malo, pero no pasado, cando fixemos iso, fixemos Anita + + porque que quere engadir o número 1 para Anita, que normalmente apuntar á seguinte persoa, como Ramón, ou a persoa próxima a el, ou a persoa próxima a el para abaixo da liña. Pero iso non é moi bo aquí, porque o que esa cousa parece na memoria? Non é iso. Temos que desactivar iso. Parece que este na memoria, e aínda que eu teña deseñado 1 e 2 e 3 preto un do outro, realmente simular este-Vostedes poden, aínda apuntando para as mesmas persoas, algúns de vostedes poden dar un paso atrás aleatoria, algúns de vostedes un paso ao chou para adiante? 

Esta confusión é aínda unha lista ligada, pero estes faces poderían estar en calquera lugar na memoria, así Anita + + non vai funcionar por que? O que está en lugar Anita + +? Quen sabe. E algún outro valor que só pasa a ser interposta entre todos eses nós por casualidade, porque non estamos usando unha matriz. Nós asignado a cada un destes nós individualmente. Ok, se vostedes poden limpar-se de volta. Deixe-me propor que, en vez de Anita + +, que en vez facer Anita queda- así, por que non imos para o que quere que Anita está a apuntar e despois facer. próximo? Noutras palabras, imos para Ramón, que está sostendo o número 22, e despois. seguinte é como se Anita sería copiar o punteiro man esquerda. Pero ela non quixo ir máis lonxe do que Ramón porque atopamos 22. Pero iso sería a idea. Agora, iso é unha desorde horrible. Honesta, ninguén vai lembrar esta sintaxe, e así, por sorte, en realidade é un pouco deliberada-oh, non realmente ver o que eu escribín. Isto sería máis convincente se puidese. Listo! 

Detrás das escenas, eu estaba resolvendo o problema desa forma. Anita, para dar ese paso cara á esquerda, en primeiro lugar, nós ir ao enderezo que Anita está a apuntar cara e onde vai atopar non só n, que verifiquei só para efectos de comparación, pero tamén vai atopar preto - neste caso, Man esquerda Ramón, apuntando para o próximo nó na lista. Pero esta é a desorde horrible a que me refire anteriormente, pero acontece C nos permite simplificar isto. En vez de escribir (* Anita), podemos no canto de só escribir Anita-> n, e é exactamente a mesma cousa funcionalmente, pero é moito máis intuitivo, e é moito máis consistente coa imaxe que temos está a deseñar todo ese tempo usando as frechas. 

Por fin, o que necesitamos facer ao final deste programa? Hai unha liña de código restante. Devolver o que? Falso, porque se pasar todo o loop while e Anita é, de feito, nulo, isto significa que percorreu todo o camiño para o fin da lista onde ela estaba apuntando-o que é o seu nome? Ari man esquerda. >> Ari, que é nulo. Anita agora é nulo, e eu entender que está de pé aquí sen xeito no limbo porque eu estou saíndo nun monólogo aquí, pero imos facela-lo novo en só un momento. Anita é nulo nese punto da historia, de xeito que o loop while remata, e nós temos que voltar falso, porque se ela ten todo o camiño para punteiro nulo de Ari entón non había número que buscou na lista. Podemos borrar iso tamén, pero esa é unha implementación moi boa, entón dunha función de paso, unha función para atopar unha lista ligada. É aínda busca lineal, pero non é tan sinxelo como un punteiro + + ou + + dunha variable i porque agora non podemos adiviñar en que cada un destes nós se atopan na memoria. Temos que, literalmente, seguir a pista de migas de pan ou, máis especificamente, punteiros, para comezar a partir dun nodo a outro. 

Agora imos tratar de outro. Anita, quere volver para aquí? Por que non imos adiante e reservar outra persoa do público? Malloc cal é o seu nome? >> Rebecca. Rebecca. Rebecca foi malloced do público, e ela é agora almacenar o número 55. E o obxectivo en mans agora é a Anita para introducir Rebecca na lista ligada aquí no seu lugar apropiado. Veña aquí por un momento. Eu teño feito algo así. Eu fixen * nodo. E cal é o seu nome? Rebecca. >> Rebecca, todo ben. Rebecca queda malloc (sizeof (nó)). Así coma nós alocamos cousas como estudantes e outros enfeites no pasado, Temos o tamaño do nó, para agora Rebecca está a apuntar cara o que? Rebecca ten dous campos dentro dela, un dos cales é 55. Imos facer o que Rebecca-> = 55. Pero, entón, Rebecca-> seguinte debe ser-como agora, a man del é unha especie de, quen sabe? Está apuntando para un valor de lixo, entón por que non facer para unha boa medida que polo menos facelo para que a man esquerda está agora ao seu lado. Agora Anita, leva-lo a partir de aquí. Tes Rebecca sendo atribuídos. Dalle descubrir onde hai que poñer Rebecca. Bo, moi bo. Ok, bo, e agora necesitamos de ti para proporcionar un pouco de dirección, de xeito que alcanzou Ari. Súa man esquerda é nulo, pero Rebecca pertence claramente á dereita, Entón como é que nós temos que cambiar este ligada a fin de introducir Rebecca no lugar axeitado? Se pode, literalmente, mover as mans das persoas de esquerda en torno a como necesario, nós imos resolver o problema desa forma. Ok, bo, e, con todo, a man esquerda de Rebecca xa está ao seu lado. 

Iso foi moi fácil. Imos tentar reservar-estamos case listo, 20. Ok, imos alí cara arriba. 20 foi asignado, entón deixe-me ir adiante e dicir de novo aquí Nós acabamos de facer Saad * nodo. Temos malloc (sizeof (nó)). A continuación, facer a mesma sintaxe exacta como fixemos antes do 20, e eu vou facer = NULL seguinte, e agora cómpre a Anita introduza na lista ligada, se podería desempeñar ese papel exacto. Executar. Ok, bo. Agora pense con coidado antes de lle comezar a mover a man esquerda ao redor. Ten, de lonxe, o papel máis difícil hoxe. Cuxa man debe ser movido en primeiro lugar? Ok, agarde, eu estou escoitando algunhas n º. Algunhas persoas educadores quere axudar a resolver unha situación embarazosa aquí. Cuxa man esquerda debe ser actualizado primeiro, quizais? Si [Estudante] Saad. Ok, Saad, por que, entón? [Resposta do alumno inaudível] Bo, porque se mover cal é o seu nome? >> Marshall. Marshall, mover a súa man primeiro para abaixo a nulo, agora temos literalmente orfos catro persoas na lista porque era a única cousa a apuntar cara Ramon e todos á esquerda, de xeito que a actualización primeiro punteiro era malo. Imos desfacer isto. Bo, e agora vai adiante e pasar a man apropiado esquerda apuntando para Ramón. Iso séntese un pouco redundante. Agora hai dúas persoas apuntando para Ramon, pero iso é bo porque agora que doutra forma é que imos actualizar a lista? O que por outra banda ten que se mover? Excelente, agora temos perdido a memoria? Non, todo ben, imos ver se non podemos romper esta unha vez máis. 

Mallocing unha última vez, o número 5. En todo o camiño de volta, veña para abaixo. É moi emocionante. [Aplausos] Cal é o seu nome? >> Ron. Ron, ok, está malloced como número 5. Acaba de executado o código que é case idéntico a estes con só un nome diferente. Excelente. Agora, Anita, boa sorte introducir o número 5 na lista agora. Bo, e? Excelente, así que este é realmente o terceiro de tres casos en total. Primeiro tivemos alguén ao final, Rebecca. Entón, tivo alguén no medio. Agora temos a alguén no inicio, e, neste exemplo, agora tivo que actualizar Lucas por primeira vez porque o primeiro elemento na lista agora ten que apuntar cara a un novo nodo, que, á súa vez, está a apuntar o número de nodo 9. 

Esta foi unha demostración moi raro, eu estou seguro, así un gran aplauso para estes faces se puidese. Ben feito. Isto é todo. Pode manter os seus anacos de papel como un pouco de memoria. Acontece que facelo no código non é tan sinxelo coma mover as mans en torno a e apuntando punteiros en cousas distintas. Pero entender que cando chega a hora de implementar algo unha lista ligada ou unha variante do que se concentrarse en realidade estes fundamentos básicos, os problemas de mordida de tamaño que eu teño que descubrir, é esta man ou este lado, entender que o que é outra forma de un programa bastante complexo pode, de feito, ser reducida a bloques de construción moi sinxelo coma este. 

Imos levar as cousas para unha dirección máis sofisticado aínda. Temos agora a noción de lista ligada. Temos tamén, grazas á suxestión alí atrás-unha lista dobremente ligada, que parece ser case a mesma, pero agora temos dous punteiros dentro da estrutura en vez de unha, e probablemente poderiamos chamar os punteiros anterior e seguinte ou á esquerda ou á dereita, pero, de feito, ten que dous deles. O código sería un pouco máis complicado. Anita tería que facer máis traballo aquí no escenario. Pero seguramente poderiamos aplicar este tipo de estrutura. En termos de tempo de funcionamento, con todo, o que sería o tempo de execución por Anita de atopar un n número nunha lista ligada agora? O aínda grande de n, non é mellor que a procura lineal. Non podemos facer busca binaria, aínda que, unha vez máis. Por que isto ocorre? Vostede non pode saltar. Aínda que ver, obviamente, todos os seres humanos no escenario, e Anita podería eyeballed e dixo: "Aquí está a medio da lista", non sabería que, se fose un programa de ordenador porque o único que tiña que coller-se no inicio do escenario era Lucas, que foi o primeiro punteiro. Ela necesariamente que seguir estes enlaces, contando o seu camiño ata que atopou preto de medio, e aínda así, ela non vai saber cando alcanzou o medio a menos que vai todo o camiño ata o final para descubrir cantos son, despois volve atrás, e que tamén sería difícil, a menos que tivo unha lista dobremente ligada dalgún tipo. 

Resolución dalgúns problemas hoxe, pero a introdución de outros. E sobre unha estrutura de datos completamente diferente? Esta é unha foto das bandexas en Mather House, e, neste caso, temos unha estrutura de datos que temos tamén unha especie de posto falando. Nós conversas sobre unha pila no contexto da memoria, e que é unha especie de deliberadamente chamado porque unha morea de conformidade de memoria é efectivamente unha estrutura de datos que ten máis e máis cousas en capas enriba del. Pero o máis interesante sobre unha pila, como é o caso na realidade, é que é un tipo especial de estrutura de datos. É unha estrutura de datos en que o primeiro elemento é o último elemento para fóra. Se é a primeira bandexa para ser colocadas na pila, vai ser, lamentablemente, a bandexa último a ser eliminado da pila, e iso non é necesariamente unha cousa boa. Por outra banda, pode pensar sobre el o camiño inverso, o último é o primeiro en saír. 

Agora, os escenarios veñen á mente que ter unha pila estrutura de datos, onde ten que a propiedade do último, en primeiro lugar, é realmente atractivo? Iso é unha cousa boa? É que unha cousa ruín? É en definitiva, unha cousa ruín as bandexas non eran todos iguais e todos eles eran diferentes cores especiais ou outros enfeites, ea cor que quere é todo o camiño na parte inferior. Por suposto, non se pode lograr que sen gran esforzo. Ten que comezar dende o principio e traballar súa maneira para abaixo. Do mesmo xeito, se fose un deses nenos de fans que espera toda a noite intentando conseguir un iPhone e aliñar nun lugar coma este? Non sería bo se a tenda de Apple foron unha estrutura de datos de pila? Yay? Non? Só é bo para as persoas que aparecen no último minuto posible e despois arranquei a cola. E, en realidade, o feito de que eu estaba tan inclinado a dicir cola é realmente consistente co que chamariamos este tipo de estrutura de datos, un na realidade onde a orde non importa, e quere que o primeiro en ser o primeiro en saír aínda que só por unha cuestión de equidade humana. Imos chamar xeral de que unha estrutura de datos cola. 

Acontece que ademais de listas ligadas, podemos comezar a usar esas mesmas ideas básicas e comezar a crear novos tipos e diferentes solucións aos problemas. Por exemplo, no caso de que unha pila, que pode representar unha pila usando unha estrutura de datos coma este, gustaríame propoñer. Neste caso, eu teño declarado un struct, e eu xa dixen dentro desta estrutura é unha matriz de números e, a continuación, un tamaño variable chamada, e eu vou chamar esa cousa de unha pila. Agora, por que isto realmente funciona? No caso de que unha pila, podería deseñar esa eficacia na pantalla como unha matriz. Aquí é a miña pila. Estes son os meus números. E nós imos chamar-lles como este, este, este, este, este. E entón eu teño algún membro doutros datos aquí, que se chama de tamaño, de xeito que este é o tamaño, e isto é números, e colectivamente, o iPad todo aquí representa unha estrutura de pila. Agora, por defecto, o tamaño presuntamente ten que ser inicializar a 0, e que está dentro da matriz de números inicialmente cando reservar unha matriz? Lixo. Quen sabe? E iso realmente non importa. Non importa se é 1, 2, 3, 4, 5, de forma completamente aleatoria pola mala sorte almacenados na miña estrutura, porque desde que sei que o tamaño da pila é 0, entón eu sei que programaticamente, non mire para calquera dos elementos do array. Non importa o que está aí. Non mire para eles, como sería a implicación dun tamaño de 0. 

Pero supoña que agora vai adiante e introducir algo na pila. Quero introducir o número 5, entón eu coloque o número 5 aquí, e entón o que eu poño aquí? Agora eu realmente poñer para abaixo 1 para o tamaño, e agora, a pila é de tamaño 1. E se eu ir adiante e escribir o número, digamos, 7 próximo? Iso, entón, é actualizado a 2, e despois imos facer 9, e entón esta é actualizado a 3. Pero a característica interesante agora esta pila é que Eu teño que borrar elemento que se eu queira pop algo fóra da pila, por así dicir? 9 sería a primeira cousa a ir. Como a imaxe debe cambiar se eu queira aparecer un elemento da pila, Moi parecido cunha bandexa na Mather? Si >> [Estudante] tamaño definido para 2. Exactamente, todo o que fago é facer que o tamaño para 2, eo que fago coa matriz? Eu non teño que facer nada. Eu podería, só para ser anal, engada un 0 alí ou -1 ou algo para referirse a que este non é un valor legal, pero non importa porque Podo gravar fóra do conxunto en si o tempo que para que eu saiba só ollar para os dous primeiros elementos desta matriz. Agora, se eu for e engadir o número de 8 a esa matriz, como é que o cadro cambie a continuación? Isto torna-se 8, e isto fai-se 3. Estou cortando algúns cantos aquí. Agora temos 5, 7, 8, e estamos de volta a un tamaño de 3. Isto é moi sinxelo de implementar, pero cando é que imos lamentar esta decisión deseño? Cando as cousas comezan a ir moi, moi malo? Si [Resposta do alumno inaudível] Cando se quere volver e incorporarse o primeiro elemento que poñer dentro 

Acontece aquí, aínda que unha pila é unha matriz debaixo do capó, esas estruturas de datos que xa comezou a falar xeralmente tamén son coñecidos como abstractos estruturas de datos polo cal como son aplicadas é totalmente fóra de cuestión. Unha estrutura de datos como unha pila se quere engadir soporte operacións como impulso, que empuxa unha bandexa para a pila, e pop, que elimina un elemento da pila, e é iso. Se tivese que baixar código doutra persoa que xa implantadas esta cousa chamada unha pila, esa persoa tería escrito só dúas funcións para ti, push e pop, cuxo único propósito na vida sería facer exactamente isto. Vostede ou el ou a ela que aplicou o programa sería enteiramente un para decidir como aplicar a semántica de empurrar e aparecendo debaixo do capó ou a función de empurrar e popping. E eu fixen unha decisión un tanto miope aquí a través da implementación da miña pila con esta estrutura de datos simples por que? Cando é que esta pausa estrutura de datos? En que punto eu teño que voltar un erro cando o usuario chama push, por exemplo? [Estudante] Se non hai máis espazo. Exactamente, se hai non máis espazo, se superou a capacidade, que é todo en maiúsculas, porque suxire que é algún tipo de constante global. Ben, entón eu só vou ter que dicir: "Sentímolo, eu non podo empuxar outro valor na pila ", así como en Mather. 

Nalgún momento, eles van bater a parte de arriba do despacho que pouco. Non hai máis espazo ou capacidade de pila, momento no que hai algún tipo de erro. Teñen que poñer o elemento noutro lugar, a bandexa en outro lugar, ou en lugar ningún. Agora, con unha fila, podemos implementar lo un pouco diferente. Unha cola é un pouco diferente, no que, baixo o capo, pode ser aplicado como unha matriz, pero por que, neste caso, estou propondo ter tamén un elemento de cabeza que representa a cabeza de lista, a fronte da lista, a primeira persoa da cola na tenda de Apple, ademais de tamaño? Por que eu teño unha peza adicional de datos aquí? Debería de volta para o que os números e se eu deseño deste xeito. Supoñamos que esta é agora unha fila, en vez de unha pila, a diferenza ser-así como a cola de almacenamento de Apple é xusto. A primeira persoa en liña no inicio da lista, o número 5, neste caso, el ou ela vai quedar na primeira tenda. Imos facelo. Supoñamos que este é o estado da miña cola neste momento no tempo, e agora a tenda de Apple Abre ea primeira persoa, número 5, é conducido para a tenda. ¿Como cambiar o cadro, agora que eu de-cola a primeira persoa na parte da fronte da liña? ¿Que é iso? >> [Estudante] Cambiar a cola. Cambiar a cabeza, para 5 desaparece. En realidade, é coma se, a mellor forma de facelo? En realidade, é coma se este cara desaparece. Cal sería o número 7 facer nunha tenda real? Eles ían dar un gran paso cara a adiante. 

Pero o que temos benvida a apreciar cando se trata de matrices e mover as cousas? Isto é un desperdicio do seu tempo, non? Por que ten que ser tan anal como ter a primeira persoa no inicio da liña de física o inicio do bloque de memoria? Isto é completamente innecesario. Por que? O que eu podería só lembrar en vez diso? >> [Resposta do alumno inaudível] Exactamente, eu podería só lembrar con esta cabeza adicional membro de datos que agora o cabeza da lista non é 0, o que foi un momento atrás. Agora é realmente o número 1. Desta forma, recibín unha optimización leve. Só porque eu teño de-cola alguén de liña no inicio da liña na tenda de Apple non significa que todo o mundo ten que cambiar, que recall é unha operación lineal. Podo pasar o tempo en vez única constante e, a continuación, obter unha resposta moito máis rápida. Pero o prezo que eu estou pagando o que gañar ese adicional de desempeño e non ter que cambiar todos? Si >> [Resposta do alumno inaudível] Pode engadir máis persoas, así, o problema é ortogonal ao feito de que nós non estamos cambiando as persoas en todo. É aínda unha matriz para se imos ou non cambiar todos ou non oh, eu vexo o que quere dicir, todo ben. En realidade, eu estou de acordo co que está dicindo que é case como se nós nunca imos agora a usar o inicio desta matriz máis porque se eu eliminar 5, entón eu eliminar 7. Pero eu só poñer a xente cara á dereita. 

Parece que eu estou perdendo espazo e, finalmente, a miña cola se desintegra en nada, polo tanto, pode só ter contorno persoas, e podemos pensar desa matriz realmente como unha especie de estrutura circular, pero usamos o operador en C para facer este tipo de contorno? [Resposta do alumno inaudível] >> O operador módulo. Sería un pouco aburrido para pensar en como fai a envolvente, pero podería facelo, e nós poderiamos comezar a poñer as persoas no que adoitaba ser a fronte da liña, pero lembre-se con esta variable cabeza que a cabeza dunha liña realmente é. E se, en vez diso, o noso obxectivo, en última análise, non obstante, era para buscar números, como fixemos aquí no escenario con Anita, pero nós realmente queremos o mellor de todos os mundos? Queremos máis que sofisticación matriz permite porque queremos que a capacidade de crecer de forma dinámica a estrutura de datos. Pero nós non queremos ter que recorrer a algo que indicamos na primeira conferencia non era un algoritmo óptimo, o de procura lineal. Acontece que pode, de feito, alcanzar ou polo menos preto de tempo constante, en que alguén como Anita, se establece a estrutura de datos non ser unha lista ligada, a non ser unha pila, a non ser nunha cola, pode, en realidade, chegar a unha estrutura de datos que permite ver as cousas, mesmo modo, non só en números, o que chamamos tempo constante. 

E, de feito, mirando cara adiante, unha das serie de exercicios nesta clase é case sempre a implementación dun corrector ortográfico, que nós dámoslle algunhas palabras novo 150.000 ingleses eo obxectivo é cargar os a memoria e rapidamente ser capaz de responder ás preguntas do formulario é esta palabra soletrada correctamente? E sería realmente mamar se tivese que percorrer todos os 150 mil palabras para responder a iso. Pero, en realidade, nós imos ver que podemos facelo en tempo moi, moi rápido. E vai implicar algo implementación chamada táboa hash, e aínda que a primeira vista esa cousa chamada unha táboa hash vai imos acadar estes super-rápidas tempos de resposta, verifícase que hai, de feito, un problema. Cando chega a hora de implementar esta cousa chamada de novo, eu estou facendo iso de novo. Eu son o único aquí. Cando chega a hora de implementar esa cousa chamada unha táboa hash, Nós imos ter que tomar unha decisión. Cal debe ser esa cousa realmente ser? E cando comezamos a inserción de números para esta táboa hash, como é que imos para almacena-los de tal forma que pode levalos de volta o máis rápido que chegamos los? Pero imos ver antes de tempo que esta cuestión de Cando o aniversario de todos está na clase será moi pertinente. Acontece que nesta sala, temos algunhas centenas de persoas, así as posibilidades de que dous de nós teñen a mesma data de aniversario é probablemente moi elevado. E se houbese só 40 nós nesta sala? Cales son as posibilidades de dúas persoas que teñen a mesma data de aniversario? [Os alumnos] Máis do 50%. Si, máis do 50%. En realidade, eu aínda trouxo un gráfico. Acontece, e iso é realmente só un sneak preview- hai só 58 nós nesta sala, a probabilidade de dous de nós ter a mesma data de aniversario é moi alta, case o 100%, e que vai causar unha morea de dor para nós o mércores. 

Con iso dito, imos atrasar aquí. Vemo-nos o mércores. [Aplausos] [CS50.TV]