1. Recall in lectures that we were building up a linked list class and on our way to that goal, we constructed an intermediate class called INT_LIST. This class models simple (singly) linked lists and acts as a useful interface for using the NODE class. The attributes (that is, data features) of INT_LIST are first (a reference to the first node of the current list), last (a reference to the last node of the current list) and count (the number of elements in the current list). The routines of INT_LIST that we have seen so far are make (which creates an empty list), append(v) (which appends a node containing integer v to the end of the current list). [Note: In lectures I omitted the make procedure since it really does nothing. I have included it in the class here since having a creation procedure, even a dummy one, is good programming style].
Write the following function which could be included in the class INT_LIST:
present(x : G) : boolean
This function is supposed to return true if and only if x is in the current list.
Write a short test class that uses INT_LIST to show you understand how to use the function you have written. For example, suppose that a linked list L has already been built and a user wishes to be informed as to whether or not a certain integer `query' is present in L. Write a few lines to satisfy the user's wish.
2. Write the following procedure which could also be included in the class INT_LIST:
insert_after(x : integer ; y : integer)
This procedure inserts a node containing y after the first occurrence of x in the current list, if x is present in the list, and does nothing otherwise.
3. 1999 Semester 2 Mid-Semester Exam, Question 6 (reprinted here because so few people can be bothered reading these questions before they come to class and bringing the appropriate printouts). [Note: There is a small difference between the code given here and the code that appears in lectures. This was a minor error, but we decided to leave it in an see how people worked around it].
(a) (8 marks)
During lectures we looked at the NODE class and examined how we could use this class to create simple linked lists of objects. Complete the procedure build_list in the program, APPLICATION (shown below), so that it will store the characters of the input string in a linked list of character nodes.
(b) (12 marks)
Write a function find_character (ch:CHARACTER):BOOLEAN which will search the linked list of character nodes and return TRUE if the character ch exists in the list.
class APPLICATION
creation
main
feature
L : NODE[CHARACTER]
main is
local
temp_string : STRING
temp_char : CHARACTER
do
io.put_string ("Please enter a string: ")
io.read_line
temp_string := io.last_string
build_list(temp_string)
io.put_string ("Please enter a character: ")
io.read_character
temp_char := io.last_character
if find_character(temp_char) then
io.put_string ("This character appears in the string")
else
io.put_string ("This character doesn’t appear in the string")
end --if
end --main
build_list (str : STRING) is
local
num : INTEGER
last, new_node : NODE
do
from
num := 1
until
num > str.count
loop
--fill in code here
end --loop
end --build_list
find_character (ch:CHARACTER):BOOLEAN is
--fill in code here
end --find_character
end --APPLICATION