estructuras de datos con vb.net

Instituto Tecnológico de Zacatecas

Estructuras de datos con

microsoft VB.NET Para las carreras de Ingeniería en Sistemas Computacionales e

Ingeniería en Informática retículas 2010.

Ricardo Alfonso Almanza Márquez

15/01/2013

Estructuras de datos con microsoft VB.NET

2

INTRODUCCIÓN.

El presente trabajo pretende servir como referencia a los alumnos (y docentes) de las carreras de Ingeniería

en Sistemas Computacionales e Ingeniería en Informática que oferta la DGEST (retículas 2010). Se asume que

el estudiante tiene cierta experiencia en el manejo del lenguaje VB.NET. En esta institución, cuando he tenido

oportunidad, he impartido las materias que son competencias previas a Estructura de Datos (Fundamentos de

Programación y Programación Orientada a Objetos) usando el lenguaje de programación Visual Basic .NET ®.

De manera que el tránsito por la materia objeto de este libro es bastante amigable.

Se ha usado una extraña mezcla de ingles – español con el fin de no usar la traducción literal de las palabras

reservadas del lenguaje para tratar de evitar confusiones en los alumnos.

Es claro que en la práctica real, las estructuras de datos juegan un papel preponderante, así que la

importancia de esta materia en la formación de futures desarrolladores de software no tiene lugar a dudas.

Muchos de los casos aquí expuestos han sido tomados de la práctica profesional personal a lo largo de muchos

de los sistemas que he tenido la fortuna de implementar. Otros casos son revisiones del material de varios de

los autores clásicos de esta materia.

El enfoque por competencias que se ha pretendido dar hace que el enfoque sea mucho más práctico que

teórico, el estudiante deberá escribir los programas aquí presentados con el fin de alcanzar las competencias

específicas que establece el programa de la materia y así mismo, realizar los ejercicios propuestos.

Es recomendable, cuando sea posible, que los estudiantes asistan a las exposiciones con una lap, al menos

una por grupo de trabajo, dadas las limitaciones, que como en el caso nuestro, existen en los laboratorios de

cómputo. En esos equipos debe estar instalado al menos la última version VBEE [edición express] (que es

gratuita) disponible en los sitios de Microsoft.

La idea es que el estudiante escriba todos los programas que se muestran en este texto, tratando de evitar la

nociva práctica de copiar – pegar, razón por la cual no se proporciona el código fuente de estos. Habrá que

teclear línea por línea.

DEDICATORIAS:

El trabajo diario de un programador trae consigo una serie de privaciones sobre todo en la familia, quiero

dedicar este trabajo a mi esposa Susana, a mis hijos Ricardo y Sandra quienes soportaron privaciones sobre

todo en el tiempo que debí dedicarles. A mi nieta Carolina quien vino a darme una nueva oportunidad de

reponer ese tiempo y ha sido una nueva luz en mi vida. Quizá tarde he comprendido la importancia de

administrar el tiempo en la tarea del desarrollo de sistemas evitando la obsesion de terminar alguna tarea a

como dé lugar y nunca quitar tiempo de dedicación a la familia.

Ricardo Alfonso Almanza Márquez


3

Tabla de contenido

Introducción a las Estructuras de Datos ................................................................ 5

Definiciones ...................................................................................................... 5

Tipos de datos abstractos (TDA) .................................................................... 6

Arreglos ....................................................................................................... 21

Recursividad ....................................................................................................... 67

Estructuras Lineales............................................................................................ 73

Listas .............................................................................................................. 73

Lista ligada simple ....................................................................................... 74

Lista ligada doble ......................................................................................... 82

Lista circular ................................................................................................ 94

Pilas .............................................................................................................. 103

Estructuras No Lineales .................................................................................... 127

Árboles ...................................................................................................... 127

Árboles Binarios ......................................................................................... 128

Árboles balanceados .................................................................................. 139

Grafos ........................................................................................................ 141

Métodos de Ordenamiento ............................................................................... 151

Ordemamiento por selección ..................................................................... 153

Ordenamiento de la burbuja ...................................................................... 157

