1

Estructura de datos C# 1 Análisis de algoritmos. Introduccion

Primero que nada debemos saber que el término algoritmo no está exclusivamente relacionado con la matemática, ciencias de la computación o informática. Un algoritmo es un sistema por el cual se llega a una o varias soluciones, teniendo en cuenta que debe ser definido, finito y preciso. Por preciso entendemos que cada paso a seguir tiene un orden; finito implica que tiene un determinado número de pasos, o sea, que tiene un fin; y definido, que si se sigue el mismo proceso más de una vez llegaremos al mismo resultado. En realidad, en la vida cotidiana empleamos algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos son el uso de una lavadora (se siguen las instrucciones), pero no la preparación de una comida (porque no están perfectamente definidos los pasos) o el mismo lenguaje humano que “transforma” nuestros pensamientos en sonidos y hace que otro humano nos pueda entender. También existen ejemplos de índole matemática, como el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para calcular el máximo común divisor de dos enteros positivos, o incluso el método de Gauss para resolver Sistema lineal de ecuaciones.

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.

A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los más usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundos y/o con Mb bytes de memoria? Complejidad de algoritmos

Es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema los cuales se dividen en: el tiempo y el espacio.

Los problemas de decisión se clasifican en conjuntos de complejidad llamadas clases de complejidad:

- Clase de complejidad P:

Es el conjunto de los problemas de decisión que puedan ser resueltos en tiempo polinómico calculado a partir de la entrada por una maquina de turins determinista y que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos. Ejemplo:

1. Saber si un número entero es primo. 2. Saber si una frase pertenece a un conjunto de frases.

2

- Clase de complejidad NP: Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turins

no determinista en tiempo polinómico las cuales tienen la propiedad de que su solución puede ser verificada.

- Clase de complejidad NP-Completo:

Es el subconjunto de los problemas de decisión en NP que destacan por su extrema complejidad y que decimos se hayan en la frontera externa de la clase NP. Notación aritmética

Notación asintótica “O” grande se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrar un limite superior del tiempo de ejecución de un algoritmo es decir el peor caso.

La definición de esta notación es la siguiente:

Una función g(n) pertenece a O(f(n)) si y solo si existen las constantes c y n. tales que:

g(n) < = c · f(n)

Para todo n > = n. y se tiene que T(n) < = cn.

Nota: el orden de magnitud de una función es el orden del término de la función más grande respecto de n.

Notación asintótica “Omega” grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de T(n), y significa que existe una constante c tal que T(n) es mayor o igual a c(g(n)) para un número infinito de valores n. Tiempo de ejecución de un algoritmo

El tiempo de ejecución de un programa en función de N(numero de datos) se denomina T(N) y se calcula sobre el código contando las instrucciones a ejecutar y multiplicando por el tiempo requerido para cada instrucción. Ejemplo:

S1; (sentencia = s) For (int i = 0; i < N; i++)

S2; Requiere: T(N) = t1 + t2 * N

Los algoritmos bien estructurados combinan las sentencias de algunas de las formas siguientes:

A) Sentencias sencillas. Contempla las sentencias de asignación, entrada y salida de datos y tienen una complejidad constante que se establece Orden 1 = O(1).

3

B) Secuencia de sentencias. La complejidad de ella es la suma de las complejidades individuales de cada una de ellas. O(1). C) Decisión (if). Una condición es de complejidad O(1) ya sea en la rama then o en la rama else. D) Decisión multiple (switch case). Se tomara la complejidad de la peor de las ramas. E) Bucles de contador explicito (for). Si se realiza un numero fijo de veces independientemente de N sera el siguiente. Ejemplo: For ( i = 0 ; i < k; i++) {algo de O(1)} K * O(1) = O(1) Dependiendo de N: ejemplo: For (i = 0; i < N; i++) {algo de O(1)} N * O(1) = O(n) F) Ciclos anidados: Ejemplo: For (i = 0; i < N; i++) {For (j = 0; j<N; j++) {algo de O(1)} N * N * O(1) = O(n2) G) Llamada a procedimiento. Su complejidad depende del contenido de las instrucciones que formen el cuerpo del procedimiento. Ejemplo: Int factorial (int n) O(1) entrada { int Fact = 1 O(1) asignación for (int i = N; i > 0; i–) O(n) bucle dependiente de N Fact = Fact * i; O(1) sentencia sencilla Return Fact; O(1) sentencia sencilla } resultado complejidad mayor = O(n) Ordenes de Complejidad:

O(1) Constante Ideal

O(n) Lineal Eficiente

O(log n) Logaritmico Eficiente

O(n log n) Logaritmico Eficiente

4

O(nK) Polinomial Tratable

O(Kn) Exponencial Intratable

O(n!) Factorial Intratable

Complejidad en el espacio

Es la memoria que utiliza un programa para su ejecución; es decir el espacio de memoria que ocupan todas las variables propias del algoritmo.

Esta se divide en Memoria Estática y Memoria Dinámica. Memoria estática. Para calcularla se suma de memoria que ocupan las variables declaradas en el algoritmo. Memoria dinámica. Su cálculo no es tan simple ya que depende de cada ejecución del algoritmo. Ejemplo: algoritmo de búsqueda en arboles. Función búsqueda_arboles. Devuelve una solución o fallo. Inicializa un árbol de búsqueda con estado inicial. Bucle hacer - Si no hay candidatos para expandir. - Entonces devolver fallo. - En otro caso escoger nodo para expandir. - Si el nodo es el objetivo. - Entonces devolver solución. - En otro caso expandir nodo. M = profundidad máxima del árbol (puede ser infinita) D = profundidad de la mejor solución (menor costo) B = factor de ramificacion (numero máximo de sucesiones) = 10

Depth Nodes Time Memory

0 1 1 milisecond 100 bytes

2 111 .1 second 11 Kb

4 11111 11 second 1 Mb

6 1000000 18 minutos 111 Mb

5

2 Manejo de memoria. Manejo de memoria estática

Es la memoria que se reserva en el momento de la compilación antes de comenzar a ejecutar el programa. Los objetos son creados al iniciar el programa y destruidos al finalizar el mismo. Mantienen la misma localizacion en memoria durante todo el transcurso del programa hasta que son destruidos.

Los objetos administrados de este modo son: variables globales, variables estáticas de funciones, miembros static de clases y literales de cualquier tipo.

El inconveniente de la reserva estática es que la cantidad de memoria se reserva siempre antes de conocer los datos concretos del problema.

Tampoco se adapta bien a la memoria real disponible del ordenador en que se esta ejecutando el programa. Las estructuras de datos estáticas:

Son aquellas en las que el tamaño ocupado en memoria se define antes de que el programa se ejecute y no puede modificarse dicho tamaño durante la ejecución del programa.

Estas estructuras están implementadas en casi todos los lenguajes.

Su principal característica es que ocupan solo una casilla de memoria, por lo tanto una variable simple hace referencia a un único valor a la vez, dentro de este grupo de datos se encuentra: enteros, reales, caracteres, boléanos, enumerados y subrangos (los últimos no existen en algunos lenguajes de programación)

La forma más fácil de almacenar el contenido de una variable en memoria en tiempo de ejecución es en memoria estática o permanente a lo largo de toda la ejecución del programa. No todos los objetos (variables) pueden ser almacenados estáticamente. Para que un objeto pueda ser almacenado en memoria estática su tamaño (número de bytes necesarios para su almacenamiento) ha de ser conocido en tiempo de compilación. Como consecuencia de esta condición no podrán almacenarse en memoria estática:

Los objetos correspondientes a procedimientos o funciones recursivas, ya que en tiempo de

compilación no se sabe el número de variables que serán necesarias. Las estructuras dinámicas de datos tales como listas, árboles, etc. ya que el número de

elementos que las forman no es conocido hasta que el programa se ejecuta.

Las técnicas de asignación de memoria estática son sencillas. A partir de una posición señalada por un puntero de referencia se aloja el objeto X, y se avanza el puntero tantos bytes como sean necesarios para almacenar el objeto X. La asignación de memoria puede hacerse en tiempo de

6

compilación y los objetos están vigentes desde que comienza la ejecución del programa hasta que termina.

En los lenguajes que permiten la existencia de subprogramas, y siempre que todos los objetos de

estos subprogramas puedan almacenarse estáticamente -por ejemplo en FORTRAN-IV, como se puede ver en la figura 4a- se aloja en la memoria estática un registro de activación correspondiente a cada uno de los subprogramas.

Estos registros de activación contendrán las variables locales, parámetros formales y valor devuelto por la función. Dentro de cada registro de activación las variables locales se organizan secuencialmente. Existe un solo registro de activación para cada procedimiento y por tanto no están permitidas las llamadas recursivas. El proceso que se sigue cuando un procedimiento p llama a otra q es el siguiente:

1. p evalúa los parámetros de llamada, en caso de que se trate de expresiones complejas, usando para ello una zona de memoria temporal para el almacenamiento intermedio. Por ejemplos, sí la llamada a q es q((3*5)+(2*2),7) las operaciones previas a la llamada propiamente dicha en código máquina han de realizarse sobre alguna zona de memoria temporal. (En algún momento debe haber una zona de memoria que contenga el valor intermedio 15, y el valor intermedio 4 para sumarlos a continuación). En caso de utilización de memoria estática ésta zona de temporales puede ser común a todo el programa, ya que su tamaño puede deducirse en tiempo de compilación.

2. q inicializa sus variables y comienza su ejecución.

Dado que las variables están permanentemente en memoria es fácil implementar la propiedad de que conserven o no su contenido para cada nueva llamada. Manejo de memoria dinámica

Es también llamada almacenamiento libre (freestore) y en estos casos el programador solicita (new) memoria para almacenar un objeto y es responsable de liberarla (delete) para que pueda ser reutilizada por otros objetos.

Es aquella que se reserva en tiempo de ejecución después de leer los datos y de conocer el tamaño exacto del problema a resolver. El sitio donde se almacenan los objetos se le denomina HEAP = MONTÍCULO pero el sitio preciso donde se encuentra tal montículo depende del compilador y el tipo de puntero utilizado en l reserva de memoria dinámica.

Puntero (apuntador): un puntero o apuntador es un tipo especial de variable que almacena el valor de una dirección de memoria la cual puede ser de una variable individual, de un elemento de un arreglo, una estructura u objeto de una clase y se anota de la siguiente manera:

Tipo de apuntador + nombre de la variable. Int * Pint; puntero a un entero.

7

Char * Pchar; puntero de carácter. Fecha * Pfecha; puntero objeto de la clase fecha.

Independientemente del tamaño del objeto apuntado por una variable puntero el valor almacenado por esta sera el de una única dirección de memoria, por este motivo no existen diferencias sintácticas entre punteros a elementos individuales y punteros a elementos a un arreglo o una clase. Sintáxis para requerir y liberar memoria dinámica.

Variable individual Array de elementos

Reserva de memoria int * a = new int; int * a = new int [N];

Liberación de memoria delete a; delete [] a;

3 Estructura de datos. Pilas (stack)

Una pila (stack en inglés) es una estructura de datos de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura. Representación gráfica de una pila

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

Ejemplo Forma principal

8

Procedimiento: Inserción de un elemento en Pila Algoritmo

Insercion(Pila, Cima, Elemento) 1. [¿Pila llena?] Si Cima = MaxPila, entonces: - Escribir: Desbordamiento (Overflow) y Volver Cima = Cima + 1; Pila[Cima] = Elemento

