COLUMNA 1: Todo ben, entón que é CS50 Este é o fin de semana cinco. E lembrar que a última vez que comecei a ollar os datos máis chic estruturas que pasaron a resolver problemas, que comezaron a introducir novos problemas, pero a clave para este Era o tipo de rosqueamento que comezou a facer a partir de nó a nó. Entón, iso, por suposto, é unha lista vinculada illadamente. E por vinculada illadamente, É dicir, hai só un enrosque entre cada un destes nós. Acontece que pode facer máis chic cousas como listas dobremente ligadas en que ten unha frecha indo en ambas as direccións, o que pode axudar con determinadas eficiencias. Pero iso resolveu o problema? O problema é que isto resolve? Por que nós nos importa o luns? Por que, en teoría, se nós nos importa o luns? O que fai? 

Audiencia: Podemos redimensionar-lo dinamicamente. 

COLUMNA 1: OK, entón podemos redimensiona-lo dinamicamente. Ben feito tanto de ti. Así, pode cambiar o tamaño dinamicamente este estrutura de datos, mentres que unha matriz, recall, ten que saber un priori como espazo quere e se precisa de algo máis espazo, é tipo de fóra da sorte. Ten que crear unha matriz totalmente novo. Ten que mover os seus datos de un para o outro, finalmente, liberar o array antigo se pode, e despois continuar. Que só se sente moi caro e moi ineficiente, e en realidade pode ser. Pero iso non é todo de bo. Nós pagamos un prezo, o que era unha dos prezos máis obvios nós pagar usando unha lista ligada? 

Audiencia: Temos que usar dobre espazo para cada un. COLUMNA 1: Si, por iso necesitamos polo menos dúas veces máis espazo. En realidade, eu entender iso de imaxe incluso un pouco erro, porque no IDE CS50 en unha morea de moderno ordenadores, un punteiro ou un enderezo non é, de feito, catro bytes. É moi frecuentemente estes días oito bytes, os cales significa que a parte inferior máis rectángulos alí en realidade son unha especie de dúas veces máis grande como o que eu deseño, o que significa que está a usar tres veces máis tanto espazo como poderiamos ter outra forma. Agora, ao mesmo tempo, estamos aínda falando bytes, non? Non estamos necesariamente falando megabytes ou gigabytes, a non ser que esas estruturas de datos quedar grande. 

E por iso hoxe comezan a considerar como podemos explotar datos de forma máis eficiente en traxe dos datos se fai maior. Pero imos tratar canonizar as primeiras operacións que podes facer sobre estes tipos de estruturas de datos. Entón, algo así como un conectado lista soporta xeralmente Operacións como eliminar, introducir e buscar. E o que quero dicir con iso? Isto só significa que, xeralmente, se a xente está usando lista encadeada, eles ou alguén ten aplicado funcións como DELETE, INSERT, e busca, para que poida realmente facer algo útil coa estrutura de datos. Entón, imos dar un ollo rápida en como podemos aplicar algún código para unha lista ligada deste xeito. 

Polo tanto, este é só un código C, nin sequera un programa completo que realmente rápido empolada. Non é en liña na distribución de código, pois non han funcionar. Pero teña en conta Acaba cun comentario dixo, dot dot dot, hai algo alí, dot dot dot, algo alí. E imos só ollar para que as pezas son suculentos. Así, na liña tres, Recordamos que este é agora propuxemos declarando un nó último tempo, un destes obxectos rectangulares. Ten un int que imos chamar N, pero poderiamos chamalo de calquera cousa, e, a continuación, unha estrela nó struct chamada seguinte. E só para quedar claro, que segundo liña, en liña seis, o que é iso? O que está facendo por nós? Porque certamente parece máis críptica do que as nosas variables habituais. 

Audiencia: Faise pasar un. 

COLUMNA 1: Fai moverse máis dun. E para ser máis preciso, ha almacenar o enderezo do nodo que está destinado a ser semanticamente próximo a el, non? Por iso, non vai necesariamente mover calquera cousa. El só vai almacenar un valor que é será a dirección dalgún outro no, e é por iso que nós dixemos struct estrela no, a estrela denotando un punteiro ou un enderezo. OK, entón agora se asumir que temos N esta dispoñible para nós, e imos supoñer que alguén ten insire unha morea de números enteiros nunha lista ligada. E esa lista ligada é apuntada por algún punto un chamado lista de variables que se pasou aquí como un parámetro, como fago para ir sobre a liña 14 execución de investigación? Noutras palabras, se eu estou aplicando función cuxo propósito na vida é tomar un int e, a continuación, o comezando dunha lista ligada, que é un enlace á lista encadeada. Como primeiro, que eu creo que David foi o noso voluntario o luns, estaba a apuntar cara toda ligada a lista, é coma se nós estamos pasando David en como o noso argumento aquí. Como é que imos atravesar esta lista? Ben, resulta que, a pesar de punteiros son relativamente novo para nós agora, podemos facelo relativamente directamente. 

Eu estou indo a ir adiante e declarar unha variable temporal que por convención é só ir a ser chamado de punteiro, ou PTR, pero podería chamalo de calquera cousa que sexa. E eu estou indo a iniciar Lo para o inicio da lista. Así, pode tipo de pensar neste como o profesor me o outro día, tipo de apuntando para alguén entre os nosos seres humanos como voluntarios. Entón, eu son unha variable temporal que é só apuntando para o mesmo que a nosa coincidentemente chamado voluntario David tamén estaba apuntando. Agora, mentres punteiro é non nulo, porque recordo que nulo é un valor especial sentinela o demarca o fin da lista, así, mentres eu non estou a apuntar cara a terra como a nosa última voluntario era, imos adiante e faga o seguinte. Se pointer-- e agora eu medio que quero para facer o que fixemos co alumno structure-- se punteiro punto próximo equals-- vez, se é igual a N punteiro punto é igual á variable n, a argumento que foi transmitido, entón eu quero ir adiante e dicir return true. Eu atopei o número N dentro un dos nós da miña lista ligada. Pero o punto deixa funciona neste contexto, porque punteiro, PTR, é de feito, un punteiro, un enderezo, realmente podemos marabillosas Finalmente usar unha peza de sintaxe este tipo de marcas sentido intuitivo e, de feito, usar unha frecha aquí, o que significa ir de este enderezo ao número enteiro alí dentro. Polo tanto, é moi semellante en espírito ao operador punto, senón porque punteiro non é un punteiro e non unha struct en si real, nós só usar a frecha. 

Polo tanto, se o nodo actual que eu, o variable temporal, estou apuntando para non é N, o que quero facer? Ben, cos meus voluntarios humanos que tivemos aquí o outro día, o meu primeiro ser humano non é o que eu quere, e quizais o segundo humano non é o que quero, eo terceiro, I precisa para manterse fisicamente en movemento. Como como fago para percorrer unha lista? Cando tivemos un array ti, só fixen como eu plus plus. Pero, neste caso, pode facer punteiro, queda, punteiro, a continuación. Noutras palabras, o campo seguinte é como todas as mans esquerda que os nosos voluntarios humanos o luns estaban a usar para ligar a algún outro nodo. Aqueles eran os seus veciños próximos. 

Entón, se eu queira pasar por esta lista, Non podo simplemente facer eu plus plus máis, Eu teño que dicir, en vez I, punteiro, vai para igualar calquera que sexa o campo seguinte é, O seguinte campo, o campo seguinte é, seguindo todas esas mans esquerdas que tivemos no escenario ligazón para algúns valores seguintes. E se eu pasar Toda esa iteración, e, finalmente, eu bati nulo non N atopou aínda, eu só retornar falso. Entón, de novo, todo o que estamos facendo aquí, segundo a imaxe dun momento atrás, comeza por apuntar á inicio da lista presuntamente. E entón eu vaia, é o valor Estou buscando igual a nove? Se é así, volvo verdade e eu son feito. Se non, eu actualizar miña man, Punteiro AKA, para apuntar a localización da próxima frecha e, a continuación, a localización próxima da frecha, e no próximo. Estou simplemente camiñando a través desta matriz. 

