miércoles, 6 de junio de 2012

PROGRAMACIÓN ESTRUCTURADA

¿Qué es una Programación Estructurada?
             Es un estilo con el cual el programador busca elaborar programas sencillos y fáciles de entender. Para ello, la programación estructurada hace uso de tres estructuras básicas de control, Éstas son:

           La programación estructurada se basa un teorema fundamental, el cual afirma que cualquier programa, no importa el tipo de trabajo que ejecute, puede ser elaborado utilizando únicamente las tres estructuras básicas (secuencia, selección, iteración).

Estructuras básicas de control
En programación, una estructura de control permite controlar el flujo de la ejecución de instrucciones. Con estas estructuras, el programador puede determinar el orden en que se ejecutarán las instrucciones que están dentro de estas estructuras.
*Estructura Secuencial: que una o varias acciones se realiza solo tras haberse realizado la anterior
*Estructura Selectiva: dada una condición se realiza una o varias acciones
*Estructura Repetitiva (ó Iterativa): una o varias acciones se realizan mientras se cumpla una condición dada
Originalmente las líneas de código de programación (instrucciones) eran ejecutadas secuencialmente, o sea, una después de la otra. Para alterar el orden de ejecución se utilizaba el enunciado goto, llamado "transferencia de control". Dos investigadores, Bohm y Jacopini, demostraron que el goto traía grandes problemas en el desarrollo de programas. También demostraron que los programas podían ser escritos sin ningún enunciado goto utilizando tres estructuras de control: estructura de secuencia, estructura de selección y estructura de repetición.

Programación Modular:
INSERCIÓN DE UN MÓDULO EN UN PROGRAMA.
 Para poder insertar un módulo en un programa o algoritmo hemos de declarar su existencia y contenido. Para ello escribiremos:
Módulo [Nombre del módulo]
Instrucción 1;
Instrucción 2;
.
.
.
Instrucción n;
     FinMódulo.
DECLARACIÓN.
Para nombrar a un módulo se seguirán las mismas pautas que con las variables. Se buscará que los nombres sean interpretables y claros. Se evitará que sean similares entre sí o con las variables que existan en el programa.
La numeración de las líneas del módulo es independiente de la del algoritmo principal, pudiendo repetirse si se quiere. Se entiende que el módulo se encuentra dentro del programa pero no se ejecuta hasta que es llamado desde el algoritmo principal de acuerdo con esta estructura.


INSTRUCCIÓN LLAMAR.
Hemos dicho que un módulo no se ejecuta hasta que es llamado a ejecutarse desde el algoritmo principal. Para ello utilizaremos la instrucción Llamar de acuerdo con esta sintaxis:
Llamar [Nombre del Módulo]
Cuando se llama a un módulo la ejecución del algoritmo principal se detiene y el flujo se desvía al módulo. Una vez se llega al fin del módulo, la ejecución en el algoritmo principal continúa por la sentencia inmediatamente posterior a la instrucción Llamar. Un módulo puede ser llamado cuantas veces se quiera. Es posible llamar a un módulo desde otro módulo: el efecto es el mismo al comentado anteriormente. La ejecución del módulo en curso se detiene prosiguiendo el flujo por el módulo que ha sido llamado. Una vez se termina de procesar el módulo llamado, se continúa en la instrucción inmediatamente posterior a la de llamada.

RECURSIÓN
Si en un programa llamamos en distintos puntos a un módulo, éste realiza una serie de procesos sin necesidad de repetir el código. Nos supondrá por tanto, un ahorro considerable.
La llamada a un módulo desde sí mismo también es posible, dando lugar a un anidamiento o módulo recursivo. Como en el caso de los bucles, la repetición normalmente irá sujeta a la evaluación de una condición que evoluciona a medida que se producen recursiones hasta dar lugar a una salida, que va devolviendo el control al punto desde el cual se autollamó el módulo. El sistema equivale a la generación sucesiva de copias del módulo. Las autollamadas se deben evitar siempre que sea posible, pues dificultan el seguimiento del flujo de los programas y es habitual que si no se controlan bien den lugar a situaciones de bloqueo o bucles infinitos. No haremos un desarrollo teórico de la recursión aunque quien lo desee puede dirigirse a otros contenidos de aprenderaprogramar.com donde se aborda el uso de la recursión.

Veamos un ejemplo de aproximación al concepto de módulo:
1. Inicio [PROGRAMA Comunicado]
          2. Mostrar “Comunicado de la empresa”
          3. Llamar Saludo
          4. Llamar Comunicado
          5. Llamar Despedida
6. Fin

    Módulo Saludo
          1. Mostrar “Con motivo de la celebración el próximo día 5 del Día Mundial del Medioambiente la empresa saluda a todos los empleados y les agradece el compromiso con el cuidado de ka naturaleza"
    FinMódulo

    Módulo Comunicado
           1. Mostrar "Con motivo de dicha conmemoración está previsto realizar un acto de plantaciones de arboles en los jardines del edificio central el próximo día 5  a las  12 del mediodía al que estan todo invitados”
    FinMódulo

    Módulo Despedida
           1. Mostrar “La empresa agradece su  participación y  les invita a sumarse al programa  <<Empleados por   una   ciudad sostenible>>.  
                                        Atentamente, El Director General”
    FinMódulo
