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

Fundamentos de la 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
Luis Hernández Yáñez / Pablo Moreno Ger
Universidad Complutense

Recorrido de arrays

Arrays completos
Arrays no completos con centinela
Arrays no completos con contador
Ejemplos
Generación de números aleatorios

Búsquedas en arrays
Arrays completos
Arrays no completos con centinela
Arrays no completos con contador
Ejemplo

Recorridos y búsquedas en cadenas
Más ejemplos de manejo de arrays
Arrays multidimensionales

Inicialización de arrays multidimensionales
Recorrido de un array bidimensional
Recorrido de un array N‐dimensional
Búsqueda en un array multidimensional

Fundamentos de la programación: Recorrido y búsqueda en arrays

590
593
594
595
597
601
604
606
607
608
610
614
617
630
638
641
644
647

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

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

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 590

Esquema de recorrido

Inicialización
Mientras no al final de la secuencia:
Obtener el siguiente elemento
Procesar el elemento
Finalización

truetrue

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

false
false
false

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 591

Recorrido de secuencias en arrays

Todas las posiciones ocupadas:
Tamaño del array = longitud de la secuencia
N elementos en un array de N posiciones:
Recorrer el array desde la primera posición hasta la última
Posiciones libres al final del array:
Tamaño del array > longitud de la secuencia
Con centinela:
Recorrer el array hasta encontrar el valor centinela
Con contadorde elementos:
Recorrer el array hasta el índice contador–1

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 592

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

Recorrido de arrays completos

Todas las posiciones del array ocupadas

const int N = 10;
typedef double tVentas[N];
tVentas ventas;
...

ventas 125.40

76.95

328.80 254.62 435.00 164.29 316.05 219.99

93.45

756.62

0

1

2

3

4

5

6

7

8

9

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

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

}

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

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 593

Recorrido de arrays no completos – con centinela

No todas las posiciones del array están ocupadas

const int N = 10;
typedef double tArray[N];
tArray datos; // Datos positivos: centinela = ‐1
...

datos 125.40

76.95

328.80 254.62 435.00 164.29 316.05

‐1.0

0

1

2

3

4

5

6

7

8

9

int i = 0;
double elemento = datos[i];
while (elemento != ‐1) {

// Procesar el elemento ...
i++;
elemento = datos[i];

}

int i = 0;
double elemento;
do {

elemento = datos[i];
if (elemento != ‐1) {

// Procesar el elemento...
i++;

}

} while (elemento != ‐1);

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 594

Recorrido de arrays no completos – con contador

Array y contador íntimamente relacionados: estructura

const int N = 10;
typedef double tArray[N];
typedef struct {

tArray elementos;
int contador;

} tLista;

Listas de elementos de longitud variable
Listas de elementos de longitud variable

elementos
125.40

76.95

328.80

254.62

435.00

164.29

316.05

0

1

2

3

contador
contador

7

6

7

8

4

5

Nº de elementos (primer índice sin elemento)
Nº de elementos (primer índice sin elemento)

9

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 595

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

Recorrido de arrays no completos – con contador

const int N = 10;
typedef double tArray[N];
typedef struct {

tArray elementos;
int contador;

} tLista;
tLista lista;
...
double elemento;
for (int i = 0; i < lista.contador; i++) {

elemento = lista.elementos[i];
// Procesar el elemento...

}

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

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 596

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 597

fibonacci.cpp
fibonacci.cpp

Array con los N primeros números de Fibonacci

const int N = 50;
typedef long long int tFibonacci[N]; // 50 números
tFibonacci fib;
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] << "   ";

}

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

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 598

Cuenta de valores con k dígitos

Recorrer una lista de N enteros contabilizando cuántos son
de 1 dígito, cuántos de 2 dígitos, etcétera (hasta 5 dígitos)
2 arrays: array con los números y array de contadores

const int NUM = 100;
typedef int tNum[NUM]; // Exactamente 100 números
tNum numeros;
const int DIG = 5;
typedef int tDig[DIG]; // i ‐‐> números de i+1 dígitos
tDig numDig = { 0 };

numeros

numDig

123
0

0
0

2
1

0
1

46237

2345

2

0
2

3

0
3

236
4

0
4

11234

5

33
6

999
7

...

61
99

0
5

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

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 599

Función que devuelve el número de dígitos de un entero:

Cuenta de valores con k dígitos

