To get the values back going from
smallest to largest, you trace the structure to the bottom of the smaller path,
assign the value, then go down the local larger path to the smallest value and
repeat the process. In the end all values are read in a sorted manner. The red
numbers in the figure represent the order in which the values must be assigned
to get the correct sorted list. To implement this the following steps have to be
- Look at the Makefile. It assumes
that there are a main_list.f90 and a
list.f90 program. The first is provided
- only a few holes you need to fill out - and a skeleton for the second is
- Look through the three files to see how the structure of the program is
- Random numbers are (again) provided using the build in function random_number.
- Define a type in list.f90 that
includes three entries: one real (value) and two pointers (smaller and
larger), as indicated in the figure above.
- Initialize the first structure using the first value in the array.
- Then build up the tree structure by adding new numbers to the list:
- Check relative numerical value against the value in the structure.
- Check the relevant pointer smaller/larger.
- If the pointer exist, then call the routine again, this time with the
address of smaller/larger and repeat the steps above.
- Notice that we are recursively calling the same routine until there
is a free space to open a new structure and place the given
- If the pointer is empty:
- Allocate a new structure.
- Add the value to this structure.
- Assign its address to the smaller/larger pointer in the parent
- Return back to the main routine.
- This tree structure does not allow for multiple identical values.
- Could easily be included by adding an integer variable counting the
number of repeated values.
- Also requires a small change to the reading
This is the type of program where it may be
difficult to predict how the flow structure behaves. It may therefore be useful
to use the debugger from last exercise to track the evolution of the program
while it runs.
The routine for reading the tree structure is included,
with a single small error. Check this part of the routine to make sure you know
how it works. Especially make sure you understand the way that it steps through
the routine to actually place the values in the correct order. Run the program
to check that it sorts the data correctly.
Using pointers and allocate
this way, is a typical approach in which one can create a program that can grow
in size without limits, especially if the full sort algorithm is repeated many
times. The problem is often that one does not clean up properly when dismissing
the tree structure. It is not enough to release the root pointer, as it only
releases the amount of data included in this part of the code, leaving the lower
level structures still hanging there, but without a change to access them.
Therefore address this type of programs with some care! Making sure that you do
the correct cleaning all the time.
When it is working, make the small
change such that it can read the data file data.bin, which contains one block of
data containing 1000 random numbers. Read these data into the program and sort
them. If you downloaded the fortran7.tgz file before the
14 October at 11pm, you have to download it again and extract an updated version
of the data.bin file again:
$ tar -zxvf fortran7.tgz
$Id: index.php,v 1.8 2009/10/14 21:21:18 kg Exp $ email@example.com