Chapter 4

Structs

Struct Syntax

C is a procedural programming language, which means that a program is just a collection of functions – no classes. However, C does have a construct called a struct that is similar to a data class in Java. A struct is simply a new variable type that is a collection of related data.

Syntax

Here is the format of a struct declaration:

struct name {
    type1 name1;
    type2 name2;
    ...
} objList;

Here, name is the optional name for this structure type. This name is needed if you plan to created any variables of this struct type. The type name elements are fields that you want in your struct. For example, if the struct represented a person, you might want these fields:

char name[20];
int age;

Fields in structs are the same idea as fields in a Java or C# class.

Finally, objList is an optional list of variable names you want constructed with this struct type.

First Example

Here is a simple struct:

struct person {
    char name[20];
    int age;
} p1, p2;

Now, struct person is a new datatype. p1 and p2 are variables of type struct person.

Declaring Struct Variables

You can automatically declare struct variables by listing variable names at the end of the struct definition. You can also declare them outside the definition just like you do ordinary variables. The format for declaring variables in C is:

type name;

The type of the above struct, for example, is struct person. So we can declare another struct variable as follows:

struct person p3;

This declaration automatically allocates space for the struct, including space for every field in the struct.

Accessing Struct Fields

Accessing a field in a struct variable is exactly like accessing a field in a Java or C# object:

structVar.fieldName

Here, structVar is the name of the struct variable and fieldName is one of the fields in the struct. This allows us to access or change that field. Let’s declare another struct person variable, and set the person’s name to “Bob” and age to 20.

Here’s how:

struct person bobPerson;        //declare struct variable
bobPerson.age = 20;             //set person's age to 20
strcpy(bobPerson.name, "Bob");  //set person's name to "Bob"

Notice that if we are initializing a string field, we must use strcpy. The following will NOT compile since name is an array (a constant pointer):

bobPerson.name = "Bob";         //Will not compile!

Struct Example

Structs can be declared at any point in a C program, but they are usually declared with the global variables (right after the include statements). This way, the struct type can be used throughout the file.

Here is an example that uses a struct to store a two-dimensional point (x, y location). It gets two points as input, and then prints the equation that passes through the points.

#include <stdio.h>
struct point {
    int x;
    int y;
}; //No variables declared here

double getSlope(int, int, int, int);
double getIntercept(int, int, double);

int main() {
    struct point p1;
    struct point p2;
    double slope;
    double intercept;

    printf("Enter point1, e.g. (1, 2): ");
    scanf("(%d, %d)", &(p1.x), &(p1.y));
    printf("Enter point2, e.g. (1, 2): ");
    scanf("(%d, %d)", &(p2.x), &(p2.y));

    slope = getSlope(p1.x, p1.y, p2.x, p2.y);
    intercept = getIntercept(p1.x, p1.y, slope);

    //prints equation in form y = mx + b
    //m: slope, b: y-intercept
    printf("y = %.2lfx + %.2lf\n", slope, intercept);

    return 0;
}

double getSlope(int x1, int x2, int y1, int y2) {
    //slope = change in y / change in x
    return (y2-y1)/(x2-x1);
}

double getIntercept(int x, int y, double slope) {
    //if y = mx + b, b = y - mx
    return y - slope*x;
}

Structs and Functions

We could have also written the point example by passing the point structs to the getSlope and getIntercept functions (instead of passing their fields). This works just like passing other variable types, except struct point will be an argument type. Here’s the example when we pass the points to the functions:

#include <stdio.h>

struct point {
    int x;
    int y;
}; //No variables declared here

double getSlope(struct point, struct point);
double getIntercept(struct point, double);

int main() {
    struct point p1;
    struct point p2;
    double slope;
    double intercept;

    printf("Enter point1, e.g. (1, 2): ");
    scanf("(%d, %d)", &(p1.x), &(p1.y));
    printf("Enter point2, e.g. (1, 2): ");
    scanf("(%d, %d)", &(p2.x), &(p2.y));

    slope = getSlope(p1, p2);
    intercept = getIntercept(p1, slope);

    //prints equation in form y = mx + b
    //m: slope, b: y-intercept
    printf("y = %.2lfx + %.2lf\n", slope, intercept);

    return 0;
}

double getSlope(struct point p1, struct point p2) {
    //slope = change in y / change in x
    return (p2.y-p1.y)/(p2.x-p1.x);
}

double getIntercept(struct point p, double slope) {
    //if y = mx + b, b = y - mx
    return p.y - slope*p.x;
}

Arrays of Structs

You can create arrays of structs in C just like you can create arrays of any other type. The format for creating constant-sized arrays is:

type name[size];

Consider the person struct again:

struct person {
    char name[20];
    int age;
};

Here’s how to create a 3-slot array of type struct person called group:

//"struct person" is the type; "group" is the array name
struct person group[3];

When you create an array of type struct, C allocates space for each struct element (and its fields) in the array.

We can get out a particular struct element using an array index:

group[0]        //the first struct person in the array

For example, here’s how we could set the first person’s name to “Bob” and age to 20:

strcpy(group[0].name, "Bob");
group[0].age = 20;

Pointers to Structs

You can declare a pointer to a struct just like you declare a pointer to another element type. The format for declaring a pointer is:

type* name;

So, to declare a pointer to a struct person element, we could say:

