[MÚSICA DE XOGO] DAVID J. Malan: Todo ben. Este é CS50. Esta é semana de cinco continuou, e nós teño unha boa noticia e unha mala noticia. Entón bo é que CS50 lanza este venres. Se desexa unirse a nós, cabeza para o URL de costume aquí. Unha noticia aínda mellor, ningunha charla vindeiro luns día 13. Pouco menos mellor noticia, cuestionario cero é mércores. Máis detalles poden ser atopados neste URL aquí. E ao longo dos próximos dous días estaremos cubrindo os espazos en branco no que se refire aos cuartos que teremos reservados. Mellor é que non vou ser unha revisión de todo o curso sesión o próximo Luns pola noite. Sexa en conta para o curso de Sitio web para localización e detalles. Seccións, aínda que sexa un vacacións, tamén vai atender ben. Mellor noticia, charla na próxima venres. Polo tanto, esta é unha tradición que teñen, segundo o contido programático. Apenas-- que será incrible. Vai ver cousas como estruturas de datos de tempo constante e táboas de hash e árbores e intentos. E imos falar sobre os problemas de aniversario. Unha morea de cousas agarda próxima venres. Está ben. De calquera forma. Entón lembro que fomos focando esta imaxe do que está dentro da memoria do noso ordenador. Así, a memoria ou a memoria RAM é onde os programas existir mentres está executando-os. Se fai clic dúas veces un icona para realizar algún programa ou prema dúas veces nun icona para abrir un arquivo, el é cargado dende o disco duro ou unidade de estado sólido na memoria RAM, Random Access Memory, onde el vive ata se apagar, a tapa pecha portátil, ou saír do programa. 

Agora que a memoria, de que probablemente ten 1 gigabyte nos días de hoxe, 2 gigabytes, ou mesmo moito máis, xeralmente é colocado para fóra para un determinado programa neste tipo de rectangular modelo conceptual polo que temos a pila na parte inferior e unha morea de outras cousas na parte superior. O superior vimos nesta imaxe antes, pero nunca falamos sobre é o chamado segmento de texto. Segmento de texto é só un xeito elegante de dicir os ceros e uns que compoñer o seu programa compilado real. 

Entón, cando fai clic dúas veces Microsoft Word no seu Mac ou PC, ou ao executar o punto barra Mario nun Ordenador Linux na súa fiestra de terminal, os ceros e uns que compoñen Word ou Mario almacénanse temporalmente na memoria RAM do seu ordenador na chamada segmento de texto para un programa particular. Abaixo diso vai iniciar e datos non inicializado. Este é o material como variables globais, que non usei moitos, pero de cando en vez temos tiña as variábeis globais ou estaticamente cordas definido que é codificado palabras como "Ola" que non son tidos en do usuario que son codificados no seu programa. 

Agora, para abaixo na parte inferior nós ter a pila de chamada. E a pila, ata agora, temos sido usando para que tipo de efectos? Que a pila foi utilizado? Si? 

Audiencia: Funcións. 

DAVID J. Malan: Para funcións? En que sentido para as funcións? 

Audiencia: Cando chamar unha función, o argumentos son copiados para a pila. 

DAVID J. Malan: Exactamente. Cando chama unha función, a argumentos son copiados para a pila. Así, calquera Xs ou Y do ou dun ou B que está pasando a unha función son temporalmente colocados en a pila así chamado, só como un dos Annenberg bandexas salón-comedor, e tamén as cousas como variables locais. Se a súa función foo ou a súa cambio función de variables locais, como temperatura, estes dous acabar na pila. Agora, non imos falar moito sobre eles, pero estas variables de ambiente na parte inferior que vimos hai un tempo atrás, cando Estaba mexendo no teclado dun día e comece a acceder cousas argv como 100 ou argv 1000, só elements-- eu esquezo Números de a, pero que Non era para acceder por min. Comezamos a ver algúns símbolos funk na pantalla. Aqueles eran chamados variables de ambiente como opcións globais para o meu programa ou para o meu ordenador, non sen relación coa recente erro que discutir, Shellshock, que foi asola moi poucos ordenadores. 

Agora, para rematar, en foco de hoxe que en definitiva será na pila. Este é un anaco de memoria. E todo isto fundamentalmente memoria é o mesmo. É o mesmo hardware. Somos só unha especie de tratamento de distintos grupos de bytes para distintos fins. A pila tamén será onde variables e memoria que solicitar desde o sistema operativo é temporalmente almacenado. 

Pero hai un tipo de problema aquí, como a foto indica. Nós medio que temos dous barcos a piques de chocar. Porque, como se usa cada vez máis do conxunto, e como vemos hoxe para adiante, como se usa cada vez máis a pila, seguramente as cousas malas poden ocorrer. E, de feito, podemos inducir que intencionalmente ou non. Así, o suspense última tempo era ese programa, que non serven calquera funcional outro propósito ademais de demostrar como como un cara mal realmente pode ter vantaxe de erros no programa de alguén e asumir un programa ou un sistema informático ou servidor de todo. Entón, só para ollar brevemente, ten ter en conta que o principal na parte inferior toma en liña de comandos argumentos, por argv. E ten unha chamada a unha función f, esencialmente unha función de chamada sen nome f, e está pasando en argv [1]. 

Entón, calquera palabra que o usuario escribe en polo a solicitude despois do nome deste programa, e pode que a función arbitraria up top, f, leva nunha corda, aka char *, como comezamos a discutir, e el simplemente chama de "bar". Pero poderiamos chamalo nada. E entón el declara, dentro de f, unha serie de caracteres chamado C-- 12 destes personaxes. 

Agora, pola historia que eu estaba dicindo un momento atrás, onde na memoria c é, ou son aqueles 12 PERSONAXES vai acabar? Só queda claro. Si? 

Audiencia: Na pila. 

DAVID J. Malan: Na pila. Así, c é unha variable local. Estamos pedindo para 12 caracteres ou 12 bytes. Aqueles van acabar na pila de chamadas. Agora, por fin, se esta outra función que é realmente moi útil, pero non usei moito nós mesmos, strncopy. Significa copia corda, pero só n letras, n caracteres. Entón n caracteres será copiado bar en c. E cantos? A lonxitude da barra. Así, noutras palabras, que unha liña, strncopy, vai copiar efectivamente bar no c. 

Agora, só a especie de anticipar A moral desta historia, o que é potencialmente problemático aquí? Aínda que estamos comprobando a lonxitude de bar e pasala en strncopy, o que é o seu intestino dicindo é aínda roto sobre este programa? Si? 

Audiencia: Non inclúe espazo para o carácter nulo. DAVID J. Malan: Non inclúe espazo para o carácter nulo. Potencialmente, a diferenza de as prácticas do pasado que nin sequera ten tanto como unha vantaxe de 1 a acomodar ese carácter nulo. Pero é aínda peor que iso. Que máis estamos deixando de facer? Si? 