Entón, de novo, quen lle importa? Como o que é este un ingrediente para? Ben, lembre que introducimos a noción de unha pila, que é un tipo abstracto de datos na medida en que é non é unha cousa C, non é unha cousa CS50, é unha idea abstracta, esa idea de empilhado cousas enriba da outra que pode ser aplicado en acios de xeitos diferentes. E un xeito que propuxemos foi con unha matriz, ou cunha lista ligada. E parece que canonicamente, unha pila soporta, polo menos, dúas operacións. E as palabras de zumbido son pulo, para empurrar algo para a pila, como unha nova bandexa no comedor, ou pop, o que significa que para eliminar o máis alto bandexa do conxunto na cea hall, e entón pode que algúns así como outras operacións. Entón, como podemos definir a estrutura que agora estamos chamando unha pila? 

Ben, temos todo o requisite sintaxe á nosa disposición en C. Eu digo, me dea unha definición de tipo de unha estrutura dentro dunha pila, Eu vou dicir é un array, dun todo morea de números e logo tamaño. Polo tanto, noutras palabras, se eu queira para aplicar tanto no código, Déixame ir só unha especie de deseñar o que se di. Polo tanto, este está dicindo, me dea un estrutura que ten unha matriz, e eu non sei o que é capacidade, é aparentemente algunha constante que eu teño definido noutro lugar, e iso é bo. Pero supoño que non é máis que un, dous, tres, catro, cinco. Así, a capacidade é de 5. Este elemento dentro da miña estrutura serán chamados números. E entón eu teño un outra variable aparentemente chamado tamaño que inicialmente eu vou estipular é inicializar a cero. Se non hai nada en a pila, o tamaño é cero, e os seus valores de lixo en números. Eu non teño idea o que está aí aínda. 

Entón, se eu quero empurrar algo na pila, supoñamos que eu chamo de impulso función, e Digo empurrar 50, como o número 50, onde proporía Eu deseña-lo nesa matriz? Hai cinco diferentes respostas posibles. Onde queiras empurrar o número 50? O obxectivo aquí, unha vez máis, chamar a pulo función, pasa un argumento de 50, onde podo poñelas? Cinco possible-- 20% de posibilidades de adiviñar correctamente. Si? 

Audiencia: Extrema-dereita. 

COLUMNA 1: Extrema-dereita. Existe agora unha oportunidade de 25% de adiviñar correctamente. De xeito que sería realmente bo. Por convención, eu vou dicir cunha matriz, que sería normalmente comezar á esquerda, pero poderiamos certamente comeza pola dereita. Entón, o alerón aquí sería eu son probablemente, vai deseña-lo á esquerda, así como nunha matriz normal, onde Eu comezo a ir á esquerda cara á dereita. Pero se pode virar aritmética, todo ben. Non é só convencional. OK, eu teño que facer unha máis cambios aínda. Agora que eu empurre algo para a pila, o que está preto? 

Todo ben, eu teño que aumentar o tamaño. Entón deixe-me ir adiante e só actualizar esta, que era igual a cero. E, no canto agora, eu vou para poñer por valor de un. E agora supoño que eu empurre outro número na pila, como 51. Ben, eu teño que facer unha cambio, que é ata o tamaño dous. E entón supoño que empurrar unha número na pila como 61, agora eu teño actualizar o tamaño unha tempo, e obter o valor 3 como o tamaño. E agora supoño que eu chamo pop. Agora pop, por convención, Non é preciso un argumento. Cunha pila, o conxunto punto da metáfora bandexa é que non ten poder discreccionario para ir buscar a bandexa, todo o que pode facer é pop o máis alto dunha pila, só porque. Iso é o que esta estrutura de datos fai. 

Entón, por que a lóxica si dicir pop, o que sae? Entón, 61. Entón, o que realmente é o ordenador vai facer na memoria? Que o meu código ten que facer? Que proporía nós cambiamos a pantalla? O que debe cambiar? Sentímolo? Por iso, se librar de 61. Entón eu sempre podo facelo. E eu me podo librar de 61. E entón o que os outros cambio ten que ocorrer? Tamaño, probablemente, ten que volver para dous. E así todo ben. Pero agarde un minuto, tamaño un momento atrás tiña tres anos. Nós só facer unha verificación de sanidade rápida. Como é que sabemos que nos quería desfacerse de 61? Porque estamos estalado. E entón eu teño esta segunda tamaño da propiedade. 

Agarde un minuto, estou pensar de volta para a segunda semana cando comezamos a falar arrays, onde este foi lugar de cero, este foi un lugar, este foi localización dous, este é o lugar de tres, catro, parece que o relación entre o tamaño eo elemento que quero eliminar desde a matriz parece ser só o que? Tamaño menos un. E foi así que, como seres humanos sabemos que 61 ven en primeiro lugar. Como está o ordenador vai saber? Cando o seu código, onde probablemente quere facer o tamaño menos un, Así, tres menos un é dous, e que significa que queren se librar de 61. E entón podemos realmente actualizar o tamaño de xeito que o tamaño agora vai desde tres a só dous. E só para ser pedante, eu vou a propoñer que eu son feito, non? Vostede proposto intuitivamente correctamente debería librarse de 61. Pero non ten que tipo de tipo de libro de 61? Eu efectivamente esquecido que é realmente alí. E creo que volta a PSet4, se leu o artigo sobre forense, o PDF que tiñamos vostedes ler, ou vai ler esta semana para PSet4. Lembre que este é realmente pertinente para toda a idea de computación forense. O que un ordenador fai é xeralmente simplemente se esquece de onde algo é, pero non ir e como tentar risco-lo fóra ou substitución eses bits con ceros e uns ou algún outro estándar chou a non ser que mesmo facelo deliberadamente. Así, a súa intuición estaba ben, imos nos librar de 61. Pero, en realidade, non ten que se preocupar. Nós só necesitamos esquecer que está alí cambiando noso tamaño. 

Agora hai un problema con esta pila. Se eu continuar presionando as cousas para a pila, o que é obviamente, vai pasar en só algúns momentos do tempo? Nós imos quedar sen espazo. E o que imos facer? Estamos tipo de rosca. Esta aplicación non deixa nos redimensionar a matriz, porque usar esta sintaxe, se creo que volta a dúas semanas, xa que declarou o tamaño dunha matriz, nós non vimos aínda un mecanismo onde pode cambiar o tamaño da matriz. E, de feito C non ten este recurso. Se di que me dar cinco Nths, chamalos de números, iso é todo o que está indo para obtelo. Entón, o que facemos agora como de luns ten a capacidade de expresar unha solución porén, só necesitamos axustar a definición da nosa pila a menos algúns matriz codificados, pero só para almacenar un enderezo. 

Agora, por que é isto? Agora só temos que estar cómodo con o feito de que cando o meu programa é executado, Eu estou indo a presuntamente ten que preguntar o ser humano, cantos números que quere almacenar? Así, a entrada ten que vir de algures. Pero xa sei que número, entón podo só usar o que traballa para dar me unha peza de memoria? Podo usar malloc. E podo dicir calquera número de bytes Quero voltar estes Nths. E todo o que teño para almacenar os números variable aquí dentro deste struct debe ser o que? O que realmente vai ao números nese escenario? É un punteiro para o primeiro byte dese anaco de memoria, ou máis especificamente, a dirección do primeiro destes bytes. Non importa se é un bytes ou mil millóns de bytes, Só se preocupe co primeiro. Porque o que malloc e garantías miñas garantías do sistema operativo, é que o anaco de memoria I obter, que vai ser contiguos. Non vai ser lagoas. Entón, se eu pedín a 50 ou bytes 1.000 bytes, están todos indo a ser back to back to back. E desde que eu recordo como gran, como Eu pedín moito, todo o que precisa saber é o primeiro tal dirección. 

