Much that I bound, I could not free; Much that I freed returned to me. | ||
| --Lee Wilson Dodd | ||
There is always room at the top. | ||
| --Daniel Webster | ||
I think that I shall never see A poem lovely as a tree. | ||
| --Joyce Kilmer | ||
In this chapter you’ll learn:
<objective>To form linked data structures using references, self-referential classes and recursion.
</objective> <objective>How boxing and unboxing enable simple-type values to be used where objects are expected in a program.
To create and manipulate dynamic data structures, such as linked lists, queues, stacks and binary trees.
</objective> <objective>Various important applications of linked data structures.
</objective> <objective>To create reusable data structures with classes, inheritance and composition.
</objective> </feature><feature> <supertitle>Outline</supertitle> </feature>This chapter continues our four-chapter treatment of data structures. Most of the data structures that we have studied thus far have had fixed sizes, such as one- and two-dimensional arrays. Previously, we also introduced the dynamically resizable List<T> collection (Chapter 9). This chapter enhances our discussion of dynamic data structures that grow and shrink at execution time. Linked lists are collections of data items “lined up in a row” or “chained together”—users can make insertions and deletions anywhere in a linked list. Stacks are important in compilers and operating systems; insertions and deletions are made at only one end—its top. Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue, and deletions are made from the front (also referred to as the head) of a queue. Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, representation of file-system directories and compilation of expressions into machine language. These data structures have many other interesting applications as well.
We’ll discuss each of these major types of data structures and implement programs that create and manipulate them. We use classes, inheritance and composition to create and package these data structures for reusability and maintainability. In Chapter 22, we introduce generics, which allow you to declare data structures that can be automatically adapted to contain data of any type. In Chapter 23, we discuss C#’s predefined collection classes that implement various data structures.
The chapter examples are practical programs that will be useful in more advanced courses and in industrial applications. The programs focus on reference manipulation. The exercises offer a rich collection of useful applications.
The data structures we discuss in this chapter store object references. However, as you’ll soon see, we’re able to store both simple- and reference-type values in these data structures. This section discusses the mechanisms that enable simple-type values to be manipulated as objects.
Each simple type (see Appendix B, Operator Precedence Chart) has a corresponding struct in namespace System that declares the simple type. These structs are called Boolean, Byte, SByte, Char, Decimal, Double, Single, Int32, UInt32, Int64, UInt64, Int16 and UInt16. Types declared with keyword struct are implicitly value types.
Simple types are actually aliases for their corresponding structs, so a variable of a simple type can be declared using either the keyword for that simple type or the struct name—e.g., int and Int32 are interchangeable. The methods related to a simple type are located in the corresponding struct (e.g., method Parse, which converts a string to an int value, is located in struct Int32). Refer to the documentation for the corresponding struct type to see the methods available for manipulating values of that type.
Simple types and other structs inherit from class ValueType in namespace System. Class ValueType inherits from class object. Thus, any simple-type value can be assigned to an object variable; this is referred to as a boxing conversion and enables simple types to be used anywhere objects are expected. In a boxing conversion, the simple-type value is copied into an object so that the simple-type value can be manipulated as an object. Boxing conversions can be performed either explicitly or implicitly as shown in the following statements:
int i = 5; // create an int value object object1 = ( object ) i; // explicitly box the int value object object2 = i; // implicitly box the int value |
After executing the preceding code, both object1 and object2 refer to two different objects that contain a copy of the integer value in int variable i.
An unboxing conversion can be used to explicitly convert an object reference to a simple value, as shown in the following statement:
int int1 = ( int ) object1; // explicitly unbox the int value |
Explicitly attempting to unbox an object reference that does not refer to the correct simple value type causes an InvalidCastException.
In Chapters 22 and 23, we discuss C#’s generics and generic collections. As you’ll see, generics eliminate the overhead of boxing and unboxing conversions by enabling us to create and use collections of specific value types.
A self-referential class contains a reference member that refers to an object of the same class type. For example, the class declaration in Fig. 21.1 defines the shell of a self-referential class named Node. This type has two properties—integer Data and Node reference Next. Next references an object of type Node, an object of the same type as the one being declared here—hence, the term “self-referential class.” Next is referred to as a link (i.e., Next can be used to “tie” an object of type Node to another object of the same type).
Example 21.1. Self-referential Node class declaration.
1 // Fig. 21.1: Fig21_01.cs 2 // Self-referential Node class declaration. 3 class Node 4 { 5 public int Data { get; set; } // store integer data 6 public Node Next { get; set; } // store reference to next Node 7 8 public Node( int dataValue ) 9 { 10 Data = dataValue; 11 } // end constructor 12 } // end class node
Self-referential objects can be linked together to form useful data structures, such as lists, queues, stacks and trees. Figure 21.2 illustrates two self-referential objects linked together to form a linked list. A backslash (representing a null reference) is placed in the link member of the second self-referential object to indicate that the link does not refer to another object. The backslash is for illustration purposes; it does not correspond to the backslash character in C#. A null link normally indicates the end of a data structure.
Common Programming Error 21.1
Not setting the link in the last node of a list to null is a logic error.
Creating and maintaining dynamic data structures requires dynamic memory allocation—a program’s ability to obtain more memory space at execution time to hold new nodes and to release space no longer needed. As you learned in Section 10.8, C# programs do not explicitly release dynamically allocated memory—rather, the CLR performs automatic garbage collection.
The new operator is essential to dynamic memory allocation. Operator new takes as an operand the type of the object being dynamically allocated and returns a reference to an object of that type. For example, the statement
Node nodeToAdd = new Node( 10 ); |
allocates the appropriate amount of memory to store a Node and stores a reference to this object in nodeToAdd. If no memory is available, new throws an OutOfMemoryException. The constructor argument 10 specifies the Node object’s data.
The following sections discuss lists, stacks, queues and trees. These data structures are created and maintained with dynamic memory allocation and self-referential classes.
A linked list is a linear collection (i.e., a sequence) of self-referential class objects, called nodes, connected by reference links—hence, the term “linked” list. A program accesses a linked list via a reference to the first node of the list. Each subsequent node is accessed via the link-reference member stored in the previous node. By convention, the link reference in the last node of a list is set to null to mark the end of the list. Data is stored in a linked list dynamically—that is, each node is created as necessary. A node can contain data of any type, including references to objects of other classes. Stacks and queues are also linear data structures—in fact, they’re constrained versions of linked lists. Trees are nonlinear data structures.
Lists of data can be stored in arrays, but linked lists provide several advantages. A linked list is appropriate when the number of data elements to be represented in the data structure is unpredictable. Unlike a linked list, the size of a conventional C# array cannot be altered, because the array size is fixed at creation time. Conventional arrays can become full, but linked lists become full only when the system has insufficient memory to satisfy dynamic memory allocation requests.
Performance Tip 21.1
An array can be declared to contain more elements than the number of items expected, possibly wasting memory. Linked lists provide better memory utilization in these situations, because they can grow and shrink at execution time.
Programmers can maintain linked lists in sorted order simply by inserting each new element at the proper point in the list (locating the proper insertion point does take time). They do not need to move existing list elements.
Performance Tip 21.2
The elements of an array are stored contiguously in memory to allow immediate access to any array element—the address of any element can be calculated directly from its index. Linked lists do not afford such immediate access to their elements—an element can be accessed only by traversing the list from the front.
Normally linked-list nodes are not stored contiguously in memory. Rather, the nodes are logically contiguous. Figure 21.3 illustrates a linked list with several nodes.
Performance Tip 21.3
Using linked data structures and dynamic memory allocation (instead of arrays) for data structures that grow and shrink at execution time can save memory. Keep in mind, however, that reference links occupy space, and dynamic memory allocation incurs the overhead of method calls.
Figures 21.4–21.5 use an object of our List class to manipulate a list of miscellaneous object types. Class ListTest’s Main method (Fig. 21.5) creates a list of objects, inserts objects at the beginning of the list using List method InsertAtFront, inserts objects at the end of the list using List method InsertAtBack, deletes objects from the front of the list using List method RemoveFromFront and deletes objects from the end of the list using List method RemoveFromBack. After each insert and delete operation, the program invokes List method Display to output the current list contents. If an attempt is made to remove an item from an empty list, an EmptyListException occurs. A detailed discussion of the program follows.
Example 21.4. ListNode, List and EmptyListException class declarations.
1 // Fig. 21.4: LinkedListLibrary.cs 2 // ListNode, List and EmptyListException class declarations. 3 using System; 4 5 namespace LinkedListLibrary 6 { 7 // class to represent one node in a list 8 class ListNode 9 { 10 // automatic read-only property Data 11 public object Data { get; private set; } 12 13 // automatic property Next 14 public ListNode Next { get; set; } 15 16 // constructor to create ListNode that refers to dataValue 17 // and is last node in list 18 public ListNode( object dataValue ) 19 : this( dataValue, null ) 20 { 21 } // end default constructor 22 23 // constructor to create ListNode that refers to dataValue 24 // and refers to next ListNode in List 25 public ListNode( object dataValue, ListNode nextNode ) 26 { 27 Data = dataValue; 28 Next = nextNode; 29 } // end constructor 30 } // end class ListNode 31 32 // class List declaration 33 public class List 34 { 35 private ListNode firstNode; 36 private ListNode lastNode; 37 private string name; // string like "list" to display 38 39 // construct empty List with specified name 40 public List( string listName ) 41 { 42 name = listName; 43 firstNode = lastNode = null; 44 } // end constructor 45 46 // construct empty List with "list" as its name 47 public List() 48 : this( "list" ) 49 { 50 } // end default constructor 51 52 // Insert object at front of List. If List is empty, 53 // firstNode and lastNode will refer to same object. 54 // Otherwise, firstNode refers to new node. 55 public void InsertAtFront( object insertItem ) 56 { 57 if ( IsEmpty() ) 58 firstNode = lastNode = new ListNode( insertItem ); 59 else 60 firstNode = new ListNode( insertItem, firstNode ); 61 } // end method InsertAtFront 62 63 // Insert object at end of List. If List is empty, 64 // firstNode and lastNode will refer to same object. 65 // Otherwise, lastNode's Next property refers to new node. 66 public void InsertAtBack( object insertItem ) 67 { 68 if ( IsEmpty() ) 69 firstNode = lastNode = new ListNode( insertItem ); 70 else 71 lastNode = lastNode.Next = new ListNode( insertItem ); 72 } // end method InsertAtBack 73 74 // remove first node from List 75 public object RemoveFromFront() 76 { 77 if ( IsEmpty() ) 78 throw new EmptyListException( name ); 79 80 object removeItem = firstNode.Data; // retrieve data 81 82 // reset firstNode and lastNode references 83 if ( firstNode == lastNode ) 84 firstNode = lastNode = null; 85 else 86 firstNode = firstNode.Next; 87 88 return removeItem; // return removed data 89 } // end method RemoveFromFront 90 91 // remove last node from List 92 public object RemoveFromBack() 93 { 94 if ( IsEmpty() ) 95 throw new EmptyListException( name ); 96 97 object removeItem = lastNode.Data; // retrieve data 98 99 // reset firstNode and lastNode references 100 if ( firstNode == lastNode ) 101 firstNode = lastNode = null; 102 else 103 { 104 ListNode current = firstNode; 105 106 // loop while current node is not lastNode 107 while ( current.Next != lastNode ) 108 current = current.Next; // move to next node 109 110 // current is new lastNode 111 lastNode = current; 112 current.Next = null; 113 } // end else 114 115 return removeItem; // return removed data 116 } // end method RemoveFromBack 117 118 // return true if List is empty 119 public bool IsEmpty() 120 { 121 return firstNode == null; 122 } // end method IsEmpty 123 124 // output List contents 125 public void Display() 126 { 127 if ( IsEmpty() ) 128 { 129 Console.WriteLine( "Empty " + name ); 130 } // end if 131 else 132 { 133 Console.Write( "The " + name + " is: " ); 134 135 ListNode current = firstNode; 136 137 // output current node data while not at end of list 138 while ( current != null ) 139 { 140 Console.Write( current.Data + " " ); 141 current = current.Next; 142 } // end while 143 144 Console.WriteLine( " " ); 145 } // end else 146 } // end method Display 147 } // end class List 148 149 // class EmptyListException declaration 150 public class EmptyListException : Exception 151 { 152 // parameterless constructor 153 public EmptyListException() 154 : base( "The list is empty" ) 155 { 156 // empty constructor 157 } // end EmptyListException constructor 158 159 // one-parameter constructor 160 public EmptyListException( string name ) 161 : base( "The " + name + " is empty" ) 162 { 163 // empty constructor 164 } // end EmptyListException constructor 165 166 // two-parameter constructor 167 public EmptyListException( string exception, Exception inner ) 168 : base( exception, inner ) 169 { 170 // empty constructor 171 } // end EmptyListException constructor 172 } // end class EmptyListException 173 } // end namespace LinkedListLibrary
Example 21.5. Testing class List.
1 // Fig. 21.5: ListTest.cs 2 // Testing class List. 3 using System; 4 using LinkedListLibrary; 5 6 // class to test List class functionality 7 class ListTest 8 { 9 public static void Main( string[] args ) 10 { 11 List list = new List(); // create List container 12 13 // create data to store in List 14 bool aBoolean = true; 15 char aCharacter = '$'; 16 int anInteger = 34567; 17 string aString = "hello"; 18 19 // use List insert methods 20 list.InsertAtFront( aBoolean ); 21 list.Display(); 22 list.InsertAtFront( aCharacter ); 23 list.Display(); 24 list.InsertAtBack( anInteger ); 25 list.Display(); 26 list.InsertAtBack( aString ); 27 list.Display(); 28 29 // use List remove methods 30 object removedObject; 31 32 // remove data from list and display after each removal 33 try 34 { 35 removedObject = list.RemoveFromFront(); 36 Console.WriteLine( removedObject + " removed" ); 37 list.Display(); 38 39 removedObject = list.RemoveFromFront(); 40 Console.WriteLine( removedObject + " removed" ); 41 list.Display(); 42 43 removedObject = list.RemoveFromBack(); 44 Console.WriteLine( removedObject + " removed" ); 45 list.Display(); 46 47 removedObject = list.RemoveFromBack(); 48 Console.WriteLine( removedObject + " removed" ); 49 list.Display(); 50 } // end try 51 catch ( EmptyListException emptyListException ) 52 { 53 Console.Error.WriteLine( " " + emptyListException ); 54 } // end catch 55 } // end Main 56 } // end class ListTest
The list is: True The list is: $ True The list is: $ True 34567 The list is: $ True 34567 hello $ removed The list is: True 34567 hello True removed The list is: 34567 hello hello removed The list is: 34567 34567 removed Empty list |
Performance Tip 21.4
Insertion and deletion in a sorted array can be time consuming—all the elements following the inserted or deleted element must be shifted appropriately.
The program consists of four classes—ListNode (Fig. 21.4, lines 8–30), List (lines 33–147), EmptyListException (lines 150–172) and ListTest (Fig. 21.5). The classes in Fig. 21.4 create a linked-list library (defined in namespace LinkedListLibrary) that can be reused throughout this chapter. You should place the code of Fig. 21.4 in its own class library project, as we described in Section 15.13.
Encapsulated in each List object is a linked list of ListNode objects. Class ListNode (Fig. 21.4, lines 8–30) contains two properties—Data and Next. Data can refer to any object. [Note: Typically, a data structure will contain data of only one type, or data of any type derived from one base type.] In this example, we use data of various types derived from object to demonstrate that our List class can store data of any type. Next stores a reference to the next ListNode object in the linked list. The ListNode constructors (lines 18–21 and 25–29) enable us to initialize a ListNode that will be placed at the end of a List or before a specific ListNode in a List, respectively.
Class List (lines 33–147) contains private instance variables firstNode (a reference to the first ListNode in a List) and lastNode (a reference to the last ListNode in a List). The constructors (lines 40–44 and 47–50) initialize both references to null and enable us to specify the List’s name for output purposes. InsertAtFront (lines 55–61), InsertAtBack (lines 66–72), RemoveFromFront (lines 75–89) and RemoveFromBack (lines 92–116) are the primary methods of class List. Method IsEmpty (lines 119–122) is a predicate method that determines whether the list is empty (i.e., the reference to the first node of the list is null). Predicate methods typically test a condition and do not modify the object on which they’re called. If the list is empty, method IsEmpty returns true; otherwise, it returns false. Method Display (lines 125–146) displays the list’s contents. A detailed discussion of class List’s methods follows Fig. 21.5.
Class EmptyListException (lines 150–172) defines an exception class that we use to indicate illegal operations on an empty List.
Class ListTest (Fig. 21.5) uses the linked-list library to create and manipulate a linked list. [Note: In the project containing Fig. 21.5, you must add a reference to the class library containing the classes in Fig. 21.4. If you use our existing example, you may need to update this reference.] Line 11 creates a new List object and assigns it to variable list. Lines 14–17 create data to add to the list. Lines 20–27 use List insertion methods to insert these values and use List method Display to output the contents of list after each insertion. The values of the simple-type variables are implicitly boxed in lines 20, 22 and 24 where object references are expected. The code inside the try block (lines 33–50) removes objects via List deletion methods, outputs each removed object and outputs list after every deletion. If there’s an attempt to remove an object from an empty list, the catch at lines 51–54 catches the EmptyListException and displays an error message.
Over the next several pages, we discuss each of the methods of class List in detail. Method InsertAtFront (Fig. 21.4, lines 55–61) places a new node at the front of the list. The method consists of three steps:
Call
IsEmptyto determine whether the list is empty (line 57).If the list is empty, set both
firstNodeandlastNodeto refer to a newListNodeinitialized withinsertItem(line 58). TheListNodeconstructor at lines 18–21 of Fig. 21.4 calls theListNodeconstructor at lines 25–29, which sets propertyDatato refer to theobjectpassed as the first argument and sets theNextproperty’s reference tonull.If the list is not empty, the new node is “linked” into the list by setting
firstNodeto refer to a newListNodeobject initialized withinsertItemandfirstNode(line 60). When theListNodeconstructor (lines 25–29) executes, it sets propertyDatato refer to theobjectpassed as the first argument and performs the insertion by setting theNextreference to theListNodepassed as the second argument.
In Fig. 21.6, part (a) shows a list and a new node during the InsertAtFront operation before the new node is linked into the list. The dashed lines and arrows in part (b) illustrate Step 3 of the InsertAtFront operation, which enables the node containing 12 to become the new list front.
Method InsertAtBack (Fig. 21.4, lines 66–72) places a new node at the back of the list. The method consists of three steps:
Call
IsEmptyto determine whether the list is empty (line 68).If the list is empty, set both
firstNodeandlastNodeto refer to a newListNodeinitialized withinsertItem(lines 68–69). TheListNodeconstructor at lines 18–21 calls theListNodeconstructor at lines 25–29, which sets propertyDatato refer to theobjectpassed as the first argument and sets theNextreference tonull.If the list is not empty, link the new node into the list by setting
lastNodeandlastNode.Nextto refer to a newListNodeobject initialized withinsertItem(line 71). When theListNodeconstructor (lines 18–21) executes, it calls the constructor at lines 25–29, which sets propertyDatato refer to theobjectpassed as an argument and sets theNextreference tonull.
In Fig. 21.7, part (a) shows a list and a new node during the InsertAtBack operation before the new node has been linked into the list. The dashed lines and arrows in part (b) illustrate Step 3 of method InsertAtBack, which enables a new node to be added to the end of a list that is not empty.
Method RemoveFromFront (Fig. 21.4, lines 75–89) removes the front node of the list and returns a reference to the removed data. The method throws an EmptyListException (line 78) if the programmer tries to remove a node from an empty list. Otherwise, the method returns a reference to the removed data. After determining that a List is not empty, the method consists of four steps to remove the first node:
Assign
firstNode.Data(the data being removed from the list) to variableremoveItem(line 80).If the objects to which
firstNodeandlastNoderefer are the same object, the list has only one element, so the method setsfirstNodeandlastNodetonull(line 84) to remove the node from the list (leaving the list empty).If the list has more than one node, the method leaves reference
lastNodeas is and assignsfirstNode.NexttofirstNode(line 86). Thus,firstNodereferences the node that was previously the second node in theList.Return the
removeItemreference (line 88).
In Fig. 21.8, part (a) illustrates a list before a removal operation. The dashed lines and arrows in part (b) show the reference manipulations.
Method RemoveFromBack (Fig. 21.4, lines 92–116) removes the last node of a list and returns a reference to the removed data. The method throws an EmptyListException (line 95) if the program attempts to remove a node from an empty list. The method consists of several steps:
Assign
lastNode.Data(the data being removed from the list) to variableremoveItem(line 97).If
firstNodeandlastNoderefer to the same object (line 100), the list has only one element, so the method setsfirstNodeandlastNodetonull(line 101) to remove that node from the list (leaving the list empty).If the list has more than one node, create
ListNodevariablecurrentand assign itfirstNode(line 104).Now “walk the list” with
currentuntil it references the node before the last node. Thewhileloop (lines 107–108) assignscurrent.Nexttocurrentas long ascurrent.Nextis not equal tolastNode.After locating the second-to-last node, assign
currenttolastNode(line 111) to update which node is last in the list.Set
current.Nexttonull(line 112) to remove the last node from the list and terminate the list at the current node.Return the
removeItemreference (line 115).
In Fig. 21.9, part (a) illustrates a list before a removal operation. The dashed lines and arrows in part (b) show the reference manipulations.
Method Display (Fig. 21.4, lines 125–146) first determines whether the list is empty (line 127). If so, Display displays a string consisting of the string "Empty " and the list’s name, then returns control to the calling method. Otherwise, Display outputs the data in the list. The method writes a string consisting of the string "The ", the list’s name and the string " is: ". Then line 135 creates ListNode variable current and initializes it with firstNode. While current is not null, there are more items in the list. Therefore, the method displays current.Data (line 140), then assigns current.Next to current (line 141) to move to the next node in the list.
The kind of linked list we have been discussing is a singly linked list—it begins with a reference to the first node, and each node contains a reference to the next node “in sequence.” This list terminates with a node whose reference member has the value null. A singly linked list may be traversed in only one direction.
A circular, singly linked list (Fig. 21.10) begins with a reference to the first node, and each node contains a reference to the next node. The “last node” does not contain a null reference; rather, the reference in the last node points back to the first node, thus closing the “circle.”
A doubly linked list (Fig. 21.11) allows traversals both forward and backward. Such a list is often implemented with two “start references”—one that refers to the first element of the list to allow front-to-back traversal of the list and one that refers to the last element to allow back-to-front traversal. Each node has both a forward reference to the next node in the list and a backward reference to the previous node. If your list contains an alphabetized telephone directory, for example, a search for someone whose name begins with a letter near the front of the alphabet might begin from the front of the list. A search for someone whose name begins with a letter near the end of the alphabet might begin from the back.
In a circular, doubly linked list (Fig. 21.12), the forward reference of the last node refers to the first node, and the backward reference of the first node refers to the last node, thus closing the “circle.”
A stack is a constrained version of a linked list—it receives new nodes and releases nodes only at the top. For this reason, a stack is referred to as a last-in, first-out (LIFO) data structure.
The primary operations to manipulate a stack are push and pop. Operation push adds a new node to the top of the stack. Operation pop removes a node from the top of the stack and returns the data item from the popped node.
Stacks have many interesting applications. For example, when a program calls a method, the called method must know how to return to its caller, so the return address is pushed onto the method-call stack. If a series of method calls occurs, the successive return values are pushed onto the stack in last-in, first-out order so that each method can return to its caller. Stacks support recursive method calls in the same manner that they do conventional nonrecursive method calls.
The System.Collections namespace contains class Stack for implementing and manipulating stacks that can grow and shrink during program execution.
In our next example, we take advantage of the close relationship between lists and stacks to implement a stack class by reusing a list class. We demonstrate two different forms of reusability. First, we implement the stack class by inheriting from class List of Fig. 21.4. Then we implement an identically performing stack class through composition by including a List object as a private member of a stack class.
The program of Figs. 21.13 and 21.14 creates a stack class by inheriting from class List of Fig. 21.4 (line 8 of Fig. 21.3). We want the stack to have methods Push, Pop, IsEmpty and Display. Essentially, these are the methods InsertAtFront, RemoveFromFront, IsEmpty and Display of class List. Of course, class List contains other methods (such as InsertAtBack and RemoveFromBack) that we would rather not make accessible through the public interface of the stack. It is important to remember that all methods in the public interface of class List are also public methods of the derived class StackInheritance (Fig. 21.13).
Example 21.13. Implementing a stack by inheriting from class List.
1 // Fig. 21.13: StackInheritanceLibrary.cs 2 // Implementing a stack by inheriting from class List. 3 using LinkedListLibrary; 4 5 namespace StackInheritanceLibrary 6 { 7 // class StackInheritance inherits class List's capabilities 8 public class StackInheritance : List 9 { 10 // pass name "stack" to List constructor 11 public StackInheritance() 12 : base( "stack" ) 13 { 14 } // end constructor 15 16 // place dataValue at top of stack by inserting 17 // dataValue at front of linked list 18 public void Push( object dataValue ) 19 { 20 InsertAtFront( dataValue ); 21 } // end method Push 22 23 // remove item from top of stack by removing 24 // item at front of linked list 25 public object Pop() 26 { 27 return RemoveFromFront(); 28 } // end method Pop 29 } // end class StackInheritance 30 } // end namespace StackInheritanceLibrary
Example 21.14. Testing class StackInheritance.
1 // Fig. 21.14: StackInheritanceTest.cs 2 // Testing class StackInheritance. 3 using System; 4 using StackInheritanceLibrary; 5 using LinkedListLibrary; 6 7 // demonstrate functionality of class StackInheritance 8 class StackInheritanceTest 9 { 10 public static void Main( string[] args ) 11 { 12 StackInheritance stack = new StackInheritance(); 13 14 // create objects to store in the stack 15 bool aBoolean = true; 16 char aCharacter = '$'; 17 int anInteger = 34567; 18 string aString = "hello"; 19 20 // use method Push to add items to stack 21 stack.Push( aBoolean ); 22 stack.Display(); 23 stack.Push( aCharacter ); 24 stack.Display(); 25 stack.Push( anInteger ); 26 stack.Display(); 27 stack.Push( aString ); 28 stack.Display(); 29 30 // remove items from stack 31 try 32 { 33 while ( true ) 34 { 35 object removedObject = stack.Pop(); 36 Console.WriteLine( removedObject + " popped" ); 37 stack.Display(); 38 } // end while 39 } // end try 40 catch ( EmptyListException emptyListException ) 41 { 42 // if exception occurs, write stack trace 43 Console.Error.WriteLine( emptyListException.StackTrace ); 44 } // end catch 45 } // end Main 46 } // end class StackInheritanceTest
The stack is: True The stack is: $ True The stack is: 34567 $ True The stack is: hello 34567 $ True hello popped The stack is: 34567 $ True 34567 popped The stack is: $ True $ popped The stack is: True True popped Empty stack at LinkedListLibrary.List.RemoveFromFront() in C:examplesch21Fig21_04LinkedListLibrary LinkedListLibraryLinkedListLibrary.cs:line 78 at StackInheritanceLibrary.StackInheritance.Pop() in C:examplesch21Fig21_13StackInheritanceLibrary StackInheritanceLibraryStackInheritance.cs:line 27 at StackInheritanceTest.Main(String[] args) in C:examplesch21Fig21_14StackInheritanceTest StackInheritanceTestStackInheritanceTest.cs:line 35 |
The implementation of each StackInheritance method calls the appropriate List method—method Push calls InsertAtFront, method Pop calls RemoveFromFront. Class StackInheritance does not define methods IsEmpty and Display, because StackInheritance inherits these methods from class List into StackInheritance’s public interface. Class StackInheritance uses namespace LinkedListLibrary (Fig. 21.4); thus, the class library that defines StackInheritance must have a reference to the LinkedListLibrary class library.
StackInheritanceTest’s Main method (Fig. 21.14) uses class StackInheritance to create a stack of objects called stack (line 12). Lines 15–18 define four values that will be pushed onto the stack and popped off it. The program pushes onto the stack (lines 21, 23, 25 and 27) a bool containing true, a char containing '$', an int containing 34567 and a string containing "hello". An infinite while loop (lines 33–38) pops the elements from the stack. When the stack is empty, method Pop throws an EmptyListException, and the program displays the exception’s stack trace, which shows the program-execution stack at the time the exception occurred. The program uses method Display (inherited by StackInheritance from class List) to output the contents of the stack after each operation. Class StackInheritanceTest uses namespace LinkedListLibrary (Fig. 21.4) and namespace StackInheritanceLibrary (Fig. 21.13); thus, the solution for class StackInheritanceTest must have references to both class libraries.
Another way to implement a stack class is by reusing a list class through composition. The class in Fig. 21.15 uses a private object of class List (line 10) in the declaration of class StackComposition. Composition enables us to hide the methods of class List that should not be in our stack’s public interface by providing public interface methods only to the required List methods. This class implements each stack method by delegating its work to an appropriate List method. StackComposition’s methods call List methods InsertAtFront, RemoveFromFront, IsEmpty and Display. In this example, we do not show class StackCompositionTest, because the only difference in this example is that we change the name of the stack class from StackInheritance to StackComposition.
Example 21.15. StackComposition class encapsulates functionality of class List.
1 // Fig. 21.15: StackCompositionLibrary.cs 2 // StackComposition declaration with composed List object. 3 using LinkedListLibrary; 4 5 namespace StackCompositionLibrary 6 { 7 // class StackComposition encapsulates List's capabilities 8 public class StackComposition 9 { 10 private List stack; 11 12 // construct empty stack 13 public StackComposition() 14 { 15 stack = new List( "stack" ); 16 } // end constructor 17 18 // add object to stack 19 public void Push( object dataValue ) 20 { 21 stack.InsertAtFront( dataValue ); 22 } // end method Push 23 24 // remove object from stack 25 public object Pop() 26 { 27 return stack.RemoveFromFront(); 28 } // end method Pop 29 30 // determine whether stack is empty 31 public bool IsEmpty() 32 { 33 return stack.IsEmpty(); 34 } // end method IsEmpty 35 36 // output stack contents 37 public void Display() 38 { 39 stack.Display(); 40 } // end method Display 41 } // end class StackComposition 42 } // end namespace StackCompositionLibrary
Another commonly used data structure is the queue. A queue is similar to a checkout line in a supermarket—the cashier services the person at the beginning of the line first. Other customers enter the line only at the end and wait for service. Queue nodes are removed only from the head (or front) of the queue and are inserted only at the tail (or end). For this reason, a queue is a first-in, first-out (FIFO) data structure. The insert and remove operations are known as enqueue and dequeue.
Queues have many uses in computer systems. Computers with only a single processor can service only one application at a time. Each application requiring processor time is placed in a queue. The application at the front of the queue is the next to receive service. Each application gradually advances to the front as the applications before it receive service.
Queues are also used to support print spooling. For example, a single printer might be shared by all users of a network. Many users can send print jobs to the printer, even when the printer is already busy. These print jobs are placed in a queue until the printer becomes available. A program called a spooler manages the queue to ensure that as each print job completes, the next one is sent to the printer.
Information packets also wait in queues in computer networks. Each time a packet arrives at a network node, it must be routed to the next node along the path to the packet’s final destination. The routing node routes one packet at a time, so additional packets are enqueued until the router can route them.
A file server in a computer network handles file-access requests from many clients throughout the network. Servers have a limited capacity to service requests from clients. When that capacity is exceeded, client requests wait in queues.
The program of Figs. 21.16 and 21.17 creates a queue class by inheriting from a list class. We want the QueueInheritance class (Fig. 21.16) to have methods Enqueue, Dequeue, IsEmpty and Display. Essentially, these are the methods InsertAtBack, RemoveFromFront, IsEmpty and Display of class List. Of course, the list class contains other methods (such as InsertAtFront and RemoveFromBack) that we would rather not make accessible through the public interface to the queue class. Remember that all methods in the public interface of the List class are also public methods of the derived class QueueInheritance.
Example 21.16. Implementing a queue by inheriting from class List.
1 // Fig. 21.16: QueueInheritanceLibrary.cs 2 // Implementing a queue by inheriting from class List. 3 using LinkedListLibrary; 4 5 namespace QueueInheritanceLibrary 6 { 7 // class QueueInheritance inherits List's capabilities 8 public class QueueInheritance : List 9 { 10 // pass name "queue" to List constructor 11 public QueueInheritance() 12 : base( "queue" ) 13 { 14 } // end constructor 15 16 // place dataValue at end of queue by inserting 17 // dataValue at end of linked list 18 public void Enqueue( object dataValue ) 19 { 20 InsertAtBack( dataValue ); 21 } // end method Enqueue 22 23 // remove item from front of queue by removing 24 // item at front of linked list 25 public object Dequeue() 26 { 27 return RemoveFromFront(); 28 } // end method Dequeue 29 } // end class QueueInheritance 30 } // end namespace QueueInheritanceLibrary
Example 21.17. Testing class QueueInheritance.
1 // Fig. 21.17: QueueTest.cs 2 // Testing class QueueInheritance. 3 using System; 4 using QueueInheritanceLibrary; 5 using LinkedListLibrary; 6 7 // demonstrate functionality of class QueueInheritance 8 class QueueTest 9 { 10 public static void Main( string[] args ) 11 { 12 QueueInheritance queue = new QueueInheritance(); 13 14 // create objects to store in the queue 15 bool aBoolean = true; 16 char aCharacter = '$'; 17 int anInteger = 34567; 18 string aString = "hello"; 19 20 // use method Enqueue to add items to queue 21 queue.Enqueue( aBoolean ); 22 queue.Display(); 23 queue.Enqueue( aCharacter ); 24 queue.Display(); 25 queue.Enqueue( anInteger ); 26 queue.Display(); 27 queue.Enqueue( aString ); 28 queue.Display(); 29 30 // use method Dequeue to remove items from queue 31 object removedObject = null; 32 33 // remove items from queue 34 try 35 { 36 while ( true ) 37 { 38 removedObject = queue.Dequeue(); 39 Console.WriteLine( removedObject + " dequeued" ); 40 queue.Display(); 41 } // end while 42 } // end try 43 catch ( EmptyListException emptyListException ) 44 { 45 // if exception occurs, write stack trace 46 Console.Error.WriteLine( emptyListException.StackTrace ); 47 } // end catch 48 } // end Main 49 } // end class QueueTest
The queue is: True The queue is: True $ The queue is: True $ 34567 The queue is: True $ 34567 hello True dequeued The queue is: $ 34567 hello $ dequeued The queue is: 34567 hello 34567 dequeued The queue is: hello hello dequeued Empty queue at LinkedListLibrary.List.RemoveFromFront() in C:examplesch21Fig21_04LinkedListLibrary LinkedListLibraryLinkedListLibrary.cs:line 78 at QueueInheritanceLibrary.QueueInheritance.Dequeue() in C:examplesch21Fig21_16QueueInheritanceLibrary QueueInheritanceLibraryQueueInheritance.cs:line 28 at QueueTest.Main(String[] args) in C:examplesch21Fig21_17QueueTest QueueTestQueueTest.cs:line 38 |
The implementation of each QueueInheritance method calls the appropriate List method—method Enqueue calls InsertAtBack and method Dequeue calls RemoveFromFront. Calls to IsEmpty and Display invoke the base-class versions that were inherited from class List into QueueInheritance’s public interface. Class QueueInheritance uses namespace LinkedListLibrary (Fig. 21.4); thus, the class library for QueueInheritance must have a reference to the LinkedListLibrary class library.
Class QueueInheritanceTest’s Main method (Fig. 21.17) creates a QueueInheritance object called queue. Lines 15–18 define four values that will be enqueued and dequeued. The program enqueues (lines 21, 23, 25 and 27) a bool containing true, a char containing '$', an int containing 34567 and a string containing "hello". Class QueueInheritanceTest uses namespace LinkedListLibrary and namespace QueueInheritanceLibrary; thus, the solution for class StackInheritanceTest must have references to both class libraries.
An infinite while loop (lines 36–41) dequeues the elements from the queue in FIFO order. When there are no objects left to dequeue, method Dequeue throws an EmptyListException, and the program displays the exception’s stack trace, which shows the program-execution stack at the time the exception occurred. The program uses method Display (inherited from class List) to output the contents of the queue after each operation. Class QueueInheritanceTest uses namespace LinkedListLibrary (Fig. 21.4) and namespace QueueInheritanceLibrary (Fig. 21.16); thus, the solution for class QueueInheritanceTest must have references to both class libraries.
Linked lists, stacks and queues are linear data structures (i.e., sequences). A tree is a nonlinear, two-dimensional data structure with special properties. Tree nodes contain two or more links.
With binary trees (Fig. 21.18), each tree node contains two links (none, one or both of which may be null). The root node is the first node in a tree. Each link in the root node refers to a child. The left child is the first node in the left subtree, and the right child is the first node in the right subtree. The children of a specific node are called siblings. A node with no children is called a leaf node. Computer scientists normally draw trees from the root node down—exactly the opposite of the way most trees grow in nature.
In our binary-tree example, we create a special binary tree called a binary search tree. A binary search tree (with no duplicate node values) has the characteristic that the values in any left subtree are less than the value in the subtree’s parent node, and the values in any right subtree are greater than the value in the subtree’s parent node. Figure 21.19 illustrates a binary search tree with 9 integer values. The shape of the binary search tree that corresponds to a set of data can depend on the order in which the values are inserted into the tree.
The application of Figs. 21.20 and 21.21 creates a binary search tree of integers and traverses it (i.e., walks through all its nodes) in three ways—using recursive inorder, preorder and postorder traversals. The program generates 10 random numbers and inserts each into the tree. Figure 21.20 defines class Tree in namespace BinaryTreeLibrary for reuse purposes. Figure 21.21 defines class TreeTest to demonstrate class Tree’s functionality. Method Main of class TreeTest instantiates an empty Tree object, then randomly generates 10 integers and inserts each value in the binary tree by calling Tree method InsertNode. The program then performs preorder, inorder and postorder traversals of the tree. We’ll discuss these traversals shortly.
Example 21.20. Declaration of class TreeNode and class Tree.
1 // Fig. 21.20: BinaryTreeLibrary.cs 2 // Declaration of class TreeNode and class Tree. 3 using System; 4 5 namespace BinaryTreeLibrary 6 { 7 // class TreeNode declaration 8 class TreeNode 9 { 10 // automatic property LeftNode 11 public TreeNode LeftNode { get; set; } 12 13 // automatic property Data 14 public int Data { get; set; } 15 16 // automatic property RightNode 17 public TreeNode RightNode { get; set; } 18 19 // initialize Data and make this a leaf node 20 public TreeNode( int nodeData ) 21 { 22 Data = nodeData; 23 LeftNode = RightNode = null; // node has no children 24 } // end constructor 25 26 // insert TreeNode into Tree that contains nodes; 27 // ignore duplicate values 28 public void Insert( int insertValue ) 29 { 30 if ( insertValue < Data ) // insert in left subtree 31 { 32 // insert new TreeNode 33 if ( LeftNode == null ) 34 LeftNode = new TreeNode( insertValue ); 35 else // continue traversing left subtree 36 LeftNode.Insert( insertValue ); 37 } // end if 38 else if ( insertValue > Data ) // insert in right subtree 39 { 40 // insert new TreeNode 41 if ( RightNode == null ) 42 RightNode = new TreeNode( insertValue ); 43 else // continue traversing right subtree 44 RightNode.Insert( insertValue ); 45 } // end else if 46 } // end method Insert 47 } // end class TreeNode 48 49 // class Tree declaration 50 public class Tree 51 { 52 private TreeNode root; 53 54 // construct an empty Tree of integers 55 public Tree() 56 { 57 root = null; 58 } // end constructor 59 60 // Insert a new node in the binary search tree. 61 // If the root node is null, create the root node here. 62 // Otherwise, call the insert method of class TreeNode. 63 public void InsertNode( int insertValue ) 64 { 65 if ( root == null ) 66 root = new TreeNode( insertValue ); 67 else 68 root.Insert( insertValue ); 69 } // end method InsertNode 70 71 // begin preorder traversal 72 public void PreorderTraversal() 73 { 74 PreorderHelper( root ); 75 } // end method PreorderTraversal 76 77 // recursive method to perform preorder traversal 78 private void PreorderHelper( TreeNode node ) 79 { 80 if ( node != null ) 81 { 82 // output node Data 83 Console.Write( node.Data + " " ); 84 85 // traverse left subtree 86 PreorderHelper( node.LeftNode ); 87 88 // traverse right subtree 89 PreorderHelper( node.RightNode ); 90 } // end if 91 } // end method PreorderHelper 92 93 // begin inorder traversal 94 public void InorderTraversal() 95 { 96 InorderHelper( root ); 97 } // end method InorderTraversal 98 99 // recursive method to perform inorder traversal 100 private void InorderHelper( TreeNode node ) 101 { 102 if ( node != null ) 103 { 104 // traverse left subtree 105 InorderHelper( node.LeftNode ); 106 107 // output node data 108 Console.Write( node.Data + " " ); 109 110 // traverse right subtree 111 InorderHelper( node.RightNode ); 112 } // end if 113 } // end method InorderHelper 114 115 // begin postorder traversal 116 public void PostorderTraversal() 117 { 118 PostorderHelper( root ); 119 } // end method PostorderTraversal 120 121 // recursive method to perform postorder traversal 122 private void PostorderHelper( TreeNode node ) 123 { 124 if ( node != null ) 125 { 126 // traverse left subtree 127 PostorderHelper( node.LeftNode ); 128 129 // traverse right subtree 130 PostorderHelper( node.RightNode ); 131 132 // output node Data 133 Console.Write( node.Data + " " ); 134 } // end if 135 } // end method PostorderHelper 136 } // end class Tree 137 } // end namespace BinaryTreeLibrary
Example 21.21. Testing class Tree with a binary tree.
1 // Fig. 21.21: TreeTest.cs 2 // Testing class Tree with a binary tree. 3 using System; 4 using BinaryTreeLibrary; 5 6 // class TreeTest declaration 7 public class TreeTest 8 { 9 // test class Tree 10 public static void Main( string[] args ) 11 { 12 Tree tree = new Tree(); 13 int insertValue; 14 15 Console.WriteLine( "Inserting values: " ); 16 Random random = new Random(); 17 18 // insert 10 random integers from 0-99 in tree 19 for ( int i = 1; i <= 10; i++ ) 20 { 21 insertValue = random.Next( 100 ); 22 Console.Write( insertValue + " " ); 23 24 tree.InsertNode( insertValue ); 25 } // end for 26 27 // perform preorder traversal of tree 28 Console.WriteLine( " Preorder traversal" ); 29 tree.PreorderTraversal(); 30 31 // perform inorder traversal of tree 32 Console.WriteLine( " Inorder traversal" ); 33 tree.InorderTraversal(); 34 35 // perform postorder traversal of tree 36 Console.WriteLine( " Postorder traversal" ); 37 tree.PostorderTraversal(); 38 Console.WriteLine(); 39 } // end Main 40 } // end class TreeTest
Inserting values: 39 69 94 47 50 72 55 41 97 73 Preorder traversal 39 69 47 41 50 55 94 72 73 97 Inorder traversal 39 41 47 50 55 69 72 73 94 97 Postorder traversal 41 55 50 47 73 72 97 94 69 39 |
Class TreeNode (lines 8–47 of Fig. 21.20) is a self-referential class containing three properties—LeftNode and RightNode of type TreeNode and Data of type int. Initially, every TreeNode is a leaf node, so the constructor (lines 20–24) initializes references LeftNode and RightNode to null. We discuss TreeNode method Insert (lines 28–46) shortly.
Class Tree (lines 50–136 of Fig. 21.20) manipulates objects of class TreeNode. Class Tree has as private data root (line 52)—a reference to the root node of the tree. The class contains public method InsertNode (lines 63–69) to insert a new node in the tree and public methods PreorderTraversal (lines 72–75), InorderTraversal (lines 94–97) and PostorderTraversal (lines 116–119) to begin traversals of the tree. Each of these methods calls a separate recursive utility method to perform the traversal operations on the internal representation of the tree. The Tree constructor (lines 55–58) initializes root to null to indicate that the tree initially is empty.
Tree method InsertNode (lines 63–69) first determines whether the tree is empty. If so, line 66 allocates a new TreeNode, initializes the node with the integer being inserted in the tree and assigns the new node to root. If the tree is not empty, InsertNode calls TreeNode method Insert (lines 28–46), which recursively determines the location for the new node in the tree and inserts the node at that location. A node can be inserted only as a leaf node in a binary search tree.
The TreeNode method Insert compares the value to insert with the data value in the root node. If the insert value is less than the root-node data, the program determines whether the left subtree is empty (line 33). If so, line 34 allocates a new TreeNode, initializes it with the integer being inserted and assigns the new node to reference LeftNode. Otherwise, line 36 recursively calls Insert for the left subtree to insert the value into the left subtree. If the insert value is greater than the root-node data, the program determines whether the right subtree is empty (line 41). If so, line 42 allocates a new TreeNode, initializes it with the integer being inserted and assigns the new node to reference RightNode. Otherwise, line 44 recursively calls Insert for the right subtree to insert the value in the right subtree.
Methods InorderTraversal, PreorderTraversal and PostorderTraversal call helper methods InorderHelper (lines 100–113), PreorderHelper (lines 78–91) and PostorderHelper (lines 122–135), respectively, to traverse the tree and display the node values. The purpose of the helper methods in class Tree is to allow the programmer to start a traversal without needing to obtain a reference to the root node first, then call the recursive method with that reference. Methods InorderTraversal, PreorderTraversal and PostorderTraversal simply take private variable root and pass it to the appropriate helper method to initiate a traversal of the tree. For the following discussion, we use the binary search tree shown in Fig. 21.22.
Method InorderHelper (lines 100–113) defines the steps for an inorder traversal. Those steps are as follows:
If the argument is
null, do not process the tree.Traverse the left subtree with a call to
InorderHelper(line 105).Process the value in the node (line 108).
Traverse the right subtree with a call to
InorderHelper(line 111).
The inorder traversal does not process the value in a node until the values in that node’s left subtree are processed. The inorder traversal of the tree in Fig. 21.22 is
6 13 17 27 33 42 48 |
The inorder traversal of a binary search tree displays the node values in ascending order. The process of creating a binary search tree actually sorts the data (when coupled with an inorder traversal)—thus, this process is called the binary-tree sort.
Method PreorderHelper (lines 78–91) defines the steps for a preorder traversal. Those steps are as follows:
If the argument is
null, do not process the tree.Process the value in the node (line 83).
Traverse the left subtree with a call to
PreorderHelper(line 86).Traverse the right subtree with a call to
PreorderHelper(line 89).
The preorder traversal processes the value in each node as the node is visited. After processing the value in a given node, the preorder traversal processes the values in the left subtree, then the values in the right subtree. The preorder traversal of the tree in Fig. 21.22 is
27 13 6 17 42 33 48 |
Method PostorderHelper (lines 122–135) defines the steps for a postorder traversal. Those steps are as follows:
If the argument is
null, do not process the tree.Traverse the left subtree with a call to
PostorderHelper(line 127).Traverse the right subtree with a call to
PostorderHelper(line 130).Process the value in the node (line 133).
The postorder traversal processes the value in each node after the values of all that node’s children are processed. The postorder traversal of the tree in Fig. 21.22 is
6 17 13 33 48 42 27 |
A binary search tree facilitates duplicate elimination. While building a tree, the insertion operation recognizes attempts to insert a duplicate value, because a duplicate follows the same “go left” or “go right” decisions on each comparison as the original value did. Thus, the insertion operation eventually compares the duplicate with a node containing the same value. At this point, the insertion operation might simply discard the duplicate value.
Searching a binary tree for a value that matches a key value is fast, especially for tightly packed binary trees. In a tightly packed binary tree, each level contains about twice as many elements as the previous level. Figure 21.22 is a tightly packed binary tree. A binary search tree with n elements has a minimum of log2 n levels. Thus, at most log2 n comparisons are required either to find a match or to determine that no match exists. Searching a (tightly packed) 1000-element binary search tree requires at most 10 comparisons, because 210 > 1000. Searching a (tightly packed) 1,000,000-element binary search tree requires at most 20 comparisons, because 220 > 1,000,000.
The chapter exercises present algorithms for other binary-tree operations, such as performing a level-order traversal of a binary tree. The level-order traversal of a binary tree visits the nodes of the tree row by row, starting at the root-node level. On each level of the tree, a level-order traversal visits the nodes from left to right.
The binary-tree example in Section 21.7.1 works nicely when all the data is of type int. Suppose that you want to manipulate a binary tree of doubles. You could rewrite the TreeNode and Tree classes with different names and customize the classes to manipulate doubles. Similarly, for each data type you could create customized versions of classes TreeNode and Tree. This proliferates code, and can become difficult to manage and maintain.
Ideally, we’d like to define the binary tree’s functionality once and reuse it for many types. Languages like C# provide polymorphic capabilities that enable all objects to be manipulated in a uniform manner. Using such capabilities enables us to design a more flexible data structure. C# provides these capabilities with generics (Chapter 22).
In our next example, we take advantage of C#’s polymorphic capabilities by implementing TreeNode and Tree classes that manipulate objects of any type that implements interface IComparable (namespace System). It is imperative that we be able to compare objects stored in a binary search, so we can determine the path to the insertion point of a new node. Classes that implement IComparable define method CompareTo, which compares the object that invokes the method with the object that the method receives as an argument. The method returns an int value less than zero if the calling object is less than the argument object, zero if the objects are equal and a positive value if the calling object is greater than the argument object. Also, both the calling and argument objects must be of the same data type; otherwise, the method throws an ArgumentException.
Figures 21.23–21.24 enhance the program of Section 21.7.1 to manipulate IComparable objects. One restriction on the new versions of classes TreeNode and Tree is that each Tree object can contain objects of only one type (e.g., all strings or all doubles). If a program attempts to insert multiple types in the same Tree object, ArgumentExceptions will occur. We modified only five lines of code in class TreeNode (lines 14, 20, 28, 30 and 38) and one line of code in class Tree (line 63) to enable processing of IComparable objects. Except for lines 30 and 38, all other changes simply replaced int with IComparable. Lines 30 and 38 previously used the < and > operators to compare the value being inserted with the value in a given node. These lines now compare IComparable objects via the interface’s CompareTo method, then test the method’s return value to determine whether it is less than zero (the calling object is less than the argument object) or greater than zero (the calling object is greater than the argument object), respectively. [Note: If this class were written using generics, the type of data, int or IComparable, could be replaced at compile time by any other type that implements the necessary operators and methods.]
Example 21.23. Declaration of class TreeNode and class Tree.
1 // Fig. 21.23: BinaryTreeLibrary2.cs 2 // Declaration of class TreeNode and class Tree. 3 using System; 4 5 namespace BinaryTreeLibrary2 6 { 7 // class TreeNode declaration 8 class TreeNode 9 { 10 // automatic property LeftNode 11 public TreeNode LeftNode { get; set; } 12 13 // automatic property Data 14 public IComparable Data { get; set; } 15 16 // automatic property RightNode 17 public TreeNode RightNode { get; set; } 18 19 // initialize Data and make this a leaf node 20 public TreeNode( IComparable nodeData ) 21 { 22 Data = nodeData; 23 LeftNode = RightNode = null; // node has no children 24 } // end constructor 25 26 // insert TreeNode into Tree that contains nodes; 27 // ignore duplicate values 28 public void Insert( IComparable insertValue ) 29 { 30 if ( insertValue.CompareTo(Data) < 0 ) // insert in left subtree 31 { 32 // insert new TreeNode 33 if ( LeftNode == null ) 34 LeftNode = new TreeNode( insertValue ); 35 else // continue traversing left subtree 36 LeftNode.Insert( insertValue ); 37 } // end if 38 else if ( insertValue.CompareTo( Data ) > 0 ) // insert in right 39 { 40 // insert new TreeNode 41 if ( RightNode == null ) 42 RightNode = new TreeNode( insertValue ); 43 else // continue traversing right subtree 44 RightNode.Insert( insertValue ); 45 } // end else if 46 } // end method Insert 47 } // end class TreeNode 48 49 // class Tree declaration 50 public class Tree 51 { 52 private TreeNode root; 53 54 // construct an empty Tree of IComparable objects 55 public Tree() 56 { 57 root = null; 58 } // end constructor 59 60 // Insert a new node in the binary search tree. 61 // If the root node is null, create the root node here. 62 // Otherwise, call the insert method of class TreeNode. 63 public void InsertNode( IComparable insertValue ) 64 { 65 if ( root == null ) 66 root = new TreeNode( insertValue ); 67 else 68 root.Insert( insertValue ); 69 } // end method InsertNode 70 71 // begin preorder traversal 72 public void PreorderTraversal() 73 { 74 PreorderHelper( root ); 75 } // end method PreorderTraversal 76 77 // recursive method to perform preorder traversal 78 private void PreorderHelper( TreeNode node ) 79 { 80 if ( node != null ) 81 { 82 // output node Data 83 Console.Write( node.Data + " " ); 84 85 // traverse left subtree 86 PreorderHelper( node.LeftNode ); 87 88 // traverse right subtree 89 PreorderHelper( node.RightNode ); 90 } // end if 91 } // end method PreorderHelper 92 93 // begin inorder traversal 94 public void InorderTraversal() 95 { 96 InorderHelper( root ); 97 } // end method InorderTraversal 98 99 // recursive method to perform inorder traversal 100 private void InorderHelper( TreeNode node ) 101 { 102 if ( node != null ) 103 { 104 // traverse left subtree 105 InorderHelper( node.LeftNode ); 106 107 // output node data 108 Console.Write( node.Data + " " ); 109 110 // traverse right subtree 111 InorderHelper( node.RightNode ); 112 } // end if 113 } // end method InorderHelper 114 115 // begin postorder traversal 116 public void PostorderTraversal() 117 { 118 PostorderHelper( root ); 119 } // end method PostorderTraversal 120 121 // recursive method to perform postorder traversal 122 private void PostorderHelper( TreeNode node ) 123 { 124 if ( node != null ) 125 { 126 // traverse left subtree 127 PostorderHelper( node.LeftNode ); 128 129 // traverse right subtree 130 PostorderHelper( node.RightNode ); 131 132 // output node Data 133 Console.Write( node.Data + " " ); 134 } // end if 135 } // end method PostorderHelper 136 } // end class Tree 137 } // end namespace BinaryTreeLibrary
Example 21.24. Testing class Tree with IComparable objects.
1 // Fig. 21.24: TreeTest.cs 2 // Testing class Tree with IComparable objects. 3 using System; 4 using BinaryTreeLibrary2; 5 6 // class TreeTest declaration 7 public class TreeTest 8 { 9 // test class Tree 10 public static void Main( string[] args ) 11 { 12 int[] intArray = { 8, 2, 4, 3, 1, 7, 5, 6 }; 13 double[] doubleArray = { 8.8, 2.2, 4.4, 3.3, 1.1, 7.7, 5.5, 6.6 }; 14 string[] stringArray = { "eight", "two", "four", 15 "three", "one", "seven", "five", "six" }; 16 17 // create int Tree 18 Tree intTree = new Tree(); 19 PopulateTree( intArray, intTree, "intTree" ); 20 TraverseTree( intTree, "intTree" ); 21 22 // create double Tree 23 Tree doubleTree = new Tree(); 24 PopulateTree( doubleArray, doubleTree, "doubleTree" ); 25 TraverseTree( doubleTree, "doubleTree" ); 26 27 // create string Tree 28 Tree stringTree = new Tree(); 29 PopulateTree( stringArray, stringTree, "stringTree" ); 30 TraverseTree( stringTree, "stringTree" ); 31 } // end Main 32 33 // populate Tree with array elements 34 private static void PopulateTree( Array array, Tree tree, string name ) 35 { 36 Console.WriteLine( " Inserting into " + name + ":" ); 37 38 foreach ( IComparable data in array ) 39 { 40 Console.Write( data + " " ); 41 tree.InsertNode( data ); 42 } // end foreach 43 } // end method PopulateTree 44 45 // perform traversals 46 private static void TraverseTree( Tree tree, string treeType ) 47 { 48 // perform preorder traversal of tree 49 Console.WriteLine( " Preorder traversal of " + treeType ); 50 tree.PreorderTraversal(); 51 52 // perform inorder traversal of tree 53 Console.WriteLine( " Inorder traversal of " + treeType ); 54 tree.InorderTraversal(); 55 56 // perform postorder traversal of tree 57 Console.WriteLine( " Postorder traversal of " + treeType ); 58 tree.PostorderTraversal(); 59 } // end method TraverseTree 60 } // end class TreeTest
Inserting into intTree: 8 2 4 3 1 7 5 6 Preorder traversal of intTree 8 2 1 4 3 7 5 6 Inorder traversal of intTree 1 2 3 4 5 6 7 8 Postorder traversal of intTree 1 3 6 5 7 4 2 8 Inserting into doubleTree: 8.8 2.2 4.4 3.3 1.1 7.7 5.5 6.6 Preorder traversal of doubleTree 8.8 2.2 1.1 4.4 3.3 7.7 5.5 6.6 Inorder traversal of doubleTree 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 Postorder traversal of doubleTree 1.1 3.3 6.6 5.5 7.7 4.4 2.2 8.8 Inserting into stringTree: eight two four three one seven five six Preorder traversal of stringTree eight two four five three one seven six Inorder traversal of stringTree eight five four one seven six three two Postorder traversal of stringTree five six seven one three four two eight |
Class TreeTest (Fig. 21.24) creates three Tree objects to store int, double and string values, all of which the .NET Framework defines as IComparable types. The program populates the trees with the values in arrays intArray (line 12), doubleArray (line 13) and stringArray (lines 14–15), respectively.
Method PopulateTree (lines 34–43) receives as arguments an Array containing the initializer values for the Tree, a Tree in which the array elements will be placed and a string representing the Tree name, then inserts each Array element into the Tree. Method TraverseTree (lines 46–59) receives as arguments a Tree and a string representing the Tree name, then outputs the preorder, inorder and postorder traversals of the Tree. The inorder traversal of each Tree outputs the data in sorted order regardless of the data type stored in the Tree. Our polymorphic implementation of class Tree invokes the appropriate data type’s CompareTo method to determine the path to each value’s insertion point by using the standard binary-search-tree insertion rules. Also, notice that the Tree of strings appears in alphabetical order.
In this chapter, you learned that simple types are value-type structs but can still be used anywhere objects are expected in a program due to boxing and unboxing conversions. You learned that linked lists are collections of data items that are “linked together in a chain.” You also learned that a program can perform insertions and deletions anywhere in a linked list (though our implementation performed insertions and deletions only at the ends of the list). We demonstrated that the stack and queue data structures are constrained versions of lists. For stacks, you saw that insertions and deletions are made only at the top—so stacks are known as last-in, first out (LIFO) data structures. For queues, which represent waiting lines, you saw that insertions are made at the tail and deletions are made from the head—so queues are known as first-in, first out (FIFO) data structures. We also presented the binary tree data structure. You saw a binary search tree that facilitated highspeed searching and sorting of data and efficient duplicate elimination. In the next chapter, we introduce generics, which allow you to declare a family of classes and methods that implement the same functionality on any type.
All simple-type names are aliases for corresponding
structs in namespaceSystem.Each simple type
structdeclares methods for manipulating the corresponding simple-type values.Each struct that represents a simple type inherits from class
ValueTypein namespaceSystem.A boxing conversion creates an object that contains a copy of a simple-type value.
An unboxing conversion retrieves a simple-type value from an object.
A self-referential class contains a data member that refers to an object of the same class type. Self-referential objects can be linked to form data structures, such as lists, queues, stacks and trees.
Creating and maintaining dynamic data structures requires dynamic memory allocation—a program’s ability to obtain more memory at execution time (to hold new nodes) and to release memory no longer needed.
Operator
newtakes as an operand the type of the object being dynamically allocated, calls the appropriate constructor to initialize the object and returns a reference to the new object. If no memory is available,newthrows anOutOfMemoryException.
A linked list is a linear collection (i.e., a sequence) of self-referential class objects called nodes, connected by reference links.
A node can contain properties of any type, including references to objects of other classes.
A linked list is accessed via a reference to the first node of the list. Each subsequent node is accessed via the link-reference member stored in the previous node.
By convention, the link reference in the last node of a list is set to
nullto mark the end of the list.A circular, singly linked list begins with a reference to the first node, and each node contains a reference to the next node. The “last node” does not contain a null reference; rather, the reference in the last node points back to the first node, thus closing the “circle.”
A doubly linked list allows traversals both forward and backward. Such a list is often implemented with two “start references”—one that refers to the first element of the list to allow front-to-back traversal of the list and one that refers to the last element to allow back-to-front traversal. Each node has both a forward reference to the next node in the list and a backward reference to the previous node.
In a circular, doubly linked list, the forward reference of the last node refers to the first node, and the backward reference of the first node refers to the last node, thus closing the “circle.”
Stacks are important in compilers and operating systems.
A stack is a constrained version of a linked list—new nodes can be added to and removed from a stack only at the top. A stack is referred to as a last-in, first-out (LIFO) data structure.
The primary stack operations are push and pop. Operation push adds a new node to the top of the stack. Operation pop removes a node from the top of the stack and returns the data object from the popped node.
Queues represent waiting lines. Insertions occur at the back (also referred to as the tail) of a queue, and deletions occur from the front (also referred to as the head) of a queue.
A queue is similar to a checkout line in a supermarket: The first person in line is served first; other customers enter the line at the end and wait to be served.
Queue nodes are removed only from the head of the queue and are inserted only at the tail of the queue. For this reason, a queue is referred to as a first-in, first-out (FIFO) data structure.
The insert and remove operations for a queue are known as enqueue and dequeue.
Binary trees facilitate high-speed searching and sorting of data.
Tree nodes contain two or more links.
A binary tree is a tree whose nodes all contain two links. The root node is the first node in a tree.
Each link in the root node refers to a child. The left child is the root node of the left subtree, and the right child is the root node of the right subtree.
The children of a node are called siblings. A node with no children is called a leaf node.
A binary search tree (with no duplicate node values) has the characteristic that the values in any left subtree are less than the value in that subtree’s parent node, and the values in any right subtree are greater than the value in that subtree’s parent node.
A node can be inserted only as a leaf node in a binary search tree.
In a preorder traversal, the value in each node is processed as the node is visited. After the value in a given node is processed, the values in the left subtree are processed, then the values in the right subtree are processed.
In a postorder traversal, the value in each node is processed after the node’s left and right subtrees are processed.
In an inorder traversal, the value in each node is processed after the node’s left subtree is processed and before the node’s right subtree is processed.
The inorder traversal of a binary search tree processes the node values in ascending order. The process of creating a binary search tree actually sorts the data (when coupled with an inorder traversal)—thus, this process is called the binary-tree sort.
The binary search tree facilitates duplicate elimination. As the tree is created, attempts to insert a duplicate value are recognized because a duplicate follows the same “go left” or “go right” decisions on each comparison that the original value did. Thus, the duplicate eventually is compared with a node containing the same value. The duplicate value may simply be discarded at this point.
21.3 | (Merging Ordered-List Objects) Write a program that merges two ordered-list objects of integers into a single ordered-list object of integers. Method | ||||||||||||
21.4 | (Reversing a Line of Text with a Stack) Write a program that inputs a line of text and uses a stack object to display the line reversed. | ||||||||||||
21.5 | (Palindromes) Write a program that uses a stack to determine whether a string is a palindrome (i.e., the string is spelled identically backward and forward). The program should ignore capitalization, spaces and punctuation. | ||||||||||||
21.6 | (Evaluating Expressions with a Stack) Stacks are used by compilers to evaluate expressions and generate machine-language code. In this and the next exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses. Humans generally write expressions like To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation, then evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its operation, and in each algorithm the stack is used for a different purpose. Here, you’ll implement the infix-to-postfix conversion algorithm. In the next exercise, you’ll implement the postfix-expression evaluation algorithm. In a later exercise, you’ll discover that code you write in this exercise can help you implement a complete working compiler. Write class (6 + 2) * 5 - 8 / 4 to a postfix expression. The postfix version of the preceding infix expression is 6 2 + 5 * 8 4 / - The program should read the expression into
The following arithmetic operations are allowed in an expression:
Some of the methods you may want to provide in your program follow:
| ||||||||||||
21.7 | (Evaluating a Postfix Expression with a Stack) Write class 6 2 + 5 * 8 4 / - The program should read a postfix expression consisting of digits and operators into a
[Note: In Part b above (based on the sample expression at the beginning of this exercise), if the operator is
You may want to provide the following methods:
| ||||||||||||
21.8 | (Level-Order Binary Tree-Traversal) The program of Fig. 21.21 illustrated three recursive methods of traversing a binary tree—inorder, preorder, and postorder traversals. This exercise presents the level-order traversal of a binary tree, in which the node values are displayed level by level, starting at the root-node level. The nodes on each level are displayed from left to right. The level-order traversal is not a recursive algorithm. It uses a queue object to control the output of the nodes. The algorithm is as follows:
|