Audiencia: [inaudível] DAVID J. Malan: Perfecto. Nós codificado 12 moi arbitrariamente. Isto non é tanto a problema, pero o feito que non estamos aínda comprobando se a lonxitude da barra é menos que 12, caso en que será seguro para poñelas na memoria chamada c que temos asignado. Efectivamente, se a barra é así 20 caracteres, esta función parece estar copiando 20 personaxes de bar en c, así, tendo, polo menos, 8 bytes que non deben ser. Esta é a implicación aquí. 

Así, no programa curto, roto. Non como un gran negocio. Quizais comeza un fallo de segmento. Todos nós xa tivemos erros nos programas. Todos nós pode ter erros en programas de agora. Pero cal é a implicación? Ben, aquí está unha versión máis grande-in de que imaxe de memoria do meu ordenador. Este é o fondo do meu stack. E, de feito, ben no fondo é o que se chamado pila rutina pai, forma extravagante de dicir que é principal. Así que quen chamou a función f que estamos a falar. Así, este é o fondo da pila. Enderezo de retorno é algo novo. El sempre estivo alí, sempre estiven nesa imaxe. Nós só nunca chamou atención a el. Porque sucede o camiño c funciona é que cando unha función chama outra, non só os argumentos para que función son empurrados para a pila, non só local de función variables son empurrados para a pila, algo chamado un enderezo de retorno tamén é colocado na pila. En concreto, as chamadas principais Foo, principais do propio enderezo en memoria, algo boi, efectivamente colócase na pila de xeito que, cando f está feito de executa-lo sabe onde saltar de volta no texto segmento, a fin de continuar a execución. 

Entón, se estamos aquí, conceptualmente, na principal, entón f é chamada. Como f saber quen para control de man de volta? Ben, este pequeno breadcrumb en vermello aquí, chamado a dirección de retorno, el só cheques, que é o que a dirección de retorno? Oh, déixeme ir de volta a principal aquí. E iso é algo dunha simplificación, porque os ceros e uns para principal son tecnicamente aquí enriba no segmento de tecnoloxía. Pero esa é a idea. f só ten que saber o que en definitiva, no que o control de volta. 

Pero o xeito no que os ordenadores Hai moito tempo establecidas as cousas como variables locais e argumentos é así. Así, na parte superior da imaxe en azul é o cadro de pila para f, entón todo da memoria que f especialmente se emprega. Entón, nese sentido, entender que bar é neste marco. Bar era o seu argumento. E defendeu que os argumentos para funcións son empurrados para a pila. E c, por suposto, é Tamén nesta foto. 

E só para fins de notación, conta na esquina superior esquerda é o que sería c soporte 0 e entón lixeiramente abaixo á dereita é c soporte 11. Polo tanto, noutras palabras, pode imaxinar que hai unha reixa de bytes hai, en primeiro lugar, que é superior esquerda, abaixo do que é o último dos 12 bytes. 

Pero agora tentar avanzar. O que está a ocorrer se pasarmos nun bar de cadea que é máis que c? E non estamos comprobando se é de feito maior que 12. Cal parte da imaxe vai se substituído por bytes 0, 1, 2, 3, dot dot dot, 11, e, a continuación, malo, 12, 13 a 19? O que vai ocorrer aquí, inferir a partir da ordenación que c 0 soporte está na parte superior ec soporte 11 é unha especie de abaixo á dereita? Si? 

Audiencia: Ben, que vai para substituír o bar char *. 

DAVID J. Malan: Si, parece que está indo a substituír carbón bar *. E peor, se publique nun tempo moi longo cadea, pode ata substituír o que? O enderezo de retorno. Que unha vez máis, é como un breadcrumb para dicir ao programa onde volver cando f está feito de ser chamado. 

Entón, o que bandas adoitan facer é se atopou con un programa que son curiosos se é explorável, cesta, de tal xeito que el ou ela pode tomar vantaxe deste erro, xeralmente non reciben este dereito por primeira vez. Eles só comezar a enviar, por exemplo, secuencias aleatorias no seu programa, no teclado, ou, francamente probablemente escribir un pequeno programa para só xerar automaticamente cordas, e comezar a bater o seu programa o envío de lotes de entradas diferentes en diferentes lonxitudes. 

Así que os seus fallos do programa, iso é unha cousa incrible. Porque isto significa que el ou ela descubriu o que probablemente é de feito un erro. E entón poden ser máis intelixente e comezar a concentrarse máis estreitamente sobre o xeito de explotar ese erro. En particular, o que el ou ela pode facer é enviar, no mellor dos casos, Ola. Non é gran cousa. É unha cadea que é suficientemente curto. Pero e se el ou ela envía, e imos xeneralizar-lo como, ataque code-- tan ceros e os que fan as cousas rm-rf como, que elimina todo dende o disco duro ou enviar spam ou de algunha maneira a atacar máquina? 

Por iso, cada unha delas letras A só representa, conceptualmente, ataque, ataque, ataque, ataque, un código malo que alguén escribiu, pero se esa persoa é intelixente dabondo non só para incluír todos destes rm-RFS, pero tamén que os seus últimos bytes ser un número que corresponde ao enderezo do seu ou o seu propio código de ataque que el ou ela pasou en só , Dando-lle o poder, pode efectivamente enganar o ordenador para entender cando f faise en execución, Oh, é hora de eu ir de volta ao enderezo do remitente vermella. Pero por que el ou ela ten de algunha maneira sobrepostas que a dirección de retorno co seu propio número, e son intelixentes abondo configurar que número para referirse, como ver no super top esquina esquerda alí, a dirección real no ordenador de memoria de parte do seu código de ataque, un bandido pode enganar o ordenador para realizar o seu propio código. 

E ese código, unha vez máis, pode ser calquera cousa. É xeralmente chamado código shell, que é só unha forma de dicir que non é xeralmente algo tan simple como rm-rf. Realmente algo como Bash, ou un programa real que lle dá ou o seu control programático para realizar calquera outra cousa que eles queren. Entón, en definitiva, todo isto deriva do simple feito que este erro non implica a comprobación os límites da súa matriz. E por que o camiño ordenadores de traballo é que utilizar a pila efectivamente, conceptualmente, inferior enriba, pero, a continuación, os elementos empurrar para a pila crecer de arriba abaixo, iso é moi problemático. Agora, hai formas de evitar isto. E, francamente, hai linguas coa que traballar en torno a este. Java é inmune, por exemplo, a esta cuestión particular. ¿Por que non darlle indicacións. Eles non dan a vostede enderezos de memoria directas. Así, con este poder que temos tocar nada na memoria que queremos vén, en realidade, un gran risco. 

Polo tanto, manter un ollo para fóra. Se, a verdade, nos meses ou anos, a calquera hora ler sobre algunha explotación dun programa ou dun servidor, se xa viu un toque de algo como un ataque de estourido de buffer, ou estourido de pila é outro tipo de ataque, semellante en espírito, tanto como inspira o sitio web da nome, se sabe diso, todo está falando só rebordando o tamaño dalgún personaxe matriz ou matriz dalgún modo máis xeral. Todas as preguntas, entón, sobre este asunto? Non intente facer iso na casa. 

