Fundamentals of data structures: Arrays

From Wikibooks, open books for an open world
Jump to navigation Jump to search

PAPER 1 - ⇑ Fundamentals of data structures ⇑

← Data structures Arrays Fields records and files →


Arrays[edit]

An array is an indexed set of related elements. When we want to store several pieces of data of the same type, instead of using many variables we can instead use an array. You can think of an array as a list of data items or elements each with a number or index to enable you to refer to each item. Note that the index of the array starts at 0

Many similar variables One Array

name0=Alice
name1=Bob
name2=Claire
name3=Dan
name4=Eve

Names
0 Alice
1 Bob
2 Claire
3 Dan
4 Eve

In most languages, an array must be declared. This sets up how many elements there are in the array and what data type the elements are. This will reserve space in memory for the array before it has been filled with data. Python uses lists in place of arrays. Lists are more flexible and do not require initialisation but it can still be useful to perform this step in order to make your intentions and your code easier to understand.

VB.NET Python
Dim names(0 To 4) As String
names(0) = "Alice"
names(1) = "Bob"
names(2) = "Claire"
names(3) = "Dan"
names(4) = "Eve"
names = ["" for x in range(5)]
names[0] = "Alice"
names[1] = "Bob"
names[2] = "Claire"
names[3] = "Dan"
names[4] = "Eve"

This can also be done in a single line of code, initialising and populating the array in one step.

VB.NET Python
Dim names() As String = {"Alice","Bob","Claire","Dan","Eve"}
names = ["Alice","Bob","Claire","Dan","Eve"]

Array indicies[edit]

We can access a single element of an array by using the index. This is written in parentheses or brackets after the array name. To access Eve from our names array we would useː

VB.NET Python
console.WriteLine(names(4))
print(names[4])

Some programming languages start numbering arrays from 1, others from 0. In our examples above, it does not matter which number relates to which person and so 0 is used as a starting point but if we were storing months, many people might prefer January to be stored in months[1] rather than months[0]. XKCD on Array indicies

Exercise: One-Dimensional Arrays
Declare an array listing 5 animals in a zoo (aardvark, bear, cuckoo, deer, elephant) in alphabetical order:

Answer:

VB.NET Python
dim zooanimals() as string = {"aardvark","bear","cow","deer","elephant"}
zooanimals = ["aardvark","bear","cow","deer","elephant"]
Write code to output the first and last animal

Answer:

