Fortran 90 & 95 Array and Pointer Techniques (PDF)

$10.00

Category:

Description

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
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

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.