Transcript CSCI 240 Abstract Data Types - Department of Computer and

Department of Computer and Information Science,
School of Science, IUPUI
CSCI 240
Abstract Data Types
Dale Roberts, Lecturer
IUPUI
[email protected]
Dale Roberts
Abstract Data Type Defined
Sedgewick Definition 4.1:
An abstract data type (ADT) is a data type (a set of values
and a collection of operations on those values) that is
accessed only through an interface. We refer to a program
that uses an ADT as a client, and a program that specifies
the data type as an implementation.
The key distinction that makes a data type abstract is the word
only. Client programs never access data except through the
operations provided in the interface. We say that the interface is
opaque. The client cannot see the implementation through the
interface. This is also called encapsulation.
Dale Roberts
Point ADT Interface
// point.h
class POINT
{
private:
// Implementation-dependent code
public:
POINT();
float distance(POINT) const;
};
We can use different implementations (point.cpp) that have the
same interface without changing any code in the client programs
that use the ADT.
Dale Roberts
Pushdown-stack
Stack model
A stack is a list with the restriction that insertion & deletion can be performed
only at the end (or top) of the list.
Only the top node is accessible: New nodes can be added and removed only
at the top
Similar to a pile of dishes
S4
top
Last-in, first-out (LIFO)
S3
Bottom of stack indicated by a link member to NULL
S2
S1
Constrained version of a linked list
push
Adds a new node to the top of the stack
pop
top
Removes a node from the top
Stores the popped value
Returns true if pop was successful
1
3
6

Push (4)
4
1
3
6
top

Pop (4)
1
3
6
top
A stack can be empty, “pop” from an empty stack is an error
A stack can never be full (assuming infinite memory)
Dale Roberts
Sample stack linked-list implementation (C)
struct list
{
int data
struct list *next;
}
typedef struct list node;
typedef node *link;
4
newnode
4
3
stack
3
2
Push
link push(link stack, int value)
{
1
link newnode;
newnode = (link)malloc(sizeof(node));
newnode->data = value;
newnode->next = stack;
stack = newnode;
top
return(stack);
4
stack
}
Pop
3
link pop(link stack, int *valuePtr)
{
2
link top;
top = stack;
stack = stack->next;
1
*valuePtr = top->data;
free(top);
return(stack);
}
stack
newnode
2
1
4
top
3
stack
valuePtr
4
2
1
Dale Roberts
Pushdown-stack ADT interface
template <class Item>
class STACK
{
private:
// Implementation-dependent code
public:
STACK(int);
int empty() const;
void push(Item item);
Item pop();
};
Dale Roberts
Array implementation of pushdown stack
template <class Item>
class STACK
{
private:
Item *s; int N;
public:
STACK(int maxN)
{ s = new Item[maxN]; N = 0; }
int empty() const
{ return N == 0; }
void push(Item item)
{ s[N++] = item; }
Item pop()
{ return s[--N]; }
};
Dale Roberts
Linked-list implementation of a pushdown stack
template <class Item>
class STACK
{
private:
struct node
{ Item item; node* next;
node(Item x, node* t)
{ item = x; next = t; }
};
typedef node *link;
link head;
public:
STACK(int)
{ head = 0; }
int empty() const
{ return head == 0; }
void push(Item x)
{ head = new node(x, head); }
Item pop()
{ Item v = head->item; link t = head->next;
delete head; head = t; return v; }
};
We can implement the push and
pop operations for the pushdown
stack ADT in constant time, using
either arrays or linked lists.
Dale Roberts
Queues
Queue
Similar to a supermarket checkout line
First-in, first-out (FIFO)
Nodes are removed only from the head
Nodes are inserted only at the tail
Insert and remove operations
Enqueue (insert) and dequeue (remove)
Queue Model
queue is a list, with insertion done only at one end and deletion done at the other
end.
enqueue: insert an element at the end of the queue
dequeue: delete (and return) the element at the start of the queue
first in first out model (FIFO)
Linked list implementation of queues
operating as a list
constant time for enqueue & dequeue (keeping pointer to both the head
and tail of the list)
Dale Roberts
Sample linked-list implementation (C)
enqueue
link enqueue(link queue, int value)
{
link newnode;
newnode = (link)malloc(sizeof(node));
newnode->data = value;
newnode->next = NULL;
if (queue!=NULL)
{
queue->next = newnode;
queue = queue->next;
}
else
queue = newnode;
return(queue);
}
queue
newnode
dequeue
link dequeue(link queue, int *valuePtr)
{
link dequeuenode;
dequeuenode = queue;
*valuePtr = dequeuenode ->data;
queue = queue->next;
free(dequeuenode);
return(queue);
}
Dale Roberts
FIFO queue ADT interface
template <class Item>
class QUEUE
{
private:
// Implementation-dependent code
public:
QUEUE(int);
int empty();
void put(Item);
Item get();
};
Dale Roberts
FIFO queue linked-list implementation
template <class Item>
class QUEUE
{
private:
struct node
{ Item item; node* next;
node(Item x)
{ item = x; next = 0; }
};
typedef node *link;
link head, tail;
public:
QUEUE(int)
{ head = 0; }
int empty() const
{ return head == 0; }
void put(Item x)
{ link t = tail;
tail = new node(x);
if (head == 0)
head = tail;
else t->next = tail;
}
Item get()
{ Item v = head->item; link t = head->next;
delete head; head = t; return v; }
};
Dale Roberts
FIFO queue array implementation
template <class Item>
We can implement get and
class QUEUE
put operations for the
{
FIFO queue ADT in
private:
Item *q; int N, head, tail; constant time, using either
public:
arrays or linked-lists.
QUEUE(int maxN)
{ q = new Item[maxN+1];
N = maxN+1; head = N; tail = 0; }
int empty() const
{ return head % N == tail; }
void put(Item item)
{ q[tail++] = item; tail = tail % N; }
Item get()
{ head = head % N; return q[head++]; }
};
If head = tail, then empty; if put would make them
equal, then full. Array is 1 larger to allow checks.
Dale Roberts
DYNAMICALLY LINKED STACKS AND QUEUES
top
element link


  
NULL
(a) Linked Stack
front
rear
element link


  
NULL
(b) Linked queue
*Figure 4.10: Linked Stack and queue (p.147)
Dale Roberts
Represent n stacks
#define MAX_STACKS 10 /* maximum number of
stacks */
typedef struct {
int key;
/* other fields */
} element;
typedef struct stack *stack_pointer;
typedef struct stack {
element item;
stack_pointer link;
};
stack_pointer top[MAX_STACKS];
Dale Roberts
Represent n queues
#define MAX_QUEUES 10 /* maximum number of
queues */
typedef struct queue *queue_pointer;
typedef struct queue {
element item;
queue_pointer link;
};
queue_pointer front[MAX_QUEUE],
rear[MAX_QUEUES];
Dale Roberts
First-class ADT
Sedgewick Definition 4.4:
Our Fraction ADT
is a first-class
ADT.
A first-class data type is one for which we can have
potentially many different instances, and which we
can assign to variables which we declare to hold the
instances.
Our prior examples provided a capability to use a single instance of
a particular generalized stack or queue, and to achieve the important
objective or hiding the data structure (or encapsulating the data)
from the client. This situation is analogous to having a program that
manipulates only one integer.
Dale Roberts
First-class Queue ADT
template <class Item>
class QUEUE
{
private:
// Implementation-dependent code
public:
QUEUE(int);
QUEUE(const QUEUE&);
QUEUE& operator=(const QUEUE&);
~QUEUE();
Notice how each and every
int empty() const;
interface operations now includes
void put(Item);
a references to a particular Q. We
Item get();
can create as many queues as we
};
need.
Dale Roberts
First-class ADT interface for polynomials
template <class Number>
class POLY
{
private:
// Implementation-dependent code
public:
POLY<Number>(Number, int);
float eval(float) const;
friend POLY operator+(POLY &, POLY &);
friend POLY operator*(POLY &, POLY &);
};
Dale Roberts
Linked-list implementation of polynomials
A( x )  a m 1 x e
m1
 a m 2 x e
