Estructura de Datos
51.9K views | +91 today
Follow
Estructura de Datos
Estructura de Dator
Your new post is loading...
Your new post is loading...
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

6.3 Búsqueda por funciones de HASH

6.3 Búsqueda por funciones de HASH | Estructura de Datos | Scoop.it
Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash. La correspondencia más sencilla es la identidad, esto es, al número 0 se le asigna el índice 0, al elemento 1 el índice 1, y así sucesivamente. Pero si los números a almacenar son demasiado grandes esta función es inservible. Por ejemplo, se quiere guardar en un array la información de los 1000 usuarios de una empresa, y se elige el núemro de DNI como elemento identificativo. Es inviable hacer un array de 100.000.000 elementos, sobre todo porque se desaprovecha demasiado espacio. Por eso, se realiza una transformación al número de DNI para que nos de un número menor, por ejemplo coger las 3 últimas cifras para guardar a los empleados en un array de 1000 elementos. Para buscar a uno de ellos, bastaría con realizar la transformación a su DNI y ver si está o no en el array.

La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar.


"LAS TABLAS HASH"

En una "tabla hash", los elementos están formados por una pareja: una clave y un valor, como en un SortedList, pero la diferencia está en la forma en que se manejan internamente estos datos: la "tabla hash" usa una "función de dispersión" para colocar los elementos, de forma que no se pueden recorrer secuencialmente, pero a cambio el acceso a partir de la clave es muy rápido, más que si hacemos una búsqueda secuencial (como en un array) o binaria (como en un ArrayList ordenado). Un ejemplo de diccionario, parecido al anterior (que es más rápido de consultar para un dato concreto, pero que no se puede recorrer en orden), podría ser:

/*---------------------------*/
/* Ejemplo en C# */
/* HashTable1.cs */
/* */
/* Ejemplo de HashTable: */
/* Diccionario de inform. */
/* */
/* Introduccion a C#, */
/* Nacho Cabanes */
/*---------------------------*/

Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

6.1 Búsqueda secuencial

6.1 Búsqueda secuencial | Estructura de Datos | Scoop.it
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave. Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista.
La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones. Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.

Mejoras en la eficiencia de la búsqueda secuencial
1) Muestreo de acceso
Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas.
2) Movimiento hacia el frente
Este esquema consiste en que la lista de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el.
3) Transposición
Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre mas accesos tenga el registro, mas rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere mas tiempo de actividad para reorganizar al conjunto de registros . Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.
4) Ordenamiento

Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

5.1 MÉTODOS DE ORDENAMIENTO

5.1 MÉTODOS DE ORDENAMIENTO | Estructura de Datos | Scoop.it
5.1 ALGORITMOS DE ORDENAMIENTO INTERNOS

5.1.1 BURBUJA.

El método de burbuja también se le puede llamar como Método de "intercambiodirecto". El algoritmo ordena los elementos del arreglo utilizando el método de laburbuja . Transporta en cada pasada el elemento más pequeño hacia la parte deizquierda del arreglo.Este ordenamiento es eficiente sólo en listas pequeñas (10 elementos).El método de burbuja va comparando cada elemento del arreglo con el siguiente;si un elemento es mayor que el que le sigue, entonces se intercambian; estoproducirá que en el arreglo quede como su último elemento, el más grande. Esteproceso deberá repetirse recorriendo todo el arreglo hasta que no ocurra ningúnintercambio. Los elementos que van quedando ordenados ya no se comparan."Baja el más pesado".Este método se basa en el principio de comparar pares de elementos adyacentese intercambiarlos entre sí hasta que estén todos ordenados. A continuación se muestra el código del método de la burbuja
método de ordenamiento burbuja

public

void burbuja ()

{
inicio del método burbujafor(int i=nElementos-1;i>1;i--)
primer

for
recorreel
arreglo

{

for(int j=1;j<=i;j++)
for interno compara{if (datos[j-1]>datos[j])intercambiar(j-i,j);}
fin del for interno

}
fin del primer for recorre}//fin del método burbuja


5.1.2 QUICKSORT.

QUICKSORT (ORDENAMIENTO RAPIDO)
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 lóg. n. el algoritmooriginal es recursivo, pero se utilizan versiones interactivas para mejorar suordenamiento.

5.1.3 SHELLSORT.

El método de Shell es una versión mejorada del método de inserción directa. Yrecibe el nombre en honor a su autor, Donald Shell.El método también se conoce como de inserción con incrementos decrecientes.En el método de ordenación por inserción directa cada elemento se compara parasu ubicación correcta en el arreglo con los elementos que se encuentren en laparte izquierda del si mismo. Si el elemento a insertar es mas pequeño que elgrupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.Shell propone que las comparaciones entre elementos se efectúen con saltos demayor tamaño pero con incrementos decrecientes, así, los elementos quedaranordenados en el arreglo más rápidamente
.


