Pointers are useful in building dynamic memory structures, such as linked lists and trees. The following examples demonstrate how pointers are used to build several types of dynamic structures. The purpose of these examples is to illustrate how pointers are used. As such, they may not represent the “best” or most efficient way to accomplish a given task. Readers interested in learning more about efficient use of data structures are urged to consult any good text on data structures.
Creating a Linked List
The following example uses pointers to create and manipulate a linked list. One procedure reads string input from the keyboard and creates a list of pointers to heap variables that have the strings as their values. Another procedure prints the strings, given the pointer to the beginning of the linked list. A third procedure uses a modified “bubble sort” algorithm to reorder the values so the strings are in alphabetical order.
Creating the List
The following program prompts the user to enter a series of strings from the keyboard. After reading each string, it creates a new heap variable containing a list element—an anonymous structure with two fields; one to hold the string data and one to hold a pointer to the next list element. Any number of strings can be entered. When the user is finished entering strings, the program can be exited by entering a period by itself at the “Enter string:” prompt.
The source code for this example can be found in the file ptr_read.pro in the examples/doc/language subdirectory of the IDL distribution. Run the example procedure by entering ptr_read at the IDL command prompt or view the file in an IDL Editor window by entering .EDIT ptr_read.pro.
Run the PTR_READ program by entering the following command at the IDL prompt:
ptr_read, first
Type a string, press Return, and the program prompts for another string. You can enter as many strings as you want. Each time a string is entered, PTR_READ creates a new list element with that string as its value.
For example, you could enter the following three strings (used in the rest of this example):
Enter a list of names.
Enter a period (.) to stop list entry.
Enter string: wilma
Enter string: biff
Enter string: cosmo
Enter string: .
The following figure shows one way of visualizing the linked list that we have created.
Printing the Linked List
The next program in our example accepts the pointer to the first element of the linked list and prints all the values in the list in order. To illustrate how the list is linked, we will also print the name of the heap variable that contains each element, and the name of the heap variable in the next field of that element.
The source code for this example can be found in the file ptr_print.pro in the examples/doc/language subdirectory of the IDL distribution. Run the example procedure by entering ptr_print at the IDL command prompt or view the file in an IDL Editor window by entering .EDIT ptr_print.pro.
If we run the PTR_PRINT program with the list generated in the previous example:
IDL> ptr_print, first
IDL prints:
<PtrHeapVar1>, named wilma, has a pointer to: <PtrHeapVar2>
<PtrHeapVar2>, named biff, has a pointer to: <PtrHeapVar3>
<PtrHeapVar3>, named cosmo, has a pointer to: <NullPointer>
A Simple Sorting Routine for the Linked List
The next example program takes a list generated by PTR_READ and moves the values so that they are in alphabetical order. The sorting algorithm used in this program is a variation on the classic “bubble sort”. However, instead of starting with the last element in the list and letting lower values “rise” to the top, this example starts at the top of the list and lets higher (“heavier”) values “sink” to the bottom of the list. Note that this is not a very efficient sorting algorithm and is shown as an illustration because of its simplicity. For real sorting applications, use IDL’s SORT function.
The source code for this example can be found in the file ptr_sort.pro in the examples/doc/language subdirectory of the IDL distribution. Run the example procedure by entering ptr_sort at the IDL command prompt or view the file in an IDL Editor window by entering .EDIT ptr_sort.pro.
To run the PTR_SORT routine with the list from our previous examples as input, enter:
ptr_sort, first
We can see the results of the sorting by calling the PTR_PRINT routine again:
ptr_print, first
IDL prints:
<PtrHeapVar1>, named biff, has a pointer to: <PtrHeapVar2>
<PtrHeapVar2>, named cosmo, has a pointer to: <PtrHeapVar3>
<PtrHeapVar3>, named wilma, has a pointer to: <NullPointer>
and we see that now the names are in alphabetical order.
Example Files: Using Pointers to Create Binary Trees
Two more-complicated example programs demonstrate using IDL pointers to create and search a simple tree structure.
These files, named idl_tree.pro and tree_example.pro, can be found in the examples/doc/language subdirectory of the IDL distribution. Run these example procedures by entering idl_tree or tree_example at the IDL command prompt or view the file in an IDL Editor window by entering .EDIT idl_tree.pro or .EDIT tree_example.pro.
To run the tree examples, enter the following commands at the IDL prompt:
.run idl_tree
tree_example
The TREE_EXAMPLE and IDL_TREE routines create a binary tree with ten nodes whose values are structures that contain random values for two fields, “Time” and “Data”. The TREE_EXAMPLE routine then prints the tree sorted by both time and data. It then searches for and deletes the nodes containing the fourth and second data values. The resulting 8-node trees are again printed in both time and data order.
A detailed explication of the TREE_EXAMPLE and IDL_TREE routines is beyond the scope of this section. Interested users should examine the files, starting with tree_example.pro, to see how the trees are created and searched.