SIBT COMP 125

Week 7 Tutorial Exercises

Exercises

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