1.4 RADIX

Es un algoritmo que ordena números enteros de forma individual, es decir delmenos significativo al mas significativo.Este ordenamiento consta de 10 dígitos de (0-9), su ordenamiento es del más
significativo al menos significativo de “menor a mayor”




Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

4.1 Arboles

4.1 Arboles | Estructura de Datos | Scoop.it
4.1.1 Concepto de á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
Definiremos varios conceptos. En relación con otros nodos:
Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol:
Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.
Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.
Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.
En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:
Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios.
Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas.
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol.
El nodo típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque sólo en el número de nodos. Veamos un ejemplo de nodo para crear árboles de orden tres:
struct nodo \{
int dato;
struct nodo *rama1;
struct nodo *rama2;
struct nodo *rama3;
};
O generalizando más:
#define ORDEN 5

struct nodo \{
int dato;
struct nodo *rama[ORDEN];
};

4.1.2 Clasificación de árboles

Existen cuatro tipos de árbol binario:.
A. B. Distinto.
A. B. Similares.
A. B. Equivalentes.
A. B. Completos.
A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

A. B. DISTINTO
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:


A. B. SIMILARES
Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo:


A. B. EQUIVALENTES
Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:


A. B. COMPLETOS
Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.

4.1.3 Operaciones básicas sobre árboles binarios.

Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles.
De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:
Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Moverse a través del árbol.
Recorrer el árbol completo.
Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles.

4.1.4 Aplicaciones

Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo.Aunque en este caso se trata de árboles con nodos de dos tipos, nodos directorio y nodos archivo,podríamos considerar que los nodos hoja son archivos y los nodos rama son directorios.Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo de este mismo manual,dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, comouna lista, en el que cada capítulo sigue al anterior, también es posible acceder a cualquier puntode él a través de la tabla de contenido.También se suelen organizar en forma de árbol los organigramas de mando en empresas o en elejército, y los árboles genealógicos.

4.1.5 Arboles balanceados (AVL)

Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1.
No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos donde los ABB no garantizan tiempos de búsqueda óptimos.
El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibrados locales, de modo que no es necesario explorar todo el árbol después de cada inserción o borrado.

Los AVL son también ABB, de modo que mantienen todas las operaciones que poseen éstos. Las nuevas operaciones son las de equilibrar el árbol, pero eso se hace como parte de las operaciones de insertado y borrado.
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

Pila

Pila | Estructura de Datos | Scoop.it
Con relación a la Estructura PILA:

Indicar objetos reales que se puedan modelar con dicha estructura.Memoria de una pc Caja de objetosDefiniciones de Pila.Una pila es un caso especial de lista en la cual todas las inserciones y supresiones tienen lugar en un extremo determinado llamado tope.
Definiciones de Pila.A las pilas se les llama también listas LIFO (last-in first-out) o listas “primero en entrar, primero en salir”. En el TDA Pila no se definen operaciones de posicionamiento en la pila. Esto es debido a que todas las operaciones de acceso se realizan en la misma posición, el tope de la pila.
TAD que modele las PILAS.Nombre: TAD PilaInvariante: n<>0Operaciones:crearPila()*/ Devuelve un valor del tipo pila preparado para ser usado y que contiene un valor de pila vacía. Esta operación es la misma que la de las listas generales.*/ Precondiciones: N=0 Pos condiciones: pila creada
insertarPila(crearPila)*/ mediante este método se insertan datos a la pila ya creada. Con las pilas se usa el método push para insertar*/Precondiciones: pila <> null Pos condiciones: insertarPila completado (datos insertados en pila)borrarPila()*/con este método se elmina cierta pila de datos */ Precondiciones: pila <> null Pos condiciones: pila eliminada
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

2.3 Ejemplos de casos recursivos

2.3 Ejemplos de casos recursivos | Estructura de Datos | Scoop.it
En el siguiente ejemplo se muetra un procedimiento recursivo.


