[Powered by Google Translate] [Sección 6: menos cómodo] [Nate Hardison] [Harvard University] [Esta é CS50.] [CS50.TV] Todo ben. Benvido á sección 6. Esta semana, imos estar fala de estruturas de datos na sección, principalmente porque o problema desta semana definir spellr fai unha morea de explotación diferente da estrutura de datos. Hai unha morea de maneiras diferentes pode ir co conxunto de problemas, E canto máis estruturas de datos que vostede sabe sobre as cousas máis legais que podes facer. 

Entón imos comezar. Primeiro imos falar sobre pilas, datos da pila e cola estruturas que nós imos falar sobre. Pilas e colas son realmente útiles cando comezamos a falar sobre os gráficos, que non imos facer tanto agora. Pero son moi bos para entender un dos grandes estruturas de datos fundamentais do CS. A descrición da especificación do conxunto de problemas, Se puxar-lo, fala sobre pilas como semellante a a pila de bandexas de comidas que ten na lanchonete nas salas de cea onde cando a cea o equipo vén e pon as bandexas de comida para fóra despois que limpa-los, eles empilhá-los un por riba do outro. E entón, cando os nenos veñen para obter alimentos, eles tiran as bandexas de fóra, primeiro a de arriba, entón o que está abaixo dela, entón a un abaixo diso. Entón, en realidade, a primeira bandexa que a cea o equipo poñer para abaixo é a última que é levado. O último que a cea o equipo poñer é o primeiro que se levou a cea. Na especificación do conxunto de problemas, que podes baixar, se non ten, falamos sobre a modelaxe dun stucture datos da pila empregando este tipo de estrutura. 

Entón, o que temos aquí, que é semellante ao que foi presentado na clase, excepto en charla que presentou esta con ints ao contrario char * s. Esta vai ser unha pila que almacena o que? Daniel? O que estamos almacenando nesta pila? [Daniel] Cordas? >> Estamos almacenar cadeas nesta pila, exactamente. Todo o que ten que ter para crear unha pila é un array dunha capacidade particular, que, neste caso, capacidade vai ser en todas as tapas, pois é unha constante. E entón, ademais da matriz, todo o que necesitamos para seguir é o tamaño actual da matriz. Unha cousa a notar aquí que é legal é que estamos a crear a estrutura de datos empilhada sobre outra estrutura, a matriz. Hai diferentes xeitos de implementar pilas. Non imos facelo bastante aínda, pero espero que despois de facer os problemas de lista vinculada, vai ver como pode facilmente aplicar unha pila enriba dunha lista ligada tamén. Pero, por agora, imos ir con matrices. Entón, de novo, todo o que necesitamos é un array e só necesitamos controlar o tamaño da matriz. [Sam] Sentímolo, por que é o que dixo a pila está na parte superior das cordas? Para min parece que as cordas están dentro da pila. [Hardison] Yeah. Estamos creando, nós estamos levando a nosa matriz de estructura de datos - esta é unha gran cuestión. Entón a cuestión é por iso que, para as persoas que están a asistir esta liña, por que estamos dicindo que a pila está encima das cordas, porque aquí parece que as cordas están dentro da pila? O que é totalmente o caso. O que eu estaba referíndose a era que nós temos unha estrutura de datos matriz. Nós temos unha matriz de char * s, este arranxo de cordas, e imos engadir a isto, a fin de crear a estrutura de datos empilhados. 

Así, unha pila é un pouco máis complexo que un array. Podemos usar unha matriz para construír unha pila. Entón é aí onde nós dicimos que a pila está construída enriba dunha matriz. Do mesmo xeito, como dixen anteriormente, podemos construír unha pila enriba dunha lista ligada. En vez de usar unha matriz para almacenar os nosos elementos, poderiamos usar unha lista ligada a manter os nosos elementos e construír a pila en torno a iso. Imos camiñar a través de un par de exemplos, mirando para un código, para ver o que está realmente a suceder aquí. Na esquerda, eu teño xogado para abaixo o que struct pila quedaría na memoria a capacidade de # definido como catro. Temos os nosos catro elemento do array char *. Temos cadeas [0], cadeas, [1] strings [2] strings [3], e, a continuación, que o espacio para o noso pasado enteiro tamaño. Será que isto ten sentido? Okay. Isto é o que pasa se o que fago á dereita, cal será o meu código, é só para declarar unha estrutura, unha estrutura chamada empilhados s. Isto é o que temos. Establece esta pegada na memoria. A primeira pregunta aquí é o que son os contidos struct pila? Agora non é nada, pero eles non son absolutamente nada. San este tipo de lixo. Nós non temos idea do que está neles. Cando declaramos s pila, estamos só xogando que encima da memoria. É unha especie de como declarar int i non arrincar-la. Vostede non sabe o que está aí. Podes ler o que está aí, pero non pode ser super útil. Unha cousa que quere sempre se lembrar de facer é iniciar o que debe ser inicializar. Neste caso, nós estamos indo a iniciar o tamaño para ser cero, porque que vai pasar a ser moi importante para nós. Nós poderiamos ir adiante e iniciar os punteiros, todos os s * char, ser un valor comprensible, probablemente nulo. Pero non é totalmente necesario que fagamos isto. 

Agora, as dúas principais operacións sobre pilas son? Alguén se lembra da charla que fai pila? Si? [Stella] empurrando e popping? >> Exactamente. Empurrando e popping son as dúas principais operacións sobre pilas. E o que facer presión? >> Pon algo para o cumio da pila, e despois leva-lo de estalo. [Hardison] Exactamente. Entón, empurrando empurra algo na parte superior da pila. É como a cea o equipo poñendo unha bandexa de cea no mostrador. E popping está levando unha bandexa de cea á beira da pila. Imos examinar algúns exemplos do que acontece cando empurrar as cousas para a pila. Se fósemos para empurrar a cadea 'Ola' para o noso conxunto, este é o noso diagrama será coma agora. Mira o que ocorre? Nós empurrado para dentro do primeiro elemento da nosa matriz cordas e elevou a conta de tamaño para ser 1. Entón, se olharmos para a diferenza entre os dous diapositivas, aquí foi de 0, aquí está antes do pulo. Aquí é despois do empurrón. Antes do envío, tras a presión. E agora temos un elemento na nosa pila. É a cadea "Ola", e é iso. Todo o resto na matriz, na nosa matriz cordas, aínda é lixo. Non inicializar el. Imos dicir que empurrar outra corda para o noso conxunto. Nós imos empurrar "mundo" neste momento. Así podes ver "o mundo" aquí vai enriba do "Ola", e a conta de tamaño vai ata 2. Agora podemos empurrar "CS50", e que vai enriba de novo. Se volver, podes ver como estamos empurrando as cousas enriba da pila. E agora temos a pop. Cando apareceu algo fóra da pila, o que pasou? Alguén viu a diferencia? É moi sutil. [Alumno] O tamaño. >> Si, o tamaño modificado. 

