COMP2012H Lab (Pointers and Dynamic Objects)

COMP 2012H
Honors OOP and Data Structures

Lab 6: Pointers, Dynamic Objects, Linked List and File I/O

In this lab, we first review the pointers, dynamic objects. Then we introduce the linked list and briefly go through the file i/o.

Review of Pointers

In previous labs, variables are memory cells that can be accessed by an identifier (variable name). In fact, variables are stored in computer memory with a unique address.

We can imagine computer memory as a street in a city. On the street, all houses are consecutively numbered with an unique identifier such as 1st of Nathan Road, we will be able to find that place directly. The operating system organizes the memory with unique and consecutive numbers, so if we talk about location 1104 in the memory, we can access it at once.

Address (dereference) operator (`&`).

At the moment in which we declare a variable it must be stored in a concrete location in this succession of cells (the memory). We generally do not decide where the variable is to be placed - fortunately that is something automatically done by the compiler and the operating system at runtime, but once the operating system has assigned an address there are some cases in which we may be interested in knowing where the variable is stored.

This can be done by preceding the variable identifier by an ampersand sign (&), which literally means "address of". For example:

ted = &andy;

would assign to variable ted the address of variable andy, since when preceding the name of the variable andy with the ampersand (&) character we are no longer talking about the content of the variable, but about its address in memory.

We are going to suppose that andy has been placed in the memory address 1776 and that we write the following:

andy = 25; fred = andy; ted = &andy;

the result is shown in the following diagram:

Reference operator (`*`)

Using a pointer we can directly access the value stored in the variable pointed by it just by preceding the pointer identifier with the reference operator asterisk (*), that can be literally translated to "value pointed by". Therefore, following with the values of the previous example, if we write:

beth = *ted;

(that we could read as: "beth equal to value pointed by ted") beth would take the value 25, since ted is 1776, and the value pointed by 1776 is 25.

You must clearly differentiate that ted stores 1776, but *ted refers to the value stored in the address 1776, that is 25. Notice the difference of including or not including the reference asterisk.

beth = ted; // beth equal to ted ( 1776 ) beth = *ted; // beth equal to value pointed by ted ( 25 )

Operator of address or dereference (&)
It is used as a variable prefix and can be translated as "address of", thus: &variable1 can be read as "address of variable1"

Operator of reference (*)
It indicates that what has to be evaluated is the content pointed by the expression considered as an address. It can be translated by "value pointed by".
* mypointer can be read as "value pointed by mypointer".

At this point, and following with the same examples initiated above where:
　

andy = 25; ted = &andy; 　

what is the value of the following expressions?

andy == 25

&andy == 1776

ted == 1776

*ted == 25

What is the result of the following examples?

Example 1

#include <iostream.h> int main () { int value1 = 5, value2 = 15; int * mypointer; mypointer = &value1; *mypointer = 10; mypointer = &value2; *mypointer = 20; cout << "value1==" << value1 << "/ value2==" << value2; return 0; } 　

Example 2

