CSC2059 Data structures and Algorithms - Practical 5: Lists
Practical 5: Lists
Acknowledgement
The practical is based on the module material of Prof. Ji Ming and maintained by Muhammad Fahim and module team.
Launch Visual Studio.
Create a new Solution Practical5 and name the first project List1.
Exercise 1. Linked List class expansion
In this project, we will add new member functions into the List class to expand this class. Download the provided template classes ListNode.h and List.h, and add these classes into the project List1.
(1) Inside the List class, add a new public function void print();
which prints the data items of the list nodes in a list object, from the first node to the last node.
(2) Inside the List class, add a new public function bool remove(int p1, int p2);
This function is an extension of the member function int remove(int p); which removes a node in a list at position p. The new function will remove a range of nodes from position p1 to position p2 (inclusive). It returns true for successful removal and false for illegal parameters p1 and/or p2.
(3) Create a test1.cpp in the project and use the following main function to test the above new member functions. The expected outputs are shown below the test function.
int main() {
}
// create an alphabet list
List<char> chlist;
for (int i = 0; i < 26; i++)
chlist.insert_end(97 + i);
// print chlist
chlist.print();
// remove nodes from 22-25
if (chlist.remove(22, 25)) chlist.print();
// remove nodes from 0-3
if (chlist.remove(0, 3)) chlist.print();
// remove nodes from 5-10
if (chlist.remove(5, 10)) chlist.print();
return 0;
Exercise 2. Linked List for storage of data with an unknown size
In solution Practical5 add a new project List2, in which create a source file test2.cpp. Download the provided corpus.txt file and place it into the List2 folder along with the test2.cpp file. Add the template classes ListNode.h and List.h into the project.
The following shows an incomplete program, showing the use of a linked list (an object of our List class) for loading data of an unknown size into the program. The program uses C++ file I/O classes for opening the corpus file for reading the data into a linked list, each list node storing a word. To use the class you need to #include <fstream>.
As you can notice, the corpus contains many word items which include some non-alphabetic character(s), e.g., \’, \-, \., \,, \”, \&, \%, \; .... There is also a sentence code (e.g., 011a0101) at the beginning of each sentence which is not a word. You should ignore all these items and only store the proper words, in which each character is an alphabetic letter, in the list.
You are asked to complete this program, in test2.cpp, by completing the missing parts indicated by points 1-4 in the program. After execution, your program should print out the number of the proper words in this corpus file.
Hint: You will find it useful to write a function for testing for proper words (and non-proper words):
bool isWord(string item);
The incomplete program with missing parts indicated by 1-4
int main() {
// allocate a string-type list pointed to by pc, used to store all // words in the corpus
List<string>* pc = new List<string>;
// open the corpus.txt file for input
ifstream fi("corpus.txt");
string item;
// read each item in the file separated by space until the end of the file while (fi >> item) {
// 1. test if the read item is a word - with only letters and // no other characters
// 2. if yes insert the word into the list pointed by pc
}
// close the file
fi.close();
// 3. print the size of the list
// 4. free the memory used to store the corpus return 0;
}