O que máis lle esperar para cambiar? [Alumno] As cordas, tamén. >> Dereito. As cordas tamén. Acontece que cando está facendo desta forma, porque non estamos copiando os elementos na nosa pila, Nós realmente non ten que facer nada, podemos usar só o tamaño para manter o control do número de cousas na nosa matriz para que, cando aparecer de novo, unha vez máis, só diminuír noso tamaño 1. Non hai necesidade de realmente entrar e substituír nada. Tipo de funky. Acontece que normalmente simplemente deixar as cousas só, porque é menos traballo para nós. Se non temos que volver e substituír algo, entón por que facelo? Así, cando aparecer dúas veces fóra da pila, é todo o que fai diminuír o tamaño dun par de veces. E unha vez máis, este é só porque non estamos copiando as cousas na nosa pila. Si? Dalle. [Estudante, inintelixible] >> E entón o que ocorre cando empurrar algo novo? Cando empurrar algo novo, onde vai? Para onde vai, Basil? >> En cordas [1]? >> Dereito. Por que non ir cadeas [3]? [Basil] Porque se esqueceu de que non había nada en cordas [1] e [2]? [Hardison] Exactamente. A nosa pila, esencialmente, "esqueceu" que estaba suxeitando en nada en cordas [1] ou cordas [2], polo tanto, cando empurrar "woot", el simplemente pon que o elemento en cordas [1]. Hai dúbidas sobre como funciona isto, nun nivel básico? [Sam] Así, este non é dinámica, de calquera maneira, en termos de cantidade ou en virtude do tamaño da pila? [Hardison] Exactamente. Isto é - o punto era que esta non era unha pila dinámicamente growning. Trátase de unha pila que pode conter, como máximo, catro char * s, como máximo catro cousas. Se fósemos tentar empurrar unha cousa quinto, o que pensas que debe ocorrer? [Estudantes, inintelixible] [Hardison] Exactamente. Hai unha serie de cousas que poden ocorrer. Podería seg falla, dependendo do que nós - exactamente como nós estaban a aplicar o back-end. El podería substituír. El podería ter ese estourido de buffer que falamos en clase. Cal sería a cousa máis obvia que pode ser substituído se intentou empurrar algo extra no noso pila? Entón mencionar un estourido de buffer. O que pode ser o único que se escribiu máis ou pisou se rebordou accidentalmente por tentar empurrar unha cousa extra? [Daniel, inintelixible] Posible. >> Pero, inicialmente, o que pode ocorrer? O que se intentou empurrar unha cuarta cousa? Pode substituír o tamaño mínimo con este diagrama de memoria que temos. 

Na especificación conxunto de problemas, que é o que nós imos estar aplicando hoxe, o que queremos facer é volver falso. O noso método push vai voltar un valor booleano, e ese valor booleano será certo o impulso éxito e falso se non podemos empurrar máis nada, porque a pila está chea. Imos examinar un pouco de que o código agora. Aquí é a nosa función push. A nosa función push para unha pila vai ter na cadea para poñer na pila. Vai voltar certo a cadea foi empuxado con éxito na outra pila e teito. Todas as suxestións sobre o que pode ser unha cousa boa primeiro a facer aquí? [Sam] Se tamaño é igual capacidade logo retornar falso? [Hardison] Bingo. Bo traballo. Se o tamaño é a capacidade, imos voltar falso. Non podemos poñer algo máis na nosa pila. En caso contrario, queremos poñer algo na parte superior da pila. ¿Que é o "principio da pila", inicialmente? [Daniel] Tamaño 0? Tamaño >> 0. Que é o cume da pila despois hai unha cousa na pila? Missy, vostede sabe? [Missy] un. Tamaño >> é unha, exactamente. Continúa a engadir ao tamaño, e cada vez que está poñendo no novo elemento no tamaño do índice na matriz. Podemos facelo con este tipo de one-Liner, se iso ten sentido. Entón, nós temos a nosa matriz cordas, imos para acceder-lo no índice tamaño, e nós só estamos indo para gardar o noso char * alí. Observe como non hai como copia cadea suceder aquí, non asignación dinámica de memoria? E entón Missy trouxo o que temos agora de facer, porque temos gardado a cadea no lugar axeitado na matriz, e ela dixo que tiña que aumentar o tamaño dun xeito que nós estamos preparados para o impulso seguinte. Así, podemos facelo con s.size + +. Neste punto, nós empurrado para a nosa matriz. Cal é a última cousa que temos que facer? [Estudante] voltar true. Voltar >> verdade. Entón é moi simple, un código moi sinxelo. Non moito. Unha vez que implica a súa cabeza en torno a como a pila funciona, iso é moi sinxelo de implementar. 

Agora, a próxima parte deste está xurdindo unha corda fóra da pila. Eu vou dar a vostedes moito tempo para traballar niso un pouco. É case esencialmente o contrario do que fixemos aquí en empurrón. O que eu teño feito é, en realidade - Oops. Eu iniciado un aparello aquí, e no aparello, Eu puxei o conxunto de problemas 5 especificación. Se zoom aquí, podemos ver que eu estou cdn.cs50.net/2012/fall/psets/pset5.pdf. Vós xa baixou este código que está situado aquí, section6.zip? Todo ben. Se non ten feito isto, fai iso agora, moi rapidamente. Eu vou facer iso na miña xanela de terminal. En realidade, eu fixen iso aquí enriba. Si Si, Sam? >> Eu teño unha pregunta sobre por que dixo s.string 's pistas de tamaño = str? ¿Que é str? É o definido en algún lugar antes, ou - oh, no str char *? [Hardison] Si, exactamente. Ese foi o argumento. >> Ah, ok. Sentímolo. [Hardison] Estamos especificando a corda para empurrar dentro A outra cuestión que poida xurdir que realmente non falar aquí era tomamos por certo que tivemos esta variable chamada s que estaba no ámbito e accesible para nós. Tomamos por certo que s esta struct pila. Entón, mirando cara atrás, este código push, podes ver que nós estamos facendo cousas con esta corda que foi aprobada en pero entón, de súpeto, estamos accedendo s.size, como, onde s vén? O código que imos ollar no arquivo sección e, a continuación, o material que estará facendo no seu problema se pon, fixemos nosa pila struct dunha variable global para que poidamos ter acceso a el en todas as nosas funcións distintas sen ter que manualmente pasar ao redor e pasalo por referencia, facer todo tipo de cousas a el. Estamos só enganando un pouco, se queres, para facer as cousas mellor. E iso é algo que estamos facendo aquí, porque iso é para divertirse, é máis fácil. Moitas veces, vai ver as persoas fan iso, eles teñen unha gran estrutura de datos que está sendo operado dentro do seu programa. 

