Data">
Estructura de Datos
Estructura de Datos
Estructura de Datos
ESTRUCTURA
TEMARIO:
REPASO DE PASCAL.
LIBROS:
- Programación avanzada y resolución de problemas en Pascal estructura de datos,
metodología de la programación e ingeniería del Software (Autores G. M. Steven C.
Bruell) Editorial Anaya.
- Gusta a ella es: Pascal y estructura de datos. Date/Lilly Mc Graw Hill.
- Otro clásico es: Estructura de datos. Seymoul Lipschntz Mc Craw Hill. Es todo en
Pseudocódigo.
Apuntes realizados por Ignacio Domínguez (Nacho) y Jose Luis Blanco (Chevere)
ESTRUCTURA Pag: 2
Integer String
SIMPLES Char ESTRUCTURADOS Array
Boolean El resto....
Real
3. ENTRADA. SALIDA.
READ( ); WRITE( );
READLN( ); WRITELN( );
SIMPLE DOBLE
IF Múltiple CASE:
CASE Variable OF
Valor1:----
----
Valor2:----
----
End;
FOR:
WHILE: REPEAT:
Program ejer1;
Uses CRT;
Var i,num,may,men: integer;
BEGIN
ESTRUCTURA Pag: 4
may := 0; men := 0;
for i := 1 to 20 do
begin
repeat
readln(num);
until (num >= 1) and ( num < 50);
if num >= 25 then may := may+1;
else men := men+1;
end;
writeln(“Hay”, may, “nº mayores o igual a 25 años”);
writeln(“Hay”, men, “nº menores a 25 años”);
END.
ax 2 +bx+c=0 2 --cuadrado
PROGRAM RAIZ;
VAR
X,A,B,C,X1,X2:INTEGER;
BEGIN
WRITE('TECLEE TÉRMINO CUADRÁTICO');
READLN(A);
WRITE('TECLEE TÉRMINO REAL');
READLN(B);
WRITE('TECLEE TÉRMINO INDEPENDIENTE');
READLN(C);
IF A=0 THEN
BEGIN
X := -C/B;
WRITE('EL RESULTADO ES: ',X);
END;
EJER 3: Hacer una función que devuelva la suma de los elementos de un vector de
n posiciones. Esta cargado con números enteros:
FUNCTION SUMA:integer;
Var i,aux:integer;
BEGIN
aux := 0;
for i := 1 to n do
aux := aux+vector[i[;
suma:=aux;
END;
EJER 4: Hacer una función de tipo boolean que devuelve verdadero si el número
n es > 10 y falso en el caso contrario.
FUNCTION POTENCIA:integer;
VAR aux:integer;
BEGIN
aux:=1;
for i:=1 to exp do
aux:=aux*base;
potencia:=aux;
END;
EJER 6: Programa que acepte un número entero y mediante una función de tipo
boolean visualice en pantalla si el número es > ó <=10
PROGRAM EJERCICIO;
VAR
a,b,c:Integer;
PROCEDURE Parametros (Var x,y:Integer;Z:Integer);
VAR h:Integer
BEGIN
h:=x+2; y:=y+h;
z:=2*y; x:=z;
END;
ESTRUCTURA Pag: 7
BEGIN
a:=1; b:=2; c:=3;
Parametros (a,b,c);
WRITE (A); WRITE (B); WRITE (C);
END.
PROCEDURE SUPERIOR(X:VECTOR);
VAR
PROM:REAL;
BEGIN
PROM:=PROMEDIO(X);
FOR I:=1 TO 20 DO
IF X[I[ > PROM THEN WRITELN(I);
END;
BEGIN
WRITELN('EL PROMEDIO DE COCHES ES: ' PROMEDIO(COCHES));
WRITELN('EL PROMEDIO DE MOTOS ES: ' PROMEDIO(MOTOS));
....
....
END.
IMPLEMENTACION:
TYPE
VECTOR: = Array [lim.inf. ... lim.sup.[ OF tipo;
VAR
v1,v2,v3: VECTOR;
- BUSQUEDA DICOTOMICA:
1.- Calcular el elemento mitad.
2.- Comparar el elemento a buscar con el elemento mitad.
3.- Hacer el vector mas pequeño.
TYPE
VECTOR: = Array [lim.inf. ... lim.sup.[ OF tipo;
VAR
v1,v2: VECTOR;
IMPLEMENTACION:
TYPE datos=RECORD
nombre:string;
provincia:string;
ventas:ARRAY[1..12[ of real;
END;
VAR tiendas:ARRAY[1..50[ of datos;
FOR I:=1 TO 50 DO
BEGIN
IF TIENDAS[I[ .PROVINCIA=‘CUENCA’ THEN
BEGIN
ACUM:=0;
FOR J:=1 TO 12 DO
SUM:=SUM+TIENDAS[I[ .VENTAS[J[ ;
IF SUM/12 < 100000 THEN
WRITELN(TIENDAS[I[ .NOMBRE);
END;
END;
ESTRUCTURA Pag: 10
PROCEDURE VISUALIZAR:
VAR X,Y: INTEGER; PROM: REAL;
BEGIN
FOR X:=1 TO 35 DO
BEGIN
PROM:=0;
FOR Y:=1 TO 8 DO
PROM:=PROM+CLASE2TA[X].NOTAS[Y];
PROM:=PROM/8;
IF PROM >7 THEN WRITELN (CLASE2TA[X].NOMBRE):
END;
END;
FUNCTION NUMERO:INTEGER;
VAR I, CON: INTEGER;
BEGIN
CONT:=0;
FOR I:=1 TO 35 DO
BEGIN
IF CLASE2TA[I[.F_NAC.MED=2 THEN CONT:=CONT+1;
NUMERO:=CONT;
END;
END;
EJER 10: Con la misma declaración de tipos que el ejercicio anterior y con la variable
CLASES hacer un algoritmo que visualice el nombre de los alumnos del curso 2TA
cuyo año de nacimiento sea 1970 y cuya nota en la asignatura 3 sea inferior a 5.
9.- FICHEROS:
IMPLEMENTACION:
OPERACIONES:
PROCEDURE CARGAR;
VAR
REG:ALUMNO;
BEGIN
ASSIGN(F,’A:\PASCAL\ALUMNOS.DAT);
{$I-}
RESET(F);
{$I+}
REWRITE(F);
SEGUIR:=‘S’;
REPEAT
WRITELN(‘Teclee nombre: ‘);READLN(Reg.nombre);
WRITELN(‘Teclee dia de nacimiento: ‘);READLN(Reg.fecha_nac.dia);
WRITELN(‘Teclee mes: ‘);READLN(Reg.fecha_nac.mes);
WRITELN(‘Teclee año: ‘);READLN(Reg.fecha_nac.año);
WRITELN(‘Teclee el curso: ‘);READLN(Reg.curso);
FOR I:=1 TO 6 DO
BEGIN
WRITE(‘Teclee la nota: ‘);
READ(Reg.notas[I[ ;
END;
WRITELN(‘¿DESEA SEGUIR?’);
SEGUIR:=READKEY;
UNTIL SEGUIR:=‘N’;
CLOSE(F);
END;
ESTRUCTURA Pag: 13
TEMA II - PUNTEROS
IMPLEMENTACION
TYPE
Puntero=^Integer;
VAR
P,Q:PUNTERO;
BEGIN
NEW (P);
NEW: Este procedimiento asigna al puntero P,a traves del parámetro una dirección
de memoria libre. En esta dirección es donde se almacena la variable dinámica.
Ejemplo:
TYPE Puntero=^Integer;
VAR P,Q: puntero;
BEGIN
NEW (P);
NEW (Q);
Q^:=7; Dirección de memoria de q guarda un 7.
P^:=5; Dirección de memoria de p guarda un 5.
P:=Q; Asignación de P, lo que tenga Q.
WRITE (P^); Visualizo un 7.
WRITE (Q^); Visualizo un 7.
END;
¿Que es un NODO?:
Es un elemento formado por 2 partes, la parte de la Izquierda es el INFO, es
donde guarda el dato y el de la Derecha, es el SIG, me da la dirección de memoria
del siguiente NODO.
Lista
TYPE
Puntero=^nodo;
Nodo=RECORD
INFO:...;
SIG:Puntero;
END;
VAR
Lista,Aux:Puntero;
BEGIN
NEW (Lista);
READ (Lista^.Info);
Aux:=Lista;
FOR I:=1 TO N DO
BEGIN
NEW (Aux^.Sig);
Aux:=Aux^.Sig;
READ (Aux^.Info);
END;
Aux^.Sig:=NIL;
END.
Aux:=Lista;
WHILE Aux <> NIL DO
BEGIN
WRITE (Aux^.Info);
Aux:=Aux^.Sig;
END;
NEW (Aux);
Aux^.Info:=Elem;
Aux^.Sig:=NIL;
P:=Lista;
WHILE P^.Sig <> NIL DO
BEGIN
P:=P^.Sig;
END;
P^.Sig:=Aux;
EJER 12: Insertar el elemento Elem despues del NODO que apunta P.
NEW (Aux);
Aux^.Info:=Elem;
Aux^.Sig:=P^.Sig;
P^.Sig:=Aux;
Aux:=Lista;
WHILE Aux^.Sig <> NIL DO
BEGIN
Aux:=Aux^.Sig;
END;
NEW (Aux^.Sig);
Aux:=Aux^.Sig;
Aux^.Info:=Elem;
Aux^.Sig:=NIL;
ESTRUCTURA Pag: 17
DISPOSE: Libera memoria, al reves del NEW. La dirección que tiene el puntero
que se le pasa como parámetro pasa a ser una dirección libre.
IF Lista^.Info=Elem THEN
BEGIN
Aux:=Lista;
Lista:=Lista^.Sig;.
DISPOSE ( Aux );
END
ELSE
BEGIN
Ant:=Lista;
Aux:=Lista^.Sig;
Enc:=FALSE;
END;
WHILE ( NOT Enc ) AND ( Aux< >NIL ) DO
BEGIN
IF Aux^.Info=Elem THEN
Enc:=TRUE
ELSE
BEGIN
Ant:=Aux;
Aux:=Aux^.Sig;
END;
END;
IF Enc THEN
BEGIN
Ant^.Sig:=Aux^.Sig;
DISPOSE (Aux);
END;
WHILE ( Lista^.Info=Elem) DO
BEGIN
Aux:=Lista;
Lista:=Lista^.Sig;.
DISPOSE ( Aux );
END;
Aux:=Lista^.Sig;
Ant:=Lista;
WHILE ( Aux< >NIL ) DO
BEGIN
IF Aux^.Info=Elem THEN
ESTRUCTURA Pag: 18
BEGIN
Ant^.Sig:=Aux^.Sig;
DISPOSE (Aux);
Aux:=Ant^.Sig;
END
ELSE
BEGIN
Ant:=Aux;
Aux:=Aux^.Sig;
END;
END;
Medicos
Pacientes
Especialidades
b) TYPE
DIRECCION = ^ PACIENTE ;
PACIENTE = RECORD
NOM_ PAC : STRING ;
PROX : DIRECCION ;
END ;
PUNTERO = ^MEDICO ;
MEDICO = RECORD
NOM_MED : STRING ;
SIG : PUNTERO ;
PROX : DIRECCION ;
END ;
ESPECIALIDAD = RECORD
NOMBRE : STRING ;
ESTRUCTURA Pag: 19
SIG : PUNTERO ;
END ;
VAR
HOSPITAL : ARRAY [ 1.. 20 ] OF ESPECIALIDAD ;
AUX_MED : PUNTERO ;
AUX_PAC : DIRECCION ;
c) Ι := 1;
WHILE ( HOSPITAL [ Ι ] . NOMBRE <> ‘ALERGIA’ ) DO
Ι := Ι +1 ;
AUX_MED := HOSPITAL [ Ι ] . SIG ;
WHILE ( AUX_MED <> NIL ) DO
BEGIN
Ι := 0 ;
AUX _PAC := AUX_MED ^. PROX ;
WHILE ( AUX_PAC <>NIL ) DO
BEGIN
C := C +1 ;
AUX_PAC := AUX_PAC ^. PROX ;
END ;
IF ( C > 10 ) THEN WRITELN ( AUX_MED ^. NOM_MED ) ;
AUX_MED := AUX_MED ^. SIG ;
END ;
EJER 14: Dada esta declaración de tipos y suponiendo que está cargada la estructuta
hacer un algoritmo que acepte por teclado una palabra y la busque en la estructura,
en caso de no encontrarla la inserta.
TYPE
PUNTERO = ^PALABRA;
PALABRA = RECORD
INFO : STRING;
SIG : PUNTERO;
END;
VAR
DICCIONARIO = ARRAY[‘A’..’Z’] OF PUNTERO;
PAL : STRING;
AUX : PUNTERO;
ENC : BOOLEAN;
BEGIN
READLN(PAL);
AUX := DICCIONARIO[PAL[1]];
ENC := FALSO;
WHILE (AUX<>NIL) AND (ENC=FALSO) DO
BEGIN
IF AUX^.INFO = PAL THEN
ESTRUCTURA Pag: 20
ENC := VERDAD
ELSE
AUX := AUX^.SIG;
END;
IF (ENC = FALSO) THEN
BEGIN
NEW(AUX);
AUX^.INFO := PAL;
AUX^.SIG := DICCIONARIO[PAL[1]];
DICCIONARIO[PAL[1]] := AUX;
END;
END;
’A’
’B’
’Z’
TYPE
DIRECCION = ^CURSO;
CURSO = RECORD
NOMBRE : STRING;
NUMERO : INTEGER;
PROX : DIRECCION;
END;
PUNTERO = ^FACULTAD;
FACULTAD = RECORD
NOMBRE : STRIG;
PROX : DIRECCION;
SIG : PUNTERO;
END;
UNIVER = RECORD
NOMBRE : STRING;
SIG : PUNTERO;
END;
VECTOR = ARRAY[1..15] OF UNIVER;
VAR
UNIVERSIDAD : VECTOR;
AUX_FAC : PUNTERO;
ESTRUCTURA Pag: 22
AUX_CUR : DIRECCION;
BEGIN
I:=1;
WHILE (UNIVERSIDAD[I].NOMBRE <> ‘UCM’) DO
I:=I+1;
AUX_FAC := UNIVERSIDAD[I].SIG;
WHILE (AUX_FAC <> NIL) DO
BEGIN
AUX_CUR := AUX_FAC^.PROX;
WHILE (AUX_CUR<>NIL) AND (AUX_CUR^.NOMBRE<>‘PRIMERO’)
DO
AUX_CUR := AUX_CUR^.PROX;
IF AUX_CUR^.NUMERO >1000 THEN
WRITELN(AUX_FAC^.NOMBRE);
AUX_FAC := AUX_FAC^.SIG;
END;
END;
EJER 17: Hacer una función que reciba como parámetro el puntero a comienzo de una
lista enlazada simple cuyos elementos son enteros y devuelva el número de nodos
con contenido impar.
WRITE(IMPAR(LISTA));
ant info sig ant info sig ant info sig ant info sig
Comienzo Fin
IMPLEMENTACION:
TYPE
puntero=^nodo;
nodo=RECORD
info: ...;
ant,sig: puntero;
END;
VAR
comienzo, fin: puntero;
NEW (comienzo);
READ (comienzo^.info);
comienzo^.ant:=NIL;
fin:=comienzo;
FOR I:=1 TO N DO
BEGIN
NEW(fin^.sig);
fin^. sig^.ant:=fin;
fin:=fin^.sig
READ (fin^.info);
END;
fin^.sig:=NIL;
NEW (aux);
aux^.info:=elem;
aux^.sig:=p^.sig;
aux^.ant:=p;
p^.sig:=aux;
aux^. sig^.ant:=aux;
EJER 18: Hacer un algoritmo que intercambie los nodos que ocupan las posiciones
k y k+1, modificando unicamente los campos sig.
b) Dinámica
FUNTION PILA_VACIA ( VAR PILA1: TIPOPILA ) : BOOLEAN ;
BEGIN
PILA_VACIA := PILA1 = NIL ;
END;
a) Estática
PROCEDURE INSERTAR ( VAR PILA1: TIPOPILA ; ELEM : ....) ;
BEGIN
IF PILA_LLENA ( PILA1 ) = FALSE THEN
BEGIN
PILA1. CAB := PILA1. CAB+1 ;
PILA1 . DATOS [ PILA1. CAB] := ELEM ;
END;
END;
b) Dinámica
PROCEDURE INSERTAR ( VAR PILA1: TIPOPILA ; ELEM : ....) ;
VAR AUX : TIPOPILA ;
BEGIN
NEW ( AUX ) ;
AUX ^. INFO := ELEM ;
AUX ^. SIG := PILA1 ;
PILA1:= AUX ;
END;
ESTRUCTURA Pag: 28
EJER 19: Hacer un algoritmo que visualize el contenido de una lista enlazada
simple en orden inverso . El puntero a comienzo es ‘ lista’ . Es decir, dada una
lista enlazada simple visualizarla al reves.
LIMPIA_PILA ( PILA1 ) ;
AUX := LISTA ;
WHILE ( AUX <>NIL ) DO
BEGIN
INSERTAR ( PILA1 , AUX ^. INFO ) ;
AUX := AUX ^. SIG ;
END ;
WHILE NOT PILA_VACIA ( PILA1 ) DO
BEGIN
SACAR ( PILA1 , ELEM ) ;
WRITELN ( ELEM ) ;
END ;
ESTRUCTURA Pag: 29
EJER 20: Se dispone de una pila de números enteros y de 2 variables enteras que se
llaman VIEJA y NUEVA. Hacer un algoritmo que reemplace de la pila el
elemento que contiene VIEJA por el valor de NUEVA, dejando el resto de la pila
como estaba.
limpiarpila(pilaaux);
enc := falso;
mientras (no pilavacia(pila)) y (no enc)
sacar(pila,h)
si h = vieja
enc := verdad
meter(pila,nueva)
sino
meter(pilaaux,h)
fin
fin
mientras no pilavacia(pilaaux)
sacar(pilaaux,h)
meter(pila,h)
fin
TEMA V- COLAS
1.- DEFINICIÓN.
Estructura lineal de elementos homogeneos, los cuales entran (por final) y salen
(por frente) por extremos opuestos, es decir el 1º que entra es el 1º que sale.
Listas FIFO.
FRENTE FINAL
2.- IMPLEMENTACIÓN.
Declaración de tipos y variables.
2.1.- ESTÁTICA.
Se representa con un vector y dos números. El nº frente me da la
posición del primero en salir y el nº final el último en entrar.
Vamos a hacer un vector circular.
COLALLENA COLAVACIA
IMPLEMENTACIÓN ERRONEA
COLALLENA COLAVACIA
CONST max= ?
TYPE tipocola = RECORD
datos : ARRAY [1..max[ OF ... ;
frente,final : 1..max ;
END;
VAR cola : tipocola;
2.2.- DINÁMICA.
Frente Final
3. OPERACIONES.
ESTÁTICA (Secuencial):
PROCEDURE INICOLA (VAR cola : tipocola);
BEGIN
cola.frente := max;
ESTRUCTURA Pag: 32
cola.final := max;
END;
DINÁMICA:
PROCEDURE INICOLA (VAR cola : tipocola);
BEGIN
cola.frente := NIL;
cola.final := NIL;
END;
SECUENCIAL:
FUNCTION COLAVACIA (cola : tipocola): BOOLEAN;
BEGIN
colavacia := cola.frente :=cola.final;
END;
SECUENCIAL:
FUNCTION COLALLENA (cola : tipocola): BOOLEAN;
VAR siguiente : 1..max;
BEGIN
IF cola.final=max THEN siguiente :=1
ELSE siguiente :=cola.final+1;
END;
DINÁMICA:
La representación de colallena en una lista enlazada no existe ya que
una lista nunca se llena.
SECUENCIAL:
DINÁMICA:
ESTRUCTURA Pag: 33
DINÁMICA:
PROCEDURE EXTRAER (VAR cola : tipocola;VAR elem: ... );
BEGIN
IF NOT colavacia(cola) THEN
BEGIN
IF cola.frente=cola.final THEN
BEGIN
aux:=cola.frente;
cola.frente:=NIL;
cola.final:=NIL;
elem:=cola.frente^.dato;
DISPOSE(aux);
END
ELSE
BEGIN
elem:=cola.frente^.dato;
ESTRUCTURA Pag: 34
aux:=cola.frente;
cola.frente:=aux^.sig;
DISPOSE(aux);
END;
END;
END;
EJER 22: Se tiene un array de 20 colas cuyo nº de elementos puede variar entre 0 y
1000 elementos.
Cada cola tiene una prioridad distinta de 1 a 20, siendo la 1 la mas alta y la 20 la
mas baja. 1-Hacer la declaración. 2-Insertar un elemento en la cola de prioridad
n. 3-Extraer un elemento de la cola de mayor prioridad no vacia.
TYPE
PUNTERO = ^NODO;
NODO = RECORD
DATO : TIPODATO;
SIG : PUNTERO;
END;
TIPOCOLA = RECORD
FRENTE, FINAL : PUNTERO;
END;
VAR COLAS : ARRAY [1..20] OF TIPOCOLA;
PROCEDURE INSERTARELEM(ELEM:TIPODATO; N:INTEGER);
BEGIN inserta un elem en la posición N
INSERTAR(COLAS[N], ELEM);
END;
PROCEDURE DEVOLVERELEM(ELEM:TIPODATO; N:INTEGER);
VAR I:INTEGER; devuelve un elem de la posición
BEGIN con más prioridad no vacia
I:=1;
WHILE (I<=20) AND (COLAVACIA(COLAS[I])) DO I:=I+1;
IF I>20 THEN WRITE(‘TODAS VACIAS’);
END;
ESTRUCTURA Pag: 35
factorial(0)= 1
EJER 25:
FUNCTION DOLORCABEZA(LISTA:PUNTERO):INTEGER;
BEGIN
IF LISTA <>NIL THEN DOLORCABEZA :=1+DOLORCABEZA(LISTA^.SIG)
ELSE DOLORCABEZA :=DOLORCABEZA(LISTA)
END; no funciona por que no tiene salida
EJER 26: Hacer una función que cuente en forma recursiva el número de nodos de
una lista enlazada simple.
SALIDA LISTA VACIA
FUNCTION CONTAR (LISTA:PUNTERO):INTEGER;
BEGIN
IF LISTA=NIL THEN CONTAR:=0
ELSE CONTAR :=1+CONTAR(LISTA^.SIG);
END;
EJER 27: Procedimiento que visualice los contenidos de los nodos de una lista
enlazada simple en forma capicua.
PROCEDURE VISUAL (LISTA:PUNTERO);
BEGIN
IF LISTA <>NIL THEN
BEGIN
WRITE (LISTA^.INFO);
VISUAL (LISTA^.SIG);
WRITE (LISTA^.INFO);
END;
END;
ESTRUCTURA Pag: 37
EJER 28: Función recursiva que devuelva la suma de los elementos de un vector
sabiendo que el primer elemento está en la posición LI y el último en la posición LS.
FUNCTION SUMA (V:VECTOR ; LI ,LS : INTEGER) : INTEGER ;
BEGIN
IF LI = LS THEN SUMA := V[LI[ ;
ELSE SUMA := V[LI[ + SUMA (V, LI+1, LS);
END;
EJER 29: Función recursiva de tipo BOOLEAN que devuelva TRUE si el elemento
ELEM es miembro de la lista enlazada simple LISTA.
FUNCTION MIEMBRO (LISTA:PUNTERO ; ELEM: ... ):BOOLEAN;
BEGIN
IF LISTA = NIL THEN MIEMBRO := FALSE
ELSE MIEMBRO := MIEMBRO(LISTA^.SIG, ELEM);
END;
EJER 30: Procedimiento recursivo que reciba una lista enlazada simple coma
parámetro y devuelva una copia exacta de la lista.
PROCEDURE COPIAR (LISTA:PUNTERO; VAR COPIA:PUNTERO);
BEGIN
IF LISTA = NIL THEN COPIA := NIL
ELSE
BEGIN
NEW(COPIA);
COPIA^.INFO := LISTA^.INFO;
COPIAR (LISTA^.SIG; COPIA^.SIG);
END;
END;
EJER 33: Función recursiva que cuente el número de nodos de una lista enlazada
simple.
FUNCTION CONTAR (LISTA:PUNTERO):INTEGER;
BEGIN
IF LISTA = NIL THEN CONTAR := 0
ELSE CONTAR := 1+CONTAR(LISTA^.SIG);
END;
EJER 34: Hacer una función recursiva que devuelva el número de elementos pares
que hay en un vector cuyas dimensiones son LI...LS
FUNCTION PAR(LI,LS:INTEGER):INTEGER;
BEGIN
IF LI=LS THEN
IF V[LI] MOD 2=0 THEN PAR:=1
ELSE PAR:=0
ELSE
IF V[LI] MOD 2=0 THEN PAR:=1+PAR(LI+1,LS)
ELSE PAR:=PAR(LI+1,LS);
END;
EJER 35: Hacer un procedimiento recursivo que visualice el contenido de una lista
enlazada simple tal que asi: si la lista tiene a b c, visualizaría a b c c b a
PROCEDURE VISUAL(LISTA:PUNTERO);
BEGIN
IF LISTA<>NIL THEN
BEGIN
WRITE(LISTA^.INFO);
VISUAL(LISTA^.SIG);
WRITE(LISTA^.INFO);
END;
END;
ESTRUCTURA Pag: 39
TEMA VII-ÁRBOLES
TERMINOLOGÍA:
EJER 36: Hacer una función recursiva que cuente el nº de nodos que tiene el árbol.
EJER 37: Hacer una función que devuelva el nº de nodos terminales que hay en un
árbol.
15 2
5 9 19
17 3 23
25
EJER 38: Hacer un seguimiento del siguiente algoritmo con el árbol que se da.
PROCEDURE EJERCICIO(RAIZ:PUNTERO);
BEGIN
IF RAIZ<>NIL THEN
BEGIN
IF RAIZ^.INFO MOD 2=0 THEN WRITE(RAIZ^.INFO);
EJERCICIO(RAIZ^.IZQ);
EJERCICIO(RAIZ^.DER);
IF RAIZ^.INFO>0 THEN WRITE(RAIZ^.INFO);
END;
END;
2 9
3 8 10 15
11 16
4 5
12
6 13
7 14
Obtendriamos: 2, 4, 4, 6, 7, 6, 5, 3, 8, 8, 2, 10, 12, 14, 14, 13, 12, 11, 10, 16, 16, 15, 9,1
25
12 37
1 30 63
9 29 48
11 40
EJER 40: Hacer una función que cuente el número de nodos que tienen contenido
impar en un árbol binario. (¿cuantos números impares hay?)
FUNCTION IMPARES(RAIZ:ARBOL):INTEGER;
BEGIN
IF RAIZ=NIL THEN IMPARES:=0
ELSE
IF RAIZ^.INFO MOD 2<>0 THEN
IMPARES:=1+IMPARES(RAIZ^.IZQ)+IMARES(RAIZ^.DER)
ELSE
IMPARES:=IMPARES(RAIZ^.IZQ)+IMARES(RAIZ^.DER);
END;
EJER 41: Dado un árbol binario de busqueda , que contiene el nombre, el apellido
y la edad de un grupo de personas , ordenados por edades .
ESTRUCTURA Pag: 46
Se pide :
Hacer un algoritmo que visualice los datos de las personas de mayor a menor
edad .
TYPE
ARBOL = ^ NODO ;
NODO = RECORD
NOMBRE : STRING[20] ;
APELLIDO : STRING[30] ;
EDAD : BYTE ;
DER , IZQ : ARBOL ;
END ;
VAR
RAIZ : ARBOL ;
TYPE
ARBOL = ^ NODO ;
NODO = RECORD
INFO : INTEGER ;
ESTRUCTURA Pag: 47
Vertice
1 2
3
4 5
Arco
G : grafo
V(G) = {1,2,3,4,5,6} conjunto de vertices
A(G) = {(1,2),(1,4),(2,1),(2,3),(2,5),(3,2),(3,5),
(4,1),(4,5),(4,6),(5,2),(5,3),(5,4),(6,4)}
TERMINOLOGÍA
ESTRUCTURA Pag: 49
Grafo no dirigido : Cuando los arcos tienen los dos sentidos.
Grafo dirigido : Cuando los arcos tienen un único sentido.
Vertices adyacentes : Dos vertices son adyacentes cuando están conectados
mediante un arco . Se dice que el arco es incidente a dichos vertices.
Grado de un vertice : El nº de arcos que inciden en dicho vertice . Si el grafo es
dirigido se habla de grado de entrada y grado de salida de dicho vertice.
Camino de un vertice : Del Vi al Vj . Es la secuencia de vertices que hay desde
uno a otro.
Longuitud de un camino : Es el nº de arcos que forman el camino .
Grafo valorado : Es un grafo en el que cada arco tienen asociado un valor o peso.
1 2 3 4 5 6
1 T T T F F F
2 T F F F T T
3 T F F T T F
4 F F T F T F
5 F T T T F F
6 F T F F F F
* Conjuntovertices
a) Implementación Estática .
TYPE
TIPOVERTICE = 1.. N ;
TIPOARCO = RECORD
ORIGEN,DESTINO : TIPOVERTICES ;
END ;
CONJUNTOVERTICES = ARRAY [1.. N ] OF BOOLEAN ;
CONJUNTOARCOS = ARRAY [1.. N , 1 .. N ] OF BOOLEAN ;
TIPOGRAFO = RECORD
VERTICES : CONJUNTOVERTICES ;
ARCOS : CONJUNTOARCOS ;
END ;
ESTRUCTURA Pag: 50
VAR
GRAFO : TIPOGRAFO ;
VECTOR : ARRAY[1..N] OF STRING ;
1 2 3 4 5 6
T T T T T T
* Conjuntoarcos
b) Implementación Dinámica .
TYPE
TIPOVERTICE = ...... ;
TIPOARCO = RECORD
ORIGEN,DESTINO : TIPOVERTICES ;
END ;
PUNTEROARCO = ^ NODOARCO ;
NODOARCO = RECORD
INFO : TIPOVERTICE ;
ADYA : PUNTEROARCO ;
END ;
TIPOGRAFO = ^ NODOVERTICE ;
NODOVERTICE = RECORD
INFO : TIPOVERTICES ;
SIG : TIPOGRAFO ;
ADYA : PUNTEROARCOS ;
END ;
VAR
GRAFO : TIPOGRAFO ;
a ) Estática .
PROCEDURE GRAFO_VACIO ( VAR GRAFO : TIPOGRAFO ) ;
ESTRUCTURA Pag: 51
VAR
X , Y : INTEGER ;
BEGIN
FOR X := 1 TO N DO
BEGIN
GRAFO . VERTICES [ X ] := FALSE ;
FOR I:= 1 TO N DO
BEGIN
GRAFO . ARCOS [ X , Y ]:= FALSE ;
END ;
END ;
END ;
a ) Dinámica .
PROCEDURE GRAFO_VACIO ( VAR GRAFO : TIPOGRAFO ) ;
BEGIN
GRAFO ^ . SIG:= NIL ;
GRAFO ^ . ADYA := NIL ;
END ;
b ) Dinámica .
PROCEDURE BORRA_ARC (VAR GRAFO : TIPOGRAFO ; ARC :
TIPOARCO ) ;
VAR
POS1 , POS2 : TIPOGRAFO ;
AUX , ANT : PUNTEROARCO ;
ENC : BOOLEAN ;
BEGIN
BUSCAR ( GRAFO , ARC . ORGIGEN , POS1 ) ; --- Buscamos el origen
IF ( POS1 <> NIL ) THEN
BEGIN
BUSCAR ( GRAFO , ARC . DESTINO , POS2 ); --- Buscamos destino
IF ( POS2 <>NIL ) THEN
BEGIN
IF ( POS1^. ADYA^. INFO = ARC. DESTINO ) THEN
BEGIN
AUX := POS1 ^. ADYA ;
Elimimamos sí es el 1º -------------- POS1 ^. ADYA := AUX ^. ADYA ;
DISPOSE ( AUX ) ;
END ;
ELSE
BEGIN
ANT := POS1 ^. ADYA ;
AUX := ANT ^. ADYA ;
ENC := FALSE ;
WHILE ( AUX <> NIL ) AND ( NOT ENC ) DO
BEGIN
ESTRUCTURA Pag: 53
IF ( AUX ^. INFO = ARC . DESTINO ) THEN
BEGIN
ENC := TRUE ;
ANT ^. ADYA := AUX ^. ADYA ;
DISPOSE ( AUX ) ;
END;
ELSE
BEGIN
ANT := AUX ;
AUX := AUX ^. ADYA ;
END;
END;
END;
END;
END;
4.2.- EN ANCHURA .
ESTRUCTURA Pag: 54
El recorrido en anchura consta de los siguientes pasos :
- Se parte de un vertice V . Se ‘marca’ como vertice procesado o visitado y
se mete en una cola . A continuación se repetiran los siguientes pasos hasta
que la cola esté vacía :
1º .- Se saca un elemento de la cola y se procesa .
2º .- Se meten en la cola sus vertices adyacentes no visitados y se
marcan como visitados .
E F
C
G
A B D C E F
Visitados : A , B , D , C , E , F
a) TYPE
TIPOARCO = RECORD
ORIGEN,DESTINO : STRING ;
DISTANCIA : INTEGER ;
END ;
PUNTEROARCO = ^ NODOARCO ;
NODOARCO = RECORD
DISTANCIA : INTEGER ;
CIUDAD : STRING ;
ADYA : PUNTEROARCO ;
ESTRUCTURA Pag: 55
END ;
TIPOGRAFO = ^ NODOVERTICE ;
NODOVERTICE = RECORD
INFO : TIPOVERTICES ;
SIG : TIPOGRAFO ;
ADYA : PUNTEROARCOS ;
END ;
VAR
GRAFO : TIPOGRAFO ;
a) TYPE
TIPOVERTICE = 1.. N ;
TIPOARCO = RECORD
ORIGEN,DESTINO : TIPOVERTICES ;
DISTANCIA : INTEGER ;
END ;
CONJUNTOVERTICES = ARRAY [1.. N ] OF BOOLEAN ;
CONJUNTOARCOS = ARRAY [1.. N , 1 .. N ] OF BOOLEAN ;
CIUDADES = ARRAY [ 1 .. N ] OF STRING ;
TIPOGRAFO = RECORD
VERTICES : CONJUNTOVERTICES ;
ARCOS : CONJUNTOARCOS ;
END ;
VAR
GRAFO : TIPOGRAFO ;
Ι , J : INTEGER ;
ENC : BOOLEAN ;
b) I:=1 ;
ENC := FALSE ;
WHILE ( I < = N ) AND ( NOT ENC ) DO
BEGIN
IF ( CIUDADES [ Ι ] = ‘ Madrid ‘ ) THEN ENC := TRUE ;
ELSE I:=I+1 ;
MENOR := GRAFO . ARCOS [ Ι ,1] ;
POS := 1 ;
FOR Ι := 2 TO N DO
BEGIN
IF ( GRAFO . ARCOS [ Ι , J] < MENOR THEN
BEGIN
MENOR := GRAFO . ARCOS [ Ι , J] ;
POS := J ;
END;
END;
WRITELN ( CIUDADES ) ;
END;