Tutorial de Estructura de datos II
Elaborado por: LINDA MARIANA GONZALEZ VALDEZ Y MARLA YASMIN GONZALEZ JIMENEZ
Asesor: Fernando Campos Camacho. Universidad de Occidente [Campus Guamúchil]
UNIDAD I (STRINGS) UNIDAD II (ARBOLES) UNIDAD III(GRAFOS)
Temas: 1.-Conceptos y aplicaciones 2.-Manipulación de string 3.-Proyecto de strings
1.- CONCEPTO DE CADENA DE CARACTERES(STRINGS)
Una cadena de caracteres string es una serie de caracteres cuya longitud (numero de caracteres que contiene) puede variar de 1 a 255 caracteres. La aplicación string consiste en declarar la sección tipo var ó type. Declaración en var. var Mensaje:string[80]; Nombre:string[40]; Ciudad:string[30]; estado:string[70]; Declaración en type. type cadena 80=string[80]; cadena 40=string[40]; cadena 30=string[30]; cadena J=string[J]; var Mensaje=cadena 80 Nombre=cadena 40 Ciudad=cadena 30 Estado=cadena J Una vez que están declaradas las variables de cadenas se pueden realizar operaciones de lectura ó escritura en los programas. Mensaje:=`Hola forastero, yo que tu no lo haría´; Nombre:=`Mortionery Cazorla´; Ciudad:=`Cazorla´; Estado:=`España´;
2.- MANIPULACION DE STRINGS
Para poder realizar operaciónes con strings es necesario conocer la
estructura del mismo, cada string se representara en dos partes:
cadena y longitud.
La colección de caracteres en el propio string y un valor entero que
indica su longitud.
Cada string se almacenara en un arreglo de longitud maxima pero los
caracteres del string pueden a su vez constituir toda esa parte del
arreglo.(Desde la posición 1 hasta el final del arreglo donde
posiblemente ese string tenga una longitud menor que la que ya esta
declarada).
strings:array[1,...long-max] of char;
Longitud [ ]
Char [ ][ ][ ][ ][...][...]
[1][2][3][4]longitud[long.max]
REPRESENTACION DE STRING EN MEMORIA
Una variable puede tener de 0 a 255 caracteres de longitud, sin embargo,
la ocupación en memoria de una cadena es un numero de bytes igual al de
caracteres de la cadena mas uno, por ejemplo la cadena MORTIMER tiene una
longitud de 8 bytes pero ocupa 4 bytes.El primer byte contiene la long de
cadena si la variable nombre contiene `Motimer´ ocupara en memoria 9 bytes
(8 bytes, uno por cada letra, mas uno por la longitud).
Cadena de 0 1 2 3 4 5 6 7 8
Longitud [8][ ][ ][ ][ ][ ][ ][ ][ ]
LONGITUD.- Determina el numero de caracteres en una linea ó cadena.
OBTENER LINEA.-Introduce una linea de texto.
OBTENER CADENA.- Introduce una palabra de texto.
IMPRIMIR.- Escribe los contenidos de una cadena.
write(`Nombre´;Nombre);
SUBCADENA.-Devuelve una parte de la cadena.
CONCAT.-Devuelve una cadena creada poniendo dos cadenas juntas.
SUPRIMIR.-Suprime una subcadena de una cadena.
INSERTAR.-Inserrta una cadena en otra cadena.
BUSCAR.-Busca en una cadena una subcadena dada.
COMPARAR.-Compara dos cadenas para determinar la relación
(iguales,menor que ó mayor que).
AÑADIR.-Añade un caracter al final de una cadena
LONGITUD
Mensaje:string[80]; length(`Octavio´)
devuelve 7
CONCAT
VAR
cad1,cad2,cad3:string
Begin
cad1:=`Marla Yasmin´
cad2:=`González´
cad3:=concat(cad1,cad2)
resultado:marla yasmin gonzález
INSERTAR
s:=`Marla Gonzalez´
insert(´Yasmin´10,7).
NOTA: El uso de una cadena esta enfocada a las operaciones que
internamente realiza un compilador con estos ,asi como tambien
se describe la manera de como se presento las strings en memoria.
3.-PROYECTO DE STRINGS
Temas: 1.- OPERACION LONGITUD 2.- ALGORITMO PARA OBTENER LINEA 3.- OPERACION OBTENER CADENA 4.- OPERACION IMPRIMIR CADENA 5.- OPERACION SUBCADENA 6.- OPERACION CONCAT 7.- OPERACION SUPRIMIR 8.- OPERACION INSERTAR 9.- OPERACION BUSCAR 10.-OPERACION COMPARAR 11.-OPERACION AÑADIR
1.- OPERACION LONGITUD
1.- i=strsize
2.- encontro=false
3.- mientras i>0 encontro=false
4.- si s[i]<>0 entonces
enconrto=verdadero
ir al paso #5
de lo contrario:
i=i-1
ir al paso #3
5.- longitud=i
6.- fin
NOTA:
strsize.-tamaño o longitud del srting declarado.
s[i] .- indica la posición en el arreglo.
[8]
[H][O][L][A][ ][ ][ ][ ]
1 2 3 4 5 6 7 8
^ ^ ^ ^ ^
| | | | |
i=8,7,6,5,4
encontro=false,verdadero
longitud=4
Observese que al iniciar el algoritmo la variable i tiene como valor
el tamaño del string declarado. Posteriormente se procede al leer el string
de derecha a izquierda mientras sean blancos, almacenarlo de encontrar un
caracter diferente al blanco se termina de leer y el valor que cotenga i
es el de la longitud.
Se declaran 2 string con long de 10 cada uno, y se le introduce los
siguientes strings respectivamente:
sillas,xbbby
[10]
[ S][I][L][L][A][S][ ][ ][ ][ ]
1 2 3 4 5 6 7 8 9 10
^ ^ ^ ^
| | | |
i=10,9,8,7,6
encontro=false,verdadero
longitud=6
[10]
[ X][b][b][b][Y][ ][ ][ ][ ][ ]
1 2 3 4 5 6 7 8 9 10
^ ^ ^ ^ ^
| | | | |
i=10,9,8,7,6,5
encontro=false,verdadero
longitud=5
2.- ALGORITMO PARA OBTENER LINEA
1.- pos=0,lineaobt=` ´
2.- si es EOLN o pos >=maxlong entonces
ir al paso #3
de lo contrario
pos=pos+1
leer (datos,lineas,char[pos])
lineaobt=lineaobt+char[pos]
ir al paso #2
3.- si pos >= maxlong y no EOLN entonces
obtener lineaobt
ir al paso #1
4.- si pos
3.- OPERACION OBTENER CADENA
Está operación obtiene de un archivo de texto un string o cadena mediante
la función de leer los caracteres del archivo hasta encontrar un fin de cade
na, es decir encontrar un caracter que indique que es fin de cadena, estos
podrian ser los siguientes:
.,`´,´;:.
ALGORIMO PARA OBTENER CADENA
1.-Fin cadena=[.,;:`´´]
2.-pos=1
3.-string=`´
4.-si es EOLN ó pos>maxlong
entonces
ir al paso #5
de lo contrario
leer(datos,linea caracter[pos])
si caracter es fin de cadena
entonces ir al paso #5
de lo contrario
string=string+caracter[pos]
pos=pos+1
ir al paso #4
5.-si pos>maxlong
entonces
obtener string
ir al paso #2
6.-si pos<=maxlong entonces string="string" +`´ pos="pos+1" ir al paso #6 de lo contrario ir al paso #8 7.-si es EOLN entonces obtener string ir al paso #9 8.-obtener string 9.-fin. EJEMPLO Del siguiente texto obtener los string tomando en cuenta que la maxlongitud del string declarado es de 5: "Ejemplo de operaciones obtener cadena" pos="1,2,3,4,5,6" pos="1,2,3,4,5,6" string="Ejemp" string="l,o,`´,`´,`´" caracter[pos]="E,j,e,m,p" caracter[pos]="l,o,`´" Obtener del siguiente texto los string tomando en cuenta que la maxlong del string declarado es de 8. "Resumamos las operaciones de la fila,correspondiente a obtener cadena" pos="1,2,3,4,5,6,7,8,9" pos="1,2,3,4,5,6,7,8,9" string="Resumamo" string="la`´`´`´`´`´`´" caracter[pos]="R,e,s,u,m,a,m,o" caracter[pos]="l,a,`´,`´,`´,`´,`´,`´" pos="1,2,3,4,5,6,7,8,9" pos="1,2,3,4,5,6,7,8,9" string="s,`´,`´,`´,`´,`´,`´,`´" string="fila" caracter[pos]="s,`´,`´,`´,`´,`´,`´,`´" caracter[pos]="f,i,l,a,`´,`´,`´" pos="1,2,3,4,5,6,7,8,9" pos="1,2,3,4,5,6,7,8,9" string="las`´`´`´`´`´" string="correspo" caracter[pos]="l,a,s,`´,`´,`´,`´" caracter[pos]="c,o,r,r,e,s,p,o" pos="1,2,3,4,5,6,7,8,9" pos="1,2,3,4,5,6,7,8,9" string="operacio" string="ndiente`´" caracter[pos]="o,p,e,r,a,c,i,o" caracter[pos]="n,d,i,e,n,t,e,`´" pos="1,2,3,4,5,6,7,8,9" pos="1,2,3,4,5,6,7,8,9" string="nes`´`´`´`´`´" string="a`´`´`´`´`´`´`´" caracter[pos]="n,e,s,`´,`´,`´,`´,`´" caracter[pos]="a,`´,`´,`´,`´,`´,`´,`´,`´" pos="1,2,3,4,5,6,7,8,9" pos="1,2,3,4,5,6,7,8,9" string="de`´`´`´`´`´`´" string="obtener`´" caracter[pos]="d,e,`´,`´,`´,`´,`´,`´" caracter[pos]="o,b,t,e,n,e,r,`´" pos="1,2,3,4,5,6,7,8,9" string="cadena`´`´" caracter[pos]="c,a,d,e,n,a,`´,`´"
4.- OPERACION IMPRIMIR CADENA
1.- Pos=1
2.- si pos>longstring entonces
ir al paso #3
de lo contrario
imprime(string char[pos])
pos=pos+1
ir al paso #2
3.- fin.
EJEMPLO:
Primero tenemos que sacar la longitud.
Imprime caracter por caracter.
[5]
[L][A][P][I][Z]
pos=1,2,3,4,5,6
longstring=5
char[pos]=L,A,P,I,Z
imprime:LAPIZ
5.- OPERACION SUBCADENA
Esta operación realiz la función de obtener un string de un string ya dado. Por ejemplo, obtener el substring del siguiente substrig dado.
ALGORITMO PARA OBTENER SUBCADENA> 1.- error=poscomienzo+num-1 2.- substr=`´ 3.- cont=0 4.- si error <= longstring entonces 5.- si cont>= entonces ir al paso #6 de lo contrario ir al paso #5 car=string caracter[cont+poscomienzo] substr=substr+car cont=cont+1 ir al paso #5 de lo contrario ir al #4 error ir al paso #7 6.- obtener substr 7.- fin. DECLARACION DE VARIABLES: POSCOMIENZO=Posición a partir de la cual s tomara los caracteres. NUM=Numero de caracteres a tomar. LONGSTRING= Longitud del string. EJEMPLO: A partir de la posición 3 tomar 4 caraceres para formar un substring. POS CARACTER 3 4 string caracter [7] [C][A][D][E][N][A][S] 1 2 3 4 5 6 7 ^ ^ ^ ^ | | | | poscomienzo=3 num=4 longsring=7 error=6 substr=DENA cont=0,1,2,3,4 car=`D´,`E´,`N´,`A´
6.- OPERACION CONCAT
Esta operación añade un string al final de otro string. Por ejemplo:
Se tiene dos strings, se decean concatenar y almacenar.
[20]
string1 [L ][A][ ][F][L][O][R][ ][ ]
string2 [7]
[E][S][ ][R][O][J][A]
string1 [20]
[L ][A][ ][F][L][O][R][ ][E][S][ ][R][O][J][A][ ][ ][ ][ ]
Para realizar la operación concat, se deben tomar todos los caracteres
del segundo string en el primero, de uno en uno, comenzando en la primera
posición despues de los caracteres propios del string1.
ALGORITMO PARA CONCATENAR
1.- error=[string1.long+string2.long] 2.- si error
DEFINICION DE VARIABLES
STRING1.LONG= Longitud del string1
STRING2.LONG= Longitud del string2
MAXLONG1= Max.long declarada para el string1
POS= Contador que indica las posiciones del string2
POSULTIMA1= Posición ultima del string1
EJEMPLO:
Se decean concatenar los siguientes strings.
string1 [15]
[L ][A][S][ ][R][O][S][A][S][ ][R][O][J][A][S]
string2 [19]
[L ][A][S][ ][V][I][O][L][E][T][A][S][ ][A][Z][U][L][E][S]
maxlong1=40
error=34
pos=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19
posultima1=16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40
[40]
[L ][A][S][][R][O][S][A][S][][R][O][J][A][S][L][A][S][][V][I][O][L][E][T][A][S][][A][Z][U][L][E][S][][][][]
7.- OPERACION SUPRIMIR
La operación suprimir elimina un número especificado de caracteres del
primer string, comenzando en una posición de caracter, despues rellena el
hueco con los caracteres que queden y vayan a continuación de los
suprimidos.
Para esta operación es posible llevarla a cabo aprovechando dos
procedimientos ya vistos (subcadena y concatenar).
La operación con subcadena puede utilizarse para romper el sring original
en dos partes :
La parte anterior a los caracteres a suprimir y la parte que le sigue.
Estos dos strings puden despues ser concatenados para producir el srting
que se desea.
[27]
[ L][O][S][][P][A][J][A][R][O][S][][V][U][E][L][A][N][][Y][][C][A][N][T][A][N]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 18 1920 21 22 23 24 25 26 27
STR1[6] STR2[4]
[V][U][E][L][A][N] [L][O][S][]
[27]
[ L][O][S][][V][U][E][L][A][N][][][]
DEFINICION DE VARIABLES
Pos= Posición apartir de la cual se vn a suprimir los carateres.
NUm= Número de cracteres a suprimir.
Posúltima= Posición última a eliminar (postnum-1).
Posstring2= Posición inicio del string2.
Error= Posúltima > maxlong.
ALGORITMO
1.- posultima= pos + num -1
2.- substr= " "
3.- cont=0
4.- si posultima > maxlong entonces
ir al paso #11
5.- si cont >= num entonces
ir al paso #6
de lo contrario
car = string caracter[cont + pos]
substr = substr + car
cont= cont + 1
ir al paso #5
6.- Obtener string
7.- error= string1.long + string2.long
8.- si error
8.- OPERACION INSERTAR
La operación de insertar es la simetrica de suprimir. Insertar hasta que
se inserte un string en otro string en una posición especificada, es posible
utilizar el mismo metodo que en la operación suprimir utilizando la operación
subcadena y concat, para tomar y separar los strings y ponerlos
posteriormente unidos correctamente.
ALGORITMO
1.- pos=posinic Insertar
2.- num= longstring1 - pos
3.- error=pos + num - 1
4.- substr= `´
5.- cont = 0
6.- si pos > longstring1 entonces
error
ir al paso #16
de lo contrario
7.- si cont > num entonces
ir al paso #8
de lo contrario
car = string caracter[cont + pos]
substr = substr + car
cont = cont + 1
ir al paso #7
8.- obtener substring
9.- error = (longstr1 + longstr a insertar)
10.- si error subcadena
string2 der. |
[6] |
[A][Z][U][L][E][S] |
1 2 3 4 5 6 |
-
Concatenar (str original, string) a partir de la 11
[26]
[ R][O][S][A][S][][S][O][N][][R][O][J][A][S][][Y][][A][Z][U][L][E][S][][]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1516 1718 19 20 21 22 23 242526
pos=11
num=16-11=5
error=11+5-1=15
substr=`´
cont=0,1,2,3,4,5,6
car=A,Z,U,L,E,S
substr=AZULES
error=16+8=24
pos=1,2,3,4,5,6,7,8,9
posultima1=11,12,13,14,15,16,17,18
string1=ROJAS`´Y`´
error=18+6=24
pos=1,2,3,4,5,6,7,8,9
posultima1=19,20,21,22,23,24,25,26
string1=AZULES`´`´`´
9.- OPERACION BUSCAR
La operación de busqueda es un poco mas complejo de lo que se a considero
anteriormente.
Se trata de buscar la ocurrencia de un patron dentro de un string, un
patrón es exactamente otro string el cual puede o no coincidir con un sub-
string del string original. Si se encuentra una ocurrencia queremos saber
donde comienza e patrón en el string original.
El algoritmo funciona dee la siguiente forma:
Examinamos el string original para ver si hay una ocurrencia del primer
caracter del patrón.
Si encontramos una coincidencia con el primer caracter continuaremos
intentando hacer coincidir los sucesivos caracteres del patrón. Si coinciden
"todos" la busqueda terminara con exito sin embargo si encontramos un
caracter que no coincida volvemos atras y comenzamos buscando otra
coincidencia del primer caracter. El proceso concluye cuando la busqueda
termina en exito o cuando el número de caracteres que queda de buscar en el
string original es menor que la longitud de la subcadena patrón.
ALGORITMO BUSCAR
1.- postr= 0
2.- i=0
3.- encontro = falso
4.- si longstr > 0 ó longpatr
DEFINICION DE VARIABLES
Postr = posición dentro del string.
Longstr = longitud del string.
Longpatr = longitud del patrón.
Interm = posición dentro del string.
Str = string original.
Part = patrón.
a = posición dentro del patrón.
i = posición dentro del patrón.
EJEMPLO:
[4] [3]
[C][A][S][A] [A][S][I]
1 2 3 4 1 2 3
postr = 0,1,2
i = 0,1
encontro = falso
longstr = 4
longpatr = 3
a = 2,3
interm = 2+1=3,4
"BUSQUEDA SIN EXITO"
10.- OPERACION COMPARAR
Para realizar la operacion comparar es necesario examinar los dos
strings a comparar, caracter por caracter iniciando al comienzo de cada
string comparados los caracteres de las posiciones que coinciden tan pronto
como encontramos dos caracteres que no son iguales, su orden determina el
resultado de los dos strings. Detenemos en este caso la comparación así como
en el caso en donde no hay mas caracteres en el string mas corto. La
operación comparar nos enviara un resultado de la comparación de los dos
strings(><=), en cuanto a su orden alfabetico. [4] [3] string1 [F][L][O][R] string2 [O][S][O] STR1> STR2
ALGORITMO COMPARAR
1.- Pos = 1
2.- Si pos <= minlong entonces si str1[pos]="str2[pos]" entonces pos="pos" + 1 ir al paso #2 de lo contrario si str1[pos]> str2[pos] entonces
"string 1 es mayor que string 2"
ir al paso #3
si str1[pos] longstr2 entonces
"string 1 es mayor que string 2"
si longstr1
DEFINICION DE VARIABLES
Pos = Posición dentro del string
Str1 = string 1
Str2 = string 2
EJEMPLO:
string1 = [5] string2 = [6]
[S][I][L][L][A] [S][I][L][L][O][N]
pos = 1,2,3,4,5
minlong = 5
str1 = string 1 "String 1 es mayor que strig 2"
str2 = string 2
11.- OPERACION AÑADIR
Esta operación realmente sencilla. Su función es añadir un caracter al
final del string.
ALGORITMO
1.-Si longstr=maxlong entonces
"Error de longitud"
ir al paso #2
de lo contrario
leer char
longstr=longstr+1
str[longstr] =char
2.-Fin.
EJEMPLO:
[6]
Str [F][O][C][O][S][]
1 2 3 4 5 6
^
|
longstr maxlong char
4 6 S
5
Regresar al menu principal
Temas: 1.-Conceptos y aplicaciones 2.-Arboles binarios 3.-Proyecto de arboles
1.- CONCEPTOS Y APLICACIONES
Un arbol binario es un conjunto finito de elementos el cual puede estar
vacias o contener un elemento denominado raiz del arbol y otros elementos
divididos en dos subconjuntos separados cada uno de los cuales es en si un
arbol binario.
Estos dos subconjuntos son denominados subarbol izquierdo y subarbol
derecho del arbol original. Cada elemento en un arbol binario se denomina
nodo del arbol. La figura representa un arbol binario en el cual esta
compuesto con "I" nodos con "A" como raiz y el subarbol de hecho tiene como
raiz a "C".
Esto se indica con los dos brazos que salen de "A" una hacia B a la
izquierda y otra hacia C a la derecha. La ausencia de ramificación indica la
un subarbol vacio por ejemplo el subabol de la izquierda de un arbol binario
cuyas raices "C" y es arbol de hecho cuya raiz es E, estan ambos vacios, los
arboles binarios D,G,H,I, tienen vacios sus respectivos arboles izquierda y
derecha y se les llama nodos hojas.
Raiz
(padre o ancestro) Nivel
(A)--------------------(0)
subarbol / \
izquierdo(B) (C)---------------(1) Hijo descendiente (subarbol derecho)
/ \ \
(D) (E) (F)-----------(2)
^ / / \
| (G) (H) (I)-------(3)
| ^ ^ ^
| | | |
|___|_________|_______|______Nodos hojas
subarboles vacios
Nodos hojas (D,G,H,I)
Nodos hemanos {(B,C),(D,E),(H,I)}
2.- ARBOLES BINARIOS
NIVELES DE NODOS
El nivel de un nodo en un arbol binario se puede definir de la siguiente
manera:
La raiz de un arbol tiene nivel cero y el nivel de cualquier otro nodo en
el arbol es de un nivel mayor en una unidad que el nivel de su padre.
Un arbol binario completo de nivel "n" es aquel en el cual cada nodo es de
un nivel menor que "n", no tiene subarboles izquierdo y derecho. Nivel "n"
representa donde se encuentran las hojas aunque solamente exista una.
Un método para visualizar un árbol binario es el de considerar cada nodo
como si tuviera 3 campos elementales.
1.-INFO.-Es el campo que hace referencia a la información que está almace-
nada en un elemento en particular.
2.-LEFT Y RIGHT.- Se refieren a los punteros de lad raices de los subarboles
izquierdo y derecho de un árbol binario. Por supuesto si un subárbol izquier-
do o derecho esta vacio el puntero correspondiente es nulo o Nil.
CREACION DE UN ARBOL BINARIO.
Al construir un arbol binario se utilizarán 3 operaciones maketree,setleft
(p,x, setright(p,x).
1.- MAKETREE. Crea un nuevo árbol binario de un solo nodo con un campo de
información x y retorna un puntero a este nodo.
p=Getnode P raiz
info(p)=x
left(p)=nil //-[ ][X][ ]-//
right(p)=nil
maketree=p
2.- SETLEFT(P,X).-Acepta un puntero con información de un nodo de árbol,
creando un hijo izquierdo del nodo p con un campo de información x.
1.- si left(p)<>nil entonces
"Error de operación setleft ilegal" P Raiz
ir a # 2
de lo contrario -[ ][a][ ]-//
q=maketree -[ ][b][ ]-//
left(p)=q [ ][c][ ]-//
2.-fin
3.-SETRIGHT(P,X).-Consiste en agregar un hijo al lado derecho del arbol
(nodo binario)esta operación es analoga a setleft ecepto de que está
crea un hijo derecho al nodo p.
1.-si right(p)<>nil
entonces "error de operación setright ilegal"
ir al #2
de lo contrario //-[ ][a][ ]-
q=maketree //-[ ][b][ ]-
right(p)=q //-[ ][c][ ]-//
2.-fin
EJEMPLO:
Crea un árbol binario de la forma siguiente:
1.- Crear un nodo con campo de información ´H´
2.- Al nodo ´H´se le agrega el hijo derecho con info ´7´
3.- Al nodo ´7´se le agrega un subárbol izquierdo con información ´N´
4.- Al nodo ´H´se le agrega un subárbol con info ´C´
5.- Al nodo ´C´se le agrega un nodo derecho con info ´Z´
6.- Al nodo ´Z´se le agrega un nodo al lado izquierdo con info ´X´
7.- Al nodo ´C´se le agrega un nodo derecho con info ´T´
8.- Al nodo ´7´se le agrega un nodo izquierdo con info ´R´.
Raiz
-[ ][H][ ]-
//-[ ][C][ ]- -[ ][7][ ]-//
-[ ][Z][ ]-// -[ ][N][ ]-//
//-[ ][X][ ]-//
3.- (Proyecto) APLICACION DE ARBOLES BINARIOS
Un árbol binario es una estructura de datos muy util cuando se tiene que hacer desiciones de dos caminos en cada punto en un proceso. Por ejemplo, supongamos que queremos encontrar todos los duplicados en una lista de números. Una forma de conseguir esto es comparando cada nú- mero con todos los otros que le preceden. Sin embargo, esto implica un número muy grande de comparaciones. El número de comparaciones puede ser reducido si es utilizado un árbol binario. El primer número es leido y colocado en un nodo como la raiz del árbol con subarbol izquierdo y derecho vacios. cada número sucesivo en la lis- ta es entonces comparado con el elemento de la raiz, si estos son igua- les tenemos un duplicado, si es menor el proceso se repite con el sub- arbol izquierdo y si es mayor el proceso repetido con el subárbol derecho. Esto continua hasta que se encuentre un duplicado o se llega a un subárbol vacio y se termina con todos los elementos de la lista. RECORRIDO DE UN ARBOL BINARIO Existen 3 formas para recorrer un árbol binario:Preorden,entreorden y posorden. En cualquiera de los casos hablamos de visitar los nodos de un árbol bimario. El orden en el cuál son visitados los nodos de una lista lineal duran- te su recorrido es del primero al último. Sin embargo no existe tal orden para nodos de un árbol, es decir aqui utilizarán diferentes ordenamientos para el recorrido en diferentes casos. Definiremos 3 metodos para hacer este recorrido: PREORDEN 1.- Visitar la raiz 2.- Recorrer el subárbol de la izquierda en preorden 3.- Recorrer el subárbol de la derecha en preorden ENTREORDEN 1.- Recorrer el subarbol de la izquierda en entreorden 2.- Visitar la raiz 3.- Recorrer el subárbol de la derecha en entreorden POSTORDEN 1.- Recorrer el subárbol de la izquierda en postorden 2.- Recorrer el subárbol de la derecha en postorden 3.- Visitar la raiz NOTACION DE SUCESORES Y ANTECESORES EN EL RECORRIDO DE LOS ARBOLES BINARIOS. P*= Dirección del nodo sucesor en preorden P$= Dirección del nodo sucesor en entreorden P#= Dirección del nodo sucesor en postorden *P= Dirección del nodo antecesor en preorden $P= Dirección del nodo antecesor en entreorden #P= dirección del nodo antecesor en postorden. Regresar al menu principal.
Temas: 1.-Conceptos y aplicaciones 2.-Manipulación de grafos 3.-Proyecto de grafos
1.- CONCEPTOS Y APLICACIONES
GRAFOS.- Está formado por un conjunto de nodos o vertices y un conjunto de
árboles .
--------->(B)
(A) --------->(C)
--------->(D)<-------(f) (E)----------->(G)
(H)
ARCO.-Se especifica por medio de un par de nodos. Por ejemplo del grafo
anterior se tiene un conjunto de nodos: {A,B,C,D,E,F,G,H} los arcos será
{(A,B),(A,C),(A,D),(A,A),(F,D),(E,G)}.
Las flechas entre nodos indican los arcos, la cabeza de cada flecha
representa el segundo nodo en el par de nodos ordenados que hacen un arco,
mientras que la cola de las flechas representan el primer nodo en el par.
NODO N INCIDENTE.- Un nodo N se dice que es incidente a un arco "X"
si N es uno de los dos nodos en el par ordenado de nodos que componen "X".
X
A--------->B .: A y B son incidentes al arco X
GRADO DE UN NODO N .- Es el numero de arcos incidentes a el.
Por ejemplo:
A=4 B=1 C=1 D=2
E=1 F=1 G=1 H=0
ENTRE GRADO DE UN NODO N.- Es el numero de arcos que contienen a N
como cabeza.
A=1 B=1 C=1 D=2 E=0 F=0 G=1 H=0
FUERA DE GRADO DE UN NODO N.- Es el numero de arcos que contienen
a N como la cola.
A=4 B=0 C=0 D=0 E=1 F=1 G=0 H=0
NODO N ADYACENTE.- Un nodo N es adyacente al nodo M si existe un
arco de M a N ò viceverza.
(A,B) (B,A)
Si existe un arco de el nodo A al nodo B con una longitud K,
entonces hay un camino del nodo A hasta el nodo B, un camino de un nodo
en el mismo nodo se denomina ciclo. Si un grafo contiene un ciclo este se
denomina ciclico en caso contrario se denomina aciclico.
LISTA DE ADYACENCIA
Son listas enlazadas una para cada nodo conteniendo los nombres de
los nodos a los que el nodo esta conectado; las cabezas de cada una de estas
listas se tienen en listas encadenadas o enlazadas.
[O][]--------->[J][]------->[S][]--//
[J][]--------->[C][]------->[M][]--//
[S][]--------->[Q][]------->[U][]--//
[C][]--//
[M][]--//
[Q][]--//
[U][]--//
En todas las estructuras de datos se necesita alguna forma
sistematica de alcanzar o buscar algun elemento, o bien recorrerlo.
En un arregl unidimensional por medio de un ciclo y un contador
se localizan elementos, en un arreglo bidimensional por medio de dos ciclos
y dos contadores. En una pila se saca uno a uno los elementos hasta
localizarlos, en una cola se remueven los elementos uno a uno hasta
localizarlos, en un arbol binario se utilizan tres diferentes recorridos
cada uno de los cuales va a un nivel mas profundo del arbol y luego sube,
esta estrategia se denomina primera en profundidad.
Existe otra forma la cual se denomina estrategia primera en anchura,
esta estrategia junto con la estrategia primera en profundidad se utiliza
para recorrer los grafos.
Este tipo de grafo en el cual un numero esta asociado con cada arco
es denominado un grafo con factor de peso o una red.
El numero asociado por un arco es denominado subfactor de peso.
2.- MANIPULACION DE GRAFOS
Un grafo puede estar representado por una matriz de adyacencia o por una lista de adyacencia.
MATRIZ DE ADYACENCIA
Si hay N nodos en un grafo la matriz de adyacencia sera una tabla con N filas y N columnas. El valor de la posición (I,J) de la tabla sera 1, si existe un arco de un nodo a otro y cero si no lo existe. Si el grafo contiene factor de peso puede contener en la celda ó posición (I,J), el peso sobre el arco si no contiene peso o arco su valor sera será cero. O T S C M Q U (O) O [0][1][1][0][0][0][0] / \ T [0][0][0][1][1][0][0] / \ S [0][0][0][0][0][1][1] (T) (S) C [0][0][0][0][0][0][0] / \ / \ M [0][0][0][0][0][0][0] / \ / \ Q [0][0][0][0][0][0][0] (C) (M)(Q) (U) U [0][0][0][0][0][0][0]
3.- PROYECTO DE GRAFOS
Los grafos son estructurados utiles para representación fisica en
donde existan elementos que puedan tener relaciones entre si como por
ejemplo carreteras y rutas entre ciudades, etc.
Supongamos que se desea viajar de una determinada ciudad a otra por
una determinada linea las rutas que tienen estas lineas.
Atlas-Houston
Atlas-Washigton
Austin-Dallas
Austin-Houston
Chicago-Denver
Dallas-Austin
Dallas-Chicago
Dallas-Denver
Denver-Atlanta
Denver-Chicago
Houston-Atlanta
Washigton-Atlanta
Washigton-Dallas
Cada una de estas ciudades son los nodos los pares dirigidos de
ciudades que describan las rutas, son las areas de los grafos.
Su representación es la siguiente:
ATL AUS CHI DAL DEN HOU WAS
ATL[ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 1 ][ 1 ]
AUS[ 0 ][ 0 ][ 0 ][ 1 ][ 0 ][ 1 ][ 0 ]
CHI[ 0 ][ 0 ][ 0 ][ 0 ][ 1 ][ 0 ][ 0 ]
DAL[ 0 ][ 1 ][ 1 ][ 0 ][ 1 ][ 0 ][ 0 ]
DEN[ 1 ][ 0 ][ 1 ][ 0 ][ 0 ][ 0 ][ 0 ]
HOU[ 1 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ]
WAS[ 1 ][ 0 ][ 0 ][ 1 ][ 0 ][ 0 ][ 0 ]
La pregunta es:
¿Puede ser posible ir desde la ciudad X a la ciudad Y en está linea?
La estrategia será investigar si es posible alcanzar el destino direc-
tamente si no es asi se tomara cada uno de los lugares que pueden alcanzar
el destino directamente desde calquiera de ellas; si no podemos repetiremos
el proceso para ver si podemos alcanzar nuestro destino desde cualquiera de
las siguientes ciudades.El proceso continuara hasta que encontremos el des-
tino o determinemos que no se puede ir ahi desde la ciudad de partida.
El objetivo sera buscar la solucion mas optima.
Solucion al problema de grafos utilizando estrategias primeras en
profundidad.
PROCEDIMIENTO:
Iniciamos examinando si del nodo de origen no existe un camino directo al
destino, si no es asi todos los nodos proximos que tengan al nodo de origen
como cola,se empujan a una pila,si sus nodos mas proximos que tengan a ese
elemento como cola es el destino.
Si ninguno de esos nodos es el destino se empujan a la pila y asi sucesivamente
hasta encontrar el destino o bien que la pila quede vacia tomando en cuenta que
si un nodo no es el destino pero ya fue visitado no se empuje a la pila para no
caer a un ciclo infinito.
1.-Chicago-Dallas
2.-Houston-Austin
1.-Chicago-Denver-Atlanta-Washington-Dallas
2.-Houston-Atlanta-Washington-Dallas-Austin
SOLUCION AL PROBLEMA DE GRAFOS UTILIZANDO LA ESTRATEGIA PRIMERA EN ANCHURA.
Esta busqueda es detreminada primera en ayuda pues examina todos los
posibles caminos en la misma profundidad antes de ir a un nivel mas profundo
AUSTIN-WASHINGTON
1.-AUSTIN-DALLAS Y HOUSTON
DALLAS-DENVER Y CHICAGO
HOUSTON-ATLANTA
HOUSTON-CHICAGO
2.-HOUSTON-ATLANTA-WASHINGTON-DALLAS-CHICAGO
HOUSTON-ATLANTA-WASHINGTON-CHICAGO.
LISTA ENLAZADA: Es una representacion de listas en la que el orden de los
elemento esta determinada por un campo de enlace explicito en cada elemento,
en vez de su posicion secuencial.
LISTAS CON LEANAS: Son punteros que apuntan a los nuevos sucesores o antece
sores de un arbol binario segun sea el metodo de recorrido que se este
utilizando los cuales pueden ser entrelanzamiento izquierdo,derecho y arbol
binario entrelazado dichas listas tambien se les llama listas entrelazadas.
LISTAS ENLAZADAS: En administracion de dato s un grupo de elementos en el
que cada uno de ellos apunta al proximo. Una lista encadenada permite la
organizacion de un conjunto secuencial de datos y en posiciones de almace-
namiento no contiguas.
BIBLIOGRAFIA
1.-Estructura de datos en pascal Aaron M. Tenembaum/Mashe J.Augenstein Edit. Prentice Hall 2.-Pascal y estructura de datos Nell Dale/ Susan C. Lilly Edit. Mc Graw Hill ------------------------------------------------------ Regresar al menu principal. Hasta la vista Baby....