Transcript Class

Chapter 4
Review of Sequential Representations
• Previously introduced data structures, including
array, queue, and stack, they all have the property
that successive nodes of data object were stored
a fixed distance apart.
• The drawback of sequential mapping for ordered
lists is that operations such as insertion and
deletion become expensive.
• Also sequential representation tends to have less
space efficiency when handling multiple various
sizes of ordered lists.
Linked List
• A better solutions to resolve the issues of
sequential representations is linked lists.
• Elements in a linked list are not stored in
sequential in memory. Instead, they are stored all
over the memory. They form a list by recording
the address of next element for each element in
the list. Therefore, the list is linked together.
• A linked list has a head pointer that points to the
first element of the list.
• By following the links, you can traverse the linked
list and visit each element in the list one by one.
Ordered List for Three-letter words
Linked List Insertion
• To insert an element (GAT) into the
three letter linked list:
– Get a node that is currently unused; let
its address be x.
– Set the data field of this node to GAT.
– Set the link field of x to point to the
node after FAT, which contains HAT.
– Set the link field of the node cotaining
FAT to x.
Designing a List in C++
• Design Attempt 1: Use a global variable first
which is a pointer of ThreeLetterNode.
– Unable to access to private data members: data and link.
• Design Attempt 2: Make member functions public.
– Defeat the purpose of data encapsulation.
• Design Attempt 3: Use of two classes. Create a
class that represents the linked list. The class
contains the items of another objects of another
class.
Class ThreeLetterNode {
Private:
char data[3];
ThreeLetterNode *link;
};
ThreeLetterNode *first;
Design 1
Design 3
Program 4.1 Composite Classes
Nested Classes
• The Three Letter List problem can also use nested
classes to represent its structure.
class ThreeLetterList {
public:
// List Manipulation operations
.
.
private:
class ThreeLetterNode { // nested class
public:
char data[3];
ThreeLetterNode *link;
};
ThreeLetterNode *first;
};
Pointer Manipulation in C++
• Addition of integers to pointer variable is
permitted in C++ but sometimes it has no logical
meaning.
• Two pointer variables of the same type can be
compared.
– x == y, x != y, x == 0
x
a
y
b
x
y
a
x
b
b
y
b
x=y
*x = * y
Composite Classes for List and ListNode
Class List; // forward declaration
Class ListNode {
Friend class List;
Private:
int
data ;
ListNode *link;
};
Class List {
Public: // List manipulation operations
Private:
};
ListNode *first:
Define A Linked List Template
• A linked list is a container class, so its
implementation is a good template candidate.
• Member functions of a linked list should be
general that can be applied to all types of objects.
• When some operations are missing in the original
linked list definition, users should not be forced
to add these into the original class design.
• Users should be shielded from the detailed
implementation of a linked list while be able to
traverse the linked list.
Solution => Use of ListIterator
List Iterator
• A list iterator is an object that is used to
traverse all the elements of a container class.
• ListIterator<Type> is delcared as a friend of
both List<Type> and ListNode<Type>.
• A ListIterator<Type> object is initialized with
the name of a List<Type> object l with which it
will be associated.
• The ListIterator<Type> object contains a
private data member current of type
ListNode<Type> *. At all times, current points to
a node of list l.
• The ListIterator<Type> object defines public
member functions NotNull(), NextNotNull(),
First(), and Next() to perform various tests on
and to retrieve elements of l.
Template of Linked Lists
Enum Boolean { FALSE, TRUE};
template <class Type> class List;
template <class Type> class ListIterator;
template <class Type> class ListNode {
friend class List<Type>; friend class ListIterator <Type>;
private:
Type data;
ListNode *link;
};
Template <class Type> class List {
friend class ListIterator <Type>;
public:
List() {first = 0;};
// List manipulation operations
.
.
private:
ListNode <Type> *first;
};
Template of Linked Lists (Cont.)
template <class Type> class ListIterator {
public:
ListIterator(const List<Type> &l): list(l), current(l.first) {};
Boolean NotNull();
Boolean NextNotNull();
Type * First();
Type * Next();
Private:
const List<Type>& list; // refers to an existing list
ListNode<Type>* current; // points to a node in list
};
Attaching A Node To The End
Of A List
Assume there is a private ListNode<Type>* last in
class List<Type>
Template <class Type>
Void List<Type>::Attach(Type k)
{
ListNode<Type>*newnode = new ListNode<Type>(k);
if (first == 0) first = last =newnode;
else {
last->link = newnode;
last = newnode;
}
};
Inverting a List
Concatenating Two Chains
Template <class Type>
void List<Type>:: Concatenate(List<Type> b)
// this = (a1, …, am) and b = (b1, …, bn) m, n ≥ ,
// produces the new chain z = (a1, …, am, b1, bn) in
this.
{
if (!first) { first = b.first; return;}
if (b.first) {
for (ListNode<Type> *p = first; p->link; p = p->link);
// no body
p->link = b.first;
}
}
When Not To Reuse A Class
• If efficiency becomes a problem
when reuse one class to implement
another class.
• If the operations required by the
application are complex and
specialized, and therefore not
offered by the class.
Circular Lists
• By having the link of the last node points
to the first node, we have a circular list.
– Need to make sure when current is pointing to
the last node by checking for current->link ==
first.
– Insertion and deletion must make sure that the
circular structure is not broken, especially the
link between last node and first node.
Examples of Circular Lists
Diagram of A Circular List
first
last
Linked Stacks and Queues
top
front
rear
0
Linked Queue
0
Linked Stack
Revisit Polynomials
a.first
3
14
2
8
1
0
10
6
0
a  3 x14  2 x8  1
b.first
8
14
-3 10
b  8 x14  3x10  10 x 6
0
Polynomial Class Definition
struct Term
// all members of Terms are public by default
{
int coef;
// coefficient
int exp;
// exponent
void Init(int c, int e) {coef = c; exp = e;};
};
class Polynomial
{
friend Polynomial operator+(const Polynomial&, const
Polynomial&);
private:
List<Term> poly;
};
Operating On Polynomials
• With linked lists, it is much easier to
perform operations on polynomials
such as adding and deleting.
– E.g., adding two polynomials a and b
a.first
3
14
2
8
1
0
0
-3
10
10
6
0
p
b.first
8
14
q
c.first
11
14
0
(i) p->exp == q->exp
Operating On Polynomials
a.first
3
14
2
8
1
0
0
10
6
0
p
b.first
8
14
-3
10
q
c.first
11
14
0
-3
10
(ii) p->exp < q->exp
0
Operating On Polynomials
a.first
3
14
2
8
1
0
0
10
6
0
p
b.first
8
14
-3
10
q
c.first
11
14
0
-3
10
(iii) p->exp > q->exp
2
8
0
Memory Leak
• When polynomials are created for computation and
then later on out of the program scope, all the memory
occupied by these polynomials is supposed to return to
system. But that is not the case. Since
ListNode<Term> objects are not physically contained
in List<Term> objects, the memory they occupy is lost
to the program and is not returned to the system.
This is called memory leak.
• Memory leak will eventually occupy all system memory
and causes system to crash.
• To handle the memory leak problem, a destructor is
needed to properly recycle the memory and return it
back to the system.
List Destructor
Template <class Type>
List<Type>::~List()
// Free all nodes in the chain
{
ListNode<Type>* next;
for (; first; first = next) {
next = first->link;
delete first;
}
}
Free Pool
• When items are created and deleted
constantly, it is more efficient to have a
circular list to contain all available items.
• When an item is needed, the free pool is
checked to see if there is any item
available. If yes, then an item is retrieved
and assigned for use.
• If the list is empty, then either we stop
allocating new items or use new to create
more items for use.
Using Circular Lists For Polynomials
• By using circular lists for polynomials
and free pool mechanism, the
deleting of a polynomial can be done
in a fixed amount of time
independent of the number of terms
in the polynomial.
Deleting A Polynomial with a
Circular List Structure
av
3
a.first
3
14
2
1
2
av
second
8
1
0
Equivalence Class
• For any polygon x, x ≡ x. Thus, ≡ is
reflexive.
• For any two polygons x and y, if x ≡ y,
then y ≡ x. Thus, the relation ≡ is
symmetric.
• For any three polygons x, y, and z, if
x ≡ y and y ≡ z, then x ≡ z. The
relation ≡ is transitive.
Equivalence
Definition: A relation ≡ over a set S, is said
to be an equivalence relation over S iff it
is symmetric, reflexive, and transitive
over S.
Example: Supposed 12 polygons 0 ≡ 4, 3 ≡ 1,
6 ≡ 10, 8 ≡ 9, 7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11, and
11 ≡ 0. Then they are partitioned into
three equivalence classes:
{0, 2, 4, 7, 11}; {1 , 3, 5}; {6, 8, 9 , 10}
Equivalence (Cont.)
• Two phases to determine equivalence
– In the first phase the equivalence pairs
(i, j) are read in and stored.
– In phase two, we begin at 0 and find all
pairs of the form (0, j). Continue until
the entire equivalence class containing 0
has been found, marked, and printed.
• Next find another object not yet
output, and repeat the above process.
Equivalence
Definition: A relation ≡ over a set S, is said
to be an equivalence relation over S iff it
is symmetric, reflexive, and transitive
over S.
Example: Supposed 12 polygons 0 ≡ 4, 3 ≡ 1,
6 ≡ 10, 8 ≡ 9, 7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11, and
11 ≡ 0. Then they are partitioned into
three equivalence classes:
{0, 2, 4, 7, 11}; {1 , 3, 5}; {6, 8, 9 , 10}
Equivalence (Cont.)
• Two phases to determine equivalence
– In the first phase the equivalence pairs
(i, j) are read in and stored.
– In phase two, we begin at 0 and find all
pairs of the form (0, j). Continue until
the entire equivalence class containing 0
has been found, marked, and printed.
• Next find another object not yet
output, and repeat the above process.
Equivalence Classes (Cont.)
• If a Boolean array pairs[n][n] is used
to hold the input pairs, then it might
waste a lot of space and its
initialization requires complexity
Θ(n2) .
• The use of linked list is more
efficient on the memory usage and
has less complexity, Θ(m+n) .
Linked List Representation
Linked List for Sparse Matrix
• Sequential representation of sparse matrix suffered from
the same inadequacies as the similar representation of
Polynomial.
• Circular linked list representation of a sparse matrix has
two types of nodes:
– head node: tag, down, right, and next
– entry node: tag, down, row, col, right, value
• Head node i is the head node for both row i and column i.
• Each head node is belonged to three lists: a row list, a
column list, and a head node list.
• For an nxm sparse matrix with r nonzero terms, the number
of nodes needed is max{n, m} + r + 1.
Node Structure for Sparse Matrices
A 4x4 sparse
matrix
 0 0 11 0 