Imos volver para o aparello. Será que todo o mundo con éxito obter o section6.zip? Todo o mundo descompactá-lo usando section6.zip unzip? Se vai para o directorio sección 6 - aah, en todo o lugar - e incluír o que aquí, ve que ten tres diferentes arquivos. c. Ten unha cola, un SLL, que, illadamente, é ligada lista, e unha pila. Se abrir stack.c, podes ver que temos esa estrutura definida para nós, a estrutura exacta que acabamos de falar nos diapositivas. Temos a nosa variable global para a pila, Nós temos a nosa función push, e despois temos a nosa función pop. Vou poñer o código para empurrar de volta no slide aquí, pero o que me gustaría que vós que facer é, o mellor da súa capacidade, ir e aplicar a función pop. Despois de aplicar, pode compilar este co make de pila, e, a continuación, executar o arquivo executábel pila resultante, e que pode facer todo ese código de proba aquí abaixo que está na principal. E principal coida de realmente facer o push e pop chamadas e asegurarse de que todo pasa ben. Tamén se inicia o tamaño da pila aquí así que non se preocupe o arranque iso. Pode asumir que foi inicializar correctamente polo tempo que acceder a ela na función de pop. Isto ten sentido? Entón, imos alí. Hai o código empurrón. Eu vou dar a vostedes 5 ou 10 minutos. E se tes algunha dúbida no ínterim, mentres está de codificación, pregunta-lle en voz alta. Entón, se chegar a un punto de discordia, é só pedir. Deixe-me saber, deixe todo o mundo sabe. Traballa co seu veciño tamén. [Daniel] Estamos só aplicando pop agora? Só >> pop. Aínda que pode copiar a implementación de impulso se quere de xeito que a proba vai funcionar. Porque é difícil para probar as cousas ficando en - ou é difícil probar as cousas pulando para fóra de unha pila se non hai nada na pila para comezar. 

¿Que é pop suposto estar volvendo? O elemento dende o principio da pila. É suposto obter o elemento para fóra da parte superior da pila e, a continuación, diminuír o tamaño da pila, e agora perdeu o elemento superior. E entón voltar o elemento superior. [Estudante, inintelixible] [Hardison] Entón, o que pasa se fai iso? [Estudante, inintelixible] O que acaba pasando é que probablemente está accedendo ou un elemento que non foi inicializado aínda, para que o seu cálculo onde o último elemento é desligado. Entón, aquí, se observar, no impulso, estamos accedendo cordas no elemento s.size porque é un novo índice. É o novo cume da pila. Considerando que, pop, s.size vai ser o seguinte espazo, o espazo que está na parte superior de todos os elementos no seu stack. Así, o elemento de nivel máis alto non é s.size, pero si, é por baixo. 

A outra cousa a facer cando - en pop, é que ten que diminuír o tamaño. Se se lembrar de volta ao noso pequeno diagrama aquí, realmente, o único que vimos pasar cando chamado pop era que este tamaño descartado, primeiro en 2, entón a 1. Entón, cando empuxou un novo elemento ligado, el iría para o lugar axeitado. [Basil] Se o s.size é 2, entón non vai pasar ao elemento 2, e despois que desexa que apareza ese elemento fóra? Entón, se nós fomos para - >> Entón, imos ollar para iso de novo. Se esta é a pila neste punto e chamamos pop, en que o contido é o elemento máis alto? [Basil] O 2, pero vai aparecer 3. >> Dereito. Entón é aí que o noso tamaño é 3, pero queremos poñer o elemento no índice 2. É ese tipo típico de fóra por un que ten o cero-indexación de matrices. Entón, quere aparecer o terceiro elemento, pero o terceiro elemento non está no índice 3. E a razón pola que non tes que facer iso unha menos cando estamos empurrando é porque agora, entender que o elemento máis alto, se fósemos para empurrar outra cousa para a pila, neste punto, que quere empurralo lo no índice 3. E iso só acontece se o tamaño e os índices aliñar cando está empurrando. 

Quen ten unha implementación do conxunto de traballo? Ten unha pila de traballar un. Tes pop funcionando aínda? [Daniel] Si Creo que si. Programa >> funciona e non seg falhamento, está imprimindo? Será que imprimir "éxito" cando o fai? Si Fai apilar, executa-lo, se imprime "éxito" e non vai boom, entón todo é bo. Todo ben. Imos pasar o aparello moi rapidamente, e nós imos camiñar por este. Se olharmos para o que está a suceder aquí con pop, Daniel, que foi o primeiro que fixo? [Daniel] Se s.size é maior que 0. [Hardison] Okay. E por que fixo iso? [Daniel] Para asegurarse de que había algo dentro da pila. [Hardison] Dereito. Quere probar para estar seguro de que s.size é maior que 0; doutra forma, o que quere que aconteza? [Daniel] return null? >> Return null, exactamente. Polo tanto, se s.size é maior que 0. Entón, o que imos facer? O que imos facer a pila non está baleiro? [Stella] Vostede diminuír o tamaño? >> Vostede diminuír o tamaño, todo ben. Entón, como fixo iso? >> S.size--. [Hardison] Grande. E entón, o que fixo? [Stella] E entón eu dixo que o retorno s.string [s.size]. [Hardison] Grande. Se non, regresar nulo. Si, Sam? [Sam] Por que non necesita ser s.size + 1? [Hardison] Plus 1? Si >>. >> Entender. [Sam] Eu penso, porque está levando un fóra, entón está indo estar volvendo non o que eles pediron. [Hardison] E iso foi exactamente o que estaban falando con toda esta cuestión de 0 índices. Entón, se o zoom aquí. Se olharmos para este cara aquí, podes ver que, cando apareza, estamos estourando o elemento no índice 2. 

Entón, nós diminuímos noso tamaño primeiro, despois o noso tamaño corresponde ao índice. Se non diminuír o tamaño do primeiro, entón temos que facer o tamaño -1 e decremento. Grande. Todo ben? Calquera dúbida sobre iso? Hai unha serie de formas diferentes para escribir iso tamén. En realidade, podemos facer algo aínda - podemos facer un one-Liner. Podemos facer un retorno dunha liña. Así, podemos realmente diminuír antes de volver ao facelo. Entón, poñer o - antes do s.size. Isto fai que a liña realmente denso. Se a diferenza entre o - S e tamaño. S.size - é que este postfix - que eles chaman de postfix, porque o - vén despois do s.size - significa que s.size é valorada para efectos de atopar o índice como é actualmente, cando esta liña é executada, e despois iso - acontece despois da liña é executada. Tras o elemento s.size contido é accesible. E iso non é o que queremos, porque queremos que o decremento ocorrer primeiro. Othewise, imos estar accedendo a matriz, efectivamente, fóra dos límites. Nós imos estar accedendo ao elemento sobre o que realmente quere acceder. Si, Sam? >> É máis rápido ou usar menos memoria RAM para facer en liña ou non? [Hardison] Honesta, iso realmente depende. [Sam, inintelixible] >> Si, depende. Podes facer trucos compilador para obter o compilador para recoñecer que, xeralmente, eu imaxino. 

Entón, nós mencionados un pouco sobre isto optimización do compilador que pode facer na compilación, e ese é o tipo de cousa que un compilador pode ser capaz de descubrir, como oh, hey, quizais eu poida facer todo isto nunha soa operación, ao contrario de cargar a variable en tamaño a partir da RAM, decrementando-lo, gardalo lo de volta para fóra, e despois poñer-lo de volta de novo para procesar o resto da operación. Pero, normalmente, non, este non é o tipo de cousas que vai facer o seu programa significativamente máis rápido. Algunha pregunta sobre pilas? 

