Wednesday, November 1
Getting a segmentation fault?
If you are getting a segmentation fault when you run the program, it
may be because you are trying to dereference a NULL or dangling pointer.
As noted in lecture and the lecture slides, you should look at every
place where a pointer is being dereferenced in your code, and see if
you can argue that there is no chance that the pointer is NULL or dangling.
On a somewhat related note, you can find a
definition of segmentation fault at this
mirror of the New Hacker's Dictionary. That site also explains the
eytmology of 'foo', if you are interested in such trivia.
Tuesday, October 31
Compiling the assignment and doing a sanity check
A main.c that performs a sanity check
on the Dictionary type and functions is now available.
(This is different from the main.c supplied with the starter
code.)
Assuming that you have correctly implemented all the functions, you
should get this output. Note that in the first
part of the output, the words are printed in alphabetical order, as
the keys of the Dictionary's internal BST
are visited in order.
The BST should be able to store ANY type of data
If you specifically mention Strings or Lists
in your BST code, that is bad (X). The BST should not be
restricted to storing only Strings and Lists.
Conceivably, you should be able to reuse the same BST code
if you were to store other key-value pairs (such as student records
and marks arrays). That is why the keys and values are of type void*,
to let you store anything.
Monday, October 30
For bstInsert, if the key to be inserted
already exists in the tree, then do not allow this key (and its accompanying
value) to be inserted
This way, you can avoid insertion of duplicate keys.
Do not use assert to disallow the duplicate key
insertion; just ignore the insertion entirely by having your function
do nothing.
Return value of function pointed to by compareKeys
(in BST)
compareKeys will point to a comparison function like stringCompare
(if you look at the Dictionary code, you'll see that its
internal BST is initialized so that this is the case).
If this function is passed two arguments k1 and k2
(in that order) then it will return:
== 0, if k1 == k2< 0, if k1 < k2> 0, if k1 > k2
Note that this comparison function compares the contents of
the two arguments. A function like stringCompare tells
you whether the word k1 appears in the dictionary before
k2 (lexicographical order, which is essentially alphabetical
order).
When the Dictionary uses the BST,
the words are the keys, and the definitions are the values, but you
have to be careful about how you store the definitions
Your Dictionary cannot store multiple definitions for
a word in separate BST nodes, because each of these nodes
would have the same key (word). (Hint: Use the List type
and functions.)
Saturday, October 28
Ignore warning message about dictionaryInit
and bstInit
If you compile the original starter code without modifications, you
may get the following warning message:
dictionary.c: In function 'dictionaryInit':
dictionary.c:18: warning: passing arg 1 of 'bstInit' from incompatible pointer type
The problem described by this message will not prevent your code from
working properly. However, the starter code has been fixed so that this
warning message will no longer appear: You will need to download new
versions of utility.c and
utility.h.
The BST must be implemented correctly
This entails, among other things, that:
- the BST must satisfy the BST Property
- the pointers for each BST node (
left, right
and parent) must be set to the appropriate values
- no two nodes in the BST share the same keys; i.e. the keys inserted
into the BST are unique
Testing of the BST module will be carried out separately
from testing of the Dictionary module, to verify the correctness
of the BST implementation.
Assume the words entered into the dictionary are
lowercase
For example, "mellifluous" and "sack" are legal
words for the dictionary, but "MeLLiFLuouS" and "sAck"
are not.
|