Homework #4

The C Programming Language

The purpose of this question is for you to practise using pointers, dynamic storage allocation, and recursion.

Your program is to read input from the standard input. The input will be a series of lines, each with exactly one integer per line (there may be leading and/or trailing whitespace, but there will be only one number per line on well-formed input). Your program will insert each number into two different storage structures, one a linked list, and the other a binary tree. The numbers are to be inserted so that they are sorted. The program continues until there is no more input. It then prints the following data for each storage structure:

number of integers read
number of nodes in the storage structure
number of nodes visited to insert all the integers
mean number of nodes visited for each insertion
maximum number of nodes visited for any insertion

For example, suppose the input integers are 2, 5, 7, 3, 5, and 1 (in that order). Then your program would print

For the linked list:
6 integers read
5 nodes in the linked list
9 nodes visited to insert integers
1.5 nodes visited per insertion on the average
3 nodes visited in the worst case

For the binary tree:
6 integers read
5 nodes in the binary tree
8 nodes visited to insert integers
1.33 nodes visited per insertion on the average
2 nodes visited in the worst case

Notes: For the linked list, the list grows as: 2, 25, 257, 2357, 2357, 12357. To insert the integers, inserting 2 checks 0 nodes, 5 checks 1 node (the one containing 2). 7 checks 2 (2 and 5), 3 checks 2 (2 and 5), 5 checks 3 (2, 3, and 5), and 1 checks 1 (2). The total number of nodes checked is 0 + 1 + 2 + 2 + 3 + 1 = 9. That is 9/6 = 1.5 nodes visited per integer, on the average; and the most nodes checked to insert any single integer is 3 (to insert 5).

For the binary tree, inserting 2 checks 0 nodes, 5 checks 1 node (the one containing 2), 7 checks 2 nodes (2 and 5), 3 checks 2 (2 and 5), 5 checks 2 (2 and 5), and 1 checks 1 (2). The total number of nodes checked is 0 + 1 + 2 + 2 + 2 + 1 = 8. That is 8/6 = 1.33 nodes visited per integer, on the average; and the most nodes checked to insert any single integer is 2 (to insert 7, 3, and 5).