: La ejecución es controlada por el algoritmo principal. Si existiera un módulo que no es llamado desde el algoritmo principal (ni a través de un módulo sí llamado) no se ejecutaría nunca.

Los módulos pueden situarse antes o después del algoritmo principal y seguir el orden de llamada o no. En este caso se han ordenado los módulos con Saludo ® Comunicado ® Despedida buscando un orden lógico.
La ordenación de módulos y algoritmo principal debe obedecer a la intención de facilitar la lectura y compresión del programa, al igual que los nombres que se usen. La representación gráfica de un módulo en el diagrama de flujo la haremos con el símbolo:

  
Si existen llamadas a módulos en un diagrama de flujo, habrá de existir, a continuación del diagrama del algoritmo principal, otros diagramas explicativos de cada módulo (un diagrama por módulo). La representación será:

Obsérvese que un módulo es tal por cuanto se identifica así y se subordina al algoritmo principal, pero su estructura es la de un programa y se le podría hacer funcionar como tal.

El algoritmo principal puede llamarse a sí mismo o ser llamado desde otro módulo. Para ello escribiremos:
  
Llamar Inicio

Llamar Inicio constituye en cualquier caso una autollamada debiendo tenerse en cuenta lo ya comentado al respecto. La representación gráfica del ejemplo anterior sería la siguiente:


Aunque este ejemplo por su sencillez no da demasiado juego, sí podemos intuir que supone una potente herramienta de cara a conseguir una mejor organización de los programas largos y complejos y facilitar su comprensión. Procesos muy complejos pueden quedar resumidos en el nombre de un módulo.

PROGRAMACIÓN PHP


PROGRAMACIÓN PHP:

      PHP es un lenguaje de código abierto muy popular, adecuado para desarrollo web y que puede ser incrustado en HTML. Es popular porque un gran número de páginas y portales web están creadas con PHP. Código abierto significa que es de uso libre y gratuito para todos los programadores que quieran usarlo. Incrustado en HTML significa que en un mismo archivo vamos a poder combinar código PHP con código HTML, siguiendo unas reglas.

     PHP se utiliza para generar páginas web dinámicas. Recordar que llamamos página estática a aquella cuyos contenidos permanecen siempre igual, mientras que llamamos páginas dinámicas a aquellas cuyo contenido no es el mismo siempre. Por ejemplo, los contenidos pueden cambiar en base a los cambios que haya en una base de datos, de búsquedas o aportaciones de los usuarios, etc.
 ¿Cómo trabaja PHP? El lenguaje PHP se procesa en servidores, que son potentes ordenadores con un software y hardware especial. Cuando se escribe una dirección tipo http://www.aprenderaprogramar.com/index.php en un navegador web como Internet Explorer, Firefox o Chrome, ¿qué ocurre? Se envían los datos de la solicitud al servidor que los procesa, reúne los datos (por eso decimos que es un proceso dinámico) y el servidor lo que devuelve es una página HTML como si fuera estática.

  El esquema es:
 
       Petición de página web al servidor --> El servidor recibe la petición, reúne la información necesaria consultando a bases de datos o a otras páginas webs, otros servidores, etc --> El servidor responde enviando una página web “normal” (estática) pero cuya creación ha sido dinámica (realizando procesos de modo que la página web devuelta no siempre es igual).

       Resumen:

Páginas estáticas: Petición --> Respuesta
Páginas dinámicas: Petición --> Procesado y preparación --> Respuesta

  Por regla general este tipo de lenguaje suele ser utilizado para crear contenido dinámico y poder interactuar con el usuario.

Lo mejor de usar PHP es que es extremadamente simple para el principiante, pero a su vez, ofrece muchas características avanzadas para los programadores profesionales y más avanzados.

  Con PHP puedes procesar la información de formularios, generar páginas con contenidos dinámicos, o enviar y recibir cookies, entre muchas más cosas. PHP lo utilizan desde pequeñas páginas web hasta grandes empresas. Muchas aplicaciones web están construidas usando PHP. Podemos citar Joomla y Drupal (gestores de contenido de páginas web), osCommerce (tiendas on-line para comercio electrónico), phpBB y SMF (sistemas de foros para páginas web), Moodle (plataforma educativa para educación on-line), etc.
 
          Arreglos en PHP:
         Se define a un arreglo como un grupo de elementos relacionados entre sí por medio de índices. Los arreglos pueden ser de una o más dimensiones, los de una dimensión, son llamadas comúnmente "vectores".

        A diferencia con el lenguaje C, en PHP, un vector puede tener elementos de distintos tipos.
Para hacer referencia a un elemento del vector, se utiliza un índice, que indica la dirección en donde se encuentra un determinado valor. El índice en un arreglo comienza siempre por cero. (Más adelante se verá que el índice de un vector, no necesariamente debe ser un número entero, sino que también puede ser un texto).
Ejemplo :
       Almacenar los nombres de los días de la semana en un vector y luego imprimirlos uno debajo de otro.
