martes, 12 de enero de 2010

UNIDAD IV: ESTRUCTURAS LINEALES

4.1 ARBOLES DEFINICION

Un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que bes hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.

El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.


4.1.2 REPRESENTACION EN MEMORIA DE ARBOLES

Existen dos formas de representar un Arbol en Memoria:


1- Mediante Listas Enlazadas:
Utilizando la firma de las listas lineales. Los Nodos del arbolbinario serán representados como registros que contendran como minimo dos 3 campos. En un campo se almacenará la información del nodo y los dos campos restantes se utilizarán para apuntar los arboles izquierdo y derecho respectivamente del nodo en cuestión.

Dado el siguiente nodo T

IZQ INFO DER

Donde el IZQ es el campo donde se almacenara la dirección del subarbol iszquierdo, INFO Contendra la información del nodo y DER La dirección del subarbol derecho

2- Representacion Secuencial :
Se utiliza un arreglo simple en el cual la raíz ocupara la posición uno y sus hijos estaran en la posicion 2*k para el hijo izquierdo y 2*k+1 para el hijo derecho

Ejem:


K Arbol
1 45
2 22
3
4 22
5
6 11
7
8
9
10
11 15
12
13 30
14
15 25
...
19 77
...
27 90

4.1.2.1 ARBOLES GENERALES

En ciencias de la computación, un árbol es una estructura de datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.

El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.


4.1.2.2 ARBOLES BINARIOS


Árboles Binarios

Un árbol binario T se define como un conjunto finito de elementos, llamados nodos, de forma que:

  1. T es vacío ( en cuyo caso se llama árbol nulo o árbol vació) o
  2. T contiene un nodo distinguido R, llamado raíz de T, y los restantes nodos de T forman un par ordenado de árboles binarios disjuntos T1 y T2.

Si T contiene una raíz R, los dos árboles T1 y T2 se llaman, respectivamente, subárboles izquierdo y derecho de la raíz R. Si T1 no es vació , entonces su raíz se llama sucesor izquierdo de R; y análogamente, si T2 no es vació, su raíz se llama sucesor derecho de R.

Observe que :

  1. B es un sucesor izquierdo y C un sucesor derecho del nodo A.
  2. El subárbol izquierdo de la raíz A consiste en los nodos B, D, E y F, y el subárbol derecho de A consiste en los nodos C , G, H, J, K y L.

Figura (1)

Cualquier nodo N de un árbol binario T tiene 0, 1 ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores, los nodos R y J sólo tienen un sucesor , y los nodos D,F, G,L y K no tienen sucesores. Los nodos sin sucesores se llaman nodos terminales.

La definición anterior del árbol binario T es recursiva, ya que T se define en términos de los subárboles binarios T1 y T2. Esto significa, en particular, que cada nodo N de T contiene un subárbol izquierdo y uno derecho. Más aun, si N es un nodo terminal, ambos árboles están vacíos.

Dos árboles binarios T y T’ se dicen que son similares si tienen la misma estructura o, en otras palabras, si tienen la misma forma. Los árboles se dice que son copias si son similares y tienen los mismos contenidos en sus correspondientes nodos.


4.1.3 RECORRIDO EN ARBOL BINARIO EN PREORDEN

El recorrido en un árbol binario permite rescatar los datos en formas diferentes. Aunque existen varias maneras de hacerlo, aquí se verán las más conocidas : inorden , preorden , postorden.

Una de los recorridos más usados (inorden) es el que rescata los datos en forma ordenada (de menor a mayor).

La técnica que usualmente se usa para hacer el recorrido, es ir almacenando los datos en una estructura lineal : Cola , Lista o Pila.