Polo tanto, agora temos a capacidade de código. Aínda que, iso vai levar máis tempo para escribir isto, poderiamos agora recolocar que a memoria por só almacenar un enderezo diferente alí se queremos unha maior ou mesmo unha peza menor de memoria. Entón aquí para atopar un compromiso. Agora temos dinamismo. Aínda temos contiguidade estou afirmando. Porque malloc daranos unha peza contiguo de memoria. Pero iso vai ser unha dor no o pescozo para nós, o programador, para realmente codificar. É só máis traballo. Necesitamos código semellante ao que eu era batendo fóra só un momento atrás. Moi factible, senón que engade complexidade. E así creador tempo, programador o tempo é aínda outro recurso para que puidésemos necesita gastar moito tempo para obter novas características. E despois, claro, hai unha fila. Non imos entrar nese un en moi detalle. Pero é moi semellante en espírito. Podería aplicar unha cola, e súas operacións correspondentes, enqueue ou dequeue, como engadir ou eliminar, é só unha forma de dicilo máis chique, enfileiramento ou desenfileirar, como segue. Só podo darme un struct que de novo ten matriz dun número, que de novo ten un tamaño, Pero por que eu teño agora para manter o control da cabeza dunha fila? Non teño que saber a cabeza da miña stack. Ben, se eu volver á queue-- imos duro codifica-lo como tendo como cinco enteiros en aquí potencialmente. Polo tanto, este é cero, un, dous, tres, catro. Este será números chamados de novo. E iso vai ser chamado de tamaño. 

Por que non é suficiente ter só o tamaño? Ben, imos empurrar os mesmos números por diante. Entón eu pushed-- I enfileirado, ou empurrado. Agora eu vou enfileirar 50, e, a continuación, 51, e despois 61, e Dot Dot Dot. Entón, iso é enqueue. I enfileirados 50, despois 51, despois 61. E iso parece idéntico para unha pila de momento, só que eu teño que facer un cambio. Necesito actualizar ese tamaño, entón eu ir de cero a un de dous a tres agora. ¿Como retirar da cola? Que pasa con dequeue? Quen debe saír esta lista primeiro se é a liña na tenda de Apple? Entón, 50. Entón é medio complicado desta vez. Considerando última vez que foi super doado simplemente facer o tamaño menos un, Chegar ao final da miña matriz efectivamente onde as cifras son, el elimina 61. Pero eu non quero eliminar 61. Quero ter 50 anos, que estaba alí na 5:00 para a liña para o novo iPhone ou outros enfeites. E así se librar de 50, I Non pode simplemente facelo, non? Podo atravesar a 50. Pero nós só dixo que Non ten que ser tan anal como a risco ou ocultar os datos. Podemos simplemente esquecer onde está. 

Pero se eu cambiar o meu tamaño agora dous, é esta información suficiente para saber o que está a suceder na miña cola? En realidade non. Así como o meu tamaño é dous, pero onde é que a cola de comezar, especialmente se eu teño eses mesmos números na memoria. 50, 51, 61. Entón, eu teño lembrar Agora, onde a cabeza é. E así como eu propuxen a alí, nós imos ter chamado só Fronte nth, cuxa inicial valor debe ser o que? Cero, só o comezo da lista. Pero agora, ademais de decrementing o tamaño, nós só incrementar a fronte. Aquí está outro problema. Entón, cando eu sigo indo. Supoñamos que este é o número de como 121, 124, e, a continuación, caramba, Estou fóra do espazo. Pero agarde un minuto, eu non son. Entón, neste punto da historia, supoñamos que o tamaño é un, dous, tres, catro, de forma que o supor tamaño é catro, a fronte é un, para 51 é a parte da fronte. Quero poñer outro número aquí, pero, caramba, eu estou fóra do espazo. Pero eu non son realmente, non? Onde eu podería poñer algún valor adicional, como 171? Si, eu podería só unha especie de volver para alí, non? E, a continuación, atravesar a 50, ou só substituílo con 171. E se está a se pregunta por nosos números quedou tan aleatorio, estes adoitan ser tomadas ordenador cursos de ciencias en Harvard tras CS50. Pero iso foi unha boa optimización, porque agora eu non estou perdendo espazo. Eu aínda teño que lembrar o grande esa cousa é total. É cinco totais. Porque eu non quero comezar a substituír 51. Entón agora eu estou sen espazo, de xeito que o mesmo problema de antes. Pero se pode ver como agora no seu código, probablemente ten que escribir un pouco máis complexidade para que isto ocorre. E, de feito, o operador en C probablemente permite vostede Magic facelo a circularidade? Si, o operador módulo, o sinal de porcentaxe. Entón, o que é legal sobre unha fila, aínda que manter matrices deseño como estas liñas rectas como, se tipo de pensar sobre iso como encurvamento en torno a como un círculo, a continuación, pode intuitivamente que tipo de obras mental Eu creo que un pouco máis limpa. Aínda tería que aplicar que modelo mental no código. Entón, non é difícil, en definitiva, para aplicar, pero aínda perder o size-- vez, o capacidade de cambiar o tamaño, a menos que fagamos isto. 

Debemos librar-se da matriz, nós substituílo por un único punteiro, e, a continuación, en algún lugar no meu código que teño a chamar o que funciona para realmente crear a matriz de números chamados? Malloc, ou algunha similar función, exactamente. Calquera preguntas sobre pilas ou filas. Si? Boa pregunta. Cal módulo usaría aquí. Así, en xeral, cando se utiliza mod, faría iso co tamaño do estrutura enteira de datos. Entón, algo así como cinco ou capacidade, se é constante, está probablemente parte. Pero só facendo modulo cinco probablemente non é suficiente, porque necesitamos saber é que nós participa en torno de aquí ou aquí ou aquí. Entón probablemente está tamén Vai querer involucrarse o tamaño da cousa, ou a variable fronte tamén. Entón é só iso relativamente expresión aritmética simple, pero módulo sería ingrediente clave. 

Entón, curtametraxe se quere. Unha animación que algúns pobos noutra universidade xuntos que temos adaptado para este fío. Trátase de aprender a Jack feitos sobre filas e estatísticas. 

PELÍCULA: Había unha vez, había un cara chamado Jack. Cando el veu para facer amigos, Jack non ten un talento especial. Entón Jack foi falar co máis cara popular que coñecía. Foi para Lou e preguntou: O que fago? Lou viu que o seu amigo foi moi angustiado. Ben, el comezou, só mira como está vestida. Non ten ningunha roupa cunha mirada diferente? Si, dixo Jack. Eu seguramente facer. Veña á miña casa e Eu vou amosar a vostede. Entón, eles foron para Jack. Jack e Lou mostrou a caixa onde gardaba as súas camisas, e os pantalóns e as medias. Lou dixo, eu vexo que ten todas as súas roupas nunha pila. Por que non usar algún outros de cando en vez? 

Jack dixo, ben, cando eliminar roupa e medias, Eu lava-los e colocá- Los no cadro. A continuación, vén o seguinte mañá, e se eu pulo. Ir á caixa e obter miñas roupas fóra do cumio. Lou entendeu rapidamente O problema con Jack. El mantivo roupa, CDs, e libros na pila. Cando chegou a algo para ler ou para levar, el escollería o cumio libro ou roupa interior. Entón, cando se fixo, el ía poñer-lo de volta. Volver sería ir, na parte superior do conxunto. Sei a solución, dixo un alto triunfante. Debe aprender a comezar a usar unha cola. Lou colleu roupa de Jack e colgou os no armario. E cando baleirara a caixa, simplemente xogouse a. 

