PDF de programación - 6 Algoritmos de recorrido y búsqueda de arrays

21/02/2014

Fundamentos de programación

6

Grado en Ingeniería Informática
Grado en Ingeniería del Software
Grado en Ingeniería de Computadores
Facultad de Informática
Universidad Complutense

Recorrido de arrays

Recorrido de arrays completos
Recorrido de arrays no completos

Con contador
Con centinela

Ejemplos
De archivo a array
De array a archivo
Arrays multidimensionales

Búsquedas en arrays

Búsqueda de arrays completos
Búsqueda de arrays no completos

Con contador
Con centinela

Ejemplos
Arrays multidimensionales

Recorridos y búsquedas en cadenas

2
4
7
7
9
12
17
22
25
29
30
34
34
36
38
42
45

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Algoritmos de recorrido y búsqueda para arrays

Página 1

1

Esquema de recorrido

Inicialización
Mientras no se llegue al final de la secuencia:
Obtener el siguiente elemento
Procesar el elemento
Finalización
Secuencias en arrays:
 Todas las posiciones ocupadas:
Tamaño del array = longitud de la secuencia
 Posiciones libres al final del array:
Tamaño del array > longitud de la secuencia
 Con contador de elementos.
 Con centinela.

truetrue

Inicialización
¿Al final?
Obtener elemento
Procesar elemento
Finalización

false
false

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 2

Recorrido de secuencias en arrays

 Todas las posiciones ocupadas:
N elementos en un array de N posiciones:
Recorrer todo el array desde la primera posición hasta la última.
 Posiciones libres al final del array:
 Con contador de elementos:
Recorrer las posiciones del array desde la primera hasta contador‐1.
 Con centinela:
Recorrer el array hasta encontrar el valor centinela.

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 3

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

21/02/2014

2

21/02/2014

Todas las posiciones del array ocupadas.

Recorrido de arrays completos

const int N = 10;
double ventas[N];
ventas
125.40

328.80

76.95

254.62

435.00

164.29

316.05

219.99

93.45

756.62

0

1

2

3

4

5

6

7

8

9

int i = 0;
double dato; 
while (i < N) {

dato = ventas[i];
// Procesar el dato...
i++;

Versión con for
Versión con for

}
// ...

double dato;
for (int i = 0; i < N; i++) {

dato = ventas[i];
// Procesar el dato...

}
// ...

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 4

Propiedad invariante

Expresa la relación entre la variables
que controlan el bucle
Se cumple vuelta tras vuelta

int i = 0;
double dato; 
while (i < N) {

}
// ...

dato = ventas[i];
// Procesar el dato...
i++;

Invariante :
Procesado(ventas[0 … i‐1])
0 ≤ i≤ N

Invariante
Invariante
truetrue

Inicialización
¿Al final?
Obtener elemento
Procesar elemento
Finalización

false
false

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 5

3

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

21/02/2014

Invariante
Invariante
truetrue

Inicialización
¿Al final?
Obtener elemento
Procesar elemento
Finalización

false
false

int i = 0;
double dato = ventas[i]; //N>0
// Procesar el dato...
while (i < (N‐1)) {

i++;
dato = ventas[i];
// Procesar el dato...

}
// ...

Invariante :
Procesado(ventas[0 … i])
dato= ventas[i]
0 ≤ i≤ N‐1

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 6

Recorrido de arrays no completos – con contador

No todas las posiciones del array ocupadas. Contador de elementos.
Como el array y el contador están íntimamente relacionados,
usamos una estructura para encapsularlos:

const int N = 10;
typedef struct {

double elementos[N];
int contador;

} tLista; // struct termina en ;

elementos
125.40

76.95

0

1

328.80

2

contador
contador

7

254.62

3

7

6

5

4

164.29

316.05

435.00

Nº de elementos o primer índice sin elemento
Nº de elementos o primer índice sin elemento
contador=0 ↔ el array está vacío
contador=0 ↔ el array está vacío
contador=N ↔ el array está lleno
contador=N ↔ el array está lleno

8

9

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 7

4

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

21/02/2014

Invariante
Invariante
truetrue

Inicialización
¿Al final?
Obtener elemento
Procesar elemento
Finalización

false
false

} // ...

