estructura de datos en c++

Estructura de Datos En C++

Dr. Romeo Sánchez Nigenda.E-mail: [email protected]://yalma.fime.uanl.mx/~romeo/Oficina: 1er. Piso del CIDET. Oficina con Dr. Oscar ChacónHoras de Tutoría: 10am-11am Martes y Jueves, 3:30pm-4:30pm Miércoles, 2:00pm-4:00pm Viernes.

Website: http://yalma.fime.uanl.mx/~romeo/ED/2011/Sesiones: 48

http://yalma.fime.uanl.mx/~romeo/




http://yalma.fime.uanl.mx/~romeo/ED/2011/

Objetivo General: Conocerá y manejará las estructuras internas de información

Temario:

1. Conceptos Básicos2. La Pila3. Colas4. Recursión5. Listas6. Árboles7. Ordenamiento8. Búsqueda9. Administración de Almacenamiento

Total a calificar: 110 puntos.

40% Tareas30% Examen Parcial30% Examen Final10% Participación

Material de apoyo:Estructura de Datos con C y C++. Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum, Brooklyn CollegeSegunda Edición, Prentice-Hall.

Algorithms. Third Edition.Parts 1-4, Fundamentals Data Structures Sorting SearchingRobert Sedgewick.

Estructura de Datos. Román Martínez, Elda Quiroga.Thomson Learning.

Cualquier libro de Estructura de Datos!

Software:Compiladores GCC (GNU Compiler Collection)

IDEs (Integrated Development Environment):http://www.eclipse.org/downloads/http://kdevelop.org/ http://www.bloodshed.net/devcpp.html

3. Listas

Objetivo: El alumno manejará estructuras de datos lineales y dinámicas, y entenderá las ventajas de utilizarlas para optimizar el uso de espacio en memoria.

Temario: ◦ Definición y conceptos utilizados◦ Operaciones con listas◦ Listas circulares◦ Listas doblemente ligadas◦ Aplicaciones

Listas Cuáles son las desventajas de usar almacenamiento

secuencial para presentar filas y colas?

Una lista vinculada (linked list) es una estructura dinámica de nodos de datos los cuales se representan como una secuencia. En su forma más simple, cada nodo se compone:◦ De un área de datos o información◦ De una referencia (link) al siguiente nodo en la secuencia

Se puede acceder a la lista vinculada por medio de una variable apuntador externa, que contenga la dirección del primer elemento en la lista.

El último nodo en la lista apunta al valor null para señalar el término de la secuencia.

inf sig inf sig inf signul

l

inf sigcabeza

Cada registro de una lista vinculada es a menudo llamado un elemento o nodo

El campo de cada nodo que contiene la dirección al siguiente nodo es usualmente llamado el siguiente link o siguiente puntero (next)

Los campos remanentes contienen los datos, información, o valores

La cabeza (head) de la lista es su primer elemento

La cola (tail) de la lista se puede referir al resto de los elementos después de la cabeza, o al último nodo

Listas

Características:◦ La estructura permite inserción y remoción de

elementos eficientemente de cualquier posición en la secuencia

◦ El principal beneficio entonces de una lista sobre arreglos es que sus elementos no necesitan reacomodarse cada vez que se actualiza la lista

◦ Una lista sin nodos se denomina lista vacía, el apuntador externo a la lista es null

◦ Sin embargo, listas simples no permiten acceso randomizado o indexación, por lo que operaciones básicas como obtener el último nodo en la lista o encontrar un nodo puede requerir escanear la mayoría o todos sus elementos

Listas

Listas: Operaciones básicasInserción en la parte delantera

de la lista6inf sig

3inf sig

8 null

inf sigcabeza

inf sigSe obtiene memoria para el nuevo nodo:

Se establecen los valores (datos) del nodo:

Se establece el link (sig) del nodo al primer elemento en la lista:

P & Nodo vacío

12inf sig

P &

P->sig = cabeza

6inf sig

3inf sig

8 null

inf sigcabeza

12inf sig

P &

Operaciones básicas: Inserción

Se actualiza el apuntador externo cabeza al nuevo nodo insertado:

El valor de P es irrelevante antes y después de la inserción del elemento a la lista:

El algoritmo básico de inserción queda entonces:

p = creaNodo ();info (p) = 12 //Datos nuevosnext (p) = cabezacabeza = p

cabeza = P

6inf sig

3inf sig

8 null

inf sig

cabeza12inf sigP

6inf sig

3inf sig

8 null

inf sigcabeza

12inf sig

Qué pasa cuando la lista está vacía?

Operaciones básicas: Remoción

