A data structure is a simple way of representing data held in a computers memory.
Types of data Structures to know:
One dimensional Arrays
Two dimensional Arrays
Three dimensional Arrays
Records
Tuples
Lists
Stacks
Queues
Characteristics:
There are two categories of data structures:
- Static or Dynamic
This means it could be seen as inefficient
Static structures are easier to program and on system requirements, this is because they are fixed sizes, inflexible.
Dynamic:
Dynamic structures, data can vary in size to fulfil all of memory. Memory is allocated dynamically (as the program is executed, therefore changes in size.
Disadvantage= memory allocation is dynamic possibility of data overflow, exceeding the limit.
Advantage= makes the most efficient use of memory
Static:
Memory is allocated at compile time in fixed sizes
Advantages= Memory allocation is fixed and so there is no problem with adding and removing data items.
Disadvantages= Can be very inefficient as the memory for this data has been set aside whether its needed of not during execution of the program.
Advantages= Easier to program as there is no need to check on data structure size at any point.
Key operations:
Sorting data - e.g. by a unique key
Searching data- using a specific item to search.
Append date (based on primary key
Big O Notation measures the efficiency of data structures.
www.bigocheatsheet.com
Arrays- Their dimensions
One-Dimensional
All arrays have one unique identifier
There is also an index number - these are 0 based, therefore they always start at 0
Each piece of data within any data structure is called an element.
To code an Array
You use [] square brackets to code the start and the end
To access or change data you simply call the index n umber of the data that you want.
Arrays are static data structures so their sizes do not change once compiled from the programming language.
Two Dimensional
Arrays can have double dimensions.
It is an array within an array
There is a unique identifier
Square brackets used to open first array
The second set of square brackets are used to create the table.
ALL THE DIFFERENT SQUARE BRACKETS MEAN A DIFFERENT ARRAY WITH THE ARRAY IS STARTING!
To separate an array we use an X and Y column
Therefore you need to have 2 index numbers,
X always comes first as if it were a graph
Three Dimensional
There is an X Y and Z axis.
These consist of an array that is inside of an array which is also inside of an array.
Similar to a cube of data.
Different brackets code different data structures!
Array values are stored in a contiguous way (one after the other) and 2D arrays are allocated in row order (first row and then second)
Arrays can be Global or Local variables.
It is impossible to remove all elements from an array once it has been created however you can set the elements to NULL (which means none in python)
For loops have a predefined amount of times to loop
However a WHILE loop doesn't know how many times it needs to be executed.
Records, Lists and Tuples:
Records:
- A record is a data structure
- It is always sorted by a type of attribute
- They do not have to be the same data type
- When you want to access data within a data structure like a record you always have to access it through its attribute
- To do this you use a dot system (address_book.first_name)
- Data found within a data structure is unordered unless you use indices, these can be used to order them.
- Only numbers can be ordered in a data structure.
- Attributes make the data more user friendly
- Lists can be used in Python in order to create arrays
- These and Tuples are very similar however there are some key minor differences:
- In the exam you can identify a list as they use square brackets
- These sit halfway between an array and Tuple (in appearance and characteristics)
- These can hold different types of data types like Tuples
- Unlike Tuples these can be edited once they have been assigned (just like arrays)
- These require an index number to retrieve data (Makes it harder to use as attributes are easy to understand instead of index numbers)
- Lists are mutable (items can be edited or deleted)
Tuples:
- These are similar to records
- They are used to group data together
- Very similar to a one dimensional array however there are differences:
- Tuples are immutable once they have been assigned (cannot be changed)
- Unlike arrays the data types don't have to be the same
- In the exam you can identify a Tuple as it uses normal brackets
- Items are retrieved again using an index like an array
- You cannot add or remove items as these are immutable they can not be changed in anyway.
- Most commonly used where it is important that data can be accessed but not changed!
Dictionary brackets-{}
Tuples brackets-()
Stacks:
- These are good for linear data
- These operate on a LIFO data structure (Last in, First Out)
- Add data from the top and remove from the top (Pancake stack on a plate, the last on the plate: Last cooked, is the first eaten!)
- Adding data to the stack is called Pushing
- Removing data from the stack is called Popping
- These terms are used with the Little Man computer
- Stacks are implemented using an array
- A stack within computers memory system is implemented using pointers.
- Pointers are only used to located the top of the stack
- Stack pointers use a base 0 number system.
- Pushing or popping always takes place at the top of the stack
- If you have a pop instruction the stack pointer moves by -1
- If you have a push instruction the stack pointer moves by +1
- Errors can occur at the bottom or the top of the stack;
- if the stack is full and you try to push another piece of data there will be a stack overflow error
- if the stack is empty and you try to pop another piece of data there will be an error
IF stack pointer =maximum:
THEN repot stack full
STOP
ELSE:
increase stack pointed by 1
set stack (stack pointer) to data
END-IF
IF stack pointer =minimum:
THEN repot stack empty
STOP
ELSE:
set data to stack (stack pointer)
decrease stack pointed by -1
END-IF
Queues:
- First in first out
- The most recent piece of data to the queue is the last piece of data to be taken out
- There are two pointers:
- One to monitor the back of the queue where data is added
- one for the front of the queue where data will be removed from
- The data within a queue does not physically move forward in the queue (this is because it will be inefficient), instead the two pointers are used to denote the front (data removed) and back (data added) of the queue, and these pointers move.
- The pointers are designated ranges so they know where to move.
- These are a circular data structure- unlike stacks.
- The end pointer can be 'before' the start pointer, but as the queue is a circular data structure it will read from the start, then go back to the beginning to read to the end point
The Questions:
2. A stack contains the values 3,4,5 with a 3 being the start/ the first value in the stack stored and the 5 being the last. Show how the stack changes when the following sequence of commands is used:
POP
PUSH 7
POP
PUSH 8
PUSH 9
9
|
|||||
5
|
7
|
8
|
8
|
||
4
|
4
|
4
|
4
|
4
|
4
|
3
|
3
|
3
|
3
|
3
|
3
|
3. A queue contains the values 3, 4, 5, with 3 being 3 being the first value stored and 5 the last, Show how the queue changes after the following commands:
POP
PUSH 7
POP
PUSH 8
PUSH 9
3
|
4
|
5
|
|||
4
|
5
|
||||
4
|
5
|
7
|
|||
5
|
7
|
||||
5
|
7
|
8
|
|||
5
|
7
|
8
|
9
|
No comments:
Post a Comment