Entón el dixo, agora Jack, a finais de o día, poñer a roupa na parte esquerda cando poñer-los fóra. Entón, mañá pola mañá cando ver a luz do sol, incorporarse a roupa á dereita, a partir da extremidade da liña. Non ve? dixo Lou. Que vai ser tan bo. Vai empregar todo xa antes de usar algo dúas veces. E con todo en filas no seu armario e andel, Jack comezou a sentirse moi seguro de si. Todo grazas a Lou e súa marabillosa cola. COLUMNA 1: Todo ben, é encantador. Entón, o que foi realmente a suceder por baixo do capuz agora? Que temos punteiros, que temos malloc, que temos a capacidade de crear anacos de memoria para nós mesmos dinamicamente. Polo tanto, esta é unha imaxe que vislumbrada só o outro día. Nós realmente non habitará sobre el, pero esta imaxe foi pasando por baixo o capó hai semanas. E así que representa, só un rectángulo que temos deseñado, a memoria do seu ordenador. E quizais o seu ordenador, ou CS50 ID, ten un gigabyte de memoria RAM ou ou dous gigabytes ou catro. Realmente non importa. O seu sistema operativo Windows ou Mac OS ou Linux, esencialmente permite que o programa pensando que ten acceso para o conxunto do a memoria do seu ordenador, aínda que pode estar executando varios programas á vez. Entón, en realidade, que realmente non funciona. Pero é tipo de unha ilusión dado a todos os seus programas. Entón se tivese dous gigas de memoria RAM, este É así que o ordenador pode pensar niso. 

Agora coincidentemente, un deles cousas, un deses segmentos de memoria, chámase unha pila. E, de feito calquera momento ata agora en escribir código que ten chamado a función, por exemplo principal. Lembre que en calquera momento eu teño memoria tirada do ordenador, Sempre deseñar tipo de metade dun rectángulo aquí e non se incomoda de falar sobre o que está enriba. Porque cando principal chámase, eu reivindico que comeza este anaco de memoria que vai para abaixo aquí. E se unha función principal chamada como intercambio, así cambio vai aquí. E ao parecer, iso é onde acaba. En algo chamado unha pila dentro da memoria do seu ordenador. Agora, ao final do día, este é só aborda. É como byte cero, byte un, byte 2 millóns. Pero se pensar sobre iso como este obxecto rectangular, todo o que estamos facendo cada xa que chamar a unha función é estratificación unha nova porción de memoria. Estamos dando esa función dunha porción da súa propia memoria para traballar. 

E lembro agora que isto é importante. Porque se temos algo así como intercambio e dúas variables locais como A e B e podemos cambiar estes valores a partir de un e dous para dous e un, Lembre que cando retorna permuta, é coma se esa porción de memoria é só ir. En realidade, aínda é hai forense. E algo aínda está realmente alí. Pero conceptualmente, é como aínda é completamente desaparecido. E así principal non sabe calquera dos traballos que se fixo nesa función de intercambio, a non ser que sexa realmente pasou naqueles argumentos de punteiro ou por referencia. Agora, a solución fundamental para este problema con permuta está pasando por cousas no enderezo. Pero ao parecer, tamén, o que é vén acontecendo enriba que parte do rectángulo de todo este tempo é Aínda hai máis memoria alí enriba. E cando dinamicamente reservar a memoria, se é dentro GetString, que temos está a facer para ti no CS50 biblioteca, ou se vostedes chamar malloc e pedir o sistema operativo para unha peza de memoria, non vén do conxunto. Vén doutro lugar na memoria do seu ordenador que se chama de datos dinámicos. E iso non é diferente. É a mesma memoria RAM. É a mesma memoria. É só a memoria RAM que está por riba alí en vez de baixar aquí. 

E entón o que é que iso significa? Ben, se o ordenador ten unha cantidade finita de memoria ea pila é evidente, entón para falar, ea pila, segundo para esta frecha, é evidente para abaixo. Noutras palabras, cada vez que chamar malloc, está a ser dada unha porción de memoria dende arriba, a continuación, se cadra un pouco máis abaixo, entón un pouco inferior, cada vez que chamar malloc, a pila, é o uso, é unha especie de crecemento, crecendo cada vez máis preto para o que? A pila. Entón, iso parece ser unha boa idea? Quero dicir, onde non é moi claro o que máis pode facer se só ten unha cantidade finita de memoria. Pero este é certamente mal. Esas dúas frechas están nun Crash Course un polo outro. 

E parece que cara mal, persoas que son particularmente bos coa programación, e tentando invadir ordenadores, Pode explotar esa realidade. De feito, imos considerar un pequeno fragmento. Polo tanto, este é un exemplo que pode ler con máis detalle na Wikipedia. Nós imos sinala-lo no artigo curioso. Pero hai un ataque xeral coñecido como buffer overflow que existiu durante o tempo que o ser humano ter a capacidade de manipular a memoria do ordenador, especialmente en C. Polo tanto, este é un programa moi arbitraria, pero imos lelo desde abaixo. Principal en ARGC carbón estrela argv. Polo tanto, é un programa que tira argumentos de liña de comandos. E todo principal é que, ao parecer, é chamada unha función, chamalo F pola simplicidade. E pasa que? Argv dun. Entón, el pasa a que quere que F a palabra é que o usuario introduciu no poder tras a nome do programa en todo. Tanto como César ou Vigenère, que pode lembrar facendo argv. 

Entón, o que é F? F leva nunha cadea como o seu único argumento, AKA unha estrela char, mesmo cousa, como unha cadea. E é chamado arbitrariamente bar neste exemplo. E despois de char c 12, só en termos leigos, o que é char c soporte de 12 facendo por nós? O que fai? A distribución de memoria, especialmente 12 bytes para 12 caracteres. Exactamente. E entón a última liña, mexa e copia, probablemente non vin. Esta é unha copia cadea función cuxo propósito na vida é copiar o seu segundo argumento no seu primeiro argumento, pero só ata un número de bytes. Así, o terceiro argumento di, cantos bytes ten que copiar? A lonxitude da barra, todo o que o usuario escribiu. E os contidos de Bar, esa secuencia, son copiada á memoria apuntada para a C. 

Entón, iso parece medio idiota, e é. É un exemplo artificial, pero é representante dunha clase de vectores de ataque, unha forma de atacar un programa. Todo está ben e bo se o usuario tipo nunha palabra que é 11 caracteres ou menos, máis a barra invertida cero. E se o usuario escribe en máis de 11 ou 12 ou 20 ou 50 caracteres? ¿Que é este programa vai facer? Fallo potencialmente seg. Vai para copiar cegamente todo no bar-se á súa lonxitude, que é literalmente todo o bar, ao enderezo sinalado polo C. Pero C só cautelarmente dada como 12 bytes. Pero non hai ningunha verificación adicional. Non hai ningún caso as condicións. Non hai ningunha verificación de erros aquí. 

E entón o que este programa é vai facer é só cega copiar algo á outra. E así se deseñar ese como unha imaxe, é aquí só unha pequena parte do espazo de memoria. Entón, observe no fondo, nós teñen o bar variable local. Entón, ese punteiro que store-- xa que o argumento local que é indo para almacenar a barra de cadea. A continuación, teña en conta só enriba dela nunha pila, porque cada vez que preguntar para memoria na pila, vai un pouco anterior, pictorially, aviso de que temos 12 bytes alí. A de arriba esquerda é cero e soporte C o certo é inferior C soporte 11. Isto é só a forma como os ordenadores indo para poñelas fóra. Entón, só intuitivamente, se bar ten máis de 12 caracteres en total, incluíndo a barra invertida cero, onde está o 12 ou o soporte de C 12 indo a ir? Ou mellor, onde é o 12º personaxe ou o personaxe 13th, o personaxe vai centésimo para acabar na imaxe? Arriba ou abaixo? 

