Unidad I INTRODUCCIÓN A LA ESTRUCTURA DE DATOS.

ﻈ        TIPOS DE DATOS ABSTRACTOS:

• Un TDA es un tipo de dato definido por el programador que se puede manipular de un modo similar a los tipos de datos definidos por el sistema.

• Está formado por un conjunto válido de elementos y un número de operaciones primitivas que se pueden realizar sobre ellos.

·         TDA Pila

Es una colección lineal, dinámica y homogénea, en la que los elementos de insertan y se extraen por el mismo extremo. También conocida como estructura LIFO (Last In, First Out).

ü  Operaciones:

ü CrearPila

ü  Meter

ü  Sacar

ü  DestruirPila

ü  EstaVacia

Representación:

ü  Utilizaremos un array para representar la pila.

ü  Definiremos un tamaño máximo de array (MaxElemPila).

ü  Llevaremos una variable: cima que indicará cual es el último elemento ocupado en el array.

Ejemplo de representación:

#define MaxElemPila

struct _TPilaEnteros {

int elementos[MaxElemPila];

int cima;

};

typedef struct _TPilaEnteros TPilaEnteros;

void CreaPila (TPilaEnteros *p) { p->cima = 0; };

int InsertaPila (int nelem, TpilaEnteros *p) {

if (p->cima==MaxElemPila) {

return 0; /*No se ha podido insertar*/

} else {

p->cima++;

p->elementos[p->cima]=nelem;

return 1;

};

};

·         TDA Lista

Notas:

• Es una estructura homogénea, dinámica y de acceso por posición.

• El tipo lista no existe en C por lo que habrá que implementarlo como un TAD.

Definición del tipo:

Una lista es una colección homogénea de elementos con una relación lineal entre ellos. Es decir, cada elemento de la lista (excepto el primero) tiene un único elemento predecesor y cada elemento (excepto el último) tiene un elemento sucesor

Operaciones:

ü  Creación

§  CreaLista

ü  Transformación

§  VaciarLista

§  InsertarElementoLista

§  BorrarElementoLista

§  ModificarElementoLista

ü  Observación

§  LongitudLista

§  RecuperarElementoLista

ü  Iteradores

§  PrimeroLista

§  SiguienteLista

§  AnteriorLista

§  FinalLista

♦ Representación Listas

• La representación escogida dependerá de la utilización que se le vaya a dar al tipo. Lo normal es implementarlas como listas de elementos enlazados mediante punteros.

• Los elementos serán estructuras con un uno o varios campos de datos y un campo de tipo puntero que hará referencia al siguiente elemento.

Ejemplo de representación:

/*lista de enteros*/

struct Tnodo {

int dato;

struct Tnodo *siguiente;

};

typedef struct Tnodo *TLista;

/*Permitira iterar sobre la lista*/

typedef struct Tnodo *TPosicion;

Ejemplo de declaración:

TLista listaValores;

TPosicion p;

OPERACIONES HABITUALES

CreaLista(L), BorraLista(L)	ß Crea una nueva lista vacía o la borra
EsVacia(L)	ß  Determina si la lista está vacía
Inserta(x,p,L)	ß Inserta en la lista L un nodo con el campo X, delante del nodo de dirección p.
Localiza(x,L),Recupera (x,p,L)	ß Posición donde está el valor x o su valor
Suprime(p,L)	ß Elimina el nodo p
Anterior(p,L)	ß Siguiente(p,L) Posición anterior o siguiente del elemento p
Primero(L)	ß Ultimo(L) Posición del primer o último elemento

UNIDAD I  MANEJO DE MEMORIA ESTATICA Y DINÁMICA.

*La administración de memoria de una computadora es una tarea fundamental debido a que la cantidad de memoria es limitada.

*La ejecución de un programa requiere que diversos elementos se almacenen en la memoria:

Código del programa (instrucciones)

Datos

Permanentes

Temporales

*Direcciones para controlar el flujo de ejecución del programa.

Asignación de memoria estática y dinámica.

ﻈ        A la asignación de memoria para algunos elementos fijos del programa que es controlada por el compilador se le llama asignación de memoria estática.

ﻈ        A la asignación y posible recuperación de memoria durante la ejecución de un programa y bajo su control, se le llama asignación de memoria dinámica.

MEMORIA ESTÁTICA

ü Define la cantidad de memoria necesaria para un programa durante el tiempo de compilación.

ü El tamaño no puede cambiar durante el tiempo de ejecución del programa.

ü Algunos lenguajes de programación utilizan la palabra static para especificar elementos del programa que deben almacenarse en memoria estática.

Ø Elementos que residen en memoria estática:

Ú Código del programa

Ú Las variables definidas en la sección principal del programa, las cuales pueden solo cambiar su contenido no su tamaño.

Ú Todas aquellas variables declaradas como estáticas en otras clases o módulos.

Ú Estos elementos se almacenan en direcciones fijas que son relocalizadas dependiendo de la dirección en donde el cargador las coloque para su ejecución.

MÉTODO COMÚN DE ASIGNACIÓN DE MEMORIA.

Un mapa de memoria (del inglés memory map) es una estructura de datos (tablas) que indica cómo está distribuida la memoria. Contiene información sobre el tamaño total de memoria y las relaciones que existen entre direcciones lógicas y físicas, además de poder proveer otros detalles específicos sobre la arquitectura de la computadora.