using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;namespace WindowsApplication1{public partial class Recursividad : Form{public Recursividad(){InitializeComponent();}double r;int fin = 0;private void button1_Click(object sender, EventArgs e){fin = int.Parse(textBox4.Text.ToString());listBox1.Items.Clear();


listBox1.Items.Add("x\ty");evaluar();}//Procedimiento recusivopublic void evaluar(){while (fin <= int.Parse(textBox5.Text.ToString())){r = int.Parse(textBox1.Text.ToString()) * (fin * fin) +int.Parse(textBox2.Text.ToString()) * fin +int.Parse(textBox3.Text.ToString());listBox1.Items.Add(fin.ToString() + "\t" + r.ToString());fin++;evaluar();}}}
}

A continuación se expone otro ejemplo de programa que utiliza recursiónindirecta, y nos dice si un número es par o impar. Cabe mencionar que existenotros métodos mucho más sencillos para determinar la solución a este problema,basta con determinar el resto de la división entre dos. Por ejemplo: si hacemospar(2) devuelve 1 (cierto). Si hacemos impar (4) devuelve 0 (falso).
int par(int n);int impar(int n);int par(int n){ if (n == 0) return 1;return impar(n-1);}int impar(int n){ if (n == 0) return 0;return par(n-1);}
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

2.1 Definición

2.1 Definición | Estructura de Datos | Scoop.it
La recursividad es una técnica de programación importante. Se utiliza pararealizar una llamada a una funcion desde la misma funcion. Como ejemplo útil sepuede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante lamultiplicación de 1 * 2 *…, incrementando el número de 1 en 1 hasta llegar alnúmero para el que se está calculando el factorial.El siguiente parrafo muestra una función, expresada con palabras, quecalcula 8-un factorial.“Si el número es menor que cero, se rechaza. Si no es un entero, seredondea al siguiente entero. Si el número es cero, su factorial es uno. Si elnúmero es mayor que cero, se multiplica por él factorial del número menor inmediato.”Para calcular el factorial de cualquier número mayor que cero hay quecalcular como mínimo el factorial de otro número. La función que se utiliza es lafunción en la que se encuentra en estos momentos, esta función debe llamarse así misma para el número menor inmediato, para poder ejecutarse en el númeroactual. Esto es un ejemplo de recursividad.La recursividad es un concepto importante en informatica. Muchos algoritmosse pueden describir mejor en terminos de recursividad.Supongamos que P es un procedimiento que contiene una sentencia deLlamada a si mismo o una sentencia de Llamada a un segundo procedimiento quepuede eventualmente llamar de vuelta al procedimiento original P. Entonces P sedice que es u procedimiento recursivo. Como el progrma no ha de continuar ejecutandose indefinidamente, un procedimiento recursivo ha de tener las dossiguientes propiedades:

(1) Debe existir un cierto criterio, llamado criterio base, por el que elprocedimiento no se llama asi mismo.(2) Cada vez que el procedimiento se llame a si mismo (directa oinderectamente), debe estar mas cerca del criterio base.Un procedimiento recursivo con estas dos propiedades se dice que esta biendefinido.Similarmente, una funcion se dice que esta definida recursivamente si ladefinicion de la funcion se refiere a si misma. De nuevo, para que la definicion nosea circular, debe tener las dos siguientes propiedades:(1) Debe haber ciertos argumentos, llamados valores base, para los que lafuncion no se refiera a si misma.(2) Cada vez que la funcion se refiera a si misma, el argumento de la funciondebe acercarse mas al valor base.Una funcion recursiva con estas dos propiedades se dice tambien que estabien definida.
Tipos.
Podemos distinguir dos tipos de recursividad:

Directa: Cuando un subprograma se llama a si mismo una o mas vecesdirectamente.

Indirecta: Cuando se definen una serie de subprogramas usándose unos aotros.
Características.
Un algoritmo recursivo consta de una parte recursiva, otra iterativa o norecursiva y un acondición de terminación. La parte recursiva y la condición determinación siempre existen. En cambio la parte no recursiva puede coincidir conla condición de terminación. Algo muy importante a tener en cuenta cuandousemos la recursividad es que es necesario asegurarnos que llega un momentoen que no hacemos más llamadas recursivas. Si no se cumple esta condición elprograma no parará nunca.
Ventajas e inconvenientes.

La principal ventaja es la simplicidad de comprensión y su gran potencia,favoreciendo la resolución de problemas de manera natural, sencilla y elegante; yfacilidad para comprobar y convencerse de que la solución del problema escorrecta. El principal inconveniente es la ineficiencia tanto en tiempo como enmemoria, dado que para permitir su uso es necesario transformar el programarecursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

1.4 Manejo de memoria estática

1.4 Manejo de memoria estática | Estructura de Datos | Scoop.it
La forma más fácil de almacenar el contenido de una variable en memoria entiempo de ejecución es en memoria estática o permanente a lo largo de toda laejecución del programa.No todos los objetos (variables) pueden ser almacenados estáticamente.Para que un objeto pueda ser almacenado en memoria estática su tamaño(número de bytes necesarios para su almacenamiento) ha de ser conocido entiempo decompilación, como consecuencia de esta condición no podrán almacenarseen memoria estática:* Los objetos correspondientes a procedimientos o funciones recursivas, ya que entiempo de compilación no se sabe el número de variables que serán necesarias.* Las estructuras dinámicas de datos tales como listas, árboles, etc. ya que elnúmero de elementos que las forman no es conocido hasta que el programa seejecuta.Las técnicas de asignación de memoria estática son sencillas.A partir de una posición señalada por un puntero de referencia se aloja el objeto X, yse avanza el puntero tantos bytes como sean necesarios para almacenar el objeto X.La asignación de memoria puede hacerse en tiempo de compilación y los objetos estánvigentes desde que comienza la ejecución del programa hasta que termina.En los lenguajes que permiten la existencia de subprogramas, y siempre que todos losobjetos de estos subprogramas puedan almacenarse estáticamente se aloja enla memoria estática un registro de activación correspondiente a cada uno de lossubprogramas.Estos registros de activación contendrán las variables locales, parámetros formales yvalor devuelto por la función.Dentro de cada registro de activación las variables locales se organizansecuencialmente. Existe un solo registro de activación para cada procedimiento y portanto no están permitidas las llamadas recursivas. El proceso que se sigue cuando unprocedimiento p llama a otro q es el siguiente:1. p evalúa los parámetros de llamada, en caso de que se trate de expresionescomplejas, usando para ello una zona de memoria temporal para el almacenamientointermedio. Por ejemplos, sí la llamada a q es q((3*5)+(2*2),7) las operacionesprevias a la llamada propiamente dicha en código máquina han de realizarse sobrealguna zona de memoria temporal. (En algún momento debe haber unazona de memoria que contenga el valor intermedio 15, y el valor intermedio 4 parasumarlos a continuación). En caso de utilización de memoria estática éstazona de temporales puede ser común a todo el programa, ya que su tamañopuede deducirse en tiempo de compilación.2. q inicializa sus variables y comienza su ejecución
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

1.2 Modularidad

1.2 Modularidad | Estructura de Datos | Scoop.it
Modularidad en Ciencias de la computación es la característica por la cual un programa de computador está compuesto de porciones que se conocen como módulos. El diseño estructurado es la técnica de diseño de algoritmos en que se basa la programación modular, paradigma de programación que persigue desarrollar programas modulares.

La modularidad se basa en la descomposición de un problema en una serie de sub problemas; dividiéndolo en módulos que resultan de segmentar el problema en funciones lógicas que son perfectamente diferenciadas. Esta división exige la presencia de un módulo denominado módulo de base o principal a objeto de que controle y se relacione con los demás.

Es una técnica de programación que todavía se utiliza tanto para la construcción de algoritmos computacionales básicos así como apoyo al desarrollo de sistemas de gestión (en el diseño de diagramas modulares).

La salida del módulo debe ser función de la entrada, pero no de ningún estado interno. En la creación de los módulos deben cumplirse tres aspectos básicos: descripción, rendimiento y diseño.

En la descripción se definen las funciones y objetivos del programa. Para obtener el máximo rendimiento se ha de comprobar que el programa realice el proceso aprovechando al máximo todos los recursos de los que dispone. En cuanto al diseño, se debe comprobar la estructura que sigue el módulo, así como la estructura de los datos y la forma de comunicaciones entre los diversos y diferentes módulos.
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

6.2 Búsqueda binaria

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

Para utilizar este algoritmo, el array debe estar ordenado. La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:

Búsqueda Binaria
Si la tabla de números está ordenada, por ejemplo, en orden creciente, es posible utilizar para la búsqueda un algoritmo más eficiente que se basa en un concepto muy utilizado en la programación: dividir para vencer.
Si está ordenada la tabla y miramos el número situado en la mitad para ver si es mayor o menor que el número buscado (o con suerte igual), sabremos si la búsqueda ha de proceder en la subtabla con la mitad de tamaño que está antes o después de la mitad. Si se repite recursivamente el algoritmo al final o bien encontraremos el número sobre una tabla de un sólo elemento o estaremos seguros de que no se encuentra allí.
Este método permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de búsqueda binaria. Se trata de un algoritmo muy eficiente en cuanto el tiempo requerido para realizar una búsqueda es muy pequeño. La sintaxis expresada de forma genérica para realizar este método es la siguiente:
Int BinarySearch ([ ] m. tipo clave)
Donde m representa la matriz, clave es el valor que se desea buscar del mismo tipo que los elementos de la matriz, tipo es cualquier tipo de datos de los siguientes: objet, string, byte, char, short, int, long, flota, double, etc.
La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
int vector[10] = {2,4,6,8,10,12,14,16,18,20};
La clave que queremos buscar es 6. El algoritmo funciona de la siguiente manera
1. Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente.
2. Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5.
3. Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es
4. igual ya encontramos la clave y devolvemos Icentro.
5. Si son distintos, evaluamos si vector[Icentro] es mayor o menor que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 5 < 6, entonces la parte del arreglo vector[0…5] ya puede descartarse.
6. Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos que subir hasta 6, entonces quedaría Iarriba = 10, Iabajo = 6. Y volvemos al paso 2

Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

5.2 ALGORITMOS DE ORDENAMIENTO EXTERNOS

5.2 ALGORITMOS DE ORDENAMIENTO EXTERNOS | Estructura de Datos | Scoop.it
5.2.1 INTERCALACIÓN

En este método de ordenamiento existen dos archivos con llaves ordenadas, loscuales se mezclan para formar un solo archivo.La longitud de los archivos puede ser diferente.El proceso consiste en leer un registro de cada archivo y compararlos, el menor esalmacenando en el archivo de resultado y el otro se compara con el siguienteelemento del archivo si existe. El proceso se repite hasta que alguno de losarchivos quede vacío y los elementos del otro archivo se almacenan directamenteen el archivo resultado.


5.2.2 MEZCLA DIRECTA

ƒ Algoritmo de Mezcla Directa:

ƒ Dividir una secuencia inicial de datos en dos subcadenas y mezclar elemento a
elemento de forma ordenada.
ƒ El proceso se repite hasta que la secuencia inicial queda totalmente ordenada.

ƒ Pasos:

ƒ 1) Se divide la secuencia inicial de datos del fichero a
en dos mitades b y c
ƒ 2) Se mezclan b y c combinando elementos aislados para formar pares
ordenados
ƒ 3) La secuencia resultante se almacena en el fichero a y se repiten los pasos 1)
y 2) para formar cuádruplos ordenados.
ƒ 4) Se repiten los pasos ante
riores para formar octetos ordenados, y asísucesivamente.