6inf sig

3inf sig

8 null

inf sigcabeza

12inf sig

Se hace referencia al primer nodo en la lista a través de un apuntador:P = cabeza

La cabeza de la lista debe apuntar al siguiente nodo en la secuencia:cabeza = P->sig

Se guardan los valores a retornar en una variable: x = P->info

6inf sig

3inf sig

8 null

inf sig

cabeza12inf sigP

6inf sig

3inf sig

8 null

inf sigcabeza

12inf sig

P

Operaciones básicas: Remoción

En este momento se considera que P ya ha sido removido de la lista, pues a pesar que conserva un apuntador a un nodo en la lista, no es posible acceder a P a través del apuntador externo cabeza.

El siguiente paso sería liberar la memoria que P usa:liberaNodo(P)

El algoritmo de remoción es básicamente opuesto al de inserción:

P = cabezaCabeza = next(P)X = info(P) liberaNodo(P)

6inf sig

3inf sig

8 null

inf sigcabeza

12inf sig

P

Operaciones Básicas: Travesar

6inf sig

3inf sig

8 null

inf sigcabeza

12inf sig

Se obtiene un apuntador al primer elemento (cabeza) de la lista:P = cabeza

MIENTRAS que el apuntador no sea nulo (null), se lee el campo de información:X = P -> info

Se actualiza la variable apuntador al siguiente elemento en la lista:P = P -> sig

6inf sig

3inf sig

8 null

inf sig

cabeza12inf sigP

6inf sig

3inf sig

8 null

inf sig

cabeza12inf sig

P P P P… … …

Operaciones Básicas: Implementación

struct nodo{int info;struct nodo * sig;

};

typedef struct nodo *NODEPTR;

NODEPTR cabeza=NULL;

Definición de un nodo simple usando estructuras en C:

Inicialización de una lista vacía, usando un apuntador externo:

NODEPTR creaNodo(void){NODEPTR p = (NODEPTR) malloc (sizeof(struct nodo));return(p);

}

void liberaNodo(NODEPTR p){free(p);

}

Asignación de Memoria

Liberación de Memoria


void traversaLista(NODEPTR cabeza){NODEPTR p = cabeza;while(p!=NULL){

cout<<"Elem: "<<p->info<<endl;p=p->sig;

}}

6inf sig

3inf sig

8 null

inf sig

cabeza12inf sig

P P P… … …P

Operaciones Básicas: Implementaciónvoid insertaNodo(NODEPTR * cabeza, int valor){

NODEPTR p =creaNodo();p->info=valor;p->sig = *cabeza;*cabeza=p;

}

int borraNodo(NODEPTR * cabeza){int value = -1;if(*cabeza!=NULL){

NODEPTR p = *cabeza;*cabeza= p->sig;value = p->info;liberaNodo(p);

}return value;

} NODEPTR cabeza=NULL;insertaNodo(&cabeza,1);traversaLista(cabeza);borraNodo(&cabeza);

6inf sig

3inf sig

8 null

inf sigcabeza


Inserta después de un nodo P:

Pvoid insertaDespuesNodo(NODEPTR * P, int valor){

NODEPTR q =creaNodo();

q->info=valor;

q->sig=(*P)->sig;

(*P)->sig=q;}

valor

inf sig

q

inf sig

q

3inf sig

8 null

inf sig

P

valor

inf sig

q

3inf sig

8 null

inf sig

Pvalo

r

inf sig

q

6inf sig

3inf sig

8 null

inf sigcabeza


Elimina después de un nodo P:

P

int deleteDespuesNodo(NODEPTR * P){q=(*P)->sig;

valor = q->info;

(*P)->siq=q->sig;

liberaNodo(q);}

3inf sig

P

8 null

inf sig

8 null

inf sig

null…

Listas Implementando Colas

6inf sig

3inf sig

8 null

inf sigcabeza

P

cola

Se consideran dos apuntadores, uno al principio de la lista para remover elementos. El segundo al final de la lista para insertar (FIFO).

Pseudocódigo para remover un elemento:

remueve(Cola q){if(!colaVacia(q)){

p = q.cabezax = info(p) // Almacena 6 en X para retornarloq.cabeza = next(P) //cabeza apunta ahora al

segundo nodoif(q.cabeza==NULL){

q.cola=NULL //Si eliminamos el ultimo, actualiza cola

}liberaNodo(p);

}}

Listas Implementando Colas

6inf sig

3inf sig

8 null

inf sigcabeza

P

cola

Pseudocódigo para insertar un elemento:

