3.3.5: Data Structures and Data Manipulation

Static data structure
1. Size of structure determined when writing program.
2. Size of data structure has to be estimated during the creation of the program
3. Space can be wasted.
Dynamic data structure
1. Size of structure updates based on the information that is stored in it.
2. Only uses the space needed at any time
3. More difficult to program.
Stacks
1. Last in first out data structure
2. Insertion
  1. 1: Check to see if stack is full
  2. 2: If stack is full report an error and stop
  3. 3: Increment stack pointer
  4. 4: Insert item into cell pointed to by the stack pointer and stop
3. Deletion / Reading
  1. 1: Check to see if stack is empty
  2. 2: If stack is empty report an error and stop
  3. 3: Copy data item at cell pointed at by the stack pointer
    1. The data item copied can be either discarded or read depending on the operation that is being performed
  4. 4: Decrement the stack pointer and stop
Queues
1. First in first out data structure
2. Insertion
  1. 1: Check to see if queue is full
  2. 2: If queue is full report an error and stop
  3. 3: Insert item to the cell that is pointed to by the head pointer.
  4. 4: Increment head pointer and stop
3. Deletion / Reading
  1. 1: Check to see if queue is empty
  2. 2: If queue is empty report an error and stop
  3. 3: Copy data item pointed to by the tail pointer
  4. 4: Increment the tail pointer and stop
Binary Tree
1. 1. An example of a binary tree
2. 1. Dynamic data structures have to be stored as static data structures in order to be processed by the computer. Binary trees, for example, are stored in the form of an array (a static data structure). Above is the binary tree on the left stored as an array.
3. Insertion
  1. 1: If tree is empty enter data item at root and stop
  2. 2: Current node = root
  3. 3: Repeat steps 4 & 5 until current node = null
  4. 4: If data item is less than the value at the current node then go left else go right
  5. 5: Current node = node reached (null if no node).
  6. 6: Create new node and enter data
4. Deletion
  1. Option 1: Leave the structure of the tree unchanged by labeling the deleted node as deleted, keeping it in the tree but making sure it is not read when the tree is searched.
  2. Option 2: Start from the node to be deleted and gather all of the values from the nodes below the node to be deleted and store in some form of data structure (other than a tree). Then remove the node to be deleted and starting from the node above the node that was deleted add the nodes saved in the separate file back into the tree.
    1. In reality both methods are used. Option 1 because it is quicker and, after a certain number of nodes have been deleted this way,Option 2 is used in order to clear space in memory (as marking the node as deleted means that the node stays in memory.)
Searching
1. Serial Searching
  1. Requires data to be in consecutive order locations (meaning require data to be in a data structure such as an array)
  2. Does not require data to be in a order
  3. To find the position of a value you have to iterate through the list comparing each value with the value you are looking for.
  4. The smallest amount of searches that is required is 1 when the item is at the top of the list and n where n = number of items, when item is at the bottom of the list, therefore the speed of this algorithm is n / 2
2. Binary Searching
  1. Like serial searching requires data to be in consecutive order locations
  2. The data needs to be sorted into order first which can take some time.
  3. To find the position of a value the midway of the list is looked at and the item is compared against this item to see if it is smaller or bigger than the item. The same is then done for the items above or below it depending on whether the item is less or more than the item that is midway until one item is left.
    1. If there are two items in the middle the smaller value item is used.
  4. 1. Speed of serial searching as opposed to binary searching
Merging lists
1. Compare the first two items in two sorted lists. The smaller one is put in a new list and is removed from it's list. The lists are again compared until all of the items have been put in the new list.

Next up

3.3.5: Data Structures and Data Manipulation

Description

Resource summary

Media attachments

Similar

	Created by Adam Cook over 8 years ago