Código void CmdInsercionClick(object sender, EventArgs e) { string elemento = txtElemento.Text; txtElemento.Text = ""; txtElemento.Focus(); if (frmPrincipal.Cima == frmPrincipal.MaxPila) { MessageBox.Show("Pila llena (Overflow)"); return; } frmPrincipal.Cima = frmPrincipal.Cima + 1; frmPrincipal.Pila[frmPrincipal.Cima] = elemento; // Inserta elemento en Pila } Corrida

9

Procedimiento: Recorrido de elementos en Pila Algoritmo

RECORRIDO(Pila, Top) 1. Apuntador = Top 2. repetir paso 3 mientras Apuntador != nulo 3. imprimir Pila(Apunatdor) 4. Apuntador = Apuntador - 1. Fin del ciclo. 5. Salir.

Código void CmdRecorrerClick(object sender, EventArgs e) { // Verifica si la Pila esta vacia if (frmPrincipal.Cima == -1) { MessageBox.Show("Pila Vacia (Underflow)"); return; } int i = 0; do { lsRecorrer.Items.Add(frmPrincipal.Pila[i]); i = i + 1; } while (i <= frmPrincipal.Cima); } Corrida

10

Procedimiento: Búsqueda de un elemento en Pila Algoritmo

BUSQUEDA(Pila, Top, Elemento) 1. Si Top != Nulo Apuntador = Top 2. Repetir mientras Apuntador != Nulo 3. Si Pila[Apuntador] = Elemento Imprimir “El Dato fue encontrado” y Salir Apuntador = Apuntador - 1 Fin del ciclo Si no: Imprimir “El Dato no se encontró” 4. Salir.

Código void CmdBuscarClick(object sender, EventArgs e) { string elemento = txtElemento.Text; txtElemento.Text = ""; txtElemento.Focus(); // Verifica si la pila esta vacia if (frmPrincipal.Cima == -1) { MessageBox.Show("Pila vacia (Underflow)"); return; } int i = 0; do { int res = string.Compare(elemento,frmPrincipal.Pila[i]);

11

if (res == 0) { lsRes.Items.Add(frmPrincipal.Pila[i]); return; } i = i + 1; } while (i <= frmPrincipal.Cima); MessageBox.Show("Elemento no encontrado en Pila"); } Corrida

Procedimiento: Eliminación de elemento en Pila Algoritmo

Eliminar(Pila, Cima, Elemento) 1. [¿Pila Vacía?] Si Cima = -1, entonces: Escribe: Subdesbordamiento (Underflow) 2. Elemento = Pila[Cima] 3. Cima = Cima - 1

Código void CmdEliminarClick(object sender, EventArgs e) { if (frmPrincipal.Cima == -1) { MessageBox.Show("Pila Vacia (Underflow)"); return; } string Elemento = frmPrincipal.Pila[frmPrincipal.Cima]; frmPrincipal.Cima = frmPrincipal.Cima - 1; lsEliminados.Items.Add(Elemento); } Corrida

12

Colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

El tipo cola representa la idea que tenemos de cola en la vida real. La cola para subir al autobús está compuesta de elementos (personas), que dispone de dos extremos comienzo y fin. Por el comienzo se extraerá un elemento cuando haya comprado el billete para su viaje, y si llega una nueva persona con intención de usar el autobús, tendrá que colocarse al final y esperar que todos los elementos situados antes que él abandonen la cola. CODIGO PRINCIPAL public partial class frmPrincipal { // Variables globales public static string[] Cola; public static int Frente; public static int Final; public static int N; [STAThread] public static void Main(string[] args) { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new frmPrincipal()); } public frmPrincipal() // Constructor

13

{ InitializeComponent(); Cola = new string[5]; // Arreglo lineal de 5 N = 4; Frente = -1; Final = -1; } void CmdInsercionClick(object sender, System.EventArgs e) { frmInsercion Insercion = new frmInsercion(); Insercion.Show(); } void CmdRecorridoClick(object sender, System.EventArgs e) { frmRecorrido Recorrido = new frmRecorrido(); Recorrido.Show(); } void CmdBusquedaClick(object sender, EventArgs e) { frmBusqueda Busqueda = new frmBusqueda(); Busqueda.Show(); } void CmdEliminacionClick(object sender, EventArgs e) { frmEliminacion Eliminar = new frmEliminacion(); Eliminar.Show(); } } Corrida

14

Procedimiento 1: Inserción de elemento en Cola Algoritmo Insertar(Cola, N, Frente, Final, Elemento)

1. [¿La Cola esta llena?] Si Frente = 0 y Final = N Escribir: Desbordamiento y Volver Si Frente = Final + 1 Escribir: Desbordamiento y Volver 2. [Encontrar el nuevo valor de Final] Si Frente = -1 , entonces: [La cola esta vacía] Hacer Frente = 0 y Final = 0 Si no, Si Final = N, entonces: Hacer Final = 0 Si no Hacer Final = Final + 1 [Fin del condicional] 3. Hacer Cola[Final] = Elemento

CODIGO void CmdInsertarClick(object sender, System.EventArgs e) { elemento = txtInsercion.Text; // Se verifica que haya espacio en la Cola if (frmPrincipal.Frente == 0 && frmPrincipal.Final == frmPrincipal.N) { MessageBox.Show("La Cola esta llena"); // Desbordamiento (Overflow) return; } if (frmPrincipal.Frente == frmPrincipal.Final + 1) { MessageBox.Show("La Cola esta llena"); // Desbordamiento (Overflow)

15

return; } // Si la cola esta vacia se inicializan punteros if (frmPrincipal.Frente == -1) { frmPrincipal.Frente = 0; frmPrincipal.Final = 0; } else if (frmPrincipal.Final == frmPrincipal.N) { frmPrincipal.Final = 0; } else { frmPrincipal.Final = frmPrincipal.Final + 1; } // Se agrega elemento a la Cola frmPrincipal.Cola[frmPrincipal.Final] = elemento; txtInsercion.Text = ""; } Corrida

Procedimiento 2: Recorrido de elementos en Cola Algoritmo Recorrido (Cola, Frente, Final, N)

1. [¿Cola Vacía?] Si Frente = -1 y Final = -1, entonces Escribir: Cola Vacía (Underflow) 2. Si no, si Frente = Final, entonces: Escribir: Cola[Frente] 3. Si no, si Final < Frente Hacer i = Frente Repetir Mientras i <= N Escribir: Cola[i] Hacer i = i + 1 Hacer j = 0

16

Repetir Mientras j <= Final Escribir: Cola[j] Hacer j = j + 1 4. Si no Hacer i = Frente Repetir Mientras i <= Final Escribir: Cola[i] Hacer i = i + 1

CODIGO void CmdRecorridoClick(object sender, System.EventArgs e) { if (frmPrincipal.Frente == -1 && frmPrincipal.Final == -1) { MessageBox.Show("Cola Vacia"); return; } else if (frmPrincipal.Frente == frmPrincipal.Final) { lsElemCola.Items.Add(frmPrincipal.Cola[frmPrincipal.Frente]); } else if (frmPrincipal.Final < frmPrincipal.Frente) { int i = frmPrincipal.Frente; do { lsElemCola.Items.Add(frmPrincipal.Cola[i]); i = i + 1; } while (i <= frmPrincipal.N); int j = 0; do { lsElemCola.Items.Add(frmPrincipal.Cola[j]); j = j + 1; } while (j <= frmPrincipal.Final); } else { int i = frmPrincipal.Frente; do

17

{ lsElemCola.Items.Add(frmPrincipal.Cola[i]); i = i + 1; } while (i <= frmPrincipal.Final); }

Procedimiento 3: Busqueda de elemento en cola Algoritmo Búsqueda(Elemento, Cola, N, Frente, Final)

1. [¿Cola Vacía?] Si Frente = -1 y Final = -1, entonces Escribir: Cola Vacía (Underflow) 2. Si no, si Frente = Final, entonces: Si Elemento = Cola[Frente] Escribir: Cola[Frente] y Volver 3. Si no, si Final < Frente Hacer i = Frente Repetir Mientras i <= N Si Elemento = Cola[i] Escribir: Cola[i] y Volver Si no Hacer i = i + 1 Hacer j = 0 Repetir Mientras j <= Final Si Elemento = Cola[j] Escribir: Cola[j] y Volver Si no Hacer j = j + 1 4. Si no Hacer i = Frente Repetir Mientras i <= Final Si Elemento = Cola[i]

18

Escribir: Cola[i] y Volver Si no Hacer i = i + 1 5. Escribir: “No se encuentra elemento en cola”

CODIGO void CmdBuscarClick(object sender, EventArgs e) { string elemento = txtBuscar.Text; txtBuscar.Text = ""; txtBuscar.Focus(); if (frmPrincipal.Frente == -1) { MessageBox.Show("Cola Vacía"); return; } if (frmPrincipal.Frente == frmPrincipal.Final) { int res = string.Compare(elemento,frmPrincipal.Cola[frmPrincipal.Frente]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[frmPrincipal.Frente]); return; } } else if (frmPrincipal.Final < frmPrincipal.Frente) { int i = frmPrincipal.Frente; do { int res = string.Compare(elemento,frmPrincipal.Cola[i]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[i]); return; } else i = i + 1; } while (i <= frmPrincipal.N); int j = 0; do {

19

int res = string.Compare(elemento,frmPrincipal.Cola[j]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[j]); return; } else j = j + 1; } while (j <= frmPrincipal.Final); } else { int i = frmPrincipal.Frente; do { int res = string.Compare(elemento,frmPrincipal.Cola[i]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[i]); return; } else i = i + 1; } while (i <= frmPrincipal.Final); } MessageBox.Show("No se encuentra elemento en cola"); }

Procedimiento 4: Eliminación de elemento en cola Algoritmo Eliminación (Cola, Frente, Final, N)

1. [¿Cola Vacía?] Si Frente = -1 entonces

20

Escribir: "Cola Vacía" (Underflow) y Volver 2. Hacer Elemento = Cola[Frente] 3. [Encontrar el nuevo valor de Frente] Si Frente = Final, entonces [La cola solo tenía un elemento] Hacer Frente = -1 y Final = -1 Si no, si Frente = N, entonces Hacer Frente = 0 Si no Hacer Frente = Frente + 1 [Fin de la condición] 4. Escribir: “Elemento eliminado (Elemento)” 5. Volver

Código void CmdEliminarClick(object sender, EventArgs e) { if (frmPrincipal.Frente == -1) { MessageBox.Show("Cola Vacia"); return; } string elemento = frmPrincipal.Cola[frmPrincipal.Frente]; // si la cola tiene un solo elemento if (frmPrincipal.Frente == frmPrincipal.Final) { frmPrincipal.Frente = -1; frmPrincipal.Final = -1; } else if (frmPrincipal.Frente == frmPrincipal.N) { frmPrincipal.Frente = 0; } else { frmPrincipal.Frente = frmPrincipal.Frente + 1; } lsEliminado.Items.Add(elemento); }

21

Listas enlazadas

Una lista enlazada la constituye una colección lineal de elementos, llamados nodos, donde el orden de los mismos se establece mediante punteros. Cada nodo se divide en dos partes: una primera que contiene la información asociada al elemento, y una segunda parte, llamada campo de enlace o campo al siguiente puntero, que contiene la dirección del siguiente nodo de la lista.

Una lista enlazada es una colección lineal de elementos donde el orden de los mismos se establece mediante punteros. La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista.

Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:

Ventajas de usar listas: Las listas son dinámicas, es decir, podemos almacenar en ellas tantos elementos como necesitemos, siempre y cuando haya espacio suficiente espacio en memoria. Al insertar un elemento en la lista, la operación tiene un tiempo constante independientemente de la posición en la que se inserte, solo se debe crear el nodo y modificar los enlaces. Esto no es así en los arreglos, ya que si el elemento lo insertamos al inicio o en medio, tenemos un tiempo lineal debido a que se tienen que mover todos los elementos que se encuentran a la derecha de la posición donde lo vamos a insertar y después insertar el elemento en dicha posición; solo al insertar al final del arreglo se obtienen tiempos constantes. Al eliminar un elemento paso lo mismo que se menciono en el punto anterior.

Desventajas de usar listas: El acceso a un elemento es más lento, debido a que la información no

está en posiciones contiguas de memoria, por lo que no podemos acceder a un elemento con base en su posición como se hace en los arreglos. Representacion de listas enlazadas en memoria

22

Sea LISTA una lista enlazada, salvo que se indique lo contrario. Almacenaremos LISTA en

memoria de la forma siguiente. Como mínimo, LISTA estará compuesta por dos arrays lineales, a los que llamaremos INFO y ENLACE, tales que INFO [K] y ENLACE [K] contienen la parte de información y el campo de puntero de cada nodo de LISTA respectivamente. Necesitamos también una variable especial llamada COMIENZO que contiene la posición ocupada por el primer elemento de la lista, y una marca especial NULO que indica el final de la misma. Puesto que los índices de los arrays INFO y ENLACE serán habitualmente positivos, el valor NULO será el -999, salvo que digamos lo contrario.

El siguiente ejemplo muestra la representación memoria de una lista enlazada en la que cada nodo de la lista contiene un único carácter. Podemos obtener la lista de caracteres o, en otras palabras, la cadena de la forma siguiente:

COMIENZO = 9, luego INFO [9] = N primer carácter. ENLACE [9] = 3, luego INFO [3] = 0 segundo carácter. ENLACE [3] = 6, luego INFO [6] = (carácter blanco) tercer carácter. ENLACE [6] = 11, luego INFO [11] = E cuarto carácter. ENLACE [11] = 7, luego INFO [7] = X quinto carácter. ENLACE [7] = 10, luego INFO [10] = I sexto carácter. ENLACE [10] = 4, luego INFO [4] = T séptimo carácter. ENLACE [4] = -999 valor nulo, luego termina la lista. Forma principal de la lista enlazada Codigo: using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { public partial class Listas : Form { public Listas() { InitializeComponent(); } public static int[] enlace = new int[10] { 2, 3, 4, 0, -999, 6, 7, 8, 9, -999 }; public static string[] alumno = new string[10] { "Jose", "Ana", "Rosa", "Beto", "zeta", "", "", "", "", "" }; public static int comienzo = 1; public static int disponible = 5;

23

private void cmdInsercion_Click(object sender, EventArgs e) { Insercion ins = new Insercion(); ins.Show(); } private void cmdRecorrido_Click(object sender, EventArgs e) { Recorrer rec = new Recorrer(); rec.Show(); } private void cmdBusqueda_Click(object sender, EventArgs e) { Busqueda bus = new Busqueda(); bus.Show(); } private void cmdEliminacion_Click(object sender, EventArgs e) { Eliminacion eli = new Eliminacion(); eli.Show(); } } }

Corrida Recorrido de una lista enlazada

Sea la lista enlazada, almacenada en memoria mediante dos arrays INFO y ENLACE. Adicionalmente definimos la variable COMIENZO que apunta al primer elemento de la lista y suponemos que el último nodo de la lista contiene en su campo ENLACE el valor NULO. Supongamos que queremos recorrer LISTA para procesar cada uno de sus nodos exactamente una vez. A continuación te mostrare el algoritmo que realiza esta tarea y que utilizaremos en otras aplicaciones.

Nuestro algoritmo utiliza una variable puntero PTR que apunta siempre al nodo procesado en cada momento. Por ello ENLACE [PTR] indica el siguiente nodo a ser procesado. De esta forma la asignación PTR:= ENLACE [PTR] Tiene el efecto de mover el puntero al siguiente nodo de la lista.

La descripción del algoritmo es la siguiente. Inicializamos PTR a COMIENZO. A continuación procesamos INFO [PTR], es decir, la información del primer nodo. En el paso siguiente actualizamos PTR mediante la asignación PRT: = ENLACE [PTR], lo que hace que PTR apunte ahora al segundo nodo.

24

Nuevamente tratamos de la información contenida en INFO [PTR] (segundo nodo) y tras esto volvemos a actulizar PTR y procesamos INFO [PTR], y asi sucesivamente. Este proceso de actualizacion y procesamiento continuara hasta que en una de las actualizaciones de PTR obtengamos que PTR = NULO, que marca el final de la lista.

Una representación formal de algoritmo es la siguiente. Algoritmo: Recorrido de una lista enlazada.

Sea LISTA una lista enlazada que almacenamos en memoria. El algoritmo recorre LISTA realizando la operación PROCESO a cada elemento de LISTA. La variable PTR, apunta en cada momento al nodo que se esta tratando.

1. PTR: = COMIENZO. [inicializa el puntero]. 2. repetir pasos 3 y 4 mientras PTR != 0. 3. aplicar PROCESO a INFO [PTR]. 4. PTR: = ENLACE [PTR]. [PTR apunta ahora al siguiente nodo]. [fin del ciclo paso 2]. 5. salir.

Codigo: using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { public partial class Recorrer : Form { public Recorrer() { InitializeComponent(); Recorrido(); } private void cmdRecorrer_Click(object sender, EventArgs e) { listBox1.Items.Clear(); Recorrido(); } private void Recorrido()

25

{ int ptr = Listas.comienzo; while (ptr != -999) { listBox1.Items.Add(Listas.alumno[ptr]); ptr = Listas.enlace[ptr]; } } private void button1_Click(object sender, EventArgs e) { this.Close(); } } } Corrida

Búsqueda en una lista enlazada

Sea LISTA una lista enlazada, almacenada en memoria. En esta seccion discutimos dos algoritmos de búsqueda que localizan la posición del nodo (LUG) en el cual un elemento dado (ELEMENTO) aparece por primera vez en la lista. El primer algoritmo no necesita que la lista este ordenada, mientras que el segundo si lo exige.

Si ELEMENTO es un valor de clave y buscamos en el archivo para encontrar el registro que lo contiene, este solo puede aparecer una vez en la lista. Lista no ordenadas

Supongamos que los datos de lista no estan ordenados (necesariamente). En este caso podremos localizar ELEMENTO sin mas que recorrer LISTA utilizando el puntero PTR y comparando ELEMENTO con el contenido INFO [PTR] de cada nodo. Cada vez que actualicemos PTR mediante la asignación PTR: = ENLACE [PTR], necesitamos dos comprobaciones. Primero necesitamos ver si hemos alcanzado el final de la lista, es decir comprobamos si PTR = NULO, si no, entonces comprobamos si INFO [PTR] = ELEMENTO.

26

Las dos comprobaciones no podemos realizarlas simultáneamente, puesto que si PTR = NULO no existira INFO [PTR]. De acuerdo con esto utilizamos la primera comparación para controlar la ejecución de un ciclo y realizamos la segunda comparación dentro de este. Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

LISTA es una lista enlazada almacenada en memoria. el algoritmo encuentra la posicion LUG del nodo donde ELEMENTO aparece por primera vez en lista y devuelve LUG = NULO.

1. PTR: = COMIENZO. 2. repetir paso 3 mientras PTR != NULO: 3. si ELEMENTO = INFO[PTR], entonces: LUG: = PTR y salir. 4. si no: PTR: = ENLACE [PTR]. [PTR apunta ahora al nodo siguiente]. 5. [final de la estructura condicional]. 6. [final del ciclo del paso 2]. 7. [la busqueda es fallida]. LUG: = NULO. 8. salir

Lista ordenada

Supongamos que los datos de LISTA estan ordenados. de nuevo buscamos ELEMENTO en la lista recorriendo la misma utilizando una variable puntero y comparando ELEMENTO con el contenido de INFO[PTR] nodo a nodo. en este caso, sin embargo, podremos finalizar la busqueda una vez que ELEMENTO sea mayor que INFO[PTR]. Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

LISTA es una lista ordenada que se encuentra en memoria. el algoritmo encuentra la posicion

LUG del nodo donde se encuentra por pirmera vez ELEMENTO o bien devuelve LUG = NULO. 1. PTR:= COMIENZO. 2. repetir paso 3 mientras PTR != NULO: 3. si ELEMENTO < INFO[PTR], entonces: 4. PTR: = ENLACE [PTR]. [PTR apunta al siguiente nodo]. 5. si no, si ELEMENTO = INFO[PTR], entonces: 6. LUG = PTR y salir. [la busqueda es satisfactoria]. 7. si no: LUG: = NULO y salir. [ELEMENTO es mayor que INFO[PTR]]. 8. [final de la estructura condicional] 9. [final del ciclo del paso 2] 10. LUG: = NULO. 11. salir.

Codigo: using System; using System.Collections.Generic; using System.ComponentModel;

27

using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { public partial class Busqueda : Form { public Busqueda() { InitializeComponent(); } private void cmdBuscar_Click(object sender, EventArgs e) { string elemento = txtbuscador.Text.ToString(); int lug = -999; int ptr = Listas.comienzo; if (ptr == -999) MessageBox.Show("Lista vacia", "Error"); while (ptr != -999) { if (Listas.alumno[ptr] == elemento) { lug = ptr; MessageBox.Show("Elemento encontrado en \nposicion: " + lug.ToString(), "Elemento Encontrado"); txtbuscador.Clear(); } else ptr = Listas.enlace[ptr]; } if (lug == -999) MessageBox.Show("Elemento no encontrado", "Error"); } private void button1_Click(object sender, EventArgs e) { this.Hide(); } } } Corrida

28

Inserción en una lista enlazada

Sea LISTA una lista enlazada en la que los nodos A y B ocupan posiciones sucesivas en el orden impuesto en la lista. Supongamos que queremos insertar en ella un nodo N que debe ocupar un lugar entre A y B. Después de la operación el nodo A apuntara al nodo N y este apuntara al nodo B, es decir, el nodo al que apuntaba antes A. Algoritmo de insercion

Tres son las situaciones mas comunes que nos encontraremos cuando insertamos nodos en una lista. Primero cuando queremos insertar un nodo al principio de la lista, segundo cuando queramos insertar un nodo detras de un detreminado, y tercero, cuando insertamos un nodo en una lista previamente ordenada. A continuacion discutimos los algoritmos que llevan a cabo estas tareas suponiendo que la lista esta almacenada en memoria en la forma LISTA(INFO, ENLACE, COMIENZO, DISP) y que la variable ELEMENTO contiene la informacion que debe incorporarse a la lista.

Puesto que nuestros algoritmos de insercion utilizaran nodos de la lista de nodos disponibles, todos ellos deben incluir los siguientes pasos:

Estudiar si existe espacio libre en la lista de espacio disponible. Si no es asi, es decir, si

DISPONIBLE = NULO, el algoritmo debe imprimir el mensaje OVERFLOW. Extraer el primer nodo de la lista de disponible. Si utilizamos la variable Nuevo, esta operacion

puede realizarse mediante dos asignaciones (en este orden) NUEVO: = DISP. DISP: = ENLACE[DISP].

Incorporar la informacion a insertar en el nodo recien obtenido, es decir: INFO[NUEVO] = ELEMENTO.

Insercion al principio de una lista

Supongamos que nuestra lista no esta ordenada ni existe ninguna razon por la cual cualquier nodo que insertemos deba ocupar una determinada posicion. En este caso lo mas sencillo sera insertar el nuevo nodo al comienzo de la misma. Un algoritmo que realiza esta operacion es el siguiente. Algoritmo: INSPRIN(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo coloca ELEMENTO como primer componente de la lista.

29

1. [Overflow] si DISP = NULO, entonces: Escribir: OVERFLOW y salir. 2. [extrae el primer nodo de la lista DISP]. 3. NUEVO: = DISP y DISP: = ENLACE[DISP]. 4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo]. 5. ENLACE[NUEVO]: = COMIENZO. [el nuevo nodo apunta ahora al que ocupa antes la primera

posicion]. 6. COMIENZO: = NUEVO. [COMIENZO apunta ahora al elemento que ocupa la primera posicion de

la lista]. 7. Salir.

Insercion a continuacion de un nodo determinado

Supongamos en este caso que se nos da un valor LUG que o bien representa la localizacion de un nodo A determinado o bien LUG = NULO. El algoritmo siguiente inserta ELEMENTO en la lista a continuacion de A o bien coloca ELEMENTO como primer componente de la lista si LUG = NULO.

Sea N el nuevo nodo (cuya posicion es NUEVO). Si LUG = NULO, entonces el nodo se coloca al comienzo de la lista. En otro caso hacemos que N apunte al nodo B (que originalmente seguia a A). El proceso implica las siguientes operaciones: ENLACE[NUEVO]: = ENLACE[LUG] despues del cual N apunta a B y ENLACE[LUG]: = NUEVO tras el cual A apunta al nodo N. Algoritmo: INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO)