<Html>
<Title> Ejemplo   </Title>
<Body>
<?PHP
  // Inicialización del Vector
  $dia[0] = "Domingo";
  $dia[1] = "Lunes";
  $dia[2] = "Martes";
  $dia[3] = "Miércoles";
  $dia[4] = "Jueves";
  $dia[5] = "Viernes";
  $dia[6] = "Sábado";
  // Impresion del vector
  for($i=0; $i<7; $i++)
   {
    echo ($dia[$i] . "<Br>") ;
   }
 ?>
</Body>
</Html>
       Comentario:
  Se inicializa el vector indicando el número que le corresponde a cada posición entre corchetes [ ] y asignando el valor que se desea almacenar en dicha posición.
Un vector, en PHP, puede contener elementos de distintos tipos de datos, es decir, un elemento puede ser un número entero, otro una cadena, otro un número con decimales, etc.
Un modelo de este caso se puede observar en el siguiente ejemplo.
 Ejemplo: 
                        Almacenar en un vector los datos personales de un empleado y luego mostrarlos en pantalla.
<Html>
<Title>  Ejemplo  </Title>
<Body>
<?PHP
  // Inicializacion del Vector
  $Empleado[0] = 4371;
  $Empleado[1] = "Martinez Leandro";
  $Empleado[2] = "27.643.742";
  $Empleado[3] = 1429.54;
  $Empleado[4] = "Arquitecto";
  // Impresion del vector
  echo ("Legajo: " . $Empleado[0] . "<Br>");
  echo ("Nombre: " . $Empleado[1] . "<Br>");
  echo ("DNI : " . $Empleado[2] . "<Br>");
  echo ("Sueldo: " . $Empleado[3] . "<Br>");
  echo ("Profesion: " . $Empleado[4] . "<Br>");
 ?>
</Body>
</Html>

     Existen varias maneras de inicializar vectores en PHP. A continuación se describen algunos ejemplos.

    Pais[] = "Argentina";
    Pais[] = "Uruguay";
    Pais[] = "Brasil";
    Pais[] = "Chile";

      En este caso se observa que no es necesario colocar el número de índice, ya que PHP lo asigna automáticamente para cada valor, comenzando siempre desde cero. 
Otra forma de inicializar un vector, es a través del constructor array, como se muestra en el siguiente ejemplo:

     Pais =array("Argentina","Uruguay","Brasil","Chile");

    También  se puede definir un arreglo asociando explícitamente el índice a un valor, como se indica a continuación:
    $Frutas = array(0 => "Manzana",
                              1 => "Naranja",
                              2 => "Pera",
                              3 => "Ananá");
     
    Además, los índices, pueden no ser obligatoriamente consecutivos, ni tampoco comenzar de cero, ni tampoco ser un número. 
Vectores con índice de Texto
    
     Un vector en PHP, no solamente debe contener índice numérico, sino también, puede ser una letra o un texto.
Ejemplo : 
     
      Cargar en un vector algunas ciudades del mundo, de manera que el índice del vector contenga los tres primeros caracteres de la ciudad almacenada.
<Html>
<Title>  Ejemplo.php  </Title>
<Body>
<?Php
  // Inicializacion del Vector
  $Ciudad = array("Par" => "Paris",
                            "Lon" => "Londres",
                            "Ate" => "Atenas",
                            "Ber" => "Berlin",
                            "Lim" => "Lima");
  echo "<H2>"."Vector de Ciudades";
  echo "<H3>"."<Hr>";
  while (list($i,$Valor)=each($Ciudad))
   {
     echo "Posición: " . $i . " - ";
     echo "Contenido: " . $Valor;
     echo "<Br>";
    }
 ?>
</Body>
</Html>
La salida obtenida es:
   





Variables PHP:
     El ámbito de una variable es el contexto dentro del que la variable está definida. La mayor parte de las variables PHP sólo tienen un ámbito simple. Este ámbito simple también abarca los ficheros incluídos y los requeridos. Por ejemplo:

<?php
$a = 1;
include 'b.inc';
?>

     Aquí, la variable $a estará disponible al interior del script incluido b.inc. Sin embargo, al interior de las funciones definidas por el usuario se introduce un ámbito local a la función. Cualquier variable usada dentro de una función está, por omisión, limitada al ámbito local de la función. Por ejemplo:

<?php
$a = 1; /* ámbito global */

function test()
{
    echo $a; /* referencia a una variable del ámbito local */
}

test();
?>

       Este script no producirá salida, ya que la sentencia echo utiliza una versión local de la variable $a, a la que no se ha asignado ningún valor en su ámbito. Puede que usted note que hay una pequeña diferencia con el lenguaje C, en el que las variables globales están disponibles automáticamente dentro de la función a menos que sean expresamente sobre escritas por una definición local. Esto puede causar algunos problemas, ya que la gente puede cambiar variables globales inadvertidamente. En PHP, las variables globales deben ser declaradas globales dentro de la función si van a ser utilizadas dentro de dicha función.
La palabra clave global

En primer lugar, un ejemplo de uso de global:

<?php
$a = 1;
$b = 2;
function Suma()
{
    global $a, $b;

    $b = $a + $b;
}

