g = hash & 0xF0000000;
if(g!=0){
hash ^= g >>> 24;
hash ^= g;
}
}
return hash;
}
A collision occurs in a hash table when two keys are mapped to the same location.
Linked Lists
More flexible than stacks & queues. Objects stored non-contiguously. Objects can be removed or inserted at any point.
A linear data structure where each item has a link to the next item in addition to its own data. Each node usually has two items, data and a link to another node.
private Node head = null;//private Node next;
class Node{
int data;
Node next = null;
}//end Node()
public void addTo(int data){
Node newNode = new Node();
newNode.data = data;
newNode.next = head;
head = newNode;
}//end addTo()
Linked Lists, more
Linked Lists, more
Java example
Circular Linked List
In a typical list, the list ends in null(or a link to null). The circular list is one in which the end node links to the start or to some other node in the list.
public void loopList(){Node current = head;
while(current.next != null){
current = current.next;
}
current.next = head;
}
Double Linked List
The basic list node has its data and a link to the next node. A double link list node has a link to the next node and the previous node.
public void addTo(int data){Node newNode = new Node();
if(isEmpty()){
newNode.prev = null;
newNode.data = data;
newNode.next = null;
head = newNode;
}else{
newNode.data = data;
head.prev = newNode;
newNode.next = head;
head = newNode; }
}//end addTo()
public boolean isEmpty()
{return head == null;}
public void printList(){
Node current = head;
while(current != null){
if(current.prev != null){
System.out.print("prev: "+current.prev.data);
}
System.out.print(" data: "+current.data);
if(current.next != null){
System.out.println(" next: "+current.next.data);
}
current = current.next;
}
System.out.println();
}//end printList()
Max and Min
Function that returns the greatest or smallest item. Useful in sorting.
public static int findMax(int arr[]){
int max = arr[0];
for(int i = 1; i
max=arr[i];
}
}
return max;
}
public static int findMin(int arr[]){
int min = arr[0];
for(int i = 1; i
}
}
return min;
}
Queues
Follows FIFO model, First In First Out. Items may be inserted at any time but only the oldest item may be removed. enqueue objets are inserted at bottom and dequeue removes from the front.Methods
enqueue() Insert item at bottomdequeue() Remove item from front
getFront() Access item at front of queue
isEmpty() Checks to see if the stack is empty, returns "true" if empty
makeEmpty() Remove all items
size() Returns number of items in stack
&nbs p; |QUEUE|
enqueue ---> | |---> dequeue
Java example
data structure where items are typically inserted from the back and removed from the front.
public class BasicQueue{
int maxSize;
int queArray[];
int front;
int rear;
int nItems;
public BasicQueue(int s)
{
maxSize = s;
queArray = new int[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(int j)
{
if(rear == maxSize-1){
for(int i = 0; i
}
queArray[4]=j;
nItems++;
}else{
queArray[++rear]=j;
nItems++;
}
}//end insert
public void showQueue(){
for(int i=0;i<5;i++){
System.out.print(queArray[i]);
}
System.out.println(" endq");
}
/******** end methods ****************/
public static void main(String args[]){
BasicQueue queue = new BasicQueue(5);
queue.insert(5);
queue.insert(4);
queue.insert(3);
queue.insert(2);
queue.insert(1);
queue.showQueue();
queue.insert(8);
queue.showQueue();
queue.insert(5);
queue.showQueue();
queue.insert(7);
queue.showQueue();
}//end main
}//end class
Recursion
Recursive loops make calls to themselves until a condition is met, as opposed iteration which is a loop that repeats until a condition is met.
Iteration:While(x<5){
x++
}
Recursion:
addX(x){
if(x<5){ x++; addX(x); }
}
Recursion and Backtracking
Backtracking is a search method. Similar to going through a maze, one option is followed until exhausted then we backtrack to the next option and try that one.
Sorting
Arrange items in a predetermined order
Terms:Keys: data used to sort, index and cross reference
In place: A sort in which the sorted items occupy the same storage space as the original
Stable: An algorithm where the relative order of input is preserved in the output
Pivot: Used for sorting. A point in a list used for dividing the list into roughly equal sizes for sub-sorting.
Partitioning: Division of a set into non-empty sets, dividing an array into two or more sub-arrays.
Binary Insertion Sort
public void BinaryInsertionSort()
{
for(int Unsorted = 1; Unsorted < a.length; ++Unsorted)
{
if(a[Unsorted] < a[Unsorted-1])
{
int Left = 0;
int Right = Unsorted;
int Mid = 0;
int NextItem = a[Unsorted];
while(Left < Right)
{
Mid = (Left + Right)/2;
if(a[Mid] < NextItem){
Left = Mid + 1;
}else{
Right = Mid;
}
}
}
}
}//end bininsert
Bubble Sort
Repeatedly moving through array and exchanging neighbors that are not in order.
void BubbleSort(){
int N = a.length;
boolean Sorted = false;
for(int Pass = 1; (Pass < N) && !Sorted; ++Pass)
{
Sorted = true;
for(int Index = 0; Index < N-Pass; ++Index)
{
if(compare(Index, Index+1) > 0)
{
swap(Index, Index+1);
Sorted = false;
}
}
}
}//endbubble
Heap Sort
Non-stable. Builds a heap and repeatedly extracts the maximum item. A heap is where every node has a key more extreme than or equal to the one of its parents.
void RebuildHeap(int Root, int Limit){
int Child = 2 * Root + 1;
if(Child < Limit)
{
int RightChild = Child + 1;
if((RightChild < Limit) && (a[RightChild] > a[Child]))
Child = RightChild;
if(compare(Root, Child) < 0)
{
swap(Root, Child);
RebuildHeap(Child, Limit);
}
}
}//rebheap
void HeapSort()
{
int Left, Right, N = a.length;
for(Left = N/2; Left >=0; Left--)
RebuildHeap(Left, N);
for(Right = N - 1; Right >= 1; Right--)
{
swap(0, Right);
RebuildHeap(0, Right);
}
}
Insertion Sort
Stable. Uses original array to hold the sets of keys. “In-place” sort, by taking the next item repeatedly and inserting it into the final structure with respect to items already sorted.
public void InsertionSort(){
for(int Unsorted = 1; Unsorted < a.length; ++Unsorted)
{
int NextItem = a[Unsorted];
int Loc = Unsorted;
for(; (Loc > 0) && (a[Loc-1]>NextItem); --Loc)
{
a[Loc] = a[Loc-1];
}
a[Loc] = NextItem;
}
}//end insertion
Merge Sort
Stable. Splits arrays into two groups then recursively sorts each group and then merges them into a final sorted sequence.
public void mergeSort(int tempArr[], int bottom, int top){
if(bottom == top)
return; //work is done if only 1 item left
else
{
int middle = (bottom+top)/2;
mergeSort(tempArr, bottom, middle);
mergeSort(tempArr, middle+1, top);
merge(tempArr, bottom, middle+1, top);
}
}
/** puts the sorted arrays back together **/
private void merge(int tempArr[], int low, int hi, int top)
{
int j = 0;
int bottom = low;
int middle = hi-1;
int n = top-bottom+1;
while(low <= middle && hi <= top)
if(a[low] < a[hi]){
tempArr[j++] = a[low++];}
else{
tempArr[j++] = a[hi++];}
while(low<=middle){
tempArr[j++] = a[low++];}
while(hi<=top){
tempArr[j++] = a[hi++];}
for(j=0; j
}
O(n), O(log n)
Used for analyzing comparison algorithms. The number of times the major operation occurs, comparison. The worst case is O(n), for too many comparisons and O(1) is the best case, just one comparison. A log of n is much smaller than n, so O(log n) is much smaller than O(n)
Quick sort
Non-stable. Select some key in the array as a pivot key. This is used to separate the array into a right and left partition. Quick sort is then applied to the left and right recursively.
int Partition(int F, int L){
int Pivot = a[F];
int LastS1 = F;
int FirstUnknown = F + 1;
for(; FirstUnknown <= L; ++FirstUnknown)
{
if(a[FirstUnknown] > Pivot)
swap(FirstUnknown, ++LastS1);
}
swap(F, LastS1);
return LastS1;
}//Partition
void Quicksort(int F, int L)
{
if(F < L)
{
int PivotIndex = Partition(F, L);
Quicksort(F, PivotIndex-1);
Quicksort(PivotIndex+1, L);
}
}
Radix Sort
Distributes each item into a bucket according to part of the item’s key. A bucket is an area of storage where items with a common property are stored.
Selection Sort
Look through list finding the smallest item and moving it to the final location.
int IndexOfLargest(int A[], int Size){
int IndexSoFar = 0;
for(int CurrentIndex = 1; CurrentIndex < Size; ++CurrentIndex)
{
if(A[CurrentIndex] > A[IndexSoFar])
IndexSoFar = CurrentIndex;
}
return IndexSoFar;
}//indexoflarg
void SelectionSort()
{
for(int Last = a.length-1; Last >= 1; --Last)
{
int L = IndexOfLargest(a, Last+1);
swap(L, Last);
}
}//selectsort
Shell Sort
A in-place sort which repeatedly reorders small subsets.
public int getexp(int x, int N){
int y = 1;
int val = x;
while(val < N)
{
val *= x;
y++;
}
return y;
}
public int pow(int x, int y)
{
int val = 1;
while(y > 0)
{
val *= x;
y--;
}
return val;
}
void ShellSort()
{
int i, j, k;
int x = 2, y = 0;
y = getexp(x, a.length);
while((k = (((int)pow(x, --y))-1)) > 0)
{
for(i = k; i < a.length; i++)
{
if(a[i] < a[i-k])
{
int scratch = a[i];
j = i;
while((j >= k) && (scratch < a[j - k]))
{
a[j] = a[j - k];
j -= k;
}
a[j] = scratch;
}
}
}
}
Sorting Networks
An oblivious comparison-based algorithm is such that the sequence of comparisons performed is the same for all inputs of any given size. This kind of algorithm has received much attention since it shown as an implementation of circuits:
0 --x--x--------------
| |
1 --x--|--x---x-------
| | |
2 --x--x--|---x-------
| |
3 --x-----x-----------
public class SortNet
{
public static void main(String args[]){
int unSorted[] = {10, 8, 9, 3};
System.out.println("Original array: ");
display(unSorted);System.out.println("- Sorted? :"+isSorted(unSorted));
System.out.println();
System.out.println("Sorted correctly: ");
int sorted[] = sortNet(unSorted);
display(sorted);System.out.println("- Sorted? :"+isSorted(sorted));
System.out.println();
System.out.println("Sent to bad sorter: ");
int unSorted2[] = {10, 8, 9, 3};
int sortedNot[] = sortNetBad(unSorted2);
display(sortedNot);System.out.println("- Sorted? :"+isSorted(sortedNot));
}//end main
/* Good sorting network */
public static int[] sortNet(int arr[]){
arr = compExch(arr, 0, 1);
arr = compExch(arr, 2, 3);
arr = compExch(arr, 0, 2);
arr = compExch(arr, 1, 3);
arr = compExch(arr, 1, 2);
return arr;
}
/* Bad sorting network */
public static int[] sortNetBad(int sortedNot[]){
sortedNot = compExch(sortedNot, 0, 1);
sortedNot = compExch(sortedNot, 2, 3);
sortedNot = compExch(sortedNot, 1, 2);
sortedNot = compExch(sortedNot, 0, 2);
sortedNot = compExch(sortedNot, 1, 3);
sortedNot = compExch(sortedNot, 1, 2);
return sortedNot;
}
public static int[] compExch(int listArray[],int index1, int index2){
if(listArray[index1]>listArray[index2]){
int temp = listArray[index1];
listArray[index1] = listArray[index2];
listArray[index2] = temp;
}
return listArray;
}//end compExch
public static void display(int listArray[]){
for(int i=0; i
}
}//end display
public static boolean isSorted(int listArray[]){
boolean sorted = true;
for(int i=0;i
sorted = false;
}
}
}
return sorted;
}//end isSorted
}//end class
Sorting Networks and the END search algorithm
Sorting networks, more
Sorting Networks, more
Tree Sort
Take unsorted keys in an array and insert them into an empty binary tree. Then perform an in-order traversal.
Stacks
Stacks follow the LIFO model, Last In First Out. Items are inserted at the top of the stack moving other items down in position. Items are removed from the top also and the other items move up in position. The insert function is called PUSH and the removal function is called a POP. In order to access items deep within the stack all the preceding items must be removed. A data structure in which only the most recently added item can be removed. If you need the item at the bottom, everything on the top must be “popped” off first.
PUSH A
| --> |
|
POP A
| --> |
|
Methods
push() Adds item to toppop() extracts most recently added item
topAndPop() Return and remove most recent item
makeEmpty() Remove all items
size() Returns number of items in stack
top() return the item on top without removing it
isEmpty() Checks to see if the stack is empty, returns "true" if empty
public class Stack {
private StackObject s;
private int size;
/** Constructs the empty stack. */
public Stack() {
s = null;
size = 0;
}
/Adds an object to the stack.@param obj the object that will be pushed onto the stack. */
public void push(Object obj) {
if (obj != null) {
s = new StackObject(obj,s);
size = size + 1;
}
}
/** Removes the object at the top of the stack.
* @return The object at the top of the stack, or
*
null if the stack is empty. */public Object pop() {
if (s == null)
return null;
Object obj = s.obj;
s = s.next;
size = size - 1;
return obj;
}
/** Peeks at the object at the top of the stack without removing
* it. @return The object at the top of the stack, or
*
null if the stack is empty. */public Object peek() {
if (s == null) {
return null;
} else {
return s.obj;
}
}
/** Reports if the stack is empty.
* @return
true if the stack is empty,*
false otherwise. */public boolean empty() {
return (s == null);
}
/** The number of elements on the stack.
* @return the number of elements on the stack. */
public int size() {
return size;
}
public void clear() {
s = null;
size = 0;
}/** Clears the stack. */
private class StackObject {
Object obj;
StackObject next;
/** Constructor.
* @param obj The object that is to be put onto the stack.
* @param next The former top of the stack. */
StackObject(Object obj, StackObject next) {
this.obj = obj;
this.next = next;
}/** Represents a single object on the stack. */
}
}
Trees
A data structure made up of child nodes linked to parent nodes.
Terms:Static: Shape determined before run
Dynamic: Shape determined while running
Game Tree: Represents all the possible moves at each stage in a game
Search Tree: Helps to search for pre-stored info that is associated with search keys
Binary Tree: Each node has two children that are either null or trees themselves. Ordered tree in which each internal node has either zero or two children(left and right).
Binary Tree Traversal: A traversal that visits each node of a tree exactly once in a certain order
AVL Tree: Trees in near balanced condition
2-3 Trees: Nodes may have 2 or 3 children
Tries: Organized by a “discrimination net”, shape insensitive to insertion order
General Trees: Set of nodes and a set of edges. Rooted trees: one node is a "root" node.
Ordered tree: Linear ordering defined for the children of each node.
Trees, more
Java example
AVL Trees
A nearly balanced tree where the height of the left and right sub-trees differ no more than one. If more items are inserted, the tree is re-balanced. At each node the height of the two sub tress must differ by at most 1. When insertions/deletions happen, the balance changes. The tree is fixed by rotation
AVL Trees, moreB-Tree
A balanced search tree in which every node has between ceiling(m/2) and m children where m>1 is a fixed integer. A
generalization of 2-3 trees. A “multi-way” tree, designed for disks
Each page has between n & 2n items, except the root which may have as few as 1. Each page has either a leaf page with no
descendants or has m+1 descendants to go with its m terms(n Each node has two children. The children are either empty(null) or are trees themselves, typically left and right. Has a finite set of nodes that are either empty or consist of exactly one root node and at most two sub-trees(right and
left). Each node has at most two children. Each node, except the root node, has exactly one parent node. Once a link has
been followed from a parent to a child, it is not possible to get to the parent by following more links. Children of a node
are trees themselves. Trees with nodes that include keys so that the nodes are sorted with nodes on the left being lesser than those on the
right. Insertion scheme is if n Pre-order: At each node, visit the first node, perform pre-order of left sub-tree then
pre-order the right tree. In-order: At each node, perform in-order of left sub-tree, visit node, then in-order right
tree. Post-order: At each node, perform post-order of left sub-tree, then post order right
tree, then visit node Level-order: Traverse the levels from top to bottom. Within each level, visit nodes
from left to right.
Binary Tree
/ \
C B
/\ /\
n n n n
Binary Search Tree
{
int value; //can be string, char, other ADTs
Tree left;
Tree right;
Tree(int v){
value = v;
left = null;
right = null;
}
Tree(){
left = null;
right = null;
}
public void insert(int v){
//this is the left side of the tree
if(v < value){
//if it’s empty, enter it as a new node
if(left==null){
left = new Tree(v);
//if the node is occupied, insert it again
}else{left.insert(v);}
}
//this is the right side of the tree
else if(v > value){
if(right==null){
right = new Tree(v);
}else{right.insert(v);}
}
}
}
Tree Traversals
System.out.print(value+" ");
if(left != null){
left.preOrder();
}
if(right != null){
right.preOrder();
}
}
if(left != null){
left.inOrder();
}
System.out.print(value+" ");
if(right != null){
right.inOrder();
}
}
if(left != null){
left.postOrder();
}
if(right != null){
right.postOrder();
}
System.out.print(value+" ");
}
Reconstructing Binary Trees From Traversal
Sequences
Other Sources
8 Puzzle
8 Puzzle GUI
AVL Trees
Abstract Data Types
Different Algorithms
DS Examples
DS Intro
DS Programs in C
DS
Programs in Java
Java Examples
Hashing
Hash Table Code
Hash Tables
Huffman Encoding
Huffman Encoding(compression)
Huffman Encoding, more
Huffman Encoding, more
KWIC.java
Linked Lists
Linked Lists, more
Reconstructing Binary Trees From Traversal
Sequences
Sorting Networks and the END search algorithm
Sorting networks, more
Sorting Networks, more
Trees,
more
Trees, more
Books:
Data Structures in Java, Standish
Data Structures and Algorithm Analysis in C, Weiss