int i = 0;
double dato;
while (i < miLista.contador) {
dato = miLista.elementos[i]; 
// Procesar el dato...
i++;

Invariante :
Procesado(miLista.elementos[0 … i‐1])
0 ≤ i≤ miLista.contador≤ N
Versión con for

double dato;
for (int i = 0; i < miLista.contador; i++){
dato = miLista.elementos[i];
// Procesar el dato...

} // ...

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 8

Recorrido de arrays no completos – con centinela

No todas las posiciones del array ocupadas.
Todos los valores positivos: centinela = cualquier negativo

const int N = 10;
double array[N];

array
125.40

76.95

328.80

254.62

435.00

164.29

316.05

‐1.0

3

4

5

2

0

1
int i = 0;
double dato;
bool final = false;
while (!final) {

dato = array[i];
if (dato < 0) final = true;
else {

// Procesar el dato...
i++;

}

} // ...

7

6

9

8

Invariante : esquema asimétrico
•Procesado(array[0 … i‐1])
• final → array[i] < 0
• array[0 … i‐1] ≥ 0
•0 ≤ i≤ N‐1

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 9

5

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

21/02/2014

Recorrido de arrays no completos – con centinela

No todas las posiciones del array ocupadas.
Todos los valores positivos: centinela = cualquier negativo

const int N = 10;
double array[N];

array
125.40

76.95

328.80

254.62

435.00

164.29

316.05

‐1.0

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

0

1

2

3

4

5

int i = 0;
double dato = array[i]; // N>0
bool final = dato<0;
while (!final){

// Procesar el dato... 
i++;
dato = array[i];
final = dato<0; 

} // …

9

8

7

6

Invariante : esquema simétrico
•Procesado(array[0 … i‐1])
• final ↔ array[i] < 0
• array[0 … i‐1] ≥ 0
• dato= array[i]
•0 ≤ i≤ N‐1

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 10

Recorrido de arrays no completos – con centinela

No todas las posiciones del array ocupadas.
Todos los valores positivos: centinela = cualquier negativo

const int N = 10;
double array[N];

array
125.40

76.95

328.80

254.62

435.00

164.29

0

1

2

3

4

5

int i = 0;
double dato = array[i]; // N>0
while (dato >= 0){

// Procesar el dato... 
i++;
dato = array[i];

} // …

9

8

7

6

‐1.0

316.05

Invariante : esquema simétrico
•Procesado(array[0 … i‐1])
• array[0 … i‐1] ≥ 0
• dato= array[i]
•0 ≤ i≤ N‐1

controlado por
expresión centinela

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 11

6

Media de una lista de N números enteros en array

media.cpp
media.cpp

const int N = 100;
int nums[N]; // Exactamente 100 enteros

// Por ejemplo, los 100 primeros cuadrados:
for (int i = 0; i < N; i++)

nums[i] = i * i;

double total = 0, media;
for (int i = 0; i < N; i++)

total += nums[i];
media = total / N;
cout << "Media de la lista de enteros: " << media << endl;

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 12

Array con los N primeros números de Fibonacci

fibonacci.cpp
fibonacci.cpp

const int N = 50;
long long int fib[N]; // Exactamente 50 números

fib[0] = 1;
fib[1] = 1;

for (int i = 2; i < N; i++)

fib[i] = fib[i‐1] + fib[i‐2];

for (int i = 0; i < N; i++)
cout << fib[i] << "   ";

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 13

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

21/02/2014

7

21/02/2014

Cuenta de valores con k dígitos

Recorrer una lista de N números enteros no negativos contabilizando
cuántos son de 1 dígito, de 2 dígitos, de 3 dígitos, etcétera (hasta 6 dígitos).
2 arrays: array con valores y array de contadores
Función que devuelve el número de dígitos de un valor entero positivo:

const unsigned int N = 100;
unsigned int num[N]; // Exactamente 100 números
const unsigned int D = 6;
unsigned int dig[D];
// Posición i ‐‐> cantidad de números de i+1 dígitos

unsigned int digitos( unsigned int dato) {

unsigned int n_digitos = 1;
while (dato >= 10) {
dato = dato / 10;
n_digitos++;

}
return n_digitos;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

Fundamentos de programación: Algoritmos de recorrido y búsqueda para arrays

Página 14

digitos.cpp
digitos.cpp

Cuenta de valores con k dígitos

#include <iostream>
#include <cstdlib>
using namespace std;

unsigned int digitos(unsigned int);

int main() {

const unsigned int N = 100;
unsigned int num[N]; // Exactamente 100 números
const unsigned int D = 6;
unsigned int dig[D];
// Posición i ‐‐> cantidad de números de i+1 dígitos

for (unsigned int i = 0; i < N; i++) num[i] = rand(); 
for (unsigned int