|
|
|
|
Summary
• Pointers (continued)
• Multi-dimensional Arrays
• Pointers to Pointers
• Command-line Arguments
• Exercises
• Tips
Pointers (continued)
We will continue with the elaboration of the concept of pointers in this lecture.
To further
understand pointers, let's consider the following statement.
char myName[] = "Full Name";
This statement creates a 'char' type array and populates it with a string. Remember
the
character strings are null ( '\0' ) terminated. We can achieve the same thing with
the use
of pointer as under:
char * myNamePtr = "Full Name";
Page 174
Let's see what's the difference between these two approaches?
When we create an array, the array name, 'myName' in this case, is a constant pointer.
The starting address of the memory allocated to string "FullName" becomes the contents
of the array name 'myName' and the array name 'myName' can not be assigned any other
value. In other words, the location to which array names points to can not be changed.
In
the second statement, the 'myNamePtr' is a pointer to a string "FullName", which
can
always be changed to point to some other string.
Hence, the array names can be used as pointers but only as constant ones.
Multi-dimensional Arrays
Now we will see what is the relationship between the name of the array and the pointer.
Suppose we have a two-dimensional array:
char multi[5][10];
In the above statement, we have declared a 'char' type array of 5 rows and 10 columns.
As discussed above, the array name points to the starting memory location of the
memory
allocated for the array elements. Here the question arises where the 'multi' will
be
pointing if we add 1 to ‘multi’.
We know that a pointer is incremented by its type number of bytes. In this case,
'multi' is
an array of 'char' type that takes 1 byte. Therefore, ‘muti+1’ should take us to
the second
Full Name\0
myName Full Name\0
myNamePtr
75
[0]
72
[1]
68
[2]
82
[3]
80
[4]
79
[5]
69
[6]
67
[7]
73
[8]
77
[9]
83
[0]
1st row 1st
col 2nd
row 1st
col
Multi-dimensional array in the memory
80
[1]
Page 175
element of the first row (row 0). But this time, it is behaving differently. It
is pointing to
the first element (col 0) of the second row (row 1). So by adding '1' in the array
name, it
has jumped the whole row or jumped over as many memory locations as number of
columns in the array. The width of the columns depends upon the type of the data
inside
columns. Here, the data type is 'char', which is of 1 byte. As the number of columns
for
this array 'multi' is 10, it has jumped 10 bytes.
Remember, whenever some number is added in an array name, it will jump as many rows
as the added number. If we want to go to the second row (row 1) and third column
(col 2)
using the same technique, it is given ahead but it is not as that straight forward.
Remember, if the array is to be accessed in random order, then the pointer approach
may
not be better than array indexing.
We already know how to dereference array elements using indexing. So the element
at
second row and third column can be accessed as 'multi[1][2]'.
To do dereferencing using pointers we use '*' operator. In case of one-dimensional
array,
'*multi' means 'the value at the address, pointed to by the name of the array'.
But for twodimensional
array '*multi' still contains an address of the first element of the first row of
the array or starting address of the array 'multi'. See the code snippet to prove
it.
/* This program uses the multi-dimensional array name as pointer */
#include <iostream.h>
void main(void)
{
//To avoid any confusion, we have used ‘int’ type below
int multi[5][10];
cout << "\n The value of multi is: " << multi;
cout << "\n The value of *multi is: " << *multi;
}
Now, look at the output below:
The value of multi is: 0x22feb0
The value of *multi is: 0x22feb0
It is pertinent to note that in the above code, the array ‘multi’ has been changed
to ‘int’
from ‘char’ type to avoid any confusion.
Page 176
To access the elements of the two-dimensional array, we do double dereferencing
like
'**multi'. If we want to go to, say, 4th row (row 3), it is achieved as 'multi +
3' . Once
reached in the desired row, we can dereference to go to the desired column. Let's
say we
want to go to the 4th column (col 3). It can be done in the following manner.
*(*(multi+3)+3)
This is an alternative way of manipulating arrays. So 'multi[3][3]' element can
also be
accessed by '*(*(multi+3)+3)'.
There is another alternative of doing this by using the normal pointer. Following
code
reflects it.
/* This program uses array manipulation using indexing */
#include <iostream.h>
void main(void)
{
int multi [5][10];
int *ptr; // A normal ‘int’ pointer
ptr = *multi; // ‘ptr’ is assigned the starting address of the first row
/* Initialize the array elements */
for(int i=0; i < 5; i++)
{
for (int j=0; j < 10; j++)
{
multi[i][j] = i * j;
}
}
/* Array manipulation using indexing */
cout << "\n Array manipulated using indexing is: \n";
for(int i=0; i < 5; i++)
{
for (int j=0; j < 10; j++)
{
cout << multi[i][j] << '\t';
}
cout << '\n';
}
/* Array manipulation using pointer */
cout << "\n Array manipulated using pointer is: \n";
for(int k=0; k < 50; k++, ptr ++) // 5 * 10 = 50
{
cout << *ptr << '\t';
}
Page 177
}
The output of this program is:
Array manipulated using indexing is:
0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
0 2 4 6 8 10 12 14 16 18
0 3 6 9 12 15 18 21 24 27
0 4 8 12 16 20 24 28 32 36
Array manipulated using pointer is:
0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5
6 7 8 9 0 2 4 6 8 10 12 14 16 18 0 3
6 9 12 15 18 21 24 27 0 4 8 12 16 20 24
28 32 36
The above line of output of array manipulation is wrapped because of the fixed width
of
the table. Actually, it is a single line.
Why it is a single line? As discussed in the previous lectures, computer stores
array in
straight line (contiguous memory locations). This straight line is just due to the
fact that a
function accepting a multi-dimensional array as an argument, needs to know all the
dimensions of the array except the leftmost one. In case of two-dimensional array,
the
function needs to know the number of columns so that it has much information about
the
end and start of rows within an array.
It is recommended to write programs to understand and practice the concepts of double
dereferencing, single dereferencing, incrementing the name of the array to access
different rows and columns etc. Only hands on practice will help understand the
concept
thoroughly.
Pointers to Pointers
What we have been talking about, now we will introduce a new terminology, is actually
a
case of ‘Pointer to Pointer’. We were doing double dereferencing to access the elements
of a two-dimensional array by using array name (a pointer) to access a row (another
pointer) and further to access a column element (of ‘int’ data type).
In case of single dereference, the value of the pointer is the address of the variable
that
contains the value desired as shown in the following figure. In the case of pointer
to
pointer or double dereference, the first pointer contains the address of the second
pointer,
which contains the address of the variable, which contains the desired value.
address
P i
value
V i bl
Si l I di i ( i l d f )
P i P i V i bl
Page 178
Pointers to Pointers are very useful. But you need to be very careful while using
the
technique to avoid any problem.
Earlier, we used arrays and pointers interchangeably. We can think that a pointer
to
pointer is like a pointer to a group of arrays because a pointer itself can be considered
as
an array. We can elaborate with the following example by declaring character strings.
While using an array, we at first decide about the length of the array. For example,
you
are asked to calculate the average age of your class using the array. What would
be the
dimension of the array? Normally, you will look around, count the students of the
class
and keep the same size of the array as the number of students, say 53. Being a good
programmer, you will look ahead and think about the maximum size of the class in
the
future and decide to take the size of the array as 100. Here, you have taken care
of the
future requirements and made the program flexible. But the best thing could be:
to get the
size of the array from the user at runtime and set it in the program instead of
declaring the
array of maximum size. We will cover this topic at some later stage.
When we initialize an array with a character string, the number of characters in
the
character string determines the length of array (plus one character to include the
‘\0’
character). eg. it is a single-dimensional array:
char name[] = “My full name”;
The size of the ‘name’ array is 13.
Suppose, we have a group of character strings and we want to store them in a twodimensional
array. As we already discussed, an array has same number of columns in
each row, e.g. a[5][10] array has 10 columns in each row. Now if we store character
strings of variable length in a two-dimensional array, it is necessary to set the
number of
columns of the array as the length of the longest character string in the group
(plus 1 byte
for ‘\0’ character). But the space within rows of the array would be wasted for
all
character strings with shorter length as compared to the number of columns. We don’t
want to waste this space and want to occupy the minimum space required to store
a
character string in the memory.
If we use the conventional two-dimensional array like a [5] [10], there is no way
of using
variable space for rows. All the rows will have fixed ’10’ number of columns in
this case.
But in case of an Array of Pointers, we can allocate variable space. An array of
pointers
Page 179
is used to store pointers in it. Now we will try to understand how do we declare
an array
of pointers. The following statement can help us in comprehending it properly.
char * myarray[10];
We read it as: ‘myarray is an array of 10 pointers to character’. If we take out
the size of
the array, it will become variable as:
char * myarray[] = {“Amir”, “Jehangir”};
For first pointer myarray[0], 5 bytes (4 bytes for ‘Amir’ plus 1 byte for ‘\0’)
of memory
has been allocated. For second pointer myarray[1], 9 bytes of memory is allocated.
So
this is variable allocation depending on the length of character string.
What this construct has done for us? If we use normal two-dimensional array, it
will
require fixed space for rows and columns. Therefore, we have used array of pointers
here.
We declared an array of pointers and initialized it with variable length character
strings.
The compiler allocates the same space as required for the character string to fit
in.
Therefore, no space goes waste. This approach has huge advantage.
We will know more about Pointers to Pointers within next topic of Command-line
Arguments and also in the case study given at the end of this lecture.
Command Line Arguments
Until now, we have always written the ‘main()’ function as under:
main( )
{
. . . // code statements
}
But we are now in a position to write something inside the parenthesis of the ‘main()’
function. In C language, whenever a program is executed, the user can provide the
command-line arguments to it like:
C:\Dev-cpp\work>Program-name argument1 argument2 ……argumentN
We have so far been taking input using the ‘cout’ and ‘cin’ in the program. But
now we
can also pass arguments from the command line just before executing the program.
For
this purpose, we will need a mechanism. In C, this can be done by using ‘argc’ and
‘argv’
arguments inside the main( ) function as:
Amir\0
Jehangir\0
myarray
Page 180
void main(int argc, char **argv)
{
. . .
}
Note that ‘argc’ and ‘argv’ are conventional names of the command line parameters
of
the ‘main()’ function. However, you can give the desired names to them.
argc = Number of command line arguments. Its type is ‘int’.
argv = It is a pointer to an array of character strings that contain the arguments,
one per
string. ‘**argv’ can be read as pointer to pointer to char.
Page 181
Now the command line arguments can be accessed from inside the program using ‘argc’
and ‘argv’ variables. It will be an interesting experience for you to try out the
following
code:
/* Accessing the command line arguments */
#include <iostream.h>
main(int argc, char **argv)
{
cout << argc << endl;
cout << *argv;
}
If we run this program without any argument, then what should be the answer. It
will be
not correct to think that the argc (number of arguments) is zero as we have not
passed any
argument. It counts program name as the first argument. So programs written in C/C++
know their names supplied in the first command-line argument. By running the above
program, we can have the following output:
Program-name
Argument 1
Argument 2
Argument 3
0
argv
Page 182
c:\dev-cpp\work>program
1
program
Here we see that the number of arguments is 1 with the first argument as the program
name itself. You have to go to the command prompt to provide the command line
arguments or you can discuss on the discussion board, how to use Dev-C++ to pass
command line arguments.
The command line arguments are separated by spaces. You can provide command line
arguments to a program as under:
c:\dev-cpp\work>program 1 2
Here the number of arguments (argc) will be 3. The argument “1” and “2” are available
inside the program as character strings. Therefore, you have to convert them into
integers
to ensure their usage as as numbers.
This has been further explained in the following program. It counts down from a
value
specified on the command line and beeps when it reaches 0.
/* This program explains the use of command line arguments */
#include <iostream.h>
#include <stdlib.h> //Included for ‘atoi( )’ function
main(int argc, char **argv)
{
int disp, count;
Page 183
if(argc < 2)
{
cout << "Enter the length of the count\n";
cout << "on the command line. Try again.\n";
return 1;
}
if(argc == 3 && !strcmp(*(argv + 2), "display"))
{
disp = 1;
}
else
{
disp = 0;
}
for(count = atoi(*(argv + 1)); count; --count)
{
if(disp)
Page 184
{
cout << count <<' ';
}
}
cout << '\a'; // ’\a’causes the computer to beep
return 0;
}
You must have noted that if no arguments are specified, an error message will be
printed.
It is common for a program that uses command-line arguments to issue instructions
if an
attempt has been made to run it without the availability of proper information.
The first
argument containing the number is converted into an integer using the standard function
‘atoi( )’. Similarly, if the string ‘display’ is present as the second command-line
argument, the count will also be displayed on the screen.
In theory, you can have up to 32,767 arguments but most operating systems do not
allow
more than a few because of the fixed maximum length of command-line. These
arguments are normally used to indicate a file name or an option. Using command-line
arguments lends your program a very professional touch and facilitates the program’s
use
in batch files.
Case Study: A Card Shuffling and Dealing Simulation
Now we want to move on to a real-world example where we can demonstrate pointer
to
pointer mechanism.
Problem:
Write a program to randomly shuffle the deck of cards and to deal it out.
Some Facts of Card Games:
- There are 4 suits in one deck: Hearts, Spades, Diamonds and Clubs.
Page 185
- Each suit has 13 cards: Ace, Deuce, Three, Four, Five, Six, Seven, Eight,
Nine, Ten,
Jack, Queen and King.
- A deck has 13 * 4 = 52 cards in total.
Problem Analysis, Design and Implementation:
As obvious from the problem statement, we are dealing with the deck of cards, required
to be identified. A card is identified by its suit i.e. it may be one of the Hearts,
Spades,
Diamonds or Clubs. Also every card has one value in the range starting from Ace
to
King. So we want to identify them in our program and our requirement is to use English
like ‘five of Clubs’. We will declare one array of suit like:
const char *suite[4] = {“Hearts”, “Diamonds”, “Clubs”, “Spades” };
The second array is of values of cards:
const char *face[13] = { “Ace”, “Deuce”, “Three”, “Four”, “Five”, “Six”,
“Seven”, “Eight”, “Nine”, “Ten”, “Jack”, “Queen” and “King”};
You must have noticed the use of array of pointers and ‘const’ keyword here. Both
the
arrays are declared in a way to avoid any wastage of space. Also notice the use
of ‘const’
keyword. We declared arrays as constants because we want to use these values without
modifying them.
Now we come to deck which has 52 cards. The deck is the one that is being shuffled
and
dealt. Definitely, it has some algorithmic requirements.
Firstly, what should be size and structure of the deck. It can either be linear
array of 52
elements or 4 suites and 13 values (faces) per suit. Logically, it makes sense to
have twodimensional
array of 4 suites and 13 faces per suit like:
int deck[4][13] = {0};
We will now think in terms of Algorithm Analysis.
The ‘deck’ is initialized with the 0 value, so that it holds no cards at start or
it is empty.
We want to distribute 52 cards. Who will load the ‘deck’ first, shuffle the cards
and deal
them out. How to do it?
As we want to select 52 cards (a deck) randomly, therefore, we can think of a loop
to get
one card randomly in every iteration. We will randomly choose one out of the 4 suites
and select one value out of 13 values and store the card with its card number value
in the
deck. By this way, we will be writing numbers in the two-dimensional array of ‘deck’
randomly. That functionality is part of ‘shuffle ()’ function.
Page 186
void shuffle( int wDeck[][13] )
{
int row, column, card;
for ( card = 1; card <= 52; card++){
do{
row = rand() % 4;
column = rand() % 13;
} while( wDeck [ row ][ column ] != 0 );
wDeck[ row ][ column ] = card;
}
}
You have noticed the ‘rand()’ function usage to generate random numbers. We are
dividing the randomly generated number by 4 and 13 to ensure that we get numbers
within our desired range. That is 0 to 3 for suites and 0 to 12 for values or faces.
You also
see the condition inside the ‘while statement, ‘wDeck[ row ][ column ] != 0 ‘. This
is to
ensure that we don’t overwrite row and column, which has already been occupied by
some card.
Now we want to deal the deck. How to deal it?
“At first, search for card number 1 inside the deck, wherever it is found inside
the ‘deck’
array, note down the row of this element. Use this row to get the name of the suite
from
the ‘suite’ array. Similarly use the column to take out the value of the card from
the ‘face’
array.” See that the deal function is quite simple now.
void deal( const int wDeck[][ 13 ], const char *wFace[], const char *wSuit[])
{
int card, row, column;
for ( card = 1; card <= 52; card++ )
for( row = 0; row <= 3; row++)
for( column = 0; column <= 12; column++)
if( wDeck[ row ][ column ] == card )
cout << card << ". " <<wFace[ column ] <<
" of " << wSuit [row ] << '\n';
}
Here, we are not doing binary search that is more efficient. Instead, we are using
simple
brute force search. Also see the ‘for loops’ carefully and how we are printing the
desired
output.
Now we will discuss a little bit about the srand() function used while generating
random
numbers. We know that computers can generate random numbers through the ‘rand()’
function. Is it truly random? Be sure , it is not truly random. If you call ‘rand()’
function
Page 187
again and again. It will give you numbers in the same sequence. If you want your
number
to be really random number, it is better to set the sequence to start every time
from a new
value. We have used ‘srand()’ function for this purpose. It is a seed to the random
number
generator. Seed initializes the random number generator with a different value every
time
to generate true random numbers. We call ‘srand()’ function with a different value
every
time. The argument to ‘srand()’ function is taken from the ‘time()’ function which
is
giving us a new value after every one second. Every time we try to run the program,
‘time()’ returns a different number of seconds, which are passed to ‘srand()’ function
as
an argument so that the seed to the random number generator is a different number.
It
means that the random number generator now generates a different sequence of random
numbers.
Although, you can copy this program and see the output after executing it, but this
is not
the objective of this exercise. You are required to study the problem and see the
constructs very carefully. In this problem, you have examples of nested loops, array
of
pointers, variable sized strings in an array of pointers and random number usage
in the
real world problem etc.
/* Card shuffling and dealing program */
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
void shuffle( int [] [ 13 ]);
void deal( const int [][ 13 ], const char *[], const char *[]);
int main()
{
Page 188
const char *suite[ 4 ] = {"Hearts", "Diamonds", "Clubs", "Spades" };
const char *face[ 13 ] = { "Ace", "Deuce", "Three", "Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Jack", "Queen", "King"};
int deck[ 4 ][ 13 ] = { 0 };
srand( time( 0 ) );
shuffle( deck );
deal( deck, face, suite );
return 0;
}
void shuffle( int wDeck[][13] )
{
int row, column, card;
for ( card = 1; card <= 52; card++){
do{
Page 189
row = rand() % 4;
column = rand() % 13;
} while( wDeck [ row ][ column ] != 0 );
wDeck[ row ][ column ] = card;
}
}
void deal( const int wDeck[][ 13 ], const char *wFace[], const char *wSuit[])
{
int card, row, column;
const char *space;
for ( card = 1; card <= 52; card++ )
for( row = 0; row <= 3; row++)
for( column = 0; column <= 12; column++)
if( wDeck[ row ][ column ] == card )
cout << card << ". " <<wFace[ column ] << " of " << wSuit
[row ] << '\n';
Page 190
}
A sample output of the program is:
1. Six of Diamonds
2. Ten of Hearts
3. Nine of Clubs
4. King of Hearts
5. Queen of Clubs
6. Five of Clubs
7. Queen of Hearts
8. Eight of Hearts
9. Ace of Diamonds
10. Ten of Diamonds
11. Seven of Spades
12. Ten of Clubs
13. Seven of Clubs
14. Three of Spades
15. Deuce of Clubs
Page 191
16. Eight of Diamonds
17. Eight of Clubs
18. Nine of Spades
19. Three of Clubs
20. Jack of Clubs
21. Queen of Spades
22. Jack of Hearts
23. Jack of Spades
24. Jack of Diamonds
25. King of Diamonds
26. Seven of Hearts
27. Five of Spades
28. Seven of Diamonds
29. Deuce of Hearts
30. Ace of Spades
31. Five of Diamonds
32. Three of Hearts
33. Six of Clubs
34. Four of Hearts
Page 192
35. Ten of Spades
36. Deuce of Spades
37. Three of Diamonds
38. Eight of Spades
39. Nine of Hearts
40. Ace of Clubs
41. Four of Spades
42. Queen of Diamonds
43. King of Clubs
44. Five of Hearts
45. Ace of Hearts
46. Deuce of Diamonds
47. Four of Diamonds
48. Four of Clubs
49. Six of Hearts
50. Six of Spades
51. King of Spades
52. Nine of Diamonds
Page 193
Exercises
1. Write the program ‘tail’, which prints the last n lines of its input. By default,
n is 10,
let’s say, but it can be changed by an optional argument, so that
tail -n
prints the last n lines.
Tips
Pointers and arrays are closely related in C. The array names can be used
as pointers
but only as constant pointers.
A function receiving a multi-dimensional array as a parameter must minimally
define
all dimensions except the leftmost one.
Each time a pointer is incremented, it points to the memory location of
the next
element of its base type but in case of two-dimensional array, if you add some
number in a two-dimensional array name, it will jump as many rows as the added
number.
If the array is to be accessed in random order, then the pointer approach
may not be
better than array indexing.
The use of pointers may reduce the wastage of memory space. As discussed
in this
lecture if we store a set of character strings of different lengths in a two-dimensional
array, the memory space is wasted.
Pointers may be arrayed (stored in an array) like any other data type.
An array of pointers is the same as pointers to pointers.
Although, you can give your desired names to the command line parameters
inside
‘main()’ function but ‘argc’ and ‘argv’ are conventionally used.
|
|
|
|
|