Arrays and Structs

Data Structures

  • Data structures are organized collections of values used for data management, along with operations that can be performed on the data.

  • Data structures can be classified into three types:

    • Scalar or Elementary

    • Structure

    • Abstract

Elementary or Scalar Data Structures

  • Data whose values are directly supported by the computer's hardware.

  • Examples:

    • Integer

    • Float

    • Double

    • Character

Structure Data Structures

  • Contain groups of scalars, each accessed by a referencing mechanism.

  • Examples:

    • Array

    • Records

    • Structures

Abstract Data Structures

  • Data types defined by developers.

  • Examples:

    • Enumeration

    • Type declaration

Arrays

  • Arrays are finite, ordered collections of homogeneous elements, each accessed through a subscript value.

    • Finite: Arrays have a specific number of elements.

    • Ordered: Elements are arranged in a specific sequence (first, second, third, etc.).

    • Homogeneous: All elements in an array must be of the same data type (e.g., all integers, all characters, or all floating-point numbers).

Array Data Types

  • Two data types are associated with an array:

    • Base Type (Common Type): The data type of the elements or components of the array.

    • Index (Subscript Type): The data type of the values used to access the individual elements of the array.

Declaring Arrays

  • The general syntax for declaring an array is:

    dataType array_name[arraySize]

    • dataType: Specifies the data type of the array (e.g., int, float, double, char).

    • array_name: The name of the array.

    • array_size: The size of the array, usually enclosed in brackets, determines the number of elements the array can contain.

Single Dimension Array:

  • Example:

    int N[10];
Multidimensional Array:

  • Example:

    int sample[3][5]; // 3 x 5 matrix

Accessing Arrays

  • The general syntax for accessing array elements is:

    array_name[indexExp]

    • array_name: The name of the array.

    • indexExp: Specifies the position (index) of the component of the array that you want to access.

Example of accessing arrays:

  • Assign the value of 34 to the 6th array element (index 5) in a single-dimensional array that contains 10 array elements:

    array_name[5] = 34;

  • For a 2D array int board[4][3], the statement board[0][2] = 9; assigns the value 9 to the element at the first row and third column.

Initializing Arrays

  • The general syntax for initializing arrays is:

    dataType array_name[arraySize] = {values};

    • dataType: The data type of the array (e.g., int, float, double, char).

    • array_name: The name of the array.

    • array_size: The size of the array, enclosed in brackets, determines the number of elements that the array has to contain.

    • values: Comma-separated list of values to initialize the array elements.

Examples of initializing arrays:
int example[5] = {16, 2, 77, 40, 12071};
int example[] = {16, 2, 77, 40, 12071}; // Valid, size is inferred from the number of initializers

Restrictions in Array Processing

  • To copy one array into another, you must copy it component-wise (element by element).

  • To read data into an array, you must read one component at a time.

Initializing Arrays Using Loops

  • Arrays can be initialized using loops to assign values to each element.

Basic Operations in Arrays

  • Extraction: A function that accepts an array variable (indicated by its array name) and an element of its index type, returning the array's content.

    • Example:

      X = b[3];
H = x[ctr1][ctr2];

  • Storing: An operation that accepts a value and stores it in an array variable.

    • Example:

      A[4] = 4;
F[ctr] = ctr + 1;

Sorting

  • Sorting is the process of arranging items of information into a desired order.

  • Applications of sorting:

    • Alphabetizing names in a telephone directory.

    • Chronological ordering of customer orders.

    • Arranging books in a library.

Selection Sort

  • Performs sorting by repeatedly placing the largest element in the unsorted portion of the array to the end of this unsorted portion until the entire array is sorted.

Bubble Sort

  • Performs sorting by repeatedly comparing neighboring elements. If a larger element is found before a smaller element, it swaps them until the entire array is sorted.

Searching

  • Searching is the process of finding a particular element (key) in an array.

  • Methods in searching algorithms:

    • Sequential Search

    • Binary Search

Sequential Search

  • The list or array is traversed sequentially, and every element is checked.

Binary Search

  • Repeatedly targets the center of the search structure and divides the search space in half. This method requires that the data be sorted.

Comparison between Sequential and Binary Search

  • Binary search is more efficient than sequential search, especially for large datasets, but requires the data to be sorted.

Structures

  • Structures are collections of variables that are referenced under one name, providing a convenient means of keeping related information together.

  • Data type: struct.

Declaring Structure Variables:

  • Structure varibles can be constructed in three different ways.

struct Date {
 char Month[16];
 int Day;
 int Year;
 char weekday[11];
} Christmas, Birthday, Valentines;

struct Date {
 char Month[16];
 int Day;
 int Year;
 char weekday[11];
};
struct Date Christmas, Birthday, Valentines;

struct {
 char Month[16];
 int Day;
 int Year;
 char weekday[11];
} Christmas, Birthday, Valentines;

Accessing elements of Structure Variables

  • Individual structure elements are referenced by using the dot operator (.).

Structures with Array Components

struct Student_Grade {
 char Name[21];
 int Grade[5];
} Male, Female;

Male.Name // Accessing Name of Male
Female.Name // Accessing Name of Female

Male.Grade[0] // Accessing the first grade of Male
Female.Grade[0] // Accessing the first grade of Female

// Similarly for other grades:
Male.Grade[1], Female.Grade[1]
Male.Grade[2], Female.Grade[2]
Male.Grade[3], Female.Grade[3]
Male.Grade[4], Female.Grade[4]

Array of Structures

struct Student_Grade {
 char Name[21];
 int Grade[2];
} Student[5];

//Accessing Elements or components:
Student[0].Name // Accessing Name of the first student
Student[4].Name // Accessing Name of the fifth student
Student[0].Grade[0] // Accessing the first grade of the first student
Student[4].Grade[0] // Accessing the first grade of the fifth student
Student[0].Grade[1] // Accessing the second grade of the first student
Student[4].Grade[1] // Accessing the second grade of the fifth student

DEMONSTRATION

C++ Demonstration #1:

  • Show the screen output of a given program segment.

C++ Demonstration #2:

  • Write a program that loads 25 integers into a square array S and displays the sum of the elements in the left diagonal.