2.3 MEZCLA NATURAL


Es una mejora del algoritmo de mezcla directa puesto que en vez de considerar tramos de tamaño fijo se toman en cuenta para la ordenación en todo momentotramos de longitud máxima. Al igual que la mezcla directa se debe hacer un proceso de partir el archivooriginal para mezclarlo, posteriormente mientras en el archivo C haya elementos amezclar.
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

4.2 Grafos

4.2 Grafos | Estructura de Datos | Scoop.it
Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos o aristas A. Los vertice se denominan también nodos o puntos.

Un arco, es un par ordenado de vértices(V,W) donde V es el vértice inicial y W es el vértice terminal del arco. Un arco se expresa como: V-->W y se representa de la siguiente manera:

Los vértice de un grafo pueden usarse para representar objetos. Los arcos se utilizan para representar relaciones entre estos objetos.

Las aplicaciones más importantes de los grafos son las siguientes:

Rutas entre ciudades.
Determinar tiempos máximos y mínimos en un proceso.
Flujo y control en un programa.


4.2.1 Terminología de grafos

La terminología que manejaremos regularmente para el uso de grafos es la siguiente:
CAMINO.Es una secuencia de vértices V1, V2, V3, ... , Vn, tal que cada uno de estos V1->V2, V2->V3, V1->V3.
LONGITUD DE CAMINO. Es el número de arcos en ese camino.
CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el último son distintos.
CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice.
ARISTAS PARALELAS. Es cuando hay más de una arista con un vértice inicial y uno terminal dados.
GRAFO CICLICO. Se dice que un grafo es cíclico cuando contiene por lo menos un ciclo.
GRAFO ACICLICO. Se dice que un grafo es aciclíco cuando no contiene ciclos.
GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un camino simple en cualesquiera dos nodos de G.
GRAFO COMPLETO ó FUERTEMENTE CONEXO.Un grafo dirigido G es completo si para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente tendrán que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a todos los demás nodos de G.
GRAFO UNILATERALMENTE CONEXO.Un grafo G es unilateralmente conexo si para cada par de nodos (V,W) de G hay un camino de V a W o un camino de W a V.
GRAFO PESADO ó ETIQUETADO. Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso.
VERTICE ADYACENTE. Un nodo o vértice V es adyacente al nodo W si existe un arco de m a n.
GRADO DE SALIDA.El grado de salida de un nodo V de un grafo G, es el número de arcos o aristas que empiezan en V.
GRADO DE ENTRADA.El grado de entrada de un nodo V de un grafo G, es el número de aristas que terminan en V.
NODO FUENTE.Se le llama así a los nodos que tienen grado de salida positivo y un grado de entrada nulo.
NODO SUMIDERO.Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo.


