martes, 18 de octubre de 2011

Recursividad:
Es aquella propiedad que provee metodo por la capacidad que puede llamarse a si mismo.
Un metodo que tiene sentencia entre las que se encuentrn al menos una que se llama al propio metodo

No recursividad:
metodo1(...)
{
...
}
metodo(...)
{
...
metodo1()//llamada al metodo2
...
}
Recursividad
Metodo1(...)
{
...
Metodo1
...
}

Aplicaciones de Recursividad
-La suma de los primeros numeros positivos:
-S(6)=S(6)+S(5)+S(4)+S(3)+S(2)+S(1)
-long SumaNenteros(int n)
{
if(n==1)
return 1;
else
return n + SumaNenteros(n-1);
}
-Serie Fibonacci 0,1,2,3,4,8,13,21
-Esta serie inicia con 8 y 1 y tiene la propiedad de que cada elemento es la suma de los 2 elementos.
Suma de los 2 elementos:
ejemplo
0+1=1
1+1=2
2+1=3
3+2=5
5+3=8

 Entonces se puede establecer que:
Fibonacci(0)=0
Fibonacci(1)=1

Fibonacci
Publicado por en No hay comentarios:

viernes, 7 de octubre de 2011

Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.



Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

  • Evaluación de expresiones en notación postfija (notación polaca inversa).
  • Reconocedores sintácticos de lenguajes independientes del contexto
  • Implementación de recursividad.



Operaciones

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.
  • Crear: se crea la pila vacía.
  • Apilar: se añade un elemento a la pila.(push)
  • Desapilar: se elimina el elemento frontal de la pila.(pop)
  • Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
  • Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.


ejemplos de pilas
Estatica

import java.util.Scanner;



/**

 *
 * @author Pollo
 */
public class Pila Estatica {
    public static void main(String[] args) {
        int dato=-1;
        int opcion;
        int num=5;
        int pila[]= new int[num];
        Scanner op = new Scanner(System.in);

        System.out.println("Opciones de Pila");
        System.out.println("1.Insertar");
        System.out.println("2.Eliminar");
        System.out.println("3.Mostrar");
        System.out.println("4.Salir");
        System.out.println("\nElija la operacion que desee:");
        opcion = op.nextInt();
        switch(opcion){
            case 1:
                System.out.println("Inserte el numero:");
                for (int tope = 0; tope < 5; tope++) {
                    Scanner scaner= new Scanner(System.in);
                    dato=scaner.nextInt();
                    pila[tope]=dato;
                }
                break;
            case 2:
                if(dato== -1){
                    System.out.println("No se puede eliminar, pila vacia!!");
                }
                else{
                    
                }
                break;
            case 3:
                System.out.println("La pila tiene los siguientes datos: ");
                for (int tope = 4; tope >= 0; tope--) {
                    System.out.println(pila[tope]);
                }
                break;
            case 4:
                System.exit(1);
                break;
                 default:break;
        }
    }
}
Pila dinamica

2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h>
#include <stdlib.h>
 
/* estructura auto-referenciada */
struct nodoPila {      int dato;                  /* define un dato como int */
   struct nodoPila *ptrSiguiente; /* apuntador a nodoPila */
}; /* fin de la estructura nodoPila */
 
typedef struct nodoPila NodoPila; /* sinónimo de la estructura nodoPila */typedef NodoPila *ptrNodoPila; /* sinónimo para NodoPila* */
 
/* prototipos */
void empujar( ptrNodoPila *ptrCima, int info );
int sacar( ptrNodoPila *ptrCima );int estaVacia( ptrNodoPila ptrCima );
void imprimePila( ptrNodoPila ptrActual );
void instrucciones( void );
 