Entón, empurrando e popping. Se vostedes queren experimentar a edición de hacker, o que fixemos na edición de hacker é realmente ir e fixo esta pila crecer dinámicamente. O reto non é todo aquí na función push, para descubrir como facer esa matriz crecer como continuar presionando máis e máis elementos na pila. Non é realmente moi código adicional. Só unha chamada - vostede ten que lembrar de obter as chamadas malloc alí correctamente, e despois descubrir cando está indo a chamar realloc. Isto é un reto divertido se vostede está interesado. 

Pero, por agora, imos seguir adiante, e imos falar sobre as filas. Rolar por aquí. A cola é un irmán preto da pila. Entón, na pila, as cousas que foron colocadas en último foron as primeiras cousas a ser recuperados. Temos este último en entrar, primeiro fóra, ou LIFO, ordenando. Considerando que, en fila, como sería de esperar a partir de cando está en pé na cola, a primeira persoa a entrar na cola, o primeiro en entrar na cola, é a primeira cousa que é recuperada da cola. As filas tamén son frecuentemente utilizados cando estamos lidando con gráficos, como falamos brevemente con pilas, e as filas tamén son útiles para unha morea de outras cousas. Unha cousa que xorde moitas veces é tentar manter, por exemplo, unha lista ordenada de elementos. E pode facer iso con unha matriz. Pode manter unha lista ordenada de cousas nunha matriz, pero onde que queda complicado é, entón sempre que atopa o lugar apropiado para introducir a seguinte cousa. Entón se ten unha matriz de números, do 1 ao 10, e entón quere ampliar isto para todos os números do 1 ao 100, e está quedando estes números de forma aleatoria e tentando manter todo clasificados como pasar, acaba tendo que facer unha chea de cambio. Con certos tipos de colas e certos tipos de estruturas de datos subxacentes, realmente pode perder lo moi sinxelo. Non ten que engadir algo e, a continuación reordene a cousa toda de cada vez. Non ten que facer unha chea de cambio dos elementos internos arredor. Cando ollamos para unha fila, vostede ve que - tamén en queue.c no código de sección - a estrutura que temos dado a vostede realmente é parecida coa estrutura que lle deu unha pila. 

Hai unha excepción a iso, e que unha excepción é que temos este enteiro adicional chamado a cabeza, eo xefe aquí é para manter o control da cabeza da cola, ou o primeiro elemento na cola. Con unha pila, fomos capaces de manter o control do elemento que estabamos a piques de recuperar, ou a parte superior da pila, utilizando só o tamaño, mentres que cunha cola, estamos tendo que xestione extremos opostos. Estamos intentando alinhavar as cousas en ao final, pero a continuación, voltar as cousas de fronte. Así, de forma eficaz, coa cabeza, temos o índice do inicio da fila, é o tamaño da-nos o índice do fin da cola para que poidamos recuperar as cousas da cabeza e engadir cousas a cola. Mentres que a pila, estabamos sempre só trata sobre o cume da pila. Nunca a acceder ao fondo da pila. Nós só engadiu cousas para arriba e levou as cousas fóra do arriba así nós non necesitamos que campo extra dentro da nosa estrutura. Isto xeralmente ten sentido? Todo ben. Si, Charlotte? [Charlotte, inintelixible] [Hardison] Iso é unha gran cuestión, e que foi un que xurdiu en charla. Quizais camiñando a través de algúns exemplos que ilustran por nós non queremos usar cordas [0] como xefe de fila. 

Entón, imaxine que temos a nosa cola, imos chamalo de cola. En principio, cando temos só instanciado-lo, cando temos só declarou que, non temos nada inicializar. É todo lixo. Entón, por suposto que queremos estar seguro de que arrincar tanto o tamaño e os campos de cabeza a ser 0, algo razoable. Tamén pode ir adiante e nulo fóra os elementos na nosa cola. E para facer este axuste diagrama, observe que agora a nosa cola só pode ter tres elementos; mentres que a nosa pila podería prender catro, a nosa cola só pode ter tres. E iso é só para facer o axuste diagrama. A primeira cousa que acontece aquí é que poñer na cola a cadea "ola". E, así como fixemos coa pila, nada moi diferente aquí, xogamos a corda no en cordas [0] e incrementar o noso tamaño en 1. Nós enfileirar "adeus", el e colocar. Polo tanto, esta parece unha pila para a maior parte. Nós comezamos aquí, elemento novo, elemento novo, o tamaño segue a subir. O que acontece neste momento cando queremos desenfileirar algo? Cando queremos retirarse da cola, que é o elemento que queremos retirarse da fila? [Basil] Strings [0]. >> Cero. Exactamente, Basil. Queremos librar-se da primeira cadea, este, "ola". Entón, cal foi a outra cousa que cambiou? Teña en conta cando apareceu algo fóra da pila, só cambiou o tamaño, pero aquí temos un par de cousas que cambian. Non só a cambio de tamaño, pero os cambios de cabeza. Isto vai de volta ao punto de Charlotte anteriormente: Por que temos esta cabeza tamén? Será que ten sentido agora, Charlotte? Tipo de >>. [Hardison] Kind of? Entón, o que pasou cando dequeued? O que fixo a cabeza de facelo agora é interesante? [Charlotte] Ah, porque cambiou - todo ben. Eu vexo. Porque a cabeza - onde a cabeza está a apuntar cara mudanzas en termos de localización. Non é máis sempre un índice cero. >> Si, exactamente. O que pasou foi dequeueing o elemento de alta foi feito e nós non teñen esa cabeza campo porque estabamos sempre ligando esa cadea en 0 índice de xefe da nosa fila, entón teriamos que cambiar o resto da fila de abaixo. Nós teriamos que cambiar o "adeus" de de cordas [1] as cordas [0]. E cordas [2] para abaixo para cordas [1]. E nós temos que facer iso para toda a lista de elementos, toda a matriz de elementos. E cando estamos facendo iso con unha matriz, que queda moi caro. Entón, aquí, non é un gran negocio. Só temos tres elementos na nosa matriz. Pero se tivésemos unha fila de miles de elementos ou dun millón de elementos, e entón, de súpeto, comezan a facer unha chea de dequeue chama a todos en un loop, as cousas están realmente indo para desacelerar como cambia todo para abaixo constantemente. Vostede sabe, cambiar por 1, por un cambio de quenda, por 1, por un cambio. En vez diso, usan esa cabeza, chamamos iso dun "punteiro", a pesar de que non é realmente un punteiro en sentido estrito, non é un tipo de punteiro. Non é un * int ou char * ou algo así. Pero está a apuntar ou indicando o xefe da nosa fila. Si? 

[Estudante] Como dequeue sabe só pop fóra o que está na cabeza? [Hardison] Como dequeue saber como pop fóra todo o que está na cabeza? Dereito >>, si. >> O que está a ver é só o que a cabeza campo está definido. Así, neste primeiro caso, se miramos ben aquí, nosa cabeza é 0, 0 índice. >> Dereito. [Hardison] Entón el só di ben, ben, o elemento no índice 0, a secuencia de "ola", é o elemento na cabeza da nosa fila. Entón, imos para desenfileirar este cara. E iso vai ser un elemento que é devolto para o chamador. Si, Saad? Así, a cabeza >> basicamente define o - onde está indo para indexa-lo? Isto é o comezo? Si >>. Ok >>. [Hardison] que se está facendo o novo comezo para a nosa matriz. Entón, cando desenfileirar algo, todo o que precisa facer é acceder ao elemento no índice q.head, e que será o elemento que desexa eliminar da cola. Tamén ten que diminuír o tamaño. Imos ver un pouco as cousas están un pouco complicado con iso. Nós desenfileirar, e agora, se enfileirar novo, onde é que imos poñer na cola? Onde é que o próximo elemento ir na nosa cola? Dicir que queren pór na cola a cadea "CS". En cal índice vai? [Os alumnos] Strings [2]. >> Dous. Por 2 e non 0? [Basil] Porque agora a cabeza é 1, polo que é como o inicio da lista? [Hardison] Dereito. E o que indica o fin da lista? O que estabamos usando para indicar o final da nosa fila? A cabeza é o xefe da nosa fila, o inicio da nosa fila. O que é o fin da nosa fila? [Os alumnos] Tamaño. Tamaño >>, exactamente. Así, os nosos novos elementos entrar en tamaño, e os elementos que tiramos saír na cabeza. Cando enfileirar o seguinte elemento, estamos poñendo o en no tamaño. [Estudante] Antes de poñer isto en porén, tamaño era un, non? [Hardison] Dereito. Polo tanto, non moito en tamaño. + Tamaño, non un, pero a cabeza +. Porque cambiou todo pola cantidade cabeza. Entón, aquí, agora temos unha cola de tamaño 1 que comeza no índice 1. A cola é índice 2. Si? 

[Alumno] O que acontece cando dequeue cadeas [0], e as cordas "slots de memoria só se baleirou, basicamente, ou simplemente esquecida? [Hardison] Yeah. Neste sentido, estamos só esquece-los. Se estivésemos almacenar copias deles para - moitas estruturas de datos, moitas veces, almacenar as súas propias copias dos elementos de xeito que a persoa que xestiona a estrutura de datos non teñen que se preocupar sobre onde todos os punteiros están indo. A estrutura de datos segura para todo, suxeita a todas as copias, para asegurarse de que todo persiste de forma adecuada. Con todo, neste caso, estas estruturas de datos só para simplificar, non están facendo copias de todo o que estamos almacenando en los. [Estudante] Entón este é un conxunto continuo de -? Si >>. Se miramos cara atrás, o que a definición foi desta estrutura é. É só unha matriz defecto, como viu, unha matriz de char * s. Será que -? >> Si, eu estaba pensando Se finalmente se esgote a memoria, de certa forma, se ten todos eses lugares baleiros na súa matriz? [Hardison] Si, é un bo punto. 

Se olharmos para o que pasou agora, neste punto, nós preenchemos a nosa cola, que parece. Pero nós non temos realmente cheo nosa cola porque temos unha fila que é tamaño 2, pero comeza o índice 1, porque é onde o noso punteiro cabeza. Como estaba dicindo, ese elemento en cadeas [0], o índice 0, non está realmente alí. Non está na nosa cola de máis. Nós só non se preocupou en ir e substitúe-lo cando dequeued-lo. Así, aínda que parece que estamos sen memoria, nós realmente non temos. Este punto está dispoñible para nós para usar. O comportamento adecuado, se fósemos tentar algo primeira dequeue como "bye", que sería pop bye fóra. Agora a nosa cola comeza o índice 2 e é de tamaño 1. E agora, se intentemos e enfileirar algo novo, digamos, 50, 50 debe ir neste lugar no índice 0 porque aínda está dispoñible para nós. Si, Saad? [Saad] Isto acontece automaticamente? [Hardison] Isto non acontece moito automaticamente. Ten que facer a matemática para facer o traballo, pero esencialmente o que fixemos é que acabamos enrolado. [Saad] E todo ben se isto ten un buraco no medio dela? [Hardison] e podemos facer as matemáticas funcionar correctamente. 

E resulta que iso non é realmente difícil de facer co operador mod. Así como fixemos con César e as cousas de cifrado, usando mod, podemos facer as cousas para involucrar e continuar arredor e arredor coa nosa cola, manter ese punteiro cabeza movendo. Nótese que o tamaño é sempre respectando o número de elementos, en realidade, dentro da cola. E iso é só o punteiro de cabeza que mantén bicicleta pasar. Se olharmos para o que pasou aquí, se volver para o inicio, e só ve o que pasa na cabeza cando enfileirar algo, nada aconteceu coa cabeza. Cando enfileirados outra cousa, nada aconteceu coa cabeza. Así que dequeued algo, a cabeza vai a por un. Nós enfileirado algo, non pasa nada na cabeza. Cando desenfileirar algo, de súpeto, a cabeza é incrementado. Cando enfileirar algo, non pasa nada na cabeza. 

O que sucedería, neste punto, se fósemos desenfileirar algo de novo? Todos os pensamentos? O que sucedería coa cabeza? O que debe ocorrer con cabeza se fósemos para desenfileirar outra cousa? A cabeza agora está no índice 2, o que significa que a cabeza da cola é cadeas [2]. [Estudante] que retorna 0? >> Debe volver a 0. Debe involucrar en torno a volta, exactamente. Ata agora, cada vez que chama dequeue, estamos engadindo unha na cabeza, engadir un para a cabeza, engade unha para a cabeza, engade unha para a cabeza. Así que ese punteiro cabeza queda para o último índice na nosa matriz, entón temos que implica-la de volta ao redor para o comezo, voltar a 0. [Charlotte] O que determina a capacidade da fila nunha pila? [Hardison] Neste caso, acabamos usando ser unha constante # definido. Ok >>. [Hardison] O arquivo c real., Pode poñerse e xogar con el un pouco e facelo tan grande ou tan pouco como quere. [Charlotte] Entón, cando está facendo-se nunha cola, como fai o ordenador sabe como gran quere a pila para ser? [Hardison] Iso é unha gran cuestión. Hai un par de formas. Un é para define-lo na fronte e dicir que iso vai ser unha cola que ten 4 elementos ou 50 elementos ou 10.000. A outra forma é facer o que a xente está facendo edición de hackers e crear funcións para ter a súa cola crecer dinámicamente como máis cousas son engadidos dentro 

