Estructura de Datos

Estructuras de Datos
Jos´ M. Saavedra Rondo
e
February 28, 2010

1

Introducci´n
o

Toda la informaci´n que se maneja dentro de un computador se encuentra almao
cenada en su memoria, que en trminos simples es una secuencia de caracteres
(bytes) en donde se encuentran las instrucciones y datos a los que se accede
directamente a travs del procesador del computador.
Los sistemas omtodos de organizacin de datos que permiten un almacenamiento eficiente de la informacin en la memoria del computador son conocidos como estructuras de datos. Estos mtodos de organizacin constituyen
las piezas bsicas para la construccin de algoritmos complejos, y permiten implementarlos de manera eficiente. Las estructuras de datos permiten luego definir
tipos abstractos de datos.
• Tipo Abstracto deDato (TAD): Un modelo computacional definido
por una estructura de datos determinada y un conjunto de operaciones
sobre dicha estructura: Ej. (Pila, Cola, Cadena son TAD’s).
TAD
Pila
Cadena
Lista

operaciones
push, pop
charAt, append, getLength.
insert, delete, getValue, sort.

• Estructuras Estticas y Dinmicas: Las estructuras de datos gestionan
la memoria del computador para poderalmacenar los datos. En este sentido existen estructuras estticas y dinmicas segn la gestin de la memoria.
– Estructuras Estticas: Define un tamao fijo (contiguo) de la memoria y solamente en ese espacio reservado se pueden almacenar los
datos (Ej. Arreglos)
– Estructuras Dinmicas: El tamao de la memoria no se fija a priori,
y por lo tanto los datos se encuentran dispersos en la memoria (Ej.Listas enlazadas)
• Manejo de Memoria: Al ejecutar un programa la memoria se divide en
3 segmentos. El segmento de Texto, que alamacena el cdigo compilado,
el segmento Stack, para almacenar la funciones que se ejecutan junto a
sus variables locales y el segmento Heap para varibles globales, estticas y
asignacin dinmica de memoria.

1

2

Arreglos

Un arreglo es una secuencia contigua deun n´mero fijo de elementos homog´neos.
u
e
Los arreglos se pueden crear seg´n los siguientes ejempos:
u
int A[10]
int *A= (int*)malloc(10*sizeof(int));

2.1

Problemas

1. Obtener el mayor de una secuencia.
2. Buscar un elemento en un arreglo.
3. Buscar un elemento en tiempo O(logn).
4. Crear una base de datos de M vectores aleatorios de tamao d cada uno.
Ahora, dado un vector p,encontrar el vecino m´s cercano a p usando la
a
distancia euclideana.
Ejemplo de soluci´n:
o
//Este programa permite leer datos en un arreglo y obtener el mayor
#include
#include
int obtenerMayor(int A[], int N)
{
int i=0, may=0;
may=A[0];
for(i=0;imay)
{
may=A[i];
}
}
return may;
}

int* leerDatos(int N)
{
int *A=(int*)malloc(N*sizeof(int));
int i=0;
printf("Ingreso dedatos: \n");
for(i=0;idato=x;
nodo->sgt=NULL;
return nodo;
}
TLE *crearLista()
{
TLE *lista=(TLE*)malloc(sizeof(TLE));
lista->inicio=NULL;
return lista;
}
void insertar(TLE *lista, int x)
{
TNodo *nodo=crearNodo(x);
TNodo *p=NULL;
if(lista->inicio==NULL)
{
lista->inicio=nodo;
}
22

else
{
p=lista->inicio;
while(p->sgt!=NULL)
{
p=p->sgt;
}
p->sgt=nodo;
}
}
voidreportar(TLE lista)
{
TNodo *p=NULL;
p=lista.inicio;
while(p!=NULL)
{
printf("%d \n",p->dato);
p=p->sgt;
}
}
int main()
{
TLE *l=crearLista();
insertar(l,1);
insertar(l,2);
insertar(l,3);
reportar(*l);
return 0;
}

7.3.3

Eliminar elemento

Supongamos que lo que queremos hacer es eliminar el nodo de la lista que contiene una cierto dato. La idea simplemente es encontrar el nodocorrespondiente
q y hacer que el nodo anterior a q apunte al siguiente de q. Con esto la lista deja
de tener acceso a q. Finalmente, liberamos el espacio que ocupaba q usando la
funci´n f ree. Miremos la implementaci´n:
o
o
void eliminar(TLE *lista, int dato)
{
TNodo *p=lista->inicio;
TNodo *ant=NULL;
int encontrado=0;
while((p!=NULL)&&(!encontrado))
{
if(p->dato==dato)

23

{...