A structure (struct) joins several pieces of data of different types into one unit – e.g. a student's name, grade and average. Instead of three separate arrays we have one array of students. This lesson covers defining structures, accessing fields, arrays of structures, passing them to functions and sorting.
Before you start: prior knowledge you need – pointers, strings, functions. How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C (C11); they have been checked to compile (gcc -Wall) and give the output shown.
Defining a structure and accessing fields
A structure is defined outside the function main. Each part of a structure is called a field (member). A field is accessed with a dot: p.x.
#include <stdio.h>
/* a new type: a point in the plane */
struct Point {
int x;
int y;
};
int main(void) {
struct Point a; /* a variable of type struct Point */
a.x = 3;
a.y = 4;
struct Point b = {1, 2}; /* initializing the fields in order */
struct Point c = {.y = 7, .x = 5}; /* or by field names */
printf("a = (%d, %d)\n", a.x, a.y);
printf("b = (%d, %d)\n", b.x, b.y);
printf("c = (%d, %d)\n", c.x, c.y);
b = a; /* assignment copies all fields */
printf("after b = a: (%d, %d)\n", b.x, b.y);
return 0;
}
The program prints:
a = (3, 4)
b = (1, 2)
c = (5, 7)
after b = a: (3, 4)
Structures can be assigned (b = a), but they cannot be compared with == – they are compared field by field.
A shorter type name: typedef
So that we do not have to write struct Point all the time, a shorter name is introduced with typedef:
#include <stdio.h>
typedef struct {
char name[30];
int grade;
double average;
} Student; /* now Student is the name of a type */
int main(void) {
Student s;
scanf("%29s %d %lf", s.name, &s.grade, &s.average);
printf("%s, grade %d, average %.2f\n", s.name, s.grade, s.average);
return 0;
}
For the input Ana 7 4.85 the program prints Ana, grade 7, average 4.85.
For a text field (char name[30]) you do not write & in scanf – the name of an array is already an address. The number 29 keeps room for the terminating character '\0' (see Strings in C).
An array of structures
The most common use: an array of structures instead of several parallel arrays. An element of the array is a whole structure, and a field is accessed with array[i].field.
#include <stdio.h>
typedef struct {
char name[30];
int points;
int time; /* in minutes */
} Contestant;
int main(void) {
int n;
Contestant c[100];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%29s %d %d", c[i].name, &c[i].points, &c[i].time);
/* the best: more points; with equal points – shorter time */
int best = 0;
for (int i = 1; i < n; i++)
if (c[i].points > c[best].points ||
(c[i].points == c[best].points && c[i].time < c[best].time))
best = i;
printf("Winner: %s (%d points, %d min)\n", c[best].name, c[best].points, c[best].time);
return 0;
}
For the input below the program prints:
3
Marko 80 95
Ana 90 110
Iva 90 100
Winner: Iva (90 points, 100 min)
Compare this with a solution without structures: three arrays name[], points[], time[] whose elements with the same index "belong" to the same contestant. When sorting, you would have to swap all three arrays – with a structure we swap one element.
Structures and functions, the -> operator
A structure is passed to a function by value – the function gets a copy and cannot change the original. For a function to change a structure, it is given a pointer, and a field is accessed with the operator -> (p->x is the same as (*p).x).
#include <stdio.h>
typedef struct {
int x, y;
} Point;
/* by value: gets a copy, returns a result */
int squaredDistance(Point a, Point b) {
int dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
/* through a pointer: changes the original */
void move(Point *p, int dx, int dy) {
p->x += dx; /* the same as (*p).x += dx */
p->y += dy;
}
int main(void) {
Point a = {0, 0}, b = {3, 4};
printf("d^2 = %d\n", squaredDistance(a, b));
move(&a, 1, 1);
printf("a = (%d, %d)\n", a.x, a.y);
printf("d^2 = %d\n", squaredDistance(a, b));
return 0;
}
The program prints:
d^2 = 25
a = (1, 1)
d^2 = 13
For large structures that are not changed, a pointer is also passed for speed – the whole content is not copied. Then you write const Point *p. More about pointers: Pointers in C.
A structure inside a structure
A field of a structure can be another structure:
#include <stdio.h>
typedef struct {
int day, month, year;
} Date;
typedef struct {
char name[30];
Date born; /* a field that is itself a structure */
} Person;
/* returns a negative number if d1 is before d2, 0 if they are equal, a positive number otherwise */
int compareDates(Date d1, Date d2) {
if (d1.year != d2.year) return d1.year - d2.year;
if (d1.month != d2.month) return d1.month - d2.month;
return d1.day - d2.day;
}
int main(void) {
Person a = {"Mila", {12, 5, 2013}};
Person b = {"Teodor", {3, 11, 2012}};
Person *older = compareDates(a.born, b.born) < 0 ? &a : &b;
printf("The older one is %s, born %d.%d.%d.\n", older->name,
older->born.day, older->born.month, older->born.year);
return 0;
}
The program prints The older one is Teodor, born 3.11.2012.
Sorting an array of structures: qsort
The function qsort from stdlib.h sorts any array. It gets the array, the number of elements, the size of one element and a comparison function that returns a negative number if the first element goes before the second, zero if they are equal and a positive number otherwise.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char name[30];
int points;
} Contestant;
/* more points go first; with equal points – alphabetically */
int compare(const void *a, const void *b) {
const Contestant *x = a, *y = b;
if (x->points != y->points)
return y->points - x->points;
return strcmp(x->name, y->name);
}
int main(void) {
int n;
Contestant c[100];
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%29s %d", c[i].name, &c[i].points);
qsort(c, n, sizeof(Contestant), compare);
for (int i = 0; i < n; i++)
printf("%d. %s %d\n", i + 1, c[i].name, c[i].points);
return 0;
}
For the input 4 / Marko 80 / Ana 95 / Luka 95 / Iva 80 the program prints:
1. Ana 95
2. Luka 95
3. Iva 80
4. Marko 80
In C++ the same job is done by sort with a lambda function – see STL in C++. Unions (union) and the layout of structures in memory are explained in the lesson Introduction to structures and unions.
Practice tasks
Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.
TASK 01Difficulty: easy
Fractions
Define a structure Fraction with the fields num and den. Read two fractions (numerator and denominator, the denominators are positive) and print their sum in reduced form num/den.
Example 1
Input
1 2 1 3
Output
5/6
Example 2
Input
3 4 1 4
Output
1/1
Hint
The sum: a/b + c/d = (a·d + c·b) / (b·d). It is reduced by dividing by the GCD (Euclid's algorithm) – write a function Fraction add(Fraction, Fraction).
Solution (C)
#include <stdio.h>
typedef struct {
int num, den;
} Fraction;
int gcd(int a, int b) {
if (a < 0) a = -a;
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
Fraction add(Fraction x, Fraction y) {
Fraction z = {x.num * y.den + y.num * x.den, x.den * y.den};
int d = gcd(z.num, z.den);
z.num /= d;
z.den /= d;
return z;
}
int main(void) {
Fraction a, b;
scanf("%d %d %d %d", &a.num, &a.den, &b.num, &b.den);
Fraction s = add(a, b);
printf("%d/%d\n", s.num, s.den);
return 0;
}
TASK 02Difficulty: medium
Excellent results
The input is n, then for every student a name and the grades in 5 subjects. Print the names of the students with an average of at least 4.50, sorted by average in descending order (with an equal average, alphabetically), together with the average to two decimal places. If there are no such students, print NONE.
Example
Input
4
Marko 5 5 4 5 4
Ana 5 5 5 5 4
Iva 4 4 5 3 5
Luka 5 5 5 4 4
Output
Ana 4.80
Luka 4.60
Marko 4.60
Hint
A structure with the fields name and sum (the sum of the grades). Copy into an array only the students with an average of at least 4.5, then sort it with qsort. Do not compute the average as a real number for comparing: an average ≥ 4.5 is the same as 2 · sum ≥ 45, and a larger average means a larger sum.
Solution (C)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char name[30];
int sum; /* the sum of 5 grades – an integer, no rounding errors */
} Student;
int compare(const void *a, const void *b) {
const Student *x = a, *y = b;
if (x->sum != y->sum)
return x->sum > y->sum ? -1 : 1; /* the larger sum (average) first */
return strcmp(x->name, y->name);
}
int main(void) {
int n, k = 0;
Student s[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
Student t;
t.sum = 0;
scanf("%29s", t.name);
for (int j = 0; j < 5; j++) {
int g;
scanf("%d", &g);
t.sum += g;
}
if (2 * t.sum >= 45) /* average >= 4.5 */
s[k++] = t;
}
if (k == 0) {
printf("NONE\n");
return 0;
}
qsort(s, k, sizeof(Student), compare);
for (int i = 0; i < k; i++)
printf("%s %.2f\n", s[i].name, s[i].sum / 5.0);
return 0;
}
Common mistakes and tips
After the closing brace of a structure definition comes a semicolon: struct Point { int x, y; };.
Without typedef the type is called struct Point, not just Point.
The dot (p.x) is used for a structure variable, the arrow (p->x) for a pointer to a structure.
Structures cannot be compared with ==; write a function that compares the fields.
In a comparison function for qsort do not return the difference of real numbers (x->average - y->average) – the result is truncated to int and 0.3 becomes 0.
Check your knowledge
Open the quiz
Structures
1. How do you access the field name of a variable s of type struct Student?
2. If p is a pointer to a structure, what is p->x?
3. What does a function get when a structure is passed to it by value?
4. What should a comparison function for qsort return when the first element goes before the second?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.