Todo correcto. Entón malloc, ata agora, foi o noso novo amigo no que podemos reservar memoria que non saben necesariamente en avanzar que queremos de xeito que non temos código ríxido na nosa Os números de programas como 12. Unha vez que o usuario nos di o que datos que el ou ela quere de entrada, podemos malloc que moita memoria. 

Entón malloc se ve, ao medida en que temos que chegou a utilizar, explicitamente última vez, e logo vostedes teñen usado para GetString sen saber para varias semanas, todos a memoria do malloc vén o chamado chea. E é por iso getString, por exemplo, pode reservar memoria dinámica sen saber o que está a vai escribir con antelación, entrega-lo de volta un punteiro para a memoria, e que a memoria aínda é o seu para manter, mesmo despois getString retorna. Como recordo despois de todo o que o pila está constantemente indo para arriba e abaixo, arriba e abaixo. E así que vai abaixo, isto significa que calquera memoria Esta función debe non ser usado por calquera persoa. É valores de lixo agora. 

Pero a pila está aquí enriba. E o que é agradable sobre malloc é que cando malloc aloca memoria ata aquí, non é afectado, pois o maior parte dos casos, por a pila. E así calquera función pode acceder memoria que foi malloc'd, incluso por unha función como getString, mesmo despois de ser devoltos. 

Agora, o inverso do malloc é gratuíto. E, de feito, a regra que Debe comezar a adoptar é calquera, calquera, calquera hora que usar malloc pode usar-se libre, finalmente, o mesmo punteiro. Todo este tempo que vimos escribir erros, código de buggy, por moitas razóns. Pero un dos cales foi a través da biblioteca de CS50, que en si é deliberadamente Buggy, que perdas de memoria. Cada vez que chamou getString ao longo das últimas semanas estamos pedindo a operación sistema, Linux, para a memoria. E nunca xa dado de volta. E iso non é, en practicar, bo. 

E Valgrind, unha das ferramentas introducidas no Pset 4, é todo a axudar agora atopar erros coma este. Pero, por sorte para Pset 4 non necesita para usar a biblioteca CS50 ou getString. Así, os erros relacionados coa memoria son en definitiva, será o seu propio. 

Entón malloc é máis que conveniente para este propósito. De feito, podemos agora resolver fundamentalmente diferentes problemas, e, fundamentalmente, resolver problemas máis eficaz como promesa á semana ceros. Ata agora, esta é a máis sexy estrutura de datos que tivemos. E por estrutura de datos Eu só quero dicir unha forma de memoria conceituar dunha forma que vai alén de só dicir: este é un enteiro, este é un caracter. Podemos comezar coas cousas de cluster xuntos. 

Así, un conxunto coma este. E o que foi fundamental en aproximadamente unha matriz é que lle dá back-to-back anacos de memoria, cada unha das cales será do mesmo tipo, int int, int, int ou char, char, char, car. Pero hai algunhas desvantaxes. Este, por exemplo, é unha matriz de tamaño seis. Supoña que enche esa matriz con seis números e, a continuación, por calquera motivo, o usuario quere dar vostede un sétimo número. Onde puxo? 

Cal é a solución se ten creada unha matriz sobre a pila, por exemplo, só coa semana dous notación que introducimos, de corchetes cun número dentro? Ben, ten seis números nestas caixas. Que os seus instintos ser? Onde quere poñelas? 

Audiencia: [inaudível] 

DAVID J. Malan: Sentímolo? 

Audiencia: Pon-o ao final. 

DAVID J. Malan: Pon-o ao final. Entón, só para a dereita, fóra da caixa. O que sería bo, pero Acontece que non pode facelo. Porque se non pediu a este anaco de memoria, podería ser casualidade que este está sendo usado por outra variable completamente. Debería de volta unha semana ou así cando poñemos os nomes de Zamyla e Davin e Gabe na memoria. Estaban literalmente back to back to back. Polo tanto, non podemos necesariamente confiar que todo de aquí está dispoñible para eu usar. 

Entón o que máis pode facer? Ben, xa que entender precisa dunha matriz de tamaño sete, pode simplemente crear un matriz de tamaño sete entón usar un loop ou un loop while, copia-lo para o novo matriz, e, a continuación, dalgún xeito, se librar de esa matriz ou simplemente deixar de usalo. Pero iso non é especialmente eficiente. En suma, as matrices non deixe redimensionar dinamicamente. 

Así, por unha banda, obtén de acceso aleatorio, que é incrible. Porque nos permite facer cousas como dividir e conquistar, busca binaria, todos os cales temos falou na pantalla aquí. Pero pintar só nun canto. Así que acertar o fin da súa matriz, ten que facer unha moi operación dispendiosa ou escribir unha morea de código agora xestionar este problema. 

Entón, o que se no canto tivemos algo chamado unha lista, ou unha lista ligada en particular? E se en vez de ter rectángulos volta atrás cara atrás, temos rectángulos que deixan un pouco pouco espazo de manobra entre eles? E aínda que eu deseño este foto ou adaptado esta foto dende un dos textos aquí para volver ao volta atrás moi ordenada, en realidade, un deses rectángulos podería estar aquí na memoria. Un deles podería ser ata aquí. Un deles podería ser ata aquí, aquí, e así por diante. 

Pero o que se chamou, neste caso, frechas que dalgún xeito vincular estes rectángulos xuntos? De feito, vimos un técnico encarnación dunha frecha. O que temos usado nos últimos anos días que, debaixo do capó, é representativa dunha frecha? Un punteiro, non? 

Entón, o que se, no canto de só almacenar os números, como 9, 17, 22, 26, 34, E se nós non gardados só un número, pero un enlace xunto a cada número tal? Entón, que así como enfiar unha agulla través de unha chea de tecido, cousas de algunha maneira de subordinación en conxunto, de xeito semellante pode nós con punteiros, como encarnado por frechas aquí, tipo de tecer deses rectángulos individuais por efectivamente usando un punteiro xunto a cada número que apunta para algún número seguinte, que indica, á súa vez, algúns próximo número? Polo tanto, noutras palabras, o que se realmente quería para aplicar algo coma isto? Ben, sentímolo, estes rectángulos, , Polo menos, un con 9, 17, 22, e así por diante, estes non son máis prazas agradables con números individuais. O fondo, rectángulo por baixo de 9, por exemplo, representa o que debe ser un punteiro, 32 bits. Agora, eu non estou ao tanto de calquera tipo de datos en C que lle dá non só un int pero un enlace completo. 

Entón, cal é a solución, se quere inventar a nosa propia resposta a iso? Si? 

Audiencia: [inaudível] 

DAVID J. Malan: ¿Que é iso? 

Audiencia: Nova estrutura. 

