Stacks

Stacks and queues are two very common and popular data structures. These data structures are often implemented using arrays since most programming languages provide array as a predefined data type, and such an implementation is therefore quite easy. However, when implemented as an array these data structures suffer from the basic limitation of an array: that its size cannot be increased or decreased once it is declared. As a result one ends up reserving either too much space or too less space for an array and in turn for a stack or a queue. This difficulty is eliminated when we implement these data structures using linked lists. Before we do so let us formally define these data structures.

A stack is a data structure in which addition of new element or deletion of existing element always takes place at the same end. This end is often known as top of stack. This situation can be compared to a stack of plates in a cafeteria where every new plate added to the stack is added at the top. Similarly, every new plate taken off the stack is also from the top of the stack. There are several applications where stack can be put to use. For example, recursion, keeping track of function calls, evaluation of expressions etc. Unlike a stack, in a queue the addition of new element takes place at the end (called rear of queue), whereas deletion takes place at the other end (called front of queue). The following figure shows these two data structures. A stack is often called a Last-In-First-Out (LIFO) structure, whereas a queue is called a First-In-First-Out (FIFO) structure


Implementing A Stack Using An Array

The program given below implements the stack data structure using an array. In this program the elements are pushed into array stack[ ] through push( ) function. The parameters passed to push( ) are the base address of the array, the position in the stack at which the element is to be placed and the element itself. Care is taken by the push( ) function that the user does not try to place the element beyond the bounds of the stack. This is done by checking the value stored in pos. pop( ) function pops out the last element stored in the stack[ ]. Because, pos holds the position which has the last element in the stack.

 
/* To pop and push items in a stack */
#define MAX 10
 
void push ( int ) ;
int pop( ) ;
 
int stack[MAX] ;
int pos ;
 

void main( )

{

int n ;

clrscr( ) ;
 
pos = -1 ; /* stack is empty */
 
push ( 10 ) ;
push ( 20 ) ;
push ( 30 ) ;
push ( 40 ) ;
 
n = pop( ) ;
printf ( "\nitem popped out is : %d", n ) ;
 
n = pop( ) ;
printf ( "\nitem popped out is : %d", n ) ;
}
 
/* pushes item on the stack */
void push ( int data )
{

if ( pos == MAX - 1 )

printf ( "\nStack is full" ) ;

else

{

pos++ ;

stack[ pos ] = data ;

}

}

/* pops off the items from the stack */

int pop( )

{

int data ;

if ( pos == -1 )

{

printf ( "\nStack is empty" ) ;

return ( -1 ) ;

}

else

{

data = stack[ pos ] ;

pos-- ;

return ( data ) ;

}

}


Implementing Stack As A Linked List

In this program stack is implemented and maintained using linked list. This implementation is more sophisticated compared to the one that uses an array, the added advantage being we can push as many elements as we want. A new node is created by push( ) (using malloc( )) every time an element is pushed in the stack. Each node in the linked list contains two members, data holding the data and link holding the address of the next node. The end of the stack is identified by the the node holding NULL in its link part. The pop( ) function pops out the last element inserted in the stack and frees the memory allocated to hold it. stack_display( ) displays all the elements that stack holds. count( ) counts and returns the number of elements present in the stack.

#include "alloc.h"

struct node

{

int data ;

struct node *link ;

} ;

push ( struct node **, int ) ;

pop ( struct node ** ) ;

main( )

{

struct node *top ; /* top will always point to top of a stack */

int item ;

top = NULL ; /* empty stack */

push ( &top, 11 ) ;

push ( &top, 12 ) ;

push ( &top, 13 ) ;

push ( &top, 14 ) ;

push ( &top, 15 ) ;

push ( &top, 16 ) ;

push ( &top, 17 ) ;

clrscr( ) ;

stack_display ( top ) ;

printf ( "No. of items in stack = %d" , count ( top ) ) ;

printf ( "\nItems extracted from stack : " ) ;

item = pop ( &top ) ;

printf ( "%d ", item ) ;

item = pop ( &top ) ;

printf ( "%d ", item ) ;

item = pop ( &top ) ;

printf ( "%d ", item ) ;

stack_display ( top ) ;

printf ( "No. of items in stack = %d" , count ( top ) ) ;

}

/* adds a new element on the top of stack */