VB.NET Python
console.writeline(zooanimals(0))
console.writeline(zooanimals(4))
print(zooanimals[0]
print(zooanimals[4]
Someone has accidentally eaten the cuckoo, let the user add a new third animal and print them all out:
   Code Output
Down arrow Hexagonal Icon.svg

Insert new third animal: Crocodile
1: Aardvark
2: Bear
3: Crocodile
4: Deer
5: Elephant

Answer:

VB.NET Python
console.write("Insert new third animal:")
zooanimals(2) = console.readline()
console.writeline("1: " & zooanimals(0))
console.writeline("2: " & zooanimals(1))
console.writeline("3: " & zooanimals(2))
console.writeline("4: " & zooanimals(3))
console.writeline("5: " & zooanimals(4))
''Alternatively an A-grade student might write:
for x = 0 to 4
  console.writeline(x + 1 & ": " & zooanimals(x))
next
zooanimals[2] = input("Insert new third animal: ")
print("1:",zooanimals[0])
print("2:",zooanimals[1])
print("3:",zooanimals[2])
print("4:",zooanimals[3])
print("5:",zooanimals[4])

#Alternatively an A-grade student might write:
for x in range(5):
 print(x,": ",zooanimals[x],sep="")

Two dimensional arrays[edit]

An array is an indexed set of elements. If each element is itself an array then we have a two dimensional (2d) array.
If we think of an array as a list, we can think of a 2d array as a grid or matrix.
Most major programming languages allow you to use two-dimensional arrays. They work in much the same way as a one-dimensional array but allow you to specify a column index and a row index.

Treat a 2D array like a grid, the location of a cell is shown above

We can create the two-dimensional array shown above and assign values by doing the following:

VB.NET Python
Dim grid(4,4) As String
grid(0,3) = "A"
grid(3,2) = "B"
grid(1,4) = "C"
Console.Writeline("The content of 3,2 is:" & grid(3,2))
grid = [["" for x in range(4)] for x in range(4)] 
grid[0][3] = "A"
grid[3][2] = "B"
grid[1][4] = "C"
print("The content of 3,2 is:",grid[3][2])
The code would also output the value B
Example: Two-Dimensional Arrays

Two-dimensional arrays are very useful and a good place to get started is to create your own version of the game Battleships with a 4 cell by 4 cell grid. See if you can win, break it or better still, improve it!
We are modelling the following board using the two dimensional board variable:

0 1 2 3
0 x o o o
1 o o x o
2 o o o o
3 o o o o
VB.NET Python
Dim x, y As Integer
Dim board(3, 3) As Char
board(0, 0) = "x"
board(0, 1) = "o"
board(0, 2) = "o"
board(1, 0) = "o"
board(1, 1) = "o"
board(1, 2) = "x"
board(2, 0) = "o"
board(2, 1) = "o"
board(2, 2) = "o"
board(2, 0) = "o"
board(2, 1) = "o"
board(2, 2) = "o"
For z = 1 To 3
Console.WriteLine("This is guess number " & z)
Console.Write("please insert your x location:")
x = Console.ReadLine()
Console.Write("please insert your y location:")
y = Console.ReadLine()
If board(x, y) = "x" Then
Console.WriteLine("you win!")
End If
Next
board = [["" for x in range(3)] for x in range(3)] 
board[0][0] = "x"
board[0][1] = "o"
board[0][2] = "o"
board[1][0] = "o"
board[1][1] = "o"
board[1][2] = "x"
board[2][0] = "o"
board[2][1] = "o"
board[2][2] = "o"
board[2][0] = "o"
board[2][1] = "o"
board[2][2] = "o"
for z in range(1,4):
    print("This is guess number", z)
    x = int(input("please insert your x location: "))
    y = int(input("please insert your y location: "))
    if board[x][y] == "x":
        print("you win!")
Exercise: Two-Dimensional Arrays
Declare an array to make a small checkers board of type char, 3 squares by 3 squares

Answer:

VB.NET Python
dim checkBoard(3,3) as char 'also checkBoard(2,2)
checkBoard = [["" for x in range(3)] for x in range(3)]
create a chequered pattern using b for black and w for white

Answer:

VB.NET Python
 checkBoard(1, 1) = "b"
 checkBoard(1, 2) = "w"
 checkBoard(1, 3) = "b"
 checkBoard(2, 1) = "w"
 checkBoard(2, 2) = "b"
 checkBoard(2, 3) = "w"
 checkBoard(3, 1) = "b"
 checkBoard(3, 2) = "w"
 checkBoard(3, 3) = "b"
 checkBoard[0][0] = "b"
 checkBoard[0][1] = "w"
 checkBoard[0][2] = "b"
 checkBoard[1][0] = "w"
 checkBoard[1][1] = "b"
 checkBoard[1][2] = "w"
 checkBoard[2][0] = "b"
 checkBoard[2][1] = "w"
 checkBoard[2][2] = "b"

A much smarter way is to use a loop, this will allow for you to quickly create an board of any size you wish. There is a question coming up that will want you to build this! Note that in python, we are forced to start the index at 0. Also python uses the same datatype for characters and strings.

Write a sub routine to display this board (HINT: you need loops), that takes checkBoard as a parameter

Answer:

VB.NET Python
sub display(checkBoard())
for x = 1 to 3
   for y = 1 to 3
      console.write(checkBoard(x,y))
   Next
   console.writeline()
Next
def display(checkBoard):
    for x in range(3):
        for y in range(3):
            print(checkBoard[x][y],end="")
        print()
Declare a chessBoard (8*8 squares), programmatically colour it in with b for black and w. You might want to look for a pattern in the colour assignments for the checker board above and make friends with the MOD function. You might also go a little loopy trying to answer this question

Answer:

VB.NET Python
dim chessBoard(8,8) as char 'also chessBoard(7,7)
for x = 1 to 8
   for y = 1 to 8
      if (x + y) MOD 2 = 1 then
         chessBoard(x,y) = "w"
      else
         chessBoard(x,y) = "b"
      end if
   next
next
display(chessBoard()) ' using a slightly updated version of the subroutine display()
chessBoard = [["" for x in range(8)] for x in range(8)]
for x in range(8):
   for y in range(8):
      if (x + y) % 2 == 1:
         chessBoard[x][y] = "w"
      else:
         chessBoard[x][y] = "b"
display(chessBoard) # using a slightly updated version of the subroutine display()

If you've done this you might want to get the program to print some massive boards, whatever floats your boat.

Using the following two-dimensional array, grid(4,4):
  • Write code to output the name CRAIG
  • Insert MARY on row 2 (the third row)
  • Overwite STEVE with SAM

CPT-arrays-2d-names.svg

Answer:

VB.NET Python
Console.Writeline(grid(3,0) & grid(3,1) & grid(3,2) & grid(3,3) & grid(3,4))
grid(2,0) = "M"
grid(2,1) = "A"
grid(2,2) = "R"
grid(2,3) = "Y"
grid(1,0) = "S" ' you could skip this
grid(1,1) = "A" 
grid(1,2) = "M"
grid(1,3) = ""
grid(1,4) = ""
print(grid[3][0] + grid[3][1] + grid[3][2] + grid[3][3] + grid[3][4])
grid[2][0] = "M"
grid[2][1] = "A"
grid[2][2] = "R"
grid[2][3] = "Y"
grid[1][0] = "S" # you could skip this
grid[1][1] = "A" 
grid[1][2] = "M"
grid[1][3] = ""
grid[1][4] = ""