Data Structures and Data Manipulation Flashcards
Data Structure
Is a group of related data items.
Static Data Structure
Are those where the size is fixed when the structure is created (the size cannot change during processing).
Dynamic Data Structure
Are those where the size of the data structure changes as data is added and removed.
Static vs Dynamic
Static - amount of storage required known so easier to program. Dynamic - amount of storage not known more complex code.
Stack
LIFO. A stack is a list in which insertion and deletion take place at the same end (TOP). One pointer – top.
Stack - uses
Storing return addresses (during subroutine calls), Passing parameters, Storing contents of registers while processing interrupt
Reversing the order of a set of data.
Stack overflow/underflow
Overflow error when try to push an item onto a full stack and Underflow when try to pop item off empty stack.
Stack – insert algorithm
Push item onto stack
If Stack is full Then Error and stop Else Increment StackPointer. Add data item at position StackPointer End if.
Stack – retrieve/delete alg
Pop item off stack
If Stack is empty Then Error and stop Else Return the data item at position StackPointer. Decrement StackPointer End if.
Queue
FIFO. A queue is a list. Insertion is done at one end, while deletion is performed at the other end. Front and back pointers.
Q overflow/underflow
Overflow error when try to enqueue an item onto a full queue and Underflow when try to dequeue item off empty queue.
Queue - uses
Jobs waiting for a printer in a spool queue, Job queue batch processing system, Keyboard buffer.
Shuffle queue
Front index always fixed (items shuffle up to front when an item is dequeued.
Circular queue
When enqueuing next index moves forward. When dequeuing the front index moves forward. Circular as next pointer wraps to beginning once last index is reached.
Queue – insert algorithm / add item to circular queue
(Enqueue). If Queue is full Then Error and stop Else Add data item at position NextPointer. Increment NextPointer. If NextPointer > MaxIndex Then Assign the value of 1 to NextPointer End if.
Queue – retrieve/delete
from circular queue
(Dequeue). If Queue is empty Then Error and stop Else Return the data item at position FrontPointer. Increment FrontPointer. If FrontPointer > MaxIndex Then Assign the value of 1 to FrontPointer End If End If.
Tree
Tree is represents the relationship between data items. (Stack and queue don’t imply relationship between data items).
Tree - uses
Binary search tree - storing data in such a way that it makes it easy and fast to search. Representing sorted lists of data.
Most databases use this tree concept as the basis of storing, searching and sorting it’s records.
Tree – insert algorithm
add item to a tree
Start at root. REPEAT IF new data
Tree – retrieve algorithm
Start at root. WHILE pointer is not Null DO IF current data = required data THEN RETURN current data ELSE IF required data
Tree – delete algorithm
Deletion is more tricky as simply deleting a node could detach child nodes from the tree. Deletion could be done in the following ways: Mark the node deleted but leave in tree to maintain structure. OR Re-attach any child nodes to the tree
Binary Search
The binary search is more efficient than the linear search, but requires the data to be in order.
Binary Search Alg
1) Look at the item at the midpoint of the list (the current item). 2) If the current item is the item sought, then it has been found. 3) If the current item is not the item sought, discard the half of the list that can’t contain the item sought and repeat the same method with the other half of the list. 4) Keep repeating these steps until the item is found or the list contains no items.
Binary Search Adv
Usually faster because half of the data is discarded at each step and fewer items checked. This is more efficient for large files.
Binary Search Disadv
One disadvantage of a binary search is that items must be in an order to allow appropriate items to be discarded.
Serial Search (Linear)
The search starts at the beginning of the list. Each element in turn is compared with the required value until a match is found or the end of the list is reached.
Serial Search Alg
ThisElement = 1. Found = False. REPEAT IF List[ThisElement] = ElementSought THEN Found = True ELSE ThisElement = ThisElement + 1 UNTIL Found = True OR ThisElement > Max.
Serial Search Adv
A serial search can be used on unordered sets of data.
Serial Search Disadv
Generally slower because all data must be checked until the item is found or the end of the list is reached.
Merging Data Files
Note when merging data files duplicates are not kept (just one appears in the new file).
Merging Data Files Alg
OPEN existing files. CREATE a new file. CHECK existing files are not empty. Use pointers to identify records for comparison. REPEAT compare records indicated by pointers. COPY earlier value record to new file. MOVE correct pointer UNTIL end of one file. COPY the remaining records from the other file. CLOSE the files.
Insertion Sort
Insert one number at a time into correct position… so list of sorted numbers is built up.
Insertion Sort Adv
simple sorting algorithm and relatively efficient for small sets of data and mostly-sorted lists. It’s relatively fast for adding a small number of new items periodically.
Insertion Sort Disadv
Inefficient for large sets of data.
Quicksort
If the first pointer is less than the last pointer (if there are elements in the list) then:
1. Select an item at random to act as the ‘pivot’. 2. Create two new lists 3.…one with all items less than pivot 4…other with all items greater than pivot 5. Repeat these four steps until all lists only have one item.
Quicksort Adv
Very quick for large sets of data.
Quicksort Disadv
Initial arrangement of data affects the time taken. Harder to code.