Seguro, porque aínda a propia pila crece cara arriba, unha vez que poñer as cousas en el, por razóns de deseño, pon a memoria de arriba abaixo. Entón, se ten máis de 12 bytes, vai comezar a substituír bar. Agora que é un erro, pero é non é realmente un gran negocio. Pero é un gran negocio, porque hai máis cousas a suceder na memoria. Entón aquí está como nós puidemos poñer Ola, para ser claro. Se eu escriba Ola no poder. Barra invertida cero, H-E-L-L-O, acaba por dentro eses 12 bytes, e estamos super seguro. Todo está ben. Pero se eu escribir algo máis longo, que é potencialmente vai rastexaren para o espazo bar. Pero peor aínda, parece se fóra todo este tempo, aínda que nunca falamos sobre que, a pila é usada para outras cousas. Non son só as variables locais. 

C é unha linguaxe de nivel moi baixo. E que tipo de segredo utiliza tamén a pila para recordar cando un función é chamada, o que é a dirección da función anterior, así que pode ir de volta para esa función. Entón, cando as chamadas principais intercambiar entre as cousas empurrado para a pila non só cambio variables locais, ou os seus argumentos, tamén empurrou secretaría para a pila como representado pola porción vermello aquí, é a dirección do principal fisicamente na memoria do seu ordenador, de xeito que cando está feito de permuta, o ordenador sabe que eu teño para volver ao inicio e rematar de realizar a función principal. Entón, iso é perigoso agora, porque se o usuario escribe moito máis do que Ola, de tal xeito que a entrada do usuario clobbers ou substitúe esa sección vermello, loxicamente, se o ordenador só vai asumir cegamente en que os bytes que son porción vermello a dirección para o que debe retornar, e se o adversario é intelixente dabondo ou sorte o suficiente para poñer unha secuencia de bytes hai que se parece un enderezo, pero é a dirección de código que el ou ela quere o ordenador para realizar no canto de principal? 

Noutras palabras, se o que o usuario está escribindo no prompt, non é só algo como inocuo Ola, pero en realidade é un código que equivale borrar todos os ficheiros dese usuario? Ou enviar correo-e o contrasinal para min? Ou comezar a rexistrar a súa teclas escritas, non? Hai un camiño, imos estipular hoxe, que poderían escribir non só Ola mundo ou o seu nome, que podían esencialmente pasar en código, e ceros aqueles que o ordenador erros de código e un enderezo. Así, aínda que un pouco abstracto, o usuario escribe o código contraditorio suficiente que imos xeneralizar aquí como A. Unha é o ataque ou adversarios. Entón, só cousas malas. Non nos importa sobre a números ou os ceros ou aqueles hoxe, de tal forma que acaba sobrescrevendo esa sección vermello, notar que secuencia de bytes. O 835 C cero oito cero. E agora, como artigo de Wikipedia aquí propuxo, se realmente comezar agora rotular os bytes no seu ordenador de memoria, o que o artigo é Wikipedia propoñendo é que o que se a dirección de que byte superior esquerda é de 80 C 0 3508. 

Noutras palabras, se a cara é malo intelixente dabondo co seu código para realmente poñer un número aquí que corresponde ao enderezo do código el ou ela inxectado no ordenador, pode enganar o ordenador a facer calquera cousa. A eliminación de arquivos, correo electrónico cousas, rastrexando o seu tráfico, literalmente nada podería ser inxectado no ordenador. E así por un estourido de buffer ataque no seu núcleo é só un estúpido, estúpido imperiosa dunha matriz que non teñen os seus límites marcada. E iso é o que é super perigoso e á vez poderoso super en C é que realmente teñen acceso a calquera lugar da memoria. Cabe a nós, os programadores, que escriben o código orixinal para comprobar a lonxitude danado de calquera matrices que estamos manipulando. Entón, para ser claro, o que é a corrección? Se voltar a esta código, non debería só cambiar a lonxitude da barra, o que máis eu debería estar comprobando? O que máis debería estar facendo para evitar este ataque enteiramente? Non quero dicir só cega que ten que copiar como moitos bytes como é a lonxitude da barra. Quero dicir, como copiar moitos bytes como están en bar ata o asignado memoria, ou 12 como máximo. Entón eu teño algún tipo de condición if que fai comprobar a lonxitude da barra, pero se é superior a 12, nos código só difícil 12 como a distancia máxima posible. Se non, o chamado tapón ataque de estourido pode pasar. Na parte inferior das referidas láminas, Se está curioso para saber máis é a páxina orixinal real se quere dar un ollo. 

Pero agora, entre os prezos pago aquí foi ineficiencia. Así, foi un rápido ollar baixo nivel en que poden xurdir problemas agora que teñen acceso a memoria do ordenador. Pero outro problema que xa tropezou hoxe era só a ineficiencia dunha lista ligada. Estamos de volta ao tempo lineal. Xa non temos unha matriz contigua. Non temos acceso aleatorio. Non podemos usar a notación de paréntese. Nós, literalmente, ten que usar un loop while como a que escribín hai pouco. Pero o luns, que alegou que pudermos rastexaren ao seu reino de eficiencia alcanzar algo que é logarítmica quizais, ou mellor aínda, quizais mesmo algo que é o chamado tempo constante. Entón, como podemos facelo cos seus novos ferramentas, estes enderezos, estes punteiros, e enfiar cousas da nosa propia? Ben, supoñamos que aquí, estes son unha banda de números que queremos almacenar nun estrutura de datos de forma eficaz e de procura. Podemos absolutamente rebobinar a semana dous, xoga-los nunha matriz, e procura-los usando investigación binaria. Dividir e conquistar. E, de feito escribiu busca binaria en PSET3, onde aplicou o programa find. Pero vostede sabe o que. Hai unha especie de máis xeito intelixente de facelo. É un pouco máis sofisticado e quizais permítenos ver por binario busca é moito máis rápido. En primeiro lugar, imos introducir a noción dunha árbore. Que, aínda que en realidade tipo de árbores crecer como este, no mundo informático ciencia que tipo de crecer para abaixo como unha árbore de familia, onde ten seus avós ou bisavós ou outros adornos na parte superior, o patriarca e a matriarca da familia, só un chamada raíz, no, a continuación que son os seus nenos, debaixo da cal están os seus fillos, ou seus descendentes en xeral. E calquera que colga fóra a parte inferior da familia árbore, ademais de ser a caçula da familia, Tamén pode ser só xenericamente chamado as follas da árbore. 

Polo tanto, este é só unha banda de palabras e definicións para algo chamado dunha árbore no ordenador ciencia, así como unha árbore xenealóxica. Pero hai encarnações máis extravagantes de árbores, unha das cales é chamada unha árbore de busca binaria. E pode tipo de provocación ademais o que esa cousa fai. Ben, é binario en que sentido? Onde é que o binario vén aquí? Sentímolo? Non é tanto un ou. É máis que cada un de nós non ten máis de dous fillos, como vemos aquí. En xeral, unha tree-- seus pais e avós pode ter tantos fillos ou netos como realmente queren, e así, por exemplo, aí temos tres nenos fóra dese nodo man dereita, mais dunha árbore binaria, un nó posúe cero, un ou dous fillos maxima. E iso é unha propiedade agradable, Porque si é tapado por dous, nós imos ser capaces de estar un pouco rexistro base dous acción suceder aquí, en última instancia. Polo tanto, temos algo logarítmica. Pero máis sobre iso nun momento. Busca árbore significa que as cifras son disposto de tal xeito que o neno esquerda do valor é maior que a raíz. E o seu fillo dereito é maior que a raíz. Noutras palabras, se incorporarse calquera dos nós, os círculos nesta imaxe, e mira para a súa esquerda neno eo seu fillo dereito, o primeiro debe ser inferior a, o segundo debe ser maior que. Entón verificación de sanidade 55. É neno deixada é de 33. É menos que. 55, o seu fillo da dereita é de 77. É maior que. E iso é unha definición recursiva. Poderiamos comprobar cada un destes nós eo mesmo patrón ía realizar. 

