代写COMP2017 9017 Assignment 2 2024代做留学生R程序

- 首页 >> Java编程

COMP2017 9017

Assignment 2

Due: 23:59 28 March 2024

This assignment is worth 10% of your final assessment

Task Description

Your task is to create a multi-type linked list data structure and a program that interacts with it. Your assignment is broken into three tasks that must be completed in order.

•  The first part is the basic command syntax of the linked lists, creation, removal, viewing etc.

•  The second part is modifying the lists in place, through insertion and deletion of elements.

•  The third part is allowing lists to refer to each other in a nested pattern.

It is also recommended to read through the specification carefully. You should ensure that you create test cases that cover a range of possible inputs before beginning to code.  Make sure you identify and test for edge cases.

Implementation Details

All commands are read through standard in, and all output is given through standard out.

Part 1: Basic Commands

For Part 1, your linked lists must support elements of the following types:

•  int

•  float

•  char

  string

Your program should take in commands from stdin that will create and manage these multi-type linked lists. The basic commands are: 

•  NEW  <number  of  elements> - create a new list

  VIEW  <list  index> - view a specific list by its index

•  TYPE  <list  index> - view a specific list by its index, printing out the types of each ele- ment.

•  VIEW  ALL - print the number of lists and each list in order of creation

•  REMOVE  <list  index> - remove a list

The index for each list should be 1 higher than the last created list’s index, starting from 0 for the first list, regardless of how many lists have been removed.

Basic Examples

In the following examples, ">  " denotes the following line as input. Your program must not print it to stdout or read it from stdin. It is included in the formatting only as an indicator, to differentiate the input from the output of the program.

Global input restrictions

<number  of  elements> and <list  index> must be an integer, have no sign character, and no whitespace.

Command keywords are delimited by exactly one (1) space character and should have no leading and trailing whitespaces. Be sure to replicate the formatting of these examples exactly, character by character.

The NEW Command

This command takes in a number as input for the initial size of the list. It then reads in an initial value for each element to initialise the list.  0 is a valid size, negative numbers are not.  Lists are labelled starting at 0 when they begin to exist, and the label always increments, even if a list is removed. Imagine in the following section that 4 lists have already been created.


>  NEW   5

>  hello

>  1

>  2

>  3.14

>  a

List  4:  hello  ->  1  ->  2  ->  3.14  ->  a


Lists will only be considered as "created" after all lines of the input have been parsed and no error occurs.


The VIEW Command

This command prints out the contents of the list at the given index.


>  VIEW  4

hello  ->  1  ->  2  ->  3.14  ->  a


The TYPE Command

This command prints out the types of each element at the given list.


>  TYPE  4

string  ->  int  ->  int  ->  float  ->  char


The VIEW ALL Command

This command prints out the current set of lists in index-increasing order.


> VIEW ALL

Number of lists: 3

List 0

List 3

List 4



The REMOVE Command

This command deletes a list, and prints out the current set of lists again in index-increasing order.


>  REMOVE  3

List  3  has  been  removed .

Number  of  lists:  2

List  0

List  4


Invalid Commands

A command can be identified from a line if the line strictly begins with exactly the command keyword, and is invalid if its invalid otherwise.

If a command is invalid in some way, print INVALID  COMMAND:  <command  used>. For exam- ple, when there is no List  4:




>  REMOVE   4

INVALID  COMMAND:  REMOVE


If a command cannot be identified, use INPUT. For example:


>  abracadabra

INVALID  COMMAND:  INPUT


It is up to you to find and prepare for edge cases.

Type Rules and Exceptions

There can be some ambiguity in certain cases for what a given input’s type is.  The order for type checking is as follows:

  integer

•  float

•  char

  string

Requirements for types are as follows:

•  int can be negative, positive or zero (tests will also not exceed the maximum and minimum value for an int type).

•  float is the same except it will always have a decimal point.

•  float should also be printed to 2 decimal places, though they can be read in to any precision.

