ARREGLOS

Introducción a la estructura de datos:

Como ya sabemos, las computadoras fueron diseñadas o ideadas como una herramienta mediante la cual podemos realizar operaciones de cálculo complicadas en un lapso de mínimo tiempo. Pero la mayoría de las aplicaciones de este fantástico invento del hombre, son las de almacenamiento y acceso de grandes cantidades de información.

La información que se procesa en la computadora es un conjunto de datos, que pueden ser simples o estructurados. Los datos simples son aquellos que ocupan sólo una localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un identificador único.

Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada necesidad.

Las estructuras de datos son una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.

Una estructura de datos se caracteriza por lo siguiente:

• Pueden descomponerse en los elementos que la forman.
• La manera en que se colocan los elementos dentro de la estructura afectará la forma en que se realicen los accesos a cada elemento.
• La colocación de los elementos y la manera en que se accede a ellos puede ser encapsulada.

Ejemplo: Supongamos que nos enfrentamos a un problema como este: Una empresa que cuenta con 150 empleados, desea establecer una estadística sobre los salarios de sus empleados, y quiere saber cual es el salario promedio, y también cuantos de sus empleados gana entre $1250.00 y $2500.00.

Si tomamos la decisión de tratar este tipo de problemas con datos simples, pronto nos percataríamos del enorme desperdicio de tiempo, almacenamiento y velocidad. Es por eso que para situaciones de este tipo la mejor solución son los datos estructurados.

V. OBJETIVOS:

El objetivo por el cual fue el presente trabajo de Estructura de Datos, es el establecer un material de apoyo y consulta para ti que eres alumno de Ingeniería Informática y de Sistemas o de cualquier otra área afín en la cual se imparta la materia de Estructura de Datos. Una vez que hayas terminado de revisar detenidamente este material, serás capaz de establecer estructuras lógicas de datos que te permitan hacer un uso más eficiente del espacio de memoria, de minimizar los tiempos de acceso, así como de lograr formas más efectivas de inserción y eliminación de datos en estructuras de almacenamiento. Ahora que ya sabes en lo que te puede ayudar este tutorial, puedes empezar a hacer uso de él, consultando todas tu tareas y dudas que tengas acerca de la materia.

Acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.

#include<iostream>

using namespace std;

int main(){

int n1,n2, suma = 0, resta = 0, multiplicacion=0,division=0;

cout<<"Digite un numero: "; cin>>n1;

cout<<"Digite otro numero: "; cin>>n2;

suma = n1 + n2;

resta = n1 - n2;

multiplicacion = n1 * n2;

division = n1 / n2;

cout<<"\nLa suma es: "<<suma<<endl;

cout<<"La resta es: "<<resta<<endl;

cout<<"La multiplicacion es: "<<multiplicacion<<endl;

cout<<"La division es: "<<division<<endl;

return 0;

}

Arreglos unidimensionales. Los vectores:

Hasta ahora hemos visto las tres estructuras de programación fundamentales: estructuras secuenciales, estructuras condicionales y estructuras repetitivas.

Al mismo tiempo hemos empleado variables de distinto tipo para el almacenamiento de datos (variables Integer, Double, String).

En esta sección veremos otros tipos de variables que permiten almacenar un conjunto de datos en una única variable.

Tipo de dato simple:  Integer (Almacena un único entero)
   Double (Almacena un único valor flotante)
   String (Almacena un conjunto de caracteres)

Estructuras de datos: Array unidimensionales estáticos (Vector estáticos)

Un vector estático es una estructura de datos que permite almacenar un CONJUNTO de datos del mismo tipo.
Con un único nombre se define un vector y por medio de un subíndice hacemos referencia a cada elemento del mismo (componente).

Problema 1

Se desea guardar los sueldos de 5 operarios.
Según lo conocido deberíamos definir 5 variables si queremos tener en un cierto momento los 5 sueldos almacenados en memoria.

Empleando un vector solo se requiere definir un único nombre y accedemos a cada elemento por medio del subíndice.

La estructura de programación que más se adapta para cargar en forma completa las componentes de un vector es un for, ya que sabemos de antemano la cantidad de valores a cargar.