push ( struct node **s, int item )

{

struct node *q ;

q = malloc ( sizeof ( struct node ) ) ;

q -> data = item ;

q -> link = *s ;

*s = q ;

}

/* removes an element from top of stack */

pop ( struct node **s )

{

int item ;

struct node *q ;

/* if stack is empty */

if ( *s == NULL )

printf ( " stack is empty" ) ;

else

{

q = *s ;

item = q -> data ;

*s = q -> link ;

free ( q ) ;

return ( item ) ;

}

}

/* displays whole of the stack */

stack_display ( struct node *q )

{

printf ( "\n" ) ;

/* traverse the entire linked list */

while ( q != NULL )

{

printf ( "%2d ", q -> data ) ;

q = q -> link ;

}

printf ( "\n" ) ;

}

/* counts the number of nodes present in the linked list representing a stack */

count ( struct node * q )

{

int c = 0 ;

/* traverse the entire linked list */

while ( q != NULL )

{

q = q -> link ;

c++ ;

}

return c ;

}

Pointers And Structures

  1. Structure is usually a collection of dissimilar data types; unlike an array which is a collection
    of similar data types. Usually a structure is declared first followed by definition of a structure
    variable as shown below:

    /* declaration of a structure */
    struct book
    {
    char name[20] ;
    int numpages ;
    float price ;
    } ;

    /* definition of a structure variable */
    struct book b ;

  2. A structure variable can be initialized at the same place where it is being defined, as in
    struct book b = { "Basic", 425, 135.00 } ;

  3. Declaration of a structure and definition of a structure variable can be combined into one. When this
    done mentioning the structure name is optional.

    struct
    {
    char name[20] ;
    int numpages ;
    float price ;
    } b = { "Basic", 425, 135.00 } ;

  4. Size of a structure variable is sum of sizes of its individual elements. For example, size of b
    in (c) above is: 20 + 2 + 4 = 26 bytes.

  5. Elements of a structure are stored in adjacent memory locations. For example, the following program would produce the output
    4001, 4021, 4023.


  6. struct book
    {
    char name[20] ;
    int numpages ;
    float price ;
    } ;
    struct book b = { "Basic", 425, 135.00 } ;
    printf ( "%u %u %u", b.name, &b.numpages, &b.price ) ;

  7. It is possible to build an array of structures.
    struct book
    {
    char name[20] ;
    int numpages ;
    float price ;
    } ;
    struct book b[ ] = {
    { "Basic", 425, 135.00 },
    { "Pascal", 500, 155.00 },
    { "VBasic", 625, 335.00 }
    } ;

  8. Nested structures are legal as in:

    struct address
    {
    char city[20] ;
    long int pin ;
    } ;
    struct emp
    {
    char n[20] ;
    int age ;
    struct address a ;
    float s ;
    } ;
    struct emp e = { "Rahul", 23, "Nagpur", 440010, 4000.50 } ;

  9. Contents of one structure variable can be copied either into another structure variable either piece
    meal or at one shot. This is shown below:

    struct book
    {
    char name[20] ;
    int numpages ;
    float price ;
    } ;

    struct book b1 = { "Basic", 425, 135.00 } ;
    struct book b2, b3 ;

    /* piecemeal copying */
    strcpy ( b2.n, b1.n ) ;
    b2.numpages = b1.numpages ;
    b2.price = b1.price ;

    /* copying at one shot */
    b3 = b2 ;

  10. Elements of a structure can be passed to a function.

    main( )
    {
    struct book
    {
    char name[20] ;
    int numpages ;
    float price ;
    } ;

    struct book b1 = { "Basic", 425, 135.00 } ;

    /* mixed call - call be value + call by reference */
    display ( b1.name, b1.numpages, b1.price ) ;

    /* pure call by reference */
    show ( b1.name, &b1.numpages, &b1.price ) ;
    }

    display ( char *n, int nop, float pr )
    {
    printf ( "%s %d %f", n, nop, pr ) ;
    }

    display ( char *n, int *nop, float *pr )
    {
    printf ( "%s %d %f", n, *nop, *pr ) ;
    }

  11. Entire structure can also be passed to a function.

    // declaration must be global.
    // Otherwise diaplay1() and show1() can't use it
    struct book
    {
    char name[20] ;
    int numpages ;
    float price ;
    } ;

    main( )
    {
    struct book b1 = { "Basic", 425, 135.00 } ;
    // call be value
    display1 ( b1 ) ;

    // call by reference
    show1 ( &b1 ) ;
    }

    display1 ( struct book b2 )
    {
    printf ( "%s %d %f", b2.name, b2.numpages, b2.price ) ;
    }

    show1 ( struct book *b2 )
    {
    printf ( "%s %d %f", ( *b2 ).name, ( *b2 ).numpages, ( *b2 ).price ) ;
    printf ( "%s %d %f", b2->name, b2->numpages, b2->price ) ;
    }

  12. Self referential structures contain a pointer to itself within its declaration. These are necessary for building linked lists.

    struct node
    {
    int data ;
    node *link ;
    } ;

