Functions and pointers

21.01

We will recall and discuss
•	functions returning pointers,
•	pointers to functions, 
•	higher order functions.

Functions that return pointers:
When you declare
	elt* f(...);	
function f is a function that returns a pointer to something of type elt.

Linear Search returning a pointer to an element to be found.

elt* LinearSearch(elt toBeFound, elt* es, int lbnd, int ubnd) {
	int i;
	for (i = lbnd; i <= ubnd; i++)
		if (equalElts(*(es + i), toBeFound))
			return(es + i);
	return(NULL);
}

21.01

TABLE OF CONTENTS HC 21

21.02

Pointers to functions

21.02

StringCopy as a function that returns a pointer to char

	typedef char* String;
	String StringCopy(String dst, const String src) {
		char *p = dst;
		while(*p++ = *src++)
		   ;
		return(dst);
	}

Pointers to functions:
There is a pointer associated with each function. 
Logically this pointer points to the base address of the code of the function.
Actually the name of a function is a constant pointer in exactly
the same spirit as the name of an array is a constant pointer.
The declaration 
	double fun(double x);        // prototype of fun
	double fun(double x) {}      // definition of fun
	double (*funPtr) (double x); // ptr to function

21.01

TABLE OF CONTENTS HC 21

21.03

Syntax pointer to function

21.03

defines a function (fun: prototype and definition),
declares a pointer (funPtr) that might refer to the function fun,
the type of this pointer is double (*) (double)
and its name is funPtr.

Important note on syntax:
	double *funPtr (double x);
declares a function prototype!! The name of the function is funPtr and this 
function imports a double and returns a double, but
	double (*funPtr) (double x);
declares a pointer funPtr that can refer to any  function double f(double);

In general, 
if functon f has the following signature
	returnType f(formal_parameter_list)
then the corresponding pointer type pf is given by
	returnType (*)(formal parameter list)
and this type pf can be defined  explicitly by
	typedef returnType (*pf)(formal parameter list) 

21.02

TABLE OF CONTENTS HC 21

21.04

Intro higher-order functions

21.04

 
After the assignment
	funPtr = fun;
the pointer will indeed point to (the code of) the function fun.

The significance of pointer to function is that it allows functions to have
parameters that are functions again. Such functions are called higher-order
functions. They can be implemented without knowledge about the details of the
function(s) that they are supposed to execute!

Higher-order functions are introduced now by example.
Example 1: the function tabulate

	void tabulate(double (*f)(double), 
	              double lbnd, double ubnd, double delta) {
	   double x;
	   for (x = lbnd; x <= ubnd; x += delta)
	      printf("%12.8f\t%12.8f\n", x, (*f)(x));
	}

prints a table of values x against f(x), for x from lbnd to ubnd in steps delta,
for any function of type double f(double).
How?

21.03

TABLE OF CONTENTS HC 21

21.05

Function tabulate

21.05

Well let
	double test(double x) {
	   return(sqr(sin(x)) / log(x));
	}

denote the function that should be tabulated; then call

	tabulate(test, 2.0, 4.0, 0.1);

Syntax: ANCI C allows us to write
•	double f(double) for the function parameter double (*f)(double)
•	and in the code we can use f(x) instead of (*f)(x) 

Example 2: determine the square root for any real positive x
using the method of Newton:
	if y is an approximation to sqrt(x) 
	then (y + x/y)/2 is a better one.

	double newton(double x, double y) {
	   return((y + x/y) / 2);
	}

21.04

TABLE OF CONTENTS HC 21

21.06

Method newton

21.06

double theSqrtOf(double x, double eps, 
                 double f(double, double)) {
	double approx = x; // first approx to sqrt(x) is x itself
	while(fabs(x - approx * approx) > eps)
		approx = f(x, approx);
	return(approx);
}
Then use function newton in an actual call to theSqrtOf:
int main(void) {
	double pi = 4 * atan(1), 
	       sqrtPi;
	sqrtPi = theSqrtOf(pi, 1E-12, newton);
	printf("sqrt(pi) = %12.8f\n", sqrtPi);
}

Function parameters and the typedef mechanism (as discussed above):
	typedef double (*pf) (double, double); 
declares the type pf as pointer to function that returns a double
and imports two doubles. Using this new type pf we can now write

	double theSqrtOf(double x, double eps, pf f);
	// determine sqrt(x) within precision eps using function f

21.05

TABLE OF CONTENTS HC 21

21.07

Function zeroPoint

21.07

Example 3:
A zeropoint of a function f is a value x0 for which f(x0) = 0.
Determine the zero point of a function testFunction in an interval with
exactly one zero point according to any of the available methods that can
perform the job (brentMethod, ridderMethod, bisectionMethod, secantMethod).

	typedef double (*pf)(double) // pf: pointer to testFunction
	double testFunction(double); // prototype for testFunction
	double testFunction(double x) {     // actual testFunction
	   return(4*x*x*x - 16*x*x - x + 4);
	} 

	typedef double (*pzf)(pf, double, double); 
	//	pzf: pointer to a HOF with parameter pf!! 

	double secantMethod(pf, double, double, double);
	double secantMethod(pf f, 
	                    double lbnd, double ubnd, double eps) { 
	//	return zeropoint of function f 
	//	in interval [lbnd..ubnd] with precision eps 
	}

21.06

TABLE OF CONTENTS HC 21

21.08

and further ...

21.08

	double zeroPoint(pf, pzf, double, double, double);
	//	return zeropoint of function f using method m 
	    in interval [lbnd..ubnd] with precision eps 
	double zeroPoint(pf f, pzf m, 
	                 double lbnd, double ubnd, double eps) {
	   return(m(f, lbnd, ubnd, eps));       // actual code!! 
	}

int main(void) { 
	printf("zeroPoint of test using secant: %20.18f\n", 
	  zeroPoint(testFunction, secantMethod, 0.0, 1.0, 1E-10));
}
	
There is a lot more to say about higher-order functions:

•	The concept is powerfull and leads to clear, clean and concise code.
•	Read any textbook on functional programming (language Haskell).
•	Java did not inherit the concept of formal function parameters from C.
•	In Java anonymous inner classes are designed for this purpose.
•	In the discussion of lists and trees we will introduce and apply 
	higher-order functions again (processList and processTree).

21.07

TABLE OF CONTENTS HC 21

21.09

Standard elements (1)

21.09

A structure can be defined to contain members that are of type pointer to any 
type and if this type is again the same structure template the structure is 
called a selfreferential structure.

First define standard elements as structures that are build from key and data: 
key (K) is unique for an element and assists in searching for data (D).

	typedef ... keyType;  // user defined and comparable!
	typedef ... dataType; // user defined
	typedef dataType* dataPtr;

	struct elt {
	   keyType   key;
	   dataType  data;
	};
	typedef struct elt   eltType;
	typedef eltType*     eltPtr;

		           

21.08

TABLE OF CONTENTS HC 21

21.10

Standard elements (2)

21.10

An alternative to this type of element is a structure in which the 
second member is a pointer to the data (pD) instead of the data (D) itself:

	struct elt {
	   keyType   key;
	   dataPtr   data;
	};
	typedef struct elt   eltType;
	typedef eltType*     eltPtr;




	

21.09

TABLE OF CONTENTS HC 21

21.11

Standard nodes (1)

21.11

Secondly we define nodes that consist of a combination of an element
and one or more pointers to other nodes. The types xNode and xPtr are 
introduced (and for the moment x stands for list or stack or queue, etc.).

	struct node {
	   eltType     elt;
	   struct node* p1;
	   struct node* p2;
	   ...
	   struct node *pn;
	};
	typedef struct node   xNode;
	typedef xNode*        xPtr;

21.10

TABLE OF CONTENTS HC 21

21.12

Standard nodes (2)

21.12

An alternative to this type of node is a structure in which the first member is
a pointer to element (pE) instead of the element (E) itself:

	struct node {
	   eltPtr     eltP;
	   struct node* p1;
	   struct node* p2;
	   ...
	   struct node *pn;
	};
	typedef struct node   xNode;
	typedef xNode*        xPtr;
	

21.11

TABLE OF CONTENTS HC 21

21.13

Standard nodes (3)

21.13

 A second alternative to this type of node is a structure in which the first 
member is the key (K) and the second member a pointer to data (pD):

	struct node {
	   keyType     key;
	   dataPtr   dataP;
	   struct node* p1;
	   struct node* p2;
	   ...
	   struct node *pn;
	};
	typedef struct node   xNode;
	typedef xNode*        xPtr;

