[Powered by Google Translate] Na programación, moitas veces necesitamos representar listas de valores,
como os nomes dos alumnos nunha sección
ou os seus resultados no último exame.
>> Na linguaxe C, declarado matrices poden ser utilizadas
para almacenar listas.
É doado enumerar os elementos dunha lista
almacenados nunha matriz, e se precisa acceder
ou modificar o elemento da lista om
por algún índice arbitrario I,
que se pode facer en tempo constante,
pero as matrices presentan desvantaxes, tamén.
>> Cando declaralo los, somos obrigados a dicir
na fronte como son grandes,
é dicir, cantos elementos que poden almacenar
e que o tamaño destes elementos son, que é determinada polo tipo.
Por exemplo, int arr (10)
pode almacenar 10 elementos
que son do tamaño dun int.
>> Non podemos cambiar o tamaño dunha matriz tras a declaración.
Temos que facer unha nova matriz se desexa almacenar máis elementos.
A razón desa limitación existe é que o noso
programa almacena todo o conxunto
como unha peza contiguo de memoria.
Dicir que este é o buffer onde se almacenan na nosa matriz.
Pode haber outras variables
situado ao lado da matriz
na memoria, por iso non podemos
só facer a matriz maior.
>> Ás veces, nós queremos cambiar de velocidade a matriz de acceso rápido de datos
para un pouco máis de flexibilidade.
Escriba unha lista ligada, outra estrutura de datos básica
non pode ser tan familiarizado.
A un nivel elevado,
unha lista ligada almacena os datos nunha secuencia de nodos
que están ligados uns ós outros con ligazóns,
polo tanto, "lista ligada." nome
Como veremos, esta diferencia no proxecto
conduce a diferentes vantaxes e desvantaxes
dunha matriz.
>> Aquí está o código C para unha lista moi sinxelo ligada de enteiros.
Podes ver que temos representado cada nodo
na lista como unha estrutura que contén dúas cousas,
un enteiro para almacenar chamado 'Val'
e un enlace ao seguinte nodo na lista
que representamos como un punteiro chamado 'Seguinte'.
Desta forma, é posible seguir toda a lista
con só un único punteiro para o apartado 1,
e entón podemos seguir os punteiros próximos
para o apartado 2,
para o apartado 3,
ao apartado 4,
e así por diante, ata chegar ao final da lista.
>> Pode ser capaz de ver unha vantaxe que ten
sobre a estrutura array estático - con unha lista ligada,
non necesitamos un gran anaco de memoria completamente.
O apartado 1 da lista podería vivir neste lugar na memoria,
eo apartado 2 podería ser todo o camiño ata aquí.
Podemos chegar a todos os nós, non importa onde eles están na memoria,
porque dende o apartado 1, o punteiro preto de cada nodo
nos di exactamente onde ir.
>> Ademais, non hai que dicir na fronte
como unha grande lista encadeada será a nosa forma de facer arrays estáticos,
unha vez que podemos continuar a engadir nós a unha lista
mentres non hai espazo en algún lugar na memoria para novos nós.
Polo tanto, listas ligadas son fáciles de cambiar o tamaño dinamicamente.
Dicir, máis tarde no programa, cómpre engadir máis nós
na nosa lista.
Para inserir un novo nodo na nosa lista en tempo real,
todo o que temos que facer é reservar memoria para ese nodo,
plop por valor de datos,
e despois poñelas onde quere, axustando os punteiros apropiados.
>> Por exemplo, se quixésemos poñer un nó no medio
os nós 2 e 3 da lista,
non teriamos para mover os nós de 2 ou 3 en todo.
Dicir que estamos introducindo este nodo vermello.
Todo o que temos que facer é definir punteiro próximo ao novo nodo
para apuntar para o apartado 3
e, a continuación, religar punteiro próximo apartado 2 do
para apuntar para o novo nodo.
Así, podemos cambiar o tamaño nosas listas na Moscova
desde o noso ordenador non dependen de indexación,
pero si na conexión entre o uso de punteiros para almacena-los.
>> Listas No entanto, unha desvantaxe do ligadas
é que, ao contrario dunha matriz estática,
o ordenador non pode simplemente saltar para o medio da lista.
Dende que o ordenador ten que visitar cada nó na lista ligada
para chegar ó seguinte,
que vai levar máis tempo para atopar un nodo específico
do que sería nun array.
Para percorrer a lista enteira leva un tempo proporcional
a lonxitude da lista,
ou O (n) en notación asintótica.
En media, alcanzando calquera nodo
tamén leva un tempo proporcional a n.
>> Agora, imos realmente escribir un código
que traballa con listas ligadas.
Imos dicir que queremos unha lista ligada de enteiros.
Podemos representar un nó na nosa lista de novo
como unha estrutura con dous campos,
un valor enteiro chamado 'Val'
e un punteiro próximo ao seguinte nodo da lista.
Ben, parece bastante simple.
>> Imos dicir que queremos escribir unha función
que percorre a lista e imprime o
valor almacenado no último nó da lista.
Ben, iso significa que temos que percorrer todos os nodos da lista
para atopar a última, pero a condición de que non está engadindo
ou borrar nada, non queremos cambiar
a estructura interna dos punteiros seguintes na lista.
>> Entón, imos ter un punteiro especificamente para paso
que chamaremos de "rastreador".
Vai rastexaren a través de todos os elementos da lista
seguindo a cadea de punteiros próximos.
Todo o que temos almacenado é un punteiro para o apartado 1,
ou "cabeza" da lista.
Puntos de cabeza para o apartado 1.
É o tipo de punteiro a nó.
>> Para obter o apartado 1 real na lista,
temos que dereference ese punteiro,
pero antes de que poidamos cancelar a referencia de que é preciso comprobar
o punteiro é nulo primeiro.
Se é nulo, a lista está baleira,
e debemos imprimir unha mensaxe que, porque a lista é baleira,
non hai último nodo.
Pero, imos dicir que a lista non é baleira.
Se non é, entón debemos rastrexar toda a lista
ata chegar ao último nodo da lista,
e como podemos saber se nós estamos mirando para o último nó na lista?
>> Ben, se punteiro próxima dun nodo é nulo,
sabemos que estamos no final
desde o último punteiro seguinte tería ningún no seguinte na lista para apuntar.
É unha boa práctica para manter sempre punteiro preto do no pasado inicializar como nulo
ter unha propiedade estandarizada que nos alerta cando chegamos ao fin da lista.
>> Entón, se rastreador → seguinte é nulo,
Lembre que a sintaxe frecha é un atallo para dereferencing
un punteiro para unha estrutura, a continuación, acceder
seu próximo campo equivalente ao incómodo:
(* Rexistro). Seguinte.
Unha vez que teñamos atopado o último nó,
queremos imprimir rastreador → val,
o valor do nodo actual
que sabemos que é a última.
En caso contrario, se non estamos aínda no último nodo na lista,
temos que seguir adiante para o próximo nó na lista
e comprobar que este é o último.
Para iso, basta con facer o noso punteiro rastreador
para apuntar para o próximo valor do nodo actual,
é dicir, o no seguinte na lista.
Isto faise axustar
rastreador = rastreador → seguinte.
A continuación, repetimos este proceso, con un lazo, por exemplo,
ata atopar o último nodo.
Así, por exemplo, se rastreador estaba apuntando á cabeza,
imos definir rastreador para apuntar para rastreador → seguinte,
que é o mesmo que o seguinte campo da alínea 1.
Entón, agora o noso rastreador está a apuntar cara o apartado 2,
e, de novo, repetir este con un ciclo,
ata que teñamos atopado o último nó, isto é,
onde punteiro preto do nodo está a apuntar cara null.
E aí temos que,
atopamos o último nó na lista, e para imprimir o seu valor,
é só usar rastreador → val.
>> O desprazamento non é tan malo, pero o que sobre a inserción?
Imos dicir que queremos inserir un enteiro na posición 4
nunha lista de enteiros.
Que se atopa entre os nodos de corrente 3 e 4.
Unha vez máis, temos que percorrer a lista só para
chegar ao elemento terceiro, aquel que está inserindo despois.
Entón, creamos un punteiro rastreador de novo para percorrer a lista,
comprobar que o noso punteiro cabeza é nulo,
e se non é, apunta noso punteiro rastreador no nó de cabeza.
Entón, estamos no primeiro elemento.
Temos que ir para adiante dous elementos máis antes de que poidamos introducir,
polo que podemos usar un loop
int i = 1; i <3, i + +
e en cada iteração do loop,
avanzar noso punteiro rastreador fronte por un nodo
comprobando o campo preto do nodo actual é nulo,
e se non é, mover noso punteiro rastreador para o próximo nodo
definíndose o igual ao punteiro preto do nodo actual.
Así, desde que o noso circuíto para facelo, di
dúas veces,
chegamos ao apartado 3,
e unha vez que o noso punteiro rastreador alcanzou o nó despois
que queremos introducir o noso enteiro novo,
como é que nós realmente a inserción?
>> Ben, o noso novo enteiro debe ser inserida na lista
como parte da súa estrutura propio no,
unha vez que esta é realmente unha secuencia de nós.
Entón, imos facer un novo punteiro para o nodo
chamado "new_node '
e configure-lo para apuntar para a memoria que agora reservar
sobre a pila para o propio nodo,
ea cantidade de memoria que necesitamos reservar?
Así, o tamaño dun nodo,
e queremos establecer o seu campo val para o número enteiro que desexa inserir.
Imos dicir, 6.
Agora, o nodo contén o seu valor enteiro.
É tamén unha boa práctica para iniciar seguinte campo novo nodo
para apuntar para null,
pero e agora?
>> Temos que cambiar a estrutura interna da lista
e os punteiros próximos contida existente da lista
Nós 3 e 4.
Unha vez que os punteiros próximos determinar a orde da lista,
E xa que estamos introducindo o noso novo no
a dereita no medio da lista,
pode ser un pouco complicado.
Isto porque, lembre, o noso ordenador
só sabe a localización de nós na lista
por mor dos punteiros próximos almacenados nos nos anteriores.
Entón, se algunha vez perdeu a noción de calquera destes lugares,
dicir cambiando un dos punteiros próximos na nosa lista,
por exemplo, dicir que cambiou
campo seguinte o apartado 3 é
para apuntar a algún nó aquí.
Nós estariamos fóra de sorte, porque non faría
Ten algunha idea de onde atopar o resto da lista,
e iso é, obviamente, moi malo.
Entón, nós temos que ter moito coidado sobre a orde
en que manipular os punteiros próximas durante a inserción.
>> Entón, para simplificar, imos dicir que
nosos primeiros catro nós
son denominados A, B, C, e D, as frechas que representan a cadea de punteiros
que conectan os nodos.
Entón, necesitamos introducir noso novo nodo
entre os nós C e D.
É fundamental facelo na orde correcta, e eu vou amosar-lle por que.
>> Imos ollar para a forma incorrecta de facelo primeiro.
Ola, sabemos que o novo nó ten que vir despois C,
entón imos definir punteiro preto do C
para apuntar para new_node.
Todo ben, parece todo ben, só temos que rematar agora por
facendo punto o novo nó do punteiro ao lado D,
pero espera, como podemos facer iso?
O único que podería dicir onde era D,
o punteiro próximo foi previamente almacenado en C,
pero nós só reescreveu o punteiro
para apuntar para o novo nodo,
así xa non temos ningún pista onde D é na memoria,
e nós perdemos o resto da lista.
Non é bo en todo.
>> Entón, como imos facelo certo?
En primeiro lugar, apuntar punteiro seguinte, o novo nó no D.
Agora, os punteiros tanto o novo nó e C do próximo
están apuntando para o mesmo nodo, D,
pero iso é bo.
Agora podemos apuntar punteiro próximo ao C o novo nodo.
Entón, nós fixemos iso sen perder os datos.
No código, C é o nó actual
que a travesía punteiro rastreador está a apuntar,
e D é representada polo nodo apuntado polo campo seguinte do nodo actual,
ou rastreador → seguinte.
Entón, primeiro definir punteiro seguinte, o novo nodo
para apuntar para rastreador → seguinte,
do mesmo xeito que dixo punteiro próxima new_node debería
apuntar D na figura.
Entón, podemos definir punteiro preto do nodo actual
para o noso novo nodo,
así como nós tivo que esperar ata o punto C para new_node no deseño.
Agora todo está en orde, e non perdemos
o control de todos os datos, e fomos capaces de só
furar o noso novo nó no medio da lista
sen reconstruír a cousa toda ou incluso desprazando todos os elementos
do xeito que tería que ter unha matriz de lonxitude fixa.
>> Entón, listas ligadas son un básico, pero importante, estrutura de datos dinámica
que teñen vantaxes e inconvenientes
en comparación coas matrices e outras estruturas de datos,
e, como é frecuentemente o caso en ciencia da computación,
é importante saber cando usar cada ferramenta,
para que poida elixir a ferramenta certa para o traballo correcto.
>> Para máis práctica, proba escribir funcións para
eliminar nós unha lista ligada -
Lembre-se de ter coidado coa orde en que reorganizar
os punteiros próximos para garantir que non perda unha peza da súa lista -
ou unha función para contar os nós nunha lista ligada,
ou un divertimento, para inverter a orde de todos os nós nunha lista ligada.
>> O meu nome é Jackson Steinkamp, ​​este é CS50.