Segunda Unidad

Unidad 2 – Estructura de datos

TEMAS •ARREGLOS (unidimensionales, bidimensionales y multidimensionales)

•PILAS •ELEMENTOS •OPERACIONES •TIPOS DE IMPLEMENTACION DE PILAS •COLAS •TIPOS DE COLAS (SIMPLES,CIRCULARES Y BICOLAS) •



¿Que es un arreglo?

Un arreglo es una colección de posiciones de almacenamiento de datos, donde cada una tiene el mismo tipo de dato y el mismo nombre. (las variables son como carpetas individuales, y un arreglo es como una sola carpeta con muchos compartimientos).



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]



•

Un arreglo unidimensional es un arreglo que tiene solamente un subíndice. Un subíndice es un numero encerrado entre corchetes a continuación del nombre del arreglo.

•

Los elementos de arreglos individuales del arreglo son guardados en posiciones consecutivas de memoria.

•

Cuando se declara un arreglo, el compilador reserva un espacio de

memoria lo suficientemente grande para guardar el arreglo completo.

•

Un arreglo bidimensional tiene dos subíndices, al igual que en arreglos

unidimensionales, se debe usar un esquema de numeración de los elementos; en

un arreglo de n elementos los subíndices permitidos van de 0 a n-1. Si se usa un valor de subíndice n se puede tener errores en el programa. •

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



Un arreglo multidimensional tiene mas de un subíndice, un arreglo bidimensional tiene dos subíndices, Un arreglo

tridimensional tiene 3 subíndices, y asi sucesivamente; no hay limite.

 Ejemplo:

Un juego de damas. El arreglo tiene 64 elementos :

cuadro [0] [0], cuadro [0] [1], cuadro [0] [2], cuadro [7] [6] cuadro [7] [7] ... No hay un fin de elementos de un arreglo.

PILAS DEFINICION

Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. 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.

ELEMENTOS

1.arreglo de datos 2.El numero máximo 3.El numero mínimo 4.El tipo de datos de la pila 5.los índices Tope y Base de la Pila

OPERACIONES CON PILAS

Operaciones Elementales

Operaciones primitivas

1.Iniciar 2.Insertar 3.Eliminar 4.Axiomas

1.Crear() 2.Destruir(P) 3.Tope(P) 4.Pop(P) 5.Pushx,P) 6.Vacía(P)

IMPLEMENTACION DE PILAS •IMPLEMENTACIÓN MATRICIAL DE LAS PILAS.

Para la implementación basada en matrices de pilas definimos el tipo de dato abstracto Pila por : typedef int tElemento /* Por ejemplo */ typedef struct { tElemento *elementos; int Lmax; int tope; } tipoPila; typedef tipoPila *pila;

IMPLEMENTACIÓN DE LAS PILAS MEDIANTE CELDAS ENLAZADAS.

COLAS DEFINICIÓN

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.

COLAS SIMPLES

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 (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

COLAS CIRCULARES O ANILLOS

Es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida.

COLAS DOBLES (BICOLAS)

Es una generalización de una estructura de cola simple. En una cola doble, los elementos pueden ser insertados o eliminados por cualquiera de los extremos. Es decir, se pueden insertar y eliminar valores tanto por el frente como por el final de la cola.

OPERACIONES CON COLAS

Insertar: meter dato en la cola Eliminar: sacar dato de la cola.

EJEMPLO

•Void insertar (objet x) -Insertar un nuevo elemento en la cola. •Objet extraer() -Devuelve y borra el elemento mas antiguio de la cola. •Objet verPrimero() -Devuelve el elemento mas antiguo de la cola •Bolean esta vacia() -Comprueba si la cola esta vacia •Viod vaciar() -Vacia la cola.

CERVANTES RUBIO ALEJANDRO  SANCHEZ RAMIREZ RENE  HERNANDEZ VIVEROS LETICIA  JURADO HERNANDEZ CARLOS  GAMEZ TREJO ABRAHAM JABTE  CONTRERAS SANCHEZ MIGUEL ANGEL  NEGRETE QUEZADA EDUARDO 