El algoritmo inserta ELEMENTO a continuacion del nodo que ocupa la posicion LUG o coloca

ELEMENTO como primer nodo si LUG=NULO

1. [Overflow] Si DISP = NULO, entonces: escribir: OVERFLOW y salir. 2. [Extrae el primer nodo de la lista de disponibles] 3. NUEVO: = DISP y DISP: = ENLACE[DISP]. 4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo obtenido]. 5. Si LUG = NULO, entonces [Lo inserta como primer nodo]. 6. ENLACE[NUEVO]: = COMIENZO y COMIENZO: = NUEVO. 7. Si no: [Inserta detras del nodo de posicion LUG]. 8. ENLACE[NUEVO]: = ENLACE[LUG] y ENLACE[LUG]: = NUEVO. 9. [Final de la estructura condicional] 10. Salir.

Insercion de una lista enlazada y ordenada

30

Supongamos que queremos insertar ELEMENTO en una lista enlazada y ordenada y que ELEMENTO cumple que INFO(a)<ELEMENTO⇐INFO(b). Por tanto ELEMENTO debe insertarse en un nuevo nodo entre A y B. El procedimiento siguiente calcula la posicion LUG que ocupa el nodo A, es decir, la posicion del nodo que precedera a ELEMENTO en la lista.

Para ello utiliza dos punteros PTR y AUX. Con PTR recorre la lista y va comparando ELEMENTO con INFO[PTR] para todos los nodos que visita. Despues de cada comparacion actualiza el valor de ambos punteros, de tl forma que AUX:= PTR y posteiormente PTR:= ENLACE[PTR]. Con este mecanismo garantizamos que AUX siempre apunta al nodo que precede al que esta siendo apuntado por PTR. El recorrido de la lista continua hast que INFO[PTR] > ELEMENTO, o en otras palabras, la busqueda finaliza cuando ELEMENTO ⇐ INFO[PTR].

Una representacion formal del procedimiento es el siguiente. En dicho procedimiento se comtemplan por separado los casos en que la lista esta vacia o bien cuando ELEMENTO < INFO[COMIENZO] debido a que no precisan el uso de la variable AUX. Procedimiento: ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

El procedimiento encuentra la posicion LUG del ultimo nodo para el que INFO[LUG] < ELEMENTO

o hace LUG = NULO. 1. [¿Lista vacia?] Si COMIENZO = NULO, entonces: LUG = NULO y retornar. 2. [¿caso especial?] Si ELEMENTO < INFO[COMIENZO]. entonces: LUG: = NULO y retornar. 3. AUX: = COMIENZO y PTR: = ENLACE[COMIENZO]. [Inicializamos los punteros]. 4. Repetir pasos 5 y 6 mientras PTR != NULO. 5. Si ELEMENTO < INFO[PTR]. entonces: 6. LUG: = AUX y retornar. 7. [Final de la estructura condicionla]. 8. AUX: = PTR y PTR: = ENLACE[PTR]. [Actualiza los punteros]. 9. LUG: = AUX. 10. Salir.

Despues de esto ya tenemos las herramientas necesarias para diseñar un algoritmo que nos

inserte ELEMENTO en una lista enlazada. Algoritmo: INSERT(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo inserta ELEMENTO en una lista enlazada ordenada.

1. [Utilizamos el procedimiento 6 para encontrar la posicion del nodo que precedera a ELEMENTO.] 2. Llamar ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG) 3. [Utilizaremos el algoritmo 5 para insertar ELEMENTO a continuacion del nodo que ocupa la

posicion LUG.] 4. Llamar INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO) 5. Salir.

Código: using System;

31

using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { public partial class Insercion : Form { public Insercion() { InitializeComponent(); } private void cdmInserta_Click(object sender, EventArgs e) { string elemento = txtInser.Text; txtInser.Clear(); if (Listas.disponible == -999) { MessageBox.Show("Lista llena", "Error", MessageBoxButtons.OK); } else { int anterior = -999; int ptr = Listas.comienzo; int i = 0,nuevo; nuevo = Listas.disponible; bool aux = false; Listas.disponible = Listas.enlace[nuevo]; Listas.alumno[nuevo] = elemento; while (ptr != -999 && aux == false) { if (Listas.alumno[ptr].Length < elemento.Length) { i = Listas.alumno[Listas.comienzo].Length; } else { i = elemento.Length; } int h = 0; for (h=0; h < i; h++) { if (Listas.alumno[ptr][h] == elemento[h]) {} if (Listas.alumno[ptr][h] < elemento[h]) {

32

anterior = ptr; h = i; } else { h = i; aux = true; } } ptr = Listas.enlace[ptr]; } if (anterior == -999) { Listas.enlace[nuevo] = Listas.comienzo; Listas.comienzo = nuevo; } else { Listas.enlace[nuevo] = Listas.enlace[anterior]; Listas.enlace[anterior] = nuevo; } button1.Text = "Cerrar"; } } private void button1_Click(object sender, EventArgs e) { this.Hide(); } } } Corrida

Eliminación de un elemento de una lista enlazada

33

Sea lista una lista enlazada en la cual el nodo N se encuentra entre los nodos A y B. Supongamos que queremos eliminar el nodo N de la lista. La eliminación se produce tan pronto como el puntero de enlace siguiente del nodo A apunte al nodo B. (por ello cuando realizamos eliminaciones debemos almacenar de alguna forma la direccion del nodo que precede al que vamos a borrar.)

Supongamos que la lista enlazada se mantiene en memoria en la forma siguiente:

LISTA(INFO, ENLACE, COMIENZO, DISP)

Cuando eliminamos el nodo N de la lista debemos devolverlo inmediatamente a la lista de espacio disponible. Por facilidad en el proceso esta devolucion se realiza insertando el nodo devuelto al principio de la lista DISP. Observese que esta operación implica cambiar tres punteros de la forma siguiente:

el puntero siguiente del nodo A debe cambiarse para apuntar al nodo B, al que apuntaba

previamente N. el puntero del nodo N se cambia y se le hace apuntar al primer nodo de la lista de nodos

disponibles. El puntero DISP se cambia y pasa de apuntar al antiguo primer nodo de la lista de disponibles

para apuntar a N que sera el nuevo primer nodo.

Existen dos casos especiales que implican actuaciones distintas. Si el nodo N que eliminamos es el primero de la lista, el puntero COMIENZO debera cambiarse para apuntar al nodo B. En cambio, si N es el ultimo de la lista, entonces el puntero A debera ponerse a NULO. Algoritmos de eliminación

Los algoritmos que eliminan nodos de una lista son utilizados en distintas situaciones. En este epígrafe discutiremos dos de ellas. La primera situación es la que implica borrar el nodo siguiente a uno dado. La segunda situación implica borrar un nodo que contiene un determinado elemento. En todos los algoritmos suponemos que la lista enlazada se almacena en memoria de la forma LISTA (INFO, ENLACE, COMIENZO, DISP).

Tambien en todos ellos devolvemos el nodo eliminado a la lista de nodos disponibles, insertandolos al principio de esta. Por ello nuestros algoritmos incluiran las siguientes asignaciones, donde LUG es la posición del nodo N borrado: ENLACE[LUG]: = DISP y DISP: = LUG.

Algunos de nuestros algoritmos pueden borrar o bien el primer elemento de la lista o bien el ultimo. Cualquier algoritmo que haga esto debe analizar primero si existe algun elemento en la lista. Si no existe ningun, si COMIENZO = NULO, el algoritmo imprimira el mensaje UNDERFLOW. Eliminacion del nodo sucesor de uno determinado

34

Sea LISTA una lista enlazada almacenada en memoria. Supongamos que queremos eliminar de LISTA el nodo N que ocupa el lugar LUG y que conocemos el lugar LUGP del nodo que precede a N en la lista o bien si el nodo N es el primer LUG = NULO. El algoritmo siguiente elimina N de la lista. Algoritmo: BOR (INFO, ENLACE, COMIENZO, DISP, LUG, LUGP)

El algoritmo elimina de la lista el nodo N que ocupa la posición LUG, siendo LUGP la posición del

nodo que precede a N o bien LUGP = 0 si N es el primero de la lista.

1. si LUGP = NULO. Entonces: 2. COMIENZO: = ENLACE[COMIENZO]. [Elimina el primer nodo]. 3. Si no: 4. ENLACE[LUGP]: = ENLACE[LUG]. [Elimina el nodo N]. 5. [Final de la estructura condicional]. 6. [Devolvemos el nodo a la lista DISP]. 7. ENLACE[LUG]: = DISP Y DISP: = LUG. 8. Salir.

Eliminacion de un nodo que contiene un determinado elemento de informacion

Sea LISTA una lista enlazada almacenada en memoria. Supongamos que queremos eliminar de la lista el primer nodo N que contenga la informacion ELEMENTO. (Si ELEMENTO es un valor de clave, solo puede contenerlo un unico nodo.) Recuerdese que antes de borrar el nodo N que contiene a ELEMENTO debemos conocer que nodo precede a N en la lista. Por ello veremos previamente un procedimiento que localiza la posicion LUG del nodo N que contiene a ELEMENTO y la posicion LUGP del nodo que precede a N. En el caso de que N sea el primer nodo de la lista, el procedimiento devuelve LUGP = NULO y en caso de que ELEMENTO no se encuentre en la lista devolvera LUG = NULO. (Como puede verse el procedimiento es similar al procedimiento) Procedimiento: ENCB(INFO, ENLACE, COMIENZO, ELEMENTO, LUG, LUGP)

El procedimiento encuentra la posicion LUG del primer nodo N que contiene a ELEMENTO y la

posicion LUGP del nodo anterior a N. Si ELEMENTO no se encuentra en la lista, el procedimiento devuelve LUG = NULO y si ELEMENTO se encuentra en el primer nodo, entonces hace LUGP = NULO.

