nanotecnologia

ABSTRACCIONES DE DATOS


Ciencias de la Computacio´ n



I. ESTRUCTURAS DE DATOS BA´ SICAS
Recordemos que tenemos los Arreglos Homoge´neos, que son bloques de datos rectangulares cuyas entradas son del mismo tipo. Como un ejemplo podemos tener los arrays de dos dimensiones, que consisten de las y columnas, en donde las posiciones son identificadas por un par de ´ındices.
Por otrolado tenemos los Arreglos Heteroge´neos, que son bloques de datos que pueden ser de diferentes tipos. Otras estructuras ba´sicas que tenemos son por ejemplo las listas, que son entradas de datos ordenadas secuencialmente. El inicio de la lista es llamado cabecera y el final es la cola, tenemos dos tipos de lista, las pilas y las colas. Las pilas son listas en las cuales los items se van agregando yquitando a la cabecera de esta (LIFO Ultimo en llegar, primero en salir). En cambio, las colas son listas en las cuales, los nuevos datos se van agregando a la cola, y se van quitando por la cabeza, tenemos como ejemplo las colas que se hacen en alguna ventanilla (FIFO Primero en entrar, primero en salir).
Finalmente tenemos los a´rboles, que son una coleccio´ n de datos organizados de formajera´rquica, como el que tendr´ıamos en una compan˜´ıa por ejemplo, teniendo al jefe a la cabeza, y bajo su mando algu´ n otro jefe de alguna area. Cada posicio´ n de un a´rbol, es denominada nodo, y tenemos varios tipos de nodos, como nodos raiz, nodos hoja, y nodos terminales.
Las estructuras de datos definidas anteriormente se refieren a la forma en que organizamos informacio´ n, pero la memoria deun computador no esta organizada de este modo, en cambio esta organizada en una lista de celdas de memoria con direcciones. Entonces debemos simular estas estructuras, es de lo que este cap´ıtulo se trata.

A. Estructuras Esta´ ticas versus Estructuras Dina´ micas
Estos tipos de estructuras las debemos de manejar de diferente manera, ya que si tenemos una estructura esta´tica, solodebemos proveer las direcciones en las cuales se trabaja y listo, nos olvidamos de problemas, en cambio, si lo que tenemos una estructura dina´mica, debemos preocuparnos de cuando se vayan a crear nuevas entradas, de cuando se vayan a eliminar, debemos buscar las direcciones de memoria con las cuales se trabajara.

B. Punteros
Un puntero es un area de almacenamiento que contiene una direccio´ ncodificada, la cual consta de varias direcciones de memoria juntas. En el caso de estructuras de datos, los
punteros se usan para almacenar la ubicacio´ n donde los items esta´n almacenados.

II. IMPLEMENTANDO ESTRUCTURAS DE DATOS

A. Almacenando Arreglos (Arrays)

1) Arreglos Homoge´neos: Para lograr esta estructura en la memoria del computador se procede de la siguiente manera: Seubican todos los elementos del array en forma consecutiva en memoria, esta consecucio´ n sera del taman˜ o que tenga el array deseado.
2) Arreglos Heteroge´neos: Estos se almacenan de forma similar a los arreglos homoge´neos, solo que los distintos valores referidos a una misma direccio´ n son almacenados de forma sucesiva, para lograr un acceso ra´pido a todos los items de este ´ındice al que sehace referencia en un momento dado.

B. Almacenando Listas

Al momento de almacenar una lista en memoria se puede hacer guardando esta lista en un solo bloque grande de informacio´ n en memoria, esto nos es u´ til cuando trabajamos con listas esta´ticas, para solucionar este problema tenemos el modelo de lista encadenada, que permite a cada elemento de la lista estar independientemente enmemoria, y en cada celda de estos elementos se almacena la direccio´ n del elemento siguiente y la del elemento anterior, estos nos facilitara las tareas en el momento que queramos insertar o quitar elementos de una lista dina´mica.

C. Almacenando Pilas y Colas

La estructura de una Pila en memoria, es muy similar al usado en una lista continua, se reserva un espacio en memoria del taman˜...