Ordenamiento rápido (Quick Sort ............................................................... 159

Ordenamiento por acumulación (Heap Sort) ............................................... 162

Ordenamiento por mezcla (Merge Sort) ...................................................... 167

Ordenamiento externo ............................................................................... 169

Métodos de Búsqueda ...................................................................................... 177

Búsqeda secuencial .................................................................................... 177


4

Búsqueda binaria ....................................................................................... 179

Búsqueda por funciones Hash .................................................................... 180

Análisis de algoritmos ...................................................................................... 191


5

1 Introducción a las estructuras de datos.

Competencia específica a desarrollar:

Representar y aplicar los tipos de datos abstractos por medio de un lenguaje de programación.

DEFINICIONES.

Una estructura de datos es un formato especializado para almacenar y organizar datos. Los tipos de

estructuras de datos generales incluyen el arreglo, el archivo, la tabla, el árbol, etc. Toda estructura

de datos es diseñada para organizar datos con un propósito específico a la que se puede acceder y

en la que se puede trabajar de forma adecuada. En programación, se puede seleccionar una

estructura de datos puede seleccionarse o diseñarse para almacenar datos con el propósito de

trabajar sobre ella con varios algoritmos.

Por su parte, un algoritmo es un procedimiento o fórmula para resolver un problema. La palabra

algoritmo proviene del nombre del matemático Mohamed ibn-Musa al-Khwarizmi que formó parte

de la corte real en Bagdad aproximadamente entre los años 750 a 850 DC. Es fuente además de la

palabra algebra.

Enciclopedia Británica:

Estructura de datos.- Forma en la que los datos son almacenados para una búsqueda y

recuperación eficientes. La estructura de datos más simple es el arreglo unidimensional (lineal).

Enciclopedia de ciencia y tecnología de McGraw-Hill:

Medio para almacenar una colección de datos. La ciencia de la computación es en parte el estudio de

los métodos para usar efectivamente una computadora en la solución de problemas, o en otras

palabras, la determinación exacta del problema a resolver. Este proceso implica:

1. Comprender el problema.

2. Traducir descripciones vagas, metas y requerimientos contradictorios (y a menudo deseos

sin especificar) dentro de una solución conceptual formulada con precisión con un lenguaje

de programación. Esta solución generalmente consiste en dos partes: algoritmos y

estructuras de datos.

Relación con algoritmos.

Un algoritmo es una especificación concisa de un método para resolver un problema. Una estructura

de datos puede verse como un conjunto de algoritmos para realizar operaciones sobre los datos que

almacena. Así, los algoritmos son parte de lo que constituye una estructura de datos. En la

construcción de la solución a un problema, una estructura de datos debe ser elegida de manera que

permita que los datos sean manipulados fácilmente de la manera que el algoritmo lo requiere.


6

Los datos pueden organizarse en diferentes niveles y la variedad en el diseño de algoritmos

generalmente surge de la manera en la cual los datos para el programa son almacenados, esto es:

1. Cómo se organizan los datos en relación a otros.

2. Cuáles datos son calculados necesariamente.

3. Cuáles datos permanecen en memoria.

4. Cuáles datos deben almacenarse en archivos y la organización de estos archivos.

Un algoritmo puede requerir colocar datos nuevos en una colección existente de los mismos,

removerlos o acceder a una colección de datos para propósitos específicos.

Tipos de datos abstractos (TDA).

Un tipo de dato abstracto (TDA), abstract data type (ADT), es un modelo matemático que puede

usarse para capturar lo esencial del dominio de un problema con el fin de traducirlo a un lenguaje

de programación.

Es una entidad matemática que consiste en un conjunto de valores (el conjunto portador) y una

colección de operaciones que los manipule. Por ejemplo, el tipo de dato abstracto entero consiste de

un conjunto portador que contiene los número enteros negativos y positivos además del 0 y una

colección de operaciones que los manipula como pueden ser la suma, la resta, la multiplicación, la

comparación de igualdad y la comparación de orden (Algebra abstracta).

Abstracción.

Abstracción es ignorar el detalle de algunas cosas a favor de otras. La abstracción es importante en

la solución de problemas porque permite a quien los resuelve enfocarse en los detalles esenciales

en tanto ignora los no esenciales, simplificando así el problema y concentrando su atención en

aquellos aspectos del mismo que involucran su solución. Los tipos de datos abstractos son

importantes en ciencias de la computación porque proporcionan una manera clara y precisa para

especificar que datos debe manipular un programa (y cómo debe manejarlos) sin considerar los

detalles sobre cómo los datos son representados ó cómo se implementan las operaciones. Una vez

comprendidos los tipos de datos abstractos y documentados, sirven como una especificación que

los programadores pueden usar para guiar su decisión sobre la implementación y operación de los

datos y como un estándar para asegurar la exactitud del programa.

Tales especificaciones de los tipos de datos abstractos proporcionan las bases para su realización

en programas. Los programadores conocen que valores de datos necesitan ser representados, que

operaciones serán requeridas y qué limitaciones deben satisfacerse. El estudio cuidadoso del código

desarrollado y la apropiada selección de pruebas ayudan a asegurar que el programa esté correcto.

Finalmente las especificaciones de tipos de datos abstractos pueden usarse para investigar y

demostrar de los tipos de datos abstractos mismos, llevando a un mejor entendimiento de los

programas y finalmente a un software de alta calidad.


7

Relación con el paradigma orientado a objetos.

Una tendencia mayor en la ciencia de la computación ha sido el paradigma orientado a objetos, un

enfoque para programar, diseñar e implementar que usa colecciones de entidades que interactúan

entre sí llamadas objetos. Los objetos incorporan tanto datos como operaciones, de esta manera

imitan cosas del mundo real, las cuales tienen propiedades (datos) y conductas (también llamadas

métodos) – las operaciones. Los objetos que manejan el mismo tipo de datos y realizan las mismas

operaciones forman una clase.

Los valores de datos abstractos están separados de sus operaciones. Si los valores del conjunto

portador de un tipo de dato abstracto se pueden reconceptualizar para incluir no sólo valores de

datos sino también operaciones abstractas, entonces los elementos del conjunto portador se vuelve

una entidad que incorpora tanto datos como operaciones, como objetos, y el conjunto portador en

sí es mucho más parecido a una clase. El paradigma orientado a objetos puede verse como una

extensión del uso de tipos de datos abstractos.

Modularidad.

Es la propiedad que permite subdividir una aplicación en partes más pequeñas llamadas módulos

con el fin de hacerla más comprensible y manejable. Históricamente es una evolución de la

programación estructurada para solucionar problemas de programación más grandes y complejos

de lo que ésta puede resolver.

Un módulo es cada una de las partes de un programa que resuelve una de las partes en que se

divide el problema complejo original. Cada módulo tiene una tarea bien definida y algunos necesitan

de otros para poder operar. En caso de que un módulo necesite de otro, puede comunicarse con

éste mediante una interfaz de comunicación que debe estar bien definida.

Es común en la práctica tomar el concepto de módulo como sinónimo de procedimientos y

funciones. Sin embargo no necesariamente ni estrictamente un módulo es una función o un

procedimiento, ya que el mismo puede contener muchos de ellos.

La modularidad es un concepto que se ha aplicado durante muchos años en el desarrollo de

programas, actualmente es casi imposible crear aplicaciones relativamente complejas sin usar

módulos, por esta razón el estudiante que llega a esta materia (Estructuras de Datos) debe estar

familiarizado con el concepto desde sus primeros cursos de programación.

Uso de TDA.

Planteamiento del problema:


8

Una línea recta se define como la unión de dos puntos (P1 y P2) definidos sobre un eje cartesiano

XY. Cada punto se define por dos valores x-y:

P1(x₁, y₁) y P2(x₂, y₂)

Así si ambos puntos tienen valores:

P1(1,1) ; P2(5, 5) la recta resultante es:

.

La distancia entre ambos puntos está definida por:

[1]

Y la ecuación que la representa es:

[2]

Donde la pendiente m es:

[3]

Y en función de los dos puntos, la recta puede obtenerse con:

[4]

0

1

2

3

4

5

6

1 2 3 4 5


9

O en función del punto P1 y la pendiente m:

[5]

Desarrollar una aplicación que utilice un TDA que lea los dos puntos, encuentre la distancia entre

ambos y muestre la ecuación de la recta resultante usando el paradigma orientado a objetos.

Al principio de esta unidad se estableció que la determinación exacta de un problema implica, ante

todo, la comprensión del mismo. Se puede afirmar que si se es capaz de resolverlo manualmente tal

comprensión se ha alcanzado:

Solución (manual):

Pendiente:

Finalmente, de la ecuación [5]:

Que es la ecuación de esta recta:

Una vez que se entiende el problema el primer paso es la abstracción del mismo lo que requiere

identificar:

1. Que datos son necesarios (entradas).

2. Que datos se esperan en la solución.

3. Que valores son calculados en los procesos de solución.

4. Desarrollar el algoritmo que resuelva el problema.


10

Para esto representaremos la recta como un objeto (que es el TDA que la manipulará).

Esta es una abstracción simple, así para el ejemplo considerado la solución se representa como:

Definición del objeto Recta:

Recta

Propiedades Métodos

Nombre Tipo de dato Nombre Tipo de dato Propósito

X1 Número real simple Distancia Real simple Calcula distancia

X2 Número real simple Pendiente Real simple Obtiene m

Y1 Número real simple Ecuación (Ec) Cadena Ecuación resultante

Y2 Número real simple

En el diseño de clases de este texto seguimos la metodología propuesta por Deborah Kurata1

Así, una vez creada la clase que representará al objeto Recta, el algoritmo general de solución puede

plantearse de la siguiente manera:

1. Leer datos de entrada (X1, Y1, X2, Y2) Asignación de propiedades.

1 Deborah Kurata: Doing Objects in Microsoft VB.NET.

Recta

Datos de entrada:

P1 y P2 definidos por

pares de valores

numéricos para (x₁, y₁) y

(x₂, y₂)

Datos de Salida:

Distancia entre P1 y P2

(d).

Pendiente de la recta (m).

Ecuación: y = mx + b

x₁ = 1, y₁ =

1

x₂ = 5, y₂

=5

Recta d =

m = 1

y = x

Algoritmos


11

2. Calcular la distancia usando [1].

3. Calcular la pendiente usando [3].

4. A partir de las ecuaciones [4] ó [5] obtener la ecuación de la recta como una cadena de

caracteres.

5. Mostrar resultados.

Clase que representa al TDA:

Imports System.Math

Public Class CTDA_Recta

Private mvarX1 As Single

Private mvarX2 As Single

Private mvarY1 As Single

Private mvarY2 As Single

Private mvarm As Single

Property X1() As Single

Get

Return mvarX1

End Get

Set(ByVal value As Single)

mvarX1 = value

End Set

End Property

Property X2() As Single

Get

Return mvarX2

End Get


mvarX2 = value

End Set

End Property

Property Y1() As Single

Get

Return mvarY1

End Get


mvarY1 = value

End Set

End Property

Property Y2() As Single

Get

Return mvarY2

End Get


mvarY2 = value

End Set

End Property

P

r

o

p

i

e

d

a

d

e

s


12

Public Function Distancia() As Single

'De la fórmula [1]

Dim D As Single = Sqrt((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)2

Return D

End Function

Public Function m() As Single

'De la fórmula [3]

Return (Y2 - Y1) / (X2 - X1)

End Function

Public Function Ec() As String

'Usando [5]

Dim Eq As String = "Y = " & m.ToString("n2") & "X "

Dim Temp As Single = -m() * X1 + Y1

'Verificar signo de Temp

If Sign(Temp) = 1 Then

Eq += " + " + Temp.ToString("n2")

ElseIf Sign(Temp) < 0 Then

Eq += " - " + Temp.ToString("n2")

End If

Return Eq

End Function

End Class

Uso en consola:

Imports System.Console

Module Module1

Private MiTDA As New CTDA_Recta

Sub Main()

BackgroundColor = ConsoleColor.White

ForegroundColor = ConsoleColor.Black

Clear()

WriteLine("Punto P1:")

Write("X1 = ")

MiTDA.X1 = ReadLine()

Write("Y1 = ")

MiTDA.Y1 = ReadLine()

WriteLine()

WriteLine("Punto P2:")

Write("X2 = ")

MiTDA.X2 = ReadLine()

Write("Y2 = ")

MiTDA.Y2 = ReadLine()

WriteLine()

WriteLine("RESULTADOS")

WriteLine("Distancia = " + MiTDA.Distancia.ToString("n4"))

WriteLine("Pendiente m = " + MiTDA.m.ToString("n2"))

WriteLine("La ecuación es:")

WriteLine()

WriteLine(MiTDA.Ec)

ReadKey()

End Sub

End Module

Ejecución:

2 El símbolo ^ también representa al operador de potencia.

M

é

t

o

d

o

s


13

El uso de consolas permite una rápida revisión de la solución que se trata de implementar. Después

de probar con diferentes valores con resultados conocidos, la solución se transporta fácilmente al

entorno Windows®.

Para crear la solución usando las capacidades de VB.NET se puede crear la siguiente forma básica:

Objetos en esta ventana (valores sugeridos):

Objeto (Name) Tipo Propiedades Propósito frmTDA_Recta Form MaximizeBox = False

StartPosition = CenterScreen

txtX1, txtY1 Textbox TextAlign = Center Capturar X1 txtX1, txtY2 TextBox TextAlign = Center Capturar Y2 btnResult Buttton Iniciar métodos labD, labM Label AutoSize = False Mostrar distancia y


14

BackColor = White Text = 0 TextAlign = MiddleRight

Pendiente.

labEc Label AutoSize = False BackColor = White Text = “” TextAlign = MiddleCenter

Mostrar la ecuación.

Agregar al proyecto la clase TDA desarrollada previamente:

Menú Proyecto Agregar elemento existente.

El proyecto debe verse así:

Ejecución:

Public Class frmTDARecta

Private MiTDA As New CTDA_Recta

Private Sub btnResult_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnResult.Click

Try

'Lectura de puntos P1 y P2:

MiTDA.X1 = CSng(txtX1.Text)

MiTDA.Y1 = CSng(txtY1.Text)


15

MiTDA.X2 = CSng(txtX2.Text)

MiTDA.Y2 = CSng(txtY2.Text)

'Resultados

labD.Text = MiTDA.Distancia.ToString("n4")

labM.Text = MiTDA.m.ToString("n2")

labEc.Text = MiTDA.Ec

Catch ex As Exception

MsgBox("Se ha ingresado un valor no permitido", MsgBoxStyle.Exclamation)

End Try

End Sub

Private Sub btnNew_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnNew.Click

'Datos nuevos

MiTDA = New CTDA_Recta

'Limpia las cajas de texto:

For Each oTexto As Control In Me.Controls

If TypeOf (oTexto) Is TextBox Then

oTexto.Text = ""

End If

Next

labD.Text = ""

labM.Text = ""

labEc.Text = ""

txtX1.Focus()

End Sub

Private Sub btnClose_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnClose.Click

Me.Close()

End Sub

End Class

Ejercicio #1 para el desarrollo de la competencia específica:

Para un cilindro circular (recto)3 se tienen las fórmulas siguientes:

Volumen:

[1]

Área:

[2]

3 Del Manual de fórmulas técnicas. Gieck 30ª Edición. IPN.


16

Donde A es el área, d es el diámetro de la circunferencia, h

la altura del cilindro y r el radio.

Si se conocen la altura y el diámetro calcular el volumen. Si

se conoce la altura y el volumen calcular el diámetro y si se

conocen el volumen y el diámetro calcular la altura.

Diseñar la clase que represente al tipo de dato abstracto

Cilindro para realizar lo que se pide (para consola y para una

forma).

NOTA.- En el espacio de nombres Math del .NET Framework está

definida la constante π (Math.PI). Y la función Pow permite elevar

cualquier número a una potencia. Pow(n, m) donde n es el número y

m la potencia.

Por ejemplo, el pseudocódigo 4↑3 se representa como Pow(4,3).

Casos de prueba:

h = 4

d = 2

Entonces de [1] :

Y de [2]

Si

h = 4 y A =

Obteniendo el radio de [2]:

r = 1, luego el diámetro es 2r = 2

Por último si se conocen los valores de d y de A:

Entonces h ≈ 4 .

Prueba del programa:


17

Vista del proyecto:

Solución para Windows®

Aprovechando las muchas facilidades de interfaz para el usuario que proporciona VB.NET, una

solución al problema podría verse así:

Ventana de base (frmTDACilindro):

Los controles de opciones

(RadioButton) tienen asignado

un valor numérico

consecutivo en su propiedad

Tag (0, 1 y 2) que se mapea

con la misma propiedad de

las cajas de texto para los

datos:

Volumen (Tag = 0) Tag = 2

en la caja texto

correspondiente. Diámetro

(Tag = 1) Tag = 0 en la

caja de texto. Altura (Tag = 2)

Tag = 1 en la caja de texto

del diámetro. Todos tienen su

propiedad Chcked en False y

están contenidos en un

GroupBox.


18

Valores de la propiedad Tag sugeridos

Tag en RadioButton

Nombre Tag

rbVol 0

rbV 1

rbAltura 2

Cada vez que el usuario selecciona una opción el valor de la propiedad Tag es asignado a un objeto

de tipo entero corto, (iModo), manejando este evento en un solo procedimiento (de evento) y

permite conocer que partes del TDA usar.

Public Class frmTDACilindro

Private MiTDACil As CTDA_CilindroR 'La clase se importa desde la aplicación de consola

donde fue desarrollada y probada

Private iModo As Short

Private Sub frmTDACilindro_Load(ByVal sender As System.Object, ByVal e As

System.EventArgs) Handles MyBase.Load

'La carga de la forma establece la primera selección y se desencadena el evento:

rbVol.Checked = True

End Sub

Private Sub rbAltura_CheckedChanged(ByVal sender As Object, ByVal e As System.EventArgs)

Handles rbAltura.CheckedChanged _

, rbD.CheckedChanged, rbVol.CheckedChanged

'Cualquier evento de selección es manejado en este procedimiento

Dim oRB As RadioButton = sender

If oRB.Checked Then

MiTDACil = New CTDA_CilindroR

iModo = oRB.Tag

SetTextos()

btnOK.Enabled = True

End If

End Sub

Así las tres opciones son manejadas en la misma ventana:

Caso 1: Altura y diámetro conocidos.

Al seleccionar esta opción, los

objetos de texto para el volumen y

el área son desactivados

(propiedad ReadOnly = True) por el

módulo SetTextos. De esta manera,

el usuario sólo puede ingresar los

valores conocidos (propiedades del

TDA).

El botón desencadena los

métodos (operaciones)

desarrollados en la clase y muestra los resultados faltantes.


19

Cuando se cambia de opción, la ventana se prepara para recibir los nuevos datos:

Caso 2: Altura y Área conocidas.

El mismo módulo SetTextos ahora

desactiva los valores que deben

ser calculados.

Caso 3: Diámetro y altura

conocidos.

Private Sub SetTextos() For Each oTexto As Control In Me.Controls

If TypeOf (oTexto) Is TextBox Then

Dim txt As TextBox = oTexto

txt.Clear()

txt.ReadOnly = True

If iModo = 0 Then

txt_h.ReadOnly = False

txtD.ReadOnly = False

ElseIf iModo = 1 Then

txt_h.ReadOnly = False

txtArea.ReadOnly = False

Else

txtD.ReadOnly = False

txtArea.ReadOnly = False

End If

End If

Next

End Sub


20

El siguiente código depende de cómo se haya desarrollado la clase que representa al TDA para el

manejo de este tipo de cilindro y deberá ser completado y probado.

Private Sub btnOK_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnOK.Click

Try

Select Case iModo

Case 0

'Altura y diámetro conocidos:

Case 1

'Altura y área conocidas:

Case Else

'Diámetro y altura conocidos

End Select


MsgBox(ex.Message, MsgBoxStyle.Exclamation)

End Try

End Sub

Ejercicio #2: Para el cuerpo geométrico denominado cono circular (recto) se tienen las siguientes

fórmulas4:

[1]

[2]

[3]

[4]

[5]

Diseñar un TDA (clase) que permita el cálculo de:

4 Manual de fórmulas técnicas. Greck. IPN


21

Ejercicio #3.- Se desea conocer el volumen de un barril (usando una clase):

Arreglos.

El arreglo es la estructura de datos más común y existe desde los primeros lenguajes de

programación. Un arreglo permite almacenar un conjunto de elementos ordenándolos por posición,

generalmente la primera posición tiene el valor de cero y, normalmente, debe conocerse el número

de elementos N que se van a almacenar.

0 1 2 … N Posiciones

E₁ E₂ E₃ Ei En Elementos

El uso de esta estructura requiere reservar ubicaciones de memoria RAM contiguas en tiempo de

compilación y esta asignación puede ser estática o dinámica. Dependiendo de cómo sea declarado,

un arreglo puede existir (ser accesible) en:

Todo el programa.

En un módulo

En un procedimiento.

La memoria asignada de forma estática no se libera sino hasta que la ejecución del programa

termina de otro modo el arreglo deja de existir al terminar la ejecución del módulo o el

procedimiento donde fue creado.

En VB.NET, un arreglo es una instancia de la clase Array misma que proporciona un conjunto de

métodos tales como ordenación y búsqueda que en el pasado se tenían que desarrollar. Sin

embargo eso no impide que se analicen los diferentes algoritmos para tales procesos.

Este lenguaje (y todos los que usan el marco .NET) tienen una clase nueva denominada ArrayList

que es un arreglo que obtiene más espacio de forma dinámica a medida que lo requiere. En

situaciones donde no se conoce con exactitud el tamaño del arreglo o cuando éste puede cambiar

durante el ciclo de vida de un programa un ArrayList puede ser una mejor elección que un arreglo

simple.

Declaración e inicialización de arreglos.


22

Un arreglo (de una dimensión) se declara con un nombre y, opcionalmente su tamaño (N valor de

tipo entero) y estableciendo que tipo de datos manejará. Esta acción se representa como A[N], a

cada elemento del arreglo se le asigna un valor (del tipo adecuado) usando un apuntador i.

Un arreglo de una dimensión se puede declarar a nivel módulo como:

Private Arreglo(), si no se especifica su tamaño N, se dice que el arreglo es dinámico y puede

modificar su tamaño en cualquier parte del módulo usando la instrucción ReDim.

Ejemplo:


Module Module1

Private Arreglo() As Integer, N As Short

Sub Main()



Clear()

Dim i As Short

Write("N = ")

N = ReadLine()

'Se forma el arreglo, si existiera uno previo será reemplazado

'El valor de cada uno de sus elementos es cero

ReDim Arreglo(N)

For i = 0 To N - 1

Write("A[" + i.ToString + "] = ")

Arreglo(i) = ReadLine()

Next

WriteLine()

WriteLine("El arreglo es:")

WriteLine()

For i = 0 To N - 1

Write(Arreglo(i).ToString + " ")

Next

WriteLine()

ReadKey()

End Sub

End Module

Se puede modificar el tamaño de un arreglo sin perder la información almacenada en él usando la

instrucción Redim Preserve:

Modificando el programa anterior:


Module Module1

Private Arreglo() As Integer, N As Short

Sub Main()



23


Clear()

Dim i, U As Short

Write("N = ")

N = ReadLine()

'Se forma el arreglo, si existiera uno previo será reemplazado

'El valor de cada uno de sus elementos es cero

ReDim Arreglo(N)

For i = 0 To N - 1



Next

U = i 'La útima posición en el arreglo

WriteLine()


WriteLine()

For i = 0 To N - 1


Next

WriteLine()

Write("Nuevo Tamaño: ")

N = ReadLine()

'Se modifica el tamaño del arreglo manteniendo sus valores

ReDim Preserve Arreglo(N)

For i = U To N - 1



Next

WriteLine()


WriteLine()

For i = 0 To N - 1


Next

WriteLine()

ReadKey()

End Sub

End Module

Ejecución:

Si se desea usar un arreglo estático debe usarse la declaración Static:


24


Module Module1

Sub Main()



Clear()

Dim N As Short

Write("N = ")

N = ReadLine()

Static Dim A(N) As Integer

LlenaPares(N, A)

Write("El Arreglo de pares es:")

WriteLine()

For i As Short = 0 To N - 1

Write(A(i).ToString + " ")

Next

ReadKey()

End Sub

Private Sub LlenaPares(ByVal N As Short, ByRef A() As Integer)

Dim i As Short

Dim Valor As Short = 2

For i = 0 To N

A(i) = Valor

Valor += 2

Next

End Sub

End Module

Este tipo de arreglos consume más memoria que los dinámicos.

Si A[i] k, donde 0<=i <=N-1 (Tipo de datos)

Así por ejemplo: Si N = 5, A[N] (3, 5, 7, 1, 2) en VB.NET se puede crear de la manera clásica como:

El uso de consola es práctico solo para arreglos pequeños para probar procedimientos básicos.

Listado #1.


Module Module1

Sub Main()



Clear()

Dim N As Short = 5

Dim A(N - 1) As Short '5 posiciones ya que la primera comienza en cero

A(0) = 3

A(1) = 5

A(2) = 7

A(3) = 1

A(4) = 2


For i As Short = 0 To N - 1

Write(A(i).ToString + " ")

Next

WriteLine()

ReadKey()

End Sub

End Module

El mismo programa en las versiones de VB.NET 2008 y posteriores se puede escribir así:


25

Listado #2.


Module Module1

Sub Main()



Clear()

Dim A() As Short = {3, 5, 7, 1, 2}


For Each Numero As Short In A

Write(Numero.ToString + " ")

Next

WriteLine()

ReadKey()

End Sub

End Module

O también:

Listado #3.


Module Module1

Sub Main()



Clear()

Dim A() As Short

A = New Short() {3, 5, 7, 1, 2}


For Each Numero As Short In A

Write(Numero.ToString + " ")

Next

WriteLine()

ReadKey()

End Sub

End Module

Todas las ejecuciones producen la misma salida:

En todos los casos, el arreglo A[N] fue declarado localmente

(dentro del procedimiento Sub Main( ) y de forma dinámica. Por

tanto existe sólo mientras tal procedimiento es ejecutado.

Manejo de diferentes conjuntos de datos sobre un mismo arreglo.

En el siguiente código, el arreglo A[ ] es declarado a nivel del módulo usando además la palabra

Priivate, lo que significa que el arreglo permanece durante la ejecución del módulo y al ser declarado

inicialmente sin dimensión se dice que es un arreglo dinámico. Cada vez que se establece un valor

numérico para N el arreglo se crea usando ReDim que además inicializa todos sus elementos en

cero.

El ciclo For-Each itera

sobre cada elemento del

arreglo comenzando por

el primero sin necesidad

de mantener

apuntadores.


26


Module Module1

Private A() As Integer

Sub Main()



Dim A() As Integer

Dim N, i, x As Integer

Dim Continua As String = "S"

Do While Continua.ToUpper = "S"

Clear()

Write("N = ")

N = ReadLine()

If IsNumeric(N) Then

ReDim A(N - 1)

For i = A.GetLowerBound(0)5 To A.GetUpperBound(0)

6


A(i) = ReadLine()

Next

WriteLine()

WriteLine("Valorese en el arreglo:")

For Each x In A

Write(x.ToString + ", ")

Next

End If

WriteLine()

WriteLine()

WriteLine("¿Ingresa otro arreglo (S/N)? ")

Continua = ReadLine()

Loop

End Sub

End Module

Para el análisis de algoritmos que involucran arreglos de un tamaño relativamente grande, el uso de

consolas resulta bastante tedioso. Es conveniente crear una forma general que maneje arreglos de

una manera eficiente y permita desarrollar y probar diferentes algoritmos.

Forma básica para arreglos de una dimensión:

5 GetLowerBound(k) regresa el límite inferior del arreglo k = 0 para arreglos de una dimensión.

6 GetUpperBound(k) el límite superior de un arreglo, k =0 para renglones y k = 1 para columnas en una matriz.


27

Descripción de la aplicación:

Permite establecer el valor del tamaño del arreglo (N). Al

aceptarlo éste será creado y se prepara su interfaz para la

asignación de sus valores.

Los controles de esta sección están contenidos en un GroupBox cuya propiedad Name se establece

como GpoN. Un control numérico (NumericUpDown) con propiedades Maximum = 200 y Minimum =

5 y TextAlign =Center y de nombre NumN.

El arreglo resultante es manipulado en un control llamado DataGridView denominado DGVA y con la

propiedad AllowUserToAddRows = False. Los procedimientos de evento que este control tiene

permiten que la validación de los datos de entrada sean validados fácilmente.

Estos botones permiten guardar y recuperar el arreglo actual en

(desde) un archivo secuencial.

El botón guardar se ha denominado btnSave y tiene su propiedad Enabled = False. El segundo

botón se llama btnOpen sin ningún otro valor de propiedad modificado

. Es otro GroupBox llamado GpoAlg en donde se irán insertando botones

que resuelvan diferentes problemas usando arreglos.


28

Es un TextBox de nombre txtSol, con la propiedad

Multiline establecida en True. SrollBars = Both,

WordWrap = False, Font = Console (8 pts)7.

Cuadros de diálogo para el manejo de archivos de nombre SaveFD

y OpenFD respectivamente.

SaveFD.- Control SaveFileDialog, defaultExt = dat, Filter = Archivos de datos (*.dat)|*.dat.

OpenFD.- Control OpenFileDialog con las mismas propiedades Filter y defaultExt anteriores y la

propiedad FileName = “” (nada)

La primera fase de desarrollo debe permitir crear arreglos, asignar sus valores (numéricos),

guardarlo y recuperarlo

Este es el primer código a escribir.

Public Class frmArray

Private Arreglo() As Integer, N

Private Sub frmArray_Load(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles MyBase.Load

Dim sRuta As String = My.Application.Info.DirectoryPath + "\Arreglos"

'Si esta ruta no existe, se crea

If Not My.Computer.FileSystem.DirectoryExists(sRuta) Then

My.Computer.FileSystem.CreateDirectory(sRuta)

End If

'Ruta inicial para los cuadros de diálogo de archivos

SaveFD.InitialDirectory = sRuta

OpenFD.InitialDirectory = sRuta

End Sub

Creación de arreglo y de su interfaz:

7 Aunque puede dejarse el valor por defecto.


29

Private Sub btnOK_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnOK.Click

CreaArreglo()

End Sub

En este procedimiento se asigna el valor de N, se forma un arreglo nuevo y se prepara DGVA para

representarlo y manejarlo.

Private Sub CreaArreglo() N = NumN.Value

ReDim Arreglo(N)

With DGVA

.RowCount = 1 'Siempre un sólo renglón

.ColumnCount = Arreglo.GetUpperBound(0) 'Columnas = Tamaño del arreglo

For Each Kol As DataGridViewColumn In DGVA.Columns

Kol.HeaderText = Kol.Index 'Posición

Kol.AutoSizeMode = DataGridViewAutoSizeColumnMode.AllCells 'Autoajuste de

celdas

Kol.DefaultCellStyle.Alignment = DataGridViewContentAlignment.TopCenter

'Alineado al centro

Next

End With

Valores()

btnSave.Enabled = True

End Sub

Private Sub Valores()

'Muestra el arreglo en DGVA

Dim i As Integer

For i = 0 To N - 1

DGVA.Rows(0).Cells(i).Value = Arreglo(i)

Next

End Sub

Validación de entradas (procedimiento de evento en DGVA):

Si el valor ingresado en la celda actual es numérico lo convierte a tipo entero de otro modo lo

establece en cero.

Private Sub DGVA_CellEndEdit(ByVal sender As Object, ByVal e As

System.Windows.Forms.DataGridViewCellEventArgs) Handles DGVA.CellEndEdit

If IsNumeric(DGVA.CurrentCell.Value) Then

Arreglo(e.ColumnIndex) = CInt(DGVA.CurrentCell.Value)

Else

MsgBox("Valor no permitido", MsgBoxStyle.Exclamation)

DGVA.CurrentCell.Value = 0

End If

End Sub

Guardar el arreglo actual:

(Doble clic en el botón para generar la plantilla del procedimiento de evento)


30

Private Sub btnSave_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnSave.Click

'Guarda el arreglo en un archivo secuencial

If SaveFD.ShowDialog = Windows.Forms.DialogResult.OK Then

'Valor para el manejo del archivo

Dim FM As Short = FreeFile()

'Abre el archivo para escritura

FileOpen(FM, SaveFD.FileName, OpenMode.Output)

'Guarda el tamaño de N

PrintLine(FM, N)

'Guarda secuencialmente cada valor en el arreglo

For Each x As Integer In Arreglo

PrintLine(FM, x)

Next

FileClose(FM)

MsgBox("Arreglo guardado", MsgBoxStyle.Information)

End If

End Sub

Private Sub btnOpen_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnOpen.Click

If OpenFD.ShowDialog = Windows.Forms.DialogResult.OK Then

Dim FM As Short = FreeFile()

'Abre el archivo para lectura secuencial

FileOpen(FM, OpenFD.FileName, OpenMode.Input)

'Lee el primer valor (N)

N = LineInput(FM)

NumN.Value = N

CreaArreglo()

'Asigna sus valores secuencialmente:

Dim x As Integer

For i As Integer = 0 To N - 1

x = LineInput(FM)

Arreglo.SetValue(x, i) 'Equivale a Arreglo(i) = x

Next

FileClose(FM)

Valores()

End If

End Sub

Probar la aplicación creando diferentes arreglos, guardándolos y recuperándolos.

Aplicación de arreglos.

Ejemplo:

La compresión de un arreglo a veces implica eliminar los elementos que se repiten y mostrar los

valores que permanecen en la misma secuencia.

Si el arreglo es:

15 9 10 4 15 10 3 4 15 20

Al comprimirlo resultaría en:

15 9 10 4 3 20


31

Se asume que el arreglo existe y tiene valores (por lo que N es también conocida).

Algoritmo:

1. Hacer m 0 (contador de elementos eliminados)

2. Recorrer el arreglo para i 0, 1, … , N – 2 (hasta el penúltimo elemento).

3. Recorrer el arreglo hacia adelante para j i + 1, i + 2, … , i + (N – 1) (hasta el último

elemento)

a. Si A[i] no es nada (Si A[j] ≠ Nada entonces A[j] Nada: m m + 1

4. Crear el arreglo temporal de resultados: B[N – m]

5. Llenarlo con los valores del arreglo original diferentes de nada.

6. Mostrarlo.

El control DGV permite ingresar y

modificar los datos de arreglo

directamente.

Arreglo inicial.

Es importante expresar el

algoritmo en un lenguaje natural

(español, por ejemplo) separando los pasos consecutivos que han de seguirse usando expresiones

algorítmicas para denotar el cómo hacerlo de manera que se pueda resolver cualquier problema

similar. Resolver el problema directamente usando papel y lápiz para poder tener una base de

comprobación a la solución.

Arreglo comprimido ( )

Private Sub btnComprimir_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnComprimir.Click

Dim i, j, m As Integer

m = 0 '...[1]

'[2]

Nuevo botón

agregado.


32

For i = 0 To Arreglo.GetUpperBound(0) - 1

'[3]

For j = i + 1 To Arreglo.GetUpperBound(0)

If Not Arreglo(j) Is Nothing Then

'[3a]

If Arreglo(i) = Arreglo(j) Then

Arreglo(j) = Nothing

m += 1

End If

End If

Next

Next

'[4]

Dim B() As Object

ReDim B(N - m - 1)

j = 0

For i = 0 To Arreglo.GetUpperBound(0)

If Not Arreglo(i) Is Nothing Then

B(j) = Arreglo(i)

j += 1

End If

Next

'Establece nuevos valores

'[5]

NumN.Value = N - m - 1

CreaArreglo()


Arreglo(i) = B(i)

Next

'[6]

Valores()

End Sub

Ejercicio: Dado un polinomio de la forma:

Usando un arreglo para los coeficientes ai, encontrar el valor de una expresión y diferentes valores

de X (X1, X2, …)

Solución:

Sea

Para valores de X = 1, 2 y 3 la solución sería:

Para este caso, el arreglo de coeficientes quedaría:

0 1 2 3

3 4 -2 2


33

Lo primero que debe plantearse es que tamaño de arreglo usar. Una vez que los coeficientes son

asignados usando los valores de sus posiciones se puede resolver la expresión para valores de X

dados.

La solución puede presentarse como:

Cada valor de X es ingresado usando un control InputBox:

Algoritmo.

1. Establecer el tamaño del arreglo en base al grado del polinomio (m). N m + 1.

2. Crear el arreglo y asignar los coeficientes. A[i] ai

3. Inicializar el valor de la expresión: P 0

4. Leer un valor para X

5. Iterar sobre el arreglo para cada valor de X (Si X > 0) (A[i], i 0, 1, …, N)

k m - i

P P + A([i]*X ↑k

6. Mostrar resultado.

Private Sub btnPoli_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnPoli.Click

Dim X As Integer = Val(InputBox("Valor de X", "Datos", "1"))

If X > 0 Then


34

Dim P As Long = 0

Dim m, i, k As Integer

m = N - 1


k = m - i

P += Arreglo(i) * X ^ k

Next

Dim Salida As String = "P(" + X.ToString + ") = " + P.ToString

With txtSol

.SelectionStart = .Text.Length

.SelectedText = Salida + vbCrLf

End With

End If

End Sub

Ejercicios propuestos:

1.- Un número entero positivo en base decimal se puede convertir a su base binaria u octal con

divisiones sucesivas entre la base (2 u 8) y acumulando los residuos en un arreglo hasta que el

cociente se cero.

Por ejemplo: Sea Número 1024

Dividendo Divisor Cociente Residuo Arreglo de residuos

1024 2 512 0 0

512 2 256 0 0 0

256 2 128 0 0 0 0

178 2 64 0 0 0 0 0

64 2 32 0 0 0 0 0 0

32 2 16 0 0 0 0 0 0 0

16 2 8 0 0 0 0 0 0 0 0

8 2 4 0 0 0 0 0 0 0 0 0

4 2 2 0 0 0 0 0 0 0 0 0 0

2 2 1 0 0 0 0 0 0 0 0 0 0 0

1 2 0 1 0 0 0 0 0 0 0 0 0 0 1

0 1 2 3 4 5 6 7 8 9 10

El número binario resultante se obtiene leyendo el arreglo de derecha a izquierda:

10000000000

Escribir el procedimiento de evento para esta tarea (Base 2 u 8).

Sugerencia:


35

Botón nuevo btnBaseN.

RadioButtons

rbBin, propiedad Checked = True

rbOctal.

Dado que estas conversiones de base son utilizadas frecuentemente en otras soluciones es

conveniente crear este procedimiento en una función pública dentro de un módulo:

Agregar un módulo a esta aplicación (Menú Proyecto Agregar módulo) dándole un nombre a éste:

Module ModMisMetodos

Public Function BaseN(ByVal Num As Long, ByVal Base As Short, ByRef Arr() As Object) As

String

Dim Salida() As Char

Dim N As Short = 16

Dim Cociente As Long = 0, P As Short = -1, Res As Short

ReDim Salida(N)

'Solución al problema:

‘Código a desarrollar…

Do

'1.- Obtener el cociente '2.- Obtener el residuo y 'guardarlo en Salida(P) '3.- Num = Cociente '4.- Repetir desde el paso 1 hasta 'que el cociente sea cero.

Loop Until Cociente = 0

Dim sTemp As String = ""

'Se lee el arreglo resultante

'de derecha a izquierda para

'formar la cadena de salida

For i = P To 0 Step -1

sTemp += Salida(i)

Next

'Ajusta el tammaño del arreglo Arr()

'conservando el valor de sus elementos

ReDim Preserve Arr(P + 1)

Return sTemp

End Function

End Module

La función BaseN recibe la información necesaria para convertir un número decimal a su equivalente

en binario u octal.

Salida() es un arreglo temporal de tipo

Char en donde se almacenarán los

residuos (convirtiéndolos con el método

ToString..

N representa el tamaño del arreglo

anterior y no afecta a los objetos

definidos en la forma de origen (por ser

un objeto local dentro de un módulo.

P es un apuntador a los elementos de

arreglo temporal.

Res es el residuo de la división entera (\)

del número decimal entre la base.


36

Parámetro Tipo Uso

Num Entero

largo

El número decimal que se va a usar. Se pasa como una copia del valor

ingresado en la forma principal (ByVal), por lo tanto el valor original no es

afectado.

Base Entero

corto

Base a la que se convierte (2 u 8).

Arr() Objeto El arreglo principal de esta aplicación. Al pasarse por referencia (ByRef) los

cambios que se hagan en afectan al arreglo inicial.

Tal función se invoca desde la aplicación principal de esta manera:

Private Sub btnBaseN_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnBaseN.Click

Dim Numero As Long

Dim Base As Short = 2 'Base 2 u 8

Numero = Val(InputBox("Número decimal", "Cambio de base", "0"))

txtSol.Clear()

If Numero > 0 Then

ReDim Arreglo(64) 'Tamaño inicial del arreglo

Dim sCurrSel As String = rbBin.Text

If rbOctal.Checked Then

Base = 8

sCurrSel = rbOctal.Text

End If

txtSol.Text = Numero.ToString + " -->" + BaseN(Numero, Base, Arreglo) + " (" +

sCurrSel + ")"

N = Arreglo.GetUpperBound(0)

NumN.Value = N

CreaArreglo(False)

Else

MsgBox("Valor no permitido", MsgBoxStyle.Information)

End If

End Sub

Ejecución8 :

8 Usar la calculadora de Windows ® en modo científico para comprobar sus resultados.


37

2.- Problema de caracteres.

La clase ArrayList

El uso de instrucciones ReDim y ReDim Preserve consume recursos de la computadora, además debe

incluirse código cuando debe modificarse el tamaño de un arreglo. La solución a este problema es el

uso de un tipo de arreglo que se dimensiona automáticamente cuando alcanza su límite de

almacenamiento físico. Este arreglo se llama ArrayList y forma parte de la colección del espacio de

nombres en System.Collections en la librería del marco .NET.

Un objeto ArrayList tiene la capacidad de almacenar su tamaño como una propiedad cuyo valor

inicial es 16. Cuando el número de elementos en un ArrayList alcanza este límite, la propiedad

Capacidad agrega otros 16 elementos. El uso de un ArrayList en situaciones donde el número de

elementos puede crecer o disminuir, es más eficiente que usar comandos Redim o Redim Preserve

en arreglos estándar.

Estos son algunos de los métodos y propiedades que incluye la clase ArrayList:

Add() Agrega un elemento a la lista

AddRange Agrega los elementos de una colección al fina de un ArrayList

Capacity Almacena el número de elementos que un ArrayList puede manejar

Clear() Elimina todos los elementos del ArrayList

Contains() Determina si un ítem específico existe en el arreglo

CopyTo() Copia el ArrayList ó un segmento de éste a un arreglo

Count Es el número de elementos actualmente en la lista

GetEnnumerator Regresa un enumerador para iterar sobre un ArrayList

GetRange() Devuelve un subconjunto del ArrayList como otro ArrayList

IndexOf() Devuelve el índice de la primera ocurrencia de un ítem específico

Insert Inserta un elemento en un índice especificado


38

InsertRange() Inserta los elementos de una colección dentro de un ArrayList comenzando en un

índice específico

Item() Obtiene o establece un elemento en el índice especificado

Remove() Elimina la primera ocurrencia de un ítem específico

RemoveAt() Elimina el elemento con el índice especificado

Reverse() Invierte el orden de los elementos en el ArrayList

Sort() Ordena alfabéticamente los elementos en ele arreglo

ToArray() Copia los elementos de un ArrayList a un arreglo

TrimToSize() Fija la capacidad del ArrayList al número exacto de sus elementos

Ejemplo uso.- Se desea ayudar al profesor con el manejo de su grupo. Donde se requiere un objeto

Alumno con las siguientes características:

Alumno (Serializable)

Propiedades Tipo

Nombre Texto

Apellido Texto

Calif Entero corto (rango 0 a 100)

Métodos

MiNombre Apellido + Nombre (Texto)

La lista del curso es una Colección de alumnos que luego se pasa a un ArrayList para su mejor

manejo. Crear una clase que agregue algunos métodos al ArrayList para:

Ubicar al primer alumno de la lista con mayor y menor calificación.

Mostrar el promedio general del grupo.

Crear una lista de alumnos aprobados y otra de alumnos reprobados y mostrar sus

promedios.

La forma para esto puede ser como se muestra:


39

Objetos requeridos (Por secciones):

GroupBox (Contenedor GpoAlumno):

txtApe (TextBox, CharacterCasing

=Upper)

txtNom (igual a la anterior)

NumCalif (NumericUpDown Maximum

=100)

btnOK (Button).

txtLoc (igual las anteriores)

btnFind (Button )

DGV (DataGridView con tres columnas de

las cuales la tercera es numérica sin

decimales)

btnToArrayList

Botones btnSave y btnOpen para serializar y deserializar la colección 9 (opcionales).

9 Francesco Balena. Programming Microsoft Visual Basic 2005: The Languaje. Microft Press.


40

GroupBox (GpoAL)

DGVAL (DataGridViewCol con dos

columnas la última de las cuales es

numérica sin decimales).

DGVR (copia de la anterior).

btnMayor (Button)

btnMenor (Button)

labProm (Label con BorderStyle =

Fixed3D y texto 0.0 alineado a la

derecha, AutoSize = False)

labProm2 (copia de la anterior).

btnRepro (Button)

btnApro (Button)

labCalMayot (Label, BorderStyle = Fixed3D, AutoSie =False)

labCalMento (copia de la anterior)

La ventana de propiedades de

un DataGridView se abre con

un clic en la esquina superior

derecha:

El valor numérico de la

columna Calif se establece con

las propiedades

DefaultCellStyle.

Funcionamiento:


41

Se crea una colección de alumnos10:

Luego se llena un ArrayList con el nombre completo del alumno y su calificación

DGVAL

Se muestra el promedio general del grupo.

El botón

Selecciona de la lista anterior aquellos alumnos con calificación menor a 70

(calificación reprobatoria y los muestra en DGVR.

10 En este ejemplo no se agregaron botones para edición o para eliminar algún objeto de la colección. Puede

agregarlos si lo desea.


42

Se muestra el promedio de esta lista.

El botón

Hace lo mismo pero para los alumnos que aprobaron el curso (Calif >=70).

CODIGO:

Clase Alumno:

<System.Serializable()> Public Class CAlumno

Private mvarApellido As String

Private mvarNombre As String

Private mvarCalif As Short

Property Apellido() As String

Get

Return mvarApellido

End Get

Set(ByVal value As String)

mvarApellido = value

End Set


43

End Property

Property Nombre() As String

Get

Return mvarNombre

End Get


mvarNombre = value

End Set

End Property

Property Calif() As Short

Get

Return mvarCalif

End Get

Set(ByVal value As Short)

mvarCalif = value

End Set

End Property

Public Function MiNombre() As String

Return mvarApellido + " " + mvarNombre

End Function

End Class

Clase para agregar más funcionalidad al ArrayList:

Public Class CMiListaArreglo

Public Function Promedio(ByRef ElArreglo As ArrayList) As Single

Dim Alumno As New CAlumno

Dim SumCal As Integer = 0

For Each Alumno In ElArreglo

SumCal += Alumno.Calif

Next

Dim Prom As Single = SumCal / ElArreglo.Count

Return Prom

End Function

Public Function CalifMayor(ByRef ElArreglo As ArrayList) As CAlumno

Dim Alumno As CAlumno = Nothing

Dim Mejor As CAlumno = Nothing

Dim Mayor As Short = 0


If Alumno.Calif > Mayor Then

Mejor = Alumno

Mayor = Alumno.Calif

End If

Next

Return Mejor

End Function

Public Function CalifMenor(ByRef ElArreglo As ArrayList) As CAlumno

Dim Alumno As CAlumno = Nothing

Dim Peor As CAlumno = Nothing

Dim Menor As Short = 100


If Alumno.Calif < Menor Then

Peor = Alumno

Menor = Alumno.Calif

End If

Next

Return Peor

End Function

Public Function ListaRep(ByRef ElArreglo As ArrayList) As ArrayList

Dim Repro As New ArrayList

For Each A As CAlumno In ElArreglo

If A.Calif < 70 Then

Repro.Add(A)

End If

Next

Repro.TrimToSize()

Return Repro

End Function


44

Public Function ListaApro(ByVal ElArreglo As ArrayList) As ArrayList

Dim Apro As New ArrayList

For Each A As CAlumno In ElArreglo

If Not A.Calif < 70 Then

Apro.Add(A)

End If

Next

Apro.TrimToSize()

Return Apro

End Function

End Class

Forma (frmArrayList):

Public Class frmArrayList

Private ColDeAl As Collection, Alumno As CAlumno

Private ElArregloL As ArrayList, ObjetoArr As New CMiListaArreglo

Public Sub New()

' Llamada necesaria para el Diseñador de Windows Forms.

InitializeComponent()

' Agregue cualquier inicialización después de la llamada a InitializeComponent().

Dim sRuta As String = My.Application.Info.DirectoryPath + "\Colecciones"



End If

'Solo en caso de implementar serialización (Filter Archivos binarios (*.bi)



End Sub

Private Sub frmArrayList_Load(ByVal sender As System.Object, ByVal e As


ElArregloL = New ArrayList

ColDeAl = New Collection

End Sub

Para agregar alumnos a la colección:


Handles btnOK.Click

On Error GoTo Repetido

Alumno = New CAlumno

With Alumno

.Apellido = txtApe.Text.Trim

.Nombre = txtNom.Text.Trim

.Calif = NumCalif.Value

End With

'El nombre completo del alumno se toma como clave, lo que evita que se dupliquen

'en la colección

ColDeAl.Add(Alumno, Key:=Alumno.MiNombre)

AddToGrid(Alumno, DGV)

txtNom.Clear()

txtApe.Clear()

txtApe.Focus()

Exit Sub

Repetido:

If Err.Number = 457 Then

MsgBox("Ese alumno ya está en la colección", MsgBoxStyle.Information)

Resume Next

Else


45

MsgBox(Err.Description, MsgBoxStyle.Exclamation)

End If

MsgBox(Err.Description + " " + Err.Number.ToString, MsgBoxStyle.Information)

End Sub

Para agregar el alumno a un renglón de DGV:

Private Sub AddToGrid(ByVal Alumno As CAlumno, ByRef ElGrid As DataGridView)

ElGrid.Rows.Add()

Dim R As DataGridViewRow = ElGrid.Rows(ElGrid.RowCount - 1)

R.Cells(0).Value = Alumno.Apellido

R.Cells(1).Value = Alumno.Nombre

R.Cells(2).Value = Alumno.Calif

End Sub

Copiar la colección a un ArrayList :

Private Sub btnToArrayL_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnToArrayL.Click

If ColDeAl.Count > 0 Then

For Each A As CAlumno In ColDeAl

ElArregloL.Add(A)

ToGrid2(A, DGVAL)

Next

labProm.Text = ObjetoArr.Promedio(ElArregloL).ToString("N1")

End If

End Sub

Para colocar el alumno en un renglón de DGVAL:

Private Sub ToGrid2(ByVal A As CAlumno, ByRef ElGrid As DataGridView)

ElGrid.Rows.Add()

Dim R As DataGridViewRow = ElGrid.Rows(ElGrid.RowCount - 1)

R.Cells(0).Value = A.MiNombre

R.Cells(1).Value = A.Calif

End Sub

Para determinar si un alumno ya está en la colección:

Private Sub btnFind_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnFind.Click

Try

Dim sAlumno As String = txtLoc.Text.Trim

If sAlumno.Length > 0 Then

If ColDeAl.Contains(sAlumno) Then

MsgBox("Ese alumno sí está en la colección", MsgBoxStyle.Information)

Else

MsgBox("Ese alumno no está en la colección", MsgBoxStyle.Information)

End If


46

End If


MsgBox(ex.Message, MsgBoxStyle.Information)

End Try

End Sub

Obtener lista de alumnos reprobados y colocar cada objeto en DGVR:

Private Sub btnRepro_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnRepro.Click

DGVR.Rows.Clear()

If ElArregloL.Count > 0 Then

Dim Reprobados As ArrayList = ObjetoArr.ListaRep(ElArregloL)

For Each A As CAlumno In Reprobados

ToGrid2(A, DGVR)

Next

labProm2.Text = ObjetoArr.Promedio(Reprobados).ToString("N1")

End If

End Sub

De la misma manera, la lista de alumnos reprobados.

Private Sub btnApro_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnApro.Click

DGVR.Rows.Clear()

If ElArregloL.Count > 0 Then

Dim Aprobados As ArrayList = ObjetoArr.ListaApro(ElArregloL)

For Each A As CAlumno In Aprobados

ToGrid2(A, DGVR)

Next

labProm2.Text = ObjetoArr.Promedio(Aprobados).ToString("N1")

End If

End Sub

Ejercicio: Modificar la clase CMiListaArreglo para que maneje diferentes cursos y crear una

aplicación de Windows® que la implemente.

Arreglos de dos dimensiones.

Un arreglo de dos dimensiones (matriz) es un objeto (del tipo Array) que tiene N renglones y M

columnas. En álgebra lineal una matriz es simplemente un arreglo rectangular de elementos y se

dice que su orden es N x M.

A(N, M)

Y cada elemento se indica por A(i, j) donde 0 < = i < = N y 0 < = j < = M.

a11 a12 … ain

a21 a22 … a2n

A = … … … …

an1 an2 … ann


47

Por ejemplo:

En VB.NET para crear arreglos con dos dimensiones se usa la instrucción Dim Matriz( , ) para su

manejo dinámico. Una vez conocidos N y M se forma el arreglo:

Dim Matriz(N M, ) As [Tipo] crea una matriz A(N, M) en donde (al igual que en los arreglos de una

dimensión) el primer renglón y la primera columna tienen el índice 0.

Así:

N=3 y M = 3

0 1 2

0 1 5 2

1 1 0 2

2 1 1 2

Manejo de matrices en VB.NET.

Crear un proyecto nuevo y cargar el módulo desarrollado anteriormente:

Menú Proyecto Agregar elemento existente (localizarlo en la carpeta \WinArreglos).

Forma principal (frmMatrix)


48

Elementos de la forma:

GroupBox (GpoH) sin texto (Text).

Controles numéricos

(NumericIpDown) de nombre NumN. Crear primero este control y después copiarlo y pegarlo en la

forma modificando luego sus propiedades Name a NumM y NumK.

Propiedades del control numéricos NumN.

Propiedad Valor

Maximum 10

Minimum 2

TextAlign Center


49

Tres objetos del tipo DataGridViw en

donde primero se agrega el primero con el

nombre DGVA, se establecen sus

propiedades como se indica en la tabla.

Luego se copia (al portapapeles) y se pega

modificando sus nombres a DGVB y DGVR.

Éste último cambia su propiedad ReadOnly

True.

Propiedades comunes de los controles DataGridView.

Propiedad Valor

AllowUserToAddRows False

AllowUserToResizeRows False

AutCellsColumnMode AllCells

MultiSelect False

Tag11 “A” para DGVA, “B” para DGVB

btnSuma

btnProd

btnInvA

GroupBox

Name = GpoOp

Enabled = False

btnGuardar

btnAbrir

11 Sin comillas.

En esta ventana se podrán probar

diferentes algoritmos que muestran el

manejo de este tipo de arreglos. Se

podrán guardar en archivos y recuperarse

en otro momento.

Esta forma manejará tres matrices:

A[N, M), B([M, K) y R[ , ] cuyo orden

dependerá del resultado de la operación

que se realice.

Suma

Multiplicación

Inversa

Otros problemas a resolver.


50

btnClose

Operaciones con matrices.

Suma de dos matrices (A + B).- Esta operación sólo está definida para matrices del mismo orden,

esto es, con el mismo número de renglones y columnas y genera otra matriz (la suma) del mismo

orden.

Cada elemento de la matriz resultante se obtiene por:

Por ejemplo:

12

Es decir, cada elemento de la suma se obtiene sumando los elementos correspondientes en A y B en

sus respectivas posiciones.

Producto de dos matrices A x B.

El producto de dos matrices A y B sólo está definido si el número de renglones de B es igual al

número de columnas de A.

En donde cada elemento de R se obtiene por:

Por ejemplo:

Funcionalidad de la forma:

En todos los problemas desarrollados a lo largo de este texto se guardarán los datos en archivos

que se localizarán siempre en una carpeta especialmente creada dentro del directorio donde reside

12 Es matriz resultante.


51

la aplicación. Con el fin agilizar este procedimiento se crea en el módulo para de esta manera usarlo

en otras aplicaciones.

Public Function SetTestPath(ByVal sRuta As String) As String

sRuta = My.Application.Info.DirectoryPath + sRuta + My.Application.Info.ProductName



End If

Return sRuta

End Function

Código inicial de la forma:

Public Class frmMatrix

Private MatA(,), MatB(,), MatR(,) As Single

Private N, M, K As Short

Private Sub frmMatrix_Load(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles MyBase.Load

Dim Ruta As String

Ruta = SetTestPath("\Archivos de Prueba_")

SaveFD.InitialDirectory = Ruta

OpenFD.InitialDirectory = Ruta

End Sub

El siguiente procedimiento ajusta las propiedades de los controles de datos (DataGridView) para

usarlos tanto pata ingresar los datos de las matrices A y B como para mostrar resultados en R:

El procedimiento CreaGrid recibe por referencia13 el control que se va modificar (DataGridView) así

como el número de renglones y columnas requeridos; Se pasan como parámetros como ElGrid ,

iRows,e iCols. De esta manera opera sobre los controles DGVA, DGVB y DGVR.

El procedimiento VerMatriz cualquier matriz (LaMatriz) en uno de los DatagridView (ElGrid) de la

forma.

Private Sub CreaGrid(ByRef ElGrid As DataGridView, ByVal iRows As Short, ByVal iCols As

Short)

With ElGrid

.RowCount = iRows

.ColumnCount = iCols

For Each Kol As DataGridViewColumn In ElGrid.Columns

Kol.HeaderText = Kol.Index

Kol.DefaultCellStyle.Alignment = DataGridViewContentAlignment.TopCenter

Next

End With

End Sub

Private Sub VerMatriz(ByRef LaMatriz(,) As Single, ByRef ElGrid As DataGridView)

Dim i, j As Short

For i = 0 To LaMatriz.GetUpperBound(0) 'Limite de renglones

For j = 0 To LaMatriz.GetUpperBound(1) 'Limite de columnas

ElGrid.Rows(i).Cells(j).Value = LaMatriz(i, j)

Next

Next

End Sub

13 Esto es, los cambios hechos en el procedimiento afectan al control en la forma.


52

Private Sub btnOK_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnOK.Click

N = NumN.Value

M = NumM.Value

K = NumK.Value

ReDim MatA(N - 1, M - 1), MatB(M - 1, K - 1)

CreaGrid(DGVA, N, M)

CreaGrid(DGVB, M, K)

VerMatriz(MatA, DGVA)

VerMatriz(MatB, DGVB)

GpoOp.Enabled = True

End Sub



'Prepara la forma para otras matrices

DGVA.RowCount = 0

DGVA.ColumnCount = 0

DGVB.RowCount = 0

DGVB.ColumnCount = 0

DGVR.RowCount = 0

DGVR.ColumnCount = 0

GpoOp.Enabled = False

ReDim MatA(0, 0), MatB(0, 0), MatR(0, 0)

End Sub

Hasta este punto, al ejecutar la aplicación debe verse así al hacer clic en [Aceptar]:

Validación de los datos de entrada: Todo valor ingresado debe ser numérico.

El procedimiento de evento opera sobre DGVA y/o DGVB y asigna el valor ingresado a la matriz que

representa (A ó B).

Private Sub DGVA_CellEndEdit(ByVal sender As Object, ByVal e As

System.Windows.Forms.DataGridViewCellEventArgs) Handles DGVA.CellEndEdit _

, DGVB.CellEndEdit

Dim ElGrid As DataGridView = sender

If Not IsNumeric(ElGrid.CurrentCell.Value) Then

MsgBox("Valor no permitido", MsgBoxStyle.Exclamation)

ElGrid.CurrentCell.Value = 0


53

ElseIf ElGrid.Tag = "A" Then

MatA(e.RowIndex, e.ColumnIndex) = ElGrid.CurrentCell.Value

Else

MatB(e.RowIndex, e.ColumnIndex) = ElGrid.CurrentCell.Value

End If

End Sub

Procedimientos para guardar y abrir matrices (en y desde archivos).- Las matrices pueden

almacenarse también en archivos secuenciales.

Ya que el código necesario para guardar las matrices A y B es repetitivo, se crea un procedimiento

común:

Private Sub SaveMatrix(ByRef LaMatriz(,) As Single, ByVal NA As Short)

Dim i, j As Short

For i = 0 To LaMatriz.GetUpperBound(0)

For j = 0 To LaMatriz.GetUpperBound(1)

PrintLine(NA, LaMatriz(i, j))

Next

Next

End Sub

Entonces



Try


Dim NA As Short = FreeFile()

FileOpen(NA, SaveFD.FileName, OpenMode.Output)

'Primero se almacena el orden de la matriz

PrintLine(NA, N)

PrintLine(NA, M)

PrintLine(NA, K)

'Luego cada matriz en recorrido por renglones

SaveMatrix(MatA, NA)

SaveMatrix(MatB, NA)

FileClose(NA)

MsgBox("Matrices guardadas", MsgBoxStyle.Information)

End If



FileClose()

End Try

End Sub

Private Sub btnAbrir_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnAbrir.Click

Try

Dim i, j As Short



FileOpen(NA, OpenFD.FileName, OpenMode.Input)

'Leer el orden de las matarices

N = LineInput(NA)

M = LineInput(NA)

K = LineInput(NA)


54

NumN.Value = N

NumM.Value = M

NumK.Value = K

'Crear arreglos

ReDim MatA(N - 1, M - 1), MatB(M - 1, K - 1)

CreaGrid(DGVA, N, M)

CreaGrid(DGVB, M, K)

'Leer elementos de A

For i = 0 To MatA.GetUpperBound(0)

For j = 0 To MatA.GetUpperBound(1)

MatA(i, j) = LineInput(NA)

Next

Next

'Leer elementos de B

For i = 0 To MatB.GetUpperBound(0)

For j = 0 To MatB.GetUpperBound(1)

MatB(i, j) = LineInput(NA)

Next

Next

VerMatriz(MatA, DGVA)


FileClose(NA)

GpoOp.Enabled = True

End If



FileClose()

End Try

End Sub

Probar con diferentes valores en diferentes matrices estos procedimientos.

Suma de A + B:

Con el fin de generalizarlo y poder usarlo en otras aplicaciones, este procedimiento se crea en el

módulo:

Public Sub SumaAB(ByRef A(,) As Single, ByRef B(,) As Single, ByRef R(,) As Single)

Dim i, j As Short

For i = 0 To A.GetUpperBound(0)

For j = 0 To A.GetUpperBound(0)

R(i, j) = A(i, j) + B(i, j)

Next

Next

End Sub

Todas las matrices se pasan por referencia para que los cambios en ellas se reflejen en la ventana

desde donde se invoca el procedimiento.

En la forma principal:

Private Sub btnSuma_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnSuma.Click

ReDim MatR(N - 1, M - 1)

SumaAB(MatA, MatB, MatR)

CreaGrid(DGVR, N, M)

VerMatriz(MatR, DGVR)

End Sub

Prueba:


55

Producto A x B.

Al igual que la suma, este procedimiento se crea en el módulo para su uso en el futuro.

Public Sub ProdAB(ByRef A(,) As Single, ByRef B(,) As Single, ByRef R(,) As Single)

Dim i, j, c As Short

For i = 0 To A.GetUpperBound(0)

For c = 0 To B.GetUpperBound(1)

For j = 0 To A.GetUpperBound(1)

R(i, c) += A(i, j) * B(j, c)

Next

Next

Next

End Sub

Y se invoca desde la aplicación como:

Private Sub btnProd_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnProd.Click

ReDim MatR(N - 1, K - 1)

ProdAB(MatA, MatB, MatR)

CreaGrid(DGVR, N, K)

VerMatriz(MatR, DGVR)

End Sub


56

Problemas:

1.- Transpuesta. La transpuesta de una matriz se obtiene intercambiando renglones por columas:

Su transpuesta es:

Desarrollar un procedimiento que encuentre la transpuesta de una matriz A.

2.- La inversa de una matriz A(N, M) en donde N = M y denotada como A-1 es una matriz del mismo

orden tal que:


57

En donde I representa a la matriz unidad (cuyos elementos en la diagonal principal tienen el valor de

1 y todos los demás son 0.

Ejemplo:

Investigar diferentes métodos para encontrar la inversa de una matriz A. Implementar uno en el

Módulo. La inversa (si existe) debe guardarse en el arreglo B, de manera que se pueda verificar por

medio del producto AxB.


58

Private Sub btnInvA_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnInvA.Click

If N = M Then

ReDim MatR(N - 1, M - 1)

CreaGrid(DGVR, N, N)

'Procedimiento a desarrollar:

InversaA(MatA, MatB, MatR)


End If

End Sub

3.- Aplicaciones: Modelo de Regresión Lineal Múltiple. En estadística, cuando se considera que el

resultado de alguna variable (Y) depende del valor de otros valores (Xj) es posible desarrollar un

modelo que explique esa relación. El modelo más sencillo se conoce como el modelo de regresión

lineal múltiple. Definido como:

Y un método muy efectivo para obtener esta ecuación a partir de un conjunto de observaciones (en

algún experimento) es usando matrices:

Ejemplo: Se tienen los siguientes datos (observados):

Y X1 X2

3 3 5

1 1 4

8 5 6

3 2 4

5 4 6

El método14 consiste en crear una matriz X con los datos Xi,j agregando una columna inicial cuyos

valores serán siempre 1.

Matriz X:

1 3 5

1 1 4

1 5 6

1 2 4

1 4 6

14 Econometric Methods. J. Johnston. McGrawHill.


59

Y un arreglo Y(N):

3

1

8

3

5

Luego se obtiene la matriz XX de multiplicar XtX:

Luego el vector Xy de Xt Y:

Las ecuaciones normales son entonces:

Si XX-1 es la inversa de XX, entonces:

Y la ecuación resultante es:


60

A partir de la cual se puede estimar Yc conociendo cualesquiera valores de X1 y X2.

Desarrollar un programa15 cuya entrada sea:

N= N° de observaciones (y, x1, …, xm)

M = N° de variables independientes Xj

Y su salida es la ecuación de regresión resultante:

Sugerencia.- Esta forma permite capturar los datos de M variables independientes y los valores de

Y. Al mismo tiempo crea los arreglos necesarios y los llena en tiempo de ejecución cada vez que se

ingresa un dato. El programa hace un uso intensivo de varios arreglos tanto bidimensionales como

unidimensionales. Utiliza además los métodos de multiplicación de matrices, cálculo de transpuesta

y de inversa de matrices desarrollados (y probados) en el programa anterior.

Descripción de la forma:

El proyecto de denominó RegresiónLinealMultiple, la forma de denominó

frmRLM y se importó el módulo ModMisMetodos desarrollado en la

aplicación previa.

Dos controles numéricos (NumericUpDow) denominados NumN y

NumM respectivamente con valores Minimum = 5, Maximum =

15 Llevar a este programa al módulo con las operaciones de multiplicación, inversa de una matriz desarrollado

en el programa anterior.


61

10 para el primero y 1 y 10 para el segundo. Además un botón (btnOK).

Control DataGridView:

Nombre= DGV

AllowUserToAddRows = False

AllowUserToReziseRows =

False

AutoSizeColumnMode =

AllCells

MultiSelect = False

Aquí se capturan los datos.


Nombre= DGVX

Mismas propiedades que el anterior más ReadOnly = True

Muestra el arreglo X.


Nombre = DGVY

Propiedades iguales al anterior.

Muestra el vector Y.


62

Controles DataGridView. Los dos primeros son copia de DGVX, los últimos dos se copian de DGVY.

Sus nombres son:

DGVXX (muestra el arreglo XX), DGVInv (muestra la inversa de XX), DGVXy (muestra el arreglo XY) y

DGVB (para mostrar los resultados – el vector B.

Es un TextBox con nombre txtEc, TextAlign = Center y ReadOnly = True. Sirve para mostrar la

ecuación resultante.

1. btnArreglos.- Muestra los valores de los arreglos X y Y. (Enabled = False).

2. btSave.- Guarda los datos iniciales (los arreglos X y Y). Enabled = False

3. btnOpen.- Recupera el archivo de datos.

4. btnNew.- Prepara la forma para nuevos datos.

btnStart.- Inicia el proceso de cálculos. Enabled = False.

btnClose.

Diálogos para guardar y abrir archivos: DefaultExt = dat, Filter =

Archivos de datos (*.dat)|*.dat. Con los nombres que aparecen en la

imagen.

Operación:

Se ingresa el número de datos observados y el total de variables x.

5 observaciones con dos variables X.

Al aceptar se crean los arreglos iniciales y se preparan

los DataGridView:

Se asignan los valores de 1 en la primera colimna (que además se establece

como sólo lectura).

Aquí se capturan los datos.


63

Cuando los datos son ingresados éstos son asignado a los

arreglos X ó Y usando el evento CellEndEdit.

Así, cuando se selecciona se mostrarán los

arreglos X y Y en sus respectivos DataGridView:

Se declaran loa arreglos más importantes y el constructor de la forma, crea un directorio por defecto

para guardar datos:

Public Class frmRLM

Private X(,), XX(,) As Single

Private Y(), XY(), B() As Single

Private N, M As Integer

Public Sub New()




Dim sRuta As String = My.Application.Info.DirectoryPath + "\RLM"



End If



End Sub

Aquí se dimensionan algunos de los arreglos y se forman los DataGridView para visualizarlos y para

capturar los datos:


Handles btnOK.Click

With DGV

N = NumN.Value

M = NumM.Value

.RowCount = N

.ColumnCount = M + 2

ReDim X(N - 1, M), Y(N - 1)

Dim i, j As Integer

For i = 0 To X.GetUpperBound(0)

X(i, 0) = 1

Next

For j = 0 To DGV.ColumnCount - 2

.Columns(j).HeaderText = "X" + j.ToString

.Columns(j).DefaultCellStyle.Alignment =

DataGridViewContentAlignment.TopRight


64

Next

.Columns(j).HeaderText = "Y"

.Columns(j).DefaultCellStyle.Alignment = DataGridViewContentAlignment.TopRight

.Columns(0).ReadOnly = True

End With

DGVX.RowCount = N

DGVX.ColumnCount = M + 1

DGVY.RowCount = N

DGVY.ColumnCount = 1

btnArreglos.Enabled = True

VerArreglos()

End Sub

Cuando se tienen los arreglos iniciales, pueden guardarse:

Los datos se almacenan en un archivo secuencial en e siguiente orden:

1. Valores de N y M.

2. El arreglo X.

3. El arreglo Y.

Private Sub btnSave_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnSave.Click


Try



PrintLine(NA, N)

PrintLine(NA, M)

Dim i, j As Integer


'se omite la 1a columna

For j = 0 To X.GetUpperBound(1)

PrintLine(NA, X(i, j))

Next

Next

For i = 0 To Y.GetUpperBound(0)

PrintLine(NA, Y(i))

Next

FileClose(NA)

MsgBox("Arreglos guardados", MsgBoxStyle.Information)


MsgBox(ex.Message, MsgBoxStyle.Exclamation)

FileClose()

End Try

End If

End Sub

Los datos se leen en la misma secuencia en que se guardaron y se invoca al procedimiento del botón

Aceptar para crear los arreglos y formar los DataGridView iniciales. Al leer los datos, éstos son

asignados a sus arreglos y mostrados en DataGridView de datos (DGV).






N = LineInput(NA)


65

M = LineInput(NA)

NumN.Value = N

NumM.Value = M

btnOK.PerformClick()

Dim i, j As Short


For j = 0 To X.GetUpperBound(1)

X(i, j) = LineInput(NA)

DGV.Rows(i).Cells(j).Value = X(i, j)

Next

Next

For i = 0 To Y.GetUpperBound(0)

Y(i) = LineInput(NA)

DGV.Rows(i).Cells(DGV.ColumnCount - 1).Value = Y(i)

Next

FileClose(NA)

btnArreglos.PerformClick()

End If

End Sub

Private Sub btnArreglos_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnArreglos.Click

VerArreglo(DGVX, X)

VerVector(DGVY, Y)

btnSave.Enabled = True

btnStart.Enabled = True

End Sub

Private Sub VerArreglo(ByRef ElGrid As DataGridView, ByRef Arreglo(,) As Single)

Dim i, j As Integer


For j = 0 To Arreglo.GetUpperBound(1)

ElGrid.Rows(i).Cells(j).Value = Arreglo(i, j)

Next

Next

End Sub

Private Sub VerVector(ByRef ElGrid As DataGridView, ByRef MiArr() As Single)

Dim i, j As Integer

For i = 0 To MiArr.GetUpperBound(0)

ElGrid.Rows(i).Cells(0).Value = MiArr(i)

Next

End Sub

Inicia todos los procedimientos enfocados a resolver el problema: Obtener la

ecuación de ajuste.

1. Crea la transpuesta de X.

2. La multiplica por X y por Y para obtener XX y Xy.

3. Obtiene la inversa de XX.

4. Multiplica la inversa por el arreglo Xy para obtener el arreglo de resultados, B.

5. Forma los DatagridVew necesarios para mostrar resultados intermedios y el resultado final –

el arreglo B.

6. Obtiene la ecuación resultante.

Crea los arreglos y forma los

DataGridVew iniciales.

Muestra los

arreglos.


66

Se asume que los procedimientos utilizados ya fueron creados y probados en la aplicación anterior.

En caso de que falte alguno (por ejemplo la multiplicación de un arreglo de dos dimensiones por

uno de una – un vector, habrá que desarrollarlo en ese módulo - ProdMatArr(InvXX, XY, B)

Realiza la multiplicación de la inversa de XX por el vector XY y el resultado lo coloca en B.

Private Sub btnStart_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnStart.Click

'Transpuesta:

Dim XT(M - 1, N - 1) As Single

ReDim XX(M, M)

Dim InvXX(M, M) As Single

ReDim B(M)

TranspuestaA(X, XT)

'Producto Transpuesta * arreglo X para obtener XX.

ProdAB(XT, X, XX)

ReDim XY(M)

'Transpuesta * Y para obtener Xy

ProdMatArr(XT, Y, XY)

DGVXX.RowCount = M + 1

DGVXX.ColumnCount = M + 1

DGVInv.RowCount = M + 1

DGVInv.ColumnCount = M + 1

'Cálculo de la inversa de XX.

InversaA(XX, InvXX)

VerArreglo(DGVXX, XX)

VerArreglo(DGVInv, InvXX)

DGVXy.RowCount = M + 1

DGVXy.ColumnCount = 1

DGVB.ColumnCount = 1

DGVB.RowCount = M + 1

'Producto de Inversa * XY para obtener el arreglo B

ProdMatArr(InvXX, XY, B)

VerVector(DGVXy, XY)

VerVector(DGVB, B)

'Mostrar el resultado.

ShoResult()

End Sub

Private Sub ShoResult()

Dim sEc As String = "Yc = " + B(0).ToString("N2")

Dim i As Short

For i = 1 To B.GetUpperBound(0)

If Math.Sign(B(i)) = 1 Then

sEc += " + "

End If

sEc += B(i).ToString("N2") + "X" + i.ToString

Next

txtEc.Text = sEc

End Sub

Si se completa esta aplicación, la competencia específica de esta unidad queda suficientemente

acreditada.


67

2 Recursividad.

Competencia especifica.- Comprender y aplicar la recursividad como herramienta de programación

en el manejo de las estructuras de datos.

DEFINICIÓN.- Se denomina recursividad a la capacidad de un procedimiento de llamarse a sí mismo.

Es el nombre que se da a la técnica de definir un conjunto o un proceso en términos de sí mismo16.

La función factorial cuyo dominio son los números naturales puede ser definida recursivamente

como:

En donde Factorial(N) está definida en términos de Factorial(N-1) que luego se vuelve en términos

de Factorial(N-2), etc., hasta que finalmente se alcanza Factorial (0) y su valor es entonces 1. Una

definición recursiva de un conjunto de procesos debe contener una definición explícita para los

valores particulares de sus argumentos de otro modo la definición podría nunca converger. La idea

básica es definir una función para todos sus argumentos de una manera constructiva usando

inducción. El valor de una función para un valor específico de su argumento puede calcularse en un

número finito de pasos usando la definición recursiva donde en cada paso de la recursión se acerca

más a la solución.

Ejemplo 1:


Module Module1

Sub Main()



Clear()

Dim N As Integer, F As Long

Write("N = ")

N = ReadLine()

16 Jean-Paul Tremblay. An Introduction to Data Structures with applications. McGrawHill.


68

F = Factorial(N)

Write("Factorial = ")

WriteLine(F)

ReadKey()

End Sub

Private Function Factorial(ByVal N As Integer) As Long

If N = 0 Then

Factorial = 1

Else

Factorial = N * Factorial(N - 1)

End If

End Function

End Module

Este tipo de recursión de conoce como función definida recursivamente (ó funciones recursivas

primitivas). Un segundo tipo de recursión es el uso recursivo de un procedimiento (recursión no

primitiva). Un ejemplo de esta recursión es la función de Ackerman, la cual se define como 1:

Ejemplo 2.


Module Module1

Sub Main()



Clear()

Dim N, M As Short

Write("N =")

N = ReadLine()

Write("M = ")

M = ReadLine()

Write("Valor de la función A =")

WriteLine(Ackerman(M, N))

ReadKey()

End Sub

Private Function Ackerman(ByVal M As Short, ByVal N As Short) As Integer

If M = 0 Then

Ackerman = N + 1

ElseIf N = 0 Then

Ackerman = Ackerman(M - 1, 1)

Else


69

Ackerman = Ackerman(M - 1, Ackerman(M, N - 1))

End If

End Function

End Module

Usar valores en el rango 0 – 3 para M y de 0 – 5 para N para evitar desbordamiento.

Ejemplo 3.

Escribir una función recursiva para convertir enteros decimales a su representación en otra base (B)

por medio de divisiones sucesivas. El nombre de esta función debe ser CONVERT con dos

parámetros formales Número y Base donde el primero denota al entero que se va a convertir y el

segundo es la base. El resultado se regresa como una cadena (texto).

Por ejemplo, para encontrar la representación en base 6 de 184 implica que se dividirá

repetidamente entre 6 y los residuos obtenidos son concatenados:

184 ÷ 6 4

30÷6 0

5÷6 5

El resultado es entonces 504

MaximizeBox = False


70

Objeto Propiedades Descripción

TextBox Name = txtNum, TextAlign = Center, Text =0 Captura el número a convertir

NumericUpDown Name = NumB, Maximum =9, Minimum =2,

TextAlign =Center

La base.

Button Name = btnConvert Inicia el cálculo.

Button Name = btnNew Nuevo cómputo.

Label Name = labResult, BorderStyle = Fixed3D,

BackColor = Honeydew, TextAlign = TopCenter.

Public Class frmConvert

Private Numero, Base As Integer

Private Sub btnConvert_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnConvert.Click

If IsNumeric(txtNum.Text) Then

Numero = CInt(txtNum.Text)

Base = NumBase.Value

labResult.Text = StrReverse(Convert(Numero, Base))

End If

End Sub

Private Function Convert(ByVal N As Integer, ByVal B As Integer) As String

Dim Cociente, Residuo As Integer

Cociente = Math.DivRem(N, B, Residuo)

If Cociente > 0 Then

Convert = Residuo.ToString + Convert(Cociente, Base)

Else

Convert = (N Mod B).ToString

End If

End Function



txtNum.Clear()

labResult.Text = ""

txtNum.Focus()

End Sub

End Class

Ejercicios:

1.- El máximo común divisor de dos enteros se define como (Algoritmo de Euclides):

Donde MOD (m, n) es el módulo aritmético17, esto es, el residuo de dividir m ÷ n.

Escribir la función recursiva para este caso.

17 En VB.NET esta operación puede ejecutarse como m Mod n.


71

El máximo común divisor de 27 y 9 es 9. Por ejemplo.

2.- Escribir una función recursiva para calcular la raíz cuadrada de un número. Leer una tripleta de

de números N, A y E, donde N es el número para el cual debe encontrarse la raíz cuadrada, A es una

aproximación de la raíz cuadrada y E es el error permitido en el resultado.

Usar las siguientes tripletas de números para pruebas:

N A E

2 1.0 0.001

3 1.5 0.001

8 2.5 0.001

225 14.2 .001

3.- En muchas aplicaciones es necesario conocer el número de particiones diferentes de un entero

N dado, es decir, de cuantas formas diferentes se puede expresar a N como una suma de sumandos

enteros. Si se denota como QMN al número de formas en las cuales un entero M puede ser expresado

como una suma, cada uno de estos sumandos no es mayor que N, entonces el número de

particiones de N pude definirse en términos de la siguiente función:


72

Escribir una función recursiva y usar los valores N = 3, 4, 5 y 6 como datos.

El número 5 se puede expresar de tres maneras con sumandos no mayores que 2.


73

3 Estructuras Lineales.

Competencia especifica.- Conocer, Identificar y aplicar ñas estructuras no lineales en la solución de

problemas del mundo real.

LISTAS.

Lista Ligada Simple.- Colección de una clase de objetos llamados nodos. Cada nodo está ligado a su

nodo sucesor en la lista usando una referencia (apuntador). Un nodo consiste en un campo para

almacenar datos y el campo para la referencia del nodo (apuntador ó liga).

Encabezado Alicia Juan - Olga Nada

El arreglo es la estructura natural que se usa cuando se trabaja con listas. Los arreglos proporcionan

un acceso rápido a los elementos almacenados y se puede iterar fácilmente sobre ellos. No obstante,

el arreglo no es la estructura perfecta ya que la búsqueda de un ítem en un arreglo desordenado

puede tomar tiempo ya que deben visitarse cada uno de lo elementos del arreglo. Los arreglos

ordenados son mucho más eficientes para las búsquedas, pero las inserciones y remociones toman

más tiempo porque deben cambiarse los elementos hacia arriba ó hacia abajo para obtener el

espacio para una inserción o eliminar espacio en una remoción. Además en un arreglo ordenado

debe buscarse el espacio apropiado para insertar un elemento.

La mayor diferencia entre un arreglo y una lista ligada es que mientras que en arreglo los elementos

se referencian por su posición (un índice) los elementos de una lista ligada lo hace por una

referencia (apuntador) a otros elementos en el arreglo, así se dice que Juan sigue de Alicia y no que

Juan está en la segunda posición. Moverse a través de una lista ligada involucra seguir las ligas

desde el principio hasta el final (nodo inicial, nodo final).

Además las listas son marcadas al final apuntando a un valor especial que se llama Nothing (nada).

Dado que se trabaja con clases de objetos en memoria, se utiliza el objeto equivalente nulo Nothing,

para denotar el final de una lista. También es recomendable marcar el inicio de una lista con un

nodo llamado encabezado (Header).

La inserción en una lista ligada se vuelve muy eficiente ya que todo lo que implica es cambiar la liga

del nodo previo al nodo insertado y establecer la liga del nodo nuevo al punto que el nodo previo

apuntaba antes de la inserción.


74

La remoción de un nodo es igualmente sencilla ya que implica direccionar la liga del nodo antes de

removerlo al nodo que apunta actualmente y establecer la liga del nodo removido a Nothing.

Listas Ligadas Orientadas a Objetos.

La clase Nodo:

Un nodo está compuesto de dos datos miembros. Elemento que almacena el dato del nodo y Liga

que almacena la referencia al siguiente nodo. Puesto que se puede usar el tipo de dato Object para

el tipo de dato de Elemento no importará que clase de dato sea almacenado en la lista18.

Proyecto MDI para Estructuras Lineales:

Es la aplicación (Windows) en donde se analizarán las estructuras

lineales Listas, Pilas y Colas.

La forma inicial es un contenedor MDI. Nombre MDIELineales,

propiedad IsMDIContainer = True con un menú como el que se

muestra enseguida y un módulo llamado ModEL.

18 Michael McMillan. DataStructures and Algorithms Using Visual Basic .NET. Cambridge.

Header Alicia Juan

Carolina

Olga Nothing

Header Alicia Juan Carolina Olga Nothing


75

Luego se crea la clase Nodo.

La clase Lista Ligada:

Esta clase incluye algunos métodos para agregar o remover nodos en la lista, recorrer la lista y

encontrar un nodo en particular. También se requiere un constructor que instancie una lista. El

único miembro dato en una lista en la clase es el nodo de encabezado (Header).

Public Class CNodo

Public Elemento As Object

Public Liga As CNodo

Public Sub New()

Elemento = Nothing

Liga = Nothing

End Sub

'Sobrecarga

Public Sub New(ByVal ElElemento As Object)

Elemento = ElElemento

Liga = Nothing

End Sub

End Class


76

Public Class CListaLigada

Private mvarHeader As CNodo

Property Header() As CNodo

Get

Return mvarHeader

End Get

Set(ByVal value As CNodo)

mvarHeader = value

End Set

End Property

Public Sub New()

Header = New CNodo("Header")

End Sub

Private Function Buscar(ByVal Item As Object) As CNodo

Dim Actual As New CNodo

Actual = Header

If Not Actual.Liga Is Nothing Then

Do While (Actual.Elemento <> Item)

Actual = Actual.Liga

Loop

End If

Return Actual

End Function

Public Sub Insertar(ByVal ItemNuevo As Object, ByVal DespuesDe As Object)


Actual = Header

Dim NodoNuevo As New CNodo(ItemNuevo)

Actual = Buscar(DespuesDe)

NodoNuevo.Liga = Actual.Liga

Actual.Liga = NodoNuevo

End Sub

Private Function BuscarPrevio(ByVal x As Object) As CNodo

Dim Actual As CNodo = Header

Dim Prev As CNodo = Header

Do While Not (Actual.Liga Is Nothing) And Actual.Elemento <> x

Prev = Actual


Loop

Return Prev

End Function

Public Sub Remover(ByVal x As Object)

Dim P As CNodo = BuscarPrevio(x)

If Not P.Liga Is Nothing Then

P.Liga = P.Liga.Liga

End If

End Sub

Public Sub VerLista(ByRef ListaO As ListBox)


Actual = Header

ListaO.Items.Clear()

Do While Not Actual.Liga Is Nothing

ListaO.Items.Add(Actual.Liga.Elemento)


Loop

End Sub

'Esto es evaluación y no pasa al texto del libro:

Public Function CuentaItems() As Integer


Dim Cuenta As Integer = 0

Actual = Header

Do While Not Actual.Liga Is Nothing

Cuenta += 1


Loop

Return Cuenta

End Function

Public Sub Cambiar(ByVal x As Object, ByVal y As Object)

'Buscar a X:


Do While Not (Actual.Liga Is Nothing) And Actual.Elemento <> x



77

Loop

Actual.Elemento = y

End Sub

End Class

Ejemplo de implementación:

Agregar al proyecto actual una forma:


78

Objeto de

interés

Propiedades Descripción

TextBox Name = txtDato Captura de datos

Button Name = btnInserta Insertar el dato en la lista

ListBox Name = LaLista Desplegar la lista actual

Button Name=btnRemove Quita el elemento seleccionado

de la lista.

Button Name=New Prepara una lista nueva

Button Name=btnSave Guarda la lista actual

Button Name=btnOpen Abre una lista

Button Name=btnClose Cierra la ventana

Label Name=labTL Para mostrar el total de

elementos en la lista.

OpenFileDialog Name=SaveFD, Filter=Archivo de datos

(*.dat)|*.dat

DefaultExt=dat

Ubicación del archivo a crear.

SaveFileDialog Name=SaveFD e iguales propiedades que el

anterior.

Selecciona una lista

almacenada.

Public Class frmListaSimple

Public oLista As New CListaLigada

Public oActual As Object

Public Sub New()




Dim sRuta As String = My.Application.Info.DirectoryPath + "\ListaLigadaS"



End If



End Sub

Private Sub frmListaSimple_Load(ByVal sender As System.Object, ByVal e As


oActual = oLista.Header

End Sub

Private Sub btnInserta_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnInserta.Click

Dim Item As Object

If txtDato.Text.Trim.Length > 0 Then

Item = txtDato.Text

oLista.Insertar(Item, oActual)

oActual = Item

VerLista()

labTL.Text = LaLista.Items.Count

txtDato.Clear()

txtDato.Focus()

End If

End Sub

Private Sub VerLista()

LaLista.Items.Clear()

oLista.VerLista(LaLista)

End Sub


79



txtDato.Clear()


oLista = New CListaLigada


txtDato.Focus()

End Sub

Private Sub LaLista_DoubleClick(ByVal sender As Object, ByVal e As System.EventArgs)

Handles LaLista.DoubleClick

If Not LaLista.SelectedItem Is Nothing Then

oActual = LaLista.SelectedItem

MsgBox("siguiente inserción después de" + vbCr + oActual.ToString)

End If

End Sub



Close()

End Sub

Private Sub btnRemove_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnRemove.Click


Dim Item As Object = LaLista.SelectedItem

oLista.Remover(Item)

VerLista()


End If

End Sub



If LaLista.Items.Count > 0 Then




For Each Item As Object In LaLista.Items

PrintLine(NA, Item)

Next

FileClose(NA)

MsgBox("Lista guardada", MsgBoxStyle.Information)

End If

End If

End Sub





Dim Item As Object


oLista = New CListaLigada


Do While Not EOF(NA)

Item = LineInput(NA)

oLista.Insertar(Item, oActual)

oActual = Item

Loop

FileClose(NA)

VerLista()


End If

End Sub

Este código realiza la inserción cuando se pulsa ENTER al capturar un dato:


80

Private Sub txtDato_KeyPress(ByVal sender As Object, ByVal e As

System.Windows.Forms.KeyPressEventArgs) Handles txtDato.KeyPress

If e.KeyChar = Microsoft.VisualBasic.ChrW(Keys.Return) Then

btnInserta.PerformClick()

End If

End Sub

End Class

Por ahora, el código en la forma MDI es el siguiente:

Public Class MDIELineales

Private Sub ListaLigadaSimpleToolStripMenuItem_Click(ByVal sender As System.Object,

ByVal e As System.EventArgs) Handles ListaLigadaSimpleToolStripMenuItem.Click

Dim F As Form = New frmListaSimple

F.MdiParent = Me

F.Show()

End Sub

Private Sub FinToolStripMenuItem_Click(ByVal sender As System.Object, ByVal e As

System.EventArgs) Handles FinToolStripMenuItem.Click

Close()

End Sub

End Class

Ejecución:

Las inserciones se hacen en el orden

de captura, pero si se hace un clic

doble sobre cualquier elemento de la

lista éste se vuelve el elemento actual

y la siguiente inserción colocará al

dato después de tal elemento.

Para eliminar un elemento de la lista,

debe seleccionarse (con un clic) en la

lista y luego seleccionar .

Se pueden usar cualquier tipo de datos

ya que la clase CListaLigada utiliza

datos tipo Object.

Caso de evaluación de competencias adquiridas:

Realizar los cambios necesarios a la clase CListaLigada para que:

a. Cuente lo elementos en la lista (no debe usarse el control LaLista (ListBox)) de la aplicación.


81

b. Crear un método (en la misma clase) que permita modificar la información de un nodo por

otro valor (z)19. Por ejemplo que cambie la información del nodo Juan por Diana.

Tales cambios pueden probarse en misma forma:

Y el código resultante puede verse así:

Private Sub btnCuenta_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnCuenta.Click

labCuenta.Text = oLista.CuentaItems

End Sub

Private Sub btnCambio_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnCambio.Click

Dim oItem1 As Object = txtItem1.Text

Dim oItem2 As Object = txtItem2.Text

oLista.Cambiar(oItem1, oItem2)

VerLista()

End Sub

Pero puede hacerse como se quiera siempre y cuando los cambios en el código se hagan en la clase.

19 Z es un parámetro.


82

Listas Ligadas Dobles.- Aunque recorrer una lista desde el primer nodo hasta el último es muy

sencillo, no resulta fácil hacerlo a la inversa (del final al principio). Se puede facilitar esta tarea si se

agrega un campo a la clase Nodo para almacenar la liga al nodo previo. Cuando se inserta un nodo a

la lista tienen que realizarse más operaciones para asigna un dato al campo nuevo, sin embargo se

gana eficiencia cuando debe removerse un nodo de la lista ya que no se tiene que buscar el nodo

previo.

Para esto se agrega una clase nueva al proyecto:

Se copia el código de CNodo al la clase recién creada y se hacen las siguientes modificaciones:

Public Class CNodoDoble

Public Elemento As Object

Public LigaS As CNodo 'Liga al siguiente

Public LigaA As CNodo 'Liga al anterior

Public Sub New()

Elemento = Nothing

LigaS = Nothing

LigaA = Nothing

End Sub

'Sobrecarga

Public Sub New(ByVal ElElemento As Object)

Elemento = ElElemento

LigaS = Nothing

LigaA = Nothing

End Sub

End Class

Y la inserción en este tipo de lista es parecida a la que se hace en una lista simple excepto que se

tienen que establecer dos apuntadores:

Agregar una clase nueva al proyecto:

Header Alicia Juan Olga Nothing

Nothin

g


83

Algoritmo de inserción20:

1. Obtener un nodo nuevo y establecer sus campos.

2. Si la lista está vacía entonces insertar el nodo y actualizar sus ligas derecha e izquierda.

3. Si el nodo a insertar está al frente de la lista, entonces insertar el nodo y actualizar sus

apuntadores.

4. Insertar el nodo en medio de la lista.

Usando programación orientada a objetos, este algoritmo puede establecerse de la siguiente

manera:

Algoritmo Insertar (Nuevo).- Donde Nuevo es el valor que se desea insertar en la lista y sus

apuntadores al nodo anterior y al nodo siguiente son LigaA y LigaS respectivamente.

1. Si se va a insertar al final de la lista, entonces:

a. Crear un nodo nuevo y ubicar el último elemento de la lista (U).

b. Crear otro nodo nuevo con la información de Nuevo [NodoNuevo(Nuevo)].

c. Actualizar ligas:

NodoNuevo.LigaS U.LigaS

NodoNuevo.LigaA U

U.LigaS NodoNuevo

2. Inserción después de un elemento en la lista (Nuevo, DespuesDe).- Donde los parámetros Nuevo y

DespuesDe son objetos:

a. Crear un nodo nuevo para ubicar al elemento después del cual se insertará el nodo nuevo (U).

b. Crear otro nodo nuevo con la información de Nuevo. (NodoNuevo).

c. Buscar U.

d. Actualizar apuntadores:

NodoNuevo.LigaS U.LigaS

NodoNuevo.LigaA U

NodoNuevo.LigaS.LigaA NodoNuevo

U.LigaS NodoNuevo

Así, la clase NodoDoble, tendrá dos sobrecargas en su constructor:

Clase Nodo Doble (agregarla al proyecto):

Public Class CNodoDoble

Private mvarElemento As Object

Private mvarLigaS As CNodoDoble 'Liga al siguente

Private mvarLigaA As CNodoDoble 'Liga al anterior

Public Sub New()

mvarElemento = Nothing

mvarLigaA = Nothing

mvarLigaS = Nothing

End Sub

20 Tremblay.- Algoritmo modificado al paradigma orientado a objetos.


84

Public Sub New(ByVal Objeto As Object)

mvarElemento = Objeto

mvarLigaA = Nothing

mvarLigaS = Nothing

End Sub

Property Elemento() As Object

Get

Return mvarElemento

End Get

Set(ByVal value As Object)

mvarElemento = value

End Set

End Property

Property LigaS() As CNodoDoble

Get

Return mvarLigaA

End Get

Set(ByVal value As CNodoDoble)

mvarLigaA = value

End Set

End Property

Property LigaA() As CNodoDoble

Get

Return mvarLigaS

End Get

Set(ByVal value As CNodoDoble)

mvarLigaS = value

End Set

End Property

Y la clase para manipular una lista doble sería como sigue:

Clase Lista con doble liga (agregarla al proyecto):

Public Class CListaD

Protected Header As CNodoDoble

Public Sub New()

Header = New CNodoDoble("Header")

End Sub

Private Function Buscar(ByVal Item As Object) As CNodoDoble

Dim Actual As New CNodoDoble

Actual = Header

If Not Actual.LigaS Is Nothing Then

Do While (Actual.Elemento <> Item)

Actual = Actual.LigaS

Loop

End If

Return Actual

End Function

Public Function BuscarPrevio(ByVal a As Object) As CNodoDoble

Dim Actual As CNodoDoble = Header

Dim Prev As CNodoDoble = Header

Do While Not (Actual.LigaS Is Nothing) And Actual.Elemento <> a

Prev = Actual


Loop

Return Prev

End Function

Public Sub Insertar(ByVal Nuevo As Object, ByVal DespuesDe As Object)

'Inserción en medio de la lista:


Dim NodoNuevo As New CNodoDoble(Nuevo)

'Ubicar DespuesDe



85

'Actualizar apuntadores

NodoNuevo.LigaS = Actual.LigaS

NodoNuevo.LigaA = Actual

NodoNuevo.LigaS.LigaA = NodoNuevo

Actual.LigaS = NodoNuevo

End Sub

Public Sub Insertar(ByVal Nuevo As Object)

'Inserción al final de la lista:

Dim U As CNodoDoble = Ultimo() 'Crear dos nodos

Dim NodoNuevo As New CNodoDoble(Nuevo)

NodoNuevo.LigaS = U.LigaS

NodoNuevo.LigaA = U

U.LigaS = NodoNuevo

End Sub

Public Sub RemoverD(ByVal a As Object) Dim Nodo As CNodoDoble = Buscar(a)

If Not Nodo.LigaS Is Nothing Then

Nodo.LigaA.LigaS = Nodo.LigaS

Nodo.LigaS.LigaA = Nodo.LigaA

Nodo.LigaS = Nothing

Nodo.LigaA = Nothing

Else

Nodo.LigaA.LigaS = Nothing

Nodo.LigaS = Nothing

Nodo.LigaA = Nothing

End If

End Sub

Public Function Ultimo() As CNodoDoble


Actual = Header

Do While Not Actual.LigaS Is Nothing


Loop

Return Actual

End Function

Public Function Primero() As CNodoDoble


Actual = Header

If Not Actual.LigaS Is Nothing Then

Return Actual

Else

Return Nothing

End If

End Function

Public Sub VistaListaD(ByRef oLista As ListBox)

'Vista hacia adelante


Actual = Header

oLista.Items.Clear()



oLista.Items.Add(Actual.Elemento)

Loop

End Sub

Public Sub VistaRev(ByRef oLista As ListBox)

'Vista hacia atrás

Dim Actual = New CNodoDoble

Actual = Ultimo()

oLista.Items.Clear()

Do While Not Actual.LigaA Is Nothing

oLista.Items.Add(Actual.Elemento)

Actual = Actual.LigaA

Loop

End Sub

Public Sub GuardaDatos(ByVal sArchivo As String)


FileOpen(NA, sArchivo, OpenMode.Output)


Actual = Header



86


PrintLine(NA, Actual.Elemento)

Loop

FileClose(NA)

End Sub

Public Sub AbreDatos(ByVal Arhivo As String, ByRef LaLista As CListaD)


FileOpen(NA, Arhivo, OpenMode.Input)

Dim Objeto As Object


Objeto = LineInput(NA)

Insertar(Objeto)

Loop

FileClose(NA)

End Sub

'EVALUACION

Public Function CuentaItems() As Integer

End Function

End Class

Al inicializar una instancia de la lista doble:

Inserciones consecutivas:

Y una inserción después de Alicia:

Ejemplo:

Agregar una forma nueva al proyecto21:

21 La propiedad image de los controles es opcional y no necesariamente con las imágenes mostradas, en su

lugar puede establecerse Text.

Ejercicio: Escribir el código

necesario para contar los

elementos en la lista.

Header

Header Alicia

Header Alicia Juan

Header Alicia Carolina Juan


87

Etiquetas labTotal y labTotFiles, mostrarán el

total de elementos en la lista doble y el total de

archivos (con elementos de una lista)

almacenados-

txtDato

btnDel

btnModificar

btnSave

btnOpen

Tres cuadros de diálogo.

btnNew

btnClose

Las tres listas son controles ListBox.

Vista del proyecto:


88

Private ListaD As New CListaD, oActual As Object

Public sRuta, RutaPal As String

Public Sub New()




sRuta = My.Application.Info.DirectoryPath + "\ListaLigadaD"



End If

RutaPal = sRuta + "\Palindromos"

'Crea ruta para ejercicio

If Not My.Computer.FileSystem.DirectoryExists(RutaPal) Then

My.Computer.FileSystem.CreateDirectory(RutaPal)

End If



End Sub

Private Sub frmListaDoble_Load(ByVal sender As Object, ByVal e As System.EventArgs)

Handles Me.Load

oActual = Nothing

VerArchivos()

End Sub

Private Sub VerArchivos()

ListArchivos.Items.Clear()

For Each sFile As String In My.Computer.FileSystem.GetFiles(sRuta)

ListArchivos.Items.Add(My.Computer.FileSystem.GetName(sFile))

Next

labTotFiles.Text = ListArchivos.Items.Count

End Sub

Inserción de datos en secuencia ó después de un elemento de la lista, seleccionado con doble clic

den ListaA (ListBox). La inserción se realiza al pulsar ENTER en txtDato.





Dim Elemento As New Object

Elemento = txtDato.Text.Trim

If oActual Is Nothing Then

ListaD.Insertar(Elemento)

Else

ListaD.Insertar(Elemento, oActual)

oActual = Nothing

End If

ListaD.VistaListaD(ListaA)

ListaD.VistaRev(ListaR)

labTotal.Text = ListaD.CuentaItems

txtDato.Clear()

Else

MsgBox("Falta dato", MsgBoxStyle.Information)

End If

End If

End Sub

Private Sub ListaA_DoubleClick(ByVal sender As Object, ByVal e As System.EventArgs)

Handles ListaA.DoubleClick _

, ListaR.DoubleClick

Dim Lista As ListBox = sender

If Not Lista.SelectedItem Is Nothing Then

oActual = Lista.SelectedItem

MsgBox("La siguiente inserción será después de: " + oActual.ToString)

txtDato.Focus()

End If

End Sub


89



SetDialogo("dat")



Dim Archivo As String = SaveFD.FileName

ListaD.GuardaDatos(Archivo)

VerArchivos()

End If

End Sub

Este procedimiento cambia algunas propiedades de los cuadros de diálogo de acuerdo al tipo de

archivo requerido. Más adelante, los agregados a esta forma como ejercicio, requieren guardar los

datos como texto, las listas normales se guardan en archivos de datos (.dat).

Private Sub SetDialogo(ByVal sExt As String) SaveFD.DefaultExt = sExt

If sExt = "txt" Then

SaveFD.Filter = "Archivos de texto (*.txt)|*.txt"

SaveFD.InitialDirectory = RutaPal

Else

SaveFD.Filter = "Archivos de datos (*.dat)|*.dat"


End If

SaveFD.FileName = ""

OpenFD.InitialDirectory = SaveFD.InitialDirectory

OpenFD.DefaultExt = sExt

OpenFD.Filter = SaveFD.Filter

End Sub



SetDialogo("dat")

If Not ListArchivos.SelectedItem Is Nothing Then

OpenFD.FileName = ListArchivos.SelectedItem

End If



Dim sFile As String = OpenFD.FileName

Dim FI As System.IO.FileInfo

FI = My.Computer.FileSystem.GetFileInfo(sFile)

If FI.Length > 0 Then

ListaD = New CListaD

ListaD.AbreDatos(sFile, ListaD)




End If

End If

End Sub

Para remover un elemento de la lista:

Private Sub btnRem_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnRem.Click

'Elemento seleccionado en ListaA (a remover)

If Not ListaA.SelectedItem Is Nothing Then

Dim Borra As Object = ListaA.SelectedItem

ListaD.RemoverD(Borra)




End If

End Sub


90

Adicionalmente, puede abrirse una lista seleccionando el archivo en la lista que los muestra

(ListArchivos), con un clic doble:

Private Sub ListArchivos_MouseDoubleClick(ByVal sender As Object, ByVal e As

System.Windows.Forms.MouseEventArgs) Handles ListArchivos.MouseDoubleClick


btnNew.PerformClick()

Dim sFile As String = sRuta + "\" + ListArchivos.SelectedItem

If My.Computer.FileSystem.FileExists(sFile) Then

ListaD.AbreDatos(sFile, ListaD)




End If

End If

End Sub

Así por ejemplo al insertar la siguiente secuencia de datos:

Alicia, Juan Carolina, Ricardo, Roxana, las listas hacia adelante y hacia atrás se verán así:

Al hacer clic doble en un dato de la primera lista:


91

Y al pulsar ENTER:

Public Sub ModificaNodo(ByVal Item As Object, ByVal OModifca As Object)

Dim Nodo = Buscar(Item)

If Not Nodo.Elemento Is Nothing Then

Nodo.Elemento = OModifca

Else

MsgBox(Item + " no existe en la lista", MsgBoxStyle.Information)

End If

End Sub

Ejemplo: Si se selecciona Juan en la primera lista (con un clic):


92

Resultado:

Ejercicio.- Un palíndromo es una frase o palabra que se le igual de izquierda a derecha que de

derecha a izquierda. Estos son algunos ejemplos:

Somos o no somos

Luz azul

Anita lava la tina

La ruta natural

Yo hago yoga hoy.

No traces en ese cartón

Modificar la ventana de listas ligadas dobles para determinar si una palabra ó frase es ó no un

palíndromo usando la clase CListaD.

Sugerencias:

Ampliar el ancho de la forma y agregar un control contenedor Panel con las siguientes propiedades:

Name = pnlEj

Border Style = Fixed 3D

Dentro del este contenedor, se agregan los elementos que se muestran:

Los controles de interés(para el programa) son:

txtWord.- TextBox con su propiedad CaracterCasong =

lower, así solo se mostrarán letras minúsculas.

btnPal.- Command button.

labP1.- Label con BorderStyle = Fixed3D, BackColor

=HonewDew

labP2.- Label con las mismas propiedades de la


93

anterior salvo el color que debe ser otro.

btnSave, btnOpen y btnNew.

La ejecución del ejercicio en la ventana ampliada se vería así:

Como se observa, es necesario quitar espacios en la frase y escribirla sin acentos, por ejemplo, la

frase dábale arroz a la zorra el abad, se escribe sin acentos. Además sus letras son sólo minúsculas

(el control de texto está configurado así).

El código del evento Clic del botón sería el siguiente:

Private Sub btnPal_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnPal.Click

Dim Palabra As String = txtWord.Text.Trim

If Palabra.Length > 1 Then

btnNew.PerformClick()

Dim L As Char, i As Short

For i = 1 To Palabra.Length

L = Mid(Palabra, i, 1)

If CStr(L) <> " " Then

ListaD.Insertar(L)

End If

Next

With ListaD

.VistaListaD(ListaA)

.VistaRev(ListaR)

End With

If EsPalindrome() Then

MsgBox("Es un palíndrome", MsgBoxStyle.Information)

Else

MsgBox("No es palíndrome", MsgBoxStyle.Information)


94

End If

End If

End Sub

Aquí, primero se verifica que la palabra sea de longitud mayor 1. Luego se prepara la forma para

una lista doble nueva ejecutando programáticamente un clic al botón btnNew.

El proceso comienza extrayendo cada letra de la palabra o frase ingresada recorriéndola letra por

letra como se muestra en el ciclo for del procedimiento y usando la función Mid de VB.NET.

La instrucción:

L = Mid(Palabra, i, 1)

Extrae la letra del objeto Palabra que se encuentra en la posición “i” y tomando únicamente 1

carácter.

Para insertar únicamente letras sin espacios en blanco en la frase:

If CStr(L) <> " " Then

ListaD.Insertar(L)

End If

Finalmente se muestran las listas hacia adelante y hacia atrás y se ejecuta el procedimiento EsPalindrome objeto del ejercicio.

Para guardar y abrir frases que demuestren la validez del código escrito, se crea un directorio especial:

Private Sub btnSavePal_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnSavePal.Click

SetDialogo("txt")


My.Computer.FileSystem.WriteAllText(SaveFD.FileName, txtWord.Text.Trim, False)

MsgBox("Frase/Palabra guardada", MsgBoxStyle.Information)

End If

End Sub

Private Sub btnOpenPal_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnOpenPal.Click

SetDialogo("txt")


Dim sWord As String = My.Computer.FileSystem.ReadAllText(OpenFD.FileName)

txtWord.Text = sWord

End If

End Sub


95

Listas Circulares.- Una lista circular es una lista simple o en donde el apuntador del último nodo

apunta al primer elemento de la lista (encabezado).

Cuando se inicia una lista circular se tiene entonces:

Y cuando esta lista contiene nodos:

El modelo usado para la lista ligada simple puede usarse como base para crear una clase para este

tipo de listas:

En el proyecto actual, agregamos una clase nueva:

Public Class CListaC

Protected NodoA As CNodo

Protected Header As CNodo

Public CuentaNodos As Integer = 0

Public Sub New()

Header = New CNodo("Header")

Header.Liga = Header

End Sub

Header

Header Alicia Olga Laura


96

Métodos:

Public Function ListaVacia() As Boolean

If Header.Liga.Elemento = Header.Elemento Then

Return True

Else

Return False

End If

End Function

Public Sub VaciarLista()

Header.Liga = Header

CuentaNodos = 0

End Sub

Private Function BuscaPrev(ByVal X As Object) As CNodo


Do While Not Actual.Liga Is Nothing And Actual.Liga.Elemento <> X


Loop

Return Actual

End Function

Private Function Buscar(ByVal X As Object) As CNodo

Dim Actual As CNodo

Actual = Header.Liga

Do While Actual.Elemento <> X


Loop

Return Actual

End Function

Public Function Mover(ByVal N As Integer) As CNodo

Static Actual As CNodo = Header.Liga

Dim Temp As CNodo

For i As Integer = 1 To N


Next

If Actual.Elemento = "Header" Then


End If

Temp = Actual

Return Temp

End Function

La inserción puede hacerse al principio de la lista o después de algún otro elemento, por defecto el

último.

Public Sub Insertar(ByVal X As Object, ByVal DespuesDe As Object)


Dim NodoN As New CNodo(X)


NodoN.Liga = Actual.Liga

Actual.Liga = NodoN

CuentaNodos += 1

End Sub

Public Sub InsertarPrimero(ByVal X As Object)

Dim Actual As New CNodo(X)

Actual.Liga = Header

Header.Liga = Actual

CuentaNodos += 1

End Sub

Remoción:

Public Sub Remover(ByVal X As Object)

Dim NodoP As CNodo = BuscaPrev(X)

If Not NodoP.Liga Is Nothing Then

NodoP.Liga = NodoP.Liga.Liga

End If

CuentaNodos -= 1


97

End Sub

La lista se muestra en un ListBox:

Public Sub VerLista(ByRef UnaLista As ListBox)

UnaLista.Items.Clear()


Actual = Header

Do While Not Actual.Liga.Elemento = "Header"

UnaLista.Items.Add(Actual.Liga.Elemento)


Loop

End Sub

Para localizar al último elemento de la lista:

Public Function Ultimo() As CNodo

Dim Nodo As CNodo = Header.Liga

Dim NTemp As New CNodo

Do While Not Nodo.Elemento = "Header"

NTemp = Nodo

Nodo = Nodo.Liga

Loop

Return NTemp

End Function

Uso: Agregar una forma al proyecto actual (frmListaCircular):

Los controles de interés en orden descendente

son:

txtDato (TextBox)

chkDespuesDe (CheckBox)

LaLista (ListBox)

NumNodo (NumericUpDown, Minimum =0,

Maximum = 10)

txtArchivo (TextBox)

ListaArchivos (ListBox)

Los botones son:

btnDel

btnMove

btnSave

btnOpen


98

En esta ventana se omiten los cuadros de diálogo para guardar y abrir con el fin de mostrar otra

opción para el registro de la información de los nodos en una lista circular.

Esta ventana opera de la siguiente manera:

Siempre que se inicia se crea una instancia de la clase de la lista circular y se crea un directorio para

los archivos de listas circulares que, en caso de existir son mostrados:

Public Class frmListaCircular

Private ListaC As New CListaC

Private Dato As Object, RutaC, sFile As String

Private UDato As Object = Nothing

Public Sub New()




RutaC = My.Application.Info.DirectoryPath + "\Listas Circulares\"

If Not My.Computer.FileSystem.DirectoryExists(RutaC) Then

My.Computer.FileSystem.CreateDirectory(RutaC)

End If

End Sub

Private Sub VerArchivos()

ListArchivos.Items.Clear()

For Each Archivo As String In My.Computer.FileSystem.GetFiles(RutaC,

FileIO.SearchOption.SearchTopLevelOnly, "*.*")

ListArchivos.Items.Add(My.Computer.FileSystem.GetName(Archivo))

Next

End Sub

Private Sub frmListaCircular_Load(ByVal sender As Object, ByVal e As System.EventArgs)

Handles Me.Load

VerArchivos()

End Sub

Los datos de la lista se ingresan en txtDatos al pulsar ENTER:





Dato = txtDato.Text.Trim

If ListaC.ListaVacia Then

ListaC.InsertarPrimero(Dato)

UDato = Dato

Else

ListaC.Insertar(Dato, UDato)

If chkDespuesDe.Checked Then

chkDespuesDe.Checked = False

Else

UDato = Dato

End If

End If

End If

ListaC.VerLista(LaLista)

NumNodo.Maximum = ListaC.CuentaNodos

txtDato.Clear()

End If

End Sub


99

Cuando la lista tiene nodos y se desea hacer una inserción después de un nodo específico, se marca

con un clic en la lista y se activa lo que desencadena un evento

que se usa para validar:

Si el control es activado usamos el evento CheckStateChanged para validar y estalbecer el

elemento después del cual se realizará la inserción, al desactivarse se establece el último elemento

de lista para continuar insertando.

Private Sub chkDespuesDe_CheckStateChanged(ByVal sender As Object, ByVal e As

System.EventArgs) Handles chkDespuesDe.CheckStateChanged

If chkDespuesDe.Checked Then


UDato = LaLista.SelectedItem

MsgBox("Siguiente inserción después de: " + UDato, MsgBoxStyle.Information)

txtDato.Focus()

Else

MsgBox("No se ha seleccionado un elemento en la lista",

MsgBoxStyle.Information)

chkDespuesDe.CheckState = CheckState.Unchecked

End If

Else

UDato = ListaC.Ultimo.Elemento

End If

End Sub

Para moverse a un nodo (determinado por el control numérico):

Private Sub btnMove_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnMove.Click

Dim Nodo As CNodo = ListaC.Mover(NumNodo.Value)

If LaLista.Items.Count > 0 Then

LaLista.SelectedIndex = NumNodo.Value

End If

MsgBox("El nodo " + NumNodo.Value.ToString + " es: " + Nodo.Elemento,

MsgBoxStyle.Information)

End Sub

Para vaciar la lista actual ó para eliminar el nodo seleccionado:

Private Sub btnClear_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnClear.Click


ListaC.VaciarLista()

NumNodo.Value = ListaC.CuentaNodos

End Sub

Private Sub btnRem_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnRem.Click


Dim D As Object = LaLista.SelectedItem

ListaC.Remover(D)

NumNodo.Value = ListaC.CuentaNodos


End If

End Sub

Finalmente, para guardar una lista, debe introducirse el nombre del archivo, el cual si existe será

reemplazado con la lista actual.


100



If ListaC.CuentaNodos > 0 Then

sFile = txtArchivo.Text.Trim

If sFile.Length > 0 Then

sFile = RutaC + sFile

'Si el archivo existe lo elimina

If My.Computer.FileSystem.FileExists(sFile) Then

My.Computer.FileSystem.DeleteFile(sFile)

End If


FileOpen(NA, sFile, OpenMode.Output)

For Each D As Object In LaLista.Items

PrintLine(NA, D)

Next

FileClose(NA)

VerArchivos()

End If

End If

End Sub

Y para abrir una lista almacenada:




txtArchivo.Text = ListArchivos.SelectedItem

sFile = RutaC + txtArchivo.Text


FileOpen(NA, sFile, OpenMode.Input)

Dim D As Object

ListaC.VaciarLista()


D = LineInput(NA)

If ListaC.ListaVacia Then

ListaC.InsertarPrimero(D)

Else

ListaC.Insertar(D, UDato)

End If

UDato = D

Loop

FileClose(NA)


NumNodo.Value = 1

End If

End Sub

Así:

La siguiente inserción se hará después de Alicia, por

ejemplo.


101

Y si deseamos movernos al 3er nodo (que están numerados desde el cero):

Un ejercicio interesante es el siguiente22:

De acuerdo a la leyenda, el historiador judío Flavius Josephus fue capturado junto con otros 40

compatriotas por legionarios romanos durante la guerra judeo romana. Los soldados judíos

decidieron que era preferible suicidarse en lugar de ser capturados (lo que se parece a la saga de

Masada) para lo cual diseñaron un plan para ello. Formaron entonces un círculo para asesinar a cada

tercer soldado hasta que todos estuviesen muertos. José y otro decidieron que no formarían parte

de esto y rápidamente calcularon que era necesario colocarse ellos mismos en el círculo y sobrevivir

ambos. Escribir un programa que permita colocar N personas en un círculo y especificar cada M

persona debe ser eliminada. El programa debe especificar el número de la última persona a la

izquierda del círculo. Usar una lista ligada circular para resolver el problema.

Para resolverlo:

22 McMillan Michael.- Data Structures and Algorithms using Visual Basic.NET.


102

1. Crear una lista circular de N elementos (N>10) con los nombres de los que serán

ejecutados.

2. Establecer cada cuantos son eliminados (M).

3. Repetir mientras el tamaño de la lista sea >M.

a. Recorrer la lista cada m-ésimo elemento agregarlo a un ListBox

b. Agregar ese nombre a otra lista (yo utilicé un ArrayList)

c. Al terminar el recorrido eliminar la selección de la lista circular (que está en el ArrayList)

d. Vaciar el ArrayList.

e. Mostrar la lista circular restante

4. FIN

Puede usarse la ventana actual agregando una sección para resolver el ejercicio:

Panel1

NumM (NumericUpDown

Maximum = 100, Minimum =2)

btnInicio (Button)

ListaJ (ListBox)


103

Prueba 1:

En el primer recorrido se señalan a Pedro, Judas, Flavio Jacob y

Jeremías que luego son eliminados, quedando al principio Abraham.

El segundo recorrido de la lista restante se elimina a José, Barrabás

y a Tomás y vuelve a quedar Abraham al principio de la lista.

Finalmente el 2° elemento es Dimas que se elimina y sólo queda

Abraham.

La conclusión es que el que quiera sobrevivir al final, deberá

colocarse al principio de la lista.

La única validación que se realiza es M < N aunque deberían

ingresarse valores entre 2 y N/M.

Prueba 2:

PILAS

La Pila es una de las estructuras lineales de tamaño variable más importantes.

De forma general, en una lista lineal se pueden realizar inserciones o remociones en cualquier parte

esta. Una clase importante de listas permite que la inserción y remoción de un elemento se realice

únicamente al final de la lista. Este tipo de clase se conoce como una Pila. A la operación de insertar

un elemento al final de la lista se le conoce como PUSH y a la operación de eliminar el elemento al

final de la lista como POP. El primer y último elemento de una pila debe ser accesible y se conocen

como el fondo y el tope de la pila. Así la remoción se hace siempre en el orden inverso a como

fueron agregados los elementos de una pila.


104

Puesto que como generalmente no se conoce el tamaño de una pila, lo mejor es usar una estructura

dinámica como el ArrayList.

La Clase PILA (Agregar al proyecto actual) :

Public Class CPila

Private Tope As Integer

Private L As New ArrayList

Public Sub New()

Tope = -1

End Sub

ReadOnly Property Count() As Integer

Get

Return L.Count

End Get

End Property

Public Sub PUSH(ByVal X As Object)

L.Add(X)

Tope += 1

End Sub

Public Function POP() As Object

If L.Count > 0 Then

Dim x As Object = L.Item(Tope)

L.RemoveAt(Tope)

Tope -= 1

Return x

Else

Return Nothing

End If

End Function

Public Sub CLEAR()

L.Clear()

End Sub

Public Function PEEK() As Object

'Regresa el elemento en el tope de la pila

If Not Tope = -1 Then

Return L.Item(Tope)

Else 'Pila vacía

Return Nothing

End If

End Function

Public Sub VerPila(ByRef LB As ListBox)

LB.Items.Clear()

If L.Count > 0 Then

L.Reverse()

For Each X As Object In L

LB.Items.Add(X)

Next

Pila Vacía Tope 0

PUSH1 Tope 1 1

PUSH2 Tope 2

1

2

PUSH3 Tope 3

POP

1

2 Tope


105

L.Reverse()

End If

End Sub

End Class

Uso: Agregar una forma nueva al proyecto:

txtDato (TextBox)

btnPush (Button)

LaPila (ListBox)

btnPop (Button)

btnTope (Button)

btnCLS (Button)

ListaPOP (ListBox)

labCount (Label).

Implementación de la clase Pila:

Public Class frmPILA

Private Pila As CPila

Private Sub frmPILA_Load(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles MyBase.Load

Pila = New CPila

End Sub


106

Private Sub btnPush_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnPush.Click

If Not txtDato.Text Is Nothing Then

Dim Dato As Object = txtDato.Text.Trim

Pila.PUSH(Dato)

Pila.VerPila(LaPila)

txtDato.Clear()

txtDato.Focus()

labCount.Text = Pila.Count

End If

End Sub

Private Sub POP_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles POP.Click

Dim Dato As Object = Pila.POP

If Not Dato Is Nothing Then

ListaPOP.Items.Add(Dato)



Else

MsgBox("Pila vacía", MsgBoxStyle.Information)

End If

End Sub

Private Sub btnTope_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnTope.Click

Dim Dato As Object = Pila.PEEK

If Not Dato Is Nothing Then

MsgBox("El tope es " + Dato.ToString, MsgBoxStyle.Information)

Else

MsgBox("Pila vacía", MsgBoxStyle.Information)

End If

End Sub

Private Sub btnCLS_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnCLS.Click

Pila.CLEAR()

LaPila.Items.Clear()

ListaPOP.Items.Clear()

End Sub

End Class

Ejecución:

Secuencia de inserción: 150, 417, 515, 800, 90:

Tope de la pila:


107

Operaciones POP (retirar 3 elementos):

Aplicación:

El problema del Palíndromo23 puede resolverse usando una pila y usando esta misma forma:

Panel1:

txtFrase (TextBox, CharacterCasing = Lower)

btnPal (Button):

23 Ejercicio de la página 19.


108

Private Sub btnPal_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnPal.Click

Pila = New CPila

Dim sFrase As String = txtFrase.Text.Trim

If sFrase.Length > 0 Then

Dim x As Integer, Letra As Char

Dim sW1 As String = ""

Dim EsPalindromo As Boolean = True

For x = 0 To sFrase.Length - 1

Letra = sFrase.Substring(x, 1)

If Letra <> " " Then

sW1 += Letra

Pila.PUSH(Letra)

End If

Next



x = 0

Do While Pila.Count > 0

Letra = Pila.POP

ListaPOP.Items.Add(Letra)

If Letra <> sW1.Substring(x, 1) Then

EsPalindromo = False

Exit Do

End If

x += 1

Loop

If EsPalindromo Then

MsgBox("Es palíndromo", MsgBoxStyle.Information)

Else

MsgBox("No es palíndromo", MsgBoxStyle.Information)

End If

End If

End Sub

La Clase Stack.

La clase Stack es una implementación de la interfaz ICollection que representa a una pila. Esta clase

está implementada como un buffer circular que permite obtener espacio dinámicamente para los

elementos insertados en la pila. Esta clase forma parte del marco (Framework) .NET.

La clase Stack incluye métodos Push, Pop y Peek. Tiene también métodos para determinar el número

de elementos en la pila, limpiarla y regresar los valores en la pila como un arreglo.

Métodos Constructores de la clase Stack.

Existen tres maneras de instanciar un objeto Stack. El constructor por defecto instancia una pila

vacía que inicialmente tiene una capacidad de 10 elementos y puede invocarse como:

Dim LaPila As New Stack


109

Cada vez que la pila se llena, su capacidad es duplicada.

El segundo método constructor permite crear un objeto pila de otra colección. Por ejemplo se puede

pasar al constructor un arreglo y apilar los sus elementos:

Dim Nombres() As String = {"Laura", "Ana", "Juan", "Carolina"}

Dim Pila As New Stack(Nombres)

El método POP quitaría a Carolina de la pila.

El tercer método, permite especificar la capacidad inicial de la pila y se usa si se conoce de

antemano cuantos elementos debe contener la pila.

Ejemplo:

Dim P As New Stack(20)

Ejemplo de uso:

Conversión de números en base 10 a cualquier otra base24:

Agregar forma al proyecto:

txtNum (TextBox, TextAlign =_Right, Text=0

NumBase (NumericUpDown, Minimu = 2, Maximum=8)

btnConvet (Button)

labRes (Label, BorderStyle = Fixed 3D, AutoZise = False,

TextAlign = Center

Ejemplo:

24 Método descrito en Arreglos.


110

Comprobación:

Public Class frmSTACK

Private Sub btnConvert_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnConvert.Click

Dim Num As Integer = txtNum.Text

Dim Base As Short = NumBase.Value

labRes.Text = ToBase(Num, Base)

End Sub

Private Function ToBase(ByVal n As Integer, ByVal b As Short) As String

Dim Digitos As New Stack

Dim sR As String = ""

Do While n > 0

Digitos.Push(n Mod b)

n \= b

Loop

Do While Digitos.Count > 0

sR += Digitos.Pop.ToString

Loop

Return sR

End Function

End Class


111

Notación Polaca.

Sistema para especificar expresiones matemáticas desarrollado en 1920 por el matemático de

origen polaco Jan Lukasiewicz. Esta expresión se conoce como notación prefija o polaca (en honor a

él) y consiste en situar al operador antes que los operandos.

Por ejemplo, la expresión infija A * B/(C-D) se representa en notación prefija (prefija) como

/*AB+AC.

La notación posfija o polaca inversa es una variación de la notación prefija de forma que el operador

se coloca después de los operandos. Por ejemplo, la expresión infija A*B/(C-D) se representaría en

notación posfija como AB*AC+/.

Conversión de expresiones infijas sin paréntesis a notación polaca inversa:

Si se asignan valores de precedencia para los cuatro operadores básicos:

Tabla 1.

Símbolo Precedencia

F

Rango

R

+, - 1 -1

*, / 2 -1

a, b, c,… 3 1

# 0 0

Se asume que el contenido de la pila para evaluar esta expresión se inicializa con el símbolo ‘#’ que

tiene un valor de precedencia menor que los demás símbolos dados en la tabla.

El algoritmo general para esta tarea sería:

1. Inicializar el contenido de la pila con ‘#”

2. Extraer el símbolo más a la izquierda de expresión infija (símbolo de entrada actual).

3. Repetir hasta el paso 6 mientras el símbolo de entrada <>’#’

4. Remover y sacar todos los símbolos en la pila cuya precedencia sea mayor o igual al valor de

precedencia del valor del símbolo actual.

5. Colocar en la pila el símbolo actual.

6. Extraer el siguiente símbolo más a la izquierda en la expresión infija (símbolo de entrada

actual).

Algoritmo Expresiones si paréntesis 25

25 J.P. Tremblay (modificado)


112

Dada una cadena de entrada INFIJA que representa a una expresión infija donde sus símbolos tienen

la precedencia mostrada en la tabla 1, una PILA y una función denominada SIGUIENTE la cual,

cuando es invocada regresa el siguiente carácter (de izquierda a derecha) de la cadena de entrada,

este algoritmo convierte INFIJA a su correspondiente cadena POLACA. RANGO contiene el valor de

cada símbolo en la expresión polaca. ACTUAL contiene el símbolo actualmente examinado y TEMP

es el elemento que se saca de la pila. Se asume que la cadena de entrada termina con el símbolo

especial ‘#’.

1. Inicializar la PILA:

PILA.PUSH(‘#’)

2. Inicializar la cadena de salida y el contador de rangos:

POLISH ‘’

Rango 0

3. Obtener el primer símbolo:

Actual SIGUIENTE(INFIJA)

4. Traducir la expresión infija:

Repetir hasta el paso 6 mientras Actual ≠ ’#’

5. Sacar de la pila los símbolos con precedencia mayor o igual.

Repetir mientras F(Actual) <=F(Pila.Tope)

TEMP PILA.POP

POLISH POLISH + TEMP

Rango Rango + R(TEMP)

Si Rango < 1 entonces

Error ‘Expresión inválida’

[FIN]

6. Colocar el símbolo actual en la pila:

PILA.PUSH(Actual)

Actual SIGUIENTE(INFIJA)

7. Quitar los elementos remanentes de la pila:

Repetir mientras PILA(Tope) ≠ ‘#’

TEMP PILA.POP

POLACA POLACA + TEMP


Si Rango < 1 entonces


[FIN]

8. ¿Es válida la expresión?

Si Rango = 1, entonces

‘Expresión es válida

De otro modo

‘Expresión no es válida


113

FIN

Implementación:

Public Class CPolaca

Public POLACA As String = ""

Private mvarINFIJA As String = ""

Private Actual As String = ""

Private TEMP As String = ""

Private X As Short

Public Sub New()

X = 0

End Sub

Property INFIJA() As String

Get

Return mvarINFIJA

End Get


mvarINFIJA = value + "#"

End Set

End Property

Private Function RSP(ByVal C As Char) As Short

'Expresión sin paréntesis

Select Case C

Case "+", "-"

Return -1

Case "*", "/"

Return -1

Case "a" To "z"

Return 1

Case "#"

Return 0

Case Else

Return 0

End Select

End Function

Private Function FSP(ByVal C As Char) As Short

'Expresión sin paréntesis

Select Case C

Case "+", "-"

Return 1

Case "*", "/"

Return 2

Case "a" To "z"

Return 3

Case "#"

Return 0

Case Else

Return 0

End Select

End Function

Private Function SIGUIENTE() As Char

If X < mvarINFIJA.Length Then

Dim L As Char = mvarINFIJA.Substring(X, 1)

X += 1

Return L

Else

Return vbNullChar

End If

End Function

Public Function POLACASP() As String

Dim Pila As New Stack

Pila.Push("#") '...........................................[1]

Dim Rango As Short = 0 '...................................[2]

POLACA = ""

INFIJA += "#"


114

Actual = SIGUIENTE() '.....................................[3]

Do While Actual <> "#" '...................................[4]

Do While FSP(Actual) <= FSP(Pila.Peek) '...............[5]

TEMP = Pila.Pop

POLACA += TEMP

Rango += RSP(TEMP)

If Rango < 1 Then

POLACASP = "EXPRESION NO ES VALIDA"

Exit Function

End If

Loop

Pila.Push(Actual) '....................................[6]

Actual = SIGUIENTE()

Loop

Do While Pila.Peek <> "#" '................................[7]

TEMP = Pila.Pop

POLACA += TEMP

Rango += RSP(TEMP)

Loop

If Rango = 1 Then '........................................[8]

POLACASP = POLACA

Else

POLACASP = "EXPRESION NO VALIDA"

Exit Function

End If

End Function

End Class

Uso.- Agregar una forma al proyecto:

txtExp (TextBox, CaracterCasing = Lower)

btnPolaca (Button)

Public Class frmPolaca

Private Sub btnPolish_Click(ByVal sender As

System.Object, ByVal e As System.EventArgs)

Handles btnPolish.Click

If txtExp.Text.Trim.Length > 0 Then

Dim Polaca As New CPolaca

Polaca.INFIJA = txtExp.Text.Trim


115

If InStr(Polaca.INFIJA, "(") = 0 Then

labPolaca.Text = Polaca.POLACASP

End If

End If

End Sub

Algoritmo Expresiones con paréntesis (y operador de potencia).

Tabla 226.

Símbolo

Precedencia de entrada

F

Función de precedencia en la pila

G

Funciónde Rango

R

+, - 1 2 -1

*,- 3 4 -1

↑ 6 5 -1

a,b,c,… 7 8 1

( 9 0 0

) 0 0 0

Dada una cadena infija de entrada (INFIJA) que representa a una expresión infija la cual termina con

‘)’ y cuyos símbolos tienen los valores de precedencia que se muestran en la tabla 2, una PILA y una

función SIGUIENTE que cuando es invocada regresa el siguiente carácter a ser evaluado, este

algoritmo convierte la expresión infija a su polaca equivalente. La variable entera Rango acumula el

rango de la expresión. Finalmente TEMP almacena temporalmente el elemento apilado.

1. Inicializar PILA:

PILA.PUSH(“(“)

2. Inicializar la cadena de salida y contador de rangos.

POLACA ’’

26 Tremblay


116

Rango 0

3. Obtener símbolo de entrada:

Actual SIGUIENTE

4. Traducir la expresión infija:

Repetir hasta el paso 7 mientras Actual ≠ ´´

5. Quitar de la pila los símbolos con mayor precedencia:

Si Pila vacía entonces


[FIN]

Repetir mientras F(Actual) < G(PILA.Tope)

TEMP PILA.POP

POLACA POLACA + TEMP


Si Rago < 1 entonces


[FIN]

6. ¿Se encuentran paréntesis?

Si Actual ≠ PILA.TOPE entonces

PILA.PUSH(Actual)

De otro modo

PILA.POP

7. Obtener siguiente símbolo de entrada:

Actual SIGUIENTE

8. ¿Es válida la expresión?

Si PILA.TOPE ≠0 ó Rango ≠ 1 entonces


[FIN]

De otro modo, RETURN POLACA

Métodos nuevos a la clase (para expresiones con paréntesis):

Private Function FCP(ByVal c As Char) As Short

Select Case c

Case "+", "-"

Return 1

Case "/", "*"

Return 3

Case "^"

Return 6

Case "a" To "z"

Return 7

Case "("

Return 9

Case ")"

Return 0

Case Else

Return 0

End Select

End Function


117

Private Function RCP(ByVal C As Char) As Short

Select Case C

Case "+", "-"

Return -1

Case "*", "/"

Return -1

Case "^"

Return -1

Case "a" To "z"

Return 1

Case "("

Return 0

Case ")"

Return 0

Case Else

Return 0

End Select

End Function

Private Function G(ByVal C As Char) As Short

Select Case C

Case "+", "-"

Return 2

Case "*", "/"

Return 4

Case "^"

Return 5

Case "a" To "z"

Return 8

Case "("

Return 0

Case ")"

Return 0

Case Else

Return 0

End Select

End Function

Public Function POLACACP() As String

Dim PILA As New Stack

INFIJA += ")"

PILA.Push("(") '[1]

POLACA = "" '[2]

Dim Rango As Short = 0 '[2]

Actual = SIGUIENTE() '[3]

Do While Actual <> vbNullChar '[4]

If PILA.Count = 0 Then

POLACACP = "Expresión inválida"

Exit Function

End If

Do While FCP(Actual) < G(PILA.Peek) '5]

TEMP = PILA.Pop

POLACA += TEMP

Rango += RCP(TEMP)

If Rango < 1 Then


Exit Function

End If

Loop

If FCP(Actual) <> G(PILA.Peek) Then '[6]

PILA.Push(Actual)

Else

PILA.Pop()

End If


Loop

If PILA.Count <> 0 Or Rango <> 1 Then '[8]

POLACACP = "Expresión no válida"


118

Else

POLACACP = POLACA

End If

End Function

Cambios en la forma:

Private Sub btnPolish_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnPolish.Click

If txtExp.Text.Trim.Length > 0 Then


Polaca.INFIJA = txtExp.Text.Trim

If InStr(Polaca.INFIJA, "(") = 0 Then

labPolaca.Text = Polaca.POLACASP

Else

labPolaca.Text = Polaca.POLACACP

End If

End If

End Sub

Ejecución:

Como evaluar las expresiones polacas:

Una expresión simple:

a + b * c – d / e * h (1)

Representa a la expresión algebraica

(2)

Que al convertirse a su forma polaca queda como:

abc*+de/h*- (3)

Donde z es el resultado numérico final y las variables a, b, c,…, z son valores numéricos.


119

La notación polaca (1) se calcula de la siguiente manera:

1. Se inicializa una pila

2. Se recorre la expresión polaca de izquierda a derecha

3. Si el símbolo actual representa a un numero se apila , de otro modo (es un operador) se

sacan dos elementos de la pila y se realiza la operación cuyo resultado se apila:

Ejemplo: a = 5, b =3, c =1, d = 4, e = 2, h =5

Antes de llegar al símbolo *, la pila tendría los valores numéricos:

c 1

b 3

a 5

Se extraen dos elementos de la pila (c y d) y se ejecuta la operación <c><operdor><b>

R1 b * c (3 * 1 = 3) y este resultado se apila

R1 3

a 5

El siguiente símbolo es también un operador, luego se extraen dos elemento y se realiza la operación:

R2 a + R1 (5 + 3 = 8) y se apila:

R2 8

Siguientes símbolos que se extraen:

e 2

d 4

R2 8

R1 d ÷ e (4 ÷2 = 2) y se apila

R1 2

R2 8

Siguiente símbolo (h) se apila:

h 5

R1 2

R1 8

Operador *

R2 R1 * h (2 * 5 = 10)

R2 10

R1 8

El último símbolo es un operador (-), luego:

R3 R1 - R2 (8 – 10 = -2) y se apila:

R3 -2


120

4. El resultado de esta expresión es el elemento en el tope de la pila.

Ejercicio:

Construir una calculadora de expresiones algebraicas infijas que las convierta a su equivalente

polaca, y sea capaz de asignar valores numéricos a las variables para mostrar el resultado numérico

final. Algo como esto:

TxtINIFJA (TextBox, CharacterCasing = Lower) permite ingresar una expresión infija directamente o

desde el teclado alfanumérico.

Ejemplo:

Cuando se hace clic en el resultado se muestra en otro TextBox (txtRes, ReadOnly = True) y, si

es una expresión válida se activa el botón (btnRes, Enabled = False como valor inicial).

Al hacer clic en éste se extraes las variables de la expresión polaca y se muestran en el

DataGridView (DGV que se creó con dos columnas: cVar – Variable ReadOnly = True, cValue,

ReadOnly = False HeaderText= “Valor” - Numérica entera).


121

Se asignan entonces los valores de cada variable en la expresión

directamente en DGV.

Obtiene el resultado numérico y lo muestra en txtINFIJA.

Ingreso desde el teclado:

El conjunto de botones alfanuméricos:

Están nombrados como btn1, btn2, btn3,…., btn0.

Se usa la propiedad Tag de cada botón para asignar la letra:

btn1: Text 1a, Tag = a, bt2: Text 2b, Tag = b, etc.

El conjunto de operadores:

Botones nombrados btnX, btnDiv, btnSum, btnMinus, btnPot, btnPA “(“, btnPC “)” y

btnEq (“=”)

Se usa también la propiedad Tag para establecer cada operador:

btnX, Tag =*, btnDiv, Tag =/, etc,

Para ingresar valores desde el teclado de la calculadora se usa un solo evento Clic:


122

Private Sub btn1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btn1.Click, btn2.Click _

, btn3.Click, btn4.Click, btn5.Click, btn6.Click, btn7.Click, btn8.Click, btn9.Click,

btn0.Click

Dim oButton As Button = sender

txtINFIJA.SelectionStart = txtINFIJA.Text.Length

txtINFIJA.SelectedText = oButton.Tag

End Sub

Private Sub btnX_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnX.Click _

, btnDiv.Click, btnSum.Click, btnMinus.Click, btnPot.Click, btnPA.Click, btnPC.Click

Dim oButton As Button = sender

txtINFIJA.SelectionStart = txtINFIJA.Text.Length

txtINFIJA.SelectedText = oButton.Tag

End Sub

Private Sub btnEq_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnEq.Click

If txtINFIJA.Text.Trim.Length > 0 Then

Dim bValida As Boolean = False


Dim Infija As String = txtINFIJA.Text.Trim

Polaca.INFIJA = Infija

If InStr(Infija, "(") = 0 Then

txtRes.Text = Polaca.POLACASP(bValida)

Else

txtRes.Text = Polaca.POLACACP(bValida)

End If

btnRes.Enabled = bValida

End If

End Sub

En donde se hizo una ligera modificación a la clase CPolaca con el fin de saber si la expresión fue o

no válida.

Public Function POLACACP(Optional ByVal bValid As Boolean = False) As String

Dim PILA As New Stack

INFIJA += ")"

PILA.Push("(") '[1]

POLACA = "" '[2]

Dim Rango As Short = 0 '[2]


Do While Actual <> vbNullChar '[4]

If PILA.Count = 0 Then


Exit Function

End If

Do While FCP(Actual) < G(PILA.Peek) '5]

TEMP = PILA.Pop

POLACA += TEMP

Rango += RCP(TEMP)

If Rango < 1 Then


Exit Function

End If

Loop

If FCP(Actual) <> G(PILA.Peek) Then '[6]

PILA.Push(Actual)

Else

PILA.Pop()

End If


Loop

If PILA.Count <> 0 Or Rango <> 1 Then '[8]


123

POLACACP = "Expresión no válida"

Else

bValid = True

POLACACP = POLACA

End If

End Function

Public Function POLACASP(Optional ByRef bValid As Boolean = False) As String


Pila.Push("#") '...........................................[1]

Dim Rango As Short = 0 '...................................[2]

POLACA = ""

INFIJA += "#"

Actual = SIGUIENTE() '.....................................[3]

Do While Actual <> "#" '...................................[4]

Do While FSP(Actual) <= FSP(Pila.Peek) '...............[5]

TEMP = Pila.Pop

POLACA += TEMP

Rango += RSP(TEMP)

If Rango < 1 Then

POLACASP = "EXPRESION NO ES VALIDA"

Exit Function

End If

Loop

Pila.Push(Actual) '....................................[6]

Actual = SIGUIENTE()

Loop

Do While Pila.Peek <> "#" '................................[7]

TEMP = Pila.Pop

POLACA += TEMP

Rango += RSP(TEMP)

Loop

If Rango = 1 Then '........................................[8]

POLACASP = POLACA

bValid = True

Else

POLACASP = "EXPRESION NO VALIDA"

bValid = False

Exit Function

End If

End Function

Para extraer las variables de una expresión polaca válida usamos una colección que está declarada

como privada y las muestra en el DGV:

Public Class frmCalc

Private Variables As New Collection

Private Sub xVariables(ByVal Infija As String)

On Error Resume Next 'Omite valores duplicados

Variables.Clear()

DGV.Rows.Clear()

Dim L As Char, x As Integer

For i As Short = 0 To Infija.Length - 1

L = Infija.Substring(i, 1)

Select Case L

Case "a" To "z"

Variables.Add(L, Key:=L)

End Select

Next


124

For Each L In Variables

DGV.Rows.Add()

Dim R As DataGridViewRow = DGV.Rows(DGV.RowCount - 1)

R.Cells(0).Value = L

Next

End Sub

Luego deben introducirse directamente los valores numéricos de cada variable en la celda

correspondiente:

Finalmente:

Calcula el resultado final numérico y lo muestra:

Escribir este procedimiento de evento siguiendo la metodología descrita antes para obtenerlo.

Private Sub btnCalc_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnCalc.Click

'Ejercicio de evaluación

End Sub

Esta solución no es la única, puede intentar otra para alcanzar este objetivo usando cualquier otra

estructura de datos que considere pertinente.

Resultado:

Prepara la calculadora para ingresar otra expresión infija:

Private Sub btnCls_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnCls.Click


125

txtINFIJA.Clear()

txtRes.Clear()

DGV.Rows.Clear()

btnRes.Enabled = False

btnCalc.Enabled = False

End Sub

Recursión con ayuda de pilas:

Los procedimientos recursivos 27 pueden construirse con ayuda de pilas como lo muestra el

siguiente ejemplo:

En la unidad II se mostró el algoritmo recursivo para la función Factorial:

Este mismo procedimiento puede establecerse de la siguiente manera28:

FACTORIAL.- Dado un entero N, este algoritmo calcula N!. La pila P se usa para almacenar un

registro de activación asociado con cada llamada recursiva. Cada registro de activación contiene el

valor actual de N y la dirección actual retornada RET_ADDR. TEMP_REC es también un registro que

contiene dos variables: PARM y ADDRESS. Este registro temporal es necesario para simular la

apropiada transferencia de control desde un algoritmo de control del algoritmo FACTORIAL a otro.

Siempre que un TEMP_REC es colocado en la pila P, copias de PARM y ADDRESS son apiladas en A y

asignadas a N y a RET_ADDR respectivamente. Inicialmente la dirección de retorno se establece a la

llamada principal (por ejemplo: (ADDRESS dirección principal). PARM se establece con el valor

inicial de N.

27 Unidad II.

28 J.P. Tremblay.


126

1. Guardar N y regresar dirección:

P.PUSH(TEMP_REC)

2. ¿Se alcanzó el criterio base?

Si N =0 entonces

FACTORIAL 1

Ir al paso 4

De otro modo

ADDRESS Paso 3

Ir al paso 1

3. Calcular N!

FACTORIAL N * FACTORIAL

4. Restablecer el valor previo de N y regresar dirección:

TEMP_REC P.POP

(Ejemplo: PARM N, ADDRESS RET_ADDR, P.POP)

Ir a ADDRESS


127

4 Estructuras no lineales.

Competencia especifica.- Conocer y aplicar las estructuras no lineales en solución de problemas del

mundo real.

Árboles.

Definición.- Un árbol es una estructura de datos no lineal que se usa para almacenar datos de una

manera jerárquica. Un árbol es una estructura jerárquica que se aplica sobre una colección de de

elementos u objetos llamados nodos, uno de los cuales es llamado Raíz. Además se crea una

relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, sucesor,

ancestro, etc.29

Un árbol es pues un conjunto de nodos conectados por ramas. Un ejemplo de un árbol es el

organigrama de organización de una empresa.

Fig. 4. 1

29 Cairó/Guardati. Estructuras de datos. McGraw Hill.

Gerente General

Director de

Finanzas

F

Director de

Producción

Dirección de

Ventas

Jefe de operaciones Soporte técnico

Raíz


128

Otro tipo de árboles puede definirse en otros términos:

Fig 4.2

Si un nodo está conectado a otros nodos por debajo de él, se denomina nodo padre y a los nodos

por debajo de él se les denomina nodos hijos. Un nodo puede tener cero, uno ó más nodos

conectados a él. Existe una clase especial de árboles llamados Árboles Binarios que restringen el

número de hijos a no más de dos. Los árboles binarios tienen ciertas propiedades computacionales

que los hacen muy eficientes para muchas operaciones

En la figura 2 se puede observar que se pueden visitar ciertos nodos que no estén directamente

conectados siguiendo una Ruta de conexiones. Por ejemplo para llegar al nodo R, la ruta sería M

T R. El visitar todos los nodos de un árbol se denomina travesía.

Un árbol puede dividirse en dos niveles. El nodo raíz es el nivel 0, su hijo el nivel 1, sus hijos serían

el nivel 3 y así sucesivamente. Un nodo en cualquier nivel se considera la raíz de un sub-árbol el

cual consiste de esa raíz y sus hijos y los hijos de sus hijos. Se define la profundidad de un árbol

como número de capas en él.

Por último, cada nodo en el árbol tiene un valor algunas veces referido como el valor clave.

ARBOLES BINARIOS.

Un árbol binario se define como un árbol en el cual cada nodo no tiene más de dos hijos. Los nodos

hijos de un nodo padre son referidos como nodo izquierdo y nodo derecho. Para ciertas

M

D

C B A

T

W R

O

Nodo Raíz

F

H E Sub-árbol


129

implementaciones de árboles binarios los valores de los datos sólo pueden almacenarse en nodos

izquierdos y otros en nodos derechos. Por ejemplo:

Fig. 4.3

En este árbol los valores menores (a la raíz) se almacenan a la izquierda y los mayores a la derecha.

Recorridos en un árbol binario.

Se llama recorrido del árbol al procedimiento de visitar todos los nodos del mismo de diferentes

maneras. Existen tres métodos de recorridos sobre el árbol: inorder, preorder y postorder. El

recorrido inorder visita todos los nodos en orden ascendente de sus valores. Un recorrido en

preorder primero visita la raíz seguido de los nodos en los sub árboles del hijo izquierdo de la raíz.

Este procedimiento puede escribirse de manera recursiva. Puesto que el método visita cada nodo de

manera ascendente, debe además visitar tanto el hijo izquierdo como el derecho de cada sub árbol

siguiendo con los árboles a la izquierda de la raíz antes de continuar con los de la derecha.

En el recorrido en preorder la única diferencia entre ambos son tres líneas de código. La llamada al

procedimiento para visualizar un nodo está colocada entre las dos llamadas recursivas del método

inorder.

En el método postorder la diferencia con los dos anteriores es donde se coloca la llamada al

procedimiento para visualizar un nodo y las llamadas recursivas al procedimiento. En el recorrido

en postorder, el método primero hace recursión sobre los sub árboles izquierdos y luego sobre los

sub árboles derechos.

Valores mínimos y máximos en un árbol binario.

Para encontrar los valores máximo y mínimo en un árbol binario es casi trivial, en ambos casos

debido a las propiedades del mismo. El valor mínimo siempre se encontrará a la izquierda del hijo

izquierdo de un sub árbol comenzando con el hijo izquierdo de la raíz. Por otro lado, el valor

máximo se encuentra en el último nodo a la derecha del sub árbol comenzando con el hijo derecho

de la raíz.

53

30

40

80

17 75 90


130

Para encontrar el valor mínimo el método comienza creando un objeto nodo y estableciéndolo al

nodo raíz. Luego verifica que el valor en el hijo izquierdo sea nada. Si no lo es el programa establece

ese nodo al nodo actual. Esto continúa hasta encontrar un nodo cuyo hijo izquierdo sea nada. Esto

significa que no existe un valor menor debajo, y el valor mínimo ha sido localizado.

El método para localizar el valor máximo en un árbol binario luce similar al anterior excepto que se

mueve a través del hijo derecho.

Método de búsqueda en un árbol binario.

Permite determinar si un valor específico existe en el árbol. Primero se crea un nodo y se iguala a la

raíz, luego prueba donde se encontraría el valor buscado (izquierda ó derecha). Si lo encuentra el

método simplemente regresa el nodo actual. De otro modo si no se encuentra en el nodo raíz, el

dato se compara con el nodo actual. Si el valor buscado es menor que el del nodo actual entonces el

nodo actual se establece al hijo izquierdo o al hijo derecho si es mayor. El último segmento del

método regresará el valor de nada indicando el final de la búsqueda. Cuando termina el ciclo el valor

almacenado en el nodo actual (si no es nulo) es el valor encontrado.

Eliminar un nodo simple en una búsqueda binaria de un árbol a través de un recorrido.

En algunos casos la remoción de un nodo es generalmente trivial, en otros debe tenerse especial

cuidado con el código o se corre el riesgo de destruir la correcta estructura jerárquica del árbol

binario.

Fig. 4.4

Otro caso especial es la remoción de un nodo con dos hijos:

En el primer caso la solución es mover el sucesor inorder al lugar del nodo que se elimina (50). Esto

funciona bien a menos que el sucesor mismo tenga hijos. Para encontrar al sucesor del nodo

original hay que ir al nodo derecho original. Por definición, este nodo no debería ser mayor que el

nodo original. Luego se comienzan a seguir las rutas del hijo izquierdo. Puesto que el valor más

4

0

5

0

4

8

4

5

4

9

5

5

5

2

5

8

Nodo a eliminar

(No se puede eliminar

el sub-árbol).


131

pequeño del árbol debe estar al final de esta ruta, al final de la misma se marca el nodo más

pequeño que es más grande que el nodo original. (Por ejemplo si se elimina el 52).

Dos casos especiales requieren de especial atención, cuando el sucesor es el hijo derecho del nodo

que se va a remover y el otro cuando el sucesor es el hijo izquierdo del nodo a remover.

Primero el nodo ha de marcarse como el nodo actual. Remover este nodo del hijo derecho de su

padre y apuntar al nodo sucesor del hijo derecho y asignar el apuntador al nodo sucesor. Luego se

elimina el nodo actual y se asigna al nodo hijo izquierdo del nodo sucesor.

Por último, está el caso en que el nodo sucesor es el hijo izquierdo del nodo a remover. El algoritmo

que debe seguirse es:

1. Asignar el hijo derecho al nodo sucesor izquierdo del padre.

2. Asignar el hijo derecho del nodo a remover al nodo hijo derecho del nodo sucesor.

3. Remover el nodo actual del hijo derecho de su padre y apuntarlo al nodo sucesor.

4. Remover el nodo hijo izquierdo del nodo actual y asignarlo al nodo hijo izquierdo del nodo

sucesor.

Aplicación:

Crear un proyecto de Windows (con el nombre WinBTree).

Crear las clases:

Public Class CNodoAB

Public oDato As Object

Public IZQ As CNodoAB

Public DER As CNodoAB

Public Function VerNodo() As String

Return oDato.ToString & " "

End Function

End Class

Public Class CArbolB

Public Raiz As CNodoAB

Public Sub New()

Raiz = Nothing

End Sub

Public Sub Inserta(ByVal x As Object)

Dim NodoNvo As New CNodoAB

NodoNvo.oDato = x

If Raiz Is Nothing Then

Raiz = NodoNvo

Else

Dim Actual As CNodoAB = Raiz

Dim Padre As CNodoAB


132

Dim Insertado As Boolean = False

Do While Not Insertado

Padre = Actual

If x < Actual.oDato Then

Actual = Actual.IZQ

If Actual Is Nothing Then

Padre.IZQ = NodoNvo

Insertado = True

End If

Else

Actual = Actual.DER


Padre.DER = NodoNvo

Insertado = True

End If

End If

Loop

End If

End Sub

Public Sub InOrder(ByVal LaRaiz As CNodoAB, ByRef Salida As String)

If Not LaRaiz Is Nothing Then

InOrder(LaRaiz.IZQ, Salida)

Salida += LaRaiz.VerNodo

InOrder(LaRaiz.DER, Salida)

End If

End Sub

Public Sub PreOrder(ByVal LaRaiz As CNodoAB, ByRef Salida As String)


Salida += LaRaiz.VerNodo()

PreOrder(LaRaiz.IZQ, Salida)

PreOrder(LaRaiz.DER, Salida)

End If

End Sub

Public Sub PostOrder(ByVal LaRaiz As CNodoAB, ByRef Salida As String)


PostOrder(LaRaiz.IZQ, Salida)

PostOrder(LaRaiz.DER, Salida)

Salida += LaRaiz.VerNodo()

End If

End Sub

Public Function Busca(ByVal k As Integer) As CNodoAB


Do While Actual.oDato <> k

If k < Actual.oDato Then

Actual = Actual.IZQ

Else

Actual = Actual.DER

End If


Return Nothing

End If

Loop

Return Actual

End Function

Public Function BuscaMin() As Object


Do While Not Actual.IZQ Is Nothing

Actual = Actual.IZQ

Loop

Return Actual.oDato

End Function

Public Function BuscaMax() As Object


Do While Not Actual.DER Is Nothing

Actual = Actual.DER

Loop

Return Actual.oDato

End Function

Public Function ObtenSucesor(ByVal Nodo As CNodoAB) As CNodoAB

Dim PadreSucesor As CNodoAB = Nodo

Dim Sucesor As CNodoAB = Nodo


133

Dim Actual As CNodoAB = Nodo.DER

Do While Not Actual Is Nothing

PadreSucesor = Sucesor

Sucesor = Actual

Actual = Actual.IZQ

Loop

If Not Sucesor Is Nodo.DER Then

PadreSucesor.IZQ = Sucesor.DER

Sucesor.DER = Nodo.DER

End If

Return Sucesor

End Function

Public Function Borra(ByVal K As Object) As Boolean


Dim Padre As CNodoAB = Raiz

Dim EsHijoIzq As Boolean = True

Do While Actual.oDato <> K

Padre = Actual

If K < Actual.oDato Then

EsHijoIzq = True

Actual = Actual.IZQ

Else

EsHijoIzq = False

Actual = Actual.DER

End If


Return False

End If

Loop

If Actual.IZQ Is Nothing And Actual.DER Is Nothing Then

If Actual Is Raiz Then

Raiz = Nothing

ElseIf EsHijoIzq Then

Padre.IZQ = Nothing

Else

Padre.DER = Nothing

End If

ElseIf Actual.DER Is Nothing Then


Raiz = Actual.IZQ


Padre.IZQ = Actual.IZQ

Else

Padre.DER = Actual.DER

End If

ElseIf Actual.IZQ Is Nothing Then


Raiz = Actual.DER


Padre.IZQ = Padre.DER

Else

Padre.DER = Actual.DER

End If

Else

Dim Sucesor As CNodoAB = ObtenSucesor(Actual)


Raiz = Sucesor


Padre.IZQ = Sucesor

Else

Padre.DER = Sucesor

End If

Sucesor.IZQ = Actual.IZQ

End If

Return True

End Function

End Class

La forma (frmBTree):


134

Fig. 4.5

Controles en la forma:

Nombre Tipo Descripción txtDato TextBox. ReadOnly = True

CaracterCasing = Upper Permite el ingreso de datos.

btnOK Button Acepta el dato.

CheckBox Indica que los datos que se ingresan son

números. lstDatos ListBox Muestra los datos del árbol. txtSalida TextBox Multiline,

ScrollBars = Both, WordWrap = False

Muestra diferentes recorridos del árbol.

btnDel Button Elimina el nodo seleccionado (en la lista).

btnCLS Button Limpia el árbol.

btnSave Button Guarda la secuencia de datos de entrada.

btnOpen Button Abre un archivo de datos de entrada.

btnPostOrder

Button Recorre el árbol en Postorden.

btnInOrder

Button Recorre el árbol en orden.

btnPreOrder

Button Recorre el árbol en pre orden.

btnClose Button Cierra la aplicación.

btnMax Button Encuentra el nodo mayor

btnMin Button Encuentra el nodo menor

SaveFileDialog. DefaultExt = dat, Filter = Archivos de datos (*.dat)|*.dat

Diálogo para guardar archivos.

OpenFileDialog, con las mismas especificaciones que el anterior.

Diálogo para abrir archivos.


135

Código de la forma:

Public Class frmBTree

Private Ruta As String, A As Integer

Private Arbol As CArbolB

Private Sub frmBTree_Load(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles MyBase.Load

Ruta = My.Application.Info.DirectoryPath + "\datosBT"

If Not My.Computer.FileSystem.DirectoryExists(Ruta) Then

My.Computer.FileSystem.CreateDirectory(Ruta)

End If

Ruta += "\"

SaveFD.InitialDirectory = Ruta

Arbol = New CArbolB

End Sub


Handles btnOK.Click

Dim Dato As Object

Dato = txtDato.Text

If chkNum.Checked Then

Dato = CInt(Dato)

End If

Arbol.Inserta(Dato)

lstDatos.Items.Add(Dato)

txtDato.Clear()

txtDato.Focus()

End Sub



lstDatos.Items.Clear()

txtSalida.Clear()

Arbol = New CArbolB

txtDato.Clear()

End Sub



If lstDatos.Items.Count > 0 Then

Dim sFile As String

A = SaveFD.ShowDialog

If A = vbOK Then

sFile = SaveFD.FileName

Dim N As Short = FreeFile()

FileOpen(N, sFile, OpenMode.Output)

For Each Dato As Object In lstDatos.Items

PrintLine(N, Dato)

Next

FileClose(N)

MsgBox("Datos de entrada guardados", MsgBoxStyle.Information)

End If

End If

End Sub



A = OpenFD.ShowDialog()

If A = vbOK Then

Dim sFile As String = OpenFD.FileName

btnCLS.PerformClick()

Dim N As Short = FreeFile()

FileOpen(N, sFile, OpenMode.Input)

Dim Dato As Object

Do While Not EOF(N)

Dato = LineInput(N)

If IsNumeric(Dato) Then

Dato = CInt(Dato)

chkNum.Checked = True


136

End If

Arbol.Inserta(Dato)

lstDatos.Items.Add(Dato)

Loop

FileClose(N)

End If

End Sub



Close()

End Sub

Private Sub btnInOrder_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnInOrder.Click

txtSalida.Clear()

Dim Salida As String = ""

Arbol.InOrder(Arbol.Raiz, Salida)

txtSalida.Text = Salida

End Sub

Private Sub btnPostOrder_Click(ByVal sender As System.Object, ByVal e As

System.EventArgs) Handles btnPostOrder.Click

txtSalida.Clear()


Arbol.PostOrder(Arbol.Raiz, Salida)


End Sub

Private Sub btnPreorder_Click(ByVal sender As System.Object, ByVal e As

System.EventArgs) Handles btnPreorder.Click

txtSalida.Clear()


Arbol.PreOrder(Arbol.Raiz, Salida)


End Sub




btnOK.PerformClick()

End If

End Sub

Private Sub btnDel_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnDel.Click

If Not lstDatos.SelectedItem Is Nothing Then

Dim x As Object = lstDatos.SelectedItem

Arbol.Borra(x)

btnInOrder.PerformClick()

lstDatos.Items.Remove(x)

End If

End Sub

Private Sub btnMax_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnMax.Click

MsgBox(Arbol.BuscaMax.ToString, MsgBoxStyle.OkOnly, "MAYOR")

End Sub

Private Sub btnMin_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnMin.Click

MsgBox(Arbol.BuscaMin.ToString, MsgBoxStyle.OkOnly, "MENOR")

End Sub

End Class

Ejecución:


137

Fig. 4.6.

Dato no numéricos:

Secuencia de entrada.

(Fig. 4.4)


138

Fig. 4.7. Aplicación en ejecución.

Fig. 4.8.

Secuencia de entrada.

FERNANDE

Z

ALVAREZ

DIAZ

LOPEZ

BERNAL CANALES


139

Ejercicios:

1. Agregar una función a la clase CArbolB que cuente el número de ramas en el árbol.

2. Escribir un programa que lea un archivo de texto que almacene en el árbol y despliegue todas

las palabras en el archivo y encuentre el número de veces que aparecen en el archivo.

3. Una expresión aritmética como 3 + 4 * 5 / 6 puede ser evaluada usando la correcta precedencia

de operadores. Modifique la clase CArbolB para hacer esto.

Árboles Balanceados (AVL Trees).

Nombrada así (en inglés) por los dos científicos de la computación quienes descubrieron esta

estructura da datos: G.M. Alelson-Velskii y E.M. Lands – en 1962. Los árboles balanceados

proporcionan otra solución para mantener balanceados los árboles binarios. La característica que

define a un árbol balanceado es que la diferencia entre la altura de los sub árboles derecho e

izquierdo no puede ser nunca mayor que una.

Fundamentos de árboles balanceados:

Para garantizar que un árbol permanece balanceado, éste compara continuamente las alturas de los

sub árboles derecho e izquierdo usando una técnica llamada rotación para mantenerlo en balance.

Para entender cómo trabaja la rotación, considérese el ejemplo siguiente:

4

0

3

0


140

Fig. 4.9.

Si se inserta un valor intermedio (como 10):

Fig. 4.10.

El sub árbol izquierdo tiene un tamaño de 2 pero el derecho lo tiene de cero, violando las reglas de

los árboles balanceados. El árbol se balancea realizando una rotación simple derecha, moviendo 40

abajo a la derecha y el 30 arriba a la derecha resultando:

Fig. 4.11. Árbol balanceado.

Otro caso:

Fig. 4.12. Árbol balanceado

4

0

3

0

1

0

3

0

1

0

4

0

3

0

4

0 3

0

4

0

2

5

3

0

4

0

2

5


141

Fig. 4.13. Árbol balanceado.

GRAFOS.

Introducción.- El estudio de redes se ha vuelto uno de los grandes temas científicos de estudio en

este milenio, aún y cuando matemáticos y otros han estado estudiando redes durante cientos de

años. Los recientes avances en las tecnologías de información (por ejemplo el internet) y en las

redes sociales, popularmente concebidas en el concepto de “seis grados de separación” han

colocado en el foco de la atención su estudio.

DEFINICIONES.

Un grafo consiste en una colección de vértices y un conjunto de ramificaciones. Si se piensa en el

mapa de los estados México, cada población está conectada con otras a través de algún tipo de

camino. Un mapa es un tipo de grafo, cada población es un vértice y el camino que conecta a dos

poblaciones es una rama. Los nodos que son especificados como un par (v1 y v2), donde v1 y v2 son

dos vértices en el grafo. Un vértice puede también tener además un peso algunas veces llamado

también costo.

Un grafo cuyos pares están ordenados se llama un grafo directo o simplemente un dígrafo. Si el

grafo no está ordenado se llama un grafo desordenado o simplemente un grafo.

Fig. Grafo directo (digrafo).

Fig. Grafo desordenado (indirecto – no direccionado).

A B C

D E F

G H

1 2 3

4 5 6


142

Una ruta es una secuencia de vértices en un grafo de manera que todos los vértices estén

conectados por ramas. El tamaño (longitud) de una ruta es el número de ramas desde el primer al

último vértice en la ruta. Una ruta puede también ser un vértice en sí mismo, el cual se llama un

lazo. Los lazos tienen una longitud de cero.

Un ciclo es una ruta de al menos 1 en un grafo directo para que el vértice de inicio sea también el

vértice final. En un grafo directo las ramas pueden ser también una misma rama, pero en un grafo

indirecto las ramas pueden ser distintas.

Un grafo indirecto se considera conectado si existe una ruta desde cualquier vértice a cualesquiera

otros vértices. En un grafo directo (o direccionado) a esta condición se le llama altamente conectado.

Un grafo directo que no está altamente conectado, pero es considerado conectado, se denomina

poco conectado. Si un grafo tiene una rama entre cada conjunto de vértices se dice que es un grafo

completo.

Sistemas del Mundo Real modelados con Grafos.

Los grafos son usados para modelar diferentes tipos de sistemas del mundo real. Un ejemplo es el

flujo de tráfico. Los vértices representan intersecciones entre calles y las ramas representan a las

calles mismas. Grafos ponderados pueden usarse para representar los límites de velocidad o el

número de carriles o callejones.

Los modeladores pueden usar el sistema para determinar las mejores rutas y las mejores calles

alternas para navegar en tráfico denso.

Cualquier tipo de sistema de transporte puede modelarse usando un grafo. Por ejemplo, una línea

aérea puede modelar su sistema de vuelos usando un grafo. Cada aeropuerto en un vértice y cada

vuelo de un vértice a otro es una rama. Una rama ponderada puede representar el costo de un vuelo

desde un aeropuerto a otro, o la distancia entre uno y otro.

LA CLASE GRAFO.

Representación de Vértices:

Matriz adyacente. Donde se representan los vértices visitados (valores booleanos).- Arreglo de dos

dimensiones (matriz) donde los elementos indican si existe una rama entre dos vértices.

0 1

2

3 4


143

V0 V1 V2 V3 V4

V0 0 0 1 0 0

V1 0 0 1 0 0

V2 1 1 0 1 1

V3 0 0 1 0 0

V4 0 0 1 0 0

Public Class CVertice

Public Visitado As Boolean

Public Etiqueta As String

Public Sub New(ByVal Texto As String)

Etiqueta = Texto

Visitado = False

End Sub

End Class

Public Class CGrafo

Private Const NUM_V As Integer = 20

Private Vertices() As CVertice

Private AdjMatrix(,) As Integer

Private NumV As Integer

Public Sub New()

ReDim Vertices(NUM_V)

ReDim AdjMatrix(NUM_V, NUM_V)

NumV = 0

Dim i, j As Integer

For i = 0 To NUM_V - 1

For j = 0 To NUM_V - 1

AdjMatrix(i, j) = 0

Next

Next

End Sub

Public Sub AddVertex(ByVal Texto As String)

Vertices(NumV) = New CVertice(Texto)

NumV += 1

End Sub

Public Sub AddEdge(ByVal iStart As Integer, ByVal iEnd As Integer)

AdjMatrix(iStart, iEnd) = 1

AdjMatrix(iEnd, iStart) = 1

End Sub

Public Sub ShoVertex(ByVal v As Integer)

Console.Write(Vertices(v).Etiqueta)

End Sub

End Class


144

Aplicación: Clasificación Topológica:

Una clasificación topológica involucra desplegar el orden especifico en el cual una secuencia de

vértices debe ser seguido en un grafo direccionado. La secuencia de cursos que un estudiante de

licenciatura debe tomar para

obtener el grado puede modelarse

con un grafo direccionado.

Para cursar la materia de Estructuras de

Datos, un estudiante debe haber

cursado (y aprobado) :

Fundamentos de

Programación

Matemáticas para

computadora

Programación Orientada a Objetos.

En el caso de la retícula de ISC:

Fundamentos

de

Programación

Programación

OO Estructuras

de Datos

Lenguaje

Ensamblador

Fundamentos

de Bases de

Datos

Matemáticas

para Comp.


145

Algoritmo básico de clasificación topológica:

1. Encontrar un vértice sin sucesores.

2. Agregar el vértice a la lista de los mismos.

3. Remover el vértice del grafo.

4. Repetir desde el paso #1 hasta que todos los vértices sean removidos.

0 1 2 3

FP OOP ED LE

FP 1 0

OOP 1 1

ED 1 2

LE 3

A(0, 1) = 1

A(1, 2) = 1

A(2, 3) = 1

Vértices:

FP OOP ED LE

A(0, 1) Rama

Se quita:

OOP ED LE LE

FP

MoveRow y MoveCol en Del Vertex30:

0 1 2 3

OOP ED LE LE

30 Mover renglón y mover columna del vértice.


146

OOP 1 0

ED 1 1

LE 1 1 2

LE 3

BUSQUEDA EN PROFUNDIDAD (Depth-First Search)31.

Esta búsqueda involucra el segur una ruta desde el vértice inicial hasta alcanzar el último vértice,

luego se regresa para seguir la siguiente ruta hasta alcanzar el último vértice y así sucesivamente

hasta que no existan rutas que seguir.

Fig.

En un alto nivel, la búsqueda en profundidad trabaja así: Primero se marca un punto de inicio el cual

puede ser cualquier vértice. Visitar el vértice, apilarlo y marcarlo como visitado. Luego ir al siguiente

vértice no visitado, apilarlo y marcarlo. Esto continúa hasta alcanzar el último vértice. Luego se

verifica si el vértice en el tope tiene algunos vértices adyacentes no visitados. Si no lo hay entonces

se vacía la pila y se verifican los siguientes vértices. Si se encuentra uno, se comienzan a visitar

vértices adyacentes hasta que no existan más sin ser visitados. Cuando finalmente se alcanza el

último vértice en la pila y no hay más vértices adyacentes no visitados se ha completado una

búsqueda en profundidad.

Public Class CGrafo



31 McMillan.-Data Structures and Algortithms Using Visual Basic .NET.

A

K

L

M

H

I

J

E

F

G

B

C

D


147



….

Private Function getAdjUnvisitedVertex(ByVal v As Integer) As Integer

Dim j As Integer

For j = 0 To NumV - 1

If AdjMatrix(v, j) = 1 And Not Vertices(j).Visitado Then

Return j

End If

Next

Return -1

End Function

Public Sub DepthFirstSearch()


Vertices(0).Visitado = True

ShoVertex(0)

Pila.Push(0)

Dim v As Integer

Do While Pila.Count > 0

v = getAdjUnvisitedVertex(Pila.Peek)

If v = -1 Then

Pila.Pop()

Else

Vertices(v).Visitado = True

ShoVertex(v)

Pila.Push(v)

End If

Loop

Dim j As Integer

For j = 0 To NumV - 1

Vertices(j).Visitado = False

Next

End Sub

'Búsqueda a lo ancho:

Public Sub BreadthFirstSearch()

Dim GQ As New Queue

Vertices(0).Visitado = True

ShoVertex(0)

GQ.Enqueue(0)

Dim Vert1, Vert2 As Integer

Do While GQ.Count > 0

Vert1 = GQ.Dequeue

Vert2 = getAdjUnvisitedVertex(Vert1)

Do While Vert2 <> -1

Vertices(Vert2).Visitado = True

ShoVertex(Vert2)

GQ.Enqueue(Vert2)

Vert2 = getAdjUnvisitedVertex(Vert1)

Loop

Loop

Dim I As Integer

For I = 0 To NumV - 1

Vertices(I).Visitado = False

Next

End Sub

End Class


Module Module1

Sub Main()



Clear()

Dim Grafo As New CGrafo

With Grafo

.AddVertex("A")

.AddVertex("B")


148

.AddVertex("C")

.AddVertex("D")

.AddVertex("E")

.AddVertex("F")

.AddVertex("G")

.AddVertex("H")

.AddVertex("I")

.AddVertex("J")

.AddVertex("K")

.AddVertex("L")

.AddVertex("M")

.AddEdge(0, 1)

.AddEdge(1, 2)

.AddEdge(2, 3)

.AddEdge(0, 4)

.AddEdge(4, 5)

.AddEdge(5, 6)

.AddEdge(0, 7)

.AddEdge(7, 8)

.AddEdge(8, 9)

.AddEdge(0, 10)

.AddEdge(10, 11)

.AddEdge(11, 12)

End With

Grafo.DepthFirstSearch()

'==== BUSQUEDA A LO ANCHO 'Grafo.BreadthFirstSearch()

WriteLine()

ReadKey()

End Sub

End Module

Otro ejemplo:

Public Class CGrafo





Public Sub New()

ReDim Vertices(NUM_V)

ReDim AdjMatrix(NUM_V, NUM_V)

NumV = 0

Dim i, j As Integer


149

For i = 0 To NUM_V - 1

For j = 0 To NUM_V - 1

AdjMatrix(i, j) = 0

Next

Next

End Sub

Public Sub AddVertex(ByVal Texto As String)

Vertices(NumV) = New CVertice(Texto)

NumV += 1

End Sub

Public Sub AddEdge(ByVal iStart As Integer, ByVal iEnd As Integer)

AdjMatrix(iStart, iEnd) = 1

AdjMatrix(iEnd, iStart) = 1

End Sub

Public Sub ShoVertex(ByVal v As Integer)

Console.Write(Vertices(v).Etiqueta)

End Sub

Public Function SinSucesor() As Integer

Dim EsRama As Boolean

Dim R, C As Integer

For R = 0 To NumV - 1

EsRama = True

For C = 0 To NumV - 1

If AdjMatrix(R, C) > 0 Then

EsRama = True

Exit For

End If

Next

If Not EsRama Then

Return -1

Else

Return R

End If

Next

End Function

Private Sub MoveRow(ByVal R As Integer, ByVal L As Integer)

Dim C As Integer

For C = 0 To L - 1

AdjMatrix(R, C) = AdjMatrix(R + 1, C)

Next

End Sub

Private Sub MoveCol(ByVal C As Integer, ByVal L As Integer)

Dim R As Integer

For R = 0 To L - 1

AdjMatrix(R, C) = AdjMatrix(R, C + 1)

Next

End Sub

Public Sub DelVertex(ByVal v As Integer)

Dim j, R, C As Integer

If v <> NumV - 1 Then

For j = v To NumV - 1

Vertices(j) = Vertices(j + 1)

Next

For R = v To NumV - 1

MoveRow(R, NumV)

Next

'NumV -= 1

For C = v To NumV - 1

'MoveCol(C, NumV - 1)

MoveCol(NumV - 1, C)

Next

End If

End Sub

Public Sub TopSort()

Dim OV As Integer = NumV

Dim gStack As New Stack

Dim sTemp As String

Do While OV > 0


150

Dim CurrV As Integer = SinSucesor()

If CurrV = -1 Then

Console.WriteLine("Error: El Grafo tiene ciclos")

Exit Sub

End If

sTemp = Vertices(CurrV).Etiqueta

gStack.Push(Vertices(CurrV).Etiqueta)

DelVertex(CurrV)

OV -= 1

Loop

Console.WriteLine("Orden Topólogico:")

Do While gStack.Count > 0

sTemp = gStack.Pop

Console.Write(sTemp & " ")

Loop

End Sub

Public Function TopSorting() As String

Dim sTopS As String = ""

Dim OV As Integer = NumV

Dim gStack2 As New Stack

Do While OV > 0

Dim CurrV As Integer = SinSucesor()

If CurrV = -1 Then

sTopS = "Error: El Grafo tiene ciclos"

Return sTopS

Exit Function

End If

gStack2.Push(Vertices(CurrV).Etiqueta)

DelVertex(CurrV)

OV -= 1

Loop

'============================================

Dim Salida() As String

ReDim Salida(gStack2.Count)

Dim i As Short = 0

'============================================

Do While gStack2.Count > 0

Salida(i) = gStack2.Pop + " "

i += 1

Loop

For i = Salida.GetUpperBound(0) To 0 Step -1

sTopS += Salida(i)

Next

Return sTopS

End Function

End Class

Plan reticular.


151

5 Métodos de Ordenamiento.

Competencia especifica.- Aplicar el método de ordenamiento pertinente en la solución de un

problema real.

Definición.- Se denomina ordenamiento (sort) al proceso de ordenar una serie de datos que

generalmente están en un arreglo. Este proceso y la búsqueda (search) de algún dato en particular

son probablemente las operaciones más estudiadas en la Ciencia de la Computación desde el

principio de su era. Muchas de las estructuras que se han desarrollado en este libro fueron

diseñadas principalmente para ordenar y buscar datos y hacer más eficiente el almacenamiento de

datos en ellas.

Aunque los investigadores en esta ciencia han desarrollado varios algoritmos sofisticados para

ordenar datos, existen algunos muy simples que el estudiante debe analizar. Estos son: El sort de la

burbuja y el sort por selección.

Para probar estos algoritmos, se propone construir la siguiente aplicación:


152

Donde se puede crear un arreglo de gran tamaño (relativamente) y mostrar la eficiencia de los

algoritmos para ordenar y otra para probarlos analizándolos en arreglo pequeños.


153

Control (nombre) Tipo Propiedades

frmSort Forma MaximizeBox = False

NumN (1), NumM (2)

NumericUpDown 1.- Maximum = 5000, Minimum = 100 (determina el

tamaño del arreglo)

2.- Maximum = 50, Minimum = 20 (el número de

columnas a desplegar en la caja de texto).

btnOK Button Crea el arreglo y lo llena aleatoriamente con números en

el rango especificado (por defecto 1000 – 9999.

txtMin, txtMax

TextBox Especifica el rango en que se generarán los números en el

arreglo.

NumTest NumericUpDown Maximum = 20 (Limita a20 el tamaño del arreglo de

prueba).

Minimum = 10 (El tamaño mínimo del arreglo).

chkTest CheckBox Determina el tipo de arreglo a crear (pequeño o grande).

btnCrear Button Crea un arreglo pequeño y lo muestra en el DataGridView.

DGVA

DataGridView. AllowUserToAddRows = False, AutosizeColumnsMode =

AllCells

PB PregressBar Visible = False

txtArreglo

TextBox BackColor = White, Multiline = True, ScrollBars = Both,

WordWrap = False.

btnBSort, btnSSel

Button Ejecuta los métodos de ordenamiento burbuja y selección.

btnQSort, btnShell

Button Ejecuta los procedimientos señalados.

Ordenamiento por Selección.

Este procedimiento se basa en la manera en se ordenan dato manualmente. Por ejemplo si se tienen

las credenciales de los estudiantes de un grupo en principio desordenadas éstas pueden ordenarse

por apellidos (por ejemplo).

García Canales Puente López Acevedo Bernal

Se forma una pila con estas credenciales:

García

Canales

Puente

López

Acevedo

Bernal

Se toma la credencial en el tope (García) y se forma otra pila con ella:


154

García

Luego se toma la siguiente (de la pila original), que en este caso es Pérez y se acomoda en la

segunda pila de manera que queden ordenadas:

Canales Canales Canales Acevedo Acevedo

García García Canales Bernal

Puente López García Canales

Puente López García

Puente López

Puente

Las credenciales están ordenadas.

Ejemplo con números:

N = 9 (10 elementos).

i ↓

0 1 2 3 4 5 6 7 8 9

64 49 53 27 28 70 3 29 69 64 j ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑

49 64 53 27 28 70 3 29 59 64

27 64 23 49 28 70 3 29 59 64

3 64 23 49 28 70 27 29 59 64

Siguiente recorrido de i (i 1) i ↓

3 64 23 49 28 70 27 29 59 64 j ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3 23 64 49 28 70 27 29 59 64 i 2 i ↓ 3 23 64 49 28 70 27 29 59 64 ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3 23 49 64 28 70 27 29 69 64 i 3

I ↓ 3 23 49 64 28 70 27 29 69 64 3 23 49 28 64 70 27 29 69 64 3 23 49 27 64 70 28 29 69 64 j ↑ ↑ ↑ ↑ ↑ ↑ i 4 i ↓ 3 23 49 27 64 70 28 29 59 64 j ↑ ↑ ↑ ↑ ↑ 3 23 49 27 28 70 64 29 59 64 i 5

i ↓ 3 23 49 27 28 70 64 29 59 64 j ↑ ↑ ↑ ↑ 3 23 49 27 28 64 70 29 59 64 3 23 49 27 28 29 70 64 59 64 i 6

En el primer recorrido (i 0) se hacen intercambios

para las posiciones (j 1, 3, y 6.

Para el siguiente valor de i (i 1), ocurren un sólo

intercambio en j 2.

Para i 2, también ocurre un intercambio en j 3.

En i 3, ocurren intercambios en j 4 y 6.

Para i 4 se hace un intercambio en j 5, y en i 5

sólo se intercambia para j 6.

En i 6 se intercambia para j 7 y 8 y para i 7 en j

8.


155

i ↓ 3 23 49 27 28 29 70 64 59 64 j ↑ ↑ 3 23 49 27 28 29 64 70 59 64 3 23 49 27 28 29 59 70 64 64 i 7

i ↓ 3 23 49 27 28 29 59 70 64 64 j ↑ ↑ 3 23 49 27 28 29 59 64 70 64 3 23 49 27 28 29 59 64 64 70

Implementación:


Module Module1

Sub Main()



Clear()

Dim Arreglo() As Integer = {64, 49, 53, 27, 28, 70, 3, 29, 59, 64}

Dim i, j, Temp, N As Integer

N = 9

WriteLine("Arreglo desordenado:")

VerArreglo(Arreglo, N)

WriteLine("Valores intermedios en el arreglo:")

ReadKey()

For i = 0 To N - 1

For j = i + 1 To N

If Arreglo(j) < Arreglo(i) Then

Temp = Arreglo(i)

Arreglo(i) = Arreglo(j)

Arreglo(j) = Temp

End If

Next


Next

WriteLine()

WriteLine("Arreglo ordenado:")


ReadKey()

End Sub

Private Sub VerArreglo(ByRef Arr() As Integer, ByRef N As Integer)


Write(Arr(i).ToString.PadLeft(2) & " ")

Next

WriteLine()

End Sub

End Module

Ejecución:


156

Así con algunas ligeras modificaciones (quitando las relativas a la consola), se pasa este

procedimiento al la forma de Windows ®.

Private Sub btnSSel_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnSSel.Click

SortSel()

End Sub

Private Sub SortSel()

Dim i, j, Temp As Integer

For i = 0 To N - 1

For j = i + 1 To N

If Arreglo(j) < Arreglo(i) Then

Temp = Arreglo(i)


Arreglo(j) = Temp

End If

Next

Next

If chkTest.Checked Then

VerEnGrid()

VerArreglo()

Else

VerArreglo()

End If

End Sub


157

Ordenamiento de la burbuja (Bubble Sort):

Este método es una mejora al de selección en donde no siempre es necesario hacer N – 1 iteraciones

ya que cada vez hay un decremento en el recorrido del arreglo y cada vez que termina una iteración,

el elemento mayor queda en su lugar por lo que ya no requiere ser evaluado.


Module Module1

Sub Main()



Clear()

Dim Arreglo() As Integer = {64, 49, 53, 27, 28, 70, 3, 29, 59, 64}

Dim N As Integer

N = Arreglo.GetUpperBound(0)

WriteLine("Arreglo desordenado:")


WriteLine("Valores intermedios en el arreglo:")

ReadKey()

Bubble(Arreglo, N)

WriteLine()

WriteLine("Arreglo ordenado:")


ReadKey()

End Sub

Private Sub Bubble(ByRef Arr() As Integer, ByVal N As Integer)

Dim U, i, Temp, Cta As Integer


158

Dim bSorted As Boolean = False

U = N : Cta = 0

Do While Not bSorted

For i = 0 To U - 1

If Arr(i) > Arr(i + 1) Then

Temp = Arr(i)

Arr(i) = Arr(i + 1)

Arr(i + 1) = Temp

Cta += 1

End If

Next

VerArreglo(Arr, N)

If Cta = 0 Then

bSorted = True

Else

Cta = 0

U -= 1

End If

Loop

End Sub

Private Sub VerArreglo(ByRef Arr() As Integer, ByRef N As Integer)



Next

WriteLine()

End Sub

End Module

Y en la forma:

Private Sub btnBSort_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnBSort.Click

Burbuja()

End Sub

Private Sub Burbuja()

'Modificado:


Dim U = N

Dim iCta, iTemp As Integer



159

iCta = 0

For i As Integer = 0 To U - 1

If Arreglo(i) > Arreglo(i + 1) Then

iTemp = Arreglo(i)

Arreglo(i) = Arreglo(i + 1)

Arreglo(i + 1) = iTemp

iCta += 1

End If

Next

If iCta = 0 Then

bSorted = True

Else

U -= 1

Cta = 0

End If

Loop

VerArreglo()


VerEnGrid()

End If

End Sub

Quick Sort (Ordenamiento rápido).

Este método tiene una merecida reputación de ser el algoritmo más rápido de los vistos en este

capítulo lo cual es verdad sólo para la mayoría de grandes conjuntos de datos desordenados. Si los

datos son cuando mucho 100 o menos es recomendable usar cualquiera de los métodos analizados

antes.

Para visualizar como opera este algoritmo, imagine que debe ordenar alfabéticamente los trabajos

de los estudiantes de su grupo. Se selecciona una letra intermedia del alfabeto, por ejemplo M,

luego se colocan los trabajos de los estudiantes cuyos apellidos comiencen con las letras A-M en

una pila y los apellidos N-Z en otra. Luego se repite el mismo proceso pero haciendo pilas más

pequeñas, por ejemplo A-C, D-F, …, X-Z que después son más fáciles de ordenar. Puede verse que

este es un proceso recursivo.


160

Algoritmo QickSort 32 .- Dado un arreglo A[N] el siguiente algoritmo lo ordena en forma ascendente.

Se asume un registro ficticio en A[N + 1] que es mayor que los demás elementos del arreglo: A[i] ≤

A[N + 1] (para toda 0 ≤ i ≤ N) 33. Se tienen dos parámetros LI y LS que denotan los límites

inferior y superior de la partición que está siendo procesada. La variable K contiene el valor que ha

de colocarse en su posición final dentro de una partición. F es una variable lógica que indica el final

del proceso que coloca un registro en su posición final. Cuando se hace falso, la tabla de entrada ha

sido particionada en dos partes desunidas.

1. Inicio.

F Verdadero

2. Efectuar ordenamiento:

Si LI ≤ LS, entonces i LI j LS + 1 K A[LI] Repetir mientras F i i + 1 Repetir mientras A[i] < K (moverse de izquierda a derecha) i i + 1 [Fin Mientras] j j -1 Repetir mientras A[j] > K j j- 1 [Fin Mientras] Si i < j entonces A[i] ↔ A[j] (se intercambian registros) De otro modo F Falso [Fin Si] [Fin Mientras] A[LI] ↔ A[j] (intercambio de registros) Llamada recursiva QuicSort(LI, j -1) Llamada recursiva QuickSort(j+1, LS)

3. Termina.

Con algunas modificaciones, este es el código:

Private Sub btnQSort_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnQSort.Click

Dim LI As Integer = Arreglo.GetLowerBound(0)

Dim LS As Integer = Arreglo.GetUpperBound(0)

QSort(LI, LS)

VerArreglo()

End Sub

Private Sub QSort(ByVal LI As Integer, ByVal LS As Integer)

Dim F As Boolean, j, i, K As Integer

Dim T As Integer = 0

F = True

If LI < LS Then

32 Tremblay.

33 Asumiendo que el arreglo comienza desde la posición cero.


161

i = LI

j = LS + 1

K = Arreglo(LI)

Do While F

i += 1

Do While Arreglo(i) < K And i < LS

i += 1

Loop

j -= 1

Do While Arreglo(j) > K And j > LI

j -= 1

Loop

If i < j Then

'Intercambio

T = Arreglo(i)


Arreglo(j) = T

Else

F = False

End If

Loop

T = Arreglo(LI)

Arreglo(LI) = Arreglo(j)

Arreglo(j) = T

QSort(LI, j - 1)

QSort(j + 1, LS)

End If

End Sub

Arreglo desordenado:

Arreglo ordenado (con Quick Sort):


162

Ordenamiento por acumulación (heap sort).

Este método hace uso de una estructura de datos llamada heap (acumulación) que es muy similar a

un árbol binario pero con algunas diferencias importantes. A diferencia de los árboles binarios esta

estructura es generalmente usa arreglos en lugar de nodos. Existen dos importantes condiciones

para crear una acumulación:

1. Un heap debe estar completo, lo que significa que cada renglón debe estar lleno.

2. Cada nodo contiene datos que son mayores o iguales que los datos en los nodos hijos.

Por ejemplo:

5 7 10 4 3 6 9 2 8 1


163

Heap:

Fig. 5.1.- Acumulación (heap) para el arreglo

Para construir este acumulamiento34:

1. Repetir hasta el paso 7 mientras aún exista un registro que deba ser colocado en el

acumulamiento (heap).

2. Obtener el hijo a colocar en la rama.

3. Obtener la posición del padre de este hijo.

4. Repetir hasta el paso 6 mientras el hijo tenga un padre y el valor clave del hijo se mayor que

su padre.

5. Mover al padre debajo de la posición del hijo.

6. Obtener la posición de un padre nuevo para el hijo.

7. Copiar al hijo en su posición apropiada.

Este es el código:

Private Sub CrearHeap() Dim i, j, Q, K As Integer

For Q = 1 To N '[1]

i = Q '[2]

K = Arreglo(Q)

j = i \ 2 '[3]

Do While i > 0 And K > Arreglo(j) '[4]

Swap(i, j) '[5]

i = j '[6]

j = i \ 2

If j < 0 Then

j = 0

End If

Loop

34 Tremblay.

5

7

10

00

4

3 6

9 2 8

1


164

Arreglo(i) = K '[7]

Next

End Sub

El algoritmo Heap Sort es el siguiente:

1. Crear el acumulamiento inicial (CrearHeap).

2. Repetir hasta el paso 8 un total de N – 1 veces.

3. Intercambiar el primer registro con el último registro no ordenado.

4. Obtener el índice del hijo más grande del nuevo registro.

5. Repetir hasta el paso 8 para los elementos desordenados en al acumulamiento (heap) y

mientras el elemento actual sea mayor que el primer elemento.

6. Intercambiar registro y obtener el hijo izquierdo siguiente.

7. Obtener el índice del siguiente hijo más grande.

8. Copiar el registro en el lugar apropiado.

Private Sub btnHeap_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnHeap.Click

HeapSort()

End Sub

Private Sub HeapSort() Dim i, j, K, Q, T As Integer

CrearHeap()

For Q = N To 1 Step -1

Swap(0, Q)

i = 0

K = Arreglo(i)

j = 1

If (j + 1) < Q Then

If Arreglo(j + 1) > Arreglo(j) Then

j += 1

End If

End If

Do While j <= (Q - 1) And Arreglo(j) > K

Swap(i, j)

i = j

j = 2 * i

If (j + 1) < Q Then

If Arreglo(j + 1) > Arreglo(j) Then

j += 1

End If

ElseIf j > N Then

j = N

End If

Loop

Arreglo(i) = K

Next

VerArreglo()

End Sub



165

Heap Sort:

Arreglo grande:

Ordenado (Heap Sort):

Eficiencia de los diferentes métodos de ordenamiento:

Se agregan los siguientes controles a la forma:

labT1


166

Ejemplo:

Private Sub Burbuja()

'Modificado:

Dim Tiempo As New Stopwatch

Tiempo.Start()


Dim U = N

Dim iCta, iTemp As Integer


iCta = 0

For i As Integer = 0 To U - 1

If Arreglo(i) > Arreglo(i + 1) Then

iTemp = Arreglo(i)

Arreglo(i) = Arreglo(i + 1)

Arreglo(i + 1) = iTemp

iCta += 1

End If

Next

If iCta = 0 Then

bSorted = True

Else

U -= 1

iCta = 0

End If

Loop

Tiempo.Stop()

labT1.Text = Tiempo.Elapsed.Milliseconds

VerArreglo()


VerEnGrid()

End If

End Sub

Así, corriendo los diferentes métodos para arreglos de tamaño 5000 y agregando las instrucciones

mostradas arriba en cada uno:

Burbuja:

Selección:

Quick Sort:

Heap Sort:

Se concluye que el Heap Sort es el más eficiente35.

35 La velocidad de cada método depende de las capacidades del equipo donde se ejecuta.


167

Finalmente, para incrementar la velocidad en la visualización de grandes arreglos, se puede

modificar el procedimiento:

Private Sub VerArreglo(Optional ByVal bCLS As Boolean = True) Dim x, i, L As Integer

L = LSup.ToString.Length

If bCLS Then

txtArreglo.Clear()

ElseIf Not chkTest.Checked Then

txtArreglo.Clear()

End If

txtArreglo.Focus()

PB.Value = 0

PB.Visible = True

Dim sLine As String = ""

For i = 0 To N

x = Arreglo.GetValue(i)

sLine += x.ToString.PadLeft(L) + " "

If (i + 1) Mod C = 0 Then

SendKeys.SendWait(sLine + vbCr)

sLine = ""

End If

PB.Value += 1

Next

SendKeys.SendWait(vbCr)

PB.Visible = False


VerEnGrid()

End If

End Sub

Merge Sort (Mezcla).

Dados dos arreglos A[N] y B[M] ordenados.

1 3 5 7 9

2 4 6 8

El ordenamiento por mezcla produce un tercer arreglo C con tamaño N + M: C[N + M] que contiene

los elementos de A y B ordenados:

1 2 3 4 5 6 7 8 9


168

Deben recorrerse los dos arreglos (A[i], B[j], i 0,1, 2, …,N; j 0,1,2,…, M) e iniciar un

apuntador (k) al primer registro de C.

A[N]

0 1 2 3

1 3 5 7 i ↑

B[M]

0 1 2

2 4 6 8 j ↑

C[N + M]

0 1 2 3 4 5 6

K ↑


Module Module1

Sub Main()



Clear()

Dim A1() As Integer = {1, 3, 5, 7, 9, 11}

Dim A2() As Integer = {2, 4, 6, 8, 10}

Dim M As Integer = A1.GetUpperBound(0) + A2.GetUpperBound(0) + 1

Dim B(M) As Integer

WriteLine("Arreglo 1:")

VerArreglo(A1)

WriteLine("Arreglo 2:")

VerArreglo(A2)

MergeSort(A1, A2, B)

WriteLine("Mezcla:")

VerArreglo(B)

ReadKey()

End Sub

Private Sub MergeSort(ByRef Arr1() As Integer, ByVal Arr2() As Integer, ByVal ArrM() As

Integer)

Dim i, j, k As Integer

Dim N1, N2, M As Integer

N1 = Arr1.GetUpperBound(0)

N2 = Arr2.GetUpperBound(0)

M = ArrM.GetUpperBound(0)

i = 0 : j = 0

k = 0

Do While i <= N1 And j <= N2

If Arr1(i) < Arr2(j) Then

ArrM(k) = Arr1(i)

i += 1

Else

ArrM(k) = Arr2(j)

j += 1

End If

k += 1

Loop

If i <= N1 Then

1. Iniciar índices: (i 0, j 0, k 0

2. Repetir mientras no se alcancen los límites superiores de los arreglos:

Repetir Mientras i < = N Y j <= M

Si A[i] < B[j] entonces

C[k] A[i]

De otro modo

C[k] B[j]

Fin Si

K k +1

3. Si el arreglo A no ha completado su recorrido, pasar los elementos

restantes a C[k].

4. Si, por el contrario, el arreglo B no ha completado su recorrido, pasar

los elementos restantes a C[k].

5. Fin


169

Do While i <= N1 'El Arreglo 1

ArrM(k) = Arr1(i)

i += 1

k += 1

Loop

ElseIf j <= N2 Then 'El resto del arreglo 2

Do While j <= N2

ArrM(k) = Arr2(j)

j += 1

k += 1

Loop

End If

End Sub

Private Sub VerArreglo(ByRef Arr() As Integer)

Dim i As Integer

For i = 0 To Arr.GetUpperBound(0)


Next

WriteLine()

End Sub

End Module

Ordenamiento Externo.

Son algoritmos que se aplican para ordenar datos que están almacenados en la memoria secundaria

del equipo. Puede usarse cualquiera de los métodos vistos aquí ya que un archivo puede

considerarse como un arreglo en la memoria secundaria.

Para mostrar estos procedimientos, se usarán archivos directos que tienen como principal

característica que sus registros pueden leerse o escribirse directamente en cualquier renglón.

Archivo desordenado

N° de Registro Valor

1 10

2 4

3 9

4 3

5 1

Sort Externo


170

Archivo Ordenado

N° de Registro Valor

1 1

2 3

3 4

4 9

5 10

Proyecto:

Objeto Tipo Propiedades Uso

NumN1 NumericUpDown Maximun = 5000, Minimum=10,

Increment =10

Establecer el tamaño

del primer archivo.

NumN2 NumericUpDown Maximun = 5000, Minimum=10,

Increment =10

Establecer el tamaño

del segundo archivo.

lstSerieA ListBox Mostrar datos del

archivo 1

lstSerieB ListBox Mostrar datos del

archivo 2

labN1 Label Text=0 Muestra el n° de datos

del archivo 1

labN2 Label Text=0 Datos en el archivo 2

lamM Label Text=0 Muestra el n° de datos

de la mezcla


171

resultante.

lstMerge ListBox Muestra la mezcla de

archivos.

txtFileA TextBox Para establecer el

nombre del 1er

archivo.

txtFileB TextBox Para establecer el

nombre del 2° archivo.

btnO

K

Button Valida los nombre de

los archivos y prepara

al programa para

generar los datos.

btnCrear

Button Enabled = False Genera los datos de

los dos archivos

aleatoriamente.

btnMerge

Button Enabled = False Mezcla los dos

archivos.

lstFiles ListBox Muestra los archivos

generados.

btnDel Button Elimina el archivo

seleccionado.

btnO

pen

Button Abre el archivo

seleccionado y lo

muestra en una de las

dos listas.

rblstA,

rblstB

RadioButton rblstA.Checked = True Determina la lista en

donde se mostrará un

archivo.

btnCLS Button Limpia las listas.

Public Class frmSortExt

Private Structure Datos

Dim Valor As Integer

End Structure

Private Archivo1, Archivo2, Ruta As String

Private N1, N2, A As Integer

Private Sub frmSortExt_Load(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles MyBase.Load

Ruta = My.Application.Info.DirectoryPath + "\Datos"

If Not My.Computer.FileSystem.DirectoryExists(Ruta) Then

My.Computer.FileSystem.CreateDirectory(Ruta)

End If

Ruta += "\"

ShoFiles()

End Sub

Private Sub ShoFiles()

lstFiles.Items.Clear()

For Each sFile As String In My.Computer.FileSystem.GetFiles(Ruta,

FileIO.SearchOption.SearchTopLevelOnly, "*.dat")

lstFiles.Items.Add(My.Computer.FileSystem.GetName(sFile))

Next

End Sub

Private Sub btnCrear_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnCrear.Click

Generar()

ShoFiles()

End Sub

Private Sub Generar()

Dim LI As Integer = 1

Dim LS As Integer = 100

Dim x, i As Integer


172

'Se crea el primer archivo

Dim D1 As Datos

Dim D2 As Datos

N1 = NumN1.Value

N2 = NumN2.Value

Dim NA As Integer = FreeFile()

FileOpen(NA, Archivo1, OpenMode.Random, , , Len(D1))

For i = 1 To N1

x = CInt(LS - LI + 1) * Rnd() + LI

D1.Valor = x

FilePut(NA, D1.Valor)

Next

FileClose(NA)

'Segundo archivo

FileOpen(NA, Archivo2, OpenMode.Random, , , Len(D2))

For i = 1 To N2

x = CInt(LS - LI + 1) * Rnd() + LI

D2.Valor = x

FilePut(NA, D2.Valor)

Next

FileClose(NA)

Ordenar()

End Sub

Private Sub Ordenar()

SortE(Archivo1)

SortE(Archivo2)

VerDatos(Archivo1, lstSerieA)

VerDatos(Archivo2, lstSerieB)

labN1.Text = lstSerieA.Items.Count

labN2.Text = lstSerieB.Items.Count

btnMergeSort.Enabled = True

End Sub

Private Sub SortE(ByVal sFile As String)

'Burbuja:

Dim R As Integer


Dim RTemp, D As New Datos

Dim DA As New Datos

Dim DB As New Datos


FileOpen(NA, sFile, OpenMode.Random, , , Len(D))

Dim N As Integer = LOF(NA) / Len(D) 'N° de registros

Dim U As Integer = N, iCta As Integer = 0


For R = 1 To U - 1

FileGet(NA, DA, R)

FileGet(NA, DB, R + 1)

If DA.Valor > DB.Valor Then

FilePut(NA, DB, R)

FilePut(NA, DA, R + 1)

iCta += 1

End If

Next

If iCta = 0 Then

bSorted = True

Else

iCta = 0

U -= 1

End If

Loop

FileClose()

End Sub

Private Sub VerDatos(ByVal sFile As String, ByRef Lista As ListBox)

Dim D As New Datos


FileOpen(NA, sFile, OpenMode.Random, , , Len(D))

Dim N As Integer = LOF(NA) / Len(D) 'N° de registros

Dim R As Integer

Lista.Items.Clear()

For R = 1 To N

FileGet(NA, D, R)


173

Lista.Items.Add(D.Valor)

Next

FileClose(NA)

End Sub


Handles btnOK.Click

Archivo1 = Ruta + txtFileA.Text.Trim

Archivo2 = Ruta + txtFileB.Text.Trim

If Archivo1.Length > 0 Then

ValidarExt(Archivo1)

If My.Computer.FileSystem.FileExists(Archivo1) Then

If Not Borrar(Archivo1) Then

Exit Sub

End If

End If

Else

MsgBox("Falta nombre de archivo 1")

Exit Sub

End If

If Archivo2.Length > 0 Then

ValidarExt(Archivo2)

If My.Computer.FileSystem.FileExists(Archivo2) Then

If Not Borrar(Archivo2) Then

Exit Sub

End If

End If

Else

MsgBox("Falta nombre de archivo 2")

Exit Sub

End If

btnCrear.Enabled = True

End Sub

Private Function Borrar(ByVal sFile As String) As Boolean

A = MsgBox(My.Computer.FileSystem.GetName(sFile) + " ya existe" + vbCr _

+ "¿Lo elimna", MsgBoxStyle.YesNo)

If A = vbYes Then


lstFiles.Items.Remove(My.Computer.FileSystem.GetName(sFile))

Return True

Else

Return False

End If

End Function

Private Sub ValidarExt(ByRef sFile As String)

Dim x As Integer = InStrRev(sFile, ".")

If x = 0 Then

sFile += ".dat"

ElseIf Mid(sFile, x + 1, 3) <> "dat" Then

Mid(sFile, x + 1, 3) = "dat"

End If

End Sub

Private Sub btnDel_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnDel.Click

If Not lstFiles.SelectedItem Is Nothing Then

A = MsgBox("Elimina archivo", MsgBoxStyle.YesNo)

If A = vbYes Then

Dim sFile As String = Ruta + lstFiles.SelectedItem


lstFiles.Items.Remove(lstFiles.SelectedItem)

End If

End If

End Sub



If Not lstFiles.SelectedItem Is Nothing Then

If rbLstA.Checked Then

Archivo1 = Ruta + lstFiles.SelectedItem

VerDatos(Archivo1, lstSerieA)


174


labFileA.Text = My.Computer.FileSystem.GetName(Archivo1)

Else

Archivo2 = Ruta + lstFiles.SelectedItem

VerDatos(Archivo2, lstSerieB)


labFileB.Text = My.Computer.FileSystem.GetName(Archivo2)

End If

labN1.Text = lstSerieA.Items.Count

labN2.Text = lstSerieB.Items.Count

End If

End Sub

Private Sub btnMergeSort_Click(ByVal sender As System.Object, ByVal e As

System.EventArgs) Handles btnMergeSort.Click

MergeSort()

End Sub

Private Sub MergeSort()

Dim NR1, NR2, NA1, NA2, NAM, i, j, k As Integer

Dim D1, D2, MS As Datos

Dim sFileMerge As String

sFileMerge = InputBox("Nombre de la mezcla", "Nuevo archivo", "Merge1")

If sFileMerge <> "" Then

sFileMerge = Ruta + sFileMerge

ValidarExt(sFileMerge)

If My.Computer.FileSystem.FileExists(sFileMerge) Then

My.Computer.FileSystem.DeleteFile(sFileMerge)

End If

NA1 = FreeFile()

FileOpen(NA1, Archivo1, OpenMode.Random, , , Len(D1))

NR1 = LOF(NA1) / Len(D1)

NA2 = FreeFile()

FileOpen(NA2, Archivo2, OpenMode.Random, , , Len(D2))

NR2 = LOF(NA2) / Len(D2)

NAM = FreeFile()

FileOpen(NAM, sFileMerge, OpenMode.Random, , , Len(MS))

i = 1 : j = 1 : k = 1

Do While i <= NR1 And j <= NR2

FileGet(NA1, D1, i)

FileGet(NA2, D2, j)

If D1.Valor < D2.Valor Then

FilePut(NAM, D1, k)

i += 1

Else

FilePut(NAM, D2, k)

j += 1

End If

k += 1

Loop

If i <= NR1 Then

Do While i <= NR1

FileGet(NA1, D1, i)

FilePut(NAM, D1, k)

i += 1

k += 1

Loop

ElseIf j <= NR2 Then

Do While j <= NR2

FileGet(NA2, D2, j)

FilePut(NAM, D2, k)

j += 1

k += 1

Loop

End If

FileClose()

ShoFiles()

VerDatos(sFileMerge, lstMerge)

labM.Text = lstMerge.Items.Count

End If

End Sub


175



lstSerieA.Items.Clear()

lstSerieB.Items.Clear()

lstMerge.Items.Clear()

btnMergeSort.Enabled = False

End Sub

End Class

La aplicación funciona de la siguiente manera:

1. Escribir los nombres del par de archivos a generar.

2. Seleccionar

3. Generar los datos aleatoriamente

4. Mezclar archivos. (se pide el nombre del archivo resultante, si existe elimina el

previo).

5. Cuando se abre un archivo, previamente debe seleccionarse la lista donde será desplegado.


176

Ejercicio:

Modifique el método de ordenamiento usado en esta aplicación y cámbielo por:

QuickSort ó

HeapSort


177

6 Métodos de Búsqueda.

Competencia especifica.- Aplicar el método de búsqueda pertinente en la solución de un problema

real.

Competencia específica: Aplicar el método de búsqueda pertinente en la solución de un problema

real.

Introducción.- La búsqueda y recuperación de datos es una tarea fundamental en programación y es

una de las que más ha sido estudiada.

Existen básicamente dos formas de buscar datos en una lista (o arreglo); la búsqueda secuencial y la

búsqueda binaria. La primera se usa cuando los datos no están ordenados, la segunda es usada

cuando los datos están ordenados.

Búsqueda Secuencial.

Este método es bastante fácil de implementar ya que consiste en recorrer el arreglo hasta encontrar

el elemento que se busca:

Para ejemplificar lo anterior, se utilizará la misma aplicación de la Unidad V (Ordenamiento),

agregando los siguientes controles en la parte inferior

de la forma:

Objeto Tipo Propiedades

txtLoc TextBox

btnBSec Button

btnBBins Button Enabled = False

labTB Label BordeStyle = Fixed3D, TextAlignment = MiddleCenter, Text=0

Private Sub btnBSec_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnBSec.Click

If IsNumeric(txtLoc.Text) Then

Dim L As Integer = LSup.ToString.Length

Dim y As Integer = txtLoc.Text

Dim i As Integer, bFound As Boolean = False

Dim k, x, z As Integer


Tiempo.Start()


If Arreglo(i) = y Then

bFound = True


178

Exit For

End If

Next

Tiempo.Stop()

labTB.Text = Tiempo.Elapsed.Milliseconds

If bFound Then

MsgBox("Elemento encontrado en posición " + i.ToString)

'Para marcarlo en el TextBox:

Marcarlo(i, L, y)

Else

MsgBox(y.ToString + " no existe en el arreglo", MsgBoxStyle.Information)

End If

Else

MsgBox("Debe ingresar un valor numérico", MsgBoxStyle.Information)

txtLoc.Focus()

End If

End Sub

Private Sub Marcarlo(ByVal P As Integer, ByVal L As Integer, ByVal x As Integer)

Dim z, k As Integer

Dim d1, d2 As String

d1 = x.ToString.PadLeft(L)

z = InStr(txtArreglo.Text, d1)

d2 = txtArreglo.Text.Substring(z - 1, L + 1)

If d1.Trim <> d2.Trim Then

Do

'z = InStr(z, txtArreglo.Text, " ")

z = InStr(z + 1, txtArreglo.Text, d1)

d2 = txtArreglo.Text.Substring(z - 1, L + 1)

Loop Until d1.Trim = d2.Trim

End If

txtArreglo.Focus()

txtArreglo.SelectionStart = z - 1

txtArreglo.SelectionLength = x.ToString.PadLeft(L).Length

End Sub


Buscar x = 3:

Búsqueda Binaria.

Se aplica únicamente sobre arreglos ordenados. La idea es seguir un procedimiento similar a buscar

un teléfono específico en un directorio telefónico. Así si se desea buscar el teléfono de Pérez Alcocer

Alicia no se busca página por página sino que se van abriendo páginas de la A-Z, luego se parte a la

mitad esa sección, resultando por ejemplo M – Z, descartando la primera mitad y se repite el

proceso, por ejemplo M – R hasta llegar a la “P”. Luego en esos apellidos no leemos


179

secuencialmente, sino que se va dividiendo la lista hasta tener a la vista los apellidos “Pé” y localizar

(si existe) el teléfono deseado.

Así, se lleva este procedimiento a un arreglo A[N] (ordenado), deben establecerse los límites de la

búsqueda que al principio son 0 y N:

0 1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9 10

↑ ↑ ↑

A estos límites los representamos por las variables iMin e Max.

iMin 0: iMax 9 (N)

Luego se divide el arreglo en dos mitades, esta posición se representa por iMit:

Donde iMit TRUNC (iMin + iMax) / 2

Luego: iMit (0+9)/2 = 4 (valor truncado) ↑

Si x representa el valor a buscar, entonces se prueba la mitad en que debería estar si existiera:

Si x < A[iMit] entonces (debería encontrarse en la primera mitad).

Descartar la segunda mitad: iMin iMit + 1

De otro modo, Si x > A[iMit] entonces (debería encontrarse en la segunda mitad).

Descartar la primera mitad: iMax iMit – 1

De otro modo ( x = A[iMit]), el dato ha sido localizado.

Fin Si

Y este proceso deberá repetirse mientras el dato no sea localizado e iMin <= iMax.

Así, para activar la búsqueda binaria, agregar la siguiente línea a todos los métodos de ordenación:

Private Sub btnHeap_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnHeap.Click

HeapSort()

btnBBin.Enabled = True

End Sub

Private Sub btnBBin_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnBBin.Click

Dim x As Integer = txtLoc.Text

BinarySearch(x)

End Sub


180

Private Sub BinarySearch(ByVal x As Integer)

Dim L As Integer = LSup.ToString.Length

Dim iMin, iMax, iMit As Integer

Dim bFound As Boolean = False

iMin = 0 : iMax = N


Tiempo.Start()

Do While Not bFound And iMin <= iMax

iMit = (iMin + iMax) \ 2

If x < Arreglo(iMit) Then

iMax = iMit - 1

ElseIf x > Arreglo(iMit) Then

iMin = iMit + 1

Else

bFound = True

End If

Loop

Tiempo.Stop()

labTB.Text = Tiempo.ElapsedMilliseconds

If bFound Then

Dim i As Integer = Array.IndexOf(Arreglo, x)

MsgBox("Elemento en posición " + i.ToString)

Marcarlo(i, L, x)

Else

MsgBox("No se encontró " + x.ToString)

End If

End Sub

Arreglo ordenado:

Búsqueda por Funciones Hash.

Introducción36.

El hash es una técnica para almacenar y recuperar datos rápidamente. Esta utiliza una estructura de

datos llamada tabla hash. Aún y cuando estas tablas proporcionan métodos de inserción, remoción y

36 McMillan.


181

recuperación resulta pobre para operaciones que involucran la búsqueda de datos mínimo ó máximo

(por ejemplo).

Las librerías del marco .NET proporciona una clase muy poderosa para trabajar con tablas hash.

Tabla Hash.- Es una estructura desarrolla alrededor de un arreglo que consiste de varios elementos

(0 a N) y debe poder cambiar su tamaño tanto como sea necesario. Cada dato almacenado en el

arreglo se basa en una parte del dato denominado clave. Para almacenar algún elemento en la tabla

hash, la clave es mapeada sobre alguna posición en el rango 0 a N por medio de una función

denominada función hash.

Idealmente una función hash almacena cada clave en su propia celda en el arreglo. Sin embargo,

dado que existe un número ilimitado de claves posibles y un número finito de celdas en el arreglo,

una meta más realista de esta función ese el intentar en lo posible distribuir uniformemente las

claves en las celdas de un arreglo.

Además, con todo y se tenga una buena función hash es probable que dos claves tengan el mismo

valor hash. A esto se le llama colisión y debe tenerse una estrategia para manejarla cuando ocurra.

Por último, debe determinarse que tan grande debe ser el tamaño del arreglo usado como tabla

hash. Es recomendable que este tamaño sea un número primo.

Elección de una Función Hash.

La elección de una función hash se basa en el tipo de dato de la clave que será usada. Si se trabaja

con números enteros la función más simple debe retornar un valor como x mod N donde x es la

clave a insertar. Existen circunstancias, sin embargo, donde este método no es recomendable, por

ejemplo cuando todas las claves terminan en 0 y el tamaño del arreglo es 10. Esta es una de las

razones por las que N debería ser un número primo. Por otro lado, si las claves son números enteros

aleatorios, la función hash debería distribuir más eficientemente las claves.

En muchas aplicaciones, las claves son de tipo cadena (string), en cuyo caso resulta más difícil elegir

una función hash que opere sobre estas claves y debe elegirse cuidadosamente. Una función simple

que parece trabajar bien, consiste en sumar los valores ASCII de las letras en la clave y el valor

retornado por la misma es el módulo aritmético de esa suma y el valor de N:

Private Function HashSimple(ByVal s As String, ByVal Arr() As String) As Integer

Dim T, i As Integer

For i = 0 To s.Length - 1

T += Asc(s.Chars(i))

Next

Return T Mod Arr.GetUpperBound(0)

End Function


182

Y su uso sería:

Option Strict On


Module Module1

Sub Main()



Clear()

Dim Nombres(9) As String, Nombre As String

Dim VariosNombres() As String = {"Ricardo", "Ana", "Alicia", "Susana", "Sandra",

"Carolina", "Karen", "Carla", "Yolanda", "Margarita"}

Dim HashVal, i As Integer

For i = 0 To 9

Nombre = VariosNombres(i)

HashVal = HashSimple(Nombre, Nombres)

Nombres(HashVal) = Nombre

Next

VerDist(Nombres)

WriteLine()

Write("Buscar: ")

Nombre = ReadLine()

If HashSearch(Nombre, Nombres) Then

WriteLine("Dato encontrado")

Else

WriteLine("Dato no encontrado")

End If

ReadKey()

End Sub

Private Function HashSimple(ByVal s As String, ByVal Arr() As String) As Integer

Dim T, i As Integer


T += Asc(s.Chars(i))

Next

Return T Mod Arr.GetUpperBound(0)

End Function

Private Sub VerDist(ByVal Arr() As String)

Dim i As Integer

For i = 0 To Arr.GetUpperBound(0)

If Arr(i) <> "" Then

WriteLine(i & " " & Arr(i))

End If

Next

End Sub

Para localizar una clave, sólo se invoca a la función hash y se compara el valor de esa celda con el

dato a buscar:

Private Function HashSearch(ByVal s As String, ByVal Arr() As String) As Boolean

Dim H As Integer

H = HashSimple(s, Arr)

If Arr(H) = s Then

Return True

Else

Return False

End If

End Function


183

El primer problema que se observa es que no se despliegan todos los

datos. Lo interesante es que si se cambia N a un número primo < 99

todos los nombre son almacenados adecuadamente.


El tamaño que finalmente sea elegido depende del número de registros que se van almacenar en la

tabla hash, un número seguro parece ser 10, 007 que es primo y los requerimientos de memoria no

son lo suficientemente grandes como para afectar el rendimiento del programa:


Con la misma idea de usar el cómputo de los valores ASCII de la clave, el siguiente algoritmo

proporciona un mejor hash:

Private Function Hash2(ByVal s As String, ByVal Arr() As String) As Integer

Dim i As Integer, T As Long


T += 37 * T + Asc(s.Chars(i))

Next

T = T Mod Arr.GetUpperBound(0)

If T < 0 Then


184

T += Arr.GetUpperBound(0)

End If

Return CInt(T)

End Function

Esta función utiliza la regla de Horner37 para calcular la función polinomial de 37.

Líneas que se modifica:

HashVal = Hash2(Nombre, Nombres)

H = Hash2(s, Arr)

Y se observa una mejor distribución de las claves.

Cuando se almacenan más datos la probabilidad de que ocurran colisiones es alta, para resolver este

problema se pueden usar cubos (buckets). Un cubo es una estructura de datos simple almacenada

en un elemento de una tabla hash que puede almacenar ítems múltiples. En la mayoría de las

implementaciones esta estructura es a su vez un arreglo pero es mejor usar un arreglo lista

(ArrayList), así se evita el problema de requerir más memoria en caso de ser necesario.

Para insertar un ítem, primero se usa la función para determinar en qué ubicación del arreglo lista

ha de almacenarse, luego se verifica si esa ubicación ya está ocupada. Si lo está no se hace nada, si

no se invoca al método Add del arreglo lista.

Para remover un ítem, de nuevo se obtiene su valor hash y se revisa el arreglo lista para asegurarse

que ese ítem existe y liego se elimina.

37 http://www.physics.utah.edu/~detar/lessons/c++/array/node4.html

http://www.physics.utah.edu/~detar/lessons/c++/array/node4.html


185

Public Class CBucketHash

Private Const Tam As Integer = 101

Private Dato() As ArrayList

Public Sub New()

Dim i As Integer

ReDim Dato(Tam)

For i = 0 To Tam - 1

Dato(i) = New ArrayList(4)

Next

End Sub

Private Function Hash(ByVal s As String) As Integer

Dim i As Integer, Tot As Long


Tot += 37 * Tot + Asc(s.Chars(i))

Next

Tot = Tot Mod Dato.GetUpperBound(0)

If Tot < 0 Then

Tot += Dato.GetUpperBound(0)

End If

Return CInt(Tot)

End Function

Public Sub Insertar(ByVal Item As String)

Dim H As Integer

H = Hash(Item)

If Not Dato(H).Contains(Item) Then

Dato(H).Add(Item)

End If

End Sub

Public Sub Remover(ByVal Item As String)

Dim H As Integer

H = Hash(Item)

If Dato(H).Contains(Item) Then

Dato(H).Remove(Item)

End If

End Sub

Public Sub VerDist(ByVal Arr() As String)

Dim i, H As Integer, s As String

For i = 0 To Tam - 1

If Dato(i).Count > 0 Then

For j As Integer = 1 To Dato(i).Count

s = Dato(i).Item(j - 1)

Console.WriteLine(i & " " & j & " " & s)

Next

End If

Next

End Sub

End Class

Option Strict On


Module Module1

Private MiHash As New CBucketHash

Sub Main()



Clear()


Dim VariosNombres() As String = {"Ricardo", "Ana", "Teresa", "Susana", "Sandra",

"Carolina", "Martha", "Julian", "Yolanda", "Margarita"}

Dim i As Integer

For i = 0 To VariosNombres.GetUpperBound(0)

Nombre = VariosNombres(i)

MiHash.Insertar(Nombre)

Next

MiHash.VerDist(VariosNombres)

ReadKey()

End Sub

End Module

Cuando se usan cubos, el

número de elementos usados

en el arreglo lista debe

mantenerse tan bajo como sea

posible ya que esto minimiza

el trabajo extra que se tiene

que hacer cuando se agregan o

eliminan ítems de la tabla

hash. En este código, se

minimiza el tamaño del arreglo

lista estableciendo el valor

inicial a 1 en el constructor.

Luego, una vez que se tienen

colisiones la capacidad del

arreglo lista se hace 2 y así

continúa duplicándose cada

vez.

El radio del número de

elementos en la tabla hash se

denomina factor de carga.

Diferentes estudios han

demostrado que un mejor

rendimiento en una tabla hash

se logra cuando el factor de

carga es 1.0 ó cuando el

tamaño de la tabla es

exactamente igual al número

de elementos.


186

La Clase HashTable (.NET).

La clase HashTable es un tipo especial del objeto Dictionary que almacena pares de valores de

claves. Dado que esta clase es bastante eficiente, debería ser usada en aplicaciones que requieran

tablas hash.

Cómo instanciar y agregar datos a un objeto HashTable:

Private MiHash As New CBucketHash

Private MiHash As New CBucketHash(71)

Private MiHash As New CBucketHash(23, 3.0)

La primera línea crea una tabla hash con su capacidad y factor de carga por defecto. La segunda

línea crea una tabla hash con capacidad para 71 elementos y un factor de carga por defecto. Y la

tercera línea crea una tabla hash con una capacidad inicial de 23 elementos y un factor de carga de

3.0.

Uso:

Option Strict On

Imports System.Collections


Module Module1

Sub Main()



Clear()

Dim Claves() As String = {"Nombre1", "Edad1", "Carrera1"}

Dim AA As New ArrayList

Dim Alumnos As New Hashtable(17)

Alumnos.Add("01Nombre", "Olga Zuñiga")

Alumnos.Add("02Edad", 19)

Alumnos.Add("03Carrera", "ISC")

Alumnos.Add("04Género", "F")

Alumnos.Add("05Nombre", "Sandra Alvarez")

Colisiones.

Se enumeran consecutivamente los datos

para que la salida corresponda a cada

alumno.


187


Alumnos.Add("07Carrera", "INF")

Alumnos.Add("08Género", "F")

Alumnos.Add("09Nombre", "Pedro Garza")


Alumnos.Add("11Carrera", "ISC")

Alumnos.Add("12Género", "M")

For Each de As DictionaryEntry In Alumnos

AA.Add(de.Key)

Console.WriteLine("Key = {0}, Value = {1}", _

de.Key, de.Value)

Next de

AA.Sort()

WriteLine()

For Each K As String In AA

WriteLine(K & " " & Alumnos.Item(K).ToString)

Next

ReadKey()

End Sub

End Module

Aplicación: Crear un glosario de palabras reservadas de VB.NET (utilizando la ayuda).

Esta aplicación comienza creando un archivo de texto (usando el bloc de notas y guardando las

definiciones en formato UTF-8.


188

No debe haber espacios en blanco al final del archivo y éste debe guardarse en una ubicación fácil

de encontrar. En la aplicación de muestra se guardo en la misma ubicación del ejecutable.

Para esto debe crearse un proyecto nuevo:

Una vez que se cambie el nombre a la forma por defecto, debe guardarse

el proyecto en una ubicación conocida.

Option Strict On

Imports System.IO

Imports System.Collections

Public Class frmGlosario

Inherits System.Windows.Forms.Form

Private Glosario As New Hashtable

ListBox. Sorted = True. Font

Consolas 9

txtDef (TextBox). MultiLine = True,

ScrollBars = Verticarl, Font =

Consolas, 9


189

Private Sub frmGlosario_Load(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles MyBase.Load

CrearGlosario()

VerPalabras()

End Sub

Private Sub CrearGlosario()

Dim Archivo As StreamReader

Dim sLine As String

Dim Palabras() As String

Archivo = File.OpenText(My.Application.Info.DirectoryPath & "\glosario.txt")

Do While Archivo.Peek <> -1

sLine = Archivo.ReadLine

Palabras = sLine.Split(","c)

Glosario.Add(Palabras(0), Palabras(1))

Loop

Archivo.Close()

End Sub

Private Sub VerPalabras()

For Each K As Object In Glosario.Keys

lstTerminos.Items.Add(K)

Next

If lstTerminos.Items.Count > 0 Then

lstTerminos.SelectedIndex = 0

End If

End Sub

'Procedimiento de evento

Private Sub lstTerminos_SelectedIndexChanged(ByVal sender As Object, ByVal e As

System.EventArgs) Handles lstTerminos.SelectedIndexChanged

Dim Termino As Object = lstTerminos.SelectedItem

txtDef.Text = CStr(Glosario.Item(Termino))

End Sub

End Class

Ejecución:

Ejercicios:


190

1. Re escribir este programa pero usando la clase CBucketHash desarrollada antes en esta unidad.

2. Usando la clase HashTable escribir un programa que verifique la ortografía de algunas palabras,

que las lea desde un archivo de texto y verifique errores ortográficos. El límite del diccionario

debe ser sólo de algunas palabras comunes. La ortografía es para palabras en español.


191

7 Análisis de los Algoritmos.

Competencia Específica: Comprender la complejidad de los algoritmos e identificar la eficiencia de

los mismos.

Introducción.

Se sabe que un algoritmo es una secuencia de instrucciones que tiene como objetivo resolver un

problema y que puede haber diferentes algoritmos que lo pueden resolver. Saber cuál de estos

algoritmos es mejor requiere poder en cierto modo cuantificar su eficiencia de manera que se pueda

“calificar” su eficiencia. Eso es la complejidad.

Al tiempo que consume un algoritmo para resolver un problema se le denomina complejidad

temporal y a la cantidad de memoria que requiere el algoritmo se le denomina complejidad espacial.

Un concepto que se usa en este tipo de análisis se conoce como el tamaño del problema. Todo

problema requiere datos de entrada pare resolverlo, así por ejemplo cuando ordenamos arreglos38

los diferente algoritmos que se usan pueden requerir un tiempo más o menos igual para arreglos

pequeños, por ejemplo N = 100. Sin embargo cuando se ordenan arreglos grandes las diferencias

de tiempo son evidentes.

Por ejemplo, para un arreglo de tamaño 5000, se tienen los tiempos siguientes para ordenarlo

(tomados del programa desarrollado en la Unidad V):

Modo Tiempo (ms)

Selección 246

Burbuja 318

QuickSort 100

HeapSort 6

El tamaño del arreglo, incide directamente en el tiempo de ejecución.

Se puede concluir que HeapSort es el más eficiente en cuanto a lo temporal.

Algunos lenguajes (como .NET) contienen librerías sumamente eficientes para resolver una serie de

problemas, cual simplifica enormemente la tarea de desarrollar grandes aplicaciones. Así por

ejemplo, agregando lo siguiente a esa aplicación:

Private Sub btnSortNet_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)

Handles btnSortNet.Click


Tiempo.Start()

38 Unidad V.


192

Array.Sort(Arreglo)

Tiempo.Stop()

VerArreglo()

labTB.Text = Tiempo.ElapsedMilliseconds

End Sub

End Class

El cual tarda 0 ms en ejecutarse. Claramente una situación real es el mejor.

La complejidad, por otro lado, no es un número es una función y sus valores dependen de en qué

equipo se ejecuta así los valores obtenidos difieren de acuerdo al equipo.

Cada problema tiene uno varios valores que determinan su tamaño y se calcula de un tamaño

genérico y no concreto, así por ejemplo la complejidad de los algoritmos de ordenación se calcula

en base a un arreglo de tamaño N y no de 5, 10 ó 5000.

Un problema generalmente usado para ejemplificar la complejidad de un algoritmo consiste en

encontrar el n-ésimo término de una sucesión de Fibonacci.

1 ½ 1/3 1/5 1/8 …

0 1 2 3 4 n

La complejidad en el tiempo depende de cómo se resuelva este problema (por ejemplo una función

iterativa ó una recursiva).


Module Module1

Module Module1

Sub Main()



Clear()

Dim T As New Stopwatch

Dim N As Integer = 37

T.Start()

WriteLine("Iterativa_")

Dim FBNI As Long = FiboIter(N)

WriteLine(T.ElapsedMilliseconds)

T.Stop()

WriteLine(FBNI)

WriteLine()

WriteLine("Recursiva")

T.Start()

Dim FBR As Long = FiboRec(N)

T.Stop()

WriteLine(FBR)

WriteLine(T.ElapsedMilliseconds)


193

ReadKey()

End Sub

Private Function FiboIter(ByVal N As Integer) As Long

Dim i As Integer

Dim Valores(N) As Integer

If N = 1 Or N = 2 Then

Return 1

Else

Valores(1) = 1

Valores(2) = 2

For i = 3 To N - 1

Valores(i) = Valores(i - 1) + Valores(i - 2)

Next

Return Valores(N - 1)

End If

End Function

Private Function FiboRec(ByVal N As Integer) As Long

If N < 2 Then

Return N

Else

Return FiboRec(N - 1) + FiboRec(N - 2)

End If

End Function

End Module

El tiempo requerido para completar cada tarea depende del valor N (en este caso

37) que se va a calcular (además de la potencia del equipo donde se ejecuta).

Otra medida de la complejidad son el número de instrucciones necesarias que un algoritmo necesita

para completar su tarea:

Claramente, el sort por selección es menos complejo

en el espacio, y además debe considerarse que en el

HeapSort se invoca al procedimiento CrearHeap.


194

Esta complejidad se mide por el número de líneas que se ha requerido para resolver el problema.

Además se considera el número de ciclos e instrucciones If-Then-Else involucradas. PSP (Personal

Software Process) es una herramienta que proporciona varias métricas para medir la complejidad de

un programa39.

Otro caso que puede ejemplificar el concepto de complejidad es el programa de sort externo, que

agregándole algunas pocas líneas nos puede mostrar que el tiempo requerido está en función del

tamaño de los archivos:

Se observa que entre más grandes

sean los tamaños de los archivos, el

proceso de sort externo tarda más.

Una solución a este problema sería

implementar un sort más rápido

(como el heap sort). Aunque el

número de líneas será mayor.

Por otro lado, la recuperación de

los datos iniciales desde un archivo

existente, es más rápida que los

procesos anteriores porque los

datos ya están ordenados.

39 Ingeniería de Software.


195

Aunque se tarda más en mostrar los datos desde el archivo, se ahorra el tiempo

del sort (que ya no se realiza).

Y cuando se abre la mezcla desde un archivo40 el tiempo es mucho menor que el

obtenido por el proceso (porque ya no se efectúa).

Ciertos autores señalan que la complejidad de algoritmos es muy útil en el nivel teórico pero que no

es conveniente obsesionarse demasiado en un nivel práctico.

Para cada algoritmo existe un par de medidas generales:

El peor de los casos que se denota con la notación о (O micrón –Big-O).

El mejor de los casos denotado por Ω (omega)

En general es imprescindible conocer el peor de los casos ya que proporciona una visión de lo que

puede pasar cuando las cosas van realmente mal.

Ejemplo:

Para una cierta cantidad de datos n, la desviación estándar de estos puede medirse por:

Pero también se puede encontrar por:

Con la primera ecuación:

40 Debe modificarse el programa (unas pocas líneas) para medir este tiempo.


196

Con la segunda:

A medida que se incrementa N

(1)

(2)

Este es el código:


197

Public Class frmStat

Dim N As Integer, Datos() As Integer

Dim sMedia As Single, sDS As Single


Handles btnOK.Click

N = NumN.Value - 1

GeneraDatos()

End Sub

Private Sub GeneraDatos()


Tiempo.Start()

ReDim Datos(N)



Dim x, i As Integer

For i = 0 To N

x = CInt(Int(LS - LI + 1) * Rnd() + LS)

Datos(i) = x

lstDatos.Items.Add(x)

Next

sMedia = Media()

'sDS = sDesv()

sDS = sDev2()

Tiempo.Stop()

labMedia.Text = sMedia.ToString("n2")

labdDev.Text = sDesv.ToString("n4")

labT.Text = Tiempo.ElapsedMilliseconds

End Sub

Private Function Media() As Single

Dim SX As Integer = 0


SX += Datos(i)

Next

Return SX / N

End Function

Private Function sDesv() As Single

Dim SX2 As Integer = 0, i As Integer

For i = 0 To N

SX2 += (Datos(i) - sMedia) ^ 2

Next

Return Math.Sqrt(SX2) / N - 1

End Function

Private Function sDev2() As Single

Dim SX2 As Long = 0, s2 As Single

Dim i As Integer

For i = 0 To N

SX2 += Datos(i) ^ 2

Next

s2 = (SX2 - N * sMedia ^ 2) / (N - 1)

Return Math.Sqrt(s2)

End Function

End Class

Este proceso puede mejorarse si, por ejemplo se calcula ∑x2 al momento de ingresar los datos:


198

Estos son los cambios:

Private Sub GeneraDatos()

Dim SX2 As Long = 0


Tiempo.Start()

ReDim Datos(N)



Dim x, i As Integer

For i = 0 To N

x = CInt(Int(LS - LI + 1) * Rnd() + LS)

Datos(i) = x

SX2 += x ^ 2

lstDatos.Items.Add(x)

Next

sMedia = Media()

'sDS = sDesv()

sDS = sDev2(SX2)

Tiempo.Stop()

labMedia.Text = sMedia.ToString("n2")

labdDev.Text = sDesv.ToString("n4")

labT.Text = Tiempo.ElapsedMilliseconds

End Sub

Private Function sDev2(ByRef SX2 As Long) As Single

Dim s2 As Single

s2 = (SX2 - N * sMedia ^ 2) / (N - 1)

Return Math.Sqrt(s2)

End Function

Así, el primer intento con la ecuación 1 repesentaría el peor de los casos, y la última modificación

será el mejor de los casos.

Ejercicio: Para el problema de encontrar una ecuación de ajuste con regresión lineal múltiple41, se

tiene el siguiente método42:

Ecuación general de ajuste:

Para J variables independientes (X1, X2, …, Xj), la varia dependiente Y. Para la ecuación anterior utilizando a como

una estimación de ∂ y bj como una estimación de βj , las ecuaciones normales son:

………..

41 Unidad I.

42 Richard L. Mils. Estadística para economía y administración. McGraw Hill

La función que calcula la

desviación estándar se

reduce, además,

considerablemente.


199

Si se usa álgebra de matrices. Estas ecuaciones pueden describirse como:

n ∑X1 ∑X2 . . . ∑Xj

∑X1 ∑X12 ∑X1X2 . . . ∑X1Xj

A= ∑X2 ∑X1X2 ∑X22 . . . ∑X2Xj

. . . . . . . . . . . . . . .

∑Xj ∑X1Xj ∑X1Xj . . . ∑Xj2

a ∑Y

b1 ∑YX1

Z = b2 Y d = ∑YX2

.

.

.

.

.

.

bj ∑YXj

Entonces pueden resolverse las ecuaciones por:

. . . (1)

Para simplificar este caso, considérese el caso de tres variables:

Y = Consumo anual de carne

X1 = Un índice del precio al por menor de carne

X2 = Índice del precio al por menor de la carne de cerdo.

Estos son los datos históricos de los últimos 5 años (x10)- hipotéticos

Consumo

de carne

Precio de

la carne

Precio del

cerdo.

Y X1 X2

6 1 1

5 1 2

4 2 1

3 2 2

7 4 9

Cálculos preliminares:


200

Y X1 X2 YX1 YX2 Y2 X1

2 X2

2 X1X2

6 1 1 6 6 36 1 1 1

5 1 2 5 10 25 1 4 2

4 2 1 8 4 16 4 1 2

3 2 2 6 6 9 4 4 4

7 4 9 28 63 49 16 81 36

25 10 15 53 89 135 26 91 45

Las matrices resultantes son:

5 10 15

25

A= 10 26 45

d = 53

15 45 91

89

El resultado es (de la ecuación 1):

Escribir un programa que lea los valores de muestra (Y, X1, X2) y obtenga los valores de Z siguiendo esta

metodología y luego compárelo con el mostrado en la página 58. ¿Cuál algoritmo es más eficiente?

estructuras de datos con vb.net

Documents