DAVID J. Malan: Si, entón por que Non podemos crear unha nova estrutura, ou en C, un struct? Vimos estruturas antes, brevemente, onde lidamos cunha estrutura de estudante como este, que tiña un nome e unha casa. En Pset 3 fuga usou un todo banda de GRect structs-- e GOvals Stanford que creou a información de cluster xuntos. Entón, o que se tomamos esa mesma idea de as palabras clave "typedef" e "struct" e, a continuación, algunhas cousas específicas do alumno, e evolucionar esta no seguinte: typedef struct node-- e nodo é só unha ciencia da computación moi xenérico prazo para algo nunha estrutura de datos, un recipiente, dunha estrutura de datos. Un nó Eu reivindico terá un int n, totalmente simple, e, a continuación, un pouco máis enigmaticamente, Nesta segunda liña, nó struct * próximo. Pero, en termos menos técnicos, que é o que a segunda liña de código dentro das claves? Si? 

Audiencia: [inaudível] David J. Malan: Un punteiro a outro nodo. Entón, en realidade, sintaxe algo enigmática. Pero se le-lo, literalmente, logo é o nome dunha variable. Cal é o seu tipo de datos? É un pouco prolixo, esta vez, pero é o tipo de nodo struct *. Calquera vez que vimos algo estrela, que significa que é un punteiro para este tipo de datos. Entón, a próxima é, ao parecer, un punteiro para un nó de struct. 

Agora, o que é un nodo struct? Ben, observe que ve os mesmas palabras na esquina superior dereita. E, de feito, tamén verá a palabra "Nó" aquí abaixo na parte inferior esquerda. E iso é realmente só unha conveniencia. Teña en conta que na nosa definición de estudante hai a palabra "alumno" só unha vez. E iso é porque un alumno obxecto non era auto-referencial. Non hai nada dentro dun estudante que debe apuntar a outro estudante, persay. Iso sería unha especie de estraño no mundo real. 

Pero, cun nó nunha ligada lista, queremos un nó para ser referencial a un obxecto semellante. E así entender o cambio aquí non é só o que está dentro das chaves. Pero engadir a palabra "nó" , Na parte superior, así como engadindo-o ao fondo no canto de "alumno". E este é só un detalle técnico de xeito que, de novo, a súa estrutura de datos pode ser auto-referencial, de xeito que a nó pode apuntar a outro tal nó. 

Entón o que é iso, en última instancia significará para nós? Ben, un, este material dentro é o contido do noso nó. Esta cousa aquí enriba, superior dereita, é tan que, unha vez máis, podemos referirnos a nós mesmos. E entón as cousas máis externa, aínda nodo é un novo termo quizais, aínda o é mesmo como estudante e que estaba debaixo do capó en SPL. 

Entón, se nós agora quería comezar implantación desta lista ligada, como podemos traducir algo así para codificar? Ben, imos ver unha exemplo dun programa que en realidade, emprega unha lista ligada. Entre código de distribución de hoxe é un programa chamado Lista Cero. E se eu executar este creei un super GUI simple, Interface gráfica de usuario, pero é realmente só printf. E agora que eu me dei algunhas menú opções-- DELETE, INSERT, Investigación, e Traverse. E Saír. Estes son só operacións comúns nun estrutura de datos coñecida como lista de enlace. 

Agora Eliminar vai eliminar un número da lista. Inserir vai engadir un número á lista. Busca vai mirar ao número da lista. E travesía é só un xeito elegante de dicir, percorrer a lista, imprimir lo, pero é iso. Non cambia-lo de calquera maneira. 

Entón, imos tentar iso. Imos adiante e escriba 2. E entón eu vou inserir o número, din 9. Intro. E agora o meu programa é só programa para dicir lista é agora 9. Agora, se eu ir adiante e que introducir de novo, imos me ir adiante e diminuír o zoom e escriba 17. Agora, a miña lista é 9, entón con 17 anos. Se eu fai introducir de novo, imos saltar un. No canto de 22, segundo a imaxe que teño estado a ollar a aquí, déixeme pasar adiante e introducir 26 próximo. Entón eu vou para escribir 26. A lista é como eu esperaba. Pero agora, só a ver se este código será flexible, deixe-me agora Tipo 22, o cal, polo menos conceptualmente, se temos Tendo isto resolto, o que é de feito será outro obxectivo, agora, debe ir entre 17 e 26. Entón eu prema Intro. En realidade, iso funciona. E agora déixeme introducir o pasado, por a imaxe, 34. 

Todo correcto. Entón, por agora, deixe-me estipulan que Eliminar e Traverse e Investigación facer, de feito, traballar. En realidade, se eu executar investigación, imos busque o número 22, Intro. Constatouse que 22. Entón é iso que este Programa Lista Cero fai. 

Pero o que realmente está a suceder en que aplica isto? Ben, primeiro eu podería, e de feito Eu teño un arquivo chamado list0.h. E nalgún lugar existe esa liña, typedef, nó struct, entón eu teño as miñas chaves, int n, e entón struct-- cal era a definición? Nó struct seguinte. Por iso, necesitamos da estrela. Agora, tecnicamente, entrar o costume de debuxar-lo aquí. Podes ver libros didácticos e referencias en liña facelo alí. É funcionalmente equivalente. En realidade, iso é un pouco máis típico. Pero eu vou ser coherente co que fixemos a última vez e facelo. E entón, finalmente, eu vou facer iso. 

Así, nun ficheiro de cabeceira nalgún lugar, en list0.h hoxe é esta definición struct, e quizais algunhas outras cousas. Mentres tanto, na list0c hai Vai ser algunhas cousas. Pero imos só comezar e non rematar isto. List0.h é un arquivo que quero para incluír no meu arquivo C. E entón, nalgún momento eu son terá int, principal, anular. E entón eu vou Ten algún de tarefas está aquí. Eu tamén vou ter un prototipo, como baleiro, procura, int, n, cuxo propósito na vida é para buscar un elemento. E entón aquí eu afirmo en código de hoxe, baleiro, procura, int, n, ningún punto e coma, pero claves abertas. E agora quero buscar algunha maneira para un elemento da lista. Pero non temos o suficiente información sobre a pantalla aínda. Eu non teño, de feito, representaba a propia lista. Polo tanto, unha forma que puidésemos aplicar unha lista ligada dun programa é que eu medio que quero facer algo como declarar lista ligada aquí. Para simplificar, vou facer este mundial, aínda que en xeral nos non debe facelo máis. Pero vai simplificar este exemplo. Entón, quero declarar unha lista ligada aquí. Agora, como eu podería facelo? 

Aquí está a foto dunha lista encadeada. E eu realmente non saber o momento como Eu estou indo a ir sobre a representación tantas cousas con só un variable na memoria. Pero creo que volta un momento. Todo este tempo que tivemos cordas, que despois revelouse como matrices de caracteres, que despois revelou ser só un punteiro para o primeiro carácter nun array de caracteres que ten un terminador nulo. Entón, por esa lóxica, e con iso tipo de imaxe de sementar os seus pensamentos, Para que necesitamos realmente escribir na nosa código para representar unha lista ligada? Como moitas desas información que necesitamos para capturar en código C, diría? Si? 

Audiencia: Necesitamos un punteiro para un nó. DAVID J. Malan: Un punteiro para un nó. En particular, o que sería o seu nó instintos ser para manter un punteiro para? 

