This isn't a conspiracy to drive you crazy; you need exposure to this for more interesting things to make sense.
It's time for us to get into some more advanced programming . Trying to solve more interesting problems with cruder techniques results in poorly structured code and overly complex functions which will be more difficult for you to design, develop and debug. Learning more advanced techniques will also make solving problems of the kind you have already worked on a lot easier.
For the head of a linked list or top of a tree (which we'll come to later), the object to be manipulated is a pointer itself.
As you have to modularise the code that does this, i.e. having a function which changes the the node which is at the head of a list, or at the top of a tree, the pointer which makes the tree or list accessible becomes part of the object to be changed by a function. Passing an ordinary variable as a parameter so a function can change it requires a pointer to that variable. We say this variable is passed by reference and not by value. When a pointer has to be passed by reference and not by value so a function can change it, the function parameter has to be a pointer to a pointer.
Another kind of problem this solves is allowing more flexible space allocations for 2 dimensional arrays, when you don't know the sizes of records or how many records are needed at compile time, or where not all records are of the same size and you want to avoid memory wastage.
The following program which inputs command line parameters is similar to the Unix or MSDOS echo command utility:
#include <stdio.h>
int main(int argc, char *argv[]){
int i;
for(i=0;i<argc;i++)
printf("%s ",argv[i]);
printf("\n");
return 0;
}
We could also have written char *argv[] as char **argv . This means that what is passed to the main function is an array of command line argument string addresses, in other words the address of a 2D char array.
Running this from the command line providing the program with extra arguments on the Linux command line:
[rich@saturn c]$ ./argcargv this that another ./argcargv this that another
The program prints out its arguments. To make this more like the echo command, you would start printing at argument 1 not argument 0. The MS-DOS command line works with program arguments sent to the main function as strings in a similar manner.
The 'C' language allows programs to be parameterised by enabling operating systems to pass a set of strings as input to the main function. argc is set to the number of strings passed, and argv is the address of the 2D array of strings. By convention argv[0] is the address of the path used to execute the program and the other arguments are additional parameters provided when the program is executed.
/* program to demonstrate use of pointers to pointers
* in connection with a 2D array of strings,
* and use of a NULL pointer as a sentinel to
* end the list of pointers. Richard Kay, Jan 06 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNAMESIZE 50
char **get_names(void); /* inputs a set of names */
void print_names(char **names); /* prints set of names */
void sort_names(char **names); /* sorts names in 2D array */
void free_names(char **names); /* frees memory used for names */
int main(void){
/* test code for other functions */
char **names;
names=get_names();
sort_names(names);
printf("\nThe sorted names are:\n");
print_names(names);
free_names(names);
return 0;
}
char **get_names(void){
/* inputs names into dynamically allocated storage */
char **names,buff[MAXNAMESIZE];
int num,i,lenname;
printf("how many names ?\n");
scanf("%d",&num);
fflush(stdin);
/* allocate space for array of pointers plus NULL terminator */
names=(char**)malloc(sizeof(char*)*(num+1));
printf("OK, enter %d names\n",num);
for(i=0;i<num;i++){
scanf("%s",buff); /* input name */
lenname=strlen(buff); /* measure name length */
names[i]=(char*)malloc(lenname+1); /* alloc space */
strcpy(names[i],buff); /* copy name to allocated space */
}
names[num]=NULL; /* sentinel to mark end of list */
return names; /* space for names is allocated by malloc
so is not automatically freed */
}
void print_names(char **names){ /* prints set of names */
char *name;
int i=0;
for(i=0;names[i];i++) /* loop terminates at NULL sentinel */
printf("%s\n",names[i]);
}
void sort_names(char **names){
/* sorts NULL terminated array of strings
* using bubble sort algorithm */
int i,j=0,num=0;
char *temp;
/* count names */
while(names[num++]);
num--; /* num indexes last name */
for(j=1;j<=num;j++) /* outer loop */
for(i=0;i<num-j;i++) /* inner loop */
if(strcmp(names[i],names[i+1])>0){
/* swap pointers */
temp=names[i];
names[i]=names[i+1];
names[i+1]=temp;
}
}
void free_names(char **names){ /* frees all storage for names */
int i;
for(i=0;names[i];i++) /* loop ends at NULL */
free(names[i]);
free(names);
}
[rich@saturn ptrptr]$ ./ptrptr how many names ? 4 OK, enter 4 names Peter Anabel Richard Mohammed The sorted names are: Anabel Mohammed Peter Richard
The following stack implementation doesn't use a typedef to mask the fact the pop() and push() functions are using a pointer to the stack head pointer to call the latter by reference, i.e. to change it outside these functions. We got around this another way in our more general linked list applications by keeping a dummy node at the head of the list.
/* program to demonstrate use of pointers to pointers
* in connection with modular use of addresses as objects.
* Richard Kay, Jan 2006 */
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
typedef struct stack {
DATA d;
struct stack *next;
} STACK;
DATA pop(STACK **s); /* removes and returns top record on stack s */
void push(STACK **s, DATA d); /* puts record d onto stack s */
int main(void){
STACK *s=NULL;
char c,test[]="tset a si sihT"; /* this is a test reversed */
int i;
printf("%s\n",test);
/* push test string into stack */
for(i=0;test[i];i++){
push(&s,(DATA)test[i]);
}
/* pop and print chars from stack */
while(s){
c=(char)pop(&s);
putchar(c);
}
putchar('\n');
return 1;
}
DATA pop(STACK **s){
/* removes and returns top record on stack s */
STACK *oldtop,*newtop;
DATA da;
oldtop=*s; /* make oldtop thing pointed at by s */
if(!oldtop){
fprintf(stderr,"can't pop empty stack!\n");
exit(1);
}
da=oldtop->d;
newtop=oldtop->next;
*s=newtop; /* make thing pointed at by s the new top */
free(oldtop); /* free space used by popped node */
return da;
}
void push(STACK **s, DATA da){
/* puts record d onto stack s */
STACK *oldtop, *newtop;
oldtop=*s;
/* create new stack node and insert at list head */
newtop=(STACK*)malloc(sizeof(STACK));
newtop->d=da;
newtop->next=oldtop;
/* update list head */
*s=newtop; /* make thing pointed at by s the new top */
}
Here is the output:
[rich@saturn ptrptr]$ ./stack tset a si sihT This is a test
| Single Variable | Array Variable | Pointer Variable | |
|---|---|---|---|
| Declaration | int i; | char str[10]; | NODE *ptr,*head; |
| Expression | i=2*4; | n/a | ptr=(NODE*)malloc(sizeof(NODE)); |
| Call by value | j=square(i); | n/a | print_list(ptr); |
| Call by reference | swap(&i,&j); | j=strlen(str); | fill_list(&head); |
| Read only parameter | int square(int i); | int strlen(const char str[]); | void print_list(NODE *ptr); |
| Read/Write parameter | void swap(int *i, int *j); | getstring(char str[]); | void fill_list(NODE **ptr); |
A different approach to achieving more flexible communication through function arguments is used by printf() . The prototype for printf indicates from 0 to many parameters of unstated type after the first format string parameter:
int printf(const char *format, ...);
We already know that the sequence and types of any parameters after the first are specified through escapes such as %d, %s, %.2f etc. within the format string, e.g:
printf("Value of pi to 5 decimal places is %.5f",3.14159);
Being able to have variable parameter lists allows for polymorphism, i.e. for a function call to have more than one form. You may have seen this in object oriented languages such as Java, where the version of a method called depends upon the sequence of parameters used.
In 'C' this facility is made available through the stdargs.h header. va_list provides a type for declaring an argument pointer. va_start() initialises the variable argument pointer to the first parameter. va_arg() is passed the type of the next argument, and returns its value.
The following program tests a function myprintf() which provides a simplified wrapper around calls to putchar() and printf() functions, to demonstrate how variable length and type parameters can be handled.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdarg.h> /* facilities for variable length argument lists */
/* This program is a simplified version of the similar
* program in Kernighan and Ritchie "The 'C' Programming
* Language, 2e page 156 */
void myprintf(char *fmt, ...); /* var length arg list function */
int main(void){
myprintf("hello myprintf world!\n");
myprintf("An escaped percent: %%\n");
myprintf("An integer: %d\n",2*3);
myprintf("A float: %f\n",sinf(2*3.14159/12)); /* sin of 30 degrees */
myprintf("An embedded string: %s\n","Hello string world");
myprintf("Int %d, Float %f, String %s\n",42,10.0/3,"Hello");
return 0;
}
void myprintf(char *fmt, ...){
/* var length arg list function similar to printf() */
char *s;
float f;
int i,j,lenfmt;
va_list ap; /* argument pointer */
va_start(ap,fmt); /* make ap point to first unnamed argument */
lenfmt=strlen(fmt);
for(j=0;j<lenfmt;j++){
if(fmt[j]!='%'){
putchar(fmt[j]);
} else {
j++;
if(fmt[j]=='d'){
i=va_arg(ap,int);
printf("%d",i);
} else if(fmt[j]=='f'){
f=(float)va_arg(ap,double);
printf("%f",f);
} else if(fmt[j]=='s'){
s=va_arg(ap,char*);
while(*s)
putchar(*s++);
} else
putchar(fmt[j]);
}
}
}
Running this program generated the following output:
[rich@saturn ptrptr]$ ./myprintf hello myprintf world! An escaped percent: % An integer: 6 A float: 0.500000 An embedded string: Hello string world Int 42, Float 3.333333, String Hello