IMPORTANCIA DE LA ORGANIZACIÓN DE DATOS

[pic 3][pic 4]

TEMA N°1

INTRODUCCION A LA ESTRUCTURA DE DATOS

1. IMPORTANCIA DE LA ORGANIZACIÓN DE DATOS

Datos son los hechos que describen sucesos y entidades, “datos” es una palabra plural que se refiere a más de un hecho simple, se le denomina “data-item” o elemento de datos son comunicados por varios tipos de símbolos como ser: letras, números, etc. Tienen la capacidad de convertirse en información, estos a su vez están organizados dentro de un conjunto de información.

1.1 DATOS ABSTRACTOS “TDA”

Es como un modelo matemático, con una serie de operaciones definida en ese modelo.[pic 5]

1.2 FORMA DE ALMACENAMIENTO

Las formas de asignación de memoria cuando se hace uso de la estructura de datos, existen dos: Estático y Dinámico.

1.2.1 ALMACENAMIENTO ESTATICO

Forma de asignación de espacio que no varía durante la ejecución de un programa se debe indicar al inicio, cuantos espacios requiere para ubicar el espacio necesario solicitado.[pic 6][pic 7]

1.2.2 ALMACENAMIENTO DINAMICO

El tamaño de la estructura o la cantidad de elementos que esta pueda almacenar varia a medida que el usuario ejecuta el programa por lo que no requiere que se indique el espacio a utilizar y solo lo limita el espacio físico del computador (memoria ram).

1.3 LISTAS DE DATOS (más de un dato)

2.1.1 malloc

La función malloc reserva un bloque de memoria y devuelve un puntero void al inicio de la misma. Tiene la siguiente definición:

void  *malloc(size_t size);

2.1.2 calloc

La función calloc funciona de modo similar, pero además de reservar memoria, inicializa a 0 a la memoria reservada. Se usa comúnmente para arreglos y matrices. Está definida de esa forma:

Void  *calloc(size_t memb, size_t size);

2.1.3 realloc

La función realloc redimensiona el espacio asignado de forma dinámica anteriormente a un puntero. Tiene la siguiente definición:

void  *realloc(void  *ptr, size_t size)

2.1.4 free

Esta función sirve para liberar memoria que se asigna dinámicamente. Si el puntero es malo, free no hace nada. Tiene la siguiente definición:

void free (void *ptr);

El parámetro ptr es el puntero de la memoria que se desea liberar.

 [pic 8]

/*reservamos la memoria suficiente para almacenar un int y asignamos su dirección*/

[pic 9]

/*verificamos que la asignación se haya realizado correctamente*/

[pic 10]

/*error al reservar memoria*/

3. LISTAS ENLAZADAS

Estas son usadas para implementar otras estructuras de datos, consiste en una secuencia de Nodos, en las que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al Nodo anterior o posterior. Una lista de datos es un tipo de dato auto referenciado, contiene un puntero o un enlace a otro dato del mismo tipo. Estas listas permiten inserciones y eliminaciones de Nodos en cualquier punto de la lista.[pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18]

3.1 TIPOS DE LISTAS ENLAZADAS

3.1.2 LISTAS ENLAZADAS LINEALES

3.1.2.1 LISTA SIMPLE ENLAZADA

En esta lista cada Nodo tiene un único campo de enlace. El ultimo Nodo contiene NULL.

[pic 19][pic 20]

[pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28]

3.1.2.2 LISTAS DOBLEMENTE ENLAZADAS

Esta lista también se llama lista enlazada de dos vías. Cada Nodo tiene dos enlaces uno apunta al Nodo anterior y otro al Nodo siguiente o al valor NULL si es el ultimo

[pic 29]

3.1.2.3 LISTAS ENLAZADAS CIRCULARES

Estas listas tienen un primer y un último Nodo que están unidos. Esto se puede hacer tanto para las listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier Nodo y según la lista en cualquier dirección hasta que se regresa al Nodo original (también llamada lista sin comienzos ni fin).

[pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39]

En las listas enlazadas simples los nuevos nodos pueden ser insertados de uno ya referenciado.

En las listas dobles las inserciones y eliminaciones pueden ser hechos desde cualquier punto de acceso a algún Nodo cercano.[pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47]

[pic 48][pic 49][pic 50][pic 51][pic 52][pic 53]

[pic 54][pic 55]

[pic 56]

3.1.2.4 NODO CENTINELA

También llamado falso Nodo o Nodo ficticio. Puede ser implementado al principio o al final de una lista el cual no es usado para guardar datos. Su propósito es agilizar algunas operaciones asegurando que cualquier Nodo tiene un anterior o posterior.

 [pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66]

[pic 67]

[pic 68][pic 69][pic 70][pic 71][pic 72][pic 73]

[pic 74][pic 75][pic 76][pic 77][pic 78]

[pic 79][pic 80][pic 81][pic 82][pic 83][pic 84][pic 85][pic 86][pic 87]

[pic 88][pic 89][pic 90][pic 91]

3.2 APLICACIONES DE LAS LISTAS ENLAZADAS

Las listas enlazadas son usadas como modelos para otras estructuras de datos, tales como pilas, colas y sus variaciones.

El campo de datos de un Nodo puede ser otra lista enlazada, mediante este mecanismo podemos construir muchas estructuras de datos enlazadas con listas.

...