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.

Hay pocas ventajas para implementar estas estructuras, sin embargo, son usadas más eficientemente para recorrer esta serie de datos.

3.2.1 DOBLEMENTE ENLAZADAS VS SIMPLEMENTE ENLAZADAS

1) En las simples, las operaciones son más sencillas.

2) Las listas dobles ocupan más espacio de memoria por Nodo y sus operaciones resultan ser más costosos, lo bueno es que permiten el fácil acceso a los Nodos.

4 IMPLEMENTACIONES

4.1 OPERACIONES SOBRE LISTAS ENLAZADAS

Estos son insertar y borrar Nodos en las listas.

4.1.1 PSEUDOCODIGO

1) LISTAS SIMPLEMENTE ENLAZADAS

Nuestra estructura de datos tendrá 2 campos, los variables serán: primer Nodo que siempre apuntan al primero de la lista o Nulo para la lista vacía.

[pic 92][pic 93]

2) INSERTAR UN ELEMENTO[pic 94][pic 95]

[pic 96][pic 97][pic 98][pic 99][pic 100][pic 101][pic 102][pic 103][pic 104]

[pic 105][pic 106][pic 107][pic 108]

[pic 109][pic 110][pic 111][pic 112][pic 113][pic 114]

[pic 115]

3) BORRAR UN ELEMENTO[pic 116][pic 117][pic 118][pic 119][pic 120][pic 121][pic 122][pic 123][pic 124]

[pic 125]

[pic 126]

[pic 127][pic 128][pic 129][pic 130][pic 131][pic 132][pic 133][pic 134][pic 135][pic 136][pic 137]

[pic 138]

TEMA N°2

PILAS Y COLAS

El método de Pila para la evaluación de expresiones fue propuesto en 1955 por una sociedad pionera en compilación para su uso en la estructura de datos.[pic 139][pic 140]

[pic 141][pic 142][pic 143][pic 144][pic 145][pic 146][pic 147][pic 148][pic 149][pic 150]

1. PILA COMO TIPO ABSTRACTO DE DATOS

La pila es un contenedor de Nodos y tiene 2 operaciones básicas push (apilar) y pop (desapilar).

...