Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ukma!uflorida!novavax!hcx1!bill From: bill@ssd.harris.com (Bill Leonard) Newsgroups: comp.lang.fortran Subject: Pointer examples and 8x Message-ID: Date: 16 Jun 89 17:20:46 GMT Sender: news@hcx1.UUCP Distribution: usa Organization: Harris Computer Systems Division Lines: 170 In article <6028@microsoft.UUCP> bobal@microsoft.UUCP (Bob Allison) writes: My second biggest problem is that it is an attribute. Bill Leonard, in email to members of the committee complained that it was awfully difficult to use this form of pointers to insert items in a linked list (at least, > I think that was the example), a fairly common usage of pointers. As I > recall, someone came back with a solution which was deemed "elegant" and > was implemented using recursion. Ugh! I just want to walk around > lists and stuff. Bill, could you post the problem again and see if > anyone else can come up with a solution which doesn't require retraining > everyone who has ever used pointers in any other language? Okay, here are my examples. I am wrote these in C, since that is the language that both has pointers as a data type and is one I use on a regular basis. Please excuse any minor programming errors -- the point is that 8x pointers cannot point to other pointers, nor can I have an array of pointers. I think these examples show why those two features are very important. NOTE: I know that you CAN implement these routines in 8x IF you make each pointer be a structure whose only field is the pointer. This is fine, if your purpose is to obscure what the code is doing. Also, there is a very good reason for only using _ONE_ pointer in the update example, rather than two: it is much more efficient. Any computer-science freshman can do it with two! Example 1: Updating a linked list. struct list_element { struct list_element * next ; int data ; } * list_header ; /* Routine delete removes a given element from the list. */ delete (key) int key ; { struct list_element ** update_ptr ; /* Pointer to the next field to be updated when an element is deleted. */ update_ptr = &list_header ; while (*update_ptr != NULL) { if ((*update_ptr)->data == key) { /* The list pointer pointed to by update_ptr now needs to point to the following element. Note that this works even if update_ptr is pointing to the list header. */ *update_ptr = (*update_ptr)->next ; return ; } update_ptr = &(*update_ptr)->next ; } } /* Routine insert inserts a new element before a given one. Assume the macro NEW allocates a new list element. */ insert (newkey, inskey) int newkey ; /* New key-value to insert. */ int inskey ; /* Key value of element that should immediately succeed the new one. */ { struct list_element ** update_ptr ; /* Pointer to the next field to be updated when the new element is inserted. */ struct list_element * new_element ; /* New list element pointer */ update_ptr = &list_header ; while (*update_ptr != NULL) { if ((*update_ptr)->data == inskey) { /* The list pointer pointed to by update_ptr now needs to point to the new element. The new element's next field needs to point to the element formerly referenced by *update_ptr. */ new_element = NEW() ; new_element->data = newkey ; new_element->next = *update_ptr ; *update_ptr = new_element ; return ; } update_ptr = &(*update_ptr)->next ; } fprintf (stderr, "Desired element not found\n") ; exit (1) ; } Example 2: Sparse matrix. /* This is an example of implementing a sparse matrix of integers. For simplicity, I show only the insertion routine, and I have assumed the number of rows is fixed. In many cases, the number of rows would be dynamic, and so the array of row-pointers would be a dynamic array, itself referenced by a pointer. Each row element represents a range of consecutive integers, which may be only a single integer (if high==low). The row elements are maintained in ascending order. */ struct row_element { struct row_element * next ; int low ; int high ; } ; struct row_element * (rows [NUM_ROWS]) ; /* Array of pointers to row headers. In 8x, this would have to be an array of structures whose sole element is a pointer. That introduces a lot of syntactic baggage that obscures rather than illuminates. */ /* Routine insert inserts a new element into the matrix, if it is not already there. For simplicity and brevity, I have not implemented all the special cases possible. */ insert (row, col) int row, col ; { struct row_element ** insert_ptr ; /* Pointer used for insertion. */ struct row_element * new_element ; /* Pointer to new element if needed */ insert_ptr = &(rows [row]) ; /* Search for the place to insert. */ while ( ((*insert_ptr) != NULL) && ((*insert_ptr)->high < col) ) { insert_ptr = &(*insert_ptr)->next ; } if (*insert_ptr == NULL) { /* We reached the end of the list. Create a new element. */ new_element = NEW() ; new_element->next = NULL ; *insert_ptr = new_element ; new_element->low = col ; new_element->high = col ; } else if ((*insert_ptr)->low < col) { /* The element is already in the list. Do nothing. */ ; } else if ((*insert_ptr)->low == col+1) { /* Extend this element backward. */ (*insert_ptr)->low = col ; } else { /* Create a new element and insert it. */ new_element = NEW() ; new_element->next = *insert_ptr ; *insert_ptr = new_element ; new_element->low = col ; new_element->high = col ; } } -- Bill Leonard Harris Computer Systems Division 2101 W. Cypress Creek Road Fort Lauderdale, FL 33309 bill@ssd.harris.com or hcx1!bill@uunet.uu.net