Considerations for Cosequential Algorithms
- Initialization - What has to be set up for the main loop to work correctly.
- Getting the next item on each list - This should be simple and easy, from the main algorithm.
- Synchronization - Progress of access in the lists should be coordinated.
- Handling End-Of-File conditions - For a match, processing can stop when the end of any list is reached.
- Recognizing Errors - Items out of sequence can "break" the synchronization.
¶ 8.1.2 Matching Names in Two Lists
T E R M S
- match
- The process of forming a list containing all items common to two or more lists.
Cosequential Match Algorithm
- Initialize (open the input and output files.)
- Get the first item from each list.
- While there is more to do:
- Compare the current items from each list.
- If the items are equal,
- Process the item.
- Get the next item from each list.
- Set more to true iff none of this lists is at end of file.
- If the item from list A is less than the
item from list B,
- Get the next item from list A.
- Set more to true iff list A is not at end-of-file.
- If the item from list A is more than the
item from list B,
- Get the next item from list B.
- Set more to true iff list B is not at end-of-file.
- Finalize (close the files.)
Cosequential Match Code
void Match (char * InputName1,
char * InputName2,
char * OutputName) {
/* Local Declarations */
OrderedFile Input1;
OrderedFile Input2;
OrderedFile Output;
int Item1;
int Item2;
int more;
/* Initialization */
cout << "Data Matched:" << endl;
Input1.open (InputName1, ios::in);
Input2.open (InputName2, ios::in);
Output.open (OutputName, ios::out);
/* Algorithm */
Input1 >> Item1;
Input2 >> Item2;
more = Input1.good() && Input2.good();
while (more) {
cout << Item1 << ':' << Item2 << " => " << flush; /* DEMO only */
if (Item1 < Item2) {
Input1 >> Item1;
cout << '\n'; /* DEMO only */
} else if (Item1 > Item2) {
Input2 >> Item2;
cout << '\n'; /* DEMO only */
} else {
Output << Item1 << endl;
cout << Item1 << endl; /* DEMO only */
Input1 >> Item1;
Input2 >> Item2;
}
more = Input1.good() && Input2.good();
}
/* Finalization */
Input1.close ();
Input2.close ();
Output.close ();
}
Heaps
Logical Structue of a Heap
- A heap is a version of binary tree.
- A heap is ordered along each branch, from the root to any of the leaves.
- A heap is not ordered in the left-right method of a binary search tree.
- A heap is not ordered horizontally, within the tree levels.
- A heap is ordered vertically, from the leaves to the root.
- A heap is a complete binary tree.
- All levels of a heap are filled, except for the lowest.
- The lowest level is filled from left to right.
- The root of a heap is always the lowest (or highest) item in the heap.
Physical Structue of a Heap
- The nodes of a heap are stored physically in an array.
- The root of the tree is in the first element of the array.
- The children of the node at location n are at locations 2n and 2n + 1.
- The parent of the node at location n is at location
n/2
.
Building a Heap
- A heap is built by inserting elements at the end of the heap, as a
new leaf, and then "sifting up," sorting the branch from the new leaf to
the root.
- Example:
- Insert R: R
- Insert L: R L
-
- Sift L: L R
-
- Insert C: L R C
-
- Sift C: C R L
-
- Insert A: C R L A
-
- Sift A: A C L R
-
- Insert H: A C L R H
-
- Sift H: A C L R H
-
- Insert V: A C L R H V
-
- Sift V: A C L R H V
-
- Insert E: A C L R H V E
-
- Sift E: A C E R H V L
-
