Imperative Programming
(C & C++) II
Yinong Chen
Additions by Ruben Acuña
Last updated: 1/4/21
Learning Outcomes
• LO1: Develop a C program that performs basic use of pointers.
• LO1.1: Describe the basic concept of a pointer.
• LO1.2: Apply knowledge of pointer operators to trace the contents of pointer variables.
• LO1.3: Interpret a program using pointers on strings.
• LO1.4: Interpret a program using pointers on multi-dimensional arrays.
• LO1.5: Compare and contrast pointer types with unsigned integers.
• LO2: Interpret a program using an array of strings.
• LO2.1: Describe the limitations of using string literals.
• LO2.2: Interpret a program using an array of strings.
• LO3: Describe common mechanisms in C and C++ for defining new types.
• LO3.1: Interpret a program using macros and keyword const to define constants.
• LO3.2: Interpret a program using typedef enumerations.
• LO3.3: Interpret a program using structures.
• LO4: Develop a C program with flow control, arrays, pointers, structs, and console I/O.
Pointer Basics
LO1: Develop a C program that performs basic use of pointers.
LO1.1: Describe the basic concept of a pointer.
LO1.2: Apply knowledge of pointer operators to trace the contents of pointer variables.
LO1.3: Interpret a program using pointers on strings.
LO1.4: Interpret a program using pointers on multi-dimensional arrays.
LO1.5: Compare and contrast pointer types with unsigned integers.
The Concept: Library Collections
Let’s consider the different aspects of a variable and relate them to a real-
world scenario: the books and shelves in a library.
• Value stored in the variable (book).
• Location in which the value is stored (a place on some bookshelf).
• Address (floor number + shelf number + location number): Use by human or
hardware to access the memory location where the variable value is stored.
• Name (name of the book: e.g., “Introduction to C”, “Land of LISP”); Not all
locations have a name.
A pointer is a variable that contains the address of another variable:
• Pointer (a catalog entry for a book). A pointer is also a variable, thus it has
• Value: data (book location address) saved somewhere.
• Location (an entry in the library database).
• Address: an index number associated with the entry’s location.
• Name: some location could be given a name, e.g., “newest book on C”.
The Concept:
• Variable names are simply binding a physical memory address to a
human readable symbol (name).
• Humans are good at remembering names.
• Machines can handle addresses (numbers) only.
• Although we are used to manipulating names to obtain data, we can
also use the underlying addresses which have some structure.
• Direct manipulation of addresses can be useful!
• Let’s construct large collections of data.
• Let’s access something from anywhere.
If we use a variable to store an address, it is called a pointer type.
Careful: all variables store a value at some address. It’s just that
sometimes that value at that address is itself an address.
Example:
int x=5, *y=&x;
*y = 49;
The Concept: C Notation
Operations on pointer variables:
• An address value can be assigned to a pointer variable.
• The address stored in a pointer variable can be modified.
• Referencing: Obtain the address of a variable from its name.
• Dereferencing: Returns the value pointed at by a pointer.
C has unary 2 pointer operations: & and *
& is a referencing operator that returns the address value of the
variable it precedes. If y = &x;, then &x is called a “r-value”.
* returns the value at the address stored by the variable it
precedes. If *y = 5;, then *y is called a “l-value” (locator value).
Note: r-value means a pure value that can occur on the right of an assignment,
while l-value means an variable that can occur on left and right of an assignment.
They are (in general) complementary:
• * converts pointer to address &(*p) → p
• & converts address to variable content *(&x) → x 6
This is not a
logical and!
The Concept: Box and Arrow Notation
It can be hard to understand how
the different variables in a program
using pointers are related.
To help, we sometimes use box and
arrow notation: a box indicates a
storage location, and an arrow
indicates that the value in a location
is actually the address of some other
location.
If we want, we can visualize the
boxes as locations in main memory.
var1
var2
…
5
1104
…
var1
var2
1104
1108
1112
1116
1120
int var1 = 5;
int *var2 = &var1;
5
Pointer Tracing: Example 0
Notice that an asterisk is used to denote a pointer type, but it is also
used for dereferencing.
8
int y = 10;
int* yptr;
int *xptr; // Is there a difference between int* vs. int *xptr?
yptr = &y;
xptr = &y; // Is this legal?
*yptr = 20; // Dereferencing?
*xptr = 30; // What is the value of y? 10 or 20 or 30
Pointer Tracing: Example 1
Let’s try tracing the contents of memory as a program
runs line by line.
Assume that the address of x is 2000.
1: int x=500, *y;
2: y = &x;
3: *y = 100;
4: y = y + 10;
5: *y = 100;
After Line x y
1 500 3232978
2
3
4
5
Potentially a
random value
Pointer Tracing: Example 2
137
i
100
j = &i
160
k = &j
120
k = &&i
is not
valid &i is a r-value
j is the name of a variable
*k
*k is a name of the
variable whose address
is in k. *k is an alias of j
int i = 137, *j, **k;
j = &i;
k= &j;
**k = 0;
**k
**k is a name of the
variable whose address
is in *k. **k is an alias of *j
and a alias of i
*j
**k
100160
 i