Suma();
echo $b;
?>

       El script anterior producirá la salida "3". Al declarar $a y $b globales dentro de la función, todas las referencias a tales variables se referirán a la versión global. No hay límite al número de variables globales que se pueden manipular dentro de una función.
Un segundo método para acceder a las variables desde un ámbito global es usando el array $GLOBALS. 

El ejemplo anterior se puede reescribir así:

<?php
$a = 1;
$b = 2;

function Suma()
{
    $GLOBALS['b'] = $GLOBALS['a'] + $GLOBALS['b'];
}

Suma();
echo $b;
?>

       El array $GLOBALS es un array asociativo con el nombre de la variable global como clave y los contenidos de dicha variable como el valor del elemento del array. 

Uso de variables estáticas

       Una variable estática existe sólo en el ámbito local de la función, pero no pierde su valor cuando la ejecución del programa abandona este ámbito. Consideremos el siguiente ejemplo:

<?php
function test()
{
    $a = 0;
    echo $a;
    $a++;
}
?>

       Esta función tiene poca utilidad ya que cada vez que es llamada asigna a $a el valor 0 e imprime un "0". La sentencia $a++, que incrementa la variable, no sirve para nada, ya que en cuanto la función finaliza, la variable$a desaparece. Para hacer una función útil para contar, que no pierda la pista del valor actual del conteo, la variable $a debe declararse como estática:

<?php
function test()
{
    static $a = 0;
    echo $a;
    $a++;
}
?>

       Ahora, $a se inicializa únicamente en la primera llamada a la función, y cada vez que la función test() es llamada, imprimirá el valor de $a y lo incrementa.
Las variables estáticas también proporcionan una forma de manejar funciones recursivas. Una función recursiva es la que se llama a sí misma. Se debe tener cuidado al escribir una función recursiva, ya que puede ocurrir que se llame a sí misma indefinidamente. Hay que asegurarse de implementar una forma adecuada de terminar la recursión. La siguiente función cuenta recursivamente hasta 10, usando la variable estática $count para saber cuándo parar:

<?php
function test()
{
    static $count = 0;

    $count++;
    echo $count;
    if ($count < 10) {
        test();
    }
    $count--;
}
?>
Nota:
       
       Las variables estáticas pueden ser declaradas como se ha visto en los ejemplos anteriores. Al tratar de asignar valores a estas variables que sean el resultado de expresiones, causará un error de análisis sintáctico.

Ejemplo: Declaración de variables estáticas

<?php
function foo(){
    static $int = 0;          // correcto
    static $int = 1+2;        // incorrecto  (ya que es una expresión)
    static $int = sqrt(121);  // incorrecto  (es una expresión también)

    $int++;
    echo $int;
}
?>

Nota: Las declaraciones estáticas son resueltas en tiempo de compilación.

Nota: Utilizar una clave global fuera de una función no es un error. Esta pueda ser utilizada aún si el fichero está incluido en el interior de una función.

Funciones:
  La función podría ser definida como un conjunto de instrucciones que explotan ciertas variables para realizar una tarea más o menos elemental.

    PHP basa su eficacia principalmente en este tipo de elemento. Una gran librería que crece constantemente, a medida que nuevas versiones van surgiendo, es complementada con las funciones de propia cosecha dando como resultado un sinfín de recursos que son aplicados por una simple llamada.

        Las funciones integradas en PHP son muy fáciles de utilizar. Tan sólo hemos de realizar la llamada de la forma apropiada y especificar los parámetros y/o variables necesarios para que la función realice su tarea.

      Lo que puede parecer ligeramente más complicado, pero que resulta sin lugar a dudas muy práctico, es crear nuestras propias funciones. De una forma general, podríamos crear nuestras propias funciones para conectarnos a una base de datos o crear los encabezados o etiquetas meta de un documento HTML. En definitiva, es interesante crear funciones para la mayoría de acciones más o menos sistemáticas que realizamos en nuestros programas.

       Aquí daremos el ejemplo de creación de una función que, llamada al comienzo de nuestro script, nos crea el encabezado de nuestro documento HTML y coloca el titulo que queremos a la página:

<?
function hacer_encabezado($titulo)
{
$encabezado="<html><head>t<title>$titulo</title></head>";
echo $encabezado;
}
?>

       Esta función podría ser llamada al principio de todas nuestras páginas de la siguiente forma:
$titulo="Mi web";
hacer_encabezado($titulo);

      De esta forma automatizamos el proceso de creación de nuestro documento. Podríamos por ejemplo incluir en la función otras variables que nos ayudasen a construir las etiquetas meta y de esta forma, con un esfuerzo mínimo, crearíamos los encabezados personalizados para cada una de nuestras páginas. De este mismo modo nos es posible crear cierres de documento o formatos diversos para nuestros textos como si se tratase de hojas de estilo que tendrían la ventaja de ser reconocidas por todos los navegadores.

       Por supuesto, la función ha de ser definida dentro del script ya que no se encuentra integrada en PHP sino que la hemos creado nosotros. Esto en realidad no pone ninguna pega ya que puede ser incluida desde un archivo en el que iremos almacenando las definiciones de las funciones que vayamos creando o recopilando.

       Estos archivos en los que se guardan las funciones se llaman librerías. La forma de incluirlos en nuestro script es a partir de la instrucción require o include:
