Programming Fundamentals/Arrays

From Wikiversity
Jump to navigation Jump to search

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.[1] Some programming languages may refer to arrays as lists. This lesson introduces defined-value arrays, fixed-length arrays, and dynamic arrays.

Objectives and Skills[edit | edit source]

Objectives and skills for this lesson include:

  • Understand single and multi-dimensional arrays
  • Understand dynamic arrays
  • Use arrays to implement program functionality

Readings[edit | edit source]

  1. Rebus: Programming Fundamentals
  2. Wikipedia: Array data type
  3. Wikipedia: Dynamic array

Multimedia[edit | edit source]

  1. YouTube: Programming For Beginners - Arrays
  2. YouTube: Programming For Beginners - Dictionaries and Hashes
  3. YouTube: Static Arrays vs. Dynamic Arrays
  4. YouTube: An Overview of Arrays and Memory (Data Structures and Algorithms #2)
  5. YouTube: What is an Array? - Processing Tutorial

Practice[edit | edit source]

Examples[edit | edit source]

Activities[edit | edit source]

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[edit | edit source]

  1. Review MathsIsFun: Leap Years. Create a program with a defined 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. Ask the user to enter a year and month number and then look up the corresponding month name and number of days and display the information. Continue accepting input until the user enters an invalid year or invalid month number.[2]
  2. 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[edit | edit source]

  1. 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.
  2. 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.
  3. 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[edit | edit source]

  1. 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.
  2. 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.
  3. 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[edit | edit source]

  • 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.[3] In Python, the built-in array data structure is a list.[4]
  • 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]".[5]
  • 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.[6]
  • 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.[7]
  • 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.[8]
  • 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.[9]

Key Terms[edit | edit source]

Data structure consisting of a collection of elements (variables or values), each identified by at least one index or key.[10] It can also be defined as an ordered collection of items indexed by contiguous inters.[11]
array member
An item or value in an array.[12]
An axis of an array. Defines the amount of associated pieces of data that can be stored.[13]
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.[14]
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.[15]
flexible coding
Using the size of an array to determine the number of loop iterations required.[16]
index notation
Used to specify the elements of an array. Most current programming languages use square brackets [] as the array index operator.[17] 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. [18]
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.[19]
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.[20]
The method of referencing array members by starting at zero.[21]
parallel array
A form of implicit data structure that uses multiple arrays to represent a singular array of records.[22] 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.[23]
Arranging data according to their values.[24]
static array
An array with its length not changing. Items can be replaced or changed but no more can be added or subtracted.[25]
A two dimensional array.[26] 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.[27]

Assessments[edit | edit source]

See Also[edit | edit source]

References[edit | edit source]

  1. Wikipedia: Array data type
  2. Farrell, J. (2015). Programming Logic and Design, Introductory, 8th Edition. Cengage. ISBN 9781285845777
  3. "Array data type". Wikipedia. 2019-01-30. 
  5. "Arrays and Lists – Index Notation". Retrieved 2019-10-25.
  6. "Arrays and Lists – Programming Fundamentals". Retrieved 2019-04-03.
  7. "Math Statistics with Arrays – Programming Fundamentals". Retrieved 2019-04-03.
  8. "Searching Arrays – Programming Fundamentals". Retrieved 2019-04-03.
  20. "Programming Concepts: Lists - Wikibooks, open books for an open world". Retrieved 2019-11-01.
  25. Wikipedia: Array data structure