Estudiar

Estructuras de datos lineales



1. Listas

2. Pilas

3. Colas

Listas:

Definición: lista está conformada por ninguno, uno o varios elementos que tienen una relación de adyacencia ordenada donde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último. El tipo de dato de los elementos puede ser cualquiera, pero debe ser el mismotipo para todos. El valor contenido en los elementos puede ser el mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o eliminar elementos a la lista según un criterio particular. Sobre la base de la forma y el lugar de la realización de estas operaciones en la misma, las listas se clasifican en listas de acceso restringido y listas de acceso no restringido.Representación de listas:

La forma clásica de representar una lista es a través de los vectores con la siguiente forma

|A1 |A2 |A3 |…… |……. |An |


Operaciones con listas:

Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:
• Recorrido: Esta operación consiste envisitar cada uno de los nodos que forman la lista. Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
• Inserción: Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:o Insertar un nodo al inicio.
o Insertar un nodo antes o después de cierto nodo.
o Insertar un nodo al final.
• Borrado: La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:
o Eliminar el primer nodo.
o Eliminar el último nodo.
o Eliminar un nodocon cierta información.
o Eliminar el nodo anterior o posterior al nodo cierta con información.
• Búsqueda: Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.


Desarrollo del trayecto del puntero:
El concepto de puntero está basado en la idea de una variable cuya misión es contener la dirección de otravariable a la dirección de memoria de un dato. Se dice entonces que el puntero apunta a la variable, según el tipo de variable al que apunte tendremos un puntero “a” entero, a float, char, etc.

Para trabajar con punteros es importante conocer el significado de los operadores de dirección (símbolo & e in-dirección símbolo &), que también se puede leer como “lo apuntado por”. De este modo &var, puedeleerse como “lo apuntado por pun” o “lo que hay en la dirección contenida en pun”

La memoria está dividida en bloques numerados, imaginemos que en la posición de memoria 50 tenemos la variable “a” cuyo valor es 10, a continuación, si declaramos el puntero “p” que contiene la dirección de la variable “a” vemos como el puntero “p” apunta a la dirección que tiene el valor 10



47 48 49 50 5152

a 10&

24810122550
Como vemos no tendría sentido asignar directamente la dirección al puntero “p” ya que no sabemos dónde está almacenado el valor de “a”. por lo tanto utilizamos el operador de dirección & para poder obtener el valor de la variable “a”.
Además un puntero puede contener la dirección de memoria de un dato, sin la necesidad de tener declarado una variableintermedia. Para ello se hace necesario la reserva de memoria. No podemos elegir las posicione que queremos arbitrariamente ya que podrían estar ocupadas por otros datos.
Listas circulares:
En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada...