4.2.1 Data Structures and Abstract Data Types Flashcards
Data Structure definition
Containers used by computers to store information within.
Array definition
An indexed set of related elements.
An array must be
Finite, indexed and only contain elements with the same data type.
Array indexes start from
0
Two types of arrays
One dimensional and two dimensional.
How is information stored by computers
As a series of files.
Files are made up of
Records
Records are composed of
Fields
What are abstract data structures
Don’t exist as data structures in their own right, instead they make use of other structures such as arrays to form a new way of storing data.
Example of abstract data strucutres
Queues Stacks Graphs Trees Hash tables Dictionaries
Queue definition
Abstract data structure based on an array
First thing added to a queue is
The first thing to be removed
Queues are used by computers in
Keyboard buffers, each keypress is added to the queue and then removed when the computer has processed the keypress - ensuring the letters appear on the screen in the same way they were typed.
An algorithm using the queue is
The breadth first search algorithm to keep track of which nodes in a network have been visited.
Linear queue components
Two pointers - a front pointer and a rear pointer