What will be the output of the following program

main( )

{

struct s1

{

char *z ;

int i ;

struct s1 *p ;

} ;

static struct s1 a[ ] = {

{ "Nagpur", 1, a + 1 },

{ "Raipur", 2, a + 2 },

{ "Kanpur", 3, a }

} ;

struct s1 *ptr = a ;

printf ( "\n%s %s %s", a[0].z, ptr->z, a[2].p->z ) ;

}

Output
Nagpur Nagpur Nagpur

Explanation:
The zeroth and first elements of struct s1 are a char pointer and an int respectively. The second element is what's new.
It is a pointer to a structure. That is, p stores the starting address of a structure variable of the type struct s1. Next, a[ ], an array of such structures is declared as well as initialised. During initialisation the base address of "Nagpur" is stored in a[0].z, 1 is stored in the element a[0].i, and a + 1 is assigned to a[0].p. On similar lines, the remaining two elements of the array are initialised. a[1].z, a[1].i and a[1].p are assigned "Raipur", 2 and a + 2 in that order, and "Kanpur", 3 and a are stored at a[2].z, a[2].i and a[2].p respectively. What exactly do a, a + 1 and a + 2 signify? a, of course, is the base address of the array a[ ]. Let us assume it to be 4000, as shown in Figure 1. Locations 4000 and 4001 are occupied by the char pointer a[0].z, since a pointer is always two bytes long.

The next two bytes are used to store the integer a[0].i, and then 4004 and 4005 are used by a[0].p. Similarly, the next 6 bytes store the first structure a[1], and the 6 bytes after that contain a[2], the second structure in the array.


Figure 1.

Now, when we say a + 1, we do not arrive at 4001, but at 4006. This is because on incrementing any pointer, it points to the next location of its type. a points to the zeroth structure in the array, i.e. a[0]. Hence, on incrementing a, it will point to the next immediate element of its type, i.e. the first structure a[1] of the array. Likewise, a + 2 signifies the address of the second element a[2] of the array. Thus, a[0].p contains address 4006 (refer figure), a[1].p contains 4012, and a[2].p stores 4000. A struct pointer ptr is now set up, which is assigned a, the base address of the array. In the printf( ), a[0].z denotes the address from where "Nagpur" is stored. Hence "Nagpur" gets printed out. Since ptr contains the address of a[0], ptr->z refers to the contents of element z of the array element a[0]. Thus ptr->z gives the address A0 (refer figure) and this address happens to be the base address of the string "Nagpur". Hence "Nagpur" gets printed out. Let us now analyse the expression a[2].p->z. The left side of the arrow operator always represents the base address of a structure. What structure does a[2].p point to? Looking at the figure we can confirm that a[2].p contains the address 4000, which is the base address of the array a[ ]. Hence the expression a[2].p->z can also be written as a->z. Since a is the base address of the structure a[0], this expression refers to the element z of the zeroth structure. Thus, "Nagpur" gets printed for the third time.

What will be the output of the following program

main( )

{

struct s1

{

char *str ;

int i ;

struct s1 *ptr ;

} ;

static struct s1 a[ ] = {

{ "Nagpur", 1, a + 1 },

{ "Raipur", 2, a + 2 },

{ "Kanpur", 3, a }

} ;

struct s1 *p = a ;

int j ;

for ( j = 0 ; j <<= 2 ; j++ )

{

printf ( "\n%d " , --a[j].i ) ;

printf ( "%s" , ++a[j].str ) ;

}

}