Entón, o que é bo en un árbore de busca binaria, é este, podemos implementar lo cunha estrutura, como este. E aínda que estamos xogando lotes de estruturas na súa, son un pouco intuitiva agora esperanzas. A sintaxe é aínda misterioso, con certeza, pero o contido dun nodo nesta context-- e seguimos utilizando o no palabra, se é un rectángulo na pantalla ou un círculo, é só algúns contedores xenérico, Neste caso dunha árbore, como o vimos, necesitamos un número enteiro en cada un dos nós e entón eu teño dous punteiros apuntando para o fillo esquerdo e dereito do neno, respectivamente. Entón é así que nós puidemos aplicar isto nun struct. E como eu podería implementar lo en código? Ben, imos dar unha rápida mirar para este pequeno exemplo. Non é funcional, pero eu teño copiado e pegado esa estrutura. E se a miña función para un par árbore de busca é chamado de busca, e iso leva dous argumentos, un N de número enteiro e un punteiro para un nó, de xeito que un punteiro para a árbore ou un punteiro para a raíz dunha árbore, como fago para ir sobre como buscar N? Ben, en primeiro lugar, porque son xestionar punteiros, Vou facer unha proba de sanidade. Iguais árbore é igual a cero, é N nesta árbore ou non nesta árbore? Non pode ser, non? Se eu son pasado null, non hai nada alí. Podería moi ben só cegamente dicir return false. Se me der nada, eu certamente non podo atopar calquera número N. Entón, o que máis podería comprobar agora? Eu vou dicir ben else if N é menos que o que está no nó de árbore que teño valor N entregou. Noutras palabras, se o número son buscar, n, sexa menor que o nó que eu estou mirando. E o no que estou a buscar a árbore é chamado, e lembrar do exemplo anterior para obter o valor nun punteiro, Eu uso a notación de frecha. Polo tanto, se n é inferior a frecha árbore N, quero ir conceptualmente esquerda. Como podo expresar searching esquerda? Para ser claro, se este é a imaxe en cuestión, e eu teño que pasou de nivel superior arrow que está a apuntar cara a abaixo. Ese é o meu punteiro árbore. Estou a apuntar cara a raíz da árbore. E eu estou ollando por exemplo, para o número 44, de forma arbitraria. 44 é inferior ou superior a 55, obviamente ,? Polo que é menos que. E así este condición é aplicable. Así, conceptualmente, o que quero buscar seguinte se eu estou buscando 44? Si? 

Exactamente, quero buscar o fillo esquerdo, ou a sub-árbore á esquerda da imaxe. E, de feito, deixe-me a través de a foto aquí por só un momento, xa que Non podo rabuñar iso. Se eu comezar en 55, e Sei que o valor 44 Estou buscando é a á esquerda, é unha especie de como rasgar o libro de teléfono en metade ou rasgar a árbore no medio. Eu xa non se preocupe toda esta metade da árbore. E, con todo, curiosamente, en termos de estrutura, esta cousa aquí que iníciase coa 33, que se é unha árbore de busca binaria. Eu dixen a palabra recursiva antes porque De feito, esta é unha estrutura de datos que por definición é recursiva. Pode que unha árbore que é iso grande, pero cada un dos seus fillos representa unha árbore só un pouco menor. En vez de ser vovô ou a avoa, agora é só nai ou-- Non podo non dizer-- nai ou pai, que sería estraño. No canto das dúas nenos alí sería como irmán e irmá. A nova xeración de árbore xenealóxica. Pero estruturalmente, é a mesma idea. E resulta que eu teño unha función co cal podo buscar unha busca binaria árbore. El é chamado de busca. I buscar N na árbore frecha para a esquerda outro se n é maior que o valor que eu son actualmente. 55 na historia un momento atrás. Eu teño unha función chamada investigación que podo só N pasar iso e buscar de forma recursiva a sub-árbore e só retorno calquera que sexa a resposta. Outra cousa que eu teño algún caso base final aquí. 

¿Que é o caso final? Árbore ou é nulo. O valor que tanto estou buscando é menos que ou maior que aquela ou mesmo que o mesmo. E eu podería dicir igual igual, pero loxicamente é equivalente a só dicindo outra cousa aquí. Tanto é así como eu atopar algo. Polo tanto, esperamos que esta é unha mesmo exemplo máis atractivo que a función sigma estúpido fixemos algunhas conferencias atrás, onde era tan fácil de usar un loop para contar todos os números dun a N. aquí cunha estrutura de datos que en si é recursivamente definido e de forma recursiva deseñada, agora nós teñen a capacidade de nos expresarmos no código que en si é recursiva. Polo tanto, este é o mesmo código aquí. 

Entón, o que os outros problemas que podemos resolver? Entón, un paso rápido lonxe de árbores para só un momento. Aquí é, digamos, a bandeira alemá. E hai claramente un estándar para esta bandeira. E hai moita bandeiras do mundo que son tan sinxelo coma iso en termos das súas cores e patróns. Pero supoñamos que esta se garda como un .gif, Ou un JPEG ou bitmap, ou un ping, calquera formato de arquivo gráfico co que está familiarizado, algúns dos cales somos xogar con en PSet4. Isto non parece valer a pena para almacenar pixel negro, pixel negro, pixel negro, punto, punto, punto, unha morea de píxeles negros para a primeira liña de varrido, ou liña, a continuación, un grupo enteiro de a mesma, a continuación, un grupo enteiro do mesmo, e, a continuación, unha todo grupo de píxeles vermellos, píxeles vermellos, píxeles vermellos, a continuación, un todo puñado de píxeles amarelo, amarelo, non? 

Non hai tal ineficiencia aquí. Como é que intuitivamente comprimir a bandeira alemá se implementar lo como un arquivo? Como o que información pode non incomodar o almacenamento en disco en orde para diminuír o noso tamaño do arquivo de como un megabyte dun kilobyte, algo menor? Onde reside a redundancia aquí para ser claro? O que podería facer? Si? Exactamente. Por que non, no canto de se lembrar a cor de cada píxel danado así como está facendo en PSet4 co formato de arquivo de mapa de bits, por que non só representar a columna máis á esquerda de píxeles, por exemplo unha morea de píxeles negros, un grupo de vermello, e unha morea de amarelo, e despois é só algunha maneira codificar o idea de repetir este 100 veces ou repetir isto 1.000 veces? Onde é 100 ou 1000 só un número enteiro, para que pode comezar afastado con só un único número en vez de centos ou miles píxeles de adicionais. E, de feito, é así que podería comprimir a bandeira alemá. E Agora o que pasa coa bandeira francesa? E un pouco de calquera tipo de exercicio mental, que flag pode ser comprimida máis no disco? A bandeira alemán ou francés bandeira, se temos esa visión? A bandeira alemán, porque non hai máis redundancia horizontal. E polo deseño, moitos arquivos gráfico formatos de feito traballar como liñas de varrido horizontalmente. Poderían traballar vertical, basta humanidade anos decidiu que imos Xeralmente pensamos en cousas fileira por liña en vez de columna por columna. Entón, en realidade, se fose mirar para o ficheiro tamaño dunha bandeira alemá e unha francesa bandeira, sempre que a resolución é o mesmo, o mesmo ancho e altura, este aquí vai ser maior, porque ten que repetir-se tres veces. Ten que especificar azul, repita Se, branco, repita a, vermello, repetirse. Non pode simplemente ir todo o camiño para a dereita. E como unha banda, para facer desmarque a compresión está en todas partes, se estas son catro cadros dunha video-- vostede que lembrar que unha película ou de vídeo é xeralmente como 29 ou 30 cadros por segundo. É como un pouco flip book, onde basta ver imaxe, imaxe, imaxe, imaxe, imaxe só super rápido así que mira como os actores na pantalla están movendo. Aquí está unha abella do bumble en encima dun ramo de flores. E aínda que poida ser unha especie de difícil de ver a primeira vista, o único que se desprazan en esta película é a abella. 

