Lista lineal secuencial
| ||||
Lista lineal secuencial. Es una lista con almacenamiento secuencial de memoria, lo que significa que está sobre un arreglo unidimensional.
Sumario
Listas lineales
Una lista lineal de datos es una agrupación de uno o más elementos a1, a2 , a3, …aN donde N > = 0 y cada ai para i = 1,2,3,4,…..N es del mismo tipo de datos, donde se cumplen:
- la longitud de la lista es la cantidad de elementos de la lista N
- si N =0 entonces se dice lista vacía
- si N > = 1 entonces a1 es el primer elemento y aN es el último elemento de la lista.
Propiedades
- ai precede a ai + 1
- ai sucede a ai - 1
- ai está en la posición i
Lista lineal
Una lista lineal (de longitud n) es una ED B= (K,R) donde K consiste de n nodos y R consiste exactamente de una relación r donde los nodos k pueden ser ordenados tal que r ={( k i - 1,ki) para 2 i N}
Listas lineales secuenciales
En varios textos podemos encontrar que una lista lineal secuencial o realizada en forma secuencial es aquella que es almacenada sobre un arreglo unidimensional, es decir, en localizaciones consecutivas de memoria y el orden de cada elemento queda establecido por el valor del subíndice en el arreglo.
Formalmente una lista lineal (de longitud n) es una ED B= (K,R) donde R consiste exactamente de una relación r se dice que está almacenada secuencialmente en memoria, si r está realizada en forma secuencial es decir para r = { ( k i - 1 , ki ) para 2 i N } se tiene que dir k i = dir k - 1 + h.
Véase que en la representación de la estructura:
- Se tiene en cuenta la cantidad máxima de elementos definidos en el arreglo que contendrá la estructura de datos.
- Se ha empleado una variable de tipo entero que llamaremos “Puntero o cursor” (no apuntador) que indicará un elemento importante en la estructura de datos. En el caso de la lista lineal, Ultimo, indicará la posición del último elemento de la lista de datos y a su vez la cantidad de nodos de la misma.
- Este puntero (variable de tipo entero) constituye un elemento esencial para la manipulación (operaciones) de las listas lineales en términos de programación.
- Para la definición de una lista lineal secuencial en lenguaje C la declaración de la estructura sería declarar un arreglo, si la lista está constituida por un solo tipo de datos o bien un arreglo de registro si tendrá más de un tipio de datos.
- Ejemplo
float número [50]
struct nodo {char *nombre; int edad;}
struct nodo X [20]
¿Qué se está declarando en ambos ejemplos?
Representación gráfica de una lista lineal secuencial sobre un arreglo unidimensional.
Operaciones con listas lineales secuenciales LLS)
- Inserción
- Eliminación
- Recorrido
- Búsqueda
- Ordenamiento
- Lista vacía
- Añadir
- Obtener
- Longitud
Procedimientos algorítmicos para las operaciones
Partiremos de una lista lineal secuencial almacenada sobre un arreglo llamado LISTA.
Inserción
Inserta un nodo ELEM en la posición K del arreglo LISTA que tiene una cantidad, ultimo, de elementos que componen la lista, el arreglo tiene MaxElem como posiciones del arreglo.
La idea es desplazar una posición hacia la derecha todos los elementos de la lista desde el último hasta el elemento que ocupa la posición donde será insertado el nuevo elemento, y así dejar una posición vacía para colocar el nuevo elemento.
Antes: posición inicial, el elemento será insertado en la posición 2 (k=2)
Intermedio: elementos desplazados
Final: el elemento 3 ha sido insertado en la posición 2, y la variable última señala la posición 6.
El procedimiento algorítmico, escrito como una función o procedimiento es el siguiente:
Inserción _ Lista_Secuencial (Lista, Elem, K, último)
i es un entero: subíndice para trabajar el arreglo
Si último=MaxElem entonces
Imprimir “Desbordamiento derecho”
sino
i= último
Repetir mientras i > = k
Lista [ i + 1 ] = Lista [ i ]
Fin de repetir
Lista [ k ] = Elem
Ultimo = último + 1
Fin si
Salir
Eliminación
Elimina un nodo ELEM en la posición K del arreglo LISTA que tiene una cantidad, ultimo, de elementos que componen la lista, el arreglo tiene MaxElem como posiciones del arreglo.
La idea es desplazar una posición hacia la izquierda, sobrescribiendo los elementos de la lista que se encuentran a la derecha, desde la posición del elemento a eliminar hasta el último elemento, disminuyendo la lista en un elemento.
Antes: posición inicial, el elemento será eliminado es el de la posición 1 (k=1) Final: en la posición 1 el elemento 4 ha sido eliminado y la variable último señala la posición 4, uno menos en la lista
El procedimiento algorítmico, escrito como una función o procedimiento es el siguiente:
Eliminación _ Lista_Secuencial (Lista, Elem, K, último) j es un entero: subíndice para trabajar el arreglo
Si último=0 entonces
Imprimir “Desbordamiento izquierdo”
sino
Elem = Lista [ k ]
Repetir desde j = k hasta último – 1
Lista [ j ] = Lista [ j + 1 ]
Fin repetir
último = último - 1
Fin si
Salir