[Charlotte] Entón, para ir coa primeira opción, o que usa sintaxe para dicir ao programa que é o tamaño da cola? [Hardison] Ah. Entón, imos saír desta. Eu aínda estou en stack.c aquí, entón eu estou indo só para rolar ata o cumio aquí. Podes ver iso aquí? Este é o # define capacidade 10. E iso é case exactamente a mesma sintaxe que temos para cola. Excepto na cola, temos que o campo estrutura extra aquí. [Charlotte] Oh, eu penso que a capacidade significaba a capacidade para a cadea. [Hardison] Ah. >> Iso é o lonxitude máxima da palabra. >> Entender. Si A capacidade aquí - que é un gran punto. E iso é algo que é complicado porque o que temos declarado aquí é unha matriz de char * s. Unha matriz de punteiros. Esta é unha matriz de caracteres. Este é probablemente o que viu cando foi declarar os seus buffers para o arquivo I / O, cando foi crear cadeas manualmente na pila. Con todo, o que temos aquí é unha matriz de char * s. Entón, é unha matriz de punteiros. En realidade, o zoom para fóra, e miramos o que está a suceder aquí na presentación, ve que os elementos reais, os datos de carácter non se garda dentro da propia matriz. O que está almacenada dentro da nosa matriz aquí son punteiros para os datos de caracteres. Okay. Entón, vimos como o tamaño da cola é como a pila, o tamaño respecta sempre o número de elementos na cola neste momento. Despois de facer 2 enfileira, o tamaño é 2. Despois de facer unha dequeue o tamaño agora é 1. Despois de facer outra enqueue o tamaño está de volta a 2. Así, o tamaño definitivamente respecta ao número de elementos na cola, e despois a cabeza só mantén ciclismo. El vai de 0-1-2, 0-1-2, 0-1-2. E cada vez que chamamos dequeue, o punteiro cabeza é incrementado para o próximo curso. E a cabeza está a piques de pasar por riba, el volve a 0. Entón, con iso, podemos escribir a función dequeue. E imos deixar a función enqueue para vós para aplicar no seu lugar. 

Cando desenfileirar un elemento da nosa fila, cal foi o primeiro que Daniel fixo cando comezou a escribir a función pop para pilas? Deixe-me escoitar de alguén que non teña falado aínda. Imos ver, Saad, se recorda o que Daniel fixo o que a primeira cousa cando escribiu pop? [Saad] Non foi - >> El probou algo. [Saad] Se o tamaño é maior que 0. >> Exactamente. E o que foi que o exame para? [Saad] Iso foi unha proba para ver se hai algo dentro da matriz. [Hardison] Yeah. Exactamente. Entón non pode aparecer calquera cousa fóra da pila, se está baleiro. Do mesmo xeito, non se pode retirar da fila calquera cousa de unha fila se está baleiro. Cal é a primeira cousa que temos que facer a nosa función dequeue aquí, que pensas? [Saad] Se o tamaño é maior que 0? Si >>. Neste caso, realmente só probado para ver se é 0. Se é 0, podemos volver nulo. Pero a lóxica exactamente o mesmo. E imos seguir con iso. Se o tamaño non é 0, onde é o elemento que queremos retirarse da fila? [Saad] na cabeza? >> Exactamente. Podemos só retirar o primeiro elemento na nosa cola acceder ao elemento na cabeza. Nada tolo. Despois diso, o que temos que facer? O que ten que ocorrer? Cal foi a outra cousa que falamos no dequeue? Dúas cousas ten que acontecer, porque a nosa cola cambiou. [Daniel] Reducir o tamaño. >> Temos de reducir o tamaño e aumentar a cabeza? Exactamente. Para aumentar a cabeza, non podemos só cega aumentar a cabeza, lembre-se. Non podemos só facer queue.head + +. Temos tamén a incluír este mod pola capacidade. E por que mod por capacidade, Stella? [Stella] Porque ten que implicar. >> Exactamente. Nós mod pola capacidade porque ten que implicar a volta a 0. Entón, agora, neste momento, podemos facer o que dixo Daniel. Podemos diminuír o tamaño. E entón podemos simplemente devolver o elemento que estaba no inicio da fila. Mira o tipo de gnarly en primeiro lugar. Pode ter unha pregunta. Sentímolo? 

[Sam] Por que é o primeiro na parte superior da fila? Onde é que isto vai? [Hardison] Vén da cuarta liña do fondo. Despois de que probar para estar seguro de que a nosa cola non está baleira, nós retiramos char * En primeiro lugar, elimina o elemento que está sentado no índice cabeza da nosa matriz, da nosa matriz cordas >>, e chamada que primeiro? [Hardison] E chamamos iso de primeira. Si Só para acompañar iso, por que pensas que tivemos que facer iso? [Sam] Cada primeiro só retornando q.strings [q.head]? Si >>. >> Porque estamos facendo isto cambio q.head coa función mod, e non hai forma de facelo dentro da liña de retorno tamén. [Hardison] Exactamente. Vostede está no lugar. Sam está totalmente recoñecidas. A razón pola que tivo que retirar o primeiro elemento na nosa cola e almacena-lo nunha variable é porque esta liña que só q.head, hai operador mod alí non é algo que podemos facer e telo en vigor na cabeza sen - nunha única liña. Entón, nós realmente temos que aproveitar o primeiro elemento, a continuación, axuste a cabeza, axustar o tamaño, e, a continuación, voltar o elemento que tirou. E iso é algo que imos ver xurdir máis tarde con listas ligadas, como xogar con eles. Moitas veces, cando está liberando ou eliminación de listas ligadas hai que lembrar o seguinte elemento, o punteiro preto dunha lista ligada antes de descartar o actual. Porque senón tirar a información que queda na lista. Agora, se vai para o seu dispositivo, abre queue.c X fóra deste. Entón, se eu abrir queue.c, deixe-me zoom aquí, vai ver que ten un arquivo similar para o futuro. Parecidas ficheiro co que tiñamos antes con stack.c. Nós temos a nosa estrutura de cola definida só como vimos nos diapositivas. 

Nós temos a nosa función enqueue que é para facer. E nós temos a función dequeue aquí. A función dequeue no arquivo non implementado, pero vou poñer-lo de volta en PowerPoint para que poida escriba-lo, se queres. Así, para os próximos 5 minutos ou máis, vostedes traballan en enqueue que é case o contrario do dequeue. Non ten que axustar cabeza cando está enqueueing, pero o que ten que axustar? Tamaño. Entón, cando enqueue, a cabeza permanece intocada, o tamaño é alterado. Mais é preciso un pouco de - vostede vai ter que xogar con esa mod para descubrir o que o índice do novo elemento debe ser inserido no. Entón, eu vou dar a vostedes un pouco, poñer desenfileirar volta no slide, e como vostedes teñen preguntas, berrar-los para que poidamos todos falan sobre eles como un grupo. Ademais, o tamaño que non - cando axustar o tamaño, pode sempre - ten para modificar o tamaño de sempre? [Daniel] Non >> Non ten para modificar o tamaño, a dereita. Como o tamaño sempre, se está - supoñendo que está administrando as cousas de forma adecuada, o tamaño será sempre entre 0 e 3. Onde ten que mod cando está facendo enqueue? [Estudante] Só a cabeza. Só >> para a cabeza, exactamente. E por que ten de mod en todo enqueue? Cando é unha situación en que ten que mod? [Estudante] Se ten cousas en espazos como en espazos 1 e 2, e despois que necesitas para engadir algo a 0. [Hardison] Si, exactamente. Entón, se o punteiro cabeza está no fin, ou se o seu tamaño, máis a súa cabeza é grande, ou mellor, vai involucrar en torno á cola. 