Audiencias: O primeiro nodo. 

DAVID J. Malan: Si, probablemente só o primeiro. E teña en conta, o primeiro nó é unha forma distinta. É só a metade do tamaño da estrutura, porque é en realidade só un punteiro. Entón, o que realmente pode facer é declarar unha lista ligada a ser do tipo nodo *. E imos chamalo de primeira e inicialize-o como nulo. Entón, null, unha vez máis, está chegando en escena aquí. Non só é nulo usado como como un especial valor de retorno para cousas como getString e malloc, nulo é tamén o cero punteiro, a falta dun punteiro, se quere. Significa só que nada está aínda aquí. Agora en primeiro lugar, eu podería chamou iso de nada. Podería telo chamado "lista" ou calquera número de outras cousas. Pero eu estou chamando-o de "primeira" para que se aliñan con esta imaxe. Así como unha corda pode ser representado co enderezo do seu primeiro byte pode así unha lista ligada. E veremos outros datos estruturas ser representado con só un punteiro, unha frecha de 32 bits, que apunta o primeiro nodo na estrutura. 

Pero agora imos anticipar un problema. Se eu só estou recordando no meu programa a dirección do primeiro nodo, o primeiro rectángulo nesta estrutura de datos, o mellor que sexa o caso sobre a implantación do resto da miña lista? ¿Que é un detalle clave que está a suceder para asegurar que realmente funciona? E por "realmente funciona" Eu É dicir, moi parecido cunha corda, permítenos ir desde o primeiro carácter en nome do Davin para o segundo, para o terceiro, o cuarto, ata o final, como sabemos cando estamos ao final dunha lista encadeada que se parece con isto? Cando é nulo. E eu teño representado este tipo de como como unha forza enxeñeiro eléctrico, co pouco de terra símbolo, das sortes. Pero iso só significa nulo neste caso. Pode deseñar calquera número de formas, pero o mesmo autor pasou a usar este símbolo aquí. 

Mentres nós estamos amarre todos estes nodos xuntos, só lembrando que o primeiro é, desde como poñer un símbolo especial no o último nó na lista, e usaremos nulo, porque iso é o que temos á nosa disposición, esta lista está completa. E aínda que eu só darlle un punteiro para o primeiro elemento, que, o programador, certamente pode acceder ao resto. Pero imos deixar as súas mentes vagar un pouco, se eles non están xa moi wandered-- o que é será o tempo de execución atopar algo nesa lista? Porra, é grande o de n, que non está mal, na xustiza. Pero é lineal. Temos dado o recurso de matrices movendo máis para ese cadro de forma dinámica entrelazados ou nós conectados? Nós desistimos de acceso aleatorio. Unha matriz é bo porque matematicamente todo está de volta para facer a volta atrás. Aínda que esta foto parece moito, e mesmo pero parece que estes nós son ben espazos entre si, en realidade poderían estar en calquera lugar. OX 1, Ox50, Ox123, Ox99, estes nós podería estar en calquera lugar. Porque malloc aloca memoria do conxunto, pero en calquera lugar do heap. Non necesariamente sabe que é será back to back to back. E así esta foto en realidade non vai ser moi esta fermosa. 

Entón, que vai levar un pouco de traballar para aplicar esta función. Entón, imos aplicar a investigación agora. E nós imos ver unha especie de xeito intelixente de facelo. Entón, se eu son unha función de busca e Eu son dado unha variable, enteiro n buscar, eu teño que saber o nova sintaxe para ollar para dentro dunha estrutura que está apuntou, para atopar n. Entón, imos facelo. 

Entón, primeiro eu vou adiante e declarar un nó *. E eu vou chamalo punteiro, só por convención. E eu estou indo a arrincar o primeiro. E agora podo facelo nun número de formas. Pero eu vou ter unha visión común. Mentres anotador non coincide null, e iso é válido sintaxe. E iso significa só facer o seguinte, de xeito Sempre que non está a apuntar cara ao nada. O que quero facer? 

Se punteiro punto n, déixeme volver para que, equals-- iguala o que? Cal o valor que eu estou buscando? O n real que foi pasado. Entón aquí está a outra característica de C e moitas linguas. Aínda que a estrutura chamada nodo ten un valor de n, totalmente lexítimo ter un argumento locais ou variable chamada n. Porque aínda que, con Os ollos humanos, pódese distinguir que esta n é presuntamente diferente deste n. Porque a sintaxe é diferente. Ten un punto e un punteiro, mentres este non ten tal cousa. Entón, iso é OK. Isto é OK para chamar-lles as mesmas cousas. 

Se eu non atopar iso, eu son Vai querer facer algo como anunciar que atopamos n. E nós imos deixar isto como un comentar ou código de pseudocódigo. Outra cousa, e aquí está o parte interesante, o que gustaríame facer se o nodo actual non se conteñen n que eu me importa? ¿Como conseguir o seguinte? Se o meu dedo na momento é PTR, e é apuntando para o que quere que primeiro está a apuntar, ¿Como mover meu dedo ao nodo seguinte código? Ben, cal é a ruta que estamos vai seguir neste caso? Audiencia: [inaudível]. DAVID J. Malan: Si, por iso a continuación. Entón, se eu volver para o meu código aquí, en realidade, eu son indo a ir adiante e dicir punteiro, que é só un variable-- temporal é un nome raro, PTR, pero é como temp-- Vou configurar o punteiro igual a calquera punteiro é-- e unha vez máis, que vai ser un buggy pouco para un punto moment-- seguinte. Noutras palabras, eu vou tomar o meu dedo que está a apuntar para este nodo aquí e eu vou dicir, xa sabe o que, bótalle un ollo ao seguinte campo e mover o dedo sexa o que está a apuntar. E iso vai repetir, repetir, repetir. Pero cando o meu dedo deixar de facer algo? Tan pronto que liña de código en patadas? Audiencia: [inaudível] DAVID J. Malan: Si o punto mentres punteiro non é igual a null. Nalgún momento o meu dedo do estará apuntando nulo e eu estou indo a entender isto é o final da lista. Agora, este é un pouco mentirinha para simplificar. Acontece que, aínda que acaba de aprender esta notación de punto para estruturas, o punteiro non é un struct. PTR é o que? Só para ser máis detallista. É un punteiro para un nó. Non é un nó en si. Se eu non tiña ningunha estrela aquí, punteiro absolutely-- é un nó. Isto é debido a unha semana declaración dunha variable, aínda que a palabra "nó" é novo. 

Pero así que introducir un estrela, agora é un punteiro para un nó. E, por desgraza, non pode usar a notación de punto para un punteiro. Ten que usar a frecha notación, o que, sorprendentemente, é a primeira vez que unha peza de sintaxe parece intuitiva. Isto literalmente parece unha frecha. E iso é unha cousa boa. E aquí embaixo, literalmente parece unha frecha. Entón, eu creo que é a la-- non creo que estou over-cometer aqui-- I creo que é a última peza nova de sintaxe, xa veremos. E, por sorte, é de feito algo máis intuitivo. 

Agora, para aqueles de vostedes que pode preferir a vella forma, Aínda pode usar a notación de punto. Pero por luns de conversa, primeiro que ir alí, ir a ese abordar, a continuación, acceder ao campo. Entón, iso tamén é correcto. E, francamente, este é un pouco máis pedante. Está literalmente dicindo, desreferenciava o punteiro e ir máis alá. Logo, cara .n, o campo chamado n. Pero, francamente, ninguén quere para escribir ou ler isto. E así o mundo inventado a notación de frecha, que é equivalente, idéntica, é só un azucre sintático. Así, un xeito elegante de dicir iso parece mellor, ou parece máis simple. 

Entón, agora eu vou facer outra cousa. Eu vou dicir "romper" xa que eu penso tan non seguir mirando para el. Pero esta é a esencia dunha función de investigación. Pero é moito máis doado, no final, non andar a través do código. Este é de feito a implementación formal de investigación en código de distribución de hoxe. Ouso dicir que inserir non é particularmente diversión a pé visualmente, nin borrar, mesmo con todo, ao final do día eles se resumen a moi heurísticas simple. 

Entón, imos facelo. Se vai humor me aquí, eu fixen traer unha morea de bolas de estrés. Eu trouxo unha morea de números. E poderiamos obter uns poucos voluntarios para representar a 9, 17, 20, 22, 29, e 34? Entón, basicamente todo quen está aquí hoxe. Isto foi un, dous, tres, catro, cinco, seis persoas. E eu fun convidado a vai-- ver, non unha na parte de atrás levanta as mans. OK, un, dous, tres, catro, cinco-- déixeme subir balance-- seis. OK, vostede seis suba. Imos ter que outros. Trouxo estrés bolas extras. E se podería, por só un momento, a liña -vos só como esta foto aquí. 

Todo correcto. A ver, cal é o seu nome? 

Audiencia: Andrew. 

DAVID J. Malan: Andrew, é o número 9. Pracer en coñece-lo. Aquí vai. Audiencia: Jen. DAVID J. Malan: Jen. David. Número 17. Si? 

Audiencia: Eu son Julia. 

DAVID J. Malan: Julia, David. Número 20. Audiencia: Christian. DAVID J. Malan: Christian, David. Número 22. E? 

Audiencia: JP. DAVID J. Malan: JP. Número 29. Entón vai adiante e obter em-- Uh oh. Uh oh. Espérase. 20. Alguén ten un favorito? Audiencia: Eu teño unha sharpie. DAVID J. Malan: Ten un sharpie? Está ben. E alguén ten un anaco de papel? Salva a charla. Veña. Audiencia: Temos iso. DAVID J. Malan: Temos isto? Todo ben, grazas. Aquí imos nós. Foi iso de ti? Acaba de salvar o día. Entón, 29. Todo correcto. Eu mal escrito 29, pero Aceptar. Continúe. Todo ben, eu vou che dar a pluma de volta momentaneamente. Entón, temos esas persoas aquí. Imos ter outro. Gabe, quere xogar o primeiro elemento aquí? Imos ter que vostede para ligar a estas persoas finas. Entón, 9, 17, 20, 22, especie de 29, e despois 34. Será que imos perder alguén? Eu teño un 34. Onde fez-- OK, quen quere ser 34? OK, imos para arriba, 34. Todo ben, este será valeu a pena o clímax. Cal é o seu nome? 

Audiencia: Peter. 

DAVID J. Malan: Peter, imos cara arriba. Todo ben, entón aquí está un grupo enteiro de nós. Cada un de vós representa un deses rectángulos. E Gabe, a un pouco raro home para fóra, representa o primeiro. Así, o seu punteiro é algo menor na pantalla do que todos os outros. E neste caso, cada un a súa esquerda mans vai ou apuntar cara a abaixo, representando, así, nulo, de xeito só na ausencia dun punteiro, ou que vai estar apuntando nun nó xunto a ti. 

Entón, agora, se adornar vós similares a imaxe aquí, vai adiante e punto un para o outro, con Gabe en particular, que apunta ao o número 9 para representar a lista. OK, eo número 34, a súa man esquerda debe só estar apuntando para o chan. 

OK, entón esta é a lista encadeada. Polo tanto, este é o escenario en cuestión. E, de feito, este é representante dunha clase de problemas que pode tentar resolver co código. Quere introducir en última instancia un novo elemento na lista. Neste caso, imos intente inserir o número 55. Pero non vai ser casos diferentes a considerar. E, de feito, este será un do gran-retrato takeaways aquí, é, cales son os diferentes casos. Cales son os distintos as condicións ou ramas que o programa poida ter? 

Ben, o número que estás inserción, que sabemos agora para ser 55, pero se non sabía con antelación, eu diría cae, polo menos, tres situacións posibles. Onde pode un elemento novo ser? Audiencia: E o fin ou medio. David J. Malan: Ao final, en no medio, ou no inicio. Entón, eu afirmo que hai polo menos tres problemas que necesitamos resolver. Imos escoller o que é, se cadra, sen dúbida o máis simple un, en que o novo elemento pertence ao principio. Entón, eu vou ter bastante código como buscar, o que eu acabo de escribir. E eu vou ter PTR, que Vou representar aquí co meu dedo, como de costume. 

E lembre, o valor fixemos arrincar PTR para? Por iso, el inicializar como nulo inicialmente. Pero entón o que fixemos, xa que estaban dentro da nosa función de procura? Nós configure-lo igual ao primeiro, o que non significa facelo. Se eu definir PTR igual ao primeiro, o que debe ser realmente a miña man apuntando? Certo. Entón, se Gabe e eu imos ser valores iguais aquí, necesitamos tanto do punto no número 9. 

Polo tanto, este foi o inicio da nosa historia. E agora este é só simple, aínda que a sintaxe é novo. Conceptualmente, esta é só a busca lineal. É 55 igual a 9? Ou mellor, imos dicir menos que 9. Porque eu estou tentando descubrir onde poñer 55. Menos de 9, menos de 17, menos de 20, menos de 22, menos de 29, menos que 34, n. Polo tanto, agora estamos en caso un de polo menos tres. 

Se eu queira inserir 55 para aquí, o que liñas de código necesidade de ter executado? Como é que ese cadro de os seres humanos necesitan cambiar? O que fago coa man esquerda? Isto debe ser inicialmente nula, porque eu estou no final da lista. E o que debe ocorrer aquí con Peter, foi? Está, obviamente, vai apuntar para min. Entón, eu afirmo que hai polo menos dúas liñas de código no código de exemplo a partir de hoxe que vai aplicar este escenario de adición de 55 na cola. E eu podería alguén hop e representan só 55? Todo ben, que é o novo 55. 

Entón, agora que o próximo escenario ven xunto, e queremos introducir o inicio ou a cabeza de lista? E cal é o seu nome, o número 55? 

Audiencia: Jack. 

