Reference no: EM131794719
Extend the program in Problem 26, so that an ordered linked list of all occurrences of each word is stored. When the concordance is searched for a particular word, the program should display the line (or page) numbers of all occurrences of this word.
The data structure used for the concordance is thus constructed from a good sample of those we have been studying: an array of binary search trees, each of whose nodes is a class, one of whose members is a string and whose other member is an ordered linked list.
Problem 26,
Programming Problems 20-22 at the end of Chapter 11 ask for a program to construct a text concordance, which is an alphabetical listing of all the distinct words in a piece of text. The basic storage structure for such a concordance was an array of ordered linked lists, one for words beginning with A, another for words beginning with B, and so on.
Write a program that reads a piece of text, constructs a concordance that contains the distinct words that appear in the text and, for each word, the line (or page) number of its first occurrence, and then allows the user to search for this concordance. Use an array of BSTs as storage for the concordance.
Problem 20,
Test the function 1eve1ByLeve10 of Exercise 27. Generate binary trees using the function generate BSTO in Problem 14, and then traverse them using 1evel By Level O.
Exercise 27,
Write a function 1eve1ByLeve10 to traverse a tree level by level; that is, first visit the root, then all nodes on level 1 (children of the root), then all nodes on level 2, and so on. Nodes on the same level should be visited in order from left to right. (Hint: Write a no recursive function, and use a queue of pointers.)
Problem 21,
In this section, binary search trees were implemented using pointers, but it also is possible to use an array-based implementation, similar to that for linked lists described in Section 6.6. In this implementation, each node is represented as a class Bi n Node and the BST is stored in an array of Bi n Nodes.
Each Bi n Node object contains three data members: one to store data and two link members that point to the left and the right child, respectively, by storing their indices in the array. Imitating the array-based implementation of linked lists in Section 6.6, do the following:
a. Write appropriate declarations for this array-based implementation of binary search trees.
b. Design and test a class for maintaining a storage pool of available nodes, with operations to initialize it, to get a node from it, and to return a node to it.
Problem 22,
Assuming the array-based implementation of BSTs in Problem 21, write and test a function member search () for searching a BST.
Problem 21,
In this section, binary search trees were implemented using pointers, but it also is possible to use an array-based implementation, similar to that for linked lists described in Section 6.6. In this implementation, each node is represented as a class Bi n Node and the BST is stored in an array of Bi n Nodes.
Each Bi n Node object contains three data members: one to store data and two link members that point to the left and the right child, respectively, by storing their indices in the array. Imitating the array-based implementation of linked lists in Section 6.6, do the following:
a. Write appropriate declarations for this array-based implementation of binary search trees.
b. Design and test a class for maintaining a storage pool of available nodes, with operations to initialize it, to get a node from it, and to return a node to it.