Entón, nesa situación que temos aquí enriba no slide agora, se eu queira poñer na cola algo agora, queremos algo enfileirar no índice 0. Entón, se ollar para onde o 50 vai, e eu chamo enqueue 50, vai alí no fondo. El vai en 0 índice. El substitúe o 'ola' que xa foi retirado da cola. [Daniel] Non Tomé o coidado de que en dequeue xa? Por que facer algo coa cabeza en enqueue? [Hardison] Ah, entón non está modificando a cabeza, me desculpe. Pero tes que usar o operador mod cando está accedendo o elemento que quere poñer na cola cando está accedendo o seguinte elemento na súa cola. [Basil] Eu non fixen iso, e eu teño "éxito" por alí. [Daniel] Oh, eu entendo o que está dicindo. [Hardison] Entón didn't - fixo no q.size? [Basil] Yeah. Eu só cambiou de lado, eu non fixen nada coa cabeza. [Hardison] Realmente non ten que restaurar a cabeza para ser calquera cousa, pero cando índice na matriz cordas, realmente ten que ir adiante e calcular onde o próximo elemento, withe porque a pila, o elemento seguinte na súa pila sempre foi no índice correspondente ao tamaño. Se miramos cara atrás ata a nosa función push pila, podemos sempre plunk no noso novo elemento á dereita no tamaño do índice. Considerando que, coa cola, non podemos facelo porque, se estamos nesta situación, se enfileirado 50 cadea de noso novo ía ben no strings [1] que non queremos facer. Queremos ter a nova cadea ir no índice 0. 

Alguén - si? [Estudante] Eu teño unha pregunta, pero non é realmente relacionados. O que significa cando alguén só chama algo así como punteiro pred? O que é que o nome curto para? Sei que é só un nome. [Hardison] punteiro Pred? Imos ver. En que contexto? [Alumno] Foi para a inserción. Podo pedir-lle máis tarde, se quere porque realmente non é relacionado, pero eu só - [Hardison] o código de David inserción de clase? Podemos tirar isto e falar sobre iso. Imos falar sobre iso a continuación, unha vez que temos de listas ligadas. 

Entón, imos moi rápido ollar para o que a función enqueue parece. Cal foi o primeiro que as persoas tentaron facer na súa liña enqueue? Para esta fila? Semellante ao que fixo para a pila de empurrar. O que fixo, Stella? [Stella, inintelixible] [Hardison] Exactamente. If (q.size CAPACIDADE ==) - Eu teño poñer o meu dispositivo no lugar seguro - regresar falso. Zoom un pouco. Okay. Agora, cal é a seguinte cousa que temos que facer? Así como coa pila, e inserida no lugar seguro. E así o que era o lugar seguro para introducir esa? Coa pila era o tamaño do índice, con iso, non é ben así. [Daniel] Eu teño q.head--ou - q.strings >>? >> Si q.strings [q.head + q.size mod CAPACIDADE]? [Hardison] Nós probablemente quere poñer parénteses en torno a este de xeito que nós estamos comezando a precedencia axeitada e de modo que é cleart a todos. E establecer que igual? >> Para str? >> Para str. Grande. E agora o que é a última cousa que temos que facer? Así como fixemos na pila. >> Incrementar o tamaño? >> Incrementar o tamaño. Boom. E entón, xa que o código de inicio só retornou falso por defecto, queremos cambiar isto para true todo pasa e todo vai ben. Todo ben. Isto é unha morea de información para sección. Non somos moito máis. Queremos falar moi rapidamente sobre illadamente conectados listas. Vou poñer isto para que poidamos volver a el máis tarde. Pero imos voltar a nosa presentación para só algúns diapositivas. Entón enqueue é todo, agora temos feito isto. 

Agora imos dar un ollo illadamente conectados listas. Nós conversas sobre iso un pouco máis na charla. Como moitos de vostedes viu a demo onde tivemos persoas desajeitadamente apuntando a outros números e cada unha explotación? >> Eu estaba nesa. >> O que vostedes pensan? Fixen iso, espero que desmitificar estes un pouco? Cunha lista, verifícase que xestione ese tipo que nós imos chamar un nó. Considerando que, coa cola ea pila que tiñamos estruturas que chamamos de cola na pila, tivemos estes nova fila en tipos de pila, aquí unha lista realmente está feita só de unha morea de nós. Do mesmo xeito que as cordas son só unha morea de chars todo aliñados ao lado do outro. Unha lista ligada é só un nó e outro no e outro no e outro nodo. E, en vez de esmagar todos os nós e almacena-los en conxunto de forma contigua todos á beira uns dos outros na memoria, ter este punteiro próximo nos permite almacenar os nós onde queira que, de forma aleatoria. E, a continuación, o tipo de fío de todos eles en conxunto para o punto de un para o outro. 

E o que era a gran vantaxe que esta tivo sobre unha matriz? Sobre todo o almacenamento de forma contigua só preso ao lado do outro? Vostede recorda? Si? >> Alocação de memoria dinámica? >> Alocação de memoria dinámica en que sentido? [Estudante] En que pode continuar facendo-o máis grande e non ten que mover o conxunto enteiro? [Hardison] Exactamente. Así, con unha matriz, cando quere poñer un novo elemento para o medio, ten que cambiar todo para o espazo. E como falamos coa cola, é por iso que manter o punteiro cabeza, de xeito que non estamos constantemente cambiando as cousas. Porque iso queda caro, se ten unha gran matriz e está constantemente facendo esas insercións aleatorias. Considerando que, con unha lista, todo o que tes que facer é xoga-lo en un novo nodo, axustar os punteiros, e está feito. O que suga sobre iso? Fóra o feito de que non é tan fácil de traballar como unha matriz? Si? [Daniel] Ben, eu creo que é moito máis difícil de acceder a un elemento específico na lista ligada? [Hardison] Non pode simplemente saltar dun elemento arbitrario no medio da lista de relacionados. Como é que ten que facer iso en vez diso? >> Ten que percorrer a cousa toda. [Hardison] Yeah. Ten que pasar por un de cada vez, unha de cada vez. É unha enorme - é unha dor. Cal é a outra - non hai outra caída para iso. [Basil] Vostede non pode ir para adiante e cara atrás? Ten que ir nunha dirección? [Hardison] Yeah. Entón, como imos solucionar isto, ás veces? [Basil] dobremente vinculada listas? >> Exactamente. Hai listas dobremente ligadas. Hai tamén - moi? 

[Sam] É o mesmo que usar a cousa que pred - Acaba de me lembrar, non é iso que a cousa é para pred? Non é que entre dobre e individual? Ollar [Hardison] Imos para o que exactamente estaba facendo. Entón, imos alí. Aquí está a lista de códigos. Aquí temos predptr, aquí. É iso o que estaba falando? Polo tanto, este foi - está liberando unha lista e está intentando gardar un punteiro para el. Este non é o dobre, vinculada illadamente-listas. Podemos falar máis sobre iso máis tarde xa que este está falando sobre a liberación da lista e quero mostrar algunhas outras cousas primeiro. pero é só - é lembrar o valor de PTR [Estudante] Ah, é punteiro precedente? Si >>. Para que poidamos entón incrementar PTR-se antes de que, entón, libre predptr que é. Porque nós non podemos PTR libre e despois chamar PTR = PTR vén, non? Iso sería malo. Entón imos ver, de novo este cara. 

