Project 6 - Linked Lists

Overview

In this project, you will design a simple data management system for a map. The map will store a list of categories (ex: "Food and Drink", "Office", "Hospitals", etc.), and each category will contain a list of businesses.

Structs

You will create the following three structs:

• Map, which has a name and a pointer to the list of categories
• Category, which has a name, a pointer to a list of businesses, and a pointer to the next category in the list
• Business, which has a name, an integer which stores the number of employees, and a pointer to the next business in the list

These will be defined as:

typedef struct _map Map;
typedef struct _category Category;
typedef struct _business Business;

struct _map {
    char* name;
    Category* category_head;
};

struct _category {
    char* name;
    Business* business_head;
    Category* next;
};

struct _business {
    char* name;
    int num_employees;
    Business* next;
};

Methods

newMap

Given a name, it will return a pointer to a new Map struct. Initialize the category_head to NULL. Be sure to copy the passed name string into the new map instead of simply assigning the pointer passed.

Map* newMap(char* name) {
}

addCategory

int addCategory(Map* map, char* name) {
}

Given a map, add a category with name name. If the category already exists, do nothing and return a 1. Else, add the category in the proper spot within the list for lexicographical ordering and return a 0.

Lexicographical order is similar to alphabetical order, but generalized to all possible strings passed (letters, numbers, punctuation, etc). You can use the strcmp method in string.h to compare two strings lexicographically.

An example is provided in the Examples section.

addBusiness

int addBusiness(Map* map, char* category, char* name, int num_employees) {
}

Given a map, add a business with the name name and the number of employees num_employees to the category with name category. Businesses should be ordered according to the number of employees descending. When adding a new business, if existing businesses have the same number of employees, add the new business after the existing ones.

If the category does not exists, do nothing and return 1. Else, add the business and return a 0.

If the business already exists, simply update the number of employees in the existing business to be the passed number of employees.

An example is provided in the Examples section.

removeCategory

int removeCategory(Map* map, char* name) {
}

Remove the category with name name from the list. If the category does not exists, return 1, else, remove it and return 0.

When you remove a category, be sure to free the memory assigned to the category. Also do not forget to remove every business that was stored in the category and free the memory of each one.

removeBusiness

int removeBusiness(Map* map, char* category, char* name) {
}

Remove the business with name name under category category from the list. If the category does not exists, return 1. If the business does not exists, return 2. Else, remove the business and return 0.

When you remove a business, be sure to free the memory allocated for the business.

countBusinesses

int countBusinesses(Map* map, char* category, int min_employees, int max_employees) {
}

Count the number of businesses in category category with a number of employees less than or equal to max_employees and greater than or equal to min_employees. Return -1 if the category does not exist. For example:

int small_offices = countBusinesses(map, "Office", 0, 50); // Returns 2

display

void display(Map* map) {
}

The display method should display every category in the map and every business in that category, formatted as:

map_name
category_name: business_name (number_of_employees), business_name (number_of_employees), etc.
category_name: business_name (number_of_employees), business_name (number_of_employees), etc.
etc.

Where map_name is the name of the map, category_name is the name of the category, business_name is the name of the business, and number_of_employees is the number of employees.

If there are no categories, display:

map_name
Map is empty

For example, if the map name is Tuscaloosa, the output would be:

Tuscaloosa
Map is empty

If a category has no businesses, display:

category_name: Empty

Examples

Given a main:

int main() {
    Map* map = newMap("TV City");

    addCategory(map, "Office");
    addBusiness(map, "Office", "Dunder Mifflin Utica", 10);

    display(map);
    printf("-----\n");

    addBusiness(map, "Office", "Dunder Mifflin Scranton", 19);

    display(map);
    printf("-----\n");

    addCategory(map, "Food and Drink");
    addBusiness(map, "Food and Drink", "Jasmine Dragon", 7);

    addCategory(map, "Hospitals");
    addBusiness(map, "Hospitals", "Princeton-Plainsboro Teaching Hospital", 8672);
    addBusiness(map, "Hospitals", "Seattle Grace Hospital", 6824);

    addCategory(map, "Gas");

    display(map);
    printf("-----\n");

    removeCategory(map, "Food and Drink");

    display(map);
    printf("-----\n");

    removeBusiness(map, "Hospitals", "Princeton-Plainsboro Teaching Hospital");

    display(map);
    printf("-----\n");

    printf("Number of very small office businesses: %d\n", countBusinesses(map, "Office", 0, 10));
}

The expected output would be:

TV City
Office: Dunder Mifflin Utica (10)
-----
TV City
Office: Dunder Mifflin Scranton (19), Dunder Mifflin Utica (10)
-----
TV City
Food and Drink: Jasmine Dragon (7)
Gas: Empty
Hospitals: Princeton-Plainsboro Teaching Hospital (8672), Seattle Grace Hospital (6824)
Office: Dunder Mifflin Scranton (19), Dunder Mifflin Utica (10)
-----
TV City
Gas: Empty
Hospitals: Princeton-Plainsboro Teaching Hospital (8672), Seattle Grace Hospital (6824)
Office: Dunder Mifflin Scranton (19), Dunder Mifflin Utica (10)
-----
TV City
Gas: Empty
Hospitals: Seattle Grace Hospital (6824)
Office: Dunder Mifflin Scranton (19), Dunder Mifflin Utica (10)
-----
Number of very small office businesses: 1