[Powered by Google Translate] [Sección 6] [máis cómodo]
[Rob Bowden] [Harvard University]
[Esta é CS50.] [CS50.TV]
>> Podemos ir para a nosa sección de preguntas.
Eu mandei a URL para o espazo antes.
O inicio da sección de preguntas din-
Ao parecer, eu non son enteiramente unsick é unha pregunta moi fácil
só o que é valgrind?
O que valgrind facer?
Alguén quere dicir que valgrind fai?
[Estudante] verifica a memoria.
Si, valgrind é un verificador de memoria xeral.
É, ao final, di que se tes algunha derrames de memoria,
que é principalmente o que estamos usando para iso, porque se quere
facer ben no conxunto de problemas ou se quere
obter na tarxeta grande, ten que ter ningún escape de memoria que sexa,
e no caso de que vostede un baleirado de memoria que non pode atopar,
tamén ter presente que cando se abre un ficheiro
e se non pecha-lo, iso é un baleirado de memoria.
>> Unha morea de persoas están á procura de algún no que eles non están liberando
cando, en realidade, non pechar o dicionario no primeiro paso.
Tamén di que se ten calquera válido le ou escribe,
o que significa que se tentar definir un valor
que está alén do fin da pila e que non aconteza o fallo seg
pero valgrind pega, como non debe realmente ser escrito alí,
e entón vostede definitivamente non debe ter ningunha desas tamén.
Como vostede usa Valgrind?
>> É unha cuestión xeral de
tipo de executa-lo e ollar para a saída.
A saída é sobrecargar unha morea de veces.
Hai tamén erros de diversión onde se ten algo moi mal
suceder en un loop, a continuación, el acabará por dicir, "Camiño erros de máis.
Vou deixar de contar agora. "
É basicamente saída textual que ten que analizar.
Ao final, el vai dicir calquera escape de memoria que ten,
cantos bloques, o que pode ser útil, pois
se é un unfreed bloque, entón é xeralmente máis fácil de atopar
de 1.000 bloques unfreed.
1.000 bloques unfreed probablemente significa que non está liberando
súas listas ligadas de forma adecuada ou algo así.
Isto valgrind.
>> Agora temos a nosa sección de preguntas,
que non precisa facer a descarga.
Podes premer no meu nome e tire-los no espazo.
Agora prema en min.
Revisión 1 será de pila, que estamos a facer en primeiro lugar.
Revisión 2 será cola e Revisión 3 será a lista vinculada illadamente.
Comezando coa nosa pila.
Como se di aquí, unha pila é unha das máis básicas,
estruturas de datos fundamentais da ciencia da computación.
O exemplo prototípico é moi
a pila de bandexas no salón de cea.
É basicamente sempre que está a ser presentado a unha pila,
alguén vai dicir: "Oh, como unha pila de bandexas."
Vostede empilhar as bandexas para arriba.
Entón cando vai tirar unha bandexa,
a primeira bandexa que está a ser levado é a última que foi colocado na pila.
A pila tamén, como se di aquí-
temos o segmento de memoria denominada pila.
E por que é chamado de pila?
>> Porque, como unha estrutura de datos de pila,
el empurra e aparece pila de cadros na pila,
onde cadros de pila son como unha chamada específica dunha función.
E como unha pila, sempre ten que voltar
a partir dunha chamada de función antes de descender en cadros menores pila de novo.
Non podes ter principal chamada barra chamada foo e retorno barra directamente principal.
El sempre ten que seguir a pila correcta empurrando e popping.
As dúas operacións, como eu dixen, son push e pop.
Estes son termos universais.
Debes saber push e pop en termos de pilas, non importa o que.
Imos ver colas son un pouco diferente.
El realmente non ten un termo universal, pero push e pop son universais para pilas.
Push é só poñer na pila.
Pop é sacar a pila.
E vemos aquí temos a nosa pila typedef struct,
por iso temos cordas char **.
Non sexa con medo por calquera **.
Isto vai acabar sendo unha matriz de cadeas
ou unha matriz de punteiros para caracteres, onde
punteiros para personaxes tenden a ser cordas.
Non ten que ser cadeas, pero aquí, eles van ser strings.
>> Nós temos unha matriz de cadeas.
Temos un tamaño, o que representa cantos elementos están na pila,
e despois temos a capacidade, que é o número de elementos pode ser na pila.
A capacidade que comezar como algo maior que 1,
pero o tamaño vai comezar como 0.
Agora, hai basicamente tres xeitos diferentes que pode pensar dunha pila.
Así, hai probablemente máis, pero as dúas principais formas son
pode implementar lo usando unha matriz, ou pode implementar lo usando unha lista ligada.
Listas ligadas son unha especie de trivial para facer pilas de.
É moi fácil facer unha pila empregando listas ligadas,
Entón, aquí, imos facer unha pila empregando matrices,
e en seguida, usando matrices, tamén hai dúas formas que pode pensar sobre iso.
Antes, cando dixo que temos unha capacidade para a pila,
para que poida axustar un elemento na pila.
>> O único xeito que podería acontecer é así que acertar 10 elementos, entón está feito.
Podes saber que existe un límite superior de 10 cousas no mundo
que nunca vai ter máis que 10 cousas na súa pila,
caso en que pode ter un límite superior do tamaño do seu stack.
Ou podería ter a súa pila ser ilimitado,
pero se está facendo unha matriz, o que significa que cada vez que acertar 10 elementos,
entón vai ter que medrar para 20 elementos, e cando bate 20 elementos,
vai ter que medrar a súa matriz de 30 elementos ou 40 elementos.
Está indo a necesidade de aumentar a capacidade, que é o que imos facer aquí.
Cada vez que alcanzar o tamaño máximo da nosa pila,
cando empurrar outra cousa, nós imos ter que aumentar a capacidade.
Aquí, nós impulso declarado como impulso bool (char * str).
* Str Char é a cadea que estamos empurrando para a pila,
bool e só se se conseguimos ou non.
>> Como non?
Cal é a única circunstancia que pode pensar
onde iriamos ter voltar falso?
Si
[Estudante] Se está cheo e estamos a usar unha implementación limitada.
Si, así como nós definimos, el respondeu
se é total e estamos a usar unha aplicación limitada.
Entón, nós definitivamente return false.
Así que alcanzou 10 cousas na matriz, non pode caber 11, así volvemos falso.
E se é ilimitado? Si
Se non pode ampliar a matriz por algún motivo.
Si, entón a memoria é un recurso limitado,
e, finalmente, manter as cousas empurrando para a pila de unha e outra vez,
imos tentar reservar un maior matriz para caber
maior capacidade, malloc e ou o que estamos usando vai voltar falso.
Ben, malloc volverá nulo.
>> Teña en conta que, cada vez que sempre chamar malloc, ten que comprobar a ver se
retorna nulo ou ben que é unha dedución corrección.
Dende que nós queremos ter unha pila ilimitada,
o único caso que imos estar retornando teito é se intentemos
aumentar a capacidade e malloc ou o que retorna falso.
Entón pop non ten argumentos,
e devolve a cadea de caracteres que está na parte superior da pila.
Todo o que foi máis recentemente colocado na pila é o pop volve,
e tamén elimina da pila.
E noten que retorna nulo se non hai nada na pila.
É sempre posible que a pila está baleira.
En Java, se está acostumado a iso, ou outras linguas,
intentando aparecer a partir dunha pila baleira pode causar unha excepción ou algo así.
>> Pero en C, nulo é unha especie de gran cantidade de casos como tratar con estes problemas.
Voltar nulo é como nós imos para significar que a pila estaba baleiro.
Nós fornecen o código que ha probar a funcionalidade do seu stack,
aplicar push e pop.
Iso non vai ser unha morea de código.
Vou, en realidade, antes de facelo, Consello, suxestión-
Se aínda non viu, malloc non é a única función
que aloca memoria na pila para ti.
Hai unha familia de funcións alloc.
O primeiro é malloc, que está acostumado.
Entón hai calloc, que fai a mesma cousa que malloc,
pero vai zerar todo para ti.
Se vostede sempre quixo para definir todo para null despois mallocing algo
ten que ter usado só calloc, en primeiro lugar, en vez de escribir
un loop for a zerar todo o bloque de memoria.
>> Realloc é como malloc e ten unha morea de casos especiais,
pero basicamente o que fai é realloc
leva un punteiro que xa fora asignado.
Realloc é a función que quere estar prestando atención aquí.
É preciso un punteiro que xa fora devolto a partir de malloc.
Imos dicir que solicitar malloc un punteiro de 10 bytes.
Entón, máis tarde entender que quería 20 bytes,
Entón chama realloc en que o punteiro con 20 bytes,
realloc e automaticamente copiar todo para ti.
Se acaba de chamar malloc novo, como eu teño un bloque de 10 bytes.
Agora eu teño un bloque de 20 bytes,
entón eu malloc 20 bytes, entón eu teño que copiar manualmente ao longo dos 10 bytes de o primeiro
na segunda cousa e entón libre o primeiro.
Realloc vai tratar con isto para ti.
>> Observe a sinatura vai ser void *,
que é só devolver un punteiro para o bloque de memoria,
a continuación, void * PTR.
Podes pensar en void * como un punteiro xenérico.
Xeralmente, nunca xestione void *,
malloc pero está retornando un void *, e entón é só usar como
é dicir, en realidade, vai ser un char *.
Void * anterior, que fora devolto por malloc
agora vai ser pasado para realloc e tamaño
é o novo número de bytes que quere reservar para que a súa nova capacidade.
Eu vou te dar un par de minutos, e facelo no noso espazo.
Comece Revisión 1.
Vou deixar despois espero que sobre tempo suficiente para aplicar push,
e entón eu vou dar-lle outra rotura de facer pop.
Pero realmente non é que o código moito en todo.
A maior parte do código é probablemente o material en expansión, a expansión da capacidade.
Ok, non hai presión para ser completamente feito,
pero sempre que sente que está no camiño certo, iso é bo.
>> Alguén ten algún código que sentirse cómodo comigo tirando para arriba?
Si, eu vou, pero alguén ten algún código que podes tirar cara arriba?
Ok, pode comezar, garda-lo, sexa o que sexa?
Eu sempre esquezo que paso.
Ok, ollando para push,
quere explicar o seu código?
[Estudante] Primeiro de todo, eu aumentei o tamaño.
Eu creo que talvez debería ter que de calquera xeito, eu aumentei o tamaño,
e eu ver se é menos que a capacidade.
E se é menos que a capacidade, eu engadir á matriz que xa temos.
E se non é, eu multiplicar a capacidade por 2,
e eu realocar a matriz cordas para algo cun tamaño maior capacidade agora.
E despois, se falla, eu digo o usuario e voltar falso,
e se está ben, entón eu coloque a corda no novo local.
>> [Rob B.] Nótese tamén que a un operador bit a bit agradable aquí
a multiplicar por 2.
Lembre, desvío á esquerda é sempre vai ser multiplicada por 2.
Desprazamento cara á dereita está dividido por dous, sempre que lembre que isto significa
dividir por 2, como en un enteiro dividido por 2.
Pode truncar a 1 aquí ou alí.
Pero cambio deixada por un sempre vai ser multiplicado por 2,
a menos que desbordan os límites do número enteiro, e entón non vai ser.
Un comentario lateral.
Eu gusto de facer iso non vai cambiar a codificación calquera caso,
pero me gustaría facer algo así.
El realmente está indo a facelo un pouco máis.
Quizais este non é o caso perfecto para amosar que,
pero eu gosto de segmento que nestes bloques de-
ok, se iso acontecer, entón eu vou facer algo,
e, a continuación, a función está feito.
Eu non teño de role meus ollos todo o camiño ata a función
para ver o que pasa despois do outro.
E, se iso acontecer, entón eu volver.
Tamén ten o beneficio adicional de todo agradable para alén deste
agora é desprazado cara á esquerda unha vez.
Eu xa non precisa que sempre preto ridiculamente longas colas,
entón eses 4 bytes pode axudar, e tamén a algo máis á esquerda é,
a menos resaltado se sentiría se lle gusta, todo ben, eu teño que lembrar
Eu estou actualmente en un loop while dentro dun interior máis de un loop.
En calquera lugar pode facelo de retorno inmediato, eu medio que me gusta.
É totalmente opcional e non se espera de calquera forma.
>> [Estudante] Debe haber un tamaño - na condición de fallo?
A condición de fallo aquí é que nós non realloc, entón si.
Observe como na súa condición de fallo, presuntamente,
a non ser que o material libre despois, estamos sempre vai fallar
non importa cantas veces nós tentar empurrar algo.
Se seguimos a empuxar, imos manter o tamaño do incremento,
aínda que non estamos poñendo todo na pila.
Normalmente non aumentar o tamaño ata
despois logramos poñelas na pila.
Podemos facer, por exemplo, ou aquí e aquí.
E entón, en vez de dicir s.size capacidade ≤, é menos que a capacidade,
só porque nos cambiamos onde estaba todo.
>> E lembre, o único lugar que podería voltar falso
é aquí onde realloc retornou nulo,
e se ocorrer de se lembrar de erro estándar,
quizais pode considerar este un caso en que quere imprimir un erro estándar,
stderr para fprintf en vez de só imprimir directamente á saída estándar.
Unha vez máis, iso non é unha expectativa, pero é un erro,
printf escribir, entón podes querer facelo imprimir ao erro estándar en vez de saída estándar.
>> Alguén ten algunha outra cousa a notar? Si
[Estudante] Pode ir ata o [inaudível]?
[Rob B.] Si, o binariness real del ou só o que é?
[Estudante] Entón multiplicar isto por 2?
[Rob B.] Si, basicamente.
En terra binario, sempre temos o conxunto de díxitos.
Cambiando esta esquerda por unha basicamente inserir-lo aquí no lado dereito.
Voltar iso, basta lembrar que todo en binario
é unha potencia de 2, polo que esta representa 2 a 0,
este 2 a 1, 2 para a esta 2.
Para inserir un 0 para o lado dereito agora, só cambiar todo de novo.
O que adoitaba ser de 2 a 0 é agora 2 a 1, 2 e é o 2.
O lado dereito que inserimos
é necesariamente vai ser 0,
o que ten sentido.
Se xa se multiplicar un número por 2, iso non vai acabar estraño,
de xeito que o 2 ata o lugar de 0 debe ser de 0,
e é iso que eu medio que alertou sobre antes e se fai pasar para cambiar
ademais do número de bits de un número enteiro,
entón este é un vai acabar saíndo.
Esa é a única preocupación se ocorrer de estar lidando con capacidades moi grandes.
Pero nese punto, entón está lidando con unha matriz de miles de millóns de cousas,
que pode non caber na memoria de calquera maneira.
>> Agora podemos chegar ao pop, o que é aínda máis fácil.
Vostede podería facer como se ocorrer de aparecer unha morea,
e agora está na metade da súa capacidade novo.
Vostede podería realloc para diminuír a cantidade de memoria que ten,
pero non ten que se preocupar con iso, entón o caso realloc só vai ser
crecente memoria, nunca baixar a memoria,
que vai facer de super pop sinxelo.
Agora filas, que van ser como pilas,
pero a orde que Tomé as cousas é invertida.
O exemplo prototípico dunha fila é unha liña,
entón eu creo que se fose inglés, eu diría
un exemplo prototípico dunha fila é unha fila.
Así como unha liña, se é a primeira persoa en liña,
espera ser a primeira persoa fóra da liña.
Se vostede é a última persoa na liña, vai ser a última persoa atendida.
Chamamos ese estándar FIFO, mentres pila era patrón LIFO.
Estas palabras son moi universal.
>> Como pilas e diferenza de matrices, as colas normalmente non permiten o acceso a elementos no medio.
Aquí, unha pila, temos push e pop.
Aquí, pasa que temos chamado enqueue e dequeue.
Eu tamén oín-los chamado de quenda e unshift.
Eu oín persoas diciren push e pop para tamén aplicar a filas.
Oín inserir, eliminar,
para push e pop, se está falando de pilas, está empurrando e popping.
Se está falando sobre filas, pode escoller as palabras que desexa utilizar
para a inserción e eliminación, e non hai consenso sobre o que debe ser chamado.
Pero aquí temos enqueue e dequeue.
Agora, a estrutura é case idéntico ao da estrutura de pila.
Pero temos que manter o control de cabeza.
Coido que di aquí, pero por que necesitamos da cabeza?
Os prototipos son practicamente idénticos ao push e pop.
Podes pensar niso como push e pop.
A única diferenza é pop volve en vez da última, está retornando o primeiro.
2, 1, 3, 4, ou algo así.
E aquí está o principio.
A nosa cola está completamente cheo, por iso hai catro elementos nel.
O fin da nosa fila é actualmente de 2,
e agora imos para introducir algo máis.
>> Cando queremos introducir ese algo máis, o que fixemos para a versión de pila
é que estenden o noso bloque de memoria.
Cal é o problema con iso?
[Estudante] move o 2.
O que eu dixen antes sobre o fin da cola,
iso non ten sentido que comezan o 1,
entón queremos dequeue 1, entón dequeue 3, entón dequeue 4,
entón dequeue 2, entón desenfileirar este.
Non podemos usar realloc agora,
ou, como mínimo, ten que usar realloc dun xeito diferente.
Pero probablemente non debe só usar realloc.
Vai ter que copiar manualmente súa memoria.
>> Existen dúas funcións de copiar a memoria.
Hai memcopy e memmove.
Actualmente estou lendo as páxinas do manual para ver cal deles vai querer empregar.
Ok, memcopy, a diferenza é
que memcopy e memmove, un trata do caso correctamente
onde está copiando a unha rexión que pasa a sobrepasar-se a rexión
está copiando.
Memcopy non tratar con isto. Memmove fai.
Podes pensar no problema como-
digamos que quero copiar este cara,
estes catro para este cara.
Ao final, o que a matriz debe ser semellante
tras a copia é 2, 1, 2, 1, 3, 4, e, a continuación, algunhas cousas ao final.
Pero esta é dependente da orde en que, en realidade, copiar,
pois, se non considerarmos o feito de que a rexión que está copiando en
igual que estamos copiando,
entón podemos facer como comezo aquí, por favor copie o 2 ao lugar que quere ir,
a continuación, pasar os nosos punteiros para adiante.
>> Agora imos estar aquí e aquí, e agora queremos copiar
este cara esa cara e mover os nosos punteiros para adiante.
O que imos acabar quedando é de 2, 1, 2, 1, 2, 1
en vez do 2 apropiado, 1, 2, 1, 3, 4, porque
2, 1 superou o orixinal 3, 4.
Memmove tirantes que correctamente.
Neste caso, basicamente, só Utilice sempre memmove
porque trata correctamente.
Xeralmente non realizar calquera peor.
A idea é, en vez de comezar de inicio e copia deste xeito
como fixemos aquí, que comeza a partir do final e copia,
e, nese caso, vostede non pode ter un problema.
Non hai perda de rendemento.
Sempre use memmove. Nunca te preocupes memcopy.
E é aí onde vai ter que por separado memmove
a porción envolta en torno a súa cola.
Non te preocupes se non completamente feito.
Isto é máis difícil do que pila, pop push, e.
>> Alguén ten algún código que podería traballar?
Mesmo completamente incompleto?
[Estudante] Si, é completamente incompleta, con todo.
Completamente incompleta é bo, sempre que-pode gardar a revisión?
Eu esquezo que en cada momento.
Ok, ignorando o que ocorre cando necesitamos cambiar o tamaño as cousas.
Ignorar por completo Adaptación.
Explicar este código.
Estou comprobando en primeiro lugar, o tamaño é inferior a primeira copia de todas
e despois diso, eu insiro me tomar a cabeza + tamaño,
e eu que seguro que implica a capacidade da matriz,
e eu introducir a nova cadea nesa posición.
Entón eu aumentar o tamaño e voltar true.
>> [Rob B.] Este é sempre un dos casos en que vai querer estar usando mod.
Calquera tipo de caso onde enrolar, se pensas que enrolar,
o pensamento inmediato debe ser mod.
Como unha optimización rápido / facer o seu código dunha liña máis curta,
entender que a liña inmediatamente logo deste
é só o tamaño + +, entón mesturar en que esta liña, tamaño + +.
Agora aquí abaixo, temos o caso
onde non ten memoria suficiente,
por iso estamos aumentando a nosa capacidade por 2.
Eu creo que podería ter o mesmo problema aquí, pero podemos ignore-lo agora
onde se non conseguiu aumentar a súa capacidade,
entón vai querer diminuír a súa capacidade en 2 de novo.
Outra nota curta é exactamente como pode facer + =,
Tamén pode facer << =.
Case todo pode ir antes de igual a igual, + =, | =, & =, << =.
Char * novo é o noso novo bloque de memoria.
Oh, aquí.
>> O que a xente pensa sobre o tipo do noso novo bloque de memoria?
[Estudante] Debe ser char **.
Pensando na nosa estrutura aquí enriba,
cordas é o que estamos realocando.
Estamos a facer un novo almacenamento dinámico enteiro para os elementos na cola.
O que nós imos estar atribuíndo ás súas cordas é o que estamos mallocing agora,
e tan nova, vai ser un char **.
Vai ser unha matriz de cadeas.
Entón o que é o caso en que imos regresar falso?
[Estudante] Deberiamos estar facendo o char *?
[Rob B.] Si, boa chamada.
[Estudante] O que foi iso?
[Rob B.] Nós queriamos facer o tamaño char *, porque non estamos máis-
este sería realmente un problema moi grande, porque sizeof (char) sería 1.
Sizeof char * vai ser 4,
iso unha morea de veces, cando está lidando con ints,
tende a fuxir con el porque o tamaño de int e tamaño de int *
nun sistema de 32 bits vai ser a mesma cousa.
Pero aquí, sizeof (char) e sizeof (char *) son agora vai ser a mesma cousa.
>> ¿Que é a circunstancia en que volva falso?
[Estudante] Nova é nulo.
Si, si é novo é nulo, nós voltar falso,
e eu vou xogar aquí-
[Estudante] [inaudível]
[Rob B.] Si, iso é óptimo.
Vostede podería facer dúas veces a capacidade ou cambio de capacidade 1 e só entón colocouse a aquí ou o que sexa.
Nós imos facer todo o que se tiña.
Capacidade >> = 1.
E nunca vai ter que se preocupar en perder o seu lugar un
porque deixou desviado por un, de xeito que o seu sitio un é necesariamente a 0,
tan certo desprazamento por 1, aínda vai estar ben.
[Estudante] Debe facelo antes do retorno?
[Rob B.] Si, iso non fai ningún sentido.
>> Agora, imos supor que imos acabar volvendo verdade ata o final.
A maneira que nós imos facer estas memmoves,
temos que ter coidado coa forma como as facemos.
Alguén ten algunha suxestión de como as facemos?
Aquí está o noso principio.
Inevitablemente, queremos comezar a principios de novo
e copia en cousas de alí, 1, 3, 4, 2.
Como fai iso?
En primeiro lugar, eu teño de ollar para a páxina do manual para memmove novo.
Memmove, a orde de argumentos é sempre importante.
Queremos que o noso primeiro destino, segundo fonte, a terceira dimensión.
Hai unha serie de funcións que inverten orixe e destino.
Orixe, destino, tende a ser un pouco consistente.
Movemento, que é volver?
El retorna un punteiro para o destino, por calquera motivo, pode querer iso.
Podo imaxinar lelo, pero queremos avanzar cara ao noso destino.
>> O que é o noso destino será?
[Estudante] Novo.
[Rob B.] Si, e onde estamos copiando?
A primeira cousa que estamos copiando é este 1, 3, 4.
Cal é esta-1, 3, 4.
Que é o enderezo do 1?
Que é o enderezo que 1?
[Estudante] [inaudível]
[Rob B.] Head + o enderezo do primeiro elemento.
Como podemos obter o primeiro elemento na matriz?
[Estudante] Fila.
[Rob B.] Si, q.strings.
Teña en conta que, aquí, a nosa cabeza é 1.
Drogas. Eu só creo que é Magic
Aquí, a nosa cabeza é 1. Eu vou cambiar a miña cor tamén.
E aquí está cordas.
Tanto, nós pode escribir como fixemos aquí
con cabezas + q.strings.
Unha morea de xente tamén escribilo lo e q.strings [cabeza].
Isto non é realmente menos eficiente.
Podes pensar niso como está dereferencing-lo e, a continuación, obter o enderezo,
pero o compilador vai traducir-lo para o que tiñamos antes de calquera forma, q.strings cabeza +.
De calquera maneira que quere pensar niso.
>> E cantos bytes que queremos copiar?
[Estudante] Capacidade - cabeza.
Capacidade - cabeza.
E entón podes sempre escribir un exemplo
para descubrir se isto é certo.
[Estudante] Ela precisa ser dividido por dous, entón.
Si, entón eu creo que nós poderíamos usar tamaño.
Aínda temos tamaño ser-
usando tamaño, que ten tamaño igual a 4.
O noso tamaño e 4. A nosa cabeza é unha.
Queremos copiar estes tres elementos.
Esa é a comprobación de sanidade que tamaño - cabeza é correctamente 3.
E volver aquí, como dixemos antes,
se usássemos capacidade, entón teriamos que dividir por dous
porque xa creceu a nosa capacidade, entón en vez diso, imos usar o tamaño.
Que copiar esa parte.
Agora, necesitamos copiar a outra parte, a parte que está á esquerda do inicio.
>> Isto vai memmove en que posición?
[Estudante] tamaño Plus - cabeza.
Si, por iso, xa copiou en tamaño - bytes de cabeza,
e así por onde queremos copiar os bytes restantes é novo
e tamaño de menos ben, o número de bytes que xa copiado dentro
E entón onde estamos copiando?
[Estudante] Q.strings [0].
[Rob B.] Si, q.strings.
Podiamos facer e q.strings [0].
Isto é moito menos común do que este.
Se só vai ser 0, entón tenden a ver q.strings.
É aí onde estamos copiando.
Cantos máis que nos queda para copiar? >> [Estudante] 10.
Dereito.
[Estudante] Temos que multiplicar 5-10 veces o tamaño dos bytes ou algo así?
Si, por iso este é o lugar onde, o que exactamente estamos copiando?
[Estudante] [inaudível]
Cal é o tipo de cousas que estamos copiando?
[Estudante] [inaudível]
Si, entón o char * s que estamos copiando, non sabemos onde os proveñen.
Ben, onde están apuntando, como as cordas, acabamos empurrando-o para a fila
ou enqueuing para a cola.
Onde os están vindo, non temos idea.
Nós só necesitamos manter o control do char * s si.
Nós non queremos copiar tamaño - bytes de cabeza.
Queremos copiar o tamaño - cabeza char * s,
entón imos multiplicar isto por sizeof (char).
Mesmo aquí abaixo, cabeza * sizeof (char *).
>> [Estudante] E sobre [inaudível]?
Iso aquí?
[Estudante] Non, a continuación diso, o tamaño - cabeza.
[Rob B.] Iso aquí?
Aritmética de punteiro.
Como a aritmética de punteiro está indo para o traballo é
el automaticamente multiplica polo tamaño do tipo que estamos lidando.
Así como aquí, novo + (tamaño - cabeza)
é exactamente equivalente a & [tamaño - cabeza] Novo
ata que esperamos que funcione correctamente,
pois, se estamos lidando con unha matriz int, non facer índice int-
ou se é do tamaño de 5 e quere que o elemento 4, entón o índice que no
int array [4].
Vostede non fan [4] * O tamaño int.
Que manipula-lo automaticamente, e neste caso
é literalmente equivalente, entón, a sintaxe soporte
é só ir a ser convertido para iso así que compilar.
Iso é algo que cómpre ter coidado con iso
cando está engadindo tamaño - cabeza
está engadindo non un byte.
Vostede está engadindo un char *, que pode ser unha máis ou o que sexa.
>> Outras preguntas?
Ok, dequeue vai ser máis fácil.
Eu vou te dar un minuto de aplicar.
Ah, e eu creo que esa é a mesma situación onde
que o caso enqueue, se estamos enqueuing nulo,
quizais queremos tratar con isto, quizais non.
Non imos facelo de novo aquí, pero aínda que o noso caso pila.
Se enfileirar nulo, que pode querer ignore-lo.
Alguén ten algún código que podes tirar cara arriba?
[Estudante] eu só teño dequeue.
A versión 2 é que, todo ben.
Quere explicar?
[Estudante] Primeiro, asegurarse de que hai algo na cola
e que o tamaño está indo para abaixo en 1.
Cómpre facer iso, e despois volver a cabeza
e mover a cabeza 1.
Ok, entón non é un caso extremo, temos que considerar. Si
[Estudante] Se a súa cabeza está no último elemento,
entón non quere cabeza para apuntar fóra da matriz.
>> Si, tan pronto como sexa cabeza bate o fin da nosa matriz,
cando desenfileirar, a nosa cabeza debe ser modded a 0.
Desafortunadamente, non podemos facelo nunha única etapa.
Eu creo que a forma que eu probablemente resolve-lo é
este vai ser un char *, o que estamos volvendo,
calquera que sexa o seu nome variable quere ser.
Entón queremos mod cabeza pola nosa capacidade
e despois volver Ret.
Unha morea de xente aquí que poderían facerse
Este é o caso de ver a xente, porque facer a cabeza
é maior que a capacidade, facer a cabeza - capacidade.
E iso é só a traballar en torno ao que é mod.
Xefe mod = capacidade é moito máis limpo
dun invólucro en torno ao que se a cabeza maior que a cabeza de capacidade - A capacidade.
>> Preguntas?
Ok, a última cousa que nos queda é a nosa lista encadeada.
Pode ser usado para algúns dos comportamentos lista ligada se fixo
listas ligadas nas súas táboas de hash, se fixo unha táboa hash.
Eu recomendo encarecidamente que facer unha táboa hash.
Xa debería ter feito unha trie,
pero intentos son máis difíciles.
En teoría, son assintoticamente mellor.
Pero basta ollar para a tarxeta grande,
e intenta non facer mellor, e eles ocupan máis memoria.
Todo sobre intenta acaba sendo peor para máis traballo.
É o que solución David Malan sempre é
El sempre mensaxes Súa solución trie, e imos ver onde está actualmente.
O que estaba baixo, David J?
El é n º 18, de xeito que non é terriblemente malo,
e que vai ser un dos mellores intentos pode pensar
ou un dos mellores da procura dun trie.
Non é mesmo a súa solución orixinal?
Eu me sinto como solucións trie tenden a ser máis nesta franxa de uso de memoria RAM.
>> Desprácese ata o cumio, e uso de RAM está na casa de un díxito.
Desc para o fondo, e entón comeza a ver intenta
onde comeza o uso de RAM absolutamente enorme,
e intentos son máis difíciles.
Non enteiramente pena, pero unha experiencia educativa se fixo un.
A última cousa é a nosa lista ligada,
e esas tres cousas, pilas, colas e listas ligadas,
calquera cousa futura que fai en ciencia da computación
supoñer que ten familiaridade con estas cousas.
Son tan fundamental para todo.
>> Listas ligadas, e aquí temos unha lista vinculada illadamente vai ser a nosa implantación.
O que significa vinculada illadamente ao contrario dobremente ligada? Si
[Estudante] É só apunta para o punteiro próximo e non para os punteiros,
como o que precede e aquel tras el.
É, entón, en formato de imaxe, o que fago?
Eu teño dúas cousas. Eu teño imaxe e imaxe.
En formato de imaxe, os nosos individualmente listas ligadas,
inevitablemente, temos algún tipo de punteiro para a cabeza da lista,
e, a continuación, dentro da nosa lista, só temos punteiros,
e quizais iso apunta a nulo.
Vai ser o seu deseño típico dunha lista vinculada illadamente.
Unha lista dobremente ligada, pode ir cara atrás.
Se eu lle der calquera nodo na lista, entón podes necesariamente chegar a
calquera outro no da lista se é unha lista dobremente ligada.
Pero se eu te o terceiro nó na lista e é unha lista vinculada illadamente,
ningunha maneira que está indo cada vez para chegar a nós de primeiro e segundo.
E hai beneficios e malefícios, e un un evidente
é incorporarse máis tamaño, e ten que manter o control de onde esas cousas están apuntando agora.
Pero só se preocupan vinculada illadamente.
>> Algunhas cousas que imos ter que aplicar.
O seu nó typedef struct, int i: struct node * seguinte; nodo.
Typedef que deben ser queimados nas súas mentes.
Quiz 1 debe ser como dar un typedef dun nodo de lista ligada,
e ten que ser capaz de rabiscar inmediatamente que abaixo
sen sequera pensar sobre iso.
Eu creo que algunhas preguntas, por que necesitamos struct aquí?
Por que non podemos dicir * no?
[Estudante] [inaudível]
Si
O único que define un nodo como unha cousa
é o typedef si.
Pero a partir deste punto, cando estamos tipo de análise por esta definición do nodo de estrutura,
non terminais noso typedef aínda, entón desde o typedef non rematou,
nó non existe.
Pero struct nodo fai, e ese nó aquí,
iso tamén podería ser chamado de calquera outra cousa.
Isto podería ser chamado n.
Podería ser chamado de nó de lista encadeada.
Podería ser chamado de calquera cousa.
Pero ese nó estrutura debe ser chamada o mesmo que este nodo struct.
O que chama iso ten que ser tamén aquí,
e para que tamén responde o segundo punto da cuestión
É por iso que, moitas veces, cando ves estruturas e typedefs de estruturas,
vai ver estruturas anónimos onde só vai ver typedef struct,
implementación de dicionario estrutura, ou o que sexa.
>> Por que aquí non necesitamos dicir no?
Por que non pode ser unha estrutura anónimo?
É case a mesma resposta.
[Estudante] Debe referirse a el dentro da estrutura.
Si, dentro da estructura, que precisa para referirse á estrutura en si.
Se non dá a estrutura dun nome, se é unha estrutura anónimo, non pode se referir a el.
E por último, pero, polo menos, estes non deben ser todos un pouco simple,
e eles deben axudar a entender se está escribindo isto
que está facendo algo mal, se este tipo de cousas non teñen sentido.
Por último, pero non menos importante, por que iso ten que ser struct * no?
Por que non pode ser só struct próximo no?
[Estudante] Punteiro para a estrutura que vén.
Iso é inevitable que queremos.
Por que nunca ser no struct próximo?
Por que ten que ser struct node * próximo? Si
[Estudante] É como un loop infinito.
Si
[Estudante] Sería todo nun.
Si, só de pensar como sería facer o tamaño ou algo así.
Tamaño dunha estrutura é basicamente + ou - un estándar aquí ou alí.
É basicamente vai ser a suma dos tamaños das cousas na estrutura.
Iso aquí, sen cambiar nada, o tamaño vai ser doado.
Tamaño do nó struct será tamaño de I + tamaño do próximo.
Tamaño da i vai ser 4. Tamaño da próxima vai ser 4.
Tamaño do nó struct vai ser 8.
Se non temos o *, pensando sizeof,
a continuación, sizeof (i) será 4.
Tamaño do nó struct próximo vai ser o tamaño da I + tamaño do nó seguinte struct
+ Tamaño da I + tamaño do nó struct seguinte.
Sería unha recursividade infinita de nós.
É por iso que esta é a forma como as cousas teñen que ser.
>> Unha vez máis, en definitiva Recordar que,
ou polo menos entendelo lo o suficiente para que pode ser capaz de
razón pola cal debe ser parecido.
As cousas que imos querer implantar.
Se a lonxitude da lista
pode enganar e manter en torno a un
lonxitude global ou algo así, pero nós non imos facelo.
Nós imos contar o tamaño da lista.
Nós contén, de xeito que é, basicamente, como unha busca,
por iso temos unha lista ligada de enteiros para ver este enteiro está na lista ligada.
Prepend vai introducir no inicio da lista.
Anexar vai introducir no fin.
Insert_sorted vai inserir na posición clasificada na lista.
Tipo de Insert_sorted asume que nunca usou preceder ou achegar en malos camiños.
>> Insert_sorted cando está aplicando insert_sorted-
imos dicir que temos a nosa lista ligada.
Isto é o que parece actualmente, 2, 4, 5.
Quero introducir 3, polo que, mentres a propia lista xa está clasificado,
é fácil atopar onde 3 pertence.
Eu comezo o 2.
Ok, 3 é maior que 2, entón eu quero continuar.
Oh, 4 é moi grande, entón eu sei 3 está a ir entre 2 e 4,
e eu teño que corrixir punteiros e todas esas cousas.
Pero se nós non estrictamente usar insert_sorted,
como imos só dicir que eu preceder 6,
entón miña lista encadeada vai facer iso.
El agora non ten sentido, polo tanto, para insert_sorted, pode simplemente asumir
que a lista é ordenada, aínda que existan operacións
o que pode causar-lle para non ser ordenado, e é iso.
Atopar un útil de inserción, de xeito estas son as principais cousas que vai ter que aplicar.
>> Por agora, tomar un minuto para facer lonxitude e contén,
e os que deben ser relativamente rápida.
Achegando-se o tempo de peche, polo que ninguén ten nada para a lonxitude ou contén?
Eles van ser case idénticos.
[Estudante] lonxitude.
Imos ver, de revisión.
Okay.
Quere explicar?
[Estudante] Eu só crear un nó punteiro e arrincar a primeira, que é a nosa variable global,
e entón eu comprobar a ver se é nulo, entón eu non ten un fallo de seg e voltar 0 se é o caso.
Se non, eu percorrer, mantendo o control de dentro enteiro
cantas veces eu xa identificado elemento seguinte da lista
e na operación mesmo incremento tamén acceder a este elemento real,
e entón eu continuamente facer a comprobación para ver se é nulo,
e é nulo, entón aborta e só devolve o número de elementos que acceder.
>> [Rob B.] Alguén ten algún comentario sobre calquera cousa?
Isto parece correcto ben sabio.
[Estudante] Eu non creo que precisa do nó == null.
É, entón, se o nó == 0 retorno nulo.
Pero se nulo nó == entón esta-oh, non é unha cuestión de corrección.
Era só está retornando i, pero non é de ámbito agora.
Só ten int i, para i = 0.
Pero se o nodo é nulo, entón eu aínda vai ser 0,
e nós estamos indo para voltar 0, polo tanto, neste caso, é o mesmo.
Outra cousa común é a de manter a declaración
dentro do nó do lazo é.
Vostede podería dicir-oh, non.
Imos mantelo coma este.
Eu, probablemente, poñer int i = 0 aquí,
entón no * nodo = primeiro aquí.
E este é, probablemente, como se librar diso agora.
Este é, probablemente, como eu tería escrito.
Tamén pode ollar-lo así.
Esta estrutura de loop para aquí
debe ser case tan natural para ti como para int i = 0
i é inferior á lonxitude da matriz i + +.
Se é así que iterar sobre unha matriz, isto é como iterar sobre unha lista ligada.
>> Esta debe ser unha segunda natureza nalgún punto.
Con isto en mente, este vai ser case o mesmo.
Vai querer iterar sobre unha lista encadeada.
O No-Eu non teño ningunha idea do que o valor é chamado.
No I.
Se o valor dese nó = i volver certo, e é iso.
Teña en conta que a única forma de sempre volver false
é se iterar sobre a lista enteira conexionada e nunca máis volver verdade,
de xeito que é o que este fai.
Como unha nota lateral, probablemente non vai comezar a engadir ou preceder.
>> Última nota rápida.
Se ves a palabra chave estática, entón imos dicir contador Static int = 0,
entón o que facemos reconto + +, pode basicamente pensar niso como unha variable global,
aínda que eu dixen non é así que nós imos implementar lonxitude.
Eu estou facendo iso aquí, e entón contar + +.
Calquera forma, podemos introducir un nó na nosa lista ligada estamos incrementando a nosa conta.
O punto é que a palabra clave Static significa.
Se eu tivese int count = 0 que sería unha variable antiga regulares global.
O que significa conta Static int é que é unha variable global para este ficheiro.
É imposible para un ficheiro,
gusto de pensar en pset 5, se comezou.
Ten tanto speller.c, e ten dictionary.c,
e simplemente declarar unha cousa global, entón calquera cousa en speller.c
se pode acceder no dictionary.c e viceversa.
As variables globais son accesibles por calquera arquivo c.,
pero variables estáticas só son accesibles desde dentro do propio arquivo,
dentro de corrector ortográfico ou dentro dictionary.c,
este é o tipo de como eu ía declarar miña variable para o tamaño da miña matriz
ou o tamaño do meu número de palabras no dicionario.
Dende que eu non quero declarar unha variable global que calquera ten acceso,
Realmente só se preocupan con iso para os meus propios fins.
>> A cousa boa sobre iso é tamén o material de colisión todo nome.
Se algún ficheiro intenta usar unha variable global chamada conta, as cousas van moi, moi mal,
de xeito que este mantén as cousas ben seguro, e só pode acceder a ela,
e ninguén máis pode, e se alguén declara unha variable global chamada conta,
el non ha interferir coa súa variable estática chamada conta.
Isto é o que é estática. É unha variable de arquivo global.
>> Preguntas sobre algo?
Todo preparado. Tchau.
[CS50.TV]