Description
In this homework, you are asked to implement a simple word processor that will read two words
from two different files and store them in two linked lists character by character. Your program
will also process these lists by reading certain commands such as for inserting, deleting characters
and finding the level of similarity between two words. After each command, some outputs
regarding the operation will be displayed. The program details will be explained in the subsequent
sections.
The Data Structure to be used
In this homework, you must use linked list (regular one-way linked list) as your main data
structure. The node struct of this list must have the following data members (if you want, you can
add constructors to the struct).
struct node
{
char ch;
node * next;
};
Figure 1. The minimal data members that the node should have© Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
In this struct, ch stores one character of a word, and next pointer points to the next node in the
linked list.
You are not allowed to use arrays, vectors or any similar containers (including files) in this
homework; all data must be stored and processed within the linked list structure.
Moreover, you are not allowed to use string to store the data that you will read from the
files; strings can only be used to read the file names and the commands/arguments from the
keyboard.
The input data will be given to the program using text files. A screenshot of a sample input file
named in1.txt and the final structure of the linked list after reading the letters from this file are
shown in
Figure 2.
Figure 2. A visualization of a linked list (pointed by head1) after reading the data from input file
“in1.txt”(screenshot on the right) and storing all of the characters in the nodes
A screenshot of a sample input file named in1.txt and the final structure of the linked list after
reading the letters from this file are shown in Figure 3.
Figure 3 A visualization of a linked list (pointed by head2) after reading the data from input file
“in2.txt”(screenshot on the right) and storing all of the characters in the nodes
Reading the Files and Creating the Linked Lists
Your program will start by asking the user to enter two file names, one by one. For each of these files, first
you should check if it is opened successfully or not. If not opened, you have to read another file name.
Then, your program should read the contents of these two files and store each file’s content in a separate
linked list character by character as described above. © Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
Each file has one word, which is lined up vertically and each line has only one character. This is an
assumption and you do not have to make an input check for this. We also assume that:
The file does not contain empty lines or whitespaces.
The file contains only lowercase English letters (i.e., from a to z).
The file may contain duplicate letters.
The file is not empty and may contain any number of letters.
These are the assumptions and you do not need to make an input check for the content of the files (but
there will be some input checks for the commands and arguments as detailed below).
In order to store the contents of two files, you need to have two different linked lists with different head
pointers. For each of the files, you will read file’s content line by line (i.e. letter by letter) and append each
letter read to the end of the corresponding linked list. After that, your linked lists become ready to be
processed with some commands as described below.
Operations/Commands to be Performed on the Linked Lists
After reading the data from the two files and storing them in two linked lists, first, you have to display the
contents of the lists one by one. After that, your program will keep asking the user to enter a command
followed by its arguments, if any. Basically, these commands are for inserting and deleting characters from
the linked lists, finding similarity between two lists, and for exiting the program. Insertion and deletion
commands also indicate the linked list number that this operation will be performed on (i.e., whether it is
the linked list 1 or the linked list 2). Thus, we have a total of six commands that your program should
support: del1, del2, insert1, insert2, sim, and exit.
del1 and del2 commands are followed by one argument, which is the letter to be deleted from the
corresponding list. This command will delete all of the nodes that contain the given letter in the
argument from the specified linked list. For example, if the list contains l l a m a and if the
argument is l, then the list will contain a m a. As another example, if another list contains
g o o g l e, and if the argument was g then the list will contain o o l e.
If the letter to be deleted does not exist in the list, then nothing will be deleted and a message that
explains this has to be displayed. You have to display an output about the operation details and the
content of the list after deletion. Please see the sample runs for example outputs. Other details about
deletion are as follows.
o del1 will apply the deletion operation on the linked list 1.
o del2 will apply the deletion operation on the linked list 2.
o The command and argument are separated by at least one whitespace and the argument is
only one character. These are assumptions and you do not need to make input check for
those.
o The argument should be a lowercase letter and you have to do an input check for this.
insert1 and insert2 commands are followed by two arguments, which have to be lowercase English
letters. The first argument indicates the letter to be inserted after the first occurrence (just after first
occurrence, not after all of the occurrences) of a node that contains the letter specified as the second
argument. If the linked list does not contain a node with the second argument, then the program
should insert the node that contains the first argument to the beginning of the linked list (i.e., it will
become the head node). For example, if the list contains a l b a l a and if the arguments are
t and l, then after insertion the list will contain a l t b a l a. As another example, suppose
you insert once again to this updated list with arguments b and s; the list will contain© Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
b a l t b a l a after insertion; here we inserted b to the beginning since there was no s.
You have to display an output about the operation details and the content of the list after insertion.
Please see the sample runs for example outputs. Other details about insertion are as follows.
o insert1 will apply the insertion operation on linked list 1.
o insert2 will apply the insertion operation on linked list 2.
o The command and the arguments are separated by at least one whitespace and each
argument is only one character. These are assumptions and you do not need to make input
check for those.
o The arguments should be lowercase letters and you have to do input check for this.
sim does not take any argument. It is an abbreviation for similarity, and when the user enters this
command the program will count and display the total number of matching letters in the same
positions in both lists. For example, if the first list contains a l k i and the second list contains
e l t i k, the similarity value is 2 since the letters l and i match in the same positions. This
command should display this similarity value and also the current contents of the lists. Here be
careful that the lists may have different sizes, so you have to stop checking once you reach NULL
in one of them.
exit command indicates that the program will end. At this point, the program will stop asking the
user for more commands and clear both of the lists by properly deleting all the memory allocated
for them.
If the user enters an invalid command and/or invalid argument(s), your program should give an error
message and continue by reading new commands and arguments.
If the command is entered correctly, you may assume that the number of arguments is also correct (no input
check needed); that means please assume that there are two arguments for insertion, one argument for
deletion and no argument for similarity and exit. The only input check for the arguments is that they have
to be lowercase letters (as mentioned above).
You have to ignore all of the extra characters that might appear after an invalid command in the input line
so that the next command is read fresh. You can do so by using the command
cin.ignore(numeric_limits<streamsize>::max(),’\n’);
CAUTION
One of the lists or both of them may become empty during the execution of the program due to delete
operations. Your program should keep processing commands in such a case as well. Please note that if one
or both of the lists is/are empty, then similarity value should be zero, by definition of similarity. © Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
Walk-through Example
A walk-through run of the program is shown in Table 1. The example given in the table assumes that data
from in1.txt and in2.txt have been successfully read and stored in two different linked lists.
Table 1 A walk-through example
Command Argum
ents (if
any)
Effect on the corresponding linked list
Explanation
sim
sim command will
display the similarity
value (2 in this case)
and the contents of the
linked lists without
changing them.
del1
h
Deleting all
occurrences of letter
‘h’ from linked list 1
insert1
k m
Inserting a node with
letter ‘k’ after the
node with letter ‘m’ in
linked list 1
insert1
k f
Inserting a node with
letter ‘k’ at the
beginning (i.e., to the
head) of the linked list
because no node with
letter ‘f’ exists in
linked list 1
insert2
h e
Inserting a node with
letter ‘h’ after the
node with letter ‘e’ in
linked list 2
insert2
m h
Inserting a node with
letter ‘m’ after the
first occurrence of a
node with letter ‘h’
sim
sim command will
display the similarity
value (0 in this case)
and the contents of the
linked lists without
changing them.
exit
The program will stop
asking for further
commands and will
delete the two lists and
terminate.© Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
File with name ‘in1’ does not exist. So, the program asks again for a valid file
name. Same for file 2 name, the program kept asking for a valid file name
go sim is considered as invalid command
as the first word is not one of the valid
commands
insert 1 u o is invalid
command as the valid
commands for insertion into
the linked list 1 is insert1 as
a single word. Same for
insert2 with linked list 2
del2 E is invalid argument
as E is uppercase
A message to show that no deletion
has been done when the item to be
deleted is not in the list
Sample Runs
Sample runs are given below, but these are not comprehensive, therefore you have to consider all possible
cases to get full mark. Inputs are shown in bold and italic.
Sample Run 1:
Please enter the file 1 name: in1
Please enter the file 1 name: in1.txt
Please enter the file 2 name: in2.text
Please enter the file 2 name: in2.txt
List1: home
List2: house
Enter a command and its corresponding argument(s), if any: go sim
Invalid command.
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: home
List2: house
There is/are 2 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: insert u o
Invalid command.
Enter a command and its corresponding argument(s), if any: insert 1 u o
Invalid command.
Enter a command and its corresponding argument(s), if any: insert1 u o
Inserting u after o in List1.
The node with o has been inserted after the first occurrence of a node with u value.
The current content of List1 is: houme
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: houme
List2: house
There is/are 4 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: del2 E
Invalid arguments.
Enter a command and its corresponding argument(s), if any: del2 e
Deleting all occurrences of e in List2.
The current content of List2 is: hous
Enter a command and its corresponding argument(s), if any: del1 k
No deletion as the value k was not found in the list
Enter a command and its corresponding argument(s), if any: del1 m
Deleting all occurrences of m in List1.
The current content of List1 is: houe
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: houe
List2: hous
There is/are 3 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: exit© Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
Displaying the contents of the lists one by one, after reading the
data from the two files and storing them in two linked lists.
List 1 became empty after several del1 operations
List 2 became empty after several del2 operations
Clearing the two lists and saying Goodbye!
Sample Run 2:
Please enter the file 1 name: in11.txt
Please enter the file 2 name: in8.txt
List1: llama
List2: bubble
Enter a command and its corresponding argument(s), if any: del1 a
Deleting all occurrences of a in List1.
The current content of List1 is: llm
Enter a command and its corresponding argument(s), if any: del2 b
Deleting all occurrences of b in List2.
The current content of List2 is: ule
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: llm
List2: ule
There is/are 1 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: del1 l
Deleting all occurrences of l in List1.
The current content of List1 is: m
Enter a command and its corresponding argument(s), if any: del1 m
Deleting all occurrences of m in List1.
The current content of List1 is:
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1:
List2: ule
There is/are 0 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: del2 u
Deleting all occurrences of u in List2.
The current content of List2 is: le
Enter a command and its corresponding argument(s), if any: del2 l
Deleting all occurrences of l in List2.
The current content of List2 is: e
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1:
List2: e
There is/are 0 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: del2 e
Deleting all occurrences of e in List2.
The current content of List2 is:
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1:
List2:
There is/are 0 letter(s) matched in the same positions in both lists.© Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
Inserting to list 1 after it became empty. Your program should support that case.
Inserting to list 2 after it became empty. Your program should support that case.
Similarity value
between an empty
and a non-empty
list is zero.
Similarity
value between
two empty lists
is zero.
Enter a command and its corresponding argument(s), if any: insert1 a h
Inserting a after h in List1.
The node with h value does not exist. Therefore, Inserting a at the beginning of the list.
The current content of List1 is: a
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: a
List2:
There is/are 0 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: del2 j
No deletion as the value j was not found in the list
Enter a command and its corresponding argument(s), if any: insert2 o p
Inserting o after p in List2.
The node with p value does not exist. Therefore, Inserting o at the beginning of the list.
The current content of List2 is: o
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: a
List2: o
There is/are 0 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: exit
Clearing the two lists and saying Goodbye!
Sample Run 3:
Please enter the file 1 name: in5.txt
Please enter the file 2 name: in6.txt
List1: wow
List2: odd
Enter a command and its corresponding argument(s), if any: del1 w
Deleting all occurrences of w in List1.
The current content of List1 is: o
Enter a command and its corresponding argument(s), if any: del1 o
Deleting all occurrences of o in List1.
The current content of List1 is:
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1:
List2: odd
There is/are 0 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: del2 o
Deleting all occurrences of o in List2.
The current content of List2 is: dd
Enter a command and its corresponding argument(s), if any: del2 d
Deleting all occurrences of d in List2.
The current content of List2 is:
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1:
List2:© Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
There is/are 0 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: insert1 m b
Inserting m after b in List1.
The node with b value does not exist. Therefore, Inserting m at the beginning of the list.
The current content of List1 is: m
Enter a command and its corresponding argument(s), if any: insert2 k r
Inserting k after r in List2.
The node with r value does not exist. Therefore, Inserting k at the beginning of the list.
The current content of List2 is: k
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: m
List2: k
There is/are 0 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: insert2 m u
Inserting m after u in List2.
The node with u value does not exist. Therefore, Inserting m at the beginning of the list.
The current content of List2 is: mk
Enter a command and its corresponding argument(s), if any: sim
Displaying the contents of the two lists:
List1: m
List2: mk
There is/are 1 letter(s) matched in the same positions in both lists.
Enter a command and its corresponding argument(s), if any: exit
Clearing the two lists and saying Goodbye!© Sabancı University, unauthorized reproduction, usage, posting are strictly prohibited
