ADT's
Abstract
Data Types:
An abstract data
type is a description of a collection of data and things you can do with that
data. It is strictly a "pencil and paper" thing.
each operator
should have a pre-condition and a post-condition
There is no
definitive abstract data type (ADT)
Larger projects
take planning about what kind of classes you have to make for the particular
project so you really need to read and understand this in Data Structures book
Chapter 2 - It's very important
Abstract data
types( ADT's) include… strings, list, queue,
stack to name a few
Example:
string:
- a
sequential collection of characters.
operations of a string:
- altering
- clearing
- copying
- comparing
- concatenating
- character access
- deleting characters
- input
- output
- sorting
- sub-string
- string length
Various ways
of representing strings
|
a) |
W |
e |
l |
c |
o |
m |
e |
`\0' |
character array with terminating
character
|
b) |
H |
e |
l |
l |
o |
length = 5 |
character array with variable length determining end of
string
|
c) |
c |
o |
m |
p |
u |
t |
e |
r | |
|
* |
* |
chained arrays of set size using pointers to chain
together
Let's go with
example b) since it is most like the strings used in C++ standard string
class
String Class:
const int String::MAXLEN = 80;
// above all else in class.C but here only for
use in this class
/*****************************************************************/
class String
{
const int MAXLEN;
char data[MAXLEN];
int len;
// length of
string
public:
String();
String(const char *);
//
initialize from C style string
int size(void) const;
//
return size - const and
int length(void)const;
// won't
effect class members
bool operator < (const String &)const;
// overloads < operator
// friend function here overloads the <<
operator
friend ostream & operator << (ostream
&ostr, const String s);
};
/****************************************************************/
String::String()
{
len = 0;
}
/****************************************************************/
String::String(const char *c)
{
len = 0;
while(*c != `\0' && len < MAXLEN) //
copies char until end of array
{
data[len] =
*c;
len++;
c++;
}
}
/*****************************************************************/
int
String::size(void) const
{
return len;
}
/*****************************************************************/
int
String::length(void) const
{
return len;
}
String Class Continued:
/****************************************************************/
bool String::operator < (const String &s)const
{
//
Left side is the current instance
int i=0;
while(data[i] == data[s] && i<len
&& i<s.len)
{
if(i==len
&& i==s.len)
return
false;
… to be
continued
}
}
/****************************************************************/
ostream & operator << (ostream &ostr, const String
&s)
{
for (int i=0; i<s.len; i++) // can access
s.len because friend func.
ostr <<
s.data[i];
return ostr;
}
when you call the overloaded << operator in the main(
) you will call it by simply using it.
Example:
cout << `*'
<< s << `*';
will print out:
*Mine!*