¿Que é mudo sobre o almacenamento vídeo sen comprimir? É unha especie de un desperdicio para almacenar vídeo como catro imaxes que case idénticos difiren só na medida en que a abella é. Pode xogar fóra máis de que a información e lembre-se só, por exemplo, o primeiro cadro eo último cadro, cadros clave se Xa escoitou a palabra, e só almacenar no medio, onde a abella é. E non ten que almacenar todo o rosa, eo azul, ea valores verdes tamén. Polo tanto, esta é só a dicir que compresión está en todas partes. É unha técnica miúdo usan ou exame para concedida nestes días. 

Pero como comprimir texto? Como vai facer sobre a compresión de texto? Ben, cada un dos personaxes en Ascii é un byte, ou oito bits. E iso é medio idiota, non? Porque probablemente tipo A e E e I e O e U moi máis veces que como W ou Q ou Z, dependendo do idioma en que está escribindo certamente. E entón por que estamos usando oito bits para cada letra, incluíndo a menos letras populares, non? Por que non usar menos bits para as letras super popular, E como, as cousas que adiviñar por primeira vez en Wheel of Fortune, e utilizar máis bits para as letras menos populares? Por que? Porque só estamos indo a usalos con menos frecuencia. 

Ben, resulta que non teñen intentos de facelo foi. E se se lembra de grao escola ou colexio, código Morse. Código Morse ten puntos e trazos que se pode transmitido ao longo dun fío conforme sons ou signos de calquera tipo. Pero o código Morse é un super limpo. É unha especie de un sistema binario en que ten puntos ou trazos. Pero se ver, por exemplo, dous puntos. Ou se pensas que ao seu operador que vai como bip, bip, bip, Campá, acadando un pouco gatillo que transmite un sinal, se, o destinatario recibe dous puntos, que a mensaxe que recibiu? Completamente arbitraria. 

I? I? Ou o que about-- ou eu? Quizais fose só dous á dereita de E? Polo tanto, non hai ese problema de Desencriptación con Morse código, por medio de que a non ser que o persoa que enviou a mensaxe de feito, fai unha pausa para que poida clasificar de ver ou escoitar as lagoas entre as letras, non é suficiente só para enviar un fluxo de ceros e uns, ou puntos e trazos, porque non hai ambigüidade. E é un único punto, polo que, se ver dous puntos ou escoitar dous puntos, quizais sexa dous e de ou que sexa unha I. Entón, necesitamos un sistema que é un pouco máis intelixente do que iso. Entón un home chamado Huffman anos atrás veu con exactamente isto. Entón, nós só estamos indo para tomar un rápido ollar o xeito no que as árbores son pertinentes a esta. Supoña que esta é unha estúpido mensaxe que desexe enviar, composto por só A, B, C de D's e E do, pero hai unha morea de redundancia aquí. Isto non debería ser inglés. Non e criptografía. É só unha mensaxe estúpida con moita repetición. Entón, se realmente contar para fóra toda a A, B de, C de, D's, e E de aquí está a frecuencia. 20% do que as letras son Un, 45% das cartas E son de, e outros tres frecuencias. Contamos alí enriba manualmente e só fixo as contas. 

Así, verifícase que Huffman, hai algún tempo, entender que, vostede sabe o que, se eu comezar a construír unha árbore ou bosque de árbores, se quixeren, do seguinte xeito, eu podo facer o seguinte. Vou dar un nó para cada das cartas que me interesa e eu estou indo para almacenar dentro dese nodo as frecuencias como un punto flotante valor, ou pode usalo unha N, tamén, pero imos só usar un flotador aquí. E que o algoritmo el propuxo é que aproveitar esta bosque de nó único árbores, árbores tan super curtas, e comezar a conectar-los con novos grupos, pais novos, se quere. E facelo escollendo o dous menores frecuencias á vez. Entón, eu levei o 10% e 10%. Eu crear un novo nodo. E eu chamo o novo nó de 20%. 

Que dous nós Eu combino o próximo? É un pouco ambigua. Polo tanto, hai algúns casos canto para considerar, pero para manter as cousas ben, Vou escoller 20% - Eu agora ignorar os nenos. Vou escoller un 20% e 15% e deseñar dúas novas arestas. E agora que dous nós eu loxicamente combinar? Ignorar todos os nenos, as netos, basta ollar para as raíces agora. Que dous nós podo amarre xuntos? Punto dous e 0,35. Entón deixe-me deseñar dúas novas arestas. E entón eu teño só un á esquerda. Entón aquí está unha árbore. E deseñada deliberadamente ollar tipo de bonito, de ter en conta que as arestas teñen Tamén foi marcado cero e un. Así, todas as beiras esquerdas son cero arbitrariamente, senón de forma consistente. Todas as beiras dereitas son queridos. 

E entón o que Hoffman proposta é, se quere representar un B, en vez de representar o número 66 como un ASCII que é oito bits enteiros, Vostede sabe o que, exactamente tenda o estándar cero, cero, cero, cero, porque ese é o camiño da miña árbore, árbore do Sr Huffman, para a folla a partir da raíz. Se desexa almacenar unha E, por outra banda, non facer enviar oito bits que representan un E. Pola contra, enviar o estándar de bits? Unha. E o que é agradable sobre esta é que e é a letra máis popular, e está a executar o código máis curto para el. O seguinte máis popular carta parece que era A. E así cantos bits el propoñer usando para iso? Cero, un. 

E porque é aplicado como esta árbore, polo de agora déixeme estipular hai calquera ambigüidade en Morse código, porque todo o letras que se preocupan son a finais destes cantos. Entón, iso é só un aplicación dunha árbore. Isto é-- e eu vou acenar miña man neste como pode aplicar isto como unha estrutura C. Nós só necesitamos combinar un símbolo, como un char, ea miúdo en esquerda e dereita. Pero imos ollar para dous exemplos finais que vai bastante familiarizado con logo cuestionario cero no conxunto de problemas cinco. 

Polo tanto, hai a estrutura de datos coñecida como unha táboa de hash. E unha táboa hash é unha especie de arrefecer na medida en que ten baldes. E supoña que hai catro baldes aquí, só catro espazos en branco. Aquí está un baralla de cartas, e aquí está club, pa, club, diamantes, club, diamantes, clubs, diamantes, clubs-- entón que é o azar. Corazóns, entón estou hearts-- bucketizing todas as entradas aquí. E unha táboa de hash necesidades a ollar para a súa entrada, e, a continuación, colocar-lo en un poñer a base do que ve. É un algoritmo. E eu estaba a usar un super- algoritmo visual simple. A parte máis difícil do que foi lembrando-se de que as imaxes foron. E despois hai catro cousas totais. 

Agora, as pilas estaban crecendo, o que é unha cousa deliberada proxecto aquí. Pero o que máis podería facer? Entón, en realidade, temos aquí un banda de vellos libros de exame escolar. Supoña que un grupo de nomes alumnos están aquí. Aquí está unha táboa hash maior. No canto de catro baldes, Teño, digamos 26. E nós non queremos ir pedir prestado 26 cousas de fóra [? Annenberg?] Así aquí está cinco que representan A a Z. E se eu ver un alumno cuxo nome comeza con A, Vou poñer o seu cuestionario alí. Se alguén comeza con C, ata alí, A--, en realidade, non quería facelo. B pasa por aquí. Entón eu teño A e B e C. E Agora, aquí está outro estudante A. Pero, se esta táboa hash é aplicado con unha matriz, Eu son do tipo aparafusado Actualmente, non? Eu medio que cómpre poñer isto en algún lugar. 

Así, un xeito que podo resolver isto é, todo dereito, A é ocupado, B está ocupado, C está ocupado. Vou poñelas D. Entón, en primeiro lugar, eu teño acceso instantáneo chou para cada un dos baldes para os alumnos. Pero agora é unha especie de delegada en algo lineal, porque se eu queira buscar alguén cuxo nome comeza con A, eu verifico aquí. Pero, se esta non é a dun estudante que eu estou a buscar, Eu medio que teño que comezar a comprobar os baldes, xa que o que eu fixen era unha especie de linearmente sondar a estrutura de datos. Un xeito estúpido dicir basta ollar para a primeira apertura dispoñible, e poñer no seu plan B, por así dicir, ou plan D neste caso, o valor nese lugar. Este é só para que se ten ten 26 locais e ningún alumno co nome Q ou Z, ou algo así que, polo menos está a usar o espazo. 

