代做KIT205留学生、代写c/c++、Data Structures代写、代做c/c++程序设计

日期：2019-03-27 10:19

KIT205 Data Structures and Algorithms

Assignment 1: Data Structures

Due: 26th April, 11:55pm

Introduction

You work for an online marketing company that manages a number of store loyalty programs.

You have been asked to develop some software to manage the customer database. You

decide to develop a prototype solution to test the performance of different data structures

and algorithms.

The company manages the program for several stores, but this number is not expected to

grow beyond a few dozen. More importantly, each program may have many thousands

(perhaps even millions) of customers; and, as a result of aggressive cross-marketing, many of

these customers are subscribed to multiple loyalty programs. Your software needs to provide

the following functions:

1. Subscribe: This function will prompt the user for a customer id and loyalty program

name. If this data does not already exist in the database, it will be added. A

subscription will then be added for this customer and program.

2. Unsubscribe: This function will prompt the user for a customer id and loyalty program

name. The function will then remove this subscription but will not remove customers

or loyalty programs from the database, even if they have no subscriptions.

3. Print Summary: This function will print a line for each loyalty program, with each line

containing the name of the program followed by the number of subscribed customers.

4. Print Subscribers: This function will prompt the user for the name of a loyalty

program, then print an ordered list of customer ids for all subscribers to this program,

each one on a separate line.

5. Print Subscriptions: This function will prompt the user for a customer id, then print all

of the loyalty that this customer is subscribed to.

It is very important that access to data is very fast since many operations may occur each

second. This will be especially important when dealing with customers since the number of

customers may be very large and insert, delete, and find operations will be very common.

Initially, you decide to test performance using a combination of binary search trees, linked lists

and arrays, but you would like to test an AVL tree as well. For preliminary testing, you decide

that only the customer ids and loyalty program names will be stored.

Assignment Specification – Part A

For this part of the assignment you will select appropriate linked list, BST, and array data

structure to implement the four operations. Part of the assignment task is to use these data

structures in an efficient way. Your implementations of list and BST data structures MUST be

based on the definitions used in lectures and tutorials as given below.

typedef struct listNode{

int data;

struct listNode *next;

} *ListNodePtr;

typedef struct list {

ListNodePtr head;

} List;

typedef struct bstNode {

int data;

struct bstNode *left;

struct bstNode *right;

} *BSTNodePtr;

typedef struct bst {

BSTNodePtr root;

} BST;

These data structures will need to be modified to support the customer and loyalty program

information, which will be stored as long ints and strings. You will also need to add crossreferences

between the data structures to represent subscriptions. These may be one-way

references – i.e. a customer might have references to the programs they are subscribed to,

but the programs might not have references to the subscribed customers, or vice versa.

The ListNodePtr and List definitions and (modified) linked list functions must be placed in

files list.h and list.c. The BSTNodePtr and BST definitions and (modified) BST functions

must be placed in files bst.h and bst.c.

All remaining code should be placed in a file called main.c that contains the main function

and program logic. This file will contain separate functions for each of the four operations

listed in the introduction, as well as a fifth function to handle termination. Other functions

may be added if required.

Program I/O

All interactions with the program will be via the console. Operations 1-4 will be selected by

typing 1-4 at the command prompt. Quitting the application will be selected by typing 0. For

example, the following input sequence would subscribe the customer ‘123’ to the loyalty

program ‘abc’, and then quit:e input only, not the program response (if any). You are free

to add prompts to make the application more user friendly, but this will not be assessed

(although it may be useful).

Program output in response to operations 3 and 4, should be as minimal as possible. You may

print a header if you wish, but this should be followed by one record per line with spaces

separating data. For example, in response to operation 3, the output might be:

Current subscriptions:

abc 32

def 0

ggg 10236

I/O Restrictions

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

errors.

Commands will always be in the range 0-4

Loyalty program names will always be strings less than 100 characters long and may

contain any alpha-numeric characters excluding spaces

Customer ids will always be positive integers in the range 0-999999999

The user will never attempt to print data for a non-existent loyalty program

The user will never attempt to print data for a non-existent customer

Memory Management

Loyalty program names should be stored in appropriately size dynamically allocated memory.

Names will always be less than 100 characters long. For example, the program name “abcdef”

would be stored in a char string of length 7.

Unsubscribing from a program may require you to free memory for that subscription (but not

for the customer or program itself). The quit function should free all dynamically allocated

memory.

Solution Requirements

You must develop a reasonably time efficient solution, but you also want to keep the code

clean and simple to make your code easier to modify and maintain (a computer scientist called

Donald Knuth, famously said that “premature optimisation is the root of all evil”).

Remember that, while the number of customers may be large, the number of loyalty programs

is expected to be relatively small.

So, to score full marks your solution must:

utilise at least one linked list and at least one bst

strings must be stored in appropriately sized dynamically allocated memory

the memory for all data structures should be freed when the data is no longer

required

If the number of customers is C and the number of loyalty programs is L then:

o Op 1 should be O(L + log C)

o Op 2 should be O(L + log C)

o Op 3 should be O(L * C)

o Op 4 should be O(L + C)

o Op 5 should be O(L * log C)

Note: A clever implementation might be able to achieve a better Big O for some of these

operations, but that is not required to achieve full marks on this assignment. You will not

receive extra marks for an implementation that achieves better performance.

Also note that the following work would get close to a pass mark:

BST and linked list code implemented correctly as per tutorial work

