Ingenieria de software

A.- ALGORÍTMICA
________________________________________
I.- Representación y manipulación de datos
Sugerencias bibliográficas: [CORL90], [KNUD73], [KNUD73a], [MAGM90], [SEDR95], [WEIM95], [WIRN87]
1. Taxonomía de las estructuras de datos
• Apuntadores (R, E, RP)
¿Qué son los apuntadores? Los apuntadores no tienen nada que ver con el texto en sí. Un apuntador es sencillamente unareferencia a algo. Todos utilizamos apuntadores en la vida diaria sin siquiera notarlo.
Cuando buscamos en un libro un tema que nos interesa, buscamos en el índice para saber en qué página está lo que queremos, eso es un apuntador.
Ejemplo:
Roms de computadora ............................ Página 55.
Esta es una manera muy simple de explicar lo que es un apuntador, pero su funcionamiento esbásicamente el mismo, en los ROMS. Los apuntadores le dicen al ROM donde debe empezar a leer una cadena de caracteres, es así como sabe que frase debe escribir en cada parte del juego.
Ejemplo:
Código máquina: Explicación:
float V1[16], V2[16], Res;
void main()
{ VectProd(16, V1, V2, &Res); exit(0); }
void VectProd(int length, float *A, float *B, float *C)
{
float tmp=0.0;
for (;length;length--, A++, B++)
tmp= tmp + (*A) * (*B);
*C = tmp;
} La rutina VectProd tiene 4 parámetros,
length, que indica el número de elementos
de cada vector de entrada, A y B
que son los apuntadores a cada uno de los
vectores de entrada, y C, que es el apuntador
a la variable donde se ha de copiar el resultado.

• Vectores, matrices, cubos, hipercubos (R, E, RP)
En muchos casos cuandose define un array, hay una tendencia a confundir la estructura de datos con su representación en memoria. En principio esta confusión no debería darse, pues como ya se ha comentado en el anterior tema, se trata de dos conceptos que representan diferentes niveles de abstracción de los datos. Por lo tanto, hay que dejar claro que un array NO es un conjunto de localizaciones consecutivas en memoria.Es cierto que muchas veces ésta es su representación, pero no siempre tiene porque ser asi. Consultado desde www.masapuntes.com
Intuitivamente, se puede definir un array como un conjunto de pares (indice, valor). De manera que, para cada indice definido como válido puede existir un valor (dato) asociado, siendo todos los valores del mismo tipo.
En los arrays hay definidas dos operacionesbásicas: recuperar y almacenar información. Las operaciones que se pudiesen realizar individualmente sobre cada uno de los elementos de la estructura carecen de sentido globalmente.
Por ejemplo, si un array es unidimensional (solo tiene un índice para acceder a un valor), todos los elementos estan almacenados consecutivamente en memoria y cada uno de ellos ocupa un cierto numero de bytes (p), entoncesbasta conocer la direccion donde comienza a almacenarse la estructura (d(0)) para poder calcular la dirección donde reside cualquier componente en función del índice que tiene asociado (d(i)). La expresión quedaría así:
d(i) = d(0)+ (i-1)* p
En el caso multidimensional más simple, denominado tabla o matriz, en el que se tienen 2 índices, la solución suele consistir en almacenar los elementosorganizados por filas, es decir, primero todos los elementos en los que el primer indice coincide y tiene el valor del primer indice válido, estos elementos estan organizados como un array unidimensional como vemos, a continuación se almacenan los elementos para los que el primer índice tiene el segundo valor válido y así sucesivamente. De manera que en este caso, suponiendo una matriz con mfilas y n columnas, la expresión que permite acceder a la dirección de un elemento de la estructura mediante dos índices sería:
d(i,j) = d(0) + (i-1)*n*p + (j-1)*p
(array m x n)
Veamos ahora un resumen de las operaciones y axiomas que caracterizan la manipulación de un array usando un vector.
Operaciones:
Crear( ) --------> vector
Almacenar (vector, indice, valor) --------> vector...