•  char is any printable  character in ascii as long as it is singular.

•  string covers all other cases.

  Empty lines in list creation should be considered as string.

•  string can start with leading and trailing whitespace characters.

•  Lines containing one int or float can have leading and trailing whitespaces. These will be interpreted as numbers. (Note that this is the default behaviour of scanf).

•  All inputs will have a maximum total line length of 128 bytes.



>  NEW   4

>  1.0

>

>    baguette

>  5

List  4:  1.00  ->    ->    baguette  ->  5


Note the empty line that was interpreted as an empty string, as well as the extra space in "  baguette". There will be no test cases that do not fit this description.

Note: Curly brackets {} are used in Part 3, and are considered invalid input if they appear in any form. other than specified there.


>  NEW   3

>  1.0

>  {}

>  baguette

INVALID  COMMAND:  NEW

>  NEW   3

>  1.0

>  {

>  wordswords  }  words

INVALID  COMMAND:  NEW


Exiting the program

Upon EOF, the program should free all used dynamic memory, then exit.

Part 2: Dynamic Lists

In this part you are to implement two extra commands:  INSERT and DELETE.

The INSERT Command

This command takes input of the form INSERT  <list  id>  <index>  <value>, and inserts the value at the given indexof the given list. It should then print out the new list in the same format as VIEW, but with the string "List  <n>:   " before it. For example:


>  VIEW  1

a  ->  b  ->  c  ->  d

>  INSERT  1  0  Baguettes

List  1:  Baguettes  ->  a  ->  b  ->  c  ->  d



Negative indices should insert from the end of the list. Indices outside the range are invalid:


>  VIEW  1

a  ->  b  ->  c  ->  d

>  INSERT  1  -1  Baguettes

List  1:  a  ->  b  ->  c  ->  d  ->  Baguettes

>  INSERT  1  97  Croissants

INVALID  COMMAND:  INSERT


The DELETE COMMAND

This command takes input of the form DELETE  <list  id>  <index> and removes the given index from the list.  It should then print out the new list in the same format as INSERT. The same conditions on indices apply. For example:


>  VIEW  1

a  ->  b  ->  c  ->  d

> INSERT 1 -1 Baguettes

List  1:  b  ->  c  ->  d

>  DELETE  1  -1

List  1:  b  ->  c

>  DELETE  1  4

INVALID  COMMAND:  DELETE


Part 3: Nested Lists

For this section, you are to modify your previous code to accept a new type: other lists.  This is to a maximum depth of one. This means every list is either a simple list (contains only regular types), or a nested list (contains regular types and simple lists). Nested lists cannot contain other nested lists.

Nested lists contain only references to simple list(s). Thus, changes to the simple list should also be reflected in the nested list.

To insert a simple list into a nested list, it should be specified with curly brackets. When nested lists are printed, they should be labelled as Nested, like so:


>  VIEW  1

a  ->  b  ->  c  ->  d

>  NEW   3

>  first

>  {1}

>  last

Nested 2: first -> {List 1} -> last

>  VIEW  ALL

Number  of  lists:  2




List  1

Nested  2


Any command that refers to a non-existent list, or would result in any list having depth greater than 1 should give an INVALID  COMMAND:



>  VIEW  0

a  ->  b  ->  c  ->  d

>  NEW   2

>  first

>  last

List  1:  first  ->  last


>  INSERT  1  1  { 0}


Nested  1:  first  ->  {List  0}  ->  last

>  NEW   1

>  {1}

INVALID  COMMAND:  NEW



If all references are deleted from a nested list with DELETE, then it becomes a simple list. The TYPE command should print reference as the type of any references to other lists.


>  VIEW  0

a  ->  b  ->  c  ->  d


>  VIEW  1


first  ->  {List  0}  ->  last

>  TYPE  1

string  ->  reference  ->  string


Removal of a simple list while it is referenced by any other list should give an

INVALID  COMMAND:  REMOVE.

