Conclusiones
Nodo: es un elemento formado por dos partes, la parte izquierda es la información y en donde se quedan los datos y la derecha es el la dirección de la memoria del próximo elemento del nodo siguiente.
Cuando hablamos de una “Cantidad de memoria variable, utilizamos construyendo un apuntador (puntero) cuyos valores corresponden a direcciones de memoria, en las que se incluye una dirección NULA llamada NIL.
Definición.
TYPE Tipo_P = ^Tipo_V ;
VAR p,q : Tipo_P
Son datos dinámicos que pueden crearse o eliminarse en el transcurso del programa, almacena la dirección fija en memoria, las variables dinámicas se definen y acceden a ellas a través de variables de tipo puntero.
Var
Pi:=^ integer;
Pr:=^ real;
a) una variable tiene asignación estática de memoria cuando su tamaño difiere en el momento de la compilación (un entero gasta 2 bytes). (vectores).
b)una variable tiene asignación dinámica de memoria cuando se defina en la compilación pero no ocupa memoria (no existe realmente como variable) y crea existencia en el momento de la ejecución (punteros).
Ej.
Var
X:=integer;
Pi:=^ integer;
Sea x:=6
Pi^:= x;
Writeln(pi^);
Writeln(x);
CREACION DE UN PUNTERO
Var
p,q:^ integer;
x:=integer;
begin
new(p);
new(q);
p^:=3;
q:= p;
writeln(p^,q^),
new(p);
P^:=5;
Writeln(p^, q^);
End,
Para liberar la memoria de un puntero solo debemos hacer un DISPOSE(puntero). Y quedara liberada.
LISTAS
Es una estructura de datos LINEAL con un número limitado de elementos homogéneos que se llaman nodos. Se puede acceder a estos a través de su dirección, se pueden insertar y suprimir en cualquier posición
Por convención el último nodo se marca con NIL (nulo)
La definición de la lista sería:
TYPE
PUNTERO:=^NODO;
NODO:= RECORD;
INFO:= INTEGER;
SIG := PUNTERO;
END;
Crear una lista
En toda creación de una lista existen dos pasos:
a)creación del primer nodo.
b)Creación del resto de nodos.
a)creación del primer nodo
new(lista);
lista^_nodo:= 1;
lista^.siguiente=nil; .
b)creación de una lista con N nodos.
begin
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;
end;
Recorrido de una lista
Aux:= lista;
While aux <> nil do
Write (aux^.info);
Aux:=(aux^.siguiente);
end.
Modo de Inserción por el principio de la lista.
For i=n to downto 1 do
Begin
New(aux);
Aux^.info:=I;
Aux^.siguiente:0lista;
Lista:=aux;
end
Busqueda de un elemento dentro de una lista
Procedure Busqueda(comienzo:puntero, Elemento:integer);
Var
Aux:=puntero;
Inc:
Begin
Aux:=comienzo;
Inc:=false;
While (not inc) and (aux <> nil) do
Begin
If aux^.info:=elemento then
Inc:=true;
Else
Aux:=aux^.siguiente;
End
If inc=false then
Write(‘ Elemento no encontrado ‘);
Else
Write(‘ elemento Encontrado’);
End
End
Borrar una lista
Procedure Borrar(var l:=lista, elem:=integer);
Var
Igual, anterior:=lista;
Begin
{ se debe buscar la posición del elemento a borrar }
Actual:=l,
Anterior:=l;
While (actual <> nil) and (actual^.clave <> elem) do
Begin
Anterior:= actual;
Actual:0actual^.siguiente;
End;
If (actual <> nil) and (actual^. Clave<> elem) then
Begin
If (anterior=actual) then
L:=actual^. Sig { borrar el primero }
Else
Anterior^. Sig:= actual^.sig;
Dispose(actual);
End;
End;
COLAS
Una cola es una estructura de datos caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir. El tipo cola representa la idea que tenemos de cola en la vida real. La cola para subir al autobús está compuesta de elementos (personas), que dispone de dos extremos comienzo y fin. Por el comienzo se extraerá un elemento cuando haya comprado el billete para su viaje, y si llega una nueva persona con intención de usar el autobús, tendrá que colocarse al final y esperar que todos los elementos situados antes que él abandonen la cola.
La definición de la COLA sería:
Crear una COLA
IF P=NIL
BEGIN
P:=CREAR_NODO();
P.INFO:=DATO;
P.DIR:=NIL;
END;
ELSE
BEGIN
Q:=P;
WHILE Q.DIR <> NIL DO
Q:=Q.DIR;
S:= CREARNODO()
S.INFO:=DATO;
Q.DIR:=S;
Q:=S:=NIL;
END;
IMPLEMENTACION
1.- FORMA ESTATICA: Se representa como un vector(arreglo) y dos números el número de frente me da la posición del primero en salir y el número final me da la posición de la última en encontrar. (FIFO).
CONST MAXIMO;
TYPE TIPOCOLA:=RECORD;
DATOS:ARRAY[1.. MAXIMO]OF …;
FRENTE, FINAL =1.. MAXIMO;
END
VAR
COLA, TIPOCOLA;
PROCEDURE INICOLA( VAR COLA: TIPOCOLA);
BEGIN
COLA.FRENTE=1
COLA.FINAL=1
END
Para verificar que una cola este vacía Habrá que ver si el frente es igual al final.
COLA VACIA
PROCEDURE COLA_VACIA( VAR COLA: TIPOCOLA);BOOLEAN
BEGIN
COLA.VACIA:=COLA.FRENTE:=COLA_FINAL;
END
COLA LLENA
FUNCTION COLA_LLENA(COLA:TIPOCOLA):BOOLEAN;
VAR
SIG:1.. MAXIMO
BEGIN
IF COLA.FINAL=MAXIMO THEN
COLA.LLENA:=TRUE
ELSE
SIG:=COLA.FINAL+1
ENDIF
2.- FORMA DINAMICA:
TYPE TIPOCOLA:=^NODO;
NODO:=RECORD
DATO: …
SIG:=PUNTERO,
END
TIPOCOLA=RECORD
FRENTE, FINAL:PUNTERO;
END;
VAR
COLA, TIPOCOLA;
PROCEDURE INICOLA( VAR COLA: TIPOCOLA);
BEGIN
COLA.FRENTE=nil
COLA.FINAL=nil
END
COLA VACIA
PROCEDURE COLA_VACIA( VAR COLA: TIPOCOLA);BOOLEAN
BEGIN
COLA.VACIA:=COLA.FRENTE:=COLA_FINAL;
END
COLA LLENA: NO EXISTE ESTA REPRESENTACION YA QUE UNA COLA NUNCA ESTA LLENA
INSERTAR UN ELEMENTO EN LA COLA
A) ESTATICA
PROCEDURE INSERTAR(VAR COLA:TIPOCOLA, ELEM:INTEGER);
VAR
SIGUIENTE:ARRAY[1.. Max] of integer;
BEGIN
COLA.FINAL:=SIGUIENTE(COLA_FINAL):
COLA.DATOS[COLA_FINAL]:=ELEM;
END
B) DINAMICA
PROCEDURE INSERTAR(VAR COLA:TIPOCOLA, ELEM:INTEGER);
BEGIN
IF COLA_VACIA(COLA) THEN
BEGIN
NEW(AUX);
AUX^.DATO:=ELEM;
COLA.FINAL^.SIG=AUX;
COLA.FINAL:=AUX;
END
ELSE
BEGIN
NEW(AUX);
AUX^.DATO=ELEM;
COLA.FINAL:=AUX;
END;
END;
STACK(PILAS)
Estructura de datos lineal de elementos homogéneos, en lo cual los elementos entran y salen por el mismo extremo, llamado, TOPE, CABEZA o cima de la pila. También se denominan “listas lifo”, (last in first out) último en entrar primero en salir. Al crearse la pila su índice se inicializa en -1
Su implementación se puede realizar desde dos puntos de vista
CREAR PILA O STACK
P:=NIL;
Q:=NILP;
WHILE CONDICION DO
BEGIN
XDATO:=LEERDATO()
Q:=CREARNODO()
Q.INFO:=XDATO;
IF P=NIL THEN
P:=Q;
ELSE
BEGIN
Q.DIR:=P
P:=Q
END;
Q:=NIL
1.- IMPLEMENTACION ESTATICA O SECUENCIAL
TYPE
TIPOPILA=RECORD
DATOS:=ARRAY[1.. MAX] OF TIPO;
CAB:=0… MAX
END;
VAR
PILA1,PILA2:TIPOPILA;
2.- IMPLEMENTACION DINAMICA
TIPOPILA:=^NODO
NODO=RECORD
INFO:=STRING;
SIG:=TIPOPILA
END;
1.- LIMPIAR UNA PILA EN FORMA ESTATICA
PROCEDURE LIMPIAR_PILA(VAR PILA1:TIPOPILA)
BEGIN
PILA1:=NIL
END
2.- LIMPIAR UNA PILA EN FORMA DINAMICA
PROCEDURE LIMPIAR_PILA(VAR PILA1:TIPOPILA)
BEGIN
PILA1:=NIL
END
3.- CONSULTAR SI UNA PILA ESTA VALIDA, EN FORMA ESTATICA
FUNCTION PILA_VACIA(VAR PILA1:TIPOPILA):BOLEAN;
BEGIN
PILA_VACIA:=PILA1 .CAB:=0
END
3.- CONSULTAR SI UNA PILA ESTA VALIDA, EN FORMA DINAMICA
FUNCTION PILA_VACIA(VAR PILA1:TIPOPILA):BOLEAN;
BEGIN
PILA_VACIA:=PILA :=NIL
END
4.- FUNCION PILA LLENA : ES UNA FUNCION BOOLEANA QUE RECIBE UNA PILA COMO PARAMETRO Y DEVUELVE TRUE SI ESTA LLENA Y FALSE SI NO ESTA.
ESTATICA:
FUNCTION PILA_LLENA(VAR PILA1:TIPOPILA):BOOLENA;
BEGIN
PILA_LLENA:=PILA1.CAB:=MAX;
END
5.- INSERTAR UN ELEMENTO EN UNA PILA
ESTATICA
PROCEDURE INSERTAR(VAR PILA1:TIPOPILA;ELEM:INTEGER)
BEGIN
IF PILA_LLENA(PILA1)=FALSE THEN
BEGIN
PILA1.CAB:=PILA1.CAB +1;
PILA1.DATOS[PILA1.CAB]:=ELEM;
END
END
DINAMICA
PROCEDURE INSERTAR(VAR PILA1:TIPOPILA;ELEM:INTEGER)
VAR
AUX:TIPOPILA;
BEGIN
NEW(AUX);
AUX^.INFO:=ELEM;
AUX^.SIG:=PILA1;
PILA1:= AUX
END
ESTATICA : SE RECORRE COMENZANDO DESDE EL MAXIMO , SI ESTA LLENA O DESDE EL ULTIMO INGRESADO
6.- EXTRAER UN ELEMENTO EN UNA PILA
ESTATICA:
PROCEDURE SACAR(VAR PILA1:TIPO PILA;ELEM:=STRIN);
BEGIN
IF NOT(PILA_VACIA(PILA1)) THEN
BEGIN
ELEM:=PILA1.DATOS[PILA1.CAB]
PILA1.CAB:=PILA1.CAB-1
END;
END;
DINAMICA:
PROCEDURE SACAR(VAR PILA1:TIPO PILA;ELEM:=STRIN);
VAR
AUX:=TIPOPILA;
BEGIN
IF NOT(PILA_VACIA(PILA1)) THEN
BEGIN
ELEM:=PILA1.INFO
AUX:=PILA1
END;
END;
EJERCICIOS COMPILADOS EN PASCAL
1.- {creación de una lista con N-nodos y método de inserción por el final}
program lista1(i,o);
uses
crt;
type
puntero=^nodo;
nodo=record
info:integer;
sig:puntero;
end;
var
lista, aux:puntero;
n,i :integer;
begin
clrscr;
gotoxy (2,2); write ('ingrese largo de la lista: ');
gotoxy (30,2); read(n);
new(lista); {crea el primer nodo}
lista^.info:=1;
lista^.sig:=NIL;
for i:=2 to n do {crea los nodos siguientes}
begin
new(aux); {crea el resto pero con el auxiliar }
aux^.info:=i; {traspaza la informacion }
aux^.sig:=lista;
lista:=aux;
end;
{iniciar el recorrido de la lista}
aux:=lista;
while aux <> nil do
begin
writeln(aux^.info);
aux:=aux^.sig;
end;
repeat until keypressed;
readln;
end.
2.- {creación de una lista con N-nodos por el principio de ella}{
buscar un elemento en la lista}
program lista1(i,o);
uses
crt;
type
puntero=^nodo;
nodo=record
info:integer;
sig:puntero;
end;
var
lista, aux:puntero;
n,i,ele :integer;
procedure busqueda(comienzo:puntero;elemento:integer);
var
aux:puntero;
inc:boolean;
begin
aux:=comienzo;
inc:=false;
while (not inc) and (aux <> nil ) do
begin
if aux^.info=elemento then
inc:=true
else
aux:=aux^.sig;
end;
if inc=false then
writeln('NO encontrado')
else
writeln('Encontrado');
end;
{programa principal}
begin
clrscr;
gotoxy (2,2); write ('ingrese largo de la lista: ');
gotoxy (30,2); read(n);
new(lista); {crea el primer nodo}
lista^.info:=1;
lista^.sig:=NIL;
for i:=n downto 2 do {crea los nodos siguientes}
begin
new(aux); {crea el resto pero con el auxiliar }
aux^.info:=i; {traspaza la informacion }
aux^.sig:=lista;
lista:=aux;
end;
gotoxy(5,10);writeln('Ingrese Elemento de Busqueda');
gotoxy(40,10);readln(ele);
busqueda(ele);
readln;
end.
3.- BUSCA ELEMENTO EN UNA LISTA
Program lista_nueva(i,o);
uses crt;
type
puntero=^nodo;
nodo=record
info:integer;
sig:puntero;
end;
Procedure busqueda(comienzo:puntero;elem:integer; var pos:puntero);
var
aux:puntero;
enc:boolean;
begin
aux:=comienzo;
enc:=false;
While (not enc) and (aux<>nil) do
begin
If aux^.info=elem then
enc:=true
else
aux:=aux^.sig;
end;
If enc then
write('encontrado');
end;
var
lista,aux,mipos:puntero;
i,nro:integer;
begin
new(lista);
lista^.info:=1;
aux:=lista;
For i:=2 to 10 do
begin
new(aux^.sig);
aux:=aux^.sig;
aux^.info:=i;
end;
aux^.sig:=nil;
write('Elemento a buscar');
readln(nro);
busqueda(lista,nro,mipos);
end.
4.- { program que busca un elemento y lo borra}
program listas4(i,o);
uses
crt;
type lista=^nodo;
nodo=record
clave:integer;
sig:lista;
end;
var
i,ene :integer;
lis,aux,lst :lista;
{*************************************************************************}
procedure borrar(var l:lista;elem:integer);
var
actual,anterior:lista;
begin
actual:=l;
anterior:=l;
while (actual <> nil) and (actual^.clave <> elem) do
begin
anterior:=actual;
actual:=actual^.sig;
end;
if (actual <> nil) and (actual^.clave=elem) then
begin
if (anterior=actual) then
l:=actual^.sig
else
anterior^.sig:=actual^.sig;
gotoxy(5,20);writeln('elemento borrado');
readln;
dispose(actual);
end;
end;
{***********************************************************************}
procedure muestra(var lst:lista);
begin
aux^.sig:=nil;
aux:=lst;
while aux<> nil do
begin
writeln (aux^.clave);
aux:=aux^.sig;
end;
end;
{******************** programa principal ******************************}
begin
clrscr;
new(lis);
lis^.clave:=1;
aux:=lis;
for i:=1 to 5 do
begin
new(aux^.sig);
aux:=aux^.sig;
aux^.clave:=I;
end;
aux^.sig:=nil;
{enviar al procedimiento borrar lista}
gotoxy(5,15);writeln('Ingrese Elemento a buscar');
gotoxy(30,15);readln(ene);
lst:=lis;
borrar(lst,ene);
MUESTRA(LIS);
READLN;
end.
5.-{crea colas dinámicas}
program colas_di(i,o);
uses
crt;
type puntero=^nodo;
nodo=record
dato:integer;
sig:puntero
end;
type
tipocola=record
frente,final:puntero
end;
var
cola,aux:tipocola;
i:integer;
{inicializar cola}
procedure inicola(var cola:tipocola);
begin
cola.frente:=nil;
cola.final:=nil
end;
{cola vacia}
function cola_vacia(cola:tipocola):boolean;
begin
cola_vacia:=cola.frente=cola.final
end;
{insertar un elemento}
procedure insertar(var cola:tipocola;elem:integer);
var
aux:puntero;
begin
if cola_vacia(cola) then
begin
new(aux);
aux^.dato:=elem;
cola.final^.sig:=aux;
cola.final:=aux;
end
else
begin
new(aux);
aux^.dato:=elem;
cola.final:=aux
end;
end;
{ *********** programa principal **************** }
begin
clrscr;
for i:=1 to 10 do
insertar(cola,i);
{impresion}
{ for i:=1 to 10 do
begin
write(aux^.dato);
aux^.final:=aux;
aux^.sig:=aux
end;}
readln;
end.
6.- {PROGRAMA CREAR COLAS en forma estática }
PROGRAM COLAS (I,O);
USES
CRT;
CONST MAX=5;
TYPE TIPOCOLA=RECORD
DATOS :ARRAY[1..5] OF INTEGER;
FRENTE,FINAL:1..MAX;
END;
VAR
COLA :TIPOCOLA;
ELEM1, I :INTEGER;
{inicializar cola}
PROCEDURE INICOLA(VAR COLA:TIPOCOLA);
BEGIN
COLA.FRENTE:=MAX;
COLA.FINAL:=MAX;
END;
{insertar elementos en una cola }
PROCEDURE INSERTAR(VAR COLA:TIPOCOLA;ELEM:INTEGER);
VAR
SIGUIENTE:ARRAY [1..MAX] OF INTEGER;
BEGIN
COLA.FINAL:=COLA.FINAL+1;
COLA.DATOS[COLA.FINAL]:=ELEM
END;
{cola vacia}
function cola_vacia(cola:tipocola):boolean;
begin
cola_vacia:=cola.frente=cola.final
end;
{cola llena}
function cola_llena(COLA:tipocola):boolean;
var
sig:1..max;
begin
if COLA.FINAL=max then
cola_llena:=true
else
sig:=cola.final+1
end;
{****************************** PROGRAMA PRINCIPAL ************************** }
BEGIN
CLRSCR;
GOTOXY(5,5);WRITELN('INGRESE ELEMENTO');
FOR I:=1 TO 5 DO
BEGIN
GOTOXY(30,5);READLN(ELEM1);
INSERTAR(COLA,ELEM1);
END;
READLN;
{impresion cola}
FOR I:=1 TO 5 DO
BEGIN
write(cola.datos[i]);
COLA.FINAL:=COLA.FINAL+1;
END;
readln;
END.
7.- {programa que trabaja con 1 pila}
Program Pilas;
uses
Crt;
Type TipoPila= ^Nodo;
Nodo = Record
nueva:integer;
vieja:integer;
Sig :TipoPila ;
end;
var
aux1,aux2,pila1 :TipoPila;
x,num1,num2,c :Integer;
PROCEDURE vacia_pila(var pila:TIPOPILA);
BEGIN
PILA:=NIL;
GOTOXY(15,15);WRITELN('PILA VIEJA VACIA ');
END;
Function Pila_Vacia(var Pila1:TipoPila):Boolean ;
begin
Pila_vacia:=pila1=Nil; {verifica si la pila esta vacia}
end;
Procedure Insertar(var pila1:TipoPila; elem1,elem2:integer);
var aux: TipoPila;
begin
if pila_vacia(pila1) then
begin
New(aux);
aux^.nueva:= elem1;
aux^.vieja:=elem2;
aux^.sig:= Pila1;
Pila1:= aux;
end
else
begin
New(aux);
aux^.nueva:= elem1;
aux^.vieja:=elem2;
aux^.sig:= Pila1;
Pila1:= aux;
end;
end;
{programa principal }
begin
clrscr;
gotoxy(5,5);writeln('Nueva');
gotoxy(5,6);writeln('Vieja');
new(pila1); { ingresa por primera vez }
gotoxy(25,5);readln(pila1^.nueva);
gotoxy(25,6);readln(pila1^.vieja);
pila1^.sig:=nil;
for x:= 1 to 4 do
begin
gotoxy(25,5);readln(num1);
gotoxy(25,6);readln(num2);
insertar(pila1,num1,num2);
end;
{imprimo pila con sus dos elementos}
aux1:=pila1;
c:=5;;
while aux1 <> nil do
begin
gotoxy(c,10);writeln(aux1^.nueva);
gotoxy(c,14);writeln(aux1^.vieja);
aux1:=aux1^.sig;
c:=c+3;
end;
readln;
aux1:=pila1;
while aux1 <> nil do
begin
aux1^.vieja:=aux1^.nueva;
aux1:=aux1^.sig;
c:=c+3;
end;
aux1:=pila1;
c:=5;;
while aux1 <> nil do
begin
gotoxy(c,16);writeln(aux1^.nueva);
gotoxy(c,18);writeln(aux1^.vieja);
aux1:=aux1^.sig;
c:=c+3;
end;
readln;
end.