Es fundamental señalar qué elemento se está cargando en cada momento, esto se logra indicando el subíndice del vector: Sueldos[f], como sabemos la variable f es un contador del for que tomará valores entre 1 y 5.

Es un error si disponemos en la carga el nombre del vector únicamente sin indicar subíndice.

Se podría haber cargado con una estructura secuencial:

#include<iostream>

#include<math.h>

using namespace std;

int main(){

float a,b,c,resultado1 = 0,resultado2 = 0;

cout<<"Digite el valor de a: "; cin>>a;

cout<<"Digite el valor de b: "; cin>>b;

cout<<"Digite el valor de c: "; cin>>c;

resultado1 = (-b+sqrt(pow(b,2)-4*a*c))/(2*a);

resultado2 = (-b-sqrt(pow(b,2)-4*a*c))/(2*a);

cout<<"\nEl resultado 1 es: "<<resultado1<<endl;

cout<<"El resultado 2 es: "<<resultado2<<endl;

return 0;

}

Arreglos multidimensionales:

Arreglos multidimensionales pueden ser descritos como arreglos de arreglos. Por ejemplo, un arreglo bidimensional se puede imaginar como una tabla bidimensional de un tipo de dato concreto y uniforme.Los Arreglos multidimensionales no están limitados a dos índices (dos dimensiones). Pueden contener tantos índices como sea necesario, aunque es raro tener que representar más de 3 dimensiones. Solo considere la cantidad de memoria que un arreglo con muchos índices puede requerir. Por ejemplo: char century [100][365][24][60][60]; assigna un char para cada segundo contenido en un siglo, que es más de 3 mil millones de chars! Esto consumiría cerca de 3000 megabytes de memoria RAM si pudiéramos declararlo. Los arreglos multidimensionales no son más que una abstracción, ya que podemos obtener los mismos resultados con un simple arreglo poniendo un factor entre sus indices: int matriz [3][5]; es equivalente a int vector [15]; (3 * 5 = 15)

