Algorithms and Data Structures in F and Fortran
by R. A. Vowels (robin_v@bigpond.com)
ISBN 0-9640135-4-1
12 chapters, 487 pages.
This book was published by Unicomp in August 1999. An outline of the book and
the contents are shown below.
ALGORITHMS AND DATA STRUCTURES IN F AND Fortran emphasizes fundamentals of structured programming through study of F and Fortran 90/95. It is designed for a reader's second exposure to computer programming, whether it be through self-study or a course in computer science.
What is F? F is modern Fortran. F is Fortran 2003 with the old
error-prone Fortran constructs removed. So F contains the new free
source form, compulsory declarations, data structures,
program structures including select case and where, modules,
interface blocks, dynamic storage, recursion, array operations
including array sections and subscript triplets, and the new
built-in procedures including those for array processing,
string processing, and linked lists. F programs run under
Imagine1's F compiler that is available for a range of systems,
including Imagine1's excellent low-cost F development system for
the PC. F programs also run under standard Fortran compilers
(Fortran 90, Fortran 95, and Fortran 2003).
This book contains a detailed exposition on important
algorithms, some traditional, some new.
For most of these topics, no prior or special knowledge is assumed. Popular sort algorithms are examined: the Bubble Sort, Shell Sort, Heap Sort, Quicksort, and Hash Sort. Various search algorithms are studied: linear, binary, hash, binary search tree. The chapter on recursion commences with some short examples, and culminates with Quicksort and algorithms for space-filling curves. Algorithms for solving linear equations including tri-diagonal and banded systems (Gauss, Gauss-Siedel), matrix inversion, and roots of polynomials, are covered in detail. Algorithms for performing Fourier Transforms are included. The significant string search algorithms studied include the Knuth-Morris-Pratt, Rabin-Karp, Boyer-Moore, Baeza-Yates-Gonnet, and Baeza-Yates-Perleberg. Graphics algorithms for creating fractals and space-filling curves, for creating picture files (PCX and TIFF files), for reading a PCX file, and data compression and expansion, are provided. The chapter on numerical methods includes basic algorithms for integration, differentiation, root-finding, least squares approximation, interpolation, and for solving differential equations. The adventurous will find that the large bibliography includes many works appropriate for further reading, study, or research.
The book is not just algorithms. Additional F/Fortran topics are included: separate theme chapters are devoted to complex arithmetic, file processing, list processing (the extensive chapter includes binary search trees), text processing including string searching, and recursion.
Chapters can be studied in any order, as they are mostly independent. They can be selected at will according to the reader's interests.
The book is backed up by a comprehensive appendix on the built-in procedures, many with examples. There is also a summary of F/Fortran statements, and ASCII and EBCDIC reference tables. Comes with a floppy disc with the programs, subroutines, and functions from the book.
CONTENTS
<![CDATA[
1 Sorting 1
1.1 Cocktail-Shaker Sort 1
1.2 Double-Bubble Sort 3
1.3 Shell Sort 5
1.4 Heap Sort 9
1.5 Indirect Addressing 16
1.6 Hash Sort 19
1.7 Hash Sort (Version 2) 24
1.8 Sorting Structures 28
1.9 Sorting Structures, on Two Fields 29
2 Recursion 35
2.1 Factorials 35
2.2 Fibonacci Numbers 38
2.3 Multiplication 39
2.4 Greatest Common Divisor 40
2.5 Base Conversion 41
2.6 Quicksort 42
2.7 QuickSort Version 2 48
2.8 QuickSort Version 3 50
2.9 Sierpi{eq \o(n,´)}ski Curves 55
2.10 Hilbert Curves 65
2.11 Penrose Curves 65
2.12 Dragon Curves 65
2.13 Wirth Curves 68
Exercises
3 Linked Lists and Trees 73
3.1 Linked List 73
3.2 Creating a One-Way Linked List 74
Appending to the Tail, Creating and Deleting Nodes
3.3 Circular Linked List - Josephus' Problem 83
Exercises
3.4 Two-Way Linked List 87
Exercises
3.5 Binary Tree 88
3.6 Binary Search Tree 89
Searching, Traversal, Insertion
3.7 Sorting Using Red-Black Binary Trees 98
Insertion, Left Rotation, Right Rotation, Rebalance the tree and re-color nodes,
Red-Black Tree algorithm, Shortened version of the REBALANCE_TREE algorithm
3.8 Displaying a Tree Decorated with Nodes 118
Normal and sideways
3.9 Deleting a Node from a Red-Black Tree 125
Splicing out and restructuring
3.10 Algebraic Expression and Trees 131
Exercise
3.11 Indirect Sort of a Linked List 137
Exercise
4 Complex Arithmetic 144
4.1 Complex Arithmetic Facilities 144
4.2 Exponentiation, taking roots 147
4.3 Complex Roots of a Quadratic Equation 148
4.4 Real and Complex Roots of a Cubic Equation 151
4.5 Real and Complex Roots of a Polynomial 154
4.6 Fractals 163
4.7 Making a Picture File (PCX format) 172
4.8 Complex Roots of Complex Linear Equations 181
4.9 Electrical Circuit 184
4.10 Impedance of an Electrical Circuit 186
4.11 Defining a complex type for Integers 189
4.12 Converting integer, real, and complex values to string 194
Exercises
5 Using Published Algorithms 198
5.1 Fast Fourier Transform 198
5.2 Fast Fourier Transforms of Real, Sine, and Cosine Functions 203
5.3 Matrix Multiplication 207
5.4 Directed Graphs - Transitive Closure 210
6 Text Processing 215
6.1 A Simple Text Editor 215
Exercises
Example - Converting a plain text file to HTML format 227
6.2 String Searching 236
6.3 Classic String Search 236
6.4 The Knuth-Morris-Pratt String Search 238
6.5 The Boyer-Moore String Search 242
6.6 The Rabin-Karp String Search 247
6.7 The Baeza-Yates-Gonnet String Search 251
6.8 Approximate Searching 256
6.9 Approximate String Search 261
7 Files 267
7.1 Unformatted Input-Output 267
7.2 Sequential Unformatted File 268
7.3 Random Access Files 272
7.4 Operations on Direct Access Files 274
7.5 Writing Unformatted Files 277
7.6 Internal Input-Output 278
Summary of open, read, and write statements
8 Solving Simultaneous Equations 285
8.1 Solving Equations using Gauss Elimination 285
8.2 Gauss-Siedel Iteration 293
8.3 Tri-Diagonal System of Linear Equations 297
8.4 Banded System of Equations 300
8.5 Sparse matrices 306
8.6 Matrix Inversion 315
8.7 Printing Arrays 321
9 Graphics 324
9.1 Seashells 324
9.2 New Shapes 328
9.3 Uccello's Chalice 335
9.4 Making a Picture File (TIFF file) 338
Color TIFF file
9.5 Reading and Displaying a Picture File (PCX File) 349
Summary of select case statement
10 Searching 367
10.1 Linear Search 367
10.2 Binary Search 368
10.3 Hash Search 371
10.4 Hash Table with Quadratic Searching 375
11 Numerical Methods 380
11.1 Integration - Rectangle Method 380
11.2 Trapezoidal Method 381
11.3 Simpson's Rule 383
11.4 Romberg Integration 384
11.5 Adaptive Quadrature 387
11.6 Differentiation 391
11.7 Roots of an Equation: the Newton-Raphson Method 392
11.8 Least-Squares Approximation 395
11.9 Interpolation 397
11.10 Solving a Differential Equation: Euler's Method 400
11.11 Solving a Differential Equation: The Runge-Kutta Method 402
11.12 Plotting a Function 403
12 Whole Array Operations 405
12.1 One-Dimensional Arrays 405
Initialization
12.2 Two-Dimensional Arrays 407
Initialization and the reshape Built-in Function
12.3 Printing Tables 411
12.4 Cross-Sections of Arrays 413
12.5 Parts of Arrays 414
Extracting Sub-Matrices
12.6 minval, maxval 416
12.7 minloc, maxloc 418
12.8 The where Construct 418
12.9 The forall Statement 420
Appendixes 422
A F Built-in Functions 422
B Character Sets 438
ASCII, EBCDIC
C Extended-Precision Constants 443
D Useful Functions 445
E Quick Reference to F Statements 464
F F/Fortran Resources 470
Bibliography 475
Index 480
]]>
For further information, contact
email: robin_v@bigpond.com
Copyright (c) 1999 by R. A. Vowels. All rights reserved.
Updated: 9 February 2005.