Elementary Data Structures with Pascal
by Angela B. Shiflet
January 7, 1989
Preface
Chapter 1 Programming Methodology
1.1 Program Design - Top-down design, modularity, pseudocode
1.2 Coding - Program style, documentation
1.3 Testing and Debugging - Techniques, choosing test data
1.4 Analysis of Algorithms - Big-O notation
Chapter 2 Fundamentals
2.1 Recursion
2.2 Recursion versus iteration - Implementation, efficiency, conversion between
2.3 Program Verification
2.4 Abstract Data Types - Definitions
Chapter 3 Elementary Data Structures
3.1 ADT Array - single and multidimensional implementation; static memory allocation
3.2 Sequential and Binary Searches
3.3 ADT Record - Implementation; address computation
3.4 ADT File - Implementation
3.5 ADT Set and Predefined Type
Chapter 4 Stacks
4.1 ADT Stack
4.2 Array Implementation of Stacks
4.3 Applications of Stacks - Simulation of recursion; postfix notation
Chapter 5 Queues
5.1 ADT Queue
5.2 Array Implementation of Queue
5.3 Queue Applications - Simulation; priority queue
Chapter 6 Lists
6.1 ADT Pointer and Dynamic Memory Allocation
6.2 Linked List
6.3 ADT Linked List
6.4 Linked Lists Implementations
6.5 Applications of Linked Lists - Alternative to new and dispose; arithmetic on large integers
6.6 Variations of Linked Lists - Dummy first node, circular linked list, doubly linked list, multiply linked list, sparse matrix
Chapter 7 Tables
7.1 ADT Table
7.2 Table Implementations
7.3 Hashing Table
Chapter 8 Linked List Implementations of Stacks and Queues
8.1 Linked List Implementation of Stack
8.2 Linked List Implementation of Queue
Chapter 9 Strings
9.1 ADT String
9.2 String Implementation
9.3 String Applications - compare, update, substitute, substitute all
Chapter 10 Binary Trees
10.1 Tree Terminology
10.2 ADT Binary Tree
10.3 Binary Tree Implementation
10.4 Binary Search Tree
10.5 AVL and Threaded Trees
10.6 More Applications of Binary Trees - expression tree, Huffman code, decision tree
Chapter 11 Sorting
11.1 Selection Sort
11.2 Insertion Sort
11.3 Quicksort
11.4 Heapsort
11.5 Mergesort
11.6 Comparison of Sorting Techniques
Chapter 12 Graphs and Networks
12.1 ADT Graph
12.2 Adjacency Matrix Implementation of ADT Graph
12.3 Adjacency List Implementation of ADT Graph
12.4 Graph Traversal - breadth-first, depth-first; backtrack
12.5 Graph Applications - Maze, minimal spanning tree, shortest path, ADT network, digraph