DAVID J. Malan: Jack? OK, pracer de coñece-lo. Benvido a bordo. Entón agora nós imos introducir, por exemplo, o número 5. Este é o segundo caso do tres nós vimos con antes. Así, se pertence 5 ao principio, imos ver como podemos descubrir iso. Eu arrincar o meu PTR punteiro ao 9 de novo. E podo entender, oh, 5 é inferior a 9. Entón corrixir esta foto para nós. Cuxas mans, Gabe é David de ou-- cal é o nome do número 9? 

Audiencia: Jen. 

DAVID J. Malan: hands-- de Jen que das nosas mans que cambiar? OK, entón Gabe apunta ao que agora? Para min. Eu son o novo nodo. Entón eu vou tipo de movemento aquí para velo visualmente. E mentres tanto o que eu apuntar isto? Aínda así, onde estou a apuntar. Entón é iso. Entón, só realmente unha liña de correccións de código esta cuestión en particular, ao parecer. Todo ben, entón iso é bo. E alguén pode ser un marcador a 5? Imos cara arriba. Nós imos aproveitar vostede da próxima vez. 

Todo ben, entón agora-- e Como un aparte, os nomes Eu non estou facendo mención explícita de dereito agora, punteiro pred, punteiro antecesor e novo punteiro, que é só os nomes dado no código de exemplo para os punteiros ou miñas mans que é tipo de apuntar ao redor. Cal é o seu nome? 

Audiencia: Christine. 

DAVID J. Malan: Christine. Benvido a bordo. Todo ben, entón imos considerar agora un escenario un pouco máis aburrido, polo cal quero inserir algo así como 26 para iso. 20? O que? Estes é-- cousa boa que temos esta pluma. Todo ben, 20. Se alguén puidese ter outra peza de papel preparado, só en caso-- todo ben. Oh, interesante. Ben, este é un exemplo dun erro charla. OK entón, cal é o seu nome? Audiencia: Julia. DAVID J. Malan: Julia, pode pop para fóra, e finxir que nunca foron alí? OK, iso nunca sucedeu. Grazas. Entón, supoña que queremos inserir Julia para esta lista ligada. Ela é o número 20. E, por suposto, é vai pertencer ao begin-- non apuntan nada aínda. Entón a súa man se pode tipo de valor nulo ou algún lixo. Imos contar a historia rápida. Estou apuntando ao número 5 esta vez. Entón eu verifico 9. Entón eu verifico 17. Entón eu verifico 22. E eu entendo, ooh, Julia que ir antes de 22. Entón, o que ten que ocorrer? Cuxas mans que cambiar? Julia, miña, ou-- Cal é o seu nome? 

Audiencia: Christian. 

DAVID J. Malan: Christian ou? 

Audiencia: Andy. 

DAVID J. Malan: Andy. Christian ou Andy? Andy ten apuntar? Julia. Todo correcto. Entón, Andy, quere apuntar Julia? Pero agarde un minuto. Na historia, ata agora, Eu son o tipo de unha en carga, no sentido de que punteiro é o que é movéndose a través da lista. Podemos ter un nome para Andy, pero non hai ningunha variábel chamada Andy. A única outra variable que temos é primeiro, que está representado por Gabe. 

Polo tanto, este é, en realidade, porque así agora non teño necesidade diso. Pero agora na pantalla existe falar de novo do punteiro pred. Entón deixe-me ser máis explícita. Se esta é punteiro, eu tiña mellor estar un pouco máis intelixente sobre a miña iteración. Se non lle importa de pasar por aquí de novo, que apunta aquí, que apunta aquí. Pero deixe-me ter un punteiro pred, punteiro antecesor, que é tipo de apuntar ao elemento que eu estaba só no. Entón, cando eu ir máis alá, agora miña esquerda actualizacións manuais. Cando vou aquí miñas actualizacións man esquerda. E agora eu teño non só un punteiro para o elemento que vai detrás de Julia, Eu aínda teño un punteiro para Andy, o elemento antes. Entón, ten acceso, esencialmente, fariña de rosca, se quere, para todas as indicacións necesarias. 

Entón, se eu estou a apuntar cara Andy e eu tamén estou a apuntar na cristiá, cuxas mans agora debe ser apuntado noutro lugar? Entón Andy agora pode apuntar Julia. Julia agora pode apuntar Christian. Porque pode copiar a miña punteiro do lado dereito. E que efectivamente pon de volta a este sitio aquí. Así, en breve, aínda que iso está nos levando especie de sempre realmente actualizar un lista ligada, entender que as operacións son relativamente simple. É de un, dous, tres liñas de código ao final. Pero envolto en torno de quen liñas de código presuntamente é un pouco de lóxica que efectivamente fai a pregunta: ¿onde estamos? Estamos no principio, no medio, ou o fin? 

Agora, por suposto hai algunha outra operacións que poidan aplicar. E estas fotos aquí só retratan o que fixemos cos seres humanos. E como a retirada? Se eu queira, por exemplo, eliminar o número 34 ou 55, Podería ter o mesmo tipo de código, pero eu vou ter un ou dous pasos. Porque o que hai de novo? Se eu eliminar alguén ao final, como número 55 e logo 34, o que tamén ten que cambiar como fago isto? Teño que non evict-- Cal é o seu nome? 

Audiencia: Jack. 

DAVID J. Malan: Jack. Teño non só evict-- libre Jack, tan literalmente conectar balde Jack, ou polo menos o punteiro alí tamén, pero agora o que ten que cambiar con Peter? A súa man mellor comezar a apuntar cara a abaixo. Porque así que eu chamo libre en Jack, se de Pedro aínda apuntando para Jack e, polo tanto, eu sigo percorrendo Árbore e acceso este punteiro, que é cando o noso vello amigo segmentación fallo realmente chutar. Porque temos dado o memoria de volta a Jack. 

Pode estar alí torpes por só un momento. Porque temos só un par operacións finais a considerar. Eliminar o cabeza de lista, ou o beginning-- e este de un pouco aburrido. Porque temos que saber que Gabe é unha especie de especial neste programa. Porque, en realidade, ten o seu propio punteiro. Non está só a ser apuntada para, como é case todo o mundo aquí. 

Así, cando a cabeza da lista é eliminada, cuxas mans que cambiar agora? Cal é o seu nome? 

Audiencia: Christine. 

DAVID J. Malan: Eu son terrible en nomes, aparentemente. Entón Christine e Gabe, cuxas mans que cambiar cando tentamos eliminar Christine, número 5, a partir da imaxe? OK, entón imos facer Gabe. Gabe vai apuntar, presuntamente, no número 9. Pero o que debe ocorrer o próximo? Audiencia: Christine debería ser nulo [inaudível]. DAVID J. Malan: OK, nós temos que ser make-- escoitei "nulo" en algún lugar. Audiencia: Null e liberalo la. DAVID J. Malan: null o que? Audiencia: Null e liberalo la. DAVID J. Malan: Null e liberalo la. Entón iso é moi fácil. E é perfecto que agora é especie de pé, non pertencer. Porque foi dissociado da lista. Vostede foi eficaz orfos a partir da lista. E así sería mellor chamar gratuitamente agora Christine dar esa memoria de volta. Se non, cada vez que borrar un nodo da lista fósemos facer a lista máis curto, pero non realmente a diminuír o tamaño da memoria. E así se continuar a engadir e engadindo, engadindo cousas para a lista, meu ordenador pode ser máis lento e máis lento e máis lento, porque eu estou quedando sen memoria, aínda que eu non son realmente usando bytes de Christine de memoria máis. 