21.12

TABLE OF CONTENTS HC 21

21.14

Header nodes

21.14

Finally we define headernodes that consist of a combination of pointers that
give access to the datastructure and provide global information about the 
current status. As an example (slide 21.21) consider 

	struct xHeader {
	   xPtr   first;
	   xPtr   last;
	   int    size;
	};

which represents a header node that contains two access pointers, one to the 
first node and one to the last node and a member that is used 
to store the number of nodes currently present in the datastructure.

If no headernode is used we finish the declaration 
by a renaming of the type xPtr

	typedef xPtr x; // x stands for list stack or tree etc
	x   myX, yourX; // variables of type x
	

21.13

TABLE OF CONTENTS HC 21

21.15

Constructors (1)

21.15

If, on the other hand, headernodes are used, we finish the declaration as:

	typedef struct xHeader* x; // x stands for list stack tree
	x   myX, yourX;            //variables of type x
	
It is convenient to have constructors for elements and for nodes.

•	Constructor that returns an element:
	combine key and data into an element and return this element 

	eltType newElt(keyType k, dataType d) {
		eltType e;
		e.key = k; e.data = d;
		return(e);
	} 

•	Constructor that returns a pointer to an element element:

	eltPtr newElt(keyType k, dataType d) {
		eltPtr pE = (eltPtr)malloc(sizeof(eltType));
		pE->key = k; pE->data = d;
		return(pE);
	} 

21.14

TABLE OF CONTENTS HC 21

21.16

Constructors (2)

21.16

•	Constructor that returns a pointer to a node that contains element e:

	xPtr newNode(eltType e) {
		xPtr pN = (xPtr)malloc(sizeof(xNode));
		pN->elt = e;
		return(pN);
	} 

•	Constructor that returns a pointer to a node that contains pointer to e:

	xPtr newNode(eltPtr pE) {
		xPtr pN = (xPtr)malloc(sizeof(xNode));
		pN->eltP = pE;
		return(pN);
	} 

With the building blocks element and node we will construct several 
dynamic datastructures where nodes are linked together using pointers.
Dynamic: these datastructures can grow and shrink during execution of the 
program unlike static datastructures like arrays and structs where the size
has been fixed and memory is allocated during compile time.

21.15

TABLE OF CONTENTS HC 21

21.17

List: definition

21.17

The most convenient way to define the datatype LIST is inductively: thus
•	the list is empty, L=[ ], or
•	the list is not empty, L=[H:T] where
	H denotes the first node (often called the head) and 
	T denotes the remainder (often called the tail) of the list. 
•	An empty list has no head and no tail.
•	The tail of a non-empty list is a list.
Think about this definition!

The basic operations that define the datastructure LIST are collected below 
together with the axioms that must be satisfied. 
First we define the functions create, insert and delete:

•	The function create 
	creates a new and empty list: 
		create() = [ ]
•	The function insert 
	adds a new head (with element E) to an existing list: 
		insert(E,L) = [E:L]
•	The function delete 
	removes the head from an existing non-empty list: 
		delete(L) = T iff L = [E:T]

21.16

TABLE OF CONTENTS HC 21

21.18

List: axioms and C interface

21.18

Hence the axioms for the basic operations can be stated as:
	isEmpty(create())    = TRUE
	isEmpty(insert(E,L)) = FALSE

	head(create())       = ERROR (error in head: empty list)
	tail(create())       = ERROR (error in tail: empty list)
	delete(create())     = ERROR (error in delete: empty list)

	head(insert(E,L))    = E
	tail(insert(E,L))    = L
	delete(insert(E, L)) = L

A possible (incomplete) list interface in C:
	list createList();
	list destroyList(list L);    // YES!
	
	bool isEmptyList(list L);
	bool isFullList(list L);     // YES!
	int  sizeOfList(list L);

	list insert(eltPtr pe, list L);
	list delete(list L);

21.17

TABLE OF CONTENTS HC 21

21.19

More list operations

21.19

Other operations that might be of interest:

	dataPtr getData(keyType k, list L);
	list   setData(keyType k, dataPtr pd, list L);

	list copyList(list L);
	list revertList(list L);
	list sortList(list L);

	void traverseList(list L);
	list processList(list L, eltPtr f(eltPtr));
	...
	concat, merge, etc., etc.


