Transcript List

CS121 Data Structures
CS_121 Data Structures
Credit Points:
Taught:
Contact Hours:
Lecturer:
10
Teaching Block 2
20 lectures
Dr. Sharp
CS121 © JAS 2005
1-1
CS121 Data Structures
Lectures
Monday 17.00-17.50 Faraday - K
Thursday 14.00-15.00 Grove
Practical Classes
There are no practical classes
There will be Program Advisory
CS121 © JAS 2005
1-2
CS121 Data Structures
Assessment:
CS121 is assessed by written examination in May/June (70%)
and by coursework (30%).
CORE module so need 40%
Students will be expected to pass both the exam and the coursework
Recommended Reading
There are many books – all cover similar ground. It is not necessary
to purchase one – you are advised to use them in the library
to read round topics and purchase if you find one especially
useful
CS121 © JAS 2005
1-3
CS121 Data Structures
Some possible texts
D A Riley, The object of data abstraction and structures using Java, AddisonWesley, 2003
D A Bailey, Java Structures: Data Structures in Java for the Principled
Programmer, McGraw-Hill, 2002
W J Collins, Data Structures And The Java Generic Library , International
Student Edition, McGraw-Hill, 2001
M Main, Data Structures and Other Objects using Java, Addison-Wesley, 2nd
Edition, 2003
F M Carrano & W Savitch, Data Structures and Abstractions with Java,
Pearson Education, 2003
D J Barnes & M Kolling, Objects First with Java, Prentice-Hall, 2003
CS121 © JAS 2005
1-4
CS121 Data Structures
Aims:
•
Enforce the idea that we must make careful selection of
the data structure we are to use
•
Provide practise in identifying the efficiency aspects of
data structures which are in turn dependent upon what
operations we are to carry out on the data structures
•
To contribute to the knowledge that will make you
competent programmers
CS121 © JAS 2005
1-5
CS121 Data Structures
Content:
•
We will look at different data structures of varying
complexity
•
We will look at the operations that can be carried out on
these data structures
•
We will compare the efficiency aspects of all the data
structures
•
The exercises will give you practise implementing these
data structures
CS121 © JAS 2005
1-6
CS121 Data Structures
Algorithms + Data Structures = Programs
Niklaus Wirth, 1976
Programming
Algorithms
Data
Done in CS-141
See CS-132
This module
CS121 © JAS 2005
1-7
CS121 Data Structures
All data is stored in terms of
Bits, Bytes, Words, Records, Files
Bit pattern can be used to represent different types of data –
integer, character, real number etc
Bit pattern can be interpreted as various data values
Bit pattern is implementation of a data type
Data Type is representation + operations
CS121 © JAS 2005
1-8
CS121 Data Structures
Some standard Data Types
Stacks, Queues, Lists, Trees, Hash Tables
For each Data Type
define by operations
specify representation in pre-defined types
implement operations
CS121 © JAS 2005
1-9
CS121 Data Structures
Abstract Data Types (ADTs)
• provide precise specifications
• specify requirements independent of implementation
• can be used to prove correctness of implementation
We will initially look at ADTs for two linear (list-like) data
structures
Stacks
- LIFO (last in, first out)
Queues
- FIFO (first in, first out)
CS121 © JAS 2005
1-10
CS121 Data Structures
A Stack, S, of items of type T is a sequence of items of type T
on which the following operations are defined:
1.
Initialise the stack S to be the empty stack.
2.
Determine whether or not the stack, S, is empty.
3.
Determine whether or not the stack, S, is full.
4.
Push a new item onto the top of the stack, S.
5.
If S is nonempty determine the value of the top item of
the stack.
6.
If S is nonempty, pop an item from the top of stack, S.
CS121 © JAS 2005
1-11
CS121 Data Structures
A Queue, Q, of items of type T is a sequence of items of type
T on which the following operations are defined:
1.
Initialise the queue Q to be the empty queue.
2.
Determine whether or not the queue, Q, is empty.
3.
Determine whether or not the queue, Q, is full.
4.
Insert a new item onto the back of the queue, Q.
5.
If Q is nonempty, determine the value at the head of the
queue.
6.
Provided Q is nonempty, remove an item from the head
of Q.
CS121 © JAS 2005
1-12
CS121 Data Structures
Types for Stack ADT
•
•
•
•
•
•
initialise: |  S
empty: S  Boolean
full: S  Boolean
top:
S  T  error
pop:
S  S  error
push: S  T  S
CS121 © JAS 2005
1-13
CS121 Data Structures
Axioms for Stack ADT
•
•
•
•
•
•
•
empty(nil_stack)
empty(push(x,s))
top(push(x,s))
pop(push(x,s))
top(nil_stack)
pop(nil_stack)
push(x,nil_stack)
where {x} is a
• push(x,s)
where {x|s} is
been placed on
= true
= false
= x
= s
= error
= error
= {x}
stack containing only x
= {x|s}
a stack where x has
top of stack s.
CS121 © JAS 2005
1-14
CS121 Data Structures
Applications
Reversing a list/word
Matching parentheses
Arithmetic Expression Conversion and Evaluation
CS121 © JAS 2005
1-15
CS121 Data Structures
Template for Stack ADT
The Java Class Libraries include a stack class called
Java.util.stack
We will look at how we could define a Stack class
CS121 © JAS 2005
1-16
CS121 Data Structures
public class MyStack
{ public MyStack( int max)
{ }
public boolean empty()
{ }
public Object top()
{ }
public void pop()
{ }
public void push(Object z)
{ }
}
CS121 © JAS 2005
1-17
CS121 Data Structures
Infix Expression
Postfix Expression
(a + b)
a b +
(x – y - z)
x y – z -
(x – y - z) / (u + v)
x y – z – u v + /
(a2 + b2) * (m - n)
a 2 ^ b 2 ^ + m n - *
CS121 © JAS 2005
1-18
CS121 Data Structures
public String infixToPostfix(String exp)
{ stack shunt = new stack();
String pofix = "";
for ( int i=0;i<exp.length();i++)
{ switch (exp.charAt(i))
{case '(' : { shunt.push('('); break;}
case ')' : { while (shunt.top()!= '(')
{pofix = pofix+shunt.pop();}
shunt.pop();
break;
}
CS121 © JAS 2005
1-19
CS121 Data Structures
case '+' : case '-': case '*': case '/':
case '^‘ :
{ while((!shunt.isEmpty() &&
((shunt.top()!= '(') &&
(oppriority(shunt.top()) >=
oppriority(exp.charAt(i))))))
{ pofix = pofix + shunt.pop();}
shunt.push(exp.charAt(i));
break;
}
default :
{ pofix = pofix + exp.charAt(i);}
} // end of switch
} // end of for
1-20
CS121 © JAS 2005
CS121 Data Structures
while (!shunt.isEmpty())
{ pofix = pofix + shunt.pop(); }
return pofix;
} // end of infixToPostfix
private int oppriority(char ch)
{ switch (ch)
{
case '+': case '-' : return(1);
case '*': case '/' : return(2);
case '^': return(3);
default : return(4);
}
}
CS121 © JAS 2005
1-21
CS121 Data Structures
Types for Queue ADT
•
•
•
•
•
•
initialise: |  Q
empty: Q  Boolean
full:
Q  Boolean
head: Q  T  error
remove: Q  Q  error
insert: Q  T  Q
CS121 © JAS 2005
1-22
CS121 Data Structures
Axioms for Queue ADT
•
•
•
•
•
•
•
•
•
empty(nil_queue)
= true
empty(insert(x,q)) = false
head(insert(x,nil_queue)) = x
head(insert(x,q)) = head(q)
remove(insert(x,nil_queue)) = nil_queue
remove(insert(x,q)) = insert(x,remove(q))
head(nil_queue)
= error
remove(nil_queue)
= error
insert(x,nil_queue) = {x}
where {x} is a queue containing only x
• insert(x,q)
= {q|x}
where {q|x} is a queue where x has
been placed at the end of queue q. 1-23
CS121 © JAS 2005
CS121 Data Structures
A template for Queue ADT
public class MyQueue
{ public MyQueue( int max)
{ }
public boolean empty()
{ }
public Object head()
{ }
public void remove()
{ }
public void insert(Object z)
{ }
}
CS121 © JAS 2005
1-24
CS121 Data Structures
Applications of Queues
• Simulations
– Queues at checkouts, traffic systems, production lines
• Scheduling Systems
• Reservation Systems
CS121 © JAS 2005
1-25
CS121 Data Structures
Implementing a Stack using an Array
public class ArrayStack
{ private Object[] theArray;
private int topIndex;
public ArrayStack( int max)
{ theArray = new Object[max];
topIndex = -1;
}
public boolean isEmpty()
{ return (topIndex == -1);
}
CS121 © JAS 2005
1-26
CS121 Data Structures
public Object top()
{ if (isEmpty())
{throw new EmptyStackException();}
else {return theArray[topIndex];}
}
public void pop()
{ if (isEmpty())
{throw new EmptyStackException();}
else {topIndex--;}
}
CS121 © JAS 2005
1-27
CS121 Data Structures
public void push(Object z)
{ if (topIndex < theArray.length-1)
{ topIndex++;
theArray[topIndex] = z;
}
else {throw new IllegalStateException();}
}
}
CS121 © JAS 2005
1-28
CS121 Data Structures
An a
An alternative to throwing exceptions
for methods that don’t return
a value is return a boolean value indicating success or failure
public boolean pop()
{ if (isEmpty())
{return false;}
else
{topIndex--;
return true;}
}
CS121 © JAS 2005
1-29
CS121 Data Structures
For methods that do return a value we could return a null or
dummy value
public Object top ()
{if (isEmpty())
{return null; /* or suitable value */}
else
{return theArray[topIndex];}
}
CS121 © JAS 2005
1-30
CS121 Data Structures
Implementation of a Queue
using an array
length-1
0
length-2
1
2
3
4
CS121 © JAS 2005
1-31
CS121 Data Structures
public class ArrayQueue
{ private Object[] theQ;
private int front;
private int back;
public ArrayQueue( int max)
{ theQ = new Object[max+1];
front = max; /* one before front */
back = max;
}
CS121 © JAS 2005
1-32
CS121 Data Structures
public boolean isEmpty()
{ return( front == back )
}
public Object head()
{ if isEmpty()
{ throw new NoSuchElementException();}
else
{ return(theQ[NextIndex(front)]) }
}
CS121 © JAS 2005
1-33
CS121 Data Structures
private int NextIndex(int i)
{ if (i++ == theQ.length)
return 0;
else return i;
}
public void remove()
{ if isEmpty()
{ throw new NoSuchElementException();}
else
{ front = NextIndex(front); }
}
CS121 © JAS 2005
1-34
CS121 Data Structures
public void insert(Object z)
{ back = NextIndex(back);
if (front == back)
{ throw new IllegalStateException();}
else
{ theQ[back] = z;}
}
}
CS121 © JAS 2005
1-35
CS121 Data Structures
Stacks and Queues are linear data structures
We can combine them by defining a Dequeue (double-ended queue)
add and remove operations can be performed at both ends
CS121 © JAS 2005
1-36
CS121 Data Structures
isEmpty(EmptyDQ)
isEmpty(DQ)
lHd(lJoin(x, DQ))
rHd(rJoin(DQ, x))
lHd(rJoin(EmptyDQ, x))
rHd(lJoin(x, EmptyDQ))
lHd(rJoin(DQ,x))
rHd(lJoin(x,DQ))
lTl(lJoin(x, DQ))
rTl(rJoin(DQ, x))
lTl(rJoin(EmptyQ, x))
rTl(lJoin(x, EmptyQ))
lTl(rJoin(DQ, x))
rTl(lJoin(x,DQ))
CS121 © JAS 2005
=
=
=
=
=
=
=
=
=
=
=
=
=
=
True
False
x
x
x
x
lHd(DQ)
rHd(DQ)
DQ
DQ
EmptyQ
EmptyQ
rJoin(lTl(DQ), x)
lJoin(x, rTl(DQ))
1-37
CS121 Data Structures
Stacks, Queues and Dequeues are special forms of List
For a List as well as adding and removing items from the
ends we normally define methods to add or delete items
from anywhere in the List
CS121 © JAS 2005
1-38
CS121 Data Structures
Operations that could be defined
isEmpty, isFull – test to see if list empty, or full
length – return length of list
add – at front, at back, at given position
replace – at front, at back, at given position
remove – at front, at back, at given position
view – entry at front, at back, at given position
clear – remove all entries
search – to see if an entry exists in a list
CS121 © JAS 2005
1-39
CS121 Data Structures
Many of these methods are going to be similar to those for
Stacks, Queues and Dequeues.
In particular the methods for manipulating the two ends of a
List are identical to those required for a Dequeue (which
combines the Stack and Queue methods
CS121 © JAS 2005
1-40
CS121 Data Structures
public class AList
{ private Object[] theList;
private int length;
public Alist(int max)
{ length = 0;
theList = new Object[max];
}
public boolean isEmpty()
{ return (length == 0); }
public boolean isFull()
{ return (length == theList.length); }
CS121 © JAS 2005
1-41
CS121 Data Structures
public boolean add(Object newEntry)
{ if (!isFull())
{ theList[length] = newEntry;
length++;
}
else
{throw new IllegalStateException();}
}
CS121 © JAS 2005
1-42
CS121 Data Structures
public addat(int newPosn, Object entry)
//for position count from 1
//whereas array is indexed from 0
{ if (!isFull() && (newPosn >=1)
&& (newPosn <= length+1))
{ makeRoom(newPosn);
theList[newPosn-1] = entry;
length++;
}
else {throw new
IllegalStateException();}
}
CS121 © JAS 2005
1-43
CS121 Data Structures
private void makeRoom(int newPosn)
{ //work from end of list,
//move each entry to next higher position
//until entry at newPosn
for (int index = length;
index >= newPosn;
index--)
theList[index] = theList[index-1];
}
CS121 © JAS 2005
1-44
CS121 Data Structures
Removing and viewing entries at either end can use the same
methods as for stacks, queues, dequeues
To view, remove or replace an entry at a given position can all
use the same basic approach
CS121 © JAS 2005
1-45
CS121 Data Structures
public Object viewEntry(int posn)
{ if ((posn >= 1) && (posn <= length))
return theList[posn-1];
else
{throw new IllegalStateException();}
}
public void replace(int posn, Object entry)
{ if ((posn >= 1) && (posn <= length))
theList[posn-1] = entry;
else
{throw new IllegalStateException();}
}
CS121 © JAS 2005
1-46
CS121 Data Structures
public Object remove(int posn)
{ Object result = null; //return value
if ((posn >= 1) && (posn <= length))
{ result = theList[posn-1];
if (posn < length)
removeGap(posn);
length--;
}
return result;
}
CS121 © JAS 2005
1-47
CS121 Data Structures
private void removeGap(int posn)
{ // Shift entries that are above posn
// to next lower position
for (int index = posn;
index < length;
index++)
theList[index – 1] = theList[index];
}
CS121 © JAS 2005
1-48
CS121 Data Structures
For large lists (arrays) both the removeGap and
makeRoom methods can cause a lot of data movement.
The implementation of a Queue avoided the need for data
movement by using a (virtual) circular array.
The same approach could be used for a list. removeGap
and makeRoom could be adapted to move entries forwards
or backwards depending upon which end was nearer the
position referred to.
CS121 © JAS 2005
1-49
CS121 Data Structures
As well as accessing entries in a list by position, we
may wish to access by value - search for an entry.
public int locate(Object reqd)
{ for (int index = 0;
index < length;
index++)
{ if (reqd.equals(theList[index]))
return (index+1);
}
throw new IllegalStateException();
}
CS121 © JAS 2005
1-50
CS121 Data Structures
We have implemented lots of different methods for Stacks,
Queues, Dequeues, and Lists.
Many of them can be implemented in terms of a smaller set of
“basic” or “fundamental” methods.
Assume we have only
List.isEmpty
List.isFull
List.addAt
List.removeAt
List.size
CS121 © JAS 2005
1-51
CS121 Data Structures
Stack.isEmpty
Stack.isFull
Stack.push
Stack.pop
Stack.top
Stack.size
==
==
==
==
==
==
Queue.isEmpty
List.isEmpty
Queue.isFull
List.isFull
List.addAt(1)
List.removeAt(1)
//ignore value
== List.removeAt(1);
List.addAt(1,<top>)
== List.size
CS121 © JAS 2005
1-52
CS121 Data Structures
Queue.add
Queue.remove
Queue.examine
List.add
List.replace(x,z)
List.viewEntry(x)
== List.addAt(List.size)
== List.removeAt(1)
// ignore value
== List.removeAt(1);
List.addAt(1,<examine>)
== List.addAt(List.size)
== List.removeAt(x);
List.addAt(x,z)
== List.removeAt(x);
List.addAt(x,<entry>)
CS121 © JAS 2005
1-53
CS121 Data Structures
List.locate(value)
==
for (index = 0; index < length; index++)
{ if(value.equals(List.viewEntry(index))
return index;
}
CS121 © JAS 2005
1-54
CS121 Data Structures
Our Stack, Queue and List implementations have all
been based on a fixed size array
A max value was supplied with the constructor when a new
Stack, Queue or List object was created
If the size of the Stack, Queue or List grew beyond this
value we either get an error, or we need to increase the size
of the array
CS121 © JAS 2005
1-55
CS121 Data Structures
In Java we have a number of options
• Instead of using the Java array use vector
• When the Stack, Queue, List is full create a new
Stack, Queue, List object based on a larger array
and copy the data into it
– How much bigger?
• Use linked objects – which can also reduce the amount of
data movement
CS121 © JAS 2005
1-56
CS121 Data Structures
The concept of a list relies on the concept of a reference
When a variable stores an object it is not stored in the
variable directly; rather an object reference is stored in the
variable. This reference can be thought of as the address
of the object
CS121 © JAS 2005
1-57
CS121 Data Structures
The general format for a node in a list is:data
next
data
next
private class Node
{ private Object data;
private Node next;
private Node(Object value)
{ data = value;
next = null;
}
private Node(Object value,
Node rest)
{ data = value;
next = rest;
}
1-58
}
CS121 © JAS 2005
CS121 Data Structures
We can now implement a linked list in Java
public class LList
{ private Node firstnode;
private int length; //not essential
public LList()
{ clear(); // default constructor
}
public final void clear()
{ firstnode = null;
length = 0;
}
CS121 © JAS 2005
1-59
CS121 Data Structures
public boolean isEmpty ()
{ return (firstnode == null);
}
public Object viewHead ()
{ if isEmpty()
{ throw new NoSuchElementException(); }
else
{ return firstnode.data; }
}
CS121 © JAS 2005
1-60
CS121 Data Structures
public Node tail()
{ if isEmpty ()
{ throw new IllegalStateException(); }
else
{ length--;
return (firstnode.next); }
}
public int size()
{ return length; }
CS121 © JAS 2005
1-61
CS121 Data Structures
public void prefix(Object x)
{ Node tmp = new Node(x);
length++;
firstnode = tmp;
}
public LList prefix2(Object x, LList y)
{ Node tmpnode = new Node(x,y);
LList newlist = new Llist();
newlist.firstnode = tmpnode;
newlist.length = y.length + 1;
return newlist;
1-62
}
CS121 © JAS 2005
CS121 Data Structures
As before with the array implementation let us consider the
operations that add/view/delete entries at a specified
position.
We can implement a private getNodeAt method
private getNodeAt(int posn)
{//assume not an empty list
Node current = firstnode;
for (int cnt = 1; cnt < posn; cnt++)
current = current.next;
return current;
}
CS121 © JAS 2005
1-63
CS121 Data Structures
We can now define our position specific methods
public boolean addAt(int pos,Object entry)
{ boolean success = true;
if ((pos >=1) && (posn <= length+1))
{ Node newNode = new Node(entry);
if (isEmpty() || (pos == 1))
{ newNode.next = firstnode;
firstnode = newNode;
}
CS121 © JAS 2005
1-64
CS121 Data Structures
else
{ Node before = getNodeAt(posn-1);
Node after = before.next;
newNode.next = after;
before.next = newNode;
}
length++;
else success = false;
return success;
}
CS121 © JAS 2005
1-65
CS121 Data Structures
The methods for removing or viewing entries should be
obvious.
Another common requirement for a list is to be able to access
the end (as opposed to the head) – typically if we are using
it to implement a queue.
This can be done by knowing the length and using the
getNodeAt method.
An alternative is a doubly-linked list.
CS121 © JAS 2005
1-66
CS121 Data Structures
The general format for a node is:before
data
next
before
data
next
private class DNode
{ private Object data;
private Node next;
private Node before;
private Node(Object value)
{ data = value;
next = null;
before = null;
}
}
CS121 © JAS 2005
1-67
CS121 Data Structures
Arrays vs Linked Lists
Space Requirements
• Array fixed size; Linked List flexible (limited by computer
memory)
• Array allocates space for unused entries; Linked List
requires space for references
Operational Efficiency
• Array access to any element is O(1); Linked list access to
any element (except end(s)) is O(n)
• Insertion into Array O(n) and involves data movement;
Insertion into Linked List does not involve data movement
CS121 © JAS 2005
1-68
CS121 Data Structures
CS121 © JAS 2005
1-69