3 Tablas o matrices
3.1. Concepto
Las tablas corresponden al concepto matemático de matriz.
Todos sus elementos deben ser del mismo tipo y se accede
a ellos por su posición.
La tabla siguiente es unidimensional, i.e., un vector.
a = [2, 4, 5, 6, 7]
Su primer elemento a[0] es 2, su segundo elemento es 4.
La siguiente tabla es bidimensional, i.e., una matriz.
b:=
2
4 5
3
1
7
Para acceder a sus
elementos se usa la
notación b[1][2] que
corresponde a 7.
1
3.2. Declaración
a = [2, 4, 5, 6, 7]
b=
2 4 5
3 1 7
En C las tablas se especifican de la siguiente forma:
double c[6];
int a[5] = {2, 4, 5, 6, 7};
double m[4][5];
int b[2][3] = {{2, 4, 5}, {3, 1, 7}};
2
Se pueden definir nuevos tipos de variables a partir de la
especificación de las tablas. La definición de estos tipos
se hace del modo siguiente:
typedef char palabra[25];
typedef int tablero_ajedrez[8][8];
Una vez definido un nuevo tipo se puede utilizar como cualquier otro tipo predefinido en la declaración de variables.
palabra nombre;
tablero_ajedrez mi_tablero;
3
Cadenas de caracteres
Una cadena de caracteres (string) es un vector de caracteres.
Las cadenas de caracteres literales se encierran entre comillas (e.g., “Hola”).
Cuando consideramos una palabra como una cadena de caracteres hay que tener en cuenta que las longitudes de las palabras varían. Por este motivo, se coloca un centinela al final
de cada palabra de manera que podamos saber donde termina la información relevante de la cadena de caracteres.
El centinela por defecto es el carácter nulo ‘\0’. Este carácter
se añade por defecto en las asignaciones.
char p[25]; p = “Hola”;
[H, o, l, a, nulo, , , , , … , , ]
1 2 3 4 5
6 7 8 9 … 24 25
4
3.3. Inicialización, Acceso y Modificación
Inicialización: Cuando se crea una tabla hay que dar valores
iniciales a todos sus componentes. Estos valores pueden
asignarse directamente o leerse mediante instrucciones de
entrada.
#define N 10
int main(void) {
double t[3] = {2.3, 4.5, 6.7}; // inicialización
char a[N];
int b[2][3];
a[0] = ‘c’;
// inicialización
cin >> b[1][0]; // inicialización
cout << a[0]; // acceso
b[1][0] = 3;
// modificación
}
5
3.4. Esquema de recorrido
El esquema de recorrido para vectores y matrices es similar.
La diferencia estriba en que en el caso de las matrices hay
que iterar sobre filas y columnas.
inicializar el tratamiento del vector
for (i=0; i<N; i++) {
tratar el i-esimo elemento del vector
}
tratamiento final
6
Ejemplo 1 Calcular el producto escalar de dos vectores usando acciones y
funciones.
7
Ejemplo 2 Calcular el máximo de un vector usando acciones y funciones.
8
Ejemplo 3 Un algoritmo que lee una secuencia de enteros positivos acabada en 0,
los almacena en un vector v e informa del número de enteros positivos que
contiene la secuencia.
9
Ejemplo Método de ordenación por selección. Se coloca en primera posición el
mínimo elemento del vector, en segunda posición en segundo menor elemento, y así
sucesivamente.
void ordenacion_seleccion(int n, int t[LongTabla]) {
int i, j, posicion_minimo;
for (i=0; i<n-1; i++) {
// Se busca la posición del mínimo elemento
// a partir de la posición i y se almacena en la
// variable posicion_minimo.
posicion_minimo=i;
for (j=i+1; j<n; j++) {
if (t[j] < t[posicion_minimo]) posicion_minimo=j;
}
// Se intercambia el elemento de la posición i por el mínimo
// elemento del vector a partir de la posición i.
intercambia(t[i],t[posicion_minimo]);
}
}
void intercambia (int& n, int& m) { int aux; aux=n; n=m; m=aux; }
10
3.4. Esquema de recorrido
inicializar el tratamiento de la matriz
for (i=0; i<N; i++) {
inicializar el tratamiento de la fila i (opcional)
for (j=0; j<M; j++) {
tratar el [i][j]-esimo elemento de la matriz
}
tratamiento final de la fila i (opcional)
}
tratamiento final
11
Ejemplo 4 Calcular la transpuesta de una matriz.
Si a es una matriz m x n, la transpuesta at de a es una matriz n x m cuyos elementos
son de la forma siguiente:
at[i,j] = a[j,i]
Por ejemplo
a11 a12 a13
si a = a21 a22 a23
b11 b12
b21 b22
entonces la transpuesta de a es b31 b32
donde
b11 = a11
b21 = a12
b31 = a13
b12 = a21
b22 = a22
b32 = a23
12
3.5. Esquema de búsqueda
El esquema de búsqueda para vectores y matrices es similar.
La diferencia es que en el caso de las matrices hay que
iterar sobre filas y columnas.
inicializar el tratamiento
encontrado = false; i = 0;
while (i < N && ! encontrado) {
if ( propiedad_búsqueda(a[i]) )
encontrado = true;
else
i++;
}
tratamiento final
13
Ejemplo 5 Busca número igual a la suma de los anteriores.
14
Ejemplo 6 Leer dos palabras y determinar cuál es menor en orden alfabético
usando acciones y funciones.
15
Ejemplo Búsqueda binaria o dicotómica de un número en un vector ordenado
crecientemente.
void busca_dic(int e, int n, int t[LongTabla], bool& encontrado, int& posicion) {
int inf=0, sup=n-1, k;
while (inf != sup) {
k=(inf+sup)/2;
if (t[k] <e) inf=k+1; else sup=k;
}
if (t[inf] == e) encontrado=true;
if (encontrado) posicion=inf; else posicion=-1;
}
16
inicializar el tratamiento
encontrado := false ;
i = 0;
while (i < N && ! encontrado) {
j = 0;
while (j < N && ! encontrado) {
if ( propiedad_búsqueda(b[i][j]) )
encontrado := true;
else
j++;
}
i++;
}
tratamiento final
17
Ejercicio 1 Invertir el orden de los elementos de un vector.
18
Ejercicio 2 Calcular la posición del máximo de un vector e intercambiar el
máximo con el primer elemento del vector
19
Ejercicio 3 Búsqueda de la posición de un número en un vector. Si el número no
aparece en el vector devuelve -1.
20
Ejercicio 4 Calcular la posición del mínimo elemento de una matriz a partir de una
fila y de una columna dadas.
21
Ejercicio 5 Ordenar una matriz intercambiado el elemento de la fila f y la columna
c con el mínimo elemento de dicha matriz a partir de la fila f y de la columna c.
22
Ejercicio 6 Calcular el producto de dos matrices.
Si a es una matriz m x n y b es una matriz n x p, entonces el producto de ambas
matrices a * b es una matriz c m x p cuyos elementos son
n
c[i,j] = k=1 a[i,k] * b[k,j]
Por ejemplo
b11 b12
a11 a12 a13 * b21 b22 = c11 c12
a21 a22 a23
b31 b32
c21 c22
donde
c11 = a11b11 + a12b21 + a13b31
c21 = a21b11 + a22b21 + a23b31
c12 = a11b12 + a12b22 + a13b32
c22 = a21b12 + a22b22 + a23b32
23
Ejercicio 7 Comprobar si una matriz es simétrica.
Una matriz es simétrica si es igual a su transpuesta.
Consideramos la siguiente matriz 3x3
a11 a12 a13
a21 a22 a23
a31 a32 a33
su transpuesta es
a11 a21 a31
a12 a22 a32
a13 a23 a33
Para ver si es simétrica hay que comprobar que a[i,j]=a[j,i] para todo i, j. Pero como
a[j,i]=a[i,j] si a[i,j]=a[j,i], basta comprobar estas igualdades para los elementos de la
mitad superior o de la mitad inferior de la matriz.
24
Ejercicio 8 Comprobar si una matriz cuadrada NxN es triangular
superior.
Ejercicio 9 Comprobar si una matriz cuadrada NxN es diagonal.
Ejercicio 10 Comprobar si una matriz cuadrada NxN es un cuadrado
mágico. Esto es, la suma de los elementos de cada fila es igual a S, la
suma de los elementos de cada columna es igual a S, y la suma de los
elementos de cada diagonal es igual a S.
25
Descargar

Informatica Basica