Imperative Programming
Lesson 12
Arrays of pointers
Today we will…
• Learn about arrays of pointers.
• Use arrays of pointers to char to
implement arrays of variable
length strings.
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
2
The array of city names
• In its current implementation, all the
strings have the same capacity.
• On the other hand, the city names are
not all of the same length.
• Therefore, we waste a lot of memory.
• Watch the diagram on the next page.
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
3
Memory layout, matrix form
• This represents an array with
strings whose capacity is 16:
l
i
s
b
o
p
o
r
t
o
c
o
i
m
b
f
a
r
o
v
i
l
a
b
e
j
a
c
a
s
t
e
b
r
a
g
a
15 April 2011
a
r
a
r
e
l
o
a
l
b
r
a
n
c
o
Imperative Programming - 12 © Pedro Guerreiro
4
Example: bubblesort
• Here’s how we program bubblesort for
the array of city names:
void bubblesort_cities (void)
#define MAX_CITIES 200
{
#define MAX_LEN 32
int i;
int j;
char cities[MAX_CITIES][MAX_LEN];
for (i = 1; i < n_cities; i++)
int n_cities;
for (j = n_cities-1; j >= i; j--)
if (strcmp (cities[j-1], cities[j]) > 0)
{
Strings swap using the
char m [MAX_LEN];
familiar triangular
strcpy (m, cities[j-1]);
rotation, with string
assigment made with
strcpy (cities[j-1], cities[j]);
strcpy.
strcpy (cities[j], m);
}
Imperative Programming - 12 © Pedro Guerreiro
5
}15 April 2011
Testing read and write
• Here is a simple test function:
faro
coimbra
aveiro
void test_read_write_cities (void)
viseu
{
^Z
read_cities ();
faro
write_cities ();
coimbra
}
aveiro
void read_cities (void)
viseu
{
void write_cities (void)
char line [1024];
{
int i = 0;
int i;
while (fgets (line, 1024, stdin) != NULL)
for (i = 0; i < n_cities; i++)
strcpy (cities[i++], str_pop_last(line));
printf ("%s\n", cities[i]);
n_cities = i;
}
}
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
6
str_pop_last
• It removes the last character of a nonempty string and returns a pointer to the
modified string, i.e., the string passed in the
argument.
15 April 2011
char *str_pop_last (char *s)
{
char *p = s;
assert (*s);
It’s similar to str_remove, but it is
while (*p)
not void and the result can be
p++;
used immediately, for example as
an argument to another function,
*(p-1) = '\0';
as in the previous page.
return s;
}Imperative Programming - 12 © Pedro Guerreiro
7
Testing bubblesort
void test_bubblesort_cities (void)
{
read_cities ();
bubblesort_cities ();
write_cities ();
}
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
coimbra
faro
aveiro
braga
viseu
porto
leiria
guarda
^Z
aveiro
braga
coimbra
faro
guarda
leiria
porto
viseu
8
Arrays of pointers
• Instead of using an array of strings with
fixed capacity, let us use an array of
pointers to char.
• Then, for each string that we get, we add
to the array a pointer to a dynamic copy of
the string, with just the required capacity.
• The memory for each string is allocated
dynamically, that is, by explicit request of
the running program, and not statically, by
the compiler.
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
9
Watching arrays of pointers
• Consider the new declaration:
char cities[MAX_CITIES][MAX_LEN];
int n_cities;
char *p_cities [MAX_CITIES];
• Watch:
0
14759616
14759616
1
14759616
14759648
2
14759616
14759680
10
14759616
14759936
100
14759616
14762816
^Z
void test_show_addresses (void)
{
int x;
while (scanf ("%d", &x) != EOF)
{
printf ("%d %d\n", cities, p_cities);
printf ("%d %d\n", cities+x, p_cities+x);
}
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
}
14758816
14758816
14758816
14758820
14758816
14758824
14758816
14758856
14758816
14759216
10
Dynamic string copy
• Watch very carefully:
char *str_new (const char *s)
{
return strcpy ((char *) malloc (strlen(s) + 1), s);
}
Function malloc allocates in the
free memory a contiguous block
with the number of bytes passed in
the argument, and returns the
memory address of that block.
15 April 2011
There is also a similar function
called calloc: calloc (x, y) returns
a points to a dynamically
allocated memory space for an
array of x objects, each of size y.
Additionally, the memory space is
cleared (all bits become zero).
Imperative Programming - 12 © Pedro Guerreiro
11
Watching str_new
• Each time str_new is called, a new
block of memory is allocated:
void test_str_new (void)
{
char line [1024];
char *p;
while (fgets (line, 1024, stdin) != NULL)
{
str_remove (line);
printf ("%d %s\n", line, line);
p = str_new (line);
printf ("%d %s\n", p, p);
}
}
15 April 2011
carapau
3208992 carapau
1841944 carapau
sardinha
3208992 sardinha
1849640 sardinha
rodovalho
3208992 rodovalho
1849664 rodovalho
bacalhau da noruega
3208992 bacalhau da noruega
1849688 bacalhau da noruega
faneca
3208992 faneca
1849720 faneca
Imperative Programming - 12 © Pedro Guerreiro
12
Reading arrays of strings
• The array argument is an array of pointers.
We are not constrained by the length of the
strings that are being read:
int read_strings (char **v)
{
As a matter of fact, this only works well
if the lines are not longer than 1023…
char **p = v;
char line [1024];
while (fgets (line, 1024, stdin) != NULL)
*p++ = str_new (str_pop_last (line));
return p-v;
}
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
13
Testing with city names
• We now use the array of pointers:
void test_read_write_strings (void)
{
n_cities = read_strings (p_cities);
write_strings (p_cities, n_cities);
}
void write_strings (char **v, int n)
{
while (n--)
printf ("%s\n", *v++);
}
15 April 2011
faro
coimbra
aveiro
viseu
^Z
faro
coimbra
aveiro
viseu
Writing an array of
pointers.
Imperative Programming - 12 © Pedro Guerreiro
14
Memory layout, with pointers
l
i
s
b
o
a
f
p
c
o
i
m
b
r
e
j
c
15 April 2011
a
a
s
t
e
r
t
r
o
o
a
v
b
o
a
i
b
r
l
o
l
a
a
r
g
a
b
r
Imperative Programming - 12 © Pedro Guerreiro
a
e
n
a
c
l
o
15
Bubblesort of pointers
• We do not have to swap the strings: it
is enough to swap the pointers.
void bubblesort_strings (char **v, int n)
{
int i;
int j;
Swapping the pointers is more
for (i = 1; i < n; i++)
efficient that swapping the
for (j = n-1; j >= i; j--)
actual strings, of course!
if (strcmp (v[j-1], v[j]) > 0)
{
char* m = v[j-1];
v[j-1] = v[j];
v[j] = m;
}
}
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
16
Memory layout, after sorting
l
i
s
b
o
a
f
p
c
o
i
m
b
r
e
j
c
a
a
s
t
e
r
t
r
o
o
a
v
b
o
a
i
b
r
l
o
l
a
a
r
g
a
b
r
a
e
n
a
c
l
o
The array elements, which represent the addresses
of the strings in memory have changed positions but
the strings in memory have stayed put.
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
17
faro
tavira
albufeira
lagos
vila do bispo
alcoutim
^Z
faro
tavira
albufeira
void test_show_addresses_2 (void)
lagos
{
vila do bispo
alcoutim
int x;
0
n_cities = read_strings (p_cities);
3552160 3552160
2169624 faro
write_strings (p_cities, n_cities);
1
while (scanf ("%d", &x) != EOF)
3552160 3552164
{
2173216 tavira
2
printf ("%d %d\n", p_cities, p_cities+x);
3552160 3552168
printf ("%d %s\n", p_cities[x], p_cities[x]);
2173232 albufeira
3
}
3552160 3552172
}
2173256 lagos
4
3552160 3552176
2173272 vila do bispo
5
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
3552160 3552180
2173296 alcoutim
Watching the
memory layout
18
Testing
• Here’s an example, using local
morango
array of fruits:
void test_bubblesort_strings_1 (void)
{
char *fruits [100];
int n_fruits = read_strings (fruits);
bubblesort_strings (fruits, n_fruits);
write_strings (fruits, n_fruits);
}
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
laranja
banana
uva
tangerina
ameixa
quivi
^Z
ameixa
banana
laranja
morango
quivi
tangerina
uva
19
uva
pera
laranja
morango
quivi
banana
^Z
uva
pera
void test_show_bubblesort_pointers (void)
laranja
{
morango
char *fruits [100];
quivi
banana
int n_fruits;
0 7609112
int i;
1 7612704
2 7612720
n_fruits = read_strings (fruits);
3 7612736
write_strings (fruits, n_fruits);
4 7612752
5 7612768
for (i = 0; i < n_fruits; i++)
banana
printf ("%d %d %s\n", i, fruits[i], fruits[i]);
laranja
bubblesort_strings (fruits, n_fruits);
morango
pera
write_strings (fruits, n_fruits);
quivi
for (i = 0; i < n_fruits; i++)
uva
0 7612768
printf ("%d %d %s\n", i, fruits[i], fruits[i]);
1 7612720
}
2 7612736
3 7612704
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
4 7612752
5 7609112
Watching the
sorted addresses
uva
pera
laranja
morango
quivi
banana
banana
laranja
morango
pera
quivi
uva
20
Funny, common error
• If we forget the dynamic copy of the
string that was read, all the pointers in
the array refer the same memory cell,
which may be not available anymore:
int read_strings_w (char **v)
{
char **p = v;
char line [1024];
while (fgets (line, 1024, stdin) != NULL)
*p++ = str_pop_last (line);
return p-v;
}
This is what we get, if we use the above
function for reading the array in the test
function
in the Programming
previous page.
15 April 2011
Imperative
- 12 © Pedro Guerreiro
laranja
figo
banana
morango
ameixa
^Z
ameixa
ameixa
ameixa
ameixa
ameixa
21
Exercises
• Program bubblesort for an array of
structures, where one of the members
is a string. Sort by the string.
• Program a function that removes all
characters from a string, after (and
including) the first ocurrence of a given
character.
• Program a function that removes from
a given string all the occurrences of
characters present in another given
string.
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
22
Control
• What is the difference between
malloc and calloc?
• Which are the arguments of fgets? In
which order do they appear?
• How many bytes in memory does an
array of 100 pointers occupy?
• What happens when we forget
dynamic memory allocation when
reading strings to arrays of pointers.
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
23
Tomorrow
• We will learn about using text
files, other than stdin and stdout.
• We will learn about defining new
types.
15 April 2011
Imperative Programming - 12 © Pedro Guerreiro
24