jk
What happens if you
declare *k, instead?
100
104
108
112
116
120
124
128
i
j
k
initial
12
104
0
i
j
k
24
0
i
j
k 112
i
j
k
48 i
j
k
j = &i *j = 24 k = &j **k = 48
12
0
0
int i = 12, * j = 0, ** k = 0; // initialization j = 0, k = 0
printf("i = %d, j = %d, k = %d\n", i, j, k); // i = 12, j = 0, k = 0
j = &i;
*j = 24; // Are we modifying j or *j?
k = &j;
**k = 48;
printf("i = %d, j = %d, k = %d\n", i, j, k);
What is the difference?
int **k = 0;
**k = 0;Pointer Tracing: Example 3
Although a pointer can point to a variable of any type, it is
especially common for complex/compound types. Why?
12
void main() {
char *p = "hello", *s = "this is a str";
p = s;
printf("%s\n", p);
}
p s
e
0x10
0x11
0x12
0x13
0x14
0x15
h
l
l
o
\0
h
t
i
s
i
s
a
s
t
r
\0
0x40
0x41
0x42
0x43
0x44
0x45
0x46
0x47
0x48
…
String Usage
The strings are created implicitly: p and s expect an address. The
syntax above creates the strings as arrays in memory and saves the
address of where that array starts as the pointer values.
Afterward, p and s are the addresses of the first characters that
appear on right side.
String Usage: Brackets to Pointers
Practice: given the array version, rewrite the program using pointers.
#include
#include
void main() {
int n = 0, len;
char str[] = "hello world";
len = strlen(str);
for (n = 0; n < len; n++)
putc(str[n], stdout);
printf("\nn = %d\n", n);
}
#include
void main() {
// int n=0;
char ___ = "hello world";
while (____) {
putc(____, stdout);
____;
}
printf("\np = %d", *p);
printf("\np = %d\n", p);
}
String Usage: Brackets to Pointers
Why might we want to use pointer version? Pointer is a little faster.
• Array: Internally it looks like str+n*sizeof(entry) to access str[n].
• Pointer: p is the direct address of str[n]. Moving forward is just an addition.
#include
void main() {
// int n=0;
char *p = "hello world";
while (*p!=‘\0’) {
putc(*p, stdout);
p++;
}
printf("\np = %d", *p);
printf("\np = %d\n", p);
}
Multi-Dimension Arrays
There are a two ways a multi-dimension array can be structured in memory:
• If it is allocated statically (i.e., we define all dimensions in advance), then
the memory is contiguous. In this case, the name of the array is the initial
address of the entire multi-dimension array.
• If it is allocated dynamically (i.e., size defined at run-time), then memory
will be fragmented. In this case, the name of the array is the initial address
of a series of addresses that lead to each other part of the array.
Next, we’ll look at an example using contiguous allocation.
Contiguous
arr[0][0]
arr[0][1]
arr[1][0]
arr[1][1]
Fragmented
ma[0]
ma[1]
…
arr[][0]
arr[][1]
…
arr[][0]
arr[][1]
Multi-Dimension Arrays
Memory
ma[0][0] a
ma[0][1] b
ma[0][2] c
ma[0][3] d
ma[1][0] e
ma[1][1] f
ma[1][2] g
ma[1][3] \0
char* p = 0;
char ma[2][4]; // 0123
ma[0][0] = 'a'; //0: abcd
ma[0][1] = 'b'; //1: efg\0
ma[0][2] = 'c';
ma[0][3] = 'd';
ma[1][0] = 'e';
ma[1][1] = 'f';
ma[1][2] = 'g';
ma[1][3] = '\0';
p = ma;
while (*p) {
printf("%c", *p);
*p = *p + 1; p++;
}
printf("\n");
p = &ma[0][0];
while (*p != 0) printf("%c", *p++);
Depending on the language, 2D arrays are stored in different ways.
C uses row-major order, where rows are stored one after another.
Pointer Types versus Unsigned Int:
Are they equivalent?
#include
void main() {
unsigned int n1 = 4, n2 = 8, * pn1 = &n1, * pn2 = &n2;
printf("ptr-size = %d, ", sizeof(pn1)); //1
printf("uint-size = %d\n", sizeof(*pn1)); //1
printf("pn1 = %d, n1 = %d\n", pn1, *pn1); //2
pn1 = pn1 + 2; // can do addition
pn1 = pn1 - 1; // can do subtraction
printf("pn1 = %d, n? = %d\n", pn1, *pn1); //3
// pn1 = pn1 * 2; // will cause error if not comment out
// pn1 = pn1 / 2;
printf("pn1 = %d, n? = %d\n", pn1, *pn1);
printf("pn2 = %d, n2 = %d\n", pn2, *pn2);
}
// 1
// 2
// 3
Pointer Types versus Unsigned Int:
Are they equivalent?
Comparing Pointer Types and unsigned int Types, we see:
• Both have the same data range, e.g., from 0 to 232 - 1
• Both support + and – operations. However, the operations
may have different meanings!
• Pointer type does not support multiplication * and division /
• C/C++ allows coercion and casting between the two types as
far as it makes some sense. However, some compiler, e.g.,
Visual Studio C compiler will give you a warning.
Arrays and Strings
LO2: Interpret a program using an array of strings.
LO2.1: Describe the limitations of using string literals.
LO2.2: Interpret a program using an array of strings.
String Literals
/* The purpose of this program is to demonstrate operations on strings defined
as an array of characters and a string associated with a pointer. The former is
a variable string, whereas the latter is a constant that cannot be modified. */
#include
void main() {
int i = 0;
char a[] = "my password is 1a2s3", b[22]; // array
char* p = "send me your password", * q; // ptr (const / imm)
// printf("message before encryption:\n");
printf(" %s\n %s\n", a, p);
while (a[i] != '\0') // encrypt a[ ]
a[i] = *(a + i++) + 1; // a[i] = a[i]+1; i++;
my password is 1a2s3
send me your password
String Literals
//These 3 lines of code demonstrate that the string pointed to
//by p and q is a constant string literal and may not be changed.
//q = p;
//while (*q != '\0')
// *q = *(q++) + 1; //error: *q is a constant / immutable
i = 0;
while (i < 22)
b[i] = *(p + i++); // copy p into b[ ]
q = b; // b is the initial address of array b[]
while (*q != '\0’) // encrypt b[ ]
*q = *(q++) + 1; // now *q can be modified
printf("message after encryption:\n");
printf(" %s\n %s\n", a, b);
message after encryption:
nz!qbttxpse!jt!2b3t4
tfoe!nf!zpvs!qbttxpse
String Literals
//SLIDE 3
p = a;
q = b;
while (*p != '\0') // decrypt a
*p = *(p++) - 1;
while (*q != '\0') // decrypt b
*q = *(q++) - 1;
printf("message after decryption:\n");
printf(" %s\n %s\n", a, b); message before encryption:
my password is 1a2s3
send me your password
message after encryption:
nz!qbttxpse!jt!2b3t4
tfoe!nf!zpvs!qbttxpse
message after decryption:
my password is 1a2s3
send me your password
2D Arrays of Strings: Pointers
char ma[2][4];
char *p = 0;
ma[0][0] = 'C';
ma[0][1] = 'a';
ma[0][2] = 'r';
ma[0][3] = 'B';
ma[1][0] = 'i';
ma[1][1] = 'k';
ma[1][2] = 'e';
ma[1][3] = '\0';
p = &ma[0][0];
while (*p != 0) {
printf("%c", *p);
*p = *p+1; p++; }
printf("\n");
p = &ma[0][0];
while (*p != 0) printf("%c", *p++);
Memory
p 0
ma[0][0] C
ma[0][1] a
ma[0][2] r
ma[0][3] B
ma[1][0] i
ma[1][1] k
ma[1][2] e
ma[1][3] \0
char ma[2][4];
char *p = &ma[0][0];
*p = 'C'; p++;
*p = 'a'; p++;
*p = 'r'; p++;
*p = 'B'; p++;
*p = 'i'; p++;
*p = 'k'; p++;
*p = 'e'; p++;
*p = '\0';
Pointer verson.
2-D Array of String is a 3D Array
Use Array Operations Only
#include
void main() {
char *ma[2][4] = {
{"Car", "Bike", "Boat", "Plane"},
{"Horse", "Cow", "Dog", "Cat"}};
int i=0, j=0, k=0;
for (i=0; i<2; i++) {
for (j=0; j<4; j++) {
for (k=0; ma[i][j][k]!= '\0'; k++)
printf("%c", ma[i][j][k]);
printf("\n");
}
printf("\n");
}
}
Memory
(1)
Alternative:
for (k=0; k < strlen(ma[i][j]); k++)
ma[0][0] C a r \0
ma[0][1] B i k e \0
ma[0][2] B o a t \0
ma[0][3] P l a n e\0
ma[1][0] H o r s e\0
ma[1][1] C o w \0
ma[1][2] D o g \0
ma[1][3] C a t \0
2-D Array of String is a 3D Array
Use String Operations
#include
void main() {
char **p; int i, j;
char *ma[2][4] = {
{ "Car", "Bike", "Boat", "Plane" },
{ "Horse", "Cow", "Dog", "Cat" } };
for (i = 0; i < 2; i++) {
for (j = 0; j < 4; j++) {
p = &ma[i][j]; // p: address of an array of strings
printf("%s", *p);//*p: addr of a string
printf("\n");
}
printf("\n");
}
}
Memory
(2)
ma[0][0] C a r \0
ma[0][1] B i k e \0
ma[0][2] B o a t \0
ma[0][3] P l a n e\0
ma[1][0] H o r s e\0
ma[1][1] C o w \0
ma[1][2] D o g \0
ma[1][3] C a t \0
2-D Array of String is a 3D Array
Use Pointer & String Operations
#include
void main() {
char **p; int i, j;
char *ma[2][4] = {
{ "Car", "Bike", "Boat", "Plane" },
{ "Horse", "Cow", "Dog", "Cat" } };
for (i = 0; i < 2; i++) {
p = ma[i]; // p: address of 1-D array of strings
for (j = 0; j < 4; j++){
printf("%s", *p);
p++;
printf("\n");
}
}
}
Memory
p is the address of 1-D array of
strings
*p is the first string in the array
(3)
ma[0][0] C a r \0
ma[0][1] B i k e \0
ma[0][2] B o a t \0
ma[0][3] P l a n e\0
ma[1][0] H o r s e\0
ma[1][1] C o w \0
ma[1][2] D o g \0
ma[1][3] C a t \0
2-D Array of String and Its Memory Map
* * * *
* * * *
ma
C a r
B i k e
B o a t
P l a n e
H o r s e
C o w
D o g
C a t
‘\0’
‘\0’
‘\0’
‘\0’
‘\0’
‘\0’
‘\0’
‘\0’
char *ma[2][4] = { {"Car", "Bike", "Boat", "Plane"},
{"Horse", "Cow", "Dog", "Cat"} };
char **p = &ma[0][0];
p
*p
printf("%s", *p);
p++;
Defining New Types
LO3: Describe common mechanisms in C and C++ for defining new types.
LO3.1: Interpret a program using macros and keyword const to define constants.
LO3.2: Interpret a program using typedef enumerations.
LO3.3: Interpret a program using structures.
Constants
Most languages allow constants to be declared. There are two mechanisms for
representing constants in C and C++:
• (macros) The compiler may at compilation time substitute values for constant
definitions -- faster execution, may fit in one instruction. The constant is defined
by a macro.
• (const) A constant may be a 'variable' which the program cannot modify -- have
to read memory: slower.
In Ada: I, J: constant Integer := 5;
Java: final double pi = 3.14159265358979;
In C:
const int i= 5, j = 9;
const double pi = 3.14159265358979;
 j = j + 1; This will cause a compilation error!
#include
void main() {
const int i = 5;
int *j;
// i = i + 2; // What would happen? Why?
j = &i;
printf("i = %d\n", i);
*j = *j + 2; // What would happen? Why?
printf("i = %d\n", i); return 0;
}
C allows constants to be declared using the const keyword…
Constants: Misusing Pointers
Constants
A constant defined by const is actually a variable:
• It has memory allocated.
• You can use the & function to find its address.
• It can be modified.
Compiler protection is used for const variable.
• A compilation error will occur if you try to modify.
• If you can get around the compiler, e.g., using an alias, you can modify a constant.
• It is NOT a good programming practice to do so!
A constant defined by a macro (#define max 20) is not modifiable.
Thinking: when you declare an array, which is valid?
const int MAX = 20;
char a[MAX]; // Visual Studio throws a compilation error
#define MAX 20
char b[MAX]; // Works for all environments: VS and GCC
The typedef keyword introduces a new name that becomes a
synonym for the type given by the typename portion of the
declaration. For example:
32
Typedef and Enum
//example 1
typedef int boolean;
void main() {
boolean x = 0;
int counter = 5;
if (x == 0) counter++;
}
Wait, why not
just use char
directly?
//example 2
typedef char FlagType;
int main() {
FlagType x = '\0';
...
}
33
Typedef and Enum: Declarations
Another keyword is enum, which allows us to define a type that is to be
populated by specific elements (symbols). In C, each enum value is an actual int,
and can be directly manipulated. Note that an enum value is not type safe.
//Example 1:
enum { false, true } boolean;
void main() {
enum boolean x = false;
int counter = 5;
if (x == true) counter++;
}
//Example 2:
enum {
Sun=0, Mon, Tue, Wed, Thu, Fri, Sat
} days;
enum days day = Mon;
Forces enum elements to be
numbered from zero – otherwise
their values are not well defined.
Typedef and Enum: Usage
Recall that in the previous example we created a variable with “enum
days day;”. This is a little awkward because we have to write “enum
days” for the type name. We can fix this with typedef though:
enum { Sun=0, Mon, Tue, Wed, Thu, Fri, Sat } days;
typedef enum days Days;
Days now = Mon;
As a final thought about type safety, consider the following code.
• What is the final value of x?
• What is the value of x, after x++ is executed and if x was Sat before?
Days x = Mon, y = Fri;
while (x != y)
x++; 34
A structure is created by the keyword struct. A structure is composite data type,
similar to a class in Java but only containing state.
struct type_name {
type1 element1;
type2 element2;
…
typen element;
};
struct type_name a, b;
a.element1 = 10;
• Why is structure useful?
35
Structures (Composite Data)
Don’t like having to put
struct in front of the
typename? Use typedef.
36
Structures (Composite Data)
How much memory is allocated for this structure?
#include
#include
struct Course {
int sln;
char title[256];
char instructor[250];
int time;
};
struct Course ser222;
void main() {
ser222.sln = 1774;
strcpy(ser222.title, “Data Structures & Algorithms");
strcat(ser222.instructor, “Acuna, Ruben");
printf("Memory allocated for this structure is %d", sizeof(ser222));
}
Demonstration
LO4: Develop a C program with flow control, arrays, pointers, structs, and console I/O.
Contact Manager
• Goal: create a program to manage a contact database. Each entry will
have a name, phone number, and email. It should be possible to add
new contacts, look up existing contacts, and remove unneeded
contacts.
• Basic Design:
• Create a new structure to store the data for each entry.
• Create an array of the new structure to store all contacts.
• Will need to keep track of how many contacts have been entered.
• Create a menu to offer the user different ways to interact with the program.
• Next Step: get a shell program compiling that has a contact struct and
a basic menu.
Contact Manager
Contact Manager: Inserting an Entry
Contact Manager: Searching for an Entry
Contact Manager: Deleting an Entry
• Goal: add support to search for an entry by name and delete it.