A outra cousa ruín sobre listas é que, mentres que cunha matriz temos só todos os elementos propios apiladas de xeito conxunto, Aquí tamén temos introducido este punteiro. Polo tanto, hai unha peza adicional de memoria que estamos tendo que usar para cada elemento que estamos gardando na nosa lista. Temos flexibilidade, pero ten un custo. El vén con ese tempo, custo e el vén con ese custo de memoria tamén. Tempo, no sentido de que agora temos que pasar por cada elemento na matriz para atopar o índice de 10, ou que sería índice 10 nunha matriz. 

Só moi rapidamente, cando diagrama de fóra destas listas, normalmente temos a cabeza da lista ou o primeiro punteiro da lista e teña en conta que este é un punteiro verdade. É só 4 bytes. Non é un nó en si. Entón ve que non ten valor int nel, ningún punteiro próxima nel. É literalmente só un punteiro. Vai apuntar para algo que é unha estrutura de nodo real. [Sam] Un punteiro chamado nó? >> Este é - non. Este é un punteiro para algo do tipo de nodo. É un punteiro para unha estrutura de nodo. >> Ah, ok. Diagrama sobre o código, esquerda á dereita. Podemos definilo como nulo, o que é unha boa forma de comezar. Cando diagrama, quere gravala-lo como nulo ou poñer unha liña a través del así. 

Unha das formas máis fáciles de traballar con listas, e pedimos que tanto prepend e achegar para ver as diferenzas entre os dous, prepending pero é sempre máis fácil. Cando precede, este é o lugar onde - cando prepend (7), vai crear a estrutura do nodo e definir primeiro a apuntar cara a el, porque agora, xa que prefixado, vai estar no inicio da lista. Se prepend (3), que crea un outro no, pero agora 3 vén antes do 7. Entón estamos esencialmente empurrando as cousas para a nosa lista. Agora, podes ver que prepend, ás veces, as persoas chaman de empurrar, porque está empurrando un novo elemento na súa lista. Tamén é doado de borrar diante de unha lista. Entón, as persoas moitas veces chamada de pop. E desta maneira, pode emular unha pila empregando unha lista ligada. Gritos. Sentímolo, agora estamos entrando en aumento. Entón aquí nós prefixado (7), agora prepend (3). Se prefixado algo máis desta lista, se prefixado (4), entón temos 4 e logo 3 e despois 7. Entón nós podería pop e eliminar 4, elimina 3, elimine 7. Moitas veces, a forma máis intuitiva de pensar sobre iso é con aumento. Entón eu diagramado para fóra o que sería parecido engadir aquí. Aquí, adxunto (7) non parece ser diferente porque hai só un elemento da lista. E anexando (3) pon-lo ao final. Quizais podes ver agora o truco con append é que dende que nós só sabemos onde o principio da lista, Para achegar a unha lista que ten que andar todo o camiño a través da lista para chegar ao fin, deixar, a continuación, construír o nó e todo dólar abaixo. Chame todas as cousas para arriba. Así, con prepend, como acabamos resgou esta moi rapidamente, cando precede a unha lista, é moi sinxelo. 

Fai o seu novo nodo, implica algún distribución dinámica de memoria. Entón aquí estamos facendo un struct nodo usando malloc. Entón malloc estamos usando porque iso vai reservar memoria para nós para máis tarde porque nós non queremos iso - queremos esa memoria a continuar por un longo tempo. E nós temos un punteiro para o espazo na memoria que só alocado. Usan tamaño nó, non sumar os campos. Non xerar a man o número de bytes, en vez diso, use sizeof para que saibamos que estamos recibindo un número adecuado de bytes. Temos seguro de que o noso para probar chamada malloc conseguiu. Iso é algo que quere facer en xeral. En máquinas modernas, a falta de memoria non é algo que é fácil a menos que está a asignación dunha tonelada de cousas e facer unha lista enorme, pero se está construíndo cousas para, digamos, como un iPhone ou un Android, ten recursos limitados de memoria, especialmente se está facendo algo intenso. Polo tanto, é bo para poñerse en práctica. 

Repare que eu usei algunhas funcións diferentes aquí que xa viu que son unha especie de novo. Entón fprintf é como printf excepto o seu primeiro argumento é o fluxo para o que quere imprimir. Neste caso, queremos imprimir a cadea de erro estándar que é distinto do estándar outstream. Por defecto, el mostra-se no mesmo lugar. Ela tamén imprime á terminal, pero pode - usando os comandos que aprendeu sobre as técnicas de redirección, que aprendeu na video de Tommy por conxunto de problemas 4, pode dirixilas-lo para diferentes áreas e, despois, saír, aquí, sae do seu programa. É esencialmente como volver de inicio, agás que usamos, porque aquí saída de retorno non vai facer nada. Non estamos no inicio, para retorno non saír do programa como queremos. Entón, usamos a función de saída e darlle un código de erro. Entón, aquí imos definir campo novo nodo de valor, o seu campo i igual a i, e entón conecta-lo. Montar punteiro seguinte, o novo nó para que apunte cara ao primeiro, e despois na primeira vai agora apuntar para o novo nodo. Estas primeiras liñas de código, estamos realmente construíndo o novo nodo. Nin as dúas últimas liñas desta función, pero os primeiros. Pode realmente saír nunha función, nunha función auxiliar. Que moitas veces é o que fago é, eu retirala-lo nunha función, Eu chamo-lle algo como o de construción, e que mantén a función prepend moi pequena, con só 3 liñas de entón. Fago unha chamada para o meu función do nó de construción, e entón eu todo fíos para arriba. 

A última cousa que quero te amosar, e eu vou deixar facer append e todo o que no seu propio país, é como iterar sobre unha lista. Hai unha morea de maneiras diferentes de abordar unha lista. Neste caso, imos atopar a lonxitude dunha lista. Entón, imos comezar coa lonxitude = 0. Isto é moi semellante á escritura strlen para unha cadea. Iso é o que quero amosar para ti, este lazo for ben aquí. Parece medio funk, non é o habitual int i = 0, i <calquera que sexa, i + +. En vez diso, está a iniciar a variable n ser o inicio da lista. E entón, cando a nosa variable iterator non é nulo, nós continuar. Isto porque, por convención, o fin da nosa lista será nulo. E, a continuación, para incrementar, en vez de facer + +, o equivalente lista ligada de + + é n = n-> seguinte. 

Eu vou deixar cubrir as lagoas aquí porque estamos fóra do tempo. Pero manter isto presente como traballar en serie de exercicios seus spellr. Listas ligadas, se está aplicando unha táboa hash, vai certamente ser moi útil. E, tendo esta expresión para looping sobre as cousas van facer a vida moito máis fácil, eu espero. Calquera dúbida, rapidamente? [Sam] Será que enviar o SLL completado e sc? [Hardison] Yeah. Vou enviar láminas concluídas e pila SLL completado e queue.cs. [CS50.TV]