include <iostream.h> int main () { int value1 = 5, value2 = 15; int *p1, *p2; p1 = &value1; // p1 = address of value1 p2 = &value2; // p2 = address of value2 *p1 = 10; // value pointed by p1 = 10 *p2 = *p1; // value pointed by p2 = value pointed by p1 p1 = p2; // p1 = p2 (value of pointer copied) *p1 = 20; // value pointed by p1 = 20 cout << "value1==" << value1 << "/ value2==" << value2; return 0; } 　

Pointers to pointers

C++ allows the use of pointers that point to pointers, that these, in its turn, point to data. In order to do that we only need to add an asterisk (*) for each level of reference:

char a; char * b; char ** c; a = 'z'; b = &a; c = &b; 　

this, supposing the randomly chosen memory locations of 7230, 8092 and 10502, could be described thus:

(inside the cells there is the content of the variable; under the cells its location)

The new thing in this example is variable c, which we can talk about in three different ways, each one of them would correspond to a different value:

c is a variable of type (char **) with a value of 8092 *c is a variable of type (char*) with a value of 7230 **c is a variable of type (char) with a value of'z'

　
Dynamic objects
　

Until now, all the declarations of variables, arrays and other objects in our programs are having a fixed size before the execution of the program. What if we need a variable amount of memory that can only be determined during the program execution at runtime? For example, in case that we need an user input to determine the amount of space? In C++, the solution is dynamic memory.

Operators new and new[ ]
In order to request dynamic memory, the operator new exists. new is followed by a data type and optionally the number of elements required within brackets []. It returns a pointer to the beginning of the new block of assigned memory. Its syntax is:

pointer = new type //assign memory to contain one single element of type type

or

pointer = new type [elements] //assign a block (an array) of elements of type type.

For example:

int * bobby; bobby = new int [5]; 　

in this case, the operating system has assigned space for 5 elements of type int and it has returned a pointer to its beginning that has been assigned to bobby. Therefore, now, bobby points to a valid block of memory with space of 5 int elements.

You could ask what is the difference between declaring a normal array and assigning memory to a pointer as we have just done. The most important one is that the size of an array must be a constant value, which limits its size to what we decide at the moment of designing the program before its execution, whereas the dynamic memory allocation allows assigning memory during the execution of the program using any variable, constant or combination of both as size.

Operator delete.
Since dynamic memory is usually limited within a program at run time, once it is no longer needed it should be freed for future requests of dynamic memory. The operator delete exists for this purpose, whose syntax is:
　

delete pointer; //delete memory alloccated for a single element

or

delete [] pointer; //delete memory allocated for multiple elements (arrays)

For example:

#include <iostream.h> #include <stdlib.h> int main () { char input [100]; int i,n; long * l; cout << "How many numbers do you want to type in? "; cin.getline (input,100); i=atoi (input); l= new long[i]; if (l == NULL) exit (1); for (n=0; n<i; n++) { cout << "Enter number: "; cin.getline (input,100); l[n]=atol (input); } cout << "You have entered: "; for (n=0; n<i; n++) cout << l[n] << ", "; delete[] l; return 0; } 　

The above simple example does not have a predetermined maximum number of integers to be introduced. The program dyanamically provides as much space as necessary to store all the numbers that the user wishes to introduce.
　

Linked List

Review: Comparing Linked List with Array:

Array is finite and fixed, and needs to be resized if it is full.
Linked List can be dynamically allocated.
Array insertion/deletion is expensive (room creating).
Insertion/deletion is easier for Linked List.

Fundamental Data Structures:

Homgeneous collection of values (all same type)
Store values anywhere in memory
Associate link with each value
Use link for immediate access to the next value

Overview of Linked Lists:

Not directly built in C language
How to associate pieces of information: User-defined type using struct; include struct field for coeffcient and exponent
How to specify links: include struct field for POINTER to next linked list element
How to reserve memory to be used: Allocate memory DYNAMICALLY (as you need it); malloc()
How to use links to access information: use -> and . operators

No Free Lunch:
Linked List has following drawbacks:

Random access is not allowed;
Extra memory for a pointer is required for each element of the list;
Arrays have better cache locality that can make a pretty big difference in performance.

File I/O

The file I/O type: ifstream (for input), ofstream (for output), fstream (for input output).
Before you begin

If you want to use the files, you need to claim the file variable
File variable is a pointer.

Some classical and useful examples:

fstream:

fstream file;
file.open(“Reader.txt”,ios::in);
file.open(“Reader.txt”,ios::in | :ios::binary);

The following example is useful:

#include<iostream>

#include<fstream>

using namespace std;

int main(){

    char filename[]="Reader.txt";

    fstream fp;

    fp.open(filename, ios::out);//Open the files

    if(!fp){//If the openning fails, fp is 0; otherwise fp is 1;

        cout<<"Fail to open file: "<<filename<<endl;

}

    cout<<"File Descriptor: "<<fp<<endl;

    fp<<"Hello HappyMan!!"<<endl;//write strings

    fp.close();//close the file

}

ostream:

#include <fstream.h>
int main(){
     ofstream file;
    file.open("file.txt");
    file<<"Hello file"<<75;
    file.close();
}

Facilitate readings:

use getline(buffer, max) to read the whole line. Note that \n will not be read in getline!!

const MAX=80;
char buffer[MAX];
ifstream infile("strdata.txt");
while(infile)
{
infile.getline(buffer,MAX);
cout<<buffer<<endl;
}

To prevent error:

fail(): return a boolean true if the file has not been opened;
good(): true if the file is available for program use;
bad(): true if a read has been attempted past the end;
eof(): return true if a read has been attempted past the end of file;

Example:
char ch;
ifstream file("kool.cpp",ios::in|ios:out);
if(file.good()) cout<<"The file has been opened without problems";
else cout<<"An Error has happened on opening";
while(!file.eof()){
file>>ch;
cout<<ch;
}

Lab Task: Linked List & File I/O

Reverse a singly linked list. You should implement it both iteratively AND recursively.

1) Given an "input.txt" with the test cases, read in the information;
2) Reverse the input linked list at each line;
3) Output a file "output.txt" with the results.

Test case:

Input:

null;
1->null;
1->2->3->4->5->null;
a->b->c->d->e->f->null;

Output:

null
1->null
5->4->3->2->1->null
f->e->d->c->b->a->null

Address (dereference) operator (&).

Reference operator (*)

Pointers to pointers

Review: Comparing Linked List with Array:

Fundamental Data Structures:

Address (dereference) operator (`&`).

Reference operator (`*`)