Evidence that you have made a sensible choice about how to use the data structures

(this could be determined from code comments or variable names, that make it clear

what choices you have made)

BST and linked list code adapted to store customers and loyalty programs (node

definitions only – functions don’t need to be correctly adapted)

A working main loop (calls functions when options are selected, functions collect

required input, but may not do anything with that input, exits without errors)

A solid attempt to get BST and linked list functions working in this context (with the

main loop and adapted data structures)

It is best to submit a program that compiles and runs without errors, even if the program

doesn’t do anything. If you have added new code that breaks you program, comment this

code out before submitting (and add an explanation) so that the marker can easily see what

you have completed. After running your program, the marker will then check the code to

determine what else you have attempted. Code that doesn’t compile or crashes is extremely

difficult to mark, and the marker may be forced to give you less marks if they are unable to

confirm what is working (they have very limited time to fix bugs).

Assignment Specification – Part B

This part of the assignment should only be attempted once you have a fully implemented and

thoroughly tested solution to part A. It would be better to submit a complete part A and no

part B than to submit a partially complete part A and part B. (If you look at the marking sheet

below, you will see that this part is worth at most 15%)

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 a BST. The AVL code should be placed in bst.h and

bst.c, with AVL functions added to these two files (you may also need to modify the node

definition, but this should have no effect on the BST functions).

Minimal assistance will be provided for this part of the assignment, especially if you cannot

demonstrate a fully implemented and thoroughly tested solution to part A.

Testing

It can be very time consuming to thoroughly test a program like this when all input is done

manually (imagine testing that your solution can manage 10000 customers). A common

method of testing code like this is to use input redirection (and possibly output redirection).

When using input redirection your code runs without modification, but all input comes from a

file instead of from the keyboard.

This facility is provided in Visual Studio through the project properties dialog. For example, to

redirect input from a file called “test.txt”, you would add:

<"$(ProjectDir)test.txt"

to Configuration Properties|Debugging|Command Arguments. This will be demonstrated in

tutorials.

At least one small input test file with sample output will be provided. It is recommended that

you construct larger files to fully test your program.

Assignment Submission

Assignments will be submitted via MyLO (an Assignment 1 dropbox will be created). You

should use the following procedure to prepare your submission:

Make sure that your project has been thoroughly tested using the School’s lab

computers

Choose “Clean Solution” from the “Build” menu in Visual Studio. This step is very

important as it ensures that the version that the marker runs will be the same as the

version that you believe the marker is running.

Quit Visual Studio and zip your entire project folder along with a completed

assignment cover sheet

Upload a copy of the zip file to the MyLO dropbox

History tells us that mistakes frequently happen when following this process, so you should

then:

Unzip the folder to a new location

Open the project and confirm that it still compiles and runs as expected

o If not, repeat the process from the start

KIT205 Data Structures and Algorithms: Assignment 1 - Data Structures

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. Select appropriate data structures to store problem-specific data

2. Adapt generic data structures for use in a specific problem

3. Implement generic list data structures and algorithms

4. Implement generic tree data structures and algorithms

A significant and extremely important part of software development is thorough testing. Small programming errors may attract a large penalty if the error is something

that should have been picked up in testing! Please try to complete your program early to leave enough time for testing.

Match between learning outcomes and criteria for the task:

Unit learning outcomes

On successful completion of this unit you will be able to … Task criteria:

1. Transform a real-world problem into a simple abstract form that is suitable for efficient computation

2. Implement common data structures and algorithms using a common programming language

3. Analyse the theoretical and practical run time and space complexity of computer code in order to select algorithms for

specific tasks

4. Use common algorithm design strategies to develop new algorithms when there are no pre-existing solutions

5. Create diagrams to reason and communicate about data structures and algorithms

1, 2

3, 4

-

-

-

Criteria HD (High Distinction) DN (Distinction) CR (Credit) PP (Pass) NN (Fail)

You have: You have: You have: You have: You have:

1. Select appropriate data

structures to store

problem-specific data

Weighting 10%

Data structures have been mapped

to problem data in a way that

promotes efficient time and memory

utilisation

Data structures have been mapped to problem data Working linked list and

BST code from tutorials,

but little attempt to match

data structures to problem

data

2. Adapt generic data

structures for use in a

specific problem

Weighting 15%

Correct adaption of linked list data

structure for storing customers,

programs or subscriptions

- and -

Correct adaption of tree data

structure for storing customers,

programs or subscriptions

Correct adaption of linked list data structure for

storing customers, programs or subscriptions

- or -

Correct adaption of tree data structure for

storing customers, programs or subscriptions

Partially correct adaption of linked list

data structure for storing customers,

programs or subscriptions

- or -

Partially correct adaption of tree data

structure for storing customers,

programs or subscriptions

Correct code for input

loop, but little attempt to

adapt data structures for

this problem

3. Implement generic list

data structures and

algorithms

Weighting 25%

Linked list functions implemented

correctly, including freeing all

memory correctly (including on quit)

Linked list functions

implemented correctly,

without freeing all

memory

Implemented some linked list functions correctly for this

problem

Little attempt to get linked

list operations working

4. Implement generic tree

data structures and

algorithms

Weighting 50%

AVL functions implemented

correctly, including freeing all

memory correctly (including on quit)

Implemented some

AVL functions correctly

for this problem.

BST functions

implemented correctly,

including freeing all

memory correctly

(including on quit)

Implemented some BST functions

correctly for this problem.

Little attempt to get BST

operations working