struct, dynamic memory and I/O in C (printf, scanf)

The last topic of the semester is the way to keep several pieces of information together in C: struct. A student’s name and grade, the x and y of a point, a node of a list. Besides that, you will also see how a program asks for memory while it runs (malloc) and how it talks to the user (printf, scanf). The question types do not change: “What is printed?” with structs and pointers, printf format questions, memory region questions.

struct

struct point {
    int x;
    int y;
};

struct point p;
p.x = 7;
p.y = -1;

A struct defines a new type; the variables inside it are called members. Members are accessed with .. In memory the members sit one after another: on the LC-3 a struct point takes two words, p.x in the first word, p.y in the second.

Initialization: struct point p = {3, 4}; (in order x = 3, y = 4).

typedef

To avoid writing struct point every time, a nickname is given:

typedef struct {
    char name[12];
    int score;
} Student;

Student s = {"Ada", 70};

Structs are copied by value

b = a; copies all the members. Passing a struct to a function is also copying. The function changes the copy, the original does not change. (The exact opposite of arrays: when you pass an array, the address is passed.)

void moveBad(struct point p)   { p.x += 10; }   /* copy */
void moveGood(struct point *p) { p->x += 10; }  /* original */

The -> operator

To access a member through a struct pointer you write (*p).x. Because this is used so often, it has a shorthand: p->x.

struct point p;
p.x = 7;
p.y = -1;
struct point *pp = &p;
pp->y = pp->x * 2;
printf("(%d, %d)\n", p.x, p.y);

(7, 14)

PITFALL · *p.x. The precedence of the . operator is higher than *: *p.x = *(p.x), that is “treat the x member as a pointer”. The correct version is (*p).x or p->x.

Arrays of structs

Student s[3] = {{"Ada", 70}, {"Can", 85}, {"Ece", 60}};
s[1].score      /* 85 */
s[2].name[0]    /* 'E' */

When you increment a struct pointer by one, it advances one struct (pointer arithmetic knows the size of the type).

Linked list

A struct can contain a pointer of its own type. This way the nodes are linked to each other:

struct node {
    int val;
    struct node *next;
};

head ──► [10 | •]──► [20 | •]──► [30 | NULL]

The traversal pattern:

for (p = head; p != NULL; p = p->next)
    ... p->val ...

The difference from an array: adding an element requires no shifting, only the pointers change. But you cannot jump directly to the i-th element, you have to walk from the start.

Dynamic memory: malloc and free

If you do not know in advance how much memory the program will ask for while running, you ask for space from the heap.

#include <stdlib.h>

int *v = malloc(4 * sizeof(int));   /* space for 4 ints */
v[0] = 5;                           /* use it like an array */
free(v);                            /* give it back when done */

• malloc(n) reserves n bytes and returns the starting address (NULL if there is no space).
• sizeof(T) gives how many bytes a type has; do not write the number by hand.
• Memory that is not freed is lost until the program ends (memory leak).

Building a list:

struct node *head = NULL;
int i;
for (i = 1; i <= 3; i++) {
    struct node *n = malloc(sizeof(struct node));
    n->val = i * 10;
    n->next = head;     /* add at the front */
    head = n;
}

The list: 30 → 20 → 10. Because each new node is added at the front, the order is reversed.

When you traverse and print:

struct node *p;
for (p = head; p != NULL; p = p->next)
    printf("%d ", p->val);

30 20 10

Step by step what happened:

i=1: n1 = {10, NULL}   head → n1
i=2: n2 = {20, n1}     head → n2 → n1
i=3: n3 = {30, n2}     head → n3 → n2 → n1

To delete the whole list there is a pattern as well: while (head) { t = head; head = head->next; free(t); }. If you do free(head) without saving next first, you cannot reach the rest of the list.

The LC-3 memory layout of a struct

Since an int is one word on the LC-3, struct point is two words. If struct point pts[3]; starts at x4000:

x4000  pts[0].x      x4001  pts[0].y
x4002  pts[1].x      x4003  pts[1].y
x4004  pts[2].x      x4005  pts[2].y

The general formula: &pts[i].y = base + 2i + 1. For q->y the compiler adds 1 to the address in q and does an LDR: LDR R1, R0, #1. Because the distance (offset) of the members from the start of the struct is constant, the base+offset mode of LDR/STR is just right for this job.

Memory regions

On the LC-3 the stack grows down from high addresses, and the heap grows up from above the global region.

PITFALL · returning the address of a local variable. int *f(void) { int x = 5; return &x; } is wrong: when f returns, x’s record is removed from the stack and the pointer now points to an invalid place. For data that will outlive the function, use malloc.

printf

int age = 20;
double gpa = 3.456;
char grade = 'B';
printf("Age: %d, GPA: %.2f, Grade: %c\n", age, gpa, grade);

Age: 20, GPA: 3.46, Grade: B

Escape sequences: \n newline, \t tab, \\ backslash, \" quote.

printf returns the number of characters it wrote: printf("abc\n") returns 4.

scanf

int a, b;
int n = scanf("%d %d", &a, &b);

• The address of the variable is given (&a). scanf writes what it reads to that address.
• When reading a string, no & is used, because the array name is already an address: scanf("%9s", word);. The width (9) prevents overflow.
• The return value is the number of items read successfully. If the user types 12 30, n = 2.
• %d skips spaces and newlines.

At the LC-3 level, printf and scanf eventually call operating system routines such as TRAP x21 (OUT) and TRAP x20 (GETC). Formatting (turning a number into ASCII digits) is the library’s job; the general form of what you did in week 10 by adding x30.

Common mistakes

struct point { int x; int y; };
/* in main: */
struct point p = {3, 4};
p.x += 2;
printf("%d %d\n", p.x, p.y);

void moveBad(struct point p)   { p.x += 10; }
void moveGood(struct point *p) { p->x += 10; }
/* in main: */
struct point p = {1, 2};
moveBad(p);   printf("%d ", p.x);
moveGood(&p); printf("%d\n", p.x);

struct point a = {5, 6};
struct point b = a;
b.y = 0;
printf("%d %d\n", a.y, b.y);

typedef struct { char name[12]; int score; } Student;
/* in main: */
Student s[3] = {{"Ada", 70}, {"Can", 85}, {"Ece", 60}};
int i, best = 0, sum = 0;
for (i = 0; i < 3; i++) {
    sum += s[i].score;
    if (s[i].score > s[best].score) best = i;
}
printf("%s %d\n", s[best].name, sum / 3);

struct node { int val; struct node *next; };
/* in main: */
struct node c = {30, NULL}, b = {20, &c}, a = {10, &b};
struct node *p;
int s = 0;
for (p = &a; p != NULL; p = p->next)
    s += p->val;
printf("%d %d\n", s, a.next->next->val);

printf("[%5d][%-5d][%05d]\n", 42, 42, 42);

printf("%.2f %8.3f|\n", 3.14159, 3.14159);

printf("%x %X %o %c\n", 255, 255, 8, 65);

int a, b;
int n = scanf("%d %d", &a, &b);
printf("%d %d %d\n", n, a, b);

int *v = malloc(4 * sizeof(int));
int i;
for (i = 0; i < 4; i++) v[i] = i * i;
printf("%d %d\n", v[3], v[1] + v[2]);
free(v);

struct point pts[2] = {{1, 2}, {3, 4}};
struct point *q = pts;
q++;
printf("%d %d\n", q->x, (*q).y + pts[0].x);