require("libreria.php") o include("libreria.php")

   En resumen,  quedaría así:

   Tendríamos un archivo libreria.php como sigue

<?
//función de encabezado y colocación del titulo
function hacer_encabezado($titulo)
{
$encabezado="<html>n<head>nt<title>$titulo</title>n</head>n";
echo $encabezado;
}
?>

    Por otra parte tendríamos nuestro script principal página.php:
<?
include("libreria.php");
$titulo="Mi Web";
hacer_encabezado($titulo);
?>
<body>
El cuerpo de la página
</body>
</html>

       También puede resultar muy práctico el utilizar una nomenclatura sistemática a la hora de nombrarlas: Las funciones comerciales podrían ser llamadas com_loquesea, las de bases de datos bd_loquesea, las de tratamiento de archivos file_loquesea. Esto nos permitirá reconocerlas enseguida cuando leamos el script sin tener que recurrir a nuestra oxidada memoria para descubrir su utilidad.

Estructura de control en PHP:

       PHP es un lenguaje basado en Perl, con una sintaxis muy parecida a la de C/C++ o Java. Una de las partes importantes de cualquier lenguaje son las estructuras de control. A continuación, se muestra un ejemplo de cada una de las estructuras de control que se manejan en PHP.
# PHP: If 

if ($a == $b) {
    Instrucciones
} elseif ($a > $b) {
    Instrucciones
} else ($a < $b) {
    Instrucciones
}
# PHP: Operador ternario (aplicación especial del If)
$a = ($b > 10) ? true : false;

# PHP: Switch
switch ($var1) {
case 0:
    Instrucciones
    break;
case 1:
    Instrucciones
    break;
default:
    Instrucciones
    break;
}
       El operador ternario es utilizado como un método abreviado de asignación de variables, en donde se debe comparar un valor para determinar el valor que tomará una variable. Este está dividido por la expresión a evaluar, el signo de interrogación (?), el valor que tomará de ser verdadera la expresión, dos puntos (:) y el valor si la expresión es falsa.
# PHP: For

for ($i = 0; $i < 10; $i++) {
    Instrucciones
}
# PHP: While
while ($var1 != false) {
    Instrucciones
}
# PHP: Do..While
do {
    Instrucciones
} while ($var2 === true);

      La estructura de control Do..While tiene la funcionabilidad de que el ciclo se realice por lo menos una vez, y después evaluar la expresión de salida. Tiene la misma funcionabilidad que la sentencia Repeat, en lenguaje Pascal.

      Ahora, existe una cuarta estructura de bucles llamada Foreach, que en PHP, nos sirve para recorrer mucho más facilmente los elementos de un arreglo. La sintaxis, indica que las filas o registros se van recorriendo de uno en uno, y el valor de cada uno, se almacena en una variable.

# PHP: Foreach
foreach ($foo as $bar) {
    echo $bar . "<br />";
}
      
      En el ejemplo, la variable $foo es el arreglo y $bar, la variable que recibe el valor de cada una de las filas recorridas.

ORDENAMIENTO Y BUSQUEDA


ORDENAMIENTO.

Uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la clasificación u ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada. Cuando se analiza un método de ordenación, hay que determinar cuántas comparaciones e intercambios se realizan para el caso más favorable, para el caso medio y para el caso más desfavorable.

La colocación en orden de una lista de valores se llama Ordenación. Por ejemplo, se podría disponer una lista de valores numéricos en orden ascendente o descendente, o bien una lista de nombres en orden alfabético. La localización de un elemento de una lista se llama búsqueda.

Tal operación se puede hacer de manera más eficiente después de que la lista ha sido ordenada.

Existen varios métodos para ordenamiento, clasificados en tres formas:

Intercambio
Selección
Inserción.

En cada familia se distinguen dos versiones: un método simple y directo, fácil de comprender pero de escasa eficiencia respecto al tiempo de ejecución, y un método rápido, más sofisticado en su ejecución por la complejidad de las operaciones a realizar, pero mucho más eficiente en cuanto a tiempo de ejecución. En general, para arreglos con pocos elementos, los métodos directos son más eficientes (menor tiempo de ejecución) mientras que para grandes cantidades de datos se deben emplear los llamados métodos rápidos.

Intercambio

El método de intercambio se basa en comparar los elementos del arreglo e intercambiarlos si su posición actual o inicial es contraria inversa a la deseada. Pertenece a este método el de la burbuja clasificado como intercambio directo. Aunque no es muy eficiente para ordenar listas grandes, es fácil de entender y muy adecuado para ordenar una pequeña lista de unos 100 elementos o menos.

Una pasada por la ordenación de burbujeo consiste en un recorrido completo a través del arreglo, en el que se comparan los contenidos de las casillas adyacentes, y se cambian si no están en orden. La ordenación por burbujeo completa consiste en una serie de pasadas ("burbujeo") que termina con una en la que ya no se hacen cambios porque todo está en orden.

Ejemplo:
Supóngase que están almacenados cuatro números en un arreglo con casillas de memoria de x[1] a x[4]. Se desea disponer esos números en orden creciente. La primera pasada de la ordenación por burbujeo haría lo siguiente:

Comparar el contenido de x[1] con el de x[2]; si x[1] contiene el mayor de los números, se intercambian sus contenidos.

Comparar el contenido de x[2] con el de x[3]; e intercambiarlos si fuera necesario.

Comparar el contenido de x[3] con el de x[4]; e intercambiarlos si fuera necesario.
Al final de la primera pasada, el mayor de los números estará en x[4].




Quicksort.

Si bien el método de la burbuja era considerado como el peor método de ordenación simple o menos eficiente, el método Quicksort basa su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre ellas. En otras palabras, si dividimos el array a ordenar en dos subarrays de forma que los elementos del subarray inferior sean más pequeños que los del subarray superior, y aplicamos el método reiteradamente, al final tendremos el array inicial totalmente ordenado. Existen además otros métodos conocidos, el de ordenación por montículo y el de shell.

        Selección
   
        Los métodos de ordenación por selección se basan en dos principios básicos:

           Seleccionar el elemento más pequeño (o más grande) del arreglo.
Colocarlo en la posición más baja (o más alta) del arreglo.
A diferencia del método de la burbuja, en este método el elemento más pequeño (o más grande) es el que se coloca en la posición final que le corresponde.

Inserción.

El fundamento de este método consiste en insertar los elementos no ordenados del arreglo en subarreglos del mismo que ya estén ordenados. Dependiendo del método elegido para encontrar la posición de inserción tendremos distintas versiones del método de inserción.

          BÚSQUEDA.

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado.

Siendo el array de una dimensión o lista una estructura de acceso directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso, para encontrar elementos dentro de un array: búsqueda lineal y búsqueda binaria.
Búsqueda Secuencial:

La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.

        El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria, donde se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

Búsqueda Binaria.

La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.

ESTRUCTURAS DINÁMICAS DE DATOS



ESTRUCTURAS DINÁMICAS DE DATOS

En función de la forma en que se relacionan existen varios tipos de estructuras de datos. Este tipo de estructuras son autorreferenciadas, es decir, contienen entre sus campos un puntero de su mismo tipo. Las más utilizadas son:

PILAS
COLAS


PILAS

La pila es una lista de elementos caracterizada porque las operaciones de inserción y eliminación se realizan solamente en un extremo de la estructura. El extremo donde se realizan estas operaciones se denomina habitualmente 'cima' (top en nomenclatura inglesa). 
Dada una pila P=(a,b,c,...k), se dice que a, que es el elemento más inaccesible de la pila, está en el fondo de la pila (bottom) y que k, por el contrario, el más accesible, está en la cima. 

Las restricciones definidas para la pila implican que si una serie de elementos A,B,C,D,E se añaden, en este orden a una pila, entonces el primer elemento que se borre de la estructura deberá ser el E. Por tanto, resulta que el último elemento que se inserta en una pila es el primero que se borra. Por esta razón, se dice que una pila es una lista LIFO (Last In First Out, es decir, el último que entra es el primero que sale). 
Un ejemplo típico de pila lo constituye un montón de platos, cuando se quiere introducir un nuevo plato, éste se pone en la posición más accesible, encima del último plato. Cuando se coge un nuevo plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido. 
Otro ejemplo natural de la aplicación de la estructura pila aparece durante la ejecución de un programa de ordenador, en la forma en que la máquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información asociada con ese procedimiento (parámetros, variables, constantes, dirección de retorno, etc..) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador sólo se puede estar ejecutando un procedimiento, esto quiere decir que sólo es necesario que sean accesibles los datos de un procedimiento (el último activado que está en la cima). De ahí que la estructura pila sea muy apropiada para este fin. 

Como en cualquier estructura de datos, asociadas con la estructura pila existen una serie de operaciones necesarias para su manipulación, éstas son: 
Crear la pila. 
Comprobar si la pila está vacia. Es necesaria para saber si es posible eliminar elementos. 
Acceder al elemento situado en la cima. 
Añadir elementos a la cima. 
Eliminar elementos de la cima. 

La especificación correcta de todas estas operaciones permitirá definir adecuadamente una pila.      Este tipo de estructuras se caracteriza porque todas las operaciones se realizan en el mismo lado. Es de tipo LIFO ( Last In First Out ), el último elemento en entrar es el primero en salir.

REPRESENTACIÓN DE LAS PILAS

Los lenguajes de programación de alto nivel no suelen disponer de un tipo de datos pila. Aunque por el contrario, en lenguajes de bajo nivel (ensamblador) es posible manipular directamente alguna estructura pila propia del sistema. Por lo tanto, en general, es necesario representar la estructura pila a partir de otros tipos de datos existentes en el lenguaje. 

La forma más simple, y habitual, de representar una pila es mediante un vector unidimensional. Este tipo de datos permite definir una secuencia de elementos (de cualquier tipo) y posee un eficiente mecanismo de acceso a la información contenida en él. 

Al definir un array hay que determinar el número de índices válidos y, por lo tanto, el número de componentes definidos. Entonces, la estructura pila representada por un array tendrá limitado el número de posibles elementos. 

Se puede definir una pila como una variable: 
Pila: array [1..n] de T 