4.2.2 Operaciones básicas sobre grafos

En esta sección analizaremos algunas de las operaciones sobre grafos, como :

Creación.
Inserción.
Búsqueda.
Eliminación.
En esta sección, continuaremos utilizando los apuntadores que se usaron en las secciones anteriores. TOP para hacer referencia al primer nodo, LD para indicar liga derecha y LA para indicar liga abajo, por último usaremos los apuntadores P y Q para hacer referencia a los nuevos nodos que vayan a ser usados.

ALGORITMO DE CREACION.
repite
si top=NIL entonces
new(top)
top(la)<--NIL
top(ld)<--NIL
lee(top(dato))
q<--top
en caso contrario
new(p)
p(ld)<--NIL
p(la)<--NIL
q(la)<--p
lee(p(dato))
q<--p
mensaje(otro vertice ?)
lee(respuesta)
hasta repuesta=no
p<--top
mientras p<>NIL haz
mensaje(tiene vértices adyacentes p(dato) ?)
lee(respuesta)
si respueta=si entonces
repite
new(q)
lee(q(dato))
q(ld)<--p(ld)
p(ld)<--q
mensaje(otro vértice ?)
lee(respuesta2)
hasta respuesta2=no
p<--p(la)

ALGORITMO DE INSERCION
mensaje(valor a insertar ?)
lee(valor_a_insertar)
si top<>NIL entonces
p<--top
mientras p(la)<>NIL haz
p<--p(la)
new(q)
lee(q(dato))
p(la)<--q
q(la)<--NIL
mensaje(Hay vértices adyacentes?)
lee(respuesta)
si respuesta=si entonces
mensaje(Cuantos vértices?)
lee(número_vértices)
desde i=1 hasta número_vértices haz
new(p)
lee(p(dato))
q(ld)<--p
q<--q(ld)
en caso contrario
mensaje(no existe lista)

