COMP2011 PA3: Simplified Company Management
System
The goal of PA3 is to implement a simplified company management system using linked lists and dynamic arrays.
The system maintains the structure of the company as well as tasks assgined to each staff using the following structure:
A Staff tree with each Staff node pointing to a dynamic Staff pointer to pointer array to maintain a list of his/her subordinates.
A Task linked list with each Task node pointing to the next Task node and Assignee_node linked list.
A Assignee_node linked list with each node pointing to the next node and the Staff assigned to the task.
Upon completion of this project assignment, you should be able to:
Allocate and de-allocate the memory spaces for dyamic data structures (e.g. dynamic array, linked list).
Write functions to manipulate the above structures (e.g. insertion, deletion, traversal).
Implement the logic design/algorithm with C++ code in practical and complex tasks.
Announcements
This section will be updated after the release. Important announcements will also be sent to students via Canvas.
1. T.B.A
Introduction
Your goal is to implement a simplified company management system:
1. The system begins by displaying a default company structure and a default set of tasks.
2. The system asks for an option in a loop. The following operations are supported:
Display all the Staffs
Display all the Tasks
Count the total number of staffs in this company
Search for a staff by staff id
Search for a task by task id
Search for every tasks assigned to the given staff id
Hire a new staff
Promote a staff by staff id
Create a task
Assign a task to staff by staff id
Layoff a staff by staff id
Exit the system
3. When the system exits, all dynamically allocated memory MUST BE properly deallocated.
The C++ struct definitions are shown below:
const int MAX_CHAR_NUM = 100; // at most 100 characters (including the NULL character)
const int MAX_TASK_NUM = 50; // at most 50 tasks assgined to staffs
// A dynamic array to store the Staff structure
struct Staff {
unsigned int sid; // id is an unique identifier of the Staff (e.g., 39)
char name[MAX_CHAR_NUM]; // name of the employee
char gender[MAX_CHAR_NUM]; // gender of the employee
unsigned int number_of_subordinate; // The total number of subordinates assigned to this staff
Staff** subordinate; // The pointer pointing to the Staff pointer dynamic array
};
struct Task_assignee_node {
Staff* staff_ptr; // The pointer pointing to the Staff
Task_assignee_node* next; // The pointer pointing to the next assignee_node
};
struct Task {
unsigned int tid; // id is an unique identifier of the task (e.g., 39)
char name[MAX_CHAR_NUM]; // name of the task
unsigned int num_of_people; // number of people assigned to this task
Task_assignee_node *assignees_list; // The pointer pointing to the first Assignee node
Task *next; // The pointer pointing to the next task
};
Skeleton Code
The skeleton code: pa3_skeleton.cpp is provided.
You DO NOT need to start from scratch.
You can search the keyword TODO in the skeleton code to quickly locate the parts you need to implement
READ the skeleton code carefully. Useful things such as input handling are already provided in the skeleton code
DO NOT include extra header files
DO NOT use global variables
DO NOT add any additional arguments to the given functions
DO NOT add extra cin or cout statements
It is because the input and output handling are given in the skeleton code
Extra input and output statements (even output an extra space) may fail the ZINC test cases
If you add extra input and output statements for debugging purposes, please remember to delete them before your final code
submission
If needed, you can add extra constants, local variables, and extra helper functions
Assumptions
In Staff:
The Staff ID of layoff employees will not be re-used again.
When hiring a new staff, the system should assign the staff ID of the most recently hired + 1 as the staff ID of the new hire.
The system cannot lay off the most recently hired staff.
When laying off a staff, the system should assign the subordinate of the layoff staff to the supervisor of the layoff staff.
You cannot layoff the CEO and you cannot promote a staff to be at the same level as the CEO.
In this PA3, the term "CEO" always refers to the root node of the Staff tree.
The composition of the subordinates of the promoted staff will remain the same.
The valid characters are A-Z, a-z, , 0-9
No spaces and tabs will be used when entering the name of Staff and Task name
The valid gender are male and female
For numeric input, you can assume the input values are valid (i.e., we won't enter alphabetical characters when entering a number)
Tasks
Think carefully before writing code
In this project assignment, you are free to define new constants, variables (excluding global variables), functions, etc.
DO NOT write any code if you do not understand the skeleton code.
READ the skeleton code and the problem description carefully.
REVIEW the related lecture and lab topics.
The suggested order of implementation is: Searching > Modifications > Deletions
For each task on this web page, we illustrate the general cases using some sample data. The examples are for illustration of typical cases only.
For each task, you need to think carefully about other cases.
Two functions, display_staffs and display_tasks, are already implemented for you to help you check your implementation for the
following tasks.
Four helper functions, create_staff, create_task, create_task_assignee_node, and dynamic_init_subordinate_array are given to
help you implement the following tasks.
Task 1: Count the total number of staffs within the company
/**
* function count_staffs counts the total number of staffs within the company
* @param staff_head points to the head of the Staff tree
*
* @return the total number of staffs
*/
int count_staffs(const Staff *staff_head) {
int count = 0;
//TODO:
return count;
}
Hint: You may use recursion to implement this function, and by default, the system starts with 8 staffs.
Task 2: Search for the Staff by the staff id
/**
* function search_staff search for the target staff given his/her staff id
* @param staff_head points to the head of the Staff tree
* @param target_sid is the id of the staff you need to search for
*
* @return the Staff pointer pointed to the target staff, and if the staff can't be found, return nullptr
*/
Staff* search_staff(Staff *staff_head, const unsigned int target_sid)
{
Staff *staff = nullptr;
//TODO:
return staff;
}
Hint: You may use recursion to implement this function
ɠ**;
Task 3: Search for the task by the task id
/**
* function search_task search for the target task given the task id
* @param task_head points to the head of the Task linked list
* @param target_tid is the id of the task you need to search for
*
* @return the Task pointer pointed to the target task, and if the task can't be found, return nullptr
*/
Task* search_task(Task *task_head, const unsigned int target_tid)
{
Task *task = nullptr;
//TODO:
return task;
}
Hint: You may use recursion to implement this function
Task 4: Search for every tasks that are assigned to the Staff with the given staff id
/**
* function search_tasks_to_staff searches for all the tasks that have been assigned
* to a particular staff, based on the staff id.
* The function return a Task pointer to pointer array which store the pointers pointed to all the tasks that are a
*
* @param task_head points to the head of the Task linked list
* @param sid is the staff id of the staff that you want to search for all the assigned tasks
* @param total_tasks_to_staff is a int which store the total number of tasks assigned to the staff
*
* @return ret, which contains the pointers to all the assigned tasks. If there are no tasks assigned
* to the staff, return nullptr.
*/
Task** search_tasks_to_staff(Task* task_head, const unsigned int sid, unsigned int& total_tasks_to_staff)
{
Task **ret = nullptr;
//TODO:
return ret;
}
Task 5: Hire a new staff
ɠ**;
ɠ**;
/**
* function hire_new_staff hires a new staff given his/her name, gender, and which supervisor to assign to
* @param staff_head points to the head of the Staff tree
* @param name of the hiring staff
* @param gender of the hiring staff
* @param supervisor_sid is the staff id of the staff who will be supervising the new hired staff
*
*/
void hire_new_staff(Staff* staff_head, const char name[MAX_CHAR_NUM], const char gender[MAX_CHAR_NUM], const unsig
{
// First check if supervisor exists or not, if not end the hiring process
Staff* supervisor = search_staff(staff_head, supervisor_sid);
if (supervisor == nullptr){
cout << "Supervisor not found, fail to hire" << endl;
return;
}
//TODO:
return;
}
Assumptions: When hiring a new staff, the system should assign the staff ID of the most recently hired + 1 as the staff ID of the new hire. The
system cannot lay off the most recently hired staff. It does not matter if the new hired staff has the same personal information as existing staffs.
Note that this task involves creating a new staff node.
Hint: Think carefully about how to calculate the staff id of the new hired.
Task 6: Promote a staff
/**
* function promote_staff promotes the staff to a position that is one level higher than their original position.
* Additionally, the promoted staff will be assigned as a subordinate to the supervisor of their original superviso
*
* Note that the CEO, who is pointed by the staff_head pointer, cannot be promoted.
* Furthermore, it is not possible to promote any staff member to the same level as the CEO.
*
* @param staff_head points to the head of the Staff tree
* @param sid is the staff id of the staff that you wish to promote
*
* @return true if the promotion is succesful. Otherwise, return false
*/
bool promote_staff(Staff* staff_head, const unsigned int sid)
{
return false; // TODO: delete this line to start your work
}
Assumption: The promoted staff is always added to the end of the subordinate list.
Hint: You can create a helper function to help find the supervisor of the given staff.
Task 7: Insert a new task
/**
* function insert_task inserts a new task to the end of the Task linked list
* @param task_head points to the head of the Task linked list
* @param task_name is the name of the newly added task
*
* @return the Task pointer pointed to the new inserted task
*/
Task* insert_task(Task* task_head, const char task_name[MAX_CHAR_NUM])
{
return nullptr; // TODO: delete this line to start your work
}
Hint: new task id will always be the most recently created task's id + 1 and the new task (just after insertion) will have no assignee.
Task 8: Assign a task to a staff
/**
* function assign_task_to_staff assigns a task given the task id to a staff by the staff id
*
* @param staff_head points to the head of the Staff tree
* @param task_head points to the head of the Task linked list
* @param tid is the id of the task you wish to assign to the staff
* @param sid is the id of the staff that you wish to assign the task to
*
* return true if assignment is succesful. Otherwise, return false
*/
bool assign_task_to_staff(Staff* staff_head, Task* task_head, const unsigned int tid, const unsigned int sid)
{
//TODO:
return false;
}
Hint: You need to check whether the target task and staff exist or not. You also need to consider whether the task is already assigned to the staff.
The new assignee should be added to the tail.
Task 9: Lay off a staff
/**
* function layoff_staff deletes the staff by staff id from the staff tree and it also cleans up
* the corresponding assignee_nodes that point to the staff.
* Furthermore, the funtion also re-assigns the subordinates of the laid-off staff to his/her supervisor.
* No memory leak should result from calling the layoff_staff function.
*
* @param staff_head points to the head of the Staff tree
* @param task_head points to the head of the Task linked list
* @param sid is the id of the staff that you wish to lay off
*
* @return true if the lay-off is succesful. Otherwise, return false
*/
bool layoff_staff(Staff* staff_head, Task* task_head, const unsigned int sid)
{
// TODO:
return false; // delete this line to start your work
}
Hint: You need to carefully consider all the corner cases.
Task 10: Exit the system
Cleans up the linked lists and dynamically allocated memory used in this system
No memory leak should be found after the clean up
You need to implement 2 functions for this task
/**
* function delete_every_tasks deletes the Task linked list
* Furthermore, this function should also release the memory occupied by assignees_list
*
* @param task_head points to the head of the Task linked list
*
*/
void delete_every_tasks(Task *&task_head)
{
return;
}
/**
* function delete_every_staffs deletes the Staff tree
*
* @param staff_head points to the root node of the Staff tree
*
*/
void delete_every_staffs(Staff *&staff_head, Task *&task_head)
{
return;
}
Hint: You can create a helper function to deal with deleting the assignees_list of each task.
About memory leak and other potential errors
Memory leak checking is done via the -fsanitize=address,leak,undefined option of a recent g++ compiler on Linux (it won't work on
Windows for the versions we have tested). Other errors/bugs such as out-of-bounds, use-after-free bugs, and some memory-related bugs may
also be detected. If you wish to check for memory leaks yourself, you may follow our Memory Leak Checking guide.
Checking uninitialized variables
Many students forget to initialize the variables before using them. Sometimes, it will cause serious problems.
The following method can ask the compiler to check uninitialized variables. For example, the following code is stored in a file named
uninitialized_variables.cpp, you can add a flag -Wuninitialized to check:
g++ uninitialized_variables.cpp -Wuninitialized
The above technique may be useful for your labs and projects. Here is a demo in vscode:
Compilation and Running Test Cases
Important: Make sure you use -std=c++11 to compile the program. It is recommended to use a terminal and a command to compile. For
example:
g++ -std=c++11 -o pa3 pa3.cpp
Assume the test cases are stored in a folder named "testcase", you can run your program like this:
To run the first test case:
./pa3 < testcase/input01.txt > myOutput01.txt (in Mac/Linux) or
Get-Content testcase/input01.txt | ./pa3 > myOutput01.txt (in Windows)
To run the remaining test cases, change the digits 01 to another valid digits
Grading
Before the deadline
For each test case, you should compare your program output with the sample output. The file comparison technique was introduced in lab1 and
has been repeated in many labs. If you forget the details, please refer to lab1.
During debugging, you can type the input manually instead of redirecting the input file. It may help you identify the bugs in your program.
The following test cases are released:
Sample Input Sample Output Description
input01.txt output01.txt A test case for Task 1
input02.txt output02.txt A test case for Task 2
input03.txt output03.txt A test case for Task 3
input04.txt output04.txt A test case for Task 4
input05.txt output05.txt A test case for Task 5
input06.txt output06.txt A test case for Task 6
input07.txt output07.txt A test case for Task 7
input08.txt output08.txt A test case for Task 8
input09.txt output09.txt A test case for Task 9
input10.txt output10.txt A test case for a mix of different tasks
After the deadline
In addition to the given test cases, we have hidden test cases. They are summarized in the following table:
(*): In this project assignment, we may not be able to completely isolate one feature from another feature. So, we only list out the main areas in the
following table.
(**): When the Canvas grades are released, you may see different scores on ZINC and on Canvas.
ZINC does not handle the weighted score calculations well.
For each test case on ZINC, you should only see a score of 0 or 1.
0 means the test case is failed.
1 means the test case is passed.
The total score on ZINC is wrong because ZINC only sums up these 0s/1s and does not consider the weights of each test case.
The weighted score calculations will be done after the ZINC auto-grading, using the following formula:
sum ( score_of_test_case_i * weight_i ) / number_of_test_cases * 100
Main Area (*) Given test cases Hidden test cases Total Weight in Each Area % (**)
Task 1 1 1 2.5
Task 2 1 1 2.5
Task 3 1 1 5
Task 4 1 2 5
Task 5 1 2 10
Task 6 1 2 10
Task 7 1 1 5
Task 8 1 2 10
Task 9 1 2 10
Task 10 a.k.a Memory leak checking N/A 2 10
Mix of Different Operations (will also check Memory leak) 1 4 30
Total 10 20 100
Important Notes
About Academic Integrity
We highly value academic integrity. Please read the Honor Code section on our course webpage to make sure you understand what is
considered as plagiarism and what the penalties are. The following are some of the highlights:
DO NOT try your "LUCK" - we use sophisticated plagiarism detection software to find cheaters. We also review codes for potential cases
manually.
The penalty (for BOTH the copier and the copiee) is not just getting a zero in your assignment. Please read the Honor Code thoroughly.
Serious offenders will fail the course immediately, and there may be additional disciplinary actions from the department and university, up
to and including expulsion.
This programming assignment is challenging, so you are highly recommended to start early. If you need clarification on the requirements,
please feel free to post on Piazza. However, to avoid cluttering the forum with repeated/trivial questions, please carefully read the given code,
the description, the sample output, and the latest FAQ (refresh this page regularly) in this page before you post your questions. In addition,
please be reminded that we won't help debug for any student's assignment for the sake of fairness.
Submission
Deadline: 10-May-2024 (23:59)
You are required to submit your solution to our auto-grading system: ZINC.
Please read the ZINC student submission guidelines if you still don't know how to submit to ZINC.
Before submitting your code, make sure to rename the submission file to pa3.cpp, and submit it to ZINC. 50% penalty will be given if your
filename is wrong. You don't need to zip the file if you only submit one file to ZINC.
Filename checking is enabled on ZINC. If your filename is wrong, you should see something like this:
Other names do not work (e.g., PA3.cpp, Pa3.cpp, pa3.cpp.cpp, pa 3.cpp (a space is added between pa and 3) etc. )
Notes:
You may submit your file multiple times, but only the last submission will be graded. You do NOT get to choose which version we grade.
If you submit after the deadline, late penalty will be applied according to the submission time of your last submission.
Submit early to avoid any last-minute problem. Only ZINC submissions will be accepted.
The ZINC server will be very busy on the last day especially in the last few hours. However, as long as your submission is successful, we
would grade your latest submission with all test cases after the deadline.
Make sure you submit the correct file yourself. You can download your own file back from ZINC to verify. Again, we only grade the last
submission you upload to ZINC.
Compilation Requirements
It is required that your submissions can be compiled and run successfully in our online auto-grader ZINC. If we cannot even compile your work,
it won't be graded. Therefore, for parts that you cannot finish, just put in a dummy/empty implementation so that your whole program can be
compiled for ZINC to grade the other parts that you have done.
Late Submission Policy
There will be a penalty of -1 point (out of a maximum 100 points) for every minute you are late. The lowest score is 0 though.
FAQs
This section will be updated if necessary.
My code doesn't work / there is an error, here is the code, can you help me fix it?
As the assignment is a major course assessment, to be fair, we would not work out a task with you. We might provide you some hints, but
we won't debug for you.
Can I use functions defined in <cstring>?
Yes. You can. For example, strcpy and strcmp.
、
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
