Unidad 7 vid

Question 1

¿Qué es una lista en el contexto de los Tipos Abstractos de Datos (TDA)?


Answer 1

Una lista es una colección de elementos homogéneos con una relación lineal. Cada elemento, excepto el primero, tiene un único predecesor, y cada elemento, excepto el último, tiene un sucesor. Los elementos son registros que contienen datos y un enlace al siguiente elemento, también conocidos como nodos.

Question 2

¿Cuáles son las características del TDA Lista?

Answer 2

Se crean a partir de punteros.
Son estructuras donde se almacenan datos sin conocer su cantidad de antemano.
Son estructuras dinámicas: se reserva y libera memoria según sea necesario.
Siempre se debe guardar el puntero inicial de la lista para recorrerla.

Question 3

¿Cuáles son los tipos de listas mencionados?

Answer 3

Listas Enlazadas
Listas Lineales (con nodo de cabecera)
Listas Dobles (doblemente ligadas)
Listas Circulares

Question 4

¿Cuál es la sintaxis para crear una lista en Pascal y cuáles son los dos pasos involucrados?


Answer 4

a) Creación del primer nodo:

new(lista);
lista^.info := 1;
lista^.siguiente := nil;

b) Creación de una lista con N nodos:

new(lista);
lista^.info := 1;
aux := lista;
for i := 1 to N do
begin
new(aux^.sig);
aux := aux^.sig;
aux^.info := i;
end;
aux^.sig := nil;

Question 5

¿Cuál es la declaración genérica del TDA Lista en Pascal?

Answer 5

Program ejemplo;
Type
nombreTipo = ^nodoTipo;
nodoTipo = record
elemento: tipoElemento;
punteroSig: nombreTipo;
end;
Var
L: nombreTipo;

Question 6

¿Cuáles son las operaciones básicas de las listas?

Answer 6

Insertar: Introducción de un nuevo elemento en la lista, pudiendo realizarse en cualquier lugar en una lista no ordenada.

Borrar: Eliminación de un elemento específico de la lista. La eliminación no requiere trabajo adicional más allá de reestructurar los punteros.

Question 7

¿Puedes proporcionar un ejemplo de operaciones básicas de lista en Pascal?


Answer 7

Sí, aquí hay un ejemplo:
Procedure Insertar (Var L : nombreTipo);
Var
nuevoNodo : nombreTipo;
Begin
new(nuevoNodo);
nuevoNodo^.elemento := nuevoElemento;
nuevoNodo^.punteroSig := L;
L := nuevoNodo;
End;

Procedure Borrar (Var L : nombreTipo; elementoABorrar : tipoElemento);
Var
actual, anterior : nombreTipo;
Begin
actual := L;
anterior := nil;
While (actual <> nil) and (actual^.elemento <> elementoABorrar) do
begin
anterior := actual;
actual := actual^.punteroSig;
end;
If actual <> nil then
begin
If anterior = nil then
L := actual^.punteroSig
Else
anterior^.punteroSig := actual^.punteroSig;
dispose(actual);
end;
End;