inserta(Cola q, Elemento x){p = creaNodo()info(p) = x // Almacena el valor del nuevo elemento en el

nodonext(p) = NULL //Nuevo elemento es el últimoif(q.cola==NULL){

q.cabeza = p; //Cola vacia, entonces p es el primero

}else{next(q.cola) = p //El siguiente de cola apunta al

nuevo}q.cola = p //Cola se actualiza al ultimo elemento

}

Ejemplo: Remueve X elementos

Pseudocódigo para remover X elementos:

q = NULLP = cabezaWhile(P!=NULL){

If(info(p) == X){if(q==NULL){

cabeza = next(P)P=cabeza;

}else{p = next(P);deleteDespuesNodo(q)

}}else{

q=p;p = next(p)

}}

6inf sig

Xinf sig

8inf sig

cabeza X null

inf sig

Listas Circulares

6inf sig

3inf sig

8inf sig

12inf sig

• Una convención es que el apuntador externo apunte al último nodo en la lista, para así también acceder al primer nodo con el campo sig del último nodo.

Ejemplo: Pilas como listas circulares, donde el primer nodo es el tope de la Pila.

La pila está vacía si: apunta = NULL

int estaVacia(NODEPTR apunta) {return (apunta == NULL);

}

apunta

Listas Circulares: Pilas

6inf sig

3inf sig

Xinf sig

12inf sig

• Operación Push

void push(NODEPTR * apunta, int x) {NODEPTR p = creaNodo();p->info = x;if (estaVacia(*apunta)) {

(*apunta) = p;} else {

p->sig = (*apunta)->sig;}(*apunta)->sig = p;

}

Último nodo

apunta

P6inf sig

3inf sig

12inf sig

apunta

PUSH

Listas Circulares: Pilas

6inf sig

3inf sig

8inf sig

12inf sig

• Operación Pop

int pop(NODEPTR * apunta) {if (estaVacia(*apunta)) {

cout << “Pila vacia!" << endl;exit(1);}NODEPTR p = (*apunta)->sig;int x = p->info;if (p == (*apunta))

(*apunta) = NULL;else

(*apunta)->sig = p->sig;liberaNodo(p);return x;

}

Último Nodo Insertado

apunta

Listas Circulares

6inf sig

3inf sig

8inf sig

12inf sig

• Operación Traversal

void traversaPila(NODEPTR apunta) {NODEPTR p = apunta;NODEPTR q, ultimo;if (!estaVacia(apunta)) {

ultimo = q = p->sig;cout << "Elem: " << q->info << endl;q = q->sig;while (q != ultimo) {

cout << "Elem: " << q->info << endl;

q = q->sig;}

}}

Último Nodo Insertado

apunta

PrimerNodo Insertado

Listas Doblemente VinculadasAunque las listas circulares tienen

ventajas sobre las listas lineales, todavía tienen algunas limitaciones importantes:◦No se puede recorrer la lista hacia atrás◦No puede suprimirse un nodo dado solo un

apuntador hacia dicho nodo

En una lista doblemente vinculada, cada nodo posee dos apuntadores, uno a su antecesor y otro a su sucesor

Pueden ser lineales o circulares, y pueden o no tener un nodo de encabezado

Ejemplos de Listas Doblemente Vinculadas

inf sigNul

l12

prev inf sig14

prev inf sig10 Nul

l

prev

Lista doblemente vinculada

inf sig12

prev inf sig14

prev inf sig10

prev

Lista circular doblemente vinculada sin encabezado

inf sig12

prev inf sig14

prev inf sig10

prev

Lista circular doblemente vinculada con encabezado

inf sigprev

• Definición:

struct nodod{int info;struct nodod *prev, *sig;

};

typedef struct nodod * NODODOBLEPTR;

Implementación de Listas Doblemente Vinculadas

inf sigprev


• Borra el nodo dado:

int deleteNodoListaDoble(NODODOBLEPTR p){if((p)==NULL){

cout<<"Error en borrado!"<<endl;exit(1);

}NODODOBLEPTR l,r;int x = p->info;l = p->prev;r = p->sig;if(l!=NULL)

l->sig = r;if(r!=NULL)

r->prev = l;free(p);return x;

}

inf sigNul

l12

prev inf sig14

prev inf sig10 Nul

l

prev

void insertaNodoDerecha(NODODOBLEPTR p, int x){if(p==NULL){

cout<<"Error en insercion!"<<endl;exit(1);

}NODODOBLEPTR q,r;q = creaNodoDoble();q->info = x;r = p->sig;if(r!=NULL){

r->prev = q;}q->sig = r;q->prev = p;p->sig = q;

}


estructura de datos en c++

Documents