Monash University > CSSE > CSE1303 > Part A> Pracs > Prac A5

CSE1303 Computer Science
Semester 2, 2003
Part A
Prac A5 : Binary Search Trees

This prac covers material from lectures A11 to A13 and Tutorial A5.

Project

To write a program to find anagrams.

Background

An anagram of a word is a rearrangement of the letters in the word, in order to form a different word. For example tear, rate, and tare are all anagrams of each other - they all use the same letters, just in a different order.

In this practical session you will use a Binary Search Tree to implement a database for storing character strings. Then you will use this database in a program to find anagrams.

Preparation (3 marks if completed before class)

The marks for Preparation will be awarded only if the preparation is complete before the start of the class.

1. Find the anagrams of:
   1. least
   2. heir

2. Modify the code for a Binary Search Tree given in lectures, so that instead of holding numbers of type float it holds an address of a character string.

   Note: You must use the function strdup to make a copy of each character string in function makeNode. If your C libraries do not contain a copy of strdup(), use the one given in the solutions for Tute 3.

3. Write a C program which uses a Binary Search Tree to store character strings, and has a menu with the following options:
   1. Read String which asks the user for a character string, and stores the character string in the Binary Search Tree.
   2. List which prints out all the character strings stored in the Binary Search Tree in alphabetical order.
   3. Quit which allows the user to quit the menu and exit the program.

   Notes:You may assume all character strings have at most 30 characters.
             Deallocate any memory allocated when it is no longer required.

Question 1: (2 marks)

Modify your C program you wrote for the preparation to have the following functions and options:

1. Read File which asks the user for a filename, opens the file, and stores all the character strings in the file in the Binary Search Tree.

2. Search which asks the user for a character string, and then prints a message indicating whether or not the string is contained in the Binary Search Tree.

3. List which prints out all the character strings stored in the Binary Search Tree in alphabetical order.

4. Quit which allows the user to quit the menu and exit the program.

Question 2: (2 marks)

Write the following two C functions and a C program which demonstrates that the two functions work.

1. char* doubleString(char* str) which creates a new character string which contains a copy of str followed by a space, followed by another copy of str concatenated together, and returns the address of the new string. For example, when given the string "spot" it return the address to the character string , "spot spot".

2. void sortString(char* str, int size) which sorts the letters of the string, of length size, into alphabetical order using insertion sort. For example, when given the string "spot" and 4 as input, on return the string would be "opst"

   For question 3 you will need to sort the first part of the doubled string (for example, you would sort the first 4 characters of "spot spot" to get "opst spot"), so keep this in mind when you write your functions.

Question 3: (3 marks)

Change the program you wrote in Question 1, so that the program has a menu with the following options:

1. Read which asks the user for a filename and opens the file. Then for each word in the file stores into the Binary Search Tree a character string, consisting of:
   • the letters of the word sorted in alphabetical order,
   • followed by a space,
   • followed by a copy of the word.

   For example instead of storing the words spot, pots, act, and cat, it inserts the strings, "opst spot", "opst pots", "act act", and "act cat" into the Binary Search Tree.
   (use the function you wrote for Question 2b to do the sorting)

2. Search which asks the user for a word, and then prints the second half of any string (the part after the space) in the Binary Search Tree whose first half is the word sorted alphabetically.

   For example if "opst spot", "opst pots", "act act", and "act cat" were the only strings contained in the Binary Search Tree, and the user gave the word , "spot", the program should print "spot" and "pots".

   Note: this option is finding all the anagrams of the given word, so you can't just use binary tree search (it only finds one entry). You can still use the binary tree search to find the first occurance, and then do a traversal of the subtree from that node to find all of the anagrams.

3. Quit which allows the user to quit the menu and exit the program.

Important: Test your program on the file words.txt, which can found at http://www.csse.monash.edu.au/courseware/cse1303s/parta/prac/a5/words.txt, and find the anagrams of subessential.

Advanced Questions: (2 marks)

As you can see, storing anagrams in a tree is not efficient, especially as you need to step through a number of nodes to find the anagrams of a word!
A better way of storing anagrams would be to store the sorted string of a word as a key in the Binary search tree, and inside the node have a linked list of the words that form anagrams.

The list node and tree node structures would then look something like:

typedef struct ListNodeRec
{
   char *word;
   struct ListNodeRec next;
} ListNode;

typedef struct NodeRec
{
   char *key;
   ListNode* list;
   struct NodeRec leftPtr;
   struct NodeRec rightPtr;
} Node;

When you are inserting a new anagram into the tree, you need to search for the sorted string, and if it doesn't exist in the tree, create and insert a new node, with the sorted string as the key, and the original word as the first node in the list. If the sorted version of the word is in the tree, you simply need to add the word to the list inside the tree node where you found the sorted anagram.

Questions:

1. Write an improved Binary Search Tree implementation for storing and finding anagrams, using a linked list in each tree node to store the anagrams, and store the alphabetised string as the key in each tree node. Make sure all of the menu options still work.

   For example, a node would look like:
   

[ Top | Home ]

Last modified: Thursday 26 June 2003 14:42:13