C++: object-oriented data structures

Front Cover
Springer Science & Business Media, Mar 11, 1994 - Computers - 708 pages
This book provides a broad coverage of fundamental and advanced con cepts of data structures and algorithms. The material presented includes a treatment of elementary data structures such as arrays, lists, stacks, and trees, as well as newer structures that have emerged to support the process ing of multidimensional or spatial data files. These newer structures and algorithms have received increasing attention in recent years in conjunc tion with the rapid growth in computer-aided design, computer graphics, and related fields in which multidimensional data structures are of great interest. Our main objective is to mesh the underlying concepts with application examples that are of practical use and are timely in their implementations. To this end, we have used mainly the Abstract Data Structure (or Abstract Data Type (ADT)) approach to define structures for data and operations. Object-oriented programming (OOP) methodologies are employed to im plement these ADT concepts. In OOP, data and operations for an ADT are combined into a single entity (object). ADTs are used to specifiy the objects-arrays, stacks, queues, trees, and graphs. OOP allows the pro grammer to more closely mimic the real-world applications. This OOP is more structured and modular than previous attempts. OOP has become de facto state-of-the-art in the 1990s.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Concepts of FunctionOriented and ObjectOriented Data Structures
1
12 Definition of Abstract Data Structures
2
13 ObjectOriented Design and the ADT
4
131 FUNCTIONORIENTED DATA STRUCTURES
5
132 OBJECTORIENTED DATA STRUCTURES
6
133 A UNIFIED APPROACH
8
134 STEPS FOR DERIVING AN OBJECTORIENTED DESIGN
11
14 Implementing an OOP in C++
12
7112 PERFORMANCE ANALYSES OF SORTING METHODS
356
72 Searching Methods
357
721 LINEAR SEARCH OF AN UNSORTED ARRAY
358
722 LINEAR SEARCH OF AN UNSORTED LINKED LIST
361
723 LINEAR SEARCH OF A SORTED ARRAY
363
724 LINEAR SEARCH OF A SORTED LIST
366
726 INTERPOLATION SEARCH OF A SORTED ARRAY
370
727 FIBONACCI SEARCH OF A SORTED ARRAY
373