ALGORITMO DE BUSQUEDA
mensaje(vértice a buscar)
lee(vértice_a_buscar)
p<--top
repite
si p(dato)=vértice_a_buscar entonces
repite
p<--p(ld)
escribe(p(dato))
hasta p(ld)=NIL
en caso contrario
p<--(la)
hasta p=NIL

ALGORITMO DE BORRADO
mensaje(vértice a borrar ?)
lee(vértice_a_borrar)
p≪--top
r<--p
q<--p
sw<--falso
repite
si p(dato)=vértice_a_borrar entonces
si p=top entonces
top<--top(la)
r<--top
sw<--verdadero
en caso contrario
r(la)<--p(la)
repite
p<--p(ld)
dispose(q)
q<--p
hasta p=NIL
si sw=verdadero entonces
p<--r
q<--p
en caso contrario
p<--r(la)
q<--p
en caso contrario
r<--p
repite
q<--p(ld)
si q(dato)=vértice_a_borrar entonces
p(ld)<--q(ld)
dispose(q)
p<--p
en caso contrario
p<--p(ld)
hasta p=NIL
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

Cola

Cola | Estructura de Datos | Scoop.it
Con relación a la Estructura COLA:

Varias definiciones Cola.Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In FirstOut), debido a que el primer elemento en entrar será también el primero en salir.Una cola es también una estructura de datos lineal en donde las eliminaciones se realizan por uno de sus extremos que normalmente se llama frente, y las inserciones se realizan por el otro extremo que normalmente se llama final. A estas estructuras se les llama FIFO (First In FirstOut).
TAD que modele las COLAS.Nombre: TAD COLAInvariante: n/aOperaciones:crearCola()*/ Devuelve un valor del tipo cola preparado para ser usado y que contiene un valor de pila vacía. Esta operación es la misma que la de las listas generales.*/ Precondiciones: N=0 Pos condiciones: cola vacia creada
insertarCola(crearCola)*/ mediante este método se insertan datos a la cola ya creada. */ Precondiciones: cola <> null Pos condiciones: datos insertados en cola, cola insertada.borrarCola()*/con este método se elmina cierta cola de datos */ Precondiciones: cola != 0 Pos condiciones: cola eliminada
Particularidades de un TAD COLA con prioridades.Se introduce una forma de simular genericidad en los TADs de Modula-2 mediante el uso del TAD ITEM.En una cola de prioridad los elementos están ordenados dependiendo de su prioridad, de manera que esté disponible (para las operaciones Frente y Extraer) el elemento de máxima prioridad. En caso de igualdad se sigue la regla FIFO, de dos elementos con igual prioridad sale primero el que primero entró. Esto se puede conseguir bien insertando ordenadamente y extrayendo el primer elemento, bienDpto
Implementaciones de COLAS con vectores circularespublic class Cola { private static int max = 100; private Object elementos[]; private intfrente, post; } // fin clase Cola
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

Listas

