[Powered by Google Translate] En la programación, a menudo necesitamos para representar listas de valores,
tales como los nombres de los estudiantes de una sección
o sus puntuaciones en la última prueba.
>> En el lenguaje C, declaró matrices pueden utilizarse
para almacenar listas.
Es fácil enumerar los elementos de una lista
almacenados en una matriz, y si usted necesita para acceder a
o modificar el elemento de la lista ith
por algún índice arbitrario I,
que se puede hacer en un tiempo constante,
pero las matrices tienen desventajas, también.
>> Cuando les declaro, estamos obligados a decir
desde el principio lo grandes que son,
es decir, cuántos elementos se pueden almacenar
y lo grande que estos elementos son, que se determina por su tipo.
Por ejemplo, arreglo de int (10)
Puede almacenar 10 elementos
que tienen el tamaño de un int.
>> No podemos cambiar el tamaño de una matriz después de la declaración.
Tenemos que hacer una nueva matriz si queremos almacenar más elementos.
La razón de esta limitación que existe es que nuestro
programa almacena toda la matriz
como un trozo contiguo de memoria.
Decir esto es el buffer donde se almacena en nuestra matriz.
Puede haber otras variables
situado justo al lado de la matriz
en la memoria, por lo que no puede
sólo que la matriz más grande.
>> A veces nos gustaría que el comercio de la matriz rápida velocidad de acceso a datos
para un poco más de flexibilidad.
Introduzca la lista enlazada, otra estructura de datos básicos
usted podría no ser tan familiarizados.
En un nivel alto,
una lista enlazada almacena los datos en una secuencia de nodos
que están conectados entre sí con enlaces,
por lo tanto "lista enlazada. 'el nombre
Como veremos, esta diferencia en el diseño
conduce a distintas ventajas y desventajas
de una matriz.
>> Aquí hay un código C para una lista muy simple enlazada de números enteros.
Se puede ver que hemos representado a cada nodo
en la lista como una estructura que contiene dos cosas,
un entero para almacenar llamado 'val'
y un enlace para el nodo siguiente en la lista
que representamos como un puntero llamado 'next'.
De esta manera, podemos seguir la lista entera
con sólo un único puntero al nodo primero,
y luego podemos seguir los siguientes consejos
para el segundo nodo,
al nodo tercero,
para el cuarto nodo,
y así sucesivamente, hasta llegar a la final de la lista.
>> Usted puede ser capaz de ver una ventaja que esto tiene
sobre la estructura matriz estática - con una lista enlazada,
no necesitamos una gran parte de la memoria por completo.
El nodo 1 de la lista podría vivir en este lugar en la memoria,
y el segundo nodo podría ser todo el camino hasta aquí.
Podemos llegar a todos los nodos no importa donde en la memoria son,
porque a partir de la primera nodo, el puntero siguiente de cada nodo
nos dice exactamente dónde ir después.
>> Además, no tienes que decir por adelantado
lo grande que una lista enlazada será el camino que hacemos con arrays estáticos,
ya que podemos seguir añadiendo nodos a una lista
siempre y cuando no hay espacio en algún lugar de la memoria de los nuevos nodos.
Por lo tanto, las listas enlazadas son fáciles de cambiar el tamaño de forma dinámica.
Digamos, más tarde en el programa tenemos que añadir más nodos
a nuestra lista.
Para insertar un nuevo nodo en la lista sobre la marcha,
todo lo que tenemos que hacer es asignar memoria para ese nodo,
plop en el valor de los datos,
y luego colocarlo donde queramos mediante el ajuste de los indicadores apropiados.
>> Por ejemplo, si quisiéramos poner un nodo en el medio
los nodos 2 y 3 de la lista,
no tendríamos que mover los nodos segundo o tercero en absoluto.
Digamos que vas a insertar este nodo rojo.
Todo lo que tendría que hacer es configurar puntero siguiente del nuevo nodo
para que apunte al nodo tercera
y luego volver a colocar el puntero siguiente nodo de segundo
para que apunte a nuestro nuevo nodo.
Por lo tanto, podemos cambiar el tamaño de nuestras listas sobre la marcha
ya que nuestro equipo no depende de la indexación,
sino más bien en vincular el uso de punteros para almacenarlos.
>> Listas Sin embargo, una desventaja de vinculados
es que, a diferencia de una matriz estática,
el ordenador no sólo puede saltar a la mitad de la lista.
Dado que el equipo tiene que visitar cada nodo en la lista enlazada
para llegar a la siguiente,
que va a tomar más tiempo para encontrar un nodo particular
lo que lo haría en una matriz.
Para recorrer toda la lista toma tiempo proporcional
a la longitud de la lista,
o O (n) en notación asintótica.
En promedio, alcanzando cualquier nodo
También se necesita tiempo proporcional a n.
>> Ahora, vamos a realmente escribir código
que trabaja con listas enlazadas.
Digamos que queremos una lista enlazada de enteros.
Podemos representar un nodo en la lista de nuevo
como una estructura con dos campos,
un valor entero llamado 'val'
y un puntero próximo al siguiente nodo de la lista.
Bueno, parece bastante simple.
>> Supongamos que queremos escribir una función
que recorre la lista e imprime el
valor almacenado en el último nodo de la lista.
Bueno, eso significa que tendremos que recorrer todos los nodos de la lista
para encontrar la última, pero ya no estamos añadiendo
o borrar nada, no queremos cambiar
la estructura interna de los punteros siguientes en la lista.
>> Por lo tanto, vamos a necesitar un puntero específicamente para traversal
que llamaremos "crawler".
Se arrastran a través de todos los elementos de la lista
siguiendo la cadena de punteros próximos.
Todos hemos almacenado es un puntero al nodo primero,
o "cabeza" de la lista.
Puntos de la cabeza a la primera nodo.
Es de tipo puntero a nodo.
>> Para obtener la actual primera nodo en la lista,
tenemos que eliminar la referencia este indicador,
pero antes de que podamos deferenciarlo, tenemos que comprobar
si el puntero es nulo en primer lugar.
Si es nulo, la lista está vacía,
y debemos imprimir un mensaje que, debido a que la lista está vacía,
no hay último nodo.
Pero, supongamos que la lista no está vacía.
Si no es así, entonces tenemos que gatear por toda la lista
hasta llegar al último nodo de la lista,
y ¿cómo podemos saber si estamos ante el último nodo en la lista?
>> Bueno, si el puntero siguiente de un nodo es nulo,
sabemos que estamos en el final
desde el siguiente puntero última no tendría ningún nodo siguiente en la lista para apuntar.
Es una buena práctica para mantener siempre puntero siguiente del último nodo de inicializan a null
tener una propiedad estándar que nos avisa cuando hemos llegado al final de la lista.
>> Por lo tanto, si crawler → siguiente es nulo,
recordar que la sintaxis de flecha es un acceso directo para eliminar la referencia
un puntero a una estructura, a continuación, acceder a
su siguiente campo equivalente al torpe:
(* Crawler). Siguiente.
Una vez que hayas encontrado el último nodo,
queremos imprimir crawler → val,
el valor en el nodo actual
que sabemos que es la última.
De lo contrario, si no estamos todavía en el último nodo de la lista,
tenemos que pasar a la siguiente nodo en la lista
y comprobar si ese es el último.
Para ello, se acaba de establecer nuestro puntero sobre orugas
para apuntar al siguiente valor del nodo actual,
es decir, el nodo siguiente en la lista.
Esto se hace mediante el establecimiento
crawler = crawler → siguiente.
Luego repetimos este proceso, con un lazo por ejemplo,
hasta encontrar el último nodo.
Así, por ejemplo, si rastreador estaba apuntando a la cabeza,
nos propusimos rastreador para que apunte a orugas → siguiente,
que es el mismo que el campo próximo de la primera nodo.
Así que, ahora que nuestro rastreador está apuntando al nodo 2,
y, de nuevo, se repite esto con un bucle,
hasta que hayamos encontrado el último nodo, es decir,
donde puntero siguiente del nodo apunta a null.
Y ahí lo tenemos,
hemos encontrado el último nodo de la lista, y la impresión de su valor,
sólo tiene que utilizar crawler → val.
>> Atravesando no es tan malo, pero ¿qué pasa con la inserción?
Digamos que queremos insertar un número entero en la 4 ª posición
en una lista de números enteros.
Que está entre los nodos actuales tercero y cuarto.
Una vez más, tenemos que recorrer la lista sólo para
llegar a la tercera parte, la que estamos insertando después.
Así, creamos un puntero rastreador de nuevo para recorrer la lista,
comprobar si nuestra cabeza puntero es nulo,
y si no lo es, apuntar con el puntero sobre orugas en el nodo principal.
Por lo tanto, estamos en el elemento primero.
Tenemos que ir hacia adelante 2 elementos más antes de que podamos insertar,
por lo que podemos utilizar un bucle for
int i = 1; i <3; i + +
y en cada iteración del bucle,
avanzar en el puntero sobre orugas presentadas por un nodo
comprobando si el campo próximo del nodo actual es nula,
y si no es así, mover nuestro rastreador puntero al siguiente nodo
fijándolo igual al siguiente puntero del nodo actual.
Por lo tanto, desde nuestro bucle para hacer eso, dice
dos veces,
hemos llegado al nodo 3,
y una vez que nuestro puntero rastreador ha alcanzado el nodo después de
que queremos insertar nuestro nuevo entero,
¿cómo es en realidad la inserción?
>> Pues bien, nuestro nuevo entero tiene que ser insertado en la lista
como parte de su propia estructura de nodo,
ya que esto es realmente una secuencia de nodos.
Por lo tanto, vamos a hacer un nuevo puntero al nodo
llamado 'new_node,'
y configurarlo para que apunte a la memoria que ahora asignar
en el montón para el nodo en sí,
y la cantidad de memoria tenemos que asignar?
Pues bien, el tamaño de un nodo,
y queremos establecer su campo val al entero que queremos insertar.
Digamos, 6.
Ahora, el nodo contiene nuestro valor entero.
También es una buena práctica para inicializar campo próximo del nuevo nodo
para apuntar a null,
pero ¿ahora qué?
>> Hay que cambiar la estructura interna de la lista
y los indicadores contenidos en los siguientes de la lista
Los nodos 3 y 4.
Dado que los punteros próximos determinar el orden de la lista,
y ya que estamos introduciendo nuestro nuevo nodo
a la derecha en el medio de la lista,
que puede ser un poco complicado.
Esto es porque, recuerde, nuestro equipo
sólo conoce la ubicación de los nodos en la lista
porque de los punteros próximos almacenados en los nodos anteriores.
Por lo tanto, si alguna vez perdido el rastro de ninguno de estos lugares,
dicen que al cambiar uno de los punteros siguientes en la lista,
Por ejemplo, digamos que cambiamos
campo siguiente nodo de la tercera de
para que apunte a algún nodo por aquí.
Nos gustaría estar fuera de suerte, ya que no lo haría
Tiene alguna idea de dónde encontrar el resto de la lista,
y eso es, obviamente, muy mal.
Por lo tanto, tenemos que tener mucho cuidado con el fin de
en el que manipulamos nuestros punteros próximos durante la inserción.
>> Así que, para simplificar esto, vamos a decir que
nuestros primeros 4 nodos
se denominan A, B, C, y D, con las flechas que representan la cadena de punteros
que conectan los nodos.
Por lo tanto, tenemos que insertar nuestro nuevo nodo
entre los nodos C y D.
Es muy importante hacerlo en el orden correcto, y yo te mostraré por qué.
>> Echemos un vistazo a la forma incorrecta de hacerlo en primer lugar.
Hey, sabemos que el nuevo nodo tiene que venir a la derecha después de C,
así que vamos a establecer el puntero próximo C
para que apunte a new_node.
De acuerdo, parece estar bien, sólo tenemos que terminar ahora por
hacer punto del nuevo nodo puntero próximo a D,
pero espera, ¿cómo podemos hacer esto?
Lo único que nos puede decir donde D es,
fue el siguiente puntero almacenado previamente en C,
pero nos volvió a escribir ese puntero
para que apunte al nuevo nodo,
por lo que ya no tenemos ni idea de donde D es en la memoria,
y hemos perdido el resto de la lista.
No es bueno en absoluto.
>> Así que, ¿cómo podemos hacer esto bien?
En primer lugar, señalar puntero siguiente del nuevo nodo a D.
Ahora, tanto el nuevo nodo y la de C próximos punteros
apuntan hacia el mismo nodo, D,
pero eso está bien.
Ahora podemos señalar siguiente puntero de C en el nuevo nodo.
Por lo tanto, hemos hecho esto sin perder ningún dato.
En el código, C es el nodo actual
que el recorrido puntero rastreador hace referencia,
y D está representado por el nodo al que apunta el campo siguiente nodo actual,
o rastreador → siguiente.
Así, en primer lugar establecer el puntero siguiente del nuevo nodo
para que apunte a orugas → siguiente,
de la misma manera que dijimos puntero próximo new_node deben tener por
apuntar a D en la ilustración.
Entonces, podemos establecer el puntero siguiente del nodo actual
a nuestro nuevo nodo,
del mismo modo que tuvo que esperar al punto C new_node en el dibujo.
Ahora todo está en orden, y no perdió
realizar un seguimiento de los datos, y fuimos capaces de simplemente
pegarse nuestro nuevo nodo en el medio de la lista
sin reconstruir toda la cosa, o incluso cambiando los elementos
la forma en que se han tenido que con una matriz de longitud fija.
>> Por lo tanto, las listas enlazadas son un básico, pero importante, la estructura de datos dinámica
que tienen ventajas y desventajas
en comparación con las matrices y otras estructuras de datos,
y como es a menudo el caso en informática,
es importante saber cuando usar cada herramienta,
para que pueda elegir la herramienta adecuada para el trabajo correcto.
>> Si desea practicar más, intente escribir funciones para
eliminar nodos de una lista enlazada -
recuerde tener cuidado con el orden en el que se reorganizan
los punteros siguientes para asegurarse de que no pierda una buena parte de su lista -
o una función para contar los nodos en una lista enlazada,
o una diversión, para invertir el orden de todos los nodos de una lista enlazada.
>> Mi nombre es Jackson Steinkamp, ​​esto es CS50.