Guia De Examen Programacion Avanzada

GUIA EXAMEN FINAL MAYO2012

1. Apuntadores. Relación entre apuntadores y arreglos

Un apuntador es una variable que contiene la dirección en memoria de otra variable. Se pueden tener apuntadores a cualquier tipo de variable. Ej: int *apuntador;

Los arreglos son una colección de variables del mismo tipo que se referencian utilizando un nombre común. Un arreglo consta de posiciones de memoria contigua. La dirección más baja corresponde al primer elemento y la más alta al último. Un arreglo puede tener una o varias dimensiones. Para acceder a un elemento en particular de un arreglo se usa un índice. El formato para declarar un arreglo unidimensional es: int listanum[10];

Existe una relación estrecha entre los punteros y los arreglos. En C, un nombre de un arreglo es un índice a la dirección de comienzo del arreglo. En esencia, el nombre de un arreglo es un puntero al arreglo. Considerar lo siguiente:

int a[10], x;

int *ap;

ap = &a[0]; /* ap apunta a la direccion de a[0] */

x = *ap; /* A x se le asigna el contenido de ap (a[0] en este caso) */

*(ap + 1) = 100; /* Se asigna al segundo elemento de 'a' el valor 100 usando ap*/

Como se puede observar en el ejemplo la sentencia a[t] es idéntica a ap+t. Se debe tener cuidado ya que C no hace una revisión de los límites del arreglo, por lo que se puede ir fácilmente más alla del arreglo en memoria y sobreescribir otras cosas.

C sin embargo es mucho más sútil en su relación entre arreglos y apuntadores. Por ejemplo se puede teclear solamente:

ap = a; en vez de ap = &a[0]; y también *(a + i) en vez de a[i], esto es, &a[i] es equivalente con a+i.

Y como se ve en el ejemplo, el direccionamiento de apuntadores se puede expresar como:

a[i] que es equivalente a *(ap + i)

Sin embargo los apuntadores y los arreglos son diferentes:

Un apuntador es una variable. Se puede hacer ap = a y ap++.

Un arreglo NO ES una variable. Hacer a = ap y a++ ES ILEGAL.

Esta parte es muy importante, asegúrese haberla entendido.

Con lo comentado se puede entender como los arreglos son pasados a las funciones. Cuando un arreglo es pasado a una función lo que en realidad se le esta pasando es la localidad de su elemento inicial en memoria.

2. Intercambio de datos mediante función swap (con apuntadores)

Hay muchos casos que se quiere alterar el argumento pasado a la función y recibir el nuevo valor una vez que la función ha terminado. Para hacer lo anterior se debe usar una llamada por referencia, en C se puede simular pasando un puntero al argumento. Con esto se provoca que la computadora pase la dirección del argumento a la función.

Para entender mejor lo anterior consideremos la función swap() que intercambia el valor de dos argumentos enteros:

void swap(int *px, int *py);

main()

{

int x, y;

x = 10;

y = 20;

printf("x=%d\ty=%d\n",x,y);

swap(&x, &y);

printf("x=%d\ty=%d\n",x,y);

}

void swap(int *px, int *py)

{

int temp;

temp = *px; /* guarda el valor de la direccion x */

*px = *py; /* pone y en x */

*py = temp; /* pone x en y */

}

3. Busqueda lineal. Complejidad del algoritmo O(n) // que tanto tarda el algoritmo en ejecutarse

La búsqueda lineal probablemente es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado. Entonces este algoritmo tiene una complejidad de O(n).

4. Ordenamiento burbuja. Complejidad del algoritmo (O(n²)

El método de ordenación por burbuja es el más conocido y popular entre estudiantes y aprendices

de programación, por su facilidad de comprensión y programación; por el contrario, es el menos

eficiente y por ello, normalmente, se aprende su técnica pero no suele utilizarse.

La técnica utilizada se denomina ordenación por burbuja u ordenación por hundimiento debido

a que los valores más pequeños «burbujean» gradualmente (suben) hacia la cima o parte superior

del array de modo similar a como suben las burbujas en el agua, mientras que los valores mayores

se hunden en la parte inferior del array. La técnica consiste en hacer varias pasadas a través del

array. En cada pasada, se comparan parejas sucesivas de elementos. Si una pareja está en orden

creciente (o los valores son idénticos), se dejan los valores como están. Si una pareja está en orden

decreciente, sus valores se intercambian en el array.

¿Cuál es la eficiencia del algoritmo de ordenación de la burbuja? Dependerá de la versión utilizada.

En la versión más simple se hacen n − 1 pasadas y n − 1 comparaciones en cada pasada. Por

consiguiente, el número de comparaciones es (n − 1) * (n − 1) = n2 − 2n + 1, es decir, la complejidad

es 0(n2).

Si se tienen en cuenta las versiones mejoradas haciendo uso de las variables interruptor o

indiceIntercambio, entonces se tendrá una eficiencia diferente

...