Reference no: EM131459005

Assignment 1: Data Structures

Introduction

The government wants to crack down on welfare cheats. They ask you to develop a program that can cross-reference welfare and tax records. Unfortunately, this data is in separate databases, with the welfare data sorted by name, and the tax data sorted by tax file number.

Centrelink staff need to be able to quickly check to see the tax and welfare records of individuals.

Assignment Specification - Part A

For this part of the assignment you will implement a prototype that uses a BST to store welfare and tax data. The BST will consist of individual records where each record contains a tax file number (used as a key for the BST); the name of the individual (we will just prototype with a single name with no spaces); a list of years that the person received welfare payments; and a list of years that the person lodged a tax return.

The program will start by reading the data from the separate files into the BST (populating each list in turn). The program will then prompt for a tax file number and print a message displaying the years in which that person both received welfare payments and lodged a tax return. The program will terminate if the user enters a 0 as the tax file number.

Data Structure Requirements

You must use the BST and linked list code developed in the tutorials, however the data structures will be modified for the new types (and functions will also require minor modifications to accommodate these changes).

The following definitions MUST be used:

typedef struct listNode{ int data;

struct listNode*next;} *ListNodePtr;

typedef struct list{ListNodePtr head;
} List;

typedef struct taxRecord{ long tfn;

char *name;List welfare; List tax;
} *TaxRecordPtr;

typedef struct bstNode{TaxRecordPtr data;struct bstNode*left; struct bstNode*right;
} *BSTNodePtr;

typedef struct bst{BSTNodePtr root;

} BST;

The BST, BSTNodePtr, and TaxRecordPtr definitions, must be placed in a file called bst.h, along with the BST function prototypes. The modified BST functions must be placed in bst.c.

The List and ListNodePtr definitions must be placed in list.h, along with the list function prototypes. The modified list functions must be placed in list.c. No other code should be placed in these files.

All remaining code, should be placed in a file called main.c that contains the main function and program logic. Other functions may be added if required.

Program I/O

The welfare data consists of a text file, with the first line containing the number of entries. Each entry is then split over three lines. The first line contains a name, the second line contains a tax file number (no spaces), and the third line contains a single number indicating the number of years followed by an ordered list of that many 4 digit years separated by spaces. For example:

4 Robert

123456789

3 1991 1992 1993 Julian 987654321 1 1990

James 123581321

4 2012 2013 2014 2015 Joel

666666666

0

The tax data consists of a text file with the first line containing the number of entries. Each entry is split over two lines. The first line contains the tax file number (no spaces), the second line contains a single number indicating the number of years followed by an ordered list of that many 4 digit years separated by spaces. For example:

4

123456789

6 1993 1997 2011 2012 2013 2017

111000111

4 1995 1998 2000 2007

987654321

6 2011 2012 2013 2014 2015 2016

123581321

5 2013 2014 2015 2016 2017

We will use fscanf to read the input files. For example, to read the first three lines of the welfare file above, you could write:

FILE *filePtr;
filePtr = fopen("welfare.txt", "r"); // open for 'r'eading

fscanf(filePtr, "%d", &num_records); // num_records is an int or long
fscanf(filePtr, "%s", buffer); // buffer is a char array
fscanf(filePtr, "%d", &tfn); // tfn is a long
// ...
fclose(filePtr);

Note that there may be individuals with entries in one file and not the other. Your program only needs to keep track of individuals with an entry in the welfare file.

All interactions with the program will be via the console. The program will continuously ask for a tax file number. If the tax file number is not zero, it will either print the name of the person with that tax file number followed by the year that individual both received welfare and lodged a tax return; or it will print a message saying that individual has never received welfare payments. If the tax file number is zero, the program will exit. For example, given the data above, a session might look like this:

123456789 Robert 1993

111000111

No entry with that tax file number

987654321 Julian

123581321

James 2013 2014 2015

0

I/O Restrictions

You may assume that all input will always be in the correct format and contain no logical errors.

- Data files will always be in the correct format

- The user will only ever enter integers in the range 0 - 999999999

Algorithms

Aside from the basic algorithms for storing items in linked lists and binary search trees, the only other algorithm that needs to be developed is the one to determine which years appear in both linked lists. If the length of the first list is n, and the length of the second list is m, there is a simple method that is 0 (m ×n), but there is a much more efficient method that is O (m +n). You will get most of the marks for the linked list if you use the simple method, butto get a high distinction for the linked list task, you need to use the more sophisticated method.

Memory Management

Names should be stored in appropriately size dynamically allocated memory. Names will always be less than 100 characters long. For example, the name "robert" would be stored in a char string of length 7.

On termination, all dynamically allocated memory should be freed, including char strings, lists and the BST.

Assignment Specification - Part B

This part of the assignment should only be attempted once you have a fully implemented andthoroughly tested solution to part A. It would be better to submit a complete part A and nopart B than to submit a partially complete part A and part B.

The requirements for this part of the assignment are exactly the same as for part A except that an AVL tree must be used rather than the BST. The AVL files should be named avl.h and avl.c, but avl.h should #include the node and tax record definitions from bst.h (i.e. avl.h will only add the AVL function prototypes, the struct definitions are the same).

Minimal assistance will be provided for this part of the assignment. No assistance at all will be given unless you can demonstrate a fully implemented and thoroughly tested solution to part A.

Part B should be a separate submission - i.e. submit Part A and Part B as two separate Visual Studio projects.

Testing

It can be very time consuming to thoroughly test a program like this where large datasets are required.

At least one small pair of test files will be provided with sample output for a hypothetical session. It is recommended that you construct larger files to fully test your program (I use Python scripts to construct test files, but you could also use Excel or similar).

This is an important part of program development! It has been a common complaint from students that their code worked for "all of their tests", but not for the markers. Make sure that you allow enough time for testing so that this doesn't happen to you.

Synopsis of the task and its context

This is an individual assignment making up 10% of the overall unit assessment. The assessment criteria for this task are:

1. Implement basic program functionality for a console driven application

2. Implement and test a linked list to store years

3. Implement and test a BST to store data

4. Implement and test an AVL tree to store data

A significant part of the assessment procedure will involve automated tests. Therefore, it is very important that your own testing is very thorough.

Attachment:- tax.txt