[Powered by Google Translate] [Semana 6, continuación] [David J. Malan] [Harvard University] [Esta é CS50.] [CS50.TV] Este é CS50 e este é o fin da semana 6. Entón CS50x, un dos primeiros cursos de Harvard implicados na iniciativa EDX de feito estreou este luns pasado. Se desexa obter un vislumbre do que os outros en Internet agora están acompañando con, pode ir x.cs50.net. Que ha redireccionándoos lo para o lugar apropiado no edx.org, que foi onde este e outros cursos do MIT e Berkeley viven agora. Vai ter que rexistrarte para unha conta, vai descubrir que o material é basicamente o mesmo como tivo neste semestre, aínda que algunhas semanas atrasadas, como temos todo listo. Pero o que os alumnos en CS50x vai ver agora unha interface bastante coma este. Este, por exemplo, é Zamyla levando paso a paso para conxunto de problemas 0. Ao facer o login para edx.org, un estudante CS50x ve os tipos de cousas que sería de esperar a ver nun curso: a palestra para o luns, charla para o mércores, shorts diversos, os conxuntos de problemas, as orientacións, PDFs. Ademais, como se ve aquí, traducións automáticas transcricións de inglés para chinés, xaponés, español, italiano, e unha banda enteiro de outras linguas que seguramente vai ser imperfecto coma nós rolamos-los programaticamente usando unha cousa chamada API, ou interface de programación de aplicación, Google que nos permite converter Inglés para esas outras linguas. Pero, grazas ao marabilloso espírito de algúns voluntarios máis de cen, persoas aleatorias en Internet que xentilmente ofrecidos a se involucrar Neste proxecto, nós imos ser gradualmente mellorar a calidade destas traducións por humanos corrixir os erros que os nosos ordenadores fixeron. Así, verifícase que había algúns estudantes máis aparecer o luns do inicialmente esperado. En realidade, agora CS50x ten 100.000 persoas que seguen xunto na casa. Entón, entende que son todos parte desa clase inaugural de facer este curso de ciencia da computación educación máis xeralmente, de forma máis ampla, accesible. E a realidade é agora, con algúns deses cursos masivos en liña, todas elas comezan con estas cifras moi elevados, como parece ter feito aquí. Pero o obxectivo, en última instancia, para CS50x é realmente levar a xente como moitos a liña de chegada como sexa posible. Polo proxecto, CS50x vai ser ofrecido dende esta pasado luns todo o camiño ata 15 de abril de 2013, para que as persoas que teñen compromisos escolares noutros lugares, traballo, a familia, os conflitos outros e semellantes, ten un pouco máis de flexibilidade co cal a mergullo neste curso, que basta dicir, é moi ambiciosa feito só ao longo de tres meses, durante un semestre de costume. Pero estes alumnos serán afrontar os conxuntos mesmo problema, a ver o mesmo contido, ter acceso aos mesmos calzóns e similares. Entón, entender que todos nós somos verdadeiramente xuntos nesa. E un dos obxectivos finais de CS50x non é só para ter xente como moitos para a liña de chegada e darlles esa nova comprensión da ciencia da computación e programación, pero tamén para que eles teñen esa experiencia compartida. Unha das características definidoras do 50 no campus, esperamos, Foi este tipo de experiencia común, para mellor ou para peor, ás veces, pero ter estas persoas a volver-se cara á esquerda e cara á dereita, e as horas de oficina e Hackathon e da feira. É un pouco máis difícil de facer isto persoalmente con persoas en liña, pero CS50x vai concluír en abril, coa primeira CS50 Expo, que será unha adaptación en liña da nosa idea da feira onde estes miles de estudantes todos serán invitados a presentar unha 1 - a 2 minutos de vídeo, ou un screencast do seu proxecto final ou vídeo deles aceno Ola e falar sobre o seu proxecto e demos-lo, así como os seus antecesores fixeron aquí no campus da feira, de xeito que ata o final do semestre, a esperanza é ter unha exposición mundial de proxectos dos alumnos CS50x 'finais, así como aquel que o espera en decembro aquí no campus. Así, máis do que en próximos meses. Con 100.000 estudantes, porén, vén a necesidade dunha CAs algúns. Dado que están abrindo a banda aquí e tendo CS50 varias semanas antes do lanzamento deste material para as persoas en EDX, entender que queremos involucrar como moitos dos nosos propios alumnos como sexa posible a esta iniciativa, tanto durante o semestre, así como neste inverno e na próxima primavera. Entón, se quere se involucrar en CS50x, xuntándose particularmente en CS50x discutir, a versión de EDX CS50 discutir, que moitos de vostedes están usando no campus, no cadro de avisos en liña Por favor, faga a cabeza para esa URL, deixe-nos saber quen é vostede, porque adoraríamos para construír un equipo de alumnos e funcionarios e profesores iguais no campus que están simplemente xogando ben e axudando. E cando ven unha cuestión que é familiar a eles, oe un estudante informar algún erro en algún lugar aí fóra, nalgún país en Internet, e que toca unha campá porque tamén tivo que mesmo tema no seu d-hall, hai algún tempo, espero, entón podes dialogar e compartir a súa propia experiencia. Entón por favor non participar se desexa. Cursos de ciencia da computación na Universidade de Harvard ten un pouco de unha tradición, CS50 entre eles, ter algún efecto, algunhas roupas, que pode usar con orgullo ao final do semestre, dicindo con certa orgullo que rematou CS50 e tomou CS50 e afíns, e nós tratamos sempre involucrar os alumnos neste proceso, na medida do posible, en que convidamos, nesa época do semestre, os alumnos presenten proxectos usando o Photoshop ou calquera ferramenta de selección que desexa usar Se vostede é un deseñador, a someterse proxectos para camisetas e camisolas e parasois e bandana para cans pequenos que temos agora e similares. E todo é entón - os vencedores de cada ano son, entón, mostrou na páxina web do curso en store.cs50.net. Todo é vendido ao custo de alí, pero o sitio só funciona só e permite que a xente a escoller as cores e debuxos que lle gusta. Entón eu penso que tiña acaba de compartir algúns dos proxectos do ano pasado que estaban no sitio alén deste aquí, que é unha tradición anual. "Todo o día eu estou L Faultn" era unha das propostas do ano pasado, que aínda está dispoñible alí para ex-alumnos. Tivemos un regalo ", CS50, Fundación 1989." Un dos nosos Bowdens, Rob, era moi popular o ano pasado. "Team Bowden" naceu, este proxecto foi sometido, entre os máis vendidos. Como foi este aquí. Moitas persoas tiveron "Fever Bowden" de acordo cos rexistros de vendas. Entenda que que podería agora ser o seu proxecto alí, enriba da Internet. Máis detalles sobre este problema na próxima define por vir. Unha ferramenta: tivo algunha exposición e espero que agora algunha experiencia hands-on co GDB, que é, naturalmente, un depurador e permite que manipule o seu programa nun nivel bastante baixo, facendo o tipo de cousas? O que o GDB deixar facer? Si? Déame algo. [Responder Estudante, inintelixible] Bo Etapa en función, para que non só ten que escribir run e ter o golpe programa a través do seu conxunto, imprimir cousas para a saída estándar. En vez diso, pode percorrelo-lo liña por liña, escribindo seguinte ir liña por liña por liña ou paso para mergullar nunha función, normalmente o que escribiu. O que máis fai GDB deixar facer? Si? [Responder Estudante, inintelixible] Imprimir variables. Entón, se quere facer un pouco de introspección dentro do seu programa sen ter que recorrer a escribir instrucións printf en todo o lugar, pode só imprimir unha variable ou mostrar unha variable. O que máis pode facer un depurador como o GDB? [Responder Estudante, inintelixible] Exactamente. Podes establecer puntos de interrupción, pode dicir que a execución pausa A función principal ou a función foo. Pode dicir que a execución pausa na liña 123. E puntos de interrupción son unha técnica moi poderosa porque se ten unha sensación xeral de que o seu problema probablemente é, non precisa perder tempo percorrendo totalidade do programa. Pode saltar esencialmente á dereita e entón comezar a escribir - percorrendo a con paso ou próximo ou semellante. Pero o problema con algo parecido ao GDB é que axuda, o humano, atopar os seus problemas e atopar os seus erros. Iso non significa necesariamente atopalos moito por ti. Entón, nós introducimos o style50 outro día, que é unha ferramenta de liña de comandos curta que intenta estilizar o seu código un pouco máis limpa do que o humano, podería ter feito. Pero iso, tamén, é realmente só unha cousa estética. Pero acontece que hai esa outra ferramenta chamada Valgrind que é un pouco máis escuro de usar. A súa saída é atrozmente enigmática, a primeira vista. Pero é marabillosas útil, especialmente agora que estamos na parte do termo onde está empezando a usar malloc e distribución dinámica de memoria. As cousas poden dar moito mal rapidamente. Porque se esquecer de liberar a súa memoria, ou cancelar a referencia dalgún punteiro NULL, ou cancelar a referencia dalgún punteiro de lixo, que normalmente é o síntoma que resultados? L culpa. E comeza este ficheiro núcleo dalgún número de kilobytes ou megabytes que representa o estado da memoria do seu programa cando el caeu, pero o seu programa, en última análise seg fallos, fallo de segmento, o que significa que algo malo aconteceu case sempre relacionados a un erro relacionado coa memoria que fixo nalgún lugar. Entón Valgrind axuda a atopar cousas como esta. É unha ferramenta que executa, como GDB, despois de feita seu programa, pero en vez de executar o programa directamente, vostede corre Valgrind e pasar a el o seu programa, así como fai o GDB. Agora, o uso, para obter o mellor tipo de saída, é un pouco longo, por iso alí na parte superior da pantalla, podes ver Valgrind-v. "-V" case universalmente significa verbose cando está usando programas nun ordenador Linux. Entón iso significa cuspir máis datos do que pode, por defecto. "- Leak-check = total". Este é só dicir selección para todos os posibles derrames de memoria, erros que eu podería ter feito. Isto, tamén, é un paradigma común con programas Linux. Xeralmente, se ten un argumento de liña de comandos que é un "interruptor", que debería cambiar o comportamento do programa, e unha única letra, é-v, pero iso está conectado, só polo deseño do programador, é unha palabra completa ou serie de palabras, o argumento de liña de comandos comeza con -. Estes son só convencións humanas, pero vai ve-los cada vez máis. E, a continuación, finalmente, "a.out" é o nome arbitrario para o programa, neste exemplo particular. E aquí vai unha saída representativa. Antes de olharmos para o que iso significa, deixe-me ir a un fragmento de código aquí. E deixe-me pasar esta fora do camiño, en breve, e imos dar un ollo a memory.c, que é este pequeno exemplo aquí. Polo tanto, neste programa, deixe-me zoom e as funcións e preguntas. Temos unha función principal que chama unha función, f, e entón o que se f continuar a facer, en inglés un pouco técnico? O que fai f proceder a facer? Que tal eu vou comezar coa liña 20, e localización da estrela non importa, pero eu só vou ser coherente aquí con última charla. Cal é a liña 20 non para nós? No lado da man esquerda. Imos división la aínda máis. Int * x: que é o que fai? Okay. É declarar un punteiro, e agora imos ser aínda máis técnico. O que significa, moi concretamente, para declarar un punteiro? Alguén máis? Si? [Responder Estudante, inintelixible] Moi lonxe. Entón está lendo o lado dereito do signo igual. Imos nos centrarse só na esquerda, só int * x. Isto significa "declarar" un punteiro, pero agora imos mergullar máis fondo para esa definición. O que isto concretamente, tecnicamente significa? Si? [Responder Estudante, inintelixible] Okay. Está preparado para gravar un enderezo na memoria. Bo E imos dar un paso adiante, que é declarar unha variable, x, que é de 32 bits. E eu sei que é de 32 bits porque -? Non é porque é un int, porque é un punteiro neste caso. Coincidencia que é un eo mesmo con un int, pero o feito de que non é a estrela que significa que este é un punteiro e no interior do aparello, como acontece con moitos ordenadores, pero non todas, as indicacións son de 32 bits. En máis hardware moderno, como os máis recentes Macs, os máis recentes PCs, pode ter punteiros de 64 bits, pero no aparello, esas cousas son de 32 bits. Entón, imos padronizar iso. Máis concretamente, a historia é a seguinte: Nós "declarar" un punteiro, que é o que significa isto? Nós nos preparamos para almacenar un enderezo de memoria. O que significa isto? Creamos unha variable chamada x, que ocupa 32 bits que en breve almacenar o enderezo de un número enteiro. E iso pode ser tan preciso como podemos chegar. É bo avanzar para simplificar o mundo e dicir declarar un punteiro chamado x. Declare un punteiro, pero entender e comprender o que está realmente a suceder mesmo en só algúns deses personaxes. Agora, este é case un pouco máis fácil, aínda que sexa unha máis expresión. Entón que é o que está facendo, que é destacado agora: "malloc (10 * sizeof (int));" Si? [Responder Estudante, inintelixible] Bo E eu vou leva-lo alí. É atribución dun bloque de memoria para 10 enteiros. E agora imos mergullar un pouco máis profunda, que é reservar un bloque de memoria para 10 enteiros. ¿Que é malloc despois volver? O enderezo do bloque, ou, de forma máis concreta, o enderezo do primeiro byte do referido peza. Como, entón, son eu, o programador, para saber onde ese pedazo de fins de memoria? Sei que é contiguo. Malloc, por definición, lle dará un anaco contiguo de memoria. Ningún lagoas. Ten acceso a todos os bytes nese anaco, de costas cara atrás, pero como sei que o fin deste pedazo de memoria é? Cando usa malloc? [Responder Estudante, inintelixible] Boa. Non. Ten que se lembrar. Eu teño que lembrar que eu usei o valor 10, e eu non parecen mesmo ter feito isto aquí. Pero a responsabilidade é enteiramente en min. Strlen, que nos facemos un pouco dependente para cordas, só funciona por mor desa convención de \ 0 ou este carácter especial nul, NUL, ao final dunha cadea. Isto non val para só anacos arbitrarios de memoria. Correspóndelle a vostede. Así, a liña 20, entón, aloca un bloque de memoria que pode almacenar 10 enteiros, e almacena o enderezo do primeiro byte dese anaco de memoria na variable x chamado. Logo, o que é un punteiro. Entón, liña 21, desgraciadamente, foi un erro. Pero, primeiro, o que está facendo? É dicir tenda no lugar 10, 0 indexados, do bloque de memoria chamado X o valor 0. Entón, observe algunhas cousas están a ocorrer. Aínda que x é un punteiro, lembrar de algunhas semanas atrás que aínda pode usar a matriz estilo de notación de colchete. Porque iso é realmente curto man notación para a aritmética de punteiro máis crítico para o futuro. onde iríamos facer algo como isto: Colla o enderezo x, mover máis de 10 puntos, a continuación, ir para alí a calquera enderezo é almacenado no lugar. Pero, francamente, este é só atroz de ler e sentirse cómodo con. Así, o mundo normalmente usa os corchetes só porque é moito máis humano-agradable para ler. Pero iso é o que realmente está a suceder debaixo do capó; x é un enderezo non, unha matriz, de per si. Polo tanto, este é almacenar 0 na posición 10 en x. Por que iso é malo? Si? [Responder Estudante, inintelixible] Exactamente. Nós só alocados 10 ints, pero contar de 0 a programar en C, para que teña acceso a 0 10 1 2 3 4 5 6 7 8 9 pero non. Así, ou o programa vai culpa seg ou non é. Pero nós realmente non sabemos, este é un tipo de comportamento non determinístico. Isto realmente depende se temos sorte. Se se comprobar que o sistema operativo non se importa se eu usar este byte extra, aínda que non lle deses ningunha para min, o meu programa non pode fallar. É cru, é buggy, pero non pode ver este síntoma, ou pode velo só de cando en vez. Pero a realidade é que o erro é, de feito, non hai. E é realmente problemático se escribiu nun programa que quere ser correcto, que vendeu o programa que a xente está a usar que de cando en cando cae porque, por suposto, este non é boa. De feito, se ten un móbil con Android ou un iPhone e baixar aplicacións nos días de hoxe, se xa tivo un app abortar, de súpeto el desaparece, que é case sempre o resultado algún problema relacionado coa memoria, cal o desenvolvedor asneira e dereferenced un punteiro que el ou ela non debe ter, eo resultado do IOS ou Android é só para matar o programa completo en vez de comportamento indefinido risco ou algún tipo de compromiso da seguridade. Hai outro erro no programa alén deste. O que máis me estraguei todo neste programa? Eu non practiquei o que eu teño cravado. Si? [Responder Estudante, inintelixible] Boa. Eu non liberou a memoria. Polo tanto, a regra de ouro agora ten que ser sempre que chamar malloc, ten que chamar libre cando está feito usando a memoria. Agora, cando eu ía querer liberar esta memoria? Probablemente, asumindo que esta primeira liña foi correcta, gustaríame facelo aquí. Porque eu non podería, por exemplo, fai-o aquí. Por que? Só fóra do alcance. Así, aínda que estamos falando de punteiros, Esta é unha semana 2 ou 3 cuestión, no que x é só un alcance dentro das bosquexo onde foi declarado. Entón vostede definitivamente non pode liberar-lo alí. A miña única oportunidade de liberar-la é de aproximadamente tras a liña 21. Este é un programa moi sinxelo, era bastante fácil, xa que o tipo de enrolado súa mente en torno ao que o programa está facendo, onde os erros foron. E mesmo se non velo en primeiro lugar, espero que sexa un pouco obvio agora que estes erros son moi facilmente resoltos e facilidade. Pero cando un programa é máis que 12 liñas de tempo, é 50 liñas, 100 liñas, andar a través do seu código liña por liña, pensando por iso, loxicamente, é posible, pero non particularmente divertido de facer, sempre á procura de erros, e tamén é difícil de facer, e é por iso que unha ferramenta como Valgrind existe. Deixe-me ir adiante e facelo: déixeme abrir a xanela de terminal, e deixe-me non só realizar memoria, porque a memoria parece estar ben. Eu estou tendo sorte. Indo para o byte adicional ao final da matriz non parece ser moi problemático. Pero deixe-me, con todo, facer unha comprobación de sanidade mental, o que significa só para comprobar este é ou non realmente correcto. Entón imos facer valgrind-v - Leak-check = completo, e, a continuación, o nome do programa, neste caso, é a memoria, e non a.out. Entón deixe-me ir adiante e facelo. Prema Intro. Querido Deus. Esta é a súa saída, e iso é o que me refire anteriormente. Pero, se aprender a ler a través de todos os disparates aquí, máis iso é só a saída de diagnóstico que non é tan interesante. O seu ollo realmente quere estar buscando é calquera mención de erro ou non é válido. Palabras que suxiren problemas. E, de feito, imos ver o que está a suceder de malo aquí. Eu teño un resumo de calquera tipo, "en uso na saída:. 40 bytes en bloques de 1" Eu non estou seguro do que un bloque é aínda, pero 40 máis realmente se sente como se eu puidese descubrir de onde que vén. 40 bytes. Por que o 40 bytes en uso na saída? E, máis concretamente, se rolar aquí, por que eu sempre perdeu 40 bytes? Si? [Responder Estudante, inintelixible] Perfecto. Si, exactamente. Había dez números enteiros, e cada un destes é o tamaño de 4 ou 32 bits, entón eu perdín exactamente 40 bytes, porque, como propuxo, non chamei libre. Isto é un erro, e agora imos ollar para abaixo un pouco máis e ver ao lado deste, "Válido escribir de tamaño 4". Agora, o que é iso? Este enderezo é expresado que a notación de base, ao parecer? Este é hexadecimal, ea calquera momento ve un número comezando con 0x, isto significa hexadecimal, o que fixemos no camiño de volta, eu creo, sección pset 0 de preguntas, que era só para facer un exercicio de calefacción, a conversión de decimal para hexadecimal para binario e así por diante. Hexadecimal, só por convención humana, é xeralmente usado para representar punteiros ou, de xeito máis xeral, aborda. É só unha convención, porque é un pouco máis fácil de ler, é un pouco máis compacto do que algo así como decimal, e binario é inútil para a maioría dos seres humanos de usar. Entón agora o que significa isto? Ben, parece que hai unha gravación válido de tamaño 4 na liña 21 de memory.c. Entón imos voltar á liña 21 e, de feito, é aquí que a gravación non válido. Entón Valgrind non completamente segura miña man e me diga o que a corrección é, pero está detectando que eu estou facendo unha gravación válido. Estou tocando 4 bytes que eu non debería ser, e, ao parecer, iso porque, como apuntou, eu estou facendo [10] no canto de [9] maximamente ou [0] ou algo entre os dous. Con Valgrind, realizar calquera momento que está escribindo un programa que usa punteiros e utiliza a memoria, e máis especificamente malloc, definitivamente o costume de correr tanto tempo pero moi facilmente copiado e pegado mando do Valgrind a ver se hai algúns erros alí. E vai ser esmagadora cada vez que ver a saída, pero só analizar visualmente a través de toda a saída e ver se ves mencións de erros ou avisos ou non válido ou perdido. Todas as palabras que soan como errou en algún lugar. Entón entender que é unha nova ferramenta no seu toolkit. Agora o luns, tivemos unha morea de xente veu aquí e representar a noción de unha lista ligada. E introducimos a lista ligada como unha solución para o problema? Si? [Responder Estudante, inintelixible] Boa. Matrices non poden ter memoria engadidos a eles. Se reservar unha matriz de tamaño 10, que é todo o que pode. Pode chamar unha función como realloc inicialmente chamada malloc, e que pode probar a crecer a matriz, se hai espazo para o fin de que que ninguén máis está a usar e, se non hai, ela só vai atopar unha peza maior noutro lugar. Pero entón vai copiar todos os bytes para a nova matriz. Isto soa como unha solución moi correcta. Por que iso é pouco atractiva? Quero dicir que funciona, os seres humanos teñen resolto este problema. Por que temos que resolver iso o luns con listas ligadas? Si? [Responder Estudante, inintelixible] Pode levar un longo tempo. En realidade, en calquera momento que está chamando malloc calloc ou realloc ou, o que é aínda un outro, calquera momento que o programa está falando co sistema operativo, tende a facer o programa lento. E se está facendo eses tipos de cousas en loops, está realmente abrandar as cousas. Non vai entender iso por máis sinxelo de "Hello World" programas do tipo, pero en programas moi grandes, pedindo que o sistema operativo novo e de novo para a memoria ou dándolle de volta unha e outra vez tende a non ser unha cousa boa. Ademais, é só unha especie de intelectual - é un completo pérdida de tempo. Por que reservar máis memoria e máis risco, copiar todo para a nova matriz, Se vostede ten unha alternativa que permite reservar memoria só o que realmente precisa? Polo tanto, hai pros e contras aquí. Unha das vantaxes é que agora temos dinamismo. Non importa de onde os anacos de memoria son de que están libres, Eu só podo clasificar de crear estas migas de pan a través de punteiros amarre miña lista enteira conectados. Pero eu pagar polo menos un prezo. O que eu teño a dar-se na obtención de listas ligadas? Si? [Responder Estudante, inintelixible] Boa. Precisa máis memoria. Agora eu teño espazo para estas indicacións, e no caso de este super sinxelo conectado que só a tentar gardar números enteiros, que son 4 bytes, que segue dicindo ben, un punteiro é de 4 bytes, entón agora eu teño literalmente dobrou a cantidade de memoria que eu teño só para gardar esta lista. Pero, de novo, esta é unha cambio constante en ciencia da computación entre tempo e espazo e esforzo de desenvolvemento, e outros recursos. O que é outra desvantaxe de usar unha lista ligada? Si? [Responder Estudante, inintelixible] Bo Non é tan fácil de acceder. Non podemos máis alavancagem Semana 0 principios como dividir e conquistar. E, máis concretamente, a investigación binaria. Porque aínda que nós, seres humanos pode ver máis ou menos onde a metade da lista, o ordenador só sabe que este ligada comeza no enderezo chamado primeiro. E iso é 0x123 ou algo parecido. E a única forma de que o programa pode atopar o elemento do medio é realmente buscar a lista enteira. E aínda así, el literalmente ten que buscar a lista enteira porque mesmo cando chegue o elemento do medio, seguindo os punteiros, ti, o programa, non ten idea de canto tempo esa lista é, potencialmente, ata chegar ao final do mesmo, e como vostede sabe de programación que está ao final dunha lista ligada? Hai un punteiro especial NULL, polo tanto, de novo, unha convención. En vez de usar este punteiro, nós definitivamente non queremos que sexa un valor lixo apuntando para fóra do escenario en algún lugar, queremos que sexa man para abaixo, NULL, de xeito que temos este terminal nesta estrutura de datos para sabermos onde remata. O que se quere manipular iso? Fixemos a maior parte deste visualmente, e cos seres humanos, pero o que se quere facer unha inserción? Así, a lista orixinal era de 9, 17, 20, 22, 29, 34. E se nós entón quería espazo malloc para o número 55, un nó para el, e entón queremos introducir 55 na lista, así como fixemos o luns? Como podemos facer iso? Ben, Anita veu e ela camiñou esencialmente da lista. Comezou o primeiro elemento, entón o próximo, o próximo, o outro, o próximo, o seguinte. Finalmente chegou a man esquerda todo o camiño e entender oh, iso é NULL. Entón, o que a manipulación de agullas precisaba ser feito? A persoa que estaba no fin, número 34, precisaba da súa man esquerda levantada para apuntar para 55, 55 precisaban do seu brazo esquerdo apuntando cara abaixo para o novo terminador nulo. Feito. Moi doado de inserir unha lista de 55 clasificados. E como isto pode ollar? Deixe-me ir adiante e abrir un exemplo de código aquí. Vou abrir o gedit, e deixe-me abrir dous arquivos primeiro. Un é list1.h, e deixe-me lembrar que este foi o anaco de código que usan para representar un nó. Un nó ten tanto un int chamado n e un punteiro chamado a continuación que só puntos para a próxima cousa na lista. Que agora está nun arquivo h .. Por que? Hai esa convención, e non temos aproveitado este unha enorme cantidade de nós mesmos, pero a persoa que escribiu funcións printf e outros deu como agasallo para o mundo todas esas funcións por escribir un ficheiro chamado stdio.h. E despois hai string.h, e entón hai map.h, e hai todos estes arquivos h que pode ver ou usar durante o prazo escritos por outras persoas. Normalmente nos. Arquivos h son só cousas como typedefs ou declaracións de tipos personalizados ou declaracións de constantes. Non poñer implementacións funcións 'en arquivos de cabeceira. Vostede pon, en vez diso, só os seus prototipos. Vostede pon as cousas que quere compartir co mundo o que eles precisan para compilar o código. Entón, só para chegar a este hábito, decidimos facer a mesma cousa. Non hai moito en list1.h, pero poñemos algo que pode ser do interese de persoas no mundo que queren usar a nosa implantación lista encadeada. Agora, en list1.c, eu non vou pasar por esa cousa toda porque é un pouco longo, este programa, pero imos executa-lo real rapidamente no prompt. Deixe-me compilar Lista1, deixe-me a continuación, realizar Lista1, eo que vai ver é temos un programa de simulación simple pouco aquí que vai me permite engadir e eliminar números a unha lista. Entón deixe-me ir adiante e escriba 3 a 3 opción de menú. Quero introducir o número - imos facer o primeiro número, que foi de 9, e agora eu son informados a lista é agora 9. Deixe-me ir adiante e facer outra inserción, entón eu bati opción de menú 3. Cal é o número que quero introducir? 17. Intro. E eu vou facer só un. Deixe-me introducir o número 22. Polo tanto, temos o inicio da lista encadeada que tiñamos en forma de diapositivas nun momento atrás. Como é que esta inserción realmente a suceder? De feito, 22 e agora no fin da lista. Así, a historia que contou no escenario o luns e só agora recapitulou debe realmente estar a suceder no código. Imos dar un ollo. Deixe-me rolar neste arquivo. Nós imos pasar por riba algunhas das funcións, pero nós imos descender para, digamos, a función de inserción. Imos ver como nós imos sobre a inserción dun novo nodo a esta lista ligada. Onde está a lista declarada? Ben, imos percorrer todo o camiño ata o cumio, e entender que a miña lista ligada esencialmente declarado como un punteiro único que é inicialmente NULL. Entón, eu estou usando unha variable global aquí, que en xeral temos predicado contra porque fai que o seu código un pouco confuso para manter, é unha especie de preguiza, normalmente, pero non é preguiceiro e non é malo e non é malo o propósito único do seu programa na vida é para simular unha lista ligada. Que é o que estamos facendo. Entón en vez de declarar isto principal e logo ter que pasalo para cada función temos escrito neste programa, en vez entender oh, imos facelo global porque todo o propósito deste programa é demostrar unha e só unha lista ligada. Entón, que se sente ben. Aquí están os meus prototipos, e non imos pasar por todo iso, pero eu escribín unha función de exclusión, unha función de atopar, unha función de inserción, e unha función de travesía. Pero imos agora volverse para a función de inserción para ver como este funciona aquí. Inserción e on line - aquí imos nós. Inserir. Entón, non é preciso ningún argumento, porque nós imos pedir o interior usuario desta función ao número que desexa introducir. Pero, primeiro, nos preparamos para darlles un pouco de espazo. Esta é unha especie de copiar e pegar do outro exemplo. Neste caso, fomos asignación dun int, esta vez estamos alocando un nó. Eu realmente non me lembro cantos bytes un nó é, pero iso é bo. Sizeof pode descubrir iso para min. E por que estou comprobando NULL na liña 120? O que podería dar mal na liña 119? Si? [Responder Estudante, inintelixible] Bo Só podería ser o caso de que eu pedín moita memoria ou algo está mal eo sistema operativo non ten máis suficiente para me dar, por iso sinala tanto por volver nulo, e eu non comprobar que e eu só cega continuar a utilizar o enderezo de retorno, pode ser NULL. Podería ser algún valor descoñecido, non é unha boa cousa a non ser que eu - en realidade, non será un valor descoñecido. Pode ser NULL, entón eu non quero a abusar dela e arriscar dereferencing-lo. Se isto acontecer, eu só volver e imos finxir que eu non volver calquera memoria de todos. Se non, eu digo que o usuario me dar un número para introducir, eu chamo a nosa GetInt vello amigo, e entón esta foi a nova sintaxe que introduciu o luns. 'Newptr-> n' significa ter o enderezo que lle foi subministrado por malloc que representa o primeiro byte dun obxecto novo nodo, e despois ir para o campo chamado n. Unha cuestión pouco trivial: Este é equivalente ao que liña máis enigmática do código? Como podería eu escribir isto? Quere dar unha facada? [Responder Estudante, inintelixible] Bo Usando o n., Pero non é tan sinxelo coma iso. O que eu primeiro teño que facer? [Responder Estudante, inintelixible] Bo Eu teño que facer newptr.n *. Polo tanto, este novo punteiro está dicindo é, obviamente, un enderezo. Por que? Porque foi devolto por malloc. O newptr * dicindo "vaia alí", e, a continuación, unha vez que está alí, entón podes usar o máis familiar. n, pero iso só parece un pouco feo, especialmente se nós, seres humanos van deseñar os punteiros coas frechas todo o tempo, o mundo ten estándar nesta notación de frecha, que fai exactamente a mesma cousa. Así, só usar - notación> cando a cousa da esquerda é un punteiro. En caso contrario, se é unha estrutura real, use o n .. E despois este: Por qué me arrincar newptr-> ao lado nulo? Nós non queremos unha man pendurada esquerda fóra da final da etapa. Queremos que apuntar directamente cara abaixo, o que significa o fin desta lista podería ser neste nodo, entón é mellor que seguro que é NULL. E, en xeral, arrincar súas variables ou membros de datos e estruturas a algo é só unha boa práctica. Só deixar lixo existen e seguirán a existir, xeralmente queda en apuros Se se esquecer de facer algo máis tarde. Aquí está algúns casos. Isto, de novo, é a función de inserción, ea primeira cousa que eu comprobar se a variable chamada primeiro, esa variable global é NULL, o que significa que non hai lista ligada. Non inseriu ningún número, por iso é trivial para introducir este número actual na lista, porque só pertence ao comezo da lista. Entón, iso foi cando Anita estaba en pé aquí só, finxindo non había máis ninguén aquí no escenario ata alocamos un nó, entón ela podería levantar a man por primeira vez, se todo o mundo tivese benvida no escenario despois da súa luns. Agora, aquí, este é un cheque pequeno onde eu teño que dicir que o valor do novo nodo n é seguinte, o que significa ir a estrutura que está a ser apuntado por newptr, entón aquí estamos nós, vai alí. A continuación, a frecha está dicindo obter o seguinte campo, e entón a = está dicindo poñer o valor alí? O valor que estaba en primeiro, que o valor que estaba en primeiro lugar? Primeiro foi apuntando para este nodo, o que significa que este debe agora apuntar a este nodo. Noutras palabras, o que parece aínda unha desorde ridículo coa miña letra, o que é unha idea simple de só mover esas frechas ao redor traduce código con só forro este. Almacenar o que está en primeiro no campo ao lado e entón actualizar o primeiro realmente é. Imos adiante e avanzar rapidamente un pouco diso, e mirar só para esa inserción do rabo por agora. Supoña que chegar ao punto no que eu considerar que o seguinte campo de algún no é NULL. E neste punto da historia, un detalle que eu estou pasando por riba é que eu introducín outro punteiro se aquí na liña 142, punteiro antecesor. Esencialmente, neste punto da historia, unha vez que a lista é longa, Eu medio que teño piso con dous dedos, porque se eu for moi lonxe, Teña en conta que nunha única lista de longo, non pode ir cara atrás. Entón esa idea de predptr é o meu dedo cara á esquerda, e newptr - non newptr. Outro indicador que está aquí é o meu outro dedo, e eu son só un tipo de andar a lista. É por iso que existe. Pero imos considerar só un dos casos máis simple aquí. Se o campo seguinte que punteiro é NULL, o que é a implicación lóxica? Se está atravesando este e bater un punteiro NULL? Está no fin da lista, e así o código para entón engadir este elemento adicional é unha especie de intuitiva terá que no cuxa próxima punteiro é NULL, por iso este é actualmente NULL, e cambia-lo, aínda que, de ser o enderezo do novo nodo. Entón, estamos só debuxando no código da frecha que trazamos no escenario, levantando a man esquerda de alguén. É o caso que eu vou acenar as mans menos por agora, só porque eu creo que é fácil perderse cando o facemos neste tipo de ambiente, é a comprobación de inserción no medio da lista. Pero só de forma intuitiva, o que debe ocorrer se queres descubrir onde un número pertence no medio é que ten que camiñar con máis de un dedo, máis dun punteiro, descubrir onde el pertence, a verificación é o elemento O actual, e unha vez que atopar ese lugar, entón tes que facer este tipo de xogo de cunchas onde move os punteiros en torno de moito coidado. E esa resposta, se desexa razón por este na casa no seu propio país, se reduce só a estas dúas liñas de código, pero a orde das liñas é super importante. Porque se soltar a man de alguén e levantar outra persoa na orde errada, de novo, pode acabar orfandade da lista. Para resumir máis conceptualmente, a inserción na cola é relativamente sinxelo. A inserción na cabeza tamén é relativamente simple, pero precisa actualizar un punteiro adicional neste momento para espremer o número 5 na lista aquí, e, a continuación, a inserción no medio implica un esforzo aínda maior, Para inserir coidadosamente o número 20 na súa posición correcta, que é entre 17 e 22. Entón, ten que facer algo como ter o novo nó de punto de 20 a 22, e, a continuación, o punteiro que no debe ser actualizado pasado? E 17, de verdade inserir-lo. Entón, de novo, eu vou retrasar o código real para que a implementación particular. A primeira vista, é un pouco asustado, pero é realmente só un ciclo infinito que é looping, looping, looping, looping, e rompendo así que bateu o punteiro NULL, en que punto pode facer a inserción necesaria. Este, entón, é o código de inserción representante lista ligada. Que era unha especie de un lote, e parece que resolvemos un problema, pero nós introducimos un totalmente diferente. Francamente, nós pasamos todo ese tempo en grande e Ω e correndo o tempo, intentando resolver os problemas máis rapidamente, e aquí estamos dando un gran paso cara atrás, el se sente. E, no entanto, se o obxectivo é almacenar datos, parece que o Santo Graal, como dixemos o luns, sería realmente para gardar cousas instantaneamente. En realidade, creo que fixemos poñer lista de banda conectado por un momento e nós, en vez introduciu a noción dunha mesa. E imos pensar nunha mesa por un momento como unha matriz. Esta matriz e neste caso aquí ten preto de 26 elementos, de 0 a 25, e supoña que precisaba dalgún anaco de almacenamento de nomes: Alicia e Bob e Charlie e similares. E precisa algunha estrutura de datos para almacenar eses nomes. Ben, vostede podería usar algo como unha lista ligada e pode percorrer a lista de introducir Alicia antes de Bob e Charlie despois de Bob e así por diante. E, de feito, se queres ver o código así como un aparte, sei que en list2.h, facemos exactamente isto. Non vai pasar por este código, pero esta é unha variante do primeiro exemplo que introduce outra struct que xa vimos antes estudante chamado, e entón o que realmente almacena na lista vinculada é un punteiro para unha estrutura de estudante en vez de enteiro un pouco simple, n. Entón, entendo que hai código alí que implica cordas reais, Pero se o obxectivo en mans realmente agora é resolver o problema da eficiencia, Non sería bo se nós estamos dando un obxecto chamado Alice, queremos poñer-la no lugar correcto, nunha estrutura de datos, parece que sería moi bo para só poñer Alicia, cuxo nome comeza con A, no primeiro lugar. E Bob, cuxo nome comeza con B, na segunda posición. Con unha matriz, ou imos comezar chamándoo de unha táboa, a táboa hash en que, podemos facer exactamente isto. Se nos é dado un nome como Alicia, unha secuencia como Alicia, onde pon a-l-i-c-e? Necesitamos un hueristic. Necesitamos dunha función para sacar algunha entrada como Alicia e voltar unha resposta, "Alicia Pon este lugar." E esta función, esta caixa negra, vai ser chamado de función hash. Unha función hash é algo que ten unha entrada, como "Alicia", e volta para ti, normalmente, a localización numérica nalgunha estrutura de datos onde Alicia pertence. Neste caso, a función hash debe ser relativamente sinxela. A nosa función hash debe dicir, se está dado "Alicia", que o personaxe debería me importar? O primeiro. Entón eu ollo para [0], e entón eu digo si [0] carácter é A, voltar o número 0. Se é B, voltar 1. Se é C, o retorno 2, e así por diante. Todos índice 0, e que me permita inserir Alicia e Bob e Charlie e así por diante para esa estrutura de datos. Pero hai un problema. O que se Anita vén de novo? Onde poñemos Anita? O seu nome tamén comeza coa letra A, e parece que fixemos unha confusión aínda maior do problema. Temos agora a inserción inmediata, inserción constante de tempo, para unha estrutura de datos en vez de peor caso lineal, pero o que podemos facer con Anita neste caso? Cales son as dúas opcións, realmente? Si? [Responder Estudante, inintelixible] Ok, entón nós poderíamos ter outra dimensión. Isto é bo. Así, podemos construír cousas en 3D como falamos verbalmente o luns. Poderiamos engadir outro acceso aquí, pero creo que non, eu estou tentando manter isto simple. O obxectivo xeral aquí é ter acceso constante de tempo inmediato, de xeito que é a adición de moita complexidade. Cales son as outras opcións ao tentar inserir Anita para esta estrutura de datos? Si? [Responder Estudante, inintelixible] Boa. Entón, nós poderíamos pasar todo o mundo para abaixo, como Charlie cutuca baixo Bob e Alicia, e entón poñemos Anita onde realmente quere ser. Está claro que, agora, hai un efecto colateral desta. Esta estrutura de datos é probablemente útil non porque queremos introducir a xente xa senón porque queremos comprobar se eles están alí máis tarde se queremos imprimir os nomes na estrutura de datos. Nós imos facer algo con eses datos, eventualmente. Entón agora nós medio que parafuso sobre Alicia, que non é máis onde debería estar. Non é Bob, nin é Charlie. Entón quizais iso non é unha boa idea. Pero, en realidade, esta é unha opción. Nós poderiamos cambiar todos para abaixo, ou diaños, Anita chegou atrasado para o xogo, por que non imos só poñer Anita aquí non, aquí non, aquí non, imos poñer-la un pouco máis abaixo da lista. Pero, entón, este problema comeza a devolver de novo. Pode ser capaz de atopar Alicia instantaneamente, con base no seu nome. E Bob instantaneamente, e Charlie. Pero entón mira para Anita, e ve, hein, Alice está no camiño. Ben, deixe-me ver abaixo Alicia. Bob non é Anita. Charlie non é Anita. Oh, hai Anita. E se seguir ese tren da lóxica toda a maneira, o que é o tempo de execución do peor caso de atopar ou inserción de Anita para esta nova estrutura de datos? É O (n), non? Porque, no peor dos casos, hai Alicia, Bob, Charlie. . . todo o camiño para alguén chamado "Y", polo que hai só un punto á esquerda. Afortunadamente, non temos un chamado "Z", entón poñemos Anita na parte inferior. Nós realmente non resolveu o problema. Entón quizais necesitamos introducir esta terceira dimensión. E non é que se non introducir esta terceira dimensión, non podemos facelo perfectamente, pero o Santo Graal vai estar recibindo constante de tempo de inserción e dinámicos para que as insercións non temos a hard-código dunha matriz de tamaño 26. Podemos introducir tantos nomes como queremos, pero imos dar o noso intervalo de 5 minutos aquí e despois facelo correctamente. Todo ben. Eu define a historia ata moi artificialmente hai escollendo Alicia e Bob e Charlie e Anita, cuxo nome foi, obviamente, vai chocar con Alice. Pero a pregunta que terminou o luns con só quão probable é que quere obter eses tipos de colisións? Noutras palabras, se comezar a usar esa estrutura de táboa, que é realmente só unha matriz, neste caso, de 26 posicións, E se os nosos insumos son distribuídos uniformemente en vez? Non é artificialmente Alicia e Bob e Charlie e David e así por diante en orde alfabética, é uniformemente distribuída ao longo da a Z. Quizais nós imos ter sorte e non imos ter dous un ou dous de B con probabilidade moi alta, pero como alguén apuntou, este problema xeneralizado e non 0-25 pero, digamos, de 0 a 364 ou 65, moitas veces, o número de días nun ano típico, e fixo a pregunta: "Cal é a probabilidade de que dous de nós nesta sala ten a mesma data de aniversario?" Dito doutra forma, cal é a probabilidade de que dous de nós ten un nome que comeza coa? O tipo de pregunta é a mesma, pero este espazo de enderezos, este espazo de procura, é maior no caso de aniversarios, porque temos tantos días de máis o ano que letras no alfabeto. Cal é a probabilidade dunha colisión? Ben, podemos pensar niso por descubrir as matemáticas de forma oposta. Cal é a probabilidade de colisións non? Ben, esa expresión aquí di que o que é a probabilidade hai só unha persoa neste cuarto, que ten un aniversario? É 100%. Porque se hai só unha persoa na sala, seu aniversario pode ser calquera dos 365 días fóra do ano. Logo, as opcións 365/365 me dá un valor de 1. Así, a probabilidade en cuestión no momento é só 1. Pero se hai unha segunda persoa no cuarto, cal é a probabilidade de que o seu aniversario é diferente? Hai só 364 días posibles, anos bisestos, ignorando para o seu aniversario para non chocar con outras persoas. Así, 364/365. Unha terceira persoa entra, é 363/365, e así por diante. Así, continúan multiplicando xunto destas fraccións, que están ficando cada vez menores, para descubrir cal é a probabilidade de que todos temos aniversarios orixinais? Pero, entón, podemos, por suposto, pode ter esa resposta e lanzalo ao redor de e facer 1 menos de todo isto, unha expresión que vai finalmente chegar se recorda a parte de atrás dos seus libros de matemáticas, que parece un pouco algo como isto, que é moito máis facilmente interpretado graficamente. E este gráfico aquí ten no eixe x o número de aniversarios, ou o número de persoas con aniversarios, e no eixe y é a probabilidade dunha saída. E o que iso está dicindo é que se ten, digamos, ata, imos escoller algo así como 22, 23. Se hai 22 ou 23 persoas na sala, a probabilidade de que dúas desas poucas persoas van ter o mesmo aniversario é realmente super alta, combinatoriamente. 50% as probabilidades de que unha clase de só 22 persoas, dun seminario, practicamente, 2 de esas persoas van ter o mesmo aniversario. Porque hai moitas maneiras en que pode ter o mesmo aniversario. Peor aínda, se ollar para o lado dereito da gráfica, no momento en que ten unha clase con 58 alumnos en que, a probabilidade de dúas persoas que teñan un aniversario é alta, super super, preto do 100%. Agora, iso é unha especie de traxe divertido sobre a vida real. Pero as implicacións, agora, para estruturas de datos e almacenamento de información significa que só supoñendo que ten un bo, distribución, limpa e uniforme de datos e ten unha matriz grande abondo para caber unha morea de cousas non significa que está indo para obter as persoas en lugares exclusivos. Vai ter colisións. Polo tanto, esta noción de hash, como se chama, tomando unha entrada como "Alicia" e Masaxes-o de algunha maneira e despois volver unha resposta como 0 ou 1 ou 2. Voltar algunha saída desa función é atormentado por esa probabilidade de colisión. Entón, como podemos tratar con esas colisións? Ben, en ningún caso, podemos ter a idea de que foi suxerido. Podemos só cambiar todos para abaixo, ou quizais, un pouco máis simple, en vez de todos os outros movemento, imos mover Anita para o fondo do local dispoñible. Entón, se Alice está en 0, Bob está en 1, Charlie está en 2, imos poñer Anita na localización 3. E esta é unha técnica en estruturas de datos chamado lineal enquisa. Lineal porque está só camiñando nesa liña, e é unha especie de sondaxe para os lugares dispoñibles na estrutura de datos. Por suposto, este transfórmase en O (n). A estrutura de datos é realmente completo, hai 25 persoas que xa, e Anita vén, ela acaba co que sería localización Z, e iso é bo. Ela aínda encaixa, e podemos atopala máis tarde. Pero iso era contrario ao obxectivo de acelerar as cousas. Entón, o que se creou, esa terceira dimensión? Esta técnica é xeralmente chamado encadeamento separado, ou que posúan cadeas. E o que unha táboa hash é agora, esta estrutura tabular, súa táboa é só unha matriz de punteiros. Pero o que os punteiros apuntan para adiviñar o que é? Unha lista ligada. Entón, o que se aproveitar o mellor de ambos os mundos? Usan matrices para os índices iniciais na estrutura de datos, de xeito que pode inmediatamente ir a [0] [1], [30], ou así por diante, pero para que poidamos ter algunha flexibilidade e podemos encaixar Anita e Alice e Adam e calquera nome de outro, nós pero deixar que o outro eixe crecer de forma arbitraria. E finalmente, a partir do luns, ten esa capacidade expresiva con lista encadeada. Podemos crecer unha estrutura de datos de forma arbitraria. Alternativamente, podemos só facer unha matriz de 2 dimensións enormes, pero que vai ser unha situación terrible unha das liñas dunha matriz de 2 dimensións non é suficientemente grande para a persoa cuxo nome adicional acontece a comezar con A. Deus nos libre de ter que recolocar unha estrutura 2-dimensional enorme só porque hai tantas persoas denominados A, especialmente cando hai tan poucas persoas nomeadas algo Z. El só vai ser unha moi escasa estrutura de datos. Polo tanto, non é perfecto, por calquera medio, pero agora polo menos temos a capacidade Para atopar onde Alicia ou Anita pertence, polo menos en termos de eixe vertical, e despois só temos que decidir onde poñer Anita ou Alice nesta lista ligada. Se non nos importa con clasificando as cousas, que rapidez podemos inserir Alicia nunha estrutura como esta? É tempo constante. Nós índice para [0], e se non hai ninguén, Alicia vai no inicio desta lista ligada. Pero isto non é un gran negocio. Porque se Anita entón vén un número de pasos despois, onde é que Anita pertence? Ben, [0]. POO. Alicia xa está na lista ligada. Pero, se non lle importan a clasificación destes nomes, podemos só pasar máis de Alicia, inserción Anita, pero iso é tempo constante. Mesmo se hai Alicia e Adán e todos eses outros nomes A, non está realmente cambiando-los fisicamente. Por que? Porque nós fixemos aquí con lista encadeada, quen sabe se estes nós son ao final? Todo o que tes que facer é mover as migas de pan. Move as frechas ao redor, non ten que mover fisicamente todos os datos ao redor. Así, podemos introducir Anita, nese caso, instantaneamente. Tempo constante. Polo tanto, temos de tempo constante de investigación e de tempo constante inserción de alguén como Anita. Pero tipo de simplificar o mundo. O que máis tarde quere atopar Alicia? O que máis tarde quere atopar Alicia? Cantos pasos que vai levar? [Responder Estudante, inintelixible] Exactamente. O número de persoas antes de Alicia na lista ligada. Polo tanto, non é perfecta, porque a nosa estrutura de datos, unha vez máis, ten este acceso vertical e el ten esas listas ligadas de suspensión - na verdade, non imos deseñar unha matriz. Ten estas listas ligadas colgado fóra del que se parece un pouco algo como isto. Pero o problema é se Alicia e Adán e todos eses outros nomes A acabar máis e máis para alí, atopar alguén pode acabar levando unha morea de pasos, bcause ten que atravesar a lista ligada, que é unha operación lineal. Entón, realmente, a continuación, o tempo de inserción, en última análise é O (n), onde n é o número de elementos na lista. Dividido por, imos chamalo arbitrariamente m, onde m é o número de listas ligadas que temos neste eixe vertical. Noutras palabras, se realmente asumir unha distribución uniforme de nomes, totalmente irrealista. Hai, obviamente, máis de algunhas letras que outros. Pero se nós asumimos para o momento dunha distribución uniforme, e temos n total de persoas, e m correntes totais á nosa disposición, a continuación, a lonxitude de cada unha destas cadeas forma moi simple, será o total, n, dividido polo número de cadeas. Así, n / m. Pero aquí é onde podemos ser todo matematicamente intelixente. m é unha constante, porque non hai un número fixo de estes. Está indo para declarar a matriz en principio, e non estamos redimensionando o eixe vertical. Por definición, que permanece fixo. É só o eixe horizontal, por así dicir, iso está cambiando. Entón, tecnicamente, é unha constante. Entón, agora, o tempo de inserción é moi fermoso o (n). De xeito que non se sente todo o que moito mellor. Pero o que hai de certo niso? Ben, todo este tempo, por semanas, estamos dicindo o (n ²). O (n), 2 x n ², - n, dividido por 2. . . ech. É só ² n. Pero agora, nesta parte do semestre, podemos empezar a falar sobre o mundo real novo. E n / m é absolutamente máis rápido que só n soa. Se ten mil nomes, e división las en varios baldes para que teña só 10 nomes en cada unha destas cadeas, absolutamente buscar 10 cousas vai ser máis rápido que mil cousas. E así un dos conxuntos de problemas futuros vai desafia-lo para pensar sobre exactamente que, a pesar de si, assintoticamente e matematicamente, iso aínda é só lineal, que suga, en xeral, ao tentar atopar as cousas. En realidade, o que vai ser máis rápido que debido a este divisor. E así, alí está de novo vai ser este trade-off e este conflito entre a teoría ea realidade, e un dos botóns vai comezar a xirar neste punto no semestre é máis a realidade como un tipo de preparar para o final de semster, como imos introducir no mundo da programación web, onde realmente, o rendemento vai contar porque os seus usuarios están indo para comezar a sentir e apreciar as decisións de deseño pobre. Entón, como vai facer sobre a implementación dun conectado - dunha táboa hash con 31 elementos? E o exemplo anterior foi arbitrariamente sobre aniversarios. Se alguén ten un aniversario de 01 de xaneiro ou 01 de febreiro, imos poñer-los neste balde. Se é 02 de xaneiro, 02 de febreiro, 2 de marzo, nós imos poñer-los neste balde. É por iso que foi de 31. Como declarar unha táboa hash? Pode ser moi sinxelo, mesa * ó é o meu nome arbitrario para el, [31]. Tanto me dá 31 consellos para nós, e que me permite ter 31 punteiros para listas ligadas aínda que estas correntes son inicialmente NULL. O que quero poñer, se eu queira gardar "Alicia", "Bob", "Charlie"? Ben, é preciso involucrar esas cousas nunha estrutura porque necesitamos Alicia para apuntar para Bob, para apuntar para Charlie, e así por diante. Non podemos só ter os nomes só, entón eu podería crear unha nova estrutura chamada no aquí. ¿Que é un nodo real? ¿Que é un nodo nesta nova lista ligada? O primeiro, chamado palabra, é o nome da persoa. Lonxitude, presuntamente, refírese ao lonxitude máxima do nome dun ser humano, sexa o que sexa, 20, 30, 40 personaxes en casos de canto tolo, e un é para o que? É só o carácter NULL extra, \ 0. Polo tanto, este nodo é embrulho "algo" dentro de si, pero tamén declara un punteiro chamado seguinte para que poidamos cadea de Alicia para Bob para Charlie e así por diante. Pode ser NULL, pero non necesariamente ten que ser. Calquera dúbida sobre estas táboas de hash? Si? [Estudante pedindo cuestión, inintelixible] Unha matriz - boa pregunta. ¿Por que esta palabra char nunha matriz en vez de só char *? Neste exemplo un tanto arbitraria, eu non quería ter que recorrer para malloc para cada un dos nomes orixinais. Eu quería declarar unha cantidade máxima de memoria para a cadea para que eu puidese copiar a estrutura de Alicia \ 0 e non ter que tratar con malloc e free e similares. Pero eu podería facelo se eu quería ser máis consciente do uso do espazo. Boa pregunta. Entón, imos tratar de xeneralizar lonxe deste e centrar o resto de hoxe en estruturas de datos máis xeral e outros problemas que pode resolver empregando os mesmos fundamentos aínda que as estruturas de datos elas mesmas poden diferir nos seus detalles. Así, verifícase en ciencia da computación, as árbores son moi comúns. E pode pensar nunha especie de árbore como unha árbore xenealóxica, onde hai algunhas raíces, algúns matriarca ou patriarca, avó ou avoa ou máis cedo de volta, baixo o cal están a nai eo pai ou irmáns diversas ou similares. Así, unha estrutura de árbore ten nós e ten fillos, xeralmente 0 ou máis nenos para cada nó. E algúns dos xerga que ve nesta foto aquí é calquera das nenos pequenos ou netos nas beiras que non teñen frechas que emanan a partir deles, estas son as follas chamados, e calquera persoa no interior é un nó interior, pode chamalo de calquera cousa nese sentido. Pero esa estrutura é moi común. Este aquí é un pouco arbitraria. Temos un fillo á esquerda, temos tres fillos, á dereita, dous nenos no ángulo inferior esquerdo. Así podemos ter diferentes tamaños de árbores, pero se comezar a estandarizar as cousas, e pode chamar este vídeo Patrick en busca binaria dun curto anterior investigación, en liña binario non ten que ser aplicado con unha matriz ou anacos de papel en un cadro negro. Supoña que vostede quería para almacenar os seus números nunha estrutura de datos máis sofisticados. Vostede podería crear unha árbore coma esta. Pode ter un nó declarado en C, e que o nodo pode ter, polo menos, dous elementos no interior do mesmo. Un deles é o número que desexa almacenar, eo outro é - ben, necesitamos máis. A outra é os seus fillos. Entón, aquí está outra estrutura de datos. Desta vez, o nó defínese como o almacenamento dun número n e, a continuación, dous punteiros, neno esquerdo e dereito do neno. E eles non son arbitrarias. O que é interesante sobre esta árbore? Cal é o estándar en forma como temos colocado iso ou como Patrick colocouse no seu vídeo? É medio obvio que hai algunha ordenación suceder aquí, pero o que é a regra simple? Si? [Responder Estudante, inintelixible] Perfecto. Se ollar para iso, ve os números pequenos de esquerda, grandes números do lado esquerdo, pero iso é certo para cada nó. Para cada nodo, o seu fillo esquerdo inferior, e á súa neno dereita máis grande que. O que isto significa que agora é que se eu queira buscar esta estrutura de datos, por exemplo, o número 44, Eu teño que comezar na raíz, porque, como con todas estas estruturas máis complexas de datos, agora, Temos só un punteiro para unha cousa, o inicio. E, neste caso, o inicio é a raíz. Non é o lado esquerdo, é a raíz desta estrutura. Entón eu vexo aquí é 55, e eu estou buscando 44. Cal dirección que quero ir? Ben, eu quero ir á esquerda, porque, obviamente, á dereita vai ser moi grande. Entón, observe aquí, é unha especie de conceptualmente cortar a árbore en media porque nunca está indo para o lado dereito. Entón agora eu ir do 55 ao 33. É moi pequeno de un número. Estou na procura de 44, pero agora sei se 44 é nesta árbore, podo ir, por suposto, á dereita. Entón, de novo, eu son a poda da árbore no medio. É practicamente idéntico conceptualmente para o libro de teléfono. É idéntico ao que fixemos cos papeis no cadro negro, pero é unha estrutura máis sofisticada, que nos permite realmente facer este dividir e conquistar, polo deseño do algoritmo, e, de feito, atravesando unha estrutura como esta - berros. Atravesando unha estrutura como esta, onde é só "ir por este camiño ou ir por ese camiño", significa todo o código que que dobrado a súa mente en primeiro lugar cando implementar lo na sección ou andar con el na casa, por busca binaria, usando recursão ou iteração, é unha dor no pescozo. Atopar o elemento do medio, a continuación, facer o seu redondeo cara arriba ou cara abaixo. Hai unha beleza a este, porque agora podemos utilizar recursão novo, pero moito máis limpa. En realidade, se está no número 55 e quere atopar 44, vaia á esquerda, neste caso, entón o que fai? Vostede corre o algoritmo exacto. Vostede verifica o valor do nodo, entón vai cara á esquerda ou á dereita. Entón comprobar o valor do nodo, vai cara á esquerda ou á dereita. Isto é perfectamente adecuado para a recursividade. Así, aínda que no pasado fixemos algúns exemplos bastante arbitrarias que implica recursão que non debe ser recursiva, con stuctures de datos, especialmente árbores, é unha perfecta aplicación desta idea de levar un problema, reducindo-a, e logo a solución do mesmo tipo de, pero menor do programa. Polo tanto, hai outra estrutura de datos que podemos presentar. Este é proxectada a primeira vista ollar enigmático, pero este é incrible. Polo tanto, esta é unha estrutura de datos chamada trie, trie, que é herdado da recuperación de palabra, que non é pronunciado re-try-val, pero é o que o mundo chámase esas cousas. Intenta. T-r-i-e. É unha estrutura de árbore de calquera tipo, pero cada un de nós nun trie parece ser o que? E iso é un pouco erro, porque é unha especie de abreviado. Pero parece que cada nodo neste trie é na verdade unha matriz. E aínda que o autor deste diagrama non demostrou que, neste caso, este trie é unha estrutura de datos cuxo propósito na vida é almacenar palabras como A-l-i-c-e ou B-o-b. E a maneira pola cal os datos tendas Alicia e Bob e Charlie e Anita e así por diante é que usa unha matriz para almacenar que Alicia nunha trie, comezamos o nodo raíz que se parece unha matriz, e que foi escrito en notación abreviada. O autor omitido abcdefg porque non había nomes con iso. Eles só mostrou M e P e T, pero neste caso, imos pasar lonxe de Alicia e Bob e Charlie para algúns nomes que están aquí. Maxwell é realmente neste diagrama. Entón, como o almacenamento de autor M-a-x-w-e-l-l? El ou ela comezou no nodo raíz, e foi para [M], de xeito máis ou menos 13, o lugar 13 na matriz. Entón, a partir de aí, hai un punteiro. Un punteiro levando a outro array. A partir de aí o autor indexados en que a matriz na posición A, como se mostra alí enriba, á esquerda, e despois que el ou ela seguiu ese punteiro a outra matriz, e foi para o punteiro no lugar X. A continuación, na seguinte localización matriz W, E, L, L, e así por diante, e, finalmente, imos realmente tentar poñer unha imaxe para iso. O que fai un nó como no código? Un nó nunha trie contén unha matriz de punteiros para nós máis. Pero hai tamén debe haber algún tipo de valor booleano, polo menos nesta aplicación. Acontece que eu chamalo is_word. Por que? Porque cando está inserindo Maxwell, non está inserindo nada a esta estrutura de datos. Non está escribindo M. Non está escribindo X. Todo o que está facendo é seguir punteiros. O punteiro que representa M, entón o punteiro que representa a, a continuación, o punteiro que representa X, a continuación, W, E, L, L, pero o que ten que facer ao final é unha especie de balde, comprobar, cheguei a este sitio. Había unha palabra que termina aquí na estrutura de datos. Entón, o que unha trie é realmente cheo e co autor escolleu para representar Estes terminuses con pequenos triángulos. Isto só significa que o feito de este triángulo está aquí, este valor booleano verdadeiro significa que se ir cara atrás na árbore, significa que unha palabra é chamado Maxwell neste. Pero a palabra foo, por exemplo, non está na árbore, porque se eu comezar no nodo raíz aquí enriba, Non hai punteiro f, ningún punteiro o, non o punteiro. Foo non é un nome neste dicionario. Pero por outro lado, turação, t-u-r-i-n-g. Unha vez máis, eu non almacenar t ou u ou r ou i ou n ou g. Pero eu fixen na tenda esta estrutura de datos dun valor verdadeiro camiño ata aquí neste nó - na árbore definindo ese valor booleano de is_word a verdade. Así, un trie é unha especie de esta estrutura meta moi interesante, onde non está realmente gardar as propias palabras para este tipo de dicionario. Para ser claro, só está almacenando si ou non, non é unha palabra que termina aquí. Agora, cal é a implicación? Se ten 150 mil palabras nun dicionario que estás almacenar na memoria usar algo como unha lista ligada, vai ter 150 mil nós na súa lista ligada. E atopar unha desas palabras en orde alfabética pode levar tempo O (n). Tempo lineal. Pero no caso aquí dunha trie, o que é o tempo de execución de atopar unha palabra? Acontece que a beleza aquí é que, mesmo se ten 149.999 palabras xa neste dicionario, como aplicado con esta estrutura de datos, canto tempo leva para atopar ou inserir unha persoa que, como Alicia, Alicia? Ben, é só 5, quizais 6 pasos para o personaxe de fuga. Porque o presense doutros nomes na estrutura non estar no camiño de entrada de Alicia. Ademais, atopar Alicia xa que hai 150.000 palabras neste dicionario non entrar no seu camiño de atopar Alicia en todo, porque Alicia é. . . . . aquí, porque eu atope un valor booleano. E se non hai booleano verdadeiro, entón Alicia non está na esta estrutura de datos de palabras. Noutras palabras, o tempo de execución de atopar as cousas e inserindo as cousas para este novo estrutura de datos de trie é o de - non é n. Porque o presense de 150.000 persoas non ten efecto sobre Alicia, que parece. Entón, imos chamalo de k, onde k é o lonxitude máxima dunha palabra en inglés que é, tipicamente, non máis que 20 e poucos caracteres. Así, k é unha constante. Así, o Santo Graal que parecen ter atopado agora é o dunha vez, trie constante para pastillas para investigacións, por eliminacións. Como o número de cousas xa na estrutura, que non son nin mesmo físicamente alí. Unha vez máis, eles están só unha especie de DESestablecido, si ou non, non ten impacto no seu tempo futuro en execución. Pero ten que ser un problema, se non, non tería perdido tanto tempo en todas estas estruturas de datos outros só para finalmente chegar ao un segredo que é incrible. Entón, cal é o prezo que estamos pagando para alcanzar esa grandeza aquí? Espazo. Esa cousa é enorme. E a razón que o autor non presenta-lo aquí, destacar que todas esas cousas que se parecen con matrices, non debuxar o resto da árbore, o resto do trie, porque son non só relevantes para a historia. Pero todos estes nós son super grande, e cada nodo na árbore ocupa 26 ou, en realidade, podería ser de 27 carácteres, porque neste caso eu estaba incluído espazo para o apóstrofo para que pudéssemos ter palabras apostrofado. Neste caso, trátase se matrices de ancho. Así, aínda que eles non están picutured, iso leva a unha enorme cantidade de RAM. O que pode ser bo, especilly en hardware moderno, pero esa é a cambio. Temos menos tempo, gastan máis espazo. Entón, onde é que isto vai? Ben, imos facer - imos ver aquí. Imos facer un salto este cara aquí. Acreditar ou non, divertido como C foi xa hai algún tempo, estamos chegando ao punto en que, no semestre é hora de transición para as cousas máis modernas. Cousas nun nivel superior. E aínda que para o próximo par de semanas imos continuar a mergullo no mundo de punteiros e xestión de memoria para ese confort coa que podemos entón construír, O xogo final é, finalmente, para introducir, ironicamente, non esta linguaxe. Nós imos gastar, como 10 minutos falando HTML. Todo o HTML é unha linguaxe de marcación, e que é unha linguaxe de marcación é é esta serie de soportes abertos e pechados soportes que din "facer este bold ' "Facer esta cursiva" "facer esta centrada." Non é todo o que intelectualmente interesante, pero é super útil. E é certamente omnipresente nos días de hoxe. Pero o que é poderoso sobre o mundo do HTML e programación web en xeral, constrúe cousas dinámicas; escribir código en linguaxes como PHP ou Python ou Ruby ou Java ou C #. Realmente, calquera que sexa o idioma da súa elección, e xerar HTML dinamicamente. Xerando unha cousa chamada CSS dinamicamente. Follas de estilo en cascada, o que é tamén sobre a estética. E por iso mesmo que, hoxe, se eu for a algún sitio como o Google.com familiar, e vou ver, creador, fonte de visión, que talvez teña feito antes, pero vai ver o código fonte, este material probablemente parece moi enigmática. Pero este é o código subxacente que aplica Google.com. No extremo dianteira. E, de feito, todo isto é cousa de estética gordo. Este é CSS aquí. Se eu continuar a rolagem para abaixo imos incorporarse algunhas cousas con código de cores. Este é HTML. Código de Google parece unha desorde, pero realmente abrir unha xanela distinta, podemos ver algunha estrutura para iso. Se eu abrir isto, observe aquí, é un pouco máis lexible. Nós imos ver en pouco tempo esa marca, [palabra] é unha etiqueta, HTML, cabeza, corpo, div, guión, área de texto, extensión, centrado, div. E esta é tamén clasificar de aparencia enigmática, a primeira vista, pero toda esta confusión segue certos patróns e normas repetitivos, de modo que unha vez que temos o básico para abaixo, vai ser capaz de escribir un código coma este e, entón, manipular o código como esta usando outra linguaxe, chamada de JavaScript. E JavaScript é unha linguaxe que roda dentro dun navegador hoxe, que usan en Harvard cursos, a ferramenta de compras curso que usa mapas de Google para darlle unha morea de dinamismo, Facebook ofrece a vostede para amosar actualizacións de estado instantánea, Twitter usa para amosar o tweets instantaneamente. Todo iso, imos comezar a mergullo dentro Pero para chegar alí, necesitamos entender un pouco sobre a Internet. Este clip aquí é só un minuto de duración, e imos asumir por agora este é, de feito, como a Internet funciona como un teaser para o que está por vir. Eu darlle "Guerreiros do líquido." [♫ ♫ música lenta coro] [Narrador Masculino] El veu con unha mensaxe. Con un protocolo de todo o seu. [♫ ♫ música Faster electrónico] El veu para un mundo de firewalls frías, insensibles routers, e perigos moito peores que a morte. El é rápido. El é forte. El é o TCP / IP, e ten o seu enderezo. Guerreiros da rede. [Malan] Na próxima semana, entón. Internet. Programación web. Este é CS50. [CS50.TV]