* 9.3, 9.13(a,c,e,i).
Reading Assignments
* Ch 9-9.2, 9.5-9.8.
Assignment #5
* due Fri, Aug 4.
Midterm #2
* Monday, July 31 (covers Recursion!, Arrays, Dynamic Data!!, Linked Lists!!, Data Structures, ADT Design/Implementation!!, OO Design, Big-O!!)
Next Lecture - Q & A about homework/midterm
Object Model (operations omitted)
The implicit "this" pointer
* ref: Lippman pp.233 - 238.
* Each class member function contains a pointer of its class type named "this". (yet another keyword!)
class Customer {
public:
const char* get_name();
private:
char* name;
};
const char*
Customer::get_name()
{
return this->name; // you can omit "this->"
}
Using the "this" pointer
* Usually you do not have to explicitly use the "this" pointer, because
1. You can make a member function call without it.
2. You can access a data member without it.
* But if you need to return the entire class object...
return this; // return the pointer to this object
return *this; // return the object
* Why do you need that?
class Complex {
public:
Complex operator = (const Complex& other);
...
};
Complex
Complex::operator = (const Complex& other)
{
real = other.real;
imag = other.imag;
// return Complex(real,imag);
return *this; // you can do this!
}
An example of the design of ADTs - Set ADT
* Recall: a set is an unordered collection of objects without duplicates.
class Int_Set { // different from the text.
public:
Int_Set();
~Int_Set();
Boolean is_empty() const;
Boolean is_member(int x) const;
void insert(int x);
void remove(int x);
private:
int* elem;
int size;
int max_size;
};
Int_Set::Int_Set()
{
max_size = 4;
size = 0;
elem = new int[max_size];
}
Int_Set::~Int_Set()
{
delete [] elem;
}
// O(1)
Boolean
Int_Set::is_empty() const
{
return (size == 0);
}
is_member
// O(size)
Boolean
Int_Set::is_member(int x) const
{
for (int i = 0; i < size; i++) {
if (elem[i] == x) {
return TRUE;
}
}
return FALSE;
}
insert
void
Int_Set::insert(int x)
{
if (is_member(x) { // no duplicate!
return;
}
if (size == max_size) {
max_size *= 2;
int* old = elem;
elem = new int [max_size];
for (int i = 0; i < size; i++) {
elem[i] = old[i]
} delete [] old;
}
elem[size] = x;
size++;
} // run time complexity? O(size)
remove
void
Int_Set::remove(int x)
{
int pos = locate(x); // O(size)
elem[pos] = elem[size];
size--;
// if you want to shrink the array if necessary
if (size <= max_size / 4) {
max_size /= 2;
// allocate new array and copy array elem's
// similar to the code for insert.
}
}
Ring Buffer implementation of a Queue
* Recall: a queue is a linear, sequential access data structure in which all insertions occur at the rear and all deletions occur at the front.
class Int_Queue { // similar to the text
public:
Int_Queue();
Boolean is_empty() const;
Boolean is_full() const;
int get_front() const;
void enqueue(int x)
void dequeue();
private:
int data[SIZE];
int front;
int rear;
};
Int_Queue()
{
front = rear = 0;
}
Boolean
Int_Queue::is_empty() const // O(1)
{
return (front == rear);
}
Boolean
Int_Queue::is_full() const // O(1)
{
return ((rear + 1) % SIZE) == front);
}
int
Int_Queue::get_front() const // O(1)
{
if (is_empty()) {
// some appropriate error message
} else {
return data[front];
}
}
void Int_Queue::enqueue(int x) // O(1)
{
if (is_full()) {
// some appropriate error message
} else {
data[rear] = x;
rear = (rear + 1) % SIZE;
}
}
void
Int_Queue::dequeue() // O(1)
{
if (is_empty()) {
// some appropriate error message
} else {
front = (front + 1) % SIZE;
}
}
Int_Queue q;
q.enqueue(1);
q.enqueue(3);
q.enqueue(5);
q.enqueue(7);
q.enqueue(2);
q.get_front();
q.dequeue();
q.dequeue();
q.enqueue(4);
q.enqueue(6);
Summary
* An ADT is more than data structures and functions. It is a tightly knit encapsulation of data values and related operations.
* Designing ADTs is a creative process of inventing a "type" and "operations" that match the problem to be solved.
* Every ADT may have many possible implementations, and the implementor must evaluate their trade-offs in efficiency, memory usage, flexibility and ease of coding.
* C++ classes are important for constructing ADTs.
* ADTs => more readable, maintainable, reusable!