Listas | Estructura de Datos | Scoop.it
Con relación a la Estructura LISTA Indicar objetos reales que se puedan modelar con dicha estructura.Listas de Ordenes de visitas (hospital…)Lista de aplicaciones Lista de pacientes.
Una lista es una estructura de datos secuencial. Una manera de clasificarlas es por la forma de acceder al siguiente elemento:- Lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array.- Lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.Definiciones de la misma LISTA
Definiciones de la misma LISTA Las Listas son secuencias de 0 o más elementos de un tipo de datos almacenado en memoria. Son estructuras lineales donde cada elemento de una lista excepto el primero tiene un único predecesor y cada elemento de la lista excepto el ultimo tiene un sucesor. Gráficamente:
TAD que modele las LISTAS.Nombre: TAD ListaInvariante: n/aOperaciones:crearLista()*/ Devuelve un valor del tipo pila preparado para ser usado y que contiene un valor de pila vacía. Esta operación es la misma que la de las listas generales.*/ Precondiciones: N=0 Pos condiciones: Lista creada
insertar(crearLista, x pos)*/ mediante este método se insertan datos a la Lista ya creada. Inserta elemento x en pos */ Precondiciones: pos != null Pos condiciones: insertarLista completado (dato insertado en Lista) FIN(): */Retorna la posición del último elemento, en otras palabras el “fin” de la lista, también se puede considerar con el tamaño de la lista. Sí la lista está vacía retorna una posición invalida que podría ser -1. */ Precondiciones: n/A Pos condiciones: operación finalizada ….TAD que modele las LISTAS.
TAD que modele las LISTAS.Siguiente(pos)*/con este método se Retorna pos + 1, si pos es igual o mayor a FIN(), retorna FIN(). */ Precondiciones: pos != 0 Pos condiciones: retorna posanterior(pos)*/con este método se Retorna pos – 1. */ Precondiciones: pos != 0 Pos condiciones: retorna pos limpiar(pos)*/Limpia la lista y Finaliza FIN()*/ Precondiciones: n…n+1, pos = 0 Pos condiciones: Lista vacia…
Relacionar el concepto de VENTANA con el de Lista.Una ventana es un área visual, normalmente de forma rectangular, que contiene algún tipo de interfaz de usuario, mostrando la salida y permitiendo la entrada de datos para uno de varios procesos que se ejecutan simultáneamente. Y un Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior.
Relacionar el concepto de VENTANA con el de Lista.El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco.La relación es que con ambos términos nos referimos a manipulación de datos sin importar el orden de los mismos, solo el acceso y su modificación.
Describir las implementaciones de Listas:Para representar en lenguaje C esta estructura de datos se utilizarán punteros, un tipo de datos que suministra el lenguaje. Se representaráunalistavacía con la constante NULL. Se puededefinir la listaenlazada de la siguientemanera:struct lista{int clave;struct lista *sig;};
Describir las implementaciones de Listas: e1.- VectoresUtilizando una estructura de datos estática arreglo para representar e implementar el TDA LISTAS. Asumamos que los ELEMENTOS que contiene la LISTA son representados por el tipo ENTERO. La cantidad de ELEMENTOS que puede contener la LISTA tiene un máximo de n ELEMENTOS. Por lo que la representación formal de este tipo se define de la siguiente manera: Tipo LISTA= arreglo [1..n] de ENTEROS; VarL : LISTA;
Describir las implementaciones de Listas: Implementación Procedimiento: Operaciones básicas… LISTA_VACÏA (Var L :LISTA)var i : ENTERO; principio Para i := 1 hasta n hacer L[ i ]:= 0; fin;Función ES_VACÍA(L :LISTA) : LÓGICO principio Si L[ 1 ] = 0 entonces ES_VACÏA := Verdad Sino ES_VACÏA := Falso; Fin;
Describir las implementaciones de Listas: Procedimiento Insertar (Var L :LISTA, p: POSICIÓN, e : ENTERO) var i : ENTERO; principio Si L [p] <> 0 entonces mientras (i <=n) y ( L [i ] <> 0 ) hacer principio sig := l[p]; l[i] := e; e := sig; fin; l [ i ] := e; fin;
Describir las implementaciones de Listas: e2.- Listas doblemente enlazadasUna lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior.El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Son listas que tienen un enlace con el elemento siguiente y con el anterior. Unaventajaquetienenesquepuedenrecorrerse en ambos sentidos, ya sea paraefectuarunaoperación con cadaelemento o parainsertar/actualizar y borrar. La otraventajaesquelasbúsquedas son algomásrápidaspuestoque no hacefaltahacerreferencia al elemento anterior. Su inconvenienteesqueocupanmásmemoriapornodoqueunalista simple.… Describir las implementaciones de Listas:
Mecanismos para implementar las listas.En el lenguaje C se utiliza los llamados punteros para representar esta estructura de datos.En java se encuentra un paquete completo en java.util de donde se pueden utilizar las listas, como un tipo abstracto de datos, este tipo de estructura de datos también se utiliza a partir y/o como una interfaz.
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

2.2 Procedimientos recursivos

2.2 Procedimientos recursivos | Estructura de Datos | Scoop.it
Un procedimiento o función recursiva es aquella que se llama así misma.Esta característica permite a un procedimiento recursivo repetirse valoresdiferentes de parámetros. La recursion es una alternativa a la iteración muyelegante en la solución de problemas, especialmente si estos tienen naturalezarecursiva.Normalmente, una solución recursiva es menos eficiente en términos detiempo de computadora que una solución iterativa debido al tiempo adicional dellamada a procedimientos.En muchos casos, la recursion permite especificar una solución mas simple ynatural para resolver un problema que en otro caso seria difícil. Por esta razón larecursion (recursividad) es una herramienta muy potente para la resolución deproblemas de programación.
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

1.5 Manejo de memoria dinámica

