Programming in C and C++
3. Pointers and Structures
Dr. Neel Krishnaswami
University of Cambridge
(based on notes from and with thanks to Anil Madhavapeddy, Alan Mycroft,
Alastair Beresford and Andrew Moore)
Michaelmas Term 2016-2017
Pointers
I Computer memory is often abstracted as a sequence of bytes,
grouped into words
I Each byte has a unique address or index into this sequence
I The size of a word (and byte!) determines the size of addressable
memory in the machine
I A pointer in C is a variable which contains the memory address of
another variable (this can, itself, be a pointer)
I Pointers are declared or defined using an asterisk(*); for example:
char *pc; or int **ppi;
I The asterisk binds to the variable name, not the type specifier; for
example char *pc,c;
I A pointer does not necessarily take the same amount of storage space
as the type it points to
2 / 25
Example
int **ppi
char *pc
int *pi
char c
int i
00 00 52 00
00 00 1c 00 41 Little
... ... ...
00 00 42 00 41 Big
38 4c 05 62
0x2c
0x30
0x34
0x38
0x4c
0x50
0x60
3 / 25
Manipulating pointers
I The value “pointed to” by a pointer can be “retrieved” or
dereferenced by using the unary * operator; for example:
int *p = ...
int x = *p;
I The memory address of a variable is returned with the unary
ampersand (&) operator; for example
int *p = &x;
I Dereferenced pointer values can be used in normal expressions; for
example: *pi += 5; or (*pi)++
4 / 25
Example
1 #include <stdio.h>
2
3 int main(void) {
4 int x=1,y=2;
5 int *pi;
6 int **ppi;
7
8 pi = &x; ppi = π
9 printf("%p, %p, %d=%d=%d\n",ppi,pi,x,*pi,**ppi);
10 pi = &y;
11 printf("%p, %p, %d=%d=%d\n",ppi,pi,y,*pi,**ppi);
12
13 return 0;
14 }
5 / 25
Pointers and arrays
I A C array uses consecutive memory addresses without padding to
store data
I An array name (used in an expression without an index) represents
the memory address of the first element of the array; for example:
char c[10];
char *pc = c; is the same as
char *pc = &c[0];
I Pointers can be used to “index” into any element of an array; for
example:
int i[10];
int *pi = &i[5];
6 / 25
Pointer arithmetic
I Pointer arithmetic can be used to adjust where a pointer points; for
example, if pc points to the first element of an array, after executing
pc+=3; then pc points to the fourth element
I A pointer can even be dereferenced using array notation; for example
pc[2] represents the value of the array element which is two elements
beyond the array element currently pointed to by pc
I In summary, for an array c, *(c+i)≡c[i] and c+i≡&c[i]
I A pointer is a variable, but an array name is not; therefore pc=c and
pc++ are valid, but c=pc and c++ are not
7 / 25
Example
1 #include <stdio.h>
2
3 int main(void) {
4 char str[] = "A string.";
5 char *pc = str;
6
7 printf("%c %c %c\n",str[0],*pc,pc[3]);
8 pc += 2;
9 printf("%c %c %c\n",*pc, pc[2], pc[5]);
10
11 return 0;
12 }
8 / 25
Pointers as function arguments
I Recall that all arguments to a function are copied, i.e.
passed-by-value; modification of the local value does not affect the
original
I In the second lecture we defined functions which took an array as an
argument; for example void reverse(char s[])
I Why, then, does reverse affect the values of the array after the
function returns (i.e. the array values haven’t been copied)?
I because s is re-written to char *s and the caller implicitly passes a
pointer to the start of the array
I Pointers of any type can be passed as parameters and return types of
functions
I Pointers allow a function to alter parameters passed to it
9 / 25
Example
I Compare swp1(a,b) with swp2(&a,&b):
1 void swp1(int x,int y) 1 void swp2(int *px,int *py)
2 { 2 {
3 int temp = x; 3 int temp = *px;
4 x = y; 4 *px = *py;
5 y = temp; 5 *py = temp;
6 } 6 }
10 / 25
Arrays of pointers
I C allows the creation of arrays of pointers; for example
int *a[5];
I Arrays of pointers are particularly useful with strings
I An example is C support of command line arguments:
int main(int argc, char *argv[]) { ... }
I In this case argv is an array of character pointers, and argc tells the
programmer the length of the array
11 / 25
Example
argv: argv[0] progname\0
argv[1] firstarg\0
argc: 3
argv[2] secondarg\0
argv[3] NULL
12 / 25
Multi-dimensional arrays
I Multi-dimensional arrays can be declared in C; for example:
int i[5][10];
I Values of the array can be accessed using square brackets; for
example: i[3][2]
I When passing a two dimensional array to a function, the first
dimension is not needed; for example, the following are equivalent:
void f(int i[5][10]) { ... }
void f(int i[][10]) { ... }
void f(int (*i)[10]) { ... }
I In arrays with higher dimensionality, all but the first dimension must
be specified
13 / 25
Pointers to functions
I C allows the programmer to use pointers to functions
I This allows functions to be passed as arguments to functions
I For example, we may wish to parameterise a sort algorithm on
different comparison operators (e.g. lexicographically or numerically)
I If the sort routine accepts a pointer to a function, the sort routine can
call this function when deciding how to order values
14 / 25
Example
1 void sort(int a[], const int len,
2 int (*compare)(int, int))
3 {
4 int i,j,tmp;
5 for(i=0;i<len-1;i++)
6 for(j=0;j<len-1-i;j++)
7 if ((*compare)(a[j],a[j+1]))
8 tmp=a[j], a[j]=a[j+1], a[j+1]=tmp;
9 }
10
11 int inc(int a, int b) {
12 return a > b ? 1 : 0;
13 }
Source of some confusion: either or both of the *s in *compare may be
omitted due to language (over-)generosity.
15 / 25
Example
1 #include <stdio.h>
2 #include "example8.h"
3
4 int main(void) {
5 int a[] = {1,4,3,2,5};
6 unsigned int len = 5;
7 sort(a,len,inc); //or sort(a,len,&inc);
8
9 int *pa = a; //C99
10 printf("[");
11 while (len--)
12 printf("%d%s",*pa++,len?" ":"");
13 printf("]\n");
14
15 return 0;
16 }
16 / 25
The void * pointer
I C has a “typeless” or “generic” pointer: void *p
I This can be a pointer to any object (but not legally to a function)
I This can be useful when dealing with dynamic memory
I Enables “polymorphic” code; for example:
1 sort(void *p, const unsigned int len,
2 int (*comp)(void *,void *));
I However this is also a big “hole” in the type system
I Therefore void * pointers should only be used where necessary
17 / 25
Structure declaration
I A structure is a collection of one or more members (fields)
I It provides a simple method of abstraction and grouping
I A structure may itself contain structures
I A structure can be assigned to, as well as passed to, and returned
from functions
I We declare a structure using the keyword struct
I For example, to declare a structure circle we write
struct circle {int x; int y; unsigned int r;};
I Declaring a structure creates a new type
18 / 25
Structure definition
I To define an instance of the structure circle we write
struct circle c;
I A structure can also be initialised with values:
struct circle c = {12, 23, 5};
I An automatic, or local, structure variable can be initialised by
function call:
struct circle c = circle_init();
I A structure can declared, and several instances defined in one go:
struct circle {int x; int y; unsigned int r;} a, b;
19 / 25
Member access
I A structure member can be accessed using ‘.’ notation:
structname.member; for example: vect.x
I Comparison (e.g. vect1 > vect2) is undefined
I Pointers to structures may be defined; for example:
struct circle *pc
I When using a pointer to a struct, member access can be achieved
with the ‘.’ operator, but can look clumsy; for example: (*pc).x
I Equivalently, the ‘->’ operator can be used; for example: pc->x
20 / 25
Self-referential structures
I A structure declaration cannot contain itself as a member, but it can
contain a member which is a pointer whose type is the structure
declaration itself
I This means we can build recursive data structures; for example:
1 struct tree {
1 struct link {
2 int val;
2 int val;
3 struct tree *left;
3 struct link *next;
4 struct tree *right;
4 }
5 }
21 / 25
Unions
I A union variable is a single variable which can hold one of a number
of different types
I A union variable is declared using a notation similar to structures;
for example: union u { int i; float f; char c;};
I The size of a union variable is the size of its largest member
I The type held can change during program execution
I The type retrieved must be the type most recently stored
I Member access to unions is the same as for structures (‘.’ and ‘->’)
I Unions can be nested inside structures, and vice versa
22 / 25
Bit fields
I Bit fields allow low-level access to individual bits of a word
I Useful when memory is limited, or to interact with hardware
I A bit field is specified inside a struct by appending a declaration with
a colon (:) and number of bits; for example:
struct fields { int f1 : 2; int f2 : 3;};
I Members are accessed in the same way as for structs and unions
I A bit field member does not have an address (no & operator)
I Lots of details about bit fields are implementation specific:
I word boundary overlap & alignment, assignment direction, etc.
23 / 25
Example (adapted from K&R)
1 struct { /* a compiler symbol table */
2 char *name;
3 struct {
4 unsigned int is_keyword : 1;
5 unsigned int is_extern : 1;
6 unsigned int is_static : 1;
7 ...
8 } flags;
9 int utype;
10 union {
11 int ival; /* accessed as symtab[i].u.ival */
12 float fval;
13 char *sval;
14 } u;
15 } symtab[NSYM];
24 / 25
Exercises
1. If p is a pointer, what does p[-2] mean? When is this legal?
2. Write a string search function with a declaration of
char *strfind(const char *s, const char *f);
which returns a pointer to first occurrence of the string s in the string f
(and NULL otherwise)
3. If p is a pointer to a structure, write some C code which uses all the
following code snippets: “++p->i”, “p++->i”, “*p->i”, “*p->i++”,
“(*p->i)++” and “*p++->i”; describe the action of each code snippet
4. Write a program calc which evaluates a reverse Polish expression given on
the command line; for example
$ calc 2 3 4 + *
should print 14 (K&R Exercise 5-10)
25 / 25