141 A SHORT PREVIEW OF OBJECTORIENTED PROGRAMMING
14
15 Example Databases
17
17 Exercises
18
Pointers Structures Classes Functions Overloaded Functions and Overloaded Operators in CH++
21
211 C++ POINTER ARITHMETIC AND OPERATIONS
24
213 POINTERS AS RETURN VALUES OF FUNCTIONS
26
222 POINTERS TO STRUCTURES
27
223 ACCESSING STRUCTURES
28
225 STRUCTURE AS A FUNCTION ARGUMENT AND RETURN VALUE
30
227 ARRAYS OF STRUCTURES
31
24 C++ Class
32
241 DEFINING A MEMBER FUNCTION OF A CLASS OUTSIDE ITS SCOPE
34
243 ACCESSING A MEMBER OF A CLASS
35
244 FRIEND OF A CLASS AND INHERITANCE
37
245 DERIVED CLASS AND MULTIPLE INHERITANCE
38
246 NESTED CLASS
40
25 Functions in C++
41
DESTRUCTORS
42
26 Polymorphism Virtual Functions and Inheritance
43
264 OVERLOADED OPERATORS
44
271 DANGLING POINTERS
45
Complex Numbers
47
29 Exercises
50
Arrays and Strings
51
32 OneDimensional Arrays
53
323 INITIALIZING AN ARRAY
54
325 ARRAY AS FUNCTION ARGUMENTS
55
327 OOP FOR ONEDIMENSIONAL ARRAY
56
33 TwoDimensional Arrays
61
331 C++ DECLARATION OF TWODIMENSIONAL ARRAYS
62
333 INITIALIZING A TWODIMENSIONAL ARRAY
64
335 TWODIMENSIONAL ARRAYS AS FUNCTION ARGUMENTS
65
337 OOP TWODIMENSIONAL ARRAY
66
34 Strings
74
342 ARRAY OF ARRAYBASED STRINGS
76
343 ARRAY OF POINTERS TO STRINGS
77
344 STRING OBJECT AND ITS OOP IMPLEMENTATION
78
An ObjectOriented Database
84
Recursion
97
42 DivideandConquer and Recursion
98
44 Recursion and Trace of C++ Stack
103
The Towers of Hanoi
106
Nonattacking TVQueens
120
47 Key Points for Using Recursion
125
48 Exercises
126
Lists
131
51 List Objects
132
52 Implementation Specific Linked List Classes
134
531 OOP FOR ARRAYBASED LINKED LISTS WITH IMPLICIT LINKS
136
532 ADDING AN ELEMENT AFTER A GIVEN ELEMENT
138
54 PointerBased Linked Lists
142
541 NONOOP IMPLEMENTATION OF THE SINGLY LINKED LIST
143
545 DELETING AN ELEMENT IN A SINGLY LINKED LIST
149
546 METHODS OF THE singiy_Linked_List CLASS
151
547 OOP IMPLEMENTATION OF THE DOUBLY LINKED LIST
157
548 ADDING AN ELEMENT IN A DOUBLY LINKED LIST
160
551 OOP IMPLEMENTATION OF SINGLY LINKED CIRCULAR LISTS
171
552 METHODS OF THE circ_Linked_List CLASS
172
553 DOUBLY LINKED CIRCULAR LIST AND ITS OOP IMPLEMENTATION
179
Polynomial Objects in Single Variable
180
572 POLYNOMIAL OBJECTS
181
Memory Management
193
581 THE FREE LIST
194
582 FREE LIST MANAGEMENT BY COUNTED POINTERS
203
583 FREE LIST MANAGEMENT BY GARBAGE COLLECTION
207
59 Summary
208
510 Exercises
209
Stacks and Queues
217
612 OOP IMPLEMENTATION OF A STACK USING LINKED LISTS
228
613 PERFORMANCE ANALYSES OF STACK OPERATIONS
236
Reverse Polish Notation Using Stacks
237
631 POSTFIX EVALUATION
238
632 INFIX TO RPN TRANSLATION
243
64 Queue Objects
250
65 Implementation Specific Queue Classes
253
652 OOP IMPLEMENTATION OF A QUEUE USING LINKED LIST
261
66 Circular Queue Objects
268
661 OOP IMPLEMENTATION OF A CIRCULAR QUEUE USING ARRAY
269
662 OOP IMPLEMENTATION OF A CIRCULAR QUEUE USING A LINKED LIST
278
663 PERFORMANCE ANALYSES OF QUEUE OPERATIONS
279
SCAN Disk Scheduling with Priority Queues
280
68 Exercises
290
Sorting and Searching
295
711 INSERTION SORT FOR AN ARRAY LIST
298
712 INSERTION SORT FOR A LINKED LIST
301
713 SELECTION SORT
306
714 BUBBLE SORT
309
715 QUICKSORT
314
716 MERGE SORT
320
717 BINARY TREE SORT
330
718 HEAP SORT
331
719 STRAIGHT RADIX SORT
342
7110 RADIX EXCHANGE SORT
347
7111 SHELL SORT
352
728 SEARCHING A BINARY SEARCH TREE
376
729 HASH STRATEGY FOR HASH SEARCH METHOD
378
7210 PERFORMANCE ANALYSES OF SEARCHING ALGORITHMS
405
Trees and Tries
409
83 Traversing a Tree
413
84 Tree Objects
417
85 OOP Implementation of Binary Trees
418
851 OOP IMPLEMENTATION OF A BINARY TREE USING ARRAYS
419
852 OOP IMPLEMENTATION OF A BINARY TREE USING POINTERS
423
853 METHODS OF THE BinaryTree CLASS
426
86 General Trees
433
861 STRATEGIES FOR REPRESENTING GENERAL TREES
435
BINARY TREE IMPLEMENTATION
436
863 GENERAL TREE TRAVERSAL
437
865 METHODS OF THE GeneralTree CLASS
439
87 Search Trees
443
88 DataComparative Mary Search Trees
446
881 INSERTING A NODE AND BUILDING A BINARY SEARCH TREE
447
882 DELETING A NODE FROM A BST
449
883 OOP IMPLEMENTATION OF A BINARY SEARCH TREE USING POINTERS
451
887 AVL TREES
460
888 AVL TREE OBJECTS
462
8810 INSERTION OF A NODE IN AN AVL TREE
464
8813 CREATING A NODE FOR AN AVL TREE
468
TECHNIQUES
469
89 Radix Search Trees
478
891 DISCRETE VERSUS NONDISCRETE KEYS
479
892 DIGITAL SEARCH TREES
481
893 OOP IMPLEMENTATION OF A BINARY DIGITAL SEARCH TREE BDST
482
894 RADIX SEARCH TRIES
488
895 OOP IMPLEMENTATION OF AN MARY RADIX SEARCH TRIE
493
896 BALANCE CHARACTERISTICS OF RADIX SEARCH TREES
500
897 HYBRID RADIX SEARCH TRIES
502
WORD DICTIONARIES USING TRIES
503
8910 PATRICIA TREES AND TRIES
504
810 ComparativeBased BTrees for External Searching and Sorting
507
8102 INSERTING A KEY AND BUILDING A BTREE
509
8103 DELETING A KEY FROM A BTREE
513
811 Performance Analysis of Tree Operations
517
812 Exercises
518
Multidimensional Search Trees and Search Tries
527
92 Geometric Formulation of Associative Search
528
922 GEOMETRIC OBJECTS IN EUCLIDEAN SPACE
529
93 Types of Associative Search
532
94 Examples of Associative Search
534
95 Approaches to Associative Search
536
951 ADT INVERTED LIST
537
96 Multidimensional ComparativeBased Search Trees
538
962 OOP IMPLEMENTATION OF QUADTREE
539
963 KTREE BALANCE AND NODE DELETION
547
965 OOP IMPLEMENTATION OF SDTREE
550
97 Multidimensional Radix Search Tries
560
971 KTRIE OBJECTS
561
973 IMPLEMENTATION OF KTRIE AND KDTRIE
563
98 Multidimensional Structures for External Search
565
A Taxonomy of Trees and Tries
566
Graphs and Digraphs
569
101 Fundamental Definitions and Terminologies
570
102 Graph Traversals
571
1021 DEPTHFIRST TRAVERSALS
572
1022 BREADTHFIRST TRAVERSALS
573
103 Graph Objects
575
104 Implementations of a Graph
576
1041 REPRESENTING A WEIGHTED UNDIRECTED OR DIRECTED GRAPH USING ADJACENCY MATRIX
577
1042 OOP IMPLEMENTATION OF A GRAPH USING ADJACENCY MATRIX
579
1043 METHODS OF WeightedDlGraph CLASS
581
1044 OOP IMPLEMENTATION OF A GRAPH USING LINKED ADJACENCY LISTS
589
1045 METHODS OF THE WtDiGrapn CLASS
591
105 Spanning Trees of a Graph
602
1051 CONSTRUCTING A SPANNING TREE USING DEPTHFIRST TRAVERSALS
603
1052 CONSTRUCTING A SPANNING TREE USING BREADTHFIRST TRAVERSALS
604
107 Exercises
609
An ObjectOriented Database with BTrees
613
112 OOP Implementation of Simple People Database Using BTrees
614
1121 METHODS OF THE B_Tree CLASS
616
113 ObjectOriented People Database Program
619
114 Limitations of Implementation
637
115 Exercises
638
Applications in Image Processing Computer Graphics and ComputerAided Design
639
123 3D RayTracing Acceleration with an Octrie Object
659
124 3D Hidden Surface Removal with a BSP Tree Object
674
125 Exercises
684
Fundamentals
687
A5 Statement Formats of Some C++ Keywords
688
A6 A Sample C++ Program
689
Assorted Library Functions for Handling Strings
691
Appendix C Example Databases
693
C12 PEOPLE_2D
696
C13 PEOPLE_3D
697
C14 GEOMETRY_2D
698
C15 GEOMETRY_3D
699
References
701
Index
704
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 702 - Programming With Abstract Data Types,

Bibliographic information