Output
0 agpur
1 aipur
2 anpur

Explanation
The example deals with a structure similar to the one we just encountered. Picking up from the for loop, it is executed for 3 values of j: 0, 1 and 2. The first time through the for loop, j is equal to zero, so the first printf( ) prints --a[0].i. Since the dot operator has a higher priority, first a[0].i is evaluated, which is 1. As -- precedes the value to be printed, 1 is first decremented to 0, and then printed out.

The second printf( ) prints the string at address ++a[0].str. a[0].str gives the starting address of "Nagpur". On incrementing, it points to the next character, `a' of "Nagpur", so starting from `a', the remaining string "agpur" is outputted. A similar procedure is repeated for j = 1, and then once again for j = 2, following which the execution is terminated.

Pointers And Strings

  1. A string is a collection of characters ending with a '\0'.

    char str1[] = { 'A', 'j', 'a', 'y', '\0' } ;
    char str2[] = "Ajay" ;

    In "Ajay", '\0' is assumed.

  2. If a string is defined and initialized at the same place mentioning its dimension is optional.

  3. While returning the size of a string the sizeof operator counts '\0'.

  4. Base address of a string is address of zeroth element of the string.

  5. Following string library functions are frequently used:

    char str1[] = "Ajay" ;
    char str2[10] ;
    char str3[] = "Kumar" ;

    int l, m, n ;
    l = strlen ( str1 ) ; // returns count of characters. Doesn;t count '\0'.
    strcpy ( str2, str1 ) ; // copies contents of str1 into str2
    strcat ( str3, str1 ) ; // appends contents str3 with that of str1
    m = strcmp ( str1, str2 ) ; // compares two strings, returns zero if equal, non-zero otherwise
    n = strcmp ( str1, "Ajay" ) ; // compares two strings, returns zero if equal, non-zero otherwise

    If the two strings are unequal the ascii difference between first non-matching pair of characters is returned.

  6. There are two ways to handle several strings:
    - using a 2-D array of characters
    - using an array of pointers to strings

char names[][20] = {

"Ajay",

"Atul",

"Ramesh",

"Sivaramakrishnan",

"Sameer"

} ;

char *n[] = {

"Ajay",

"Atul",

"Ramesh",

"Sivaramakrishnan",

"Sameer"

} ;

2-D array suffers from two limitations:
- Leads to lot of wastage of space
- Processing of 2-D array is tedious

Both disadvantages can be overcome using the array of pointers to strings. Array of pointers to strings suffers from the disadvantage that it always needs to be initialized, unless you decide to allocate space for each name dynamically using malloc( ) and then store the address in the array of pointers to strings.

What will be the output of the following program

main( )

{

static char *s[ ] = {

"ice",

"green",

"cone",

"please"

} ;

staic char **ptr[ ] = { s + 3 , s + 2 , s + 1 , s } ;

char ***p = ptr ;

printf ( "\n%s" , **++p ) ;

printf ( "\n%s" , *--*++p + 3 ) ;

printf ( "\n%s" , *p[-2] + 3 ) ;

printf ( "\n%s" , p[-1][-1] + 1 ) ;

}

Output:
cone
ase
reen

Explanation:
This time we seem to be faced with a galaxy of stars! We would do well to take the help of a figure 1. in crossing them one by one. At the outset, s[ ] has been declared and initialised as an array of pointers. Simply saying s gives us the base address of this array, 4006 as can be seen from Figure 1. ptr[ ] stores the addresses of the locations where the base addresses of strings comprising s[ ] have been stored, starting with the last string. To put it more clearly, ptr[0] stores the address 4012, which is the address at which base address of the string "please" is stored. Similarly, ptr[1] stores the address 4010, which is where the base address of the string "cone" is stored, and so on. Since ptr[ ] essentially stores addresses of addresses, it is a pointer to a pointer, and has been declared as such using ** .

Finally, the base address of ptr[ ] is assigned to a pointer to a pointer to a pointer, p. Reeling?! Going through the figure would decidedly aid you to get disentangled. Thus, p is assigned the address 6020.


Figure 1.

Having sorted out what is present where, we now proceed to the printf( ) s. Let us tackle the expressions one by one.

**++p

The first one prints out the string starting from the address **++p . The ++ goes to work first and increments p not to 6021, but to 6022. The C compiler has been made to understand that on incrementing a pointer variable, it is to point to the next location of its type. The words `of its type' hold significance here. A pointer to a char on incrementing goes one byte further, since a char is a 1-byte entity. A pointer to an int points 2 bytes further, as an int is a 2-byte entity. Also, a pointer by itself is always a 2-byte entity, so incrementing a pointer to a pointer would advance you by 2 bytes.

Having convinced ourselves that p now stores 6022, we go on to evaluate the expression further. *p signifies contents of 6022, i.e. 4010. **p means value at this address, i.e. value at 4010, which is the address 1010. The printf( ) prints the string at this address, which is "cone".

*--*++p + 3

p , presently contains 6022, which on incrementing becomes 6024. Value at this address is the address 4008, or in terms of s , s + 1 . On this the decrement operator -- works to give 4006, i.e. s . Value at 4006, or *( s ) is 1000. Thus the expression is now reduced to ( 1000 + 3 ), and what finally gets passed to printf( ) is the address 1003. Value at this address is a '\0', as at the end of every string a '\0' is inserted automatically. This '\0' is printed out as a blank by printf( ) .

*p[-2] + 3

The current address in p is 6024. *p[-2] can be thought of as *( *( p - 2 ) ) , as num[i] is same as *( num + i ) . This in turn evaluates as *( *( 6024 - 2 ) ) , i.e. *( *( 6020 ) ) , as p is a pointer to a pointer. This is equal to *( 4012 ) , as at 6020 the address 4012 is present. Value at 4012 is 1015, i.e. the base address of the fourth string, "please". Having reached the address of letter `p', 3 is added, which yields the address 1018. The string starting from 1018 is printed out, which comprises of the last three letters of "please", i.e. `ase'.

p[-1][-1] + 1

The above expression can be thought of as *( p[-1] - 1 ) + 1, as num[i] and *( num + i ) amounts to the same thing. Further, p[-1] can itself be simplified to *( p - 1 ) . Hence we can interpret the given expression as *( *( p - 1 ) - 1 ) + 1 . Now let us evaluate this expression.