m 2
... a 0 x e
0
Representation
typedef struct poly_node *poly_pointer;
typedef struct poly_node {
int coef;
int expon;
poly_pointer link;
};
poly_pointer a, b, c;
coef
expon
link
Dale Roberts
Examples
a  3x  2 x  1
14
a
3
8
14
2
b  8 x  3x  10 x
14
b
8
14
10
-3 10
0
null
10 6
null
1
8
6
Dale Roberts
Adding Polynomials
3
14
a
8 14
b
11 14
d
3
14
2
8
1
-3 10
0
10 6
a->expon == b->expon
2
8
1
0
-3 10
10
6
b
-3 10
d
a->expon < b->expon
a
8
14
11 14
Dale Roberts
Adding Polynomials (Continued)
3
14
2
8
1
0
a
8
14
-3 10
10 6
b
11 14
-3 10
a->expon > b->expon
2
8
d
Dale Roberts
Circularly Linked Lists
circular list vs. chain
ptr
3
14
2 8
1
0
avail
ptr
temp
avail
...
Dale Roberts
Deleting a polynomial in contant time using a circular
linked-list and an available list.
avail

ptr
(1)
(2)

  

  

temp

NULL
avail
Dale Roberts
Head Node
Represent polynomial as circular list.
(1) zero
-1
a
Zero polynomial
(2) others
a
-1
3
2 8
14
1 0
a  3x  2 x  1
14
8
Dale Roberts
Sparse Matrices
0

12
0

0
0
11
5
4
0
0
0
0
0 

0 
0 

15 
Sparse matrices have a large number of zero
elements in proportion to the number of nonzero
elements.
Storing in n x n array will have a lot of wasted
space.
Alternative: circular lists storing only nonzero
elements.
Dale Roberts
Matrix ADT (C)
matrix_pointer mread(void);
void mwrite(matrix_pointer node);
void merase(matrix_pointer *node);
matrix_pointer madd(
matrix_pointer a,
matrix_pointer b)
And other matrix operations like sub, multiply, etc.
It is typical to typedef matrix_pointer Matrix.
#include “Matrix.h”
In code:
Matrix a, b, c;
c = madd(a, b);
Dale Roberts
Sparse Matrix Nodes
# of head nodes = # of rows + # of columns
head node
down
head
right
next
entry node
down entry row col
right
value
aij
tag
i
j
aij
tag is used to tell entry, head and aij nodes part Dale Roberts
Linked Representation for Matrix
4 4
0 2
11
1 0
12
1
1
5
2 1
-4
3 3
-15
Circular linked list
Dale Roberts
Sparse Matrix Data Structure
#define
typedef
typedef
typedef
MAX_SIZE 50 /* size of largest matrix */
enum {head, entry} tagfield;
struct matrix_node *matrix_pointer;
struct entry_node {
int row;
int col;
int value;
};
typedef struct matrix_node {
matrix_pointer down;
matrix_pointer right;
tagfield tag;
union {
matrix_pointer next;
entry_node entry;
} u;
};
matrix_pointer hdnode[MAX_SIZE];
Dale Roberts
Try creating your data for this matrix
[0] [1] [2]
[0]
[1]
[2]
[3]
[4]
4
0
1
2
3
4
4
2 11
0 12
1 -4
3 -15
Dale Roberts
Acknowledgements
All of this code is from Horowitz, Sahni, and Anderson-Freed,
Fundamentals of Data Structures in C.
Some slides were originally developed by Chen, Hsin-His.
Dale Roberts