PowerPoint Presentation
CS2313 Computer Programming
LT11 – Pointer/IO/Recursion
1
Outlines
2
Revision on Pointer
Pointer Arithmetic
I/O
Stream
Open File
File I/O
Error Handling
Recursion
Pointer
3
int count= 5;
short status = 2;
char letter = ‘A’;
int * pCount = &count;
char * pLetter = &letter;
pCount = &count;
&: address operator
&count: the address of count
*: dereference operator
*pCount: value pointed to by pCount
Declare a Pointer
Pointer, like normal variable has a type, its type is determined by the type of variable it points to.
dataType* pVarName;
Each variable being declared as a pointer must be preceded by an asterisk (*). The following statement declares a pointer variable named pCount that can point to an int varaible.
int* pCount; pCount=&count;
4
Dereferencing
Get access to the value of the variable pointed to by the pointer
*pointer
For example, you can increase count using
count++; // direct reference, increment the value in count by 1
or
(*pCount)++; // indirect reference, the value in the memory pointed to by pCount is incremented by 1
5
Arrays and Pointers
An array variable without a bracket and a subscript represents the starting address of the array.
An array variable is essentially a pointer.
int list[6] = {11, 13, 15, 17, 19, 21};
cout<<*list; //11 is printed;
cout<<(*list+1); //12 is printed;
cout<<*(list+1); //13 is printed;
6
Function-
array parameter or pointer parameter
7
Dynamic Memory Allocation
int* result = new int[n]; // Allocate
delete [] result; // Deallocate
int* p = new int; // Allocate
delete p; // Deallocate
8
Array and Pointer
What are the values in values array?
11, 1, 3, 6, 10
9
Program with pointer arithmetic
10
p points to the first element
p points to the next element
dereference
Example-reverse an array
Task: write a program to reverse an array
Input: an array with 6 elements { 1, 2, 3, 4, 5, 6 }
Output: an array with 6 elements {6, 5, 4, 3, 2, 1}
The pointer arithmetic is required to be used
Solution
Pointer: int *p…
Dereference: *p
Pointer++, --: p++, p--
11
Example-reverse an array
12
#define N 6
Example-dynamic memory allocation
13
We can use the variable to initialize the array size!
If you still need to use the array list (return list in the function), do not delete the array.
Pointer (Function – count)
14
int count(char *s, char c)
{
int occurrence=0;
for (char * pi=s; *pi!='\0'; pi++){
if (*pi==c)
occurrence++;
}
return occurrence;
}
Pointer (Function – count)
15
void main(){
char str[]="Hong Kong is a very good place to live";
int count1 = count(str, 'o');
cout << "count = “ <
cin : input stream physically linked to the keyboard
cout: output stream physically linked to the screen
File stream class in C++
#include
ifstream: stream class for file input
ofstream: stream class for file output
To declare an objects of class ifstream or ofstream, use
ifstream fin;
ofstream fout;
ifstream
24
To declare an ifsteam object
ifstream fin;
To open a file for reading
fin.open(“infile.dat”);
To read the file content
fin >> x; //x is a variable
To close the file
fin.close();
ofstream
25
To declare an ofsteam object
ofstream fout;
To open a file for writing
fout.open(“myfile.dat”) ;
To write something to the file
fout << x; //x is a variable
To close the file
fout.close();
PS: fin.open() and fout.open() refer to different functions
Examples
26
#include
using namespace std;
void main(){
ifstream fin;
ofstream fout;
int x,y,z;
fin.open(“input.txt”);
fout.open(“output.txt”);
fin >>x>>y>>z;
fout << “The sum is “<
if (fin.eof()) …
The expression fin >> x has value 0 if fin has no more data
E.g. while (fin>> x)
{…}
Examples: File Dump (Integer Only)
28
#include
#include
using namespace std;
void main(){
ifstream fin;
int x;
fin.open(“input.txt”);
while (!fin.eof()){
fin >> x;
cout <
#include
using namespace std;
void main(){
ifstream fin;
int x;
fin.open(“input.txt”);
while (fin >> x){
cout <
#include
Using namespace std;
void main(){
ifstream in1, in2;
in1.open(“infile1.dat”);
in2.open(“infile2.dat”);
if (in1.fail()) {
cout << “Input file 1 opening failed.\n”;
exit(1); // 1 stands for error
}
...
Reference Only: I/O Re-directions
32
A facility offered by many OS’s.
Allows the program input and output to be redirected from/to specified files.
E.g. suppose you have an executable file hello.exe. If you type:
hello > outfile1.dat
in the MSDOS prompt, the output is written to the file outfile1.dat instead of the screen.
Similarly, hello < infile1.dat specifies that the input is from infile1.dat instead of the keyboard.
Summary
33
Beside reading and writing data from and to console, program can read and write data from and to file.
ifstream and ofstream are two classes defined in
File must be open before access and close after access.
fin.open(“filename”);
fin.close();
File I/O is similar to console I/O.
cin >> x;
fin >> x;
Recursion
A recursive function is a function that calls itself.
In some problems, it may be natural to define the problem in terms of the problem itself.
Recursive functions can be useful in solving problems that can be broken down into smaller or simpler sub-problems of the same type.
A base case should eventually be reached, at which time the breaking down (recursion) will stop.
34
34
Example 1:
Problem of Recursive Nature (1)
35
The factorial function
6! = 6 * 5 * 4 * 3 * 2 * 1
We could write:
6! = 6 * 5!
Example 1:
Problem of Recursive Nature (2)
In general, we can express the factorial function on the last slide as follows:
n! = n * (n-1)!
Is this correct? Well… almost.
The factorial function is only defined for positive integers. So we should be a bit more precise:
n! = 1 (if n is equal to 1)
n! = n * (n-1)! (if n is larger than 1)
33
Example 1:
Problem of Recursive Nature (3)
The C++ equivalent of this definition:
int fac(int numb){
if(numb<=1)
return 1;
else
return numb * fac(numb-1);
}
34
Example 1:
Problem of Recursive Nature (4)
Assume the number typed is 3, that is, numb=3.
fac(3) :
int fac(int numb){
if(numb<=1)
return 1;
else
return numb * fac(numb-1);
}
3 <= 1 ? No.
fac(3) = 3 * fac(2)
fac(2) :
2 <= 1 ? No.
fac(2) = 2 * fac(1)
fac(1) :
1 <= 1 ? Yes.
return 1
fac(2) = 2 * 1 = 2
return fac(2)
fac(3) = 3 * 2 = 6
return fac(3)
fac(3) has the value 6
35
Example 1:
Problem of Recursive Nature (5)
For certain problems (such as the factorial function), a recursive solution often leads to short and elegant code. Compare the recursive solution with the iterative solution:
Recursive solution
int fac(int numb){
if(numb<=1)
return 1;
else
return numb*fac(numb-1);
}
Iterative solution
int fac(int numb){
int product=1;
while(numb>1){
product *= numb;
numb–;
}
return product;
}
36
Recursion
If we use iteration, we must be careful, not to create an infinite loop by accident:
for(int incr=1; incr!=10;incr+=2)
…
int result = 1;
while(result >0){
…
result++;
}
Oops!
Oops!
37
Recursion
Similarly, if we use recursion, we must be careful not to create an infinite chain of function calls:
int fac(int numb){
return numb * fac(numb-1);
}
Or:
int fac(int numb){
if (numb<=1)
return 1;
else
return numb * fac(numb+1);
}
Oops!
No termination condition
Oops!
38
Recursion
We must always make sure that the recursion bottoms out:
A recursive function must contain at least one non-recursive branch.
The recursive calls must eventually lead to a non-recursive branch.
39
Recursion
Recursion is one way to decompose a task into smaller subtasks. At least one of the subtasks is a smaller example of the same task.
The smallest example of the same task has a non-recursive solution.
Example: The factorial function
n! = n * (n-1)! and 1! = 1
40
How many pairs of rabbits can be produced from a single pair in a year's time?
Assumptions:
Each pair of rabbits produces a new pair of offspring every month;
each new pair becomes fertile at the age of one month;
none of the rabbits dies in that year.
Example:
After 1 month there will be 2 pairs of rabbits;
after 2 months, there will be 3 pairs;
after 3 months, there will be 5 pairs (since the following month the original pair and the pair born during the first month will both produce a new pair and there will be 5 in all).
41
Population Growth in Nature
Leonardo Pisano (Leonardo Fibonacci = Leonardo, son of Bonaccio) proposed the sequence in 1202 in The Book of the Abacus.
Fibonacci numbers are believed to model nature to a certain extent, such as Kepler's observation of leaves and flowers in 1611.
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html
42
Direct Computation Method
Fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
where each number is the sum of the preceding two.
Recursive definition:
F(0) = 0;
F(1) = 1;
F(number) = F(number-1)+ F(number-2);
43
Example 2: Fibonacci numbers
//Calculate Fibonacci numbers using recursive function.
//A very inefficient way, but illustrates recursion well
int fib(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
return (fib(number-1) + fib(number-2));
}
int main(){// driver function
int inp_number;
cout << "Please enter an integer: ";
cin >> inp_number;
cout << "The Fibonacci number for "<< inp_number
<< " is "<< fib(inp_number)<
cout << message << endl;
nPrintln(message, times - 1);
} // The base case is n == 0
}
51
54
Example 6: Think Recursively
Many of the problems can be solved easily using recursion if you think recursively. For example, the palindrome problem can be solved recursively as follows:
A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward.
bool isPalindrome(char * s)
{
if (strlen(s) <= 1) // Base case
return true;
else if (s[0] != s[strlen(s) - 1]) // Base case
return false;
else
return isPalindrome(substring(s, 1, strlen(s) - 2));
}
52
55
Recursive Helper Methods
The preceding recursive isPalindrome method in Example 6 is not efficient, because it creates a new string for every recursive call. To avoid creating new strings, use a helper method:
#include
using namespace std;
bool isPalindrome( char * s, int low, int high)
{
if (high <= low) // Base case
return true;
else if (s[low] != s[high]) // Base case
return false;
else
return isPalindrome(s, low + 1, high - 1);
}
bool isPalindrome( char * s)
{
return isPalindrome(s, 0, strlen(s) - 1);
}
void main(){
cout << isPalindrome("ABCDCBA");
}
53
56
S
t
r
e
a
m
o
f
d
a
t
a
Program
Stream of data
Program
/docProps/thumbnail.jpeg