estructura de datos en c++
DESCRIPTION
Estructura de Datos En C++. Dr. Romeo S ánchez Nigenda . E-mail: romeo.sanchez @ gmail.com http: //yalma.fime.uanl.mx/~ romeo / Oficina: 1er. Piso del CIDET. Oficina con Dr. Oscar Chacón Horas de Tutoría: 10am-11am Martes y Jueves, 3:30pm-4:30pm Miércoles, 2:00pm-4:00pm Viernes. - PowerPoint PPT PresentationTRANSCRIPT
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
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. La Cola (Queue)Objetivo: El alumno conocerá la estructura
denominada la Cola o Fila, representación y aplicaciones.
Temario: ◦ Representación de Colas◦ Operaciones con Colas◦ Colas circulares◦ Doble cola◦ Aplicaciones de colas
La Cola (Queue) Conjunto de elementos del que pueden suprimirse
elementos de un extremo (la parte delantera de la cola, front), y pueden agregarse elementos en el otro extremo (la parte posterior de la cola (rear)).
Front Rear
Primer elemento insertado es el primero en suprimirse (estructura FIFO, first in first out).
De manera genérica la cola necesita:Un TAD para almacenar sus elementosUn índice para indicar la posición del frente de la
colaUn índice para indicar la parte posterior de la cola
A B C D EElimina Agrega
Insertar (insert(q,i)): Agrega elemento i en la parte posterior de la cola q Remover (remove(q)): Suprime el elemento delantero de la cola q,
checando que la cola no se encuentre vacía Empty : (empty(q)) Retorna falso o verdadero dependiendo si la cola q
está vacía o no, el número de elementos está dado por q.rear-q.front+1
Colas: Operaciones
Vacía = True
q.Elems
Initq.Front=0q.Rear =-1
If q.rear<q.front
Insert(q,A)
Afrontrear
Insert(q,B)
BAfront
rear
Insert(q,C)
CBAfront
rear
Remove(q)
CB
rearfront
Remove(q)
C rear=front
Existe un problema, cuál es?Usando arreglos
Colas: Representación Básica#define SIZEQ 100
struct ColaBasica{int frente;int cola;int elementos[SIZEQ];
};
bool estaVacia(struct ColaBasica * C){return (C->cola < C->frente);
}
frentecola
inicio
Colas: Representación Básicabool mueveCola(struct ColaBasica * C){
if(C->frente>0){int j = 0;for(int i=C->frente;i<=C->cola;i++){
C->elementos[j++] = C->elementos[i];}C->frente = 0;C->cola=j-1;return true;
}return false;
} Frente
Cola
Cola
Frente
Colas: Representación Básicavoid insert(struct ColaBasica * C, int elem){
bool hayEspacio = true;if(C->cola+1 > SIZEQ-1){hayEspacio = mueveCola(C);}if(hayEspacio){C->elementos[++C->cola]=elem;}else{cout<<"Elemento no se pudo insertar!"<<endl;}
}
Frente
ColaCola
Frente
Colas: Representación Básicaint remove(struct ColaBasica * C){if(!estaVacia(C)){
return (C->elementos[C->frente++]);}else{
cout<<"Error cola vacia!"<<endl;exit(1);
}}
Frente
Cola Cola
Frente
Colas Circulares usando Arreglos
Frente
Evitamos mover elementos is asumimos que la cola es circular, es decir, que el primer elemento del arreglo está inmediatamente después del el último elemento.
Se puede reservar un elemento en el arreglo para determinar si la cola se encuentra vacía o no.
N=MAX +1bool estaVacia(struct ColaCircular q){
return q.frente % N == q.cola;}
bool estaLlena(struct ColaCircular q){return q.cola + 1== q.frente;
}
Utilizamos el tamaño de la cola para determinar cuando restablecer nuestros apuntadores al índice 0, y así simular que la Cola es circular!
N
[0]
[1]
Cola
MAX elementos
Se reserva un arreglo con un espacio más
Colas Circulares usando Arreglos: Ejemplo
MAX + 1
A
FrenteInsert(q,A) Insert(q,B) Insert(q,C)
Cola
MAX + 1
BA
Frente
Cola
MAX + 1
CBA
Frente
Cola
MAX + 1B
C
BFrente
Remove(q)Cola
MAX + 1D
C
Remove(q)
Frente
Cola
Insert(q,D)
MAX + 1DCBA
Cola
Frente
MAX + 1D
Remove(q)
Frente
Cola MAX + 1
Remove(q)
Frente
Cola
Colas Circulares usando Arreglos: Remoción
int remueveCola(ColaCircular * q) {if (!estaVacia(q)) {
q->frente = q->frente%N; return q->elementos[q->frente++];
} else {cout << "Error, Cola vacía" << endl;return ERROR;
}}
MAX + 1D
C
B3) Frente2
Remove(q)Cola
Elemento removido: A
1) Frente
12,3
Pasos básicos:0) Verifica que no esté vacía1) Determina la posición correcta de Frente2) Guarda el elemento a retornar3) Incrementa frente
MAX + 1DCBA
Cola
Frente
Colas Circulares usando Arreglos: Inserciónvoid insertaCola(ColaCircular * q, int x) {
if (!estaLlena(q)) {q->elementos[q->cola++] = x;q->cola = q->cola % N;
} else {Cout << "Error, Cola llena" << endl;return;
}}
FDCB
Frente
Insert(q,F)
b) Cola
1) ColaMAX + 1D
C
B
Cola
Frente
1, 23
Pasos básicos:0) Verifica que no esté llena1) Inserta en la posición de cola 2) Incrementa el valor de cola3) Determina la posición correcta de cola
2) Cola
3) Cola
Doble Cola: BicolaCola bidimensional en la que las
inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la cola. ◦ Cola doble con entrada restringida: Acepta
inserciones solo al final de la cola◦ Cola doble con salida restringida: Acepta
eliminaciones solo al inicio de la cola
A diferencia de una cola sencilla, debe haber dos métodos para leer y dos para escribir para considerar el frente y la parte posterior
Podemos utilizar un contador para el número de elementos
Doble Cola: Operaciones
Cola Frente
insertaAtras(q,A)
A FrenteCola
insertaAtras(q,B)
B
A Frente
Cola
B
A
C
Cola
Frente
insertaFrente(q,C)
B
A
C
D Frente
Cola
insertaFrente(q,D)
B
A
C
D
E Frente
Cola llena!
insertaFrente(q,E)
Inicio:
Numelems = MAX
Doble Cola: OperacionesB
A
D
C
E Frente
Numelems = MAX B
A
D
C
Frente
Cola
RemueveFrente(q)
Copia B
A
D
C Frente
Cola
Frente
Cola
RemueveAtras(q)
A
D
C Frente
ColaB
A
D
C
struct Bicola {int nelems;int frente;int cola;int elementos[MAXQUEUE];
};
int empty() { return items == 0; }
Bicola q;
q.nelems = 0;q.frente = 0;q.cola = 0;
Doble Cola: Operaciones
Frente A FrenteCola
insertaAtras(q,B)
B
A Frente
Cola
Doble Cola: Operaciones
void insertaAtras(Bicola * q, int x){ if (q->nelems == MAXQUEUE){ cout<<"Error, cola llena"; exit(1); } q->elementos[q->cola] = x; q->nelems ++; q->cola ++;}
void insertaFrente(Bicola * q, int x){if (q->nelems == MAXQUEUE){
cout<<"Error, cola llena"; exit(1);}
mueveBicolaUp(q); q->elementos[q->frente] = x; q->nelems ++; q->cola ++; }
B
A
C
Cola
Frente
insertaFrente(q,C)
B
A Frente
Cola
Doble Cola: Operaciones
int remueveFrente(Bicola * q){ int d; if ( empty() ) return t_error; q->nelems --; q-> cola --; d = q->elementos[q->frente]; mueveBicolaDown(q); return d;}
Doble Cola: OperacionesB
A
D
C
E Frente
Numelems = MAX
B
A
D
C
Frente
Cola
RemueveFrente(q)
B
A
D
C Frente
Cola
int remueveAtras(Bicola * q){ if ( empty() ) return t_error; q->nelems --; return q->elementos[-- q->cola];}
Doble Cola: Operaciones
B
A
D
C Frente
Cola
RemueveAtras(q)
A
D
C
Cola
Frente
Aplicaciones de ColasEn Ciencias Computacionales,
Investigación de Operaciones, y muchas otras áreas donde datos son almacenados para ser procesados posteriormente, ejecutando una función de buffer (e.g., inventarios, threads, simulación, manufactura, etc).