Transcript Overview - Chap 1

Data Structures: CSCI 362 - Chapter 1
Overview of Lecture






Introduction to Data Structure
Storage Containers
Abstract Data Types (ADT)
Classes
Application Programmer Interface (API)
Strings
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
What is a Data Structure?
 A data structure is a systematic way of organizing and accessing
data
 Programmer-defined data structures bundle data with operations
that manipulate the data
 The structures, called containers have operations to access, insert,
and remove items from the collection.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Storage Containers

Containers such as vectors, lists or maps are storage structures that
provide ways to access data and insert/delete items
 Vectors
 Lists
 Maps
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Storage Containers: Vectors

A vector has all of the nice indexing features of an array along with
the ability to dynamically grow to meet demand – aka “super array”

Allows for direct access to its elements through the index

We have the option to growing or shrinking vectors
vector v (with 5 elements)
7
4
9
3
1
v.resize (8); (grow to 8 elements)
7
4
9
3
1
0
0
0
v.resize (3); (shrink to 3 elements)
7
4
9
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Storage Containers: Vectors

Limitations to Vectors:


Not an efficient storage structure for general insertion and deletion of items at an arbitrary position in the list
Suppose an application wants to store elements in order and a vector is used:
 The insert operation requires shifting a block of elements to the right to make room for a
new item
 The deletion operation requires shifting a bloc of elements to the right to make room for
the new item
Vector
15 20 30 35 40
Insert 25 at
Position 2 15 20


25
Vector 15 20 30 35 40
Erase 20 at
15
30 35 40
30 35 40
Position 1
20 Shift left
Shift right
Problem: High overhead of maintaining Vectors when collection of elements are large and the
application calls for frequent insertion and deletion of items
Solution: List containers
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Storage Containers: Lists

Each element has a reference that identifies the next item in the list.

Adding a new item involves breaking a link in the chain and creating two
new links to connect the item
//
front
Reference identifying next item on list
Dr. Nazli Mollah
newItem
The insertion occurs
locally in the list and does
not require the moving of
the other elements to
make room for the new
element
rear
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Storage Containers: Maps
Root


Arrays, vectors, and lists store
elements by position: 0,1,2 etc.,
thus to access an element
efficiently, we must know its
position in the list – otherwise
item-by-item search of list – not
very effective for large list with say
100,000 elements – time
consuming iterations of a loop to
locate the position.
Solution: Maps – which use tree
structure to store data
 Data is stored by value and not
position
 e.g. an airline reservation/ mail
has a tracking number consisting
of alphanumeric strings
Dr. Nazli Mollah
G9B7
B40A
NT2P
FA27
H14K
W29Z
D29Z
TV93


Map: structure where the index is
represented by a value not position
Maps use tree structures that
maintain system files and directories
and can parse expressions – very
useful where trees hold a large
number of items
 e.g.D29Z requires at most 3 iterations
along a path from the root
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Abstract Data Types (ADT)
Abstract view of Data Structures
 To understand the design of a data structure, we use an abstract
model that specifies the
 type of data stored
 operations that support the data.
 Abstract Data Types (ADT’s) are a model used to understand the
design of a data structure.
 The main feature if an ADT is a simple and clear description
of the operations in the data structure
 “abstract” implies that the data structure is given an
implementation-independent view
 viewing a data structure as an ADT allows a programmer to
focus on an idealized model of the data and its operations.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
ADT Operation Description

An ADT provides simple and clear description of:

the input to an operation.

the action of the operation.

its return type.

Operation Name: Action statement that specifies the

input arguments

type of operation on the elements of the date structure

output value

Preconditions: Part of the description of an operation. A listing of the
conditions that must apply in order for the operation to execute
successfully.

Postconditions: Indicate changes to the object's data caused by the
operation. Necessary because operations often alter the value of data.

If the operation does not have a precondition or a postcondition, the ADT
operation description disregards the condition
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
An ADT as a Class

An ADT provides an abstract model of a data structure:
 The view is like an architect’s first sketch of a house – layout & # of rooms
 But becomes reality only when a(n):
 architect creates a structural blueprint
 contractor builds the walls and interior

For an ADT, we need to create a:
 physical representation of the data
 computer model for the operations

The object-oriented C++ language is ideal for this:
 The class construct provides a physical realization of an ADT
 The class declaration is the blueprint
 The writing of the implementation code actually builds the class
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
The time24 ADT

Consider a data structure that uses integer values for hours and minutes to
represent the time of day in a 24-hour clock
 Use time24 to identify the structure

The ADT designer has the responsibility to specify the:
 number of operations
 action of each operation
Like the architect who creates plans for a house – focus of ADT designer is on
functionality and ease of use in a program
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
The time24 ADT: Operations

e.g., the ADT could provide the operation called duration to measure the
length of time between current value and some later time in the day
 The value is a time24 value that becomes the output parameter:
 Duration(t): Time t is an input argument. Measure the length of time from the
current time to time t, and return the result as a time24 value
 Precondition: Time t must not be earlier than the current time
 readTime(): Input from the keyboard the hours and minutes for a time24 object,
using the format hh:mm
 Postcondition: Set the hour and minute values of the time to hh and mm
respectively. If either of the values is out of its designated range, the operation
makes the appropriate adjustment e.g. 9:75 is stored as 10:15
 writeTime(): Display on the screen the current time in the form hh:mm
 getHour(): Return the hour value for the current time
 getMinute(): Return the minute value for the current time

See Exercise on page 13: “d_time24.h”
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
The C++ Class

In object-oriented program design, building blocks of an application are values
of primitive type and application
 Objects consist of data and operations on the data – specific instances of class type
 Class specifies the structure of an object - referred to as an object type
Declaration of a class includes:
Class Header consisting of
reserved word class followed by the name of the class
CLASS className
Declaration
Function Prototype:
Specifies the parameters in an
argument list within { } and
indicates the return type of the
output
Function Prototype:
return Type functionName (<argument list>);
class className
{
public:
// <public member function prototypes>
. . . . . . . .
private:
// <private data members>
. . . . . . . .
// <private member function prototypes>
. . . . . . . .
Declaration of a
class includes:
Class Body –
beginning with ({
), ending with (;)
Format of Body includes:
Private and Public sections
};
Dr. Nazli Mollah
Data values in the Class lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Classes: Private/Public Sections

The public and private sections in a class declaration allow program
statements outside the class different access to the class members.
accessible to the
implementation of
the member functions
Dr. Nazli Mollah
private:
data members
member functions
public:
data members
member functions
accessible by
any program statement
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Classes: Public Section

Public members of a class are the interface of the object to the program.
 Any statement in a program block that declares an object can access a public
member of the object
accessible to the
implementation of
the member functions
Dr. Nazli Mollah
public:
data members
member functions
accessible by
any program statement
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Classes: Private Section

The private section typically contains the data values of the object and utility
functions that support class implementation.
 Only member functions of the class may access elements in the private section.
accessible to the
implementation of
the member functions
private:
data members
member functions
In addition, a class encapsulates information by bundling the data
items and operations within an object
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Class: Constructor

Constructor: a special member function of a class whose task it is to
initialize the object

The constructor always has the name of the class
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Application Programming Interface (API)

Object-oriented programmers have developed a documentation format that
collapses the key information from the ADT and the class declaration – this
documentation is called application programming interface (API)

API allows other programmers to use the public interface of the class without
having to view the technical details of the class declaration or implementation

The format includes:
 Function prototype for the constructor – provides programmer with the function
name, arguments, and return type
 Other public member functions of the data structure

The API includes:
 An action statement that describes what the operation does
 Preconditions that must apply before the operation can execute successfully, along
with an exception that is thrown when the condition fails
 Postconditions indicate any changes to the current state of the object
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
API: Constructor
CLASS className
Constructors
“<file>.h”
className(<arguments>);
Initializes the attributes of the object
Postconditions: the data members of the object have initial values
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
API: Operations
CLASS className
Operations
“<file>.h”
returnType functionName(argument list);
Description of the action of the function and any return value
Preconditions: Necessary state of the object before executing
the operation. Any exceptions that are thrown when an error
is
detected.
Postconditions: State of the data items in the object after
executing the operation
….
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Strings
String: a sequence of characters that programs use to identify names,
words, and sequences
C++ provides two approaches to string handling.
Older Method:
C-style string - a character array that designates the end of the
string by using the NULL character.
Used by the C programming language and older C++ programs
Modern Method:
String class – defines a string as an object and provides access
to individuals characters and collections of characters within the
string.
The standard C++ library provides the string class, which is
accessed using the directive:
#include <string>
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
Strings: Functions and Operations

The string class provides:
 string handling functions that enable a programmer to search for
characters within a string
 extraction of consecutive sequence of characters called substrings
 modification of a string by adding or removing characters
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
String: Functions and Operations

Searching for characters with a string:
 This function performs simple pattern matching that looks for a single character c in
the string
 The index of the match is the return value. If no match occurs, the function returns -1
int find_first_of(char c, int start = 0):
Look for the first occurrence of c in the string
beginning at index start. Return the index of the
match if it occurs; otherwise return -1.
By default, start is 0 and the function searches
the entire string.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
String Functions and Operations
int find_last_of(char c):
Look for the last occurrence of c in the string.
Return the index of the match if it occurs;
otherwise return -1.
Since the search seeks a match in the tail of the
string, no starting index is provided.


Useful in pattern matching especially in large strings
See Example 1-4
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
String Functions and Operations

Extraction of consecutive sequence
 The function substr() extracts from the string a consecutive sequence of characters
called substrings
 The operation assumes a starting index and a count for the number of characters
 Useful in name searches on directories/ airline reservations etc
 See Example 1-5
string substr(int start = 0, int count = -1):
Copy count characters from the string beginning at index start and
return the characters as a substring. If the tail of the string has fewer
than count characters or count is -1, the copy stops at end-of-string.
By default, start is 0 and the function copies characters from the
beginning of the string. Also by default, the function copies the tail of
the string.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL
Data Structures: CSCI 362 - Chapter 1
String Functions and Operations

The function find() locates a specific pattern in the string
int find(const string& s, int start = 0):
The search takes string s and index start and
looks for a match of s as a substring. Return the
index of the match if it occurs; otherwise return 1.
By default, start is 0 and the function searches
the entire string.
Dr. Nazli Mollah
lecture notes adapted from
Data Structures with C++ using STL