Estructura de Datos En C++
description
Transcript of Estructura de Datos En C++
![Page 1: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/1.jpg)
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
![Page 2: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/2.jpg)
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
![Page 3: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/3.jpg)
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
![Page 4: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/4.jpg)
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
![Page 5: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/5.jpg)
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
![Page 6: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/6.jpg)
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
![Page 7: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/7.jpg)
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
![Page 8: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/8.jpg)
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
![Page 9: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/9.jpg)
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
![Page 10: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/10.jpg)
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
![Page 11: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/11.jpg)
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
![Page 12: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/12.jpg)
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
![Page 13: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/13.jpg)
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
![Page 14: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/14.jpg)
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
![Page 15: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/15.jpg)
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
![Page 16: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/16.jpg)
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
![Page 17: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/17.jpg)
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
![Page 18: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/18.jpg)
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
![Page 19: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/19.jpg)
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 ++;}
![Page 20: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/20.jpg)
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
![Page 21: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/21.jpg)
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
![Page 22: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/22.jpg)
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
![Page 23: Estructura de Datos En C++](https://reader036.fdocumento.com/reader036/viewer/2022062301/56815efa550346895dcdb7ba/html5/thumbnails/23.jpg)
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).