12 0 0

0


0 4 0
0 


 0 0 0  15
Linked Representation of A
Sparse Matrix
Matrix
head
4 4
H0
H1
H2
H3
H3
0 2
11
H0
H1
H2
1 0
12
2 1
-4
3 3
-15
Reading In A Sparse Matrix
• Assume the first line consists of the
number of rows, the number of columns,
and the number of nonzero terms. Then
followed by num-terms lines of input, each
of which is of the form: row, column, and
value.
• Initially, the next field of head node i is to
keep track of the last node in column i.
Then the column field of head nodes are
linked together after all nodes has been
read in.
Complexity Analysis
• Input complexity: O(max{n, m} + r) = O(n +
m + r)
• Complexity of ~Maxtrix(): Since each node
is in only one row list, it is sufficient to
return all the row lists of a matrix. Each
row is circularly linked, so they can be
erased in a constant amount of time. The
complexity is O(m+n).
Doubly Linked Lists
• The problem of a singly linked list is that
supposed we want to find the node precedes a
node ptr, we have to start from the beginning of
the list and search until find the node whose link
field contains ptr.
• To efficiently delete a node, we need to know its
preceding node. Therefore, doubly linked list is
useful.
• A node in a doubly linked list has at least three
fields: left link field (llink), a data field (item),
and a right link field (rlink).
Doubly Linked List
• A head node is also used in a doubly
linked list to allow us to implement
our operations more easily.
Head Node
llink item rlink
llink item rlink
Empty List
Deletion From A Doubly Linked
Circular List