Vectores
Páginas: 5 (1040 palabras)
Publicado: 2 de junio de 2015
Vectores y matrices
Declaración
Vector (array unidimiensional):
[];
Tipo de dato de los elementos del vector
Identificador de la variable.
Número de elementos del vector.
ü Puede ser un literal o una constante de tipo entero.
û Nunca será una variable
Matriz (array bidimensional):
[][];
Acceso
- En C, el índice de la primera componente de un vector es siempre 0.
- El índice de la última componente es-1
Vector
[<índice>]
Matriz
[<índice1>][<índice2>]
Inicialización
En la declaración, podemos asignarle un valor inicial a los elementos de un vector.
int vector[3] = {4, 5, 6};
int matriz[2][3] = { {1,2,3}, {4,5,6} };
Elcompilador puede deducir las dimensiones del array:
int vector[] = {1, 2, 3, 5, 7};
Manipulación de vectores y matrices
Las operaciones se realizan componente a componente
No es necesario utilizar todos los elementos del vector, por lo que, en C, al trabajar
con ellos, se suele utilizar una variable entera adicional que nos indique el número
de datos utilizados.
float media (float datos[], int N)
{
inti;
float suma = 0;
for (i=0; i
return suma/N;
}
IMPORTANTE: Cuando se pasa un vector como parámetro, el paso de parámetros
es por referencia (un vector es, en realidad, un puntero en C). Por tanto, tenemos
que tener cuidado con los efectos colaterales que se producen si, dentro de un
módulo, modificamos un vector que recibimos como parámetro.
Algoritmos deordenación
Ordenación por selección
void OrdenarSeleccion (double v[], int N)
{
int i, j, pos_min;
double tmp;
for (i=0; i
pos_min = i;
for (j=i+1; j
// Coloca el mínimo en v[i]
tmp = v[i];
v[i] = v[pos_min];
v[pos_min] = tmp; =
}
}
En cada iteración, se selecciona el menor elemento del subvector no ordenado yse intercambia con el primer elemento de este subvector.
Ordenación por inserción
void OrdenarInsercion (double v[], int N)
{
int i, j;
double tmp;
for (i=1; i
for (j=i; (j>0) && (tmp
v[j] = tmp;
}
}
En cada iteración, se inserta un elemento del subvector no ordenado en la posición
correcta dentro del subvector ordenado.
Ordenación porintercambio directo (método de la burbuja)
void OrdenarBurbuja (double v[], int N)
{
int i, j;
double tmp;
for (i=1; i
if (v[j] < v[j-1]) {
tmp = v[j];
v[j] = v[j-1];
v[j-1] = tmp;
}
}
En cada iteración
Estado del vector
tras cada iteración:
Ordenación rápida (QuickSort)
1. Se toma un elemento arbitrario del vector, al que denominaremos pivote (p).
2. Se divide elvector de tal forma que todos los elementos a la izquierda del
pivote sean menores que él, mientras que los que quedan a la derecha son
mayores que él.
3. Ordenamos, por separado, las dos zonas delimitadas por el pivote.
void quicksort (double v[], int izda, int dcha)
{
int pivote; // Posición del pivote
if (izda
quicksort (v, izda, pivote-1);
quicksort (v,pivote+1, dcha);
}
}
Obtención del pivote
Mientras queden elementos mal colocados respecto al pivote:
a. Se recorre el vector, de izquierda a derecha, hasta encontrar un
elemento situado en una posición i tal que v[i] > p.
b. Se recorre el vector, de derecha a izquierda, hasta encontrar otro
elemento situado en una posición j tal que v[j] < p.
c. Se intercambian los elementos situados en lascasillas i y j (de modo
que, ahora, v[i] < p < v[j]).
// Intercambio de dos valores
void swap (double *a, double *b)
{
double tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
// División el vector en dos partes
// - Devuelve la posición del pivote
int partir (double v[], int primero, int ultimo)
{
double pivote = v[primero]; // Valor del pivote
int izda = primero+1;
int dcha = ultimo;
do {
// Pivotear…...
Declaración
Vector (array unidimiensional):
Tipo de dato de los elementos del vector
Identificador de la variable.
Número de elementos del vector.
ü Puede ser un literal o una constante de tipo entero.
û Nunca será una variable
Matriz (array bidimensional):
Acceso
- En C, el índice de la primera componente de un vector es siempre 0.
- El índice de la última componente es
Vector
Matriz
Inicialización
En la declaración, podemos asignarle un valor inicial a los elementos de un vector.
int vector[3] = {4, 5, 6};
int matriz[2][3] = { {1,2,3}, {4,5,6} };
Elcompilador puede deducir las dimensiones del array:
int vector[] = {1, 2, 3, 5, 7};
Manipulación de vectores y matrices
Las operaciones se realizan componente a componente
No es necesario utilizar todos los elementos del vector, por lo que, en C, al trabajar
con ellos, se suele utilizar una variable entera adicional que nos indique el número
de datos utilizados.
float media (float datos[], int N)
{
inti;
float suma = 0;
for (i=0; i
return suma/N;
}
IMPORTANTE: Cuando se pasa un vector como parámetro, el paso de parámetros
es por referencia (un vector es, en realidad, un puntero en C). Por tanto, tenemos
que tener cuidado con los efectos colaterales que se producen si, dentro de un
módulo, modificamos un vector que recibimos como parámetro.
Algoritmos deordenación
Ordenación por selección
void OrdenarSeleccion (double v[], int N)
{
int i, j, pos_min;
double tmp;
for (i=0; i
pos_min = i;
for (j=i+1; j
// Coloca el mínimo en v[i]
tmp = v[i];
v[i] = v[pos_min];
v[pos_min] = tmp; =
}
}
En cada iteración, se selecciona el menor elemento del subvector no ordenado yse intercambia con el primer elemento de este subvector.
Ordenación por inserción
void OrdenarInsercion (double v[], int N)
{
int i, j;
double tmp;
for (i=1; i
for (j=i; (j>0) && (tmp
v[j] = tmp;
}
}
En cada iteración, se inserta un elemento del subvector no ordenado en la posición
correcta dentro del subvector ordenado.
Ordenación porintercambio directo (método de la burbuja)
void OrdenarBurbuja (double v[], int N)
{
int i, j;
double tmp;
for (i=1; i
if (v[j] < v[j-1]) {
tmp = v[j];
v[j] = v[j-1];
v[j-1] = tmp;
}
}
En cada iteración
Estado del vector
tras cada iteración:
Ordenación rápida (QuickSort)
1. Se toma un elemento arbitrario del vector, al que denominaremos pivote (p).
2. Se divide elvector de tal forma que todos los elementos a la izquierda del
pivote sean menores que él, mientras que los que quedan a la derecha son
mayores que él.
3. Ordenamos, por separado, las dos zonas delimitadas por el pivote.
void quicksort (double v[], int izda, int dcha)
{
int pivote; // Posición del pivote
if (izda
quicksort (v, izda, pivote-1);
quicksort (v,pivote+1, dcha);
}
}
Obtención del pivote
Mientras queden elementos mal colocados respecto al pivote:
a. Se recorre el vector, de izquierda a derecha, hasta encontrar un
elemento situado en una posición i tal que v[i] > p.
b. Se recorre el vector, de derecha a izquierda, hasta encontrar otro
elemento situado en una posición j tal que v[j] < p.
c. Se intercambian los elementos situados en lascasillas i y j (de modo
que, ahora, v[i] < p < v[j]).
// Intercambio de dos valores
void swap (double *a, double *b)
{
double tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
// División el vector en dos partes
// - Devuelve la posición del pivote
int partir (double v[], int primero, int ultimo)
{
double pivote = v[primero]; // Valor del pivote
int izda = primero+1;
int dcha = ultimo;
do {
// Pivotear…...
Leer documento completo
Regístrate para leer el documento completo.