1.5 Manejo de memoria dinámica | Estructura de Datos | Scoop.it
¿Qué es la memoria dinámica?Supongamos que nuestro programa debe manipularestructuras de datos de longitud desconocida. Un ejemplo simple podría ser el de unprograma que lee las líneas de un archivo y las ordena. Por tanto, deberemos leer unnúmero indeterminado de líneas, y tras leer la última, ordenarlas. Unamanera de manejar ese ``número indeterminado'', sería declarar una constanteMAX_LINEAS, darle un valor vergonzosamente grande, y declarar un array de tamañoMAX_LINEAS. Esto, obviamente, es muy ineficiente (y feo). Nuestro programa no sóloquedaría limitado por ese valor máximo, sino que además gastaría esa enormecantidad de memoria para procesar hasta el más pequeño de los ficheros.La solución consiste en utilizar memoria dinámica. La memoria dinámica es unespacio de almacenamiento que se solicita en tiempo de ejecución. De esa manera, amedida que el proceso va necesitando espacio para más líneas, va solicitandomás memoria al sistema operativo para guardarlas. El medio para manejarla memoria que otorga el sistema operativo, es el puntero, puesto que no podemossaber en tiempo de compilación dónde nos dará huecos el sistema operativo (enla memoria de nuestro PC).
Memoria Dinámica.
Sobre el tratamiento de memoria, GLib dispone de una serie de instrucciones quesustituyen a las ya conocidas por todos malloc, free, etc. y, siguiendo con elmodo de llamar a las funciones en GLib, las funciones que sustituyen a las yamencionadas son g_malloc y g_free.
Reserva de memoria
.La función g_malloc posibilita la reserva de una zona de memoria, con unnúmero de bytes que le pasemos como parámetro. Además, también existe unafunción similar llamada g_malloc0 que, no sólo reserva una zona de memoria, sinoque, además, llena esa zona de memoria con ceros, lo cual nos puede beneficiar si senecesita un zona de memoriatotalmente limpia.gpointer g_malloc (gulong numero_de_bytes );gpointer g_malloc0 (gulong numero_de_bytes );Existe otro conjunto de funciones que nos permiten reservar memoria de una formaparecida a cómo se hace en los lenguajes orientados a objetos.
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Estructura de Datos
Scoop.it!

1.3 Uso de TDA

1.3 Uso de TDA | Estructura de Datos | Scoop.it
Usar el TDA permite aprovechar el nivel de abstracción en el desarrollo de un problema.Por ejemplo: Resolver el problema de verificación si la suma y multiplicación de 2númeroscomplejos producen el mismo número complejo. Solución en pseudo lenguaje:INICIO // Programa principal X, Y COMPLEJOA BooleanoX = CREAR_COMPLEJO(3,-5) Y = CREAR_COMPLEJO(8,-3)A = VERIFICAR1(X,Y)Si A = verdadero entonces imprimir “Son iguales la suma y lamultiplicación”Sino imprimir “NO son iguales la suma y la multiplicación”FsiFINfunción VERIFICAR1 (X,Y: COMPLEJO): Booleano // Función Verificar1Z1,Z2 COMPLEJOZ1 = SUMAR (X,Y)Z2 = MULTIPLICAR (X,Y)RETORNAR IGUAL (Z1,Z2)f.funciónfunción VERIFICAR2 (X,Y: COMPLEJO): Booleano // Función Verificar2 RETORNAR IGUAL (SUMAR (X,Y), MULTIPLICAR (X,Y) )f.funciónSe provee al lector de otra versión función VERIFICAR2 que realiza la misma operación sobre los números complejos. Note que VERIFICAR1 no es una operación del TDA
Via Cinthia Carrasco
more...
No comment yet.
Rescooped by Cinthia Carrasco from Sistemas Operativos ITSAV Lerdo
Scoop.it!

1.1 Tipos de datos abstractos (TDA)

1.1 Tipos de datos abstractos (TDA) | Estructura de Datos | Scoop.it
Los tipos de datos abstractos (TDA) encapsulan datos y funciones que trabajan con estos datos.Los datos no son visibles para el usuario en un tipo de dato abstracto y el acceso a los datos esexclusivamente bajo el llamado a funciones, también llamadas métodos. Así, el tipo de datoabstracto es especificado por los métodos, no por los datos. En C++, los tipos de datos abstractosson representados por clases, las cuales presentan a pequeña deficiencia: el dato que representael estado de un objeto de este tipo de dato abstracto es visible (algunas veces no accesible) en laparte private de la clase declarada para cada programa, la clase es reconocida mediante la vía#include. Ejemplos de tipos de datos abstractos son: stack, queue, etcLos TDA por lo general manejan memoria dinámica, esto es, la asignación dinámica de memoria esuna característica que le permite al usuario crear tipos de datos y estructuras de cualquiertamaño de acuerdo a las necesidades que se tengan en el programa, para ello se empleanfunciones típicas como malloc y free
more...
No comment yet.