Software Engineering II: Algorithms and Data Structures - Assignment 1
The aim of the assignment is to test students' ability to operate with file I/O, dynamically allocate
memory, use a list structure to store the data, apply a sorting algorithm on this structure, insert a
new element, delete an element from this structure, and final y apply some processing on this
The objective of the assignment is for the student to understand the advantages and disadvantages
of using a list structure compared to the use of an array structure for manipulation of the data.
Please note that you should build up your data structure from scratch (do not use the existing list
container of C++). This restriction applies only for the main list structure of your program (i.e. the
data structure that holds your data). You can use the available containers if you wish for reading or
writing the data to the files.
You have to write a program that operates on a list. Initial y, each element of the list is a structure
that contains two data fields (apart from the pointer to the next element). Field 1 is a positive
integer taking values in the range [1, 150], and Field 2 is a string.
The program should read in two files. The first file (data_x.txt, where x is an integer) contains the
data, integers and names (in that order), and it is in ASCII format. The second file, whose filename
should be passed as a command line argument, contains a list of operations that you have to
perform on the data from the first file. Details of the two files are given below.
Data file (data_x.txt)
This file contains the data that you have to manipulate. It is an ASCII file, the data values are
characters and integers and are stored one per line. Instances of this file are data_1.txt, data_2.txt,
This file contains the operations that your program should perform on the data from the data file.
The commands are shown in Table 1. Please note that the commands are case-sensitive.
This command reads the data file data_x.txt. The command `r' is followed by a
number x indicating the exact file that has to be read. After the reading operation,
no ordering is imposed to the resulting structure. Note that this also defines the
number of the output file as wel (see below)
This command applies the Bubble Sort algorithm to sort the elements of the
structure in ascending order. The ordering is based on the arithmetic values (Field
This command writes all the data in the structure to a file output_x.txt, where x is
determined in the command file through the read command that has been
preceded. The data should be stored as one data per line. If the file already exists,
this command should append the new data to the end of the file.
This command inserts a new element in the structure without destroying the
ordering. If no ordering exists, then this command just inserts the new element in
This command deletes an element from the structure without destroying the
ordering. In the case where the structure has multiple elements of the same value,
this command deletes only one (the first instance). In the case where this value is
not in the structure, the command should not perform any operations. Note that
the delete operation is based on Field 1 of the element.
This command reverses the imposed order of the linked list
This command calculates the average value of Field 1 data and stores it to the
output file. Your program should write the following line in the output file "Average
value: x", where x is the calculated average.
This command finds the minimum value of Field 1 data in the list and stores it to
the output file. Your program should write the fol owing line in the output file
"Minimum value: x", where x is the minimum value of Field 1 data in the list.
Table 1. The list of possible commands
An instance of the command file is given below:
The commands should be interpreted as fol ows:
1. Read file data_1.txt in the internal structure
2. Sort the elements in ascending order
3. Insert entry <45, John>
4. Insert entry <50, Bil >
5. Delete entry with Field 1 <50>
6. Write the current data of the structure to file output_1.txt
7. Calculate the minimum value of Field 1 data and write the result to file output_1.txt
The data_x.txt and output_x.txt files should have one entry per line. An example of an output file it
is shown below, which is the output file that corresponds to the above example. It is assumed that
the input file had one entry only (<10, Alex>):
Minimum value: 10
* You can assume that the input and output files are in the same directory as you executable.
* You can assume that the reading command wil be performed only once in each execution of
your program, and it wil be always the first command.
* You can assume the files are properly formatted e.g. an integer fol ows the r command, as in
the command file example given above.
1. You can develop your program in a C++ environment of your choice. However, for the
submitted program you should ensure that your program is executed as fol ows:
, where assignment1.exe is the name of your executable file and commandFile.txt is the
name of the command file.
2. A set of input and anticipated output files are given for you to test your code. Please note
that these tests are not exhaustive and during marking a larger and more comprehensive
test set wil be used.
3. The markers wil use the minGW environment to test your code. Please ensure that your
program is compatible with this environment.
4. Note that some compilers are stricter than other leading to developing of code that works
fine under one system but fails in another. Make sure that your code is not prone to such
Your program wil be marked using the fol owing criteria:
1. Correct and efficient operation for
1. reading data from the file (10%)
2. sorting the data (10%)
3. inserting new data (10%)
4. deleting an entry (10%)
5. reversing the order (10%)
6. calculate the average value (10%)
7. find the minimum value (10%)
8. writing the data to the file (10%)
2. Clear and understandable code, use of functions (e.g. comments, proper name selection)
3. Assignment 1 has a 50% weight, where Assignment 2 has a 50% weight of the overal mark
for the coursework.
You should submit via Blackboard the source code, including your real, email and login name in a
comment at the start of the file.
Submission deadline: 23rd February at 23:00
If you delay the submission, the usual penalty will be applied (4% of marks per day)