Transcript WK08b

19-Jul-2006
Today’s Objectives
 Announcements
•
Homework #5 is due next Monday, July 24. Since this date is so close to
the end of the semester, no late assignments will be accepted and
email will NOT be accepted!
 Quiz #4
 File Processing (Ch. 17)
•
•
•
•
•
Files and streams
Reading from files
Writing to files
Adding structure to files
Using seekg, seekp, tellg, and tellp
 Data Structures (Ch. 21)
•
•
Self-referential structures and classes
Linked lists
1
Quiz #4
Closed book
20 minutes
Please clear your desks and
log off from the computer
2
File Processing
Chapter 17
3
File Processing (Deitel, 844)
Files and Streams
 File
•
•
Used to store data
Storing data in a file makes the data “persistent”
 File = a sequence of bytes
•
•
•
Stream = a sequence of bytes
When a file is opened, a stream object is associated
with the file
The stream object connects the file with your program
4
File Processing (Deitel, 845)
File Stream Classes and Header
 <fstream>
 ifstream
•
•
Used for input from a file
From the template class basic_ifstream<>
 ofstream
•
•
Used for output from a file
From the template class basic_ofstream<>
 fstream
•
•
Used for both output and input with a file
From the template class basic_fstream<>
5
File Processing (Deitel, 847)
Reading from a File
char *filename = "movies.dat";
ifstream inFile( filename ); //open for reading
Filename as a C-style string
Name of the stream object
Name of the class
that is used for
input from a file
6
File Processing (Deitel, 847)
Reading from a File
char *filename = "movies.dat";
ifstream inFile( filename ); //open for reading
if( !inFile ) {
cerr << "Unable to open " << filename << endl;
}
It’s a good idea to check whether the file was opened
successfully!
• Use operator! to check the state of the stream
object
• Checks the failbit
7
File Processing (Deitel, 847)
Reading from a File
char *filename = "movies.dat";
ifstream inFile( filename ); //open for reading
if( !inFile ) {
cerr << "Unable to open " << filename << endl;
}
else {
while( !inFile.eof() ) {
Movie tempMovie;
inFile >> tempMovie; //reading from the file
store.addRentalItem(tempMovie);
}
A stream’s eof() function returns true if the
end of the stream has been reached.
8
File Processing (Deitel, 847)
Reading from a File
char *filename = "movies.dat";
ifstream inFile( filename ); //open for reading
if( !inFile ) {
cerr << "Unable to open " << filename << endl;
}
else {
while( !inFile.eof() ) {
Movie tempMovie;
inFile >> tempMovie; //reading from the file
store.addRentalItem(tempMovie);
}
inFile.close();
}
What would be likely to happen if we did not
explicitly close the file? Hint: “infile” is an object.
9
File Processing (Deitel, 847)
Writing to a File
char *filename = "customers.dat";
ofstream outFile( filename ); //open for writing
Filename as a C-style string
Name of the stream object
Name of the class
that is used for
output to a file
10
File Processing (Deitel, 847)
Writing to a File
char *filename = "customers.dat";
ofstream outFile( filename ); //open for writing
if( !outFile ) {
cerr << "Unable to open " << filename << endl;
}
Check whether the file was opened successfully!
11
File Processing (Deitel, 847)
Writing to a File
char *filename = "customers.dat";
ofstream outFile( filename ); //open for writing
if( !outFile ) {
cerr << "Unable to open " << filename << endl;
}
else {
for( int i=0; i<sz; ++i ){
outFile << myData[i].getID() << '\n';
outFile << myData[i].getFirstName() << '\n';
outFile << myData[i].getLastName();
if( i < sz - 1 ) outFile << '\n';
}
Write the data to the file.
12
File Processing (Deitel, 847)
Writing to a File
char *filename = "customers.dat";
ofstream outFile( filename ); //open for writing
if( !outFile ) {
cerr << "Unable to open " << filename << endl;
}
else {
for( int i=0; i<sz; ++i ){
outFile << myData[i].getID() << '\n';
outFile << myData[i].getFirstName() << '\n';
outFile << myData[i].getLastName();
if( i < sz - 1 ) outFile << '\n';
}
outFile.close();
}
13
File Processing (Deitel, 848; Lippman, 1097)
Opening Files
 A stream object can be created without
opening a file
ofstream outFile;
 Then it can be opened later
outFile.open("customers.dat");
 If a file is opened for output and it does
not already exist, a new file will be created
automatically
14
File Processing (Deitel, 847; Lippman, 1097)
Appending to a File
 By default, when an ofstream object is opened
for output, all data already stored in the file is
discarded
 To keep the data that is in the file and add more
data to the end, open the file in append mode
ofstream outFile( "customers.dat", ios::app );
Specifies the file open mode,
see Fig. 17.5, page 847.
ios::app specifies append mode
ios::out specifies output mode, discard the content
15
File Processing (Deitel, 847; Lippman, 1102)
Using Objects of fstream
 fstream is used for both input from a file and
output to a file
 Use the mode argument to specify whether
input, output, or both
fstream io("customers.dat", ios::in|ios::app );
Specify more than one mode by
using the bitwise OR operator
16
File Processing (Deitel, 844; Folk, 119)
Unstructured Streams
 If we write data to a file as an unstructured byte stream,
we may not be able to retrieve it easily
 Example
•
If we have an array of Customer objects and we write them to a
file like this:
for( int i=0; i<sz; ++i ){
outFile << myData[i].getID();
outFile << myData[i].getFirstName();
outFile << myData[i].getLastName();
}
•
Then the bytes will be written as an unstructured byte stream,
and we will not be able to separate the data when the file is read
1001AlanTuring1002CharlesBabbage
17
File Processing (Deitel, 843; Folk, 120–125)
Fields and Records
 When working with files, the data is said to be
composed of fundamental units called “fields”
and “records”
 Field = the smallest unit of meaningful data
•
Examples: “firstName” and “lastName”
 Record = the set of fields that belong together
•
Example: each Customer object is a record that
contains several fields
18
File Processing (Deitel, 843; Folk, 120–125)
Adding Structure to Files
 If the data is structured inside the file (i.e., the fields and
records are separated), then the data can be retrieved
or changed easily
 There are many ways to add structure to a file
 Common methods to keep fields separated
•
Use fields that have a set length
1001
1002
•
Alan
Turing
CharlesBabbage
Place a delimiter at the end of each field
1001
Alan
Turing
1002
Charles
Babbage
19
File Processing (Deitel, 843; Folk, 120–126)
Structured Records
 Record = the set of fields that belong together
 Usually, a record is equivalent to the data for
one object
 Common methods to keep records separated
•
Use records that have a set length
1001
•
Alan
Turing 1002
CharlesBabbage
Make records a set number of fields
1001
Alan
Turing
1002
Charles
Babbage
20
File Processing (Deitel, 843; Folk, 120–126)
Retrieving Data
 When a file is structured, we can retrieve its
data easily
 Sequentially
•
Read data from the beginning to the end, inserting it
into variables or objects
 Randomly
•
•
Go directly to a specific record and read it
seekg
21
File Processing (Deitel, 843; Folk, 120–126)
Retrieving Data Sequentially
1001
Turing
Alan
1002
Babbage
Charles
Example file structure:
•
•
Fields are separated by ‘\n’
Each record has three lines
string ID, lName, fName;
ifstream inFile( "customers.dat" );
if( !inFile ) cerr << "Unable to open file." << endl;
else {
while( !inFile.eof() ) {
inFile >> ID;
inFile >> lName;
inFile >> fName;
Customer tempCustomer( ID, lName, fName );
store.addCustomer(tempCustomer);
}
inFile.close();
}
22
File Processing (Deitel, 843; Folk, 120–126)
Retrieving Data Sequentially
1001
Turing
Alan
1002
Babbage
Charles
Example file structure:
•
•
Fields are separated by ‘\n’
Each record has three lines
string ID, lName, fName;
ifstream inFile( "customers.dat" );
if( !inFile ) cerr << "Unable to open file." << endl;
else {
while( !inFile.eof() ) {
inFile >> ID;
inFile >> lName;
inFile >> fName;
Customer tempCustomer( ID, lName, fName );
store.addCustomer(tempCustomer);
}
inFile.close();
}
23
File Processing (Deitel, 851; Lippman, 1102)
Using seekg
seekg()
•
•
•
•
Member function of the istream class
First argument is the number of the byte in the file that
the next input will get
Second argument is optional, and it is the direction for
positioning, default is the beginning of the stream –
ios::beg, ios::cur, ios::end
Example
string temp;
ifstream inFile("customers.dat");
inFile.seekg(10);
inFile >> temp; //string beginning at byte 10
24
File Processing (Deitel, 851–826)
Retrieving Data Randomly
1001 Turing
Alan
1002 Babbage Charles
1003 Lovelace Ada
Example file structure:
•
•
Fields separated by whitespace
Each record has 23 bytes
const int RECORDSIZE = 23; long recordNumber = 0;
string ID, lName, fName;
ifstream inFile( "customers.dat" );
if( !inFile ) cerr << "Unable to open file." << endl;
else{
cout << "Enter the number of a record: ";
cin >> recordNumber;
while( recordNumber > -1 && recordNumber < 2 ){
inFile.seekg( recordNumber * RECORDSIZE, ios::beg );
inFile >> ID >> lName >> fName;
Customer tempCustomer( ID, lName, fName );
cout << "The customer is: " << tempCustomer << endl;
cout << "Enter the number of a record: ";
cin >> recordNumber;
}
inFile.close();
}
25
File Processing (Deitel, 851; Lippman, 1102)
Using seekp
seekp()
•
•
•
•
Member function of the ostream class
First argument is the number of the byte in the file
where the next output will start
Second argument is optional, and it is the direction for
positioning, default is the beginning of the stream –
ios::beg, ios::cur, ios::end
Example
const int RECORDSIZE = 23;
ofstream outFile("customers.dat");
outFile.seekp( n * RECORDSIZE );
outFile.write("1005 ",5);//changes the ID
26
File Processing (Deitel, 851; Lippman, 1102)
Using tellg, tellp
tellg()
•
•
•
Member function of the istream class
Returns the current byte in the input file
Example
long pos = inFile.tellg();
tellp()
•
•
Member function of the ostream class
Returns the current byte in the output file
 Used to mark a position in the file so that the program
can return to it later
inFile.seekg( pos );
27
Data Structures
Chapter 21
28
Data Structures (Goodrich, 108)
Data Structure
“ A systematic way of organizing and
accessing data” in a computer’s
memory
 Simple data structures – an array, a vector, a struct, a
class
 More complex data structures often use self-referential
structures or classes
29
Data Structures (Deitel, 1000)
Self-Referential Struct
 Contains a data field that holds a data value
 Contains one or more data fields that hold a
pointer to another struct object of the same
type
struct Node {
char element;
Node *next;
};
30
Data Structures (Deitel, 1000)
Struct with a Constructor
 In C++, a struct can have a constructor
struct Node {
char element;
Node *next;
Node(char e=' ',Node *p=NULL):element(e),next(p){}
};
31
Data Structures (Deitel, 1000)
Self-Referential Class
 Contains a data field that holds a data value
 Contains one or more data fields that hold a
pointer to another object of the same type
class CNode {
public:
CNode(char e=' ',CNode *p=NULL):element(e),next(p){}
void setElement( char c ){ element = c; }
char getElement(){ return element; }
void setNext( CNode *p ){ next = p; }
CNode *getNext(){ return next; }
private:
char element;
CNode *next;
};
32
Data Structures (Deitel, 1000)
Building a Data Structure with
Self-Referential Objects
Self-referential objects can be linked together to
hold a collection of related data
•
•
Similar to an array
Linked list – a type of data structure built from selfreferential objects
Collection of objects
Linked
List
Each object has a pointer that points to the next object
33
Data Structures (Deitel, 1000)
Similarities and Differences
Between Arrays and Linked Lists
Similarities
•
•
Both store data in memory
Both store data in a sequence
Differences
•
•
Array is one block of contiguous
memory
List is a collection of scattered
memory cells
Array
Linked
List
34
Data Structures (Deitel, 1000)
Linked List Example
 We normally use a pointer to keep track of the location
of the first node, called the “head node”
 Each subsequent node in the list is accessed by the
pointer member inside the previous node
 We often use another pointer to keep track of the last
node, called the “tail”
 The pointer in the last node is set to NULL
pHead
struct Node {
char element;
Node *next;
};
pTail
struct Node {
char element;
Node *next;
};
struct Node {
char element;
Node *next;
};
NULL
35
Data Structures (Deitel, 1000)
Arrays vs. Linked Lists
Arrays
Advantages
•
•
Simple
Fast performance
Drawbacks
•
•
Size is fixed – we use
up the space even if
we don’t need it
Size must be
determined in advance
Linked Lists
Advantages
•
•
No fixed size – use only
space we need
We can add more nodes
at any time
Drawbacks
•
•
Additional time for
allocating memory during
program execution
More complicated code
36
Data Structures (Deitel, 1000)
Using a Linked List
 If we create a class for our linked list, then we
can encapsulate all of the list’s data and the
operations that we can do with the list
 Operations (member functions)
•
•
•
•
size
push_front
pop_front
printList
 Data members
•
•
size
A pointer to the head node
37
Data Structures (Deitel, 1000)
Starting a List Class
class List{
private:
struct Node {
char element;
Node *next;
Node(char e=' ',Node *p=NULL):element(e),next(p){}
};
public:
List();
int size();
void push_front( char e );
void pop_front();
void printList();
private:
int sz;
Node *pHead;
38
};
Data Structures (Deitel, 1000)
Defining Some Member Functions
List::List(){
sz = 0;
pHead = NULL;
}
int List::size(){
return sz;
}
39
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing push_front
pHead
f
next
g
next
h
next
NULL
40
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing push_front
pHead
f
e
1.
next
next
g
next
h
next
NULL
pHead
//Create a new node
//Put the data into its data element
//Put the address in pHead into its “next” pointer
41
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing push_front
pHead
f
e
1.
next
g
next
h
next
NULL
g
next
h
next
NULL
pHead
next
pHead
2.
e
next
f
next
//Make pHead point to the new node
42
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing push_front
pHead
f
e
1.
next
g
next
h
next
NULL
pHead
next
pHead
2.
e
next
f
next
g
next
h
next
NULL
f
next
g
next
h
next
NULL
pHead
3.
e
next
43
Data Structures (Deitel, 1000, Goodrich, 177)
Coding push_front
//Create a new node
//Put the data into its data element
//Put the address in pHead into its “next” pointer
Node *v = new Node( 'e', pHead );
//Make pHead point to the new node
pHead = v;
//Increase the size
sz++;
44
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing printList
 We use a temporary node to print the elements
stored in a linked list
pHead
f
next
g
next
h
next
NULL
next
current
//Start at the head and print its element
45
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing printList
 We use a temporary node to print the elements
stored in a linked list
pHead
f
next
g
next
h
next
NULL
next
current
//Start at the head and print its element
//Then get the next node and print its element
46
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing printList
 We use a temporary node to print the elements
stored in a linked list
pHead
f
next
g
next
h
next
NULL
next
current
//Start at the head and print its element
//Then get the next node and print its element
47
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing printList
 We use a temporary node to print the elements
stored in a linked list
pHead
f
next
g
next
h
next
NULL
next
current
//Start at the head and print its element
//Then get the next node and print its element
//Stop when it’s NULL
48
Data Structures (Deitel, 1000, Goodrich, 177)
Coding printList
Start at the head
void List::printList(){
Node *current = pHead;
Stop if it’s NULL
while( current ){
cout << current->element << " ";
Print the element
current = current->next;
}
}
Get the next node
49
Data Structures (Deitel, 1000, Goodrich, 177)
Visualizing pop_front
//Save the address of the current head as “old head”
//Make the head pointer point to node #2
//Delete the old head
oldHead = pHead
1.
e
next
next
g
next
h
next
NULL
g
next
h
next
NULL
pHead
oldHead
2.
f
e
next
f
next
50
Data Structures (Deitel, 1000, Goodrich, 177)
Coding pop_front
//Save the address of the current head as “old head”
//Make the head pointer point to node #2
//Delete the old head
//Reduce the size
Node *oldHead = pHead;
pHead = pHead->next;
delete oldHead;
sz--;
//Hold it temporarily
//Switch the pointer
//Recover the memory
//Reduce the size
51
Data Structures (Deitel, 1000, Goodrich, 177)
The Destructor
 Every node in the list was created with new, so
every node must be deleted
List::~List(){
while( sz > 0 ){
pop_front();
}
}
52
References
C++ Language Reference (MS Visual C++ Online Help), Redmond,
Washington: Microsoft Corporation, 2001.
Deitel, H. M., and P. J. Deitel, C++ How to Program, Fifth Edition.
Upper Saddle River, NJ: Prentice Hall, 2005.
Goodrich, M. T., R. Tamassia, and D. Mount, Data Structures and
Algorithms in C++. Hoboken, NJ: John Wiley & Sons, Inc., 2004.
Josuttis, Nicolai M., The C++ Standard Library, A Tutorial and
Reference. Boston: Addison-Wesley, 1999.
53