Implementación de listas con arrays Listas con un número variable de elementos Array con un máximo de elementos + Contador de elementos const int MAX = 100; typedef double tLista[MAX]; // Hasta 100 elementos tLista lista; int contador = 0; // Se incrementa al insertar Recorrido de la lista: for (int i = 0; i < contador; i++) { … Búsqueda en la lista: while ((i < contador) && !encontrado) { … ¿Array y contador por separado? ? Estructuras
Cadenas de caracteres Arrays de caracteres Cadenas: secuencias de caracteres de longitud variable "Hola" "Adiós" "Supercalifragilístico" "1234 56 7" Variables de cadena: contienen secuencias de caracteres Se guardan en arrays de caracteres: tamaño máximo (dimensión) No todas las posiciones del array son relevantes: Longitud de la cadena: número de caracteres, desde el primero, que realmente constituyen la cadena:
Longitud actual: 4
Cadenas de caracteres Longitud de la cadena
Longitud: 5
Longitud: 21 Necesidad de saber dónde terminan los caracteres relevantes: Mantener la longitud de la cadena como dato asociado Colocar un carácter de terminación al final (centinela)
Cadenas de caracteres Cadenas de caracteres en C++ Dos alternativas para el manejo de cadenas: Cadenas al estilo de C (terminadas en nulo) Tipo string Cadenas al estilo de C Anexo del tema Arrays de tipo char con una longitud máxima Un último carácter especial al final: '' Tipo string Cadenas más sofisticadas Sin longitud máxima (gestión automática de la memoria) Multitud de funciones de utilidad (biblioteca string)
Cadenas de caracteres de tipo string El tipo string El tipo asume la responsabilidad de la gestión de memoria Define operadores sobrecargados (+ para concatenar) Cadenas más eficientes y seguras de usar Biblioteca string Requiere establecer el espacio de nombres a std Se pueden inicializar en la declaración Se pueden copiar con el operador de asignación Se pueden concatenar con el operador + Multitud de funciones de utilidad
Cadenas de tipo string #include < iostream> #include < string> using namespace std;
int main() { string cad1("Hola"); // inicialización string cad2 = "amigo"; // inicialización string cad3; cad3 = cad1; // copia cout < < "cad3 = " < < cad3 < < endl; cad3 = cad1 + " "; // concatenación cad3 += cad2; // concatenación cout < < "cad3 = " < < cad3 < < endl; cad1.swap(cad2); // intercambio cout < < "cad1 = " < < cad1 < < endl; cout < < "cad2 = " < < cad2 < < endl;
return 0; }
Cadenas de tipo string Longitud de la cadena: cadena.length() o cadena.size() Se pueden comparar con los operadores relacionales: if (cad1 < = cad2) { … Acceso a los caracteres de una cadena: Como array de caracteres: cadena[i] Sin control de acceso a posiciones inexistentes del array Sólo debe usarse si se está seguro de que el índice es válido Función at(índice): cadena.at(i) Error de ejecución si se accede a una posición inexistente
E/S con cadenas de tipo string Se muestran en la pantalla con cout < < Lectura con cin >>: termina con espacio en blanco (inc. Intro) El espacio en blanco queda pendiente Descartar el resto de los caracteres del búfer: cin.sync(); Lectura incluyendo espacios en blanco: getline(cin, cadena) Guarda en la cadena los caracteres leídos hasta el fin de línea Lectura de archivos de texto: Igual que de consola; sync() no tiene efecto archivo >> cadena getline(archivo, cadena)
E/S con cadenas de tipo string #include < iostream> #include < string> using namespace std;
int main() { string nombre, apellidos; cout < < "Introduzca un nombre: "; cin >> nombre; cout < < "Introduzca los apellidos: "; cin.sync(); getline(cin, apellidos); cout < < "Nombre completo: " < < nombre < < " " < < apellidos < < endl;
return 0; }
Operaciones con cadenas de tipo string cadena.substr(posición, longitud) Subcadena de longitud caracteres desde posición string cad = "abcdefg"; cout < < cad.substr(2, 3); // Muestra cde cadena.find(subcadena) Posición de la primera ocurrencia de subcadena en cadena string cad = "Olala"; cout < < cad.find("la"); // Muestra 1 (Recuerda que los arrays de caracteres comienzan con el índice 0) cadena.rfind(subcadena) Posición de la última ocurrencia de subcadena en cadena string cad = "Olala"; cout < < cad.rfind("la"); // Muestra 3
Operaciones con cadenas de tipo string cadena.erase(ini, num) Elimina num caracteres a partir de la posición ini string cad = "abcdefgh"; cad.erase(3, 4); // cad ahora contiene "abch" cadena.insert(ini, cadena2) Inserta cadena2 a partir de la posición ini string cad = "abcdefgh"; cad.insert(3, "123"); // cad ahora contiene "abc123defgh"
Estructuras Colecciones heterogéneas (tuplas, registros) Elementos de (posiblemente) distintos tipos: campos Campos identificados por su nombre Información relacionada que se puede manejar como una unidad Acceso a cada elemento por su nombre de campo (operador.)
Tipos de estructuras typedef struct { … // declaraciones de campos (como variables) } tTipo; // nombre de tipo – ¡al final! typedef struct { string nombre; string apellidos; int edad; string nif; } tPersona; Campos: Tipos estándar o previamente declarado
Variables de estructuras tPersona persona; Las variables de tipo tPersona contienen cuatro datos (campos): nombre apellidos edad nif Acceso a los campos con el operador punto (.): persona.nombre // una cadena (string) persona.apellidos // una cadena (string) persona.edad // un entero (int) persona.nif // una cadena (string) Podemos copiar dos estructuras directamente: tPersona persona1, persona2; … persona2 = persona1; Se copian todos los campos a la vez
typedef struct { string nombre; string apellidos; int edad; string nif; } tPersona; tPersona persona; Agrupación de datos heterogéneos (Gp:) Luis Antonio (Gp:) nombre
(Gp:) Hernández Yáñez (Gp:) apellidos
(Gp:) 22 (Gp:) edad
(Gp:) 00223344F (Gp:) nif
persona
Elementos sin orden establecido typedef struct { string nombre; string apellidos; int edad; string nif; } tPersona; tPersona persona; Los campos no siguen ningún orden establecido Acceso directo por nombre de campo (operador .) Con cada campo se puede hacer lo que permita su tipo (Gp:) Las estructuras se pasan por valor (sin &)o por referencia (con &) a los subprogramas
Estructuras dentro de estructuras typedef struct { typedef struct { string dni; … char letra; tNif nif;} tNif; } tPersona;
tPersona persona; Acceso al NIF completo: persona.nif // Otra estructura Acceso a la letra del NIF: persona.nif.letra Acceso al DNI: persona.nif.dni
(Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) tPersona
(Gp:) dni (Gp:) letra (Gp:) tNif
Arrays de estructuras const int DIM = 100; typedef struct { string nombre; string apellidos; int edad; string nif; } tPersona; typedef tPersona tArray[DIM]; tArray personal; Nombre de la tercera persona: personal[2].nombre Edad de la duodécima persona: personal[11].edad NIF de la primera persona: personal[0].nif
(Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) tPersona
(Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) 1 (Gp:) 0 (Gp:) 2 (Gp:) DIM-1 (Gp:) personal
Arrays dentro de estructuras const int MAX = 100; typedef struct { string nombre; string apellidos; int edad; string nif; } tPersona; typedef tPersona tArray[MAX]; typedef struct { tArray elementos; int contador; } tLista; tLista lista; Nombre de la tercera persona: lista.elementos[2].nombre Edad de la duodécima persona: lista.elementos[11].edad NIF de la primera persona: lista.elementos[0].nif
(Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) nombre (Gp:) apellidos (Gp:) edad (Gp:) nif (Gp:) 1 (Gp:) 0 (Gp:) 2 (Gp:) MAX-1 (Gp:) elementos (Gp:) contador (Gp:) lista
Estructura que agrupe el array y el contador: const int MAX = 10; typedef double tArray[MAX]; typedef struct { tArray elementos; int contador; } tLista;
Operaciones principales: inserción y eliminación de elementos (Gp:) 6 (Gp:) contador
Listas de longitud variable (Gp:) Nº de elementos (y primer índice sin elemento)
Elementos sin usar(datos basura)
Insertar un nuevo elemento en una posición Posiciones válidas: 0 a contador
Hay que asegurarse de que haya sitio (contador < máximo) Operación en 3 pasos: 1.- Abrir hueco para el nuevo elemento (desde la posición) 2.- Colocar el elemento nuevo en la posición 3.- Incrementar el contador 6 Inserción de elementos 42.0 nuevo 3 pos
if (lista.contador < N) { // Abrir hueco for (int i = lista.contador; i > pos; i–) { lista.elementos[i] = lista.elementos[i – 1]; } // Insertar e incrementar contador lista.elementos[pos] = nuevoElemento; lista.contador++; }
Inserción de elementos 7 42.0 nuevo 3 pos
Eliminar el elemento en una posición Posiciones válidas: 0 a contador-1
Desplazar a la izquierda desde el siguiente y decrementar el contador: for (int i = pos; i < lista.contador – 1 ; i++) { lista.elementos[i] = lista.elementos[i + 1]; } lista.contador–; 6 Eliminación de elementos 3 pos
(Gp:) 5 (Gp:) 3 (Gp:) pos
for (int i = pos; i < lista.contador – 1 ; i++) { lista.elementos[i] = lista.elementos[i + 1]; } lista.contador–; 6 Eliminación de elementos 3 pos
Ejemplo de lista de longitud variable Descripción Programa que mantenga una lista de los estudiantes de una clase De cada estudiante: nombre, apellidos, edad, NIF y nota Se desconoce el número total de estudiantes (máximo 100) La información de la lista se mantiene en un archivo clase.txt Se carga al empezar y se guarda al finalizar El programa debe ofrecer estas opciones: Añadir un nuevo alumno Eliminar un alumno existente Calificar a los estudiantes Listado de notas, identificando la mayor y la media
Ejemplo de lista de longitud variable #include < iostream> #include < string> using namespace std; #include < fstream> #include < iomanip>
const int MAX = 100; typedef struct { string nombre; string apellidos; int edad; string nif; double nota; } tEstudiante; typedef tEstudiante tArray[MAX]; typedef struct { tArray elementos; int contador; } tLista; (Gp:) Declaraciones de constantesy tipos globales Tras las bibliotecas
Ejemplo de lista de longitud variable // Prototipos int menu(); // Menú del programa – devuelve la opción elegida void cargar(tLista &lista, bool &ok); // Carga del archivo void guardar(const tLista &lista); // La guarda en el archivo void leerEstudiante(tEstudiante &estudiante); // Lee los datos void insertarEstudiante(tLista &lista, tEstudiante estudiante, bool &ok); // Inserta un nuevo estudiante en la lista void eliminarEstudiante(tLista &lista, int pos, bool &ok); // Elimina el estudiante en esa posición string nombreCompleto(tEstudiante estudiante); void calificar(tLista &lista); // Notas de los estudiantes double mediaClase(const tLista &lista); // Nota media int mayorNota(const tLista &lista); // Índice del estudiante con mayor nota void mostrarEstudiante(tEstudiante estudiante); void listado(const tLista &lista, double media, int mayor); // Listado de la clase Los prototipos, después de los tipos globales
| Página siguiente |