Pero xa vimos máis solucións intelixentes aquí, non? O que faría no canto se ten unha colisión? Se dúas persoas teñen o nome A, o que sería ser un máis intelixente ou solución intuitiva que poñendo un D, ​​onde se quere que sexa? Por que non podo simplemente ir [fóra? Annenberg?], como malloc, outro no, coloque- aquí, e logo poñer que un estudante aquí. Así que eu tivera esencialmente algún tipo de unha matriz, ou quizais máis elegante como estamos empezando a ver unha lista ligada. 

E así unha táboa hash é unha estrutura que podería ollar só como este, pero máis intelixente, algo chamado fío separado, en que unha táboa hash moi simplemente é unha matriz, cada un dos cuxos elementos non é un número, é en si unha lista ligada. Para que teña acceso super rápido decidir onde botar o seu valor para. Moi parecido ao exemplo tarxetas, Eu fixen decisións super rápido. Corazóns vai aquí, diamantes vai aquí. Mesmo aquí, A vai aquí, D vai aquí, B vai aquí. Entón super rápido look emerxentes, e se pasar de correr nun caso colisións, onde ten dous, persoas co mesmo nome, así, entón acaba de comezar ligando-os xuntos. E quizais mantelos clasificadas por orde alfabética, quizais non. Pero polo menos agora temos o dinamismo. Así, por unha banda, temos super rápido constante de tempo e tipo de tempo lineal implicados se esas listas ligadas comezan a estar un pouco longo. 

Polo tanto, este tipo de un parvo, gracejo geeky anos. No CS50 Hack a Thon, cando os alumnos facturación, algúns TF ou CA cada ano Pensas que é divertido para poñer-se un sinal como este, onde só significa que o seu nome comeza cun A, ir por este camiño. Se o seu nome comeza cun B, ir isto-- OK, é divertido quizais máis tarde no semestre. Pero hai outra forma de facelo tamén. Imos volver a iso. 

Polo tanto, hai esa estrutura. E esta é a nosa última estrutura para hoxe, que é algo chamado trie. T-R-I-E, que, por algunha razón é curto para recuperación, pero é chamado trie. Así, outro interesante é trie amálgama de moitas desas ideas. É unha árbore, o que vimos antes. Non é unha árbore de busca binaria. É unha árbore con calquera número de fillos, pero cada un dos nenos nun trie é unha matriz. Unha matriz de tamaño, din, 26 ou que 27 se quere apoiar hifenizado nomes ou apóstrofos en nomes de persoas. 

E polo que esta é unha estrutura de datos. E se ollar arriba abaixo, como se mirar para o no superior alí, M, é apuntando para o máis á esquerda alí, que é, a continuación, A, X, W, E, L, L. Isto é só unha estrutura de datos que arbitrariamente é o almacenamento de nomes de persoas. E Maxwell é almacenado por só seguindo un camiño de matriz para matriz para matriz. Pero o que é sorprendente sobre un trie é que, mentres que a lista ligada e mesmo unha matriz, o mellor que eu xa cheguei é tempo lineal ou logarítmica tempo buscando alguén. Nesta estrutura de datos dun trie, se miña estrutura de datos ten un nome nel e eu estou buscando Maxwell, eu son Vai atopalo moi rapidamente. Acaba de ollar para M-A-X-W-E-L-L. Se esta estrutura de datos, en contraste, Se N é un millón, se hai unha millón de nomes nesta estrutura de datos, Maxwell aínda vai ser detectábel tras só M-A-X-W-E-L-L pasos. E pasos David-- D-A-V-I-D. Noutras palabras, a través da construción de unha estrutura de datos que é ten todas esas matrices, as cales sosterse de acceso aleatorio, Podo comezar a ollar para arriba de persoas nome usando unha cantidade de tempo que é proporcional á non o número de cousas na estrutura de datos, como un millón de nomes existentes. A cantidade de tempo que leva-me a atopar H-A-X-W-E-G-G na estrutura de datos é este non proporcional ao o tamaño da estrutura de datos, pero coa lonxitude do nome. E realista a nomes que nós estamos mirando para arriba non vai ser tolo por moito tempo. Quizais alguén ten un carácter 10 nomear, 20 nome do personaxe. É certamente finito, non? Non é un ser humano en que a Terra ten o nome máis longo posible, pero ese nome é unha constante lonxitude valor, non? Non varía en calquera sentido. Así, deste xeito, temos conseguida unha estrutura de datos que é tempo constante look-up. Fai ter un número de pasos dependendo da lonxitude da entrada, pero non o número de nome na estrutura de datos. Entón, se nós dobrar o número de nomes o ano que de mil millóns a dous millóns, constatación Maxwell levará o mesmo número de sete pasos para atopalo. E, así, parece ter conseguido noso Santo Graal do tempo de execución. 

Así, un par de anuncios rápidos. Cuestionario de cero está chegando. Máis sobre o tema na páxina web do curso durante o próximo par de días. Luns de lecture-- É unha festa aquí en Harvard o luns. Non é en New Haven, así que estamos tomando a clase a New Haven para charla o luns. Todo será filmado e transmitido en directo, como de costume, pero imos rematar hoxe cun segundo clip 30 chamados "Pensamentos Profundos" Daven por Farnham, que foi inspirado o ano pasado ata sábado "Pensamentos Profundos" de Night Live por Jack Handy, que agora debe ter sentido. 

PELÍCULA: E agora, "Deep Pensamentos "por Daven Farnham. Táboa de hash. 

COLUMNA 1: Todo ben, iso é todo por agora. Imos velo a próxima semana. 

Doug: Para velo en acción. Entón, imos dar un ollo niso agora. Entón, aquí temos un conxunto indiferenciado. 

Ian: Doug, pode ir adiante e reinicio iso por só un segundo, por favor. Todo ben, as cámaras están rolando, entón acción sempre que estea listo, Doug, OK? Doug: Todo ben, entón o que temos aquí é un conxunto indiferenciado. E eu teño colorido todos os elementos vermello para indicar que é, en realidade, indiferenciados. Entón recordar que o primeiro que facemos é que clasificar a metade esquerda da matriz. Logo clasificar a dereita metade da matriz. E ya-da, ya-da, ya-da, que fundín-las. E nós temos unha matriz completamente ordenada. Entón é así que funciona merge sort. 

Ian: Ei, ei, ei, corta, corta, corta, corta. Doug, non pode só ya-da, ya-da, ya-da, o seu camiño a través merge sort. 

Doug: Eu só fixen. É moi ben. Somos bos de ir. Nós só seguir xogando. Entón, de calquera xeito, 

Ian: Ten que explicar El máis plenamente do que iso. Isto non é só o suficiente. Doug: Ian, non necesitamos volver a un. É moi ben. En calquera caso, se seguimos con merge-- Ian, estamos no medio da rodaxe. 

Ian: Eu sei. E nós non podemos só ya-da, ya-da, ya-da, a través de todo o proceso. Ten que explicar como o dous lados se fundiron xuntos. 

Doug: Pero nós xa explicou como os dous sides-- 

Ian: Acaba mostra -lhes unha variedade de mesclagem. Doug: Saben o proceso. Están ben. Temos ido sobre el dez veces. 

Ian: Acaba de saltar dereito sobre el. Imos voltar a un, non pode ya-da, ya-da sobre el. Todo ben, de volta a un. 

Doug: Teño que volver a través de todos os diapositivas? Meu Deus. É como o sexto tempo, Ian. É moi ben. 

Ian: Todo ben. Está preparado? Gran. Acción.