Overview

We have learned several data structures that can support data storage and searching, including:

AVL tree (self-balancing binary search tree)

Hash table

Binary Heap (priority queue).

In this homework, we will write a C/C++ program to use these data structures. More exactly, your

program should accomplish the following tasks:

Tasks

Part 1: Read the words from a file to a linked list

A token is a sequence of letters. For example for the sentence:

That I could make those people dance,

And maybe they'd be happy for a while.

The sequence of words, described here as a string marked by double quotes, will be :

"That" "I" "could" "make" "those" "people" "dance" "And" "maybe" "they" "d" "be" "happy"

"for" "a" "while"

<Task 1.1>

Open an input file message.txt (provided with this homework). It includes a paragraph of the

lyrics of the song "American Pie" and an English article excerpt from the book "Tractatus LogicoPhilosophicus"

written by the philosopher Ludwig Wittgenstein.

<Task 1.2>

Read the sequence of words into a linked list

Each node of the linked list should contain a string, which is the word.

You can choose to use a C-string or a C++ string object.

Do not use some library of linked lists. The nodes should be defined in your code.

Hint: The provided code for reading a word can be useful.

<Task 1.3>

Print the words in the linked list. Maybe something like :

1) That --> 2) I --> 3) could --> 4) make --> 5) those --> 6) people --> 7)

dance --> 8) And --> 9) maybe --> 10) they --> 11) d --> 12) be --> 13) happy -->

14) for --> 15) a --> 16) while You can design the printing visual effect.

Part 2 AVL Tree Construction

<Task 2.1>

Insert the words in list (built in task 1.2) one by one into an AVL Tree

Each node in the tree should store:

A distinct word (case ignored, e.g., "The" is the same as "the").

The count of occurrences of the word.

Nodes are ordered alphabetically by the word (dictionary order).

<Task 2.2>

Print the tree.

Hint: the provided the helpful code of printing a tree can be useful.

<Task 2.3>

Print the words (with their occurrence number) in the tree, in ascending dictionary order.

Hint: using some traversal on the tree.

Part 3 Hash Table

Task 3.1

Build a Hash table. Insert the words of the list of task 1.2, one by one, into the list. Here are some

requirements:

Each item in the hash table should be a pair <word, count> , So, when trying to insert a

word again into the table, its count should increase.

The programmer can choose

the size of the hash table (array size).

a collision resolution strategy (separate chaining, linear probing, or quadratic probing).

Task 3.2

Search on the hash table 10 words that are in the input file. Also, seach 5 words that are not

in the input file

When a word is found, print the word together with its count.

When a word is not found, print a message like "The word is not found".

The printing result could be like: Part 4 : Binary Heap

<Task 4.1>

Build a binary heap where each node stores a pair <word, count> . Here are some description

The order between two pairs is defined as follows:

<word1, count1> is less than <word2, count2> if

count1 < count2

or, count1 == count2, but word1 < word2 by the dictionary order.

<Task 4.2>

Print the <word, count> pairs on the heap in an ascending order (the order is defined above).

Hint: Just pop the items from the binary heap and print them individually.

Submission

A most three students can form a group to do the assignment together. Only one student in

the group needs to submit the homework.

The files to be submitted on Moodle include:

A .zip file containing all the source code files of your program.

Proper modularization by dividing your program into multiple files is encouraged.

Putting all code in one text file is not good for this assignment.

A text report file. The format can be (.docx, pdf, etc.). The file should describe

What tasks have you accomplished? What are the remaining problems?

The cooperation and workload sharing among the members of the group.

Anything you want to describe, like the troubles you met and how you dealt with

the problems.

For the submission deadline, see the setting of this homework on the Moodle webpage.

Search: facts       Found, Count: 3

Search: picture     Found, Count: 2

Search: logical     Found, Count: 2

Search: world       Found, Count: 2

Search: truth       Found, Count: 1

Search: representation Found, Count: 1

Search: philosophy   Not found

Search: language     Not found

Search: model       Found, Count: 1

Search: science     Not found