Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!csd4.milw.wisc.edu!uxc.cso.uiuc.edu!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.fortran
Subject: Re: Pointer examples and 8x
Message-ID: <18236@mimsy.UUCP>
Date: 23 Jun 89 06:49:39 GMT
References: <BILL.89Jun16132046@hcx2.ssd.harris.com> <158@unmvax.unm.edu>
Reply-To: chris@mimsy.umd.edu (Chris Torek)
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 96

[I deleted a `distribution: usa'.]

In article <158@unmvax.unm.edu> brainerd@unmvax.unm.edu (Walt Brainerd) writes:
>First, note that there is no need for pointers pointing to pointers.

(They are, however, sometimes convenient; see example below.  None of this
disputes jlg's point---in another article---that `convenient' and `appropriate'
are not always the same.)

>To show the contrast between the C program Bill wrote, the "walk" around
>version in Fortran 8x and the (Ugh!) elegant version using recursion
>even more, let's not pick the particularaly simple example in Bill's
>list insertion, but instead assume the list is to be maintained in
>ascending order.  If, for example, we are to insert the number 17,
>it must work if the list is empty, if all numbers are < 17, or if
>all numbers are > 17.  In this example, you have to make an insertion
>_before_ the node you find having a certain property. To do this,
>I think even nonfreshman need two pointers (a trailing pointer is needed)
>(but maybe someone else can do it with one)
>and the empty list is either a special case (Bill just printed an error mesg)
>or there must always be a dummy node in the list (I have arbitrarily chosen
>the latter).

An empty list need not (and should not, in general) be a special case.

[Code, including bugs corrected in later followups, deleted.  The
insert subroutine itself (that is, without the declarative preamble)
was 16 non-blank non-comment lines.  I counted only what was in the
referenced article, not anything in later corrections.]

For contrast, here is a correct version with a pointer that points
to a pointer, in Classic C.  (Changing it to New C [pANS C] requires
changing the argument list syntax, deleting two lines in the process.)

typedef int data_t;	/* any arithmetic type will do */

struct list {
	data_t	value;
	struct	list *next;
};

struct list *insert(head, newnode)
	struct list *head, *newnode;
{
	register struct list **p = &head;
	register data_t newvalue = newnode->value;

	for (p = &head; *p != NULL && (*p)->value < newvalue; p = &(*p)->next)
		/* void */;
	newnode->next = p;
	*p = newnode;
	return head;
}

The key to the whole thing is the ability to address the local parameter
`head', which is itself a pointer.  In the (empty) body of the `for' loop,
the following condition always holds:

	*p is not nil
		and
	*p points to a node whose value is less than the new value

The loop terminates when one of these conditions is false.  Thus,
either

	*p is nil
		or
	*p points to a node whose value is >= newvalue

(In no case is p itself ever nil.)  At that time, we make the new
node's `next' field be p (nil---the end marker---or something that
should follow).  In either case the list headed by newnode is properly
sorted, provided the input was properly sorted.  We then set *p
to newnode.  If *p was nil, this means that newnode->next is nil,
and that newnode->value must be >= all values in the list headed
by `head'.  If *p was not nil, we have two cases:

	*p aliases head
		or
	*p aliases head->next-> ... ->next

If *p aliases head, the assignment changes head so that newnode heads
the list, which is then properly sorted.  Otherwise, we know (by strong
induction) that the node whose next field is aliased by *p has a value
field which compares less than newnode->value.  The assignment then
replaces this `next' with newnode, and newnode's next is what this
node's next used to be, so again the list is properly sorted.  In
either case, the insert function returns the possibly modified head.

Note that the loop could use `<=' comparisons, and the proof would
still hold (with one change from `>=' to `>'), but if there were
several list elements with the same value, the new node would be
inserted after these elements, rather than before them.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris