ABSTRACT DATA TYPES
Data Structures and Algorithms 1 FIT – HNUE 2020
THE ARRAY STRUCTURE
• A one-dimensional array is composed of multiple sequential elements
stored in contiguous bytes of memory and allows for random access to
the individual elements.
• The entire contents of an array are identied by a single name.
• Individual elements within the array can be accessed directly by
specifying an integer subscript or index value, which indicates an oset
from the start of the array.
Data Structures and Algorithms 2 FIT – HNUE 2021
THE ARRAY ABSTRACT DATA TYPE
• A one-dimensional array is a collection of contiguous elements in which
individual elements are identified by a unique integer subscript starting with
zero. Once an array is created, its size cannot be changed.
• Array( size ): Creates a one-dimensional array consisting of size elements with each
element initially set to None. size must be greater than zero.
• length(): Returns the length or number of elements in the array.
• getitem( index ): Returns the value stored in the array at element position index. The
index argument must be within the valid range. Accessed using the subscript operator.
• setitem( index, value ): Modifies the contents of the array element at position index to
contain value. The index must be within the valid range. Accessed using the subscript
operator.
• Clearing( value ): Clears the array by setting every element to value.
• iterator(): Creates and returns an iterator that can be used to traverse the elements of
the array.
Data Structures and Algorithms 3 FIT – HNUE 2021
USING ARRAY
# Fill a 1-D array with random values, then print them, one per line.
from array import Array
import random
# The constructor is called to create the array.
valueList = Array( 100 )
# Fill the array with random floating-point values.
for i in range(len(valueList)):
valueList[ i ] = random.random()
# Print the values, one per line.
for i in range(len(valueList)):
print(valueList[ i ])
Data Structures and Algorithms 4 FIT – HNUE 2021
IMPLEMENTING THE ARRAY
• Using The ctypes Module: The ctypes module provides a technique
for creating arrays that can store references to Python objects.
import ctypes
ArrayType = ctypes.py_object * 5
slots = ArrayType()
• creates an array named slots that contains five elements
• The elements of the array have to be initialized before they can be
used.
for i in range( 5 ) :
slots[i] = None
Data Structures and Algorithms 5 FIT – HNUE 2021
THE CLASS DEFINITION
Data Structures and Algorithms 6 FIT – HNUE 2021
WHY STUDY ARRAYS?
• there are two major differences between the array and the list:
• an array has a limited number of operations, which commonly include those for array
creation, reading a value from a specific element, and writing a value to a specic
element. The list, on the other hand, provides a large number of operations for working
with the contents of the list.
• the list can grow and shrink during execution as elements are added or removed while
the size of an array cannot be changed after it has been created.
• Why use arrays:
• There are many problems that only require the use of a basic array in which the
number of elements is known beforehand and the flexible set of operations available
with the list is not needed.
• The array is best suited for problems requiring a sequence in which the maximum
number of elements are known up front, whereas the list is the better choice when the
size of the sequence needs to change after it has been created.
• But the extra space is wasteful when using a list to store a fixed number of elements.
Data Structures and Algorithms 7 FIT – HNUE 2021
