# Fortran 90 & 95 Array and Pointer Techniques (PDF)

By Loren P. Meissner

Available in PDF format only for $10.00

### Erratum

On page 21, the loop index J should have upper bound N instead of N+1, and the inner loop index K should have upper bound N+1 instead of N.

Here is the preface:

### Preface

This book covers modern Fortran array and pointer techniques, including facilities provided by Fortran 95, with attention to the subsets e-LF90 and F as well. It provides coverage of Fortran based data structures and algorithm analysis.

The principal data structure that has traditionally been provided by Fortran is the array. Data structuring with Fortran has always been possible - although not always easy: one of the first textbooks on the subject (by Berztiss, in 1971) used Fortran for its program examples. Fortran 90 significantly extended the array features of the language, especially with syntax for whole arrays and array sections and with many new intrinsic functions. Also added were data structures, pointers, and recursion. Modern Fortran is second to none in its support of features required for efficient and reliable implementation of algorithms and data structures employing linked lists and trees as well as arrays.

Examples shown in this book use some features of Fortran 95, notably derived type component initialization, pointer initialization with null, and pure functions. Electronically distributed program examples include the Fortran 95 versions printed in the book, as well as alternative versions acceptable to the Fortran 90 subsets e-LF90 and F. Each of these subsets supports all essential features of Fortran 90 but omits obsolete features, storage association, and many redundancies that are present in the full Fortran language; furthermore, they are available at a very reasonable price to students and educators. Information concerning the F subset is available from:

The Fortran Company 6025 N. Wilmot Road Tucson, Arizona 85750 +1-877-355-6640 (voice & fax) http://www.fortran.com/F

The programming style used in this book, and in all of the electronically distributed variant versions of the programming examples, is close to that required by F (the more restrictive of the two subsets). F version examples conform to the "common subset" described in essential Fortran 90 & 95: Common Subset Edition, by Loren P. Meissner (Unicomp, 1997), except that short-form read and print statements replace the more awkward form that common subset conformance requires. The e-LF90 version examples incorporate extensions described in Appendix C of essential Fortran, namely: initialization and type definition in the main program, simple logical if statements, do while, and internal procedures. Fortran 95 version examples (including those printed in the text) do not employ any further extensions except for facilities that are new in Fortran 95. All versions of the examples have been tested; the Fortran 95 versions were run under DIGITAL Visual Fortran v 5.0c: see .

Bill Long, Clive Page, John Reid, and Chuckson Yokota reviewed earlier drafts of this material and suggested many improvements.

Here is the table of contents:

### Table of Contents

Contents

Preface

Chapter 1 Arrays and Pointers 1

1.1 WHAT IS AN ARRAY? 1

Subscripts

Multidimensional Arrays

Arrays as Objects

Whole Arrays and Array Sections

Whole Array Operations

Elemental Intrinsic Functions

Array Sections

Array Input and Output

Standard Array Element Sequence

Vector Subscripts

1.2 ARRAY TECHNIQUES 10

Operation Counts and Running Time

Operation Counts for Swap Subroutine

The Invariant Assertion Method

Smallest Element in an Array Section

Operation Counts for Minimum_Location

Search in an Ordered Array

Linear Search in an Ordered Array

Binary Search in an Ordered Array

Operation Counts for Binary_Search

Crout Method for Linear Systems

1.3 POINTERS 22

The Pointer Attribute

Association Status

Automatic Dereferencing

The deallocate Statement

Storage for Pointers and Allocated Targets

Management of Allocated Targets

Pointers as Derived Type Components

Pointers with Arrays

Chapter 2 Introduction to Sorting 28

Computer Sorting

Operation Counts for Sort_3

2.1 SORTING BY SELECTION 30

Operation Counts for Selection Sort

Sorting an Array of Structures

Selection during Output

Duplicate Keys

Selection Sort is not Stable

2.2 SORTING BY INSERTION 38

Straight Insertion

Operation Counts for Straight Insertion

Initially Ordered Data

Straight Insertion Is Stable

Insertion Sort with Pointers

Insertion during Input

Expanding Array

Binary Insertion

Binary Insertion Is Not Stable

Operation Counts for Binary Insertion

2.3 SHELL SORT 48

Operation Counts for Shell Sort

Shell Sort with Array Sections

2.4 HEAPSORT 50

Binary Trees (Array Representation) and Heaps

The Procedure Peck

Building the Heap by Chain Insertion

Sorting the Heap by Selection

Operation Counts for Heapsort

2.5 OPERATION COUNTS FOR SORTING: SUMMARY 61

Sorting Methods Described So Far (Slower to Faster)

Chapter 3 Recursion and Quicksort 63

3.1 RECURSION 63

Recursion Compared with Iteration

A Good Example of Recursion: Towers of Hanoi

A Bad Example of Recursion: The Fibonacci Sequence

Application: Adaptive Quadrature (Numerical Integration)

Application: Recursive Selection Sort

Tail Recursion vs Iteration

Printing a List Forward

Factorial

3.2 QUICKSORT 72

Recursive Partitioning

Quicksort is Unstable for Duplicates

Choosing the Pivot

The Cutoff

Testing a Quicksort Implementation

Storage Space Considerations

Quicksort Operation Counts

Chapter 4 Algorithm Analysis 80

4.1 WHAT IS AN ALGORITHM? 80

Computer Algorithms

4.2 WHAT MAKES A GOOD ALGORITHM? 81

>From Thousands to Millions of Data Items

Operation Counts for Sorting

4.3 ASYMPTOTIC ANALYSIS 83

The Role of Constants

The Complexity of an Algorithm: Big Oh

Complexity of Sorting Methods

4.4 MATHEMATICAL INDUCTION 87

Chapter 5 Linked Lists 88

5.1 LINKED LIST NODE OPERATIONS 88

Create List

Insert Target Node

Delete Target Node

Print Target Node

Modify Target Node

5.2 OPERATIONS ON WHOLE LINKED LISTS 92

Making a Linked List by Insertion at the RootPrint List

Delete List

Searching in a Linked List

Maintaining a Large Ordered List

5.3 PROCESSING LINKED LISTS RECURSIVELY 95

5.4 LINKED LISTS WITH POINTERS TO POINTERS 99

5.5 APPLICATIONS WITH SEVERAL LINKED LISTS 104

Multiply Linked Lists

5.6 LINKED LISTS VS. ARRAYS 105

Array Implementation

Unordered Array

Ordered Array

Linked List Implementation

Unordered Linked List

Ordered Linked List

Summary

Chapter 6 Abstract Data Structures 107

6.1 STACKS 107

Applications of Stacks

Depth-First Search in a Graph

Stack Operations

Evaluating a Postfix Expression

Stacks and Recursion

Recursive Depth-First Search

Reversing a List

Abstraction, Encapsulation, and Information Hiding

Stack as an Object

Array Implementation of Stack

Linked List Implementation of Stack

A Stack of What?

Generic Stack Module

Stack Objects

6.2 QUEUES 122

Queue Objects

Linked List Implementation of Queue

Array Implementation of Queue

Special Considerations for High Efficiency

Chapter 7 Trees 131

7.1 BINARY SEARCH TREES 131

The Balance Problem

7.2 AVL TREES 135

Rotating a Subtree

7.3 B-TREES 139

7.4 SKIP LISTS 143

7.5 COMPARISON OF ALGORITHMS 148

Index