After the execution of the third printf( ) , p still holds the address 6024. *( 6024 - 1 ) gives *( 6022 ) , i.e. address 4010. Therefore the expression now becomes *( 4010 - 1 ) + 1 . Looking at the figure you would agree that 4010 can be expressed as s + 2 . So now the expression becomes *( s + 2 - 1 ) + 1 or *( s + 1 ) + 1 . Once again the figure would confirm that *( s + 1 ) evaluates to *( 4008 ) and *( 4008 ) yields 1004, which is the base address of the second string "green". To this, 1 is added to yield the address of the first element, `r'. With this as the starting address, printf( ) prints out what is remaining of the string "green".

What will be the output of the following program

main( )

{

char str[ ] = "For your eyes only" ;

int i ;

char *p ;

for ( p = str, i = 0 ; p + i <<= str + strlen ( str ) ; p++, i++ )

printf ( "%c", *( p + i ) ) ;

}

Output
Fryu ysol

Explanation


Figure 2

The for loop here hosts two initialisations and two incrementations, which is perfectly acceptable. However, there must always be a unique test condition. In the initialisation part, p is assigned the base address of the string, and i is set to 0. Next the condition is tested. Let us isolate this condition for closer examination.

p + i <<= str + strlen ( str )

Since length of str[ ] is 18, str + strlen ( str ) would give the address of '\0' present at the end of the string. If we assume that the base address of the string is 4001, then the address of '\0' would be 4019. Since p has been assigned the base address of the string, in the first go, p + 0 would yield 4001. Since this is less than 4019, the condition holds good, and the character present at the address ( p + 0 ) , i.e. `F', is printed out. This can be understood better with the aid of the Figure 2. After this, both p and i are incremented, so that p contains 4002 and i contains 1, and once again the condition in the for loop is tested. This time ( p + i ) yields 4003, whereas the expression str + strlen ( str ) continues to yield 4019. Therefore again the condition is satisfied and the character at address 4003, i.e. `r' gets printed. Likewise, alternate elements of the string are outputted till i is 8, corresponding to which `l' is printed. Now, when p and i are incremented one more time, the test condition evaluates to:

p + i <<= str + strlen ( str )
4019 <<= 4019

The 18th element of str is of course the '\0', which is also printed out as a blank. On further incrementation of p and i , control snaps out of the for and the program execution is terminated.

Pointers And Functions

Every type of variable with the exception of register, has an address. we have seen how we can reference variable of type char, int, float etc. through their addresses - that is by using pointers. Pointers can also point to C functions. And why not? C functions have addresses. If we know the function's address we can point to it, which provides another way to evoke it. Let us see how this can be done.

main( )

{

int display( ) ;

printf ( "\nAddress of function display is %u",display ) ;

display( ) ; /* usual way of invoking a function*/

}

display( )

{

printf ( "\n Long live viruses!!" ) ;

}

The output of the program would be:
Address of function display is 1125

Long live viruses!!

Note that to obtain the address of a function all that we have to do is to mention the name of the function, as has been done in printf( ) statement above. This is similar to mentioning the name of the array to get its base address.

Now let us see how using the address of a function we can manage to invoke it. This is shown in the program given below:

/* Invoking function using pointer to a function */

main( )

{

int display( ) ;

int ( *func_ptr )( ) ;

func_ptr = display ; /* assign address of function */

printf ( "\nAddress of function display is %u", func_ptr ) ;

( *func_ptr )( ) ;

/* invokes the function display( ) */

}

display( )

{

printf ( "\nLong live viruses!!" ) ;

}

The output of the program would be:
Address of function display is 1125

Long live viruses!!

In main( ) we declare the function display( ) as a function returning an int. But what are we to make of the declaration,

int ( *func_ptr )( ) ;

that comes in the next line? We are obviously declaring something which, like display( ), will return an int. But what is it? And why is *func_ptr enclosed in parentheses?

If we glance down a few lines in our program, we see the statement,

func_ptr = display ;

So we know that func_ptr is being assigned the address of display( ) . Therefore, func_ptr must be a

pointer to the function display( ).

Thus, all that the declaration

int ( *func_ptr )( ) ;

means is, that func_ptr is a pointer to a function, which returns an int. And to invoke the function we are just required to write the statement,

( *func_ptr )( ) ;

As we have seen, we can have an array of pointers to a int, float, string and structure similarly we can have an array of pointers to a function. It is illustrated in following program.

main( )

{

int ( *p [ 3 ] ) ( int, float ) ;

int i ;

void fun1 ( int , float ) ;

void fun2 ( int , float ) ;

void fun3 ( int , float ) ;

clrscr( ) ;

p [ 0 ] = fun1 ;

p [ 1 ] = fun2 ;

p [ 2 ] = fun3 ;

for ( i = 0; i <= 2; i++ )

( *p [ i ] ) ( 10, 3.14 ) ;

getch( ) ;

}

void fun1 ( int a, float b )

{

printf ( "\na = %d b = %f",a, b ) ;

}

void fun2 ( int c, float d )

{

printf ( "\nc = %d d = %f",c, d ) ;

}

void fun3 ( int e, float f )

{

printf ( "\ne = %d f = %f",e, f ) ;

}

In the above program we take an array of pointers to function int ( *p[3] ) ( int, float ) We store the addresses of three function f1( ), f2( ), f3( ) in array ( int *p[ ] ). In for loop we consecutively call each function using their addresses stored in array.

The output of the program would be:

i = 10 j = 3.14
a = 10 b = 3.14
x = 10 y = 3.14

Pointers And Arrays

An array is a collection of similar elements stored in adjacent memory locations.

int a[] = { 10, 13, -24, -35, 67 } ;

float b[] = { 1.2, 3.44, -5.44, 6.7, 8.9 } ;

long int c[25] ;

If an array is defined and initialized at the same place mentioning its dimension is optional.

If similarity and adjacency considerations are met we can build an array of anything, like say, an array of doubles, an array of structures, an array of pointers etc.

Size of an array is sum of sizes of individual elements of an array.

Base address of an array if address of zeroth element of the array.

Mentioning the name of the array fetches its base address.

int a[] = { 10, 13, -24, -35, 67 } ;

printf ( "%u %u", a, &a[0] ) ; // both would give base address

Array can be passed to a function element by element. Alternatively we can pass the entire array to a function at one shot.

int a[] = { 10, 13, -24, -35, 67 } ;

int i ;

// passing the array element by element

for ( i = 0 ; i <>

display ( a[i] ) ;

// passing entire array

show ( a, sizeof ( a ) / 2 ) ;

To pass an entire array we simply need to pass its base address. Whenever we pass an entire array to the function we also need to pass the size of the array, since the function has no way to find out how many elements are present in the array.

Array elements can be accessed using the subscript notation or the pointer notation.

int a[] = { 10, 13, -24, -35, 67 } ;

int i ;

// access using subscript notation

for ( i = 0 ; i <>

printf ( "%d", a[i] ) ;

// accessing using pointer notation

for ( i = 0 ; i <>

printf ( "%d", * ( a + i ) ) ;

Subscript notation is converted by the compiler into the pointer notation. Hence pointer notation would work faster since using it we would be able to save on the conversion time.

All four following expression are same:

a[i]

* ( a + i )

( * i + a )

i[a]

In the expression a[i]

Out of a and i one must be an integer. The other may either be an array name or a pointer.

An array of pointers is different than a pointer to an array.

int *a[10] ;

int ( *b )[10] ;

a is an array of pointers, whereas, b is pointer to an array. Incrementing a using a++ is illegal. On incrementing b it would start pointing to the next location of its type.

What would be the output of following program

main( )

{

int arr[ ] = { 0, 1, 2, 3, 4 } ;

int *ptr ;

for ( ptr = arr + 4 ; ptr >>= arr ; ptr-- )

printf ( "%d ", arr [ ptr - arr ] ) ;

}

Output
4 3 2 1 0

Explanation
A picture is worth a thousand words. Going by this dictum, the following figure 1 should add clarity to your understanding of the program.


Figure 1.

Now things are getting really complicated, as the printf( ) would justify. Let us begin with the for loop. Firstly ptr is assigned the address 6012, the address of the fourth integer from the base address. Since this address is greater than the base address, the condition is satisfied and the control reaches printf( ) . What does arr [ ptr - arr ] evaluate to? ptr - arr means 6012 - 6004 , which yields 4, and hence arr[4] prints out the fourth element of the array. Then ptr-- reduces ptr to 6010. Since 6010 is greater than the base address 6004, the condition is satisfied and once again the control reaches the printf( ) . This time ptr - arr becomes 6010 - 6004 , i.e. 3. Thus arr[3] prints out 3. This process is repeated till all the integers in the array have been printed out. Possibly an easier way of understanding the expression ptr - arr would be as follows. Suppose ptr contains 6012 and arr contains 6004. We can then view the subtraction as ( arr + 4 - arr ) , since ptr is nothing but arr + 4 . Now I suppose its quite logical to expect the result of the subtraction as 4.

What would be the output of following program

main( )

{

static int a[ ] = { 0, 1, 2, 3, 4 } ;

static int *p[ ] = { a, a + 1, a + 2, a + 3, a + 4 }

int **ptr = p

printf ( "\n%u %d", a, *a )

printf ( "%u %u %d", p, *p, **p )

printf ( "\n%u %u %d", ptr, *ptr, **ptr ) ;

}

Output
6004 0
9016 6004 0
9016 6004 0

Explanation
Look at the initialisation of the p[ ] . During initialisation, the addresses of various elements of the array a[ ] are stored in the array p[ ] . Since p[ ] contains addresses of integers, it has been declared as an array of pointers to integers. Figure 2 shows the content a[ ] and p[ ] . In the variable ptr , the base address of the array p[ ] , i.e. 9016 is stored. Since this address is the address of p[0] , which itself is a pointer, ptr has been declared as pointer to an integer pointer. Let us understand the printf( ) now. The first printf( ) is quite simple. printf ( "\n%u %d", a, *a ) ; It prints out the base address of the array a[ ] and the value at this base address.


Figure 2

Looking at the figure 2, this would turn out to be 6004 and 0. When you execute the program, the address may turn out to be something other than 6004, but the value at the address would be surely 0.

Now look at the second printf( ) .
printf ( "\n%u %u %d", p, *p, **p ) ;

Here p would give the base address of the array p[ ] , i.e. 9016; *p would give the value at this address, i.e. 6004; **p would give the value at the address given by *p , i.e. value at address 6004, which is 0. Now onto the last printf( ) .

printf ( "\n%u %u %d", ptr, *ptr, **ptr ) ;

Here ptr contains the base address of the array p[ ] , i.e. 9016; *ptr would give the value at this address, i.e. 6004; **ptr would give the value at the address given by *ptr , i.e. value at address 6004, which is 0.

What would be the output of following program

main( )

{

static int a[ ] = { 0, 1, 2, 3, 4 } ;

static int *p[ ] = { a, a + 1, a + 2, a + 3, a + 4 } ;

int **ptr = p ;

ptr++ ;

printf ( "\n%d %d %d", ptr - p, *ptr - a, **ptr ) ;

*ptr++ ;

printf ( "\n%d %d %d", ptr - p, *ptr - a, **ptr ) ;

*++ptr ;

printf ( "\n%d %d %d", ptr - p, *ptr - a, **ptr ) ;

++*ptr ;

printf ( "\n%d %d %d", ptr - p, *ptr - a, **ptr ) ;

}

Output
1 1 1
2 2 2
3 3 3
4 4 4

Explanation
Figure 3 would go a long way in helping to understand this program.

Here ptr has been declared as a pointer to an integer pointer and assigned the base address of the array p[ ] , which has been declared as an array of pointers. What happens when ptr++ gets executed? ptr points to the next integer pointer in the array p[ ] . In other words, now ptr contains the address 9018. Now let us analyse the meaning of ptr - p , *ptr - a and **ptr .

ptr - p

Since ptr is containing the address 9018, we can as well say that ptr is containing the address given by p + 1 . Then ptr - p is reduced to ( p + 1 - p ) , which yields 1.

*ptr - a ;

*ptr means value at the address contained in ptr . Since ptr contains 9018, the value at this address would be 6006. Now 6006 can be imagined as ( a + 1 ) . Thus the expression becomes ( a + 1 - a ) , which is nothing but 1.

**ptr

ptr contains 9018, so *ptr yields 6006, and hence **ptr becomes *( 6006 ) , which yields 1.

Thus the output of thefirst ; printf( ) becomes 1 1 1.

Take a deep breath and then begin with the analysis of *ptr++ . Here * and ++ both are unary operators. Unary operators have an associativity of right to left, hence ++ is performed before * . ++ increments ptr such that ptr now contains 9020. Then *( 9020 ) is performed, which gives the value at 9020. But since this value is not assigned to any variable, it just gets ignored. Now with ptr containing 9020, let us once again analyse the expressions ptr - p , *ptr - a and **ptr .


Figure 3.

ptr - p

Since ptr contains 9020, it can be visualised as ( p + 2 ) . Thus ptr - p would become ( p + 2 - p ) , which gives 2.

*ptr - a

*ptr would give value at address 9020, i.e. 6008, which is nothing but the address given by a + 2 . Thus the expression becomes ( a + 2 - a ) , which gives 2.

**ptr

*ptr gives the value at address 9020, i.e. 6008, and *( 6008 ) gives the value at 6008, i.e. 2.

I hope your confidence is building and you are ready to meet head on the expression *++ptr . Here, since ++ precedes ptr , firstly ptr is incremented such that it contains the address 9022, and then the value at this address is obtained. Since the value is not collected in any variable, it gets ignored. Now having cooked enough pointer stew you can easily imagine that the output of the third printf( ) would be 3 3 3.

Finally, let us understand the expression ++*ptr . Here obviously, the priority goes to the * . Thus, this expression increments the value given by *ptr . Since ptr contains 9022, *ptr gives value at 9022, i.e. 6010. This value is incremented to 6012.

So p[3] now contains 6012, whereas value of ptr remains stationary at 9022. Let us now analyse the expressions ptr - p , *ptr - a and **ptr .

ptr - p

ptr contains 9022, therefore ptr can be imagined as ( p + 3 ) . Thus ( ptr - p ) becomes ( p + 3 - p ) , which yields 3.

*ptr - a

*ptr yields 6012 which can be thought of as ( a + 4 ) . Thus the expression is reduced to ( a + 4 - a) , which yields 4.

**ptr

*ptr yields 6012, therefore **ptr would yield the value at *ptr , or the value at 6012, which is >4.