The final lab has three challenging exercises on the focal topic of this course: advanced data structures
-
(Linked Lists) Write a program called llmax.c that:
- reads numbers from stdin
- inserts these numbers into a linked list
- prints the linked list
- prints all nodes in the list starting from the largest number in the list
If the largest number occurs more than once in the list, print all nodes starting from the first occurrence of the largest number.
A testcase showing execution of the program is:
prompt$ echo "4 1 4 2 3" | ./llmax
Original list = 1->4->2->3
Truncated list = 4->2->3
|
Notice here that the first number, 4, indicates the size of the list only. More examples are:
prompt$ echo "6 5 10 14 1921 14 2" | ./llmax
Original list = 5->10->14->1921->14->2
Truncated list = 1921->14->2
|
prompt$ echo "17 2 2 4 4 4 6 4 8 6 10 6 2 4 10 2 10 10" | ./llmax
Original list = 2->2->4->4->4->6->4->8->6->10->6->2->4->10->2->10->10
Truncated list = 10->6->2->4->10->2->10->10
|
prompt$ echo "2 1 2" | ./llmax
Original list = 1->2
Truncated list = 2
|
prompt$ echo "1 13" | ./llmax
Original list = 13
Truncated list = 13
|
prompt$ echo "20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1" | ./llmax
Original list = 1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1
Truncated list = 1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1
|
If there are not enough numbers, then the result is:
prompt$ echo "3 1 2" | ./llmax
Data missing
|
If the first data is not numerical, then the result is:
prompt$ echo "xx 1" | ./llmax
No data
|
Finally, if there is no data then:
prompt$ echo "" | ./llmax
No data
|
The only data structure that you may use in your program is a single singly-linked list.
-
(Linked Lists) Write a program called llunique.c that:
- reads numbers from stdin
- inserts these numbers into a linked list
- prints the linked list
- removes all numbers that occur more than once in the list
- prints the resulting linked list
A number is repeated if it appears anywhere else in the list: all instances of repeated numbers should be removed, including(!) the first occurrence of each such number. For example:
prompt$ echo "10 1 2 3 1 2 3 4 5 6 7" | ./llunique
Original list = 1->2->3->1->2->3->4->5->6->7
Unique list = 4->5->6->7
|
Notice that the numbers 1, 2 and 3 occur more than once in the original list and hence are not in the resulting list. Notice also that, as usual,
the first number on stdin indicates the size of the list only.
More testcases are:
prompt$ echo "6 5 10 14 1921 14 2" | ./llunique
Original list = 5->10->14->1921->14->2
Unique list = 5->10->1921->2
|
prompt$ echo "1 13" | ./llunique
Original list = 13
Unique list = 13
|
prompt$ echo "20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1" | ./llunique
Original list = 1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1
Unique list is empty
|
As before, if there are not enough numbers, then the result is:
prompt$ echo "3 1 2" | ./llunique
Data missing
|
If the first data is not numerical, then the result is:
prompt$ echo "xx 1" | ./llunique
No data
|
Finally, if there is no data then:
prompt$ echo "" | ./llunique
No data
|
As before, the only data structure that you may use in your program is a single singly-linked list.
-
(Quacks, Binary search trees) Write a program called bfsTreeQ.c that traverses a BST using breadth-first search (BFS). BFS means to visit the nodes level by level: start with the root, then all nodes at level 1, then all nodes at level 2 etc.
Given a queue and a tree of nodes, an algorithm to traverse the nodes in BFS order is:
initialise the queue with the root node of the tree
for as long as the queue is not empty
dequeue an element
enqueue all its children (if any)
|
- this algorithm dequeues the elements in BFS order
- you should therefore use the Quack ADT as a queue:
- qush() to enqueue an element
- pop() to dequeue an element
- note that to enqueue a node you should qush() the value of a pointer, i.e. an address
- which requires to cast an address as an int (on a CSE lab computer) when using the Quack ADT
- and to recast it as a pointer when dequeuing the integer
The input of your program should come from the command line. These numbers should be inserted into a BST. The output of the program is the BST pretty-printed in the normal way (using printTree()), followed by the list of nodes in the tree in BFS order. Example testcases are the following:
prompt$ ./bfsTreeQ 2 1 3
1
2
3
BFS order = 2 1 3
|
prompt$ ./bfsTreeQ 8 4 6 2 7 5 3 1 12 10 9 14 13 11 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BFS order = 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15
|
prompt$ ./bfsTreeQ 6 5 4 3 2 1
1
2
3
4
5
6
BFS order = 6 5 4 3 2 1
|
prompt$ ./bfsTreeQ 1 2 3 4 5 6
1
2
3
4
5
6
BFS order = 1 2 3 4 5 6
|
prompt$ ./bfsTreeQ 5 6 7 1 2 3 4
1
2
3
4
5
6
7
BFS order = 5 1 6 2 7 3 4
|
prompt$ ./bfsTreeQ 7
7
BFS order = 7
|
If there is no argument on the command line, the error message should be:
prompt$ ./bfsTreeQ
Usage: ./bfsTreeQ integers ...
|
If there are any problems with reading the command line, the error message should be:
prompt$ ./bfsTreeQ 3 10 a
Usage: ./bfsTreeQ integers ...
|