donde T es el tipo que representa la información contenida en la pila (enteros, registros,etc.) 

El primer elemento de la pila se almacenará en Pila[1], será el fondo de la pila, el segundo elemento en Pila[2] y así sucesivamente. En general, el elemento i-úsimo estará almacenado en Pila[i]. 

Como todas las operaciones se realizan sobre la cima de la pila, es necesario tener correctamente localizada en todo instante esta posición. Es necesaria una variable, cima, que apunte al último elemento (ocupado) de la pila. 

Con estas consideraciones prácticas, se puede pasar a definir las operaciones que definen la pila. 
CREAR PILA:

Es necesario definir el array que permitirá almacenar la información y la variable que indica la posición de la cima. Además tendremos que inicializar cima al valor 0, indicando que la creación implica que la pila está vacía. 
(1) Variables 
(2)   Pila: array [1..n] de T
(3) cima: 0..n 
(4) (2) Asignación de pila vacía 
(5)   cima <-- 0 

COMPROBAR SI LA PILA ESTÁ VACÍA: 

Esta operación permitirá determinar si es posible eliminar elementos. 
ALGORITMO PILA_ VACIA
   
Entrada
    cima: 0..n

   Salida (cierto, falso)

   Inicio
     si cima=0 entonces devolver(cierto)
     sino devolver(falso)
   Fin 

OPERACIÓN DE INSERCIÓN

La operación de inserción normalmente se conoce por su nombre inglés push. La operación aplicada sobre una pila y un valor x, inserta x en la cima de la pila. Esta operación está restringida por el tipo de representación escogido. En este caso, la utilización de un array implica que se tiene un numero máximo de posibles elementos en la pila, por lo tanto, es necesario comprobar, previamente a la inserción, que realmente hay espacio en la estructura para almacenar un nuevo elemento. Con esta consideración el algoritmo de inserción sería:

ALGORITMO APILAR

   Entradas
    x: T (* elemento que se desea insertar *)
    Pila: array [1..n] de T

   Salidas
    Pila, cima

   Inicio
    si cima=n entonces "Pila llena"
    sino
       cima       <-- cima+1
       Pila[cima] <-- x
    fin_sino
   Fin 

OPERACIÓN DE ELIMINACIÓN

La operación de borrado elimina de la estructura el elemento situado en la cima. Normalmente recibe el nombre de pop en la bibliografía inglesa. El algoritmo de borrado sería: 
ALGORITMO DESAPILAR

   Entradas
    Pila: array [1..n] de T

   Salidas
    Pila, cima, x

   Inicio
    si NO(Pila_vacia) entonces
       x    <-- Pila[cima]
       cima <-- cima-1
   Fin 

(recordemos que la función Pila_vacia nos devuelve un valor lógico (cierto o falso) que en este caso nos sirve como condición para el si) 
En todos los algoritmos se podría suponer que las variables Pila y cima, lo mismo que n, son globales y, por lo tanto, no sería necesario declararlas como entradas o salidas. 

Vamos a ver un ejemplo de utilización de pilas:

<?php 
$dias = array ("lunes", "martes", "miercoles", "jueves", "viernes", "sabado", "doningo");
$dia_error = array_pop($dias);
array_push($dias,"domingo");
?>

En este ejemplo lo que hacemos es arreglar un array que tiene el último elemento equivocado, para eso, extraemos el último elemento "doningo" y lo guardamos como $error_dia, luego agregamos el elemento correcto y la pila queda corregida.

Este ejemplo no seria un buen ejemplo de funcionalidad de las pilas pues se podria realizar lo mismo sin nescesidad de pilas.

Pero vamos a ver un ejemplo que no podremos realizar tan facilmente sin pilas. imaginemos que tenemos un vector de dias de la semana y queremos imprimirlos en orden opuesto, como la pila extrae por detrás, los elementos salen en orden opuesto, y como se va vaciando, solo necesitaremos hacer un while(count($dias) != 0) o lo que es lo mismo while(count($dias)).

<? php
$dias = array ("lunes", "martes", "miercoles", "jueves", "viernes", "sabado", "domingo");
while(count($dias))echo array_pop($dias)."<br />";
?>


COLAS  

  Las colas son secuencias de elementos caracterizadas porque las operaciones de inserción y borrado se realizan sobre extremos opuestos de la secuencia. La inserción se produce en el "final" de la secuencia, mientras que el borrado se realiza en el otro extremo, el "inicio" de la secuencia. 
   
Las restricciones definidas para una cola hacen que el primer elemento que se inserta en ella sea, igualmente, el primero en ser extraido de la estructura. Si una serie de elementos A, B, C, D, E se insertan en una cola en ese mismo orden, entonces los elementos irán saliendo de la cola en el orden en que entraron. Por esa razón, en ocasiones, las colas se conocen con el nombre de listas FIFO (First In First Out, el primero que entra es el primero que sale). 
   
