TÉCNICAS DE PROGRAMACIÓN
Lenguaje C
Apuntadores y arreglos
2Daniel Finol – ICA - LUZ
APUNTADORES Y ARREGLOS
CAPÍTULO 5 DE KyR
3Daniel Finol – ICA - LUZ
Apuntadores
• Un apuntador es una variable que contiene la dirección de otra variable.
• p = &c• El operador & da la dirección en memoria de un
objeto.– Sólo se aplica a variales y elementos de arreglos.– No sa aplica a: expresiones, registros ni constantes.
4Daniel Finol – ICA - LUZ
Operador unario *
El operador unario * se aplica sólo a apuntadores. Da acceso al objeto al que señala el apuntador. Se llama "indirección" o "desreferencia".
También se usa para declarar a una variable como apuntador.
Ej: int x = 1, y = 2, z[10]; int *ip; /* ip is a pointer to int */
ip = &x; /* ip now points to x */ y = *ip; /* y is now 1 */ *ip = 0; /* x is now 0 */ ip = &z[0]; /* ip now points to z[0] */
5Daniel Finol – ICA - LUZ
Operador unario *
El operador unario * se aplica sólo a apuntadores. Da acceso al objeto al que señala el apuntador. Se llama "indirección" o "desreferencia".
También se usa para declarar a una variable como apuntador.
Ej: int x = 1, y = 2, z[10]; int *ip; /* ip is a pointer to int */
ip = &x; /* ip now points to x */ y = *ip; /* y is now 1 */ *ip = 0; /* x is now 0 */ ip = &z[0]; /* ip now points to z[0] */
*ip es un int
6Daniel Finol – ICA - LUZ
Un apuntador está restringido a señalar a una clase particular de objeto. (Excepción void *).
Ej:
*ip = *ip + 10;
y = *ip + 1
*ip += 1
++*ip
(*ip)++
iq = ip
7Daniel Finol – ICA - LUZ
Apuntadores y argumentos
¿Cómo hacer para que una función llamada altere una variable de la función que la llamó?
Ej: swap(a, b);
void swap(int x, int y) /*MAL: NO SIRVE*/ { int temp;
temp = x; x = y; y = temp; }
8Daniel Finol – ICA - LUZ
Apuntadores y argumentos: Intercambio (swap)
swap(&a, &b);
void swap(int *px, int *py) { int temp;
temp = *px; *px = *py; *py = temp; }
9Daniel Finol – ICA - LUZ
getint int n, array[SIZE], getint(int *);
for (n =0; n< SIZE && getint(&array[n]) !=EOF; n++);
int getint(int *pn) { int c, sign;
while (isspace(c = getch())); if (!isdigit(c) && c != EOF && c != '+' && c != '-') { ungetch(c); /* it is not a number */ return 0; } sign = (c == '-') ? -1 : 1; if (c == '+' || c == '-') c = getch(); for (*pn = 0; isdigit(c), c = getch()) *pn = 10 * *pn + (c - '0'); *pn *= sign; if (c != EOF) ungetch(c); return c;}
10
Daniel Finol – ICA - LUZ
Apuntadores y arreglos
int a[10]; int *pa; pa = &a[0];
x = *pa /*copia el contenido de a[0] en x */
11
Daniel Finol – ICA - LUZ
Apuntadores y arreglos
Si pa apunta a una elemento de un arreglo: pa +1; apunta al siguiente elemento. pa + i; apunta i elementos después de pa. pa - 1; apunta i elementos antes de pa.
Si pa apunta a a[0]: *(pa + 1); se refiere al contenido de a[1]. pa + i; es la dirección de a[i]; *(pa + i); es el contenido de a[i].
Todo esto funciona
independiente del tamaño de los elementos del arreglo a.
12
Daniel Finol – ICA - LUZ
Apuntadores y arreglos
El nombre de un arreglo es un sinónimo de la dirección del primer elemento: pa = &a[0]; es equivalente a: pa = a;
a[i] es equivalente a: *(a + i). &a[i] es equivalente a: a + i. Se pueden usar subíndices con un apuntador:
pa[i] es equivalente a *(pa + i). Diferencia entre nombre de arreglo y apuntador:
pa = a; pa++; son legales. a = pa; a++; son ilegales.
13
Daniel Finol – ICA - LUZ
Apuntadores, arreglos y argumentos. Cuando un nombre de arreglo se pasa a una
función, lo que se pasa es la dirección del primer elemento: Los parámetros formales char s[] y char *s, son
equivalentes. Ej:
int strlen(char *s) { int n;
for (n = 0; *s != '\0', s++) n++; return n; }
strlen("hello, world"); /* string constant */ strlen(array); /* char array[100]*/ strlen(ptr); /* char *ptr; */
14
Daniel Finol – ICA - LUZ
Apuntadores, arreglos y argumentos
Es posible pasar parte de un arreglo a una función, pasando un apuntador al inicio del subarreglo: f(&a[2]); f(a + 2);
La declaración de f puede ser: f(int arr[ ]); f(int *arr);
Para f es indiferente que lo que se le pase sea parte de un arreglo más grande.
15
Daniel Finol – ICA - LUZ
Aritmética de direcciones: alloc y afree
#define ALLOCSIZE 10000static char allocbuf[ALLOCSIZE]; static char *allocp = allocbuf;
char *alloc(int n) {if (allocbuf + ALLOCSIZE - allocp >= n) {
allocp += n; return allocp - n; } else return 0;}
void afree(char *p) { if(p >= allocbuf && p < allocbuf + ALLOCSIZE)
allocp = p;}
16
Daniel Finol – ICA - LUZ
17
Daniel Finol – ICA - LUZ
Aritmética de direcciones
Si dos apuntadores apuntan a elementos del mismo arreglo pueden compararse con: ==, !=, <, >=, etc.
A un apuntador se le puede sumar o restar un entero: p + n. (n se escala).
Dos apuntadores se pueden restar si apuntan al mismo arreglo. Si p < q, entonces: q – p + 1; es el número de elementos desde p a q
inclusive. Un apuntador puede asignarse o compararse
con el entero 0 (NULL).
18
Daniel Finol – ICA - LUZ
Aritmética de direcciones: strlen (nueva versión)
int strlen(char *s) { char *p = s;
while (*p != '\0') p++; return p - s; }
19
Daniel Finol – ICA - LUZ
Apuntadores a caracteres y funciones.
char *pmensaje; pmensaje = "ya es tiempo"; /*No hay copia*/
char amessage[] = "now is the time";
char *pmessage = "now is the time";
¿Qué se puede
modificar y qué no?
20
Daniel Finol – ICA - LUZ
strcpy: v1
void strcpy(char *s, char *t) { int i;
i = 0; while ((s[i] = t[i]) != '\0') i++; }
21
Daniel Finol – ICA - LUZ
strcpy: v2
void strcpy(char *s, char *t) { int i;
i = 0; while ((*s = *t) != '\0') { s++; t++; } }
22
Daniel Finol – ICA - LUZ
strcpy: v3
void strcpy(char *s, char *t) { while ((*s++ = *t++) != '\0') ; }
23
Daniel Finol – ICA - LUZ
strcpy: v4
void strcpy(char *s, char *t) { while (*s++ = *t++) ; }
24
Daniel Finol – ICA - LUZ
strcmp: v1
int strcmp(char *s, char *t) { int i;
for (i = 0; s[i] == t[i]; i++) if (s[i] == '\0') return 0; return s[i] - t[i]; }
25
Daniel Finol – ICA - LUZ
strcmp: v2
int strcmp(char *s, char *t) { for ( ; *s == *t; s++, t++) if (*s == '\0') return 0; return *s - *t; }
26
Daniel Finol – ICA - LUZ
Quicksort
void qsort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j);
if (left >= right) return; swap(v, left, (left + right)/2); last = left; for (i = left + 1; i <= right; i++) if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); qsort(v, left, last-1); qsort(v, last+1, right); }
27
Daniel Finol – ICA - LUZ
swap
void swap(int v[], int i, int j) { int temp;
temp = v[i]; v[i] = v[j]; v[j] = temp; }
28
Daniel Finol – ICA - LUZ
Arreglos de apuntadpres y apuntadores a apuntadores#include <stdio.h>#include <string.h>
#define MAXLINES 5000char *lineptr[MAXLINES]; int readlines(char *lineptr[], int nlines);void writelines(char *lineptr[], int nlines);void qsort(char *lineptr[], int left, int right);
main(){ int nlines; if ((nlines = readlines(lineptr, MAXLINES)) >= 0) { qsort(lineptr, 0, nlines-1); writelines(lineptr, nlines); return 0; } else { printf("error: input too big to sort\n"); return 1; }}
29
Daniel Finol – ICA - LUZ
readlines#define MAXLEN 1000 int getline(char *, int);char *alloc(int);
/* readlines: read input lines */int readlines(char *lineptr[], int maxlines){ int len, nlines; char *p, line[MAXLEN];
nlines = 0; while ((len = getline(line, MAXLEN)) > 0) if (nlines >= maxlines || p = alloc(len) == NULL) return -1; else { line[len-1] = '\0'; /* delete newline */ strcpy(p, line); lineptr[nlines++] = p; } return nlines;}
30
Daniel Finol – ICA - LUZ
writelines /* writelines: write output lines */ void writelines(char *lineptr[], int nlines) { int i;
for (i = 0; i < nlines; i++) printf("%s\n", lineptr[i]); }
void writelines(char *lineptr[], int nlines) { while (nlines-- > 0) printf("%s\n", *lineptr++); }
31
Daniel Finol – ICA - LUZ
Quicksort
void qsort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j);
if (left >= right) return; swap(v, left, (left + right)/2); last = left; for (i = left + 1; i <= right; i++) if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); qsort(v, left, last-1); qsort(v, last+1, right); }
32
Daniel Finol – ICA - LUZ
Quicksort para cadenas
void qsort(char *v[], int left, int right) { int i, last; void swap(char *v[], int i, int j);
if (left >= right) return; swap(v, left, (left + right)/2); last = left; for (i = left + 1; i <= right; i++) if (strcmp(v[i], v[left]) < 0) swap(v, ++last, i); swap(v, left, last); qsort(v, left, last-1); qsort(v, last+1, right); }
33
Daniel Finol – ICA - LUZ
swap
void swap(char *v[], int i, int j) { char *temp;
temp = v[i]; v[i] = v[j]; v[j] = temp; }
Sería mucho más costoso en tiempo de ejecución y más engorroso en manejo del
almacenamiento tener que mover las cadenas completas
34
Daniel Finol – ICA - LUZ
Arreglos multidimensionalesstatic char daytab[2][13] = { {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} };
int day_of_year(int year, int month, int day) { int i, leap; leap = year%4 == 0 && year%100 != 0 || year%400==0; for (i = 1; i < month; i++) day += daytab[leap][i]; return day;}
void diaMes(int year, int yearday, int* pmonth,int *pday){ int i, leap;
leap = year%4 == 0 && year%100 != 0 || year%400 == 0; for (i = 1; yearday > daytab[leap][i]; i++) yearday -= daytab[leap][i]; *pmonth = i; *pday = yearday;}
35
Daniel Finol – ICA - LUZ
Inicialización de arreglos a apuntadoreschar *month_name(int n){ static char *name[] = { "Mes Ilegal", "Enero", "Febrero", "Marzo", "Abril", "Mayo", "Junio", "Julio", "Agosto", "Septiembre", "Octubre", "Noviembre", "Diciembre" };
return (n < 1 || n > 12) ? name[0] : name[n];}
36
Daniel Finol – ICA - LUZ
Apuntadores versus Arreglos Multidimensionales int a[10][20]; int *b[10]; Tanto a[3][4] como b[3][4] son válidas. Para a:
se han reservado 200 localidades de memoria de tamaño de un int.
esas localidades son contiguas. se almacenan por filas. para ubicar el elemento a[fila][col] se usa la fórmula:
#columnas * fila + col Para b:
sólo existen espacios para 10 apuntadores si cada elem. de b apunta a un arreglo de 20, habrá 200 ints
reservados + 10 espacios para los apuntadores. La ventaja del arreglo de apuntadores es que cada
fila puede ser de tamaño distinto.
37
Daniel Finol – ICA - LUZ
Apuntadores versus Arreglos Multidimensionales
char *name[] = { "Illegal month", "Jan", "Feb", "Mar" };
char aname[][15] = { "Illegal month", "Jan", "Feb", "Mar" };
38
Daniel Finol – ICA - LUZ
Argumentos de la línea de comandos
echo hello, world hello, world main(int argc, char *argv[])
39
Daniel Finol – ICA - LUZ
Argumentos de la línea de comandos: echomain(int argc, char *argv[]) { int i;
for (i = 1; i < argc; i++) printf("%s%s", argv[i], (i < argc-1) ? " " : ""); printf("\n"); return 0;}
main(int argc, char *argv[]) { while (--argc > 0) printf("%s%s", *++argv, (argc > 1) ? " " : ""); printf("\n"); return 0;}
printf((argc > 1) ? "%s " : "%s", *++argv);
40
Daniel Finol – ICA - LUZ
#include <stdio.h> #include <string.h> #define MAXLINE 1000
int getline(char *line, int max);
main(int argc, char *argv[]) { char line[MAXLINE]; int found = 0;
if (argc != 2) printf("Usage: find pattern\n"); else while (getline(line, MAXLINE) > 0) if (strstr(line, argv[1]) != NULL) { printf("%s", line); found++; } return found; }
41
Daniel Finol – ICA - LUZ
main(int argc, char *argv[]) { char line[MAXLINE]; long lineno = 0; int c, except = 0, number = 0, found = 0; while (--argc > 0 && (*++argv)[0] == '-') while (c = *++argv[0]) switch (c) { case 'x': except = 1; break; case 'n': number = 1; break; default: printf("find: illegal option %c\n", c); argc = 0; found = -1; break; } if (argc != 1) printf("Usage: find -x -n pattern\n"); else while (getline(line, MAXLINE) > 0) { lineno++; if ((strstr(line, *argv) != NULL) != except) { if (number) printf("%ld:", lineno); printf("%s", line); found++; } } return found;}
42
Daniel Finol – ICA - LUZ
Apuntadores a funciones #include <stdio.h> #include <string.h> #define MAXLINES 5000 /* max #lines to be sorted */ char *lineptr[MAXLINES]; /* pointers to text lines */
int readlines(char *lineptr[], int nlines); void writelines(char *lineptr[], int nlines); void qsort(void *lineptr[], int left, int right, int (*comp)(void *, void *)); int numcmp(char *, char *);
main(int argc, char *argv[]) { int nlines; /* number of input lines read */ int numeric = 0; /* 1 if numeric sort */
if (argc > 1 && strcmp(argv[1], "-n") == 0) numeric = 1; if ((nlines = readlines(lineptr, MAXLINES)) >= 0) { qsort((void**) lineptr, 0, nlines-1, (int (*)(void*,void*))(numeric ? numcmp :
strcmp)); writelines(lineptr, nlines); return 0; } else { printf("input too big to sort\n"); return 1; } }
43
Daniel Finol – ICA - LUZ
Quicksort – más genérico void qsort(void *v[], int left, int right, int (*comp)(void *, void *)) { int i, last;
void swap(void *v[], int, int);
if (left >= right) return; swap(v, left, (left + right)/2); last = left; for (i = left+1; i <= right; i++) if ((*comp)(v[i], v[left]) < 0) swap(v, ++last, i); swap(v, left, last); qsort(v, left, last-1, comp); qsort(v, last+1, right, comp); }
44
Daniel Finol – ICA - LUZ
int numcmp(char *s1, char *s2) { double v1, v2;
v1 = atof(s1); v2 = atof(s2); if (v1 < v2) return -1; else if (v1 > v2) return 1; else return 0; }
void swap(void *v[], int i, int j;) { void *temp;
temp = v[i]; v[i] = v[j]; v[j] = temp; }