Programación I
Teoría III
http://proguno.unsl.edu.ar
[email protected]
DATOS ESTRUCTURADOS
Estructuras de Datos
Hasta ahora hemos trabajado con …
Datos simples
enteros
reales
Caracteres
punteros
Sin embargo, existe la necesidad de manipular
datos compuestos
Relacionados lógicamente
Unidad conceptual
Estructuras de Datos
Datos Estructurados
Arreglos
Registros
Pilas
Filas
Listas
Arboles …
Ejemplos de uso:
Datos de una persona
Notas de examen de los alumnos de un curso.
Estructuras de Datos
Al trabajar con datos estructurados, surgen nuevos
interrogantes:
¿Cuántos elementos se pueden almacenar? (Capacidad)
¿Cómo se incorpora, elimina o cambia y se recupera un
elemento de la estructura? (Operaciones)
¿En qué orden se encuentran elementos, uno con respecto
a los otros? (Orden)
¿Cómo se identifican o seleccionan los elementos de la
estructura? (Selector).
¿Qué tipo de datos pueden guardarse en la estructura?
(Tipo Base).
Veamos cada uno …
Capacidad de las Estructuras de Datos
Dinámica
Crece y decrece con las inserciones y
supresiones.
Estática
Fija, no crece ni decrece.
Operaciones y Predicados de Control
sobre las Estructuras de Datos
COLOCAR / INSERTAR un elemento nuevo en la estructura /
ASIGNAR en el caso de estructuras estáticas.
SACAR / SUPRIMIR de la estructura un elemento ya existente en
ella / ASIGNAR en el caso de estructuras estáticas.
INSPECCIONAR / LEER / RECUPERAR un elemento de la
estructura para conocer su valor.
¿Está LLENA?
¿Está VACÍA?
Otras operaciones propias de cada tipo de estructura de datos.
Orden de los Elementos
Orden cronológico
Ejemplos:
Orden de inserción
Orden de supresión
Orden de inspección
Orden no cronológico
Ejemplos:
Orden alfabético, numérico, lexicográfico …
Selector de Elementos
Selecciona, elige, identifica de forma unívoca cada
uno de los elementos de la estructura.
Explícito
El selector debe ser referenciado explícitamente en el
código del programa al ser utilizado.
Implícito
No es necesario definir un identificador para el selector. El
elemento seleccionado será algún elemento distinguido de
la estructura.
Tipo Base de una Estructura
Es el tipo de los elementos de la estructura
Puede ser:
Homogéneo / Heterogéneo
Simple / Compuesto o estructurado
ARREGLOS
Arreglos
Estructura de datos homogénea donde todos sus
elementos se encuentran contiguos en la memoria y se
acceden a través de un índice.
Selector: explícito (índice o suscripto).
Arreglos unidimensionales → un índice
Arreglos multidimensionales → múltiples índices
Orden cronológico: No existe. El acceso es directo y
aleatorio a cualquier elemento cuya dirección se puede
calcular por una expresión. Podría existir otro.
Arreglos
En general, la capacidad es estática. En
algunos lenguajes hay arreglos dinámicos
o extensibles.
Operaciones:
Asignación
Inspección
Arreglos en C
Son estáticos, no hay arreglos dinámicos.
Tienen las mismas reglas de alcance (ámbito)
que cualquier variable simple.
Índices: expresiones que evalúen a un entero.
Comienzan siempre desde la posición 0.
0
a[4]
23
a[5]
4
a[6]
11
a[7]
-34
a[8]
-7
a[9]
9
-1
300 -54
a[0] a[1] a[2] a[3]
int a[10];
int x = 2;
a[2+x] = a[2+x] + x;
Declaración de Arreglos en C
Ejemplos de declaraciones válidas
int a[10];
int b[50], c[8];
int a[4] = {20, 30, 40, 10};
char b[10] = {‘a’, ‘B’, ‘?’};
float c[] = {3.1, 4.5, 2.6};
#include <stdio.h>
#define SIZE 10
int main(){
int a[SIZE], i;
for (i = 0 ; i < SIZE; i++)
a[i] = 0;
printf("Indice\tElemento\n");
for (i = 0 ; i < SIZE; i++)
printf("%d\t%d\n", i, a[i]);
return 0;
}
Arreglos Multidimensionales en C
int a[2][3];
Columna 0 Columna 1 Columna 2
a[0][2]
a[1][2]
a[0][1]
a[1][1]
Fila 0 a[0][0]
Fila 1 a[1][0]
Arreglos Multidimensionales en C
int a[2][3] = {{3, 8, 4}, {-3, 6, 1}};
int a[2][3] = {3, 8, 4, -3, 6, 1};
Columna 0 Columna 1 Columna 2
Fila 0
Fila 1
3
-3
8
6
4
1
Arreglos Multidimensionales en C
int a[2][3] = {{3, 8}, {-3, 6, 1}};
Columna 0 Columna 1 Columna 2
Fila 0
Fila 1
3
-3
8
6
0
1
Arreglos Multidimensionales en C
int a[2][3] = {3, 8, 4, -3};
Columna 0 Columna 1 Columna 2
Fila 0
Fila 1
3
-3
8
0
4
0
Relación entre Punteros y Arreglos en C
En C, todas las operaciones que se realizan
con arreglos pueden ser realizadas con
punteros.
En C, la dirección base de un arreglo es
equivalente al nombre del arreglo.
Ejemplo:
int b[100];
b es equivalente a &b[0]
int a[5] = {1, 4, -5, 0, 8};
int *p;
p = a; /*es equivalente a p = &a[0];*/
a[0] a[1] a[2] a[3] a[4]
1 4 -5 0 8
p
printf(“%d”, a[0]);
printf(“%d”, *p);
printf(“%d”, *a);
Producirán el mismo
efecto
Relación entre Punteros y Arreglos en C
Aritmética de Punteros
En C, se puede realizar, bajo ciertas
condiciones, algunas operaciones aritméticas
con punteros :
Un puntero puede ser incrementado (++) o
decrementado (--).
Se le puede sumar o restar un valor entero.
Pueden sumarse y restarse punteros entre sí.
a[0] a[1] a[2] a[3] a[4]
1 4 -5 0 8
p+2 p+3 p+4
p
p+1
p
p+1
p+2
...
p+i
&a[0]
&a[1]
&a[2]
...
&a[i]
*p
a[0]
*(p+1) a[1]
*(p+2) a[2]
...
...
*(p+i) a[i]
Ejemplo1:
int x[5] = {10, -3, 7, 6, 4};
&x[0]
&x[2]
x[0]
x[2]
x
(x + 2)
*x
*(x + 2)
Dirección base del arreglo
Dirección del 3er elemento
1er elemento (10)
3er elemento (7)
Ejemplo 2:
int a[5] = {1, 4, -5, 0, 8};
int *p, *q, i;
p = a;
q = &a[3];
i = q – p;
¿Qué valor contendrá la variable i?
Un puntero, cuando apunta a la dirección
base del arreglo, puede ser usado con
suscriptos:
a[i] podría ser representado como p[i]
a[0] a[1] a[2] a[3] a[4]
p[0] p[1] p[2] p[3] p[4]
1
4
-5 0
8
p
Pasaje de un Arreglo como Parámetro
de una Función en C
Siempre el pasaje de los arreglos en C es por
referencia (simulado) ya que lo que se pasa es
el valor de la dirección base del arreglo.
int ar[33];
En la invocación:
modificarArreglo(ar, 33);
es equivalente a:
modificarArreglo(&ar[0], 33);
Pasaje de un Arreglo como Parámetro
de una Función en C
Declaración del parámetro formal
void modificarArreglo(int b[], int max)
{ … }
No hace falta el tamaño, el compilador lo ignora.
Es lo mismo que:
void modificarArreglo(int *b, int max)
{ … }
Pasaje de un Arreglo como Parámetro
de una Función en C
Declaración del prototipo
void modificarArreglo(int [], int);
O bien
void modificarArreglo(int *, int);
Ejemplo
#include <stdio.h>
#define MAX 5
void muestraArreglo(int [], int);
void modificaArreglo(int [], int);
void modificaUnElemento(int *, int);
“ modificarlos son:\n");
int main()
{
}
int a[MAX] = {2, 4, 6, 8, 10};
int i;
printf("Los valores del arreglo antes de”
muestraArreglo(a, MAX);
modificaArreglo(a, MAX);
printf(“Valores del arreglo despues de llamar”
muestraArreglo(a, MAX);
for (i = 0; i < MAX; i++)
printf(“Valores del arreglo despues de llamar”
“ a modificaUnElemento son:\n”);
muestraArreglo(a, MAX);
return 0;
“ a modificaArreglo son:\n”);
modificaUnElemento(&a[i], i);
void muestraArreglo(int b[], int max)
{
int i;
for (i = 0; i < max; i++)
printf("%d ", b[i]);
printf("\n");
}
}
void modificaArreglo(int b[], int max)
{
int i;
for (i = 0; i < max; i++)
b[i] = b[i] + 1;
void modificaUnElemento(int *elem, int pos)
{
*elem = 0;
printf(“El valor del elemento %d dentro”
“de modificaUnElemento es: %d\n”,
pos, *elem);
}
Definiciones alternativas equivalentes
void modificaArreglo(int b[], int max){
int i;
for (i = 0; i < max; i++)
b[i] = b[i] + 1;
}
void modificaArreglo(int *b, int size){
int i;
for (i = 0; i < max; i++)
b[i] = b[i] + 1;
}
void modificaArreglo(int *b, int size){
int i;
for (i = 0; i < max; i++)
*(b + i) = *(b + i) + 1;
}
void modificaArreglo(int b[], int size){
int i;
for (i = 0; i < max; i++)
*(b + i) = *(b + i) + 1;
}
Ejercicio
int a[3] = {5,8,1};
int *p, *q, i;
p = a;
q = &a[1];
i = *p + *q;
*p += *q; /* equiv. *p = *p + *q; */
*(p+1) = 0;
(*(q+1))++;
Pasaje de Arreglos Multidimensionales
como Parámetros de una Función en C
Dado que se trata de arreglos de arreglos, no
hace falta incluir el tamaño de la 1ra
dimensión, pero sí el de las siguientes:
int a[2][3];
void f(int x[][3]){
…
}
Invocación igual que en los unidimensionales
f(a);
Arreglos de Caracteres y Strings en C
Usados como estructura soporte en C para los
strings (cadenas de caracteres).
Características particulares:
Inicialización:
1)
char s[] = “Programacion I”;
char s[] = {‘P’, ‘r’, ‘o’, ‘g’, ‘r’, ‘a’,
‘m’, ‘a’, ‘c’, ‘i’, ‘o’,
‘n’,‘ ’,‘I’,‘\0’};
No todos los arreglos de caracteres representan
strings, solo los terminados en ‘\0’.
Arreglos de Caracteres y Strings en C
2) Lectura de una sola vez:
char cad[10];
scanf(“%s”, cad);
Responsabilidad del programador asegurarse que el
arreglo tenga el tamaño suficiente.
scanf(“%9s”, cad); /* ignora mas
alla de los 9 caracteres leidos */
3)
Impresión de una sola vez:
printf(“%s”, cad); /* hasta que encuentra
el primer carácter ‘\0’ */
Strings, Arreglos de Caracteres y
Punteros a char
char s1[] = “hola”;
char *s2 = “hola”;
s1 y s2 almacenan el string “hola” en un arreglo de 5
s1 y s2 apuntan a la dirección base del correspondiente
posiciones;
arreglo.
s1 es un valor constante ya que siempre representa la
dirección base del arreglo s1, es decir &s1[0].
s1 no puede cambiar su valor, por ej., no podemos hacer s1++
Para copiar un string en otro deberemos copiar elemento
a elemento usando strcpy (en string.h).
REGISTROS
Registros
Llamados también tuplas, estructuras, records,
structs, …
Estructura heterogénea
Selector: identificador de campo del registro (explícito)
Capacidad estática.
Operaciones: asignación e inspección.
No ha
Comentarios de: Programación I - Teoría III (0)
No hay comentarios