0
Ejemplos capítulo 12
Ejemplo 12.1
Vamos a realizar un pequeño programa para trabajar con punteros.
Este ejemplo consiste en invertir el orden de los elementos de un vector de enteros, usando sólo puntetos, sin variables auxiliares enteras.
Para ello recorreremos el vector empezando por los dos extremos, e intercambiando cada par de elementos:
|
// Programa que invierte el orden de un vector
// Octubre de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;
void Mostrar(int*, int);
void Intercambia(int*, int*);
int main() {
int vector[10] = { 2,5,6,7,9,12,35,67,88,99 };
int *p, *q;
Mostrar(vector, 10); // Mostrar estado inicial
p = vector; // Primer elemento
q = &vector[9]; // Ultimo elemento
while(p < q) { // Bucle de intercambio
Intercambia(p++, q--);
}
Mostrar(vector, 10); // Mostrar estado final
return 0;
}
void Mostrar(int *v, int n) {
int *f = &v[n]; // Puntero a posición siguiente al último elemento
while(v < f) {
cout << *v << " ";
v++;
}
cout << endl;
}
void Intercambia(int *p, int *q) {
// Intercambiar sin usar variables auxiliares:
*p += *q;
*q = *p-*q;
*p -= *q;
} |
Ejecutar este código en codepad.
Probablemente parezca que nos hemos complicado la vida, pero se trata de un ejercicio.
Comentemos algunos detalles de este programa.
Primero, el bucle de intercambio. Hemos usado una única sentencia while. Como condición hemos usado la comparación de los dos punteros. Esto hace que el puntero p recorra la primera mitad del vector, empezando por el principio, y que q recorra la otra mitad, empezando por el final. El bucle se reperirá hasta que ambos punteros sean iguales, o hasta que se crucen. Si ambos punteros son iguales (esto sólo sucederá si el número de elementos es impar), los dos apuntarán al elemento central del vector, y no se producirá intercambio, lo cual no es un problema, ya que no hay nada que intercambiar.
La sentencia del bucle Intercambia(p++, q--); intercambiará los elementos apuntados por p y q, y posteriormente, incrementará p y decrementará q.
Hemos diseñado dos funciones auxiliares.
La primera Mostrar muestra el número de valores indicado en el segundo parámetro del vector suministrado mediante el primer parámetro.
He querido evitar, también en este caso, el uso de variables auxiliares de tipo int, aunque he decidido hacerlo usando un puntero auxiliar, que apunte a la dirección de un hipotético elemento n+1 del vector.
Podríamos habernos aprovechado de que los parámetros se pasan por valor, y usar el parámetro n como contador:
|
void Mostrar(int *v, int n) {
while(n--) {
cout << *v << " ";
v++;
}
cout << endl;
} |
Aunque este código tiene un problema potencial, si el valor inicial de n es cero o negativo el bucle no termina.
Podemos arreglar esto añadiendo una verificación inicial:
|
void Mostrar(int *v, int n) {
if(n > 0) {
while(n--) {
cout << *v << " ";
v++;
}
}
cout << endl;
} |
La segunda función, Intercambia, como su nombre indica, intercambia los elementos del vector apuntados por los dos punteros pasados como parámetros.
También en este caso, y aprovechando que se trata de un vector de enteros, he querido evitar usar variables auxiliares. El truco consiste en mantener la información haciendo sumas y restas. Suponiendo que queremos intercambiar los valores n y m:
Sumamos los dos valores y guardamos el resultado en el primero. n=n+m
El nuevo valor de m es el resultado de restar del valor actual de n, el valor de m. Como n ahora contiene (n+m), el resultado será n+m-m = n. m=n-m
Por último, obtenemos el valor final de n restando de su valor actual (n+m) el valor actual de m (que es el valor original de n). n = n-m
Veamos un ejemplo:
| N = 10, M = 3
1) N = N+M = 10+3 = 13 [N=13, M=3]
2) M = N-M = 13-3 = 10 [N=13, M=10]
3) N = N-M = 13-10 = 3 [N=3, M=10]
|
Esto sólo funciona con vectores de enteros. Con float podemos perder precisión en algunas operaciones, y con otros tipos, como estructuras o uniones, ni siquiera tiene sentido.
Ejemplo 12.2
Este ejemplo consiste en mezclar dos vectores ordenados en otro, de modo que también esté ordenado, como en el caso anterior usaremos sólo puntetos, sin variables auxiliares enteras.
Para ello recorreremos los dos vectores de entrada, empezando por el principio, e insertaremos el valor menor de cada uno, y tomaremos el siguiente:
|
// Programa que funde dos vectores ordenados
// Octubre de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;
void Mostrar(int*, int);
int main() {
int vector1[10] = { 3, 4, 6, 9, 12, 15, 17, 19, 22, 24 };
int vector2[10] = { 1, 5, 8, 11, 13, 14, 21, 23, 25, 30 };
int vectorR[20];
int *p, *q, *r;
int *u1, *u2;
p = vector1;
q = vector2;
r = vectorR;
u1 = &vector1[9];
u2 = &vector2[9];
cout << "Vectores de entrada:" << endl;
Mostrar(vector1, 10);
Mostrar(vector2, 10);
while(p <= u1 && q <= u2) {
if(*p < *q) { *r++ = *p++; }
else { *r++ = *q++; }
}
// Llegados a este punto, quedarán elementos por
// copiar en uno de los vectores, así que hay
// que copiarlos incondicionalmente:
while(p <= u1) {
*r++ = *p++;
}
while(q <= u2) {
*r++ = *q++;
}
cout << "Resultado:" << endl;
Mostrar(vectorR, 20);
return 0;
}
void Mostrar(int *v, int n) {
int *f = &v[n]; // Puntero a posición siguiente al último elemento
while(v < f) {
cout << *v << " ";
v++;
}
cout << endl;
}
|
Ejecutar este código en codepad.
Hemos usado sólo punteros porque lo exige el enunciado, pero hubiera sido más lógico usar un índice parar recorrer los vectores de entrada.
Sin embargo, este método simplifica los movimientos de elementos entre los vectores de entrada y el de salida. En las expresiones del tipo *r++ = *p++; se evalúa primero la asignación, y después se incrementan los punteros, de modo que todo queda preparado para la siguiente iteración.
Ejemplo 12.3
Implementaremos ahora otro método de ordenación, que generalmente se usa con ficheros de disco secuenciales, pero que también se puede aplicar a vectores.
Nos centraremos ahora en el algoritmo de mezcla natural. Dada una lista de valores, en principio desordenada, este algoritmo consiste en copiar las secuencias ordenadas a otras listas, y después aplicar el método usado en el ejercicio anterior para obtener una lista más ordenada que la original.
El proceso se repite hasta que sólo hay una secuencia en la lista.
Este método se puede usar con tantas listas auxiliares como se quiera, dos o más. Cuantas más listas auxiliares se usen, más rápidamente se ordenará la lista. El problema es que para cada nueva lista auxiliar se incrementa la cantidad de memoria necesaria, y sobre todo, la complejidad del programa.
Implementaremos este algoritmo con dos vectores auxiliares.
Pero veamos un ejemplo. Partamos del siguiente vector:
34 33 23 3 54 21 1 99 12 32 51 64
La primera etapa consiste en copiar elementos a los vectores auxiliares, alternando cada vez que se rompa una secuencia ordenada. En este caso, los dos vectores de salida quedarán:
34 23 21 12 32 51 64
33 3 54 1 99
A continuación, mezclamos los dos vectores, usando un algoritmo parecido al del ejemplo anterior. La diferencia es que nuestros vectores no están ordenados, y por lo tanto, las mezclas serán de subconjuntos de esos vectores:
33 34 3 23 21 54 1 12 32 51 64 99
Repetimos el proceso:
33 34 21 54
3 23 1 12 32 51 64 99
Y volvemos a mezclar:
3 23 33 34 1 12 21 32 51 54 64 99
Volvemos a repetir el proceso:
3 23 33 34
1 12 21 32 51 54 64 99
Y mezclamos otra vez:
1 3 12 21 23 32 33 34 51 54 64 99
Y la lista queda ordenada.
Tenemos que buscar una condición para detectar el final del proceso. Lo más sencillo es contar el número de secuencias ordenadas durante el proceso de mezcla. Si hay más de una, hay que repetir el proceso.
Sobre el papel es muy sencillo, pero no será tan fácil implementarlo. Veremos que necesitaremos un montón de variables auxiliares.
El proceso de separar los vectores es relativamente simple, pero veremos que mezclar los vectores resultantes no es tan sencillo, ya que sólo están parcialmente ordenados, y hay que mezclar cada par de fragmentos por separado.
Para cada vector auxiliar necesitamos tres punteros. Uno lo usaremos para recordar la dirección de inicio. Esto nos permitirá "rebobinar" el vector cada vez que tengamos que empezar a procesarlo y liberar su memoria cuando terminemos el trabajo. El segundo puntero lo usaremos para llenar el vector en el proceso de separar los fragmentos ordenados. Una vez terminado ese proceso, el puntero se usará para saber cuantos elementos contiene y para comparaciones cuando lo recorramos. El último puntero lo usaremos para recorrer el vector en la etapa de fusión de los vectores auxiliares.
El proceso de separar responde a este algoritmo:
|
Activar la lista 1 como salida.
Tomar el primer elemento del vector y copiarlo a la lista activa.
Bucle: Mientras no se alcance el final de la lista
Si el siguiente elemento del vector es menor que el último copiado (el último de la lista activa), cambiar de lista activa.
Copiar el siguiente elemento del vector a la lista activa.
fin del bucle |
El proceso de mezcla responde a este otro algoritmo:
|
Iniciar punteros: colocar cada uno al principio de una lista.
Contador de tramos <- cero
Empezamos un tramo nuevo <- verdadero
Bucle: Mientras queden elementos en alguna de las listas auxiliares
CASO A: Empezamos un tramo nuevo
Pasar a la lista de salida el menor de los elementos actuales de cada lista auxiliar
Incrementar el número de tramos
Empezamos un tramo nuevo <- falso
CASO B: La lista auxiliar 1 está vacía
Para cada uno de los elementos restantes de la lista 2
Si el elemento a copiar es menor que el último de la salida: incrementar tramos
Copiar elemento a lista de salida
CASO C: la lista auxiliar 2 está vacía
Para cada uno de los elementos restantes de la lista 1
Si el elemento a copiar es menor que el último de la salida: incrementar tramos
Copiar elemento a lista de salida
CASO D: El primer elemento de cada lista auxiliar es mayor al último de la de salida
Copiar el elemento de la lista auxiliar que contenga el menor
CASO E: El primer elemento de la lista 1 es mayor que el último de la de salida,
el primero de la lista 2 es menor
Copiar el resto del tramo de la lista 1. Hasta que se encuentre un elemento menor que el último copiado.
CASO F: El primer elemento de la lista 2 es mayor que el último de la de salida,
el primero de la lista 1 es menor
Copiar el resto del tramo de la lista 2. Hasta que se encuentre un elemento menor que el último copiado.
CASO G: El primer elemento de cada lista auxiliar es menor que el último de la salida. Tramos agotados.
Empezamos nuevo tramo <- verdadero
Cerrar el bucle |
Hemos tenido en cuenta todos los casos posibles. El caso A se dará cuando empecemos el proceso de fusión, y también cuando terminemos de fundir cada uno de las parejas de tramos.
Los casos B y C se darán cuando una de las listas termine, y queden elementos en la otra. Podríamos pensar que esto sólo va a suceder cuando termine la segunda, ya que el número de tramos será igual en ambas listas o habrá uno más en la primera que en la segunda. Sin embargo, cuando el número de tramos sea igual en ambas listas, puede que se termine de copiar primero los de la primera lista, quedando elementos por copiar en la segunda.
El D es el caso general, cuando quedan elementos en los fragmentos de las dos listas auxiliares. Se transfiere el menor de los dos.
Los casos E y F se dan cuando uno de los fragmentos se ha terminado, y se deben transferir los elementos que queden en el otro fragmento.
Finalmente, el caso G se da cuando los dos fragmentos se ha agotado. En ese caso comenzamos un nuevo tramo en la lista de salida. Si queda algún fragmento en alguna de las listas, volveremos a estar en el caso A, si no, habremos terminado.
La implementación es la siguiente:
|
// Ordenar usando el método de mezcla natural
// Octubre de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;
void Mostrar(int*, int);
int MezclaNatural(int*, int);
int main() {
int vector[12] = { 34, 33, 23, 3, 54, 21, 1, 99, 12, 32, 51, 64 };
cout << "Vector inicial:" << endl;
Mostrar(vector, 12);
while(MezclaNatural(vector, 12) > 1);
cout << "Vector final:" << endl;
Mostrar(vector, 12);
return 0;
}
void Mostrar(int *v, int n) {
int *f = &v[n]; // Puntero a posición siguiente al último elemento
while(v < f) {
cout << *v << " ";
v++;
}
cout << endl;
}
int MezclaNatural(int *v, int n) {
int *aux[2];
int *iaux[2];
int *iaux2[2];
int *i, *f;
int activa=0; // Activamos el primer vector auxiliar
int tramo;
bool tramonuevo;
aux[0] = iaux[0] = new int[12];
aux[1] = iaux[1] = new int[12];
i = v;
f = &v[n];
// El primer elemento se copia siempre al primer vector:
*iaux[activa]++ = *i++;
// Separar vector en auxiliares:
while(i < f) {
if(*i < *(i-1)) activa++;
if(activa >=2) activa -= 2;
*iaux[activa]++ = *i++;
}
// Fundir vectores auxiliares:
iaux2[0] = aux[0];
iaux2[1] = aux[1];
i = v;
tramo = 0;
tramonuevo = true;
while(iaux2[0] < iaux[0] || iaux2[1] < iaux[1]) {
if(tramonuevo) { // caso A
// El primer elemento lo añadimos directamente:
if(*iaux2[0] < *iaux2[1]) { *i++ = *iaux2[0]++; }
else { *i++ = *iaux2[1]++; }
tramo++;
tramonuevo = false;
} else // caso B
if(iaux2[0] == iaux[0]) {
while(iaux2[1] < iaux[1]) {
if(*iaux2[1] < i[-1]) tramo++;
*i++ = *iaux2[1]++;
}
} else // caso C
if(iaux2[1] == iaux[1]) {
while(iaux2[0] < iaux[0]) {
if(*iaux2[0] < i[-1]) tramo++;
*i++ = *iaux2[0]++;
}
} else // caso D
if(*iaux2[0] > i[-1] && *iaux2[1] > i[-1]) {
if(*iaux2[0] < *iaux2[1]) { *i++ = *iaux2[0]++; }
else { *i++ = *iaux2[1]++; }
} else // caso E
if(*iaux2[0] > i[-1])
while(iaux2[0] < iaux[0] && *iaux2[0] > i[-1]) {
*i++ = *iaux2[0]++;
}
else // caso F
if(*iaux2[1] > i[-1])
while(iaux2[1] < iaux[1] && *iaux2[1] > i[-1]) {
*i++ = *iaux2[1]++;
}
else { // caso G
tramonuevo = true;
}
}
delete[] aux[1];
delete[] aux[0];
return tramo;
}
|
Ejecutar este código en codepad.
Comentarios