1. [¿Lista vacia?] Si COMIENZO: = NULO, entonces: 2. LUG: = NULO Y LUGP: = NULO y Retornar. 3. [Final de la estructura condcional]. 4. [¿Se encuentra ELEMENTO en el priemr nodo?] 5. Si INFO[COMIENZO] = ELEMENTO, entonces 6. LUG: = COMIENZO y LUGP = NULO y Retornar. 7. [Final de la estructura condicional]. 8. AUX: = COMIENZO y PTR: = ENLACE[COMIENZO]. [Inicializamos los punteros]. 9. Repetir mientras PTR != NULO. 10. Si INFO[PTR] = ELEMENTO, entonces: 11. LUG: = PTR y LUGP: = AUX y Retornar. 12. [Final de la estructura condicional].

35

13. AUX: = PTR y PTR: = ENLACE[PTR]. [Actualizamos los punteros]: 14. [Final del ciclo]. 15. LUG: = NULO [Busqueda fallida]. 16. Retornar.

El procedimiento recorre la lista utilizando dos punteros PTR y AUX. Con PTR recorremos la lista y

comparamos sucesivamente ELEMENTO con INFO[PTR]. En cada momento AUX apunta al nodo anterior al apuntado por PTR. Por ello despues de cada fallida actualizamos ambas de la siguiente forma: AUX: = PTR y PTR: = ENLACE[PTR]

El recorrido de la lista continua mientras que INFO[PTR] != ELEMENTO o, en otras palabras, la busqueda termianra cuando INFO[PTR]=ELEMENTO. En este momento PTR = LUG o direccion del nodo N buscado y AUX apuntara al nodo anterior.

La formalizacion de este procedimieno se establece a continuacion. En ella se puede observar que se tratan por separado los casos en que la lista esta vacia y el caso en que N es el primer nodo. Esto se hace asi debido a que ambos casos no precisan la utilizacion de la variable AUX.

