Make your own free website on Tripod.com

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]


ESTRUCTURA DE DATOS II

UNIDADES

  UNIDAD I  (STRINGS) 
  UNIDAD II (ARBOLES)
  UNIDAD III(GRAFOS)   



UNIDAD I (strings)

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









UNIDAD II (Arboles)

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.






UNIDAD III (Grafos)

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....