Entón, ao final, hai outra escenarios, de eliminación course-- no medio, a eliminación ao final, como vimos. Pero o máis interesante reto agora é será a considerar exactamente que o tempo de execución é. Así, non só pode manter a súa anacos de papel, se, Gabe, non lle importaría de dar todo un balón antiestrés. Moitas grazas á nosa lista ligada de voluntarios aquí, se puidese. 

[Aplausos] 

DAVID J. Malan: Todo ben. Así, un par de analítica preguntas, entón, se eu puidese. Xa vimos que antes de notación, O grande e omega, límites superiores e límites máis baixos no tempo de funcionamento dun algoritmo. Entón, imos considerar só un par de preguntas. 

Un deles, e nós dixemos que antes, o que é o funcionamento tempo de busca por un lista en termos de gran O? ¿Que é un límite superior sobre o funcionamento tempo de busca dunha lista ligada como aplicado polos nosos voluntarios aquí? É grande o de n, lineal. Porque, no peor dos casos, o elemento, como 55, que pode estar a buscar pode ser onde Jack era, todo o camiño ao final. E, por desgraza, a diferenza dun array non podemos comezar a fantasía neste momento. A pesar de todos os nosos seres humanos eran clasificadas desde pequenos elementos, 5, todo o camiño ata o elemento de maior, 55, que xeralmente é unha cousa boa. Pero o que fai esa suposición xa non nos permiten facer? Audiencia: [inaudível] DAVID J. Malan: Diga de novo? Audiencia: acceso aleatorio. DAVID J. Malan: acceso aleatorio. E á súa vez, isto significa que non podemos máis usar ceros feble, intuición, e evidencia de uso de binarios buscar e dividir e conquistar. Porque, aínda nos os seres humanos poderían obviamente ver que Andy é Christian foron máis ou menos no medio da lista, só sabemos que como un ordenador por desnatação á lista dende o principio. Entón, nós temos que desistiu de acceso aleatorio. 

Tan grande O de n agora é o superior grazas no noso tempo de busca. E sobre omega de nosa procura? Cal é o límite inferior na busca para algún número nesta lista? Audiencia: [inaudível] DAVID J. Malan: Diga de novo? Audiencia: One. DAVID J. Malan: One. Tempo tan constante. No mellor dos casos, é Christine de feito, no inicio da lista. E nós estamos a buscar número 5, de xeito que a atopou. Polo tanto, non é gran cousa. Pero ela ten que estar no inicio da lista, neste caso. Que tal algo como eliminar? E se queres eliminar un elemento? Cal é o límite superior e límite inferior sobre a eliminación de algo a partir dun conectado lista? Audiencia: [inaudível] DAVID J. Malan: Diga de novo? Audiencia: n. David J. Malan: n é en realidade, o límite superior. Porque, no peor caso intentamos eliminar Jack, como acabamos de facer. El é todo o camiño ao final. Leva connosco para sempre, ou n pasos para atopalo. Entón, iso é un límite superior. Isto é lineal, con certeza. E o mellor caso de tempo de execución, ou os límites inferiores no mellor dos casos habería tempo constante. Porque quizais a xente probe eliminar Christine, e só ter sorte está no comezo. Agora, agarde un minuto. Gabe tamén estaba en principio, e nós tamén tivemos que actualizar Gabe. Para que non foi só un paso. Entón é iso, xa constante tempo, no mellor dos casos, para eliminar o elemento máis pequeno? É, aínda que poida ser de dous, tres, ou ata 100 liñas de código, se é o mesmo número de liñas, non en algún loop, e independente do tamaño da lista, con certeza. Excluíndo o elemento no o inicio da lista, aínda que teñamos de xestionar Gabe, aínda é tempo constante. 

Polo tanto, este parece ser un enorme paso atrás. E o que é un desperdicio de tempo Se, nunha semana e na semana cero, tivemos non só código pseudocódigo que o código real para aplicar algo que é rexistro base de n, ou rexistro, no seu lugar, de n, base 2, en termos do seu tempo de execución. Entón, por que diaños sería queremos comezar usando algo así como unha lista ligada? Si. 

Audiencia: Entón, pode engadir elementos para a matriz. DAVID J. Malan: Entón pode engadir elementos á matriz. E iso tamén é temática. E imos seguir vendo este, este trade-off, moi como xa vimos un trade-off con merge sort. Nós realmente podería acelerar buscar ou clasificar, no seu lugar, se pasar un pouco máis de espazo e ten un anaco dunha memoria adicional ou unha matriz a merge sort. Pero nós gastamos máis espazo, pero aforrar tempo. Neste caso, estamos dando-se tempo, pero estamos gañando flexibilidade, dinamismo, se quixeren, que é sen dúbida unha característica positiva. 

Tamén estamos gastando espazo. En que sentido é un conectado consultar máis caro en termos de espazo dunha matriz? Onde está o espazo extra vén? Si? 

Audiencia: punteiro [inaudível]. 

DAVID J. Malan: Si, nós tamén ten o punteiro. Entón, iso é aburrido minorly en que non son máis Eu gardar só un int representar un int. Eu son almacenar un int e un anotador, que é tamén de 32 bits. Entón, eu estou literalmente dobrando a cantidade de espazo parte. Entón iso é un trade-off, pero que é, no caso de int. Supoña que non está almacenando int, pero supoño que cada un destes rectángulos ou cada un destes seres humanos estaba representando unha palabra, unha palabra en inglés que pode ser de cinco caracteres, 10 caracteres, quizais ata máis. Logo, engadindo só 32 máis bits pode ser menos de un gran negocio. 

Que cada un dos estudantes na manifestación foron literalmente estruturas estudantís que teñen nomes e casas e quizais números de teléfono e Twitter trata e similares. Así, todos os campos que comezamos falando o outro día, moito menos de un gran negocio, nosos nós están máis interesantes e gran para gastar, eh, un adicional punteiro só para conecta-los. Pero, en realidade, é un trade-off. E, de feito, o código é máis complexa, como vai ver ao percorre que o exemplo concreto. Pero o que se había algún Santo Graal aquí. E se nós non dar un paso cara atrás, pero un gran paso para adiante e aplicar un conxunto de datos estrutura a través do cal se pode atopar elementos como Jack ou Christine ou outros elementos nesa matriz en certo tempo constante? A procura é constante. Eliminar é constante. Insert é constante. Todas estas operacións son constantes. Iso sería o noso Santo Graal. E é aí onde nós vai pegar a próxima vez. Vexo vostedes despois.