Despues de desarrollar este procedimiento estamos en condiciones de diseñar un algoritmo muy sencillo que elimina de una lista enlazada aquel nodo N en el que aparece por primera vez la informacion ELEMENTO. La simplicidad de este algoritmo estriba en que la localizacion de N y de su prodecesor pueda realizarse utilizando el procedimiento anterior. Algoritmo: ELIMINAR(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo elimina de la lista enlazada el primer nodo N que contiene la informacion

ELEMENTO.

1. [Utilizamos el procedimiento anterior para encontrar la posicion de N y su predecesor en la lista.] 2. Llamar ENCB(INFO, ENLACE, COMIENZO, ELEMENTO, LUG, LUGP). 3. Si LUG: = NULO, entonces: Escribir: ELEMENTO no se encuentra en la lista y salir. 4. [Eliminamos el nodo]. 5. Si LUGP = NULO, entonces: 6. COMIENZO: = ENLACE[COMIENZO]. [Eliminamos el primer nodo]. 7. Si no: 8. ENLACE[LUGP]: = ENLACE[LUG]. 9. [Final de la estructura condicional]. 10. [Devolvemos el nodo eliminado a la lista de nodos disponibles]. 11. ENLACE[LUG]: = DISP y DISP: = LUG. 12. Salir.

Código: using System;

36

using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { public partial class Eliminacion : Form { public Eliminacion() { InitializeComponent(); } private void cmdEliminar_Click(object sender, EventArgs e) { string elemento = txtdato.Text; int aux, lug = -999, lugp = 0, ptr; txtdato.Clear(); if (Listas.comienzo == -999) { lug = -999; lugp = -999; MessageBox.Show("La lista esta vacia", "Error"); return; } if (Listas.alumno[Listas.comienzo] == elemento) { lug = Listas.comienzo; lugp = -999; Listas.comienzo = Listas.enlace[Listas.comienzo]; } else { aux = Listas.comienzo; ptr = Listas.enlace[Listas.comienzo]; while (ptr != -999) { if (Listas.alumno[ptr] == elemento) { lug = ptr; lugp = aux; } aux = ptr; ptr = Listas.enlace[ptr]; } }

37

if (lug == -999) { MessageBox.Show("Elemento no encontrado", "Error", MessageBoxButtons.OK); return; } if (lugp == -999) { Listas.comienzo = Listas.enlace[Listas.comienzo]; } else { Listas.enlace[lugp] = Listas.enlace[lug]; } Listas.enlace[lug] = Listas.disponible; Listas.disponible = lug; MessageBox.Show("Elemento borrado", "Proceso Completado"); button1.Text = "Cerrar"; } private void button1_Click(object sender, EventArgs e) { this.Close(); } } } Corrida

4 Recursividad.

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una funcion desde la misma funcion. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * …, incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

El siguiente parrafo muestra una función, expresada con palabras, que calcula un factorial. “Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero.

Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato.”

Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.

38

La recursividad es un concepto importante en informatica. Muchos algoritmos se pueden describir mejor en terminos de recursividad.

Supongamos que P es un procedimiento que contiene una sentencia de Llamada a si mismo o una sentencia de Llamada a un segundo procedimiento que puede eventualmente llamar de vuelta al procedimiento original P. Entonces P se dice que es u procedimiento recursivo. Como el progrma no ha de continuar ejecutandose indefinidamente, un procedimiento recursivo ha de tener las dos siguientes propiedades:

(1) Debe existir un cierto criterio, llamado criterio base, por el que el procedimiento no se

llama asi mismo.

(2) Cada vez que el procedimiento se llame a si mismo (directa o inderectamente), debe estar mas cerca del criterio base.

Un procedimiento recursivo con estas dos propiedades se dice que esta bien definido.

Similarmente, una funcion se dice que esta definida recursivamente si la definicion de la funcion

se refiere a si misma. De nuevo, para que la definicion no sea circular, debe tener las dos siguientes propiedades:

(1) Debe haber ciertos argumentos, llamados valores base, para los que la funcion no se

refiera a si misma.

(2) Cada vez que la funcion se refiera a si misma, el argumento de la funcion debe acercarse mas al valor base.

Una funcion recursiva con estas dos propiedades se dice tambien que esta bien definida.

Tipos.

Podemos distinguir dos tipos de recursividad:

Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente. Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros. Características.

Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y un acondición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación. Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.

39

Ventajas e inconvenientes. La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta. El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una funcion desde la misma funcion. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * …, incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

El siguiente parrafo muestra una función, expresada con palabras, que calcula el factorial de un número.

“Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato.”

Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.

La recursividad es un concepto importante en informatica. Muchos algoritmos se pueden describir mejor en terminos de recursividad.

Supongamos que P es un procedimiento que contiene una sentencia de Llamada a si mismo o una sentencia de Llamada a un segundo procedimiento que puede eventualmente llamar de vuelta al procedimiento original P. Entonces P se dice que es u procedimiento recursivo. Como el progrma no ha de continuar ejecutandose indefinidamente, un procedimiento recursivo ha de tener las dos siguientes propiedades:

(1) Debe existir un cierto criterio, llamado criterio base, por el que el procedimiento no se llama asi mismo. (2) Cada vez que el procedimiento se llame a si mismo (directa o inderectamente), debe estar más cerca del criterio base.

Un procedimiento recursivo con estas dos propiedades se dice que esta bien definido.

Similarmente, una funcion se dice que esta definida recursivamente si la definicion de la funcion

se refiere a si misma. De nuevo, para que la definicion no sea circular, debe tener las dos siguientes propiedades:

40

(1) Debe haber ciertos argumentos, llamados valores base, para los que la funcion no se refiera a si misma.

(2) Cada vez que la funcion se refiera a si misma, el argumento de la funcion debe acercarse más al valor base.

Una funcion recursiva con estas dos propiedades se dice tambien que esta bien definida.

Tipos.

Podemos distinguir dos tipos de recursividad:

Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente. Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.

Características.

Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y un acondición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación. Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.

Ventajas e inconvenientes. La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta. El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables. Ejemplo: using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { public partial class Recursividad : Form {

41

public Recursividad() { InitializeComponent(); } double r; int fin = 0; private void button1_Click(object sender, EventArgs e) { fin = int.Parse(textBox4.Text.ToString()); listBox1.Items.Clear(); listBox1.Items.Add("x\ty"); evaluar(); } //Procedimiento recusivo public void evaluar() { while (fin <= int.Parse(textBox5.Text.ToString())) { r = int.Parse(textBox1.Text.ToString()) * (fin * fin) + int.Parse(textBox2.Text.ToString()) * fin + int.Parse(textBox3.Text.ToString()); listBox1.Items.Add(fin.ToString() + "\t" + r.ToString()); fin++; evaluar(); } } } } Introducción.

Un procedimiento o función recursiva es aquella que se llama así misma. Esta característica permite a un procedimiento recursivo repetirse valores diferentes de parámetros. La recursion es una alternativa a la iteración muy elegante en la solución de problemas, especialmente si estos tienen naturaleza recursiva.

Normalmente, una solución recursiva es menos eficiente en términos de tiempo de computadora que una solución iterativa debido al tiempo adicional de llamada a procedimientos.

En muchos casos, la recursion permite especificar una solución mas simple y natural para resolver un problema que en otro caso seria difícil. Por esta razón la recursion (recursividad) es una herramienta muy potente para la resolución de problemas de programación.

Un objeto recursivo es aquel que forma parte de si mismo. Esta idea puede servir de ayuda para la definición de conceptos matematicos. Asi, la definición del conjunto de los numeros naturles es aque conjunto en el que se cumplen las siguientes caracteristicas:

42

0 es un número natural.

El siguiente número de un número natural es otro número natural.

Mediante una definición finita hemos representado un conjunto infinito.

El concepto de la recursividad es muy importante en programación. La recursividad es una herramienta muy eficaz para resolver diversos tipos de problemas existen muchos algoritmos que se describiran mejor en terminos recursivos.

Dentro de la teoría de la recursión, se tiene que existen diferentes tipos de recursión:

Recursión directa. Cuando el código F tiene una sentencia que involucra a F.

Recursión indirecta o cruzada.- Cuando la función F involucra una función G que invoca a la ves una función H, y así sucesivamente, hasta que se involucra la función F. Por ejemplo el algoritmo de Par o impar.

int par (int n) { if (n==0) return n+1; return impar(n-1); int impar(int n) if (n==0) return 0; return par(n-1); }

A continuación se expone otro ejemplo de programa que utiliza recursión indirecta, y nos dice si un número es par o impar. Cabe mencionar que existen otros métodos mucho más sencillos para determinar la solución a este problema, basta con determinar el resto de la división entre dos. Por ejemplo: si hacemos par(2) devuelve 1 (cierto). Si hacemos impar(4) devuelve 0 (falso). int par(int n); int impar(int n); int par(int n) { if (n == 0) return 1; return impar(n-1); } int impar(int n) { if (n == 0) return 0; return par(n-1); }

Recursión simple.- Aquella en cuya función solo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iteractivos.

43

Recursión múltiple.- Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de transformar a iteractiva. Poe ejemplo el algoritmo de Fibonacci.

int fibo(int n) { if (n<=1) return 1 return fibo(n-1) + fibo(n-2) }

Recursión anidada.- En algunos de los argumentos de la llamada hay una nueva llamada a sí misma. Por ejemplo la función de Ackerman:

int Ack(int m, int n) { if (m==0) return n+1 if (n=00) return Ack(n-1, 1) return Ack(m-1, Ack(m, n-1)); }

Un requisito para que un algoritmo recursivo sea correcto es que no genere una secuencia infinita de llamadas sobre sí mismo. Cualquier algoritmo que genere una secuencia de este tipo no terminará nunca. En consecuencia, la definición recursiva debe incluir un componente base (condición de salida) en el que f(n) se define directamente (es decir, no recursivamente) para uno o más valores de n. Debe existir una <> de la secuencia de llamadas recursivas.

Al estar trabajando con recursividad, la memoria de la computadora hace uso de una pila de recursión, la cual se divide de manera lógica en 4 segmentos:

1. Segmento de código.- Parte de la memoria donde se guardan las instrucciones del programa en

código máquina. 2. Segmento de datos.- Parte de la memoria destinada a almacenar las variables estáticas. 3. Montículo.- Parte de la memoria destinada a las variables dinámicas. 4. Pila de programa.- parte destinada a las variables locales y parámetros de la función que está

siendo ejecutada.

44

Funciones mutuamente recursivas.- Cuando se trabaja llamados a la ejecución de las funciones, se provocan las siguientes operaciones:

1. Reservar espacio en la pila para los parámetros de la función y sus variables locales. 2. Guardar en la pila la dirección de la línea de código desde donde se ha llamado a la función. 3. Almacenar los parámetros de la función y sus valores de pila. 4. Al terminar la función, se libera la memoria asignada en la pila y se vuelve a la instrucción actual.

Pero cuando se trabaja con funciones recursivas, se provoca además lo siguiente:

1. La función se ejecutará normalmente hasta la llamada a sí misma. En ese momento se crean en la pila nuevos parámetros y variables locales.

2. El nuevo ejemplar de función comienza a ejecutarse. 3. Se crean más copias hasta llegar a la primera llamada (ultima en cerrarse).

La ciencia de la computación hace tiempo que descubrió que se puede reemplazar a un método

que utiliza un bucle para realizar un cálculo con un método que se llame repetidamente a sí mismo para realizar el mismo cálculo. El hecho de que un método se llame repetidamente a sí mismo se conoce como recursion.

La recursión trabaja dividiendo un problema en subproblemas. Un programa llama a un método con uno o más parámetros que describen un problema. Si el método detecta que los valores no representan la forma más simple del problema, se llama a sí mismo con valores de parámetros modificados que describen un subproblema cercano a esa forma.

Esta actividad continúa hasta que el método detecta la forma más simple del problema, en cuyo caso el método simplemente retorna, posiblemente con un valor, si el tipo de retorno del método no es void. La pila de llamadas a método empieza a desbobinarse como una llamada a método anidada para ayudar a completar una evaluación de expresión. En algún punto, la llamada el método original se completa, y posiblemente se devuelve un valor.

Recursión infinita.- La iteración y la recursión pueden producirse infinitamente. Un bucle infinito ocurre si la prueba o test de continuación del bucle nunca se vuelve falsa.

Una recursión infinita ocurre si la etapa de recursión no reduce el problema en cada ocasión de

modo que converja sobre el caso base o condición de la salida.

En realidad, larecursión infinita significa que cada llamada recursiva produce otra llamada recursiva y esta a su vez otra llamada recursiva, y así para siempre. En la práctica, dicha función se ejecutará hasta que la computadora agote la memoria disponible y se produzca una terminación anormal del programa.

El flujo de control de una función recursiva requiere de tres condiciones para una terminación normal.

45

Cuando no utilizar recursividad.

La solucion recursiva de ciertos problemas simplifica mucho la estructura de los programas. Como contrapartida, en la mayoria de los lenguajes de programación las llamadas recursivas a procedimientos o funciones tienen un coste de tiempo mucho mayor que sus homologos iterativos. Se puede, por lo tanto, afrimar que la ejecución de un programa recursivo va a ser más lenta y menos eficiente que el programa iterativo que soluciona el mismo problema, aunque, a veces, la sencilles de la estructura recursiva justifica el mayor tiempo de ejecucion.

Los procedimientos recursivos se pueden convertir en no recursivos mediante la introducción de una pila y asi emular las llamadas recursivas. De esta manera se puede eliminar la recursion de aquellas partes de los programas que se ejecutan más frecuentemente. Ejemplo de mecánica de la recursividad Las torres de Hanoi Algoritmo para trasladar la torre 1…n del poste X al poste Z, usando como auxiliar el poste Y. Si n = 1, lleva el disco 1 de X a Z y termina. Traslada la torre 1…n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z. Lleva el disco n de X a Z. Traslada la torre 1…n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X. Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. Si eres como yo tendrás que implementarlo en un lenguaje de programación concreto para convencerte de que funciona. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1…n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos. Se cumple para n = 1 M3(1) = 1 = 21−1. Si se cumple para n, se cumple para d+1 Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así que M3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1. Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.

Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser «poco económicos», en el sentido de que consumen bastante memoria (y es que ellos también necesitan «tomar notas»). La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce

46

una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples. Tranformar algoritmos recursivos a iterativos

El concepto de recursividad va ligado al de repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos, que hacen uso de ciclos while, do-while, for, etc.

Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado. Ejemplo: definición de nº natural: → El N º 0 es natural → El Nº n es natural si n-1 lo es.

En un algoritmo recursivo distinguimos como mínimo 2 partes:

a. Caso trivial, base o de fin de recursión: Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.

b. Parte puramente recursiva: Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.

CODIGO RECURSIVO using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { public partial class Form1 : Form { class cap_recursivo { public float capital(float m, int n, float x) {

47

if (n == 0) { return m; } else { return capital(m, n - 1, x) * (1 + (x/100)); } } } public Form1() { InitializeComponent(); private void Form1_Load(object sender, EventArgs e) { } private void button1_Click(object sender, EventArgs e) { cap sayo = new cap(); label4.Text = int.Parse(sayo.capital()); } private void label4_Click(object sender, EventArgs e) { } } } DISEÑO

CODIGO ITERATIVO using System; using System.Collections.Generic;

48

using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication7 { public partial class Form1 : Form { class cap { public float capital(float m, int n, float x) { if (n == 0) { return m; } else { //x = x / 100;float inn; //x = x * m; x = x / 100; for (int b = n; b > 0; b--) { m = m + (x * m); //m = x + m; //n = n - 1;(m ) + } } return m; //return capital(m, n - 1, x) * (1 + (x / 100)); } } } public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { } private void button1_Click(object sender, EventArgs e)

49

{ cap sayo = new cap(); label4.Text = int.Parse(sayo.capital()); } private void label4_Click(object sender, EventArgs e) { } } }

DISEÑO EXPLICACION

Este programa lo que hace es calcular el interes de un monto inicial de acuerdo a cuanto se pidio

prestado, a cuanto porcentaje de interes y el tiempo por el que fue prestado. Al pasar el primer año, se calcula el monto inicial + interes = monto total, y al segundo año o mas se calcula el monto total + interes y asi sucesivamente hasta terminar el periodo del prestamo. la forma recursiva se vuelve a llamar, osea que vuelve a hacer el procedimiento dentro de si misma, y la iteraria es de forma seguida y larga. No importa si va primero o despues, los dos tipos llegan al mismo objetivo, son dos diferentes metodos de hacer la misma accion. La recursiva manda a llamar la misma funcion dentro de si misma y iterativo hace todo el trabajo seguido.

50

Recursividad en Diseño

Un procedimiento recursivo es aquel que se llama a si mismo, para poder funcionar tiene que tener una condición de salida que de el numero de veces que se va a llamar a si mismo el procedimiento.

La recursividad en diseño se refiere a la manera de cómo representar los procedimientos recursivos al momento de diseñar los programas.

Dependiendo del método que utilicemos para diseñar la representación grafica de la recursividad va a ser diferente sin embargo el procedimiento va a ser similar ya que el fin es el mismo poner una condición que nos diga si llamamos al método o que nos mande terminarlo. Un ejemplo en una función genérica seria este: METODO1 { Procedimiento x; Condición ( ) { Llamada al metodo1; } Fin; }

En un diagrama seria algo así:

NOTA: Estos son dos ejemplos en ambos utilizamos una condición, pero se pueden utilizar ciclos

siempre asegurándonos de que nos den salida en algún momento.

51

Lo importante y que tenemos que tomar en cuenta es que la si se cumple el criterio para llamar el procedimiento hay que apuntar a el inicio del método, y al no cumplirse debe apuntar al siguiente paso en el procedimiento o al final o viceversa. Ejemplo:

Diseñar un programa que despliegue el contenido de un arreglo el siguiente arreglo: {a, e, i, o, u} Seudo código:

1. Creamos la forma que contendrá una listbox para despliegue. 2. Creamos el arreglo que contendrá los elementos (vocales) 3. Después creamos el método despliegue. El cual contendrá:

a. Un ciclo for (int i=0;i⇐4;i++) dentro del cual se hará el despliegue en el índice i del arreglo vocales

b. llamara al método despliegue. 5. En el constructor mandamos llamar al método despliegue.

Y listo al abrir nuestro programa vamos a desplegar dentro del listbox el arreglo mediante la

recursividad. Para ver un programa visual de recursividad ver el tema recursividad.

Un algoritmo recursivo es un algoritmo que se define en términos de sí mismo. Son implementados en forma de subprogramas (funciones, subrutinas, procedimientos, etc) de tal forma que dentro de un subprograma recursivo hay una o más llamadas a él mismo. FUNCIÓN Factorial(n) INICIO SI (n<2) ENTONCES Factorial = 1; SINO Factorial = n * Factorial(n-1); FIN-SI FIN

Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.

5 Arboles. Concepto de Arbol

Un árbol es una estructura de datos, que puede definirse de forma recursiva como:

52

Una estructura vacía o Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol,

disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol como un tipo de grafo: un árbol es un grafo acíclico, conexo y no

dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta implementación. Nomenclatura sobre arboles Raíz: es aquel elemento que no tiene antecesor; ejemplo: a. Rama: arista entre dos nodos. Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede

llegar a Y. Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X. Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d

tiene grado 0, a tiene grado 2. Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d Nodo interno: aquel que tiene al menos un descendiente. Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel

del nodo a es 1 (es un convenio), el nivel del nodo e es 3. Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3. Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es

3.

Aclaraciones: se ha denominado “a” a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que “b” fuera la raíz, y “a” y “d” los sucesores inmediatos de la raíz “b”. Sin embargo, en las implementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz. Algoritmos

Los Árboles tiene 3 Recorridos Diferentes los cuales son: Pre-Orden In-Orden Post-Orden

53

Pre-Orden Definición:

El Recorrido “Pre-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a través del Nodo Izquierdo y después a través del Nodo Derecho. Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente. Algoritmo:

PreOrd(Arbol, Der, Izq, Pila, Raiz) Temp → Raiz Top → Pila*Top+ → Nulo Si Raiz = Nulo Imprimir “Árbol Vació…” y Salir Repetir mientras Temp ≠ Nulo Imprimir Arbol[Temp] Si Der*Temp+ ≠ Nulo Top → Top + 1 Pila*Top+ → Der*Temp+ Si Izq*Temp+ ≠ Nulo Temp → Izq*Temp+ Si no: Temp → Pila[Top]; Top → Top - 1 Fin del ciclo Salir

In-Orden Definición:

El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después la Raíz y finalmente viaja a través del Nodo Derecho.

54

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente. Algoritmo:

PreOrd(Arbol, Der, Izq, Pila, Raiz) Temp → Raiz Top → Pila*Top+ → Nulo Si Raiz = Nulo Imprmir “Arbol Vacio…” y Salir Etiqueta: Mientras Temp ≠ Nulo Top → Top + 1 Pila*Top+ → Temp Temp → Izq*Temp+ Fin del ciclo Temp → Pila*Top+ Top → Top - 1 Mientras Temp ≠ Nulo Imprimir Arbol[Temp] Si Der*Temp+ ≠ Nulo Temp → Der*Temp+ Ir a Etiqueta Temp → Pila*Top+ Top → Top - 1 Fin del ciclo Salir

In-Orden Definición: El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después el Nodo Derecho y finalmente viaja a través de la Raiz. Detalle: Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente. Algoritmo:

PostOrd(Arbol, Der, Izq, Pila, Raiz)

55

Temp → Raiz Top → Pila*Top+ → Nulo Si Raiz = Nulo Imprimir “Arbol Vacio…” y Salir Etiqueta: Mientras Temp ≠ Nulo Top → Top + 1 Pila*Top+ → Temp Si Der*Temp+ ≠ Nulo Top → Top + 1 Pila*Top+ → - (Der[Temp]) Temp → Izq*Temp+ Temp → Pila*Top+ Top → Top - 1 Fin del ciclo Mientras Temp ≥ 0 Imprimir Arbol[Temp] Si Arbol[Temp] = Info[Raiz] Salir Temp → Pila*Top+ Top → Top - 1 Fin del ciclo Si Temp < 0 Temp = -(Temp) Ir a Etiqueta Salir

Búsqueda Definición: La Búsqueda es Similar a todas los Métodos anteriores de Búsqueda, simplemente efectúa un recorrido comparando el Elemento que deseas encontrar contra cada uno de los Elementos en los Arreglos. Detalle: El Algoritmo de Búsqueda compara el Elemento a buscar con cada uno de los datos de nuestro Árbol, compara si el Elemento con el Nodo Raíz, si no se encuentra en la Raíz… compara Elemento contra la Raíz para empezar a viajar por el Árbol respectivamente, usa un método similar al anterior hasta encontrar el Elemento. De otra forma la búsqueda es fallida. Algoritmo:

Busqueda(Arbol, Der, Izq, Pila, Raiz, Elem) Si Raiz = Nulo Imprimir “Arbol Vacio” Pos → Nulo Pad → Nulo Regresar Pos y Pad

56

Salir Si Elem = Arbol[Raiz] Imprimir “Elemento Encontrado” Pos → Raiz Pad → Nulo Regresar Pos y Pad Salir Si Elem < Arbol[Raiz] Temp → Izq*Raiz+ Temp2 → Raiz Si no: Temp → Der*Raiz+ Temp2 → Raiz Mientras Temp ≠ Nulo Si Elem = Arbol[Temp] Imprimir “Elemento Encontrado…” Pos → Temp Pad → Temp2 Regresar Pos y Pad Salir Si Elem < Arbol[Temp] Temp2 → Temp Temp → Izq*Temp+ Si no: Temp2 → Temp Temp → Der*Temp+ Fin del ciclo Imprimir “Elemento no Encontrado…” Pos → Nulo Pad → Temp2 Regresar Pos y Pad Salir

6 Ordenación interna. Cuestiones generales Su finalidad es organizar ciertos datos (normalmente arreglos o archivos) en un orden creciente o decreciente mediante una regla prefijada (numérica, alfabética…). Atendiendo al tipo de elemento que se quiera ordenar puede ser: Ordenación interna: Los datos se encuentran en memoria (ya sean arreglos, listas, etc.), y son de acceso aleatorio o directo (se puede acceder a un determinado campo sin pasar por los anteriores). Los métodos de ordenación interna se aplican principalmente a arreglos unidimensionales. Los principales algoritmos de ordenación interna son:

57

Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento. Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados. Inserción directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada. Shell: Es una mejora del método de inserción directa, utilizado cuando el arreglo tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1. Intercalación: no es propiamente un método de ordenación, consiste en la unión de dos arreglos ordenados de modo que la unión esté también ordenada. Para ello, basta con recorrer los arreglos de izquierda a derecha e ir cogiendo el menor de los dos elementos, de forma que sólo aumenta el contador del arreglo del que sale el elemento siguiente para el arreglo-suma. Mergesort: Una técnica muy poderosa para el diseño de algoritmos es “Dividir para conquistar”. Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases: • Dividir: Se divide el problema en partes más pequeñas. • Conquistar: Se resuelven recursivamente los problemas más chicos. • Combinar: Los problemas mas chicos de combinan para resolver el grande. Los algoritmos que utilizan este principio son en la mayoría de los casos netamente recursivos como es el caso de mergesort. El algoritmo de Mergesort es un ejemplo clásico de algoritmo que utiliza el principio de dividir para conquistar. Si el vector tiene más de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace una intercalación de las dos mitades ordenadas. Ordenación rápida (quicksort): Este método se basa en la táctica “divide y vencerás”, que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el arreglo. Normalmente se toma como pivote el primer elemento de arreglo, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran. Shell Sort Esta forma de ordenación es muy parecida a la ordenación con burbuja. La diferencia es que usando el metodo de burbuja se realiza una comparación lineal, y shellsort trabaja con una segmentación entre los datos, acomodandolos en un arreglo unidimensional y subsecuentemente ordenando las columnas. Por lo tanto es un buen método, pero no el mejor para implementarlo en grandes arreglos. Este proceso se repite cada vez con un arreglo menor, es decir, con menos columnas, en la ultima repeticion solo tiene una columna, cada que se realiza el proceso se ordena mas los datos, hasta que en su ultima repeticion estan completamente ordenados. Sin embargo el numero de operaciones para

58

ordenar en cada repeticion esta limitado debido al preordenamiento que se obtuvo en las repeticiones anteriores. Algoritmo

void ShellSort(Lista)Lista es un vector que contiene los elementos a ser ordenados. - Declarar variables enteras: i, j, incremento = 3, temp - Repetir mientras incremento > 0: - Repetir mientras i sea menor al tamaño de la Lista - j = i, temp = Lista[i] - Repetir mientras j >= incremento y Lista[j - incremento] > temp - Lista[j] = Lista[j - incremento], j = j - incremento - [fin de ciclo del paso 5] - Lista[j] = temp - [fin de ciclo del paso 3] - si incremento/2 != 0 entonces: - incremento = incremento/2 - si incremento == 1 entonces: - incremento = 0 - si no, entonces: - incremento = 1 - [fin de ciclo del paso 2] - Salir —- Forma principal del programa: Codigo: <code> using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace ShellSort { public partial class Form1 : Form { public static int[] Lista = new int[10]; public static int N = 0; public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { Form2 Recorrer = new Form2(); } private void button2_Click(object sender, EventArgs e) { Form3 Insercion = new Form3(); } private void button3_Click(object sender, EventArgs e) { Form5 Eliminacion = new Form5(); } private void button4_Click(object sender, EventArgs e) { Form4 Busqueda = new Form4(); } private void button5_Click(object sender, EventArgs e) { if (N != 0) { ShellSort(); MessageBox.Show(“La lista ha sido ordenada”, “Exito”, MessageBoxButtons.OK); - else MessageBox.Show(“Lista vacia…”, “Error”, MessageBoxButtons.OK); } public static void ShellSort() { int i, j, incremento = 3, temp; while (incremento > 0) { for (i = 0; i < N; i++) { j = i; temp = Lista[i]; while 1) { Lista[j] = Lista[j - incremento]; j = j - incremento; } Lista[j] = temp; } if (incremento / 2 != 0) incremento = incremento / 2; else if (incremento == 1) incremento = 0; else incremento = 1; } } private void button6_Click(object sender, EventArgs e) { Application.Exit(); } } } </code> Recorrido: Codigo: <code> using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace ShellSort { public partial class Form2 : Form { public Form2() { InitializeComponent(); Recorrido(); } private void Recorrido() { if (Form1.N != 0) { this.Show(); listBox1.Items.Clear(); for (int i = 0; i < Form1.N; i++) listBox1.Items.Add(Form1.Lista[i]); } else , MessageBox.Show(“Lista vacia…”, “Error”, MessageBoxButtons.OK); this.Close(); - - private void button1_Click(object sender, EventArgs e) { this.Close(); } private void button2_Click(object sender, EventArgs e) { Recorrido(); } } } </code> 1) j >= incremento) && (Lista[j - incremento] > temp Ordenamiento de Burbuja Definición. El ordenamiento de burbuja (Bubble Sort), tambien conocido como “método del intercambio directo” es un algoritmo que obtiene su nombre de la forma con la que suben los elemento de una lista, como si fueran “burbujas”. Funciona comparando elementos de dos en dos en un ciclo, intecambiandolos según sea el caso. Es necesario revisar varias veces toda la lista has que no se necesiten más intercambios. Algoritmo (Ordenamiento de Burbuja) i=0,j=0,N=4 ListaNoOrdenada[5] {5,10,1,3,2} Para i desde 0 hasta N Para j desde 0 hasta N Si No_Ordenados(ListaNoOrdenada[j] > ListaNoOrdenada[j + 1] entonces

59

variable_temp = ListaNoOrdenada[j] ListaNoOrdenada[j] = ListaNoOrdenada[j + 1] ListaNoOrdenada[j + 1] = variable_temp FinSi Siguiente i Fin Ejemplo: La idea de este programa es ordenar el arreglo numérico {5,10,1,3,2} de menor a mayor. El ordenamiento de burbuja lo que hace es seleccionar los primeros dos elementos, compararlos, y si el primero es mayor que el segundo, hace el intercambio, el mayor se va a una variable temporal, cediendo su lugar al número menor, y despues pasa a ocupar la posición que ocupaba el otro. El procedimiento se lleva a cabo en un ciclo hasta que verifica todos los números y estan correctamente ordenados. Código using System; using System.Collections.Generic; using System.Drawing; using System.Windows.Forms; namespace BubbleSort { /// <summary> /// Description of MainForm. /// </summary> public partial class frmPrincipal { public int[] ListaNoOrdenada; public int N; [STAThread] public static void Main(string[] args) { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new frmPrincipal()); } public frmPrincipal() { // // The InitializeComponent() call is required for Windows Forms designer support. // InitializeComponent(); ListaNoOrdenada = new int[5] {5,10,1,3,2};

60

N = 4; // // TODO: Add constructor code after the InitializeComponent() call. // } void CmdOrdenarClick(object sender, System.EventArgs e) { Burbuja(ListaNoOrdenada); } void FrmPrincipalLoad(object sender, System.EventArgs e) { //Despliega datos en ListBox for (int i=0; i <= N;i++) { lsNoOrd.Items.Add(ListaNoOrdenada[i]); } } // Procedimiento recibiendo parametros public void Burbuja(int[] LNO) { // Variables int i, j; int temp; // N Pasadas for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { // Comparando parejas de numeros if (LNO[j] > LNO[j + 1]) { // Asignando valores ordenados temp = LNO[j]; LNO[j] = LNO[j + 1]; LNO[j + 1] = temp;

61

} } } // Despliega datos en ListBox for (int c=0; c <= N;c++) { lsOrd.Items.Add(LNO[c]); } } } }

Algoritmos de ordenamiento por distribución La ordenación y la búsqueda son operaciones fundamentales en informática. La ordenación se refiere a la operación de organizar datos en algún orden dado, tal como creciente o decreciente para datos numéricos o alfabéticamente para datos de caracteres. La búsqueda se refiere a la operación de encontrar la posición de un ítem dado de entre un conjunto de ítems. Existen muchos algoritmos de ordenación y búsqueda. En particular, el algoritmo que uno elija dependerá de las propiedades de los datos y de las operaciones que se desee realizar sobre los datos. De acuerdo con esto, queremos saber la complejidad de cada algoritmo; o sea, queremos saber el tiempo de ejecución f(n) de cada algoritmo como una función del número n de elementos de entrada. Distribución simple Este algoritmo tiene la siguiente metodología: Ordena el vector tomando cada número e insertándolo en la posición que toma su valor, es decir, tengo un cinco en el arreglo; lo pongo en la posición cinco, algo así como: “lo que valgas en esa posición te pongo”. Por supuesto, no se podrán ordenar los arreglos que tengan valores repetidos y el vector necesita estar del tamaño del número más grande que se encuentre en él.

62

Principios de distribución Cuando los datos tienen ciertas características como por ejemplo estar dentro de determinado rango y no haber elementos repetidos, pueden aprovecharse estas características para colocar un elemento en su lugar, por ejemplo: Origen 0 1 2 3 4 5 6 7 8 9 7 1 3 0 4 2 6 5 8 9 Destino 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 A continuación se presenta el código para cambiar los valores del Origen al Destino: for(int x=0; x<10;x++) destino[origen[x]]=origen[x]; ¿Que hacer cuando se repitan los datos? Lo que debemos hacer es incrementar la capacidad de la urna. Para lograrlo podemos hacer lo siguiente: 1.- Definir un arreglo en el que cada posición puede ser ocupada por mas de un registro (un arreglo de arreglo de registros) puede darse la situación de ser insuficiente la cantidad de registros adicionales o de existir demasiado desperdicio de memoria. 2.- Definir el tamaño de la urna variable a través del uso de estructuras como las listas simples enlazadas. Urna simple struct nodo { _______ info; struct nodo *sig; } nodo *nuevo, *ini[10], *fin[10]; int i,p; void main() { for(i=0;i<10:i++) ini=fin=NULL; for(i=0;i<n’i++) { nuevo=new nodo; nuevo->info=A; nuevo-> sig=NULL; if(ini[A]==NULL) ini=fin=nuevo; else { fin->sig=nuevo; fin=nuevo; } for(i=0,p=0; i<10;i++) {

63

nuevo=ini; while(nuevo) { A[p]=nuevo->info; p++; ini=nuevo->sig; delete nuevo; nuevo=ini; } } } ¿Que hacer cuando el rango de los valores que queremos ordenar es de 100 a 999? Aplicar urnas simples tantas veces como dígitos tenga el mayor de los números a ordenar. Para la ordenación se hará de la siguiente manera: En la primera pasada se tomará en consideración el digito menos significativo (unidades), en la siguiente vuelta se tomará el siguiente digito hasta terminar (Decenas, Centena,…). void main() { for(cont=1; cont<=veces; cont++) { for (y=0; i<n; y++) { np=A% (i*10cont); np=np/(1* 10 cont - 1 ); urnas_simples(); } } } Ordenamiento Radix Ordenamiento de distribución por conteo Un problema que se presenta con frecuencia es el siguiente: “Ordenar un archivo con N registros cuyas llaves son enteros comprendidos entre 0 y M-1”. Si M no es muy grande, se puede usar el algoritmo de distribución por conteo. La idea básica es contar el número de veces que se repite cada llave diferente y en una segunda pasada utilizar el conteo para posicionar los registros en el archivo. void distributioncounting (itemType a[], int N, int M) { itemType *b; b = new itemType [N]; int *count; count = new int[M]; int i, j; for (j = 0; j < M; j++) count [j] = 0; for (i = 1; i <= N; i++) count [a] ++; for (j = 1; j < M; j++) count [j] += count[j - 1];

64

for (i = N; i >= 1; i--) b[count[a]--] = a ; for (i = 1; i <= N; i++) a = b; delete b; delete count; } Definición En muchas aplicaciones se puede aprovechar el hecho de que las llaves se pueden representar como números dentro de un rango restringido. Se denominan ordenamientos radix a los métodos que sacan ventaja de las propiedades digitales de estos números. Estos métodos no comparan llaves; sino que procesan y comparan pedazos de llaves. Los algoritmos de ordenamiento radix trabajan sobre dígitos individuales de los números que representan a las llaves cuando estas pertenecen a un sistema numérico base M (el radix). Muchas aplicaciones de ordenamiento pueden operar en llaves compuestas de números binarios. Ordenamiento por intercambio radix. Este algoritmo se basa en ordenar las llaves de forma tal que todas las que inicien con un bit en 0 aparezcan antes que todas las que inicien con un bit en 1 y proceder sucesivamente con el resto de los bits mientras queden elementos pendientes de ordenar. Esto da lugar a un algoritmo recursivo. Para reordenar el arreglo inspeccionar comenzando por la izquierda hasta encontrar una llave que empiece con un bit en 1, después inspeccionar por la derecha hasta encontrar una llave que empiece con un bit en 0, intercambiar las llaves y continuar hasta que se crucen los apuntadores de ambas inspecciones. void radixexchange (itemType a[], int left, int right, int bit) { int i, j; itemType t; if (right > left && bit >= 0) { i = left; j = right; while (j != i) { while (!a.bits (bit, 1) && i < j) i++; while ( a[j].bits (bit, 1) && j > i) j--; swap (a, i, j); } if (!a[right].bits (bit, 1)) j++; radixexchange (a, left, j - 1, bit - 1); radixexchange (a, j, right, bit - 1); } } Este método se emplea para organizar información por mas de un criterio. Lo que hacemos es determinar la importancia de los criterios de ordenación y aplicar ordenación estable tantas veces como criterios se tengan, empezando por el criterio menos importante y determinando por el criterio más importante. Estabilidad Un algoritmo de ordenamiento se considera estable si preserva el orden relativo de llaves iguales en la estructura de datos. Por ejemplo, si queremos ordenar por calificación una lista de asistencia que se encuentra ordenada alfabéticamente, un algoritmo estable produce una lista en la que los estudiantes

65

con el mismo grado se mantienen ordenados alfabéticamente, mientras que un algoritmo inestable no dejará trazas del ordenamiento original. La mayoría de los métodos básicos son estables, pero la mayoría de los métodos sofisticados no lo son. Ordenamiento por radix directo Una variante al método de intercambio radix consiste en examinar los bits de derecha a izquierda. El método depende de que el proceso de partición de un bit sea estable. Por lo que el proceso de partición utilizado en el algoritmo de intercambio radix no nos sirve; el proceso de partición es como ordenar una estructura con solo dos valores, por lo que el algoritmo de distribución por conteo nos sirve muy bien. Si asumimos que M = 2 en el algoritmo de distribución por conteo y reemplazamos a por bits (a, k, 1) podemos ordenar el arreglo a en sus k posiciones menos significativas usando un arreglo temporal b. Pero nos conviene más usar un valor de M mayor que corresponda a m bits a la vez durante el ordenamiento con M = 2m como en el siguiente código. void straightradix (itemType a[], itemType b[], int N) { int i, j, pass, count [M-1]; for (pass = 0; pass < numBits / m; pass++) { for (j=0; j < M; j++) count [j] = 0; for (i = 1; i <= N; i++) count [a .bits (pass * m, m)]++; for (j = 1; j < M; j++) count [j] += count [j - 1]; for (i = N; i >= 1; i--) b [count [a .bits (pass * m, m)] --] = a ; for (i = 1; i <= N; i++) a = b; } } Aplicación Creamos primero nuestra forma de la siguiente manera:

66

Ahora implementamos el siguiente código en el botón Ordenamiento Radix: public void RadixSort(int[] a) { // Este es nuestro arreglo auxiliar . int[] t=new int[a.Length]; // Tamaño en bits de nuestro grupo. // Intenta también 2, 8 o 16 para ver si es rápido o no. int r=2; // Número de bits de un entero en c#. int b=32; // Inicia el conteo a asignación de los arreglos. // Notar dimensiones 2^r el cual es el número de todos los valores posibles de un número r-bit. int[] count=new int[1<<r]; int[] pref=new int[1<<r]; // Número de grupos. int groups=(int)Math.Ceiling((double)b/(double)r); // Máscara para identificar los grupos. int mask = (1<<r)-1; // Implementación del algoritmo for (int c=0, shift=0; c<groups; c++, shift+=r) { // Reiniciar el conteo en los arreglos. for (int j=0; j<count.Length; j++) count[j]=0; // Contar elementos del c-vo grupo. for (int i=0; i<a.Length; i++) count[(a[i]>>shift)&mask]++; // Calculando prefijos. pref[0]=0; for (int i=1; i<count.Length; i++) pref[i]=pref[i-1]+count[i-1]; // De a[] a t[] elementos ordenados por c-vo grupo . for (int i=0; i<a.Length; i++) t[pref[(a[i]>>shift)&mask]++]=a[i]; // a[]=t[] e inicia otra vez hasta el último grupo.

67

t.CopyTo(a,0); Console.WriteLine("{0}",c); } // Está ordenado } Ejecutando el programa:

O bien en consola insertar el código: using System; using System.Collections.Generic; namespace RadixSort { class Radix { public void RadixSort(int[] a) { // Este es nuestro arreglo auxiliar . int[] t=new int[a.Length]; // Tamaño en bits de nuestro grupo. // Intenta también 2, 8 o 16 para ver si es rápido o no. int r=2; // Número de bits de un entero en c#. int b=32; // Inicia el conteo a asignación de los arreglos. // Notar dimensiones 2^r el cual es el número de todos los valores posibles de un número r-bit.

68

int[] count=new int[1<<r]; int[] pref=new int[1<<r]; // Número de grupos. int groups=(int)Math.Ceiling((double)b/(double)r); // Máscara para identificar los grupos. int mask = (1<<r)-1; // Implementación del algoritmo for (int c=0, shift=0; c<groups; c++, shift+=r) { // Reiniciar el conteo en los arreglos. for (int j=0; j<count.Length; j++) count[j]=0; // Contar elementos del c-vo grupo. for (int i=0; i<a.Length; i++) count[(a[i]>>shift)&mask]++; // Calculando prefijos. pref[0]=0; for (int i=1; i<count.Length; i++) pref[i]=pref[i-1]+count[i-1]; // De a[] a t[] elementos ordenados por c-vo grupo . for (int i=0; i<a.Length; i++) t[pref[(a[i]>>shift)&mask]++]=a[i]; // a[]=t[] e inicia otra vez hasta el último grupo. t.CopyTo(a,0); Console.WriteLine("{0}",c); } // Está ordenado } public static void Main(string[] args) { int[] a = new int[7] {2,3,1,0,5,6,9}; Console.WriteLine("Ordenamiento Radix"); Radix O = new Radix(); O.RadixSort(a);

69

Console.ReadLine(); } } } Y obtendremos:

Análisis de eficiencia de los ordenamientos por radix La eficiencia de este algoritmo depende en que las llaves estén compuestas de bits aleatorios en un orden aleatorio. Si esta condición no se cumple ocurre una fuerte degradación en el desempeño de estos métodos. Adicionalmente, requiere de espacio adicional para realizar los intercambios. Los algoritmos de ordenamiento basados en radix se consideran como de propósito particular debido a que su factibilidad depende de propiedades especiales de las llaves, en contraste con algoritmos de propósito general como Quicksort que se usan con mayor frecuencia debido a su adaptabilidad a una mayor variedad de aplicaciones. En algunas aplicaciones a la medida, el ordenamiento por radix puede ejecutarse hasta en el doble de velocidad que Quicksort, pero no vale la pena intentarlo si existe problemas potenciales de espacio de almacenamiento o si las llaves son de tamaño variable y/o no son aleatorias.

7 Ordenación externa. ALGORITMOS DE ORDENACION EXTERNA Es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso. Existen otros tipos de memoria externa que son los usb de almacenamiento entre otros. La Ordenación externa de los datos están en un dispositivo de almacenamiento externo (Archivos) y su ordenación es más lenta que la interna.

70

BUSQUEDA ARCHIVO Aqui primero se crea un archivo en notepado o en cualquier editor de texto, despues se busca el archivo que ene este caso es paises en el disco duro con extencion TXT y los muestra en la tabla y lo abrimos como se muestra en el algoritmo.

CODIGO using System; using System.Collections.Generic;

71

using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { class abriendo archivo { static void Main(string[] args) { // crear archivo y abrir Textreader tr = new StreamReader("paises.txt"); // leer linea de texto Console.WriteLine(tr.ReadLine()); // cerrar tr.Close(); } } } ORDENACION Aqui se muestra como se se puede editar un texto txt, abriendolo y ordenandolo como se muetra en la figura yalgoritmo siguiente.

72

CODIGO using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication1 { class escribir en el texto { static void Main(string[] args) { // escribir en en el texto TextWriter tw = new StreamWriter("paises.txt"); // escribir por linea tw.WriteLine(escribe la linea.escribir lo modificado); // close the stream tw.Close(); } } } En conclusion este tema es muy simple y sencillo ya que sirve para ver o editar o textos desde un lenguaje que ene este caso seria c# para poder manipularlos y trabajarlos en un problema mas esntenso y complicado que se pudiera situar Teoria de Mezcla Natural Las secuencias intermedias no tienen tamaño prefijado ni longitud constante. Estas se generan con sus elementos ordenados, separando un elemento nuevo a otra secuencia si no se respeta esta condición. Se incluyen separadores de secuencia. En la mezcla directa no se obtiene ventaja alguna cuando los datos al inicio ya están parcialmente clasificados. La longitud de todas las subsecuencias combinadas en el k-ésimo pase es menor o igual que

73

2k, sin importar si las subsecuencias más largas ya están ordenadas o podrían también combinarse. En efecto, dos subsecuencias ordenadas de longitudes m y n podrían combinarse directamente en una sola secuencia de m + n elementos. Una clasificación por mezcla que en cualquier momento combina las dos subsecuencias mas largas posibles recibe el nombre de clasificación por mezcla natural. A menudo a la sub secuencia ordenada se le llama cadena. Pero como este término se emplea comúnmente para designar secuencias de caracteres, seguiremos el criterio de Knuth en nuestra terminología y utilizaremos la palabra corrida en vez de cadena al referirnos a subsecuencias ordenadas. Llamamos corrida máxima o, simplemente, corrida a una subsecuencia a1 … aj tal que (a¡-l> a¡) & (Ak: i:<> k < j: ak:<> ak+l) & (aj > aj+l) (2.25) Una clasificación por mezcla natural combina, pues, corridas (máximas) en vez de secuencias de longitud fija previamente determinada. Las corridas tienen la propiedad de que, si dos secuencias de n corridas das se combinan, se produce una sola secuencia de exactamente n corridas. Por tanto, el número total se divide a la mitad en cada paso y el número de movimientos requeridos de elementos es n* [log n] en el peor caso, pero en el caso promedio es menos todavía. El número previsto de comparaciones es mucho mayor que además de las que se necesitan para selecionar elementos, se requieren más entre elementos consecutivos de cada archivo para determinar el final de cada corrida. Algoritmo de Mezcla Natural function mergesort(array A[0..n]) begin array A1 := mergesort(A[0..(int(n / 2))]) array A2 := mergesort(A[int(1 + n / 2)..n]) return merge(A1, A2) end function merge(array A1[0..n1], array A2[0..n2]) begin integer p1 := 0 integer p2 := 0 array R[0..(n1 + n2 + 1)] while (p1 <= n1 or p2 <= n2): if (p1 <= n1 and A1[p1] <= A2[p2]): R[p1 + p2] := A1[p1] p1 := p1 + 1 if (p2 <= n2 and A1[p1] > A2[p2]): R[p1 + p2] := A2[p2] p2 := p2 + 1 return R end Ejemlplo: Es un buen método para ordenar barajas de naipes, por ejemplo. Cada pasada se compone de dos fases. En la primera se separa el fichero original en dos auxiliares, los elementos se dirigen a uno u otro fichero separando los tramos de registros que ya estén ordenados. En la segunda fase los dos ficheros auxiliares se mezclan de nuevo de modo que de cada dos tramos se obtiene siempre uno ordenado. El proceso se repite hasta que sólo obtenemos un tramo. Por ejemplo, supongamos los siguientes valores en un fichero de acceso secuencial, que ordenaremos de menor a mayor:

74

3, 1, 2, 4, 6, 9, 5, 8, 10, 7 Separaremos todos los tramos ordenados de este fichero: [3], [1, 2, 4, 6, 9], [5, 8, 10], [7] La primera pasada separará los tramos alternándolos en dos ficheros auxiliares: aux1: [3], [5, 8, 10] aux2: [1, 2, 4, 6, 9], [7] Ahora sigue una pasada de mezcla, mezclaremos un tramo de cada fichero auxiliar en un único tramo: mezcla: [1, 2, 3, 4, 6, 9], [5, 7, 8, 10] Ahora repetimos el proceso, separando los tramos en los ficheros auxiliares: aux1: [1, 2, 3, 4, 6, 9] aux2: [5, 7, 8, 10] Y de mezclándolos de nuevo: mezcla: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 El fichero ya está ordenado, para verificarlo contaremos los tramos obtenidos después de cada proceso de mezcla, el fichero estará desordenado si nos encontramos más de un tramo. Codificacion using System; using System.Collections.Generic; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int num, i = 0, a = 0, j = 0, k = 0; Console.WriteLine(“Ingrese cuantos numeros desea capturar”); num = System.Int16.Parse(Console.ReadLine()); int[] arre = new int[num]; for (i = 0; i < num; i++) { Console.WriteLine(“Ingrese el numero ,0-”, i + 1); arre[i] = System.Int16.Parse(Console.ReadLine()); } Console.WriteLine(“Ordenando…\n\n”); Console.WriteLine(“Ordenado”); a = (num / 2); if (a == 0) { a = num / 2; int[] tem1 = new int[a]; int[] tem2 = new int[a]; for (i = 0, j = a; i < a; i++, j++) { tem1[i] = arre[i]; tem2[i] = arre[j]; } Array.Sort(tem1); Array.Sort(tem2); int lim = num / 2; for (i=0, j=0, k=0, a=0; a < num; a++) { if 1) { arre[k] = tem1[i]; k++; i++; } else { if 2) { arre[k] = tem2[j]; k++; j++; } } } Console.Clear(); Console.WriteLine(“Ordenado por mezcla natural nos queda lo siguiente:”); for (i = 0; i < num; i++) , Console.WriteLine(”,0-”, arre*i+); - Console.ReadLine(); - - - } Corrida

75

Esta ventana es cuando el programa esta capturando los datos para mezclar, se le esta dando clic en el boton agregar hasta que el usuario termina de capturar los datos para despues dar clic en el boton mezclar y asi ordenar por mezcla natural

76

En esta pantalla se puede ver como los datos que el usuario metio se encontran ordenados por mezcla natural. Referencias: http://www.conclase.net/c/ficheros/index.php?cap=005 http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla 1) tem1[i] < tem2[j]) && (i < lim) && (j < lim 2) tem2[j] < tem1[i]) && (i < lim) && (j < lim

8 Métodos de búsqueda. Búsqueda Binaria Si la tabla de números está ordenada, por ejemplo, en orden creciente, es posible utilizar para la búsqueda un algoritmo más eficiente que se basa en un concepto muy utilizado en la programación: dividir para vencer. Si está ordenada la tabla y miramos el número situado en la mitad para ver si es mayor o menor que el número buscado (o con suerte igual), sabremos si la búsqueda ha de proceder en la subtabla con la mitad de tamaño que está antes o después de la mitad. Si se repite recursivamente el algoritmo al final o bien encontraremos el número sobre una tabla de un sólo elemento o estaremos seguros de que no se encuentra allí. Este método permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de búsqueda binaria. Se trata de un algoritmo muy eficiente en cuanto el tiempo requerido para realizar una búsqueda es muy pequeño. La sintaxis expresada de forma genérica para realizar este método es la siguiente: Int BinarySearch ([ ] m. tipo clave) Donde m representa la matriz, clave es el valor que se desea buscar del mismo tipo que los elementos de la matriz, tipo es cualquier tipo de datos de los siguientes: objet, string, byte, char, short, int, long, flota, double, etc. La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector: int vector[10] = {2,4,6,8,10,12,14,16,18,20}; La clave que queremos buscar es 6. El algoritmo funciona de la siguiente manera

1. Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente. 2. Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5. 3. Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y

devolvemos Icentro. 4. Si son distintos, evaluamos si vector[Icentro] es mayor o menor que la clave, como el arreglo está

ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 5 < 6, entonces la parte del arreglo vector*0…5+ ya puede descartarse.

5. Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos que subir hasta 6, entonces quedaría Iarriba = 10, Iabajo = 6. Y volvemos al paso 2.

CODIGO

77

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace busquedabinaria { public partial class Form1 : Form { public int[] num = new int[100]; public int x; public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { int Primero = 0, Ultimo = N - 1,Centro = 0; if (textBox1 != 0) { while ((Primero <= Ultimo) && (Encontrado == false)) { Centro = (Primero + Ultimo) / 2; if ( num[x] == textBox1) Encontrado = true; else { if (num[x] > textBox1) Ultimo = Centro - 1; else Primero = Centro + 1; } } } } private void button3_Click(object sender, EventArgs e) { num[x] = textBox1; }

78

private void label2_Click(object sender, EventArgs e) { if (Encontrado == false) label2 = "el numero fue encontrado"; else label2 = "el numero no fue encontrado"; } } } Corrida

BUSQUEDA SECUENCIAL INTERNA Es la forma mas simple de los metodos de busqueda, inicia el principio de la lista y va buscando el registro deseado en forma secuencial hasta que lo encuentra o hasta que ha llegado al fin de la lista y entonces termina. Este metodo es aplicable a tablas, arreglos, listas, archivos, etc. que se encuentran en desorden. Algoritmo

1.- Empezar con el primer elemento de la lista e inicializar la variable que servira de bandera. 2.- Efectuar la busqueda mientras hay elementos en la lista y el valor de la llave no se ha encontrado. 3.- Verificar si se encontro el elemento objeto de la busqueda. 4.- fin

Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementos buscados, o hasta que se han mirado todos los elementos del array. for(i=j=0;i<N;i++) if(array[i]==elemento) { solucion[j]=i;

79

j++; } Este algoritmo se puede optimizar cuando el array está ordenado, en cuyo caso la condición de salida cambiaría a: for(i=j=0;array[i]⇐elemento;i++) o cuando sólo interesa conocer la primera ocurrencia del elemento en el array: for(i=0;i<N;i++) if(array[i]==elemento) break; En este último caso, cuando sólo interesa la primera posición, se puede utilizar un centinela, esto es, dar a la posición siguiente al último elemento de array el valor del elemento, para estar seguro de que se encuentra el elemento, y no tener que comprobar a cada paso si seguimos buscando dentro de los límites del array: array[N]=elemento; for(i=0;;i++) if(array[i]==elemento) break; Si al acabar el bucle, i vale N es que no se encontraba el elemento. El número medio de comparaciones que hay que hacer antes de encontrar el elemento buscado es de (N+1)/2. CODIGO using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace WindowsApplication2 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } public static int[] arreglo = new int[10]; private void cmdLista_Click(object sender, EventArgs e) { Random num = new Random(); int top, izq; top = 5; izq = 3; for (int i = 0; i < arreglo.Length; i++) {

80

arreglo[i] = num.Next(100, 999);Aqui se genera el arreglo. listBox1.Items.Add(arreglo[i]); top++; if (top >= 25) { izq = izq + 15; top = 5; } } } private void cmdBuscar_Click(object sender, EventArgs e) { int bus, j,con=0; bus = System.Int32.Parse(txtBuscado.Text); bool encontrado = false; j = 0; encontrado = false; while (j < arreglo.Length && encontrado == false) { if (bus == arreglo[j]) encontrado = true; else j++; } if (encontrado == false) { lblMensaje.Text = ("No Esta El Elemento " + bus + " En El Arreglo"); } else { con = j + 1; lblMensaje.Text = ("El Elemento " + bus + " Está En La Posición " + con); } } } } FORMA PRINCIPAL Aqui podemos observar la forma principal.

81

En este ejemplo el arreglo estara dado aleatoriamente del 100 al 999 automaticamente.

Despues de observar el arreglo en pantalla anotaremos el dato a buscar en la caja de texto.

82

Despues presionamos la tecla buscar.

y obtenemos la posicion correcta del dato ingresado por el usuario. La busqueda secuencial interna puede realizarse tambien para datos no visibles en este caso lo realizamos de esta manera para observar que si funciona. Búsqueda Hash En este método se requiere que los elementos estén ordenados. El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento. La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el 1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres, para utilizar mejor el espacio se utilizan funciones mas complejas.

83

La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar. La función de hash depende de cada problema y de cada finalidad, y se pueden utilizar con números o cadenas, pero las más utilizadas son: 1.- Restas sucesivas: Esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas. Un ejemplo serian los alumnos de ingeniería en sistemas que entraron en el año 2005 sus números de control son consecutivos y esta definido el numero de alumnos. 05210800 -05210800»» 0 05210801 -05210800»» 1 05210802 -05210800»» 2 … 05210899 -05210800»» 99 2.- Aritmética modular: El índice de un número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que dos o más elementos pueden producir el mismo residuo y un índice puede ser señalado por varios elementos. A este fenómeno se le llama colisión. Si el número N es el 7, los números siguientes quedan transformados en: 1679 »> 6 4567 »> 3 8471 »> 1 0435 »> 1 5033 »> 0 Mientras mas grande sea número de elementos es mejor escoger un número primo mayor para seccionar el arreglo en más partes. El número elegido da el número de partes en que se secciona el arreglo, y las cada sección esta compuesta por todos los elementos que arrojen el mismo residuo, y mientras mas pequeñas sean las secciones la búsqueda se agilizara mas que es lo que nos interesa. 3.- Mitad del cuadrado: Consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión. 709^2=502681 –> 26 456^2=207936 –> 79 105^2=11025 –> 10 879^2=772641 –> 26 619^2=383161 –> 31 Nota: en caso de que la cifra resultante sea impar se toma el valor número y el anterior. 4.- Truncamiento: Consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión. Por ejemplo, si un número de 7 cifras se debe ordenar en un arreglo de elementos, se pueden tomar el segundo, el cuarto y el sexto para formar un nuevo número: 5700931 »> 703 3498610 »> 481 0056241 »> 064

84

9134720 »> 142 5174829 »> 142 5.- Plegamiento: Consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión. Por ejemplo, si dividimos el número de 7 cifras en 2, 2 y 3 cifras y se suman, dará otro número de tres cifras (y si no, se toman las tres últimas cifras): 5700931 »> 57 + 00 + 931 = 988 3498610 »> 34 + 98 + 610 = 742 0056241 »> 00 + 56 + 241 = 297 9134720 »> 91 + 34 + 720 = 845 5174929 »> 51 + 74 + 929 = 1054 Nota: Estas solo son sugerencias y que con cada problema se pude implementar una nueva función hash que incluso tu puedes inventar o formular. Tratamiento de colisiones Hay diferentes maneras de solucionarlas pero lo más efectivo es en vez de crear un arreglo de número, crear un arreglo de punteros, donde cada puntero señala el principio de una lista enlazada. Así, cada elemento que llega a un determinado índice se pone en el último lugar de la lista de ese índice. El tiempo de búsqueda se reduce considerablemente, y no hace falta poner restricciones al tamaño del arreglo, ya que se pueden añadir nodos dinámicamente a la lista. PRUEBA LINEAL Consiste en que una vez detectada la colisión se debe recorrer el arreglo secuencialmente a partir del punto de colisión, buscando al elemento. El proceso de búsqueda concluye cuando el elemento es hallado, o bien cuando se encuentra una posición vacía. Se trata al arreglo como a una estructura circular: el siguiente elemento después del último es el primero. La función de rehashing es, por tanto, de la forma: R(H(X)) = (H(X) + 1) % m (siendo m el tamaño del arreglo) Ejemplo: Si la posición 397 ya estaba ocupada, el registro con clave 0596397 es colocado en la posición 398, la cual se encuentra disponible. Una vez que el registro ha sido insertado en esta posición, otro registro que genere la posición 397 o la 398 es insertado en la posición siguiente disponible. Ejemplo: Tomando en cuenta los datos de la sección 2 de este tema crea un programa que mediante búsqueda hash encuentre los datos requeridos y asegurate de tratar las colisiones. using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.IO; namespace WindowsApplication1 { public partial class Form1 : Form { private int[] datos = new int[5] {1679, 4567, 8471, 0435, 5033 };

85

private int[] hash = new int[7]; private int[] enlace = new int[7]; public Form1() { InitializeComponent(); for (int b = 0; b <= 6; b++) { enlace[b] = -9999; } //Reacomodo por hash int r, aux=0; for (int i = 0; i <= 4; i++) { r= datos[i] % 7; if (datos[i] == 0) { hash[r] = datos[i]; } else { for(int s=0;s<=6;s++) { if(hash[s]==0) { aux=s; } } hash[aux]=datos[i]; enlace[r] = aux; } } } private void buscar_Click(object sender, EventArgs e) { int temp,r; temp = int.Parse(textBox1.Text.ToString()); r = temp % 7; if (temp == hash[r]) { MessageBox.Show("Se encuentra en \nel renglon:" + r.ToString(), "Resultado"); } else { while(enlace[r] != -9999)

86

{ if (temp == hash[enlace[r]]) { MessageBox.Show("Se encuentra en \nel renglon:" + enlace[r].ToString(), "Resultado"); r = enlace[r]; } } } } } } Imagenes de programa corriendo:

Búsqueda externa En los algoritmos de búsqueda interna se hacían búsquedas en arreglos y variables dentro de la memoria del programa, ahora en búsqueda externa trataremos la manera de cómo encontrar datos dentro de documentos guardados fuera de la memoria del programa es decir dispositivos de almacenamiento(disco duro, CD, USV, etc.). Para poder realizar dicha búsqueda primero hay que tener acceso al documento desde el programa y para eso tenemos que implementar una función del siguiente tipo: Si la dirección del documento es fija: FileStream son = new FileStream(OpenFile.Direccion del documento, FileMode.Open, FileAccess.Read); StreamReader so = new StreamReader(son); Si no es fija puedes usar esta estructura: OpenFileDialog Open = new OpenFileDialog(); Open.ShowDialog(); try { FileStream son = new FileStream(OpenFile.FileName, FileMode.Open, FileAccess.Read); StreamReader so = new StreamReader(son); } catch(ArgumentException) {

87

} Lo que esta asi son nombres de objetos y si modificas uno modifica todos los que lleven el mismo nombre, lo que esta asi lo puedes modificar tomando en consideracion lo que dice el texto. La parte de StreamReader so = new StreamReader(son); tomala a consideracion. Ahora ya tenemos acceso de lectura al documento especificado y podremos hacer la búsqueda de los datos requeridos esto lo haremos mediante algún método planteado en los siguientes temas. Ejemplo 1: Crea un documento de notepad que contenga 5 nombres (Ana, Claudia, Norma, Paola, Sandra) uno por renglón y busca un nombre desde C#.

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.IO; namespace WindowsApplication1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); }

88

private void buscar_Click(object sender, EventArgs e) { int r=0; OpenFileDialog OpenFile = new OpenFileDialog(); OpenFile.ShowDialog(); try { FileStream son = new FileStream(OpenFile.FileName, FileMode.Open, FileAccess.Read); StreamReader so = new StreamReader(son); for (int i = 0; i <=4; i++) { if (textBox1.Text.ToString() == (so.ReadLine()).ToString()) { r = i + 1; } } so.Close(); } catch (ArgumentException) { } if (r != 0) { MessageBox.Show("Se encuentra en \nel renglon:" + r.ToString(), "Resultado"); } else { MessageBox.Show("No se encontro en el arreglo", "Resultado"); } } } } Programa corriendo:

89

BUSQUEDA SECUENCIAL EXTERNA La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades: - Determinar si el elemento buscado se encuentra en el conjunto en el que se busca. - Si el elemento está en el conjunto, hallar la posición en la que se encuentra. En este apartado nos centramos en la búsqueda interna. Como principales algoritmos de búsqueda en arrays tenemos la búsqueda secuencial, la binaria y la búsqueda utilizando tablas de hash. Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementos buscados, o hasta que se han mirado todos los elementos del array. EJEMPLO NOTA En este ejemplo se debe ir primero a la opción mostrar, pues de esta manera el arreglo se cargara de los datos del archivo, de otra manera marcara que no se encuentra el dato buscado.

90

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace BusquedaSecuencialExterna { public partial class Principal : Form { public Principal() { InitializeComponent(); } private void cmdMostrar_Click(object sender, EventArgs e) { frmMostrar m = new frmMostrar(); m.Show(); } private void cmdBuscar_Click(object sender, EventArgs e) { frmBuscar b = new frmBuscar(); b.Show(); }

91

private void cmdSalir_Click(object sender, EventArgs e) { Close(); } } }

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.IO; namespace BusquedaSecuencialExterna { public partial class frmMostrar : Form { public frmMostrar() { InitializeComponent(); } //Este método despliega los valores almacenados en el archivo previamente creado //Los valores se despliegan al cargar la forma private void frmMostrar_Load(object sender, EventArgs e) { //variable que almacenara lo que se extraerá del archivo. string res; //Creación del objeto de la clase StreamReader que se encargara de leer

92

//el archivo cuya ubicación será en un fólder previamente creado en la //carpeta donde se encuentra la clase program.cs //**NOTA** //La ubicación se escribe ../../Archivo/Informacion.txt, incluyendo la //extensión del archivo, ejemplo Info.dat, Info.txt, etc. StreamReader s = new StreamReader("../../Archivo/Informacion.txt"); //Ciclo que se encargara de ir almacenando los datos del archivo //(en este caso números) en un arreglo for (int c = 0; c < Program.tamano; c++) { res = s.ReadLine(); //Línea especifica que se encarga de guardar la información en un arreglo //Como los datos extraídos del archivo son de texto y se desea manipular //la información como numéricos solo agregamos la parte "int.Parse(res)" //para indicar que lo que queremos almacenar será transformado a valor entero. Program.arreglo[c] = int.Parse(res); } //Ciclo que se encarga de desplegar la información del arreglo en un listbox. for (int i = 0; i < Program.tamano; i++) listBox1.Items.Add(Program.arreglo[i]); } private void cmdCerrar_Click(object sender, EventArgs e) { Close(); } } }

using System; using System.Collections.Generic;

93

using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace BusquedaSecuencialExterna { public partial class frmBuscar : Form { public frmBuscar() { InitializeComponent(); } // método que contiene el código que realizara la búsqueda (secuencial) int BusquedaSecuencial() { int i = 0; // Se da entrada a la "clave" que es valor que se desea buscar. Program.clave = int.Parse(txtBusqueda.Text); while (i < Program.tamano) { if (Program.arreglo[i] == Program.clave) return i; i = i + 1; } return -1; // No se encuentra en el arreglo } private void cmdBuscar_Click(object sender, EventArgs e) { try { // Creación de la variable que almacenara el resultado int Res; //llamada al método que realiza la búsqueda binaria y se le asigna a una //variable. Res = BusquedaSecuencial(); //condición que determina si se encontró el elemento, de lo contrario, despliega //un mensaje. if (Res == -1) MessageBox.Show("No se encontró el elemento"); //Despliegue del Resultado. txtResultado.Text = Res.ToString(); groupBox2.Visible = true;

94

} catch { MessageBox.Show("Ocurrió un error"); } } private void cmdLimpiar_Click(object sender, EventArgs e) { txtBusqueda.Clear(); txtResultado.Clear(); txtBusqueda.Focus(); groupBox2.Visible = false; } private void cmdCerrar_Click(object sender, EventArgs e) { Close(); } } } Al igual que en la ventana de Busqueda secuencial, después de presionar el botón de Buscar, aparecerá un groupbox el cual al principio se encuentra “invisible”, es decir se manipulo la propiedad Visible = false, y cuando se presiona el botón buscar se cambia la propiedad a Visible = true, para mostrar los resultados de la búsqueda. NOTA: Esta ventana muestra el indice del elemento en el arreglo, es decir, que nos muestra en la posicion en la que se encuentra dentro del arreglo. BUSQUEDA BINARIA EXTERNA Para realizarla, es necesario contar con un array o vector ordenado. Luego tomamos un elemento central, normalmente el elemento que se encuentra a la mitad del arreglo, y lo comparamos con el elemento buscado. Si el elemento buscado es menor, tomamos el intervalo que va desde el elemento central al principio, en caso contrario, tomamos el intervalo que va desde el elemento central hasta el final del intervalo. Procedemos de esta manera con intervalos cada vez menores hasta que lleguemos a un intervalo indivisible, en cuyo caso el elemento no está en el vector, o el elemento central sea nuestro elemento. De esta forma la complejidad computacional se reduce a O(ln N). Ejemplo NOTA En este ejemplo se debe ir primero a la opción mostrar, pues de esta manera el arreglo se cargara de los datos del archivo, de otra manera marcara que no se encuentra el dato buscado. DISEÑO DE LA FORMA PRINCIPAL En la forma principal únicamente se empleo un groupbox el cual contiene los botones para cada una de las formas que se van a emplear, y se emplea como se observa a continuación: CODIGO DE LA FORMA PRINCIPAL

95

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace BusquedaBinariaExterna { public partial class frmPrincipal : Form { public frmPrincipal() { InitializeComponent(); } private void cmdMostrar_Click(object sender, EventArgs e) { frmMostrar m = new frmMostrar(); m.Show(); } private void cmdBuscar_Click(object sender, EventArgs e) { frmBuscar b = new frmBuscar(); b.Show(); } private void cmdSalir_Click(object sender, EventArgs e) { Close(); } } } En este código se observa que se crearon objetos de cada una de las clases que se desean llamar, ejemplo frmMostrar m = new frmMostrar(); y de esta manera se utiliza dicho objeto para mostrar la forma que se desea emplear al momento. DISEÑO DE LA FORMA MOSTRAR: “DONDE SE CARGAN LOS DATOS AL ARREGLO” En esta forma solo se observa solo un botón, el cual es el botón cerrar, esto se debe a que los datos se cargan automáticamente al cargar la forma, esto se observa en el método de private void frmMostrar_Load(object sender, EventArgs e) el cual se genera automáticamente al dar doble clic en la forma frmMostrar. Se observa que los datos se cargan en un listbox, el cual puede ir agregando elementos. En este caso se implementa de esta manera: listBox1.Items.Add(Program.arreglo[i]); como se puede observar en el código. CODIGO DE LA FORMA MOSTRAR

96

using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.IO; namespace BusquedaBinariaExterna { public partial class frmMostrar : Form { public frmMostrar() { InitializeComponent(); } private void cmdCerrar_Click(object sender, EventArgs e) { Close(); } private void frmMostrar_Load(object sender, EventArgs e) { string res; StreamReader s = new StreamReader("../../Archivo/Informacion.txt"); for (int c = 0; c < Program.tamano; c++) { res = s.ReadLine(); Program.arreglo[c] = int.Parse(res); } for (int i = 0; i < Program.tamano; i++) listBox1.Items.Add(Program.arreglo[i]); } } } en esta parte del código se cargan los datos del archivo en el arreglo, se debe acceder a esta opción primero, antes de realizar la búsqueda, pues como lo mencionaba, en esta opción se cargan los datos. DISEÑO DE LA FORMA BUSCAR En esta forma se observa que se crearon 3 botones; buscar, limpiar, Cerrar. Se observa que se creo una etiqueta la cual muestra una pequeña instrucción y se observa una caja de texto, que será en la cual se introducirá el elemento que se desea buscar. CODIGO DE LA FORMA BUSCAR using System; using System.Collections.Generic;

97

using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; namespace BusquedaBinariaExterna { public partial class frmBuscar : Form { public frmBuscar() { InitializeComponent(); } int busquedaBinaria() { // Se da entrada a la "clave" que es valor que se desea buscar. Program.clave = int.Parse(txtBusqueda.Text); //código que se encarga de hacer la BUSQUEDA BINARIA int Iarriba = Program.tamano - 1; int Iabajo = 0; int Icentro; while (Iabajo <= Iarriba) { Icentro = (Iarriba + Iabajo) / 2; if (Program.arreglo[Icentro] == Program.clave) return Icentro; else if (Program.clave < Program.arreglo[Icentro]) Iarriba = Icentro - 1; else Iabajo = Icentro + 1; } //En caso de no encontrarse regresara el valor -1 para indicar el error return -1; } private void cmdBuscar_Click(object sender, EventArgs e) { try { // Creación de la variable que almacenara el resultado int Res; //llamada al método que realiza la búsqueda binaria y se le asigna a una //variable. Res = busquedaBinaria();

98

//condición que determina si se encontró el elemento, de lo contrario, despliega //un mensaje. if (Res == -1) MessageBox.Show("No se encontró el elemento"); //Despliegue del Resultado. txtResultado.Text = Res.ToString(); groupBox2.Visible = true; } catch { MessageBox.Show("Ocurrió un error"); } } private void cmdLimpiar_Click(object sender, EventArgs e) { txtBusqueda.Clear(); txtResultado.Clear(); txtBusqueda.Focus(); groupBox2.Visible = false; } private void cmdCerrar_Click(object sender, EventArgs e) { Close(); } } } Después de presionar el botón de Buscar, aparecerá un groupbox el cual al principio se encuentra “invisible”, es decir se manipulo la propiedad Visible = false, y cuando se presiona el botón buscar se cambia la propiedad a Visible = true, para mostrar los resultados de la búsqueda. NOTA: Esta ventana muestra el indice del elemento en el arreglo, es decir, que nos muestra en la posicion en la que se encuentra dentro del arreglo.