C++ Notes: Struct Example

Problem - Points

Suppose we have the following problem. We want to read a set of (x, y) coordinates and a name, then sort them in order increasing distance from the origin (0, 0). This is the kind of data you might have if we digitized a map with the origin at some central point (eg, London) and the coordinates of other cities.

Global Declaration

Types are usually used in more than one function, and are therefore global or defined in an include file.

// Define a struct to hold each point.
struct Point {
    float x;   // x coordinate
    float y;   // y coordinate
    char  name[20]; // name of the point
};

Local Declarations

Point pts[1000];  // array to hold up to 1000 points.
int   n = 0;      // number of points in the array.

Reading the input

To read structs, you need to read each of the fields.

while (cin >> pts[n].name >> pts[n].x >> pts[n].y) {
    n++;
}

Utility function to compute distance to origin

float dist(Point p) {
    // Compute the distance from the origin
    return sqrt(p.x*p.x + p.y*p.y);
}

Sorting an array of Points

Here's a simple bubble sort function that stops when there are no more exchanges. It sorts Points by their distance from the origin by calling on the function defined above.

void bubbleSort(Point pt[], int size) {
    bool doMore = true;
    while (doMore) {
        doMore = false;  // Assume no more passes unless exchange made.
        for (int i=0; i<size-1; i++) {
            if (dist(pt[i]) > dist(pt[i+1])) {
                // Exchange elements
                Point temp = pt[i]; pt[i] = pt[i+1]; pt[i+1] = temp;
                doMore = true;  // Exchange requires another pass.
            }
        }
    }
}