using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Intercalacion_Simple
{
public int[] A;
public int[] B;
int[] C;
int[] TempA;
int[] TempB;
int N = 10;
int M = 10;
int i, j, x, w;
int I, J, K, X;
public Intercalacion_Simple()
{
A = new int[N];
B = new int[M];
C = new int[A.Length+B.Length];
TempA = new int[A.Length];
TempB = new int[B.Length];
}
public void Generar()
{
Random Aleatorio = new Random();
for (int i = 0; i < N; i++)
{
A[i] = Aleatorio.Next(10, 99);
TempA[i] = A[i];
}
for (int i = 0; i < M; i++)
{
B[i] = Aleatorio.Next(10, 99);
TempB[i] = B[i];
}
}
public void quicksortA(int L, int R)
{
i = L;
j = R;
x = A[(L + R) / 2];
do
{
while (A[i] < x)
i = i + 1;
while (x < A[j])
j = j - 1;
if (i <= j)
{
w = A[i];
A[i] = A[j];
A[j] = w;
i = i + 1;
j = j - 1;
}
} while (i < j);
if (L < j)
quicksortA(L, j);
if (i < R)
quicksortA(i, R);
}
public void quicksortB(int L, int R)
{
i = L;
j = R;
x = B[(L + R) / 2];
do
{
while (B[i] < x)
i = i + 1;
while (x < B[j])
j = j - 1;
if (i <= j)
{
w = B[i];
B[i] = B[j];
B[j] = w;
i = i + 1;
j = j - 1;
}
} while (i < j);
if (L < j)
quicksortB(L, j);
if (i < R)
quicksortB(i, R);
}
public void Intercalar()
{
I = 0;
J = 0;
K = 0;
X = 0;
while (I < N && J < M)
{
if (A[I] <= B[J])
{
C[K] = A[I];
I = I + 1;
K = K + 1;
}
else
{
C[K] = B[J];
J = J + 1;
K = K + 1;
}
}
if (I > N)
{
for (X = J; X < M; X++)
{
C[K] = B[X];
K = K + 1;
}
}
else
{
for (X = I; X < N; X++)
{
C[K] = A[X];
K = K + 1;
}
}
}
public void DesplegarDesA()
{
int Cont = 1;
Console.Write("Vector A\n\n");
for (int i = 0; i < TempA.Length; i++)
{
Console.Write("{0}: {1}\t\t", i + 1, TempA[i]);
if (Cont == 5)
{
Console.Write("\n\n");
Cont = 0;
}
Cont++;
}
}
public void DesplegarDesB()
{
int Cont = 1;
Console.Write("\nVector B\n\n");
for (int i = 0; i < TempB.Length; i++)
{
Console.Write("{0}: {1}\t\t", i + 1, TempB[i]);
if (Cont == 5)
{
Console.Write("\n\n");
Cont = 0;
}
Cont++;
}
}
public void DesplegarOrdA()
{
int Cont = 1;
Console.Write("Vector A\n\n");
for (int i = 0; i < A.Length; i++)
{
Console.Write("{0}: {1}\t\t", i + 1, A[i]);
if (Cont == 5)
{
Console.Write("\n\n");
Cont = 0;
}
Cont++;
}
}
public void DesplegarOrdB()
{
int Cont = 1;
Console.Write("\nVector B\n\n");
for (int i = 0; i < B.Length; i++)
{
Console.Write("{0}: {1}\t\t", i + 1, B[i]);
if (Cont == 5)
{
Console.Write("\n\n");
Cont = 0;
}
Cont++;
}
}
public void DesplegarIntercalado()
{
int Cont = 1;
for (int i = 0; i < C.Length; i++)
{
Console.Write("{0}: {1}\t\t", i + 1, C[i]);
if (Cont == 5)
{
Console.Write("\n\n");
Cont = 0;
}
Cont++;
}
}
}
class Program
{
static void Main(string[] args)
{
int Opcion;
Intercalacion_Simple I = new Intercalacion_Simple();
do
{
Console.Clear();
Console.WriteLine("Menú");
Console.WriteLine("1.- Generar numeros aleatorios");
Console.WriteLine("2.- Ordenamiento de vectores");
Console.WriteLine("3.- Intercalar");
Console.WriteLine("4.- Salir");
Console.Write("\nQue opcion desea realizar: ");
Opcion = Int32.Parse(Console.ReadLine());
Console.Clear();
switch (Opcion)
{
case 1:
I.Generar();
Console.WriteLine("\nValores generados\n");
I.DesplegarDesA();
I.DesplegarDesB();
break;
case 2:
Console.WriteLine("\nDespliegue Ordenado\n");
I.quicksortA(0, I.A.Length-1);
I.quicksortB(0, I.B.Length-1);
I.DesplegarOrdA();
I.DesplegarOrdB();
break;
case 3:
Console.WriteLine("\nDespliegue Intercalado\n");
I.Intercalar();
I.DesplegarIntercalado();
break;
case 4:
break;
default:
Console.WriteLine("\nOpción Incorrecta");
break;
}
Console.ReadLine();
} while (Opcion != 4);
}
}
}
Mostrando entradas con la etiqueta Estructura de Datos. Mostrar todas las entradas
Mostrando entradas con la etiqueta Estructura de Datos. Mostrar todas las entradas
Intercalación Simple
Es un ejemplo del algoritmo y el código en c#, de la ordenación Externa de Estructuras de Datos mediante la intercalación directa.
Algoritmo Quicksort, ordenación interna
Algoritmo y código de la búsqueda interna, en base al intercambio, usados para Estructuras de Datos.
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Ejemplo
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Ejemplo
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Quick_Sort
{
int i, j, X, W;
int N = 25;
public int[] A;
public Quick_Sort()
{
A = new int[N];
}
public void Generar()
{
Random aleatorio = new Random();
for (int c = 0; c < 25; c++)
A[c] = aleatorio.Next(50);
}
public void quick(int L, int R)
{
i = L;
j = R;
X = A[(L + R) / 2];
do
{
while (A[i] < X)
i = i + 1;
while (X < A[j])
j = j - 1;
if (i <= j)
{
W = A[i];
A[i] = A[j];
A[j] = W;
i = i + 1;
j = j - 1;
}
} while (i < j);
if (L < j)
quick(L, j);
if (i < R)
quick(i, R);
}
public void Despliegue()
{
int contador = 1;
for (int j = 0; j < 25; j++)
{
Console.Write("{0}: {1}\t", j + 1, A[j]);
if (contador == 5)
{
Console.WriteLine("\n");
contador = 0;
}
contador++;
}
}
class Program
{
static void Main(string[] args)
{
Quick_Sort Q = new Quick_Sort();
int opcion = 0;
do
{
Console.Clear();
Console.WriteLine("MENU");
Console.WriteLine("1.- Generar numero aleatorios:");
Console.WriteLine("2.- Ordenar");
Console.WriteLine("3.- Desplegar");
Console.WriteLine("4.- Salir");
Console.WriteLine("\n Que opcion deseas realizar?");
opcion = int.Parse(Console.ReadLine());
switch (opcion)
{
case 1:
Console.WriteLine("Lista generada:\n");
Q.Generar();
Q.Despliegue();
Console.ReadLine();
break;
case 2:
Console.WriteLine("Se ordeno la lista");
Console.ReadLine();
Q.quick(0, Q.N - 1);
break;
case 3:
Console.WriteLine("\nLista ordenada:");
Q.Despliegue();
Console.ReadLine();
break;
case 4:
break;
default:
Console.WriteLine("incorrecto");
Console.ReadLine();
break;
}
} while (opcion != 4);
}
}
}
}
Programa C# Merge
Se muestra un ejemplo del algoritmo (código) meerge en consola en c# con datos INT, y datos STRING.
Definición:
El algoritmo Merge divide el arreglo original en dos arreglos y los coloca en arreglos separados. Cada arreglo es recursivamente ordenado y finalmente se unen los arreglos en un arreglo ordenado. Como cualquiera de los algoritmos de ordenamiento recursivo el algoritmo Merge tiene complejidad de O(n log n). Fue desarrollado por John Von Neumann.
El proceso del merge es fusionar mitades de arreglos ordenados dentro de un arreglo. Sin embargo, estas mitades de arreglos tienen que ser ordenadas primero, por lo que se requiere de fusinar mitades de arreglos ya ordenados de estas mitades. Este proceso de partición de arreglos en dos mitades termina cuando el arreglo tiene por lo menos dos elementos.
Ejemplo del programa de Merge con datos tipo INT
Definición:
El algoritmo Merge divide el arreglo original en dos arreglos y los coloca en arreglos separados. Cada arreglo es recursivamente ordenado y finalmente se unen los arreglos en un arreglo ordenado. Como cualquiera de los algoritmos de ordenamiento recursivo el algoritmo Merge tiene complejidad de O(n log n). Fue desarrollado por John Von Neumann.
El proceso del merge es fusionar mitades de arreglos ordenados dentro de un arreglo. Sin embargo, estas mitades de arreglos tienen que ser ordenadas primero, por lo que se requiere de fusinar mitades de arreglos ya ordenados de estas mitades. Este proceso de partición de arreglos en dos mitades termina cuando el arreglo tiene por lo menos dos elementos.
Ejemplo del programa de Merge con datos tipo INT
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
bool up;
int p, h, m, n = 25, k, l, i, j, q, r, t, con;
int[] a = new int[50];
public void Generar()
{
Random X = new Random();
for (int i = 0; i <= n; i++)
a[i] = X.Next(1, 200);
}
public void Desplegar()
{
con = 0;
for (int j = 0; j < n; j++)
{
if (con < 4)
{
Console.Write("{0}:{1}\t", j + 1, a[j]);
con++;
}
else
{
Console.Write("{0}:{1}\t\r\n", j + 1, a[j]);
con = 0;
}
}
}
public void MERGE()
{
up = true;
p = 1;
do
{
h = 1;
m = n;
if (up == true)
{
i = 0;
j = n-1;
k = n;
l = 2 * n-1;
}
else
{
k = 0;
l = n-1;
i = n;
j = 2 * n-1;
}
do
{
if (m >= p)
q = p;
else
q = m;
m = m - q;
if (m >= p)
r = p;
else
r = m;
m = m - r;
while (q != 0 && r != 0)
{
if (a[i] < a[j])
{
a[k] = a[i];
k = k + h;
i = i + 1;
q = q - 1;
}
else
{
a[k] = a[j];
k = k + h;
j = j - 1;
r = r - 1;
}
}
while (r > 0)
{
a[k] = a[j];
k = k + h;
j = j - 1;
r = r - 1;
}
while (q > 0)
{
a[k] = a[i];
k = k + h;
i = i + 1;
q = q - 1;
}
h = h*-1;
t = k;
k = l;
l = t;
}
while (m != 0);
up = !up;
p = 2 * p;
}
while (p < n);
if (up == false)
{
for (i = 0; i < n; i++)
a[i] = a[i + n];
}
con = 0;
for (int u = 0; u < n; u++)
{
if (con < 4)
{
Console.Write("{0}:{1}\t", u + 1, a[u]);
con++;
}
else
{
Console.Write("{0}:{1}\t\r\n", u + 1, a[u]);
con = 0;
}
}
}
static void Main(string[] args)
{
Program x = new Program();
int y = 0;
do
{
Console.Clear();
Console.WriteLine("Menu MERGE");
Console.WriteLine("1.-Generar");
Console.WriteLine("2.-Ordenar");
Console.WriteLine("3-Salir");
Console.WriteLine("Opcion a realizar");
y = System.Int16.Parse(Console.ReadLine());
switch (y)
{
case 1:
Console.Clear();
Console.WriteLine("Numeros sin ordenar");
x.Generar();
x.Desplegar();
Console.ReadLine();
Console.Clear();
break;
case 2:
Console.Clear();
Console.WriteLine("Sin ordenar");
x.Desplegar();
Console.WriteLine("\r\nOrdenado");
x.MERGE();
Console.ReadLine();
break;
case 3:
Console.Clear();
Console.WriteLine("Enter para salir");
Console.ReadLine();
break;
default:
Console.WriteLine("introduce opcion correcta");
y = 0;
Console.ReadLine();
break;
}
} while (y < 3);
}
}
}
Árbol Binario
Árbol.
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto.
Árbol Binario
Este tipo de árbol permite almacenar información ordenada. Reglas a cumplir:
- Cada nodo del árbol puede tener 0, 1 ó 2 hijos.
- Los descendientes izquierdos deben tener un valor menor al padre.
- Los descendientes derechos deben tener un valor mayor al padre.ones simples. Pero las características que implican no lo son tanto.
Ejemplo código de árbol binario:
using System;
using System.Collections.Generic;
using System.Text;
namespace ArbolBinario
{
class Arbol
{
int info;
Arbol izq, der;
public Arbol raiz = null;
public Arbol()
{
info = 0;
izq = null;
der = null;
}
public void Insertar(int X)
{
Arbol temp= new Arbol();
int bandera = 0;
Arbol hoja = new Arbol();
hoja.info = X;
hoja.izq = null;
hoja.der = null;
if (raiz == null)
raiz = hoja;
else
{
temp = raiz;
while (bandera != 1)
{
if (hoja.info < temp.info)
{
if (temp.izq == null)
{
temp.izq = hoja;
bandera = 1;
}
else
temp = temp.izq;
}
else
{
if (temp.der == null)
{
temp.der = hoja;
bandera = 1;
}
else
temp = temp.der;
}
}
}
}
public void Preorden(Arbol temp)
{
if (temp != null)
{
Console.WriteLine("{0}", temp.info);
if (temp.izq != null)
Preorden(temp.izq);
if (temp.der != null)
Preorden(temp.der);
}
else
Console.WriteLine("El arbol esta vacio.");
}
public void Enorden(Arbol temp)
{
if (temp != null)
{
if (temp.izq != null)
Enorden(temp.izq);
Console.WriteLine("{0}", temp.info);
if (temp.der != null)
Enorden(temp.der);
}
else
Console.WriteLine("El arbol esta vacio.");
}
public void Posorden(Arbol temp)
{
if (temp != null)
{
if (temp.izq != null)
Posorden(temp.izq);
if (temp.der != null)
Posorden(temp.der);
Console.WriteLine("{0}", temp.info);
}
else
Console.WriteLine("El arbol esta vacio.");
}
public void Eliminar()
{
Arbol p, q, r, s, t;
int X;
bool encontrado = false;
p = raiz;
q = null;
if (p != null)
{
Console.WriteLine("Cual nodo deseas eliminar?");
X = int.Parse(Console.ReadLine());
while (p != null && encontrado == false)
{
if (p.info == X)
{
encontrado = true;
Console.WriteLine("El nodo {0} sera eliminado del arbol binario", p.info);
}
else
{
q = p;
if (X < p.info)
p = p.izq;
else
p = p.der;
}
}
if (encontrado == true)
{
if (p.izq == null)
r = p.der;
else
{
if (p.der == null)
r = p.izq;
else
{
t = p;
r = p.der;
s = r.izq;
while (s != null)
{
t = r;
r = s;
s = r.izq;
}
if (t != p)
{
t.izq = r.der;
r.der = p.der;
}
r.izq = p.izq;
}
}
if (q == null)
raiz = r;
else
{
if (p == q.izq)
q.izq = r;
else
q.der = r;
}
}
else
Console.WriteLine("El nodo {0} no esta en el arbol binario",X);
}
else
Console.WriteLine("El arbol binario esta vacio.");
}
public void BusqRecursiva(Arbol temp, int X)
{
if (temp == null)
Console.WriteLine("No esta el nodo {0} en el arbo binario.",X);
else
{
if (X == temp.info)
Console.WriteLine("El nodo {0} si esta en el arbol binario.", X);
else
{
if (X < temp.info)
BusqRecursiva(temp.izq,X);
else
BusqRecursiva(temp.der, X);
}
}
}
public void BusqIterativa(Arbol temp, int X)
{
bool encontrado = false;
while (temp != null && encontrado == false)
{
if (X == temp.info)
encontrado = true;
else
{
if (X < temp.info)
temp = temp.izq;
else
temp = temp.der;
}
}
if (encontrado == false)
Console.WriteLine("El nodo {0} No esta en el arbol binario.", X);
else
Console.WriteLine("El nodo {0} si esta en el arbo binario.",X);
}
}
class Program
{
static void Main(string[] args)
{
Arbol A = new Arbol();
int opcion, X;
do
{
Console.Clear();
Console.WriteLine("Menu\n");
Console.WriteLine("1.- Insertar.");
Console.WriteLine("2.- Recorrido en Preorden");
Console.WriteLine("3.- Recorrido Enorden.");
Console.WriteLine("4.- Recorrido en Posorden.");
Console.WriteLine("5.- Eliminar nodos");
Console.WriteLine("6.- Busqueda recursiva de nodos.");
Console.WriteLine("7.- Busqueda iterativa de nodos.");
Console.WriteLine("8.- Salir.\n");
Console.WriteLine("Que opcion desea realizar?\n");
opcion = int.Parse(Console.ReadLine());
Console.Clear();
switch (opcion)
{
case 1:
Console.Write("Introduzca nuevo valor: ");
X = int.Parse(Console.ReadLine());
A.Insertar(X);
break;
case 2:
A.Preorden(A.raiz);
Console.ReadLine();
Console.Clear();
break;
case 3:
A.Enorden(A.raiz);
Console.ReadLine();
Console.Clear();
break;
case 4:
A.Posorden(A.raiz);
Console.ReadLine();
Console.Clear();
break;
case 5:
A.Eliminar();
Console.ReadLine();
Console.Clear();
break;
case 6:
Console.WriteLine("Que numero desea buscar?");
X = int.Parse(Console.ReadLine());
A.BusqRecursiva(A.raiz, X);
Console.ReadLine();
Console.Clear();
break;
case 7:
Console.WriteLine("Que numero desea buscar?");
X = int.Parse(Console.ReadLine());
A.BusqIterativa(A.raiz, X);
Console.ReadLine();
Console.Clear();
break;
case 8:
break;
default:
Console.WriteLine("Opcion Incorrecta.");
break;
}
} while (opcion != 8);
}
}
}
Manejo de Memoria Estática y Dinámica (Estructura de Datos)
Manejo de Memoria
El problema con la memoria estática de memoria es que siempre se reserva antes de conocer los datos concretos del problema y esto origina reservar siempre un máximo de memoria que en la mayoría de las veces no se va a necesitar.
Memoria dinámica:
La reserva de memoria dinámica se hace en tiempo de ejecución después de leer los datos y de conocer el tamaño exacto del problema. Como consecuencia se adapta mucho mejor a las necesidades en cada caso.
El sitio donde se almacenan los objetos se denominan en ingles heap o free store traducido como montículo o memoria libre, y el sitio preciso donde se encuentre depende del compilador y el tipo de puntero utilizado. La creación y estrucción de los objetos esta en manos del programador a través de los operadores new y delete.
En C# las variables que se declaran son punteros y se pasan eficientemente con referencia, tampoco es necesario considerar la liberación de la memoria puesto que framework se encarga de liberar todas las referencias que no se estén utilizando y compactar la memoria para mejorar el rendimiento.emoria para mejorar el rendimiento.
Memoria Estática
La forma más fácil de almacenar el contenido de una variable en memoria en tiempo de ejecución es en memoria estática o permanente a lo largo de toda la ejecución del programa.
Ventajas de utilizar memoria dinámica vs memoria estática
La memoria dinámica sirve para que los programadores se adapten siempre al tamaño del problema que tienen que resolver sin desperdiciar recursos de memoria y esto se traduce en una mayor eficiencia en la ejecución de los programas, las ventajas de utilizar memoria dinámica se valoran mejor en comparación con la utilización de la reserva de la memoria estática, como se muestra en el siguiente cuadro.
Ejemplo de uso del memoria estática:
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Csimple
{
static void Main(string[] args)
{
int[] numeros = new int[] { 1, 2, 3, 4, 5 };
for (int i = 0; i <>
Console.WriteLine("Numero:{0}={1}", i + 1, numeros[i]);
Console.ReadLine();
}
}
}
Ejemplo de uso de memoria dinámica:
using System;
namespace Circunferencia1
{
class CircunferenciaApp
{
public static void Main()
{
const double PI=3.1415926; // Esto es una constante
double Radio=4; // Esto es una variable
Console.WriteLine("El perímetro de una circunferencia de radio {0} es {1}", Radio,
2*PI*Radio);
Console.WriteLine("El área de un círculo de radio {0} es {1}", Radio,
PI*Math.Pow(Radio,2));
}
}
}
La salida en la consola de este programa sería la siguente:
El perímetro de una circunferencia de radio 4 es 25,1327408
El área de un círculo de radio 4 es 50,2654816
}
Suscribirse a:
Entradas (Atom)