El criterio para escoger una de las tres depende del problema , pero generalmente los criterios generales son los siguientes :

  • Cola : los datos quieren ser vistos en el mismo orden en el cual fueron recorridos y la cola pasa a ser un instrumento de almacenamiento de "corto plazo" : (almacenar , ver , vaciar ).

  • Lista : los datos necesitan ser almacenados y se requieren operaciones en donde es necesario acceder a los datos en cualquier posición.

  • Pila : se necesita que los datos se almacenen en forma de pila, pasando a ser un instrumento de almacenamiento de "corto plazo".

    De aquí en adelante , las implementaciones de recorrido serán usando una Cola , ya que los problemas que vienen, requieren los datos en forma ordenada.


  • 4.1.3.2 RECORRIDO EN ARBOL BINARIO INORDEN

    Se declara una función que recibe como parámetros un arbol binario y una cola.

    Las instrucciones de la función, siguen el concepto recursivo de la definición, teniendo en cuenta que el concepto de "visitar el elemento de la raiz" se reemplaza por : obtener la raíz e insertar el elemento en la cola y que la condición de la recursividad es que se encuentre con algún subárbol vacío.

    *nota : Hay que tener cuidado en verificar que la cola que se pasa como parámetro sea no vacía. Las funciones serán implementadas en el archivo "funcArbin.h".

    void inordenArbin(Arbin a,Cola col)
    {
    if (!vacioArbin(a))
    {
    inordenArbin(izqArbin(a),col);
    TipoA raiz
    = raizArbin(a);
    adicCola
    (col,raiz);
    inordenArbin
    (derArbin(a),col);
    }
    }

    4.1.3.3 RECORRIDO EN ARBOL BINARIO POSORDEN

    • Recorrer el subarbol izquierdo en postorden.
    • Recorrer el subarbol derecho en postorden.
    • Examinar la raíz.


    4.1.4 BALANCEO ARBOLES BINARIOS

    En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.

    Tiempos para varias operaciones en términos del número de nodos en el árbol n:

    Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados.

    Estructuras de datos populares que implementan este tipo de árbol:

    Operación Tiempo en cota superior asintótica
    Búsqueda O(log n)
    Inserción O(log n)
    Eliminación O(log n)
    Iteración en orden O(n)

    4.1.5 CLASES PARA IMPLEMENTACION DE ARBOLES

    • Dado que los árboles binarios son de estructura fundamental en la teoría de los árboles, será preciso disponer de algún mecanismo que permita la conversión de un árbol general en árbol binario.

      “Los árboles binarios son más fáciles de programar que los generales”. En esto es imprescindible deducir cuántas ramas o caminos se desprenden de un nodo en un momento dado. Por ello, y dado que de los árboles binarios siempre se cuelgan como máximo dos subárboles, su programación será más sencilla.

      Afortunadamente, existe una técnica para convertir un árbol general a formato de un árbol binario. Ejemplo:

      Supongamos que se tiene el árbol A y se quiere convertir en un árbol binario B. El árbol de conversión tiene 3 pasos fáciles:

      1. - La raíz de B es la raíz de A

      2. -

      a) Enlazar un nodo raíz con el camino que conecta el nodo más a la izquierda (su hijo).

      ,. b) Enlazar éste nodo con los restantes descendientes del nodo raíz en su camino con lo que se forma el nivel 1.

      c) A continuación, repetir los pasos a y b con los nodos del nivel 2, enlazando siempre en un mismo camino todos los hermanos (descendientes del mismo nodo). Repetir estos pasos hasta llegar al nivel más alto.

      3.- Girar el diagrama resultante 45° para diferenciar entre los subárboles izquierdos y derecho.

      Ejem:

      T T

      A A

      B B

      C C

      D D

      E E


    4.2 GRAFOS DEFINICION

    Definicion:

    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:

    711.jpg

    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.

    Operaciones 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.


    4.2.3 REPRESENTACION DE GRAFOS EN MEMORIA


    Los grafos se representan en memoria enlazada mediante listas de adyacencia.

    Una lista de adyacencia, se define de la siguiente manera: Para un vértice i es una lista en cierto orden formada por todos los vértices adyacentes [a,i]. Se puede representar un grafo por medio de un arreglo donde cabeza de i es un apuntador a la lista de adyacencia al vértice i.

    Veamos el siguiente grafo dirigido:

    La lista de adyacencia, que se obtuvo a partir del grafo anterior es la siguiente:



    4.2.4 CLASES PARA IMPLEMENTACION DE GRAFOS

    En un grafo se tiene un circuito de Hamilton cuando se inicie en un nodo y termina en el mismo pasando exactamente una vez por cada nodo.

    CIRCUITO DE VENN EULER

    Este circuito se da en grafos donde se realiza un camino donde se puede pasar solo una vez por cada arco.

    El factor de peso o Ponderación se da en un grafo en el cual hay datos asociados con un arco.










    UNIDAD III: LISTAS ENLAZADAS

    3.1 LISTAS ENLAZADAS SIMPLES

    Definicion:

    Recorrido simplemente despliega los datos almacenados en el arreglo Info, con ayuda de un segundo arreglo llamado Indice el cual guarda el orden en el que encuentran enlazados cada uno de los datos.

    Explicacion:

    Apuntador toma el valor de Inicio, despu¨¦s ve si la condici¨®n cumple para efectuar un Ciclo mientras Apuntador sea diferente de 0, si cumple lo que hace es que despliega la Info[Apuntador], despu¨¦s Apuntador toma el valor de Indice[Apuntador] (El cual nos indica el siguiente nodo que sigue en la lista) y hace esto hasta que Apuntador sea igual a 0 (Cuando llega a este punto a llegado al fin de la Lista Enlazada).

    3.1.2 LISTAS ENLAZADAS DOBLES

    Una lista doble , ó doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su sucesor(ld). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.

    La estructura de un nodo en una lista doble es la siguiente:

    Existen dos tipos de listas doblemente ligadas:

    • Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NIL.
    • Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista.

    Debido a que las listas dobles circulares son más eficientes, los algoritmos que en esta sección se traten serán sobre listas dobles circulares.

    En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena números:

    En la figura siguiente se muestra un ejemplo de una lista doblemente ligada circular que almacena números:

    A continuación mostraremos algunos algoritmos sobre listas enlazadas. Como ya se mencionó, llamaremos li al puntero izquierdo y ld al puntero derecho, también usaremos el apuntador top para hacer referencia al primer nodo en la lista, y p para referenciar al nodo presente.


    3.1.3 LISTAS ENLAZADAS CIRCULARES

    En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer un lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

    Circularly-linked-list.svg
    Una lista enlazada circular que contiene tres valores enteros

    3.1.4 LISTAS ENLAZADAS MULTILISTAS

    • Conjunto de nodos en que algunos tienen más de un puntero y pueden estar en más de una lista simultáneamente.
    • Para cada tipo de nodo es importante distinguir los distintos campos puntero para realizar los recorridos adecuados y evitar confusiones.
    • Estructura básica para Sistemas de Bases de Datos en Red.
    • Dados dos tipos de entidades, TipoA y TipoB , se necesitan:

    Dos nuevos tipos correspondientes a los nodos para cada clase de entidad, que junto con la información propia de la entidad incluye los punteros necesarios para mantener la estructura.

    • typedef struct NodoTipoA {

    • TipoA Info;

    • NodoRelacion *PrimerB;

    • } NodoTipoA;

    • typedef struct NodoTipoB{

    • TipoB Info;

    • NodoRelacion *PrimerA;

    • } NodoTipoB;

    Una estructura para agrupar los objetos de cada tipo de entidad (Array, Lista,Árbol, Tabla Hash, ...).

    Un TDA Nodo Relacion que incluye un puntero por cada lista así como información propia de la relación.

    • typedef struct NodoRelacion {

    • NodoTipoA *SiguienteA;

    • NodoTipoB *SiguienteB;

    campo1;

    • ........

    campo_n;

    • } NodoRelacion;

    Un nodo Multilista que engloba los distintos tipos de nodos (entidad A, entidad B y relación). El tipo de dato para construir esto es el registro variante:

    typedef enum {NODO_A, NODO_B, NODO_ML} TipoNodo;

    • typedef struct NodoMultilista {

    • TipoNodo tipo;

    • union {

    • NodoTipoA a;

    • NodoTipoB b;

    • NodoRelacion nr;

    • } cont;

    • } NodoMultilista;


    3.1.5 CLASES PARA IMPLEMENTACION DE LISTAS

    • Para comenzar partiremos con una implementacion basica de una lista, la cual

      ocuparemos para realizar los ejercicios en la clase practica. Como reforzamiento

      a lo que se vio en la ayudantia, los metodos basicos que deben de tener estas

      implementaciones son:

      • Insert ( x, p ), insert el elemento x en la posicion p

      • end (), va a la posicion final de datos.(No necesariamenta la del arreglo).

      1

      • Locate ( x ), retorna la posicion del elemento x.

      • Retrieve ( p ), retorna el elemento en la posicion p.

      • Delete ( p ) ,Delete ( x ),Borra la posicion p. Borra el o los elementos x.

      • Next () ,Next ( p ), Posicion siguiente o posicion siguiente a p. La posicion

      siguiente esta dada por el valor de la posicion actual .

      • MakeNull () , Hace la lista nula, necesario para comenzar nuevamente.

      • PrintList (), Muestra los valores de la lista.

      Adicionalmente pueden agregar los metodos que uds encuentren necesarios por

      ejemplo.

      Para el manejo del arreglo:

      • Mover ( p ), dejara vacia la posicion p para poder insertar un dato.

      • Redimencionar ( x ),Agrega una cantidad de datos x al arreglo.

      • Borrar ( p ),borra el dato en p y dezplaza todos los valores una posicion.

      Recuerden que basicamente estamos trabajando con 3 variables:

      • El arreglo.

      • Variable de posicion Actual.

      • Variable de posicion Final.

      Recuerden que estas variables como su nombre lo dice, con la ejecucion del

      Codigo iran cambiando. Las 2 ultimas noson necesarias, pero pueden hacer el

      funcionamiento de la Lista mucho mas rapido, y servira para futuras implementacion

      que usaremos.







    UNIDAD II: ESTRUCTURAS LINEALES

    2.1 ARREGLOS DEFINICION

    Arreglo: Es un acomodo de espacios (Como en una matriz) en los cuales es una colección de un tipo de dato, y pueden ser unidimensionales, bidimesionales o multidimensionales

    Es un conjunto finito y ordenado de elementos homogéneos (del mismo tipo de datos). Es un tipo de dato estructurado simple o estático y pueden ser vectores o tablas (matrices).

    En lenguaje C, se pueden definir conjuntos de datos conocidos como arreglos. Por ejemplo, si deseáramos guardar en un arreglo, diez valores enteros, debemos definir este arreglo de la siguiente manera: int elem[10]; Esta expresión es la declaración del arreglo. Donde int es el tipo de datos que almacena el arreglo, elem es el nombre del arreglo, y el número encerrado en los corchetes es el número de valores que contiene el arreglo. Cabe hacer notar que, el índice para el primer elemento es 0 y, el valor máximo del índice es igual a n-1 elementos del arreglo. En nuestro caso, el último elemento del arreglo elem será elem[9]. El programador deberá tener cuidado de no indicar elementos inexistentes en el arreglo, es decir, elementos cuyos índices son números con signo menores a 0 o elementos con índices mayores a los n-1 elementos del arreglo. De no-tener cuidado, el compilador de C no marcará error alguno, pero se produce un error en tiempo de ejecución.

    Un arreglo se puede entender mejor representándolo como en la figura 2.1

    Figura 2.1. Representación de un arreglo lineal.

    Un punto importante es que, el nombre del arreglo es, por si mismo, un apuntador a la localidad de memoria que ocupa el primer elemento, es decir, el nombre del arreglo es una variable que contiene la dirección del primer elemento. Esto se puede expresar como sigue:

    elem = &elem[0]

    A continuación se presenta un programa que emplea arreglos para mostrar una serie de números y la palabra “hola”.

    int main(void)

    {

    int y; int numeros[4] = {2, 4, 6, 8}; char palabra[ ] = {’h’, ‘o’, ‘l’, ‘a’,’\0′}; for (y=0; y<4;>

    printf (“números [%d] = %d\n”, y, números[y] ); printf(“\n”); for (y=0; y<4;>

    printf (“%c”, palabra[y] ); return (0); } ¿ Cuál es el resultado de la ejecución del programa anterior? En el ejemplo, la forma de inicialización del arreglo números solo es soportada por el estándar ANSI.


    2.1.2 ARREGLOS UNIDIMENSIONALES

    Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.

    El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.

    Para implementar arreglos unidimensionales se debe reservar espacio en memoria, y se debe proporcionar la dirección base del arreglo, la cota superior y la inferior.

    REPRESENTACION EN MEMORIA

    Los arreglos se representan en memoria de la forma siguiente:

                    x : array[1..5] of integer
    

    Para establecer el rango del arreglo (número total de elementos) que componen el arreglo se utiliza la siguiente formula:

                    RANGO = Ls - (Li+1)
    

    donde:

    ls = Límite superior del arreglo

    li = Límite inferior del arreglo

    Para calcular la dirección de memoria de un elemento dentro de un arreglo se usa la siguiente formula:

                    A[i] = base(A) + [(i-li) * w]
    

    donde :

    A = Identificador único del arreglo

    i = Indice del elemento

    li = Límite inferior

    w = Número de bytes tipo componente

    Si el arreglo en el cual estamos trabajando tiene un índice numerativo utilizaremos las siguientes fórmulas:

                    RANGO = ord (ls) - (ord (li)+1)
    

    A[i] = base (A) + [ord (i) - ord (li) * w]

    1.3 Arreglos Bidimensionales

    Este tipo de arreglos al igual que los anteriores es un tipo de dato estructurado, finito ordenado y homogéneo. El acceso a ellos también es en forma directa por medio de un par de índices.

    Los arreglos bidimensionales se usan para representar datos que pueden verse como una tabla con filas y columnas. La primera dimensión del arreglo representa las columnas, cada elemento contiene un valor y cada dimensión representa una relación

    La representación en memoria se realiza de dos formas : almacenamiento por columnas o por renglones.

    Para determinar el número total de elementos en un arreglo bidimensional usaremos las siguientes fórmulas:

    RANGO DE RENGLONES (R1) = Ls1 - (Li1+1)

    RANGO DE COLUMNAS (R2) = Ls2 - (Li2+1)

    No. TOTAL DE COMPONENTES = R1 * R2

    REPRESENTACION EN MEMORIA POR COLUMNAS

    x : array [1..5,1..7] of integer

    Para calcular la dirección de memoria de un elemento se usan la siguiente formula:

    A[i,j] = base (A) + [((j - li2) R1 + (i + li1))*w]

    REPRESENTACION EN MEMORIA POR RENGLONES

    x : array [1..5,1..7] of integer

    Para calcular la dirección de memoria de un elemento se usan la siguiente formula:

    A[i,j] = base (A) + [((i - li1) R2 + (j + li2))*w]

    donde:

    i = Indice del renglón a calcular

    j = Indice de la columna a calcular

    li1 = Límite inferior de renglones

    li2 = Límite inferior de columnas

    w = Número de bytes tipo componente

    1.4 Arreglos Multidimensionales

    Este también es un tipo de dato estructurado, que está compuesto por n dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión

    Para determinar el número de elementos en este tipo de arreglos se usan las siguientes fórmulas:

    RANGO (Ri) = lsi - (lii + 1)

    No. TOTAL DE ELEMENTOS = R1 * R2* R3 * …* Rn

    donde:

    i = 1 … n

    n = No. total de dimensiones

    Para determinar la dirección de memoria se usa la siguiente formula:

    LOC A[i1,i2,i3,…,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*… (in - lin)*Rn]*w

    1.5 Operaciones Con Arreglos

    Las operaciones en arreglos pueden clasificarse de la siguiente forma:

    Lectura

    Escritura

    Asignación

    Actualización

    Ordenación

    Búsqueda

    a) LECTURA

    Este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes.

    La lectura se realiza de la siguiente manera:

    para i desde 1 hasta N haz

    x←arreglo[i]

    b) ESCRITURA

    Consiste en asignarle un valor a cada elemento del arreglo.

    La escritura se realiza de la siguiente manera:

    para i desde 1 hasta N haz

    arreglo[i]←x

    c) ASIGNACION

    No es posible asignar directamente un valor a todo el arreglo, por lo que se realiza de la manera siguiente:

    para i desde 1 hasta N haz

    arreglo[i]←algún_valor

    d) ACTUALIZACION

    Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.

    Para arreglos ordenados los algoritmos de inserción, borrado y modificación son los siguientes:

    1.- Insertar.

    Si i<>

    2.- Borrar.

    Si N>=1 entonces

    inicio

    i←1

    encontrado←falso

    mientras i<=n y encontrado=falso

    inicio

    si arreglo[i]=valor_a_borrar entonces

    inicio

    encontrado←verdadero

    N←N-1

    para k desde i hasta N haz

    arreglo[k]←arreglo[k-1]

    fin

    en caso contrario

    i←i+1

    fin

    fin

    Si encontrado=falso entonces

    mensaje (valor no encontrado)

    3.- Modificar.

    Si N>=1 entonces

    inicio

    i←1

    encontrado←falso

    mientras i<=N y encontrado=false haz

    inicio

    Si arreglo[i]=valor entonces

    arreglo[i]←valor_nuevo

    encontrado←verdadero

    En caso contrario

    i←i+1

    fin

    fin


    2.1.3 ARREGLOS BIDIMENCIONALES


    LA APLICACION DE LOS ARREGLOS BIDIMENSIONALES SON DE GRAN UTILIDAD PARA PODER TRABAJAR CON MATRICES Y VECTORES UN EJEMPLO MUY CLARO DE ESTO ES:

    int matriz[3][3];

        for(f=0;f<3;f++)
    
    {
    suma=0;
    for(c=0;c<3;c++)
    {
    suma=suma+matriz[c][f];
    }
    vectf[f]=suma;
    }

    Bueno aqui les dejo un ejemplo de una clase de arreglos bidimensionales, con otra clase llamada Teclado ;) espero que le entiendan les puse muchas especificaciones:) //esta clase va hacer que imprima desde el teclado,, nombre alumno, calificaciones y promedio final, es una lista de 3 alumnos ;) suerte:) import java.io.*; public class Pava

     {
    
    public static void main(String[]args)
    {

    Teclado leeDato=new Teclado();//Mandas traer la clase Teclado

    int suma=0;//declaracion ‘suma’ es el k sakara el promedio String alumno[]=new String[3];//declaras el arreglo en donde le indicas que es de tipo ‘String’ es decir aceptara caracteres, el ‘3′ es el tamaño de nuestro arreglo int cali[][]=new int[3][4];//Calificaciones tipo entero(creo k es obvio no) el tamaño tambien es asigando aki double prom[]=new double[3];//arreglo donde se mostrara el promedio de alumnos, por lo k debe ser igual de tamaño a ‘alumno’ y ‘cali’ en este caso es 3 or(int i=0;i<3;i++)>

     	 	  {
    
    System.out.println(“N Ombre? de alumno (a) (“+(i+1)+”)=“);
    alumno[i]=leeDato.getCadena();
    for(int j=0;j<4;j++)
    {
    System.out.println(“Calificacion del alumno(a) (“+(j+1)+”)=“);
    cali[i][j]=leeDato.getEntero();
    }
    }

    for(int i=0;i<3;i++)
    {
    for(int j=0;j<4;j++)
    {
    suma+=cali[i][j];
    }

    prom[i]=suma/(double)4.0;
    suma=0;
    }


    System.out.println(“Alumn@ \t\t\t Calificacion \t\t\t Promedio”);
    for(int i=0;i<3;i++)
    {
    System.out.print(alumno[i]+”\t\t”);
    for(int j=0;j<3;j++)
    {
    System.out.print(cali[i][j]+”\t”);

    }
    System.out.print(“ “);
    System.out.println(prom[i]);
    }
    }
    }

    public class Arreglos {

    	public static void main(String []args)
    
    {
    int suma=0;
    float prom[]=new float [6];
    String alumno[]= new String [6];
    int cal[][]=new int [6][4]

    for(int i=0;i<6;i++)
    {
    System.out.println(“Nombre del alumno”+(i+1);
    alumno[i]=lee.cadena;
    for(int j=0;j<4;j++)
    {
    System.out.println(“Calificacion #”+(j+i);
    cal[i][j]=lee.entero;
    }
    }


    for(int i=0;i<6;i++)
    {
    for(int j=0;j<4;j++)
    {
    suma+=cal[i][j];
    }

    prom[i]=suma/(float)4.0;
    suma=0;
    }

    System.out.println(“Alumn@ Calificacion Promedio”);
    System.out.println();

    for(int i=0;i<6;i++)
    {
    System.out.print(alumno[i]+\t\t);
    for(int j=0;j<4;j++)
    {
    System.out.print(cal[i][j]+” “\t\t);
    }
    System.out.print(“ “);
    System.out.println(prom[i]);
    }
    }

    }


    2.1.4 ARREGLOS MULTIDIMENSIONALES

    Este también es un tipo de dato estructurado, que está compuesto por n dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión

    Para determinar el número de elementos en este tipo de arreglos se usan las siguientes fórmulas:

    RANGO (Ri) = lsi - (lii + 1)

    No. TOTAL DE ELEMENTOS = R1 * R2* R3 * …* Rn

    donde:

    i = 1 … n

    n = No. total de dimensiones

    Para determinar la dirección de memoria se usa la siguiente formula:

    LOC A[i1,i2,i3,…,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*… (in - lin)*Rn]*w

    2.1.5 RESOLUCION DE PROBLEMAS CON ARREGLOS


    2.1.6 CLASES PARA IMPLEMENTACION DE ARREGLOS


    2.2 PILAS DEFINICION

    Las pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a la posición en la cual pueden realizarse las inserciones y las extracciones de elementos.

    Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.

    En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena, una pila de latas en un supermercado, una pila de papeles sobre un escritorio, etc.

    Debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura LIFO (Last In, First Out: último en entrar, primero en salir).

    2.2.2 OPERACION CON PILAS

    Una Pila se compone de los siguientes elementos:

    arreglo de datos

    El numero maximo

    El numero minimo

    El tipo de datos de la pila

    los indices Tope y Base de la Pila

    Operaciones Elementales

    Iniciar

    Insertar

    Eliminar

    Axiomas

    Insertar:

    Si Tope = Maximo

         Mensaje( O Verflow)
    

    de lo Contrario

    Tope = Tope +1

    Pila Tope = Valor

    //Codigo Fuente PILAS

    1. include
    2. include
    3. include

    int pila[5],cima=−1,maxpila=4,c=0,op,x,i,n; char r=‘n’;

    void meter(int *pila,int *cima,int maxpila,int item) {

    	if(*cima==maxpila)
    
    {cout<<”\nDesbordamiento”<<”\n”;}
    else
    {*cima=*cima+1;
    pila[*cima]=item;}

    }

    void sacar(int *pila,int *cima,int *item) { if(*cima==0)

    		{cout<<”\nSubdesbordamiento”;}
    
    else
    {*item=pila[*cima];
    *cima=*cima-1;}

    }

    int main() {clrscr();

    	do
    
    {clrscr();
    cout<<”\n1.-Insertar”;
    cout<<”\n2.-Eliminar”;
    cout<<”\n3.-SALIR”;
    cout«”\nInserta una opcion “;cin»op;

    switch(op)
    {case 1:
    cout«”¨Cuantos datos deseas insertar? “;cin»n;
    if(n>5)
    {cout<<”\nMemoria insuficiente”;
    getch();}
    else
    {for(i=0;i {cout«”\nIntroduce un numero “;cin»x;
    c=c+1;
    cout<<”\nDatos insertados “< clrscr();
    meter(pila,&cima,maxpila,x);}
    getch();}
    break;
    case 2:
    sacar(pila,&cima,& x);
    cout<<”\nEl dato borrado fue “< getch();
    break;
    case 3:
    cout«”DESEA SALIR (S/N) “;cin»r;
    break;
    default:
    cout<<”Ingresa numero valido\n”;
    getch();
    break;
    }while(r==‘n’ || r==‘N’);

    return 0; }

    2.2.3 CLASES PARA IMPLEMENTACION DE PILAS

    Ejemplo completo sobre la implementación de pilas manejando Visual Studio .net 2003

    //----LIO

    1. include “stdafx.h”
    2. using

    using namespace System;

    using namespace System::Collections;

    public __gc class Ejemplo Stack?{

    public:

        static void Imprime(I Enumerable? __gc *Mi Coleccion?)
    



    {



    System::Collections::I Enumerator? __gc *Mi Enumerador?

    = Mi ColeccionGet Enumerator?();

            while (Mi EnumeradorMove Next?())
    



    Console::Write(S”\t{0}”, Mi Enumerador→Current);



    Console::Write Line?();

    }

    };

    int main() {

        Stack __gc *Mi Pila? = new Stack();
    



    Mi Pila→Push(S”Hola”);



    Mi Pila→Push(S”Mundo”);



    Mi Pila→Push(S”!”);



    // Despliega las propiedades y valores de los pila.



    Console::Write Line(S”Mi Pila”);



    Console::Write Line(S”\tCount: {0}”,

    __box(Mi Pila→Count));

        Console::Write(S”\tValores:”);
    



    Ejemplo Stack::Imprime(Mi Pila);



    system(“pause”);



    return 0;

    }


    2.3 COLAS DEFINICION

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

    El tipo cola representa la idea que tenemos de cola en la vida real. La cola para subir al autobús está compuesta de elementos (personas), que dispone de dos extremos comienzo y fin. Por el comienzo se extraerá un elemento cuando haya comprado el billete para su viaje, y si llega una nueva persona con intención de usar el autobús, tendrá que colocarse al final y esperar que todos los elementos situados antes que él abandonen la cola.


    2.3.2 TIPOS

    2.3.2.1 COLAS SIMPLES

    En las colas el elemento que entro en primer lugar también es el primero en salir por ello se conocen como listas FIFO (First in - First out).

    Así pues la diferencia con las pilas recibe en el modo de entrada y salida de datos. En las colas las inserciones se realizan al final de la lista no al principio por ello las colas se usan para almacenar datos que necesiten ser procesados según el orden de llegada.

    Nodo I M F

    En la informática muchas aplicaciones para las colas (colas de aplicación) etc. . Por ejemplo un sistema de tiempo compartido suele tener un procesador central y una serie de periféricos compartidos: discos, impresoras, etc.

    Los recursos se comparten con diferentes usuarios y se utiliza una cola para almacenar el programa por los diferentes usuarios que esperan su turno de ejecución. El procesador atiende por riguroso orden de llamado de usuario.

    2.3.2.2 COLAS CIRCULARES

    • Colas circulares (anillos): en las que el último elemento y el primero están unidos.
    • Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:
    1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
    2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
    • Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:
    • Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.
    • Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

    2.3.2.3 COLAS DOBLES

    Existe una variable de la cola simple que es la bicola (doble cola). Es una cola bidimensional en la que las inscripciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la cola.

    Inserción Eliminación

    Inicio





    Final

    Eliminación Inserción

    Existen dos variantes de la bicola (cola doble):

    Cola doble con entrada restringida: Acepta valor, inserciones solo al final de la columna.

    Cola doble con salida restringida: Acepta eliminaciones solo al inicio de la cola.

    Indica Memoria Dinámica

    Crear I I=NULL

    Crear M M=NULL

    Crear F F=NULL

    Mientras si (Quiere dar de alta)

    Si I=Null Entonces

    Crear Nodo I

    I sig=NULL

    M=I

    F=I

    Si no

    Crear nodo F

    Fsig =M

    M=F

    2.3.3 OPERACIONES CON COLAS

    La definición de la estructura de datos tipo cola queda completa al incluir las operaciones que se pueden realizar en ella. Las operaciones básicas que pueden efectuarse son:

    Insertar un elemento en la cola

    Eliminar un elemento de la cola

    Las inserciones se llevaran a cabo por el FINAL de la cola, mientras que las eliminaciones se harán por el FRENTE —recuerde que el primero en entrar es el primero en salir.

    Considerando que una cola puede almacenar un máximo número de elementos y que además FRENTE indica la posición del primer elemento y FINAL la posición del último, se presentan a continuación los algoritmos correspondientes a las operaciones mencionadas.

    2.3.4 CLASES PARA IMPLEMENTACION DE COLAS

    Mediante Vectores

    Esta realización se caracteriza por :

    Es sencilla e intuitiva, ya que se basa en un vector.

    fin apunta al último dato.

    ini apunta a la posición anterior a la que contiene al primer dato.

    Declaración del tipo de dato

    unit cola1;

    interface;

    const

    Maxcola = 100; {tamaño del vector}

    nulo = 0;

    type

    tDato = integer ;

    tPos = nulo..Maxcola ;

    tCola = record

    Datos : array [1..Maxcola] of tDato ;

    ini,fin : tPos ;

    end ;

    Al añadir los elementos vamos incrementando fin , y al borrarlos decrementamos ini .

    Para evitar que el índice final se salga del vector podemos usar un vector circular mediante una

    función que dada una posición, devuelva la siguiente :

    function Siguiente (p : integer):integer;

    begin

    Siguiente:=p mod MaxEl+1 { Esto equivale a: if p=MaxEl then p:=1 else inc (i)}

    end ;

    En las colas circulares debe prestarse atención a que los índices no se crucen.









    UNIDAD I: TIPOS DE DATOS

    1.1 TIPOS DE DATOS

    Simples:

    Son todos aquellos que abarcan una sola casilla de memoria como los boleanos, enteros, flotantes, etc.

    Estructurales:

    Arreglos de cadenas, pilas o estructuras, abarcan mas de una casilla de memoria.

    TABLA COMUN DE TIPOS DE DATOS
    TIPORANGOBYTES
    E N T E R O S
    Entero−32,768 a 32,7672
    Entero sin signo0 a 65,5352
    Corto−32,768 a 32,7672
    Corto sin signo0 a 65,5352
    Largo entero−2,147,483,648 a 2,147,483,2954
    Largo sin signo0 a 4,294,967,2954
    C A R A C T E R
    Caracter−128 a 1271
    Caracter sin signo0 a 2551
    DE PUNTO FLOTANTE
    Flotante3.4−38 a 3.4384
    Doble1.7−308 a 1.73088
    Largo doble3.4−4932 a 3.44932 10

    Primitivos:

    No tienen “descomposición”, están predefinidos en el lenguaje.

    Tipos compuestos:

    Aparte de los anteriores, C++ soporta tipos compuestos (también denominados tipos-clase). Son compuestos o agregados de tipos básicos, por esta razón se les denomina también tipos agregados o abstractos ADTs (“Abstract data types”). El “material” de que están compuestos son los tipos básicos, bien en estado “puro” o en sus diversas “adaptaciones”. El proceso es recursivo, de forma que un tipo complejo puede contener miembros que son a su vez tipos complejos y así sucesivamente.

    Desde el punto de vista semántico la gramática C++ establece como tipos compuestos (“Compound types”) los siguientes:

    • Arreglos.
    • Matrices de objetos de cualquier tipo.
    • Funciones, que aceptan parámetros de ciertos tipos y devuelven void u objetos (o referencias a objetos) de cierto tipo.
    • Punteros a-void; punteros a-objetos, o punteros a-función (incluyendo miembros estáticos de clases) de un tipo determinado.
    • Punteros a miembros no-estáticos de clases (que señalan miembros de un tipo determinado dentro de objetos de una clase determinada).
    • Referencias a objetos o funciones de un tipo determinado.
    • Clases.
    • Uniones.

    Tambien existen tipos de datos definidos por el usuario que varian sus sintaxis segun el lenguaje de programación.


    1.1.1 TIPOS DE DATOS SIMPLES

    Tipos de datos simples

    Es uno de los conceptos fundamentales de cualquier lenguaje de programación. Estos definen los métodos de almacenamiento disponibles para representar información, junto con la manera en que dicha información ha de ser interpretada.

    Para crear una variable (de un tipo simple) en memoria debe declararse indicando su tipo de variable y su identificador que la identificará de forma única. La sintaxis de declaración de variables es la siguiente:

    Tipo Simple Identificador1, Identificador2;

    Esta sentencia indica al compilador que reserve memoria para dos variables del tipo simple Tipo Simple con nombres Identificador1 e Identificador2.

    Los tipos de datos en Java pueden dividirse en dos categorías: simples y compuestos. Los simples son tipos nucleares que no se derivan de otros tipos, como los enteros, de coma flotante, booleanos y de carácter. Los tipos compuestos se basan en los tipos simples, e incluyen las cadenas, las matrices y tanto las clases como las interfaces, en general.

    Cada tipo de datos simple soporta un conjunto de literales que le pueden ser asignados, para darles valor. En este apartado se explican los tipos de datos simples (o primitivos) que presenta Java, así como los literales que soporta (sintaxis de los valores que se les puede asignar).

    a.) Tipos de datos enteros

    Se usan para representar números enteros con signo. Hay cuatro tipos: byte, short, int y long.

    Tipo

     Tamaño

    byte

     1Byte (8 bits)

    short

     2 Bytes (16 bits)

    int

     4 Bytes (32 bits)

    long

     8 Bytes (64 bits)

    Tabla 5: Tipos de datos enteros

    Literales enteros

    Son básicos en la programación en Java y presentan tres formatos:

    Decimal: Los literales decimales aparecen como números ordinarios sin ninguna notación especial.

    Hexadecimal: Los hexadecimales (base 16) aparecen con un 0x ó 0X inicial, notación similar a la utilizada en C y C++.

    Octal: Los octales aparecen con un 0 inicial delante de los dígitos.

    Por ejemplo, un literal entero para el número decimal 12 se representa en Java como 12 en decimal, como 0xC en hexadecimal, y como 014 en octal.

    Los literales enteros se almacenan por defecto en el tipo int, (4 bytes con signo), o si se trabaja con números muy grandes, con el tipo long, (8 bytes con signo), añadiendo una L ó l al final del número.

    La declaración de variables enteras es muy sencilla. Un ejemplo de ello sería:

    long numeroLargo = 0xC; // Por defecto vale 12

    b.) Tipos de datos en coma flotante

    Se usan para representar números con partes fraccionarias. Hay dos tipos de coma flotante: float y double. El primero reserva almacenamiento para un número de precisión simple de 4 bytes y el segundo lo hace para un numero de precisión doble de 8 bytes.

    Tipo

     Tamaño

    float

     4 Byte (32 bits)

    double

     8 Bytes (64 bits)

    Tabla 6: Tipos de datos numéricos en coma flotante

    Literales en coma flotante

    Representan números decimales con partes fraccionarias. Pueden representarse con notación estándar (563,84) o científica (5.6384e2).

    De forma predeterminada son del tipo double (8 bytes). Existe la opción de usar un tipo más corto (el tipo float de 4 bytes), especificándolo con una F ó f al final del número.

    La declaración de variables de coma flotante es muy similar a la de las variables enteras. Por ejemplo:

    double miPi = 314.16e-2 ; // Aproximadamente

    float temperatura = (float)36.6; // Paciente sin fiebre

    Se realiza un moldeado a temperatura, porque todos los literales con decimales por defecto se consideran double.

    c.) Tipo de datos boolean

    Se usa para almacenar variables que presenten dos estados, que serán representados por los valores true y false. Representan valores bi-estado, provenientes del denominado álgebra de Boole.

    Literales Booleanos

    Java utiliza dos palabras clave para los estados: true (para verdadero) y false (para falso). Este tipo de literales es nuevo respecto a C/C++, lenguajes en los que el valor de falso se representaba por un 0 numérico, y verdadero cualquier número que no fuese el 0.

    Para declarar un dato del tipo booleano se utiliza la palabra reservada boolean:

    boolean reciboPagado = false; // ¡¿Aun no nos han pagado?!

    d.) Tipo de datos carácter

    Se usa para almacenar caracteres Unicode simples. Debido a que el conjunto de caracteres Unicode se compone de valores de 16 bits, el tipo de datos char se almacena en un entero sin signo de 16 bits.

    Java a diferencia de C/C++ distingue entre matrices de caracteres y cadenas.

    Literales carácter

    Representan un único carácter (de la tabla de caracteres Unicode 1.1) y aparecen dentro de un par de comillas simples. De forma similar que en C/C++. Los caracteres especiales (de control y no imprimibles) se representan con una barra invertida (‘\’) seguida del código carácter.

    Descripción

     Representación
    Valor Unicode

    Caracter Unicode

     \udddd

    Numero octal

     \ddd

    Barra invertida


    \u005C

    Continuación

     

    Retroceso

     \b
    \u0008

    Retorno de carro

     \r
    \u000D

    Alimentación de formularios

     \f
    \u000C

    Tabulación horizontal

     \t
    \u0009

    Línea nueva

     \n
    \u000A

    Comillas simples

     \’
    \u0027

    Comillas dobles

     \”
    \u0022

    Números arábigos ASCII

     0–9
    \u0030 a \u0039

    Alfabeto ASCII en mayúsculas

     A.-Z
    \u0041 a \u005A

    Alfabeto ASCII en minúsculas

     a.-z
    \u0061 a \u007A

    Tabla 7: Caracteres especiales Java

    Las variables de tipo char se declaran de la siguiente forma:

    char letraMayuscula = ‘A’; // Observe la necesidad de las ‘ ‘

    char letraV = ‘\u0056′; // Letra ‘V’

    e.) Conversión de tipos de datos

    En Java es posible transformar el tipo de una variable u objeto en otro diferente al original con el que fue declarado. Este proceso se denomina “conversión”, “moldeado” o “tipado”. La conversión se lleva a cabo colocando el tipo destino entre paréntesis, a la izquierda del valor que queremos convertir de la forma siguiente:

    char c = (char)System.in.read();

    La función read devuelve un valor int, que se convierte en un char debido a la conversión (char), y el valor resultante se almacena en la variable de tipo carácter c.

    El tamaño de los tipos que queremos convertir es muy importante. No todos los tipos se convertirán de forma segura. Por ejemplo, al convertir un long en un int, el compilador corta los 32 bits superiores del long (de 64 bits), de forma que encajen en los 32 bits del int, con lo que si contienen información útil, esta se perderá.

    Por ello se establece la norma de que “en las conversiones el tipo destino siempre debe ser igual o mayor que el tipo fuente”:

    Tipo Origen

     Tipo Destino

    byte

     double, float, long, int, char, short

    short

     double, float, long, int

    char

     double, float, long, int

    int

     double, float, long

    long

     double, float

    float

     double

    Tabla 8: Conversiones sin pérdidas de información


    1.1.1.1 DEFINICION BIT BYTE CARACTER PALABRA

    Bit: es una síntesis de dos términos en inglés: Binary digit, que en español significan dígito binario, o lo que es lo mismo, número (dígito) con dos posibles valores (binario). El término surge de usar las dos primeras letras de Binary con la última de digit.: bit. Es la unidad de información más sencilla posible en el sistema binario.

    Byte: Unidad de información que consta de 8 bits equivalente a un único caracter, como una letra, número o signo de puntuación.

    Caracter: Es un elemento tomado de un conjunto de símbolos. Un ejemplo de un conjunto de símbolos es {0,1,2,3,4,5,6,7,8,9,A,B,C….Y,z,¡,-,+,*} en el cual se incluyen dígitos, los caracteres del alfabeto y algunos caracteres especiales. Un compilador de lenguaje reconoce un conjunto particular de caracteres.

    Palabra: Conjunto de bits que, como unidad elemental, puede manipular una computadora. La longitud en bits de una palabra en una computadora puede ser de 8, 16, 32, etc., y depende del microprocesador de su unidad central de proceso.

    1.1.1.2 MANIPULACION DE BITS

    ESTA PUEDE ALMACENAR DE ACUERDO A LA FORMA EN QUE SE ESTEN ESPECIFICANDO A CONTINUACION DARE ALGUNOS EJEMPLOS DONDE SE APLICAN

    & CONJUNCION

    | DISYUNCIONDISYUNCION EXCLUSIVA

    ¬ NEGACION ( COMPLEMENTO A 1)

    >> DESPLAZAMIENTO DE BITS A LA DERECHA

    <<>

    ROR ROTACION A LA DERECHA

    ROL ROTACION A LA IZQUIERDA

    C-2 COMPLEMENTO A 2

    NOTA: ESTOS SE APLICAN A TIPOS DE DATOS ENTEROS EN EL LENGUAJE


    1.1.1.3 REPRESENTACION DATOS SIMPLES

    Los principales utilizados en la computadora son: texto, números imágenes y audio. Texto: Una pieza de texto en cualquier idioma, es una secuencia de símbolos usados para representar una idea en ese idioma.

     Por Ejemplo:

    Una computadora ocupa una secuencia de bits para ejecutar las instrucciones de un programa. Para representar cualquier símbolo se puede utilizar un patrón de bits. Dicho de otra forma la palabra byte esta formada por 4 símbolos en los que cada patrón define un solo símbolo. carácter B Y T E

    Código ASCII 100010 1011001 1010100 1000101

    Decimal 66 89 84 69

    7bits carácter 1 bit=0.1

    2bit =4 (00, 01, 10, 11)

    4 bit =8

    5 bit=16

    6 bit=32

    7 bit=128

    Código ASCII

    El Instituto Nacional Norteamericano de Estándares, desarrollo un código llamado “código norteamericano de estándares para intercambios de información” (ASCII), este código utiliza 7 bits para cada símbolo lo que significa 128 caracteres distintos son los que corresponden a este código.

    Números

    Los números se representan utilizando el sistema binario, los números se pueden representar dentro de la computadora clasificándolos de acuerdo a sus características como por ejemplo si son positivos, negativos o si utilizan decimales. En la actualidad la representación de uso más común es el complemento a dos porque permite manejar la memoria de una computadora de manera más eficiente.

    En la actualidad la representaron del uso mas común es el complemento a dos porque permite manejar la memoria de una computadora de manera más eficiente.

    Imágenes

    Se representa mediante dos métodos gráficos de mapa de bits y grafico vertical.

    Mapa de bits: En este método una imagen se divide en una matriz de pixeles (elemento de imagen) en donde cada píxel es un pequeño punto, el tamaño del píxel depende de la resolución.

    P/E

    0 0 0 1 1 0 0 0

    0 0 0 1 1 0 0 0

    0 1 1 1 1 1 1 0

    0 1 1 1 1 1 1 0

    0 0 0 1 1 0 0 0

    0 0 0 1 1 0 0 0

    0 blanco

    1 negro

    Para representar imágenes a color cada píxel se descompone en tres colores primarios (RGB) Red, Green, Blue, luego se mide la intensidad de cada color y se le suma un patrón de bits. En otras palabras cada píxel tiene tres patrones de bits:

    • Uno para la intensidad de rojo

    • Uno para el verde y el azul.

    COLOR R G B

    Rojo 11111111 00000000 00000000

    Verde 00000000 11111111 00000000

    Azul 00000000 00000000 11111111

    Imágenes grafico vertical

    El problema de grafico de mapa de bits es que los patrones de bits exactos para representar una imagen deben guardarse en la computadora, posteriormente si desea cambiar el tamaño de la imagen debe debes cambiar el tamaño de los pixeles los cuales crean una apariencia difusa y granulada.

    No obstante el grafico vertical no guarda patrones de bits, una imagen se descompone en una combinación de curvas y líneas.

    Audio

    Aunque no hay un estándar para descargar un contenido de música la idea es convertir el audio a datos digitales y usar patrones de bits.

    El audio por naturaleza es información análoga (continua).

    DIGITAL ANALOGOS

    VIDEO

    Es una representación de imágenes cuadros o frames y sonido en el tiempo; una película es una serie de cuadros desplegados unos tras otros para crear la ilusión de movimiento.

    Así que almacena de igual manera que una imagen y un sonido en la computadora.

    Pixeles:

    1 2 3


    1.1.2 TIPOS DATOS ABSTRACTOS

    En la historia de la ciencia de la computación los programadores han tenido que lidiar durante mucho tiempo con el problema de la complejidad , y a fin de entender lo que son las técnicas orientadas a objetos encontramos diferentes mecanismos para controlarla y a la cabeza de ellos encontramos a la abstracción esto es, la capacidad para encapsular y aislar la información de diseño y ejecución, esto es las técnicas orientadas a objetos son el producto de una progresión que va desde los procedimientos, a los módulos, los tipos de datos abstractos y los objetos.

    Un tipo de datos abstracto es aquel definido por el programador que puede ser manipulado de una manera similar a los definidos por el sistema .

    Al igual que estos últimos, un tipo de dato abstracto corresponde a un conjunto (tal vez tamaño infinito) “”00″” HECTORINN”“00″” De valores lícitos y de un numero de operaciones primitivas que pueden ejecutarse sobre ellos. El usuario puede crear variables con valores que fluctúen dentro del conjunto aceptado y actuar sobre dichos valores por medio de las operaciones definidas. Por ejemplo si tomamos como ejemplo una pila y la definimos como n tipo de dato abstracto y las operaciones como las únicas validas para ejecutar con ejemplares de la pila.

    Para construir un tipo de dato abstracto, debemos ser capaces de:

    • Exportar una definición de tipo

    • Proporcionar un conjunto de operaciones que pueden usarse para manipular los ejemplares del tipo.

    • Proteger los datos asociados con el tipo de tal manera que se pueda operar con ellos solo mediante la operación provista.

    • Crear múltiples ejemplares del tipo.

    La abstracción es la acción de separar mentalmente o bien la Representación de las características esenciales de algo sin incluir antecedentes o detalles irrelevantes, se le llama así por que la abstracción debe de encapsular todas las propiedades esenciales de algo, en términos de programación esto quiere decir que los objetos deben abstraer tanto los datos como los procesos. L a idea básica es que un objeto esta definido por una lista de atributos abstractos (con frecuencia, divididos en variables de instancia y variables de clase, tales como tamaño, posición el color, los procedimientos.

    Un tipo abstracto de datos es una abstracción, que describe un conjunto de objetos en términos de una estructura de datos encapsulada u oculta y las operaciones sobre esta estructura. Lo tipos de datos abstractos, al contrario de los tipos de datos primitivos, pueden ser definidos por el usuario al construir una aplicación, en lugar de ser construidos por el diseñador del lenguaje subyacente. En las clases de programación los ADT incluyen métodos por ejemplo un ADT que represente longitudes expresadas en unidades inglesas incluirá métodos para sumar pies y pulgadas.

    El encapsulamiento, o su equivalente, el ocultamiento de información, se refiere a la practica de incluir dentro de un objeto todo lo que necesita, y de hacerlo, además, de tal manera que ningún objeto necesite conocer nunca su estructura interna.


    1.2 ESTRUCTURA DATOS DEFINICION

    DEFINICIÓN

    En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales (un dato elemental es la mínima información que se tiene en el sistema) con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente.

    Una estructura de datos define la organización e interrelacionamiento de estos, y un conjunto de operaciones que se pueden realizar sobre él. Las operaciones básicas son:

    Alta, adicionar un nuevo valor a la estructura.

    Baja, borrar un valor de la estructura.

    Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma SECUENCIAL o BINARIO (siempre y cuando los datos estén ordenados)…

    Otras operaciones que se pueden realizar son:

    Ordenamiento, de los elementos pertenecientes a la estructura.

    Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

    Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.


    1.2.2 CLASIFICACION ESTRUCTURA DE DATOS

    CLASIFICACIÓN DE ESTRUCTURAS DE DATOS:

    Una estructura de datos es una clase de datos que se puede caracterizar por su organización y operaciones definidas sobre ella. Algunas veces a estas estructuras se les llama tipos de datos.

    en ellas encontramos las siguientes:

    ESTRUCTURAS LÓGICAS DE DATOS:

    En un programa, cada variable pertenece a alguna estructura de datos explícita o implícitamente definida, la cual determina el conjunto de operaciones validas para ella. Las estructuras de datos que se discuten aquí son estructuras de datos lógicas. Cada estructura de datos lógica puede tener varias representaciones físicas diferentes para sus almacenamientos posibles.

    ESTRUCTURAS PRIMITIVAS Y SIMPLES:

    Son primitivas aquellas que no están compuestas por otras estructuras de datos por ejemplo, enteros, booleanos y caracteres. Otras estructuras de datos se pueden construir de una o mas primitivas. Las estructuras de datos simples que consideramos se construyen a partir de estructuras primitivas y son: cadenas, arreglos y registros. A estas estructuras de datos las respaldan muchos lenguajes de programación.

    ESTRUCTURAS LINEALES Y NO LINEALES:

    Las estructuras de datos simples se pueden combinar de varias maneras para formar estructuras mas complejas. Las dos cases principales de estructuras de datos son las lineales y las no lineales, dependiendo de la complejidad de las relaciones lógicas que representan. Las estructuras de datos lineales incluyen pilas, colas y listas ligadas lineales. Las estructuras de datos no lineales incluyen grafos y árboles.


    1.2.2.1 ESTRUCTURA DE DATOS LINEALES Y NO LINEALES

    Estructura de datos lineales: arreglos, listas enlazadas, pilas y colas.

    Comprender, definir y utilizar os conceptos de las estructuras lineales – arreglos unidimensionales, bidimensionales y arreglos paralelos. Conocer y utilizar las operaciones mas usuales con arreglos unidimensionales y bidimensionales.

    Manejar los términos punteros y arreglos de punteros.

    Definir una lista enlazada y conocer y hacer uso de las operaciones mas comunes

    Definir y diferenciar las estructuras de datos TAD pilas y colas. Utilizar cada una de estas estructuras en la codificación de un algoritmo, utilizando el lenguaje de programación C++.

    Arreglos:

    Es un conjunto de datos o una estructura de datos homogéneos que se encuentran ubicados en forma consecutiva en la memoria RAM (sirve para almacenar datos en forma temporal).

    Un arreglo puede definirse como un grupo o una colección finita, homogénea y ordenada de elementos. Los arreglos pueden ser de los siguientes tipos:

    • De una dimensión. • De dos dimensiones. • De tres o más dimensiones.

    Listas enlazadas.

    Simples.

    Dobles.

    Circulares.

    Multilistas.

    Clases para la implementación de Listas.

    Pilas.

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

    Colas.

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

    Estructura de datos no lineales: árboles y grafos.

    Diferenciar entre las estructuras árboles y grafos. Conocer la representación en memoria de un árbol y de un grafo. Árboles.

    • Árboles binarios. • Árboles de expresión. • Construcción de árbol binario. • Recorrido de un árbol. • Aplicación de árboles binarios. • Árbol binario y de búsqueda. • Opresiones con árboles binarios de búsqueda.

    Grafos.

    Un grafo (específicamente, grafo simple no dirigido) es un par G D .V; E/ D .V .G/; V .E//, donde V es un conjunto finito no vacío de elementos llamados vértices y E es un conjunto de pares desordenados de elementos distintos de V llamados aristas. Es decir, una arista e 2 E tiene la forma fu; vg, donde u; v 2 V y u 6D v.

    La terminología en teoría de grafos varía muchísimo: prácticamente no hay dos textos que adopten la misma. En particular, los vértices de un grafo también reciben a veces el nombre de nodos, y las aristas arcos, ejes o líneas.


    1.2.2.2 ESTRUCTURA DE DATOS DINAMICAS Y ESTATICAS

    Datos estáticos: su tamaño y forma es constante durante la ejecución de un programa y por tanto se determinan en tiempo de compilación. El ejemplo típico son los arrays. Tienen el problema de que hay que dimensionar la estructura de antemano, lo que puede conllevar desperdicio o falta de memoria.

    Datos dinámicos: su tamaño y forma es variable (o puede serlo) a lo largo de un programa, por lo que se crean y destruyen en tiempo de ejecución. Esto permite dimensionar la estructura de datos de una forma precisa: se va asignando memoria en tiempo de ejecución según se va necesitando.




    lunes, 14 de septiembre de 2009

    INTEGRANTES

    Arizmendi Sosa Veronica

    Carrillo Monterro Aaron

    Castellanos Garcia Karen

    Pamela

    Maria Fernanda