struct person* personPtr;

Suppose we have another struct person variable:

struct person p1;
strcpy(p1.name, "Jill");
p1.age = 18;

Then we can make personPtr point to p1:

personPtr = &p1;

Allocating Memory

We can also create struct variables by:

Declaring a pointer to a struct
Allocating memory for the struct

This approach (using pointers instead of standard variables) is handy when building data structures like linked lists.

To create a struct person in this way, we first declare a pointer:

struct person* personPtr;

Then we allocate memory for the struct, and give personPtr the address of that memory. We can use sizeof(struct person) to get the number of bytes needed to store a variable of type struct person:

personPtr = malloc(sizeof(struct person));

Now, personPtr points to a struct person, which has space for the name and age fields.

Accessing Fields

We can get at the struct person object itself by dereferencing personPtr:

*personPtr

We can then initialize the fields:

(*personPtr).age = 18;

This line does two things:

Dereferences the pointer to get at the struct person object
Changes the person’s age to 18

Do NOT write something like this:

*personPtr.age = 18;    //BAD!

The compiler will try to resolve the “.” operator first. Because personPtr is a pointer and not a struct, using a . doesn’t make sense. This line will result in a compiler error. We need to dereference the pointer before we can access any fields.

Pointers to structs are very common in C, and you’ll often find yourself dereferencing a struct pointer and then accessing one of the fields. Because of this, there is a shortcut notation:

personPtr->age = 18;

//Is equivalent to:
(*personPtr).age = 18;

Linked Lists

We can use structs to help implement all the common data structures in C. For example, whereas before we would have created a Node class to help us write a linked list, we will now create a node struct:

struct node {
    int data;
    struct node *next; //pointer to next node in list
};

Suppose we want to create a linked list with a single node. First, we declare a head variable:

struct node *head;

Then, we allocate memory for the node:

head = malloc(sizeof(struct node));

Finally, we initialize the fields in head:

head->data = 4;
head->next = NULL;

Here’s a full C program that inserts values into a linked list and then prints them out:

#include <stdio.h>

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

struct node *head;

void add(int);
void print(void);

int main() {
    head = NULL;
    add(1);
    add(2);
    add(3);
    add(4);

    //prints 1, 2, 3, 4 on separate lines
    print();
    
    return 0;
}

void add(int num) {
    //create new node
    struct node *newnode = malloc(sizeof(struct node));
    newnode->data = num;
    newnode->next = NULL;

    if (head == NULL) {
        head = newnode;
    }
    else {
        //find end of list
        struct node *cur = head;
        while (cur->next != NULL) {
            cur = cur->next;
        }

        //add newnode after cur
        cur->next = newnode;
    }
}

void print(void) {
    struct node *cur = head;
    while (cur != NULL) {
        printf("%d\n", cur->data);
        cur = cur->next;
    }
}

Linked lists in C work almost exactly the same as linked lists in Java or C#. The only differences are:

We use a struct instead of a class to represent a node
We use -> instead of . to access values in the node

Pointers to Pointers in Linked Lists

Let’s look at how pointers to pointers can be used to eliminate a nuisance we’ve had when trying to insert and delete items in linked lists. For simplicity, we’ll consider lists of integers, built using this structure:

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

Suppose we’re trying to write some code to delete a given integer from a list. The straightforward solution looks like this:

//delete node containing i from list pointed to by lp
struct node *lp, *prevlp;
for(lp = list; lp != NULL; lp = lp->next) {
    if(lp->item == i) {
        if(lp == list)
            list = lp->next;
        else {
            prevlp->next = lp->next;
        }
        break;
    }
    prevlp = lp;
}

This code works, but it has two flaws. One is that it must use an extra variable to keep track of the node behind the one it’s looking at, and the other is that it must use an extra test to special-case the situation in which the node being deleted is at the head of the list. Both problems arise because the deletion of a node from the list involves modifying the previous pointer to point to the next node (that is, the node before the deleted node to point to the one following). But, depending on whether the node being deleted is the first node in the list or not, the pointer that needs modifying is either the pointer that points to the head of the list, or the next pointer in the previous node.

To illustrate this, suppose that we have the list (1, 2, 3) and we’re trying to delete the element 1. After we’ve found the element 1, lp points to its node, which just happens to be the same node that the main list pointer points to, as illustrated in (a) below:

To remove element 1 from the list, then, we must adjust the main list pointer so that it points to 2’s node, the new head of the list (as shown in (b) below):

If we were trying to delete node 2, on the other hand (as illustrated in (c) below):

we’d have to adjust node 1’s next pointer to point to 3.

The prevlp pointer keeps track of the previous node we were looking at, since (at other than the first node in the list) that’s the node whose next pointer will need adjusting. (Notice that if we were to delete node 3, we would copy its next pointer over to 2, but since 3’s next pointer is the null pointer, copying it to node 2 would make node 2 the end of the list, as desired.)

There is another way to write the list-deletion code, which is (in some ways, at least) much cleaner, by using a pointer to a pointer to a struct node.

Hint: This pointer will point at the pointer which points at the node we’re looking at; it will either point at the head pointer or at the next pointer of the node we looked at last time. Since this pointer points at the pointer that points at the node we’re looking at, it points at the pointer which we need to modify if the node we’re looking at is the node we’re deleting.