Arrays
Arrays are the most basic data structure in C++. Read this page to learn about arrays.
An array is a data type that represents a collection of elements (values or variables), each selected by one or more indices (identifying keys) that can be computed at run time during program execution. Such a collection is usually called an array variable, array value, or simply array. Some programming languages may refer to arrays as lists. This lesson introduces defined-value arrays, fixed-length arrays, and dynamic arrays.
Objectives and Skills
Objectives and skills for this lesson include:
- Understand single and multi-dimensional arrays
- Understand dynamic arrays
- Understand associative arrays
- Use arrays to implement program functionality
Readings
- Rebus: Programming Fundamentals
- Wikipedia: Array data type
- Wikipedia: Dynamic array
- Wikipedia: Associative array
Practice
Examples
- Flowchart
- Pseudocode
- BASIC
- C
- C++
- C#
- Clojure
- COBOL
- Java
- JavaScript
- Lua
- Perl
- PHP
- PowerShell
- Python3
- Ruby
- Swift
- VB.NET
Activities
Complete the following activities using pseudocode, a flowcharting tool, or your selected programming language. Use separate functions for input, each type of processing, and output. Avoid global variables by passing parameters and returning results. Create test data to validate the accuracy of each program. Add comments at the top of the program and include references to any resources used.
Defined-Value Arrays
- Review MathsIsFun: Leap Years. Create a program that asks the user for a year, and then calculate whether or not the given year is a leap year. Build an array where each entry is the number of days in the corresponding month (January = 31, February = 28 or 29 depending on year, March = 31, etc.). Build a parallel string array with the names of each month. Then ask the user to enter a month number, and look up the corresponding month name and number of days and display the information. Continue accepting input and displaying results until the user enters a number less than 1 or greater than 12.
- Review Wikipedia: Zeller's congruence. Create a program that asks the user for their birthday (year, month, and day) and then calculate and
display the day of the week on which they were born. Use an array lookup to convert the numeric day of the week to the correct string representation (Monday, Tuesday, Wednesday, etc.).
Fixed-Length Arrays
- Review MathsIsFun: Definition of Average. Create a program that asks the user to enter grade scores. Start by asking the user how many scores they would like to enter. Then use a loop to request each score and add it to a static (fixed-size) array. After the scores are entered, calculate and display the high, low, and average for the entered scores.
- Review Wikipedia: Monty Hall problem. Create a program that uses an array to simulate the three doors. Use 0 (zero) to indicate goats and 1 (one) to indicate the car. Clear each "door" and then use a random number function to put the number 1 in one of the array elements. Then use the random number function to randomly select one of the three elements. Run the simulation in a loop 100 times to confirm a 1/3 chance of winning. Then run the simulation again, this time switching the selection after a 0 (goat) is removed from the remaining choices. Run the simulation in a loop 100 times to confirm a 2/3 chance of winning by switching.
- If your programming language supports it, use a built-in sort function to sort the grade scores from the activity above and display the array in order from highest score to lowest score.
Dynamic Arrays / Lists
- If your programming language supports it, update the grade score program above to replace the static array with a dynamic array, and extend the array as each item is added to the array. Continue accepting scores until the user enters a negative value.
- Review Khan Academy: A guessing game. Write a program that allows the user to think of a number between 0 and 100, inclusive. Then have the program try to guess their number. Start at the midpoint (50) and ask the user if their number is (h)igher, (l)ower, or (e)qual to the guess. If they indicate lower, guess the new midpoint (25). If they indicate higher, guess the new midpoint (75). Record each guess in an array and continue efficiently guessing higher or lower until they indicate equal. Finally, display the array/list of guesses made while attempting to guess their number and end the program.
- If your programming language supports it, use a built-in sort function to sort the grade scores from the activity above and display the array in order from highest score to lowest score.
Lesson Summary
- Depending on the language, array types may overlap (or be identified with) other data types that describe aggregates of values, such as lists and strings. Array types are often implemented by array data structures, but sometimes by other means, such as hash tables, linked lists, or search trees. In Python, the built-in array data structure is a list.
- Each element in an array will be assigned an index position. Most programming languages will begin at index position 0. This allows the program to recall data stored in a specific position. for instance, an array named "months" would have the data value "March" stored at index position 2. A program can reference this value by referring to "months[2]".
- Arrays can have multiple axes (more than one axis). Each axis is a dimension. Thus a single-dimension array is also known as a list. A two-dimension array is commonly known as a table.
- Arrays are an important complex data type used in almost all programming. We continue to concentrate on simple one dimension arrays also called a list. Most programmers develop a series of user-defined specific task functions that can be used with an array for normal processing. These functions are usually passed the array along with the number of elements within the array. Some functions also pass another piece of data needed for that particular functions task.
- Finding a specific member of an array means searching the array until the member is found. It’s possible that the member does not exist and the programmer must handle that possibility within the logic of his or her algorithm.
- It is important to follow the "Don't Repeat Yourself" (DRY) principle. Rather than having to keep repeating yourself, you can use loops to visit each element of an array and the loop control variable as an array index. This allows for more efficient code and smaller programs.
Key Terms
-
array
-
Data structure consisting of a collection of elements (variables or values), each identified by at least one index or key. It can also be defined as an ordered collection of items indexed by contiguous inters.
-
array member
-
An item or value in an array.
-
dimension
-
An axis of an array. Defines the amount of associated pieces of data that can be stored.
-
don’t repeat yourself
-
A principle of software development aimed at reducing repetition of software patterns, replacing it with abstractions, or repetition of the same data, using data normalization to avoid redundancy.
-
dynamic array
-
A random access, variable-size list data structure that allows elements to be added or removed. The size can be changed when new items are added.
-
flexible coding
-
Using the size of an array to determine the number of loop iterations required.
-
index notation
-
Used to specify the elements of an array. Most current programming languages use square brackets [] as the array index operator. There are different methods for referring to the elements of a list, a vector, or a matrix, depending on whether one is writing a formal mathematical paper for publication, or when one is writing a computer program.
-
linear search
-
Sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
-
list
-
Lists are a form of compiled data, in which there are two types, linear lists which are similar to static arrays, and linked lists, which are similar to dynamic arrays. They can compile multiple different data types.
-
offset
-
The method of referencing array members by starting at zero.
-
parallel array
-
A form of implicit data structure that uses multiple arrays to represent a singular array of records. Also known as structure an array (SoA), multiple arrays of the same size such that i-th element of each array is closely related and all i-th elements together represent an object or entity.
-
sort
-
Arranging data according to their values.
-
static array
-
An array with its length not changing. Items can be replaced or changed but no more can be added or subtracted.
-
table
-
A two dimensional array. A data structure used to organize information, just as it is on paper. There are many different types of computer-related tables, which work in a number of different ways. The following are examples of the more common types.
-
Source: Wikiversity, https://en.wikiversity.org/wiki/Programming_Fundamentals/Arrays This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 License.