Guided by the above considerations we can now declare a list in terms of 
listnodes which are linked to each other. Each listnode stores an element and 
at least one pointer. This pointer points to the next node. This basic design 
is called a Singly Linked List (SLL).

21.18

TABLE OF CONTENTS HC 21

21.20

List without header node

21.20

                           // SLL = Singly Linked List
                                // without header node 
	struct node {
	   eltPtr       elt;   // field to store pointer to element
	   struct node* next   // pointer to the next node
	};
	typedef struct node listNode;
	typedef listNode*   listPtr;
	typedef listPtr     list;

	list L;  // L is a variable of type list
             // L is a pointer to the first listNode (if any)
             
Very often it is convenient to introduce a header node that contains global 
information (size and one or more access pointers) about the list. 
In the next picture this design is shown graphically and the declaration that 
has been given can be read from it, nearly without further explanation. 
The last node in the list is characterized by having a next pointer that is 
equal to NULL.

21.19

TABLE OF CONTENTS HC 21

21.21

List with header node (SLL)

21.21

	struct node {
	   eltPtr       elt;  // field to store an element 
	   struct node* next  // pointer to the next node     };
	typedef struct node listNode;
	typedef listNode*   listPtr;
	
	struct header {
	   listPtr first, cur, last;
	   int     size;                                      };
	typedef struct header listHeader;
	typedef listHeader* list;

	list L;  // L is a variable of type list
	         // L is a pointer to the header node

21.20

TABLE OF CONTENTS HC 21

21.22

Empty list

21.22

Note the differences between an SLL with and without a header node. 
If no header node is used, the type list is defined as a pointer to a listnode,
otherwise it is defined as a pointer to a header node.
If L is a variable of type list then
•	if this is a list without header node 
	then L == NULL represents the empty list
•	if this is a list with a header node 
	then L->first == L->cur == L->last == NULL 
	and L->size == 0 represents the empty list!

Next we show how several important SLL operations
can be implemented. Here we have introduced a function call
	temp = newNode(pE); 
which takes a pointer to an element, allocates the node where pE is stored,
and returns a pointer to this node:

	listPtr newNode(eltPtr pe) {
	   listPtr temp = (listPtr)malloc(siseof(listNode));
	   temp->elt = pe;
	   temp->next = NULL;  // set the next field to NULL
	   return temp;
	}

21.21

TABLE OF CONTENTS HC 21

21.23

Insert in list (1)

21.23

The first operation is the basic insert operation in which an existing list gets
a new head. The important steps are indicated explicitly. If the SLL is defined
with a header node, the size field is updated in the epilogue.

21.22

TABLE OF CONTENTS HC 21

21.24

Insert in list (2)

21.24

 
The second operation treats an insert operation in which a new node is inserted
as the successor of the current node. 
The important steps are indicated explicitly. If the SLL is defined with a header
node the size field is updated in the epilogue. The case where the current node 
happens to be the last node is treated as a special case.

21.23

TABLE OF CONTENTS HC 21

21.25

Special cases for insert

21.25

This special case is treated in the next picture which deals with the insertion 
of a new last node. The case
	last == NULL 
is again a special case where the list is empty, prior to the insert operation.

21.24

TABLE OF CONTENTS HC 21

21.26

Delete from list

21.26

The basic delete operation is the deletion of the first node of the list:


and in the next delete operation we remove the successor of cur

21.25

TABLE OF CONTENTS HC 21

21.27

Variations on SLL: CSLL

21.27

REMARKS ON SLL: cheap and expensive operations ...
insert predecessor of cur, delete cur, delete predecessor of cur 
and in particular delete last node are expensive operations!

VARIATIONS ON SLL:
There exist several interesting variations on the SLL-theme that intend 
to solve the problem of expensive operations:

 •	Cyclic Singly Linked Lists (CSLL) see  SRC 

21.26

TABLE OF CONTENTS HC 21

21.28

Variations on SLL: DLL and CDLL

21.28

•	Doubly Linked Lists (DLL) see  SRC 



•	Cyclic Doubly Linked Lists (CDLL) see  SRC 

21.27

TABLE OF CONTENTS HC 21

21.29

TABLE OF CONTENT HC 21

TOC

TOC