The VIEW-NESTED Command

This command can print any list, but when it prints a nested list, it will also print its sub-lists, contained in curly brackets. Like so:


>  VIEW  1

a  ->  b  ->  c  ->  d


>  VIEW  2


first  ->  {List  1}  ->  last

>  VIEW-NESTED  1

a  ->  b  ->  c  ->  d

>  VIEW-NESTED  2

first  ->  {a  ->  b  ->  c  ->  d}  ->  last 


Restrictions

To successfully complete this assignment you must:

•  Use dynamic memory.

•  Use linked list structures, they must be your own implementation.

•  Store values of the linked list as their actual types such as int or string.

•  Free all dynamic memory that is used.

 NOT use any external libraries, other than those in glibc.

•  Other restricted functions may come at a later date.

Any submission breaking these restrictions will receive a deduction of up to 5 marks per breach.

All texts within your submission that may be read by a reviewer (marker), including code comments, git commit messages, README files, and so on, should be written in English. Any readable text that is not written in English will receive a deduction of 1 mark per line.

Working on Your Assignment

You are encouraged to submit your assignment on Ed while you are in the process of completing it. By submitting you will obtain some feedback of your progress on the sample test cases provided.

If you have any questions about C functions, then refer to the corresponding man pages. You can and should ask questions about this assignment on Ed. As with any assignment, make sure that your work is your own, and that you do not share your code or solutions with other students.

Getting Started

The most important factor for success is your choice of data structures. We recommend:

1.  Read the specification and write test cases.

2.  Design your data structures.

3.  Part 1 Commands

4.  Part 2 Commands

5.  Part 3 Commands 

Writing even a few simple test cases of your own will ensure you understand the details of what you’ve been asked to do. Even on pen and paper, this is incredibly beneficial.

Data structure design will have the largest impact on the quality of your code (both in terms of style and correctness). The scaffold has a few suggestions on the function prototypes you should use, but does not cover every instance. Be considerate of how your linked-list will function.

Debugging and Avoiding Leaks

It is recommended that you use tools such as gdb, valgrind and ASAN

(the -fsanitize=address,leaks compilation flags).

These will assist in finding basic errors (gdb) and monitoring memory leaks (valgrind, ASAN). However, they cannot automatically prevent memory errors and leaks.  You should be conscious of where leaks may occur and verify them yourself.

Note: Mac users may need to use a full virtual machine (VM) to make use of these tools. We have had reports of both valgrind and ASAN being unusable on Macs. Please refer to Ed for more details.

Compilation and Testing

Your program should be compiled by the default rule, which is the first defined rule of the Makefile. You should name this make rule build. After compilation, your program should be a single binary file called mtll which is used to run your program.


#  compile  the  program

make

#  alternatively

#  make  build

#  run  the  program

./mtll


You should implement your program in multiple C source and header files.  This is required for full style. marks.10  They must all compile together into one single binary when the program is built.

You should also do your own testing.  If you need to compile/create your tests before running them, please implement a make rule called tests for this and then a separate one for running your tests. Please also store your tests in the tests directory provided.

After the assignment is released, a small number of test files will be made available. Correctness tests will be provided to ensure that your code can execute fundamental examples. These tests will not be the complete set of tests run against your code.

Any attempt to deceive the marking system (such as hard coding test cases) will receive a zero.


#  compile  the  tests  if  necessary

make  tests

#  run  the  tests

make  run_tests


Submission

Submissions for this assignment will be through git.

The general process of writing and submitting is the same:


git  add  <files>

git  commit  -m  "fix  memory  leak  in  function  x"

git  push


If you have any questions about git usage, feel free to check the Git Lesson, the relevant manual pages, or ask on Ed.

Do NOT push binaries, including executables and object files. Either add your source files manually, or create a .gitignore file that includes the names of all your binaries.

None of your git commits should contain a binary file. Any submission breaking this restriction will receive a deduction of 1 mark per commit.

 


站长地图