int digitos(int dato) {

int n_digitos = 1; // Al menos tiene un dígito
// Recorremos la secuencia de dígitos...
while (dato >= 10) {
dato = dato / 10;
n_digitos++;

}
return n_digitos;

}

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 600

Generación de números pseudoaleatorios

Probemos con una secuencia de enteros generada aleatoriamente
Función rand()(cstdlib): entero aleatorio entre 0 y 32766
srand()(cstdlib): inicia la secuencia de números aleatorios
Acepta un entero que usa como semilla para iniciar la secuencia
¿Qué valor usar? Uno distinto en cada ejecución
El instante de tiempo actual (diferente cada vez)
Función time()(ctime): segundos transcurridos desde 1970
Requiere un argumento, que en nuestro caso será NULL

srand(time(NULL)); // Inicia la secuencia
...
numeros[0] = rand(); // Entre 0 y 32766

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 601

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

digitos.cpp
digitos.cpp

Cuenta de valores con k dígitos

#include <iostream>
using namespace std;
#include <cstdlib> // srand() y rand()
#include <ctime> // time()

int digitos(int dato);

int main() {

const int NUM = 100;
typedef int tNum[NUM]; // Exactamente 100 números
const int DIG = 5;
typedef int tDig[DIG];
tNum numeros;
tDig numDig = { 0 }; // Inicializa todo el array a 0

srand(time(NULL)); // Inicia la secuencia aleatoria
...

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 602

for (int i = 0; i < NUM; i++) { // Creamos la secuencia

numeros[i] = rand(); // Entre 0 y 32766

}

for (int i = 0; i < NUM; i++) {
// Recorremos la secuencia de enteros
numDig[digitos(numeros[i]) ‐ 1]++;

}

for (int i = 0; i < DIG; i++) {
// Recorremos la secuencia de contadores

cout << "De " << i + 1 << " díg. = " << numDig[i] 

<< endl;

}
return 0;

}

int digitos(int dato) {
...

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 603

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

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

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 604

Esquema de búsqueda

Inicialización
Mientras no se encuentre el elemento
y no se esté al final de la secuencia:
Obtener el siguiente elemento
Comprobar si el elemento
satisface la condición
Finalización
(tratar el elemento encontrado
o indicar que no se ha encontrado)

Inicialización / encontrado = false;

truetrue

false
false

¿Al final o
encontrado?
Obtener elemento
¿Encontrado?
Finalización

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 605

Todas las posiciones ocupadas

const int N = 100;
typedef int tArray[N];
tArray lista;

int buscado;
bool encontrado = false;
cout << "Valor a buscar: ";
cin >> buscado;
int pos = 0;
while ((pos < N) && !encontrado) {
// Mientras no se llegue al final y no encontrado

if (lista[pos] == buscado) {

encontrado = true;

}
else {

pos++;

}

}
if (encontrado) // ...

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 606

Con centinela

int buscado;
cout << "Valor a buscar: ";
cin >> buscado;
int pos = 0;
bool encontrado = false;
while ((array[pos] != centinela) && !encontrado) {

const int N = 10;
typedef int tArray[N];
tArray array;
const int centinela = ‐1;

if (array[pos] == buscado) {

encontrado = true;

}
else {

pos++;

}

}
if (encontrado) // ...

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 607

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

Con contador

int buscado;
cout << "Valor a buscar: ";
cin >> buscado;
int pos = 0;
bool encontrado = false;
while ((pos < miLista.contador)

&& !encontrado) {

const int N = 10;
typedef double tArray[N];
typedef struct {

tArray elementos;
int contador;

} tLista;
tLista miLista;

// Mientras no al final y no encontrado
if (miLista.elementos[pos] == buscado) {

encontrado = true;

}
else {

pos++;

}

}
if (encontrado) // ...

Fundamentos de la programación: Recorrido y búsqueda en arrays

Página 608

Acceso directo a cualquier posición

Acceso directo: array[posición]
Si se puede calcular la posición del elemento, su acceso es directo

typedef double tVentaMes[DIAS][SUCURSALES];
typedef struct {

tVentaMes ventas;
int dias;

} tMes;
typedef tMes tVentaAnual[MESES];
tVentaAnual anual;
Ventas del cuarto día del tercer mes en la primera sucursal:
anual[2].ventas[3][0]

Fundamentos de la pr