/* la función main comienza la ejecución del programa */int main()
{ 
   ptrNodoPila ptrPila = NULL; /* apunta al tope de la pila */
   int eleccion; /* elección de menú del usuario */
   int valor;  /* entrada int del usuario */ 
   instrucciones(); /* despliega el menú */
   printf( "? " );
   scanf( "%d", &eleccion );
    /* mientras el usuario no introduzca 3 */
   while ( eleccion != 3 ) { 
 
      switch ( eleccion ) { 
          /* empuja el valor dentro de la pila */
         case 1:      
            printf( "Introduzca un entero: " );
            scanf( "%d", &valor );
            empujar( &ptrPila, valor );            imprimePila( ptrPila );
            break;
 
         /* saca el valor de la pila */
         case 2:       
            /* si la pila no esta vacía */
            if ( !estaVacia( ptrPila ) ) {
               printf( "El valor sacsdo es %d.n", sacar( &ptrPila ) );
            } /* fin de if */ 
            imprimePila( ptrPila );
            break;
 
         default:            printf( "Eleccion no valida.nn" );
            instrucciones();
            break;
 
      } /* fin de switch */ 
      printf( "? " );
      scanf( "%d", &eleccion );
   } /* fin de while */
    printf( "Fin del programa.n" );
 
   return 0; /* indica terminación exitosa */
 
} /* fin de main */ 
/* despliega las instrucciones del programa para el usuario */
void instrucciones( void )
{ 
   printf( "Introduzca su eleccion:n"      "1 para empujar un valor dentro de la pilan"
      "2 para sacar un valor dwe la pilan"
      "3 para terminar el programan" );
} /* fin de la función instrucciones */
 /* Inserta un nodo en la cima de la pila */
void empujar( ptrNodoPila *ptrCima, int info )
{ 
   ptrNodoPila ptrNuevo; /* apuntador al nuevo nodo */
    ptrNuevo = malloc( sizeof( NodoPila ) );
 
   /* inserta el nodo en la cima de la pila */
   if ( ptrNuevo != NULL ) {   
      ptrNuevo->dato = info;      ptrNuevo->ptrSiguiente = *ptrCima;
      *ptrCima = ptrNuevo;
   } /* fin de if */
   else { /* no queda espacio disponible */
      printf( "%d no se inserto. Memoria insuficiente.n", info );   } /* fin de else */
 
} /* fin de la función empujar */
 
/* Elimina un nodo de la cima de la pila */int sacar( ptrNodoPila *ptrCima )
{ 
   ptrNodoPila ptrTemp; /* apuntador a un nodo temporal */
   int valorElim; /* valor del nodo */
    ptrTemp = *ptrCima;
   valorElim = ( *ptrCima )->dato;
   *ptrCima = ( *ptrCima )->ptrSiguiente;
   free( ptrTemp );
    return valorElim;
 
} /* fin de la función sacar */
 
/* Imprime la pila */void imprimePila( ptrNodoPila ptrActual )
{ 
 
   /* si la pila esta vacía */
   if ( ptrActual == NULL ) {      printf( "La pila esta vacia.nn" );
   } /* fin de if */
   else { 
      printf( "La pila es:n" );
       /* mientras no sea el final de la pila */
      while ( ptrActual != NULL ) { 
         printf( "%d --> ", ptrActual->dato );
         ptrActual = ptrActual->ptrSiguiente;
      } /* fin de while */ 
      printf( "NULLnn" );
   } /* fin de else */
 
} /* fin de la función imprimePila */ 
/* Devuelve 1 si la pila está vacía, de lo contrario 0 */
int estaVacia( ptrNodoPila ptrCima )
{ 
   return ptrCima == NULL;




Publicado por en No hay comentarios:

lunes, 12 de septiembre de 2011


Diagrama:
image581.jpg
Programa:
#include <conio.h>

#include <iostream.h>

void Recorrido(char Info[8][2],int Indice[8],int Inicio,int Disp);

void main()

{

char Info[8][2]={{"G"},{"I"},{" "},{"T"},{"O"},{"A"},

{" "},{"T"}};

int Indice[8]={5,7,6,1,-999,3,-999,4};

int Inicio=0,Disp=2;

cout<<"El Recorrido es:\n";

Recorrido(Info,Indice,Inicio,Disp);

getch();

}

void Recorrido(char Info[8][2],int Indice[8],int Inicio,int Disp)

{

int Apuntador=Inicio;

while(Apuntador!=-999)

{

cout<<Info[Apuntador];

Apuntador=Indice[Apuntador];

}

}
Corrida:
image582.jpg
Publicado por en No hay comentarios:

Publicado por en No hay comentarios:
Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.

Tipos de Listas Enlazadas


Listas enlazadas lineales


Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.
Singly-linked-list.svg
Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo


Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.
Doubly-linked-list.svg
Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior
En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta técnica no se suele utilizar.


Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.
Circularly-linked-list.svg
Una lista enlazada circular que contiene tres valores enteros


Listas enlazadas circulares simples

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. 1


Lista Enlazada Doblemente Circular

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.


Nodos Centinelas

A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propósito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un “primer y último” nodo.


Publicado por en No hay comentarios:
Suscribirse a: Entradas (Atom)