Las colas, al igual que las pilas, resultan de aplicación habitual en muchos problemas informáticos. Quizás la aplicación más común de las colas es la organización de tareas de un ordenador. En general, los trabajos enviados a un ordenador son "encolados" por éste, para ir procesando secuencialmente todos los trabajos en el mismo orden en que se reciben. Cuando el ordenador recibe el encargo de realizar una tarea, ésta es almacenada al final de la cola de trabajos. En el momento que la tarea que estaba realizando el procesador acaba, éste selecciona la tarea situada al principio de la cola para ser ejecutada a continuación. Todo esto suponiendo la ausencia de prioridades en los trabajos. En caso contrario, existirá una cola para cada prioridad. Del mismo modo, es necesaria una cola, por ejemplo, a la hora de gestionar eficientemente los trabajos que deben ser enviados a una impresora (o a casi cualquier dispositivo conectado a un ordenador). De esta manera, el ordenador controla el envio de trabajos al dispositivo, no enviando un trabajo hasta que la impresora no termine con el anterior. 
  
Análogamente a las pilas, es necesario definir el conjunto de operaciones básicas para especificar adecuadamente una estructura cola. Estas operaciones serían: 
Crear una cola vacía. 
Determinar si la cola está vacía, en cuyo caso no es posible eliminar elementos. 
Acceder al elemento inicial de la cola. 
Insertar elementos al final de la cola. 
Eliminar elementos al inicio de la cola. 
   
Para determinar correctamente cada una de estas operaciones, es necesario especificar un tipo de representación para las colas. 


     Este tipo de estructuras se caracteriza porque insertamos los elementos por un lado y los extraemos por el otro lado. Es de tipo FIFO ( First In First Out ), el primer elemento en entrar es el primero en salir. Para gestionar la cola utilizaremos 3 punteros (para la pila solo eran necesarios 2)

REPRESENTACIÓN DE LAS COLAS

La representación de una cola finita en forma de vector es una tarea algo más compleja que la realizada para el caso de las pilas. Además de un array unidimensional, son necesarias un par de variables que indiquen dónde está el inicio de la cola y dónde el final.  Hay diferentes formas de implementar las operaciones relacionadas con colas pero una de las más eficientes es representar el array Cola[1..n] como si fuese circular, es decir, cuando se dé la condición de cola llena se podrá continuar por el principio de la misma si esas posiciones no estan ocupadas.  Con este esquema de representación, se puede pasar a especificar el conjunto de operaciones necesarias para definir una cola circular. 

CREAR COLA:

Esta operación consistirá en definir la variable de tipo array que permitirá almacenar la información y las variables que apuntarán a los extremos de la estructura. Además, hay que indicar explícitamente que la cola, trás la creación, está vacía. 

(1) Declaraciones: 
  Cola : array [1..n] de T 
   inicio, fin: 1..n 

(2)Cola vacía:

   inicio <-- 1
   fin    <-- 1 

COMPROBAR SI LA COLA ESTÁ VACÍA:

Con las condiciones establecidas, basta comprobar si inicio = fin:

 si Cola.inicio = Cola.fin entonces devolver(cierto)
 sino devolver(falso)

FUNCIÓN SIGUIENTE:
Con esta función obtenemos el índice del siguiente elemento a i, se trata de calcular el resto de ese i entre el máximo índice de la cola, algo así: (Siguiente := i MOD n + 1). 

Todo esto es necesario porque como hemos dicho antes Cola.inicio y Cola.fin son 1 cuando la Cola está vacia, por tanto el primer elemento nunca estará en el valor de Cola.inicio sino en el de Siguiente(Cola.inicio). 

ACCEDER AL ELEMENTO INICIAL DE LA COLA:

Es importante poder acceder fácilmente al inicio de la cola; para ello se puede crear una función para tal propósito. 

 si Vacia(Cola) entonces "Error. Cola vacía."
 sino devolver (Cola.info[Siguiente(Cola.inicio)])

INSERTAR UN ELEMENTO EN LA COLA:

Debido a la implementación estática de la estructura cola es necesario determinar si existen huecos libres donde poder insertar antes de hacerlo. Esto puede hacerse de varias formas:

si Cola.inicio = Siguiente(Cola.fin) entonces "Error. Cola llena."
sino
   incrementar(Cola.fin)
   Cola.info[Cola.fin] <-- x
Fin_sino

O incrementando antes y luego comparando que 'Cola.inicio' sea igual a 'Cola.fin'. 

ELIMINAR UN ELEMENTO DE LA COLA:
Como puedes ver la eliminación no borra nada 'físicamente', sólo se encarga de actualizar el puntero 'Cola.inicio' en una posición y devolver el valor x como mucho, aunque esto último no sea estrictamente necesario. Aunque esa posición aun contenga datos será considerada como vacía a efectos del otro puntero 'Cola.final'. 

si Vacia(Cola) entonces "Error. Cola vacía."
sino 
   x <-- Primero(Cola)
   incrementar(Cola.inicio)
   devolver(x)
fin_sino

Vamos a ver un ejemplo de utilización de colas:

 <?php
// array_unshift insertar al inicio

$cola = array("A", "B", "C", "D");
echo "</br>Antes de insertar con unshift </br>";
print_r($cola);

array_unshift($cola,"AAAA");
echo "</br></br>Despues de insertar</br>";
print_r($cola);

?>

Aquí les dejo el enlace de un PDF espero que pueda servir es de estructuras Dinámicas de Datos