DATA STRUCTURES
A data structure is a collection of different data items that are stored
together as a single unit and the operations allowable on them. Such
data structures includes arrays, trees, linked lists, stacks and queues.
Data structures can be static or dynamic.
Static data structure
Are those which do not change in size while the program is running,
e.g arrays and fixed length records.
Most arrays are static, i.e., once you declare them, they cannot change
in size.
It main advantage is that amount of storage is known and therefore is
easier to program
Advantages of Static Data Structures
Easy to check for overflow
Memory allocation is fixed and therefore there is no problem with
adding and removing data items.
Compiler can allocate space during compilation
Easy to program as there is no need to check for data structure size at
any given time/point
An array allows random access and is faster to access elements than in
other data structures
Disadvantages of Static Data Structures
Programmer has to estimate maximum amount of space needed,
which may be difficult
Can waste a lot of space if some space is left with no data entered into
it.
Adding, removing and modifying elements is not directly possible. If
done, it requires a lot of resources like memory.
DYNAMIC DATA STRUCTURES
Can increase and decrease in size while the program is running, e.g.
binary trees, linked lists, etc.
they uses the space needed at any time, no limitations at all, unless
computer memory is full
its size changes as data is added & removed (size is not fixed)
Advantages of Dynamic Data Structures
Only uses the space that is needed at any time
Makes efficient use of the memory, no spaces lie idle at any given point
Storage no-longer required can be returned to the system for other
uses.
Does not allow overflow
There is effective use of resources as resources are allocated at run-
time, as they are required.
Disadvantages of Dynamic Data Structures
Complex and more difficult to program as software needs to keep track
of its size and data item locations at all times
Can be slow to implement searches
A linked list only allows serial access
Static data structure
Array
An array is a static data structure, which stores and implements a set of items
of the same data type using the same identifier name, in contiguous memory
location. Every array element is accessed or referenced using an index
(subscript), therefore uses index register addressing. It can either store
integers, or names, but not both in one unit.
Declaration of arrays using VB 6.0
Arrays are declared by stating the following parameters: array name, array
size, dimensions and the data type. The size of the array is the maximum
number of elements that it can store. For example, the following declares an
array that reserves five locations in memory and labels these as ‘Names’:
Dim Names(4) As String
This can also be declared as
Dim Names(0 to 4 ) As String
One may also declare the array as
Dim Names(1 to 5) As String
The last option modifies the starting value and the ending value of the indices,
but the number of elements still remains the same.
By default, this implies that the array stores at most 5 elements. On
running, the computer creates 5 contiguous memory locations under
the name “Names”. Thus Names will contain 5 partitions. Each memory
partition will be accessed using an index, which is the address of the
memory space in the array.
In Visual Basic, the number of elements stored in an array is N + 1,
N being the number (subscript) used when declaring the array.
Array index starts at Zero up to N, N being the number in the declaration
of the array.
The index is also called Subscript, and therefore arrays are subscripted
data types.
It is not possible to exceed the upper limit or go below the lower limit
on the array index values. You will receive a “Subscript out of range”
error message if you try to do so.
In the above declaration, the array index starts from 0 to 4 and are
integer values. The memory locations will be as follows:
Names[0] Names[1] Names[2] Names[3] Names[4]
The five individual locations are Names (0), Names (1), Names (2),
Names (3) and Names (4).
Each data item is called an element of the array. To reference a
particular element one must use the appropriate index.
NB: However, most programming languages differ with Microsoft Visual basic in
handling arrays, especially on the amount of memory allocated. For example, using
Java, the following declaration:
Int [4 ]Names;
This array declaration creates exactly 4 memory spaces for the array Names. The
indices of the array range from 0 to 3 which are
Names[0], Names[1], Names[2] and Names[3]
Initialising an array in Visual Basic 6.0
The procedure of initializing an array in the computer memory is as
follows:
- Size of array is calculated
- Location of array is decided according to data type and size
- Locations are reserved for the array
- Size of array is stored in a table
- Lower bound of the array is stored in a table
- Upper bound of array is stored in a table
- Data type is stored in a table
- Address of first element is stored in a table
Inserting data into an array
One may use the assignment statement or use looping structures. For
example, the following statement assigns data to the 4th element:
Names(3) = “Manyeruke”
Arrays simplify the processing of similar data. An algorithm for getting
four names from the user and storing them in the array Names is shown
below:
Dim Names(4) As String
For i=0 to 4
Input Value
Names(i)=Value
Next i
One-dimensional arrays
A one-dimensional array is a data structure in which the array is
declared using a single index and can be visually represented as a list.
The following diagram shows the visual representation of the array
Names(4):
0 Theresa
1 Lameck
2 Johanne
3 Laurence
4 Fadzai
Two-dimensional arrays
A two-dimensional array is a data structure in which the array is
declared using two indices and can be visually represented as a table.
Indices 0 1 2 3
0 Makombe Tinashe M 4A
1 Vheremu Alex M 4B
2 Mununi Mary F 3C
3 Chirongera Salpicio M 2C
4 Mutero Violet F 4C
The diagram above shows the visual representation of a 2 dimensional
array Names(4,3)- 5 rows and 4 columns:
Each individual element can be referenced by its row and column
indices. For example:
Names(0,0) is the data item “Makombe”
Names(2,1) is the item “Mary”
Names(1,2) is the item “M”
Initialising an array
Initialising an array is a procedure in which every value in the array is
set with starting values – this starting value would typically be “” for a
string array, or 0 for a numeric array.
Initialisation is important to ensure that the array does not contain
results from a previous use, elsewhere in the program.
Algorithm for initialising a one-dimensional numeric array:
DIM TestScores(9) As Integer
DIM Index As Integer
FOR Index = 0 TO 9
TestScores(Index) = 0
NEXT Index
Algorithm for initialising a two-dimensional string array:
DIM Students(4,3) As String
DIM RowIndex, ColumnIndex As Integer
FOR RowIndex = 0 TO 4
FOR ColumnIndex = 0 TO 3
Students(RowIndex,ColumnIndex) = “”
NEXT ColumnIndex
NEXT RowIndex
Serial search on an array
The following pseudo-co de can be used to search an array to see if an
item X exists:
01 DIM Index As Integer
02 DIM Flag As Boolean
03 Index = 0
04 Flag = False
05 Input X
06 REPEAT
07 IF TheArray(Index) = X THEN
08 Output Index
09 Flag = True
10 END IF
11 Index = Index + 1
12 UNTIL Flag = True OR Index > Maximum Size Of TheArray
13 IF Flag = False THEN
14 Show Message “Item not found”
15 END IF
Note that the variable Flag (line 04 and 09) is used to indicate when the
item has been found and stop the loop repeating unnecessarily (line 12
ends the loop if Flag has been set to True).
The Actual Visual Basic Code will be as follows:
Dim Index As Integer
Dim Flag As Boolean
Dim x As Integer
Index = 0
Flag = False
x = InputBox("Enter item to Search")
Do
If Names(Index) = x Then
MsgBox (Names(Index) & " Has Been Found")
Flag = True
End If
Index = Index + 1
Loop Until (Flag = True Or Index > UBound(Names))
If Flag = False Then
MsgBox (x & " is not in the array")
End If
Sorting Array Elements
Dim y As Integer
Dim p As Integer
Dim z As Integer
For y = LBound(Names) To UBound(Names)
For p = LBound(Names) To UBound(Names) - 1
If Names(y) < Names(p) Then
z = Names(y)
Names(y) = Names(p)
Names(p) = z
End If
Next p
Next y
Deleting Array Elements
Dim i As Integer
For i = LBound(Names) To UBound(Names) - 1
Names(i) = Names(i + 1)
Next
' VB will convert this to 0 or to an empty string.
Names(UBound(Names)) = Empty
The above algorithm will shift elements of the array up (or left), removing
the first element and then completely removing the last element in the array.
The following is an alternative method of deleting an array element:
Dim Index As Integer
Dim Flag As Boolean
Dim x As Integer
Index = 0
Flag = False
x = InputBox("Enter item to Search")
Do
If Names(Index) = x Then
MsgBox (Names(Index) & " Has Been Found")
Flag = True
Names(Index) = Empty
End If
Index = Index + 1
Loop Until (Flag = True Or Index > UBound(Names))
If Flag = False Then
MsgBox (x & " is not in the array")
End If
The algorithm first searches the element to delete, and then remove it from
the array.
NB:
If the item is string, it replaces with empty spaces. However, if it is
numeric, it replaces with a 0.
Deleting form an array is often difficult as elements need to be shifted
positions after deletion. It is an effective method for deleting elements.
Dynamic Declaration of Arrays:
Arrays can also be declared dynamically so that the user has to decide the
size of the array when the program is running. The user does not need to
specify the number of elements during the declaration stage. Dynamic
declaration of arrays is done as follows:
Dim Names( ) As String
Inside the module, one then needs to redefine the array as follows:
ReDim Names(5) As String
This allows the user to create the array when he/she actually needs it, using
a ReDim statement: Dynamic arrays can be re-created at will, each time with
a different number of items. When you re-create a dynamic array, its
contents are reset to 0 (or to an empty string) and you lose the data it
contains. If you want to resize an array without losing its contents, use the
ReDim Preserve command:
ReDim Preserve Names(20) As String