#include<iostream>#include<stdlib.h>#include<conio.h>using namespace std;
struct Nodo{ int dato; Nodo *siguiente; };
void insertarLista(Nodo *&,int);void mostrarLista(Nodo *);void calcularMayorMenor(Nodo *);
int main(){ Nodo *lista = NULL; int dato; char opcion; do{ cout<<"Digite un numero para agregarlo a lista: "; cin>>dato; insertarLista(lista,dato); cout<<"\nDesea agregar un nuevo numero(s/n): "; cin>>opcion; }while(opcion == 's' || opcion == 'S'); cout<<"\nElementos de la lista: \n"; mostrarLista(lista); //mostramos la lista calcularMayorMenor(lista); getch(); return 0;}
//Insertar elemento en la listavoid insertarLista(Nodo *&lista,int n){ Nodo *nuevo_nodo = new Nodo(); Nodo *aux; nuevo_nodo->dato = n; nuevo_nodo->siguiente = NULL; if(lista == NULL){//Si la lista esta vacia lista = nuevo_nodo;//agregamos el primer nodo } else{ aux = lista; while(aux->siguiente != NULL){//recorremos la lista hasta llegar al final aux = aux->siguiente; } aux->siguiente = nuevo_nodo;//agregamos el nuevo nodo al final de la lista } cout<<"\tElemento "<<n<<" agregado a lista correctamente\n";}
//Mostrar todos los elementos de la listavoid mostrarLista(Nodo *lista){ Nodo *actual = new Nodo(); actual = lista; while(actual != NULL){ //mientras no sea final de la lista cout<<actual->dato<<" -> "; //mostramos el dato actual = actual->siguiente; //avanzamos a la siguiente posicion de la lista }}
//Calcular el menor y mayor elemento de la listavoid calcularMayorMenor(Nodo *lista){ int mayor=0,menor=99999; while(lista != NULL){//mientras no sea el final de la lista if((lista->dato)>mayor){//Comprobamos el numero mayor mayor = lista->dato; } if((lista->dato)<menor){//Comprobamos el numero menor menor = lista->dato; } lista = lista->siguiente;//Avanzamos en la lista } cout<<"\n\nEl mayor numero es: "<<mayor<<endl; cout<<"El menor numero es: "<<menor<<endl; }

ARREGLOS Y ESTRUCTURAS

Arreglo (array)

Es una colección o conjunto de variables relacionadas entre sí, por el hecho de que todas tienen el mismo nombre y son del mismo tipo.Un arreglo es una variable capaz de guardar uno o más valores del mismo tipo.  Un arreglo consta de posiciones de memoria contiguas, para referirse a una posición en particular o elemento dentro de un arreglo especificamos el nombre del arreglo y el número de posición del elemento particular dentro del mismo.                    - Unidimensionales (vectores)
Arreglos     - Bidimensionales (matrices)
                    - Multidimensionales

Arreglos unidimensionales
Son esencialmente listas de información de un solo tipo, es decir, de una sola dimensión.  Por ejemplo, tenemos el siguiente arreglo de enteros llamado a.



Arreglo tridimencional




 
CADENASEl uso más corriente de un arreglo unidimensional es crear cadenas de caracteres.En C/C++, una cadena es un arreglo de caracteres, que termina con un caracter nulo (‘\0’).Por esta razón, se debe declarar arreglos de caracteres con un caracter más que la cadena más larga que vaya a guardar.Se tiene acceso a una cadena mediante un apuntador al primer caracter de la cadena.Una cadena puede ser asignada en una declaración, ya sea un arreglo de caracteres o una variable de tipo char.            char cadena [11];                //cadena de 10 caracteres            char color[  ] = “blue”;          // 5 elementos            char color [  ] = [“’b’, ‘l’, ‘u’, ‘e’, ‘\0’};La mejor manera de introducir una cadena desde el teclado es usando la función de biblioteca gets ( ).  El formato general es:  gets (nombre_arreglo);Funciones de cadena de la biblioteca de C/C++El archivo cabecera <string.h> contiene un gran número de funciones de manipulación de cadena.  Las más comunes son:Ø  strcpy ( )Ø  strcat ( )Ø  strcmp ( )Ø  strlen ( ) Función strcpyCopia los contenidos de la cadena desde  a la cadena a.Función strcatLa función strcat ( ) añade s2 al final de s1; s2 no se altera.  Ambas cadenas terminan con un nulo y el resultado temina en nulo.Función strcmpLa función strcmp ( ) compara dos cadenas y devuelve 0 (cero) si son iguales.  Si s1 es lexicográficamente mayor que s2, entonces la función devuelve un número positivo; su s1 es menor que s2, la función devuelve un número negativo. Función strlenLa función strlen ( ) devuelve la longitud de la cadena s.  Arreglos bidimensionalesLos arreglos multidimensionales constan de dos o más dimensiones.  La forma más común para utilizar los arreglos multidimensionales son los arreglos bidimensionales (matrices)  que representan tablas de valores, consistiendo de información arreglada en renglones (filas) y columnas.El formato general para la declaración de un arreglo bidimensional:tipo nombre_arreglo [m][n];tipo nombre_arreglo[tam];tipo nombre_arreglo[tam];tipo declara el tipo de datos de cada elemento del arreglo.m número de renglones (filas) del arreglo.n número de columnas del arreglo.Para identificar un elemento particular de la tabla, se especifican 2 subíndices:-          el primero identifica el renglón del elemento.-          el segundo identifica la columna del elemento.Por ejemplo, para declarar un arreglo bidimensional (matriz) de 3x4 de tipo flotante:float  matriz [3] [4];Otras declaraciones:int num [3] [2];double a [100] [40];int m [F] [C];              // donde F y C se declaran como constantes simbólicasfloat f [10] [5];Estructuras (struct)En muchos casos, los programas necesitarán agrupar información relacionada que puede no ser del mismo tipo.  Por ejemplo, supongamos que el programa trabaja con registros de empleado.  Se debe seguir la pista del nombre, la edad, el salario, la dirección, el número de empleado, el número de puesto, etc. Para almacenar esta información el programa necesitaría variables de tipo char, int, float, así como cadenas de caracteres.  Cuando es necesario guardar información relacionada de tipo diferente, el programa puede utilizar una estructura.Las estructuras son colecciones de variables relacionadas que se referencian bajo un mismo nombre.struct (palabra reservada para definir una estructura) dice al compilador que se va a definir una estructura.dire (rótulo de la estructura) da nombre a la definición de la estructura.Las variables declaradas dentro de las llaves de la definición de la estructura son los miembros de la estructura.  Los miembros de la estructura deben tener nombres únicos, pero dos estructuras diferentes pueden contener miembros con el mismo nombre sin entrar en conflicto.Cada definición de estructura debe terminar con punto y coma (;).Por lo tanto, el formato general de una definición de estructura es:struct nombre_tipo_de_estructura {            tipo nombre_elemento1;            tipo nombre_elemento2;      miembros                        ...            tipo nombre_elemento_n;} variables_estructura;struct define un determinado tipo de estructura (nombre_tipo_de_estructura) y declara las variables_estructura del mismo tipo.Si sólo se necesita una variable estructurada, no se necesita incluir el nombre de la estructura.Las únicas operaciones válidas que pueden ejecutarse sobre estructuras son: asignar variables de estructura a variables de estructura del mismo tipo, tomando la dirección (&) de una variable de estructura, obteniendo acceso a los miembros de una variable de estructura, y utilizando el operador sizeof,  a fin de determinar el tamaño de la variable de estructura.Operador sizeofEl operador unario especial sizeof  determina el tamaño de un arreglo en bytes (o de cualquier otro tipo de datos) durante la compilación de un programa.   Cuando se aplica al nombre de un arreglo, el operador sizeof regresa como un entero el número total del bytes del arreglo.  Para esto, se utiliza de la siguiente manera:                        sizeof (nombre_arreglo)El operador sizeof  puede ser aplicado a cualquier nombre de variable, tipo o constante.  Al se aplicado aun nombre de variable (que no sea un nombre de arreglo), o a una constante, será regresado el número de bytes utilizados para almacenar el tipo específico de variable o de constante.UnionesConforme los programas se vuelven más complejos, habrá ocasiones en que necesiten diferentes formas de ver una parte de la información, además habrá otras veces que se tenga la necesidad de trabajar con dos o más valores, pero solamente utilizar uno de los valores en un momento dado.  En tales casos, los programas pueden utilizar las uniones para guardar los datos.Una unión es un tipo de datos derivado, como lo es una estructura, cuyos miembros comparten el mismo espacio de almacenamiento.  Para distintas situaciones en un programa, algunas variables pudieran no ser de importancia, pero otras variables lo son, por lo que una unión comparte el espacio, en vez de desperdiciar el almacenamiento en variables que no están siendo utilizadas.  Los miembros de una unión pueden ser de cualquier tipo.  El número de bytes utilizados para almacenar una unión, deben ser por lo menos suficiente para contener el miembro más grande.   En la mayor parte de los casos, las uniones contienen dos o más tipos de datos.  Únicamente un miembro y, por lot anto, únicamente un tipo de datos, puede ser referenciado en un momento dado.  Es responsabilidad del programador asegurarse que en una unión los datos están referenciados con el tipo de dato apropiado.Una unión se declara con la palabra reservada union en el mismo formato que una estructura:union nombre_tipo_union {      tipo elemento_1;      tipo elemento_2;   . . .      tipo elemento_n;   }  variables_union;EnumeracionesUna enumeración es un conjunto de constantes enteras representadas por identificadores.  Estas constantes de enumeración  son constantes simbólicas cuyos valores pueden ser definidos automáticamente.La declaración de una enumeración se realiza con la palabra reservada enum:enum nombre_enum {lista_enum} lista_variables;Arreglos bidimensionalesSon arreglos de dos dimensiones, son llamados tablas o matrices.  Se accesa a los elementos de un arreglo bidimensional por medio de dos índices, b [i] [j].
 







Arreglos multidimensionales
Son arreglos de 3 dimensiones o más, se accesa a los elementos por medio de 3
índices o más, c [i] [j] [k]

Arreglos unidimensionales